# Multirobot Federating Method for Disjoint Segments in Wireless Sensor Network Based on Optimal Anchor Point and Local Priority

Authors: Rong Jing; MingWang Chen; FengDa Zhao; XianShan Li; LingFu Kong
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In order to solve the connectivity problem between multiple islands in the wireless sensor network (WSN) due to large-scale damage, a multirobot WSN island alliance method based on the local priority of the optimal anchor point is proposed. This method introduces the idea of priority restoration of local connectivity in weighted networks and uses the optimal anchor point election mechanism to construct connectivity paths. Compared with existing methods, LPRMA’s local preferential recovery thinking makes WSN island alliances more adaptable. And LPRMA’s trunk deployment strategy based on optimal anchor can significantly reduce the path length and the number of trunk deployments for connected recovery. Finally, through the comparison and simulation experiments with the existing methods, the results show that the proposed method can effectively improve the efficiency of WSN island alliance while satisfying the constraints of lower network delay and higher robustness.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) is a multihop self-organizing network system formed by wireless communication by deploying numerous microsensor nodes in its monitoring area. It integrates distributed information processing technology, sensor technology, embedded computing technology, and communication technology and can monitor, perceive, and collect information about various environments or target objects in the network monitoring area in real-time. It has been widely used in military surveillance, fire detection, target tracking, and wireless security [1] and has become an integral part of the Internet of Things.As an important measure of the quality of the WSN service, connectivity determines whether the information collected by sensor nodes can be transmitted to the base station (Base Station, BS for short) in a timely and accurate manner, which is the premise of the WSN application [2]. However, when the WSN suffers large-scale damage, it is likely to cause many wide-bound coverage holes inside the WSN, forming multiple subwireless sensor networks that are not connected, thus destroying the connectivity of the WSN. This phenomenon is called the islanding effect, as shown in Figure 1. Therefore, it is of great significance to restore the connectivity of WSN by aligning various network islands to restore the WSN’s recovery function.Figure 1
WSN damage situation.For the connectivity repair problem of the islanding effect caused by large-scale coverage holes in WSN, the proposed solutions can be divided into two categories: one is to reestablish the connection between islands by relocating the remaining surviving nodes from each island to reconstruct network connectivity [3–6]. Joshi and Younis proposed an autonomous repair approach (AuR) that relocates to an assumed preknown regional center [3]. In AuR, the recovery process is guided by extending the neighbors of the faulty node towards the faulty node, so that the topology within the island is extended. Lee and Younis uses a distributed algorithm to optimize the layout of the relay nodes using minimum Steiner trees (DORMS) [4], selecting a suitable node from the existing nodes on each island as the relay node, and then moving the relay node from the island to the deployment center. When the communication range of each relay node overlaps with each other, the network connection can be restored. However, when the network is destroyed on a large scale and forms multiple islands, such methods cannot effectively repair network connectivity because the resources and capabilities of the sensor nodes themselves are limited, which makes them unable to move for long distances. Therefore, another method is to restore connectivity between islands by deploying additional relay nodes, at which point the connection restoration problem becomes to determine the minimum number of relay nodes and their locations to form data routing between each pair of islands. The repaired network topology formed by such methods has strong scalability and is very suitable for island alliances in self-organizing networks. Senel and Younis [7] proposed a heuristic algorithm based on a minimum spanning tree (MST). The algorithm performs the filling by moving the relay nodes along the edge of the island or finding a point within the island. Han et al. proposed to deploy additional relay nodes between each pair of target nodes and construct multiple disjoint paths to restore network connectivity [8]. A connectivity restoration algorithm with the ability to handle single-node failures is studied by reference [9], which achieves network connectivity by building a backbone polygon around the center of the damaged area and deploying relay nodes to connect each outer island to the backbone polygon. In [10], Lee et al., a two-vertex recovery strategy is constructed between each pair of islands or a single island to reduce the number of deployed relay nodes and improve the efficiency of the construction of the network topology according to the degree of the average node. Liu et al. proposed a path planning strategy for mobile data collection [11], called double approximation of anchor points (DAAP), which aims to achieve full connectivity of islands in wireless sensor networks with shorter paths and deploying the fewest relay nodes.Although the literature [7–15] all use the optimal deployment path to deploy additional relays to damaged areas under certain constraints to restore network connectivity, they all ignore the impact of secondary disasters on the alliance of WSN islands, making the WSN network less robust. In addition, most of the existing island alliances adopt incremental alliances [16–19], which not only reduces the efficiency of island alliances but also seriously affects the processing progress of the islands themselves and greatly increases the network delay after island alliances.Given the shortcomings of the above-mentioned island alliance method, we propose a multirobot WSN island alliance method based on the optimal anchor point local priority. This method starts with path optimization, network robustness, and network delay. Appropriate anchor points and planning the optimal deployment path of relay nodes deploy additional relay nodes in a multirobot cooperative manner to restore the connectivity between islands. The main contributions of this paper are summarized as follows.(1)
In order to improve the ability to deal with secondary disasters after the network connection is restored, the multianchor point problem is proposed, that is, different optimal anchor points are selected for different islands. A formulaic description of the problem is given by using an integer linear programming model combined with multiple constraints(2)
To improve the efficiency and reduce network latency after disaster recovery. Based on the optimization problem of multianchor points, the local priority recovery strategy is designed(3)
From the three evaluation indexes of relay deployment number, deployment time, and a number of surviving nodes in the network after a secondary disaster and network delay, comparison simulation and practical experiments are carried out with the existing WSN island alliance method to verify the effectiveness of the proposed methodThis approach is characterized by(1)
Using multianchor connections, that is, selecting multiple connection points in an island to connect to other islands. When a connection point fails in an island, the entire island does not lose its connection to other islands. To ensure that the entire network is still in a connected state, which greatly enhances the robustness of the network(2)
The priority recovery strategy for the local area is beneficial to processing transactions within the network after the network is damaged in a large area. After the local area network is restored, some transactions belonging to the current local area network are processed, and the remaining global transactions are processed after the entire network is restored, which reduces the probability of network transaction processing conflicts and effectively improves the processing efficiency of network transactions, and reduces network latency(3)
The total length of the recovery path is minimized under the condition that the network is fully connected, which greatly reduces the number of relay nodes deployed. The deployment time during recovery is less than that of the existing solutionThe rest of this paper is organized as follows. Section2 describes the model of the system and provides a formulaic description of the problem to be solved. Section 3 introduces the proposed method in details. The simulation results are shown in Section 4 to verify the effectiveness of the proposed algorithm. Section 5 deals with the conclusion.


## 2. System Model and Problem Formulation Description

### 2.1. Hypothesis of System Model

#### 2.1.1. Network Model

The WSN consists of sensor nodes, all of which are randomly distributed within the square region. The WSN MAC layer adopts the IEEE 802.15.4 standard and the network layer adopts the TEDG-WMR data collection protocol. WSN is abstracted as a connected graph, which is the set of all nodes in the perceptual region and is the set of edges between connected nodes. In addition, nodes have the same maximum perceptual radius and communication radius, and it is possible to know their position by positioning algorithm.


#### 2.1.2. Robotic Model

There are roboticm in the area and the number is more than the number of islands. The communication radius and perception radii are rc and rs, respectively, and the robotics can be assigned to the corresponding anchor point by means of anchor search. It ignores acceleration and braking time, i.e., constant speed v and the same efficiency during deployment. Furthermore, we assume that the trunks deployed by the robot are common sensor nodes and their load and communication capabilities are sufficient for the LPRMA solution.


#### 2.1.3. Island Model

The network is divided intoNN>3 islands, denoted. Each island has a different number of static sensor nodes with different initial energy E0 and the same maximum transmission power and maximum transmission range. In addition, property information is known for all surviving nodes themselves. Anchors node in islands can collect data that sense other nodes in islands. Each anchor has enough storage space to cache collected data. When connecting with other island anchors, the data stored in the anchor can be exchanged by employing relay nodes.


### 2.2. Problem Formulas

As a basis for analyzing and solving the LPRMA problem, the LPRMA formulaic description plays an important role. Based on the hypothesis of Section2.1 system model, we give the relevant symbols and definitions (see Table 1). The goal of LPRMA is to divide all isolated islands into local networks and select several suitable anchors from the isolated islands. The network is fully connected by constructing a multiclosed loop path between all anchor points. Establish a formulaic description of the LPRMA problem by following the principles of multianchor connection and local preferential recovery.Table 1
Symbols and definitions.
SymbolDefinitionδIsland collectionηCollection of island’s nodesψCollection of island centersmNumber of nodes in the islandNNumber of islandsGNumber of anchors in each islandCTpathPath cost between islandsCTenRelay deployment energy costKNumber of node groupsCλiCollection of nodes in a groupuiIsland centroids collectionΩGlobal network zoneΛNode degreeTNetwork affairsLLocal network collectionδEXIOutreach islandsRCRelay node communication radiusZDelayed evaluation functionThe core of LPRMA lies in the choice of the most suitable anchor node in the island. In addition, both local and global network connections follow the multianchor approach, so that the number of anchors on each island is not less than two. The determination of the optimal anchor point of the island is to model all the islands in the local area as a graphG, and the nodes in the island are represented by the vertex ηi in G. If the two nodes ηi and ηj in the island are in a connected state, then there is an edge between vi and vj. Let xji be a binary variable, if the node j is located at the position i, it is represented by the xji=1, xji=0. When this condition does not hold, it means that node j is selected as the most suitable anchor point. The choice of the most suitable anchor point is determined by the cost CTpath of the path between the current island node and the other island center. Moreover, in the process of finding the most suitable anchor AP, we also consider the energy cost Ue of the multirobot deployment relay node under the condition that the robot has fixed consumption CTen=UeqUli+UeqUlb. Thus, the connectivity restoration cost of the LPRMA problem is obtained CTcon:Objective function(1)CTcon=argmin∑i∈G∑j∈Gxjidji2r−ω+UeqUli+qUlb.Constraints(2)∑i∈Nxji=1,∀j∈N,(3)∑j∈N,j∉Ψxji=1,∀i∈N,(4)λaλpE≥∑i=1mλai∑i=1mλpi⋅∑i=1mEim,(5)xjidji≤dΨt,Ψk,∀i,j∈M,∀t,k∈N,(6)δv>2,qUli=δv,v=Lrt,Lrd,Llt,Lld,li∈v,(7)0<δv<2,qUli=δv−1,(8)qUlb=v,(9)∃pathS,S=riort,s1li,⋯,sjliorg,s1lb,⋯,sclb,∀i∈1,⋯,qUliorqUlb,∀t∈δli,sj∈Rli,qUli,∀g∈δlb,sc∈Rlb,(10)distsi,si+1≤Rc,∀si∈S,i≤RliorRlb.In the above LPRMA optimization problem (1)–(10)
(i)
Constraints (2) and(3) ensures that the i position is not used by multiple nodes at the same time and that only one anchor is determined at the same time(ii)
Constraints (4) and (5) ensure that the node selected as the anchor point has relatively good stability, and the process of finding the anchor point is only carried out in the range where the two isolated islands are close to each other, avoiding the need for two isolated islands computation of nodes in the range far away from each other. Among them(a)
λa is the degree of node in the island before network damage(b)
λp is the degree of the node in the island after the network is damaged(c)
E is the energy state of the node(d)
dψt,ψk is the distance between the centers of the two islands(iii)
Constraints (6)–(8) specify the number of robots to be used in the connection recovery process. Of which(a)
δv is the number of islands within the local area network(b)
v is the number of local area networks(c)
qUli is the number of connected recovery robots within the local area network(d)
qUlb is the number of connectivity recovery robots between local networks(iv)
Constraints (9) and (10) ensure that there is at least one valid routing path between every two islands in the local network or the global network. Among them(a)
δli is a collection of islands in the local area network(b)
δlb is a collection of outreach islands between local networks(c)
Rli is the set of relay nodes deployed in the local area network(d)
Rlb is the set of relay nodes deployed between local area networks(e)
Rli is the number of relay nodes deployed in the local area network(f)
Rlb is the number of relay nodes deployed between local area networks


