Adaptive Topology Reconfiguration from an Actor Failure in Wireless Sensor-Actor Networks

Abstract

Wireless Sensor-Actor Network (WSAN) usually consists of numerous sensor nodes and fewer actors, and the connectivity of interactors is critical to the whole network. Due to the hash deployed environments and limited energy supply, actor nodes may fail and impact the performance of the whole network. Since the failure of a cut-vertex will disrupt connectivity and divide the topology into disjoint segments, most of the previous researches have already considered this scenario. However, the impact of an abruptly actor's failure to the network will be far more than that. This paper focuses on the problem of an actor's failure and gives a more comprehensive view of the faulty actor, that is, not only restricts to the cut-vertex. Length-Aware Topology Reconfiguration Algorithm (LTRA) is proposed on the basis of two vital definitions named as length impact index (LII) and vertex cut set (VCS). LTRA is a hybrid method which selects a best candidate for each actor (if it has) and then initiates in a distributed manner. Main idea of this approach is that candidate will move to replace the faulty one once the failure occurs. In addition, the candidate is selected from one-hop neighbors of each actor. Finally, performance of LTRA is validated by extensive simulation experiments.

1. Introduction

Nowadays, tremendous applications of Wireless Sensor-Actor Networks (WSANs) have been drawing the increasing attention of many researchers [1], such as urban search and rescue, battlefield surveillance, forest fire detection and containment, and underwater surveillance. A typical WSAN is a network with the hierarchical structure, which is composed of lots of sensor nodes and fewer actors. Sensor nodes can probe the ambient conditions and transmit the collected data to one or multiple actors for further processing and transmitting. Actors are movable nodes and primary in charge of collecting data from sensors.

Generally, actors are utilized to connect the sink node and sensing dots. Connectivity would be the bottommost requirement to ensure the availability of a network; thus the connectivity of interactors network is essential. That is, actors should keep connectivity with others all the time. Nevertheless, due to the hash deployed environments and limited energy supply (mostly powered by battery), actors are prone to failure. As we all know that, the failures of some critical actors will affect the performance of the whole network. For instance, if some cut-vertexes are out of service, connectivity could not be maintained any more. Most of the existing approaches only considered the failure of an cut-vertex, such as DARA [2], PDARA [3], PCR [4], VCR [5], DCR [6], and AFDR [7].

Indeed, once a cut-vertex fails, the interactors interaction may cease. However, the impact of an abruptly actor failure to the network will be far more than that. For example, given a circle graph with some actors on the arc and a single actor at the center, the central actor can connect to other actors directly. Although this central actor is not a cut-vertex, the absence of it will prolong the link length between others observably. On the other hand, there is another kind of actors whose failures may disturb the robustness of interactors interaction. More specifically, those actors are not cut-vertexes in themselves, but their failures generate new cut-vertexes in the network. These two special cases will be discussed in Section 4. In addition, since we focus on the interactors graph, we use the actor and node alternatively to simplify the description hereafter.

This paper investigates the tolerance of the actor failure in WSANs from a general perspective. Similar to some of the previous researches, here we focus on the problem that only single actor has failed, and we primary concern the following two categories of actors. Firstly, those actors whose failures prolong the link length among other actors, such as cut-vertexes. Secondly, those actors whose failures generate new cut-vertex which may effect the robustness and cause cascaded failures in WSANs. Here, we regard the recovery issue as an optimization problem when an actor is failed and prefer utilizing an adjacent actor to replace the faulty one. In this study, our contributions can be summarized as the following four aspects.

• (i)

We give a more comprehensive view on the disabled actor and indicate that the failed node will not only be restricted to the cut-vertex. Then we do some analysis of the two categories of actors we will concern.

(ii)

Dealing with actors belong to the first category, we propose a novel parameter named as length impact index (LII) which can reflect the impact of the link length between other actors when an actor is out of service.

(iii)

Dealing with actors belong to the second category, we formally define the vertex cut set (VCS) and propose a method to judge whether the failed actor belongs to BVCS (Binary-VCS) or not. One faulty cannot be ignored if the failed one is in BVCS. In addition, when we choose the candidate of each actor, the chosen one also needs to be judged.

(iv)

We propose a novel algorithm named LTRA (Length-Aware Topology Reconfiguration Algorithm) to handle the problem of an actor failure; we also validate its correctness and reliability via abundant simulations.

The rest of this paper is organized as follows. Related work is reviewed in Section 2. In Section 3, we describe the considered system model and highlight the implications of actors failure on network topology. Then, two categories of actors are investigated, and the LTRA is also proposed in Section 4. Further, the algorithm is analyzed in Section 5. Validation experiments and performance analysis are provided in Section 6. Finally, we give a conclusion of this paper in Section 7.

