“fig...
733”“
‘ «A

.t

‘
3mm». .
flaw. Emma.
3%
1..

«Ma: .

tfldi.is I. it‘i‘

:17 .m 4.3!. to .
4E..5..«.L.".w..m.«£
«a.

IT . r 5»-
a...
yrnvxmil. If. ‘

In» A

 

xx

3551...;2.

3 at...
.0! W.

.5
535;.»

J... .u
‘0 ‘¥:‘!'. II.

saluti; . z...

‘ .L- ‘I.

$1.?J. :3
iv .65!

 

 

1w.— uminrov 34?...3.“

 

 

11113315 ‘ LIBRARY
Michigan State
University

.‘3 U

4:)

 

 

This is to certify that the
dissertation entitled

SELF ORGANIZATION IN MEDIUM ACCESS
CONTROL
FOR WIRELESS AD HOC AND SENSOR NETWORKS

presented by

FAN YU

has been accepted towards fulfillment
of the requirements for the

Ph.D. degree In Electrical Engineering

 

 

933M (km...

 

Major Professor’ 5 Signature
I o/ 2 9/o 3

Date

 

MSU is an Affirmative Action/Equal Opportunity Employer

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

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5/08 K:IProj/Acc&Pres/ClRC/DateDue.indd

 

SELF ORGANIZATION IN MEDIUM ACCESS CONTROL
FOR WIRELESS AD HOC AND SENSOR NETWORKS

By

Fan Yu

A DISSERTATION

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

DOCTOR OF PHILOSOPHY
Electrical Engineering

2008

ABSTRACT

SELF ORGANIZATION IN MEDIUM ACCESS CONTROL
FOR WIRELESS AD HOC AND SENSOR NETWORKS

By

Fan Yu

The objective of this thesis is to investigate the role of protocol self organization
at the Medium Access Control Layer in wireless ad hoc and sensor networks.
Protocol self organization is defined as autonomous and self-calibrating
communication state machines that can adjust their operating parameters and state
machine logic as a reactive response to external operating environment such as
network load, node crowding, topology changes due to mobility, energy depletion,
infrastructure failure and communication errors. While the traditional wired
networks continue to enjoy relatively stable operating environments, the emerging
wireless and sensor networks suffer from the mentioned operating instabilities due to
their ad hoc deployments, specialized applications and various resource constraints.
The goal in this work is to utilize protocol reorganization as defined above in order
to mitigate the effects of the mentioned instabilities. We propose a MAC self
organization framework for both intra-MAC and inter-MAC as outlined below.

For infra-MAC self organization, we develop an In-band Self-Organized Mfg;
(ISOMAC), for wireless sensor networks with arbitrary mesh topologies. The
specific problems the mechanism attempts to solve are arbitrary ad hoc deployment,

energy limitation, and network dynamics. The novelty of the proposed framework

lies in its in-band control mechanism. Both analytical and simulation models show
that in addition to the reasonably fast reorganization convergence, the energy penalty
of the in-band information is quite negligible.

A cross-layer approach, Minimized Slot Misordered Routing (MSMR) with
ISOMAC style MAC, is also developed. The self organizing TDMA MAC schedule
is used as input to the routing protocol to generate routing paths.

As for validation and extension of the ISOMAC framework, an application
adaptation in vehicular wireless networks is investigated. An adapted ISOMAC,
Vehicular Self-Organizing MAC (VeSOMAC), which is capable of inter-vehicle
message delivery with short and deterministic delay bounds has been developed.
Through n32 simulation experiments, the efficiency of self organizing abilities of
VeSOMAC is demonstrated in the presence of fast topology variation in vehicular
networks.

Finally, we propose an inter-MAC self organization framework in the form of
dynamic MAC protocol switching. The problem we address with this framework is
to make a network adaptable with dynamic network loading conditions while
providing acceptable user perceived performance. The key concept is that a network
node can autonomously switch across different MAC layer protocols as a response to
network traffic heterogeneity. Therefore, the reorganization here is accomplished
across multiple protocols. Both theoretical and experimental analyses support that
the dynamic MAC protocol switching logic enhances the network-wide throughput

in the presence of traffic heterogeneity.

Copyright by
Fanifii

2008

To My Families
For All Their

Love and Support

Acknowledgements

I would like to thank my advisor Dr. Subir Biswas for supporting me through my
Ph.D. study. His patient guidance allowed me to flourish during my research. I
would also like to thank my committee Dr. Michael Shanblatt, Dr. Jian Ren and Dr.
Philip McKinley for their precious suggestions and advices.

Thanks must be given to my lab mates Tao Wu, Jayanthi Rao, Anthony Plummer,
and Muhannad Quwaider for all of the helps, brainstorming and discussions. Last but
not least, I would like give thanks to Changqing Chen, Juanita Dion and Lan Yang

along with the rest of my friends for supporting me through this process.

vi

TABLE OF CONTENTS

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

LIST OF TABLES X
- LIST OF FIGURES XI
CHAPTER 1 1
BACKGROUND 1
1.1. WIRELESS AD HOC NETWORKS I
1.2. WIRELESS SENSOR NETWORKS l
1.3. APPLICATIONS OF WIRELESS SENSOR NETWORKS 6
1.3.1 Military applications 6
1.3.2 Environmental Data Collection Applications 7
1.3.3 Health applications 8
1.3.4 Other Applications 9
CHAPTER 2 10
SELF ORGANIZING MEDIUM ACCESS CONTROL PROTOCOLS .............. 10
2.1 ROLE OF MEDIUM ACCESS CONTROL IN WIRELESS NETWORKS 10
2.2 CONCEPT OF MAC SELF ORGANIZATION 10
2.3 NEEDS FOR MAC SELF ORGANIZATION 11
2.4 RESEARCH ISSUES ADDRESSED IN THIS THESIS ...... 13
2.4.1 Design of Self Organizing MAC 13
2.4.2 Cross-layer Design 14
2.4.3 Application of ISOMAC Protocol for Vehicular Networks 16
2.4.4 MAC Protocol Switching 17
2.5 SUMMARY . I 9
CHAPTER 3 20
TOWARDS IN-BAND SELF ORGANIZATION IN ENERGY-EFFICIENT
MAC PROTOCOLS FOR SENSOR NETWORKS 20
3.1 INTRODUCTION - 20
3.1.1 Motivation ........ 20
3.1.2 Related Work 20
3.1.3 Proposed ISOMAC Protocol ...... 24
3.2 NETWORK, TRAFFIC AND OPERATION MODEL 25
3.3 ISOMAC PROTOCOL DETAILS ............. 26
3.3.1 Frame and Slot Structure ................................. 26
3.3.2 Asynchronous ISOMAC (ISOMAC-A) ..... 28
3.3.3 Synchronous ISOMAC (ISOMAC-S) ........ 42

 

3.4 MODEL FOR FRAME SIZE DIMENSIONING AND ENERGY CONSUMPTION 43

 

vii

3.5 MULTl-SLOT ISOMAC FOR VARIABLE TRAFFIC .....
3.6 PERFORMANCE .

47
49

 

49

 

3.6.1 Experimental Parameters
3.6.2 Protocol Convergence

50

 

3.6.3 Sensor Deployment

 

 

3.6.4 Spatial Channel Reuse .........
3.6.5 Channel Errors

55
57

 

3.6.6 Energy Consumption

 

3.6.7 Effects of Clock Drift

62

 

3.6.8 Multi-Slot ISOMAC

 

3.7 SUMMARY AND CONCLUSIONS

65

 

CHAPTER4

 

CROSS-LAYER ROUTING PROTOCOLS IN THE PRESENCE OF MAC

SELF ORGANIZATION

 

4.1 INTRODUCTION

67

67
67

 

4.1.1 Current MAC Self Organization Strategies in WSN

67

 

4.1.2 End-to-End Delay due to TDMA Slot Misordering

67

 

4.1.3 Related Work

70

 

4.1.4 Proposed Solution

71

 

4.2 MINIMIZED SLOT MISORDERD ROUTING (MSMR)

72

 

4.2.1 TDMA Allocation Model

72

 

4.2.2 Link Cost Formulation .....

73

 

74

 

4.2.3 Baseline MSMR Route Computation
4.2.4 Balanced MSMR to Mitigate Packet Queuing

75

 

4.3 PERFORMANCE CHARACTERIZATION

78

 

4.3.1 Network and Data Model

78

 

4.3.2 Effects of MSMR on Delay .....

79

 

4.3.3 Energy-delay 'II’adeo3....

81

 

82

 

4.3.4 E3ects of Congestion and Packet Queuing
4.3.5 Balanced MSMR for Mitigating Congestion

83

 

4.4 SUMMARY AND CONCLUSIONS

85

 

CHAPTER 5

 

APPLICATION OF ISOMAC FOR VEHICLE-TO-VEHICLE
COMMUNICATIONS FOR SAFETY AND DATA INTENSIVE
APPLICATION S

 

5.1 INTRODUCTION ..........................

 

87

 

5.1.1 Application of ISOMAC... ..............................................
5.1.2 Background and Motivation ..... .............
5.1.3 Related Work ..............................................................

 

 

 

viii

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.1.4 VeSOMAC: Vehicular Adaptation of ISOMAC 92
5.2 VESOMAC PROTOCOL ADAPTATION DETAILS 95
5.2.1 Adapted Frame and Slot Structures 95
5.2.2 Adaptation of ISOMAC Protocol Logic for the proposed VeSOMAC .................... 96
5.3 PERFORMANCE EVALUATION 106
5.3.1 VeSOMAC Protocol Convergence 107
5.3.2 Highway Scenario Performance 111
5.3.3 Urban Traffic Intersection Scenario 126
5.3.4 Inter-vehicle Data 'h'ansfer Applications Performance 139
5.4 SUMMARY AND CONCLUSIONS 150
CHAPTER 6 152
DYNAMIC MAC PROTOCOL SWITCHING FOR PERFORMANCE
ADAPTATION WITH TRAFFIC HETEROGENEITY 152
6.1 INTRODUCTION ..... 1 52
6.1 .1 Background 152
6.1.2 Related work ..... 153
6.1.3 Proposed Dynamic MAC Protocol Switching 155
6.2 PROTOCOLS SUPPORTING MAC SWITCHING 156
6.2.1 Generalized Concept 157
6.2.2 Specific Mechanisms for MAC Protocol Switching 158
6.2.3 Detailed Transmission Rules 162
6.3 MAC PROTOCOL SWITCHING LOGIC 166
6.3.1 Switching Criteria 166
6.3.2 Model for Switching Criteria 169
6.3.3 Mechanics of Protocol Switching 173
6.3.4 Response to Network Topology Variations 176
6.4 EXPERIMENTAL EVALUATION 177
6.4.1 Validation of Protocol Switching Decision Threshold .. 178
6.4.2 General Network Experiments 186
6.5 CONCLUSIONS AND ONGOING WORK ..... 193
CHAPTER 7 194
SUMMARY AND FUTURE WORK 194
7.] SUMMARY ....... 194
7.2 FUTURE WORK ............................................... 196
APPENDIX A 198
A MODEL FOR CONVERGENCE IN LINEAR NETWORKS 198
BIBLIOGRAPHY 202

 

ix

LIST OF TABLES

Table 3.1: Baseline system parameters in simulation ...................................... 49

Table 5.1: Baseline experimental parameters ............................................. 113

Table 5.2: Baseline experimental parameters for the UICW application

simulation ..................................................................................... 133
Table 5.3: Time constant of protocols ..................................................... 150
Table 6.1: Baseline parameters of experiment ............................................ 178

LIST OF FIGURES

Figure 1.1: Sensor Nodes Mote2, Mote2dot, Imote, TelosB, Cricket .................. 2
Figure 1.2: System architecture of clickable environment ............................... 8
Figure 1.3: Clickable environment sensor platform ....................................... 9

Figure 2.1: Pictorial summary of the investigated issues in this thesis proposal. . ..13

Figure 3.1 Slot allocation in ISOMAC .................................................... 27
Figure 3 .2: Concept of in-band header bitmap ........................................... 29
Figure 3.3: Slot selection feasibility ....................................................... 32
Figure 3.4: Iterative slot movement for convergence .................................... 35
Figure 3.5: State machine for ISOMAC ................................................... 40
Figure 3.6: Convergence characteristics for ISOMAC-A .............................. 50
Figure 3.7: Convergence in arbitrary mesh networks ................................... 53

Figure 3.8: Effects of sensor deployment pattern and spatial reuse in ISOMAC. . .55
Figure 3.9: Effects of channel error on protocol convergence ......................... 57
Figure 3.10: Stability and allocation recovery under varying packet error rates. . . .58
Figure 3.11: Energy performance of TDMA-W and ISOMAC ........................ 59

Figure 3.12: Effects of channel error on energy, clock drift on allocation stability..62

Figure 3.13: Effects of static and dynamic multi-slot allocation ...................... 64
Figure 4.1: Effects of TDMA on end-to-end delay ...................................... 68
Figure 4.2: Example MAC allocation and link cost formulation ...................... 73
Figure 4.3: MSMR operation with synchronized TDMA .............................. 74
Figure 4.4: pseudo-code of Balanced MSMR logic ..................................... 76

xi

Figure 4.5: Effects of MSMR routing on delay .......................................... 79

Figure 4.6: Effects of density and hop count on PHO ................................... 82
Figure 4.7 : Packet queuing at higher sensor event rates ................................ 83
Figure 4.8: Increased allowable event rate with load balancing ....................... 84
Figure 5.1: Location aware MAC allocation by synchronous VeSOMAC ............ 93

Figure 5.2: Slot structure and steady allocation in adapted asynchronous
VeSOMAC ..................................................................................... 95

Figure 5.3: Adaptation of ISOMAC feasible slot scenarios in example VeSOMAC..99

Figure 5.4: Iterative slot movements for allocation convergence ..................... 101

Figure 5.5: Adapted State machine for the VeSOMAC protocol with all
constraints .................................................................................... 104

Figure 5.6: Pseudo code for the adapted VeSOMAC with all constraints ............ 105
Figure 5.7: VeNTSim: ITS application and network evaluation/planning tool. . .. 106
Figure 5.8: VeSOMAC convergence dynamics after a topology change ............ 108
Figure 5.9: VeSOMAC convergence latency for platoon mergers .................... 109

Figure 5.10: VeSOMAC convergence latency for intra-platoon vehicle passing... 110

Figure 5.11: Efficiency of VeSOMAC for reducing vehicle crashes in CCA

application ................................................................................... 1 13
Figure 5.12: The effects of background non-safety traffic on avoiding vehicle
crashes ....................................................................................... 114
Figure 5.13: Latency and crash statistics for CCA with VeSOMAC ................. 116
Figure 5.14: Latency and crash statistics for CCA with 802.11 ..................... 117
Figure 5.15: Effects of channel error on cooperative collision avoidance .......... 118

xii

Figure 5.16: WCW message delivery latency across the entire platoon ............ 120

Figure 5.17: Distribution of cross-platoon delivery latency for 802.11 and

VeSOMAC .................................................................................... 121
Figure 5.18: Message drop at different platoon locations ............................. 122
Figure 5.19: Effects of the ordering constraint on delay for VeSOMAC ............123
Figure 5.20: Impacts of TDMA slot reorganization during a UICW process ...... 125
Figure 5.21: Cooperative Collision Avoidance in an urban intersection scenario..127
Figure 5.22: Dynamics of a cross-street chain collision without UICW ............ 129
Figure 5.23: Leveraging UICW for reducing intersection vehicle crashes ......... 130
Figure 5.24: Pseudo-code for the WCW generation and interpretation in UICW..131
Figure 5.25: Vehicle crash performance with 802.11 and VeSOMAC ............... 134
Figure 5.26: Latency and crash statistics for CCA with VeSOMAC... .........136
Figure 5.27: Latency and crash statistics for UICW with 802.11 .................... 137
Figure 5.28: Message drop at different platoon locations ............................. 138
Figure 5.29: Crash performance with varying speed and vehicle count ............ 139
Figure 5.30: Throughput performance of non-safety data streams .................. 140
Figure 5.31: FTP duration with varying hop counts ................................... 142
Figure 5.32: TCP Performance: a) throughput, b) round trip time ................... 143
Figure 5.33: Dynamics of TCP : a) TCP-over-802.11, b) TCP-over-VeSOMAC. . ..144
Figure 5.34: Dynamics of TCP segment generation: a) 30 5-hop connections b) 10
1-hop connections .......................................................................... 145

Figure 5.35:

FTP duration with varying vehicle switching rates ..................... 146

xiii

Figure 5.36: TCP Dynamics with passing events: a) congestion window, b) segments
generation ..................................................................................... 148

Figure 5.37: Dynamics of TCP throughput: a)TCP-over-802.ll, b)

TCP-over-VeSOMAC ...................................................................... 149
Figure 5.38: Dynamics of TCP segment generation .................................... 150
Figure 6.1: MAC variations within networks ........................................... 158
Figure 6.2: Pseudo code for adapted CSMA/CA logic ................................ 160
Figure 6.3: Pseudo code for adapted TDMA logic ..................................... 161
Figure 6.4: Transmission fi'om TDMA node to CSMA/CA node .................... 162

Figure 6.5: Transmission from CSMA/CA node to TDMA node scenario 1 ....... 165
Figure 6.6: Transmission from CSMA/CA node to TDMA node scenario 2 ....... 165

Figure 6.7: Transmission from CSMA/CA node to TDMA node scenario 3 ....... 166

Figure 6.8: Pseudo code for protocol switching decision with ,1 and n. . . . . . . . .....170
Figure 6.9: Pseudo code for protocol switching decision with p and n. . . . . . . . .....172
Figure 6.10: Pseudo code of MAC protocol switching logic ......................... 175

Figure 6.11: Adapted network stack with dynamic MAC protocol switching

logic ........................................................................................... 176
Figure 6.12: Protocol switching decision threshold on CSMA/CA .................. 179
Figure 6.13: Impacts of number of contenders on maximum service rate .......... 181

Figure 6.14: Impacts of protocol switching decision threshold on fully connected
network ....................................................................................... 182

Figure 6.15: MAC protocol dynamics on fully connected network .................. 183
Figure 6.16: Impacts of switching decision threshold on arbitrary mesh network..l84

Figure 6.17: MAC protocol dynamics on arbitrary mesh network .................. 185

xiv

Figure 6.18: Real-time throughput with varying data rate ............................ 186
Figure 6.19: MAC protocol dynamics with varying data rate ........................ 187
Figure 6.20: Real-time throughput with varying number of contenders ............ 188

Figure 6.21: MAC protocol dynamics with varying number of contenders ........ 189

Figure 6.22: Pictorial diagram of spatial traffic variation ............................. 190
Figure 6.23: Real-time throughput with varying spatial traffic profile .............. 191
Figure 6.24: MAC protocol dynamics with varying spatial traffic profile ......... 192

XV

Chapter 1
Background
1.1. Wireless Ad Hoc Networks
Wireless ad hoc networks are formed by wireless communication links among
multiple communication devices. Nodes in an ad hoc network can forward data for
other nodes, and hence the decision on whom and where the forwarding data should
go are dynamically optimized based on the network connectivity and traflic load. It
is unlike the traditional networks in which the task of data forwarding is commonly
performed by designated routers with customized hardware and software. It is also
different from managed wireless networks where a special node called access point
manages the communication among other nodes.

Minimal configuration and quick deployment are the two most important features
of ad hoc networks. These features make these networks favorable for emergency
and tactical situations such as battle-field surveillance and disaster recovery. The
decentralized nature of most wireless ad hoc networks provides the adaptability of
applications in circumstances in which a central entity is not available or cannot be
relied on. And the scalability of the wireless ad hoc networks can be possibly
improved in contrast with managed wireless networks, although the overall capacity
is still limited, which has already been identified in [l] and [2] theoretically and
practically . A
1.2. Wireless Sensor Networks

Wireless sensor is a hardware device which is equipped with battery, sensor

module, micro-processor, memory, and RF receiver/transmitter. The advances in
micro-electro-mechanical system (MEMS) technology and digital electronics have
made it possible to integrate a wireless sensor node with low-cost, low-power tiny
hardware. For example, a Berkeley and Crossbow mote [3, 4] has an 8-bit Atmel
AT90L88535 microprocessor as CPU running at 7.3728 MHz clock fi'equency,
providing a data transmission rate of 19.2 Kbps by using the 916 MHz wireless

frequency. Figure 1.1 shows some of the currently available sensor devices.

 

Figure 1.1: Sensor Nodes Mote2, MoteZdot, Imote, TelosB, Cricket

The concept of wireless sensor networks (W SN) is leveraged by these tiny sensor
nodes, capable of sensing, processing, and communicating data. Many applications
can be operated via WSN, such as environmental monitoring, target field imaging,
intrusion detection, tactical surveillance, vehicle-tO-vehicle management, seismic
structure response, and ecosystems monitoring. A sensor network usually is
composed of a large number of sensor nodes that are densely deployed either within
the phenomenon or very close to it in a stationary manner. Most of the time it is not
necessary to engineer or predetermine the exact geographic positions of sensor nodes,
which makes it possible to arbitrarily deploy in some inaccessible terrains or in
disaster relief environments. Hence self-organization capability of individual sensor
nodes is essential for algorithms and protocols used in sensor networks.

Collaboration between the sensor nodes is another distinct feature. Due to the limited

resources, each sensor node is expected to carry out few simple local processing and
to transmit only the required and partially processed data to a “fusion” node through
a low data rate flow. Node failure is also a problem that the sensor network protocols
and algorithms have to face since sensor nodes are powered by battery and in most
cases frequent replacements of batteries are not a possibility.

Following is a list of wireless sensor network specific issues [5-8]:

Application Specific: There are a large number of applications of the sensor
networks such as environment data collection, public facility monitoring, vehicle
tracking, battle-field surveillance and intrusion detection, which all benefit fiom
combination of sensing, computing and communication technology. Different
application scenarios diverge from each other (i.e., design requirements of a sensor
network change with application), thus it is unlikely to find a general solution for all
applications. For example, the challenging problem of low-latency precision tactical
surveillance is different from that of a periodic weather monitoring task.

Ad Hoc Deployment: Often times, there is no infrastructure in the regions where
sensor nodes are deployed. Under unplanned wireless sensor network deployment, it
is the individual sensor node’s responsibility to figure out the connectivity and data
flow direction. This requires the sensor nodes to be self-organizing.

Eneggz Constraint; Different from ad hoc networks, sensor nodes in WSN are all
powered by battery and the replacement is usually difficult. Thus energy
consumption is a primary consideration for wireless sensor network protocol and

algorithm design. Since communication is significantly more expensive than

computation [9], reducing energy dissipation used in communication becomes very
important. Typically the non-essential energy consumptions are contributed from
four sources.
> Protocol overhead: besides valid data certain control messages have to be
exchanged to access communication resources;
> Message collision: unnecessary additional energy is wasted by
retransmitting as well as receiving possible duplicate messages;
> Overheating: sensor nodes spend energy in receiving messages for which
they are not intended, because that message transmission usually is
broadcast within WSN;
> Idle listening: when there is no centralized scheduler to manage sequence
of transmission, sensor nodes have to keep the wireless radio interface up
(power on) for possible message receptions. Even when the sensor nodes
do not transmit or receive any messages, the consumed energy can still be
prevalent. Researches [9, 10] have shown that idle listening actually
accounts for most of the energy expenditure at low traffic situations, which
is quite common for most applications in WSN.

In order to prolong network lifetime, different strategies should be incorporated at
various network layers including hardware improvement at physical layer, energy
efficient medium access control protocol, avoiding packet collision and idle listening,
optimal routing path selection, and content filtering or error tolerance at application

layer.

Scalabilim' For certain applications, the number of sensor nodes in WSN can be
very large, in some cases up to hundreds or thousands. Protocols and algorithms
have to scale to these large numbers and deal with issues such as protocol overhead,
limited bandwidth, and energy expenditure. Furthermore, it is not possible to build a
global addressing scheme for the deployment of such large number of sensor nodes
as the overhead of ID maintenance can become very high. Thus, traditional IP-based
protocols can not be directly applied to WSN.

Network Dvnthics: Although wireless sensor networks are often considered as
stationary, some applications may require one or several powerful mobile nodes to
achieve better performance [11, 12]. Beside mobile nodes, nodes addition and nodes
failure (possibly due to battery drain) can also invoke network connectivity changes.
The potential dynamics in the networks strengthens the need for self organization at
the MAC and the routing layer. The MAC and routing protocols which can smoothly
respond to the dynamics are preferable

T rafic Patterns: Unlike communication in traditional ad hoc networks which is
based mostly on point-tO-point transmission, sensor network mainly uses a
multi-point to point communication paradigm and almost all applications of sensor
networks require the flow of sensed data from multiple sources to a particular base
station. This, however, does not prevent the flow of data to be in other forms (e.g.,
multicast or peer to peer). The reason that all messages are sent to all the radio
neighbors is because a single sensor node lack the global knowledge of the whole

network. In addition, the traffic in the sensor networks can be continuous,

event—driven, query—driven, or hybrid, based on specific applications.

anIin of Service: Providing bounded message latency and high delivery ratio
may be crucial in certain time-constraint applications such as intrusion detection and
disaster warning. However, in some other applications like environmental
monitoring it is enough to have only occasional packet delivery but with long
network lifetime requirements. Especially when battery power is below normal
operating threshold, quality of service has to be compromised for lifetime.

Lo_cgtion Awareness: Location awareness in sensor nodes is important since data
collection is normally based on the location of data and event generation. In a WSN
often it is not feasrhle to use Global Positioning System (GPS) hardware in cost and
energy constrained nodes. Methods based on triangulation [13], for example, allow
sensor nodes to approximate their positions using radio strength from a few nodes
with known coordinates. It is found in [13] that algorithms based on triangulation or
multilateration can work quite well under conditions where only very few nodes
know their positions a priori.

1.3. Applications of Wireless Sensor Networks

Sensor networks are initially motivated by military applications such as intrusion
detection, battle-field surveillance and enemy tracking. Recent research shows a
rapid increase on the civilian applications like environment data collection, health
monitoring, and disaster relief.

1.3.1 Military applications

Battlefield Surveillance: Important terrains, routes, and paths can be monitored by

deploying sensor nodes to the dedicated field. Sensor nodes can sense the activities
or predefined critical events then send raw or post-processed information to the base
station. Real-time situation requests can also be generated at the base station, and
disseminated to requested areas.

Tamet Hacking: Collaborative mobile sensing can cooperate with navigation
system. For example, networked tracking of adversarial mobile targets using
unmanned ground and airborne sensors is an emerging application for the militaries’
network-centric warfare capability. Target tracking is a prevalent military
requirement across a wide spectrum of surveillance and reconnaissance scenarios
including those in remote and urban battlefields, inside large buildings and public
places such as airports, train stations, and inside underground tunnels.

Forces and Equipment Monitoring: All forces and equipment can be attached with
sensor nodes. Then the attached sensor nodes can periodically report the status to the
commanders or leaders. The report can be sent to a single sink or multiple sinks and
forward to upper command hierarchy if necessary.

1.3.2 Environmental Data Collection Applications

Clickable Ecosvstem: This system is developed in the cooperation of Dr. Stuart
Gage fi'om Department of Entomology and Dr. Subir Biswas from Department of
Electrical and Computer Engineering at Michigan State University. Sensor nodes are
placed at interested spots in the outdoor field. Bach sensor node automatically
records the acoustic signals, weather data and images of monitoring spot. After the

recording, acoustic signals are sent back to a data server in the laboratory via

wireless through a single-hop or multi-hop network depending on locatiOn and
availability. If individual sensor node is strong enough and there are not many
obstacles in the sensing field, single-hop communication will be used to collect all
sensing data. Otherwise, multi-hop communication will be used so that sensing field
is covered without requiring a very powerful sink node. When an acoustic signal is
received by the server, further analysis on biological indices are computed based on
acoustic intensity in selected frequency bands. The final environmental acoustics are
then stored in digital library, which can be accessed via regular internet network.

Some sound tracks, sensing spot images and videos are available in [14].

 

     
 

 
  

Network

National Repository
‘Clickable Environment’
Web Based Clients for

 

 

