Dynamic Hierarchical Communication Paradigm for Wireless Sensor Networks: A Centralized, Energy Efficient Approach

doi:10.4236/wsn.2009.14042

Paper Menu >>

Journal Menu >>

Wireless Sensor Network, 2009, 1, 340-349

doi:10.4236/wsn.2009.14042 Published Online November 2009 (http://www.scirp.org/journal/wsn).

Dynamic Hierarchical Communication Paradigm for

Wireless Sensor Networks: A Centralized,

Energy Efficient Approach

Suraiya TARANNUM1, S. Srividya2, D. S. Asha2, K. R. Venugopal2

1Department of Telecommunication Engineering, AMC Engineering College, Bangalore, India

2Department of Computer Science and Engineering, Bangalore University, Bangalore, India

Email: [email protected]

Abstract

A Wireless Sensor Network (WSN) consists of a large number of randomly deployed sensor nodes. These

sensor nodes organize themselves into a cooperative network and perform the three basic functions of sens-

ing, computations and communications. Research in WSNs has become an extensive explorative area during

the last few years, especially due the challenges offered, energy constraints of the sensors being one of them.

In this paper, the need for effective utilization of limited power resources is emphasized, which becomes

pre-eminent to the Wireless Sensor Networks. Organizing the network to achieve balanced clusters based on

assigning equal number of sensors to each cluster may have the consequence of unbalanced load on the clus-

ter heads. This results in an unbalanced consumption of energy by the nodes, cumulatively leading to mini-

mization of network lifetime. In this paper, we put forth a Sink administered Load balanced Dynamic Hier-

archical Protocol (SLDHP) to balance the load on the principal nodes. Hierarchical layout of the sensors en-

dows the network with considerable minimization of energy consumption of nodes leading to an increased

lifespan. Simulation results indicate significant improvement of performance over Base station Controlled

Dynamic Clustering Protocol (BCDCP).

Keywords: Wireless Sensor Network, Sink, Principal Node, Superior Node, Network Lifetime

1. Introduction

A Wireless Sensor Network (WSN) is an ad-hoc wireless

telecommunication network which embodies a number

of tiny, low-powered sensor nodes densely deployed

either inside a phenomenon or close to it [1]. The multi-

functioning sensor nodes operate in an unattended envi-

ronment with limited sensing and computational capa-

bilities. The advent of wireless sensor networks has

marked a remarkable change in the ﬁeld of information

sensing and detection. It is a conjunction of sensor, dis-

tributed information processing, embedded and commu-

nication techniques. WSNs may in the near future be

equally prominent by providing information of the

physical phenomena of interest and ultimately being able

to detect and control them or enable us to construct more

meticulous models of the physical world.

WSNs are easier, faster and cheaper to deploy than

other forms of wireless networks as there are no prede-

termined positions for the sensors. They have higher de-

gree of faulttolerance than other wireless networks and

are self-conﬁguring or self-organizing [2]. Sensors are

deployed randomly and are expected to perform their

mission properly and efﬁciently. Another unique feature

of sensor networks is the co-operative effort of sensor

nodes to achieve a particular task.

A WSN is envisioned to consist of a large number of

sensors and many base stations. The sensors are equipped

with transceivers to gather information from the environ-

ment and pass it on to one of the base stations. A typical

sensor node consists of four major components: a data

processor unit; a sensor; a radio communication subsystem

that consists of transmitter/receiver electronics, antennas, an

ampliﬁer; and a power supply unit [3]. The sensors are

compact in size which make them extremely energy re-

strained. Further more, replacing batteries in large scales in

possibly harsh terrain becomes infeasible. Hence, it is well

accepted that the key challenge in unlocking the potential of

such networks is maximizing their post-deployment active

lifetime. The lifetime of the wireless sensors may be pro-

longed by ensuring that all aspects of the system achieve

energy efﬁciency. Since communications in wireless sensor

networks consume signiﬁcant amount of energy, the de-

signed algorithms must ensure that nodes expend minimum

amount of energy for transmitting and receiving data.

S. TARANNUM ET AL. 341

A web of sensor nodes can be deployed to gather

productive information from the sensor ﬁeld. Some of

the beneﬁts of using WSNs are extended range of

sensing, fault-tolerance, improved accuracy and lower

cost. As a consequence, the sensor networks are ex-

pected to ﬁnd extensive use in a variety of applications

including remote climate monitoring, seismic, acoustic,

medical and intelligence data-gathering [4,5]. Hence,

they are suitable for a wide range of applications like

military, health, education, commerce and so on. Mili-

tary applications may range from tracking enemy

movement in the battleﬁeld to guiding targeting system.

Bio-sensors are used for monitoring patients blood

sugar level. Commercial applications may range from

tracking postal packages or office equipment to moni-

toring product quality on an assembly line. Environ-

mental applications include forest-ﬁre detection, ﬂood

detection, tracking movements of birds etc. Sensors are

also used to simulate home automation and to build

smart environments.

Efﬁcient utilization of energy is crucial to the WSNs.

Wireless microsensor network protocols should therefore

be selfconﬁguring to enable ease of deployment of nodes,

latency aware, qualitative, robust and to extend system

lifetime. The sensors are extremely energy bounded,

hence the network formed by these sensors are also en-

ergy constrained. The communication devices on these

sensors are small and have limited power and sensing

ranges. A routing protocol coordinates the activities of

individual nodes in the network to achieve global goals

and does it in an efﬁcient manner. The simplest is the

Direct Communication Routing Protocol, where each

node transmits the sensed information directly to the

base station. The nodes consume considerable amount of

energy if the communication path is long. This results in

the early death of distant nodes. To overcome this draw-

back, the technique of Minimum Transmission Energy

utilizes a multhop routing scheme. In this scheme, the

nodes that are close to the base station drain their energy

rapidly as they are involved in transmission of messages

on behalf of others.

Hierarchical routing groups sensors in the entire net-

work into clusters. It aims at reduction of energy con-

sumption by localizing data communication within a

cluster and aggregating data to decrease transmissions to

the base station. The ﬁrst attempt in this regard, was

made by Low Energy Adaptive Cluster Hierarchy

(LEACH). The operation is framed in iterations and each

iteration comprises of a setup and a data transmission

phase. During the setup phase, nodes organize them-

selves into clusters with predetermined number of

nodes serving as cluster heads. In the data transmission

phase, the self-elected cluster heads aggregate data re-

ceived from the nodes in their cluster before forwarding

to the base station. The role of cluster heads is randomly

rotated among all the nodes in the network. This tech-

nique serves as a basic model for other hierarchical rout-

ing protocols. A centralized version of the adaptive ap-

proach comprises a hierarchical structure in which the

base station has control over the cluster formation. The

base station uses the location and energy information

sent by the nodes to select the predetermined number of

cluster heads. Efﬁcient clustering is achieved as the base

station possess the global knowledge of the network.

This technique exhibits improvement over the adaptive

approach.

In Power Efﬁcient Gathering in Sensor Information

Systems (PEGASIS), the nodes function co-operatively

to optimize network lifetime. A greedy algorithm is used

to conﬁgure the network into chains. In each iteration, a

randomly chosen leader node directs the aggregated data

to the base station. A centralized energy efﬁcient routing

protocol called Base Station Controlled Dynamic Clus-

tering Protocol (BCDCP), was proposed which widened

the area for research in hierarchical routing. Here, much

of the functionalities like formation of clusters and rout-

ing paths are performed by the high energy base station

which lightens the load of sensor nodes. This protocol

conﬁgures the network into balanced clusters where each

cluster head serves an approximately equal number of

member nodes. Cluster head-to-cluster head multihop

routing is employed in this protocol to transfer the data

to the base station.

Motivation: Efﬁcient management of energy deserves

much of the attention in the WSNs. Routing protocols

designed for WSNs must therefore effectively tackle this

issue in order to enhance the lifetime of the network.

Hierarchical routing techniques are preferable in this

direction. The arrangement of the nodes in the form of a

load balanced hierarchy proves to be beneficial.

Contribution: In our paper, we propose a energy effi-

cient hierarchical routing protocol, SLDHP to increase

the lifetime of homogeneous as well as heterogeneous

WSNs. SLDHP achieves a load balanced hierarchical

arrangement of nodes in the network which performs

better than the other hierarchical routing protocols.

Organization: The rest of the paper is organized as

follows. In section II, we discuss the related work. In

section III, the underlying model is described and the

problem is deﬁned in section IV. Our proposed algorithm,

SLDHP is presented in section V. Performance analysis

is presented in section VI and section VII contains the

conclusion.

2. Related Work

Hierarchical routing aims to efﬁciently maintain the en-

ergy consumption of sensor nodes by involving them in

multihop communication within a particular cluster and

342 S. TARANNUM ET AL.

Figure 1. Three main topologies of hierarchical routing

protocols.

by performing data aggregation and fusion to decrease

the number of transmitted messages to the base station.

Heinzelman et al. [6] proposed an adaptive clustering

protocol. This approach employs the technique of ran-

domly changing the role of cluster head among all nodes

in the sensor network. The operation of this protocol is

organized into different iterations where each iteration

consists of a setup phase and a transmission phase. Dur-

ing setup phase, nodes organize themselves into clusters

in which cluster head is elected locally within each clus-

ter. During transmission phase, the self elected cluster

heads aggregate data received from all the nodes within

its cluster, applies a data fusion technique before sending

it directly to the base station. In this method, the decision

is made per iteration and it is assumed that we have a

knowledge of the total residual energy of the network.

In [7], a centralized algorithm for routing is described.

This protocol uses the base station for centralized com-

putation of cluster heads. The base station upon receiving

the location and energy level information from the sensor

nodes during the setup phase, locates a predetermined

number of cluster heads and conﬁgures the entire net-

work into clusters. The cluster heads are chosen in such a

way that nodes consume minimum energy for transmit-

ting their data. The shortcoming may be that they drain

their energy rapidly as they have to communicate di-

rectly with the base station irrespective of their positions.

The results in [7] show improvement over [6].

A chain based protocol is presented in [8]. In this pro-

tocol, each node communicates only with a close

neighbour and takes turns to transmit to the base station,

thus reducing the amount of energy spent per iteration.

For constructing a chain, it is assumed that all nodes

have global knowledge of network. A greedy algorithm

is employed to ensure that nodes already on the chain

need not be revisited. Here, even though the forwarding

node has capability of taking more load, it is not assigned

if it is already on the chain.

A centralized clustering based routing protocol is dis-

cussed in [9]. According to this protocol, energy inten-

sive tasks such as cluster setup, cluster head selection,

routing path formation and TDMA schedule creation are

performed by the base station which is assumed to have

unlimited power supply. This protocol conﬁgures the

network into balanced clusters, i.e., the number of nodes

in each cluster are same. Such equal clustering results in

an unequal load on the cluster head.

Guangyan et al. [10] have reviewed the energy

efﬁciency of cluster based routing protocols with ex-

tended conditions of general complexity of data fusion

algorithm, general data compressing ratio and long dis-

tances. They present three discoveries, ﬁrst of which is

that data fusion algorithm is computed based on applica-

tions. Secondly, multihop scheme not used by earlier

works could sometimes prove beneﬁcial. Thirdly, when

network area is larger than 200mx200m, the number of

high energy dissipating nodes are more which accelerates

the death of nodes. These ﬁndings guide in improving

the routing protocols and hence to extend their applica-

tion ranges.

Geographic and energy aware routing algorithm de-

veloped by Yan Yu et al. [11], propagates a query to the

appropriate geographical region without ﬂooding. The

protocol uses energy aware and geographically informed

neighbor selection to route a packet towards the target

region. To disseminate the packet inside the destination

region, a recursive geographic forwarding or restricted

ﬂooding algorithm is used. The protocol exhibits no-

ticeably longer network lifetime as compared to non-

energy aware geographic routing algorithms.

A novel algorithm proposed by Andrea in [12], per-

forms three main functions of conﬁguring the network

into optimum number of clusters, decentralized cluster

head selection and cluster formation. The value of opti-

mum number of clusters depends on total number of

sensors in the network, on the path-loss exponent (α), on

S. TARANNUM ET AL. 343

dimensions of the network and distance of the broadcast

packets. They use an adaptive strategy for cluster head

selection. The algorithm for cluster formation uses total

path energy dissipation instead of energy lost in path

from the node to its cluster head. The algorithm opti-

mizes system lifetime in a large range of applications and

situations.

A cost based comparison of homogeneous and het-

erogeneous clustered sensor networks has been presented.

It ﬁrst considers single hop clustered sensor networks

and use adaptive clustering protocol. It also takes into

account sensor-network with two types of nodes as rep-

resentative single hop heterogeneous networks. For mul-

tihop homogeneous network Vivek et al. [13] propose

and analyze a multihop variant of the adaptive approach.

They consider communication radius for in-cluster

communication and size of clusters. This algorithm ex-

hibits better energy efﬁciency in many cases, but does

not give expected performance if the heterogeneity is due

to the operation of the network.

An energy efﬁcient distributed clustering approach for

adhoc sensor network is developed in paper [14]. In this

approach, cluster heads are chosen randomly based on

their residual energy and nodes participate in cluster op-

eration such that the communication cost is minimized.

The protocol does not make any assumptions regarding

the distribution density of nodes. The clustering process

takes a ﬁxed number of iterations and does not depend

on network topology. This protocol acheives only a

two-level hierarchy.

Alan et al. [15] have derived a load balancing heuristic

for wireless adhoc networks in order to extend the life-

span of a cluster head to as large an extent as possible

before another node becomes the cluster head. Two

cluster head load balancing heuristics are described. The

ﬁrst approach is for cluster election heuristics that favour

the election of cluster head based on node-id, and the

second approach is based on the degree of connectivity.

In [16], a cluster based query protocol is illustrated for

wireless sensor networks using self-organized sensor

clusters to register queries, process queries and dissemi-

nate data within the network. This protocol uses cluster

heads as data storage and aggregation points. Instead of

sending large amounts of raw data over a network to

reply to a query, each cluster head collects and ﬁlters

data from its member sensors. This is achieved using the

information about the cluster location. With this protocol,

energy efﬁciency is achieved by reducing the number of

data transmissions over the network during the course of

the data collection and query processing.

A stable election protocol is described in [17] which is

a heterogeneous-energy-aware protocol. It is based on

weighted election probabilities of each node to become

cluster head based on the remaining energy of each node.

In this approach every sensor node in a heterogeneous

two-level hierarchical network independently elects itself

as a cluster head based on its initial energy relative to

that of other nodes. The protocol does not demand any

global knowledge of energy at every election iteration

and also does not consider as to how nodes could be as-

signed optimally to cluster heads.

In [18], a balanced k-clustering algorithm, for cluster-

ing sensor nodes into k number of clusters is described.

Each cluster is balanced and the total distance between

sensor nodes and the head nodes is minimized. Mini-

mizing the total distance helps in reducing the commu-

nication overhead and hence energy dissipation. The

algorithm demonstrates that the balanced k-clustering

problem can be solved optimally using network ﬂow, but

assumes the number of nodes as a multiple of k at all

times, which may not be practical.

A cluster based routing algorithm is depicted in [19] to

extend the lifetime of the sensor networks and hence to

maintain a uniform consumption of the energy by the

nodes. This is obtained by the addition of a slot in a

frame, which enables the exchange of residual energy

messages between the base station, cluster heads and

nodes. The algorithm takes into account the residual en-

ergy of the nodes during cluster head selection, resulting

in balanced energy consumption of the sensor nodes. The

protocol performs better than the adaptive approach.

In [2], the authors focus on the design criteria for

routing protocols and issues and challenges of clus-

ter-based routing in WSNs. The characteristics and the

general routing models for protocols in sensor networks

are studied here. Yunfeng et al. [20] have devised a pro-

tocol called energy balancing multipath routing, the basic

idea being that instead of source-initiated or destina-

tion-initiated route discovery, it is the base station that

ﬁnds multiple paths to the source of the data and selects

one of them to be used during communication. It is based

on the assumption that the base stations are typically

many orders of magnitude more powerful than common

sensor nodes. It adopts a scheme similar to the well

known software architecture client server model.

Energy aware routing that uses sub-optimal paths oc-

casionally to provide substantial gains is designed by

Rahul et al. [22]. It emphasizes that using lowest energy

paths may not be always optimal from the point of view

of network lifetime and long-term connectivity. The

protocol is suitable for low energy and low bitrate net-

works. The key concept is to send trafﬁc through differ-

ent routes which helps in using the node resources more

evenly. It sends the trafﬁc on multiple paths without

adding much complexity by using a probabilistic for-

warding technique. According to this method, the nodes

burn their energy uniformly across the network ensuring

a more graceful degradation of service with time.

The problem of energy-aware routing in networks with

renewable energy sources is adressed by Longbi et al.

[21]. They present a simple, static multi-path routing

approach that is optimal in the large system limit. The

344 S. TARANNUM ET AL.

proposed static routing scheme utilizes the knowledge on

the trafﬁc patterns and energy consumption, and does not

demand the instantaneous information about the node

energy. For the distributed computation of the optimal

policy, they outline the possible approaches and propose

heuristics to build the set of pre-computed paths. This

scheme outperforms leading dynamic routing algorithms,

and is close to an optimal solution when the energy

claimed by each packet is relatively small compared to

the battery capacity.

3. Model

3.1. The Nomenclature

The terminology used in our study are,

HmNt Homogeneous Network consists of sensors

possessing a uniform initial energy.

HtNt Heterogeneous Network comprises of sensors

with different initial energies.

Set of all the sensor nodes deployed in the

sensor ﬁeld of the network.

Eavg This is deﬁned as the average energy of the

wireless sensor network.

avg k

n

E (1)

where n is the number of the sensors and Ek is theenergy

of the kth sensor.

Set consisting of sensor nodes with energy

equal to or greater than Eavg, and is a subset of set ,

which is a set of all the sensor nodes deployed in the

network.

PrNd Principal Node is a node which receives the

sensed data from other nodes in its hierarchy, aggregates

it to forward either to another principal node or to the

Superior Node. This functions as the root of the hierar-

chy and sends the aggregated message to the sink.

nmin Minimum energy node.

3.2. Radio Power Model

A typical sensor node is depicted in Figure 2 and con-

sists of four major components: a data processor unit; a

micro-sensor; a radio communication subsystem that

consists of transmitter/receiver electronics, antennas

and an ampliﬁer; and a power supply unit. [23]. Al-

though energy is dissipated in all of the ﬁrst three

components of a sensor node, energy dissipations as-

sociated with the radio component is considered since

the core objective of this study is to develop an en-

ergy-efﬁcient network layer protocol to improve the

network lifetime. In addition to this, energy dissipated

during data aggregation in the cluster heads is also

accounted.

Figure 2. A typica l se nsor node.

The radio energy model [9] employed in our study is

described in terms of the energy dissipated in transmit-

ting k-bits of data between two nodes separated by a dis-

tancer meters and also the energy spent for receiving at

the destination sensor node and is given by,





TTxamp

EkrEkEr k





  (2)





amp FS

Erεr



 (3)

The energy cost incurred in the receiver is given by,





RRx

EkE k



 (4)

where denote energy dissipated in the transmitter

of the source node is required to maintain an acceptable

signal-to-noise ratio for reliable transfer of data messages.

We use free space propagation model and hence the en-

ergy dissipation of the ampliﬁer is given by:

amp





amp FS

Er r (5)

where FS



denotes the transmit ampliﬁer parameter

corresponding to free space.

The assumed values for the various parameters is as

given below.

50n

Tx Rx

EE J/bit



10 //

FS pJbitm





The energy spent for data aggregation is,

5nJ / bit/ message.



4. Problem Definition

A sensor network is described by means of an edge-

weighted graph, (

WSN

G, , Sink),





n, 2n

n ....n

is a set of sensor nodes and



d, d .



...d contains

the inter-node distances.

The objectives of our work are:

1) To develop an energy-efficient hierarchical routing

