# Hybrid Recovery Strategy Based on Random Terrain in Wireless Sensor Networks

Authors: Xiaoding Wang; Li Xu; Shuming Zhou; Wei Wu
Journal: Scientific Programming
 (2017)

---

## Abstract

Providing successful data collection and aggregation is a primary goal for a broad spectrum of critical applications of wireless sensor networks. Unfortunately, the problem of connectivity loss, which may occur when a network suffers from natural disasters or human sabotages, may cause failure in data aggregation. To tackle this issue, plenty of strategies that deploy relay devices on target areas to restore connectivity have been devised. However, all of them assume that either the landforms of target areas are flat or there are sufficient relay devices. In real scenarios, such assumptions are not realistic. In this paper, we propose a hybrid recovery strategy based on random terrain (simply, HRSRT) that takes both realistic terrain influences and quantitative limitations of relay devices into consideration.HRSRT is proved to accomplish the biconnectivity restoration and meanwhile minimize the energy cost for data collection and aggregation. In addition, both of complexity and approximation ratio of HRSRT are explored. The simulation results show that HRSRT performs well in terms of overall/maximum energy cost.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) have raised a great attention thanks to their vast spectrum of industrial and social applications [1, 2], such as biological detection, environment monitoring, and battlefield surveillance. Data collection and aggregation are the first priority of WSNs. The primary objective of such task is to gather sensor readings from field sensors deployed over a geographic area (called the area of interest (AOI)) and then successfully deliver all gathered data to the sink node through multihop paths [3]. That implies the importance of both connectivity maintenance and optimal network topologies discovery for WSNs [4]. However, natural disasters and human sabotages will jeopardize the network connectivity so that the process of data aggregation will be compromised without doubt. For example, when a WSN is carrying out a surveillance mission on the activity of a volcano, if the connectivity is lost, then all gathered data will not be able to reach the sink node for further analysis. Without such important data, volcano eruption can not be predicted. That may cause massive casualties and severe economic losses.Due to the significance of network connectivity as mentioned above, the problem of connectivity restoration has been receiving increasing attention in recent years. Thus, it is imperative to design both connectivity recovery strategies and routing algorithms forWSNs. All known solutions, which exploit relay devices such as stationary relay nodes (RNs) and mobile data collectors (MDCs), can be classified into two categories. One is employing RNs only for the purpose of establishing a connected intersegment topology with stable communication paths between every pair of segments [5–9]. This category of work generally aims to minimize the number of RNs during the restoration process. The other one relies mainly on MDCs repeatedly visiting each individual’s segments for data collection and aggregation with a few RNs involved [10–18]. However, all of these works assume that either the terrain of AOI is flat or the number of relay devices is unlimited.Given that these assumptions are not realistic in real scenarios, our goal in this paper is to develop an efficient connectivity restoration strategy that takes both realistic terrain influences and quantitative limitations of relay devices into consideration.Our Contribution. This paper presents a hybrid recovery strategy based on random terrain in WSNs, namely, HRSRT, that establishes a biconnected intersegment topology in a disconnected network with a limited number of RNs and MDCs; meanwhile, the energy cost for data collection and aggregation is minimized. The HRSRT accomplishes our goal in this paper as follows:(1)
To quantify realistic terrain influences, the area of interest (AOI) is mapped into a grid of equal-sized cells. Each cell c is associated with a weight ω(c) that represents the corresponding terrain influence within. We calculate ω(P), the weight of each path P, by accumulating the weight of each cell along P, so that the weighted complete graph Kn is constructed based on minimum weight paths between segments.(2)
A path planning algorithm (PRTP) is developed on Kn to build a Hamilton cycle of minimum weight as the biconnectivity restoration tour T for MDCs. And ω(T) is proportional to the cost for data collection and aggregation during the connectivity restoration.(3)
According to different numbers ofMDCs, two different relay nodes deployment strategy, ORND and RND, are devised to merge intersected paths of T by carefully choosing candidate positions for RNs, so that ω(T) is greatly reduced.The rest of the paper is organized as follows. Related work is covered in Section2. The notions and terminologies are introduced in Section 3. The problem description is described in Section 4. The algorithm HRSRT is elaborated in Section 5. Section 6 gives the theoretical analysis on approximation radio and complexity of HRSRT. And the validation results are presented in this section as well. We conclude this paper in Section 7.


## 2. Related Work

There are two categories of approaches pursued for connectivity restoration [19]: the first category is to establish connectivity without terrain influences; the second one is to federate disconnected segments with consideration of terrain influences.There are many excellent works regardless terrain influences during the connectivity restoration, which fall into the first category. Some of these works that employRNs deployment only are listed as follows. Cheng et al. formulate placing the fewest RNs to connect segments as finding the Steiner minimum tree with minimum number of Steiner points and bounded edge length [5]. Lee and Younis propose grid based approaches, CORP [6] and ORC [7], both of which recursively deploy RNs until all segments are connected. In [20], recovery algorithms are proposed to minimize the deployment cost of sinks and relays and guarantee all sensors have two length-constrained paths to two sinks. Sitanayah et al. [8] find a minimal set of RNs which ensures k length-bounded vertex-disjoint shortest paths to a sink for each sensor node. Lee et al. [9] focus on achieving a biconnected intercluster topology. Other works that employ RNs, MDCs, and mobile nodes are listed as follows. In [10], Senel and Younis devise a convex hulk based recovery strategy IDM-kMDC. It finds k convex hulks of segments; then, each optimal tour for a convex hulk is assigned a MDC to restore the connectivity. In [13], a least-disruptive algorithm is designed, which considers the impact of topology change on network performance through selecting candidate mobile nodes based on routing tables. In [14], a k-hop neighboring information based algorithm is presented, which drives the backup mobile nodes to its destination to avoid intersensor collisions. In [15], a localized hybrid timer based cut-vertex node failure recovery approach is proposed, which adopts cascaded movement to relocate the mobile nodes so that the timely restoration is ensured. Joshi and Younis [21] establish balanced and optimized data collection and aggregation tours using the mobile nodes within the network. They first construct a minimum spanning tree then successively split it around the center into partitions such that the segments of each partition form a convex hulk. Eventually, all available MDCs are assigned to partitions to complete the recovery process. In [16], Liao et al. aim at providing target coverage and network connectivity establishment through the minimum movement of mobile sensors. In [11], a delay-conscious recovery strategy, FeSMoR, was proposed to federate disjoint segments with a limited number of relay nodes. In [12], a convex hulk based recovery scheme MiMSI is designed, which assigns MDCs for intersegment federation and deploys RNs for intercluster connection. In [18], a distributed algorithm GSR is designed to decompose the deployment area into its corresponding skeleton outline, along which mobile RNs are placed to finish connectivity restoration.There are many excellent works with consideration of terrain influences during the connectivity restoration, which fall into the second category. Zhou et al. [22] propose an extended rapidly exploring random tree (RRT) based algorithm to initiate a path for a mobile node to reach the intended destination without crashing into any obstacles. Senturk and Akkaya [23] investigate how realistic terrain influences affect network connectivity recovery. Then, they design a terrain based restoration strategy ReBAT [24] that considers different terrain types, such as forest, hill, swamp, and flat. ReBAT attempts to find the least cost paths between disjoint segments regardless of the subsequent data collection and aggregation. Truong et al. [17] propose a family of algorithms under the consideration of the impact of obstacles on mobility and communication, all of which collaborate to restore the connectivity with the least number of relay nodes and meanwhile minimize the mobility cost of agents. In [25], Mi et al. propose an obstacle-avoiding connectivity restoration strategy to avoid convex obstacles and intersensor collisions; however, they fail to consider realistic terrain influences on the process of connectivity restoration.In this paper, we focus on establishing a biconnected intersegment topology in a disconnected network with a limited number ofRNs and MDCs and meanwhile minimize the energy cost for data collection and aggregation. It is worth to mention that establishing a biconnected intersegment topology, the quantitative limitation of relay devices, and minimizing the energy cost for data collection and aggregation are seldom considered all at pervious works unlike ours.


## 3. Preliminary

Some notations used throughout this paper are given first; the important symbols with their definitions are collected in Notations.Definition 1.
A weighted complete graphKn=(V,E,W) is a complete graph of n vertices with each edge associated with its weight, where V and E denote the set of vertices and edges in Kn, while W stands for the set of weights of edges. To be more specific, the weight of an edge sisj∈Kn is equal to ω(Pi,j∗).Definition 2 (see [26]).
An Euler closed trailEG is a closed trail that visits every edge of graph G exactly once. A graph that has an Euler closed trail is called an Euler graph.Definition 3 (see [26]).
A Hamilton cycleH is a closed trail that visits every vertex of graph G exactly once. A minimum weighted Hamilton cycle of graph G is denoted by HG.Figures2 and 3 show the examples of a Euler closed trail E and a Hamilton cycle H, where (1)E=s1s2s6s3s4s5s6s7s1,H=s1s2s3s4s5s1.Figure 1
S P 6 versus CH6.
(a) (b)Figure 2
An Euler closed trail.Figure 3
A Hamilton cycle.Definition 4 (see [26]).
Given a graphG=(V,E), a matching MG is a set of pairwise nonadjacent edges; that is, any two edges share no common vertex.Definition 5 (see [26]).
A perfect matchingMG∗  is a matching which matches all vertices of the graph G. That is, every vertex of the graph is incident to exactly one edge of the matching.Definition 6.
For three edgesa, b, and c of a triangle T, we define ω(a)+ω(b)≥ω(c), the weighted triangle inequality, abbreviated as WTI.Definition 7 (see [26]).
A graphG is said to be k-connected, if for each pair of vertices there exist at least k mutually independent paths connecting them; that is, the graph G is still connected even after removal of any k-1 vertices from G. A k-connected graph G is of k-connectivity.


## 4. Problem Description

Wireless sensor networks are deployed in realistic environments for data collection and aggregation. Therefore, the connectivity of aWSN is easily compromised due to nature disasters. Under such circumstances, the recovery strategy is required to restore the connectivity in a realistic environment. That implies that the terrain influences need to be taken into consideration. It is worth mentioning that the terrain influences on connectivity restoration are closely related to the landforms of AOI, such as forest, hill, swamp, and flat. Especially in some realistic scenarios, there exists a shortcut between two cites si and sj; however, taking such shortcut will incur a significant energy cost. Intuitively, the possibility of taking a detour should be considered. To quantify the terrain influences, the area of interest (AOI) is mapped into a grid of equal-sized cells (squares) with side length (2/2)R. Besides, both segments and RNs are assumed to center at cells. The rationale is that RNs placed at eight neighboring cells are reachable for si. More importantly, sensing data from eight neighboring sensors can be collected by a MDC while travelling through si.As shown in Figure4(a), a set of segments or RNs, for example, S={s2,s3,s4,s5,s6,s7,s8,s9}, is located at eight neighboring cells of s1. It is clear that (2/2)R≤L(s1,si)≤R, where 2≤i≤9. Therefore, they are neighbors. Figure 4(b) shows that sensing data of s2, s3, s4, s6, s8, and s9 are collected by a MDC while travelling through s1, where the dotted line represents the data collection tour.Figure 4
Neighboring cells and data collection.
(a) (b)Similar to ReBAT [24], risk and elevation are taken into account while determining the optimal path besides the distance. Specifically, each cell ci∈Cells is associated with a random terrain type, the corresponding risk factor, and an elevation. Accordingly, we use the weight function(2)ωci=side_lengthci×riskci×elevationcito represent the terrain influence on travelling through ci. In addition, Manhattan distance is used to accurately estimate the cost of paths and 4 directions (north, east, west, and south) are considered directly accessible while moving MDCs to an adjacent cell. We then measure the weight of Pi,j through the sum of the weight of all visiting cells except two specific cells, for example, ci and cj, where si and sj are located. According to (2), we give the weight function of a path ω(Pi,j) as follows:(3)ωPi,j=∑ck∈Pi,j∖ci,cjωck.Figures5(a) and 5(b) give the examples of ω(P1,2) and ω(P3,4), respectively. Note that if there are several minimum weighted paths Pi,j∗s, then choose the one with the shortest MD(si,sj) as Pi,j∗. Furthermore, we assume ω(Pi,j)=ω(Pj,i) in this paper. Let T be a data collection and aggregation tour; according to (3), ω(T) is given as follows:(4)ωT=∑Pi,j∗∈TωPi,j∗.In [24], Senturk et al. give the energy cost function Cost⁡(ci) for travelling through a cell ci as follows, where c is a constant value:(5)Cost⁡ci=ωci×c.According to (4) and (5), it is easy to deduce that the energy cost is proportional to the terrain influence. For simplicity, we use ω(Pi,j) and ω(T) to represent the energy cost of the path Pi,j and the tour T, respectively. The performance comparison in energy cost will be conducted using (8) in Section 6.2.Figure 5
The weights of paths.In addition, the required restoration strategy should be allowed to use only a limited number ofRNs and MDCs due to the fact that relay devices could be expensive. We then give the formal problem definition as follows.Givenn nodes with a transmission range of R that form k disjoint partitions in a squared region which consists of m×m cells of size (2/2)R, the goal is to provide a random terrain based solution (distributed/centralized) which ensures that k partitions and the sink node will bebiconnected by deploying a limited number of RNs and MDCs and meanwhile minimize the cost of data collection and aggregation.This paper is dedicated to solving such problem by proposing a polynomial time algorithm, namedHRSRT. It is worth mentioning that the the tour T constructed by HRSRT is not only the connectivity restoration tour but also the data collection and aggregation tour (see Figure 6).Figure 6
Network connectivity recovery withRNs and MDCs.


## 5. The HRSRT Approach

H R S R T is a random terrain based recovery strategy. It aims to ensure all disjoint segments including the sink node are biconnected; meanwhile, the energy cost of data collection and aggregation is minimized. During the restoration process, only k  RNs and m  MDCs are employed. In fact, the energy cost is tremendously reduced with more MDCs involved. Thus, according to different values of m, HRSRT adopts corresponding approaches to achieve the connectivity restoration as follows:(i)
m=1: If there is only one MDC available, then it needs to tour around all disjoint segments and the sink to collect and aggregate data.(ii)
m>1: If the number of MDCs is more than one, then the corresponding tour for each MDC should be carefully chosen so that total energy cost for data collection and aggregation is minimized.The framework ofHRSRT is shown in Figure 7. In this paper, we first introduce HRSRT as a centralized procedure; then, the distributed HRSRT is elaborated in Section 5.3. It is worth mentioning that the theoretical proof on the biconnectivity of tour T established by HRSRT is given in Section 6.1. That implies HRSRT can restore the connectivity with the consideration of terrain influences.Figure 7
The framework ofHRSRT.


