A Coverage Hole Healing Strategy with Awareness of Data Delivery Time in Wireless Sensor Networks

Abstract

An efficient wireless sensor network (WSN) should maintain full sensing coverage and topology connectivity within its sensing field. Once holes occur due to failed sensors, the functionality and performance of the WSN will be affected. In this work, the proposed hole healing strategy aims to shorten the delivery hop count by a dynamic hole healing process in order to improve the data delivery time while maintaining the coverage ratio and topology connectivity. The criteria used to determine which hole should have the highest priority for healing in the next round include the weighted distance, angle magnitude, and depth of the hole. This study proposes a mobile robot, operating within the WSN, which carries redundant sensors to patch the holes by an optimum healing path. This path is determined based on the proposed EDPS (equally divided path selection) algorithm. Simulation results show the superiority of the proposed hole healing scheme over other general methods.

1. Introduction

A wireless sensor network (WSN) [1] consists of many sensing devices; however, each device only has limited resources. Under the constraint of these limited resources, these wireless devices have limited abilities, such as environment information sensing around itself, simplified computation capacity, and shorter communication distances [2, 3]. Even so, by cooperating with neighboring devices, nodes can form a network topology for WSN applications, which is important for guaranteeing the integrity and reliability of the environmental information in sensor network applications. Therefore, WSN applications usually deploy a large number of devices to guarantee full coverage and topology connectivity [4, 5]. After the wireless devices have been deployed, a network topology will be constructed via the devices' autonomous exchange of information with neighboring devices. WSN applications always require complete coverage [6], but as the abilities of wireless devices and their battery energy are limited, device failures are unavoidable. A single failed device is called a hole, which induces a coverage hole and reduces the system efficiency. Additionally, when the conveyance path is established, environment information will be sent along this path to data receiver center. In order to prevent the data transmission being interrupted because of node failures, two methods for ensuring data transmission are to reroute, or to patch nodes. The latter method (patching nodes for hole healing) is chosen in this study. The hole-healing approach was chosen over a rerouting approach for two main reasons. The first is that once the sensors near the sink, or a considerable number of sensors malfunction, either the rerouted path will become much longer, or it will not be possible to find a path for data transmission by a rerouting approach. The second reason is that a rerouting approach cannot avoid or solve the problem of coverage ratio decreases. A hole healing approach, however, will be able to keep routing paths and coverage ratios properly maintained for data transmission and the sensing tasks in a WSN. This study therefore used a hole healing approach and focused on the design of the healing strategy and mechanism. In addition, it was assumed that the WSN would always have enough reserved backup sensors for the hole healing process.

This study proposes a healing scheme that is not only able to solve the above problems but is also able to improve the delay time for data transmission. Some WSN applications require a real time response, for example, the protection of bridges, railway track security, traffic surveillance, rescue operations, or battlefield reconstruction. When an event occurs, the information must be sent to the data center as soon as possible. Therefore, the propagation time of event response in the surveillance field is an important factor in WSN applications. Data is conveyed directly or indirectly to a data receiver center, and if a node fails during this process, it will either induce data loss or postpone the propagation delay time. Therefore, failed nodes must be healed in order to increase the coverage rate and to rebuild the topology connectivity, the latter of which is more important. Before the hole is healed, carefully calculating which hole must be selected for healing, with special attention paid to the data propagation time.

This paper considers an asymmetrical WSN topology. This consists of a data collection center called a sink, and many wireless sensor devices called nodes. Nodes are responsible for collecting information on their surrounding environment and forwarding data from neighbor nodes. The information is transmitted to the data center by one-hop or multihop methods. The information flow structure is called multi-to-one topology, which differs from peer-to-peer architecture. In the multi-to-one architecture, node loading is very unbalanced, because sensors need to sense environmental information and forward others' data to the sink. Therefore, a node closer to the sink will have a heavier traffic load. As shown in Figure 1, the direction and thickness of the arrows represent the data flow direction and volume, respectively. Consequently, coverage holes occur due to node failures owing to the limited node energy being exhausted, or other accidental events. As a result, data will be lost, the conveyance time will be increased, and the topology may be separated. Because of the lack of infrastructure backbone, WSN applications usually use an ad hoc network mode. When nodes do not work together, however, it will be difficult to maintain a topology connection. To make matters worse, when they do communicate with each other, they use up their limited energy, causing node failure. As a result, there will be communication problems.

Figure 1

The multi-to-one data flow concept.

The remainder of this paper is organized as follows. Section 2 introduces relevant works. Section 3 makes system model statements concerning assumptions made in this study. Section 4 presents the proposed healing scheme algorithm. Section 5 summarizes the simulation results, and Section 6 draws conclusions.

2. Related Works

In WSN applications, connectivity and coverage are two major problems. Specifically, increasing the coverage rate and maintaining the topology connectivity can reduce node energy consumption and prolong the network lifetime. Based on limited energy resources and the nature of wireless networks, node failure is unavoidable. Therefore, reactivating failed nodes is an effective method to keep WSN applications working continuously. To do this, it is necessary to know the positions of failed nodes or holes. The Voronoi diagram concept [7] is used to detect a coverage hole and to calculate the hole size [8, 9] or improve the coverage [10, 11]. The article in [12] proposed a triangular oriented diagram to detect holes and calculate the hole size and then determine which mobile sensor should have priority for healing. Additionally, articles in [13–15] proposed a method for discovering failed nodes and estimating hole positions by periodically collecting and updating the surveillance information at the data receiver center.

