A Distributed Wake-Up Scheduling for Opportunistic Forwarding in Wireless Sensor Networks

In wireless sensor networks (WSNs), sensor nodes are typically subjected to energy constraints and often prone to topology changes. While duty cycling has been widely used for energy conservation in WSNs, random walks have been popular for many delay-tolerant applications in WSNs due to their many inherent desirable properties. In this paper, we consider an opportunistic forwarding under an asynchronous and heterogeneous duty cycling. We first show that its resulting packet trajectory can be interpreted as a continuous-time random walk, and then provide an analytical formula for its end-to-end delay. Since the extremely large end-to-end delay is still undesirable even for most delay-tolerant applications, we develop a distributed wake-up scheduling algorithm in which each node autonomously adjusts its (heterogeneous) wake-up rate based only on its own degree information so as to improve the worst-case end-to-end delay. In particular, we prove that our algorithm outperforms pure homogeneous duty cycling, where every node uses the same wake-up rate, in its guaranteed asymptotic upper bound of the worst-case delay for any graph. In addition, we show that our proposed algorithm brings out more than 35% performance improvement on average when compared with pure homogeneous duty cycling, under various settings of random geometric graphs via numerical evaluations and independent simulation results.