tail :

.15..
é.

 

 

H...

 

 

B,- ’PJWJ:
£th a .. .

 

510317....- .1}

new

in

a.

.1‘

 

2.9.4. ,
a... fax.

‘21-: 3:59.:
24.1.} 1...?“ x
. Linn-V“ ,
..‘):~!.(I

w
. .
.. (b. iafihfi.
valetii :umWL 4
s.
.¥2.§:§
‘u'lt‘§l‘“fl! .
$.38:

 

1113533 LIBRARY
Michigan State
University x

This is to certify that the
dissertation entitled

OFF-NETWORK CONTROL PROCESSING FOR SCALABLE
ROUTING IN VERY LARGE SENSOR NETWORKS

presented by
Tao Wu

has been accepted towards fulfillment
of the requirements for the

PhD. degree in Electrical Engineerim

 

 

omitlixw.

Major Professor's Signature
:0 /e 0/0 a
l 7

Date

 

 

MSU is an Affirmative Action/Equal Opportunity Employer

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DAIEDUE

DAIEDUE

DAIEDUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5/08 K:lProj/Acc&Pres/ClRCIDateDueindd

 

OFF-NETWORK CONTROL PROCESSING FOR SCALABLE ROUTING IN
VERY LARGE SENSOR NETWORKS

By

Tao Wu

A DISSERTATION

Submitted to
Michigan State University
In partial fiilfillment of the requirements
For the degree of

DOCTOR OF PHILOSOPHY
Electrical Engineering

2008

ABSTRACT

OFF-NETWORK CONTROL PROCESSING FOR SCALABLE ROUTING IN
VERY LARGE SENSOR NETWORKS

By
Tao Wu

Although wireless sensor networks have demonstrated a promising future, there are
still a significant number of challenges to be overcome before they become reality. The
prime research issues involve fault tolerance, network scalability, cost, hardware design,
topology management, and power consumption. In this thesis we investigate two
problems concerning wireless sensor networks: (A) energy efficient medium access
control and (B) scalable routing architecture for very large wireless sensor networks.

Regarding problem A, we propose a Self Reorganizing Slot Allocation (SRSA)
mechanism for a TDMA-based medium access control (MAC) protocol in wireless
sensor networks. With SRSA, a node can achieve significant energy savings by
remaining active only during allocated slots for transmissions and receptions. In
multi-cluster networks, it is often necessary for nodes to use either CDMA or FDMA
for preventing TDMA slots across neighboring clusters from interfering with each other.
Using FDMA or CDMA incurs costs in terms of spectrum usage as well as hardware
complexity. Our goal is to provide an alternative design that can reduce inter-cluster
TDMA interference without having to use CDMA or FDMA. The primary contribution
of our work is to demonstrate that with adaptive slot allocation algorithms, it is possible
to minimize such interference under low traffic loading conditions. The second

contribution is to design a feedback-based adaptive allocation protocol that can

minimize those interferences without relying on any global synchronization
mechanisms. We present the design of SRSA and provide a detailed simulation-based
characterization of the protocol.

In the second problem, we motivate an architectural solution to address the problem
of scalable routing in very large sensor networks. The control complexities of the
existing sensor routing protocols, both node-centric and data-centric, do not scale well
for large networks with potentially hundreds of thousands of embedded sensor devices.
We develop a routing solution Off-Network Control Processing (ONCP) that achieves
control scalability in large sensor networks by shifting a certain amount of routing
functions to an “off-network” server. A tiered hybrid routing approach, consisting of
“coarse grain” server-based global routing, and distributed “fine grain” local routing is
proposed for achieving scalability by avoiding network-wide control message
dissemination. We present the ONCP architectural concepts and analytically
characterize its performance in relations to both flat and hierarchical routing
architectures. Through an nsZ-based simulation model, the experimental results
indicate that for large sensor networks with realistic data models, the packet dr0p,
A latency and energy performance of ONCP can be significantly better than those for a
flat sensor routing protocol such as Directed Diffusion and hieratical cluster-based
protocol like CBRP. We also incorporate the sink mobility into routing architecture,
and investigate its impacts on the ONCP, Directed Diffusion, and CBRP routing

protocols.

To my wife, Lan Yang,
my father; Daxin Wu

and in memory of my mother: Yzzhi Zhou

iv

ACKNOWLEGDEMENTS

I would like to take this opportunity to acknowledge all the help and support I have
received over the years in Michigan State University. No amount of words can do this
adequately.

First of all, I am extremely fortunate to have Dr. Subir Biswas as my thesis advisor,
who committed years in training and helping me to be a qualified researcher. Under his
excellent guidance, I have learnt to be a researcher with a lifelong interest in academic
area. He offered valuable insights and suggestions in guiding my research directions.
He read my paper and dissertation drafts and edited my grammar errors without a
complaint. I am also grateful for his excellent advices regarding to presentations,
writings and many other non-technical endeavors. It is an honor and privilege to be his
student and to work with him. I would be delighted if I can still keep his high standards
after graduation. I am also very thankful for Dr. Biswas’s family, who welcomed me
warmly.

I wish to thank Dr. Stuart H. Gage, a member of my Ph.D. committee. As a biological
professor, Dr. Gage gave the knowledge and insight I needed to apply the research
principles to the real world problems. He taught me to think about research problems
with broad perspectives, and encouraged me to study practical problems at the same
time. He provided many suggestions in designing experiments. I also appreciate the
help from other members of my Ph. D. committee: Dr. Eric Goodman, Dr. Peixin
Zhong, and Dr. Jian Ren. They encouraged me in the process of this dissertation and

offered invaluable feedbacks.

I could not have accomplished anything without the support from all my fellow
students and lab-mates: J ayanthi Rao, Fan Yu, Darshak Thakore, Rohit Naik, Nagendra
Singh, Anthony Plummer, Howard Hardiman, Muhannad Quwaider, Sonny
Gupta, Raymond Tatchikou, etc. I thank all of them for many useful discussions, help
and friendship.

I thank all the professors at Michigan State University whom I have taken courses
from and interacted with: Professor Matt W. Mutka, Eric Tomg, Li Xiao, John R. Deller,
Oweiss Karim, and Yimin Xiao. I especially thank Professor Yimin Xiao for
demonstrating that statistics is interesting and fun.

Last, and most importantly, I would like to thank my family. They are the reasons for
who I am, and they are always encouraging and supporting me in all times. I would like
to thank my wife Lan Yang for her support and love during the past few years. Her
understanding and encouragement is very important for my dissertation. My parents,
Daxin Wu and erhi Zhou, receive my deepest gratitude for their many years of support
during my undergraduate and graduate studies.

I wish I could enumerate all the people I need to give thanks, but I am sure I missed
many of them on this short acknowledgment. I am grateful for each of them and wish I
could pass their spirits and kindness to other people in the future.

This work was supported by an NSF grant (SCI-O43 8271) on Sensor Network
Protocols. And most of simulations in this thesis were performed in the cluster
computers of the High Performance Computing Center (HPCC) in Michigan State

University.

vi

TABLE OF CONTENTS

LIST OF TABLES ................................................... x
LIST OF FIGURES ................................................... xi
1. Introduction 1
1.1. Wireless Sensor Networks ..................................... l
1.2. Wireless Sensor Network Applications ............................ 6
1.2.1. Environmental Data Collection .............................. 6
1.2.2. Event Based Monitoring ................................... 8
1.2.3. Object Tracking ......................................... 10

1 .2.4. Other Applications ....................................... 1 1
1.3. Research Issues on Energy Efficiency and Network Scalability ....... 12
1.3.1. Energy Efficient Medium Access Control ...................... 13
1.3.2. Scalable Routing for Very Large Sensor Network ............... 14

2. A Self Reorganizing Slot Allocation Protocol for Multi-cluster Sensor

Networks 18
2.1. Introduction and Motivation .................................... 18
2.2. Related Work .............................................. 21
2.3. Self-Reorganizing Slot Allocation Protocol (SRSA) ................ 24

2.3.1. Network Model and Assumptions ........................... 24
2.3.2. SRSA Protocol Overview ................................... 26
2.3.3. Inter-cluster Allocation Dependency .......................... 28
2.3.4. Frame Scaling for Collision Reduction ....................... 30
2.3.5. Allocation Reorganization Algorithm ........................ 31
2.3.6. Dimensioning Frame Scaling Factor ......................... 35
2.3.7. Protocol Convergence ..................................... 38
2.4. Performance Evaluation ...................................... 39
2.4. 1. Experimental Parameters .................................. 39
2.4.2. Simulation Results ....................................... 40
2.5. Summary ................................................. 53
3. Scalable Routing for Very Large Sensor Network 55
3.1. Related Work on Sensor Routing Protocols ....................... 55
3.1.1. Flat Sensor Routing Protocols ............................ 57
3.1.2. Hierarchical Sensor Routing Protocols ..................... 58
3.1.3. Geographic Sensor Routing Protocols ...................... 59
3.2. Motivation and Problem Description ............................ ‘ .60
3.3. Network And Application Model ............................... 61
3.4. Off-Network Control Processing (ONCP) Routing Architecture ...... 62
3.4.1. Region Management ................................... 64
3.4.2. Cluster Organization ................................... 66

vii

3.4.3. Status Updates ........................................ 68
3.4.4. Global Routing ....................................... 69
3.4.5. Command & Global Routing Download ................... 72
3.4.6. In-network Local Routing .............................. 73

4. Protocol Overhead Analysis 76
4.1. Notations and Definitions ........................................ 76
4.2. Overhead Analysis of Flat Protocols. ........................... 77
4.3. Overhead Analysis of Hierarchical Cluster-based Protocols .......... 78
4.4. Overhead Analysis of ONCP protocol ............................ 79
4.5. Numerical Results ........................................... 81
Il.t5. Eitrrrirriztrjr ................................................. 2355
5. Simulation Models and Experimental Setup 86
5.1. NS-2 Simulation Models ..................................... 86
5.1.1. Channel Propagation Model ............................. 86
5.1.2. Radio Energy Model .................................. 88
5.1.3. Application Data Model ................................ 89
5.2. ONCP Routing Implementation ................................ 91
5.2.1. ONCP Agent Structure ................................ 92
5.2.2. Cluster Organization .................................. 94
5.2.3. Status Updates ....................................... 97
5.2.4. Global Routing and Command Forwarding ................. 98
5.2.5. Local Routing Mechanism ............................. 100

6. Experimental Performance Evaluation of ONCP 103
6. 1 . Experimental Environment ................................... 103
6.2. Results and Analysis ........................................ 105
6.2.1. The Scenarios with Single Base Station .......................... 105
6.2.2. The Scenarios with Multiple Base Stations ........................ 116
6.2.3. Impacts of Region Status Updates ................................ 131
6.2.4. Impacts of Network Size ....................................... 133
t5.22.fi. Eitrrrrrriztryi ................................................... 12315

7. Off-Network Control Processing with Sink Mobility 137
7.1. Introduction and Motivation .................................... 137
7.2. Related Work ............................................... 140
7.3. ONCP-M: Off-Network Control Processing with Sink Mobility ...... 142
7.3.1. Network and Data Model for ONCP with Sink Mobility ...... 142
7.3.2. Extension of ONCP Framework .......................... 144
7.3.3. Sink Relocation Algorithm .............................. 146
7.4. Simulation Results .......................................... 148
17.15. ESirrrirrrzrrjyr .................................................. 1.6577

viii

8. Summary and Future Work 168

8.1. Summary .................................................. 168
8.2. Future Work ................................................ 170
APPENDIX
A Functional Validation of ONCP through Software Emulation and
Hardware Prototype Implementation 172
A]. Introduction ................................................ 172
A2. TinyOS Operating System ................................... 173
A3. ONCP Protocol Stack Implementation .......................... 175
AA. Software Emulation Results .................................. 181
A5. Prototype Hardware Implementation ............................ 184
REFERENCES ...................................................... 187

LIST OF TABLES

Table 2.1: Allocation possibilities for the network in Fig.2.2 ............................. 30
Table 2.2: Overall performance summary ................................................... 53
Table 5.1: Radio Parameters .................................................................. 89

LIST OF FIGURES

F ig.2. 1: Target sensor network and data flow model ....................................... 25
Fig.2.2: TDMA Collisions across overlapping clusters .................................... 28
Fig.2.3: Example slot allocations for network in Fig.2.2 ................................... 29
F ig.2.4: Use of frame scaling for collision reduction ....................................... 31
Fig.2.5: Pseudo code of SRSA protocol logic at each cluster head ...................... 34
Fig.2.6: Parameters for Frame Scaling Factor dimensioning .............................. 36
Fig.2.7: Comparison between SRSA and ideal allocation .................................. 37
Fig.2.8: Model to represent system state with SRSA ........................................ 39
Fig.2.9: Throughput as a function of load ..................................................... 41
Fig.2. 10: CS and I-IN collisions as a function of load ....................................... 42
Fig.2.11: Protocol convergence in SRSA ..................................................... 44
Fig.2.12: Protocol convergence for varying network size .................................. 45
F ig.2. 13: Spatial distribution of packet drops ................................................ 46
Fig.2.14: Packet delivery latency as a function of load .................................... 47
Fig.2. 15: Energy expenditure as node uptime ................................................ 48
Fig.2.16: Collisions for different cluster overlapping ....................................... 49
Fig.2. 17: Throughput with varying cluster overlapping .................................... 50
Fig.2.18: Effects of flame scaling on collisions in SRSA .................................. 51
Fig.2.19: Effects of mobility on Collisions in SRSA ....................................... 52
Fig.3.1: Network and application model ...................................................... 62
Fig.3.2: Tiered concept of ONCP routing .................................................... 63
Fig.3.3: Example region-to-region connectivity metric .................................... 65
Fig.3.4: Pseudo code of ONCP global path computation ................................... 71
Fig.3.5: Pseudo code of command & global routing forwarding .......................... 72

xi

Fig.3.6: Local routing in ONCP architecture ................................................ 73

Fig.4.1: Impact on network size on relative transmission ratio ............................ 82
Fig.4.2: Impacts of data per request (D) on transmission ratio ............................. 83
Fig.4.3: Impacts of region size on the transmissions ratio ................................... 84
Fig.5. 1: Internal blocks of mobile node ...................................................... 92
Fig.5 .2: ONCP agent diagram .................................................................. 93
F ig.5.3: Format of neighbor hello message ................................................... 95
F ig.5.4: Pseudo code for cluster organization algorithm .................................... 96
Fig.5.5: Format of status update message .................................................... 98
Fig.5.6: Format of command message ...................................................... 100
F ig.5.7: Format of local route request message ............................................. 101
Fig.5.8: Format of local route reply message ............................................... 101
F ig.6. 1: Timing diagram of sensing task requests from user clients ..................... 103

Fig.6.2: The diagram of sensing target area and number of nodes per target area. . 104

Fig.6.3: Normalized protocol overhead at rates of 0.5 and l packet/sec ............... 106
Fig.6.4: Normalized protocol overhead at rates of 2 and 4 packet/sec .................. 106
Fig.6.5: Expected packet delivery ratio rates of 0.5 and 1 packet/sec ................... 107
F ig.6.6: Expected packet delivery ratio rates of 2 and 4 packet/sec ..................... 108
Fig.6.7: End to end packet delivery latency at rates of 0.5 and 1 packet/sec ........... 109
Fig.6.8: End to end packet delivery latency at rates of 2 and 4 packet/sec .............. 110
Fig.6.9: Average hop counts at rates of 0.5 and 1 packet/sec ............................. 111
F ig.6. 10: Average hop counts at rates of 2 and 4 packet/sec .............................. 112
Fig.6.11: Average dissipated energy at rates of 0.5 and 1 packet/sec .................... 113
Fig.6. 12: Average dissipated energy at rates of 2 and 4 packet/sec ...................... 114
Fig.6.13: Communication energy consumption at rates of 0.5 and l packet/sec ....... 115

xii

F ig.6. 14: Communication energy consumption at rates of 2 and 4 packet/sec ......... 116
Fig.6.15: Normalized protocol overhead at rates of 0.5 and 1 packet/sec (2BS) ...... 118
Fig.6. l6: Normalized protocol overhead at rates of 2 and 4 packet/sec (2BS) ......... 118
Fig.6.17: Normalized protocol overhead at rates of 0.5 and l packet/sec (4BS) ...... 119
Fig.6.18: Normalized protocol overhead at rates of 2 and 4 packet/sec (4B 8) ......... 119
Fig.6.19: Expected packet delivery ratio at rates of 0.5 and 1 packet/sec (ZBS) ....... 121
F ig.6.20: Expected packet delivery ratio at rates of 2 and 4 packet/sec (2BS) ......... 121
Fig.6.21: Expected packet delivery ratio at rates of 0.5 and 1 packet/sec (4BS) ....... 122
Fig.6.22: Expected packet delivery ratio at rates of 2 and 4 packet/sec (43 S) ......... 122
Fig.6.23: End to end packet delivery latency at rates of 0.5 and 1 packet/sec (23S)...123
F ig.6.24: End to end packet delivery latency at rates of 2 and 4 packet/sec (2BS).... 124
Fig.6.25: End to end packet delivery latency at rates of 0.5 and l packet/sec (438)... 125

Fig.6.26: End to end packet delivery latency at rates of 2 and 4 packet/sec (43 S). . 125

Fig.6.27: Average hop counts at rates of 0.5 and 1 packet/sec (2BS) .................... 126
Fig.6.28: Average hop counts at rates of 2 and 4 packet/sec (2BS) ...................... 126
Fig.6.29: Average hop counts at rates of 0.5 and l packet/sec (4BS) ................... 127
Fig.6.30: Average hop counts at rates of 2 and 4 packet/sec (4BS) ...................... 127
Fig.6.3 1: Average dissipated energy at rates of 0.5 and 1 packet/sec (2BS) ............ 129
Fig.6.32: Average dissipated energy at rates of 2 and 4 packet/sec (2BS) ............... 129
Fig.6.33: Average dissipated energy at rates of 0.5 and 1 packet/sec (4BS) ............ 130
Fig.6.34: Average dissipated energy at rates of 2 and 4 packet/sec (4BS) .............. 130
Fig.6.35: Impacts of node failure on a) delivery performance and b) quality of global
routes ............................................................................................ 132
Fig.6.36: Impacts of status update on energy dissipation ................................. 133
Fig.6.37: Expected packet delivery ratio (13:6) ............................................. 134

Fig.6.38: Communication energy consumption (13:6) .................................... 135

xiii

F ig.7. 1: Network and Application Model with Mobile Base Stations ................... 143

Fig.7.2: Pseudo code for Joint Sink Relocation Algorithm ............................... 148
F ig.7.3: Normalized protocol overhead ..................................................... 15 1
Fig.7.4: Expected packet delivery ratio ..................................................... 152
Fig.7.5: Normalized energy consumption .................................................. 153
F ig.7.6: End to end packet delivery latency ................................................ 153
Fig.7.7: Average transmission hops ......................................................... 154
F ig.7.8: Energy variance at data rate 1 packet per second ................................. 155
Fig.7.9: Energy variance at data rate 2 packet per second ................................ 155
Fig.7.10: Energy variance at different times (data rate = 4 packets per second and 1
node per target area) ................................................. ' .......................... 1 57
Fig.7.11: Energy variance vs the received packets by the base station (data rate = 4
packets per second and 1 node per target area) ............................................ 158
F ig.7.12: Energy variance reduction (data rate = 4 packets per second and 1 node per
target area) ...................................................................................... 15 8
Fig.7.13: Node-energy distribution (data rate = 4 packets per second and 1 node per
target area) ...................................................................................... 159
Fig.7. l4.A: Node-energy distribution at 1080 see (Directed Diffusion - M) ......... 161
Fig.7.14.B: Node-energy distribution at 1820 see (Directed Diffusion - M) ......... 161
Fig.7 . 14.C: Node-energy distribution at 2550 sec (Directed Diffusion — M) ......... 162
Fig.7. l4.D: Node-energy distribution at 3260 sec (Directed Diffusion — M) ......... 162
Fig.7 . 1 5.A: Node-energy distribution at 1080 see (CBRP — M) ........................ 163
Fig.7 . 1 SB: Node-energy distribution at 1820 see (CBRP — M) ........................ 163
Fig.7.15.C: Node-energy distribution at 2550 see (CBRP — M) ........................ 164
Fig.7.15.D: Node-energy disuibution at 3260 sec (CBRP — M) ........................ 164
Fig.7. 16.A: Node-energy distribution at 1080 sec (ONCP — M) ........................ 165
Fig.7. 16.B: Node-energy distribution at 1820 see (ONCP — M) ........................ 165

xiv

Fig.7.16.C: Node-energy distribution at 2550 see (ONCP — M) ........................ 166

Fig.7.16.D: Node-energy distribution at 3260 see (ONCP — M) ........................ 166
Fig.A. l: ONCP Protocol Stack Component Graph ........................................ 176
Fig.A.2: Expected Delivery Ratio ........................................................... 182
Fig.A.3: Routing Overhead .................................................................. 183
Fig.A.4: Average Transmission Hops ....................................................... 184
F ig.A.5: Sensor Node Mote2dot, Mote2, Imote, TelosB, Cricket (from left to
right) ........................................................................................... .185
Fig.A.6: Grid structure of hardware implementation ........................... 186

XV

Chapter 1
Introduction
1.1 Wireless Sensor Networks

Recent advances in micro-electro-mechanical system (MEMS) and integrated digital
electronics make it possible to integrate sensing, computation, communication into
single tiny devices. Such devices are generally equipped with the capabilities of data
processing and communication. These inexpensive and low power devices can provide
high-resolution measurement of physical environment, processes and location
information to enable a wide range of applications. While the capabilities of a single
device can be often limited, the composition of hundreds or thousands of such devices
forms wireless sensor networks (W SN). Such networks promise advantages over
traditional sensing methods in many ways. Large scale deployment and close proximity
to physical environments not only extend the spatial coverage and increase orders of
magnitude measurement granularity, but also provide fault-tolerance and robustness for
systems.

The major strength of wireless sensor networks results from the ability of large scale
node deployment and in-network data processing at very low cost. The network size
can be scaled to thousands or even hundreds of thousands of wireless sensor nodes in
applications, such as environmental monitor, battlefield surveillance and enemy
tracking. By the year 2010, the price of these devices is expected to be less than $1 [1].
At this price range, with a communication range of 50 meters, it costs only 40 thousand

dollars to fully monitor a 100 square kilometer habitat area. Also, the deployment costs

for wireless sensor networks can be minimal. Unlike traditional wired systems, network
operators do not need to deploy thousands of feet of wires to connect the sensor nodes.
The network can be easily extended by adding more nodes into the network without
additional configuration. And in case of node failures, wireless sensor networks have
the ability to self-reorganize and reestablish network topologies.

While wireless sensor networks share many commonalities with Ad-hoc networks
and wireless mesh networks, there are a number of differences and unique challenges
due to their specific design characteristics. Such challenges arise from constrained
energy supply, limited bandwidth and processing ability, and ultra large scale of node
deployment. The unique characteristics of wireless sensor networks are highlighted as
follows.

Applica_tion specific ISSMZ Sensor networks have a wide variety of applications,
ranging from environmental data collection, seismic detection, health monitoring,
battlefield surveillance and enemy tracking, etc. It is unlikely that there will be a
general solution to satisfy all diversified or even conflicting requirements of all
applications. For example, the tracking and surveillance applications need the detected
events to be processed and reported within a very short period at high delivery rate. On
the other hand, environmental data collection applications can tolerate a certain amount
of data loss and larger transmission latency in order to maximize the network lifetime.
Generally, sensor network protocols are optimized at all layers to meet the demands of
the specific applications.

Enemy Consinerations: Energy is a scarce resource for wireless sensor networks.

Most sensor nodes are powered by non-rechargeable batteries, except for a few mobile
sinks [2]. Therefore, it is essential to conserve computation and communication energy
dissipation at all layers, from hardware design, medium access control, to network
routing. Communication is usually the most energy extensive operation. The network
stack should attempt to minimize energy usage, either by eliminating communication,
or by turning off the radio when no communication is needed. The network lifetime has
a strong dependency on the battery lifetime. In multiple hop communications, sensor
nodes have a dual role: data generation and data forwarding. Node failure can break
routing paths, and incur network topology re-organization. In some severe cases, it can
even block all paths to data sinks, causing network partition. The need to efiiciently
utilize energy has a deep impact on the system architecture and protocol design.

Scalability: The number of nodes deployed in sensing fields may vary from hundreds
to thousands, or even hundreds of thousands, depending on the type of applications. For
example, the networks for environmental monitoring are likely to cover miles of target
area comprising potentially thousands of sensor nodes. The huge number of devices
not only provides increasing ability to instrument the physical world with great fidelity,
but also poses a big challenge for network design. Frequent network-wide data
dissemination or routing path establishment is not appropriate, which not only
consumes the limited available bandwidth, but also incurs a heavy energy burden on
networks. Scalability requires information exchange and node coordination to be local.
Minimal information should be disseminated towards the whole network.

Data DeliverLModels.' Depending on the application types, the data delivery model

from data sources to sink nodes can be categorized as continuous, event-driven,
query-driven, or hybrid [3]. In the continuous data delivery model, sensor data sources
periodically send data to sink nodes. Typical applications include environmental
monitoring and health monitoring. In event-driven and query-driven models, the
transmission of data is triggered when interesting events are detected by sensor nodes
or queries are generated by sink nodes to measure sensing attributes. This type of data
delivery model is suitable for time-critical applications, such as intrusion detection and
collaborative disaster management. Some networks apply a hybrid model of continuous,
event-driven delivery model. Network architecture, especially routing protocols, is
highly influenced by the data delivery model. It is suggested in [4] that for habitat
monitoring applications, a hierarchical routing protocol is the most desirable to
suppress the redundant data.

In-network Da_ta Processing: Low cost and low energy supply require redundant
deployment of wireless sensor nodes in many applications. This fact, together with
simultaneous event detection by multiple nodes, results in significant redundant data
being generated. Highly correlated data from multiple nodes in close proximity should
be aggregated before being reported to sink nodes. Considering the fact that
computation is much less energy consuming than communication [5], it is desirable to
perform in-network data processing instead of sending all raw information to sink
nodes. Data fi'om different sources can be combined based on aggregation functions,
such as suppression, min, max, and average [6]. Signal processing techniques can also

be utilized, which are capable of producing more accurate signals by beamforming or

noise reduction [5]. In-network data processing has multiple impacts on routing
protocols, such as improving energy efficiency and reducing traffic load.

Network Dynamch: wireless sensor nodes are assumed to be stationary in most
network architectures. However, there are some applications which require mobile sink
nodes to improve performance [2]. Routing in the mobile context is more challenging
as route stability becomes an important issue. The sensing event can be dynamic as well,
based on the specific applications. For instance, in target detection/tracking
applications, the movement of a target might incur dynamic event generation. Dynamic
events generally require in-network data processing; otherwise extensive traffic will be
route back to base stations. Even if all the nodes in the networks are static, yet the
network topology can still be dynamic because of node failure or energy drainage.
Frequent topology changes impose additional overheads on the network layer, as
routing paths need to be rediscovered.

@alitv of Service: In some applications, data should be delivered within a certain
period of time from the moment it is sensed; otherwise the data will be useless.
Therefore bounded latency for data delivery is another condition for time-constrained
applications. However, in many applications, conservation of energy, which is directly
related to network lifetime, is considered relatively more important than the quality of
data sent. As the energy gets depleted, the network may be required to reduce the
quality of the results in order to reduce the energy dissipation in the nodes and hence
lengthen the total network lifetime. Hence, energy-aware routing protocols are required

to capture this requirement.

1.2 Wireless Sensor Network Applications

The majority of wireless sensor network applications can be categorized into three
classes: environmental data collection, event-based monitoring and object tracking.
1.2.1 Environmental Data Collection

Environmental data collection applications represent a class of sensor network
applications with enormous potential benefits for scientific research communities and
the society. It provides long term data collection at scales and resolutions which are
very difficult to obtain in traditional methods. The intimate connection with the
physical environment allows sensor networks to provide localized measurement and
detailed information. Researchers collect sensor measurement from an environment
over a long period of time in order to detect data trends and interdependencies. The
measurement would be gathered from hundreds of points spread over several miles in
field environment The data collection duration would last over several months or even
years in order to get long-term and seasonal trends. For the data to be meaningful it may
require to be measured at regular intervals and the nodes would remain at known
locations. The data collection tasks should be flexible, and adjustable by user requests.
For example, researchers should be able to send out sensing tasks, asking to collect
information about temperature at area “A” for 2 weeks at an interval of 10 minutes. And
later a new task to know humidity measurement at area “B” for half year at an interval
of 20 minutes may also be generated. The sensor networks should be flexible to support
various and dynamic data collection applications.

At the network level, the environmental data collection application is characterized

by having a large number of nodes continually sensing and transmitting data back to a
set of base stations. These networks generally require very low data rates and extremely
long lifetimes. Depending on application’s requirements for sensing coverage and
resolution, the network size may vary from hundreds to hundreds of thousands of
nodes.

While the base stations for data collection and aggregation may be powered by wire
connections, the majority of nodes in the networks are powered by batteries, which are
not replaceable. Environment data collection applications usually use tree-based
routing strategy. Data is transmitted from child nodes to parent nodes along the tree, till
reaches the rooted base stations. Although the leaf nodes may generate a small amount
of data, the nodes with lots of descendants need to receive and relay considerably large
amount of data. Therefore, these nodes are more likely to be energy bottlenecks. In
order to conserve communication energy, the radios of nodes should be turned off
whenever there is no ongoing traflic. In this case, an energy-efficient TDMA type
Medium Access Control is desired.

For sensor networks, it is expected that some nodes will fail over time, due to
hardware failure or energy drainage. And it is also possible for new nodes to be added
into the network to replace failed ones or to extend coverage. In both scenarios, the
networks need to reconfigure to discover the topology and reestablish routing paths.
The network reconfiguration should be local and infrequent to avoid high energy
dissipation due these overhead.

One of the typical environment data collection applications is the Great Duck Island

(GDI) system. Researches deployed a mote-based tiered sensor network on Great Duck
Island, Maine to monitor the behavior of storm petrel from collected information on
light, temperature, infrared, humidity and barometric pressure [7]. 32 motes are
deployed at area of interests, which are grouped into sensor patches. These sensor
patches send data to gateways through multiple hops, and then the gateways relay the
data to a base station through an 802.11 wireless network. At the base station, the data is
updated to database in Berkeley every 15 minutes through satellite links. Users can
access the data either from the remote server in Berkeley or read local data at Great
Duck Island by a Compaq iPaq PDA.

In general, environmental data collections applications are characterized by long
network lifetime, low data rate, relative static network topology, and tolerable delay.
1.2.2 Event-Based Monitoring

Another class of sensor network applications is event based monitoring. Compared
with environmental data collection applications, event detection monitoring
applications are not intended to collect data, instead they aim to detect whether
predefined events happen in the environment, and report these events to users. The
majority of energy dissipation here is not for communication, but for event detection
and in-network processing. The real-time and reliable communication of detected
events is the most important requirement, as the events are expected to happen very
infrequently and the consequences of event loss could be severe. All these requirements
have a significant impact on network architecture design.

When sensor nodes detect an event, a message needs to be generated and reliably

forwarded to the base station in real time. The allowable message latency is determined
by the nature of different applications. For example, the latency for a detected fire
alarm in forest can be within minutes, while enemy intrusion detection must be reported
in seconds. In the latter case, the network should be able to respond quickly to detected
events and forward data.

The traflic pattern of event detection monitoring applications is “bursty”. Most of
the time events do not happen in the networks, and sensor nodes only need to
periodically check neighbor information to ensure nodes’ ftmctionality. However, once
an event is detected, a significant amount of traffic will be generated in a short period.
Nodes need to collaborate with each other track the changes, and report messages to the
base stations. It is very likely that multiple nodes will detect the same event
simultaneously; therefore, in-network data processing may be employed to enhance
message accuracy and reduce traffic load.

It is also important to confirm the functionality and aliveness of sensor nodes. If
nodes had suffered failure and could not monitor sensing areas, it would represent a
security violation that need to be reported. The network should have the ability to
ensure the monitoring coverage of sensor nodes; otherwise it can not fimction properly.
This requires coordination between neighbor nodes. The topology control of an event
detection monitoring network will look quite different from that of a data collection
network. A large portion of the energy will be spent on confirming the firnctionality of
neighbor nodes and performing event detection. The data message transmission will

consume a small fraction of the network energy.

Firebug [8] project is a wildfire monitoring application, based on Berkeley motes. It
is composed of environmental sensors collecting temperature, relative humidity and
barometric pressure with an on-board GPS unit attached to a wireless, networked mote.
The motes communicate with a base station, which sends the collected data to a
database server. The data can be accessed using a browser-based web application or
other application capable of communicating with the database server. Performance of
the monitoring system during two prescribed fires at Pinole Point Regional Park
(Contra Costa County, California) is promising. Sensors within the fire zone recorded
the passage of the flame front before being scorched, with temperature increasing, and
barometric pressure and humidity decreasing as the flame front advanced.

1.2.3 Object Tracking