In terms of hole deployment, authors in [16] utilize redundant dynamic nodes that have been distributed within the field and use dynamic scheme technology to fix the holes, based on a centralized computer to drive the appropriate dynamic nodes to holes. In [17] a TSP-Delaunay re-deployment method was proposed for repairing holes. Also, a BFNP (best fit node policy) method [18] was proposed for fixing holes by activating inactive nodes around holes. In [19], the bidding contention protocol was proposed, which enables redundant nodes in dense deployment areas to move to sparsely covered areas during the contention process. Unlike redundant nodes, static nodes are able to identify field holes. Active redundant nodes must derive hole information and calculate the healing efficiency before moving, a method which may induce erroneous movement and result in wasted energy. Besides the problem of energy consumption, the speed of the mobile nodes' movement is a critical issue which will affect the efficiency of the healing scheme; see [20] for further details. Authors in [21] considered a small group of mobile robots operating in WSNs and proposed the randomized robot-assisted relocation of static sensors (R3S2) and a grid-based variant (G-R3S2) algorithm for hole identification and coverage repair. However, these studies did not consider the delay time induced by data transmission in the hole healing process.

3. Preliminary

This study considers a centralized WSN architecture, with nodes uniformly deployed within the $W * D$ field, and with prior knowledge of the boundary nodes [22]. The field can be imagined as an $r \times r$ virtual grid, each grid possibly placed by some sensor nodes. If no nodes are located within a grid it is called a vacant grid. The coordinate of a grid is defined at the grid center. This study also assumes that all nodes are homogeneous; that is to say, all sensors have the same hardware and software features, so all nodes in a field have the same protocol stack. In addition, it was assumed that the WSN would always have enough reserved backup sensors for the hole healing process.

Vacant grids are areas uncovered by sensors; adjacent and continuously vacant grids are called coverage holes (HOLEs, which also include single vacant grids), and each HOLE is assigned a serial number i. For ease of reference, $H_{i}$ stands for the ith HOLE, where $i \leq m$ , m is the total number of HOLEs within the field of interest. This paper also uses $n_{i}$ to represent the total number of boundary nodes in the ith HOLE, $B_{i j}$ ( $j \leq n_{i}$ ), the boundary nodes of $H_{i}$ . R is the communication radius of a node with an omni-directional radio communication mode. In order to guarantee that neighboring nodes are within communication range of each other, the relationship between r and R is as shown in Figure 2, where r is the grid edge, and its length is equal to $R / \sqrt{2}$ .

Figure 2

The distance relationship of nodes under grid topology.

With the centralized WSN architecture, the sink knows the HOLE distribution in the surveillance field. To explain the node locations, Cartesian coordinates ( $x, y$ ) are used. For example, $H_{i} (x, y)$ are the coordinates of $H_{i}$ 's position, which is the gravitational mass center of the HOLE. x and y are computed as follows:

\begin{matrix} x = \frac{1}{n_{i}} (\sum_{j = 1}^{n_{i}} B_{i j} x_{j}), y = \frac{1}{n_{i}} (\sum_{j = 1}^{n_{i}} B_{i j} y_{j}) . \end{matrix}

(1)

To make the paper more readable, the term “HOLE angle” is defined as $Θ (H_{i})$ , which is from the sink viewpoint and is the minimum angle of $H_{i}$ . A HOLE is presented as a graph topology with virtual grids, denoted as $G_{i} = (V_{i}, E_{i})$ , where $V_{i}$ is the set of vertices, which include the vacant grids and the boundary nodes on the ith HOLE, and $E_{i}$ is the set of edges within HOLE $H_{i}$ . Specifically, the edge is the connection of the adjacent vertices with a distance less than or equal to R.

To maintain the topology connectivity and ensure the integrity of the environment sensing information with a shortened postponement time for data transmission, a HOLE healing scheme is proposed. Specifically, this scheme has two phases, the first is to select one HOLE while at the same time calculating a healing path, which is based on the three properties of the HOLE, and the second phase is to drive a robot to patch the HOLE along the healing path decided by the first phase. The robot is equipped with a positioning component and has the ability to move to the appointed location. Terrain obstacles are not considered, and the mobile robot only carries out and finishes an established healing path each time; the shortest route is determined by the Dijkstra algorithm.

4. Hole Healing Scheme

The purpose of the proposed scheme is to select a HOLE and to include one optimized healing path for this HOLE. In WSN applications, when the connected topology is disrupted, the connection must be restored for data transmission to continue; otherwise the environment information will either be lost or delayed at the sink. The results of the hole healing scheme are not only expected to increase the coverage rate but to also improve the data propagation time. In fact, when a HOLE is healed, the sequence will affect the system efficiency, especially used in real time applications.

Optimizing the area coverage and topology connectivity is a very complicated process. First, the Cartesian coordinates are used to describe the location of the nodes as described above. The position of the node is expressed as $C (x, y)$ , abbreviated to $C_{x, y}$ , and the origin $C_{0, 0}$ is located at the lower left hand corner. Figure 3 illustrates the relative positions. A sink is responsible for collecting the environmental information, for example, the locations $S 1$ , $S 2$ , $S 3$ , $S 4$ , and $S 5$ , representing the sensor nodes with the coordinates $C_{8, 4}$ , $C_{10, 9}$ , $C_{12, 5}$ , $C_{15, 9}$ , and $C_{6, 1}$ , respectively. Also, according to the earlier definition, the node position is always located at the center of the grid.

