Obstacle Aware Connectivity Restoration for Disjoint Wireless Sensor Networks Using a Mix of Stationary and Mobile Nodes

Abstract

In many applications, wireless sensor networks (WSNs) are deployed in inhospitable environments and therefore the nodes are at increased risk of failure. Large scale damage may partition a network into disjoint segments, which has very negative effect on the application. Mobile nodes have been exploited to act as mobile data collectors (MDCs) among segments to restore the connectivity of WSNs in the previous works. However, almost all of the works assumed that mobile nodes travel via a direct path, which may not be the case in real-world applications. In order to improve the applicability of the recovery strategy, obstacles should be taken into account. In this paper, we present an obstacle aware connectivity restoration strategy (OACRS) to fit these requirements. Our algorithm is designed for the scenarios that the number of available relays is less than the number of relays required to construct stable links and more than the number of segments. At first we construct and optimize the obstacle-avoiding minimum spanning tree of the segments and then determine the relays which keep static and the ones which act as MDCs. Finally we optimize the tour path of MDCs. The effectiveness of the proposed algorithm is validated through simulation experiments.

1. Introduction

In recent years, wireless sensor networks (WSNs) have attracted many research attentions in numerous applications [1–4]. In many applications, WSNs are deployed into hazard environment, such as battle field, border protection, and security surveillance, where the networks may suffer large scale damage and be partitioned into disjoint segments. For example, in a battle field, multiple nodes would be destroyed by explosives and the surviving nodes are split into disjoint partitions, which prevent data exchange and hinder coordination among some nodes. Thus, connectivity restoration of intersegments would be essential for the networks to resume full operation.

A number of reactive approaches are proposed to establish connectivity among WSN segments in the literature. Some of the approaches form intersegment paths by repositioning some nodes from the individual segments [5–9]. However, this strategy is feasible only when the network is composed of movable nodes. The other strategy is to deploy additional relay nodes to relink segments. The approaches proposed in [10–12] involve the deployment of static relay nodes to establish stable communication links among segments, which is only suitable for the scenario that relay nodes are sufficient. In many emergent situations, it is difficult to obtain sufficient relay nodes. When the number of relay nodes is not enough to construct stable links among the partitions, some approaches deploy mobile data collectors (MDCs) traveling among the segments to provide intermittent communication links [9, 12–15]. MDCs can be designated to serve on the individual links and carry data from nodes in one segment to recipients in another.

When involved in the mobile node, almost all of the works assume that destinations can be reached via direct path movement. The only two recent works considering obstacle avoidance in connectivity restoration can be found in [5, 8]. However, neither of the two works considers the scenario of how to place stationary and mobile nodes among disjoint segments to restore the connectivity of the WSNs.

In this paper, we present an obstacle aware connectivity restoration strategy (OACRS), which considers the scenario that available relays are not sufficient to construct stable links but the number is more than that of segments. OACRS exploits a hybrid solution that employs a mix of stationary and mobile relays to restore the connectivity of the network. Rather than following a direct path, obstacles are taken into account when the MDCs are moving. The main objective of OACRS is to minimize the total tour length and maximum tour length. The strategy is divided into two phases. In the first phase, we propose an algorithm to construct and optimize the obstacle-avoiding minimum spanning tree (oamst) of all the segments. And in the second phase, an algorithm is present to determine which edges of the oamst will be served by MDCs and optimize the tours path to minimize the tour length. In order to avoid interference of signal caused by obstacles, we employed MDCs on the routes along the obstacle boundary. The simulation results confirm the effectiveness of OACRS compared to recent work in the literature.

This paper is organized as follows. Related work is summarized in Section 2. The system model and assumptions are discussed in Section 3. In Section 4, the proposed OARCS approach is described in detail. Section 5 presents the simulation results and finally Section 6 concludes the paper.

2. Related Work

The published relays placement schemes about connectivity restoration of disjoint WSNs segments fall into three categories. The first category is to establish a stable intersegment topology under the scenario that all relay nodes are stable. The second category is that all the relays act as mobile data collectors. And the third is to restore connectivity using a mix of mobile and stationary relays.