2. Related Work

In this section, we will review the related work briefly. In recent years, the issue of connectivity restoration has been well studied in Wireless Sensor Networks (WSNs) and WSANs; many studies focus on restoring the broken WSANs network caused by single actor failure, which is summarized in [9, 10]. Generally, according to the functional principle, existing schemes on tolerating node failure can be classified into two primary categories: proactive and reactive solutions.

Proactive solutions rely on the availability of redundant resources that can make up for the lost node(s). A significant concept is the k-connectivity, which means that there are at least k disjoint paths between any pair of nodes, and hence it can tolerate the failure of $k-\mathrm{1}$ members. For example, 2CRNDC [11] strives to deploy minimum relay nodes to ensure the whole network to be $\mathrm{2}$ -connected, which can still maintain the connectivity when one of the nodes is out of service. However, proactive solutions for connectivity restoration are not suitable for WSANs since the actors are quite expensive and hard to be deployed when compared with sensors, and therefore the placement of redundant actors is not practical.

Different from the proactive solutions, reactive approaches initiate the recovery process once the failure is detected. One of the most popular reactive methods is exploiting node’ repositioning to repair a partitioned WSAN and it has been deemed as an effective strategy in most of recent literatures [2–7, 12]. The main idea of these approaches is to replace the failed node with one of its neighbors or move its neighbors inward to autonomously mend damaged topology in the vicinity. For instance, DARA [2] pursues a coordinated multiactor relocation in order to reestablish communication links among disjoint actors. That is, once an actor fails, DARA will choose the best backup node move to replace the faulty one. The candidate among neighbors of the failed node is selected based on its degree, distance between the failed node and the nodes ID, respectively. Similar to our LTRA, DARA also considers the scenario that only one actor has failed. Nevertheless, DARA only focuses on the failure of cut-vertex, which may still ignore some critical nodes like mentioned before. In addition, DARA requires that all the actors need to aware 2-hop neighbors’ information to identify whether an actor is a cut-vertex or not. Moreover, Akkaya et al. [3] propose a connected dominating set (CDS) based algorithm named as PDARA. The approach was executed gradually; the first step is to identify whether the failure of a node causes partitioning or not; once the partitioning happens, the connectivity restoration process needs to be initiated with its dominatee or one of the neighboring dominators. The overall goal is to localize the scope of the recovery and minimize the movement overhead imposed on the involved actors.

As discussed above, both DARA and PDARA utilize one of the neighboring nodes to replace the failed one. However, they do not evaluate the absence of the candidate, if the movement damages the connectivity, the restoration process will work in the iteration pattern until the whole network is connected. Thus, cascaded movement is applied to sustain network connectivity. In this paper, cascaded movement is utilized to deal with several special cases. Unlike the DARA and PDARA in which the candidate is required to move to the location of failed actor, another notable work on connectivity restoration named as RIM is proposed by Younis et al. [12]. They have avoided the position of failed node and proposed a local recovery process by relocating the neighbors of the faulty node. The main idea of RIM is that each adjacent node of the failed one moves “ $R/2$ ” towards it and other nodes need to move inward in a cascaded manner until they can be reconnected with each other. In addition, RIM aims at the failure of any node and requires one-hop neighbors’ information. However, considering the reduction of distance that the individual nodes have to travel during the recovery, RIM may cause the movement of too many actors. Recently, two novel methods named as DCR and AFDR are proposed on the basis of RIM [6, 7]; both of them are reactive strategies. However, they have still investigated the failure of cut-vertex and concerned some other optimization objectives.

3. System Model and Problem Statement

We consider a WSAN which is composed by sensors, actors, and a single sink node. The moveable actors are operated as cluster heads or relay nodes to transmit information gathered by sensors, and hence actors are more critical to the whole network. This paper only investigates the impact of single actor failure and analyzes the influence through two categories of actors. It is assumed that the sensors are stationary; they could reach the actors directly or over multihop paths. Since the scope of sensors is pretty large, we also assume that there must be lots of paths to provide the connectivity between sensors and actors, and those paths will not be affected if some actors have to change their positions. We are also assuming that actors are powered by limited batteries, and all have same communication range R. Such an assumption is usually valid since actors will be homogeneous in most applications of WSANs. Moreover, upon deployment, actors are assumed to discover each other and form a connected interactors network using some of the existing strategies such as C2AP [13].