Figure 3

The ruled grid structure with Cartesian coordinates.

To calculate the sequence of HOLEs to be healed, three weighted metrics are considered, which are the properties of a HOLE. The first metric is the HOLE angle, $W (Θ (H_{i}))$ , the size of the angle indicating the degree to which data transmission is hindered by the HOLE; the second metric is the distance between the sink and the HOLE, denoted as $W (l e n (H_{i}))$ ; and the last metric is the depth of the HOLE, expressed as $W (d e e p (H_{i}))$ , where $i = 1,2, 3, \dots, m$ . The details of these three weighted metrics are introduced in Sections 4.1, 4.2, and 4.3, respectively.

4.1. Discussion of the HOLE Angle

The authors of [23] proposed the boundary node detection scheme, which uses the LVP (localized Voronoi polygons) algorithm to find border nodes. By using the algorithm, the nodes will know whether they are a border node or not by neighboring nodes' information only, and these nodes will transmit their status information to the sink. Figure 4 shows a typical example of HOLE distribution in the field, which results from the sink collecting information in the surveillance field.

Figure 4

The HOLE distribution in the surveillance field.

However, the angle can provide information on how the data flow will be hindered by a HOLE. Specifically, if a hole occurs in the middle of a transmission path, this will cause a conveyance interruption, and more time for rerouting will be required in order to maintain the data transmission path. The data are conveyed to the sink from all sides, and the data transmission influence is directly proportional to the HOLE width; that is to say, a larger HOLE width will mean more interference. In this study, the HOLE angle is considered equivalent to the HOLE width.

Before computing $Θ (H_{i})$ , a ray expressed by [Sink, $B_{i}$ ) which starts at the sink and extends toward border node $B_{i}$ is denoted by $\vec{L_{ı}}$ . According to the property of the trigonometric function, the method proposed in article [24] is used to solve $Θ (H_{i})$ over 180 degree problems. Here it must be noted that all angles are measured either in a clockwise direction, or a counter-clockwise direction.

The algorithm applies the slope of the ray to find the upper border node $B_{u}$ and the lower border node $B_{d}$ in $H_{i}$ , as well as the angle $Θ (H_{i})$ . The algorithm discussed in Algorithm 1 is used in a typical example shown in Figure 5. The metric of the HOLE angle $W (Θ (H_{i}))$ can be calculated by

\begin{matrix} W (Θ (H_{i})) = \frac{Θ (H_{i})}{180} . \end{matrix}

(2)

Algorithm 1: The algorithm of HOLE angle calculation.

Input: $H_{i}$ , $B_{i j}$

Output: $∠ Θ (H_{i})$ , $B_{u}$ and $B_{d}$

Initial:

Let $B_{u} \leftarrow H_{i} (x, y)$ , $B_{d} \leftarrow H_{i} (x, y)$

${slope}_{\min} \leftarrow slope (H_{i})$ , $slop e_{\max} \leftarrow slope (H_{i})$

(1) For j from 1 to n do

(2) $\overset{⟶}{L_{J}} \leftarrow [Sink, B_{i j})$ .

(3) if $slope (\overset{⟶}{L_{J}}) < slop e_{\min}$

(4) $B_{d} = B_{i j}$ , $slop e_{\min} = slope (\overset{⟶}{L_{J}})$

(5) else if $slope (\overset{⟶}{L_{J}}) > slop e_{\max}$

(6) $B_{u} = B_{i j}$ , $slop e_{\max} = slope (\overset{⟶}{L_{J}})$

(7) End For

