A Method to Analyze the Effectiveness of the Holes Healing Scheme in Wireless Sensor Network

Abstract

Because of the maturation of wireless technologies, the wireless sensor network has been used in various applications, especially in the environmental monitoring. After the nodes are deployed on the surveillance field, nodes will die due to the limited energy of the node or accidental events, inducing the coverage holes and the break of the transference path. To tackle this problem, researchers had proposed the rebuild network topology, such as adding Relay nodes. However, it costs a lot to build such a system. Therefore, in this paper, we would like to propose another method to tackle the dying nodes as well as the cost. Specifically, we propose a holes healing scheme. In order to check its feasibility, we use the analysis of mathematics to acquire the value of the parameters for the holes healing scheme. With the parameters, we could use the simulated result to prove the effectiveness of the scheme. The result shows that with the appropriate parameters we could confirm and extend the lifetime of WSN to infinity.

1. Introduction

Issues of the wireless sensor network (WSN) and related technologies have been studied for many years, the related technologies making advances such as the function and sensitivity of nodes. Also with the lowering the cost, the wireless sensor nodes are widely applied in various fields, especially in the environmental monitoring. There are two issues most discussed in WSN. One is the sensing coverage, and the other is the network connectivity. Since the wireless sensors are all battery-powered and constrained by limited energy, it is hard to recharge them in practice. Additionally, how to prolong the network lifetime is an important issue. This attracts a lot of attention on the topology control as well as discussion on how to reduce energy consumption of sensor nodes such as balancing energy consumptions among nodes to avoid some nodes overused result in early exhaustion of the precious energy.

The key issue of maintaining sensor network's topology depends on the limited energy of sensor nodes. In practice, all of the solutions proposed to solve the consumption problem about limited energy of sensor nodes use cluster architecture for data transmission route algorithm and adjust the nodes' active and sleep ratio and so on. In the applications of WSN, nodes are deployed in the surveillance field. This tends to cause the disconnection of network because of the nature of wireless and unexpected events. To keep the system in perpetual services, the replacement method for the failure nodes is a useful method. However, to use this method, we need to know the location of failure node. One article proposed the coverage holes detection algorithms [1], a self-monitoring mechanism for detecting node failures. Another [2], the BOND-CIP algorithm, used the bound nodes problem, which can accurately detect the network holes. In fact, there are other approaches to solve the disconnection problems. For example, the healing method proposed by one researcher used mobile nodes to recover the coverage holes [3]. Another similar approach used the Vector-based Hole Recovery algorithm to recover the holes, an approach using the overlapped nodes to move to the neighbor holes. Still another similar approach used the Relay nodes to rebuild the connect path on the destroyed area [4–6]. Although the Relay node has more energy and stronger computation capability, the energy consumption is still a problem, not to mention the accidental event. Therefore, we propose a method which uses robots to deploy a homogeneous node to replace a failure one. Specifically, we replace new nodes with proper adaptive parameters acquired through mathematics models and extensive simulations to prolong the lifetime of WSN.

The rest of this paper is organized as follows. In Section 2, we will discuss the related works, and in Section 3, we will discuss the system model. Then, in Section 4, we will provide the numerical and simulation results. Finally, we will present conclude remarks and some future research in Section 5.

2. Related Works

Coverage rate including the deployment methods is the most fundamental requirement in WSN, which affects the integrality of environmental data and network connectivity. The node deployment methods are either random or deterministic. For spacious areas where human cannot reach or full of danger, random deployment is more suitable. However, random deployment may result in less control on the coverage of the surveillance region. High-density node deployment is usually adopted to reduce the holes in the surveillance regions. On the other hand, when the surveillance regions are reachable, deterministic node deployment method will be adopted, and the predictable regional coverage rate could be obtained. One of the methods [1, 7] suggests using robot to deploy the nodes and emphasizes the robots access algorithm to fulfill complete coverage rate in the restricted area. Another method [8] uses mobile nodes to solve the holes left by static nodes and to improve the coverage on the monitored regions. Still another method uses the bidding algorithm [9] which can arrange the static nodes on the monitored regions to form a Voronoi cell structure to calculate the holes information in each cell and then determine which mobile node is responsible for healing the system hole through broadcasting bidding mechanism. In short, these mentioned algorithms are very effective methods that can improve the coverage rate in the field of surveillance.

Besides coverage rate, lifetime is also another issue in WSN. Lifetime of the nodes is related to the lifetime of the network. The first cluster algorithm created to balance the energy consumption of the nodes and prolong the lifetime of the WSN was proposed in [10]. Based on the cluster structure which consumes less energy for data processing and transmission, articles such as [11–13] are used to prevent the cluster head overuse, which results in energy exhausted too early, although they may use different approaches to select the cluster head. This as a result can help prolong the network lifetime by balancing nodes energy dissipation.

A nodes location with Gaussian distribution was proposed in [14], which prohibits the nodes staying too close to the sink node, a mechanism from failing too early. This is because when the nodes are close to the sink node, they usually have heavier data loading and cause early failure due to too much energy consumed. In [15], the grouping concept is used to move nodes through centralized algorithm. When nodes are grouped, centralized algorithm will calculate the number of nodes, total energy, and limitation of minimal number nodes and consider the coverage rate in each group. It will then send those useless nodes to other groups. By doing this, it should be able to balance each group's energy and optimize the network lifetime. [16] suggests a method to prolong the network lifetime, which uses decision phase and sensing phase to balance the connection maintenance load and reduce energy consumption. These researchers just focus on the current nodes energy. This as a result cannot lengthen the network lifetime because the wireless of all devices has limited energy. In other words, even the node energy dissipation balance in the field, the lifetime of network maybe be reduced due to the complex computers, and the lifetime of the network cannot be prolonged infinitely.

Connectivity and coverage have a certain degree of relation. In application, the former is a more critical issue for application of the WSN. When the environment data cannot be transmitted to the data center for further processing, the application will become pointless. A multifunctional node element called die-hard sensor network (DSN) [17], in which when a deployed node fails, the system adjusts its neighboring nodes to take over its tasks and uses dynamic routing mechanism to maintain the topology of connection, results in waste more energy in transformation of nodes function. Unfortunately, again it does not consider the problem of the total energy in the field. This will limit the network lifetime.

The location of the nodes is critical for WSN applications. If the failed nodes location in the field that is known to heal the coverage hole and maintain the topology connection is feasible. For example, in [18, 19], the authors proposed the distributive algorithm to find the system holes. In short, the replacement method can be a feasible method to prolong the lifetime of the network.

3. System Model

3.1. Problem Description

When deploying nodes in the environment field, we do not have to worry the deployment methods, either deterministic or random methods. A complete coverage of the surveillance field is the basic requirement. The sensing data will be directly or indirectly sent to the sink node through the transmission path. The nodes establishing the path are supplied by the battery power. When operating for a long time, the node would run out of energy and die. This will, therefore, result in increasing the quantity of system coverage holes and then reduce the efficiency of the environmental monitoring.

When the system has failure nodes, we could use a method to keep the WSN applications working by providing redundant nodes to heal the failed ones and recover the coverage rate in surveillance field. In this paper we use the mechanism of holes healing method, one node at a time, to adjust the parameters including the healing speed, node energy, and the number of redundant nodes. Based on the adaptively selected parameters, we can improve the coverage rate and prolong the lifetime of the network substantially.

3.2. System Parameters and Assumptions

We adopt some WSN applications, such as flat and no-obstacle environment; the nodes are deployed with a uniform distribution on the surveillance field. It is assumed that all nodes are homogeneous with the same sensing range ( $R_s$ ) and communication range ( $R_c$ ). Initially, there are a sink and a lot of nodes evenly spread on the surveillance field and full coverage, and the adjacent nodes communication with each other if the Euclidean distance between the nodes is smaller or equal to the communication range $R_c$ . To simplify process, in this paper we consider $R_c\ge 2R_s$ only. And we assume the sink node has some redundant nodes and takes charge of collecting data from the nodes and dispatching robots to heal the coverage holes on the surveillance field.

