Energy-Balanced Density Control to Avoid Energy Hole for Wireless Sensor Networks

Abstract

Density control is of great relevance for wireless sensor networks monitoring hazardous applications where sensors are deployed with high density. Due to the multihop relay communication and many-to-one traffic characters in wireless sensor networks, the nodes closer to the sink tend to die faster, causing a bottleneck for improving the network lifetime. In this paper, the theoretical aspects of the network load and the node density are investigated systematically. And then, the accessibility condition to satisfy that all the working sensors exhaust their energy with the same ratio is proved. By introducing the concept of the equivalent sensing radius, a novel algorithm for density control to achieve balanced energy consumption per node is thus proposed. Different from other methods in the literature, a new pixel-based transmission mechanism is adopted, to reduce the duplication of the same messages. Combined with the accessibility condition, nodes on different energy layers are activated with a nonuniform distribution, so as to balance the energy depletion and enhance the survival of the network effectively. Extensive simulation results are presented to demonstrate the effectiveness of our algorithm.

1. Introduction

With the help of technological advances in MEMS, a mass production of tiny and economical sensors becomes possible. A wireless sensor network consists of a large number of sensor nodes deployed in region of interest to collect related information and communicate the results to the users [1]. The network can be embedded in our physical environment and have many potential applications, such as battlefield surveillance, environment monitoring, and fire detection.

Since the microsensors are usually supported by battery, they are thus limited in resources and vulnerable in nature. When sensor nodes are deployed to monitor hazardous applications like over a battlefield, an important question is to guarantee that the target area is covered and the detection probability is high. If a small number of nodes are deployed, blind spots or sensing holes might be left, which may reduce the accuracy of the results obtained. In order to enhance the reliability of the network, sensor nodes are usually deployed with high density, up to 20 nodes/m³. However, as all of the nodes share common sensing tasks, if those sensors operate in the active mode simultaneously, data collected in such a high-density network would be highly correlated and redundant, consuming an excessive amount of energy. To illustrate the point, imagine the scenario that when a certain triggering event occurs, a large number of nodes will send packets at the same time, making such a network less responsive and less energy efficient. As a result, deploying such a sensor network to monitor hazardous applications and maintaining its sensing coverage could be a daunting task.

In general, density control is an effective method to solve the above problem. Recently, a class of work has appeared to find the optimal subset of sensor nodes for densely deployed wireless sensor network while these working nodes can completely cover the monitored area [2– 8]. In addition, the problem is proved to be NP-complete [3]. However, most of the current works do not consider the issue of uneven energy depletion with distance to a predetermined sink. They all aimed to achieve a uniform hexagonal distribution to preserve area coverage with the fewest sensors. When using such a uniform distribution in many-to-one sensor network applications, the sensor nodes around the sink should forward more data and deplete their energy faster. Consequently, an energy imbalance problem manifests itself, as an energy hole is created around the sink node. If this happens, no more data can be transmitted to the sink. Moreover, the network lifetime ends soon and more energy of the nodes would be wasted. Experimental results in [9] show that when the network lifetime is over, up to 90% of the total initial energy of the nodes is left unused if the nodes are distributed uniformly in the network. It becomes a major concern for network designers to maintain the balance of power consumption so that the lifetime of sensor network is prolonged.

In this paper, we formulate the energy imbalance problem and present a nonuniform distribution of sensor nodes to analyze the maximum network lifetime for many-to-one wireless sensor networks. In contrast to constant data acquisition rate, we import the pixel-based transmission mechanism to avoid sending needless duplication of the same sensing data. Furthermore, a density control algorithm is proposed to achieve balance of energy depletion by introducing the concept of the equivalent sensing radius. The rest of this paper is organized as follows. In Section 2, we review the related work in the literature. In Section 3, we theoretically analyze the nonuniform node distribution strategy. And after that, an energy-balanced density control algorithm is proposed in Section 4. Section 5 describes the simulation results of the proposed algorithm. Finally, the paper is concluded in Section 6.

2. Related Work

As one of the most fundamental issues in wireless sensor networks, the density control problem has attracted significant research attention. Therefore, coverage together with sensor management has been a strong research focus for the last few years. In [3], the authors provide a method for finding the maximum number of disjoint cover sets that are working successively in a WSN. In each cover set, a sufficient number of sensor nodes necessary to cover the targets are active, while the remainder of the nodes are put to sleep. However, their approach is based on a centralized solution. A distributed approach named PEAS is proposed in [4], in which the nodes use a simple rule to decide about their activity. If a node cannot find any active node in the probing range, it becomes active. Otherwise, it returns to the sleeping mode. Although this approach eliminates the complexity of getting neighbours' status, it does not require location information and cannot guarantee full sensing coverage for the target area. Similarly, the authors in [5] propose a scheduling scheme that enables each node to enter active or sleeping state based on the coverage relationship with its neighbours. In their approach, in order to avoid the “blind point” caused by two neighbours simultaneously turning off, a random back-off time is introduced before the node makes a decision about its status. However, these algorithms cannot achieve full sensing coverage for the target area. Our previous work reported in [6] attempted to find the best cover to maintain a full coverage of the network with the least number of working nodes, and a NSGA-II based approach was proposed. The coverage problem is also explored in [7], and a distributed, localized algorithm, called OGDC (Optimal Geographical Density Control), is proposed to maintain coverage as well as connectivity. They prove that if the communication range is at least twice the sensing range, complete coverage implies connectivity. In particular, the jointly coverage and connectivity problem is studied in [8], and a sleep-awake scheduling scheme is proposed for energy conservation and surveillance quality provisioning. In [10], the coverage maintenance protocol named as PCP is proposed, and the simulation results show that it can significantly save the number of activated sensors by using probabilistic sensing model.

