Energy Efficiency in Wireless Sensor Networks
Except where reference is made to the work of others, the work described in this thesis is
my own or was done in collaboration with my advisory committee. This thesis does not
include proprietary or classifled information.
Pratap Simha Prasad
Certiflcate of Approval:
Sadasiva M. Rao
Professor
Electrical and Computer Engineering
Prathima Agrawal, Chair
Samuel Ginn Distinguished Professor
Electrical and Computer Engineering
Ramesh Ramadoss
Assistant Professor
Electrical and Computer Engineering
George T. Flowers
Interim Dean
Graduate School
Energy Efficiency in Wireless Sensor Networks
Pratap Simha Prasad
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
May 10, 2007
Energy Efficiency in Wireless Sensor Networks
Pratap Simha Prasad
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Pratap Simha Prasad, son of Sri. C. S. Prasad and Smt. Nagamani Prasad was born in
Bangalore, India on 11th October, 1981. He completed Pre-University education from Vi-
jaya High School and National College, Bangalore in May 1997 and May 1999 respectively.
He graduated from Visvesvaraya Technological University?s P.E.S Institute of Technology,
Bangalore with a Bachelor of Engineering degree in Electronics and Communications En-
gineering in 2003. He began his graduate studies in Electrical and Computer Engineering
at Auburn University in August 2004.
iv
Thesis Abstract
Energy Efficiency in Wireless Sensor Networks
Pratap Simha Prasad
Master of Science, May 10, 2007
(B.E., Visvesvaraya Technological University, India 2003)
66 Typed Pages
Directed by Professor Prathima Agrawal
Wireless Sensor Networks are an emerging area of Communication technology. These
networks are made up of tiny wireless sensors that collect and transmit data toward a sink
node(s). Energy e?ciency in sensor networks is one of the most important considerations
in network design. This is because of the low energy resources that can be supplied with
these sensor nodes.
In this work, we describe methods to increase the lifetime of sensor networks using a
hybrid routing scheme. Our routing scheme uses a probabilistic method of routing to trans-
mit data from the sensor nodes to a sink. This scheme incorporates link usage probabilities
and energy metrics to prevent failure of nodes due to their excessive usage. In addition, it
also incorporates angular routing which forwards packets only to neighboring sensor nodes
in assigned conical regions to prevent unnecessarily lengthy routes. Our scheme bounds
routing delays in a predetermined manner to ensure that time critical data is not rendered
obsolete.
There are regions of sensor networks that are more vulnerable to outages, called
hotspots. We also propose a difierential method of deployment of sensor nodes to prevent
v
network partitions around hotspots. This scheme ensures that there are no local outages
that might create a network partition thereby isolating pockets of nodes from transmitting
their data seamlessly to a central processor.
In summary, we demonstrate improved performance in comparison with other schemes.
We also show that our scheme is more successful in delaying network partitions and in
enhancing the lifetime of the network.
vi
Acknowledgments
It is a pleasure to acknowledge help and extend thanks to so many people who helped
me during my Master?s degree program at Auburn University. First and foremost, it is my
humble duty to convey my hearty thanks to my advisor Professor Prathima Agrawal. She
has provided me with full freedom to identify research problems, sound advice and ideas
to solve them and motivation to lead this project to fruition. Moreover, she has inculcated
objective thinking and the drive to pursue research problems. For these and a lot more, I
am forever indebted to her.
I also wish to thank Professors Sadasiva M. Rao and Ramesh Ramadoss for graciously
accepting to be on my advisory committee. My thanks also go out to my colleagues in
the Wireless Research Laboratory at Broun Hall. In particular, I wish to thank Santosh
Pandey, RaviParuchuri, SowmiaDevi, PriyankaSinhaand Dr. Shaoqiang Dong for valuable
suggestions and discussions that we have had during my stay here.
Many friends at Auburn and elsewhere have contributed to shaping my thoughts and
provided moral support when I most needed it. Also, several other friends and relatives
have ensured that I never felt homesick. I gratefully thank them all for their time and
caring thoughts. I also thank my younger brother for his genuine love.
Finally, I am grateful for the tremendous sacriflces that my parents have made to ensure
that I had an excellent education. They have inspired me, instilled values, supported me in
all my ventures and made me what I am today. For this and much more, I am forever in
their debt. It is to them that I humbly dedicate this thesis.
vii
Style manual or journal used Journal of Approximation Theory (together with the style
known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally LATEX)
together with the departmental style-flle aums.sty.
viii
Table of Contents
List of Figures xi
1 Introduction 1
1.1 Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Applications of Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Military Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Environmental Applications . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.3 Domestic Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4 Other Commercial Applications . . . . . . . . . . . . . . . . . . . . . 11
2 Challenges associated with Sensor Networks 13
2.1 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Environmental Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Energy Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Topology and Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1 Network Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Sensor Network Routing 17
3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1 Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.2 Data Centric Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.3 Hierarchical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.4 Energy Aware Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Sensor Network Model 23
4.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Problem Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 Routing Framework and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4.1 Probabilistic Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4.2 Angular Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Simulation and Results 33
5.1 Simulation study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3 Difierential Sensor Node Deployment . . . . . . . . . . . . . . . . . . . . . . 40
ix
6 Conclusion 47
7 Proposed Future Work 49
Bibliography 51
x
List of Figures
1.1 A sensor node in comparison with a penny . . . . . . . . . . . . . . . . . . . 3
1.2 Some popular commercially available commercial sensor nodes . . . . . . . 3
1.3 A Crossbow sensor mote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Schematic Representation of a Sensor Field . . . . . . . . . . . . . . . . . . 6
1.5 Representation of a sensor network interacting with a real world network . 6
4.1 Variation of connectivity with density of the network . . . . . . . . . . . . . 24
4.2 Conical sector routing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Angular routing with sector angle  . . . . . . . . . . . . . . . . . . . . . . . 31
5.1 Visualization of key network parameters . . . . . . . . . . . . . . . . . . . . 34
5.2 Sample topology used in the simulation . . . . . . . . . . . . . . . . . . . . 36
5.3 Variation of Delay with cone angle. . . . . . . . . . . . . . . . . . . . . . . . 38
5.4 Variation of hopcount with and without angular routing. . . . . . . . . . . . 38
5.5 Energy proflle of the grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.6 Averaged energy proflle of the grid for routing model proposed by Shah and
Rabaey [45]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.7 Averaged energy proflle of the grid of sensor nodes. . . . . . . . . . . . . . . 41
5.8 Efiect of spatial node distribution on node failures . . . . . . . . . . . . . . . . . 43
5.9 Histogram of tra?c distribution on the nodes . . . . . . . . . . . . . . . . . . . 43
5.10 Energy Proflle of the nodes using gradient deployment . . . . . . . . . . . . . . . 44
5.11 A snapshot of average energy over time . . . . . . . . . . . . . . . . . . . . . . 45
xi
Chapter 1
Introduction
The networking revolution has grown from an ARPA project connecting isolated com-
puters on difierent university campuses in the early 70s to the world wide web today. Along
with the rapid advances in networking of computers, Moore?s law has held true all the
while helping the proliferation of faster and smaller chips in many electronic and networked
devices. Wireless networking has been a revolution in the network world since the early
90s and has exploited advances in several areas such as communications, VLSI (Very Large
Scale Integrated circuits), networking and software.
Mobile ad hoc networks(MANETs) are a class of wireless networks in which the network
componentsare able to communicate with eachwithout pre conflgured infrastructure. These
components can form separate groups, auto-conflgure themselves and communicate on-the-
 y with other devices. Some network interfaces may be cellular, some may be connected to