algorithm which minimizes the energy consumption of

the network.

S. TARANNUM ET AL. 345

2) To maximize the network lifetime.

4.1. Assumptions

 WSN consisting of a ﬁxed sink with unlimited sup-

ply of energy and n wireless sensor nodes having

limited power resources.

 The wireless sensor network can be either homo-

geneous or heterogeneous in nature.

 The nodes are equipped with power control capa-

bilities to vary their transmitted power.

 Each node senses the environment at a ﬁxed rate

and always has data to send to the sink.

 The sensor nodes are aware of their geographic

position as each of them are equipped with a Global

Positioning System (GPS).

5. Sink Administered Load Balanced Dynamic

Hierarchical Protocol (SLDHP)

This section focuses on design details of our proposed

protocol SLDHP, which is a hierarchical wireless sen-

sor network routing protocol. Here the sink with unre-

strained energy plays a vital role by performing energy

intensive tasks thereby bringing out the energy

efﬁciency of the sensors and rendering the network

endurable. The pattern of the hierarchy varies dynami-

cally as it is based on energy levels of the sensors in

each iteration.

SLDHP functions in two phases namely:

1) Network Conﬁguring Phase

2) Communication Phase.

The algorithm steps are described in Table 1.

5.1. Network Conﬁguring Phase

