Multi-objective performance optimization of a probabilistic similarity/dissimilarity-based broadcasting scheme for mobile ad hoc networks in disaster response scenarios

Multi-objective Performance Optimization of a Probabilistic Similarity/Dissimilarity-based Broadcasting Scheme for Mobile Ad hoc Networks in Disaster Response Scenarios D. G. Reina1 , J.M. Leon-Coca2, S. L. Toral3, E. Asimakopoulou4 , F. Barrero5, N. Bessis6 Abstract: Communications among crewmembers in rescue teams and among victims are crucial to relief the consequences and damages of a disaster situation. A common communication system for establishing real time communications between the elements (victims, crewmembers, people living in the vicinity of the disaster scenario, among others) involved in a disaster scenario is required. Ad hoc networks have been envisioned for years as a possible solution. They allow users to establish 1 D. G. Reina Electronic Engineering Department, University of Seville, Spain, dgutierrezrein[email protected] 2 J. M. León-Coca Electronic Engineering Department, University of Seville, Spain, [email protected] 3 S. L. Toral Electronic Engineering Department, University of Seville, Spain, [email protected] 4 E. Asimakopoulou School of Computing and Maths, University of Derby, UK, [email protected] 5 F. Barrero Electronic Engineering Department, University of Seville, Spain, [email protected] 6 N. Bessis School of Computing and Maths, University of Derby, UK, [email protected] decentralized communications quickly and using common devices like mobile phones. Broadcasting is the main mechanism used to disseminate information in all-to-all fashion in ad hoc networks. The objective of this paper is to optimize a broadcasting scheme based on similarity/dissimilarity coefficient designed for disaster response scenarios through a multi-objective optimization problem in which several performance metrics such as reachability, number of retransmissions and delay are optimized simultaneously. Keywords MANETs, Disaster Response Scenarios, Similarity/Dissimilarity Coefficients, Multi-objective optimization 1 Introduction Communications in disaster scenarios are crucial especially during the immediate hours after the disaster occurred in order to coordinate the relief actions. The actual scenario can be unknown for the crewmembers involved in the rescue operations or it can be entirely different from what it was before the disaster due to damages in the scenario. Consequently, the exchange of data on the current state of the scenario plays an important role and can be useful to save lives and alleviate the possible damages. The fixed infrastructure like cellular networks can be inaccessible or degraded due to the disaster [1]. In addition, the performance of these cellular networks can be worsened when a high number of users try to access them simultaneously. Another flaw is the higher power consumption of 3G technologies used in cellular networks to transfer data compared to the Local Area Networks (LANs) technologies like Wireless Fidelity (WiFi) or Personal Area Networks like Bluetooth. For these reasons, Wireless Mobile Ad Hoc Networks (MANETs) [1][2][3][4] can be an appealing alternative to be used in disaster response scenarios [5][6][7][8]. MANETs can connect mobile devices through wireless links without the need for a fixed infrastructure. Since nowadays smart phones are equipped with wireless technologies such as WiFi and Bluetooth they can easily form a MANET. These communications can serve to connect both victims and crewmembers improving technical actions like triage, identification, rescue, and evacuation in the disaster area. Furthermore, MANETs can also be used as a complementary network of Public Protection and Disaster Relief (PPDR) radio networks such as the Terrestrial Trunked Ratio (TETRA) [9] and TETRAPOL [10]. Although the TETRAPOL systems can also perform in direct mode (ad hoc mode) without infrastructure, communications between crewmembers and victims are not possible with these systems because the victims will not have access to TETRAPOL terminals. It has been stated that the collaboration between victims and crewmembers is crucial in disaster response scenarios [11]. In addition, the TETRA systems have low rates so these are not suitable for transferring data such as images and video. They are primarily used for voice communications and text messages. Data dissemination in MANETs is an active research field [12][13][14]. In MANETs data dissemination in all-to-all fashion is normally performed by flooding (the simplest broadcasting mechanism). In flooding technique each device retransmits once the incoming messages. This type of communications is suitable for disaster scenarios since the same information can be useful for many users in the network at the same time. However, it has been demonstrated that it is inefficient in term of bandwidth and power consumption due to the well-known broadcast storm problem [15]. Many alternatives of flooding can found in the literature [14], among them probabilistic broadcast [16][17] is interesting in terms of robustness against failures and attacks, and also exhibits low power consumption compared to deterministic broadcast. Owing to these appealing features, probabilistic broadcast can be suitable for disaster response scenarios among other applications such as routing protocols and resource discovery [18][19]. In probabilistic broadcast, each node can have a different forwarding probability and it can be adjusted to achieve the target objectives of data dissemination (high reliability, low end-to-end delay, low power consumption, etc). In this paper, we proposed a probabilistic broadcast scheme (DissBroadcast) based on similarity/dissimilarity metrics which will be optimized for disaster response scenarios through an evolutionary multi-objective optimization problem considering multiple performance metrics simultaneously and a disaster mobility model which models the tactical movements of crewmembers in a disaster area. This paper continues as follows. Section II details the related work on MANETs in disaster response scenarios. Section III introduces broadcasting as multi-objective optimization problem. Section IV presents the proposed probabilistic broadcast mechanism (DissBroadcast) to be optimized. Section V describes the proposed methodology for optimizing the proposed broadcast scheme consisting of integrating a disaster mobility model, the evolutionary framework DEAP and the event driven simulator NS-2. Section VI shows the obtained simulations results and conclusions are finally provided in section VII. 2 Related work The use of MANETs for disaster relief is not a new idea [5][6][7][8]. Due to the decentralized features of MANETs, these have been envisioned as an appealing technology to be used in disaster response scenarios [3]. MANETs can be implemented in different ways 1) in Unmanned Aerial Vehicles (UAV) and drones, 2) in robot assisted rescue teams, and 3) in human rescue teams carrying wireless devices. In all these cases, the ad hoc networks are used to disseminate the collected information from the disaster area such as voice and data like images and videos, in order to coordinate the technical emergency and rescue actions. In [1] the authors stated the main features required of two types of networks used in disaster scenarios such as Disaster Recovery Networks (DRN) and Search and Rescue Network (SRN) which are: quick response, life expectancy of the network, interoperability, tariff-free operation, network coverage, support for heterogeneous traffic types, network capacity, ease of use and cost equipment cost, outdoor and indoor operation, high precision for localization and search operation. Mobile ad hoc networks [1], [3] exhibit many of the mentioned features so they are suitable for DRN and SRN and consequently for disaster response networks in general. With regard to the evaluation of ad hoc networks in disaster scenarios, in [5] and [6] several popular routing protocols for MANETs (AODV [20], AOMDV [21], and DSR [22]) were evaluated in disaster scenarios, considering different communication patterns. Notice that routing protocols in MANETs are responsible for establishing a communication path between a source node and a destination node [2]. As for the obtained results in [5] and [6], the reactive routing protocol AODV (Ad hoc Ondemand Distance Vector) is the most suitable protocol for the scenarios considered. AODV is a distance vector-based routing protocol which maintains routing table on demand [20]. A similar evaluation was conducted in [23] in which also several routing protocols for MANETs (AODV [20], DYMO [24], BATMAN [25], and OLSR [26]) were evaluated under a real emergency scenario modeling an explosion in a chemical facility. According to the results shown in [23], AODV again achieved the best results. Although routing protocols are fundamental in the performance of MANETs, it is not probable that communication links among nodes last for long time in disaster response scenarios due to the harsh conditions in terms of obstacles, noisy and mobility. Consequently, direct dissemination techniques like broadcasting seem to be more suitable in such complex and changeable scenarios. In the light of direct dissemination techniques, Delay Tolerant Networks (DTN) [4] are a variant of classic MANETs based on the carry-store-and forward paradigm. In [8], several dissemination schemes for DTNs (PRoHET [27], MaxProp [28], and TTR [29]) were evaluated in disaster scenarios. According to the results, MaxProp is the best technique in terms of packet delivery ratio (PDR), and TTR in terms of energy consumption. Regarding the use of evolutionary algorithms in disaster response scenarios, in [30] the authors proposed to use a genetic algorithm for positioning auxiliary beacon nodes to improve the connectivity among crewmembers in rescue operations. The objective was to improve the reachability of broadcast messages through static beacon nodes. Moreover, in [31] the authors optimized broadcasting in disaster scenarios through a single objective genetic algorithm. The single objective was to optimize the reachability of the broadcast mechanism. Nonetheless, as it will be shown in this paper, broadcasting must be seen as a multiobjective problem in which several performance metrics need to be optimized simultaneously. This paper is a further step by determining the Pareto front (optimal solution for each considered objective) of a proposed broadcasting scheme (DissBroadcast) based on the similarity/dissimilarity of nodes in the network. 3 Broadcasting in disaster response scenarios as a multi-objective problem When a node wants to spread out a crucial message in a disaster scenario, it should be done efficiently. It means that it must be transmitted as fast as possible, as reliable as possible and consuming as low resources as possible, among other features. However, the aforementioned requisites cannot be accomplished simultaneously. On one hand, if we want to increase reliability we must increase the number of packets sent, and consequently, we will also increase the power consumption. On the other hand, if we want to guarantee a low delay in communications, we must reduce the number of messages transmitted in order to reduce contention in the network (considering a shared wireless medium like 802.11 which is typically used in ad hoc networks), and consequently, we will worsen the reliability. These are clear examples of how the objectives of the dissemination of messages through broadcasting in disaster response scenarios are counterbalanced. A possible solution for considering all the performance metrics together can be to define a new performance metric as a combination of them, weighting every single metrics and tuning the broadcasting procedure to optimize the new global metric. This method can be solved using a single objective evolutionary algorithm like a Genetic Algorithm (GA) [32] or a Particle Swarm Optimization (PSO) algorithm [33]. However, this solution can be dominated by any of the mentioned single metrics (reliability, delay or power consumption) leaving the others with a very low value, and, as a result, providing an unbalanced solution. An alternative solution is to define the broadcasting mechanism as a Multi-objective Optimization Problem (MOP) in which several metrics will be optimized at the same time (minimized and/or maximized), and then leaving to the decision maker the decision about which of the obtained possible solutions is the most optimal according to the intended requisites. Formally, a MOP can be defined as: Definition 1: minimize or maximize 𝑓𝑓(𝑥𝑥)= [𝑓𝑓 1(𝑥𝑥),𝑓𝑓 2(𝑥𝑥),…,𝑓𝑓 𝑘𝑘(𝑥𝑥)]𝑇𝑇 Subject to 𝑥𝑥 ∈ 𝑋𝑋 Where, the vector 𝑥𝑥 ∈ ℝ𝑛𝑛 is formed by n decision variables representing the parameters to be tuned in the optimization problem. The feasible set 𝑋𝑋 ⊆ ℝ𝑛𝑛 is implicitly determined by a set of equality and inequality constraints. The vector function 𝑓𝑓:ℝ𝑛𝑛→ ℝ𝑘𝑘 is composed by k scalar objective functions 𝑓𝑓 𝑖𝑖:ℝ𝑛𝑛→ ℝ(𝑖𝑖= 1, … , 𝑘𝑘;𝑘𝑘 ≥ 2). In the broadcasting problem, the vector function is composed of the metrics to be optimized such as reachability, delay, and number of packets transmitted, among others. The decision variables will depend on the type of broadcasting used. Thus the decision variable will be responsible for adjusting the forwarding probability at each node. These decision variables can vary from density parameters like the number of nodes to topological features of the network like dissimilarity measures. In a MOP there is no a straightforward method to know whether a solution is better than others. The decision maker will be responsible for deciding which solution is the best one in any case. The most common used method to compare solutions is the so-called Pareto dominance relation in which instead of using a single optimal solution, a set of different solutions with different trade-offs among objectives is considered. This set of solutions is known as Pareto optimal solutions or non-dominated solutions [34]. Notice that a solution in a multi-objective problem is a vector in which each dimension represents a different objective. In a MOP the Pareto dominance is defined as follows: Definition 2: We say that a vector 𝑣𝑣1 Pareto-dominates vector 𝑣𝑣2, denoted by 𝑣𝑣1≺𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑣𝑣2 (considering a minimization problem), if and only if: ∀𝑖𝑖 ∈ {1, … , 𝑘𝑘}:𝑣𝑣1≤ 𝑣𝑣2 (1) and 𝑖𝑖 ∈ {1, … , 𝑘𝑘}:𝑣𝑣1≤ 𝑣𝑣2 Let us consider Figure 1 to illustrate the Pareto dominance in a MOP. In Figure 1 a two-objective optimization problem (𝑓𝑓 1,𝑓𝑓 2) with four possible solutions (𝑣𝑣1,𝑣𝑣2,𝑣𝑣3,𝑣𝑣4) is represented. Both objective functions (𝑓𝑓 1,𝑓𝑓 2) want to be minimized. It is easy to see that 𝑣𝑣3 is strictly less than 𝑣𝑣2 in both objectives so 𝑣𝑣3≺𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑣𝑣2. At the same time 𝑣𝑣3≺𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑣𝑣1 because for 𝑓𝑓 1 both solution obtain the same fitness. On the other hand, it is also easy to see that 𝑣𝑣4 does not dominate 𝑣𝑣3 because 𝑣𝑣4>𝑣𝑣3 for 𝑓𝑓 1. As a rule, the goal of a MOP is to find all the non-dominated solutions. This set of solution is known as Pareto front and the set of variables for such Pareto front is known as Pareto optimal set. f 1 f 2 V 1 V 2 V 3 V 4 Figure 1. Illustration of Pareto dominance in a multi-objective optimization problem In the proposed multi-objective broadcasting problem for disaster response scenarios, we will consider three objective functions such as reachability, number of messages transmitted, and the delay. These met- rics are widely used to evaluate broadcasting schemes in MANETs and they are defined as follows [15]: • Reachability (Re): it is the ratio of nodes receiving the broadcast packet to the total number of nodes in the network. The goal is to achieve high reachability since it means that many nodes will receive the emergency message. • Number of messages transmitted (Nt): is the total number of broadcast messages transmitted among nodes in the network. It is desirable to achieve a low number of messages transmitted since Nt is related to the total power consumption in the network. • Delay (d): it is the total time elapsed since the packet is originated at the source nodes until the last receiving node receives the packet. Since the broadcast messages will include relevant information, it is necessary that nodes receive the messages as fast as possible. According to the above definitions of the performance metrics, achieving a high Re is a maximization problem whereas achieving a low Nt and d are both minimization problems. The variables to be tuned in the broadcast scheme will be described in the next section where the proposed broadcast scheme based on a similarity/dissimilarity coefficient is presented. Figure 2 represents the directions towards the optimal solutions for each target metric will go. Figure 2. Target metrics Figure 4. Evaluation framework The Disaster_Mobility.pl is a script coded in Perl used to configure the input parameters of BonnMotion in order to generate the disaster area mobility model. The traffic_pattern.tcl is a script coded in Tcl used to determine the communications among nodes in the network. The mentioned scripts will generate the mobility and communication patterns which will be later used by the script disaster.tcl, a script coded in Tcl including all the required simulation parameters. Once the NS-2 simulation ends, the output is a trace file which contains all the simulation events occurred during the simulation time. This trace file will be the main input of the script Target_metrics.py which calculates the target metrics (Re, Nt, and d). Since the proposed is probabilistic, we average out the results of five runs for each individual included in the population. Then, the calculated target metrics will be used by the DEAP framework to determine the non-dominated solutions and generate the new generations. Regarding the configuration of NSGA-II, the off-spring generations are obtained using a two-point crossover with probability of 0.9 and a mutation probability of 0.05. The population size is 64 and the number of generation is 15. 5.2 Disaster Area Mobility Model The disaster area mobility model is based on a method called separation of the rooms [46][47]. Using this method, the disaster scenario is divided into different context-based areas. These areas are: incident site, casualty treatment area, transport zone, and technical operational command zone. Figure 5 illustrates the disaster scenario. • Incident site: the place where the disaster happened. Here injured people are normally found waiting to be transported to a casualty treatment area. With regard to the rescue team, fire-fighters or police officers could belong to the incident site. Consequently, in this are we will find only mobile nodes. Notice that the mobility model does not model the victims so it only models the mobility of rescue teams. • Casualty treatment area: consists of two places, (a) patient waiting for treatment and (b) the casualty clearing station. In (a), people wait for a first inspection and classification; after that they can be transported to a casualty clearing station (b) in which patients will be waiting to be transported to a hospital. Paramedics belong to this area. • Transport zone: an area where transport units wait in stand-by areas to transport people to hospitals. The transport units can be either ambulances or rescue helicopters. • Technical operational command: the zone where the rescue operations are commanded, usually located in the casualty treatment area. In this zone only static nodes are found. INCIDENT LOCATION Patients waiting for treatment Casualty clearing station Casualty clearing station Casualty clearing stations Ambulance Parking Point Technical Operation Command DISASTER AREA SCENARIO Figure 5. Illustration of zones in the disaster mobility model The disaster mobility model used in the paper has already been used to model real disaster scenarios. In [46] a suspension railway crash, which happened in Wuppertal (Germany) in 1999, was studied. In addition, in the authors also analyzed another disaster happened because of a fire in an amusement park in Cologne (Germany) in 2001. Furthermore, in [23] the same mobility model was used to model a disaster occurred because of an explosion in chemical industry. 6 Simulation results and discussion In this paper we use the simulation scenario proposed in our previous work [30] which is composed of one incident location, one patient waiting for treatment area, two casualty clearing stations, one ambulance parking area, and one technical operation area. Table 1 includes more details about the features of the technical areas. Area Size (m2) Nº Nodes Nº Transport nodes Incident site 200 x 200 30 30 Patient waiting for treatment 100 x 100 10 8 Casualties clearing stations 150 x 150 15 0 Parking 250 x 200 30 25 Technical operation 100 x 50 2 0 Table 1. Number and type of nodes in the disaster mobility model The movements of nodes inside and outside the mentioned zones are illustrated Figure 6. Figure 6. Movements of nodes in the disaster mobility model In Table 2 we include the general simulation parameters used in each simulation run. The number of flows among nodes in each zone of the disaster mobility model is 20. The source and destination nodes are chosen randomly. The type of traffic used is Constant Bit Rate (CBR). The simulation time is 150 s and a warm up period of 50 s has been selected. Consequently, the results are collected from 100 s of the total simulation time. Simulation Parameter Value Nº nodes 102 Scenario size 850 x 300 m2 Propagation model Two-ray ground Carrier frequency 914 MHz Node’s transmission range 150 m MAC protocol 802.11 Traffic Constant Bit Rate (CBR) Nº connections 20 Mobility model Disaster Mobility Model Simulation time 150 s Table 2. Global simulation parameters In Figure 7 the obtained Pareto front is shown. It is easy to see that the trade-off situation among the three target objectives. The obtained Pareto front is composed of 95 non dominated solutions. Notice that this number can vary depending of the number of generations run. Figure 7. Pareto front The 2D projections of the above Pareto front are shown in Figure 8, Figure 9, and Figure 10. Regarding Figure 8, it is observed a clear trade-off between the Reachability and Nt. It means that if a solution with high Reachability want to be obtained the number of transmission must also be high. Figure 8. Reachability vs Nt in the Pareto front In Figure 9 it is observed the tendency of a higher delay when the Reachability is high. However, it is also possible to achieve acceptable values of Reachability with low Delay as it is seen in Figure 9 on the right. A similar behavior is also observed in Figure 10, where, the normal tendency is that if Nt increases, the Delay will also be increased mainly because of congestion in the network. Notice that considering the obtained Pareto front, a decision maker, for instance located in the technical operation zone, can select the parameters of the proposed DissBroadcast scheme in order to achieve the target objectives. Figure 9. Reachability vs Delay in the Pareto front Figure 10. Nt vs Delay in the Pareto front Regarding the above presented simulation results, it is clear that broadcasting in ad hoc in general and more specifically in disaster response scenarios can be modeled as multi-objective optimization problem. There is a trade-off between the performance metrics of broadcast such as reachability and number of transmitted packets. The methodology proposed in this paper can be applied to real disaster scenarios in which the separation of rooms method in applicable such as fires, explosions, etc. The communications devices can be smart phones with specific software responsible for exchange and maintain information. The proposed evolutionary framework can be also used to optimize routing in ad hoc networks and data dissemination schemes in delay tolerant networks. In those cases the performance metrics are also counterbalanced so the routing problem can also be seen as a multi-objective optimization problem. However, the applicability of routing in disaster response scenarios is limited by the fact that high mobility conditions along with hash and noisy condition make difficult to establish stable path to route packets, which is the main assumption in to effectively route packets from a source node to one or several destination nodes. For this reason, the proposed broadcast algorithm is good alternative to routing since it can dynamically adjust the forwarding probability considering only topological features. 7 Conclusions The broadcasting problem in disaster response scenarios has been evaluated through a multi-objective optimization problem. We propose DissBroadcast, a broadcasting scheme based on topological characteristics of nodes in order to optimize three widely used metrics such as reachability, number of retransmissions and delay. The main advantage of the proposed scheme with respect to others found in the literature is that the proposed scheme can adapt the forwarding decisions based on the target performance metrics which can vary as the time goes by. We demonstrated the feasibility of the proposed approach with simulation results based on an implemented framework. This framework is based on the widely used NS-2 simulator, the evolutionary framework deap, and the mobility generator BonnMotion. The Pareto front of a disaster scenario sample has been presented. This Pareto front can be used by a decision maker in order to select the most suitable parameters of the proposed DissBroadcast to achieve the target objectives in terms of reachability, number of retransmissions and Delay. As future work the proposed scheme will be run online collecting the mobility data from the nodes. 8 Acknowledgements This work was supported in part by the University of Seville under the PhD grant PIF (Personal Investigador en Formación) of Daniel Gutiérrez Reina. 8 References [1] Lakshmi Narayanan R.G, Ibe O. C (2012) A joint network for disaster recovery and search and rescue operations, Computer Networks 56:3347-3373. [2] Sakar S. K, Basavaraju T.G, and Puttamadappa C (2008) Ad hoc mobile wireless networks: Principles protocols, and applications. Auerbach Publications, Taylor & Francis Group. pp. 24. [3] Reina D. G, Toral S. L, Barrero F, Bessis N, Asimakopoulou E (2013) The role of ad hoc networks in the internet of things, Internet of Things and Inter-cooperative Computational Technologies for Collective Intelligence 340:89-113. [4] Conti M, Giordano S, Martin M, Passarella A (2010) From Opportunistic networks to opportunistic computing, IEEE Communications Magazine 48:126-139. [5] Reina D. G, Toral S. L, Barrero F, Bessis N, Asimakopoulou E (2011) Evaluation of ad hoc networks in disaster scenarios. Third International Conference on Intelligent Networking and Collaborative Systems (INCOS, 2011), pp. 759-764. [6] Reina D. G, Toral S. L, Barrero F, Bessis N, Asimakopoulou E (2012) Modelling and assessing ad hoc networks in disaster scenarios. Journal of Ambient Intelligence and Humanized Computing. D.O.I. 10.1007/s12652-012-0113-3. [7] Reina D. G, Hinojo J. M., Toral S.L, Barrero F, Cortés F, Soto M, Marsal E (2010) A wireless in-door system for assisting victims and rescue equipments in a disaster management. Intelligent Networking and Collaborative Systems (INCOS, 2010). [8] Martín-Campillo A, Crowcroft J, Yoneki E, Martí R (2013) Evaluating opportunistic networks in disaster scenarios. Journal of Networks and Computer Applications 36:870-880. [9] Terrestrial Trunked Radio (TETRA) (2010) Voice plus Data (V + D), Part 2: Air interface (AI), European Standard (Telecommunication series), ETSI EN 300 392-2 [10] Tetrapol specifications (1998) Part 1: General network design, Part 2: Voice and data services in network and direct mode. www.tetrapol.com. Accessed 19 August 2013. [11] McEntire D. A (2007) Disaster Response and Recovery. Wiley. [12] Reina D. G, Toral S. L., Johnson P, Barrero F (2013) Hybrid Flooding Scheme for Mobile Ad Hoc Networks. IEEE Communicacion Letters 17:592-595.