the wired network and others through a wireless medium.
MANETs have come to be known as multi-hop networks. This is because the network
components (referred to as nodes) not only function as source and destination, but also
help in forwarding packets destined to other nodes. Hence they participate in relaying
the information to the destination across multiple hops. Hence, even when the source and
destination are out of each others? range, they can communicate with each other through
the participation of other intermediate nodes.
Coupled with sensor technology on these chips and their shrinking sizes, it is now
possible to design chips capable of sensing and computing information on these tiny chipsets.
1
Figure 1.1 shows how small the sizes of commercial sensors are shrinking with the advent
of technology. Such tiny low power devices are possible only due to the VLSI chip design
technologies. Figure 1.2 shows a variety of sensor nodes as developed by other academic
universities and research labs for speciflc purposes.
For research and developmental purpose most researchers use sensor motes. A mote is
a term used to describe a wireless sensor device which is a basic component in a wireless
sensor network. Each such mote consists of a cpu, radio interface and sensor development
board. It can form an ad hoc network with neighboring nodes. Because of the size of these
nodes, they are also referred to as smart dust. One such developmental sensor mote is
shown in Figure 1.3. Some of the prominent manufacturers of sensor motes are Crossbow
Technology, Mica Mote, Sensi Net, etc.
The next revolution in the wireless networking world is sensor networks. Combining
sensor devices with networking, it is now possible to network a number of these low cost
sensor chipsets into a full  edged network. Capabilities of such networks include physical
sensing of information, some local computing and transmission of the same to a central
machine which is able to process and analyze such information. All this is possible in
devices that are just a few centimeters in dimensions.
Advances in this direction have been made possible because of a huge number of re-
searchers working in this fleld. There has been tremendous developments in the areas of
low power chip design, improved protocols for networking sensors, etc. However, sensor
networks are inherently difierent in a number of ways from traditional networks or even ad
hoc networks. Their data transmission rate, communication range and battery life are some
of the parameters that are considerably lower in comparison to traditional networks.
2
Figure 1.1: A sensor node in comparison with a penny
Figure 1.2: Some popular commercially available commercial sensor nodes
3
Figure 1.3: A Crossbow sensor mote
1.1 Sensor Networks
Deployment of sensor networks presents a wide range of advantages over traditional
networks. The obvious advantage of size and low cost apart, they can easily be deployed
in a wide variety of environments. They also provide many beneflts over other existing
schemes. Sensor nodes can be scattered in a given are and can sense the phenomenon and
transmit wirelessly. Another advantage is that with large-scale deployment, they can be
customized for various applications through hardware, software or a combination of both.
To efiectively use the sensed data, the sensor nodes transmit the sensed information to
one or more central processors, commonly referred to as sinks. For this, the sensors have to
act collaboratively and co-operatively to transmit information [13]. The sinks collect such
information from several sensors deployed in the fleld and collate the information, generate
results and analyze to aid further monitoring of the phenomena or to take action. This
4
whole process can be either centralized or distributed based on the network architecture
and the underlying protocol.
Sensor networks are quite difierent from ad hoc networks. Though they are both
autonomousnetworksandrequirenopre-conflguration, theyaresetapartbycertainfeatures
that make it hard to use the same techniques used for ad hoc networks. The number of nodes
in a sensor network may be several orders of magnitude more than that in an ad hoc network.
This makes non scalable protocols used for ad hoc networks unsuitable for sensor networks.
Energy resource is one other feature that distinguishes these two networks. Sensors usually
have a limited energy supply that are non rechargeable. However, ad hoc networks have
much better batteries that can periodically be replenished. Sensor networks are more data
centric, i.e., the focus is on nodes that have data satisfying certain conditions. Ad hoc
networks are address centric in the sense that identifying individual nodes is important in
delivering data.
A simple schematic diagram of a sensor network is shown in Figure 1.4.
Sensor networks can be connected to mainstream networks through the sink by mak-
ing it act as a gateway. This enables monitoring of even individual sensors from remote
locations. A representative diagram is shown in Figure 1.5.
Typically, wireless sensor nodes are deployed in thousands or hundreds of thousands.
They can be deployed right inside or very close to the physical phenomenon that they need
to sense. A larger number of sensor nodes usually provides greater accuracy, robustness,
longer lifetime and speed of communication.
5
Figure 1.4: Schematic Representation of a Sensor Field
Figure 1.5: Representation of a sensor network interacting with a real world network
6
As much as they come with all the advantages, sensor networks also pose a plethora of
problems. Sensornetworkscanusuallybescatteredrandomly. Hencethereisnoneedtopre-
engineer their positioning scheme. However, they now have the problem of discovering their
neighbors and conflguring themselves to communicate with them. Their self-conflguring
capabilities must be extremely efiective. Also, because of their large numbers, the protocols
used in sensor networks must be highly scalable.
Irrespective of whether there is only one sink or several along the network periphery,
the nodes closer to the sink expend comparatively more energy in relaying the information of
other nodes to the sink rather than transmitting their own sensed information. This causes
such nodes to fail more often due to energy depletion and might cause network discontinuity
near the sink. This leads to network partitions and can create separate networks incapable
of communicating with each other. In such a scenario, it may be infeasible to replace the
energy sources of the sensor nodes or even replace them individually. For example, a sensor
network deployed in the jungle for habitat monitoring [34] or perhaps monitoring an active
volcano [52] barely permits constant energy replenishment.
Hence, energy conservation plays a prominent role in sensor network management. One
energy saving tactic is to prevent the sensor nodes from transmitting information continu-
ously. It may transmit sporadically only after being triggered by a particular threshold of
the sensed phenomena or periodically based on a timer. This is not only to prevent rapid
depletion of energy but also to conserve the bandwidth of the network by transmitting
unnecessary duplicate packets. However, this might not always work since powering on a
sleeping node repeatedly and frequently may consume a rather large amount of energy.
7
Sensor networks also face a wide variety of other problems that are difierent from
wired, cellular, WLAN or ad hoc networks. This leads to new challenges in the network
layer due to problems such as extremely limited battery life, constantly changing topology
of the network, sheer size of the network, addressing problems etc. Moreover, there might
be unpredictable wireless conditions leading to higher packet error rates (PER) [23]. Also,
critical relaying nodes might fail causing network partitions. Movement of nodes might be
too frequent or the remaining nodes might not be able to reconflgure themselves efiectively
to transmit information.
One of the primary problems of sensor networks [26], as we discussed earlier, is lim-
ited energy resource. There are various paradigms for conserving energy to make a sensor
network last longer and within the upper bounds of the network lifetime [5]. Here, lifetime
may refer to extending the time duration till the flrst node fails or to prevent a network
partition. Energy e?cient techniques have been proposed in almost all layers such as phys-
ical, MAC [54] and network layers. One way of efiectively enhancing the collective lifetime
of a sensor network is to use energy e?cient routing protocols. There are several types
of routing protocols which emphasize difierent methods of routing [2] [3]. They are ge-
ographic routing [24] [55] [14] [40], power-aware routing [47] [32], directed difiusion [21],
data centric routing [27], semi-probabilistic routing for dynamic networks [10], probabilistic
routing [44] [4], etc. There are others that suggest mobile sinks as an alternative to prolong
the lifetime of these networks [33] [15]. Probabilistic routing [30] is one that focuses mainly
on network survivability [45].
8
1.2 Applications of Sensor Networks
Deployment of large-scale sensor networks in real life scenarios is now a reality with
several companies making customized sensors for practical applications. These large-scale
deployments consist of sensors capable of detecting intruders in secure areas or sensing phys-
ical phenomena such as temperature, chemical leaks, water contamination, environmental
conditions, radioactive leaks, pressure, etc. Often, manual deployment of sensor nodes is
infeasible.
Inpractice, theyareusuallyscatteredbyanaeroplaneandbasedonaparticularrandom
distribution. There are also other methods suggested [2] such as delivery by artillery shells
or using a robot to do the same. Such random deployment necessitates self-organization of
the nodes. Since the network is usually inaccessible, it has to be made robust to overcome
movement or failure of nodes.
Sensor networks are used for a wide variety of applications as mentioned above. Here,
let us look at a few real-life examples of wireless sensor networks.
1.2.1 Military Applications
Sensor networks were primarily envisioned to serve the military. They can be used in a
range of applications to help military personnel plan and flght wars better. Sensor networks
can be deployed in battleflelds to perform reconnaissance activities periodically. This will
help in monitoring movements and re-deploying troops. They can be used to monitor
NCBR (Nuclear, Chemical, Biological and Radioactive) attacks. This is very useful since
these physical conditions cannot be monitored in person. Also, these kind of applications
need to be planned much earlier, the network deployed and monitored from a far away place.
9
Such a scenario demonstrates an ideal use of sensor networks. Deploying sensors to sense
these phenomena will help in maintaining personnel safety. Some of the other proposed
applications in the military are in troop movements, battlefleld surveillance, equipment
status, etc.
1.2.2 Environmental Applications
This is an area of application of Wireless Sensor Networks that is extremely useful for
the community. Deploying sensor networks for monitoring environmental conditions can
help avert the community from coming in direct contact with natural disasters and other
environmental forces [19] [8] [16] [18] [48] [42].
An excellent example of an environmental application of a sensor network is RIVER-
SCOPE. This is a collaborative project by RPI and Columbia Universities. The project
has deployed sensors along the Hudson river to monitor aquatic conditions. An underwater
robot periodically traverses through the river to gather data from the sensors. This helps in
keeping track of pollutants, salination, chemical additives let loose by industries, etc. There
are several other environmental sensor network projects such as ALERT, COUGAR [53],
etc that focus on  ood detection.
Several other possible applications exist in monitoring humidity, weather stations, geo-
physical monitoring, forest flre detection, etc.
1.2.3 Domestic Applications
Domestic applications abound for wireless sensor networks. Applications are only lim-
ited by imagination in the fleld of domestic/home applications. Sensor nodes can be em-
bedded in various home appliances and networked to monitor them better [38] [19] [11].
10
They can be controlled from a central computer which can monitor their battery life, mal-
functioning, etc.
Another interesting application is in making smart homes through the use of sensors.
The sensors can be used in several devices and monitored over the internet. They can then
be remotely given instructions based on the sensed phenomena. Also, intruder detection
is a perfectly simple and feasible application involving just a few motion detection sensors.
This saves the cost of installing hi-tech security devices and paying a security company to
monitor those devices.
1.2.4 Other Commercial Applications
Commercial applications can exploit wireless sensor networks in many ways. Some
of the common commercial applications are in robotics, inventory control and warehouse
management, smart buildings, etc [1] [12] [22] [46] [51]. A very innovative usage is in
vehicular sensor networks. Sensor networks in vehicles are used to see tra?c congestion,
tra?c jams, etc on the web or on Global Positioning Systems (GPS). This helps other
travelers avoid tra?c jams, plan alternate routes, etc.
Large stores and warehouses can use sensors to keep track of shipments and inventories.
They can be coupled with the vehicular GPS devices to provide information to the central
warehouse. Also, large cities in the USA are now deploying vehicular sensor networks to
help manage tra?c better. Sensor nodes can be placed along the streets and highways
which can monitor tra?c conditions such as tra?c jams, accidents, etc, and inform vehicles
about alternative routes and delay times. This helps in decongesting and smoothing the
tra?c  ow.
11
There are several other workplace applications [9] that are in the pipeline in becoming
available commercially. Applications such as guiding guests in a new building through hand
held devices or cellphones, helping employees to flnd empty conference rooms, etc are all
practical applications that would be welcome in many large corporations. Such applications
which improve the lifestyle and lead to more organization would deflnitely be a welcome
improvement thanks to wireless sensor networks.
12
Chapter 2
Challenges associated with Sensor Networks
There are several challenges associated with sensor networks. Some of them are carried
over from the wired and wireless ancestors whereas a few others are acquired from their
characteristic difierences from them. Also, sensor networks are quite difierent from their
closest relatives, the MANET. One major problems associated with sensor networks is the
customization required for each network. They cannot be deployed out of the box. Each
application is difierent, the scale of operation, the management and the scenario totally
difierent from other projects. This leads to a lot of customization and may increase the cost
of the network.
In this section, we shall identify some of the challenges associated in the design of
sensor networks.
2.1 Scalability
Scalability is one of the biggest problems associated with sensor networks. A distin-
guishing feature of a sensor network is the large number of network components associated
with it. It is normally of the order of thousands or hundreds of thousands whereas MANETs
consist of about tens to maybe a few hundred elements. The density of nodes also may vary
depending on the application. It may be anywhere from a few nodes to a few hundred
sensor nodes within a region of about 10 m in diameter [7]. Also, network density is given
by [7] as
?(R) = N?R
2
A
13
where ?(R) is the number of nodes within the radio range R of each node in a region
of interest of area A; N gives the total number of nodes scattered in the region.
Managing such a large network requires scalable protocols and extremely well planned
deployment.
2.2 Deployment
Sensor nodes can be deployed in several ways. Due to the large number of nodes,
it is impractical to manually deploy them by hand. Hence some of the methods resorted
to are artillery shelling, scattering from an aeroplane, using a robot or in the worst case
deploying manually [2]. Most protocols assume some kind of random distribution. Hence
the deployment has to be in accord with such a distribution.
One advantage of such a deployment is that there is no necessity to plan for each node.
This reduces the installation cost tremendously. However, monitoring individual sensors is
very complex due to various factors such as size of network, accurate identiflcation of each
node, etc. The nodes themselves may be unreachable. In case of malfunctioning, it might
be very expensive to replace a very small subset of scattered nodes in difierent geographical
locations.
2.3 Environmental Conditions
Sensor nodes are typically deployed in regions with adverse climatic conditions. Un-
derground sensor networks, underwater networks, volcanic and habitat monitoring sensor
networks are some examples where they are tested to the extreme. In such scenarios, they
have to sense the phenomenon and transmit information. The problem is usually associated
14
with link quality and channel conditions. This might afiect the radio range of the nodes or
make them lose contact with immediate neighbors.
In busy commercial and workplace environments, they may face difierent problems
such as unintentional jamming and noisy environments.
2.4 Energy Resources
Sensor nodes are tiny and hence so are their energy reserves. Most sensor nodes use
tiny Lithium batteries. Hence they have to operate on low data rates and small radio
ranges. Moreover, sensor nodes deployed in adverse environments are in no way individually
replaceable or maintainable. This brings out a unique problem of managing whatever the
scarce energy it has in a very e?cient manner. They not only have to transmit their sensed
information but also have to participate in relaying the information of other nodes.
Hence energy conservation and prudent management is one of the major challenges in
sensor networks.
2.5 Topology and Connectivity
Sensor networks are usually deployed very densely so that coverage is not a problem.
Such a dense network will initially not have problems discovering neighbors, flnding con-
nectivity, etc. However, as some nodes start to fail, there might be pockets of sparsely
distributed nodes.
Wireless Sensor Networks can be analyzed theoretically by treating them as graphs [25].
The vertices can be treated as sensor nodes and the edges as links. The number of edges for
any given vertex is called the degree. There will be connectivity problems in areas where the
15
local degree is much lesser than the average degree of the graph. In such cases, connectivity
may be lost and potentially create network partitions. Connectivity also depends on the
distribution.
In sparse networks, it is obviously a much bigger problem.
2.5.1 Network Dynamics
Most scenarios of sensor networks consist of static nodes. However, there can be several
cases such as fauna monitoring or vehicle tracking which may involve highly dynamic nodes.
This creates a very mobile environment and hence a rapidly changing topology.
High mobility gives rise to a number of problems which cannot be handled by most
protocols. Hence network dynamics can dramatically degrade overall sensor network per-
formance.
16
Chapter 3
Sensor Network Routing
Routing in wireless sensor networks is quite difierent in many ways when compared
to that in MANETs. This is primarily because of the challenges faced by wireless sensor
networks as discussed in the previous section. The design of routing protocols for sensor
networks will depend on many factors such as scalability, node deployment, transmission
characteristics, delay tolerance, QoS, mobility, node heterogeneity, etc.
Coming up with e?cient protocols when dictated by so many parameters is very di?-
cult. One of the main objectives of a Wireless Sensor Network is to sense information and
communicate it. However, it should also simultaneously take care of prolonging the lifetime
of the network and reduce connectivity degradation by using excellent energy management.
There are various approaches to route packets based on the network characteristics.
These approaches may use local information such as geographic location, neighbor move-
ment or energy available in the nodes.
In the subsequent section, we investigate some of the approaches followed by various
protocols. We also provide a critical survey of such protocols to determine what is the main
feature lacking in a good sensor routing protocol.
3.1 Related Work
There are various paradigms in sensor network routing protocols. In this section, we
shall classify some of the well known sensor routing protocols along with some of their
shortcomings.
17
As discussed earlier, one of the most pressing problems in sensor networks is the scarce
energy in the sensors. Hence, we emphasize the energy e?ciency features adopted by
previous methods.
3.1.1 Flooding
One of the simplest methods to disseminate information in sensor networks is to  ood
the network. Flooding is the process of forwarding of a packet from any node to every other
node attached to the router except the node from which the packet arrived. This is an easy
way to distribute routing information updates quickly to every node in a large network.
However, it is also sometimes used to forward multicast packets.
It is obvious that such  ooded information will reach every undesired corner of the
network thereby wasting energy. There are other variants of full scale  ooding such as
constrained [56] and directed  ood-routing [35] which reduce the overhead considerably.
Constrained  ooding uses techniques called difierential delay mechanism and probabilistic
retransmission policy. Using these techniques, it conserves energy by constraining retrans-
missions. Directed  ood-routing has a  ood routing engine that deflnes the routing policy.
These policies specify the direction of  ooding and how intermediate nodes rebroadcast
messages. Also, there are global and local broadcast messages that are used to disseminate
information to other nodes.
3.1.2 Data Centric Routing
One of the problems associated with sensor networks is that it is not practical to build a
global addressing scheme which can compare with the classical IP-based addressing scheme.
This is partly because of the sheer number of sensors deployed and also due to redundancy
18
in regional data. Hence the data aggregation concept [27] [31] is more e?cient in conserving
energy. This concept involves combining regional data to eliminate redundancy and reduce
the number of transmissions.
One of the flrst data centric routing protocols was SPIN [29]. This involves two fea-
tures called negotiation and resource-adaptation. Negotiation involves a data advertisement
scheme wherein sensors exchange descriptors called meta-data before transmission. Energy
adaptation is controlled by the nodes when they are polled using a resource manager. This
helps the nodes in deciding whether to participate in relaying third party information when
battery resources are at a premium. These two features help in making it a better option
than  ooding.
Another important milestone in data centric routing was directed difiusion [21]. All
data generated by the nodes is named by attribute-value pairs. For example, temperature
and humidity may be two attributes in an environmental sensor. The values will be stored
corresponding for the corresponding attribute. Hence the sink queries the nodes on an on-
demand basis. The querying is done using attribute-value pairs. From a list of attribute-
value pairs, a query (called interest) is generated by the sink and propagated through its
neighbors. The neighbors cache these interests while forwarding them further. The source,
receiving the interest, replies using the best gradient. A gradient is the information about
the neighbor from which the interest was received. Hence, the source will be able to flnd
an empirically best-performing path. The advantage of directed difiusion is that it is based
on an on-demand model. This facilitates enormous saving of energy since there is no need
to keep track of node movements. But this method would probably not work in a sensor
networkwherethesinkwouldneedconstantfeedbackfromthesensorstofunctionefiectively.
19
Also, naming schemes for attribute-values are application dependent and occasionally each
sensor might spend a lot of energy querying its own cache.
There are also other protocols such as gossiping [49] that avoid the problem of implo-
sion. Implosion occurs when multiple copies of the same data reach a single destination
leading to wastage of energy. This also causes delays in the propagation of valid data
through the nodes. Rumor-routing [6] is a routing protocol which is a variant of directed
difiusion which is used where geographic routing is not feasible. However, rumor routing
performs well only when the quantity of sensed data is small.
3.1.3 Hierarchical Routing
One of the main network layer issues involved in sensor networks is scalability. This
might cause the sink and the nodes near the sink to be engulfed with too much of tra?c
to handle. Due to the large number of sensors involved, some researchers have devised
network clustering and then routing data through clusters to reach the sink. This creates
a multi-tiered network.
LEACH [17] was one of the earliest routing schemes to involve cluster formation and
many other routing protocols have been suggested based on this protocol. Some of the key
features of LEACH are mentioned here. Small clusters are formed locally and cluster heads
are elected in each cluster. Cluster heads are usually nodes with higher energy reserves.
However, to balance the load evenly, cluster heads are rotated randomly. Also, all local
data is compressed so as to reduce the number of packets.
In a cluster, the cluster head organizes all data aggregation and fusion. All transmis-
sions are done only by the cluster heads. It has been shown that LEACH [17] reduces
20
energy dissipation by a factor of about 7 compared to direct communication. Since cluster-
ing and election of cluster heads is dynamic, lifetime is increased and nodes die randomly.
However, all nodes in a cluster need to be within a single-hop away from the cluster head.
There might be overhead in electing a cluster head for certain sparse topologies which might
mitigate the positive efiects of adaptive clustering.
3.1.4 Energy Aware Routing
When energy conservation itself is the prime factor, the routing protocol has to be
designed with focus on using the available energy of the nodes and preserving it for as
long as possible. There are several protocols described in the literature where the main
emphasis is on preserving the energy level of the network [45] [43] [55]. Shah and Rabaey
propose a protocol [45] that concentrates on network survivability and tries to ensure that
connectivity is maintained in the network as long as possible. It does not select the shortest
path or a single path to route packets. Instead, it is a reactive protocol where each node
makes a local decision based on available local metrics and computed probabilistic values to
select a path. It is shown to provide a 44% increase in the lifetime of the network compared
to directed difiusion for certain conditions.
In [43], the authors propose an energy e?cient routing model to spread the tra?c.
This is done by a method called Gradient Based Routing where each node deflnes its height
based on its energy.
21
3.2 Organization of the Thesis
In this work, we concentrate on an energy e?cient packet routing technique for sensor
networks [28] [43] and compare it with some of the existing routing methods. The remainder
of this thesis is organized as follows. In Chapter 4, we propose a new probabilistic framework
for routing. Chapter 5 deals with a simulation study and analysis of results. Finally, in
Chapter 6, we provide a conclusion and propose some future work which could lead to
improvements over the proposed method.
22
Chapter 4
Sensor Network Model
In this section, we propose a sensor network model which forms the basis for the
simulation experiments performed. We brie y discuss some of the parameters that are
involved in addressing the problem and
We propose a probabilistic framework for routing in wireless sensor networks [39]. Our
method is based on [45] and is a considerable improvement over other proposals like [45]
and [43]. Our model shows improvement in delaying the time of failure of the flrst node
and also preserving more energy in the nodes near the sink.
The formation of hotspots in the network is caused by frequent routing through princi-
pally located nodes. Thus, an area in the proximity of a sink can be considered a hotspot.
The main objective of this model is to enhance network lifetime (i.e., increase the time to
the flrst node failure) as much as possible and also to mitigate the formation of hot-spots.
This is done by spreading the energy consumption amongst as many nodes as possible.
4.1 Connectivity
Firstly, we discuss connectivity properties in the sensor network. We have to make sure
that the sensor nodes in the network are connected with every other node. The notion of
connectivity is explained as follows. If two sensor nodes are within each other?s radio ranges,
they are directly connected and can be called one-hop neighbors. If they are not within
each other?s radio ranges, then they can communicate with each other only by relaying
information through other nodes that are their one-hop neighbors. These neighbors further
23
Figure 4.1: Variation of connectivity with density of the network
relay the information to their neighbors and flnally reaches the destination over a path.
It may so happen that for a particular distribution, there may be some nodes which are
unreachablefromanyothernode. Theyaresaidtobetotallydisconnectedfromthenetwork.
If a node is connected to all other nodes in the network, we can say that the entire network
is connected.
Connectivity also depends on the radio range and sparsity or density of nodes in the
network. For a sparse network, the radio range has to be long to establish connectivity. For
a dense network, it su?ces to have a short radio range to keep the network connected. As
we increase the number of nodes, the connectivity also increases [36]. This is evident from
the Figure 4.1 [36].
24
Based on the model used for connectivity in Figure 4.1, we decide on the number of
nodes to be deployed in a planar region. Also, the radio range of the nodes are set to a value
so as to get maximum connectivity in the network. It is better to deploy more nodes than
to increase the radio range of the sensor nodes. Hence we cover the network by deploying
additional sensors and decreasing the radio range.
To demonstrate connectivity, consider N sensor nodes deployed in a plane. We can
model this as an undirected planar graph G = (V;E). Here V denotes the set of vertices
(nodes) and E the set of edges (radio links) between the nodes. An edge E exists between
two nodes if the nodes are within each other?s radio ranges and can directly communicate
with each other.
Let the N nodes be in a region S of area As square units. Also, we suppose that the
nodes are uniformly distributed over the planar region. To quantify connectivity, we deflne
Pc as the probability that a node is connected to n nodes where n ? N ?1.
It can be shown that there is a lower bound on Pc given by [50]
Pc > 1?(1?a)n?1 ?
n?1X
k=1
?
n?1
k
!
(1?x)n?1?k(r
2
As)
k
k?1Y
j=0
(? +2j)
where x = ?r
2
2As
This probability corroborates with the Figure 4.1 and ensures desired connectivity for
a given number of nodes and a given area of deployment.
4.2 Problem Motivation
In a network of sensor nodes, the sensors produce data that has to be disseminated
towards the sink. The data may be time sensitive and hence there may be a maximum
25
tolerable delay of tmax. For a particular source S and destination d, we may assume that
there are a total of P paths that exist in the network graph. Let us also assume that Ei
and ti denote the energy consumed and time taken along a particular path Pi 2 P.
To obtain a path P0 such that
P0 2 P and E0 < Ej8Pj 2 Pc
where Pc = PijPi 2 Pandti < tmax
This problem of flnding such a path Pi belongs to a class of constrained optimization
problems. Hence it is NP-complete and we can only flnd heuristic solutions to obtain the
solution for this problem.
One way of flnding heuristic solutions to the above mentioned problem is to use prob-
abilistic routing methods. This is explained in detail later.
4.3 Assumptions
In our study, we make a few assumption in the description of the sensor network. The
assumption are listed below.
1. All nodes are assumed to be stationary and links with their neighbors are assumed
to be bidirectional. The only unidirectional links belong to those nodes which are
connected to the sink. There is no interfering tra?c involved.
2. Nodes are deployed for sensing and transmission of information. They are homoge-
neous, i.e., they have the same capabilities and functions. They all cooperatively route
the information to the sink.
26
3. Every node maintains a table which stores information required for routing. This
table contains the node?s location information, energy level, number of hops to a sink,
one-hop neighbors, their locations, energy levels and their distance from the sink. The
neighbors exchange energy level information through infrequent hello messages.
4. Based on this information, every node assigns routing link probabilities to each of its
neighbors. This probability metric deflnes the possibility of a packet being forwarded
through a particular neighbor. These probabilities are based on the energy level of
neighboring nodes, their recent activity and distance from the sink. This will be
discussed in more detail in the next section.
In our simulation study, except for the energy levels, most of the information is dis-
seminated one-time only during the start of the simulation.
4.4 Routing Framework and Analysis
This section discusses the theory behind the routing framework. We discuss two meth-
ods called Probabilistic Routing and Angular Routing which are combined together to
improve energy e?ciency in the network.
4.4.1 Probabilistic Routing
Let us assume that nodes y1;y2;:::;yn are the n one-hop neighbors of x. The routing
table of node x will have an entry px(yi) for every neighbor yi where i 2 1;2;:::;n and
denotes the probability of taking that link to reach a destination z. Hence, px(yi) indicates
the probability of a packet being forwarded from node x to a neighboring node yi.
It also follows that
27
px(yi) ? 0
Pn
i=1 px(yi) = 1
All nodes can access their energy levels e at any instant. Initially, every node computes
the distances dyi and gets to know of the energy levels eyi where i 2 1;2;:::;n of all its n
neighboring nodes through hello messages. They also advertise their distance from the
sink in hops as hyi. Such information is stored as a vector in the form:
< yi;eyi;dyi;hyi;eav;hxz(yi) >.
Each node has a hop count to the sink hyi that is calculated during the initial phase.
Since we have assumed that the network is stationary, the hop count computed once will
remain the same throughout the lifetime of the network unless intermediate nodes die. This
metric is useful because if a node?s neighbor has a smaller hop count number, then that
node is closer to the sink. Hence, it should be assigned a higher probability for forwarding
the packet. In other words, the probability should be proportional to the weight determined
by the hop count. Thus, a neighboring node, which is closer to the sink, relays a packet
with a higher probability.
The average energy of a node eav denotes the average of the energy levels of its neigh-
boring nodes including itself. Ordinarily, eav is used for all calculations. However, it may
so happen that a node and one of its neighbors have quite ample reserves of energy but its
average energy is very less. If eav ? 0:5eyj, then eyj is used for the calculation.
hxz(y) is initially not present but it is updated through feedback from the other nodes
dynamically. This fleld denotes the distance in hop count from node x to z via the neigh-
boring node y. This metric is not always used to compute the probability values since it
28
converges only after sometime. However, if hxz(y) is comparable to the hop count of another
neighboring node and also has comparatively the same energy, then it is used as a metric
for computation.
The objective is to forward a packet to a neighbor with the maximum average energy
and least hop count. This neighbor will have the maximum probability of receiving the
packet. Also, the probabilities have to be recomputed after a certain number of transmis-
sions so as to re ect the state of the node?s and its neighbors? energy status.
We now compute the probability of forwarding a packet to a node as:
pxz(yi) = eavyihyinX
i=1
eavyihyi
This gives the probability of routing a packet to an adjacent node.
4.4.2 Angular Routing
Whenthenetworkisdeployed, thesensorsconflgureanddiscovertheirneighbors. Thus,
every node knows its position relative to the sink. It also knows its neighbors? positions.
Using this information, we propose to route data with minimum number of hops. Hence,
we introduce another parameter to the routing procedure called the angle of routing.
If routing is based only on probability, the packet might take a lengthy path if the
energy metric outweighs the hop count metric. To prevent this, sector based routing as
shown in Figure 4.2 helps in keeping the paths comparable to the shortest path. This
procedure is explained below.
When nodes determine their localization information [37], they also exchange this in-
formation with their immediate neighbors. There is no necessity to have absolute location
29
Figure 4.2: Conical sector routing.
information. This gives a relative location of a node with reference to its neighbors. We
can use this localization information to direct packets towards the intended destination and
reduce latency and energy consumption to some extent. In this work, since we assume
that the destination is always flxed, all nodes have direction information about the sink.
Initially, when a node has a packet to forward, it starts ofi by scanning only those neighbors
within a  ? cone directed towards the sink. Hence the fleld of interest is reduced and the
other neighboring nodes do not have to listen to the broadcast and expend their energy.
Now, amongst the nodes selected, it forwards the packet to the neighboring node with the
highest probability value. All the neighboring nodes which relay packets also update their
recent activity flelds. Hence, over a period of time, the probability values also change to
re ect the current energy levels of the nodes.
30
Figure 4.3: Angular routing with sector angle  .
The nodes that come under the coverage of this cone are determined as follows. For
the sake of analysis, this cone is approximated to a sector of a circle.
The sector is in the direction of the sink and the radio range r of the node is the radius
and the length of the arc s can easily be determined as follows. The two end points of s on
either sides of the center of the arc deflne the boundaries and the sensor nodes lying in this
region can be identifled for forwarding the packet.
s = r 
This can lead to a problem over time. As all the nodes towards the sink expend their
energy reserves, the probability of forwarding a packet to any of them remains same since
their energies are relative. However, when the battery level reaches the threshold, the source
has to flnd alternative routes to the sink. Let us suppose that a node has to relay a packet
and all its  ? cone neighbors have energy levels below a certain threshold. Then the sector
angle is increased to  +? so that there are more neighboring nodes that now come within
31
its coverage. So the probability of forwarding a packet to one of these new nodes is now
higher than the others. Hence, packets now flnd their way to the sink through other routes.
Summarizing, the routing model suggests spreading the packets across more nodes to
conserve energy. This is done using a probability metric computed using hop counts to
sink and average energy of the nodes. In addition, a sector for routing only to particular
neighboring nodes is deflned using  .
As we demonstrate in the next section, we achieve considerable improvement in the
conservation of energy and hence prevent the creation of hot-spots.
32
Chapter 5
Simulation and Results
In this section, we describe efiorts to validate the proposed routing model. We perform
a simulation study using realistic parameters to verify the claims that we have made for the
proposed framework. The details are explained below.
5.1 Simulation study
To assess the performance of the routing model proposed above, we perform a MAT-
LAB simulation study. Sensors are uniformly randomly deployed in a 100 X 100 grid as
shown in Figure 5.1. All sensors are assumed to be homogeneous, i.e., they are assumed to
have the same capabilities and functions. The deployment assumes that there is a high con-
nectivity initially when deployed. Also, the sensors have to conflgure themselves, undergo
localization and discover their neighbors. We assume that there is only one centralized sink
with unlimited processing power and resources at the right edge of the grid. This is more
practical than assuming a sink somewhere in the center which would be infeasible for most
scenarios.
We assume a dense deployment of sensor nodes and the average node degree of the
graph to be approximately 5. This facilitates high connectivity and thus permitting multiple
routes to the sink. For every simulation run, we choose a sensor node in the fleld randomly.
Then, we generate a packet to be routed to the sink using all the metrics proposed above
and evaluate the energy consumed for each run. There is no other tra?c in the network.
The resource manager for each node also updates the energy usage for that node if it is
33
0 10 20 30 40 50 60 70 80 90 1000
10
20
30
40
50
60
70
80
90
100 Visualization of Key Parameters of the Sensor Network
SINK 
Random  Source 
   Neighbors with weighted 
  probability to forward packet
 HOTSPOT 
