Journal
IEEE TRANSACTIONS ON COMPUTERS
Volume 62, Issue 5, Pages 969-983Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TC.2012.36
Keywords
Time dependent; shortest path; wireless sensor networks; routing; routing maintenance; least latency
Ask authors/readers for more resources
We consider the problem of least-latency end-to-end routing over adaptively duty-cycled wireless sensor networks. Such networks exhibit a time-dependent feature, where the link cost and transmission latency from one node to other nodes vary constantly in different discrete time moments. We model the problem as the time-dependent Bellman-Ford problem. We show that such networks satisfy the first-in-first-out (FIFO) property, which makes the time-dependent Bellman-Ford problem solvable in polynomial-time. Using the ss-synchronizer, we propose a fast distributed algorithm to construct all-to-one shortest paths with polynomial message complexity and time complexity. The algorithm determines the shortest paths for all discrete times in a single execution, in contrast with multiple executions needed by previous solutions. We further propose an efficient distributed algorithm for time-dependent shortest path (TDSP) maintenance. The proposed algorithm is loop-free with low message complexity and low space complexity of O(maxdeg), where maxdeg is the maximum degree for all nodes. We discuss a suboptimal implementation of our proposed algorithms that reduces their memory requirement. The performance of our algorithms are experimentally evaluated under diverse network configurations. The results reveal that our algorithms are more efficient than previous solutions in terms of message cost and space cost.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available