The Role of Nodes Distribution in Extending the Lifetime of Wireless Sensor Networks

Abstract

One of the most important issues in sensor networks is prolonging the network lifetime. In this paper, we demonstrate that given a constant number of nodes, how distribution of nodes affects the lifetime. For this purpose, we first show that in a network with cluster-based routing protocol, nodes do not have equal importance, and their importance depends on their location, and we determine the most critical regions. We prove that the uniform distribution of nodes is not a good distribution. Finally, we propose a solution for the best distribution that concentrates the population of nodes on critical areas. Simulation results of our proposed distribution show a remarkable increase in network lifetime.

1. Introduction

A sensor network consists of a large number of sensor nodes deployed over an area. Nodes are low cost and are usually equipped with a power supply, a microprocessor, microsensors, and radio component that provides for wireless communication between nodes. This set of nodes is used for a variety of applications. The most common use is to monitor changes in a special parameter in a region. For instance, in [1], the temperature and humidity of different elevations of a tree are measured over a period of time, or, in [2], the environment of a coalmine is monitored by a wireless sensor network.

The most distinctive characteristic of a sensor network is the limited energy supply available for each node (a typical battery) due to their small size. Moreover, because of their size and low cost it would not be beneficial to recharge or replace the depleted battery of the nodes. In other words, every node is deemed useless after its battery discharges; therefore, finding energy-efficient routing protocols has become a significant issue. Flooding and gossiping [3], SPIN [4], LEACH [5], and HEED [6] are some examples of routing protocols proposed in the literature.

One of the most well-known techniques is clustering in which nodes are divided into groups called clusters with a node assigned as the cluster head. This technique prevents long-distance communication from distant nodes to the base station, thus, manages to save considerable amounts of energy. Instead, nodes included in a cluster communicate directly with their cluster head, and cluster heads forward the information to the base station within one-hop or multihop routes [7–10]. Clustering algorithms vary mainly based on their number of cluster heads, methods to form a cluster, cluster head election techniques, intercluster communications, and so forth.

One of the primary goals of all mentioned methods is to extend the time that the network is functioning as expected for its specific application. The effective lifetime has been defined in different ways. In [11], life time is defined as the time period for the first node to run out of its energy reserve. Authors of [12] define lifetime as the time until the first failure of the packet delivery due to battery outage. Definition of lifetime in [13] is the time for which 100% or 90% of the network coverage is preserved.

In a given routing algorithm, several parameters directly affect the performance of the network, such as number of the nodes, the area that needs to be observed, the mobility of nodes, and so forth. One of the most effective factors is the distribution of the nodes. The position of the nodes relative to each other and the base station can greatly influence the effective lifetime of the network.

In this paper, we are going to study the relation between the distribution of nodes over the monitored area and network's lifetime. Here, we consider lifetime to be the period that the network's coverage remains at more than 90% of its initial value. Then, we will try to extract the optimum solution for distributing the nodes.

2. Related Works

Several researches have been done addressing the issue of distribution in WSNs. Authors of [14] show how to improve the total data capacity of WSNs by using nonuniform sensor deployment strategy. In [14], SSEP model (Single Static Sink Edge Placement) is discussed in which nodes are placed uniformly in a rectangular area, and base station is located on one of the edges of this rectangle. The performance of such model is measured against the SSEP-NU (SSEP with nonuniform distribution) model for the network. Finally, it is shown that using the SSEP-NU model along with a mobile sink and a suitable routing protocol can improve the total data capacity by one order of magnitude compared to the original SSEP model. The authors extend their models in [15], where they introduce SSEP-NS (SSEP with nonuniform sensor distribution) model. In [16], another nonuniform distribution is suggested in order to avoid unbalanced energy depletion in the network. In this work, it is assumed that all the nodes are deployed in a circular area with a radius of R, and the base station is located in the center. The area around the base station is divided into R adjacent coronas with the same width of 1 unit. In the proposed nonuniform node distribution strategy, number of nodes increases with geometric proportion from the outer parts to the inner ones. The ratio between the node densities of the adjacent ${(i + 1)}_{th}$ corona and the $i_{th}$ corona is equal to $(2 i - 1) / q (2 i + 1)$ , where q is the geometric proportion mentioned above. A high energy utilization is reached using this distribution in circular wireless sensor networks. However, it incurs some costs. With the number of nodes in the coronas increasing from outer to the inner areas with geometric proportion, the total number of nodes in the network grows exponentially.

