Graph-Theoretic Based Connectivity Restoration Algorithms for Mobile Sensor Networks

Abstract

In mobile sensor networks (MSN), actuated sensors collaborate with each other in some predefined missions. The collaboration requires application-level coordination based on a strongly connected underlying network, which is often in an infrastructure-free ad hoc manner. The particular network topology provides flexibility as well as vulnerability to the potential applications of MSN; for example, the connectivity can be easily jeopardized if the network is partitioned into disjoint segments from the failure of some critical sensors. In this paper, a critical sensor determination and substitution (CSDS) strategy is proposed to address the important problem of network partitions in mobile sensor networks (MSN) due to the failure of particular sensors. CSDS utilizes a graph-theoretic method to locally identify critical sensors with 2-hop neighboring information. Then, an efficient backup sensor selection algorithm is proposed to monitor the critical sensors and, if necessary, substitute it in order to eliminate the partitions in MSN. The main contribution of our proposed work is that CSDS requires the relocation of only one sensor in each partition elimination process, so that the impacts on the primary missions of the MSN are minimized. Experimental simulations are conducted to evaluate the correctness and effectiveness of CSDS.

1. Introduction

Last decade we have witnessed a rapidly growing development in mobile sensor network (MSN) based on its enormous potential applications in a variety of scenarios such as terrain exploration, environmental monitoring, and remote measuring [1]. As an effective substitution of human, MSN often works in harsh environments where many potential risks, for example, mechanism malfunction or intentional sabotage, can be expected. The vulnerable topology of the ad hoc network based sensor system can be easily jeopardized due to the failure of some sensors caused by the potential risks. In particular, if the failed node is a critical sensor, for example, a cut-vertex, the network will be partitioned into a few disconnected segments. In this case, intersensor communications will not be possible for all sensors to deliver a timely response to critical missions, which may further cause fatal consequences to the applications [2]. Therefore, an efficient partition elimination, also called connectivity restoration [3] method, is pivotal to guarantee the successful execution of certain missions for MSN.

To date, many connectivity restoration schemes have been proposed; please refer to [3] for a comprehensive review on this topic. When the MSN is deployed into a remote area, where manually moving sensors are not applicable, a feasible way to restore the connectivity is to substitute the failed sensor by autonomously relocating the healthy ones. Both centralized [4] and decentralized [5] methods are designed in order to fulfill this objective. We argue that decentralized methods are rather a natural choice due to the distributed and autonomous characteristic of most MSNs. Typically, the restoration process involves a series of actions, including cut-vertices determination, backup sensors selection, and sensor relocation [6]. Contemporary schemes often focus on the connectivity restoration with multiple sensors. However, the sensors' current tasks are often neglected. When relocating sensors, most connectivity methods simply adopt direct movement, that is, the backup sensor moves directly towards the failed sensor [7], while other methods use potential function based controller to navigate the movements of sensors [8]. These methods, however, assume that all sensors in the network are free to be relocated in case of connectivity restoration.

Whether by cascaded movements or by potential force driven movements, it is often required to move several sensors just to restore single failure. It is argued that if a sensor rests in a spot, it may stay there for a reason; for example, it is occupied by a particular mission. It would not be feasible to move it just for reconnecting the network. Therefore, minimizing the number of sensors moved in connectivity restoration is important for task-oriented applications of MSN. To address this problem, a critical sensor determination and substitution (CSDS) strategy is proposed to eliminate partitions in mobile sensor networks (MSN) due to the failure of a critical sensor. First, a graph-theoretic method is designed to locally identify critical sensors with 2-hop neighboring information by computing the Laplacian matrix of a local spanning subgraph. Then, an efficient backup sensor selection algorithm is proposed to monitor the critical sensors and, if necessary, substitute it in order to eliminate the partitions in MSN. A preliminary version of this work was presented in [9].

The main contribution of our proposed work is to guarantee all partitions caused by the failure of a critical sensor are eliminated by moving only ONE backup sensor, as long as a noncritical sensor exists. Therefore, the negative impacts on the primary missions of the MSN are minimized. Theoretical analysis and experimental simulation studies are provided to verify the correctness and evaluate the performance of the proposed CSDS.

The outline of this paper is as follows. Section 2 presents the related work and motivations. The problem is then formulated in Section 3. In Section 4, we present the cut-vertices determination and backup selection algorithms in detail and provide the analytical results of CSDS. The results and discussions for CSDS simulation are provided in Section 5. Finally, Section 6 concludes the paper.

2. Related Work

2.1. Graph and Network Optimization