### 5.1. HRSRT withm=1

Form=1, HRSRT works in two phases. First, a random terrain based path planning (RTPP) is implemented to initiate a connectivity restoration tour T in phase one. Then, an Optimized Relay Node Deployment (ORND) is adopted to reduce ω(T) in phase two. The pseudocode for HRSRT with m=1 is shown in Algorithm 1.Algorithm 1:HRSRT with m=1.
Input: A set S of n disjoint segments, S={S1,S2,…,Sn}. Output: A data collection and aggregation tour T. ( 1 ) T′=RTPP(S). ( 2 )  T=ORND(T′). ( 3 )  Return T.


#### 5.1.1. Random Terrain Based Path Planning (RTPP)

As we explained above, various terrains have significant influences on the cost of data collection and aggregation forMDCs. To quantify such influences, the cost for travelling through a unit area(cell) is represented by a weight value. Therefore, the priority of a path planning strategy on realistic terrains is to establish a tour of minimum weight for MDCs. In this section, a random terrain based path planning strategy, called RTPP, is proposed to accomplish the goal under the constrain that only m  MDCs are available.Suppose there aren disjoint segments. We take six steps to build a minimum weighted tour T′ as follows:(1)
According to the weight of each unit area, construct a complete weighted graphKn over the set of segments remaining disjoint. Each edge of Kn, for example, sisj∈Kn, is the minimum weighted path from si to sj, that is, Pi,j∗. Note that if there are several Pi,j∗s, then choose Pi,j∗ with the shortest Manhattan Distance between si and sj. The rationale is that the MDC movement toward an adjacent cell is in one of four directions as we mentioned above.(2)
Discover a minimum spanning tree (mst) of Kn.(3)
Find the setS of odd-degree vertices in mst; that is, S={si∣si∈mst,d(si)isodd}. Construct K|S|, an introduced graph of Kn, to establish a minimum weighted perfect math MK|S|. Then, initiate an Euler graph G′=MK|S|⋃mst.(4)
Randomly choose a vertexsi∈G′ and draw an Euler closed trail EG′ that begins with si.(5)
According to the order ofEG′, consistently visit all vertices starting from si. If a vertex sj has already been visited, then directly go to next vertex sk∈EG′ until all vertices are visited. Then, all the visited sis are put into T.(6)
LocateCHn and check whether each segment si is on CHn. If there is at least one segment, for example, sk, not on CHn, then find the edge (si,sj)∈CHn closest to sk and create the tour T′=CHn∖(si,sj)∪(si,sk)∪(sk,sj). Otherwise, let T′=CHn. Next, calculate min⁡{ω(T),ω(T′)}, and choose the corresponding tour as the data collection and aggregation tour.As shown in Figure8, there are 4 RNs and one MDC available for a set S of disjoint segments, where S={s1,s2,s3,s4,s5}. Figure 8(b) shows the weighted complete graph K5 over S. And each edge sisj∈K5 is associated with a weight value ω(sisj) that represents the minimum cost of travelling from si to sj. A mst of K5 is built in Figure 8(c). And there are only two odd-degree vertices s1,s2∈mst, so the perfect matching of K2 is s1s2. As shown in Figure 8(d), the trail E=s1s2s3s4s5s1 is the Euler closed trail of mst∪{s1s2}. Then, according to the order of E, continuingly visit all vertices starting from s1. The solid lines consist of the Hamilton cycle H=s1s2s3s4s5s1. And H is chosen as the initial data collection and aggregation tour T. It is worth mentioning that the tour T  is 2-connected and the corresponding theoretical proof is given in Section 6.1. The pseudocode for RTPP is shown in Algorithm 2.Algorithm 2:Random terrain based path planning (RTPP).
Input: A set U of n disjoint segments, U={s1,s2,…,sn} and S=∅. Output: The initial data collection and aggregation tour T′ ( 1 )  Construct Kn on U ( 2 )  foreach edge sisj∈Kn  do ( 3 )   ω(sisj)=ω(Pi,j∗) ( 4 )  end for ( 5 )  Find a minimum spanning tree mst of Kn ( 6 )  foreach odd-degree vertex si∈mst  do ( 7 )   S=S∪{si} ( 8 )  end for ( 9 )  Construct KS on S and establish a minimum weighted perfect mathing MK|S| ( 10 )  Build an Euler graph G′=MKS⋃mst ( 11 )  Draw an Euler closed trail EG′ from a randomly chosen vertex si∈G′ and record the sequence C of the trail ( 12 )   T=T∪{si} ( 13 )  repeat ( 14 )   Starts from si, visit every vertex sj∈C ( 15 )   if  sj is visited, then ( 16 )    jump to the next vertex in C ( 17 )    else ( 18 )     T=T∪sj ( 19 )    end if ( 20 )  untilall sjs are visited ( 21 )   ifall n segments are on CHn  then ( 22 )   ifω(T)≤ω(CHn)  then ( 23 )    T′=T ( 24 )   else ( 25 )     T′=CHn ( 26 )    end if ( 27 )  else ( 28 )   T∗=CHn ( 29 )   for allsks not on CHn  do ( 30 )    Find the edge (si,sj)∈CHn closest to sk ( 31 )    T∗=T∗∖(si,sj)∪(si,sk)∪(sk,sj) ( 32 )   end for ( 33 )   ifω(T)≤ω(T∗)  then ( 34 )    T′=T ( 35 )   else ( 36 )    T′=T∗ ( 37 )   end if ( 38 )  end if ( 39 )  Return T′Figure 8
Random terrain based path planning (RTPP).
(a) (b) (c) (d)


#### 5.1.2. Optimized Relay Node Deployment (ORND)

O R N D is a highly effective algorithm that aims to improve the initial data collection and aggregation tour T′ established by RTPP. Although there are only k  RNs available, ORND attempts to place RNs at the optimal positions such that a number of intersected paths are merged to reduce ω(T′) and the final data collection and aggregation tour T is built (see Figure 9). Now we introduce how ORND works:(1)
Check all paths onT and find out if there exist at least two paths, for example, Pi,j∗ and Pj,q∗, such that they have t consecutive cells in common except the cell where sj is located. That is, Pi,j∗=Psi,ct∗∪Pct,sj∗ and Pj,q∗=Psj,ct∗∪Pct,sq∗.(2)
Start to deployRNs along Pc1,ct; then, let T=T∖(Pi,j∗∪Pj,q∗).(3)
Merge pathsPi,j∗ and Pj,q∗ to reconstruct the tour T as follows:Figure 9
Two paths merged as one by Optimized Relay Node Deployment (ORND).
(a) (b)Ifk≥t, then T=T∪(Psi,ct∪Pct,sq). Otherwise, T=T∪(Psi,ck∪Pck,sq).Step (3) implies that if there exists only one pair of paths, for example, Pi,j∗ and Pj,q∗, that have t consecutive cells in common, then ω(T) can be reduced by 2ω(Pc1,ct) at most due to the merging process of ORND. More specifically, if the RNs deployed along Pc1,ct reach the cell ct, then the MDC can directly collect the data sensed by sj by simply travelling through the merged path Pi,q=Psi,ct∪Pct,sq, as shown in Figure 9, instead of travelling along paths Pi,j∗ and Pj,q∗ sequentially.In Figure10, it is obvious that although the initial tour is a Hamilton cycle H and CH5, the MDC does not have to go directly from si to sj along the path Pi,j due to the fact that there may exist at least two paths, that is, P3,4 and P4,5, that can merge as one. In addition, a common cell cx within the communication range of s4 is the only cell shared by both of P3,4∗ and P4,5∗. Thus, such two paths merge as P3,5 by deploying a RN at cell cx and all data sensed by s4 will be collected while a MDC is travelling through cx. Figure 10(b) shows the final MDC tour T, with ω(T)=6+23+10+11=50. Note that although there are sufficient RNs, only one RN is needed. This is attributed to the fact that even if more RNs are deployed, ω(T) remains the same in this example. The pseudocode for ORND is shown in Algorithm 3.Algorithm 3:Optimized Relay Node Deployment (ORND).
Input: The initial data collection and aggregation tour T′ and k  RNs. Output: The final data collection and aggregation tour T. ( 1 )  for  all paths on T  do ( 2 )   if there exist at least two paths Pi,j∗ and Pj,q∗ such that they have t consecutive cells in common except the cell wheresj is located then ( 3 )    Start to deploy RNs along Pc1,ct and do T′=T′∖(Pi,j∗∪Pj,q∗) ( 4 )    ifk≥t  then ( 5 )      T=T∪(Psi,ct∪Pct,sq) ( 6 )    else ( 7 )      T=T∪(Psi,ck∪Pck,sq) ( 8 )    end if ( 9 )    end if ( 10 )   end for ( 11 )  Return TFigure 10
An example ofHRSRT with m=1 and k=4.
(a) (b)


### 5.2. HRSRT withm>1

Form>1, the same path planning algorithm RTPP elaborated in Section 5.1.1 is employed. It takes n original disjoint segments as the input to establish a data collection and aggregation tour T. Then, we devise a new RNs deployment strategy (RND) to determine candidate positions for RNs on T such that the energy cost is minimized. Finally, a Path Allocation (PA) approach is developed to locate optimal tours for all MDCs (see Figure 11). Now we elaborate how a minimum weighted tour T is built as follows:(1)
For eachsi∈T, deploy ⌈k/2n⌉RNs along path Pi,i-1∗ and populate (⌈k/n⌉-⌈k/2n⌉)RNs along path Pi,i+1∗, where T=s1s2⋯sns1. We use symbols sil and sir to mark the latest deployed RNs along Pi,i-1∗ and Pi,i+1∗, respectively.(2)
Ifm≥n, then choose Ti=Pi,j∗∖(Psi,sir∗∪Psj,sjl∗) as the optimal tour of a MDC for all paths Pi,j∗s∈T. Otherwise, use the same way to choose optimal tours for all  (m-1)MDCs. For the last MDC, the tour Tm=⋃i=mnTi is assigned to it.(3)
For allTi, let T=T∪Ti, where i≤m.Figure 11
One path subdivided into three optimal paths byRNs deployment (RND) and Path Allocation (PA).
(a) (b)We call the strategies, described in steps(1) and (2), RND and PA, respectively. In fact, if there exists a path Pi,j∗∈T such that the RNs are deployed along Pi,j∗ as step (1), then ω(T) is reduced by ω(Psi,sir∗∪Psj,sjl∗). This is because Ti=Pi,j∗∖(Psi,sir∗∪Psj,sjl∗) is the tour allocated to a MDC, instead of Pi,j∗. Besides, all data sensed by si and sj can be collected, while both ends of the tour Ti are reached by the MDC. As shown in Figure 12(c), since P3,4∗ and P4,5∗ have a common cell cx, HRSRT with m=1 deploys a RN at cx. The reason for HRSRT with m>1 deploying a RN at the same location is that s4l and s4r refer to the same cell cx for paths P3,4∗ and P4,5∗, respectively. Figures 12(b) and 12(d) represent final data collection and aggregation tours T and T′ of HRSRT for m=1 and m=2, respectively. It is obvious that T′ is established with less weight than T. That is, ω(T′)=11+16=27<ω(T)=6+23+10+11=50.Figure 12
H R S R T with m=2 and k=4 versus HRSRT with m=1 and k=4.
(a) (b) (c) (d)It is worth mentioning thatHRSRT adopts different strategies based on different values of m. The rationale is that if HRSRT employs RTPP, RND, and PA sequentially with only one MDC available, then the MDC still needs to tour around the entire set of segments to collect data along the same path. That implies the RNs deployment incurs no reduction in energy cost. Unlike RND and PA, ORND is designed to merge intersected paths into one through deploying RNs at optimal positions such that the weight of T is minimized, regardless of how many MDCs are available. Thus, ORND is an ideal choice for the single MDC case. The pseudocode for HRSRT with m>1 is shown in Algorithm 4.Algorithm 4:HRSRT with m>1.
Input: A set S of n disjoint segments, S={S1,S2,…,Sn}. Output: A data collection and aggregation tour T. ( 1 )  T=RTPP(S). ( 2 )  for each Si∈T  do ( 3 )   Deploy k/2n  RNs along path Pi,i-1∗ and mark the last deployed RN  Sil ( 4 )   Deploy (k/n-k/2n)  RNs along path Pi,i+1∗ and mark the last deployed RN  Sir ( 5 )  end for ( 6 )  if  m≥n  then ( 7 )   for  all  Pi,j∗s∈T  do ( 8 )    Choose Ti=Pi,j∗∖(PSi,Sir∗∪PSj,Sjl∗) as a MDC tour ( 9 )   end  for ( 10 )  else ( 11 )   for  all  (m-1)  Pi,j∗s∈T  do ( 12 )    Choose Ti=Pi,j∗∖(PSi,Sir∗∪PSj,Sjl∗) as a MDC tour ( 13 )   end  for ( 14 )   Choose Tm=⋃i=mnTi as a MDC tour for the last MDC ( 15 )  end  if ( 16 )  for  all  Tis do ( 17 )   T=T∪Ti ( 18 )  end  for


### 5.3. Distributed Implementation

