Scott Moeller
ABSTRACT
Current data collection protocols for wireless sensor networks are mostly based on quasi-static minimum-cost routing trees. We 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 a considerable theoretical literature on backpressure routing, it has not been implemented on practical systems to date due to concerns about packet looping, the effect of link losses, large packet delays, and scalability. Addressing these concerns, 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 highly dynamic network settings, including conditions of extreme external interference and highly mobile sinks.
- Tutornet. http://enl.usc.edu/projects/tutornet/.Google Scholar
- U. Akyol, M. Andrews, P. Gupta, and J. Hobby. Joint scheduling and congestion control in mobile ad-hoc networks. IEEE INFOCOM, Jan 2008.Google ScholarCross Ref
- M. Bathula, M. Ramezanali, I. Pradhan, N. Patel, J. Gotschall, and N. Sridhar. A sensor network system for measuring traffic in short-term construction work zones. DCOSS, Jan 2009. Google ScholarDigital Library
- S. Biswas and R. Morris. Exor: opportunistic multi-hop routing for wireless networks. ACM SIGCOMM, Jan 2005. Google ScholarDigital Library
- L. Bui, R. Srikant, and A. Stolyar. Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. ACM Infocom mini-conference, 2008.Google Scholar
- J. Burke, D. Estrin, M. Hansen, and A. Parker. Participatory sensing. World Sensor Web Workshop, Jan 2006.Google Scholar
- J. I. Choi, M. A. Kazandjieva, M. Jain, and P. Levis. The case for a network protocol isolation layer. Sensys, Oct 2009.Google ScholarDigital Library
- J. I. Choi, J. W. Lee, M. Wachs, and P. Levis. Opening the sensornet black box. Proceedings of the International Workshop on Wireless Sensornet Architecture (WWSNA), Mar 2007.Google ScholarDigital Library
- D. Couto, D. Aguayo, B. Chambers, and R. Morris. Performance of multihop wireless networks: Shortest path is not enough. ACM SIGCOMM, Jan 2003. Google ScholarDigital Library
- L. Filipponi, S. Santini, and A. Vitaletti. Data collection in wireless sensor networks for noise pollution monitoring. DCOSS, Jan 2008. Google ScholarDigital Library
- R. Fonseca, O. Gnawali, K. Jamieson, and P. Levis. Four-bit wireless link estimation. HotNets, Oct 2007.Google Scholar
- D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly-resilient, energy-efficient multipath routing in wireless sensor networks. ACM SIGMOBILE, Jan 2001. Google ScholarDigital Library
- Y. Ganjali and N. McKeown. Routing in a highly dynamic topology. IEEE SECON, Jan 2005.Google ScholarCross Ref
- L. Georgiadis, M. Neely, M. Neely, and L. Tassiulas. Resource allocation and cross layer control in wireless networks. 2006. Google ScholarDigital Library
- O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis. Collection tree protocol. ACM Sensys, Apr 2009. Google ScholarDigital Library
- L. Huang and M. J. Neely. Delay reduction via lagrange multipliers in stochastic network optimization. WiOpt, Apr 2009. Google ScholarDigital Library
- A. Jayasumana, N. Piratla, T. Banka, A. Bare, and R. Whitner. Improved packet reordering metrics. IETF RFC 5236.Google Scholar
- L. Jiang and J. Walrand. A distributed csma algorithm for throughput and utility maximization in wireless networks. Proc. Allerton Conf. on Comm., Jan 2008.Google ScholarCross Ref
- S. Katti and H. Balakrishnan. Symbol-level network coding for wireless mesh networks. ACM SIGCOMM, 2008. Google ScholarDigital Library
- C. Li and M. Neely. Energy-optimal scheduling with dynamic channel acquisition in wireless downlinks. IEEE CDC, Jan 2007.Google Scholar
- J. Liu, A. Stolyar, M. Chiang, and H. Poor. Queue back-pressure random access in multi-hop wireless networks: Optimality and stability. IEEE Trans on Information Theory, Jan 2008. Google ScholarDigital Library
- M. Neely. Order optimal delay for opportunistic scheduling in multi-user wireless uplinks and downlinks. IEEE/ACM TON, Jan 2008. Google ScholarDigital Library
- M. Neely and R. Urgaonkar. Opportunism, backpressure, and stochastic optimization with the wireless broadcast advantage. IEEE SSC, Jan 2008.Google ScholarCross Ref
- M. J. Neely. Dynamic power allocation and routing for satellite and wireless networks with time varying channels. PhD Thesis, Massachusetts Institute of Technolog, 2003. Google ScholarDigital Library
- M. J. Neely. Super-fast delay tradeoffs for utility optimal fair scheduling in wireless networks. IEEE JSAC, Aug 2006. Google ScholarDigital Library
- M. J. Neely. Intelligent packet dropping for optimal energy-delay tradeoffs in wireless downlinks. IEEE TAC, Feb 2009.Google ScholarCross Ref
- M. J. Neely, E. Modiano, and C.-P. Li. Fairness and optimal stochastic control for heterogeneous networks. IEEE INFOCOM, Sep 2005.Google ScholarCross Ref
- J. Ni and R. Srikant. Q-csma: Queue-length based csma/ca algorithms for achieving maximum throughput and low delay in wireless networks. Proc. of Information Theory and Applications Workshop, Jan 2009.Google Scholar
- N. Piratla and A. Jayasumana. Reordering of packets due to multipath forwarding-an analysis. IEEE ICC, Jan 2006.Google ScholarCross Ref
- N. Piratla and A. Jayasumana. Metrics for packet reordering-a comparative analysis. International Journal of Communication Systems, Jan 2008. Google ScholarDigital Library
- D. Puccinelli and M. Haenggi. Reliable data delivery in large-scale low-power sensor networks. ACM TOSN, Sep 2009. Google ScholarDigital Library
- B. Radunovic, C. Gkantsidis, and D. Gunawardena. Horizon: Balancing tcp over multiple paths in wireless mesh network. ACM MOBICOM, Jan 2008. Google ScholarDigital Library
- T. Schoellhammer, B. Greenstein, and D. Estrin. Hyper: A routing protocol to support mobile users of sensor networks. Tech Report 2013, CENS, Oct 2006.Google Scholar
- A. Sridharan, S. Moeller, and B. Krishnamachari. Implementing backpressure-based rate control in wireless networks. ITA Workshop, Sep 2008.Google Scholar
- A. Sridharan, S. Moeller, and B. Krishnamachari. Making distributed rate control using lyapunov drifts a reality in wireless sensor networks. WiOpt, 2008.Google ScholarCross Ref
- A. Stolyar. Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm. Queueing Systems, Jan 2005. Google ScholarDigital Library
- L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and schedulingpolicies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 1992.Google Scholar
- M. Wachs, J. I. Choi, J. W. Lee, K. Srinivasan, Z. Chen, M. Jain, and P. Levis. Visibility: A new metric for protocol design. ACM Sensys, Sep 2007. Google ScholarDigital Library
- A. Warrier, S. Janakiraman, S. Ha, and I. Rhee. Diffq: Practical differential backlog congestion control for wireless networks. INFOCOM, Jan 2009.Google ScholarCross Ref
- A. Woo, T. Tong, and D. Culler. Taming the underlying challenges of reliable multihop routing in sensor networks. ACM Sensys, 2003. Google ScholarDigital Library
- W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor networks. IEEE INFOCOM, Jan 2002.Google Scholar
- L. Ying, S. Shakkottai, and A. Reddy. On combining shortest-path and back-pressure routing over multihop wireless networks. Proceedings of the IEEE INFOCOM, Jan 2009.Google ScholarCross Ref
Index Terms
- Routing without routes: the backpressure collection protocol
Recommendations
Self-selecting reliable paths for wireless sensor network routing
Routing protocols for wireless sensor networks face two challenges. One is an efficient bandwidth usage which requires minimum delay between transfers of packets. Establishing permanent routes from the source to destination addresses this challenge ...
Traffic-aware routing protocol for wireless sensor networks
In wireless sensor networks, when a sensor node detects events in the surrounding environment, the sensing period for learning detailed information is likely to be short. However, the short sensing cycle increases the data traffic of the sensor nodes in ...
Efficient and Balanced Routing in Energy-Constrained Wireless Sensor Networks for Data Collection
EWSN '16: Proceedings of the 2016 International Conference on Embedded Wireless Systems and NetworksCost-based routing protocols are the main approach used in practical wireless sensor network (WSN) deployments for data collection applications with energy constrains; however, those routing protocols lead to the concentration of most of the data ...
Comments