Restoration Strategy Based on Optimal Relay Node Placement in Wireless Sensor Networks

Abstract

In wireless sensor networks (WSNs), connecting disjoint segments is significant for network restoration, especially in some mission critical applications. However, the variability of distances between disjoint segments has tremendous influence on relay nodes deployment. In fact, finding the optimal solution for connecting disjoint segments in terms of the number and positions of relay nodes is NP-hard. To address this issue, plenty of heuristics, such as STP-MSP (Cheng et al., 2008), MST-1tRN (Lloyd et al., 2007), and CORP (Lee and Younis, 2010) are deeply pursued. In this paper, we propose a distributed restoration algorithm based on optimal relay node placement (simply, ORNP). It aims at federating separated segments by populating the minimum number of relay nodes in a WSN that has suffered a significant damage. In addition, both of complexity and upper bound of the relay count for ORNP are explored. The simulation results show that ORNP performs better than STP-MSP, MST-1tRN, and CORP in terms of relay count and the connectivity of resulting topology.

1. Introduction

Wireless sensor networks (WSNs) are well-known by the significant advantage in monitoring space, such as battlefield surveillance, environment monitoring, and biological detection [1–3]. To accomplish such surveillance missions, a large amount of sensors are intentionally placed over a geographic area (called the area of interest, $\mathrm{A}\mathrm{O}\mathrm{I}$ ) to monitor certain events. In general, a sensor node is powered by the battery with a limited capacity. And the majority of energy consumption results from communication. Because of such energy constraint, a large number of sensors are deployed for area coverage. In fact, such deployment will facilitate the surveillance mission. For example, all sensors can be easily coordinated to forward gathered data to a base station along a multihop wireless path. In this case, the reachability between any pair of sensors is required which implies the importance of the connectivity in $\mathrm{W}\mathrm{S}\mathrm{N}$ s.

Due to this special network architecture, $\mathrm{W}\mathrm{S}\mathrm{N}$ s are subject to damage that can partition the network into disjoint segments. In Figure 1, the dark areas represent the extent of the damage that partitions the surviving sensors into several disconnected segments. In particular, the network is performing critical tasks, such as forecasting the activity of volcano and monitoring the security status of a border. In these scenarios, all important data are shared to coordinate the action of the segments. Thus restoring connectivity for a disconnected $\mathrm{W}\mathrm{S}\mathrm{N}$ is crucial.

Figure 1

Segments discovery in a damaged $\mathrm{W}\mathrm{S}\mathrm{N}$ .

Some distributed algorithms in references [4, 5] have been designed to relocate some operational nodes such that the network becomes connected. However the algorithms are inappropriate to connectivity restoration for a severely damaged network.

Unlike those algorithms above, this paper aims to design an efficient algorithm that deploys the minimum number of relay nodes ( $\mathrm{R}\mathrm{N}\mathrm{s}$ ) to connect the disjoint network segments. Similarly, Lin and Xue [6] mapped such optimal relay nodes deployment problem into establishing the Steiner minimum tree with a minimum number of Steiner points. They also proved the NP hardness of this problem.

Our Contribution. This paper presents a polynomial-time algorithm, namely, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ , that opts to seek the minimum number of relays required for establishing a connected intersegment topology through the following steps.

• (1)

We subdivide the area of interest $\mathrm{A}\mathrm{O}\mathrm{I}$ into clusters through Voronoi partition that the virtual backbone is built by the collaboration of all cluster heads.

(2)

A novel strategy for relay nodes selection among cluster members, with respect to the properties of Global Voronoi Coverage, is proposed to execute the prerestoration of a disconnected network.

(3)

The $\mathrm{3}\text{-}star$ technology is applied to further decrease the number of disjoint segments by recursively deploying one relay node for every three separated segments.

(4)

We propose a geometrical center based algorithm that places relay nodes toward the center of mass of the polygon formed by the remaining disjoint segments to achieve the connectivity of the entire network.

The rest of the paper is organized as follows. Related work is covered in Section 2. The federation problem and Voronoi coverage based system model are described in Section 3. The algorithm $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is elaborated in Section 4. Section 5 gives the theoretical analysis on upper bound of $\mathrm{R}\mathrm{N}$ count and complexity of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ . And the validation results are presented in this section as well. We conclude this paper in Section 6.

2. Related Work

There are two categories of heuristics pursued for federating segmented $\mathrm{W}\mathrm{S}\mathrm{N}$ s [7]: the first category is about establishing connectivity by populating extra relay nodes and the second one is transporting data between segments through mobile agents.

Previous work on $\mathrm{R}\mathrm{N}$ placement can be classified into two categories. The first strives to establish connectivity between end points [8] in unconstrained network. In the second category, a higher degree of connectivity as an additional performance objective is pursued in [9, 10]. In [8], Lloyd and Xue designed $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}1t\mathrm{R}\mathrm{N}$ that is based on constructing a minimum Steiner tree with minimum number of Steiner points by a geometric disk cover algorithm. Lee and Younis proposed $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ and $\mathrm{O}\mathrm{R}\mathrm{C}$ [11, 12]. Both of $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ and $\mathrm{O}\mathrm{R}\mathrm{C}$ model the network as a grid of equal-sized squares (cells) with all segments and relays located at the center of cells. $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ works in rounds. In each round, it chooses a neighbor cell that is the closest to the other segments to place a relay node. Unlike $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ , $\mathrm{O}\mathrm{R}\mathrm{C}$ works in two phases: (1) identifying Steiner points ( $\mathrm{S}\mathrm{P}$ s) at which $\mathrm{R}\mathrm{N}$ s would be populated to minimize the number of deployed $\mathrm{R}\mathrm{N}$ s for connecting segments and (2) for every three neighboring boundary segments identified, deploying an additional $\mathrm{R}\mathrm{N}$ to form a connected $inter\text{-}\mathrm{S}\mathrm{P}$ topology. These two steps are repeated recursively, until all segments are united. We improve $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ and propose $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ that tends to provide a better performance than $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ . The details of performance comparison are discussed in Section 5.

To achieve higher connectivity [9, 10, 13], Tang et al. connected each sensor to at least two $\mathrm{R}\mathrm{N}$ s with a minimum number of $\mathrm{R}\mathrm{N}$ s involved. And he achieved the $\mathrm{2}\text{-}connected\hspace{0.17em}\hspace{0.17em}inter\text{-}\mathrm{R}\mathrm{N}$ network [9]. Younis et al. proposed a heuristic $\mathrm{2}C\text{-}SpiderWeb$ [13] that establishes an $inter\text{-}segment$ topology such that each segment at the perimeter is connected to two distinct $\mathrm{R}\mathrm{N}$ s on the inner mesh through 2 disjoint paths. Meanwhile, different transmission radiuses of heterogeneous nodes are considered by Han et al. in [10]. They opted to establish $k\text{-}vertex$ disjoint paths by deterministically populating the minimum number of additional $\mathrm{R}\mathrm{N}\mathrm{s}$ .

