Dynamic Weight-Based Connectivity Recovery in Wireless Sensor and Actor Networks

doi:10.21203/rs.3.rs-2567211/v1

Download PDF

Research Article

Dynamic Weight-Based Connectivity Recovery in Wireless Sensor and Actor Networks

https://doi.org/10.21203/rs.3.rs-2567211/v1

This work is licensed under a CC BY 4.0 License

You are reading this latest preprint version

Wireless sensors and actor networks (WSANs) have been widely used in various fields, from basic data collection to precise real-time control and monitoring, including battlefield monitoring, rescue, and exploration. The actor nodes in a WSAN play a key role in processing and transmitting data, and because of the harsh environmental conditions encountered, network node failures are prone to occur. The failure of an actor causes a loss of connectivity with its neighbor nodes, resulting in network splits and failure to deliver messages between nodes. Therefore, determining how to quickly and autonomously recover network connectivity while minimizing the moving distance of backup nodes and the number of relocated nodes is crucial. In this paper, we propose a dynamic weight-based connectivity recovery (DWCR) method to minimize the total moving distance of actor nodes, the number of relocated nodes, the total messages sent, and the coverage loss rate. The proposed DWCR method involves selecting a backup node for each critical node by dynamically adjusting the weight. If a critical node fails, the backup node starts to move to restore the connectivity of the failed node. The simulation results indicate that the proposed DWCR method outperforms the recovery through inward motion (RIM) method and other methods in terms of minimizing the total moving distance, the number of relocated nodes, and the total messages sent. However, because the RIM algorithm requires the relocation of more nodes during the network process, the DWCR algorithm is slightly inferior to the RIM algorithm in terms of coverage loss rate. Nevertheless, the DWCR algorithm still outperforms the DARA and DCRMF algorithms.

Wireless sensor network

Weight-Based Connectivity Recovery

Distributed Actor Recovery

In a wireless sensor and actor network (WSAN) [1], sensors and actors work together to perform specific tasks. A WSAN consists of sensors, actors, and base stations. Because the actors in a WSAN can move, WSANs have numerous advantages over conventional wireless sensor networks (WSNs) [2][3][4][5][6]. Sensor nodes sense specific activities or events from an area of interest and send them to the relevant actor nodes. Actors are powerful high-performance nodes that collect and process data and transmit the processed data to the relevant base station. WSANs have mobile functionality and can be used for activities that are not suitable for human operation, such as battlefield reconnaissance, border surveillance, deep-sea exploration, and search and rescue [7][8][9][10]. The actors and sensors in a WSAN can cooperate and provide information collected about surrounding environmental conditions to a control center through multiple hops mode to facilitate monitoring and immediate response. The architecture of a WSAN is illustrated in Fig. 1.

Generally, a WSN can only perceive the external environment through wireless sensors and cannot make real-time autonomous decisions. Therefore, it cannot be used for some applications that require large-scale self-management. However, with the development of autonomous control technologies, the demand for WSNs that can make automatic decisions and control events in the external environment while left unattended is increasing. Therefore, actor nodes were introduced into conventional WSNs to create WSANs, which are characterized by perception abilities, high computing power, automatic control systems, communication capabilities, and high battery capacity battery; they are therefore able to perform more complex tasks. A WSAN requires only one actor to integrate the environmental sensing data collected by general sensors in the area; therefore, the deployment of actors is usually sparse and decentralized.

Although actors in WSANs can function autonomously in unattended environments, they can still be damaged or run out of battery, especially when deployed in harsh environments, which can lead to network interruptions [11][12][13][14] or network partition. To overcome the aforementioned problems, researchers have developed pre-configuration and reactive mechanisms [15][16]. Preconfiguration mechanisms involve deploying some redundant nodes in advance to ensure that each critical node has at least two independent paths, which can help prevent connectivity interruptions when the original path fails [17]. However, the main disadvantage of pre-configuration mechanisms is that they require the deployment of numerous redundant nodes, leading to excessive construction costs [18][19].

In contrast to pre-configuration mechanisms, reactive mechanisms involve the use of node relocation [20][21][22][23][24][25][26] to restore network connectivity immediately. Because they do not require the deployment of numerous redundant actors, reactive mechanisms are characterized by lower costs and higher scalability relative to pre-configuration mechanisms. However, existing reactive mechanisms are time-consuming and resource-intensive. Too many nodes are involved in cascaded motion, and some network recovery methods overreact to general node failures, which can result in an excessive number of relocated nodes and long recovery times. In summary, determining how to discover and resolve node failures as soon as possible and autonomously in a distributed environment [27] is crucial.

Researchers must explore the role of critical nodes in the network recovery process in detail to minimize the total moving distance, required time, and power consumption involved in the aforementioned process. Although numerous distributed critical node recovery algorithms have been proposed, most involve the movement of nodes over long distances or the transmission of large messages. The recovery through inward motion (RIM) algorithm is one such algorithm [28]. The RIM method involves nodes moving inward but is still characterized by the relocation of numerous nodes and a large total moving distance.

To address the shortcomings of the RIM algorithm and other node recovery methods, in this study, we developed a dynamic weight-based connectivity recovery (DWCR) method that can achieve higher performance in terms of the total moving distance and the number of relocated nodes. The main concept of the proposed DWCR method involves using a weighted formula to select a backup node for each critical node [29]. When a critical node fails, its backup node can be quickly moved into position to replace the original node, thus eliminating the need to deploy numerous redundant actors and minimizing the total moving distance. In addition, the DWCR method is a distributed method; each node is only required to maintain messages from its one-hop neighbors, thus minimizing the number of transmitted messages. During node recovery, the backup node may lose connectivity with the original neighbor nodes; therefore, the recovery process may be cascaded until the network is restored.