This section describes howHRSRT is implemented in a distributed manner. When the network is partitioned into n disjoint segments, each segment si first chooses a sensor as its representative ri and then broadcasts its location ci. We assume that there are some mobile agents in this network. These mobile agents will be sent to those segments that lost contacts based on their original positions. Eventually, all ris share each other’s cis after mobile agents return. Each ri calculates the coordinate of the CoM of SPn using (6) [27]. Note that cx and cy are coordinates of the CoM, where xi and yi are coordinates of the segment si.(6)AreaA=12∑i=0n-1xiyi+1-xi+1yi,cx=16A∑i=0n-1xi+xi+1xiyi+1-xi+1yi,cy=16A∑i=0n-1yi+yi+1xiyi+1-xi+1yi.Then,ri starts to populate relays toward CoM. Note that each RN placed by ri will become new representative of si. While two or more ris are within each other’s communication range, the corresponding si’s merge as a new segment and the closest ri to the CoM is chosen as the representative of such a newly established segment. Then, rj’s (where i≠j) will stop to deploy RNs toward the CoM. Each ri will recursively deploy relays until all RNs assigned to it are placed.The path planning is followed by theRNs deployment. Since the position of the CoM is calculated by each ri, final positions of each segment, for example, ri′s, are known by ri. Then, all L(ri′,rj′)’s are calculated and stored in the database D in increasing order, where i≠j. Next, the shortest ri′rj′s are iteratively added to the data collection and aggregation tour T, which does not create a cycle, unless it completes the tour. Note that if the number of mobile data collectors Nm is sufficient, then each segment is assigned a MDC. Otherwise, only n segments are assigned MDCs, where n<Nm. Finally, each MDC tours around all existing disjoint segments along T to collect and aggregate data (see Figure 13). The pseudocode for the distributed HRSRT is shown in Algorithm 5.Algorithm 5:Distributed HRSRT.
Input: A set S of n disjoint segments, S={s1,s2,…,sn}. Output: A data collection circuit T. ( 1 )  for each si∈S  do ( 2 )   randomly choose a sensor as the representative ri ( 3 )   sends a mobile agent to locate sjs, where i≠j ( 4 )   calculate the coordinate of the CoM of  SPn ( 5 )  end for ( 6 )  repeat ( 7 )   ri place a RN toward the CoM and let this RN as a new ri to represent si ( 8 )   if there are k  ris that meet each other, then ( 9 )    they merge as one and choose the ri closest to other rjs as the representative ( 10 )   end if ( 11 )   Update the list of disjoint segments ( 12 )  until (All RNs assigned to each si are populated.) ( 13 )  for each pair of remaining disjoint segments ri′ and rj′  do ( 14 )   calculate L(ri′,rj′) and store it in the database D in increasing order ( 15 )  end for ( 16 )  while  T is not a circuit do ( 17 )   Get the first element L(ri′,rj′) in D. ( 18 )   if  ri′rj′ does not form a cycle, unless it completes the circuit  T  then ( 19 )    add ri′rj′ to T ( 20 )   end if ( 21 )   end while ( 22 )  Return T.Figure 13
A distributedHRSRT.


## 5.1. HRSRT withm=1

Form=1, HRSRT works in two phases. First, a random terrain based path planning (RTPP) is implemented to initiate a connectivity restoration tour T in phase one. Then, an Optimized Relay Node Deployment (ORND) is adopted to reduce ω(T) in phase two. The pseudocode for HRSRT with m=1 is shown in Algorithm 1.Algorithm 1:HRSRT with m=1.
Input: A set S of n disjoint segments, S={S1,S2,…,Sn}. Output: A data collection and aggregation tour T. ( 1 ) T′=RTPP(S). ( 2 )  T=ORND(T′). ( 3 )  Return T.


### 5.1.1. Random Terrain Based Path Planning (RTPP)

As we explained above, various terrains have significant influences on the cost of data collection and aggregation forMDCs. To quantify such influences, the cost for travelling through a unit area(cell) is represented by a weight value. Therefore, the priority of a path planning strategy on realistic terrains is to establish a tour of minimum weight for MDCs. In this section, a random terrain based path planning strategy, called RTPP, is proposed to accomplish the goal under the constrain that only m  MDCs are available.Suppose there aren disjoint segments. We take six steps to build a minimum weighted tour T′ as follows:(1)
According to the weight of each unit area, construct a complete weighted graphKn over the set of segments remaining disjoint. Each edge of Kn, for example, sisj∈Kn, is the minimum weighted path from si to sj, that is, Pi,j∗. Note that if there are several Pi,j∗s, then choose Pi,j∗ with the shortest Manhattan Distance between si and sj. The rationale is that the MDC movement toward an adjacent cell is in one of four directions as we mentioned above.(2)
Discover a minimum spanning tree (mst) of Kn.(3)
Find the setS of odd-degree vertices in mst; that is, S={si∣si∈mst,d(si)isodd}. Construct K|S|, an introduced graph of Kn, to establish a minimum weighted perfect math MK|S|. Then, initiate an Euler graph G′=MK|S|⋃mst.(4)
Randomly choose a vertexsi∈G′ and draw an Euler closed trail EG′ that begins with si.(5)
According to the order ofEG′, consistently visit all vertices starting from si. If a vertex sj has already been visited, then directly go to next vertex sk∈EG′ until all vertices are visited. Then, all the visited sis are put into T.(6)
LocateCHn and check whether each segment si is on CHn. If there is at least one segment, for example, sk, not on CHn, then find the edge (si,sj)∈CHn closest to sk and create the tour T′=CHn∖(si,sj)∪(si,sk)∪(sk,sj). Otherwise, let T′=CHn. Next, calculate min⁡{ω(T),ω(T′)}, and choose the corresponding tour as the data collection and aggregation tour.As shown in Figure8, there are 4 RNs and one MDC available for a set S of disjoint segments, where S={s1,s2,s3,s4,s5}. Figure 8(b) shows the weighted complete graph K5 over S. And each edge sisj∈K5 is associated with a weight value ω(sisj) that represents the minimum cost of travelling from si to sj. A mst of K5 is built in Figure 8(c). And there are only two odd-degree vertices s1,s2∈mst, so the perfect matching of K2 is s1s2. As shown in Figure 8(d), the trail E=s1s2s3s4s5s1 is the Euler closed trail of mst∪{s1s2}. Then, according to the order of E, continuingly visit all vertices starting from s1. The solid lines consist of the Hamilton cycle H=s1s2s3s4s5s1. And H is chosen as the initial data collection and aggregation tour T. It is worth mentioning that the tour T  is 2-connected and the corresponding theoretical proof is given in Section 6.1. The pseudocode for RTPP is shown in Algorithm 2.Algorithm 2:Random terrain based path planning (RTPP).
Input: A set U of n disjoint segments, U={s1,s2,…,sn} and S=∅. Output: The initial data collection and aggregation tour T′ ( 1 )  Construct Kn on U ( 2 )  foreach edge sisj∈Kn  do ( 3 )   ω(sisj)=ω(Pi,j∗) ( 4 )  end for ( 5 )  Find a minimum spanning tree mst of Kn ( 6 )  foreach odd-degree vertex si∈mst  do ( 7 )   S=S∪{si} ( 8 )  end for ( 9 )  Construct KS on S and establish a minimum weighted perfect mathing MK|S| ( 10 )  Build an Euler graph G′=MKS⋃mst ( 11 )  Draw an Euler closed trail EG′ from a randomly chosen vertex si∈G′ and record the sequence C of the trail ( 12 )   T=T∪{si} ( 13 )  repeat ( 14 )   Starts from si, visit every vertex sj∈C ( 15 )   if  sj is visited, then ( 16 )    jump to the next vertex in C ( 17 )    else ( 18 )     T=T∪sj ( 19 )    end if ( 20 )  untilall sjs are visited ( 21 )   ifall n segments are on CHn  then ( 22 )   ifω(T)≤ω(CHn)  then ( 23 )    T′=T ( 24 )   else ( 25 )     T′=CHn ( 26 )    end if ( 27 )  else ( 28 )   T∗=CHn ( 29 )   for allsks not on CHn  do ( 30 )    Find the edge (si,sj)∈CHn closest to sk ( 31 )    T∗=T∗∖(si,sj)∪(si,sk)∪(sk,sj) ( 32 )   end for ( 33 )   ifω(T)≤ω(T∗)  then ( 34 )    T′=T ( 35 )   else ( 36 )    T′=T∗ ( 37 )   end if ( 38 )  end if ( 39 )  Return T′Figure 8
Random terrain based path planning (RTPP).
(a) (b) (c) (d)


### 5.1.2. Optimized Relay Node Deployment (ORND)

O R N D is a highly effective algorithm that aims to improve the initial data collection and aggregation tour T′ established by RTPP. Although there are only k  RNs available, ORND attempts to place RNs at the optimal positions such that a number of intersected paths are merged to reduce ω(T′) and the final data collection and aggregation tour T is built (see Figure 9). Now we introduce how ORND works:(1)
Check all paths onT and find out if there exist at least two paths, for example, Pi,j∗ and Pj,q∗, such that they have t consecutive cells in common except the cell where sj is located. That is, Pi,j∗=Psi,ct∗∪Pct,sj∗ and Pj,q∗=Psj,ct∗∪Pct,sq∗.(2)
Start to deployRNs along Pc1,ct; then, let T=T∖(Pi,j∗∪Pj,q∗).(3)
Merge pathsPi,j∗ and Pj,q∗ to reconstruct the tour T as follows:Figure 9
Two paths merged as one by Optimized Relay Node Deployment (ORND).
(a) (b)Ifk≥t, then T=T∪(Psi,ct∪Pct,sq). Otherwise, T=T∪(Psi,ck∪Pck,sq).Step (3) implies that if there exists only one pair of paths, for example, Pi,j∗ and Pj,q∗, that have t consecutive cells in common, then ω(T) can be reduced by 2ω(Pc1,ct) at most due to the merging process of ORND. More specifically, if the RNs deployed along Pc1,ct reach the cell ct, then the MDC can directly collect the data sensed by sj by simply travelling through the merged path Pi,q=Psi,ct∪Pct,sq, as shown in Figure 9, instead of travelling along paths Pi,j∗ and Pj,q∗ sequentially.In Figure10, it is obvious that although the initial tour is a Hamilton cycle H and CH5, the MDC does not have to go directly from si to sj along the path Pi,j due to the fact that there may exist at least two paths, that is, P3,4 and P4,5, that can merge as one. In addition, a common cell cx within the communication range of s4 is the only cell shared by both of P3,4∗ and P4,5∗. Thus, such two paths merge as P3,5 by deploying a RN at cell cx and all data sensed by s4 will be collected while a MDC is travelling through cx. Figure 10(b) shows the final MDC tour T, with ω(T)=6+23+10+11=50. Note that although there are sufficient RNs, only one RN is needed. This is attributed to the fact that even if more RNs are deployed, ω(T) remains the same in this example. The pseudocode for ORND is shown in Algorithm 3.Algorithm 3:Optimized Relay Node Deployment (ORND).
Input: The initial data collection and aggregation tour T′ and k  RNs. Output: The final data collection and aggregation tour T. ( 1 )  for  all paths on T  do ( 2 )   if there exist at least two paths Pi,j∗ and Pj,q∗ such that they have t consecutive cells in common except the cell wheresj is located then ( 3 )    Start to deploy RNs along Pc1,ct and do T′=T′∖(Pi,j∗∪Pj,q∗) ( 4 )    ifk≥t  then ( 5 )      T=T∪(Psi,ct∪Pct,sq) ( 6 )    else ( 7 )      T=T∪(Psi,ck∪Pck,sq) ( 8 )    end if ( 9 )    end if ( 10 )   end for ( 11 )  Return TFigure 10
An example ofHRSRT with m=1 and k=4.
(a) (b)


## 5.1.1. Random Terrain Based Path Planning (RTPP)

As we explained above, various terrains have significant influences on the cost of data collection and aggregation forMDCs. To quantify such influences, the cost for travelling through a unit area(cell) is represented by a weight value. Therefore, the priority of a path planning strategy on realistic terrains is to establish a tour of minimum weight for MDCs. In this section, a random terrain based path planning strategy, called RTPP, is proposed to accomplish the goal under the constrain that only m  MDCs are available.Suppose there aren disjoint segments. We take six steps to build a minimum weighted tour T′ as follows:(1)
According to the weight of each unit area, construct a complete weighted graphKn over the set of segments remaining disjoint. Each edge of Kn, for example, sisj∈Kn, is the minimum weighted path from si to sj, that is, Pi,j∗. Note that if there are several Pi,j∗s, then choose Pi,j∗ with the shortest Manhattan Distance between si and sj. The rationale is that the MDC movement toward an adjacent cell is in one of four directions as we mentioned above.(2)
Discover a minimum spanning tree (mst) of Kn.(3)
Find the setS of odd-degree vertices in mst; that is, S={si∣si∈mst,d(si)isodd}. Construct K|S|, an introduced graph of Kn, to establish a minimum weighted perfect math MK|S|. Then, initiate an Euler graph G′=MK|S|⋃mst.(4)
Randomly choose a vertexsi∈G′ and draw an Euler closed trail EG′ that begins with si.(5)
According to the order ofEG′, consistently visit all vertices starting from si. If a vertex sj has already been visited, then directly go to next vertex sk∈EG′ until all vertices are visited. Then, all the visited sis are put into T.(6)
LocateCHn and check whether each segment si is on CHn. If there is at least one segment, for example, sk, not on CHn, then find the edge (si,sj)∈CHn closest to sk and create the tour T′=CHn∖(si,sj)∪(si,sk)∪(sk,sj). Otherwise, let T′=CHn. Next, calculate min⁡{ω(T),ω(T′)}, and choose the corresponding tour as the data collection and aggregation tour.As shown in Figure8, there are 4 RNs and one MDC available for a set S of disjoint segments, where S={s1,s2,s3,s4,s5}. Figure 8(b) shows the weighted complete graph K5 over S. And each edge sisj∈K5 is associated with a weight value ω(sisj) that represents the minimum cost of travelling from si to sj. A mst of K5 is built in Figure 8(c). And there are only two odd-degree vertices s1,s2∈mst, so the perfect matching of K2 is s1s2. As shown in Figure 8(d), the trail E=s1s2s3s4s5s1 is the Euler closed trail of mst∪{s1s2}. Then, according to the order of E, continuingly visit all vertices starting from s1. The solid lines consist of the Hamilton cycle H=s1s2s3s4s5s1. And H is chosen as the initial data collection and aggregation tour T. It is worth mentioning that the tour T  is 2-connected and the corresponding theoretical proof is given in Section 6.1. The pseudocode for RTPP is shown in Algorithm 2.Algorithm 2:Random terrain based path planning (RTPP).
Input: A set U of n disjoint segments, U={s1,s2,…,sn} and S=∅. Output: The initial data collection and aggregation tour T′ ( 1 )  Construct Kn on U ( 2 )  foreach edge sisj∈Kn  do ( 3 )   ω(sisj)=ω(Pi,j∗) ( 4 )  end for ( 5 )  Find a minimum spanning tree mst of Kn ( 6 )  foreach odd-degree vertex si∈mst  do ( 7 )   S=S∪{si} ( 8 )  end for ( 9 )  Construct KS on S and establish a minimum weighted perfect mathing MK|S| ( 10 )  Build an Euler graph G′=MKS⋃mst ( 11 )  Draw an Euler closed trail EG′ from a randomly chosen vertex si∈G′ and record the sequence C of the trail ( 12 )   T=T∪{si} ( 13 )  repeat ( 14 )   Starts from si, visit every vertex sj∈C ( 15 )   if  sj is visited, then ( 16 )    jump to the next vertex in C ( 17 )    else ( 18 )     T=T∪sj ( 19 )    end if ( 20 )  untilall sjs are visited ( 21 )   ifall n segments are on CHn  then ( 22 )   ifω(T)≤ω(CHn)  then ( 23 )    T′=T ( 24 )   else ( 25 )     T′=CHn ( 26 )    end if ( 27 )  else ( 28 )   T∗=CHn ( 29 )   for allsks not on CHn  do ( 30 )    Find the edge (si,sj)∈CHn closest to sk ( 31 )    T∗=T∗∖(si,sj)∪(si,sk)∪(sk,sj) ( 32 )   end for ( 33 )   ifω(T)≤ω(T∗)  then ( 34 )    T′=T ( 35 )   else ( 36 )    T′=T∗ ( 37 )   end if ( 38 )  end if ( 39 )  Return T′Figure 8
Random terrain based path planning (RTPP).
(a) (b) (c) (d)


