The extra-bit technique for reducing idle listening in data collection. (2017) - Rasul, Aram; Erlebach, Thomas
Data collection is one of the predominant operations in wireless sensor networks (WSNs). This paper focuses on the problem of efficient data collection in a setting where some nodes may not possess data each time data is collected. In that case, idle listening slots may occur, which lead to a waste of energy and an increase in latency. To alleviate these problems, successive-slot schedules were proposed by Zhao and Tang (Infocom 2011). In this paper, we introduce a so-called extra-bit technique to reduce idle listening further. Each packet includes an extra bit that informs the receiver whether further data packets will follow or not. The extra-bit technique leads to significantly reduced idle listening and improved latency in many cases. We prove that every successive-slot schedule is also an extra-bit schedule. We then consider the special case of linear networks and prove that the optimal length of a successive-slot schedule (or extra-bit schedule) is 4N - 6 time slots, where N ≥ 3 is the number of nodes excluding the sink. Furthermore, we determine the optimal schedule length for balanced multi-chains. We then consider the setting where two frequencies (channels) can be used for transmission and determine the optimal schedule length for chains and balanced multi-chains in that case as well. Finally, the proposed extra-bit technique is compared with the successive-slot technique with respect to the expected amount of idle listening, and it is shown that the extra-bit technique reduces idle listening substantially.