The goal of this phase is to establish optimal routing paths

for all the sensors in the network. The key factors consid-

ered are balancing the load on the principal nodes and

minimization of energy consumption for data communica-

tion. In this phase, the sink probes the sensors to send the

status message that encapsulates information regarding their

geographical position and current energy level. The sink

upon receiving this, stores the information in its data struc-

tures to facilitate further computations. To construct the

routing path, ﬁrst the sink traces the node with minimum

energy, from the set N. The minimum energy node

will be alloted to the principal node, which will be

selected based on the following criteria:

min

 The sink reckons the set , that contains nodes

with energy above Eavg, which is a subset of set .

 It then computes the distance between nmin and each

of the nodes in . Consider any two nodes with

respective x and y positions given by (x1, y1) and (x2,

y2). The Euclidean Distance between these two

nodes is given by:



12 12

| - | | - |xx yy2

(6)

 The node in the set P which has minimum distance

to min

n is selected as the principal node.

To aid further calculations, the amount of energy spent by

the principal node on receiving and aggregating message

sent from is reduced virtually. The minimum energy

node is then removed from the set

min

. This phase repeats

until all the nodes in the network are assigned to principal

nodes. The last node that remains in set is the node with

maximum energy which serves as a superior node and has

the job of sending the aggregated message to the sink.

