Overview of Hybrid MANET-DTN Networking and its Potential for Emergency Response Operations Electronic Communications of the EASST Volume 56 (2013) Proceedings of the Combined workshop on Self-organizing, Adaptive, and Context-Sensitive Distributed Systems and Self-organized Communication in Disaster Scenarios (SACS/SoCoDiS 2013) Overview of Hybrid MANET-DTN Networking and its Potential for Emergency Response Operations Christian Raffelsberger, Hermann Hellwagner 12 pages Guest Editors: Michael Zapf, Florian Evers Managing Editors: Tiziana Margaria, Julia Padberg, Gabriele Taentzer ECEASST Home Page: http://www.easst.org/eceasst/ ISSN 1863-2122 http://www.easst.org/eceasst/ ECEASST Overview of Hybrid MANET-DTN Networking and its Potential for Emergency Response Operations Christian Raffelsberger1, Hermann Hellwagner2 1 christian.raffelsberger@aau.at 2 hermann.hellwagner@aau.at Institute of Information Technology Alpen-Adria-Universität Klagenfurt, Austria Abstract: Communication networks for emergency response operations have to op- erate in harsh environments. As fixed infrastructures may be unavailable (e.g., they are destroyed or overloaded), mobile ad-hoc networks (MANETs) are a promising solution to establish communication for emergency response operations. However, networks for emergency responses may provide diverse connectivity characteristics which imposes some challenges, especially on routing. Routing protocols need to take transmission errors, node failures and even the partitioning of the network into account. Thus, there is a need for routing algorithms that provide mechanisms from Delay or Disruption Tolerant Networking (DTN) in order to cope with network dis- ruptions but at the same time are as efficient as MANET routing schemes in order to preserve network resources. This paper reviews several hybrid MANET-DTN routing schemes that can be found in the literature. Additionally, the paper evalu- ates a realistic emergency response scenario and shows that MANET-DTN routing schemes have the potential to improve network performance as the resulting net- work is diverse in terms of connectivity. In particular, the network provides well- connected regions whereas other parts are only intermittently connected. Keywords: wireless networks, mobile ad-hoc networks, routing protocols, delay tolerant networking, simulation 1 Introduction Emergency response and recovery operations are highly collaborative efforts which involve dif- ferent first responder organizations. Establishing and maintaining communication as well as disseminating information between first responders are critical tasks in order to create situational awareness and establish a common operational picture. However, networks in an emergency re- sponse operation have to be established in an ad-hoc manner if fixed infrastructures are not avail- able (e.g., because they have been destroyed or are overloaded in the aftermath of the disaster). Such hastily formed networks are often diverse in terms of connectivity and network equipment. Connectivity settings may range from almost fully connected networks to very sparse networks. Apart from these two extremes, the network may be intermittently connected, providing sepa- rated “islands” of well-connected nodes. For instance, different search and rescue teams may be separated from each other as they are out of communication range but members of the same 1 / 12 Volume 56 (2013) mailto:christian.raffelsberger@aau.at mailto:hermann.hellwagner@aau.at Overview of Hybrid MANET-DTN Networking team are well-connected. Due to the mobility of the rescue workers as well as link and device failures, the network topology and connectivity characteristics of the network will constantly change. This imposes some challenges on the network routing protocols. The majority of state-of-the-art routing protocols for Mobile Ad-hoc Networks (MANETs) [AM12] assume that an end-to-end path between source and destination is available (we will refer to this approach as MANET routing). Even though these protocols were designed for MANETs that are prone to link failures, they fail to route packets if such an end-to-end path does not exist. Hence, these protocols are not suited for intermittently connected networks. On the other hand, Delay or Disruption Tolerant Networking (DTN) protocols [SRT+10] do not presume the existence of an end-to-end path between source and destination (we will refer to this approach as DTN routing). Instead, messages are stored at the sender or at intermediate nodes until there is an opportunity to deliver the message towards the destination. This mechanism is called store-and- forward (or store-carry-forward). Store-and-forward routing allows nodes in different network partitions to exchange data, even if there is no end-to-end path available. Many DTN routing protocols use replication (i.e., store multiple copies of a message in the network) to increase the chance of delivery as well as to reduce the delivery delay. However, in dense networks this approach is not very efficient as it increases the communication and storage overhead. We argue that neither MANET nor DTN routing schemes alone can work satisfactorily in the majority of emergency response scenarios. Rather, hybrid MANET-DTN routing protocols, that use the store-and-forward principle to work in intermittently connected networks but also work efficiently in the well-connected regions, are needed. However, compared to MANET and DTN routing, such hybrid approaches did not get much research attention. The contributions of this paper are twofold. First, this paper gives an overview and comparison of existing hybrid MANET-DTN routing approaches. Second, this paper evaluates the connec- tivity settings of a realistic emergency response communication network to show that emergency responses are a promising application area for hybrid MANET-DTN approaches. The rest of this paper is structured as follows: Section 2 introduces hybrid MANET-DTN routing schemes that combine both routing approaches. Section 3 evaluates a realistic emer- gency response scenario and shows that the connectivity characteristics of the ad-hoc network are appropriate to use hybrid MANET-DTN routing. Section 4 concludes the paper and points out possible future work. 2 Hybrid MANET-DTN routing schemes Intuitively, neither MANET nor DTN routing protocols are suited for networks that are parti- tioned but at the same time provide well-connected regions. MANET routing is unable to provide an inter-partition communication, whereas DTN routing is not efficient in the well-connected regions. A formal framework by Manfredi et al. [MCK11] confirms this assumption. The framework uses the connectivity of the network, the uncertainty of links and network contention to organize the decision space into regions where path-oriented routing (i.e., MANET routing), DTN routing or flooding1 is most appropriate. MANET routing is best suited when there is a high 1 Flooding is a special case of DTN routing where stored packets are always replicated and forwarded to all available neighbors. Proc. SACS/SoCoDiS 2013 2 / 12 ECEASST probability that a route exists and the route is stable (i.e., the link uncertainty is low). DTN is best suited when paths are not available or are likely to fail. Flooding can only be used in unreliable networks with low network load since flooding introduces a lot of communication overhead. The authors of [MCK11] used simulations and network traces to confirm this model. Interestingly, most of the networks that were analyzed spent most of their time in the low connectivity and low uncertainty region (i.e., only a few but relatively stable paths exist). As path-based routing is best suited for stable networks and DTN routing (or flooding) is best suited for networks with low connectivity, this hybrid region is a field of application for protocols that combine both routing paradigms. Section 3 shows that networks for emergency response operations may also fall into this hybrid region. 2.1 State-of-the-art hybrid MANET-DTN routing schemes Hybrid MANET-DTN routing schemes are not as well researched as MANET or DTN routing where many protocols have been proposed. However, such approaches gained more interest recently. The Context-aware Adaptive Routing (CAR) protocol [MHM05] is one of the first approaches that combines MANET with DTN routing. In particular, CAR integrates custodian selection and message buffering, two well-known mechanisms from DTN, into a proactive distance vector MANET routing protocol. The proactive routing protocol is utilized to exchange network-related context information such as the change rate of connectivity or the probability that two nodes are connected. Based on this information, CAR uses a context framework to calculate and predict the delivery probability between nodes. The information about the best candidate node to deliver a message is added to the routing table. In connected parts of the network, CAR uses a proactive MANET routing protocol to exchange data. In partitioned networks, CAR uses the delivery probability to determine the best custodian for the message. As messages are not replicated, CAR introduces only little overhead for the exchange of context information, piggybacked on routing control messages. Lakkakorpi et al. [LPO10] introduced an adaptive routing scheme that allows a message source to choose between a reactive MANET (e.g., AODV) and a DTN (e.g., spray-and-wait, epidemic routing) routing protocol. The decision between MANET and DTN routing is based on information that is locally available or can be gathered by means of probing packets (e.g., node density, available bandwidth). Based on this context information, a decision framework selects between a MANET and a DTN routing scheme. The decision is only made at the message source and intermediate nodes do not change the routing paradigm. It is important to note that the decision framework could also select DTN routing in the presence of an end-to-end path (e.g., if the estimated message transfer time is larger than the estimated path lifetime). The basic operation of the utilized MANET routing protocol is not changed (e.g., AODV control messages and the route finding process are not modified). The Delay-tolerant DYMO (DT-DYMO) protocol [KRS09] integrates a probability model into the reactive DYMO routing protocol. The probability model is based on the history of encounters between nodes. DYMO’s routing control messages and the route request process are modified in order to find potential custodian nodes, that can deliver data messages in the presence of network disruptions. All DT-DYMO route requests contain a delivery probability threshold and nodes 3 / 12 Volume 56 (2013) Overview of Hybrid MANET-DTN Networking reply if their delivery probability is greater than this threshold. If an end-to-end path is available, DT-DYMO works similar to the unmodified DYMO protocol. In the presence of disruptions, a DT-DYMO source node forwards messages to the node with the highest probability of meeting the destination. This node stores the message until it can be delivered to the destination. In order to perform an accurate delivery likelihood estimation, nodes have to periodically exchange their delivery probabilities. However, as reactive routing protocols like DYMO do not periodically exchange control messages, DT-DYMO requires an additional beaconing mechanism. The Hybrid MANET DTN (HYMAD) protocol [WC10] combines techniques from traditional MANET routing protocols and DTN routing. HYMAD partitions the network into several dis- joint groups of nodes. All nodes within a group are connected by an end-to-end path and a conventional MANET routing protocol can be used for intra-group communication. For inter- group communication a DTN routing protocol (e.g., spray-and-wait, epidemic routing) is used. Hence, a HYMAD group can be seen as one node in a DTN network. The maximum size of a group is a means to control the communication paradigm. For instance, if small groups are used (e.g., all members must be within two hops), more DTN-style inter-group communication is needed because the network is partitioned into many groups. If the groups are very large (e.g., the entire connected portion of the network), HYMAD acts like a MANET protocol with a store-and-forward capability. BATMAN Store-and-Forward (SF-BATMAN) [DN12] adds a store-and-forward capability to the proactive MANET routing protocol BATMAN. It is designed to be compatible with the standard BATMAN routing protocol. Hence, it does not change routing control messages nor forward multiple copies of a message. A SF-BATMAN node stores a message if currently no path to the destination can be found. Similarly, packets are buffered if the designated next hop was not recently active (i.e., a control packet was received recently via this node). This reduces packet loss due to stale links. Apart from these modifications, SF-BATMAN acts like the basic BATMAN protocol. Whenever a node receives a routing control packet which may update or validate a routing table entry, the node tries to send all buffered packets. The Storage Aware Routing (STAR) protocol [JGR11] uses a two-dimensional routing metric to decide between storing and forwarding packets. STAR uses OLSR to discover paths in the network and modified routing control messages in order to monitor short term and long term link costs (e.g., the link delay) and the available storage of nodes. Similarly to traditional MANET routing protocols, STAR utilizes the path with minimum costs to deliver packets. If the short term costs of a link are higher than its long term costs, this is an indication that the link is saturated. In such a case packets are stored instead of being sent instantly. Packets are also stored if there is no path available or if the nodes on the end-to-end path do not provide enough storage space to buffer the packet. Compared to the basic OLSR protocol, STAR increases the delivery delay of certain packets to increase the overall delivery ratio (e.g., by avoiding network congestion). AODV-DTN [OKD06] combines AODV with the DTN bundle protocol [SB07]2. To be more precise, AODV messages are extended and the route request/reply process is modified to ex- change information about which nodes in the network support the bundle protocol (such nodes are also called DTN routers). After the route finding process has finished, the source is aware 2 The bundle protocol is an application layer protocol that supports store-and-forward communication. Application data is encapsulated in so called bundles. Proc. SACS/SoCoDiS 2013 4 / 12 ECEASST of the shortest end-to-end path and also all available DTN routers. If the source node supports the bundle protocol, applications can dynamically switch to bundle transport when no end-to- end path is available. As nodes must also support the bundle protocol to use DTN routing, this approach basically enhances the DTN bundle routing by an AODV-based discovery process for bundle routers. Hence, this approach is better suited for networks where most of the nodes already use the bundle protocol. Delay Tolerant Structured Overlay Link State Routing (DTS-OLSR) [PTM+10] builds a DTN- based overlay network on top of the OLSR routing protocol. The periodic link state updates of OLSR are used to form and maintain an overlay network. This overlay network provides methods to register and find overlay nodes that support the DTN bundle protocol (these nodes are called DTS-OLSR nodes). If a node does not support the bundle protocol, it may use the nearest DTS- OLSR node to send and receive bundles. All communication between the DTS-OLSR and the non DTS-OLSR node is performed via so called lite bundles. Hence, all messages have to be encapsulated into bundles or lite bundles before they can be sent, even if an end-to-end path exists. As a result, DTS-OLSR introduces some communication overhead which decreases its performance compared to standard OLSR, especially when the network is well-connected. The Robust Replication Routing (R3) protocol [TVB11] is another hybrid approach. However, it does not extend or switch between existing routing protocols but is designed in a way that it performs well under different connectivity characteristics. R3 achieves this by adapting the number of message replications based on the distribution of path delays. In order to monitor path delays, all nodes periodically exchange probing packets. The distribution of path delays has a direct effect on the replication gain (i.e., the benefit of replicating a packet and sending it via multiple paths). The replication gain is higher if the predictability of the delay is low (i.e., the path delays are highly variable). If the expected delay is well predictable, R3 uses the path with the minimum expected delay (MANET-style routing). If the expected delay is unpredictable, R3 uses multiple paths to convey the message via those paths that minimize the expected delay (DTN-style routing). Hence, R3 requires source routing (i.e., the addresses of all nodes along the path are stored in the packet header) in order to control which paths are used. 2.2 Comparison of hybrid MANET-DTN approaches The hybrid MANET-DTN approaches that have been introduced can be divided into three ba- sic classes. The first class of approaches includes DTN mechanisms (e.g., store-and-forward routing, probabilistic custodian selection, message replication) into a MANET routing protocol. Another possibility to design hybrid MANET-DTN routing schemes is to combine the DTN bun- dle protocol with a MANET routing protocol. Finally, there are approaches that do not rely on existing protocols but are designed in a way that they can work in a broad range of networks, for instance, by using routing metrics that perform well under diverse connectivity characteristics. Integration of DTN mechanisms into MANET protocols: This type of hybrid approaches in- tegrates DTN mechanisms into a traditional MANET protocol. Particularly, these approaches change an existing end-to-end MANET protocol in order to provide communication between network partitions. To achieve inter-partition communication, at least a store-and-forward mech- anism needs to be integrated. Optionally, routing performance may be improved by selecting message custodians based on predicted future communication opportunities and replicating mes- 5 / 12 Volume 56 (2013) Overview of Hybrid MANET-DTN Networking sages in the network. SF-BATMAN and STAR only include packet buffering. DT-DYMO and CAR additionally use modified routing control messages to probabilistically select message cus- todians. To save network resources, none of these protocols replicates packets. Message repli- cation is only used by HYMAD. The advantage of this kind of approaches is that they can be implemented at the network layer without adapting the upper layers. However, these approaches are application agnostic but certain types of applications such as real-time multimedia commu- nication will not work well as stored packets introduce higher packet delay and jitter. Support for the DTN bundle protocol: This kind of approaches combines the DTN bundle protocol with a traditional MANET routing scheme. The bundle protocol is an application layer protocol that forms a store-and-forward overlay network. The basic protocol units are called bun- dles and are typically larger than data units of the underlying transport and network protocols. The bundle protocol does not define how bundles are routed. Hence, a DTN routing algorithm is needed to route bundles in the network. The DTN routing protocol determines if packets are replicated and how custodians are selected (e.g., if they are selected probabilistically). Hence, the performance of this kind of hybrid approaches is mainly influenced by the DTN routing pro- tocol that is used. As the bundle protocol is an application layer protocol, the decision between MANET and DTN routing has to be made at the application layer. For instance, AODV-DTN uses the bundle protocol if no end-to-end routes are available. Lakkakorpi et al. use a more advanced decision framework that includes locally available context information (e.g., message size). Additionally, approaches such as AODV-DTN and DTS-OLSR utilize the MANET rout- ing protocol to discover DTN routers (i.e., nodes that can forward DTN bundles) in the network. This is performed by including information about DTN routers into the MANET routing control messages. Since the decision between MANET and DTN routing is performed at the application layer, it is possible to consider application-specific context. For instance, a voice communica- tion application could either refrain to use DTN routing or switch from streaming to a “walkie- talkie”-like communication, which is more appropriate in the presence of network partitions. On the other hand, this kind of hybrid approaches requires the modification of existing applications. Another disadvantage is that the bundle protocol introduces some additional overhead. Espe- cially when only bundles are used for delivering data (e.g., as performed by DTS-OLSR), this may decrease the performance of the network. Design of new routing protocols for diverse networks: There are also approaches that do not combine or integrate existing MANET or DTN protocols but are especially developed to support a broad range of networks with diverse connectivity characteristics. One key to successfully developing such hybrid protocols is to find routing metrics that perform well under diverse con- nectivity settings. The main advantage is that these protocols have been designed particularly for hybrid networks and use mechanisms and metrics that are suited for well-connected and sparse networks. On the other hand, deployment of such clean-slate approaches may be difficult since no existing MANET protocols nor the DTN bundle protocol can be re-used. R3 is an example for such an approach. A summary of the hybrid MANET-DTN approaches can be found in Table 1. The approaches are compared based on these aspects: the underlying MANET routing protocol or metric, support for the DTN bundle protocol and if message replication or custodian selection are supported. Proc. SACS/SoCoDiS 2013 6 / 12 ECEASST Table 1: Comparison of hybrid MANET-DTN routing approaches Protocol MANET prot. Bundle prot. Message Custodian (metric) replication selection AODV-DTN [OKD06] AODV optional1 optional2 optional2 BATMAN-SF [DN12] BATMAN no no no CAR [MHM05] DSDV no no yes DT-DYMO [KRS09] DYMO no no yes DTS-OLSR [PTM+10] OLSR yes optional2 optional2 HYMAD [WC10] distance vector no yes yes Lakkakorpi et al. [LPO10] AODV optional3 optional2 optional2 R3 [TVB11] expected delay no yes no STAR [JGR11] OLSR no no no 1 The bundle protocol is used if AODV does not report a route to the destination. 2 Determined by the DTN routing protocol that is used to route bundles. 3 Decision framework at sender decides about the usage of bundles. Chemical Facilities Chemical Facilities Ch em ic al F ac ili ti es Explosion Area PWFTA CCS2CCS1 APP TOC IL 1 (Administrative Building) IL 2 R iv er R iv er Disaster Model Area Obstacle (Disaster Model) First responder path Nodes 1 4 Obstacle (Shadowing Model) APP: Ambulance Parking Point CCS (n): Casulties Clearing Station IL (n): Incident Location PWFTA: Patients Waiting For Treatment Area TOC: Technical Operational Command 400m 30 0m 4 4 2 2 4 4 en tr y/ ex it p oi nt Figure 1: Map of the disaster area for the chemical disaster scenario. 3 Evaluation of a realistic emergency response network Intuitively, emergency response operations are a promising application area for hybrid MANET- DTN routing schemes. For instance, different first responder teams may be separated from each other, although the network density is high in certain parts of the network. To confirm this assumption, this section uses an emergency response scenario, similar to the one introduced in [RH12], to evaluate the connectivity settings of an ad-hoc network of first responders. The scenario uses a specific mobility model that mimics the movements of first responders on the disaster site. Additionally, a wireless obstacle model is used to show the effects of first responders working indoors. The scenario models an emergency response effort after an explosion in a chemical facility. The facility contains two administrative buildings that haven been damaged by the explosion and may contain people that are trapped inside the buildings and need to be rescued by first responders. Figure 1 depicts the disaster area. The performance of a MANET is influenced by the mobility pattern of the nodes. As first responders do not move randomly in the disaster area, we use a mobility model by Aschenbruck 7 / 12 Volume 56 (2013) Overview of Hybrid MANET-DTN Networking Table 2: Simulation parameters Wireless model MAC protocol 802.11 (g) Propagation model Free-space path loss (α = 2) Transmission range 25 m, 50 m, 100 m, 150 m, 200 m Wireless obstacle model [SEGD11] Per-wall attenuation 18 dB Indoor attenuation 0.5 dB/m Mobility model [AGG+07] Node speed 1 to 2 m/s Speed (vehicles) 5 to 12 m/s Traffic model Type IP broadcast Packet size 100 bytes Send rate 4 packets/s Jitter 5 ms et al. [AGG+07] to mimic the movements of first responders more realistically. The mobility model defines several types of tactical areas and two types of first responders (i.e., people and vehicles). Every first responder is assigned to one tactical area that defines his or her tasks. Apart from special transport units, first responders do not leave their assigned area. The transport units are responsible for transporting victims between areas. To be more precise, transport units carry victims from the Incident Locations (IL) to the Patients Waiting For Treatment Areas (PWFTA) and finally to the Casualty Clearing Stations (CCS). Vehicles that wait in the Ambulance Parking Points (APP) pick up the victims in the CCS and bring them to a hospital (i.e., leave the dis- aster area). The Technical Operational Command (TOC) contains the incident command staff. Obstacle areas that restrict the available paths can be defined as well. Wireless signals may get attenuated or blocked by obstacles. To capture these effects, we use a wireless obstacle model [SEGD11]. The model attenuates the wireless signal if there is an obstacle in the line of sight between sender and receiver. The disaster scenario contains two obstacles that represent the damaged buildings. First responders enter these buildings in order to search and rescue victims. Hence, these first responders may get isolated from the rest of the network or form smaller network partitions. 3.1 Simulation setup As described in Section 2, the connectivity of the network is an important decision criterion for deciding which communication strategy is suited. Thus, we used the OMNet++ network simulator to model a realistic emergency response and evaluate the connectivity characteristics of the resulting first responder communication network. The experiment consists of 25 nodes that are placed in the simulation area. These nodes represent first responders that are equipped with a wireless device and move according to the disaster area mobility model. Simulation parameters are listed in Table 2. Proc. SACS/SoCoDiS 2013 8 / 12 ECEASST To gather data about which nodes are connected at a certain point in time, all nodes regularly broadcast IP packets and log from which nodes they received packets within the last second. To reduce collisions due to the synchronization of broadcasts from different nodes, a jitter of 5 ms is applied to the broadcast interval. In contrast to a graph-based analysis that presumes homogeneous transmission ranges, this approach also captures effects of the wireless obstacle model as well as transmission errors. The broadcasts reveal all 1-hop neighbors of a node. Two nodes are connected if they received at least one broadcast packet from each other within the last second. Similarly, if a node does not receive at least one packet from another node, the two nodes are not connected. Based on the information about direct neighbors, all n-hop paths in the network can be calculated by exploiting transitive relations (e.g., if A is a neighbor of B and B is a neighbor of C, A and C are 2-hop neighbors). All nodes that are connected directly or via an n-hop path form a connected component (we use the term partition interchangeably). It is important to note that an isolated node also forms a connected component. If there is only one connected component, consisting of all nodes in the network, the whole network is connected. Otherwise the network is partitioned. As MANET routing protocols only can route data within connected components, connectivity is a good measure to evaluate how well MANET routing protocols are suited for a network. Similarly, the number of connected components determines whether DTN routing is needed. 3.2 Results In general, the connectivity in the network increases for larger transmission ranges. Figure 2 shows the number of connected components and the size of the largest connected component over the simulation time. For a transmission range of 25 m (see Figure 2a) there are at least two network partitions at any time. This means that the network is never connected. Hence, a MANET protocol fails to establish communication between all pairs of nodes in the network. Al- though the time for which the network is connected increases for larger communication ranges, the network is partitioned most of the time. Even with a transmission range of 200 m (cf. Fig- ure 2c). The partitioning of the network is a result of node movements and wireless attenuation that is experienced by nodes working inside buildings. These nodes are completely isolated or form smaller connected components with other nodes that are located in or are nearby the same building. As the network is partitioned most of the time, DTN mechanisms are needed to provide inter-partition data delivery and improve the packet delivery ratio. Although the network is partitioned most of the time, all nodes are also regularly connected with each other. Hence, simple hybrid protocols (such as SF-BATMAN) that only store messages until the destination is available may work in this scenario. However, advanced schemes that try to predict nodes that have a higher probability to meet the destination may be able to reduce the transmission delay. In scenarios where the disaster areas are further apart (i.e., sender and receiver are never in the same partition), such advanced approaches are the only way of providing inter-partition communication. On the other hand, the size of the largest connected components shows that MANET routing is suited for large parts of the network. A transmission range of 50 m (see Figure 2b) allows the nodes to form a connected component that contains the majority of nodes most of the time. For transmission ranges of 100 m and more the largest connected component contains more than 20 9 / 12 Volume 56 (2013) Overview of Hybrid MANET-DTN Networking 0 5 10 15 20 25 30 0 300 600 900 1200 1500 1800 2100 2400 2700 3000 C o u n t Time (s) no. of partitions no. of nodes in largest partition (a) 25 m 0 5 10 15 20 25 30 0 300 600 900 1200 1500 1800 2100 2400 2700 3000 C o u n t Time (s) no. of partitions no. of nodes in largest partition (b) 50 m 0 5 10 15 20 25 30 0 300 600 900 1200 1500 1800 2100 2400 2700 3000 C o u n t Time (s) no. of partitions no. of nodes in largest partition (c) 200 m Figure 2: No. of connected components and no. of nodes in largest partition for different transmission ranges. 0 3 6 9 12 15 18 25 50 100 150 200 A v e ra g e n o . o f n e ig h b o rs Transmission range (m) (a) 0 5 10 15 20 25 30 0 300 600 900 1200 1500 1800 2100 2400 2700 3000 A v e ra g e n o . o f n e ig h b o rs Time (s) 200m 150m 100m 50m 25m (b) Figure 3: Average number of neighbors for different transmission ranges. nodes (i.e., more than 80% of all nodes) most of the time (cf. Figure 2c). Increasing the transmission range has a positive effect on network connectivity. On the other hand, it also increases the probability that transmissions collide. Figure 3a and Figure 3b show the number of average neighbors for varying transmission ranges and how the number of neigh- bors varies over time. For a transmission range greater than or equal to 150 m the average number of neighbors is about 18. This means that the majority of nodes cannot transmit data concur- rently. These nodes all share the available bandwidth which limits the network capacity. Hence, although larger transmission ranges have a positive impact on the connectivity of the network, it may be necessary to adjust the transmission range to reduce collisions in the dense parts of the network. This requires the use of hybrid MANET-DTN routing schemes since transmission range adaptation may increase the number of partitions. 4 Discussion and outlook Ad-hoc networks may provide the only way of communication in emergency response opera- tions if the fixed infrastructure is damaged or overloaded. However, neither traditional MANET nor DTN routing protocols solely fulfill all requirements of such an environment. This paper provided an overview of hybrid MANET-DTN routing schemes that could be used in disaster response networks. Most of the current approaches are either based on an existing MANET pro- tocol or the DTN bundle protocol. MANET protocols can be enhanced with mechanisms such as message replication or store-and-forward in order to increase their robustness in the presence Proc. SACS/SoCoDiS 2013 10 / 12 ECEASST of network disruptions. DTN overlay networks that use the bundle protocol to deliver data can utilize MANET protocols to find DTN-capable nodes. None of these hybrid approaches has been evaluated in an emergency scenario. Thus, it is difficult to state which approach is the most promising one. Approaches that change existing MANET protocols are beneficial in terms of deployment as existing well-tested protocols can be re-used, especially if the hybrid approach is compatible with the original version of the MANET protocol and both can co-exist in the same network (e.g., this is the case for SF-BATMAN or AODV-DTN). Additionally, the evaluation showed that the network provides connected regions where MANET routing protocols can operate well. Providing inter-partition communication by applying DTN mechanisms can improve the perfor- mance. However, the concrete effects of the introduced delay and jitter have not been evaluated yet. Proactive routing protocols seem to be more appropriate than reactive protocols as basis for this kind of hybrid approaches, as they already provide periodic route updates which can be utilized to exchange data that may be required for the DTN mechanisms (e.g., information about node encounters). Similarly, link state based approaches offer the advantage that every node is aware of the whole topology (of the connected component that it is part of) and can use this information to decide whether to use MANET or DTN delivery. Information about the topology of the network may also be valuable for first responders (e.g., to locate other first responders). Approaches that support the DTN bundle protocol are beneficial if applications already sup- port bundles. As the bundle protocol operates at the application layer, these approaches can take application context into account for deciding which communication strategy is best suited in the given environment. However, as not all applications are well suited to use the bundle proto- col, its use should be optional (e.g., as provided by the solution of Lakkakorpi et al. [LPO10]). The mandatory use of the bundle protocol even for the communication in connected components introduces additional overhead and hence reduces the performance. Approaches that have been especially designed for diverse connectivity settings are another alternative. However, the deployment of completely new protocols may be more challenging than partly re-using existing protocols. This paper used a realistic emergency response scenario to show the connectivity characteris- tics of an ad-hoc first responder network. The network showed diverse connectivity characteris- tics as the network was partitioned most of the time even though it provided large well-connected components. Evaluating hybrid routing schemes under the specific settings of a disaster response scenario is an interesting topic for future research. Acknowledgements: This research was funded by the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 261817, the BRIDGE project, and was partly performed in the Lakeside Labs research cluster at Alpen-Adria-Universität Klagenfurt. Bibliography [AGG+07] N. Aschenbruck, E. Gerhards-Padilla, M. Gerharz, M. Frank, P. Martini. Modelling Mobility in Disaster Area Scenarios. In Proc. MSWiM ’07. Pp. 4–12. ACM, 2007. 11 / 12 Volume 56 (2013) Overview of Hybrid MANET-DTN Networking [AM12] E. Alotaibi, B. Mukherjee. A survey on routing algorithms for wireless ad-hoc and mesh networks. Computer Networks 56(2):940–965, Feb. 2012. [DN12] L. Delosieres, S. Nadjm-Tehrani. BATMAN store-and-forward: The best of the two worlds. In Proc. PerCom Workshops ’12. Pp. 721 –727. IEEE, 2012. [JGR11] S. Jain, S. Gopinath, D. Raychaudhuri. STAR: Storage aware routing protocol for generalized Delay Tolerant Networks. In Proc. WoWMoM ’11. Pp. 1 –4. IEEE, 2011. [KRS09] C. Kretschmer, S. Ruhrup, C. Schindelhauer. DT-DYMO: Delay-Tolerant Dynamic MANET On-demand Routing. In Proc. ICDCSW ’09. Pp. 493–498. IEEE, 2009. [LPO10] J. Lakkakorpi, M. Pitkänen, J. Ott. Adaptive routing in mobile opportunistic net- works. In Proc. MSWIM ’10. Pp. 101–109. ACM, 2010. [MCK11] V. Manfredi, M. Crovella, J. Kurose. Understanding stateful vs stateless communi- cation strategies for ad hoc networks. In Proc. MobiCom ’11. Pp. 313–324. ACM, 2011. [MHM05] M. Musolesi, S. Hailes, C. Mascolo. Adaptive routing for intermittently connected mobile ad hoc networks. In Proc. WoWMoM ’05. Pp. 183–189. IEEE, 2005. [OKD06] J. Ott, D. Kutscher, C. Dwertmann. Integrating DTN and MANET routing. In Proc. CHANTS ’06. Pp. 221–228. ACM, 2006. [PTM+10] R. Pant, A. Tunpan, P. Mekbungwan, R. Virochpoka, K. Kanchanasut. DTN overlay on OLSR network. In Proc. AINTEC ’10. Pp. 56–63. ACM, 2010. [RH12] C. Raffelsberger, H. Hellwagner. Evaluation of MANET Routing Protocols in a Re- alistic Emergency Response Scenario. In Proc. WISES ’12. Pp. 88 –92. IEEE, 2012. [SB07] K. Scott, S. Burleigh. Bundle Protocol Specification. IETF RFC : 5050, 2007. [SEGD11] C. Sommer, D. Eckhoff, R. German, F. Dressler. A Computationally Inexpensive Empirical Model of IEEE 802.11p Radio Shadowing in Urban Environments. In Proc. WONS ’11. Pp. 84–90. IEEE, 2011. [SRT+10] T. Spyropoulos, R. N. Rais, T. Turletti, K. Obraczka, A. Vasilakos. Routing for dis- ruption tolerant networks: taxonomy and design. Wireless Networks 16(8):2349– 2370, Nov. 2010. [TVB11] X. Tie, A. Venkataramani, A. Balasubramanian. R3: Robust replication routing in wireless networks with diverse connectivity characteristics. In Proc. MobiCom ’11. Pp. 181–192. ACM, 2011. [WC10] J. Whitbeck, V. Conan. HYMAD: Hybrid DTN-MANET routing for dense and highly dynamic wireless networks. Computer Communications 33(13):1483–1492, Aug. 2010. Proc. SACS/SoCoDiS 2013 12 / 12 Introduction Hybrid MANET-DTN routing schemes State-of-the-art hybrid MANET-DTN routing schemes Comparison of hybrid MANET-DTN approaches Evaluation of a realistic emergency response network Simulation setup Results Discussion and outlook