Furthermore, all three networks, sparse mobile ad hoc networks, delay tolerant networks, and fragmented sensor networks, employ mobile nodes for data delivery. As a mobile node, it plays one of three roles: a collector that tours the sensors and carries their data, a base station that processes the data, or a relay that forwards data from one node to another [14, 15]. Furthermore, mobile nodes are deployed to link disjoint nodes as data forwarders [16] or to increase the lifetime of a network that consists of stationary sensors [17]. In [18], Senel and Younis designed a heuristic $IDM\text{-}kMDC$ that finds $k\text{-}subsets$ of segments, computes an optimized tour for each subset, and assigns one mobile data collector for each tour. Compared with these strategies that may study the effect of the number of nodes, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ only concerns minimizing the $\mathrm{R}\mathrm{N}$ count.

3. Preliminary

In this section, we first give the notations and assumptions and then present the network model and the problem statement.

3.1. Notions and Terminologies

We use the following notations throughout the paper:

• (i)

$r_c$ : the maximum communication range of sensor nodes,

(ii)

$r_s$ : the sensing range of sensor nodes,

(iii)

$d(s_i,s_j)$ : the Euclidean distance between two points $s_i$ and $s_j$ ,

(iv)

$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{k}(u)$ : the sensing disk of node u that is a closed disk centered at point u with radius $r_s$ ,

(v)

$S_i$ : the $i\mathrm{t}\mathrm{h}$ segment,

(vi)

S: the set of $S_i$ required to be connected,

(vii)

$R(S_i)$ : the sensor node that represents the segment $S_i$ ,

(viii)

$C_i$ : the $i\mathrm{t}\mathrm{h}$ cluster,

(ix)

$\mathrm{C}{\mathrm{H}}_i$ : the cluster head of the $i\mathrm{t}\mathrm{h}$ cluster,

(x)

$\mathrm{S}\mathrm{P}\mathrm{G}$ : the smallest polygon which includes all $R(S_i)$ ,

(xi)

$BR$ : the segment that lies on the perimeter of $\mathrm{S}\mathrm{P}\mathrm{G}$ ,

(xii)

$\mathrm{C}\mathrm{o}\mathrm{M}$ : the center of mass of $\mathrm{S}\mathrm{P}\mathrm{G}$ .

All sensor nodes deployed in $\mathrm{A}\mathrm{o}\mathrm{I}$ are assumed homogeneous; that is, $r_c$ and $r_s$ are the same for all nodes. If the Euclidean distance between two nodes is not greater than $r_c$ , they can directly exchange messages. A sensor node can perfectly monitor (or cover) a point in the plane, if their Euclidean distance is not greater than $r_s$ .

The Voronoi partition is a well-known geometric structure that has been applied to network clustering. For example, Voronoi trees [19] have been proposed to answer reverse nearest neighbour ( $\mathrm{R}\mathrm{N}\mathrm{N}$ ) queries [20]. Given a set of data points and a query point q, the $\mathrm{R}\mathrm{N}\mathrm{N}$ problem [21] is to find all the data points whose nearest neighbour is q. There are three formal definitions associated with Voronoi partitions.

Definition 1 (see [22]).

Given a set S of n sites $s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_n$ in a plane $R^{\mathrm{2}}$ , their Voronoi partition is defined as the subdivision of the plane into n cells, one for each site, with the property that any point in the cell corresponding to a site is closer to that site than to any other site. Formally, the Voronoi cell corresponding to site $s_i$ is defined as

$$\begin{array}{l}V\left(R^{\mathrm{2}},S,s_i\right)\\ =\text{AOI}{\displaystyle \bigcap }\left({\displaystyle \bigcap }_{j=\mathrm{1},j\ne i}^n\left\{x\hspace{0.17em}|\hspace{0.17em}d\left(s_i,x\right)\le d\left(s_j,x\right)\right\}\right).\end{array}$$

(1)

In addition, two Voronoi cells meet along a Voronoi edge, and three Voronoi cells meet at a Voronoi vertex. We call a site a neighbor of another site if the Voronoi cells of the two sites share an edge.

Definition 2 (see [23]).

The Voronoi cell $V(R^{\mathrm{2}},S,s_i)$ is said to satisfy the local Voronoi coverage, if every point $p\in V(R^{\mathrm{2}},S,s_i)$ is covered by $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{k}(s_i)$ .

Definition 3 (see [23]).

If every Voronoi cell $V(R^{\mathrm{2}},S,s_i)$ satisfies the local Voronoi coverage where $\mathrm{1}\le i\le \left|S\right|$ , then the area is said to satisfy the global Voronoi coverage.

As shown in Figure 2(a), the black solid points and hollow points denote the predetermined nodes and ordinary nodes, respectively, while the rectangle represents the $\mathrm{A}\mathrm{O}\mathrm{I}$ . And the Voronoi cell corresponding to site $s_i$ is the polygon formed by Voronoi vertices, for example, the Voronoi cell of $\mathrm{6}$ is the polygon formed by Voronoi vertices $\mathrm{1}$ , $\mathrm{2}$ , $\mathrm{3}$ , $\mathrm{4}$ , and $\mathrm{5}$ . Figure 2(b) shows the global Voronoi coverage for all $\mathrm{6}$ Voronoi cells.

Figure 2

Voronoi partition and global Voronoi coverage.

Since $\mathrm{C}\mathrm{o}\mathrm{M}$ based restoration is a part of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ , we recall two definitions about geometrical center as follows.

Definition 4 (see [24]).

Given an arbitrary nonempty finite multiset P in $R^{\mathrm{2}}$ , an Euclidean median of P is a point in $R^{\mathrm{2}}$ , denoted as $M(P)$ , that minimizes ${\sum }_{p\in P}‖x-p‖$ , when $x=M(P)$ .

We denote $L_M={\sum }_{p\in P}‖M(P)-p‖$ as the sum of the distance from $M(P)$ to all points in P.

Definition 5 (see [24]).

Given an arbitrary nonempty finite multiset P in $R^{\mathrm{2}}$ , the centre of mass of P is the function whose value, denoted by $C(P)$ , is the point in $R^{\mathrm{2}}$ given by $C(P)=\left(\mathrm{1}/\left|P\right|\right){\sum }_{p\in P}p$ .

We denote $L_C={\sum }_{p\in P}‖C(P)-p‖$ as the sum of the distance from $C(P)$ to all points in P.

Throughout this paper, we assume the entire area satisfies the global Voronoi coverage (see Figure 2(b)). The rationale is that if the sensing disks of some predetermined sensors can provide complete coverage of the entire area that implies the effective area surveillance, the area of interest is initially subdivided into clusters by Voronoi partition with respect to the positions of some predetermined sensor nodes (cites). Furthermore for each Voronoi cell (cluster), the corresponding sensor is nominated as the cluster head while the other sensors within the cell serve as cluster members; that is, there are six clusters $C_{\mathrm{1}}$ , $C_{\mathrm{2}}$ , $C_{\mathrm{3}}$ , $C_{\mathrm{4}}$ , $C_{\mathrm{5}}$ , and $C_{\mathrm{6}}$ constructed through Voronoi Partition as shown in Figure 2(b). By doing so, the cluster heads can coordinate their cluster members to execute a particular task. While the partition is established, all cluster heads form an virtual backbone that forwards collected data to the base station ( $\mathrm{B}\mathrm{S}$ ) as shown in Figure 3.