## 2.1. Hypothesis of System Model

### 2.1.1. Network Model

The WSN consists of sensor nodes, all of which are randomly distributed within the square region. The WSN MAC layer adopts the IEEE 802.15.4 standard and the network layer adopts the TEDG-WMR data collection protocol. WSN is abstracted as a connected graph, which is the set of all nodes in the perceptual region and is the set of edges between connected nodes. In addition, nodes have the same maximum perceptual radius and communication radius, and it is possible to know their position by positioning algorithm.


### 2.1.2. Robotic Model

There are roboticm in the area and the number is more than the number of islands. The communication radius and perception radii are rc and rs, respectively, and the robotics can be assigned to the corresponding anchor point by means of anchor search. It ignores acceleration and braking time, i.e., constant speed v and the same efficiency during deployment. Furthermore, we assume that the trunks deployed by the robot are common sensor nodes and their load and communication capabilities are sufficient for the LPRMA solution.


### 2.1.3. Island Model

The network is divided intoNN>3 islands, denoted. Each island has a different number of static sensor nodes with different initial energy E0 and the same maximum transmission power and maximum transmission range. In addition, property information is known for all surviving nodes themselves. Anchors node in islands can collect data that sense other nodes in islands. Each anchor has enough storage space to cache collected data. When connecting with other island anchors, the data stored in the anchor can be exchanged by employing relay nodes.


## 2.1.1. Network Model

The WSN consists of sensor nodes, all of which are randomly distributed within the square region. The WSN MAC layer adopts the IEEE 802.15.4 standard and the network layer adopts the TEDG-WMR data collection protocol. WSN is abstracted as a connected graph, which is the set of all nodes in the perceptual region and is the set of edges between connected nodes. In addition, nodes have the same maximum perceptual radius and communication radius, and it is possible to know their position by positioning algorithm.


## 2.1.2. Robotic Model

There are roboticm in the area and the number is more than the number of islands. The communication radius and perception radii are rc and rs, respectively, and the robotics can be assigned to the corresponding anchor point by means of anchor search. It ignores acceleration and braking time, i.e., constant speed v and the same efficiency during deployment. Furthermore, we assume that the trunks deployed by the robot are common sensor nodes and their load and communication capabilities are sufficient for the LPRMA solution.


## 2.1.3. Island Model

The network is divided intoNN>3 islands, denoted. Each island has a different number of static sensor nodes with different initial energy E0 and the same maximum transmission power and maximum transmission range. In addition, property information is known for all surviving nodes themselves. Anchors node in islands can collect data that sense other nodes in islands. Each anchor has enough storage space to cache collected data. When connecting with other island anchors, the data stored in the anchor can be exchanged by employing relay nodes.


## 2.2. Problem Formulas

As a basis for analyzing and solving the LPRMA problem, the LPRMA formulaic description plays an important role. Based on the hypothesis of Section2.1 system model, we give the relevant symbols and definitions (see Table 1). The goal of LPRMA is to divide all isolated islands into local networks and select several suitable anchors from the isolated islands. The network is fully connected by constructing a multiclosed loop path between all anchor points. Establish a formulaic description of the LPRMA problem by following the principles of multianchor connection and local preferential recovery.Table 1
Symbols and definitions.
SymbolDefinitionδIsland collectionηCollection of island’s nodesψCollection of island centersmNumber of nodes in the islandNNumber of islandsGNumber of anchors in each islandCTpathPath cost between islandsCTenRelay deployment energy costKNumber of node groupsCλiCollection of nodes in a groupuiIsland centroids collectionΩGlobal network zoneΛNode degreeTNetwork affairsLLocal network collectionδEXIOutreach islandsRCRelay node communication radiusZDelayed evaluation functionThe core of LPRMA lies in the choice of the most suitable anchor node in the island. In addition, both local and global network connections follow the multianchor approach, so that the number of anchors on each island is not less than two. The determination of the optimal anchor point of the island is to model all the islands in the local area as a graphG, and the nodes in the island are represented by the vertex ηi in G. If the two nodes ηi and ηj in the island are in a connected state, then there is an edge between vi and vj. Let xji be a binary variable, if the node j is located at the position i, it is represented by the xji=1, xji=0. When this condition does not hold, it means that node j is selected as the most suitable anchor point. The choice of the most suitable anchor point is determined by the cost CTpath of the path between the current island node and the other island center. Moreover, in the process of finding the most suitable anchor AP, we also consider the energy cost Ue of the multirobot deployment relay node under the condition that the robot has fixed consumption CTen=UeqUli+UeqUlb. Thus, the connectivity restoration cost of the LPRMA problem is obtained CTcon:Objective function(1)CTcon=argmin∑i∈G∑j∈Gxjidji2r−ω+UeqUli+qUlb.Constraints(2)∑i∈Nxji=1,∀j∈N,(3)∑j∈N,j∉Ψxji=1,∀i∈N,(4)λaλpE≥∑i=1mλai∑i=1mλpi⋅∑i=1mEim,(5)xjidji≤dΨt,Ψk,∀i,j∈M,∀t,k∈N,(6)δv>2,qUli=δv,v=Lrt,Lrd,Llt,Lld,li∈v,(7)0<δv<2,qUli=δv−1,(8)qUlb=v,(9)∃pathS,S=riort,s1li,⋯,sjliorg,s1lb,⋯,sclb,∀i∈1,⋯,qUliorqUlb,∀t∈δli,sj∈Rli,qUli,∀g∈δlb,sc∈Rlb,(10)distsi,si+1≤Rc,∀si∈S,i≤RliorRlb.In the above LPRMA optimization problem (1)–(10)
(i)
Constraints (2) and(3) ensures that the i position is not used by multiple nodes at the same time and that only one anchor is determined at the same time(ii)
Constraints (4) and (5) ensure that the node selected as the anchor point has relatively good stability, and the process of finding the anchor point is only carried out in the range where the two isolated islands are close to each other, avoiding the need for two isolated islands computation of nodes in the range far away from each other. Among them(a)
λa is the degree of node in the island before network damage(b)
λp is the degree of the node in the island after the network is damaged(c)
E is the energy state of the node(d)
dψt,ψk is the distance between the centers of the two islands(iii)
Constraints (6)–(8) specify the number of robots to be used in the connection recovery process. Of which(a)
δv is the number of islands within the local area network(b)
v is the number of local area networks(c)
qUli is the number of connected recovery robots within the local area network(d)
qUlb is the number of connectivity recovery robots between local networks(iv)
Constraints (9) and (10) ensure that there is at least one valid routing path between every two islands in the local network or the global network. Among them(a)
δli is a collection of islands in the local area network(b)
δlb is a collection of outreach islands between local networks(c)
Rli is the set of relay nodes deployed in the local area network(d)
Rlb is the set of relay nodes deployed between local area networks(e)
Rli is the number of relay nodes deployed in the local area network(f)
Rlb is the number of relay nodes deployed between local area networks


## 3. LPRMA Solution

During the deployment of the trunk node, a path is formed between the most suitable anchors visited by the robot. If the path is too long, it will increase not only energy consumption but also the number of trunk nodes deployed. Therefore, it is the main goal of LPRMA to select the most suitable anchor and plan the shorter trunk node deployment path.


### 3.1. Theoretical Model Solving

Nodes that satisfy constraints (2)–(5) in a collection of island nodes serve as candidate anchors to connect with other islands. The process of finding an island candidate anchor is summarized as an integer linear programming problem and set to M.For the solution of problemM, M is first relaxed, that is, the 0-1 value of xji is abandoned, to obtain the relaxation problem Q. Record the optimal solution of Q and the obtained minimum value, if the obtained solution is an integer solution, then the solution is the optimal solution of the candidate anchor point. Otherwise, the obtained candidate anchor point solution is used as the initial lower bound of the optimal solution of the problem, and the initial upper bound is set as +∞.
(11)MMin∑i∈G∑j∈Gxjidji∑i∈Nxji=1,∀j∈N∑j∈N,j∉Ψxji=1,∀i∈NλaλpE≥∑i=1mλai∑i=1mλpi∗∑i=1mEim,QMin∑i∈G∑j∈Gxjidji∑i∈Nxji=1,∀j∈N∑j∈N,j∉Ψxji=1,∀i∈NλaλpE≥∑i=1mλai∑i=1mλpi∗∑i=1mEimxji>0xji>xji+1.When the optimal solution of the relaxation problemQ of candidate anchor points is not an integer solution, the original integer programming problem M is divided into the following two subproblems.
(12)M1Min∑i∈G∑j∈Gxjidji,∑i∈Nxji=1,∀j∈N,∑j∈N,j∉Ψxji=1,∀i∈N,λaλpE≥∑i=1mλai∑i=1mλpi⋅∑i=1mEim,xji>0,xji<xji,M2Min∑i∈G∑j∈Gxjidji,∑i∈Nxji=1,∀j∈N,∑j∈N,j∉Ψxji=1,∀i∈N,λaλpE≥∑i=1mλai∑i=1mλpi∗∑i=1mEim,xji>0,xji>xji+1.In any subproblem, select one of the variables that do not satisfy the integer requirement of the candidate anchor point for processing, divide a candidate anchor point subproblem into two subproblems subject to further constraints by adding a pair of mutually exclusive constraints, and force Variables that are not integers are further approximated to integer values, and the noninteger field between two integers is removed at a time to narrow the search area. Therefore, if the subproblem does not meet the integer requirements of candidate anchor points, it will continue to branch downward.By continuously branching and solving each subproblem, the upper and lower bounds will be continuously revised. The lower bound is usually determined by the minimum target distance value between the anchor point of the subproblem and the center of the corresponding island, while the upper bound is determined by the optimal candidate anchor that has been obtained to confirm.Search for iterations according to the above steps. In each search process, whenever the lower bound is modified, all subproblems that have not been solved should be checked and those subproblems whose objective function value is less than the new lower bound should be checked. To improve the calculation process, the solution of the candidate anchor point is based on the constraint condition (5), and the nodes in the island are first selected, but the constraint may have a very small probability that no integer solution of the candidate anchor point can be found. At this time, the constraint of constraint condition (5) should be ignored, and then the solution should be resolved. Otherwise, the integer solution obtained during the search is the optimal solution for the candidate anchor, and finally, based on constraints (6)–(10), the nodes corresponding to the optimal solution for the candidate anchor are selected to satisfy the objective function. The node of (formula (1)) is the island’s most suitable anchor AP. When the most suitable anchor point AP is determined in all isolated islands, the WSN connectivity is restored through the deployment of relay nodes between the one-to-one corresponding APs by the robot, following the principle of local preferential recovery.


