Data Communication in Wireless Sensor Networks with Short Labels

Abstract Broadcast, Convergecast, and Data Aggregation are the three most used communication primitives in Wireless Sensor Networks (WSNs). Due to collisions, without labels, these communication tasks cannot be done deterministically, even in a four-cycle network. In this paper, we study the deterministic distributed broadcast, convergecast, and data aggregation algorithms enhanced with labeling schemes for WSNs in environments where collisions are present. For the convergecast algorithm, our labeling scheme uses at most O(log Δ) number of bits where Δ is the maximum node degree, which is better than previous approaches which use at least O(log n) amount of storage, where n is the number of nodes in the network. For broadcast algorithms in geometric graphs under the radio network or the SINR collision model, our labeling schemes use at most a constant number of bits. Based on the broadcast algorithms, we design data aggregation algorithms for geometric graphs under these collision models whose label sizes are at most O(log Δ). Our convergecast and broadcast algorithms are not only asymptotically space-optimal in terms of label sizes but also match the asymptotic runtime lower bounds to achieve these data communication primitives when nodes in the networks have unique IDs of size O(log n) and/or coordinate information. Finally, our data aggregation algorithms match the best runtime upper bounds when nodes are assumed to know a much larger amount of information than a label of size O(log Δ).