# A Data Forwarding Approach for Fire-Rescue Scenario with Multi-Type Mobile Nodes

Authors: Linfeng Liu; Ping Zhou; Jiagao Wu; Ran Wang; Xiaojun Fan; Haiting Zhu
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

The opportunistic mobile sensor network has been extensively applied in various public safety applications such as the fire rescue and earthquake rescue, since it can provide a surveillance range with an inexpensive cost and avoid the dangers of humans staying in risk zones. However, due to some environmental events such as building structure damage, airflow push, and fire explosions, the sensor nodes sprinkled into the fire-rescue scenario may be kept moving. Thus, the contacts between nodes become momentary, and the data packets cannot be forwarded along stable communication paths. To this end, the opportunistic forwarding manner is adopted in the fire-rescue scenario to enable the data packets to be transferred to the rescue control center (RCC) through some discrete hops. The contributions of this paper are threefold. First, the nodes in the fire-rescue scenario are carefully investigated and classified into four types: small-range mobile nodes (SRNs), large-range mobile nodes (LRNs), firefighter nodes (FNs), and robot nodes (RNs). Second, we formulate the data forwarding problem, and the optimal proportions of SRNs, LRNs, and FNs in data holders are mathematically analyzed to obtain the maximum delivery ratio. Third, a data forwarding approach for fire-rescue scenario (DFAFR) is proposed. In DFAFR, the optimal proportions of SRNs, LRNs, and FNs in data holders are maintained as far as possible through selecting different types of data holder candidates, and then the new data holders are determined from these data holder candidates and the adjacent RNs on basis of their expected delivery delay. Finally, the performance of DFAFR is analyzed through simulations of the fire-rescue scenario, and the results indicate that DFAFR can enhance the delivery ratio and shorten the delivery delay while the forwarding overhead is restricted.


---

## Body

## 1. Introduction

With the broad deployment of mobile sensor nodes, opportunistic mobile sensor networks (OMSNs) [1, 2] are introduced to achieve large-scale sensing at a lower cost compared with a ubiquitous static infrastructure of sensing devices. However, due to the node mobility, the contacts between nodes may be scarce and momentary, leading to unstable communication paths. Opportunistic data forwarding approach enables a data packet to be transferred from the source to the destination through several discrete hops, even when such a stable path never emerges.The OMSN technology has been applied to various emergency-response applications, such as fire rescue [3, 4], earthquake rescue and mine accident rescue. In this paper, we focus on the fire-rescue scenario where the information containing the survival positions, area temperatures and fire explosions is capsuled into some data packets which need to be forwarded to the rescue control center (RCC) rapidly. As depicted in Figure 1, the fire behaviors are monitored by sensor nodes sprinkled by firefighters who move on for the rescue work, and this way of deploying nodes has been mentioned as a breadcrumb system in [5], where the breadcrumbs (sensor nodes) are deployed automatically on the fly when the firefighters run into the burning buildings. Then, the data packets containing the information of fire behaviors are forwarded to the RCC through intermittent multi-hop communications. The OMSN in fire-rescue scenario is composed of four types of nodes: (a) the small-range mobile nodes (SRNs) are located far from fire explosions, and they move slowly; (b) the large-range mobile nodes (LRNs) can bounce away from current positions due to the nearby combustion explosions or building structure damage [6], and thus their positions can be altered abruptly; (c) the firefighter nodes (FNs) are carried by firefighters who usually perform purposive movements, so that the FNs are considered to move regularly; (d) the robot nodes (RNs) traverse the fire area according to a predefined rule, such as the rule introduced in Section 3.1. Note that an SRN (or an LRN) can be transformed into an LRN (or an SRN) due to its surrounding fire behaviors; besides, SRNs, LRNs, FNs or RNs can be transformed into invalid nodes when they are destroyed in the fire-rescue scenario.Figure 1
An OMSN for fire-rescue scenario.The data forwarding technique in the fire-rescue scenario is defined as the art of mobile nodes disseminating the data packets to RCC through intermittent multi-hop links. Due to the intermittent contacts between nodes, the data delivery quality cannot be guaranteed even though the epidemic forwarding is adopted. Hence, how to enhance the delivery ratio in the fire-rescue scenario is a vital issue. Besides, a data packet delivered to RCC more rapidly is believed to provide more valuable references about the fire behaviors for further decisions, and thus how to shorten the delivery delay becomes another critical issue. To enhance the delivery ratio and shorten the delivery delay, a data forwarding approach for OMSN in the fire-rescue scenario is proposed and thoroughly evaluated in this paper. In our work, the mobility patterns of SRNs, LRNs, FNs and RNs are modeled, and the optimal proportions of SRNs, LRNs and FNs in data holders are analyzed to maximize the delivery ratio. Furthermore, the new data holders are selected from the data holder candidates and the adjacent RNs to shorten the delivery delay.The remainder of this paper is organized as follows: Section2 briefly surveys some existing related studies. Section 3 proposes a network model to describe the opportunistic data forwarding problem, and then the delivery delay and delivery delay are analyzed. Section 4 presents an opportunistic data forwarding approach for the fire-rescue scenario (DFAFR). Simulation results for performance evaluation of DFAFR are reported in Section 5. Finally, Section 6 concludes the paper.This work is a significant extension of our early work [7]. Specifically, we introduce the RNs into the network model, and the new data holders will be determined from the data holder candidates and the adjacent RNs according to their expected delivery delay. The external forces in combustion process are analyzed to derive the mobility patterns of SRNs and LRNs, which are closer to the real fire-rescue scenario. Besides, more simulation results are also provided to further clarify the merits of the proposed DFAFR.


## 2. Related Work