These algorithms all focused on finding a uniform distribution, thus to reduce the number of working nodes. However, as the sensors closer to the sink tend to carry more traffic loads and thus would consume more energy, the uniform deployment will cause the network lifetime descended by the sensors at the first-hop from the sink. This is also known as the “energy hole” problem, which is characterized by a mathematical model in [11]. Apparently, it cannot prolong the system lifetime under a uniform distribution by simply increasing the number of nodes. The authors in [12– 14] have also investigated several approaches to mitigate this problem. In [12], the authors present a mathematical model and aim to investigate some approaches towards mitigating this energy hole problem. However, the uneven energy depletion still exists, even by using their mere system design and the associated routing strategy. The authors in [13] investigated the energy hole problem and designed guidelines for maximizing lifetime and avoiding energy holes in sensor networks with nonuniform distribution. In [14], the authors proposed a nonuniform deployment scheme based on a general sensor application model. They derived a formula to determine the number of nodes as a function of the distance from the sink. Simulation results show that their method can enhance the network lifetime. Since each sensor was also assumed to report the data to the sink with the same acquisition rate, it cannot achieve the energy balance completely in the entire network.

3. Preliminaries

3.1. Assumptions and Network Model

In this section, we present our network model and basic assumptions. Assume that a set ofN heterogeneous sensors are deployed in a circular area with radiusd in order to monitor some physical phenomenon. We refer to the complete set of sensors that has been deployed as $S = {s_{1}, s_{2}, \dots, s_{N}}$ . Each sensor node has an ID, a fixed transmission range $R_{c}$ , and a fixed sensing range $R_{s}$ . Note that the location awareness is impractical in the highly dense network. In recent years, many research efforts have been made to address the localization problem [15– 18]. However, this requirement can be relaxed slightly in our work if each node is aware of its relative location to the neighbours. The only sink node is located at the centre of the circle, as shown in Figure 1. We divide the area inton adjacent coronas with the same width of $R_{c}$ and denote theith corona by $C_{i}$ . Obviously, the corona $C_{i}$ is composed of nodes whose distances to the sink are between $(i - 1) * R_{c}$ and $i * R_{c}$ .

Figure 1

A circular target area with four coronas.

The network works in rounds, and each round is further divided into two phases: the first phase of node selection and the second phase of stability monitoring. In the first phase, the suitable sensor nodes are selected to work and the rest of the nodes are set to sleep state thus to save energy. During the second phase, each working node should send their sensing messages to the sink node per unit monitoring cycle $Δ T$ . In order to avoid retransmitting the same messages in cross-covered areas, each sensor needs to check its own Voronoi polygon through the establishment of Voronoi graph with its neighbours before sending any data. In our work, this mechanism is called as the pixel-based transmission mechanism, which can ensure that the information data for any pixel in the target area is sent only once.

We use a simplified power consumption model and do not consider the MAC layer and physical layer issues. In our model, the energy consumption is only dominated by communication costs, as opposed to sensing and processing costs. The initial energy of each sensor is $ε > 0$ , and the sink has no energy limitation. A node consumes $e_{1}$ units of energy when sending one bit, while it depletes $e_{2}$ units of energy when receiving one bit, where $e_{1} > e_{2} > 0$ .

3.2. Nonuniform Node Distribution

Based on the network model, nodes belonging to corona ${C_{i} | i \neq n}$ will forward both the data generated by themselves and the data generated by coronas ${C_{j} | (i + 1) \leq j \leq n}$ while the nodes in the outermost corona $C_{n}$ need not forward any data. Assume that the sensors in each corona are distributed uniformly and there is no data aggregation at any forwarding nodes. Define the number of nodes deployed in corona $C_{i}$ to be $N_{i}$ and the number of pixels in corona $C_{i}$ to be $A_{i}$ . Based on the pixel-based transmission mechanism, the number of messages for corona $C_{i}$ to receive and forward is $(A_{i + 1} + A_{i + 2} + \dots + A_{n})$ and $(A_{i} + A_{i + 1} + \dots + A_{n})$ . As the sensing messages are transmitted per monitoring cycle $Δ T$ , the average energy consumption for sensors in corona $C_{i}$ during $Δ T$ is

{\overset{̅}{E}}_{i} = \frac{[\sum_{k = i + 1}^{n} A_{k} (e_{1} + e_{2}) + A_{i} e_{1}]}{N_{i}}, 1 \leq i \leq n - 1 .

(1)

Note that (1) can be simplified as

{\overset{̅}{E}}_{i} = \frac{e_{1}}{ρ_{i}} + \frac{A_{i + 1} + A_{i + 2} + \dots + A_{n}}{A_{i} \cdot ρ_{i}} (e_{1} + e_{2}), 1 \leq i \leq n - 1,

(2)

where

ρ_{i}

is the node density of corona

C_{i}

Sensors in corona $C_{n}$ only need to send their own sensing messages; so the energy depletion of sensors in corona $C_{n}$ is

{\overset{̅}{E}}_{n} = \frac{{A_{n} \cdot e}_{1}}{N_{n}} = \frac{e_{1}}{ρ_{n}} .

