As mobile technology advances, various new mobile devices and mobile services have appeared in the market. Mobile ad hoc networks (MANETs) [Frodigh et al. 2000] have received increasing attention by researchers as typical wireless ad hoc networks. However, there are some limitations on and difficulties with mobile communications such as the communication range of a mobile devices, bandwidth, battery power, computing power, memory space, and mobility. A peer-to-peer (P2P) distributed network architecture that is able to support communications among peers without using a server is more suitable than a client/server architecture that requires a central server to provide various services such as instant messaging, file sharing, collaborative community, IP telephony, and recommendations on a MANET.

In P2P wireless environments, the information stored in peers can be utilized in a single-layered or double-layered network [Ylianttila et al. 2008]. For example, a typical single-layered Optimized Routing Independent Overlay Network (ORION) system [Klemm et al. 2003] uses flooding as its broadcast mechanism. Hence, it could not avoid very high network traffic as the number of peers increases. For reducing network traffic, some double-layered P2P systems were developed [Han et al. 2008]. A doublelayered system classifies the peers in a network into super peers and sub-peers, and most communications are done among super peers and relay peers. By a relay peer we mean a sub-peer who connects to two adjacent super peers. However, these systems use routing schemes which are suitable for wired networks, and hence they cannot make themselves reliable systems. That is, they do not consider the MANET environments when determining a routing path between a pair of super peers.

They use either hop count or randomness in determining the routing paths. Although they reduce network traffic significantly over single-layered systems, there is still much room for reducing network traffic, because they use multicasting as the communication mechanism among super peers.

In this paper, we propose a couple of new routing schemes; the shorter-lower mobility (SLM) scheme and the reverse path (RP) routing scheme. In a double-layered system, a pair of super peers are connected indirectly via either one relay peer or two relay peers. SLM first chooses the shortest routing paths among possible routing paths and then selects a path among them associated with the relay peer who has lower mobility in order to improve the reliability of the system. RP carries out unicasting (instead of multicasting) based on the reverse path information that can be obtained during the initial file search to further reduce network traffic. The experimental results show that the proposed schemes improved the reliability of the systems and noticeably reduced network traffic.

The rest of this paper is organized as follows. Backgrounds on mobile P2P systems are provided in Section 2. Network mobility models are described in Section 3. The proposed two routing schemes are explained in Section 4. The experimental results are given in Section 5, and conclusions are made in Section 6.

ORION is one of the typical single-layered systems. In ORION, communications are done based on the flooding mechanism and each peer has a routing table and a file route table. The main disadvantage of ORION is that network traffic may be increased rapidly when there are many peers within the communication range and a very large number of different files are distributed on the network.

A double-layered P2P system has two layers, the upper layer and the lower layer. The peers in the upper layer are called super peers. Each super peer manages some neighboring peers, called sub-peers, in the lower layer. By the neighborhood of a pair of peers we mean that they are within the communication range. Each super peer maintains a route table for routing paths and a file table whose entry contains the ID, address, and file list of each of its sub-peers. A super peer sends a query message to other adjacent super peers via relay peers when searching for a file.

For example, when pepeer pP wants a certain file, it first asks its super peer for the file. The super peer then looks into its file table. If the table contains the file information, the super peer sends the location of the file back to P. Otherwise, it sends the file request query message to each of its adjacent super peers. The search process continues until the file is found.

In order for a pair of adjacent super peers P₁ and P₂ to communicate with each other, one or possibly two relay peers are required as shown in Figure 1. A solid line is a management connection line between a super peer and each of its sub-peers. A super peer and its sub-peers form a cluster. A dotted line indicates a relay connection line connecting two peers in different clusters.

In a double-layered P2P system the entire network should be updated periodically to reflect the current locations of the peers in the network; new super peers and their sub-peers are selected and routing paths among peers are reestablished. We call such a reconfiguration of the network a network update. There are three types of doublelayered systems; the Greedy system [Han et al. 2008], the maximal independent set(MIS) system [Han et al. 2008], and the mobility (MOB) system [Kim et al. 2009]. Each system has a different way of selecting super peers.