Figure 3

The virtual backbone constructed through Voronoi partition.

Note that although a sensor node could locate within two cluster heads’ sensing area, every sensor can only join one cluster and send all data toward its cluster head. The rationale for that is that two copies of the same data collected by a cluster member are possibly sending towards two cluster heads such that the redundant data could travel through the virtual backbone.

It is worth mentioning that it is pointed out in [25] that the specification of $r_c=\mathrm{2}{r}_s$ holds for most commercially available sensors such as Berkeley Motes. Both Zhang and Hou [25] and Wang et al. [26] prove that if the transmission range of sensors equals or exceeds twice their sensing range, coverage implies connectivity. However we set $r_c\le \mathrm{2}{r}_s$ throughout the rest of the paper, because we consider the scenario that some nodes have to play the role of gateways to ensure connectivity of the virtual backbone such that the collected data can be relayed from one cluster head to the other.

3.2. Segment Federation Problem

In this paper, we only consider the disjoint $\mathrm{W}\mathrm{S}\mathrm{N}$ s. In this scenarios, nodes do not have mobility and all communication links are assumed bidirectional.

3.2.1. Representative Nodes Localization

For any segment $S_i$ , we designate only one representative node $R(S_i)$ . Note that $R(S_i)$ cannot be determined by a remote command center because of the damage to the communication of the network. Thus, to design a scheme for the nomination of representatives is imperative. However, we need to make sure all surviving sensors should have the knowledge of the network partitioned into segments. In Figure 1, the nodes closest to the damage area, for simplicity we call them border nodes, can easily detect the failure of communication with their neighbors. Actually once the communication of a border node with some of its neighbors is down and no more messages received from that on, it will notify all reachable nodes that a major damage has taken place which is the cause of consecutive node failures.

Then by simply observing the notification messages flooded in the segment, the border node that has most neighbors is selected as a representative. The rationale of the representative selection is that new $\mathrm{R}\mathrm{N}\mathrm{s}$ are deployed in the vicinity of these border nodes such that the network topology can be restored to its prefailure status as similar as possible. In Figure 1, five representatives, denoted by black nodes, are selected for five segments $S_{\mathrm{0}}$ , $S_{\mathrm{1}}$ , $S_{\mathrm{2}}$ , $S_{\mathrm{3}}$ , and $S_{\mathrm{4}}$ . And they will broadcast their locations to the other nodes in the segments. The problem of federating the five segments shown in Figure 1 is now mapped to reconnecting $R(S_i)$ ,   $i=\mathrm{0},\dots ,\mathrm{4}$ .

3.2.2. Relay Nodes Deployment

Throughout this paper, we assume relay nodes which have the same communication range R as that of sensor only forward data. Since relays are more expensive, the number of deployed relays is to be minimized and they should be populated carefully. Cheng et al. formulate placing the fewest relays to connect nodes as finding the Steiner minimum tree with a minimum number of Steiner points and bounded edge length [27]. Lin and Xue proved that this problem is NP-hard [6]. Therefore heuristics are pursued in this paper.

4. The ORNP Approach

The proposed $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ approach applies greedy heuristics that work in rounds until all segments are federated. First we will introduce $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ as a centralized procedure, and then the distributed $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is elaborated in Section 4.2. The framework of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is shown in Figure 4.

Figure 4

The framework of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ .

4.1. Major Steps of ORNP

4.1.1. Voronoi Partition Based Prerestoration Phase (VP)

The area of interest is subdivided into clusters through Voronoi partition with some sensor nodes (cites) predetermined. And in each Voronoi cell, the cluster head and cluster members are chosen as we assumed in Section 3.1. Furthermore some cluster members play the role of gateways due to the fact that the maximum communication range of a sensor is assumed less than two times of its sensing range. While the entire network breaks down into disjoint segments, we try to locate a sensor node s covered by at least two distinct cluster heads $C_i$ and $C_j$ , where $i\ne j$ , $C_i\in S_i$ , and $C_j\in S_j$ . Then s is designated as a relay to federate $S_i$ and $S_j$ . It is worth mentioning that there could be more than one sensor node, that is, $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ , covered by at least two distinct cluster heads $C_i$ and $C_j$ . In this case, we need to know which sensor is closer to the $\mathrm{C}\mathrm{o}\mathrm{M}$ of $\mathrm{S}\mathrm{P}\mathrm{G}$ that consists of disjoint segments. Because once several segments merge into one through the gateway, the position of the gateway could possibly become the nearest point to the $\mathrm{C}\mathrm{o}\mathrm{M}$ that directly shortens the distances from all resulting disjoint segments to the $\mathrm{C}\mathrm{o}\mathrm{M}$ for the next stage restoration. Thus if $d(s_{\mathrm{1}},\mathrm{C}\mathrm{o}\mathrm{M})<d(s_{\mathrm{2}},\mathrm{C}\mathrm{o}\mathrm{M})$ , then $s_{\mathrm{1}}$ is a proper choice for the gateway. Intuitively, the selection of this kind of sensor nodes instead of populating new ones can significantly reduce the number of disjoint segments that require federation. As shown in Figure 5(a), there are three clusters $C_{\mathrm{1}}$ , $C_{\mathrm{2}}$ , and $C_{\mathrm{3}}$ with $\mathrm{1}$ , $\mathrm{2}$ , and $\mathrm{3}$ as their cluster heads, respectively. And the virtual backbone consists of three cluster heads and one relay; for example, each of $\mathrm{1}$ , $\mathrm{2}$ , and $\mathrm{3}$ is connected by the relay node $\mathrm{4}$ . However, if sensor node $\mathrm{4}$ breaks down, then $\mathrm{1}$ , $\mathrm{2}$ , and $\mathrm{3}$ are disconnected. In Figure 5(b), there are two sensor nodes covered by three cluster headers; that is, sensor $\mathrm{5}$ is covered by $\mathrm{1}$ and $\mathrm{3}$ , while sensor $\mathrm{6}$ is covered by $\mathrm{2}$ and $\mathrm{3}$ . Therefore both sensors $\mathrm{5}\in C_{\mathrm{1}}$ and $\mathrm{6}\in C_{\mathrm{3}}$ are chosen to federate three cluster heads $\mathrm{1}$ , $\mathrm{2}$ , and $\mathrm{3}$ .

Figure 5

The selection of relay nodes.

Figure 4 shows how Voronoi partition based prerestoration federates disjoint segments with the sensor nodes (cluster members) covered by at least two cluster heads. There are 27 disjoint segments that required federation as shown in Figure 6(a). The black nodes denote the cluster members covered by at least two cluster heads (see Figure 6(b)). They are chosen as relays to joint the corresponding cluster heads such that the number of separated segments is reduced from 27 to 11, as shown in Figure 6(c).

Figure 6

Voronoi partition based prerestoration (VP).

4.1.2. CoM Based Restoration Phase (CR)

