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\ge 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 \ge 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.