The protocol gives prime importance to balance the

load on the principal nodes. The minimum energy nodes

will be assigned to a principal node as long as it has the

capability to handle them. Once the energy of the princi-

pal node falls below Eavg, it will be treated as a normal

node and hence will be assigned to another principal

node. In this way, multihop minimal spanning tree is

constructed without a need for running a separate mini-

mal spanning tree algorithm. Figure 3 depicts the hier-

archical setup of our protocol.

SLDHP eliminates the necessity of knowing the opti-

mum number of clusters in the network. The load is

evenly balanced depending upon the capacity of the

principal nodes. The protocol starts with a chaining setup

and ends in a hierarchical model. In this way, multihop,

load balanced network is achieved. The concluding task

of this phase is to determine the Time Division Multiple

Access (TDMA) slots for all the nodes within the hier-

archy. Once all the computations are over, the sink sends

messages to all the sensors indicating their principal

nodes and the TDMA slots.

5.2. Communication Phase

The sensors send their sensed data to their respective

principal nodes. Each of the principal nodes gather data

from the nodes down in their hierarchy, fuses and then

forwards either to another principal node or to the sink.

This phase inturn comprises of three activities.

 Data gathering: utilizes a time-division multiple

access scheduling scheme to minimize collisions

between sensor nodes trying to transmit data to the

