THESIS

2008’

 

LIBRARY
Michigan State
Universnty

 

 

 

This is to certify that the
thesis entitled

IMPROVING DATA TRANSMISSION RELIABILITY AND
THROUGHPUT IN WIRELESS SENSOR NETWORKS

presented by

EE FOONG LEE

has been accepted towards fulfillment
of the requirements for the

MS. degree in Computer Science

 

 

Jk: 0Q

 

Major Professor’s Signature

05/05/2008

 

Date

MSU is an affirmative-action, equal-opportunity employer

.--0---0-O-l-ui----—o—o-o-o-c-u—c—o-u—u-o-o-I-o-O-o-o-l_p—-

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.

DATE DUE

 
   
  

   

DATE DUE

   

DATE DUE

 

IMPROVING DATA TRANSMISSION RELIABILITY AND THROUGHPUT IN
WIRELESS SENSOR NETWORKS

By

136 Foong Lee

A THESIS

Submitted to
Michigan State University
in partial fiJlfilIment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Computer Science

2008

 

ABSTRACT

IMPROVING DATA TRANSMISSION RELIABILITY AND THROUGHPUT IN
WIRELESS SENSOR NETWORKS

By
Ee Foong Lee

Improving data transmission reliability and throughput in wireless sensor
networks is a challenging task. The lossy nature of wireless communication and rapidly
changing environment has caused tremendous problems in transmitting data packets
between sensor nodes. Our key objective here is to maximize the overall transmission
throughput. Before investigating various approaches to accomplish our goal, we start
with an extensive study of how radio signals behave in complex environments where
obstructions and reflections occur. We then design and implement a MAC layer overlay
thatvconsists of channel access scheduling and lost packet retransmission. The channel
access scheduling mechanism is designed based on a hierarchical tree structure where
each intermediate node collects data from multiple sources and forwards them to its
parent at a higher level. The lost packet recovery can retransmit lost packets without
reliance on any acknowledgments. We evaluate our protocol on both Mica2 and Tmote
sensor testbeds, which shows that the data transmission throughput can be significantly

improved.

 

ACKNOWLEDGMENTS
First and foremost, I would like to deeply thank my thesis advisor Dr. Li Xiao and my
committee members Dr. Matt Mutka and Dr. Sandeep Kulkami for their continual
guidance and support during this work. I would also like to thank my parents and wife for
their unconditional love and encouragement. I am also grateful to the members of the

ELANS lab, and especially Chen Wang, for mentoring and guiding me throughout.

iii

 

1.

TABLE OF CONTENTS

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

INTRODUCTION 1
I . 1 Motivation 1
1.1.1 Radio Signal Behaviors 2
1.1.2 Receiver-Centric Approach 3
1.2 Objectives 5
1,3 Organi7afinn 5
RELATED WORK 7
2.1 Related Work in Radio Signal Behaviors in Complex Environments ................ 7
2.2 Related Work in Channel Access Scheduling and Lost Packet Retransmission
10
RADIO SIGNAL BEHAVIORS 12
3.1 An RSS Ranging System 12
3.2 Signal Strength Behaviors in Complex Environments ..................................... 14
3.2.1 Comparing Indoor with Outdoor Envir- ‘ 14
3.2.2 Comparing Different Outdoor Envir- ‘ 16
3.3 Environmental Effects on RSS 17
3.3.1 Height of the Sensor Nodes from the Ground 17
3.3.2 Effects of Obstructions 20
3.3.2.] Outdoor Environment 23
3.3.2.21ndoor Environment 24
3.3.3 Effects ofReflectinne 30
3.3.3.1 Outdoor Envirnnmenf 30
3.3.3.21ndoor Environment 32
3.4 Summary 35
RECEIVER-CENTRIC PROTOCOL 39
4.1 Channel Access “ L J " u 39
4.1.1 Problem Definition 39
4.1.2 Basic Idea 40
4.1.3 Scheduling Mechanism via Overhearing 42
4.2 Lost Packet 9 ‘ ‘ ' 43
4.2.1 Problem Definition 43
4.2.2 Basic Idea 44
4.2.3 Request Lost Packets with Overhearing 45
4.3 Performance Evallmfinn 47
4.3.] Experimental Setup and Configuration 48
4.3.2 Channel Access Scheduling under Different Packet Injection Intervals .......... 50
4.3.3 Channel Access Scheduling under Different Number of Sources .................... 51
4.3.4 Channel Access Scheduling under Different Buffer Sizes ............................... 54
4.3.5 Lost Packet Retransmission under Different Packet Injection Intervals .......... 55
4.3.6 Lost Packet Retransmission under Different Buffer Sizes ............................... 58

5.

6.

4.3.7 Lost Packet Retransmission under Different Packet Sizes ............................... 60

4.4 Summary

 

CONCLUSION AND FUTURE WORK

 

5.1 Conclusion

 

5.2 Future Work

BIBLIOGRAPHY

 

62

63
63
64

66

 

LIST OF TABLES

 

Table A: Summary of Factors Affecting Radio Signal m‘ g“

Table B: Key Features of Mica2 and Tmote

 

Table C: Summary of key differences between RC and ECC

 

vi

49

56

LIST OF FIGURES

Figure 1: The maximum measurable distance between nodes for various transmission

 

 

 

powers. 13
Figure 2: An open flat parking area without obstructions. 15
Figure 3: Radio signal behavior in indoor and outdoor environments. ............................ 15
Figure 4: Radio signal behavior in different outdoor em' ‘ 16
Figure 5: The assistance with tripods to raise the sensor nodes. ...................................... 18

Figure 6: Elevation of sensor nodes affects signal strength in the outdoor environment. 18

 

 

 

 

 

 

 

Figure 7: Placement of sensor nodes in two classrooms. 21
Figure 8: The effects of lifiing both sensors in the indoor environment. ................ ' ......... 21
Figure 9: The effects of different elevations of receiver on signal strength. .................... 22
Figure 10: The effects of different elevations of sender on signal strength. .................... 22
Figure 11: The line of sight (LOS) is obstructed by a mid-sized vehicle. ........................ 23
Figure 12: A natural forest with a cluster of tall trees and bushes 25
Figure 13: The line of sight (LOS) is obstructed by tall trees. 25
Figure 14: The line of sight (LOS) is obstructed by a wall. 26
Figure 15: Environment for baseline metric measurement without obstructions. ............ 28
Figure 16: The real environment shown in Figure 15. 28
Figure 17: The setting in a basketball court for testing wall BfTPr‘fe 29
Figure 18: The line of sight (LOS) is obstructed by a wall in Figure 17 .......................... 29
Figure 19: The effects of reflections from a mid-sized vehicle. ....................................... 31
Figure 20: The trees reflections on signal ‘“ :L 31
Figure 21: Hallway setting for testing wall reflections while fixing the receiver. ........... 33
Figure 22: The effects of wall reflections on signal strength for Figure 21. .................... 33

vii

Figure 23: Hallway setting for testing wallreflections while fixing the sender ............... 34
Figure 24: The effects of wall reflections on signal strength for Figure 23. .................... 34
Figure 25: Basketball court setting for testing wall reflections while fixing the receiver. 36
Figure 26: The effects of wall reflections on signal strength for Figure 25. .................... 36

Figure 27: Receiver-centric protocol schedules time slots in a round-robin fashion via
overbearing. 41

 

Figure 28: In Receiver-centric protocol, node C continues to forward packet 4, 5, and 6
even when packet 3 is lost. 45

Figure 29: Receiver-centric protocol divides packet buffers into three regions: sending

 

 

 

region, recovery region, receiving region. 47
Figure 30: Control message format. 50
Figure 31: Scheduling in Mica2 under different packet injection intervals. .................... 52
Figure 32: Scheduling in Tmote under different packet injection intervals. .................... 52
Figure 33: Scheduling in Mica2 under different number of sources. ............................... 53
Figure 34: Scheduling in Tmote Under different number of sources. ............................... 53
Figure 35: Scheduling in Mica2 under different buffer siles. 54
Figure 36: The basic principle of lazy loss detection. 56

 

Figure 37: Lost packet retransmission in Mica2 under different packet injection intervals
in three-hop topology. 57

Figure 38: Lost packet retransmission in Mica2 under different packet injection intervals
in two-hop topology. 57

Figure 39: Lost packet retransmission in Mica2 under different buffer sizes in three-hop
topology.

 

Figure 40: Lost packet retransmission in Mica2 under different buffer sizes in two-hop
topology. 59

 

Figure 41: Lost packet retransmission in Mica2 under different packet sizes in three-hop
topology. 61

viii

 

Figure 42: Lost packet retransmission in Mica2 under different packet sizes in two-hop
topology. ' 61

 

 

1. Introduction

1.1 Motivation

Recent advancement in wireless communications and electronics has enabled the
development of low-cost sensor networks. A wireless sensor network comprises small
sensing devices that are powered by batteries, equipped with a small processor and a
limited memory. Each sensor has the ability to sense, compute, and communicate. In
order for sensors to communicate with each other, they use multihop forwarding via
wireless channels. Sensor networks have been widely deployed in certain applications
such as disaster monitoring, battle field surveillance, and handicap assistance. Some of
these sensor network applications suffer fi'om obtaining reliable data transmission and
high packet transmission throughput between sensor nodes due to the lossy nature of

wireless communication and rapidly changing environment.

In this thesis, we aim at improving data transmission reliability and maximizing the
overall transmission throughput in sensor networks. Before investigating various
approaches to accomplish our goal, we start with an extensive study of how radio signals
behave in complex environments. We then design and implement a MAC layer overlay

which consists of channel access scheduling and lost packet retransmission.

 

1.1.1 Radio Signal Behaviors

Some sensor network applications make use of radio signal strength (RSS) for
range estimation. In sensor networks, radio signal strength is defined as signal power
received by a reference antenna. Radio signal strength is suitable for range estimation
because RSS information can be collected easily without any additional cost with each
signal sent and received. To estimate the distance between a pair of sensor nodes, we
measure the received signal strength from the sender and find the corresponding distance
from a pre-defined RSSI model, in which it has a defined rate of signal strength
attenuation over distance. RSSI is defined to be the voltage in the received signal strength
indicator (RSSI) pin on our radio signal [1]. Several RSSI models have been developed
for range estimation, such as the linear and theoretical models. These models do not
usually provide accurate distance estimation because signal strength does not correlate
linearly with distance [1]. However, this methodology is an attractive alternative because
it is costless and easy to implement. The main problem of RSS-based ranging is its high
sensitivity to environmental changes. This ranging system has long been known to be
difficult to use for range estimation because it is too “unpredictable” to use for ranging
[1] [14]. The effects of the environment on RSS can be significant, especially in more
complex environments where reflections and obstructions occur continuously. Therefore,

