Building a disaster rescue platform with utilizing device-to-device communication between smart devices *

Abstract

Recently, the world is facing more risk of natural disasters as a result of ongoing climate changes. One of the most critical obstacles in disaster mitigation (especially rescue operation) is lack of communication and localization of survivors in disaster sites. This article develops a disaster rescue platform for quick and accurate rescue operation with utilizing direct communication on smart hand-held devices such as Bluetooth and Wi-Fi. Specifically, we attempt to design an application-layer ad hoc network over smart devices without relying on centralized cellular networks or wireless access points. This study also incorporates a mobile localization algorithm to effectively perform disaster rescue objectives. Specifically, it aims (1) to accurately locate survivors, (2) to help rescuers to find victims quickly, and (3) to minimize calculation overheads for power saving on smart devices. This article verifies the proposed approach with presenting simulation and implementation results compared to other studies.

Keywords

Mobile communication device-to-device disaster rescue ad hoc network localization

Introduction

The world is facing more risk of natural disasters as a result of ongoing climate change. The economic costs and the number of victims of weather-related disasters have increased dramatically in recent decades. In response, many research works have concentrated on developing frameworks to overcome difficulties of disaster rescue operations. One of the most critical obstacles in disaster mitigation (especially rescue operation) is lack of communication and localization of survivors in disaster sites. For instance, when an earthquake or tornado strikes, many people are likely to be buried and trapped under the wreckage of buildings, bridges, and so on. In this case, survivors would try to use their smart hand-held devices to get help from outside and let rescuers know their locations to find them. But, it is very likely that survivors cannot get any signal available because conventional network infrastructure such as cellular network and Wi-Fi access points (APs) would be damaged as well as shown in Figure 1. Recently, many researchers have devoted their efforts to address this issue. Some of them are exploiting wireless ad hoc networks as replacement of damaged infrastructures^1–6 by exploiting Wi-Fi Direct⁷ and/or device-to-device (D2D) service in 5G cellular networks.⁸ A wireless ad hoc network refers to a network in which specialized pieces of equipment forming the backbone are not present. Instead, the client devices such as smart hand-held devices act as both client and backbone nodes. Such an ad hoc network is decentralized in the sense that there is no need of existing infrastructure to centrally manage communication.

Figure 1.

Target scenario: victims and a rescuer are all on ad hoc networks without GPS and infrastructure networks, and a rescuer moves around searching victims.

Especially, D2D communication is an emerging technology in 5G cellular networks. D2D provides direct peer-to-peer communication between mobile devices without going through a centralized eNodeB. Thanks to its Peer-to-Peer (P2P) nature, mobile devices easily associate and quickly create an efficient network between each other anytime anywhere. This feature makes it suitable for disaster and rescue scenarios. Also, Wi-Fi Direct⁷ is one of the most popular P2P technologies. Wi-Fi Direct is based on the Wi-Fi technology that most smart devices use to communicate with wireless APs. Conceptually, each Wi-Fi Direct smart device has a “software AP” installed on itself and so that it can essentially function as an AP. Other Wi-Fi-enabled devices can connect directly to this Wi-Fi Direct smart device.

Motivated by this observation, this article exploits a wireless ad hoc network over smart devices to effectively perform search and rescue operations in disaster sites.

Main idea is that we make it possible for both rescuers and victims to join an ad hoc network for quickly localizing and rescuing survivors. Specifically, this article proposes RescueTalk with which survivors can communicate with each other and even might be able to talk to outside of the disaster site to ask for help. Over this ad hoc network, this article also proposes a localization method which is customized to search-and-rescue operation in disaster sites with no GPS service and no infrastructure.

Many indoor localization methods^9,10 including our previous work¹¹ have been proposed so far. However, most of them require hand-held devices in everyday lives to be additionally equipped with other modules such as ultra-sonic, and hence these works are not suitable to support a disaster rescue scenario. Overall, main contributions of this article can be summarized as follows:

Propose and implement a mobile ad hoc network platform and develop an application-layer protocol over smart hand-held devices. With this platform, victim nodes can connect to each other and even to an outside rescue center so that rescuers can easily locate and rescue survivors.

Develop a localization method into the above ad hoc platform. The proposed algorithm is specifically customized to a disaster rescue scenario: (1) it accurately locates survivors, (2) it helps rescuers to find victims quickly, (3) it calculates positions incrementally to save power on smart devices, and (4) it works well with no GPS service.

Present a ad hoc routing algorithm optimized for the disaster rescue mission. In particular, the proposed routing method aims to quickly spread the location information over RescueTalk with small overhead when a node identifies its location through the localization algorithm or GPS.

The rest of this article is organized as follows. The next section overviews related works. In the following, the problem statement of this article is presented. Then, we introduce the proposed platform, routing protocols, and the localization algorithm. Afterward, we provide details of experimental results with the conclusion.

Related works

Disaster rescue

CodeBlue³ is one of the frameworks which use both infrastructure and wireless ad hoc networks. It provides health care service for victims in disaster. Vital signs of patients are reported to nearby paramedics and emergency technicians. In additional, locations of rescuers and victims are calculated with the received signal strength from infrastructure such as Wi-Fi APs. However, in many cases of disaster, conventional infrastructures are likely to get damaged easily and/or do not work properly. So, these infrastructure-dependent platforms have limitations to be practically deployed. There are other studies without conventional infrastructure. DistressNet⁴ establishes multiple heterogeneous networks (802.11, 802.15.4, and IPv6), some of which are dedicated to disaster management. However, such platform requires additional network modules to be installed and hence impractical to be implemented in everyday-use smart devices.