The remainder of this paper is organized as follows. Section 2 summarizes relevant studies on WSANs. Section III provides a detailed description of the proposed DWCR method. Section 3 presents the results of the simulation experiments and a comparison of the performance of different algorithms, and Section 4 presents an analysis of the proposed algorithm. Finally, Section 5 presents our conclusion and directions for future research.

A WSN can be defined as a self-configuring and infrastructure-free wireless network that collects data on physical or environmental conditions, such as temperature, sound, and motion, on-site through receivers and transmits the data to facilitate real-time monitoring and data analysis. Unlike WSNs, WSANs can function autonomously in an unattended environment, where they can make decisions and perform related operations based on the information collected. Therefore, WSANs can be used for battlefield monitoring, environmental surveillance, telemedicine, and scientific research and development as well as for other applications in smart cities and industrial settings. However, actor nodes in a WSAN can fail, causing them to lose connectivity with their neighbors and preventing them from transmitting messages. Actor nodes that can cause network partition upon failure are called critical nodes.

Researchers have developed two methods—namely pre-configuration mechanisms [15][16] and reactive mechanisms [17]—to solve the aforementioned problems. The node recovery through the active spare designation (NORAS) algorithm [30] is one example of a pre-configuration mechanism. The NORAS algorithm only pays attention to whether the failure of a backup node will cause network partition and the impact of such partition on network coverage during the backup node selection process. The NORAS method involves selecting the backup node with the highest overlapped coverage and strongest connectivity to replace the failed critical node and assume its function immediately. Although pre-configured mechanisms can maintain the connectivity of a network, they require the deployment of numerous redundant nodes, leading to high construction costs.

The distributed actor recovery algorithm (DARA) [17] is a distributed algorithm for instant node recovery that serves as a reactive mechanism. The method involves first selecting an appropriate node from among the two-hop neighbor nodes of the abnormal node and subsequently relocating the selected node to the position of the abnormal node. However, if the selected backup nodes cannot solve the problem of a network partition, the algorithm will continue to execute until the connectivity of the entire network is restored. Although this method can restore network connectivity according to the two-hop neighbor information of the faulty node and effectively minimize the total moving distance, the recovery process is not started immediately. Younis et al. proposed another reactive mechanism: the RIM algorithm [28]. The RIM approach involves moving the neighbors of the failed node inward to the location of the failed node, thus enabling them to connect and restore the network to its pre-failure state. However, the main disadvantage of RIM is that the inward movement leads to an increase in the number of relocated nodes and the total moving distance as well as a decrease in the coverage capacity of the network.

To address the shortcomings of the aforementioned algorithms, Yan et al. developed a hybrid connectivity restoration (HCR) algorithm [31] that combines active selection and passive (cascaded) motion. The HCR method involves preparing a backup node for each critical node in advance. When a critical node fails, its backup node is moved to the optimal location to connect with all of the original node’s one-hop neighbors. However, the HCR algorithm does not consider whether a selected backup node is a critical node and only considers the cost of the distance traveled by a single backup node. Zhang et al. developed the distributed autonomous connectivity restoration method based on the finite state machine (CRMF) algorithm [32] to reduce the total moving distance during restoration. The algorithm uses a finite-state mechanism to increase the adaptability of a dynamic network. When a node fails to recover the network connectivity, the algorithm updates the node state to redetermine whether each node in the network is a critical node. Unfortunately, the backup node is moved directly to the location of the critical failed node, thus increasing the total moving distance.

To minimize the total moving distance involved and the total messages sent during the recovery process, we developed the DWCR method, which is described in detail in this paper. The DWCR method involves using a dynamic weighting formula to select a backup node for each critical node before failure and notifying and moving the backup node to replace the failed critical node and recover network connectivity. The DWCR method can thus minimize the total moving distance and the total messages sent more effectively than can other methods.

In this section, we described the proposed DWCR algorithm in detail. The parameter settings and definitions and the DWCR system model are described in Sections 3.1 and 3.2, respectively. Sections 3.3 and 3.4 present the DWCR’s backup node selection and node relocation procedures as well as the corresponding pseudocode.

3.1 Parameter Settings and Definitions

The mathematical parameters described in this article are listed and defined in Table 1.

Table 1

DWCR parameter descriptions
$ID$	Unique ID for each node.
$i$	Current critical node.
$j$	Neighbor nodes of critical node $i$.
${N}_{i}$	Set of neighbors of critical node $i$.
${F}_{i}$	Failed critical node.
${a}_{1}$	When ${N}_{i}$ contains general nodes, the distance weighting factor in formula (1) is used.
${a}_{2}$	When ${N}_{i}$ contains general nodes, the branch degree weighting factor in formula (1) is used.
${W}_{a}$	Weights calculated using formula (1).
${b}_{1}$	When ${N}_{i}$ does not contain general nodes, the distance weighting factor in formula (2) is used.
${b}_{2}$	When ${N}_{i}$ does not contain general nodes, the branch degree weighting factor in formula (2) is used.
${W}_{b}$	Weights calculated using formula (2).
${d}_{ij}$	Distance between critical node $i$ and its one-hop neighbor $j$.
${R}_{c}$	Actor’s communication range.
NEIGH_TABLE	The neighbor table which records information on the node’s one-hop neighbor ($ID$, $POSITION$).

3.2 System Model