A third class of sensor network applications is to track an object status in real time.
The most visible and publicly discussed example is the usage of RF ID (radio frequency
identification) tags in supply chain management. US Department of Defense demands
the support of RFID technology from their supplies within the next few years. Delta
Airlines with US Transportation Security Administration successfully performed a
pilot project for baggage handling through RFID at the airport of Jacksonville, Florida
[9]. And Wal-Mart Stores Inc. mandated that its top 100 US supplies tag all cases and
pallets carrying merchandise by January 2005 [10].

In the traditional inventory system, when merchandise passes a checkpoint, its
barcode is scanned by a reader, so that the system can track the data flow through

different checkpoints. However, it is time consuming and inefi'rcient to track the objects

10

because of the inflexible barcode scanning processing. And it is impossible to provide
real-time status for the merchandise. With wireless sensor networks, objects can be
identified and tracked by attaching RFID tags. The tags can be active, which are able to
announce the presence of the devices. Through wireless communication with RFID
readers, the objects can be easily and quickly tracked without any physical contact. A
database can record the location of tracked objects and check whether they are damaged
and need replacement. With the system, it is possible to query and process the current
statuses of objects at very low cost. Then the business applications respond to these
inputs and arrange the corresponding actions, such as replacing component or
requesting the delivery of additional products.

To be cost effective, the device is a very low power, low performance sensor unit [11].
It includes physical sensors, a low-power micro controller, limited memory, and a
low-power, short-range wireless radio. The duty cycle is expected to be 0.01%, which
means the devices are in sleep mode about 99.9% of the time. The medium access
control protocols should be very energy efficient, and adaptive to topology changes. In
addition, the tracked objects may continually change positions, it is important for the
network to efficiently detect the presence and leave of the objects.

1.2.4 Other Applications

In general, applications may require multiple features. For example, in an
environmental data collection application, researchers may generate requests to get
periodical monitoring data for wild animals. In the meantime, they are interested to

detect the environment anomaly, such as flood, fire, etc. Once an anomaly happens, the

11

detected events will be reported back to the base stations quickly and reliably. It is also
possible to track the movement of specific animals like giraffes, in order to understand
their behavior in the natural habitats. The networks should be flexible enough to
support all the requirements in a single system.

There are other types of applications whose major challenges are on
micro-electro-mechanical system (MEMS). In health application [12], researchers are
working on artificial retina. Retinal prosthesis chip consisting of 100 micro-sensors are
built and implanted within human eye. It allows patients with no or limited vision to see
at an acceptable level. The wireless communication is needed for feedback control,
image identification and validation.

The combination of sensing, micro controller and wireless communication provides
tremendous potential applications for wireless sensor networks. These networks
perceive the physical environment in ways that were not possible previously. They not
only offer the potential to advance many scientific pursuits, but also provide a platform
for enhancing large forms of productivity in the industry of manufacturing, agriculture,
construction and transportation.

1.3 Research Issues on Energy Efficiency and Network Scalability

Although wireless sensor networks have already demonstrated a promising future,
there are a number of challenges to be overcome before they become reality in a wide
range of applications. The issues include fault tolerance, network scalability, cost,
hardware, topology management, environment changes and power consumption [13].

In this work, we mainly consider the challenges of power consumption and network

12

scalability from the medium access control and the networking layers.
1.3.1 Energy Efficient Medium Access Control

Energy is the most constrained resource for wireless sensor networks. From the
development history of battery, it is not expected to see significant breakthrough in next
few years. Therefore, it is important to consider the energy efficiency from all
communication layers. This constraint and the associated computation and storage
limitations lead to a new set of communication architectural design.

Many wireless devices, such as cell phones and PDA, can reduce their power
consumption through the use specialized communication hardware in ASICs that
provide low-power implementations of communication protocols [14]. However, the
strength of wireless sensor networks is their flexibility and universality. The wide range
and different nature of applications makes it difficult to develop single protocol stack to
suit for all requirements. Therefore ASIC hardware design can not be applied for all
applications. A wireless sensor network platform must provide support for a suite of
application-specific protocols that drastically reduce node size, cost, and power
consumption for their target applications.

In wireless sensor networks, communication is significantly more expensive than
computation. Therefore, it is very important to reduce energy dissipation in
communication. In a shared medium MAC, the non-essential energy expenditures are
contributed [16] by the following four sources. (1) protocol overhead: to execute
resource control, a MAC protocol has to incur some overhead, besides the basic data; (2)

collisions: retransmissions due to collisions lead to unnecessary energy consumption;

13

(3) overheating: nodes expend energy to receive packets for which they are not the
intended receivers; (4) idle listening: in protocols that do not have any centralized
transmission slot allocations, nodes have to always keep their wireless radio interface
powered on for all possible receptions. This consumes power even when a node does
not transmit or receive for a long time. Research has shown [16, 17] that idle listening
accounts for most of the energy consumption at low traffic situations, which are
prevalent for lots of wireless sensor network applications.

Fortunately, many wireless sensor network applications are delay tolerant and
require low bandwidth. It is possible to trade classical performance parameters
(throughput, latency, fairness) for better energy efficiency. At MAC layer, sensor nodes
should be able to reduce the radio duty cycle to improve the lifetime of networks. In this
work, we propose the Self Reorganizmg Slot Allocation (SRSA), for implementing
spatial TDMA type MAC protocol for sensor networks with clustering abstraction. The
details of our design are given in chapter 2.

1.3.2 Scalable Routing for Very Large Sensor Network

Typically, the number of sensor nodes deployed in fields may be on the order of
hundreds or thousands. Depending on the applications, it is possible for the number to
reach even millions. These very large sensor networks not only provide a revolutionary
way to perceive physical world with great fidelity, but also pose a big challenge for
network protocol design.

Routing protocols for Ad hoc networks generally use either distance-vector or

link-state routing algorithm [18]. Both types of protocols find shortest paths to

14

destination nodes. In distance-vector routings, a vector containing the cost (e.g., hop
distance) and the path (next hop) to the destination is kept and exchanged at all the
nodes in the network, when routing discovery is generated. The link-state routing
algorithms periodically flood link information about its neighbors to maintain the
global network topology at each node. In large networks, the transmissions caused by
routing overhead can be overwhelming. These messages will consume a large part of
the bandwidth and consequently block applications. They can have a series of adverse
effects including frequent packet drops and increased latency. A more detrimental
effect is the increased energy overhead on the resource constrained sensor nodes. Thus,
reducing routing control overhead becomes a key issue in achieving the routing
scalability.

Hierarchical routing protocols relieve the scalability problem by organizing nodes in
groups and assigning nodes different ftmctionalities inside and outside of a group. Both
routing table size and the number of packets exchanged are reduced as only parts of the
nodes in the network are involved in the route discovery process. An example of
hierarchical routing is the Internet hierarchy, which has been practiced in wired
networks for a long time. In wireless hierarchical routing, the most popular way of
building hierarchy is to group nodes geographically close into clusters. Each cluster has
a leading node (cluster head) to communicate to other nodes on behalf of the cluster.
The cluster heads and the corresponding nodes connecting them build a “backbone”
network. Routing discovery messages are exchanged on the “backbone” network.

However, in the wireless network, as there are no strict hierarchy management like

15

Internet, the efficiency of hierarchical routing is very limited. To discovery paths, the
routing messages need to flood the whole “backbone” network, which includes
20%~40% of the total network nodes [19]. Hierarchical routing protocols suffer from
the scalability problem in large networks.

Geographic routing protocols take a different approach to address the scalability
problem. Sensor nodes are assumed to know their locations, either from Global
Position System (GPS) devices or location identification algorithms [42]. With the
knowledge of node locations, routing can be more effective and scalable at the cost of
overhead incurred by exchanging neighbor coordinates. The main idea of geographic
routing works as follows: when a node receives a packet with destination’s location, it
chooses one of its neighbors whose is geographically closest to the destination, and
forwards the packet to it. The process repeats at each intermediate node till the packet
reaches the destination. However, if the packet arrives at a dead end (all the neighbors
are farther way from destination than itself), a detour search is incurred to find the path
to destination. In regular topologies where detour search can be avoided, geographic
routing perhaps is one of the most efficient protocols, as it only needs to exchange
l-hop neighbor coordinates information, which does not require network-wide route
discovery. However, in sensor networks it is not financially feasible to equip every
cost-constrained sensor node with GPS devices. And in the events of frequent detour
searches, the additional control overhead lessens the advantages of these protocols.
Frequent detour searches are usually caused by irregular terrains and other

administrative and security-based network partitioning.

16

To solve the routing scalability problem, we propose a routing solution that achieves
control plane scalability by avoiding network-wide route searches without relying on
geographical information. The key idea is to shift part of the route computation to an
“off-networ ” routing server. This server is assumed to be non energy-constrained, and
it is used for performing “coarse grain” global route computation. The “fine grain”
local routing is performed locally within the sensor nodes in a distributed manner. This
hybrid server-based and distributed approach can significantly decrease the

requirements for routing control message exchange.

17

Chapter 2

A Self Reorganizing Slot Allocation Protocol
for Multi-cluster Sensor Networks

2.1 Introduction and Motivation
Sensor networks typically consist of very large number of low cost sensor nodes
which can collaborate among each other to enable a wide range of applications such as
environmental and health monitoring, security and intrusion detection, and
collaborative disaster management. Communication protocols for traditional networks
are divided into several layers, and these protocols are designed for flow-oriented
transactions in which data is generally routed from one or multiple predefined sources
to one or multiple predefined destinations. Sensor networks, however, are data-centric
in which a piece of data is generally routed based on its content and context rather than
on predefined source-destination flows. In addition, communication in sensor networks
is highly influenced by their various constraints, including limited energy supply.
Therefore, it is crucial for the sensor network protocols to be energy efficient in order to
extend the network lifetime. Traditional wireless MAC protocols such as IEEE 802.11
[2 1], CSMA and HiperLan-II [22] are designed for optimizing throughput, latency, and
fairness without specifically concentrating on their energy usage. In sensor networks,
Since energy efficiency is one of the primary requirements, these protocols are not
directly useable without substantial modifications. Therefore, new energy-aware MAC
pr Otocol models are necessary for sensor networks.
Also, while the traditional “split” layered protocols have advantages in terms of

funCational abstractions and interoperability; they often pose severe encumbrances for

18

energy optimization due to their functional generality and implementation overhead. To
address this, cross-layer designs are required so that instead of being functionally
independent, the protocols at different layers are designed to be interdependent and can
be optimized together to achieve better energy performance.

As we discussed in chapter 1.3, energy is the most constrained resource for wireless
sensor networks, and communication is significantly more expensive than computation.
It is essential to reduce to the energy dissipation in wireless communication. In this
chapter, we present an energy efficient MAC protocol, Self Reorganizing Slot
Allocation (SRSA), for implementing a spatial TDMA protocol in sensor networks.
While reducing energy consumption in MAC layer, SRSA also leaves room for
cross-layer performance optimization in routing layer. The central idea behind
cross-layer optimization is to adapt routing based on cluster-based slot allocation by the
SRSA MAC. Here we will only concentrate on the MAC layer aspects of SRSA.

In a shared medium MAC, the non-essential energy expenditures are contributed [16]
by the following four sources. (1) protocol overhead: to execute resource control, a
MAC protocol has to incur some overhead, besides the basic data; (2) collisions:
retransmissions due to collisions lead to unnecessary energy consumption; (3)
overhearing: nodes expend energy to receive packets for which they are not the
intended receivers; (4) idle listening: in protocols that do not have any centralized
transmission slot allocations, nodes have to always keep their wireless interface
powered on for possible receptions. This consumes power even when a node does not

transmit or receive for a long time. Research has shown [16, 17] that idle listening

l9

accounts for most of the energy consumption at low traffic situations, which are
prevalent for lots of wireless sensor network applications.

A significant amount of work has been done [16, 17, 21-30] on decreasing idle
listening. The main idea behind this research is to power off network interfaces when
possible. In effect, a node’s operating time is divided into active-sleep cycles. Each
cycle consists of an active duration for regular transmissions and receptions and a sleep
duration during which the network interface is powered off for saving idle listening
consumption. The ratio of active period to active-sleep cycle duration is referred to as
the duty cycle of operation. Smaller the duty cycle, lower the consumption due to idle
listening. The main goal of all protocols in this category is to operate at the smallest
possible duty cycle while being able to support application loading requirements.

TDMA MAC protocols also belong to this category because of their built-in
active-sleep duty cycles that can be leveraged for limiting idle listening. Although this
makes TDMA a natural choice for sensor MAC, successful implementation would
require some form of spatial TDMA [31] in the presence of overlapping MAC
clustering. In such deployments, the main challenge is to devise TDMA slot allocation
mechanisms with the goal of minimizing allocation collisions across overlapping
clusters. A straightforward solution [5] to this problem is to use Code Division Multiple
Access (CDMA) or Frequency Division Multiple Access (FDMA) across clusters and
then to run independent TDMA schedules within each cluster. However, using CDMA
or FDMA incurs costs in terms of spectrum usage as well as network interface

complexity for low-cost sensor nodes.

20

The design objective of our work is to devise mechanisms for minimizing
inter-cluster TDMA interference without actually using CDMA or FDMA. To
accomplish this, one approach will be to use a centralized scheduler that can perform
TDMA slot allocations for the entire network based on cluster boundaries and
overlapping across neighbor clusters. To avoid the scalability concerns of such
centralized mechanisms, we propose a distributed Self Reorganizing Slot Allocation
(SRSA) protocol that operates at the cluster level and does not rely on any information
beyond a cluster. The main idea is to initiate communication with a reasonable initial
TDMA allocation and then, adaptively change the slot allocation schedule locally based
on feedback derived from collisions experienced by the local nodes. SRSA slot
allocation is executed adaptively relying only on local information. The main
contribution of this work is to demonstrate that for low sensor loading scenarios, the
SRSA protocol is able to minimize TDMA slot interference across neighboring clusters
without relying on CDMA, FDMA or any global synchronization mechanisms.

In Section 2.2, we describe the related work on energy efficient MAC protocols.
Then in Section 2.3, we elaborate the design of the proposed SRSA MAC protocol. In
Section 2.4, we describe our simulation setup, followed by a detailed analysis of the
experimental results. And we summarize our work in Section 2.5.

2.2 Related Work

Active-sleep duty cycle based mechanisms for limiting idle listening have been

applied to both contention-based as well as contention-free MAC protocols [16, 31-36].

In contention-flee protocols like TDMA, since transmission and reception time slots

21

are pre-allocated, and nodes can sleep during the known inactive periods, they are
inherently more energy efficient compared to the contention-based protocols.

Ye et a1. propose S-MAC [16], in which the basic idea is to synchronize nodes in an
active-sleep cycle so that the nodes can communicate during the active period and turn
their interfaces off during the sleep period. During the active periods node execute an
802.11-like light weight CSMA-CA MAC protocol. Sensor nodes form virtual clusters
so that all nodes within a virtual cluster maintain the same active-sleep schedule. While
the active duration determines allowable traffic load, the sleep duration determines the
packet delivery latency. By decreasing the active-sleep duty cycle, this protocol can
trade energy for latency and channel bandwidth. SMAC suffers from the following
shortcomings. First, since the basic medium access mechanism is contention-based,
due to channel contentions the protocol cannot guarantee bounded delivery latency at
high loads. Second, nodes at boundaries of the virtual clusters require maintaining
multiple schedules, one for each cluster. Maintaining multiple schedules requires a
node to remain awake during the active periods for all its maintained schedules. As a
result, nodes with multiple schedules can have significantly larger energy drainage
compared to the nodes with only one schedule.

An alternative way to introduce periodic active-sleep cycles is by using the concept
of wake-up radio [17]. In this protocol, a node normally sleeps, but when it has data to
transmit, it first sends a signal through another channel to wake up the receiver node.
Since the only function of the radio for wake-up channel is to wake up sleeping nodes

(no data processing), the hardware for that interface can be simpler and less energy

22

hungry. Nevertheless, this design adds an extra transceiver which is an added cost and
complexity burden for low-cost sensor nodes.

CSMA with preamble sampling [32, 33] incorporates the concept of active-sleep
cycles from the receivers’ perspective. The idea is to precede each transmission with a
long preamble of duration Tp. A node wakes up every Tp duration to sense the channel.
If no preamble is detected within Ts duration, the node goes back to sleep. If a preamble
is detected, then a node continues to listen until a packet has been received or a timeout
occurs. This allows receivers to sleep most of the time when the traffic is low. When the
channel is idle, the approximate active-sleep duty cycle of the radio is Ts / (Ts + Tp). A
notable feature of this protocol is that unlike in SMAC, the duty cycle of operation does
not have to be pre-defined based on anticipated traffic load. It is automatically adjusted
based on the instantaneous loading conditions. Preamble sampling shifts idle listening
energy burden from receivers to senders in the form of energy expenditure for
transmitting long preambles. The situation worsens with increased collisions and
retransmissions at higher loads. Additionally, like other contention-based protocols, it
suffers from the unbounded delivery latency problem.

Under low traffic loads, all these protocols work well. But when load increases, these
contention—based protocols degrade drastically because of collisions and subsequent
retransmissions. For higher load situations, TDMA based protocols can offer better
channel utilization [34] and energy performance due to their inherent ability to follow
active-sleep cycles based on periodic slot allocations. The main challenge for using

spatial TDMA in a large sensor network is to come up with slot allocation schedules for

23

maximum channel utilization with minimum packet delivery latency.

Most spatial TDMA protocols do not scale well, since they assume the knowledge of
the global topology. Scalability can be achieved by partitioning a network into smaller
clusters and running independent TDMA framing within each cluster. To avoid
allocation collisions across neighbor clusters, the use of CDMA (or FDMA) has been
suggested in [5]. However, using CDMA or FDMA incurs costs in terms of spectrum
usage as well as network interface complexity for low-cost sensor nodes. The objective
of our work is to devise a mechanism for minimizing inter-cluster TDMA collisions
without using CDMA or FDMA.

2.3 Self-Reorganizing Slot Allocation Protocol (SRSA)

Design of SRSA is targeted to meet the following two requirements. First, the slot
allocation process should be online and adaptive, with detected collisions as a feedback
parameter. Second, the protocol has to operate locally without having to rely on any
inter-cluster communication, synchronization and global timing.

2.3.1 Network Model and Assumptions

In our network model (see Fig 2.1) data is sensed from a sensor field periodically and
delivered to monitoring applications through base stations and a wired network. It is
assumed that each sensor node can communicate directly with at least one base station.
For scalability, however, the network is self-organized into multiple clusters [5], and
within each cluster a sensor node is autonomously elected as the cluster head of that
cluster. A cluster head acts like the gateway between the nodes within its cluster and the

base stations.

24

From an energy standpoint, the advantages of clustering are as follows. First, by
routing all data through the local cluster heads, the nodes avoid high-power long
distance wireless transmissions to the base stations. Only the cluster heads have to
transmit under such distances. A cluster head can fiuther reduce the transmission
energy expenditure by aggregating the collected data from its cluster before relaying
them to the base stations. This reduces the overall network-wide transmission energy
expenditure. Since the monitoring applications are often interested only in
geographically aggregated rather than per-node data, aggregation at cluster heads is
highly desirable for extending the lifetime of sensor networks. Since the cluster-heads
spend more communication energy than the regular sensor nodes, the responsibility of
cluster-head has to be rotated [5] across all the sensor nodes for energy

load-distribution.

 

  
  
 
    

 

 

Ap " 88-2
pnwfion I J .- JR;- I A
\- s 2' l'r ‘ “CH" fir: "
‘ - '... ..-“-'..' "30‘“. ‘1 F 3 ‘ _
. .,'-..‘ can-1‘2?! w n ‘ ('7‘ /
....'. .. ”A ,\L ..»..n ...-

- ‘k. -,
335° ‘1 \r
Station-1 "s, "x.
'o

 

 

‘u..

’s

 

Cluster Heads

 

 

 

 

 

 

Fig. 2.1: Target sensor network and data flow model
Successful operation of this model would depend on three crucial protocol

components, namely, self-reorganizing cluster formation, autonomous cluster-head

25

election and energy-efficient medium access control. This work proposes a new MAC
protocol while relying on existing cluster formation protocols [2, 25, 26, 27, 29] and
cluster head election mechanisms [2] available in the literatures. Note that we provide a
MAC solution only for the intra-cluster communication. A separate mechanism will be
necessary for the base station to cluster head communication.

2.3.2 SRSA Protocol Overview

After the clusters are self-organized and cluster heads are elected, each cluster
maintains a local TDMA MAC flame. Each regular sensor node is allocated TDMA
slots for uplink transmissions as well as for downlink receptions. After a node receives
its slot allocation, it remains active during the allocated slots and sleeps during all other
slots.

In SRSA, we assume that the packets are of fixed size and the TDMA flame
durations in all clusters are the same and it is pre-configured. However, the frame
timing across the clusters is assumed to be asynchronous and the number of nodes in
different clusters is not assmned to be equal. Nodes within a cluster are time
synchronized through their cluster-head. TDMA slot duration is equal to the packet
time plus a short duration for carrier sensing before transmission. Data is exchanged
only between a sensor node and its local cluster head. The baseline SRSA protocol is as
follows.

Step-l (Initialization): A cluster head initially makes a random TDMA slot allocation
to its cluster nodes.

Stein-2 (Carrier sensing): Before transmitting, a node first senses the carrier to see if

26

there is an ongoing transmission due to an overlapping allocation in any of the neighbor
clusters. If the channel is found flee then the packet is transmitted. Otherwise, a Carrier
Sense Collision (CS-Collision) is declared and the packet is buflered until the next
allocated slot for that node. A CS-collision indicates that there exists at least one
overlapping allocation in one of the node’s neighbor clusters. An example CS-collision
situation will arise in the network in Fig. 2.2 when node C in cluster-1 and node D in
cluster-2 are allocated overlapping TDMA slots. Since C and D are within each otherS’
transmission range, the node which starts transmission later will detect a CS-Collision.
SteL3 (CS-Collision Feedback): Upon detection of a CS-collision, a node sends that
information to its cluster head through the next successful uplink packet transmission.
A bit in the packet header is designated for carrying this information. This method of
learning about a CS-collision by a cluster head is referred to as active detection.
Another way to infer about a CS-Collision is by passive detection. If a cluster head
observes that although uplink slots have been allocated to it, a node in the cluster is not
transmitting uplink packets for a large number of flames, then a passive detection of
CS-Collision takes place. Passive detection works better in higher loading situations.
Step-4 (HIV-Collision Detection): Consider a situation in Fig. 2.2 when node C in
cluster-1 and node E in cluster-2 are allocated overlapping TDMA slots. Since these
two nodes are outside each others’ transmission range, instead of CS-Collision, a
Hidden Collision will occur at the head of cluster-2. Unlike CS-Collisions, the
HN-Collisions cause packet drops and can be directly detected by the affected cluster

heads. It cannot be detected by the colliding nodes.

27

Step-5 (Slot Allocation Reorganization): At the end of each TDMA frame, a cluster
head examines all TDMA slots for CS-Collisions or PIN-collisions. Then the cluster
head executes a reorganization of the local slot allocation so that the number of CS and
HN collisions can be reduced in subsequent TDMA flames, and eventually minimized
to a stable range. The reorganized TDMA schedule is then downloaded by the cluster
head to its cluster members at the beginning of the next frame.

A possible schedule download mechanism for a cluster head would be to broadcast a
bitmap specifying the new slot allocation schedule. Depending on the size of the bitmap,
it can be downloaded either as a part of the header of a downlink user packet or as a
separate downlink control packet Since all clusters work in a distributed way, missing a
schedule only increases the convergence time for SRSA to reach a stable state.

Steps 3, 4 and 5 are iteratively executed to maintain stable and optimal allocation.
Details of the allocation reorganization process in Step 5 and its impacts are described

in the next few subsections.

 

Cluster-1 Cluster-2

    
  
 
 

'——--
~~~~~
I’ ‘

 

Physical
Connectivity

 

 

 

Fig. 2.2: TDMA Collisions across overlapping clusters
2.3.3 Inter-cluster Allocation Dependency
All possible overlapping slot allocations for the network in Fig. 2.2 are summarized

in Table 1. To clarify, for example if node C and node B are allocated overlapping slots

28

then an HN-Collision will occur at the head of cluster-2.

Although the goal of an optimal allocation is to maximally utilize the collision flee
combinations, depending on the relative locations of the nodes it may or may not be
possible to completely avoid collisions. For example, with the random allocation in Fig.
2: a, only nodes A and C are able to successfully transmit their uplink packets. Uplink
transmissions from all other nodes face either CS or HN collisions. Note that the
CS-Collision for the {B, D} combination affects only node B because of the relative
timing of the flames of the clusters. With the shown timing, node D’s slot always starts
before B’s, and as a result B detects a CS-Collision during the carrier sense at the

beginning of its allocated slot.

 

:l

3

I0
V

 

Cluster-1 CABCABCAB

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cluster-2 E F D E F D E F D

 

 

 

 

 

 

 

a) Random Allocation: HN-Collision due to {C, E} and {C.F} at the head
of Cluster-2; CS-Collision due to {8.0} at B

 

Cluster-1 CBACBACBA

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cluster-2 DFEDFEDFE

l

b) Optimal Allocation: HN-Collision due to {C.F} at Cluster-2 head;
CS-Collision due to { C. D} at C

 

 

 

 

 

 

 

Fig. 2.3: Example slot allocations for network in Fig. 2.2
In an optimal allocation (see Fig. 2.3 :b), the CS-Collision due to {B, D} combination

in Fig. 2.3:a has been removed. Also, the HN-Collision due to {C, E} combination in

29

Figure 2:a is removed at the expense of a new CS-Collision due to the allocation
combination {C,D}. Since HN-Collisions result in packet drops and CS-Collisions
result in increased delivery latency due to transmission deferments, it is possible to
trade better drop rates with larger delivery latency in a SRSA allocation paradigm.
Overall, the new allocation arrangement results in one less HN-Collision compared to
that in Fig. 2.3: a. This turns out to be one of the best allocations that can be achieved
for the network in question. The collisions here cannot be completely removed because
of the fact that C’s transmissions can be always be heard by the heads of both the

clusters.

 

Allocation Overlapping Slots to Node-pairs

 

Type in Neighbor Clusters
Collision Free {A,D}, {A,E}, {A,F},
{B,E} , {B,F}

 

CS-Collision {B,D}, {C,D}
HN-Collision {C,E} at E’s cluster head
{C,F} at F’s cluster head

 

 

 

 

 

Table 2.1: Allocation possibilities for the network in Fig. 2.2.

2.3.4 Frame Scaling for Collision Reduction

To reduce collisions in networks with nodes at cluster boundaries (e.g. the network in
Fig. 2.2), we introduce the concept of flame scaling, according to which the TDMA
flame duration is scaled up so that there are more slots in a flame than the traffic in that
cluster. The ratio of the number of available slots in a flame and the amount of traffic
(slots per flame) in a cluster is referred to as the Scaling Factor (SF). The motivation
for flame scaling is to introduce unused flee slots which can be used for alleviating both
CS and HN collisions during the allocation reorganization process. With scaling factor

2, a collision free slot allocation for the network on Fig. 2.2 is shown in Fig. 2.4.

30

Frame scaling has the following shortcomings. First, by inserting free slots, the
effective channel capacity of a cluster is reduced. Second, with increased flame
duration, the average packet delivery latency goes up.

Conceptually, flame scaling serves the same purpose as that of active-sleep cycles in
SMAC [16] and preamble sampling in [32, 33]. The flee slots in sealed flames extend
the sleep duration of a node at the expense of lowering the allowable loading range. In
effect, flame scaling decreases TDMA’s inherent duty cycle by the flame scaling factor
SF. Note that in our model, SF can be different in different clusters depending on the

nodes within that cluster. The flame lengths for all clusters are assumed to be the same.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Time _
Frame (SF = 2)
Cluster-1 A B C
Cluster-2 E F D
Collision-free \
allocation (SF = 2)
Free Slots

 

 

 

Fig. 2.4: Use of flame scaling for collision reduction

2.3.5 Allocation Reorganization Algorithm

For a given cluster, its future allocation schedule depends on its cmrent schedule, its
neighbors’ current schedules, scaling factor and the CS/HN collision rates. The
following mechanism is used by a cluster head for allocation reorganization mentioned
in Step 5 in Section 2.3.2.

gar-J: At the end of a flame, a cluster head examines .all the slots and mark their

status as one of F (Free), U (Uncontested: there was no collision detected for this slot),

31

C (CS-Collision detected) or H (HN-Collision detected).

M: For each H slot, the cluster head looks for an F slot and, if found, the H and F
slots are swapped between the previously allocated nodes.

M3 If for an H slot, an F slot is not found then the cluster head looks for a C slot
and, if found, the H and C slots are swapped between the previously allocated nodes.

W: If for an H slot, an F or a C slot is not found then the cluster head looks for a
U slot and, if found, the H and U slots are swapped between the previously allocated
nodes.

M1 For each un-swapped C slot, the cluster head looks for an F slot and, if found,
the C and F slots are swapped between the previously allocated nodes.

S_teL6: If for a C slot, an F slot is not found then the cluster head looks for a U slot
and, if found, the C and U slots are swapped between the previously allocated nodes.

SRSA initialization and end-of-flame execution logic is summarized in the Pseudo
code 1. Iterative and distributed execution of this protocol logic at the cluster heads
leads to a stable slot allocation with minimized HN and CS-Collisions. As mentioned
earlier, one of the main objectives of SRSA is to reduce HN-Collisions (for reducing
packet drops) more aggressively than the CS-Collisions, which are responsible for
packet delivery delay. This has been accomplished by first swapping the ‘H’ slots with
‘F’, ‘C’ and ‘U’ slots in that order, and then swapping the remaining ‘C’ slots with ‘F’
and ‘U’ slots. This way, removal of the I-lN-Collisions is given a higher priority.

Note that after exhausting the available ‘F’ slots, SRSA swaps the ‘H’ slots with

available ‘C’ slots. The rationale behind this step is to flee a slot from HN-Collision by

32

exposing it to CS-Collision. The anticipated result is to reduce the overall packet dr0p
rate (by reducing PIN-Collisions) at an expense of increased packet delivery latency (as
a result of increased CS-Collisions).

However, for the ‘C’ slots, the reverse (swapping it with ‘H’ slots) is not carried out;
this is because SRSA does not ever attempt to reduce CS-Collisions at the expense of
increased HN-Collisions.

Finally, both HN and CS collisions are attempted to be removed by swapping ‘H’ and
‘C’ slots with the ‘U’ slots. Intuitively this seems to be a disruptive process of
perturbing the already stabilized collision flee nodes. But depending on the topology,
often times it turns out that while removing the HN or CS-Collision, such a swap does
not expose the collision-flee node to a new collision. Even when it does, with sufl’icient
number of flee slots (‘F ’ slots) in the flame, as the protocol converges, eventually the
node becomes collision flee. Convergence characteristics of the protocol in such

situations are presented in Section 2.4.

33

 

 

/* SRSA protocol accented at each cluster head */
Initialize cluster schedule based on random allocation;