3. Coverage-Preserving Clustering Protocol (CPCP)

The common objective of almost every routing protocol is to guarantee the balanced energy consumption among nodes and, therefore, prolong the network's lifetime. For this purpose, a cost metric is used in order to assign a cost value to each node. Consequently, nodes with higher residual energy have relatively less cost compared to those with low residual energy, and thus participate in routing more often. As a result, the density of dead nodes would be rather uniform through the monitored area after the expiration of network's lifetime. However, studying the pattern of energy consumption of the network during its lifetime will lead to interesting information.

We use the coverage-preserving clustering protocol (CPCP) algorithm introduced in [13]. First, we briefly explain the method, and then we will investigate the patterns of energy consumption.

CPCP puts a limitation on size of every cluster, so cluster formation in sparsely covered areas is similar to densely covered areas. Through this approach, the authors try to reach the maximum time that the network sustains its high coverage even in nonuniformly distributed networks. Several coverage-aware cost metrics can be used by this algorithm. The cost metric that we use here is the weighted sum coverage

C_{w s} (s_{i}) = \int_{C (s_{i})}^{} \frac{d x d y}{E_{total} (x, y)} = \int_{C (s_{i})}^{} \frac{d x d y}{\sum_{s_{j} : (x, y) ϵ C (s_{j})} E (s_{j})} .

(1)

where

s_{i}

refers to the

i_{th}

sensor and

E (s_{i})

is the remaining energy of the sensor

s_{i}

. Every sensor performs its sensing task in a circular area surrounding it with the radius of

R_{sense}

C (s_{i})

denotes the sensing area around the sensor

s_{i}

. This cost metric measures the weighted average of the total energies of all points that are covered by the sensing area of node

s_{i}

In CPCP, the total lifetime is divided into some communication rounds. Each CPCP round consists of six phases: information update, cluster head election, route update, cluster formation, sensor activation, and data communication.

In phase 1, nodes broadcast their remaining energy to their neighbors in the range of $2 R_{sense}$ . In phase 2, nodes calculate their activation time (a value proportional to their cost), and then they broadcast an announcement message to their neighbors if they do not hear an announcement message from other nodes before the expiration of their activation time. Every node receiving an announcement considers the sender as its cluster head (CH). Consequently, the node with the lowest cost in a neighborhood becomes the CH. In the next phase, route update, cluster heads find the most efficient multihop path to communicate with the base station, which is a path with minimum sum of routing costs of the nodes involved in routing. In the 4th phase, nodes that were not selected as CHs send a join message to the CH that they belong to and clusters are formed. In sensor activation phase, a subset of nodes is chosen to perform sensing task in that communication round, so other nodes go to sleep mode to save their energy. In the last phase, nodes periodically perform their sensing task, and send their collected data to their CH, where it is aggregated and sent to the base station through multihop routes.

4. Energy Consumption Pattern

Figure 1 shows the changes in the total energy of the network (the sum of energy of the individual nodes) against time. As it is evident, the total energy of the network decreases linearly at first, but, after a certain point, it shows nonlinear behavior. Clearly, this phenomenon accelerates the depletion of network's energy. In order to find solution to eliminate this unwanted behavior, we first have to examine its possible reasons.

Figure 1

Total energy of the network against time.

The node's energy is spent for various reasons such as communication, sensing, performing inside-node computations and so forth. Communication is the most energy consuming task in almost every application. The energy required to receive or transmit data for every node is modeled by the model introduced in [10]

