Sage Journals: Discover world-class research

Abstract

Balanced energy depletion is an important way to prolong network lifetime for wireless sensor networks. Traditional algorithms mainly aim at maximizing network coverage rate with uniform sensor node distribution. However, wireless sensor network is characterized by many-to-one traffic pattern and multihop communication, which usually lead to the energy hole problem in the region around the sink node. In this paper, we investigate the problem of joint placement for both relays and sensors to eliminate energy hole. We first theoretically conclude that balanced energy depletion is achievable with rational designed deployment density for relay nodes. We then propose a novel relay deploying strategy as well as a data routing scheme to eliminate uneven energy depletion. Extensive simulations are presented to verify that our approach outperforms other schemes in terms of both network lifetime and unused energy ratio.

1. Introduction

Recent advancement in large-scale integrated circuits and radio spectrum technology has enabled the development and application of wireless sensor networks. A wireless sensor network usually consists of a large number of tiny sensor nodes with sensing, data processing, and communication components. In general, it is formed by these sensor nodes in a self-organized manner. In recent years, wireless sensor network is playing an increasingly important role in many application fields, such as medical, outer space exploration, volcano surveillance, and intelligence applications [1].

Be aware that whatever happened in the target area timely is one of the most important responsibilities for the wireless sensor network. Sensor nodes are usually able to measure various parameters of the environment and transmit collected data to the sink node through multihop communication. Once the sensor node receives sensed data, it processes and forwards it to the sink node [2]. In order to monitor the interested field preferably and achieve a higher coverage rate, sensors are usually deployed uniformly with a certain density over the target area. However, since the traffic in wireless sensor network follows a many-to-one pattern, the sensors that are nearer to the sink node not only need to send their own data but also to forward data collected by other sensors far away from the sink. As a result, sensors near the sink node will consume more energy and die more quickly. Once those sensors use up their own energy, the whole network would get disconnected and no more data can be transmitted to the sink. This may result in network partitioning and decreasing network lifetime. Consequently, a considerable amount of energy is wasted when the network lifetime ends up [3]. Experimental results in [4] show that up to 93% of the total initial energy is left unused when the network lifetime ends up with uniform sensor distribution. Hence, how to eliminate the uneven energy consumption so as to prolong the network lifetime becomes an urgent issue in wireless sensor network.

In this paper, we try to eliminate uneven energy consumption for wireless sensor network. At first, the relay nodes are introduced into wireless sensor networks. A novel placement scheme for both sensor and relay nodes is proposed to achieve energy balanced depletion. In summary, the main contributions of our work are listed as follows: (1) we theoretically analyze accessibility condition of deploying relay sensors to satisfy that all the working sensors exhaust their energy with the same ratio; (2) we also analyze the extension of network lifetime compared with traditional schemes; (3) we propose a novel relay nodes placement strategy combined with routing schemes to satisfy energy balance depletion condition; and (4) we conduct extensive simulations to verify that by separating the data acquisition and data routing, the full energy balanced depletion among all working sensors is achieved.

2. Related Work

Various approaches have been proposed to prolong the network lifetime for wireless sensor networks and they are mainly classified in two aspects: one is to deploy additional sensors to replace failure sensors, and the other is to relocate sensor nodes in different densities which vary with the distance to the sink.

The problem of unbalanced energy depletion in a wireless sensor network is investigated by Li and Mohapatra for the first time [4, 5]. They first present a mathematical model to analyze the “energy hole” issue in a uniformly distributed wireless sensor networks. And then, they propose several approaches to mitigate this problem. In addition, they point out that simply adding more sensor nodes in the network cannot solve the “energy hole” problem. In [6], the authors investigate the theoretical aspects of the nonuniform node distribution strategy to mitigate the “energy hole” problem in wireless sensor networks. They observe that nearly balanced energy consumption in the network is possible if the number of nodes increases in geometric progression from the outer coronas to the inner ones except the outermost one. And then, they propose a non-uniform node placement strategy and q-switch routing. Though their algorithm can prolong the system lifetime, the balance energy depletion among all the sensors is not achieved. There is still much energy unused in the outermost corona when the network lifetime ends up. In our pervious approach [7], we propose a pixel based sensing mechanism to reduce the sensing redundancy and propose a distributed energy balanced density control algorithm. However, additional energy is consumed in pixel decision process. In [8], the authors propose a balanced energy sleep scheduling scheme in the context of cluster-based sensor networks. They exploit the distance-based scheduling (DS) and the randomized scheduling (BS) algorithms to choose some sensors in each cluster to sleep. However, they only consider the energy consumption in each cluster and ignore the energy depletion of the cluster head. As a result, uneven energy depletion still exists. In [9], the authors propose an adaptive density deployment to mitigate the sink hole problem in wireless sensor networks. It permits a fault tolerant and self-healing deployment. However, their scheme may greatly increase the number of sensor nodes when the network scale increases. In [10], the authors convert balanced energy depletion problem into the expense of gross energy inefficiencies. They investigate the transmission range distribution optimization problem. However, searching the optimal transmission range for sensors is a NP-hard problem. In [11, 12], how to improve network coverage by means of the sensor mobility is studied. In [13, 14], the authors try to separate data collection from communication and investigate the problem of placing sensors, relays, and base station to connect the entire network. Although these algorithms can guarantee the network connectivity and coverage rate, the uneven energy consumption of the entire network is not taken into consideration. In [15], the authors propose a compressive data gathering scheme which can leverage compressive sampling principle to reduce communication cost and prolong network lifetime efficiently. They only focus on how to reduce energy consumption during data transmission, but they do not consider whether the energy consumption of the whole network is even or not.