However, RescueMe project⁵ designs a rescue framework that needs few additional infrastructure. The framework securely collects locations of normal network users from their daily networking activity via conventional infrastructure. If disaster breaks out, it creates ad hoc networks and provides locations of survivors saved prior to disaster. However, it is dealing with the “prior” locations before disaster. So, it would not be accurate if victims are moving and natural disaster happens inside building where no GPS available for a while.

Location service

Many researchers have proposed various versions of localization algorithms. Localization algorithms can be classified into two categories: (1) anchor-based and (2) anchor-free methods. Anchor-based algorithms assume multiple anchor nodes with known positions obtained by GPS or other infrastructure-aided methods. With such information of anchors, algorithms calculate locations of unknown nodes.^9–13 For example, Niculescu and Nath⁹ proposed ad hoc positioning system (APS), which is a distributed algorithm similar to distance vector routing. However, this method works well only with the high connectivity between nodes. Some studies including Horiba et al.¹⁰ and Kim et al.¹¹ proposed the indoor localization algorithms for non-line-of-sight (NLOS) scenarios. Also many multilateration algorithms, called MLAT, have been proposed including but not limited to.^12,13 MLAT methods basially use the position information of the anchor node that are several hops away. This algorithm refines the position using the least square estimation and prevents accumulation of errors using Kalman filters. However, this method has limitations that when the network has not sufficient anchor nodes or when anchor nodes’ locations have error factors, then their calculation results are not accurate either. We show these features in the evaluation section compared to our proposed method.

Recently, many researchers have adopted machine learning methods to overcome these NLOS limitations. The acoustic location processing system (ALPS) system,¹⁴ for example, combines Bluetooth and ultrasound signals and applies machine learning algorithms on the received signals. Xiao et al.¹⁵ also used similar learning systems. However, performance of the above learning-based systems might be heavily dependent on learning parameters, which are inherent limitations of machine learning systems. Also, the map-based system requires pre-processing of the target area, which might not be suitable in some real-world disaster scenarios.

As anchor-free localization methods, mobile beacon methods have been proposed.^16–19 Generally, localization error is reduced as the number of anchor nodes increases. Based on this observation, Sichitiu and Ramadurai¹⁶ proposed a localization algorithm that only uses a single mobile anchor and considers each of its dynamic locations as an anchor. Sun and Guo¹⁷ suggested a localization scheme based on probabilistic estimation, but the trajectory of the mobile anchor is fixed to helix trajectory. Ssu et al.¹⁸ and Yu et al.¹⁹ also proposed an algorithm which selects the anchor points on the received signal strength indication (RSSI)-range circle and calculates the node position using the characteristic of the circle and perpendicular bisector of a chord. However, these previous works assume the trajectory of the mobile anchor is fixed and so the locations of the mobile anchors are assumed to be pre-known. These constraints make hard it to be applied in our target disaster and rescue scenario. In our target scenario, we consider that rescuers would go into the disaster sites where rescuers’ trajectory cannot be static and so rescuers’ locations are not pre-known just like unknown victims.

Problem statement

In what follows, we describe the problem statement by presenting the target scenario and key challenges to be solved.

Target scenario

In most natural disaster scenarios such as an earthquake, a tornado, a landslide, and so on, victims are very likely to be buried and trapped in the wreckage of buildings, bridges, houses, and so on. To find and rescue them, rescuers would be deployed into the disaster sites. However, under the wreckage of buildings, network infrastructures such as cellular networks and Wi-Fi APs are very likely to be damaged and so conventional communications among victims and rescuers are not possible. Also, GPS are unlikely to work under disaster sites as well. To reflect these observations, we propose an ad hoc network method targeting to such a disaster scenario and attempting to help rescuers by accurately and promptly locating survivors without GPS and infrastructure networks. Figure 1 illustrates the target scenario of this article. In particular, we assume that each rescuer under disaster sites moves around to find victims. Most rescuers and victims do not have any network infrastructure available except a node at the edge of the disaster site such as a victim node $D$ in Figure 1. The edge node might have network connection to an outside the disaster site. By exploiting this edge node, we attempt to build an ad hoc network with which victims can send their help messages to an outside rescue center.

With such ad hoc network, this article also incorporates a localization method specialized in this disaster scenario. For example, suppose dotted lines in Figure 1 represent a trajectory of a rescuer. As the rescuer moves, a victim A can receive beacon frames from three different locations, which makes it possible to calculate a location of victim $A$ by itself. In that way, victims close to rescuers can be located first. After that, the location information of victim $A$ is propagated to victim $B$ and $C$ , then victim $C$ can calculate its location using location information received from victim A over an ad hoc network among them. Finally, victim B’s location could be found after all.

Challenges

Given a target disaster and rescue scenario in the previous section, there exist several challenges as follows:

No infrastructure available. In the target disaster site, we assume that both rescuers and victims do not have any centralized and infrastructured communication available (such as cellular networks and AP-based Wi-Fi network). Only communication method they can use is an ad hoc network among them. This implies that their networks are very likely to be isolated network and does not have a connection to outside. So, we assume that there would be no central command center and so each rescuer and victim should make a decision by themselves.

No GPS service available. In the given target disaster situation, GPS might not work properly at rescuers’ sides as well as victims’ sides.

