Adaptive Protocols for Information Dissemination in

2024年1月29日发(作者：)

AdaptiveProtocolsforInformationDisseminationinWirelessSensorNetworksJoannaKulik,WendiRabiner,andHariBalakrishnanMassachusettsInstituteofTechnologyCambridge,MA02139Email:jokulik,wendi,hari@tractInthispaper,wepresentafamilyofadaptiveprotocols,calledSPIN(SensorProtocolsforInformationviaNego-tiation),thatefficientlydisseminatesinfunningaSPINcommunicationprotocolnametheirdatausinghigh-leveldatadescriptors,emeta-datanegotiatiotion,SPINnodescanbasetheircommunicationde-cisionsbothuponapplication-specificknowledglowsthesensorstoeffilateandanalyzetheperformanceoftwospecificSPINproto-cols,comparifindthattheSPINpro-tocolscandeliver60%findthat,intermsofdisseminationrateandenergyusage,theSPINprotocolsperformclosetothetheoreticaloptimum.1IntroductionWirelessnetworksofsensorsarelikelytobewidelyde-ployedinthefuturebecausetheygreatlyextendourabil-tworkscangreatlyimprovetheaccuracyofinformationobtainedviacollaborsssensornetworksimprovesensingaccuracybyprov,seismicdata,acousticdata,high-resolutionimages,etc.).Whennetworked,sensorscanaggregatesuchdatatoprovidearich,tion,networkedsensorscanfocusthei,anintruderenter-ingabuilding).Finally,networkedsensorscancontinuetofunctionaccuratelyinthefaceoffailureofindividualsensors;forexample,ifsomesensorsinanetworkloseapieceofcrucialinformation,sssensornetworkscanalsoimproveremoteac-cesstosensordatabyprovidingsinknodesthatconnectthemtoothernetworks,suchastheInternet,ensorssharetheirobserva-tionsandprocesstheseobservationssothatmeaningfulandusefulinformationisavailableatthesinknodes,userscanretrieveinforeforeenvisionafutureinwhichcollectionsofsensornodesformadhocdistributedprocessingnetworksthatproduceeasilyansornodeoperatesautonomouslywithnocentralpointofcontrolinthenetwork,andeachnodebasesitsdecisionsonitsmis-sion,theinformationitcurrentlyhas,anditsknowledgeofitscomputing,edtotoday’sisolatedsensors,tomorrow’snet-workedsensorshavethepotentialtoperformtheirrespon-sibilitieswithmoreaccuracy,bstaclesarisefromthelimitedenergy,computationalpower,:Becausenetworkedsensorscanuseuptheirlimitedsupplyofenergysimplyperformingcompu-tationsandtransmittinginformationinawirelessen-vironment,eation:Sensorshavelimitedcomputingpower,andthereforemaynotbeabletorunsophis-ticatednetworkprotocols.

Communication:Thebandwidthofthewirelesslinksconnectingsensornodesisoftenlimited,ontheorderofafewhundredKbps,furtherconstraininginter-sensorcommunication.A(A)(A)Inthispaper,wepresentSPIN(SensorProtocolsforIn-formationviaNegotiation),afamilyofnegotiation-basedinfsontheefficientdissemina-tionofindividualsensorobservationstoallthesensorsinanetwork,reseveralbenefi,itwillgiveusawayofreplicatingcompleteviewsoftheen-vironm,,thatin-trusionhasbeendetectedinasurveillancenetwork)ignofSPINgrewoutofouranalysisofthestrengthsandlimitatotocols,whichwecharacterizeasclassicflooding,ceivingapieceofdata,thereforeastraightforwardprotocolrequiringnoprotocolstateatanynode,anditdisseminatesdataquieficienciesofthissimpleapproachrenderitin-adequateasaprotocolforsensornetworks:BC(A)D(A)Figure1:graph,nodeAstartsbyfl(q,r)CB(r,s)Implosion:Inclassicflooding,anodealwayssendsdatatoitsneighbors,regardlessofwhadstotheimplosionproblem,,nodeAstartsoutbyflood-ingdatatoitstwoneighbors,p:Sensornodesoftencoveroverlappingge-ographicareas,2illustrateswhathap-penswhentwonodes(AandB)gathersuchover-lappingdataandthenfloodthedatatotheircom-monneighbor(C).Again,thealgorithmwastepisaharderproblemtosolvethantheimplosionproblem—implosionisafunctiononlyofnetworktopology,whereasoverlapisafunctionofbothtopologyandthemappingofobserveddatatosensornodes.2Figure2:esesensorsfloodtheirdatatonodeC,ceblindness:Inclassicflooding,nodesdonotmodifytherkofem-beddedsensorscanbe“resource-aware”andadNfamilyofprotocolsincorporatestwokeyin-novationsthatovercomethesedeficiencies:cometheproblemsofimplosionandoverlap,tiatesuccessfully,how-ever,rtothedescriptorsusedinSPINnegoti-ationsasmeta-data.