When relay nodes are sufficient to reestablish connectivity, the connectivity restoration problem becomes the problem of restoring connectivity with the fewest number of relays. Ma et al. [10] model the two-tiered WSNs relay nodes placement problem as a GDC (Geometric Disc Covering) problem and improve the network robustness against connection failure by solving the relay nodes double cover problem. Sitanayah et al. [11] propose GRASP-AR, which uses counting paths to minimize the number of relay nodes. Han et al. [12] address the minimum number of relay nodes' placement in the context of H-WSNs. These approaches only suit for the scenario that there are sufficient relay nodes to establish a stable intersegment topology. However, in real-world applications, especially in an emergency, such as battlefield, it is hard to get enough relays.

When the number of additional nodes is less than the number of segments, all the relay nodes need to travel around to provide intermittent communication links. Senel and Younis [9] propose IDM-kMDC, in which disjoint segments are interconnected through k MDCs. IDM-kMDC merges two collocated MDCs to reduce the number of MDCs by one in each round. And it strives to minimize the merged tour length. Senturk et al. [14] exploit Game Theory to orchestrate the self-spreading process of mobile nodes.

Some other published approaches use a mix of stationary and mobile relays to restore connectivity of intersegments, such as MiMSI [13], FeSMoR [16], and ToCS [17]. These algorithms work under the situation that available relays are not sufficient to form stable data path among segments but the number of the available relays is still more than the count of segments. Thus, some of the relay nodes will travel among segments to establish intermittent links. MiMSI exploits the availability of relays to shorten the travel path of MDCs and lower the data delivery latency. FeSMoR assumes the relays are sufficient and the RN placement problem is modeled as Steiner Minimum Tree. And it incrementally replaces groups of relays on the Steiner Tree with mobile nodes. FeSMoR meets the resource availability constraints and achieves the minimal delay objective by exploiting relay mobility at the periphery of the federated intersegment topology. ToCS uses the available MRNs to form a simple star topology and it aims at minimizing both the maximum and average data delivery latency between any two segments.

OACRS also uses a mix of stationary and mobile relays to restore connectivity. However, unlike FeSMoR, OACRS aims at minimizing the maximum tour length and the total tour length. OACRS is also different from MiMSI. There is no limitation to the number of static nodes and mobile nodes in OACRS, while MiMSI assumes both numbers of stationary and mobile relays are fixed.

The only two works in which obstacles are under consideration [5, 8] are also different from OARCS both in application scenarios and in algorithms themselves. In OCRS [5] the failure of a single cut-vertex sensor of MRSNs is addressed and the connectivity is restored by cascaded nodes movement. Obstacle-avoiding problem is addressed when the nodes are moving. Senturk et al. [8] consider the terrain characteristics when mobile nodes are moving and pick the path with the least risk rate for the mobile nodes. This approach repositions nodes from various segments to restore network connectivity, which is much difficult to keep connectivity within segments, while OARCS addresses the connectivity restoration problem of intersegments under the scenario that available relays are insufficient but the number is more than the number of segments, which is not considered in [5, 8].

3. System Model

We consider the wireless sensor network, which suffers large scale damage and is divided into several disjoint segments, and there are obstacles among the partitions. The system model can be shown in Figure 1. For simplicity's sake, each segment is represented by a node (collection point) in our work. And the node corresponds to the common communication range R (R is the maximum Euclidean distance that its radio can reach).

Figure 1

Illustration of the system model. Solid squares indicate MDCs, solid circles indicate stationary relays, and trapezoid denotes the obstacle.

We also have the following assumptions and definitions.

Assumption 1 (relay nodes).

All the relay nodes can move on demand.

Assumption 2 (obstacles).

There is at least one edge in the minimum spanning tree which intersects the obstacles. In OACRS, an obstacle is defined as a convex polygon of any size, and the count of the vertex of one obstacle is not less than 4. In addition, any obstacles cannot overlap with segments.