The DWCR method involves the construction and maintenance of a one-hop neighbor table for each node, which includes unique node ID ($ID$) and local location ($POSITION$) information for distributed data exchange and is used to minimize the total moving distance, the number of relocated nodes, the total messages sent, and the coverage loss rate. The DWCR algorithm consists of a backup node selection procedure and a node relocation procedure, which help solve the problem of network partition in real-time. Figure 1 illustrates the architecture and process of the algorithm.

3.3 Backup Node Selection Procedure

The proposed algorithm selects a backup node for each critical node because only critical nodes can cause network partition. The purpose of selecting a backup node is to ensure rapid network recovery and to minimize the total moving distance and the number of relocated nodes. Each node sends a broadcast message containing its $ID$ and local location to all nodes within its communication range to initialize the one-hop neighbor table.

If a critical node i has noncritical nodes as neighbors, it will be selected as a backup node first. This is because the noncritical nodes can act as backup nodes to minimize the number of relocated nodes. Conversely, if a critical node is used for network recovery, the number of affected nodes and the total moving distance is greater. In addition, to minimize the total moving distance, the distance between the faulty node and its neighbor nodes must be considered. The DWCR algorithm also selects nodes with lower connectivity to minimize the number of affected nodes.

Critical node i will preferentially select non-critical nodes from among its one-hop neighbors ${N}_{i}$ as backup nodes. If its neighbors include more than two noncritical nodes, the distance and degree of the nodes are calculated, and the weight ${W}_{a}$ of each node is determined using Formula (1). Because the loss of connection between non-critical nodes and their original neighbors does not cause network partition, the distance factor is weighted more heavily than the degree factor. According to our experimental results, optimal results can be obtained when the distance and degree factors are set to 0.9 and 0.1, respectively.

$${W}_{a}= Distance \times 0.9 + Degree \times 0.1$$

${W}_{b}= Distance \times a + Degree \times b$ , where $a+b=1$ (2)

The distance factors in formulas (1) and (2) can be calculated using formula (3):

$${d}_{ij}\text{ = }\sqrt{{\left({x}_{i}-{x}_{j}\right)}^{2}+{\left({y}_{i}-{y}_{j}\right)}^{2}} \forall i=\text{1,2},3,\cdots ,n$$

Formula (3) uses the coordinates of the critical node and its neighbors; i represents the $ID$ of the critical node, which is an integer from 1 to n; j represents the $ID$ of any neighbor node of critical node i; and ${d}_{ij}$is the distance between critical node i and its one-hop neighbor j.

If the neighbors of critical node i include no non-critical nodes but multiple critical nodes, formula (2) must be used, and the weights of distance and degree factors will be dynamically adjusted as the number of nodes and the communication range change. Generally, when formula (2) is applied in a dense environment, the weight of the distance factor a increases and the weight of the degree factor b decreases. However, as a network becomes sparser and the number of nodes decreases, the weights of the distance and the degree factors decrease and increase, respectively. This is because a critical node with a higher degree in a sparse environment is more likely to have a noncritical neighboring node that can serve as a backup node during the cascading recovery process. Therefore, fewer nodes are affected during the cascading recovery process.

In a dense environment, the probability of a critical node’s neighbors including general nodes is higher, and closer nodes can be directly selected as backup nodes to minimize the total moving distance. Therefore, as a network becomes denser, the weights of the distance factor $a$ and the degree weight factor $b$ will be dynamically adjusted upward and downward, respectively. However, parameters a and b must be continually adjusted according to the number and range of actors in different environments to obtain the optimal solution. Factors $a$ and $b$ can be calculated using formulas (4) and (5) [33]:

$$a=(640 n+1866.6 r)\times \frac{1}{Area}$$

$$b=1-a$$

where $n$ represents the number of nodes, $r$ represents the communication range, and $Area$represents the network size.

Figure 2 presents an example of a network topology including critical nodes. When a noncritical node (e.g., node A5, A6, or A7) is abnormal, initiating the network connectivity recovery process is unnecessary because the abnormality will not cause a network partition. Conversely, an abnormal critical node will lead to network partition; therefore, when a critical node fails, the connectivity recovery process must be initiated. For example, if node A17 is damaged, nodes A6 and A7 cannot communicate with node A18; therefore, A17 is a critical node. Similarly, nodes A0, A8, A9, A10, A13, and A18 are critical nodes. Because node A17 is a critical node, the DWCR algorithm must be used to select a backup node. First, node A18, which is a critical node, is excluded through the backup node selection procedure. Because the neighbors of A17 include general nodes, the weight of the backup node is calculated using formula (1). Although the degrees of nodes A7 and A6 are the same, node A7 is closer to node A17 (63 m < 71 m); therefore, node A7 is selected as the backup node for node A17. By contrast, node A9, another critical node, has many critical nodes but no general nodes as neighbors. In this case, the weights of nodes A8, A10, and A13 are calculated using formula (2), and node A10 is selected as the backup node of node A9 because it outperforms nodes A8 and A13 when the weights of distance and degree are considered.

After the backup node selection procedure is completed, critical node i will periodically send heartbeat information [26] to its backup node. When the backup node does not receive heartbeat information for a designated period of time, node i is determined to be malfunctioning. Accordingly, the backup node will start to relocate to recover network connectivity.

3.4 Node Relocation Procedure