As we all know that, the loss of an actor may cause serious or nonserious break to the performance of a network according to its position. Different from most of previous researches, we primary concern two categories of actors failures as we have explained in the introduction. The failure of an actor in the first category will affect link length between others. For instance, in Figure 1(a), the failure of $A_{\mathrm{5}}$ does not disturb the whole connectivity, but link length between $A_{\mathrm{4}}$ and $A_{\mathrm{6}}$ increases from 2 to 4. Obviously, the absence of such an actor could impact the quality of connectivity. Naturally, since failure of cut-vertexes will extend link length between other actors to ∞, cut-vertexes are summarized into such a set, and we name the set of these actors as category 1 for simplicity.

Figure 1

(a) Illustration of first category of actors in simple interactor network. Nodes $A_{\mathrm{4}}$ , $A_{\mathrm{11}}$ , and $A_{\mathrm{12}}$ are cut-vertexes; the failure of other nodes like $A_{\mathrm{5}}$ still impact the link length. (b) Illustration of second category of actors in simple interactor network. Nodes A and B are not cut-vertexes, but simultaneous failures of them will divide the network.

On the other hand, once the second category of actors has failed, robustness of interactor network should be affected. Let us consider two specific nodes A and B in Figure 1(b). Although they are not cut-vertexes, simultaneous failure of these two nodes could even separate the topology into two isolated blocks. We could observe that if node A has failed, node B will become a new cut-vertex, vice versa. Since the new generated cut-vertex may be out of service quickly under the constraint of much heavier workload, the failure of such an actor will impact the robustness of whole interactor network seriously. Similarly, we temporarily name the set of those actors like A and B as category 2.

In this study, we assume that no simultaneous nodes failure will happen, and all the transmission is on the basis of an ideal signal propagation model. In addition, the presentation of LTRA focuses on the algorithmic part of the self-restoration without considering the link layer issues.

4. Length-Aware Topology Restoration Algorithm

LTRA is a self-healing algorithm to reduce the impact caused by the failure of an actor, no matter whether the connectivity is hold or not. Actually, the algorithm we proposed here initiates only when the failed actor belongs to those two categories as we described above. Thus, the most important thing is to distinguish which type of the lost one belongs to. Since we should reduce the influence of initial failure via topology reconfiguration, in this section, we formally give a definition of LII, which could reflect the significance of each actor to the network topology. In addition, we also propose a crucial definition named as vertex cut set (VCS) refers to actors in category 2.

4.1. Definition of LII

Before analyzing how LTRA works, it is important to point out the impact of node's failure to the topology. As shown in Figure 1(a), assuming node $A_{\mathrm{5}}$ has failed, obviously, this failure does not hinder whole connectivity, and hence the foregoing algorithms such as DARA et al. ignore this scenario. However, when the position of $A_{\mathrm{5}}$ is replaced by $A_{\mathrm{6}}$ , the impact of its failure to the topology seems to be reduced. Thus, how to estimate and quantify the significance of each actor to interactor network connectivity becomes a critical issue. Therefore, LII as a feature of each actor is proposed to measure the influence of its failure.

The main idea of LII is to notarize the length of the shortest path between any pair of actors in the interactor network. For example, although the failure of node $A_{\mathrm{5}}$ increases the length of the shortest path between node $A_{\mathrm{4}}$ and $A_{\mathrm{6}}$ , it will not touch the shortest path from $A_{\mathrm{4}}$ to $A_{\mathrm{11}}$ . Supposing that the initial network is connected and composed of N actors, we formally define the LII of node i as follows:

$$\begin{array}{cc}& \text{LI}{\text{I}}_i=\frac{{\sum }_{j,k=\mathrm{1};j,k\ne i;j<k}^N{L}_{jk}^{*}}{{\sum }_{j,k=\mathrm{1};j,k\ne i;j<k}^N‍L_{jk}}-\mathrm{1},\end{array}$$

(1)

where $L_{jk}$ represents the shortest length from node j to k in the original graph, while $L_{jk}^{*}$ expresses the shortest length between node j and k after the failure of node i. Basically, LII of an actor can reflect the impact of its failure to the average length of the interactors network, and (1) is utilized to measure this variation. For instance, in Figure 1(a), if we calculate the $\text{LI}{\text{I}}_{\mathrm{5}}$ , then $L_{\mathrm{46}}=\mathrm{2}$ and $L_{\mathrm{46}}^{*}=\mathrm{4}$ , while $L_{\mathrm{2,11}}=L_{\mathrm{2,11}}^{*}=\mathrm{2}$ . Since we consider the network is undirected, $L_{jk}$ is assumed to be equal to $L_{kj}$ . Absolutely, LIIs of all the cut-vertexes are ∞, and LIIs of those leaf nodes such as $A_{\mathrm{10}}$ , $A_{\mathrm{13}}$ , and $A_{\mathrm{14}}$ are $\mathrm{0}$ . However, there is another set of nodes such as $A_{\mathrm{5}}$ , $A_{\mathrm{7}}$ , whose LII is a nonzero constant. According to (1), we could obtain that the LIIs of them are 0.082 and 0.012, respectively.