Nodes are mobile. A rescuer is very likely to be mobile, not stationary. So, the localization method should consider not only between static nodes but also mobile nodes.

Power limitation. Especially, victims are very likely to have limited power resource (e.g. battery) and so the proposed method should be power-efficient and have low complexity. Especially, the proposed localization method should converge fast to find victims as fast as possible to rescue them.

Proposed rescue platform: RescueTalk

This article designs and develops an application-layer ad hoc network, called RescueTalk. The proposed platform consists of three parts: (1) ad hoc platform development, (2) survivor localization, and (3) ad hoc routing, In the following, we present the details of these three parts.

Ad hoc network architecture

This article designs and develops an application-layer ad hoc network called RescueTalk on smart devices based on open-source project.²⁰ In the developed ad hoc network application, we first design an application-layer protocol customized for localizing victims and messaging among the victims and rescuers, as illustrated in Figure 2. When the infrastructure such as Wi-Fi and cellular base stations is be available in the disaster site, the rescuer and victims are able to communicate and localize each other using the RescueTalk. Also, when an edge node is still connected to the outside disaster site (e.g. a rescuer node 2 in Figure 2) and receives RescueTalk messages from a victim, it can forward the messages to the outside rescue center for further rescue process. Specifically, the edge node performs encapsulation or decapsulation to forward RescueTalk packets to the outside or to forward the outside packets into an ad hoc network, respectively. To make this scenario possible, this article designs RescueTalk message formats and protocols as shown in Figure 3. Using this application-layer protocol, each node under the disaster site can communicate with each other and also can further forward this message through an edge node to outside rescue center. Note that there is no need to modify network infrastructures such as base stations and Wi-Fi APs because the proposed platform is an application-layer ad hoc network. We only need to install applications to each mobile device for setting up the platform.

Figure 2.

RescueTalk scenario.

Figure 3.

RescueTalk protocol message formats.

Survivor localization algorithms

On top of the RescueTalk platform, this article also proposes a localization method to quickly and accurately rescue survivors. The proposed algorithm is specifically customized for the disaster scenario. First, it does not rely on the access to network infrastructure such as Wi-Fi APs or cellular networks and it rather utilizes 5G D2D communication or Wi-Fi Direct to identify survivors’ locations. Also, it considers the situation where GPS service is not available or limited.

Another important design goal is to reduce computational overheads because victims are very likely to have limited power resource (e.g. battery). Hence, we develop an computationally light-weight algorithm attempting to minimize energy consumption. From this perspective, the previous anchor-based and anchor-free localization studies have limitations to be applied to our target scenario. For example, the multilateration method is not incremental and uses all of information received from the beginning, which causes expensive computational overheads and can cause a longer delay to obtain the solution. Especially when the anchor nodes’ locations (i.e. rescuers’ locations in our target scenario) are not accurate, then computation time further might further increase. Also, anchor-free algorithms such as Ssu’s work use computationally complex calculation methods to estimate trajectory of nodes based on pre-known information which might not be available in disaster environments.

Furthermore, the previous localization methods based on multilateration^12,13 have fundamental limitations to be applied to the disaster site. This is because they all assume that anchor nodes’ locations are accurate and they attempt to compute unknown locations of other nodes based on these anchors’ locations. However, in the disaster and rescue scenario, the anchor node’s location might be also inaccurate just like survivors’ locations. However, some anchor-free localization methods rely on pre-known information or require additional hardware equipped.^16–19 However, these features make the previous studies be unsuitable for the disaster scenario.

To solve these challenges, this article proposes a new localization method specialized for disaster rescue operation extending the previous genetic-based localization method.²¹ The proposed localization method has several unique features. First, the proposed method is based on genetic algorithm (GA) to obtain an accurate location by minimizing error factors of rescuers’ locations as well as victim nodes’ locations. GA is known to provide a robust and global solution in many optimization problems especially when the target problem is a multi-objective optimization in noisy environments. Note that GPS and other infrastructures might not be available in our target scenarios, which increase noise factors. Furthermore, GA searches a population of candidate solutions in parallel and it has the ability to avoid the local optimal solution while traditional methods might be trapped into the local solution because they search from a single point.^22,23 Second, the proposed algorithm attempts to reduce computational complexity compared to other methods using an incremental strategy.

Finally, the proposed algorithm utilizes a rescuer’s mobility so that it considers each location along a rescuer’s track as a different anchor point. Figure 4 shows that a rescuer moves around the disaster site and each location of a rescuer is considered as a separate anchor node. Specifically, an initial position, $l_{1}$ , of a rescuer $A$ (i.e. anchor $A$ ) is considered at (0,0). Then, $2 nd$ , $3 rd$ , …, $n th$ positions (i.e. $l_{2}, l_{3}, \dots, l_{n}$ ) are calculated relative to the initial position using RSSI.¹⁰ Each position $l_{i}$ is considered as a separate anchor in the proposed GA algorithm. By doing this, even though there exists a single rescuer around a survivor, we can have multiple “logical” anchors in the algorithm and so the survivor’s location is accurately calculated.

Figure 4.

A rescuer moves around and each location is considered as a separate anchor node.

