| Summary: | Wakeup scheduling has been widely used in wireless sensor networks (WSNs), for it can reduce the energy wastage caused by the idle listening state. In a traditional wakeup scheduling, sensor nodes start up numerous times in a period, thus consuming extra energy due to state transitions (e.g., from the sleep state to the active state). In this paper, we address a novel interference-free wakeup scheduling problem called compact wakeup scheduling, in which a node needs to wake up only once to communicate bidirectionally with all its neighbors. However, not all communication graphs have valid compact wakeup schedulings, and it is NP-complete to decide whether a valid compact wakeup scheduling exists for an arbitrary graph. In particular, tree and grid topologies, which are commonly used in WSNs, have valid compact wakeup schedulings. We propose polynomial-time algorithms using the optimum number of time slots in a period for trees and grid graphs. Simulations further validate our theoretical results.
|
|---|