\begin{gathered} E t (l, d) = {\begin{cases} l \times E_{elec} + l \times ϵ_{friss_amp} \times d^{2} \\ : d < d_{cross-over} \\ l \times E_{elec} + l \times ϵ_{two_ray_amp} \times d^{4} \\ : d > d_{cross-over}, \end{cases} \\ E r (l) = l \times E_{elec}, \end{gathered}

(2)

where

E t (l, d)

is the energy required for a node to send l bits of data over a distance of d, and

E r (l)

is the required energy to receive an l bit packet.

E_{elec}

is consumed energy by electronic circuits and depends on factors such as digital coding, modulation, and so forth,

ϵ_{friss_amp}

and

ϵ_{two_ray_amp}

are parameters dependent on the required receiver sensitivity and the receiver noise figure.

d_{cross-over}

is the maximum distance of 2 nodes in order for them to have a direct line of sight thus, if a node sends a packet to a destination further than

d_{cross-over}

, the transmission energy will be proportional to

d^{4}

. Needless to say, this will increase the energy consumption rate of the node. This phenomenon would not affect the overall performance of the network in cases that the dimensions of monitored area are less than

d_{cross-over}

. However, in larger areas, it can have serious impacts. In our setup, we consider a network with radio characteristics given in Table 1.

Table 1

Radio characteristics of the network.

Description	Parameter	Value
Cross over distance for Friss and two-ray ground attenuation models	$d_{crossover}$	$\frac{4 π h_{r} h_{t}}{λ}$

Transmit power	$P_{t}$	$ϵ_{friss_amp} R_{b} d^{2} : d < d_{crossover}$ $ϵ_{two_ray_amp} R_{b} d^{4} : d \geq d_{crossover}$

Receive power	$P_{r}$	$\frac{ϵ_{friss_amp} R_{b} G_{t} G_{r} λ^{2}}{{(4 π)}^{2}} : d < d_{crossover}$ $ϵ_{two_ray_amp} R_{b} G_{t} G_{r} h_{t}^{2} h_{r}^{2} : d \geq d_{crossover}$

Minimum receiver power needed for successful reception	$P_{r_thresh}$	6. 3 nW

Radio amplifier energy	$ϵ_{friss_amp}$ $ϵ_{two_ray_amp}$	$\frac{P_{r_thresh} {(4 π)}^{2}}{R_{b} G_{t} G_{r} λ^{2}}$ $\frac{P_{r_thresh}}{R_{b} G_{t} G_{r} h_{t}^{2} h_{r}^{2}}$

Radio electronics energy	$E_{elec}$	50 nJ/bit

Compute energy for beamforming	$E_{BF}$	5 nJ/bit

Bitrate	$R_{b}$	1 Mbps

Antenna gain factor	$G_{t} {, G}_{r}$	1

Antenna height above the ground	$h_{t} {, h}_{r}$	1 m

Signal wavelength	λ	0. 325 m

According to the parameters given in Table 1, $d_{cross-over}$ would be 38. 31 [m]. We use a 400 × 400 [m²] area to observe the effect of $d_{cross-over}$ .

In this scenario, 1000 nodes are deployed randomly over a 400 × 400 [m²] area. The coverage of the network at its initial state is more that 97% which is a reasonable approximation of a fully covered network. For illustrative purposes, network lifetime is divided into some intervals with a length of 500 [s]. To get a better understanding of the pattern of energy consumption through time, we took a snapshot of the network after every interval.

As it is shown in Figure 2, energy consumption of the nodes is nonuniform and is dependent on their distance from the base station. The reason is that nodes closer to the base station carry a higher rate of traffic. To put it simply, CHs form multihop routes to send their data to the base station, and since according to (2) communicating over long distances is very energy consuming, the last hop of every multihop route would be elected among nodes located relatively close to the center in order to avoid long-distance communication to the base station. As a result, central nodes are used for communication purposes more often; therefore, they lose their energy faster. Obviously, this procedure cannot continue for a long time. Excessive use of central nodes leads to the formation of a low-energy and therefore high-cost area surrounding the base station. Due to the energy-aware characteristic of the algorithm, distant nodes gradually refuse to use these high-cost nodes as hops. The result is that distant nodes are compelled to send their data over longer distances, and according to (2), because $E t$ increases nonlinearly when d is increased (proportional to $d^{2}$ ), they lose their energy at higher rates. Moreover, if the distance becomes more than $d_{cross-over}$ , $E t$ will increase at excessive higher rates (proportional to $d^{4}$ ).

Figure 2

Snapshots of network after every 500 [s].

To take a more precise look, although central nodes carry a heavy load of traffic, nodes located extremely close to the center seem to be excluded from this problem. This fact is shown in Figure 3. According to Figure 3, we calculate the communication energy to send a bit of data from C to A from 2 different paths, and we show that if B is located extremely close to A, it would be better for C to communicate directly with A instead of using B as its interface.

Figure 3

Path1: C, A $E_{total1} = E t (CA) + E r (A)$ . Path2: C, B, A $E_{total2} = E t (CB) + E r (B) + E t (BA) + E r (A)$ . If $BA \to 0 \Rightarrow CA \to CB$ ; $BA \to 0 \Rightarrow E_{total2} > E_{total1}$ .

It seems that nodes extremely close to the base station are less probable to be elected as hops by CHs compared to those located somewhat further. In other words, in the early communication rounds, the percentage of nodes' participation in routing at first increases as we get closer to the center, but, after passing a certain point, it will start to decrease, so it seems to have a maximum at a certain distance from the base station. As discussed before, communication is the most energy-consuming task of the nodes, thus any change in the percentage of nodes' participation in routing would lead to similar changes in nodes' energy consumption, and therefore in their cost.

Taking all the facts into account, it seems that the critical, high-cost area formed around the base station is similar to a ring. These conclusions can be confirmed by the simulation results. Figure 4 shows the cost of nodes versus their distance from the base station after every 500 [s]. The figure shows that there is a peak in the node's cost at a certain point. Of course, the location of this peak is dependent on the assumed parameters of this simulation (Table 3). With our setup, the maximum cost occurs at about $d = 50$ [m] which is a circle with the radius of 50 meters with its center located at the base station.

Figure 4

Cost of nodes against their distance from the base station after every 500 [s].

5. The Proposed Solution

According to Figure 4, the formation of a high-cost ring causes long-distance communications and leads to inefficient energy consumption. This problem can be solved by modifying the distribution of nodes. Since nodes in the critical ring are more often used and therefore are more important compared to other nodes, a distribution with higher concentration of nodes in the critical areas seems to be more proper than a uniform distribution. By taking a deeper look into Figure 4, we can see that cost of nodes is a function of their distance from center. We can also recognize a pattern similar to gamma distribution (explained in (3)). The pattern formed in the cost of nodes over time is a measure of their importance in routing or in other words their potential for early depletion. In order to neutralize this effect, we tend to choose a nonlinear distribution that distributes energy in the network with the same pattern seen in Figure 4. In this way, areas that are more probable to be depleted of energy are provided with more initial energy proportionally. Therefore, we suggest gamma distribution for distributing nodes (see Figure 5).

Figure 5

Gamma distribution.

However, a paramount factor that should be taken into consideration is that the number of nodes is constant at 1000 nodes. Therefore, existence of certain densely populated areas will cause other areas to be sparsely covered. This fact will limit the degree to which we can concentrate nodes at the critical area. To put it simply, we have to make sure that the network has a high coverage percentage at its initial state (more than 97%); therefore, there cannot be an unlimited increase in the density of nodes in some areas. To solve this problem, we propose a compromise. We divide the nodes into two groups. We first distribute $N 1$ nodes randomly in the area, and then we deploy the remaining $1000 - N 1$ nodes using a gamma distribution as explained below.

\begin{matrix} y = f (x | a, b) = \frac{1}{b^{a} Γ (a)} x^{a - 1} e^{- x / b}, (a = 1.5, b = 100) . \end{matrix}

(3)

In fact, we place

1000 - N 1

nodes in

(r, θ)

positions. Where r is determined according to (3) and θ is chosen uniformly. Our goal to guarantee the initial coverage tends to increase

N 1

whereas our objective to concentrate nodes on the critical ring tends to increase

1000 - N 1

and consequently decrease

N 1

. A compromise must be made. We try to decline

N 1

to the minimum point possible that the initial coverage remains more than 97%. Table 2 shows the average initial coverage obtained by MATLAB simulation for different values of

N 1

. According to Table 2,

N 1 = 600

is a reasonable choice to keep the initial coverage percentage over 97%.

Table 2

Average initial coverage of network for different values of $N 1$ .

Number of nodes deployed randomly ( $N 1$ )	Number of nodes deployed with gamma distribution ( $1000 - N 1$ )	Average initial coverage (%)
400	600	94.13
500	500	95.76
600	400	97.29

Table 3

Simulation parameters.

Parameter	Value
Number of nodes	1000
Initial energy of each node	5 [J]
Dimensions of monitored area	400 × 400 [m²]
$E_{elec}$	50 [nJ/bit]
$ϵ_{friss_amp}$	10 [pJ/bit/m²]
$ϵ_{t w o_ray_amp}$	0. 0066 [pJ/bit/m⁴]
$d_{cross-over}$	38.31 [m]
Packet rate	1 [packet/s]
$R_{sense}$	15 [m]

6. Simulation Results

We used the parameters indicated in Table 3 and our proposed nonuniform distribution. Figure 6 shows snapshots of the network after every 500 [s]. A comparison of Figures 6 and 2 will give us more insight into the network's operation over time. In uniform distribution scenario (Figure 2), the formation of a high-cost region around the base station initiating from early communication rounds is clearly observable. In Figure 2(d), which corresponds to $t = 2000$ [s], we can identify the mentioned area that develops by time as is illustrated in succeeding figures. However, network with our nonuniform distribution shows a more homogeneous behavior in sense of energy consumption. In Figure 6(h), which corresponds to a time approximately equivalent to the lifetime of the network with uniform distribution, the critical area has not been shaped yet resulting in the linear behavior of the network. Although we could not totally eliminate the formation of critical area, (due to the limitations imposed by the coverage-preserving requirements and limited number of nodes), we could greatly delay this event to reduce the nonlinearity of network.

Figure 6

Snapshots of network with our proposed distribution after every 500 [s].

Figure 7 shows the cost of nodes against their distance from center after every 500 [s]. Our effort to guaranty the homogeneous energy consumption over time translates into equalizing the cost of nodes located in various distances from the center during the network lifetime. By contrasting Figure 7 with Figure 4, we will observe the removal of the peak shaped in Figure 4 when the nonuniform distribution is applied. Due to the limitations discussed above, cost of nodes cannot be completely equal. However, its variation is substantially reduced.

Figure 7

Cost of nodes against their distance from the base station after every 500 [s] in a network with our proposed distribution.

Finally, Figure 8 shows changes in the total energy of the network over time using our method for distributing nodes in comparison with the uniform distribution. As it is illustrated, when using nonuniform distribution, the network remains its linear behavior for a longer period, so we expect a longer lifetime for the network. Theoretically, nonlinear behavior of the system emerges as soon as the formation of a high-cost corona that obliges forwarding packets to skip it during routing. Our approach in this paper was to find the most vulnerable area to energy depletion and make this area robust by concentrating more nodes and therefore more energy there. With a constant number of nodes and having in mind our obligation to satisfy the initial coverage threshold, we are confined to a predetermined number of nodes to deploy in critical regions. Therefore, although we can postpone the initiation of nonlinearity, we might not be able to completely eliminate it. In other words, we tend to make the critical region as robust as possible compared to the uniform distribution, but, considering the high traffic rate of this area, we cannot guaranty linear behavior throughout the whole lifetime.

Figure 8

Energy consumption of network using the proposed nonuniform distribution [red] compared to the uniform distribution [blue].

Figure 9 shows the coverage of network against time for both distributions. Using this figure, we can get a clear understanding of the improvement made in network's lifetime. As defined earlier, lifetime of the network is the amount of time that the coverage is more than 90%. According to Figure 9, a 66% improvement of the lifetime has occurred using the proposed distribution.

Figure 9

Coverage against time using the proposed nonuniform distribution [red] compared to the uniform distribution [blue].

7. Conclusion

In this paper, we studied the relation between nodes' location and their energy consumption in a wireless sensor network during the network's lifetime. We showed that the uniform distribution of nodes in the monitored area leads to inefficient use of energy resources. To find better distribution scenarios, we located critical areas in the network. Then, we proposed a proper solution that concentrates nodes on critical areas to the highest degree that is possible in order for the network to maintain its initial coverage more than a reasonable threshold. Using this scenario, we demonstrated the progress made in the lifetime by simulation results.

References

Culler

Estrin

Srivastava

Overview of sensor networks

Computer 2004 37 8 41 49

2-s2.0-4344668573

10.1109/MC.2004.93

Liu

Underground coal mine monitoring with wireless sensor networks

ACM Transactions on Sensor Networks 2009 5 2, article 10 29

2-s2.0-61449091346

10.1145/1498915.1498916

Hedetniemi

Liestman

A survey of gossiping andbroadcasting in communication networks

Networks 1988 18 4 319 349

Heinzelman

Kulik

Balakrishnan

Adaptive protocols for information dissemination in wireless sensor networks

Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99)