At the end of each SRSA/rame perform the following:
{

Process the CS-collision feedback received from the cluster nodes during this frame;
Identijy all slots in the frame with hidden collisions;
Mark slots as Free (F), Uncontested (ID, CS-Collision (C) and HIV-Collision (H)

For (all H slots) { // try removing the fflV-Collisions first
If (an F slot is available) {
swap H and F slots;

continue;
}

If (a C slot is available) {
swap H and C slots;
continue;

}

If (a U slot is available) {
swap H and U slots;
continue;

} // done with all IflV-Collisions; CS-Collisions next

For (all arr-swapped C slots) {

If (an F slot is available) {
swap C and F slots;
continue;

}

If (a U slot is available){
swap C and U slots;
continue;

}

} // done with CS-Collisions
} // schedule for the next frame is ready

 

Fig. 2.5: Pseudo code of SRSA protocol logic at each cluster head

34

 

2.3.6 Dimensioning Frame Scaling Factor

While being able to reduce collisions, the tradeoffs for higher SF are increased
latency and lower effective channel capacity. Therefore, it is necessary to dimension the
value of SF such that it is no larger than what is needed to guarantee zero collisions at
steady state.

For a static network with given topology, its critical scaling factor SF critical is
defined as the minimum SF at which there exists a zero-collision allocation
combination across all the clusters. It turns out that finding the value of SF critical in an
arbitrary network is NP hard. Therefore, in this work we compute the bounds for this
quantity.

For a given cluster i, we define the following parameters.

local: number of nodes that belong to cluster i

N :emote : Number of nodes that belong to other neighboring clusters and are
located within the overlapping region of cluster head i

N hflected : Number of nodes that belong to other neighboring clusters and are
located within the transmission range of all nodes in cluster i.

The concept and the defined quantities are illustrated in an example two-cluster
network in Fig. 2.5. Note that these definitions are general and hold for larger number
of overlapping clusters. Depending on the specific topology, in different clusters the
quantities low, , Niemm , and dflected may be different.

In the presence of cluster—overlapping, the minimum number of slots needed (for

. . , i i
zero collrsrons) for cluster 1 cannot be less than (N 10ml+ N remm ). Therefore, the

35

lower—bound of the critical scaling factor for cluster i can be computed as:
heal (I) (N 10ch + N remote +1)/ local
Note that the additional slot in the numerator is necessary to accommodate the
inter-cluster flame asynchrony, as illustrated in Figs. 2.3 and Fig 2.4. Similarly, the

minimum required slots for zero collisions cannot exceed (N [Zeal + N firmed). For a
given topology, this corresponds to the upper-bound of the critical scaling factor, which

can be computed as:

SFU‘tical (i): (Nlocal + Nafl'ected + 1)/1vlo

cal

These bounds provide a guideline for network-wide scaling factor dimensioning in a
multi-cluster network running SRSA. Consider a network with M clusters. Assuming
equal flame size across clusters, the bounds of SFcritical across the entire network are:

(Network): max(SFLB critical (1)) i = 1,2,3...,M

critical

crltica [=(NetW0rk) maX(SF critical(i)) i = I,2,3...,M

 

  
  

Affected
(shaded)

area by \
Cluster—1 '

Cluster-2

Cluster-1

 

 

ForCluster-1: Nlocal= 6, Nremote_ — 1 and Naffected= 4

 

Fig. 2.6: Parameters for Frame Scaling Factor dimensioning

36

LB UB LB
For the network in Fig- 2-6: SF critical (1) ’ SFhritical (1) 9 SPLritical(2) and
U3
SFcritical(2) are manually computed to be 1.33, 1.83, 1.33 and 1.66 respectively.
. LB UB
Therefore, the network-wrde values of SEW“, and SF'Icn'fic-a] are 1.33 and 1.83,
which are the maximum over both the clusters. For this network we have found the

required actual SFcritical to be 1.33 (same as the value of 5175;“, ). This was

experimentally found flom ideal allocation vectors which are established through a

brute force search across the entire allocation space for the network in Fig. 2.6.

 

 

 

 

 

 

 

 

 

 

 

    

 

 

 

 

 

 

 

 

 

 

 

 

0.1 p 0.025
0.09 . .. . . :Ideal
0.08 o 0.02 i . .
8 .. .
£0.07 a
E 0.06 .5 0.015
£0.05 g
{30.04 8 0.01
80.03 g
0.02 0.005
0.01 '
0 0
0.9 1.1 1.3 1.5 1.7 1.9 0,9 1,1 1,3 1,5 1,7 1,9
Scaling Factor Scaling Factor
3) CS-Collisions b) Packet drop rate

 

 

Fig. 2.7: Comparison between SRSA and ideal allocation
For situations when SF > SF critical, SRSA will converge to a stable state. The
convergence speed depends on network topology, SF, and the flafiic load. Collision
comparison between SRSA and the manually found ideal allocation for the network in
Fig. 2.6 is depicted in Fig. 2.7. As expected, after the scaling factor reaches SFcritical
(1.33), both CS and HN collisions are completely removed by the ideal allocation. Note
that the ideal allocation trades latency for lower packet drops. That is why its

CS-Collision (which is responsible for latency) is higher in Fig. 2.7 (a). To summarize,

37

this result demonstrates that for a small two—cluster network, the SRSA algorithm can
closely match the performance of an ideal slot allocation schedule. The performance of
SRSA in larger networks is presented in Section 2.4.

2.3.7 Protocol Convergence

Convergence and stability of the SRSA protocol can be analyzed using a discrete
time Markov chain as shown in Fig. 2.8. A state in this chain represents a combination
of slot allocation vectors across all the clusters. And the state identifier k is indicative of
the total number of collisions (both CS and HN) in the network as a result of those
allocation vectors. The system can be modeled as a memory-less Markov process
because the next allocation vector in SRSA depends only on the current collision state,
and is not related to previous allocations. In other words, the next system state depends
only on the current state. System state transitions are driven by the SRSA flame clock.

At any state with non-zero k, SRSA reacts on collision feedback and it forces the
allocation vectors to change. As a result, the system state changes. However, once the
system enters state-0, SRSA stops changing slot allocations because there are no
collisions. This corresponds to a converged stable change.

In the analysis in Section 2.3.6, we have observed that if the flame scaling factor is
larger than the parameter SF critical, then a collision-flee state (k=0) is guaranteed to
exist in the Markov chain in Fig. 2.8. Now, since by the definition of the SRSA protocol
syntax, there exists a non-zero transition probability flom state-i to state-j (i = I, 2, ...,
N; j = 0, I, N), the system is guaranteed to arrive at the absorbing state 0. Therefore,

SRSA will converge as long as the condition SF > SF critical is satisfied. Also, the total

38

time needed for the system to reach from an initial state to state-0 is the protocol

convergence time. With higher value of SF, faster convergence is expected.

A
$®A ______________

Absorbing SIBIGV

Fig. 2.8: Model to represent system state with SRSA

 

 

 

 

2.4 Performance Evaluation

SRSA has been simulated using a C-based even-driven sensor network simulator and
its performance have been compared with TDMA-over-CDMA (TDCD), TDMA with
random allocation (TDRN), and un-slotted l-persistent CSMA. CSMA is chosen to
represent the asynchronous MAC protocOls (such as 802.11) for which energy saving is
not possible by intermittent interface sleep or idling [16]. In TDRN, independent
random slot allocations are done in each cluster, as shown in Fig. 2.4: a. The protocol
TDRN can be viewed as SRSA without the iterative allocation reorganization part of it.
2.4.1 Experimental Parameters

We simulate a sensor field with 5 overlapping clusters as shown in Fig. 2.1. Clusters
have a radius of 50 m, the same as nodes’ transmission range. Each cluster contains 20
arbitrarily placed nodes, each of which can communicate directly with its cluster head.
The distance between adjacent cluster-heads is an experimental parameter for studying
the effects of cluster overlapping on SRSA performance. For this purpose, we define a
parameter, Cluster Overlapping Factor (C 0F) as l — (distance between cluster heads) /

(3 "‘ transmission range). With COF = 1, all 5 clusters in Figure 2.1 totally overlap, and

39

with C 0F = 0 (when the adjacent clusters are separated by three times node
transmission range), there is no overlapping between any two adjacent clusters. Unless
specified otherwise, we have chosen an inter-cluster distance of 70m, for which C 0F =
0.53 and the corresponding sensor field dimension is 240m x 240m.

Following the specification in [32], we choose a radio data rate of 25.6 Kbps and
fixed packet size of 128 bits (5ms), which is also the TDMA slot duration. Note that this
packet duration includes packet data time and carrier-sense duration. TDMA flame
duration is chosen as D+N*SF, where D is the number of slots allocated for downlink
transmissions, N is the number of nodes per cluster and SF is a chosen flame scaling
factor. For all the reported experiments we have chosen1 the value of D as 9. Unless
specified otherwise for all experiments we have chosen SF = 2 and N = 20.

As for data model, uplink packets are generated flom each sensor node following a
Poisson process with varying inter-packet time. We also generate download packets at a
constant rate which is enough to saturate the downlink slots.

2.4.2 Simulation Results

Throughput: Throughput for all four protocols with Scaling Factor (SF) = 2 and
Cluster Overlapping Factor (COF) = 0.53 are shown in Fig.2.8. TDCD
(TDMA-over-CDMA), being completely collision flee, can sustain a maximum load of
one packet per flame flom each node. With 20 uplink and 1 downlink slots per flame,
the flame duration is 105ms (21 x 5ms). So the maximum sustainable load is

approximately 9.5 packets/node/sec. Note that TDCD is able to achieve this high

 

' With K overlapping neighbor clusters, the minimum number of downlink slots for collision flee
downlink transmission is 2K + l (K = 4 for the network in Fig. 3.1).

40

throughput at the expense of wide-band operations (CDMA/FDMA) and high

cost/complexity of low-cost sensor nodes.

 

 

 

H
O
1
r

‘ —£—SRSA i

 
 
 
  

00
1
r

 

 

 

 

 

Througput (Packets/Node/ Sec)

 

01234567891011
Traffic Load (Packets/Node/ Sec)

 

 

 

Fig. 2.9: Throughput as a function of load

Although at steady state, the SRSA protocol does not face any collisions (see Fig.
2.10:a and 2.10:b) its throughput saturates at an earlier load (4.08 packets/node/sec) due
to flame scaling. For SRSA too, the maximum sustainable load is one packet per flame
flom each node. However, duration of the scaled flame for SRSA is 245ms (9 downlink
slots and 40 uplink slots with SF = 2). For TDRN, the flame size is exactly the same as
SRSA (i.e. TDRN was run with the same scaling factor of SRSA), but TDRN saturates
at a lower load (approximately 3.75 packets/node/sec) because of higher CS and HN
collisions as shown in Figs. 2.10:a and 2.10:b. Similarly for CSMA, flequent collisions
are responsible for its early throughput saturation at the rate of 3.74 packets/node/sec
approximately.

Collisions: CS-Collision rate is defined as the average number of transmission

41

attempts aborted due to contested medium, normalized by the successful packet
delivery count in a flame. Similarly, HN-Collision rate is computed as the ratio of
number of packets dropped due to hidden collisions to the successful packet delivery
count. As shown in Fig. 2.10, within the sustainable loading range, both the collisions
are almost eliminated for SRSA. Zero HN-Collision rate indicate zero packet drops and

zero CS-Collision rate leads to highly reduced (no queuing delay) packet delivery

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

latency.
"l
0.8 0.5
o 0.7 o
g 0.6 5 0.4
.505 .5 0.3
g 0.4 g
L?) 0.3 U? 0.2
8 0.2 g 0.1
0.1
0 0
0 1 2 3 4 0 1 2 3 4
Load (Pkts/Node/S) Load (Pkts/Node/S)
a) Impact of load on CS-Collisions b) Impact of load on packet drop

 

Fig. 2.10: CS and HN collisions as a function of load

These results indicate the effectiveness of SRSA’s feedback based slot reorganization
algorithm in the presence of flame scaling. The effects are particularly visible when
contrasted with the TDRN case in which flames are scaled and slots are randomly
allocated, but no adaptive reorganization is done for collision control. As expected, for
CSMA, both the collisions are higher than both SRSA and TDRN. For TDCD (not

shown), there are no collisions within the sustainable loading range of 9.5

42

packets/node/sec.

Algorithm Convergence: Convergence characteristics of SRSA on a five-cluster
network are plotted in Fig. 2.11. A scaling factor of 2 was used for this experiment. At a
load of 1.4 packets per second, with both active and passive CS-Collision detection
turned on (see Section 2.3.2), the allocation schedule converges after roughly 400
flames or 98 seconds. For the same set up, turning ofl‘ the passive detection causes the
CS-Collision to converge an order of magnitude slower, which is after 5000 flames or
1225 seconds. This clearly indicates the effectiveness of the passive detection
component of SRSA. While experimenting with different loading situations, it has been
observed that when an optimal allocation exists, SRSA finds it quicker at higher loads.
This fact is also evident in Fig. 2.10, in which both CS and EN collision rates have a
small non-zero value at lower loads (0.2 through 1 packets/node/sec); but then the
collisions are removed completely at higher loads. Better responsiveness of both active
and passive CS-Collision detection mechanism at higher loads explains this
observation.

In the in-band active detection process, a node informs its cluster head about an
experienced CS-Collision during the first successful uplink delivery after the collision.
At higher loads, the node gets such opportunities sooner compared to at lower loads. As
a result, active detection of collisions and their resolution are more effective at higher

loads.

43

 

 

 

     

 

 

 

 

 

o 12
5 10 CS-Collisions
“‘ 8
’6
9" 6
E 4 )lN-Collisions
o 0 1 i + ‘r
0 50 100 150 200 250 300 350 400
Frame Number

 

a) Collision convergence with both active and passive detection of CS-Collisions

 

 

 

 

 

8 ,
IE 6 CS-Collisions
g4 M...
I one
. 2
go I ll '/ L If % L7
0 1000 211210 301) 4111) 50(1)
FraneNurber

 

 

 

 

 

b) Collision convergence with only active CS—Collision detection

 

Fig. 2.11: Protocol convergence in SRSA

Scalabilig: Since the SRSA algorithm uses only local feedback to reallocate slots, it
scales well with increasing network size. Fig. 2.12 shows protocol convergence with
difl‘erent network sizes. Protocol convergence is depicted in terms of system wide
CS-Collisions, when both active and passive collision detections are used with a scaling
factor of 3. The first observation is that for 5-cluster case the system converges much
faster than that in Fig. 2.11. A higher SF value (3 as opposed to 2 in Fig. 2.11) is
responsible for this faster convergence. The second observation is that with larger
networlm (9 and 16 clusters) the protocol converges within reasonable time duration of
at most 150 SRSA flames. This experiment confirms that although it is little slower,
SRSA does converge for larger networks. We have found very similar behavior of

HN-Collision patterns with varying network size.

 

 

25

N
O

I 16 clusters

u—n
M

i 5 clusters
9 clusters

—-
O

CS_Collision Per Frame .

 

 

l 31 61 91 121
Frame Number

 

 

 

Fig. 2.12: Protocol convergence for varying network size

Coflion Distribtm: The spatial dish-ibution of collision rates is shown in Fig. 2.13.
For clarity, collisions for only the center cluster (see Fig. 2.1) are shown. The shown
area corresponds to a 100m x 100m square which contains the center circular cluster of
a radius of 50m. Each column represents the average packet drop rate (HN-Collision
rates) experienced by one of the 20 nodes in that cluster. Observe that for TDRN, the
nodes along the periphery, which are located in cluster-overlapped areas, experience
more packet drops compared to the nodes near the cluster center. This is because they
are more susceptible to HN-Collisions due to their relative location. This trend is
preserved even after SRSA’s allocation reorganization algorithm is able to significantly
reduce the overall drop rates. This particular experiment was run for a larger cluster
overlapping (COF = 0.66), which is why, unlike the last experiments, SRSA was not

able to completely remove the HN-Collisions.

45

 

Spatial Distribution of HN-Collisions in the Center Cluster

 

 

 

Packet Drop Rate with TDRN Packet Drop Rate with SRSA

 

Fig. 2.13: Spatial distribution of packet drops

I'M: For all evaluated protocols in TDMA family (TDCD, SRSA and TDRD),
the MAC latency has two components, namely, the queuing delay2 and a delay imposed
by the TDMA flaming itself. The latter is load independent and its average value is half
the flame duration. CSMA, being not a flame based protocol, does not have this
flame-latency overhead. As a result, as shown in Fig. 2.14, the latency for CSMA is the
lowest (1.2 slots) among all four protocols. The latency for CSMA increases marginally
with load, but it is not noticeable due to large linear scale in Fig. 2.14.

On the other hand, TDCD, with a flame size of 21 slots, has a flame-latency of 10.5
slots. Although there are no collisions for TDCD, with Poisson traffic there is slight
queuing which pushes the latency to a range 11.8 slots to 15.4 slots for the shown
loading conditions. SRSA has a larger frame size of 49 slots. Therefore its average

flame-latency is 24.5 slots. Additional queuing delay increases the latency further for

 

2 For all our experiments, we have used a fixed buffer size of 500 packets in each sensor node.

46

SRSA. For TDRN, the flame-latency is the same as SRSA because it also has 49 slot
flames. However, the queuing delay for TDRN is larger because of more CS-Collisions

(see Fig. 2.10) in the absence of allocation reorganization.

 

250

 

   

 

+SRSA -o—TDRN
+CSMA +TDCD

 

 

mg)
8

 

Latency (slot ti
3 8 8

A

A
A A A A A A
v v V V V V '

 

A A A A A A A
v V V'v V V V

 

 

 

 

l 2
Traffic Load (Packets/NoddSec)

 

Fig. 2.14: Packet delivery latency as a function of load
Enemy Eficz’engg: Energy performance for all four protocols with varying
inter-cluster distance is shown in Fig. 2.15. For these experiments we chose a load of
1.38 packets/node/sec. Energy consumption for a protocol is represented by the average
number of slots during which a transmitter and a receiver node have to remain active
for each successful packet delivery. For the inactive duration, nodes sleep to conserve

energy3. Larger node active times indicate higher energy consumption.
For all protocols except TDCD, the energy consumption increases with denser
cluster placements. CSMA shows the worst energy performance because all nodes have
to always remain active in order to receive asynchronous transmissions. On the other

hand, for TDMA family of protocols, all nodes except the cluster heads has to be active

 

3 We assume that a transmitter has to remain active only during 10% of a slot time to detect a
CS-Collision. If one is detected, the node can still sleep for the remaining 90% of the slot.

47

only during their respective allocated slots only if there is a packet to transmit. Energy
efficiency of TDMA based protocols is evident flom their order of magnitude energy

economy (see Fig. 2.15) compared to CSMA.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

250
I CSMA

200 W M

150
3 13
8
On
a
A.
0
.§
[—
D
.2
6
<2

0 0.2 0.4 0.6 0.8 1
Cluster Overlapping Factor

 

 

Fig. 2.15: Energy expenditure as node uptime
Due to the absence of any collisions, the energy drainage in TDCD is insensitive to
cluster overlapping. For SRSA and TDRN, both CS and HN collisions start increasing
for larger COFs (see Fig. 2.16). In closely overlapped clusters, in fact there are no
optimal allocations by SRSA that can achieve zero CS and HN collisions. In such
situations, SRSA attempts to minimize the HN—Collisions at the expense of additional
CS-Collisions. Energy wastage due to these collisions (see Fig. 2.10) accounts for the

increase in node active time for SRSA.

48

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0.7 ‘ . .
D
‘5
0.6 ‘ "‘
o 8‘
52' 0.5 - :6;
s: 8
.3 0.4 — 5;
=1 c:
(3 0.3 ~ .g
8 E
. o
0.2 L.)
0.1 — §
0 ‘ 0 :4. ¢ : h a. . r
0 0.2 0.4 0.6 0.8 0 02 0. 0.6 03
Cluster Overlappmg Factor Cluster Overlapping Factor
a) Impact of cluster b) Impact of cluster overlapping
overlapping on CS-Collisions on packet drop rates

 

 

 

Fig. 2.16: Collisions for different cluster overlapping

gm of Clu_.ger Overlapping: As evident flom Fig. 2.16, since SRSA suffers flom
lower collisions compared to TDRN, the former delivers little bit better energy
performance. Overall, as expected, SRSA’s energy performance is significantly better
than contention based protocols such as CSMA and is identical to that of TDCD for
COF up to 0.4. Beyond that, it increases by approximately 50% when the clusters are
almost completely overlapped. Finally, throughput reductions, for CSMA, TDRN and
SRSA protocols, due to increased collisions for higher cluster overlapping are shown in
Fig. 2.17.

Eflecps of Frame Scalmg: As shown in Fig. 2.18, for cluster overlapping factors
larger than 0.53, there are no slot allocations that can completely eliminate the HN and
CS Collisions for SF = 2. To eliminate collisions in closely overlapped clusters, SRSA

is required to use larger flame scaling factors. Fig. 2.18 depicts the rate of both types of

49

collisions with changing overlapping factor for SF = 2, 3, 4 and 5. For example, while
the maximum sustainable (zero collisions) overlapping factor is 0.533 with SF = 2, it
can be extended to 0.6 with SF = 3, 0.66 with SF = 4, and 0.733 with SF = 5. For higher
values of SF, more flee slots are introduced in the TDMA flame. As a result, the SRSA
slot reorganization algorithm is given more flexibility to remove collisions by
swapping the collision slots with those flee slots.

Note that the tradeoffs for higher SF are increased latency and lower effective
channel capacity. Conceptually, flame scaling serves the same purpose as that of
active-sleep cycles in SMAC [l6] and preamble sampling [32, 33], but in the context of
reducing inter-cluster MAC interference. The flee slots in sealed flames extend the

effective sleep duration of a node at the expense of lowering allowable traffic loading

 

 

  

 

  
 

 

 

 

 

 

 

 

 

range.

1.4 T
g 1.3 ~~
Q
0
'8
E; 1.2 .-
.3.
EL
33. 1.1 -- ;
g? +SRSA
8 —o—TDRN
E 1 fl +CSMA

—o—TDCD
0.9 l .1 l t .
0 0.2 0.4 0.6 0.8 1
Cluster Overlapping Factor

 

Fig. 2.17: Throughput with varying cluster overlapping

50

 

 

 

 

U)

 

 

O
N
M
r
(A
'1']
H
W

 

 

O
N
1
+
Cl)
'1']
‘II
VI

 

 

  
 

HN-Collision Rate
.o 3
~— u:

 

 

 

 

 

0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8
COF COF

a) Impact of SF on CS—Collisions b) Impact of SF on packet drop rate

 

 

 

 

 

 

Fig. 2.18: Effects of flame scaling on collisions in SRSA

Effects of Mobility: The effects of limited node mobility on the SRSA protocol
performance are shown in Fig. 2.19. In addition to the regular 100 static nodes, 5
mobile sensor nodes are added in the sensor field in Fig. 2.1. Mobility for those nodes is
implemented based on random way-point model, according to which a node randomly
chooses a destination and moves towards it with a constant speed (2 m/sec). The degree
of mobility is controlled by varying the interval between movements normalized by
flame duration. Cluster overlapping factor, traffic load and scaling factors are kept
same as those used previously.

When a mobile node moves across clusters, the old cluster de-allocates its slot, and
the new cluster allocates it a slot flom its pool of flee slots. These new allocations give
rise to temporary inter-cluster CS and HN collisions. As evident flom Fig. 2.19, with
longer intervals between moves, the allocation reorganization mechanism of SRSA can
limit these collisions to a great extent. However, with very short intervals, the mobile

nodes move more frequently than the convergence time constant of SRSA. As a result,

51

the collisions are higher. As the interval between moves increases to very large values,
it is expected that collisions will converge to zero. In efl‘ect, limited node mobility

introduces random perturbation, which increases the convergence time of SRSA.

 

 

 

0-011 + CS-CoIlision ‘ " l

_, ,+. . - , 19’5“”??? <_ ..

 
 

 

 

 

 

0.007 -

ollision Rate

0.005 i
O

0.003 ‘

 

 

 

0.001
0 200 400 600 800 1000
Interval between moves (Frames)

 

 

 

Fig. 2.19: Effects of mobility on Collisions in SRSA

However, the absolute collision rates are quite small. With no pause between moves,
the drop rate (HN-Collision) is less than 0.5% and the CS-Collision rate is less than
1.2%. These numbers should be compared with the complete static scenario, in which
both collisions are nonexistent for SRSA (see Fig. 2.9). Based on the low CS-Collision
and drop numbers, we conclude that SRSA scales well for networks with moderate
mobility for a small flaction of the sensor nodes.

Overall Comparison: From performance summary in Table 2, it is evident that
because of its largest energy overhead, CSMA cannot be used for energy-constrained
sensor nodes. Among the TDMA based protocols, although TDCD is the best

performing but its dependency on CDMA (or FDMA) makes it prohibitive for

52

narrow-band operations with cost-constrained sensor nodes.

Between SRSA and TDRN, SRSA is a better choice because of its smaller packet
drop rates and lower delivery latency (see Fig. 2.9). In fact, for low traffic loads (which
is the case for many monitoring based sensor applications) and moderate cluster
overlapping, SRSA can completely eliminate packet dr0ps at the expense of additional
latency, which is the only trade-off for this protocol. As a result, SRSA makes an
excellent medium access strategy in sensor network applications that can tolerate

relatively larger delay but not flequent packet drops.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Narrow-band Cost, Through- Packet Latency Energy
Operation Complexity put Drop Rate Usage
TDCD No @h High VeryLow Low Low
SRSA Yes Low Med. Very Low Med. Low
TDRN Yes Low Med. Med. Med. Low
CSMA Yes Low Med. High Low High ’
Table 2.2: Overall performance summary
2.5 Summary

In this work, we have proposed and evaluated a Self-Reorganizing Slot Allocation
(SRSA) mechanism for TDMA based Medium Access Control (MAC) in wireless
sensor networks. SRSA uses a feedback based local allocation reorganization that can
be used for minimizing allocation interference across overlapping sensor clusters in a
single channel network. One major advantage of SRSA protocol is that it does not
require any global or neighborhood synchronization, making it feasible in very large
sensor networks. For moderately dense clusters, SRSA uses a novel flame scaling
technique for achieving lower packet drops by reducing the maximum allowable

system loading. Comparative evaluation shows that like plain TDMA protocols, SRSA

53

has an order of magnitude lower energy overhead compared to CSMA and other
contention based protocols. The trade-off for very low energy dissipation and packet
drop rate is increased transmission latency. Because of its independence flom wideband
techniques such as CDMA or FDMA, SRSA offers a cost-effective solution for
complexity-constrained sensor hardware. To summarize, SRSA makes an ideal
medium access strategy in sensor network applications that can tolerate relatively
larger delay but not flequent packet drops. Ongoing work on SRSA includes extending
the protocol analysis, as outlined in Section 2.3.7, for analytically estimating the
convergence speed. Computing the convergence speed according to this model will
involve the following. First compute the steady state probability of finding the system
in any state-i for all i 76 0. Then evaluate the average number of transitions required
flom any state-i to state-0 and then compute the expected value over all for all i 36 0.
And we have assumed a reliable TDMA schedule transfer mechanism flom cluster
heads to individual sensor nodes. The impacts of errors in such schedule transfer need
be investigated. Effects of variable node density across clusters and their effects on

variable cluster-specific Scaling Factors (SF) are also being investigated.

54

Chapter 3
Scalable Routing for Very Large Sensor Network

This chapter presents an architectural solution to address the problem of scalable
routing in very large sensor networks. The control complexities of the existing sensor
routing protocols, both node-centric and data-centric, do not scale very well for large
networks with potentially hundreds of thousands of embedded sensor devices. We
develop a routing solution Off-Network Control Processing (ONCP) that achieves
control scalability in large sensor networks by shifting a certain amount of routing
functions to an “off-network” server. A tiered and hybrid routing approach, consisting
of “coarse grain” server based global routing, and distributed “fine grain” local routing
is proposed for achieving scalability by avoiding the network-wide control message
dissemination.

Section 3.1 describes the related routing protocols for wireless sensor networks. In
Section 3.2, we discuss the motivations and problems for scalable routing protocols.
We present the network and application model in Section 3.3. In Section 3.4, we discuss
the details of the ONCP routing architecture.

3.1 Related Work on Sensor Routing Protocols

Compared with wireless ad-hoc networks, routing protocols in sensor networks are
particularly challenging due to several unique of its characteristics. (1) It is not possible
to build or organize the global addressing for a large number of sensor nodes. Thus
classical IP-based protocols cannot be directly applied to sensor networks. (2) Unlike

the typical multiple to multiple communication traffic models, sensor networks

55

generally require the data flow flom multiple sources to one (or few) data sink. (3) The
generated data has significant redundancy since multiple sensors may generate the
similar data within the vicinity of a common phenomenon. These data needs to be
processed in-network by the routing protocols in order to improve energy efficiency
and bandwidth utilization. (4) The sensor networks comprise a large number of
unattended nodes. Depending on specific applications, the network size may be
thousands or even up to hundreds of thousands. Scalability in routing protocol is a
challenging problem in such large networks. (5) The sensor nodes are tightly
constrained in terms of processing and storage capacity, on-board energy supply,
wireless communication capacity, etc. All these need to be considered in the protocol
design.

Many new routing algorithms have been proposed for sensor networks. These
mechanisms have considered the characteristics of sensor nodes outlined above, along
with the application and architectural requirements. Generally, the routing protocols
can be categorized into flat, hierarchical and geographical routing protocols. Most flat
protocols are data-centric, in which the routing algorithms rely on the naming of data.
The naming mechanisms help to reduce data redundancy. Hierarchical protocols allow
only a small set of nodes to participate in routing path discovery and perform data
aggregation by organizing nodes in groups and assigning different functionalities.
Geographical protocols use the node position information to relay the data rather than
flooding routing discovery messages to the whole network. In this section, we will

mainly discuss these three classes of routing protocols for wireless sensor networks.

56

3.1.1 Flat Sensor Routing Protocols

In Directed Diflhsion [3 8], the sink nodes disseminate network—wide sensing
interests for the target sensor nodes. The intermediate nodes propagate interests to
establish routing gradients. When the sink nodes receive exploratory data flom target
nodes, they eventually reinforce one or multiple gradients along the reverse paths for
steady data collection. The energy benefits of Directed Diffusion come flom
in-network data processing and empirically selecting desirable paths. However, the
protocol suffers flom severe scalability issues caused by the network-wide interest and
exploratory data disseminations during the route set up phase. With flequently
changing and/or short-lived sensing tasks, the control congestion and energy penalties
make this protocol not scale for large sensor networks.

Gradient-Based Routing (GBR) [54], Energy Aware Routing [55] and COUGAR [3]
are three other flat routing approaches. GBR and Energy Aware Routing employ
different optimization techniques flom Directed Diffusion. GBR utilizes the
information of hop counts when the interest is disseminated through the network. And
Energy Aware Routing maintains and chooses paths by a certain probability to optimize
energy usage. COUGAR regards the network as a distributed database system. It uses
declarative queries to abstract query processing flom the network layer functions such
as selection of relevant sensors as lead nodes to perform aggregation and transmission.
All these flat approaches suffer flom the problem of network-wide route searching. In
large networks, the overheads of routing discovery will overwhelm their optimization

techniques.

57

3.1.2 Hierarchical Sensor Routing Protocols

LEACH [5], one of the first hierarchical sensor routing algorithms, proposes to
organize nodes into clusters, and only use cluster-heads to communicate directly with
base stations. Cluster-heads are periodically rotated in order to balance the energy
dissipation. LEACH is completely distributed and its major benefits come flom data
fusion at the cluster-heads. The primary shortcoming of LEACH architecture is its
assumption that each sensor node is able to make single-hop transmissions to the base
stations. For large networks with distant base stations, this will require prohibitively
large transmission power which may be impractical for tiny sensor nodes with
energy-limited transceivers.

PEGASIS [56] is an enhancement over LEACH protocol. In order to extend network
lifetime, nodes need to only communicate with their closest neighbors and they take
turns in communicating with the base-stations. This reduces the power required to
transmit data per round as the power draining is spread uniformly over all nodes. The
main drawback of PEGASIS is that it still needs direct nodal communication to base
stations.

HPAR [57] is a hierarchical power-aware routing protocol. Groups of nodes are
organized together as a zone and treated as an entity in routing. Each zone uses
max-min algorithm to decide how to route a message hierarchically across neighbor
zones such that network life is maximized. Hierarchical protocols help to alleviate the
problem of routing flooding messages by only allowing higher layer hierarchy to

participate in routing path establishment. Yet they still can not avoid network-wide

58

searching, which can be severely expensive in large networks. And the overheads for
establishing network hierarchy also restrict their efficiency.
3.1.3 Geographic Sensor Routing Protocols

The routing protocol GEAR [41] partially addresses the interest flooding problem of
Directed Diflusion by geographically routing the interests towards the source nodes
specified by the data attributes in interest packets. The key routing idea for a node is to
always forward interest packets to its neighbors closer to the physical location of the
source nodes. When this basic forwarding fails due to the fact that the forwarding node
itself is the geographically closest but not within the radio range of the source region, in
GEAR the interest packets are forwarded using cost based detour mechanisms.

Other geographical routing protocols such as GPSR [42] and GOAFR [43] follow
similar routing philosophies, but differ in the detour search process. While these
geographical routing protocols provide better control message complexity than
Directed Diffusion, the assumption of complete node localization makes them less
feasible for localization-denied sensor fields. Also, in the event of flequent detour
searches, the additional control overhead lessens the relative advantages of these
protocols over Directed Diffusion. Frequent detour searches may be caused by irregular
terrains and other security based partitioning.

Another family of energy aware routing protocols [49, 50, 51] is proposed to
compute the optimal routing schemes that maximize the life time of networks. These
are formulated as a class of optimization problem and heuristics are applied to select

energy-efficient routes in a distributed manner. The primary limitation of these

59

approaches is that they require prior knowledge of the source and destination sensor
pairs and the exact traffrc pattern.
3.2 Routing Scalability: Motivation and Problem Description

Wireless sensor networking is an emerging enabling technology for a wide range of
embedded applications such as large scale environmental monitoring, intrusion
detection, and collaborative disaster management. The sensor population for such
applications can often be very large due to the expanse of the targeted sensor fields and
the limited sensing and radio range of the sensor nodes. For example, the networks used
for environmental monitoring are likely to be deployed over tens of square miles of
target area comprising of potentially hundreds of thousands sensor nodes.

We focus on a major design constraint for very large sensor networks: routing
scalability. To establish routes, protocols generally incur network wide control message
flooding. For traditional node-centric routing, routing messages are generated primarily
for topology discovery in link-state protocols such as OLSR [39], and for route
discovery in distance-vector protocols such as AODV [40]. In data-centric protocols
such as Directed Diffusion [3 8], the control message complexity manifests in the form
of network wide interest and exploratory data propagation during the routing discovery
process. For flequent and short-lived sensing tasks, the control overhead can be
overwhelming in very large sensor networks (VLSN). High control overhead can have
a series of adverse effects including high packet drop rate, increased latency, and
reduced effective network bandwidth. A more detrimental effect is the increased energy

overhead on the resource constrained sensor nodes.

60

To address this problem, we prOpose an architectural solution by developing an
Off-Network Control Processing (ONCP) flamework for Very Large Sensor
Networks. The key idea is to shift a significant amount of routing functionality
“off-network” to an energy-unlimited server. This server performs “coarse grain”
global route computation, while the “fine grain” local routes are discovered solely by
local sensor nodes. This partially server-based approach allows eliminating the control
messages that otherwise are needed for distributed global route establishment. The
reduction of routing control messages by the ONCP server ensures routing scalability in
large networks.

3.3 Network and Application Model