Connectivity restoration belongs to the basic problem of network optimization and resilience, which is rooted in graph theory and its application in networks [10]. The basic concept of connectivity restoration is to find the optimal backup node and/or optimal backup location in which the backup replaces the failed one in order to achieve the objective of restoring connectivity. Meanwhile, some secondary objective, for example, minimizing the impact on topology, or reducing nodes' degree, may be pursued. Such a problem is similar to the problem of service facility location, that is, locating a central facility in a network so as to minimize the sum of distances from the sources to it; the distance reflects the associated flow volume and/or cost of the paths [11]. Service facility location can be further classified as two main problems, that is, “p-median problem” and “p-center problem,” according to different objectives. In [12], a distributed algorithm is proposed to locally compute the near-optimal p-medians in linear time, which is proved to be suitable for online calculation in dynamic and large-scale networked systems. Other objectives may be also pursued in service facility location problem. In [13], the multicovering emergency service facility location problem is investigated, and a mathematical programming model is proposed to minimize the sum of expected disaster losses and the total costs of emergency service facilities. Deploying/choosing service facility within the network may naturally cluster the network into several subgraphs, with the facility being the cluster head to provide various services to the subnet. An adaptive clustering approach is proposed for autonomic systems in [14], and a unique feature of self-healing is achieved by recalculating near-optimal cluster head in case of component failures or congestion, for example, failure of links. Both service facility location and self-healing clustering problem can be applied to the problem of network resilience with certain variation. However, for this work, we focus on the fast restoration of the network connectivity rather than network optimization, and the failure of network is caused merely by the failure of node.

2.2. Direct Movement for Connectivity Restoration

The distributed connectivity restoration with respect to the failure of single cut-vertices has been extensively investigated [4–8, 15–19]. Both direct movement and potential force based movement are implemented. The direct movement can be further divided into block movement [2] and cascaded movement [15] methods according to their different patterns. In [2], several algorithms were proposed for achieving a 2-connectivity fault-tolerant configuration in multirobot networks by moving a subset (block) of mobile robots. Block movement can maintain the topology within the subset but requires a significantly large movement distance. To overcame this drawback and reduce the number of sensors moved, the cascaded movement method that only moves a set of necessary nodes for restoration is employed. In [7], Abbasi et al. presented a Distributed Actor Recovery Algorithm (DARA) to address the 1- and 2-connectivity restoration in wireless sensor and actor network (WSAN) with 2-hop neighboring information, DARA selects the backup candidate according to its node degree and distances, and then the selected nodes move to substitute the failed actor and their parental nodes in sequence. A more effective cascaded movement method was introduced in [15], which also added an effective mechanism to determine the cut-vertices of network proactively by identifying a Connected Dominating Set (CDS) using Dai's approach [16] with 2-hop neighboring information. By selecting the dominatee and best available dominator node, the number of sensors moved in the restoration is further reduced. Considering the impact of topology change on network performance, Least-Disruptive Topology Repair (LeDiR) algorithm was recently reported in [17], unlike other methods, LeDiR selecting a candidate node for restoration based on the partial view of network topology via a routing table. Recently, a localized hybrid timer based cut-vertex node failure recovery approach was proposed in [18] to ensure the timely restoration of MSN by allowing multiple failure handlers; cascaded movement is also adopted to relocate the associated sensors. In [19], with 1-hop neighboring information, the distributed partitioning Detection and Connectivity Restoration (DCR) was designed to identify the criticality of sensors and select the backup node based on the principle of “Guardian nomination.” The movements of sensors also follow the cascaded movement.

2.3. Potential Force Based Movement

Recently, potential force based methods [20–25] are widely exploited and proved to be very effective methods to redeploy mobile sensors and robots for achieving primary goals, for example, global connectivity, coverage, or fault-tolerance. The potential forces based methods are very attractive because of their effectiveness in creating a reactive behavior that provably avoids collisions with neighboring agents during reconfiguration. In [20], Zavlanos and Pappas proposed a hybrid control system that consists of a market based control strategy and a potential force based motion controller. The control system utilized potential force to achieve the main objective of maintaining global connectivity. The connectivity control system can reduce redundant communication links while preserving connectivity based on local estimation of spanning subgraph. Such problem is also addressed by a centralized potential force based controller in [21]. In [22], Mi et al. proposed a self-organization technique known as Distributed Link Removal Algorithm (DLRA) that aims to maintain connectivity in mobile sensor networks while reducing the redundant links, limiting the sensor nodes actuation and avoiding collisions. The redeployment of the mobile sensors is also by potential force based functions. However, the main drawback for these strategies is the well-known local minima problem [26]: interacting with the primary task of the mobile sensors (e.g., moving to a destination, creating a formation), potential forces can create undesired asymptotically stable configurations that prevent the sensors from reaching the desired configuration.

