DOC PREVIEW
Berkeley ELENG 228A - Rumor Routing Algorithm for Sensor Networks

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Rumor Routing Algorithm for Sensor NetworksDavid Braginsky, Deborah EstrinEE228A presentationDesign Considerations and Requirements• Each node has limited computational power• Each node has limited communication capabilitiesNetwork:• Self-configuring, scalable, redundant• Robust to shifting topologies• Reasonable failure ratesMain IdeaDescribe a method of routing queries to nodes that have observed a particular event, which allows to retrieve the data keyed on the event and not the underlying network addressing scheme or geographyDefinitions• Event– abstraction identifying anything from sensor readings to processing results– assumed to be localized occurring in a fixed region of space• Query– request for information– order to collect specific dataQuery is originated from the query source and searches for path to the event. As soon as it finds the node with event path info it is routed directly to the event.AWhen agent creating the path to the green event comes across a path to the red event it continues propagating the aggregate path to bothAAAgents also optimize the path to the eventRumor Routing Algorithm• Network consists of densely distributed wireless sensor nodes with relatively short symmetric radio range• Nodes record events and route queries• Each node maintains a list of neighbors, list of events and forwarding information to all the events it knows • Neighbors list is created and maintained actively by broadcasting a request or passively by listening to other node broadcastsAgents• Carry the list of events• Inform nodes of the known events and routs to them• Perform sync of routing tables• Maintain the list of recently seen nodes• Pick the next hop not from that list• Created upon event• Die when TTL expiresQueries• Can be generated any time by any node• Have reasonable TTL• Perform random walk until find path to the event• Maintain the list of recently seen nodes to avoid loops• If still undelivered, then they can be retransmitted or floodedFlooding Mechanisms• Query Flooding– Independent of the number of events– Useful if the number of events is very high compared to the number of queries• Event Flooding– Independent of the number of queries– Useful if the number of queries is very high compared to the number of eventsWhen to use Rumor RoutingNumber of QueriesNumber of TransmissionsEvent FloodingQuery FloodingRumor Routing - one possibilitySimulationhttp://lecs.cs.ucla.edu/~daveey/art/code.html• Area: 200x200 sq. meters• Number of nodes: N = {3000, 4000, 5000}• Neighbors: nodes within 5m from each other• Number of queries: Q• Energy for query flooding: N*Q• Number of events: E = {10, 50, 100}• Energy for event flooding: N*E• Number of delivered queries: Qd• Average energy per query: Eq+N*(Q-Qd)/Q, where Eq – average energy spent on routing a query• Energy for rumor routing: Es+Q*(Eq+N*(Q-Qd)/Q), where Es – energy required to establish routesTunable Parameters• Number of Agents: A• Agent TTL: La• Query TTL: LqSimulation ResultsSimulation ResultsTODO• Network Dynamics: events do not occur simultaneously• Consideration of Collisions• Non-localized Events• Query Pattern and Next Hop Selection• Parameter SettingsConclusionAlgorithm may be practical under certain conditions, but when and how – TBD.In other words, there is still a lot of work


View Full Document

Berkeley ELENG 228A - Rumor Routing Algorithm for Sensor Networks

Documents in this Course
FAST TCP

FAST TCP

57 pages

Load more
Download Rumor Routing Algorithm for Sensor Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Rumor Routing Algorithm for Sensor Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Rumor Routing Algorithm for Sensor Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?