Least-Latency Routing over Time-Dependent Wireless Sensor Networks

Abstract
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 FIFO property, which makes the time-dependent Bellman-Ford problem solvable in polynomial-time. Using the -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 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 sub-optimal 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.

Comments are closed.