## 5.1.2. Optimized Relay Node Deployment (ORND)

O R N D is a highly effective algorithm that aims to improve the initial data collection and aggregation tour T′ established by RTPP. Although there are only k  RNs available, ORND attempts to place RNs at the optimal positions such that a number of intersected paths are merged to reduce ω(T′) and the final data collection and aggregation tour T is built (see Figure 9). Now we introduce how ORND works:(1)
Check all paths onT and find out if there exist at least two paths, for example, Pi,j∗ and Pj,q∗, such that they have t consecutive cells in common except the cell where sj is located. That is, Pi,j∗=Psi,ct∗∪Pct,sj∗ and Pj,q∗=Psj,ct∗∪Pct,sq∗.(2)
Start to deployRNs along Pc1,ct; then, let T=T∖(Pi,j∗∪Pj,q∗).(3)
Merge pathsPi,j∗ and Pj,q∗ to reconstruct the tour T as follows:Figure 9
Two paths merged as one by Optimized Relay Node Deployment (ORND).
(a) (b)Ifk≥t, then T=T∪(Psi,ct∪Pct,sq). Otherwise, T=T∪(Psi,ck∪Pck,sq).Step (3) implies that if there exists only one pair of paths, for example, Pi,j∗ and Pj,q∗, that have t consecutive cells in common, then ω(T) can be reduced by 2ω(Pc1,ct) at most due to the merging process of ORND. More specifically, if the RNs deployed along Pc1,ct reach the cell ct, then the MDC can directly collect the data sensed by sj by simply travelling through the merged path Pi,q=Psi,ct∪Pct,sq, as shown in Figure 9, instead of travelling along paths Pi,j∗ and Pj,q∗ sequentially.In Figure10, it is obvious that although the initial tour is a Hamilton cycle H and CH5, the MDC does not have to go directly from si to sj along the path Pi,j due to the fact that there may exist at least two paths, that is, P3,4 and P4,5, that can merge as one. In addition, a common cell cx within the communication range of s4 is the only cell shared by both of P3,4∗ and P4,5∗. Thus, such two paths merge as P3,5 by deploying a RN at cell cx and all data sensed by s4 will be collected while a MDC is travelling through cx. Figure 10(b) shows the final MDC tour T, with ω(T)=6+23+10+11=50. Note that although there are sufficient RNs, only one RN is needed. This is attributed to the fact that even if more RNs are deployed, ω(T) remains the same in this example. The pseudocode for ORND is shown in Algorithm 3.Algorithm 3:Optimized Relay Node Deployment (ORND).
Input: The initial data collection and aggregation tour T′ and k  RNs. Output: The final data collection and aggregation tour T. ( 1 )  for  all paths on T  do ( 2 )   if there exist at least two paths Pi,j∗ and Pj,q∗ such that they have t consecutive cells in common except the cell wheresj is located then ( 3 )    Start to deploy RNs along Pc1,ct and do T′=T′∖(Pi,j∗∪Pj,q∗) ( 4 )    ifk≥t  then ( 5 )      T=T∪(Psi,ct∪Pct,sq) ( 6 )    else ( 7 )      T=T∪(Psi,ck∪Pck,sq) ( 8 )    end if ( 9 )    end if ( 10 )   end for ( 11 )  Return TFigure 10
An example ofHRSRT with m=1 and k=4.
(a) (b)


## 5.2. HRSRT withm>1

Form>1, the same path planning algorithm RTPP elaborated in Section 5.1.1 is employed. It takes n original disjoint segments as the input to establish a data collection and aggregation tour T. Then, we devise a new RNs deployment strategy (RND) to determine candidate positions for RNs on T such that the energy cost is minimized. Finally, a Path Allocation (PA) approach is developed to locate optimal tours for all MDCs (see Figure 11). Now we elaborate how a minimum weighted tour T is built as follows:(1)
For eachsi∈T, deploy ⌈k/2n⌉RNs along path Pi,i-1∗ and populate (⌈k/n⌉-⌈k/2n⌉)RNs along path Pi,i+1∗, where T=s1s2⋯sns1. We use symbols sil and sir to mark the latest deployed RNs along Pi,i-1∗ and Pi,i+1∗, respectively.(2)
Ifm≥n, then choose Ti=Pi,j∗∖(Psi,sir∗∪Psj,sjl∗) as the optimal tour of a MDC for all paths Pi,j∗s∈T. Otherwise, use the same way to choose optimal tours for all  (m-1)MDCs. For the last MDC, the tour Tm=⋃i=mnTi is assigned to it.(3)
For allTi, let T=T∪Ti, where i≤m.Figure 11
One path subdivided into three optimal paths byRNs deployment (RND) and Path Allocation (PA).
(a) (b)We call the strategies, described in steps(1) and (2), RND and PA, respectively. In fact, if there exists a path Pi,j∗∈T such that the RNs are deployed along Pi,j∗ as step (1), then ω(T) is reduced by ω(Psi,sir∗∪Psj,sjl∗). This is because Ti=Pi,j∗∖(Psi,sir∗∪Psj,sjl∗) is the tour allocated to a MDC, instead of Pi,j∗. Besides, all data sensed by si and sj can be collected, while both ends of the tour Ti are reached by the MDC. As shown in Figure 12(c), since P3,4∗ and P4,5∗ have a common cell cx, HRSRT with m=1 deploys a RN at cx. The reason for HRSRT with m>1 deploying a RN at the same location is that s4l and s4r refer to the same cell cx for paths P3,4∗ and P4,5∗, respectively. Figures 12(b) and 12(d) represent final data collection and aggregation tours T and T′ of HRSRT for m=1 and m=2, respectively. It is obvious that T′ is established with less weight than T. That is, ω(T′)=11+16=27<ω(T)=6+23+10+11=50.Figure 12
H R S R T with m=2 and k=4 versus HRSRT with m=1 and k=4.
(a) (b) (c) (d)It is worth mentioning thatHRSRT adopts different strategies based on different values of m. The rationale is that if HRSRT employs RTPP, RND, and PA sequentially with only one MDC available, then the MDC still needs to tour around the entire set of segments to collect data along the same path. That implies the RNs deployment incurs no reduction in energy cost. Unlike RND and PA, ORND is designed to merge intersected paths into one through deploying RNs at optimal positions such that the weight of T is minimized, regardless of how many MDCs are available. Thus, ORND is an ideal choice for the single MDC case. The pseudocode for HRSRT with m>1 is shown in Algorithm 4.Algorithm 4:HRSRT with m>1.
Input: A set S of n disjoint segments, S={S1,S2,…,Sn}. Output: A data collection and aggregation tour T. ( 1 )  T=RTPP(S). ( 2 )  for each Si∈T  do ( 3 )   Deploy k/2n  RNs along path Pi,i-1∗ and mark the last deployed RN  Sil ( 4 )   Deploy (k/n-k/2n)  RNs along path Pi,i+1∗ and mark the last deployed RN  Sir ( 5 )  end for ( 6 )  if  m≥n  then ( 7 )   for  all  Pi,j∗s∈T  do ( 8 )    Choose Ti=Pi,j∗∖(PSi,Sir∗∪PSj,Sjl∗) as a MDC tour ( 9 )   end  for ( 10 )  else ( 11 )   for  all  (m-1)  Pi,j∗s∈T  do ( 12 )    Choose Ti=Pi,j∗∖(PSi,Sir∗∪PSj,Sjl∗) as a MDC tour ( 13 )   end  for ( 14 )   Choose Tm=⋃i=mnTi as a MDC tour for the last MDC ( 15 )  end  if ( 16 )  for  all  Tis do ( 17 )   T=T∪Ti ( 18 )  end  for


## 5.3. Distributed Implementation

This section describes howHRSRT is implemented in a distributed manner. When the network is partitioned into n disjoint segments, each segment si first chooses a sensor as its representative ri and then broadcasts its location ci. We assume that there are some mobile agents in this network. These mobile agents will be sent to those segments that lost contacts based on their original positions. Eventually, all ris share each other’s cis after mobile agents return. Each ri calculates the coordinate of the CoM of SPn using (6) [27]. Note that cx and cy are coordinates of the CoM, where xi and yi are coordinates of the segment si.(6)AreaA=12∑i=0n-1xiyi+1-xi+1yi,cx=16A∑i=0n-1xi+xi+1xiyi+1-xi+1yi,cy=16A∑i=0n-1yi+yi+1xiyi+1-xi+1yi.Then,ri starts to populate relays toward CoM. Note that each RN placed by ri will become new representative of si. While two or more ris are within each other’s communication range, the corresponding si’s merge as a new segment and the closest ri to the CoM is chosen as the representative of such a newly established segment. Then, rj’s (where i≠j) will stop to deploy RNs toward the CoM. Each ri will recursively deploy relays until all RNs assigned to it are placed.The path planning is followed by theRNs deployment. Since the position of the CoM is calculated by each ri, final positions of each segment, for example, ri′s, are known by ri. Then, all L(ri′,rj′)’s are calculated and stored in the database D in increasing order, where i≠j. Next, the shortest ri′rj′s are iteratively added to the data collection and aggregation tour T, which does not create a cycle, unless it completes the tour. Note that if the number of mobile data collectors Nm is sufficient, then each segment is assigned a MDC. Otherwise, only n segments are assigned MDCs, where n<Nm. Finally, each MDC tours around all existing disjoint segments along T to collect and aggregate data (see Figure 13). The pseudocode for the distributed HRSRT is shown in Algorithm 5.Algorithm 5:Distributed HRSRT.
Input: A set S of n disjoint segments, S={s1,s2,…,sn}. Output: A data collection circuit T. ( 1 )  for each si∈S  do ( 2 )   randomly choose a sensor as the representative ri ( 3 )   sends a mobile agent to locate sjs, where i≠j ( 4 )   calculate the coordinate of the CoM of  SPn ( 5 )  end for ( 6 )  repeat ( 7 )   ri place a RN toward the CoM and let this RN as a new ri to represent si ( 8 )   if there are k  ris that meet each other, then ( 9 )    they merge as one and choose the ri closest to other rjs as the representative ( 10 )   end if ( 11 )   Update the list of disjoint segments ( 12 )  until (All RNs assigned to each si are populated.) ( 13 )  for each pair of remaining disjoint segments ri′ and rj′  do ( 14 )   calculate L(ri′,rj′) and store it in the database D in increasing order ( 15 )  end for ( 16 )  while  T is not a circuit do ( 17 )   Get the first element L(ri′,rj′) in D. ( 18 )   if  ri′rj′ does not form a cycle, unless it completes the circuit  T  then ( 19 )    add ri′rj′ to T ( 20 )   end if ( 21 )   end while ( 22 )  Return T.Figure 13
A distributedHRSRT.


## 6. Performance Evaluation

### 6.1. Theoretical Analysis