After the prerestoration phase, we strive to further reduce the number of disjoint segments by establishing as many $\mathrm{3}\text{-}star$ s as possible. A $\mathrm{3}\text{-}star$ is the structure that a relay is placed to joint three separated segments. There are still $\mathrm{11}$ disjoint segments left (see Figure 7(a)). We build three $\mathrm{3}\text{-}star$ s such that the total number of disjoint segments is reduced by $\mathrm{6}$ . Note that although we try to build $\mathrm{3}\text{-}star$ as many as possible, if a deployed $\mathrm{R}\mathrm{N}$ can connect more than three separated segments, then all disjoint segments adjacent to this specific $\mathrm{R}\mathrm{N}$ can be federated. In fact, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ requires less $\mathrm{R}\mathrm{N}$ , if more $\mathrm{R}\mathrm{N}$ s adjacent to more than three separated segments are populated.

Figure 7

CoM based restoration (CR).

Once all $\mathrm{3}\text{-}star$ s are discovered, there will be no more segments that can be federated by deploying only one relay. Then we calculate the $\mathrm{C}\mathrm{o}\mathrm{M}$ of smallest polygon which includes all remaining segments, using the following formula [28], where $c_x$ and $c_y$ are coordinates of the $\mathrm{C}\mathrm{o}\mathrm{M}$ and $x_i$ and $y_i$ are coordinates of the segment $S_i$ :

$$\begin{array}{cc}& \text{Area}\left(A\right)=\frac{\mathrm{1}}{\mathrm{2}}{\displaystyle \sum }_{i=\mathrm{0}}^{n-\mathrm{1}}\left(x_i{y}_{i+\mathrm{1}}-x_{i+\mathrm{1}}{y}_i\right),\\ c_x=\frac{\mathrm{1}}{\mathrm{6}A}{\displaystyle \sum }_{i=\mathrm{0}}^{n-\mathrm{1}}\left(x_i+x_{i+\mathrm{1}}\right)\left(x_i{y}_{i+\mathrm{1}}-x_{i+\mathrm{1}}{y}_i\right),\\ c_y=\frac{\mathrm{1}}{\mathrm{6}A}{\displaystyle \sum }_{i=\mathrm{0}}^{n-\mathrm{1}}\left(y_i+y_{i+\mathrm{1}}\right)\left(x_i{y}_{i+\mathrm{1}}-x_{i+\mathrm{1}}{y}_i\right).\end{array}$$

(2)

The rationale is that placing $\mathrm{R}\mathrm{N}\mathrm{s}$ toward the $\mathrm{C}\mathrm{o}\mathrm{M}$ will significantly decrease the number of $\mathrm{R}\mathrm{N}\mathrm{s}$ required for segment federation. Note that the CoM based Restoration Phase works in rounds. In each round, every $R_i$ first checks whether it can reach any $\mathrm{R}\mathrm{N}$ which may have been populated from another segment j, where $i\ne j$ . If there is no $\mathrm{R}\mathrm{N}$ reachable, then $R_i$ places a relay node toward $\mathrm{C}\mathrm{o}\mathrm{M}$ . Note that each $\mathrm{R}\mathrm{N}$ placed by $R_i$ will become new representative of $S_i$ and every two $\mathrm{R}\mathrm{N}$ s should be placed at $r_c$ interval. It is worth mentioning that while two or more $R_i\mathrm{s}$ meet, the corresponding $S_i\mathrm{s}$ merge into a new segment and the closest $R_i$ to the $\mathrm{C}\mathrm{o}\mathrm{M}$ is chosen as the representative of the new segment. Then the rest segments are excluded from the next round deployment. The whole phase will recursively deploy relays until all disjoint segments connect with each other. As shown in Figure 7(b), five segments $R_{\mathrm{1}}$ , $R_{\mathrm{2}}$ , $R_{\mathrm{3}}$ , $R_{\mathrm{4}}$ , and $R_{\mathrm{5}}$ are deploying relays toward the $\mathrm{C}\mathrm{o}\mathrm{M}$ , where $R_i^j$ denotes the relay deployed by $R_i$ in the $j\mathrm{t}\mathrm{h}$ round. It is clear that the relay $R_{\mathrm{2}}^{\mathrm{2}}$ can reach $R_{\mathrm{1}}^{\mathrm{2}}$ , while $R_{\mathrm{3}}^{\mathrm{2}}$ is within the communication range of $R_{\mathrm{4}}^{\mathrm{2}}$ in the second round. Therefore $R_{\mathrm{2}}^{\mathrm{2}}$ and $R_{\mathrm{1}}^{\mathrm{2}}$ merge into one segment, so do $R_{\mathrm{3}}^{\mathrm{2}}$ and $R_{\mathrm{4}}^{\mathrm{2}}$ . Compared with $R_{\mathrm{1}}^{\mathrm{2}}$ and $R_{\mathrm{4}}^{\mathrm{2}}$ , $R_{\mathrm{2}}^{\mathrm{2}}$ and $R_{\mathrm{3}}^{\mathrm{2}}$ are closer to $\mathrm{C}\mathrm{o}\mathrm{M}$ . Hence $R_{\mathrm{2}}^{\mathrm{2}}$ will represent $R_{\mathrm{1}}$ and $R_{\mathrm{2}}$ , while $R_{\mathrm{3}}^{\mathrm{2}}$ represents $R_{\mathrm{3}}$ and $R_{\mathrm{4}}$ for the next round deployment (see Figure 7(c)). Before relays reach the $\mathrm{C}\mathrm{o}\mathrm{M}$ , $R_{\mathrm{2}}^{\mathrm{3}}$ , $R_{\mathrm{3}}^{\mathrm{3}}$ , and $R_{\mathrm{5}}^{\mathrm{3}}$ are capable of communicating with each other; therefore all those $\mathrm{5}$ disjoint segments are connected in three rounds (see Figure 7(d)). And the resulting topology is shown in Figure 8. We will analyze the quality of the resulting topology in Section 5.

Figure 8

The resulting topology through $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ .

4.2. Distributed Implementation

This section describes how $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is implemented in a distributed manner. First, we assume the area is partitioned into clusters through Voronoi partition before it is inflicted with major damage. Every cluster is considered as a segment with its cluster head chosen as the representative. The smallest polygon $\mathrm{S}\mathrm{P}\mathrm{G}$ on current set of representatives is calculated and the positions of $\mathrm{B}\mathrm{R}\mathrm{s}$ are broadcasted to all sensors as the initial status of the network. For simplicity, we call two cluster heads connecting with each other directly or through relay neighbors.

While the networks are partitioned into disjoint segments due to the major damage, each segment $S_i$ will broadcast a federation request to all cluster head $C_i$ s within $S_i$ . For each cluster head $C_i\in S_i$ , communication with all its Voronoi neighbors is established. Once a cluster head $\mathrm{C}{\mathrm{H}}_i\in S_i$ fails to communicate with at least one of its Voronoi neighbors, $\mathrm{C}{\mathrm{H}}_i$ will try to broadcast gateway spotting message to all its cluster members. If some active cluster members of $\mathrm{C}{\mathrm{H}}_i$ can still contact with $\mathrm{C}{\mathrm{H}}_j$ of $S_j$ , they will respond to federation acknowledgement messages. Then $\mathrm{C}{\mathrm{H}}_i$ randomly chooses one of those cluster members to play the role of gateway such that $\mathrm{C}{\mathrm{H}}_i$ and $\mathrm{C}{\mathrm{H}}_j$ are united.

