Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Presented by: Hossein AhmadiRouting in wireless ad-hoc and sensor networksA Review of Current Routing Protocols for Ad Hoc Mobile Wireless NetworksDirected Diffusion: A Scalable and Robust Communication Paradigm for Sensor NetworksFebruary 21, 2008 CS525 - Sensor NetworksAd-hoc and Sensor networksBoth:No infrastructureMobile nodesDynamic linksAd-hoc networks:One-to-one communicationSensor networks: Energy constrainedData centric -> Many-to-one communicationApplication oriented ->Data aggregationFebruary 21, 2008 CS525 - Sensor NetworksAd-hoc routing protocolsFebruary 21, 2008 CS525 - Sensor NetworksDestination-Sequenced Distance-vector Routing (DSDV)Common Bellman-Ford routingPeriodic updatesFull DumpIncrementalUse 2 TablesRouting TableTable to keep track of incremental updatesFebruary 21, 2008 CS525 - Sensor NetworksCluster Gateway Switch Routing (CGSR)Hierarchical architecture based on DSDVClusters of nodes with a cluster head.Cluster head is responsible to forward to/from its cluster.Gateway: nodes within the communication range of two or more cluster headUse 2 tablesCluster member table (Inter-cluster)Routing table (Intra-cluster)February 21, 2008 CS525 - Sensor NetworksCluster Gateway Switch Routing (CGSR)February 21, 2008 CS525 - Sensor NetworksThe Wireless Routing Protocol (WRP)Update: Neighborhood update messagesDiscovery: any message (Ack, hello, …)Uses 4 tables:Distance tableRouting tableLink-cost tableMessage retransmission list (MRL) tableLoop Freedom:Keeping second-to-last hop to the destinationFebruary 21, 2008 CS525 - Sensor NetworksTable-driven routing comparisonFebruary 21, 2008 CS525 - Sensor NetworksAd Hoc On-demand RoutingNodes does not maintain up-to-date routing tableExchange information when neededLess update exchange and message complexityAt the cost of path initiationMore efficient in highly dynamic environmentsFebruary 21, 2008 CS525 - Sensor NetworksAd Hoc On-demand Distance Vector Routing (AODV)Improvement to DSDVPath Discovery Request is flooded to reach the destination.Sequence number – Loop freePath is formed using the response assuming the links are symmetricRoute stored –node that PREP had came fromRoutes are cached and expire after some timeLink failure notificationOptional use of hello messagesFebruary 21, 2008 CS525 - Sensor NetworksDynamic Source Routing (DSR)Source RoutingDiscovery:Path information is stored in request and reply.Paths are cachedMultiple paths can be usedFebruary 21, 2008 CS525 - Sensor NetworksDynamic Source Routing (DSR)Asymmetric links:A new request for route to the source.Reply is piggybacked on the request packet.Route Maintenance:Error is discovered (observing retransmission or direct ACK)Route Error is generatedRecovers fast using alternative pathsFebruary 21, 2008 CS525 - Sensor NetworksTemporally Ordered Routing Algorithm (TORA)Each node has a HeightHeight is determined by the time request is received.A route is represented by Directed Acyclic Graph (DAG) build based on the height.Height changes based on the link failures.Link reversal when facing error.February 21, 2008 CS525 - Sensor NetworksTemporally Ordered Routing Algorithm (TORA)Nodes need to be synchronizedRoutes need to be clearMultiple routesLow message overhead for route reconstructionSimilar to Distance Vector algorithmsCount to infinityFebruary 21, 2008 CS525 - Sensor NetworksDirected DiffusionSink floods interestConstrained or DirectionalRefreshedInterest are cached to remember routing directionsInterests can be aggregatedGradients: Pointing back to where interests came from Multi-path routing from source to sinkFebruary 21, 2008 CS525 - Sensor NetworksData Propagation and ReinforcementThe source routes measurements along gradients at specified rateIntermediate nodes downconvert rates as necessaryReinforce some of the neighbor – Increase their gradient rateIntermediate nodes propagate reinforcements to balance the flowFebruary 21, 2008 CS525 - Sensor NetworksEvaluationSimulated in NS2Random node placement50 to 250 nodes (incremented by 50) with the same average densityRadio range: 40mSimulate node failuresEnergy profileTransmit: 660mwReceive: 395mwIdle time: 35mW802.11 MACFixed WorkloadFebruary 21, 2008 CS525 - Sensor NetworksAverage Dissipated Energy and DelayHigh energy efficiency due to in-network aggregation.Low delay due to reinforcements and MAC behaviorFebruary 21, 2008 CS525 - Sensor NetworksImpact of node failures and Negative reinforcementsRobust against failure.Negative reinforcement prunes-off energy consuming pathsFebruary 21, 2008 CS525 - Sensor NetworksAssociativity-Based Routing (ABR)Routing metric: connection-stabilityAssociativity (stability) tableAssociativity increases by receiving more beacon messages.Route Discovery (BQ)Destination node examines the best routes by associativity valuesFavor long-lived routesLocal Recovery (RN, LQ)February 21, 2008 CS525 - Sensor NetworksSignal Stability Routing (SSR)Based on signal strength between nodesUses 2 tablesSignal Strength Table (SST)Routing Table (RT)Two static and dynamic routing protocolsFebruary 21, 2008 CS525 - Sensor NetworksOn-demand routing comparisonFebruary 21, 2008 CS525 - Sensor NetworksDiscussionEnergy aware routing?Use less power consuming pathsBalanced energy consumptionEnd-to-end throughput?Low latency, high connectivity, more stabilityNetwork capacity?High total throughput in the shared mediumAbstraction for routing in many-to-one communication?Multicast and replicationLearn on the Fly: Data-driven Link Estimationand Routing in Sensor Network BackbonesHongwei Zhang, Anish Arora and Prasun SinhaComputer Science and EngineeringThe Ohio State University, USAPresented by: Hossein Ahmadi & Debessay FesehayeContents•Existing routing methods–General Description–Drawbacks•Proposed data-driven routing (LOF)–How it works–The routing metric
View Full Document
Unlocking...