Management
. and Sensor
Education and Research Public lnl I - [rzg ‘ 4 2'. P ing
Existing Data such as ::/< . ,_,.; . .-. - .
from National Weather I" “E" ‘"‘ "‘ :eomal Repository
Server rvers
Regional Data Aggregation ...;‘fl'm.’ Optional Field Data
Satellite Broadband
Networks
Gateway Uplink‘, .-" “...“... Internet. A093113101”
Node (GN)\ 3318"“ "N. W0"

   
   

l ‘-—*
Field Habitat Server
“‘ ‘Clustef .l'£:"'.12':'..' 3" ,..- "1'

Leader (CL)

Regional Field Sensor Network:
Tier-2 Lower Sensing Resolution:
e.g. 30m - 500m

   

Dynamic ' ' 0|- with
Hierarchical sensors

 

transmit} ll 3. L/ l. (l. h.

Resolution: e.g. 1m - 30m Trer -1 nodes with sengors

 

 

 

Figure 1.2: System architecture of clickable environment [14]
1.3.3 Health applications

Tracking and Monitoring Doctors and Pgtients inside a Hospital: A small and

light sensor can be attached to each patient in the hospital. The sensor is able to
monitor the heart rate, blood pressure, body temperature, and to locate the patient.
Sensor data is sent to a central monitoring center and processed so that all patients
can get immediate response if any reading is abnormal. And sensor nodes can be

attached to doctors to locate them for potential emergencies.

 

.Waterproof Case

  

Stargate Single
Board Computer

' .. . . ’ Solar Panel
Interface . Wrreless Commun Habitat \ _.

. Card: IEEE is.»

. 802.11b (blow) " .
Micro- ‘
phone Local Flash . 12V Deep

Cycle Battery

 

 

 

Figure 1.3: Clickable environment sensor platform [14]

1.3.4 Other Applications

Home Automation: Smart sensor nodes can be embedded in all home electronics,
such as vacuum cleaners, micro-wave ovens, refrigerators, washing machines, TVs,
air conditioners, lamps, and computers etc. All the electronics can interact with each
other or with external network via internet or cellular network. End users are also
able to control or manage home devices locally and remotely.

Vehicle Tracking and Detection: Sensors with GPS function can be built into cars.
Location information of cars are recorded and sent back to base station for example
city traffic management center. Individual car is tracked down and real-time traffic

information can be derived from fusing all cars’ information.

Chapter 2
Self Organizing Medium Access Control Protocols
2.1 Role of Medium Access Control in Wireless Networks
In wireless networks, packet collision is a common challenge [15-19]. Packet

collisions usually result from two or more nodes sending data at the same time over
the same transmission medium or channel. Medium Access Control (MAC)
protocols have been developed to aid nodes to determine as to which node gets to
use the channel when competitions for the channel exist. In the literature, this
problem is known as multi-access channel allocation problem of the MAC layer,
which belongs to a sub-layer of the data link layer in the seven-layer Open System
Interconnect (OSI) network model. The addressing and channel access control
mechanisms proposed in the literature make it possible for several nodes to
communicate within a network.
2.2 Concept of MAC Self Organization

Generally speaking, protocol self organization means that elements in a protocol
interact with each other to dynamically achieve a global protocol function or
behavior [20, 21]. According to the definition above, the services provided by MAC
self organization should be “self” adapted to environmental changes. More
specifically, the concept of self organization includes the following four aspects. ,

(i) The protocol itself is unsupervised and distributed.
(ii) Protocol parameters can be dynamically changed by adaptation of network

variables. The purpose of dynamic changes is to constantly improve and

10

maintain better protocol performance.

(iii) Protocol state machine can be also changed when changing just the
protocol parameters may not be enough to cope with the changes in
network environment.

(iv) A node can even change its operatingprotocol when the protocol state
machine and parameter changes within a single protocol may not be
enough to cope with the changes in network environment.

2.3 Needs for MAC Self Organization

MAC layer has a direct bearing on how data can be exchanged between two nodes
along a routing path in the network. Because of the unique features we described in
chapter 1, such as constraints on computational ability, storage and energy resources,
MAC protocols in wireless Ad H00 and sensor networks are quite different from
traditional networks. MAC self organization addresses those constraints in the
following ways:

(1] Ad hoc deployment: In Ad Hoc and sensor networks nodes are deployed in an
unplanned manner and with typically no centralized entity. The MAC protocol itself
at each node has to find out the connectivity and neighborhood information so that
all the nodes can access the shared medium or channel to create a basic
communication infrastructure. The MAC self organization addresses this
requirement because of its autonomous operation feature. And if any unplanned
redeployment happens, it could adjust to the dynamics accordingly.

(2) Enemy limitation: As mentioned before, energy is a scarce resource in wireless

ll

sensor networks. In addition to building a basic communication link, MAC protocol
in wireless sensor network has to be energy efficient by providing a smart
sleep/wake-up mechanism so that it ensures sensor nodes to sleep as long as possible
to save energy consumption and to extend network lifetime. The smart
sleep/wake-up schedule has to be obtained in a distributed manner, and the changes
caused by energy change need to be addressed. MAC self organization is suitable for
these operations due to its distributed manner and dynamic adjustment features.
(3) Network dynamics: There are three major aspects of network dynamics. They
are topology dynamics, load/name dynamics, and communication dynamics.
> Topology dynamics often include node failures, link failures, and node
mobility. Sensor nodes are more prone to failure in contrast to traditional
networks due to limited resources. Thus new sensor nodes can be deployed
for failure recovery or redundancy. Also a certain number of nodes in a
network can be mobile for enhancing the network operations, and any node
mobility adds to the network dynamics.
> Load dynamics is usually spatial and temporal. It is typically introduced by
non-uniform deployment or emergence of certain events.
> Communication dynamics can be generated by outside radio interference,
radio medium fluctuation, and radio strength change due to fading.
The advantage of MAC self organization is that it copes with these various dynamics
by changing protocol parameters, state machine, or even the protocol itself, as

outlined in Section 2.2.

12

2.4 Research Issues Addressed in this Thesis
A number of protocol self organization issues related to the MAC layer in
wireless ad hoc and sensor networks is investigated in this dissertation. A summary

of the investigated issues and their relations are outlined in Figure 2.1.

 

 

Introduction and MAC Self
Organization Overview
(Chapter 1 8r 2)

 

    
 
  
  

Inter-MAC Self
Organization

  
   

Multi-MAC
Organization

 
     
   
   
   

MAC Protocol Switching
(Chapter 6)

 

Core Self Organizing tom-layer Application
ISOMAC
(Chapter 3)

  
    
 

VeSOMAC
Extension for
Vehicular Networks

(Chapter 5)

   
 
      

Linear Network
Convergence Model
(Appendix A)

 
 
   

 

 

 

Figure 2.1: Pictorial summary of the investigated issues in this thesis proposal
2.4.1 Design of Self Organizing MAC
2.4.1.1 Motivation and Related Work

The sensor nodes are often critically constrained by their operating energy
availability. This makes energy management as one of the key challenges in
designing such systems. As a result, wireless embedded networking is often
perceived as a design problem to deal with energy-bandwidth and energy-delay
tradeoff, as Opposed to the classical delay-bandwidth tradeoff in conventional

networking systems.

13

The protocol Sensor-MAC (SMAC) [9] attempted to introduce interface
wake-sleep cycles in the presence of random channel access. T-MAC [22] enhances
the performance of SMAC by making the wake periods adaptive. Both of them
suffer from the inherent energy inefficiency of contention based protocols. In
TRAMA [23] nodes maintain a network-wide common frame which is organized
into alternating contention-based “random access” and contention-free TDMA
allocation “scheduled access” regions. Control packets of TRAMA are still
susceptible to collisions. TDMA-W [24] is another distributed out-of-band TDMA
protocol. But the adaptation of network dynamics is not handled well in TDMA-W.
2.4.1.2 Proposed Work

We wanted to address the intra-MAC self organization problems with energy
limitation, network dynamics, and ad hoc deployment from the list in Section 2.2.
Thus an In-band Self-Organized MAC (ISOMAC) protocol is proposed. ISOMAC is
a distributed TDMA typed MAC protocol. By avoiding explicit timing information
exchange, ISOMAC can work without network-wide time synchronization which
can be prohibitive for severely cost-constrained sensor nodes. Efficient energy
expenditure is achieved by employing a partial node wake-up and header-only
transmission strategy based on the instantaneous nodal data rate. The slot-cluster
effect, caused by in-band bitmap constraints, enables ISOMAC to offer better spatial
channel reuse compared to traditional distributed TDMA protocols. The detailed
ISOMAC protocol will be introduced in chapter 3.

2.4.2 Cross-layer Design

14

In traditional network design, the seven-layer open systems interconnect (081) [25]
model divides the overall networking service into seven layers and defines a
hierarchy to be provided at each layer. The central idea of cross-layer design is to
Optimize the control and exchange of information over two or more layers to achieve
significant performance improvements by exploiting the interactions between
various protocol layers. There are two primary reasons that favor the cross-layer
design. To begin with, wireless links create new problems for layered protocol
design. One classic example is TCP which considers packet error as an indication of
congestion. Additionally, cross-layer design could provide more opportunistic
communication than single layer design [26-33]. In [28] the authors divide
cross-layer design into four categories.

(1) Creation of new interfaces: The created new interface will be used to share
information between layers. This includes sharing lower layer(s) information upward
towards higher layer(s), higher layer(s) providing parameters downward towards
lower layer(s), and an iterative loop between two layers.

(2) Merging of adjacent layers: This manifestation provides service from a new
super layer that is the union of constituent layers.

(3) Design coupling without new interfaces: Two or more layers can be coupled
together without creating extra interfaces for the purpose of information sharing.

(4) Vertical calibration across layers: The performance at high layer can be a
function of the parameters at all layers below it.

2.4.2.1 Motivation and Related Work

15

While solving the energy problem at the MAC layer, the TDMA mechanism can
give rise to increased end-to-end routing layer delay. This can happen when the
TDMA slots of sensor nodes on a route are not time-ordered in the same sequence as
the nodes appearing on the route. The problem is that if we have a TDMA type
medium access control for delay sensitive and event based sensor network
application, what is the best routing scheme.

DMAC [34] tries to allocate MAC communication sequence based on routing path
along collecting tree in the sensor networks. However, DMAC only assumes
unidirectional data flow towards the root in the presence of preset routes. In [3 5], the
protocol proposes to use a link scheduling algorithm to find the minimum-delay
schedule for given slot lengths for all the links. The ignorance of congestion at
higher level nodes near sink is the primary disadvantage.
2.4.2.2 Proposed Work

We take a different approach to address the delay problem by computing
minimum delay routes based on a given TDMA allocation. We try to find the
delay-optimized routing based on pre-set TDMA slot allocation. Our proposed
Minimized Slot Misordered Routing (MSMR) addresses the problem of end-to-end
delay mitigation in sensor network with TDMA MAC. Delay reduction in MSMR is
accomplished by computing least cost routes with a link cost formulation based on
the degree of misordering of the TDMA slots of nodes across a link. Chapter 4
describes the details of MSMR.

2.4.3 Application of ISOMAC Protocol for Vehicular Networks

16

2.4.3.1 Motivation and Related Work

MAC self organization is important not only in sensor applications but also in
other applications such as the ad hoc vehicular networks. Different features of the
application impose different challenges on MAC self organization. Unlike energy
being the primary issue in sensor networks, message (especially safety related)
latency and delivery ratio become the first priority in vehicular networks.

A number of variations of CSMA/CA and 802.11 have been implemented in
[36-38]. The unbounded delay caused by the fundamental random access mechanism
is an issue for such protocols. The protocols in [39, 40] propose schedule-based
TDMA mechanisms, all with a large upfront reconfiguration delays. The protocol
LCA [41] proposes a scheduled TDMA scheduling mapping with vehicles’
instantaneous geographical location. But the problem of complete pre-mapping of
geographical locations and dimensioning of optimal cell size are non-trivial.
2.4.3.2 Proposed Work

A multi-hop delivery delay minimized MAC self organization protocol for the
vehicular networks has been adapted from ISOMAC in chapter 5. The adaptation
addresses the problems of bounded delivery latency and small reconfiguration delay.
The adapted Vehicular Self-Organizing MAC (VeSOMAC) is designed to be vehicle
location and movement aware so that the MAC TDMA slots in a vehicle platoon can
be time ordered based on the vehicles’ relative locations. Chapter 5 provides detailed
information of VeSOMA C.

2.4.4 MAC Protocol Switching

17

2.4.4.1 Motivation and Related Work

Previously we look into the MAC self organization problem in the context of
intra-MAC operations. Different types of MAC protocols have merits in varying
network scenarios. For instances contention based protocols are generally suitable
for bursty and low congestion scenarios, whereas schedule based protocols
overwhelm in multiple concurrent traffic scenarios. Multiple different MAC
protocols could coexist within the same network, especially a network with varying
traffic dynamics. Instead of MAC self organization problem in infra-MAC protocol,
coexistence of multiple MAC protocols raises new challenges for inter-MAC
protocols.

Protocols like Funneling-MAC [42] try to deal with non-uniform network
dynamics by a single hybrid MAC protocol. Although problems are relieved to some
extent, these solutions are only suitable for applications with special traffic
characteristics or assumptions with powerful nodes’ coordination. The traffic
heterogeneity is not fully explored to address the problem of maximizing the
network-wide throughput.
2.4.4.2 Proposed Work

We propose to handle the MAC self organization challenges from coexistence of
multiple MAC protocol in network by the concept of “MAC switching”. This is used
to deal with the ad hoe deployment and network dynamics problems. Instead of
trying to give a generic solution, we elaborate the MAC switching concept between

two candidate MAC protocols, TDMA and CSMA/CA. The modifications of

18

transmission rules in both protocols and the general switching logic have been
developed. Chapter 6 provides details.
2.5 Summary

We first describe the role of Medium Access Control in wireless networks. The
concept of the MAC self organization is then elaborated. Inspired from three distinct
constraints of the WSN we further discuss the needs of the MAC self organization.
The development of the topics addressed in this thesis is finally presented. A brief
motivation and related work, followed by a summary of the proposed work, are

provided for each of the four major topics in this thesis.

l9

Chapter 3
Towards In-Band Self Organization in Energy-Efficient MAC
Protocols for Sensor Networks

3.1 Introduction
3.1.1 Motivation

Because of their low cost, tiny form factor and remote unattended deployments,
embedded sensor nodes are often critically constrained by their operating energy
availability. This makes energy management one of the key challenges in designing
such systems. As a result, embedded wireless networking in WSN is perceived as a
design problem to deal with energy-bandwidth and energy-delay tradeofi‘, as
opposed to the classical delay-bandwidth tradeofl' in conventional networking
systems. While energy syntaxes are being developed by the research community at
all the protocol layers, energy-eflicient Medium Access Control (MAC) remains a
key design challenge. In this chapter, we present an intra-MAC self organization
mechanism to mainly address the problems of energy, ad hoc deployment, and
network dynamics.
3.1.2 Related Work

A common design approach for the existing energy—aware sensor MAC protocols
[9, 22-24, 34, 43, 44] is to reduce idle energy consumption [45] by introducing
network interface sleep. This is typically achieved by introducing a notion of
sleep-awake cycle, in which a node sends and receives data during the wake periods,

and conserves energy by switching off its interface during the sleep periods. The

20

smaller the wake-sleep duty cycle, the higher the savings. The goal is to operate in
the smallest possible duty cycle while being able to support the application traffic
loading. For sensor MAC protocols, it is often necessary to trade MAC delivery
delay, effective throughput and node fairness [46] for energy efficiency.

Sleep-wake cycles are typically not feasible for traditional contention-based
protocols such as ALOHA [47], CSMA [48], and 802.11 (DCF mode) [49]. This is
primarily because these random access protocols are fimdamentally asynchronous in
not having timing coordination between the senders and their receivers. As a result, a
node is needed to be always awake for possible packet receptions from its neighbors.
This results in the energy inefficiency for random access protocols.

In a hybrid design, the protocol Sensor-MAC (SMAC) [9] attempts to introduce
wake-sleep cycles in the presence of random channel access. During the wake
periods nodes execute an 802.11-like contention based MAC protocol, and during
the sleep periods all nodes turn their interfaces ofi‘. Sensor nodes form virtual
clusters so that all nodes within the same virtual cluster maintain the same
wake-sleep schedule. By decreasing the wake-sleep duty cycle, SMAC can trade
latency and effective channel capacity for energy efficiency. The main concern with
SMAC is that since its basic medium access mechanism is contention-based, the
protocol is still susceptible to collisions and its resulting energy inefficiency during
waking periods. Also, the protocol assumes static traffic loading with predetermined
duty cycles. While the latter issue is addressed in the protocol T-MAC [22] by

making the waking periods adaptive, it still suffers from the inherent energy

21

inefficiency of contention based protocols, packet collisions.

This inefficiency can be avoided in Time Division Multiple Access (T DMA)
based protocols. In TDMA protocols such as HiperLan-II [50], since all
transmissions within a MAC frame are pre-scheduled, it is possible for a node to
sleep when it is not expected to transmit or receive packets. Although it solves the
energy problem, an implementation issue with HiperLan-H of its dependency on a
centralized base station for TDMA scheduling still exists. For ad hoc deployed
sensor networks, such centralized infrastructure is usually not feasible, and thus the
design goal should be to develop a TDMA style protocol with distributed MAC slot
scheduling algorithms.

The protocol TRAMA [23] implements such a distributed TDMA allocation
among time synchronized nodes. In TRAMA, nodes maintain a network wide
common frame which is organized into alternating contention-based “random
access” and contention-free “scheduled access” regions. Data transmission is
performed in “scheduled access” slots and neighbor information exchange is
performed in “random access” slots. After the neighbor information (up to two-hops)
is collected during the contention-based phase, the nodes execute a distributed
election method to decide the transmission schedules within the local neighborhood.
TRAMA clearly achieves the goal of distributed TDMA for improved energy
efficiency without a centralized coordinating base station. The following operational
shortcomings of TRAMA have been identified. First, global TDMA frames require

network wide time synchronization, which can be a severely restrictive process [51,

22

52] for cost-constrained sensor nodes, especially in very large networks with
potentially thousands of nodes. Limited energy, bandwidth, hardware and unstable
links in multi-hop sensor networks with unpredictable delay characteristics make
network wide time synchronization particularly difficult. Second, although the data
communication in TRAMA is contention-free, the control information exchange is
still susceptible to collisions which can limit the energy-gain of the protocol to some
extent. Finally, a new node can join the network only during the random access
period. Thus, for keeping the node join-latency small, the random-scheduled duty
cycle will have to be appropriately dimensioned based on the rate of change in
network topology. In spite of these operational difficulties, TRAMA provides a
useful TDMA framework with distributed MAC scheduling.

TDMA-W [24] is another distributed MAC scheduling protocol without using
contention based control like TRAMA. Nodes in TDMA-W send control packets
during scheduled data slots, and that is how the neighbors’ allocation information is
disseminated. Based on its neighbors’ allocation information, a node is able to select
a collision-free transmission slot, which will be used for subsequent data as well as
control packet transmissions.

Although TDMA-W has a steady state allocation target very similar to our
proposed ISOMA C, the former has the following shortcomings. First, TDMA-W, as
presented in [24], requires absolute slot identifications to be exchanged through the
control packets. Unlike ISOMA C, that makes TDMA-W dependent on global

framing and time synchronization. Second, TDMA-W incurs a high energy cost as

23

follows. In each frame, a node must remain awake during its wake-up slot even if it
is not transmitting or receiving during that frame. This implies that a node must
expend one full data slot worth of energy in each frame irrespective of its
communication activities. Third, in TDMA-W there is no syntax for a node to inform
its neighbors about its own “wake-up slot”. In the absence of this information,
although the protocol will work when all network nodes are added/activated
simultaneously, it will not work in more realistic incremental node addition scenarios.
Whereas, ISOMAC addresses the shortcomings of TDMA-W.
3.1.3 Proposed ISOMAC Protocol

We present a distributed TDMA scheduling protocol ISOMAC (In-band
Self-Qrganized MAC), which achieves similar goals as in TRAMA, but without its
restrictions stated above. The key idea in ISOMAC is to use an in-band control
mechanism for MAC self-organization. Instead of sending explicit control packets as
in TRAMA, nodes use a bitmap vector in data packet headers for exchanging slot
occupancy information among the neighbors. In the header of each outgoing packet,
the transmitting node inserts a bitmap vector which represents the relative TDMA
slot timing of all its l—hop neighbors with respect to the transmitting node’s own slot
location. As a newly joined node receives data packets from its neighbors, it
gradually learns about the TDMA slot locations of all its neighbors and the
neighbors’ neighbors (i.e. 2-hop neighbors). Based on this allocation information of
up to two-hop neighbors, the new node is able to select a collision-free transmission

slot. In ISOMAC, this is how an in-band control mechanism is used to avoid the

24

contention based out-of-band control, as used in TRAMA.

In addition to its energy efficiency, the primary features of ISOMAC are as

follows.

1. MAC self-organization is achieved using a novel in-band technique. Since
there is no contention based operation in the protocol, it is virtually collision
free at steady states.

2. ISOMAC does not depend on network time synchronization. Although it can
be implemented with time synchronization, experimental results indicate that
the performance improvement due to synchronization is quite modest.

3. The protocol is fair. A guaranteed data rate is allocated to each node, which is
allowed to use a part or the entire allocated rate depending on its individual
traffic load

4. ISOMAC is insensitive to moderate channel errors. This is notable since
in-band protocols are generally known to perform poorly in erroneous channel
conditions.

5. ISOMA C’s in-band bitmap vector design intrinsically provides higher spatial
reuse compared to other distributed TDMA protocols.

6. In ISOMAC, information about the location of wake-up slot is implicit and
therefore, unlike in TDMA-W, it can handle both simultaneous and
incremental node additions.

3.2 N etwork, Traffic and Operation Model

ISOMAC is designed for arbitrary sensor mesh topology using a single channel

25

with spatial reuse. Nodes are static and the links are bidirectional. Upon deployment,
a node executes the in-band ISOMAC protocol for choosing a collision flee
transmission slot. Nodes automatically adjust their allocation to accommodate
topology changes caused by node arrivals and departures.

ISOMAC is routing protocol agnostic and it can support point-to-point,
point-to-multipoint [53] and multipoint-to-point sensor [54] traffic. In ISOMAC, a

node is allowed to transmit data at any rate up to X. which is the maximum

alloc ’

allowable rate per node. A split-slot interface sleep technique is introduced to ensure
that a node can adjust its sleep-wake duty cycle to optimize its energy expenditure
according to its own and the immediate neighbors’ data transmission rates.

The notion of flame in ISOMAC is completely local to individual nodes (same
size for all nodes). Timing information exchange between nodes is relative, thus the
protocol can work without network time synchronization. If the nodes, however, are
time synchronized, ISOMAC can be implemented with global flame structures. In
either case, all sensor nodes in the network are required to run at the same clock
flequency, with limited degree of allowable clock drifts.

3.3 ISOMAC Protocol Details
3.3.1 Frame and Slot Structure
Packets are assumed to be of constant length and correspond to the Tx-slotl

duration I. As shown in Figure 3.1, each Tx-slot is split into a header sub-slot

(T h eader) and a relatively much larger data sub-slot (T data ). A flame is of duration

 

l . . . . . .
From tins pornt, unless otherwrse specrfied, the term slot Will be used to refer to a transmisszon slot.

26

T flame , and it defines the minimum periodicity of transmission slots flom any node.
Therefore, the allocated rate to a node can be written as lalloc = 1/ T fi'ame packets
per unit time. Although one Tx-slot is periodically allocated to each node during a
flame, a node can choose to skip transmissions in the absence of data packets in its

transmission buffer. Such data skipping are marked as “Header-only Tx” in Figure

 

 

 

3.1.
Ba De Ea
a) Linear sensor topology

Time a
H er Data

 

m; T?“
A:lj

Interrupt sub-slot Tx-Slot

B 21:]

Data and header Tx

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E :ZL 11:]
H—J
\ Y J Headcr'only TX

E’s flame
b) Steady state allocation for ISOMAC-A

 

 

 

Figure 3.1 Slot allocation in ISOMAC
For each node, immediately after its transmission slot, there is an interrupt
sub-slot. This receive-mode sub-slot can overlap with any of this node’s l-hop
neighbors’ transmission slots. As a result, the interrupt sub-slots do not affect the

available data rate, as it is intended only for receiving. Also, this sub-slot is typically

much smaller than the data sub-slot duration. In our design, Tint errupt has been

set to be equal to the header duration T h ea der' The purpose of this sub-slot will be

27

explained later when the protocol details are elaborated. Note that all the defined
sub-slot types include necessary guard times for modern preambles and Tx-Rx
switch over latencies, when applicable.
3.3.2 Asynchronous ISOMAC (ISOMA C-A)
3.3.2.1 Steady State Allocation and Transmission

Slot allocation in ISOMAC needs to satisfy the following timing constraint.
liming Constraint: At steady state, no two one-hop or two-hop neighbors '
transmission slots can completely or partially overlap. Overlaps between one-hop
neighbors cause direct collisions and between two-hop neighbors cause hidden
collisions [55].

A valid allocation schedule for nodes A, B, D and E in the linear network
topology of Figure 3.1:a, is shown in Figure 3.1:b. Since the shown allocation is for
the asynchronous version of ISOAM C, nodes are depicted to maintain their own
flame boundaries. Note that except the node pair (A, E) all other nodes are within up
to two-hop distance of each other. That is why in the allocation schedule, all nodes
have completely non-overlapping Tx-slots except those of nodes A and E. Such
overlapping slots provide spatial channel reuse in ISOMAC.

Although in each flame a full Tx-slot is allocated to each node, it may transmit
both header and data, or only header. In other words, even if there is no data to be
sent, a header is always transmitted in each flame flom each node. Packet headers
are used by ISOM4C protocol for sending allocation information using an in-band

bitmap vector as explained below.

28

3.3.2.2 In-band Header Bitmap

Relative timing information about Tx-slot allocation is exchanged using a
Bitmap Vector (BV) in each packet header. Bits in the EV from a node represent how
its one-hop neighbors are occupying Tx-slots in the immediate temporal vicinity of
the node’s own Tx-slot. The concept is explained in Figure 3.2, in which the top
segment illustrates how a node P is allocated a Tx-slot within its own TDMA flame.
The middle row depicts the Tx-slots occupied by all of P’s one-hop neighbors. Note
that although these neighbors’ slots are shown in the timing context of P’s flame, all
four neighbors maintain their own frames which are asynchronous to each other.

The bottom row shows the bitmap vector that node P inserts in the header of each
of its outgoing data packets. Middle of the bitmap represents the timing of P’s own
slot. In this example, the bitmap vector is 4-bit long and each bit represents the
occupancy status of two slots in the vicinity of P’s own Tx-slot For example, the ‘ l ’
in “+1” location indicates that two slots immediately following P’s slot are already
fully or partially occupied. Similarly, a ‘0’ in the “-1” location indicates that node P

perceives both the slots before its own slot to be flee.

 

Tx Slot allocated th (Header + data)
<——— P’s Frame

HIHWZHH
I-

»? Eb
iT:

All Tx—slots allocated to P’s l-hop neighbors
Interrupt sub-slot

l
P’sBitmapVector IIIOII rlj
(LengthB=4) -2 -1|+1 +2

 

’

 

 

 

 

 

        

 

 
 
 

   

 

 

 

 

Figure 3.2: Concept of in-band header bitmap

29

The bitmap vector length is typically much smaller than the total number of
Tx-slots in a flame, and therefore it can convey the occupancy information only
about limited number Tx-slots around the temporal vicinity of the transmitting
node’s own slot. In the example in Figure 3.2, the frame size is 12, whereas the
bitmap vector length is only 4, which can convey the occupancy information about 8
slots. Observe that with a bitmap size B = 4, P is unable to represent the occupancy
information about one of its neighbors’ (the one in extreme left) slot.

Using this header bitmap, a transmitting node continually informs all its l-hop
neighbors about Tx-slots that are occupied by the transmitting node’s l-hop
neighbors. By listening to the bitmaps in all received packets, a node can figure out
the relative slot locations of all its l-hop and 2-hop neighbors. In turn, with this
information, the receiver node can choose a collision-flee Tx-slot which is
non-overlapping with the slots of its l-hop and the 2-hop neighbors.

The primary advantage here is that all timing information exchanged is relative
to the slot location of the transmitting node. This relative timing allows ISOMAC to
be implemented with or without network time synchronization. Though in the
asynchronous version, the bitmap efficiency is reduced by the overhead that one bit
here represents the occupancy information of two slots instead of one. This is
because a neighbor’s Tx-slot can partially occupy two slots in the absence of TDMA
flame synchronization. In the worst case, this effect may actually render half of the
system capacity unusable. In the synchronous case, however, this overhead does not

exist. This indicates that in the asynchronous ISOMAC-A, the capacity efficiency is

30

traded for more distributed deployments without the need for time synchronization
across the network.

Since the bitmap length is kept smaller than the flame slot count, the ISOMAC
allocation needs to satisfy the following Bitmap Constraint: If two nodes i and j are
one-hop neighbors then i is chosen slot should be able to be represented within the
bitmap vector of j. The same is applicable for node jis slot. Since each bit
corresponds to two slots, this constraint means that the slots of nodes i and j can not
be more than B slots apart, where B is the bitmap length.

For a node, the bitmap constraint is satisfied when it is able to find a ‘1’
corresponding to its own time slot in the bitmaps of Q its l-hop neighbors. In the
allocation shown in Figure 3.2, the separation between P’s Tx-slot and one of its
neighbors’ Tx-slots (extreme left) is more than B (which is 4) slots. This indicates
that the shown allocation does not satisfy the bitmap constraint, and therefore is not
stable. The bitmap constraint is particularly important because a large B incurs
higher capacity overhead, and therefore the goal of the protocol would be to use the
smallest possible B, which will allow the protocol to converge within acceptable
time duration.
3.3.2.3 Transmission Slot Feasibility

For a new node that is entering the network, a feasible transmission slot is one
that satisfies the timing and the bitmap constraints as defined in Sections 3.3.2.1 and
3.3.2.2.

Feasible Slots: From the bitmap standpoint, a feasible slot should be within a time

31

region represented by shared ‘019 in the bitmaps transmitted by all the neighbors of

the new node.

Consider the topology in Figure 3.3, in which a new node R joins in between two
unconnected nodes P and Q. Bitrnaps (with length 4) flom P and Q are shown in
Figure 3.3:a as received by the new node R. The shared ‘0’s in the bitmaps of P and
Q indicate a feasible time region for node R to choose a Tx-slot flom. The feasible

region is indicated in the figure.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a Feasible slot 1 l 0 0 ,
available ”WSW
ll Slots
<rL-'-———Feasible
T Time
Region
0 l O l
a i.
!l l I l 0 1
b. No slot available with
satisfied timing constraint
I 110 111]
Q

 

 

 

l1l10[1|

 

c. No slot available
with satisfied
bitmap and
timing constraints

 

 

I110 lll]

 

 

 

 

 

 

 

Figure 3.3: Slot selection feasibility

32

Proof of Feasibility: Since a shared ‘0’ bit indicates that the corresponding time

region is not used by any of P’s and Q’s l-hop neighbors, it is guaranteed to be
hidden collision flee flom all of R’s 2-hop neighbors. Also, since the chosen slot is
within the bitmap of all R’s l-hop neighbors (P and Q in this case), it is guaranteed
not to be used by any of those l-hop neighbors. These two clauses together satisfy
the ISOMAC protocol constraints for the chosen slot.
Since a slot (chosen by R) within that feasible time region is within the bitmap of
both of R’s neighbors, the temporal separation between R’s slot and any of its
neighbor’s slots is guaranteed to be less than the bitmap vector length, which is 4
here. This satisfies the bitmap constraint. Since both timing and bitmap constraints
are satisfied, the chosen slot can be declared as feasible.

For the bitmap vectors in the scenario in Figure 3.3:b, since there are no shared
‘O’s, no collision-flee time region will be available for R to choose a slot flom. If a
slot is chosen by R flom the time region indicated by a ‘0’ in P’s bitmap then it
would collide with a l-hop neighbor of Q. Therefore a hidden collision cannot be
avoided because of the violated timing constraint. Another possible situation is
depicted in Figure 3.3:c, in which the bitmap constraint is violated. As a result,
although there exist collision-free slots at ‘0’ regions, no feasible slots will be
available for the new node R in scenarios pictured in Figure 3.3:c.
3.3.2.4 Sleep-wake Schedule

In a steady state, a node remains awake only during the following time segments:

1. During the transmission slot header duration (T header ), and data duration

33

(T data) only if data needs to be transmitted. A data-present bit in the header is

set if data will be transmitted following the header in a given Tx-slot

2. During the header duration (T header) of all its one-hop neighbors’ slots.
Locations of those Tx-slots are learned simply by listening to the transmissions
flom all neighbors. While receiving a header flom a neighbor, if the
data-present bit is found to be set, the receiving node will remain awake.
Otherwise, it goes to sleep after the header is received.

3. During its Interrupt sub-slot immediately after the Tx-slot. During this time, a
node waits in receive mode for notification interrupts flom any newly joined
neighbor nodes.

In transient state, when a node receives a notification interrupt flom one of its
newly joined one-hop neighbors, it remains awake for W number of flames
(described in section 3.3.2.9) in order to learn about the location of the new node’s
self-chosen transmission slot.
3.3.2.5 Protocol Overview

The key strategy is that if a newly joined node does not immediately find a
feasible Tx-slot, it chooses a non-feasible slot defined as follows. The slot is chosen
right in the middle of the slots of its l-hop neighbor pair which has the largest slot
distance among all possible neighbor pairs. Upon choosing a slot, the new node
starts transmitting periodically once per framez. This action may first cause (the

middle point may satisfy few neighbors’ constraints, but not all of them) all its l-hop

 

In ISOMAC-A, upon entering the network, a node arbitrarily picks its own frame starting point.

34

neighbors to be forced out of their Stable (see Section 3.3.2.9) allocation state. But
then an iterative slot movement is used for all the nodes in the neighborhood for
incrementally attaining steady allocation state for all the neighbors including the
perturbing new node. During this iteration, each node attempts to move its slot in the

middle of all its neighbors’ slot locations.

 

 

 

 

 

 

 

tAB<B.T,tBC<B.T,tCD<B.T,tDE<B.T

B: Bitmap Vector Length T : Tx-Slot Duration

 

 

 

Figure 3.4: Iterative slot movement for convergence
Consider the 5-node topology in Figure 3.4, in which the step-l of the allocation
depicts Tx-slots chosen by nodes A, B, D and E before node C enters the network.
With the allocation in step-1, t A B , the minimum temporal distance between A’s and
B’s slots, is smaller than the quantityer, and therefore it satisfies the bitmap
constraint as stated in Section 3.3.2.2. Since their slots do not collide with any of

their l-hop and 2-hop neighbors, the timing constraint is also satisfied. As a result,

35

nodes A and B are in a stable allocation state. The same applies to nodes D and E. To
summarize, at Step-l both the sub-networks A-B and C-D are at a steady allocation
state.

Upon entering the network, node C learns about the slot locations of its l-hop
neighbors B and D flom their periodic transmissions, and the 2-hop neighbors (A
and B) through B’s and D’s bitmaps. Since the value of t B D is larger than
2 x B x r , C cannot find a slot that will satisfy the bitmap constraint of being able to
be representing both B’s and D’s slots in C’s own bitmap vector. As shown in step-2,

unable to find a feasible slot, C chooses a collision flee but non bitmap-constraint

compliant slot that is right in the middle of B’s and D’s slot locations. Since 1 BC

and ’CD in step-2 are both larger thaan t , now none of the nodes B, C and D

can satisfy the bitmap constraint, thus their allocations become unstable. Nodes A
and E however still remain stable.

Responding to its instability, in step-3 B moves its slot right in the middle of those
of its l-hop neighbors A and C. The goal of B is that by reducing the slot separation
t BC it will be able to satisfy the bitmap constraint and make its own allocation
stable. Following the same strategy, node D moves its slot between those of its own
l-hop neighbors C and E. Node C does not move since it was already in the middle
of its l-hop neighbors B and D. After these moves, the slot separations between any
node and all its l-hop neighbors become smaller than B x z' , and therefore the
allocation in Step-3 is considered to be stable because of its compliance with both

the timing and bitmap constraints. In case the bitmap constraint was not satisfied for

36

all nodes in Step-3, the same process of slot movement would have to continue till
the allocation stabilizes.

To summarize, the core idea is to let each node iteratively move its slot near the
middle of its neighbors’ slots until an allocation pattern which is stable for all nodes
in the neighborhood emerges. The idea of middle is chosen because in the absence of
time synchronization, the collective middle provides a common reference for all
nodes in the neighborhood.
3.3.2.6 Logic for Slot Selection in ISOMA C-A

In a more general situation (compared to the one in Figure 3.4), when a node has
a large number of neighbors, and no feasible slot is available, middle point
computations and slot selections involve the following steps:

1. Compute the relative slot distances between all different neighbor pairs. For a
given neighbor pair, their relative slot distance is computed by choosing the
minimum slot separation between them,

2. Identify the middle point (Tmiddle) of slots of the neighbor pair that has the
maximum relative distance, and

3. Choose a feasible slot randomly (uniform distribution) flom the range Tmt‘ddle
-Br to T middle +Br, where B is the bitmap vector length. If no feasible slot is
available in this range, in each subsequent flame the range is extended using a
binary exponential strategy until a feasible slot is available.

Steps 1 and 2 take care of flame asynchrony, and step 3 minimizes collision

probability by introducing stochasticity when two or more unstable nodes end up

37

computing the same middle point as their new slot choices. If a collision still
happens, the mechanism for its detection and resolution is presented in Section ‘
3.3.2.7.

Although in the example in Figure 3.4, a sequential approach is shown for
explanation purpose, no such sequence of slot movement is enforced in ISOMA C.
Nodes move asynchronously and independently and therefore multiple nodes can
end up colliding with each other because of their slot movement to overlapping time
regions. In the actual implementation, we implement a series of randomization both
in terms of the time and target location of the slot movement for minimizing such
collisions.

From the sleep-wake standpoint, every time a node moves its slot, it remains
completely awake during W number of flames. This is to make sure that the node
monitors the activity in the neighborhood for W flames based on which it will decide
if its own allocation is still unstable or it has become stable. In our implementation
typical value of Wwas in the range of 3 to 5.
3.3.2.7 Collision Handling

During transience, caused by a topology change, if nodes P and Q in Figure 3.3
choose overlapping transmission slots, 3 hidden collision will take place at node R.
Since R is not able to listen to P’s and Q’s transmissions due to the collision, it will
simply indicate those two overlapping slots to be empty (‘0’) in its own bitmap.
Upon receiving R’s bitmap, node P looks for its own location in R’s bitmap to see if

P’s transmission was successfully heard by R or not. A ‘0’ corresponding to P’s

38

Tx-slot will indicate that there was a collision or packet corruption due to channel
error. If the situation persists for a preset number of flames then node P will attempt
to move its own Tx-slot to resolve the collision. Node Q will also behave similarly.

To summarize, a node is required. to be able to see its own slot in the bitmaps of
all its l-hop neighbors. Otherwise, a collision or channel error is said to have
occurred. This way, the bitmaps in ISOMAC are used as an implicit
acknowledgement technique for detecting hidden collisions.
3.3.2.8 Role of Interrupt Sub-slot

When a new node joins a neighborhood and starts transmitting on a newly
chosen Tx-slot, there is no way for the existing neighbors to know about this new
node and its transmission slot. Without being able to get this information, all
one-hop neighbors of the new node would sleep during its transmission slot and miss
the data packets. Also, without knowing its existence, the neighbors will not be able
to represent this new node’s Tx-slot in their bitmap vector.

To address this, immediately following its transmission slot, a node remains
awake for a small interrupt-subslot (of duration Tint errupt ). Before the new node
chooses a slot, it sends interrupt transmissions during the interrupt sub-slots of all its
neighbors. Since all nodes remain awake during their individual interrupt sub-slots,
they can receive this interrupt transmission and know that there is a new node in the
vicinity. After a neighbor is interrupted, it remains awake for W flames to learn about
the Tx-slot location of the newly joined neighbor.

3.3.2.9 Protocol State Machine

39

The state machine of the ISOMAC protocol is presented in Figure 3.5. Upon joining
the network, a new node arbitrarily chooses its own flame boundaries and enters a

Listen state that lasts for W flames to learn about the Tx-slot locations of all its

 

l-hop and 2-hop neighbors. Locations of l-hop neighbors are learnt flom their
direct transmissions and the locations of 2—hop neighbors are learnt flom the bitmap
vectors transmitted by the l-hop neighbors. After this initial listening duration, the
new node chooses a feasible slot using the logic described in Section 3.3.2.6. At this
point, it also interrupts all its l-hop neighbors so that the neighbors wake up and
remain awake for W flames to learn about the slot location of the new node. During

the Listen state a new node needs to remain awake continuously.

 

 
 
  
 

   
    
  

Listen
Continually

 

New node 'oin ‘ W’ frames

are ROI OVCI'

  
  
 
    
    
 

Choose a slot and
interrupt neighbors

 
 

 

 

‘ W’ flames are over and
bitmap constraint is satisfied Bitmap constraint
satisfied

Stable
Regular Sleep
Schedule

   
     
   
 

       
 

Evaluate
Continually
Awake

Interrupted by

._ I '4').

    
  
  

Bitmap constraint not satisfied

 

 

‘ W’ flames are over for W consecutive flames

and bitmap constraint _ . OR .

is not satisfied A collisron is detected dunng a
skipped slot

Choose a slot and

interrupt neighbors @0053 a .5101 and
interrupt neighbors

 

 

 

 

 

 

 

 

Figure 3.5: State machine for ISOMAC

40

After choosing its own slot, the new node enters an Evaluate state which lasts for
W flames. The node expects that during these flames, allocation should stabilize in
the neighborhood. After W flames are over, if the node finds that its bitmap
constraint is satisfied then it simply gets to the Stable state and starts following the
regular sleep-wake schedule. Otherwise, it assumes that its chosen slot could not
reach a steady state. In that case, the node chooses a new feasible slot, interrupts all
its neighbors and re-enters the Evaluate state. Since during the Evaluate state it is
necessary that all l-hop neighbors should be able to listen to the node, it remains
awake during the entire state.

While in the Stable state, a node continuously monitors the bitmaps received
flom all its l-hop neighbors to detect any allocation instability including hidden
collisions. If instability is detected through unsatisfied bitmap constraint for W
consecutive flames, the node chooses a new slot, interrupts its neighbors and transits
to the Evaluate state, waiting to stabilize allocation in the neighborhood. Another
reason for a node to transit from Stable to Evaluate state is when it is interrupted by
one of its l-hop neighbors. Such an event indicates that the interrupting node has
chosen a new slot, either because it has joined the network or there is allocation
instability caused by channel error or another newly joined node. Upon receiving an
interruption, the node does not change its Tx-slot but it simply transits to the
Evaluate state to monitor the transient activity before it can come back to the Stable
state.

In the protocol state machine, both Listen and Evaluate are transient states and

41

they occur only during topology changes. In majority of the time a node remains in
the Stable state with a very tight energy schedule as outlined in Section 3.3.2.4. As a
result, although the energy expenditure is significantly more in the first two states,
overall, ISOMAC is very energy efficient.

In ISOMAC, a special type of collision can happen in extremely rare situations
when all nodes in the network happened to have entered the network exactly at the
same time and they have chosen the same slot. In such a case, none of the nodes are
able to detect the collision. To exit flom this situation, a node is programmed to
randomly skip one of its transmission slots once in a large number of flames, so that
during the skipped slot it can listen if any of its neighbors is alsotransmitting during
the same Tx-slot. If such a situation is detected, the node simply chooses a new
feasible slot, interrupts its neighbors and transitions to the Evaluate state. Although
extremely rare, this type of collision is slightly more flequent for the synchronous
ISOMAC because of its common flame timing across the nodes.

3.3.3 Synchronous ISOMAC (ISOMA 05)

Network time synchronization can be leveraged in ISOMAC by using the
following two mechanisms. First, with a common notion of flame and synchronized
slot boundaries across all nodes, the bitmaps can be used more efficiently so that a
single bit is able to represent only a single Tx-slot, as opposed to two slots as in
ISOMA C-A. As a result, a B-bit vector in ISOMAC-S can represent the slot locations
of B neighbors as opposed 2B neighbors as in ISOMAC-A.

Second, time synchronization offers a significant simplification in the iterative

42

slot movement strategy compared to that in ISOMA CA. In ISOMA C-A, each node
attempts to move its Tx-slot towards the collective temporal midpoint of all its
neighbors’ slots. The midpoint was chosen because in the absence of common
flames it provided a shared temporal target for all nodes in a neighborhood. In
ISOMAC-S, since all nodes share the same flame, this midpoint approach is not
needed. Instead, nodes can move their slots towards the beginning of the common
flame, which now acts as the shared temporal target for all nodes in a neighborhood.

If a feasible slot is not found, the following steps are used in ISOMA C-S for new
slot selection.

1. Identify the neighbor which has the earliest slot in the flame. Say the location of

that slot is at time T early:

2. Choose a slot randomly (uniform distribution) flom the range -Br/2 to

T early

T early

+Br/2, where B is the bitmap vector length. If the feasible slot is not
found, like in ISOMA CA, a binary exponential range increment is performed
till a feasible slot is found. Note that the range should not be extended beyond
the flame start boundary.

Just like in the asynchronous case (Section 3.3.2), these two steps are repeated
iteratively for all nodes in the neighborhood till a collective steady state is attained
for all the neighbors. Although this slot selection logic for ISOMAC-S is different
flom that of ISOMA C-A (see Section 3.3.2.6), its core protocol logic is still the same

as that shown in Figure 3.5.

3.4 Model for Frame Size Dimensioning and Energy Consumption

43

The bounds of flame size F (in number of slots) can be computed using the
following model. For fixed packet duration of 2' seconds (header and data), the
channel capacity can be expressed as l/ 2' packets per second (PPS). If M represents
the maximum number of combined l-hop and. 2-hop neighbors, then the wireless

bandwidth in a neighborhood is shared by (M+l) nodes. Therefore, the maximum
data rate that can be allocated to each node is: Amax =1/(r(M + 1)) (3.1).

Let the actual allocated data rate be 11

01106“ PPS per node {1113241101106}: Am)

and the flame duration be T frame seconds. For an allocation strategy of one slot

per node per flame, Tfi-ame = “ lalloc

and sinceTfmme =Fx 2', one can write
F =1/(rx/lalloc).... (3.2).

The lower bound of F is decided by the bitmap constraints. For ISOMAC-S,
since a node’s bitmap is required to represent the slots of all its N neighbors, the
length of bitmap vector: B 2 N . Also, the number of slots represented by a bitmap
cannot be larger than the flame size E Therefore,F 2 Bz N . To guarantee the
timing constraint: F 2 M +1 (3.3).

For ISOMAC-A, since each neighbor’s slot can occupy at most two bits in the
bitmap, B 2 2N . Also, since each bit may correspond to at most two slot locations,
F 228. Combing these two: F 24N (3.4). Combining those two inequalities,
the lower bound of flame size for asynchronous ISOMAC is: F 2 max(M + 1,4N)
(3.5). For the synchronous ISOMAC, the lower bound of F can be written as:

F2max(M +1,N).... (3.6). The upper bound in Equation 3.2 and the lower

bounds in Equations 3.3 and 3.4 define the feasible region for F to be chosen flom.

Note that this feasible region is defined by the packet duration, allocated rate per
node, and the network density in terms of the maximum number of combined l-hop
and 2-hop neighbors.

Like in any standard TDMA protocol, the average MAC delay is: FXT/Z

(3.7), which increases with F. As for energy consumption in ISOMAC-S, let

T

awake (in see.) he the total time that a node needs to be awake during a second for

the following operations.

Header and Data Transmission: Uptime for such transmissions is A x r see, where
the actual data rate is A PPS.

Header and Dag Reception: Since a node is required to receive data transmissions

for all its N neighbors, the corresponding wake time is A. x r x N sec.

Header-only Tmsmission: Since xi can be less than 11 the number of

alloc ,

header-only transmissions in a second is (,1 A) . Substituting

alloc _

It

alloc =l/Fr the uptime for header-only transmission is (l/F r-A)hr seconds,

where h is the ratio T header /r .

Header-only Reception: To receive a header-only transmission, a node needs to be
awake for header duration. Total uptime for such receptions flom N neighbors is
(1/Fr—2)th seconds.

Interrupt Slot: Each interrupt slot lasts for hx 2' second, during which a node needs
to remain awake. Since there is only one interrupt slot (immediately following its
transmission slot; see Figure 3.1) per flame for it, and there are l/Frnumber of

flames per second, the node needs to remain awake for(1/Fr)hr seconds out of a full

45