Because only critical node failures can disrupt network connectivity and cause network partition, when the critical node i fails, its backup node j will immediately initiate the node relocation procedure to recover network connectivity. Generally, backup node j will first update the neighbor table $NEIGH\_TABLE$ of one-hop distance to the closest distance to the faulty node ${F}_{i}$. Backup node j, a critical node, tests whether it is connected to its one-hop neighbor after completing the node relocation procedure. If the network goes down, the node relocation procedure is cascaded until the network connection is restored. After the node relocation procedure is completed, the system redetects whether the adjacent neighbors of the original faulty node and the newly migrated node in the one-hop neighbor table are critical nodes. If a one-hop neighbor is identified as a critical node, the backup node selection procedure is performed to select a suitable backup node.

Figure 3 illustrates the results of applying the DWCR algorithm, specifically the node relocation procedure, to the network topology in Fig. 2. In Fig. 3(a), node A13’s one-hop neighbors, namely nodes A9, A14, and A15, are disconnected because of the failure of node A13. The backup node A15 moves to the position of A13 until it establishes connectivity with nodes A9 and A14, as illustrated in Fig. 3(b). Because node A15 is not a critical node, cascading the node relocation procedure after the relocation of node A15 is unnecessary. The topology of the recovered network after the execution of the DWCR algorithm is illustrated in Fig. 3(c).

The pseudocode of the DWCR algorithm is presented in Fig. 4. When the algorithm is first executed, each node broadcasts a message to notify its neighbors within its communication range and records the $ID$ and location of its neighbors to construct a neighbor table $NEIGH\_TABLE$ (line 4). Subsequently, each node determines whether it is a critical node by using $NEIGH\_TABLE$. If a node is a critical one, it undergoes the backup node selection procedure (line 8).

During the backup node selection procedure, formula (1) is used to select a backup node (lines 16–19) if the neighbors of critical node i include multiple general nodes. Conversely, if the neighbors of critical node i include only critical nodes and no general nodes, formula (2) (lines 20–24) is used to select a backup node. Subsequently, the backup node j can undergo the node relocation procedure to restore connectivity to the one-hop neighbors of the faulty node i.

1. Actor_coord: the coordinate of actors

2. ${R}_{c}$: the communication range for each actor

3. ${N}_{i}$: All neighbors of critical node i

4. Initialize a one-hop neighbor table NEIGH_TABLE

5. for each actor;

6. for every Actor i in a WSAN do

7. if Is_Critical(i) then

8. Backup Node Selection

9. else

10. back_ID = 0; Position =[ inf, inf ];

11. end if

12. if i failure

13. j moves to ∀${N}_{i}$={ j }

14. end if

15. Backup Node Selection

16. if ${N}_{i}$ have non-critical node

17. for Neighbor_hop1(i) do

18. ${W}_{a}$ = Distance $\times$ $0.9$ + Degree $\times$ 0.1

19. return node←max_${W}_{a}$ (Neighbor_hop1(i))

20. else

21. for Neighbor_hop1(i) do

22. ${W}_{b}$ = Distance $\times$ $a$ + Degree$\times b$

23. return node ← max_${W}_{b}$ (Neighbor_hop1(i))

24. end if

In this section, we present our simulation-based assessment of the relative performance of the proposed algorithm in terms of four key performance metrics: the total moving distance, the number of relocated nodes, the total messages sent, and the coverage loss rate. The DWCR algorithm is compared with the RIM [28], DARA [21], and DCRMF [32] algorithms.

4.1 Simulation Environment

The simulation experiments were conducted using Matlab R2019b in an environment equipped with an Intel Core i5-4210M CPU and 12 GB of RAM. The experiments involved two scenarios characterized by sparse and dense node distributions, respectively [31]. In each scenario, 50–250 actors were randomly deployed in an area of 800 m × 800 m, and the communication range r of the nodes was set to 100–250 m. In the first scenario, the actor communication range was set to 120 m, and the number of actors was set to 50–250. We analyzed the changes in the network recovery process as the number of nodes in the network increased, thus increasing the density of the network environment. The parameter settings are listed in Tables 2 and 3. In the second scenario, the number of actors was fixed at 80, and the transmission range varied from 100 to 250 m. We analyzed the changes in the network recovery process as the transmission range increased in size, thus increasing the density of the network environment. Four metrics were used to evaluate the performance of the DWCR algorithm.

Table 2

Parameter settings in the first scenario simulation
Parameter	Parameter setting
Area	800m x 800m
Number of actor nodes	50、100、150、200、250
Range	120m

Table 3

Parameter settings in the second scenario simulation
Parameter	Parameter setting
Area	800m x 800m
Number of actor nodes	80
Range	100、125、150、175、200、225、250m

4.2 Simulation Results

4.2.1 Total Moving Distance

The total moving distance is the total distance that each node moves during the recovery process after a critical node fails; it is mainly used to evaluate the efficiency of a recovery method [34]. As indicated in Fig. 6(a) and (b), although all the algorithms resulted in similar total moving distances in sparse environments, the DWCR algorithm resulted in a smaller total moving distance than the other algorithms in different scenarios. As the number of nodes or the communication range increases and the environment becomes denser, the total moving distance of RIM increases significantly when the RIM algorithm is used but remains relatively stable and even trends downward when the DCRMF or DWCR algorithm is used. The DWCR algorithm outperformed the DCRMF algorithm because the DCRMF algorithm necessitates the movement of a backup node to the location of the faulty node, whereas the DWCR algorithm only requires the backup node to move within the communication range of the faulty node.

4.2.2 Total Messages Sent

