Dynamic routing and rate control in stochastic network optimization: from theory to practice

UnrestrictedReal-world applications of wireless sensor networks are frequently faced with network capacity constraints, restricting the sensing frequency or scalability of the deployment. In the absence of transport-layer rate control the allocation of network capacity can be highly asymmetric, favoring sensing nodes near the collection agent. Further, external interference and new participatory sensing paradigms can result in highly dynamic collection topologies. Lastly, protocols for the resource-constrained networks must emphasize low complexity while minimizing control overhead. Addressing these challenges, we present a novel backpressure-based routing and rate-control stack that is motivated by stochastic network optimization theory.; Current data collection protocols for wireless sensor networks are mostly based on quasi-static minimum-cost routing trees. We first consider an alternative, highly-agile approach called backpressure routing, in which routing and forwarding decisions are made on a per-packet basis. Although there is considerable theoretical literature on backpressure routing, it has not been previously implemented on practical systems due to concerns of packet looping, the effect of link losses, large packet delays, and scalability. We present the Backpressure Collection Protocol (BCP) for sensor networks, the first- ever implementation of dynamic backpressure routing in wireless networks. In particular, we demonstrate for the first time that replacing the traditional FIFO queue service in backpressure routing with LIFO queues reduces the average end-to-end packet delays for delivered packets drastically (75% under high load, 98% under low load). Further, we improve backpressure scalability by introducing a new concept of floating queues into the backpressure framework. Under static network settings, BCP shows a more than 60% improvement in max-min rate over the state of the art Collection Tree Protocol (CTP). We also empirically demonstrate the superior delivery performance of BCP in dynamic network settings, including conditions of extreme external interference and highly mobile sinks.; Backpressure-based stochastic network optimization theory employs a tunable optimization parameter, V . As V is increased, utility or penalty performance approaches the optimal like O( 1 ) while delay grows linearly in V . We provide analysis motivating V the novel usage of the LIFO queueing discipline in backpressure stacks, suggesting that delay scales near-optimally like O(log2(V )) for all but a small fraction of traffic. We then empirically evaluate delay and discard performance of BCP as the V parameter is raised, and find the results in strong agreement with theory.; Finally, we turn our attention to state of the art rate control protocols for wireless sensor networks, which are traditionally assumed to run atop the aforementioned quasi- static routing trees. We implement and empirically explore a backpressure rate controller, theoretically capable of maximizing an aggregate source utility function while the underlying backpressure routing framework dynamically routes packets, often amongst multi- ple paths, to the collection agent. We demonstrate an alpha-fair rate controller which achieves 95% of the empirically determined max-min fair rate allocation over a 20-mote deployment, and 80% of the max-min fair rate allocation over 40 motes