2.2.1 The Greedy system.

In the Greedy system, the number of neighboring peers, called the degree of a peer, is used for selecting super peers with the greedy set-cover approximation algorithm in [Chvatal 1979]. A peer with the largest degree is selected as a super peer among the peers who are within communication range. Ties can be broken arbitrarily. The neighboring peers become sub-peers of the super peer. Afterward, the same selection process is repeated with the rest of peers until each peer in the network becomes either a super peer or a sub-peer.

After super peer selection, relay peers should be determined to establish the routing paths among super peers. To do so, each sub-peer Q broadcasts a request message to its neighboring peers outside of its cluster?each of these peers is either a super peer or a sub-peer managed by a super peer?to get the information about the super peer that can be linked. If a super peer receives the message, then it sends its information back to Q. When a sub-peer in a different cluster receives the message, it sends the information about itself and its super peer to Q. Then Q reports all the information it received to its super peer. After each super peer collects all the information from its sub-peers, it can now select some of its sub-peers as the relay peers to connect with other adjacent super peers, and stores the routing paths associated with the relay peers into its routing table.

2.2.2 The MIS system.

The MIS system is almost the same as the Greedy system except that random numbers?instead of degrees?are used for selecting super peers. Its super peer selection mimics the randomized MIS algorithm in [Luby 1986]. For super peer selection, each peer chooses a random number at the same time. Then among the peers who are within communication range of each other, a peer who has the largest random number is selected as a super peer, and other neighboring peers become its sub-peers. The same process is repeated with the rest of peers who are not yet determined to be either super peers or sub-peers until all the peers become either super peers or sub-peers. The process to select the relay peers is the same as in the Greedy system.

2.2.3 The MOB system.

The Greedy and MIS systems select super peers with degrees and random numbers, respectively. But such values do not appropriately reflect the MANET environments. The MOB system considers a peer’s mobility for selecting super peers. In this system, a peer who has the lowest mobility among other peers within the communication range is selected as a super peer.

Suppose that a peer has higher mobility. If it happens to be a sub-peer then it may cause the reliability problem only locally. But if it is a super peer, the problem will likely affect a much larger area. For super peer selection during a network update,each peer calculates its own mobility as the total distance moved from the moment when the previous network was done until the current update time. Each peer sends its mobility value to its neighboring peers and receives their mobility values. Then each peer compares the mobility values received with its own. After such comparisons are done, the peer who has the lowest mobility value becomes a super peer. Other peers within the communication range of the super peer just selected become its subpeers.This process is repeated until all the rest of peers in the network become either super peers or sub-peers. The process for selecting the relay peers is again the same in the two other systems.

The MOB system improved reliability by enhancing the stability of clusters. Lower mobility of super peers contributes to the robustness of clusters in the system. The experimental results in [Kim et al. 2009] showed that the MOB system outperforms both the Greedy and MIS systems in terms of the hit ratio for file searches.

In a double-layered P2P system, when a super peer has to send a message, it should select a routing path toward each adjacent super peer by looking up its own routing table. In selecting a routing path in double-layered P2P systems, two schemes are used in general. One is the hop count routing scheme; a two-hop path is preferred to a three-hop path. Recall that there may be either one or two relay peers for connecting two adjacent super peers. The hop-based protocols are widely used for calculating the cost of communications. The other is the random routing scheme in which each of the possible paths are equally likely to be selected as a routing path.

For MANET research, various network mobility models have been proposed to reflect mobile user movement in the real world [Camp et al. 2002; Alshanyour and Baroudi 2008; Broch et al. 1998; Royer et al. 2001; Hong et al. 1999]. Among these models, we introduce three network mobility models for double-layered P2P systems since these three models are applied widely into most network environments.