The correctness, complexity, and approximation ratio ofHRSRT are analyzed in this subsection. First we give the following theorems.Theorem 8.
All paths of a data collection and aggregation tour established by RTPP satisfy WTI.Proof.
We prove this theorem by contradiction. Suppose there are three pathsPi,j, Pi,k, and Pj,k, for a MDC travelling among three segments si, sj, and sk, such that ω(Pi,j∗)+ω(Pj,k∗)<ω(Pi,k∗). That implies that the cost of directly travelling from si to sk is higher than travelling from si to sk via sj, which contradicts the fact that RTPP only chooses minimum weighted paths for MDCs. Therefore, Pi,k∗ should start from si and end at sk via sj. That implies ω(Pi,j∗)+ω(Pj,k∗)≥ω(Pi,k∗). So the theorem holds.As shown in Figure14, we have ω(P1,2)=1, ω(P2,3)=2, and ω(P1,3)=4. Therefore, the proper choice for travelling from s1 to s3 is via s2. That makes ω(P1,3)=3.Figure 14
The example of weighted triangle rule.
(a) (b) (c)To illustrate the following theorem clearly, we call a pathPi,j a direct path, if there is no segment on Pi,j other than si and sj.Theorem 9.
The tours constructed by RTPP is either a Hamilton cycle or a closed trail.Proof.
RTPP strives to locate the minimum weighted closed trail of a complete weighted graphKn. Without loss of generality, we set T=s1s2⋯sns1 a minimum weighted closed trail. Note that each edge sisj∈mwct is a Pi,j∗, which represents the minimum weighted path from si to sj. Then, we are going to distinguish between two cases to prove this theorem.
If all edges ofT are direct paths such that each segment si is on T exactly once for any i, then, according to Definition 2, T is a minimum weighted Hamilton cycle (see Figure 3).
If there is at least a path not a direct path, that is,Pi,j∗∈T is not a direct path, then it is easy to verify that T is a closed trail. We assume that the path Pi,j∗ starts from si and ends at sj via sk. According to algorithm RTPP, there may exist two other paths Pi,k∗ and Pk,j∗ to complete the trail T, such that Pi,j∗≠Pi,k∗∪Pk,j∗. Intuitively, sk is on T at least twice, which implies T is a closed trail (see Figure 2).Theorem 10.
The weighted complete graphK|S| established by RTPP consists of 2k vertices.Proof.
RTPP employs an introduced graph of a complete weighted graphK|S| to construct a perfect matching MK|S|. When the mst of Kn is built, the set S of odd-degree vertices are employed to construct K|S| for the establishment of a perfect matching. For simplicity, let e=|S|-1 denote the number of edges of mst. Intuitively, the overall degrees of |S| vertices in mst is even, because of the fact [26] ∑i=1nd(vi)=2e, where vi∈mst. It is easy to deduce that |S| is even.For the rest of the paper, we useK2k to represent graph K|S|.Note that a series ofMDC based connectivity recovery algorithms, such as MiMSI [12], IDM-kMDC [10], and MINDS [21], make MDCs travel along the convex hulk of n disjoint segments. Specifically, if there is at least one segment not on CHn, then n segments will be clustered into several disjoint groups so that each group U can form a convex hulk CH|U| with each segment of U on it. For simplicity, we call such algorithms A-CHns. And we call the tour along the convex hulk of n disjoint segment a CHn tour.Theorem 11.
HRSRT establishes a data collection and aggregation tour with less energy cost thanA-CHns.Proof.
LetT and T′ denote the tours established by the RTPP and a A-CHn, respectively. According to RTPP, the selection of perfect matchings of K2k could result in two different types of tours. That is, T is either a CHn tour or a non-CHn tour. We distinguish the following two cases to prove that the energy cost of tour T, Cost(T), is less than that of T′, Cost(T′), regardless of the number m of MDCs.
Case 1 ( T is a non- C H n tour). If there is at least one segment not on CHn, then T′ is a directed graph with either one of the following two structures. One is that a graph consists of at least two connected components bridged with two directed paths. The other is composed of at least two subtours that share a common vertex. We thus take Figure 15 as an example to explicate this case. Let the tour in Figure 15(d) represent T and two tours, for example, T1′ and T1′, in Figures 15(b) and 15(c) represent two types of T′s, respectively. According to Theorem 8, we have ω(P2,3∗)+ω(P3,5∗)≥ω(P2,5∗) and ω(P2,5∗)+ω(P5,1∗)≥ω(P2,1∗). That implies ω(T1′)≥ω(T2′)≥ω(T). According to (5), it is intuitive that Cost(T)≤Cost(T′).
If alln segments are on CHn, then it is easy to get T′=CHn. According to the tour selection of RTPP, we have ω(T)≤ω(CHn)=ω(T′), because T is a non-CHn tour. Again, (5) guarantees that Cost(T)≤Cost(T′).
Case 2 ( T is a C H n tour and all n segments are on C H n ). It is easy to get ω(T)≤ω(T′), since each edge sisj∈T is the minimum weighted path from si to sj, while the edge sisj∈T′ is a straight line directly from si to sj regardless of terrain influences. As shown in Figure 16, it is clear that ω(T)=5+6+9+6+10+5+3+2=46<ω(T′)=5+6+9+6+10+15=51. According to (5), it is intuitive that Cost(T)≤Cost(T′).Figure 15
H R S R T versus A-CHn.
(a) (b) (c) (d)Figure 16
Straight line paths versus minimum weighted paths.
(a) (b) (c)Theorem 12.
RTPP establishes a close trailH′, the weight of which is less than 1.5 times that of the least weight Hamilton cycle H∗.Proof.
Without loss of generality, we assume the close trail established byRTPP is a Hamilton cycle. For simplicity, let M2k represent the perfect matching of graph K2k. Then, the theoretical proof on the approximation ratio of ω(H′) to ω(H∗) is as follows.
First, we sett the minimum spanning tree of a weighted complete graph Kn. Let t′ represent the introduced graph of Hn-{e}, where e denotes an edge of t. Obviously, t′ is still a spanning tree of Kn such that ω(t′)>ω(t). That implies ω(Hn)>ω(t), because of ω(e)>0.
Second, obviouslyK2k is an introduced graph of Kn, where 2k<n. Suppose H2k=s1s2⋯s2ks1 and Hn=s1s2⋯sns1 represent the minimum weighted Hamilton cycles of H2k and Hn, respectively. Without loss of generality, we assume that at least one edge of H2k is not in Hn; for example, s2ks1∉Hn. According to Definition 6 and Theorem 8, we have ω(P2k,1)≥ω(s2ks1), where P2k,1=s2ks2k+1⋯s1. Intuitively, ω(H2k)≤ω(Hn). As shown in Figure 17, we have H6=s1s2s3s4s5s6s1 and H4=s2s3s4s6s2 such that ω(H4)=14<ω(H6)=16. And it also holds for the case that there are more than two edges of K2k not in Kn.
Third, by carefully choosing the edges fromH2k, we can find a minimum weighted M2k such that ω(M2k)≤(1/2)ω(H2k). As shown in Figure 18, we have H4=s1s3s2s4s1 and M4={s1s4,s2s3} such that ω(H4)=6<(1/2)ω(H4)=13.
Finally, letE be an Euler closed trail of T∪M2k established by RTPP. According to Theorem 8, the weights of all paths established by RTPP satisfy WTI. That is, ω(sisj)+ω(sjsk)≥ω(sisk), for every three segments si,sj,sk∈Kn. In addition, a path of k consecutively adjacent edges in E could be replaced by one edge that directly connects two end points of that path during the construction of H′. By recursively taking such steps, H′ is built. Hence, ω(H′)≤ω(E).
Summing up all four steps above, the theorem holds because the following inequation holds:(7)ωH′≤ωE=ωt+ωM2k<ωH∗+12ωH∗=32ω∗.Figure 17
The graphH2k.Figure 18
The perfect matching ofH4.
(a) (b) (c) (d)Theorem 13.
The data collection and aggregation tour construct by HRSRT is 2-connected.Proof.
We distinguish between two cases to prove this theorem.
Case 1 ( m = 1 ). HRSRT adopts RTPP first to calculate a minimum weight Hamilton cycle T as the connectivity restoration tour. Theorem 9 proves that T is either a Hamilton cycle or a closed trail. According to Definitions 3 and 7, it is intuitive that T is 2-connected. Then, ORND is employed to merge any pair of intersected paths Pi,j∗,Pj,k∗∈T so that T=T∖{Pi,j∗,Pj,k∗}∪{Pi,k∗} through RNs deployment. It is easy to verify the fact that there still exist 2 mutually independent paths which implies the biconnectivity of tour T. As shown in Figure 19, there exist C42 pairs of independent paths between any pair of segments. Even if a path is cut off, that is, P1,4 is disconnected, S1 and S4 are still connected via S2 and S3.
Case 2 ( m > 1 ). Similar to Case 1, RTPP is responsible for establishing a 2-connected tour T. Then, for each path Pi,j, RND deploys RNs to build subtour Ti=Pi,j∗∖(PSi,Sir∗∪PSj,Sjl∗). And Ti is assigned to a MDC by PA. It is obvious that T is still 2-connected.
Summing up the two cases above, it is easy to deduce that the data collection and aggregation tour construct byHRSRT is 2-connected.Figure 19
The example of 2-connectivity.
(a) (b)Theorem 14.
The approximation ratio of HRSRT is1.5.Proof.
We distinguish between two cases to prove this theorem.
Case 1 (there is only one MDC available). In this case, (4), (5), and Theorem 12 guarantee that the energy cost of tour T established by RTPP is less than 1.5 times that of the optimal tour. In addition, ω(T) can be reduced due to RNs deployment by ORND.
Case 2 (there are at least two MDCs available). In this case, RND ensures the sum of weights of all MDC tours is less than that of the tour T established by RTPP.
Summing up the two cases above, it is intuitive thatHRSRT is a 1.5-approximation algorithm.Theorem 15.
The complexity of HRSRT isO(n3).Proof.
We distinguish the following two cases to prove this theorem.
Case 1 (there is only one MDC available). In this case, HRSRT consists of algorithms RTPP and ORND. We then analyze the complexity of them, respectively. RTPP takes four steps to build the data collection and aggregation and aggregation tour: the construction of a spanning tree, the establishment of an Euler graph through calculating the perfect matching, the localization of an Euler closed trail, and the discovery of a Hamilton cycle. The cost of obtaining a spanning tree of a graph is less than O(n2). And the construction of an Euler graph through locating a perfect matching will not cost more than O(n3). In addition, the construction of an Euler closed trail requires an O(e) algorithm, where e is a constant. Furthermore, the discovery of a Hamilton cycle is accomplished by depth first search such that its complexity will not exceed O(n2). Intuitively, RTPP is a polynomial time algorithm with the complexity of O(n3). ORND discovers the intersected paths of a data collection and aggregation tour T established by RTPP. Then, it locates the optimal positions for RNs. Since both of the intersected paths discovery and the optimal positions localization can be done in a constant time, ORND is a O(ε) algorithm, where ε is a constant.
Case 2 (there are at least two MDCs available). In this case, HRSRT is composed of RTPP, RND, and PA. It is intuitive that both of RND and PA are O(ε) algorithms.
Summing up two cases above, it is intuitive that the complexity ofHRSRT is O(n3).


### 6.2. Validation Experiments

The simulation environment, performance metrics, and experimental results are discussed in this subsection.


#### 6.2.1. Experiment Setup

We consider a disconnectedMSN deployed in an application area a region of size 2000×2000m. The sensing range and transmission range of a sensor or a relay are set to 25 and 50m, respectively. In order to represent different terrain types over the deployment region, it is divided into cells (i.e., squares of a certain size) where each cell is associated with a terrain type picked randomly from Table 1. In addition, the cell size is determined on the basis of the application area and the application requirements. We choose the size of 35×35m for the cells. Then, topologies with varying number of sensors and segments are generated and 50 topologies for each test case are considered. For each topology, terrain features are randomly added. Since obstacle-free environments are assumed for all baseline approaches, terrain features without obstacles are added.Table 1
Terrain types, risk rates, and elevations.
Type Swamp Grass Water Dirt Forest Flat Risk 0.05 0.004 1 0.002 0.015 0.002 Elevation [0,1] [0,1] 0 [0,1] [0,5] 1


#### 6.2.2. Performance Metrics and Baseline Approaches

In our experiments, a partitionedWSN with varying numbers of segments has been considered. In addition, the parameters that affect the network characteristics are listed as follows.Number of Relay Nodes ( N r ). Since RNs are deployed to federate disjoint segments, a great number of RNs will significantly shortenintersegment distances, so that the energy cost for data collection and aggregation is mitigated. In this paper, Nr is assumed insufficient to connect all disjoint segments.Number of Disjoint Segments ( N s ). Intuitively, the number of communication links between segments raises with Ns. Therefore, a larger Ns results in higher energy cost for data collection and aggregation.Number of Mobile Data Collectors ( N m ). MDCs are employed to replace stationary RNs, due to Nr being insufficient. If there are plenty of MDCs for connectivity recovery, then travelling distance of data collection and aggregation is minimized [12], which implies lower energy cost.Communication Range of a Relay Node ( R ). With the growth of R, inter-segment distances are reduced effectively that contributes to a low cost data collection and aggregation tour.We use the following two metrics to evaluate the overall performance ofHRSRT.Total Energy Cost. Energy cost incurred because of movement is considered. Our goal is to minimize this cost to extend the network lifetime.Maximum Energy Cost. This metric shows the maximum energy cost of a MDC. This is directly related to the survival of a single MDC, which affects the lifetime of the repaired network.Recovery Time. This is the time required to complete network-wide recovery. Minimizing the recovery time is not a goal, but it is affected by the path planning. The velocities of MDCs are set to 0.5 m/s.We compare the performance ofHRSRT with the following three baseline approaches.FeSMoR [11]. This algorithm is designed to minimize the average end-to-end delay between every pair of segments in a damaged WSN with a limited number of relay nodes. FeSMoR works in two phases. The first phase is to construct an Euclidian Steiner Minimal Tree (ESMT) of segments to balance data traffic through stationary RN deployment. In the second phase, FeSMoR finds the edges that require multiple stationary relays and do serve on the least number of inter-segment paths. Then, mobile relays are employed to replace stationary relays on those edges. If there are two adjacent edges that have leaf segments and each of which is assigned with a mobile relay, then such two edges merge as one data collection and aggregation tour, referred to as a Steiner triangle, that requires only one mobile relay.MiMSI [12]. It is a mixed recovery strategy that utilizes MDCs and stationary RNs for connecting a set of partitions. MiMSI first builds an ESMT in terms of the average node degree. And Steiner Points of ESMT and segments are grouped into clusters based on proximity. Then, gateway nodes between every pair of neighboring clusters are determined. After that, MiMSI populates stationary relays at the positions where gateways are located for connecting two adjacent clusters. Finally, each cluster will employ a MDC that tour around segments for data collection and aggregation. If there is only one MDC available, then segments of each cluster are federated by stationary RNs and each gateway node will be repeatedly visited by the only MDC.ReBAT [24]. It is a connectivity restoration strategy that considers realistic terrain influences. ReBAT operates in two phases. The first phase is to seek the set of locations for the mobiles sensors to the ensure connectivity. In the second phase, a greedy-based heuristic constructs a CDS as the connected backbone of the network. Then, some dominatee nodes of the CDS are relocated to maintain the inter-segment connectivity. And during movement of the nodes, different terrain types associated with different frictions (i.e., risk values) are considered, such that each least cost path to the destination is found. Note that ReBAT only considers establishing a 1-connected network. In our experiments, as a baseline approach, ReBAT is slightly modified to build a data collection and aggregation tour through planning at least an extra path to the resulting 1-connected network after connectivity restoration. It is worth mentioning that if ReBAT can obtain the least cost path Pi,j∗ that contains all segments, then in the worst scenario the weight of data collection and aggregation tour ω(C) is less than or equal to two times that of Pi,j∗; that is, ω(C)≤2×ω(Pi,j∗). According to Theorem 12, it is easy to deduce that the extended ReBAT is a 2-approximation algorithm. Henceforth, we use ReBAT-EX to denote the extended ReBAT.In summary,FeSMoR and MiMSI do not consider different terrain types. They attempt to minimize movement distance considering constant energy cost per meter. ReBAT strives to reestablish a 1-connected network, while HRSRT establishes abi-connected inter-segment topology and a least cost tour for data collection and aggregation. In addition, we use Opt to represent the optimal energy cost for connectivity restoration.