second. This additional wake-time, however, is not necessary when the node’s
interrupt slot is overlapped with any one of its neighbors’ transmission slots. In
ISOMAC-S, The probability of that happening is N/B, since at steady state, all N
neighbors should be represented within B slots around this node’s own transmission
slot. Therefore, the wake duration due to interrupt slots is (1 — N / B) x (l/F t')x h r.

Adding all five components, in ISOMAC-S, a node needs to remain awake for:
l h N
T . =xir1+N + ——/t hr 1+N +— 1——
awake ( ) [Fr J ( ) F[ B) (3.8)

seconds out of a full second. This quantity represents ISOMAC-S’s energy
expenditure for the duty cycle of a node’s operation.

In case of ISOMAC-A, all the energy components except the one due to the
Interrupt Slots are the same as those in ISOMAC-S. Since in ISOMAC-A, a B-bit
bitmap vector flom a node represents the slots of 2B neighbors, the probability of its
Interrupt Slot being overlapped with at least one neighbor is h N/23, When an
overlap does not occur (probabilityz1—hN/23), the wake time as in ISOMAC-S is
h/F.When an overlap does occur, the wake time due to the Interrupt Slot may or
may not be there depending on the relative slot timings of this node and its neighbors.

So the average wake duration is h/2F. Combining these with the wake up

components for Header and Data Transmission, Header-only Transmission, and

Header-only Reception, the expression for T awa k e in case of ISOMA GA is:
l hN h hN
T =Ar1+N+ ——/l hr1+ +1———+-——x— 39

Equations 3.6 and 3.7 demonstrate that the energy expenditure increases with

46

higher data rate, network density, and packet header duration. However, nodes are
more energy efficient with larger flame size, which inflates the MAC delay (see
Equation 3.5). This clearly indicates the delay-energy trade off in ISOMA C.

As for dimensioning the flame size F, the first step is to determine its feasible
range using Equations 3.2, 3.3 and 3.4. The next step will be to choose an
appropriate value within the feasible range for striking the right balance between the
allowable MAC delay and acceptable energy efficiency for specific applications.

Note that the bitmap size is upper bounded by the flame size, which in turn is
decided by the network density (a derivative of M). Therefore, successful
dimensioning of these parameters depends on a priori knowledge about the
maximum network degree of a target network. While this is a key assumption for
ISOMA C, it is important to note that for any distributed TDMA protocol [23, 24] the
flame size needs to be dimensioned based on the network density or degree.

3.5 Multi-slot ISOMAC for Variable Traffic ’

The ISOMAC protocol logic can be extended flom is basic “one slot per flame”
mode to more general traffic scenarios in which multiple slots may have to be
assigned to individual nodes.

Following the basic ISOMAC process as described in Sections 3.3.2 and 3.3.3,
each node first assigns itself a periodic basic slot. The basic slot is used for sending a
bitmap with information about all the node’s neighbors. Subsequently, depending on
is traffic requirements, a node can grab periodic additional slots based on the timing

information received via direct receptions and via the bitmaps received flom the

47

basic slots of its neighbors. Transmissions on these additional slots do not include
bitmaps because the basic slots are already used for this purpose. The interrupt
process for the additional slots is the same as that for the basic slots.

When a node requires more bandwidth it may grab additional slots using the
process described above. When the slot is no longer required, the node stops
transmitting in the slot so that it becomes available for other nodes in the
neighborhood to choose, when they require additional network bandwidth. Also,
when a neighbor does not hear a transmission on a slot for W flames (see state
machine in Figure 3.5) it stops waking up on that slot any more to conserve energy.

If the nodal degree is N, the maximum number of two-hop neighbors per node is

N N . If each node maintains S slots (including the basic slot), then there must be

SxNN number of slots in one flame. This expression indicates the capacity

requirement of multi-slot ISOMAC protocol.

Multi-slot allocation is feasible for both ISOMA GA and ISOMAC-S. Also, there
is no restriction as all nodes should have the same number of additional slots. Each
node must have a basic slot, and a number of optional additional slots based on its
own capacity need and the availability in the local neighborhood.

Although the protocol can handle variable traffic, it is mandatory for a node to
own a slot and send a header-only transmission even when there is a no packet to be
transmitted. While the energy expense due to this header transmission can be
reduced by using a small header size, the bandwidth penalty of owning the slot

cannot be avoided. This is the basic cost associated with any in-band approach. The

48

advantage of this, however, is faster slot reorganization, especially in the presence of
energy aware node sleeping which generally make a protocol less reactive.
3.6 Performance

ISOMAC has been simulated using a C-based event-driven sensor network simulator.

 

 

 

 

 

 

 

 

 

 

 

Network Size (number of nodes) 100
Network density (average number of 5
neighbors)
Frame size (number of slots) 100
Bitmap size 24
Packet error rate 0%
State evaluation time W (flames) 3
Slot duration (millisecond) 5
Header duration (percentage of slot duration) 2.5%
Node deployment mode Arbitary
Data rate (percentage of xalloc) 10%
ISOMAC protocol version ISOMAC-A

 

 

 

 

Table 3.1: Baseline system parameters in simulation

3.6.1 Experimental Parameters

We implement ISOMAC on 100 nodes that are randomly distributed within a
rectangular sensor field. While keeping the sensor transmission range fixed at 40m,
the sensor field dimensions are changed for altering the sensor density. Following the
specification in [56], we choose a radio data rate of 25.6 Kbps and fixed packet
duration of 5ms, which is also the TDMA slot duration. Unless stated otherwise, for
all experiments, the flame duration is chosen to be 100 slots and a packet header is
assumed to occupy 2.5% of a Tx-slot. As for data model, each sensor node is

allowed to generate traffic at a maximum rate of one packet per flame. All reported

49

performance numbers are based on local MAC layer traffic. No end-to-end routing is

considered. Unless stated otherwise, all results correspond to the asynchronous

version of the ISOMA C.

3.6.2 Protocol Convergence

A network is considered to be in a stable state when all its nodes are in the Stable

state as shown in Figure 3.5. The convergence time is defined as the interval flom

when a new node is added to a stable network to when the network again becomes

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

stable.
31 , 55 l + n = 5: experiment
Convergence . 50 J -_ - _ --- +"=5: model
Time s 9 frames».— ""' n = 3‘ expenment
3o ""- ~ . 1 - ._ y +n=3: model
g 7545" “7' "'7’” -—n=1:experiment
. E
g g 40 -
29 ~
2 E
g l—35-~~~~-
O
«r
g 28 "' 9 30 “
3 2
8 5 25 ~
‘3 o
E 27 1 _§
0, 20 -—
2 i
< 15 —
26 ..
1o --
25 + i x 5
0 5 10 15 20 6 8 10 12 14 16 18 20
Time (frame count) Bitmap Length
(a) Definition of protocol convergence (b) Convergence speed in a linear
network (experiment and model)

 

 

Figure 3.6: Convergence characteristics for ISOMAC-A

The concept is illustrated using the experimental results in Figure 3.6:a. It is

shown that a new node is added in a stable network of 29 nodes at the beginning of

50

 

the 6‘11 flame. Addition of this 301’ node causes temporary instability by forcing three
nodes out of their ISOMAC Stable states. But eventually, the network converges by
the end of the 15th flame. Therefore, the convergence time is registered to be 9
flames.

To understand the convergence characteristics, we first experiment with a linear
network as shown in Figure 3.4. It is assumed that before a new node is added, two
disconnected sub networks, each with n nodes, are already in allocation steady sates.
The timing separation between these two disconnected sub networks is 48 slots, and
the inter-node timing separation within each sub network is 3 slots. In the scenario
depicted in Figure 3.4, nodes A, B, D and E form two physically disconnected, yet
stable allocation clusters (each with n = 2), before node C is added in such a way that
it physically connects the two disconnected sub networks. As explained in the Figure,
node C merges the two existing stable allocation clusters to form a large stable
cluster with all 5 nodes. We conduct experiments with various existing cluster sizes
(different values of n) and measure the protocol convergence time after adding the
cluster-joining node in the middle.

Convergence in such linear networks for different bitmap length is reported in
Figure 3.6:b. For each data point, the average convergence time is computed flom
500 experiments as outlined above3. Experimental results are compared with those

obtained flom an analytical model presented in Appendix A. As expected, the

 

3
Unless stated otherwise, all results reported in this section correspond to an average taken flom 500

experiments.

51

convergence latency increases with network size since more ISOMAC iterations are
needed to merge larger allocation clusters (see Figure 3.4 and is explanations in
Section 3.3.2.5). Therefore, convergence in larger networks is slower in general.

Note that for larger networks (n = 3, 5), convergence is faster with larger bitmap
vectors. This is because with larger bitmap vectors, the allocation is less restrictive
due to the bitmap constraint, as explained in Section 3.3.2.2. As a result, fewer slot
movements are necessary before network-wide allocation steady states are found.
The result is faster convergence.

The final point observed flom Figure 3.6:b, is that the experimental results match
quite closely with those obtained flom the analytical model. The slight differences at
smaller bitmaps are due to a few restrictive assumptions in the model and will be
explained in Appendix A.

Convergence of ISOMA GA in a lOO-node arbitrary mesh topology is depicted in
Figure 3.7. In this experiment, 100 sensor nodes are sequentially added at arbitrary
locations in a rectangular sensor field. An example convergence trace is shown in
Figure 3.7:a, in which the convergence latency after each node addition is shown for
the first 50 nodes. Results for the last 50 nodes were not shown for the sake of
maintaining clarity in this graph.

The primary observation in Figure 3.7:a is that with increasing network size the
convergence gets slower, and with larger bitmap vector length the convergence is
faster. These indicate that the results form the model for linear networks, as shown in

Figure 3.6:b, extend for more realistic arbitrary mesh networks. Since locations of

52

added nodes are arbitrary, for some nodes they can simply become a new sub
network, or a part of only one existing sub network. After addition of such nodes,
convergences are fast and are represented by small latencies mostly fewer than 5
flames. However, the large peaks in the convergence trace correspond to scenarios in
which a newly added node is forced to merge two or more disconnected sub
networks as described for a linear network in Section 3.3.2.5. Observe that with
larger bitmap vectors, there are fewer such allocation latency peaks compared to that

with shorter vectors.

 

 

15 fl . 9 . . .
+ Bitmap Length: 24 I +Asynch; Density: 4
+ 43 . +Asynch; Density. 5
+Asynch; Density: 6 .
8- +chh;Densily:5 ----.E--.

 

 

 

 

 

 

 

' l

I

I
7-__"“‘Y"‘S>‘“"_

l

l

l

—l
03
1r
l
l
l

)

 

 

A
‘

l

l

l

l

l

l

l

'l

l

 

N
l

  

 

Allocation Convergence Time (frames
(0
Allocation Convergence Time (frames)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Added Node Bitmap Length
(a) Convergence trace with arbitrary node (b) Effects of bitmap vector length on
addition allocation convergence time

 

 

 

Figure 3.7: Convergence in arbitrary mesh networks
The efl'ect of network density (average number of neighbors N) on convergence

latency is shown in Figure 3.7:b. In this experiment, all 100 nodes are first allowed

53

to join the network and the allocation convergence latency is measured after each
node is added. Finally, the convergence average for all 100 nodes was computed.
These experiments were carried out for 500 times to compute the final average that
is reported in Figure 3.7:b.

With higher density, since more iterations are needed to get stability in a
neighborhood, the convergence latency tends to be larger. In fact, if the bitmap
vector is not sufficiently long then a convergence may not be feasible. In these
experiments with ISOMAC-A, no convergence was found when the bitmap length
was 16 for network density 5, and when the bitmap lengths were 16 and 24 for
network density 6. As shown in Figure 3.7:b, although it is evident that ISOMAC-S
performs better than ISOMA CA, the average gain is never more than just one flame
duration. This implies that expensive network time synchronization can be avoided
within a sensor network running ISOMA C.

3.6.3 Sensor Deployment

In a sensor field, nodes can be added either as an Arbitrary Deployment (as in
Figure 3.7:a), or they can be added in a preplanned way so that no disconnected sub
networks are formed during the entire course of deployment. The latter case, which
we term as Connected Deployment, a newly added node is always placed in such a
way so that it can be a part of an existing connected graph. This would correspond to
a sensor deployment starting flom one side of the sensor field and then gradually
approaching to the other side of the field.

Convergence characteristics for both modes of deployments are reported in

54

Figure 3.8:a. For the Connected Deployment, since the newly added nodes are never
forced to merge multiple existing allocation clusters, the convergence latency peaks
(see Figure 3.7:a) never happen. This explains why the convergences in this
deployment mode are always faster than those in Arbitrary Deployment mode.
This trend holds across all bitmap lengths and network density values that we have
experimented with. These results imply that whenever possible, a controlled sensor

deployment is desirable flom the convergence standpoint.

 

 

 

 

8 T 66 T r r T
+ Arbitrary Deployment (density: 4) ' ’ ’
+ Arbitrary Deploymnt (desnity: 5) , 64 j j _,
+ Connected Deployment (density: 4)
-I— Connected Deployment (density: 5)

 

 

 

 

 

62*

.“
or
1

CD
0
l

    

 

Allocation Convergence Time (frames)
0)
Percent of Occupied Frame
OI
co

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

56
5.5 - , g y
54 - -- .. ,
+TDMA. Densrty: 6
5 - 1 +ISOMAC. Density. 6
52 ‘ ” +TDMA. Density 5 '
; +lSOMAC.Density.5
4.5 . 50 - +TDMA. Densitw4
. ’ -e—lSOMAC.Densitm4
4 48 r ; a .‘ . ;
15 25 35 45 15 20 25 30 35 4 45 50
Bitmap Length l Bitmap Length
(a) Effects of sensor deployment pattern (b) Spatial reuse of ISOMAC compared to
on convergence time non-constrained TDMA protocols

 

 

 

Figure 3.8: Effects of sensor deployment pattern and spatial reuse in ISOMAC
3.6.4 Spatial Channel Reuse

Distributed TDMA protocols are expected to achieve spatial channel reuse [55],
which helps increasing the supported traffic for a given number of sensor nodes and

channel bandwidth. We measure spatial reuse by computing the percentage of a

55

TDMA flame that is used by allocated Tx-slots. With 100 nodes in the field and our
chosen flame size of 100 slots, if there was no spatial reuse then 100% of the flame
will be occupied by the Tx-slots allocated to 100 nodes. With spatial reuse, however,
because of overlapped Tx-slots, less than 100% of the flame will be occupied.
Therefore, the lower the flame occupancy, the better the spatial reuse.

A comparison of percentage flame occupancy between ISOMAC and other
distributed TDMA protocols such as TDMA-W [24] is presented in Figure 3.8:b. The
main allocation difference between the two protocols is in the following. While slot
allocations in ISOMAC and regular TDMA protocols are constrained by the timing
constraint (see Section 3.3.2.1), ISOMAC allocations are additionally restricted by
the bitmap constraint. As a result, the Tx-slots of neighbor nodes in ISOMAC tend
to cluster together. This clustering gives rise to higher slot overlapping, which in turn
delivers lower flame occupancy compared to regular TDMA cases.

Since with smaller bitmap vectors the degree of clustering is higher, the flame
occupancy numbers are smaller. With our chosen flame duration of 100 slots, when
the bitmap vector size is increased to 50, the cluster width for ISOMAC-A
(asynchronous case) becomes 100, which is the entire flame. At this point, the effect
of bitmap constraint vanishes, and therefore, ISOMACs spatial reuse performance
becomes the same as that of regular TDMA protocols.

To summarize, due to its bitmap constraint, ISOMAC provides inherently better
spatial reuse compared to unconstrained distributed T'DMA protocols such as

TDMA-W. However, this improvement is traded for slower allocation convergence,

56

especially for smaller bitmap vectors.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.2 I ; 100.5 e
6 ‘ j 100 , '
$5.3 - c | ‘ 1 1
g §9954 1 -
g 8 I i
255‘ 3 99‘ _ -_ “l
i: E .
g 5.4 « 5,3, :
o g 98.5 ~ ——————————— ,L ————————— F’
2° , .
E 5.2 ‘ 8 l
8 3 93 . ____________ L ........... L—
C 2 |
8 5 ‘ ’5 :
g g97.5-~-———~-——-——‘~ --------- -
2 4.8 4 1
97 1 ------------ f ---------- n ~
4.6 -~
+ 8% Packet Error Rate: 8%J
-o- 12% 96.5 r
4-4 i . o 50 100
20 30 40 50
Bitmap Length Time (frame court)
(a) Effects of channel encr on (b) Convergence trace depicting
allocation convergence speed perturbation due to channel errors

 

 

 

Figure 3.9: Eflecs of channel error on protocol convergence

3.6.5 Channel Errors

While a node is in the Stable state (see Figure 3.5), if it does not receive implicit
in-band acknowledgements flom all its neighbors for more than W flames, the node
transits flom Stable to Evaluate state. In the presence of channel errors, excessive
packet header (and bitmap) corruption can cause protocol instability due to such
undesirable transitions state transitions flom Stable to Evaluate. This impacts both
transient and steady state operations of a network.

The impact of channel errors on convergence for the lOO-node network is reported

in Figure 3.9:a. Observe that although the convergence is slower at higher channel

57

errors, the actual increase in latency is just less than one flame for all bitmap lengths
and packet error rates up to 12%. This is due to the threshold parameter ‘ W’ used in
the protocol state machine. As a baseline, we use W to be 3, which means at least
three consecutive packet headers flom a neighbor has to be corrupted before a node
transits flom Stable to Evaluate state. Larger W will make the performance more

insensitive to the channel error, but at the expense of slower recovery times.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.E+07 . . , 4
-e- Evaluate Time (W): 3 frames
+ 5 frames
‘ ' ' ; 3.5
A 1.E+06 . . A
a)
0
f s
g '5 3 _
e 6‘
g 1.E+05 . 5;
g 3
b
(53 2 2.5
‘6 8
g 1.E+04 * g
C
E s 2 -
0 8
s .o
< ’ —
1.E+03 + <— . <
1.5 4
1 .E+02 I V T I I 1 n! r l r i
0 2 4 6 8 10 12 o 2 4 6 8 10 12
Packet Error Rate (96) Packet Error Rate (%)
(a) Effects of channel error on allocation (b) Effects of channel error on allocation
stability in steady state recovery time

 

Figure 3.10: Stability and allocation recovery under varying packet error rates
The effects of channel error in network steady state are shown in Figure 3.9:b,
which depicts the number of nodes in Stable state. These results are shown for a
packet error rate of 8%.
The steady state performance from an individual node’s perspective is depicted

in Figure 3.10. The bitmap vector length for these experiments was chosen to be 24.

58

The average interval between two consecutive transitions from Stable to Evaluate is
shown in Figure 3.10:a. For example, with the value of W chosen as 3, a node
remains at the Stable state for an average duration of 4000 frames for a packet error
rate of 4%. Also, as explained in the previous paragraph, a larger W helps a node to

remain unperturbed for longer duration.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.4 F I f 1 I
o . . . I a
FV—__-a-§gs::;rame-:gmgSign?“ +ISOMACSimulation
-It— -8 rame: 0 O l
20 -- -E-100-slot Frame: lSOMAC Simulation 3 35 +'S_?“_‘§C_“f°_flf' _ : _;_ _ _ _
—i—100-slot Frame: lSOMAC Model ' ‘" ; } ; : g
A -—1SO-slot Frame: lSOMAC Simulation ... ‘ ‘ l
g -e-150-elot Frame: ISOMAC Model 3
315 j» +50-slotFramezTDMA-W Simulation 1; 3-3 ‘" " "
‘6 +100-slot Frame: TDMA-W Simulation '6
ES —-150-clot Frame: TDMA-W Simdation ES 5 .
c ._ . > c 3.25 -- . _. «
3 t . , ; 3
g L F 50am ‘ g
0 _---_.-§__-_‘___ ' _____ 0
“’10 é ' \ o 3.2 ~
.5 5 l l l g
2 : , a
o TDMA-W F1 10° '0“ o
g g 3.15 . -
z 1 i .. i i z
54~-- -+-- :--‘-+--—-:. ---
l ' l A.
I 3.1 .
1‘ .- J - i F: 150 SIOtS - .. ,
- .1. ' a ; i i ’. I i
0 ‘ § 4 ISOM'AC : I 3.05 r r T l I
o 0.2 0.4 05 0.3 1 0% 2% 4% 6% 8% 10% 12%
Data Rate (packets/frame) Header Duration (% of slot duration)
(3) Energy consumption in TDMA-W and (b) Effects of packet header duration on
ISOMAC energy consumption in ISOMAC

 

 

Figure 3.11 : Energy performance of TDMA-W and ISOMAC

The non-linear effect in Figure 3.10:a can be explained as follows. WithE as the

packet error rate, the probability of a node to be forced out of the Stable state can be

written asEW , which represents the probability of corruption of W consecutive

packets from any one of its neighbors. For N neighbors, the probability can be

written as N xEW . This expression explains the non-linear degradation of steady

state performance with packet error rate, as shown in Figure 3.1023.

59

Once a node is forced out of stability due to channel errors, it waits for a transition
back to the Stable state till it receives W consecutive successful headers from all its
one-hop neighbors. We define this time as the allocation recovery latency, which is
reported in Figure 3.102b. As expected, the recovery latency is larger with higher
channel errors. Observe that for packet error rates up to 10%, the recovery time is
less than 4 frames’ duration, which is somewhat smaller than the lowest convergence
latency, as depicted in Figures 3.7 and 3.8. Based on the performance reported in
Figures 3.9 and 3.10, it appears that although ISOMAC is an in-band control
protocol it can tolerate moderate packet errors up to 10% without being excessively
affected in terms of its convergence and recovery latencies.

3.6.6 Energy Consumption

Steady state energy consumption is represented by the fraction of frame duration that
a node’s wireless interface is required to remain up. Experimental and analytical
energy results (see Equation 3.7 in Section 3.4) for the asynchronous ISOMAC and
TDMA-W [24] are presented in Figure 3.11. As shown in Figure 3.11:a, for ISOMAC
with higher data rates, since more number of full packets are needed to be
transmitted and received as opposed to header-only transactions, the overall energy
consumption is larger. It also indicates that for a given data rate, if the frame size
increases, a node will have to remain up less frequently, and therefore the energy
expenditure reduces. Observe that the experimental and the model data for ISOMAC
from Equation 3.7 are in complete agreement. As shown in Figure 3. l l :a, TDMA-W

has a relatively higher energy overhead, compared to ISOMAC — especially at lower

60

rates. In each flame, a node must remain awake during its wake-up slot even if it is
not transmitting or receiving during that flame. This implies that a node must expend
one full data slot worth of energy in each flame irrespective of its communication
activities. This affects TDMA-W’s energy efficiency more at lower rates, since more
often a node remains awake during its wake-up slot without any Tx/Rx activities.
With increasing data rates, the wake-up slots start getting utilized more often and
that is why the energy expenditure for TDMA-W becomes saturated at higher rates.

At steady state, even in the absence of data to be transmitted, a node in ISOMAC
requires to transmit a packet header with its bitmap during its allocated Tx-slot in
each flame. While this is essential for all its neighbors to maintain their allocation
steady states, these header transmissions consume energy that is not directly related
to sensor data. Figure 3.11:b, characterizes the energy cost with varying packet
header durations as a percentage of the total packet duration. The graph in Figure
3.11:b indicates that an increase in header size flom 2% to 10% of the packet size,
the resulting increase in node up time is less than half a percent. This linear change is
also predicted in the model presented in Equation 3.7. As in Figure 3.112a, the
experimental and the model data are in excellent agreement.

As demonstrated by the results in Section 3.6.5, excessive channel errors in the
in-band bitmap vectors cause temporary transitions from Stable to Evaluate state.
Since a node remains continuously awake in the Evaluate state, these state
transitions increase energy expenditure during the protocol steady state. This effect is

demonstrated in the experimental results shown in Figure 3.12. Since a node has to

61

miss W (chosen to be 3) consecutive headers flom any of its one-hop neighbors
before it departs from the Stable state, at lower error rates such transitions do not
happen very flequently. That is why the energy consumption is somewhat insensitive
to packet error rates up to 6%. When it increases further, we see the increase in
energy expenditure. From these results, it can be concluded that although noisy
channels can worsen the energy efficiency of ISOMA C, the overall impact for packet

error rates of up to 10% is quite within a tolerable range.

 

 

 

 

 

 

 

 

7'5 . ‘ t 1.E+06
+Data Rate: 50% of max EDn'ft: 1 parts per million
7 _ _._ 75% of max , I 0.1 parts per million
+ 100% Of max 1.E+05 ..
6_5_....:._--...-......- < *‘"t

 

1.E+O4 J ,_

1.E+03 4 ~

 

Node Awake Duration (% of frame)
Av. Duration of Stable State (frames)

 

 

 

 

 

 

 

 

 

 

 

 

 

1.E+02 -

4._1.---__ -- _
1.E+01 -. ~'

3 r r T r 1.900 - .

0% 2% 4% 6% 8% 10% 50 100 150
Packet Error Rate ('96) Frame Size (slots)
(a) Eflects of channel error on energy (b) Effects of inter-node clock drift on
consumption allocation stability at steady state

 

Figure 3.12: Effects of channel error on energy, clock drift on allocation stability
3.6.7 Effects 01' Clock Drift
The effects of clock drifl on ISOMACs steady state performance is reported in
Figure 3.12:b. We let each node choose a clock drift based on a given mean value

and 10% variance. The drift direction for an individual node is randomly chosen,

62

either forward with time or backward. The results in Figure 3.12:b are reported as
the average duration of stable state from an individual node’s perspective. The
variance and difl”erence in drift direction cause relative clock drift, which affects the
ISOMAC-A protocol as follows.

Since [$011M C-A relies on local clock for slot and flame timing, the relative drift
can move a node’s transmission slot with respect to those of its neighbors. This can
perturb allocation stability of ISOMAC-A by progressively violating the mapping
between the relative slot locations and the information coded in the corresponding
bitmap vectors. As a result, nodes can transition flom Stable to Evaluate state, thus
affecting the stability of the protocol.

Every time a node enters into the Stable state, the average duration it stays stable
before a transition to Evaluate state due to clock drift is reported in Figure 3.12:b.
The longest possible bitmap vector (flame duration in number of slots) was used for
a network with density 4. As expected, with smaller drift (0.1 ppm as opposed to
lppm) ISOMAC-A demonstrates better stability. For example, with 1 parts per
million drift and frame size 150, a node remains in the Stable state for an average
duration of 10765 frames. With 0.1 ppm drift, the number increases to nearly a
million flames. It can be also observed that larger flames size helps improving the
allocation stability to some extent This is because with larger flame size, the
average time gap between any two neighbors’ slots is also larger, and larger gaps
make the protocol less vulnerable to the undesired slot movement due to the relative

clock drift. To summarize, the ISOMAC-A protocol can be significantly influenced

63

by the clock drift, although for ISOMA C-S (the synchronous version) this is less of a

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

 

 

 

 

 

 

 

 

 

 

problem.
9 - r . . . r . . < , . 1000 ~. .1 1.8
—.— 1 Slot per Frame: Simulation 3 Latency With
. Data Rate Static Allocatlo' n:
8 + -- - -Ci-1 Slot per Frame. Formula - 1‘ 1-slot per Frame r 1.6
-x-2 Slots per Frame: Simulation 100 4* A—l - . 7
7 “ , +2 Slots per Frame: Formula At 1.4
’g‘ A -x- 3 Slots per Frame: Simulation g g
66‘ ' -o—3$lotsperFrame:Formula g 10 lb " M" ‘ H """ ’1'2g
it ~ i f r .5 g
0 5 - f 7 ' ‘ ~ 1 ..
o 2 . 3 g
a : ' E 1 d ‘ 1 r . | | 8
5» 4 - ': c » . ' ._ 0.83
r: i 2 8
93 , 3 ‘ E
to .
.434 .. 30.1- . "-0.6%
8 f I , o
3,: - "- .
1- 2 _ I / "' 0.4
0.01 ~— , - -. ~ _.
1 . ' , 1 . T l . . Latencywith Dynamic Allocation. 0,2
; ’ L 4K ‘ 2 d5 3 between1 and 2-slots per frame
. all . .585 . .
wmfifi.. . .
0 8rfirfigffi . i i r 'r ‘r 1 . i 0.001 l i 0
0.1 0.5 0.9 1.3 1.7 2.1 2.5 2.9 0 200 400
Data Rate (packets/frame) Time (frame count)
(a) Delay-bandwidth characteristics with (b) Effects of dynamic multi-slot ISOMAC
static multi-slot ISOMAC on packet delivery latency

 

 

Figure 3.13: Effects of static and dynamic multi-slot allocation

3.6.8 Multi-Slot ISOMAC

Latency-bandwidth characteristics for ISOMA GA with static multi-slot
allocation (see Section 3.5) is reported in the graphs in Figure 3.13za. During this
experiment, all nodes are statically allocated l, 2 or 3 slots per flame, including the
basic slot. As expected, with increasing date rate the latency increases following the
standard queuing pattern. Also, for the same data rate, the latency is smaller for
scenarios in which higher numbers of slots are allocated per flame. This also

indicates that statically allocating larger number of slots can enhance the sustainable

MAC data rate of the ISOMAC protocol. In addition to the simulation experiments,
we have evaluated the latency numbers using the TDMA delay analysis mechanism

presented in [57]. The latency figures are analytically computed to be
A

 

D=—l—Fr+Fr +r , D=—l-Fr+£r—-—+r and
2 2(1—2) 4 4 2(1—2/2)
D = 11:, ’1 +1 for allocations of 1, 2, and 3 slots/node/flame

+-—-r————-
6 6 3(1—1/3)

respectively. Figure 3.13:a demonstrates that the simulation experiments produce
results that are very close to the analytical results.

The working and the efl’ects of dynamic multi-slot ISOMA GA on latency are
demonstrated in Figure 3.13zb. In this experiment, variable capacity needs are
created by switching the data rate flom a node between 0.5 packets/flame and 1.5
packets/frame afier every 100 frames. With 1 slot/flame static allocation for the node,
the latency changes flom a moderate value for the lower data rate, to a dramatically
increased value for higher rates. This is simply because the sustainable data rate for
the l slot/flame allocation is much smaller than the required 1.5 packets/frame rate,
and therefore heavy queuing develops. For the same variable data rate, a dynamic
multi-slot allocation has also been experimented with. In this case the allocation for
that node is dynamically switched between 1 slot/frame and 2 slots/flame based on
the nodes instantaneous data rates. As evident flom Figure 3.13zb, the latency in this
dynamic case is much more contained compared to that in the static allocation case.
It is always in the range of 0.1 to approximately 5 flames compared to the case of
basic ISOMAC with static allocation.

3.7 Summary and Conclusions

65

We have presented a self-organizing MAC protocol for distributed sensor
networks. In the proposed ISOMAC protocol, a fixed length bitmap vector is used in
each packet header for exchanging relative slot timing information across immediate
and up to 2-hop neighbors. It is shown that by avoiding explicit timing information
exchange, ISOMAC can work without network-wide time synchronization which can
be prohibitive for severely cost-constrained sensor nodes in very large networks.
Through simulation experiments it was shown that ISOMAC is performance without
time synchronization is just marginally worse than that with synchronization. It was
also shown that a slot-clustering effect due to in-band bitmap constraints causes
ISOMAC to offer better spatial channel reuse compared to traditional distributed
TDMA protocols. Results demonstrate that with in-band bitmap vectors of moderate
length, ISOMAC converges reasonably quickly - approximately within 4 to 8 TDMA
frame duration. Also, if the bitmap is restricted within 10% of packet duration, the
energy penalty of the in-band information is quite negligible. Due to the fact that in
ISOMAC a node has to own a slot and send a header-only transmission even when
there is a no packet to be transmitted, the protocol would perform better in relatively

more uniform traffic scenarios with less such zero-traffic situations.

66

Chapter 4
Cross-layer Routing Protocols in the Presence of MAC Self
Organization
4.1 Introduction
4.1.1 Current MAC Self Organization Strategies in WSN
Generally contention-based protocols are susceptible to collisions and its

resulting energy inefficiency during the wake periods. Recent researches show that
this inefficiency can be avoided in Time Division Multiple Access (TDMA)
protocols. Since all transmissions within a TDMA MAC flame are pre-scheduled, it
is possible for a node to sleep when it is not expected to transmit or receive packets.
Such distributed TDMA approaches have been explored in protocols such as
TRAMA [23] and TDMA-W [24]. These and other TDMA based sensor MAC
protocols all attempt to achieve collision-flee slot allocation such that nodes within
up to 2-hops of each other cannot share overlapping transmission slots. Spatial reuse
can happen beyond this 2-hop neighborhood. Differences among the existing sensor
TDMA protocols [23, 24] exist in the control mechanisms for distributed slot
scheduling. But once the slots are allocated, they behave as regular TDMA protocols
and follow similar sleep-wake cycles for energy conservation.
4.1.2 End—to—End Delay due to TDMA Slot Misordering

While solving the energy saving problem at the MAC layer, the TDMA
mechanism can give rise to increased end-to-end routing layer delay. This can

happen when the TDMA slots of sensor nodes on a route are not time-ordered in the

67

same sequence as the one the nodes appear on the route.

As an example, consider a data flow from node A to node D on the linear topology
in Figure 4.1:a. With the TDMA Allocation-1 (see Figure 4.1:b), a packet from
node A can be delivered to node D within a single TDMA flame duration. This is
possible because with Allocation-I the TDMA slots on the route flom A to D are
time-ordered in the same sequence as the one the nodes appear on the route itself. As
a result, when it is a node’s turn to relay a packet, the packet is already available
because it was transmitted by this node’s upstream neighbor during an earlier slot
within the same TDMA flame. For example, since node B’s TDMA slot is preceded
by node A’s slot, node B is guaranteed to have received the packet flom A before its
own allocated slot starts. The same applies to the slots for node C. As a result, the
maximum end-to-end delay in this case is bounded by the TDMA flame duration.
Note that the location of D’s slot doesn’t affect the delay in this case since D is the

sink.

 

 

 

I. I. 1. I.

a) Linear Topology
Time

A
v

ABIC [SI ABCJDI |ABJC [D] I

‘— Frame —"’ I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Allocation-l
lCBA IEIICBA [B] ICBA E],
I Frarne-l I Frame-2 I F rame-3 I
Allocation-2
b) Synchronized TDMA allocations

 

Figure 4.1: Effects of TDMA on end-to-end delay

Now consider Allocation-2 in which the temporal ordering of the TDMA slots no

68

longer coincides with the sequence of nodes on the route from A to D. This slot
misordering can introduce significant amount of end-to-end routing delay in the
following manner. A will forward a packet to B during A’s slot in Frame-1. By the
time B receives this packet, it is past B’s transmission slot in Frame-l, and therefore
B has to wait till the next flame for transmission. After B sends the packet to C in
Frame-2, the same misordering issue is faced by C. In the end, a packet from A to D
will require three complete TDMA flames, as opposed to just one flame in the case
of Allocatioon-I. In the worst case, when the N nodes on a route have the complete
reverse ordering compared to the slot allocation ordering, the end-to-end delay will
increase linearly to N-l frame duration.

This problem of increased delay due to slot misordering can be exacerbated in
sensor networks where large flame durations are usually chosen for maintaining low
duty cycles for limiting energy consumptions. In TDMA-W [24], for example, the
chosen flame duration is 1 second, which means that for a 50-hop route the worst
case end-to—end delay due to slot misordering can be as large as 50 seconds.

In sensor networks with delay sensitive applications, such large end-to-end delays
are highly undesirable. Especially for applications such as event monitoring for
tactical surveillance, intrusion detection, industrial process monitoring, and security
attack detection, such delays need to be mitigated.

The objective of this work is to introduce a Minimized Slot Misordered Routing
(MSMR) technique to limit end-to—end application delays caused by the slot

misordering problem. In MSMR, such delay reduction is achieved at the expense of

69

increased energy overhead in routing layer.
4.1.3 Related Work

In the protocol D-MAC [34], the delay issue discussed above is resolved by
delay-optimized slot allocation based on pre-set routes. In [34] multipoint-to-point
data model is assumed over a routing spanning tree. Once a routing tree is
constructed, D-MAC allocates transmission slots to nodes based on their positions

on the routing tree. Nodes at the lowest level are allocated the earliest
transmission slots in a flame, and those at higher levels are allocated subsequent
slots. This slot ordering ensures that as long as traffic flows flom the lower to higher
levels within the tree, all transaction within the tree can be performed within a single
frame.

D-MAC suffers flom the following shortcomings. First, the protocol is not able to
operate in the absence of preset routes and therefore, unlike TRAMA [23] and
TDMA-W [24] it is forced to assume that only one routing tree is allowed in the
network. Second, D-MAC is not contention flee like regular TDMA. With D-MAC,
nodes at the same depth level of a routing tree share common transmission slots and
therefore they are susceptible to collisions and the subsequent energy inefliciency.
Third, D-MAC does not provide syntax for completely avoiding hidden-collisions.
Finally, it assumes unidirectional data flow towards the root. This can be restrictive
for many sensor applications where sensor programming commands need to be also
routed downstream along the tree.

The other existing approach for mitigating end-to-end delay due to MAC slot

70

misordering is presented in [35]. This protocol proposes a cross-layer delay
optimization scheme that works with variable length TDMA flame. The mechanism
uses a link scheduling algorithm to find the minimum-delay schedule for given slot
lengths for all the links. While this mechanism provides a cross-layer solution to the
end-to-end delay problem, like D-MAC it also assumes unidirectional tree based
data routing, which may not be practical for a number of sensor network applications.
Also, the congestion at higher level nodes near the sink is not being considered in
[3 5]. Moreover, the variable length TDMA flame may pose a disadvantage in terms
of implementation complexity.
4.1.4 Proposed Solution

In this chapter we take a different cross-layer approach to address the delay
problem by computing minimum delay routes based on a given TDMA allocation.
Unlike D-MAC, which resolves the problem by delay-optimized slot allocation
based on pre-set routes, we seeks an opposite point of view by finding the
delay-optimized routing based on pre-set TDMA slot allocation. This is
accomplished by computing least cost routes with a link cost formulation based on
the degree of misordering of the TDMA slots of nodes across a link. The goal is that
the routing algorithm will automatically choose a route with least amount of slot
misordering on an end-to-end basis. Note that unlike D-MAC [34], which supports
only multipoint-to-point data model, our proposed protocol is data model agnostic.

The primary advantage of this Minimized Slot Misordered Routing (MSMR)

approach is that unlike in D-MAC, multiple routes can be simultaneously supported

71

in a network. Also, since no specific data models need to be assumed, both
point-to-point and multipoint—to-point applications can be supported over MSMR.
Moreover, the applications can be bidirectional.

Note that MSMR is a cross-layer technique but it does not depend on the specific
TDMA allocation protocol at the MAC layer. Therefore, it is completely agnostic to
how the TDMA scheduling is achieved, as long as the steady state TDMA scheduling
is collision-flee within 2-hop neighborhood.

4.2 Minimized Slot Misorderd Routing (MSMR)
4.2.1 TDMA Allocation Model

MSMR is designed for arbitrary sensor mesh topologies using a single radio
channel with spatial reuse. Sensor nodes are assumed to be stationery and all links be
bidirectional. Upon deployment, a node executes a distributed MAC scheduling
protocol [23, 24] to be allocated a TDMA slot which is collision free from its all
l—hop and 2-hop neighbors. Frames across the network may or may not be time
synchronized based on the availability of any network time synchronization
mechanisms such as GPS.

An example of asynchronous slot allocation for the linear network in Figure 4.2:a
is shown in Figure 4.2:b. Note that in this allocation, collisions are avoided by
making all l-hop and 2-hop neighbors’ sending slots non-overlapping. However,
spatial reuse is achieved by allowing 3-hop neighbors such as A and D to share
overlapping transmission slots. Since this example allocation is asynchronous,

although their frame durations are equal, the flame boundaries of individual nodes

72

are completely independent of each other. In spite of this flame asynchrony, the
allocated slots satisfy the 2-hop non-overlapping rule [23]. After a TDMA slot is

allocated, the allocation pattern remains unchanged till the network topology

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

changes.
I A I B I, ID
a) Linear Topology
Time :
A’s Frame
k \ Data
/
AF“
1
Tx-Slot
B m m—
C I‘m t
D m m
i.— c —~
i M: *CCD‘i
i“ Frame Duration -':
b) Asynchronous TDMA Allocations and Link Cost

 