InSPIN,nsornodehasitsownresourceman-agerthatkeepstrackofresourceconsumption;,er,thesefeaturesovercomethethreedeficienciesofclassicflotiationprocessthatprecedesactualdatatransmissioneliminatesofmeta-datadescriptorseliminatesthepossibilityofoverlapbecauseitallowwareoflocalenergyresourcesallowssensorstocutbackonactivitieswhenevertheirenergyresourcesarelow,sstheefficiencyofinformationdisseminationviaSPIN,weperformasimulation-basedstudyoffiheprotocolsareSPINprotocols(whichwecallSPIN-1andSPIN-2);erthreeprotocolsfunctionascomparisonprotocols:(i)flooding,whichweoutlinedabove;(ii)gossiping,avariantonfloodingthatsendsmessagestorandomsetsofneighbor-ingnodes;and(iii)ideal,anidealizedroutingprotuatetheseprotocolsbymeasuringboththeamounNprotocolsdissultshighlighttheadv-1usesnegotiationtosolvetheimplo-sionandoverlapproblems;itreducesenergyconsump-tionbyafactorof3.5comparedtoflooding,-2,whichadditionallyincorporatesathreshold-basedresource-awarenessmechanisminadditiontonego-tiation,disseminates60%moredataperunitenergythanfloodingandinfactcomesvekoperation,,nodesinanetworkmustmonitorandadapttochangesiignoftheSPINprotocolsismotivatedinpartbytheprincipleofApplicationLevelFraming(ALF)[4].WithALF,networkprot,packeti-zationisbestdoneintermsofApplicationDataUnits(ADUs).OneoftheimportantcomponentsofALF-basedprotocolsist,[19]),ALF-likeideasonestepfurtherbyarguingthatroutingdecisionsarealsobestmadeinapplication-controlledandapplication-specificways,usingknowledgeofnotjustnetworktoevethatsuchintegratedapproachestonamingandroutingareattractivetoalargerangeofnetworksituations,ctionpresentstheindividualelementsthatmakeuptheSPINfamilyofprotocolsandpresentstwoSPINprotocolsthatwehavedesigned,SPIN-1andSPIN-2.2.1Meta-DataSensorsusemeemeta-datade-scriptorforsensordata,thenthesizeofinbytesmustbeshorterthanthesizeof,forSPINtobebenefiiecesofactualdataaredistinguishable,-wise,twopiecesoesnotspecifyaformatformeta-data;thisfor-matisapplication-specifisthatcoverdisa-datawouldthenstandfor“allthedatagatheredbysensor”.Acamerasensor,incontrast,mightuseasmeta-data,eeachapplication’smeta-dataformatmaybedifferent,SPINre-liesoneachapplicationtointerpretandsynthesizeitsownmeta-data.2SPIN:desusethreetypesofmessagestocommunicate:First,tooperateefficientlyandtoconserveenergy,sensorADV–PINnodeapplicationsneedtocommunicatewitheachotherabouthasdatatoshare,itcanadvertisethisfactbytrans-thedatathattheyalreadyhagingsensordatamaybeanexpensive3