The total number of messages sent is defined as the total number of messages sent between nodes during the recovery process and is used to evaluate the communication costs of a recovery method. As indicated in Fig. 7, the proposed DWCR algorithm resulted in a lower number of total messages sent than did the DCRMF algorithm. In addition, the difference between the total number of messages sent during the execution of the DWCR and DCRMF algorithms was larger in the sparse environment and gradually decreased in magnitude as the environment became denser. However, the DWCR algorithm still exhibited superior performance. When the RIM and DARA algorithms were applied, as the environment became denser, the total number of messages sent increased significantly. Similarly, the DWCR and DCRMF algorithms both outperformed the other methods in a dense environment. This is because the larger the number of nodes in a network is, the higher is the probability of identifying a general node that can serve as a backup node. The DWCR and DCRMF algorithms can therefore minimize the total number of messages that must be sent during the network recovery process.

4.2.3 Number of Relocated Nodes

In general, the lower is the average number of nodes relocated during a connectivity recovery process [35], the weaker is the effect of the process on the entire network. As indicated in Fig. 8(a) and (c), relative to the other algorithms, both the DWCR and DCRMF algorithms required the relocation of fewer nodes in the first simulation scenario (r = 120, N = 50–250; fixed transmission range) as well as the second simulation scenario (r = 100–250, N = 80; fixed node number). This is because both of the aforementioned algorithms can distinguish between general node failure, which does not affect network connectivity, and critical node failure, which necessitates the relocation of a backup node. As indicated in Fig. 8(b) and (d), the DWCR algorithm requires the location of fewer nodes than does the DCRMF algorithm because the DCRMF algorithm requires the backup node to move to the location of the faulty node.

4.2.3 Coverage Loss Rate

Figure 9 illustrates the performance of the RIM, DARA, DCRMF, and DWCR algorithms in terms of coverage loss rate under different communication ranges and node numbers. As the communication range or number of nodes increased, the coverage loss rates corresponding to the four algorithms all decreased. As indicated in Fig. 9(a), the coverage loss rates of the DARA and PADRA algorithms were both higher than those of the DWCR and RIM algorithms, and all the coverage loss rates decreased as the communication range increased. In addition, the coverage loss rates of all four algorithms decreased significantly as the environment became denser; because of the increased actor density, more nodes were available to help restore network connectivity.

The performance of the four algorithms is compared in Table 4, wherein r represents the communication range, N represents the total number of nodes, and ${N}_{c}$ represents the total number of critical nodes. The items listed in the table are described as follows. The topology information path indicates that each actor can obtain the neighbor information of several hops. Max. distance by all nodes involved refers to the maximum total moving distance during the node relocation procedure. Max. distance by each node represents the maximum moving distance of each actor. Segregate critical/noncritical refers to whether only critical nodes must be relocated during the node relocation procedure. Finally, Max. relocation numbers refer to the maximum number of relocations during the node relocation procedure. The DWCR and DCRMF algorithm have obvious advantages in terms of total moving distance and number of relocated nodes. Furthermore, the simulation results obtained using the DWCR algorithm were significantly superior to those obtained using the DCRMF algorithm. Although the RIM algorithm exhibited the highest performance in terms of the coverage loss rate, it resulted in an excessive number of relocated nodes and an excessively large total moving distance, reflecting poor performance.

Table 4

Comparison of four algorithms
Item	RIM	DARA	DCRMF	DWCR
Topology information path	1-hop	2-hop	2-hop	2-hop
Max. distance by all nodes involved	(N − 1) ∗ r/2	(N − 3) ∗ r	(${N}_{c}$−1) ∗ r	(${N}_{c}$−1) ∗ r
Max. distance by each node	r/2	r	r	r
Segregate critical/non-critical	No	No	Yes	Yes
Max. relocation numbers	N-1	N-3	${N}_{c}$− 1	${N}_{c}$−1

The simulation results presented herein indicate that the DWCR algorithm can achieve high performance by using a dynamic weighting formula to select backup nodes for critical nodes in the early stages of WSAN construction. The dynamic weighting formula proposed in this paper adjusted the weights of different factors according to the simulation results. When a critical node fails and the network is partitioned, the backup node can be moved to the connection range of the neighboring nodes instead of the original location of the failed node. The node relocation procedure is only initiated if a critical node fails.

Regarding the total messages sent, in sparse environments, the RIM algorithm requires significantly more messages to be sent than do the DWCR, DCRMF, and DARA algorithms. As the environment becomes denser, the DARA algorithm requires more messages to be sent, mainly because connectivity to faulty general nodes must also be recovered while the node relocation procedure of the DARA algorithm is executed. Conversely, when the DCRMF and DWCR algorithms are applied, the total number of messages sent continues to decrease as the environment becomes denser. In addition, the DWCR method proposed herein resulted in a smaller total moving distance than did the other methods. In summary, the DWCR algorithm outperforms the RIM, DARA, and DCRMF algorithms in terms of total moving distance, total messages sent, and the number of relocated nodes in both sparse and dense networks. Although the DWCR algorithm outperforms the DARA and DCRMF algorithms, it is slightly inferior to the RIM algorithm in terms of coverage loss rate. However, the RIM algorithm necessitates the relocation of nearly 10 times more nodes than does the DWCR algorithm, especially in dense environments. Furthermore, the DWCR algorithm significantly outperforms the RIM algorithm in terms of total moving distance and total messages sent. Therefore, the DWCR algorithm still outperforms the RIM algorithm in terms of overall performance.

The DWCR algorithm combines active and passive methods to recover network connectivity after a single node failure in a WSAN. The DWCR backup node selection procedure is active, while the node relocation procedure is passive. Therefore, the method proposed in this paper effectively minimizes the total moving distance, number of relocated nodes, total messages sent, and coverage loss rate in the network recovery process.

