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

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.

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:

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.

OPEN IN VIEWER

Figure 2.

RescueTalk scenario.

OPEN IN VIEWER

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 , … , 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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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 ← 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 , … , 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 = ∑ j = 1 i ( 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 ± γ

(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:

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.

OPEN IN VIEWER

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 ( num i loc nu m i + ∑ nod e j ∈ neighbo r i num j loc nu m j )

(6)

Notations in the above equations are summarized in Table 1.

OPEN IN VIEWER

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.

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.

OPEN IN VIEWER

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 = 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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Figure 8.

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

OPEN IN VIEWER

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Figure 11.

Test scenario and screenshots of implemented devices.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Figure 12.

Distance measure at a rescuer device.

OPEN IN VIEWER

Figure 13.

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

OPEN IN VIEWER

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%.