REQ–AREQDATA–ssagescontainac-tualsensordatawithameta-dataheader.(a)(b)BecauseADVandREQmessagescontainonlymeta-data,theyaresmaller,andcheapertosendandreceive,DAAADVAVADADVB2.3SPINResourcenpolltheirsystemresourcestofinalsocal-culatethecost,intermsofenergy,ofisinformation,SPINno,itspecifiesaninterfacethatapplica-tionscanusetoprobetheiravailableresources.(c)ADV(d)REQDATAABAREQTADABREQ(e)2.4SPINImplemeeforeintendtoimplementSPINasmiddlewareapplicationlibrarieswithawelldefiibrarieswillimplementthebasicSPINmes-sagetypes,messagehandlingroutines,appli3:tartsbyadver-tisingitsdatatonodeB(a).NodeBrespondsbysendingarequesttonodeA(b).Afterreceivingtherequesteddata(c),nodeBthensendsoutadvertisementstoitsneighbors(d),whointurnsendrequestsbacktoB(e,f).2.5SPIN-1:A3-StageHandshakeProtocolTheSPIN-1protocolisasimsinthreestages(ADV-REQ-DATA),thisbysendinganADVmes-sagetoitsneighbors,namingthenewdata(ADVstage).UponreceivinganADV,theneighboringnodechec,itrespondsbysendinganREQmessageforthemissingdatabacktothesender(REQstage).Theprotocolcompleteswhentheinitiatoroftheprotocolre-spondstotheREQwithaDATAmessage,containingthemissingdata(DATAstage).-ceivinganADVpacketfromnodeA,nodeBcheckstoseewhetheritpossessesalloftheadvertiseddata(a).Ifnot,nodeBsendsanREQmessagebacktoA,listingallof4thedatathatitwouldliketoacquire(b).WhennodeAre-ceivestheREQpacket,itretrievestherequesteddataandsendsitbacktonodeBasaDATAmessage(c).NodeB,inturn,sendsADVmessagesadvertisingthenewdataitreceivedfromnodeAtoallofitsneighbors(d).ItdoesnotsendanadvertisementbacktonodeA,odesthensendadvertisementsofthenewdatatoalloftheirneighbors,,ifnodeBhaditsowndata,itcouldaggre-gatethiswiththedataofnodeAandsendadvertisementsoftheaggregateddatatoallofitsneighbors(d).Second,example,oneneighbordoesnotsendanREQpacketbacktonodeB(e).thisprotocolhasbeendesignedforlosslessnet-works,,nodescouldcompenancompensateforlostREQandDATAmessagesbyre-requestingdataitemsthatdonotarrivewithinafiilenetworks,changesinthelocaltopologycantriggerupdatestoanode’sneighborDATA(f)REQDATA

enoticesthatitsneighborlisthaschanged,otocol’deinthenetworkperformslittledecisionmakingwhenitreceivesnewdata,rmore,tthatnoothertopologyinfo,SPIN-1canberuninacompletelyunconfigurednetworkwithasmall,-ond,ifthetopologyofthenetworkchangesfrequently,thesechangesonlyhavetotravelonehopbeforethenodescancontinuerunningthealgorithm.A1(a)B(a)42(a)(a)3CD2.6SPIN-2:SPIN-1withaLow-Energywardsdataontooneneighbor,oldAfternodeDreceivesthedata,itmustforwardthedataTheSPIN-2proergyisplen-tiful,PIN-2nodeobservesthatitsenergyisapproachingalow-energythreshold,ral,anodewillonlyparticipateinastageoftheprotocolifitbelievesthatitcancompleteallthenservativeapproachimpliesthat,ifanodereceivessomenewdata,itonlyinitiatesthethree-stageprotocolifitbelievesithase-larly,ifanodereceivesanadvertisement,itdoesnotsendoutarequestifitdoesnothav-proachdoesnotpreventanodefromreceiving,andthere-foreexpendingenergyon,,however,thesender(B),a,itmakescopiesofthedataandsendsthedatatoallofitsneighbors,untoftimeittakesagroupofnodestoreceivorithmfinishes,orconverges,ngconvergesinrounds,whereisthediameterofthenetwork,be-causeittakesatmoghfloodingexhibitsthesameappealingsimplic-ityasSPIN-1,4:ystep,eachnodeonlyfor-3.2GossipingGossiping[8]isanalternativetotheclassicfl-steadofindiscriminatelyforwardingdatatoallitsneigh-bors,agossipingnodeonlyforwardsdsipingnodereceivesdatafromagivenneighbor,itcanfor4Inthissection,wedescribethethreedisseminationalgo-illustratesthereasonthatgossipingnodesforwarddatDneverforwardedthedatabacktonodeB,erdatatravelstoanodewithhighdegreeinaclassicfloodingnetwork,morecopiesofthedatastart3.1ClassicFloodingflpoint,however,Inclassicflooding,ingavoidsofdataacrossthenetworkstartsbysendingacopyofthissuchercopiesmade,thelower5