radio signal strength does not always fall off linearly or theoretically with distance.

In the first part of this thesis, we collect the RSSI data that can be used for range
estimation in more complex environments. The degree of complexity depends on the
amount of reflections and obstructions that are present in the environment. Unlike the

signal strength behavior in an open space in which there are no reflections and

 

~‘

obstructions, the signal strength performs much more unpredictable with increasingly
complicated environments. The purpose is to show how great the effects of reflections
and obstructions are on RSSI characteristics. We demonstrate our methodology in a
natural forest with highly dense tall trees and bushes using only 2 sensor nodes; one is
intended for transmitting signals and the other one is for receiving and measuring signal
strengths. We then repeat the experiment in an obstructed basketball court and
classrooms. We also configure the positions of the sensor nodes in some of these
experiments in order to show how signal strength changes at different elevations. It has
been known that small changes in the height of the sensors from the ground can have a
large impact on signal strength [1].

The analysis of the overall RSSI data collections from different experiments tends
to give us an idea about its behavior in different cases. Unfortunately, some of the
experiment results are unexplainable because the environment changes rapidly and
therefore, affects signal strength. This shows that signal strength is not only a bad
indicator for distance measurement but also a weak means of packet transmission. For
example, a packet will be either corrupted or dropped if the signal strength is too low for
the transmission to be carried on. This leads to a relatively low transmission throughput
in certain “unpredictable” environment. However, we extend our research using a

different approach to improve the data transmission throughput.
1.1.2 Receiver-Centric Approach

The main task of a sensor network is to periodically send data to the sink, which is
the main unit that collects and processes data. Sensors usually work on light load unless

there are suddenly activated by unexpected events where they need to forward a huge

3 ‘

amount of data back to the sink within a short period of time. In such a case, it requires
high throughput of data transmission, which is the primary objective of our approach.
However, I the channel contention, together with the lossy nature of wireless
communication, makes it hard to achieve the high throughput of data transmission in
wireless sensor networks. Therefore, to achieve such high throughput via colliding
channels, two possible approaches are i) reduce channel collision by scheduling channel
access among neighboring sensors; ii) ensure reliable data transmission by retransmitting

lost packets.

Certainly we know that communication throughput in a wireless sensor network
can be severely degraded by channel collisions since wireless channels can interfere with
each other during broadcasting. This is a serious problem in a wireless sensor network
when a large number of sensors keep forwarding data packets to the base station. To
solve this problem, several Time Division Multiplex Access (TDMA)-based Medium
Access Control (MAC) protocols [16] [17] have been proposed to statically assign time
slots for channel access for neighboring sensors. However, TDMA is hard to deploy in
wireless sensor networks since it needs a global view of the entire network topology and
static time slot assignment cannot adapt to dynamic network change. Moreover, TDMA
reduces channel utilization if idling time slots exist. On the other hand, the Carrier Sense
Multiple Access (CSMA)-based MAC protocol is more flexible to changing network
topology and easy to deploy in wireless sensor networks. Several well-known MAC
protocols such as S-MAC [18], T-MAC [l9], and B-MAC [20] have used the CSMA

mechanism. However, the problem with CSMA is that it may increase channel collision.

 

Some hybrid protocols combining both CSMA/TDMA [21] [22] have been proposed to

compromise the disadvantages of both CSMA and TDMA.

For the second part of this thesis, we propose a receiver—centric protocol that
implements a channel access scheduling on the CSMA MAC layer and integrates lost
packet recovery. The proposed protocol that acts as an overlay between network layer
and link layer is designed to improve CSMA. It uses a tree-based topology where each
intermediate sensor receives packets from multiple sources and then forwards those
packets to its parent at higher level. The basic unit consists of one parent (receiver) and

multiple sources (senders). The receiver manages scheduling and retransmission.
1.2 Objectives

We have several objectives in this thesis. We first experimentally study how radio
signals behave in certain environment settings. Some environmental factors have severe
effects on radio signal strength'and thus, affect data packet transmissions. Most of the
factors are unavoidable because they happen so naturally in the environment, and
therefore, environment is unlikely to be tailored for better data communication
throughput. Since tailoring the environment to obtain better packet transmission
throughput is not a viable solution, we therefore implement a combined approach using
channel access scheduling and lost packet recovery to improve data transmission
throughput, even if the transmission has to take place in a more complicated environment

settings. This is our second objective in this research.
1.3 Organization

Chapter 2 discusses related work in two different scopes. In Chapter 3 we present

an extensive study of radio signal strength and its behavior in different complex

environments. We then describe the receiver-centric approach used to improve the
throughput in data packet transmission in Chapter 4, where we define the problem
definition and its basic idea and mechanisms to improve throughput in sensor networks.
In this chapter, we also include the experimental configuration and evaluation results for
both channel access scheduling and lost packet retransmission. In Chapter 5 we conclude

our research work and present future work.

 

2. Related Work

2.1 Related Work in Radio Signal Behaviors in Complex
Environments

Radio Signal Strength (RSS) has evolved as a common technique used for ranging.
Ranging is the process of estimating the distance between two nodes [1]. Many studies on
RSS have been conducted recently to determine its accuracy and consistency for ranging.
Most of the studies are focused on the factors that may influence signal strength behavior
in different environments. For example, obstructions, reflections, interference, and sensor
nodes variability can influence greatly the signal strength behavior. Table A summarizes
how the height of nodes, grass, and the different level of transmission powers affect radio
signal strength. Three different environments have been chosen for the experiment
purposes. First, the data collections took place in a large indoor room that is filled with
chairs and other items. Then, the experiment is moved to a small field with low grass, but
with several tall trees and buildings in the surrounding area. Lastly, a slightly different
environment is selected, which is in a large open field with tall grass for the same
experiment objectives. The results show that the height of nodes, height of grass, and
transmission power all yield the same effects on RSS characteristics. Furthermore, there

are other factors that have significant impact on signal strength.

‘

 

Table A: Summary of Factors Affecting Radio Signal Strength

 

 

 

 

 

Environment Height of Node Height of Grass Transmission
Characteristics Power
Large room with Higher position - Higher
cluster of chairs leads to lower transmission power
attenuation rate and yields lower
higher range attenuation rate and
higher range
Open field with low Higher position Short grass yields Higher
grass (8cm), but leads to lower lower attenuation transmission power
with tall trees and attenuation rate and rate and higher yields lower
buildings higher range range attenuation rate and
higher range
Open field with tall Higher position Tall grass yields Higher
grass (30cm) leads to lower higher attenuation transmission power

 

attenuation rate and

higher range

 

rate and lower

range

 

yields lower
attenuation rate and

higher range

 

 

 

Most systems that use RSS for ranging report that indoor environment is not
appropriate for RSS ranging because there is no correlation between signal strength and
distance [3] [12] [13]. This shows that the reflections and obstructions can make a major
impact on signal strength behavior. A study has reported that radio signals can take
multiple paths while they transmit and their signal strength changes when they hit an
obstacle [7]. The hitting on obstruction will results in two different signals, called the
transmitted and reflected signal, respectively. Their report also shows that the strength of
the transmitted and reflected signals depends on the angle at which they hit the
obstructions [7]. However, there seem to be too many variances in the experiment. One
of the problems is that no one can guarantee at which point the original signal is going to
hit on the obstacle even though the degree at which the signal is facing the obstacle is
fixed. There is no way to determine a signal transmission path because a signal can travel
in multiple ways to reach the receiver. Therefore, we will only demonstrate how signal
strength behaves in both indoor and outdoor environments with the presence of
reflections and obstructions. The effect of obstructions on RSS is certainly easier to be
tested as compared to reflections, because one can manually place an obstacle between
the sender and the receiver to see how that obstacle affects signal strength. However, it is
difficult to test the reflection effects since reflections can be caused by the floors,
ceilings, walls, and other materials in the surroundings. In this paper, we have
investigated the effects of both obstructions and reflections in a more complicated indoor
and outdoor environments in order to show that RSS is even worse for range estimation

in those environments.

 

‘

2.2 Related Work in Channel Access Scheduling and Lost Packet
Retransmission '

Many approaches have been proposed to improve the performance of data
transmission in wireless sensor networks. Some of these approaches have been described

in the Introduction section. We continue the remaining related work in this section.

MAC is important in sensor network since multiple nodes transmit data via the
shared channel. Therefore, it requires a good mechanism to control channel access among
multiple nodes with the aim to reduce channelcollisions. Several TDMA-based protocols
use the idea of time slots assignment among nodes within the network topology [16] [17]
[21] [23]. However, this protocol has several disadvantages: it requires global view
knowledge of the network topology, it is inflexible, and it is non-scalable. Other TDMA-
based solutions include SS-TDMA [31] and Infiise [32]. Conversely, the major MAC
protocols that have been implemented in sensor networks are CSMA-based [18] [19]
[20]. Hybrid solutions of CSMA and TDMA have been proposed to reduce channel
collision while maintaining the flexibility of CSMA. For instance, Z-MAC has been used
to switch between CSMA and TDMA depending on data transmission rate. Z-MAC uses
TDMA for high data transmission rate and CSMA for lower rate of data transmission to
maximize channel utilization. Another solution proposed, Funneling-MAC [22], uses
TDMA in the area that is close to the sink and CSMA in the rest of the network. It is
based on the idea that channel contention is much higher in the area closer to the sink.
Therefore, TDMA is applied to that small area while CSMA is applied to the rest. Unlike
these approaches, the receiver-centric approach neither replaces the CSMA nor

complements the CSMA. Our approach aims to reduce channel collision while retaining

 

‘

the flexibility and scalability of CSMA by applying a media access scheduling on the

CSMA. Our approach can also be integrated to the CSMA part of any hybrid solution.

It is necessary to control sending rate of data packet from sensors to the sink.
Otherwise, channels may be overloaded when large numbers of sensors continuously
send packets and compete for channel access. Therefore, several solutions to control
packet sending rate based on the channel utilization have been proposed [24] [25] [26]
[27] [28]. Unlike these approaches, our approach emphasizes channel access scheduling

along with the control of packet sending rate in order to achieve high channel throughput.

 

 

3. Radio Signal Behaviors

3.1 An RSS Ranging System