principal node.

 Data fusion or aggregation: Once data from all

sensor nodes have been received, the principal node

combines them into a target entity to greatly reduce

the amount of redundant data sent to the sink.

 Data routing: Transfers the data along the principal

node-to-principal node routing to the superior node,

which transmits the fused data to the sink.

346 S. TARANNUM ET AL.

Table 1. SLDHP algorithm.

6. Performance Analysis

6.1. The Simulation Test-Bed

A homogeneous sensor network was set up with the

simulation environment comprising 100 nodes, with all

nodes possesing the same initial energy of 2J. The simu-

lations were carried out using the Objective Modular

Network Testbed in C + + (OMNeT++) simulator [24].

The sensor nodes were deployed randomly in a sensor

ﬁeld of a grid size of 500mx500m. The simulations were

carried out several times, for different network

conﬁgurations in order to obtain consistent results. The

performance metrics considered are Average Energy

Consumption by the nodes and Network Lifetime. The

proposed protocol was compared with BCDCP and it

was found that SLDHP performed signiﬁcantly better in

all simulation runs.

6.2. Average Energy Consumption of the Sensor

Network

Figure 4 shows the Average Energy Consumption of the

sensor network, as a variation with reference to number

of iterations of the network. The simulation environment

is setup with the initial battery energy of all nodes being