#### 6.2.3. Energy Cost Formulation

We use the same formula asReBAT [24] to measure the energy cost as follows:(8)Cost⁡T=∑i=1tki×ei×di×c. Note that T represents a tour continuingly visiting t cells, di is total distance that travelled from ci-1 to ci, c is the constant value referring to the cost for movement per meter on a flat topology which is taken as 30 joules/meter, and ki and ei denote the product of risk and elevation, respectively, for the cell ci shown in Table 1. In addition, the distance of travelling from a cell to its neighboring cell in one of the four directions equals (2/2)R; that is, di=(2/2)R. According to (4), (5), and (8), it is intuitive that the energy cost of a tour T equals ω(T)×c. The performance comparison of FeSMoR, MiMSI, ReBAT-EX, and HRSRT using (8) in terms of energy cost is presented in Section 6.2.4.


#### 6.2.4. Simulation Results

Several configurations with different combinations ofNr, Ns, Nm, and R are simulated. We change the value of Nr and Ns from 4 to 20 with increment of 4, respectively, while Nm and R vary from 6 to 14 with increment of 2 and from 50 to 250 with increment of 50, respectively. For each individual experiment, we average the results over 30 runs. Note that our experiments employ MDCs instead of mobile sensors for connectivity restoration. For all baseline approaches, if there are insufficient RNs to establish connectivity, then MDCs are utilized to tour around all disjoint segments for data collection and aggregation, even if there is only one MDC available. Accordingly, the deployment of RNs will shorten the inter-segment distances. That implies the reduction in energy cost for MDCs.Total Energy Cost. It can be observed from Figure 20 that the energy cost of all approaches for varying Nr declines when there are more relays deployed. The reason for that is that RN deployment continuously shortens the inter-segment distances. This eventually reduces the energy cost for baseline approaches due to a shorter distance of the MDC, while the RNs deployment of HRSRT is responsible for the drop of its energy cost. It is clear that HRSRT consumes significantly less cost than FeSMoR and MiMSI, because of the effectiveness of the path planning. Furthermore, HRSRT incurs less than 3/2 of the cost of Opt as expected.Figure 20
Energy cost for varyingNr with Ns=4, Nm=4, and R=50 m.Figures21 and 22 give performance comparisons of HRSRT with baseline approaches for varying Ns with/without RN deployment. As Ns increases, more energy is consumed for all approaches. This is attributed to the fact that there are more inter-segment links required recovery. However, if there are more and more disjoint segments located in the area, then the inter-segment distances are shorten significantly. That eventually mitigates the energy cost due to the MDC movement of a shorter distance. It is worth mentioning that ReBAT-EX is expected to have more energy cost than HRSRT, since HRSRT plans a data collection and aggregation tour through discovering a Hamilton cycle of a weighted complete graph over disjoint segments, while ReBAT-EX constructs the tour considering an extra path over the repaired 1-connected network. Intuitively, HRSRT outperforms all the baseline approaches with/without RN deployment.Figure 21
Energy cost for varyingNs with Nr=20, Nm=4, and R=50 m.Figure 22
Energy cost for varyingNs with Nr=0, Nm=1, and R=50 m.The adverse impact on the energy cost is observed with the growth ofR as seen in Figure 23. Obviously, the expansion of R of deployed RNs contributes to shorter inter-segment distances. Consequently, overall movement energy cost of the MDC will be reduced for all approaches. Again, the effectiveness of the path planning is the key for HRSRT to succeed in establishing a data collection and aggregation tour of the least energy consumption, compared with FeSMoR and MiMSI.Figure 23
Energy cost for varyingR with Ns=4, Nr=4, and Nm=1.The performance comparisons ofHRSRT with baseline approaches for varying Nm without RN deployment are shown in Figure 24. The energy cost of all three baseline approaches falls with the Nm increases. The reason for that is that more MDCs employed will effectively shorten the total travel distance, which implies the fall in total energy cost. Although HRSRT and Opt consume constant energy due to the lack of RNs deployment, the MDC paths planned by HRSRT consume less energy cost than FeSMoR, MiMSI, and ReBAT-EX. The reason for that is that HRSRT works on discovering the minimum cost data collection and aggregation tour over the weighted complete graph of disjoint segments. More importantly, the effectiveness of HRSRT becomes the major factor in reduction of energy cost. Furthermore, the energy cost of HRSRT is less than 1.5 times that of Opt as expected.Figure 24
Energy cost for varyingNm with Ns=4, Nr=0, and R=50 m.Maximum Energy Cost. As shown in Figure 25, the maximum energy costs of all approaches decline with varying Nm. Because if there are plenty of MDCs employed for Steiner triangles of FeSMoR, clusters of MiMSI, and inter-segment link of ReBAT-EX, respectively, then overall travelling distance will be shorten. That results in the drop in maximum energy cost. For HRSRT, although the growth of Nm does not contribute to the decline in total energy cost due to the lack of RNs deployment, the maximum energy cost is reduced. That is attributed to more MDCs involved for sharing the responsibility of connectivity recovery and data collection and aggregation. It is obvious that HRSRT outperform all baseline approaches.Figure 25
Maximum energy cost for varyingNm with Ns=4, Nr=0, and R=50 m.Recovery Time. Figure 26 shows the recovery time comparison of all approaches for varying Nm. The results indicate that recovery times of all approaches increase first with more segments involved and then decrease when the deployment of segments is getting dense. This is because that the intersegment distances increase when more segments are required to be connected which results in the increase in recovery time; however, densely populated segments shorten the intersegment distances that contribute to the decrease in recovery time. It can be observed that nonterrain-aware approaches, FeSMoR and MiMSI, require less recovery time than terrain-aware approaches, HRSRT and ReBAT-EX. This is expected because direct paths are followed from source to destination when nonterrain-aware approaches are applied. Note that HRSRT is better than ReBAT-EX in recovery time.Figure 26
Recovery time for varyingNs with Nm=8, Nr=0, and R=50 m.As shown in Figure27, the recovery time decreases for all approaches with more MDCs joining in connectivity restoration. The reason for that is that all MDCs collaborate to restore the connectivity simultaneously so that the recovery time is shortened. Although nonterrain-aware approaches perform better than terrain-aware approaches, which aim at mitigating terrain influences on connectivity restoration, as expected in the recovery time, HRSRT still requires less recovery time than ReBAT-EX.Figure 27
Recovery time for varyingNm with Ns=8, Nr=0, and R=50 m.


## 6.1. Theoretical Analysis

The correctness, complexity, and approximation ratio ofHRSRT are analyzed in this subsection. First we give the following theorems.Theorem 8.
All paths of a data collection and aggregation tour established by RTPP satisfy WTI.Proof.
We prove this theorem by contradiction. Suppose there are three pathsPi,j, Pi,k, and Pj,k, for a MDC travelling among three segments si, sj, and sk, such that ω(Pi,j∗)+ω(Pj,k∗)<ω(Pi,k∗). That implies that the cost of directly travelling from si to sk is higher than travelling from si to sk via sj, which contradicts the fact that RTPP only chooses minimum weighted paths for MDCs. Therefore, Pi,k∗ should start from si and end at sk via sj. That implies ω(Pi,j∗)+ω(Pj,k∗)≥ω(Pi,k∗). So the theorem holds.As shown in Figure14, we have ω(P1,2)=1, ω(P2,3)=2, and ω(P1,3)=4. Therefore, the proper choice for travelling from s1 to s3 is via s2. That makes ω(P1,3)=3.Figure 14
The example of weighted triangle rule.
(a) (b) (c)To illustrate the following theorem clearly, we call a pathPi,j a direct path, if there is no segment on Pi,j other than si and sj.Theorem 9.
The tours constructed by RTPP is either a Hamilton cycle or a closed trail.Proof.
RTPP strives to locate the minimum weighted closed trail of a complete weighted graphKn. Without loss of generality, we set T=s1s2⋯sns1 a minimum weighted closed trail. Note that each edge sisj∈mwct is a Pi,j∗, which represents the minimum weighted path from si to sj. Then, we are going to distinguish between two cases to prove this theorem.
If all edges ofT are direct paths such that each segment si is on T exactly once for any i, then, according to Definition 2, T is a minimum weighted Hamilton cycle (see Figure 3).
If there is at least a path not a direct path, that is,Pi,j∗∈T is not a direct path, then it is easy to verify that T is a closed trail. We assume that the path Pi,j∗ starts from si and ends at sj via sk. According to algorithm RTPP, there may exist two other paths Pi,k∗ and Pk,j∗ to complete the trail T, such that Pi,j∗≠Pi,k∗∪Pk,j∗. Intuitively, sk is on T at least twice, which implies T is a closed trail (see Figure 2).Theorem 10.
The weighted complete graphK|S| established by RTPP consists of 2k vertices.Proof.
RTPP employs an introduced graph of a complete weighted graphK|S| to construct a perfect matching MK|S|. When the mst of Kn is built, the set S of odd-degree vertices are employed to construct K|S| for the establishment of a perfect matching. For simplicity, let e=|S|-1 denote the number of edges of mst. Intuitively, the overall degrees of |S| vertices in mst is even, because of the fact [26] ∑i=1nd(vi)=2e, where vi∈mst. It is easy to deduce that |S| is even.For the rest of the paper, we useK2k to represent graph K|S|.Note that a series ofMDC based connectivity recovery algorithms, such as MiMSI [12], IDM-kMDC [10], and MINDS [21], make MDCs travel along the convex hulk of n disjoint segments. Specifically, if there is at least one segment not on CHn, then n segments will be clustered into several disjoint groups so that each group U can form a convex hulk CH|U| with each segment of U on it. For simplicity, we call such algorithms A-CHns. And we call the tour along the convex hulk of n disjoint segment a CHn tour.Theorem 11.
HRSRT establishes a data collection and aggregation tour with less energy cost thanA-CHns.Proof.
LetT and T′ denote the tours established by the RTPP and a A-CHn, respectively. According to RTPP, the selection of perfect matchings of K2k could result in two different types of tours. That is, T is either a CHn tour or a non-CHn tour. We distinguish the following two cases to prove that the energy cost of tour T, Cost(T), is less than that of T′, Cost(T′), regardless of the number m of MDCs.
Case 1 ( T is a non- C H n tour). If there is at least one segment not on CHn, then T′ is a directed graph with either one of the following two structures. One is that a graph consists of at least two connected components bridged with two directed paths. The other is composed of at least two subtours that share a common vertex. We thus take Figure 15 as an example to explicate this case. Let the tour in Figure 15(d) represent T and two tours, for example, T1′ and T1′, in Figures 15(b) and 15(c) represent two types of T′s, respectively. According to Theorem 8, we have ω(P2,3∗)+ω(P3,5∗)≥ω(P2,5∗) and ω(P2,5∗)+ω(P5,1∗)≥ω(P2,1∗). That implies ω(T1′)≥ω(T2′)≥ω(T). According to (5), it is intuitive that Cost(T)≤Cost(T′).
If alln segments are on CHn, then it is easy to get T′=CHn. According to the tour selection of RTPP, we have ω(T)≤ω(CHn)=ω(T′), because T is a non-CHn tour. Again, (5) guarantees that Cost(T)≤Cost(T′).
Case 2 ( T is a C H n tour and all n segments are on C H n ). It is easy to get ω(T)≤ω(T′), since each edge sisj∈T is the minimum weighted path from si to sj, while the edge sisj∈T′ is a straight line directly from si to sj regardless of terrain influences. As shown in Figure 16, it is clear that ω(T)=5+6+9+6+10+5+3+2=46<ω(T′)=5+6+9+6+10+15=51. According to (5), it is intuitive that Cost(T)≤Cost(T′).Figure 15
H R S R T versus A-CHn.
(a) (b) (c) (d)Figure 16
Straight line paths versus minimum weighted paths.
(a) (b) (c)Theorem 12.
RTPP establishes a close trailH′, the weight of which is less than 1.5 times that of the least weight Hamilton cycle H∗.Proof.
Without loss of generality, we assume the close trail established byRTPP is a Hamilton cycle. For simplicity, let M2k represent the perfect matching of graph K2k. Then, the theoretical proof on the approximation ratio of ω(H′) to ω(H∗) is as follows.
First, we sett the minimum spanning tree of a weighted complete graph Kn. Let t′ represent the introduced graph of Hn-{e}, where e denotes an edge of t. Obviously, t′ is still a spanning tree of Kn such that ω(t′)>ω(t). That implies ω(Hn)>ω(t), because of ω(e)>0.
Second, obviouslyK2k is an introduced graph of Kn, where 2k<n. Suppose H2k=s1s2⋯s2ks1 and Hn=s1s2⋯sns1 represent the minimum weighted Hamilton cycles of H2k and Hn, respectively. Without loss of generality, we assume that at least one edge of H2k is not in Hn; for example, s2ks1∉Hn. According to Definition 6 and Theorem 8, we have ω(P2k,1)≥ω(s2ks1), where P2k,1=s2ks2k+1⋯s1. Intuitively, ω(H2k)≤ω(Hn). As shown in Figure 17, we have H6=s1s2s3s4s5s6s1 and H4=s2s3s4s6s2 such that ω(H4)=14<ω(H6)=16. And it also holds for the case that there are more than two edges of K2k not in Kn.
Third, by carefully choosing the edges fromH2k, we can find a minimum weighted M2k such that ω(M2k)≤(1/2)ω(H2k). As shown in Figure 18, we have H4=s1s3s2s4s1 and M4={s1s4,s2s3} such that ω(H4)=6<(1/2)ω(H4)=13.
Finally, letE be an Euler closed trail of T∪M2k established by RTPP. According to Theorem 8, the weights of all paths established by RTPP satisfy WTI. That is, ω(sisj)+ω(sjsk)≥ω(sisk), for every three segments si,sj,sk∈Kn. In addition, a path of k consecutively adjacent edges in E could be replaced by one edge that directly connects two end points of that path during the construction of H′. By recursively taking such steps, H′ is built. Hence, ω(H′)≤ω(E).
Summing up all four steps above, the theorem holds because the following inequation holds:(7)ωH′≤ωE=ωt+ωM2k<ωH∗+12ωH∗=32ω∗.Figure 17
The graphH2k.Figure 18
The perfect matching ofH4.
(a) (b) (c) (d)Theorem 13.
The data collection and aggregation tour construct by HRSRT is 2-connected.Proof.
We distinguish between two cases to prove this theorem.
Case 1 ( m = 1 ). HRSRT adopts RTPP first to calculate a minimum weight Hamilton cycle T as the connectivity restoration tour. Theorem 9 proves that T is either a Hamilton cycle or a closed trail. According to Definitions 3 and 7, it is intuitive that T is 2-connected. Then, ORND is employed to merge any pair of intersected paths Pi,j∗,Pj,k∗∈T so that T=T∖{Pi,j∗,Pj,k∗}∪{Pi,k∗} through RNs deployment. It is easy to verify the fact that there still exist 2 mutually independent paths which implies the biconnectivity of tour T. As shown in Figure 19, there exist C42 pairs of independent paths between any pair of segments. Even if a path is cut off, that is, P1,4 is disconnected, S1 and S4 are still connected via S2 and S3.
Case 2 ( m > 1 ). Similar to Case 1, RTPP is responsible for establishing a 2-connected tour T. Then, for each path Pi,j, RND deploys RNs to build subtour Ti=Pi,j∗∖(PSi,Sir∗∪PSj,Sjl∗). And Ti is assigned to a MDC by PA. It is obvious that T is still 2-connected.
Summing up the two cases above, it is easy to deduce that the data collection and aggregation tour construct byHRSRT is 2-connected.Figure 19
The example of 2-connectivity.
(a) (b)Theorem 14.
The approximation ratio of HRSRT is1.5.Proof.
We distinguish between two cases to prove this theorem.
Case 1 (there is only one MDC available). In this case, (4), (5), and Theorem 12 guarantee that the energy cost of tour T established by RTPP is less than 1.5 times that of the optimal tour. In addition, ω(T) can be reduced due to RNs deployment by ORND.
Case 2 (there are at least two MDCs available). In this case, RND ensures the sum of weights of all MDC tours is less than that of the tour T established by RTPP.
Summing up the two cases above, it is intuitive thatHRSRT is a 1.5-approximation algorithm.Theorem 15.
The complexity of HRSRT isO(n3).Proof.
We distinguish the following two cases to prove this theorem.
Case 1 (there is only one MDC available). In this case, HRSRT consists of algorithms RTPP and ORND. We then analyze the complexity of them, respectively. RTPP takes four steps to build the data collection and aggregation and aggregation tour: the construction of a spanning tree, the establishment of an Euler graph through calculating the perfect matching, the localization of an Euler closed trail, and the discovery of a Hamilton cycle. The cost of obtaining a spanning tree of a graph is less than O(n2). And the construction of an Euler graph through locating a perfect matching will not cost more than O(n3). In addition, the construction of an Euler closed trail requires an O(e) algorithm, where e is a constant. Furthermore, the discovery of a Hamilton cycle is accomplished by depth first search such that its complexity will not exceed O(n2). Intuitively, RTPP is a polynomial time algorithm with the complexity of O(n3). ORND discovers the intersected paths of a data collection and aggregation tour T established by RTPP. Then, it locates the optimal positions for RNs. Since both of the intersected paths discovery and the optimal positions localization can be done in a constant time, ORND is a O(ε) algorithm, where ε is a constant.
Case 2 (there are at least two MDCs available). In this case, HRSRT is composed of RTPP, RND, and PA. It is intuitive that both of RND and PA are O(ε) algorithms.
Summing up two cases above, it is intuitive that the complexity ofHRSRT is O(n3).