particularlyreliablemulticastbothrelyuponcomplicatedprotocolmachinery,muchofwhichmaybeunnecessary(a,c)forthesolvingthespecificproblemofdatadissemina-(a)11(a,c)respects,SPINmayinfactbeviewedasaformofapplication-levelmulticas-BCting,whereinformationaboutboththetopologyanddata(c)ostexistingapproachestoshortest-pathdistri-2(a)butiontreeswouldhavetobemodifiedtoachieveideal(e)1dissemination,wewillconcentrateoncomparingSPINtoDtheresultsofanidealdisseminationprotocol,soutthatwecansimulatetheresultsofanidealdisseminationprotocolusingamodifiedFigure5:veatthissimulationapproachPotentialimplosion,causedbyBandC’scommonneigh-bynoticingthat,ifyoutracedthemessagehistoryofthebor,andoverlap,causedbyAandC’soverlappingdata,SPIN-1protocolinanetwork,theDATAmessagore,tosimulateanidealdissemina-tionprotocol,weruntheSPIN-1protoeandenergycoststhatADVandREQmessagesWhilegossipingdistributesinformationslowly,hesourcesendstoonlyoneofitsneigh-4SensorNetworkSimulationsbors,andthatneighborsendstoonlyoneofitsneigh-bors,thefastestrateatwhichgossipingdistributesdataInordertocomparethedifferentcommunicationap-is1node/,iftherearedatasourcesintheproachesdiscussedintheprevioussections,wedevelopednetwork,gossiping’sfastestpossibledistributionrateisasensornetworksimulatorbyextendingthefunctional-nodes/hissimulationFinally,wenotethat,althoughgossipinglargelyavoidsframework,wecomparedSPIN-1andSPIN-2withclassicimplosion,itdoesnotsolvetheoverlapproblem.fldthatSPIN-1provideshigherthroughputthangossipingandthesameorderofthroughputasflood-3.3IdealDisseminationing,whileatthesametimeusessubstantiallylessenergyFig-2isabletodeliverevensendsobserveddataalongashortest-pathrouteandeverymoredataperunitenergythalamountofdataperunitenergybyadaptingtothecallthisiddthatinallofourarriveateachnodeintheshortestpossibleamountofsimulations,gyiseverwastedtransmittingandreceivingpatemoreenergythannodeswithalowerdegree,ntnetworkingsolutionsoffhapproachisnetwork-levelmulticast,suchasIPmulti-cast[5].Inthisapproach,thenodesinthenetworkbuildandmaintaindistributedsource-specifi-seminateanewpieceofdatatoalltheothernodesinthenetwork,asourcewouldsendthedatatothenetworkmul-ticastgroup,thusensuringthrtohandlelosses,thedisseminationprotocolwouldbemodi-fiunately,multicastand64.1nsImplementationns[14]isanevent-drivennetworksimulatorwithexten-sivesupportforsimulationofTCP,routing,ementtheSPINfamilyofdatadistributionprotocols,odeclasswasextendedtocre-ateaResource-AdaptiveNode,orcomponentsofaResource-AdaptiveNodearetheResources,theResourceManager,theResource-ConstrainedApplication(RCApplication),theResource-

Test Network20RCApplicationMeta-DataDataRCAgentMeta-DataDataResource-AdaptiveNode1510Resource ManagerMeters5Network NeighborEnergy0−5Network InterfaceLinkLinkLink−10−15−20−20−15−10−50Meters5101520Figure6:7:Topologyofthe25-node,ainedAgent(RCAgent)ourceManagerprovidespplication,asubclassofns’sApplicationclass,isresponsibleforupdatingthestatusofthenode’tion,theRCAppli-cationimplementstheSPINcommungentpacketizesthedatageneratedbytheRCAppli-cationandsendthepacketstotheNode’sNetworkInter-facefortransmissiontooneofthenode’sneighbors.4.2SimulationTestbedForourexperiments,twork,whichwasrandomlygeneratedwiththeconstraintthatthegraphbefullycon-nected,has59edges,adegreeof4.7,ahopdiameterof8,erofthesensorradiotransmitterissetsothatanynodewithina10meteriospeed(1Mbps)andthepowerdissipation(600mWintransmitmode,200mWinreceivemode)cessinializedeachnodewith3dataitems,ansthereisoverlapintheinitialdataofdifferentsen-sors,eofeachdataitemwassetto500bytes,andwegaveeachitemadistinct,16byte,hisnetworkconfiguration,weraneachprotocolandtrachexperiment,werantheprotocols10timesandaveragedthedatadistributionNodesEdgesAveragedegreeDiameterAverageshortestpathAntennareachRadiopropagationdelayProcessingdelayRadiospeedTransmitcostReceivecostDatasizeMeta-datasizeNetworklossesQueuingdelays

Total Data Acquired in the Sensor Network10.90.80.7Total

Data

(%)0.60.50.40.30.2IdealSPIN−1FloodingGossiping0.100.511.5Time (s)22.533.5Total Data Acquired in the Sensor Network10.90.80.70.60.50.40.30.20.10per-neighborstate,suchashavingeachnodekeeptrackofthedataithasalreadysenttoeachofitsneighbors,w8showsthatSPIN-1takes80mslongertocon-vergethanflooding,whereasflghitappearsthatSPIN-1performsmuchworsethanfloodinginconver-gencetime,thisincreaseisactuallyaconstantamount,rlongersimulations,terimentalresultsshe-forespeculatedthatthesecurvesmightgenerallybecon-vex,uldpre-dicttheshapeofthesecurves,wemightbeabletogainsomeintuitis,wenotedthattheamountofdatareceivedbyanodeateachroundde-pendsonlyonthenumberofneighborshopsawayfromthisnode,.However,sinceisdifferentforeachnodeandeachdistanceandisentirelydependentonthespecifictopology,wefoundthat,infact,

Data

(%)IdealSPIN−1FloodingGossiping4.3.2EnergyDissipatedOverTimeForthepreviousexperiment,wealsomeasuredtheenergydissipatedbythenetworkovertime,raphsshowthatgossipingagainisthemostcostlyprotocol;itrequiredbefore,addingasmallamountofstatetothego9alsoshowsthatSPIN-1usesapproximatelyafactorof3.5lessenergythanfl,bysacrific-ingasmall,constantoffsetinconvergencetime,-1isabletoachievethislargereductionineneethisadvantageoftheSPIN-1protocolbylookingatthemessageprofilesforthedifferentprotocols,firstthreebarsforeachproto-colshowthenumberofdataitemstransmittedthroughoutthenetwork,thenumberofthesedataitemsthatarere-dundantandthusrepresentwastefultransmission,berofuse-fuldatatransmissionsisthesameforeachprototthreebarsforeachprotocolshowthe800.020.040.060.080.10.12Time (s)0.140.160.180.2Figure8:Percentoftotaldataacquiredinthesystemovertimeforeachprotocol.(a)showstheentiretimescaleuntilalltheprotocolsconverge.(b)showsablow-upofthefirst0.22seconds.4.3.1DataAcquiredOverTimeFigure8showsthr,itisinterestingtonotethatusinggossip-ing,thesystemhasacquiredover85%ofthetotaldatainasmallamountoftime;themajorityofthetimeisspentdistributingthelast15%becauodesobtainalargeamountofdata,thistransmissionwillbecostly,and,sinceitisverylikelythattheneighboralreadyhasalargepro-portionofthedatawhichisbeingtransmitted,pingprotocolwhichkeptsome

Total Energy Dissipated in the Sensor Network50454035Energy

Dissipated

(J)300Data itemssent/receivedRedundant dataitems receivedUseful dataitems receivedMeta-data itemssent/receivedRedundant meta-dataitems receivedUseful meta-dataitems receivedNumber

of

MessagesIdealSPIN−1FloodingGossiping1Ideal00.511.5Time (s)Total Energy Dissipated in the Sensor Network22.533.5SPIN-1ProtocolFloodingGossiping10987Energy

Dissipated

(J)6543210Figure10:MessageprofiPIN−1FloodingGossipingEnergy Dissipated per Node Versus Number of Neighbors43.5IdealSPIN−1FloodingGossiping3slope = 0.40Energy