In wireless sensor networks, one purpose of radio signal strength (RSS) is to
estimate distances between sensor nodes. This is often used in sensor localization, sensor
scheduling, and other types of applications. A Radio Signal Strength (RSS) ranging
system works by measuring the received signal strength. The value of the signal strength
can be obtained from the RSSI pin on the radio signal, and the RSSI value is inversely
proportional to the signal strength. Greater RSSI value implies weaker signal strength,
and vice versa. Throughout this paper, we will use the RSSI value as an indicator for the
signal strength. The system consists of a sender and a receiver. The sender sets its
transmission power to the highest value, lOdBm. The sender sends out messages
continuously, and the receiver collects the RSSI value of each message at a certain
distance from the sender. For each 100 message received, the receiver computes the mean
RSSI and outputs the mean value on the PC through an I/O port. This step is repeated by
varying the sender at different locations. By comparing the RSSI value with some pre-
defined RSSI models such as the linear RSSI model and the theoretical RSSI model, the

distance between the sender and the receiver can be estimated.

 

 

 

Before any RSSI values can be received, we need to know how far a signal can
transmit at different transmission powers. In order to test how transmission power relates
to distance, we performed an experiment in which the sender is fixed and programmed
with different level of transmission power. For each transmission power level, we
measured the maximum distance in which the receiver can receive the signal that is
transmitted from the sender. The experiment took place in the hallway on the third floor
of the Michigan State University (MSU) Engineering Building. The result of the

experiment is shown in Figure l.

 

Maximum measurable distance vs Transmission
power

  

Maxim um distance

oaaas‘s‘é‘é

 

-20dBm -13dBm OdBm 5dBm 10dBm

Transmission power

 

 

 

Figure l: The maximum measurable distance between nodes for various
transmission powers.

By increasing the transmission power, the sender can transmit the radio signal for a
longer distance. When the transmission power increases from -20dBm to 10dBm, the

maximum measurable distance also increases by up to 99.5ft. This corresponds well with

‘

 

the predicted result [1]. Each increment in the transmission power will increase the

strength of the signal, and therefore, the signal can travel a longer distance.
3.2 Signal Strength Behaviors in Complex Environments

Different environments cause signal strength to act differently. We perform some
experiments in both indoor and outdoor environments to illustrate this point. In these
experiments, we fixed the receiver in the middle of the selected location and varied the
sender at the distances of 10ft, 20fi, 30ft, 40ft, SOfi, 60ft, 70ft, and 80fi from the receiver.

For each range, we measured the received signal strength.
3.2.1 Comparing Indoor with Outdoor Environments

In this section, we compare the signal strength behavior in indoor and outdoor
environments. The experiment took place at the third floor of the MSU Engineering
Building (indoor) and at a campus parking lot (outdoor). Figure 2 shows the signal
strength measurement in the open parking lot. The result of the experiment is shown in

Figure 3.

The result shows that signal strength is correlated with distance in the outdoor
environment, but not in the indoor environment. In the open outdoor field, as the distance
between the sender and the receiver increases, the strength of the signal becomes weaker.
However, this is not the case in the open hallway. Signal strength does not correlate with
distance. The signal strength fluctuates in an unknown pattern over distance. As shown in
Figure 2, the signal strength at the range of 3011 is even stronger than at the range of 20ft.
This makes RSS-based ranging difficult in an indoor environment, even though the

environmental factors in many studies are often held constantly indoor.

 

Figure 2: An open flat parking area without obstructions.

 

 

RSSI

350

 

300 «

250 -

200 <

150 —

100 ~

50—

~ __,
ha-

....... Open hallway
(mean)

 

— Open field
(mean)

 

 

 

I I I l I

10ft 2011 3011 40ft 5011 6011 7011 801i

Distance

 

Figure 3: Radio signal behavior in indoor and outdoor environments.

 

 

However, the signal strengths appeared to be weaker (indicated by higher RSSI) in
an outdoor environment than an indoor environment. Another disadvantage of using RSS
ranging system in an outdoor environment is that the maximum range is smaller. As
shown in Figure 3, the maximum range is only 60ft in the open field, which is smaller
than in the open hallway. As a result, both the indoor and outdoor environments have

their own disadvantages in using RSS-based ranging.

3.2.2 Comparing Different Outdoor Environments

 

 

 

 

 

 

350
300 «
250 -
------- Grassy field
a 200 : (mean)
a 150 —— Open field
I (mean)
100 —
50 -
o l T 17 I l I l
10fl 20ft 30ft 4011 50R 6011 70ft 80ft
Distance

 

 

 

Figure 4: Radio signal behavior in different outdoor environments.

In this section, we compare the signal strength behavior in different outdoor
environments. The experiment took place at a small soccer field and at the parking lot on
Service Road as shown in Figure 2. The result of the experiment is shown in Figure 4.

No obvious distinction can be obtained from Figure 4. Again, the result shows that

signal strength is correlated with distance in different outdoor environments. It shows that

‘6 A

the greater the range, the smaller the signal strength. Those short grasses in the soccer
field do not have a great impact on the signal strength. Therefore, the effects of short
grass on RSS can be ignored. However, tall grass can have large effects on signal
strength. The taller grass yields weaker signal strength and affects the range estimation
accuracy [1]. Such effects can be minimized as long as the height of the grass is less than
the height of the sensors from the ground. On the other hand, there are some other factors
that may have a great influence on signal strength. These factors will be analyzed in the

following section.
3.3 Environmental Effects on RSS

In Section 3.3.1, we will demonstrate the effects of different elevations of sensor
nodes on radio signal strength. Then, in Section 3.3.2 and 3.3.3, we will show the effect

of Obstructions and reflections on signal strength, respectively.
3.3.1 Height of the Sensor Nodes from the Ground

In this section, we will demonstrate how the position of sensor nodes from the
ground affects the radio signal strength. In order to show this, we performed the
experiment in which both the sender and the receiver are placed on the ground at first,
and then, we lifted them up to 2.5ft, 3ft, 3.5fi, and 411 from the ground using two tripods
for elevation, one for each sensor. The receiver is fixed and the sender is varied at the
distances of 10ft, 20ft, 30ft, 40fi, 50ft, 60ft, 70ft, and 80ft from the receiver. The
experiment took place at the open parking lot shown in Figure 2. The experiment setting
is shown in Figure 5. Figure 6 shows the result of this. For the same experimental

objective, we performed another experiment in two classrooms. Similarly, both the

17 ‘

 

Figure 5: The assistance with tripods to raise the sensor nodes.

 

 

RSSI

 

 

 

 

350
300 « — Open field (on the
ground)
25° ‘ ------- Open field (2.511
200 , from the ground)
- — — — Open field (3ft
150 - from the ground)
100 , — — — — Open field (3.511
from the ground)
50 « ------- Open field (4ft
0 . from the ground)

 

1011 2011 30ft 4011 5011 6011 7011 8011

Distance

 

Figure 6: Elevation of sensor nodes affects signal strength in the outdoor
environment.

 

 

sender and the receiver are placed on the ground at first, and then, we lifted both sensors
from the ground to the height of 2.511 using desks. We placed the sender in one classroom
and the receiver in the other classroom. We then varied both the sender and the receiver
at the same distance from the wall that separated the two classrooms. The setting is

shown in Figure 7. Figure 8 shows the result of this experiment.

Both the sensor nodes in the previous two experiments were positioned at the same
height. However, we are interested in determining how signal strength behavior changes
if both the sender and the receiver are of different height from the ground. To show that,
we performed an experiment in which we placed the sender on the ground and varied the
receiver at the heights of 2ft, 2.511, 311, 3.511, and 4ft from the ground. In the experiment,
we fixed the distance of 2011 between the sender and the receiver. We then repeated the
experiment by changing the distance between the sender and the receiver to 40ft and 6011.
The experiment took place in the same location as shown in Figure 2. Figure 9 displays
the experimental result. We later repeated the same experiment with slightly different
settings, in which the receiver was placed on the ground and the sender was varied at

different heights from the ground. Figure 10 shows the result of this experiment.

Both Figure 6 and 8 showed that the height of the sensors from the ground can have
a great effect on signal strength. It shows that the higher the position of the sensor from
the ground, the stronger the signal strength. This conclusion holds for both outdoor and
indoor environments. This corresponds well with the predicted result. The idea is that a
signal can possibly overcome most of the obstructions (e.g. pedestrian, moving vehicle,
and etc) if the sensors are positioned higher from the ground. How obstructions affect the

signal strength behavior will be discussed in the Section 3.3.2. However, there is a

 

difference between indoor and outdoor environments. There is a linear correlation
between signal strength and distance in the outdoor field, but not in the indoor field. The
results for indoor environment seem to be unpredictable due to the effects of obstructions
and reflections. In the indoor environment, there are more obstructions such as walls.
When a signal path is blocked, it either passes through the obstacle and has weaker signal
strength after passing it, or it is reflected from the obstructions. The effects of
obstructions and reflections will be discussed in the following sections. On the other
hand, there are less obstructions and reflection effects in the outdoor environment. The
signals are not easily reflected by obstructions because the area of an outdoor
environment is larger than an indoor environment. As a result, the RSS range estimation

is believed to be more accurate if the sensor nodes are positioned higher from the ground.

However, this result is not necessarily true if both the sensor nodes are positioned at
different elevations. This can be seen from Figure 9 and 10, in which only one of the
sensors is placed on the ground and the other one varied at various heights. Both figures
show that signal strength does not rise linearly with height. One possible reason is that
the scale that is being used for the height is too small (eg. 0.511). The difference between
the highest and lowest height is just about 211. There are some RSSI measurement errors
within this small scale. However, if we increase the scale for the height to about 111, then

we will see a more error-free result, as predicted from the previous studies.
3.3.2 Effects of Obstructions

Obstructions are one of the major concerns in RSS ranging systems. Radio signals
lose strength when traveling through obstructions such as walls, floors, and vehicles.

Large obstructions can even block a signal completely. In this section, we show how

20

 

‘

 

RSSI

511, 1011, 1511, 2011, 511, 1011, 1511, 2011,
2511. 3011, 3511, 4011 2511, 3011, 3511, 4011

Receiver Sender

D D

A
r

 

 

1011, 2011, 3011, 4011, 5011, 60ft, 7011, 8011

Desks and chairs Desks and chairs

 

— Wall

Figure 7: Placement of sensor nodes in two classrooms.

 

 

 

 

350

300 ------- Wall between

250 - sender & receiver
(Both are placed

200 - on the table)

150 , Wall between

. sender & receiver

100 . (Both are placed

on the floor)
50 —
O T I I I 1 r I

 

 

 

1 011 3011 5011 7011
Distance

 

Figure 8: The effects of lifting both sensors in the indoor environment.

21

 

 

 

 

350

 

 

 

 

 

 

 

 

 

 

 

 