Definition 3.

Given an undirected graph $G=\left(S,E\right)$ , where $S=\{s_1,s_2,s_3,\dots ,s_n\}$ is the set of segments and $E=\{(s_i,s_j)\mid s_i,s_j\in S\}$ is the set of edges, let $T=(S,E_t)$ denote the obstacles-avoiding minimum spanning tree (oamst), where $E_t$ represents the set of edges of oamst. Let $E_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}}=E-E_t$ , $\forall (s_i,s_j)\in E_t$ , and $\neg \exists \left(s_m,s_n\right)\in E_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}}\wedge \mathrm{d}\mathrm{i}\mathrm{s}\hspace{0.17em}(s_i,s_j)<\mathrm{d}\mathrm{i}\mathrm{s}\hspace{0.17em}(s_m,s_n)$ , where $\mathrm{d}\mathrm{i}\mathrm{s}\hspace{0.17em}(s_i,s_j)$ is the Euclidean distance of segments $s_i$ and $s_j$ .

Definition 4.

$\forall (s_i,s_j)\in E_t$ , $\mathrm{R}\mathrm{N}\hspace{0.17em}(s_i,s_j)$ denotes the number of relay nodes between segments $s_i$ and $s_j$ . Then $\mathrm{R}\mathrm{N}\hspace{0.17em}(s_i,s_j)$ can be computed through the following formula:

$$\begin{array}{cc}& \mathrm{R}\mathrm{N}\left(s_i,s_j\right)=⌈\frac{\mathrm{d}\mathrm{i}\mathrm{s}\left(s_i,s_j\right)}{R}⌉-\mathrm{1}.\end{array}$$

(1)

Definition 5.

Let $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ denote the total number of relay nodes required to form a stable topology. $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ can be computed through the following formula:

$$\begin{array}{cc}& \mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}={{\displaystyle \sum }}_{\left(s_i,s_j\right)\in E_t}\mathrm{R}\mathrm{N}\left(s_i,s_j\right).\end{array}$$

(2)

Assumption 6.

Let M denote the count of segments. The number of available relay nodes ${\mathrm{R}\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}$ satisfies the following criteria: ${\mathrm{R}\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}>M$ and ${\mathrm{R}\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}<\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ .

System Model. The mathematical model of OACRS can be simplified this way: let $S=\{s_1,s_2,s_3,\dots ,s_n\}$ be the set of segments and $P=\{p_1,p_2,p_3,\dots ,p_m\}$ ( $m\ge 4$ ) the set of the vertexes of the obstacle, where $p_i$ cannot overlap the segment $s_i$ . Let $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ represent the number of relays required to form a stable topology. Let $\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}=\{n_1,n_2,n_3,\dots ,n_k\}$ denote the set of available relays, where k satisfies the following condition: $k>M\wedge k<\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ .

4. Obstacle-Avoiding Connectivity Restoration Strategy

In this section, OARCS approach is described in detail. At first we construct and optimize the oamst. Then the delays deployment problem is handled. Finally the tour path of MDCs is optimized.

4.1. Obstacle-Avoiding Minimum Spanning Tree Construction

OACRS aims to shorten the tour length of MDCs. Thus we model the relays placement problem as an obstacle-avoiding minimum spanning tree. The algorithm will be handled as follows.

Construction of Minimum Spanning Tree without Considering Obstacles. At first we construct the minimum spanning tree (mst) of the segments using Prim algorithm without considering obstacles, where each segment is represented by a collection point. As shown in Figure 2(a), the wireless sensor network is divided into ten disjoint segments which are presented by $\{s_1,s_2,s_3,\dots ,s_{10}\}$ . $P=\{p_1,p_2,p_3,p_4\}$ denotes the set of vertexes of the obstacle, and edge $s_2\text{-}{s}_7$ intersects the obstacle P.

Figure 2

Construction of obstacle-avoiding minimum spanning tree.

