An efficient overlay for unstructured P2P file sharing over MANET using underlying cluster-based routing.
Peer-to-peer (P2P) network is a robust, distributed and fault tolerant network architecture for sharing resources like CPU, memory and files. The existing approaches for P2P over wired network (Internet) can be roughly classified into structured, unstructured and hybrid architecture . Each of them has its own applications and advantages. Mobile and wireless technology has achieved great progress in recent years. Today's cell phones, PDAs and other handheld devices have larger memory, higher processing capability and richer functionalities. The user can store more audio, video, text and image data with handheld devices. These devices are also equipped with low radio range technology, like Bluetooth and Wi-Fi. By means of the low radio range technology, they can communicate with each other without using communication infrastructure (e.g. cellular infrastructure) and form a mobile ad hoc network (MANET). Each node in MANET works as both a host (for sending/receiving the data) and a router (forwarding the data for other nodes). It is deployed in the places where infrastructure is either not available, for example disaster scenario, or too expensive. Due to high capability of the mobile devices, P2P networks can be deployed over MANET composed of mobile devices. There are various P2P applications over this kind of MANET. For example, the users equipped with the cell phones, PDAs or other handheld devices, are communicating through low radio range. They can form a P2P network for sharing audio/video clips, pictures, files and other information. Possible file sharing application scenarios can be found at airport lounges, music concerts, bus stops, railway stations and cafeteria.
The approaches proposed for P2P over Internet  cannot be directly applied to the ones over MANETs due to the unique characteristics of MANETs, such as nodes' mobility, scarce of power energy, limited memory, and infrastructure less nature. Recently, several schemes have been proposed for P2P over MANETs  . The existing approaches for unstructured P2P over MANETs [l4]  use flat underlying routing protocol, like AODV . Flat routing protocol for MANETs produces heavy traffic overhead when scaled up .
Our approach is targeting the MANET's scenarios where not all the nodes are to share and access the files, i.e. some nodes are peers and others are non-peers. But non-peer nodes are cooperative in forwarding the data for other peers. Our approach builds up an efficient overlay for unstructured P2P file sharing over MANET using underlying cluster-based routing protocol (CBRP) . In our approach, one of the peers in the P2P network is used as a root-peer to connect all peers. Using the information of directly connected and 2-hop away (logically) neighbor peers, each peer builds up a minimum-spanning tree to remove far away redundant links and to construct an overlay closer to the physical network. Due to the on-demand nature of inter-cluster routing of CBRP, a requesting peer may not have the route to the source peer of the file at its routing agent to retrieve the file. And to retrieve file, the path in overlay between the requesting peer and the source peer of the file may be longer than their shortest one in the physical network. So the positioning algorithms of MANET  are combined with CBRP to forward the unicast packet via location-based routing. Thus, in our approach, a peer can retrieve the file from the source peer via shorter path in the physical network instead of following the longer path in overlay network. The simulation results show that our approach outperforms random overlay approach adopted by Gnutella  in term of routing overhead, average file-discovery delay, false-negative ratio and average path-stretch value.
We present the related work in Section 2. The limitations of random unstructured P2P overlay over MANET are discussed in Section 3. The detailed description of our approach is presented in Section 4. Section 5 presents the simulation and results. Finally, Section 6 concludes the paper.
2. Related Work
Many routing protocols have been proposed for MANETs. These protocols can be classified into different categories according to different criteria. Each of them has its own applications and advantages. By the manner in which they react to network topology, the routing protocols can be classified into reactive and proactive routing protocols. Reactive routing protocol finds the route on demand, i.e. it finds the route to a destination when the data is to be sent to that destination. AODV  is one of its example. Reactive protocols have larger delivery delay and are not efficient for higher traffic. Proactive routing protocols periodically update routing information to all nodes in the network regardless of whether or not the data is to be sent to those nodes, e.g. OLSR . Proactive routing can have unnecessary route discovery producing more extra traffic overhead. By the role of routing nodes and the organization of the network, routing protocols can be classified into flat protocols and hierarchical/cluster-based routing protocols. In flat routing, every node has the same role and whole network is considered as a single flat structure, e.g. AODV. Flat routing protocols are suitable for small network size and their performance degrades as the size of network grows. In cluster-based routing, the nodes are grouped into clusters. Each cluster has one node as a cluster-head and the inter-cluster communication is done through gateway nodes. By grouping nodes into clusters, selected nodes forwards the route discovery packet reducing redundant traffic. Cluster-based routing protocol scales well as the network's size grows. The example of cluster-based routing protocol includes CBRP . According to the knowledge of location information of nodes, the routing protocols for MANET can be classified into geographic and non-geographic routing. Geographic routing utilizes the location information of the nodes during routing process, e.g. GPSR . The position of a node can be obtained through GPS or via other schemes like in . In geographic routing, the location information are used to confine the route search space into a smaller estimated range reducing routing overhead. In geographic routing, only location information of the nodes is maintained on the router therefore it scales better in term of per-router state. There also exists an approach called LORA-CBF  which uses location-based forwarding with cluster-based routing protocol (CBRP). LORA-CBF has some ambiguity, like how to avoid local-maxima  etc. An overview of CBRP and GPSR is following, because our approach uses these protocols.
Through periodic HELLO message exchange, in CBRP, a node obtains the link-state information of its neighbor nodes upto 2-hops. By grouping nodes into clusters, the CBRP efficiently minimizes the flooding traffic during route discovery and speeds up this process as well. Therefore CBRP scales well with increasing number of nodes in the network. The detail specification can be found in CBRP .
GPSR  assumes that every node in the network knows its own position through GPS or via other scheme like in . In addition to this, every node announces its own position to its one-hop neighbor nodes through periodic HELLO broadcast. Thus every node knows the position of its one-hop neighbor nodes in the network. A unicast packet has the locations of its source node and the destination node along with their node-IDs. Therefore GPSR uses greedy forwarding algorithm to forward packets to a node that is always progressively closer to the destination. In regions of the network where such a greedy path does not exist (i.e., the only path requires that one move temporarily farther away from the destination), GPSR recovers by forwarding in perimeter mode. In perimeter mode, a packet traverses successively closer faces of a planar sub-graph of the full radio network connectivity graph. This is going on until the packet reaches a node closer to the destination, where greedy forwarding resumes.
The approaches for unstructured P2P file sharing over MANET in  did not maintain overlay network among the peers. In these approaches, the file-lookup request was flooded in the whole network similar to the route request of flat routing protocol AODV . But this was content-based, i.e. it returned not only the ID of the source peer but also the route to the source peer. Flooding a packet in the network using flat routing is inefficient and does not scale well . In , using swarm-intelligence, the authors proposed a solution, called P2PSI, for addressing free-riding and hot-spot problem of unstructured P2P file sharing over MANETs. They divided the files into different categories and a pheromone-table was built up on each node which had routing information for each category of files instead of an individual file. It would perform poorly if the peers store diverse types of files. In , the authors evaluated the performance of Gnutella using various flat underlying reactive and proactive routing protocols. They also built a random overlay for all the underlying routing protocols and did not consider the optimization of Gnutella over MANETs. Diego et al.  improved the unstructured P2P over MANET using Gossiping  mechanism of MANET routing protocol. They determined the forwarding probability of a link based on the network load. Thus, in their approach, the packet was forwarded on the lower load link. They also used AODV  as underlying routing.
3. Limitations of Random Overlay
The flooding-based approaches for unstructured P2P network over MANET are inefficient and do not scale well. While the random overlay of Gnutella over AODV  has the following limitations.
3.1 Redundant Traffic in the Network
In Gnutella , a peer maintains connection with neighbor peers according to the values of lower bound (LB) and upper bound (UB) for the number of neighbors. It would lead to redundant traffic in the network. For example, let's take the part of a P2P network structure in Fig. 1-(a). For 4 and 8 as the value of LB and UB respectively, the overlay network of Fig. 1-(a) is shown in Fig. 1-(b). Let P1 sends the file-lookup request to its neighbor peers P2, P3, P4 and P5 for file discovery purpose. To deliver the file-lookup request from P1 to P2, P3, P4 and P5, it will produce eight transmissions in the physical network as shown through thin arrows in Fig. 1-(a). Then P4 will forward the same file-lookup request to its neighbor peers P2, P3, P6 and P5 producing eleven more transmissions in the physical network as shown through bold arrows in the Fig. 1-(a). We can learn from the above scenario that both P1 and P4 send redundant probe (ping) messages to their neighbor peers P2, P3 and P5 in order to maintain connectivity. In MANET, these redundant transmissions would consume a lot of bandwidth and energy.
3.2 P2P Network Partition
Though, in Gnutella over MANET , each peer maintains neighbor connection with certain number of peers. Despite this, a P2P network partition may still occur while the physical network is connected. For example, the overlay network among the peers is established as shown in Fig. 2-(a), taking 4 as the maximum size of neighbor list of a peer . The distance of the links in the physical network is shown as the weight of the links. When P6 leaves P2P network, the topology becomes the one as shown in Fig. 2-(b). This is because a peer receives early response for a request from the physically closer neighbor peers. P2P network partition exists though the underlying physical network is fully connected and each peer maintains connection with maximum number of neighbor peers according to . In this scenario, the file-lookup query from one partition would not be able to reach other partition.
[FIGURE 1 OMITTED]
3.3 Tradeoff between Traffic Overhead and P2P Network Partition
There is a tradeoff between redundant traffic and P2P network partition on the size of neighbor list of a peer (the number of neighbor peers that a peer can have connections with) in Gnutella over MANET. A P2P scenario having larger neighbor list would produce more redundant traffic in the network and have less chances of P2P network partition, and vice-versa. The selection of the neighbor list size is influenced by the distribution of peers and the peers ratio in the network. It is difficult to get an optimum neighbor list size in the P2P network over MANET due to the dynamic nature of both P2P network and MANET.
3.4 Larger Value of Path-Stretch for File Retrieval
Path-stretch is the ratio of the path length between two peers used for file retrieval to their shortest path length in the physical network. In , upon receiving the reply from the source peer P1 for a file-lookup request, a peer P may not have the route to P1 at its routing agent due to on-demand nature of AODV. To retrieve the file by P from P1 following the path of P2P overlay, this route may be longer than the one in physical network between P and P1. Therefore the value of path stretch in Gnutella over AODV would be larger.
4. Proposed Algorithm
Our objective is to develop an efficient overlay for unstructured P2P file sharing over MANET with the consideration of underlying routing. We do not use reactive routing, like AODV, as underlying routing for P2P over MANET due to the following reason. Receiving the QUERY_HIT (file-lookup reply for a file-lookup request), a requesting peer may not have the route at its routing agent to the source peer of the file to retrieve the file due to reactive nature of AODV. In this case, the requesting peer can retrieve the file from the source peer following the route in P2P overlay. This would have larger path length than the possible shortest path between the requesting peer and source peer in the physical network. This would increase traffic and file-retrieval delay. Proactive routing protocol, like OLSR, maintains the routing information to all the nodes in the network regardless of whether or not the data is to be sent to those nodes. This type of routing does not scale for larger network . By grouping nodes of network into clusters, selected nodes forward the route discovery packet reducing redundant traffic in cluster-based routing protocols, e.g. CBRP . These routing protocols scale well as the network's size grows. Due to reactive nature of inter-cluster routing of CBRP, geographic information of nodes  is used so that a requesting peer can retrieve the file from the source peer via shorter path in the physical network, the detail is following.
[FIGURE 2 OMITTED]
We use CBRP as an underlying routing protocol with following features: expanding-ring-search (ERS) algorithm , location-based forwarding  and local repair as in . In our system, a node knows its position through the positioning algorithm in . This is because in our approach, every node in the network periodically exchanges HELLO messages with its 1-hop nodes to construct and maintain clusters. In addition to other information, a node also announces its location to its 1-hop neighbor nodes in HELLO messages. Thus a node has the location information of its one-hop neighbor nodes. In our system, the unicast packet is forwarded using location-based algorithm GPSR  with following modification. In our approach a node knows the ID of its neighbor nodes upto 2-hops. Therefore, a node forwards the unicast packet to the destination directly without using location-based algorithm provided the destination node lies within its range of 2-hops in the physical network. This is done in order to reduce the chances of local-maxima . If a node cannot forward the unicast packet to the destination then the forwarding node sends the route error message to the source node of the packet. This disconnection may be because that the destination node is switched off or the destination node has moved outside the range of 2-hops from the forwarding node. In our system the nodes self-organize themselves into clusters as in CBRP . The route-request and the broadcast messages are forwarded as in CBRP without source routing. Instead of source-routing of CBRP, in our approach the route-request message has the location information of the source node. Therefore the data packets and other unicast packets are forwarded using location-based algorithm GPSR . A node maintains the location information of the nodes at the routing agent, so that other applications can also utilize these information for routing purpose.
Our system has a root-peer connecting all peers. The process is illustrated as follows. When two peers, say peer A and peer B, establish neighbor relationship, the root-peer is used as a reference point to designate one of them to be responsible for maintaining the neighbor relationship. Peer A sets its neighbor B's state as NBIND if A is closer to the root-peer or has the lowest ID in case of tie (when both A and B are at the equal distance from the root-peer). Otherwise, peer B's state is set to BIND and A is set to NBIND. A peer periodically sends probe messages to the neighbor peer with BIND state to maintain neighbor relationship, and receives probe messages from a neighbor peer with NBIND state. Each peer (except the root-peer) connects to at least one other peer with BIND state to ensure the connectivity of the P2P network. In our system, each peer maintains a peer-routing table that stores the information of the root-peer and neighbor peers, as shown in Fig. 4. The distance of the peer/root-peer represents the number of hops. Each peer also maintains a local repository which contains index of its stored files. The state transition diagram of our approach for connection establishment and file-discovery is shown in Fig. 3. The detailed description of the basic operations of our approach is given as follows.
When a node n wants to join the P2P network, the node n gets the existing physically closer surrounding peers of the P2P network as follows. The join peer first contacts its routing agent so that the routing agent can inform the peer of the P2P traffic passed through. Then the join peer broadcasts the join-request message (JRQST) using ERS algorithm to find the closest online peer in the P2P network as follows. The JRQST contains the location of the requesting node. The value of time-to-live in the JRQST is set to as given below:
TTL = 2 + (NC *3) (1)
where NC defines that JRQST can reach to the nodes in the physical network after passing through (NC+1) cluster-heads on a path. For example, for NC=1, the JRQST at least will reach to a node that lies in the cluster of sending node and the immediate neighbor clusters of the sending node. That is, for NC=1, the JRQST will pass through two cluster-heads on a path in the physical network. Receiving JRQST, a node sends the join-reply message (JRPLY) to the join peer provided the receiving node is a peer. Receiving JRQST, a gateway node decrements the TTL value of JRQST and forwards the JRQST to the corresponding cluster-head, as described in CBRP . Upon receiving the JRQST, a cluster-head also decrements the TTL value and then forwards further the JRQST with a list of unvisited adjacent neighbor clusters by broadcasting to its members provided the TTL value of the JRQST is greater than zero. JRPLY is sent to the join peer using location-based routing GPSR . Sending JRQST is stopped when the join peer receives JRPLY from at least one other peer or when the TTL reaches a maximum threshold value, which is one of following two cases
* The time-to-live (TTL) value of the ERS algorithm reaches the maximum threshold value and the join peer does not receive any JRPLY. The join peer assumes that there is no other peer of the P2P network and itself becomes the root-peer.
* The join peer receives JRPLY from at least one other closest peer. JRPLY of peer P contains P's directly connected neighbor peers, the root-peer, their distance from P, and their location. This means that the senders of JRPLY and their directly connected neighbor peers are the physically closer surrounding peers of the join peer.
After receiving JRPLY, the join peer sends connect-request message (CRQST) to each of surrounding peers to establish the neighbor relationship with them. The CRQST is forwarded to the destination peer via location-based algorithm. CRQST of the peer P also contains the location of P, P's directly connected neighbor peers, their locations and their distances from P, and the root-peer along with its distance from P. Receiving CRQST, the receiving peer stores the information of CRQST in its peer-routing table and sends the connect-reply message (CRPLY) via location-based forwarding GPSR algorithm. The CRPLY contains similar fields as in CRQST. Due to on-demand nature of the inter-cluster routing in CBRP and the use of ERS algorithm, a peer may not get the route and its distance to the root-peer from its routing agent. In this case, the peer calculates its distance to the root-peer as the total minimum distance from itself to its directly connected neighbor peer plus the distance from that neighbor peer to the root-peer, as shown by following equation
[D.sub.P] = [min.sub.n] ([D.sub.P - Q] + [D.sub.Q]) (2)
where n is number of directly connected neighbor peers of P, [D.sub.P] is the distance from peer P to the root-peer, [D.sub.P-Q] is the distance from peer P to Q, and Q is a directly connected neighbor peer of P in P2P overlay. The neighbor relationship between two peers is adjusted as discussed above. The peer constructs a connected graph having itself, its directly connected and 2-hop away (logically) neighbor peers as vertices, and assigning the number of hops as the weight of the links between two logically linked peers in the physical network. Using this connected graph, then the peer executes minimum-spanning-tree (MST) algorithm with itself as a source vertex. The peer drops the connection with a directly connected neighbor peer to which it does not have direct link in MST. The peer also establishes neighbor connection with a new peer which is not previously directly connected neighbor peer but has a direct link in MST.
To illustrate the joining process of a peer through an example, a part of P2P network is shown in Fig. 4-(a) with P1 as the root-peer. Now node N3 wants to join the P2P network. It sends the JRQST using the ERS algorithm and receives JRPLY from P2. Thus N3 comes to know that its surrounding peers are P1 and P2. Then N3 sends CRQST to these surrounding peers. After exchanging CRQST and CRPLY, the resulting physical topology is shown in Fig. 4-(b). The corresponding overlay of Fig. 4-(b) is shown in Fig. 4-(c). The connected graph of P1 is shown in Fig. 4-(d). After executing the MST algorithm, the resulting minimum-spanning tree of P1 is shown through bold lines in Fig. 4-(d). Then P1 identifies that its previous neighbor peer P2 is no longer its direct neighbor in MST while the new join peer N3 is. So P1 drops its connection with P2 and maintains its connection with N3. The resulting final overlay topology is shown in Fig. 4-(e) and its corresponding physical network is given in Fig. 4-(f). We can tell that this is a more efficient overlay with a topology closer to the physical network.
[FIGURE 3 OMITTED]
[FIGURE 4 OMITTED]
Each peer periodically sends out probe messages to a neighbor peer with BIND state to update and maintain connectivity. Upon receiving the probe message, the receiving peer also replies to the sender of the probe message. The probe message of the peer P also contains the location of P, P's directly connected neighbor peers, their locations, and their distances from P, and the root-peer along with its distance from P. After certain number of retries, if a peer P does not receive the reply for the probe messages from a neighbor peer P1 with BIND state, the peer P invokes recovery operation for the peer P1. When a peer P does not receive the probe message from a neighbor peer P2 of NBIND state and the time period of P2 expires, the peer P removes P2 from its peer-routing table.
When a peer wants to leave the P2P file-sharing network, it can inform its neighbor peers about its leaving so that the neighbor peers invoke a recovery operation. Normally, a peer does not inform its neighbor peers about its leaving.
When a peer P detects that one of its directly connected neighbor peers, say P1, with BIND state is disconnected, it invokes the recovery procedure. The disconnection of the peer P1 may be caused by nodes' mobility, or the peer P1 has left the P2P network or been switched off. In any case, the peer P broadcasts the recovery request message (RRQST) with multi-target using the ERS algorithm. The initial TTL of ERS algorithm is set to the distance between the disconnected peer P1 and peer P plus one. The list of target nodes in RRQST contains the disconnected peer P1 and the directly connected neighbor peers of P1. RRQST is forwarded in the similar way as CRQST is forwarded. Upon receiving RRQST, the peer also sends a recovery reply message (RRPLY) to the requesting peer even though it is not in the list of target nodes. This is implemented in order to ensure an efficient overlay. Upon receiving the RRQST, the target node sends the recovery-reply message (RRPLY). RRPLY is forwarded to the requesting peer in similar way as JRPLY is forwarded. RRPLY contains the same fields as in probe message. Sending RRQST is stopped when the requesting peer receives the RRPLY either from the disconnected peer or from all of the directly connected neighbor peers of the disconnected peer. Receiving RRPLY, the peer P sends the CRQST to establish connection with the senders of RRPLY. Then the peer executes the MST algorithm to remove the far away redundant links. The absence of a peer P1 can be detected by a peer P through probe messages or from the routing agent of P. If the disconnected neighbor peer is the root-peer and has left the P2P network, one of the closest directly connected neighbor peers of the disconnected root-peer will announce itself as the new root-peer. In case of tie, the one having the lowest ID is elected as the new root-peer. Then the new root-peer announces itself to the other peers in the P2P network in the same way as it sends the file-lookup query.
4.5 File Discovery
As our approach is based on unstructured P2P network; we use keyword-based searching to find a file in the network. When a peer wants to retrieve a file, it sends out the file-lookup request message (FRQST) to all of its directly connected neighbor peers. Upon receiving a file-lookup request, a peer sends the file-reply message (FRPLY) to the requesting peer provided a matching file is found in its local repository. Otherwise, the file-lookup request is forwarded to its directly connected neighbor peers excluding the one from which the request is received. The FRQST and FRPLY messages are forwarded using location-based forwarding GPSR algorithm. Receiving the FRPLY for a file-lookup request, the peer invokes the file-access operation. Due to forwarding the FRPLY by a node using location-based algorithm, therefore the file is retrieved by a peer via shorter path in the physical network in our approach. If the requesting peer does not receive any reply for a file-lookup request within certain period of time, it resends the file-lookup request provided the number of retries does not exceed the maximum threshold value.
The requesting peer may receive reply for a file-lookup request from multiple source peers. It retrieves the file from a source peer having shortest distance using location-based forwarding algorithm. The file is retrieved in blocks and complete control over the transfer of the blocks is kept on the receiver side. The block size is selected so that it can be accommodated in a single packet. A scheduling algorithm like  can be implemented, for the sake of simplicity, for the lost of blocks. The lost of a block may be caused by packet collision or link breakdown.
We implement Gnutella over AODV as in  with 4 and 8 as the value of LB and UB respectively. We use simulator ns-2 to conduct simulation to compare our approach with Gnutella . The specification of the simulation environment is IEEE 802.11 MAC Layer, total 100 nodes are moving randomly in simulation area 1000X1000, 250m as the node's radio range, total simulation time is 1000 seconds, and bandwidth is 2MB. We choose 2 as the value of number of file retries and Ping/Probe interval 8 seconds. Each node monitors the outgoing link failure from the feedback of the IEEE 802.11 MAC layer. In our scenario the nodes randomly join/leave the P2P file-sharing network while maintaining the specified ratio of peers to all nodes. The mobility scenarios are created according to RandomWayPoint mobility model using Bonnmotion  to ensure that the physical network is connected. The file-discovery is randomly initiated for total 100 random files by the peers in the network. We study the performance metrics for peer discovery, overlay maintenance and file-discovery of the resulting overlays by varying peers ratio and the maximum moving speed of nodes. Peers ratio is the ratio between the number of peers and the the total number of nodes in the network. The following metrics are used for comparison,
* Traffic overhead: The total number of packets transmitted at routing layer.
* Average file-discovery delay: The average time elapsed from the moment when a file-lookup query is sent to the moment when the first reply is received.
* False-negative (FN) ratio: The ratio between the numbers of unresolved file-lookup queries for the files that exist in P2P network and the total number of initiated file-lookup queries.
* Path-stretch: The ratio of the path length between two peers used for file retrieval and the length of their shortest path in the physical network.
5.1 Comparison of Traffic Overhead
Fig. 5 shows the routing traffic of both approaches in Kilo unit (thousand). In Fig. 5, our approach has higher traffic overhead than Gnutella  when the peers ratio is 5% and 15%. This is because, the CBRP as an underlying routing in our approach constructs and maintains the clusters in the network by periodic exchange of HELLO messages among the nodes. In Gnutella , with the increase of peers ratio in the network, the number of redundant links that a peer has in P2P overlay increases. This causes more redundant traffic in the network. In our approach, with the increase of peers ratio, the peers in the network become less dispersed and the P2P overlay is closer to the physical network. Therefore, in our approach, with the increase of peers ratio in the network, the length of overlay link between two logically linked peers decreases in the physical network. This decreases the traffic overhead per peer in the network. The use of CBRP with location-aided underlying routing further reduces the flooding traffic in our approach. Due to these reasons, with the increase of peers ratio in the network, the increase in routing traffic of our approach is less as compared to Gnutella over AODV. With the increase of moving speed of nodes, the traffic overhead increases in both approaches. This is because, with the increase of moving speed of nodes, the links disconnect more frequently. However due to CBRP with location-aided underlying routing, with the increase of moving speed of nodes, our approach produces less routing overhead in the network as compared to Gnutella over AODV when the peers ratio in the network is higher than 25%.
[FIGURE 5 OMITTED]
Generally the nodes' mobility has significant effect in MANETs in term of routing overhead. But Fig. 5 shows that in our scenarios the nodes' mobility does not appear as a significant factor because we consider the dense MANET scenario where the nodes' mobility does not have higher affect on routing traffic.
By reducing traffic overhead in MANET, the chances of packet collision, the consumption of energy and the usage of bandwidth would be reduced which would result in the increased performance of network and in increased network longevity. Thus, by reducing traffic overhead, our approach would increase the network performance and network longevity.
[FIGURE 6 OMITTED]
5.2 Comparison of the Average File-Discovery Delay
Gnutella maintains redundant links among the peers and our approach avoids redundant links, therefore, one can expect shorter average file-discovery delay in Gnutella. However, Fig. 6 shows that our approach has shorter average-file discovery delay. It is because of the following four reasons. First, Gnutella has higher traffic overhead increasing the contention delay to access the medium. Second, in our approach, the file-lookup query is forwarded along the shortest path in the physical network. This is because our P2P overlay is closer to the physical network. Third, Gnutella does not guarantee that a peer always establish connection with closer neighbor peers in the physical network. Forth, our approach uses CBRP with location-aided underlying routing which has route-shortening and local-repair features reducing redundant traffic. These figures also show that by increasing peers ratio in the network and/or by increasing the maximum moving speed of nodes, the average file-discovery delay of both approaches increases. It is because, traffic overhead increases with the increase of nodes' mobility and peers ratio in the network resulting in the increased contention delay to access the medium and more packet collision. Fig. 6 shows that the effect of nodes' mobility is not so significant on file-discovery delays. This is because that we have taken the average value of file-discovery delay and the file-discovery delay is presented in millisecond.
[FIGURE 7 OMITTED]
At the speed of 1.6 m/s, in mobile scenario the nodes come closer to each other which leads to less routing overhead as shown in Fig. 5-(d). This leads to decreased average file-discovery latency as shown in Fig. 6-(d).
5.3 Comparison of the False-Negative (FN) Ratio
As P2P network partition may occur in Gnutella  over AODV, therefore we investigate two types of false-negative (FN): false-negative due to P2P network partition (FNP) and false-negative due to packet collision (FNC). Fig. 7 shows that P2P network partition occurs in Gnutella if the peers ratio is higher which produces false-negative due to P2P network partition. Since P2P network partition does not occur in our approach, only false-negative due to packet collision exists in our approach. These figures show that normally the P2P network partition in Gnutella  over MANET occurs when the peers ratio in the network is greater than 15%. These figures also show that the number of FNC is larger than the number of FNP in Gnutella. The false-negative ratio is smaller in our approach as compared to Gnutella. This is because our approach has lower traffic overhead reducing the chances of packet collision. We can learn from the figures that the FN ratio increases with the increase of peers ratio and the nodes' maximum moving speed in both approaches. This is because with the increase of peers ratio, routing traffic increases causing larger contention delay and more packet collisions in the network. With the increase of nodes' moving speed, the topology changes more frequently which causes more routing traffic and more chances of packet collision in the network.
5.4 Comparison of the Average Path-Stretch
Due to on-demand route-discovery of AODV, in Gnutella  over AODV, receiving the reply from the source peer P1 for a file-lookup request, a peer P may not have the route to P1 at its routing agent. To retrieve the file by P from P1 following the path of P2P overlay, this route may be longer than the shortest path in physical network between P and P1. Therefore, the value of path stretch in Gnutella over AODV is larger. In our approach, every node has the location information of its neighbor nodes in its range of 2-hops and the location information of the source peer is included in the file-lookup request. Therefore by using GPSR forwarding algorithm, in our approach the file is retrieved via shorter route in the physical network. From Fig. 8, therefore the value of average path-stretch is lower in our approach as compared to Gnutella over AODV.
Fig. 8 shows that the path-stretch is greater than one even in our approach. This is because, in our approach, sometime local-maxima  occurs in location-based forwarding which leads to the longer route. In Gnutella over AODV, the average path-stretch is greater than one even for 5% peers ratio while the value of LB is 4. The reason is that AODV uses flooding mechanism for route-discovery. In flooding mechanism, a node forwards the broadcast packet after short random interval in order to avoid the packet collision. In flooding mechanism, first arrived packet is processed and the remaining duplicate broadcast packets are discarded at a node. Therefore, flooding mechanism also does not guarantee the shortest path between two peers in the physical network even though the two peers have direct neighbor connection in P2P overlay.
Fig. 8 shows, in Gnutella over AODV, the average path-stretch value increases with the increase of peers ratio. This is because the indirect connections between two peers in the overlay increases with the increased peers ratio. Therefore, its chances increases that a peer P receives the reply for a file-lookup request from another peer P1 such that P1 is more hops away from P in overlay network. This increases the difference between the path length of P1 from P in the overlay network and the path length of P1 from P in the physical network.
[FIGURE 8 OMITTED]
The traditional unstructured P2P file-sharing over MANET causes redundant transmissions and P2P network partition while the physical network is connected. We proposed an approach to construct an efficient unstructured P2P overlay over MANET using underlying cluster-based routing (CBRP). A root-peer in the P2P network was introduced to connect all peers. We proposed to construct a minimum-spanning tree (MST) at a peer P consisting of P itself, P's directly connected neighbor peers and 2-hop away neighbor peers of P. This was used to remove far away redundant links at the peer P. Due to on-demand nature of inter-cluster routing of CBRP, the positioning algorithm for MANET was used to retrieve the file by a peer from the source peer via shorter path in the physical network. The simulation results showed that our approach outperformed the random overlay approach adopted by Gnutella  in term of routing overhead, average file-discovery delay, false-negative ratio and average path-stretch value.
There are certain possible optimizations for performance improvement of our approach. For example, a node can use multicasting approaches  to send the file-lookup request to its neighbor peers. This would reduce the number of transmissions while ensuring its reliability. The location information can also be used to elect the most stable node as a cluster-head instead of using lowest-ID scheme. These optimizations will be considered in the future work.
Received March 16, 2010; revised April 18, 2010; revised June 7, 2010; revised July 12, 2010; accepted August 16, 2010; published October 30, 2010
 E. Meshkova, J. Riihijrvi, M. Petrova and P. Mhnen, "A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks," Computer Networks, vol. 52, no. 11, pp. 2097-2128, 2008.
 I. Stoica, R. Morris, D. Karger, M.F. Kaashoek and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for internet applications," in Proc. of the ACM SIGCOMM 01 Conf., San Diego, California, USA, Aug. 2001.
 A. Rowstron and P. Druschel, "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems," in Proc. of the IFIP/ACM International Conf. on Distributed Systems Platforms (Middleware), Germany, Nov. 2001.
 B Pourebrahimi, K.L.M. Bertels and S. Vassiliadis, "A Survey of Peer-to-Peer Networks," in Proc. of the 16th Annual Workshop ProRisc, Nov. 2005.
 M. Ripeanu, I. Foster and A. Iamnitchi, "Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design," IEEE Internet Computing Journal, vol. 6, no. 1, 2002.
 G. Turi, M. Conti and E. Gregori, "A Cross Layer Optimization of Gnutella for Mobile Ad hoc Networks," in Proc. of the ACM MobiHoc, Urbana-Champain, USA, May 2005.
 Leonardo B. Oliveira, I.G. Siqueira and A.F. Loureiro, "On the performance of ad hoc routing protocols under a peer-to-peer application," Journal of Parallel and Distributed Computing, vol. 65, no. 11, pp. 1337-1347, 2005.
 Diego N. da Hora, Daniel F. Macedo, Leonardo B. Oliveira c, Isabela G. Siqueira, Antonio A.F. Loureiro ,Jos M. Nogueira and Guy Pujolle, "Enhancing peer-to-peer content discovery techniques over mobile ad hoc networks," Computer Communications, vol. 32, no. 13-14, pp. 1445-1459, 2009.
 B. Tang, Z. Zhou, A. Kashyap and T.C Chiueh, "An Integrated Approach for P2P File Sharing on Multi-hop Wireless Networks," in Proc. of the IEEE Conference WIMOB 05, Montreal, Canada, Aug. 2005.
 R. H Hwang and C.C Hoh, "Cross-layer design of P2P file sharing over mobile ad hoc networks," Telecommunication Systems, vol. 42, no. 1-2, pp. 47-61, 2009.
 H. Sozer, M. Tekkalmaz and I. Korpeoglu, "A Peer-to-Peer File Search and Download Protocol for Wireless Ad Hoc Networks," Computer Communications, vol. 32, no. 1, pp. 41-50, Elsevier, Jan. 2009.
 M. Papadopouli and H. Schulzrinne, "Effects of Power Conservation, Wireless Coverage and Cooperation on Data Dissemination among Mobile Devices," in Proc. of the MobiHoc, Long Beach, CA, 2001.
 C. Lindemann and O. Waldhorst, "A Distributed Search Service for Peer -to- Peer File Sharing in Mobile Applications," in Proc. of the 2nd IEEE Conference P2P, Linkping, Sweden, 2002.
 A. Klemm, C. Lindemann and O. Waldhorst, "A special-purpose peer-to-peer file sharing system for mobile ad hoc networks," in Proc. of the MADNET, Sophia- Antipolis, France, Mar. 2003.
 A. Duran and C. Chung, "Mobile ad hoc P2P file sharing," in Proc. of the Wireless Communications and Networking Conference, IEEE WCNC, vol. 1, pp. 114-119, 2004.
 Abada A., Li Cui, C. Huang and H.H Chen, "A Novel Path Selection and Recovery Mechanism for MANETs P2P File Sharing Applications," in Proc. of the IEEE WCNC, HongKong, China, Mar. 2007.
 P. Hui, J. Leguay, C. Jon, J. Scott, T. Friedman and C. Vania, "Osmosis in Pocket Switched Networks," in Proc. of the First International Conf. on Communications and Networking in China, Beijing, Oct. 2006.
 U. Lee, J.S Park, S.H Lee, W. W. Ro, G. Pau and M. Gerla, "Efficient Peer-to-peer File Sharing using Network Coding in MANET," Journal of Communications and Networks (JCN), vol. 10, no. 4, pp. 422-429, 2008.
 C. Perkins, E. Belding-Royer and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing," RFC 3561, July 2003.
 M. Jiang, J. Li and Y.C. Tay, "Cluster Based Routing Protocol (CBRP)," IETF Internet Draft draft-ietf-manet-cbrp-spec-01.txt, Aug. 1999.
 S. Capkun, M. Hamdi and J.-P. Hubaux, "GPS-free Positioning in Mobile ad-hoc networks," Cluster Computing, vol. 5, no. 2, pp. 157-167, 2002.
 B. Karp and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks," in Proc. of 6th Annual International Conf. on Mobile Computing and Networking (MobiCom), Boston, Massachusetts, USA, pp. 243-254, Aug. 2000.
 T. Clausen and P. Jacquet. "Optimized Link-State Routing Protocol," IETFRFC-3626, Oct. 2003.
 S. Ral Aquino and B. Arthur Edwards, "A Reactive Location Routing Algorithm with Cluster-Based Flooding for Inter-vehicular communication," Computing and Systems, vol. 9, no. 4, pp. 297-313, CIC-IPN, ISSN, pp.1405-5546, Printed in Mexico, 2006.
 A. Helmy, S. Garg, P. Pamu and N. Nahata, "CARD: A Contact-based Architecture for Resource Discovery in Ad Hoc Network," ACM Mobile Networks and Applications (MONET), vol. 10, no. 1, pp. 99-113, 2005.
 S. M. Hedetniemi, S.T. Hedetniemi and A. L Liestaman "A survey of gossiping and broadcasting in communication networks," Networks, vol. 18, no. 4, pp. 319-349, 1988.
 Tridib Mukherjee , Sandeep K. S. Gupta and Georgios Varsamopoulos, "Analytical model for optimizing periodic route maintenance in proactive routing for manets," in Proc. of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, Crete Island, Greece, Oct. 22- 26, 2007, Chania.
 J. Deng and S. Zuyev, "On search sets of expanding ring search in wireless networks," Ad Hoc Networks, vol. 6, no. 7, pp. 1168-1181, 2008.
 http://ww.isi.edu/nsnam/ns November 2009
 M.T. Sun, L. Huang, S. Wang, A. Arora and T.H. Lai, "Reliable MAC Layer Multicast in IEEE 802.11 Wireless Networks," Wireless Communication and Mobile Computing, vol. 3, pp. 439-453, 2003.