As depicted in Fig. 3.1, our network model consists of multiple base stations which
act as data sinks. The base stations are connected to an Off-Network Control Processing
(ONCP) server through a low-latency wired network, which is used for network status
update to the ONCP server, and for global route download flom the ONCP to the sensor
network.

As for the application model, each user is connected to the ONCP server through a
client that generates asynchronous sensing task requests with specific geographical or
other attributes. It is envisioned that a user client will include a Graphical User Interface
(GUI) that renders a terrain map of the sensor field with environmental features such as
vegetation, mountains, water bodies, and other similar landmarks. A user will first
identify a target sensing area through the client GUI and then generate sensing task

requests to the ONCP server. For example, a user may select a certain part of a

61

vegetation area as the target sensing zone, and then deliver a sensing task request to
measure the soil pH level at a regular interval of six hours and for duration of thirty
days. Based on their target sensing areas, the task requests are routed to the appropriate
sensor nodes. Note that a user does not address or specify the sensor nodes and

therefore, no individual sensor level information is made available to the users.

 

     
 

User-1 User-2 User-n

ONCP . ‘ I

.-.r ‘."'j.-‘.z.‘.'.‘..~:o.-. . :1 9.1:”. p.13; 9:557.“ Ar ' {‘23}, H-f‘f-K if, 74:2:fls1..»,_‘,.‘ Lu
59?” Off Work cartoon “ pm “ ” ~' 9.9 '

Data/Events Commands

 

 

 

 

Base Sensors Field fl : 35’3
Station-1 5k

 

 

 

 

 

 

 

 

 

 

 

Fig. 3.1: Network and application model

3.4 Off-Network Control Processing (ONCP) Routing Architecture

ONCP is a hybrid architecture in which the routing decisions are made at two levels.
Contrary to the traditional hierarchical sensor routing protocols [30], the global path
selection in ONCP is performed solely in a centralized server, which does not require
network-wide route search. And the local routing messages are constrained only locally.
For large networks, this hybrid route discovery mechanism achieves excellent control
plane scalability compared to the flat and hierarchical protocols described in Section

3.1.

62

As shown in Fig. 3.2, the global routes are computed by the ONCP server at the level
of pre-configured regions. When a user client generates a sensing task to certain sensors
in a target source region, the ONCP server computes an energy—optimal global route
flom the target source region to an appropriate base station. Such a coarse-grain global
route is represented by specifying a sequence of regions fl'om the target source region to
the chosen base station. To realize this region level route, each region on the route
maintains a next-region routing entry for each individual sensing task.

At the lower tier, ONCP implements a fine-grain reactive local routing protocol that
provides physical routing paths at node level across adjacent regions. The local routes
are established in a completely local and distributed manner. A clustering abstraction

has been also used for achieving scalability for the local routing.

 

 

1
Region 1A A Global Routes ‘

I ' ....... . ......... é)°/‘\ A;
A A kc"
‘ A

;/:'-\"J’:\/€‘ - / A -

7
féR‘egions: Al\‘ ‘ gRegionAB
V

-A Region 4 Regiox 7

 

Region B/r—A<q 9 Region6 i A ReiionQ
9 3
A

 

 

.......................o‘ I
- f‘ u ‘ ‘5
‘- ............ u...‘ .......... .Q ...... F/"H ............... y

 

 

 

 

 

 

 

- Cluster Head (CH) ‘ Sensor Node

 

Fig. 3.2: Tiered concept of ONCP routing

A sensing task request from each user-client (Fig. 3.1, 3.2) is source routed (at the

63

region-level global route) to the target region (or regions when the target sensing area
spans multiple regions). Once the target source sensors receive the request, they start
generating and sending data at the specified rate to the chosen base station using the
global and local routing mechanisms outlined above.

Although the ONCP architecture does not perform network-wide message flooding
in its routing process, it does require periodic network status updates flom each region.
Therefore the benefits of the ONCP approach can be sustained only when the overhead
of network status update is lower than the control overhead of route message flooding
in other competing flat and hierarchical routing approaches.

3.4.1 Region Management

Regions are pre-configured based on administrative or security boundaries, or
specific topographical features of the terrain. At its deployment time, a sensor node is
assigned a region-id which does not change during the lifetime of the node. While this
way of region marking adds management and operational burdens at installation time, it
does allow the proposed ONCP routing mechanism in localization-denied
environments. It should be noted that although the id of a region may be correlated. with
its geographical location (although not necessarily), an individual node is not aware of
its location information, and therefore the proposed ONCP flamework cannot be
categorized as geographical routing protocols like GEAR [41] and GPSR [42].

Dynamic attributes of regions include its aggregated nodal energy level and the
connectivity metric between adjacent regions. The aggregated nodal energy metric is

the sum of remaining energy of all nodes in that region. If the aggregated remaining

64

energy of a region is low, then it is desirable to avoid that region when choosing a

 

 

global path.
- ....................................... ., ......................................
1001 5 1001
A- _______ 2
‘ karrr-“P A A
. [’2 \\ I l
3‘ .5 501 ‘ -
‘ \ 80 1 ’1".
‘ \‘ I’ .
k’ e 1001 A A
A ‘4 E A
901 § 801 A
I I ,AZZ“E‘~~I
3 , 901 A ' A
A’ a, ,
A ‘ 1001 [If \, l ‘
'1’ E 901’
‘ l' “?::*~\.
A ‘ A 60", ’f “' A
I i
I
- ....................................... 1; ..................................... -
Region S Region D
I Cluster Head A Cluster Member

 

 

Fig. 3.3: Example region-to-region connectivity metric

The connectivity metric between two regions is defined as the sum of the remaining
energies of all the border nodes that have direct connectivity with the nodes in the
neighbor region. Fig. 3.3 shows an example connectivity information between border
nodes in region S and region D. The connectivity flom region S to region D is (100 + 80
+ 90 +100 + 60) = 430 J, and flom region D to region S is (100 + 50 +100 + 80 + 90 +
90) = 510 J. In the above example, if the connectivity metric between region S and
region D exhibits a small value, it means there is little energy left at the border nodes
that connect those two regions. In that case, while computing a global route the ONCP
server should avoid the S-D and D-S region sequence on the global route. From each

region, the information about its aggregated remaining energy and the connectivity

65

indices with its adjacent regions are periodically uploaded to the ONCP server. From
the global routing perspective, the base stations are also treated as regions, except that
they are assumed to be non energy-constrained.

The motivation behind the region level energy and connectivity abstraction is to
avoid node-level information, which would be extensively expensive and inaccurate. It
is important to note that the concept of region does not fully describe nodal connectivity
features within regions such as voids. Lack of these nodal characteristic results flom the
usage of only aggregated information. However, this problem can be partially
addressed by careful pre-configuration of regions and status updates.

The dimensioning of region size is an important parameter. With smaller region sizes,
the ONCP flamework can achieve finer control granularity for global routing and the
less overhead for local routing, as fewer nodes are involved. On the other side, the
adverse effects of imprecise region information will increase due to reduced node
redundancy. The general guide line is to localize the impact of node dynamics within
regions so that the global routing paths remain stable. The tradeoff of region size is
analyzed and evaluated in the following section 3.5.

3.4.2 Cluster Organization

The concept of sensor clustering has been added to ONCP for implementing a
scalable local routing protocol. The clusters are also used for aggregating network
status information (region energy and inter-region connectivity) before uploading them
to the ONCP server. The layer of clustering is transparent to region management and

the global routing path selection. Neither nodal information nor cluster information is

66

available to ONCP server; this ensures the scalability in the global routing path
selection.

Clusters are generally much smaller than the regions, and they are dynamically
created and maintained in a manner that is independent of the regions. While a cluster is
usually contained within a region, it is possible for clusters near region borders to span
across multiple regions. In such overlapping situations, a cluster is regarded to belong
to the region in which the head of the cluster resides.

Each sensor node has clustering status as one of cluster-head, follower (i.e.
cluster-member), or undecided, and needs to exchange energy status periodically to
rotate the cluster—heads. We have implemented the similar clustering mechanism
described in [5] for creation and maintenance of clusters with one cluster-head per
cluster. As explained in Section 3.4.6, since the local routing is executed primarily
through the cluster-head nodes, they are more likely to run out of energy sooner than the
follower nodes. To prevent network meltdown caused by early failures of the
cluster-heads, we implement a cluster-head rotation [5] strategy in which the clusters
are dynamically reconfigured for distributing the energy burden of cluster-heads among
all the sensor nodes. This is accomplished by energy-based triggering of the follower
nodes to enter into cluster-head competition with their existing cluster-heads. The
major difference between our approach and most common clustering algorithm is that
two information exchange flequencies are adopted to manage the cluster organization
overhead. Before a sensor node joins a cluster as a cluster-head or a regular

cluster-member, it uses a high flequency information exchange to trigger cluster

67

organization; after the clustering is stabilized, it reduces the information exchange
flequency during the cluster maintenance.
3.4.3 Status Updates

The ONCP server needs to be aware of the regions’ aggregated energy attributes and
the inter-region connectivity metrics for the off-network global routing computation.
Each region maintains a designated region representative which updates the ONCP
server with the described region level information. Sensor nodes periodically send
region id, remaining energy, and connectivity information (nodes in adjacent regions)
to their cluster-head. The cluster-heads aggregate all such information flom its
members and report to their region representatives. Then the region representatives
send status updates to the ONCP server. The update information flom a region
representative includes the id of region which the reporting region representative
belongs to, the aggregated nodal energy, and the aggregated connectivity metric as
defined in Section 3.4.1. In order to differentiate updates flom multiple region
representatives, the ID of region representatives and update sequences are also
included.

The choice of region representatives can be instructed at node deployment time by
the network operator or self-selected by sensor nodes. In this work, as the main concern
is routing scalability, it is assumed that region representatives are selected by network
operator. And when representatives were out of service due to node failure, the network
operator should reselect one for the corresponding regions. Low maintenance spanning

trees, rooted at the base stations and spanning across the region representatives, are

68

used for region level status update.

The updated status information flom region representatives is maintained as soft
state on the ONCP server. They will time out to reflect the region information change,
unless refleshed by region representatives. The state complexity of updates is at the
order of the region number. Compared with the network size, the number of regions is
significantly smaller. Status updates can also implicitly solve parts of the “node voids”
problem as mentioned in Section 3.4.1. Consider the following scenario: outsider
attack or natural catastrophe destroy a portion of sensor nodes within a region, such that
that region is partitioned into two parts. As the region representative can only collect
information of nodes on its part, the ONCP server does not have knowledge of the
inaccessible part for that region. In terms of global routing, this information hidden
avoids choosing a “broken” path.

3.4.4 Global Routing

The global route computation at the off-network ONCP server relies on the
aggregated region energy information and the inter-region connectivity metric as
defined in Section 3.4.1. Based on this information, the ONCP server abstracts a
directed graph G, in which the vertices represent the regions (including the base
stations), and the edges represent the connectivity between regions. The edge value in
G is defined as the corresponding inter-region connectivity metrics and the vertex value
is defines as the aggregated nodal energy of the corresponding region.

From the applications’ perspective, it does not matter as flom which base station the

sensed data are collected. Therefore, for a given sensing task request, the global route

69

construction process can be separated into two parts: (i) choose one of the base stations
as the destination, and (ii) select the route flom the target sensing region to the base
station chosen in part 1. As the number of base stations is limited and known, the
routing process can be reduced to first computing the optimal path with each base
station as the destination, and then selecting the best one based on the energy and the
other criteria as follows.

Computing a global path is defined as finding a path flom a target data source region
(vertex) on the graph G to a given base station (vertex) so that (i) the end to end energy
consumption is minimized, and (ii) the energy loads on regions should be evenly
distributed for avoiding traffic hot-spots at the region level. While the first objective
minimizes the overall energy consumption, the second one helps extending the network
life by avoiding any early energy exhaustion due to excessive traffic concentration.
End-to-end energy consumption can be minimized using a min-hop routing, and the
load distribution can be accomplished by a MaxMin [47] routing in which the route
flom a source vertex to a base station vertex in graph G is chosen such that the
remaining energy on the minimum-energy vertex on the route is maximized.

Considering that Min-hop and MaxMin are two conflicting requirements, and the
NP-hardness of solving such optimization problem [47], we rely on a heuristics-based
route search algorithm as described in Pseudo code 2.

Additionally, to avoid the overuse of the inter-region links with low connectivity
metrics, the weak edges is purged flom G before searching the best feasible route. If

any of the links on the route has a connectivity metric value lower than a pre-defmed

70

threshold then that link is removed.

 

/* ON CP Global Routing Path Computation at the server*/
Region level Graph G Construction:

For (each status update entry stored in the server) {
If ( (current_time - the updatefs time of origination) >
update_interval x allowed_loss) { // entry too old
Remove this status update;
}
Else {

Add the contained region (vertices) and connectivity (edges) into G;

}

}
For (each edge in graph G) {
If (edge__cost < E_threshold) {
Remove the edge and the corresponding reverse edge from G;

} //purge weak edges flom the basic graph

Global Path Selection:
For (each base station j) {

Find a set S j of paths from the target region to the base station j,

on which the minimal energy of vertex is the highest;

Identify the shortest path P}. from the set S J. ,'

Pj ts the chosen path from the target region to the base station];

Base Station Selection:
From all paths Pj, choose the path P. on which the minimum energy
is the highest (MN);
If there are multiple such paths, choose the shortest one;
// Now the chosen base station for this sensing task is ‘k ’.
// with P. as the chosen global path for this sensing task

 

 

 

Fig. 3.4: Pseudo code of ONCP global path computation

71

3.4.5 Command & Global Routing Forwarding

Global route flom a region to a base station is computed when a user client generates
a sensing task request with a target sensing area within that region. After a global route
is computed at the ONCP server, the sensing command / request is sent to the targeted
region (flom the chosen base station) along the computed global route, but in the
reverse order. A region-level source routing approach is adopted for sending the request.

It is described as follows:

 

/* Command Propagation */

ONCP server forwards command to a chosen base station;
// the command includes the computed global route from
// the target region to the base station in the form of a region_list

The base station records the command, and forwards it to all its neighbor cluster-heads
When a cluster-head receives a command:

If (it had received the command before) {
Discard command; //duplicate reception;
} else if (cluster-head .’s region id is in the region_list) {
// cluster-head is on the global route
From the command, cluster-head records the global route;
Cluster—head forwards the command to all its neighbor cluster-heads
} else {
// the packet has arrived at a region that is not on the global route
Discard the command

 

 

 

Fig. 3.5: Pseudo code of command & global routing forwarding
The computed global route information is also included within the command /
request packet so that while propagating a request to the target region, the regions along

the route can note the global route from the command. As a result, after the sensing

72

request reaches the target region, all relevant regions along the route become aware of
the appropriate next-region pointer to reach an appropriate base station. Once the route
information arrives at a region, it is disseminated to all the cluster heads in that region.
Note that when the target sensing area spans multiple regions, one request-and-route
download is performed for each of the target regions for that area.
3.4.6 In-network Local Routing

While the region level global paths are computed and specified by the ONCP server,
the local paths across adjacent regions on such global paths are discovered in-network
by the sensor nodes. The in-network local routing is a reactive mechanism. When a
node receives data to be forwarded to the next region on the global path, but it does not

have a local route to the next region, a local route discovery process is invoked.

 

 

 

 

 

 

 

 

 

 

/' \ / '
cluster-heads flood A j ’ A
Requests to ‘ A ‘ ‘
neighbor cluster- i ‘ .
heads A“ \‘N A
‘ "’-
originating region (3) next region (D) ‘
- Cluster Head (CH) (a) ln-Region Local Request
A Sensor Node
........... \ / .
cluster-heads send A ‘x f .... A
Route Replies to ‘ A V‘\ . ‘
source through Selected path -
reverse paths A‘” -\‘ - A
A
originating region (S) "n\ext region (D) A
(b) ln-Region Local Reply

 

Fig. 3.6: Local routing in ONCP architecture

A clustering hierarchy is added to implement scalability to the local routing protocol

73

 

 

 

as described in Section 3.4.2. The local routing in ONCP works strictly at the level of
the clusters. As a result, a local route discovery is always originated and terminated at
cluster-heads.

Local Route Discovery Protocol: To discover a local route flom region-1 to its
adjacent next region-2 on the global path, a Local Route Request (LRQ) message is
originated flom a cluster head and propagated with the originating cluster-head ID, ID
of the originating region (region-l), ID of the next region (region-2), and a hop-count
indicating the number of clusters-heads the LRQ packet has traversed so far. When a
cluster-head receives an LRQ that is originated in its own region, the cluster-head
increments the hop-count value and re-floods the message to its neighbor cluster-heads.
If LRQ message reaches a region that is not the originating region or the next region,
this message is discarded. If the cluster-head finds that the message has arrived at the
desired next region (region-2 in this case), the recipient cluster—head replies using a
Local Route Reply (LRP) message, which is forwarded back to the originating
cluster-head along the reverse path set up during the LRQ dissemination process. The
process of local route establishment from region-1 to region-2 is summarized in Fig.
3.4.

Unlike in AODV [40], a single LRQ can be responded to by multiple cluster-heads in
the target next region. As a result, multiple simultaneous local routes can be established
and maintained in ONCP local routing. An energy based MaxMin policy is applied to
choose the best route dming the process of local route discovery. This way, the local

route will avoid using sensor nodes that are already low in energy. An AODV style

74

sequence number is adopted for avoiding loops during the local route establishment

process.

75

Chapter 4
Protocol Overhead Analysis
In this chapter, we analyze the scalability of three classes of routing protocols which
is characterized by the total amount of transmissions needed in the network for
delivering per unit of user data. This analysis does not attempt to model or compare
specific routing protocols; it should be interpreted more as architectural and relative
trend analysis of different routing architectures. We build numerical models to establish
scalability of ONCP protocol, in comparison with flat and hierarchical cluster-based
protocols.
4.1 Notations and Definitions
Consider that N nodes are uniformly deployed in a square sensing field, with a base
station at its center. Sensing requests to arbitrarily chosen target sensor nodes are
generated flom the base station. The system parameters are as follows:
N: number of nodes in the network
a : network density in nodes per unit area
7: transmission range
77: average distance flom any node to the base station at the center of the sensor
field
77 / 7 : average number of hops needed for data to reach the base station
T: number of regions
N/T: number of nodes per region

,6 : number of target source nodes per request (a parameter specified by application

76

request)

K: application request rate

D: number of data packets generated per sensing request (a parameter specified
by the request)

11.: region status update rate in updates/sec/region

0: network wide message generation rate
4.2 Overhead Analysis of Flat Protocols

With a flat protocol such as Directed Diffusion [3 8] or AODV [40], the base station
would perform a network wide flooding of the sensing request message. Since with
such flat flooding each node requires to receive the route request at least once, the
number of request message transmission is equal to the network size N.

Now, after a target sensor node receives a sensing request, it needs to discover a data
path to the base station, for which another round of network-wide flooding needs to be
incurred. In the Directed Diffusion, these messages are in the form of exploratory data.
And for a reactive routing protocol, such as AODV, this round of flooding is realized by
the RREQ route request messages. For each application request with ,6 target sensor
nodes, the number of message transmissions caused by the route discovery process is
Nfl .

Finally, the number of network-wide transmissions for the data messages can be

written as ,BDn/ 7. Therefore, with K requests generated per second, the overall

network-wide message generations rate for the flat protocol is:

09... =K(N+Nfl+flDn/7) <1)

77

For the analysis above, we ignore the impacts of route caching and the cost due to
unicast route replies. The latter is justified since the unicast route reply process
generates much fewer messages compared to the broadcast flooded route discovery
messages.

4.3 Overhead Analysis of Hierarchical Cluster-based Protocols

For hierarchical cluster based routing protocols [57], the application request
dissemination and routing path discovery processes are very similar to those of the flat
approaches, except that the route discovery messages are exchanged at the higher layer
of the routing hierarchy — that is the cluster level.

In most of the cluster-based routing mechanisms such as LEACH [5], the cluster
hierarchy is organized such that a node can communicate directly to its cluster-head.
Therefore, the cluster size is determined by the nodal transmission range. The number
of nodes within a cluster can be represented as nyza , and the number of clusters in the
sensing field is given by N /(7t72a) . Message routing between the heads of two
adjacent clusters involve two hops for a) transmission flom the source cluster head to
an intermediate node, and then b) transmission flom the intermediate node to the
destination cluster-head. Therefore, the message count for request dissemination and
route discovery for each sensing request can be represented as 2(N + Nfl)/(7Z72a).
Generated data message count for each request is [3.017 / y , which is same as that of the
flat protocols. Combining these two, with K requests generated per second, the overall

network-wide message generations rate for the hierarchical cluster based protocol is:

ohimrchy = K(2(N + Nfl)/ny2a + pom y) (2)

78

Note that the overheads for cluster construction and maintenance are omitted in the
above analysis.
4.4 Overhead analysis of ONCP Protocol

Under the ONCP architecture, since the sensing field is configured into regions, the
application request disseminations need to traverse only through the regions on the
global path. With T square regions in the field and r} as the average distance flom any
node to the base station, the average number of regions on a global route can be written
as ry/W . With N / T nodes per region, and 7012a nodes per cluster, the average
number of clusters on a global path can be written as
(r) / W ) x ((N / T ) /(7272a)) . Since the request dissemination across the
global route is performed at the cluster head level, and a message routing between two
adjacent cluster heads require a two-hop transmission, twice the quantity above would
represent the total number of messages needed for sensing request dissemination.

In the worst case, the number of messages generated for the local routing (for
discovering the routes between adjacent regions on the global route) flom each source
sensor node in the target sensing area is also represented by twice the quantity above.
With ,6 target source nodes per request, the message complexity for local routing will
be increased by the factor ,6. Combining all these, the overall message count for

sensing request routing over the global route and the local routing discovery can be

written as: 2 X (U/w/N/(QTD x (N/T) /(7z72a)) x (l + ,8) , which can be simplified

as 2____77\/——
' 22724—

The other major control overhead is contributed from the ONCP region status

—-+(1 fl) (3)

79

updates as described in Section 4.4.3. Status update comprises periodic updates (a)
flom cluster members to their respective cluster heads, (b) flom cluster heads to their
respective region representatives, and c) flom region representatives to the ONCP
server through the base station. The message count for component (a) is equal to the
number of non cluster head nodes in the network which is N (1—1/(n72a)). For
computing part (b) of the update complexity, it is assumed that the average distance
flom any node to its region representative is halfof the side length of the square shaped
region, which is W / 2 , and the corresponding hop count is W) / 27 . This
also represents the average number of transmissions needed for the part (b) of status
update flom each cluster. Now, with N / (72720:) clusters in the network, the total
message counts for part (b) amounts to N JN / (27:73 0.7sz ) . Finally, for the part (c) of
the update cost, number of messages needed flom each region representative to the base
station can be written as 17/7. Multiplying that by the number of region representatives
T, and adding to the message counts for parts (a) and (b), the overall cost for each

network wide update cycle can be written as:

1 NJN Try
2 )+ 3 + (4)
7:7 a 27:7 aJaT 7’

 

 