In this paper, we try to eliminate the “energy hole” for the wireless sensor networks by investigating the optimal placement of relay nodes. The rest of our paper is organized as follows. In Section 3, the accessibility conditions of energy balanced depletion and the extension of network lifetime are analyzed theoretically. In Section 4, on the basis of our network model and assumptions, a novel sensor and relay placement scheme is proposed. In Section 5, a node routing algorithm is proposed for energy balanced depletion. Section 6 presents the simulation results of our proposed algorithm. Finally, the paper is concluded in Section 7.

3. Theoretical Analysis

3.1. Network Model and Assumption

In this section, we will present our network model and make some basic assumptions. Assume that the target area A is a two-dimensional circular surface. There are three kinds of nodes deployed in this region, which are sensor node, relay node, and sink node. Periodical monitoring scheme is applied in our paper, in which each sensor node generates and sends L bits of sensing data per working cycle. In our scheme, a sensor node only needs to sense environmental parameters and forward the sensing data to relay node via one-hop communication. Relay node is responsible for forwarding those sensing data of sensor nodes and does not do any sensing activities. Only sink node works as a terminal data collection station, which is responsible for processing the entire sensed data. We further assume that the energy consumption is only dominated by communication costs, as opposed to the sensing and processing costs. A sensor consumes $e_{1}$ units of energy when sending one bit data while it depletes $e_{2}$ units of energy when receiving one bit data. We use a simplified power consumption model and assume that the existing MAC layer or TDMA scheduling algorithm [16] can always guarantee the success of data transmission.

We assume that all the sensor nodes are uniformly deployed over a circular area with radius d. The sink node is located in the center of this area. The target area is divided into n $(n > 1)$ adjacent coronas with the same width of $R_{c} : {R_{c} | R_{c} = d / n}$ , denoted as $C_{1}, C_{2}, \dots, {C_{i}, \dots, C}_{n}$ , from inside corona to outside corona, where $C_{i}$ is the ith corona. Thus, the distance between the sink node and sensors belonging to corona $C_{i}$ can be denoted as $l$ , where $(i - 1) \times R_{c} \leq l \leq i \times R_{c}$ . Relay nodes are uniformly deployed over the forwarding zone of each corona, as shown in Figure 1. Assume that each node has an ID, a fixed transmission range $R_{c}$ and a fixed sensing range $R_{s}$ , where $R_{c} \geq 2 R_{s}$ [17, 18]. The initial energy of each node is set as $ε$ , where $ε > 0$ . And the sink node has no energy limitation. According to the above assumptions and the network model, the relay nodes belonging to corona $C_{i} {C_{i} | i \neq n}$ need to forward data generated by coronas $C_{j} {C_{j} | (i + 1) \leq j \leq n}$ . Specially, there is no relay node in the outermost corona $C_{n}$ .

Figure 1

Network model.

3.2. Node Energy Depletion per Working Time T

Define the number of sensor nodes deployed in corona $C_{i}$ as $N_{i}^{s}$ and the number of relay nodes as $N_{i}^{r}$ . Denote average energy consumption of sensor node in $C_{i}$ as $E_{i}^{s}$ . Similarly, the average energy consumption of each relay node is denoted as $E_{i}^{r}$ . According to the above assumptions, we know that a sensor node belonging to $C_{i} (i \neq n)$ can generate and send L bits data per unit time. Thus, the average energy consumption of sensor node in corona $C_{i}$ is

\begin{matrix} E_{i}^{s} = L \cdot e_{1}, 1 \leq i < n . \end{matrix}

(1)

As sensors will choose relays in their communication range for data forwarding, the relays belonging to corona $C_{i} (i < n)$ have to transmit data collected by sensors in coronas $C_{j} {C_{j} | (i + 1) \leq j \leq n}$ per unit time. Thus, the average energy consumption of relay node in corona $C_{i}$ can be calculated as