Another solution to navigate the mobile sensors is to use a distributed potential function based motion controller. A k-hop neighboring information based connectivity restoration framework, named HERO, was presented in [8], and the proposed method includes a potential function to drive the backup sensor to its destination while avoiding intersensor collisions. Due to the nature of the potential based controller, a relatively large number of sensors are employed in the connectivity restoration. The major problem of the contemporary schemes is the participation of multiple sensors in restoration process, which may not be possible in certain missions. This paper presents a novel solution to restore connectivity by moving only one backup sensor.

3. Preliminaries and Problem Formulation

3.1. System Models

For an initially connected sensor network with M actuated mobile sensors, encode the intersensor network in terms of an undirected graph $\mathcal{G}=(\mathcal{V},E)$ , where $\mathcal{V}=(\mathrm{1},\dots ,M)$ denotes the set of vertices indexed by the set of mobile sensors $i\in [\mathrm{1},\dots ,M]$ , and $E=\{e_{ij},\mathrm{\hspace{0.17em}\hspace{0.17em}}(i,j)\in \mathcal{V}\times \mathcal{V}\}$ denotes the unordered pairs which specifies that the bidirectional communication links exist between the respective sensors. Let $d_{ij}=‖{\xi }_i-{\xi }_j‖$ be the Euclidean distance between sensors i and j, where ${\xi }_i\in {\mathbb{R}}^{\mathrm{2}}$ represents the location of sensor i. Then, a link $e_{ij}$ exists; that is, $e_{ij}\in E$ , if and only if $d_{ij}\le R$ , where R is the transmission range of the sensors. The network has homogenous configuration for all sensors; that is, every sensor in the network is equipped with the same computing devices/functions and has the same communication range. The aforementioned network model gives rise to the following definitions.

Definition 1 (connectivity).

An undirected graph $\mathcal{G}$ is connected if and only if there is at least one path for any two vertices.

Definition 2 (1-hop neighbors).

Define j as the 1-hop neighbor of i; that is, $j\in {\mathcal{N}}_i$ , if and only if $e_{ij}\in E$ , where ${\mathcal{N}}_i$ is the 1-hop neighboring set of i.

Definition 3 (2-hop neighbors).

Define k as the 2-hop neighbor of i; that is, $k\in {\mathcal{N}}_i^{\mathrm{2}}$ , where ${\mathcal{N}}_i^{\mathrm{2}}$ is the 2-hop neighboring set of i, if and only if there exists at least one route between i and k in $\mathcal{G}$ with 2 hops.

3.2. Algebraic Definitions of Connectivity

Denote $w_{ij}$ as the symmetric weight of the communication links in $\mathcal{G}$ , and $w_{ij}$ satisfies

$$\begin{array}{cc}& w_{ij}=\left\{\begin{array}{cc}\mathrm{1},\hfill & d_{ij}\le R\hfill \\ \mathrm{0},\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\hfill \end{array}\right.\end{array}$$

(1)

We further define the adjacency matrix $\mathcal{A}\left(\mathcal{G}\right)\in {\mathbb{R}}^{M\times M}$ of the graph $\mathcal{G}$ with entries as

$$\begin{array}{cc}& {\left[\mathcal{A}\left(\mathcal{G}\right)\right]}_{ij}={\left[\mathcal{A}\left(\mathcal{G}\right)\right]}_{ji}=w_{ij}.\end{array}$$

(2)

The powers of the adjacency matrix of a graph are closely related to network connectivity, which can be captured with the Laplacian matrix $\mathcal{L}(\mathcal{G})\in {\mathbb{R}}^{M\times M}$ of graph $\mathcal{G}$ . The Laplacian matrix can be defined as follows:

$$\begin{array}{cc}& \mathcal{L}\left(\mathcal{G}\right)=\left\{\begin{array}{cc}-w_{ij},\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}i\ne j\hfill \\ {\displaystyle \sum }_{s\ne i}^{}{w}_{is},\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}i=j.\hfill \end{array}\right.\end{array}$$

(3)

Furthermore, let $\mathcal{D}(\mathcal{G})=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\sum }_{j=\mathrm{1}}^M{w}_{ij})$ represent the diagonal matrix of degrees of graph $\mathcal{G}$ , and $\mathcal{L}(\mathcal{G})$ can be written as

$$\begin{array}{cc}& \mathcal{L}\left(\mathcal{G}\right)=\mathcal{D}\left(\mathcal{G}\right)-\mathcal{A}\left(\mathcal{G}\right).\end{array}$$

(4)

It is widely acknowledged that $\mathcal{L}(\mathcal{G})$ with symmetric weights is always a symmetric positive-semidefinite matrix, which is closely related to the connectivity of the graph. The algebraic connectivity of the graph $\mathcal{G}$ can be determined by the following theorem.

Theorem 4 (see [27]).