In the random way point (RWP) model [Broch et al. 1998], each peer moves to its destination with a unique speed and a direction. After arriving at a destination, a peer is supposed to move to a new destination continuously with a new speed and direction that are determined randomly. Figure 2 shows some movements of a peer in the model.

In the random direction (RD) model [Royer et al. 2001], a peer does not have a destination. Instead, when a peer hits the boundary of the network area, its new speed and direction are determined randomly. Figure 3 illustrates a peer’s movement in the model.

In the reference point group (RPG) model [Hong et al. 1999], peers are grouped according to similar movement patterns. The peers in a group have their own speeds and directions but they move along with a reference point of the group. A reference point can be regarded as a virtual moving object and hence it has a destination with its speed and sets a new destination when it arrives at the destination. Peers in a group also move along with the reference point that has a new speed and direction. Figure 4 describes the relationship between the peers and the reference point in each group.

In this section, we propose two routing schemes to improve the reliability and to reduce network traffic for the MOB system.

Both the hop count and random routing schemes used for the double-layered P2P systems may not ensure reliable network environments, because peer mobility cannot be exploited for routing. The first proposed routing scheme SLM, however, considers both the mobility of each relay peer in the routing paths and the hop counts of the paths.

Each super peer may have multiple routing paths, each of which links with an adjacent super peer. SLM first selects the paths with the smallest hop count. Among

them, it chooses the path that has the smallest maximum movement distance of a relay peer(s) as the routing path, where the maximum movement distance of a threehop path is the longer between the distances moved by two relay peers during the period between the previous and current network updates. When there is only one relay peer in a path, its moving distance is trivially the maximum moving distance.

Figure 5 illustrates how SLM selects the routing path. There are four paths between super peers A and B. Peers C, F, and G belong to A’s cluster, while peers D, E, and H belong to B’s cluster. As shown in A’s routing table, the required information about each path is stored - the moving distance(s), the hop count, and the maximum moving distance. In this example, SLM first selects two one-hop paths, A-E-B and A- F-B, because these two paths have smaller numbers of hops than others. It finally selects A-F-B as the routing path, because the maximum moving distance of F is shorter than that of E. It is expected that routing paths with a shorter moving distance sustain more stable connections in the network.

Double-layered P2P systems reduce network traffic successfully in MANETs. However, there is still much room for improvement in traffic reduction, because multicasting is carried out among the super peers in the systems. For example, in Figure 6, when sub-peer A sends a query message to search a file x, super peer B, which manages A, forwards a message to its adjacent super peers C, D and E. However, in this case, if B knows in advance the path B-G-H-D-F, B doesn’t have to send the query message toward both C and E. The same problem occurs repeatedly whenever B asks about the same file later.

To avoid such multicasting, the second proposed routing scheme RP utilizes the reverse paths so that unicasting can be performed as much as possible. In a doublelayered P2P system, when finding a certain file, a destination peer sends a response

back to the peer who requested through the routing paths used when searching. For example, in Figure 7, when F receives the query message, then it sends a response message back to A along the routing paths backward, calling them the reverse paths. For RP, each peer stores the ID of the peer who sent a response message along with the file ID into its reverse path table. Note that no additional cost is required to establish reverse paths since the replied messages during file searches should be sent back to the senders.

The experiments were performed using a mobile network simulation tool, the network simulator NS-2 v2.33 [The network simulator NS-2]. The parameters of the experiments are given in Table I.

For the experiments, 100 peers moved around with the maximum speeds of 1~5 m/sec in a network area of 1,000 m × 1,000 m. The communication range of a peer is set to 200 m and the two ray ground radio propagation model [Rappaport 2001] was implemented. The peers movements were based on the RWP, RD and RPG mobility models. For the RPG model, ten groups were constructed. Each peer can have five files and some files can be stored in other peers redundantly. In the experiments 1,000 queries from peers in the network were assumed to be processed during the

simulation period. After every 100 seconds, a network update is performed. Each peer’s movement is measured every 10 seconds. The overall simulation for each input is performed for 1,000 seconds. Under the above environment, we used 20 test data sets as input and obtained the average values as experimental results to evaluate the performance of each system.