### 3.2. Algorithm Implementation

In the process of restoring the connectivity of isolated islands, the LPRMA algorithm includes three stages, namely, the determination of the center of the isolated island, the restoration of connectivity within the local area network, and the restoration of connectivity between local networks. The specific implementation of the three phases is as follows:


#### 3.2.1. Determination of Island Center

The center of the island is a point that can represent the position of the island and is determined according to the positions of all nodes in the island. Due to the uncertainty of node distribution in the island, this paper firstly groups all nodesη=η1,η1⋯ηm in the island. Select k nodes from the node-set η as the initial k centroids μ=μ1,μ1⋯μk. Initialize the group C=C1,C1⋯Ck as Ct=∅,t=1,2⋯k.Calculate the node ηii=1,2⋯m and the similarity of each centroid μjj=1,2⋯k:
(13)distedxi,xj=∑u=1nxui,xuj2.In formula (13), distedxi,xj is the similarity between the node and the centroid, which is determined by the Euclidean distance between the node and the centroid. According to the similarity disted set of the node ηi, the ηi is divided into the group λi corresponding to the smallest disted, When all nodes are divided, the group is updated, and Cλi is the set of nodes in the group. The centroid Cjj=1,2⋯k is recalculated for all nodes in the updated group μi using the formula (15).
(14)Cλi=Cλi∪ηi,(15)μj=1Cj∑η∈Cjη.The iterative optimization of the centroid results is carried out continuously until allk centroids no longer change, then the final centroid set is output μij=1,2⋯k, which is calculated according to formula (16). Algorithm 1 is the pseudocode of the algorithm for determining the center of the island.
(16)ψ=1μi∑μ.Algorithm 1: Island Center Selection Algorithm.
Input  island selection δ,number of node groups kOutput  island center collection ψ1   μ ← null; C ← null; t =0;2   μ ← pick k nodes fromη;3   while ture do4    for i =1 to m5     for j =1 to k6     disted ← calculate the similarity between nodeηiAnd centroidμj;7      end for8     end for9    for i =1 to m10     find the ηi with the smallest similarity set of disted,And divide theηi into the corresponding group λi;11    end for12    Cλ ← Cλ∪{ηi};13    μ←recalculate the centroids of all nodes in Cλ;14    ifμnew==μbefore15     t++;16     if t==1017      break;18     end if19    end if20    end while21    according to the calculation of Cλ, the island center setψ is obtained;The number of executions of the statement in Algorithm1 is directly related to the variables m and k. The value of the variable m is determined according to the number of local area networks. In this paper, the number of local area networks is 4, and it can be known that the value range of the variable m is 1–4, and the size of the variable k is determined by the number of nodes in the island, and its value range is 1–n, then the summation formula can be used to obtain the maximum statement frequency fn of Algorithm 1.Taking the order of magnitude for fn, the time complexity of Algorithm 1 is On.(17)fn=∑i=1m∑i=1n1=4∑i=1n1=4n.


#### 3.2.2. Recovery of Intranet Connectivity

A local area network is a subnetwork formed by dividing the global network into equal parts according to the center of its area. It is much more difficult to solve the connectivity restoration problem of multiple isolated islands in the network than the existing problems in the connected network, and it is difficult to complete it in one stage. Therefore, LPRMA uses the idea of divide and conquer to group multiple isolated islands into a local area network. The global network connectivity restoration problem is simplified into multiple local network connectivity restoration problems. According to the minimum square areaΩ that can contain all the islands specified in this paper, it is easy to obtain the central coordinate ωωx,ωy of the area, and the local area is divided as follows:
(18)Lx>ωx,Ly>ωy⟶Lrt,Lx>ωx,Ly<ωy⟶Lrd,Lx<ωx,Ly>ωy⟶Llt,Lx<ωx,Ly<ωy⟶Lld,Lrt,Lrd,Llt,Lld∈Ω.All the islands are divided into the correspondingLrt, Lrd, Llt, and Lld local area networks through the area where the island center ψii=1,2⋯N obtained in the previous process is located.According to the geographical location factorGP and the functional area marker FZ, the priority sequence L=Lrt,Lrd,Llt,Lld of each local area network in the local area network set Lpre=Lrt1,Lrd2,Llt3,Lld4 is obtained, and on this basis, according to the priority of the local area network, the islands in the local area network are connected and restored in turn.In the process of restoring connectivity in the local area network, firstly find the anchor points in each isolated island corresponding to other isolated islands in the same local area network. It is worth noting that when a node has been marked as the most suitable anchor After the point is selected, the determined anchor points are not considered when selecting anchor points relative to other islands, thus ensuring the principle of LPRMA multianchor point connection. At this time, the number of selected anchor pointsAP in each island satisfy the following relationship:
(19)APnum≥1,NL≥2,L=Lrt,Llt,Lrd,Lld,APnum=0,NL=1.There is a unique mapping relationship between the determined anchor points of the isolated islands in the same local area network and other isolated island anchor points, and then according to the mapping relationship between the anchor points, relay nodes are deployed between the two anchor points, to achieve connectivity recovery between two different islands. By analogy, when all the island anchors in the local area network have been connected, the connection in the local area network can be restored.Based on the above, the pseudocode of the algorithm for determining the optimal anchor point is given as follows.Algorithm 2: Optimal Anchor Point Selection.
Input  the isolated island set δ and the isolated island center set ψ in the local area network LOutput  optimal anchor point,optimal path1   E ← initialize the energy state of the node;2   λ←calculate the node degree of the node according to the graph G;3   node suitability fit←0;4   for i =1 to t5    dis←calculate the distance between the center of theCurrent islandδtand the center of other islandsδe;6   for j =1 to m;7      dt←calculate the distance from each nodeηjIn the islandδtto all nodes in another island;8     if dt < dis9       cand←ηj;10     ηj suitability fit←fit + dt∗distance weight;11      fit←fit+λ proportion∗E∗life status weight12     end if13    end for14    anc←max(fit);15    ancList←δeis added to the set of optimal anchorPoints;16   end for17    connect the two corresponding anchor points inancList to get the optimal path;The number of executions of the statement in Algorithm2 is directly related to the number of islands t and the number of nodes in the island k. Since the number of islands and the number of nodes in the island are unpredictable in practice, the value ranges of the variables t and k are both 1–n, then the summation formula can be used to obtain the maximum statement frequency fn of Algorithm 2.Taking the order of magnitude for fn, the time complexity of Algorithm 2 is On2.
(20)fn=∑t=1n∑k=1n1=∑t=1nn=n2.


#### 3.2.3. Restore Connectivity between Local Areas

An external island is an island in a local area network that is used to establish connections with other local area networks. In order to restore connectivity between local networks, we must first determine theδEXIof the two local networks, and the identification of the island is as follows (21):
(21)δEXI=δargmindisΨv,Ψu,v=1,2,⋯t;u=1,2,⋯w,Ψv∈L1;Ψu∈L2;L1,L2∈LL=Lrt,Lrd,Llt,Lld.Among them,argmindisψv,ψurepresents the two nearest island centers among all the respective islands in the two local area networks. There is also a unique mapping relationship between the external islands in each local area network and the external islands in other local area networks. The solution method of the anchor point AP obtains the anchor points of the two external islands δEXI and establishes a connection between the corresponding anchor points so that the connectivity between the local networks can be restored, and then the purpose of global network connectivity restoration is achieved.Figure2(a) shows the random distribution of islands formed by the wireless sensor network after it suffers from large-scale disasters. It can be seen from the figure that nodes in the islands are connected with each other, and islands are independent of each other. The position of the center of the isolated island has been marked with a red five-pointed star. Figure 2(b) shows that the randomly distributed islands are divided into local areas, each island is divided into the corresponding local area, and four local area networks Llt, Lld, Lrt, and Lrd are obtained. Figure 2(c) shows that the optimal anchor points of each island are selected in the local area network, and the connectivity between islands is restored by deploying relay nodes between the optimal anchor points, so that each island in the local area network can reach the state of mutual connectivity. Figure 2(d) shows that when the connectivity of all the local area networks is restored, the external islands of each local area network are found through elections, and the same connectivity restoration method is used to restore the connectivity between the external islands, and finally to achieve connectivity recovery of the entire network.Figure 2
LPRMA recovery process of island connectivity.
(a)(b)(c)(d)In the process of realizing the recovery of isolated island connectivity, LPRMA follows the multianchor connection mode, whether within the local area network or between local networks, making the restored network more robust. The selection of anchor points in the isolated island is the key to LPRMA. The selection process of anchor points is as follows:(1)
In order to improve the efficiency of anchor point selection, the nodes in the island are firstly divided according to a specific thresholdTH=disψ1,ψ2, as shown in Figure 3(a). When the path cost of node ηi in island δ1 is PC=disηi,ψ2<TH, then node ηi is marked as a preselected node, thereby obtaining the preselected node-set η1pre of the island δ1. Similarly, under the same threshold TH, the preselected node-set η1pre of the island δ2 is obtained(2)
According to the average node degreeλave and the average energy state Eave of the nodes in η1pre, the nodes satisfying λi>λaveEi>Eave are selected as candidate anchor points, to obtain the set of candidate anchor point set η1can of the island δ1, as shown in Figure 3(b).(3)
Assign weightWEλ to ηi, assign weight WEe to Ei and assign weight WEp to PC of node ηi in η1can. Further filter according to the efficiency weight value WVE. Finally, the candidate node with the largest WVE is used as the optimal anchor AP relative to the island δ2, as shown in Figure 3(c).(22)WVE=λi⋅WEλ+Ei⋅WEe+PC⋅WEp.(4)
In the same way, the candidate anchor setη2can and the most suitable anchor AP of Island δ1 are screened, as shown in Figures 3(d) and 3(e). At this time, the most suitable anchor AP1in island δ1 and the most suitable anchor AP2 in island δ2 form a unique mapping relationship. A relay node is deployed between AP1 and AP2 to connect island δ1 and island δ2, as shown in Figure 3(f).Figure 3
Island anchor point selection process.
(a)(b)(c)(d)(e)(f)


## 3.1. Theoretical Model Solving