N(1 —

The generated message count for ONCP is at most fiflDn/ 7 , which is very
similar to those for the flat and the hierarchical protocols. The additional factor
«[2— comes here flom the fact that the global routing under ONCP is done at the level of
square shaped regions, which adds a route diversion factor that is similar to the
traditional Manhattan Routing [58] with successive horizontal and vertical route

segments.

80

Combining this data message cost with the route discovery cost in Equation 3 and
the region status update cost in Equation 4, with a request generation rate of K and

update rate of u, the overall network-wide message generation rate can be written as:

 

00...; H2720?” m++[2——”D”)+ N(1’n;a+fl;:T—+:”)2 (s)
4.5 Numerical Results

In this section we study the comparative performance trend of ONCP using the
analytical results as derived above. Note that the results in this section should be
interpreted more as architectural and relative trend analysis of the protocols as opposed
to absolute and specific protocol performance. Such specific protocol comparisons will
be presented using simulation experiments in chapter 6.

Numerical results are presented in terms of the relative ratio of message transmission
rate for the ONCP protocol (Ooncp/ 0 flat and Ooncp/ Ohierarch) obtained flom
Equations 5, and the message transmission rate for the flat and the hierarchical sensor
routing protocols obtained flom Equations 1 and 2 respectively. Unless specified
otherwise, the default system parameters are as follows: the number of regions T = 100;
the node density 0: =1 ; the normalized transmission range 7 =1; the number of data per
request D = 100; the sensing request rate K = 0.05 requests per second and the region
status update rate 11 = 6 update cycles per 1000 see.

Figure 4.1 shows the impact of network size on relative transmission ratio. It is
evident that for the same amount of data collection, the ONCP flamework generates
lesser number of network wide transmissions compared to both the flat and the

hierarchical protocols. The trend can be observed for networks as small as 500 nodes

81

up to 46000 nodes, and ,6 in the range of 1 node to 9 nodes. The proposed ONCP
architecture achieves this comparatively low transmission rates by constraining its
request and route discovery message flooding only along the centrally computed global
routes. This is in contrast to the traditional protocols in which both the flooding are

done network wide.

 

 

ONCP / Hierarchy ([3 : 9) A

  
   

 

\

 

Network Transmission Ratio
O
bx
l

 

 

 

ONCP/Flat(B:1) +\‘\
i 1 ONCP/Flat ([3 : 9)/‘r' 1 ++
0.2 l l 1 1 1 1 u 1 Jr 1
500 6000 16000 26000 36000 46000
Network Size (N)

 

 

 

Fig. 4.1: Impact on network size on relative transmission ratio
When the network size is smaller than approximately 500 nodes, the ONCP
architecture does not demonstrate many benefits due to the overhead of region updates.
In such a small network, the reduction of network-wide routing discovery overhead
does not fully compensate for the costs of status update. However, for larger networks
(1000 nodes to 21000 nodes), the effects of routing overhead reduction is amplified,
which accounts for the general decrease of the relative transmission ratios. Towards the

higher range of the network size (above 21000 nodes in our experiments), the region

82

status update component of Ooncp in Equation 5 starts dominating again, which in turn,
increases the transmission ratio — especially for smaller ,6 values. This result indicates
that the ONCP architecture delivers the best comparative performance for a large

window of network sizes.

 

 

ONCP / Hierarchy (p : 9) /

. 7“

ONCP / Hierarchy (p : 1)

 
  

  

 

ONCP / Flat (13 : 1)

Network Transmission Ratic
o
00
l

 

ONCP / Flat ([3 : 9)

 

 

 

0.2 l l #1 tr % l

50 100 200 400 800 1600 3200
Amount of Data Per Request (packets) (D)

 

 

 

Fig. 4.2: Impacts of data per request (D) on transmission ratio

Fig. 4.2 shows the variation of transmission ratios Comp / Oflat and
Ooncp / Ohierarchy as a function of the number of data packets per sensing request D
in a 50,000 node network. It is evident that the effectiveness of ONCP is significantly
sensitive to D and its comparative advantage diminishes with larger amount of data
collected per request. In fact, when the data packets per sensing request is more than
800, the transmission ratio is larger than 1, which means ONCP actually performs
worse than the traditional approaches. The reason is that with large amount of data

collection per request, the relative overheads for the flat and the hierarchical

83

approaches are already quite low. Thus, the ONCP cannot perform any better with all its
region update related additional overheads. As in Fig. 4.1, ONCP is comparatively

more effective with smaller ,6 that is smaller number of sensor nodes per target sensing

area.

 

 

‘ ONCP /Hierarchy ([1: 1)

    

. / ONCP / Hierarchy (AB : 9)

   
 
 

ONCP /Flati(B : 1)

Network Transmission Ratic
o
LII
l
l

L___+

Al
I

 

0
DJ
1
I
/+

t i
I

36 169 400 729 1156 1681 2304
Number of Regions (T)

 

 

.9
N
Tl—

 

 

 

Fig. 4.3: Impacts of region size on the transmissions ratio

The impacts of ONCP region size on the transmission ratios Ooncp IO flat and
Ooncp/Ohierarchy are reported for a 50,000 nodes network in Fig. 4.3. With
increasing number of regions T, the sensing request dissemination and route discovery
overhead, as derived in Equation 3, decreases, because less number of nodes are
involved in the overall route discovery process. However, the region status update
overhead, as derived in Equation 4, increases with T, although at a slower rate. The net
effect, as can be observed in Fig. 4.3, is initially decreasing and eventually increasing

ONCP overhead with increasing number of regions for a given network size. The

84

optimal number of regions is determined by the parameters network size, request rate,
status updates rate, and the number of target nodes per sensing request.
4.6 Summary

In this chapter, we build a nmnerical model to compare the scalability of three classes
of routing architectures: flat protocols, hierarchical cluster-based protocols, and ONCP
protocol. The scalability is characterized by the total amount of transmissions needed
in the network for delivering per unit of user data. In the analysis, we omit the impacts
of MAC layer, such as packet losses and retransmissions.

The numerical results demonstrate the comparative scalability benefits of ONCP
flamework under routing control plane. For the same amount of data collection, the
ONCP protocol generates lesser number of transmissions than both the flat and the
hierarchical protocols. The trend can be observed for networks as small as 500 nodes up
to 46000 nodes. It achieves the comparatively low transmissions by constraining its
request and route discovery messages only along the centrally computed global routes
in contrast to the traditional flat and hierarchical protocols. We also investigate impacts
of ONCP protocol parameters, such as the region size. It shows that the impacts of
region size on the transmissions ratio are not linear. The optimal number of regions is
determined by the parameters of network size, request rate, status updates rate, and the

number of target nodes per sensing request.

85

Chapter 5
Simulation Models and Experimental Setup

The ONCP protocol and experimental comparisons with flat and hierarchical
protocols have been implemented using the n32 network simulator version 2.29 with
CMU wireless extensions [46]. N82 is an event driven simulator with extensive
supports for wireless network protocols. In order to implement the ONCP architecture,
we have added several features to n82 simulator. The extensions include the application
data traffic model and ONCP routing protocol.
5.1 NS-2 Simulation Models

This section describes the models for channel propagation, radio energy dissipation
and application data traffic.
5.1.1 Channel Propagation Model

In a wireless media, the electromagnetic wave propagation can be modeled as a
power law function of the distance between the transmitter and receiver. In addition, if
there is no direct, line-of-sight path between the transmitter and the receiver, the
electromagnetic wave will bounce off objects in the environment and arrive at the
receiver flom different paths at different times. It causes multi-path fading, which again
can be modeled as a power law function of the distance between the transmitter and
receiver. The received power decreases as the distance between the transmitter and
receiver increases.
For the experiments conducted, both the free space model and multi-path fading

model are used depending on the distance between the transmitter and receiver, as

86

defined by the channel propagation model in n32. If the distance between the

transmitter and receiver is less than a certain cross-over distance dc , the F riis flee space

model is used. Otherwise, the two ray ground propagation model is used. The crossover

distance is defmed as follows:

dc

 

_ 4nJZhrh,
,1

where L : the system loss factor not related to propagation.
h, : the height of the receiving antenna above ground.
ht : the height of the transmitting antenna above ground.
/l. : the wavelength of the carrier signal.
If the distance is less than dc , then the received signal power, according to the Friis
flee space model, is described as follows:

near/12

Pr(d)= ,
(47rd) L

Where P, (d) is the received power given a transmitter-receiver distance d.
P, : the transmit power.
Gt : the gain of the transmitting antenna.
Gr : the gain of the transmitting antenna.
,1 : the wavelength of the carrier signal.
(1 : the distance between the transmitter and the receiver.
This equation models the power attenuation, when the transmitter and receiver have
a direct line of sight communication, which occurs if the transmitter and the receiver are

close to each other. If the distance is greater than dc , then the received signal power is

87

calculated using the two-ray ground propagation equation as follows.

36.0.}:th-

P.(d>= d4

 

Where P, (d) is the received power given a transmitter-receiver distance d.
P, : the transmit power.
Gt : the gain of the transmitting antenna.
Gr : the gain of the transmitting antenna.
hr : the height of the receiving antenna above ground.
ht : the height of the transmitting antenna above ground.
(1 : the distance between the transmitter and the receiver.

In the n32 implementation, where a packet arrives at the receiver, as long as the
received signal power is larger than pre-defined threshold, the packet is regarded to be
successfully received.

For all the experiments, we choose omnidirectional antenna with the following
parameters: Gt = Gr=l, hr = ht: 1m, L=l (no system loss), xi =0.328m (914M)
5.1.2 Radio Energy Model

Significant research has been done in the area of low-energy radios. In this work, we
assume a simple radio model where the transmitter dissipates energy to operate the
radio electronics and the power amplifier and the receiver dissipates energy to Operate
the radio electronics [46]. As discussed in the previous section, the power attenuation is
dependent on the distance between the transmitter and receiver. For relatively short
distances, the propagation loss can be modeled as inversely proportional to d2, whereas

for longer distances, the propagation loss can be modeled as inversely proportional to

88

d4. Power control can be used to invert this loss by setting the power amplifier to ensure
a certain power at the receiver.

The radio characteristics used are given in Table 3. All the nodes communicate with a
modified leps 802.11 MAC protocol with a radio range 40m as in [3 8]. And we also
use the same energy model [3 8]. The idle power dissipation is 35 mW, the receive
power dissipation is 395 mW, and the transmit power dissipation is 660 mW. The ration
of the energy consumption in the Idle: Rx: Tx modes is about 1: 10: 20. The energy
consumption for switching between awake and sleeping modes is negligible and thus

not considered.

 

Radio Bandwidth leps

 

Radio Transmission Range 40 m

 

Radio Interference Range 88m

 

 

 

Transmit Power 660mW
Receive Power 395mW
Idle Power 35mW

 

 

 

 

Table 5.1: Radio Parameters
5.1.3 Application Data Model
We implement ONCP application data model described in Section 3.3, instead of
commonly used CBR (constant bit rate) traffic. User clients are assumed to be
connected to the ONCP server and generate asynchronous sensing task requests with
specific geographical and/or other attributes. A user identifies a target sensing area and
then generates sensing task requests to the ONCP server. For example, a user may select

a certain part of a vegetation area as the target sensing zone, and then deliver a sensing

89

task request to measure the soil pH level at a regular interval of six hours and for
duration of thirty days. Based on the target sensing area and ONCP region
configuration, the task requests are routed to the appropriate target sensor nodes. When
target nodes receive the requests, they will start to generate data based on the specified
attributes in the requests. The traffrc data load is also specified by the requests. Note
that user clients can not address or specify the sensor nodes and therefore no individual
sensor level information is included in the sensing task requests.

lgk Request Message Structy_r_e;: Request provides a query mechanism for
applications to ask for specific data or events flom the sensor networks. A request can
be either for synchronous data collection such as periodic temperature monitoring, or
for asynchronous event collection such as detecting a specific bird species within a
certain area of the sensor field. The model for request syntax includes:

1. ID: each request is uniquely (network wide) identified by an ID through ONCP
server. All data or events generated by target sensor nodes as responses to a request will
be identified by the request ID. The concept of command-id serves as a data naming [3 8]
or meta-data abstraction. The ONCP local routing also uses the request ID information
rather than source / destination identifiers.

2. Priority: in resource-constrained situations, data/events for different requests will
be differentially treated based on this field. So far in our n82 simulations, all requests
have the same priority.

3. Geographical scope: specifies a geographical region in which one or multiple

target sensor nodes need to respond to the request and generate data. The specified

90

region can be arbitrarily large and can be non-contiguous. By changing the
geographical scope, we can vary the number of target sensor nodes per request, thus
changing the data traffic load.

4. Additional Filters: specifies additional filtering for sensor programming. An
example of this is to enable data sensing only at sensors for which the energy level is
more than a specified threshold. Any application-specific filtering can be performed
based on these parameters. The filters serve the purpose of data aggregation/fusion.

5. Queried sensor parameters: This field specifies the data generation pattern by the
following arguments: (a) data generation start time; (b) data generation end time; (c)
data generation interval.

In summary, the application data model specifies the number of target sensor nodes,
the data generation start time, end time and data generation interval. Therefore, it flrlly
specifies the data traffic patterns.

5.2 ONCP Routing Implementation

To implement our ONCP routing protocol and application data model, we add
several features to ns2. N32 has a simulation engine written in C++ with a command
and configuration interface using OTcl language. Networks can be described by
primitives such as Nodes, Links, Agents, and Applications. Nodes represent end-host in
the network, Links are connectors through which Nodes exchange packets, Agents are
basic blocks to implement network protocols at various layers where network-layer
packets are constructed and consumed, and Applications sit on top of transport agents

for traffic generation and simulated applications. Our ONCP routing protocol is

91

implemented in the Agent primitive.

5.2.1 ONCP Agent Structure

 

 

 

 

 

_ Port -
'm4- m
55
CR A dress ‘3
.1 99mm ‘ en

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Radio Propagation Network

Model I RITE.

Channel ]

 

 

 

 

 

 

 

 

 

Fig. 5.1: Internal blocks of mobile node

The internals of a mobile node is presented in Fig. 5.1, including Channel,
Network-interface, Radio Propagation model, MAC protocols, Interface Queue, Link
layer and Address Resolution protocol model (ARP). The data flow within a node can
be briefly described as follows. The Application creates data packets and sends to the
Agent. The Agent performs the transport and network layer functions of the protocol
stacks. Then packets are sent to a Connector which passes them to the link layer (LL)
for processing. Link layer forwards the packet to the queue, where it is queued if there
is more than one packet in the queue that has not yet been transmitted. When the MAC

receives the packet, it performs media access protocol to determine how to send the

92

packet. Finally, the packet is moved to Network Interface, where the transmit power is
added the packet header and send through the wireless Channel. The Channel sends a
copy of the packet to all the nodes connected to the Channel. The packet is received by
node’s Network Interface, and passed through MAC, LL, and Agent. The node also
de-multiplexes the packet to corresponding Agent based on the packet’s address and

port number. The Agent then sends notification of packet arrival to the Application.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Application-1 Application-2 Application-. . Application-n
Requests T
’ __ “Off-network Control Processing (ONCP) Functions _ h .. ___ ..
i Virtual Region , Global ROUIC Path: comma“! %
' 'C f , Decomposition ;
. Management & -____* omputation or 1 ‘
é C d and 1 ; and Response 1
. Status Update 1 g 01111erm 5 g 1
3 é ; Response g g Assembly j
1 Command ; g , 5 .
' Filtering ‘ Self-Organized : Local : iCommand &
&Response guster ti n _._): Reactive QResponse 1
i Aggregation . l gamza 0 1 ; Routing ; EForwarding
A ,. s ,.‘, AK, 1... -_ .7 A... ....-.+.----- "a L. _ A ..... .1
i it i h
r Energy Efficient MAC Protocols J

 

 

 

 

Fig. 5.2: ONCP agent diagram
Since the source and destination node may not be directly connected by the Channel,
it is possible that the intended packet needs to pass through multiple intermediate nodes.
When a packet arrives at an intermediate node, it is processed by the Routing Agent to
discover how to reach destination node. The Routing Agent performs routing functions
to find the path, during which additional routing discovery packets may be generated.
ONCP Agent is in the 1P layer, whose structure can be described in the Fig. 5.2,

comprising the modules of cluster organization, status updates, the global routing,

93

command forwarding and the local reactive routing. The implementation of these
modules in n32 will be discussed as follows.
5.2.2 Cluster Organization

The clusters serve two purposes in ONCP architecture: (1) implement a scalable local
routing; (2) aggregate network information for status updates. To organize wireless
sensor nodes into clustering, we use similar mechanisms as in [5]. Each node has
clustering status as one of cluster-head, cluster-member, or undecided. A cluster
consists of a group of nodes with one of them elected as a cluster-head, and is identified
by the cluster-head. Each cluster should have one and only one cluster-head. The
cluster-heads can not be l-hop neighbors in order to restrict the cluster size.

Each node (both cluster-head and cluster-member) maintains a neighbor table, which

is constructed flom the received “neighbor hello” messages. The neighbor table is a
data structure which describes information about its l-hop neighbors. Each entry in the
neighbor table contains: (a) ID of neighbor node; (b) the cluster status (head, member or
undecided); (c) ID of cluster-head; (d) the energy of the node; (e) the last time when a
“neighbor hello” message is received flom that node. Every node periodically
broadcasts its own status (ID, cluster status, cluster-head, and energy) as well as its
neighbor table in the “neighbor hello” message to its l-hop neighbors. The message

structure is described in Fig. 5.3.

94

 

ID Cluster_status Cluster_head Energy # of neighbor Entry

 

 

 

 

 

1th neighbor Entry (include ID, Status, Cluster_head, Energy, Last recv time)

 

 

 

 

nth neighbor Entry (include ID, Status, Cluster_head, Energy, Last recv time)

 

Fig. 5.3: Format of neighbor hello message

Cluster-heads are elected based on the nodal energy level. Apart flcm the status states
of Cluster_head and Cluster_member, we define a transitional state called
Cluster_undecided, which means a node is still in search of its host cluster. All nodes
wake up in the status of Cluster_undecided. A node uses the information obtained flom
l-hop neighbors’ hello messages for cluster formation. It periodically checks its energy
level and its l-hop neighbors’ energy levels in the neighbor table. If it discovers that it
has the highest energy among its neighbors, it declares itself as cluster-head, otherwise
as Cluster_member. When two nodes within l-hop neighborhood both declare as
Cluster_heads, the one which has lower energy should resign and change status to be
Cluster_undecided. The details of the cluster organization algorithm are described in the
Fig. 5.4.

A cluster-head has complete knowledge about its group cluster-members, after
cluster organizing stabilizes. And flom hello messages of l-hop neighbors, it is able to
gather information about the network topology 2-hops away flom itself. Thus, it keeps
a 2-hop topology database. The neighboring cluster-heads table is utilized in local

routing in Section 5.2.5.

95

 

 

/* Cluster Organization Algorithm */
Cluster Initialization:
For (each node in the network) {
Each node declares its Cluster_status as Cluster_undecided;

Broadcast “hello " messages to its neighbors at the frequency of H_F requency;
Record the “hello ” messages from its I-hop neighbors;

Cluster Organization:
F or ( ( each node in the network) {// organize cluster structure

Remove the outdated “hello ” messages;

From the recorded “hello ” messages, identrfv all I-hop neighbors ’ Cluster_status
and energy levels
Switch (Cluster_status) {
Case Cluster_undecided:
If (its energy is higher than those of all I-hop neighbors whose Cluster_status are
Cluster_undecided) {
Change its Cluster_status to be Cluster_head;
Change the broadcast frequency to be L_Frequency;
Return;
}
If (Has a neighbor whose Cluster_status is Cluster_head and has higher energy) {
Changes its Cluster_status to be Cluster_member;
Change the broadcast frequency to be L_Frequency;
Retum;

}

Case Cluster_member:
If (lost Cluster_head) {
Goto cluster initiation phase;
Return;
}
Case Cluster_head:
If (has a neighbor whose status is also Cluster_head and has higher energy) {
Goto cluster initiation phase;
Return;

 

Fig. 5.4: Pseudo code for cluster organization algorithm

96

 

5.2.3 Status Updates

Region Representatives need to periodically update region level aggregated nodal
energy and region connectivity metric information to ONCP server for the global path
selections. The status update forwarding process can be described in three phases: (1)
cluster-members to cluster-heads; (2) cluster-heads to region representatives; (3) region
representatives to ONCP server. Along each phase, the updated information is further
aggregated. For example, when a cluster-head sends update message to its region
representative, it aggregates all its members’ energy and connectivity metric. Similarly,
a region representative aggregates the energy and connectivity metric of all the nodes in
its region. Status update message has the following format as shown in F ig. 5.5: (1) ID
of the reporting Nodes. (2) Type of reporting nodes (cluster-member, cluster-head, or
region representative). (3) Sequence of update messages. (4) The numbers of entries for
aggregated nodal energy. (5) The numbers of entries for region connectivity pair metric.
(6) Values of aggregated nodal energy for each region entry. (7) Values of connectivity
metric for each connectivity pair entry.

Region Representatives can be selected through n32 OTCL interface. During the
network configuration phase, when a node is created, it is assigned a Region ID based
on its location. Each region maintains one and only one designated region
representative which updates the ONCP server with the region level information. When
a representative was out of service due to node failure, the OTCL interface is able to
reselect one for the corresponding region.

Low maintenance spanning trees, rooted at the base stations and spanning across the

97

region representatives, are used for region level status update. The spanning tree should
be periodically refleshed in a distributed manner. ONCP architecture is proposed for
static network, and the topology does not change flequently. So in our ns2
implementation, we adopt a centralized way to discover the spanning tree. During
network configuration phase, after all region representatives are designated, ONCP
server computes spanning tree using Dijkstra algorithm, and inform all the region
representatives.

The updated status information flom region representatives is maintained as soft
states on the ONCP server. They will be time out to reflect the region information
change, unless refleshed by region representatives. The state complexity of updates is

at the order of the region number.

 

ID Node Type Sequence # of Energy Entry # of Connectivity Entry

 

 

 

 

 

1th Region Energy Entry (include Region_ID, Aggregated_Energy)

 

 

nth Region Energy Entry (include Region_ID, Aggregated_Energy)

 

1th Connectivity Entry (include F rom_Region, To_Region, Connectivity Metric)

 

 

mth Connectivity Entry (include From_Region, To_Region, Connectivity Metric)

 

 

 

Fig. 5 .5: Format of status update message
5.2.4 Global Routing and Command Forwarding
When an application request is generated by a user client, it is not directly sent to the
network. The request is first forwarded to ONCP server for processing, and

decomposed into one or multiple commands based on the request’s geographical scope

98

and region configuration. It is specified that one command is designated for one single
region. So if the requested geographical scope spans multiple regions, more than one
command will be generated.

The global routing path is on the basis of region. From the application request’s
geographical scope and region configuration, the target region (regions) can be
identified. Then we rely on the information gathered flom status updates to determine
the region level paths flom target region to ONCP server. For user clients, it does not
matter as flom which base station the sensed data are collected, so we also need to
decide the base station to receive the collected data.

From the gathered aggregated region energy and the region connectivity metrics, the
ONCP server abstracts a directed graph G, in which the vertices represent the regions
(including the base stations), and the edges represent the connectivity between regions.
The edge value in G is defined as the corresponding inter-region connectivity metrics
and the vertex value is defines as the aggregated nodal energy of the corresponding
region. After that, ONCP server executes a centralized algorithm to find the region
level path flcm the target region to the chosen base station. The pseudo code of the
algorithm is described in Section 3.4.4.

After finding the path, a command is generated by ONCP server. The format is
described in Fig. 5.6. It includes: (1) Command ID, which uniquely identifies the
command during the application request’s lifetime. (2) Target Region ID. (3)
Geographical scope, it is represented by a rectangle region in current implementation.

(3) Application request query parameters. This field specifies data generation start time,

99

data generation end time; and data generation interval. (4) Region level global path. It
is a series of region ID, starting flom the chosen base station, and ending at target

region.

 

Command ID Target Region ID Geographical Scope (lefttop_x, Y; bottomright_x, Y )

 

 

 

Application request query parameters (start_time, end_time, interval )

 

 

 

Global region path (base_station, rcgion_l, . .. target_region)

 

Fig. 5.6: Format of command message

From the base station, the command is forwarded to the target region along the
specified global region path. The command propagation process is one the basis of
clusters. When a cluster-head receives a command, it checks whether its region is on
the region path. If it is the case and it has not receive the command before (identified by
the Command ID), then it sends the command to all its neighboring cluster-heads.
Otherwise, the command is discarded. This propagation process continues till the
command reaches the target region.
5.2.5 Local Routing Mechanism

The in-network local routing is a reactive mechanism. When a node receives data to
forward to the next region on the global path, but it does not have a routing entry to the
next region, a local route discovery process is invoked. A clustering hierarchy is added
to the local routing protocol as described in Section 5.2. 1. As a result, local routing is at
the level of clusters and always originated and terminated at cluster-heads in
neighboring regions.

Local Routing Request: in local route request, only cluster-heads send out Local

100

Route Request (LRQ) messages and these messages and restricted only within

originating region and the next region. The format of message is shown below:

 

 

 

ID (originating cluster-head) ID of Originating Region ID of Next Region

 

Sequence # of Hops MaxMin Energy

 

 

 

 

 

Fig. 5.7: Format of local route request message

As local routing is on the level of cluster, whenever a cluster-member receives a LRQ,
it sends to its cluster-head, and let cluster-heads to process it When a cluster-head
receives a LRQ that is originated in its own region, the cluster-head increments the
hop-count value, updates MaxMin energy metric and re-floods the message to its
neighbor cluster—heads. If a LRQ message reaches a region which is not the originating
region or the next region, this message is discarded. Along the LRP message
propagation, cluster-heads who receive the LRQs also setup the reverse paths to the
originating cluster-head. The reverse path selection is based on the MaxMin energy
metric and the number of hops. When a LRQ message arrives at the desired next region,
the recipient cluster-head replies a Local Route Reply (LRP) message to establish the
path.

Local Routing Reply: The LRQ message specifies the ID of next region, instead of
ID of node. As a result, more than one cluster-heads within the desired next region may

send local routing reply LRR message. Its format is shown as follows.

 

 

ID (replying cluster-head) ID (originating cluster-head) ID of Next Region

 

 

Sequence # of Hops MaxMin Energy

 

 

 

 

 

Fig. 5.8: Format of local route reply message

101

The originating cluster-head indicates which node should receive this reply messages,
and ID of next region specifies the desired region. MaxMin energy metric and the
number of hops have the same meaning as in LRQ messages. The local routing reply
(LRP) messages follow the reverse paths specified by LRQ messages till reaching the
originating cluster-head. The originating cluster-head will establish the routing entry to
the Next Region, which has the highest MaxMin energy metric. If more than one path
has the same energy metric, then it will choose the one which has smallest number of
hops.

Local Routing Error: In the lifetime of network, the topology connectivity might
change due to node failure or mobility. It is possible that packets arrive at a node which
does not know how to reach the next region on the global path and can not initiate local
request as it does not know what the desired next region is. In such cases, a local routing
error is generated and forwarded to the last cluster-head in previous region. A local
routing error message includes the ID of last cluster-head, ID of previous region, ID of
current region. The local routing message is restricted within the previous region and
current region. The message propagation will also stop when reaching the last
cluster-head. A cluster-head receives such messages should remove the corresponding
routing entry in its routing table. If the route to that region is still in need, then a new

local routing request / reply circle will start again.

102

Chapter 6
Experimental Performance Evaluation of ON CP

6.1 Experimental Environment

We have implemented the ONCP architecture in n32 network simulator and compared

its performance with that of the Directed Diffusion [38] and CBRP [75], which

represent the distributed and cluster-based routing protocols respectively. DCF mode

802.11 with a modified energy model [3 8] is used as the MAC protocol. Due to nsZ’s

runtime constraints, we have used a moderate size 2916-node network for validating

the ONCP performance. Comparative performance trends for very large networks are

studied with the numerical results as presented in chapter 4.5.

Experimental Scenarios: A 2916-node static network has been created by arbitrarily

deploying the nodes in a 1300m x 1300m square sensing field, with a nodal

transmission radius of 40m [3 8]. The network is configured into 81 square regions and

the number of base stations is varied flom 1, 2, to 4.

 

 

 

 

   

Sensing Request Tasks

User client9 E l E E

l |

-—.

30051 600sl 900s 1 120051

 

User client 1 @ I % I @ I w I T 5

6...“... mm {1111, gm 911111 mm .
'25: I 2:a: T 227. 1 u... I "a; '

User client 3 <3; III \I \‘L.I ,
9.0-; I "a; ' “a; '

User client 10 N E E R m

 

 

Fig 6.1: Timing diagram of sensing task requests flom user clients

103

As for the application model, we have simulated the same architecture as descried in
Section 3.3. Ten user clients have been programmed to generate repeated asynchronous
sensing task requests that are randomly targeted to sensing areas of the network. The
number of nodes per target area B is varied flom 1 to 9.

Each sensing request requires the target nodes to generate data for 60 seconds, and
two consecutive requests flom the same client are separated by a uniform randomly
distributed interval between 120 sec and 360 sec. During 1500 seconds of network
simulation, each user client generates 5 sensing requests. The baseline region status
updates interval (Up) is set to 300 seconds. Fig 6.1 shows the timing diagram of

sensing task requests in the application model.

 

 

 

 

 

 

 

 

 

A ‘ Sensing Target Area ‘ ‘
A 3 \>
; A
A 1 A
A : A A A
A I A A 5 A A
A i
A ‘ I \ A J A
A 3, .................. .-.-.- I ‘ A \ A
A A A 5 Number of Nodes per
r T I AI = 7
Number of Nodes per . ‘ arge ea (B )
A Target Area (B = 3) ' A
l ‘ A
A A 1
Region S Region D

 

Fig 6.2: The diagram of sensing target area and number of nodes per target area
This sensing request model ensures that the traffic loads are sufficiently distributed
across the network. The size of the packets sent out by sensor nodes is 64 bytes.

Experiments are carried out for data rates ranging from 0.5 packets per sec to 4 packets

104

per see. This rate is determined by the parameter D (number of data packets generated
per request). The same user request model is used while simulating ONCP, Directed
Diffusion and ONCP. The concepts of sensing target area and the number of nodes per
target area [3 are shown in Fig 6.2.

6.2 Simulation Results and Analysis

6.2.1 The Scenarios with Single Base Station

In the first set of simulations, it is configured that a single base station is placed at the
center of the network. The data rate and the number of target nodes specified by user
clients are varied from 0.5 packets per sec to 4 packets per sec, and from 1 node per
target area to 9 nodes per target area respectively. In these settings, the traffic load is
under a wide range, from the low load to the congestion phase. We intend to
characterize the impact of traffic load on the performance.

Normalizch Protocol Overhead: This index is defined as the total number of
transmitted packets per successfully delivered data packet, normalized by average hops
from source to the base station. Results in Fig. 6.3, 6.4 substantiate the claim that ONCP
has fundamental architectural benefits of reducing the control overhead, compared with
the distributed protocols like the Directed Diffusion and hierarchical cluster-based
protocols like CBRP. The normalized overhead monotonically decreases for ONCP
with increasing trafl'rc (the packet rate and the number of nodes per target area).
Directed Diffusion and ONCP, however, show a reverse trend when the number of
nodes per target area is more than 4 and 6 respectively. That is because at higher traffic,

the significant packet drops due to congestion in the two protocols offsets the effects of

105

reduced overhead per packet.

 

 

 

 

 

 

 

 

 

 

 

80
Directed Diffusion
“o . .
8
fl __
0 60 ‘, ‘ +0NCP 0.5 packets/sec)
6 -B-ONCII:31 ackets/sec
_ -+-Drrec . ion (0. packets/sec)
o *Drrected Drflirsron 1 packets/sec)
8 —e—- CBRP (0.5 packets/sec)
*5 40 + . 7. . 7 , H +CBRP lpacke sec
5:
‘O
E
7::
E 20 ‘—
CBRP
2 g 3 Z \i ‘
0 l H l H l .. i "'
l 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area ([3)

 

 

 

 

Fig. 6.3: Normalized protocol overhead at rates of 0.5 and l packet/sec

 

 

 

A
O

-0-ONCP (2 packets/sec)
-B—ONCP (4 packets/sec)
-l— Directed Diflision (2 packets/sec)
-)é-Directed Difiirsion (4 packets/sec)
+ CBRP (2 packets/sec)
-)K— CBRP (4 packets/sec)

Directed Diffusion

 

 

 

Normalized Prgtocol Overhead
O

 

 

 

 

2 3 4 5 6 7
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.4: Normalized protocol overhead at rates of 2 and 4 packet/sec

106

Expected Packet Delivefl Ratio: It is defined as the ratio of data packets received by
the base station and the expected data packets requested by user clients. This index
captures the loss of both data packets as well as the sensing request messages. When
the number of nodes in the target area is small, (1 node), Directed Difl'usion can receive
around 80% of the expected packets. This result is consistent with the original Directed
Diffusion performance [3 8]. And CBRP has very similar performance as ONCP,

achieving around 90% expected packet delivery ratio.

 

 

    

 

-0- ONCP (0.5 packets/sec)
-E—ONCP (1 packets/sec)

j -i— Direc ion (0.5 packets/sec)
0,2 — *Directed Diflision (1 packets/sec)
+ CBRP (0.5 packets/sec)

-l— CBRP (1 packets/sec)

Expected Packet Delivery Ratio

 

 

 

l l l I I l I l
l I I I I l I I

 

 

O

1 2 3 4 5 6 7
Number of Nodes Per Target Area ([3)

 

 

 

Fig. 6.5: Expected packet delivery ratio rates of 0.5 and 1 packet/sec

However, when the traffic load is larger than what was considered in [38], the
performance of Directed Diffusion degrades steeply. CBRP has better performance
than Directed Diffusion, but still notably worse than ONCP. These effects are observed

with increased traflic due to both increased data rate and increased number of nodes in

107

the sensing target areas. This degradation is because of congestion caused by intense
network-wide routing discovery. These effects are found to be particularly escalated for
short-lived sensing task models, as both Directed Diffusion and CBRP protocols need
to build fresh routes for each task through network-wide routing discovery.

As evident from Fig. 6.5, Fig. 6.6, the ONCP protocol manages to defer the delivery
ratio degradation problem significantly by avoiding the congestion in the network
through off-network routing which helps to avoid the expensive network-wide flooding.
ONCP manages to maintain nearly 90% expected delivery ratio, except for scenarios
with data rate of 4 packets/sec and more than 6 nodes per target area. At higher sensor

trafiic loads, ONCP also degrades its performance.

 

 

 

     
    

Directed
04 e— Diffusion

 

-B-ONCP 4 ackets/sec

0.2 —- -+—Directe ion (2 packets/sec;
-)(-Directed Diifirsion 4 ackets/sec

—e— CBRP E2 packets/sec?

—+— CBRP 4 packets/sec

0 1 l I l i i l
I I I I I I I

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area ([3)

 

Expected Packet Delivery Ratio

-0- ONCP32 packets/sec;

 

 

 

 

--1>—~
4...... -._.--_

 

 

 

 

Fig. 6.6: Expected packet delivery ratio rates of 2 and 4 packet/ sec

Eif-to-End Delivery Latency: The effects of relatively aggravated congestion in

108

Directed Diffusion and CBRP are apparent from the delivery latency in Fig. 6.7 and Fig.
6.8. It is notable that for small sensing target area sizes, all three protocols have similar
and small delay performance. The end-to-end delivery latency of Directed Diffusion
and CBRP is actually smaller than that of ONCP, when the number of nodes per target
area is small (1 or 2). This is because of shorter hop counts. The average hop counts are
around 20 for Directed Diffusion and 22 for ONCP, compared to 33 for ONCP. This is

due to the region layer abstraction in the global routing of ONCP.

 

 

 

 

 

 

 

 

 

1.5

o .

£3 -0-ONCP (0.5 packets/sec)
:3 -E—ONCP (1 packets/sec)

E? —I—Directed Diflirsion (0.5 packets/sec) -

a) -)(-Dinected Diflirsion (1 packets/sec)
E 1 _— -—e- CBRP (0.5 packets/sec)

a -)I(— CBRP (1 packets/sec)
“O , .

‘3

LL}

3 I
'0 ——— z
I: 0.5 > .

Q) i ‘ /

cc , .

i3 . / i " --- " "

.< M . ---—-- ...,...“
< I l I I I l I I
0 I I I I I I I I

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area ([3)

 

 

 

Fig. 6.7: End to end packet delivery latency at rates of 0.5 and l packet/sec

However, with increasing number of nodes per target area, the delay for Directed
Diffusion increases much faster than that of ONCP. Higher congestion, and subsequent
packet queuing and MAC layer retransmissions in Directed Diffusion account for its

higher delay in high traffic load range. In contrast, ONCP is able to mitigate the

109

congestion by its off-network routing approach, and therefore the delay remains

 

 

 

 

 

 

relatively steady.

>. 5 I '

0 -0- ONCP (2 packets/sec)

g -B- ONCP (4 packets/sec) 3
:3 4 —_ -I—Directed Diffusion (2 packets/sec) .. .. . ._ . . I. . ,. _
a. -)(- D'rected Diffusion (4 packets/sec) g
D ~9- CBRP (2 packets/sec) ,
:E‘ -)I(— CBRP (4 packets/sec) .
Q 3 .IL : , 7, , , .
Q :
"a . :
a ‘ ;
LT-I
8 2 “" :
Io i
G 2
m I
0 __ .
3‘30 1

g

< I

0 I I T I I I T i

 

 

 

l 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.8: End to end packet delivery latency at rates of 2 and 4 packet/sec

Average Hops per Packet: Fig. 6.9 and Fig 6.10 show the average hops needed to
deliver a data packet to the base station. Observe that for all traffic rates and sensing
region sizes, ONCP performs worse than Directed Diffusion and CBRP. This is caused
primarily by the region layer abstraction during the global routing. Because of this
region layer, the ONCP protocol is not able to compute shortest path routes, as in
Directed Difi‘usion. That results in longer paths. This, in fact, is a notable shortcoming
of the ONCP routing architecture. However, note that in spite of longer average paths,
the end-to-end delay and energy dissipation of ONCP is more favorable than Directed

Diffusion and CBRP. Lower congestion due to less number of control messages is the

110

primary reason.

 

 

40

b.)

O
I
I

 

 

Average Hops
N
O

-0- ONCP (0.5 packets/sec)
“B-ONCP (1 packets/sec)
-l— Directed Diffusion (0.5 packets/sec)

 

 

 

 

 

10 ‘” " "X—Directed Diffusion (l packets/sec)
-0- CBRP (0.5 packets/sec)
-9|E- CBRP (1 packets/sec)
0 I I I I I I I I

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig 6.9: Average hop counts at rates of 0.5 and 1 packet/sec

Observe that unlike ONCP and CBRP, the hop-count for Directed Diffusion is very
sensitive to the number of nodes per target sensing area. This is because the path
reinforcement process in Directed Diffusion depends a great deal on the network delay,
which is higher at larger traffic loads. That explains why the hop-count for Directed

Diffusion increases with both packet rates and larger target sensing areas.

111

 

 

40

 
 
   
 

I

Directed Diffusion '_’ I!

..‘h— /~"|

 
 

00

O
l
I

Average Hops
N
o

 

'9' ONCP (2 packets/sec)
‘9' ONCP (4 packets/sec)
-|'- Directed Diffusion (2 packets/sec)
*' Directed Diffusion (4 packets/sec)
-6-- CBRP (2 packets/sec)
-)K— CBRP (4 packets/sec)

0 L I I I l I I I
I I I I I I r I

1 2 3 4 5 6 7 8 '9
Number of Nodes Per Target Area (B)

y—A
O
l
I

 

 

 

 

 

 

 

 

 

Fig 6.10: Average hop counts at rates of 2 and 4 packet/sec

Avergge Energy Dissipation: Average energy dissipation, as shown in Fig. 6.11, Fig.
6.12, is expressed [3 8] as Joules per delivered packet, normalized by the total number
of network nodes. Observe that for all three protocols ONCP, CBRP and Directed
Diffusion protocols, the dissipated energy decreases with higher packet rates. This is
because at lower rates, due to MAC layer idling and overbearing, a large part of the
consumed energy is not actually used for data packet transmissions. With increasing
traffic loads, and correspondingly more received packets, however, the efl‘ects of idling
and overheating reduces gradually, which causes the dissipated energy numbers to

improve.

112

 

 

0.06

 

: -0-ONCP (0.5 packets/sec)
f -B—ONCP (1 packets/sec)
—" " " ‘ ' " ' ‘ " “ -4—Directed Drfiiision(0.5 packets/sec) "
. -)(-Directed Diffisionfl packets/sec)
? «e— CBRP (0.5 packets/sec)

-I- CBRP (1 packets/sec)

 

 

 

I

 

Dissipated Energyy (J/node/packet)
o o o o o
o o o o o
H N U) J:- U:

 

 

 

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.11: Average dissipated energy at rates of 0.5 and 1 packet /sec

Similar trends can be also observed with increasing number of nodes per target area.
For all trafiic loads (both packet rates and nodes per target area), that we have
experimented with, the energy expenditure of the ONCP protocol remained smaller
than those for the CBRP and Directed Difl'usion. In spite of its more data packet
transmissions (larger hop counts), and region status updates, ONCP is able to sustain
better energy performance by avoiding aggressive flooding using its “off-network”
architecture. Lesser packet drops for ONCP also help to keep the energy expenditure
low. Energy dissipation in CBRP and Directed Diffusion is contributed primarily by
the network-wide flooding of the route discovery messages. The energy performance of
ONCP is another indication of how the off-network routing can architecturally improve

large sensor network performance by offering better control plane scalability.

113

 

 

 

0.02 WWW” W i i

' -0-ONCP (2 packets/sec)

-B- ONCP (4 packets/sec)

-I— Directed Diffusion (2 packets/sec)
-)(— Directed Difision (4 packets/sec)
--e—- CBRP (2 packets/sec)

-+- CBRP (4 packets/sec)

IO
O
p—a
Kit
I
I

 

 

 

 

 

 

 

Dissipated Energyy (J/node/packet)
o
S

 

 

0.005 “r ‘ _
\I
\, ‘ 3 :
L‘\ I : f v C 1"; 0
:—'='—L—.-.—_.. _:
I ~ "' ' "' '" '1
0 I I I I I I I I

 

l 2 3 4 5 6 7
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.12: Average dissipated energy at rates of 2 and 4 packet /sec

Communication Energy Conmption: Energy performances of the protocols are also
evaluated by considering only the transmission and reception energy consumptions.
The idle and overbearing energy is not counted. Since this communication energy
consumption is heavily correlated with the number of transmissions in the network, it
can be regarded as an alternative index of protocol scalability compared to the
normalized energy consumption. In fact, a number of T DMA [31, 32, 34] and
sleep-based [16, 80] sensor MAC protocols are available and can be used for avoiding
energy consumption due to idling and overhearing.

As shown in Fig. 6.13, Fig. 6.14, Directed Diffusion incurs the largest energy
expenses due to its extensive network-wide routing discovery process. Although the

hierarchical protocol CBRP mitigates this effect to some extent by exploiting its

114

cluster-based abstraction, a network-wide search is still needed for route discovery.
This explains why the energy performance of CBRP is lower than that of a flat routing
protocol such as Directed Diffusion, but still higher than that of the ONCP approach.
With ONCP, the communication energy expenses are the minimum due to its smaller

transmission overheads as demonstrated through our analytical model, and through ns2

 

 

 

    
       
  

 

 

 

simulations.

40000 . 1 *-
-0-ONCP 0.5 packets/sec)
-B-ONCP 1 ackets/se?
-l—Directe ron E0. packets/sec) .
-)(-Directed Diflirsion 1 packets/sec)

30000 __ + CBRP E05 packets/sec)
+CBRP 1 packets/sec)

l

Directed mansion

I

20000 _

I

10000 ‘

Communication Energy (J) .

 

 

 

 

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.13: Communication energy consumption at rates of 0.5 and 1 packet /sec

With increasing traffic load (both data rates and the number of nodes in target sensor
areas), the communication energy expenses for all three protocols increase, since more
data transmissions are needed. The ONCP is the least sensitive to the traffic load. The
normalized energy consumption and communication energy consumption of ONCP in

Fig 6.11 to Fig 6.14 indicate how the proposed off-network routing approach can

115

architecturally improve large sensor network performance by offering better control

 

 

 

 

 

 

 

 

 

 

 

plane scalability.
50000 +ONCP (2 packets/sec)
-B-ONCP (4 packets/sec)
- -I— Directed Diflirsion (2 packets/sec)
8 40000 2_ -)(- Directed Difision (4 packets/sec)
-o— CBRP (2 packets/sec)
:6 + CBRP (4 packets/sec)
B .:
IS 30000 ——
C1
.2
8
‘a 20000 _._
E
{3 10000 -~
0 I I I I I I I I
l 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.14: Communication energy consumption at rates of 2 and 4 packet /sec

6.2.2 The Scenarios with Multiple Base Stations

In the second set of experiments, we evaluate the impacts of multiple base stations
for all three protocols. Compared with single base station, multiple base stations offer
several benefits: (1) decrease the number of transmissions needed for the packets to be
routed from target nodes to a base station; (2) increase the effective data collection
bandwidth; (3) reduce control overheads and provide better control granularity, which
is unique under the ONCP architecture.

In the multiple base stations scenarios, we experiment with both 2 and 4 base stations

with the same user client requests as in the experiments with single base station. The

116

base stations are placed near the center of the network where one base station does not
share the host region with others. For ONCP, when user client generate application
requests, the global path and designated base station is computed by the ONCP server.
So the base station collecting the data for user requests is determined at run-time.
However, the directed diffusion and CBRP protocols do not have a centralized server to
decide the nm-time base station selection. For comparisons, we manually specify their
base station selections which are the closest to the target areas for the client requests.

Normalized Protocol Overhead: The normalized protocol overhead for two and four
base stations scenarios are presented from Fig 6.15 to Fig. 6.18. It is observable that
multiple base stations do not favor normalized protocol overhead. Compared with
single base station scenario, at the same traffic load (packet rate and nodes per target
area), the overhead under multiple base stations is very similar. Although the total
number of transmitted packets network-widely per delivered data packet is reduced for
all the cases, the average hops are reduced even more. As a result, the normalized
protocol overhead does not decrease.

These results also support the claim that ONCP has fundamental architectural
benefits of reducing control overhead compared to the completely distributed protocols
and hierarchical cluster-based protocols. With increased traffic load, the normalized
overhead of ONCP is decreasing, as non-data traffic has smaller percentage in the total
transmissions. Directed Diffusion and CBRP show non-monotonical trends at higher
traffic load. The reason is that the significant packet drops due to congestion offset the

effects of the reduced overhead. These results confirm our observations at single base

117

station scenarios in Fig. 6.3, Fig. 6.4.

 

 

80

  

_ Directed __.7 :
Diffusion

 

60 W
-B- ONCP l ackets/seg)

—I— Directe bn E0. packets/sec)
-)(-Directed Dillirsion l packets/sec)
—e— CBRP E05 packets/sec)
-)I(—CBRP l packets/sec)