Let $\mathrm{0}\le {\lambda }_{\mathrm{1}}(\mathcal{G})\le {\lambda }_{\mathrm{2}}(\mathcal{G})\cdots \le {\lambda }_n(\mathcal{G})$ be the ordered eigenvalues of the Laplacian matrix $\mathcal{L}(\mathcal{G})$ . Then, ${\lambda }_{\mathrm{1}}=\mathrm{0}$ with corresponding eigenvector 1, that is, the $M\times \mathrm{1}$ vector of all entries equal to 1. Moreover, ${\lambda }_{\mathrm{2}}(\mathcal{G})>\mathrm{0}$ if and only if the graph $\mathcal{G}$ is connected.

The second smallest eigenvalue ${\lambda }_{\mathrm{2}}(\mathcal{G})$ of the Laplacian matrix is also known as the algebraic connectivity or Fiedler value of the graph. Generally, higher value of ${\lambda }_{\mathrm{2}}(\mathcal{G})$ indicates stronger connectivity of the respective network.

3.3. Main Objective

Based on the aforementioned background, the main objectives of this work can be described as follows.

Assume that the network has a nonuniform deployment topology with randomly deployed sensors, and each sensor knows its own location and periodically exchanges status information with its 1-hop neighbors and gathering information of 1- and 2-hop neighbors.

Main Objectives. The main objectives are as follows: (1) locally determining the critical sensors of the network based on 2-hop neighboring information, (2) selecting the best available backup sensor for each critical sensor so that (3) upon the failure of the critical sensor the connectivity of the network by relocating ONLY the backup sensor was restored, and further partitions of the network can be avoided.

4. Restoring Connectivity with Backup Sensor

The principle of our design is to proactively assign noncritical backup sensors to the critical sensors. Compared to the reactive methods, proactive selection of backups is beneficial for the timely execution of the restoration process, because the backup sensor can start the restoration immediately after the failure of a critical sensor. In this section, a critical sensor determination and substitution (CSDS) algorithm is proposed to determine the criticality of the sensors and select the best available backups with the aid of only 1- and 2-hop local neighboring information.

4.1. Critical Sensor Determination

Cut-vertices in a graph can be accurately determined in a centralized manner if the network-wide information is provided. However, it is not possible to accurately determine the cut-vertices with only local information. However, we manage to determine the noncritical sensor with confidence and mark others as critical; that is, if a sensor is marked as noncritical, it is not definitely a cut-vertex, whereas if a sensor is marked as critical, it may still be a global non-cut-vertex in $\mathcal{G}$ .

Step 1 (initialization).

Sensors collect neighbor's information by periodically exchanging heartbeat messages with their 1-hop neighbors. The heartbeat message must contain sensor's ID, geographic position, and one-hop neighbor set ${\mathcal{N}}_i$ . Each sensor can build complete ${\mathcal{N}}_i$ and ${\mathcal{N}}_i^{\mathrm{2}}$ after successfully collecting information.

Step 2 (determination).

Based on ${\mathcal{N}}_i$ and ${\mathcal{N}}_i^{\mathrm{2}}$ , sensor i can determine whether it is a noncritical sensor in the graph. First, let ${\mathcal{G}}_i$ be the spanning subgraph of $\mathcal{G}$ , and ${\mathcal{G}}_i$ contains all of the sensors in ${\mathcal{N}}_i$ and ${\mathcal{N}}_i^{\mathrm{2}}$ . The Laplacian matrix of ${\mathcal{G}}_i$ is given by $\mathcal{L}({\mathcal{G}}_i)=\mathcal{D}({\mathcal{G}}_i)-\mathcal{A}({\mathcal{G}}_i)$ . Then, by computing the algebraic connectivity ${\lambda }_{\mathrm{2}}({\mathcal{G}}_i)$ , sensor i can determine whether its failure can cause the disconnection of the subgraph that consists of its 1- and 2-hop neighbors. If ${\lambda }_{\mathrm{2}}({\mathcal{G}}_i)>\mathrm{0}$ , sensor i marks itself as a noncritical sensor; otherwise it is critical sensor. An example is shown in Figure 1. Figure 1(a) is the initially connected MSN with 13 mobile sensors, and graph-theoretic based method is used to determine the critical sensors. With spanning subgraph of $\mathcal{G}$ , it is determined that (1) ${\mathcal{G}}_{\mathrm{1}}$ is connected and sensor 1 is accurately determined as noncritical sensor as in Figure 1(b); (2) ${\mathcal{G}}_{\mathrm{2}}$ is disconnected and sensor 2 is accurately determined as critical sensor as in Figure 1(c); and (3) ${\mathcal{G}}_{\mathrm{3}}$ is disconnected and sensor 3 is falsely determined as critical sensor when it is not actually a global critical sensor as in Figure 1(a). The false determination is mainly caused by information unavailability of the entire network topology, which occurs when restricted to local information. It is also worthwhile to notice that a similar idea of determining the most critical node in a subgraph by locally computing the ${\lambda }_{\mathrm{2}}(\mathcal{G})$ within n-hops has been proposed in [28]. Our method defers from it in the way that CSDS computes the ${\lambda }_{\mathrm{2}}(\mathcal{G})$ of a subgraph while excluding the node itself. Therefore, the node can clearly identify whether its absence causes the disconnection of the subgraph so that no critical node will be missed.