Recently, the opportunistic data forwarding problem in mobile sensor networks has attracted a lot of interest. In the early representative work, Direct Transmission (DT) [8], each data packet is forwarded until the data holder encounters the destination node, and thus the data packet will not be copied, and this mechanism leads to a very low delivery ratio. It is obvious that DT is with the minimum expense, despite an unsatisfactory delivery ratio and a very long delivery delay. On the contrary, in Epidemic Forwarding (EF) [9], each node forwards the held data packets to all the encountered nodes. EF can achieve a large delivery ratio and a short delivery delay, but it usually produces massive data packet copies and causes the network congestion easily. In [10], based on the calculated forwarding probabilities, the Probabilistic Routing Protocol using History of Encounters and Transitivity (PROPHET) provides a mobility prediction of nodes to help the data dissemination. The performance of PROPHET relies on the movement regularity of nodes.With regard to the mobility patterns, there are some typical mobility models, as the Brown model, random waypoint model, random walk model, random direction model, reference point group mobility and so on [11–13]. Besides, some mobility models have been proposed for the disaster scenarios. In [14], Joe et al. assume that an earthquake has occurred in a city where some roads and nodes have been damaged. A Message Priority Routing Protocol (MPRP) is proposed to remedy the performance degradation caused by these damage, and MPRP is able to deliver more messages to the destination in the earthquake-scenario. Reference [15] is based on the Post Disaster Mobility model (PDM), which captures the mobility features of humans or vehicles in disaster rescue scenarios. In PDM, vehicles carrying supplies may move between the coordination centers and evacuation camps. A number of rescue workers and volunteers are dedicated to locate survivors and offer help. Reference [15] also raises an inter-contact routing method where the delivery delay and delivery ratio can be estimated. Likewise, Aschenbruck etal. propose a disaster area mobility model in [16], where the characteristics of public safety communication networks such as heterogeneous area-based movement, obstacles and joining/leaving of nodes are provided. In [17], a health care Small-World Network (SWN) evolves naturally from social interactions and population dynamics. However, during a crisis, the SWN is constrained by interrupted transportation within the limited geographic topology. Reference [18] proposes an opportunistic data transmission mechanism based on a susceptible-infected model, and this model is used to analyze the social characteristics of mobile crowd sensing networks and obtain the table of evolutionary relationships between nodes. The evolutionary relationships are quantified and added to the opportunistic routing as additional information, to guide the nodes to reach the destination successfully. Combining random waypoint and random direction model, [19] presents a novel earthquake relief mobility model through analyzing the demand characteristics of earthquake relief within a prime time. In [20], a learning automata-based multi-level heterogeneous routing is designed for energy conservation. [21] presents an SDN-based scheme to make intelligent decisions for data offloading, and it is verified that the traffic routing is managed efficiently even with an increase in the network size.Tabirca et al. construct a dynamic model for the fire emergency evacuation problem, and the model redefines the concept of safety [22]. To establish emergency communication networks for fire-fighting in underground buildings, a reliable fire emergency communication network is designed to realize the QoS communications and guarantee the stability of communication performance [23]. Besides, a fire emergency and gas detection system based on WSNs for both indoor and outdoor environments is given in [24], where the modules of sensing duties, network-node interactions, and system resiliency are integrated into this system. In [25], a localization and tracking system based on the usage of IEEE 802.11 technology is provided for augmenting the GPS coverage in emergency scenarios. Likewise, [26] proposes a localization and tracking system based on the combined usage of WiFi and GPS for emergency scenarios, and this system is characterized by ease of deployment and usage, since it does not require any particular configurations.In the fire-rescue scenario, the fire behaviors can be monitored by some sensor nodes and then encapsulated into some data packets, which are then transmitted to RCC through intermittent multi-hops. However, the typical mobility patterns of nodes in fire-rescue scenario have not been investigated and concluded in existing works, and the mobility patterns of nodes should be considered in the selection of data holders. In this paper, the typical mobility patterns in fire-rescue scenario will be concluded according to the movement features of nodes, and then a data forwarding approach is designed for the fire-rescue scenario with multi-type mobile nodes.


## 3. Analysis Framework

Suppose thatN mobile nodes are uniformly deployed in a fire area A (A∈R2). The time is divided into discrete time slots with an equal length τ. Each node (except the invalid nodes) is assumed to be equipped with a GPS equipment, and thus it can obtain the real-time coordinate. The objective of data forwarding problem is to enhance the delivery ratio and shorten the delivery delay while the forwarding overhead is restricted. Note that the energy consumption is confined as well by restricting the number of forwarded copies (forwarding overhead), because the energy consumption is mainly produced by the data dissemination. The explanations of the main notations are presented in Table 1.Table 1
Description of main notations.
Parameter Description Rc Communication range of each node ρs Proportion of SRNs in data holders ρl Proportion of LRNs in data holders ρf Proportion of FNs in data holders vs Movement speed of SRNs vf Movement speed of FNs vr Movement speed of RNs ts Residence period of an SRN at each time slot tl Residence period of an LRN after each bounce tf Residence period of an FN at each time slot re Explosion range rl Maximum bounce range Ls Size of each data packet T Forwarding deadline of each data packet κ Number of forwarded copies at each time slot C(i)t Coordinate ofVi at the t-th time slot dp(i,j)t Position alteration betweenVi and Vj at the t-th time slot Sp(i)t Position stability ofVi at the t-th time slot Dst Delivery ratio with SRNs at thet-th time slot Dlt Delivery ratio with LRNs at thet-th time slot Dft Delivery ratio with FNs at thet-th time slot Dt Delivery ratio with SRNs, LRNs and FNs at thet-th time slot


### 3.1. Mobility Patterns of Nodes