ONCP

' +ONCP305 packets/sec)

 

 

 

 

   
 

Normalized Protocol Overhead
b
O

 

 

 

 

2 3 4 5 6 7 8
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.15: Normalized protocol overhead at rates of 0.5 and 1 packet/sec (2 BS)

 

 

40

 

+ONCP (2 packets/sec)
'5- ONCP (4 packets/sec)
—l— Directed Diffusion (2 packets/sec)
-)(- Directed Diflirsion (4 packets/sec)
Directed —e—- CBRP (2 packets/sec)

. . —)tt— CBRP (4 packets/sec)
Diffusron ,

Xa\m

Va? . : ONCP
\— e #e

1

 

 

 

 

 

 

 

Normalized PrIoItocol Overhead
O

I)
“38>

C
“36>

 

 

 

2 3 4 5 7 8
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.16: Normalized protocol overhead at rates of 2 and 4 packet/sec (2 BS)

118

 

 

00

O
I
I

  
   
  
 

    

 

 

 

  
 

   

 

60 \ L :gjgg E0. .5 piclg/m/sec)
2- - -8- ac e sec
Directed ficifig néo pfké/ts/sgc)
- - —)(—D1rel)iflirs'nn 1 ac e sec
Drffusron -e— CBRP E0. .5 packets/55c)
I —)tt—CBRP 1packets/sec) 4X
40 __

Normalized Protocol Overhead

N
o
‘ O
03 .
E
3
’ 0
pg
>

[NE <>

 

IlaE<

 

 

 

 

l 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.17: Normalized protocol overhead at rates of 0.5 and 1 packet/sec (4 BS)

 

 

 

 

 

-0- ONCP (2 packets/sec)
D. t d -E-ONCP (4 packets/sec)
“60 ‘3 -+-Directed Diflirsbn (2 packets/sec)
Diffusion -)(- Directed Difirsion (4 packets/sec)
. —o— CBRP (2 packets/sec)
x : -x—- CBRP (4 packetslsecl/
20 —~ - . -

 

 

 

 

 

Normalized Protocol Overhead

 

 

 

 

 

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.18: Normalized protocol overhead at rates of 2 and 4 packet/sec (4 BS)

119

Expected Packet Delivery Ratio: the expected packet delivery ratios for multiple
base stations are presented in Fig. 6.19 to Fig. 6.22. Although multiple base stations do
not help to improve the normalized protocol overhead, they are able to significantly
increase the expected packet delivery ratio. For example, at the highest traffic load we
experiment (at packet rate 4 packet/sec and 9 nodes per target area), the delivery ratio of
Directed Diffusion is improved from about 50% and 100% (from 21% ~ to 31% and
38%) for two and four base stations respectively. And CBRP protocol improves from
58% to 75% and 79%, while ONCP is from 76% to 85% and 88% for two and four base
stations scenarios. The percentage improvement for ONCP protocol is not as much as
the other two protocols, because the performance under one base station scenario is
already reasonably good.

In our application data model, user clients generate asynchronous requests to collect
the real-time data from multiple base stations. As a result, data traffic load will
concentrate at the base stations where the nodes near the base stations become the
bottleneck nodes. More number of base stations actually increases the effective
bandwidth for data collection, thus improving the expected delivery ratio, especially
under congestion condition. As evident from Fig. 6.19 to Fig. 6.22, the ONCP protocol
manages to defer the delivery ratio degradation problem significantly by avoiding
congestion in the network through off-network routing which helps to avoid expensive
network-wide flooding. ONCP manages to maintain nearly 90% expected delivery

ratio.

120

 

 

.O

_ 00
I
I

    
 

9
O\
I
I

Directed
Diffusion

.o
4;
I

 

-0-ONCP (0.5 packets/sec)
-E-ONCP (1 packets/sec)
—I—Directed Diflision (0.5 packets/sec) . - . _
-)(- Directed Diflision (l packets/sec)
—-e— CBRP (0.5 packets/sec)

—I— CBRP (1 packets/sec)

Expected Packet Delivery Ratio

_O
N
I
I

 

 

 

I l I I I | I I
I I I I I | I I

 

 

O

1 2 3 4 5 6 7
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.19: Expected packet delivery ratio at rates of 0.5 and 1 packet/sec (2 BS)

 

 

     
 

 

 

 

 

 

 

 

 

l
.9.
Igor ~—
.2
T)
Q 0.6 r ,
1'5 Drrected /,.,
é Diffusion
‘1' 0.4 W
E
8 -0- ONCP E2 packets/sec
p, -B- ONCP 4 packets/sec
>< 0.2 ~~ -I— Directed Drflirsron (2 packets/sng
LU -)(— Directed Diflirsion (4 ackets/sec
—e— CBRP (2 packets/sec?
—+— CBRP 4 packets/sec . :
0 I I I I I I I I
l 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

Fig. 6.20: Expected packet delivery ratio at rates of 2 and 4 packet/sec (2 BS)

121

 

 

 

    
 

 

 

 

 

 

 

l

.2

'EI

04 0.8 ——

E:

<1)
.2

B 0.6 ‘— Directed

g Diffusion

«3 .

m 0.4 I I

:3: +0NCP (0. 5 packets/sec)

8 ~B—ONCP (1 Dpackets/sec)

g -t-Dme DmectedD Ifliisnn (0 5 packets/sec)

K 0.2 7‘ -)(-Directed Difiiision(l packets/sec)

m --e-— CBRP (0.5 packets/sec)

—+— CBRP (1 packets/sec)
0 I I I I I I I I
l 2 3 4 5 6 7 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.21: Expected packet delivery ratio at rates of 0.5 and 1 packet/sec (4 BS)

 

 

    
 

 

 

 

 

 

 

l

.9
‘65
a; 0.8 —~
0
.2
T)
D 0.6 -— .
3 D1rected
fig Diffiision
9* 0.4 w
B
8 + ONCP (2 packets/sng
Q -E—ONCP (4 ackets/sec
X 02 -- -I-Directed ion E2 packets/sec;
ELI +Directed Difliision ackets/sec

-—e—— CBRP E2 packets/sec)

—I—- CBRP 4 packets/sec)

I I J 4 I | I |
O I I I I | I I I
2 3 4 5 6 7 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.22: Expected packet delivery ratio at rates of 2 and 4 packet/sec (4 BS)

122

End-to-End Delivery Latency and Average Hops: we present the end to end delivery
latency and average hops for data packets in Fig. 6.23 to Fig. 6.30. As in the single base
station scenarios, when the trafiic load is low (number of nodes per target area is 1 or 2),
CBRP and Directed Diffusion have the smaller delay of around 0.06 second, and the
delay of ONCP is approximately 0.10 second. This is confirmed by the average hops of
data transmissions: around 15, 17, and 25 for Directed Diffusion, CBRP and ONCP
protocols. The imposed region infrastructure for ONCP global routing make ONCP
goes longer paths. It is one of the limitations of ONCP architecture. Meanwhile, CBRP
also has longer paths than Directed Difiusion because of cluster infrastructure. In the

low traflic range, all three protocols have comparative delay.

 

 

 

 

 

 

 

 

 

l .5

>5 : I

o ‘ ' I
§ +ONCP (0.5 packets/sec) ' I
3 -B- ONCP (l packets/sec) ‘ . i

12‘ -+— D'rected Diflixsion (0.5 packets/sec)

a) -)(- Diected Difixsion (1 packets/sec) I
g 1 ‘” 4» CBRP (0.5 packets/sec) =
8 -)|(— CBRP (1 packets/sec) f
1:: I

C‘. T
”-1 I

0 I
13 ——

a 0.5 :
m

D I

00 I

“5

h .

a) .

> I
< I I I l I l l I

0 I F 7 I I I I I I
1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.23: End to end packet delivery latency at rates of 0.5 and 1 packet/sec (2 BS)

123

 

 

U)

 

-0-ONCP (2 packets/sec)
-E-ONCP (4 packets/sec)
—|- Di‘ected Diflision (2 packets/sec)
-)(- D'rected Difliis'nn (4 packets/sec)
-—e- CBRP (2 packets/sec)
-)IE- CBRP (4 packets/sec)

N
I
I

 

 

 

Average End to End Delivery Latency

 

 

 

I
u—l
—
—-1

l
_I
.—

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.24: End to end packet delivery latency at rates of 2 and 4 packet/sec (2 BS)

However, with increasing traffic load, the delay for Directed Diffusion escalates
faster than the other protocols. Higher congestion, and subsequent packet queuing and
MAC layer retransmissions accounts for its higher delay in high traffic load range. The
effects of relatively aggravated congestion in Directed Diffusion are apparent in the
figures.

It is noticeable that for all three protocols multiple base stations substantially
decrease the end-to-end delay because of 1) shorter paths; 2) less network congestion.
For ONCP, since there is very little congestion, the first reason plays a major role. For
Directed Diffusion and CBRP, however, congestion mitigation is the primary reason for

the delay reduction.

124

 

 

1.5 . :

 

+ONCP (0.5 packets/sec)

-B- ONCP (1 packets/sec)

—I— Directed Diffusion (0.5 packets/sec)
-)(- Directed Difliision (1 packets/sec)
-1 " «I... CBRP (0.5 packets/sec)

-)I(- CBRP (1 packets/sec)

  
    

 

 

 

0.5 ‘—

 

Average End to End Delivery Latency

 

 

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

Fig. 6.25: End to end packet delivery latency at rates of 0.5 and 1 packet/sec (4 BS)

 

 

 

 

 

 

 

3 ,

>5 .

g -0- ONCP (2 packets/sec)

33‘; -B- ONCP (4 packets/sec)
...1 -l— Directed Difliision (2 packets/sec)

t‘ -)(- Directed Difiis'nn (4 packets/sec)

“>9 2 __ -—€>- CBRP (2 packets/sec)
:73 -)I(— CBRP (4 packets/sec)
Q ‘ .
'O

1:

LL]

8

I6 ...—

G 1

LL]

8;

:3

cu .. ’5
> I I,
< ’4 C " ‘ " .. . >

O " _'-““__ I I I I I I

 

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 6.26: End to end packet delivery latency at rates of 2 and 4 packet/sec (4 BS)

125

 

 

 

 

 

 

 

 

 

 

 

 

3 O
__ CBRP
a 20 ,
O
:1: . \ , '
g ark
«I ' ‘
83 ‘ U +0NCP (0.5 packets/sec)
E '9-ONCP (1 packets/sec)
10 . ' - - "I— Directed Diffusion (0.5 packets/sec)
D1rected 9(— Directed Diffusion (1 packets/sec)
- - + CBRP (0.5 packets/sec)
Diffusmn + CBRP (1 packets/sec)
0 I I I I I I I I
l 8 9

 

2 3 4 5 6 7
Number of Nodes Per Target Area (B)

 

Fig 6.27: Average hop counts at rates of 0.5 and 1 packet/sec (2 BS)

 

 

30

Average Hops
N
O

p—d
O

0

L

 

 

 

 

 

 

v

Directed U ONCP

/ Diffusion

 

  

 

    
 
    

I
I

CBRP 3

 

I
I

'0' ONCP (2 packets/sec)
'5' ONCP (4 packets/sec)
"I— Directed DiffiIsion (2 packets/sec)
-)(- Directed fousion (4 packets/sec)
—9— CBRP (2 packets/sec)
-)K- CBRP (4 packets/sec)

l I l l l l I l

 

 

| | I I I I | I

1 2 3 4 5 6 7
Number of Nodes Per Target Area (B)

 

 

 

Fig 6.28: Average hop counts at rates of 2 and 4 packet/sec (2 BS)

126

 

 

 

N
O
I
I

p—n
O
l
l

Average Hops

 

 

Directed Diffusion

 

+ONCP (0.5 packets/sec)
'E-ONCP (l packets/sec)
-l—Directed Diffusion (0.5 packets/sec)
-)(—Directed Diffusion (l packets/sec)
-0- CBRP (0.5 packets/sec)

-)K- CBRP (l packets/sec)

 

 

 

l i i I 1 i I I

 

1

I I l I l

2 3 4 5 6 7 8
Number of Nodes Per Target Area (B)

 

Fig 6.29: Average hop counts at rates of 0.5 and l packet/sec (4 BS)

 

 

 

[\J

O
l
I

H
O
l
I

Average Hops

 

  

Directed
Diffusion

 
 

 

 

 

'0'- ONCP (2 packets/sec)
'5- ONCP (4 packets/sec)
-+- Directed Diffusion (2 packets/sec)
+ Directed Diffusion (4 packets/sec)
-9- CBRP (2 packets/sec)
-)l(- CBRP (4 packets/sec)

 

 

 

 

l

i I I I i i

2 3 4 5 6 7 8
Number of Nodes Per Target Area (B)

 

Fig 6.30: Average hop counts at rates of 2 and 4 packet/sec (4 BS)

127

 

 

Average Enemy Dissipation: Average energy dissipation for multiple base stations
are shown in Fig 6.31 to Fig. 6.34. As in the single base station scenarios, the dissipated
energy decreases with higher packet rates for all three protocols. This is because at
lower rates, due to MAC layer idling and overbearing, a large part of the consumed
energy is not actually used for data packet transmissions. With increasing traffic loads,
and correspondingly more received packets, however, the effects of idling and
overbearing reduces gradually, which causes the dissipated energy numbers to improve.

Similar trends can be also observed with increasing number of nodes per target area.
In spite of its more data packet transmissions (larger hop counts), and region status
updates, ONCP is able to sustain better energy performance by avoiding the aggressive
flooding using its server based architecture. Less packet drops for ONCP also help to
keep the energy expenditure low. Although ONCP reduces around half of total network
transmissions than Directed Difiusion, these benefits do not reflect significantly in the
energy dissipation because the idling energy dominates the total energy expenditure.
For the same reason, multiple base stations do not help much to reduce the energy

dissipation.

128

 

 

 

0.06

 

+ ONCP (0.5 packets/sec)
-S-ONCP (1 packets/sec)

0.05 W ‘ ' —I-Directed Diffusion (0.5 packets/sec)
-)(- Directed Difli.Ision (1 packets/sec)
~e~ CBRP (0.5 packets/sec)

004 __ . _, . —I—CBRP(1packets/sec)

 

 

 

    

0.03 ‘—

0.02 ‘—

 

0.01 *—

Dissipated Energyy (J/node/packet)

 

 

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

Fig. 6.31: Average dissipated energy at rates of 0.5 and 1 packet /sec (2 BS)

 

 

 

 

 

 

 

 

 

0.02 p

A ‘0' ONCP (2 packets/sec)

‘5 -EI-0NCP (4 packets/sec)

AC4) . —I— Directed Difiiision (2 packets/sec)
8. 0 015 ——- . . . -)(-Directed Diflilsion (4 packets/sec)
B . «ti- CBRP (2 packets/sec)

8 —I— CBRP (4 packets/sec)

g .

V

g: 0.01 -—

DD

3";

8:

LL]

'8 __

.5 0.005

.9

CD

.9

Q

0

 

 

 

1 2 3 4 5 6 7 8
Number of Nodes Per Target Area (B)

 

Fig. 6.32: Average dissipated energy at rates of 2 and 4 packet /sec (2 BS)

129

 

 

 

 

 

0.06

 

+0NCP (0.5 packets/sec)

-E- ONCP (1 packets/sec)
' -+—Direc Diffusion (0.5 packets/sec)
-)(- Directed Diflirsion (1 packets/sec)
-—<'.-— CBRP (0.5 packets/sec)
0 04 __ 7 -1—CBRP (1 packets/sec)

0.05 '—

 

 

 

0.03 "—

0.02 ‘*

 

0.01 ‘—

Dissipated Energyy (J/node/packet)

 

 

 

 

 

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

Fig. 6.33: Average dissipated energy at rates of 0.5 and 1 packet /sec (4 BS)

 

 

 

0.015

 

-0- ONCP (2 packets/sec)
-B- ONCP (4 packets/sec)
—1— Directed Diflision (2 packets/sec)
-)(- Directed Difliision (4 packets/sec)
- -—e—~ CBRP (2 packets/sec)
0.01 -— ' —+-— CBRP (4 packets/sec)

 

 

 

 

0.005 “

Dissipated Energyy (J/node/packet)

 

 

 

 

1 2 3 4 5 6 7 8
Number of Nodes Per Target Area (B)

 

Fig. 6.34: Average dissipated energy at rates of 2 and 4 packet /sec (4 BS)

130

 

 

6.2.3 Impacts of Region Status Updates

We have designed experiments with sensor node failures in order to study the
sensitivity of ONCP routing on the frequency of region status updates. We model the
grouped node failures (certain percent of all nodes) that allow certain fraction of the
network nodes to fail over a preset duration The groups are deliberately chosen such
that a group failure will cause a region failure, and if the ONCP server is not updated by
the region status, then the global path selection will lead to inaccurate routes. For the
following experiments, the data rate is set to be 4 packets per second, and the number of
node per target area is set to be 6.

Fig. 6.35 : 3) depicts the impacts of status update intervals on the expected packet
delivery ratio at the rates of 0%, 5%, 10%, and 15% group node failures. At 0% failures,
with increasing status update frequency the expected delivery ratio decreases due to
mild congestion contributed by the status update traffic. For higher node failures,
however, frequent status updates help the ONCP server computing better energy
distributed global paths, which result in higher delivery ratios. With very frequent
updates (more than 50 update cycles per see), the delivery ratio drops because of the
congestion due to the status update traflic.

In the presence of group node failures, an invalid global path is defined as one that is
mistakenly computed through at least one failed region (caused by group node failures).
As shown in Fig. 6.35: b), with frequent status updates (smaller than 50 seconds per
update circle) the ONCP server is able to compute valid global routes for all the nodes

failure cases. With less frequent updates, however, the quality of the global paths

131

degrades depending on the severity of the node failures.

 

 

   
 
 

   
 
 
  

 

 

 

 

 

 

     
  

 

 

 

0.9 ~--- -—-~—-----—
,_, 0.8 ,. _. .
:3 2 :
33 g 0.7-* -‘ ,., 0%NodeFailure
B, E‘ 0-6 “’ 5% Node Failure
> . . ,
3% 0-5 “t , 10% Node Failure .
’ 15% Node Failure . .
0.3 r r : r r 4 I. I. 4
900 600 300 150 100 50 25 IO 5
Status Update Interval (seconds)
. l " 5 M M
'0
9:. E 0.8 -- g - , 0% Node Failure
3 3‘ 0.7 ~- ~ . . . 5% Node Failure
g 8 0.6 e 10% Node Failure
“‘ 0'5 ‘” 15% Node Failure ' “ .
0.4 i l t i i i l i i
900 600 300 150 100 50 25 10 5
Status Update Interval (seconds)

 

 

Fig. 6.35: Impacts of node failures on a) delivery performance and
b) quality of global routes

For similar reasons, with frequent updates, the delivery ratio improves because of
better quality global routes. With better delivery ratio, the energy dissipation numbers
also improves in Fig. 6.36. With very frequent status updates (smaller than 50 seconds
per update circle), however, the update packets contributes to the network congestion
and subsequent packet drops, which degrade the energy dissipation numbers.

In general, the results in this section indicate that the status update frequency needs to
be properly dimensioned in order to maximally leverage the off-network routing

mechanism offered by the ONCP architecture.

132

 

 

0.0024

       
  

0-0021 “ 0% Ndde Failure

% iNode Failure
10% Nede Perm

I

0.0018 ~ re- - -

   

0.0015 ‘—

Dissipated Energy (J/Node/Packet)

 

 

l I
I l l l I

 

0.0012

900 600 300 150 100 50 25 10 5
Status Update Interval (seconds)

 

 

 

Fig. 6.36: Impacts of status update on energy dissipation

6.2.4 Impacts of Network Size

In this set of experiments, we study the impacts of the network size on three
protocols. The network size is varied from 900, 1764 to 2916 nodes, with one base
station deployed at the center. The same data model is used as the previous experiments.
For ONCP, we keep the same region size (36 nodes per region) for the three different
network sizes.

Fig. 6.37 depicts the expected packet delivery ratio at the rate of 2 packets per
second and the number of nodes per target area B = 6. With larger network size, the
overall transmissions increase inevitably. Then the corresponding congestion will cause
the performance of all three protocols to degrade. ONCP demonstrates the smallest

decrease in the delivery ratio, as it is able to avoid the network-wide flooding. In

133

contrast, Directed Diffusion and CBRP have a sharper decrease of delivery ratio due to

more congestion. The three protocols have similar trends at other data rates.

 

 

 

[ ONCP m CBRP a Directed Dining

 

Expected Packet Delivery Ratio

 

 

 

i

900 1 764 291 6
Fig. 6.37: Expected packet delivery ratio (B =6)

 

 

 

The communication energy consumption results in Fig. 6.38 also prove the
scalability of ONCP. It compares the energy consumption of three protocols at the rate
of 2 packets per second and the number of nodes per target area B = 6. With larger
network size, energy consumption of all three protocols should increase because of
longer paths from target nodes to the base station and more routing overhead. ONCP
has not only the least energy consumption, but also the smallest increase rate regarding
to the network size. The energy consumption normalized by the network size is 3.09,
2.13, 1.80 J/node for ONCP, 3.39, 3.00, 3.15 J/node for CBRP, and 9.19, 9.28, 8.63
J/node for Directed Diffusion under 900, 1764, 2916 nodes network. These results

indicate that ONCP can architecturally improve energy performance by offering better

134

control plane scalability.

 

 

30000

 

ONCP ll] CBRP E Directed Diffusion

 

20000 —

10000 “

Communication Energy Consumption (J)

 

 

 

0—

 

900 1764 2916

 

 

Fig. 6.38: Communication energy consumption (B =6)

6.2.5 Summary

In this chapter, we characterize the performance of proposed ONCP protocol in
relation to the existing flat sensor routing protocol Directed Difl‘usion and hierarchical
cluster-based protocol CBRP through extensive simulations on one-, two- and
four-base station scenarios. The results for the one-base station indicate that for large
sensor networks with realistic data models, the normalized protocol overhead, expected
delivery ratio, latency and energy performance of ONCP can be significantly better
than those of Directed Diffusion and CBRP.

Multiple base stations improve the performance of all three protocols by reducing

the number of transmissions from target sensor nodes to base stations and increasing

135

effective data collection bandwidth. The percentage improvement of ONCP is not as
much as the other two protocols, as the performance under single base station scenarios
is already reasonably good. All the results support the claim that ONCP has
fundamental architectural benefits of reducing control overhead compared with
distributed flat protocols and hierarchical protocols.

We also evaluate the impacts of region status updates rates in the presence of grouped
node failures. It indicates that the status update frequency needs to be properly
dimensioned to leverage our off-network routing mechanism. The proper update rate
should consider both the global path selection and the overhead associated with status

updates.

136

Chapter 7
Off-Network Control Processing (ONCP) with Sink Mobility

In this chapter, we investigate the usage of sink mobility to improve the network
performance in wireless sensor networks, especially for the network lifetime. A large
class of applications requires that only a few sinks (base stations) can collect the
real-time data from the whole network, which results in a non-uniform traffic load /
energy dissipation distribution in the network. Although many energy efficient routing
and MAC protocols have been proposed for wireless sensor networks, the
concentration of data traffic towards a small number of base stations remains a big
threat to the network lifetime. The sensor nodes close to a base station not only generate
their own data, but also need to relay data from a large part of the network. As a result,
those nodes deplete their energy faster than other nodes in the networks, thus bounding
the network lifetime.

However, if a base station can change its position over time, then the traffic load and
energy dissipation will be more evenly balanced. Although a base station usually
assumes to be static, recent advances [71, 74, 75, 78, and 87] allow sink mobility in
various network environments. We will investigate the problem of energy balance
under the framework of ONCP in wireless sensor networks by incorporating sink
mobility.

7.1 Motivation and Problem Description
Wireless sensor networks can be viewed as a large collection of sensor nodes which

form ad hoc distributed sensing and data collection networks. In a large class of

137

applications, these networks are deployed in fields for monitoring. Energy is the most
precious resource of wireless sensor networks, as it is infeasible to replace nodes’
batteries once they are deployed into the environment. In most scenarios, the collected
data is disseminated to one or a few static sinks (base stations) through multiple hop
propagation.

In such approaches, as data traffic become concentrated towards the sinks, the sensor
nodes close to the sinks will have heavier energy burden, leading to non-uniform
energy dissipation. Once the nodes with direct connection with sink exhaust their
energy, the sink is disconnected from the network, which is regarded as the end of the
network lifetime. Clearly the network lifetime is bounded by the energy deposits of the
bottleneck nodes near the sinks.

A lot of energy conservation communication protocols have been proposed recently,
including energy efficient routing [58, 59, 60, 61], topology control [62, 63, 64, 65, 66],
MAC [5, 16 30, 31, 33, 36]. These protocols can achieve their optimization goals under
certain conditions, but the network lifetime problem still exits because of the inherent
data concentration characteristics of such applications. The energy optimization
techniques can not directly lead to traffic load balance in the network. However, the
network lifetime can be significantly enhanced if the bottleneck nodes can be changed
over time.

An alternative is to introduce mobility into the system to avoid excessive data relay
for the nodes near a sink. In such scenarios, nodes are attached to robots, vehicles,

animals or people [68, 73], which can traverse the network area to collect data. The

138

mobile nodes in this case are part of network infrastructure, and their mobility is
autonomously controlled either by the network or the network administrator. Recent
research trends start to shift the energy burden from sensor nodes to the sink [91, 93].
The sink is assumed to have significant and replaceable energy sources, and can move
in the areas where a sensor network is deployed. When a mobile sink moves close to the
target sensor nodes, it can acquire data more efficiently. The node mobility naturally
lessens the need for multi-hop data relaying, and balances the energy dissipation in the
network, increasing the network lifetime.

In delay tolerant applications [67 , 68, 69, 70], researchers are interested in studying
the environmental behaviors and do not need the real-time data collection. So the
transmission latency incurred by mobility is not the primary concern. When data is
generated and does not have paths to arrive to a sink, it is stored in a local buffer until a
mobile sink moves into close proximity. Mobility also can provide advantage in sparse
or disconnected network, which is caused by the constraint of physical environment,
coverage requirement, cost, security management, etc. The mobility allows monitoring
the environment with fewer sensor nodes, reducing the operational costs. It also lessens
the requirement to use high radio power to keep the network connected, which grows
exponentially (typically between the order of 2 and 4) with transmission range.

Moreover, mobile sinks are able to achieve the increased throughput and data fidelity.
By reducing the number of hops, the probability of transmission error and required

bandwidth also decrease.

139

7.2 Related Work

Recently, significant research motivating mobility for data collection in wireless
sensor networks has been proposed. Based on the mobility model, these approaches
can be generally classified as random, predictable, and controllable.

Random Mobility: In random mobility, sink nodes are assumed to randomly move
within the sensing field and collect data opportunistically from the sensor nodes. Data
Mule is proposed in [68] to exploit the mobility for energy efficient non real-time data
collection in sparse sensor network as an alternative to ad-hoc networks. A mobile sink
is utilized as data forwarder to collect data from network. As it moves in close
proximity to sensors, data is transferred to the sink for late depositing at destinations.

FRESH suggests an alternative for eflicient routing discovery [71]. Nodes memorize
the encounter of other nodes and use this information for routing search. The source
node searches for any intermediate node that encounters the destination more recently,
other than searching for the destination directly. The intermediate node then searches
for the next node that encountered the destination even more recently. The process
continues until the destination is reached. Therefore FRESH avoids the network-wide
search with a succession of smaller searches, resulting in a cheaper route discovery in a
mobile environment.

Random motion is also proposed to collect data in large wild areas from animals as
whale [73] and zebras [74]. They explore the ideas to perform studies of animal
migrations and inter-species interactions. The collected data are exchanged between

animals and uploaded to access points utilizing animals’ mobility. However, under

140

random mobility scenarios, the worst case latency of transmission is not bounded,
which may lead to buffer overflow and significant data loss.

Predictable Mobility: In predictable mobility model, the motion of mobile sinks is
known or can be learned from node contact. In [75], a mobile observer (sink) is
mounted on a public transportation vehicle that traverses campus with a pre-determined
periodic schedule. When the sink moves close to sensor devices, it wakes up them and
collects data. Since transmission only incurred when the sink and sensors are within
direct radio range, the power requirements are significantly reduced. In [76] authors
derive a link cost for each pair of nodes from historical connectivity. It takes account of
the number of transitions from disconnected states to connected state between pairs of
nodes, and duration of disconnection. The proposed routing algorithm is based on the
link cost to minimize the data delivery latency.

Controllable Mobility: In controllable mobility, not only the node motion is known,
but also it can be controlled and driven by current network status, which gives
significant flexibility to enhance network performance. To mitigate the problem of data
concentration, a joint mobility and routing algorithm is proposed to increase the
network lifetime in [77]. It leads to more uniform energy dissipation among the
network by repeatedly relocating the sink, which correspondingly changes the
bottleneck nodes near the sink. However, it does not consider reducing the overall
energy dissipation.

Wang et a1. [78] explores sink mobility to increase sensor network lifetime by

determining the movement of the sink and sojourn time at different points. A novel

141

linear programming formulation is employed to decide which nodes to be visited by the
sink and how long should the sink stay to maximize network lifetime. Yet both
approaches need to know the initial energy of all nodes and the traffic load profile,
which is not feasible in a practical system.

7.3 ONCP-M: Off-Network Control Processing with Sink Mobility

7.3.1 Network and Data Model for ONCP with Sink Mobility

We adhere to most parts of network and data models as in section 3.2. Multiple
mobile sinks (base stations) are connected to an Ofl-Network Control Processing
(ONCP) server through a low-latency wireless network, which is used for network
status update, application request dissemination and data collection from the sensor
network as shown in Fig. 7.1. Sensor nodes are static and pre-designed region ID at
deployment. We extend our previous assumption that a base station is attached to a
mobile element, and can change its position as instructed by ONCP server. This fact
states that the controllable mobility model is adopted. In addition, it is assumed that the
base stations have plentiful energy reserves and can replenish energy [65, 66, 67, 71,
and 72].

