BU CS 580S - Real-Time Communication in Sensor Networks

Unformatted text preview:

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 worldReal-time constraints may existSurveillance systemBattlefield monitoringEarthquake response systemSmart hospitalsMotivationFreshness of dataPromptness of Command and Control3Need for a new real-time communication methodExisting real-time communication solutions are inappropriateIntServ: too expensive for sensor networksResource reservationPer-flow informationSensor nodes are referred to by attributes rather than unique ID’sDiffServControl Area NetworkSmall scale (mainly local area)Many restrictions for predictabilityNeed for a new real-time communication method (cont.)MANET protocols Time insensitiveLess strict energy constraintsRoute discovery may incur a lot of delay and energy consumptionAODVDSRLARDesign GoalsProvide E2E delay guaranteeE2E delay is proportional to the distance between the source and destinationPer hop speed guaranteeProbabilistic soft real-time guaranteesImpossible to provide hard guaranteesSPEED actually improves but does not guarantees the E2E delaySupport a desired delivery speed across the sensor networkDesign GoalsLocalized behaviorAn action by a node does not affect the whole networkContrasts to MANET protocols (e.g., AODV & DSR)Stateless architectureOnly maintains immediate neighbor info.Design GoalsMinimum MAC layer supportSPEED does not require real-time/QoS-aware MAC supportCongestion ControlTraffic patterns may fluctuate significantlyShort-term rate adjustment via feedback controlLong-term backpressure re-routingVoid AvoidanceBackpressure re-routingTraffic Load BalancingNon-deterministic forwardingScalability IssuesTime ScalabilityGF (Geographic Forwarding) to avoid route discoveryE2E speed is proportional to the distance between the source & destinationsdBackground – GFChoose the node closest to the destination in FSMore appropriate for real-time communication than AODV or DSRScalability Issues (Cont.)Memory ScalabilityNo per-flow stateNo per-destination route cacheJust keep (immediate) neighbor tableEnergy ScalabilityNo network-wide floodingNondeterministic forwarding to balance energy consumptionsAssumptionsEach node is aware of its locationPeriodic 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 iFSi (Destination) = {node  NSi | L – L_next > 0 }DefinitionsSpeed Set PointDesired speed toward the destinationSpeed MissOne hop relay speed violates the set pointMiss Ratio#packet misses in a specified periodSNGFjijiHopDe laynex tLLnDestinati oSpeed_)(SNGFForward a packet to a node that is in FSi and can support the speed set pointProbabilistically select one nodeThe higher its speed, the higher its probabilityIf 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/ ofDelay Estimation: Delay= Round Trip Time – Receiver Side Processing TimeOn/Off SwitchBack-Pressure ReroutingLast Mile ProcessSNGFBackpressureReroutingNFLBeaconExchangeAPIUniCast MultiCast AnyCastMACDelayEstimationNeighborTableRelay 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 AvoidanceIn 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 ProcessAreaMulticastSend(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

BU CS 580S - Real-Time Communication in Sensor Networks

Download Real-Time Communication in 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 Real-Time Communication in 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 Real-Time Communication in 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?