Efficient and robust query processing in dynamic environments using random walk techniques

Citations Over TimeTop 10% of 2004 papers

Abstract

Many existing systems for sensor networks rely on state information stored in the nodes for proper operation (e.g., pointers to parent in a spanning tree, routing information, etc). In dynamic environments, such systems must adopt failure recovery mechanisms, which significantly increase the complexity and impact the overall performance. In this paper, we investigate alternative schemes for query processing based on random walk techniques. The robustness of this approach under dynamics follows from the simplicity of the process, which only requires the connectivity of the neighborhood to keep moving. In addition we show that visiting a constant fraction of sensor network, say 80%, using a random walk is efficient in number of messages and sufficient for answering many interesting queries with high quality. Finally, the natural behavior of a random walk, also provide the important properties of load-balancing and scalability.

Related Papers

• → Scalability Issues of Blockchain Technology(2020)30 cited
• → Diffusivity of a random walk on random walks(2014)6 cited
• → Anomalous conformation of polymer chains: random walk of a random walk on a random walk(1986)2 cited
• → Two‐Dimensional Random Walk(2013)1 cited
• RESEARCH ON THE SCALABILITY OF THE LARGE SCALE PARALLEL APPLICATION PROGRAMS(2000)