— — — — 2011 (distance
300 ~ /\——\ between
, .. ....... sender and
250 “ “ - ’ I ‘ ~ receiver)
_ 200 , \ \ ‘ ------- 4011 (distance
3 \“~\--/ """ \ between
I! 150 — \ ~ sender and
receiver)
10°“ —60ft (distance
50 , between
sender and
o , , , , receiver)
0.011 2.011 2.511 3.011 3.511 4.011
Height
Figure 9: The effects of different elevations of receiver on signal strength.
350
— - - - 20ft (distance
300 — between
sender and
250 ‘ receiver)
_ 200 - \ \ ------- 4011 (distance
5’, ‘\\,/”\\L\/,-z~\ between
I! 150 - \ sender and
receiver)
100 — .
— 60ft (distance
50 , between
sender and
0 . . . . receiver)
0.011 2.0ft 2.511 3.011 3.511 4.011
Height

 

Figure 10: The effects of different elevations of sender on signal strength.

22

‘

 

 

obstructions affect the signal strength behavior and cause large errors in range estimation.

We will demonstrate the effects of obstructions in both indoor and outdoor environments.
3.3.2.1 Outdoor Environment

To show how obstructions affect signal strength outdoors, we performed an
experiment in which the sender and the receiver are separated by a medium-sized vehicle
that is parked in an empty parking lot. The receiver was fixed at 1511 from one side of the
vehicle, and the sender was placed on the other side of the vehicle. Then, the sender was
varied at the distances of 1011, 2011, 3011, 4011, 5011, 6011, 7011, and 8011 from the receiver.

Both the sender and the receiver were placed on the ground. The result is depicted in

 

 

 

 

 

 

 

Figure 11.
350
300 .
250 - ------- Open field
200 (mean)
a
m
I! 150 «
A car between
100 ~
sender and
50 _ receiver (mean)
0 T I 1 I I I I
1011 2011 3011 4011 5011 6011 7011 8011
Distance

 

 

 

Figure 11: The line of sight (LOS) is obstructed by a mid-sized vehicle.

Additionally, we performed another experiment in a more complex outdoor

environment. The experiment is located in a natural forest clustered with tall trees and

 

bushes and it is not a flat open area. Therefore, we used two tripods to lif1 both the sender
and the receiver up to 2.511 from the ground. In the experiment, we fixed the receiver and
then varied the sender at the distances of 1011, 2011, 3011, 4011, 5011, 6011, 7011, and 8011
from the receiver. Figure 12 depicts the experimental environment and Figure 13 shows

the experimental result, respectively.

The result of the experiment shows that obstructions can have great effect on signal
strength. When the transmitting signal reached the obstruction, it is either passes around
the obstruction or deflected by the obstruction [2]. A great portion of the signal strength
is absorbed by the obstacles (eg. car and trees) when the signals try to pass through them.
Therefore, signals that have successfully passed through the obstruction suffered
reduction in signal strength. This can be seen from the graphs in Figure 11 and 13,
respectively. From Figure 11, the RSSI value increases by 190.5 from 1011 to 2011
(reduction in strength). However, the RSSI value only increases by 61 from that same
range in an unobstructed environment. On Furthermore, as the sender is placed
increasingly further from the vehicle, the reduction in signal strength is smaller.
However, the signal strength behavior is more complicated in the forest, as shown in
Figure 13. There are more fluctuations in signal strength readings due to both the
combination of reflections and obstructions effects. Hence, RSS is not a good choice for

distance estimation in an obstructed environment.
3.3.2.2 Indoor Environment

To show how obstructions affect signal strength indoors, we performed two
experiments in which the sender and the receiver were separated by a wall in both

experiments. The first experiment took place in two classrooms. These classrooms were

 

Figure 12: A natural forest with a cluster of tall trees and bushes.

 

 

R851

350

300

250 <

200 ~

150

100

50

 

....... Open field (2.511
from the
ground)

 

Forest (2.511
from the
ground)

 

 

 

 

I T l

1011 2011 3011 4011 5011 6011 7011 8011

Distance

 

Figure 13: The line of sight (LOS) is obstructed by tall trees.

25

 

 

separated by a wall. In order to minimize the effect of other obstructions, we rearranged
the tables and chairs in both classrooms. Figure 7 on page 14 shows the arrangement in
the classrooms. The sender was placed in one classroom and the receiver was placed in
the other classrooms. Both were placed on the floor. Before we measured the RSSI of the
received signal, we varied both the sender and the receiver at the same distance from the

wall each time. Figure 14 shows the result of the experiment.

 

 

 

 

 

 

350
------- Open hallway
300 i (mean)
250 - """
a 200 ~
g ., ,1
150 i — Wall between
100 ~ senqera‘.
receiver In two
50 - . classrooms
(mean)
0 I l I I I | T
1011 2011 3011 4011 5011 6011 7011 8011
Distance

 

 

 

Figure 14: The line of sight (LOS) is obstructed by a wall.

The second experiment took place in a large indoor basketball court. There is a
small store room next to one side of the basketball court. The experiment was done in
three different ways in which both the sender and the receiver were placed on the ground
each time. First, we found the middle point of the basketball court. We then varied both
the sender and the receiver at the distances of 511, 1011, 1511, 2011, 2511, 3011, 3511, and 4011

from that middle point. Both sensors are placed on the same side. This result is used as a

26

 

baseline comparison and is depicted in Figure 15. Figure 16 shows a photo of this setting.
Second, we fixed the sender at a distance of 911 away from one side of a wall (in the store
room) and then we varied the receiver at the distance of 111, 1111, 2111, 3111, 4111, 5111,
6111, and 7111 from the other side of the same wall (in the basketball court). This setting is
shown in Figure 17. Lastly, we repeated the second experiment by reversing the position
of the sender and the receiver. Figure 18 shows the combinations of the results of the

experiments.

The result of the experiment in an indoor environment shows that obstructions sirch
as wall have a great influence on radio signal strength, similar to the obstruction in an
outdoor environment. When a signal transmits through the wall, it is either passes around
the wall or is deflected by the wall. Most of the signal strength is absorbed by the wall
when the signals try to travel through it [10]. Therefore, signals that successfully passed
through the obstruction suffered great reduction in signal strength [11]. At a shorter
distance, the signal strength may be stronger in the obstructed condition. Perhaps the
strength of the signals is constantly high if it travels through short distances, even though
obstructions occurred. However, the reduction rate of signal strength over distance is still
perceived to be distinctively high in an obstructed environment compared to the
unobstructed ones. Furthermore, the maximum range that can be measured in an
obstructed condition is clearly smaller than in an unobstructed one. From Figure 18, the
maximum range is only 30-4011 in the presence of the wall, which is less than the one
without the wall. Hence, RSS ranging can provide large errors in distance estimation

since it is highly sensitive in an obstructed environment.

27

 

‘

 

Entrance .
Basketball court

4511

Sender Receiver
Middle point

' D

——-——-—+

1011, 2011, 3011, 4011, 5011, 6011,
7011, 8011

— Wall

 

 

 

Figure 15: Environment for baseline metric measurement without obstructions.

 

Figure 16: The real environment shown in Figure 15.

28

 

Entrance i

Receiver

Basketball court

111, 1111, 2111, 3111,
4111, 5111, 6111, 7111

Store
room

Sender

 

D

— Wall

 

1011, 2011, 3011, 4011,
5011, 6011, 7011, 8011

 

 

91D

Figure 17: The setting in a basketball court for testing wall effects.

 

R“ ,_,_, ,

400

 

350 -
300 -
250 ~

RSSI

200 a
150 <
100 -
50

 

 

 

 

I

1011 2011

 

3011 4011 5011

I I I

6011 7011 8011
Distance

- — — - Open basketball
court (sender and
receiver are on
the same side)

Wall between
sender & receiver
(sender is fixed at
911 away from the
wall)

------- Wall between
sender & receiver
(receiver is fixed
at 91t away from
the wall)

 

 

Figure 18: The line of sight (LOS) is obstructed by a wall in Figure 17.

29

 

‘

3.3.3 Effects of Reflections

In addition to obstructions, reflections from the objects around the environment can
also cause an impact on radio signal strength. In this section, we show how reflections
affect the signal strength behavior in both indoor and outdoor environments. The effect of

reflections is shown to be more severe in indoor environments.
3.3.3.1 Outdoor Environment

To show how reflections affect signal strength in outdoor environments, we
performed two experiments in which both the sender and the receiver were placed on the
ground. The first experiment took place at the parking lot describe in Section 3.3.2.1. In
the experiment, we fixed the receiver at the distance of 111 from a medium-sized vehicle
and varied the sender at the distances of 1011, 2011, 3011, 4011, 5011, 6011, 7011, and 8011

from the receiver. The result is shown in Figure 19.

The second experiment took place at the forest location shown in Figure 12. The
purpose of the experiment is to demonstrate the effects that reflections from tall trees and
bushes have on signal strength. We fixed the receiver and varied the sender at the
distances of 1011, 2011, 3011, 4011, 5011, 6011, 7011, and 8011 fi'om the fixed receiver. The

result is shown in Figure 20.

From all the tests performed in this section, we can observe that there are some
reflections in outdoor environments. The effects of reflections on signal strength depend
on the complexity of the outdoor environments. The less complex environment has fewer
reflections than a more complex one. As shown in Figure 19, the signal strength behaves
as if it were in an open space environment. However, signal strength exhibits a slightly

more complicated behavior in the forest as shown in Figure 20. There are more trees and

3" A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

300 a
250 - — Open field
(mean)
200 i
3
a: 150 —
------- Receiver is
100 “ fixed at 111 near
50 , to a car (mean)
0 I I I l I I I
1011 2011 3011 4011 5011 6011 7011 8011
Distance
Figure 19: The effects of reflections from a mid-sized vehicle.
350 — ~
300 «
250 —
_ 200 -
g —— Open field (mean)
or 150 «
100 - ------- Forest
0 I I I I T I I

 

 

 

1011 2011 3011 4011 5011 6011 7011 8011

Distance

 

 

Figure 20: The trees reflections on signal strength.

31

 

bushes in the experiment surroundings, and that can possibly cause some reflections.
Despite the reflections, the signal strength is still correlated to distance for the range up to
about 6011. This shows that an outdoor environment could be an ideal place for RSS-

based ranging even though reflections occurred.
3.3.3.2 Indoor Environment

To show how reflections affect signal strength indoors, we performed three
experiments in which both the sender and the receiver were placed on the ground. In the
first experiment, we fixed the receiver at the distance of 111 from a wall and varied the
sender at various distances from the receiver. The experiment took place in the same
hallway location described in Section 3.2.1. The experiment was then repeated by fixing
the receiver at 811 from the same wall. Figure 21 shows the experiment setting. The result

is shown in Figure 22.

In the second experiment, we fixed the sender at the distance of 5011 from the same
wall that was used in the previous experiment. The experiment was done in the same
hallway as in the previous experiment. We then varied the receiver at various distances
from the same wall. Figure 23 shows the experiment setting and the result is depicted in

Figure 24.

Lastly, we performed the experiment in a large indoor basketball court as described
in Section 3.3.2.2. We fixed the receiver at the distance of 1311 from a wall, in which
there are some benches in front of the wall. We then varied the sender at various
distances from the receiver. The received RSSI value was collected for each distance.
The experiment was then repeated by fixing the receiver 2611 away from the same wall.

Figure 25 shows the experiment setting. The result is shown in Figure 26.

32

Hallway

 

Receiver Sender

 

 

111, 811

 

 

 

 

 

 

L
r

1011, 2011, 3011, 4011, 5011, 6011, 7011, 8011

_ Wall

Figure 21: Hallway setting for testing wall reflections while fixing the receiver.

 

 

 

 

 

 

350 1--..-__-__-_-.________. -____.._ W. ..-__-_-.,..__h_.r ._ __
300 - I, .' ———— Open field
250 4
— 200 « Receiver is fixed
co
in at 1ft away from
‘1‘ 150 ~ the wall
100 1 ------- Receiver is fixed
50 , at 8ft away from
the wall
0 I I I I I I r
1011 2011 3011 4011 5011 6011 7011 8011
Distance

 

 

 

 

Figure 22: The effects of wall reflections on signal strength for Figure 21.

33

Hallway

 

Receiver Sender

 

 

 

 

 

 

 

511, 1011, 1511, 2011,
2511, 3011, 3511, 4011

 

 

5011

 

— Wall

Figure 23: Hallway setting for testing wall reflections while fixing the sender.

 

 

 

 

RSSI

350

 

300 —

250 ~

200 ~

150~

100 -«

504

 

— Open field

 

------- Sender is fixed
at 5011 away
from the wall

 

 

I F I T I I I

511 1011 1511 2011 2511 3011 3511 4011

Distance

 

 

 

 

 

Figure 24: The effects of wall reflections on signal strength for Figure 23.

34

From all the tests performed in this section, we can observe that reflections can
have a great influence on radio signal strength in indoor environments. From Figures 22,
25, and 27, the radio signal strength appeared to be stronger indoors than signal strength
measured outdoors (open field). The difference in signal strength is caused by the
reflections from objects in the experiment environment such as walls, floors, ceiling, and
other buildings. Since both the sender and the receiver are placed on the ground, the
transmitting signals can get reflections from the ground. The reflections caused by the
floors can be reduced by lifting both the sensors higher from the floor. Some studies have
shown that the effects related to ground reflections will disappear if the distance from the
ground to the sensors nodes is greater than 0.97m [4]. Radio signals are transmitted
through waves and the radio waves from the sender can take different paths while they
travel and their strength can change when they reflect on some obstacles [3]. The above
results show that the reflected signals have stronger strength than original signals. On the
other hand, we expected that the signal strength to be more correlated with distance in a
larger room (eg. basketball court). However, this is not the case as we seen from Figure
26. This is because the radio signals have more opportunities to travel with different
paths, and thus, create more signal interference [3]. As a result, signal strength will not be
a good indicator for estimating distances between sensor nodes in indoor places due to

the effect of reflections.

3.4 Summary

We have demonstrated how signal strength behaves in both indoor and outdoor
environments. Signal strength does not correlate to the distance in an indoor environment,

and it fluctuates over distance. Only a very small range of RSSI values can be used for

35

 

 

 

 

 

 

 

 

 

 

 

 

Basketball
court

13ft & 26ft

1011, 2011, 3011, 4011,

 

 

 

 

 

I Entrance
Bench es
Receiver
Sender
Wall Benches

 

 

 

5011, 6011, 7011, 8011

 

Figure 25: Basketball court setting for testing wall reflections while fixing the

RSSI

receiver.

 

 

 

150 -

100 a

 

50~

 

 

0 I I T I I I I
1011 2011 3011 4011 5011 6011 7011 8011

Distance

 

 

 

_ _ _ — Open field (mean)

—— Receiver is fixed at
1311 from the well
(both sender and
receiver are placed
on the ground)

------- Receiver is fixed at
26ft from the wall
(both sender and
receiver are placed
on the ground)

 

 

Figure 26: The effects of wall reflections on signal strength for Figure 25.

36

estimating the distance between a pair of sensor nodes in an indoor environment. There
are several factors that caused the signal strength to perform differently indoors. The
effects of obstructions and reflections on signal strength are the major problems in RSS.
Therefore, signal strength information is shown to be an unreliable indicator of distance
in complex indoor environments due to obstacles and reflections [5]. When a signal
travels through an obstruction, even if it successfully penetrates over, it loses its strength
[3]. This happens because the obstruction can absorb the signal and weaken its signal
strength [2]. More ofien, the signal not only goes through the obstacle, but it also gets
reflected when it hits the obstacle. This usually happens in indoor environments, in which
there are a number of nearby objects such as walls, floors, and fumiture. Both the original
signal and the reflected signal reach the receiver almost at the same time because they are
traveling at the same speed. As a result of this, the receiver is not able to distinguish the
two signals and it measures the received signal strength for both of them [6]. The
transmitted and reflected signals are weaker than the original signal. The strength of both
the transmitted and reflected signals depends on the angle at which it hits the obstacle [7].
However, obstructions and reflections do not have too much impact in an outdoor
environment since there are apparently fewer objects in an outdoor field. As a result, an

outdoor field appears to be an ideal place for RSS ranging system [15].

Yet, there are still other factors that influence radio signal strength in RSS-based
ranging. We have demonstrated that the higher the sensor nodes from the ground, the
stronger the received signal strength. By li11ing up the sensor nodes, we can possibly
avoid most of the obstructions that can undermine the signal strength. Furthermore, we

also showed that transmission power is correlated to distance. For instance, higher

37

transmission power can be used for longer range estimation. By setting the transmission
power to its highest, the signal is initiated with the strongest strength, and therefore, it can

transmit for a longer distance.

Hence, RSS is shown to be inappropriate for range estimation, especially in indoor
environments. It does not produce reliable distance estimation based on RSSI. It is only
good for very short range estimation. However, RSS provides more accurate results for
estimating distance between sensor node pairs in an outdoor environment since the
received signal strength is more correlated to distance. This shows that environment
changes have great effects on signal strength. Weak signal strength tends to corrupt or
drop packets during transmission, and therefore, results in a relatively low data
transmission throughput in “unpredictable” environment. In the next section of this
thesis, we extend our research to improve the data transmission throughput without

considering any environmental factors.

38

4. Receiver-Centric Protocol

Our previous experiments with RSS demonstrate that tailoring the environment for
better data transmission throughput is a very difficult task since signal strength that is
used as a means for packet transmission becomes very weak when obstructions and
reflections exist. Based on this result, we look for another alternative to achieve better
transmission throughput without rely on the environment. Therefore, we introduce a
protocol called receiver-centric, which is a MAC layer overlay that aims to improve
communication throughput of sensor networks. The receiver-centric protocol consists of

two parts: the channel access scheduling and the lost packet retransmission.

4.1 Channel Access Scheduling

We present the issues of media access control in sensor networks and discuss how

these issues can be addressed by our approach.
4.1.1 Problem Definition

Data collection in wireless sensor networks acquires numerous sensors to
simultaneously send packets through radio channels of the same frequency. Therefore,
media access control (MAC) needs to control the access to these shared channels among
neighboring sensors. Major MAC protocols [18] [19] [20] implementing Carrier Sense

Multiple Access (CSMA) have been widely deployed for this application due to its high

39

flexibility and adaptability. CSMA uses a carrying sensing multiple access mechanism to
schedule neighboring sensors to access a shared channel. Each sensor has to listen to the
shared channel and forward packets only if the channel is idle. Therefore, it is possible
that two sensors will forward packets at the same time when they both acknowledge that
the channel is idle. This causes collision and corrupts packets. To solve this problem, the
back—off mechanism is proposed. A sender may back-off for a random time before
sending out packets. A sender may keep resending a packet multiple times when a group
of senders try to send packets at a high transmission rate. This event intensifies the
collisions among packets and thus, reduces its transmission throughput. To reduce
channel collisions, the receiver-centric approach imposes a channel access scheduling,
which aims to improve CSMA. The design and implementation of channel access

scheduling are described in the following subsection.
4.1.2 Basic Idea

The receiver-centric protocol works with CSMA in channel access scheduling.
Sensors are still using CSMA to access shared wireless channels. In the tree-based
topology, the intermediate node acts as a parent and receives packets from multiple
children; therefore, it becomes a perfect candidate to schedule packet transmission. The
channel access scheduling is shown in Figure 27. The receiver-centric protocol takes
advantage of the broadcast nature of wireless channels for scheduling purposes. The
protocol uses two alternative approaches. First, we can reuse the acknowledgment
packets (ACKs) to schedule children’s packet transmission if a time-out mechanism is
used by MAC. Due to its broadcast nature, the ACK sent to one of the children can be

overheard by all children. Therefore, we schedule children’s packet transmission by

40

piggybacking a scheduling message to ACKs, where the message contains the ID of the
children that are scheduled to send the packet in the next iteration. All children will
overhear the message and each child will determine if it is its turn to send packets by
matching the schedule ID to its own ID. If they match, the node will start sending
packets; otherwise, it holds its transmission for the next schedule ID. It is easy to see that

only scheduled child transmits packets, and thus, reduces channel

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

LS‘4
L513 \
' .\
‘82? a ---------- -.
Sl P Sink
I
S1 P S, P .53 P S4 P
I-—_ F-TTTF-"TF-T-TF’T’TF‘T“-F’TTTF-T-T
l I I I l I I I
__-_L--__L-___L____L___-L__-_I
I t I I
. . 2 : . : . : :
r"" ""r""r""r‘-"r""I
I I 0 I I I I I
L--__L_-__ ___-L_-_-L-___L___J
: : : 3 l : : : :
F-T'TF-T—TFTTTT """" F'T'TF-T-TI
I I I I t J I I I
L____L-___L-___L-___ ___-L-_-_l
I I I I I I I
I I I I I I 4 I I
F-T'TFT'T'F'T'TF'T'TF'T"I "T'l
I I I I I I h I
L----L-___L___-L____L___-L____
I
I

 

 

 

Figure 27: Receiver-centric protocol schedules time slots in a round-robin fashion
via overbearing.

collisions. Note that the scheduling is only done within the basic unit, which is between

its immediate parent and children. Second, we can use multihop forwarding without

41

reliance on ACKs. When a parent receives packets from its children, it continues to
forward the packets to the next hop by attaching a schedule ID to those packets so that

the schedule ID can be overheard by its children.
4.1.3 Scheduling Mechanism via Overhearing

Each intermediate node contains a buffer, implemented using a queue, which stores
all packets received from its children. These packets are buffered at the tail of the queue
(enqueue operation). A background queue service task keeps fetching packets from the
head of the queue and transmits the packet when it overhears the matching schedule ID
(dequeue operation). To reduce channel collision, we insert a delay timer to dequeue
operation so that the queue service task will hold for a certain time period before sending
out the next packet. During this time, the children wait for the scheduling message from
the parent via overhearing. The parent attaches a one-byte field that contains the next
schedule ID to the packet. A child will start transmitting a packet if its ID matches the
schedule ID; otherwise, the child will reset its delay timer and continue to wait for the
next schedule ID. The channel access scheduling utilizes the round-robin fashion to
ensure fairness among children, i.e. when the parent forwards a packet from child 1', it
will attach node ID i+1 to the scheduling field, and continuing in this fashion. Figure 27
illustrates the round-robin scheduling. When parent P forwards a packet from node 1, the
node ID 2 is attached to that packet, which can be overheard by all its children. Only
node 2 will start sending its packet in the next round while other nodes hold on to their
transmission. All children will have their chance to transmit packet in the round-robin

process without intensifying channel collisions.

42

4.2 Lost Packet Retransmission

Lost packets retransmission is widely used to ensure reliable data transmission in
wireless sensor networks. However, our experiments show that the channel collision can
also be intensified by lost packet retransmission. We define this problem and discuss how

the receiver-centric protocol addresses this problem in the following discussions.
4.2.1 Problem Definition

It is necessary to retransmit lost packets in an unreliable wireless medium in an
attempt to maximize the data transmission throughput. We illustrate this point by using a
simple numerical analysis. Assuming that the packet loss rate of a wireless channel is r,
the packet transmission success rate af1er n-hop forwarding will be (l-r)“. Therefore, it
can be measured that more than 40% of the packets will be lost after 6-hop forwarding
when channel lost rate r = 0.1. This can severely degrade data transmission throughput
since many packets are lost during the forwarding phase. One of the most basic
approaches to retransmit lost packets is the time-out mechanism. In this approach, the
sender will wait for an acknowledgment from the receiver after it transmits a packet, and
will retransmit the packet if the acknowledgment is not received within a specific time
period. This mechanism is simple and easy to implement. However, it may intensify
channel collision and therefore reduce throughput in the following ways. First, the
acknowledgment packets will compete with data packets for the communication channels
and these acknowledgment packets are usually up to 15 bytes long. Therefore, the extra
overhead of these acknowledgment packets cannot be ignored. Second, the
acknowledgment packets may be lost due to unreliable wireless channels, which cause

unnecessary retransmission. These duplicate packets, again, compete with other data

43

packets for communication channels. Third, data packets may be dropped by the
overflowed buffer on the receiver’s side and the sender will not be aware of this situation
and will retransmit packets unnecessarily. This will further cause severe channel

collisions if all senders keep retransmitting lost packets.

To retransmit lost packets without intensifying channel collisions, we defer the
retransmission decision to the receiver. The receiver will request the sender to retransmit

packets only when necessary.
4.2.2 Basic Idea

The receiver-centric protocol uses a sequence-based counting mechanism to detect
and retransmit lost packets. To detect lost packets between a sender and a receiver, the
sequence-based mechanism labels all packets that are sent from the sender with
continuous sequences, and lost packets can be detected by the receiver if it receives
discontinued—sequence packets. Therefore, the receiver can request the sender to
retransmit the lost packets using the discontinued sequence. Unlike the time-out
approach, channel collision can be reduced significantly because i) acknowledgments are
not used; ii) duplicate packets incurred by lost acknowledgment will not happen; iii) the