It is clearly that if node i is on the shortest path from node j to k, the failure of i will increase the link length between j and k. Actually, the LII of each actor is the variation of average link length of interactors network before and after the failure of that actor. In addition, the shortest path can be achieved through the route discovery strategies in the existing works, for example, the deep-first-search (DFS) algorithms.

Lemma 1.

If $LI{I}_i\ne 0$ , $LI{I}_i\ne \infty$ , actor i must be in a loop with at least 5 nodes.

Proof.

At first, we could exclude leaf nodes and cut-vertexes according to the assumption. Actually, if a node is on the shortest path between arbitrary pair of nodes and it is not a cut-vertex, there must be other routes to link these two nodes. As shown in Figure 2(a), node O is a intermediate node from P to Q. Then, let us take a view of Figure 2(b), in which $POQ$ and $PRQ$ are two disjoint paths. Obviously, no matter which one of nodes R or O fails, it will take 2 hops from node P to Q. By the way, these four nodes P, Q, O, and R form a four-membered ring. This is the simplest case that any node's failure will not effect the link length between others. However, the failure of any node in Figure 2(c) will prolong the average length of the whole graph. This is a five-membered ring, and any pair of nodes has two paths with hops 2 and 3, respectively. Thus, no matter which node has failed, link length between other nodes will be 3. For example, there are two paths $PSOQ$ , $PRQ$ between nodes P and Q; if node R fails, only one path $PSOQ$ with length 3 remains. Therefore, given a n-membered ring, the link length between neighbors of the faulty node will be $n-\mathrm{2}$ , and Lemma 1 would be naturally formed in terms of our analysis.

Figure 2

(a) Illustration of several paths between P and Q, any two paths will form a loop. (b) Illustration of four-membered ring. (c) Illustration of five-membered ring and link length between P and Q will be 3 if R is failed.

In large scale WSANs, actors are prone to form loops with at least 5 nodes, and hence the failures of actors in those loops are tended to appear and need to be taken into account.

4.2. Dealing with Faulty Actor in Category 1

We assume that once original topology has formed, the LII of each actor is determinate. Each actor needs to compare the LII with its one-hop neighbors and choose the one with smallest LII as its best-candidate (backup). However, if an actor has the smallest LII when comparing to its neighbors, we temporarily note that it has no candidate. In addition, if there are many candidates with the same minimum LII, we could choose the most suitable one among them through some extra parameters, such as the nodes degree and their distance to the faulty node. To simplify the analysis, we use the distance as the final judge criterion, if the actor gets the minimum distance to the failed node among those candidates whose LIIs are all minimum, it would be the best one to replace the faulty node. Precisely, a shorter distance to the failed node could save more energy in the movement of replace process and hence prolong the life time of the relocated actor.

Once a failure occurs, the candidate will move and replace the faulty one. Thus, every actor also needs to aware of the backup of itself while the whole network initiates.

4.3. Definition of VCS

Considering an undirected graph $G=〈V,E〉$ , $\varphi \ne V^{\prime }\subset V$ is said to be a VCS of G which must satisfy the following two conditions:

$$\begin{array}{cc}& p\left(G-V^{\prime }\right)>p\left(G\right),\\ p\left(G-V^{\mathrm{\prime \prime }}\right)=p\left(G\right),\hspace{1em}\forall V^{\mathrm{\prime \prime }}\subset V^{\prime }.\end{array}$$

(2)

In (2), V and E represent the vertex and edge set. $V^{\prime }$ is a subset of V, and $V^{\mathrm{\prime \prime }}$ is a subset of $V^{\prime }$ . Moreover, $p(G)$ is the number of connected components in the original graph G, $p(G-V^{\prime })$ and $p(G-V^{\mathrm{\prime \prime }})$ denote the number of connected components in graph G without vertexes sets $V^{\prime }$ and $V^{\mathrm{\prime \prime }}$ , respectively. For example, the original graph G in Figure 1(a) is connected, if we set $V^{\prime }=A_{\mathrm{5}},A_{\mathrm{7}}$ and $V^{\mathrm{\prime \prime }}=A_{\mathrm{5}}$ , then the following parameters will be obtained:

$$\begin{array}{cc}& p\left(G\right)=\mathrm{1},\\ p(G-V^{\prime })=\mathrm{2},\\ p(G-V^{\mathrm{\prime \prime }})=\mathrm{1}.\end{array}$$