Construction and Optimization of Obstacle-Avoiding Minimum Spanning Tree. When one or more edges intersect obstacles, we change the routes to avoid obstacles. There are two scenarios.

$(1)$ Only one edge of the oamst intersects the obstacle. Suppose edge $(s_i,s_j)$ divides the obstacle into two partitions and $r_{\mathrm{1}}$ and $r_2$ are two routes linking $s_i$ to $s_j$ in the oamst. OACRS takes tour length as optimization objective. Thus, we should choose the shorter route as the tour path of MDCs. As shown in Figure 2(b), the route $r_1$ is denoted by $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ and $r_2$ is $s_2\text{-}{p}_2\text{-}{p}_3\text{-}{s}_7$ . The lengths of $r_1$ and $r_2$ satisfy the following condition: $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(r_1)<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(r_2)$ . Thus we choose $r_1$ as the tour path linking up segments $s_i$ and $s_j$ .

$(2)$ More than one edge intersects the obstacle. If there is more than one edge intersecting the obstacle, each edge should be replaced by a new route using the method described in (1). As shown in Figure 2(c), there are two edges that intersect the obstacle simultaneously, and the better replacements are $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ and $s_2\text{-}{p}_2\text{-}{s}_8$ , respectively. However, rings may be formed while searching the replacement, which is forbidden in oamst. Once a ring is formed, we destroy the ring by removing the longest edge in the ring. This case is illustrated in Figure 2(d). Edges $s_2\text{-}{s}_7$ and $s_3\text{-}{s}_8$ should be replaced by $s_2\text{-}{p}_1\text{-}{s}_7$ and $s_3\text{-}{p}_1\text{-}{p}_4\text{-}{s}_8$ , respectively. However, ring $s_3\text{-}{s}_2\text{-}{p}_1\text{-}{s}_3$ is formed, so we remove the longest edge $s_2\text{-}{s}_3$ .

Improvement of Obstacle-Avoiding Minimum Spanning Tree. The obstacle-avoiding spanning tree we have constructed may be not the minimum spanning tree because we replace some edges by routes, and the length of routes may be longer than that of a qualified link in $E_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}}$ . OACRS tries to find edge $e_i$ in $E_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}}$ , which meets the following conditions: (i) when $e_i$ substitutes for a route in the spanning tree, the network keeps intersegment connected and there is no ring formed. (ii) $e_i$ is the shortest link in $E_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}}$ which satisfies condition (i). As shown in Figure 2(b), the edge meeting conditions (i) and (ii) simultaneously is $s_1\text{-}{s}_6$ , which satisfies $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(s_1\text{-}{s}_6)<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7)$ . Now we eliminate route $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ and link $s_1$ to $s_6$ . If there is no ring formed, edge $s_1\text{-}{s}_6$ will substitute for $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ which is shown in Figure 2(e).

Figure 2(d) shows a more complicated case.

(i) The shortest link in $E_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}}$ is $s_7\text{-}{s}_8$ ; (ii) $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(s_7\text{-}{s}_8)>\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(s_2\text{-}{p}_1\text{-}{s}_7)$ and $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(s_7\text{-}{s}_8)<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(s_3\text{-}{p}_1\text{-}{p}_4\text{-}{s}_8)$ ; (iii) there is no ring formed when edge $s_7\text{-}{s}_8$ substitutes for route $s_3\text{-}{p}_1\text{-}{p}_4\text{-}{s}_8$ . Thus we remove $s_3\text{-}{p}_1\text{-}{p}_4\text{-}{s}_8$ from Figure 2(d) and link $s_7$ to $s_8$ . However, Figure 2(d) will be divided into two partitions $\{s_1,s_2,p_1,s_6,s_7,s_8,s_9,s_{10}\}$ and $\{s_3,s_4,s_5\}$ . This is because when $s_3\text{-}{p}_1\text{-}{p}_4\text{-}{s}_8$ substitutes for $s_3\text{-}{s}_8$ , edge $s_2\text{-}{s}_3$ is eliminated to destroy the ring. We should link $s_2$ to $s_3$ again to keep the connectivity of the segments. The improved obstacle-avoiding minimum spanning tree is shown in Figure 2(f).