## 6.2. Validation Experiments

The simulation environment, performance metrics, and experimental results are discussed in this subsection.


### 6.2.1. Experiment Setup

We consider a disconnectedMSN deployed in an application area a region of size 2000×2000m. The sensing range and transmission range of a sensor or a relay are set to 25 and 50m, respectively. In order to represent different terrain types over the deployment region, it is divided into cells (i.e., squares of a certain size) where each cell is associated with a terrain type picked randomly from Table 1. In addition, the cell size is determined on the basis of the application area and the application requirements. We choose the size of 35×35m for the cells. Then, topologies with varying number of sensors and segments are generated and 50 topologies for each test case are considered. For each topology, terrain features are randomly added. Since obstacle-free environments are assumed for all baseline approaches, terrain features without obstacles are added.Table 1
Terrain types, risk rates, and elevations.
Type Swamp Grass Water Dirt Forest Flat Risk 0.05 0.004 1 0.002 0.015 0.002 Elevation [0,1] [0,1] 0 [0,1] [0,5] 1


### 6.2.2. Performance Metrics and Baseline Approaches

In our experiments, a partitionedWSN with varying numbers of segments has been considered. In addition, the parameters that affect the network characteristics are listed as follows.Number of Relay Nodes ( N r ). Since RNs are deployed to federate disjoint segments, a great number of RNs will significantly shortenintersegment distances, so that the energy cost for data collection and aggregation is mitigated. In this paper, Nr is assumed insufficient to connect all disjoint segments.Number of Disjoint Segments ( N s ). Intuitively, the number of communication links between segments raises with Ns. Therefore, a larger Ns results in higher energy cost for data collection and aggregation.Number of Mobile Data Collectors ( N m ). MDCs are employed to replace stationary RNs, due to Nr being insufficient. If there are plenty of MDCs for connectivity recovery, then travelling distance of data collection and aggregation is minimized [12], which implies lower energy cost.Communication Range of a Relay Node ( R ). With the growth of R, inter-segment distances are reduced effectively that contributes to a low cost data collection and aggregation tour.We use the following two metrics to evaluate the overall performance ofHRSRT.Total Energy Cost. Energy cost incurred because of movement is considered. Our goal is to minimize this cost to extend the network lifetime.Maximum Energy Cost. This metric shows the maximum energy cost of a MDC. This is directly related to the survival of a single MDC, which affects the lifetime of the repaired network.Recovery Time. This is the time required to complete network-wide recovery. Minimizing the recovery time is not a goal, but it is affected by the path planning. The velocities of MDCs are set to 0.5 m/s.We compare the performance ofHRSRT with the following three baseline approaches.FeSMoR [11]. This algorithm is designed to minimize the average end-to-end delay between every pair of segments in a damaged WSN with a limited number of relay nodes. FeSMoR works in two phases. The first phase is to construct an Euclidian Steiner Minimal Tree (ESMT) of segments to balance data traffic through stationary RN deployment. In the second phase, FeSMoR finds the edges that require multiple stationary relays and do serve on the least number of inter-segment paths. Then, mobile relays are employed to replace stationary relays on those edges. If there are two adjacent edges that have leaf segments and each of which is assigned with a mobile relay, then such two edges merge as one data collection and aggregation tour, referred to as a Steiner triangle, that requires only one mobile relay.MiMSI [12]. It is a mixed recovery strategy that utilizes MDCs and stationary RNs for connecting a set of partitions. MiMSI first builds an ESMT in terms of the average node degree. And Steiner Points of ESMT and segments are grouped into clusters based on proximity. Then, gateway nodes between every pair of neighboring clusters are determined. After that, MiMSI populates stationary relays at the positions where gateways are located for connecting two adjacent clusters. Finally, each cluster will employ a MDC that tour around segments for data collection and aggregation. If there is only one MDC available, then segments of each cluster are federated by stationary RNs and each gateway node will be repeatedly visited by the only MDC.ReBAT [24]. It is a connectivity restoration strategy that considers realistic terrain influences. ReBAT operates in two phases. The first phase is to seek the set of locations for the mobiles sensors to the ensure connectivity. In the second phase, a greedy-based heuristic constructs a CDS as the connected backbone of the network. Then, some dominatee nodes of the CDS are relocated to maintain the inter-segment connectivity. And during movement of the nodes, different terrain types associated with different frictions (i.e., risk values) are considered, such that each least cost path to the destination is found. Note that ReBAT only considers establishing a 1-connected network. In our experiments, as a baseline approach, ReBAT is slightly modified to build a data collection and aggregation tour through planning at least an extra path to the resulting 1-connected network after connectivity restoration. It is worth mentioning that if ReBAT can obtain the least cost path Pi,j∗ that contains all segments, then in the worst scenario the weight of data collection and aggregation tour ω(C) is less than or equal to two times that of Pi,j∗; that is, ω(C)≤2×ω(Pi,j∗). According to Theorem 12, it is easy to deduce that the extended ReBAT is a 2-approximation algorithm. Henceforth, we use ReBAT-EX to denote the extended ReBAT.In summary,FeSMoR and MiMSI do not consider different terrain types. They attempt to minimize movement distance considering constant energy cost per meter. ReBAT strives to reestablish a 1-connected network, while HRSRT establishes abi-connected inter-segment topology and a least cost tour for data collection and aggregation. In addition, we use Opt to represent the optimal energy cost for connectivity restoration.


### 6.2.3. Energy Cost Formulation

We use the same formula asReBAT [24] to measure the energy cost as follows:(8)Cost⁡T=∑i=1tki×ei×di×c. Note that T represents a tour continuingly visiting t cells, di is total distance that travelled from ci-1 to ci, c is the constant value referring to the cost for movement per meter on a flat topology which is taken as 30 joules/meter, and ki and ei denote the product of risk and elevation, respectively, for the cell ci shown in Table 1. In addition, the distance of travelling from a cell to its neighboring cell in one of the four directions equals (2/2)R; that is, di=(2/2)R. According to (4), (5), and (8), it is intuitive that the energy cost of a tour T equals ω(T)×c. The performance comparison of FeSMoR, MiMSI, ReBAT-EX, and HRSRT using (8) in terms of energy cost is presented in Section 6.2.4.


### 6.2.4. Simulation Results

Several configurations with different combinations ofNr, Ns, Nm, and R are simulated. We change the value of Nr and Ns from 4 to 20 with increment of 4, respectively, while Nm and R vary from 6 to 14 with increment of 2 and from 50 to 250 with increment of 50, respectively. For each individual experiment, we average the results over 30 runs. Note that our experiments employ MDCs instead of mobile sensors for connectivity restoration. For all baseline approaches, if there are insufficient RNs to establish connectivity, then MDCs are utilized to tour around all disjoint segments for data collection and aggregation, even if there is only one MDC available. Accordingly, the deployment of RNs will shorten the inter-segment distances. That implies the reduction in energy cost for MDCs.Total Energy Cost. It can be observed from Figure 20 that the energy cost of all approaches for varying Nr declines when there are more relays deployed. The reason for that is that RN deployment continuously shortens the inter-segment distances. This eventually reduces the energy cost for baseline approaches due to a shorter distance of the MDC, while the RNs deployment of HRSRT is responsible for the drop of its energy cost. It is clear that HRSRT consumes significantly less cost than FeSMoR and MiMSI, because of the effectiveness of the path planning. Furthermore, HRSRT incurs less than 3/2 of the cost of Opt as expected.Figure 20
Energy cost for varyingNr with Ns=4, Nm=4, and R=50 m.Figures21 and 22 give performance comparisons of HRSRT with baseline approaches for varying Ns with/without RN deployment. As Ns increases, more energy is consumed for all approaches. This is attributed to the fact that there are more inter-segment links required recovery. However, if there are more and more disjoint segments located in the area, then the inter-segment distances are shorten significantly. That eventually mitigates the energy cost due to the MDC movement of a shorter distance. It is worth mentioning that ReBAT-EX is expected to have more energy cost than HRSRT, since HRSRT plans a data collection and aggregation tour through discovering a Hamilton cycle of a weighted complete graph over disjoint segments, while ReBAT-EX constructs the tour considering an extra path over the repaired 1-connected network. Intuitively, HRSRT outperforms all the baseline approaches with/without RN deployment.Figure 21
Energy cost for varyingNs with Nr=20, Nm=4, and R=50 m.Figure 22
Energy cost for varyingNs with Nr=0, Nm=1, and R=50 m.The adverse impact on the energy cost is observed with the growth ofR as seen in Figure 23. Obviously, the expansion of R of deployed RNs contributes to shorter inter-segment distances. Consequently, overall movement energy cost of the MDC will be reduced for all approaches. Again, the effectiveness of the path planning is the key for HRSRT to succeed in establishing a data collection and aggregation tour of the least energy consumption, compared with FeSMoR and MiMSI.Figure 23
Energy cost for varyingR with Ns=4, Nr=4, and Nm=1.The performance comparisons ofHRSRT with baseline approaches for varying Nm without RN deployment are shown in Figure 24. The energy cost of all three baseline approaches falls with the Nm increases. The reason for that is that more MDCs employed will effectively shorten the total travel distance, which implies the fall in total energy cost. Although HRSRT and Opt consume constant energy due to the lack of RNs deployment, the MDC paths planned by HRSRT consume less energy cost than FeSMoR, MiMSI, and ReBAT-EX. The reason for that is that HRSRT works on discovering the minimum cost data collection and aggregation tour over the weighted complete graph of disjoint segments. More importantly, the effectiveness of HRSRT becomes the major factor in reduction of energy cost. Furthermore, the energy cost of HRSRT is less than 1.5 times that of Opt as expected.Figure 24
Energy cost for varyingNm with Ns=4, Nr=0, and R=50 m.Maximum Energy Cost. As shown in Figure 25, the maximum energy costs of all approaches decline with varying Nm. Because if there are plenty of MDCs employed for Steiner triangles of FeSMoR, clusters of MiMSI, and inter-segment link of ReBAT-EX, respectively, then overall travelling distance will be shorten. That results in the drop in maximum energy cost. For HRSRT, although the growth of Nm does not contribute to the decline in total energy cost due to the lack of RNs deployment, the maximum energy cost is reduced. That is attributed to more MDCs involved for sharing the responsibility of connectivity recovery and data collection and aggregation. It is obvious that HRSRT outperform all baseline approaches.Figure 25
Maximum energy cost for varyingNm with Ns=4, Nr=0, and R=50 m.Recovery Time. Figure 26 shows the recovery time comparison of all approaches for varying Nm. The results indicate that recovery times of all approaches increase first with more segments involved and then decrease when the deployment of segments is getting dense. This is because that the intersegment distances increase when more segments are required to be connected which results in the increase in recovery time; however, densely populated segments shorten the intersegment distances that contribute to the decrease in recovery time. It can be observed that nonterrain-aware approaches, FeSMoR and MiMSI, require less recovery time than terrain-aware approaches, HRSRT and ReBAT-EX. This is expected because direct paths are followed from source to destination when nonterrain-aware approaches are applied. Note that HRSRT is better than ReBAT-EX in recovery time.Figure 26
Recovery time for varyingNs with Nm=8, Nr=0, and R=50 m.As shown in Figure27, the recovery time decreases for all approaches with more MDCs joining in connectivity restoration. The reason for that is that all MDCs collaborate to restore the connectivity simultaneously so that the recovery time is shortened. Although nonterrain-aware approaches perform better than terrain-aware approaches, which aim at mitigating terrain influences on connectivity restoration, as expected in the recovery time, HRSRT still requires less recovery time than ReBAT-EX.Figure 27
Recovery time for varyingNm with Ns=8, Nr=0, and R=50 m.