Nodes that satisfy constraints (2)–(5) in a collection of island nodes serve as candidate anchors to connect with other islands. The process of finding an island candidate anchor is summarized as an integer linear programming problem and set to M.For the solution of problemM, M is first relaxed, that is, the 0-1 value of xji is abandoned, to obtain the relaxation problem Q. Record the optimal solution of Q and the obtained minimum value, if the obtained solution is an integer solution, then the solution is the optimal solution of the candidate anchor point. Otherwise, the obtained candidate anchor point solution is used as the initial lower bound of the optimal solution of the problem, and the initial upper bound is set as +∞.
(11)MMin∑i∈G∑j∈Gxjidji∑i∈Nxji=1,∀j∈N∑j∈N,j∉Ψxji=1,∀i∈NλaλpE≥∑i=1mλai∑i=1mλpi∗∑i=1mEim,QMin∑i∈G∑j∈Gxjidji∑i∈Nxji=1,∀j∈N∑j∈N,j∉Ψxji=1,∀i∈NλaλpE≥∑i=1mλai∑i=1mλpi∗∑i=1mEimxji>0xji>xji+1.When the optimal solution of the relaxation problemQ of candidate anchor points is not an integer solution, the original integer programming problem M is divided into the following two subproblems.
(12)M1Min∑i∈G∑j∈Gxjidji,∑i∈Nxji=1,∀j∈N,∑j∈N,j∉Ψxji=1,∀i∈N,λaλpE≥∑i=1mλai∑i=1mλpi⋅∑i=1mEim,xji>0,xji<xji,M2Min∑i∈G∑j∈Gxjidji,∑i∈Nxji=1,∀j∈N,∑j∈N,j∉Ψxji=1,∀i∈N,λaλpE≥∑i=1mλai∑i=1mλpi∗∑i=1mEim,xji>0,xji>xji+1.In any subproblem, select one of the variables that do not satisfy the integer requirement of the candidate anchor point for processing, divide a candidate anchor point subproblem into two subproblems subject to further constraints by adding a pair of mutually exclusive constraints, and force Variables that are not integers are further approximated to integer values, and the noninteger field between two integers is removed at a time to narrow the search area. Therefore, if the subproblem does not meet the integer requirements of candidate anchor points, it will continue to branch downward.By continuously branching and solving each subproblem, the upper and lower bounds will be continuously revised. The lower bound is usually determined by the minimum target distance value between the anchor point of the subproblem and the center of the corresponding island, while the upper bound is determined by the optimal candidate anchor that has been obtained to confirm.Search for iterations according to the above steps. In each search process, whenever the lower bound is modified, all subproblems that have not been solved should be checked and those subproblems whose objective function value is less than the new lower bound should be checked. To improve the calculation process, the solution of the candidate anchor point is based on the constraint condition (5), and the nodes in the island are first selected, but the constraint may have a very small probability that no integer solution of the candidate anchor point can be found. At this time, the constraint of constraint condition (5) should be ignored, and then the solution should be resolved. Otherwise, the integer solution obtained during the search is the optimal solution for the candidate anchor, and finally, based on constraints (6)–(10), the nodes corresponding to the optimal solution for the candidate anchor are selected to satisfy the objective function. The node of (formula (1)) is the island’s most suitable anchor AP. When the most suitable anchor point AP is determined in all isolated islands, the WSN connectivity is restored through the deployment of relay nodes between the one-to-one corresponding APs by the robot, following the principle of local preferential recovery.


## 3.2. Algorithm Implementation

In the process of restoring the connectivity of isolated islands, the LPRMA algorithm includes three stages, namely, the determination of the center of the isolated island, the restoration of connectivity within the local area network, and the restoration of connectivity between local networks. The specific implementation of the three phases is as follows:


### 3.2.1. Determination of Island Center

The center of the island is a point that can represent the position of the island and is determined according to the positions of all nodes in the island. Due to the uncertainty of node distribution in the island, this paper firstly groups all nodesη=η1,η1⋯ηm in the island. Select k nodes from the node-set η as the initial k centroids μ=μ1,μ1⋯μk. Initialize the group C=C1,C1⋯Ck as Ct=∅,t=1,2⋯k.Calculate the node ηii=1,2⋯m and the similarity of each centroid μjj=1,2⋯k:
(13)distedxi,xj=∑u=1nxui,xuj2.In formula (13), distedxi,xj is the similarity between the node and the centroid, which is determined by the Euclidean distance between the node and the centroid. According to the similarity disted set of the node ηi, the ηi is divided into the group λi corresponding to the smallest disted, When all nodes are divided, the group is updated, and Cλi is the set of nodes in the group. The centroid Cjj=1,2⋯k is recalculated for all nodes in the updated group μi using the formula (15).
(14)Cλi=Cλi∪ηi,(15)μj=1Cj∑η∈Cjη.The iterative optimization of the centroid results is carried out continuously until allk centroids no longer change, then the final centroid set is output μij=1,2⋯k, which is calculated according to formula (16). Algorithm 1 is the pseudocode of the algorithm for determining the center of the island.
(16)ψ=1μi∑μ.Algorithm 1: Island Center Selection Algorithm.
Input  island selection δ,number of node groups kOutput  island center collection ψ1   μ ← null; C ← null; t =0;2   μ ← pick k nodes fromη;3   while ture do4    for i =1 to m5     for j =1 to k6     disted ← calculate the similarity between nodeηiAnd centroidμj;7      end for8     end for9    for i =1 to m10     find the ηi with the smallest similarity set of disted,And divide theηi into the corresponding group λi;11    end for12    Cλ ← Cλ∪{ηi};13    μ←recalculate the centroids of all nodes in Cλ;14    ifμnew==μbefore15     t++;16     if t==1017      break;18     end if19    end if20    end while21    according to the calculation of Cλ, the island center setψ is obtained;The number of executions of the statement in Algorithm1 is directly related to the variables m and k. The value of the variable m is determined according to the number of local area networks. In this paper, the number of local area networks is 4, and it can be known that the value range of the variable m is 1–4, and the size of the variable k is determined by the number of nodes in the island, and its value range is 1–n, then the summation formula can be used to obtain the maximum statement frequency fn of Algorithm 1.Taking the order of magnitude for fn, the time complexity of Algorithm 1 is On.(17)fn=∑i=1m∑i=1n1=4∑i=1n1=4n.


### 3.2.2. Recovery of Intranet Connectivity

A local area network is a subnetwork formed by dividing the global network into equal parts according to the center of its area. It is much more difficult to solve the connectivity restoration problem of multiple isolated islands in the network than the existing problems in the connected network, and it is difficult to complete it in one stage. Therefore, LPRMA uses the idea of divide and conquer to group multiple isolated islands into a local area network. The global network connectivity restoration problem is simplified into multiple local network connectivity restoration problems. According to the minimum square areaΩ that can contain all the islands specified in this paper, it is easy to obtain the central coordinate ωωx,ωy of the area, and the local area is divided as follows:
(18)Lx>ωx,Ly>ωy⟶Lrt,Lx>ωx,Ly<ωy⟶Lrd,Lx<ωx,Ly>ωy⟶Llt,Lx<ωx,Ly<ωy⟶Lld,Lrt,Lrd,Llt,Lld∈Ω.All the islands are divided into the correspondingLrt, Lrd, Llt, and Lld local area networks through the area where the island center ψii=1,2⋯N obtained in the previous process is located.According to the geographical location factorGP and the functional area marker FZ, the priority sequence L=Lrt,Lrd,Llt,Lld of each local area network in the local area network set Lpre=Lrt1,Lrd2,Llt3,Lld4 is obtained, and on this basis, according to the priority of the local area network, the islands in the local area network are connected and restored in turn.In the process of restoring connectivity in the local area network, firstly find the anchor points in each isolated island corresponding to other isolated islands in the same local area network. It is worth noting that when a node has been marked as the most suitable anchor After the point is selected, the determined anchor points are not considered when selecting anchor points relative to other islands, thus ensuring the principle of LPRMA multianchor point connection. At this time, the number of selected anchor pointsAP in each island satisfy the following relationship:
(19)APnum≥1,NL≥2,L=Lrt,Llt,Lrd,Lld,APnum=0,NL=1.There is a unique mapping relationship between the determined anchor points of the isolated islands in the same local area network and other isolated island anchor points, and then according to the mapping relationship between the anchor points, relay nodes are deployed between the two anchor points, to achieve connectivity recovery between two different islands. By analogy, when all the island anchors in the local area network have been connected, the connection in the local area network can be restored.Based on the above, the pseudocode of the algorithm for determining the optimal anchor point is given as follows.Algorithm 2: Optimal Anchor Point Selection.
Input  the isolated island set δ and the isolated island center set ψ in the local area network LOutput  optimal anchor point,optimal path1   E ← initialize the energy state of the node;2   λ←calculate the node degree of the node according to the graph G;3   node suitability fit←0;4   for i =1 to t5    dis←calculate the distance between the center of theCurrent islandδtand the center of other islandsδe;6   for j =1 to m;7      dt←calculate the distance from each nodeηjIn the islandδtto all nodes in another island;8     if dt < dis9       cand←ηj;10     ηj suitability fit←fit + dt∗distance weight;11      fit←fit+λ proportion∗E∗life status weight12     end if13    end for14    anc←max(fit);15    ancList←δeis added to the set of optimal anchorPoints;16   end for17    connect the two corresponding anchor points inancList to get the optimal path;The number of executions of the statement in Algorithm2 is directly related to the number of islands t and the number of nodes in the island k. Since the number of islands and the number of nodes in the island are unpredictable in practice, the value ranges of the variables t and k are both 1–n, then the summation formula can be used to obtain the maximum statement frequency fn of Algorithm 2.Taking the order of magnitude for fn, the time complexity of Algorithm 2 is On2.
(20)fn=∑t=1n∑k=1n1=∑t=1nn=n2.


### 3.2.3. Restore Connectivity between Local Areas

