Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
RaWMS - random walk based lightweight membership service for wireless ad hoc networks
Bar-Yossef Z., Friedman R., Kliot G. ACM Transactions on Computer Systems26 (2):1-66,2008.Type:Article
Date Reviewed: Sep 30 2008

A random walk is a trajectory made up of a series of random steps. This paper reports on using the results of the topological study of random walks (RWs) on random geometric graphs to model the network connectivity graph of two-dimensional wireless ad hoc networks and sensor networks, to provide network membership services and applications in a novel fashion. It consists of discussions organized into several sections: “Introduction,” “System Model,” “Random Walk Techniques,” “Random Walk Based Membership Services,” “Gossip Based Membership Services,” “Simulations,” “Related Work,” and “Discussion and Conclusions.” Five appendices discuss “Random Geometric Graphs,” “Chernoff Bounds,” “Reverse-RW-Based Uniform Sampling with a Proof of an Important Lemma,” “Proof of Another Important Lemma,” and “Mixing Time Bound for the Maximum Degree Random Walk.”

The system here is called random walk membership service (RaWMS). It is a novel alternative to other technologies providing membership services. Its uses are asserted to be for data dissemination algorithms, lookup and discovery services, peer sampling services, complete membership construction, and peer-to-peer (P2P) anonymization. The only constraint to the presented strategies and algorithms is the mixing time, the length of the RW in the reverse sampling procedure.

There are at least five opportunities for work on open research questions, including analyzing the exact relationship between mobility patterns and the required lengths of random walks (in the paper, this is done only by simulations). A discovery is that shorter RWs obtain better results than longer ones. Another opportunity then would be to develop protocols for measuring changes in node proximity in every node.

Reviewer:  J. Fendrich Review #: CR136116 (0908-0755)
Bookmark and Share
 
Wireless Communication (C.2.1 ... )
 
 
Design Studies (C.4 ... )
 
 
Distributed Applications (C.2.4 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Modeling Techniques (C.4 ... )
 
 
Network Problems (G.2.2 ... )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Wireless Communication": Date
Mobile power management for wireless communication networks
Rulnick J., Bambos N. Wireless Networks 3(1): 3-14, 1997. Type: Article
Aug 1 1998
New call blocking versus handoff blocking in cellular networks
Sidi M., Starobinski D. Wireless Networks 3(1): 15-27, 1997. Type: Article
Sep 1 1998
The wireless Net
Fowler D. netWorker: The Craft of Network Computing 1(2): 24-34, 1997. Type: Article
Sep 1 1998
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy