基于信息协商的传感器协议-SPIN

1、seminar for lecture:Wireless Sensor Networkstopic:SPINDepartment of Computer Science Institute for System Architecture, Chair of Computer NetworksDresden, January 9, 2007Ludwig Ludwig HhneHhneMartin KnechtelMartin KnechtelTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationsl

2、ide #2MotivationDissemination is the process of distributing individual sensor observations to the whole network, treating all sensors as sink nodesReplicating complete view of the environmentEnhance fault toleranceBroadcast critical piece of informationLimited supply of energyEnergy-Conserving comm

3、unication and computationLimited computational powerSophisticated network protocols not suitableLimited communication resourcesCommunication bandwidth is limited to a few hundred KbpsTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #3Motivation Classic FloodingClassi

4、c approach for disseminationSource node sends data to all neighborsReceiving node stores and sends data to all its neighborsRequires no protocol stateDisseminates data quicklyDeficienciesImplosionOverlapResource blindnessTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationsli

5、de #4Motivation Classic Flooding (cont.)ImplosionAlways sends data to a neighbor, even it has already received the data from another nodeFunction of topologyOverlapNodes often cover overlapping areas (e.g. temperature distr.)Function of topology and mapping of observed dataResource blindnessAmount o

6、f energy available does not affect the communication activitiesB BC CD DA Aa aa aa aa aA AB BC Cr rs sq qq qTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #5Concept - IdeaSPIN = Sensor Protocols for Information via NegotiationNegotiationBefore transmitting data, no

7、des negotiate with each other to overcome implosion and overlapOnly useful information will be transferredObserved data must be described by meta-dataResource adaptationEach sensor node has resource managerApplications probe manager before transmitting or processing dataSensors may reduce certain ac

8、tivities when energy is lowTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #6Concept - AssumptionsSensor applications need to communicate about data they have and data they need to obtainExchanging sensor data is expensive, whereas exchanging meta-data is notNodes m

9、ust monitor and adapt to changes in their energy resourcesExtend lifetime of the systemTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #7Architecture Meta-DataCompletely describe the dataMust be smaller than the actual data for SPIN to be beneficialIf you need to di

10、stinguish pieces of data, their meta-data should differMeta-Data is application specificSensors may use their geographic location or unique node IDCamera sensor may use coordinate and orientationApplication must be able to interpret and synthesize its own meta-dataTU Dresden, 10/27/2006SPIN: Sensor

11、Protocols for Information via Negotiationslide #8Architecture MessagesADV data advertisementNode that has data to share can advertise this by transmitting an ADV with meta-data attachedREQ request for dataNode sends a request when it wishes to receive some actual dataDATA data messageContains actual

12、 sensor data with a meta-data headerUsually much bigger than ADV or REQ messagesTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #9SPIN-1 ExampleHas Data Has Data to disseminateto disseminateTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiation

13、slide #10SPIN-1 Example - Advertise StageADVADVADVADVTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #11SPIN-1 Example - Request StageREQREQREQREQTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #12SPIN-1 Example - DATA StageDATDATA

14、ADATDATA ATU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #13SPIN-1 ExampleADVADVADVADVADVADVTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #14SPIN-1 ExampleREQREQREQREQTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information v

15、ia Negotiationslide #15SPIN-1 a 3-Stage Handshake ProtocolNeeds knowledge about single-hop network neighborsAdaptation for lossy networksCompensate lost ADV messages by re-advertising periodicallyCompensate lost REQ/DATA by re-requesting after fixed timeAdaptation for mobile networksTopology changes

16、 trigger updates to neighbor lists of nodesWhen a nodes neighbor list changed, re-advertise all its dataTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #16SPIN-2 Energy-conservationAdds simple energy-conservation heuristic to SPIN-1Incorporate low-energy-thresholdWo

17、rks as SPIN-1 when energy level is highReduce participation of node when approaching low-energy-thresholdWhen node receives data, it only initiates protocol if it can participate in all three stages with all neighbor nodesWhen node receives advertisement, it does not request the dataNode still exhau

18、sts energy below threshold by receiving ADV or REQ messagesTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #17Implementationsimulationno physical implementation but simulation with network simulator ns-2 2event-driven network simulatorextensive support for simulatio

19、n of: TCP, routing, multicast protocolsfunctionality of ns was extended to implement SPIN family, node class extended to create a Resource-Adaptive Node, components:11TU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #18Implementationsimulation test bed25-node wireles

20、s test network, fully connected graphedges signify communicating neighbors11Nodes25Edges59Average degree4,7 neighborsDiameter8 hopsAverage shortest path3,2 hopsAntenna reach10mRadio propagation delay3E8 m/sProcessing delay5-10msRadio speed1 MbpsTransmit cost600 mWReceive cost200 mWData size500 bytes

21、Meta-data size16 bytesNetwork lossesNoneQueuing delaysNoneTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #19Evaluationtwo other dissemination algorithms for comparison:Classic Flooding (explained on former slides)GossipingIdeal disseminationGossipingalternative to

22、classic flooding, use randomization to conserve energyonly forward to one randomly selected neighbor, not to allno implosion: only one copy of the data travels the networkslow distribution of data, slow dissipation of energyExample:resume: avoids implosion, but overlap problem still existsA AB BD DC

23、 C1 12 23 34 4TU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #20EvaluationIdeal Disseminationexplanation by an example: distribution in 2 stepsideal dissemination of observed data a and bB and C have common neighbor D, but no implosionA and C have overlapping initi

24、al data item c, but no overlapping probsimulate result of an ideal dissemination using a modified SPIN-1eliminate time and energy costs for ADV and REQ messagesseries of DATA messages in the network = ideal disseminationA A(a,c(a,c) )B BC C(c)(c)D D1: (a,c1: (a,c) )1: (a)1: (a)1: (c)1: (c)2: (a)2: (

25、a)TU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #21EvaluationSimulationsunlimited energy simulationdata acquired over timeenergy dissipated over timelimited energy simulation (1.6 Joules total energy in the network)data acquired over timeenergy dissipated over tim

26、efor unlimited energy scenario: SPIN-1 = SPIN-2, compared with flooding, gossiping and the ideal data distribution protocolTU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #22Simulation: unlimited energy11TU Dresden, 10/27/2006SPIN: Sensor Protocols for Information v

27、ia Negotiationslide #23Simulation: unlimited energymessage profiles for the simulationsonly SPIN-1 uses meta-dataSPIN-1 does not send any redundant data messageaverage energy dissipated for each node depending on its degreehigh degree nodelie upon a critical path in the networkmay die out before oth

28、er nodes and partition the network11TU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #24Simulation: limited energytotal energy in the system: 1.6 Joulemeasure energy-efficiency of protocolflooding exhausts energy quicklyif energy is very limited, gossiping can accomplish the most data distributionSPIN-2 distribute 10% more data than SPIN-1TU Dresden, 10/27/2006SPIN: Sensor Protocols for Information via Negotiationslide #25ConclusionSummarySPIN is family of data dissemination protocolsmeta-data negotiation and resource adaptationonly tran