An external island is an island in a local area network that is used to establish connections with other local area networks. In order to restore connectivity between local networks, we must first determine theδEXIof the two local networks, and the identification of the island is as follows (21):
(21)δEXI=δargmindisΨv,Ψu,v=1,2,⋯t;u=1,2,⋯w,Ψv∈L1;Ψu∈L2;L1,L2∈LL=Lrt,Lrd,Llt,Lld.Among them,argmindisψv,ψurepresents the two nearest island centers among all the respective islands in the two local area networks. There is also a unique mapping relationship between the external islands in each local area network and the external islands in other local area networks. The solution method of the anchor point AP obtains the anchor points of the two external islands δEXI and establishes a connection between the corresponding anchor points so that the connectivity between the local networks can be restored, and then the purpose of global network connectivity restoration is achieved.Figure2(a) shows the random distribution of islands formed by the wireless sensor network after it suffers from large-scale disasters. It can be seen from the figure that nodes in the islands are connected with each other, and islands are independent of each other. The position of the center of the isolated island has been marked with a red five-pointed star. Figure 2(b) shows that the randomly distributed islands are divided into local areas, each island is divided into the corresponding local area, and four local area networks Llt, Lld, Lrt, and Lrd are obtained. Figure 2(c) shows that the optimal anchor points of each island are selected in the local area network, and the connectivity between islands is restored by deploying relay nodes between the optimal anchor points, so that each island in the local area network can reach the state of mutual connectivity. Figure 2(d) shows that when the connectivity of all the local area networks is restored, the external islands of each local area network are found through elections, and the same connectivity restoration method is used to restore the connectivity between the external islands, and finally to achieve connectivity recovery of the entire network.Figure 2
LPRMA recovery process of island connectivity.
(a)(b)(c)(d)In the process of realizing the recovery of isolated island connectivity, LPRMA follows the multianchor connection mode, whether within the local area network or between local networks, making the restored network more robust. The selection of anchor points in the isolated island is the key to LPRMA. The selection process of anchor points is as follows:(1)
In order to improve the efficiency of anchor point selection, the nodes in the island are firstly divided according to a specific thresholdTH=disψ1,ψ2, as shown in Figure 3(a). When the path cost of node ηi in island δ1 is PC=disηi,ψ2<TH, then node ηi is marked as a preselected node, thereby obtaining the preselected node-set η1pre of the island δ1. Similarly, under the same threshold TH, the preselected node-set η1pre of the island δ2 is obtained(2)
According to the average node degreeλave and the average energy state Eave of the nodes in η1pre, the nodes satisfying λi>λaveEi>Eave are selected as candidate anchor points, to obtain the set of candidate anchor point set η1can of the island δ1, as shown in Figure 3(b).(3)
Assign weightWEλ to ηi, assign weight WEe to Ei and assign weight WEp to PC of node ηi in η1can. Further filter according to the efficiency weight value WVE. Finally, the candidate node with the largest WVE is used as the optimal anchor AP relative to the island δ2, as shown in Figure 3(c).(22)WVE=λi⋅WEλ+Ei⋅WEe+PC⋅WEp.(4)
In the same way, the candidate anchor setη2can and the most suitable anchor AP of Island δ1 are screened, as shown in Figures 3(d) and 3(e). At this time, the most suitable anchor AP1in island δ1 and the most suitable anchor AP2 in island δ2 form a unique mapping relationship. A relay node is deployed between AP1 and AP2 to connect island δ1 and island δ2, as shown in Figure 3(f).Figure 3
Island anchor point selection process.
(a)(b)(c)(d)(e)(f)


## 3.2.1. Determination of Island Center

The center of the island is a point that can represent the position of the island and is determined according to the positions of all nodes in the island. Due to the uncertainty of node distribution in the island, this paper firstly groups all nodesη=η1,η1⋯ηm in the island. Select k nodes from the node-set η as the initial k centroids μ=μ1,μ1⋯μk. Initialize the group C=C1,C1⋯Ck as Ct=∅,t=1,2⋯k.Calculate the node ηii=1,2⋯m and the similarity of each centroid μjj=1,2⋯k:
(13)distedxi,xj=∑u=1nxui,xuj2.In formula (13), distedxi,xj is the similarity between the node and the centroid, which is determined by the Euclidean distance between the node and the centroid. According to the similarity disted set of the node ηi, the ηi is divided into the group λi corresponding to the smallest disted, When all nodes are divided, the group is updated, and Cλi is the set of nodes in the group. The centroid Cjj=1,2⋯k is recalculated for all nodes in the updated group μi using the formula (15).
(14)Cλi=Cλi∪ηi,(15)μj=1Cj∑η∈Cjη.The iterative optimization of the centroid results is carried out continuously until allk centroids no longer change, then the final centroid set is output μij=1,2⋯k, which is calculated according to formula (16). Algorithm 1 is the pseudocode of the algorithm for determining the center of the island.
(16)ψ=1μi∑μ.Algorithm 1: Island Center Selection Algorithm.
Input  island selection δ,number of node groups kOutput  island center collection ψ1   μ ← null; C ← null; t =0;2   μ ← pick k nodes fromη;3   while ture do4    for i =1 to m5     for j =1 to k6     disted ← calculate the similarity between nodeηiAnd centroidμj;7      end for8     end for9    for i =1 to m10     find the ηi with the smallest similarity set of disted,And divide theηi into the corresponding group λi;11    end for12    Cλ ← Cλ∪{ηi};13    μ←recalculate the centroids of all nodes in Cλ;14    ifμnew==μbefore15     t++;16     if t==1017      break;18     end if19    end if20    end while21    according to the calculation of Cλ, the island center setψ is obtained;The number of executions of the statement in Algorithm1 is directly related to the variables m and k. The value of the variable m is determined according to the number of local area networks. In this paper, the number of local area networks is 4, and it can be known that the value range of the variable m is 1–4, and the size of the variable k is determined by the number of nodes in the island, and its value range is 1–n, then the summation formula can be used to obtain the maximum statement frequency fn of Algorithm 1.Taking the order of magnitude for fn, the time complexity of Algorithm 1 is On.(17)fn=∑i=1m∑i=1n1=4∑i=1n1=4n.


## 3.2.2. Recovery of Intranet Connectivity

A local area network is a subnetwork formed by dividing the global network into equal parts according to the center of its area. It is much more difficult to solve the connectivity restoration problem of multiple isolated islands in the network than the existing problems in the connected network, and it is difficult to complete it in one stage. Therefore, LPRMA uses the idea of divide and conquer to group multiple isolated islands into a local area network. The global network connectivity restoration problem is simplified into multiple local network connectivity restoration problems. According to the minimum square areaΩ that can contain all the islands specified in this paper, it is easy to obtain the central coordinate ωωx,ωy of the area, and the local area is divided as follows:
(18)Lx>ωx,Ly>ωy⟶Lrt,Lx>ωx,Ly<ωy⟶Lrd,Lx<ωx,Ly>ωy⟶Llt,Lx<ωx,Ly<ωy⟶Lld,Lrt,Lrd,Llt,Lld∈Ω.All the islands are divided into the correspondingLrt, Lrd, Llt, and Lld local area networks through the area where the island center ψii=1,2⋯N obtained in the previous process is located.According to the geographical location factorGP and the functional area marker FZ, the priority sequence L=Lrt,Lrd,Llt,Lld of each local area network in the local area network set Lpre=Lrt1,Lrd2,Llt3,Lld4 is obtained, and on this basis, according to the priority of the local area network, the islands in the local area network are connected and restored in turn.In the process of restoring connectivity in the local area network, firstly find the anchor points in each isolated island corresponding to other isolated islands in the same local area network. It is worth noting that when a node has been marked as the most suitable anchor After the point is selected, the determined anchor points are not considered when selecting anchor points relative to other islands, thus ensuring the principle of LPRMA multianchor point connection. At this time, the number of selected anchor pointsAP in each island satisfy the following relationship:
(19)APnum≥1,NL≥2,L=Lrt,Llt,Lrd,Lld,APnum=0,NL=1.There is a unique mapping relationship between the determined anchor points of the isolated islands in the same local area network and other isolated island anchor points, and then according to the mapping relationship between the anchor points, relay nodes are deployed between the two anchor points, to achieve connectivity recovery between two different islands. By analogy, when all the island anchors in the local area network have been connected, the connection in the local area network can be restored.Based on the above, the pseudocode of the algorithm for determining the optimal anchor point is given as follows.Algorithm 2: Optimal Anchor Point Selection.
Input  the isolated island set δ and the isolated island center set ψ in the local area network LOutput  optimal anchor point,optimal path1   E ← initialize the energy state of the node;2   λ←calculate the node degree of the node according to the graph G;3   node suitability fit←0;4   for i =1 to t5    dis←calculate the distance between the center of theCurrent islandδtand the center of other islandsδe;6   for j =1 to m;7      dt←calculate the distance from each nodeηjIn the islandδtto all nodes in another island;8     if dt < dis9       cand←ηj;10     ηj suitability fit←fit + dt∗distance weight;11      fit←fit+λ proportion∗E∗life status weight12     end if13    end for14    anc←max(fit);15    ancList←δeis added to the set of optimal anchorPoints;16   end for17    connect the two corresponding anchor points inancList to get the optimal path;The number of executions of the statement in Algorithm2 is directly related to the number of islands t and the number of nodes in the island k. Since the number of islands and the number of nodes in the island are unpredictable in practice, the value ranges of the variables t and k are both 1–n, then the summation formula can be used to obtain the maximum statement frequency fn of Algorithm 2.Taking the order of magnitude for fn, the time complexity of Algorithm 2 is On2.
(20)fn=∑t=1n∑k=1n1=∑t=1nn=n2.


## 3.2.3. Restore Connectivity between Local Areas

An external island is an island in a local area network that is used to establish connections with other local area networks. In order to restore connectivity between local networks, we must first determine theδEXIof the two local networks, and the identification of the island is as follows (21):
(21)δEXI=δargmindisΨv,Ψu,v=1,2,⋯t;u=1,2,⋯w,Ψv∈L1;Ψu∈L2;L1,L2∈LL=Lrt,Lrd,Llt,Lld.Among them,argmindisψv,ψurepresents the two nearest island centers among all the respective islands in the two local area networks. There is also a unique mapping relationship between the external islands in each local area network and the external islands in other local area networks. The solution method of the anchor point AP obtains the anchor points of the two external islands δEXI and establishes a connection between the corresponding anchor points so that the connectivity between the local networks can be restored, and then the purpose of global network connectivity restoration is achieved.Figure2(a) shows the random distribution of islands formed by the wireless sensor network after it suffers from large-scale disasters. It can be seen from the figure that nodes in the islands are connected with each other, and islands are independent of each other. The position of the center of the isolated island has been marked with a red five-pointed star. Figure 2(b) shows that the randomly distributed islands are divided into local areas, each island is divided into the corresponding local area, and four local area networks Llt, Lld, Lrt, and Lrd are obtained. Figure 2(c) shows that the optimal anchor points of each island are selected in the local area network, and the connectivity between islands is restored by deploying relay nodes between the optimal anchor points, so that each island in the local area network can reach the state of mutual connectivity. Figure 2(d) shows that when the connectivity of all the local area networks is restored, the external islands of each local area network are found through elections, and the same connectivity restoration method is used to restore the connectivity between the external islands, and finally to achieve connectivity recovery of the entire network.Figure 2
LPRMA recovery process of island connectivity.
(a)(b)(c)(d)In the process of realizing the recovery of isolated island connectivity, LPRMA follows the multianchor connection mode, whether within the local area network or between local networks, making the restored network more robust. The selection of anchor points in the isolated island is the key to LPRMA. The selection process of anchor points is as follows:(1)
In order to improve the efficiency of anchor point selection, the nodes in the island are firstly divided according to a specific thresholdTH=disψ1,ψ2, as shown in Figure 3(a). When the path cost of node ηi in island δ1 is PC=disηi,ψ2<TH, then node ηi is marked as a preselected node, thereby obtaining the preselected node-set η1pre of the island δ1. Similarly, under the same threshold TH, the preselected node-set η1pre of the island δ2 is obtained(2)
According to the average node degreeλave and the average energy state Eave of the nodes in η1pre, the nodes satisfying λi>λaveEi>Eave are selected as candidate anchor points, to obtain the set of candidate anchor point set η1can of the island δ1, as shown in Figure 3(b).(3)
Assign weightWEλ to ηi, assign weight WEe to Ei and assign weight WEp to PC of node ηi in η1can. Further filter according to the efficiency weight value WVE. Finally, the candidate node with the largest WVE is used as the optimal anchor AP relative to the island δ2, as shown in Figure 3(c).(22)WVE=λi⋅WEλ+Ei⋅WEe+PC⋅WEp.(4)
In the same way, the candidate anchor setη2can and the most suitable anchor AP of Island δ1 are screened, as shown in Figures 3(d) and 3(e). At this time, the most suitable anchor AP1in island δ1 and the most suitable anchor AP2 in island δ2 form a unique mapping relationship. A relay node is deployed between AP1 and AP2 to connect island δ1 and island δ2, as shown in Figure 3(f).Figure 3
Island anchor point selection process.
(a)(b)(c)(d)(e)(f)


