Heat-Diffusion (HD) routing is our recently-developed queue-aware routing policy for multi-hop wireless networks inspired by Thermodynamics. In the prior theoretical studies, we have shown that HD routing guarantees throughput optimality, minimizes a quadratic routing cost, minimizes queue congestion on the network, and provides a trade-off between routing cost and queueing delay that is Pareto-Optimal. While striking, these guarantees are based on idealized assumptions (including global synchronization, centralized control, and infinite buffers) and heretofore have only been evaluated through simplified numerical simulations. We present here the first practical decentralized Heat-Diffusion Collection Protocol (HDCP) for wireless sensor networks and detail its implementation on Contiki OS. We present a thorough evaluation of HDCP based on real testbed experiments, including a comparative analysis of its performance with respect to the state of the art Collection Tree Protocol (CTP) and Backpressure Collection Protocol (BCP) for wireless sensor networks. We find that HDCP has a significantly higher throughput region and greater resilience to interference compared to CTP. However, we also find that the best performance of HDCP is comparable to the best performance of BCP, due to the similarity in their neighbor rankings, which we verify through a Kendall's-Tau test.
Besides the original Backpressure routing algorithm, other throughput optimal policies @cite_10 @cite_14 @cite_11 have also been proposed in the existing network theory literature. The HD algorithm also provides the same throughput optimality guarantee in theory. However, what motivated us to implement HD were the striking additional expected performance capabilities (based on our theoretical results)--- that it also offers a Pareto-optimal trade-off between routing cost and queue congestion.
@cite_14 @cite_10 @cite_11
2136954685 2086002250 2109679596 2078414674
This paper considers the problem of throughput optimal routing scheduling in a multi-hop constrained queueing network with random connectivity whose special cases include opportunistic multi-hop wireless networks and input-queued switch fabrics. The main challenge in the design of throughput optimal routing policies is closely related to identifying appropriate and universal Lyapunov functions with negative expected drift. The few well-known throughput optimal policies in the literature are constructed using simple quadratic or exponential Lyapunov functions of the queue backlogs and as such they seek to balance the queue backlogs across network independent of the topology. By considering a class of continuous, differentiable, and piece-wise quadratic Lyapunov functions, this paper provides a large class of throughput optimal routing policies. The proposed class of Lyapunov functions allow for the routing policy to control the traffic along short paths for a large portion of state-space while ensuring a negative expected drift. This structure enables the design of a large class of routing policies. In particular, and in addition to recovering the throughput optimality of the well-known backpressure routing policy, an opportunistic routing policy with congestion diversity is proved to be throughput optimal. We consider the problem of optimal scheduling and routing in an ad-hoc wireless network with multiple traffic streams and time varying channel reliability. Each packet transmission can be overheard by a subset of receiver nodes, with a transmission success probability that may vary from receiver to receiver and may also vary with time. We develop a simple backpressure routing algorithm that maximizes network throughput and expends an average power that can be pushed arbitrarily close to the minimum average power required for network stability, with a corresponding tradeoff in network delay. When channels are orthogonal, the algorithm can be implemented in a distributed manner using only local link error probability information, and supports a ''blind transmission'' mode (where error probabilities are not required) in special cases when the power metric is neglected and when there is only a single destination for all traffic streams. For networks with general inter-channel interference, we present a distributed algorithm with constant-factor optimality guarantees. There has been extensive work on network architectures that support multi-path routing to improve performance in wireless mesh networks. However, previous work uses ad-hoc design principles that cannot guarantee any network-wide performance objectives such as conjointly maximizing resource utilization and improving fairness. In parallel, numerous theoretical results have addressed the issue of optimizing a combined metric of network utilization and fairness using techniques based on back-pressure scheduling, routing and flow control. However, the proposed theoretical algorithms are extremely difficult to implement in practice, especially in the presence of the 802.11 MAC and TCP. We propose Horizon, a novel system design for multi-path forwarding in wireless meshes, based on the theoretical results on back-pressure. Our design works with an unmodified TCP stack and on top of the existing 802.11 MAC. We modified the back-pressure approach to obtain a simple 802.11-compatible packet-forwarding heuristic and a novel, light-weight path estimator, while maintaining global optimality properties. We propose a delayed reordering algorithm that eliminates TCP timeouts while keeping TCP packet reordering to a minimum. We have evaluated our implementation on a 22-node testbed. We have shown that Horizon effectively utilizes available resources (disjoint paths). In contrast to previous work, our design not only avoids bottlenecks but also optimally load-balances traffic across them when needed, improving fairness among competing flows. To our knowledge, Horizon is the first practical wireless system based on back-pressure. We study the half-duplex multiple-relay channel (HD-MRC) where every node can either transmit or listen but cannot do both at the same time. We obtain a capacity upper bound based on a max-flow min-cut argument and achievable transmission rates based on the decode-forward (DF) coding strategy, for both the discrete memoryless HD-MRC and the phase-fading HD-MRC. We discover that both the upper bound and the achievable rates are functions of the transmit listen state (a description of which nodes transmit and which receive). More precisely, they are functions of the time fraction of the different states, which we term a schedule. We formulate the optimal scheduling problem to find an optimal schedule that maximizes the DF rate. The optimal scheduling problem turns out to be a maximin optimization, for which we propose an algorithmic solution. We demonstrate our approach on a four-node multiple-relay channel, obtaining closed-form solutions in certain scenarios. Furthermore, we show that for the received signal-to-noise ratio degraded phase-fading HD-MRC, the optimal scheduling problem can be simplified to a max optimization.