In the fire-rescue scenario, suppose some solid combustibles are ignited and then are converted into naked fire after a smoldering phase. At the beginning of the combustion process, the fire volume is very small, and both the burning speed and heat release rate are gradually increased. In the combustion process, fire plumes and ceiling jets [27] are produced, as depicted in Figure 2.Figure 2
Fire plumes and ceiling jets.
(a)
Combustion process (b)
Fire plumes and ceiling jetsDue to the external forces, the mobility patterns of nodes are given as follows:(i)
Mobility Pattern of SRNs. In the smoldering phase, under the external forces of fire plumes, ceiling jets, gravity and Coriolis force [28], as shown in Figure 3, SRNs will move slowly on the ground because the gravity of nodes is usually large enough. Thus, each SRN is assumed to move at a speed of vs which falls into the interval (vmin,vmax), and each SRN resides for a short period of ts at each time slot, as illustrated in Figure 5(a).(ii)
Mobility Pattern of LRNs. In the explosion phase, each node falling in the explosion range re of a fire behavior becomes an LRN. Each LRN bounces along the push force direction, and the bounce distance should be smaller than the maximum bounce range rl (as shown in Figure 4). The bounce of each LRN is repeated after a residence period of tl, unless it is beyond the explosion range. Specially, if an LRN reaches the boundary of A, it bounces off the border with the reflecting direction, as shown in Figure 5(b).(iii)
Mobility Pattern of FNs. FNs are assumed to move at a constant speed of vf. At each time slot, each FN will reside for a period of tf to detect the nearby fire behaviors. FNs first move to rescue the survivals and then move to extinguish the fire [29]. An example of the FN movements is given in Figure 5(c).(iv)
Mobility Pattern of RNs. RNs are deployed to help forward the data packets. Each RN is set to move at a constant speed of Rc/τ. The fire area is divided into some hexagonal cells, as illustrated in Figure 5(d), which indicates that an RN always moves to the adjacent cell with the minimum number of neighbouring untraversed cells. When all of the neighbouring cells are obstacle cells, the RN returns to the last traversed cell to find a neighbouring untraversed cell.Figure 3
External forces in smoldering phase.Figure 4
Push forces in explosion phase.Figure 5
Mobility patterns of SRNs, LRNs, FNs, and RNs.
(a)
SRNs (b)
LRNs (c)
FNs (d)
RNs


### 3.2. Position Stability

We give the notion of position stability to measure the position alterations of nodes over time, and the value of position stability can be used to distinguish the types of SRNs and LRNs. The position stability of each node is determined by calculating the position alterations between it and its neighbours; i.e., the position stability of a node becomes smaller when more of its neighbours are changed over time.The coordinate ofVi at the t-th time slot is expressed as C(i)t=xit,yit, and the set of neighbours is denoted by Nit. Hence, the Euclidean distance between Vi and a neighbour Vj(Vj∈Nit) at the t-th time slot is calculated as d(i,j)t=(xit-xjt)2+(yit-yjt)2. The position alteration between Vi and Vj at the t-th time slot is defined as(1)dpi,jt=ζ,ifVj∈Nit-1andVj∉Nit,xit-xjt-xit-1-xjt-12+yit-yjt-yit-1-yjt-12,otherwise,where ζ is a large constant. Formula (1) indicates that when Vi and Vj are neighbours during two consecutive time slots (at the (t-1)-th time slot and the t-th time slot) the position alteration is calculated as the distance variation between them.The position stability ofVi at the t-th time slot is denoted by Sp(i)t(2)Spit=1-2π·arctan⁡∑Vj∈Nit-1dpi,jt-d~pit2Nit-1,where Nit-1 denotes the number of neighbours of Vi at the (t-1)-th time slot, and d~p(i)t denotes the minimum position alteration between Vi and its neighbours at the t-th time slot. Note that the value of arctan⁡∑Vj∈Nit-1dp(i,j)t-d~p(i)t2/Nit-1 falls into the interval [0,π/2), and hence Sp(i)t∈(0,1]. Formula (2) implies that a larger position stability of Vi will be obtained if the position alterations between Vi and its neighbours are smaller.Besides, we have that(3)d~pit=minVj∈Nitdpi,jt.


### 3.3. Proportions of SRNs, LRNs, and FNs in Data Holders

Due to the expensive cost, the number of RNs is extremely small compared with other types of nodes, and we will analyze the optimal proportions of SRNs, LRNs and FNs in data holders in this section.At each time slot, each data holder forwards the held data packets toκ neighbours, and thus the number of data holders at the t-th time slot is (κ+1)t-1. To obtain the optimal proportions, the delivery ratio is discussed in four cases: we first analyze the delivery ratio when the data holders are SRNs, LRNs or FNs, respectively, and then the delivery ratio when the data holders are composed of three types of nodes is obtained through combining the conclusions of the aforementioned cases. Note that other cases can also be obtained similarly. The four cases are given asCase I. ρs=1, ρf=0 and ρl=0, i. e., all data holders are the SRNs. The delivery ratio at the t-th time slot is expressed as(4)Dst=Prs+∑k=2tκ+1k-1·Prs·∏i=1k-11-κ+1i-1·Prs,where Prs denotes the probability of an SRN encountering the RCC. In (4), (κ+1)k-1 is the number of data holders at the k-th time slot. Thus, (κ+1)k-1·Prs denotes the probability of the data packet being delivered through SRNs at the k-th time slot, and ∏i=1k-11-(κ+1)i-1·Prs denotes the probability of the data packet not being delivered through SRNs during the previous (k-1) time slots. As illustrated in Figure 6(a), each SRN moves at the speed of vs and resides for a period of ts at each time slot, and thus Prs=2Rc·(τ-ts)·vs/|A|.Figure 6
Communication coverage.
(a)
SRNs (b)
LRNs (c)
FNsCase II. ρl=1, ρf=0 and ρs=0, i. e., all data holders are the LRNs. Likewise, there is(5)Dlt=Prl+∑k=2tκ+1k-1·Prl·∏i=1k-11-κ+1i-1·Prl,where Prl denotes the probability of an LRN encountering the RCC, and Prl=τ/tl·π·Rc2/|A|, as shown in Figure 6(b). In (5), (κ+1)k-1·Prl denotes the probability of the data packet being delivered through LRNs at the k-th time slot, and ∏i=1k-11-(κ+1)i-1·Prl denotes the probability of the data packet not being delivered through LRNs during the previous (k-1) time slots.Case III. ρf=1, ρs=0 and ρl=0, i. e., all data holders are the FNs which move at a constant speed of vf. We have(6)Dft=Prf+∑k=2tκ+1k-1·Prf·∏i=1k-11-κ+1i-1·Prf,where Prf denotes the probability of an FN encountering the RCC, and Prf=2Rc·(τ-tf)·vf/|A|, as illustrated in Figure 6(c).Case IV. ρs>0, ρl>0, ρf>0 and ρs+ρl+ρf=1. The three types of nodes exist in the data holders simultaneously, and the delivery ratio Dt can be expressed as(7)Dt=ρs·Dst⋃ρl·Dlt⋃ρf·Dft=ρs·Dst+ρl·Dlt+ρf·Dft-ρs·ρl·Dst·Dlt-ρs·ρf·Dst·Dft-ρl·ρf·Dlt·Dft+ρs·ρl·ρf·Dst·Dlt·Dft,where ρs·Dst, ρl·Dlt and ρf·Dft denote the probabilities of the data packet being delivered at the t-th time slot through SRNs, LRNs and FNs, respectively.The forwarding deadline is⌊T/τ⌋, and the expression of delivery ratio before the forwarding deadline is derived by (4), (5), (6) and (7):(8)DT/τ≈∑i=1T/τκ+1i-1·ρs·Prs+ρl·Prl+ρf·Prf-∑i=1T/τκ+1i-12·ρs·ρl·Prs·Prl+ρs·ρf·Prs·Prf+ρl·ρf·Prl·Prf+∑i=1T/τκ+1i-13·ρs·ρl·ρf·Prs·Prl·Prf.The optimal solutions ofρs, ρl and ρf are denoted by ρ¯s, ρ¯l and ρ¯f, respectively. ρ¯s, ρ¯l and ρ¯f can be obtained by maximizing DT/τ, and the obtained solutions will be used in DFAFR to maintain the optimal proportions of SRNs, LRNs and FNs in data holders approximatively.