2J and a message length of 4 kbits/packet. We observe

that the protocol greatly reduces the energy consumed

and hence outperforms others in terms of battery

efﬁciency. This is due to the minimum-spanning tree

hierarchical structure formed by SLDHP as compared to

the cluster-based structure which consists of equal num

Figure 3. Hierarchical setup of SLDHP.

ber of member nodes with unequal distribution of energy.

BCDCP achieves balancing by assigning equal number

of nodes to each of the clusters which results in over-

loading the already overloaded cluster-heads to drain out

much of their energy on receiving, aggregating and

transmitting the data at a much faster rate. In comparison,

our proposed algorithm comprises of unequal member

nodes within the hierarchy, but load balanced in terms of

energy resources, which contributes signiﬁcantly to the

increased energy efﬁciency of the algorithm. Hence the

packet transmission time in our algorithm is predomi-

nantly short as compared to others. From the plot, it is

observed that initially when the number of iterations is

less, energy consumption in both the schemes is found to

be almost the same, with no conspicuous results. This is

due to the fact that the hierarchical structure at this point

of time seems almost the same. The real advantage

comes to light when the number of iterations increases,

with the hierarchical structure adapting itself dynami-

cally to the changing scenario. The superior performance

offered by SLDHP enables to achieve a reduction of en-

ergy consumption by about 21% as compared to the ear-

lier algorithms.

6.3. Sensor Network Lifespan

The energy consumption rate can directly inﬂuence the

lifes-pan of the sensor nodes as the depletion of battery

resources will eventually cause failure of the nodes.

Hence the wireless engineer is always entrusted with the

task of prolonging the lifespan of the network by im-

proving the longevity of the sensor nodes. The simula-

tion results of number of nodes alive over a period of

time are presented in Figure 6. The simulation environ-

ment is the same, i.e., initial energy of nodes being 2J,

message length being 4 kbits/packet and the initial node

density being 100. Both the protocols are based on a hi-

erarchical structure in which all the nodes rotate to take

responsibility for being the cluster-head and hence no

particular sensor is unfairly exploited in battery con-

sumption. Due to the hierarchical structure, it is found

that till the 806th iteration, the number of nodes that are

alive is almost the same in both schemes and equals 100.

S. TARANNUM ET AL. 347

This implies that the time duration between the ﬁrst ex-

hausted node and the last one is quite short or the differ-

ence in energy levels from node to node does not vary

greatly for lower number of iterations. After this critical

point, both the curves in the Figure drop indicating the fall

in the number of alive nodes. It is evident from the plot that

the number of alive nodes is signiﬁcantly more in our pro-

tocol as compared to other and which agrees with the re-

sults obtained in the previous simulation. This algorithm

can extend the lifespan of the network by about 34% as

compared to the earlier algorithm. It is observed that the

number of alive nodes in earlier algorithm is a maximum of

100, dropping at a steady rate till none of the nodes are

found to be alive at the 1800th iteration. In comparison, the

nodes of SLDHP are very much live and active even for a

little beyond the 2000th iteration, once again indicating the

superior performance of the algorithm. The reason for this

is again the same, the difference in hierarchical structure,

plus the added advantage of dynamically having a load

balancing scheme.

6.4. Average Energy Consumption for Varying

Message Lengths

Figure 5 shows the average energy consumption of the

network when SLDHP is run with the data communication

phase transmitting data at varying message lengths of

4kbits/packet and 8kbits/packet respectively. From the

plot, it is observed that when the message length is 4

kbits/packet, the behaviour is exactly similar to the one

depicted in Figure 4 for SLDHP due to the similarities of

