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.