### 3.4. Expected Delivery Delay

With regard to SRNs, the probability of data packets being delivered at thet-th time slot is expressed as (κ+1)t-1·Prs, and thus the expected delivery delay is expressed as(9)τ·∑k=1T/τk·κ+1k-1·Prs·∏i=1k-11-κ+1i-1·Prs,where the part of ∏i=1k-11-(κ+1)i-1·Prs denotes the probability of data packets not being delivered during (t-1) time slots. Likewise, the expected delivery delay of LRNs and FNs is written as (10)τ·∑k=1T/τk·κ+1k-1·Prl·∏i=1k-11-κ+1i-1·Prl,(11)τ·∑k=1T/τk·κ+1k-1·Prf·∏i=1k-11-κ+1i-1·Prf.The area of each cell is33/2Rc2. For each RN, the expected delivery delay is expressed as(12)A33/2Rc2-ntr-nob·τ,where ntr and nob denote the number of traversed cells and the number of obstacle cells, respectively.The expected delivery delay will be applied to determine the new data holders in DFAFR.


## 3.1. Mobility Patterns of Nodes

In the fire-rescue scenario, suppose some solid combustibles are ignited and then are converted into naked fire after a smoldering phase. At the beginning of the combustion process, the fire volume is very small, and both the burning speed and heat release rate are gradually increased. In the combustion process, fire plumes and ceiling jets [27] are produced, as depicted in Figure 2.Figure 2
Fire plumes and ceiling jets.
(a)
Combustion process (b)
Fire plumes and ceiling jetsDue to the external forces, the mobility patterns of nodes are given as follows:(i)
Mobility Pattern of SRNs. In the smoldering phase, under the external forces of fire plumes, ceiling jets, gravity and Coriolis force [28], as shown in Figure 3, SRNs will move slowly on the ground because the gravity of nodes is usually large enough. Thus, each SRN is assumed to move at a speed of vs which falls into the interval (vmin,vmax), and each SRN resides for a short period of ts at each time slot, as illustrated in Figure 5(a).(ii)
Mobility Pattern of LRNs. In the explosion phase, each node falling in the explosion range re of a fire behavior becomes an LRN. Each LRN bounces along the push force direction, and the bounce distance should be smaller than the maximum bounce range rl (as shown in Figure 4). The bounce of each LRN is repeated after a residence period of tl, unless it is beyond the explosion range. Specially, if an LRN reaches the boundary of A, it bounces off the border with the reflecting direction, as shown in Figure 5(b).(iii)
Mobility Pattern of FNs. FNs are assumed to move at a constant speed of vf. At each time slot, each FN will reside for a period of tf to detect the nearby fire behaviors. FNs first move to rescue the survivals and then move to extinguish the fire [29]. An example of the FN movements is given in Figure 5(c).(iv)
Mobility Pattern of RNs. RNs are deployed to help forward the data packets. Each RN is set to move at a constant speed of Rc/τ. The fire area is divided into some hexagonal cells, as illustrated in Figure 5(d), which indicates that an RN always moves to the adjacent cell with the minimum number of neighbouring untraversed cells. When all of the neighbouring cells are obstacle cells, the RN returns to the last traversed cell to find a neighbouring untraversed cell.Figure 3
External forces in smoldering phase.Figure 4
Push forces in explosion phase.Figure 5
Mobility patterns of SRNs, LRNs, FNs, and RNs.
(a)
SRNs (b)
LRNs (c)
FNs (d)
RNs


## 3.2. Position Stability

We give the notion of position stability to measure the position alterations of nodes over time, and the value of position stability can be used to distinguish the types of SRNs and LRNs. The position stability of each node is determined by calculating the position alterations between it and its neighbours; i.e., the position stability of a node becomes smaller when more of its neighbours are changed over time.The coordinate ofVi at the t-th time slot is expressed as C(i)t=xit,yit, and the set of neighbours is denoted by Nit. Hence, the Euclidean distance between Vi and a neighbour Vj(Vj∈Nit) at the t-th time slot is calculated as d(i,j)t=(xit-xjt)2+(yit-yjt)2. The position alteration between Vi and Vj at the t-th time slot is defined as(1)dpi,jt=ζ,ifVj∈Nit-1andVj∉Nit,xit-xjt-xit-1-xjt-12+yit-yjt-yit-1-yjt-12,otherwise,where ζ is a large constant. Formula (1) indicates that when Vi and Vj are neighbours during two consecutive time slots (at the (t-1)-th time slot and the t-th time slot) the position alteration is calculated as the distance variation between them.The position stability ofVi at the t-th time slot is denoted by Sp(i)t(2)Spit=1-2π·arctan⁡∑Vj∈Nit-1dpi,jt-d~pit2Nit-1,where Nit-1 denotes the number of neighbours of Vi at the (t-1)-th time slot, and d~p(i)t denotes the minimum position alteration between Vi and its neighbours at the t-th time slot. Note that the value of arctan⁡∑Vj∈Nit-1dp(i,j)t-d~p(i)t2/Nit-1 falls into the interval [0,π/2), and hence Sp(i)t∈(0,1]. Formula (2) implies that a larger position stability of Vi will be obtained if the position alterations between Vi and its neighbours are smaller.Besides, we have that(3)d~pit=minVj∈Nitdpi,jt.