Basic GA consists four stages: initialization, crossover, mutation, and termination. The proposed incremental genetic mobile localization algorithm adopts the basic strategy of original GA and extends it specialized for our target disaster scenario. In particular, the proposed algorithm has five steps: wait_beacon, obtain_samples, incremental_selection, evaluation, crossover/mutation, and termination. The proposed algorithm incrementally selects the potential “individuals” in incremental_selection so that the algorithm does not start over from the beginning. Instead, it keeps the past results of the localization and just appends new information on top of it. Also, to effectively evaluate the selected individuals, the proposed algorithm defines fitness function customized to accurate localization procedure under disaster scenarios. Note that potential solutions are called individuals in GAs. In this article, candidate locations for the target victim with high fitness values are selected as individuals. Algorithm 1 is the detailed procedure of the proposed localization method for unknown victim nodes.

Algorithm 1. Genetic algorithm–based incremental mobile localization pseudocode.
1: procedure PROPOSED ALGORITHM 2: while $#$ of Beacons < 3 do 3: Wait Beacons(); 4: end while 5: while !localized and Maximum _ Trial is not reached do 6: Obtain Samples(); 7: Incremental Selection(); 8: Evaluate(); 9: $generation \leftarrow 0;$ 10: while !terminated and generation < Max _ Gene. do 11: if rand[0,1] > crossrate then Crossover(); 12: end if 13: if rand[0,1] > mutationrate then Mutation(); 14: end if 15: Evaluate(); 16: isTerminated(); 17: if terminated then 18: Unknown Node localized. 19: break; 20: end if 21: $generation$ ++; 22: end while 23: Wait Beacons(); 24: end while 25: end procedure

Algorithm 1. Genetic algorithm–based incremental mobile localization pseudocode.

1: procedure PROPOSED ALGORITHM
2: while

#

of Beacons < 3 do
3: Wait Beacons();
4: end while
5: while !localized and Maximum _ Trial is not reached do
6: Obtain Samples();
7: Incremental Selection();
8: Evaluate();
9:

generation \leftarrow 0;

10: while !terminated and generation < Max _ Gene. do
11: if rand[0,1] > crossrate then Crossover();
12: end if
13: if rand[0,1] > mutationrate then Mutation();
14: end if
15: Evaluate();
16: isTerminated();
17: if terminated then
18: Unknown Node localized.
19: break;
20: end if
21:

generation

++;
22: end while
23: Wait Beacons();
24: end while
25: end procedure

First, in wait_beacon step, a mobile rescuer assumes its initial location as (0,0) and moves around broadcasting its location via a beacon. The initial position is considered as one anchor. As a rescuer moves and broadcasts a beacon, its new location is considered as a different anchor as in Figure 4. Since no GPS available, a rescuer’s each location is calculated with the relative distance to the initial position and direction assuming that beacon broadcast interval is predetermined. Specifically, each position of a rescuer is calculated using acceleration double integration and magnetic sensors.²⁴

When a victim node gets a beacon from an anchor $i$ whose location is $l_{i} = (x_{i}, y_{i})$ , it calculates the distance $d_{i}$ from itself to the anchor based on RSSI of the beacon signal and it extracts the anchor’s location information, $l_{i} = (x_{i}, y_{i})$ from the beacon frame. The stored set $B$ of received beacons is defined as below where $n$ is the latest beacon number.

B = {b_{1}, b_{2}, \dots, b_{n}} where b_{i} = (l_{i}, d_{i})

(1)

In obtain_samples step, a node $k$ draws three circles, each of which corresponds to $b_{n}, b_{n - 1}, b_{n - 2}$ . However, because of the error factors, these three circles might create intersection area instead of only one intersection point. The intersection region of these three circles has high possibility of being node k’s actual position. A node $k$ then randomly extracts a certain number of sample points from this area and saves them into $Sample s_{n}$ .

In the incremental_selection and evaluation steps, a node $k$ performs the initial population by selecting “individuals” from $Sample s_{n}$ . The selection procedure is based on tournament method. First, we randomly pick two individuals from the sample set and then compare their fitness values determined by a fitness function as follows

F = \sum_{j = 1}^{i} \frac{(n + 1) - j}{{(dist (samplepoint, l_{j}) - dis t_{RSSI})}^{2}}

(2)

Then, samples with higher fitness value will be selected as individuals in GA and inserted into “population” (i.e. a set of individuals). Note that an initial position of a rescuer is defined as (0,0) and the following position is relatively calculated using acceleration and magnetic sensors of a smart device. Hence, calculation of such following positions would have error factors. This implies that as a rescuer moves, its location information gets less accurate because error factors are accumulated as a rescuer moves. To reflect this feature, we add $(n + 1 - j)$ as a weight factor to give lower priorities to the more recent location of a rescuer. Some existing individuals with low fitness values are removed from population and the newly selected samples will fill the population. We call this procedure as incremental because at each time node k evolves its position calculation using only three recent beacons, not all of them in the past.

In the crossover and mutation steps, we perform genetic operation.¹⁸ For crossover operation, we first pick the two best-fitted individuals, $in d_{a}$ and $in d_{b}$ . Then, we apply the following equation for crossover

in d_{b} = in d_{a} * (1 - α) + in d_{b} * α

(3)

in d_{a} = in d_{b} * (1 - α) + in d_{a} * α

(4)

where $α$ is a random value in range of [0,1]. Then, we perform mutation with two offspring generated by crossover as follows

in d_{j} = in d_{j} \pm γ

(5)

where $γ$ is a random number in range of [0, $in d_{j}$ ]. Such mutation and crossover operations with randomness are performed to avoid local optimal solution.

