HYMAD: Hybrid DTN-MANET Routing for Dense and Highly Dynamic Wireless Networks John Whitbeck Thal`es Communications and UMPC Paris Universitas - LIP6 Vania Conan Thal`es Communications In this paper we propose HYMAD, a Hybrid DTN- MANET routing protocol which uses DTN between disjoint groups of nodes while using MANET routing within these groups. HYMAD is fully decentralized and only makes use of topological information exchanges be- tween the nodes. We evaluate the scheme in simulation by replaying real life traces which exhibit this highly dynamic connectivity. The results show that HYMAD outperforms the multi-copy Spray-and-Wait DTN rout- ing protocol it extends, both in terms of delivery ratio and delay, for any number of message copies. Our con- clusion is that such a Hybrid DTN-MANET approach offers a promising venue for the delivery of elastic data in mobile ad-hoc networks as it retains the resilience of a pure DTN protocol while significantly improving per- formance. When transporting data through a wireless mobile ad-hoc network, the Delay/Disruption-Tolerant Net- work (DTN) [7] paradigm uses node mobility as an advantage while compromising on message delivery de- lays [8]. Message forwarding decisions are made on a per-encounter basis, for example by using utility func- tions based on aggregating statistics on node meeting probabilities [10, 4, 9]. At any given time, a node’s vision of the network topology is limited to its cur- rent neighbor. It does not have complete or even lo- cal knowledge of the actual network topology as in the conventional Mobile Ad-hoc Network (MANET) routing schemes. While this makes perfect sense in extremely sparse networks [3, 1], there are situations where a highly mobile network is dense and sufficiently well connected to provide end-to-end connectivity be- tween a significant subset of its nodes. In the next section, we further describe how our We implemented the HYMAD hybrid approach with a self-stabilizing group service [5, 6] and the multi- copy Spray-and-Wait protocol as the DTN routing scheme [13]. We evaluated the scheme by performing simulation runs on the Rollernet data set [14], an ex- ample of a highly dynamic ad-hoc network, and show that it brings substantial performance improvements over pure Spray-and-Wait. HYMAD constantly adapts to the dynamics of the wireless ad-hoc network using only topological infor- mation. As in traditional ad-hoc routing, no extra in- formation on geographical location or social commu- nity membership is required. It does not rely on a pri- ori knowledge of connectivity patterns or inter-meeting times. This makes HYMAD amenable to implementa- tion in a DTN stack or ad-hoc routing protocol [11]. In a dense network, HYMAD can function similarly to a traditional MANET protocol. In the other extreme case of very sparse connectivity, each node is a group on its own and HYMAD behaves like a classical DTN routing protocol. In any other intermediate case its hybrid nature takes over. In this paper we propose HYMAD, a Hybrid DTN- MANET routing protocol. HYMAD combines tech- niques from both traditional ad-hoc routing and DTN approaches. HYMAD periodically scans for network topology changes and builds temporary disjoint groups of connected nodes. Intra-group delivery is performed by a conventional ad-hoc routing protocol and inter- group delivery by a DTN protocol. These nodes may even form small islands of stability. Using MANET principles within such islands can bring great improvements. Indeed, it considerably increases each node’s information of its local topology, thus lead- ing to better forwarding decisions. When high mobility rates and more generally high link instabilities reduce route life-times and threaten network-wide end-to-end connectivity, a MANET routing protocol can still suc- ceed locally even if it fails globally. Abstract 1 Introduction arXiv:1001.3405v1 [cs.NI] 19 Jan 2010 978-1-4244-4439-7/09/$25.00 c ○ 2009 IEEE