After the prerestoration phase, each segment $S_i$ chooses a sensor as its representative $R_i$ and then broadcasts the location of $R_i$ . Although each $R_i$ does not know the locations of the other $R_i\mathrm{s}$ , it assumes being a $BR$ and calculating the $\mathrm{C}\mathrm{o}\mathrm{M}$ of the $\mathrm{S}\mathrm{P}\mathrm{G}$ with respect to the positions of itself and all initial $\mathrm{B}\mathrm{R}\mathrm{s}$ that lost connections due to the damage. Then every $R_i$ starts to place relays toward $\mathrm{C}\mathrm{o}\mathrm{M}$ and each $\mathrm{R}\mathrm{N}$ placed by $R_i$ will become new representative of $S_i$ . While two or more $R_i\mathrm{s}$ meet, the corresponding $S_i\mathrm{s}$ merge into a new segment and the closest $R_i$ to the $\mathrm{C}\mathrm{o}\mathrm{M}$ is chosen as the representative of the new segment. Then the rest segments stop to deploy $\mathrm{R}\mathrm{N}\mathrm{s}$ toward the $\mathrm{C}\mathrm{o}\mathrm{M}$ . Each $R_i$ will recursively deploy relays until all disjoint segments connect with each other. Note that, without the knowledge of precise positions of neighbor representatives, there is no way to directly build the $\mathrm{3}\text{-}star$ . However the $\mathrm{3}\text{-}star$ s still can be constructed during the $\mathrm{R}\mathrm{N}$ deployment.

Intuitively, the implementation of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ in distributed way may result in more $\mathrm{R}\mathrm{N}$ s populated. However, once $\mathrm{R}\mathrm{N}$ s are deployed, any two disjoint segments can be united. And the communication in a $\mathrm{W}\mathrm{S}\mathrm{N}$ is restored.

5. Performance Evaluation

5.1. Theoretical Analysis

The correctness, complexity, and approximation ratio of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ are analysed in this subsection. First we give the following theorems and lemmas.

Theorem 6.

If the area A satisfies the global Voronoi coverage, then there exists at least one sensor node $s\in C_i$ for each $C_i\in A$ , such that s is covered by $C_i$ , $C_j$ , and $C_k$ , where $i\ne j\ne k$ .

Proof.

Based on the definition of Voronoi Partition, the position of a Voronoi vertex v is the intersection point of three Voronoi edges which is shared by $\mathrm{3}$ pairs of Voronoi neighbors; that is, $d(v,\mathrm{C}{\mathrm{H}}_{\mathrm{1}})<r_s$ , $d(v,\mathrm{C}{\mathrm{H}}_{\mathrm{2}})<r_s$ , and $d(v,\mathrm{C}{\mathrm{H}}_{\mathrm{3}})<r_s$ . As shown in Figure 5(a), sensor $\mathrm{4}$ is covered by three cluster heads $\mathrm{1}$ , $\mathrm{2}$ , and $\mathrm{3}$ . Therefore the sensor $s\in V(A,S,\mathrm{C}{\mathrm{H}}_{\mathrm{1}})$ located in the position of v is covered by $\mathrm{C}{\mathrm{H}}_{\mathrm{1}}$ , $\mathrm{C}{\mathrm{H}}_{\mathrm{2}}$ , and $\mathrm{C}{\mathrm{H}}_{\mathrm{3}}$ .

Theorem 7 (see [24]).

The centre of mass provides a $(\mathrm{2}-\mathrm{2}/n)$ -approximation of the Euclidean median, where n denotes the number of points.

We denote the optimal solution to the federation problem on a set S of disjoint segments $\mathrm{O}\mathrm{p}\mathrm{t}\left(S\right)$ . The number of relays deployed by $\mathrm{O}\mathrm{p}\mathrm{t}$ is denoted by $\left|\mathrm{O}\mathrm{p}\mathrm{t}(S)\right|$ , while $\left|\mathrm{M}\mathrm{S}\mathrm{T}(S)\right|$ denotes the number of relays placed along the edges of the $\mathrm{M}\mathrm{S}\mathrm{T}$ on set S. Furthermore, we call a $\mathrm{M}\mathrm{S}\mathrm{T}$ of the resulting topology through $\mathrm{O}\mathrm{p}\mathrm{t}(S)$ an optimal $\mathrm{M}\mathrm{S}\mathrm{T}$ ( $\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}(S)$ ). The total length of edges in $\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}(S)$ and $\mathrm{M}\mathrm{S}\mathrm{T}(S)$ is denoted by $L_{\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}(S)}$ and $L_{\mathrm{M}\mathrm{S}\mathrm{T}(S)}$ , respectively. Obviously, $\left|\mathrm{O}\mathrm{p}\mathrm{t}(S)\right|\le \left|\mathrm{M}\mathrm{S}\mathrm{T}(S)\right|$ always holds which implies that $L_{\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}(S)}\le L_{\mathrm{M}\mathrm{S}\mathrm{T}(S)}$ due to $\mathrm{R}\mathrm{N}\mathrm{s}$ are populated at the interval of $r_c$ .

Theorem 8.

The number of relays deployed by $ORNP$ is less than $\mathrm{3}$ times that of $Opt$ .

Proof.

The $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ is a 3-approximation algorithm. It first combines nodes that can directly merge each other into one group. Then for every three groups, it seeks a position S that is at most R units away and place a $\mathrm{R}\mathrm{N}$ in S to merge three groups into one. These steps are repeated until no such position could be found. Then each group is represented as a point p and an $\mathrm{M}\mathrm{S}\mathrm{T}$ is constructed based on a set P of point p, denoted by $\mathrm{M}\mathrm{S}\mathrm{T}(P)$ . Thus the number of relays populated equals the sum of the number of S and $⌈\mathrm{L}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(e)/r_c⌉-\mathrm{1}$ relays populated on each edge, e, of the computed $\mathrm{M}\mathrm{S}\mathrm{T}$ . Although $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ establishes $\mathrm{3}\text{-}star$ s on a set $S_p$ of disjoint segments as $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ , relays are deployed towards the $\mathrm{C}\mathrm{o}\mathrm{M}$ of the $\mathrm{S}\mathrm{P}\mathrm{G}$ formed by the set $S_r$ of remaining disconnected segments instead of deploying $\mathrm{R}\mathrm{N}\mathrm{s}$ along the edges of $\mathrm{M}\mathrm{S}\mathrm{T}$ on $S_r$ . Note that $\left|S_r\right|+\left|S_p\right|=N$ , where N denotes the total number of disjoint segments.