## 4. Performance Evaluation

### 4.1. Performance Analysis

In the process of restoring island connectivity, LPRMA follows two principles. One is the principle of multianchor point connection. Whether it is the connectivity restoration within the local area network or the connection restoration between local area networks, the connection mode of multianchor points is adopted, thereby reducing the connection recovery cost, enhancing the network robustness, and prolonging the network life. The second is the principle of local priority recovery, which improves the recovery efficiency of global network connectivity, enhances the performance of network transaction processing, and reduces network latency.


#### 4.1.1. Robustness Analysis

After the network encounters secondary damage, the multianchor connection between islands is more stable than the traditional single-anchor connection, making the network more robust.The method of connection of a single anchor point is to select only one node in the island as the node of communication between the island and other islands. When the network suffers secondary damage, the connection between the island and the other islands perhaps is disrupted. As shown in Figure4(a), when the island communication node of island δ1 stops working due to secondary injury, the communication paths p1 and p2 are interrupted, causing island δ1 to lose connection. Only Island δ2 and Island δ3 are connected in the network, as shown in Figure 4(b).Figure 4
Single anchor performance.
(a)(b)When the multianchor connection is adopted, the communication connection between an island and other islands does not depend on one node alone. When a communication node stops working due to secondary damage, only part of the communication path is interrupted. As shown in Figure5(a), when one of the communication nodes of Island δ1 is destroyed, it only interrupts the communication path p2 between Island δ1 and Island δ2. But in this network, Island δ2, Island δ2, and Island δ3 are still connected, as shown in Figure 5(b). Therefore, the multianchor connection method has stronger network robustness.Figure 5
Multianchor performance.
(a)(b)


#### 4.1.2. Analysis of Transaction Efficiency

After the island connection is restored, the processing efficiency of the network transactions in the island directly affects the size of the network delay. Therefore, more efficient network transaction processing performance plays a crucial role in reducing network delay. Compared with existing solutions, the transaction processing efficiency of LPRMA is more efficient and the network delay is lower. In Table2, the transactions in some islands after large-scale damage to the network are listed. When the network is restored to a fully connected state, the interrupted transactions must be reprocessed in each isolated island. Therefore, the processing efficiency of the transaction is particularly important and the processing efficiency depends on the processing delay.Table 2
Transactions in island.
IslandPending transactionδ1T11(1,3)T12(1,2,4)T13(1,5,3,6)δ2T21(2,4)T22(2,3,4)T23(2,1,3,8)δ3T31(3,6)T32(3,2,5)T33(3,4,6,9)δ4T31(4,7)T32(4,6,7)T43(4,5,7,8)δ5T51(5,3)T52(5,3,4)T53(5,7,8,9)δ6T61(6,4)T62(6,4,8)T63(6,3,7,9)δ7T71(7,5)T72(7,3,6)T73(7,4,6,9)δ8T81(8,9)T82(8,4,9)T83(7,5,6,8)δ9T91(9,4)T92(9,3,4)T93(9,2,4,5)Due to the different ways of connecting islands, the delay in handling transactions is different. Table3 is the process path of each transaction in the island using the connected recovery strategy and the existing connected recovery strategy.Table 3
Transaction paths.
T11(1,3)T12(1,2,4)T13(1,5,6,3)LPRMAδ1−>δ2−>δ5−>δ3δ1−>δ2−>δ4δ1−>δ2−>δ5−>δ6−>δ3DAAPδ1−>δ2−>δ5−>δ3δ1−>δ2−>δ1−>δ4δ1−>δ2−>δ5−>δ3−>δ6−>δ3The delay functionZ is used to determine the size of the delay. Let Z1 be a transaction delay for LPRMA, and Z2 be a transaction delay for existing recovery policies, Z1<Z2is obtained by calculating the data in Table 1.
(23)Ζ=1n∑in∑j=1mLijv+wt.In formula (23), Lij is the length of the transaction path, v is the data propagation rate, and wt is the waiting time. In addition, this paper conducts random processing on the transaction composition in the island and calculates the result according to formula (23): Z1≤Z2. When the transaction volume in the island is small, Z1=Z2 may occur, but the probability of this situation is relatively small, and more cases are Z1<Z2, indicating that the transaction processing efficiency of LPRMA is better than the existing recovery strategy transaction processing efficiency.


### 4.2. Simulation Comparison Experiment

This part uses MATLAB R2016a to establish the simulation model of wireless sensor network, and uses its efficient numerical calculation and symbolic calculation functions to simulate the generation of islands and implement the method proposed in this paper and the existing methods, and then through the software’s graphics processing function, realize the visualization of simulation comparison results. We take the final path length of relay deployment, the number of relay deployments and the deployment time of relays, the number of remaining nodes in the network after secondary disasters, and the processing efficiency of network transactions as evaluation indicators to compare LPRMA with other island connection recovery schemes DR-ACO [12] and DAAP [13]. The simulation environment and initial conditions are set as follows: (1) the network area W is a square plane of 1000×1000m, and there are multiple islands randomly distributed in W, and multiple sensor nodes are randomly distributed in each island. (2) The sensing and communication radii of sensor nodes are 5 m and 10 m, respectively. (3) The traveling speed of the robot used to deploy the relay node is v=5m/s, and the deployment time of each relay is T=10s; 4. The sensing and communication radius of the robot is 20 m and 30 m, respectively; 5. The relay is an ordinary sensor node. In addition, considering the randomness of the island distribution, the experimental test is run 100 times, and the average is taken as the final result.


#### 4.2.1. Final Path Length

This experiment evaluates the total length of connection recovery paths for three different schemes. This metric can be used to evaluate the recovery efficiency of network connections. The smaller the path length, the higher the connection recovery efficiency.As shown in Figure6, in the LPRMA scheme and the existing restoration schemes DR-ACO and DAAP, as the number of islands increases, the total length of the final paths of the three connection restoration schemes also increases. In DAAP, since more polygon lines are generated as the number of islands increases, polygon lines increase the total length of the path compared to straight lines. In the LPRMA scheme, the number of paths connected by islands increases as the number of islands increases, thus increasing the length of the final path. Although the number of paths in LPRMA increases, each path in LPRMA is a short path, making LPRMA. The final path length is always smaller than the DR-ACO and DAAP schemes. The reason for the existence of several short paths in LPRMA is the special connection selection mechanism of LPRMA. The LPRMA multianchor point is connected by selecting the anchor point with the shortest path as the target in the two relatively nearest islands. When the number of islands increases, the selection range of multi-islands connected by multianchor points is wider, and the formed connection path is shorter, thus minimizing the final path length.Figure 6
Final path length comparison.Therefore, the performance of LPRMA is more prominent in the total length of the final connection recovery path, and the connection recovery efficiency is higher.


#### 4.2.2. Number of Relay Deployments and Deployment Time

Figures7 and 8 show the comparison results of the number of relay deployments and the deployment time of relays between LPRMA, DR-ACO, and DAAP as the relay communication radius Rc and the number of islands N gradually increase.Figure 7
Comparison of the number of relay deployments.
(a)(b)Figure 8
Comparison of relay deployment time.
(a)(b)In Figure7(a), under the conditions of N=10 and W=1000m×1000m, with the increase of Rc, the number of relay deployments of LPRMA and the other two schemes gradually decreases. This is because the number of relay deployments is determined by the number of routing hops between islands, which is inversely proportional to Rc. Furthermore, compared to the other two schemes, the advantages of LPRMA are more prominent. This is because the final connection path length of LPRMA is shorter than that of DR-ACO and DAAP, which makes the middle. There are fewer deployments of the successor nodes. In Figure 7(b), under the conditions of Rc=20, W=1000m×1000m, with increasing N, the number of relay nodes deployed in LPRMA and the other two schemes gradually increases. Due to the increase in the number of islands, the connectivity when the recovered final path length increases, more relay nodes are needed to construct the connected path, so the deployment number of relay nodes for the three schemes increases. But LPRMA has more advantages than the other two schemes in terms of the final connected path length, so the number of relay nodes deployed is less than the other two schemes.Under the same conditions, the relay deployment time in Figures8(a) and 8(b) is similar to the relay deployment number in Figures 7(a) and 7(b). This is because the relay deployment time depends on the deployment path length and the number of relay deployments, and the trends of the final path lengths of the three schemes are relatively unchanged. Therefore, when the robot’s travel speed v is the same as the single relay deployment time T, the relay deployment of the three schemes. The time is mainly determined by the number of relay deployments.


#### 4.2.3. Robustness of the Network

The experimental design is to evaluate the robustness of the network after the network recovery by judging the number of remaining nodes in the network. As shown in Figure9(a), the number of remaining nodes in the three recovery schemes decreases when the damage to the network increases after secondary injury. In Figure 9(b), when the degree of secondary damage is certain, the number of remaining nodes in the three schemes increases with increasing number of islands, because the increase in the number of islands increases the total number of nodes in the network. Regardless of the degree of damage or the number of islands, the number of remaining nodes in the LPRMA scheme is higher than in the existing two schemes, which is due to the multianchor connection method in the LPRMA scheme. When the restored network suffers secondary damage, it is likely to damage the communication anchor points used to connect with other isolated islands. Most of the existing restoration schemes use a single-anchor point connection mode. Under this connection mode, once the communication anchor is damaged, the entire island will lose connection to other islands. The multianchor connection method adopted by the LPRMA scheme will not lose contact with all other islands due to the damage to one anchor, which makes the LPRMA scheme better than the existing DR-ACO and DAAP schemes in terms of restoring the number of nodes remaining in the network after secondary damage. Thus, the restoration scheme proposed in this paper has higher network robustness.Figure 9
Comparison of the number of remaining nodes.
(a)(b)


#### 4.2.4. Transaction Processing Efficiency