Figure 4.2: Example MAC allocation and link cost formulation
4.2.2 Link Cost Formulation
The objective of the Minimized Slot Misordered Routing (MSMR) is to avoid
mismatch between the sequential ordering of the nodes in an end-to-end route and
the temporal ordering of those nodes’ TDMA allocation. We formulate a new link

cost fimction to capture the degree of such mismatch by defining the cost of the link
LI. 1 based on the relative slot timings for nodes i and node j.

The cost Ci j for link Li jis defined as the time difference between node j’s

transmission slot and node i’s transmission slot. Example of link costs for links

LC D and L D cm Figure 4.2:a are shown in Figure 4.2:b. This formulation

73

always makes the sum of the cost of link j to i and link i to j the fixed flame duration.

In other words, the condition Ci j +Cj ,- =F is always true, where Ci jis the

cost flom node i to j, C,- j is the cost flom node j to i and F is the flame duration,

which remains the same for all nodes. Since the MAC slot of the sink node on a
route does not contribute to the end-to-end delay, the cost of the link that contains
the sink as the receiver is always set to be zero.

The underlying meaning of this cost formulation is that Ci, -represents the time
delay flom the time a packet is received by node j flom node i, to the time the packet
is sent out by node j. The time when the packet is received by node j is decided by
the location of the transmission slot of node i.

4.2.3 Baseline MSMR Route Computation

After the link costs are assigned, a minimum cost route computation algorithm
such as Dijkstra’s can be used for computing MSMR routes. Distributed
minimum—cost routing algorithms such as Bellman-Ford can also be used for the

route computation.

 

1m

mmnnannemnnnhaal

a) Synchronous MAC Allocation

 

 

 

   

b) Spanning Tree for Node—0 c) Spanning Tree for Node-0
with MHCR Routes with MSMR Routes

 

 

 

Figure 4.3: MSMR operation with synchronized TDMA

74

The process is fiuther explained using an example of 6-node network as shown by
the solid lines in Figure 4.3:b and 4.3:c. The synchronized MAC allocation pattern
used for link cost computation is shown in Figure 4.3:a. Routes created flom all
nodes to node-0 using a Minimum Hop Count Routing (MHCR) is shown as a
spanning tree represented by the dotted lines in Figure 4.3:b. Similarly, the spanning
tree constructed using MSMR routing flom all other nodes to node-0 is depicted in
Figure 4.3:c.

Consider the route flom node 5 to node 0, which is two hops in the case of MHCR
routing, but three hops for the MSMR routing. This example indicates that
sometimes it is desirable to take a longer route to minimize the end-to-end delay due
to MAC slot misordering. This, however, also indicates that such delay reduction is
achieved in MSMR at the expense of larger hop-counts which in turn would cause
larger energy consumptions due to added transmissions. Therefore, it is fair to say
that MSMR is expected to mitigate the end-to-end delay by trading overall energy
efficiency.

4.2.4 Balanced MSMR to Mitigate Packet Queuing

So far, the end-to-end latency has been discussed only in terms of the delay due
to MAC slot misordering. While this is reasonable at lower traffic volumes, delay
due to packet queuing can dominate the overall end-to-end delay during congestions
at higher traflic situations. This effect is expected to be prominent at nodes near the
sink node (e. g. node-0 in Figure 4.3). Since all packets are destined towards a single

sink node, these nearby nodes are more susceptible to congestion caused by traffic

75

aggregation. If the end-to-end cumulative queuing delay becomes dominating over
the delay due to MAC slot misordering, then the effectiveness of MSMR on delay
reduction is likely to diminish.

This problem can be partially mitigated by in-network data aggregation as
proposed [58].While aggregation in sensor networks can be effective for monitoring
applications with spatially correlated sensor data, it is less so for event monitoring

applications as targeted for this work.

 

/* Balanced MSll/fli’ Sensor Routing Mechanism */
Use a T DMA MA C [2, 5] for slot scheduling

For all network links Li,j{

Using the allocated MAC slots, compute link slot

misordering cost C i jas in Sec. 2.2;

}

Create an ascending ordered list of all nodes based on
their WCR hop counts to the sink node;
for (each node from the list, chosen sequentially){
Compute the MSMR route from this node to the sink
using the baseline MSW described in Section 2. 3;
Load traflic on this route at a target event rate;
Measure the queuing delay at each node on the

route;

Adjust the cost of all links on the route as:
Ci,j =Ci,j +Qj, where lethE
measured queuing delay at node j

}

 

 

 

Figure 4.4: pseudo-code of Balanced MSMR logic
Therefore, instead of adopting data aggregation, we rely on traffic load balancing
for reducing the effects of queuing. By reducing the dominance of the queuing delay

on the overall end-to-end latency we expect to preserve the effectiveness of MSMR

76

for latency reduction.

To mitigate queuing, we adopt a heuristics based centralized Balanced MSMR
mechanism. Although a distributed version is feasible, considering its additional
control and subsequent energy overhead, initially we have chosen to use a
centralized version in this paper. Moreover, as considered in protocols LEACH-C
[59] and BCDCP [60], centralized routing is deemed appropriate for networks with
static sensor nodes, as targeted in this paper. The Balanced MSMR routing logic is
outlined in the following pseudo-code in Figure 4.4.

The heuristics behind the Balanced MSMR logic is to a) load the shorter routes
with targeted traffic, b) compute the link costs as a combination of latency due to slot
misordering and queuing, and finally c) compute longer routes based on this adjusted
cost metric. Considering the queuing delay as a part of the link cost helps mitigating
this by load distribution at the routing layer. Note that the routes constructed by the
Balanced MSMR mechanism depend on a target event rate from each node. This is a
reasonable assumption in application-specific sensor networks with known
long-term event generation rates.

In the Balanced MSMR heuristics, the longer paths are constructed after the
shorter ones for the following reason. According to the presented logic, the later a
route is created, the more accurate it is because of the iterative adjustments of the
link costs during the earlier route constructions. The objective is to make the longer
routes more accurate so that the effects of inaccuracy in queuing latency estimation

are minimized across the network. In order to attain that the longer routes are

77

constructed after the shorter ones.
4.3 Performance Characterization
4.3.1 Network and Data Model

MSMR has been simulated using a C-based event-driven and packet-level
sensor network simulator, and its performance has been compared with the
Minimum Hop Count Routing (MHCR). The reported results represent MAC and
routing layer modeling without a detailed PHY layer model. Since we compare the
performance of MSMR and MHCR at the routing layer, any PHY layer variation
may change the absolute routing layer performance, but the comparative
performance trends of the protocols reported here are expected to be valid.

A sensor network with nodes deployed uniformly within a circular sensor field
has been simulated. While keeping the transmission range constant, we vary the
sensor field size for experimenting with different network densities. Also, to keep
the routing trees symmetric, the sink node (access point) is always placed at the
center of the circular sensor filed.

For the MAC layer, the slot duration and the frame duration are chosen to be 5
ms and 500 ms respectively. As for the MAC, we have used the scheduling scheme
of the TDMA-W [24] sensor MAC protocol. Note that the proposed MSMR
mechanism is agnostic to the control/scheduling part of the underlying MAC
protocol. It depends only on the resulting MAC schedule, and therefore can work
with other TDMA MAC protocols [23] without any performance differences.

Event-based data is generated at a constant rate (events/sec/node) from all nodes

78

except the sink node. The data is contributed flom independent sensing events which
are assumed to be occurring at nodes with a Poisson distribution. The cost modeling
is performed as explained in Section 4.2.2, and a centralized Dijkstra’s
minimum-cost algorithm is used for computing routes in both MSMR and MHCR.
In the following results, each data point corresponds to the average of 500 unique
simulation runs.
4.3.2 Effects of MSMR on Delay

MSMR has been evaluated in a 5000-node network in which each sensor node
generates packets at a very low data rate corresponding to approximately 0.001
events per second Initially, the data rate is deliberately kept very low in order to
evaluate MSMR without packet queuing. Also, such low event rates are quite
realistic for intrusion detection applications, where the events are rare but once such

an event happens, it is required to be reported from the detecting sensor node to the

 

 

 

 

  
 
 
 
  

 

 

 

sink node as quickly as possible.

11000 . i j
A 10000 - +MHCR2Densrty5 ------” -, .
E 9000-+MSMR:Density5 ~.~ "iw
g; 8000i+MHCRzDensity10hmwn”i“ """"""" “”1
— 7000 — . i --------- , -------- — -l
a 6000,+MSMR:Densrty10,_M __

E 5000 ' — - —
é 4000 __......,... ..._. - -.., ,. ;w_~ _-

1': 3000 r”— M ~

[5‘ 2000 __--._---.-_ . - . _ :__.. .. H _ -

0- + i l i

0 10 20 30 40

MinimrmHopCount

 

 

 

Figure 4.5: Effects of MSMR routing on delay

79

The experimental results for two different density values are presented as a
function of hop-count in Figure 4.5. Density is defined as the average nodal degree.
The hop-count in the x-axis represents the minimum possible hop-count from a
sensor node to the sink node. From each sensor node, routes are computed to the
sink using both MHCR and MSMR, and the corresponding end-to-end delays are
measured through simulation. Afterwards, the delay values are plotted as a function
of the minimum hop-count for all nodes in the network. The end-to-end delay is
recorded as the time difference between the instant an event is detected by a sensor
node and the time when it is reported to the sink node.

Note that for the minimum hop MHCR routing the end-to-end delay is
insensitive to the network density, and therefore the graphs for MHCR with different
density values are overlapping in Figure 4.5. Also, for both MHCR and MSMR,
lower density requires longer hop-count routes.

From Figure 4.5, it is evident that for a given network density, the MSMR
routing delivers lower end-to-end delay compared to the min-hop MHCR routing at
all the hop-count values. Data flom nodes which are further from the sink benefits
more flom the MSMR routing. This monotonic dependency is due to the fact that
end-to-end delay reduction by MSMR is a cumulative effect of MAC delay
reduction over all the hops on a route.

Consider the results for density 10. For example, a packet traveling flom a node
with minimum hop-count 27 (flom the sink) the end-to-end delay with the MHCR

routing is 6.4 sec, whereas the delay with the MSMR routing is 2.9 see. In other

80

words, by employing the MSMR technique, the reporting delay of an emergency
event can be reduced by up to 3.5 seconds, which is a significant amount of time for
possible remedial actions for an intrusion or disaster event. With a lower density of 5,
similar trends are observed, although with a relatively lower delay reduction. This is
because with lower density each node has fewer neighbors, and therefore MSMR has
lesser route diversity leading to a smaller delay gain.
4.3.3 Energy-delay Tradeoff

As shown in Figure 4.3, the hop-counts of MSMR routes are always greater than
or equal to those of the corresponding MHCR routes. Larger hop-counts translate to
larger transmission energy expenditure for each packet transport to the sink, and
therefore it can be said that MSMR obtains better delay performance at the expense
of increased energy overhead. The measure for energy overhead is expressed in

ad PHo = ”MSMR "HM”CR x100%,
HMHCR

terms of Percent Hop Overhe which is

reported in Figure 4.6 as a function of hop-count. The x-axis represents the same
quantity as in Figure 4.5.

The results in Figure 4.6, together with Figure 4.5, demonstrate how the
energy-delay tradeoff plays out in the given context. As evidently seen flom Figure
4.6, the increase in PHO with hop-counts is not monotonic. The overhead is less for
packets flom the nodes which has very small or very large minimum hop-counts
flom the sink. The reason for this overhead pattern is that nodes which are closest to
the sink and farthest to the sink have less number of possible routes comparing to the

nodes in the intermediate distances.

81

 

 

30
1.325 —

 

i—- N
Ur O
1 1

   

 

“II-MSMR: Density 10
+MSMR: Density 5

Percent Hop Overhe

   

 

 

 

 

0 10 20 30 40
M'n'nun Hop Court

 

 

 

Figure 4.6: Effects of density and hop count on PHO

As for network density, higher densities bring in more delay reduction by MSMR
(see Figure 4.5) due to increased routing diversity. As expected, the hop overhead is
also larger for higher density. Observe this efl’ect in Figure 4.6. As Experimental
results in Figure 4.6 show that the PHO for density 10 is around two times of that for
density 5.
4.3.4 Effects of Congestion and Packet Queuing

To study the efi’ects of packet queuing as described in Section 4.2.4, we have

experimented with MSMR routing in a 100-node network with varying event rates.
Note that with 5ms slot duration and 500ms flame duration [24], the maximum
possible event rate is 2 events/second/node. The results of packet queuing are
reported in Figure 4.7.

Observe that for lower event rates (e.g. 0.05 events/second/node) MSMR delivers
significantly better end-to-end delay compared to the minimum-hop MHCR routing.
This result is consistent with what has been observed for a low event rate of 0.01

events/second/node in Figure 4.5. With increasing event rate, the delay performance

82

of MSMR starts deteriorating due to increased packet congestions. As reported in
Figure 4.6, since MSMR uses longer routes than MHCR, it generates more overall

traffic, and as a result is more susceptible to queuing than MHCR In addition, links

with smaller MAC slot misordering cost Ci are found to be chosen in large

1'
number of MSMR routes, thus making those links highly congested. These explain
why the MSMR delay shoots up at a relatively smaller event rate (i.e. 0.15

events/second/node) compared to the MHCR routing.

 

 

 

   
  
 
  

 

 

 

 

 

 

 

 

 

 

 

 

1700 ~———a ; l ’
“'9' NIHCR ;
731500 # MSMR ..-: --.-
E "A" Balanced MSMR
E
1: Low Queuing ' . High Queuing
c: .
ill __ _ _ ...... -
é 1100
1':
r:
m 900 ‘“
700 l .1 l
O 0.05 0.1 O. 15 0.2 0.25 0.3
Event Rate (events/second/node)

 

Figure 4.7: Packet queuing at higher sensor event rates
This result clearly demonstrates another tradeoff which states that MSMR routing
can reduce the overall end-to-end delay only up to a maximum allowable event rate,
which is smaller than the maximum allowable rate for MHCR.
4.3.5 Balanced MSMR for Mitigating Congestion
The effect of this Balanced MSMR on queuing is also shown in Figure 4.7. Note

that at lower event rates, where the queuing is negligible, Balanced MSMR has

83

delay reduction abilities very similar to the plain MSMR. With increasing event rates,
however, the load spreading in Balanced MSMR is able to defer the congestion load
point compared to the plain MSMR. In this case, it is flom 0.15 events/second/node
to 0.25 events/second/node, which is almost a 66% improvement. Observe that for
even higher loads, the delay for Balanced MSMR eventually exceeds that of MHCR,
thus indicating that even with load balancing MSMR is more congestion prone than

MHCR.

 

 

 

 

 

 

15
10

UI

 

Percent Delay Reduction
O

 

 

 

 

 

r
Ur

0.04 0.09 0.14 0.19 0.24
Event Rate (events/second/node)

 

 

 

Figure 4.8: Increased allowable event rate with load balancing
The percent delay reductions with respect to MHCR routing for both balanced
and unbalanced MSMR are shown in Figure 4.8. At lower event rates, MSMR
slightly outperforms its balanced counterpart. Balancing however helps significantly
in terms of sustaining the delay reduction property for higher event rates. In this case,
while delay reduction for MSMR can be achieved up to 0.15 events/second/node, the
same for Balanced MSMR is approximately 0.24 events/second/node. This is a gain

of 60% in terms of maximum allowable event rate with sustainable delay reductions.

84

For very high rates, however, both MSMR and Balanced MSMR lose this property
by actually performing worse than the MHCR routing.
4.4 Summary and Conclusions

A Minimized Slot Misordered Routing (MSMR) protocol has been proposed for
end-to-end delay mitigation in sensor networks with TDMA MAC. Different from
the existing D-MAC [34], which resolves the problem by delay-optimized slot,
allocation based on pre-set routes, MSMR seeks an opposite point of view by finding
the delay-optimized routing based on pre-set TDMA slot allocation. MSMR has been
targeted towards delay sensitive sensor network applications such as tactical
surveillance, intrusion detection, and industrial process monitoring. Delay reduction
in MSMR is accomplished by computing least cost routes with a link cost
formulation based on the degree of misordering of the TDMA slots of nodes across a
link. It has been shown that with realistic TDMA models and sensor event generation
rates, in a 5000-node sensor network, MSMR can reduce the reporting delay of
emergency events by up to 3.5 seconds, which is a significant amount of time for
possible remedial actions. We have also shown that while controlling end-to-end
delay due to slot misordering, at higher event rates MSMR can give rise to
undesirable queuing delay as a result of congestions. We propose a centralized
Balanced MSMR routing protocol that can strike a balance between queuing delay
and slot misordering delay by adjusting link costs based on instantaneous node level
congestions.

Future work on this topic includes developing a distributed Balanced MSMR

85

protocol. The goal is to avoid network wide information flooding and to let the

sensor nodes compute the delay optimal routing locally.

86

Chapter 5
Application of ISOMAC for Vehicle-to-Vehicle Communications for
Safety and Data Intensive Applications

5.1 Introduction
5.1.1 Application of ISOMAC

In Chapter 3, we provide a generic MAC self organization solution ISOMAC for
wireless sensor networks. MAC self organization can play a crucial role in many
other Ad Hoc networks such as battlefield organization, disaster recovery
management, and vehicle communication. In this chapter, we adapt the concept of
the proposed ISOMAC protocol in the context of vehicular networks.
5.1.2 Background and Motivation

The emerging Intelligent Transportation System (ITS) [61] architecture is
currently being developed for enhancing vehicle safety, driving experience, fuel
economy, and economic stimulation through safer and efficient transportation
networks. A key component of the ITS architecture is vehicle-to-vehicle (V 2V) and
vehicle-to-roadside (V2R) communication for application data exchange between
vehicles and road-side inflastructure.

ITS applications can be categorized broadly into two kinds: safety oriented and
data intensive applications. Examples of the safety oriented applications include
Cooperative Collision Avoidance (CCA), Cooperative Adaptive Cruise Control
(CACC), Emergency Xehicle Preemption (EVP), and Intersection Collision Warning

(ICW) systems. Notable examples of data intensive applications are vehicle based

87

probe data collection for traffic congestion management, drive-through payment
such as the EZ Pass system, parking lot payment, enhanced route planning and
guidance, and entertainment applications such as inter-vehicle gaming and music
downloads [62]. From the networking standpoint, the safety oriented applications
generally have much stringer performance requirements including lower and
bounded delay [63], and better fairness. Whereas in data intensive applications, a
higher achievable end-to-end throughput is favorable.

Dedicated Short Range Communication (DSRC) [62] is an emerging V2V and
V2R communication standard, which is being developed for a FCC allocated 75
MHz wide spectrum segment at the 5.9 GHz band. Although IEEE 802.11p is
currently recommended as the Medium Access Control (MAC) protocol within
DSRC, like other random access protocols it does not work well at high traffic
conditions. At high traffic loads, the packet delivery latency increases due to
increased collisions, retransmissions, self-competition within a single data flow, and
cross-competition among multiple data flows [64]. Also, because of the underlying
random access, at higher loads the delivery latency becomes unpredictable, and
therefore not bounded [64, 65]. These effects could also bring down the achievable
end-to-end throughput for inter-vehicle data transfer through connections spanning
across multiple vehicles.

This implies that for a delay-sensitive ITS safety application such as Cooperative
Collision Avoidance (CCA) [66], 802.11 may not be able to provide the required

small and bounded message delivery latency. This problem has been identified and

88

various solutions have been proposed in [63, 67]. It has been demonstrated that the
stated latency problem is severer in the presence of vehicle crowding and broadcast
storm in the events of road emergencies. The required end-to-end throughput is not
provided in the data intensive applications by 802.11.

The above problems and requirements challenge the MAC self organization in the
vehicular networks. To address those delay issues, which are far different flom
wireless sensor networks, we adapt the previous ISOMAC of wireless sensor
networks and develop an alternative MAC layer architecture that can support ITS
safety applications by providing bounded delivery latency over a DSRC network.
The adapted TDMA protocol yghicular Self-Qrganizing MAC (VeSOMAC) is
self-configurable and firlly distributed just like ISOMAC, and capable of low-latency
data delivery with fast allocation convergence achieved by slot scheduling based on
the relative location, speed and other context parameters of a vehicle platoon, and the
application-specific data flow within the platoon.

5.1.3 Related Work

The desirable features [41] of a MAC protocol for V2V and V2R applications
include a) small and bounded delay, b) inter-vehicle fairness, c) scalability with
vehicle crowding, d) distributed operation, and e) the ability to cope with frequently
changing network topology caused by vehicle movements.

The vehicular MAC protocols in the literature are again in two broad categories:
contention-based and schedule-based. The contention based approaches have the

advantage of not being sensitive to underlying mobility and topology changes. As a

89

result, unlike for the schedule-based protocols, vehicle movements do not impose
any reconfiguration overhead due to the network topology changes. This is a
significant advantage. The unbounded delay issue however, applies to all protocols
in this category because of their underlying random access. A number of variations
of CSMA/CA and 802.11 have been implemented in [36-38]. Although somewhat
mitigated, the firndamental issue of unbounded delay still remains within this
category of protocols.

Note, however, these contention based approaches are completely agnostic about
the underlying mobility and topology changes. As a result, unlike the schedule-based
protocols as explained later, the vehicle movements do not impose any
reconfiguration overhead due to the topology changes. This is a major advantage of
the contention based approaches in vehicular networks.

The protocols in [39, 40] and [23] propose schedule-based TDMA mechanisms,
in which TDMA slots are self-selected by the nodes in a distributed manner. While
providing bounded data plane latency, the contention based slot allocation process
itself involves collisions, which are stochastically resolved. As a result, the slot
reallocation due to topology change may often incur a large upfront delay before the
application data can start or resume flowing. The protocol in [67] proposes to
configure a token ring protocol so that the maximum delivery delay is always
bounded by the round-trip token time. Although being bounded, the delay can be
very large for large rings due to high vehicle crowding. This can be addressed by

having multiple rings, but then the ring management with frequently changing

90

topology can cause huge upfront reconfiguration delays. MCS/CDMA [68] is another
schedule based protocol that uses CDMA code scheduling. Each vehicle has to have
parallel receiver matched filters corresponding to all the codes used. If the search for
flee code is done sequentially, it could take long time when the number of vehicles
involved is large. This will add substantial reconfiguration latency in the event of a
topology change. Also, when there are more vehicles than the number of codes, there
could be a contention for flee codes resulting in large delays in channel access. The
protocol LCA [41] proposes a scheduled MAC, in which TDMA slots are allocated
based on a vehicle’s instantaneous geographical location, which is pro-allocated a
TDMA slot. This mechanism offers bounded delay, and also there is no
reconfiguration latency due to network topology changes. However, the system
requires complete pro-mapping of geographical locations to TDMA slots, which may
have practical limitations especially when the huge geographic coverage of a
transportation system is considered. Also, dimensioning optimal cell size for varying
application requirements and vehicle density is a non-trivial problem.

The following distributed TDMA protocols, which were proposed for wireless
sensor networks, can also be considered in the context of vehicular networks. The
protocols TDMA-W [24] and DRAND [69] both use an out of band handshake
signaling mechanism for distributed TDMA slot allocation. Nodes send control
packets during scheduled data slots, and that is how the neighbors’ allocation
information is disseminated. Based on its neighbors’ allocation information, a node

is able to select a collision-flee transmission slot, which is used for subsequent data

91

as well as control packet transmissions. Both these protocols have been designed for
networks with limited node mobility, since flequent topology changes may require
substantial reconfiguration latency caused by the two-way handshake signaling
needed after every topology change event.

The protocol ZMAC [70] offers a hybrid solution, in which although each node
is allocated a dedicated TDMA slot, the nodes are allowed to contend for bandwidth
using CSMA with a goal to improve the bandwidth usage. This protocol too, due to
its out-of-band allocation signaling, may suffer flom high slot reallocation latency
afier a network t0pology change. The protocol D-MAC [34] allocates node and route
aware TDMA slots with a goal of minimizing the end-to-end application delay. The
primary difliculty of applying D-MAC to the targeted vehicular applications is that
the MAC protocol assumes preset routes, which are not feasible in most safety
related applications for their latency constraints. Additionally, the protocol does not
provide syntax for completely avoiding hidden-collisions, which can prove
detrimental to safety critical vehicular applications.

From the existing literature we conclude that schedule based protocols are desirable
for their bounded delays, which is a critical requirement for ITS safety applications
which require fast reconfiguration and low message delivery latency. However, the
primary researchable question still remains: how to cope with flequent topology
changes by fast TDMA reconfiguration. This paper attempts to address this key
question.

5.1.4 VeSOMA C: Vehicular Adaptation of ISOMAC

92

A distinctive feature of the adapted Ehicular Self-Crganizing MA_C (VeSOMAC)
is its distributed design with fast schedule reconfiguration for coping with vehicular
topology changes. Distributed design allows MAC allocation without having to
depend on roadside inflastructure or virtual schedulers such as leader vehicles. This
allocation autonomy, coupled with the bitmap based in-band signaling mechanism,
allows VeSOMAC to perform fast slot reconfiguration after topology changes in
dynamic scenarios such as highway platoon mergers, vehicle passing, and other
urban traffic situations. Fast slot reconfiguration translates into low upflont latency
(during a topology change) which was noted to be a serious issue for other

deterministic protocols in [67] and [68].

 

................
n" fi

 

 

 

 

 

 

 

 

 

 

 

 

. ' ' Movement direction Emergency
( . . . Event
. Radio communrcatron
‘ ‘ a) Highway CCA scenario
Trme >
IICBIAI lICBA IBI IICIBA IEII
I Frame-1 I Frame-2 I Frame-3 I

b) Allocation-l: regular TDMA

I ABICI El | ABIC IBI I AFICI [D] l
I Frame-1 I Frame-2 I Frame-3 I

c) Allocation-2: VeSOMAC’s platoon aware TDMA

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 5.1: Location aware MAC allocation by synchronous VeSOMAC

VeSOMAC is adapted to be vehicle location and movement aware for application

93

specific delay provisioning. Consider the Cooperative Collision Avoidance (CCA)
application as shown in Figure 5.1:a. After an emergency event (e.g. an accident) in
flont of the platoon A-B-C-D, the platoon head A periodically broadcasts warning
messages instructing other vehicles to slow down for avoiding collisions4 [66, 72].
Such warning messages are to be forwarded across the entire platoon with minimum
possible delivery latency, by and to all vehicles. With an example TDMA allocation
[39] with arbitrarily slot placement (Figure 5.1:b), it will take three TDMA flames
before the message generated by vehicle A will be delivered to all vehicles in the
platoon. However, with a possible VeSOMAC allocation, in which slots are allocated
based on the vehicles’ relative locations (see Figure 5.1:c), the delivery delay can be
significantly reduced. In this example, all messages can be delivered within a single
flame. This improvement can be much more pronounced for larger platoons. This
way VeSOMAC can effectively enhance highway safety by leveraging its ability to
allocate slots based on location, speed, and other vehicular contexts.

The adapted VeSOMAC inherently has all the advantages of ISOMA C. Furthermore,
the avoidance of out-of-band explicit signaling makes VeSOMAC a faster
reallocation, which is particularly suitable for vehicular applications with frequently
changing network topologies. Finally, an option of sequential TDMA slot allocation
with respect to vehicles’ physical positions allows VeSOMAC to reduce message

delivery delays for a number of highway safety applications such as Cooperative

 

An example: on a 2004 foggy morning, more than 200 cars were involved in a multi-car pile-up on

1-96 near Iansing MI [71].

94

Collision Avoidance.
5.2 VeSOMAC Protocol Adaptation Details
5.2.1 Adapted Frame and Slot Structures

The adapted VeSOMAC generally has the same flame and slot structure as
ISOMAC like shown in Figure 5.2. Similarly to ISOMAC, in VeSOMAC it is
mandatory for each vehicle to send a packet every flame, even if no application data

is available.

 

 

 

 

D C B p A
Movement direction
a) Vehicle platoon topology
Time
_,. I ,‘_ Header Data »

 

 

 

 

 

Tx-Slot

B Z1 JZ:

 

 

 

 

 

 

 

 

 

 

 

Tx-Slot

 

 

 

 

 

 

L J ‘—y—‘
b) Steady state allocation for asynchronous VeSOMAC

 

 

 

Figure 5.2: Slot structure and steady allocation in adapted asynchronous VeSOMAC
The only difference we make to the adapted VeSOMAC is that we remove the
“interrupt” sub-slot slot flom ISOMAC flamework. The purpose of the interrupt slot
in ISOMAC is to advertise existence of newly joined node to sleeping neighbors. As

we stated before, energy is less a consideration in the vehicular networks. The

95

adapted VeSOMAC requires nodes to maintain awake all the time. Thus there is no
chance of missing joining advertisement because of in sleeping mode. The structure
of interrupt sub-slot consequently fades out flom the adapted VeSOMAC logic.

VeSOMAC operates in both synchronous and asynchronous modes just like
ISOMA C.

5.2.2 Adaptation of ISOMAC Protocol Logic for the proposed VeSOMAC
5.2.2.1 Timing and Bitmap Constraints Adaptation

The adapted VeSOMAC still follows the timing and bitmap constraints as defined
in ISOMA C. The timing constraint is hold for any distributed TDMA MAC protocol.
There is no change in the timing constraint at all in VeSOMAC. Spatial reuse in
VeSOMAC is accomplished by allowing vehicles which are more than two hops
away to share TDMA slots as usual.

Convergence results flom ISOMAC show that larger bitmap vectors can attain
faster convergence. The VeSOMAC logic potentially could completely remove the
bitmap constraint by having the maximum B value (flame size). Even with the
largest required bitmap vector, which is the flame duration in number of slots, the
number of bits required is usually much smaller (around 5% [73, 74]) compared to
the entire data packet, and therefore its capacity overhead can be considered
negligible. In addition to the function of the “dummy packet” in ISOMAC,
VeSOMAC obtains more responsive slot reorganization compared to the out-of-band
mechanisms that rely on explicit reallocation signaling without contribution to any

form of channel congestion.

96

5.2.2.2 Location Aware Slot Ordering for Delay Reduction

As shown in the Allocation-2 in Figure 5.1:c, one way to achieve location aware
delay reduction is to temporally order the slots in the same sequence as the vehicles
appear in a platoon. A packet flom the platoon-flout A can now be delivered to the
platoon-tail D within a single flame duration. This is because when it is a vehicle’s
turn to relay a packet, the packet is already available because it was transmitted by
this vehicle’s upstream neighbor during an earlier slot within the same flame. For
example, since B’s slot is preceded by A’s slot, B is guaranteed to have received the
packet flom A before its own slot starts. The same applies to the slot for C. As a
result, the maximum end-to—end delay in this case is bounded by the frame duration.

The absence of location-aware slot ordering introduces end-to-end delay in the
following manner. According to the allocation in Figure 5.1:b, vehicle A will forward
a packet to B during A’s slot in Frame-1. By the time B receives this packet, it is past
B’s transmission slot in Frame-l, and therefore B has to wait till the next flame for
transmission. After B sends the packet to C in Frame-2, the same misordering issue
is faced by C. In the end, a packet flom A to D will require three complete TDMA
frames, as opposed to just one frame in the case of Allocatioon-I. In the worst case,
when all N vehicles in a platoon have the complete reverse ordering, the end-to-end
delay will be N-I frame durations. Therefore, in order to minimize end-to-end
routing delay, VeSOMAC allocation needs the following constraint to be satisfied.

Ordering Constraint: If two vehicles 1' and j are geographical neighbors and is

location is ahead of j in the platoon, then is chosen slot should be earlier than j is

97

slot in the time domain.

The ordering constraint is optional, and it is useful when the wireless messages
flowing flom the flont to the tail of a platoon are more delay critical than the
messages flowing in the reverse direction. While this is generally true for most ITS
safety applications, a reverse requirement can be accommodated by adjusting the
definition of the constraint itself. A disadvantage of the ordering constraint is that it
can delay the self-configuration process of VeSOMAC by slowing down its
convergence. More about convergence will be discussed later in Section 5.2.2.5.
5.2.2.3 Transmission Slot Feasibility Adaptation

Besides timing, bitmap constraints in ISOMAC, the feasible transmission slot of
VeSOMAC has to satisfy the ordering constraints as defined in Section 5.2.2.2.

The definition of feasible slots now becomes: within the admissible region, a
feasible time region for a vehicle is defined by the duration which is sooner (on the
left on time axis) than the slots of all its rear neighbors, and later (on the right on the
time axis) than the slots of all its flont‘ neighbors. Any slot chosen within the feasible
region will satisfy all the protocol constraints.

Consider the VeSOMAC example in a highway platoon scenario in Figure 5.4. A
new vehicle R joins in between two unconnected vehicles P and Q. Bitrnaps (with
length 4) flom P and Q, as received by the new vehicle R, are shown in Figure 5.4:a.
The shared ‘0’s in the bitmaps of P and Q indicate an admissible time region for

vehicle R. The feasible region is indicated in Figure 5.4:a.

98

 

P’s
Neighbors
(rear)

 

 

Movement direction

 

P
. lllllo|o|‘/Ve‘?tor
a. Feasrble Physrcal
slot mg l i l/ Slots
°lable . =
avar Feasrble /

(Admissible
TimeRegion) I 0| 1 i 1 [II

I Bitmap

 

 

 

 

 

 

 

 

 

 

Q 7 Time )

 

 

 

 

b. No slot available with

satisfied timing constraint @
I

 

 

 

 

 

 

 

 

 

c. No slot available
with satisfied
bitmap constraints

 

 

l ,
|1|o|1|1|
Q

 

 

 

 

 

 

 

 

 

 

 

 

