Unformatted text preview:

DSR vs. TinyOS BeaconingTopics CoveredAd Hoc Routing ProtocolsTable Driven ProtocolsOn Demand ProtocolsProtocol CharacteristicsProtocol ComparisonTinyOS ImplementationsTinyOS BeaconingTinyOS Beaconing Cont’dTinyOS Beaconing Tree (in TinyViz)Dynamic Source RoutingDSR Implemented AlgorithmDSR IllustrationMote ImplementationThe monsters (revisited):Mica2 Performance EvaluationPerformance Comparison Cont’dProtocol Mobility ConsiderationsJava Sensor Network QuerierJava Sensor Network Querier Cont’dQuerier ImageConclusionsC’est finiDSR vs. TinyOS DSR vs. TinyOS BeaconingBeaconingBy: Brent RoodBy: Brent RoodTopics CoveredTopics Covered•Routing Protocol Overview•Routing Protocol Implementation Details–TinyOS Beaconing–Dynamic Source Routing•Performance Comparison•Mote Implementation•Java Sensor Network QuerierAd Hoc Routing ProtocolsAd Hoc Routing Protocols•Two Basic Types of Ad Hoc Wireless Routing Protocols used in Sensor Networks–Table Driven•E.g. Dynamic Source Routing–On Demand•E.g. TinyOS BeaconingTable Driven ProtocolsTable Driven Protocols•Attempt to maintain consistent up to date routing information for each node–In some cases, tables have nodes keep routes to everyone•Table number/size varies by protocol–Sensor Network’s many-to-one communications paradigm allows smaller tables•Respond to network changes by propagating information–Allows for consistent topology informationOn Demand ProtocolsOn Demand Protocols•Routes are only created on an as needed basis•When a node requires a route, it initiates a route discovery process–Process completes upon receiving a route found message–However, various metrics can be used to determine the returned route that is accepted•Route discovery process can continue until optimal route is found•Route information is maintained in route database until:–Destination is no longer needed–Route times out–An error packet indicates that the route has failedProtocol CharacteristicsProtocol Characteristics•Table Driven–Relies on underlying routing table update mechanism•Involves constant propagation of information–Routes always available (possibly useless)•Resource constraints of sensor networks are sensitive to this sort of useless energy expenditure for unneeded routes•On Demand–Routes only acquired when needed•Direct result is that routes are not always availableProtocol ComparisonProtocol Comparison•On Demand protocols increase latency of packets with unknown destinations•Table Driven protocols require a constant (possibly unneeded) overhead•Balancing act with two factors:–Desired latency (On Demand: Hi; Table: Low)•Depending on rate of route changes and the need for routes to unknown destinations–Constant energy use (On Demand: Low; Table: Hi)•Depending on the rate of constant updateTinyOS ImplementationsTinyOS Implementations•Two protocols implemented in TinyOS–TinyOS Beaconing–Simplified Dynamic Source Routing•TOSSIM used to test/debug protocols•MICA2 motes used for final analysisTinyOS BeaconingTinyOS Beaconing•A Simplified Table Driven Approach•Allows for many-to-one sensor network data-centric routing paradigm•Implemented Algorithm:–Root of network broadcasts a HELLO beacon with it as the source and hop count as 0–All those hearing the beacon mark the root down as their parent –Node forwards the beacon message with its address as the source and the hop count incremented–Recursively, nodes will mark as their parent the node from which they hear the beacon from and forward onTinyOS Beaconing Cont’dTinyOS Beaconing Cont’d•Considerations–Sequence Numbers•Nodes avoid rebroadcasting old beacons by keeping the current beacon sequence number on hand–Hop count is used as a metric•If a node hears a packet with the latest sequence number, but with a smaller hop count than they adopt the source of that packet as their parent–Note: This packet must also be rebroadcastTinyOS Beaconing Tree (in TinyViz)TinyOS Beaconing Tree (in TinyViz)Dynamic Source RoutingDynamic Source Routing•Example of a simple On Demand routing protocol•This implementation does not include–Advanced route caching mechanisms–Optimizations in terms of route selection–Although it has the ability to maintain routes to multiple destinations, only a route to the root is ever obtained/cachedDSR Implemented AlgorithmDSR Implemented Algorithm•Upon a node needing a route to a destination, it creates a Route Request (RREQ) packet and broadcasts•All nodes receiving this packet, append their address to the packet and forward it•When received by the destination, the node generates a Route Reply (RREP) packet•The RREP is then source routed (using the provided list of nodes addresses) back to the destination•Now when the node has data to send, it just sends it source routed (with the entire path attached)–Each node need only forward the packet to the next address indicated in the route•RERR packets are generate upon failure of a link level send–The node will then forward the RERR back to the source–The source will generate another RREQ looking for a new route to the destinationDSR IllustrationDSR IllustrationMote ImplementationMote Implementation•Mica2 motes used•Motes attached to sensor boards–Programmed to automatically take light intensity reading every 2 seconds•DSR–If a node does not have a route to the root upon taking a reading, it initiates a route request (RREQ)•TinyOS Beaconing–Root node is programmed to initiate a beacon once every two secondsThe monsters (revisited):The monsters (revisited):Programming BoardMICA2 MOTEMica2 Performance EvaluationMica2 Performance Evaluation•Given a sensor network of size N and no mobility–Beaconing generates N beacon packets every two seconds (assuming un-partitioned network)–DSR generates (assuming a roughly complete binary tree like topology):•Approximately (ln (N-1) * (N-1)) RREQ transmissions and the same number of RREPs needed for all nodes to get route to the root–N-1 indicates number of nodes excluding root–Ln factors in the depth of the binary tree•2 * ln(N) * N messages needed total•After this initial investment, without mobility/failure, no more routing messages need be generatedPerformance Comparison Cont’dPerformance Comparison Cont’d•Given: –7 participating nodes (including root)–Complete binary tree topology–No node mobility/failureProtocol


View Full Document

BU CS 580S - Routing Protocols

Download Routing Protocols
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 Routing Protocols 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 Routing Protocols 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?