Finally, in the termination step, mutated two offspring are included to a gene pool (i.e. population) and two worst-fitted individuals are removed from the gene pool. This corresponds to one generation of GA. If the highest fitness value among all individuals in the gene pool is higher than a threshold (TERMINATE_ FITNESS), then iteration ends and we take the coordinate of the individual with the highest $F$ value to the position of node $k$ . If the highest $F$ is still lower than TERMINATE_FITNESS after MAX_ GENERATION iterations, the proposed GA algorithm stops.

RescueTalk routing algorithm

In order to make the proposed RescueTalk ad hoc platform more effective for rescue operations, we need to use a proper routing protocol in this platform. We can use existing traditional routing protocols such as traditional ad hoc on-demand distance vector (AODV), destination sequenced distance vector (DSDV), and dynamic source routing (DSR). However, these protocols generate control packets with increasing network the overhead, thereby promoting battery consumption.

However, geography-based routing protocols such as greedy perimeter stateless routing (GPSR) use geographical locations of nodes instead of constructing the routing tables. As a consequence, there is no process of path update, and therefore, there is little overhead. Although there is an advantage, it is not necessary to know the location information of all nodes beforehand. Especially, in the disaster scenario, location information is not likely to be known a priori at all.

To alleviate these problems of existing routing protocols, in this article, we propose a routing algorithm optimized for the disaster situation. In particular, if a node identifies its location through the localization algorithm or GPS, it broadcasts its location in an ad hoc network to spread the information over RescueTalk with small overhead. The key design goals of the proposed RescueTalk routing protocol are as follows:

Low overhead. In the disaster site, victims are very likely to have limited power resource (e.g. battery). Hence, the proposed routing method should be power-efficient and generate little overhead.

High packet delivery rate. The messages on RescueTalk platform are very likely to be urgent and so should be successfully delivered.

Customized for survivors’ localization. The main goal of RescueTalk is to rescue survivors by locating them. The proposed routing protocol should put the highest priority on this objective.

To achieve these goals, this article proposes a hybrid of flooding and location-based routing protocols. A flooding method is known to provide a high packet delivery rate at the cost of packet overhead. However, location-based protocols such as GPSR generate low overhead, but they have limitations that location information should be provided beforehand. The proposed hybrid method first uses a flooding mechanism to quickly detect locations of nodes and then changes to use GPSR when the position recognition is completed to some extent. Figure 5 shows a flowchart of the proposed hybrid routing algorithm.

Figure 5.

The flowchart of the proposed routing algorithm.

At the beginning, each node i checks if it has neighbor nodes to forward the data. Such neighbor information is gathered via hello messages exchanged between nodes. If there is no neighbor around it, then it fails to transmit the packet. If at least one neighbor node exists, it checks whether or not it has its own location information available. If it does not know its location, it performs flooding routing method because flooding does not require location information. If its location has been identified, the node i checks a percentage of the localized nodes in the neighborhood ( $= τ_{i}$ , that is, trustable factor). The $τ_{i}$ is defined as follows

τ_{i} = avg (\frac{{num}_{i}^{loc}}{nu m_{i}} + \sum_{nod e_{j} \in neighbo r_{i}} \frac{{num}_{j}^{loc}}{nu m_{j}})

(6)

Notations in the above equations are summarized in Table 1.

Table 1.

Notations in the proposed hybrid routing.

Notations	Definitions
$nu m_{i}$	Total no. of neighbors of a node $i$
${num}_{i}^{loc}$	No. of neighbors whose locations are identified.
$neighbo r_{i}$	A set of neighbor nodes of node $i$
$τ_{i}$	Trustable factor of a node $i$

If this $τ$ value is greater than a threshold, it changes its routing strategy from flooding to GPSR. If not, it chooses $k$ of its neighbors and does flooding packets only to these selected neighbors. At this time, the number of $k$ is determined as follows

k = ⌈ (1 - τ - c) * nu m_{i} ⌉

(7)

where $c$ is a constant value to control the degree of flooding.

Evaluation

In this section, we evaluate the proposed localization method by comparing it with well-known localization methods, multilateration, and/or Ssu’s algorithm.^12,19 Multilateration method is one of the anchor-based algorithms which calculate locations of unknown nodes with exploiting anchor nodes with known positions. And, Ssu’s method is an anchor-free algorithm which does not need anchor nodes but estimates a trajectory of nodes based on additional pre-known information. For such evaluation, (1) we first developed a NS-2 simulation platform to check validity of the proposed framework and then (2) we implemented it in a real world and verified the performance of the proposed methods.

NS-2 simulation

Once we develop NS-2 modules, we configure our simulation as follows. First, as we randomly deployed a rescuer and a victim node within 100 m × 100 m two-dimensional (2D) area. A rescuer node is designed to periodically broadcast its location via beacon, and a victim node receives beacon signals and tries to localize itself. The mobile rescuer starts at (0,0) and keeps moving around with calculating its relative location using accelerometer and magnetic sensor.²⁴ Also, the unknown victim node calculates the distance to the rescuer using a RSSI value of a received beacon from the mobile rescuer. In our NS-2 simulation, we added an error factor to both rescuer’s location calculation (8) and RSSI-based distance calculation between a victim and a rescuer (9). We come up with these equations based on the NS-2 simulation²⁵

lo c_{anchor} = lo c_{anchor} (1 + gaussian_noise () * NF)

(8)

dist = dist (1 + gaussian_noise () * NF)

(9)