Time ,
. . |1|1|010|
Admrssrble . {—1.1
d. No slot available (but not @—
with satisfied Feasible) Le:
ordering constraint Time Region 3
l

 

. [01l0
Trme i Q

m

 

 

 

 

Figure 5.3: Adaptation of ISOMAC feasible slot scenarios in example VeSOMAC

99

Proof of F easibilitjy: Like in ISOMAC timing and bitmap constraint is guaranteed.
Also, since the admissible region is both sooner than Rs rear neighbors’ (Q and its
neighbors) slots and later than R 3 front neighbors’ (P and its neighbors) slots, the
ordering constraint is also satisfied. Therefore, in Fig. 4:a, the entire admissible
region is also a feasible region.

Scenarios in Figure 5.3:b and c are same as ISOMAC. In Figure 5.3:d although an
admissible region is found, a feasible region is not there because of a violation of the
ordering constraint. This is because although the admissible region for R is later than
vehicle P’s slot, a slot cannot be chosen from the admissible region so that it lies
sooner than Q’s slot.
5.2.2.4 Adapted VeSOMAC Protocol Overview

Similar to ISOMAC, the key strategy is that if a newly joined vehicle cannot
immediately identify a feasible time region, it first chooses a non-feasible slot that
lies on the right side of the slot of the vehicle immediately ahead in the platoon. At
this stage, the ordering constraint for the rear neighbor is not satisfied and the
bitmap constraint may or may not be satisfied. In the following iterative slot
movement each vehicle attempts to place its slot behind the slot of its immediate
front neighbor.

Contrast to ISOMA C, both the initial slot selection and the iterative slot
movement process require a vehicle to know its neighbors’ location information.
This is accomplished by including a vehicle’s location in the header of each of its

transmitted packets. This is a reasonable assumption for most of the ITS application

100

models [67, 75] with access to onboard GPS systems.

Consider the topology in Figure 5.4, in which the allocation step-l depicts
Tx—slots chosen by vehicles A-E before vehicle C enters the network. Here we
assume the maximum bitmap length (fi’ame length), thus eliminating the bitmap
constraint. Therefore, we only consider the timing and the ordering constraints. With
the allocation in step-1, vehicles A, B, D, and E each has a collision free slot that
satisfies the timing constraint. Also vehicle pairs A-B and DE individually satisfy
the ordering constraint. This is because Ais slot is ahead of Bis, and Dis is ahead of

E is. As a result, at step-1 all vehicles are at a steady allocation state.

 

 

I E [- D m C m B m A
Movement Direction
A B D E Time +

 

 

 

Step-l .

 

 

ABD E‘tC

s. spleen: 1
ep N’s move I

 

 

A B
Steps M I
’s ove |

A B

 

Step-4 El-

 

 

 

 

 

 

Figure 5.4: Iterative slot movements for allocation convergence
Upon entering the network, C learns about the slot locations of its l-hop
neighbors B and D from their periodic transmissions, and the 2-hop neighbors (A and
E) through the bitmaps in B ’s and Dis packet headers. Since the temporal gap

between Bis and Dis slots is less than a single slot, C is not able to find a slot

101

satisfying the ordering constraints with respect to both B and D. As shown in step-2,
unable to find a feasible slot, C chooses a collision free but non ordering-constraint
compliant slot right after E ’s slot. With this, the ordering constraint with respect to B
is satisfied but not with respect to D. Since at the end of step-2 the slot ordering of
CD is reverse to their physical ordering, now vehicles D and C cannot satisfy the
ordering constraint, and therefore their allocations become unstable. Vehicles A, B
and E however still remain stable.

Responding to its own instability, in step-3 D moves its slot after its front
neighbor C is slot for satisfying the ordering constraint. Similarly in step-4, E moves
its slot after Dis slot. After these moves, the allocation slot ordering of the platoon
becomes consistent with the vehicles’ physical ordering. Finally, the allocation
pattern after step-4 becomes compliant with the timing, bitmap and the ordering
constraints, and therefore it is considered to be stable.

To summarize, the core idea of VeSOMAC logic adaptation is to let each vehicle
iteratively move its slot following its immediate front neighbor’s slot until a
combined allocation pattern which is stable for all vehicles in the neighborhood
emerges.

If the ordering constraint is removed, the iterations above become much simpler.
In Figure 5.4, the allocation reconfiguration will now stop at step 2 after C chooses
its slot. This indicates a much faster convergence (2 steps) compared to the one with
ordering constraint scenario (4 steps) as explained above. Generally speaking, by

removing the ordering constraint in VeSOMAC, it is possible to trade data plane

102

delay for faster protocol convergence during a topology change.
5.2.2.5 Generalized Slot Selection Logic of VeSOMAC Adaptation

After joining a network, if a vehicle finds no feasible slot as defined in Section
5.2.2.3, it picks a collision-free slot (satisfying bitmap and timing, but not the
ordering constraint) that is chosen randomly (uniformly distributed) within B.r
duration after the slot of its immediately front vehicle. If no such collision-free slot
is found, the same binary exponential logic in ISOMAC applies.
5.2.2.6 Inherent Collision Detection and Resolution Logic

Packet collisions in VeSOMAC are resolved using the exact logic used in

ISOMAC. Note that the VeSOMAC logic can handle collisions in the presence of
interference range as used in 802.11 or any kinds of packet collision caused by
special vehicle network scenarios. Consider a situation with two vehicles A and C,
which are more than two hops away and sharing a transmission slot. Another vehicle
B is only Ais l-hop neighbor but within C is interference range. In this situation, B
can not receive a message from A, since it will be corrupted due to the interference
from vehicle C. According to VeSOMAC/ISOMAC logic, vehicle B in this situation
will not acknowledge to Ais transmission in its bitmap, therefore vehicle A will
eventually move its time slot thus resolving the collision with C. This means that the
timing constraint in VeSOMAC/ISOAMC for 2-hop communication range turns into
an equivalent constraint for Z-hop interference range, when the latter is considered.”
5.2.2.7 Protocol State Machine Adaptation

Adapted VeSOMAC protocol state machine with all three constraints is presented

103

in Figure 5.5, and the equivalent pseudo-code is depicted in Figure 5.6. In general
VeSOMAC logic follows the same routine as ISOMAC logic. Only difference is the
adapted VeSOM4C has three constraints as opposed to two constraints in ISOMA C.
Since the asynchronous VeSOMAC relies on local clock for slot and frame timing,
the relative clock drifi between vehicles can move a vehicle’s transmission slot with
respect to those of its neighbors. This can perturb allocation stability of VeSOMAC
by progressively violating the mapping between the relative slot locations and the
information coded in the corresponding bitmap vectors. As a result, nodes can
transition from Stable to Evaluate state, thus affecting the stability of the protocol.
With periodic time synchronization using onboard GPS, the relative drift is

periodically reset, and therefore it is less of an issue for the synchronous VeSOMA C.

 

    
  
   
   

New vehicle 'oin

Choose fi'arn
[boundary points

 

‘ W’ flames are over

Choose a slot i

 

 

 
 

’ All three
‘ fiam rotocol
W es ‘ W’ frames are over p .
are n“ 0"“ AND all three mm?” are
. . satisfied
constraints are satisfied

 
    
  

 

Stable

 

 

Evaluate

   

Network topology
or relative vehicle
location change

 
      

‘ At least one

W’ frames are over constraint is not
AND at least one of the satisfied for ‘W’
three constraints is not consecutive frames

satisfied

Choose a new slot

 

 

Choose a new slot

 

 

 

 

 

 

 

 

Figure 5.5: Adapted State machine for the VeSOMAC protocol with all constraints

104

 

 

/* VESOMAC Protocol Logic for Each Vehicle */

Arbitrarily choose the MAC fi'ame boundary;
Listen:
Listen to the existing network for W flames;
// observe received transmissions to know the slot
// location of all I—hop neighbors; also observe the
// bitmaps in the l-hop neighbors' transmissions to
// know the slot location of all 2-hop neighbors
choose a slot using the logic described
in Section 2.3.6;
Evaluate:
Periodically transmit packets using the chosen slot
and listen from neighbors for W frames;
if (W is over && bitmap/timing/ordering constraints
are all satisfied)
goto Stable;
else{
Move the slot using the logic described in
Section 2.3.5;
goto Evaluate;
}
Stable:
Periodically transmit packets using the chosen slot;
If (violation of at least one constraint persists
for W frames){
Move the slot using the logic described in
Section 2.3.5;
goto Evaluate;

If (new neighbor vehicle arrives or topology
changes or packets get corrupted due to channel
errors) {/* do not change slot */

goto Evaluate;

}

 

Figure 5.6: Pseudo code for the adapted VeSOMAC with all constraints
Due to the capacity scarcity created by inappropriately dimensioned frame size (see
Section 3.4) when collisions are unavoidable in VeSOMA C, the optimality of
allocation can be defined as how fairly the collisions are cycled among the
participating vehicles. The objective is to prevent only a specific set of vehicles from
suffering repeated slot collisions while the others enjoying the available bandwidth.

According to the collision resolution logic in section 5.2.2.6, the implicit

105

 

acknowledgement mechanism in VeSOMAC forces the vehicles with colliding slots
to move their slots so that the slot collisions are uniformly and randomly shifted
around the vehicle in the neighborhood of limited capacity.

The model of flame size dimension in adapted VeSOMAC is same as in ISOMA C.

 

   
   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

VII/ITS Use Cases and their Mapping on Applications
(e.g. Collision Avoidance in Highway and Urban Intersections)
Drivers’ ‘
‘ IEEE Standards based Custom-built, Third-party '
Routing (AODV, Mobile IP) ‘ Routing Protocols
Vehicle-to-Vehicle and Vehicle-to-Infrastructure Message Routing
Vehicle and VII
Application
Interaction g
f: o
g ':
Vehicle 33 ‘5 WIMax MAC and Cellular Network
Following Logic L_t_.l :5 Physical Layer
>
Traffic and Human DSRC Physical Layer
Factor Modeling Available Wireless Technologies

 

 

 

 

 

Figure 5.7: VeNT Sim: ITS application and network evaluation/planning tool

5.3 Performance Evaluation

A hybrid simulation system for joint evaluation of different wireless network
technologies, including their MAC and routing protocols, ITS applications, and
vehicle following logic with drivers’ behavior has been developed for evaluating the
UICW and other applications under difi’erent MAC protocols. Figure 5.7 depicts the
architectural components of our VeN T Sim system which is designed to be open for
incorporating the evolving DSRC and other radio technologies, ITS applications [62],
and their required network protocols. Using VeNT Sim, Both DSRC and non-DSRC

radio technologies, including WiMax [62] and Cellular mechanisms [62] can be

106

 

architecturally evaluated for characterizing their impacts on heterogeneous ITS
applications and use cases outlined by the research community and various
standardization consortiums.

The networking functions in VeNTSim has been developed on top of ns-2 network
simulator [76] by adding a vehicle mobility module that can react to the received
wireless messages according to the modeled vehicle following logic with various
drivers’ reaction models. An ITS application modeling module capable of simulating
a series of ITS applications such as cooperative collision control, cooperative cruise
control and emergency vehicle preemption [62] has been also added The
synchronous version of VeSOMAC has been implemented at the ns-2 MAC layer, so
that they can be compared with the 802.11 protocol running in the same radio
environment. 802.11 is chosen for comparison is simply because it is the current
DSRC recommending protocol. The architecture of VeNT Sim is designed to be open
for incorporating evolving DSRC and ITS applications [62], and their required
network protocols.

5.3.1 VeSOMAC Protocol Convergence

Afier a network topology change, the convergence latency for VeSOMAC is
defined as the time interval from when at least one vehicle becomes unstable to
when all the vehicles become Stable, as defined in the state machine in Figure 5.5.
The scenario shown in Figure 5.8 corresponds to an instability triggered by a vehicle
passing 40 vehicles in a platoon. From the VeSOMAC standpoint, the platoon is

stable till the 8th frame, when the switching takes place. The vehicle passing causes

107

temporary instability by forcing at least two vehicles (not necessarily always the
passing and the last-passed vehicles) out of their VeSOMAC stable states. But

eventually, the network converges after 11 flames, which is 0.11 second for lOms

 

 

  
  

  
 

long flames.
51 T ; ; ; Q
. Convergence Latency: l
4 i 11 frames (0.11 Sec) 5
50«~- . ~~~~~ vvvvvvv ;

'l .
l 3 i
49-4 ————————— .__, ————————— -- ——-—q'» ———————— .——‘o————
.' l I
..
l ' 1

Number of Vehicles with Stable Allocation

 

 

47 . l . Q t '; , , g
1 6 11 16 21 26
Time (Frame Count)

 

 

 

 

Figure 5.8: VeSOMAC convergence dynamics after a topology change

5.3.1.1 Platoon Merger

Figure 5.9 depicts convergence performance when two platoons, with
individually stable VeSOMAC allocation, merge together. A bitmap size of 96 bits,
which is closed to the flame size (100 slots), has been used for eliminating the
bitmap constraint (see Section 3.3.2.2). Convergence during a platoon merger is
needed because certain vehicles within the merging platoons may have had slots that
can violate the timing and/or the ordering constraints after the merger. Therefore,
post-merger slot movements are needed to resolve such situations. Observer that the
convergence latency is always smaller without the ordering constraints, because

convergence in this case is needed for fewer nodes which violate only the timing

108

constraint. Also, the convergence is faster when two platoons of 10 and 40 vehicles
merge, compared to the 20 and 30 vehicles case. The results in Figure 5.9
demonstrate that during mergers of practical size highway platoons, the allocation
convergence latency of VeSOMAC remains within only few hundreds of milliseconds,
which are deemed acceptable for ITS related applications. It is also evident that the
ordering constraint in VeSOMAC logic can be used for trading reduced data plane

latency for slower protocol convergence.

1.4
E! VeSOMAC with Ordering Constraint Bitmap Length: 96 bits

5 VeSOMAC without ' Constraint * " Vehicle Spacing: 45 m ----- -—

i3

y—o

p
on

.O
as

9
4:.

A
O
0
VJ
V
>s
O
t:
0
fill
rd
t—l
0
O
t:
0
DD
1...
(D
E
O
U

_o
N

O

10 vehicles and 40 vehicles 20 vehicles and 30 vehicles
Sizes of the Merged Platoons

 

Figure 5.9: VeSOMAC convergence latency for platoon mergers

5.3.1.2 Intra-platoon Vehicle Passing

Figure 5.11 reports VeSOMAC is convergence performance when a vehicle passes
few vehicles in flont to get ahead in the platoon. Convergence after a passing is
needed because a passing vehicle’s slot can violate the timing and/or ordering
constraints of the vehicles that it is passing and the ones in the neighborhood of its

new location in the platoon. As expected, the convergence latency increases with

109

longer passing events because more vehicles’ slots are prone to be violated in these
cases. Also, the absence of the ordering constraint does expedite the convergence
process. For all the experimented scenarios within a SO-vehicle platoon, the
post-passing allocations have always converged within 100 ms, when the ordering
constraint was not used. Notice that the convergence time of 40 vehicle-passing is
the largest. The reason for is explained as followed. The slot distance between two
immediate vehicles is 2.5 slots on average. Considering the flame size is 100 slots in
our experiments. This means that on average every 40 vehicles, the slot position will
be repeated. As a result, passing 40 vehicles has the largest probability to have a
VeSOMAC slot collision. This explains why the convergence time of passing 40

vehicles is the largest. And the convergence would not increase as passing more

 

 

number of vehicles.
1.E+02
El VeSOMAC w/ Ordering Constraint itmap Lengthz96 b'

1.E+01 E VeSOMAC w/o ' ' ehicle Spacingz45 m
A . . - - . Passin time: Passin time:
3 1.E+00 Passrng tune: .Passmg time. .— _g . _ _ - -_ .......
V 450s
3‘
g 1.E-Ol
8
5 1.5-02
99
g 1.E—03
u

1.E-04

1.E-05

5 10 20 40
Number of Vehicles being Passed

 

 

 

Figure 5.10: VeSOMAC convergence latency for intra-platoon vehicle passing

VeSOMAC has a speed-aware component which prevents a passing vehicle from

110

perturbing the allocation stability of the vehicles that it passes at a higher speed. The
relative speed is inferred flom the vehicle-location and timing information in the
packet headers. A vehicle’s VeSOMAC state machine does not react to the
transmissions from neighbors with relative velocity larger than a pre-defined
threshold. This way, the effects of passing shows up only after the passing vehicle
settle down at a platoon location.

We have observed the convergence behavior with different size of the bitmap
vectors. As expected, since with larger bitmap size the bitmap constraint becomes
weaker, the convergence becomes faster. For example, in an experiment in which a
vehicle passes five other vehicles, the convergence latency was registered to be 0.54
sec. and 0.49 sec. for bitmap size of 72 and 96 respectively. With ordering
constraint turned on, the absolute values have dropped but they showed similar
bitmap dependency. This indicates that whenever possible, the largest possrble
bitmap size should be used for the fastest protocol convergence.

Although the evaluation has been focused primarily on highway situations, the
VeSOMAC architecture is fully extendible for other traffic and application scenarios
including data streaming, internet services, vehicle-to—roadside and urban
intersections, and bi-directional highway traffic.

5.3.2 Highway Scenario Performance

The experiments in this paper were carried out for the CCA application on a

one-lane highway platoon scenario [72] with DSRC radio communications. V2V

communication was leveraged for reducing chain vehicle crashes caused by

111

emergency events in flont of moving highway platoon. First, an emergency event is
simulated in flout of a moving platoon. Upon detecting the event, the platoon-flout
vehicle rapidly decelerates (8 m/s2) [77] and starts broadcasting periodic Wireless
Collision Warning (W CW) packets with the format (event-id, sequence-number).
While the event-id remains constant for an event, the sequence-number is
incremented within subsequent WCW packets, transmitted once in every lOOms [37,
66]. Upon receiving a WCW packet for an event for the first time, each vehicle in the
platoon starts decelerating (4 m/sz) [78] in order to avoid any impending collision
due to the emergency event. Also, it rebroadcasts the packet only when it receives it
for the first time. Fast and reliable WCW message delivery across the platoon is
expected to reduce the number of vehicles involved in a chain collision [66, 72].

The CCA application was simulated in the presence of background UDP traffic
generated by data intensive ITS applications. Because of their non-deterministic
message recipients, all CCA traffic is forwarded using MAC layer broadcasts
coupled with multi-hop broadcast forwarding [66]. The data intensive traffic is
unicast forwarded both at MAC and routing layers. Unless specified otherwise, we
have always used the worst case VeSOMAC allocation in which the TDMA slot
ordering is completely reverse to the vehicle ordering in a platoon. The purpose is to
evaluate VeSOMA C’s worst case application impacts compared to 802.11. The
baseline vehicle, network, and VeSOMAC parameters are summarized in Table 6.1.
Each presented data point corresponds to the average flom 500 independent

simulation runs.

112

 

Vehicle Related

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   
  

 

 

 

 

 

 

 

 

  

 

 

 

 

Platoon Size 50 vehicles
Vehicle Speed 68 mph (30 m/sec)
Inter-vehicle Spacing 25m to 45m 5 [0.8 sec to 1.5 sec]
Vehicle Length 4 m
Emergency Deceleration 8 m/s2
Regular Deceleration 4 m/s2
Drivers’ Reaction Time 0.75 sec to 1.5 sec
Network Related
Channel DSRC 5.9 GHz band, 24Mbps
Radio Model Two ray ground
Radio Range 300m
MAC Protocols IEEE 802.11 and Worst case VeSOMA C-Synchrorrous
WCW Packet Size 300 bytes (0.1 ms)
WCW Message Period 100 ms
VeSOMAC Frame Size 100 packets (10 ms)
VeSOMAC Bitmap Size 96 Bits (very weak bitmap constraint)
VeSOIlMC Evaluation Time W = 3 flames
Table 5.1: Baseline experimental parameters
50 '. .
3 Background Traffic:
.2 40 i _________________________________ 4O packets/sec/vehicle ”
3 l
U i
a 30 _l..z —-4-e___.--.-_._.___-_-._ .-.-.._--__i. __________
g -9-802.ll
5 e—VeSOMAC
t... ,
:2 20 -~ -- -- ~ - ~ - -
CU .-
OO .
c:
8 :
no? 10 .m— - a ._ -. j ._
’1 € ‘3
0 l l i r l
20 25 30 35 4O 45 50

Average Inter Vehicle Spacing (meter)

 

Figure 5.11: Efficiency of VeSOMAC for reducing vehicle crashes in CCA

application

113

 

 

5.3.2.1 Highway Vehicle Crash Performance

Effects of Vehicle Spacing: The number of vehicles crashed as a percentage of a
50-vehicle platoon is plotted in Figure 5.11. With the CCA system turned off, if the
vehicles decelerate based only on the tail brake light of the flont cars, then for this
entire range of vehicle spacing, all cars in the platoon were found to crash in a chain
collision. However, as shown in Figure 5.11, by turning the CCA system on, with
VeSOMAC as the MAC layer protocol, it was possible to bring the platoon collision
down to 8%, when the vehicle spacing is nearly one second (i.e. 30 111). With 802.11,
however, the vehicle crash probabilities are observed to be significantly higher,
especially for closely following vehicles. As expected, fewer vehicles crash with
increasing vehicle spacing. This is because with larger inter-vehicle space a vehicle
gets a longer time cushion for safely decelerating to a stop before crashing into the

vehicle in flont

 

 

 

 
  
 

 

 

 

 

 

 

 

 

 

 

 

 

70 . ,
+VeSOMAC; Spacing: 45 m
35,60 TIM—”H“!— iiiiiiiiiiiiiiiiiiiiiii i-BK-802.11;Spacing45m V
g 50 w, - _ _. - - ._ ' . ,. -. _. , . _. ,. _ .. -a-VeSOMAC; Spacing: 25 m
g . -B-802.ll; Spacing 25 m
940 __,,._-,,,_,_,__________,,__, ........... .--._--_.._—____T. ........... .-
2 ; 802.11 :
a. . ‘ .
‘8 30 + ‘
0
2? , . .
5 2° ‘ “““““““““ i """"" ' ““““““ "‘;S‘C;,‘,;.g,"i ““““““
3 . g “V . s. .
a" 10 —»— .. u as -1- um-.-~u-.....-—.L\.
e c c e <>
0 l l
0 2O 40 60 80 100
Background Traflic (Packets/Sec/Vehicle)

 

Figure 5.12: The effects of background non-safety traffic on avoiding vehicle crashes

114

Effects of Backggound Traffic: As shown in Figure 5.12, the performance
advantage of VeSOMAC over 802.11 is maintained for a large range of background
traffic load flom the non-safety applications. Unlike 802.11, for which the MAC
layer delivery delay goes up with the background traffic due to increased access
contentions, the TDMA based VeSOMAC’s delay is virtually insensitive to the
amount of background traffic. This is because of zero packet collisions, which
explain why the vehicle crash count remains flat for VeSOMA C with increasing
background traffic. For 802.11, on the other hand, the crash count increases linearly
beyond background traffics of 25 ppsv and 35 ppsv for vehicle spacing of 25m and
45m respectively.

The cross-platoon message delivery latency for an example run of CCA with
VeSOMAC is presented in the top graph of Figure 5.13. Latency is defined by the
duration between when the emergency event occurs at the platoon front and when a
corresponding WCW message is delivered to a vehicle. Relative stop distances
between consecutive vehicles are reported in the middle graph. Since the vehicle
length is assumed to be 4m, any relative stop distance of 4m or less corresponds to a
crash. For vehicles avoiding a crash, the relative distance thus indicates the margin
of safety provided by CCA. The bottom graph further reports the severity of vehicle
crashes in terms of the relative speed between two crashing vehicles. Any relative
speed which is greater than zero indicates a crash, and its magnitude indicates the

crash severity.

115

 

—R6 ,
0'05 VeSOMAC: Vehicle spacing: 30 meters

 

8 0.04 «
m

10.03:

g .

2 0.02~
illlllllllllllll”

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

La

 

 

O

 

Vehicle Position In Platoon

 

 

 

60
50 ; Relatiie distance between consecutive whicles after stop

02
O: I III I I I III I I III 36:II46 II I
o 25"III! I I I II [I I II III I I I

Distance (m)
N u
o

d
O

 

 

 

rIrIrIrIIrrvrrrIrIr Yvrrr'l rIr' rrrrrlr rv 1W! '7' r rrrv r rrrurr vvrrr Ir 1 r rrrr rv rv rrru'rrrr—rrvrrr

20
15
10
. |

Figure 5.13: Latency and crash statistics for CCA with VeSOMAC

Vehicle Position In Pbiozn

 

 

 

Speed ditterence between two consecutive: vehicles aner stop

Speed (m/s)

1!! llllllllllltltlllllltvlrlIlvlvvvllttvrlvyrr rvlrrvlvlvvvlrlvvrlrlIllllvlvvlvvrlrrrrivvlr

11 16 2126 31 36 41 46
Vehicle Position in Platoon

 

 

 

Results for an example CCA run with 802.11 MAC are reported in Figure 5.14.
For VeSOMAC, since there are no packet collisions and the cross-platoon latencies
are very small (up to only 51 ms), the only crashes are in the platoon front. These
crashes are due to the lack of enough distance cushions and cannot be avoided with
CCA even with zero message delivery latency. For 802.11, due to packet collisions
and delay unpredictability, the WCW message latency increases significantly
towards the rear of the platoon, where the broadcast traffic load increases

progressively. This abrupt increase in latency flom few milliseconds to few seconds

116

causes a cluster of vehicles to crash due to insufficient reaction time for their drivers
to brake. This explains the chain crashes at the middle of the platoon. For the
vehicles towards the rear, although the absolute latencies are very high, the relative
latency is small. Therefore, all vehicles get suflicient time to react, thus avoiding
crashes. This explains why there are no crashes towards the platoon end. Crash
performance flom these example CCA runs with VeSOMAC and 802.11 are
consistent with the average crash results flom 500 different experiments presented in

Figure 5.11 and 5.12.

 

100 ,
10 802.11: Vehicle Spacing: 30 meters
1
0.1
0.01

 

 

Latency (Second)

9
O
O
.5

 

 

 

 

 

 

 

0.0001

1 6 11 16 21 26 31 36 41 46
Vehicle Position in Platoon

 

 

 

70
so Relative distance between consecutive vehicle afier stop
50

 

Distance (m)
8

 

1 6 1 1 16 21 26 31 36 41 46
Vehicle Position in Platoon

 

 

 

25 Speed dlfierence between two consecutive vehicle after stop
20

10

Speed (m/s)
'o‘a

 

 

1 6 1 1 16 21 26 31 36 41 46
Vehicle Position in Platoon

 

 

 

Figure 5.14: Latency and crash statistics for CCA with 802.11

117

 

 

 

'0- VeSOMAC Worst: 25 meters

- ‘5- VeSOMAC Worst: 35 meters 7 i 7 I

80 -: “fir-VeSOMAC Worst: 45 meters — - . .. - -

70 El *802.ll: 25meters
f 91+ 802.1]: 35 meters

60 -I -9- 802.11: 45 meters

5

0"VV "

   
  
  

 

 

 

rul r

 

Percengate of Platoon Collided

 

 

 

 

 

 

 

 

40 i
30 1]
20 E
1
10 ii »
O I mm fiT fl#1 l T
0 20 40 60 80 100
Packet Error Rate (%)

 

 

Figure 5.15: Effects of channel error on cooperative collision avoidance

Effects of Channel Errors: Crash performance with independent bit errors (no
fading and burst errors were modeled) are reported in Figure 5.15. With increasing
packet errors up to 80%, VeSOMAC is crash performance is insensitive to the errors,
whereas for 802.11, the crashes steadily increase. For 802.11, with increasing
channel error, latency for successful reception of a WCW message progressively
increases towards the platoon end. This delay is compounded by 802.11’s own
contention related packet drops. As shown in Figure 5.14, higher latency translates
into more vehicle crashes. With VeSOMA C, the latency was found to be low and
steady for up to the 80% error mark. This low latency is due to the fact that in the
absence of MAC collisions, a vehicle receives a specific WCW message several
times - once flom each of its neighbors. Therefore, in spite of certain number of

packet losses due to channel errors, the vehicle is still able to receive at least one

118

copy of the message flom an emergency event. VeSOMAC is low latency and the
subsequent insensitivity to channel errors are because this reception redundancy. For
error rates beyond 80%, however, the delay and the vehicle crash count shoot up.
Packet drops beyond 80% is not practical, and they are shown only for
understanding purposes.

Within the practical range of channel errors, the crash performance expectedly
worsens with smaller inter-vehicle spacing for both the protocols. With very large
packet rates though, there is an interesting trend reversal in which closely spaced
vehicles actually suffer flom less crashes. The reason for this turned out to be higher
reception redundancy at lower inter-vehicle spacing.

Based on these results we conclude that the proposed VeSOMAC protocol offers
significantly better CCA vehicle crash performance compared to the DSRC proposed
802.11 protocols. In fact, within an acceptable packet error of less than 10%,
VeSOMAC shows no sensitivity to errors.
5.3.2.2 Highway Data Plane Network Performance
5.3.2.2.] Cross-platoon Message Delivery

Deliveg Delay: Experiments were carried out with both VeSOMAC and 802.11
protocols with varying levels of background unicast load generated using a Poisson
traffic model. For a 50-node platoons, the multi-hop WCW message delivery delay

to vehicle number 49 is depicted in Figure 5.16. In addition to the worst case

 

The platoon-front vehicle that encounters the emergency event is number 0 and the vehicle at the

platoon end is number 49.

119

allocation (see Section 5.3), a version of VeSOMAC with the ordering constraint
turned on has also been experimented with. With increasing background traffic, the
cross-platoon latency goes up for all the protocols due to increased MAC and
queuing delays. However, compared to VeSOMAC, the delay for 802.11 is much
more sensitive to the background data rate. With 802.11, for traffic higher than
approximately 33 ppsv, the latency goes beyond seconds. With both versions of
VeSOMAC however, the delays are constrained within only tens of milliseconds even
for traffic rates as high as 90 ppsv. This large comparative latency of 802.11 further

explains its poor CCA crash performance as shown in Figure 5.11 and 5.12.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1000 I T we;
g I802.ll , ;
Z), 100 ___ IVeSOMACzwith OrderingConstraint , _,,,__
‘5; E VeSOMAC: Worst Case Allocation 1 i
* i % r s 2 s ' x
g 10 _ _,.-__.~,.__.._.__.-.-._,,____--_,_-___12 -..r_-_m-fw___,~_--:_..---.j._-__
Ir 1 , ,
.‘e.’ ‘ . it ' * f
a :1 ? i :5 : : : :
Q 1 d W A I I 7 I ‘ kh‘i *Vffi" - I IV 7'
g 1 I ‘ 5/ i i E
: 1’ r r l l
8 * I a l/ l l I l
3 - : t l 1/ l l l l
‘3‘ 0-1‘ 3’ 17"“? "i” ‘I """" T iiiii 1”" T"
8 “:1 E: :5 E :5 a: : f i t ?
8 a. a. .g 5 M . . ; . , :
o = ._ = g I, = g . , I . , 3
0.01 a I i I I I i I ' I '
10 20 25 30 35 40 45 50 60 70 80 90
Background Data Rate (Packets/SecNehicle)

 

Figure 5.16: WCW message delivery latency across the entire platoon

At lower rates (i.e. between 10 to 20 ppsv), there is no queuing latency for both
the protocols, and the MAC delay for VeSOMAC is actually larger than that of
802.11. This is because unlike in 802.11, for TDMA protocols a half-frame average

MAC latency is there irrespective of the data rates. As the data rate increases, the

120

802.11 delay increases at a much faster rate due to MAC layer collisions,
retransmissions and carrier-sensing delays. For VeSOMAC however, there are no
such delays at the MAC layer at steady state. As a result, the queuing efi‘ects are also

less severe. These account for the lower rate sensitivity for the VeSOMAC delay.

 

 

 

 

 

 

 

 

 

 

   

 

 

 

 

802.111End-to-End Message Delivery Delay (Sec)
1 3 5 7 9 11 13 15 17
U 50 J_LL1;4':L1 1.1111111 rl 1T 1’1 1 1‘1 ’1 #LT1%+ L¥1 :17: ‘l L[II‘ 30 f;
g -9-VeSOMAC: with Ordering Constraint E e:
o 40 4 ____ -£I-VeSOMAC:WorstCaseAllocation _125 3,
g r f ; ' : +8021] E 8
> , I A I . . . . . j _ 00
I: ' .. .II:205
3 30 ~~l~~~ - -f:-~-’ ;--3-%---+-ZHEHtHI-fi-“IHE-‘i-i-r-r '5
3 A I i I ‘ I . z I I I I I I I I I L 3
-'° o\° . : ' ' . - 15 --
5 V | l 0 ; ; . :Background Traffic. I a
g 20 ‘ ' " ’05“? 45ppsv *: '5
.‘E‘ ;;,.:E:§::,-10§.
:s‘ Io—— — .— — : '5
~§ ; 3231,i:,i‘iisia:5§
5: :f W“;:'::W::,::;m m
01:3: --_;.-_-_ “ ‘."‘vl‘l'l‘l'l'l'l'l'l“1r O
0.005 0.025 0.045 0.065 0.085 0.105 0.125
VeSOMAC: End-to-End Message Delivery Delay (Sec)

 

 

Figure 5.17: Distribution of cross-platoon delivery latency for 802.11 and VeSOMAC

Delay Distribution: Distributions from 500 experiments involving message
deliveries to the platoon-end vehicle are plotted in Figure 5.17. For 802.11, the
distribution has a much wider spread (tens of seconds) compared to both the versions
of VeSOMAC (only tens of milliseconds). Unlike 802.11, since VeSOMAC does not
have stochastic delay due to carrier sensing, collisions, and retransmissions, its
latency is deterministic. This explains the low delay jitter for VeSOMA C, which not
only contributes to its better CCA crash performance, but it can be also beneficial for
inter-vehicle audio and video streaming applications [62].

Packet Drops: Drop statistics for the WCW safety messages across the platoon is

121

presented in Figure 5.18. Due to collisions, 802.11 is susceptible to frequent packet
drops. For instance, with a background data rate of 45 ppsv, on an average an 802.11
based CCA application would loose the first WCW message by the time it reaches
the 24m vehicle in the platoon. Meaning, if the platoon-front was not periodically
sending the WCW messages, the vehicles beyond the 24th vehicle would not have
received the message, thus suffering from the possibility of chain crashes. Similarly,
the 2'Id WCW message gets lost by the time it reaches the 32"d vehicle. However,
because of zero collisions, VeSOMAC can deliver the very first WCW message to all
vehicles in the platoon. The results from Figure 5.18 reinforce the CCA crash

performance findings in Figure 5.11 and 5.12.

 

 

 

3.75

‘ +802.“ : ‘
-0-VeSOMAC: with Ordering Constraint 2 . ' e : = = = = -_- =
-A-VeSOMAC: Worst Case Allocation ' " ' — '

 
      
     
  
 

 

 

 

L 1

 

N

\l

kit
1

.....-u..__-....r......-.......-m......-r--._.«.-..._.....

W Second message is
dropped by the 32th

vehicle ‘

 

Background Traffic:
45 ppsv

 

 

 

 

 

 

 

~ * * First message is dropped
by the 24th vehicle

 

 

 

First Received Sequence Number

4——-

 

 

 

0 10 20 30 40 50
Vehicle Position in Platoon

 

 

 

Figure 5.18: Message drop at different platoon locations

5.3.2.2.2 Benefits of Location-aware Slot Ordering
Cross-platoon latency performance for the worst, the average and the best case

VeSOMA C are presented in Figure 5.19. The best and the average cases represent

122

VeSOMAC with ordering constraint turned on and off respectively. And the worst
case represents a forced allocation in which the TDMA slot ordering is completely
reverse to the vehicle ordering in a platoon. For a low background data rate of 10
packets/sec/vehicle (ppsv), VeSOMAC with ordering constraint is able to deliver a
WCW message to the platoon-end vehicle approximately 21 .5ms sooner than the
average case (without ordering constraint), and approximately 45ms sooner than the
worst case allocation. This indicates that the ordering constraint in the VeSOM4C
logic (Section 5.2.2.7) can indeed achieve reduced multi-hop packet delivery latency

through a location aware slot allocation.

 

 

 

.0
N
I

1 -9-VeSOMAC with Ordering Constraint: 10 ppsv - - ,_ , ,_ -- .- - - -
3 43- VeSOMAC with Ordering Constraint: 90 ppsv
:- + veSOMAC: Worst Case:10ppsv J ____
I -)K- veSOMAC: Worst Case:90ppsv ‘ . = '- ”

High BackgroundrTraffic ’ _ -. ’- ’ 5

~_...' .......—.....—.~. ___—......

.o
h
Ox

1

i

I

I

J.

I

I

 

 

 

 

i
It
6".»
|| '
I
I

j - ,, .7 ofat-Amt-" - 1 i A .. a a

[ ,av" ‘ Z |VeSOMACz Average Case: 10ppsv I

.. . 2 ”Low Background Traffic 1 i
H--_‘.\. “---: --q ...............

 

 

Message Delivery Latency (Sec)
9
S

 
 

P 9
o c:
4:. oo
1 l

 

 

 

 

 

 

 

0 I 7 T T l I I T T l' I fir fir T I 7 I I I l I I I r

0 10 20 30 40 50
Vehicle Position in Platoon

 

 

 

Figure 5.19: Effects of the ordering constraint on delay for VeSOMAC

However, for higher background data rates (e.g. 90 ppsv) the delay differential
between with and without ordering constraint scenarios are less prominent. This is
because packet queuing at higher rates introduces delay, which makes the cut-though

forwarding with ordered TDMA as explained in Section 5.2.2.2 not possible. With

123

the present experimental setup, the benefits of ordering constraint were found to be
preserved for rates up to approximately 46 ppsv.
5.3.2.3 Highway Scenario Performance during VeSOMAC Reorganization

Although the performance of CCA with TDMA at its steady state allocation is
consistently better than that with 802.11 MAC, the majority of TDMA protocols
(with a notable exception of the protocol LCA [41]) suffer from transient instability
during slot reorganizations triggered by network topology changes due to vehicle
movement. The results in this section report the impacts of such TDMA slot
reorganizations on an ongoing CCA process.

Controlled vehicle movements in terms of vehicle passing within a 50 vehicle
were created for triggering slot reorganization. The vehicle passing events were
created in a way so that each such event is able to give rise to a temporary (before
the reorganization process is able to converge) slot collision between a passing
vehicle and the vehicles being passed. As a result of such collisions, the WCW
message propagation within the platoon is blocked, thus causing potential vehicle
crashes. Sequential vehicle passing events are designed in a way that each vehicle
passing event is able to block the WCW message relay within the platoon for one
WCW message cycle period, which is 100ms. In other words, with k consecutive
passing events, the WCW messages generated in k number of consecutive WCW
message cycle periods are blocked from propagation within the platoon.

Each vehicle passing event involves a simultaneous group passing movement of 6

adjacent vehicles and subsequent slot collisions between all those 6 vehicles and 6

124

other vehicles that are being passed. In total, there are 12 vehicles that are involved
in one passing event. For the given radio range and inter-vehicle spacing as reported
in Table 6.1, 6 represents the minimum group size that is required for completely
blocking a WCW message due to temporary collisions caused by the TDMA slot
reorganization process. The vehicle crash performance with different number of

sequential passing events is shown in Figure 5.20.

 

 

 

 

 

 

 

 

 

 

60 »
E ; \802.11
840 ._ .. , .....
3 .
.9. 30 r . ,
5 : ;
g: 20 _. V.TDMAf:reconfig. . ,
g\ 10 _ ¢ ; 4TBMA£ reconfig.
O i i I l
0 I 2 3 ‘ 4 5
Number of Sequential Passing Events

 

Figure 5.20: Impacts of TDMA slot reorganization during a UICW process

From Figure 5.20, it can be seen that since each passing event involves 12
vehicles, there are at most 4 sequential passing events possible within a platoon of
50 vehicles. Each passing event causes the WCW message propagation to be delayed
by a complete WCW cycle period of 1001115, which is sufficient for two more
vehicles in the platoon to crash. This explains as to why the percentage numbers for
the crashed vehicles in Figure 5.20 increases linearly with the number of sequential
passing events. Note, however, that for this experiment with 50 vehicles on the

West-to—East street, the maximum percentage of platoon collided for TDMA is only

125

24%, which is less than half of that with the 802.11 MAC, which is 52%. The graph
for TDMA without MAC reallocation depicts the baseline CCA performance in the
absence of vehicle passing or other similar events that can trigger slot
reorganizations.

Note that although not very practical, a large passing vehicle group size of six is
chosen just to ensure guaranteed blockage of the WCW message. This serves a stress
test for the TDMA protocol in the context of the targeted CCA application. In order
to study the impacts of more practical group sizes, experiments were carried out for
groups of 1 through 5 vehicles. Since the WCW messages are not able to be
completely blocked in these situations, the vehicle crash count of CCA did not get
any worse than the baseline performance with steady state TDMA, as reported in
Figure 5.20. For the crashed vehicles, the collision speed in the experiments was
found to be increased by at most 0.04 meters/sec. From the results in this section, it
can be concluded that although the slot reorganization in TDMA due to network
topology changes does degrade the CCA application performance temporarily, in an
absolute sense it still remains better than that with the 802.11 MAC protocol.

5.3.3 Urban Traffic Intersection Scenario
5.3.3.1 flrban Intersection Collision flaming (UICW)

The urban Intersection Collision Warning (UICW) application is designed for
Cooperative Collision Avoidance (CCA) [62, 66] in urban traffic intersections using
vehicle-to-vehicle DSRC communications. A representative UICW execution is

described in Figure 5.21, which depicts a situation when the South-to-North traffic

126

light is red and the West-to-East light is green. Vehicle crashes in such a situation can
occur if a bad driver on the South-to-North street runs the red light and collides with
the cross vehicles in the West—to-East street. Once a single vehicle on the
West-to-East street crashes with the bad driver’s vehicle, a chain crash may also

occur due to insufficient reaction time and stop distance available to the drivers of

1‘ .
I Slgnal ‘ Red
' I Signal - Green

Car-3 Car-2 :Car-1 C r /
- - — -)

22-“)?

I
l
I

\ Vehicle with
N 1‘ Bad Driver
- ......... '\
I i I ' WCW Message
I

Generation "Threshold

the West-to-East street.

 

   

Cross-street
Vehicle Position

  
  

 

 

 

 

 

 

- ' ' : Position of the front cross-street vehicle
when the vehicle with bad driver crosses the WCW message threshold

 

 

 

 

Figure 5.21: Cooperative Collision Avoidance in an urban intersection scenario

However, when the UICW application is turned on, such crashes can potentially
be avoided or mitigated using the following mechanism. The DSRC onboard unit in
the bad driver’s vehicle first detects a problem situation from the vehicle’s speed and
location with respect to the intersection point. If a problem situation is detected so
that the vehicle reaches a threshold distance from the intersection (referred to as the
WC W Message Generation Threshold in the Figure 5.21) at a high speed while the
traffic light is red, the onboard unit starts broadcasting periodic Wireless Collision

Warning (WCW) packets, one in each message cycle period. A tuple containing the

127

identification of the originating vehicle and a monotonically increasing sequence
number is used in the WCW messages for their unique identification. Upon receiving
a WCW packet for the first time, each vehicle on the West-to-East street starts
decelerating after a driver’s reaction time, in order to avoid any impending collision
due to the event. Also, the vehicle on the cross-street rebroadcasts the WCW packet
when received for the first time. Note that the Cross-street Vehicle Position in Figure
5.21 represents the position of the front cross-street vehicle when the bad driver
crosses the WC W Message Generation Threshold point. Although the WCW
message is generated by the bad driver’s vehicle in the above explanation, it can also
be generated by a roadside infrastructure by measuring the speed of the violating
vehicle at the generation threshold point, and by noting the status of the traffic light.
Once the WCW message is generated by the roadside infrastructure, the same logic
involving the WCW message interpretation applies.

Depending on the network protocol efficiency, vehicle speed, and the inter-vehicle
spacing, a significant number of the cross-street vehicles can be saved using the
UICW application as outlined above. From the network standpoint, the delivery
delay and reliability of the WCW messages from the bad driver’s vehicle to the
cross-street vehicles play a crucial role in reducing the number of vehicles involved
in a chain crash.
5.3.3.2 UICW Operational Details

Figure 5.22 illustrates the dynamics of a chain crash after the front car (Car-0) on

the West-to-East street collides with the vehicle with bad driver on the

128

South-to-North street. For the sake of clarity, the dynamics of only three vehicles are
presented in Figure 5.22. The y-axis in Figure 5.22 represents the vehicles’ positions
in terms of the distance from the street intersection point, as a function of time. As
shown in the figure, the driver in Car-l starts decelerating when he or she sees the
tail brake light of Car-0, and the driver in Car-2 and Car-3 do so when they see the
brake lights of the vehicles ahead. Note that a vehicle starts decelerating after a
driver’s reaction delay following when the vehicle ahead applies its brake. In Figure
5.22, with a finite driver’s reaction time, Car-O gets hit by Car-1 at the intersection
point. Subsequently, Car-l is hit by Car-2, and Car-2 is hit by Car-3. This example
shows when the drivers react solely on the visual information (tail brake light), how

all the vehicles on the West-to-East street can end up in a chain collision.

 

Cars-O a bad Cars-1 Collides 03.3-2 Collides

 

 

 

 
    

  

 

 

driver Collide with Car-O with Car-1
\ \

Intersection fl

Point
Driver .
Reaction Time

¥ ; : Vehicles apply
3 l brake on tail light
Distance to :
intersection '

 

 

Time (sec) ,

 

 

Car-O Car-1 Car-2

 

Figure 5.22: Dynamics of a cross-street chain collision without UICW
For the same scenario, the usefulness of UICW application is illustrated in Figure
5.23. With UICW [62] turned on, all West-to-East vehicles apply their respective

brakes and start decelerating afier a combined delay of Wireless Collision Warning

129

(W CW) message delivery and a driver’s reaction time following the generation of
the WCW message by the vehicle of the bad driver. In the depicted instance in
Figure 5.23, for the given WCW delivery latency and the driver’s reaction time,
although the driver in Car-0 is able to apply its brake, due to insufliciently available
stop distance the vehicle is not able to avoid a collision with the vehicle in the

South-to—North direction.

 

      
   
  
 
      
     

Car-0 brakes on Cars-O & bad
WCW Reception driver Pollide

Cars-1 collides with
Car-0 when the WCW

latency is large (T 1)
\Cars-1 stops safely

when the WCW
latency is small (T 2)

 

Intersection
Point

\

a...” K

Cars-2 stops safely for
both small (T 2) and large
(T 1) WCW latencies

,,,,,,,,
.......

'-
'-
'c
o
'0
'0
'0
o
o

 

Car-1 and Car-2 brake
on WCW Reception
with large delay (T 1)

     

 

 

 

 

 

 

 

 

Distance to i E ’//////// wcw Delivery Latency
Intersection E E |:] Drivers’ Reaction TIme
' . Time (sec) ’
Car-O Car-1 Car-2 Car-1 and Car-2 brake
. on WCW Reception
Tune of WCW -
Generation WIth small delay (T 2)

 

Figure 5.23: Leveraging UICW for reducing intersection vehicle crashes
For Car-l and Car-2, two scenarios are explored: with a large WCW message
delivery delay T1, and a small delivery delay T 2. For the same driver’s reaction
time, while the smaller WCW latency can save Car-l, the larger latency cannot. For
Car-2, however, because of its sufficiently available stop distance a crash can be

avoided even with the large WCW delivery latency. The scenarios in Figure 5.22 and

130

5.23 illustrate that: a) the UICW application can indeed reduce vehicle crashes when
the vehicles in the West-to-East street rely on wireless warning messages, and b) low
message delivery latency is a key to the overall success of this ITS application. This
also reinforces the need for a MAC layer protocol with low and deterministic
delivery latency. The core logic for WCW message generation and interpretation are

shown as the pseudo-code in Figure 5.24.

 

 

/* WC W msg Generation Logic at the vehicle with bad driver*/
do{
keep checking the vehicle speed,
distance to the intersection,
and traflic signal status;
if(this vehicle will be unable to stop before intersection
&& the traflic signal is currently red
&& distance to intersection < = threshold distance){
/* the vehicle is exepected to run a red light */
Start originating WC W msg. periodically;
}
}

/"‘ Message Interpretation Logic at the West-to-East vehicles */
/* A WC W Message arrives at a West-to-East vehicle */
check the message origantor and sequence number;
if(new msg. origantor){
store new msg. origantor id and seq. #;
rebroadcast the msg;

 

 

}

else {
if(seq. # is new) {// newly updated msg.
store new seq. #;
rebroadcast the msg. ;
}
else{// received old msg.
drop the msg;

}

 

 

 

 

 

 

Figure 5.24: Pseudo-code for the WCW generation and interpretation in UICW

5.3.3.3 Multi-slot Message Broadcast with TDMA MACS

131

With TDMA MAC, when the vehicle with bad driver in the UIWC application
generates its WCW message, there is a possibility that this message will collide due
to a MAC slot overlapping between the generating vehicle and at least another
vehicle within its wireless range on the West-to-East street. Such collisions can occur
before a TDMA slot reallocation can take place as a response to the network
topology change caused by the vehicular movements. From an UIWC crash
avoidance standpoint, these collisions can prove fatal and need to be avoided.

We introduce a multi-slot MAC broadcast mechanism in which the WCW
generating vehicle sends the message on multiple TDMA slots in a flame, in addition
to on its own allocated slot This way, if the generating vehicle’s slot does collide
with that of a cross-street vehicle, the redundancy in the multi-slot MAC broadcast
will improve the chance of a collision free transmission of the WCW message. The
redundant slots are chosen randomly within the TDMA frame during the successive
WCW message transmission to avoid any persistent collisions, thus further
improving the chance of successful delivery of a WCW message. For a UICW
scenario with vehicle density D (average number of l-hop radio neighbor of a
vehicle) and frame size F (number of TDMA slots per frame), if the multi-slot MAC
broadcast redundancy is n (the number of TDMA slots used for a multi-slot MAC
broadcast), then the probability of a collision free WCW transmission can be written
as: 1 — (D/F)n . Note that the multi-slot MAC broadcast is needed only for the
UICW safety application and is not enabled for data intensive non-safety

applications.

132

5.3.3.4 Urban Traffic Intersection Experimental Setup

For the evaluation in this paper, we have used DSRC as the radio technology with
a custom-built message forwarding for UICW, and DSDV [79] routing for
non-safety data intensive applications. The vehicle following logic in UICW
comprises of the intersection traffic rules, and the drivers’ behavior is modeled in
terms of the reaction time with different ranges and distributions. A synchronous
version of TDMA (VeSOMAC [73, 74]) has been implemented at the ns-2 MAC
layer so that its impacts on the chosen applications can be compared with the current

DSRC recommended 802.11 running in the same radio environment.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Vehicle and Scenario Related
Platoon Size 50 vehicles
Vehicle Speed 45 mph (20 m/sec)
Inter-vehicle Spacing 9m to 15m E [0.45 sec to 0.75 sec]
Vehicle Length 4 m
Emergency Deceleration 8 rn/s2
Regular Deceleration 4 rn/s2
Drivers’ Reaction Time Fast [0.5 - 1.0 sec], Slow [0.75 - 1.5 sec]
WCW Msg. Generation Threshold Dist. 50 m
Cross Street Vehicle Position 20 m to 50 m

Network Related

Channel DSRC 5.9 GHz band, 24Mbps
Radio Model Two ray ground
Radio Range 100m
MAC Protocols IEEE 802.11 & Synchronous VeSOM4C
WCW Packet Size 300 bytes (0.1 ms)
WCW Message Period 100 ms
TDMA Frame Size 100 packets (10 ms)
Channel Packet Error Rate 5%

 

 

Table 5.2: Baseline experimental parameters for the UICW application simulation
The UICW scenario was simulated in the presence of background UDP traffic

generated by non-safety ITS applications. Due to their non-deterministic message

133

recipients, all UICW traffic is forwarded using MAC layer broadcasts and multi-hop
broadcast forwarding [66]. The non-safety background traffic is unicast forwarded
both at MAC and routing layers. The baseline simulation parameters are summarized
in Table 6.2. Each presented data point corresponds to the average from 500
independent simulation runs.
5.3.3.5 Urban Traffic Intersection Vehicle Crash Performance

The percentages of 26 vehicles (25 cross-street and one bad driver) that crash
during the simulated incident are reported in Figure 5.25. When the UICW is turned
off, the drivers respond only to visual information, and a large number of cross
street-vehicles crash. It was observed that one vehicle first collides with the bad
driver’s vehicle, and then the vehicles behind engages in a chain collision. With no
UICW, at 45 mph vehicle speed, even with a large vehicle spacing of 15 meters,

almost 75% of the cross-street vehicles crash due to the red light running of the bad

 

 

 

 

 

   

 

 

 

 

 

 

 

 

 

driver.
100
'8
E 80 T"
8
m 60 “—
.2
O
'43 _
> 40 7" ‘
‘H i
o _ r
c,\<’ 20 —— Fast Drivers' . - .;_ -
Reaction u 2 ~21
0 1 I \ VeSOMAC
8 10 12 14 16
Inter Vehicle Spacing

 

Figure 5.25: Vehicle crash performance with 802.11 and VeSOMAC

134

5.3.3.6 Impacts of MAC Protocols

When UICW is turned on, with VeSOMAC as the MAC protocol, it was possible
to bring the crashes down to nearly 13% (3 vehicles), which is with 15m spacing and
fast drivers’ reactions (0.5-1 second). With 802.11, the vehicle crash probabilities are
observed to be significantly higher; i.e. 39% for 15m spacing and fast drivers’
reactions. As expected, fewer vehicles crash with increasing vehicle spacing. This is
because with larger inter-vehicle space a vehicle gets a longer time cushion for
safely stopping before crashing into the vehicle in front. Also, a fast drivers’ reaction
time helps to prevent the collision as shown in Figure 5.25. The reason that
VeSOMAC has much smaller collision number can be explained fi'om Figures 5.26
and 5.27 as followed.

The cross-platoon WCW delivery latency for an example run of UICW with
VeSOMAC is presented in the top graph of Figure 5.26. This latency is defined by the
duration between when the bad driver’s vehicle generates the first WCW message
after crossing the threshold point (see Figure 5.21) and when it is delivered to a
vehicle. Relative stop distances between consecutive vehicles are reported in the
middle. With a vehicle length of 4m, any relative distance of 4m or less corresponds
to a crash. For vehicles avoiding a crash, the relative distance thus indicates the

margin of safety provided by UICW.

135

 

 

0.05
Warn'ng Message Delivery latency

s:
E
%

0.03 -L
0.02 -~
0.01 -

Latency(Second)

Message Delivery

 

C
I

l 3 5 7 10 ll 13 15 17 19 21 23 25
Veh'cb Posiion in Cross- Street Platoon

 

 

 

30
25 4 Rehtive distance between consecutive ve17mlee after stop
20 r
15 -
10 -
5 ..

Distance (m)

 

l 3 5 7 9 l 1 13 15 l7 19 21 23 25
Vehicb Posit'nn '11 Cross- Street Platoon

 

 

 

12 ‘ Speed dfirence between two comecutives veh'nles afier stop

Speed (m/s)
0‘

 

o _ l 1 l 1 1 l I I I L 1 1 l l I l 1 l l l I l
I I I I I I I r I I I I f I I I I I I I I I

0 2 4 6 8 10 12 l4 l6 18 20 22 24
Vehicle Posit'nn in Cross- Street Phtoon

 

 

 

Figure 5.26: Latency and crash statistics for CCA with VeSOMAC

The bottom graph reports the severity of crashes in terms of the relative speed
between two crashing vehicles. Relative speeds greater than zero indicates a crash
and its severity.

Similar results for an example UICW run with 802.11 MAC are reported in Figure
5.27. For VeSOMA C, since there are no packet collisions and the cross-platoon
latencies are very small (up to only 43 ms compared to seconds in 802.11), the
crashes involve only the front of the cross-street vehicles. For 802.11, due to packet
collisions the WCW latency increases significantly towards the rear of the cross

street vehicles. This increase in latency causes a cluster of vehicles to crash due to

136

insufficient reaction time. This explains the chain crashes at the middle of the
platoon starting from vehicle 7 in the Figure 5.27. Crash performance from these
example UICW runs with VeSOMAC and 802.11 are consistent with the average

crash results from 500 different experiments presented in Figure 5.25.

 

_
O

 

Warning message delivery htency

.—

Latency (Second)

 

 

 

 

0.l -
l 3 5 7 9 ll 13 15 17 19 21 23 25
Vehicle Posiion in Cross- Street Phtoon

40
’5‘ 30 _ Relative d'stance between consecutive vehicle afler stop
D
g 2
b l

 

 

l 3 5 7 9 ll 13 15 l7 19 21 23 25
Veh'cb Position in Cross-Street Phtoon

 

 

 

Speed difirence between two corsecutive vehicle afler stop

 

0 ‘ F i % i i i i i l l
0 2 4 6 8 10 12 l4 16 18 20 22 24
Vehicle Posi'nn it Cross- Street Phtoon

 

 

 

 

Figure 5.27 : Latency and crash statistics for UICW with 802.11
Based on these results we conclude that the proposed VeSOMAC protocol offers
significantly better UICW vehicle crash performance compared to the

DSRC-proposed 802.11.

137

 

 

 

 
   

 

 

      
 
 

 

 
  
   

 

 

 

  

 

 

 

 

  

 

 

 

 

 

35 . ‘: I ,
Seconds 5
9) 30 an -. r .. : .......
g Message Drop ‘ ‘ ‘ . """" >
g 25 ‘7 . h : . I
.3 320 i +802.“
E S _,_ _ _: ‘ g g . e-VeSOMAC _
a 215 I . ; ;
5’2 10 3 f T
g ., First Message Drop
h. 5 r “““““““ ' *by4'hVehicle “““““““
0 L’“i"£-§ 2 = = : 2 Z = Z : 1' : 2 : ... 2 = J
0 5 10 15 20 25
Vehicle Position in Crossing-Street Platoon

 

Figure 5.28: Message drop at different platoon locations
Packet drop statistics across the cross-street vehicles is presented in Figure 5.28.
Due to collisions, 802.11 is susceptible to frequent packet drops. For instance, with a
background data rate of 40 packets per second per vehicle (ppsv), on an average the
802.11 based UICW application would loose the first WCW message by the time it
reaches the 4th cross-street vehicle. Meaning, if the message was not periodically
broadcast by the bad driver’s vehicle, the vehicles beyond the 4th vehicle would not
have received the message, thus suffering from the possibility of chain crashes.
Similarly, the 2nd WCW message gets lost by the time it reaches the 5th vehicle.
However, because of zero collisions, VeSOMAC can deliver the very first WCW
message to all cross-street vehicles. These drop results reinforce the UICW crash
performance findings in Figure 5.25.
5.3.3.7 Impacts of Vehicle Count and Speed
Crash performance with varying vehicle count and speed is reported in Figure

5.29. As expected, with higher vehicle speeds more vehicle crash for the without

138

UICW as well as with UICW with 802.11 and VeSOMAC scenarios. This is because
for a given vehicle spacing, at higher speeds, the vehicles get lower stop distances to

avoid a crash.

 

 

80

O\
O
l
I

.b
0
_Ir

 

 

% of Vehicles Collided
N
o

 

 

 

 

 

15 , 20
Cross Street Vehicle Count

 

 

Figure 5.29: Crash performance with varying speed and vehicle count
Unlike the crash results in Figure 5.25 (for 25 vehicles), with fewer cross-street
vehicles 802.11 performs as well as VeSOMA C. This is because the delay and drops
for 802.11 are small (see Figure 5.27 and 5.28) and comparable to that of VeSOMAC
for the front cross-street vehicles. With larger number of vehicles, however, the
latency is larger — which explains more crashes for 802.11.
5.3.4 Inter-vehicle Data Transfer Applications Performance
The experiments in this paper were carried out for inter-vehicle data and file
transfer applications on a one-lane highway platoon scenario [66] with DSRC radio
communications. We have evaluated both DSRC-recommended 802.11 and the
proposed VeSOMAC protocols with a channel rate of 24 Mbps. Two-ray ground

propagation model was used with a radio transmission range of 300m. Packet and

139

frame size for VeSOMAC were chosen to be 300 bytes and 100 packets (lOms)

 

 

 

 

 

 

  

 

 

 

 

respectively.
75 get-802.11: 10ppsv
' 2? i ~B-802.ll: 20 ppsv With Ordering Constraint
g 55 ”+VeSOMAco.Consnaint: 10ppsv”'”" " :Y‘lopps‘f
E -G-VeSOMAC O. Constraint: 20 ppsv
{43 55 “ -l-VeSOMACWorst210ppsv “zoppsv'
a: *VeSOMAC Worst :Qm2v . . e “
E 45 —- ———————————— ‘ ——————————— t—-—— .figflfl———-—
O. I i
t?” .; . _______________________ ;-_/.19.PP_SVI
é : /.:'/ 80211
25+ -___-_-H:,n_. ”_n
l (7) 15 i = a RPSVI
‘ O 20 40 60 80 100
Stream Data Rate (Packets/Sec)

 

 

Figure 5.30: Throughput performance of non-safety data streams

5.3.4.1 Performance of Non-safety UDP Applications

Throughput of cross-platoon UDP data streams, representing applications such as
inter-vehicle file, music, video, and traffic information downloads, are reported in
Figure 5.30. With varying background traffic, the data rate of a UDP stream from the
platoon front-to the platoon end was changed to determine the maximum sustainable
stream throughput. With low background traffic of 10 ppsv, a stream using 802.11
can sustain a throughput of up to approximately 47 packets/sec, beyond which it
starts degrading due to packet collisions. With higher background traffic of 20 ppsv,
its performance suffers drastically with a sustainable stream throughput of nearly 20

ppS.

However, for VeSOMAC with ordering constraint the throughputs are much higher.

140

At 10 ppsv, VeSOMAC with ordering constraint is able to attain 27% higher
throughput compared to the 802.11 (60 pps over 47 pps). Zero collisions, bounded
delay, and location aware slot ordering in VeSOMAC account for this performance
superiority. Without the ordering constraint, VeSOMAC can still offer better stream
throughput than 802.11, especially at higher background rates. These results indicate
the suitability of VeSOMAC for non-safety oriented vehicular data applications.
5.3.4.2 Performance of Non-safety FTPApplications

Figure 5.30 reports the FTP completion time for a 1 Mbytc data file transferred
across vehicles which are multi-hop apart within a highway platoon of 50 vehicles.
The reported results indicate the average FTP completion time computed over 30 and
10 simultaneous file transfer sessions active across different vehicle pairs within the
platoon. In each experiment, a given number of connections with a specified
connection length have been established with randomly chosen source and
destination vehicles within the 50—vehicle highway platoon. Each point on the graph
represents the average duration computed from 200 such independent experimental
runs.

FTP has been run over TCP over 802.11 or VeSOMA C, and the TCP connections

were set up using DSDV MANET [79] routing protocol. Note that such FTP based
data transfer corresponds to a large number of data intensive applications such as

maps, navigation and location based service, and music download [62].

141

 

 

File Transfer Duration (Sec.)

 

 

 

 

0 2 4 6 8
File Transfer Distance (Hop Count)

 

 

 

Figure 5.31: FTP duration with varying hop counts

The graphs in Figure 5.31 demonstrate that in majority of the situations, the file
transfers are faster with the VeSOMAC compared to with 802.11, especially for
scenarios when the involved vehicles are located farther apart within the platoon.
The reason for this is better TCP performance with VeSOMA C compared to with
802.11 as reported in Figure 5.31. Note that the only scenario in which 802.11
performs better is when files are transferred across l-hop, and with lesser number
(10 in this case) simultaneously active connections within the platoon.

Figure 5.322a reports the corresponding TCP throughputs using 802.11 and
VeSOMA C. Observe that with longer connections the TCP throughput per connection
reduces for both the MAC protocols due to increased user data traffic in the platoon.
However, the proposed VeSOMAC enables higher TCP throughput compared to
802.11 for all scenarios except for l-hop connections under small connection counts

(10 in this case). For example, when the connections are 2-hop long and there are 10

142

connections present in the platoon, VeSOMAC can enable a per connection TCP
throughput of 51 Kbps, which is a 66% improvement over the 802.11 enabled
throughput of 30 Kbps. As explained later, the MAC layer packet drops of 802.11 in
all scenarios except for the l-hop connections under small connection counts turn

out to be the reason [64] for the low TCP throughput.

 

 

 

 

    

 

 

 

 

 

 

 

4000
30 com.
fi- 200 - é iVeSOMAC
E, @3000 -_ .. ... i .- .- ,- -. -.
- 0
i E
B a,
.‘3‘ [_ 2000 __
a 13
"5b 100 i g
M 0
E E; 1000 _L.- .- .-
a. [_ ‘
B
, \802 ll
0 8 0 2 4 6 3
Hop Count

 

 

 

 

 

 

 

Figure 5.32: TCP Performance: a) throughput, b) round trip time

Generally higher TCP throughput using VeSOMAC can be explained through the
TCP congestion window evolution as reported in Figure 5.33:a and 5.33:b (for a
S-hop connection with 30 simultaneously active connections). Observe that due to
frequent MAC layer packet drops, the congestion window for the 802.11 case is reset
much more frequently compared to the VeSOMAC case, in which there are no MAC
drops. TCP segment drops due to 802.11 drops in this experiment are reported in
Figure 5.34:a. The infrequent window resets for VeSOMAC are due to

out-of-sequenee packet delivery in the events of rerouting caused by the routing

143

protocol DSDV’s periodic route refresh operations. Zero packet drops for the

VeSOMAC allows the congestion window to grow higher, which in turn yields better

 

 

 

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

TCPthroughput.

2.5 i . j 16

. Round Trip Time Congestion Windo I 802.11 .
”'5 _ a--- --_~_-»:__--_.-n._. .,-..-.-.,..-._.--_- ,____' -.-._-.-______-._- 0
E154 - _ g
E" ,, 8 .E
'0 if .0
20.5 4 33
o , no
a: ' g

0 0 u
130

5
P} o
8 4 r 5’;
w
it e
E3 ‘ f;
.o‘ 'I
5 2 7 g
e :5' 33
§ 1—' a
a: 8

0 U

130 230
Tnne(second)

 

 

 

 

 

 

Figure 5.33: Dynamics of TCP : a) TCP-over-802. l l , b) TCP-over- VeSOMAC
Note, however, from Figure 5.32:b and 6.33 that in spite of its better throughput,
the TCP round trip delay for the VeSOMAC case is actually higher than that with
802.11. This is due to the higher load for VeSOMA C caused by larger TCP
congestion windows. Larger TCP load in the VeSOMAC case is evident from the
higher sent segment sequence numbers compared to the 802.11 case as shown in
Figure 5.34:a. Higher TCP load forces VeSOMAC to operate at a higher MAC load

point, which results into larger MAC queuing and subsequent TCP round trip time.

144

 

 

 

 

 

 

 

 

 

   
 

 

 

 

3000 _ . _ 1000

30 Simultaneous 5-hop TCP Connections n.
8 2500“”““‘TCPSegmentDropsdueton ‘‘‘‘‘ ‘ “3002
t: 2“!) -... . , -.. 802.11 MAC Drops --__- “.1. __________ E. a
“ *2 1 ; i” 600 8 5
is §’1500rL ‘7 - ~~~~~~~ i ~~~~~~ -~SegmentSeq.er 5 5)
°. ., . with VeSOMAC ~- 400% a
O mum a- - . ......... ,_ . _______________ .
z. : : * 7‘3
(g)- smd ______ ’3 -.-- "_ng. ' “$2003-

f' ! ; Segment Seq. No. with 802.11 to
0 i i i 0
130 180 230 280 330
Time (Second)
:3' 35000 If T I I I
a 30000 4 10 Simultaneous Il-hop TCP Connections _ - ;_ g g - - _ _i_ _____
$3) 25% .I ........ I. ............ .. .. L ...... L. ____________________
§ 20000 . [Segment Seq. No. wrth 802.11 _ __________________
a 15000 -- — -. —
c2 ,
“5 10000 ~~ ~ ~ ---------
2 500° ‘ V ”' " ‘ Segment Seq. No. with VeSOMAC '
g 0 i i 4r r l i l
130 150 170 190 210 230 250 270
Time (Second)

 

 

 

 

 

 

Figure 5.34: Dynamics of TCP segment generation:
a) 30 5-hop connections b) 10 l-hop connections
TCP loading for l-hop connections under small connection counts (10 in this
case) are reported in Figure 5.34:b. Unlike in Figure 5.34:a, 802.11 in this case
enables higher TCP loading compared to the VeSOMA C. Lack of self-competition
[64] for the l-hop connections and mild inter-connection competition due to fewer
connections help significantly reduce the MAC layer drops for the 802.11. This
explains 802.11’s better TCP and file transfer performance for l-hop connections

under small connection counts as shown in Figure 5.31 and 5.32.

145

 

 

 
  

VeSOMA C

FTP Transfer Duration(second)

 

 

 

 

 

300 “r
200 i I I e i
I O l 2 3 4 5 6
Passing Rate (times/min)

 

Figure 5.35: FTP duration with varying vehicle switching rates
5.3.4.3 Inter-vehicle Data Transfer Performance during VeSOMAC
Reorganization

We also conduct experiments when there is a VeSOMAC slot allocation
reconfiguration. A 50—vehicle platoon is used for these experiments and there are 10
concurrent 7-hop away TCP connections. We have some vehicles to pass certain
number of vehicles, which is an ordinary traffic event in practical scenarios. Notice
that all the experiments in the following are controlled in a way that the routing path
of those 10 TCP connections will not be affected by the passing events. This is to say
that the vehicles with passing events will not be on the route of any TCP connection.
This minimizes the effect of the routing layer on the performance. Also, afier each
vehicle passing events, we force the passing vehicle to have a‘slot collision with one
of its new neighbor which is the intermediate vehicle in the TCP connection route
path. The VeSOMA C logic will then be used to choose a slot collision allocation after

the passing events.

146

Figure 5.35 reports the FTP transfer duration of 1 Mbytes data changes over
different vehicle passing rate in one of FTP connections. The FTP transfer duration
of 802.11 is not prone to change with changing vehicle passing rate because of the
inherit 802.11’s topology change unawareness property. On average it takes around
550 seconds for 802.11 MAC to finish this FTP service. On contrast VeSOMAC has
a much smaller FTP transfer duration as shown in Figure 5.31 in the stable state.
Although the FTP transfer duration of VeSOMAC has a clear rise with increasing the
vehicle passing rate, it reaches around 550 seconds when the passing rate is around
5.3 times per minute. VeSOMAC has still smaller FTP transfer duration than 802.11
does.

In the Figure 5.36:a, it shows the TCP congestion window evolution when there are
two vehicle passing events, which all cause a slot collision on the routing path. The
two passing events happen at time 190.0 and 260.0 second respectively. As we can
see from the figure, there are TCP congestion window drops at both time stamps.
The TCP segments loss during the temporary slot allocation configuration process
leads to the TCP congestion window drops. After the VeSOMAC configuration, TCP
congestion window then gradually increases to the maximum value. When there is
no such vehicle passing event, as we can see the congestion window will maintain
the maximum value after it increase to the maximum value. With 802.11 MAC, the
congestion window evolutions with or without passing events are not much difl’erent.
Similar to Figure 5.33, VeSOMAC is still able to reach much larger TCP congestion

window size than 802.11 even there are some slot allocation reconfigurations.

147

 

 

 

 

    
 
      

40 fl - / VeSOMAC: Nonpassing . .- . . - - :
30n_;'rl"'.1 --.--- _ -,,._.n_..._ a
if“ VeSOMAC -. " i i .

I" Passing . “M "- 802'1 :Passmg ___ 7802.11:Nonpassing J

  

i

—
O
l

 

 

 

TCP Congestion Window .
N
o

5!-
h
L
..‘t.
r»

'3qu
é...
3a..
.15.. I-
1" I
L 1
_\ .
M
7*
H.
7"

 

O

130 l 80 230 280 330
Time(second)

 

 

 

r

i l l
i ‘ f
I I
. . _ a;
_ - -.‘n. _ r" -. -

.3
O
O
C

   
  
  

l

w

‘ VeSOMAC Nonpassing

 

 

 

TCP Segment Sequence #
o ’5 o
8 8 8

 

 

l _. _____-.__r_-_-
i \802.11:Passing
O ‘ i I i i
130 180 230 280 330
Time(second)

 

 

 

 

Figure 5.36: TCP Dynamics with passing events: a) congestion window, b) segments
generation

Figure 5.36zb shows how the TCP segments generation pattern at the TCP source
in the same TCP connection as we analysis in Figure 5.36:a. As we can see that two
passing events cause some short period retransmissions. These retransmissions are
the results of TCP segments loss during the short VeSOMAC reconfiguration period.
The segments generation rate recovers quickly upon finishing slot reallocation. As
we found before in the stable case, VeSOMAC is still able to send much more
number of TCP segments than 802.11.

The dynamic of TCP throughput of the same connection is reported in Figure 5.37.

Figure 5.37:a is the throughput dynamics with 802.11 MAC. As we mentioned

148

 

before, there is not much difference between with and without passing events. With
VeSOMAC MAC, those two passing events will also temporarily affect the TCP
throughput. As shown in Figure 5.37zb, there are two drops corresponding to two
passing events at time 190.0 and 260.0 seconds. Whereas there is no such drop when
no such passing events. Even with two drops, the average throughput of VeSOMAC

is still around two times larger than 802.11.

 

/{ — 802. 11 'Passing
-— 802.11Nonpassing

 

N
O

l

in MI N"

)—I

 

 

 

TCP Throughput(Kbps)
M 8 M

 

 

 

 

0 l l
130 l 80 230 280 330
Time(second)
20 — VeSOMAC Passing
-— VeSOMAC: Nonpassing

 

_I
M

 

UI

 

 

TCP Throughput(Kbps)
o S

y—n
U)
C
H
00
O

230 280 330
Time(second)

 

 

 

Figure 5.37: Dynamics of TCP throughput: a)TCP-over-802.l 1, b)
TCP-over- VeSOMA C
Same as the results given before, the TCP round trip time is reported in Figure
5.38. VeSOAMC is having larger round trop time than 802.11 because of working in

a higher traffic load.

149

 

 

. .N
LII N (I! u.)

put

 

TCP RTT(second)

O

a /— VeSOMAC: Passing
T --- VeSOMAC: Nonpassing

 

—802. 11: Passing

802.11Nonpassigg

 

 

i
t '2 ‘
t
I

 

1

l
1
I
l

 

 

o'm

130

 

280

Time(second)

 

 

Figure 5.38: Dynamics of TCP segment generation

In the Table 6.3, we give some time constants of TCP, routing protocol and

proposed VeSOMAC protocol. As we can see, if the vehicle platoon topology

changes cause the routing and TCP protocol to respond, it may take 45 seconds to

rebuild the TCP connections. This time constant is same even using mobility

transparent 802.11 MAC protocol. Comparing to this time constant, VeSOMAC

reconfiguration time is just 0.27% of it. This means VeSOMAC would not cause

obvious delay overhead when there is a routing path reset-up.

 

TCP retransmission

timeout (seconds)

DSDV routing

timeout (seconds)

entry

VeSOMA C

time (seconds)

reconfiguration

 

 

6

 

45

 

0.12

 

Table 5.3: Time constant of protocols

5.4 Summary and Conclusions

150

 

We have adapted ISOMAC logic to a fihicular _S_elf-_Qrganizing M
(VeSOMAC) protocol for distributed TDMA allocation in vehicle-to-vehicle wireless
networks. In additional to ISOMAC, VeSOMAC is designed to be vehicle location
and movement aware. Simulation results demonstrate that unlike the 802.11 style
contention based protocols, VeSOMAC can offer better vehicle safety and data
transfer throughput through smaller and bounded packet latency. It has been also
shown that the protocol convergence during topology changes is fast including

platoon mergers and vehicle passing.

151

Chapter 6
Dynamic MAC Protocol Switching for Performance Adaptation
with Traffic Heterogeneity
6.1 Introduction
6.1.1 Background
Wireless sensor networks are initially motivated by military applications such as
intrusion detection, battle-field surveillance and enemy tracking. Recent research
shows a rapid increase in the civilian applications like environment data collection,
health monitoring, and disaster relief. Although there have been significant recent
improvements, maximizing network throughput at the MAC layer in a multi-mission
network is still a key design challenge.
The traffic heterogeneity in a multi-mission network can be considered in three
categories:
> Variance of data rate: Applications of wireless sensor networks can range
from very low data rates such as intrusion detection events, to very high data
rate video surveillance. In [80], the author has shown that the data rates in
future wireless sensor networks can vary from several bits or bytes per
second up to 10 to 100 Mbps. This means that there can be over 100 times
spread of working data rates within the same network. Recent applications
such as video sensor networks indicate that gradually the share of high data
rate applications are expected to become similar to the share of traditional

low data rate applications.

152

> Variance in num_ber of active transmitters: The number of active transmitters
can be different for different applications. Applications like environment
monitoring, typically involve a large number of deployed nodes sending data
simultaneously. Whereas in applications like intrusion detection, only nodes
in the vicinity of an intrusion event transmit at a time. This heterogeneity in
number of transmitters is unavoidable for multi-mission applications and
networks.

> Spatial variance: It is unlikely that in a very large network all sensors will
experience the same trafi'rc profile. Instead, multiple and possibly distinct
traffic profiles are expected in different parts of a network.

The problem we address in this chapter is: how to develop a MAC layer that can
maximize network throughput in the presence of the above traffic and network
heterogeneity.

6.1.2 Related work

The MAC layer approaches for wireless sensor networks can be divided into three
broad categories: contention-based [9, 22, 48, 49, 81, 82], schedule-based [23, 24, 44,
50, 69, 83], and hybrid [42].

CSMA/CA [48] is an example of the contention based approach. If the channel is
sensed busy before any transmission, nodes defer the current transmission for a
random back-off period. The RTS/CTS handshake mechanism is used to prevent the
exposed and hidden terminal problems. CSMA/CA has the advantages of simplicity,

flexibility and robustness. No infrastructure support and clock synchronization is

153

needed for CSMA/CA protocol to work. The most prominent feature of CSMA/CA
is that anode can access all available bandwidth in its neighborhood when needed.
However, the medium access collisions and the corresponding unbounded delay is a
problem for CSMA/CA and all other protocols in this category, mainly because of
their underlying random access.

Comparing with contention based protocols, schedule based protocols like TDMA
consists of establishing transmission schedules in a way that no collisions occur, and
efficient spatial reuse of the available bandwidth can be achieved. A number of
TDMA protocols for sensor networks are proposed in [23, 24, 44, 50, 69, 83].
Despite all the known drawbacks which have been pointed out in the literature,
TDMA protocols allocate fixed and guaranteed bandwidth for all nodes in the
network. The spatial reuse feature provides efficient bandwidth usage when all nodes
in a network transmit at the same time. The collision free feature in the steady state
makes sure that all the bandwidth is used for data transmissions rather than packet
collisions.

In a hybrid design [42], the authors proposed a protocol called Funneling-MAC.
The Funneling-MAC is designed to address the funneling efi'ect near base stations in
a sensor network. The funneling effect means that events or data generated in the
sensor field travel hop-by-hop in a multipoint—to-point pattern toward one or more
sink points. It assumes that the sink nodes are more energy-rich than other sensor
nodes. A sink node niggers localized TDMA by a beacon broadcasting process.

Nodes that are able to receive the beacon are said to be within an intensity area. The

154

boundary of the intensity area is regulated by the transmission power of the beacons
from the sink. Through a dynamic depth-tuning algorithm, the throughput can be
maximized and the packet loss rate is minimized at the sink point. A sink constantly
monitors the traffic that arrives at the sink on a per-aggregated-path manner,
calculates the favorable TDMA schedule based on the monitored traflic for all paths,
and distributes the schedule by broadcasting a schedule packet at the same
transmission power used for beaconing. Nodes in the intensity area run an alternate
CSMA/TDMA frame, called superfiame. The duty cycle of CSMA and TDMA is
decided by the schedule computed by the sink. Nodes outside the intensity area still
run CSMA. They are aware of the localized TDMA schedule by overbearing
meta-schedule advertisements containing TDMA scheduling information, which are
sent out by nodes in intensity area in the first event data packet toward the sink every
beacon interval. The problem of how to achieve maximum throughput is alleviated
to some extent, but the Funneling-MAC scheme is suitable only for
multipoint-to-point applications and not for peer-to-peer traffic.
6.1.3 Proposed Dynamic MAC Protocol Switching

In this chapter, we present a distributed Dynamic MAC Protocol Switching
framework, which achieves the goal of maximizing network throughput as in
Funneling-MAC but without its restrictions. The key idea behind the proposed
Dynamic MAC Protocol Switching is to use neighborhood traffic information to
decide the most appropriate MAC protocol under current traffic situation for each

active node. Instead of monitoring incoming traffic constantly only by the sink node,

155

all the nodes monitor the local traffic, compute the appropriate MAC protocol to run,
and make decision of protocol switching within their neighborhoods. In fact, the
presence of a sink node is not necessary for the proposed mechanism to work. The
primary contributions of this chapter are listed as follows:

1. Propose a novel dynamic MAC protocol switching paradigm to address the
problem of how to achieve the maximum throughput in a network with
traffic heterogeneity.

2. Specify two examples of MAC protocols, CSMA/CA and TDMA, and
describe the extensions of both protocols so as to use for co-existence and
dynamic MAC protocol switching. The corresponding revision of
transmission rules is also stated.

3. Develop the protocol switching criteria, supported with a mathematic model.

4. Experimentally validate the concept of dynamic MAC protocol switching.

The structure of this chapter is as follows. In Section 6.2 we explain the features
of protocols supporting MAC switching. Two examples are used in this section to
elaborate the concept. The detailed modifications and transmission rules of protocol
revision are presented. The general MAC protocol switching logic is described in
Section 6.3, including description and model of switching criteria, main switching
logic and response to topology changes. An experimental evaluation is shown in
Section 6.4 to support the proposed paradigm. Finally Section 6.5 states the
conclusions and ongoing work.

6.2 Protocols Supporting MAC Switching

156

6.2.1 Generalized Concept

To generalize, there could be multiple MAC protocols running at different node
clusters (see Figure 6.1) with heterogeneous trafiic profiles. Conceptually, a typical
example of a real-life situation is as follows. The home wireless router
communicates with the outside internet through CSMA/CD wired MAC protocol,
and at the same time uses 802.11b/g wireless MAC protocol to communicate with
home computers. Therefore, the home wireless router operates in a Multi-MAC
Operating Mode (MMOM) node. In the context of wireless sensor networks, the
MMOM can have three differences from this example. Egg, the different MAC
protocols all have to be wireless. mtg, sensor nodes, unlike wireless router in the
example, usually are not equipped with multiple interfaces. Various MAC protocols
run at individual sensor node have to use the same wireless communication interface.
M, at MMOM nodes, different MAC protocols have to coexist MMOM node has
to bridge different MAC protocols through the same wireless radio interface. If
different MAC protocols could not “talk” with each other, the network can be
partitioned.

Most of the currently used MAC protocols, however, are not able to communicate
with each other. Often times, researchers focus on proposing a single MAC protocol
to solve a series of problems. For instance, contention based protocols are proposed
to provide satisfactory performance for moderate trafiic scenarios, whereas schedule
based protocols are proposed to provide performance guarantee in high or congested

trafiic scenarios. This results in certain modifications of the current protocols so that

157

they can communicate with each other without changing their individual primary

advantages.

 

 

 

 

 

Figure 6.1: MAC variations within networks

6.2.2 Specific Mechanisms for MAC Protocol Switching

In this chapter, coexistence of two MAC protocols, namely a random access
CSMA/CA and a schedule based TDMA, are studied. CSMA/CA and TDMA are
chosen because they serve as good representations of contention based and schedule
based protocols respectively. Current MAC mechanism, both random access [9, 22,
48, 49, 81, 82] and schedule based [23, 24, 44, 50, 69, 83], are not able to
communicate to each other because of different “languages” they speak. In order to
have two different protocols communicate with each other, smart adaptations of
transmission rules to CSMA/CA and TDMA are required. With such adaptations,
two protocols are then able to coexist at MMOM nodes. Furthermore, the

coexistence also aids the capability of protocol switching. In this section, we

158

concentrate on the adaptations of transmission rules of CSMA/CA and TDMA to
cope with the coexistence problem. The capability of protocol switching will be
elaborated in Section 6.3.

6.2.2.1 Adaptations of CSMA/CA for TDMA Coexistence

In general, the basic transmission rules in CSMA/CA are not changed. A
successful transmission between two nodes is still through a control message
handshake. If a node wants to transmit, it first listens to the channel for a
predetermined amount of time so as to check any ongoing activity in the channel. If
the channel is “busy”, the node will defer its own transmission. If the channel is
“idle”, the node then sends a Request-to-Send (RTS) message, and a Clear-to-Send
(CTS) message will be sent back by the intended receiver. The handshake of RTS
and CTS will alert all the nodes within the range of the sender and/or the receiver to
maintain silence for the duration of the data packet transmission. Upon receiving the
CTS message, the sender finally sends the data message to the receiver. The
Acknowledgement (ACK) is not utilized in our CSMA/CA logic, which means that
there is no link layer. The other features of CSMA/CA such as exponential back-off
and so on are still applied here.

TDMA is well known for its collision-free transmission in steady state. We still
want to maintain the collision-free feature of TDMA. Thus, the key idea of the
adaptation of the CSMA/CA is to guarantee the collision-free transmission of TDMA
nodes in a CSMA/CA nodes neighborhood. The pseudo code for the adapted

CSMA/CA logic is shown in Figure 6.2. The new adaptations lie in two categories:

159

at sender side and at receiver side.
> Sender side: The sender is able to estimate the duration of a successful
transmission in terms of RTS, CTS, the data message, and the inter frame
space, before the RTS transmission. If it knows the TDMA slots of all its
neighbors, then the sender can determine whether the following data
transmission will overlap with the neighbors’ TDMA slots or not. If there
is at least one anticipated overlapping, the sender simply defers
transmission till the end of all its neighbors’ TDMA slots. Otherwise, the

data transmission could carry on as usual.

 

/* Adapted CSMA/CA Logic */

Sender Side:
Estimate the duration of a success/ill transmission;
if ( any overlapping with T DMA neighbors ’ slots)
defer transmission till end of neighbors ' TDMA slot;
else // no overlapping within knowledge of sender side
start R T S transmission;
Receiver Side:
Upon receiving RT S, check the duration of the intended
message transmission;
if ( any overlapping with TDMA neighbors ’ slots)
send NT S message back to the sender;
else // no overlapping within knowledge of receiver side
start CTS transmission;

 

 

 

Figure 6.2: Pseudo code for adapted CSMA/CA logic
> Receiver side. Upon receiving an RTS message, the intended receiver is
able to know the duration of the following data message by looking at the
RTS NAV duration field of the RTS message. If within the knowledge of
the receiver, there are TDMA slots of neighbors overlapping with the
following data message, the receiver will send a Not-to-Send (NTS)

message, containing the duration of the overlapping period, back to the

160

sender. Upon receiving the NTS message, the sender will then know when
to restart the current data transmission to avoid the neighbors’ TDMA
slots.
6.2.2.2 Adaptations of TDMA for CSMA/CA Coexistence
Unlike CSMA/CA, TDMA requires more adaptations even for its basic
transmission rules. The frame and slot structure of regular TDMA is maintained as
usual. Every node has one slot per frame to transmit. The frame is periodic, so the
transmission of each node is periodic with periodicity of frame duration. Instead of
transmitting data directly within the slot in regular TDMA, we impose RTS/CT S
handshake mechanism inside each TDMA slot. Before transmitting the data message,
the two way RTS/CTS handshake is used. The RTS/CTS handshake mechanism is
different from the one in CSMA/CA in a way that there is no need to sense the
channel before transmitting the RTS message. With the new RTS/CTS mechanism
inside each slot, TDMA is now able to “talk” to CSMA/CA. Note that even when
two nodes use TDMA MAC to communicate, they still use RTS/CTS mechanism
inside their respective slots. The pseudo code for the adapted TDMA logic is shown

in Figure 6.3.

 

/* Adapted T DMA Logic ‘/
Sender Side:
if ( in sender’s own TDMA slot)
start RTS transmission and wait for C T S;
M:
if ( receiving RT S)
send C T S message and wait for data message;

 

 

 

Figure 6.3: Pseudo code for adapted TDMA logic

161

6.2.3 Detailed Transmission Rules
6.2.3.1 Transmission Among Nodes with Same MAC Protocol

Nodes with same MAC protocol refer to nodes within two hop neighborhood
which are all running the same MAC protocol. For CSMA/CA, nodes will act like
running regular CSMA/CA. There is no need to consider TDMA slots because there
are no TDMA MAC neighbors within two hop neighborhood. The modified
CSMA/CA performs the same as the regular CSMA/CA. For nodes with TDMA
MAC, the RTS/CTS mechanism is still used within the TDMA slot. The throughput
performance of modified TDMA is expected to be the same as regular TDMA.
6.2.3.2 Transmissions From TDMA to CSMA/CA Nodes

The transmission fi'om a TDMA node to a CSMA/CA node is schematically

elaborated by an example shown in Figure 6.4.

 

 

 

 

 

 

 

TDMA Frame
TDMA Slot
TDMA
sender RTS DATA
Tx
Rx
CSMA/CA T"

 

 

receiver Rx

 

RTS DATA

 

 

 

Figure 6.4: Transmission from TDMA node to CSMA/CA node
When a node with TDMA wants to transmit a message to a neighbor which is
running CSMA/CA, RTS message will first be sent out in the beginning of the
transmission slot. When the CSMA/CA neighbor receives the RTS from the TDMA

node, a CTS message will be sent in response. Afier receiving the CTS message

162

from the CSMA/CA neighbor, data message transmission follows in the remaining
slot time. Since the RTS and CTS message are generally very short compared to the
actual data message, the transmission time spent on RTS/CTS handshake should be
relatively small. The RTS/CTS exchange at the beginning of each slot of the TDMA
nodes is regarded as overhead.

Another issue here is the relationship between the slot time and data message
transmission time. If not carefully dimensioned, it is possible that the data message
transmission will not be finished before the slot boundary ends. The transmission
started in the previous slot could potentially cross over to the next slot, which may
cause collision in the following slot. However, the slot size should be large enough
to handle at least one message transmission, and we will make assumption that data
transmission will not cross the slot boundary. The last thing to note is that TDMA
nodes will only transmit messages in their assigned TDMA slot.
6.2.3.3 Transmissions From CSMA/CA to TDMA Nodes

The transmission rules used when a CSMA/CA node transmits to a TDMA
neighbor node is more complex than the previous two cases. Ideally, assuming the
carrier sense is successful, a CSMA/CA node should be able to transmit when there
is a message to be sent without the notion of any slot constraints. However, in this
design, when CSMA/CA node transmits to a TDMA neighbor, transmission should
not start without any notion of timing. Without such constraints, there is a chance
that the transmission for a CSMA/CA node may collide with the transmission of a

TDMA node in its assigned slot time.

163

The collision at the CSMA/CA node is less of a problem because the
retransmission mechanism will handle the collision anyway after timeout or back-off.
The collision at the TDMA node is a relatively severe problem compared with at the
CSMA/CA node. The transmission of TDMA nodes is scheduled once every frame.
If there is a collision, transmission has to be deferred until the next frame, which
could greatly increase the delivery latency. Thus the collision at the CSMA/CA node
is much cheaper than at the TDMA node. This motivates us to give higher priority to
TDMA nodes when CSMA/CA nodes try to access the medium at the same time.

The priority is achieved in the following two ways:

(1) CSMA/CA packet transmission should not cross the slot boundary to interfere
potential TDMA neighbors’ (up to 2-hop) transmission in the next slot. The owner of
the next slot can be the neighbor of either the sender, which is a CSMA/CA node in
this case, or the receiver, which is a TDMA node. To make sure both cases are
handled, the existing message duration in the control message (RTS/CTS) is
extended. The logic of the control message duration extension is explained in the
following three scenarios.

First Scenario: at the CSMA/CA side, if message transmission including RTS/CTS
duration starting from current time is not able to finish message transmission before
entering a TDMA neighbor’s slot, the CSMA/CA node should defer currently

intended message transmission after the TDMA neighbor’s slot.

164

 

Scenario 1

 

 

 

 

Packet arrives
Packet Duration RTS DATA
CSMA/CA Tx 5335353255533355335533
sender ...4 ................
Rx .
‘_ Recelver’s _, CTS
TDMA Slot
TDMA Tx CTS
receiver * —
Rx
‘—TDMA Slot-OI RTS DATA

 

 

TDMA Frame

A
V

 

 

 

 

 

Figure 6.5: Transmission from CSMA/CA node to TDMA node scenario 1
W1 CSMA/CA node is flee to transmit an RTS due to know the
message overlapping period. After the RTS reception, if the TDMA node finds out
that the interval between current time and the earliest next TDMA neighbor’s slot is
smaller than the RTS message duration, CTS will not be sent back to the CSMA/CA

node. Instead, an NTS (Not-to-Send) message will be sent back to the CSMA/CA

 

 

 

 

 

 

 

 
 

 

 

 

 

 

 

node.
Scenarioz
Packetarrives
RTS NTS Duration RTS DATA
CSMA/CA g531733252?s?2§2§2§s§:§:§s§25
senda ‘.‘.;.;.:.:. ............ #'.
CTS
LNeighbor’sd,
TDMA Tx NTS TDMA Slot CTS
receiver :;:§:§:;:;:§:§:;:;:;J
Rx I;I;I;I;I;:;I;I;I:I:
RTS RTS Duration RTS DATA
1 TDMAFrame >

 

 

 

 

 

Figure 6.6: Transmission from CSMA/CA node to TDMA node scenario 2
Third Scenario: The TDMA node does not find any overlapping RTS duration and

neighbors’ TDMA slots. A CTS will be sent back to CSMA/CA node in the

165

RTS/CTS handshake. Upon CTS reception, data message could be finished if no
violation of scenario one. In this case at the sender, there is no clear NTS message
reception to ask for deferring. CSMA/CA node still checks the validity of the first
scenario when having CTS. This redundancy is to ensure the priority even in the
presence of network topology dynamics. The diagrams of all three scenarios are

shown in Figure 6.5, 6.6, and 6.7 respectively.

 

   
    

 

 

 

 

Scenario 3
Packet arrives
RTS DATA
sender
Rx CTS
TDMA Tx
receiver Rx
RTS DATA
Receivers
TDMA Slot
: TDMA Frame

 

 

 

 

 

 

 

Figure 6.7: Transmission from CSMA/CA node to TDMA node scenario 3

(2) Usage of a TDMA neighbor’s slots by a CSMA/CA node is allowed only when
the TDMA neighbors do not have anything to send. This is accomplished by having
a randomly distributed RTS deferring time for the CSMA/CA nodes when current
time is in their TDMA neighbors’ slots.
6.3 MAC Protocol Switching Logic

In this section we discuss the detailed design of the proposed protocol switching
logic, and issues related to the involving criteria and thresholds.
6.3.1 Switching Criteria

The goal of protocol switching is to be able to provide the best network-wide

166

throughput irrespective of the heterogeneous traflic profile at different parts of a
network. Thus, the criteria for protocol switching have to be decided by the
network-wide throughput. If we consider the generic queuing model of MAC
protocols, the network-wide throughput includes two distinct types, unsaturated and
saturated throughput. For example, for a network with it active nodes and each node
is modeled as a simple M/M/l queue, the unsaturated network-wide throughput is
n - ,1 , and the saturated network-wide throughput is n . ,u , where l is the data rate
at each node and ,u is the queue service rate at each node.

The above observations lead to the following conclusions about the network-wide
throughput in a fully-connected l-hop network for both unsaturated and saturated
cases. The network-wide throughput of TDMA, as shown in [84], is of the form:

STDMA = f(1.n,F), (6.1)
where 2. is the generated data rate at each node, n is the number of active nodes,
and F is the TDMA frame duration which is fixed for a given network. The
performance analysis of CSMA/CA presented in [85-90] shows that the
network-wide throughput of CSMA/CA is of the form:

SCSMA/CA = g(/1,n.Wmin,m), (6.2)
where l is the generated data rate at each node, n is the number of active nodes

(contenders), Wmin is the minimum contention window size, and m is the

167

maximum back-off stage".
The throughput of a given network running protocol switching is:

S = 5mm +SCSMA/CA = f (Anibal/1J7) + g(’12"CSAM/CA,Wminam): (63)
where "TDMA and "CSMA /CA are the number of nodes running TDMA and
CSMA/CA MAC respectively. The combination of anA and ”CSMA ICA is the
number of active nodes n in whole network. Considering the situation that some of
the nodes may not actively send messages all the time, the number of active nodes is
not necessarily equal to the network size. Given a fixed network, F, m and Wm
are all constants for TDMA and CSMA/CA protocols. Thus, the throughput is
decided based on the xi and n values from Equation 6.3. Consequently, if we want
to maximize the throughput, 2. (generated data rate at each node) and n (number of
active nodes) should be the criteria to decide protocol switching.

> Data rate ( A ): Generally speaking, larger data rate results in larger
throughput. The maximum service rate of TDMA is bounded by the TDMA
frame duration, and can be reported as #MAX—TDMA, which is fixed for a
given network. From a single node’s perspective, when the generated data
rate xi. is equal to or less than #MAX—TDMA» theoretically, the achievable
throughput is equal to ,1 while running TDMA MAC. On the other hand,

the “maximum” achievable throughput with CSMA/CA MAC is equal to or

 

6
In CSMA/CA MAC, a back-off time is uniformly chosen in the range (0, W-l) at each message

transmission. The parameter Wis called contention window. At the first transmission attempt, w is set

to a value Wmin , and can go up to Wmax = 2m Wmin after m unsuccessful transmission.

168

less than 1, depending on the possible message collisions. To summarize,
when the data rate 11 is larger than #AMX—TDmi the throughput is equal
to #MAX—TDMA with TDMA, and the throughput can be larger than
#MAX—TDMA with CSMA/CA.

> Num_ber of gctive nodes (n): Generally speaking, more active nodes lead to
larger throughput. Assume when there is only one node in the network
sending at a data rate A , the throughput of that single active node is Ssin gle-
When there is n active nodes, the network-wide throughput is
n - Ssin gIe—TDMA for TDMA and n - Ssin gle—CSMA /CA for CSMA/CA. The
difference here is that Ssh, gIe—IDMA = Ssin gIe , but

Ssin gle-CSNIA/CA S Ssin gle‘ The reason is that for TDMA there are no

collisions, thus putting more number of nodes will not affect the throughput
of individual nodes. Whereas for CSMA/CA, a contention based protocol,
putting more active nodes means introducing more contenders to the same
channel. From a single node’s perspective, the throughput goes down with
increasing number of active nodes.

From the above analysis, in order to boost fidelity of the network, a node should
use TDMA MAC when the traffic and node density (Ii. and n) in its neighborhood is
favorable for TDMA and should use CSMA/CA when the parameters A and n are
favorable for CSMA/CA.

6.3.2 Model for Switching Criteria

This section solves the problem as to when nodes should switch their MAC

169

protocols. From the analysis in Section 6.3.1, the decision of protocol switching is
based on the data rate A and the number of active nodes (contenders) n in the
neighborhood. If A s #MAX—TDMA , it was shown in Section 6.3.1 that using TDMA
MAC protocol gives better throughput. Therefore the number of contenders (n) in
the neighborhood does not have to be considered for this data rate range. As the data
rate becomes larger than ”MAX—TDMA , we should consider the number of active
nodes 12. Increasing n will at the same time shrink the Ssingle—CSMA/CA- If we also
model CSMA/CA MAC as a queue, the critical point is when the data rate 2. is
equal to service rate of CSMA/CA ( #CSMA/CA), where /l > fimx-IDMA- After
this critical point, even if we fiirther increase ,1 or n, the throughput of CSMA/CA
will not go up any more. This ceiling effect is because that at this time the
throughput has already saturated. The throughput of C SMA/CA is unsaturated before

the critical point ( #CS‘MA /CA ).

 

/* MAC Protocol Switching Logic decisions with J. and n */
if( ’1 (z/JMAX-TDAM)
run TDMA MAC;
else If (’K :auCSMA/Ct and Pcs.rLUCA>f‘MAX—mm)
//A>pM4X-TDM4

// and for moderate "r ”CSMUCA>PMAX-TDMA
run CSMd/CA MAC;

else if(/‘CSMA/CA<= ”MIX-TDMA)
run T DMA MA C; // large n reduces pCSWC-A

 

 

 

Figure 6.8: Pseudo code for protocol switching decision with 2. and n
To summarize, the protocol switching decisions are as follows:
> When the data rate xi. is not greater than #MAX—TDMA, nodes should run

TDMA;

170

> When 2 is larger than #MAX-TDMA , nodes should run CSMA/CA till
,1 = #CSMA/CA;

> Nodes should run TDMA when #CSMA /CA S #ZIDMA with large n. The
corresponding pseudo code is shown in Figure 6.8.

Data rate is usually considered as an application layer parameter. If the decision of
MAC protocol switching is based on the data rate, it requires a cross-layer design so
that the upper application layer can pass the data rate parameter down to the MAC
layer. Another alternative is to try to find a MAC layer substitution parameter for the
data rate. The queue utilization, which is of the form ,0 = xi / p , is a good candidate
for the MAC layer substitution parameter for the data rate.

Considering the utilization p the corresponding protocol switching decision
become:

> Nodes should run TDMA if PTDMA <1, or PCSAM/CA <W,

#CSMA/CA
where #MAX—IDMA < .UCSMA/CA-

> Nodes should run CSMA/CA when PTDMA = 1 and

#MAX—TDMA
PCSMA / CA > , Where ”MAX—TDMA < #CSMA / CA-

PCSMA/ CA

> Nodes should run TDMA when PCSMA / CA 2 l

(l-e-#CSAIA/CA S #MAX—Toml-

171

 

/* MAC Protocol Switching Logic decisions with p and n */

if(” TDMA<1 0"

pCSMA/CA<( ”MAX. IBM 1“ CSMA/CA ) With P.11.4r-rom< 1U cant/(:4)
run T DMA MAC;

else if(.0 7:0sz and

*0 CSMA/CA>( ”Mix—mM/FCSMA/CA) With I"MAX-7DM4< ”CSMA/CA)
run CSMA/CA MAC;

else if( pCSMA/CA21)
run TDMA MAC; // large n makes pCSWCA<= Fmrmu

 

 

 

Figure 6.9: Pseudo code for protocol switching decision with p and n
The numerical value of above decisions can be derived from the theoretical

analysis in [85-88] by solving the following series of eight nonlinear equations:

 

 

 

 

 

 

 

2lel—(2p) ](l-p)+p(l-2p)(1-p )+(2—ps)(W+l)+1-pb,m3m.
2(1 -.2p)(1 -p) 2 pa
_1_=< 2lel—(2p)"’ 1(l—P)+P(1-2P)(1“Pm)+(2‘Pb)(W+1)+1_Pb
bo,o 2(1 - 2p)(l - p) 2 pa
m'+l m-m'
+p (Wmax+l)(l—p ),m>m.
1 220-17)
(6.4)
m 1_pm+l
1': Ebro bit—50,0 (6.5)
i=0
p=1—(1-r)N‘l (so)
1— - 2 ’" W
l/,u= p p( p) —o*+tx+tc P +p(N-1)(tx+tc——l-)—) (6.7)
1—2p 2 l—p l—p
Pa =1-e—M (6.8)
. vi
Pb =.0=— (6.9)
,u

tx = RTS + SIFS + CTS + SIFS + Header+ DATA + DIFS (6.10)

tc =RTS+DISF (6.11)

where m is the maximum number of retransmissions, m ’ is the maximum number of

172

back-off stage, 0' is the slot unit duration of CSMA/CA, W is the minimum
congestion window size, N is the number of contenders, A is the data rate and ,u
is the service rate.

Equation 6.4 is the expression of but, the steady-state probability of the active
state (i,k) when i=0 and k=0, where i is for the number of retransmissions and k is
for the contention window size. Equation 6.5 expresses the probability 1 that a
node transmits in a randomly chosen time slot. Having the transmission probability
r , a collision happens if at least two nodes transmit at the same time. This gives the
collision probability p in Equation 6.6. Equation 6.7 is obtained from [91] by having
the collision probability p in Equation 6.6. Equation 6.8 is the expression of the
probability that there is at least one frame arriving during the unit time slot 0'.
Equation 6.9 shows the probability that a node is in a busy period or equivalently.
Both Equation 6.8 and 6.9 are written based on the queuing theorem in [92]. It is
shown in Equation 6.10 for the average time that the channel is sensed busy due to
as successful transmission. Equation 6.11 gives the average time that the channel is
sensed busy due to a collision.

6.3.3 Mechanics of Protocol Switching
The general protocol switching logic is shown in Figure 6.10 in the form of a pseudo
code. There are three steps which a newly joined node needs to follow for protocol
switching logic.

(1) Upon joining the network, a new node first relies on a TDMA logic to choose

a TDMA slot for future use. This is just an upfront one time process. At this

173

stage, the new node should not transmit any valid data messages. At the same
time, the new node starts to build the neighbor table, which contains up to
2-hop neighbors’ information including the moving average of their queue
utilization and number of contenders. The complete information of the
moving average of queue utilization and number of contenders is maintained
by the new node.

(2) New node can then start with any type of MAC protocols to transmit valid
data messages. There is no difference between starting with TDMA and
CSMA/CA protocol. In our experiments, we start with CSMA/CA. The
pseudo code is also shown with CSMA/CA as the starting MAC protocol.

(3) After starting with CSMA/CA protocol, the new node enters CSMA/CA
MAC state which lasts for W message transmissions. During the W message
transmissions, the new node will periodically check all its 2-hop neighbors’
information about their queue utilizations and numbers of contenders. When
W message transmissions are over, if the node finds that the protocol
switching decisions are satisfied by at least D% of the total number of active
2-hop neighbors, it then simply goes to the TDMA MAC state. Otherwise, it
assumes that in current network traflic and density situation it is not
necessary to switch the protocol. In this case, the node maintains the current
CSMA/CA protocol unchanged and starts to check the next W message

transmissions.

174

 

/* MAC Protocol Switching Logic for Each Node */

Initial State:
Choose a TDMA slot using any T DMA MAC logic;
Start to maintain a moving average of local queue
utilization;
Start to maintain Z-hop neighbor table about
neighbors ’ protocol type, queue utilization and their
number of contenders;
Start to run CSMA/CA MAC protocol;
WW:
Periodically check 2-hop neighbors ’ queue utilization
& number of contenders for W message transmissions;
Count the number of 2-hop neighbors, which satisjfv
the protocol switching decisions in Section 6. 3.2
if (W is over && count > D% of total number of 2-hop

neighbors)
goto ZDM MC State;
ZDMA mg Statg:

Periodically check Z-hop neighbors ’ queue utilization
& number of contenders for W message transmissions;
Count the number of 2—hop neighbors, which satisjy
the protocol switching decisions in Section 6.3. 2;
if (W is over && count > D% of total number of 2-hop
neighbors)
goto (EM/CA MC Statg;
If (no more trafiic for Tseconds'
goto W‘

 

 

 

Figure 6.10: Pseudo code of MAC protocol switching logic

While in the TDMA MAC state, the node still periodically checks 2-hop
neighbors’ information to see if they satisfy the protocol switching decisions. Like in
CSMA/CA MAC state, if there is at least D% out of total number of 2-hop neighbors
satisfy the protocol switching decisions, the node then goes to CSMA/CA MAC state.
In addition to that, in our experiments we also define that if a node does not have

traffic for T seconds, it switches back to CSMA/CA MAC protocol because of low

In the general protocol switching logic, the Initial state is a transient state that

only occurs during initial node joining. The transition between CSMA/CA and

175

TDMA will only happen when there is a trigger because of network traffic

heterogeneity or variation as we described in Section 6.3.1.

 

 

 

 

 

 

 

 

 

      

 

 

 

 

 

 

 

 

   

 

     

 

 

 

 

 

 

 

 

 

 

 

 

 

MAC Swrtchrng Control Modules Application Layer
a Protocol Switching Logic (e.g. intrusion detection,
Model video surveillance, etc.)
Based “—6 . __ . 1
Threshold ThresholdDecision’Computation FF .- a
I ‘ Transport Layer
, ... . e. .UDP,TCP
Expenment Neighbor Neighbor Local ( g )
Based 1 Protocol Queue Queue
Threshold Sensing Sensing 3805109 ’ RoutiQIaerf - .
Switchable. MAC Layer ‘1 .' i i i 5' i i i ’

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Protocol-1 Protocol-2 Protocol-n
(e.g. TDMA) (e.g. CSMA/CA) ...... with Adaptation
with Adaptation with Adaptation for for Coexistence
for Coexistence Coexistence
f
[ Physical Layer

 

 

 

Figure 6.11: Adapted network stack with dynamic MAC protocol switching logic
6.3.4 Response to Network Topology Variations

Network topology variations can occur due to node joining or node leaving a
network.
6.3.4.1 Node Joining

When a new node attempts to join an existing network, it listens to the
information exchange within its neighborhood. The 2-hop neighbors’ information
can be inferred from the information exchanges of l-hop neighbors like the regular
TDMA does. If all the neighbors are running TDMA MAC, the new node can simply

choose a slot like the ISOMAC logic [73, 74] or any other TDMA logic. However,

176

when few neighbors may run CSMA/CA, which means that the neighbors may not
send anything over a long period. The silent period of the CSMA/CA neighbors
could be larger than the listen period of the new node. The new node has to send an
explicit notification packet to announce its existence, and then gets acknowledge
packets fi'om all its neighbors which run CSMA/CA MAC. The acknowledge packet
is not MAC layer ACK message in CSMA/CA. It is the control message which
belongs to the protocol switching logic. The neighbors’ acknowledge packets contain
the information about their assigned TDMA slots. The slot for the new node then can
be decided based on all neighbors’ slots. After choosing the slot, the new node starts
to run CSMA/CA MAC as the protocol switching logic described in Section 6.3.1.
6.3.4.2 Node Leaving

The logic to deal with node leaving is much simpler compared with the one for
node joining. Only the neighbor table update is needed within the neighborhood. No
additional messages need to be sent. And the transmission rules based on neighbor
table will also be adjusted by reclaiming the slot occupied by according to the
leaving node.
6.4 Experimental Evaluation

We implemented our protocol switching logic on 100 nodes within N52

simulator [76]. We choose a radio data rate of 2 Mbps and fixed packet duration of 2
ms, which is also the TDMA slot duration. All considered traffic is l-hop. All
reported performance numbers are based on l-hop MAC layer traffic. Unless stated

otherwise, we fixed the TDMA frame size to 20 slots for all experiments. The

177

numbers of active nodes and data generation rate have been varied. Before running
protocol switching logic, we run ISOMAC (see Chapter 3) to get TDMA slot
assignment. The other baseline parameters are shown in Table 7.1. The evaluation

time (W) and percentage of decision count (D) are the parameters used in Figure

 

 

 

 

 

 

 

 

6.10.
TDMA MAC Related
Frame Size (number of slots) 20
TDMA Slot Duration 2m
CSMA/CA MAC Related

Minimum Congestion Window Size 32
Maximum Number of Back-off Stage 5
CSMA/CA Slot size 2011s

 

Maximum Number of Retransmission 7

 

 

 

 

 

 

 

 

SIFS Duration 10 us
DIFS Duration 30 us
Protocol Switching Related
Evaluation Time W=3
Percentage of Decision Count D=55%

 

 

Table 6.1: Baseline parameters of experiment
6.4.1 Validation of Protocol Switching Decision Threshold
6.4.1.1 Protocol Switching Decision Threshold
In Section 6.3.2, we develop a mathematical model to estimate the protocol
switching decision threshold. In this section, we illustrate the difference between the
threshold obtained from the model and the threshold obtained through
experimentation. The experiments reported in this section are for a 20-node fully

connected network. All 20 nodes are l-hop neighbors to each others. For TDMA

178

MAC protocol, the frame size is set to 20 slots. Here we only show the decision
threshold for CSMA/CA, since the decision threshold for TDMA is just the queue

utilization value equal to “1” as discussed in Section 6.3.1.

 

 

 

 

 

 

 

 

 

 

l .'
’3. 0.8 r g
g ‘9'experrment
'5 0.6 r' “El-model
‘3 —
o 0.4 l
8
:1
0' 0.2 r

0 1 . r r r

0 5 10 15 20 25
number of contenders

 

 

 

Figure 6.12: Protocol switching decision threshold for CSMA/CA

Figure 6.12 shows the protocol switching decision threshold for CSMA/CA MAC.
The y-axis is the queue utilization (p), which is used in pseudo code in Figure 6.9 in
Section 6.3.2 for switching decision threshold. The curve for model is derived by
solving the series of nonlinear equations stated in Section 6.3.3. Because the TDMA
frame size is 20 slots and TDMA slot duration is 2 ms, the maximum TDMA service
rate #MAX—TDMA is 25 pps (packets/second). Therefore, the data rate ,1 used for
CSMA/CA is the same as #MAX—IDMA , which is 25 pps. The curve for the
experiment is obtained by running simulation for this 20-node network with TDMA
and CSMA/CA MAC individually. We manually find the points where CSMA/CA is

achieving better throughput than TDMA with various number of contenders. The

179

corresponding queue utilization of those points are recorded and shown in Figure
6.12. As can be seen the queue utilization rises in both cases as the number of
contenders increases. This is because the service rate for contention based protocol
CSMA/CA ( #CSA/IA/CA) drops when there are more contenders transmitting at the
same data rate (A ). This was discussed and explained in Section 6.3.1 and 6.3.2. The
difference between the lines for the model and for the experiment initially becomes
large with larger number of contenders, and finally shrinks when both lines meet at

61.1”

the ceiling value of . The initially increasing difference between the model and
the experiment is caused due to the assumptions made by the model. As stated in [85,
87] the model assumes the collision probability p, and the queue busy probability
p b are independent of the number of contenders. However, as the number of
contenders increases, which means that real traflic approaches to saturated scenarios

from unsaturated scenarios, this assumption may not hold true. Finally, the shrinking

difference is because model and experiment queue utilization are both bounded by

6‘1” 6‘12,

the ceiling value of . When the model reaches , it can not grow larger any

more while the experiment keeps approaching “1”.
Figure 6.13 shows the last scenario that is discussed in Section 6.3.1, which is the
saturated service rate for both MAC protocols. From this point onward, the “exp” in
the legend of the graph means the results obtained from experiments, “model” means
the results from solving equations in Section 6.3.2, “mesh” means the average results

for three different arbitrary mesh multi-hop networks, and “l-hop” means the results

from fully connected l-hop networks. Here, the saturated service rates of both MAC

180

protocols are in fact the maximum throughputs of both MAC protocols from

pervious discussion in Section 6.3.

 

 

 

  
 
 
   

 

 

 

 

 

 

240
+ CSMA/CA_exp_md

7,300 ‘ -x— CSMA/CA_mode1

g 160 _ -*- TDMA_model
g -9- TDMA__exp_md

3 120 _ 43- CSMA/CA_exp_l-hop
é -¢- TDMAjXpJ -hop

.§ 80 .

1?.

Q)

m 40 a a.

O 1 1 1 1
O 5 10 15 20 25
Number of Contenders

 

 

 

Figure 6.13: Impacts of number of contenders on maximum service rate

From Figure 6.13, the first observation is that when the traffic density (number of
contenders) becomes larger than certain value (17 contenders in this case) the
saturated service rate of TDMA is larger than that of CSMA/CA. Second, the
experimental result in the l-hop case closely matches the theoretical model result.
Third, the experimental result of a lOO-node arbitrary mesh network has a larger
difference from the model result than the one of l-hop case. This difference comes
from the irregularity of the arbitrary mesh topology. The arbitrariness of node
placement causes the number of contenders to be not uniformly distributed across
the network. Also, nodes at the edge of the network have a much smaller node

degree than nodes in the center. These two factors bring some benefits to CSMA/CA.

181

 

 

 

 

  
 

 

 

 

 

 

 

 

 

 

600
500 ~ ‘” 32
m 0
.. 0
3 400 $3
{5 ._ 22 f9
3. 300 . a
a ' e
:3 +CSMA/CA o
8 200 ‘ -B-TDMA 53
fi + Switching_exp : qb 12
100 a + Switching_model ; .. _. i
— Data Rate ‘ ‘ . -
0 t t ; i i t t 2
0 10 20 30 4O 50 60 7O 80
Time (sec)

 

 

Figure 6.14: Impacts of protocol switching decision thresholds on fully connected network

6.4.1.2 Impacts of Switching Decision Threshold on Fully Connected l-hop
Networks

We use two different protocol switching decision thresholds to evaluate the
performance of real-time protocol switching in this section. In Section 6.4.1.1, we
see that for the 20-node firlly connected network, the largest difierence of decision
threshold between model and experimental data is when the number of contenders is
equal to 16. We thus conduct an experiment in the 20-node fully connected network
having 16 active nodes sending l-hop traffic with variable data rate. Figure 6.14
shows the real-time throughput performance of MAC protocol switching over the
20-node fully connected network. We start our traffic at time 11.0 second with a data
rate of 33.3 packets/second, change the data rate to 5 packets/second at time 31.0

second, and finally change back the data rate to 33.3 packets/second.

182

 

 

 

 

 

 

 

 

 

 

 

 

 

25

20 -
8
'8
5 15 -
o
S
g 10 ~ .
s .
Z 5 —CSMA/CA_exp

—CSMA/CA_model
0 i t .
0 20 40 60 80
Time(sec)

 

 

 

Figure 6.15: MAC protocol dynamics on fully connected networks

As we can see in Figure 6.14, at high rates if running TDMA, the throughput will
be limited by the frame size. But CSMA/CA is able to achieve higher throughput
than TDMA at high rates. At a lower rate, TDMA is expected to perform better than
CSMA/CA because of zero collisions. But the data rate is so low that the benefit of
TDMA is not obvious at lower data rates. However, using protocol switching, the
real-time throughput is generally able to track the upper envelop of both CSMA/CA
and T DMA protocol at both high and low rate scenarios. At high data rates, nodes
choose CSMA/CA to obtain larger throughput, and TDMA is chosen at low rates.
Note that there is a slight difference in throughput performance when switching logic
is obtained based on thresholds from the experiments and from the model.

The difference is further elaborated by using Figure 6.15. Figure 6.15 shows the
CSMA/CA protocol dynamics for all the 20 nodes. The y-axis shows the number of
nodes running CSMA/CA MAC at any given time. The number of nodes running

TDMA MAC can be computed by subtracting the CSMA/CA node count from the

183

total number of network nodes. As we can see in Figure 6.15, due to the difference in
Figure 6.12, the experimental and the theoretical decision thresholds result MAC
switching at difi’erent times. For example, using model based decision threshold,
nodes start to switch to TDMA MAC about 0.5 seconds earlier than using
experimental decision threshold. But this half seconds difference is small enough to
not to make a difference in the throughput figure as shown in Figure 6.14. Especially
when we consider the long term impact of protocol switching, the effect of different

decision thresholds can be considered negligible.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2500 a 35
A 2000 — 30
B _W A
31500—»~~ E
i? _. a it
'5’ 1000 — g
8 +CSMA/CA {3
E +TDMA ‘ _ a
500 - +Switching_model ,. , , . 7, p, _ . - q j 20
+Switch1ng_exp :
+Data Rate 1
0 ‘ 1 . 15
0 20 40 60 80
Time (sec)

 

 

Figure 6.16: Impacts of switching decision thresholds on arbitrary mesh network
6.4.1.3 Impacts of Switching Decision Threshold on Multi-hop Mesh Networks

Experiments are also conducted on a lOO-node network with arbitrary mesh
topology to evaluate the switching logic with decision thresholds obtained from the
model and from experiments. We still maintain the number of contenders within

2-hop neighborhood to be 16. Data rate varies from 33.3 packets/second to 20

184

packets/second at time 31.0 second and back to 33.3 packets/second at time 51.0
second respectively. Similar to the results shown in Section 6.4.1.2 for the fully
connected network, the real-time throughput with protocol switching is able to track
the upper throughput envelope for the mesh network scenario as shown in Figure
6.16. At high rates, nodes switch their MAC to CSMA/CA to achieve larger

throughput, and change to TDMA to maximize the throughput at low rates.

 

 

120

 

 

100—
80 J

60‘

Number of nodes

40“

 

 

'-'CSNL%KLkJmodd .. '

2°"-——-C8huutmgcnp ”"“"'“”“'

O t r r
0 20 4o 60 80

Time (sec)

 

 

 

 

 

 

 

 

 

Figure 6.17: MAC protocol dynamics on arbitrary mesh network
In Figure 6.17, we can see that nodes using the experimental threshold are
switching their protocol around 2 seconds later than when using model threshold.
This explains the approximate 2-second delayed tracking of larger throughput for
experiment threshold compared to the model threshold in Figure 6.16. The difference
between model and experiment decision threshold is limited only at the point of
protocol switching. The latency effect of 2 seconds on upper throughput envelope

tracking is negligible compared with the long term benefit of protocol switching.

185

This is particularly true with the assumption that the switching is relatively
infrequent compared to the usually long operating life of practical networks.
6.4.2 General Network Experiments

In this section, all the experiments are conducted in a general arbitrary mesh
topology. All the protocol switching results are based on the experimental decision
threshold.
6.4.2.1 Impacts of Data Rate

As stated in Section 6.3.1, data rate variance is one of the parameters that affects
the MAC throughput. The data rate variance in wireless sensor networks is caused
by several factors, such as mission objective changes or detection of special events.
In our lOO—node arbitrary mesh network, all nodes using the same data rate send to
one of their l-hop neighbors. The data rate varies from 100 packets/second to 20

packets/second at time 21.0 second and reversely at time 31.0 second.

 

 

  

 

 

 

 

 

 

 

 

 

3500 110
-~ 90
g 3000 * ““1 s
b .
:a, -— 70 3
.5 8
ca. 2500 “ g 8
{b 8
g —o—CSMA/CA ‘” 50 g
.r: O
+Swtchmg __ 30
—Data Rate
1500 I 1 I ' 10
0 10 20 30 40 50
Tirm (sec)

 

 

 

Figure 6.18: Real-time throughput with varying data rate

The real-time throughput values are shown in Figure 6.18. As we can see that for

186

TDMA, the throughput is limited by the maximum TDMA service rate at high data
rates, whereas CSMA/CA is able to provide relatively larger throughput. In a low
rate scenario, TDMA provides better throughput due to zero message collisions.
Using the protocol switching logic, nodes are able to track CSMA/CA throughput at

the high rates and turn to TDMA when the rates are less than the maximum TDMA

service rate (#MAX—IDMA )-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

120

g .
g 80 r
“a
35 60 7
..D
S 40 ~ ..
z . . —CSMA/CA

0 t r ; i

0 10 20 30 40 50
Time(sec)

 

Figure 6.19: MAC protocol dynamics with varying data rate

The dynamic behavior of MAC switching is shown in Figure 6.19. As the data rate
changes from high to low, the number of nodes running CSMA/CA reduces and the
number of nodes running TDMA rises. Based on the switching decision thresholds
represented in Figure 6.12, nodes decide to switch to different protocols based on the
queue utilization, which is the threshold we use for switching. When data rate
changes, the queue utilization does not change immediately. The queue behavior
usually has a lag between rate changes and queue build-up, which is known as the

time for the queue to reach the steady state in standard queuing theory [93]. This

187

explains why usually there is a few seconds delay between the time data rate change
and the nodes switch their protocols.
6.4.2.2 Impacts of Number of Contender Nodes

Besides the data rate, the number of contenders is also a factor that affects the
network throughput performance. An experiment is conducted to study the impacts
of variable number of contenders on the performance of protocol switching. As
shown in Figure 6.20, the number of active nodes starts from 100, changes to 25 at
time 21.0 second, and turns back to 100 at time 31.0 second. When there are only 25
active nodes, they are randomly selected out of all 100 nodes. The number of
contenders in a neighborhood is accordingly changed by varying the number of

active nodes. All active nodes send data to all l-hop neighbors at rate of 35

 

 

 

    
 

 

 

 

 

 

 

packets/second.

3000
6‘ 2500 e +CSMA/CA
% 2000 +TDMA
E- +Switching
E, 1500 d
4:
0.0
§ 1000 -
5‘3

500 r

o r r a
5 15 25 35 45
Time (sec)

 

 

 

Figure 6.20: Real-time throughput with varying number of contenders
According to the graphs in Figure 6.20, CSMA/CA performs better when there are

less number of contenders because of its larger service rate in the absence of

188

collisions as we describe in Section 6.3.1. When the number of contenders increases,
the contention brings down the service rate of CSMA/CA. Observe that the protocol
switching logic is able to track the throughput upper envelope of both the protocols,

providing larger throughput in a manner that is independent of the number of

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

contenders.

120 . :

100-~ j *~ Q '
a ; 11’] _ 1
ti : " i
.o —CSMA/CA

0 . L ,
5 15 25 35 45
Time (sec)

 

Figure 6.21: MAC protocol dynamics with varying number of contenders

The dynamics of protocol distribution is shown in Figure 6.21. Like the results
shown before, the switching of the protocol does not happen at the same time for all
the active nodes. There is an approximate two seconds delay for all the active nodes
before they make the decision for switching.
6.4.2.3 Impacts of Spatially Clustered Traffic Profiles

In the previous experiments, the switching logic causes all the active nodes in a
network to switch their protocols to the same type. The scenarios describe in this
section, active nodes in a network can run different MAC protocols and switch to

different protocols when there is spatial traffic heterogeneity. The experiment here is

189

conducted in a rectangular field with an arbitrary mesh network topology consisting
of 400 active nodes. The varying traffic profile is shown in Figure 6.22. The traffic
distribution is changed from Profile-(l) to Profile-(2) at time 31.0 second. In high
traffic density region, a node sends to all its l—hop neighbors each with a data rate of
3 packets/second. Nodes in the medium traffic density region send to only one l-hop
neighbor at a data rate of 140 packets/second. Nodes in the low traffic density region

send to only one l-hop neighbor at a rate of 12.5 packets/second.

 

      

Profile-(1) Profile-(2)

High Traffic Density

Medium Traffic Density
Low Traffic Density

  

 

 

 

Figure 6.22: Pictorial diagram of spatial traffic variation

A node in the high traffic density region is expected to run TDMA to achieve
higher throughput, because the CSMA/CA service rate is less than the TDMA
service rate at this traffic level (due to data rate and number of contenders).
CSMA/CA is expected in a medium traffic region. TDMA is then favored in a low
density region.

The real-time throughput result is shown in Figure 6.23. The scenario with
switching enable achieves larger throughput than both scenarios in which the TDMA

or CSMA/CA protocol was run individually in the entire network. The reason is that

190

with acn'vated protocol switching, TDMA is able to be used in various traffic density
regions when needed. So is CSMA/CA. If only one protocol is used in the entire
network, the network-wide throughput is afi’ected either by the throughput in high
traffic density region or in low traffic density region. With protocol switching
enabled, it is possible to provide the best achievable throughput at both high and low
traflic density regions. When the traffic profile is flipped over completely (from
profile (1) to profile (2) in Figure 6.22), the switching logic is able to adjust

appropriate protocols to accommodate the changes.

 

 

   

 

 

 

 

 

 

 

 

 

8200
8000 -
ii
g 7800 —
3'
8. 7600 ., ;
Eb +CSMA/CA
O 7400 i
E +TDMA
7200 - + Switching enable
7000 l I 1 l 1
0 10 20 _ 30 40 50 6O
Trme (sec)

 

Figure 6.23: Real-time throughput with varying spatial traffic profile
Results in Figure 6.23 show the adaptation process due to switching. Note that
during the actual switching, there is a temporary throughput drop. While the
protocols of nodes are switching, certain packets experience collisions, and thus
MAC layer drops and queue drops give rise to reduced service rate. After the

transient state is over, the throughput benefit of switching resumes.

191

 

 

 

 

 

 

 

 

 

 

 

 

 

 

500
3400 ~ —-—
“O
2
,H 300 — f
O .
£200 _ _ (_CSMA/CA
E v--TDMA
z 100 — i
O r r 1 l l
0 10 20 Timgqsec) 4o 50 60

 

 

 

Figure 6.24: MAC protocol dynamics with varying spatial traffic profile

Two observations can be made from the reported in Figure 6.24. First, nodes
change their protocols in a period of few seconds after the traffic profile actually
changes. Second, the protocol distribution is different in these two traffic density
profiles across time. During the time that the network is working in the first traffic
density profile, the number of nodes running TDMA is equal to the number of nodes
running CSMA/CA. However, during the time running the second traffic density
profile, there are 328 nodes running TDMA and 72 nodes running CSMA/CA. The
variance of network MAC protocol distribution in two trafiic density profiles is
coming from the irregularity of the network connectivity, although the traffic pattern
is similar to each other in both traffic scenarios. Each node changes its protocol
based on the switching decision threshold shown in Figure 6.9 and the logic in
Figure 6.10. Due to the topology irregularity, even nodes in the same trafic density

region experience difl’erent number of contender nodes (n) and queue utilization (p),

which are used in the switching decision threshold and the switching logic. The

192

different views of n and p cause nodes to run different protocols as expected. For
example, some nodes in the medium traffic density region run TDMA instead of
expected CSMA/CA.

6.5 Conclusions and Ongoing Work

We present a distributed Dynamic MAC Protocol Switching paradigm, which
achieves the goal of maximizing network throughput in the presence of traffic and
topology heterogeneity. The key idea behinds Dynamic MAC Protocol Switching is
to use local neighborhood information and traffic density to decide the most
favorable MAC protocol under current traffic conditions for each active node.
Instead of only the sink node constantly monitoring incoming trafi'rc as in the
protocol Funneling-MAC [42], each node in the proposed scheme constantly
monitors the local traffic, computes the most favorable MAC protocol, and makes
decision on switching within its neighborhoods. Simulation experiments demonstrate
that with the novel dynamic protocol switching logic, the MAC layer is able to
achieve maximum throughput in response to the network traffic heterogeneity,
including data rate, number of contenders and traffic spatial patterns.

Ongoing work includes refining transmission rules for CSMA/CA to achieve
higher throughput in Multi-MAC Operating Mode. For examples, the transmission
rules can include a smarter deferring mechanism when overlapping with TDMA slots,
and giving TDMA priority with less than one probability. We also intend to study the
processes and effects of protocol switching notification. Finally new protocol

switching criteria could be introduced to have better performance.

193

Chapter 7
Summary and Future Work
7.1 Summary

In this thesis we present a MAC self organization framework for both intra-MAC
and inter-MAC for wireless ad hoc and sensor networks. These frameworks are
developed to address the specific design issues raised by unique constraints of the
wireless ad hoc and sensor networks. Such constraints include ad hoc deployment,
energy limitation, topology changes due to mobility, infrastructure failure,
communication errors and trafiic heterogeneity.

The objective of the proposed ISOMAC is to address the intra-MAC self
organization problems with energy limitations, network dynamics, and ad hoc
deployment In ISOMA C, a fixed length bitmap vector is used in each packet header
for exchanging relative slot timing information across immediate and up to 2-hop
neighbors. It is shown that by avoiding explicit timing information exchange,
ISOMAC can work without network-wide time synchronization which can be
prohibitive for severely cost-constrained sensor nodes in very large networks.
Through simulation experiments it was shown that ISOMAC s performance without
time synchronization is just marginally worse than that with synchronization. Results
demonstrate that with in-band bitmap vectors of moderate length, ISOMA C
converges reasonably quickly - approximately within 4 to 8 TDMA fi'ame duration.
Also, if the bitmap is restricted within 10% of packet duration, the energy penalty of

the in-band information is quite negligible.

194

In Chapter 4, a Minimized Slot Misordered Routing (MSMR) protocol has been
proposed for end-to-end delay mitigation in sensor networks with TDMA MAC.
Different from the existing D-MAC [34], which resolves the problem by
delay-optimized slot allocation based on pre-set routes, MSMR seeks an opposite
point of view by finding the delay-optimized routing based on pre-set TDMA slot
allocation. MSMR has been targeted towards delay sensitive sensor network
applications such as tactical surveillance, intrusion detection, and industrial process
monitoring. Delay reduction in MSMR is accomplished by computing least cost
routes with a link cost formulation based on the degree of misordering of the TDMA
slots of nodes across a link. It has been shown that with realistic TDMA models and
sensor event generation rates, in a 5000-node sensor network, MSMR can reduce the
reporting delay of emergency events by up to 3.5 seconds, which is a significant
amount of time for possible remedial actions. We have also shown that while
controlling end-to-end delay due to slot misordering, at higher event rates MSMR
can give rise to undesirable queuing delay as a result of congestions. We propose a
centralized Balanced MSMR routing protocol that can strike a balance between
queuing delay and slot misordering delay by adjusting link costs based on
instantaneous node level congestions.

We adapt the concept of ISOMAC logic in the context of vehicular networks and
propose the _Y_e_hicular Self-Organizing MAC; (VeSOMAC) protocol in Chapter 5.
VeSOMAC is designed to be vehicle location and movement aware so that the MAC

TDMA slots in a vehicle platoon can be time ordered based on the vehicles’ relative

195

locations. Simulation results of both highway and urban intersection scenarios
demonstrate that unlike the 802.11 style contention based protocols, VeSOMAC can
offer better vehicle safety and data transfer throughput through smaller and bounded
packet latency. It has been also shown that the protocol convergence during topology
changes is fast including platoon mergers and vehicle passing.

In Chapter 6, a distributed Dynamic MAC Protocol Switching logic is presented.
The key idea behind our Dynamic Protocol Switching is to use local neighborhood
information to decide the most favorable MAC protocol under current traffic
conditions for each active node. Each node constantly monitors the local traffic,
computes the most favorable MAC protocol, and makes decision on protocol
switching within its neighborhood. The experiments demonstrate that with the novel
dynamic MAC protocol switching logic, the MAC layer is able to enhance
throughput in response to the network traffic heterogeneity, including data rate, and
the number of contenders.

7 .2 Future Work
Here, we highlight some of the key items tat we plan to pursue in the future:
> Develop a theoretical approach to prove the convergence of the asynchronous
ISOMAC protocol using some methods fi'om the multi-agent system[94-105]
in embedded control system theories [106-108].
‘9 For our proposed centralized Balanced MSMR routing protocol, future work
includes developing a distributed Balanced MSMR protocol. The goal is to

avoid network wide information flooding and to let the sensor nodes compute

196

the delay optimal routing locally.

The extensions of the VeSOAMC framework include border ITS scenarios
involving vehicle-to-roadside communication, bi-directional and multiple
highway lanes, and the presence of multiple simultaneous emergency events.
We also intend to evaluate it in the presence of more detailed physical layer
models including fading and multi-paths. Finally, variable traffic rates will be
introduced in VeSOMAC by allocating multiple slots to a vehicle in each
T DMA frame.

Ongoing work of Dynamic Protocol Switching includes refining transmission
rules for CSMA/CA to achieve higher throughput in Multi-MAC Operating
Mode. For examples, the transmission rules can include a smarter deferring
mechanism when overlapping with TDMA slots, and giving TDMA priority
with less than one probability. We also intend to study the processes and
effects of protocol switching notification. Finally new protocol switching

criteria could be introduced to have better performance.

197

Appendix A
A Model for ISOMAC Convergence in Linear Networks

We construct an analytical model for ISOMACs convergence in a linear network
as described in Section 3.3.2.5. The purpose of this model is to validate the
experimental convergence results presented in Figure 3.6:b. Consider the linear
topology in Figure A.l :a, in which there are two disconnected physical clusters {01 ,
(12 , ...... an} and . Within each cluster, nodes are in allocation steady state, and
as shown in Figure A.l:b, the inter-slot timing separation between connecting nodes
is kept fixed at 3 slots, which is what was used for the experiments described in
Section 3.6.2. Also, it is assumed that the separation of slots between the two clusters
is larger than the bitmap size.

We study the allocation dynamics after node 00 joins right in between the
clusters so that they are forced to merge to a single connected graph. When 00
joins, according to ISOMA C-A described in Section 3.3.2.6, 610 will choose a slot
right at the middle of those of 0.1 and 01. Since in this model the topology and
slot allocation are symmetric across the clusters, and the slot of a0 never moves, we
analyze the slot movement by observing it only in one cluster. In Figure A.l :c, slot
movements of the right hand cluster is demonstrated, keeping the slot location of
00 fixed.

After 00 joins the network in step-0, the separation between slots of 00 and
(10, a], 02, ...... an are defined as 00(0), 01(0), 02(0), an (0). In

step-l, in order to satisfy the bitmap constraint, ao , a1 , £12 , ...... an.

198

sequentially pick up new slots. After step-l, the separation durations are defined as
do (1) , (11(1) , 02 (1) , 61,,(1). To state generally, the separation between node
00 and node a,- in step j is a,- (j) . Mth the stated initial inter-node separation of
3 slots, we can write ao(O)=0, ai(0)=T+3xi, for i= 1, 2,... n, where T is the
half of the initial timing separation between the two disconnected clusters, i.e.

T=01(0)—00(0).

 

 

   

an anl... 81 210 311-1 an

"=32: """ H .2: E
(a) Physical topology "’-

ana'n-r.. as an an 31 a2... an.1 an

 

[1 FL: n [1 Fl 11 1:: [H]
(b) Slot allocation 1’2 Tn-l,n
210 at a2... an-lan

Step-0 -1 11 n 11 " _1

F335;!

r alto;
Step-l H 1] 1
a1(1)—)1
”(1H,. *

\ any}

Step-j 1 , 11 "I 1'1
(-—a1(r)—)l

(--—-az(j

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

aflU‘r
(c) Iterative slot movement

 

 

 

Figure A. 1: Convergence model in linear networks

According to the ISOMAC-A protocol, as described in Section 3.3.2.6, the

199

quantity a,- (j) will reduce, although non-monotonically, with increasing iteration
step j. We make a simplifying assumption that the edge node 0,, will always
follow node an_1 ’5 slot at each allocation iteration step. This implies
an (l) = an—l(j) for all j. With this assumption, the quantity 01(1) becomes

monotonically decreasing and the protocol becomes analytically tractable. Now,
. , , . l . .
01(1) can be written as: 00(1)=0.atU)=§(at—1(J)+at+1(J-1)) (Al).

for i = 1, 2,.... n-l. With this iteration model, the protocol is said to have converged
when the condition a1 (j) < B is true. This is because at any protocol step-j,
01 (j) represents the largest inter slot separation between any two connecting
nodes in the cluster. Therefore, if this separation satisfies the bitmap constraint then
all a ,- (j) values will satisfy the bitmap constraint, thus the protocol will have
converged.

We use the iterative expression in Equation Al to compute the convergence time
from the model, and compare that with experimental results for different cluster sizes
in Figure 3.6:b. Observe that the experimental results are always slightly larger that
the values from the model.

The following assumptions in the model account for this difference. The first
assumption that an (j) = an_1( j) in the model results in a faster convergence than
what happens in the experiments. This is because in the experiments the edge node
does not always move. When the distance between edge node and its neighbors is
smaller than the bitmap range, the bitmap constraint is satisfied for the edge node

and therefore, it does not move. This slows down the rate of reduction of the inter

200

cluster separation, which is the speed of convergence in this scenario.

Another assumption here is that nodes’ slot movements at two sides of the center
node 610 are symmetric, which means slots used by the two clusters are
non-overlapping. In the experiments, however, this may not always be true. For
example, when n=1, two nodes at each side may end up picking an overlapped slot,
which would require four more frames for resolving such a collision. The collision
probability will decrease with larger bitmaps. That is why with increasing bitmaps,

the experimental results have better agreement with this model (Figure 3.6:b).

201

[11

[21

[31

[4]
[51

[6]

[71

[81

[9]

[101

[111

[12]

[131

[14]

Bibliography

P. Gupta and P. R. Kumar, "Capacity of wireless networks," IEEE
Transactions on Information Theory, vol. 64, pp. 388 - 404, March 2000.

J. Li, C. Blake, D. S. J. D. Couto, H. 1. Lee, and R. Morris, "Capacity of Ad
Hoc Wrreless Networks," in the 7th ACM International Conference on
Mobile Computing and Networking, Rome, Italy, July 2001.

"Mote Documentation and Development Information,"
http://www.cs.berkeley.edu/~awoo/smartdust.

www.xbow.com.

I. F. Akyildiz, W. Su, and Y. Sankarasubramaniam, "A Survey on Sensor
Networks," in IEEE Communications Magazine. vol. 40, 2002, pp. 102—114.

I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless
sensor networks: a survey," Computer Networks: The International Journal of
Computer and Telecommunications Networking, vol. 38, pp. 393-422, March
2002.

H. Karl and A. Willig, "A short survey of wireless sensor networks,"
August 2003.

N. Xu, "A Survey of Sensor Network Applications," University of Southern
California 2003.

W. Ye, J. Heidemann, and D. Estrin, "An Energy-Efficient MAC Protocol for
Wrreless Sensor Networks," in INFOCOM, June 2002, pp. 1567-1576.

S. Singh and C. S. Raghavendra, "PAMAS: Power aware multi-access
protocol with signaling for ad hoc networks," ACM Computer
Communication Review, vol. 28, pp. 5-26, July 1998.

J. Rao and S. Biswas, "Biologically Inspired Mobility Models for Energy
Conservation in Sensor Networ ," in The Second IEEE Workshop on
Embedded Networked Sensors,, Australia, 2005.

J. Rao and S. Biswas, "Controlled Node Mobility: A Mechansim for Energy
Load Distribution in Sensor Networks," in IEEE Globecom 2006, 2006.

N. Bulusu, J. Heidemann, and a. D. Estrin, "GPS-less Low Cost Out Door
Localization for Very Small Devices," Technical report 00729, Computer
Science Department, USC April 2000.

S. Gage, "Computational Ecology and Visualization Laboratory,"
http://envirosonic.cevl.msu.edu/Home.asp.

202

[15]

[16]

[171

[131

[191

[20]

[211

[221

[23]

[241

[251
[261

[271

S. Kumar, V. S. Raghavan, and J. Deng, " Medium Access Control Protocols
for Ad-Hoc Wireless Networks: A Survey," Elsevier Ad-Hoc Networks
Journal, vol. 4, pp. 326-358, May 2006.

W. Ye and J. Heidemann, "Medium Access Control in Wireless Sensor
Networks," Information Sciences Institute, University of Southern California
October, 2003. .

A. Tanenbaum, Computer Networks, 4 ed.: Prentice Hall PT R, 2002.

I. Demirkol, C. Ersoy, and Fatih Alagoz, "MAC Protocols for Wireless
Sensor Networks: A Survey," in IEEE Communication Magazine, April,
2006.

P. Naik and K. M. Sivalingam, "A survey of MAC protocols for sensor
networks," in Wireless sensor networks, 2004, pp. 93 - 107.

C. Gershenson, "Design and Control of Self-organizing Systems." vol. PhD:
Vrije Universiteit Brussel, 2007.

C. Gershenson, "A general methodology for designing self-organizing
systems," ECCO, Vrije Universiteit Brussel May 2005.

T. Dam and K. Langendoen, "An Adaptive Energy-Efficient MAC Protocol
for Wireless Sensor Networks," in lst ACM International Conference on
Embedded Networked Sensor Systems, Nov. 2003, pp. 171-180.

V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves, "Energy-Efficient,
Collision-Free Medium Access Control for Wireless Sensor Networks," in

International Conference on Embedded Networked Sensor Systems, Nov.
2003, pp. 181-192.

Z. Chen and A. Khokhar, "Self organization and Energy Efficient TDMA
MAC Protocol by Wake up for Wireless Sensor Networks," in lst Annual
IEEE Communications Society Conference on Sensor and Ad Hoc
Communications and Networks 2004 (IEEE SECON' 04), Oct. 2004, pp.
335-341.

D. Bertsekas and R. Gallager, Data Networks, 2nd ed.: Prentice Hall, 1992.

H. Karvonen and C. Pomalaza-Raez, "A cross layer design of coding and
awake/sleep periods in WSNS," in the 17th IEEE International Symposium
on Personal, Indoor and Mobile Radio Communications (PIMRC '06),
Helsinki, Finland, September 2006, pp. 1-5.

C. Buratti, A. Giorgetti, and R. Verdone, "Cross-layer design of an
energy-efficient cluster formation algorithm with carrier-sensing multiple
access for wireless sensor networks," EURASIP Journal on Wireless
Communications and Networking vol. 5, pp. 672 - 685, October 2005.

203

[28]

[29]

[301

[31]

[32]

[331

[341

[35]

[36]

[371

[3 8]

[391

V. Srivastava and M. Motani, "Cross-layer design: a survey and the road
ahead," IEEE Communications Magazine, vol. 43, pp. 112- 119, December
2005.

S. Cui, R. Madan, A J. Goldsmith, and S. Lall., "Cross-layer Energy and
Delay Optimization in Small-scale Sensor Networks," IEEE Transactions on
Wireless Communications, vol. 6, pp. 3688--3699, 2007.

C.-F. Chou and K.-T. Chuang, "CoLaNet: a cross-layer design of
energy-efficient wireless sensor networks," in IEEE Systems
Communications (ICW '05), Montreal, Canada, August 25, pp. 364- 369.

H. Kwon, T. H. Kim, S. Choi, and B. G Lee, "A cross-layer strategy for
energy-efficient reliable delivery in wireless sensor networks," IEEE
Transactions on Wireless Communications, vol. 5, pp. 3689-3699, 2006.

X. Lu, Y. Sun, J. Yu, and W. Yan, "An energy efficient cross-layer routing
algorithm for wireless sensor networks," in the 1st IEEE Conference on
Industrial Electronics and Applications (ICIEA '06), Singapore, May 2006,

pp. 1-5.

I.-Y. Kong and W.-J. Hwang, "Lifetime maximization by cross-layer
interaction in wireless sensor networks," in the 8th International Conference
Advanced Communication Technology (ICACT '06), , Phoenix Park, Korea,
February 2006, pp. 2055-2060.

G. Lu, B. Krishnamachari, and C. S. Raghavendra, "An Adaptive
Energy-efficient and Low-Latency MAC for Data Gathering in Wireless
Sensor Networks," in 18th International Parallel and Distributed Processing
Symposium, Apr. 2004, p. 224.

S. Cui, R. Madan, A. J. Goldsmith, and S. Lall, "Energy-delay Tradeoff for
Data Collection in Sensor Networks," in Intemation Communication
Conference (ICC2005), South Korea, 2005.

N. H. Vaidya, "Mobile Ad-hoc Networks: Routing, MAC and Transport
Issues," http://www.crhc.uiuc.edu/~nhv.

Q. Xu, T. Mak, J. Ko, and R. Sengupta, "Vehicle-to-Vehicle Safety
Messaging in DSRC," in the lst ACM International Workshop on Vehicular
ad hoc networks, October 01-01, 2004.

R. M. Yadumurthy, A. Chimalakonda, m. Sandashivaiah, and R.
Makanaboyina, "Reliable MAC Broadcast in Directional and
Omni-directional Transmissions for Vehicular Ad Hoc Networks," in the 2nd
ACM International workshop on Vehicular ad hoc networks, 2005.

T. Liu, J. A. Sylvester, and A. Polydoros, "Performance Evaluation of

204

[40]

[411

[42]

[431

[44]

[451

[461

[47]

[48]

[49]

[501

R-ALOHA in Distributed Packet Radio Networks with Hard Real-time
Communication," in IEEE Vehicle Technology Conference 1995.

R. Verdone, "Multihop R-ALOHA for Intervehicle Communications at
Millimeter Waves," IEEE Transaction on Vehicular Technology, vol. 4, 1997.

S. Katragadda, G M. C.N.S., R. R. M.S., K. S. M, and R. Sachin, "A
Decentralized Location-based Channel Access Protocol for Inter-vehicle
Communication," in Vehicular Technology Conference (VTC 2003-Spring),
2003.

G-S. Ahn, E. Miluzzo, A. T. Campbell, S. G. Hong, and F. Cuomo,
"Funneling-MAC: A Localized, Sink-Oriented MAC For Boosting Fidelity in
Sensor Networks," in Fourth ACM Conference on Embedded Networked
Sensor Systems (SenSys 2006) Boulder, Colorado, USA, November 2006.

K. Sohrabi, J. Gao, V. Ailawadhi, and G J. Pottie, "Protocols for
Self-Organization of a Wireless Sensor Network," IEEE Personal
Communications, vol. 7, pp. l6-27 Oct. 2000.

T. Wu and S. Biswas, "A self-reorganizing Slot Allocation Protocol for
Multi-cluster Sensor Netwo ," in Fourth International Symposium on
Information Processing in Sensor Networks(IPSN 2005) Apr. 2005, pp.

309-316.

J. Reason and J. M. Rabaey, "A Study of Energy Consumption and
Reliability in a Multi-Hop Sensor Network," in ACM SIGMOBILE Mobile
Computing and Communications, Jan. 2004, pp. 84-97.

A. Woo and D. E. Cullar, "A Transmission Control Scheme for Media Access
in Sensor Networ ," in the 7th annual international conference on Mobile
computing and networking, 2001, pp. 221-235.

N. Abramson, "The Aloha system - Another Alternative for Computer
Communication," in Fall Joint Computer Conference, AFIPS Conference
1970, pp. 281-285.

L. Kleinrock and F. Tobagi, "Carrier Sense Multiple Access for Packet
Switched Radio Channels," in International Conference on Communications,
Minneapolis, Minnesota, Jun. 1974, pp. 21B-l -21B-7.

"Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)
Specification," LAN MAN Standards Committee of the IEEE Computer
Society, 1997.

ETSI, "Broadband Radio Access Networks (BRAN); HIPERLAN type 2
Technical Specification; Physical (PHY) layer." vol. DTS/BRAN-0023003,
Aug. 1999.

205

[511

[521

[531

[541

[55]

[56]

[571

[58]

[591

[601

[61]

[62]

[63]

F. Sivrikaya and B. Yener, "Time Synchronization in Sensor Networks: A
Survey," IEEE Networks, pp. 45-50, July/August 2004.

B. Sundararaman, U. Buy, and A. D. Kshemkalyani, "Clock Synchronization
in Wireless Sensor Networks: A Survey," Ad-Hoc Networks,, vol. 3, pp.
281-323, May 2005.

Y. Zhang, M. Roughan, C. Lund, and D. L. Donoho, "Estimating
Point-to-Point and Point-to-Multipoint Traffic Matrices: An
Information-theoretic Approach," IEEE/ACM Transactions on Networking,
vol. 13, pp. 947-960, Oct. 2005.

G. Urvoy-Keller, G. Hebutene, and Y. Dallery, "Traffic Engineering in a
Multipoint-to-Point network," IEEE Journal on Selected Areas in
Communications, vol. 20, pp. 834-849, May 2002.

R Nelson and L. Kleinrock, "Spatial-TDMA: A Collision-free Multihop
Channel Access Protocol," IEEE Transaction on Communications, vol. 33, pp.
934-944, September 1985.

A. El-Hoiyfi, "Spatial TDMA and CSMA with Preamble Sampling for Low
Power Ad Hoc Wireless Sensor Networ ," in International Symposium On
Computer and Communication, 2002.

K. Khan and H. Peyravi, "Delay and Queue Size Analysis of TDMA with
General Traffic," in the Sixth International Symposium Modeling, and
Simulation of Computer Systems, July 1998, pp. 217-225.

C. Intanagonwiwat, R Govindan, and D. Estrin, "Directed Diffusion: A
Scalable and Robust Communication Paradigm for Sensor Networks," in the
6th Annual International Conference on Mobile Computer and Networks,
August 2000, pp. 56-67.

W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An
Application- Specific Protocol Architecture for Wireless Microsensor
Networks," IEEE Transaction on Wireless Communication, vol. 1, pp. 660-70,
October 2002.

S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin, and A. O. Fapojuwo, "A
Centralized Energy-Efficient Routing Protocol for Wireless Sensor
Networks," IEEE Radio Communication, pp. 58-813, March 2005.

"Intelligent transportation systems," United States Department of
Transportation, www.its.dot.gov/index.htm.

L. Armstrong, "Dedicated Short Range Communications (DSRC),"
www.leearmstrong.com/DSRC/DSRCHomeset.htm.

Y. Liu, F. Dion, and S. Biswas, "Dedicated Short-range Wireless

206

[64]

[651

[661

[67]

[68]

[691

[70]

[711

[721

[73]

[74]

[75]

Communications for Intelligent Transportation System Applications: State of
the Art," ITS and vehicle-highway automation, vol. 1910, 2005.

Y. Wang and B. Bensaou, "Achieving Fairness in IEEE 802.11 DFWMAC
with Variable Packet Size," in IEEE Global Telecommunication Conference,
2001.

T. Pagtzis, P. Kirstein, and S. Hailers, "Operational and Fairness Issues with
Connection-Less Traflic Over IEEE802.llb," in IEEE International
Conference on Communication (ICC), 2001.

H. Krishnan and C. Kellum, "Use of Communication in Vehicle Safety
Application," Internal Report of General Motors Company 2002.

M. Ergen, D. Lee, R. Sengupta, and P. Varaiya, "WTRP-Wireless Token Ring
Protocol," IEEE Transaction on Vehicular Technology, vol. 53, 2004.

T. Nagaosa and T. Hasegawa, "Code Assignment and the Multicode Sense
Scheme in an Inter-Vehicle CDMA Communication Network," IEICE
TRANSACTTONS on Fundamentals of Electronics, Communications and
Computer, vol. E81-A, 1998.

I. Rhee, A. Warrier, J. Min, and L. Xu, "DRAND: Distributed Randomized
TDMA Scheduling for \Vrreless Ad-hoc Networks," in the 7th ACM
international symposium on Mobile ad hoc networking and computing,
Florence, Italy, May 22-25, 2006,.

I. Rhee, A. Warrier, M. Aia, and J. Min, "Z-MAC: A Hybrid MAC for
Wireless Sensor Networks," in ACM SenSys 2005, 2005.

"Michigan Auto Accident News,"
www.michiganautolaw.com/blog/michiganautoaccidents/index.php.

X. Yang, J. Liu, F. Zhao, and N. Vaidya, "A Vehicle-to-Vehicle
Communication Protocol for Cooperative Collision Warning," in the First
International Conference on Mobile and Ubiquitous Systems: Networking
and Services, 2004.

F. Yu, T. Wu, and S. Biswas, "Towards In-Band Self-Organization in
Energy-Efficient MAC Protocols for Sensor Networks," IEEE Transaction of
Mobile Computing, Accepted 2007.

S. Biswas and F. Yu, "An in-band self-organized MAC protocol for sensor
networks," in SPIE in Wireless Sensing and Processing, Orlando FL, USA,
May 12, 2006.

P. Varaiya, "Smart Cars on Smart Roads: Problems of Control," IEEE
transaction Automatic Control, vol. 38, 1993.

207

[76]

[771

[78]

[79]

[30]

[811

[821

[83]

[84]

[85]

[861

[87]

[88]

"The network simulator: NS-2," www.isi.edu/nsnam/ns.

"2006 michigan state police testing evaulation,"
www.michigan.gov/documents/MSP_Eval_l 4682 3_7 .pdf.

T. J. Gates, D. A. Noyce, and L. Laracuente, "Analysis of Dilemma Zone
Driver Behavior at Signalized Intersections," in Transportation Research
Board (TRB) of the National Academies the 86th Annual Meeting January
2007.

C. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers," in the ACM
SIGCOMM, October 1994.

H. Balakrishnan, "Opportunities and challenges in high-rate wireless sensor
networking," in 29th Annual IEEE International Conference on Local
Computer Networks, 2004. , November 2004.

N. Abramson, "The Aloha system - Another Alternative for Computer
Communication," in AFIPS, 1970, pp. 295-298.

J. Polastre, J. Hill, and D. Culler, "Versatile low power media access for
wireless sensor networks," in the 2nd international conference on Embedded
networked sensor systems, 2004, pp. 95 - 107.

F. Yu, T. Wu, and S. Biswas, "Towards In-Band Self-Organization in
Energy-Efficient MAC Protocols for Sensor Networks," IEEE Transaction of
Mobile Computing, vol. 7, pp. 156-170, February 2008.

"Funneling-MAC Technical Report:
http://www.cs.dartmouth.edu/~sensorlab/funneling-mach’APTR-2006-08-00
3.pdf.."

J. V. Sudarev, L. B. White, and S. Perreau, "Performance Analysis of 802.11
C SMA/CA for Infrastructure Networks under Finite Load Conditions," in
The 14th IEEE Workshop on Local and Metropolitan Area Networks, 2005.
LANMAN 2005. , September 2005.

M. Y. Chung, M.-H. Jung, T.-J. Lee, and Y. Lee, "Performance Analysis of
HomePlug 1.0 MAC With CSMA/CA," IEEE Journal on Selected Areas in
Communications, vol. 24, pp. 1411-1420, July 2006.

W. Lee, C. Wang, and K. Sohraby, "On Use of Traditional MIG/1 Model for
IEEE 802.11 DCF in Unsaturated Traffic Conditions," in IEEE Wireless
Communications and Networking Conference (WCNC' 06), Las Vegas,
Nevada, April 2006, pp. 1933-1937.

Y. Barowski and S. Biaz, "The Performance Analysis of IEEE 802.1] Under
Unsaturated Traffic

208

[89]

[901

[911

[921

[93]

[941

[95]

[96]

[97]

[98]

[99]

[100]

[101]

Conditions,ftp://ftp.eng.aubum.edu/pub/techreports/csse/04/CSSE04-08.pdf,"
August 2004.

F. Daneshgaran, M. Laddomada, F. Mesiti, and M. Mondin, "Unsaturated
Throughput Analysis of IEEE 802.11 in Presence of Non Ideal Transmission
Channel and Capture Effects," IEEE Transactions on Wireless
Communications, vol. 7, pp. 1276-1286, April 2008.

G Bianchi, "Performance Analysis of the IEEE 802.11 Distributed
Coordination Function," IEEE Journal on Selected Areas in Communications,
vol. 18, pp. 535-547, March 2000.

O. Tickoo and B. Sikdar, "A queueing model for finite load IEEE 802.11
random access MAC," in IEEE International Conference of Communication
(ICC), 2004, pp. 175-179.

R. B. Cooper, Introduction to Queueing Theory, Third ed.: CEE Press Books,
1990.

D. Bertsekas and R. Gallager, Data Networks, Second ed.: Prentice-Hall
1992.

E. W. Justh and P. S. Krishnamrasad, "A simple control law for UAV
formation flying, " Institute for System Research Technical Report 2002.

Y. U. Cao, A. S. Fukunaga, and A. kahng, "Cooperative mobile robotics:
Antecedents and directions," Automation Robots, March 1997.

N. Shimoyama, K. Sugawara, T. Mizuguchi, Y. Hayakawa, and M. Sano,
"Collective motion in a system of motile elements," Physical Review Letters,
1996.

B. T. Ludington, L.tang, and G. J. Vachtsevanos, "Target tracking in an urban
warfare environment using particle filters," in Aerospace, 2005 IEEE
Conference, 2005.

S. Biswas, S. Gupta, F. Yu, and T. Wu, "Collaborative Multi-target Tracking
Using Networked Micro-robotic Vehicles," in SPIE Defense Transformation
and Net-Centric Systems 2007, Orlando FL, USA, May 2007.

A. Jadbabaie, J. Lin, and A. S. Morse, "Coordination of groups of mobile
autonomous agents using nearest neighbor rules," IEEE Transation on
Automation Control, 2003.

L. Moreau, "Staility of multiagent systems with time-dependent
communication links," IEEE Transation on Automatic Control, 2005.

W. Xi, X. Tan, and J. S. Baras, "Gibbs’ sarnpler-based coordination of
autonomous swarms," Antomatica, 2006.

209

[102]

[103]

[104]

[105]

[106]

[107]

[108]

R. Olfati-Saber, "F locking for multi-agent dynamic systems: algorithms and
theory," IEEE. Transaction On Automatic Control,, March 2006.

R. O. Saber and R. M. Murray, "Consensus Protocols for dynamic agent
networks," in American Control Conference, 2003.

A. Savvides, C.-C. Han, and M. Srivastava, "Dynamic Fine-Grained
Localization in Ad-Hoc Networks of Sensors," in 7th ACM MobiCom, July
2001.

A. V. Savkin, "Coordinated collective motion of groups of autonomous
mobile robots: analysis of Vlcsek’s model," IEEE transactions on Automatic
Control, June 2004.

T. Vlcsek, A. Czirok, E. B. Jacob, 1. Cohen, and O. Schochet, "Novel type of
phase transitions in a system of self-driven particles," Physical Review
Letters, 1995.

A. Jadbabaie, N. Motee, and M. Barahona, "On the stability of the Kuramoto
model of coupled nonlinear oscillators," in American Control Conference,
2004.

E. W. Justh and P. S. Krishnamrasad, "Equilibria and steering laws for planar
formations," in the 42nd IEEE conference On Decision and Control 2003.

210

      

MIC

11111111111111[illiiijliljliiii’