After the network connection is restored, the efficiency of transaction processing in the network is also very important, which affects the level of network delay. This paper evaluates the performance of three connectivity schemes in network transaction processing using the transaction processing efficiency indexPEI and processing delay Z. Among them, the higher the PEI, the higher the transaction processing efficiency.
(24)PEI=1NDT−DTPN.DT is the degree of transaction sequence, which represents the number of islands involved in a transaction, and PN is the number of valid paths for transaction processing. As shown in Figure 10(a), with the increase in the number of islands, the PEI of the three schemes gradually decreases, because the increase in the number of islands intensifies the number of transactions in the network and increases the complexity of transaction processing, thus reducing the PEI. However, in different numbers of islands, the PEI of LPRMA is always higher than the other two schemes, which is because the multianchor connection mode of LPRMA will generate more short paths with the increase of the number of islands, the increase of short paths will increase the PN of LPRMA transaction processing, and thus the PEI will be higher. As shown in Figure 10(b), due to the gradual decrease of PEI, the transaction processing delay Z of the three schemes increases with the increase of the number of islands. Because LPRMA is more efficient for transaction processing, the processing delay of LPRMA is lower than the other two options.Figure 10
Comparison of transaction efficiency.
(a)(b)


## 4.1. Performance Analysis

In the process of restoring island connectivity, LPRMA follows two principles. One is the principle of multianchor point connection. Whether it is the connectivity restoration within the local area network or the connection restoration between local area networks, the connection mode of multianchor points is adopted, thereby reducing the connection recovery cost, enhancing the network robustness, and prolonging the network life. The second is the principle of local priority recovery, which improves the recovery efficiency of global network connectivity, enhances the performance of network transaction processing, and reduces network latency.


### 4.1.1. Robustness Analysis

After the network encounters secondary damage, the multianchor connection between islands is more stable than the traditional single-anchor connection, making the network more robust.The method of connection of a single anchor point is to select only one node in the island as the node of communication between the island and other islands. When the network suffers secondary damage, the connection between the island and the other islands perhaps is disrupted. As shown in Figure4(a), when the island communication node of island δ1 stops working due to secondary injury, the communication paths p1 and p2 are interrupted, causing island δ1 to lose connection. Only Island δ2 and Island δ3 are connected in the network, as shown in Figure 4(b).Figure 4
Single anchor performance.
(a)(b)When the multianchor connection is adopted, the communication connection between an island and other islands does not depend on one node alone. When a communication node stops working due to secondary damage, only part of the communication path is interrupted. As shown in Figure5(a), when one of the communication nodes of Island δ1 is destroyed, it only interrupts the communication path p2 between Island δ1 and Island δ2. But in this network, Island δ2, Island δ2, and Island δ3 are still connected, as shown in Figure 5(b). Therefore, the multianchor connection method has stronger network robustness.Figure 5
Multianchor performance.
(a)(b)


### 4.1.2. Analysis of Transaction Efficiency

After the island connection is restored, the processing efficiency of the network transactions in the island directly affects the size of the network delay. Therefore, more efficient network transaction processing performance plays a crucial role in reducing network delay. Compared with existing solutions, the transaction processing efficiency of LPRMA is more efficient and the network delay is lower. In Table2, the transactions in some islands after large-scale damage to the network are listed. When the network is restored to a fully connected state, the interrupted transactions must be reprocessed in each isolated island. Therefore, the processing efficiency of the transaction is particularly important and the processing efficiency depends on the processing delay.Table 2
Transactions in island.
IslandPending transactionδ1T11(1,3)T12(1,2,4)T13(1,5,3,6)δ2T21(2,4)T22(2,3,4)T23(2,1,3,8)δ3T31(3,6)T32(3,2,5)T33(3,4,6,9)δ4T31(4,7)T32(4,6,7)T43(4,5,7,8)δ5T51(5,3)T52(5,3,4)T53(5,7,8,9)δ6T61(6,4)T62(6,4,8)T63(6,3,7,9)δ7T71(7,5)T72(7,3,6)T73(7,4,6,9)δ8T81(8,9)T82(8,4,9)T83(7,5,6,8)δ9T91(9,4)T92(9,3,4)T93(9,2,4,5)Due to the different ways of connecting islands, the delay in handling transactions is different. Table3 is the process path of each transaction in the island using the connected recovery strategy and the existing connected recovery strategy.Table 3
Transaction paths.
T11(1,3)T12(1,2,4)T13(1,5,6,3)LPRMAδ1−>δ2−>δ5−>δ3δ1−>δ2−>δ4δ1−>δ2−>δ5−>δ6−>δ3DAAPδ1−>δ2−>δ5−>δ3δ1−>δ2−>δ1−>δ4δ1−>δ2−>δ5−>δ3−>δ6−>δ3The delay functionZ is used to determine the size of the delay. Let Z1 be a transaction delay for LPRMA, and Z2 be a transaction delay for existing recovery policies, Z1<Z2is obtained by calculating the data in Table 1.
(23)Ζ=1n∑in∑j=1mLijv+wt.In formula (23), Lij is the length of the transaction path, v is the data propagation rate, and wt is the waiting time. In addition, this paper conducts random processing on the transaction composition in the island and calculates the result according to formula (23): Z1≤Z2. When the transaction volume in the island is small, Z1=Z2 may occur, but the probability of this situation is relatively small, and more cases are Z1<Z2, indicating that the transaction processing efficiency of LPRMA is better than the existing recovery strategy transaction processing efficiency.


## 4.1.1. Robustness Analysis

After the network encounters secondary damage, the multianchor connection between islands is more stable than the traditional single-anchor connection, making the network more robust.The method of connection of a single anchor point is to select only one node in the island as the node of communication between the island and other islands. When the network suffers secondary damage, the connection between the island and the other islands perhaps is disrupted. As shown in Figure4(a), when the island communication node of island δ1 stops working due to secondary injury, the communication paths p1 and p2 are interrupted, causing island δ1 to lose connection. Only Island δ2 and Island δ3 are connected in the network, as shown in Figure 4(b).Figure 4
Single anchor performance.
(a)(b)When the multianchor connection is adopted, the communication connection between an island and other islands does not depend on one node alone. When a communication node stops working due to secondary damage, only part of the communication path is interrupted. As shown in Figure5(a), when one of the communication nodes of Island δ1 is destroyed, it only interrupts the communication path p2 between Island δ1 and Island δ2. But in this network, Island δ2, Island δ2, and Island δ3 are still connected, as shown in Figure 5(b). Therefore, the multianchor connection method has stronger network robustness.Figure 5
Multianchor performance.
(a)(b)


## 4.1.2. Analysis of Transaction Efficiency

After the island connection is restored, the processing efficiency of the network transactions in the island directly affects the size of the network delay. Therefore, more efficient network transaction processing performance plays a crucial role in reducing network delay. Compared with existing solutions, the transaction processing efficiency of LPRMA is more efficient and the network delay is lower. In Table2, the transactions in some islands after large-scale damage to the network are listed. When the network is restored to a fully connected state, the interrupted transactions must be reprocessed in each isolated island. Therefore, the processing efficiency of the transaction is particularly important and the processing efficiency depends on the processing delay.Table 2
Transactions in island.
IslandPending transactionδ1T11(1,3)T12(1,2,4)T13(1,5,3,6)δ2T21(2,4)T22(2,3,4)T23(2,1,3,8)δ3T31(3,6)T32(3,2,5)T33(3,4,6,9)δ4T31(4,7)T32(4,6,7)T43(4,5,7,8)δ5T51(5,3)T52(5,3,4)T53(5,7,8,9)δ6T61(6,4)T62(6,4,8)T63(6,3,7,9)δ7T71(7,5)T72(7,3,6)T73(7,4,6,9)δ8T81(8,9)T82(8,4,9)T83(7,5,6,8)δ9T91(9,4)T92(9,3,4)T93(9,2,4,5)Due to the different ways of connecting islands, the delay in handling transactions is different. Table3 is the process path of each transaction in the island using the connected recovery strategy and the existing connected recovery strategy.Table 3
Transaction paths.
T11(1,3)T12(1,2,4)T13(1,5,6,3)LPRMAδ1−>δ2−>δ5−>δ3δ1−>δ2−>δ4δ1−>δ2−>δ5−>δ6−>δ3DAAPδ1−>δ2−>δ5−>δ3δ1−>δ2−>δ1−>δ4δ1−>δ2−>δ5−>δ3−>δ6−>δ3The delay functionZ is used to determine the size of the delay. Let Z1 be a transaction delay for LPRMA, and Z2 be a transaction delay for existing recovery policies, Z1<Z2is obtained by calculating the data in Table 1.
(23)Ζ=1n∑in∑j=1mLijv+wt.In formula (23), Lij is the length of the transaction path, v is the data propagation rate, and wt is the waiting time. In addition, this paper conducts random processing on the transaction composition in the island and calculates the result according to formula (23): Z1≤Z2. When the transaction volume in the island is small, Z1=Z2 may occur, but the probability of this situation is relatively small, and more cases are Z1<Z2, indicating that the transaction processing efficiency of LPRMA is better than the existing recovery strategy transaction processing efficiency.


## 4.2. Simulation Comparison Experiment

This part uses MATLAB R2016a to establish the simulation model of wireless sensor network, and uses its efficient numerical calculation and symbolic calculation functions to simulate the generation of islands and implement the method proposed in this paper and the existing methods, and then through the software’s graphics processing function, realize the visualization of simulation comparison results. We take the final path length of relay deployment, the number of relay deployments and the deployment time of relays, the number of remaining nodes in the network after secondary disasters, and the processing efficiency of network transactions as evaluation indicators to compare LPRMA with other island connection recovery schemes DR-ACO [12] and DAAP [13]. The simulation environment and initial conditions are set as follows: (1) the network area W is a square plane of 1000×1000m, and there are multiple islands randomly distributed in W, and multiple sensor nodes are randomly distributed in each island. (2) The sensing and communication radii of sensor nodes are 5 m and 10 m, respectively. (3) The traveling speed of the robot used to deploy the relay node is v=5m/s, and the deployment time of each relay is T=10s; 4. The sensing and communication radius of the robot is 20 m and 30 m, respectively; 5. The relay is an ordinary sensor node. In addition, considering the randomness of the island distribution, the experimental test is run 100 times, and the average is taken as the final result.


### 4.2.1. Final Path Length

This experiment evaluates the total length of connection recovery paths for three different schemes. This metric can be used to evaluate the recovery efficiency of network connections. The smaller the path length, the higher the connection recovery efficiency.As shown in Figure6, in the LPRMA scheme and the existing restoration schemes DR-ACO and DAAP, as the number of islands increases, the total length of the final paths of the three connection restoration schemes also increases. In DAAP, since more polygon lines are generated as the number of islands increases, polygon lines increase the total length of the path compared to straight lines. In the LPRMA scheme, the number of paths connected by islands increases as the number of islands increases, thus increasing the length of the final path. Although the number of paths in LPRMA increases, each path in LPRMA is a short path, making LPRMA. The final path length is always smaller than the DR-ACO and DAAP schemes. The reason for the existence of several short paths in LPRMA is the special connection selection mechanism of LPRMA. The LPRMA multianchor point is connected by selecting the anchor point with the shortest path as the target in the two relatively nearest islands. When the number of islands increases, the selection range of multi-islands connected by multianchor points is wider, and the formed connection path is shorter, thus minimizing the final path length.Figure 6
Final path length comparison.Therefore, the performance of LPRMA is more prominent in the total length of the final connection recovery path, and the connection recovery efficiency is higher.