After the sensing data of nodes in the field are collected by sink, it would know the location of each node and the situation of topology. In addition to sensing the neighboring data, each node is also responsible for forwarding neighboring data to the sink. The failure of node can only be attributed to energy depletion. The $f(t)$ is defined as the probability density function of a node failure, which is approximated by an exponential distribution with parameter λ, and we let the $f(t)$ distribution equate to $\lambda \hspace{0.17em}{\exp \hspace{0.17em}}^{(-\lambda t)}$  , where λdenotes the node failure rate and assume the node failures are independently. $T_v$ is defined as the average healing time to heal one hole; under steady state we calculate  $((\mathrm{2}/N){\sum }_{i=1}^N{d}_i)/M_v$ to represent the $T_v$ time, where N is the number of nodes on the surveillance field (not including redundant nodes). Notation $d_i$ denotes the Euclidean distance between node i and the sink node, while $M_v$ denotes the moving speed of the robot. The notation $\gamma (t)$ is defined as the cumulative distribution function of one node failure probability. According to those assumptions, the probability of one node failure in a time duration $T_v$ can be presented as $\gamma (T_v)$ ; for the following simple explanation, we simplify the symbol $\gamma (T_v)$ as γ, so the $\gamma (T_v)$ may be as follows:

$$\begin{array}{cc}& \gamma \mathrm{\hspace{0.17em}\hspace{0.17em}}=\mathrm{1}-{\exp \hspace{0.17em}}^{\left(-\lambda *T_v\right)}.\end{array}$$

(1)

Robot is assigned to work as the healing tool. It also has furnished with a GPS and compass device and is capable of reaching a designated location. The dispatching is executed by sink in order unless there is no hole on the surveillance field.

Assuming that as long as a hole appears, the sink will take initiative to execute the dispatching healing scheme, and if a sensor failed during the current $T_v$ time, it can only be healed in the next $T_v$ time.

3.3. Model Establishing

The holes state transform model of the system is illustrated in Figure 1, in which $P_{i,j}$ is used to represent the probability of the holes state transformation. If there are k nodes distributions on the surveillance field, then the largest number of states is k. The number at the lower right hand corner of S in Figure 1 denotes the total number of failed nodes in the system. Specifically, a node failure within the sensing region will lead to a hole. So, the holes state i means that there are i numbers of nodes failed in the field. After one $T_v$ time elapses, the state i can transformed to statej, a state lying between the state $i-1$ and state kwith the condition, $1\le i<k$ . In each holes state change can be represented with a probability $P_{i,j}$ , and the probability of all node must fit the following equation:

$$\begin{array}{cc}& P_{i,i-\mathrm{1}}+P_{i,i}+\cdots +P_{i,k}=\mathrm{1};\hspace{1em}\mathrm{0}\le i\le k,\hspace{0.17em}\hspace{0.17em}\text{if}\hspace{0.17em}\hspace{0.17em}i=\mathrm{0}\hspace{0.17em}\hspace{0.17em}\text{then}\hspace{0.17em}\hspace{0.17em}{P}_{i,i-\mathrm{1}}=\mathrm{0}.\end{array}$$

(2)

Figure 1

The probability of the change description in the system of the holes state.

3.4. Mathematical Analysis

Have N nodes uniformly distributed on the surveillance field, and the coverage holes will be produced due to the energy exhaustion of nodes; Figure 2 illustrates the holes transformation of the state in the proposed system. State i means that there are i numbers of existing holes in system ( $0\le i\le N$ ) and will be marked as $S_i$ as described in Figure 1. $P_{i,j}$ stands for the probability of system holes transforming from state i to state $j\hspace{0.17em}\hspace{0.17em}(0\le i,j\le N)$ after one $T_v$ time, that is, an average dispatch time. The $S_0$ means that there is no hole in system; in other words, all nodes are alive on the field (sink will not be dispatched under this state). The $S_1$ means that one holes existed on the field, and the $S_i$ explains that there are i numbers of holes within the surveillance field. The relationship between the states change is according to both the nodes failure and the proposed healing scheme execution. Therefore we use the probability of mathematical methods to discuss the holes state transformation issues in system.