Figure 1

Example of the initial graph in (a), spanning subgraph in (b), spanning subgraph in (c), and spanning subgraph in (d).

Step 3 (notification).

If a sensor i determines itself as a critical sensor, it will inform all of its one-hop neighbors; that is, $j\in {\mathcal{N}}_i$ , by sending a CriSen $(i)$ message to them. Any noncritical sensor j that receives this message and is not currently occupied by another task will send a backup application message $\mathcal{B}\mathcal{A}(j)$ back to notify i that it is available to be chosen as a backup. The value of $\mathcal{B}\mathcal{A}(j)$ is equal to the Euclidean distance between i and j; that is, $\Phi [\mathcal{B}\mathcal{A}(j)]=d_{ij}$ . The pseudocode for critical sensor determination is shown in Pseudocode 1, and the sequence diagram of the algorithm is shown in Figure 2.

Pseudocode 1: Pseudocode of the critical sensor determination algorithm.

Step  1. Initialization

Receiving heartbeat messages from one-hop neighbor and collecting 2-hop neighbor information.

Constructing $${\mathcal{N}}_i$$ and $${\mathcal{N}}_i^{\mathrm{2}}$$

Step  2. Determination

(1) For   $$i\in \mathcal{V}$$

(2)  if   $${\mathcal{N}}_i$$ and $${\mathcal{N}}_i^{\mathrm{2}}$$ are completely collected

(3)    SpanningGraph( $$\mathcal{G}$$ ) = $${\mathcal{G}}_i$$

(4)    Return $$\mathcal{L}({\mathcal{G}}_i)=\mathcal{D}({\mathcal{G}}_i)-\mathcal{A}({\mathcal{G}}_i)$$

(5)  else go to (1)

(6)  EigenValue( $${\mathcal{G}}_i$$ ) = $${\lambda }_{\mathrm{2}}({\mathcal{G}}_i)$$

(7)    if   $${\lambda }_{\mathrm{2}}({\mathcal{G}}_i)>\mathrm{0}$$

(8)      Critical(i) = false

(9)    else  Critical(i) = true

(10)    end if

(11)   end if

Step  3. Notification

(12) For   $$i\in \mathcal{V}$$

(13)  if  Critical(i) = true

(14)        Send CriSen(i) to every $$j\in {\mathcal{N}}_i$$

(15)  end if

(16)  for  j received CriSen $$(i)$$

(17)    if  Critical(j) = false and Occupied(j) = false

(18)         Send $$\mathcal{B}\mathcal{A}(j)$$ to i

(19)    end if

Figure 2

Sequence diagram of the critical sensor determination algorithm.

4.2. Backup Sensor Selection and Connectivity Restoration

Backup selection of best available sensors is based on the criticality, hop-count, and Euclidean distances of their neighbors. The following criteria should be met when a critical sensor chooses its backup.

Case 1.

If a critical sensor i receives more than one $\mathcal{B}\mathcal{A}()$ , which indicates that there is at least one 1-hop neighbor who is available to be chosen as backup, the sensor will choose a backup among its 1-hop neighbors. Specifically, a 1-hop neighbor j is chosen as the backup of a critical sensor i if and only if the following terms are satisfied:

$$\begin{array}{cc}& {\lambda }_{\mathrm{2}}\left({\mathcal{G}}_j\right)>\mathrm{0},\end{array}$$

(5)

$\begin{array}{cc}& \Phi \left[\mathcal{B}\mathcal{A}\left(j\right)\right]=\min \left\{\Phi \left[\mathcal{B}\mathcal{A}\left(\right)\right]\right\};\end{array}$

(6)

that is, (1) j must be a noncritical sensor and (2) among all of the available 1-hop neighbors of i, j is geographically the closest one.

A very interesting yet crucial fact is that a noncritical node may become critical upon the failure of other nodes, and any movement of it may cause further partition of the network. This can be seen from Figure 3. As shown in Figure 3(a), upon the failure of the critical sensor 1, sensor 2 turns out to be a critical sensor while it was initially noncritical, and the movement of sensor 2 may cause further disconnection between sensor 3 and sensor 4. However, as shown in Figure 3(b), relocating sensor 2 to the exact position of the failed sensor 1 will not affect the global connectivity. The explanation of these interesting phenomena is straightforward: by substituting a failed critical node with a noncritical node, the final topology of the graph can be viewed as the initial topology without the noncritical node, that is, the failure of the noncritical node. Thus the global connectivity is maintained. The aforementioned fact is of great importance and entitles us to use just one sensor to restore the connectivity rather than use cascaded and potential based movements of a group of sensors.