where $gaussian_noise$ has a mean value of 0 and its standard deviation is 1, and NF is a noise factor with a value between 0 and 0.2.²⁵ Details of other simulation parameters are shown in Table 2. Note that we set up these parameters based on the literature,^26–28 common assumptions, and empirical observations of experiments (such setting is anecdotal in this article. We will work on finding the optimal setting of these parameters in the next research topic). With a given NS-2 setting, this article compares the proposed localization method with multilateration¹³ and Ssu et al.’s¹⁸ algorithms. We evaluate the performance of these works with two different aspects: (1) error rate and (2) time delay.

Table 2.

Simulation parameters.

Parameter	Parameter value
Population size	100
Crossover probability	0.9
Mutation probability	0.1
MAX_GENERATION	200
TERMINATE_FITNESS	150,000
Incremental selection proportion	0.2
Speed of a rescuer and victims	Randomly selected in arange of [0.5, 1.5] m/s

Localization error

As a metric to evaluate algorithms, we here define an error rate of localization for each node as follows

Error = \frac{distance (estimated_loc, actual_loc)}{MAX_RANGE} * 100

(10)

This error rate is a normalized value²⁵ and presented in percentage in Figure 6. Simulation results in Figure 6 show error rates by varying NF (noise factor) from 0 to 0.1. In the simulation scenario of Figure 6, both rescuer and victim nodes randomly move. We repeated these simulations 10 times, and a graph in Figure 6 shows the average error rate over 10 times of simulations. In this result, it is trivial that the more noise factor and the more location error rates. One important thing we observed is that the proposed algorithm outperforms other algorithms for most cases. Furthermore, as NF becomes large, the error rate of multilateration increases more rapidly, whereas our algorithm increases rather slowly. Note that localization errors of Ssu’s algorithm is huge in this experiment. This is because Ssu’s algorithm assumes that one of the anchors’ locations is pre-known or predictable, which is not the case in our disaster scenario experiment.

Figure 6.

Localization error rates with different NFs. Both rescuer and victim nodes randomly move.

One interesting thing we noticed is that when NF is very low, multilateration works better than the proposed method. It is explained by the fact that multilateration is not incremental and use all of information received from the beginning. Hence, multilateration method can give relatively more accurate output when NF is very low by exploiting all of the received information together. However, Since NF is accumulated in multilateration method, when NF becomes large multilateration method results in bad performance. This implies that multilateration is heavily dependent on NF of a rescuer’s position. From this perspective, it is desirable to use multilateration when there is little location error of a rescuer node. However, this argument does not hold anymore in our target disaster scenario where a rescuer keeps moving and its position cannot be obtained from GPS and infrastructure networks.

Convergence and time delay

In a disaster and rescue scenario, on-time rescue is very critical. Not only accurateness but also promptness is an important aspect of a localization method. From this point of view, we evaluate the proposed algorithm by examining time delay. As a metric to measure delay of calculation, we here count the number beacons a victim should receive in order to accurately find its location.

In Figure 7, a y axis represents the number of beacons and x axis corresponds to each simulation trial. In this simulation, we set up NF as 0.1 and repeated 50 simulation trials and assume both an anchor and a victim nodes are moving around. In average, multilateration methods used around 80 beacons while Ssu’s and our algorithms wait for only 45 beacons. This can be rephrased that multilateration method has to wait a longer time until it finds its own location while the proposed algorithms can locate its position relatively faster.

Figure 7.

The number of beacons received to be localized. Both rescuer and unknown victim nodes move.

We finally analyzed time delay features with a different metric: we examined changes of localization errors as simulation time goes as shown in Figures 8 and 9. The x axis represents a simulation time and the y axis means an error rate. In this simulation, we set up NF as 0 and 0.1 in Figures 8 and 9, respectively. We also configured that both rescuer and victim nodes moved around at the random speed in range of [0.5, 1.5] m/s. The results showed us that in the realistic scenario where the noise factor exists, the proposed algorithm performed far better than other two methods in the sense that it converged quickly (theoretical proofs of convergence of GAs are available²⁵). Furthermore, even in the ideal case where NF = 0, the proposed algorithm’s convergence delay is similar to others.

Figure 8.

Error rate versus converge time (with NF = 0).

Figure 9.

Error rate versus converge time (with NF = 0.1).

Routing algorithm evaluation

We now compared the proposed hybrid routing protocol with other traditional routing protocols in the above disaster scenario. As seen in Figure 10, all of routing protocols show that the packet delivery rate becomes better as the localization proceeds. It is important that even when there is no location information (i.e. the beginning of the simulation), the transmission success rate of the proposed algorithm is similar to that of flooding algorithm. However, GPSR shows a very low packet delivery rate because it does not obtain location information of itself and neighbors and so it cannot forward packets. However, if we once have location information, GPSR shows high packet delivery rates.

Figure 10.

Packet delivery rate of flooding, GPSR, and the proposed algorithm.

We also examined the overhead of each routing method by counting the the number of packets on the networks, as shown in Table 3. From this result, we found that the flooding method generates a large number of packets for high packet delivery and GPSR makes the least amount of overhead at the cost of a low packet delivery rate. Overall, we observe that the proposed hybrid mechanism takes both benefits of the flooding and GPSR in both aspects of packet delivery rates and overhead.

Table 3.

The number of transmitted packets.

Routing algorithm	No. of packets
Flooding	135,547
GPSR	65,576
Proposed hybrid $(α = 0.5)$	82,210

GPSR: greedy perimeter stateless routing.