For simplicity, we let $L_{\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}(S_r)}=L_{\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}}$ , $L_{\mathrm{M}\mathrm{S}\mathrm{T}(S_r)}=L_{\mathrm{M}\mathrm{S}\mathrm{T}}$ , $L_{C(S_r)}=L_C$ , and $L_{M(S_r)}={\mathrm{L}}_M$ . According to Definitions 4 and 5 and Theorem 7, we have $L_M\le L_{\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}}\le L_{\mathrm{M}\mathrm{S}\mathrm{T}}$ and $L_C<\mathrm{2}·L_M$ . Hence $L_C<\mathrm{2}·L_{\mathrm{O}\mathrm{M}\mathrm{S}\mathrm{T}}<\mathrm{2}·L_{\mathrm{M}\mathrm{S}\mathrm{T}}$ that implies $\left|\mathrm{C}\mathrm{o}\mathrm{M}(S_r)\right|\le \mathrm{2}·\left|\mathrm{O}\mathrm{p}\mathrm{t}(S_r)\right|$ , where $\left|\mathrm{C}\mathrm{o}\mathrm{M}(S_r)\right|$ represent the number of relays placed by $\mathrm{C}\mathrm{o}\mathrm{M}$ based restoration.

Intuitively, the construction of $\mathrm{3}\text{-}star$ s is a 3-approximation algorithm on $S_p$ of segments while relay nodes deployment toward $\mathrm{C}\mathrm{o}\mathrm{M}$ is a 2-approximation algorithm on $S_p$ ; thus, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is a 3-approximation algorithm.

Theorem 9.

The complexity of relay nodes deployment toward the $CoM$ is $O(N\times d(S_j,CoM)/r_c)$ , where $N=\left|S\right|$ and $d(S_j,CoM)=\mathrm{m}\mathrm{a}\mathrm{x}\{d(S_i,CoM)\hspace{0.17em}|\hspace{0.17em}{S}_i\in S\}$ .

Proof.

The $\mathrm{C}\mathrm{o}\mathrm{M}$ based restoration ( $\mathrm{C}\mathrm{P}$ ) places $\mathrm{R}\mathrm{N}$ toward $\mathrm{C}\mathrm{o}\mathrm{M}$ of $\mathrm{S}\mathrm{P}\mathrm{G}$ . More specifically, one $\mathrm{R}\mathrm{N}$ in a round for each $S_i$ until all $S_i$ s are united. Since two $\mathrm{R}\mathrm{N}$ s should be placed at the distance of $r_c$ , intuitively the process takes at most $d(S_j,\mathrm{C}\mathrm{o}\mathrm{M})/r_c$ rounds to federate all disjoint segments, where $d(S_j,\mathrm{C}\mathrm{o}\mathrm{M})=\mathrm{m}\mathrm{a}\mathrm{x}\{d(S_i,\mathrm{C}\mathrm{o}\mathrm{M})\hspace{0.17em}|\hspace{0.17em}{S}_i\in S\}$ . Furthermore, there are N segments engaged in the process. Thus the complexity of relay nodes deployment toward the $\mathrm{C}\mathrm{o}\mathrm{M}$ is $O(N\times d(S_j,\mathrm{C}\mathrm{o}\mathrm{M})/r_c)$ .

Theorem 10.

The complexity of the $ORNP$ is $O(N^{\mathrm{3}})$ , and N is the number of partitioned segments.

Proof.

Since $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ consists of two efficient algorithms, Voronoi partition based prerestoration (VP) (Algorithm 1) and $\mathrm{C}\mathrm{o}\mathrm{M}$ based restoration ( $\mathrm{C}\mathrm{P}$ ) (Algorithm 2), we analyse the complexity of them, respectively.

The $\mathrm{C}\mathrm{o}\mathrm{M}$ based restoration works in two phases. In the first phase, it strives to construct $\mathrm{3}\text{-}star$ s as many as possible. It is clear that the complexity of $\mathrm{3}\text{-}star$ construction is $O(N^{\mathrm{3}})$ . In the second phase, all remaining disjoint segments are populating relays towards the $\mathrm{C}\mathrm{o}\mathrm{M}$ . If two or more segments meet, the one closest to the CoM is chosen as a representative for the next round deployment. According to Theorem 9, the complexity of relay nodes deployment toward the $\mathrm{C}\mathrm{o}\mathrm{M}$ is $O(N\times d(S_j,\mathrm{C}\mathrm{o}\mathrm{M})/r_c)$ , where N denotes the number of remaining disjoint segments and $d(S_j,\mathrm{C}\mathrm{o}\mathrm{M})=\mathrm{m}\mathrm{a}\mathrm{x}\{d(S_i,\mathrm{C}\mathrm{o}\mathrm{M})\hspace{0.17em}|\hspace{0.17em}{S}_i\in S\}$ . Therefore the complexity of $\mathrm{C}\mathrm{o}\mathrm{M}$ based restoration is $O(N^{\mathrm{3}})$ .

In addition, the $\mathrm{V}\mathrm{P}$ partitions the network into Voronoi cells for relay nodes selection, the complexity of which is $O(N)$ [29].

So, the complexity of the $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is $O(N^{\mathrm{3}})$ .

Algorithm 1: Voronoi partition based prerestoration.

Input:  n disjoint segments $$S_{\mathit{1}},S_{\mathit{2}},\dots ,S_n$$ .

Output: The federation of $$S_i$$ , $$i\le n$$ .

(1) Calculate the CoM of the SPG on the current set of separated $$S_i$$ .

(2) while (there exist at least a sensor $$s_j\in {\bigcap }_{i=\mathit{1}}^k\text{disk}({\text{CH}}_i)$$ , where $${\text{CH}}_i\in S_i$$ ) do

(3)    if   $$d\left(s_l,\text{CoM}\right)=\underset{}{\min }\{d\left(s_j,\text{CoM}\right)\hspace{0.17em}|\hspace{0.17em}{s}_j\in {\bigcap }_{i=\mathit{1}}^k\text{disk}({\text{CH}}_i)\}$$   then

(4)   Choose the sensor $$s_l$$ as a relay to federate the segments from $$S_{\mathit{1}}$$ to $$S_k$$

(5)   Update the list of disjoint segments.

(6)    end if

(7) end while

Algorithm 2: CoM based restoration phase.

Input: The remaining l segments $$S_{\mathit{1}},S_{\mathit{2}},\dots ,S_l$$ .

Output: The federation of $$S_i$$ , $$i\le l$$ .

(1) while (there exists a position p such that $$d(p,S_i)<r_S$$ , $$d(p,S_j)<r_S$$ and $$d(p,S_k)<r_S$$ where $$i,j,k\le l$$ ) do

(2) Place a sensor s as a relay to federate three segments $$S_i$$ , $$S_j$$ and $$S_k$$ .

(3) Update the list of disjoint segments.

(4) end while

(5) Calculate the CoM of the SPG on the current set of separated $$S_i$$ .

(6) repeat

(7) Each $$S_i$$ populates a relay $$r_i$$ toward the CoM and let $$r_i$$ represent $$S_i$$ .

(8) if there are k   $$r_{i}s$$ that meet each other then