dissipated00.020.040.060.080.10.12Time (s)0.140.160.180.22.521.51slope = 0.080.5slope = 0.02Figure9:Totalamountofenergydissipatedinthesystemforeachprotocol.(a)showstheentiretimescaleuntilalltheprotocolsconverge.(b)showsablow-upofthefirst0.22seconds.0123456Number of neighbors789Figure11:ofmeta-dataitarshaveaheightzeroforideal,flooding,andgossiping,atthenumberofusefulmeta-datatransmissionsfortheSPIN-1protocolisthreetimesthenumberofusefuldatatransmissions,sinceeachdatatrrmore,77%ofthesedataitemsareredundantforfloodingand96%ofthedataitemsareredundantforgossiping,-1nodesalsosendoutalargenumberofredundantmessages(53%);however,-datamessagescomeatarelativelylowcostandcomewithanimportantbenefit:meta-datanego-tiatedtheaverageenergydissipatedforeachnodeofacertaindegree,figureshowsthatforalltheprotocols,ercussionsofthisfindingisthatifahigh-degreenodehappenstolieuponacriticalpathinthenetwork,evethathandlingsresultsfromtheseunlimitedenergysimula-tionsaresummarizedinTable2.

PerformanceSPIN-1IncreaseinEnergy90msConvergenceTimeSlopeofEnergyNodeDegree%ofTotalDataRedundantProtocolGossiping6.3J3025ms5x77%

Total Energy Dissipated in the Sensor Network1.80.9Total Data Acquired per Amount of Energy1.60.81.40.7IdealSPIN−1SPIN−2FloodingGossiping1.2Energy

Dissipated

(J)0.61Total

Data

(%)0.50.80.40.60.4IdealSPIN−1SPIN−2FloodingGossiping0.30.20.2000.020.040.060.08Time (s)0.10.120.140.160.100.20.40.60.81Energy Dissipated (J)1.21.41.61.8Figure13:Energydissipated14:-2distributes10%moredataperunitenergythanSPIN-1and60%moredataperunitenergythanflthreeprotocols,thelongestpathanypieceofdatawillneedtotraverseisthemaximumshortestpathofthenetwork,orthenetworkdiameter,.nsmissionadatamessageofsizebytesistimeforADVandREQmessagesisnegligiblecompartion,thenetworkimposesafixedmsandarandom[0-],ADV,REQ,orDATA)ansthattheconvergencetimefortheidealandfloodingprotocolsare:(1)Theminimumconvergencetimewouldoccuriftheran-domdelaywasalwayszeroandthemaximumconver-gencain,r,thedelayincurredtogetthe,datafromonenodetothenextwillbesinceeachmessage(ADV,REQ,andDATA)ansSPIN-1hastheconvergencebounds:overlapintheinitialdataofeachnodeandtherearenoqueuingdelays;thereisnochoiceofnetworkparametersforwhichSPIN-1willconvergebeforeflr,thedifferencebetweenconvelysischangesslightlyforthecasewherenwith,thelengthofthelongestpathwhichapieceofdatamusttraversei,thislengthwilldtion,mple,initiallyar,thepiecesofdatanodeBreceivesfromAmightnotallbenew;thereforenodeBwillonlytransmitofthesedatapiecestoitsneighbors,whereisthenum-berofdataitemsthatAseore,thetimetotransmitadatamessageisbetweenand,dependingonthenumberofdataitemsinthemes-sage,sotheconvergenceboundsforfloodingandidealbecome:(2)(3)Therefore,therewillalwaysbeanoffsetofbetweenandbetweentheconvergencetimeofSPIN-1andflooding(orideal)forthecasewhenthereisnoSimilarly,theconvergenceboundsforSPIN-1become:(4)11

Convergence Time versus Link Bandwidth (Non−Overlapping Initial Data)Convergence

Time

(seconds)10.80.60.40.20500600Bandwidth (Kbps)7Convergence

Time

(seconds)Convergence Time versus Processing Delay (Non−Overlapping Initial Data)10.80.60.40.20012345Delay (+ [0−5] ms) (ms)6789IdealSPIN−1FloodingIdealSPIN−1FloodingConvergence Time versus Link Bandwidth (Overlapping Initial Data)Convergence

Time

(seconds)10.80.60.40.20500600Bandwidth (Kbps)7Convergence

Time