4.2. Federating Disjoint Segments

We assume relays are sufficient firstly and employ the relay nodes on each edge or route of the oamst. As is shown in Figure 3(a), each edge or route in oamst is served by one or more relays to form a stable topology among these segments. However, in this paper, we consider the case that available relays are not sufficient; that is to say, $\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}<\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ . Thus OACRS tries to serve an edge, part of an edge, or several edges with a single MDC to meet the relays availability constraints. The question is which edge(s) should be served by static relays and which should be served by MDCs to minimize the total tour length and maximum tour length. This process is done as follows.

Figure 3

Illustration of how the OACRS operates.

Handling the Employment on the Route. We should emphasize that the obstacles may interfere with the signal of the stable relays. Thus we place MDCs on the routes. Let $L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}(s_i,s_j)$ denote the length of a route linking $s_i$ to $s_j$ and let $\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ represent the average length of the edges in oamst. $L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}(s_i,s_j)$ and $\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ can be computed from formulas (3) and (4), respectively:

$$\begin{array}{c}{L}_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}\left(s_i,s_j\right)=\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}\left(s_i,p_i\right)\\ +{{\displaystyle \sum }}_{p_m,p_n\in \mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}\left(p_m,p_n\right)\\ +\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}\left(p_j,s_j\right),\end{array}$$

(3)

$$\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}=\frac{\left({\sum }_{\left(s_i,s_j\right)\in E_{\mathrm{o}\mathrm{a}\mathrm{m}\mathrm{s}\mathrm{t}}}\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}\left(s_i,s_j\right)\right)}{N_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}},$$

(4)

where $N_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ is the count of edges in oamst.

In order to shorten the maximum tour length, the tour path of MDCs must follow the rule below: the tour length of each MDC cannot be longer than $\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ .

If $L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}(s_i,s_j)<\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ , the route needs one MDC.

If $L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}(s_i,s_j)>n\hspace{0.17em}\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ and $L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}(s_i,s_j)<(n+1)\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ , the route needs ( $2n+1$ ) relays, where n relay nodes keep stable and the other ( $n+1$ ) relays act as MDCs to form an intermittent link.

After the placement of relays on route $s_i\text{-}{p}_i\cdots p_m\cdots p_j\text{-}{s}_j$ , we assume the released number of relays is $\mathrm{R}{\mathrm{N}}_{\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{e}}$ . If $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}-\mathrm{R}{\mathrm{N}}_{\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{e}}=\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}$ , the algorithm ends. Otherwise OACRS continues to place MDCs on edges of the oamst.

Employment on the Edges. Let $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(s_i,s_j)$ denote the Euclidean distance between segments $s_i$ and $s_j$ , where $s_i\text{-}{s}_j$ is an edge of oamst. We try to find out all the adjacent edges of the tree. As shown in Figure 3(b), each triangle has one edge expressed by a dotted line. Then we compute the perimeter of the triangles which are constructed by the terminals of the two adjacent edges. Let $\min L$ denote the length of the shortest edge in $E_t$ and $\min P$ shortest perimeter. At each iteration, OACRS firstly compares $\min L$ and $\min P$ .

If $\min L<\min P$ , the shortest edge is chosen. There are three cases:

• (1)

If $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}-\mathrm{R}{\mathrm{N}}_{\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{e}}>\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}$ , OACRS will place a MDC on the shortest edge and eliminate the edge from $E_t$ . The iteration continues.

(2)

If $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}-\mathrm{R}{\mathrm{N}}_{\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{e}}=\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}$ , the algorithm ends.

(3)

If $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}-\mathrm{R}{\mathrm{N}}_{\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{e}}<\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}$ , the MDCs on the chosen edge will reduce tour length; that is to say, OARCS will place some stationary relays and a MDC on the edge. And the algorithm ends.

If $\min P<\mathrm{m}\mathrm{i}\mathrm{n}L$ , OARCS will place a MDC on the triangle. Then the following treatment is similar to (1), (2), and (3).