the simulation environment set up. When the message

length is doubled, the average energy consumption of the

sensor network is much more as observed from the simu-

lation results. This is quite obvious because of greater

overhead involved in aggregating and transmitting a larger

sized message. From the plot, it is seen that at the end of

the 2000th iteration, the energy consumed for transmitting

a smaller message is close to 2J while the same energy

level is reached in the 1620th iteration itself, for a larger

message transmission. A message length of 4 kbits/pkt

seems ideal as lesser length message may not be in a posi-

tion to carry out the desired task and a larger length may

unnecessarily contribute to additional overhead which can

degrade the performance of the network.

The plots in Figure 7 show the average energy con-

sumption of the network with proposed algorithm run for

two different message lengths. The simulation environ-

ment is set up with all the nodes equipped with a uniform

initial energy of 2J. The node density is varied to account

for scalability of the WSN and at the same time will aid

in understanding the behaviour of the network especially

in terms of energy management of the network for vary-

ing node densities. For comparatively lower value of

node density, the average energy consumption of the

network is smaller being a little less than 0.06J for a

Figure 4. Comparison of average energy consumption.

Figure 5. Average energy consumption (SLDHP) with vari-

able size of the packet.

smaller message length, increasing steadily to about

0.09J for a node density of 100. In comparison, it is

found that the energy consumption is relatively more for

a larger sized message, varying from 0.078J for 40 nodes

reaching a value of 0.12J for 100 nodes. This behavior is

much the same as for a smaller message, the difference

being that obviously more energy is consumed for a lar-

ger message size. As the number of nodes increase, the

complexity of the network conﬁguring phase also in-

creases proportionately leading to an increased overhead

on the sink to dynamically form load balanced hierar-

chical structures. The complexity of the data communi-

cation phase is no less, with more number of nodes being

involved in data communications and with the complex-

ity increasing with increasing nodes. The energy con-

sumption of the network increases in proportion to the

number of nodes and the same analogy holds good for

348 S. TARANNUM ET AL.

Figure 6. Comparison of lifespan of the wireless sensor

network.

different message lengths, the consumption being much

more for larger sized messages.

6.5. Network Lifespan for Varying Size of Packet

Figure 8 shows another performance run when com-

munications in SLDHP, take place by transmitting

varying length messages of 4 kbits/packet and 8

kbits/packet. The simulations are carried out under

similar conditions. As seen from the plot, when the

message length is 4 kbits/packet, larger number of

nodes are alive and the same is conﬁrmed by the results

obtained in Figure 6. When the message length is dou-

bled, the saturation of the network takes place at a

faster rate due to increased overhead on the sensor

nodes and the principal nodes in particular. This mani-

fests in nodes consuming larger energy, resulting in a

larger transmission cost, leading to a shorter lifespan of

the network. The smaller the message length, greater is

the lifespan of the network with the number of live

nodes prolonging the network lifespan to as long as the

2000th iteration. Till the 1400th iteration, the number of

alive nodes in both cases seems exactly the same, but

drops abruptly to zero at the 1635th iteration, for a

larger message length. The reason for this is the same

as described for Figure 6 and hence the same inference

can be drawn here as well. Hence it is inferred that

4kbits/packet is apt for the present scenario.

7. Conclusions

A WSN is composed of tens to thousands of sensor

nodes which communicate through a wireless channel for

information sharing and processing. The sensors can be

Figure 7. Average energy consumption (SLDHP) for dif-

ferent packet lengths.

Figure 8. Lifespan of the wireless sensor network (SLDHP)

with variable size of packet.

deployed on a large scale for environmental monitoring

and habitat study, for military surveillance, in emergent

environments for search and rescue, in buildings for in-

frastructure health monitoring, in homes to realize a

smart environment. SLDHP manages to balance the load

on the principal nodes and hence the sensor nodes are

relieved from the energy intensive tasks such as forma-

tion of hierarchy and scheduling of slots to send their

sensed data. This job is effectively accomplished by the

high powered sink. The simulation results indicate that

the network lifetime is elevated to a large extent when

S. TARANNUM ET AL. 349

compared to other hierarchical routing protocols. The

future work includes applying our protocol to a distrib-

uted wireless sensor network and hence to improve the

network performance as in present scenario.

8. References

[1] E. Shih, S. H. Cho, N. Ickes, R. Min, A. Sinha, A. Wang,

and A. Chandrakasan, “Physical layer driven protocol and

algorithm design for energy-efﬁcient wireless sensor

networks,” Seventh Annual ACM SIGMOBILE Confer-

ence on Mobile Computing and Networking, July 2001.

[2] J. Ibriq and I. Mahgoub, “Cluster-based routing in wire-

less sensor networks: Issues and challenges,” SPECTS,

pp. 759–766, 2004.

[3] I. F. Akylidiz, W. L. Su, Y. Sankarasubramaniam, and E.