Figure 2

The diagram of the transformation of the system holes state.

With the definition given above, $S_0$ represents the state 0, that is, no hole in the field, and $P_{0.0}$ means that the probability of the current state is 0, and the next state is also 0. In other words, all nodes remain active after one $T_v$ time, which means none of them fails and the whole system is still in good condition. Under the circumstance, the probability $P_{0.0}$ is shown as

$$\begin{array}{cc}& P_{\mathrm{0,0}}={\left(\mathrm{1}-\gamma \right)}^N.\end{array}$$

(3)

Active nodes in the system may fail due to the power exhaustion; in consideration of that, if the current hole states is 0, and there are j nodes fail during the next one $T_v$ time, the probability is marked as $P_{0,j}$ and displayed as follows:

$$\begin{array}{cc}& P_{\mathrm{0},j}=\left(\begin{array}{c}N\\ j\end{array}\right){\gamma }^j{\left(\mathrm{1}-\gamma \right)}^{N-j};\hspace{1em}\mathrm{0}<j\le N.\end{array}$$

(4)

Some different cases will be discussed here. Based on the healing scheme, when there are i numbers of holes ( $0<i\le N$ ) in the system and no other nodes failure in the next one $T_v$ time, one hole will be healed. Thus, the holes state transform will go from i to $i-1$ , and the probability shall be marked as $P_{i,i-\mathrm{1}}$

$$\begin{array}{cc}& P_{i,i-\mathrm{1}}={(\mathrm{1}-\gamma )}^{N-i};\hspace{1em}\mathrm{0}<i\le N.\end{array}$$

(5)

Unlike the previous case, we have i ( $\ne 0$ ) numbers of holes in the system, but there is a new failure node in the next one $T_v$ time. Since the healing task has been dispatched by sink, the system holes states will not change, and the probability of the state change is marked as $P_{i,i}\text{.}$

$$\begin{array}{cc}& P_{i,i}=\left(\begin{array}{c}N-i\\ \mathrm{1}\end{array}\right)\gamma {\left(\mathrm{1}-\gamma \right)}^{N-i-\mathrm{1}};\hspace{1em}\mathrm{0}<i<N.\\ \text{When\hspace{0.17em}\hspace{0.17em}}i=\mathrm{0}\text{\hspace{0.17em}\hspace{0.17em}or\hspace{0.17em}\hspace{0.17em}}i=N\text{\hspace{0.17em}\hspace{0.17em}then\hspace{0.17em}\hspace{0.17em}}{P}_{i,i}=\{\begin{array}{cc}{(\mathrm{1}-\gamma )}^N,\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}i=\mathrm{0}\hfill \\ \mathrm{0},\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}i=N.\hfill \end{array}\end{array}$$

(6)

Here we would like to focus on the range of i. According to the assumption, if the current state is N, then the next state cannot be still at Nstate. Similarly, if there is a new hole appears under the state 0, according to the assumption provided above, the new hole can only be healed at the next $T_v$ time. Therefore the next holes state will not be state 0.

In Addition, the holes state is i at time t, and the next holes state is j ( $i<j<N$ ) at time $t+T_v$ , due to the power exhaustion with the $j-i+1$ nodes failure after one $T_v$ elapsed time. The probability of this condition is marked as $P_{i,j},$ and the necessary condition is $1\le j-1<i\le N$ , otherwise $P_{i,j}=\mathrm{0}$ , such that the probability of $P_{i,j}$ will be represented as follows:

$$\begin{array}{cc}& P_{i,j}=\left(\begin{array}{c}N-i\\ j-i+\mathrm{1}\end{array}\right){\gamma }^{j-i+\mathrm{1}}{\left(\mathrm{1}-\gamma \right)}^{N-j-\mathrm{1}},\hspace{1em}\mathrm{0}<i<j<N.\end{array}$$

(7)