In this section, we first analyze the network recovery process after a single node failure. We subsequently analyze whether the number of critical nodes changes during the recovery process. In addition, we analyze the communication overhead and computational complexity associated with the aforementioned process. Our theorems and their corresponding proofs are as follows.

Theorem 1

The DWCR algorithm can restore network connectivity after a single node failure.

Proof The failure of a noncritical node does not disrupt network connectivity, and other neighboring nodes continue to connect even if the failed node leaves the network. The DWCR algorithm identifies critical nodes during initialization and selects backup nodes through a backup node selection procedure to determine the path of movement. When a critical node fails, its backup node can move within the range of all the critical node’s one-hop neighbors to reconnect the network. During the node relocation procedure, the backup node reconnects its neighbors until all the neighbors are connected. To ensure that the DWCR algorithm is terminated within a limited number of steps, each backup node can only move once during the recovery process, and critical nodes will not be selected as backup nodes for each other.

Theorem 2

The total number of critical nodes does not increase after the network recovery process.

Proof During the DWCR algorithm’s execution, the selection of backup nodes ensures that the total number of critical nodes does not increase. Similarly, the degree of each node does not decrease after network recovery. The main reason for this is that the backup node moves and reconnects all its neighbor nodes. In Fig. 10(a), when node A5, a critical node, fails, node A3, which is the designated backup node of node A5, can directly move into the communication range of nodes A4 and A6 to restore network connectivity without moving to the location of the failed node. As indicated in Fig. 5(b), after the recovery process, the number of unmoved critical nodes does not change; neither nodes A4, A6, or A7 nor the relocated noncritical nodes become critical nodes. Furthermore, the total number of critical nodes may even decrease, as illustrated in Fig. 6. If node A7 fails, node A8 does not become a critical node after moving to a position close to the critical nodes.

Theorem 3

The maximum distance that a node moves during DWCR is the communication range Rc.

Proof During DWCR, one of the neighbors of the failed node is selected as a backup node, and it moves to reconnect the neighboring nodes of the failed node. In the worst-case scenario, the backup node must move to the location of the original faulty node, and the DCR [17] relocation scheme involves moving to the location of the original faulty node. Accordingly, the maximum distance that a node moves in the DCR is the communication range Rc. For example, in Fig. 11, node A4 is malfunctioning. Node A5 moves to A5′ to connect A3, and ${d}_{A5,A5{\prime }}$ < ${d}_{A5,A4}$ < Rc. Because node A5 moves to A5′, the original node A5 will lose connectivity with its neighbor nodes A6 and A7. Therefore, before moving to A5′, A5 will select a node from its one-hop neighbors {A6, A7} as a backup node. Because node A6 is a general node, it is selected as a backup node and moves to the position of A6′. Then, the distance is ${d}_{A6,A6{\prime }}$ < ${d}_{A6,A5}$ < Rc.

Theorem 4

The time complexity of the backup node selection process and movement path calculations is O(n ³ ), where n is the number of one-hop neighbors of the faulty node.

Proof The position of the backup node after node movement and network recovery is completed must be within the communication range of each neighbor node of ${N}_{i}$. Therefore, during the recovery process, the nearest intersection between the backup node and each neighbor of the faulty node must first be calculated; the time complexity of this calculation is O(n²). Once the overlapping range between neighbor nodes is determined, it is used to calculate the nearest distance to move past. The time complexity of these calculations is O(n²); therefore, the time complexity of the movement of each backup node is O(n² + n²). In addition, the time complexity of selecting a backup node must be taken into account. The time complexity of the process of selecting a backup node and calculating its movement path is O(n³).

Theorem 5

The total “message sent” complexity of the DWCR algorithm is O(N), where N is the number of actors.

Proof The backup node selection process is executed before a node fails to construct and maintain a one-hop neighbor table for each node. Until a node fails, it will only send messages to the backup node about its movement. In the worst-case scenario, N − 2 nodes move and only send messages to the backup node; therefore, the total “messages sent” complexity of the DWCR algorithm is O(N).

Because of harsh environmental conditions and limited power supplies, network disconnection and partition due to node failure may occur in a WSAN. However, previously developed network recovery algorithms still have room for improvement in terms of the total moving distance, the number of relocated nodes, the total messages sent, and the coverage loss rate. Therefore, in this paper, we propose a DWCR algorithm that not only selects backup nodes for critical nodes by dynamically adjusting the weight of the distance and degree factors but also restores the network structure with minimal costs. The performance of the DWCR algorithm was assessed through extensive simulations and compared with the performance of the RIM, DARA, and DCRMF algorithms. According to the experimental results, the performance of the proposed DWCR algorithm is not negatively affected by the number of nodes in sparse or dense networks, especially relative to that of recovery algorithms lacking a mechanism for distinguishing between critical and non-critical nodes. The DWCR algorithm outperforms other algorithms in terms of total moving distance, the number of relocated nodes, and total messages sent. Although the DWCR algorithm outperforms the DARA and DCRMF algorithms, it is slightly inferior to the RIM algorithm in terms of coverage loss rate. However, the RIM algorithm may result in an excessive number of relocated nodes and may produce results inferior to those obtained using the DWCR algorithm in terms of total moving distance, number of relocated nodes, and total messages sent. Therefore, the DWCR algorithm is still far superior to the RIM algorithm in terms of overall performance.

This study did not account for the use of electricity during backup node selection, and the backup node may run out of power as it moves. Therefore, in the future, researchers must improve upon the DWCR algorithm by accounting for the power factor to prolong the lifetime of relocated nodes and maintain the stability of the WSAN.

Ethical Approval

