A Novel Hybrid Optimization Scheme on Connectivity Restoration Processes for Large Scale Industrial Wireless Sensor and Actuator Networks

Abstract

In the wireless sensor and actuator networks (WSANs) of industrial field monitoring, maintaining network connectivity with coverage perception plays a decisive role in many industrial process scenarios. The mobile actuator node is responsible for collecting data from the sensing nodes and performing diverse specific collaborative operation tasks. However, the failure of the nodes usually causes coverage vulnerability and partition of the network. Urgent and time-sensitive applications expect a minimum coverage loss to complete an instant connectivity restoration. This paper presents a hybrid coverage perception-based connectivity restoration algorithm, which is designed to restore network connectivity with minimal coverage area loss. The algorithm uses a backup node, which is selected nearby the critical node, to ensure a timely restoration when the critical node encounters failure. In the process of backup node migration, the optimal destination will be reselected to maintain the best network coverage after network connectivity recovery. The effectiveness of the proposed algorithm was verified by some simulation experiments.

1. Introduction

With the continuous development of sensor technology, computing power, and embedded intelligent systems, the applications of large-scale wireless sensors and actuator networks (WSANs) have attracted more and more attention for industrial processes [1,2,3,4]. Adding actuator nodes to wireless sensor networks not only enhances the practicality of the networks, but also expands the application functions of these kinds of industrial networks.

As shown in Figure 1, in marine WSANs, movable ships for field monitoring are regarded as the actuator nodes, which are responsible for converging and transmitting information, decision-making, and performing corresponding actions. The sensor nodes are responsible for perceiving the surrounding environment, and can forward the sensing information by multi-hops. The sensor nodes are usually static, while the actuator nodes are movable, and have more energy, powerful computing and storage capabilities, and larger communication ranges. So, these actuator nodes can be manned or unmanned boats, marine mobile robots, or other smart marine devices. The role of the actuator node is to make execution decisions based on the data that the sensor node perceives. Marine WSANs have broad prospects for applications in border protection, environmental monitoring, maritime search and rescue, disaster warnings, etc. [5,6,7].

In general, for this kind of distributed monitoring and control of large-scale industrial processes, there are various kinds of field disturbances that affect the nodes′ working states. It is a common phenomenon for the network connectivity to be interrupted due to interference and node failure, and the failed nodes will have a negative impact on the network coverage. In most applications, network connectivity with perceptual coverage is very important [8,9]. The nodes in WSANs receive data from various kinds of sensors through autonomous cooperation, and fuse to make decisions on the data. The actuator nodes can make corresponding coordination and response actions for interference events [10]. For example, in marine oil spilling detection and protection systems, the sensor network deployment area cannot have any coverage vulnerabilities because it is an event-sensitive detection network, and we do not want oil spills to diffuse to larger and larger extents due to network coverage loss. When the sensing node detects the oil spill, the actuator node immediately executes and controls the oil spills diffusion. This kind of event sensitive collaboration action relies highly on the network to maintain connectivity based on coverage perception [11].

This paper presents a hybrid perception coverage-based connectivity restoration algorithm, which is designed to restore network connectivity to the optimal network coverage rate. It is of great significance to the self-healing control of industrial processes. The algorithm uses a hybrid approach to set up backup nodes around the critical nodes to timely restore network connectivity. There is no overreaction when a non-critical node loses efficacy. When selecting an alternative backup sensing node to replace the abnormal node, the overlap of the coverage area of the neighbor nodes and the abnormal node is taken into consideration. The neighbor node with maximum overlap area will be considered preferentially, and in the backup node migration process, the optimal destination of the migrating node is re-selected, to make nodes maintain the maximum coverage area. However, the proposed algorithm is not suitable for scenarios where multiple nodes are disabled at the same time.

The rest of this paper is organized as follows: the work on existing connectivity remediation algorithms is discussed in Section 2. The problem model is described in Section 3. The 4th section describes the details of the proposed algorithm. Simulation and analysis results are presented in Section 5. Section 6 concludes the paper.

2. Related Works