We evaluated the hit ratio for file searches. We tested four MOB systems with different schemes - the hop count scheme, the random scheme, SLM, and the hybrid scheme of SML and RP. Figure 8 shows the hit ratios while the maximum speed of a peer varies from 1 to 5 m/sec on the RWP, RD and RPG mobility models, respectively.

SLM showed the highest hit ratio in all the input models, since the distance between a pair of peers in the routing paths was maintained for a longer period of time. In contrast, a random routing scheme that neither considered the hop count nor peer’s mobility showed the lowest hit ratio. SLM improved the hit ratio by 3.0% (3.9%) and 5.3% (7.4%) over the hop count and random routing schemes, respectively, in the RWP (RD) model. In the RPG model, the hit ratio gaps become narrower than those in the other two models, because the communication range of each peer in the RPG model depends on the groups’ movement. Even though SLM selects the relay peers with lower mobility, some messages could not be reached at other peers when groups moved in different directions to each other.

The hit ratio of the hybrid scheme was dropped by 1.4% with respect to that of SLM, because the hybrid scheme relied on unicasting; that is, if a peer on a path deviated from the path, future searches along the path could not be successful. But the hybrid scheme showed still 1.3% and 3.7% higher average hit ratios than the hop count and random schemes, respectively.

Figure 9 shows the average number of packets for searches while the peer’s maximum speed varied from 1 to 5 m/sec. SLM showed larger numbers of packets than others for the RWP and RD models, since its hit ratio was higher than others. RP generated

many wasteful packets, since it did not consider the hop counts. This made packets detour the paths. In the RPG model, the random scheme showed the largest number of packets, because there were more chances to establish three-hop routing paths even though the hit ratio was the lowest.

The hybrid scheme reduced the number of packets over SLM for all the models. But in the RD model the hybrid scheme showed a slightly higher value than the random scheme, since the hit ratio of the random scheme was too low. From the experimental results, we could verify that the hybrid scheme reduces successfully the number of packets for file searches further by avoiding multicast among super peers.

Figure 10 compares the overall network traffic, that is, the number of packets for searches plus all the network updates during the entire simulation period. As for the number of packets for searches, each value is averaged from the results when the

peer’s maximum speed varies from 1 to 5 m/sec.

SLM showed 5.6% and 4.7% higher network traffic than the hop count and random schemes, respectively, since it had a higher hit ratio and hence there were chances to forward more packets. The reason for showing the highest network traffic by the random scheme in the RPG model is that it has more chances to establish three-hop routing paths even though the hit ratio is the lowest. The hybrid scheme did not always show the lowest traffic amount, because the two additional bytes for storing relay peers’ movement information when exchanging the routing information are required. However, the hybrid scheme showed the lowest network traffic on the average for all the input models.

The hybrid scheme reduced the overall network traffic 6.8%, 7.2%, and 2.4% over SLM on the RWP, RD, and RPG models, respectively. It also showed lower network traffic than both the hop count and random schemes. From the experimental results, we could verify that the hybrid scheme is the more effective routing scheme for reducing network traffic while maintaining higher reliability than two conventional schemes.

We proposed two new routing schemes for the double-layered P2P. SLM considers not only the hop count but also peer mobility which is one of the most critical factors in MANETs. As shown in the experimental results, the lower mobility of relay peers contributes to both the stability of clusters and the robustness of the system.

RP was also proposed to reduce network traffic further. In implementing this scheme, the overhead for space and traffic were found to be minimal. But the scheme allows searches using unicasting instead of multicasting after initial searches, resulting in a further reduction in network traffic. But RP is too weak to be a stand-alone routing scheme of a system. Hence, RP was combined with SLM to get a more effective routing scheme for double-layered P2P systems.

The experimental results showed that the proposed schemes improved the reliability of the systems and reduced network traffic noticeably.