State i means that there are i numbers of nodes failed in the system. Provided that the process of the dispatching healing scheme, one of the failed nodes must be healed during the next $T_v$ time. Thus, it is impossible to transfer state from holes state i to the next state N, where i is constrained under $\mathrm{0}<i\le N$ . The probability of transformation then can be written as $P_{i,N}=\mathrm{0}$ .

Based on the discussion above, we can further analyze the relationship between the probability of transformation and the holes state change. We assumed the analysis method is at the steady state statistically, meaning that the probability of the holes state is steady. According to the above analysis, we summarize the following results:

$$\begin{array}{ll}& S_{\mathrm{1}}\times P_{\mathrm{1,0}}=S_{\mathrm{0}}\times \sum _{j=\mathrm{1}}^N{P}_{\mathrm{0},j},\\ S_{i+\mathrm{1}}\times P_{i+\mathrm{1},i}+S_i\times P_{i,i}+\sum _{j=\mathrm{0}}^{i-\mathrm{1}}{S}_j\times P_{j,i}\\ \hspace{1em}\hspace{1em}=\sum _{j=i}^{N-\mathrm{1}}{S}_i\times P_{i,j}+{S_{i}P}_{i,i-\mathrm{1}};\hspace{1em}\mathrm{0}<i<N,\\ S_{\mathrm{0}}\times P_{\mathrm{0},N}=S_N\times P_{N,N-\mathrm{1}}.\end{array}$$

(8)

The holes state transformation is illustrated in Figure 2, and the description of equation is also listed above. The probability is normalized to ensure the sum of all states probability is 1. Thus, we can calculate the relationship among the holes state probability through

$$\begin{array}{cc}& \sum _{i=\mathrm{0}}^N{S}_i=\mathrm{1},\hspace{1em}{\sum }_{j=i-\mathrm{1}}^N{P}_{i,j}=\mathrm{1},\hspace{1em}\mathrm{0}<i<N.\end{array}$$

(9)

By using iterative method on (8) and (9) with the probability from (3) to (7), we can get the value of $S_i$ ( $i=0~N$ ), which stands for the probability of steady holes state, and we can calculate the number of the holes ( $N_h$ ) under the proposed healing scheme. Thus the average number of holes in system will be calculated as follows:

$$\begin{array}{cc}& N_h={\sum }_{i=\mathrm{1}}^{N}i\times S_i.\end{array}$$

(10)

4. Numerical and Simulation Results

4.1. Numerical Discussing

In this section, we execute the mathematical analysis proposed in this paper. The range of sensed areas assumed has been established. In order to simplify the analysis, we ignore the nodes deployment methods, but consider the initial network application which meets both requirements of area coverage and network connectivity. In other words, nodes can fulfill sensing the environmental data and then transfer it to the sink node by directly or indirectly (multihops) methods. Therefore, all environmental data can be collected in the sink node.

Given that there are N numbers of nodes evenly distributed in the network, each node is equipped with Q amount of limited energy. We only consider the failure nodes caused by the node energy exhaustion while the other uncertain network failure factors are ignored. For convenience in discussion, we only take three nodes for discussion; that is, let $N=3$ , and list the $P_{i,j}$ probability in Table 1, the values of which are calculated from (3) to (7).

Table 1

The list of probability of $P_{i,j}$ ( $N=3$ ).

