Title page for ETD etd-04262010-160152


Type of Document Dissertation
Author Lai, Shouwen
Author's Email Address swlai@vt.edu
URN etd-04262010-160152
Title Duty-Cycled Wireless Sensor Networks: Wakeup Scheduling, Routing, and Broadcasting
Degree PhD
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
Ravindran, Binoy Committee Chair
Hou, Yiwei Thomas Committee Member
Plassmann, Paul E. Committee Member
Vullikanti, Anil Kumar S. Committee Member
Yang, Yaling Committee Member
Keywords
  • Wireless Sensor Network
  • Duty Cycle
  • MAC
  • Routing
  • Broadcast
  • Quorum System
Date of Defense 2010-04-26
Availability unrestricted
Abstract
In order to save energy consumption in idle states, low duty-cycled operation is widely used in Wireless Sensor Networks (WSNs), where each node periodically switches between sleeping mode and awake mode. Although efficient toward saving energy, duty-cycling causes many challenges, such as difficulty in neighbor discovery due to asynchronous wakeup/sleep scheduling, time-varying transmission latencies due to varying neighbor discovery latencies, and difficulty on multihop broadcasting due to non-simultaneous wakeup in neighborhood. This dissertation focuses on this problem space. Specifically, we focus on three co-related problems in duty-cycled WSNs: wakeup scheduling, routing and broadcasting.

We propose an asynchronous quorum-based wakeup scheduling scheme, which optimizes heterogenous energy saving ratio and achieves bounded neighbor discovery latency, without requiring time synchronization. Our solution is based on quorum system design. We propose two designs: cyclic quorum system pair (cqs-pair) and grid quorum system pair (gqs-pair). We also present fast offline construction algorithms for such designs. Our analytical and experimental results show that cqs-pair and gqs-pair achieve better trade-off between the average discovery delay and energy consumption ratio. We also study asymmetric quorum-based wakeup scheduling for two-tiered network topologies for further improving energy efficiency.

Heterogenous duty-cycling causes transmission latencies to be time-varying. Hence, the routing problem becomes more complex when the time domain must be considered for data delivery in duty-cycled WSNs. We formulate the routing problem as time-dependent Bellman-Ford problem, and use vector representation for time-varying link costs and end-to-end (E2E) distances. We present efficient algorithms for route construction and maintenance, which have bounded time and message complexities in the worst case by ameliorating with beta-synchronizer.

Multihop broadcast is complex in duty-cycled WSNs due to non simultaneous wakeup in neighborhoods. We present Hybrid-cast, an asynchronous multihop broadcast protocol, which can be applied to low duty-cycling or quorum-based duty-cycling schedules, where nodes send out a beacon message at the beginning of wakeup slots. Hybrid-cast achieves better tradeoff between broadcast latency and broadcast count compared to previous broadcast solutions. It adopts opportunistic data delivery in order to reduce the broadcast latency. Meanwhile, it reduces redundant transmission via delivery deferring and online forwarder selection. We analytically establish the upper bound of broadcast count and the broadcast latency under Hybrid-cast.

To verify the feasibility, effectiveness, and performance of our solutions for asynchronous wakeup scheduling, we developed a prototype implementation using Telosb and TinyOS 2.0 WSN platforms. We integrated our algorithms with the existing protocol stack in TinyOS, and compared them with the CSMA mechanism. Our implementation measurements illustrate the feasibility, performance trade-off, and effectiveness of the proposed solutions for low duty-cycled WSNs.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Lai_Shouwen_D_2010.pdf 1.26 Mb 00:05:51 00:03:00 00:02:38 00:01:19 00:00:06

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.