Illustrative Example. Figure 3 illustrates the operation of OACRS on federating 10 segments $s_1,s_2,\dots ,s_{10}$ with 15 relays. Based on the communication range, the total number of relays $\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ is 23. Firstly, we assume 23 stable relays are placed on edges or routes, as shown in Figure 3(a). Then we will determine the number of relays placed on route $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ . The length of the route $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ satisfies the following conditions: (i) $L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}(s_2,s_7)>\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ and (ii) $L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}(s_2,s_7)<\mathrm{2}\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ . We have emphasized that the tour length of each MDC cannot be longer than $\mathrm{A}\mathrm{v}\mathrm{g}\hspace{0.17em}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}$ . Each route needs ( $2n+1$ ) relays to link up two segments, where n follows

$$\begin{array}{cc}& n=\left[\frac{L_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}}\left(s_i,s_j\right)}{\mathrm{A}\mathrm{v}\mathrm{g}{L}_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}}\right].\end{array}$$

(5)

According to conditions (i) and (ii), we are aware that $n=1$ . So route $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ needs 3 relay nodes, where one keeps stable and the other two nodes act as MDCs. As shown in Figure 3(a), if we only place stable nodes, the route $s_2\text{-}{p}_1\text{-}{p}_4\text{-}{s}_7$ needs 5 nodes. Thus 2 nodes are released. The placement of relays on edges is an iterative process, where 5 MDCs institute the remaining 11 RNs. Firstly, OACRS compares $\min L$ and $\min P$ . The length of edges $s_3\text{-}{s}_4$ , $s_4\text{-}{s}_5$ , and $s_7\text{-}{s}_8$ follows $L_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}(s_i,s_j)>R\wedge L_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}(s_i,s_j)<\mathrm{2}R$ , so here no relay needs to be released. Then OACRS places one MDC on each of the edges $s_2\text{-}{s}_3$ , $s_9\text{-}{s}_{10}$ , and $s_8\text{-}{s}_9$ , so 4 relays can be released. In the comparison of seventh time, the shortest edge is $s_1\text{-}{s}_2$ , and the triangle with shortest perimeter is $s_3\text{-}{s}_4\text{-}{s}_5\text{-}{s}_3$ , where $\min L>\min P$ . So OACRS places one MDC along the triangle, where one relay is released. By now, the number of relays in the oamst is 16, and $\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}$ is 15. OACRS employs one MDC on the shortest edge $s_1\text{-}{s}_2$ to release one relay, and the other two relays remain still. Thus, we restore the connectivity of the segments with 15 relays nodes, where 7 relays act as MDCs and 8 remain still.

4.3. Determining MDCs Tours

The tours length should be computed before iteration. The tour of a MDC is defined as the shortest possible cycle when it visits one collection point of the segments and returns to its initial position. A MDC must pass within the transmission range of a collection point so that data exchange can take place. There are two types of tour in this paper: traveling along the edges or along the triangles. The computation depends on the number of segments in a tour as follows.

Traveling along an Edge. This case is shown in Figure 4(a). The MDC will move back and forth between $s_1$ and $s_2$ to exchange data. Let d denote the Euclidean distance of $s_1$ and $s_j$ , where $d>2R$ ; then the tour length is $d-2R$ .

Figure 4

Determining MDCs tours.

Traveling along a Triangle. When a MDC travels among three segments, OACRS constructs a triangle tour path, as shown in Figure 4(b). O is the center of gravity of the triangle $(s_1,s_2,s_3)$ . The intersection point of transmission disc of $s_i$ with the line connecting it to O serves as a tour stop for the MDC, where $s_i\in \{s_1,s_2,s_3\}$ . The tour path is expressed by the dotted triangle in Figure 4(b).

5. Performance Validation

The performance of OACRS is validated through simulation. In this section we discuss the simulation environment, performance metrics, and simulation results.

5.1. Experiment Setup and Performance Metrics