In wireless sensor networks, connectivity is the required premise to guarantee data transmission. The loss of connectivity poses a threat to the integrity and accuracy of network data. Therefore, it is very important to restore network connectivity [12]. Meanwhile, due to a lack of resources, the restoration process requires minimal resource expenditure as well as minimal influence on network performance. The network performance here refers to the impact on applications, caused by the decline of data integrity and accuracy. However, most of the connectivity restoration schemes belong to the reaction style, which is only concerned with the moving distance in the repair process, rather than evaluating the impact of node failures on network connectivity, and it usually ignores the coverage area during the restoration. Once a node failure happens, the implementation of these methods may also involve the relocation of critical nodes, which do not have any positive effect in the restoration process, since the moving of critical nodes will have an additional negative impact on the topology control of the network. In addition, many schemes do not consider the impact of failed nodes on network coverage rate, and they usually ignore the impact of coverage rate on the network performance during the restoration of network connectivity [13,14].

The RIM (Recovery through Inward Motion) algorithm was proposed in [15]. Its main idea is that all neighbors of the failed node move inwards until they are all connected to each other. As a result, the network performance will be affected by the degradation of network coverage. The algorithm executes recursively until all the nodes are connected again. This kind of reactive scheme may not be suitable for time sensitive critical applications, since these applications cannot usually tolerate the long-time calculations this algorithm uses. In addition, this algorithm not only has weak performance in the case of non-critical node failures, but also may cause unnecessary overhead in the case where critical nodes are involved in the restoration process. Moreover, the reduction of coverage may make the algorithm fail to respond to important events in time, which may cause serious consequences for applications.

In [16], Younis et al. proposed the DARA (Distributed Actor Recovery Algorithm) algorithm, which requires each node to maintain two-hop neighborhood information. The neighbors of the failed node detect and identify the fault. The best candidate will be selected among the neighbor nodes, and moved to the fault location. Moving the best candidate can lead to more link disconnection, and can recursively perform the connectivity restoration process in cascading way. Such reactive schemes can overreact to non-critical node failures and usually cause unnecessary overhead, by involving the critical nodes in the restoration process. Due to delays, these reactive schemes may not be suitable for the time sensitive tasks in some applications.

The authors in [17] proposed the C3R (Coverage Conscious Connectivity Restoration) algorithm to cope with the loss of coverage and connectivity caused by node failures through reorienting movable sensor nodes. The neighbors of the faulty node move backward or forward, providing temporary network coverage and intermittent connectivity, until an alternate node is deployed. It is a temporary restoration method. After the alternate node is deployed, each node returns to its original location. This algorithm does not distinguish between the critical and non-critical nodes, but provides a reactive way to save the energy overhead of each node.

NORAS (Node Recovery through Active Spare) is another restoration algorithm considering network coverage [18], which specifies the alternate nodes based on the network coverage and the connectivity of each critical node. However, in the NORAS algorithm, each node is required to maintain two-hop node status information, and the algorithm can only distinguish critical and non-critical nodes correctly at a 90% rate. In other words, it has the possibility of fixing the non-critical nodes as critical nodes, which would cause extra overheads.

The CARE (Coverage-Aware connectivity Restoration) algorithm proposed in [19] is also a connectivity restoration algorithm that concerns the coverage area of the network. The design idea of the algorithm is based on the concept that nodes can look after one another. Unlike most of the reactive schemes, CARE is an early defense type algorithm that finds a specific care node for each critical node in advance. Only the care node detects the fault situation of the node, and in the case of node failure, the care node replaces the failed node to perform the restoration. This is an early defensive type algorithm that requires information about the entire network, and the choice of destination for the alternate node does not consider the network coverage rate.

In [20,21,22], the impact of placement of relays is investigated. The experiments in [20] revealed that the diversity order gain depends not only on the number of relays, but also on the relay placement. It was proved in [21] that changing the energy threshold for source transmit power and relay location could improve the performance of the network. In order to control the outage probability of the network, two relay selection schemes were proposed in [22], which were named limited interference (LI) and quasi-orthogonal (QO). In conclusion, when selecting relays, a network restoration algorithm should take into account not only the number and location of nodes, but also the communication channels of nodes into consideration.

This paper presents a hybrid connectivity restoration algorithm distinguishing critical nodes and non-critical nodes in the network. It seeks a backup node for each critical node in advance. When a node fails, the algorithm will choose an optimal destination for the migration of the backup node. After the alternate nodes migrate to their destinations, not only is the connectivity of the network restored, but also the local coverage area maintains its maximum value. In this way, this coverage-oriented connectivity restoration algorithm does not require redundant network nodes, and the reduction of coverage is maintained as low as possible. According to the features of the proposed method, we can make some conclusions of the comparison with other methods as follows: The RIM algorithm requires that all neighbors of the failed node move inwards, while the proposed algorithm only moves the selected backup nodes, which obviously reduces the total moving distance of nodes. The DARA algorithm requires each node to maintain two-hop neighborhood information, and can lead to overreacting to non-critical nodes. Instead, the proposed algorithm distinguishes critical nodes and non-critical nodes in the network, and only the selected backup nodes need to maintain one-hop information tables of the corresponding critical node. The C3R algorithm is a temporary restoration method, which consumes much more energy than the proposed algorithm. Although the NORAS algorithm can distinguish between critical and non-critical nodes, it cannot reach an acceptable accuracy compared to the proposed algorithm. Compared with the proposed algorithm, the CARE algorithm does not consider the network coverage rate during connectivity restoration.

