RaWMS -: random walk based lightweight membership service for wireless ad hoc network

ABSTRACT

RaWMS is a novel lightweight random membership service for ad hoc networks. The service provides each node with a partial uniformly chosen view of network nodes. Such a membership service is useful, e.g., in data dissemination algorithms, lookup and discovery services, peer sampling services, and complete member-ship construction. The design of RaWMS is based on a novel re-verse random walk (RW) sampling technique. The paper includes a formal analysis of both the reverse RW sampling technique and RaWMS and verifies it through a detailed simulation study. In addition, RaWMS is compared with a number of other known methods such as flooding and gossip-based techniques.

REFERENCES

• 1: André Allavena , Alan Demers , John E. Hopcroft, Correctness of a gossip based membership protocol, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073871]
• 2: C. Avin and G. Ercal. Bounds on the mixing time and partial cover of ad-hoc and sensor networks. Technical Report 040028, UCLA, June 2004.
• 3: Ziv Bar-Yossef , Alexander Berg , Steve Chien , Jittat Fakcharoenphol , Dror Weitz, Approximating Aggregate Queries about Web Pages via Random Walks, Proceedings of the 26th International Conference on Very Large Data Bases, p.535-544, September 10-14, 2000
• 4: Z. Bar-Yossef, R. Friedman, and G. Kliot. RaWMS - Random Walk based Lightweight Membership Service for Wireless Ad Hoc Networks. Technical Report CS-2006-05, Technion, Haifa, Israel, January 2006.
• 5: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 6: Stephen Boyd , Persi Diaconis , Lin Xiao, Fastest Mixing Markov Chain on a Graph, SIAM Review, v.46 n.4, p.667-689, 2004 [doi>10.1137/S0036144503423264]
• 7: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Mixing times for random walks on geometric random graphs. In The 2nd Workshop on Analytic Algorithmics and Combinatorics (ANALCO), January 2005.
• 8: Anonymous Gossip: Improving Multicast Reliability in Mobile Ad-Hoc Networks, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.275, April 16-19, 2001
• 9: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 10: Shlomi Dolev , Elad Schiller , Jennifer Welch, Random walk for self-stabilizing group communication in ad hoc networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571872]
• 11: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 12: Uriel Feige, A fast randomized LOGSPACE algorithm for graph connectivity, Theoretical Computer Science, v.169 n.2, p.147-160, Dec. 5, 1996
• 13: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, SCAMP: Peer-to-Peer Lightweight Membership Service for Large-Scale Group Communication, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.44-55, November 07-09, 2001
• 14: D. Gavidia, S. Voulgaris, and M. van Steen. Epidemic-style Monitoring in Large-Scale Sensor Networks. Technical Report IR-CS-012, Vrije Universiteit, Amsterdam, Netherlands, March 2005.
• 15: C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In Proc. of the 23rd INFOCOM, pages 259--259, 2004.
• 16: P. Gupta and P. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. In Stochastic Analysis, Control, Optimization and Applications, Birkhauser, Boston, pages 547--566, 1998.
• 17: V. Guruswami. Rapidly mixing markov chains: a comparison of techniques. May 2000, Available at http: //www.cs.washington.edu/homes/venkat/pubs/pubs.html.
• 18: Z. Haas, J. Halpern, and L. Li. Gossip-Based Ad Hoc Routing. In Proc. of the 21st INFOCOM, pages 1707--1716, June 2002.
• 19: Z. Haas and B. Liang. Ad Hoc mobility management with randomized database groups. In Proc. of ICC, volume 3, pages 1756--1762, June 1999.
• 20: Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 21: Anne-Marie Kermarrec , Laurent Massoulié , Ayalvadi J. Ganesh, Probabilistic Reliable Dissemination in Large-Scale Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.248-258, March 2003 [doi>10.1109/TPDS.2003.1189583]
• 22: L. Lovász. Random Walks on Graphs: A Survey. Combinatorics, 2:1--46, 1993.
• 23: J. Luo, P.Th. Eugster, and J.-P. Hubaux. Route Driven Gossip: Probabilistic Reliable Multicast in Ad Hoc Networks. In Proc. of 23rd INFOCOM, 2003.
• 24: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 25: Roie Melamed , Idit Keidar, Araneola: A Scalable Reliable Multicast System for Dynamic Environments, Proceedings of the Network Computing and Applications, Third IEEE International Symposium on (NCA'04), p.5-14, August 30-September 01, 2004
• 26: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 27: P. Panchapakesan and D. Manjunath. On the Transmission Range in Dense Ad Hoc Radio Networks. In Proc. of IEEE SPCOM, 2001.
• 28: M. D. Penrose. Random Geometric Graphs. Oxford Press, 2003.
• 29: Himabindu Pucha , Saumitra M. Das , Y. Charlie Hu, Ekta: An Efficient DHT Substrate for Distributed Applications in Mobile Ad Hoc Networks, Proceedings of the Sixth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'04), p.163-173, December 02-03, 2004 [doi>10.1109/MCSA.2004.11]
• 30: Sergio D. Servetto , Guillermo Barrenechea, Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570741]
• 31: A. Sinclair. Improved bounds for mixing rates of Markov chains and multi-commodity flow. Combinatorics, Probability & Computing, 1:351--370, 1992.
• 32: Cornell University. JiST/SWANS. http://jist.ece.cornell.edu/.

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.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Design

Keywords:
ad hoc networks, membership service, random walk