Implementation

Once we confirmed the theoretical validity of the proposed platform based on NS-2 simulation as described above, then we implemented the platform to check practicality and feasibility in the real world. Specifically, we developed an application-layer ad hoc network on smart devices. In the developed RescueTalk, we implemented the localization and routing methods customized for localizing victims and messaging among the victims and rescuers, as illustrated in Figure 11. When the network infrastructure is not available in the disaster site, the rescuer and victims are able to communicate and localize each other using the RescueTalk. Also, RescueTalk messages received by a rescuer connected to the outside network (e.g. node 2 in Figure 11) can be forwarded to the outside rescue center for further rescue process. The left figure in Figure 11 is a screenshot of RescueTalk on one of the smart devices in our experiment showing the relative location of neighbors. If GPS is not available in the disaster site, RescueTalk uses the proposed localization algorithm. In this implementation, we used two smart devices and we enabled Wi-Fi based ad hoc networking features on them. Then, we installed the application with rescuer and victim modes. Table 4 shows the experimental environment and related parameters of our implementation.

Figure 11.

Test scenario and screenshots of implemented devices.

Table 4.

Implementation environment and parameters.

Parameter	Parameter value
Field size	5 m × 5 m
Field environment	Even ground, outdoor
Walk model	Random walk
Beacon period	1 s
The number of trials	50

In this experiment, we used two smart devices. One is for the victim and the other is for the rescuer. In this experiment setup, a victim is positioned at the left bottom corner of a 5 m × 5 m field and a rescuer walks around with a random walk model—a rescuer device moves at a random speed and in a random direction. A victim’s location is calculated relative to the rescuer during a rescuer’s random walk. Once a victim’s location is identified, this localization process is finished and considered as one trial. After one trial, we reset everything—a rescuer moved back to the original position—and calculate again victim’s position. We performed 50 trials for each of the proposed localization algorithm, multilateration method.

In each trial, a rescuer device broadcasts beacon signal with its location information periodically. When a victim device collects beacons, it calculates RSSI-based distance using the received beacon signals from a rescuer device. A rescuer’s location is also transmitted to a victim. With these collected distance and rescuer’s location information, a victim device localizes itself with either the proposed localization method or the multilaterlation algorithm.

Note that GPS of a rescuer device in disaster sites might not be available just like victim devices. So, we developed a location-measure feature for a rescuer-mode device. The location of a rescuer device is calculated using the accelerator and orientation sensor modules of Android phones. Specifically, we calculate the rescuer’s distance from its initial position by calibrating the outputs of the accelerator sensor in smart devices and associate such distance values with its orientation to compute its current location. Figure 12 shows the test results of this location-measure module we implemented in the rescuer-mode device. The x axis is the real distance and the y axis represents the measured distance. The average NF value observed in this test set is about 0.1–0.2. The next experiment results in Figures 13 and 14 show that such range of NF can be well filtered out by the proposed algorithm.

Figure 12.

Distance measure at a rescuer device.

Figure 13.

Localization error rate at each trial (no GPS on both rescuers and survivors).

Figure 14.

Localization error rate at each trial (no GPS on survivors and GPS available on rescuers).

Figures 13 and 14 compared accuracy of two localization methods—the proposed and multilateration—in our implementation. An x axis represents each trial and a y axis indicates location errors derived from the same equation (i.e. equation (8)) presented in NS-2 simulation section. As shown in the graphs, the proposed algorithm works better than multilateration in most cases excepts two trials (i.e. 16th and 42th trials in Figure 14). Specifically, the average error rates of the proposed method are 17.11% and 12.79% in Figures 13 and 14, respectively, while the average error rates of the multilateration method are 27.33% and 22.07% in Figures 13 and 14. Also, the maximum error rates are much further reduced from 41% to 23% and 30% to 21%.

Conclusion

The proposed RescueTalk is a mobile ad hoc network platform specifically developed to quickly and accurately search and rescue survivors in disasters. RescueTalk is built at an application-layer by exploiting underlying direct communications such as D2D for 5G and Wi-Fi Direct. The proposed method has several strengths over other related studies. First, it presents and implements a real-world platform for rescue operations by effectively utilizing direct communications between smart devices. It does not rely on infrastructure such as GPS, cellular, and Wi-Fi APs. Furthermore, the proposed platform is built at an application-layer over smart hand-held devices. This implies that the proposed protocol requires little modification of existing underlying protocols. With this platform, survivors are able to communicate with each other and even send help messages to an outside rescue center so that rescuers can easily locate and rescue survivors. Finally, we also developed the localization algorithm and a hybrid routing method, both of which are customized for satisfying requirements of disaster rescue operation: low overhead, high data delivery, quick localization, and low energy consumption. The simulation and real-world experiment results confirmed this fact that the proposed algorithms outperformed other studies in most cases.

Footnotes

Handling Editor: Paolo Barsocchi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was funded by the Ministry of Science and ICT (award number: NRF-2015R1C1A2A01055444), and the Ministry of Trade, Industry and Energy/Korea Evaluation Institute of Industrial Technology (award number: 10079767, Project Title: “Development of distress search system using drones and wireless signal detect”).

ORCID iD

Junghee Han

References

Han

. Exploiting ad-hoc networks over smart handheld devices for disaster rescue. Int J Urban Des Ubiquitous Comput 2017; 6(1): 39–45.

Trono

Fujimoto

Suwa

