The extra-bit technique for reducing idle listening in data collection

摘要

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.