## 3.3. Proportions of SRNs, LRNs, and FNs in Data Holders

Due to the expensive cost, the number of RNs is extremely small compared with other types of nodes, and we will analyze the optimal proportions of SRNs, LRNs and FNs in data holders in this section.At each time slot, each data holder forwards the held data packets toκ neighbours, and thus the number of data holders at the t-th time slot is (κ+1)t-1. To obtain the optimal proportions, the delivery ratio is discussed in four cases: we first analyze the delivery ratio when the data holders are SRNs, LRNs or FNs, respectively, and then the delivery ratio when the data holders are composed of three types of nodes is obtained through combining the conclusions of the aforementioned cases. Note that other cases can also be obtained similarly. The four cases are given asCase I. ρs=1, ρf=0 and ρl=0, i. e., all data holders are the SRNs. The delivery ratio at the t-th time slot is expressed as(4)Dst=Prs+∑k=2tκ+1k-1·Prs·∏i=1k-11-κ+1i-1·Prs,where Prs denotes the probability of an SRN encountering the RCC. In (4), (κ+1)k-1 is the number of data holders at the k-th time slot. Thus, (κ+1)k-1·Prs denotes the probability of the data packet being delivered through SRNs at the k-th time slot, and ∏i=1k-11-(κ+1)i-1·Prs denotes the probability of the data packet not being delivered through SRNs during the previous (k-1) time slots. As illustrated in Figure 6(a), each SRN moves at the speed of vs and resides for a period of ts at each time slot, and thus Prs=2Rc·(τ-ts)·vs/|A|.Figure 6
Communication coverage.
(a)
SRNs (b)
LRNs (c)
FNsCase II. ρl=1, ρf=0 and ρs=0, i. e., all data holders are the LRNs. Likewise, there is(5)Dlt=Prl+∑k=2tκ+1k-1·Prl·∏i=1k-11-κ+1i-1·Prl,where Prl denotes the probability of an LRN encountering the RCC, and Prl=τ/tl·π·Rc2/|A|, as shown in Figure 6(b). In (5), (κ+1)k-1·Prl denotes the probability of the data packet being delivered through LRNs at the k-th time slot, and ∏i=1k-11-(κ+1)i-1·Prl denotes the probability of the data packet not being delivered through LRNs during the previous (k-1) time slots.Case III. ρf=1, ρs=0 and ρl=0, i. e., all data holders are the FNs which move at a constant speed of vf. We have(6)Dft=Prf+∑k=2tκ+1k-1·Prf·∏i=1k-11-κ+1i-1·Prf,where Prf denotes the probability of an FN encountering the RCC, and Prf=2Rc·(τ-tf)·vf/|A|, as illustrated in Figure 6(c).Case IV. ρs>0, ρl>0, ρf>0 and ρs+ρl+ρf=1. The three types of nodes exist in the data holders simultaneously, and the delivery ratio Dt can be expressed as(7)Dt=ρs·Dst⋃ρl·Dlt⋃ρf·Dft=ρs·Dst+ρl·Dlt+ρf·Dft-ρs·ρl·Dst·Dlt-ρs·ρf·Dst·Dft-ρl·ρf·Dlt·Dft+ρs·ρl·ρf·Dst·Dlt·Dft,where ρs·Dst, ρl·Dlt and ρf·Dft denote the probabilities of the data packet being delivered at the t-th time slot through SRNs, LRNs and FNs, respectively.The forwarding deadline is⌊T/τ⌋, and the expression of delivery ratio before the forwarding deadline is derived by (4), (5), (6) and (7):(8)DT/τ≈∑i=1T/τκ+1i-1·ρs·Prs+ρl·Prl+ρf·Prf-∑i=1T/τκ+1i-12·ρs·ρl·Prs·Prl+ρs·ρf·Prs·Prf+ρl·ρf·Prl·Prf+∑i=1T/τκ+1i-13·ρs·ρl·ρf·Prs·Prl·Prf.The optimal solutions ofρs, ρl and ρf are denoted by ρ¯s, ρ¯l and ρ¯f, respectively. ρ¯s, ρ¯l and ρ¯f can be obtained by maximizing DT/τ, and the obtained solutions will be used in DFAFR to maintain the optimal proportions of SRNs, LRNs and FNs in data holders approximatively.


## 3.4. Expected Delivery Delay

With regard to SRNs, the probability of data packets being delivered at thet-th time slot is expressed as (κ+1)t-1·Prs, and thus the expected delivery delay is expressed as(9)τ·∑k=1T/τk·κ+1k-1·Prs·∏i=1k-11-κ+1i-1·Prs,where the part of ∏i=1k-11-(κ+1)i-1·Prs denotes the probability of data packets not being delivered during (t-1) time slots. Likewise, the expected delivery delay of LRNs and FNs is written as (10)τ·∑k=1T/τk·κ+1k-1·Prl·∏i=1k-11-κ+1i-1·Prl,(11)τ·∑k=1T/τk·κ+1k-1·Prf·∏i=1k-11-κ+1i-1·Prf.The area of each cell is33/2Rc2. For each RN, the expected delivery delay is expressed as(12)A33/2Rc2-ntr-nob·τ,where ntr and nob denote the number of traversed cells and the number of obstacle cells, respectively.The expected delivery delay will be applied to determine the new data holders in DFAFR.


## 4. Opportunistic Data Forwarding Approach