Cayirci, “Wireless sensor network: A survey on sensor

networks,” IEEE Communications Magazine, Vol. 40,

No. 8, pp. 102–114, August 2002.

[4] M. Bhardwaj and A. P. Chandrakasan, “Bounding the

lifetime of sensor networks via optimal role assign-

ments,” Twenty-First Annual Joint Conference of the

IEEE Computer and Communications Society, INFO-

COMM, 2002.

[5] J. Agre and L. Clare, “An integrated architecture for co-

operative sensing networks,” IEEE Computer Magazine,

pp. 106–108, May 2000.

[6] W. B. Heinzelman, A. P. Chandrakasan, and H.

Balakrishnan, “Energy-efﬁcient communication protocol

for wireless microsensor networks,” Proc. 33rd Hawaii

Int’l. Conf. Sys. Sci., January 2000.

[7] W. B. Heizelman, A. P. Chandrakasan, and H. Balakrish-

nan, “An application-speciﬁc protocol architecture for

wireless microsensor networks,” IEEE Transactions on

Wireless Communications, Vol. 1, No. 4, pp. 660–670,

October 2002.

[8] S. Lindsey, C. Raghavendra, and K. M. Sivalingam,

“Data gathering algorithms in sensor networks using en-

ergy metrics,” IEEE Trans. Parallel and Distrib. Sys., Vol.

13, No. 9, pp. 924–935, September 2002.

[9] S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin, and A. O.

Fapojuwo, “A centralized energy-efﬁcient routing proto-

col for wireless sensor networks,” IEEE Communications

Magazine, Vol. 43, pp. 8–13, March 2005.

[10] G. Huang, X. Li, and J. He, “Energy-efﬁciency analysis

of cluster-based routing protocols in wireless sensor net-

works,” IEEE Aerospace Conference, March 2006.

[11] Y. Yu, R. Govindan, and D. Estrin, “Geographical and

energy aware routing: A recursive data dissemination

protocol for wireless sensor networks,” UCLA Computer

Science Department Technical Report UCLA/CSD-

TR-01-0023, pp. 159–169, May 2001.

[12] A. Depedri, A. Zanella, and R. Verdone, “An energy

efﬁcient protocol for wireless sensor networks,” Decem-

ber 2003.

[13] V. Mhatre and C. Rosenberg, “Homogeneous vs hetero-

geneous sensor networks: A comparative study,” Pro-

ceedings of International Conference on Communications

(ICC 2004), June 2004.

[14] O. Younis and S. Fahmy, “HEED: A hybrid, energy-

efﬁcient, distributed clustering approach for ad hoc sen-

sor networks,” IEEE Transactions on Mobile Computing,

Vol. 3, No. 4, December 2004.

[15] A. D. Amis and R. Prakash, “Load-balancing clusters in

wireless ad hoc networks,” Proceedings of the 3rd IEEE

Symposium on Application-Speciﬁc Systems and Soft-

ware Engineering Technology (ASSET’00), 2000.

[16] Z. Zhang and G. Zheng, “A cluster based query protocol

for wireless sensor networks,” The 8th International Con-

ference on Advanced Communication Technology, Vol. 1,

pp. 140–145, February 2006.

[17] G. Smaragdakis, I. Matta, and A. Bestavros, “SEP: A

stable election protocol for clustered heterogenous wire-

less sensor networks,” The 8th International Conference

on Advanced Communication Technology, 2004.

[18] S. Ghiasi, A. Srivastava, X. Yang, and M. Sarrafzadeh,

“Optimal energy aware clustering in sensor networks,”

Sensors, Vol. 2, pp. 258–269, July 2002.

[19] U. P. Han, S. E. Park, S. N. Kim, and Y. J. Chung, “An

enhanced cluster based routing algorithm for wireless

sensor networks,” International Conference on Parallel

and Distributed Processing Techniques and Applications,

Vol. 1, June 2006.

[20] Y. Chen and N. Nasser. “Energy-balancing multipath

routing protocol for wireless sensor networks,” Proceed-

ings of the 3rd International Conference on Quality of

Service in Heterogeneous Wired/Wireless Networks, Vol.

191, 2006.

[21] L. Lin, N. B. Shroff, and R. Srikant, “Energy-aware rout-

ing in sensor networks: A large systems approach,”

WONS 2006: Third Annual Conference on Wireless

On-demand Network Systems and Services, pp. 159–169,

January 2006.

[22] R. C. Shah and J. Rabaey, “Energy aware routing for low

energy ad hoc sensor networks,” WCNC 2002 Confer-

ence, March 2002.

[23] V. Raghunathan et al., “Energy aware wireless mi-

crosensor networks,” IEEE Signal Processing Magazine,

Vol. 1, No. 2, pp. 40–50, March 2002.

[24] A. Vargas, OMNeT++ Discrete Event Simulator System,

version 2.3 edition, 2003.