SPEED: A Stateless Protocol for Real-Time Communication in Sensor NetworksMotivation: Why real-time communication?MotivationNeed for a new real-time communication methodNeed for a new real-time communication method (cont.)Design GoalsSlide 7Slide 8Scalability IssuesBackground – GFScalability Issues (Cont.)AssumptionsSPEED ArchitectureSNGF (Stateless Non-deterministic Geographic Forwarding)DefinitionsSNGFSlide 17NFL (MAC Layer Feedback)Backpressure Rerouting based on MAC Layer Feedback & SNGFSlide 20Void AvoidanceLast Mile ProcessEvaluations: Simulation Setup -1Congestion AvoidanceControl OverheadEnergy ConsumptionSlide 27Reminder: RAP (Real-Time MAC)RAP: Prioritized MACSPEED vs. RAPResearch Issues (Possible Projects)Slide 32SPEED: A Stateless Protocol for Real-Time Communication in Sensor NetworksT. He, J. A. Stankovic, C. Lu, T. AbdelzaherMotivation: Why real-time communication?Sense networks monitor the real worldReal-time constraints may existSurveillance systemBattlefield monitoringEarthquake response systemSmart hospitalsMotivationFreshness of dataPromptness of Command and Control3Need for a new real-time communication methodExisting real-time communication solutions are inappropriateIntServ: too expensive for sensor networksResource reservationPer-flow informationSensor nodes are referred to by attributes rather than unique ID’sDiffServControl Area NetworkSmall scale (mainly local area)Many restrictions for predictabilityNeed for a new real-time communication method (cont.)MANET protocols Time insensitiveLess strict energy constraintsRoute discovery may incur a lot of delay and energy consumptionAODVDSRLARDesign GoalsProvide E2E delay guaranteeE2E delay is proportional to the distance between the source and destinationPer hop speed guaranteeProbabilistic soft real-time guaranteesImpossible to provide hard guaranteesSPEED actually improves but does not guarantees the E2E delaySupport a desired delivery speed across the sensor networkDesign GoalsLocalized behaviorAn action by a node does not affect the whole networkContrasts to MANET protocols (e.g., AODV & DSR)Stateless architectureOnly maintains immediate neighbor info.Design GoalsMinimum MAC layer supportSPEED does not require real-time/QoS-aware MAC supportCongestion ControlTraffic patterns may fluctuate significantlyShort-term rate adjustment via feedback controlLong-term backpressure re-routingVoid AvoidanceBackpressure re-routingTraffic Load BalancingNon-deterministic forwardingScalability IssuesTime ScalabilityGF (Geographic Forwarding) to avoid route discoveryE2E speed is proportional to the distance between the source & destinationsdBackground – GFChoose the node closest to the destination in FSMore appropriate for real-time communication than AODV or DSRScalability Issues (Cont.)Memory ScalabilityNo per-flow stateNo per-destination route cacheJust keep (immediate) neighbor tableEnergy ScalabilityNo network-wide floodingNondeterministic forwarding to balance energy consumptionsAssumptionsEach node is aware of its locationPeriodic beacons to exchange location info.Beaconing rate can be very low when sensor nodes are static Senor network is dense enough to supporting greedy geographic routing, while avoiding a voidSPEED ArchitectureSNGF (Stateless Non-deterministic Geographic Forwarding)Neighbor Set of Node i NSi = {node| distance (node, node i ) R}Forwarding Set of Node iFSi (Destination) = {node NSi | L – L_next > 0 }DefinitionsSpeed Set PointDesired speed toward the destinationSpeed MissOne hop relay speed violates the set pointMiss Ratio#packet misses in a specified periodSNGFjijiHopDe laynex tLLnDestinati oSpeed_)(SNGFForward a packet to a node that is in FSi and can support the speed set pointProbabilistically select one nodeThe higher its speed, the higher its probabilityIf no node in FSi can support the set point, reduce the relay ratio via NFLNFL (MAC Layer Feedback)-SNGFNeighborNodesBeaconMR Setpoi ntNeighborhood TableDel ay Esti mati on BeaconSELF Nei ghborsMAC FeedbackBack Pressure BeaconRelay RatioControllerRel ayRat i omi ssrati oon/ ofDelay Estimation: Delay= Round Trip Time – Receiver Side Processing TimeOn/Off SwitchBack-Pressure ReroutingLast Mile ProcessSNGFBackpressureReroutingNFLBeaconExchangeAPIUniCast MultiCast AnyCastMACDelayEstimationNeighborTableRelay Ratio Control01 iieifNeKu01 ieifuBackpressure Rerouting based on MAC Layer Feedback & SNGF2359107Delay11BooSPEED2011030115Node 5's NTDelay0.5s0.1s0.4s0.1sID97103PacketPacketSourceDestinationBackpressure Rerouting based on MAC Layer Feedback & SNGF2359107DelayBooID Delay 5 0.5S 2 0.1S 4 0.1SNode 3's NT411613ID Delay 5 0.1S 7 0.4SNode 6's NT12Packet 1Packet 1BeaconPacket 2Packet 2Packet 2Packet 2Packet 2Packet (to 4)Void AvoidanceIn a similar way it deals with traffic congestion.Backpressure beacon (ID, Destination, Positive Infinity)Greedy: It may not find a path even if it exists in the worst caseLast Mile ProcessSNGFBackpressureReroutingNFLBeaconExchangeAPIUniCast MultiCast AnyCastMACDelayEstimationNeighborTable12345Last Mile ProcessAreaMulticastSend(Center position, radius, deadline, packet)AreaAnyCastSend(Center position, radius, deadline, packet)UnicastSend(Global_ID,deadline,packet)SpeedReceive()Last Mile ProcessSNGFBackpressureReroutingNFLBeaconExchangeAPIUniCast MultiCast AnyCastMACDelayEstimationNeighborTableEvaluations: Simulation Setup -1Components SettingSimulator & TestBed GloMoSim & Berkeley MotesRouting SPEED, AODV, DSR, GF (Max Progress )SPEED-S (Max Speed ), SPEED-T ( minimum delay)MAC Layer 802.11Bandwidth 200Kb/sPayload size 32 ByteTERRAIN (200m, 200m) Node number 100Node Placement UniformRadio Range 40mRuns 16Congestion Avoidance40901401902402900 10 20 30 40 50 60 70 80 90 100Rate (P/S)Delay (MS)AODVDSRSPEED40901401902400 10 20 30 40 50 60 70 80 90 100Rate(P/S)Delay (MS)SPEEDGFSPEED-SSPEED-T#E2E Delay vs. Congestion-Level#E2E Delay vs. Congestion-LevelDelay: AODV>DSR>SPEED Delay: SPEED-T > GF,SPEED,SPEED-S(Heavy Congestion) Delay: SPEED performs bestControl Overhead#Control Packets vs. Congestion-Level#Control Packets vs.
View Full Document