PowerPoint PresentationSensor Networks vs. Ad hoc NetworksSensor Networks PreliminariesSlide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Rumor Routing AlgorithmSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32ReferencesRouting inSensor NetworksSensor Networks vs. Ad hoc Networks –Higher number of sensor nodes (several orders of magnitude) Higher number of sensor nodes (several orders of magnitude) –Dense deploymentDense deployment–Prone to failuresProne to failures–Limited in power, computation and memoryLimited in power, computation and memory–May not have global identification (ID) due to high overhead and May not have global identification (ID) due to high overhead and the total number of sensorsthe total number of sensorsDeployment:Deployment:–RandomlyRandomly–Pre-determined or engineeredPre-determined or engineeredSensor Networks Preliminaries –For large scale environment monitoring applications, dense For large scale environment monitoring applications, dense sensor networks are mainly used sensor networks are mainly used –Sensing capabilities should be distributed and coordinated Sensing capabilities should be distributed and coordinated amongst the sensor nodesamongst the sensor nodes–Algorithms deployed should be localized since transmissions Algorithms deployed should be localized since transmissions between large distances are expensive and lowers networks life between large distances are expensive and lowers networks life timetime–These networks should be self-configuring, scalable, redundant These networks should be self-configuring, scalable, redundant and robust during topology changesand robust during topology changes–Probabilistic algorithm and makes packet forwarding decisions based on Probabilistic algorithm and makes packet forwarding decisions based on localized informationlocalized information–Based on a tree-like topology rooted at the sink of the networkBased on a tree-like topology rooted at the sink of the network–Uses Uses forwardforward approach to contribute to end-to-end reliability approach to contribute to end-to-end reliability–Avoids packet loss by sending multiple packets of the single eventAvoids packet loss by sending multiple packets of the single event–Three sources of packets loss expected:Three sources of packets loss expected:Isolated linkIsolated linkPatterned node failuresPatterned node failuresMalicious or misbehaving nodesMalicious or misbehaving nodesAlgorithm for Robust Routing in Volatile Environments(ARRIVE)[Karlof+ 2002]TerminologyTerminology–EventEvent: Identified by [SourceID, EventID]: Identified by [SourceID, EventID]–LevelLevel: Each node has unique level indicating distance from source to sink (in terms : Each node has unique level indicating distance from source to sink (in terms of hops)of hops)–ParentsParents: Nodes one level closer to the sink: Nodes one level closer to the sink–Neighbors: Neighbors: Nodes on the same level and be able hear each otherNodes on the same level and be able hear each other–PushPush: Push packet to one of the neighbors: Push packet to one of the neighbors–Forward: Forward: Forward packet to one of the parentsForward packet to one of the parents–Forwarding Probability: Forwarding Probability: Included in the packet header and used to probabilistically Included in the packet header and used to probabilistically select whether to push or forwardselect whether to push or forward–Reputation History: Reputation History: Each node keeps this information for each of its parents and Each node keeps this information for each of its parents and neighbors neighbors –Convergence: Convergence: Prevents multiple packets of the same event being sent to same Prevents multiple packets of the same event being sent to same source of failuresource of failureARRIVE–Achieves Achieves diversitydiversity in paths in two ways: in paths in two ways:Upon receiving a packet, the next hop is selected probabilistically Upon receiving a packet, the next hop is selected probabilistically based on link reliability and node reputationbased on link reliability and node reputationWhen more than two or more packets of the same event are When more than two or more packets of the same event are processed, these packets are ensured to follow different outgoing linksprocessed, these packets are ensured to follow different outgoing links–Takes advantage of passive participation and needs to be used cautiouslyTakes advantage of passive participation and needs to be used cautiously–Each nodes keeps the following information:Each nodes keeps the following information:LevelLevelNeighbors listNeighbors listParents listParents listReputation history of neighbors and parentsReputation history of neighbors and parentsConvergence history of specific eventsConvergence history of specific eventsARRIVEAssumptionsAssumptions–The networks is assumed to be dense enough that sufficient multiplicity of paths The networks is assumed to be dense enough that sufficient multiplicity of paths between sources and sink for algorithm to perform wellbetween sources and sink for algorithm to perform well–The network is almost considered as a static networkThe network is almost considered as a static network–Sensors are considered to have a low per-node costSensors are considered to have a low per-node cost–Routes used by the packets are unlikely to be optimal due to the probabilistic nature Routes used by the packets are unlikely to be optimal due to the probabilistic nature of the algorithmof the algorithm–Messages flow from nodes to sink, not the other way aroundMessages flow from nodes to sink, not the other way around–There is only one sink availableThere is only one sink availablePerformance MetricsPerformance Metrics–Event delivery ratioEvent delivery ratio–Three other metrics measuring the cost of deploying ARRIVEThree other metrics measuring the cost of deploying ARRIVEARRIVEAlgorithm DescriptionAlgorithm Description–Bread first search rooted at sink is used to initialize level, parents, neighbors state Bread first search rooted at sink is used to initialize level, parents, neighbors state information at each nodeinformation at each node–When a nodes hears a packets, it checks to see if the packet is addressed for itWhen a nodes