$P_{\mathrm{0,0}}=(\mathrm{1}-\mathrm{\gamma }{)}^N$	$P_{\mathrm{0,1}}=\left(\begin{array}{c}N\\ j\end{array}\right){\mathrm{\gamma }}^j(\mathrm{1}-\mathrm{\gamma }{)}^{N-j}$	$P_{\mathrm{0,2}}=\left(\begin{array}{c}N\\ j\end{array}\right){\mathrm{\gamma }}^j(\mathrm{1}-\mathrm{\gamma }{)}^{N-j}$	$P_{\mathrm{0,3}}={\mathrm{\gamma }}^{\mathrm{3}}$
$P_{\mathrm{1,0}}=(\mathrm{1}-\mathrm{\gamma }{)}^{N-i}$	$P_{\mathrm{1,1}}=\left(\begin{array}{c}N-i\\ \mathrm{1}\end{array}\right){\mathrm{\gamma }}^{}(\mathrm{1}-\mathrm{\gamma }{)}^{N-i-\mathrm{1}}$	$P_{\mathrm{1,2}}=\left(\begin{array}{c}N-i\\ j-i+\mathrm{1}\end{array}\right){\mathrm{\gamma }}^{j-i+\mathrm{1}}(\mathrm{1}-\mathrm{\gamma }{)}^{N-j-\mathrm{1}}$	$P_{\mathrm{1,3}}=\mathrm{0}$
$P_{\mathrm{2,0}}=\mathrm{0}$	$P_{\mathrm{2,1}}=(\mathrm{1}-\mathrm{\gamma }{)}^{N-i}$	$P_{\mathrm{2,2}}=\left(\begin{array}{c}N-i\\ \mathrm{1}\end{array}\right){\mathrm{\gamma }}^{}(\mathrm{1}-\mathrm{\gamma }{)}^{N-i-\mathrm{1}}$	$P_{\mathrm{2,3}}=\mathrm{0}$
$P_{\mathrm{3,0}}=\mathrm{0}$	$P_{\mathrm{3,1}}=\mathrm{0}$	$P_{\mathrm{3,2}}=(\mathrm{1}-\mathrm{\gamma }{)}^{N-i}$	$P_{\mathrm{3,3}}=\mathrm{0}$

The probability of each holes state from $S_0$ to $S_3$ is stated in (8) and (9). The state probability can be obtained by Cramer's rule. Since it is small for $N=3$ , we can use the iterative method to simplify the equation as below:

$$\begin{array}{ll}& S_{\mathrm{0}}=\frac{P_{\mathrm{10}}}{P_{\mathrm{01}}+P_{\mathrm{02}}+P_{\mathrm{03}}}\times S_{\mathrm{1}},\\ S_{\mathrm{1}}=\frac{P_{\mathrm{21}}}{P_{\mathrm{10}}+P_{\mathrm{12}}-\left(P_{\mathrm{10}}\times P_{\mathrm{01}}/\left(P_{\mathrm{01}}+P_{\mathrm{02}}+P_{\mathrm{03}}\right)\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}}\times S_{\mathrm{2}},\\ S_{\mathrm{2}}=P_{\mathrm{32}}\\ \times (P_{\mathrm{21}}-(P_{\mathrm{21}}\times P_{\mathrm{12}}/\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left(\left(P_{\mathrm{10}}+P_{\mathrm{12}}\right)-\left(P_{\mathrm{10}}\times P_{\mathrm{01}}/\left(P_{\mathrm{01}}+P_{\mathrm{02}}+P_{\mathrm{03}}\right)\right)\right))\\ \hspace{1em}\hspace{0.17em}\hspace{0.17em}-(P_{\mathrm{10}}\times P_{\mathrm{21}}\times P_{\mathrm{02}}/\\ \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\left(\left(P_{12}+P_{10}\right)\times \left(P_{01}+P_{02}+P_{03}\right)-P_{10}\times P_{01}\right)))}^{-1}\\ \times S_{\mathrm{3}},\\ S_{\mathrm{0}}+S_{\mathrm{1}}+S_{\mathrm{2}}+S_{\mathrm{3}}=\mathrm{1}.\end{array}$$

(11)

Figure 3 shows the probability of each state $S_i$ ( $i\le 3$ ) with different failure probability γ condition. The smaller the γ is, the harder for the nodes to fail. From the aspect of system features, it is obvious that when $S_0$ becomes bigger, $S_2$ will become smaller. Therefore, the relationship between $S_1$ and γ can be derived out in the Figure 3. For instance, when γ is approximately 0.4, and the maximal value of $S_1$ is about 0.5.

Figure 3

Numerical result with $N=3$ .