(3)

It is obvious that no matter which one of $A_{\mathrm{5}}$ and $A_{\mathrm{7}}$ fails, the whole topology is also connected. However, simultaneous failure of them will divide the network; then set $V^{\prime }=(A_{\mathrm{5}},A_{\mathrm{7}})$ is a VCS of the network in Figure 1(a). Similarly, actors A and B form a VCS of the interactors network in Figure 1(b). Given a determinate topology, there could be numerous VCSs, and the sizes of them are also various. For instance, cut-vertexes are VCSs with size 1, and they belong to category 1. On the other hand, those actors in category 2 belong to VCSs with size 2. And hence, when one of them has failed, new cut-vertex will be generated. It is worth noting that we do not focus on actors in VCSs with size 3 or more, since there will be at least two routes between other actors when the failure occurs.

4.4. Dealing with Faulty Actor in Category 2

In this section, we focus on the failure of actors in category 2; this kind of actors’ failure does not destroy the connectivity directly. More often than not, they will lead to cascaded failure, which means that some other actors may be out of service due to heavier workload and faster energy exhaustion. Failure of an actor in category 2 generates a new cut-vertex; that is, there is a one-to-one correspondence between such a failure and generation. And now the most pressing problem is how to identify those actors.

Lemma 2.

Actors in category 2 all belong to Binary-VCS (BVCS).

Proof.

According to the definition of VCS, Lemma 2 is clearly established.

There is a feasible solution to gain VCSs [14], in which authors tried to judge whether the submatrix of adjacent matrix is a quasidiagonal matrix with the elimination of some nodes. If it is true, the removed set of nodes is a VCS of the given graph. However, it will cause too much computation overhead to determine the attribute of each submatrix and may not suit our method. Therefore, in this section, we propose a strategy to find all the actors in category 2 based on the definition of VCS.

Lemma 3.

Given a certain actor-actor connected graph G, if node A failed and the number of cut-vertexes in graph $G^{\prime }$ satisfies the following qualification, then node A belongs to category 2:

$$\begin{array}{cc}& \left|C\left(G^{\prime }\right)\right|=\left|C\left(G\right)\right|+\mathrm{1},\end{array}$$

(4)

where $G^{\prime }$ denotes the connected graph without node A and $C(G)$ and $C(G^{\prime })$ represent the set of cut-vertexes in G and $G^{\prime }$ . Similarly, $\left|C(G)\right|$ and $\left|C(G^{\prime })\right|$ represent the number of cut-vertexes in each graph. Since the failure of a node in category 2 will generate a new cut-vertex, Lemma 3 would be naturally formed.

Lemma 4.

If node $B=C(G^{\prime })-C(G)$ , then node B belongs to category 2.

Proof.

From Lemma 2, we know that all the actors in category 2 come in pairs. Combining this observation with Lemma 3, Lemma 4 would be naturally formed. Thus, once the interactors topology is confirmed, steps to find out all the actors in category 2 can be represented as Algorithm 1.

Algorithm 1: How to find out all the actors that belong to category 2.

(1) Given an inter-actors graph G, and $$N(G)$$ denotes the set of nodes.

   Then, obtain it's cut-vertex set which named as $$C(G)$$ ;

(2) Assuming leaf nodes in set L, thus all the actors belong to category 2 are

  in an alternative set $$N^{\prime }=N(G)-C(G)-L$$ ;

(3) For every node $$i\in N^{\prime }$$ , do

(4)  Calculate the new cut-vertex set $$C(G^{\prime })$$ of graph $$G^{\prime }$$ , where $$N(G^{\prime })=N(G)-i$$ ;

(5)  if $$\left|C(G^{\prime })\right|=\left|C(G)\right|+\mathrm{1}$$

(6)   actor i belongs to category 2, and node

     $$j=C(G^{\prime })-C(G)$$ as well;

(7)  end if

(8) end for

Actually, despite those cut-vertexes and leaf nodes, the scale of nodes in category 2 is limited. When the network launches, each actor should aware whether it belongs to category 2 or not. For simplicity, we name the set of actors in category 2 as BVCS.

4.5. Implement of LTRA

LTRA executes a partial topological restoration when an actor is out of service. Actors will periodically send heartbeat messages to their neighbors to ensure that they are functional and can report changes to the one-hop neighbors. Therefore, missing heartbeat messages can be used to detect the failure of actors. An actor is purported to failure if its neighbors lose the heartbeat message for two sampling periods. According to the analyses above, we find that the most critical step of LTRA is to select the candidate. Obviously, only actors in category 1 and BVCS are necessary to be concerned.