In the simulation experiments, segments are randomly placed in an area of 1500 m × 1500 m with one obstacle. The number of segments “n” is varied from 3 to 13. The communication range “R” for the collection points and MDCs has been set to 60, 80, 100, 120, 140, and 160. When changing the number of segments, the communication range R is fixed at 100 m; and the segments count is set to 8 while varying the communication range. In our simulation we set the number of available relays using the following formula:

$$\begin{array}{cc}& \mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}=\mathrm{R}{\mathrm{N}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}\ast p,\end{array}$$

(6)

where $0<p<1$ . We repeat the experiment for different p values (0.6, 0.7, and 0.8) for a fair comparison, and $\mathrm{R}{\mathrm{N}}_{\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}}$ is kept greater than or equal to the number of segments. We use the total tour length and maximum tour length as the performance metrics:

• (i)

  Total tour length is the sum of distances traveled by all employed MDCs. Our goal is to minimize this metric in order to limit the overhead imposed on the MDCs.

• (ii)

  Maximum tour length is the longest distance among all MDCs tours. This metric indicates the load that one of the MDCs will experience, and a large value indicates increased energy consumption, which would affect the rate of energy depletion and the node lifetime. The goal is to minimize this distance.

In our experiment, each individual simulation experiment involves 30 different topologies and the average result is reported.

5.2. Experiment Results

5.2.1. Total Tour Length

Figure 5 shows the effects of different parameters on total tour length. As shown in Figures 5(a) and 5(b), we can see that the total tour length decreases as the value of p increases. This is because the number of nodes which act as MDCs can be reduced when there are more available relays. Thus, the sum of tour length of all MDC will be reduced. From Figure 5(a), we observer that the changing of total tour length is not too large in whole while the number of segments increases, which indicates that the number of segments is not strict in OACRS. Figure 5(b) shows that the total tour length decreases as the values of communication range increase. This is because OACRS optimized MDCs tours, and the tour length from one segment to another is $d-2R$ , where d is the Euclidean distance between the two segments.

Figure 5

Total tour length with varying number of segments and communication range.

5.2.2. Maximum Tour Length

Figure 6 shows the trend of maximum tour length with varying number of segments and communication range. As shown in Figures 6(a) and 6(b), we can see that the maximum tour length decreases as the value of p increases in most cases. This is because the smaller p is, the smaller the number of available relays is; then the distance of each MDC is increased. Thus, the maximum tour length increases as p decreases. From Figure 6(a), we can observe that the maximum tour length decreases as the number of segments increases, which is because the long tour decreases in dense networks. And we can observe in Figure 6(b) that the maximum tour length decreases as communication range increases, which is also because OACRS optimized MDCs tours, and when communication range increases, the value of $d-2R$ is decreased.

Figure 6

Maximum tour length with varying number of segments and communication range.

5.2.3. Comparison with FeSMoR

We compare the performance of OACRS with that of FeSMoR, which also uses mix of mobile and stationary relays to restore connectivity of WSNs. With the same setup, the results for the total tour length and the maximum tour length are shown in Figures 7(a) and 7(b), respectively. As can be seen from Figures 7(a) and 7(b), when the number of segments is more than 8, OACRS outperforms FeSMoR in terms of both total tour length and maximum tour length, which confirms that OACRS is more suitable for the case that the distance between segments is not too large.

Figure 7

Total tour length and maximum tour length comparing with FeSMoR.

6. Conclusion

Restoring network connectivity is crucial to ensure the WSNs functions effectively. In this paper, we studied the connectivity restoration problem of WSNs, where obstacles are considered when MDCs are traveling.

We have proposed OACRS, an obstacle aware connectivity restoration strategy. OACRS firstly constructs and optimizes the obstacle-avoiding minimum spanning tree among the segments and then determines the placement of relay nodes. We further optimize the tour path of MDCs to minimize the touring length. The simulation results have confirmed the effectiveness of OACRS. Our future work is to evaluate the performance of the proposed approaches when there is more than one obstacle and considering the signal interference.