\begin{matrix} E_{i}^{r} = \frac{L \cdot (e_{1} + e_{2}) \cdot \sum_{k = i + 1}^{n} N_{k}^{s}}{N_{i}^{r}}, 1 \leq i < n . \end{matrix}

(2)

Since there are no relays deployed in the outermost corona $C_{n}$ , the average energy depletion of a sensor node in the corona $C_{n}$ can be expressed as follows:

\begin{matrix} E_{n}^{s} = L \cdot e_{1} . \end{matrix}

(3)

3.3. Accessibility Conditions of Balanced Energy Depletion

Ideally, when all the nodes, including sensors and relays, consume their energy with the same ratio, the energy balanced depletion situation can be achieved, and the utilization of network energy can be improved, which can be expressed as

\begin{matrix} E_{n}^{s} = E_{n - 1}^{s} = \dots E_{1}^{s} = E_{n - 1}^{r} = E_{n - 2}^{r} = \dots = E_{1}^{r} . \end{matrix}

(4)

Theorem 1.

Realizing the balanced energy depletion in the whole network is possible when the number of relay nodes in corona $C_{i} (1 \leq i < n)$ satisfies $N_{i}^{r} = ((e_{1} + e_{2}) \cdot \sum_{k = i + 1}^{n} N_{k}^{s}) / e_{1}$ .

Proof.

Since all the sensors in the network work in the same way and have the same initial energy, the energy consumption of sensors in corona $C_{i} (1 \leq i \leq n)$ per unit time satisfies

\begin{matrix} E_{i}^{s} = E_{j}^{s} = L \cdot e_{1}, 1 \leq i, j \leq n, i \neq j . \end{matrix}

(5)

According to (2), we know that when the number of relays in corona $C_{i} (1 \leq i < n)$ satisfies $N_{i}^{r} = ({(e}_{1} + e_{2}) \cdot \sum_{k = i + 1}^{n} N_{k}^{s}) / e_{1}$ , the average energy consumption of each relay in corona $C_{i}$ can be calculated as

\begin{matrix} E_{i}^{r} = \frac{L \cdot (e_{1} + e_{2}) \cdot \sum_{k = i + 1}^{n} N_{k}^{s}}{((e_{1} + e_{2}) \cdot \sum_{k = i + 1}^{n} N_{k}^{s}) / e_{1}} = L \cdot e_{1} . \end{matrix}

(6)

Combining (5) with (6), we conclude that the condition of energy balanced consumption is accessible, and this completes the proof of Theorem 1.

Lemma 2.

Assume that all the sensors are deployed uniformly with density $ρ_{s}$ in wireless sensor network. In order to balance energy depletion in the network, the number of relays in corona $C_{i}$ ( $1 \leq i < n)$ must satisfy $N_{i}^{r} = ρ_{s} \cdot π \cdot R_{c}^{2} \cdot (n^{2} - i^{2}) \cdot (e_{1} + e_{2}) / e_{1}$ .

Proof.

Denoting the acreage of corona $C_{i}$ as $A_{i}$ , according to the network model, $A_{i}$ can be calculated as

\begin{matrix} A_{i} = π \cdot R_{c}^{2} \cdot (i^{2} - {(i - 1)}^{2}) . \end{matrix}

(7)

Assuming the deployed sensors density as $ρ_{s}$ , the number of sensor nodes in corona $C_{i}$ can be calculated as

\begin{matrix} N_{i}^{s} = ρ_{s} \cdot A_{i} = ρ_{s} \cdot π \cdot R_{c}^{2} \cdot (i^{2} - {(i - 1)}^{2}) . \end{matrix}

(8)

Substituting (8) into the balanced energy depletion condition, the number of relays in corona $C_{i}$ can be expressed as

\begin{matrix} N_{i}^{r} = ρ_{s} \cdot π \cdot R_{c}^{2} \cdot (n^{2} - i^{2}) \cdot \frac{(e_{1} + e_{2})}{e_{1}} . \end{matrix}

(9)

This completes the proof of Lemma 2.

Lemma 2 shows that if the sensor nodes are distributed uniformly and the relay node in each corona meets some certain conditions, complete balanced energy depletion is possible in a circular monitor area. Here, we should note that in order to balance energy depletion, the number of relays $N_{i}^{r}$ in corona $C_{i}$ only relates to the deployed sensor density $ρ_{s}$ and the corona number i.

3.4. Extension of the Network Lifetime

