2004 · 124 citations · 16 references
ComputingComputer ScienceComputer SystemsComputer NetworksDistributed SystemsFault-tolerant SystemsDistributed Sensor NetworksLoad Balancing Under FailuresQuery ProcessingRandom WalksSensor NetworksWireless Sensor NetworksFailure MechanismsRandom Walk AlgorithmsRandom Walk ModelsRandom Walks On NetworksRecovery MechanismsScalable Sensor NetworksSensor Network RoutingWireless Sensor Network Routing
Many sensor‑network systems depend on node‑stored state such as routing pointers, and in dynamic environments the need for failure recovery adds complexity and degrades performance. The study investigates alternative query‑processing schemes using random walk techniques. The approach relies on a simple random walk that only needs neighborhood connectivity, ensuring robustness in dynamic settings. The results demonstrate that a random walk visiting 80 % of the network uses few messages yet answers many queries with high quality, while also delivering load balancing and scalability.
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.
16
The broadcast storm problem in a mobile ad hoc network
Sze-Yao Ni, Yu‐Chee Tseng, Yuh‐Shyan Chen et al. · 1999 · 3.1K citations · Full text
Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein et al. · ACM SIGOPS Operating Systems Review · 2002 · 2.7K citations
Directed diffusion for wireless sensor networking
Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin et al. · IEEE/ACM Transactions on Networking · 2003 · 2.4K citations