receiver will not request for retransmission packets if its buffer is overflowed.

The sequence-based mechanism relies on strictly in-order sequence to detect lost
packets, which may interrupt packet forwarding. If packet forwarding can be interrupted
by lost packet retransmission, the situation will become worse if some packets cannot be
recovered due to buffer overflow. These lost packets will always be detected by the
following intermediate forwarding nodes, and these nodes will request the retransmission

for the unrecoverable packets. The interruption occurs because the sequence-based

44

0
0
O

Ill

01

III/Ii

,
\2»
\
i

/.

\5-

 

 

 

 

Figure 28: In Receiver-centric protocol, node C continues to forward packet 4, 5,
and 6 even when packet 3 is lost.

mechanism uses strict continuous sequences that are maintained globally between the
source and the sink. To solve this problem, we use a localized numbering mechanism to
re-label each packet that needs to be forwarded. In this mechanism, when a node receives
a packet, it will re—label the packet with a continuously increased sequence maintained in
a local variable. As illustrated in Figure 28, each node maintains a local sequence
numbering that is increased with received packets. When node C detects lost packet 3
based on discontinued sequence, node C can still continue to forward packets 4, 5, and 6
to node D since all packets are re-labeled by node C with new sequences. Therefore,

packet interruption in one hop will not affect the continuous packet forwarding.
4.2.3 Request Lost Packets with Overhearing
To ensure continuous packet forwarding, the receiver-centric protocol does not use