3. System Model

3.1. Network Model

In this paper, the nodes in the network are mainly the actuator nodes in the wireless sensor and actuator networks. All nodes in the network communicate with each other using OFDM (Orthogonal Frequency Division Multiplexing) modulation in the Media Access Control (MAC) layer of the network. The nodes can move at the same speed through the network, and know their positional information through the positioning device. Each node maintains a neighbor information list, and can know the location, status and other information of neighboring nodes. The communication radius (r_c) of the node refers to the maximum Euclidean distance that its radio energy achieves, and assumes that all the nodes have the same communication radius [23]. The perceived range (r_s) of the node refers to the coverage of the node that can effectively acquire event information, and performs the corresponding actions, where r_s is assumed to be half of the maximum communication radius r_c.

As shown in Figure 2, A1–A13 are all the actuator nodes. The coverage of each node is a circular area, and the dotted circles in the figure are the coverage area of the nodes. The perceived radius of each node is the same, and each node can communicate with each other. It is assumed that each node in the initial network has the same communication radius, perceived radius, computational power, residual energy, and a unique identity (ID). This model was chosen as the basic model to analyze network connectivity.

3.2. Node Coverage Aware Model

The coverage problem of the network is often related to the perceived model and the position of the actuator nodes. Here we adopted the omnidirectional perception model, and the node sensing range is the two-dimensional circular space centered on the node. Such a perceptual model is made for ideal cases. Actually, the perceived area is associated with its surroundings and disturbances. Here, we used the Boolean perception model [24], for as long as the event occurs within the sensor′s perceived area, it can be successfully perceived with the probability of 1. The mathematical expression is described in formula (1)