Table 2 provides the values of $P_{i,j}$ and $S_i$ when γ is 0.4. When N becomes bigger, the contribution of this research will be more significant. The proposed method in this paper can provide significant discoveries in the WSN applications; it is more helpful for the parameters adjustment and obtains the optimum results, such as when to use more rapid robots or when to replace the failure node with better quality devices.

Table 2

$N=\mathrm{3},\hspace{0.17em}\gamma =\mathrm{0.4}$ .

$P_{\mathrm{0,0}}=0.216$	$P_{\mathrm{0,1}}=0.432$	$P_{\mathrm{0,2}}=0.288$	$P_{\mathrm{0,3}}=0.064$	$S_0=0.2267$
$P_{\mathrm{1,0}}=0.360$	$P_{\mathrm{1,1}}=0.480$	$P_{\mathrm{1,2}}=0.160$	$P_{\mathrm{1,3}}=0$	$S_1=0.4939$
$P_{\mathrm{2,0}}=0$	$P_{\mathrm{2,1}}=0.600$	$P_{\mathrm{2,2}}=0.400$	$P_{\mathrm{2,3}}=0$	$S_2=0.2648$
$P_{\mathrm{3,0}}=0$	$P_{\mathrm{3,1}}=0$	$P_{\mathrm{3,2}}=1.0$	$P_{\mathrm{3,3}}=0$	$S_3=0.0145$
$P_{i,j}$				$S_i$

Figure 4 illustrates the system holes number with varied node failure rate, which can present the network coverage rate under different node energy and varied robot speed conditions according to (1). Because the distributed node density is fixed, we assume the total number of nodes stands for the area of the surveillance field. Furthermore, when the distance between the hole and the sink is long, it represents the dispatch scheme in the large area. It is obvious when the healing time becomes longer, the efficiency of the healing scheme will be bad and vice versa. In other words, when the healing time is less, the healing scheme will be more efficient, and the coverage rate and connectivity will be better. However, there are circumstances that even if we provide the healing time, we still cannot prolong the lifetime, as shown in Figure 4. Specifically, too many numbers of holes will result in poor coverage rate and reduce the network connectivity. According to the proposed analysis method, the results can offer decisions of the parameter values in WSN and achieve what we plan. For example, when the number of nodes is 64 and the γ is 0.009, the system will lose efficiency, because the number of holes is large (the average number of holes is 59.52), resulting in partition the network topology. This influences the coverage rate and network connections and shortens the lifetime of the WSN.

Figure 4

Holes number versus nodes failure rate (γ).

4.2. Simulation Results

In this section we use simulation to evaluate the results of the proposed healing scheme. First we assume a square simulation area 100 m * 100 m; in this particular environment, all sensor nodes are homogeneous and can fully cover the virtual Grid-based field. We let the node sensing range $R_s$ 6 m under grid distribution, and each node has 8 connection degree exclusive the boundary nodes as shown in Figure 5. During simulation, we use the lifetime of node (day as the unit) to represent the node energy and assume the nodes initial lifetime is 2 days. We will discuss two cases, one is the sink node located at the lower left corner position, and the others are located at the field center as in Figure 5. Sink node is responsible for data collection and further processing, so it knows the coverage holes position and can carry out the dispatch healing scheme. We assume the average time of a hole healed is one $T_v$ time, the holes will be healed work in order with one node at a time, and the performance of healing scheme will be evaluated by the average of 50 repeated time simulations.

Figure 5

Grid-based topology architecture.

We describe the transformation of the holes state in the system in Figure 6, where α represents the number of new failure nodes during one $T_v$ time, and $u(T_v)$ is the number of healed hole within one $T_v$ time. $S_t$ denotes the system holes state at time t, so the number of holes on the field at the next time $t+T_v$ is $S_t+u(T_v)+\alpha$ , where $u(T_v)$ can be expressed by

