Communication recovery is necessary for rescue and reconstruction scenarios including earthquakes, typhoons, floods, etc. The rapid and stable communication link can provide efficient victims’ real-time information for the rescue process. However, traditional centralized communication links cannot traverse the further victims with information-sharing requirements. And the even communication link distribution leads to a load burden on the crowded victim area. Thus, we propose a three-layer architecture consisting of the emergency communication vehicle, backbone links, and branch links to rapidly recover communication via mobile robots. Then, considering victims’ distribution, an improved MaxMin distance algorithm is presented as the basis of robot dispatch. The relay probability of the link is also estimated with closed formulae. Finally, simulation results verify that our proposed algorithm can recover communication with lower delay and higher packet delivery ratio.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Introduction
Communication recovery is one of the most important components of disaster relief. Because disasters may damage or even fail communication infrastructure such as base stations and internet servers. It is also difficult for these devices to restore normal operation in the short term. This leads to the failure of conventional communication methods. However, the communication demand is enormous when rescuers need to pay close attention to the situations of victims trapped somewhere and the rescue progress at all times. Thus, in harsh disaster scenarios, the contradiction between urgent communication needs and damaged communication infrastructure motivates the rapid development of robot-assisted communication.
Compared to ground robots, the advantage of Unmanned Aerial Vehicles (UAVs) is that they can hover over disaster areas to collect real-time information without venturing into hazardous areas [1, 2]. Generally, UAVs can reach a rapid reconstruction of communication links by air and avoid ground obstacles [3]. Meanwhile, the macroscopic information acquired by UAVs provides crucial preprocessed messages for ground communication recovery and other rescue missions.
Advertisement
Ground robots can enter disaster areas and establish relatively stable emergency communication links to connect all victims at a close distance. The general pattern is the combination of the emergency communication vehicle (ECV) and mobile robots [4]. ECV equipped with a tiny server stops at the rim of the disaster area for safety and efficiency reasons and works as a control center [5]. While, based on mobile ad hoc networks (MANET), mobile robots with On-Board Units (OBU) move into the disaster area and transmit information through multi-hops [6‐8].
Many factors affect the construction and performance of emergency communication networks. Since the primary purpose of emergency communication networks is to connect victims, their locations need to be considered first. When disasters (for example, earthquakes, typhoons, and floods) suddenly strike, people are likely to be trapped in living areas where they gather, so victims may exhibit a non-uniform distribution. Another influencing factor is the robot’s trajectory [9]. The ergodic from the rim to the disaster area guarantees stability, but the segments away from ECV need a longer waiting time for links to be established, which may procrastinate the rescue process. Robots patrolling (visiting all victims at a certain frequency) the disaster area [10] brings fairness to victims, but the unremitting mobility of robots may hinder the stability of communication links. Therefore, rapid establishment and link stability are vital requirements for emergency communication. In addition, the limitation of resources, especially the number of robots, is also a factor worth noting. Robots are committed to maximizing communication performance in limited quantities.
The main contributions of this paper are as follows:
1.
A three-layer framework consisting of the ECV, backbone links, and branch links is proposed for emergency communication. Fixed backbones ensure the stability of the network, while flexible branches bring effectiveness and fairness.
2.
Considering the distribution of victims, an improved MaxMin distance algorithm is presented for clustering. The added fine-tuning mechanism makes the clustering results more reasonable and robust.
3.
With the influence of practical factors, the closed formulae for calculating the connection probability and data delivery delay of communication links are theoretically analyzed and provided. The provision of these closed formulae lays a theoretical foundation for robots’ dispatches.
The remaining sections are organized as follows: Sect. “Related work” discusses state-of-the-art work on communication recovery issues. The system model and multi-hop relay probability of mobile rescue robots are given in Sect. “System model”. Section “Adaptive communication recovery algorithm” proposes the three-layer communication recovery algorithm to solve the model mentioned in Sect. “System model”. Performance evaluations are shown in Sect. “Simulation results and analysis”. Section “Conclusions” presents the conclusion and future work.
Advertisement
Related work
The reconstruction of the communication network is an efficient and essential approach to realizing post-disaster rescue and smooth recovery [11]. Common equipment, i.e., emergency communication vehicles (ECV) [12], mobile robots [13], satellite access stations [14], etc., contributes to emergency communication. Meanwhile, emergency communication in complex disaster scenarios is also assisted by many advanced technologies for example big data analytics before, during, and after disaster scenes [15], edge and cloud computing [16], deep reinforcement learning [17], intelligent optimization [18], decision-making [19], etc. [20‐24]. From our perspective, methods for establishing rapid and reliable communication links can be classified into three categories: using assisted aerial nodes such as UAVs, planning efficient routing protocols for robots, and other communication methods.
1.
Assisted aerial nodes: Patrolling above the ruined area, UAVs with wireless communication terminals recover emergency communication with lower delay. Flexible aerial nodes are employed to recover communication rapidly [25]. The analytical model of the recovery probability recovers communication with a lower delay when the connectivity requirement is of the utmost importance. A social relationship-based timeliness-aware message splitting scheme is proposed for the energy-friendly UAV-assisted delay tolerant networks [26]. The social network evaluates the value of the messages based on the splitting optimization problem. The designed scheme can guarantee a lower delay. The number of served Internet of Things is formulated as an optimization model considering bandwidth, power allocation, and UAV’s trajectory to meet the device’s requirement during emergency communication [27]. In short, although established quickly and flexibly, communication links set by UAVs are usually susceptible to environmental changes and show instability. Also, continuous hovering is energy consuming and brings short duration of links.
2.
Efficient routing for robots: To efficiently complete the rescue and communication recovery tasks, multi-robot systems (MRSs) on the ground should consider optimal path routing. Combined with the endocrine cooperative particle swarm optimization algorithm, the improved routing recovery protocol considers the direction and diversity of victims. The repair of broken paths guarantees lower delay and overhead during communication recovery [28]. The multi-path routing protocol via a heuristic model of the attractor selection mechanism is extended [29]. The mechanism uses biological entities to change the environment adaptively and realize automatic recording and updating of alternative paths. It improves the packet delivery ratio and QoS during the communication recovery. Similar to [30], there are a large number of vehicles and robots to be scheduled in the dynamic rescue scene. A responsive ant colony optimization (RACO) is put forward to make a quick response to the large-scale routing. A novel particle swarm optimization (PSO) algorithm focusing on task allocation (TAPSO) is proposed to deal with robots’ dispatch in rescue scenes. This paper considers the survivors’ survival time in uncertain situations [31]. A novel four-quadrant mobility model is proposed to help robots move from the most intense core to the rim of the earthquake area. The given mobility model improves the rescue quality, and the routing protocol increases the packet delivery ratio of an emergency communication network [32]. Although many studies on ground robots have been proposed, there are still some practical influencing factors not be considered. For example, the non-uniform distribution of victims and the various performance of communication networks.
3.
Other communication methods: A smartphone-assisted disaster recovery method is proposed for post-disaster communication. Combining 5G technology and D2D communication, the method improves the performance of energy consumption and channel quality, which does not need mobile access points and mobile base stations [33]. An algorithm is devised to create clusters and select cluster heads appropriately [34]. The establishment of long-range links connects cluster heads and relay stations. This approach can save the power consumption and capacity of emergency wireless communication. The long-range system (LoRa) is presented and analyzed to obtain persons’ location through path-loss measurements [35]. LoRa achieves a relatively high packet delivery ratio when the sink range is reduced during communication recovery. However, for complex disaster scenarios with dense personnel, MANET is more flexible and resource-efficient compared to other methods mentioned above.
Overall, the existing approaches and algorithms for emergency communication recovery performance are constantly improved. The accuracy and efficiency of the communication link are gradually increased. In this paper, we intend to discuss the emergency communication recovery issue via multi-robot mobility. Compared to aerial node emergency networks, the approach assisted by ground robots can also combine communication recovery and the subsequent rescue process. However, there are still some problems seldom discussed in the complex changeable post-disaster scenario: (1) There is no effective architecture to analyze the emergency communication recovery based on multi-robot mobility and the victims’ distribution. (2) The mobility of robots lacks comprehensive consideration of connection stability and recovery delay. (3) The optimization model to describe the emergency communication recovery problem is seldom discussed. Therefore, this paper mainly aims to solve the problems of the three aspects.
System model
In this section, we propose an emergency communication recovery architecture and discuss the recovery process. Then, the connection probability is analyzed based on impact factors including the clusters of victims, the backbone, and branch links.
System architecture and assumption
As shown in Fig. 1, this paper mainly discusses the issue of robot-assisted emergency communication recovery based on MANET. In disaster scenarios, taking cities after earthquakes as an example, the distribution of victims represents a non-uniform model. Because victims are more likely concentrated and trapped in living areas for example apartment buildings, schools, shopping malls, etc. Therefore, communication recovery considering victims’ distribution realizes the rapid response and communication cost saving. In this paper, we assume that the macroscopical information on victims’ distribution is acquired via the GPS [36] or UAV [37]. As shown in Fig. 1, the victims’ information is collected by the ECV, which stops at the rim of the disaster area. The ECV equipped with a tiny temporary base station works as a server during the communication recovery process and subsequent rescue tasks. Robots are deployed with on-broad units (OBU) [6]. It can realize the device-to-device (D2D) communication among moving robots via MANET [38]. The robots used for communication recovery can be divided into two categories according to their different tasks. One is called fixed robots that establish backbone links according to the victim’s distribution. The fixed robots remain in the calculated positions during the whole rescue process. The other consists of mobile robots that establish the branch links. Mobile robots move within the area of the cluster they belong to. The branch links aim to ensure the information of all victims in the cluster is obtained.
Fig. 1
Illustration of the emergency communication recovery procedure
×
Based on the system assumptions and scenario descriptions, our emergency communication recovery architecture contains three layers. The first layer is the ECV with a tiny base station at the rim of the disaster area. It collects all victims’ information acquired from GPS or UAVs. Based on the collected distribution information, the ECV can determine the clusters of victims and initialize the robot sets, i.e., step 1∼3 in Fig. 1. The second layer is constructed by fixed robots. The number of backbone links and fixed robots depends on the volume and positions of the clusters. Backbone links are from the ECV to the centers of clusters. Furthermore, the optimal positions of relay nodes in a backbone link are calculated by the proposed closed formulae. Then, robots allotted for the cluster start moving to these optimal positions to work as fixed relays. So far, backbone links are established as shown in step 4∼7 of Fig. 1. The third layer contains the remaining mobile robots that wait for further dispatch. Specifically, a single dispatch can cover all the branch links when mobile robots are sufficient. Otherwise, the dispatches are more than once, i.e., step 8 in Fig. 1. The victim clustering, the calculating of fixed relay positions, and the dispatch of mobile robots in branch links are further discussed quantificationally in the next subsection. The notations and descriptions mentioned are shown in Table 1.
Table 1
Notations and descriptions
Notations
Descriptions
\({\mathbb{V}}\)
The vector space of victims
\(V\left(k\right)\)
The kth victim vector includes the position
\(\mathbf{R}\)
The set of robots
\(r\)
The wireless communication range of robots
\(\rho \)
The average density of relay nodes in robots’ range
\({\mathbf{R}}_{\mathbf{f}}\)
The set of robots dispatched to backbone links
\({\mathbf{R}}_{\mathbf{m}}\)
The set of robots dispatched to branch links
\(N\)
The number of victims
\(Q\)
The number of robots
\(m\)
The number of divided victim clusters
\({P}_{h}\)
Connection probability per hop in recovery link
\({t}_{hop}\)
The duration per hop in wireless communication
\(v\)
The average speed of robots
\(D{e}_{bb}\left(i\right)\)
End-to-end delay of backbone communication link \(i\)
\(T\left(j\right)\)
Duration of jth cluster’s communication recovery
\(TT\)
Total time of communication recovery in the scenario
\({\mathbb{C}}\)
The set of clusters after clustering
\(C\left(i\right)\)
The divided ith cluster via victims’ distribution
\(c\left(i\right)\)
The center position of ith cluster
\(ch\left(i\right)\)
The ith cluster head in the clustering process
\({L}_{ij}\)
Euclidean distance between \(i\) and \(j\)
\(D\)
The number of loops within a branch link
Problem formulation and communication recovery estimation
Problem description and modeling of clustering
We define the victims’ information as a vector space as \({\mathbb{V}}=\{V\left(1\right),V\left(2\right),\dots ,V(N)\}\). Vector \(V\left(k\right)=({x}_{k},{y}_{k})\) contains the Euclid position of a victim whose identification denotes \(k\). The positions of victims are acquired via GPS or UAVs as above discussions and assumptions. The geographical distribution determines the clustering results of victims. The number of clusters equals the number of backbone links. Then, victims’ clusters are formed as a new vector space \({\mathbb{C}}=\{C\left(1\right),C\left(2\right),\dots ,C(m)\}\). The ith cluster is represented as \(C\left(i\right)=\{V\left(p\right),V\left(q\right),\dots \}\). Specifically, we define the vector \(c\left(i\right)=({x}_{i},{y}_{i})\) as the center position of cluster \(i\). Therefore, the clustering of victims is extracted as a multi-objective optimization model:
Here, the first objective Eq. (1) satisfies the minimum sum of distances between victims within the specific cluster. \(Q\left(i\right)\) is a scalar that denotes the number of victims in the ith cluster. The second objective Eq. (2) guarantees the maximum sum of the distance between the divided clusters. The distance between any two clusters depends on the positions of their centers, which denotes as \({c(i)}_{x}=\frac{1}{Q\left(i\right)}\sum \{{V(k)}_{x}\}\) and \({c(i)}_{y}=\frac{1}{Q\left(i\right)}\sum \{{V(k)}_{y}\}\). The multi-objective of the proposed optimization model considers the positions of both inter-cluster and intra-cluster. The constraints further limit the victims’ clustering. The first constraint shows that all the victims will be divided into a specific cluster without missing. Equation (4) constricts that there is no overlap of any two clusters. Equation (5) means that there is at least one victim in each cluster and \(\frac{N}{2}\) at most. \(N\) denotes the total number of victims. Furthermore, Eq. (6) shows that the number of clusters \(m\) should not be larger than \(\frac{N}{2}\). The third and fourth constraints, i.e. Equations (5) and (6), control the clustering process within a reasonable range. A victim \(V\left(k\right)\) is classified into cluster \(i\) instead of \(j\), because it is closer to \(c\left(i\right)\) than \(c\left(j\right)\) as shown in Eq. (7).
Modelling and communication estimation of backbones and branches
Based on the above multi-objective optimization model, all victims can be divided into several clusters according to their positions. The number of clusters determines the number of backbone communication links. Backbone links are built by using rescue robots as fixed relay nodes and start from the ECV to the centers of clusters.
To model backbone and branch links, some communication performance metrics are given first. The connection probability per hop \({P}_{h}\) denotes Eq. (8) [8].
$${P}_{h}=(1-{e}^{-r\rho })$$
(8)
Here, \(r\) denotes the average wireless communication range of rescue robots. \(\rho \) denotes the density of relay nodes per communication range. The entire connection probability from the source to the destination depends on the relative distance of adjacent fixed robots. Therefore, the connection probability of the backbone link \(i\) denotes Eq. (9).
Here, \({k}_{i}\) is the number of hops in the backbone link \(i\), as well as the fixed robots needed in this link. To simplify, the fixed robots obey the uniform distribution in the backbone link, which means that \({k}_{i}=\lceil\frac{{L}_{i}}{r}\rceil\). \({L}_{i}\) denotes the distance from the ECV to \(c\left(i\right)\). Suppose that the duration per hop denotes \({t}_{\mathrm{hop}}\) and the average moving speed of robots is \(v\). \(D{e}_{bb}\left(i\right)\), the end-to-end data delivery delay estimation of backbone link \(i\) is in Eq. (10).
After discussing backbone links, branch links connecting all victims within a cluster attract attention. The dispatch of robots including fixed ones for backbone links and mobile ones for branches should satisfy several basic rules shown in Eqs. (12–15). Certainly, the specific dispatch mechanism will be formed according to various factors of the actual cases.
\(\mathbf{R}\left(i\right)\) represents the set of robots dispatched to the cluster \(i\). \({\mathbf{R}}_{\mathbf{f}}\left(i\right)\) is the set of fixed robots on the backbone link \(i\). \({\mathbf{R}}_{\mathbf{m}}\left(i\right)\) is the set of mobile robots wandering within cluster \(i\). \(m\) equals the number of total robots.
To further draw up the dispatching plan of mobile robots in cluster \(i\), \({R}_{m}^{\mathrm{thr}}\left(i\right)\), a threshold number of mobile robots is put in Eq. (16). It means besides the fixed robots if there are still at least \({R}_{m}^{\mathrm{thr}}\left(i\right)\) robots in cluster \(i\), communication can be resumed without dispatching robots again.
Comparing the number of mobile robots \({R}_{m}\left(i\right)\) and \({R}_{m}^{\mathrm{thr}}\left(i\right)\), there are two cases:
Case 1: \({{R}_{m}\left(i\right)\ge R}_{m}^{\mathrm{thr}}\left(i\right).\) The intra-cluster communication of cluster \(i\) can be recovered within one loop when the number of available robots is more than the threshold. In this case, \({R}_{m}^{\mathrm{thr}}\left(i\right)\) mobile robots can make sure every victim is connected. The robot dispatch can be extracted as an optimization model with a drift-plus-penalty architecture, shown as Eqs. (17)–(19). The model considers the max connection probability of victims and the min moving time of robots.
Here, \({L}_{V\left(k\right),c(i)}\) denotes the distance between victim \(k\) and the center of cluster \(i\). Similar to \({T}_{bb}\left(i\right)\) in Eq. (11), the completed recovery time of the branch link \(i\) denotes \({T}_{br}\left(i\right)\) in Eq. (20).
$$\begin{aligned} T_{{br}} \left( i \right) &= {\mkern 1mu} \mathop {{\text{max}}}\limits_{{V(k) \in C(i)}} \Bigg\{ \left( {1 - e^{{ - r\rho }} } \right)^{{\left\lceil {\frac{{L_{{V\left( k \right),c\left( i \right)}} }}{r}} \right\rceil }} \left\lceil {\frac{{L_{{V\left( k \right),c\left( i \right)}} }}{r}} \right\rceil t_{{{\text{hop}}}} \\ & \quad + \frac{{L_{{V\left( k \right),c\left( i \right)}} }}{v} \Bigg\} \end{aligned}$$
(20)
Case 2: \({{R}_{m}\left(i\right)<R}_{m}^{\mathrm{thr}}\left(i\right).\) The intra-cluster communication of cluster \(i\) will be recovered after multiple dispatching attempts because robots are understaffed. The more than once dispatch maintains the connection status of all victims to the greatest extent. The number of dispatch loops denotes \(D=\lceil\frac{{R}_{m}^{\mathrm{thr}}\left(i\right)}{{R}_{m}\left(i\right)}\rceil\). Equation (17) is modified accordingly.
Therefore, \(T\left(i\right)\) the total recovery time of cluster \(i\) containing both backbone and branch link is shown in Eq. (21).
Because the communication links to all clusters are recovered synchronously, the total communication recovery time \(TT\) depends on the slowest cluster, as shown in Eq. (22).
$$TT={\mathrm{max}}_{i=1}^{m}\{T(i)\}$$
(22)
Overall, the models of victim distribution, backbone link establishment, and mobile robot dispatch in branch links are extracted in this subsection.
Adaptive communication recovery algorithm
In this section, we design and propose a real-time adaptive communication recovery algorithm to deal with the above optimization models. The proposed algorithm contains three processes. (1) An improved MaxMin algorithm with a heuristic index parameter α. (2) An adaptive fixed robot dispatch algorithm to build backbone links. (3) A real-time dispatch mechanism for mobile robots to establish branch links.
Victim clustering via the improved MaxMin distance algorithm
We use the MaxMin distance algorithm (MMDA) for the victim clustering process. Because objects far apart from each other are more likely to be selected as cluster heads in MMDA. This avoids the possibility of clusters being too close in Euclidean space at the beginning of clustering. To be specific, our improved MaxMin distance algorithm (IMMDA) first initializes the environment parameters and loads the victims’ id and positions shown as the vector space \({\mathbb{V}}\). Then, randomly select a victim \(\mathrm{V}\left(k\right)\) as the initial cluster head, which denotes \(ch(1)=V\left(k\right)\). The second cluster head is the victim furthest from \(ch\left(1\right)\). The distance between \(ch(1)\) and \(ch(2)\) marks as \({L}_{12}\). Next, calculate the distance from all victims to \(ch(1)\) and \(ch(2)\), donated as \({D}_{i1},\) and \({D}_{i2}\). If \({D}_{i}=\mathrm{max}\{\mathrm{min}({D}_{i1},\)\({D}_{i2})\}\) and \({D}_{i}>\alpha {L}_{12}, \alpha \in (\mathrm{0,1}),\)\(\mathrm{V}\left(i\right)\) is selected as the third cluster head \(ch\left(3\right)\). The rest of the cluster heads are processed in this way. Finally, allocate all victims to each cluster according to the principle of proximity. There are three stop criteria to mark the end of clustering.
1.
Maximum iteration: The number of iterations should be less than half of the number of victims. Otherwise, the victims’ distribution will be too dispersed to be clustered.
2.
Satisfy the constraints: The current clusters satisfy the constraints of our optimization model in the meantime, shown in Eqs. (3)∼(7). The clustering result represents the optimal results considering the index parameter is \(\alpha \).
3.
Clustering results fine-tuning: Whether a new cluster is created largely depends on the value of \(\alpha \). Thus, some fine adjustments are employed to \(\alpha \) to check the robustness of clustering results. Following this line of thinking, IMMDA adjusts \(\alpha \) to \(\alpha \pm n\delta \), where \(\delta \) is a tiny value to float \(\alpha \), and introduces a voting mechanism. The new cluster head will be designated when the \(n+1\) (more than half) votes are in favor. Because the number of votes is \(2n+1\), as shown as {\(\alpha -n\delta \), \(\alpha -(n-1)\delta \), …, \(\alpha \), …, \(\alpha +(n-1)\delta \), \(\alpha +n\delta \)}. The pseudocode of the victim clustering is shown in Algorithm 1.
×
Backbone links establishment via adaptive fixed robot dispatches
After Sect. “Victim clustering via the improved maxmin distance algorithm”, \(m\) clusters are generated via IMMDA. Then, the backbone links from the ECV to \(m\) clusters start to be established instantly. To improve efficiency, the center positions of clusters instead of cluster heads become the end of the backbone links. Some robots in \(\mathbf{R}\) are selected as fixed robots, which will stay at the precalculated positions to work as relay nodes of backbones. To be specific, \(m\) backbone links are recovered via two steps: (1) Establishment: Set up hello packages and routing tables of relays. (2) Routing table update and maintenance: Test whether the \(m\) backbone links are recovered and communicate well or not.
(1) Hello package and routing table setting up: The recovery process relies on the Ad hoc On-Demand Distance Vector (AODV) routing. The parameters of the fixed robots will be filled in the reserved labels of AODV’s hello package. The added labels are shown in the shaded part of Fig. 2.
Fig. 2
Illustration of labels in the hello package
×
At the beginning of communication recovery, the ECV needs to allocate all robots to \(m\) clusters in a certain proportion. This proportion i.e. the number of rescue robots in every cluster is determined by two weight parameters \({\beta }_{1}\), \({\beta }_{2}\) in Eq. (23).
where \({\beta }_{1}+{\beta }_{2}=1\), and \({0\le \beta }_{1}\), \({\beta }_{2}\le 1\). It means that the number of dispatched robots for cluster \(i\) relates to 1) the number of victims in cluster \(i\) and 2) the number of hops from the ECV to the center of cluster \(i\). Both parameters have a positive relationship with the dispatched robots. In other words, clusters with more victims and farther away from the ECV need more robots. \(Q\) robots are dispatched to \(m\) clusters via Eq. (23), and the dispatched cluster ID will be filled in the robots’ CID label in Fig. 2. According to the practice, the algorithm assigns 4 bits for CID, as well as FLID. Robots begin moving along the trajectory from the ECV to the center of the dispatched cluster once the label of CID is determined. In the meanwhile, the label of AFN is arranged as 0. The AFN occupies 1 bit to label whether the robot has arrived at the relay position or not. The first arrival robot executes three procedures. (1) Changes its AFN label from 0 to 1. (2) Fills the sequence of the current fixed relay position in the entire backbone link into the FLID label. (3) Broadcast the message containing its AFN and FLID to all robots with the same CID. The remaining robots will keep moving until all scheduled positions are occupied.
(2) Routing table update and maintenance: The routing table is gradually updated as the robots move to the fixed relay positions one by one. The ECV sends the request messages within a specific duration to the robots that AFN equals 1. The FLID in response message reflects the procedure of backbone communication recovery. The routing table is updated when FLID updates from \(k\) to \(k+1\). Once ECV receives the response message from the center of the cluster i.e., \(c(i)\), it labels that the \(i\mathrm{th}\) backbone link is built up and recovered. Regarding the finished backbone links, ECV stores and maintains the previous routing table. The repeat request message guarantees the previous backbone links’ stability. Backbone links are deemed recovered when ECV obtains \(m\) completed routing tables. The pseudocode of the backbone link communication recovery is shown in Algorithm 2.
×
Real-time multi-loop robot dispatch for branch links
After the establishment of backbone links, ECV can communicate with the centers of clusters. However, the wireless communication range of the cluster center may not cover all victims within this cluster. Furthermore, some victims may be unconscious or lose communication terminals. Therefore, it is necessary to build up branch links within a cluster to guarantee every victim’s information is collected. Except for the robots that work as fixed relay nodes in backbone links, the remaining ones wandering around centers are available to build up branch links. Based on the relation between the number of victims and that of mobile robots, the detailed real-time multi-loop robots dispatch mechanism is classified into two cases:
Case 1: The intra-cluster communication can be recovered within one loop when the number of dispatched mobile robots is larger than the required threshold as \({{R}_{m}\left(i\right)\ge R}_{m}^{\mathrm{thr}}\left(i\right)\).
In this case, mobile robots are sufficient to cover the dispatched cluster. The branch links from the cluster center to every victim can be recover within one loop. However, when \({{R}_{m}\left(i\right)>R}_{m}^{\mathrm{thr}}\left(i\right)\), surplus robots will lead to a waste of communication resources to some extent. On the other hand, it takes time for these surplus robots to move from the current cluster to another. Therefore, we use surplus robots to improve the overall communication performance of branch links in this cluster. The number of surplus robots after one loop denotes \({{R}_{m}\left(i\right)-R}_{m}^{\mathrm{thr}}\left(i\right)\). As shown in Fig. 3a, the approach evaluates the connection probability of branch links in cluster \(i\) first. Then select the link with the minimum connection probability as the first priority to dispatch the surplus robots. The selected robots will move along this branch link at a constant speed. The labels of this dispatched robot are CID \(=i\), AFN = 0, and FLID \(=p\), where \(p\) is the ID of the branch link with the minimum connection. By adding a surplus robot to this branch link, the number of candidate relay nodes increases. The data package will be delivered even if part of the relay nodes discard it. The data package delivery ratio is improved via these surplus robots. The approach will repeat to find the link with minimum connection probability until \({{R}_{m}\left(i\right)-R}_{m}^{\mathrm{thr}}\left(i\right)\) mobile robots are all dispatched.
Fig. 3
a Illustration of branch link recovery within a cluster in Case 1; b Illustration of branch link recovery within a cluster in Case 2
×
Case 2: The intra-cluster communication can be recovered with more than one loop dispatch when the number of available robots is smaller than the required threshold as \({{R}_{m}\left(i\right)<R}_{m}^{\mathrm{thr}}\left(i\right)\). Because of the limitation of robot resources, \(D\) loops dispatch is taken to cover every victim, where \(D=\lceil\frac{{R}_{m}^{\mathrm{thr}}\left(i\right)}{{R}_{m}\left(i\right)}\rceil\). As shown in Fig. 3b, the proposed approach selects the branch link with the maximum connection probability to dispatch in every loop. The current loop of dispatch is completed until available robots are exhausted. Mobile robots are recycled and waiting for the next dispatch until all victims can communicate with the cluster center. There are two differences between 2 cases:
In case 2, the approach dispatches the robots to victims with a larger connection probability first, rather than the minimum in case 1. Because the approach needs to ensure every loop has optimal performance.
Branch links are built up and removed uninterruptedly to ensure that every victim can communicate at intervals until robots receive the task completion message from ECV. The pseudocode of the branch link communication recovery is shown in Algorithm 3. Moreover, the computing time complexity is \(n\).
×
To be clear, a flowchart of our method is presented to describe the relationship of the three algorithms step by step vividly (Fig. 4).
Fig. 4
The flowchart of our method
×
Simulation results and analysis
The simulations and evaluations aim to answer three questions: (1) Does the proposed communication recovery approach realize in general post-disaster scenarios. (2) How is the communication performance on the recovered backbone and branch links. (3) Does our proposed approach outperform other existing practical solutions.
Simulation environments
The simulations of the proposed algorithm and compared algorithms are employed in MATLAB. Post-disaster scenarios with different numbers and distributions of victims are generated randomly to test the generality of the proposed approaches. Considering the ECV’s ability to computing and dispatch, the length and width of the scene are both set as 500 m. The default average speed of robots denotes 6 m/s. Regarding the energy consumption during movement and communication, the max work duration per robot denotes 120 min. It means that the established communication links will be disconnected if the duration extends 2 h. The details of the parameters and metrics are shown in Table 2.
Table 2
Simulation parameters and value
Simulation parameters
Value
Scenario length (m)
500
Scenario width (m)
500
Average robot mobile speed (m/s)
6
Default communication range (m)
20
cbr packet generation rate
0.01
Default duration per hop (s)
0.0042
Simulation time upper bound (min)
200
Wireless communication bandwidth (Mhz)
3
Package size (kb)
512
Four metrics are selected to evaluate the performance of emergency communication recovery:
Packet delivery ratio (PDR): The ratio of the successfully delivered packets to the total packets ECV sends. This metric reflects the stability performance of the communication recovery methods.
The first packet arrival time (FPAT): The minimum duration to recover communication from victims to the ECV. This metric reflects the performance of response speed.
The communication recovery time (CRT): The maximum duration to recover communication from victims to the ECV. Compared to FPAT, CRT reflects the fairness of the communication recovery method.
Average data delivery delay (ADDD): The average duration between two successive delivered packets.
Comparing algorithms based on the AODV routing protocol are chosen as follows:
1.
Non-clustered method: The method dispatches robots evenly and victims are not clustered. Victims near the ECV will be selected in earlier loops when the number of robots is insufficient to complete recovery tasks in one loop [39].
2.
Four-quadrant mobility method: Robots move and start communication recovery from the center of the scenario. The robots are dispatched evenly to four divided quadrants and diffuse to peripheral rectangle rings [32].
The proposed algorithm performance analysis
Based on the settings in Table 2, an example is taken to show the victim clustering results visually in Fig. 5. Twenty victims are generated randomly within the boundary of the scene as shown in Fig. 5a. Based on the IMMDA, victims are divided into four clusters shown in different colors and the calculated position of every cluster center is shown as a black triangle in Fig. 5b. After cluster centers are obtained, the fixed relay positions of backbone links can be determined. Considering the robots’ wireless communication range is 20 m, the fixed relays are presented by red triangles in Fig. 5c. Figure 5 shows that the backbone links are built up with a limited number of robots successfully. In addition, a video example of the entire communication recovery process is available at https://github.com/cherriezhao/CIS.
Fig. 5
The snapshots of clustering results and backbones’ establishment
×
To test the performance of our algorithm, four scenarios with different parameters are conducted as shown in Table 3. The number of robots in all four scenarios is set to 100. And the number of victims is 20 in scenarios 1, 2, and 3, while 30 in scenario 4. The communication range of robots is 25 m in scenario 1 and 30 m in others. Because of the differences in these parameters and the different initial distributions of victims, the number of clusters in each scene is also different. Because IMMDA is related to the geographical distribution of victims, the same number of victims may be divided into different numbers of clusters, and vice versa. In short, IMMDA adjusts the cluster results based on the relative Euclidean distance among victims and guarantees the cluster division results are suitable for the following backbone link setting up.
Table 3
Illustration of four communication recovery cases
Scenario
1
2
3
4
#robots
100
100
100
100
#victims
20
20
20
30
Communication range (m)
25
30
30
30
#clusters
4
4
5
4
#robots for backbone links
53
46
58
43
#robots for each cluster
10 14 12 11
15 12 10 17
12 4 9 6 11
16 14 10 17
one loop dispatch?
N N N N
N Y Y Y
Y N Y N Y
N Y Y N
PDR (backbones) theoretical (%)
66.2 72.3 64.8 86.2
61.5 78.2 70.5 76.1
79.7 82.8 75.0 76.5 80.6
68.4 71.7 82.4 79.3
PDR (backbones) simulated (%)
65.8 72.9 65.1 84.9
60.8 79.9 71.3 77.0
80.3 83.2 75.8 77.4 81.4
69.1 70.8 83.2 80.0
PDR (branches) theoretical (%)
87.5 86.7 91.5 80.8
83.3 81.3 84.7 94.5
87.9 88.6 85.8 89.2 89.5
78.6 89.2 95.5 88.4
PDR (branches) simulated (%)
87.0 87.1 89.6 81.2
83.8 81.7 85.3 93.9
88.3 89.2 86.4 90.5 90.3
77.7 90.0 96.4 89.9
Total simulated PDR (%)
72.1
80.2
79.6
77.4
FPAT(s)
104.4
100.3
89.6
115.8
recovery finished time(s)
120.6
130.7
109.3
137
Delay theoretical(s)
2.3
2.8
2.9
2.6
Delay simulated(s)
3.1
3.3
3.6
2.6
Table 3 also reflects the differences among clusters of dispatched robots. As mentioned before, the number of robots sent to a cluster depends on the number of clusters, the number of victims in the cluster, the communication range of robots, and the distance between a cluster and the ECV. Except for the ones in the backbone link, other robots belonging to this cluster are sent to build branches within the cluster. The number of robots in a cluster directly affects the establishment and performance of the branch. Due to limited robot resources, some clusters cannot recover their branch links within one loop. For instance, as scenario 1 owns a lower wireless communication range, it occupies more robots on the backbone link thus fewer on the branch. With similar but not the same reasons, scenario 4 with more victims needs more robots to cover all branch links.
To discuss the PDR performance, we take scenario 3 as an example, which owns five backbones and branches. The PDR of the five branches is different because PDR depends on the number of hops from ECV to victims. The farther the center of a cluster is from ECV, the longer this backbone link is. When the communication range is the same, a longer link means more relays and more hops, thus increasing the probability of packet discard per hop. It is also worth noting that PDR is independent of the number of loops in a cluster. Take Scenario 3 as an example again, the fourth branch link cannot recover in one loop but the fifth can. However, they get very close PDR values, which are 90.5 and 90.3, respectively. Furthermore, the average data delivery delay of 4 cases maintains between 2 and 4 s. The reason is that the backbones are fixed and stable, while the branch links are looped when robots are inadequate, which can realize a robust link from ECV to victims. In the next subsection, we will further discuss our proposed method’s performance compared with other algorithms.
Performances comparison analysis
Figure 6 shows PDR performances among our proposed algorithm and the comparing algorithms in different scenarios. Figure 6a focuses on different scenarios with the same limited resources, which is 100 robots with a communication range of 25 m to assist 20 victims. As per the aforementioned discussion, IMMDA divides different numbers of clusters as 3, 4, and 5 based on the victims’ distribution. In these three scenarios, the PDR ranks as Our proposed method > No clusters method > Four quadrant method. Furthermore, the PDR of our proposed method performs better when the number of clusters is fewer. For instance, the PDRs are 75.7%, 67.9%, and 65.5% in 3 clusters, 4 clusters, and 5 clusters scenarios, respectively. Because the number of clusters reflects the distribution of victims. The fewer clusters mean that victims assemble in relatively near or concentrated areas. Therefore, the number of robots dispatched as fixed relay nodes in backbone links is fewer. In that way, more robots are set to recover the branch links, which increases the stability of the entire link.
Fig. 6
Packet delivery ratio performance comparison in different parameters: a in different numbers of clusters; b in different numbers of robots; c in different communication ranges
×
Figure 6b shows the PDR performances of three algorithms in different numbers of robots from 100 to 300. PDR of all three algorithms increases as the number of robots increases. Because the more dispatched robots, the more relay nodes contain. When a link is broken or disconnects in some of the hops, other surplus robots can be the candidates to reconnect it, which will increase the PDR. The rank of PDR is also Our method > No clusters method > Four quadrant method.
Accordingly, Fig. 6c shows the PDR performances of three algorithms in different communication ranges from 25 to 50 m. PDR of all three algorithms increases as the communication range increases. The reason is that the number of muti-hops decreases as the range rises with the same number of dispatched robots, which will present a negative relation to the PDR. The rank of packet delivery ratio is also Our proposed method > No clusters method > Four quadrant method. The reason for our proposed method’s advantage on PDR with the limited recovery resource is that the multi-layer architecture can maintain the stability of recovered links. Backbone links are fixed during the entire recovery process to guarantee the robust. The end of branch links located at the centers of clusters sends packets repeatedly until all victims are connected within one or multiple loops. Moreover, we also evaluate the PDR with both theoretical and simulated results. The trend of theoretical results matches the simulated results, which proves the correctness of our discussion in “Adaptive communication recovery algorithm”.
Figure 7 shows three duration-related metrics’ performances on three algorithms in different numbers of robots with a 25 m communication range and 20 victims. Figure 7a shows the average data delivery delay performance. With the number of dispatched robots ranging from 100 to 300 at intervals of 50, the ADDD of all three algorithms maintains within a narrow range, i.e., no cluster method denotes 9.10 s, four quadrant method denotes 7.55 s and ours denotes 2.78 s. Compared to the other two, our proposed method has the lowest ADDD because relatively short links are obtained from the parallel work of clusters. Without backbone links, the four quadrant method and no cluster method need to reconsider the routing results during each loop, which will increase the data delivery delay.
Fig. 7
Performance comparisons in the different numbers of dispatched robots: a average data delivery delay; b first packet arrival time; c communication recovery time
×
Figure 7b shows the first packet arrival time among the three algorithms. No cluster method has the best performance because its recovery strategy is based on the distance between victims and ECV. Victims located near the ECV may be within its communication range. Thus, they can be connected and communicated from the beginning without waiting for robots’ dispatches. However, in practice, victims near the rim usually suffer less from the disaster due to being relatively far away from the hypocenter. Their communication recovery may not need a high priority. Similar to no cluster, in the four-quadrant method, the value of FPAT is higher but fluctuates in a small range of around 51.42 s. The increase in FPAT is because the ECV must move from the rim to the center of the scene first before dispatching robots. Compared to the no-cluster method, the four-quadrant can preferentially recover communication of victims in more serious conditions. Obviously, our method has a shortage in the scenario with fewer robots. The reason is that victims need to wait for the accomplishment of all backbone links first. With the increment of the number of robots, most clusters can recover the branch link synchronously, and the FPAT reduces to 32.53 s.
Conversely, our proposed method has the best performance on communication recovery time, as shown in Fig. 7c. Because no cluster method and four quadrant method take a lot of time to get communication with the victim farthest from the ECV. Though there is a downward trend in the two comparing algorithms with the increment of dispatched robots, our proposed method still outperforms the accomplishment of total links and the fairness of victims. Furthermore, we also evaluate the three duration metrics with both theoretical and simulated results. The trend of theoretical results matches the simulated results, which proves the correctness of our discussion in “Adaptive communication recovery algorithm”. It is worth noting that the positions of victims are randomly generated in every scenario. When calculating communication metrics such as ADDD, the data packet is sent 1000 times repeatedly.
Figure 8 shows three duration-related metric performances on three algorithms in different communication range with 150 robots and 20 victims. Figure 8a shows the average data delivery delay performance. With the communication increases from 25 to 50 m at intervals of 5 m, the ADDD of all three algorithms has a decrement trend, for example, the no cluster method reduces 20.7%, the four quadrant method denotes 13.6% and our proposed method is 41.7%. The reason is that the number of hops between ECV and victims is reduced as the range increases, which has a positive relation to data delivery delay. Compared to the other two algorithms, our proposed method has the lowest ADDD because of the multi-layer architecture, and links of all clusters are established synchronously, which may bring relatively fewer hops for each victim. Without backbone links, the four quadrant method and no cluster method should reconsider the routing results during different loops of recovery, which will increase the data delivery delay.
Fig. 8
Performance comparisons on different communication ranges: a average data delivery delay; b first packet arrival time; c communication recovery time
×
Figure 8b shows the first packet arrival time performance on the three algorithms. No cluster method has the best performance also because its communication recovery strategy is based on the distance between victims and ECV. Similar to no cluster, the FPAT of the four-quadrant method maintains around 53.99 s. The reason is the same as the aforementioned discussion in Fig. 5b. As the increment in communication range, the number of the fixed relays decreases, and most clusters can recover the branch link synchronously, the FPAT of our method reduces by 83.26% from 136.09 to 22.79 s.
Similar to Fig. 7c, our proposed method has a relatively stable performance on communication recovery time. However, in the case of large communication ranges, our method is inverted by the no-cluster method as shown in Fig. 8c. The other two both have a downward trend with the increment of communication range, which is because loops of dispatch are reduced. Fewer loops have the greatest impact on the no-cluster method compared with the other two methods. However, a larger communication range brings greater energy consumption. Also, both theoretical and simulated results are evaluated and the match of their trends proves the correctness of our discussion in “Adaptive communication recovery algorithm”.
Conclusions
This paper is dedicated to recovering communication connectivity for all victims in disaster scenarios. Considering the non-uniform distribution of victims and the limited number of robots, we propose a practical method to quickly establish stable links for every victim. First, we propose an IMMDA clustering algorithm to divide victims into some clusters based on their distribution. Then, a three-layer communication architecture containing ECV, the backbone links, and the branch links is put forward. Among them, branch links collect information from all victims to the center of a cluster, while, ECV connects to every cluster center via backbones. Different from the fixed backbones calculated by equations, the branch link recovery method is real-time and adaptive. Because it can independently complete one or multi-loop dispatch based on the threshold and the number of victims and robots in this cluster. Simulation results (four communication metrics and many different scenarios) on our method and the comparisons with the other two algorithms show the advantage of rapidity and stability of the establishment. The established communication network also has good performance on the packet delivery ratio and data delivery delay which reflects the reliability of the network. In summary, our method performs better in resource-constrained situations and the established communication network lays the foundation for subsequent rescue efforts. In future work, more practice will be considered to improve our method, i.e., the injury conditions of victims and the priority of the rescue.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