Figure 3

An example of an initially noncritical sensor 2 becomes a critical vertex when sensor 1 fails, (a) the initial topology, and (b) the updated topology after sensor 2 restored the connectivity.

Case 2.

If a critical sensor i receives none $\mathcal{B}\mathcal{A}()$ from 1-hop neighbors, which indicates that no 1-hop neighbor is available to be chosen as the backup. Then, sensor i will locate a noncritical sensor from 2 or more hop-count neighbors. First, sensor i will compose a backup request message $\mathcal{B}\mathcal{R}(i)$ . Then, the BSR message will be sent to its 2-hop neighbor by setting the hop-count to $\mathrm{T}\mathrm{T}\mathrm{L}=\mathrm{2}$ . Any noncritical sensor receiving a $\mathcal{B}\mathcal{R}(i)$ will respond to it by sending a $\mathcal{B}\mathcal{A}()$ back to sensor i. The value of $\mathcal{B}\mathcal{A}()$ from a two-hop sensor j is all the Euclidean distance from it to the critical sensor i; that is, $\Phi [\mathcal{B}\mathcal{A}(j)]=d_{ij}$ . Finally, after collecting $\mathcal{B}\mathcal{A}()$ , sensor i will select a backup sensor according to (6). Note that a gradual expansion technique [29] is used to locate a noncritical sensor from higher hop-count neighbors; that is, sensor i composes a new $\mathcal{B}\mathcal{R}(i)$ with $\mathrm{T}\mathrm{T}\mathrm{L}=k$ if there is no backup available within $k-\mathrm{1}$ . Sensor i will stop sending $\mathcal{B}\mathcal{R}(i)$ as soon as a backup is located. However, there is a rare case where no noncritical node exists in the network.

Case 3.

In case a critical sensor i does not receive any $\mathcal{B}\mathcal{A}()$ message after searching the network, then all sensors in the network were identified as critical, which may not be restorable upon the failure of some special sensor. A heuristic solution to this situation under limited information is for each 1-hop neighbor of a critical sensor i, for example, j, to rerun the critical sensor determination algorithm without the critical sensor i and its other 1-hop neighbors. Specifically, each 1-hop sensor of one critical sensor, for example, i, will run the critical sensor determination algorithm again. However, in this step, instead of computing the Fiedler value of ${\mathcal{G}}_j$ , it computes the Fiedler value of another subgraph ${\mathcal{G}}_j^{\prime }$ , where ${\mathcal{G}}_j^{\prime }=\mathcal{G}{\mathcal{j}}_j\setminus (i\cup (k\in {\mathcal{N}}_i))$ , that is, a subgraph that excludes sensor i all the 1-hop sensor of i. If such a subgraph is connected without sensor j, that is, ${\lambda }_{\mathrm{2}}({\mathcal{G}}_j^{\prime })>\mathrm{0}$ , then sensor j will be able to replace sensor i without incurring any further disconnection of the network. For instance, as shown in Figure 4, all of the sensors in the network are initially critical sensors, and to choose a backup for sensor 1, its 1-hop sensors will again compute its criticality. If ${\lambda }_{\mathrm{2}}({\mathcal{G}}_{\mathrm{2}}^{\prime })>\mathrm{0}$ , it will compose a $\mathcal{B}\mathcal{R}(\mathrm{2})$ to participate in the backup selection. According to our methods, sensors 3, 4, and 5 will also participate in the selection, and the selection will again obey (6). It is obvious that substituting sensor 1 with either of the 4 sensors can restore the global connectivity. The detailed pseudocode for the backup sensor selection is shown in Pseudocode 2, and the sequence diagram for this backup sensor selection algorithm can be found in Figure 5.

Pseudocode 2: Pseudocode of the backup sensor selection.

(1) For  Critical(i) = true

(2)  if   $$\left\{\mathrm{\Phi }[\mathcal{B}\mathcal{A}()]\right\}\ne \mathrm{⌀}$$    #Case 1

(3)   if   $$\mathrm{\Phi }[\mathcal{B}\mathcal{A}(j)]=\underset{}{\min }\left\{\mathrm{\Phi }[\mathcal{B}\mathcal{A}()]\right\}$$

(4)    Backup(i) = j, inform j

(5)   end if

(6)  else

(7)   TTL = TTL + 1     #Case 2, initial TTL = 2

(8)   if  TTL < M

(9)    waiting for $$\mathcal{B}\mathcal{A}()$$ , go to (2)

(10)   else

(11)     for   $$j\in {\mathcal{N}}_i$$      #Case 3, for every 1-hop neighbor of sensor i

(12)     Subgraph( $${\mathcal{G}}_j$$ ) = $${\mathcal{G}}_j^{\prime }$$