et al . Disaster area mapping using spatially-distributed computing nodes across a DTN. In: IEEE international conference on pervasive computing and communication workshops (Percom Workshops), Sydney, NSW, Australia, 14–18 March 2016, pp.1–6. New York: IEEE.

Lorincz

Malan

Fulford-Jones

et al . Sensor networks for emergency response: challenges and opportunities. IEEE Pervas Comput 2004; 3(4): 16–23.

Chenji

Zhang

Stoleru

et al . DistressNet: a disaster response system providing constant availability cloud-like services. Ad Hoc Netw 2013; 11(8): 2440–2460.

Sun

Zhu

Zhang

et al . RescueMe: location-based secure and dependable VANETs for disaster rescue. IEEE J Sel Area Comm 2011; 29(3): 659–669.

Hossain

Ray

Sinha

. A smartphone-assisted post-disaster victim localization method. In: IEEE 18th international conference on high performance computing and communications; IEEE 14th international conference on smart city; IEEE 2nd international conference on data science and systems (HPCC/SmartCity/DSS), Sydney, NSW, Australia, 12–14 December 2016, pp.1173–1179. New York: IEEE.

Wi-Fi Alliance. http://www.ieee802.org/11/; http://www.wi-fi.org/ko/discover-wi-fi/wi-fi-direct

3GPP. http://www.3gpp.org/release-13

Niculescu

Nath

. Ad hoc positioning system (APS). In: IEEE global telecommunications conference (GLOBECOM ’01), San Antonio, TX, 25–29 November 2001, vol. 5, pp.2926–2931. New York: IEEE.

10.

Horiba

Okamoto

Shinohara

et al . An accurate indoor-localization scheme with NLOS detection and elimination exploiting stochastic characteristics. IEICE T Commun 2015; E98-B(9): 1758–1767.

11.

Kim

Kwon

Lee

et al . Accurate indoor location tracking exploiting ultrasonic reflections. IEEE Sens J 2016; 24: 9075–9088.

12.

Mathias

Leonardi

Galati

. An efficient multilateration algorithm. In: Tyrrhenian international workshop on digital communications—enhanced surveillance of aircraft and vehicles (TIWDC/ESAV), Capri, 3–5 September 2008. New York: IEEE.

13.

Leonardi

Mathias

Galati

. Two efficient localization algorithms for multilateration. Int J Microw Wirel T 2009; 1(6): 223–229.

14.

Lazik

Rajagopal

Shih

et al . ALPS: a Bluetooth and ultra-sound platform for mapping and localization. In: Proceedings of the 13th ACM conference on embedded networked sensor systems, Seoul, Korea, 1–4 November 2015, pp.73–84. New York: ACM.

15.

Xiao

Wen

Markham

et al . Non-line-of-sight iden-tification and mitigation using received signal strength. IEEE T Wirel Commun 2015; 14(3): 1689–1702.

16.

Sichitiu

Ramadurai

. Localization of wireless sensor networks with a mobile beacon. In: IEEE international conference on mobile ad-hoc and sensor systems, Fort Lauderdale, FL, 25–27 October 2004, pp.174–183. New York: IEEE.

17.

Sun

Guo

. Comparison of distributed localization algorithms for sensor network with a mobile beacon. In: IEEE international conference on networking, sensing and control, Taipei, Taiwan, 21–23 March 2004, pp.536–540. New York: IEEE.

18.

Ssu

Jiau

. Localization with mobile anchor points in wireless sensor networks. IEEE T Veh Technol 2005; 54(3): 1187–1197.

19.

Feng

. A three dimensional localization algorithm using a mobile anchor node under wireless channel. In: IEEE international joint conference on neural networks, Hong Kong, China, 1–8 June 2008, pp.477–483. New York: IEEE.

20.

Open source project. Ad-hoc-on-android, https://code.google.com/p/adhoc-on-android

21.

Jang

Han

. On-time internal pedestrian localization algorithm based on infrastructure-free ad-hoc networks. J Korean Inst Commun Inf Sci 2014; 39(11): 1000–1008.

22.

Goldberg

. Genetic algorithms in search, optimization, and machine learning. Boston, MA: Addison-Wesley Longman Publishing, 1989.

23.

Peng

. An improved localization algorithm based on genetic algorithm in wireless sensor networks. Cogn Neurodyn 2015; 9(2): 249–256.

24.

Tantamjarik

Tanprasert

. Distance measurement with smartphone using acceleration model of hand movement. In: 8th international conference on knowledge and smart technology (KST), Chiangmai, Thailand, 3–6 February 2016. New York: IEEE.

25.

Abu-Mahfouz

Hancke

. NS-2 extension to simulate localization system in wireless sensor networks. In: AFRICON, Livingstone, Zambia, 13–15 September 2011, pp.1–7. New York: IEEE.

26.

Roeva

Fidanova

Paprzycki

et al . Influence of the population size on the genetic algorithm performance in case of cultivation process modeling. In: Federated conference on computer science and information systems, Kraków, 8–11 September 2013, pp.371–376. New York: IEEE.

27.

Zhang

Sakamoto

Furutani

. Effects of population size and mutation rate on results of genetic algorithm. In: Fourth international conference on natural computation (ICNC ‘08), Jinan, China, 18–20 October 2008. New York: IEEE.

28.

Alajmi

Wright

. Selecting the most efficient genetic algorithm sets in solving unconstrained building optimization problem. Int J Sust Built Environ 2014; 3(1): 18–26.