We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Interference-free scheduling with minimum latency in cluster-based wireless sensor networks.
- Authors
Navarra, Alfredo; Pinotti, Cristina; Francesco, Mario; Das, Sajal
- 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\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.
- Subjects
WIRELESS sensor networks; WIRELESS sensor nodes; COMPUTER workstation clusters; GRAPH connectivity; SPANNING trees; ALGORITHMS; SIMULATION methods &; models
- Publication
Wireless Networks (10220038), 2015, Vol 21, Issue 7, p2395
- ISSN
1022-0038
- Publication type
Article
- DOI
10.1007/s11276-015-0925-0