The typical mobility patterns of nodes are considered in the design of data forwarding approach. In the opportunistic Data Forwarding Approach of Fire-Rescue scenario (DFAFR), each data holder independently forwards the held data packets to the nodes which are selected from the data holder candidates and the adjacent RNs, and the data holder candidates are determined through maintaining the optimal proportions of SRNs, LRNs and FNs in data holders. Note that the optimal proportions are related to the mobility patterns of nodes. Besides, each node probably alters its mobility pattern during the data forwarding process; e.g., an SRN (or an LRN) is probably transformed into an LRN (or SRN) due to the external forces, which is considered in DFAFR as well.The storage capacities of nodes are usually insufficient, because the capacity of nodal storage modules is extremely limited (the space memory is even measured in KB [30]), and thus some held data packets must be discarded to make room for the arrivals of new data packets. A data packet data(s,d) is assumed to be forwarded from the source node Vs to the destination Vd (RCC), and the detailed description of DFAFR is given as follows:Step 1.
ρ ¯ s, ρ¯l and ρ¯f are obtained from formula (8).Step 2.
At thet-th time slot, each data holder Vi broadcasts an inquire_msg containing a quintet (ID,t,C(i)t,type,data_list(i)t), where type and data_list(i)t denote the node type and the list of held data packets, respectively.Step 3.
After the reception ofinquire_msg from Vi, each neighbour Vj replies a reply_msg which contains the similar information with inquire_msg. If Vd has received the inquire_msg from Vi, and then Vi sends data(s,d) to Vd immediately.Step 4.
The position stability of each node (excluding the FNs and RNs) is locally computed. Then, each nodeVk is classified into an SRN or an LRN according to a stability threshold ξ: if Sp(k)t≥ξ, and then Vk is an SRN; otherwise, Vk is an LRN. If the new type of Vk is different from that in the quintet of inquire_msg, and then a type_msg is sent to the neighbours for the type updates.Step 5.
The new data holders will be selected by the following two sub-steps:(i)
Step 5-1. Each data holderVi selects κ data holder candidates from its neighbours on the basis of ρ¯s, ρ¯l and ρ¯f which are obtained from (8) in Step 1.(ii)
Step 5-2.κ new data holders are selected from the data holder candidates and the adjacent RNs according to the expected delivery delay calculated by (9), (10), (11) and (12), i.e., the neighbours with shorter expected delivery delay are selected as the new data holders. Note that all of the κ data holder candidates will become the new data holders if there are no RNs around Vi.
After that,Vi sends data(s,d) to the selected new data holders.Step 6.
If a new data holderVj receives the data(s,d) from Vi, and then Vj updates the list of held data packets as(13)data_listjt+1←data_listjt⋃datas,d.
Specially, if the storage capacity ofVj has been full, the earliest held data packet is discarded to make room for the arrival of data(s,d).Step 7.
Steps2–6 are repeated until Vd receives data(s,d) or the deadline has been expired. If data(s,d) has been delivered to Vd before the deadline, and then an announcement message originated from Vd will be propagated to all the data holders of data(s,d) to stop their further forwardings and discard all data(s,d) copies. The size of announcement message is very small and can be piggybacked with other messages, and thus the effect of broadcast is negligible. A demonstration of DFAFR execution is given in Figure 7.Figure 7
Message exchanges between neighbours.The exchanged messages of DFAFR are mainly yielded in Steps2, 3, 4, and 6. In Step 2, each node broadcasts an inquire_msg, and therefore the total message amount will reach N in the worst case; in Steps 3 and 4, there are N2·π·Rc2/|A|  reply_msgs and type_msgs to be transmitted, respectively; Step 5 makes each data holder forward κ copies of data(s,d), and thus there are utmost κ·(κ+1)T/τ-1 copies of data(s,d); As a result, the message complexity of DFAFR is at most O(N2). Table 2 shows the message complexity of each step in DFAFR.Table 2
Message complexity of each step.
Step Complexity 1 O ( 1 ) 2 O(N) 3 O ( N 2 ) 4 O(N2) 5 O ( 1 ) 6 O(1)) 7 O ( 1 )


## 5. Simulation Evaluation

In this section, DFAFR is evaluated by observing the performance variations with respect to different parameters and by comparing with other algorithms (DT, EF, PROPHET and MPRP). DFAFR is realized in ONE (Opportunistic Networks Environment) [31], which is a simulation environment that can generate the node mobility using different movement models and forward the data packets between nodes with various routing algorithms. The delay for each forwarding is computed as Ls/B+Rc/ς [32], where B is the channel capacity (in bits per second), and ς is the propagation speed of electromagnetic wave.The deadline is set according to the statistical data provided in an USFA’s report “Structure Fire Response Times”, which claims that51% of structure fires confined to room of origin and floor of origin had response times of less than 5 minutes, while 54% of fires confined to building and 49% beyond building had response times of less than 6 minutes. The deadline of data packet delivery should be shorter than the response time, and we set it to 120 seconds (2 minutes). Besides, the capacity of nodal storage modules is extremely limited (the space memory is even measured in KB or MB [30], e.g., the chip CC2430 has a flash memory of 128 KB [33]), and we set S=30,000 KB in the following simulations.


### 5.1. Environment Settings

The fire-rescue area is with the size of 35m×65m. At the beginning, N nodes (including 15 FNs and 3 RNs) are evenly deployed into the fire-rescue area. Every time slot, 3 explosion locations are randomly selected from all of the fire locations, and the nodes falling into the explosion ranges become LRNs. Each node generates a new data packet with a probability pg to report the nearby fire behaviors, and these data packets should be forwarded to RCC. The storage capacity of SRNs, LRNs, FNs and RNs is set to 5MB, 5MB, 50MB and 50MB, respectively. The values of other parameters are given in Table 3.Table 3
Simulation Parameters.
Parameter Description Value N Number of nodes 100 T Deadline 120 s pg Probability of a node generating a data packet at each time slot 0.5 Rc Communication range of each node 8 m τ Length of each time slot 20 s Ls Size of each data packet 500 KB S Storage of each node 30,000 KB κ Number of forwarded copies at each time slot 2 (vmin,vmax) Speed interval of SRNs (0.1,1.5) m/s ts Residence period of SRNs at each time slot 3 s tl Residence period of LRNs after each bounce 10 s tf Residence period of FNs at each time slot 5 s vf Movement speed of FNs 2.0 m/s re Explosion range 9 m rl Maximum bounce range 12 m ξ Stability threshold 0.4 ζ Constant in formula (1) 65 ς Propagation speed of electromagnetic wave 300,000 km/s B Channel capacity 8 kbps


### 5.2. Impacts of Time Slot Length and Data Packet Size

