Challenges and new approaches for efficient data gathering and dissemination in pervasive wireless networks

ABSTRACT

Motivated by the current trends in wireless technologies, we present challenging scenarios consisting of moving and uncoordinated wireless objects as well as algorithms that are likely to perform well in such environments. Our primary interest is to design network protocols to efficiently build and maintain distributed communication systems based on opportunistic design principles. Such systems should continue to operate well even if communication is sporadic, no end-to-end routes are available, and sources and consumers of information are not known in advance. Also the environment poses many challenges, that are typical for wireless mobile devices, such as wireless channel impairments, the impossibility of having up-to-date and accurate views of the network topology at every device, and limited energy resources. In the second part of the paper, we discuss and propose solutions for data dissemination in such an environment by exploiting network coding techniques. Furthermore, we report first results which reveal that network coding largely outperforms standard solutions which are based on the classical store and forward paradigm.

REFERENCES

• 1: A. Vahdat and D. Becker, "Epidemic routing for partially--connected ad hoc networks," in Technical Report CS-2000-06, July 2000.
• 2: Anders Lindgren , Avri Doria , Olov Schelén, Probabilistic routing in intermittently connected networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.3, July 2003 [doi>10.1145/961268.961272]
• 3: Jörg Widmer , Jean-Yves Le Boudec, Network coding for efficient communication in extreme networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.284-291, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080147]
• 4: P. A. Chou, T. Wu, and K. Jain, "Practical network coding," in 51st Allerton Conf. Communication, Control and Computing, Oct. 2003.
• 5: R. Koetter, "Network coding bibliography," URL: http://tesla.csl.uiuc.edu/~koetter/NWC/Bibliography.html.
• 6: John Heidemann , Fabio Silva , Deborah Estrin, Matching data dissemination algorithms to application requirements, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958517]
• 7: S.-Y. R. Li, R. W. Yeung, and N. Cai, "Linear network Coding," IEEE Trans. on Information Theory, vol. 49, no. 2, Feb. 2003.
• 8: R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. on Information Theory, vol. 46, no. 4, July 2000.
• 9: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 10: J. Widmer, C. Fragouli, and J.-Y. L. Boudec, "Low--complexity energy--efficient broadcasting in wireless ad--hoc networks usign network coding," in Proc. IEEE Information Theory Workshop, Oct. 2004.
• 11: C. Fragouli, J. Widmer, and J.-Y. L. Boudec, "A network coding approach to energy efficient broadcasting: from theory to practice," in IEEE Infocom, 2006.
• 12: Mehul Motani , Vikram Srinivasan , Pavan S. Nuggehalli, PeopleNet: engineering a wireless virtual social network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080855]
• 13: P. T. Eugster, R. Guerraoui, A. M. Kermarrec, and L. Massoulié, "Epidemic information dissemination in distributed system," Innovative Technology for Computing Professionals, vol. 37, no. 5, May 2004.
• 14: Y. Yao and J. Gehrke, "Query processing for sensor networks," in CIDR 2003, 2003.
• 15: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 16: Deepak Ganesan , Ben Greenstein , Denis Perelyubskiy , Deborah Estrin , John Heidemann, An evaluation of multi-resolution storage for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958502]
• 17: Deepak Ganesan , Deborah Estrin , John Heidemann, Dimensions: why do we need a new data handling architecture for sensor networks?, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.143-148, January 2003 [doi>10.1145/774763.774786]
• 18: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang, Fractionally cascaded information in a sensor network, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984668]
• 19: Joanna Kulik , Wendi Heinzelman , Hari Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks, v.8 n.2/3, p.169-185, March-May 2002 [doi>10.1023/A:1013715909417]
• 20: Alexandros G. Dimakis , Vinod Prabhakaran , Kannan Ramchandran, Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 21: Y. Shavitt and A. Shay, "Optimal Routing in Gossip Networks," IEEE Trans. Veh. Technol., vol. 54, no. 4, July 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.3 Network Operations
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Design, Management, Theory