a dedicated message to request lost packets. Instead, the lost sequence is piggybacked to

45

the data packets and the sender can be notified through overbearing. This mechanism
uses the broadcast nature of wireless channels where packets forwarded by an
intermediate node can always be overheard by its predecessor. By using this overhearing,

all the bandwidth can be allocated to data packets when dedicated messages are avoided.

In the receiver-centric protocol, each forwarding node maintains a buffer that
operates as a regular queue, i.e. a received packet is stored at the tail of the queue
whereas a packet is transmitted at the head of the queue. Moreover, the queue is divided
into three regions: sending region, receiving region, and recovery region. As shown in
Figure 29, where the sending region contains all packets that wait to be sent, the recovery
region contains all packets that have been sent, and the receiving region contains empty
buffers that are destined for the new packets. Here, the sending region sends out packets
at the head and receives packets at the tail. However, when a packet is transmitted, it will
be moved temporarily from the sending region to the recovery region, which can be used
to recover lost packets. The recovery of a lost packet is detailed in the following. We use
an extra pointer, vHead, which pointed to the buffer containing the lost packets. When
the lost packet is retransmitted, the head will continue to be used for packet forwarding.
Here, vHead is used to look up the lost packet in the recovery region without having to
screen through the entire region. This is achieved by renumbering a packet based on the
index of the buffer containing the lost packet. Since the local sequence variable will
increase simultaneously with the queue movement, the sequence number will be
increased by 1 when a new packet is buffered into the queue, and the sequence number s

assigned to the new packet is corresponded to the index i of the buffer containing that

46

I Sending region

Sent region

1:] Receiving region

 

Figure 29: Receiver-centric protocol divides packet buffers into three regions:
sending region, recovery region, receiving region.

packet. Therefore, we have i = s mode N, where N is the buffer size. As a result, the

index of a lost packet can be computed easily from its sequence number in O(l) time.
4.3 Performance Evaluation

We implement the receiver-centric protocol in TinyOS and evaluate the
performance in both Mica2 and Tmote sensors. The key features of both Mica2 and
Tmote are listed in Table B. We evaluate the performance of the receiver-centric protocol
by comparing with the time-out retransmission enabled with acknowledgments (ACK)
and the best—effort mechanism without acknowledgments (NACK). The following

metrics are used in our evaluation.

Event throughput: the total number of unique packets received at the sink per

second.

47

Packet injection interval: the time period between two consecutive packet

transmissions (the sending speed of a sender).

Buffer size: the length of transmission queue, which is the maximum number of

packets that a forwarding node can store.
Data length: the number of bytes in a packet that is used to store collected data.
4.3.1 Experimental Setup and Configuration

Our experimental system consists of two parts, the management part and the data

transmission part. In the management part, the control message is broadcast from the sink

to the entire network, which initializes the network with desired configuration parameters
including the radio transmission power, the buffer size, and the packet data size. The sink
also uses the control messages to trigger sources to start sending packets. The format of
the control message is shown in Figure 30, which contains several fields including inject
rate, transmission power, ACK field, and packet size. By setting those fields with proper
values, sources can be initiated with different parameters for each testing. It is possible
that control messages may be lost during the broadcast, which results that i) some sources
may not be triggered; ii) intermediate nodes may not be initiated with proper transmission
power and buffer size. We use two strategies to solve this problem. First, all packets
received by the sink are forwarded to the laptop through the serial cable. The packets
contain the source ID that generates the packets. By checking all received source IDs, the
inactive sources that do not send packets can be identified and re—triggered. Since all the
configuration parameters, such as the transmission power and buffer size, are included in
the control messages, sources can be initialized with correct parameters as long as they

can be triggered by the control messages. Second, sources can pass the configuration

48

Table B: Key Features of Mica2 and Tmote

 

Key Features MicaZ Tmote

 

 

 

Interface COM (Serial) USB

 

Multi-Channel

 

 

 

 

916 MHz 2.4 GHz
Radio Frequency
Maximum Power 5 dBm 40 dBm
Encryption No Yes
Outdoor Range 50011 42011
Cost $200 per mote $130 per mote

 

 

 

 

 

parameters to intermediate nodes through data packets. When sources generating data
packets, they will initialize packets with the transmission power and buffer size.
Therefore, intermediate nodes can reset the configuration parameters with the same

values as long as they receive packets from sources.

49

typedef struct SF_CMD {
uint8_t src;
uint8_t CMD;
bool bACK;
uint8_t power;
uint16_t inj ectRate;
uint8_t num_children;
} SF_CMD;

Figure 30: Control message format.

We use three network topologies in our evaluation: the linear topology, the star
topology, and the tree topology. Since we only evaluate the communication performance
of a sensor network at the link layer, the routing function at the network layer is not
included in our program. Instead, we use a fixed routing path in our test. This can be
achieved by statically assigning a routing table when sensors are initially reprogrammed.
For the three topologies used in our evaluation, we only need to define the child/parent
relationship in the routing table, such that an intermediate node can receive packets from

its children and forward packets to its parent.

Assisted by the management part, we can control the testbed and evaluate different
approaches in the data transmission part. After we reprogrammed sensors with one
approach, we conducted multiple tests with different settings of packet inject rate, buffer
size and packets size. This is achieved by the control message broadcast from the sink.

We detail our performance evaluation under various settings in the discussion below.
4.3.2 Channel Access Scheduling under Different Packet Injection Intervals

We first evaluate the event throughput of channel access scheduling under different

intervals. In our test, two sources simultaneously send packets to a parent, which continue

50