Nadir Shah is a PhD student of Sino-German Joint Software Institute at Beihang University. He earned M.S. in Computer Science from International Islamic University, Islamabad, Pakistan in 2007. He earned B.Sc and M.Sc in Computer Science from Peshawar University, Peshawar, Pakistan in 2002 and 2005 respectively. He was a Lecturer at Department of Computer Science, COMSATS Institute of Information Technology, Abbottabad, Pakistan between August 2007 and June 2008. His current research interests include mobile ad hoc networks, peer-to-peer network, and delay/disruption tolerant networks.
* Corresponding author: Nadir Shah
Qian Depei professor at Beihang University, director of Sino-German Joint Software Institute. His current research interests include high performance computer architecture and implementation technology, distributed systems, and network performance measurement. He has published more than 100 papers.
Nadir Shah and Depei Qian Sino-German Joint Software Institute, Beihang University Beijing, P.R China [e-mail: email@example.com, firstname.lastname@example.org]
|Printer friendly Cite/link Email Feedback|
|Author:||Shah, Nadir; Qian, Depei|
|Publication:||KSII Transactions on Internet and Information Systems|
|Date:||Oct 1, 2010|
|Previous Article:||Research on anti-reader collision protocols for integrated RFID-WSNs.|
|Next Article:||Performance analysis of selection relaying schemes over different fading environments in wireless networks.|