Not applicable.

Competing interests

The authors declare that they have no known competing fnancial interests or personal

relationships that could have appeared to infuence the work reported in this paper.

Authors' contributions

Mao-Lun Chiang: conceived of the presented idea, and verified the analytical methods. Hui-Ching Hsieh: conceived the presented idea, verified the analytical methods and wrote the manuscript. Tzu-Ling Lin: verified the analytical methods. Tsui-Ping Chang: carried out the experiment. Hong-Wei Chen: carried out the experiment.

Funding

Not applicable

Availability of data and materials

Not applicable.

S. Cheng, Z. Cai, J. Li, and X Fang, “Drawing dominant dataset from big sensory data in wireless sensor networks,” 2015 IEEE Conference on Computer Communications (INFOCOM), August 2015, pp. 531–539.
Z. Cai, G. Lin, and G. Xue, “Improved approximation algorithms for the capacitated multicast routing problem,” International Computing and Combinatorics Conference, Springer 2005, pp. 136-145.
Z. Cai, R. Goebel, and G. Lin, “Size-constrained tree partitioning: approximating the multicast k-tree routing problem,” Theoretical Computer Science, January 2011, Vol. 412, No. 3, pp. 240-245.
Z. He, Z. Cai, S. Cheng, and X. Wang, “Approximate aggregation for tracking quantiles and range countings in wireless sensor networks,” Theoretical Computer Science, November 2015, Vol. 607, No. 3, pp. 381-39.
P. P. Rawat, K.D. Singh, H. Chaouchi, and J.M. Bonnin, “Wireless sensor networks: a survey on recent developments and potential synergies,” The Journal of supercomputing, October 2013, Vol. 68, pp. 1-48.
S. Cheng, Z. Cai, and J. Li, “Curve query processing in wireless sensor networks,” IEEE Transactions on Vehicular Technology, November 2014, Vol. 64, No. 11, pp. 5198–5209.
A. Malaver, N. Motta, P. Corke, and F. Gonzalez, “Development and integration of a solar powered unmanned aerial vehicle and a wireless sensor network to monitor greenhouse gases,” Sensors, February 2015, Vol. 15, No. 2, pp. 4072–4096.
F. Senturk, K. Akkaya, and S. Janansefat, “Towards realistic connectivity restoration in partitioned mobile sensor networks,” International Journal of Communication Systems, June 2014, Vol. 29, No. 2, pp. 230-250.
I. F. Akyildiz, and I. H. Kasimoglu, “Wireless sensor and Actor networks: Research challenges”, Ad hoc networks, October 2004, Vol. 2, No. 4, pp. 351-367.
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless sensor networks: a survey”, Computer networks, March 2002, Vol. 38, No. 4, pp. 393-422.
F. Xia, “QoS challenges and opportunities in wireless sensor/actuator networks,” Sensors, February 2008, Vol. 8, No. 2, pp. 1099-1110.
M. Imran, M. A. Alnuem, M. S. Fayed, and A. Alamri, “Localized algorithm for segregation of critical/non-critical nodes in mobile ad hoc and sensor networks,” Procedia Computer Science, June 2013, Vol. 19, pp. 1167-1172.
M. Imran, M. Younis, and A. M. Said, “Localized motion-based connectivity restoration algorithms for wireless sensor and actor networks,” Journal of Network and Computer Applications, March 2012, Vol. 35, No. 2, pp. 844-856.
X. Dai, F. Qin, Z. Gao, K. Pan, and K. Busawon, “Model-based on-line sensor fault detection in Wireless Sensor Actuator Networks,” 2015 IEEE 13th International Conference on Industrial Informatics (INDIN), July 2015, pp. 556-561.
I. Senturk, S. Yilmaz, and K. Akkaya, “Connectivity restoration in delay–tolerant sensor networks using game theory,” International Journal of Ad Hoc and Ubiquitous Computing, November 2012, Vol. 11, No. 2-3, pp. 109-124.
M. Younis, I. F. Senturk, K. Akkaya, S. Lee, and F. Senel, “Topology management techniques for tolerating node failures in wireless sensor networks: A survey,” Computer Networks, January 2014, Vol. 58, pp. 254-283.
O. Dagdeviren, and V. K. Akram, “An energy-efficient distributed cut vertex detection algorithm for wireless sensor networks,” The Computer Journal, December 2014, Vol. 57, No. 12, pp. 1852-1869.
A. Berger, A. Grigoriev, and R. van der Zwaan, “Complexity and approximability of the k‐way vertex cut,” Networks, March 2014, Vol. 63, No. 2, pp. 170-178.
M. Imran, M. Younis, N. Haider, and M.A. Alnuem, “Resource efficient connectivity restoration algorithm for mobile sensor/Actor networks,” EURASIP Journal on Wireless Communications and Networking, November 2012, pp. 1-16.
A. Abbasi, M. F. Younis, and U. A. Baroudi, “Recovering from a node failure in wireless sensor-actor networks with minimal topology changes,” IEEE Transactions on vehicular technology, August 2012, Vol. 62, No. 1, pp. 256-271.
A. A. Abbasi, M. Younis, and K. Akkaya, “Movement-Assisted Connectivity Restoration in Wireless Sensor and Actor Networks,” IEEE Transactions on parallel and distributed systems, November 2008, Vol. 20, No. 9, pp.1366-1379.
A. Alfadhly, U. Baroudi, and M. Younis, “Least distance movement recovery approach for large scale wireless sensor and actor networks,” In 2011 7th International Wireless Communications and Mobile Computing Conference, July 2011, pp. 2058-2063.
K. Akkaya, F. Senel, A. Thimmapuram, and S. Uludag, “Distributed recovery from network partitioning in movable sensor/actor networks via controlled mobility,” IEEE Transactions on Computers, July 2009, Vol. 59 No. 2, pp. 258-271.
M. K. Saeed, M. ul Hassan, K. Mahmood, A. M. Shah, and J. Khan, “Efficient Solution for Connectivity Restoration (ESCR) in Wireless Sensor and Actor-Networks. Wireless Personal Communications, November 2020, Vol. 117, pp. 2115-2134.
M. Younis, S. Lee, and A. A. Abbasi, “A localized algorithm for restoring internode connectivity in networks of moveable sensors,” IEEE Transactions on Computers, August 2010, Vol. 59, No. 12, pp. 1669-1682.
Y. Zhang, Z. Zhang, and B. Zhang, “A novel hybrid optimization scheme on connectivity restoration processes for large scale industrial wireless sensor and actuator networks,” Processes, December 2019, Vol. 7, No. 12: 939.
A. Zear, and V. Ranga, “Distributed partition detection and recovery using UAV in wireless sensor and actor networks,” Kuwait Journal of Science, October 2021, Vol. 48, No. 4.
M. Younis, S. Lee, S. Gupta, and K. Fisher, “A Localized Self-Healing Algorithm for Networks of Moveable Sensor Nodes,” IEEE GLOBECOM 2008-2008 IEEE global telecommunications conference, December 2008, pp. 1-5.
N. Ajmi, A. Helali, P. Lorenz, and R. Mghaieth, “MWCSGA—multi weight chicken swarm based genetic algorithm for energy efficient clustered wireless sensor network,” Sensors, January 2021, Vol. 21, No. 3.
K. Vaidya, and M. Younis, “Efficient failure restoration in Wireless Sensor Networks through active, spare designation,” 2010 6th IEEE International Conference on Distributed Computing in Sensor Systems Workshops (DCOSSW), 2010, pp. 1-6.
K. Yan, G. Luo, L. Tian, Q. Jia, and C. Peng, “Hybrid connectivity restoration in wireless sensor and Actor networks,” EURASIP Journal on Wireless Communications and Networking, August 2017, pp. 1-16.
Y. Zhang, J. Wang, and G. Hao, “An Autonomous Connectivity Restoration Algorithm Based on Finite State Machine for Wireless Sensor-Actor Networks,” Sensors, January 2018, Vol. 18, No. 1.
G. A. Mutiara, O. Mohd, N. Suryana, and A. N. Pee, “Weights-Based Energy-Efficient Wireless Sensor Network Protocol with Firefly Synchronization for Illegal Logging,” International Journal of Intelligent Engineering and Systems, March 2021, Vol. 14, No. 3, pp. 374-387.
S. Liu, D. Liu, Y. Feng, and Y. Ji, “Distributed Connectivity Restoration Algorithm with Optimal Repair Path in Wireless Sensor and Actor Networks,” Journal of Sensors, April 2022, Vol. 2022.
Y. Zeng, X. Li, and Z. Chen, “Fault-Tolerant Algorithms for Connectivity Restoration in Wireless Sensor Networks,” Sensors, December 2015, Vol. 16, No. 1.

