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 β-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.

We revisit the shortest path problem in asynchronous duty-cycled wireless sensor networks, which exhibit time-dependent features. We model the time-varying link cost and distance from each node to the sink as periodic functions. We show that the time-cost function satisfies the FIFO property, which makes the time-dependent shortest path problem solvable in polynomial-time. Using the ß-synchronizer, we propose a fast distributed algorithm to build all-to-one shortest paths with polynomial message complexity and time complexity. The algorithm determines the shortest paths for all discrete times with 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. The performance of our solution is evaluated under diverse network configurations. The results suggest that our algorithm is more efficient than previous solutions in terms of message complexity and space complexity.

We present heterogenous quorum-based asynchronous wake-up scheduling schemes for wireless sensor networks. The schemes can ensure that two nodes that adopt different quorum systems as their wake-up schedules can hear each other at least once in bounded time intervals. We propose two such schemes: cyclic quorum system pair (cqs-pair) and grid quorum system pair (gqs-pair). The cqs-pair which contains two cyclic quorum systems provides an optimal solution, in terms of energy saving ratio, for asynchronous wake-up scheduling. To quickly assemble a cqs-pair, we present a fast construction scheme which is based on the multiplier theorem and the (N,k,M, l)-difference pair defined by us. Regarding the gqs-pair, we prove that any two grid quorum systems will automatically form a gqs-pair. We further analyze the performance of both designs, in terms of average discovery delay, quorum ratio, and energy saving ratio. We show that our designs achieve better trade-off between the average discovery delay and quorum ratio (and thus energy consumption) for different cycle lengths. We implemented the proposed designs in a wireless sensor network platform of Telosb motes. Our implementation-based measurements further validate the analytically-established performance trade-off of our designs.

We consider the rate allocation problem for data aggregation in wireless sensor networks with two objectives: 1) maximizing the lifetime of a local aggregation cluster and 2) achieving fairness among all data sources. The two objectives are generally correlated with each other and usually they cannot be maximized simultaneously. We adopt a lexicographic method to solve this multi-objective programming problem. First, we recursively induce the maximum lifetime for the local aggregation cluster. Under the given maximum lifetime, we then formulate the problem of maximizing fairness as a convex optimization problem, and derive the optimal rate allocation strategy. We also present low-complexity algorithms that a local aggregation cluster can use to determine the optimal rate allocation. Our simulation results validate our analytical results and illustrate the effectiveness of the approach.