Duty-Cycled Wireless Sensor Networks: Wakeup Scheduling, Routing, and Broadcasting

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.