Interference-Free Scheduling with Minimum Latency in Cluster-Based Wireless Sensor Networks


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.


Computer Science


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.

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


File Type





© 2015 Kluwer Academic Publishers, All rights reserved.

Publication Date

01 Oct 2015