to forward the received packets to the sink. All packets received by the sink are further
forwarded to the attached laptop, which can filter duplicated packets based on their
unique packet IDs and compute event throughput of data transmission. Three approaches,
including the receiver-centric with channel access scheduling, the ACK with CSMA, and
the NACK with CSMA, are evaluated with both Mica2 and Tmote sensors. We evaluate
how the packet inject rate affects the event throughput by varying the packet inject
intervals. Figure 31 shows the event throughput of the three approaches in Mica2 sensors,
and Figure 32 shows the event throughput of the three approaches in Tmote sensors. The
tests on both platforms show that the receiver-centric protocol helps to improve the event
throughput of CSMA when the packet inject interval is small. We also observe that the
event throughput of NACK outperforms the ACK when the packet inject interval is

small.

When the packet inject interval is increased to a large value (greater than 100
milliseconds), our test on Mica2 sensors shows that all the three approaches have close
event throughput performance. Based on this test, we conclude that the ACK can.
intensify channel collision and degrade event throughput at high packet sending rate. We
also conclude that the channel collision of both ACK and NACK approaches can be
reduced by the channel access scheduling of the receiver-centric approach, and therefore

high event throughput can be achieved under high packet sending rates.
4.3.3 Channel Access Scheduling under Different Number of Sources

We further evaluate the scheduling mechanism under different number of sources.
Figure 33 (in Mica2) and Figure 34 (in Tmote) show that the event throughput is reduced

with the increased number of sources. This is because i) the bandwidth is divided and less

51

 

 
 
   

 

 

 

 

4’ -ih-ACK
'5' -+- NACK
g- 3 ~ + Receiver—Centric
on
3
£2 2-
.C
+4

d
v

 

 

 

0 100 200 300
interval

Figure 31: Scheduling in Mica2 under different packet injection intervals.

7, ..,,.'7 , .7 .7_

22 re—wwflfi—--e«

 

 
   
     
  

+ ACK
+ NACK
-{- Receiver—Centric

 

 

 

fluoughput

 
 

.fil_—. ¥ .fim_l¥ ‘__ 7k

8 1o 12 14 16 18
interval

 

Figure 32: Scheduling in Tmote under different packet injection intervals.

52

 

 

-.-ACK
+ NACK
+ Receiver—Centric

  
   
 
 

 

 

 

 

throughput

—J
Y

 

 

2 3 4 5
number of sources

Figure 33: Scheduling in Mica2 under different number of sources.

13 ME Tu4»- MTM- -A;

_.|
0‘

b

 

 

throughput
:3

 

 

 

 

 

10 r
+ ACK
8 * + NACK
+ Receiver—Centric _
62 3 4 5 6 7
number of sources

Figure 34: Scheduling in Tmote under different number of sources.

53

bandwidth can be reserved by an individual source and ii) increasing the number of
sources intensifies the channel collisions, which results in more packets being lost during
the transmission. Both figures also show that the receiver-centric approach outperforms
the other two approaches at different number sources, because the scheduling mechanism

reduces the channel collisions.

4.3.4 Channel Access Scheduling under Different Buffer Sizes

3 r— —— 7. . . ,-____._,, ,,
+ AC /
-+-NACK

" + Receiver-Centric

 

 

N
U1

 

 

 

throughput

 

 

 

 

o 20 40 ‘60 so
queue size

Figure 35: Scheduling in Mica2 under different buffer sizes.

We evaluate how the buffer size affects channel access scheduling on Mica2
sensors by varying the buffer size from 16 to 64. Figure 35 shows that the event
throughput of all three approaches is increased when the buffer size is increased. The
three approaches have close event throughput when the buffer size is small. However, the

receiver-centric approach outperforms the other two approaches when the buffer becomes

54

larger. All the three approaches have close and worst performance with small buffer size,
because a large number packets are dropped due to buffer overflow. When sensors have
sufficient buffer size, they can achieve higher event throughput. Particularly, this event
throughput can be further improved by channel access scheduling of the receiver-centric

approach.
4.3.5 Lost Packet Retransmission under Different Packet Injection Intervals

To evaluate the lost packet retransmission of the receiver-centric protocol, we use
only one source in both two-hop and three-hop topologies where a sender continuously
sends 200 packets to the intermediate nodes and later forwards to the receiver. In
addition, we compare our lost packet retransmission of our protocol against the lazy loss
detection of efficiency-centric communication (ECC) protocol [29]. The lazy loss
detection is somewhat similar to our recovery mechanism. It also uses the overbearing
technique and sequence-based counting to detect lost packets. It then chooses either of
two possible alternatives to notify the sender about the loss of packets: overbearing or
retransmission request packet (RRP). For easier implementation, we use the second
method, RRP. These implicit acknowledgments are necessary because they are used to
remove sent packets from the buffer in order to free up space for newly received packets.
For example, in Figure 36, which is taken from [29], node B detects the loss of packet 3
when it receives packet 4. Node B then recovers lost packet 3 by sending a RRP to node
A. Note that multiple RRPs may be necessary to inform node A because link
imperfection usually occurs. In addition, lazy loss detection needs to temporarily buffer

any subsequent packets after detection of a lost packet to maintain the correct sequence of

55

  
  
  
 
    
   

  
   

mamas-{ma

."i' '— — - -- “- , Packet1
Packet 1 overheating —————— «1. Packet ‘1
if“
—————— Packet 2 Bi
—————— 11., Packet 2
—— -— x— — —— Packet 3 lost :3
Ask f ______ Packet 4 arrives, node E
. . or B detects lost packet E
retransrmsswn of _,,_.-;:--_~;-.—.,,._ 1,?

packet 3

Packet 5 ; Packet 3
—————— f Packet 4
—————— 1' 5"‘3 Packet 5
Packet 6 £

—————— 1.. ,2 Packet 6

---' -a--
"- -h‘u
--

\
*—_—_“

Packet 6 overheating

"CMW

tiff
Node A Node 8 Node C

Figure 36: The basic principle of lazy loss detection.

Table C: Summary of key differences between RC and ECC

 

 

 

 

Key Differences Lost Packet Recovery (RC) Lazy Loss Detection (ECC)
Sequence
Local Global
Numbering
Re-number subsequent
Lost Packet Buffer subsequent packets
packets and forward to the
Detection until lost packet recovered
next hop

 

 

 

56

 

5.5

 

5
4.5
g 4 + KK
)3 -—l—- NACK
3.5 + RC
«0‘ gr,
3
2.5 '
20 30 40 50 60
irtervd

Figure 37: Lost packet retransmission in Mica2 under different packet injection
intervals in three-hop topology.

+PCK
+NPCK
+RC
":‘*EZC

 

Figure 38: Lost packet retransmission in Mica2 under different packet injection
intervals in two-hop topology.

57

packets. Table C summarizes the differences between our lost packet retransmission and

lazy loss detection of ECC.

In this experiment, the event throughput is only determined by the lost packet
retransmission since no channel access scheduling is necessary for only one source.
Figure 37 shows that the ACK approach performs more poorly than any other approaches
regardless of packet injection interval. This happens because the ACK approach
intensifies channel contention, especially when packets are sent at higher rate, which
lowers the event throughput. On the other hand, the NACK approach has a higher overall
throughput than the ECC approach. Though both mechanisms will send a request
retransmission packet back to the sender when a packet is lost, there is a higher
probability that lost packets cannot be recovered with the ECC approach because buffer
overflows occurs more frequently since it buffers all subsequent packets. A notable one is
our receiver-centric approach which outperforms all other approaches because our
approach can recover lost packets with very small overhead. However, Figure 38 shows
that ECC closely approaches our protocol and performs better than NACK because
network topology becomes much simpler when we repeat the same experiment using a
two-hop topology.

4.3.6 Lost Packet Retransmission under Different Buffer Sizes

We evaluate how buffer sizes affect event throughput of the lost packet
retransmission by varying the buffer size of all forwarding nodes from 4 to 64. The result
in Figure 39 shows that receiver-centric performs worse when the buffer size is small,

and outperforms other three approaches when the buffer size is larger than 4. The better

performance with larger buffer size happened because more buffer space can be allocated

58

N
U!

 

6.5
i
.5 5.5 —e—ACK
g +NACK
5 4.5 +RC