(13)     if   $${\lambda }_{\mathrm{2}}({\mathcal{G}}_j^{\prime })>\mathrm{0}$$

(14)      Send $$\mathcal{B}\mathcal{A}(j)$$ to i

(15)     end if

(16)    end

(17)    go to (2)

(18)   end if

(19)  end

Figure 4

An example of a topology contains only critical sensors.

Figure 5

Sequence diagram of the backup sensor selection algorithm.

The designated backup sensor is responsible for monitoring the status of its parental critical sensor. If it is a 1-hop neighbor of the critical sensor, the failure of the critical sensor can be easily detected from the missing of heartbeat messages. Otherwise, if the backup sensor is 2 hops away from the critical sensor, the critical sensor should unicast the heart-beat message to it. If any of the heartbeat messages misses for more than a tolerant time period, the restoration process will be initiated.

Since cascaded movement is not required in CSDS, a simple node relocation method will be sufficient to drive the backup sensor to the position of the failed critical sensor in order to restore the connectivity. A straightforward solution is to utilize a target potential force ${\mathbb{F}}_T$ , which can be a simple quadratic function in the distance to the target with a minimum at the target, such as ${\mathbb{F}}_T=-\nabla V_T(\xi )$ , and

$$\begin{array}{cc}& V_T\left(\xi \right)=K_r{‖{\xi }_b-{\xi }_f‖}^{\mathrm{2}},\end{array}$$

(7)

where $K_r$ is a constant gain and ${\xi }_b$ and ${\xi }_f$ are the positions of the backup sensor and its corresponding failed critical sensor.

4.3. Algorithm Analysis

To verify the correctness and efficiency of CSDS, we introduce the following theorems.

Theorem 5.

In the worst case, the total movement distance (TMD) in CSDS is $\mathrm{0.5}(M-\mathrm{1})R$ .

Proof.

The worst case topology for TMD is a line topology as in Figure 6, and the distances between each pair of neighbors are equal R. The failed sensor must be right in the center of the line; otherwise, a closer backup (either sensor 1 or sensor M) will be located first, and its TMD is smaller than the TMD in the worst case. Therefore, (1) if M is even, then the worst case TMD occurs when the failed sensor ID is $\mathrm{0.5}M-\mathrm{1}$ or $\mathrm{0.5}M+\mathrm{1}$ , and the TMD for both cases equals $\mathrm{0.5}MR-R$ ; (2) if M is odd, then the worst case TMD occurs when the failed sensor ID is $\mathrm{0.5}(M+\mathrm{1})$ , and the worst case TMD in this case is $\mathrm{0.5}(M-\mathrm{1})R$ . To conclude, the worst case TMD in CSDS is $\mathrm{0.5}(M-\mathrm{1})R$ .

Figure 6

The worst case topology in terms of TMD.

CSDS outperforms some of the well-known methods in terms of TMD, as shown in Table 1. In addition, with cascaded movement, the maximum number of sensors moved in the worst case amounts to nearly all of the sensors in the entire network. CSDS, on the other hand, ensures that only one sensor moved regardless of the network topology.

Table 1

Comparisons of different methods.

Methods	Matrices (in worst case)
	Information	NSMa	TMD	TNM
DARA [7]	2-hop	$$M-\mathrm{3}$$	$$(M-\mathrm{3})R$$	$$\mathrm{O}(M)$$
PADRA+ [15]	2-hop	$$\mathrm{0.5}(M-\mathrm{1})$$	$$\mathrm{0.5}(M-\mathrm{1})R$$	$$\mathrm{O}(M^{\mathrm{2}})$$
HERO [8]	2-hop	$$M-\mathrm{1}$$	$$(M-\mathrm{1})R$$	$$\mathrm{O}(M)$$
CSDS	2-hop	1	$$\mathrm{0.5}(M-\mathrm{1})R$$	$$\mathrm{O}(M^{\mathrm{2}})$$

^aNSM denotes number of sensors moved.

Another important metric that is measured in partition elimination is the message complexity of the algorithm, which indicates its scalability in large-scale networks. The message complexity is often measured by the total number of messages (TNM) in each execution loop of the algorithm. For CSDS, we have the following theorem.

Theorem 6.

The message complexity of CSDS is $O(M^{\mathrm{2}})$ .

Proof.

The message complexity refers to the maximum quantity of generated messages of all sensors in the worst case with respect to number of mobile nodes. First, since CSDS requires 2-hop neighboring information in critical sensor determination, there are a total of $\mathrm{2}M$ messages. Second, for the backup selection algorithm, the worst case structure for TNM is a pure ringlike topology as shown in Figure 7. In this topology, all sensors in the network are critical vertices, and each sensor needs to send a total of $M-\mathrm{2}$ messages just to search for the backup sensor, and another 2 messages are required to determine the backup sensor. This leads to a total of M messages for each sensor and $M^{\mathrm{2}}$ messages for the entire MSN in the backup selection step. Including the $\mathrm{2}M$ messages in the critical sensor determination, the TNM for CSDS is $M^{\mathrm{2}}+\mathrm{2}M$ which is $O(M^{\mathrm{2}})$ .