The results regarding the impacts ofτ on the total number of data packet copies and the delivery ratio are given in Figure 8. Each node generates a new data packet with the probability pg at the interval of τ, and thus a smaller τ leads to a larger number of data packets, which makes the network be saturated more easily and depresses the delivery ratio more severely.Figure 8
Impacts of time slot lengthτ.
(a)
Total Number of Data Packet Copies (b)
Delivery RatioFigure9 illustrates the impacts of data packet size on the delivery ratio, forwarding overhead (Forwarding overhead is defined as the average number of forwarded copies for each delivered data packet, and the index of forwarding overhead can measure the expense of the data packet deliveries.) and delivery delay. Figure 9(a) shows that a larger delivery ratio can be achieved with a smaller data packet size, which is attributed to the fact that more data packets can be propagated and held by nodes when the data packets are with smaller size. Besides, the curve of delivery ratio rises with the increase of N, regardless of the data packet size. This is because more receivers are available when the nodes are deployed more densely, and thus better data holders can be selected to enhance the delivery ratio. In Figure 9(b), the bars of forwarding overhead fluctuate very slightly with the increase of N, which indicates that DFAFR has a good scalability with respect to the forwarding overhead. In Figure 9(c), the curve with a smaller data packet size is much lower than others, and the delivery delay gradually decreases with the increase of N. The reason is that better intermittent paths can be found to shorten the delivery delay when the nodes are deployed more densely.Figure 9
Impacts of data packet size.
(a)
Delivery Ratio (b)
Forwarding Overhead (c)
Delivery Delay


### 5.3. Proportions of SRNs, LRNs and FNs in Data Holders

As described in Section4, DFAFR strives for maintaining the optimal proportions of SRNs, LRNs and FNs in data holders to enhance the delivery ratio. To verify the effect of this mechanism, some simulation results are given in Figure 10. Figure 10(a) shows the optimal solutions ρ¯s, ρ¯l and ρ¯f which are calculated by formula (8). Then, we can observe that DFAFR outperforms the results of other proportions (such as 8:1:1, 7:2:1 and 6:3:1, which are given in the form of ρs:ρl:ρf) in terms of the number of data packet copies, as shown in Figure 10(b). This is because the optimal proportions can increase the delivery ratio effectively, and thus the number of data packet copies is reduced simultaneously. Moreover, the total number of data packet copies increases with the increase of N, since more nodes generate more data packets. Accordingly, Figure 10(c) shows that DFAFR achieves the largest delivery ratio through adopting the optimal proportions, and this phenomenon tallies with the aforementioned analysis in Section 3.Figure 10
Impacts of the proportions of SRNs, LRNs and FNs in data holders.
(a)
Optimal Proportions (b)
Total Number of Data Packet Copies (c)
Delivery Ratio


### 5.4. Comparisons with Other Algorithms

This simulation compares the delivery ratio, forwarding overhead, delivery delay and network throughput (Network throughput is defined as the total number of data messages received per unit time by the destinations of all the multi-hop flows in the network) among DFAFR, DT, EF, PROPHET and MPRP, and the results are given in Figure11.Figure 11
Algorithm comparisons.
(a)
Delivery Ratio (b)
Forwarding Overhead (c)
Delivery Delay (d)
Network ThroughputSome observations are provided as follows: (a) DT achieves the smallest delivery ratio and the largest delivery delay because the source holds the data packets until it encounters the destination node, although the forwarding overhead of DT is much lower than other algorithms. (b) The forwarding overhead of EF is significantly larger than those of other algorithms due to its flooding mechanism. (c) The delivery ratio, delivery delay and network throughput of DFAFR are better than those of other algorithms. The reason is that DFAFR selects the appropriate data holders to enhance the delivery ratio and shorten the delivery delay, and some held data packets are allowed to be discarded by nodes to make room for new data packets. Especially note that the flooding mechanism in EF will make the storage of nodes be rapidly occupied, and many held data packets have to be casually discarded by nodes, thereby decreasing the delivery ratio and prolonging the delivery delay. (d) The forwarding overhead of DFAFR is lower than those of EF, PROPHET and MPRP, and the gaps become large with the increase ofN, as illustrated in Figure 11(b).The above results indicate that DFAFR outperforms other algorithms in terms of delivery ratio, delivery delay and network throughput with a low forwarding overhead. In summary, we give Table4 to show the differences of DFAFR, DT, EF, PROPHET and MPRP visually.Table 4
Comparisons of DFAFR, DT, EF, PROPHET and MPRP.
Algorithm Forwarding manner Mobility patterns Delivery ratio Delivery delay Forwarding overhead Scenario DFAFR opportunistic forwarding multiple types large short low fire-rescue scenario DT direct transmission single type small extremely long low delay-insensitive scenario EF flooding broadcast single type large short extremely high cost-insensitive scenario PROPHET probabilistic routing single type large short low regular-movent scenario MPRP opportunistic forwarding single type large short low earthquake-scenario


## 5.1. Environment Settings

The fire-rescue area is with the size of 35m×65m. At the beginning, N nodes (including 15 FNs and 3 RNs) are evenly deployed into the fire-rescue area. Every time slot, 3 explosion locations are randomly selected from all of the fire locations, and the nodes falling into the explosion ranges become LRNs. Each node generates a new data packet with a probability pg to report the nearby fire behaviors, and these data packets should be forwarded to RCC. The storage capacity of SRNs, LRNs, FNs and RNs is set to 5MB, 5MB, 50MB and 50MB, respectively. The values of other parameters are given in Table 3.Table 3
Simulation Parameters.
Parameter Description Value N Number of nodes 100 T Deadline 120 s pg Probability of a node generating a data packet at each time slot 0.5 Rc Communication range of each node 8 m τ Length of each time slot 20 s Ls Size of each data packet 500 KB S Storage of each node 30,000 KB κ Number of forwarded copies at each time slot 2 (vmin,vmax) Speed interval of SRNs (0.1,1.5) m/s ts Residence period of SRNs at each time slot 3 s tl Residence period of LRNs after each bounce 10 s tf Residence period of FNs at each time slot 5 s vf Movement speed of FNs 2.0 m/s re Explosion range 9 m rl Maximum bounce range 12 m ξ Stability threshold 0.4 ζ Constant in formula (1) 65 ς Propagation speed of electromagnetic wave 300,000 km/s B Channel capacity 8 kbps