(seconds)Convergence Time versus Processing Delay (Overlapping Initial Data)IdealSPIN−1Flooding10.80.60.40.2001IdealSPIN−1Flooding2345Delay (+ [0−5] ms) (ms)6789Figure15:fixedprocessingdelayissetto5msandthedatasizeissetto500bytes.(a)Eachnodebeginswithasinglepieceofuniquedata.(b)16:Convergencetimeasthefikbandwidthissetto1Mbpsandthedatasizeissetto500bytes.(a)Eachnodebeginswithasinglepieceofuniquedata.(b)r,SPIN-1andidealnodeswillbemuchmorelikelytoonlysendasmallnumberofdataitems,ore,theconvergencetimefortheSPIN-1andidealprotocolswillmostoftenbebetweentheupperandlowerbounds,whereastheconvergencetimeforflowerboundofcon-vergenceforSPIN-1ismuchlessthantheupperboundofconvergenceforflooding,thereisanonzeroprobabilitythatSPIN-1willconvergebeforeflcurswhen:ngtheseparametersintoEqns.3and4givethefollowingconvergenceboundsforournetwork:(6)(7)Theexperimentalresultsshowthat,onaverage,flood-ingconvergesin135ms,SPIN-1convergesin215ms,(5)Shortestpathforoverlappinginitialdata(hops)7Randomprocessingdelay(s)5xDatasize(bytes)500Ifeachnodebeginswithpiecesofdatabutthedataareunique,itisthesameasconsideringeachnodestartingwithonepieceofuniquedatathatistimesaslargeasasinglepieceofdataandSPIN-1will

Convergence Time versus Data Size (Non−Overlapping Initial Data)Convergence

Time

(seconds)10.80.60.40.2020002500Data Size (bytes)3IdealSPIN−1FloodingConvergence Time versus Data Size (Overlapping Initial Data)Convergence

Time

(seconds)10.80.60.40.2020002500Data Size (bytes)3IdealSPIN−1FloodingFigure17:Convergenckbandwidthissetto1Mbpsandthefixedprocessingdelayissetto5ms.(a)Eachnodebeginswithasinglepieceofuniquedata.(b)thatthefloodingconvergencetimeisclosetotheupperbound,whereastheSPIN-1convergencetimeisinthemiddleofthetwobounds,asagreeswithourintuitionthatSPIN-1sendslessthandataitemspermessagemoreoftenthanfledbefore,thisincreaseinconvergencetimeisconstantfoeuingdelaysareincorporatedintoournetworktestbed,theconvergencetimeforfltion,weex-pecttheconvergencetimeforfloodingtobeworsethantheconvergencetimeforSPIN-1,evenintheuniqueini-tialdatacase,duetotheextraneoustransmissionscausingqueuingdelaysinaflssnetworks:,[15]).Thelatterstyleisbettersuitedforwirelesssensornetworksthantheformer,giventheadhoc,-cently,mobileadhocroutingprotocolshavebecomeanactiveareaofresearch[3,10,16,18,22].Whilethesepro-tocolssolveimportantproblems,theyareadiffeicular,webelievethatsensornetworkswillbenefitfromapplication-controllednegotiation-baseddisseminationprotocols,gprotocolsbasedonminimum-energyrouting[11,21]andotherpower-friendlyalgorithmshavebeenproposedintheliterature[12].Webelievethatsuchpro-tocolswillbeusefulinwirelesssensornetworks,ossipingandbroadcastingalgorithmstodis-seminateinformationindistributedsystemshasbeenex-tensivelyexploredintheliterature,oftenasepidemical-gorithms[6].In[1,6],gossipingisusedtomaintaindatabaseconsistency,whilein[17],eticalanal-ysisofgossipingispresentedin[8].Recently,suchtech-niqueshavealsobeenusedforresourcediscoveryinnet-works[7].Perhapsclosestinphilosophytothenegotiation-basedapproachofSPINisthepopularNetworkNewsTransferProtocol(NNTP)forUsenetnewsdistributionontheIn-ternet[2].Here,newsserversformneighborhoodsanddisseminatenewinformationbetweeneachother,notethattherehasbeenalotofrecentinterestinusingIPmulticast[5]astheunderlyinginfrastructuretoefficientlyandreliablydisseminatedatafromasourcetomanyreceivers[20]r,forthereasonsdescribedinSection3,webelievethatenablingapplicationstocontrolroutingdecisionsisalesscomplexandbetterapproachforwirelesssensornetworks.6Conclusions5RelatedWorkInthispaper,weintroducedSPIN(SensorProtocolsforInformationviaNegotiation),afamilyofdatadissemina-Perhapsthemostfundamenestocolsinnetworkingisinthecontextofroutingtablemple,nodesinlink-stateprotocolscomeseveraldeficienciesintraditionaldisseminationap-(suchasOSPF[13])eta-datanames,nodesnegotiatewithofthenetworktopologytotheirneighbors,egotia-in[9,23].Suchprotocolscloselymimictheclassicflood-tionsensurethatherearegenerallytwotypesoftopologiesusedinresource-aware,nodesareabletocutbackontheirac-13

