Kaisen Lin
ABSTRACT
We present DIP, a data discovery and dissemination protocol for wireless networks. Prior approaches, such as Trickle or SPIN, have overheads that scale linearly with the number of data items. For T items, DIP can identify new items with O(log(T)) packets while maintaining a O(1) detection latency. To achieve this performance in a wide spectrum of network configurations, DIP uses a hybrid approach of randomized scanning and tree-based directed searches. By dynamically selecting which of the two algorithms to use, DIP outperforms both in terms of transmissions and speed. Simulation and testbed experiments show that DIP sends 20-60% fewer packets than existing protocols and can be 200% faster, while only requiring O(log(log(T))) additional state per data item.
- A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. In Internet Mathematics, volume 1, pages 485-509, 2004.Google Scholar
Cross Ref
- B. Chun, P. Buonadonna, A. AuYoung, C. Ng, D. Parkes, J. Shneidman, A. Snoeren, and A. Vahdat. Mirage: A microeconomic resource allocation system for sensornet testbeds. In Proceedings of the 2nd IEEE Workshop on Embedded Networked Sensors (EmNets), 2005. Google ScholarDigital Library
- Crossbow, Inc. Mote in network programming user reference. http://webs.cs.berkeley.edu/tos/tinyos-1.x/doc/Xnp.pdf.Google Scholar
- F. M. Cuenca-Acuna, C. Peery, R. P. Martin, and T. D. Nguyen. Planetp: Using gossiping to build content addressable peer-to-peer information sharing communities. In HPDC '03: Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, page 236, Washington, DC, USA, 2003. IEEE Computer Society. Google ScholarDigital Library
- A. Demers, D. Greene, C. Hauser, W. Irish, and J. Larson. Epidemic algorithms for replicated database maintenance. In Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pages 1-12. ACM Press, 1987. Google ScholarDigital Library
- S. Floyd, V. Jacobson, S. McCanne, C.-G. Liu, and L. Zhang. A reliable multicast framework for light-weight sessions and application level framing. In Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pages 342-356. ACM Press, 1995. Google ScholarDigital Library
- O. Gnawali, B. Greenstein, K.-Y. Jang, A. Joki, J. Paek, M. Vieira, D. Estrin, R. Govindan, and E. Kohler. The TENET architecture for tiered sensor networks. In Proceedings of the ACM Conference on Embedded Networked Sensor Systems (Sensys), 2006. Google ScholarDigital Library
- J.W. Hui and D. Culler. The dynamic behavior of a data dissemination protocol for network programming at scale. In SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 81- 94, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- P. Levis, D. Gay, and D. Culler. Active sensor networks. In Second USENIX/ACM Symposium on Network Systems Design and Implementation (NSDI), 2005. Google ScholarDigital Library
- P. Levis, N. Lee, M. Welsh, and D. Culler. TOSSIM: Simulating large wireless sensor networks of tinyos motes. In Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003), 2003.Google ScholarDigital Library
- P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code maintenance and propagation in wireless sensor networks. In First USENIX/ACM Symposium on Network Systems Design and Implementation (NSDI), 2004. Google ScholarDigital Library
- C.-J. M. Liang, R. Musaloiu-Elefteri, and A. Terzis. Typhoon: A reliable data dissemination protocol for wireless sensor networks. In Proceedings of 5th European Conference on Wireless Sensor Networks (EWSN), pages 268-285, 2008. Google ScholarDigital Library
- M. Luby. Lt codes. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 271-282, 2002. Google ScholarDigital Library
- R. Merkle. Secrecy, authentication, and public key systems. Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. Google ScholarDigital Library
- R. Morris and K. Thompson. Password security: a case history. Commun. ACM, 22(11):594-597, 1979. Google ScholarDigital Library
- V. Naik, A. Arora, P. Sinha, and H. Zhang. Sprinkler: A reliable and energy efficient data dissemination service for extreme scale wireless networks of embedded devices. IEEE Transactions on Mobile Computing, 6(7):777-789, 2007. Google ScholarDigital Library
- S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu. The broadcast storm problem in a mobile ad hoc network. In Proceedings of the fifth annual ACM/IEEE international conference on Mobile computing and networking, pages 151-162. ACM Press, 1999. Google ScholarDigital Library
- E. Soljanin. Hybrid arq in wireless networks. DIMACS Workshop on Network Information Theory, 2003.Google Scholar
- F. Stann, J. Heidemann, R. Shroff, and M. Z. Murtaza. Rbp: robust broadcast propagation in wireless networks. In SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems, pages 85-98, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- G. Tolle and D. Culler. Design of an application-cooperative management system for wireless sensor networks. In Proceedings of the Second European Workshop of Wireless Sensor Networks (EWSN 2005), 2005.Google ScholarCross Ref
- L. Wang. MNP: multihop network reprogramming service for sensor networks. In Proceedings of the Second ACM Conference On Embedded Networked Sensor Systems (SenSys), pages 285-286, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- K. Whitehouse, G. Tolle, J. Taneja, C. Sharp, S. Kim, J. Jeong, J. Hui, P. Dutta, and D. Culler. Marionette: using rpc for interactive development and debugging of wireless embedded networks. In IPSN '06: Proceedings of the fifth international conference on Information processing in sensor networks, pages 416-423, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- M. Zuniga and B. Krishnamachari. Analyzing the transitional region in low power wireless links. In First IEEE International Conference on Sensor and Ad hoc Communications and Networks (SECON), 2004.Google ScholarCross Ref
Index Terms
- Data Discovery and Dissemination with DIP
Recommendations
A Data Dissemination Algorithm for Opportunistic Networks
SYNASC '11: Proceedings of the 2011 13th International Symposium on Symbolic and Numeric Algorithms for Scientific ComputingOpportunistic networks are an evolution of MANETs, where highly mobile nodes that have no physical route connecting them might need to communicate. In this case routes are built dynamically, as nodes act according to a store-carry-and-forward paradigm. ...
Bloom filter based secure and anonymous DSR protocol in wireless ad hoc networks
Wireless ad hoc networks, especially in the hostile environment, are vulnerable to traffic analysis which allows the adversary to trace the routing messages and the sensitive data packets. Anonymity mechanism in ad hoc networks is a critical securing ...
Comments