## 5.2. Impacts of Time Slot Length and Data Packet Size

The results regarding the impacts ofτ on the total number of data packet copies and the delivery ratio are given in Figure 8. Each node generates a new data packet with the probability pg at the interval of τ, and thus a smaller τ leads to a larger number of data packets, which makes the network be saturated more easily and depresses the delivery ratio more severely.Figure 8
Impacts of time slot lengthτ.
(a)
Total Number of Data Packet Copies (b)
Delivery RatioFigure9 illustrates the impacts of data packet size on the delivery ratio, forwarding overhead (Forwarding overhead is defined as the average number of forwarded copies for each delivered data packet, and the index of forwarding overhead can measure the expense of the data packet deliveries.) and delivery delay. Figure 9(a) shows that a larger delivery ratio can be achieved with a smaller data packet size, which is attributed to the fact that more data packets can be propagated and held by nodes when the data packets are with smaller size. Besides, the curve of delivery ratio rises with the increase of N, regardless of the data packet size. This is because more receivers are available when the nodes are deployed more densely, and thus better data holders can be selected to enhance the delivery ratio. In Figure 9(b), the bars of forwarding overhead fluctuate very slightly with the increase of N, which indicates that DFAFR has a good scalability with respect to the forwarding overhead. In Figure 9(c), the curve with a smaller data packet size is much lower than others, and the delivery delay gradually decreases with the increase of N. The reason is that better intermittent paths can be found to shorten the delivery delay when the nodes are deployed more densely.Figure 9
Impacts of data packet size.
(a)
Delivery Ratio (b)
Forwarding Overhead (c)
Delivery Delay


## 5.3. Proportions of SRNs, LRNs and FNs in Data Holders

As described in Section4, DFAFR strives for maintaining the optimal proportions of SRNs, LRNs and FNs in data holders to enhance the delivery ratio. To verify the effect of this mechanism, some simulation results are given in Figure 10. Figure 10(a) shows the optimal solutions ρ¯s, ρ¯l and ρ¯f which are calculated by formula (8). Then, we can observe that DFAFR outperforms the results of other proportions (such as 8:1:1, 7:2:1 and 6:3:1, which are given in the form of ρs:ρl:ρf) in terms of the number of data packet copies, as shown in Figure 10(b). This is because the optimal proportions can increase the delivery ratio effectively, and thus the number of data packet copies is reduced simultaneously. Moreover, the total number of data packet copies increases with the increase of N, since more nodes generate more data packets. Accordingly, Figure 10(c) shows that DFAFR achieves the largest delivery ratio through adopting the optimal proportions, and this phenomenon tallies with the aforementioned analysis in Section 3.Figure 10
Impacts of the proportions of SRNs, LRNs and FNs in data holders.
(a)
Optimal Proportions (b)
Total Number of Data Packet Copies (c)
Delivery Ratio


## 5.4. Comparisons with Other Algorithms

This simulation compares the delivery ratio, forwarding overhead, delivery delay and network throughput (Network throughput is defined as the total number of data messages received per unit time by the destinations of all the multi-hop flows in the network) among DFAFR, DT, EF, PROPHET and MPRP, and the results are given in Figure11.Figure 11
Algorithm comparisons.
(a)
Delivery Ratio (b)
Forwarding Overhead (c)
Delivery Delay (d)
Network ThroughputSome observations are provided as follows: (a) DT achieves the smallest delivery ratio and the largest delivery delay because the source holds the data packets until it encounters the destination node, although the forwarding overhead of DT is much lower than other algorithms. (b) The forwarding overhead of EF is significantly larger than those of other algorithms due to its flooding mechanism. (c) The delivery ratio, delivery delay and network throughput of DFAFR are better than those of other algorithms. The reason is that DFAFR selects the appropriate data holders to enhance the delivery ratio and shorten the delivery delay, and some held data packets are allowed to be discarded by nodes to make room for new data packets. Especially note that the flooding mechanism in EF will make the storage of nodes be rapidly occupied, and many held data packets have to be casually discarded by nodes, thereby decreasing the delivery ratio and prolonging the delivery delay. (d) The forwarding overhead of DFAFR is lower than those of EF, PROPHET and MPRP, and the gaps become large with the increase ofN, as illustrated in Figure 11(b).The above results indicate that DFAFR outperforms other algorithms in terms of delivery ratio, delivery delay and network throughput with a low forwarding overhead. In summary, we give Table4 to show the differences of DFAFR, DT, EF, PROPHET and MPRP visually.Table 4
Comparisons of DFAFR, DT, EF, PROPHET and MPRP.
Algorithm Forwarding manner Mobility patterns Delivery ratio Delivery delay Forwarding overhead Scenario DFAFR opportunistic forwarding multiple types large short low fire-rescue scenario DT direct transmission single type small extremely long low delay-insensitive scenario EF flooding broadcast single type large short extremely high cost-insensitive scenario PROPHET probabilistic routing single type large short low regular-movent scenario MPRP opportunistic forwarding single type large short low earthquake-scenario


## 6. Conclusions

This paper investigates the opportunistic data forwarding problem for OMSNs in the fire-rescue scenario. In DFAFR, the types of SRNs and LRNs can be differentiated according to the position stabilities of nodes. DFAFR can enhance the delivery ratio and shorten the delivery delay with a low forwarding overhead, through maintaining the optimal proportions of SRNs, LRNs and FNs in data holders approximatively, and the new data holders are selected from the data holder candidates and the adjacent RNs according to the expected delivery delay.DFAFR is suitable for the event-emergent scenarios, especially the fire-rescue scenario. Note that in some practical applications the battery capacity of nodes is limited, and some nodes may exhaust their battery energy; besides, some nodes are probably damaged due to the nearby fire behaviors such as explosions. The exhausted nodes or damaged nodes are considered to quit the network, and in these cases the optimal proportions of SRNs, LRNs and FNs in data holders must be recalculated.



---

*Source: 3906483-2019-07-04.xml*