$$p(i,j)=\{\begin{array}{c}1,\hspace{1em}\hspace{1em}d(i,j)\le 2r_s\\ 0,\hspace{1em}\hspace{1em}d(i,j)>2r_s\end{array}$$

(1)

where, $d(i,j)$ is the distance between nodes i and j, $p(i,j)$ is the probability that there is an event point, which can be perceived by node i and node j simultaneously. r_s is the perceived range of nodes i and j.

Figure 3 shows the model of perceptual overlapping coverage between two adjacent nodes, A and B. With nodes A and B as the centers, the areas covered by the circles with the radius of r_s constitute the whole network coverage area. M and N are the intersections of the two circles, and P and Q are the intersections of the arcs within the overlapping area, and the A to B (AB) line.

The shadow area, comprised of the area between M, Q, N, and P, (MQNP) is the overlapping coverage area. The length of AB is smaller than the communication radius, r_c, of the nodes, and the smaller AB is, the larger the overlapping coverage area will be.

We can calculate the overlap area with the model in Figure 3. The area of the portion MPN is the area of sector BNPM minus the area of triangular region BNM, and it can be expressed as Formula (2). The whole shadow area is just twice the area of the MPN portion.

$$S_{MPN}=S_{BNPM}-S_{BNM}$$

(2)

where $S_{BNPM}$ is the area of the sector, $S_{BNM}$ is the triangular area, and $S_{BNPM}$ can be calculated by Formula (3).

$$S_{BNPM}=2\times r_s^2\times (\angle MBQ\times \frac{\pi }{360})$$

(3)

where $\angle MBQ$ can be calculated by Formula (4).

$$\angle MBQ=\arccos (0.5\times \frac{AB}{r_s})$$

(4)

The area of the triangular region $S_{BNM}$ can be calculated by Formula (5).

$$S_{BNM}=\frac{1}{2}\times r_s^2\times \sin (\angle MBN)$$

(5)

Finally, the total overlapping area of the shadow can be calculated as Formula (6).

$$S_{MPNQ}=2\times (S_{BNPM}-S_{BNM})=r_s^2\times (\angle MBQ\times \frac{\pi }{180}-\sin (\angle MBN))$$

(6)

The location of the faulty actuator node will affect network connectivity and coverage. Therefore, the purpose of this article is to maintain the minimum reduction rate of network coverage, and to restore the network connectivity when a faulty node appears in the network. For example, in the network of Figure 1, the failure of node A6 will seriously harm the connectivity of the network, and cause coverage loopholes in the network. Even if the connectivity recovery algorithm is performed, when replacing the faulty node with the surrounding node, a coverage loophole still emerges because of the reduction of the network coverage area. So, it is very challenging to consider the coverage of network when restoring connectivity.

4. Algorithm Details

As mentioned above, the failure of the critical actuator nodes not only divides the network into disjointed networks, but also brings loopholes into the networks. Ignoring the criticality of nodes will cause additional movement consumptions. In order to solve this problem, the proposed algorithm distinguishes node criticality, and uses an active restoration mechanism to select an alternative node for each critical node from its neighbor nodes. In the implementation of the restoration process, the reactive mechanism will be adopted, and the destination coordinates of the alternative node will be reselected to reach its maximum coverage. When an alternative node detects that the monitored critical node is faulty, it will trigger the restoration process. In order to maximize the local coverage area, the alternative node recalculates the optimal coordinates of the migration destination, and the alternative node migrates to this position. Therefore, the network connectivity is restored, and the local coverage area could also be maintained at its maximum value.

The proposed algorithm is divided into the following steps:

(1)

Distinguish the criticality of each node in the network and mark the criticality record in the information table of corresponding nodes.

(2)

Select a neighbor node as an alternative node for each critical node based on the principle of maximum overlapping area of regional coverage. Instead of being a redundant node, the selected node should be an ordinary actuator node in the network.

(3)

When the alternative node detects the failure of a critical node, the alternative node calculates the optimal destination of migration to maximize the local coverage area after migration.

(4)

If the alternative node is not a critical node, the restoration process will be completed after the node moves to the destination location. If the alternative node is a critical node, the connectivity restoration mechanism will be performed continuously until a non-critical node is selected to be the alternative node, and moved to the destination.

The following Sections describe the specific process of each step.

4.1. Distinguish the Critical Nodes and the Non-Critical Nodes

If a network’s non-critical nodes fail, it will not affect the network′s connectivity. So, identifying the criticality of each node helps the network reduce the energy consumption for movement in the restoration process. Therefore, distinguishing the critical and non-critical nodes plays an essential role in the proposed algorithm, and each critical node has an alternative node as backup node.

The topology of the network may change frequently, and this requires a specific restoration algorithm to maintain the mobility, expandability, and robustness of the network. So, the LASCNN (Localized Algorithm for Segregation of Critical/Non-critical Nodes) algorithm [25] is adopted to calculate the criticality of network nodes. This algorithm can distinguish the critical nodes of the network with high precision, and the accuracy can reach 90%. More importantly, the accuracy of this algorithm can reach 100% when identifying non-critical nodes. The advantage of 100% accuracy for identifying non-critical nodes is exactly what the proposed algorithm needs. A schematic diagram after distinguishing the critical and non-critical nodes is shown in Figure 4.

4.2. The Backup Alternative Nodes Setting

After distinguishing the critical and non-critical nodes of the network, we can select a neighbor node for each critical node as the corresponding backup node. The selected backup node can be a non-critical node or a critical node. When a critical node fails, the backup node can move to the failed node′s area and replace the failed node, and the network can thus be self-healing.

Selection of the backup nodes:

The backup node is not a redundant node, but a node temporarily with two different functions. That means it can take on the perception tasks as an ordinary actuator node, and it is also responsible for maintaining the normal communication between itself and the critical node. The neighbor nodes of a faulty node may not communicate with each other, because each node only stores information of one-hop of its neighbor nodes. The proposed algorithm reserves a backup node for each critical node so that the network can have capacity for fault tolerance. The selected backup node needs to maintain the one-hop information table of the corresponding critical node. When selecting a backup node, the parameters used as references are as follows.

(1) Overlap of the coverage area of the node

The total overlap area of node i and all its surrounding neighbor nodes can be calculated by Formula (7), where S_ij is the overlap area between nodes i and j.

$$S_{all}={\displaystyle \sum _{j\in N_i}{S}_{ij}}$$

(7)

The larger the total overlap coverage is, the lower the coverage reduction rate caused by the movement of the node is, and the higher the possibility for the node to be chosen as a backup node will be.

(2) Node degree

The node degree of a node refers to the number of communication links between the node and the other nodes, and it is equal to the number of neighboring nodes of the node. The greater the degree of the node is, the larger the number of its surrounding nodes is, and the greater the possibility that the node is a critical node will be. When we prepare to perform the restoration of the network, it is better to select a backup node with a small node degree number. For the network in Figure 4, the information about the critical nodes and their corresponding backup nodes is shown in

Table 1. Critical node and the corresponding backup node.

Critical Node	The Backup Node
A3	A1
A4	A8
A8	A9
A6	A8
A10	A11

.

(3) Orthogonal channel [22]

The algorithm prefers to select nodes using orthogonal channels when the candidates have a similar total overlapping coverage area.

Faulty node detection:

Once the backup node is marked, it begins to monitor the specified critical node. Through the heartbeat information between the nodes of the network, the backup node can detect the situation of the protected critical node in time. The monitoring algorithm running in the node periodically detects faulty nodes through heartbeat communication among the nodes in every detection round. If the backup node does not receive enough heartbeat information as expected, the backup node considers the protected node to be abnormal, and thereby the restoration algorithm will be inducted. As shown in Figure 5, after the A6 node fails, the connectivity of the whole network is destroyed, the network is divided into blocks which results the partition between these blocks, the network cannot guarantee the reachability between any two nodes in the network, and the network coverage rate is reduced as well.

4.3. Relocate the Backup Node to the Best Destination

When a faulty node is detected certainly, the backup node set up in advance will perform the restoration strategy, and initiate the cooperative motion. When the backup node is a critical node, it will be a cascaded motion, and the restoration algorithm will continue to perform in the next backup node, until the next backup node is not a critical node. Before the backup node migrates, it sends a message to the surrounding neighbor nodes, and this will update the one-hop neighbor information table which exists in each neighbor node.

In the process of selecting the migration location of backup nodes, the coverage areas of the backup node and its surrounding neighbor nodes should be considered. After the backup node migrates to the location of the faulty node, there may be a coverage loophole left. Therefore, in order to obtain the lowest coverage loss of the network while restoring the network connectivity, we need to optimize the destination of the backup node migrating, which can maximize the effective coverage area while the backup node replaces the exited faulty node.

When the backup node detects that a failure has occurred in its monitoring critical node, the optimal destination coordinates are calculated to maximize the local coverage area. While calculating the coordinates of the migration destination, the principle of minimum overlapping area is used, that is to say, a set of non-linear programming equations is established, and the coordinates of nodes corresponding to the minimum value of overlapping area function are solved. Thus, the calculated coordinate can be considered as the optimal position of migration destination. The specific schematic calculation model is shown as Figure 6.

Assume that the optimal coordinates of node O is (x, y). The coordinates of nodes 1, 2, and 3 are known quantities, they are (x₁, y₁), (x₂, y₂) and (x₃, y₃), respectively.

The most appropriate location is the minimum coverage of node O and the other neighbor nodes. The total coverage of node O and the other neighbor nodes is S.

Supposing that $i$ is the neighbor node of node O, $S_{Oi}$ is the overlapping coverage of node O and node $i$, and it can be calculated by Formula (8).

$$S_{Oi}=r_s^2\times (\theta -\sin (2\theta ))$$

(8)

where,

$$\theta =\arccos \frac{Oi}{2r_s}$$

(9)

$$Oi=\sqrt{{\left(x-X_i\right)}^2+{\left(y-Y_i\right)}^2}$$

(10)

The overall objective function of overlapping coverage area is represented by Formula (11):

$$S={\displaystyle \sum _{i=1}^n{S}_{Oi}}={\displaystyle \sum _{i=1}^n{r}_s^2\times (\arccos \frac{\sqrt{{\left(x-X_i\right)}^2+{\left(y-Y_i\right)}^2}}{2r_s}-\sin (2\times \arccos \frac{\sqrt{{\left(x-X_i\right)}^2+{\left(y-Y_i\right)}^2}}{2r_s}))}$$

(11)

Every adjacent node and O-point have the constraints as follows:

$$\{\begin{array}{c}\Vert O_1\Vert \le r_c\\ \Vert O_2\Vert \le r_c\\ \Vert O_i\Vert \le r_c\end{array}$$

(12)

That is

$$\{\begin{array}{l}\sqrt{{\left(x-X_1\right)}^2+{\left(y-Y_1\right)}^2}\le r_c\\ \sqrt{{\left(x-X_2\right)}^2+{\left(y-Y_2\right)}^2}\le r_c\\ \sqrt{{\left(x-X_i\right)}^2+{\left(y-Y_i\right)}^2}\le r_c\end{array}$$

(13)

Under these constraint conditions for nonlinear programming, the minimum value of the objective function S and the corresponding coordinate value (x, y) can be yielded, which is the optimal migration destination coordinate.

As shown in Figure 7, when the node A6 fails, its backup node A8 detects the failure and immediately calculates the optimal destination location to replace node A6. This calculated location ensures that the overlapping coverage area, consisting of the original surrounding neighbor nodes of the faulty node A6 and the migrated node A8, is the smallest. This minimizes the coverage loss caused by the restoration connectivity algorithm.

4.4. The Situation that Backup Node is Critical Node

If the migrated backup node is a critical node, its backup node can also detect its loss, and also executes the optimal destination calculation program to get the appropriate location and migrate to replace it. According to the rule of minimizing the loss of network coverage, the algorithm selects a backup node for each critical node which acts as a care node in case of failure occurring. The progress repeats until a non-critical node is selected to be a backup node. However, a threshold is set to prevent the algorithm from entering an infinite loop. The threshold represents the maximum repeat times of the algorithm. The base station counts the number of times the algorithm is repeated, and decides whether to stop the algorithm. When the threshold is reached, the base station will change its strategy. Instead of finding a node with the scheme of optimal coverage area, the algorithm will directly select a non-critical node and move it to the calculated destination. At this time, the previously selected critical node sends a message to its one-hop neighbor nodes. If a non-critical node receives the message, it will send a message back, and the first non-critical node that sends a message back will be selected as a backup node. Otherwise, these one-hop neighbor nodes will send message to their own one-hop neighbor nodes to find a non-critical node. This will repeat until a non-critical node is selected as a backup node and moved to the calculated destination. There must be non-critical nodes in the network, and every node in the network must have neighbor nodes. By the way a of hop by hop search, the algorithm will find a non-critical node. Thus, the algorithm will not enter an infinite loop in regular cases. As shown in Figure 8, node A9 is the backup node of node A8, when A8 migrates away, A9 will calculate the coordinates of the optimal location and migrate to the destination. In Figure 8, A8` denotes the original location of node A8. If A9 is still a critical node, the cascaded operations will continue until the backup node is not a critical node; If A9 is a non-critical node, the connectivity restoration algorithm with coverage optimization is terminated. As we know, the failure or migration of non-critical nodes will not affect network connectivity, so the connectivity of the whole network can be guaranteed.

The pseudocode is divided into a base station part: Algorithm 1 and a node part: Algorithm 2 as required, and the callback function is applied in the procedure. The base station sends instructions to nodes and saves the messages from nodes. The node part mainly calculates the coverage area and the criticality of the nodes, and sends information to the neighboring nodes. It is a combination of distributed and centralized methods. A function named “FindNonCriticalNode” is defined to select a backup node after the threshold is reached. Through calling the function recursively, at least one non-critical node can be selected as a backup node. A function named “ReceiveResponse” is defined for the base station to receive messages sent by nodes. The nodes send messages back to base station after calculation, and the base station receives these messages when the function is called.

The pseudocode of the proposed algorithm is represented as follows:

Algorithm1. Coverage Perception Based Connectivity Restoration Algorithm (The Base Station Part)

-- Ci: the criticality of the node -- C: the threshold of the criticality -- S: the overlap area with each neighbor node -- Sbest: the maximum overlap area --T: the threshold of the algorithm --message A: base station requires each node to calculate Ci --message B: base station requires the neighbor nodes of failure node to calculate S --message C: base station requires selected node to find a non-critical node among its neighbor nodes --message D: the node calls for the function “FindNonCriticalNode” 1: Initialization 2: function ReceiveResponse 3: { 4: receive the messages sent by nodes 5:} 6: F ← 1 7: send message (A) to each node to calculate Ci 8: call for the function ReceiveResponse() 9: if receive the message from nodes 10:  then mark the nodes as a critical node 11: end if 12: While F 13: Count ← 0 14: Sbest ← 0 15: if the failure of a node is detected 16:  if Count < T 17:   then send message (B) to the neighbor nodes of the failed node 18:     call for the function ReveiveResponse() 19:     if base station receives S && S > Sbest 20:       then Sbest ← S 21:         select the node with Sbest as the backup node 22:     end if 23:  else send message (C) to the selected node 24:    call for the function ReceiveResponse() 25:    save the first response of the nodes 26:  end if 27:  calculate the best destination coordinates 28:  relocate the backup node to the location 29:  if the backup node is not a critical node 30:   then F = 0 31:  end if 32: end if

Algorithm2. Coverage Perception Based Connectivity Restoration Algorithm (The Node Part)

-- Ci: the criticality of the node -- C: the threshold of the criticality -- S: the overlap area with each neighbor node -- Sbest: the maximum overlap area --T: the threshold of the algorithm --message A: base station requires each node to calculate Ci --message B: base station requires the neighbor nodes of failure node to calculate S --message C: base station requires selected node to find a non-critical node among its neighbor nodes --message D: the node calls for the function “FindNonCriticalNode” 1: Initialization 2: function FindNonCriticalNode /* find a non-critical after the threshold is reached */ 3: { 4: send message (D) to one-hop neighbor nodes 5: } 6: if receive message (A) from base station 7: then calculate Ci              /*LASCNN algorithm*/ 8:    if Ci > C 9:     then mark itself as a critical node 10:       send message back to base station 11:    end if 12: end if 13: if receive message (B) from base station 14:  then calculate S              /*$\mathrm{S}={\displaystyle {\sum }_{\mathrm{j}\in N_i}{S}_{ij}}$*/ 15:  send S back to base station 16: end if 17: if receive message (C) from base station 18:  then call for function FindNonCriticalNode() 19: end if 20: if receive message (D) from one-hop neighbor nodes 21:  if it is a non-critical node 22:   then send message to base station and select itself as a backup node 23:   else call for function FindNonCriticalNode() /* call the function recursively */ 24:  end if 25: end if

5. Simulation and Analysis

5.1. Simulation Environment Settings

We performed a simulation to verify the effectiveness and reliability of the connectivity restoration algorithms by comparing the proposed algorithm to other algorithms. The proposed algorithm was designed and analyzed on the Matlab2010b simulation platform. Assume that the network is composed of actuator nodes randomly distributed in an area of 800 m × 800 m.

First, the communication radius (r) is fixed at 100 m, the total number of sensor nodes (N) changes from 10 to 140, to construct different network topology relationships. For random single node failures, the restoration algorithms are implemented, and the corresponding data are recorded.

Then, the total number of sensor nodes is fixed at 80, the communication radius is a variable and it varies between 60 m and 140 m, and the change step is 20 m. For random single node failures, the restoration algorithms are implemented, and the corresponding data are recorded. In the simulation experiment, the total number of nodes and the node communication radius are used as the dependent variables. In this paper, we do not consider the channel interference problem of the MAC layer, and assume that the nodes can communicate with each other reliably within the effective communication range.

In order to analyze the effectiveness of the proposed algorithm, the DARA [16] and CARE [19] algorithms are used as contrast algorithms. We make the analysis and comparison from the following aspects.

(1) Coverage reduction rate

This parameter is the main concern of the connectivity restoration algorithm with perceptual coverage, which is the main parameter to measure the influence of the algorithm on network coverage. The coverage reduction rate is the ratio of the difference between the coverage areas of the whole network, before and after connectivity restoration, to the area of the entire network deployment area. The calculation of the coverage reduction rate is shown as equation (14)

$$r=\left|C_a-C_b\right|$$

(14)

where $C_a$ represents the coverage after restoration, and $C_b$ represents the coverage before restoration. To calculate $C_a$ or $C_b$, we can use the formula of coverage rate calculation as follows

$$C=\frac{U_{i=1,2,\dots ,n}^{\epsilon }}{S_A}=\frac{U_{i=1.2.\dots ,n}{A}_i-U_{i=1.2.\dots ,n}^{ov}}{S_A}$$

(15)

where $S_A$ represents the area of the region where the network is located, i is the node ID, and n is the total actuator nodes in the network. $A_i$ is the coverage area of node i. $U_{i=1,2,\dots ,n}^{\epsilon }$ is the effective coverage area of n nodes, $U_{i=1.2.\dots ,n}{A}_i$ is the sum of coverage areas of all nodes, and $U_{i=1.2.\dots ,n}^{ov}$ is the overlapping coverage area among n nodes.

(2) Single node moving distance

The moving distance of a single node is the average distance that the migrating node moves each time during the execution of the restoration algorithm. The shorter the moving distance of each single node is, the more balanced the consumption of entire network will be, and there will be no network paralysis due to too much mobile energy consumption by some individual nodes.

(3) Total moving distance

This parameter refers to the sum of the moving distances of all the migrating nodes when the execution of restoration algorithm is completed. Considering that the migration movement consumes significant node energy, minimizing the total moving distance is an effective way to save overall energy in the network. The total moving distance is an important indicator of measuring the algorithmic performance of connectivity restoration.

5.2. Analysis of Simulation Result

Figure 9 shows the relationship between the reduction rate of coverage and the number of nodes. The failed nodes will inevitably lead to the reduction of network coverage. If coverage is taken into account while restoring connectivity, the coverage reduction rate will be significantly improved. The DARA algorithm does not consider the coverage of the network when it is restoring connectivity, nor does it distinguish the criticality of nodes. Recovery processes may involve the migration of multiple nodes, which eventually results in the loss of coverage area where the leaf nodes are located, thus leading to a large coverage reduction rate. Compared with the DARA algorithm, the CARE algorithm takes coverage area into consideration, which reduces the coverage reduction rate to some extent, but it does not consider the destination coordinate optimization of migrating nodes, and the improvement of CARE is therefore limited. The proposed algorithm in this paper further reduces the reduction rate of coverage area by choosing the optimal destination coordinates. As the simulation experiments shown, the proposed algorithm has obvious advantages in restraining the coverage reduction of the network.

It can be seen from Figure 9 that the coverage reduction rate of the DARA algorithm is about twice that of the CARE algorithm. Compared with CARE, the proposed algorithm has an advantage of about 20% in coverage reduction. Figure 10 shows the relationship between the coverage reduction rate and the communication radius, it can be seen that the influence of the communication radius on the coverage rate is higher than the number of network nodes as a whole. Moreover, the proposed algorithm has little advantage over CARE, while the communication radius is small, but it has an obvious advantage when the communication radius increases.

It can be seen from Figure 11 that the proposed algorithm has an obvious advantage over the DARA algorithm in the moving distance of a single node. However, compared with the CARE algorithm, the result is inferior in the case of low node density. The reason is that, when the proposed algorithm recalculates the optimal destination coordinates during node movement, it sometimes leads to additional movement distance. However, in a dense network, the overlapping coverage of the nodes will increase, it will reduce the moving distance of the migrating nodes, and the proposed algorithm thus not only has advantage over DARA, but also over CARE. Figure 12 shows that the increase in communication radius of a node will result in an increase in the moving distance of the alternative nodes.

Figure 13 and Figure 14 show the difference of the total moving distance between the different algorithms with an accurate bar chart showing the varying of node density and communication radius, respectively. Due to the advantage of backup nodes setting method in the network, the proposed algorithm has great advantages whether the density of nodes or the radius of communication changes. Both the proposed algorithm and the CARE algorithm distinguish the criticality of the nodes, and use the method of setting the backup node or the guard node in the network. Therefore, they all have great advantages compared with the reactive type of algorithm, like DARA. However, the backup node selection of CARE does not take into account the total coverage area of the nodes or the distances situation among the nodes, thus it has no advantage over the proposed algorithm.

The experiments show that when the number of nodes is more than 10, the algorithm is capable of restoring the connectivity of the network. However, as shown in Figure 15, Figure 16 and Figure 17, as the number of nodes decreases, the advantages of the proposed algorithm decreases gradually. In this case, the performance of the three algorithms is almost the same, in terms of the two indicators of total moving distance of nodes and the moving distance of a single node. When the number of nodes is less than 10, it is possible for the algorithm to be ineffective. Because the nodes are deployed randomly, the failure of a single node could destroy network connectivity entirely. Apparently, it is hard, not only for the proposed algorithm but also for the other cited CARE and DARA algorithms, to restore connectivity by moving backup nodes in cases utilizing very few nodes. In other words, the proposed algorithm can still work well in lower connectivity networks, unless there are too few nodes in the network.

In general, the proposed algorithm has obvious advantages in terms of the coverage reduction rate, single node moving distance, and total moving distance. In terms of its advantage in resisting coverage reduction, it is greater in event-sensitive applications, and the smaller moving distance of the nodes gives it advantages in the energy consumption balance of the network.

6. Conclusions

In this paper, a connectivity restoration algorithm for perceptual coverage is proposed. In the process of restoring the connectivity of the network, the coverage area is taken into account, and the location of a migrated node replacing a faulty node is optimized; thus the regional coverage is improved. This method reduces the loss of network coverage as much as possible when network connectivity is restored after the failure of network nodes, and reduces the impact of node failure on network coverage as much as possible. This connectivity restoration algorithm, which focuses on network coverage, plays an important role in event-sensitive applications. The simulation results show that the proposed algorithm has great advantages in maintaining network coverage rate and reducing total moving distance of migrated nodes.