Interference-Free Scheduling with Minimum Latency in Cluster-Based Wireless Sensor Networks
Abstract
This article addresses wireless sensor networks (WSN) whose nodes are organized in groups (i.e., clusters) and follow a duty-cycle. Each cluster is locally managed by a cluster head which employs a medium access control protocol to avoid interferences in all intra-cluster communications. Nevertheless, inter-cluster interferences can still occur. To this regard, we consider two clusters as interfering if their hop distance is at most t, with t ≥ 2, in the cluster connectivity graph. Under such a model, we target convergecast data collection of aggregated traffic and show that finding a minimum-latency interference-free convergecast schedule up to distance t is NP-hard for cluster-based WSNs with arbitrary topologies. Due to the hardness result, we restrict our attention to cluster-tree WSNs which can model ad hoc WSN deployments. We optimally solve the problem on trees for t = 2 by minimizing both the latency and the schedule length. Then, for any t ≥ 2, we propose a minimum-latency interference-free algorithm that obtains a slot assignment with guaranteed approximated latency in O(nt) time, where n is the number of clusters in the WSN. We also discuss a distributed implementation of such a scheduling algorithm that results in an exchange of O(nt) messages. Moreover, we consider a minimum-latency data collection in complete trees of arbitrary degree as a special case. We finally validate our findings by a simulation study on synthetic tree topologies.
Recommended Citation
A. Navarra et al., "Interference-Free Scheduling with Minimum Latency in Cluster-Based Wireless Sensor Networks," Wireless Networks, vol. 21, no. 7, pp. 2395 - 2411, Kluwer Academic Publishers, Oct 2015.
The definitive version is available at https://doi.org/10.1007/s11276-015-0925-0
Department(s)
Computer Science
Keywords and Phrases
Access control; Aggregates; Data acquisition; Hardness; Medium access control; Scheduling; Scheduling algorithms; Sensor nodes; Topology; Trees (mathematics); Convergecast; Intercluster communication; Interference-free; NP-hardness; Trees; Wireless sensor networks; Inter-cluster communication; Interference-free scheduling; Minimum-latency aggregated convergecast
International Standard Serial Number (ISSN)
1022-0038; 1572-8196
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2015 Kluwer Academic Publishers, All rights reserved.
Publication Date
01 Oct 2015
Comments
This work has been partially supported by the US National Science Foundation (NSF) under grant CNS-1049652, by the Academy of Finland under Grant No. 284806, and by the Italian Ministry of University and Research under Grant 2010N5 K7EB-PRIN 2010 ARS TechnoMedia (Algoritmica per le Reti Sociali Tecno-mediate). Any opinions, findings and conclusions or recommendations expressed in this article are those of the authors and do not necessarily reflect the views of the NSF.