Context-Aware Routing Method for P2P File Sharing Systems over MANET Taoufik Yeferny Khedija Arour Amel Bouzeghoub Dept. of Computer Science Dept. of Computer Science Dept. of Computer Science Faculty of Sciences of Tunis National Institute of Applied Telecom SudParis MOSIC Research Group Sciences and Technology of SAMOVAR CNRS LAB Tunis, Tunisia Tunis Paris, France Taoufik.Yeferny@it- URPAH Research Group Amel.Bouzeghoub@it- Tunis, Tunisia sudparis.eu sudparis.eu Khedija.arour@issatm.rnu.tn ABSTRACT devices are also equipped with low radio range technology, Mobile devices have achieved great progress. They allow like Bluetooth [1] and Wi-Fi [2], etc. By means of the low ra- user to store more audio, video, text and image data. These dio range technology, they can communicate with each other devices are also equipped with low radio range technology, without using communication infrastructure (e.g. Internet like Bluetooth and Wi-Fi, etc. By means of the low radio network) and form a mobile ad hoc network (MANET). Mo- range technology, they can communicate with each other bile peers that are in the transmission range of each other without using communication infrastructure (e.g. Internet can communicate with their peers directly. To communi- network) and form a mobile ad hoc network (MANET). cate with peers outside the transmission range, messages are The peers in the MANET are typically powered by bat- propagated across multiple hops in the network. Hence, P2P teries which have limited energy reservoir also they are free file sharing systems can be also deployed over MANET. Due to move from their locations at anytime. Recently, P2P the nature of MANET, these systems suffer from tow prin- file sharing systems are deployed over MANET. A chal- ciples constraints. Firstly, wireless medium is much more lenging problem in these systems is (i) the selection of best dynamic due to peer mobility and the frequent variations in peers that share pertinent resources for user’s queries and channel quality due to interference and fading [4]. Secondly, (ii) guarantee that the pertinent peers can be reached in mobile devices are battery operated and energy-limited. If a such dynamic and energy-limited environment. To tackle peer is frequently asked to provide or relay files, its battery this problem, we propose a context-aware integrated rout- would be quickly exhausted. ing method for P2P file sharing systems over MANET. Our method selects the best peers based on the query content A challenging problem in these systems is (i) the selection and the user’s profile. Furthermore, it considers the energy of best peers that share pertinent resources for user’s queries efficiency, peer mobility and peer load factors into the query and (ii) guarantee that the best peers can be reached in forwarding process to guarantee that the pertinent peers can such dynamic and energy-limited environment (query rout- be reached. ing problem). In the literature, several works proposed different tech- niques of query routing in P2P systems on wired scenarios 1. INTRODUCTION [16]. However, they are not applicable to MANET, since In the last few years, peer-to-peer file sharing systems they don’t consider the constraints of this network; thus have emerged as platforms for users to search and share they cannot grantee that the pertinent peers can be reached information over the Internet network. There are different in such dynamic and energy-limited environment. Hence, kinds of P2P systems architectures that can be roughly clas- energy efficiency and peer mobility are uncompromising fac- sified into structured, unstructured and hybrid architectures tors in the design of query routing P2P file sharing systems [7]. Nowadays, mobile and wireless technology has achieved over MANET. Several routing methods have been proposed great progress. Cell phones, PDAs and other handheld de- for P2P file sharing systems over MANET. Each of them vices have larger memory, higher processing capability and has its own advantages and limits. richer functionalities. They allow user to store more audio, video, text and image data with handheld devices. These In this paper, we propose a context-aware integrated rout- ing method for P2P file sharing systems over MANET. The key contributions of our proposal are: • The selection of best peers that share pertinent re- sources is based on the query content and the user’s profile. Indeed, each peer builds a profile of its neigh- bors. The profile contains the list of the most recent past queries and neighbor that supplied answers for. We defined a similarity function that computes the aggregate similarity of a peer to a given query. 21 • Our routing method takes into account the constraints query content. Although this protocol virtually controls the of MANET environment to guarantee that the best macroscopic usage of energy and establishes a stable link, in peers can be reached. Hence, we defined a Link stablity term of energy efficiency, fairness and incentive, between a function that combines the peer mobility and battery source and destination peers. However, it does not compro- energy factors to compute the stability of link between mise the satisfaction of user because queries are flooded re- two peers. In addition, we defined a function to guar- gardless their content. Moreover, user’s mobility is not con- antee a load balancing and palliate the congestion prob- sidered. E − U nP 2P method [14] builds an efficient overlay lem. avoiding redundant links and redundant transmissions while ensuring connectivity among the peers, it introduces a root- The rest of the paper is organized as follows. In Section peer in the P2P network connecting all other peers. Each 2, we present a critical overview of query routing methods peer maintains connection with other closest peers such that in P2P systems over MANET. Section 3 discusses our ap- it can reach the root-peer. Using the information of its di- proach. Section 4 concludes with some proposed direction rectly connected and 2-hop away (logically) neighbor peers, for further works. each peer builds up a minimum-spanning tree to identify far away peers and builds up the overlay closer to the physical 2. RELATED WORK network. Thereafter, when a peer wants to retrieve a file, it In the literature there are several points of view of the sends the query to all of its neighbor peers. routing problem in unstructured P2P systems over MANET. Bin Tang et al [15] classify the existing approaches for un- A second idea consists to define a progressive search mech- structured P2P systems over MANET into layered or inte- anism that allows to route the search queries to the best grated design approaches. neighbors. In order to find content, a peer sends a query to its best neighbors, which, in turn, forward the query to their 2.1 Layered design approach best neighbors and so on, until the query time-to-live (TTL) The layered design decouples functionalities of the appli- expires. To select the best neighbors a peer is based on some cation layer and the network layer, which enables indepen- factors (i.e. Battery energy, signal power, neighbor velocity, dent development of protocols at the two layers. In this neighbor’s content, etc.). In Data Dissemination in Mobile design, routing protocol at application layer (for example, P2P Networks [13] each peer maintains a global description Gnutella) are operated on top of an existing MANET rout- of other peers’ content (content synopses), and utilizes that ing protocol at network layer. This design is similar to the synopses in order to route queries more efficiently. A peer approach in the Internet, which layers a P2P protocol on top that receives a query searches in its local collection. If it of the existing IP infrastructure. The routing protocol at the is not possible to answer this query, it calculates a score of application layer selects the overlay neighbor to forward the peers from the global index then propagates the query to the search query then it uses an existing routing protocol at the peers, which have the greatest score. If there is no match network layer (i.e. DSR [8], AODV [11], DSDV [12], etc) between the query and the content synopses, the query is to localize this neighbor. However, due to peer mobility, forwarded to a set of random neighbors. Content synopses these overlay neighbors may not reflect the current physical must be updated whenever an object is added, deleted or topology of the ad hoc network, and thus may need a multi- its contents have changed, which generates a lot of message hop route to be reached. As a result, each such overlay hop traffic and load charge of peers. Furthermore, this method required by Gnutella at the application layer could result does not consider the mobility and the energy factors. In en- in a costly flooding-based route discovery by the multi-hop hancing peer-to-peer content discovery techniques over mo- routing protocol. bile ad hoc networks [4], the authors propose to improve the unstructured P2P over MANET using Gossiping [5] ap- 2.2 Integrated design approach proach of MANET routing protocol. This is achieved by computing the forwarding probability of a link based on the MANETs are a limited resource environment where the network load. Indeed, if a peer want to send a query it com- performance can be more important than portability and putes the forwarding probability for a given neighbor based separation of functionalities. Hence, integrated design ap- on it computational load (the queue utilization of the neigh- proach is proposed as alternative to layered design approach. bor) then forwards the query to neighbors with lower load. In integrated design, routing protocol at the application Significantly, this probability allows sending more messages layer is integrated with a MANET routing protocol at the to neighbors with lower load, while less messages are sent network layer. In the literature, there are several integrated to saturated peers. This method grantees a load balancing approaches. between peers but it floods the query regardless its content. Furthermore, it does not consider the mobility and the en- A first idea consists to build an efficient unstructured P2P ergy factors. overlay over MANET. In this overlay connections between mobile peers are closely match the physical topology of the underlying MANET. To find relevant resources for a given search query, flooding technique is used. Andrew et al [9] 3. PROPOSED APPROACH propose a decentralized and dynamic topology control pro- In this paper, we consider the pure peer-to-peer systems tocol called T CP 2P . This protocol allows each peer in (Gnutella system) over MANET and we propose new tech- MANET to select a set of neighbors according to preference niques that are more efficient than the Gnutella search. Flood- defined function that take into account the energy efficiency, ing is a fundamental file search operation in pure peer-to- fairness and incentive. After building the network topology, peer (P2P) file sharing systems, in which a peer starts the each peer routes the query to its neighbors regardless the file search procedure by broadcasting a query to a random 22 set of its neighbors, who continue to propagate it with the function, we present two principle metrics. The first one same manner to their neighbors. This procedure repeats un- takes into account the peer mobility factor to predict life- til a time-to-live (TTL) counter is decremented to 0. If a time of a link between tow peers. The second one predicts contacted peer has pertinent resources for the search query, the remaining battery energy of a given peer. it sends a query hit message to the source peer. The query hit message is routed back to the source peer through the Peer mobility reverse path of the query message. This solution generates In MANET environment peers are free to move from their a very large number of messages and it cannot quickly lo- location at anytime. In our approach we consider this im- cate the request resource. Furthermore, query hits may not portant factor, thus we predict the lifetime of a link between be received by the source peer due to the peer mobility and the forwarding peer and its neighbors. To predict the life- energy limitation. Indeed, peers in the reverse path of the time of a link i − j between the peer pi and its neighbor query message may turn off or move out of the network. nj ∈ N we are based on the RABR protocol [3] functions. This protocol operates at network layer. It predicts the life- In our approach, to find relevant resources for a specific time of a link i−j using a metric called the ”affinity” aij and user query a peer sends the query to its best neighbors, it is a measure of the time taken by peer nj to move out of which, in turn, forward the query to their best neighbors and the range of peer pi . Peers exchange beacons periodically. so on, until the query time-to-live (TTL) expires. Neighbor- Peer pi periodically samples, for every 4t time units, the ing peers refer to those peers which are within the transmis- strength of the beacon signals received from peer nj . The sion range of the forwarding peer. rate of change of signal strength is given as: Assume that a peer pi which has a set N of neighboring Sij (current) − Sij (prev) ∆(Sij ) = (2) peers. Now the question is ”How we determine the best ∆t k neighbors?”, k is a user defined threshold and k ≤ N . The above quantity is then averaged over the last few sam- In the following, we present the different context features ples to obtain ∆(Sij (ave)). Hence, based on this metric we considered to select the best k neighbors for a given query define a link lifetime measure Lif etime(i − j), which com- q. Thereafter, we present our neighbors selection algorithm. putes the time taken by peer nj to move out of the range of 3.1 Context features peer pi , as follows:   ∆(Sij (ave)) if ∆(Sij (ave)) ≥ 0 3.1.1 User’s profile and query content Lif etime(i − j) = We consider the query content to help the querying peer  Sthresh −Sij (current) ∆(Sij (ave)) otherwise to find the most relevant answers to its query quickly and (3) efficiency. To achieve this, a peer estimates, for each query, which of its neighbors are more likely to reply to this query, Battery energy and propagates the query message to those peers. To de- termine the pertinent neighbors, we compute the similarity The calculation of energy level is important to determine the between the query and each neighbors. Hence, each peer battery level of every peer during active data transmission. maintains a profile for each of its peers. The profile contains We assume that the battery level of a wireless peer decreased the list of the most recent past queries, that the specific peer when the peer initiated data transmission or when the peer that provided the answer for. Although logically we consider forwards packets. A peer gets killed (disconnected) if the each profile to be a distinct list of queries, we use a single battery power finishes. To predict the remaining battery Queries table with (Query-peer) entries that keeps the most power we assume that the transmit power is fixed. As in [6], recent queries the peer has recorded. energy required for each operation like receive, transmit, broadcast, discard on a packet is given by: For each query it receives, the receiver peer uses the pro- E(packet) = b × (packet size) + c (4) files of its peers to find which ones are more likely to have documents that are relevant to the query. To compute the Coefficient b denotes the packet size dependent energy con- similarity, the receiver peer compares the query to previ- sumption whereas c is a fixed cost that accounts for ac- ously seen queries and finds the most similar ones in the quiring the channel and for MAC layer control negotiation. repository. To find the similarity between the queries, it Each peer has to maintain a table to record the remaining uses the cosine similarity [10]. Thereafter, we compute an energy of its neighboring peer. This data is used by the peer aggregate similarity of a peer to a given query. The aggre- to predict the remaining energy of the neighboring peer nj . gate similarity of peer nj to query q that peer pi computes Assume the remaining energy, of a neighbor peer at time t1 is: and t2 are rengy1(nj ) and rengy2(nj ). The prediction of remaining energy of this peer at time t is given by X P simpi (nj , q) = Cosine(qk , q) rengy(nj ) = rengy2(nj ) qk was answered by nj +[(rengy2(nj ) − rengy1(nj ))/(t2 − t1)] × (t − t2) (1) (5) Every peer has to calculate the rengy by itself and sends 3.1.2 Link stability it to its neighbors. We defined a Link stablity function that combines the peer mobility and battery energy factors to compute the We combine the lifetime and the remaining energy metrics stability of link between two peers. Before describing our to define our function Link stability. This metric calculates 23 the time taken by peer nj to move out of the range of peer pi proposed method and evaluate its retrieval effectiveness and or the battery power of nj finishes. The Link stability(i−j) routing efficiency. of a link i − j between the peer pi and its neighbor nj is computed as follows: 5. REFERENCES Link stability(i − j) = M in(rengy(nj ), Lif etime(i − j)) [1] Bluetooth. (6) http://simple.wikipedia.org/wiki/Bluetooth, March, Where, rengy(nj ) is the remaining energy of the neighbor 2012. nj . [2] Wifi. http://simple.wikipedia.org/wiki/Wifi, March, 2012. 3.1.3 Peer load [3] S. Agarwal, A. Ahuja, J. P. Singh, and R. Shorey. A vital part of the optimal network is the load balancing. Route-lifetime assessment based routing (rabr) For instance, job completion becomes complex, if huge load protocol for mobile ad-hoc networks. In ICC (3), is given to the peers with less processing capabilities. There pages 1697–1701, 2000. is a possibility of load imbalance due to that the comput- [4] D. N. da Hora, D. F. Macedo, L. B. Oliveira, I. G. ing/processing power of the systems are non-uniform few Siqueira, A. A. F. Loureiro, J. M. Nogueira, and peers may be idle and few will be overloaded. A peer which G. Pujolle. Enhancing peer-to-peer content discovery has high processing power finishes its own work quickly and techniques over mobile ad hoc networks. Comput. is estimated to have less or no load at all most of the time. Commun., 32(13-14):1445–1459, Aug. 2009. However, if we send queries only to peers that have hight [5] M. Dietzfelbinger. Gossiping and broadcasting versus processing capabilities data packets will take routes that computing functions in networks. In STACS 97, could introduce more delay hence increasing latency. With volume 1200, pages 189–200. Springer Berlin / proper ways to transferring traffic load onto routes that are Heidelberg, 1997. relatively less congested can result in overall better through- [6] N. Gupta, K. Bafna, and N. Gupta. 2011 international put and reduced latency. An important parameter indicates conference on information and network technology. In the line congestion is the queue utilization of the neighbor 2011 Seventh International Conference on Mobile (i.e. Number of packets waiting in queue), a high count Ad-hoc and Sensor Networks (MSN), volume 4. indicates line congestion. We define a Peer Load function IACSIT Press, 2011. based on the CP U capabilities and the queue utilization of [7] H. Jin, X. Ning, H. Chen, and Z. Yin. Efficient query the neighbor. The Peer Load of a neighbor nj is calculated routing for information retrieval in semantic overlays. as follows: In Proceedings of the 21st Annual ACM Symposium on Applied Computing, pages 23–27, Dijon, France, April 23–27 2006. ACM Press. P eer Load(nj ) = cpu × (1 − u) (7) [8] D. B. Johnson, D. A. Maltz, and J. Broch. Dsr: The where cpu is the processing power and 0 ≤ u ≤ 1 is the dynamic source routing protocol for multi-hop wireless queue utilization of the neighbor ni . This function allows to ad hoc networks. In In Ad Hoc Networking, edited by send more messages to neighbors with lower load, while less Charles E. Perkins, Chapter 5, pages 139–172. messages are sent to saturated peers. Addison-Wesley, 2001. [9] A.-H. Leung and Y.-K. Kwok. On topology control of 3.2 Neighbors selection algorithm wireless peer-to-peer file sharing networks: energy To select its K best neighbors, the forwarding peer pi efficiency, fairness and incentive. In World of Wireless ranks its neighbors according to a Preference function that Mobile and Multimedia Networks, 2005. WoWMoM we define. Thereafter, it selects the first k neighbors, which 2005. Sixth IEEE International Symposium on a, have the greatest score. Our Preference function computes pages 318 – 323, june 2005. the score of each neighbor nj for a given query q, as a [10] J. Makhoul, F. Kubala, R. Schwartz, and weighted arithmetic sum of Link stability, Peer Load and R. Weischedel. Performance measures for information Psim metrics: extraction. In Proceedings of DARPA Broadcast News Workshop, pages 249–252, Herndon, VA, February P ref (nj ) = α1 × Link stability(i − j) + α2 × P eer Load(nj ) 1999. +α3 × P simPi (nj , q) (8) [11] C. Perkins, E. Belding-Royer, and S. Das. Ad hoc where α1, α2 and α3 represent the relative importance of on-demand distance vector (aodv) routing, 2003. these three metrics. [12] C. E. Perkins and P. Bhagwat. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. In Proceedings of the conference 4. CONCLUSION AND FUTURE WORKS on Communications architectures, protocols and We have presented a novel context-aware integrated rout- applications, SIGCOMM ’94, pages 234–244, New ing method for P2P file sharing systems over MANET. Our York, NY, USA, 1994. ACM. method selects the best peers based on the query content [13] T. Repantis and V. Kalogeraki. Data dissemination in and the user’s profile. Furthermore, it considers the energy mobile peer-to-peer networks. In Proceedings of the efficiency, peer mobility and peer load factor into the query 6th international conference on Mobile data forwarding process to guarantee that the pertinent peers can management, MDM ’05, pages 211–219, New York, be reached. As the future work, we plan to implement the NY, USA, 2005. ACM. 24 [14] N. Shah and D. Qian. An efficient unstructured p2p overlay over manet using underlying proactive routing. In 2011 Seventh International Conference on Mobile Ad-hoc and Sensor Networks (MSN), pages 248 –255, dec 2011. [15] B. Tang, Z. Zhou, A. Kashyap, and T. cker Chiueh. An integrated approach for p2p file sharing on multi-hop wireless networks. In WiMob (3), pages 268–274, 2005. [16] T. Yeferny and K. Arour. Learningpeerselection: A query routing approach for information retrieval in p2p systems. In International Conference on Internet and Web Applications and Services, pages 235–241, Barcelona, Spain, May 09-15 2010. IEEE Computer Society. 25