Let the tree Bloom: scalable opportunistic routing with ORPL

ABSTRACT

Routing in battery-operated wireless networks is challenging, posing a tradeoff between energy and latency. Previous work has shown that opportunistic routing can achieve low-latency data collection in duty-cycled networks. However, applications are now considered where nodes are not only periodic data sources, but rather addressable end points generating traffic with arbitrary patterns.

We present ORPL, an opportunistic routing protocol that supports any-to-any, on-demand traffic. ORPL builds upon RPL, the standard protocol for low-power IPv6 networks. By combining RPL's tree-like topology with opportunistic routing, ORPL forwards data to any destination based on the mere knowledge of the nodes' sub-tree. We use bitmaps and Bloom filters to represent and propagate this information in a space-efficient way, making ORPL scale to large networks of addressable nodes. Our results in a 135-node testbed show that ORPL outperforms a number of state-of-the-art solutions including RPL and CTP, conciliating a sub-second latency and a sub-percent duty cycle. ORPL also increases robustness and scalability, addressing the whole network reliably through a 64-byte Bloom filter, where RPL needs kilobytes of routing tables for the same task.

References

1. F. Ashraf, N. H. Vaidya, and R. Kravets. Any-MAC: Extending any Asynchronous MAC with Anycast to Improve Delay in WSN. In Proceedings of the Conference on Sensor, Mesh and Ad Hoc Communications and Networks (IEEE SECON), 2011.
2. F. Ashref, R. H. Kravets, and N. H. Vaidya. Exploiting Routing Redundancy using MAC Layer Anycast to Improve Delay in WSN. SIGMOBILE Mob. Comput. Commun. Rev., 14, 2010.
3. P. Basu and C.-K. Chau. Opportunistic Forwarding in Wireless Networks with Duty Cycling. In Proceedings of the Workshop on Challenged Networks (ACM CHANTS), 2008.
4. S. Biswas and R. Morris. ExOR: Opportunistic Multi-Hop Routing for Wireless Networks. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (ACM SIGCOMM), 2005.
5. B. H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM, 13(7):422--426, July 1970.
6. F. Bonomi, M. Mitzenmacher, R. Panigrah, S. Singh, and G. Varghese. Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (ACM SIGCOMM), 2006.
7. A. Broder and M. Mitzenmacher. Network Applications of Bloom Filters: A Survey. In Internet Mathematics, pages 636--646, 2002.
8. N. Burri, P. V. Rickenbach, and R. Wattenhofer. Dozer: Ultra-Low Power Data Gathering in Sensor Networks. In Proceedings of the Conference on Information Processing in Sensor Networks (ACM/IEEE IPSN), 2007.
9. S. Chachulski, M. Jennings, S. Katti, and D. Katabi. Trading Structure for Randomness in Wireless Opportunistic Routing. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (ACM SIGCOMM), 2007.
10. D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris. A High-Throughput Path Metric for Multi-Hop Wireless Routing. Wirel. Netw., 11(4):419--434, July 2005.
11. M. Doddavenkatappa, M. C. Chan, and A. Ananda. Indriya: A Low-Cost, 3D Wireless Sensor Network Testbed. In Proceedings of the Conference on Testbeds and Research Infrastructures for the Development of Networks & Communities (TridentCom), 2011.
12. H. Dubois-Ferriè andre, M. Grossglauser, and M. Vetterli. Valuable Detours: Least-Cost Anypath Routing. IEEE/ACM Trans. Netw., 19(2), 2011.
13. A. Dunkels. The ContikiMAC Radio Duty Cycling Protocol. Technical Report T2011:13, Swedish Institute of Computer Science, 2011.
14. A. Dunkels, B. Gronvall, and T. Voigt. Contiki - A Lightweight and Flexible Operating System for Tiny Networked Sensors. In Proceedings of the Conference on Local Computer Networks (IEEE LCN), 2004.
15. A. Dunkels, F. Österlind, N. Tsiftes, and Z. He. Software-based On-line Energy Estimation for Sensor Nodes. In Proceedings of the Workshop on Embedded Networked Sensor Systems (IEEE Emnets), 2007.
16. S. Duquennoy, F. Österlind, and A. Dunkels. Lossy Links, Low Power, High Throughput. In Proceedings of the Conference on Embedded Networked Sensor Systems (ACM SenSys), 2011.
17. P. Dutta, S. Dawson-Haggerty, Y. Chen, C.-J. M. Liang, and A. Terzis. Design and Evaluation of a Versatile and Efficient Receiver-Initiated Link Layer for Low-Power Wireless. In Proceedings of the Conference on Embedded Networked Sensor Systems (ACM SenSys), 2010.
18. F. Ferrari, M. Zimmerling, L. Mottola, and L. Thiele. Low-Power Wireless Bus. In Proceedings of the Conference on Embedded Networked Sensor Systems (ACM SenSys), 2012.
19. F. Ferrari, M. Zimmerling, L. Thiele, and O. Saukh. Efficient Network Flooding and Time Synchronization with Glossy. In Proceedings of the Conference on Information Processing in Sensor Networks (ACM/IEEE IPSN), 2011.
20. J. Flathagen, E. Larsen, P. Engelstad, and O. Kure. O-CTP: Hybrid Opportunistic Collection Tree Protocol for Wireless Sensor Networks. In Proceedings of the Workshop on Practical Issues in Building Sensor Network Applications (IEEE SenseApp), 2012.
21. O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis. Collection Tree Protocol. In Proceedings of the Conference on Embedded Networked Sensor Systems (ACM SenSys), 2009.
22. Z. Heszberger, J. Tapolcai, A. Gulyas, J. Biro, A. Zahemszky, and P.-H. Ho. Adaptive Bloom Filters for Multicast Addressing. In Proceedings of the Workshop on High-Speed Networks (IEEE HSN), 2011.
23. JP. Vasseur and J. Hui and S. Dasgupta and G. Yoon. RPL Deployment Experience in Large Scale Networks. IETF draft-hui-vasseur-roll-rpl-deployment-01, WiP.
24. J. Kim, X. Lin, and N. B. Shroff. Optimal Anycast Technique for Delay-Sensitive Energy-Constrained Asynchronous Sensor Networks. IEEE/ACM Trans. Netw., 19(2):484--497, Apr. 2011.
25. M. Kovatsch, S. Duquennoy, and A. Dunkels. A Low-Power CoAP for Contiki. In Proceedings of the Workshop on Internet of Things Technology and Architectures (IEEE IoTech), 2011.
26. O. Landsiedel, E. Ghadimi, S. Duquennoy, and M. Johansson. Low Power, Low Delay: Opportunistic Routing meets Duty Cycling. In Proceedings of the Conference on Information Processing in Sensor Networks (ACM/IEEE IPSN), 2012.
27. P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks. In Proceedings of the Symposium on Networked Systems Design & Implementation (USENIX NSDI), 2004.
28. S. Liu, K.-W. Fan, and P. Sinha. CMAC: An Energy-Efficient MAC Layer Protocol using Convergent Packet Forwarding for Wireless Sensor Networks. ACM Trans. on Senor Networks, 5, 2009.
29. X. Mao, X.-Y. Li, W.-Z. Song, P. Xu, and K. Moaveni-Nejad. Energy Efficient Opportunistic Routing in Wireless Networks. In Proceedings of the Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (ACM MSWiM), 2009.
30. D. Moss and P. Levis. BoX-MACs: Exploiting Physical and Link Layer Boundaries in Low-Power Networking. Technical Report SING-08-00, Stanford, 2008.
31. V. Paruchuri, S. Basavaraju, A. Durresi, R. Kannan, and S. S. Iyengar. Random Asynchronous Wakeup Protocol for Sensor Networks. In Proceedings of the Conference on Broadband Communications, Networks, and Systems (IEEE BROADNETS), 2004.
32. B. Pavković, F. Theoleyre, and A. Duda. Multipath Opportunistic RPL Routing over IEEE 802.15.4. In Proceedings of the Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (ACM MSWiM), 2011.
33. M. V. Ramakrishna and J. Zobel. Performance in Practice of String Hashing Functions. In Proceedings of the Conference on Database Systems for Advanced Applications (DASFAA), 1997.
34. A. Reinhardt, O. Morar, S. Santini, S. Zöller, and R. Steinmetz. CBFR: Bloom Filter Routing with Gradual Forgetting for Tree-structured Wireless Sensor Networks with Mobile Nodes. In Proceedings of the Symposium on a World of Wireless Mobile and Multimedia Networks (IEEE WoWMoM), 2012.
35. G. Schaefer, F. Ingelrest, and M. Vetterli. Potentials of Opportunistic Routing in Energy-Constrained Wireless Sensor Networks. In Proceedings of the European Conference on Wireless Sensor Networks (EWSN), 2009.
36. K. Srinivasan, M. Jain, J. I. Choi, T. Azim, E. S. Kim, P. Levis, and B. Krishnamachari. The κ Factor: Inferring Protocol Performance using Inter-Link Reception Correlation. In Proceedings of the Conference on Mobile Computing and Networking (ACM MobiCom), 2010.
37. K. Srinivasan, M. A. Kazandjieva, S. Agarwal, and P. Levis. The β Factor: Measuring Wireless Link Burstiness. In Proceedings of the Conference on Embedded Networked Sensor Systems (ACM SenSys), 2008.
38. S. Unterschütz, C. Renner, and V. Turau. Opportunistic, Receiver-Initiated Data-Collection Protocol. In Proceedings of the European Conference on Wireless Sensor Networks (EWSN), 2012.
39. T. Winter (Ed.), P. Thubert (Ed.), and RPL Author Team. RPL: IPv6 Routing Protocol for Low power and Lossy Networks, Mar. 2012. RFC 6550.
40. M. Zorzi and R. R. Rao. Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Energy and Latency Performance. IEEE Trans. on Mobile Computing, 2(4):349--348, 2003.

Index Terms

• Networks

  • Network architectures

  • Network protocols