When the network initiates, sink node gathers the information of each actor and finds candidates for those actors who need to be concerned and then notifies the result through broadcasting. Once a failure is detected in the neighborhood, if the faulty actor has a backup node, the candidate will move to replace it. Synthesizing actors in category 1 and BVCS, the major steps of LTRA are expressed in Algorithm 2.

Algorithm 2: Length-Aware Topology Reconfiguration Algorithm.

(1) Given an inter-actors graph, calculate the LII of each actor and judge

   whether actors belong to category 2 or not;

(2) If node $$i\in \text{BVCS}$$ ;

(3)   The adjacent node $$j\notin \text{BVCS}$$ with the

      minimum $$\text{LI}{\text{I}}_i$$ will be selected as the

      backup node of i;

(4)   if some candidates have the same LII

(5)    The actor which is hithermost will be

       selected;

(6)   end if

(7) else

(8)   if $$\text{LI}{\text{I}}_i$$ is the smaller than any if its

      neighbors’

(9)    This failure would be ignored;

(10)  else

(11)   The adjacent node $$j\notin \text{BVCS}$$ with

    the minimum $$\text{LI}{\text{I}}_i$$ will be selected

    as the backup node of i;

(12)  end if

(13) end if

(14) Every actor need to communicate with its backup node and

     confirm the relationship with it;

(15) When the failure appears, backup of the failed actor will move to replace it,

     and the performance of inter-actors network holds;

Primitively, backup node of each actor is elected (if it has) according to LTRA, the codes from line 1 to line 13 have represented this process. When the failure happens, the candidate only needs to replace the failed actor. For example, actor $A_{\mathrm{5}}$ in Figure 1(a) belongs to BVCS, actors $A_{\mathrm{4}}$ , $A_{\mathrm{7}}$ , $A_{\mathrm{11}}$ , and $A_{\mathrm{6}}$ are one-hop neighbors of it, and the LIIs that belong to them are ∞, 0.012, ∞, and 0, respectively. Since $A_{\mathrm{7}}\in \text{BVCS}$ and $\text{LI}{\text{I}}_{\mathrm{7}}>\text{LI}{\text{I}}_{\mathrm{6}}$ , actor $A_{\mathrm{6}}$ is the best candidate of $A_{\mathrm{5}}$ . If $A_{\mathrm{5}}$ fails, $A_{\mathrm{6}}$ moves to replace it and the movement breaks down the link between $A_{\mathrm{6}}$ and $A_{\mathrm{7}}$ ; then the fixed network is expressed in Figure 3.

Figure 3

How the LTRA works after the failure of node $A_{\mathrm{5}}$ in the connected interactor topology of Figure 1(a).

4.6. Rare Cases of Restoration

Although LTRA can deal with the most of situations, there are still few rare cases that need to be concerned. One of the most classical scenarios is that one-hop neighbors of the failed actor are all cut-vertexes; movement of anyone will disrupt the connectivity. Thus, cascaded movement is needed. The selection of candidate of faulty node is also according to the factor of distance. When the cut-vertex starts to move, the backup of it initiates as well. In addition, the scenario that neighbors of the failed actor are all in BVCS also needs cascaded movement. Next, four basic cases are represented in Figure 4.

Figure 4

Illustration of four rare cases.

According to the types of faulty actor and its neighbors, we name these four cases as C-C, C-B, B-B, and B-C, respectively. In (a), supposing node 3 has failed, then node 4 moves to replace 3, and node 5 moves to replace 4 in a cascaded manner. This case is named as C-C, because of the faulty node and its neighbors are cut-vertexes. Then, if node 7 in (b) is disabled, nodes move in a cascaded manner as indicated by the arrows. Since node 7 is a cut-vertex and its one-hop neighbors belong to BVCS, this case is named as C-B. Similarly, (c) denotes the case of B-B, in which the failed node 5 belongs to BVCS and its neighbors are also in it. (d) represents the case of B-C; if node 4 has failed, its neighbors node 3 and node 6 are cut-vertexes. Since $d_{\mathrm{3,4}}<d_{\mathrm{6,4}}$ , node 3 moves to the position of node 4, and node 2 moves to replace node 3. Additionally, these movements of backup nodes initiate almost at the same time. Namely, once the backup node of faulty node starts to move, it sends a message to notify its own candidate; then the candidate moves immediately to reduce the time of reconfiguration.

Actually, those typical cases are basically referred to as two issues: the first one is the failed node which must be replaced and the second is the backup of faulty node which is also critical. Although it is hard to deal with these cases, the probabilities of their occurrences are very small in actual network.