Further, we will give an analysis on the network lifetime enhancement of our scheme compared with the traditional uniform distribution. Assume that the initial conditions of the network are the same. Sensor nodes in each corona are deployed uniformly with density $ρ_{s}$ , and the number of sensors in corona $C_{i}$ is $N_{i}^{s}$ . Since the relays in the innermost corona $C_{1}$ need to forward all the sensed messages in the whole network, those nodes consume the most energy. Thus, the maximum lifetime of a network with traditional uniform node distribution is determined by the survival time $C_{1}$ , which can be calculated as $ε / E_{1}^{'}$ , where $E_{1}^{'}$ is the average energy depletion of sensor in corona $C_{1}$ . Note that $E_{1}^{'}$ can be calculated by

\begin{matrix} E_{1}^{'} = L \cdot e_{1} + \frac{L \cdot (e_{1} + e_{2}) \cdot \sum_{k = 2}^{n} N_{k}^{s}}{N_{1}^{s}} . \end{matrix}

(10)

Thus, the network lifetime enhancement can be expressed as

\begin{array}{l} \frac{ε / E_{1}}{ε / E_{1}^{'}} = \frac{E_{1}^{'}}{E_{1}} \\ = \frac{(L \cdot e_{1} + ((L \cdot (e_{1} + e_{2}) \cdot \sum_{k = 2}^{n} N_{k}^{s}) / N_{i}^{s}))}{(L \cdot e_{1})} \\ = 1 + \frac{(e_{1} + e_{2}) \cdot \sum_{k = 2}^{n} N_{k}^{s}}{N_{1}^{s}} ≫ 1 . \end{array}

(11)

Therefore, the network lifetime can be greatly prolonged.

4. Relay Placement

According to the analysis derived in the previous section, we can calculate the ratio of relay angles in adjacent corona $C_{i}$ and $C_{i + 1}$ , where $1 \leq i < n - 1$ . In order to guarantee the energy balanced depletion and the connectivity of the network, we assume that the number of sensors in the network satisfies (8) and the number of relays satisfies (9). Assume that relay nodes are uniformly deployed over the forwarding area in corona $C_{i} (1 \leq i < n)$ . When the forwarding area approximates to arc-shaped, the angle between any two relay nodes in corona $C_{i}$ can be calculated as

\begin{matrix} α_{i} = \frac{2 π}{N_{i}^{r}}, \end{matrix}

(12)

where $α_{i}$ is defined as the relay angle of corona $C_{i}$ .

The ratio of relay angles of two adjacent coronas $C_{i + 1}$ and $C_{i}$ can be expressed as

\begin{matrix} \frac{α_{i}}{α_{i + 1}} = \frac{n^{2} - {(i + 1)}^{2}}{n^{2} - i^{2}} . \end{matrix}

(13)

Theorem 3.

Define that the distance between corona $C_{i}$ and the sink node is $d_{i}^{r}$ and the distance between corona $C_{i}$ and $C_{i + 1}$ is $d_{i, i + 1}^{r}$ . If $d_{i, i + 1}^{r} \leq \sqrt{R_{c}^{2} - {(d_{i}^{r} \cdot \sin α_{i})}^{2}}$ , it can always guarantee that the messages forwarded by relay nodes in corona $C_{i + 1}$ are evenly distributed along relay nodes in corona $C_{i}$ .

Proof.

As shown in Figure 2, according to the relationship of relay angles within adjacent coronas, the relay angle of corona $C_{i + 1}$ and corona $C_{i}$ satisfies

\begin{matrix} α_{i + 1} = ⌈ \frac{n^{2} - i^{2}}{n^{2} - {(i + 1)}^{2}} ⌉ \cdot α_{i}, \end{matrix}

(14)

where $⌈ ⌉$ represents the ceil function. Note that $(n^{2} - i^{2}) / (n^{2} - {(i + 1)}^{2})$ can be rewritten as

\begin{matrix} \frac{n^{2} - i^{2}}{n^{2} - {(i + 1)}^{2}} = 1 + \frac{2 i + 1}{n^{2} - {(i + 1)}^{2}} . \end{matrix}

(15)

Here, we should notice that (15) is an increasing function with respect to i, $1 \leq i \leq n - 1$ . When $i = n - 2$ , the maximum value of (15) is

\begin{matrix} {(\frac{n^{2} - i^{2}}{n^{2} - {(i + 1)}^{2}})}_{\max} = 1 + \frac{2 n - 3}{2 n - 1} < 2 . \end{matrix}

(16)

Combining (16) with (14), we can conclude that, to meet the condition of balanced energy depletion among all the nodes, each relay in corona $C_{i + 1}$ needs at least two forwarding nodes in corona $C_{i}$ . That is,

\begin{matrix} α_{i + 1} = ⌈ \frac{n^{2} - i^{2}}{n^{2} - {(i + 1)}^{2}} ⌉ \cdot α_{i} = 2 \cdot α_{i} . \end{matrix}

(17)

Owning to triangle conversion relation, when $d_{i, i + 1}^{r} \leq \sqrt{R_{c}^{2} - {(d_{i}^{r} \cdot \sin α_{i})}^{2}}$ , we have

\begin{matrix} \sqrt{R_{c}^{2} - {(d_{i, i + 1}^{r})}^{2}} \geq d_{i}^{r} \cdot \sin α_{i} . \end{matrix}

(18)

That is to say, when the relay angle in corona $C_{i + 1}$ is no smaller than $2 α_{i}$ , we can always guarantee that any relays in corona $C_{i + 1}$ can choose at least two forwarding relay nodes in $C_{i}$ . This completes the proof of Theorem 3.

Figure 2

Distance calculation between adjacent coronas.

Consider that the sensor nodes are uniformly deployed in the network, and assume that the distance between the relays and sink node in the first corona $C_{1}$ is $R_{c}$ to guarantee the network connectivity. And then, the largest distance between adjacent coronas is calculated to determine the position of forwarding region from corona $C_{2}$ to $C_{n - 1}$ in order, which is updated according to the following equation:

\begin{matrix} d_{1}^{r} = R_{c}, i = 1, \\ d_{i}^{r} = d_{i - 1}^{r} + \sqrt{R_{c}^{2} - {(d_{i - 1}^{r} \cdot \sin α_{i})}^{2}}, 2 \leq i \leq n - 1 . \end{matrix}

(19)

5. Routing Scheme

Assume each sensor is aware of its positions and know the corona ID which it belongs to. The communication model of sensor i is expressed as a circle with radius $R_{c}$ and the center of its coordinates $(x_{i}^{s}, y_{i}^{s})$ . We refer to the set of sensor nodes as $S = {s_{1}, s_{2}, \dots, s_{n}}$ , where $s_{i} = {x_{i}^{s}, y_{i}^{s}}$ . Similarly, we refer the set of relay nodes as $R = {r_{1}, r_{2}, \dots, r_{n}}$ , where $r_{i} = {x_{i}^{r}, y_{i}^{r}}$ is the coordinate of relay node $r_{i}$ . Assume that sensor nodes are uniformly deployed in each corona $C_{i}$ with density $ρ_{s}$ . The location of each relay region is calculated according to (19). Thus, the distance between any sensor iand any relay j can be denoted as

\begin{matrix} d (s_{i}, r_{j}) = \sqrt{{(x_{i}^{s} - x_{j}^{r})}^{2} + {(y_{i}^{s} - y_{j}^{r})}^{2}} . \end{matrix}

(20)

If $d (s_{i}, r_{j}) \leq R_{c}$ , we say j is a candidate relay node of sensor i in its one-hop communication range. In other words, sensor i can transmit the data to sink node via relay j. We refer the set of candidate relays of sensor node i as ${R S}_{i} = {r_{j} | d (s_{i}, r_{j}) \leq R_{c}}$ . Similarly, the distance between any relays n and m can be denoted as

\begin{matrix} d (r_{n}, r_{m}) = \sqrt{{(x_{n}^{r} - x_{m}^{r})}^{2} + {(y_{n}^{r} - y_{m}^{r})}^{2}} . \end{matrix}

(21)

If $d (r_{n}, r_{m}) \leq R_{c}$ , we say that n and m are neighbour relays and they can send data to each other. Denote the candidate relay set of $r_{n}$ as ${R R}_{n} = {r_{m} | d (r_{n}, r_{m}) \leq R_{c}}$ . Figure 3 shows a typical data forwarding via relays. The red nodes represent relays while the blue nodes represent sensors. The light blue area is the communication range of sensors while the light red one is the communication range of relays. As shown in Figure 3, the candidate set of sensor $s_{j}$ is ${R S}_{j} = {r_{e} {, r}_{f}, r_{g}, r_{h}, r_{i}}$ . The candidate set of relay $r_{h}$ is ${R R}_{h} = {r_{j}, r_{k}}$ . When sensor $s_{j}$ has completed the data collection process, it first sends the collected data to one of its candidate relays in ${R S}_{j}$ . Assume $r_{h}$ is selected from ${R S}_{j}$ . Then, $r_{h}$ receives these data and forwards them to one of its candidate relays in ${R R}_{h}$ . Finally, the collected data will be forwarded to the sink node.

Figure 3

Data forwarding via relays.

According to Theorem 3, when the distance between corona $C_{i + 1}$ and $C_{i}$ satisfies $d_{i, i + 1}^{r} \leq \sqrt{R_{c}^{2} - {(d_{i}^{r} \cdot \sin α_{i})}^{2}}$ , any relays in corona $C_{i + 1}$ are able to choose at least two forwarding nodes from corona $C_{i}$ . In order to balance energy consumption, the relay with maximum residual energy will be selected first for data forwarding. And the whole routing scheme mainly contains two phases. The first phase aim at initializing the candidate relay set of all the nodes, including both the sensor nodes and the relay nodes. The second phase is data forwarding. Finally, the residual energy will be updated. Assume that all the nodes have the same initial energy $ε$ , where $ε > 0$ . The unused energy of sensor $s_{i}$ is denoted as ${U S}_{i}$ while the unused energy of relay $r_{j}$ is denoted as ${U R}_{j}$ . The detailed algorithm for data forwarding is shown in Algorithm 1.

Algorithm 1: Routing algorithm.

Step 1. Set ${R S}_{i} = \emptyset$ and ${R R}_{j} = \emptyset$

IF $s_{i} \in C_{1}$ THEN SET ${R S}_{i} = {Sink}$

IF $r_{j} \in C_{1}$ THEN SET ${R R}_{j} = {Sink}$

Step 2. All the sensor nodes start to collect data

Step 3. All the sensor nodes start to send data

IF $s_{i} \in C_{1}$

Sensor $s_{i}$ chooses the sink node as its forwarding node;

Sensor $s_{i}$ sends its own data to the sink node;

Update the residual energy of sensor $s_{i}$ ;

ELSE

Sensor $s_{i}$ chooses the first relay $r_{j}$ with maximum residual

energy through clockwise from ${R S}_{i}$ as its forwarding node;

Sensor $s_{i}$ sends out its own data, and $r_{j}$ receives them;

Update the residual energy of $s_{i}$ and $r_{j}$ ;

Step 4. All the relays begin to forward data

IF $r_{j} \in C_{1}$

Relay $r_{j}$ chooses the sink node as its forwarding node;

Relay $r_{j}$ forwards its received data, and the sink node receives

these data;

Update the residual energy of $r_{j}$ ;

ELSE

Relay $r_{j}$ chooses relay $r_{k} \in {R R}_{j}$ with maximum residual energy

as the data forwarding node;

$r_{j}$ sends out its received data while $r_{k}$ receives them;

Update the residual energy of $r_{j}$ and $r_{k}$ .

In our algorithm, the time complexity of each sensor is corresponding to the size of its candidate relay set. According to Theorem 1, sensors in corona $C_{2}$ have the largest number of candidate relays, which can be calculated as $N_{1}^{r} / N_{2}^{s}$ . Therefore, the complexity of each sensor is smaller than $O (N_{1}^{r} / N_{2}^{s})$ . As to relay nodes, the complexity is smaller than $O (C)$ . Therefore, the time complexity of the whole algorithm is smaller than $O ((N_{1}^{r} / N_{2}^{s}) * \sum_{i = 1}^{n} N_{i}^{s}) + O (C * \sum_{i = 1}^{n - 1} N_{i}^{r})$ .

6. Simulation

In this section, we present the simulation results to verify the performance of our proposed algorithm. We mainly consider three metrics which are the average residual energy, the residual energy ratio, and the network lifetime.

6.1. Simulation Environment

Assume that the radius of the target region $d$ is 100 m. The initial energy of each node $ε$ is 100 J. The values of $e_{1}$ and $e_{2}$ are given as follows: $e_{1} = 0.5 / 10^{3} J/bit$ , $e_{2} = 0.25 / 10^{3} J/bit$ [19]. The length of data L generated by each sensor per unit time is set as 1000 bits. The sensing range $R_{s}$ of each sensor is 12.5 m, and the communication range $R_{c}$ of each node is 25 m. The deployment density of sensor nodes $ρ_{s}$ is $2 / \sqrt{27} R_{s}^{2}$ [20].

6.2. Residual Energy

At first, 81 sensors and 255 relays are deployed in a circular area. The whole network is divided into 4 adjacent coronas with the same width. The sink node is located in the center of the target area. Figure 4 shows the residual energy of all the nodes when the network lifetime ends up. A node is said to be dead when it is unable to forward any data or send its own data. The network lifetime is defined as the duration from the beginning of the network operation until the first node dies [6]. As can be seen from Figure 4, almost all the nodes run out of energy at the same time, which verifies the correctness and feasibility of our network model. On the other hand, we can also find that there is a small gap of the residual energy of all the nodes, including relays and sensors. This is mainly because the innermost corona is involved in forwarding all the sensed data, and in the last data transmission cycle, some nodes do not have enough energy to receive data. Even though these nodes receive data successfully, some of them may not be able to forward the data out. As a result, some of the nodes finish sending data while others fail, which leads to a slight difference in node residual energy.

Figure 4

Residual energy of each node.

Figure 5 illustrates the simulation results of average residual energy of sensors and relays in each corona $C_{i}$ . From Figure 5, we observe that (1) when the network lifetime ends up, the difference between average residual energy of sensors and relays in each corona is nearly less than 0.1 J. (2) The average unused energy of all the relays in each corona is almost the same. This is in accordance with our analysis; when all the nodes consume the energy with the same ratio, the utilization of network energy can be improved.

Figure 5

Average residual energy.

6.3. Comparisons with Existed Algorithms

In order to further evaluate the performance of our algorithm, we compare our approach with random node distribution model and uniform node distribution model. Figure 6 shows the unused energy of all nodes after a certain data collection cycle. In Figure 6, sensors with smaller ID numbers are closer to the sink, whereas those with larger ID numbers are far away from the sink node. As shown from Figure 6, we can find that in a random node distribution model, the network connectivity is seriously affected by the sensor distribution over the target area. Almost all the sensors cannot forward their own data to the sink node. For example, the total energy consumption of sensor 10 is almost close to 0 J. In uniform node distribution model, we can see that those sensors with larger ID consume less energy and the unused energy is greater than 60 J. However, those with smaller IDs consume more energy and the residual energy is almost close to 0 J. From the simulation results in Figure 6, we can make a conclusion that although the network connectivity is guaranteed, sensors that are nearer to the sink node carry heavier traffic loads than those farther from the sink node. Thus, unbalanced energy depletion is inevitable. In our model, all the nodes, including both sensors and relays, consume the same energy and have the same energy left, which verify that our algorithm can achieve the balanced energy depletion.

Figure 6

Residual energy of each node after a certain data collection cycle.

Figure 7 shows the comparison of the unused energy ratio after different data collection cycles. In order to facilitate the comparison, we randomly choose parts of the nodes for presenting our algorithm results. As shown in Figure 7, with the increasing data acquisition cycle of, sensor energy consumption becomes more uneven in the network with random and uniform distribution. In uniform node distribution, the heavy load on the inner corona has seriously affected the sensor energy depletion. After 15 times data collections, some sensors use up their energy. Thus, the whole network lifetime is over. As for random sensor deployment, the whole network lifetime is only related to the initial location of each sensor and the energy depletion process is very unstable. In contrast, our algorithm can effectively maintain the stability of energy consumption process. As shown in Figure 7, our algorithm can balance the energy depletion, in which almost all the nodes have the same residual energy after each data collection cycle.

Figure 7

Energy depletion after different data collection cycles.

Figure 8 shows the comparison of network lifetime in different target area sizes. As seen from Figure 8, when the radius of the area $d \leq R_{c}$ , that is to say, d, is less than or equal to 25 m, these three deployment models can achieve maximum network lifetime. This is mainly because all the nodes can send data to the sink node directly. However, the network lifetime decreases sharply in random and uniform node distribution when the size of the target area enlarges and the number of communication hops increases. Especially for uniform model, when $d = 150$ m, the network lifetime dropped to 10. This is mainly because when the number of sensors increases, the traffic load on innermost corona is seriously exacerbated, which results the shortest network lifetime. Although the network lifetime in random distribution model is longer than the one in uniform distribution, it is also affected by the scale of the target area. Since the relays are adopted to share the traffic load of the sensors, we can effectively balance the energy consumption in the whole network. As shown in Figure 8, the data collection process can always remain stable regardless of the changes of area radius. Hence, it has the longest network lifetime.

Figure 8

Comparison of network lifetime in different target areas.

7. Conclusion

In wireless sensor networks, traditional deployment approaches mainly focus on maximizing the coverage rate so as to improve the monitoring efficiency, which leads to the creation of “energy hole” near the sink node. In this paper, we theoretically analyze the balanced energy depletion condition by deploying additional relay sensors on the target area. Further, we prove that the network lifetime can be prolonged effectively. Contributively, a novel relay deployment scheme and its corresponding routing scheme are proposed. Extensive simulation results show that our algorithm can achieve complete balanced energy depletion, and outperform other existed algorithms.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grant No. 61173153, No. 60903159, No. 61070162 and No. 71071028; the National Science Foundation for Distinguished Young Scholars of China under Grant No. 61225012; the Fundamental Research Funds for the Central Universities under Grant Nos. N110404014, N110318001, N110204003 and N120104001; the China Postdoctoral Science Foundation Funded project under Grant No. 20110491508 and No. 2012T50248; The Specialized Research Fund of the Doctoral Program of Higher Education for the Priority Development Areas under Grant No. 20120042130003.

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 114

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

Ghosh

Das

S. K.

Coverage and connectivity issues in wireless sensor networks: a survey

Pervasive and Mobile Computing 2008 4 3 303 334

2-s2.0-43549098529

10.1016/j.pmcj.2008.02.001

Chen

Das

S. K.

On the energy hole problem of nonuniform node distribution in wireless sensor networks

Proceedings of the IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems (MASS '06)

October 2006

180 187

2-s2.0-39049087707

10.1109/MOBHOC.2006.278555

Mohapatra

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

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

2005

IEEE

2721 2725

Mohapatra

Analytical modeling and mitigation techniques for the energy hole problem in sensor networks

Pervasive and Mobile Computing 2007 3 3 233 254

2-s2.0-34047261116

10.1016/j.pmcj.2006.11.001

Chen

Das

S. K.

Avoiding energy holes in wireless sensor networks with nonuniform node distribution

IEEE Transactions on Parallel and Distributed Systems 2008 19 5 710 720

2-s2.0-42549104040

10.1109/TPDS.2007.70770

Jia

Chen

Wang

Zhao

Energy-balanced density control to avoid energy hole for wireless sensor networks

International Journal of Distributed Sensor Networks 2012 2012 10

2-s2.0-84856425093

10.1155/2012/812013

812013

Deng

Han

Y. S.

Heinzelman

W. B.

Varshney

P. K.

Balanced-energy sleep scheduling scheme for high-density cluster-based sensor networks

Computer Communications 2005 28 14 1631 1642

2-s2.0-23844469130

10.1016/j.comcom.2005.02.019

Bartolini

Calamoneri

Massini

Silvestri

On adaptive density deployment to mitigate the sink-hole problem in mobile sensor networks

Mobile Networks and Applications 2011 16 1 134 145

2-s2.0-79751529780

10.1007/s11036-010-0247-5

10.

Perillo

Cheng

Heinzelman

On the problem of unbalanced load distribution in wireless sensor networks

Proceedings of the IEEE Global Telecommunications Conference Workshops (GLOBECOM '04)

December 2004

IEEE

74 79

2-s2.0-20344398474

11.

Abbasi

A. A.

Younis

Akkaya

Movement-assisted connectivity restoration in wireless sensor and actor networks

IEEE Transactions on Parallel and Distributed Systems 2009 20 9 1366 1379

2-s2.0-68849104727

10.1109/TPDS.2008.246

12.

Wang

Cao

La Porta

T. F.

Movement-assisted sensor deployment

IEEE Transactions on Mobile Computing 2006 5 6 640 652

2-s2.0-33646437020

10.1109/TMC.2006.80

13.

Patel

Chandrasekaran

Venkatesan

Energy efficient sensor, relay and base station placements for coverage, connectivity and routing

Proceedings of the 24th IEEE International Performance, Computing, and Communications Conference (IPCCC '05)

April 2005

581 586

2-s2.0-28544448977

14.

Liu

Wan

Jia

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

Journal of Combinatorial Optimization 2006 11 2 249 260

2-s2.0-33646532423

10.1007/s10878-006-7140-y

15.

Luo

Sun

Chen

C. W.

Efficient measurement generation and pervasive sparsity for compressive data gathering

IEEE Transactions on Wireless Communications 2010 9 12 3728 3738

2-s2.0-78650203708

10.1109/TWC.2010.092810.100063

16.

Cheng

Xiong

Yang

L. T.

Jeong

Y.-S.

Distributed scheduling algorithms for channel access in TDMA wireless mesh networks

Journal of Supercomputing 2013 63 407 430

2-s2.0-54049093594

10.1007/s11227-008-0244-7

17.

Zhang

Hou

J. C.

Maintaining sensing coverage and connectivity in large sensor networks

Ad Hoc & Sensor Wireless Networks 2005 1 1-2 89 124

18.

Slijepcevic

Potkonjak

Power efficient organization of wireless sensor networks

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

June 2000

472 476

2-s2.0-0034865562

19.

Anastasi

Falchi

Passarella

Conti

Gregori

Performance measurements of motes sensor networks

Proceedings of the International Conference on Modelling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM '04)

October 2004

174 181

2-s2.0-27644577349

20.

Jia

Chen

Wang

Exploiting sensor redistribution for eliminating the energy hole problem in mobile sensor networks

EURASIP Journal on Wireless Communications and Networking 2012 2012, article 68

10.1186/1687-1499-2012-68

On the Problem of Energy Balanced Relay Sensor Placement in Wireless Sensor Networks

Abstract

1. Introduction

2. Related Work

3. Theoretical Analysis

3.1. Network Model and Assumption

3.2. Node Energy Depletion per Working Time T

3.3. Accessibility Conditions of Balanced Energy Depletion

Theorem 1.

Proof.

Lemma 2.

Proof.

3.4. Extension of the Network Lifetime

4. Relay Placement

Theorem 3.

Proof.

5. Routing Scheme

Algorithm 1: Routing algorithm.

6. Simulation

6.1. Simulation Environment

6.2. Residual Energy

6.3. Comparisons with Existed Algorithms

7. Conclusion

Footnotes

Acknowledgments

References