(8) $\emptyset (H_{i}) = {\begin{cases} {2sin}^{- 1} (\frac{R / 2}{| \overset{⃑}{Sink H_{i}} |}); & {if slope}_{\min} = {slope}_{\max} \\ \cos^{- 1} (\frac{\overset{⃑}{Sink B_{u}} n \overset{⃑}{Sink B_{d}}}{| \overset{⃑}{Sink B_{u}} | \times | \overset{⃑}{Sink B_{d}} |}); & otherwise \end{cases}$

(9) $Θ (H_{i}) = {\begin{cases} \emptyset (H_{i}); & if \emptyset (H_{i}) ϵ [0^{°}, 180^{°}] \\ 360^{°} - \emptyset (H_{i}); & if \emptyset (H_{i}) ϵ [180^{°}, 360^{°}] \end{cases}$

Figure 5

Illustration of the relationship between $B_{u}$ , $B_{d}$ , and $Θ (H_{i})$ .

4.2. The Distance Metric $W (l e n (H_{i}))$

The proposed hole healing scheme is based on a centralized topology. Obviously, the environmental information is conveyed to the sink, and if any HOLE exits within the field, then the data transmission will be hindered. Influence on the fixed size of a HOLE owing to the different influences of various positions depends on how close the sink is. If the HOLE position is closer to the sink, then the interference will be more serious, and if the HOLE is far away from the sink, the interference will be much less. Therefore, HOLE healing must first consider the influence intensity of data transmission. Figure 6 illustrates the HOLE distribution by Euclidean distance in the field, where $d_{i}$ denotes the Euclidean distance between the sink and the HOLE:

\begin{matrix} d_{i} = \sqrt{{(H_{i} \cdot x - S_{0} \cdot x)}^{2} + {(H_{i} \cdot y - S_{0} \cdot y)}^{2}} . \end{matrix}

(3)

Figure 6

The HOLE distribution by Euclidean distance.

The metric of the HOLE distance is denoted as $W (l e n (H_{i}))$ . If the efficiency of data propagation time that considers the HOLE distance only is discussed, it is easy to see that the shorter the distance is, the shorter the propagation time will be. Conversely, if the HOLE position is far away from the sink, or even located at the field border, then the influence on the data transmission will be less, most of which is the coverage rate problem. So let this metric be inversely proportional to the reciprocal of the HOLE distance between the HOLE and the sink:

\begin{matrix} W (l e n (H_{i})) = \frac{1}{d_{i}} . \end{matrix}

(4)

4.3. The Metric of the HOLE Depth, $W (d e e p (H_{i}))$

When the HOLE area is small, it is clear which HOLE must be selected, with the path healing determined by the metrics $W (Θ (H_{i}))$ and $W (l e n (H_{i}))$ only. However, when the HOLE area is large, the HOLE area effects must be considered. Under such circumstances, not only the shorter delay time for the data transmission must be taken into account, but topology disconnection must also be avoided. To do this, the third factor should be considered—the HOLE depth.

To determine the depth of the HOLE, the nearest border nodes $B_{near}$ and farthest border nodes $B_{far}$ must first be calculated, based on the distance from the sink. In order to choose the optimum healing path and simplify the problem of irregular HOLEs, a bisector is used to divide the HOLE angle. The length of the line within the HOLE is considered the depth of the HOLE. Here, the definition of the HOLE depth $W (d e e p (H_{i}))$ is the Euclidean distance between $B_{near}$ and $B_{far}$ . In order to find the two boundary nodes, the following definition is used.

Definition 1.

A ray [Sink, $B_{i}$ ) divides $Θ (H_{i})$ equally and passes through $H_{i}$ , which intersects the nearest border node on $H_{i}$ , $B_{near}$ and the farthest border node on $H_{i}$ , $B_{far}$ . The method of finding the path from $B_{near}$ to $B_{far}$ is called the equally divided path selection method, abbreviated as EDPS.

To calculate both nodes $B_{near}$ and $B_{far}$ , known conditions like the sink, $B_{d}$ and $Θ (H_{i})$ are used to establish a ray $\vec{S B_{ı}}$ , denoted as $L_{c}$ , which is based on the ${S B}_{d}$ side and starts at the sink position with $Θ (H_{i}) / 2$ . $L_{c}$ intersects with the HOLE at two boundary nodes called $B_{near}$ and $B_{far}$ , shown in Figure 7. It is worth noting that the term “intersect” means that $L_{c}$ passes through the transmission range of a node. So the value of the boundary nodes $B_{near}$ , $B_{far}$ and the metric of the HOLE depth $W (d e e p (H_{i}))$ can be described as follows:

\begin{array}{l} B_{near} = {B_{j} | d (L_{c}, B_{j}) ≦ R & & \min d (S, B_{j}), B_{j} \in H_{i}}, \\ B_{far} = {B_{j} | d (L_{c}, B_{j}) ≦ R & & \max d (S, B_{j}), B_{j} \in H_{i}}, \\ W (d e e p (H_{i})) \\ = \sqrt{{(B_{far} \cdot x - B_{near} \cdot x)}^{2} + {(B_{far} \cdot y - B_{near} \cdot y)}^{2}} . \end{array}

(5)

Figure 7

Illustration of the relationship between $B_{near}$ , $B_{far}$ , and $Θ (H_{i})$ .

As discussed above, an established path from $B_{near}$ to $B_{far}$ is the shortest distance to the farthest node that crosses the HOLE and arrives at the sink. This paper will demonstrate that the decided path is the shortest distance for data transmission. Before Theorem 2, which calculates the shortest distance for node data transmission, is carried out, facing the sink first gives a rectangle parallelogram TUWV surrounding the HOLE, as shown in Figure 8.

Figure 8

Illustration of the path selection by EDPS.

Theorem 2.

The shortest healing path in $H_{i}$ can be determined by EDPS.

Proof.

In Figure 8, the parallelogram TUWV contains a HOLE $H_{i}$ , and p is an arbitrary point on segment TU, under uniform node distribution. A and B represent two nodes in symmetrical positions from the perspective of the sink. The proposed method attempts to find the shortest path that passes through the region of TUWV. It summarizes those distances from both points A and B to go through the same path and reach the sink. Points A and B are two symmetric points based on the stochastic random process.

Point q is one point on segment $A B$ . Let the length of $A B$ be L, and let $\bar{A q} = x$ and $\bar{B q} = y$ . As a result, $x + y = L$ . In addition, let h be the distance between $\bar{A B}$ and p, assuming that $\bar{A p} = a$ and $\bar{B p} = b$ . According to the triangular theory, the following equations are obtained:

\begin{matrix} a^{2} = h^{2} + x^{2}, \end{matrix}

(6)

\begin{matrix} b^{2} = h^{2} + y^{2} . \end{matrix}

(7)

Here the function

f (x)

is defined, and let

f (x) = a + b

Both (6) and (7) substitute for $f (x)$ , so

\begin{matrix} f (x) = \sqrt{x^{2} + h^{2}} + \sqrt{{(L - x)}^{2} + h^{2}} . \end{matrix}

(8)

Take (8) to derive by once and twice differential operations. This yields the first and second differential equations, respectively:

\begin{array}{l} f^{'} (x) = \frac{x}{{(x^{2} + h^{2})}^{1 / 2}} - \frac{L - x}{{[{(L - x)}^{2} + h^{2}]}^{1 / 2}}, \end{array}

(9)

\begin{array}{l} f^{′′} (x) = \frac{{(x^{2} + h^{2})}^{1 / 2} + x \times (1 / 2) {(x^{2} + h^{2})}^{- 1 / 2}}{(x^{2} + h^{2})} \\ - ({[{(L - x)}^{2} + h^{2}]}^{1 / 2} \times (- 1) + (L - x) \\ \times \frac{1}{2} {(x^{2} + h^{2})}^{- 1 / 2} \times (- 2) (L - x)) \\ \times {[{(L - x)}^{2} + h^{2}]}^{- 1} . \end{array}

(10)

According to the extreme value theorem, it is known that the function $f (x)$ has a minimum value when $x = L / 2$ . In other words, $a + b$ has a minimum value when the point q is located at the center of L. In short, it is proved that the path found by EDPS from nodes A and B to point p arriving at the sink is the shortest possible distance.

4.4. The Selection of the Optimal Healing Path

The healing path will be selected according to the three factors described above, that is, the angle, the distance, and the depth of the HOLE. Here, it is worth noting to patch one node in the HOLE, if we pay attention to the position needed to be healed. Even though the coverage increase is fixed with a maximum size of the sensing range of a node, the delay time for the data transmission may vary with different healing positions. To extend the analysis of the proposed scheme to various applications, three parameters, α, β, and γ weighting on the three HOLE metrics, respectively, are used. The formula of the total healing metric is denoted as $W (H_{i})$ , shown as follows:

\begin{array}{l} W (H_{i}) = α W (Θ (H_{i})) \times β W (l e n (H_{i})) \\ \times γ W (d e e p (H_{i})), \end{array}

(11)

where α, β, and γ are positive harmonic coefficients. Let

α + β + γ = 1

. Changing the parameters will induce different results. Based on (11), one HOLE will be selected. However, because the EDPS method selected healing path from

B_{near}

B_{far}

is a straight line, the patch nodes will be located in a virtual grid, as assumed earlier. As the straight line patch nodes may not be the real node positions, it is necessary to modify the straight line healing. To find the real path, the vertices in the HOLE which are close to

L_{c}

are used. According to the virtual vertices computed in Algorithm 2, the vertices' accordance with the healing sequence should be arranged in the set of Path

{}

Algorithm 2: The algorithm for the modification from straight healing line to real positions.

Input: $L_{c}$ , $B_{near}$ , $B_{far}$ , $V_{i}$

Output: Path ${}$

Initial: Path ${} = φ$

(1) $P \leftarrow B_{near}$

(2) Adding $B_{near}$ to Path ${}$

(3) $V_{s} \leftarrow P$

(4) $P = {V_{i} | d (V_{s}, V_{i}) \leq R_{c} & & \min d (L_{c}, V_{i})}$

(5) Add the vertex P to Path ${}$

(6) $V_{s} \leftarrow P$ , ${V_{i}} = {V_{i}} - P$

(7) Repeat step 4 until $P = B_{far}$

(8) Adding $B_{far}$ to Path ${}$

In Algorithm 2, $L_{c}$ is determined as in Figure 7. The virtual vertices set $V_{i}$ are the grid locations in $H_{i}$ . The Steiner point problem layout method [25] is used with the proposed grid topology to determine the actual vertices' positions. As shown in Figure 9, the blue ray is calculated by the EDPS method in $H_{5}$ . The optimum healing path, which consists of the real healed positions, is denoted by the red arrows. In fact, these positions must also be sequentially recorded in Path ${}$ . The elements of the set are sequenced locations of the vertices which will be healed. For example, Figure 9 has two nodes, $B_{6,4}$ and $B_{8,9}$ , which are the border nodes $B_{near}$ and $B_{far}$ , respectively. In addition, there are four vertices, $C_{7,5}$ , $C_{7,6}$ , $C_{7,7}$ , and $C_{8,8}$ . That is to say, the elements of Path ${}$ are ${B_{6,4}$ , $C_{7,5}$ , $C_{7,6}$ , $C_{7,7}$ , $C_{8,8}$ , $B_{8,9}}$ .

Figure 9

Illustration of the real healing path.

5. Simulation Results

The hole healing scheme proposed in this paper considers three weighted metrics, which are the angle, $W (Θ (H_{i}))$ , the depth, $W (d e e p (H_{i}))$ , and the distance, $W (l e n (H_{i}))$ , of the HOLE. The abbreviations $p_{i a}$ , $p_{i d}$ , and $p_{i l}$ are used to represent the normalized values between 0 and 1 of these three metrics. The delivery hop count was used to measure the data propagation delay. Therefore, if the number of hops can be reduced during data transmission, the data transmission will have a shorter delay time. This also has the advantages of reducing energy consumption and prolonging the lifetime of the WSN applications. The experiment in this paper was carried out by simulations under different environmental parameters to illustrate the variety of the average delivery path length for data transmission. The results show that the proposed weighted method has less delivery hops than do other methods, listed as follows: (1)

random selection for healing hole,

(2)

nearest distance selection for healing hole,

(3)

maximum size selection for healing hole.

First, in this simulation let the three weight values of α, β, and γ be equal; in other words, all of them are equal to 1/3. The average delivery hops (ADH) of the proposed weighted method were calculated and compared with those of the other methods. In the simulations, sensor nodes were initially deployed in the ruled fields of $10 \times 10$ , $20 \times 20$ , $30 \times 30$ , $40 \times 40$ , and $50 \times 50$ , respectively. The sizes and locations of the HOLEs were randomly generated, and the maximum number of HOLEs is limited to 15. Each ADH result is the average of 1000 iterations for each case in the simulation, as shown in Table 1 and Figure 10.

Table 1

ADH (random HOLE = 15, $α = β = γ = 1 / 3$ ).

Node count	Method
Node count	Random	Nearest	MaxSize	Weighted
$10 \times 10$	7.34	6.64	6.52	6.41
$20 \times 20$	16.44	14.96	14.55	14.37
$30 \times 30$	25.89	23.48	22.75	22.49
$40 \times 40$	35.2	31.97	31.05	30.66
$50 \times 50$	44.66	40.5	39.35	38.81

Figure 10

ADH (random $H O L E = 15$ , $α = β = γ = 1 / 3$ ).

$W {(H_{i})}_{\max}$ denotes the largest HOLE score and is calculated by (12). $H_{i}$ denotes the ith HOLE with the maximum score, which will be selected for healing:

\begin{array}{l} {W (H_{i})}_{\max} = \underset{\forall i}{argmax} (α \cdot p_{i a} + β \cdot p_{i d} + γ \cdot p_{i l}), \\ α + β + γ = 1 . \end{array}

(12)

Obviously, the longest average transmitted path was obtained by random selection; the second longest path was achieved by nearest distance selection; the third longest path was achieved by maximum size selection; and the best result (the shortest route) was obtained by the proposed weighted selection scheme. It also can be observed from the results that the number of ADH increased proportionally according to the number of nodes, and the result differences between the four methods were more conspicuous in larger areas.

To discuss the decrement rate ( $D_{r}$ ) of ADH in the various methods, the $D_{r}$ of ADH is calculated by formula (13), and the results are shown in Table 2 and Figure 11. This roughly illustrates that the weighted method is reduced by 12.9% more than the random method, by 4% more than the nearest method, and by 1.3% more than the MaxSize method:

\begin{matrix} D_{r} = \frac{result - {result}_{w}}{result} \times 100 % . \end{matrix}

(13)

Table 2

Decrement rate of ADH (random HOLE = 15, $α = β = γ = 1 / 3$ ).

Node count	Method
Node count	Random →Weighted	Nearest →Weighted	MaxSize →Weighted
$10 \times 10$	12.67%	3.46%	1.69%
$20 \times 20$	12.59%	3.94%	1.24%
$30 \times 30$	13.13%	4.22%	1.14%
$40 \times 40$	12.9%	4.1%	1.26%
$50 \times 50$	13.1%	4.17%	1.37%

Figure 11

$D_{r}$ of ADH (random $H O L E = 15$ , $α = β = γ = 1 / 3$ ).

The above simulation results were based on a fixed number of HOLEs and various numbers of deployed nodes. The next simulations were conducted with a fixed number of $30 \times 30$ nodes, and both the position and size of the HOLEs were produced by randomization. However, the numbers of HOLEs were given as 5, 10, 15, 20, or 25 for different cases. After carrying out 1000 simulations for each case, the ADH results were obtained as shown in Table 3 and Figure 12. The results show that the longest distance of the average transmission path was obtained by the random selection method; the second longest path was the nearest distance first selection; and the third longest path was the maximum size first selection method. However the best result (the shortest route) was obtained by the proposed weighted method. It also can be observed that when the number of HOLEs increases, the results of the different methods differ more significantly.

Table 3

ADH (node count = $30 \times 30$ , $α = β = γ = 1 / 3$ ).

HOLE count	Method
HOLE count	Random	Nearest	MaxSize	Weighted
5	22.97	21.14	20.92	20.73
10	24.83	22.77	22.3	21.98
15	25.89	23.48	22.75	22.49
20	26.37	23.92	23.09	22.77
25	26.76	24.35	23.2	22.92

Figure 12

Average delivery hops (node count = $30 \times 30$ , $α = β = γ = 1 / 3$ ).

Similarly, a fixed number of $30 \times 30$ nodes was used, and both the position and size of the HOLEs were produced by randomization, and the number of HOLEs were given as 5, 10, 15, 20, or 25, respectively. By comparing the proposed weighted method with the random, nearest, and MaxSize methods, the results of the decrement rate of ADH were obtained, as shown in Table 4 and Figure 13, which roughly illustrate that the weighted method was reduced by about 9.75%~14.35% more than the random method, by about 1.94%~5.87% more than the nearest method, and by about 0.91%~1.21% more than the MaxSize method.

Table 4

Decrement of ADH (node count = $30 \times 30$ , $α = β = γ = 1 / 3$ ).

HOLE count	Method
HOLE count	Random →Weighted	Nearest →Weighted	MaxSize →Weighted
5	9.75%	1.94%	0.91%
10	11.48%	3.47%	1.43%
15	13.13%	4.22%	1.14%
20	13.65%	4.81%	1.39%
25	14.35%	5.87%	1.21%

Figure 13

Decrement of ADH (node count = $30 \times 30$ , $α = β = γ = 1 / 3$ ).

The simulation results shown above are compared with the different methods. However, Table 5 and Figure 14 show the varied ADH results based on the simulations of simultaneously changing both the number of nodes and HOLEs in the weighted method. It is clear that if the number of nodes or HOLEs increases, the ADH count will also increases. It is also clear that an increased number of nodes results in a more significant increase of ADH than does an increased number of HOLEs.

Table 5

ADH for proposed weighted HOLE selection method ( $α = β = γ = 1 / 3$ ).

Node count	HOLE count
Node count	5	10	15	20	25
$10 \times 10$	6.15	6.31	6.41	6.46	6.48
$20 \times 20$	13.38	14.08	14.37	14.53	14.56
$30 \times 30$	20.73	21.98	22.49	22.77	22.92
$40 \times 40$	28.15	29.85	30.66	31.07	31.34
$50 \times 50$	35.5	37.82	38.81	39.36	39.59

Figure 14

ADH for proposed weighted HOLE selection method ( $α = β = γ = 1 / 3$ ).

The results discussed above were under the condition of three equal weighting coefficients, $α = 1 / 3$ for the HOLE angle, $β = 1 / 3$ for the HOLE depth, and $γ = 1 / 3$ for the HOLE distance parameters. Next, the various values of the coefficients α, β, and γ were considered, and the changes of the ADH in the weighted method were observed. Because the values of the weights α, β, and γ are between 0 and 1 and $α + β + γ = 1$ , in Table 6, the oblique line illustrates that the cases will never happen (the total value of weights exceeds 1). The value of γ is related to α and β and is calculated according to the following formula:

\begin{matrix} γ = 1 - α - β . \end{matrix}

(14)

Table 6

ADH count (node count = $30 \times 30$ , random HOLE = 15).

α	β
α	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
0	23.49	23.02	22.77	22.62	22.66	22.67	22.82	22.87	22.94	22.94	22.99
0.1	23.31	22.83	22.64	22.5	22.59	22.64	22.79	22.89	22.86	22.84
0.2	23.05	22.71	22.54	22.54	22.58	22.63	22.71	22.79	22.88
0.3	22.87	22.67	22.51	22.51	22.55	22.59	22.69	22.79
0.4	22.84	22.62	22.49	22.5	22.51	22.59	22.64
0.5	22.83	22.55	22.5	22.52	22.47	22.64
0.6	22.67	22.54	22.5	22.38	22.53
0.7	22.75	22.57	22.5	22.53
0.8	22.66	22.59	22.45
0.9	22.69	22.61
1	22.7

Table 6 and Figure 15 illustrate the change of the ADH count with variously changed weighting values of α, β, and γ. The result is also the average of 1000 iterations in each simulation case. The numbers of nodes and HOLEs are $30 \times 30$ and 15, respectively. As the results show, when both weighting values α and β are lower, the delivery hop count will become larger. When $α = 0.6$ , $β = 0.3$ , and $γ = 0.1$ , the lowest ADH count (= 22.38) is obtained, which means higher data transmission efficiency and lower energy consumption than the other permutations of the weighting coefficients.

Figure 15

ADH (node count = $30 \times 30$ , random $H O L E = 15$ ).

According to the above simulation results, it clear that the proposed weighted method has demonstrates significantly better performance than the other methods. In addition, the simulations with adjusted of weighting values were able to obtain the optimum values for α, β, and γ in order to obtain the shortest ADH and apply the proposed weighted HOLE healing strategy to practical applications.

6. Conclusion

The focus of this paper is the rebuilding and maintenance of network topology connections. Reducing the time of postponement in the data transmission process is the purpose of the proposed hole healing scheme. Three properties of HOLEs for HOLE selection are proposed to improve the data conveyance time. They consider factors such as the angle of a HOLE, the distance between the sink and a HOLE, and the depth of the HOLE. In addition, the proposed EDPS algorithm is able to find a shorter path for healing the selected HOLE. This idea is quite useful for the healing process, especially when large HOLEs occur in the field. To ensure the accuracy of node location calculation, the field is imagined as a virtual ruled grid, and a robot is utilized to patch sensors in order to rebuild the topology connection. The performance of this proposed strategy is evaluated according to the average delivery hops. By comparing the proposed method with the random selection, nearest selection, and maximum size selection methods, the simulation results show that the proposed strategy outperforms the others. We believe that our proposed method of hole healing with data delivery awareness (HHDDA) is a valuable maintenance method for WSN applications.

Footnotes

Acknowledgment

The authors would like to thank the Research Center for Energy Technology and Strategy (RCETS) of National Cheng Kung University for financially supporting this research under Grants no. D102-23015 and no. D102-15103.

References

Pottie

G. J.

Wireless Sensor Networks

Proceedings of the IEEE Information Theory Workshop

1998

Killarney, Ireland

139 140

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

2-s2.0-0037086890

10.1016/S1389-1286(01)00302-4

Estrin

Govindan

Heidemann

Kumar

Next century challenges: scalable coordination in sensor networks

Proceedings of the Annual ACM International Conference on Mobile Computing and Networking MobiCom

1999

263 270

Sung

T.-W.

Yang

C.-S.

A cell-based sensor deployment strategy with improved coverage for mobility-assisted hybrid wireless sensor networks

International Journal of Ad Hoc and Ubiquitous Computing 2010 5 3 189 198

2-s2.0-77949769032

10.1504/IJAHUC.2010.032231

Sung

T.-W.

Yang

C.-S.

An adaptive joining mechanism for improving the connection ratio of ZigBee wireless sensor networks

International Journal of Communication Systems 2010 23 2 231 251

2-s2.0-77049123262

10.1002/dac.1067

Meguerdichian

Koushanfar

Potkonjak

Srivastava

M. B.

Coverage problems in wireless ad-hoc sensor networks

Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies

April 2001

1380 1387

2-s2.0-0034997317

Aurenhammer

Voronoi diagrams—a survey of a fundamental geometric data structure

ACM Computing Surveys 1991 23 4 345 406

Ghosh

Estimating coverage holes and enhancing coverage in mixed sensor networks

Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN '04)

November 2004

68 76

2-s2.0-20544442644

10.1109/LCN.2004.53

Wang

Cao

Berman

La Porta

T. F.

Bidding protocols for deploying mobile sensors

IEEE Transactions on Mobile Computing 2007 6 5 515 528

2-s2.0-33947622591

10.1109/TMC.2007.1022

10.

Sung

T.-W.

Yang

C.-S.

Voronoi-based coverage improvement approach for wireless directional sensor networks

Journal of Network and Computer Applications 2013

10.1016/j.jnca.2013.07.003

11.

Sung

T.-W.

Yang

C.-S.

Distributed voronoi-based self-redeployment for coverage enhancement in a mobile directional sensor network

International Journal of Distributed Sensor Networks 2013 2013 15

165498

10.1155/2013/165498

12.

Babaie

Pirahesh

S. S.

Hole detection for increasing coverage in wireless sensor network using triangular structure

IJCSI International Journal of Computer Science Issues 2012 9 1, article 2

13.

Huang

C. -F.

Tseng

Y. C.

The coverage problem in a wireless sensor network

Proceedings of the 2nd ACM international conference on Wireless Networks and Applications (WSNA ’03)

2003

14.

Hunter

D. K.

Yang

Distributed coordinate-free hole detection and recovery

Proceedings of the IEEE Global Telecommunications Conference (Globecom ’06)

December 2006

2-s2.0-50949106113

10.1109/GLOCOM.2006.680

15.

N. P.

Quan

B. T.

Hieu

N. T.

Van

N. K.

Efficient approximation of routing holes in wireless sensor networks

Proceedings of the 2nd Symposium on Information and Communication Technology (SoICT '11)

October 2011

72 79

2-s2.0-82955197448

10.1145/2069216.2069234

16.

Zhou

M.-Y.

Shu

Finding optimal placements for mobile sensors: wireless sensor network topology adjustment

Proceedings of the IEEE 6th Circuits and Systems Symposium on Emerging Technologies: Frontiers of Mobile and Wireless Communication

June 2004

529 532

2-s2.0-20344397962

17.

Zhang

Xia

Cheng

A hole detection and redeployment strategy in wireless sensor network

Journal of Information and Computational Science 2011 8 13 2577 2585

2-s2.0-83255171123

18.

Deng

X.-H.

C.-G.

Zhao

F.-Y.

Liu

Repair policies of coverage holes based dynamic node activation in Wireless Sensor Networks

Proceedings of the 8th International Conference on Embedded and Ubiquitous Computing (EUC '10)

December 2010

368 371

2-s2.0-79951788070

10.1109/EUC.2010.61

19.

Wang

Cao

Berman

La Porta

T. F.

Bidding protocols for deploying mobile sensors

IEEE Transactions on Mobile Computing 2007 6 5 515 528

2-s2.0-33947622591

10.1109/TMC.2007.1022

20.

Fu-Tian Lin Liang-Cheng Shiu Chao-Yang Lee Chu-Sing Yang

A method to analyze the effectiveness of the holes healing scheme in wireless sensor network

International Journal of Distributed Sensor Networks 2013 2013 10

725452

10.1155/2013/725452

21.

Hao

Tang

Xue

Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation

Proceedings of the Workshop on High Perfomance Switching and Routing (HPSR '04)

April 2004

246 250

2-s2.0-2942525470

22.

Funke

Topological hole detection in wireless sensor networks and its applications

Proceedings of the joint workshop on Foundations of mobile computing (DIALMPOMC '05)

September 2005

23.

Zhang

Fang

A coverage inference protocol for wireless sensor networks

IEEE Transactions on Mobile Computing 2010 9 6 850 864

24.

Bejerano

Coverage verification without location information

IEEE Transactions on Mobile Computing 2011 4 11631 11643

10.1109/TMC.2011.85

25.

Lin

G.-H.

Xue

Steiner tree problem with minimum number of Steiner points and bounded edge-length

Information Processing Letters 1999 69 2 53 57

2-s2.0-0032755118

A Coverage Hole Healing Strategy with Awareness of Data Delivery Time in Wireless Sensor Networks

Abstract

1. Introduction

2. Related Works

3. Preliminary

4. Hole Healing Scheme

4.1. Discussion of the HOLE Angle

Algorithm 1: The algorithm of HOLE angle calculation.

4.2. The Distance Metric W ( l e n ( H i ) )

4.3. The Metric of the HOLE Depth, W ( d e e p ( H i ) )

Definition 1.

Theorem 2.

Proof.

4.4. The Selection of the Optimal Healing Path

Algorithm 2: The algorithm for the modification from straight healing line to real positions.

5. Simulation Results

6. Conclusion

Footnotes

Acknowledgment

References

4.2. The Distance Metric $W (l e n (H_{i}))$

4.3. The Metric of the HOLE Depth, $W (d e e p (H_{i}))$