5. Algorithm Analysis

In this section, we will do some property analysis of our algorithm. Generally, the major step of LTRA is how to find a best candidate of each actor (if it has). This is a hybrid method consisting of two aspects: backup selection and replacement initiation. Now, we give a brief comparison of LTRA with some previous algorithms which refer to three parameters: type of faulty node, information maintained by node, and the working pattern. Result is shown in Table 1.

Table 1

Comparison with previous algorithms.

Algorithms	Node	Information	Pattern
DARA	Cut-vertex	2-hop	Reactive
ILP [8]	Any	Global	Reactive
PCR	Cut-vertex	1-hop	Hybrid
VCR	Cut-vertex	1-hop	Reactive
CRR	Cut-vertex	3-hop	Reactive
RIM	Any one	1-hop	Reactive
PDARA	Cut-vertex	2-hop	Proactive
DCR	Cut-vertex	1-hop	Reactive
AFDR	Cut-vertex	2-hop	Reactive
LTRA	Category 1 and category 2	1-hop	Hybrid

In our algorithm, the candidate selection process needs to compare the LII of each actor with its one-hop neighbors, and everyone should also know the category of its adjacent neighbors. Thus, LTRA only requires that each actor maintains the information of one-hop neighbors. Further, we also discuss the message complexity of LTRA.

Theorem 5.

The message complexity of LTRA is $O(n^{\mathrm{2}})$ , where n is the number of actors.

Proof.

The calculation of LII depends on information gained by sink node in which the communication overhead of whole network is $O(n^{\mathrm{2}})$ . Then sink node should notify the property (i.e., which category and LII) and backup information to each actor, which spans the whole network with n messages. In addition, actors need to confirm the relationship between their candidates (if have); the two basic steps of transmission and reception need $\mathrm{2}·k$ messages, where k denotes the number of actors in category 1 and category 2. Moreover, if the cascaded movement initiates, this process needs $\mathrm{2}·l$ messages as well, where l denotes the total number of nodes that need to move. Therefore, the message complexity of LTRA is $O(n^{\mathrm{2}})$ .

Remark 6.

Considering the number of actors is limited, the message complexity of LTRA would be acceptable in most cases. As we know that the message complexity of DARA and RIM is $O(n)$ [2, 12], the message overhead of LTRA is heavier than theirs, but LTRA could deal with more general situations which are not restricted to the failures of cut-vertexes. Moreover, most of the burden of communication is utilized to find out the candidate of each actor and this process would be accomplished once the interactors network is formed. And hence, the heavier message overhead will not impact the regular communication.

Theorem 7.

The maximum travel distance of a node in LTRA is “R,” where R is the actor radio range.

Proof.

In LTRA, we adopt an adjacent neighbor to replace the faulty actor; even in the rare cascaded movement, every actor is replaced by its backup. And hence, the maximum travel distance of a node in LTRA is “R.”

6. Performance Evaluation

6.1. Simulation Settings

In this section, we wish to study how LTRA affects the overall performance of the interactors network numerically when the failure of an actor occurs. We evaluate the performance of LTRA by comparing them with two foregoing approaches named as the distributed actor recovery algorithm (DARA) [2] and the recovery through inward motion (RIM) [12]. Without loss of generality, we suppose that the LTRA starts from a random deployed graph. As explained above, DARA pursues to minimize the total distance traveled by the involved actors in order to limit the overhead incurred by the movement and chooses the candidates based on the node degree and the proximity to the failed actor. Meanwhile, RIM opts to reduce the distance of the individual nodes which have to travel by scheduling that all the adjacent neighbors need to move toward the faulty actor until $R/\mathrm{2}$ away from it (R denotes the communication range of the actor). Nevertheless, LTRA not only concerns the number of involved candidates but also pays attention to the total travel distance of them.

The simulations are performed on the Matlab 2010(b), and simulation parameters are summarized in Table 2. In addition, we set the actors which are randomly distributed and the original interactors network is also assumed to be connected. Since LTRA opts to minimize the number of actors involved into relocation process and limit the travel distance by electing the nearest neighbor, the following metrics are utilized to measure the performance of LTRA in terms of recovery (optimization) overhead.

• (1)

The number of relocated nodes indicates the number of nodes involved in the relocation process. This metric could reflect the scope of topology changes during the execution of LTRA and assess the real-time performance of LTRA.

(2)

Total travel distance of relocated nodes implies the total travel distance of those which need moving to replace the failed actor. Obviously, longer travel distance will lead to lager delay due to the limited moving velocity of actors. Furthermore, since the traveling will cause significant energy consumption, total travel distance could impact the residual energy of relocated actors which relates to the network lifetime closely. Thus, total travel distance of relocated nodes is a critical metric to measure the performance of LTRA.