Figure 5.1: Visualization of key network parameters
34
used in either packet generation or relaying packets. The energy spent for receiving and
transmitting a packet is assumed to be the same as that of Rabaey and Shah [45] which
is 25nJ/bit. Also, all energy calculations are only for the network layer and do not take
overheads of other layers into account.
Packets are numbered so that there is no looping and nodes do not receive the same
packet multiple times. For comparison of the proposed routing method, we analyze the per-
formance of the network for the routing protocol proposed in [45]. The packet transmitted
from a node to the sink keeps track of the delay and the hop count. To obtain a statis-
tical result, we run the simulation 100 times using difierent randomly generated network
topologies and random sources.
5.2 Results
A sample topology in Figure 5.2 shows an instant of the simulation when the nodes have
discovered their neighbors, formed links and updated their resource tables. Hence, location
estimation,  ooding, exchange of hello messages, etc. This connected graph shows that
there is a high degree of connectivity with each node being connected to many neighbors.
Packets are generated randomly and transmitted. As described earlier, energy and
probability metrics are updated regularly. As the energy of some of the nodes gets depleted,
the sector angle as shown in Figure 4.3 needs to change. This has repercussions in the delay
or the hop count. In such a case, the packets take longer paths to reach the sink for a
wider sector angle than for a narrower angle. This is because as the angle increases, more
candidate nodes are generated for packet forwarding. Hence, the packet might be routed
35
0 10 20 30 40 50 60 70 80 90 1000
10
20
30
40
50
60
70
80
90
100 Sample deployment of Sensor Nodes
Figure 5.2: Sample topology used in the simulation
36
through a node which has more energy but would be farther from the sink. As a compromise,
the maximum angle of the cone can be specifled to prevent the longer path delays.
The simulation study shows the variation of path delay with the angle of the cone in
Figure 5.3. As we observe, the sector angle has to be controlled to prevent the delay from
getting too long. We notice that there is no variation in the delay when the angle is varied
from 60? to 100?. This is probably due to the fact that when the angle is varied above
60?, the new candidate nodes would have almost the same hop count as the forwarding
node. Hence, the sector angle can be increased up to 100? to obtain best efiects of angular
routing. For a given sector angle  , we study the difierence in the number of hops for a
packet to reach the sink with and without angular routing. Figure 5.4 shows the difierence
in the average number of hops required for a packet to reach the sink. From the curves in
Figure 5.4, we observe that using angular routing along with probabilistic routing has quite
signiflcant beneflts. Though there is no major variation for shorter distances, we notice that
for longer distances there is some advantage in using angular routing.
After a hundred rounds of simulations with difierent network topologies each with 1000
packet transmissions, the collective energy results collated and analyzed. An energy proflle
of the sensor nodes is shown in Figure 5.5. The colormap is also shown to the side. A
region that has expended the maximum energy is shown in a reddish color and one with
least energy spent in blue. We observe from Figure 5.5 that the energy is spread out and
not many nodes die out in the routing process. In this flgure, the energy consumption has
been normalized.
As expected, there will deflnitely be more energy expended by the sensor nodes located
near the sink than elsewhere. This is because even though they are not responsible for
37
0 20 40 60 80 100 120 140 1601
1.5
2
2.5
3
3.5 Variation of Delay vs Cone angle
Cone angle in degrees
Normalized delay 
Figure 5.3: Variation of Delay with cone angle.
2 3 4 5 6 7 8 9 101
2
3
4
5
6
7
8
Distance from the sink
Number of hops to reach the sink
Effect of angular routing on the hop count
Without angular routingWith angular routing
Figure 5.4: Variation of hopcount with and without angular routing.
38
Energy profile of Sensor Nodes
5
10
15
20
Figure 5.5: Energy proflle of the grid .
39
generating packets, they are almost always relaying some other node?s packets to the sink.
However, it can be observed from Figure 5.5 that the formation of hot-spots near the sink
is extremely slow. Hence the sensor nodes have conserved some amount of energy.
To demonstrate the robustness of our model, we compare our results with the one
proposed by Rabaey and Shah [45]. We have simulated the energy aware routing protocol
using the same network parameters. Then, we have averaged out the fleld of sensor nodes
into a 10X10 grid. The energy proflles are shown in the Figure 5.6 and Figure 5.7. Though
the energy plots look almost the same, we can calculate that there is an improvement in
the conservation of average energy. We have obtained the difierence in the energy values
in the corresponding grids of the two flgures. If we assume that the 25 grids near the sink
as hot-spots, then we can show 11% e?ciency of our routing model in distributing energy
across the sensor nodes.
There is still potential cause of failure in the future since the nodes which are very close
to the sink have depleted most of their stored energy. Their participation in the relaying
process is extensively greater than other nodes.
To overcome some of the problems mentioned above, we suggest a difierential deploy-
ment of sensor nodes. The details are explained in the subsequent section.
5.3 Difierential Sensor Node Deployment
There are many ways in which we can conserve energy of the sensor nodes situated
in hotspots. These include replacing or replenishing such nodes frequently, moving those
nodes so that they exchange their locations with nodes that haveexpended less energy [41] or
deploying more nodes in such regions to ofiset the tra?c load. As we have already described,
40
1 2
3 4
5 6
7 8
9 10
1 2
3 4
5 6
7 8
910
0
5
10
15
20
25
Averaged grid energy for probabilistic model(Shah and Rabaey)
Figure 5.6: Averaged energy proflle of the grid for routing model proposed by Shah and
Rabaey [45].
1 2 3
4 5 6
7 8 9
10
1 2
3 4
5 6
7 8
910
0
5
10
15
20
25
Averaged grid energy profile for routing model
Figure 5.7: Averaged energy proflle of the grid of sensor nodes.
41
it might not be feasible to recharge or replace nodes after deployment. Also, mobile nodes
swapping their places might involve high end motes which have guided mobility and larger
energy reserves. There has been some work in this area [20] on the efiect of node density on
data aggregation in sensor networks. Hence in this experiment, we have tried to demonstrate
the efiectiveness of the last option - i.e., deploying more nodes in such regions to see their
efiect on longevity of the network.
We do not consider the logistics of deploying a larger sample in hotspot regions. We
shall assume that such a task is achievable and concentrate on performance analysis. We
propose deployment of sensor nodes with difiering densities in regions of extensive network
usage. These difierential deployments are made using a certain probability distribution.
Since the purpose of deployment with difierent ? values is to aid the distribution of energy
and hence prevent failure of nodes, we study how the variation of the mean will in uence
the hotspots. Figure 5.8 shows the sensor node failure rates for difierent distributions. We
observe that for a particular distribution, the failure of nodes in the hotspot is particularly
low. This depends on the routing protocol and the metrics used in the network such as the
threshold eav.
The whole purpose of using a gradient distribution is to spread the tra?c load as
uniformly as possible among nodes. We demonstrate this through a histogram in Figure
5.9. The histogram shows the distribution of data tra?c on the nodes. We notice that this
sensor node distribution coupled with the angular routing technique is quite successful in
uniformly distributing the tra?c. This, in fact, substantiates the energy proflle of Figure
5.10 where we notice that most of the nodes in the hotspot have participated equally in
the routing process. Though we still observe a few peaks in the histogram, these are not
42
0 100 200 300 400 500 600 700 8000
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Elapsed Time
Number of Failed nodes (Normalized)
mumu1
mu2
Figure 5.8: Efiect of spatial node distribution on node failures
0 500 1000 1500 2000 25000
5
10
15
20
25
30
35
40
Load (Number of Packets)
Number of nodes
Figure 5.9: Histogram of tra?c distribution on the nodes
43
Energy profile of Sensor Nodes with gradient deployment
2
4
6
8
10
12
14
16
18
20
22
Figure 5.10: Energy Proflle of the nodes using gradient deployment
44
0 100 200 300 400 500 600 700 8002
3
4
5
6
7
8
9
10
11
12
Elapsed time
Average energy of various distributions (Normalized)
mu3mu2
mu1
Figure 5.11: A snapshot of average energy over time
critical. This demonstrates that a majority of the nodes handle small to medium number
of packets.
We also perform other studies from the simulation. Figure 5.11 shows the variation of
average energy in the hotspot region over time. As we see, there is a noticeable difierence in
the energies consumed over time. The distribution with ?3 corresponds to the least energy
consumption and ?1 to the highest among the three. It can be shown that the theoretical
bound on the maximum energy consumed is closest to the curve corresponding to ?3. From
this flgure, we conclude that difierence in spatial distributions deflnitely in uences the
formation of hotspots and reduces failed nodes. Hence, flnding the ideal distribution for
any scenario will increase the lifetime of the network.
We can infer from Figure 5.11 that the energy consumption depends on the distribution
of the nodes. Also, the gradient in deployment used to overprovision the network plays a
45
signiflcant role in preventing network partitions in the hotspots. Though initial energy
consumption in the hotspot is almost the same for all distributions, we can see a notable
difierence during the later stages of the simulation.
46
Chapter 6
Conclusion
In this work, we set out to improve the energy e?ciency of wireless sensor networks.
We approached this problem through e?cient routing methods.
We have proposed a routing framework for wireless sensor networks for avoiding the
formation of hot-spots of energy depletion. This routing framework incorporates assigning
probabilities to the links to neighboring sensor nodes.
To incorporate the changing energy proflle of the network, we re-evaluate the network
parameters frequently. We have used the idea of changing routes over time depending on
the probability. This is based on computing probability with parameters such as remaining
energy of the sensor nodes, recent activity, etc.
To prevent increased latency and extremely long routes, we bring in the idea of angular
routing. This prevents taking paths that are in the opposite direction from the sink and
thereby elongating routes. We have also demonstrated via simulations that probabilistic
routing using energy and angular metrics can increase the lifetime of the network. There is
also evidence of this fact by the reduction of hot-spots.
It is true that to extend the lifetime of the network, we have employed data forwarding
through suboptimal paths. Viewed in isolation, these look bad since they not only increase
the latency for the packet but also increase the average energy consumed for a packet.
However, if we look at the big picture, we have been successful in spreading the energy
consumption over a larger area thereby reducing node failures.
47
In spite of these methods to tackle the problem of hot-spots in networks, there is still
increased activity in regions near the sink. To overcome the energy depleting efiects, we
also propose a method to difierentially deploy more nodes in such regions. This will spread
the tra?c in such regions and extend the life of such networks.
Probabilistic angular routing method may not be optimal for all network topologies.
Topological changes induced by mobility might have difierent efiects on the energy proflles
and network lifetime.
48
Chapter 7
Proposed Future Work
The proposed framework has been validated by extensive simulations using MATLAB.
The parameters used are quite realistic and map closely to real time scenarios. In future, we
propose to use real sensor nodes and program them with this routing framework. This will
help take into consideration many other factors that had been previously neglected. A real
emulation using sensor motes would involve cases of channel fading, co-channel interference,
congestion, hidden terminal problems, environmental in uences on the sensor nodes, etc.
This would also bring out some of the deflciencies of the packet format used, the need for
efiective data aggregation, cluster formation, heterogeneous sensors, etc. Also, in future,
we propose to extend this work with a network simulator that tries to take care of at least
a few of these parameters. All this would substantiate the efiectiveness of the proposed
methods ever better.
We have proposed a routing framework that tries to elongate the lifetime of wireless
sensor networks. However, it is not without some minor loopholes.
Probabilistic angular routing method may not be the most optimal routing framework
for all kinds of network topologies. Moreover, topological changes induced by mobility
might have difierent efiects on the energy proflles and network lifetime. As future work,
we propose to extend this work to incorporate the efiect of node densities throughout the
network. The objective of such architectures is to deploy nodes according to the energy
usage proflles in the network. We also propose to investigate this in comparison with other
49
network architectures such as multi-tier (clustered) networks, data aggregation models, etc
which represent a paradigm difierence in architecture.
In this work, we have considered a stationary sensor network and a stationary sink.
In future, we propose to investigate mobility in the network and also mobility of the sink.
This might be a realistic scenario in some specialized applications.
50
Bibliography
[1] J. Agre and L. Clare. An integrated architecture for cooperative sensing networks.
IEEE Computer Magazine, May 2000, pp 106108, 2000.
[2] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor
networks. IEEE Commun. Mag. 40 (8), pages 102{114, 2002.
[3] J.N. Al-Karaki and A.E. Kamal. Routing techniques in wireless sensor networks: a
survey. Wireless Communications, IEEE [see also IEEE Personal Communications],
11, 2004.
[4] Christopher L. Barrett, Stephan J. Eidenbenz, Lukas Kroc, Madhav Marathe, and
James P Smith. Parametric probabilistic sensor network routing. Wireless sensor
networks and applications, 2003.
[5] M. Bhardwaj, A. Chandrakasan, and T. Garnett. Upper bounds on the lifetime of
sensor networks. In IEEE International Conference on Communications, pages 785 {
790, 2001.
[6] D. Braginsky and D. Estrin. Rumor routing algorithm for sensor networks. In Inter-
national Conference on Distributed Computing Systems, ICDCS-22., 2002.
[7] Nirupama Bulusu, Deborah Estrin, Lewis Girod, and John Heidemann. Scalable coor-
dination for wireless sensor networks: Self-conguring localization systems. In Interna-
tional Symposium on Communication Theory and Applications (ISCTA), July 2001.,
2001.
[8] A. Cerpa, J. Elson, M. Hamilton, and J. Zhao. Habitat monitoring: application driver
for wireless communications technology. In ACM SIGCOMM2000, Costa Rica, 2000.
[9] W. Steven Conner, John Heidemann, Lakshman Krishnamurthy, Xi Wang, and Mark
Yarvis. Workplace applications of sensor networks. Technical Report ISI-TR-2004-591,
USC/Information Sciences Institute, July 2004.
[10] Paolo Costa and Gian Pietro Picco. Semi-probabilistic routing for highly dynamic
networks. In F. Davoli, S. Palazzo, and S. Zappatore, editors, Distributed Cooperative
Laboratories: Networking, Instrumentation, and Measurements. Springer, December
2005.
[11] I.A. Essa. Ubiquitous sensing for smart and aware environments. IEEE Personal
Communications, (October 2000) pp 47-49., 2000.
51
[12] D. Estrin, R. Govindan, and J. Heidemann. Embedding the internet. Communication
ACM 43, pp 38-41, 2000.
[13] D Estrin, R Govindan, J Heidemann, and S Kumar. Next century challenges: scalable
coordination in sensor networks. Proceedings of the 5th annual ACM/IEEE interna-
tional on Mobile Computing and Networking, MobiCom?99, Seattle, WA, August, 1999.
[14] J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Geometric spanner for
routing in mobile networks. In Proc. of ACM MobiHoc01, pages 45{55, 2001.
[15] Matthias Grossglauser and David N. C. Tse. Mobility increases the capacity of ad-hoc
wireless networks. In INFOCOM, pages 1360{1369, 2001.
[16] B. Halweil. Study flnds modern farming is costly. World Watch 14 (1) (2001) 910,
2001.
[17] W. Rabiner Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-e?cient
communication protocol for wireless microsensor networks. In Proceedings of the 33rd
International Conference on System Sciences(HICSS ?00), January, 2002.
[18] W.R. Heinzelman, J. Kulik, and H. Balakrishnan. Adaptive protocols for information
dissemination in wireless sensor networks. In Proceedings of the ACM MobiCom99,
Seattle, Washington, pp. 174185., 1999.
[19] C. Herring and S. Kaplan. Component-based software systems for smart environments.
IEEE Personal Communications, (October 2000) pp 60-61., 2000.
[20] Chalermek Intanagonwiwat, Deborah Estrin, Ramesh Govindan, and John Heidemann.
Impact of network density on data aggregation in wireless sensor networks. In Inter-
national Conference on Distributed Computing Systems, 2002.
[21] Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin. Directed difiu-
sion: A scalable and robust communication paradigm for sensor networks. In Sixth
Annual International Conference on Mobile Computing and Networking (MobiCOM
?00), August 2000, Boston, MA.
[22] K.S.J. Pister J.M. Kahn, R.H. Katz. Next century challenges: mobile networking for
smart dust. In Proceedings of the ACM MobiCom99, Washington, USA, 1999.
[23] J.Zhao and R.Govindan. Understanding packet delivery performance in dense wireless
sensor networks. Proc. of ACM Sensys, pages 1{13, 2003.
[24] Brad Karp and H. T. Kung. Gpsr: greedy perimeter stateless routing for wireless
networks. In Mobile Computing and Networking, pages 243{254, 2000.
52
[25] H. Kawahigashi, Y. Terashima, N. Miyauchi, and T. Nakakawaji. Modeling ad hoc sen-
sor networks using random graph theory. In Second IEEE Consumer Communications
and Networking Conference, 2005.
[26] Bhaskar Krishnamachari. Networking Wireless Sensors. Cambridge University Press,
2005.
[27] Bhaskar Krishnamachari, Deborah Estrin, and Stephen Wicker. Modelling data-centric
routing in wireless sensor networks. In IEEE INFOCOM 2002, 2002.
[28] K.Seada, M.Zunida, and B.Krishnamachari. Energy-e?ciently forwarding strategies
for geographic routing in lossy wireless sensor networks. Proc. of ACM Sensys, pp
108-121, 2004.
[29] Joanna Kulik, Wendi Rabiner Heinzelman, and Hari Balakrishnan. Negotiation-based
protocols for disseminating information in wireless sensor networks. Wireless Networks,
8(2-3):169{185, 2002.
[30] Anders Lindgren, Avri Doria, and Olov Schelen. Probabilistic routing in intermittently
connected networks. Springer, 2004.
[31] Stephanie Lindsey, Cauligi Raghavendra, and Krishna Sivalingam. Data gathering in
sensor networks using the energy*delay metric. In Proc. of 15th International Parallel
and Distributed Processing Symposium, April 2001.
[32] L.Lin, N.B.Shrofi, and R.Srikant. Aymptotically optimal power aware routing for
multihop wireless networks with renewable energy sources. In Proc. of IEEE Infocom,
2005.
[33] J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser, and J.-P. Hubaux. Mobiroute:
Routing towards a mobile sink for improving lifetime in sensor networks. In Proc. of
the 2nd IEEE/ACM DCOSS, 2006.
[34] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson. Wireless sensor
networks for habitat monitoring. In WSNA?02, Atlanta, Georgia, September 2002.
[35] Miklos Maroti. Directed  ood-routing framework for wireless sensor networks. In Proc.
of the 5th ACM international conference on Middleware, 2004.
[36] Mohammad Naserian, Kemal Tepe, and Tarique Mohammed. On the connectivity of
nodes in wireless ad hoc and sensor networks. In 18th Annual Canadian Conference
on Electrical and Computer Engineering (CCECE?05), 2005, Saskatchewan, Canada.
[37] S. Pandey, P. Prasad, P. Sinha, and P. Agrawal. Localization of sensor networks con-
sidering energy accuracy tradeofis. In IEEE CollaborateCom, San Jose, CA, December
2005.
53
[38] E.M. Petriu, N.D. Georganas, D.C. Petriu, D. Makrakis, and V.Z. Groza. Sensor-based
information appliances. IEEE Instrumentation and Measurement Magazine, (December
2000) pp 3135., 2000.
[39] Pratap Prasad and Prathima Agrawal. Energy e?cient spatial distribution of nodes
in a sensor network. In IEEE Sarnofi Symposium, Princeton, NJ, May 2007.
[40] A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica. Geographic routing
without location information. In In Proc. of ACM MobiCom03, pages 96{108, Sept
2003.
[41] Jayanthi Rao and Subir Biswas. Controlled node mobility: A mechanism for energy
load distribution in sensor networks. In Proc. of the Globecom, 2006, 2006.
[42] RIVERSCOPE. Hudson riverscope pilot program.
http://xtide.ldeo.columbia.edu/hudson/.
[43] C. Schurgers and M. Srivastava. Energy e?cient routing in wireless sensor networks.
In Proc. of MILCOM 2001, 2001.
[44] Sergio D. Servetto and Guillermo Barrenechea. Constrained random walks on ran-
dom graphs: Routing algorithms for large scale wireless sensor networks. Interna-
tional Workshop on Wireless Sensor Networks and Applications, Atlanta, Georgia,
USA, 2002.
[45] R. Shah and J. Rabaey. Energy aware routing for low energy ad hoc sensor networks.
In In Proc. IEEE Wireless Communications and Networking Conference (WCNC),
Orlando, FL, March, 2002.
[46] E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan. Physical
layer driven protocol and algorithm design for energy-e?cient wireless sensor networks.
In Proceedings of the ACM MobiCom01, Rome, Italy, 2001.
[47] Suresh Singh, Mike Woo, and C. S. Raghavendra. Power-aware routing in mobile ad
hoc networks. In Mobile Computing and Networking, pages 181{190, 1998.
[48] S. Slijepcevic and M. Potkonjak. Power e?cient organization of wireless sensor net-
works. In IEEE International Conference on Communications ICC01, Helsinki, Fin-
land, June, 2001.
[49] S.M.Hedetniemi, S.T.Hedetniemi, and Liestman.A. A survey of gossiping and broad-
casting in communication networks. Networks, pages 319{349, 1988.
[50] Patrick Vincent, Murali Tummala, and John McEachen. Connectivity in sen-
sor networks. In Fortieth Annual Hawaii International Conference on System Sci-
ences(HICSS?07), 2007, Hawaii.
54
[51] B. Warneke, B. Liebowitz, and K.S.J. Pister. Smart dust: communicating with a
cubic-millimeter computer. IEEE Computer, January 2001, pp 2-9, 2001.
[52] Geofi Werner-Allen, Konrad Lorincz, Mario Ruiz, Omar Marcillo, Jefi Johnson,
Jonathan Lees, and Matt Welsh. Deploying a wireless sensor network on an active
volcano. IEEE Internet Computing, Special Issue on Data-Driven Applications in Sen-
sor Networks, March/April, 2006.
[53] Yong Yao and J. E. Gehrke. The cougar approach to in-network query processing in
sensor networks. In International Conference on Distributed Computing Systems, 2002.
[54] W. Ye, J. Heidemann, and D. Estrin. An energy-e?cient mac protocol for wireless
sensor networks. In An energy-e?cient MAC protocol for wireless sensor networks, in
INFOCOM 2002., 2002.
[55] Y. Yu, R. Govindan, and D. Estrin. Geographical and energy aware routing: A re-
cursive data dissemination protocol for wireless sensor networks. In UCLA Computer
Science Department Technical Report UCLA/CSD-TR-01-0023., May, 2001.
[56] Y. Zhang and M. P. J. Fromherz. Constrained  ooding: a robust and e?cient routing
framework for wireless sensor networks. In IEEE International Conference on Advanced
Information Networking and Applications, 2006.
55