As our previous application model in section 3.2, user clients are connected to ONCP
server and generate asynchronous sensing tasks. When the ONCP server receives
sensing tasks, it decides the global region level routing paths and forwards sensing
tasks to a base station for command propagation. After corresponding sensor nodes
receive a task request, they start generating data which are routing back to the user

client through the hybrid routing mechanisms.

142

ONCP server periodically collects network status and decides the movement of base
stations based on the overall network information. To simplify the support of the
mobility, it is assumed that the movement of the base stations is fully controlled by
ONCP server. A base station resides statically to collect the real-time data unless it is
instructed to change its location by the server. And the movement only happens
between the intervals of sensing tasks. Therefore, the routing and data collection
processes will not be interrupted by the movement of base stations. The mobility will
impact the traffic load and energy dissipation distributions across the network. It is also
assumed that the sojourn time of a base station at a given location is significantly larger

than the traveling time to the new location, so that the impacts of moving speed are

 

 

 

 

 

    

 

      

 

 

negligible.
User-1 User-2 User-n
‘ ! 4 o 000 o o o *
[ 'eeuemerreeada preeeserng ‘ ’ |
ONCP Sewer .
Commands
Data/Events T /Relocation
. Mobile _ ‘
Sensors Freld River 3333”,”- : :
Bottleneck , If“)? . \ Rg/‘I :
Nodes ~ ' 5 _____ ,. l :
Mobile = -- M ' Mobile: :
.- ~. 5' ‘L - '
BS-1 ._‘ ”’31. ‘ _ ~ , 3‘4 : 5
‘5 ::"'"'-.”’ '\ . .a . ' .
‘* z in. x "i ‘3 «a r :
. Mobile % "L ------------- > .
I ' 38 Regions '
L ..................................... ..J

 

 

Fig. 7.1: Network and Application Model with Mobile Base Stations

143

7.3.2 Extensions of ONCP Framework

ONCP-M has the same architecture components as regular ONCP described in chapter
3, such as Region Management, Cluster Organization, Status Updates, Global Routing,
Command & Global Routing Download, and In-network Local Routing. However, to
support the sink mobility, we need to extend some network services. The followings
only focus the differences between ONCP-M and ONCP.

Relocation Detection: To perform the sink mobility, it is necessary to detect the
bottleneck nodes. Because of the characteristics of data concentration, this problem
happens at the nodes close to a base station. By “neighbor hello” messages, a base
station can only detect the energy levels of its l-hop neighbors, which is not sufficient
to make the relocation decisions. The reason is that ONCP server does not have
node-specific information; it does not know whether the nodes farther have better or
worse energy situations.

Fortunately, through network status updates the ONCP server can get the overall
network information at the region level. When a base station stays in a region for a long
time, that region will deplete energy faster than other parts of network because of traffic
concentration toward sinks. When ONCP server detects such situation happens, it will
instruct the base station to move toward other regions between the intervals of user
requests.

Status Ugdates: in ONCP —M architecture, the status updates mechanism needs to be
extended. The approach described in Section 3.4.3 uses the low-cost spanning trees,

which are rooted at the base stations and spanning across the region representatives, to

144

collect region level status updates. Under the mobility scenarios, when a base station
changes its location, the original spanning trees will break Thus it is necessary to
update the low-cost spanning trees over time. Since the movement of a base station is
controlled by the ONCP server, the server can decide the timing to update the low-cost
spanning trees. And it is not expected that a base station will relocate frequently, the
additional costs of rebuilding the spanning trees will not increase much.

The updated status information from region representatives is maintained as soft
state on the ONCP server. It will be timed out to reflect the region - level status changes,
unless refreshed by new updates from region representatives. The state complexity of
updates is at the order of the region number.

Joint Mobility and Routing Strategy: In static networks, as data traffic concentrates
toward a few base stations, the nodes around a base station have to relay data for a large
number of other nodes. This data concentration will cause uneven energy distribution,
no matter what energy conserving protocols are used. As a result, those bottleneck
nodes close to base stations will deplete energy faster than the rest of the network, thus
bounding the lifetime of the network.

A mobile base station can distribute the “hot spots” spatially, such that the energy
dissipation will be balanced across the network. Based on the network conditions, the
ONCP server instructs a base station to move to other regions, which have more energy.
Traditionally, the mobility strategy and routing strategy are considered separately.
From example, routing problem can be modeled into linear programming [77], where

the constraints are flow conservation. And mobility strategy only considers the network

145

conditions. However, the goals of these two strategies may be conflicting: energy
balance vs minimum energy dissipation. Therefore, it is necessary to consider a joint
routing and mobility strategy to achieve a better overall performance. Not only it is
desirable to make the network have balanced energy to prolong the network lifetime,
but also it is important to minimize the overall energy dissipation The details of the
joint sink relocation implementation are described in the following section.
7.3.3 Joint Sink Relocation Algorithm

We will investigate on how to optimally move a base station to collect the real-time
data in a sensor network, such that the network lifetime is maximized. Considering the
fact the traffic load is not known as a prior and flow-constrain optimization is NP-hard
[77, 87], we will develop heuristic solutions for the joint sink relocation algorithm
under ONCP architecture.

From the status updates as described in Section 3.4.3, the ONCP server knows the
aggregated region energy information and the inter-region connectivity metrics. Based
on this information, it abstracts a directed graph G, in which the vertices represent the
regions (including the base stations), and the edges represent the connectivity between
regions. The edge cost in G is defined as the corresponding inter-region connectivity
metrics and the vertex cost is defined as the aggregated nodal energy of the
corresponding region.

As the data traffic concentrates towards the base station, the region which the base
station resides in will consume more energy than the rest of the network. These facts are

updated and reflected in the directed graph G. As a result, the ONCP will decide to

146

move the base stations to other regions in the graph G. The new region the ONCP server
chooses should have higher residual energy, so that the energy dissipation across the
network can be balanced to prolong the network lifetime.

However, when a base station moves to other regions, the global routing path
selection described in Section 3.4.4 has to change accordingly, which implies the sink
relocation is a joint problem with global routing selection. The new region should be
chosen in a way so that (l) the energy dissipation across the network is balanced to
avoid “hot-spots” and (2) the overall energy consumption is minimized. These two
goals are often conflicting. For example, to balance energy often requires a base station
to move into a region at the periphery of the network. However, this will increase the
number of transmissions from the target nodes to the base stations. Considering these

facts, we rely on a heuristics-based sink relocation algorithm as described in Fig 7.2.

147

 

/* ONCP Sink Relocation Computation at the server */
Region level Graph G Construction:

Construct the region level graph G using the algorithm described in Section 3. 4. 4.

Sink Reallocation Algorithm:

//iterate all regions in the network and find the global paths for ongoing client requests
For (each vertex (region) j in the graph G) {

// if moving the sink to region j, compute the global region-level paths
For (each target region k in ongoing user client requests) {
Find the global path P1,. between regions j and k, using
the global path selection algorithm in Section 3. 4. 4;

Get the average length H,- of all the global paths ij;

//The next region should have as short a path as possible
Sort H,- in ascending order;

//The next region should also have a residual energy as high as possible

For (the first M regions in the sorted H, list) {
Choose region I; which has the highest residual aggregated energy;

Relocate the mobile base station to region r;

 

 

 

Fig. 7.2: Pseudo code for Joint Sink Relocation Algorithm

7.4 Simulation Results

We have implemented the mobility model in n32 network simulator and compared

the performance for three protocols: ONCP, Directed Diffusion and CBRP. The main

148

goal for these experiments is to investigate the impacts of mobility on the different
routing protocols, and characterize their relative benefits. In the experiments, because
of ns2’ runtime constraints for very large networks, we do not measure the network
lifetime directly; we evaluate the energy dissipation distributions and energy variance
instead, which is an indication of network lifetime [77].

Experimental Scenarios: A 2916-node static network has been created by deploying
the nodes with a uniform random distribution in a 1300m x 1300m square sensing field,
with a nodal transmission radius of 40m [3 8]. The network is configured into 81 square
regions for ONCP protocol.

As for the application model, we have simulated the same architecture as descried in
Section 3.3. Thirty user clients have been programmed to generate repeated
asynchronous sensing task requests that are targeted to randomly chosen sensing areas.
The number of nodes per target sensing area B is varied from 1 to 9.

Each sensing request requires the nodes in the target area to generate the data for 60
seconds, and two consecutive requests from the same client are separated by a uniform
randomly distributed interval between 120 sec and 360 sec. During 3300 seconds of
network simulations, each user client generates 3 sensing requests. The baseline region
status updates interval (1/ tr) is set to 300 seconds

This sensing request model ensures that the data streams are sufficiently distributed
across the network. The size of the packets sent out by sensor nodes is 64 bytes.
Experiments were carried out for data rates ranging from 0.5 packets per sec to 4

packets per sec. The same user request model is used while simulating ONCP, CBRP

149

and Directed Diffusion.

In the experiments, only the base station is mobile, the sensor nodes are static. It is
ensured that the base station does not change the location during the process of the user
clients’ sensing requests; it only moves between the intervals of user clients’ requests.
The traveling time between different locations is neglectable compared with the whole
simulation time, so the mobility does not interfere with the data collection process. At
the beginning of simulations, the base station is placed at the center of network. With
network status changing, the base station will change its position based on the
algorithms as described in section 7.3.3. In the experiments, the base station relocates 8
times.

Impacts of Mobility on ONCP Routing Architectur_e: Generally, because of our
mobility model and data model, the mobility of base station does not have significant
impacts on the performance of ONCP routing architecture. Fig 7.3 to Fig 7.7 present
the results for the normalized protocol overhead, expected packet delivery ratio,
normalized energy consumption, average end-to-end delivery latency, and average

transmission hops for ONCP and ONCP-M.

150

 

 

 

 

 

 

 

 

 

 

10 ,

-o +0.5 Packet/sec -B—l Packet/sec

E . -t- 2 Packet/sec *4 Packet/sec

a: 8 ‘" A ; —e—M-0.5 Packet/sec —t-—M-1Packet/sec

O -A-M- 2Packet/sec -B—M -4Packet/sec

'§ i

o 6 “ .

'4" , 2

O . .

H _

O4 r ; ,

E 4 \

R .- :- i

E A\‘ l _. ‘\f\‘~‘~

Z 2 ‘7 L i A - " :3 .. Mi" ..

: ?-—:___ ‘ “=-—-‘_......._.‘_ ~‘

0 r r r r : t r r

1 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 7 .3: Normalized protocol overhead

In both scenarios of ONCP with and without mobility, the normalized protocol
overhead decreases with increasing traffic (the packet rates and the number of nodes
per target area), as more data packets are received by the base station. ONCP-M has
higher average transmission hops than ONCP, which results that its normalized
overhead is slightly smaller after normalization.

Since the base station changes its position only between the intervals of user clients’
requests, the movement does not interrupt the processes of route discovery and data
forwarding. From network’s perspective, the mobility does not impact the network
congestion condition. As a result, it is shown that the packet delivery ratio changes very
little. Since the target areas are randomly distributed and the mobility requires the base

station to leave the center of the network, the average transmission hops from target

151

nodes to the base station increases from around 34 to 38 as presented in Fig 7.7. The
correspondingly more number of transmissions causes ONCP-M to have slightly worse
performances than ONCP in terms of expected delivery ratio, average end-to-end delay
and the normalized energy consumption shown in Fig 7.4, Fig 7.5, and Fig 7.6. But in
general, the impacts of mobility on ONCP routing architecture are very small for those

“network average” performance indices.

 

 

 

 

 

 

 

 

 

 

.2
13
E 0.8 ‘-
.2
5 0.6 4~
'33 , .
-§ +0.5 Packet/sec -a- 1 Packet/sec
Du 0_4 —» -l—2Packet/sec -)(-4 Packet/sec
B —e— M - 0.5 Packet/sec —+—M - r Packet/sec
8 -¢-M-2Paeket/see -E-M-4Packet/sec
o. .
X __ : .-
m OI2
0 J. t + r l r r .L

l 2 3 4 5 6 7 - 8 9
Number of Nodes Per Target Area (B)

 

 

 

Fig. 7.4: Expected packet delivery ratio

152

 

 

 

Dissipated Energyy (J/node/packet)

 

  
 
 
    

 

+0.5 Packet/sec -B— 1 Packet/sec

-l—2 Packet/sec -)(-4 Packet/sec
—o— M - 0.5 Packet/sec —+—- M - l Packet/sec

 

 

~A— M - 2 Packet/sec —B—-M - 4 Packet/sec

 

l

2 3 4 5 6 7 8
Number of Nodes Per Target Area (B)

 

Fig. 7.5: Normalized energy consumption

 

 

 

—- N

._ 'u. N u:
l l I
l I 1

Average End to End Delivery Dela)
o
in

 

 

+0.5 Packet/sec -S-1 Packet/sec

-l--2 Packet/sec *4 Packet/sec
—e— M - 0.5 Packet/sec —r— M - l Packet/sec
—A—M - 2 Packet/sec -B—M - 4 Packet/sec

 

 

 

 

1

 

2 3 5 6 7
Number of Nodes Per Target Area (B)

 

Fig. 7.6: End to end packet delivery latency

153

 

 

 

 

 

 

 

 

 

 

a +0.5 Packet/sec -S—1 Packet/sec

:3 -r-2 Packet/sec *4 Packet/sec .
€020 ‘3 -0- M - 0.5 Packet/sec —t—M - l Packet/sec l
g -A— M - 2 Packet/sec -e— M - 4 Packet/sec '
>

<

10 ~—
0 r r r r l r .L :

 

 

 

l 2 3 5 6 7
Number of Nodes Per Target Area (B)

 

 

 

Fig. 7.7: Average transmission hops

I_mpacts of Mobility on Energy Distribution: Although the mobility does not change
“average networ ” performance such as the packet delivery ratio, the overall energy
dissipation etc, it does impact the dissipated energy distributions across individual
sensor nodes. In the experiments, we measure the dissipated energy variance to
understand how the mobility aflects network performance and its relative impacts on
different routing architectures (flat, hierarchy and hybrid). For Directed Diffusion and
CBRP protocols, since they do not have the global information about the network status,
we set the base station follow the same mobility trajectory as ONCP-M in the
experiments. We measure the dissipated energy variance at different time and the

correspondingly data packets received by the base station.

154

 

 

 

 

 

 

 

 

 

 

2400 ,
+0NCP -B—ONCP-M
-9—CBRP . . -)(-CBRP-M. _
5 2000 __ -A-DrectedDrfl‘usron -E-DlectedDrflirsron-M
.5 '
5
> 1600 "—
E
E 1200 -_
m
B _
a 800 r
2 '
Q 400 —~
0 — ‘ . r I. l r r
l 2 3 4 5 6 7 8 9
Number of Nodes Per Target Area (B) (l packet/sec)

 

 

Fig. 7.8: Energy variance at data rate 1 packet per second

 

 

 

 

 

 

 

 

 

 

+0Ncr - -a-0NCP-M
4000 __ -9-CBRP *CBRP-M
8 +DirectedDiflision -B—D'rectedDiflirsion-M
.5 2 1 - 4
5 3200 -—
>
a
e 2400 ~~ .,
CI
[1.] V.
3 1600 —— . .
CU ,
.9 .~ 2 ‘ .
a 800 —— ‘ 7 = . ; = ,
: ? i ' ‘ 2 '— 3“":
slid-lit!
O ‘ _ r - T i i JI i i
1 2 4 5 6 7 8 9
Number of Nodes Per Target Area (B)(2 packets/sec)

 

 

Fig. 7.9: Energy variance at data rate 2 packets per second

From the results in Fig 7.8 to Fig 7.11, it is observable that ONCP has higher energy

155

variance than Directed Diffusion and CBRP in both static and mobility cases when the
traffic load is low (the number of nodes per target area less than 2). However, it does not
mean that ONCP has the worst network lifetime. In the cases of static base station, these
three routing protocols should have almost the same network lifetime, which is
bounded by the residual energy of sensor nodes near the base station. Since the data
traffic is concentrated toward the base station, the network lifetime is determined by the
amount of traffic data received. Different routing protocols impact the energy
distribution differently across the network. As ONCP avoids the network-wide route
discovery to save the overall energy dissipation, the global path selection may cause
unbalanced energy dissipation (nodes not on the routing paths do not need to spend
energy), which results in a higher energy variance. When the traffic load increases, the
dissipated energy variances for all three protocols will increase too. However, the
impacts of different routing architectures are significantly different ONCP architecture
has the least increase of energy variance in both static and mobile cases, compared with
Directed Diffusion and CBRP. The global path selection enables ONCP to take
advantage of nodes which have higher residual energy.

It is notable that mobility can reduce the dissipated energy variance for all three
protocols, but the efi‘ects are not the same. Mobility has the least energy variance
reduction for Directed Diffusion, as it adopts the network-wide routing discovery. The
mobility only helps to change the bottle-neck nodes near the base station. The routing
architecture of Directed Diffusion can not fully take advantage of the mobility. All the

nodes in the network are still required to dissipate energy for path discovery; even they

156

 

are not on the routing paths. Although CBRP incurs less network transmissions than
Directed Diffusion, it still has the problem of network-wide routing discovery. In
contrast, ONCP routing architecture can utilize the mobility better than those two
protocols. When the base station moves to the new positions and generates users’
requests, the global routing will selects the regions, which have higher residual energy.
The joint mobility with the global path selection helps to balance the energy
distribution among nodes. Fig. 7.10 and Fig 7.11 depict the dissipated energy variance
vs time and the received packets at a low traffic load (1 node per target area). Although
ONCP-M has larger absolute energy variance, it has the highest variance reduction, as

shown in Fig. 7.12. It can be concluded that the mobility favors the ONCP routing

 

 

 

 

architecture.
200 i .,
-0- ONCP -B— ONCP -M
-9- CBRP -A- CBRP - M
-A— D'rected Diflirsion -B- Directed Diffusion -M

 

 

p—r

Ur

O
l
I

Dissipated Energyy Variance
o. S
o o

 

 

 

420 740 1080 1460 1820 2180 2550 2890 3260
Time (seconds) (B=1; 4 packets/sec)

 

 

 

Fig. 7.10: Energy variance at different times (data rate = 4 packets per second and 1
node per target area)

157

 

 

200

 

 

 

-o— ONCP ' -a- ONCP -M
-e- CBRP -a— CBRP - M
-a- Directed Diflirsion -a— D'rected Difirs'nn -M

 

u—r

'J’I

O
l

Dissipated Energyy Variance
o. S
o o

 

 

 

 

0 5000 10000 15000 20000
The number of received packets (B=1; 4 packets/sec)

 

 

 

Fig. 7.11: Energy variance vs the received packets by the base station (data rate = 4
packets per second and 1 node per target area)

 

 

 

 

 

 

 

 

 

,, 1.2

.2

’2

a 1 w _

M - , _ -

8 -_ - ‘ .

.5 0.8

E ’3 .. - a
0.6 ‘” F = = " =

E:

g” .

c: 0.4 “T

Lu

3 ;

£02 “ +0NCP -B—CBRP -A-D'rectedDiflirsion ' ' i

'5 0 r t l r r r r r i

420 740 1080 1460 1820 2180 2550 2890 3260
Time (seconds) (B=l; 4 packets/sec)

 

 

 

Fig. 7.12: Energy variance reduction (data rate = 4 packets per second and 1 node per
target area)

Fig 7.13 shows how the mobility affects node-energy distribution for three protocols

158

at the data rate of 4 packets per second and 1 node per target area. For ONCP static case,

52.4% nodes dissipate energy in the range of [105 tol 15] J, 30.5% nodes in [115 t0125]

J, 8.6% nodes in [125 to 135], 4.2% nodes in [135 to 145] J, 1.6% nodes in [145 to 155]

J, and 1.9% nodes above 155 J. With mobility, the distribution of nodes becomes 35.6%,
35.4%, 26.9%, 2.0%, respectively, and none of nodes spend more than 145 J. For
CBRP, we observe a similar trend. 29.4%, 59.1%, 8.1%, 1.9%, 1.0% nodes in the static

case, and 25.9%, 58.1%, 15.7% 0.3%, O % nodes in mobile case.

For all protocols, mobility reduces the number of nodes in the lowest and highest
energy range. After the base station changes its position, the bottleneck nodes near the
base station are replaced, which helps to reduce the energy variance in the network It is
shown that ONCP routing architecture has the largest distribution difference between

the static and mobility cases, which confirms that it has the highest variance reduction.

 

 

 

 

 

 

 

 

70
r EONCP-S BONCP-M
60 _ ~ ~ I ODD-S EDD-M
:5 l BCBRP-S DCBRP-M
E E t.
8 a E= SE
*3 40 E \E 02
: \: ’9. .
g-D :_ s: ’9. I
E :: : s: ‘9. I ‘
U, :: : s: r. I =
.... 30 =: a: s: -’t. I i
Q :: s :: \: fit. I ;
:: s— :: s: : I. I i
0 :: \: a: s: : ’I. I ;
'8 20 55 E is :5 ._ 5: g
z 55 :5 55 \E E g»: u 3
E! \E EE ‘5 E. _ I'- 3‘ ‘
-: \z -: ‘: :r’i : '- ’ T
:. \- :. s- .p. - ’I. ’I -
10 =5 ~5 =5 ‘5 Eats “- ’t ’
=. \- =. \. ...,». - ’9. ’I
a: s: :: s: 3,»: ’I. ’I
as E as E 554:5: t» :I .
0 a; 3% a; !; ram; zeal. = II. ~_ . _ -
115 125 135 145 155 165 175 185
Energy (J) (B=1; 4 packets/sec)

 

 

 

Fig 7.13: Node-energy distribution (data rate = 4 packets per second and 1 nodes per
target area)

159

Fig. 7.14, Fig 7.15 and Fig. 7.16 visually demonstrate how mobility affects the
energy distributions across the network at the data rate of 1 packet per second and 9
nodes per target area for three protocols over time. It is clear that the mobility decreases
the maximum energy dissipations for all three protocols. But the impacts of mobility on
different routing architectures are different: ONCP-M incurs the smallest maximum
energy dissipation at around 166 J, compared with CBRP at around 206 J and Directed
Diffusion at around 371 J. The major reason is that ONCP has the smallest overall
network transmission achieved by avoiding the network-wide routing discovery
overhead.

These figures also show the impacts of different routing architectures on the energy
distribution across the nodes. It is evident that a significant part of nodes do not join
routing discovery for ONCP protocol by avoiding network-wide message
disseminations from Fig. 7.16. In contrast, Directed Difl’usion requires all the nodes to
participate in routing searching, which results in more homogenous energy distribution.
CBRP performs network-wide routing search on the basis of clusters, which requires
few transmissions than Directed Diffusion but more transmissions than ONCP. As a

result, its distribution resides between Directed Diffusion and ONCP.

160

 

Fig 7.14.B: Node-energy distribution at 1820 see (Directed Diffusion-M)

161

 

Fig 7.14.C: Node-energy distribution at 2550 see (Directed Diffusion-M)

 

Fig 7.14.D: Node-energy distribution at 3260 sec (Directed Diffusion-M)

162

 

Fig 7.15.B: Node-energy distribution at 1820 sec (CBRP-M)

163

 

Fig 7.15.C: Node-energy distribution at 2550 see (CBRP-M)

 

Fig 7.15.D: Node-energy distribution at 3260 see (CBRP-M)

 

Fig 7.16.B: Node-energy distribution at 1820 see (ONCP-M)

 

Fig 7.16.C: Node-energy distribution at 2550 see (ONCP-M)

 

Fig 7.16.D: Node-energy distribution at 3260 see (ONCP-M)

166

7.5 Summary

In this chapter, we incorporate the sink mobility into routing architecture, and
investigate its impacts on different routing protocols. When the traffrc data concentrates
toward one (or a few) data sink, the nodes near a sink deplete energy faster than other
nodes in the network, as they need to relay data for a large part of the network. This
unbalanced energy dissipation is a big threat to the network lifetime. To address this
problem, we propose a joint sink relocation algorithm to periodically change the
locations of a sink in order to balance energy dissipation across the network under
ONCP framework. We also investigate impacts of the sink mobility for the other two
routing protocols: Direct Diffusion and CBRP.

Simulation results indicate that mobility does not change the “average networ ”
performance such as the packet delivery ratio, the overall energy dissipation etc.,
except that average transmission hops are increased. However, it helps to reduce the
energy variance significantly and change the energy distributions across individual
sensor nodes for all three routing protocols. We find out that the impacts of sink
mobility on the different routing architectures are significantly different. ONCP
architecture has the smaller energy variance increase than Directed Diffusion and
CBRP with increasing traffic load. The primary reason is that the global path selection
enables ONCP to take advantage of nodes which have higher residue energy, which is

not feasible for the other two protocols.

167

Chapter 8
Summary and Future Work
8.1 Summary

In this thesis, we present a Self Reorganizing Slot Allocation (SRSA) MAC protocol
and Off-Network Control Processing (ONCP) routing architecture for wireless sensor
networks. These works address the challenges of power consumption and network
scalability issues from the medium access control and networking layer.

The design objective of SRSA MAC protocol is to devise mechanisms for
minimizing inter—cluster TDMA interference without using CDMA or FDMA. SRSA
adapts a feedback-based local allocation reorganization that can be used for minimizing
allocation interference across overlapping sensor clusters in a single channel network.
One major advantage of SRSA protocol is that it does not require any global or
neighborhood synchronization. SRSA protocol operates at the cluster level and does
not rely on any information beyond a cluster. It initiates communication with a
reasonable initial TDMA allocation and then adaptively changes the slot allocation
schedule locally based on feedback derived from collisions experienced by the local
nodes. The slot allocation is executed adaptively relying only on local information.
These features make it feasible in very large sensor networks. Comparative evaluation
shows that like plain TDMA protocols, SRSA has an order of magnitude lower energy
overhead compared to CSMA and other contention based protocols. The trade-off for
very low energy dissipation and packet drop rate is increased transmission latency.

SRSA makes an ideal medium access strategy in sensor network applications that can

168

tolerate relatively larger delay but not frequent packet drops.

In chapter 3, we present the Off-Network Control Processing (ONCP) routing
architecture to address the issue of routing scalability in very large sensor networks.
The control complexities of the existing sensor routing protocols, both node-centric and
data-centric, do not scale very well for large networks with potentially hundreds of
thousands of embedded sensor devices. We propose an architectural solution by
developing an Ofi-Network Control Processing routing framework. The key idea is to
shift a significant amount of routing frmctionality “off-networ ” to an energy-unlimited
server. This server performs “coarse grain” global route computation, while the “fine
grain” local routes are discovered solely by local sensor nodes. This partially
server-based approach allows eliminating the control messages that otherwise are
needed for distributed global route establishment. The reduction of routing control
messages by the ONCP server sustains the routing scalability in large networks. We
analytically characterize its routing overhead in relations to both flat and hierarchical
cluster-based sensor routing architectures by mathematical model in chapter 4. In
chapter 6, we have shown nsZ-based simulation results indicating that for large sensor
networks with realistic data models, the packet drop, latency and energy performance
of ONCP can be significantly better than those for flat protocols such as Directed
Diffusion and hierarchical protocols such as CBRP.

We incorporate the sink mobility into routing architecture, and investigate its impacts
on routing protocols in chapter 7. When the traffic data concentrates toward one (or a

few) data sink, the nodes near a sink deplete energy faster than other nodes in the

169

network. The unbalanced energy dissipation is a big threat to the network lifetime. To
address this problem, we propose a joint sink relocation algorithm to periodically
change the locations of a sink in order to balance energy dissipation across the network
under ONCP framework. We also investigate impacts of the sink mobility on the other
two routing protocols: Direct Difl’usion and CBRP. The simulation results indicate the
sink mobility helps to reduce the energy variance significantly and change the energy
distributions across individual sensor nodes for all three routing protocols. We also find
out that the mobility has different impacts on the different routing architectures. ONCP
architecture has smaller energy variance increase than Directed Diffusion and CBRP
with increasing traffic load. The primary reason is that the routing architecture of
ONCP enables it to take advantage of nodes which have higher residue energy, which is
not feasible for the'other two protocols.

In appendix A, a prototype system is implemented to functionally validate the ONCP
architecture concepts. And we present a set of routing APIs under the TinyOS
embedded operating system On top of the API interfaces, several applications are
developed. We also demonstrate software emulation comparison results for ONCP and
Tiny-AODV protocols.

8.2 Future Work

We highlight some of the key items that we plan to purse in the future work:

0 In chapter 2, we build a model to study the convergence of SRSA protocol. We
intend to extend the protocol analysis for analytically estimating the protocol

convergence speed. We need to identify the steady state probability of the

170

system in any state-i for all i ¢ 0. Then we evaluate the average number of
transitions required from state-i to state-0 and compute the expected value
over all states for all i 96 0.

We use a numerical model and extensive simulations to characterize the
routing scalability of ONCP in comparisons with Directed Diffusion (flat),
CBRP (hierarchical) protocols. To fully understand the performance under
different routing architectures, the geographic routing protocol will be
evaluated. And the performance of different protocols in lossy wireless
channel and irregular network topology conditions needs to be further
investigated.

In Appendix A, we implement a prototype system to frmctionally validate the
ONCP architecture concepts and present software emulation results in
TOS SIM simulator. However, the performance needs to be further validated in
real hardware platforms under realistic wireless channel conditions. Difl’erent
routing protocols (Directed Difl’usion) need be implemented and compared

with ONCP under Mica2 hardware platform.

17]

Appendix A

Functional Validation of ON CP through Software Emulation and
Hardware Prototype Implementation

In this appendix, we implement a prototype system to frmctionally validate the ONCP
architecture concepts under TinyOS [95] embedded operating system. We first describe
our motivation, and briefly discuss TinyOS Operating System. Then we present the
ONCP protocol stack implementation and the software emulation results. Finally we
discuss the hardware platform on which the prototype is implemented.

A.l Introduction

The implementation issues for wireless sensor networks are substantially different
from those of traditional Ad-hoc wireless networks because sensor networks typically
comprise many resource-constrained nodes connected by low-power radios. For
example, it is well lcnown that the wireless channel is very dynamic and time-varying
[79, 80]. As a result, the connectivity between nodes is not deterministic due to the
stochastic nature of interference, physical channel, and other sources of errors. The
links between nodes are lossy and the loss rates may change dynamically with
environmental factors and wireless channel contentions.

To capture the impacts of non-deterministic physical layer, the routing protocol for
sensor networks should consider these underlying factors and be able to cope with the
dynamic low level radio characteristics under real hardware platforms.

The resources for embedded sensor nodes are highly constrained. A typical sensor
node is equipped only with a low-power 8 bits microcontroller, limited memory storage,

and battery for energy supply [5]. This resource limitation must be taken into account

172

while implementing a routing protocol stack. For example, the operating system may
not support the process/thread structure, because of the limited memory constraint. The
protocol stack needs to relay on the interrupt-driven event architecture to provide the
interface API for applications.

In the chapter 4 and chapter 6, we have characterized the ONCP routing architecture
through the numerical models and extensive simulations. In order to perform a
functional validation, we have implemented and tested routing API for ONCP
architecture under the TinyOS embedded operating system. On top of the API
interfaces, several applications are developed. Using this prototype, we present certain
comparisons between ONCP and Tiny-AODV protocols in a 32 nodes network by
software emulation under TOS SIM.

A.2 TinyOS Operating System

TinyOS is an open source, component-based operating system targeting for wireless
sensor networks. It is an embedded operating system designed as a set of cooperating
tasks. It features a component-based architecture which enables rapid implementation
and minimizes the code size as required by the severe memory constraints in sensor
networks [95]. The component library of TinyOS comprises network protocols, sensor
drivers, distributed services, etc.

The TinyOS operating system, libraries, and applications are written in nesC, a
dialect of the C programming language which is optimized for sensor networks. The
nesC language supports the concurrency model, and provides mechanisms for

structuring, naming, and linking components into a networked embedded system.

173

TinyOS provides built-in interfaces, modules, and sensor-board specific configurations,
which allow programmers to build programs as a set of modules. It also provides
interfaces to the common hardware inputs, outputs, and sensors card. The application
program is statically linked with TinyOS operating system, and compiled into a small
binary file, using a custom GNU tool chain.

A TinyOS application is based on one or multiple of components linking together to
an executable file. These components are designed to be reusable for multiple
applications. NesC uses two types of components: modules and configurations.
Modules are implementation of executable logic, define functions and allocate memory
for variables. A module provides or uses interfaces. An interface describes the
commands and events provided by a component. Whereas configurations are used to
wire multiple components together, composing modules into larger abstractions. For
example, a routing module depends on a single hop packet layer, which is also a
configuration of protocol modules with a raw packet layer on top of the radio
configuration. A top-level configuration wires all components into the application.

An Interface within a component consists of two syntaxes: command and event. A
command is a function that interface provider must provide and interface users can call
to execute. An event is a function declaration which interface user must implement. If a
component wants to use a command in an interface, then it must implement all events
declared in that interface.

Concurrency model of TinyOS is composed by tasks and hardware interrupt handlers.

Tasks are generally long running computation functions. When a task is posted to the

174

task queue, the scheduler will execute it to completion unless it is interrupted by
hardware interrupt handlers. Tasks run to completion and cannot preempt other tasks. A
hardware interrupt handler is triggered by hardware. It also runs to completion, but may
preempt the execution of other interrupt handlers or tasks. Async keyword must be used
to declare commands and events which will be executed within hardware interrupt
handlers. When long-latency operations are used, a technique of split-phase operation
is employed. In that case, commands are used to initiate the requested action, e. g.
componentrequest, by posting a task and returning immediately. Events are then
signaled in response to the completion of the split-phase operation, e. g. typically using
componentrequestDone. These kinds of events do not preempt as those caused by
hardware interrupts.
A.3 ONCP Protocol Stack Implementation

In this section, we will describe the architectural support necessary for providing
ONCP functionalities at the routing layer. It defines a set of interfaces that allow
different algorithms to be independently implemented on top of a common radio stack.
Introduction of these interfaces enables support for flexibly integrating different
components into a system based on its specific application requirements. By combining
these requirements inside a separate architectural component, ONCP routing protocol
can be made to work with a diverse set of applications and platforms. This leads to the

components graph for our implementation, illustrated in Fig. A. l.

175

__________________________ v /\ v /\ V
iONCP Routingi statusUpdatel [appRequest I I regionControl
..Ii.___993.1.129999£_.i

 

   

 

 

 

 

 

 

 

 

 

 

 

Radio Stack
Fig. A.1: ONCP Protocol Stack Component Graph

 

 

 

 

ONCP Routing component is a configuration wired together by a couple of sub
modules, namely SingHopMsg, RegionMange, AppCommand, LocalRouting, and
StatusUpdate. It performs three main operations: (1) application data request/reception;
(2) status updates; (3) region management. A message arriving on a link interface is
dispatched to its associated network protocol, which processes the message based on its
type. Optional message filtering may occur and discard messages not destined for the
node’s address.

The ONCP component provides three interfaces for application components, and
uses the interface of the raw radio stack, which separate ONCP routing functionalities
from applications and the radio stack. The interface statusUpdate allows application
components to generate and receive network status information. The node periodically

calls this interface’s commands to send status update messages to ONCP server. The

176

second interface appRequest is intended to send sensing task request messages to the
network, and get the sensed data back to the applications. It is able to specify the
querying parameters, such as data type, request duration, data generation interval, etc.
The third interface is regionControl. It allows applications to dynamically designate,
change, and get the region ID associated with the node. These three interfaces must be
implemented. The detailed semantics of these interfaces are the follows.

interface statusUpdate {

command result_t sendUpdate (uint16_t address, uint8_t length, T OS_MsgPtr msg);

event result_t rechpdate (T OS_MsgPtr msg, result_t success);

interface regionControl {
command uint8_t getRegionID 0;

command void setRegionID (uint8_t Region);

interface appRequest {
command void generateReq (uint8_t [I param);

event result_t rechata ( T 0S_MsgPtr msg, result_t success);

In the prototype development, we do not implement clustering algorithm, as we did
in the simulations. Because of the limited number of nodes in the network, we can not
designate enough nodes to support clustering within a region. For the same reason, the

local routing algorithm in our implementation is based on the node instead of clusters,

177

which could lessen the benefits of ONCP routing protocol. However, our architecture
does support different local routing algorithms including cluster-based protocols.
Below, we describe the internal components of ONCP protocol stack.

SingleHopMsg Module:

The SingleHopMsg component is intended for the basic point-to-point
communication primitives directly on t0p of the radio stack. Through the two
parameterized interfaces sendMsg [uint8_t id] and receiveMsg [uint8_t id], it provides
one-hop message sending and receiving services for other components. A simple queue
is also implemented in the module. If sendMsg.send is called to send a message, this
message is put into a queue first. A message is send out when only the radio is idle.
After the radio stack sends/drops the message, the event sendMsg.sendDone is invoked
to notify function call result to the component. When a message from the radio stack
arrives at a node, the event receiveMsg .receive in the interface receiveMsg will be
invoked.
interface sendMsg {

command result_t send (uint16_t address, uint8_t length, T 0S_MsgPtr msg);

event result_t sendDone ( T 0S_MsgPtr msg, result_t success);

interface receiveMsg {

event T OS_MsgPtr receive (T OS_MsgPtr m);

Region Management Module:

178

It provides the interface to dynamically set and get node’s region ID. Without it, it is
not possible for implementing the functionalities of local routing, command and status
updates components. As when a node receives a local routing/command request
message, it frrst decides whether to process or discard the message based on the
region_ID gotten from this component.
interface region_Manage {

command uint8_t getRegionID 0;

command void setRegionID (uint8_t Region);

}
APP_Command Module:

This component is responsible for sensing task request dissemination, processing,
and data reception notification to applications. When the ONCP server gets a sensing
task from a user client, it computes the region level paths and disseminates the
corresponding request command to the network via the interface command. The
component also provides functionalities to record the next_region ID for each
individual command in order to support local routing algorithm. When a desired
sensing data message arrives at a node; the interface of command is responsible to
notify the data arrival to the corresponding applications.
interface command {

command void processCommand (uint8_t [I param);

command void recordNextregion (uint8_t commandID);

event result_t rechata ( T OS_MsgPtr msg, result_t success);

179

StatusUpdate Module:

The module allows nodes to generate and report status update messages to the ONCP
server. A reported message includes the region id, the region energy level, and the
connectivity metric. It provides an interface status Update for upper-layer component to
periodically generate status update messages. Meanwhile, it implements the algorithm
to relay the reported messages to the ONCP server through multi-hop communication
and notify the arrival of such messages.
interface status Update {

command void generateStatusupdate 0;

command void processStatrLsupdate (T 0S;MsgPtr msg, result_t success);

event result_t recvStatusupdate (T 0S_MsgPtr msg, result_t success);

LocalRouting Module:

It implements the local routing algorithm to discover the paths to reach the next
region. When a node receives a data message, it calls the command nextHop in the
localRouting interface to check whether there is a valid entry in the route table. If there
is one, then the data message is send to the next hop through the SingleHopMsg
component. Otherwise, the local routing discovery messages (route request/reply/error)
are disseminated by invoking the commands and events in the interface of localRouting.
Through the components of AppCommand and RegionManage, the localRouting
component has access to the protocol states of desired next region_ID on the global
paths and the node’s own region_ID, which are essential for local routing algorithms.

interface localRouting {

180

command uint8_t nextHop (uint8_t commandID );

command void sendReq (T 0S_MsgPtr msg, result_t success);
command void sendRep (T OS_MsgPtr msg, result_t success);
command void sendErro (T 0S_MsgPtr msg, result_t success);
event result_t recvReq (T 0S_MsgPtr msg, result_t success);
event result_t recvRep (T 0S_MsgPtr msg, result_t success);

event result_t rechrror (T 0S_MsgPtr msg, result_t success);

A.4 Software Emulation Results

In this section, we present software emulation results in order to functionally validate
our prototype development of ONCP routing protocol. As we discuss in the chapter 3, 4,
6, the ONCP routing architecture is proposed to reduce the routing overheads in large
networks, which suggests that its benefits can not manifest in small networks. The
results here should be interpreted as demonstration of effectiveness of ONCP prototype
implementation, rather than specific performance comparisons.

We conduct the experiments under TOSSIM [96], a TinyOS mote simulator, which
compiles directly from TinyOS codes. It can test not only the algorithms, but also the
implementations. TOSSIM simulates the TinyOS network stack at the bit level,
allowing experimentation with low-level protocols in addition to top-level application
systems. In our experiments, 32 nodes are deployed in a grid topology, where one node
has four neighbors. The base station is placed at the center of the network. And it

periodically disseminates application request messages to arbitrary nodes in the

181

network. Each message requests the nodes to generate 30 application data messages at
the interval specified by the message attributes. In the experiments, the base station
totally generates 50 application request messages to the network. For the ONCP
protocol, the network is configured into 9 regions, which contains 4 nodes.

We compare the performance of ONCP with that of Tiny-AODV protocol (a
simplified version of AODV) in terms of expected delivery ratio, routing overhead and
average hop counts. Unlike our simulation results in large networks in chapter 6 (2916
nodes network), ONCP does not demonstrate improvement for the expected delivery
ratio in the 32 nodes network. It has a similar expected delivery ratio with Tiny-AODV
at all packet generation intervals as shown in Fig A.2. Under such small network size,
the routing control overhead will not cause network congestion, which explains that

both protocols have high expected delivery ratios.

 

 

 

 

 

 

 

 

 

 

 

1
e __ .
33 0.8
9‘ -B-ONCP
8‘ +Tiny-AODV
.2
g 0 6 ——
E
8
o.
><
“1 0.4 ‘3

0.2 i l i i l
0.5 0.6 0.7 0.8 0.9 1
Packet Generation Interval (sec)

 

Fig. A.2: Expected Delivery Ratio

182

It is observable that the routing control overhead of ONCP is still smaller than
Tiny-AODV in such small networks in Fig A.3, which is defined as the ratio of the
number of application data messages the base station receives by the number of all
messages transmitted in the network. This fact demonstrates the effectiveness of ONCP
in reducing the network-wide routing discovery messages. It also shows in Fig A.4 that
the average transmission hops of ONCP are larger than those of Tiny-AODV because of
the abstraction of regions, which is consistent with the previous simulation results in
chapter 6. Even considering this, the routing overhead of ONCP is smaller. These facts
prove that the hybrid routing architecture enables eliminating unnecessary

transmissions significantly.

 

 

ll ‘—

 

 

 

-e-0NCP I

 

 

 

 

Routing Overhead .
\)

 

 

5 __ V '15-Tiny—AODV

3 __ .

1 l l i t i '
0.5 0.6 0.7 0.8 0.9 1

 

 

Packet Generation Interval (see)

Fig. A.3: Routing Overhead

 

183

 

 

 

 

 

 

 

 
 

 

 

 

 

§ 4 “ ' -a—0Ncr>
m +Tiny-AODV
.S , . n E .
g 2
I; 2 -_

if

a 1 -_

0 i i i l i
0.5 0.6 0.7 0.8 0.9 1
Packet Generation Interval (sec)

 

 

 

Fig. A.4: Average Transmission Hops

A.5 Prototype Hardware Implementation
Crossbow Technology Inc [1] provides a series of wireless sensor nodes as shown in
Fig. A.5. For ONCP prototype implementation, we choose Mica2 mote. It is a third
generation mote module used for low power, wireless sensor networks. Mica2 is based
on a low power microcontroller AtmegallZSL, designed specifically for embedded
sensor networks. It also has a 51-pin expansion connector for light, temperature, RH,
Barometric Pressure, Acceleration/Seismic, Acoustic, Magnetic and other Sensor
Boards. It has the following major components:
0 Microprocessor: 8 bits Atrnel ATmega128L
0 7.3728 MHz clock
0 128 kB of Flash for program memory

0 4 kB of SRAM for data and variables

184

o 2 UARTs (Universal Asynchronous Receive and Transmit)
0 Serial Port Interface (SPI) bus
0 Inter IC (12C) bus

0 Radio: Chipcon’s CC1000
0 Center Frequency: 868/916 MHz
0 Data Rate 38.4 Kbps
0 Outdoor Range 500 ft

0 External serial flash memory: 512 kB

0 51-pin expansion connector

0 User interface: 3 programmable LEDs

0 JTAG port

0 Powered by two AA batteries:

0 1850 mAh capacity

 

Fig. A.5: Sensor Node Mote2dot, Mote2, Imote, TelosB, Cricket (from left to right)

We build a grid structure for the prototype hardware implementation as show in Fig.
A.6. On the structure, we attached 12 Mica2 nodes which are powered by an extern
power supply. And it can be extended to support 36 MicaZ nodes. To configure the
wireless transmission change, we reset the transmission power levels of Mica2 nodes,

and shorten their antennas. The ONCP protocol stack described in section A.3 has been

185

tested under this hardware platform.

 

Fig. A.6: Grid structure of hardware implementation

186

References

[l] www.xbow.com

[2] F. Ye, H. Luo, J. Cheng, S. Lu, L. Zhang, “A Two-tier data dissemination model for
large-scale wireless sensor networks,” ACM/IEEE MOBICOM, 2002.

[3] Y. Yao and J. Gehrke, “The cougar approach to in-network query processing in
sensor networks,” SIGMOD Record, September 2002.

[4] W. Heinzelman, “Application specific protocol architectures for wireless
networks,” PhD Thesis, MIT, 2000.

[5] W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-efficient
communication protocols for wireless microsensor networks,” Proceedings of the
Hawaii International Conference on Systems Sciences, Jan.2000.

[6] B. Krishnamachari, D. Estrin, S. Wicker, “Modeling Data Centric Routing in
Wireless Sensor Networks,” in the Proceedings of IEEE INF OCOM, , June 2002

[7] Alan Mainwaring, Joseph Polastre, Robert Szewczyk, David Culler, and John
Anderson, “Wireless sensor networks for habitat monitoring,” In ACM
International Workshop on Wireless Sensor Networks and Applications

(W SNA'02), Atlanta, GA, September 2002.
[8] http://firebug.sourceforge.net

[9] RI F eder, “Delta to Invest in Radio Tags for Luggage at Airports,” the New York
Times, July 1, 2004.

[10] Marc L. Songini, “Wal-Mart Shifts RFID Plans,” Computerworld, February, 2007.

[11] Rolf Clauberg, “RFID and Sensor Networks,” RFID Workshop, University of St.
Gallen, Switzerland, Sept, 2004

[12] Loren Schwiebert, Sandeep K. S. Gupta, and Jennifer Weinmann, “Research
challenges in wireless networks of biomedical sensors,” In Mobile Computing and
Networking, 2001.

[13] I. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, “A survey on sensor
networks,” in IEEE Communication Magazine, 2002

[14] McMahan, M.L., “Evolving Cellular Handset Architectures but a Continuing
Insatiable Desire for DSP MIPS,” Texas Instruments Incorporated, 2000.

[15] K. Yao, R. Hudson, C. Reed, D. Chen, and F. Lorenzelli, “Blind Beamforming on
a Randomly Distributed Sensor Array System,” Proceedings of SiPS, Oct 1998.

[16] W. Ye, J. Heidemann, and D. Estrin, “An energy-efficient MAC protocol for
wireless sensor networks,” INFOCOM 2002.

187

[17] S. Singh and C. S. Raghavendra, “PAMAS: Power aware multi-access protocol
with signaling for ad hoc networks,” ACM Computer Communication Review,
28(3):5-26, July 1998.

[18] S. Keshav, “An Engineering Approach to Computer Networking: ATM networks,
the Internet, and the telephone network,” Addison Wesley Inc., 1997.

[19] Stefano Basagni, Michele Mastrogiovanni, Alessandro Panconesi, and Chiara
Petrioli, “Localized Protocols for Ad Hoc Clustering and Backbone Formation: A
Performance Comparison,” in IEEE Transactions on Parallel and Distributed
Systems, Apr, 2006.

[20] X Lu, Y. Sun, J. Yu, and W. Yan, “An energy efficient cross-layer routing
algorithm for wireless sensor networ ,” in the lst IEEE Conference on Industrial
Electronics and Applications (ICIEA '06), Singapore, May 2006.

[21] LAN MAN Standards Committee of the IEEE Computer Society. IEEE Std 802.11
1999, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)
specifications. IEEE, 1999.

[22] J. Zander, “Trends in resource management future wireless networks,” in Proc. of
FTF 99, Beijing, China, December 1999.

[23] R. Nelson and L. Kleinrock, “Spatial TDMA: A Collision-Free Multihop Channel
Access Protocol,” IEEE Transactions on Communications, Vol. COM-33, No. 9,
Sept. 1985, pp.934-944.

[24] L. Kleinrock and F. A. Tobagi, “Packet Switching in Radio Channels: Part II -
Carrier Sense Multiple-Access Modes and Their Throughput-Delay
Characteristics,” IEEE Transactions on Communications, Vol. COM-23, No. 12,
December 1975, 1400-1416.

[25] C. R Lin and M. Gerla, “Adaptive clustering for mobile wireless networks,” IEEE
Journal on Selected Areas in Communications, vol. 15, pp. 1265—1275, September
1997.

[26] P. Krishna, N. H. Vaidya, M. Chatterjee, and D. K. Pradhan, “A cluster-based
approach for routing in dynamic networks,” in SIGCOMM Computer
Communications Review (CCR), 1997.

[27] P. F. Tsuchiya, “The landmark hierarchy: a new hierarchy for routing in very large
networ ,” in Symposium proceedings on communication architectures and
protocols. ACM Press, 1988, pp. 35—42.

[28] J. M. Reason and J. M. Rabaey, “A study of energy consumption and reliability in
a multi-hop sensor network,” ACM SIGMOBILE Mobile Computing and
Communications Review, Vol 8, January 2004.

[29]E. M. Belding-Royer, “Multi level Hierarchies for Scalable Ad hoc Routing,”
Wireless Networks, 9, pp. 461-478, Sept. 2003

188

[30] C. E. Jones, K. M. Sivalingam, P. Agrawal and J. C. Chen, “A Survey of Energy
Efficient Network Protocols for Wireless Networks,” Wireless Networks, v.7 n.4,
p.343-358, September 2001.

[31] K Arisha, M. Youssef, and M. Younis, “Energy-Aware TDMA-Based MAC for
Sensor Networks,” IMPACCT 2002, New York City, New York, May 2002.

[32] A. El-Hoiydi, “Spatial TDMA and CSMA with Preamble Sampling for Low
Power Ad Hoc Wireless Sensor Networks,” Proc. of the Int]. Symp. on Comp. and
Com., 2002.

[33] A. El-Hoiydi, “Aloha with Preamble Sampling for Sporadic Traflic in Ad Hoc
Wireless Sensor Networks,” Proc. IEEE International Conference on
Communications, 2002.

[34] I. Chlamtac and A. Farag'o, “Making transmission schedules immune to topology
changes in multihop packet radio networks,” IEEE/ACM, Trans. Networking, vol.2,
pp.23—29, Apr. 1994.

[3 5] K Sohrabi and G Pottie, “Performance of a novel self-organization protocol for
wireless ad-hoc sensor networks,” 50th IEEE Vehicle Technology Conference, The
Netherlands, September 1999.

[36] R. Naik, S. Biswas and S. Datta, “Distributed Sleep Scheduling Protocols for
Energy Conservation in Wireless Networks,” In The 38th Hawaii Int’l Conference
on System Sciences, 2005

[3 7] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An Application-Specific
Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on
Wireless Communications, Vol. 1, No. 4, October 2002, pp. 660-670.

[3 8] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed diffusion: a scalable
and robust communication paradigm for sensor networks,” ACM Mobicom, Boston,
MA, August 2000.

[39] T. Clausen and P. Jacquet, “Optimized Link State Routing Protocol (OLSR),” RFC
3626, IETF Network Working Group, Oct. 2003.

[40] C. E. Perkins and E. M. Royer, “Ad hoc On-Demand Distance Vector Routing,” in
Proc. WMCSA, Feb. 1999.

[41] Yan Yu, Ramesh Govindan and Deborah Estrin, “Geographical and Energy Aware
Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks,”
UCLA Computer Science Department Technical Report UCLA/CSD-TR-Ol-0023,
May 2001.

[42] B. Karp and HT. Kung, “GPSR: Greedy perimeter stateless routing for wireless
networks,” ACM MOBICOM, August 2000.

189

[43] F. Kuhn, R. Wattenhofer, A. Zollinger, “Worst-Case and average-case efficient
geometric ad-hoc routing,” MOBIHOC, 2003.

[44] Q. Fang, J. Gao, L. J. Guibas, V. de Silva, L. Zhang, “GLIDER: Gradient
Landmark-Based Distributed Routing for Sensor Networks,” INFOCOM 2005.

[45] J. Bruck, J.Gao and A.Jiang, “MAP: Medial Axis Based Geometric Routing in
Sensor Networks,” ACM MOBICOM 2005.

[46] Ns-2 Simulator, at www.isi.edu/nsnam/ns.

[47] Javed Aslam, Qun Li and Daniela Rus, “Three Power-aware Routing Algorithms
for Sensor Networks,” Journal of Wireless Communications and Mobile
Computing, March 2003.

[48] Ljubica Blazevic, Jean-Yves Le Boudec, and Silvia Giordano, “A location-based
routing method for mobile ad hoc networks,” IEEE Transactions on Mobile
Computing, Volume 4, Issue 2, 2005

[49] R. Madan and S. Lall, “Distributed Algorithms for Maximum Lifetime Routing in
Wireless Sensor Networks,” IEEE Transactions on Wireless Communications, June
2006.

[50] J. Park and S. Sahni, “An oline heuristic for maximum lifetime routing in wireless
sensor networks,” IEEE Transactions on Computers, 2006.

[51]]ae-Hwan Chang and Leandros Tassiulas, “Maximum life time routing in wireless
sensor networks,” IEEE/ACM Transactions on Networking, 2004.

[52] Shashidhar R. Gandham, M. Dawande, Ravi Prakash and S. Venkatesan, “Energy
Efficient Schemes for Wireless Sensor Networks with multiple mobile base
stations,” Proceedings of IEEE Globecom, 2003.

[53] Y. Thomas Hou, Yi Shi, and Hanif D. Sherali, “Optimal Base Station Selection for
Anycast Routing in Wireless Sensor Networks,” IEEE Transactions on Vehicular
Technology, 2006.

[54] C. Schurgers and MB. Srivastava, “Energy efficient routing in wireless sensor
networks,” MILCOM Proceedings, 2001.

[55] R. C. Shah and J. Rabaey, “Energy Aware Routing for Low Energy Ad Hoc Sensor
Networks,” IEEE Wireless Communications and Networking Conference (W CN C),
2002.

[56] S. Lindsey, C. Raghavendra, “PEGASIS: Power Efficient Gathering in Sensor
Information Systems,” IEEE Aerospace Conference Proceedings, 2002.

[57] Q. Li and J. Aslam and D. Rus, “Hierarchical Power-aware Routing in Sensor

Networks,” In Proceedings of the DIMACS Workshop on Pervasive Networking,
2001.

190

[58] J.-H. Chang and L. Tassiulas, “Energy Conserving Routing in Wireless Ad-hoc
Networks,” in Proc. of the 19th IEEE INF OCOM, 2000.

[59] K. Kar, M. Kodialam, T.V. Lakshman, and L. Tassiulas, “Routing for Network
Capacity Maximization in Energy-constrained Ad-hoc Networks,” in Proc. of the
22rd IEEE INFOCOM, 2003.

[60] A. Sankar and Z. Liu, “Maximum Lifetime Routing in Wireless Ad-hoc
Networks,” in Proc. of the 23rd IEEE INFOCOM, 2004.

[61] J. Gao and L. Zhang, “Load Balanced Short Path Routing in Wireless Networks,”
in Proc. of the 23rd IEEE INFOCOM, 2004.

[62] J. Pan, Y.T. Hou, L. Cai, Y. Shi, and S.X. Shen, “Topology Control for Wireless
Sensor Networks,” in Proc. of the 9th ACM MobiCom, 2003.

[63] N. Li and J. Hou, “Topology Control in Heterogeneous Wireless Networks:
Problems and Solutions,” in Proc. of the 23rd IEEE INFOCOM, 2004.

[64] R. Ramanathan and R. Rosales-Hain, “Topology control of multihop wireless
networks using transmit power adjustment,” in Proc. IEEE INFOCOM 2000, Tel
Aviv, Israel, Mar. 2000.

[65] S. A. Borbash and E. H. Jennings, “Distributed topology control algorithm for
multihop wireless networks,” in Proc. 2002 World Congress on Computational
Intelligence (W CCI 2002), Honolulu, Hawaii, US, May 2002.

[66] N. Li, J. C. Hou, and L. Sha, “Design and analysis of an MST-based topology
control algorithm,” in Proc. IEEE INFOCOM 2003, San Francisco, California, US,
Apr. 2003.

[67] K Fall, “A Delay-Tolerant Network Architecture for Challenged Internets,” In
ACM SIGCOMM, Aug. 2003.

[68] R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data MULEs: Modeling a
Three-tier Architecture for Sparse Sensor Networks,” In IEEE SNPA, May 2003.

[69] A. Vahdat and D. Becker, “Epidemic Routing for Partially-connected Ad hoc
Networks,” Technical Report, Duke University, July 2000.

[70] S. Jain, K. Fall, and R. Patra, “Routing in a delay tolerant network,” In Proc.
SIGCOMM, 2004.

[71] S. Jain, R.C. Shah, G Borriello, W. Brunette, and S. Roy, “Exploiting Mobility for
Energy Efficient Data Collection in Sensor Networks,” in Proc. Modeling and
Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2004.

[72] H. Dubois-Feniere, M. Grossglauser, and M. Vetterli, “Age Matters: Efficient

Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages,” in Proc.
ACM MobiHoc, 2003.

191

[73] T. Small and Z. Has, “The Shared Wireless Infostation Model - A New Ad Hoc
Networking Paradigm (or Where There Is a Whale,There Is a Way),” in Proc. ACM
MobiHoc, 2003.

[74] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. Peh, and D. Rubenstein,
“Energy-Efficient Computing for Wildlife Tracking: Design T radeoffs and Early
Experiences with Zebranet,” in Proc. Architectural Support for Programming
languages and Operating Systems (ASPLOS), 2002.

[75] A. Chakrabarti, A. Sabharwal, and B. Aazhang, “Using Predictable Observer
Mobility for Power Efficient Design of Sensor Networ ,” in Proc. Information
Processing in Sensor Networks (IPSN), 2003.

[76] D. Thakore and S. Biswas, “Routing with persistent link modeling in
intermittently connected wireless networks,” in Proc. of MILCOM 2005.

[77] J. Luo and J .-P. Hubaux, “Joint Mobility and Routing for Lifetime Elongation in
Wireless Sensor Networks,” in Proc. INFOCOM, 2005.

[78] Wang, Z., Basagni, S., Melachrinoudis, E., Petrioli, C., “Exploiting Sink Mobility
for Maximizing Sensor Networks Lifetime,” in Proc. of the 38th Hawaii
International Conference on System Sciences, January, 2005.

[79] Kevin Klues, Guoliang Xing_, Chenyang Lu, “Link layer support for unified radio
power management in wireless sensor networ ,” in Proc. of international
conference on Information processing in sensor networks (IPSN), 2007.

[80] J. Polastre, J. Hill, and D. Culler, “Versatile low power media access for wireless
sensor networks,” In SenSys, 2004.

[81] Mingliang Jiang, Jinyang Li, and Y.C. Tay, “Cluster based routing protocol
(CBRP),” draft-ietf-manet-cbrp-spec-Ol.txt, 1999.

[82] N. Priyantha, A. Chakraborty, and H. Balakrishnan, “The Cricket
Location-Support System,” In Proceedings of. 6th ACM MOBICOM, 2000.

[83] K. Seada, M. Zuniga, A. Helmy and B. Krishnamachari, “Energy-Efficient
Forwarding Strategies for Geographic Routing in Lossy Wireless Sensor
Networks,” In Proceedings of ACM SenSys 2004.

[84] S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z.M. Wang, “A new
MILP formulation and distributed protocols for wireless sensor networks lifetime

maximization,” in Proc. IEEE International Conference on Communications, pp.
3517—3524, Istanbul, Turkey, June 11—15, 2006.

[85] A. Efrat, S. Har-Peled, and J. Mitchell, “Approximation algorithms for location

problems in sensor networks,” in Proc. IEEE BROADNETS 2005 — Wireless
Networking Symposium, pp. 767—776, Boston, MA, Oct. 3-7, 2005.

192

[86] V. Rodoplu and TH. Meng, “Minimum energy mobile wireless networks,” IEEE
Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1333-1344, Aug.
1999.

[87] Y. Shi and Y.T. Hou, “Theoretical results on base station movement problem for
sensor networks,” Technical Report, the Bradley Department of Electrical and
Computer Engineering, Virginia Tech, Blacksburg, VA, July 2007.

[88] S. Singh, M. Woo, and CS. Raghavendra, “Power-aware routing in mobile ad hoc
networks,” in Proc. ACM Mobicom, pp. 181—190, Dallas, TX, Oct. 25—30, 1998.

[89] I. Stojmenovic and X. Lin, “Power-aware localized routing in wireless networks,”
IEEE Trans. on Parallel and Distributed Systems, vol. 12, no. 11, pp. 1122—1133,
Nov. 2001.

[90] R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang, “Distributed topology control for
power efficient operation in multihop wireless ad hoc networks,” in Proc. IEEE
Infocom, pp. 1388—1397, Anchorage, AK, April 22—26, 2001.

[91] M. Younis, M. Bangad, and K. Akkaya, “Base-station repositioning for optimized
performance of sensor networks,” in Proc. IEEE Vehicular Technology Conference,
pp. 2956—2960, Orlando, FL, Oct. 4—9, 2003.

[92] RP. Pham and S. Perreau, “Performance Analysis of Reactive Shortest Path and
Multi-path Routing Mechanism with Load Balance,” in Proc. of the 22nd IEEE
INFOCOM, 2003.

[93] D. Goldenberg, J. Lin, A.S. Morse, B. Rosen, and YR Yang, “Towards Mobility
as a Network Control Primitive,” in Proc. of the 5th ACM MobiHoc, 2004.

[94] MA. Batalin, M. Rahimi, Y. Yu, D. Liu, A. Kansal, GS. Sukhatrne, W.J. Kaiser,
M.Hansen, GJ. Pottie, M.Srivastava, and D. Estrin, “Call and Response:
Experiments in Sampling the Environment,” in Proc. Of the 2nd ACM SenSys,
2004.

[95] http://www.tinyos.net/

[96] Philip Levis, Nelson Lee, Matt Welsh, and David Culler, “TOSSIM: Accurate and
Scalable Simulation of Entire TinyOS Applications,” In Proceedings of the First
ACM Conference on Embedded Networked Sensor Systems (SenSys 2003).

[97] G Wang, G Cao, and T. La Porta, “Movement-Assisted Sensor Deployment,” in
Proc. of the 23rd IEEE INFOCOM, 2004.

[98] M. Grossglauser and D. Tse, “Mobility increases the capacity of ad hoc wireless
networks,” IEEE/ACM Trans. on Networking, vol. 10, no. 4, pp. 477—486, 2002.

[99] EJ. Duarte-Melo, M. Liu, and A. Misra, “A Modeling Framework for Computing

Lifetime and Information Capacity in Wireless Sensor Networks,” in Proc. of the
2nd WiOpt, 2004.

193

 

[100] A. Woo, T. Tong, and D. Culler, “Taming the Underlying Challenges of
Reliable Multihop Routing in Sensor Networks,” in Proc. of the lst ACM SenSys,
2003.

[101] M. Bhardwaj and AP. Chandrakasan, “Bounding the Lifetime of Sensor
Networks Via Optimal Role Assignments,” in Proc. of the let IEEE INFOCOM,
2002.

[102] F. Sivrikaya and B. Yener, “Time Synchronization in Sensor Networks: A
Survey,” IEEE Networks, pp. 45-50, July/August 2004.

[103] B. Sundararaman, U. Buy, and A. D. Kshemkalyani, “Clock Synchronization
in Wireless Sensor Networks: A Survey,” Ad-Hoc Networks, vol. 3, pp. 281-323,
May 2005.

[104] D. Bertsekas and R. Gallager, Data Networks, 2nd ed.: Prentice Hall, 1992.

[105] V. Srivastava and M. Motani, “Cross-layer design: a survey and the road
ahead,” IEEE Communications Magazine, vol. 43, pp. 112- 119, December 2005.

[106] S. Cui, R Madan, A. J. Goldsmith, and S. I..all., “Cross-layer Energy and
Delay Optimization in Small-scale Sensor Networks,” IEEE Transactions on
Wireless Communications, vol. 6, pp. 3688--3699, 2007.

[107] H. Kwon, T. H. Kim, S. Choi, and B. G Lee, “A cross-layer strategy for
energy-efficient reliable delivery in wireless sensor networks,” IEEE Transactions
on Wireless Communications, vol. 5, pp. 3689—3699, 2006.

[108] S. Chri, R. Madan, A. J. Goldsmith, and S. Lall, “Energy-delay Tradeoff for
Data Collection in Sensor Networks,” in International Communication Conference
(ICC), South Korea, 2005.

[109] R. Verdone, “Multihop R-ALOHA for Intervehicle Communications at
Millimeter Waves,” IEEE Transaction on Vehicular Technology, vol. 4, 1997.

[1 10] I. Rhee, A. Wanier, M. Aia, and J. Min, “Z-MAC: A Hybrid MAC for Wireless
Sensor Networks,” in ACM SenSys 2005, 2005.

[111] A. Woo and D. E. Cullar, “A Transmission Control Scheme for Media Access
in Sensor Networks,” in the 7th annual international conference on Mobile
computing and networking, 2001, pp. 221-235.

[112] G Urvoy-Keller, G Hebutene, and Y. Dallery, “Trafiic Engineering in a
Multipoint-to-Point network,” IEEE Journal on Selected Areas in Communications,
vol. 20, pp. 834-849, May 2002.

[113] M. Avlonitis, P. Vlamos, and K. Oikonomou, “A Space-Time Analytical

Model for Energy Consumption in Wireless Sensor Networks,” in Med-Hoc-Net
2007, Greece, June 2007.

194