## 6.2.1. Experiment Setup

We consider a disconnectedMSN deployed in an application area a region of size 2000×2000m. The sensing range and transmission range of a sensor or a relay are set to 25 and 50m, respectively. In order to represent different terrain types over the deployment region, it is divided into cells (i.e., squares of a certain size) where each cell is associated with a terrain type picked randomly from Table 1. In addition, the cell size is determined on the basis of the application area and the application requirements. We choose the size of 35×35m for the cells. Then, topologies with varying number of sensors and segments are generated and 50 topologies for each test case are considered. For each topology, terrain features are randomly added. Since obstacle-free environments are assumed for all baseline approaches, terrain features without obstacles are added.Table 1
Terrain types, risk rates, and elevations.
Type Swamp Grass Water Dirt Forest Flat Risk 0.05 0.004 1 0.002 0.015 0.002 Elevation [0,1] [0,1] 0 [0,1] [0,5] 1


## 6.2.2. Performance Metrics and Baseline Approaches

In our experiments, a partitionedWSN with varying numbers of segments has been considered. In addition, the parameters that affect the network characteristics are listed as follows.Number of Relay Nodes ( N r ). Since RNs are deployed to federate disjoint segments, a great number of RNs will significantly shortenintersegment distances, so that the energy cost for data collection and aggregation is mitigated. In this paper, Nr is assumed insufficient to connect all disjoint segments.Number of Disjoint Segments ( N s ). Intuitively, the number of communication links between segments raises with Ns. Therefore, a larger Ns results in higher energy cost for data collection and aggregation.Number of Mobile Data Collectors ( N m ). MDCs are employed to replace stationary RNs, due to Nr being insufficient. If there are plenty of MDCs for connectivity recovery, then travelling distance of data collection and aggregation is minimized [12], which implies lower energy cost.Communication Range of a Relay Node ( R ). With the growth of R, inter-segment distances are reduced effectively that contributes to a low cost data collection and aggregation tour.We use the following two metrics to evaluate the overall performance ofHRSRT.Total Energy Cost. Energy cost incurred because of movement is considered. Our goal is to minimize this cost to extend the network lifetime.Maximum Energy Cost. This metric shows the maximum energy cost of a MDC. This is directly related to the survival of a single MDC, which affects the lifetime of the repaired network.Recovery Time. This is the time required to complete network-wide recovery. Minimizing the recovery time is not a goal, but it is affected by the path planning. The velocities of MDCs are set to 0.5 m/s.We compare the performance ofHRSRT with the following three baseline approaches.FeSMoR [11]. This algorithm is designed to minimize the average end-to-end delay between every pair of segments in a damaged WSN with a limited number of relay nodes. FeSMoR works in two phases. The first phase is to construct an Euclidian Steiner Minimal Tree (ESMT) of segments to balance data traffic through stationary RN deployment. In the second phase, FeSMoR finds the edges that require multiple stationary relays and do serve on the least number of inter-segment paths. Then, mobile relays are employed to replace stationary relays on those edges. If there are two adjacent edges that have leaf segments and each of which is assigned with a mobile relay, then such two edges merge as one data collection and aggregation tour, referred to as a Steiner triangle, that requires only one mobile relay.MiMSI [12]. It is a mixed recovery strategy that utilizes MDCs and stationary RNs for connecting a set of partitions. MiMSI first builds an ESMT in terms of the average node degree. And Steiner Points of ESMT and segments are grouped into clusters based on proximity. Then, gateway nodes between every pair of neighboring clusters are determined. After that, MiMSI populates stationary relays at the positions where gateways are located for connecting two adjacent clusters. Finally, each cluster will employ a MDC that tour around segments for data collection and aggregation. If there is only one MDC available, then segments of each cluster are federated by stationary RNs and each gateway node will be repeatedly visited by the only MDC.ReBAT [24]. It is a connectivity restoration strategy that considers realistic terrain influences. ReBAT operates in two phases. The first phase is to seek the set of locations for the mobiles sensors to the ensure connectivity. In the second phase, a greedy-based heuristic constructs a CDS as the connected backbone of the network. Then, some dominatee nodes of the CDS are relocated to maintain the inter-segment connectivity. And during movement of the nodes, different terrain types associated with different frictions (i.e., risk values) are considered, such that each least cost path to the destination is found. Note that ReBAT only considers establishing a 1-connected network. In our experiments, as a baseline approach, ReBAT is slightly modified to build a data collection and aggregation tour through planning at least an extra path to the resulting 1-connected network after connectivity restoration. It is worth mentioning that if ReBAT can obtain the least cost path Pi,j∗ that contains all segments, then in the worst scenario the weight of data collection and aggregation tour ω(C) is less than or equal to two times that of Pi,j∗; that is, ω(C)≤2×ω(Pi,j∗). According to Theorem 12, it is easy to deduce that the extended ReBAT is a 2-approximation algorithm. Henceforth, we use ReBAT-EX to denote the extended ReBAT.In summary,FeSMoR and MiMSI do not consider different terrain types. They attempt to minimize movement distance considering constant energy cost per meter. ReBAT strives to reestablish a 1-connected network, while HRSRT establishes abi-connected inter-segment topology and a least cost tour for data collection and aggregation. In addition, we use Opt to represent the optimal energy cost for connectivity restoration.


## 6.2.3. Energy Cost Formulation

We use the same formula asReBAT [24] to measure the energy cost as follows:(8)Cost⁡T=∑i=1tki×ei×di×c. Note that T represents a tour continuingly visiting t cells, di is total distance that travelled from ci-1 to ci, c is the constant value referring to the cost for movement per meter on a flat topology which is taken as 30 joules/meter, and ki and ei denote the product of risk and elevation, respectively, for the cell ci shown in Table 1. In addition, the distance of travelling from a cell to its neighboring cell in one of the four directions equals (2/2)R; that is, di=(2/2)R. According to (4), (5), and (8), it is intuitive that the energy cost of a tour T equals ω(T)×c. The performance comparison of FeSMoR, MiMSI, ReBAT-EX, and HRSRT using (8) in terms of energy cost is presented in Section 6.2.4.


## 6.2.4. Simulation Results

Several configurations with different combinations ofNr, Ns, Nm, and R are simulated. We change the value of Nr and Ns from 4 to 20 with increment of 4, respectively, while Nm and R vary from 6 to 14 with increment of 2 and from 50 to 250 with increment of 50, respectively. For each individual experiment, we average the results over 30 runs. Note that our experiments employ MDCs instead of mobile sensors for connectivity restoration. For all baseline approaches, if there are insufficient RNs to establish connectivity, then MDCs are utilized to tour around all disjoint segments for data collection and aggregation, even if there is only one MDC available. Accordingly, the deployment of RNs will shorten the inter-segment distances. That implies the reduction in energy cost for MDCs.Total Energy Cost. It can be observed from Figure 20 that the energy cost of all approaches for varying Nr declines when there are more relays deployed. The reason for that is that RN deployment continuously shortens the inter-segment distances. This eventually reduces the energy cost for baseline approaches due to a shorter distance of the MDC, while the RNs deployment of HRSRT is responsible for the drop of its energy cost. It is clear that HRSRT consumes significantly less cost than FeSMoR and MiMSI, because of the effectiveness of the path planning. Furthermore, HRSRT incurs less than 3/2 of the cost of Opt as expected.Figure 20
Energy cost for varyingNr with Ns=4, Nm=4, and R=50 m.Figures21 and 22 give performance comparisons of HRSRT with baseline approaches for varying Ns with/without RN deployment. As Ns increases, more energy is consumed for all approaches. This is attributed to the fact that there are more inter-segment links required recovery. However, if there are more and more disjoint segments located in the area, then the inter-segment distances are shorten significantly. That eventually mitigates the energy cost due to the MDC movement of a shorter distance. It is worth mentioning that ReBAT-EX is expected to have more energy cost than HRSRT, since HRSRT plans a data collection and aggregation tour through discovering a Hamilton cycle of a weighted complete graph over disjoint segments, while ReBAT-EX constructs the tour considering an extra path over the repaired 1-connected network. Intuitively, HRSRT outperforms all the baseline approaches with/without RN deployment.Figure 21
Energy cost for varyingNs with Nr=20, Nm=4, and R=50 m.Figure 22
Energy cost for varyingNs with Nr=0, Nm=1, and R=50 m.The adverse impact on the energy cost is observed with the growth ofR as seen in Figure 23. Obviously, the expansion of R of deployed RNs contributes to shorter inter-segment distances. Consequently, overall movement energy cost of the MDC will be reduced for all approaches. Again, the effectiveness of the path planning is the key for HRSRT to succeed in establishing a data collection and aggregation tour of the least energy consumption, compared with FeSMoR and MiMSI.Figure 23
Energy cost for varyingR with Ns=4, Nr=4, and Nm=1.The performance comparisons ofHRSRT with baseline approaches for varying Nm without RN deployment are shown in Figure 24. The energy cost of all three baseline approaches falls with the Nm increases. The reason for that is that more MDCs employed will effectively shorten the total travel distance, which implies the fall in total energy cost. Although HRSRT and Opt consume constant energy due to the lack of RNs deployment, the MDC paths planned by HRSRT consume less energy cost than FeSMoR, MiMSI, and ReBAT-EX. The reason for that is that HRSRT works on discovering the minimum cost data collection and aggregation tour over the weighted complete graph of disjoint segments. More importantly, the effectiveness of HRSRT becomes the major factor in reduction of energy cost. Furthermore, the energy cost of HRSRT is less than 1.5 times that of Opt as expected.Figure 24
Energy cost for varyingNm with Ns=4, Nr=0, and R=50 m.Maximum Energy Cost. As shown in Figure 25, the maximum energy costs of all approaches decline with varying Nm. Because if there are plenty of MDCs employed for Steiner triangles of FeSMoR, clusters of MiMSI, and inter-segment link of ReBAT-EX, respectively, then overall travelling distance will be shorten. That results in the drop in maximum energy cost. For HRSRT, although the growth of Nm does not contribute to the decline in total energy cost due to the lack of RNs deployment, the maximum energy cost is reduced. That is attributed to more MDCs involved for sharing the responsibility of connectivity recovery and data collection and aggregation. It is obvious that HRSRT outperform all baseline approaches.Figure 25
Maximum energy cost for varyingNm with Ns=4, Nr=0, and R=50 m.Recovery Time. Figure 26 shows the recovery time comparison of all approaches for varying Nm. The results indicate that recovery times of all approaches increase first with more segments involved and then decrease when the deployment of segments is getting dense. This is because that the intersegment distances increase when more segments are required to be connected which results in the increase in recovery time; however, densely populated segments shorten the intersegment distances that contribute to the decrease in recovery time. It can be observed that nonterrain-aware approaches, FeSMoR and MiMSI, require less recovery time than terrain-aware approaches, HRSRT and ReBAT-EX. This is expected because direct paths are followed from source to destination when nonterrain-aware approaches are applied. Note that HRSRT is better than ReBAT-EX in recovery time.Figure 26
Recovery time for varyingNs with Nm=8, Nr=0, and R=50 m.As shown in Figure27, the recovery time decreases for all approaches with more MDCs joining in connectivity restoration. The reason for that is that all MDCs collaborate to restore the connectivity simultaneously so that the recovery time is shortened. Although nonterrain-aware approaches perform better than terrain-aware approaches, which aim at mitigating terrain influences on connectivity restoration, as expected in the recovery time, HRSRT still requires less recovery time than ReBAT-EX.Figure 27
Recovery time for varyingNm with Ns=8, Nr=0, and R=50 m.


## 7. Conclusion and Future Work

Due to the significance of both connectivity maintenance and optimal network topologies discovery forWSNs, in this paper, we have discussed a random terrain based connectivity recovery problem in a disconnected WSN under the constraint that there are only k relay nodes (RNs) and m mobile data collectors (MDCs) available. According to different values of m, a hybrid connectivity restoration and routing strategy HRSRT is designed. For m=1, two highly efficient algorithms, the random terrain based path planning (RTPP) and the Optimized Relay Node Deployment (ORND), constitute HRSRT. For m>1, HRSRT is composed of RTPP, relay nodes deployment (RND), and optimal Path Allocation (PA). All four algorithms collaborate to accomplish the biconnectivity restoration of a disconnected network; meanwhile, the energy cost of data collection and aggregation is minimized. The performance of HRSRT is analyzed theoretically and validated through simulation. The simulation results show that HRSRT outperforms FeSMoR, MiMSI, and the extended version of ReBAT (namely, ReBAT-EX) in terms of the total/maximum energy cost. Our future work is to investigate the connectivity recovery problem with the consideration of the cost for RNs and MDCs deployment.



---

*Source: 5807289-2017-01-05.xml*