Rumor Routing Algorithm For Sensor Networks. David Braginsky ([email protected]), Deborah Estrin. Abstract Advances in micro-sensor and radio technology will enable small but smart sensors to be deployed for a wide range of environmental monitoring applications. In order to constrain communication overhead, dense sensor networks call for new and highly efficient methods for distributing queries to nodes that have observed interesting events in the network. A highly efficient data-centric routing mechanism will offer significant power cost reductions [6], and improve network longevity. Moreover, because of the large amount of system and data redundancy possible, data becomes disassociated from specific node and resides in regions of the network [1][3][8]. This paper describes and evaluates through simulation a scheme we call Rumor Routing, which allows for queries to be delivered to events in the network. Rumor Routing is tunable, and allows for tradeoffs between setup overhead and delivery reliability. It’s intended for contexts in which geographic routing criteria are not applicable because a coordinate system is not available or the phenomenon of interest is not geographically correlated. 1. Introduction The emerging low-power and small form-factor processors, equipped with wireless communication capabilities and sensors allow for large-scale, extremely dense networks for environment monitoring. While most current sensing networks involve small numbers of sensors, supported by centralized processing and analysis hardware [4], these new networks will distribute computation among a high number of nodes. Applications for these networks must use algorithms that are highly distributed, since only short-ranged communication is preferred in the context of the stringent power constraints.[9][1] Furthermore, each node has limited high SNR sensing range, so sensing is best distributed and coordinated amongst a potentially large set of nodes. The algorithms these networks employ must be highly localized [18], as large distance transmissions are very expensive, and diminish the network’s overall lifespan. Due to the size of these networks, they must be self-configuring, highly scalable, redundant, and robust in dealing with shifting topologies due to node failure and environment changes. [7] Applications utilizing these networks must be able to gather data from different parts of the network, without taxing the network’s limited bandwidth and power. The communication channels are noisy, failure rates high, and routes ephemeral. Furthermore, ad-hoc deployment, required for dealing with networks of this size, may not provide global localization information to individual nodes. One area in which these sensor-nets will be used is large scale environmental monitoring. [5] The goal is to enable the scattering of thousands of these nodes in areas that are difficult to access for study using conventional methods. The network could then monitor events [15], perform local computations on the data, and either, relay aggregated data, or configure local and global actuators. In this paper we describe and analyze a method of routing queries to nodes that have observed a particular event. This allows retrieval of data keyed on the event, not the underlying network addressing scheme or geography. An event is an abstraction, identifying anything from a set of sensor readings, to the node’s processing capabilities. For the purpose of the simulation studies in this paper, events are assumed to be localized phenomenon, occurring in a fixed region of space. This assumption will hold for a wide variety of sensor-net applications, since many external events are localized them selves. A query can be a request for information, or orders to collect more data. Once the query arrives at its destination, data can begin to flow back to the query’s originator. If the amount of returning data is significant, it makes sense to invest in discovering short paths from the source to the sink. Methods such as directed diffusion [1] resort to flooding the query throughout the entire network [11], in order to discover the best path. If geographic information is available, the best path is the greedy shortest path, and does not require flooding [17][2]. However, in many applications the quality of the path may not be very important, since the application may only request a small amount of data back, or simply needs to order the target node to initiate morethorough sensing. In such cases, flooding every query may not be as efficient as delivering it by a non-optimal route. Flooding does not have to be restricted to queries. For applications where there are few events and many queries, it makes sense to flood the event, and set up gradients towards it. [3] However, unless the number of queries per event and the amount of data generated by each event is quite high, the setup cost for event flooding cannot be effectively amortized. This paper proposes rumor routing, a logical compromise between flooding queries and flooding event notifications. The idea is to create paths leading to each event; whereas event flooding creates a network-wide gradient field [3]. In this way, when a query is generated it can be sent on a random walk until it finds the event path; instead of flooding it throughout the network. Figure 1: Query is originated from the query source and searches for a path to the event. As soon as it finds a node on the path, it’s routed directly to the event. As soon as the query discovers the event path, it can be routed directly to the event. If the path cannot be found, the application can try re-submitting the query, or as a last resort, flooding it. As this paper shows, under a wide range of conditions, it is possible to achieve an extremely high delivery rate. Monte-Carlo simulations show the probability of two lines intersecting in a bounded rectangular region to be approximately 69%. This means five paths leading to an event will have a 99.7% chance of being encountered by a query. Although neither the path nor the query is entirely straight, and the topology may not be rectangular, the heuristic should still hold. The number of paths and the number of query attempts increase the likelihood of delivery exponentially, making the Rumor Routing tunable to a wide variety of application requirements. The method for setting up these paths to an event is the main focus of this paper.
View Full Document
Unlocking...