(9)  Choose the closest $$r_i$$ to the CoM to represent k   $$r_{i}s$$

(10)  Update the list of disjoint segments.

(11) end if

(12) until (All segments are united)

5.2. Validation Experiments

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

5.2.1. Performance Metrics and Baseline Approaches

In our experiments, a partitioned $\mathrm{W}\mathrm{S}\mathrm{N}$ with varying numbers of segments has been considered. In addition, the parameters that affect the network characteristics are listed as follows.

Communication Range of Relays $(R)$ . The performance of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is affected by R; basically longer distances between segments require more $\mathrm{R}\mathrm{N}\mathrm{s}$ placed.

Number of Segments $(N_s)$ . Intuitively, a large number of segments require a larger $\mathrm{R}\mathrm{N}$ count.

We used the following two metrics to evaluate the overall performance of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ .

Number of $RNs\hspace{0.17em}\hspace{0.17em}(N_{rn})$ . A better approximation algorithm for the optimization of $\mathrm{R}\mathrm{N}$ placement deploys less $\mathrm{R}\mathrm{N}$ s than other strategies.

Average Node Degree. The connectivity of the resulting topology is measured by the total number of links among neighboring $\mathrm{R}\mathrm{N}\mathrm{s}$ dividing $N_{\mathrm{r}\mathrm{n}}$ .

We compare the performance of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ with the following three baseline approaches; the first algorithm is $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}\mathrm{1}t\mathrm{R}\mathrm{N}$ that establish a minimum spanning tree based on single-tiered relay node placement [8]. $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ , the second one, is designed for solving a Steiner tree problem with a minimum number of Steiner points [27]. The third approach that maps the network into grid to find the least $\mathrm{R}\mathrm{N}$ count is called $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ [11].

MST-1tRN. This algorithm strives to place the minimum number of $\mathrm{R}\mathrm{N}$ s to establish an $\mathrm{M}\mathrm{S}\mathrm{T}$ and its approximation ratio is between $\mathrm{5}$ and $\mathrm{7}$ . It is based on the assumption that the communication range R of a $\mathrm{R}\mathrm{N}$ is larger than that of a sensor, r. For the given segments, $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}\mathrm{1}t\mathrm{R}\mathrm{N}$ first computes an $\mathrm{M}\mathrm{S}\mathrm{T}$ . Then it deploys $\mathrm{R}\mathrm{N}\mathrm{s}$ on each edge, e, of the $\mathrm{M}\mathrm{S}\mathrm{T}$ . Note that if $r\le \mathrm{L}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(e)<\mathrm{2}r$ , then one $\mathrm{R}\mathrm{N}$ should be placed right in the middle of the edge. $\mathrm{2}+⌈(\mathrm{L}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(e)-\mathrm{2}r)/R⌉-\mathrm{1}\hspace{0.17em}\hspace{0.17em}\mathrm{R}\mathrm{N}$ s are placed along the edge e, while $\mathrm{L}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(e)$ is larger than $\mathrm{2}r$ . It is worth mentioning that r is assumed to be equal to R in our simulation.

$STP\text{-}MSP$ . It populates the minimum number of $\mathrm{R}\mathrm{N}$ s to establish connectivity such that the transmission range of each node is at most R. As a 3-approximation algorithm, it first combines reachable nodes into one group. Then for each three components, it seeks a position S that is at most R units away and places a $\mathrm{R}\mathrm{N}$ in S to merge three components into one. By Repeating these steps, all three components that can be connected by one $\mathrm{R}\mathrm{N}$ are located. After that, each component is represented as a point P and an $\mathrm{M}\mathrm{S}\mathrm{T}$ is computed based on Ps. Intuitively, the number of populated $\mathrm{R}\mathrm{N}$ s is the sum of the number of position Ss and $⌈\mathrm{L}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(e)/R⌉-\mathrm{1}\hspace{0.17em}\hspace{0.17em}\mathrm{R}\mathrm{N}$ s placed on each edge, e, of the $\mathrm{M}\mathrm{S}\mathrm{T}$ .

$CORP$ . This scheme models $\mathrm{A}\mathrm{O}\mathrm{I}$ as a grid of squares (cells) with equal sizes. Because all segments and relays are located at the center of cells, a segment or a relay can reach relays located at the center of neighboring cells. $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ works in rounds. In each round, it first identifies the border segments. Then for each border segment, it chooses a neighbor cell that is closest to the other border segments to place a $\mathrm{R}\mathrm{N}$ . If some segments are within each other's communication range, among which a segment is chosen to represent all of them for the next round deployment, these steps are repeated until all segments are federated.

Note that among three baseline approaches, only $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ maps the network into grid and it assumes all the segments and relays are located at the center of cells. However this assumption does not hold for some realistic applications. Since $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ works under this assumption, a few more relays are required to be added to make sure that all segments center at cells. According to the proposed algorithm for cell coverage in [9], for each cell with the side length $R/\sqrt{\mathrm{2}}$ , there is one relay with communication range R needed to cover every sensor within the cell as a representative.

In summary, $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ and $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}\mathrm{1}t\mathrm{R}\mathrm{N}$ opt to form an $\mathrm{M}\mathrm{S}\mathrm{T}$ among the segments using the least possible $\mathrm{R}\mathrm{N}$ count. In addition, $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ tries to form a network topology that has the segments at the periphery. Meanwhile, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ strives to reduce the number of segments needed to be connected before the fewest $\mathrm{R}\mathrm{N}\mathrm{s}$ are placed to federate the entire network. The characteristics of the generated topologies will be later elaborated through a detailed example. This section focuses on the number of $\mathrm{R}\mathrm{N}\mathrm{s}$ and the node degree.

5.2.2. Simulation Results and Comparison of the Generated Topology Quality

Several configurations with different combinations of R and $N_s$ are simulated. We change the value of R from $\mathrm{50}$ to $\mathrm{300}$ with increment of $\mathrm{50}$ , while $N_s$ varies from $\mathrm{3}$ to $\mathrm{8}$ . And all segments are randomly deployed in an area $\mathrm{1000}\hspace{0.17em}\mathrm{m}\times \mathrm{1000}\hspace{0.17em}\mathrm{m}$ . For each individual experiment, we average the results over $\mathrm{20}$ runs.

Number of RNs. Figure 9 gives a performance comparison of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ with baseline approaches in terms of the $\mathrm{R}\mathrm{N}$ count through varying R and $N_s$ . Seen in Figure 9(a), as R increases, $N_{\mathrm{r}\mathrm{n}}$ decreases generally. The performance of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is better than $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}\mathrm{1}t\mathrm{R}\mathrm{N}$ and $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ for R varied from $\mathrm{50}\hspace{0.17em}\mathrm{m}$ to $\mathrm{300}\hspace{0.17em}\mathrm{m}$ that is attributed to how $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ populates $\mathrm{R}\mathrm{N}\mathrm{s}$ toward the $\mathrm{C}\mathrm{o}\mathrm{M}$ rather than having an $\mathrm{M}\mathrm{S}\mathrm{T}$ or a Steiner tree when the number of segments is small. Note that $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ seeks less $\mathrm{R}\mathrm{N}\mathrm{s}$ than $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ , because $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ requires extra relays to make the segments centered at cells.