August 1999

Seattle, Wash, USA

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of The 33rd Annual Hawaii International Conference on System Siences (HICSS-33 '00)

January 2000

2-s2.0-0033877788

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for Ad Hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

2-s2.0-10944266504

10.1109/TMC.2004.41

Gupta

Younis

Load-balanced clustering in wireless sensor networks

Proceedings of the Proceedings of the International Conference on Communication (ICC '03)

May 2003

Anchorage, Alaska, USA

Bandyopadhyay

Coyle

E. J.

An energy efficient hierarchical clustering algorithm for wireless sensor networks

Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '03)

April 2003

San Francisco, Calif, USA

1713 1723

Ghiasi

Srivastava

Yang

Sarrafzadeh

Optimal energy aware clustering in sensor networks

Sensors 2002 2 7 258 269

2-s2.0-0242513481

10.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

2-s2.0-33646589837

10.1109/TWC.2002.804190

11.

Chang

J. H.

Tassiulas

Energy conserving routing in wireless Ad-Hoc networks

Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM '00)

March 2000

22 31

2-s2.0-0033885342

12.

Chang

J.-H.

Tassiulas

Maximum lifetime routing in wireless sensor networks

Proceedings of the Advanced and Information Distribution Research Program (ATIRP '00)

March 2000

College Park, Md, USA

13.

Soro

Heinzelman

W. B.

Cluster head election techniques for coverage preservation in wireless sensor networks

Ad Hoc Networks 2009 7 5 955 972

2-s2.0-60249083032

10.1016/j.adhoc.2008.08.006

14.

Lian

Naik

Agnew

La Porta

Phoha

Modeling and Enhancing the Data Capacity of Wireless Sensor Networks

Sensor Network Operations 2005 chapter 3.5

New York, NY, USA

IEEE Press

157 179

15.

Lian

Naik

Agnew

G. B.

Data capacity improvement of wireless sensor networks using non-uniform sensor distribution

International Journal of Distributed Sensor Networks 2006 2 2 121 145

2-s2.0-34548851055

10.1080/15501320500201276

16.

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