(3)

Thus, we can formulate ${\overset{̅}{E}}_{i}$ as follows:

{\bar{E}}_{i} = {\begin{cases} \frac{e_{1}}{ρ_{n}}, & i = n, \\ \frac{e_{1}}{ρ_{i}} + \frac{\sum_{i = k + 1}^{n} A_{i}}{A_{i} \cdot ρ_{i}} (e_{1} + e_{2}), & 1 \leq i \leq n - 1 . \end{cases}

(4)

Ideally, when all the nodes deplete their energy with the same ratio, the network lifetime is prolonged and the energy efficiency is improved. In particular, there is no energy wasted and the network lifetime can be given by

\frac{ε}{{\overset{̅}{E}}_{1}} = \frac{ε}{{\overset{̅}{E}}_{2}} = \dots = \frac{ε}{{\overset{̅}{E}}_{i}} = \dots = \frac{ε}{{\overset{̅}{E}}_{n}} .

(5)

Theorem 1.

Maximum energy efficiency is possible, in the sense that all the working nodes take the pixel-based transmission mechanism, and the node distribution densityρ _i in corona C_i satisfies

ρ_{i} = ρ_{n} \cdot [1 + \frac{(n^{2} - i^{2}) \cdot (e_{1} + e_{2})}{(2 i - 1) \cdot e_{1}}], ρ_{1} \geq ρ_{2} \geq \dots \geq ρ_{n} .

(6)

Proof.

To use the deductive method, suppose that (6) is true, and thus (2) can be described as follows:

\begin{matrix} {\overset{̅}{E}}_{i} & = \frac{A_{i} \cdot e_{1} + \sum_{k = i + 1}^{n} A_{k} \cdot (e_{1} + e_{2})}{A_{i} \cdot ρ_{i}} \\ = \frac{[A_{i} \cdot e_{1} + \sum_{k = i + 1}^{n} A_{k} \cdot (e_{1} + e_{2})] \cdot (2 i - 1) \cdot e_{1}}{A_{i} \cdot ρ_{n} \cdot [(2 i - 1) \cdot e_{1} + (n^{2} - i^{2}) \cdot (e_{1} + e_{2})]} . \end{matrix}

(7)

Owing to $A_{i} = π {R_{c}}^{2} \cdot (2 i - 1)$ , after basic transformations, we have

\begin{matrix} {\overset{̅}{E}}_{i} & = \frac{[(2 i - 1) \cdot e_{1} + (n^{2} - i^{2}) \cdot (e_{1} + e_{2})] \cdot (2 i - 1) \cdot e_{1}}{(2 i - 1) \cdot ρ_{n} \cdot [(2 i - 1) \cdot e_{1} + (n^{2} - i^{2}) \cdot (e_{1} + e_{2})]} \\ = \frac{e_{1}}{ρ_{n}} = {\overset{̅}{E}}_{n} . \end{matrix}

(8)

Since $d ρ_{i} / d i = - 2 i / (2 i - 1) - 2 (n^{2} - i^{2}) / (2 i - 1)^{2} < 0$ is a permanent establishment, we can get the following conclusion, $ρ_{1} \geq ρ_{2} \geq \dots \geq ρ_{n}$ . This completes the proof of Theorem 1.

Theorem 1 shows that in a circular monitored area, based on the pixel data transmission mechanism, if the sensors in each corona obey a nonuniform distribution and the distribution density meets a certain condition, the energy-balanced depletion of the whole network can be achieved. Besides, the node density $ρ_{i}$ of corona $C_{i}$ only relates to $ρ_{n}$ of corona $C_{n}$ and the corona numberi.

Further we will analyze the lifetime enhancement of the nonuniform distribution strategy to the traditional one. Suppose that the node density in nonuniform distribution satisfies (6) and the initial conditions are the same. In the uniform distribution, the density $ρ_{i}$ is equal to $ρ_{n}$ . As the innermost corona $C_{1}$ needs to forward all of the sensing messages in the whole network, it consumes the most energy. Thus the maximum lifetime of network in uniform distribution is determined by the survival time $C_{1}$ . The network lifetime can be calculated as

\begin{matrix} \frac{ε}{\overset{̅}{E_{1}^{'}}} & = \frac{ε}{e_{1} / ρ_{n} + (\sum_{j = 2}^{n} A_{j} / A_{1} \cdot ρ_{n}) (e_{1} + e_{2})} \\ = \frac{ρ_{n} \cdot ε}{e_{1} + (n^{2} - 1) \cdot (e_{1} + e_{2})}, \end{matrix}

(9)

where

\overset{̅}{E_{1}^{'}}

is the average energy depletion of

C_{1}

per unit time in uniform distribution. Using (8), we can get the average energy depletion in

C_{1}

under energy-balanced conditions as

{\overset{̅}{E}}_{1} = {\overset{̅}{E}}_{2} = \dots {\overset{̅}{E}}_{i} = \dots = {\overset{̅}{E}}_{n} = \frac{e_{1}}{ρ_{n}} .

(10)

Thus the lifetime enhancement is

\frac{ε / {\overset{̅}{E}}_{1}}{ε / \overset{̅}{E_{1}^{'}}} = \frac{(e_{1} + (n^{2} - 1) \cdot (e_{1} + e_{2})) / ρ_{n}}{e_{1} / ρ_{n}} = \frac{ρ_{1}}{ρ_{n}} > 1 .

(11)

Therefore, the network lifetime of nonuniform distribution can be extended $ρ_{1} / ρ_{n}$ times effectively compared with the traditional uniform distribution strategy.

4. Energy-Balanced Density Control

4.1. Problem Formulation

The problem of Energy-Balanced Density Control (EBDC) is formalized as follows. Given a set ofN potential sensors, $S = {s_{1}, s_{2}, \dots, s_{N}}$ , find a subset $cov \subset S$ , which achieves a nonuniform sensor distribution satisfying (6), and the number of sensors $K_{cov} = | cov |$ is minimized with a full coverage. The subset $cov$ is named as the energy balance working cover for the target area.

4.2. Density Control Based on Equivalent Sensing Radius

The proposed algorithm, called EBDC, is inspired by the algorithm introduced in [7]. As a contribution, we made major modifications with the purpose of selecting sensors at variable densities according to (6).

Definition 2 (Equivalent sensing radius).

It is defined as the sensing radius when the given distribution density $ρ_{i}$ is the lowest one to maintain network coverage.

As the hexagonal distribution is the optimal sensor distribution to fully cover the target area with the fewest sensors, define $Hex (i)$ to be the hexagonal area covered by sensori with the sensing radius $R_{i} \cdot Hex (i)$ can be calculated as

Hex (i) = \frac{3 \sqrt{3}}{2} R_{i}^{2} .

(12)

And the minimum distribution density $ρ_{i}$ to fully cover the area is

ρ_{i} = \frac{1}{Hex (i)} .

(13)

Thus, the relationship of the equivalent sensing radius and the distribution density $ρ_{i}$ is

R_{i} = \sqrt{\frac{2}{\sqrt{27} \cdot ρ_{i}}} .

(14)

Theorem 3.

If the sensor selection algorithm uses the equivalent sensing radius $R_{i}$ according to the density $ρ_{i}$ , the network can achieve balanced energy depletion, where $R_{i}$ satisfies

\begin{matrix} R_{i} = R_{s} \sqrt{\frac{(2 i - 1) \cdot e_{1}}{(2 i - 1) \cdot e_{1} + (n^{2} - i^{2}) \cdot (e_{1} + e_{2})}}, \\ R_{1} \leq R_{2} \leq \dots \leq R_{n} . \end{matrix}

(15)

Proof.

According to the definition of equivalent sensing radius, we can combine it with the energy-balanced condition in (6). Thus we have

\begin{matrix} ρ_{i} & = \frac{2}{\sqrt{27} \cdot {R_{i}}^{2}} \\ = \frac{2}{\sqrt{27} \cdot {R_{s}}^{2}} \cdot [1 + \frac{(n^{2} - i^{2}) \cdot (e_{1} + e_{2})}{(2 i - 1) \cdot e_{1}}] . \end{matrix}

(16)

After transformation, we have

R_{i} = R_{s} \cdot \sqrt{\frac{(2 i - 1) \cdot e_{1}}{(2 i - 1) \cdot e_{1} + (n^{2} - i^{2}) \cdot (e_{1} + e_{2})}} .

(17)

This concludes the proof of Theorem 3.

Therefore, by introducing the concept of equivalent sensing radius, the problem of EBDC can be transformed into a uniform density control problem with different sensing radius, which gives the chance of using the existing schemes to solve it. In this paper, the density control algorithm is combined with OGDC approach, which only needs relative location during node selection.

In order to make sure that the node selected in each corona satisfies hexagonal distribution with its equivalent sensing radius, first, each sensor needs to know which corona is located. The calculation mechanism of corona number is presented in Section 4.2.1. And then the optimal principle for sensor selection is adopted [7]: anytime when a sensor in corona $C_{i}$ is active, the next active node with the distance of $\sqrt{3} R_{i}$ away from the first one will be selected, and a similar selection method is used for the third node. Ideally, the centres of the three sensors should form an equilateral triangle with edge $\sqrt{3} R_{i}$ .

4.2.1. Calculation of Corona Number

Since the sensors are deployed with high density, there are challenges to calculating each sensor's location and measuring the distance between sensor nodes accurately. Moreover, it seems to be impossible for sensor $s_{i}$ to calculate corona number based on the distance $dist (s_{i}, sink)$ . On the other hand, as the corona number is equal to the minimum hop count from each sensor to sink, the corona number for each sensor can be calculated simply on the basis of its minimum hop count through routing. In our paper, this minimum hop count is calculated by using DV-hop localization algorithm [16].

The calculation of minimum hop count in DV-hop localization algorithm is similar to classical distance vector routing. At first, the sink node broadcasts a beacon to be flooded throughout the network containing its position with a hop-count parameter, which is initialized to be one. Then, each receiving node maintains the minimum counter value per anchor of all the beacons received and ignores those with higher hop-count values. At every intermediate hop, beacons are flooded outward with hop-count values incremented. Through this mechanism, all of the sensor nodes can get the minimum hops to the sink. The calculation of corona number based on hop count is shown in Figure 2.

Figure 2

The calculation of corona number.

4.2.2. Selection of the Starting Node

After all the sensors calculated their corona number and the corresponding equivalent sensing radius, they are powered on with undecided status. Then the node volunteer whose energy exceeds a predetermined power threshold $P_{t}$ will become a starting node with probabilityp, where $P_{t}$ is related to the length of the round. In general, it is set to a value so as to ensure that the sensor can remain powered on until the end of the round with high probability. And then, a back-off timer of $τ_{1}$ seconds is set, where $τ_{1}$ is distributed uniformly in $[0, T_{d}]$ . When the timer expires, the node turns into the “ON” state and broadcasts a power-on message meanwhile. The power-on message is a quaternary array of $〈$ location, $R_{i}$ ,Corona_Num, $α 〉$ , indicating the location of sensor, the equivalent sensing radius, the serial corona number, and the angle of next node. Note thatα is used to determine the direction along which the second working node should be located. It is uniformly distributed in $[0, α_{d}]$ , where $α_{d}$ represents the direction range of the next selecting nodes and is related to the location of the first selecting node. In the next section, we will give a detailed description of how to calculate $α_{d}$ . A message-driven mechanism is used in the wake-up process. If the initial candidate node receives power-on messages before the back-off time finishes, its timer is cancelled and this node cannot become a starting node. This method helps to avoid many neighbours to become the starting node at the same time effectively. If the node does not volunteer itself to be a starting node, a timer of $T_{s}$ seconds will be set to a sufficiently large value, such that there is at least one node whose power level qualifying to be a starting node and the selection of working nodes can be completed in an early stage of each round.

4.2.3. Actions Taken When Receiving a Power-on Message

When a node receives a power-on message, it first checks whether theCorona_Num are equal. If this message comes from an adjacent corona, and the receiving node is not “ON”, or there are not any uncovered crossings, it will omit this message and sets itself to “OFF” state. Otherwise, it will become a starting node of its corona and transmits a new power-on message with newCorona_Num and a new equivalent sensing radius. If the power-on message comes from the same corona, the subsequent actions taken are to ensure that the working sensors selected form a hexagon distribution.

Similar to OGDC, $T_{c 1}$ , $T_{c 2}$ , and $T_{c 3}$ are back-off timers indicating the different retreated actions in different cases. In any of the above three cases, when the back-off timer expires, the node sets its state to “ON” and broadcasts a power-on message with a new direction fieldα set to −1 (indicating a message generated by a nonstarting node). The whole procedure of a node receiving a power-on message is shown in Figure 3.

Figure 3

Flowchart of the actions taken after receiving a power-on message.

4.2.4. Direction Range $α_{d}$ in Power-on Message

The parameterα in power-on message indicates the direction along which next working node hoping to be activated. In terms of large coverage area,α is distributed uniformly in $[0, 2 π]$ . In order to distinguish the power-on message from starting nodes or nonstarting nodes, we set the latterα to −1. In terms of the node selection in different coronas with different equivalent sensing radius, the ratio of corona width to equivalent sensing radius $R_{c} / R_{i}$ cannot be ignored. Therefore, when the OGDC scheme is implemented in each corona with $R_{i}$ , the boundary effect must be considered. Furthermore, in order to speed the dissemination of power-on message in the same corona, it is also need to control the direction range $α_{d}$ .

Define the coordinate of candidate starting sensor as $A (x_{a}, y_{a})$ , and the sink as $(x_{0}, y_{0})$ . Firstly, the distance betweenA and sink is calculated, and then the corona serial number as well as the equivalent sensing radius $R_{i}$ is determined according to dist(A, sink). Based on this point, we can calculate the direction range $α_{d}$ as follows: if the sensing disc centred atA with radius $\sqrt{3} R_{i}$ has at most one crossing point with the inner or outer boundary of corona $C_{i}$ , $α_{d}$ is set to $2 π$ , as shown in Figure 4(a). Otherwise, we have one of the three cases, as depicted from Figure 4(b) to Figure 4(d): (i) there exists two crossing points between the sensing disc and the inner border of the outer adjacent corona; (ii) there exists two crossing points between the sensing disc and the outer border of the inner adjacent corona; (iii) there exists four crossing points between the sensing disc and the border of both inner and outer adjacent coronas.

Figure 4

The possible intersection between sensing disc and the corona borders. (a) At most one crossing point. (b) Two crossing points between the sensing disc and the inner border of the outer adjacent corona. (c) Two crossing points between the sensing disc and the outer border of the inner adjacent corona. (d) Four crossing points between the sensing disc and the border of both inner and outer adjacent coronas.

If case (i) satisfies, we have $\sqrt{(x_{a} - x_{0})^{2} + (y_{a} - y_{0})^{2}} + \sqrt{3} R_{i} > i \cdot R_{c}$ and $\sqrt{(x_{a} - x_{0})^{2} + (y_{a} - y_{0})^{2}} - \sqrt{3} R_{i} > (i - 1) \cdot R_{c}$ , as shown in Figure 4(b). The intersection coordinates can be obtained by the following formulation:

\begin{gathered} {(x - x_{a})}^{2} + {(y - y_{a})}^{2} = 3 {R_{i}}^{2}, \\ {(x - x_{0})}^{2} + {(y - y_{0})}^{2} = {(i \cdot R_{c})}^{2} . \end{gathered}

(18)

Assuming the calculated crossing points as $A_{1} (x_{1}, y_{1})$ and $A_{2} (x_{2}, y_{2})$ , the direction range $α_{d}$ is given by $\tan^{- 1} ((y_{1} - y_{a}) / (x_{1} - x_{a})) ~ π + ta n^{- 1} ((y_{2} - y_{a}) / (x_{2} - x_{a}))$ .

If case (ii) satisfies, we have $\sqrt{(x_{a} - x_{0})^{2} + (y_{a} - y_{0})^{2}} + \sqrt{3} R_{i} < i \cdot R_{c}$ and $\sqrt{(x_{a} - x_{0})^{2} + (y_{a} - y_{0})^{2}} - \sqrt{3} R_{i} < (i - 1) \cdot R_{c}$ , as shown in Figure 4(c). The intersection coordinates can be obtained by the following formulation:

\begin{gathered} {(x - x_{a})}^{2} + {(y - y_{a})}^{2} = 3 {R_{i}}^{2}, \\ {(x - x_{0})}^{2} + {(y - y_{0})}^{2} = {[(i - 1) \cdot R_{c}]}^{2} . \end{gathered}

(19)

Assuming the calculated crossing points as $A_{1} (x_{1}, y_{1})$ and $A_{2} (x_{2}, y_{2})$ , the direction range $α_{d}$ is given by $(0 ~ \tan^{- 1} ((y_{1} - y_{a}) / (x_{1} - x_{a}))) \cup (π + ta n^{- 1} ((y_{2} - y_{a}) / (x_{2} - x_{a})) ~ 2 π)$ .

If case (iii) satisfies, we have $\sqrt{(x_{a} - x_{0})^{2} + (y_{a} - y_{0})^{2}} + \sqrt{3} R_{i} > i \cdot R_{c}$ and $\sqrt{(x_{a} - x_{0})^{2} + (y_{a} - y_{0})^{2}} - \sqrt{3} R_{i} < (i - 1) \cdot R_{c}$ , as shown in Figure 4(d). The intersection coordinates can be obtained by the following formulation:

\begin{gathered} \begin{matrix} {(x - x_{a})}^{2} + {(y - y_{a})}^{2} = 3 {R_{i}}^{2}, \\ {(x - x_{0})}^{2} + {(y - y_{0})}^{2} = {(i \cdot R_{c})}^{2}, \end{matrix} \\ \begin{matrix} {(x - x_{a})}^{2} + {(y - y_{a})}^{2} = 3 {R_{i}}^{2}, \\ {(x - x_{0})}^{2} + {(y - y_{0})}^{2} = {[(i - 1) \cdot R_{c}]}^{2} . \end{matrix} \end{gathered}

(20)

Using $A_{1} (x_{1}, y_{1})$ , $A_{2} (x_{2}, y_{2})$ , $A_{3} (x_{3}, y_{3})$ , and $A_{4} (x_{4}, y_{4})$ to represent the calculated crossing points, we can get the direction range $α_{d}$ :

\begin{matrix} (\tan^{- 1} (\frac{y_{1} - y_{a}}{x_{1} - x_{a}}) ~ \tan^{- 1} (\frac{y_{2} - y_{a}}{x_{2} - x_{a}})) \\ \cup (π + \tan^{- 1} (\frac{y_{3} - y_{a}}{x_{3} - x_{a}}) ~ π + \tan^{- 1} (\frac{y_{4} - y_{a}}{x_{4} - x_{a}})) . \end{matrix}

(21)

After the direction range $α_{d}$ is set, the nodes along $α_{d}$ will be selected first, like nodesD andC in Figure 4(d). When nodeA becomes the power-on node,D andC will be the following active nodes to form a hexagonal distribution. We should note that although the node selection along range will result in the region out of $α_{d}$ being uncovered originally, with the dissemination of the power-on message in the adjacent coronas, finally, it will be fully covered by the node in its adjacent coronas. Take nodeB in Figure 4(d) as an example. When nodeB receives a power-on message from nodeA, it will become the new starting node in corona $C_{i - 1}$ according to Figure 2, thus to cover the shadow area in corona $C_{i}$ . To summarize, by calculating the direction range, we can achieve a rapid selection of the working nodes in the same corona and reduce the number of invalid power-on messages effectively.

5. Simulations Results

In this section, we evaluate the performance of the proposed density control algorithm. The basic simulation parameters are listed in Table 1.

Table 1

Simulation parameters.

Parameters	value
Initial energy of sensor node (ε)	1000 J
Energy consumed to send one bit of data ( $e_{1}$ )	0.5/10³ J
Energy consumed to receive one bit of data $(e_{2})$	0.25/10³ J
The basic unit of data length (L)	1000 Bit
Monitoring area radius (R)	60
The number of nodes deployed	1000–3000
Communication radius ( $R_{c}$ )	20
Sensing radius ( $R_{s}$ )	10
Recombination rate	0.9
Working roundT	1000 s
Monitoring cycle $Δ T$	3 s
The threshold of working node energy (used to maintain the energy level of dormancy) ( $P_{t}$ )	900 s
Time of the initial node from timer ( $T_{d}$ )	10 ms
Time of the initial node selection process ( $T_{s}$ )	1 s
Time of receiving the power-on message from the first noninitial node and the working area of node not covered by its neighbours ( $T_{c 3}$ )	200 ms
Power-on message sending time	6.8 ms
Time of calculation $T_{c 1}$ and $T_{c 2}$ required constantC	10/rs²

Initially, in order to deploy more nodes close to the sink node, the deployment model of two-dimensional Gaussian distribution is adopted. Given the coordinate of sink as $(x_{0}, y_{0})$ , the node deployment density follows:

f (x, y) = f (x - x_{0}, y - y_{0}) = \frac{1}{2 π σ^{2}} e^{- [(x - x_{0})^{2} + (y - y_{0})^{2}] / 2 σ^{2}},

(22)

whereσ is the standard deviation of coordinate

(x, y)

, and it is equal to the communication radius

R_{c}

in our simulation.

As the finally selected nodes obey approximate uniform distribution in the corona in each round, the sensing data forwarding strategy is similar to [13]. Any node in corona $C_{i}$ can communicate with almostq nodes in the ring $C_{i - 1}$ directly, where $q_{i} = ρ_{i - 1} \cdot A_{i - 1} / ρ_{i} \cdot A_{i}$ . Among these $q_{i}$ candidate forwarding nodes, the node with most residual energy will be selected as the forwarding node.

There are 1000 potential sensors randomly distributed in the circular area of radius 60 using Gaussian distribution deployment model, as shown in Figure 5(a). The target area is divided into three coronas denoted by $C_{1}$ , $C_{2}$ , and $C_{3}$ . From (17), we can calculate the equivalent sensing radius from $C_{1}$ to $C_{3}$ to be 2.8, 5.28, and 10.

Figure 5

Distribution of wireless sensor network.

Figure 5(b) shows the working sensors selected after running NSGA-II 500 generations. The number of working nodes selected from corona $C_{1}$ to $C_{3}$ is 24, 53, and 59. Further, those working sensors in Figure 5(b) are renamed as 1, 2, 3,…, 136, where the sensors with the larger IDs belong to outer coronas and those with smaller IDs are closer to sink node.

In order to verify that the working sensors selected by our algorithm can balance energy consumption, the energy depletion of this working set in one round is investigated especially. In our simulation, the working round is set as 1000 s, and the monitoring cycle is 3 s. The energy depletion of those nodes in one working round is shown in Figure 6.

Figure 6

Energy consumption of the working nodes in one round.

From Figure 6, we can see that although the nodes in corona $C_{1}$ and $C_{2}$ behave as both data originator and router, the energy consumption of the whole working set is almost equal, thus to enhance the power efficiency of sensors in outer coronas. This is mainly because the inner sensors' sensing pixels are much smaller than those of the outer sensors by adopting nonuniform sensor distribution and pixel-based transmission mechanism.

Figure 7 shows the relationship between the total energy left and working rounds. From Figure 7, we can see that the total energy left with working rounds has an approximate linear relation. When the network runs to 150 working rounds, the remaining energy is 102300. Continuing to run algorithm, we can see that the energy attenuation with the working cycles becomes more flat. That is because the remaining survival nodes can no longer establish communication with the sink node, and the energy consumption is mainly caused by network sensing with little data forwarding. Although there is about 10% of the residual energy, due to the uneven distribution of these final survival nodes, they cannot meet the needs of the network coverage and connectivity any more.

Figure 7

Changes of energy left in different working rounds.

We further compare the performance of EBDC with OGDC, PCP, and the nonuniform distribution in [13]. In those series of simulations, we vary the deployed nodes density from 1000 to 3000 nodes in the circular area with radius 60. The round length is set as 1000 s and the monitoring cycle is 3 s.

Figure 8 shows the network lifetime comparison with different node deployments. Although OGDC focuses on how to select the optimal cover set, it does not consider the imbalance consumption of energy near the sink. This mainly causes the nodes near the sink node to forward data more frequently and finally gets a much shorter network lifetime. As PCP uses a probabilistic detection model, it needs fewer active sensors to cover the target area completely and thus has more working rounds than OGDC. However, the problem of imbalanced energy depletion is not solved effectively in PCP. Although literature [13] adopts a nonuniform node distribution, the energy imbalance still exists because of constant data acquisition, which inevitably leads inner sensors consume more energy than outer sensors. As the pixel-based transmission mechanism is imported in our scheme, the total transmitted messages in each round are much smaller. Our algorithm can achieve the energy balance by selecting suitable nodes to work and thus has a much longer network lifetime.

Figure 8

The number of nodes deployed versus working cycles.

Figure 9 shows the comparison of the energy unused ratio with different deployed nodes, which refers to the ratio of the residual energy to the total energy at the end of the network lifetime. With the increase of deployed nodes in the network, the energy unused ratio shows a downward tendency using our algorithm. This is because that the energy consumption of each node selected by our algorithm in each working cycle is almost equal. The energy unused is mainly caused by the initially uneven distribution of nodes. The more nodes deployed, the more chance can be got for the survival nodes connecting to the sink and thus reduce the energy unused ratio. Since OGDC and PCP adopt a uniform node selection strategy and do not consider the phenomenon of energy imbalance consumption, both of them have a large energy unused ratio. Actually, as the nonuniform distribution strategy does not take the pixel-based data transmission mechanism, the energy imbalance cannot be avoided. Compared with the above methods, our density control algorithm based on energy balance has the higher-energy efficiency, which verifies the effectiveness of the algorithm.

Figure 9

Comparison of energy unused ratio with different deployed nodes.

6. Conclusion

In this paper, we have investigated the density control problem to select the energy-balanced working nodes for sensor networks. We analyze energy attenuation in nonuniform distribution strategy theoretically and prove that when the pixel-based transmission mechanism is adopted, a full energy balance can be achieved through the rational node distribution density. Contributively, a distributed nonuniform density control algorithm with the concept of equivalent sensing radius is proposed. Simulation results show that our algorithm has a better performance than the existing algorithms and can prolong the network lifetime effectively.

In the future, as our work requires that each node knows its relative locations, we plan to investigate more deeply the impact of location on the performance of the proposed approach. We also intend to extend EBDC to the probabilistic sensing models and investigate some potential applications of EBDC such as topology control, distributed storage, and network health monitoring.

Footnotes

Acknowledgment

The authors would like to thank the reviewers giving valuable comments on the earlier version of this paper. This work is supported by the National Natural Science Foundation of China under Grant nos. 60903159, 61173153, 61070162, 71071028, and 70931001; China Postdoctoral Science Foundation funded project under Grant no. 20110491508; the Specialized Research Fund for the Doctoral Program of Higher Education under Grant no. 20070145017; and the Fundamental Research Funds for the Central Universities under Grant nos. N090504003 and N090504006.

References

Akyildiz

I. F.

Weilian

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 114

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

Jiang

Dou

A coverage-preserving density control algorithm for wireless sensor networks

3158

Proceedings of the 3rd International Conference on Ad Hoc Networks and Wireless

2004

LNCS

42 55

Slijepcevic

Potkonjak

Power efficient organization of wireless sensor networks

Proceedings of the IEEE International Conference on Communications, (ICC '01)

June 2000

IEEE

472 476

Zhong

Cheng

Zhang

PEAS: a robust energy conserving protocol for long-lived sensor networks

Proceedings of the 23th IEEE International Conference on Distributed Computing Systems, (ICDCS '03)

May 2003

IEEE

28 37

Tian

Georganas

N. D.

A coverage-preserving node scheduling scheme for large wireless sensor networks

Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, (WSNA '02)

September 2002

ACM

32 41

2-s2.0-0036983403

Jia

Chen

Chang

G. R.

Wen

Y. Y.

Efficient cover set selection in wireless sensor networks

Acta Automatica Sinica 2008 34 9 1157 1162

2-s2.0-53649103866

10.3724/SP.J.1004.2008.01157

Zhang

Hou

J. C.

Maintaining sensing coverage and connectivity in large sensor networks

Adhoc and Sensor Wireless Networks 2005 1 1 89 124

Keshavarzian

Lee

Venkatraman

Wakeup scheduling in wireless sensor networks

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, (MOBIHOC '06)

May 2006

ACM

322 333

2-s2.0-33748034055

Wadaa

Olariu

Wilson

Eltoweissy

Jones

Training a wireless sensor network

Mobile Networks and Applications 2005 10 1 151 168

2-s2.0-17444366210

10.1023/B:MONE.0000048552.15853.c2

10.

Hefeeda

Ahmadi

Energy-efficient protocol for deterministic and probabilistic coverage in sensor networks

IEEE Transactions on Parallel and Distributed Systems 2010 21 5 579 593

2-s2.0-77950629206

10.1109/TPDS.2009.112

11.

Mohapatra

An analytical model for the energy hole problem in many-to-one sensor networks

Proceedings of the 62nd Vehicular Technology Conference, (VTC '05)

September 2005

IEEE

2721 2725

12.

Olariu

Stojmenovic

Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting

Proceedings of the 25th IEEE International Conference on Computer Communications, (INFOCOM '06)

April 2006

IEEE

1 12

13.

X. B.

Chen

G. H.

The energy hole problem of nonuniform node distribution in wireless sensor networks

Chinese Journal of Computers 2008 31 2 253 261

2-s2.0-40949088039

14.

Cardei

Yang

Non-uniform sensor deployment in mobile wireless sensor networks

Proceedings of the International Symposium on a World of Wireless, Mobile and Multimedia Networks, (WoWMoM '08)

June 2008

1 8

2-s2.0-52049098498

10.1109/WOWMOM.2008.4594823

15.

Savvides

Han

C. C.

Strivastava

M. B.

Dynamic fine-grained localization in ad-hoc networks of sensors

Proceedings of the seventh annual international conference on Mobile computing and networking, (Mobicom '01)

July 2001

166 179

2-s2.0-0034775930

16.

Niculescu

Nath

DV based positioning in ad hoc networks

Telecommunication Systems 2003 22 1–4 267 280

2-s2.0-0038703640

10.1023/A:1023403323460

17.

Sugihara

Gupta

R. K.

Sensor localization with deterministic accuracy guarantee

Proceedings of the 30th International Conference on Computer Communications, (INFOCOM '11)

June 2011

1772 1780

18.

Jin

Xia

Scalable and fully distributed localization with mere connectivity

Proceedings of the 30th International Conference on Computer Communications, (INFOCOM '11)

June 2011

3164 3172

Energy-Balanced Density Control to Avoid Energy Hole for Wireless Sensor Networks

Abstract

1. Introduction

2. Related Work

3. Preliminaries

3.1. Assumptions and Network Model

3.2. Nonuniform Node Distribution

Theorem 1.

Proof.

4. Energy-Balanced Density Control

4.1. Problem Formulation

4.2. Density Control Based on Equivalent Sensing Radius

Definition 2 (Equivalent sensing radius).

Theorem 3.

Proof.

4.2.1. Calculation of Corona Number

4.2.2. Selection of the Starting Node

4.2.3. Actions Taken When Receiving a Power-on Message

4.2.4. Direction Range α d in Power-on Message

5. Simulations Results

6. Conclusion

Footnotes

Acknowledgment

References

4.2.4. Direction Range $α_{d}$ in Power-on Message