### 4.2.2. Number of Relay Deployments and Deployment Time

Figures7 and 8 show the comparison results of the number of relay deployments and the deployment time of relays between LPRMA, DR-ACO, and DAAP as the relay communication radius Rc and the number of islands N gradually increase.Figure 7
Comparison of the number of relay deployments.
(a)(b)Figure 8
Comparison of relay deployment time.
(a)(b)In Figure7(a), under the conditions of N=10 and W=1000m×1000m, with the increase of Rc, the number of relay deployments of LPRMA and the other two schemes gradually decreases. This is because the number of relay deployments is determined by the number of routing hops between islands, which is inversely proportional to Rc. Furthermore, compared to the other two schemes, the advantages of LPRMA are more prominent. This is because the final connection path length of LPRMA is shorter than that of DR-ACO and DAAP, which makes the middle. There are fewer deployments of the successor nodes. In Figure 7(b), under the conditions of Rc=20, W=1000m×1000m, with increasing N, the number of relay nodes deployed in LPRMA and the other two schemes gradually increases. Due to the increase in the number of islands, the connectivity when the recovered final path length increases, more relay nodes are needed to construct the connected path, so the deployment number of relay nodes for the three schemes increases. But LPRMA has more advantages than the other two schemes in terms of the final connected path length, so the number of relay nodes deployed is less than the other two schemes.Under the same conditions, the relay deployment time in Figures8(a) and 8(b) is similar to the relay deployment number in Figures 7(a) and 7(b). This is because the relay deployment time depends on the deployment path length and the number of relay deployments, and the trends of the final path lengths of the three schemes are relatively unchanged. Therefore, when the robot’s travel speed v is the same as the single relay deployment time T, the relay deployment of the three schemes. The time is mainly determined by the number of relay deployments.


### 4.2.3. Robustness of the Network

The experimental design is to evaluate the robustness of the network after the network recovery by judging the number of remaining nodes in the network. As shown in Figure9(a), the number of remaining nodes in the three recovery schemes decreases when the damage to the network increases after secondary injury. In Figure 9(b), when the degree of secondary damage is certain, the number of remaining nodes in the three schemes increases with increasing number of islands, because the increase in the number of islands increases the total number of nodes in the network. Regardless of the degree of damage or the number of islands, the number of remaining nodes in the LPRMA scheme is higher than in the existing two schemes, which is due to the multianchor connection method in the LPRMA scheme. When the restored network suffers secondary damage, it is likely to damage the communication anchor points used to connect with other isolated islands. Most of the existing restoration schemes use a single-anchor point connection mode. Under this connection mode, once the communication anchor is damaged, the entire island will lose connection to other islands. The multianchor connection method adopted by the LPRMA scheme will not lose contact with all other islands due to the damage to one anchor, which makes the LPRMA scheme better than the existing DR-ACO and DAAP schemes in terms of restoring the number of nodes remaining in the network after secondary damage. Thus, the restoration scheme proposed in this paper has higher network robustness.Figure 9
Comparison of the number of remaining nodes.
(a)(b)


### 4.2.4. Transaction Processing Efficiency

After the network connection is restored, the efficiency of transaction processing in the network is also very important, which affects the level of network delay. This paper evaluates the performance of three connectivity schemes in network transaction processing using the transaction processing efficiency indexPEI and processing delay Z. Among them, the higher the PEI, the higher the transaction processing efficiency.
(24)PEI=1NDT−DTPN.DT is the degree of transaction sequence, which represents the number of islands involved in a transaction, and PN is the number of valid paths for transaction processing. As shown in Figure 10(a), with the increase in the number of islands, the PEI of the three schemes gradually decreases, because the increase in the number of islands intensifies the number of transactions in the network and increases the complexity of transaction processing, thus reducing the PEI. However, in different numbers of islands, the PEI of LPRMA is always higher than the other two schemes, which is because the multianchor connection mode of LPRMA will generate more short paths with the increase of the number of islands, the increase of short paths will increase the PN of LPRMA transaction processing, and thus the PEI will be higher. As shown in Figure 10(b), due to the gradual decrease of PEI, the transaction processing delay Z of the three schemes increases with the increase of the number of islands. Because LPRMA is more efficient for transaction processing, the processing delay of LPRMA is lower than the other two options.Figure 10
Comparison of transaction efficiency.
(a)(b)


## 4.2.1. Final Path Length

This experiment evaluates the total length of connection recovery paths for three different schemes. This metric can be used to evaluate the recovery efficiency of network connections. The smaller the path length, the higher the connection recovery efficiency.As shown in Figure6, in the LPRMA scheme and the existing restoration schemes DR-ACO and DAAP, as the number of islands increases, the total length of the final paths of the three connection restoration schemes also increases. In DAAP, since more polygon lines are generated as the number of islands increases, polygon lines increase the total length of the path compared to straight lines. In the LPRMA scheme, the number of paths connected by islands increases as the number of islands increases, thus increasing the length of the final path. Although the number of paths in LPRMA increases, each path in LPRMA is a short path, making LPRMA. The final path length is always smaller than the DR-ACO and DAAP schemes. The reason for the existence of several short paths in LPRMA is the special connection selection mechanism of LPRMA. The LPRMA multianchor point is connected by selecting the anchor point with the shortest path as the target in the two relatively nearest islands. When the number of islands increases, the selection range of multi-islands connected by multianchor points is wider, and the formed connection path is shorter, thus minimizing the final path length.Figure 6
Final path length comparison.Therefore, the performance of LPRMA is more prominent in the total length of the final connection recovery path, and the connection recovery efficiency is higher.


## 4.2.2. Number of Relay Deployments and Deployment Time

Figures7 and 8 show the comparison results of the number of relay deployments and the deployment time of relays between LPRMA, DR-ACO, and DAAP as the relay communication radius Rc and the number of islands N gradually increase.Figure 7
Comparison of the number of relay deployments.
(a)(b)Figure 8
Comparison of relay deployment time.
(a)(b)In Figure7(a), under the conditions of N=10 and W=1000m×1000m, with the increase of Rc, the number of relay deployments of LPRMA and the other two schemes gradually decreases. This is because the number of relay deployments is determined by the number of routing hops between islands, which is inversely proportional to Rc. Furthermore, compared to the other two schemes, the advantages of LPRMA are more prominent. This is because the final connection path length of LPRMA is shorter than that of DR-ACO and DAAP, which makes the middle. There are fewer deployments of the successor nodes. In Figure 7(b), under the conditions of Rc=20, W=1000m×1000m, with increasing N, the number of relay nodes deployed in LPRMA and the other two schemes gradually increases. Due to the increase in the number of islands, the connectivity when the recovered final path length increases, more relay nodes are needed to construct the connected path, so the deployment number of relay nodes for the three schemes increases. But LPRMA has more advantages than the other two schemes in terms of the final connected path length, so the number of relay nodes deployed is less than the other two schemes.Under the same conditions, the relay deployment time in Figures8(a) and 8(b) is similar to the relay deployment number in Figures 7(a) and 7(b). This is because the relay deployment time depends on the deployment path length and the number of relay deployments, and the trends of the final path lengths of the three schemes are relatively unchanged. Therefore, when the robot’s travel speed v is the same as the single relay deployment time T, the relay deployment of the three schemes. The time is mainly determined by the number of relay deployments.


## 4.2.3. Robustness of the Network

The experimental design is to evaluate the robustness of the network after the network recovery by judging the number of remaining nodes in the network. As shown in Figure9(a), the number of remaining nodes in the three recovery schemes decreases when the damage to the network increases after secondary injury. In Figure 9(b), when the degree of secondary damage is certain, the number of remaining nodes in the three schemes increases with increasing number of islands, because the increase in the number of islands increases the total number of nodes in the network. Regardless of the degree of damage or the number of islands, the number of remaining nodes in the LPRMA scheme is higher than in the existing two schemes, which is due to the multianchor connection method in the LPRMA scheme. When the restored network suffers secondary damage, it is likely to damage the communication anchor points used to connect with other isolated islands. Most of the existing restoration schemes use a single-anchor point connection mode. Under this connection mode, once the communication anchor is damaged, the entire island will lose connection to other islands. The multianchor connection method adopted by the LPRMA scheme will not lose contact with all other islands due to the damage to one anchor, which makes the LPRMA scheme better than the existing DR-ACO and DAAP schemes in terms of restoring the number of nodes remaining in the network after secondary damage. Thus, the restoration scheme proposed in this paper has higher network robustness.Figure 9
Comparison of the number of remaining nodes.
(a)(b)


## 4.2.4. Transaction Processing Efficiency

After the network connection is restored, the efficiency of transaction processing in the network is also very important, which affects the level of network delay. This paper evaluates the performance of three connectivity schemes in network transaction processing using the transaction processing efficiency indexPEI and processing delay Z. Among them, the higher the PEI, the higher the transaction processing efficiency.
(24)PEI=1NDT−DTPN.DT is the degree of transaction sequence, which represents the number of islands involved in a transaction, and PN is the number of valid paths for transaction processing. As shown in Figure 10(a), with the increase in the number of islands, the PEI of the three schemes gradually decreases, because the increase in the number of islands intensifies the number of transactions in the network and increases the complexity of transaction processing, thus reducing the PEI. However, in different numbers of islands, the PEI of LPRMA is always higher than the other two schemes, which is because the multianchor connection mode of LPRMA will generate more short paths with the increase of the number of islands, the increase of short paths will increase the PN of LPRMA transaction processing, and thus the PEI will be higher. As shown in Figure 10(b), due to the gradual decrease of PEI, the transaction processing delay Z of the three schemes increases with the increase of the number of islands. Because LPRMA is more efficient for transaction processing, the processing delay of LPRMA is lower than the other two options.Figure 10
Comparison of transaction efficiency.
(a)(b)


## 5. Conclusions

This paper proposes a solution (LPRMA) for solving the multi-island connectivity problem in wireless sensor networks. In the process of restoring multi-island connectivity, the scheme follows two principles. The first is the principle of local area priority restoration. By adopting the idea of divide and conquer, the entire network is first divided into multiple local area networks, and each local area network is connected and restored separately, and then the connectivity between local area networks is restored. This restoration principle improves the global network. The recovery efficiency of connectivity enhances the performance of interrupted transaction processing after network recovery. Secondly, based on the connection principle of the optimal anchor point, the connection mode of the optimal anchor point is adopted for both the connectivity restoration within the local area network and the connectivity restoration between the local area networks, thus reducing the connection recovery cost, enhancing the network robustness and prolonging the network life. Finally, the effectiveness and advantages of the LPRMA scheme in terms of connection restoration cost, network robustness and connection restoration delay are verified through numerous simulation experiments.



---

*Source: 6800847-2022-12-24.xml*