Luận án tiến sĩ: Wireless MAC layer flexibility for extending effective system lifetime

WIRELESS MAC LAYER FLEXIBILITY FOR EXTENDING EFFECTIVE SYSTEM LIFETIME by Rebecca Lynn Braynard Silberstein Department of Computer Science Duke University Date: Z2 HOY, Zccé A pproved: LL LL IE LE Dr. Carla Schlatter Ellis, Supervisor Zee “ “Dr. J Piel we tol Dr. Maria Papadopouli Dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Computer Science in the Graduate School of Duke University 2006 UMI Number: 3244842 Copyright 2006 by Silberstein, Rebecca Lynn Braynard All rights reserved.

INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.

® UMI UMI Microform 3244842 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 Copyright © 2006 by Rebecca Lynn Braynard Silberstein All rights reserved ABSTRACT (Computer Science) WIRELESS MAC LAYER FLEXIBILITY FOR EXTENDING EFFECTIVE SYSTEM LIFETIME by Rebecca Lynn Braynard Silberstein Department of Computer Science Duke University Date: ZLorel 4, ZOOE “Approved: Dr. Carla Schlatter Ellis, Supervisor Dr. Maria Papadopouli An abstract of a dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Computer Science in the Graduate School of Duke University 2006 Abstract The scenario of wireless devices deployed in an ad hoc network is a compelling one. For the system to support its assigned tasks, nodes must cooperate to forward data packets through the network.

The act of forwarding, however, is directly linked to node lifetime. The more a node forwards data packets, the sooner it depletes its bat- tery through use of its high energy-consuming radio. Once forwarding nodes deplete their batteries, the network may partition and fail to provide its designated services. To reduce the burden on nodes maintaining network connectivity, we propose to bal- ance energy consumption among all participating networked nodes, so they all fail at approximately the same time.

We do this through our Medium Access Control (MAC) layer protocol, SEESAW, which offloads communication control overhead from heavily loaded nodes to more lightly loaded neighbors. SEESAW’s unique combina- tion of asynchrony, asymmetry and batching allow probabilistic communication with reliable delivery, while both reducing and balancing energy consumption. We present SEESAW and an accompanying online, distributed, self-tuning algo- rithm. We evaluate SEESAW through simulation using our detailed energy modeling simulator, SENSIM, and implementation on Mica2 Motes in TinyOS.

Our results show SEESAW is competitive in terms of energy consumption and delivery performance with related protocols, despite additional overhead needed for an asynchronous and asym- metric protocol. Additionally, we show SEESAW successfully balances consumption among networked nodes while providing acceptable delivery performance with static random topologies and static, random, and bursty application workloads. iv Acknowledgements Without the support of family and friends, completing this thesis would not have been possible. I would especially like to thank my parents, Jerry and Gerry Braynard, who help with everything I try to do in whatever way they can.

My husband, Adam Silberstein, who is not only my best friend but also happens to be a wonderful collaborator, has helped every way possible. Carla Ellis, thank you for guiding me with this project and all of your help, whether or not it was related to this thesis. Thank you Dr. Alvy Lebeck, Dr.

Jun Yang and Dr. Maria Papadopouli, your help with research and graduate school advice made it possible for me to finish. Diane Riggs, thank you for your guidance through every step along the way and all the reminders to make sure I could actually graduate. I also could not miss the chance to thank Adolfo Rodriguez, Steve Kacsmark, Andrea Klostermann, Richenda Petersen and Billy and Alexa Corbett who all provide encouragement, help and a good laugh whenever needed.

Contents Abstract iv Acknowledgements List of Tables List of Figures 1 Introduction 1.1 Balancing Energy Consumption .2 Wireles and Ad Hoc Network Challengs .23 Radio Range and Link Asymmetry .3 Preview of Contributions. ee 2 Background and Related Work 11 2.1 Energy Savings in Wireless Protocols. Ha HH Ha. ä 12 22 Utiizing Radio States.

eee ee ee 14 2. HQ HH vs 3.000 eee eee eee 3.3 Decoupled Sending and Receiving. an na ee 3. ee ee SenSim: Simulating Ad Hoc Sensor Networks 41 Design.

TH Evaluating Static Seesaw 5.1 Asymmetry and Asynchrony Overhead. eee ee ee 5.3 Batch Size: Bo. ee 5 an ốc. Q Q LH ke kg ky 5.

kg kg k kia 5. ch nu kg và kia Evaluating Autotuning Seesaw with Random Topologies 76 6. cuc Q Q LH vn va 76 6.2 Constant Bit Rates.3 Changing Data Rates.1 Random Data Rates. ee 88 Seesaw in TinyOS on Mica2 Motes 91 7.2 Comparison of TinyOS Implementation and Simulation Results 92 7.3 Impact of Clock Instability.4 Nature of Clock Instability on Motes.

- c c Q es A Objective Function Variable Derivations 104 B Random Test Topology Set 106 C Individual Test Data Tables 108 C.1 Constant Bit Rate (CBR) Experiments .2 Changing Data Rate (CDR) Experimens.3 Hot Spot Burst (HSB) Experiments ee eee ee ee ee we tl lt 113 Bibliography 115 Biography 120 ix List of Tables 1.1 Power values for Mica2 Motes [42, 43, 28] used in analysis and simula- tion. For transition times, we use the approximation utilized by Jung and Vaidya [15], 800useconds and 2*IDLE power [11, 32].1 Objective function notation 2.2 Sample neighbor parameter tables for the 4 nodes in the topology of Figure 3. HQ HH HQ gà gi gà kg va ky 39 3.3 Node settings after processing the neighbor table entries (action booleans include percent diference when set to True).4 Node settings after processing action booleans and accounting for the local power consumption trend. ee ee Al 3.5 Final node parameter values after tuning.6 Đervice level checks after tuning.1 SEESAW parameter settings for both sets of parameter comparison tests.