Figure 9

Comparison of RN count.

Figure 9(b) shows how $N_s$ affects the performance of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ in a partitioned network. As $N_s$ grows, more $\mathrm{R}\mathrm{N}\mathrm{s}$ are populated for all approaches. When $N_s$ is as large as $\mathrm{7}$ , all segments are connected. Once $N_s$ is larger than $\mathrm{7}$ , the number of $\mathrm{R}\mathrm{N}\mathrm{s}$ drops because of the density of the segments population getting high. When the communication range R is fixed, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ still performs better than baseline approaches with various $N_s$ .

It is worth mentioning that even if there are no eligible sensors chosen as gateways which implies the Voronoi partition based prerestoration does not work, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ always seeks less $\mathrm{R}\mathrm{N}$ s than $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ . The reason for that is although both of $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ and $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ deploy $\mathrm{R}\mathrm{N}$ s toward the geometrical center of the convex of all disjoint segments, $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ is based on the assumption of every segment located at the center of a cell. In fact, this assumption does not hold in real applications. Therefore $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ requires an extra relay to make sure all sensors within the cell will be covered by the extra relay that results in more $\mathrm{R}\mathrm{N}$ s count.

Average Node Degree. Seen in Figures 10(a) and 10(b), a better topology with higher connectivity in terms of the average node degree is generated by $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ . As R grows, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ tends to build a network with much higher average node degree, when R reaches $\mathrm{150}\hspace{0.17em}\mathrm{m}$ as shown in Figure 10(a). The performance advantage of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is not affected by $N_s$ as shown in Figure 10(b). To sum up, the initial positions of segments have significant influence on the average node degree of the topology by $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ instead of the number of segments.

Figure 10

Comparison of average node degree.

$\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ populates $\mathrm{R}\mathrm{N}$ toward the $\mathrm{C}\mathrm{o}\mathrm{M}$ that results in a better topology compared to baseline approaches in terms of connectivity.

Figure 11 shows the comparison on the resulting topologies obtained by $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ and the minimum steiner tree ( $\mathrm{M}\mathrm{S}\mathrm{T}$ ) that $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ and $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}\mathrm{1}t\mathrm{R}\mathrm{N}$ establish with the same setup. Table 1 presents the number of $\mathrm{R}\mathrm{N}\mathrm{s}$ deployed along the shortest path between every two segments in both topologies. We assume bidirectional data delivery between two segments use the same path, where $A_{\mathrm{0}}$ denotes $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ as $A_{\mathrm{1}}$ denotes $\mathrm{M}\mathrm{S}\mathrm{T}$ . For all segments, $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ deploys less $\mathrm{R}\mathrm{N}\mathrm{s}$ to forward data than $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ and $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}\mathrm{1}t\mathrm{R}\mathrm{N}$ . Overall $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ requires 150 hops for delivery between all pairs of segments, which is 66 hops less than that in $\mathrm{M}\mathrm{S}\mathrm{T}$ . Therefore, $\mathrm{R}\mathrm{N}$ s deployment of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ results in a topology with less overall latency, while data are delivered between segments.

Table 1

ORNP versus MST.

Hops	$$S_{\mathit{0}}$$		$$S_{\mathit{1}}$$		$$S_{\mathit{2}}$$		$$S_{\mathit{3}}$$		$$S_{\mathit{4}}$$		$$S_{\mathit{5}}$$		$$S_{\mathit{6}}$$
	$$A_{\mathit{0}}$$	$$A_{\mathit{1}}$$	$$A_{\mathit{0}}$$	$$A_{\mathit{1}}$$	$$A_{\mathit{0}}$$	$$A_{\mathit{1}}$$	$$A_{\mathit{0}}$$	$$A_{\mathit{1}}$$	$$A_{\mathit{0}}$$	$$A_{\mathit{1}}$$	$$A_{\mathit{0}}$$	$$A_{\mathit{1}}$$	$$A_{\mathit{0}}$$	$$A_{\mathit{1}}$$
$$S_{\mathit{0}}$$	0	0	2	2	2	2	5	8	5	8	5	8	3	4
$$S_{\mathit{1}}$$	2	2	0	0	2	2	5	8	5	8	5	8	3	4
$$S_{\mathit{2}}$$	2	2	2	2	0	0	5	8	5	8	5	8	3	4
$$S_{\mathit{3}}$$	5	8	5	8	5	8	0	0	2	2	2	2	3	4
$$S_{\mathit{4}}$$	5	8	5	8	5	8	2	2	0	0	2	2	3	4
$$S_{\mathit{5}}$$	5	8	5	8	5	8	2	2	2	2	0	0	3	4
$$S_{\mathit{6}}$$	3	4	3	4	3	4	3	4	3	4	3	4	0	0
Sum	22	32	22	32	22	32	22	32	22	32	22	32	18	24
Average	3.1	4.5	3.1	4.5	3.1	4.5	3.1	4.5	3.1	4.5	3.1	4.5	2.5	3.4

Figure 11

Comparison of resulting topology.

6. Conclusion

In this paper, we have discussed the problem of federating disjoint segments in a partitioned $\mathrm{W}\mathrm{S}\mathrm{N}$ . The proposed solution $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ consists of two efficient algorithms, Voronoi partition based prerestoration and $\mathrm{C}\mathrm{o}\mathrm{M}$ based restoration, both of which collaborate to establish communication links between segments. The performance of $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is analyzed mathematically and validated through simulation. The simulation results show $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ outperforms $\mathrm{S}\mathrm{T}\mathrm{P}\text{-}\mathrm{M}\mathrm{S}\mathrm{P}$ , $\mathrm{M}\mathrm{S}\mathrm{T}\text{-}\mathrm{1}t\mathrm{R}\mathrm{N}$ , and $\mathrm{C}\mathrm{O}\mathrm{R}\mathrm{P}$ in terms of the relay count and the connectivity of resulted topology. It is worth mentioning that although $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ is a centralized algorithm, it can be implemented in a distributed manner. Thus it is applicable to all kinds of networks’ restoration and it does not rely on any particular $\mathrm{W}\mathrm{S}\mathrm{N}$ features.

Here are some open issues that will be addressed in the future. The first one is that relay nodes deployment may consider the quality of service ( $\mathrm{Q}\mathrm{o}\mathrm{S}$ ) requirement instead of just establishing the connectivity only. For example, when massive data travel through those pathes with overall capacity lower than $\mathrm{Q}\mathrm{o}\mathrm{S}$ requirement, the relays on those pathes will drain their batteries that can directly cut off communications in the network. The second one is how to restore damaged networks with obstacles involved. Under some circumstance, relays cannot be placed on obstacles that are difficult to travel through by mobile relays. Therefore, the future work includes extending $\mathrm{O}\mathrm{R}\mathrm{N}\mathrm{P}$ to solve the network restoration problems with the $\mathrm{Q}\mathrm{o}\mathrm{S}$ requirement or the obstacle constrain.