«(LO-ECC
3.5
2.5 >
4 16 32 64
queue size

Figure 39: Lost packet retransmission in Mica2 under different buffer sizes in three-

 

hop topology.
10
9
8
g» 7 +ACK
g + NPCK
6 +RC
"*0“ ace
5
4 .
4 16 32 64
queue dze

Figure 40: Lost packet retransmission in Mica2 under different buffer sizes in two-
hop topology.

59

to the recovery region, which increases the possibility of recovering the lost packets.
However, Figure 40 shows that receiver-centric has very little improvement in
performance when we repeat the same experiment using a two-hop topology where only

once intermediate node exists.
4.3.7 Lost Packet Retransmission under Different Packet Sizes

The event throughput can be affected by the packet size because larger packet sizes
consume more bandwidth and are more easily lost during the transmission. We evaluate
how packet size affects the event throughput by varying the length of the data field from
10 to 40 bytes. The default maximum data length is 29 bytes in TinyOS 1.13, we modify
the system configuration to increase the maximum data length to 40 bytes. The
comparison results of Figure 41 show that the event throughput of all the four approaches
is reduced when the packet size becomes larger. However, the ACK approach has the
lowest event throughput regardless of the size of data length. This happened because
channel contentions are intensified by the ACK approach. The NACK approach performs
much better than ECC at larger packet size. This is because when packet size becomes
larger, more packets will be lost and cannot be recovered in the ECC approach. However,
some of the lost packets can be recovered by the NACK approach, and therefore achieve
higher event throughput. Among all the four approaches, the receiver-centric has the
highest event throughput at different data lengths because packets are recovered with
small overhead. We then repeat the experiment using a two-hop topology. Figure 42
shows that ECC has higher throughput than NACK as opposed to Figure 41. This is
because channel contention is reduced in a much simpler topology, and therefore, more

packets can be recovered.

60

5.5

 

5
‘9; 4.5
E, -e—ACK
g 3 +NACK
5 4 1
‘ +RC
«mo—ECC
3.5 '
3 . .
7 14 2']
packet size

Figure 41: Lost packet retransmission in Mica2 under different packet sizes in
three-hop topology.

 

7
6.5
6
E 5.5 +1”
2 + NPCK
5 + RC
-—---— sec
4.5
4 » ~ 1
7 14 21
pairet in

Figure 42: Lost packet retransmission in Mica2 under different packet sizes in two-
hop topology.

61

4.4 Summary

We aim to improve data transmission throughput in sensor networks through two
approaches. First, we enforce channel access scheduling to the CSMA, which improves
channel throughput by reducing channel collisions. Our solution is flexible and scalable,
and can be easily deployed in sensor networks. Second, we realize the sequence-based
retransmission in the hop-by-hop recovery of sensor networks, which improves
throughput by reserving all bandwidth resources for data transmission. We have
implemented the channel access scheduling and sequence-based mechanism in TinyOS
1.13 and evaluated their performance on both Mica2 sensors and Tmote sensors. Our
evaluation shows that the receiver-centric protocol can significantly improve

transmission throughput of wireless sensor networks.

62

5. Conclusion and Future Work

In this section, we present the conclusion of our research and discuss possible

future work to further improve our receiver-centric protocol.

5.1 Conclusion

To improve data transmission throughput, we first provide an overview of radio
signal and their signal strength behavior in complex environments. Our study
demonstrates that the lossy nature of wireless communication and rapidly changing
environment have severe effects on radio signal strength, which is widely used for data
packet transmissions. Secondly, we propose a new MAC overlay protocol that is

designed to improve CSMA that further maximizes data transmission throughput.
The main contributions of this research are:

0 To study how radio signals react in different environment settings where

obstructions and reflections occurred randomly.

0 To improve data transmission throughput, we build an efficient MAC
overlay protocol in which we implement a channel access scheduling

based on round-robin fashion to schedule nodes for packet transmissions

63

at specific time slots and a lost packet recovery mechanism based on

number sequencing to retransmit lost packets.

0 To analyze the feasibility of our approach by varying the input parameters
to the control message that is used to configure and initialize the sensor

nodes.

5.2 Future Work

In future, there are several possibilities that we can consider to further improve our
performance in maximizing data transmission throughput. For channel access scheduling,
we can consider not only round robin, but other types of scheduling methods such as
FCFS (First Come First Serve) and priority scheduling. FCFS can be used as a baseline
comparison metric for evaluation against the other two scheduling mechanisms. To
implement priority scheduling, we can design in such a way that intermediate nodes that
have more data packets to be forwarded to their parent node will be assigned a higher
priority. The main idea behind this technique is that more buffer overflow cases can
potentially be avoided for highly active nodes since more slots will be available for newly
arriving packets. To utilize priority for scheduling, we need to introduce a new variable
for each node that indicates its priority level within the parent-child structure. Priority
scheduling can eventually cause more overhead because a check needs to be done at each
scheduling point to determine which node will get to send a packet next. This is in
contrast to our round robin that the next node with ID i +1 , will get scheduled next. Note
that the experiment configurations that we have been using to evaluate our protocol need
to be changed. To evaluate the performance of priority scheduling, we have to initialize

each source to send out a different number of packets for initial priority assignments.

64

Besides exploring different scheduling methods, we can also extend our receiver-
centric protocol to work in a more randomized network topology. For example, each
parent node can have a different number of children. Currently, our protocol is
implemented based on the assumption that all parent have the same number of children at
each level of the tree, which is certainly not the ideal case in real deployment. However,
this extension requires a much more complicated node ID assignment during the

initialization phase and may cause more overhead.

One of the limitations in our lost packet retransmission mechanism is that it only
works in a linear topology where some intermediates nodes are placed between a source
and a destination. The idea of using sequence-based counting and overbearing for
detecting and retransmitting lost packets is fairly simple in a linear topology. However,
things get complicated when we consider applying this mechanism in a random topology.
This is partly due to the need for a parent to identify which child node requires resending
the lost packets. When a lost packet is detected, we need to only notify the sender of this
lost packet, and request for a recovery. This may incur some extra overhead during

identification process.

To further assure our evaluation results, we can repeat the experiments by applying
the same application to another type of sensing device (eg. mica2dot). Several TinyOS
configurations and code modifications are required in order to accomplish the data

collections.

If all the above improvements can be implemented, our receiver-centric protocol
will become a practical solution for real deployment while maintaining high data

transmission throughput.

65

6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

BIBLIOGRAPHY

Kamin Whitehouse, Chris Karlof, David Culler, “Getting Ad-hoc Signal Strength
Localization to Wor ”, UC Berkeley Technical Report UCB//CSD-04-1348, May 26,
2004.

Signal Clarity, “Solectek Wireless Networking Solutions Technical Papers”, August
3, 2001. bttp://www.solectek.com/techlib/techpapers/tecbtalk/tt-clarity.html.

Jaein Jeong and Sukun Kim, “C8268 Computer Networks Localization using Dot3
wireless sensors”, Class Project, UC Berkeley, 2003.

Giuseppe Anastasi, Eleonora Borgia, Marco Conti, Enrico Gregori, Andrea
Passarella, “Understanding the Real Behavior of Mote and 802.11 Ad boc Networks:
an Experimental Approach”, National Research Council (CNR), Italy, 2005.

Cameron Dean Whitehouse, “The Design of Calamari: an Ad-hoc Localization
System for Sensor Networks”, Master Thesis, UC Berkeley Research Project, 2002.

Dimitrios Lyrnberopoulos, Quentin Lindsey and Andreas Savvides, “An Empirical
Analysis of Radio Signal Strength Variability in IEEE 802.154 Networks using
Monopole Antennas” in EWSN, 2006.

Matthew Taylor, Yi-Feng Ni, and Tuan T Troung, “Radio Propagation Simulation
Tool for Wireless Communications”, Norwich University, 2005.

“ChipCon CClOOO Data Sheet”, http://www.cbipcon.com/_les/CC1000 Data Sheet 2
l.pdf. '

Nelson Lee, Philip Levis, Jason Hill, “Mica High Speed Radio Stack”, Sept 11, 2002.
http://www.tinyos.net/tinyos-1 .x/doc/stack.pdf.

66

[10] Tereus Scott, “Mica Mote Antenna Radiation Analysis”, University of Victoria, May
28, 2004. http://www.cs.uvic.ca/%7Ewkui/research/motereport-p.pdf.

[1 1] Don Button, “Effect of Obstructions on RF Signal Propagation”, EMS Wireless, Feb
24, 1999. http://www.emswireless.com/english/Tecb_Articles/tecb_art03.asp.

[12] Vaidyanatban Ramadurai, Mihail L. Sichitiu, “Simulation-based Analysis of a
Localization Algorithm for Wireless Ad-Hoc Sensor Networks”, North Carolina State
University Technical Report.
bttp://www4.ncsu.edu/~mlsichit/Researcb/Publications/opnet.pdf.

[13] Song Li, Gang Zhao and Lin Liao, “User Location Service over an 802.11 Ad-Hoc
Networ ”, University of Washington Technical Report.
http://www.cs.washington.edu/homes/liaolin/Courses/networksOZ.pdf.

[14]Jonathan Bachracb and Christopher Taylor, “Localization in Sensor Networks”,
Massachusetts Institute of Technology, Cambridge, MA.
bttp://people.csail.mit.edu/jrb/Projects/poschappdf

[15] Mihail L. Sichitiu and Vaidyanatban Ramadurai, " Localization of Wireless Sensor
Networks with a Mobile Beacon”, North Carolina State University Technical Report,
July 2003.
bttp://www4.ncsu.edu/~mlsichit/Research/Publications/oneMobileBeaconTR.pdf.

[16] K. Arisha, M. Youssef, and M. Younis, “Energy-aware tdma based mac for sensor
networks,” in IEEE Workshop on Integrated Management of Power Aware
Communications Computing and Networking, 2002.

[17]V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves, “Energyefficient collision-
free medium access control for wireless sensor networks,” in SenSys, (New York,
NY, USA), pp. 181—192, ACM Press, 2003.

[18] W. Ye, J. Heidemann, and D. Estrin, “An energy-efficient mac protocol for wireless
sensor networks,” in INFOCOM, 2002.

[19]T. van Dam and K. Langendoen, “An adaptive energy-efficient mac protocol for
wireless sensor networks,” in SenSys, 2003.

[20] J. Polastre, J. Hill, and D. Culler, “Versatile low power media access for wireless
sensor networks,” in SenSys, 2004.

67

[21]I. Rhee, A. Warrier, M. Aia, and J. Min, “Z-MAC: a hybrid mac for wireless sensor
networks,” in SenSys, 2005.

[22]G.-S. Ahn, S. G. Hong, E. Miluzzo, A. T. Campbell, and F. Cuomo, “Funneling-mac:
a localized, sink-oriented mac for boosting fidelity in sensor networks,” in SenSys,
(New York, NY, USA), pp. 293—306, ACM Press, 2006.

[23]J. Li and G. Y. Lazarou, “A bit-map-assisted energy-efficient mac scheme for
wireless sensor networks,” in IPSN, (New York, NY, USA), pp. 55—60, ACM Press,
2004.

[24]B. Hull, K. Jamieson, and H. Balakrisbnan, “Mitigating congestion in wireless sensor
networks,” in SenSys, 2004.

[25]C.-Y. Wan, S. B. Eisenman, and A. T. Campbell, “CODA: congestion detection and
avoidance in sensor networks,” in SenSys, 2003.

[26]C.-Y. Wan, S. B. Eisenman, A. T. Campbell, and J. Crowcrofl, “Siphon: overload

traffic management using multi-radio virtual sinks in sensor networks,” in SenSys,
2005.

[27] C. T. Be and R. Bajcsy, “Congestion control and fairness for many-toone routing in
sensor networks,” in SenSys, 2004.

[28]C. Wang, K. Sohraby, V. Lawrence, B. Li, and Y. Hu, “Priority-based congestion
control in wireless sensor networks,” in Sensor Networks, Ubiquitous, and
Trustworthy Computing, 2006.

[29] Q. Cao, T. He, L. Fang, T. F. Abdelzaher, J. A. Stankovic, and S. Son, “Efficiency
centric communication model for wireless sensor networks,” in INF OCOM, 2006.

[30] H. Zhang, A. Arora, Y. Choi, and M. Gouda, “Reliable bursty convergecast in
wireless sensor network,” in ACM MobiHoc, 2005.

[31] S. S. Kulkarni, M. Arumugam, “SS-TDMA: A self-stabilizing MAC for sensor
networks,” in Sensor Network Operations, S. Pboba (editor), T. F. La Porta (editor),
C. Griffin (editor), ISBN: 0-471-71976-5, Wiley-IEEE Press, 2006.

[32] S. S. Kulkarni, M. Arumugam, “Infuse: A TDMA based data dissemination protocol

for sensor networks,” in International Journal on Distributed Sensor Networks
(IJDSN), 2(1):55-78, 2006.

68

 

LIBRARIES

311V

{‘1 rE iJNWER

'ILHIGAH

11

1

W1

3 1293 02956 4832