Figure 5 is not included with this version

No competing interests reported.

Download PDF

Editorial decision: Major revision
20 May, 2023
Reviews received at journal
30 Apr, 2023
Reviewers agreed at journal
29 Apr, 2023
Reviewers invited by journal
29 Apr, 2023
Editor assigned by journal
10 Feb, 2023
Submission checks completed at journal
10 Feb, 2023
First submitted to journal
09 Feb, 2023

You are reading this latest preprint version

\(ID\)	Unique ID for each node.
\(i\)	Current critical node.
\(j\)	Neighbor nodes of critical node \(i\).
\({N}_{i}\)	Set of neighbors of critical node \(i\).
\({F}_{i}\)	Failed critical node.
\({a}_{1}\)	When \({N}_{i}\) contains general nodes, the distance weighting factor in formula (1) is used.
\({a}_{2}\)	When \({N}_{i}\) contains general nodes, the branch degree weighting factor in formula (1) is used.
\({W}_{a}\)	Weights calculated using formula (1).
\({b}_{1}\)	When \({N}_{i}\) does not contain general nodes, the distance weighting factor in formula (2) is used.
\({b}_{2}\)	When \({N}_{i}\) does not contain general nodes, the branch degree weighting factor in formula (2) is used.
\({W}_{b}\)	Weights calculated using formula (2).
\({d}_{ij}\)	Distance between critical node \(i\) and its one-hop neighbor \(j\).
\({R}_{c}\)	Actor’s communication range.
NEIGH_TABLE	The neighbor table which records information on the node’s one-hop neighbor (\(ID\), \(POSITION\)).

Dynamic Weight-Based Connectivity Recovery in Wireless Sensor and Actor Networks

Status:

Version 1

Abstract

Figures

1. Introduction

2. Relevant Works

3. Dwcr Algorithm

3.1 Parameter Settings and Definitions

3.2 System Model

3.3 Backup Node Selection Procedure

3.4 Node Relocation Procedure

4. Simulation Experiments

4.1 Simulation Environment

4.2 Simulation Results

4.2.1 Total Moving Distance

4.2.2 Total Messages Sent

4.2.3 Number of Relocated Nodes

4.2.3 Coverage Loss Rate

5. Algorithm Analysis

6. Conclusion

Declarations

References

Figure

Additional Declarations

Status:

Version 1