discussedthedetailsoftwospecificSPINpro-tocols,-1isa3-stagehand-shakeprotocolfordisseminatingdata,andSPIN-2isavery,wecomparedtheSPIN-1andSPIN-2protocolstoflooding,gossiping,xaminingSPINinthispaper,bothqualitativelyandquantitatively,wearriveatthefollowingconclusions:AcknowledgmentsWearegratefultoWeiShi,whoparticipatedintheini-tialdesignandevaluationofsomeoftheworkinthispa-per,kSuchitraRamanandJohnWroclawskiforseverathankAnanthaChandrakasanforhidatausingmeta-datadescriptorsandnego-tiatingdatatransmissionsusingmeta-datasucce-1andSPIN-2aresimpleprotocolsthateffi-cientlydisseminatedata,rotocolsarewell-suitedforanenvironmentwherethesensorsaremobilebecausesoftime,SPIN-1achievescomparableresultstoclassicfloodingprotocols,andinsomecasesout-performsclassicflsofenergy,SPIN-1usesonlyabout25%asmuchenergyasaclassicfl-2isabletodistribute60%moredataperunitenergythanflfourexperiments,socomeclosetoanidealdissnces[1]AGRAWAL,D.,ABBADI,A.,ANDSTEINKE,.16thACMPrinciplesofDatabaseSystems(May1997).[2]BORMANN,etDraft,IETF,progress.[3]BROCH,J.,MALTZ,D.,JOHNSON,D.,HU,Y.,ANDJETCHEVA,.4thACMInternationalConfer-enceonMobileComputingandNetworking(Mobi-com’98)(Oct.1998).[4]CLARK,D.,ANDTENNENHOUSE,COMM(September1990).[5]DEERING,S.,ANDCHERITON,nsactionsonComputerSystems8,2(May1990).[6]DEMERS,A.,GREENE,D.,HAUSER,C.,IRISH,W.,ANDLARSON,rinci-plesofDistributedComputing(Aug.1987).[7]HARCHOL-BALTER,M.,LEIGHTON,T.,ANDLEWIN,ymposiumonPrinciplesofDis-tributedComputing(May1999).[8]HEDETNIEMI,S.,HEDETNIEMI,S.,ANDLIEST-MAN,ks18(1988).[9]HUITEMA,ceHall,ary,SPINprotocolsholdthepromiseofachievinghighperformanceatalowcostintermsofcom-plexity,energy,computation,ghourinitialworkandresultsarepromising,s-pronenatureofwirelesschannelsneedstobein-corporatedandexperimentedwithinourframework,andwebelievethatthiswillnotbediffidliketodevelopmoresoicular,weareinter-estedindesigningprotocolsthatmakeadaptivedecisionsbasednotonlyonthecostofcommunicatingdata,source-adaptiveap-proachesmayholdthekeytomakingcompute-intensivesensorapplications(suchasbeam-forming)arealityinthefuture.14

[10]JOHNSON,rkshoponMobileCom-putingSystemsandApplications(Dec.1994).[11]KARN,alEffi10thComputerNetworkingConf.(1991).[12]MENG,T.,ANDVOLKAN,SCAS(May1998).[13]MOY,rsion2,1583.[14]:///ns/,1998.[15]PAHLAVAN,K.,ANDLEVESQUE,ley&Sons,Inc.,1995.[16]PARK,V.,ANDCORSON,M’97(Apr.1997).[17]PELC,ks28,3(Oct.1996).[18]PERKINS,C.,ANDBHAGWAT,DynamicDestination-SequencedDistance-VectorRouting(DSDV)m’94ConferenceonCommunicationsArchi-tectures,Protocols,andApplications(Aug.1994).[19]RAMAN,S.,ANDMCCANNE,timedia(Sept.1998).[20]ReliableMulticastResearch/RMRG/,.[21]SHEPARD,-COMM(Aug.1998).[22]SINHA,P.,SIVAKUMAR,R.,ANDBHARGHAVAN,:FOCOM(Mar.1999).[23]STEENSTRUP,ceHall,1995.15