Abstract
Most of the existing research work in mobile ad hocnetworking is based on the assumption that a path exists betweenthe sender and the receiver. On the other hand, applications ofdecentralised mobile systems are often characterised by networkpartitions. As a consequence delay tolerant networking researchhas received considerable attention in the recent years as a meansto obviate to the gap between ad hoc network research and realapplications.In this paper we present the design, implementation andevaluation of the Context-aware Adaptive Routing (CAR) protocolfor delay tolerant unicast communication in intermittentlyconnected mobile ad hoc networks. The protocol is based on theidea of exploiting nodes as carriers of messages among networkpartitions to achieve delivery. The choice of the best carrier ismade using Kalman filter based prediction techniques and utilitytheory. The large scale performance of the CAR protocol areevaluated using simulations based on a social network foundedmobility model, a purely random one and real traces fromDartmouth College
.Index Terms—Wireless communication, routing protocols
I. INTRODUCTION
Mobile ad hoc network research [1] has often assumed that aconnected path exists between a sender and a receiver node atany point in time. This assumption reveals itself unrealistic inmany decentralized mobile network applications such as vehicularnetworks, wildlife monitoring sensor networks, deep spacecommunication systems and emergency operations networks. Toanswer this dichotomy, delay tolerant networking (DTN) [2] hasreceived considerable attention from the research community inrecent years as a means of addressing exactly the issue of routingmessages in partitioned networks.DTNs span very challenging application scenarios where nodes(e.g., people, wild animals) move around in environments whereinfrastructures cannot be installed (e.g., emergency operations,military grounds, protected environments). Some solutions torouting have been presented also for these cases, starting fromthe basic epidemic routing [3], where messages are blindly storedand forwarded to all neighbouring nodes generating a floodof messages. The drawback of epidemic dissemination lies inthe very high number of messages which are needed to obtainsuccessful delivery to the right recipient. Other solutions havebeen proposed to tackle the problem of routing in (possiblymobile) delay tolerant networks, based on the previous knowledgeof the routes of the potential carriers [4]–[6] or on probabilisticapproaches [7], [8]..In this paper we present the Context-aware Adaptive Routing(CAR) protocol, an approach to delay tolerant mobile ad hocnetwork routing which uses prediction to allow the efficientrouting of messages to the recipient. A host willing to send amessage to a recipient, or any host in the multi hop path to it, usesa Kalman Filter prediction and multi-criteria decision theory [9]to choose the best next hop (or carrier) for the message. Thedecision is based on the mobility of the host (a highly mobile hostis a good carrier as it meets many hosts) and its past colocationwith the recipient (we implicitly assume that past colocationindicates that the host will meet the recipient again in the future).CAR does not assume any previous knowledge of the routes ofthe hosts like other approaches, such as the Message Ferryingproject [5], that rely on the a priori knowledge of the routes ofthe special hosts carrying the information. Moreover, our protocolis based on a single copy of the message in the system, instead ofhaving multiple replicas. Other solutions are predicated on semiepidemicalgorithms like PRoPHET [7], where the probabilityof replication is proportional to the time of the last encountersand their frequency. Finally, we do not exploit any geographicalinformation such as GPS coordinates.An earlier version of the protocol with a limited evaluationhas been presented previously in a symposium paper [10]: wehave extended that paper with additional protocol details, animplementation and a thorough performance evaluation with anew mobility model validated using real traces provided byIntel [11]. Our approach can be considered the first one exploitingforecasting techniques for carrier selection founded on analyticalprediction models.This paper is organised as follows. Section II presents thedesign of the CAR protocol. The performance evaluation of theprotocol is discussed in Section III. A comparison with the stateof the art is presented in Section IV. Section V summarises thecontribution of this work.
II. DESIGN OF THE CAR PROTOCOL
A. OverviewIn this section we give an overview of the Context-awareAdaptive Routing (CAR) protocol, presenting the key designchoices and the novel mechanisms that are at the basis of itsimplementation. Firstly, we describe the general steps of theprotocol. Secondly, we analyse the prediction theory and itsfoundation algorithms. Thirdly, we discuss the protocol implementation,focussing on the management of routing informationfor synchronous and asynchronous delivery.
Download full report
http://cl.cam.ac.uk/~cm542/papers/tmc08.pdf