Figure 7

The worst case topology in terms of TNM.

In fact, CSDC may need to locate a remote sensor as its backup due to its requirement of only one sensor to be moved for the partition elimination. Then, a relatively higher message complexity is inevitable, as can be seen from Table 1. However, the worst case topology is extremely unlikely in a typical uniform randomly distributed MSN, and the critical sensors are expected to locate a backup within a few hops. This phenomenon can be clearly observed in experimental simulation, which will be discussed in the next section.

5. Experimental Simulations

5.1. Simulation Scenarios and Performance Metrics

In the simulation scenarios, an initially connected MSN is randomly distributed into 1000 m × 1000 m area of interests. During the simulation, a random possible cut-vertex fails at a given time point. Each simulation is run for 50 different network topologies and the results were based on the average performances. We choose the NSM, TNM, and TMD as the performance matrices to evaluate the overall efficiency of CSDS against other popular methods. We adopt DARA, HERO, and PADRA+ as the baseline approaches to compare with the proposed CSDS, due to their similarity of using two-hop neighboring information in the restoration process.

5.2. Results and Discussions

Before presenting the performance evaluation of CSDS, a simulation study is conducted to show the possibility of 1-hop and 2-hop backups; that is, among the critical sensors in a randomly distributed network, how many of them have a backup from their 1-hop or 2-hop neighboring sets. The results shown in Figure 8 indicate that CSDS guarantees a high possibility that the critical sensor can locate a backup within 2 hops, which is important since it can effectively reduce the message cost by avoiding searching through the networks. Meanwhile, when the network becomes denser, the number of critical sensors is rapidly decreased; thus, there is an even higher possibility to locate a 1-hop backup sensor.

Figure 8

Ratios of 1- and 2-hop backup sensors with increased density.

The results of NSM are shown in Figure 9(a). Only 1 sensor is involved in a restoration process for CSDS. Meanwhile, the NSM for PADRA+ is around 2.5, due to its computing of CDS and the cascaded movement scheme. The NSM for DARA is around 4, and an even higher NSM can be observed for HERO due to its attractive potential function that causes smaller movements of a relatively large number of sensors. The NSM for HERO becomes at most 7 with the increased density of the network.

Figure 9

Comparative studies. (a) Number of sensors moved with increased density, (b) total number of messages with increased density, and (c) total movement distances with increased density.

Furthermore, the TMN of CSDS is shown in Figure 9(b). Since the message complexity for CSDS is $O(M^{\mathrm{2}})$ , relatively higher message cost is expected in comparison with HERO and DARA, whose message complexity is $O(M)$ . Moreover, since PADRA+ allows cascaded movements, its TNM is also smaller than CSDS, even though its message complexity is also $O(M^{\mathrm{2}})$ . It is worthwhile to note that the TMN of CSDS is much smaller than $M^{\mathrm{2}}$ due to the fact that the occurrence of the worst case topology is unlikely, and the possibility of locating a 1-hop backup is high. Therefore, the relatively higher TMN should not be a major concern in applications.

As an important factor to evaluate the efficiency of the partition elimination, the results of TMD are shown in Figure 9(c). Comparing with cascaded and potential function based movement pattern, direct relocation of only 1 sensor can effectively reduce the TMD regardless of the topology and density of the networks. As is validated in the simulation study, the TMD of CSDS is smaller than that of the HERO, PADRA+, and DARA and is further reduced as the density of the network is increased. The TMD of CSDS can be as small as nearly 50 meters when the number of sensors reaches 180, which validates that the backups are almost always selected from the 1-hop neighbor sets.

6. Conclusions

To minimize the impacts on the network structure and sensor's current tasks, a partition elimination strategy CSDS, which moves only one sensor during a restoration process, is presented in this work. CSDS is fully distributed and requires only local information of 2-hop neighbors. Consisted of a graph-theoretic based critical sensor determination algorithm and an effective backup sensor selection algorithm, CSDS can restore the disconnections of the network caused by the failure of a cut-vertex immediately. Experimental simulation studies verify that, with a slightly higher message cost, CSDS can improve the efficiency of connectivity restoration in terms of total movement distance and maintain the layout of the sensor system by moving only one mobile sensor.

Future work will consider the network optimization prior to the disconnection of network or during the connectivity restoration process by implementing clustering algorithms and dual descent approach [30]. More realistic system and environment models will also be considered so that the connectivity restoration methods can be more suitable in the real-world applications.