$$\begin{array}{cc}& u\left(T_v\right)=\{\begin{array}{cc}\mathrm{0},\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{S}_t=\mathrm{0}\hfill \\ -\mathrm{1},\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(12)

Figure 6

System holes state transform diagram.

First, we do not consider the number of redundant nodes. In other words, there are unlimited numbers of redundant nodes for sink, and these nodes can execute the holes healing scheme. Figures 7(a) and 7(b) show the relationship between the numbers of failure nodes and diverse healing speeds in Scenario 1 and Scenario 2, respectively. Each line in Figure 7 denotes the different mobile speeds in Figure 7(a) which illustrates more high speed dispatch healing scheme always results in fewer holes. Since the robot speed is faster than 0.7 m/s in Figure 7(a), the probability of number of holes greater than 8 is closely 0, which indicates some areas may not have been covered by nodes, but the routing path for data transfer can still be maintained. When robot speed is 0.5 m/s, the network topology cannot be maintained due to the slower healing speed and results in increasing the system holes number. The network connectivity may be broken by the holes. Figure 7(b) shows the various speeds of robot in dispatching with the number of holes always less than 5. Therefore, the network connectivity can be maintained.

Figure 7

(a) Healing speeds ( $M_v$ ) versus Scenario 1. (b) Healing speeds ( $M_v$ ) versus Scenario 2.

Figure 8 illustrates the fixed robot speed versus various node lifetimes. We simulate two cases for healing scheme and the results will be represented in Figures 8(a) and 8(b) with speeds $M_v=1$  m/sec and  $M_v=2$  m/sec. From the results of the both conditions, when the lifetime of nodes is shorter, the node failure is apt to happen.

Figure 8

System holes versus node lifetimes.

In WSNs, the energy of sensor nodes is typically consumed by environment sensing, data transmission, and processing. Due to the limited power supply in sensor node, the node will fail after long-time operation. The results of proposed healing scheme, both analysis and simulation, indicate the lifetime of the network can be extended limitlessly if the number of redundant nodes is unlimited. In addition, the coverage rate and network connectivity can be effectively improved. We also simulate the fixed number of redundant nodes added to sink for dispatching healing job and calculate the number of holes within the field. We assume the robot speed at 1 m/s in Figure 9 illustrating the probability of three cases under the constant healing speed and unlimited numbers of redundant nodes. From the results shown in the Figure 9, based on the cost efficiency, we can select adaptive number of redundant nodes for varied applications in WSN.

Figure 9

The relationship among holes number, redundant nodes, and node lifetime.

We adopt the proposed method in [20], which constructs a WSN with k-coverage and $k^{\prime }$ -connectivity, where a $k^{\prime }$ -connected network is disconnected only if a minimum of $k^{\prime }$ sensor failures exist. Based on the above inferences, the results of the proposed healing scheme are shown in Figure 10. Under the Grid-based node deployment similar to Figure 5, when the number of system holes is smaller than 8, the network topology can be kept connective. In addition, as shown in Figure 10, the faster the speed in healing process is, the shorter the network lifetime is because the redundant nodes will be used up soon, but the number of coverage holes is small. This phenomenon is because the number of redundant nodes is fixed. Although the network lifetime can be reduced, the coverage rate in surveillance field can be improved. From the results, the designer can make tradeoff parameters including the robot healing speed, node lifetime, and the number of redundant nodes.

Figure 10

Network lifetime versus robot speeds ( $M_v$ ).

5. Conclusion and Future Work

In this paper we propose a dispatch scheme and analyze the healing performance in wireless sensors network applications by using sink node dispatching the redundant node to replace the failure nodes. With the dispatching scheme, the result can promise the network longevity. We analyze the results of holes state transition and calculate the relationship among the node energy, the healing speed, and the number of redundant nodes. When using different parameters, we get different network lifetime. The analysis reveals that selecting inappropriate parameters for WSN application will shorten the lifetime of the network. Thus, the proposed adaptive parameter selecting method can be used in supporting the applications of WSN.

Generally speaking, the geographical and environmental conditions in wireless sensing applications are very complicated. Factors like path occlusions, channel interferences, signal decay, and dispatch method can all influence the efficiency of the healing scheme. Therefore, more research on those factors in practical environment for WSN applications and selecting adaptive parameters for sensors network will be our further works.