Table 2

Simulation parameters.

Simulation parameters	Value
Target region	500 m × 500 m
Number of actors	50 → 80
Communication range	$$\text{100\hspace{0.17em}m}$$ → $$\text{160}\hspace{0.17em}\text{m}$$

Moreover, with a view to the random failure model, we firstly investigate the possibility that the failed actor belongs to which category. Most of the previous literatures focus on the failure of cut-vertex; however, some other cases need to be considered are ignored, that is, other actors in category 1 and BVCS. Therefore, the probability distribution of failed actor is obtained among four varieties.

6.2. Numerical Results

Firstly, we do some simulations to see the probability distribution of the faulty actor under the random failure model. Simulation results are shown in Figure 5; the number of deployed nodes in two configurations is 50 and 80, respectively. There are four categories of the failure named as I, II, cut-vertex, and BVCS, in which I denotes the set of actors with zero LIIs and II represents those actors in category 1 except cut-vertexes. It is clear that the failures of cut-vertexes are only a small part of the whole scenarios, and more than 50% of the failures occur with the impact to the average length of interactors network. In addition, failures of actors in BVCS also exist; they need to be taken into consideration although the scope is limited. In Figure 5(b), we observe that the probability of failures in category II becomes larger along with the increase of scale of network. Since the more number of actors in a fixed area will lead the network to become more intense and hence more loops between actors are formed, the scale of actors in category 1 (without cut-vertexes) is naturally bigger.

Figure 5

(a) Probability distribution of an actor failure with 50 initial actors. (b) Probability distribution of an actor failure with 80 initial actors.

Then we compare the performance of the foregoing two metrics between LTRA, DARA, and RIM. Generally, all the evaluation results are averaged based on 20 different runs. Figure 6(a) compares the total distance moved by all the relocated actors of LTRA, RIM, and DARA. Figure 6(b) expresses the impact of network size (i.e., the number of deployed actors) on the numbers of relocated actors under these three algorithms. This simulation scenario is based on a fixed communication range $R=\mathrm{100}$  m. According to Figure 6, it is clear to see that LTRA outperforms RIM and DARA in terms of both total distance traveled and the number of moved actors. When the network size is growing larger, the total travel distance of relocated actors achieved by LTRA becomes smaller. It indicates that LTRA works even better in the dense network due to the decreased interval between actors. In Figure 6(b), we can see that the self-healing process under LTRA and DARA causes very small changes to the topology, and the number of relocated actors is almost 1. Although the scope of relocated actors of LTRA and DARA is quite approximate, LTRA is more proper due to the consideration of distance parameter rather than the node degree in DARA.

Figure 6

(a) Comparison of the total distance traveled by actors under LTRA, RIM, and DARA, where the network size is changing and the communication range is fixed as $R=\mathrm{100}$  m. (b) Effect of varying network size on the number of relocated actors with fixed network size.

Further, we valuate the impact of varying communication range on the total traveled distance and number of relocated actors. The number of randomly deployed actors is fixed as 50. Intuitively, smaller R indicates smaller distance between actors; all of the LTRA, DARA, and RIM perform well when R is set as 100 m. However, the overhead of them will keep increasing with R. In fact, as shown in Figure 7(a), the total traveled distance under LTRA is increasing with the communication range slowly. Moreover, since LTRA only needs moving one candidate to replace the failed actor in most cases, the total travel distance will be smaller than the communication range. Figure 7(b) shows the number of relocated actors altering with the communication ranges; similar to the graph shown in Figure 6(b), LTRA could accomplish the self-healing process with minimum involved actors.

Figure 7

(a) Comparison of the total distance traveled by actors under varying communication range with fixed network size. (b) Effect of varying communication range on the number of relocated actors with fixed network size.

Therefore, LTRA is able to reduce the impact of actor failure to the interactors network, and it outperforms the DARA; RIM refers to the following metrics: number of relocated nodes and total travel distance of relocated nodes.

7. Conclusion

The problem of topology reconfiguration from an actor failure in Wireless Sensor-Actor Network is studied in this paper. We have divided the failure of an actor into two major categories and presented two definitions named as LII and VCS. We have also proposed LTRA that engages to recover from a stochastic failure by topology reconfiguration in the partial region. Actually, LTRA could be regarded as an optimization approach because of the fact that the faulty actor will not restrict to cut-vertex. It should be noted that we only consider the failure of single actor and primary concern the interactors network in this study. Further, we will investigate the failure of multiple actors in our future work.