In the base tests, batching is disabled and the enhanced version, batching is enabled with node B settings shown above.2 Baseline settings for parameter influence experiments .3 SEESAW parameter settings for batch size influence experiments .4 Cross topology parameter values for the three scenarios, Symmetric, Elected Forwarder and Balanced.5 CPLEX a, / values for 3 datarates 2.6 Packets delivered and average delay for SENSIM tests using offline determined parameter settings.7 Node parameter settings after 50000 seconds of simulation without (left) and with (right) batch size tuning enabled.1 Parameter settings for interval skew tests.1 Variables used in detailed definitions of the components of the model introduced in Table3.00 eee ees 104 C1 8 Nodes CBR: 1 packet per 2seconds. 108 C2 8Nodes CBR: 1 packet per 4seconds.3 8 Nodes CBR: 1 packet per 8seconds.4 20 Nodes CBR: 1 packet per 8seconds. 1 packet per l6 seconds.6 CDR: rate change every 60-120 seconds.7 CDR: rate change every 120-240 seconds .8 CDR: rate change every 1000-2000 seconds.9 HSB: about 120 seconds between hot spots.10 HSB: about 240 seconds between hot spots.11 HSB: about 480 seconds between hot spots.0, 114 xi List of Figures 1.1 Offloading protocol overhead from highly loaded nodes to lightly loaded neighbors can increase system lifetime.2 With a shared medium and limited transmission ranges, nodes may not detect active transmissions and inadvertently cause collisions.1 To avoid collisions, nodes exchange RTS and CTS packets to estab- lish communication and follow Data packets with acknowledgments Z9.2 S-MAC nodes participating in multiple virtual clusters take on multi- ple scehedules. QC QC Q Q Q ng.1 Nodes listen for a percent (/) of each interval for incoming transmis- SIONS 2.2 Nodes send a evenly spaced Ads each interval when they have data packets ready tO §end,.

ng c HQ Q Q vn và v va 23 3.3 Nodes use the same interval length, but the intervals can start at different times. Interval counts are depicted by dintervalNum - - - - -- 24 3.4 Ad packet components .5 Accept (establish communication) packet components .6 Data packet header components .7 Ack packet component§S.8 Decoupling sending and listening allows nodes to build asymmetric sehedules. QC Q Q Q Q H H n Q v v v2 và va 28 3.9 Two interval segment of time for each of two unsynchronized nodes.10 Simple three node topology with a source generating data, a forwarder passing data along the path and a destination acting as the data packet Sink, es 33 3.11 State information from a portion of a SEESAW simulation run.12 Simple four node topology with nodes 1, 2 and 3 producing data pack- ets for the sink, node 0. To maintain connectivity, node 1 forwards packets to node 0 for nodes 2 and Ä.13 Online tuning algorithim.

Q Q vu ng gà kg và KV 4.2 SENSIM provides three layers for implementing functionality, applica- tion, routing and medium access. The Channel provides communica- 01950052042.AgdAaAÁAIA aTn.3 Reproduced energy consumption results from S-MAC [43].4 Validation of our simulator results for S-MAC and B-MAC against published results from S-MAC [43] and B-MAC [25),. HQ Hà gà g kg kg 5.2 Base: Total system energy .3 Base: Delivered packets ©. pee ee ee eee 5.4 Base: Energy per packet .5 Base: Avg packet latency.6 Better: Total system energy .7 Better: Delivered packets.8 Better: Energy per packet.

HQ HH kg va 5.9 Better: Avg packet delay. LH HQ và kia 5. LH ng vo ð.11 Varying Ads per intervalÌ, đ. cv c Q LH HQ và va 5.12 Varying listen time per interVaÌl,Ì.

cuc ee ee 5.13 Varying node batch size, .14 Varying the node interVal?. cu va ko 5.15 Using the cross traffic topology (”X” Topology), we compare three scenarios using hand-tuned SEESAW parameters.16 Node energy consumption for three data rates using CPLEX determined parameter settings.17 Total node consumption with static settings: a=12and/=0.18 Total node consumption using offline algorithm settings.19 Total node consumption with a and / tuning and static B.20 Total node consumption with a, / and B tuning enabled.1 Sample topology that is difficult to balance. Node 1 is forwarding for many nodes and node 7 simply does not need to, nor possibly can, consume enough to balance consumption with nodel.2 Sample box plot.3 Simple network where all sources can directly communicate with the sink, nodeQ.4 Simple network with maximum packet forwarding to the sink, node 0.5 Box plot for 8-node topologies with nodes generating a packet approx- imately every 2 seconds.6 Box plot for 8-node topologies with nodes generating a packet approx- imately every 4seconds. Q Q Q cv ga ai 6.7 Box plot for 8-node topologies with nodes generating a packet approx- imately every 8 seconds.8 Random 8-node topology 2.9 Random 8-node topology.

be eee eee ee 6.10 Box plot for 20 node topologies with nodes generating a packet ap- proximately every 8seconds. pee ee ee ns 6.11 Box plot for 20 node topologies with nodes generating a packet ap- proximately every 16 seconds. eee ee en 6.12 Box plot for 8 node topologies with nodes generating packets with random intervals for random durations.13 Box plot for 8 node topologies with nodes generating packets with random intervals for random durations.14 Box plot for 8 node topologies with nodes generating packets with random intervals for random durations.15 Box plot for 8 node topologies with 120 second hot spot bursts spaced approximately 120 seconds apart.16 Box plot for 8 node topologies with 120 second hot spot bursts spaced approximately 240 seconds apart.