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.
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
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)
Article - Journal
© 2015 Kluwer Academic Publishers, All rights reserved.
01 Oct 2015