∗
Persistence
AbhinavKamra
ColumbiaUniversityNewYork,USA
kamra@cs.columbia.edu
JonFeldman
GoogleInc.NewYork,USA
jonfeld@google.com
ABSTRACT
Sensornetworksareespeciallyusefulincatastrophicoremergencyscenariossuchasfloods,fires,terroristattacksorearthquakeswherehumanparticipationmaybetoodangerous.However,suchdisas-terscenariosposeaninterestingdesignchallengesincethesensornodesusedtocollectandcommunicatedatamaythemselvesfailsuddenlyandunpredictably,resultinginthelossofvaluabledata.Furthermore,becausethesenetworksareoftenexpectedtobede-ployedinresponsetoadisaster,orbecauseofsuddenconfigurationchangesduetofailure,thesenetworksareoftenexpectedtooper-ateina“zero-configuration”paradigm,wheredatacollectionandtransmissionmustbeinitiatedimmediately,beforethenodeshaveachancetoassessthecurrentnetworktopology.Inthispaper,wedesignandanalyzetechniquestoincrease“persistence”ofsenseddata,sothatdataismorelikelytoreachadatasink,evenasnetworknodesfail.Thisisdonebyreplicatingdatacompactlyatneighbor-ingnodesusingnovel“GrowthCodes”thatincreaseinefficiencyasdataaccumulatesatthesink.WeshowthatGrowthCodespre-servemoredatainthepresenceofnodefailuresthanpreviouslyproposederasureresilienttechniques.
CategoriesandSubjectDescriptors:E.4[CodingandInforma-tionTheory]:Formalmodelsofcommunication
GeneralTerms:Algorithms,Design,Experimentation.Keywords:NetworkResilience,LDPCcodes.
1.INTRODUCTION
Oneofthemotivatingusesofsensornettechnologyisthemon-itoringofemergencyordisasterscenarios,suchasfloods,fires,earthquakes,andlandslides.Sensingnetworksareidealforsuchscenariossinceconventionalsensingmethodsthatinvolvehuman∗CNS-0435168,ThisworkwassupportedinpartbyNSFgrantsfromMicrosoft,ANI-0133829,IntelandCisco.
ITR-0325495andANI-0238299,researchgiftsPermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.
SIGCOMM’06,September11–15,2006,Pisa,Italy.Copyright2006ACM1-59593-308-5/06/0009...$5.00.
VishalMisra
ColumbiaUniversityNewYork,USA
misra@cs.columbia.edu
DanRubenstein
ColumbiaUniversityNewYork,USA
danr@cs.columbia.edu
participationwithinthesensingregionareoftentoodangerous.Thesescenariosofferachallengingdesignenvironmentbecausethenodesusedtocollectandtransmitdatacanfailsuddenlyandunpredictablyastheymaymelt,corrodeorgetsmashed.
Thissudden,unpredictablefailureisespeciallytroublingbecauseofthepotentiallossofdatacollectedbythesensornodes.Often,therateofdatageneratedwithinasensornetworkgreatlyexceedsthecapacityavailabletodeliverthedatatothedatasinks.Withsomanynodestryingtochanneldatatothesinknode,thereiscongestionanddelayintheneighborhoodofthesink.Thisphe-nomenoncanbedescribedasafunnelingeffect[11],wheremuchofthedatatryingtoreachthesinkisstalled.Itisduringthistimethatdataisespeciallyvulnerabletolossifthenodesstoringthedataaredestroyedordisconnectedfromtherestofthenetwork.Evenifstate-of-the-artcompressiontechniquessuchasdistributedsourcecoding[33]orroutingwithre-codingareapplied[8],therecanbeasignificantdelaybetweenthetimeaunitofdataisgeneratedandthetimeatwhichitreachesthesink.Wedefinethepersistenceofasensornetworktobethefractionofdatageneratedwithinthenetworkthateventuallyreachesthesink.
Thegoalofthispaperistoinvestigatetechniquestoincreasethepersistenceofsensornetworks.Toourknowledge,thisisthefirstpaperthatconcernsitselfwiththisparticularproblem.Oursolutionsarebasedontheobservationthateventhoughthereislimitedbandwidthtoforwarddatatowardsthesink,therestillre-mainssufficientbandwidthforneighboringnodestoexchangeandreplicateoneanothers’information.Whilesuchreplicationdoesnotincreasetherateatwhichdatamovestowardthesink,itdoesincreasethelikelihoodthatdatawillsurviveassomeofthestoragepointsfail.
Wefirstfocusonprovidingpersistenceinasensornetworkthatisdeployedtotakea“snapshot”readingofaparticularregion:eachnode’sprimarytaskistotakeasinglereadingandrelaythisread-ingtoasinkwhoseposition(withrespecttothenode)isnotnec-essarilyknown.Thisscenarioislikelyindisastersettingswheregettinganinitialreadingisessential,andnodesmustbe“dumped”intotheregionwithlimitedornoplanningandconfiguration,andwherethetopologymaychangerapidlyduetonodefailures(burn-ingup,gettingcrushed,etc.).Suchnetworkscanbethoughtofas“zero-configuration”,wheredatacollectionandtransmissionmustbeinitiatedimmediately.Hence,nodeshavelittleopportunitytolearnaboutspecificsofthetopologywithinwhichtheyarede-ployed,asidefromsomelimitedinformationdescribingtheirim-mediatesurroundingarea.Globalinformation,suchasthelocation
ordirectionofasink,orthecompletesensornetworktopologyareunknown.Evenifthenodesgettoknowthelocationanddirectionofsink(s)andareabletosetuparoutingtree,nodefailureswillre-sultinfrequentdisruptionsandcausetheroutingsetuptobecomeinvalid.
WedesignanoveldataencodinganddistributiontechniquethatwerefertoasaGrowthCode.Thiscodeisdesignedtoincreasetheamountofinformationthatcanberecoveredatasinknodeatanypointintime,suchthattheinformationthatcanberetrievedfromafailingnetworkisincreased.Thesecodesarealsoeasilyim-plementedinadistributedfashion-anotherimportantcriterionforsensornetworks.Thecodegrowswithtime:initiallycodewordsarejustthesymbolsthemselves,butovertime,thecodewordsbe-comelinearcombinationsof(randomlyselected)growinggroup-ingsofdataunits.Awell-designedcodewillgrowataratesuchthatthesizeofthecodewordreceivedbythesinkisthatwhichismostlikelytobesuccessfullydecodedanddeliverpreviouslyunre-covereddata.
InadistributedsensornetworkwherethenodesemployGrowthCodestoencodeanddistributedata,thesinkreceiveslowcom-plexitycodewordsinthebeginningandcodewordsofhigherandhighercomplexitylateron.Identifyingtheoptimaltransitionpointsatwhichthecodeswitchestohighercomplexitycodewordsisanon-trivialtask.Weprovethatsuchacodewherethecomplexityofcodewordsincreasesmonotonicallyisoptimalinrecoveringthemaximumamountofdataatanytimeprovidedthetransitionpointsarecarefullychosen.
WeformallyanalyzeGrowthCodesandfindcloseupperboundsforthetransitionpoints.Inaperfectsourcesetting,wherethesinkreceivescodewordsthatexactlyfitacertaindesireddegreedistri-bution,wecomparetheperformanceofadegreedistributionbasedonGrowthCodeswithotherwellknowndistributionssuchasSoli-tonandRobustSoliton[18].Furthermore,wesimulatevariousdistributednetworkscenarios(includingsomemimickingdisasterscenarios)toevaluatetheperformanceofGrowthCodes.Wefindthatinallthestudiednetworkscenarios,ifthesensornodesusetheencodingprotocolbasedonGrowthCodes,thesinknodeisabletoreceivenoveldataatleastasfastasanyotherprotocolandinmostcases,isabletorecoverallsymbolsinlessthanhalfthetimecomparedtowhennocodingisused.
Wethenshowhowtoextendgrowthcodestonetworksettingsinwhichnodesmustmakeperiodicmeasurementsoftheexistingregion.Tothisend,weprovidethemainfeaturesofapracticalimplementationofGrowthCodes.Usingthesefeatures,wealsoimplementthesecodesonrealmote-basedsensordevicesandper-formexperimentswhichshowusingGrowthCodesresultsinmuchfasterrecoveryofdistributedsensordata.
Therestofthepaperisorganizedasfollows:Thenextsectiondetailssomepreviousrelatedwork.InSection3,weformulatetheproblemanddescribethenetworksettinginwhichitisemployed.Section4describesthevarioussolutionapproachesincludingthenovelapproachbasedonGrowthCodesandtheencoding/decodingalgorithmsused.InSection5wemathematicallyanalyzetheen-codingprotocolbasedonGrowthCodesandproveinterestingprop-ertiesofthesaidprotocol.WecompareGrowthCodeswithothercodingschemesinaperfectsourcesettinginsection6.InSec-tion7,wedescribethepracticalaspectsofimplementingGrowthCodes.WepresentsimulationandexperimentalresultsinSections8and9tostudytheperformanceofourprotocolinvarioussensornetworksettings.Section10describeshowtohandlesensornodeswhichgeneratedataperiodically.WeconcludeinSection11.
2.RELATEDWORK
Muchofthecodingworkinsensornetworkstargetedtowardsincreasingtheefficiencyofdatatransmissiontosinkpointsuti-lizessourcecoding,whichtakesadvantageofspatialandtemporalcorrelationsindatatocompressthedatatobedelivered.Exam-plesincludesystemslikeTSAR[25]andPRESTO[19]thatusewaveletcompressiontoreducetheoverheadsintransmittingcorre-lateddata.Alocalclusteringschemewhichisnear-optimalacrossarangeofspatialcorrelationsissuggestedin[32]althoughtheyignoretemporalcorrelationsandlossesinthenetwork.
Ourwork,incontrast,canbeviewedasadistributedchannelcodingwherecodingisperformedtomoreeffectivelyrecoverfromstochasticlossesofinformation(inourcase,failingnodes).Mostworkinthisareaisfocusedonefficientlyrecoveringalldata,andformanyoftheschemes,datacannotbepartiallyrecovered.ThecanonicalcodingschemeistheoptimalblockerasureReed-Solomoncodes[17]whichhavebeenadaptedforerasure-resilientdatatrans-fer[21].ThehighcomputationalcostsforencodinganddecodingthesecodeshaspushedresearchinthedirectionofLDPCcodes,suchastheclassofDigitalFountaincodes[16],thatincludeTor-nadocodes[20]andLTcodes[18].Byerset.al.optimizelargetransfersin[14]usingcodesbyhavingthesourcere-codedataasitlearnsfromreceiverswhatinformationtheystillrequire.Considineet.al.[15]proposeaheuristicforgeneratinggooddegreedistribu-tionswhichcanbeusedtoconstructlowcomplexityerasurecodes.Theseschemesnotonlyemphasizetherecoveryofalldata,butarealsocentrallyencoded,andcannotbetriviallyappliedinsettingswherethedataisdistributedtobeginwith.
Distributedencodingschemesthataimtorecoveralldataper-mitnodestore-codedataen-routetothedestinationhavealsobeenshowntobeamoreefficientmeansofcommunication[27].Aparticularareaofrecentinterestistheapplicationofnetworkcod-ingwithinmulticastenvironments(e.g.,[29,9],whereithasbeenshownthatsimplelinearcodesareveryefficient[24].In[31,5],acodingschemeisconstructedtofacilitaterecoveryofpopulardatabyreplicatingcodedversionsofthedataatmultiplenodes.Kattiet.al.[3]proposethatnodesguesswhatdataothernodesalreadyhaveandexploitlocalcodingopportunitiestoreducetheconsumedbandwidth.
Somestudiestrytocombinesourceandchannelcoding.In[23],atechniqueispresentedthatusesLDPCcodesandsourcecodingacrosstwoorthreecorrelatedsourcestoimprovetheenergyeffi-ciencyoftransmissioninasensornetwork.Marcoet.al.[12]ex-plorethetradeoffbetweenefficientSlepian-Wolfcodingandpacketlosses.TheyintroducevariationsintheSlepian-Wolfdistributedcodingtoaddsomeredundancy.
Toourknowledge,theonlyworkthatfocusesonpartialrecoveryisPriorityEncodingTransmission[4]whichprioritizesdataandprovidesreliabledeliveryofhighprioritydataatlowcost,attheexpenseofincreasedoverheadtoalsorecoverlowprioritydata.Drawbacksofthisschemeinasensornetsenvironmentarethehighrecoverycostformuchofthe(lowerpriority)data,andthatthereisnoknownwaytoefficientlydistributetheencodingprocess.DirectedDiffusion[10]usesdynamicallychosenbestpathsandin-networkdataaggregationindistributedsensingenvironmentstoachieveenergyandbandwidthefficiency.
3.PROBLEMSETUP
Ourformulationconsistsofasensornetworkwhosegeneralcon-figurationissimilartothatconsideredinalargebodyofwork.WeconsideranetworkconsistingofNsensornodeswheredatasensedbyanodedescribingpropertiesofitsimmediatesensingregionis
tobeforwardedtoasinkforfurtherprocessing.Therateatwhichthenodesasanaggregategeneratedatamaygreatlyexceedthecommunicationcapacityofthenetworksuchthatforwardingbe-comescongested,anddatamustresidetemporarilyinthenodesbeforebeingdeliveredtothesink.Furthermore,themajorityofthenodescannotdirectlytransmittothesink,andhenceothernodesmustactasintermediateforwardingagentsofdata.Theseinterme-diatenodeshavesomecomputationalpowertomanipulatedataintransit,i.e.,theycancompressorrecodedatatoincreasedeliveryefficiency[34,33].
Therearealsosomespecificstoourformulationthatdistinguishourenvironmentfrommuchpreviouswork.Weareconcernedwithmonitoringdangerousemergencyordisasterareas,suchasearth-quakes,floods,orfires.Often,nodesmustbedeployedquicklyinresponsetotheemergency,preventinganopportunitytostaticallyoptimizethedeployment.Evenifthenetworkisplannedbefore-hand,thedisasteritselfmaysignificantlyalterthenetworkcon-figuration,makingthepre-plannedconfigurationobsolete.Thesespecificstranslatetoourproblemasfollow:
•Ourinitialstudywillassumethateachnodetakesasingleread-ingatasinglepointintime,andthenetworkobjectiveistodeliverasmanyofthesereadingsaspossibletothesinkandasquicklyaspossible.
•Thenetworkis“zero-configuration”,suchthatnodesmustop-erateknowingonlyabouttheirimmediatesensingenvironment:theonlytopologyinformationavailabletoanodeisitssetofneighborswithwhomitcancommunicatedirectly.Thisiseitherbecausethedataisurgentlyneeded,ornodesareexpectedtohaveextremelylimitedlifetimes.Thelatterpropertynotonlyleaveslimitedtimeforthenetworktoconfigure,butalsoinducesrapidvariationintopology,whichwouldlikelyobviateanyconfigurationthatwasconstructedbasedonpreviousobservationsoftopology.
•Ourprimaryconcernisthepersistenceofdata:ourgoalistominimizetheamountofdatalostduetofailuresofnodesastheemergencyprogresses(e.g.,thefirespreads,rockscontinuetobombardanarea,orfloodwaterscontinuetogrow).Traditionalas-sumptions,likepowerconservation[22,26]andoptimizedrouting[7,36]aresecondaryissuesandarenotaddressedindetailinthispaper.
3.1SensorNetworksthatNeedPersistence
28x1x1x1x1In the beginning:Nodes 1 and 3 x31exchanging codewords3x1x3x3x3x38x8x4⊕x3x8⊕x7x1⊕x42Later on:Node 1 xis destroyed: 1⊕x4Symbol xx12⊕x8survives in the 1network3x3x2⊕x8x6⊕x3x4⊕x5Figure1:Localizedviewofthenetwork.Inthebeginning,thenodesexchangedegree1codewords,graduallyincreasingthedegreeovertime.Evenwhenanodefails,itsdatasurvivesintheanothernode’sstorage
Figure1depictsthesensornetworkfromthepointofviewofasinglenodeattwodifferenttimes.EachsensornodeintheN-nodenetworkisarbitrarilyplacedtosenseitsdata,andconnectstoasmallsubsetofnodeswithwhomitcancommunicatedirectly.Therearesinklocationswheredatacanbecollected,butinazero-configurationsetting,theselocationsarealmostalwaysunknowntothesensingnodes.Thearrowsinthefigureindicatethecommu-nicationbetweennodesinanattempttomovethedata,hopefullytowardsasink.Initiallythenodehasonlycopiesofitsowndata,butovertime,itwillalsocontain(encoded)copiesofothernodes’data,suchthatthefailureofanothernode(inthefigure,node1)doesnotnecessarilyresultinthelossofthatnodes’data.
Thetypeofdisasterimposesaspecifictypeoffailureprocessofnodesinthenetwork.Forinstance,inafireorflood,onewouldprobablyexpectnodefailurestobespatiallyandtemporallycorre-lated,whereanodeismorelikelytofailifitsneighborhasrecentlyfailed.Inanearthquakeorrock-storm,thefailureprocessisproba-blybestviewedasasequenceofrandomlyselectedregionsfailingovertime,whereallnodeswithinaregionarewithinclosespatialproximityofoneanotherandfailsimultaneously,withdifferentre-gionsfailingatindependenttimes.
Thefailureofnodesinaregiontranslatestoalossofmemoryintheglobalnetwork,andanyinformationstoredinthesefailedregionsislostunlessitisduplicatedelsewhereorisalreadydeliv-eredtothesink.Datathatisretrievedviatheinformationcollectedatthesinkisreferredtoasrecovereddata.InFigure1,thenodesexchangecodewordsthatconsistoforiginaldataorXOR’dcon-glomeratesoforiginaldata.Lateron,eventhoughanodefails,itsdatasurvivesinthenetwork.
Atahighlevel,ourgoalistotrytofindthebestwaytorepli-cateinformationinthesensornetworktomaximizethequantityofrecovereddataatalltimest,evenasnodesfailinthenetwork.
3.2NetworkDescriptionandAssumptions
Eachnodeisequippedwithsomememoryandprocessingpowersothatthereisroomforreplicationofinformation.The“best”waytoreplicatewilldependonthecapabilitiesofthevariousnodes,aswellasvariouspropertiesofthedata(e.g.,spatialandtemporalcorrelation,priority,presumedaccuracy).Asinknodeabsorbsdataatarateλs,whereλsdependsonthenumberofsensornodestowhichthesinkconnects.Inthenetwork,theneighboringnodescanexchangedataatasecondrateλe.
Sincewearemakingapreliminaryforayintotheproblemofper-sistence,webelieveitismostappropriatetothoroughlyanalyzethebasicdesignofapersistenceprotocolinasomewhatconstraineddesignspace.Ouranalysisanddescriptionoftheprotocolmakesthefollowingassumptionsaboutthesensornetworkingenviron-ment,thoughlaterinthepaper,weextendtheprotocolandshowexperimentswheretheseassumptionsarerelaxed.
•Nodeconfigurationsarehomogeneous:eachnodehasasimilarmemorysizeC.Thedatacollectedateachsensorhasanidenticalstoragesizeofc,andwerefertothissize-cdataunitasasymbol.Hence,anodecanideallystoreuptoC/csymbols.Weassumefornowthatthecodewordsalsorequiresizec1.
•Dataisnotcompressed,andallgenerateddataisofequalim-portance.Thisassumptionignoresthepotentialspatialcorrelationsthatoftenexistamongsenseddata[32,13]aswellasthelikeli-hoodthatsomedatageneratedismoreimportantthanothers(e.g.,atnodesclosertoregionsofanomalousactivity).
1
scribeInpractice,someadditional“header”issueintheSectionsetofsymbols7.
encodedinthecodeword.spaceisnecessaryWeaddresstothisde-4.THEBASICPERSISTENCEPROCEDURE
Havinglaidoutourpreliminarynetworkmodelintheprevioussection,wearenowreadytodescribeourbasicpersistencepro-cedure.Wedividethetimeintorounds.Weemphasizethatthisdivisionismerelytofacilitatethedescriptionandevaluationofourtechniques.ThedescribedtechniquesareeasilyextendedtoanasynchronousenvironmentasweshowinSection7.Ineachround,neighboringnodesexchangeinformation.Sinkpointsattachtoasubsetofnetworknodesandareabletoretrieveafixedamountofinformationineachround.
•Ineveryround,eachnodedecideswhatinformationitmusttransmittoitsneighbor,andhowtheincominginformationfromitsneighboringnodesisstored.•Ineveryround,eachsinkcollectsnewcodewordsymbolsanddecodesthisinformationtoretrievetheoriginaldata.Initially,anodefillsitsmemorywithcopiesofitsowndata.Ineachround,anodehastheopportunitytomoveorreplicatecode-wordsthatexistinitsmemorytoanothernode.Sincethelocationofthesinkisunknown,andsincealldataisofequalimportance,weuseasimplealgorithmwhereanoderandomlychoosesaneighborandarandomcodewordinitsmemoryandexchangesthiscode-wordwithoneofthecodewordsstoredintheselectedneighbor’smemory.Theonlycaveattothisexchangeisthateachnodekeepsacopyofitsoriginaldata(thiscopywillbeusedintheencodingpro-cessdescribedlater).Periodically(perhapsonceeveryMrounds,orperhapsMtimesaround),thesinksamplescodewordsfromnearbynodes.Unlessotherwisespecified,weassumeM=1,i.e.,thatλs=λe.
Toincreasetheefficiencyofdatarecoveryatthesink,nodescanchoosetoencodethedatatobesent.Weconsiderseveralcodingvariants:
Nocoding:Nodessimplyexchangetheoriginalsymbols.Thesinkislikelytoreceivemanyduplicates.InthewellstudiedCouponCollectors’Problem[30],ithasbeenshownthatiftheNoriginalsymbolsaregenerateduniformlyrandomly,thesinkneedstore-ceiveapproximatelyO(NlogN)symbolstorecoverallNoriginalsymbols.
RandomLinearcodes[35]:Here,theNoriginalsymbolsareassumedtobeelementsofsomefinitefieldandeachcodewordisalinearcombinationofallNsymbols,withthecoefficientsalsobeingmembersofthesamefinitefield.However,theencod-ing/decodingcomputationalcomplexityofthesecodesisveryhighandhence,asmentionedinSection2,theyareimpracticalinoursensornetworksetting.
Erasurecodes:Nodescanstoreandexchangecodewordsym-bolsformedusingerasurecodes.Thesecaneitherbeoptimalera-surecodessuchasReed-Solomon[17]orerasurecodesbasedonsparsebipartitegraphssuchasTornado[20]orLTcodes[18]whichtradeefficiencyofthecodeforfastencoding/decodingtime.Con-sideringthelowcomputationalpowerthatsensornodeshaveandthelimitedtimetheywillhaveavailabletoperformtheencoding,onlycodeslikeLTCodeswhichhavefastencoding/decodingalgo-rithmsarepracticalinourscenario.
EachcodewordisanXORofasubsetoftheNoriginalsymbols.ThenumberofsymbolswhichareXOR’dtogetherisreferredtoasthedegreeofthecodeword.Thesecodeschoosethedegreeofeachcodewordtofitapre-determineddegreedistributionπwhichisaprobabilitydistributionoverthedegreeslengths.
AsimpleXORencoderbasedonthedegreedistributionπworksasfollows:
1.Chooseadegreed,whered=iwithprobabilityπi.
2.RandomlychooseddistinctsymbolsoutoftheNsymbolsx1,...,xN.ConstructthecodewordsymbolbyXOR-ingthedsymbols.IthasbeenshownthatifthesinkreceivesanexpectednumberoflittlemorethanNsuchencodedsymbols,itcandecodealloftheNoriginalsymbolswithhighprobability.OneofthesimpledegreedistributionsusedinLTcodesistheSolitondistribution[18]whichrequiresthesinktoreceiveexactlyNcodewordstorecoverallNsymbols.Unfortunately,thisdistributionhasahighvariancewhichmeansthatthereisanon-negligibleprobabilitythatthesinkwillneedmanymorecodewordsinpractice.RobustSolitonisamodifiedformofSolitondistributionandperformsmuchbetterinpractice.Weemphasizetwodrawbacksinapplyingthesecodestoourdomainhere:
•Itisnotstraightforwardtoimplementtheencodingprocessinadistributedsettingsuchthattheappropriatedegreedistributionisobtained.
•Thesecodesarenotdesignedtomaximizetheamountofinfor-mationrecoveredbythesinkwhenonlyasmallnumberofcode-wordsarereceived,butareattemptingtominimizethenumberofcodewordsneededtoretrievealldata.WewillshowthatGrowthCodesout-performtheirSolitoncounterpartsinthisaspect.
4.1GrowthCodes
x1In the beginning:Sinkx3Recovered Symbolsx5⊕x8Later on:
Sinkx2⊕x3Recovered Symbolsx1xx53Figure2:GrowthCodesinaction:Thesinkreceiveslowdegreecodewordsinthebeginningandhigherandhigherdegreelateron
GrowthCodesisalinearcodingtechniquethatencodesinfor-mationviaacompletelydistributedprocess.ThetechniquenotonlyensuresthatthesinkisabletorecoverallNofthedatafromonlyalittlemorethanNcodewordsymbols,butalsothatdataisefficientlyrecoveredwhenonlyasmallnumberofcodewordsisreceived.
WemotivatethedevelopmentofGrowthCodesusingthefollow-ingtoyproblem.Considerasinkthatisattemptingtocollectdataoveraseriesofrounds.ThedatacanbeXOR’dtogethertogener-atefixed-sizecodewords.Supposethesinkcanselectthedegree2ofthearrivingcodeword,butthesetofsymbolsthatformthecode-wordareselecteduniformlyatrandom.Alsosupposethesink’sgoalatanytimeistomaximizetheexpectednumberofsymbolsithasrecoveredbythattime.Atanytimet,giventhecollectionofcodewordsthesinkhasalreadyreceived,whatshouldthesinkchooseasthedegreeofthenextarrivingcodeword?
Clearly,forthefirstcodeword,thedegreeshouldbeone.Suchacodewordwillproduceonesymbolwhereasanycodewordof2
XOR’dOnceagain,togetherthetodegreeformtheofacodeword
codewordisthenumberofsymbolshigherdegreewillproducenosymbols.Ifthetotalnumberofsym-bolsNislarge,thenthesinkwillalsodowelltorequestthatitssecondreceivedcodewordbeofdegreeone.Ifthesinkcontin-uestorequestcodewordsofdegreeone,eventuallyapointwillbereachedwhereacodewordofhigherdegreewillverylikelybede-codablegiventheinformationreceived,andanothercodewordofdegreeonewillverylikelycontaindatathathasalreadybeenre-ceived.Itisnothardtofollowthislogicthroughtoseethatasmorecodewordsarereceived,the“best”degreeforthenextcode-wordcontinuestogrow.Wewillexplorethisphenomenonmoreformallyinthenextsection.
Figure2depictstheworkingoftheGrowthCodesprotocol.Thesinknodereceiveslowdegreesymbolsinthebeginningfromwhichitisabletoimmediatelyrecoverdata.Lateron,thesinkreceivedhigherdegreesymbolswhicharemoreefficientinrecoveringmoredata.
Inacompletelydistributedsensornetworksettingsuchasours,wherethenodeshavelimitedstorageandmeagercomputationalresources,asuitableencodingprotocolisonewhichiseasilyim-plementablebythenodesandwhichisalsoefficientintermsofthenumberofsymbolsthatcanberecoveredbythesinkforagivennumberofreceivedcodewords.
GrowthCodesarenovelinthatthecodewordsusedtoencodeafixedsetofdatachangeovertime.Codewordsinthenetworkstartwithdegreeoneand“grow”overtimeastheytravelthroughthenetworken-routetothesink.Thisresultsisthethesinkreceivingcodewordswhosedegreegrowswithtime.Usingsuchadesign,ifthenetworkisdamagedatanytimeandthesinkisnotabletoreceiveanyfurtherinformation,itcanstillrecoverasubstantialnumberoforiginalsymbolsfromthereceivedcodewords.
Inordertofacilitateformalspecificationoftheprocedureforen-codinganddecodingGrowthCodes,wemustfirstintroducesometerminologywewilluse:
DEFINITION4.1.GivenasetXoforiginalsymbolsandacode-wordsymbolsofdegreed,thedistanceofsfromsetX,dist(s,X),isthenumberofsymbolsoutofthedsymbolsXOR’dtogethertoforms,whicharenotpresentinX.
Thedecoder,D,thatweuseforourGrowthCodes(tobeimple-mentedatthesink)willperformitsdecodinginanidenticalfash-iontowhatistraditionallyusedinallSparseBipartitegraph-basedcodingschemessuchasLTCodesandTornadoCodes.Thiswillal-lowustofairlycomparetheperformanceofGrowthCodestopriorcodingschemes:
•LetAbethesetofcodewordsreceivedandXbethesetofsymbolsalreadydecoded(whereXisinitially0).
•Ifthereexistsanycodewordsforwhichdist(s,X)=1,thendecodethemissingsymbolencodedins(byXOR’ingswiththesymbolsinXthatwereusedtogenerates),andaddthatsymboltoX.
ThedecodingprocessusedbythesinkisanonlineversionofdecoderDsuchthatthecodewordsaredecodedon-the-flyastheyarereceivedandthecodewordswhichcannotbedecodedatthemomentarestoredforlateruse.Wenotethatsymbolswhosedis-tanceisgreaterthan1fromXcouldpotentiallybecombinedtoextractdatasymbolsusingsophisticatedbutmorecomputationallyexpensivetechniques(e.g.,gaussianelimination).
Asequenceofincreasingvalues,K1,...,KNarehard-codedintothenodespriortotheirdeployment.ThevalueofKiindicatesthepointintime(i.e.,thenumberofroundsafterthedatawasgen-erated)wheresuchdatashouldbeencodedincodewordsofdegreenolessthani.IfaftertimeKi,acodewordofdegreesmallerthaniistobeexchangedwithaneighbor,thesendingnodewillXOR
thecodewordwithitsowndatasymbolpriortoexchangingit.Incasethecodewordalreadycontainsthedatasymbolofthesendingnode,nothingisdoneandthecodewordisexchangedasis.Even-tually,afterbeingexchangedfromnodetonode,thecodewordwillbeexchangedbyanodewhosedatasymbolisnotcontainedinthecodeword.Then,thatdatasymbolcanbeXOR’dintothecodewordanditsdegreeincreased.
5.
GROWTHCODESFORDISTRIBUTEDENCODINGANDONLINEDECODING
InthissectionweprovesomebasicpropertiesofGrowthCodeswhicharecriticalinfindinggoodvaluesforthedegreetransitionpoints,{Ki},thepointsintimewherethecodeshouldincreaseindegree.The“best”timeforanetworkdependsnotonlyonthewaythecodersareimplemented,butalsoonthetopologyofthenetwork.Sincewearedesigningcodesforazero-configurationnetwork,topologyinformationisnotavailable.Hence,ourcodeswillbedesignedundertheassumptionthatwhenthesinkreceivesacodewordofdegreed,thedatacontainedinthatcodewordisuniformlydrawnatrandom.Ifthesensornetworkperformsagood“mixing”ofdatapriortothedatareachingthesink,thisassumptionisnotunreasonable.
Solvingfortheoptimaltransitionpointsisnon-trivialforthede-coderDdescribedintheprevioussection.Thedifficultyisthatthedecodermaintainsamemoryofpreviouslyreceivedcodewordsthatcouldnotbeusedatthetimeoftheirarrival,butcanbeusedlateronasfurthercodewordsarriveandadditionaldatasymbolsarede-coded.Fortractabilityoftheanalysis,wewillconsiderarestricteddecoderthatthrowsawayanycodewordsitreceiveswhichcannotbedecodedimmediately,anddoesnotmaintainthemforlateruse.Duetolackofspace,alltheproofsareomittedbutareavailableinourtechnicalreport[6].
5.1RestrictedDecoder
Wedefineadecodingalgorithmthatislesspowerfulthande-coderD.Onemightneverusethisdecoderinpractice,butitisusedheresinceitissimplertoanalyzeandwillhelpusproveboundsonthetransitiontimesKiofGrowthCodes.
Adecoderisfedasequenceofsymbols,s1,s2,...,sk.Foradecoderα,wedefineα(s1,s2,...,sk)tobethenumberofsym-bolsthatαcandecodewhenfedthesequences1,s2,...,skinthatorder.
DEFINITION5.1.DecoderS,givenafixedsequenceofcode-wordsymbolss1,s2,...,sk,worksasfollows:InitiallythesetXofrecoveredsymbolsisempty.1.Leti=0.
2.Fromtheremainingsymbols,choosesymbolsiofthelowestdegree.Ifdist(si,X)=1,decodeanewsymbolandaddtosetX.3.Ifdist(si,X)=0ORdist(si,X)>1,throwsiasunus-able.4.Incrementiandgotostep2.Repeatuntilallsymbolshavebeenconsidered.DecoderSismoreconstrainedthandecoderD:Sconsiderscode-wordsinafixedorderonlyandthrowsawayallcodewordswhichcannotbedecodedimmediately(butcouldbeofusetoDatalaterpointinthedecodingprocess).Moreformally,thiscanbestatedasfollows:
LEMMA5.2.Givenasequenceofsymbolsσ=s1,s2,...,sandareorderingofthesesamesymbolsσ=s1,s
k,
D(s1,s2,...,sk)≥S(s1,s2,...,s
2,...,sk.Then
k)foranysequenceσandanyreorderingσofthatsequence.
DecoderSworksonasequenceofsymbolssortedinnon-decreasingorderoftheirdegrees.OnecanalsoviewSasadecoderoper-atinginanenvironmentwherecodewordsarriveintheorderofnon-decreasingdegree.
5.2
Findingcoderthebest-degreecodewordsforde-S
LetusconsiderourdecoderSwhichdoesnotmaintainprevi-ouslyreceivedcodewords.Whenattemptingtodecode,itcanonlyutilizethedatathatithasreceivedpreviouslyandthenextarriv-ingcodeword.Thefollowinglemmasaddressthe“best”degreethatthenextcodewordshouldhaveasafunctionofthenumberofalready-decodeddatasymbols.
LEMMA5.3.Letρr,dbetheprobabilityofsuccessfullydecod-ingrandomlychosenadegreedsymbolreadybeenrecovered.Thenρr,d=(r
whenrsymbolshaveal-d−1)(N−r)(N.d)LetRirepresentthenumberofsymbolsrecoveredbyasinkwhencodewordsofsizegreaterthaniprovideagreaterlikelihoodforprovidingrecoverythanthoseofdegreelessthani.Wewillshowthat,fordecoderS,
R1=
N−12,...,RiN−1
i=i+1
∀i∈[1,N−1].(1)
LEMMA5.4.ρr,i≥ρr,i+1aslongasr≤Ri=
iN−1
i+1Theaboveresultvalidatesourearlierintuitionthatwhenthenumberofrecoveredsymbolsissmall,lowdegreecodewordsarebetterandasthenumberofrecoveredsymbolsincreases,higherdegreecodewordsarebetter.
TheresultprovesthatbeforeR1=N−1
2symbolshavebeenrecovered,degree1codewordsarethemostuseful.AfterthatuntilR2symbolshavebeenrecovered,degree2codewordsarethemostusefulandsoitgoes.
LEMMA5.5.Ifρr,i<ρr,jforsomei Thisresultbasicallystatesthatoncedegreejcodewordshavebecomemoreusefulthanlowerdegreecodewords,theywillre-mainsoevenwhenmoresymbolsarerecovered.ThismonotonicitypropertyisessentialforGrowthCodeswhichstartwithlowdegreecodewordsandswitchtohigherandhigherdegreecodewordswithtime. 5.3PropertiesofDecoderD Nowweconsidersomepropertiesoftheofflineversionofde-coderD,whichcanthenbeappliedtotheonlineversionofdecoder DtohelpdesignGrowthCodes. THEOREM5.6.WhenusingdecoderDtorecoversuchthatr≤R1=N−1 rsymbols, ,theoptimaldegreedistributionhas symbolsofonlydegree1. 2 THEOREM5.7.WhenusingdecoderDtorecoverRN−1 1= dataunits,theexpectednumberofencodedsymbolsrequired2 is RKX1−1 1=N . i=0 N−iTheorems5.6and5.7showthatifmostofthenetworknodesfailandasmallamountofthedatasurvives,thennotusinganycodingisthebestwaytorecovermaximumnumberofdataunits.WegeneralizetheseproofsinTheorems5.8and5.9. jNTHEOREM−1 5.8.Torecoverrsymbolssuchthatr≤Rj=,theoptimaldegreedistributionhassymbolsofdegreenolargerj+1 thanjLet Rj−1 Kj=KX Nj−1+ ij i=R(j−1) j−1 (N−i) (2) THEOREM5.9.TorecoverRjN−1 j=j+1 symbols,atmostKj symbolsarerequiredinexpectation 5.4 ACodes NewDegreeDistributionbasedonGrowthAccordingtotheanalysisinsection5.3,weobservethatitisbesttouseonlydegree1symbolstorecoverthefirstR1sym-bols,onlydegree2symbolstorecoverthenextR2−R1symbolsandsoon.Furthermore,anexpectednumberofK1encodedsym-bolsarerequiredtorecoverR1symbols,anexpectedmaximumK2codewords(recallthatK1istheexactexpectednumberwhile{Ki,i>1}areupperboundsontheexpectednumberofcode-wordsrequired)arerequiredtorecoverR2symbolsandsoon.Thissuggestsanaturalprobabilitydistributiononthedegreesoftheencodedsymbols.Inparticular,ifweneedtoconstructatotalofkencodedsymbols,weshouldhaveK1degree1symbolssothatwecanrecoveranexpectedR1symbolsfromthem,K2−K1degree2symbolssothatwecanrecoveranexpectedR2−R1symbolsfromthemandsoonaslongastheksymbolsarenotyetreceived.Adegreedistributioncanthusbedefinedas π¯∗(k):π∗ Ki−Ki−1k−Ki−i=max(0,min( k,1 k ))(3)WecallthistheGrowthCodesdegreedistribution. IntheencodinganddataexchangeprotocolbasedonGrowthCodes,sensornodescanconstructcodewordsthatfitthedesireddegreedistributionπ¯∗(k).BychoosingthedegreetransitionpointsasK1,K2,...etc,thenodesgeneratecodewordsaccordingtothedistributionπ¯∗(k)wherekvarieswithtime.Ifasinknodereceives1codewordperround,itwillreceivedegree1codewordsforthefirstK1rounds,followedbydegree2codewordsuntilroundK2andsoon.Iftherearemultiplesinknodesandtheyreceivemanycodewordsperround,thenjustbyscalingthevaluesofKi,thedesiredeffectcanstillbeeasilyachieved. 6. PERFECTSOURCESIMULATION MODEL GrowthCodesdegreedistributionasdefinedinEquation3growsmonotonicallyincomplexitywithtimeandhencegivesitselfnicelytoanimplementationinadistributedenvironment(wherethesourcedataisdistributedtobeginwith)asdescribedinSection4.1.ItisdifficulttocompareGrowthCodeswithotherwellknowndegreedistributionssuchasSolitonsinceitisnotclearhowthesedistri-butionscanbeimplementedinadistributedscenario.Thedatasymbolsareinherentlydistributedtobeginwithanditisimpossi-bletogenerateatrulyrandomcodewordofaspecificdegreeunlessallsymbolsarefirstaggregatedatasinglenode.Thisproblemis Average Output of various degree distributions 1000 800derevocer 600 slobmys ega 400 revA 200 No Coding Robust SolitonSoliton 0 Theoretical Upper Bound Growth Codes 0 500 1000 1500 2000 2500 3000 Number of codewords used Figure3:Comparingtheperformanceofvariousdegreedistri-butionsinaperfectsourcesetting.Nischosentobe1000 bypassedintheGrowthCodesprotocolbygraduallyincreasingthedegreesofcodewordsgeneratedinacompletelydistributedman-ner. Forsakeofcomparison,letusassumeitispossibletoimplementanydegreedistributioninadistributedsettingsothatthesinkre-ceivescodewordsexactlyfollowingthisdistribution.Wenoweval-uatehowtheGrowthCodesdegreedistributioncomparestootherwellknowdegreedistributionsinsuchascenario.Wecallthistheperfectsourcesimulationmodelsincewegeneratecodewordsac-cordingtoaspecificdegreedistributionandassumethatallthesecodewordsarereceivedatthesink. Wehavethefollowingscenario:Thereisonesourceandonesink.Thesourcehasallsymbolsx1,...,xN.Itconstructscode-wordsaccordingtosomedegreedistributionπ,i.e.,acodewordofdegreedisconstructedwithprobabilityπdandeverycodewordofdegreedwithuniformprobability.Thesinkreceivesthecodewordsonebyoneanddecodesthemonthefly.Ifthesinkcannotdecodeacodewordatanytime,itisstoredforlaterusewhenmoresymbolshavebeenrecovered.NotethattheGrowthCodesdegreedistribu-tionasdefinedinEquation3changeswithtime,sothathigherandhigherdegreecodewordsaregeneratedastimegoeson.Wewanttoevaluatehowmuchdatacanberecoveredbythesinkforagivennumberofreceivedcodewords.ThesinkusestheonlineversionofdecoderDasdescribedinSection4.1torecoverdataonthefly.WecomparewiththeSolitonandRobustSolitondistributionswherethevaluesofRobustSolitonparameterscandδarechosentobe0.9and0.1respectivelyassuggestedbytheauthorsin[18].Toassesstheadvantageofusingcodingifatall,wecomparewithanocodingschemewhereeachcodewordisarandomlyselecteddegree1symbol. Figure3depictsthenumberofsymbolsrecoveredatthesinkforanygivennumberofcodewordsreceivedaccordingtothecorre-spondingdegreedistribution.Theresultsarefromameanof100simulationruns.Thetopmostcurveplotsthetheoreticalboundonthemaximumnumberofsymbolsthatcouldberecoveredbythatpointintime(i.e.,themin(k,N))wherekisthenumberofcode-wordsreceivedatanypoint. Ifnocodingisused,thesinkisabletodecodeasubstantialnum-berofsymbolsinthebeginning.Asmoresymbolsarerecovered,theCouponCollector’seffectkicksinandthenocodingisnotasgoodanymore.SolitonandRobustSolitonaccumulatealotofhighdegreecodewordswhichcannotbedecodeduntilasubstan-tialnumberofsymbolshavebeenrecovered.Thisiswhywesee asuddenjumpinthecurveforRobustSoliton.Formaximumdatarecoveryatanytime,itiseasytoseethatGrowthCodesperformthebest. 7. PRACTICALIMPLEMENTATIONOFGROWTHCODES Uptonow,wehavemadesomeratherstrongassumptionsaboutthesensingnetworkenvironmenttofacilitatethepresentationandevaluationofGrowthCodes.Here,weaddressseveralofthelimi-tations 7.1Removingthenotionofa“round” OurpreviousdescriptionofGrowthCodesrequirednodestoex-changeinformationoveraseriesofrounds.Thereis,however,noexplicitneedforsynchronizingmultipleexchanges.Allthatisnec-essaryisthatthedegreedistribution“grows”atapproximatelytherightrate.Therateatwhichthecodesgrow(especiallyinitially)isslowenoughthatevenifthetimeatwhichnodesinitialize(i.e.,sensetheirdataandattempttoexchangedatawithothernodes)varies,weexpectlittlevariationintheresults.OurTOSSIM-basedsimulationsandexperimentsdemonstratethisclaim. 7.2CoefficientOverhead 1id1logN bitsFigure4:StructureofacoefficientwhennocodingisusedAsalludedtoearlier,eachcodeword,regardlessofwhetheritcontainsoriginal(degreeone)symbolsorabonafideXORoforig-inalsymbols,mustincludeacoefficientthatdescibesthesymbolsfromwhichitisformed.WeassumethateachsensornodehasauniqueID,andthatitprependsthisIDtoitssymbol.AcodewordofdegreeimustthereforecontainioftheseIDsforthedecoder(sink)toknowhowtodecodethepacket. m bytes0degreeid1id2id37 bitslogN bits(a) d log(N) < N 1001011000100017 bitsN bits(b) d log(N) ≥N Figure5:Structureofacoefficientwithmultipledegreecode-words •Nocoding:Whennocodingisused,eachcodewordisal-waysdegree1.AsshowninFigure4,onlyasingleIDisnecessarytospecifythecoefficient.Thefirstbitisalways1andthelastlog(N)bitsspecifywhichsymbolmakesupthedegree1codeword. •WithCoding:Whencodewordscanbemorethandegree1,theycanbespecifiedintwoways:inabitformatandinlog(N)format.Thefirstbytespecifieshowtheremainingbytesareconstructed.Thefirstbitofthefirstbyteis1ifthecoefficientisspecifiedinlog(N)formatand0whenitisspecifiedinthebitformat. Whenthedegreedofacodewordislow(inparticular,thanN less log(N)),lessspaceisconsumedbylistingtheIDsofthedsymbolsthatmakeupacodeword.Inthiscase,thecoef-ficientisconstructedintheformatasshowninFigure5(a).Thedsymbolidentifierseachofsizelog(N)arepackedintoasfewbytesaspossible. Whenthedegreeishigh(higherthanN log(N)),lessspaceisconsumedbyreservingabitforeachoftheNpossiblesym-bolsthatformacodeword.AsshowninFigure5(b),a1bitsignifiesthepresenceofaparticularcomponentand0speci-fiestheabsence. Ifthesizeofasymbolislarge,thentheseoverheadsarenegligi-ble.However,theyareclearlylessnegligiblewhenthedatasizesaresmall.However,wenotethatGrowthCodesgrowslowly,andthedegreeofthecodewordis,forthemajorityofthetime,fairlysmall.InSection10,whenweconsiderhowtoforwardfromnodesthatgeneratedataperiodically,wewilldemonstratehowtofurtherreducetheamortizedcostofthesecoefficients. 8.EXPERIMENTSONAGRIDNETWORK 18Growth Codes 15 node simulation in 5x3 gridC Simulator with 15 nodes in 5x3 grid 16Growth Codes on micaz motes with 15 nodes in 5x3 gridRouting with 15 nodes in 5x3 grid 14 12derevoc 10eR slob 8myS 6 4 2 0 0 20 40 60 80 100 120 140Time (seconds) Figure6:Datarecoveryona5x3gridnetwork.Thesinknodeisinthemiddleofthegrid Inthissection,weintroduceaC-simulatorthatwewrotetoeval-uatetheperformanceofthevariouscodingschemes.Inaddition,weuseTinyOS[2]andtheaccompanyingsimulatorTOSSIMtosimulateanetworkofnodeswithourimplementationoftheGrowthCodesprotocol.Finally,weusemicazmotesfromCrossbow[1]totesttheprotocolinarealsetting.Wealsoperformexperimentstocomparewithrouting,weuseMultiHopRouter,aroutingproto-colincludedinTinyOSformote-basedsensornetworks.Wemod-ifytheSurgeapplication(whichusesMultihopRoutertosetupandmaintainaforwardingtree)tosimulateanetworkofnodeswhichusethisforwardingtreetoroutedatatowardsthesinknode. BecausenodistributedencodingschemesexistfortheSolitondistributions,wecanonlycomparehowGrowthCodesachievefasterdatadisseminationtothesinknode(s)comparedtowhennocodingisusedinthenetwork. 30 Growth Codes 25 node simulation in 5x5 gridRouting with 25 nodes in 5x5 grid 25 20 derevoceR 15 slobmyS 10 5 0 0 100 200 300 400 500 600 700 800 Time (seconds) Figure7:Datarecoveryintheeventofnodefailuresona5x5gridnetwork.Thesinknodeisinthemiddleofthegrid Ourpurposeinpresentingtheresultsoftheexperimentsandsim-ulationsistwofold.Firstly,wedemonstratethatrelaxingsomeoftheassumptionsofourabstractmodeldoesnotresultinadegra-dationofperformance.Indeed,thesimulationresultsofourroundbasedC-simulatorwiththemodelingabstractionspresentmatchcloselywiththeresultsobtainedwithTOSSIMandthemotesex-periment.Thus,introducingrealdevices,aMACprotocolandnodeswithlimitedmemoryandcomputationalpowerdoesnotdis-tortthebiggerpictureoftheperformanceofGrowthCodes.AfterestablishingthefidelityofourCsimulator,weemployittoper-formlargersimulationsinlatersections,wherewearenotlimitedbythesizeofourphysicaltestbedorthevagariesoftheTOSSIMsimulator.Secondly,ourclaimsonthebenefitsofGrowthCodesinazero-configurationsettingaresubstantiated. InFigure6,weseehowthevariousschemescompare.Thenet-workconsistsof15nodesarrangedina5x3gridtopology.Theradiorangeissetsuchthatanodecancommunicateonlywithitsx-andy-axisneighbors(andnotdiagonally).Themiddlenodeonthegridisthesink.UsingGrowthCodes,eachnodessendsoneofitscodewordsymbolstoarandomneighborevery1second.WeobservethatboththeTOSSIMandtheCsimulatoraswellasthemicazmotesareabletotransmitalldatatothesinkinabout40sec-onds.Withmultihoprouting,eachnodesendsitsdatatowardsthesinkevery1second,butittakesawhilefortheforwardingtreetobeestablished.Ifthenext-hopforanodehasnotbeenestablished,thenodebroadcastsitsdata.Weobservethatthesinkreceivesdatafromit4neighborsfairlyquicklybutafterthatthereisahugelagduringwhichtimetheroutingisbeingsetup.Thismaybeanar-tifactoftheparticularimplementationofMultiHopRouterusedinTinyOS,butsincethisistheonlysuitableroutingprotocolavailableonTinyOSweuseitforcomparisonpurposes.WeaimtocomparewithbetterroutingprotocolsavailableontheTinyOSplatforminfuture. WenowlookathownodefailuresaffectdatarecoveryandhowGrowthCodescanrecoverfromthem.Weusea5x5gridtopol-ogyandassumethatnodesgeneratenewdataevery300seconds.Usingrouting,aftertheforwardingtreehasbeenestablished,thenodescangettheirdataacrossveryquickly.Lateron,att=600seconds,whennewdataisgeneratedoneofthenodesclosetothesinkfails.Att=650,threemorenodeswhichwereroutingthroughthealreadyfailednodealsofailbeforetheyhaveachancetore-establishtheirpathstothesink.ThisresultsintheirdataneverreachingthesinkandascanbeobservedfromFigure7,thecurve neverreachesthemaximumdatarecoveryof25.Ontheotherhand,theGrowthCodesallowsdatatoberecoveredfromthethreenodesmentionedabovebydisseminatingtheirdatatootherneighboringnodes.Whiletheexperimentisdesignedtohighlighttheadvan-tageofGrowthCodes,suchscenariosarelikelytobecommoninlargesensornetworkswherenodesfailwithafairdegreeofregular-ity.GrowthCodesperformwellwithminimalrelianceontransientcomponents,e.g.,optimizedroutes,thattakealongtimetorecom-puteoncebroken.Itisthisabilitythatmakesthemparticularlywellsuitedforlarge-scalesensornetworks. Notethatintheaboveexperiments,weorganizemicazmotesintoagridtopologybyalgorithmicmeans,i.e.bymodifyingtheimplementationsothateachnodeisawareofandcancommunicatewithonlythenodesadjacenttoitinthegridtopology.Nodesphys-icallyarrangedinagridformationstillshowerraticradioconnec-tivityandhenceitisdifficulttoimposeagridtopologybymeansofphysicalplacementalone. 9. GROWTHCODESINADISTRIBUTEDSETTING Inthefollowingsections,welookathowfastGrowthCodescanhelpthesinkrecoverdatainacompletelydistributedenvironment.Weevaluatetheefficacyofthecodingtechniquebothasafunc-tionoftheunderlyingtopologyandasafunctionofthesizeofsetoffailednodes.Wecomparewitharandom“diffusion”schemewherenodesrandomlyexchangedatawiththeirneighborsjustasinGrowthCodesbutnocodingisused. InallsimulationsweusetheroundbasedCsimulatorandun-lessotherwisestated,weassumethatasensornodehasastoragecapacityC=10,i.e.,thenodecanstoreupto10codewordsym-bolsatanygiventime.Witheachnode,havingastoragememoryofC=10,amaximumof10Ncodewordscanbestoredinthenetworkatanytime.Thisissufficienttofacilitategoodspreadandmixingofsymbolsgeneratedbythenodes.Wealsoperformedsim-ulationswithlargervaluesofC,buttheresultswerenotnoticeablydifferentfromwhatispresentedbelow. 9.1GrowthCodesinaRandomTopology Data Persistence in a Sensor Networkwith Random Topology (N = 500) 1 0.8derevocer s 0.6 lobmys fo no 0.4 itcarF 0.2 Growth Codes, Random Network(R=0.3) No Coding, Random Network(R=0.3) 0 Growth Codes, Clique Network 0 200 400 600 800 1000 Time (=number of codewords received at the sink) Figure8:Datarecoveredatthesinkina500noderandomnetworkofradiusR=0.3asmoreandmorecodewordsarereceived Inanypracticaldeploymentofsensornodesinageographicalarea,typicallythenetworkconsistsofwirelesssensornodesthathaveacertainrangewithinwhichtheycancommunicate.Insucha Data Persistence in a Sensor Networkwith Random Topology (N = 500) 1 0.8derevocer s 0.6 lobmys fo no 0.4 itcarF 0.2 Growth Codes, Random Network(R=0.2) No Coding, Random Network(R=0.2) 0 Growth Codes, Clique Network 0 200 400 600 800 1000 Time (=number of codewords received at the sink) Figure9:Datarecoveredatthesinkina500noderandomnetworkofradiusR=0.2asmoreandmorecodewordsarereceived scenario,thenodesaggregateinanaturaltopologydefinedbythewirelessrangeofthenodes. Wesimulatethisnetworkasa1x1square,byplacingsensornodesuniformlyatrandomwithinthesquare.Apairofnodes,isconnectedbyalinkiftheyarewithinadistanceRfromonean-other.TheparameterRiscalledtheradiusofthenetwork.Thisissimilartotheconnectivitymodelusedwithin[28]. Weassumeeachnodeinthenetworkinitiallygeneratesasymbolxi.Thereisonesinkthatisattachedtoasinglerandomnodeinthenetwork.Henceitisabletoreceiveonecodewordsymbolineachround.Therefore,theroundnumberisthesameasthenumberofcodewordsreceivedatthesink.ThenodesfollowtheencodinganddataexchangeprotocolbasedonGrowthCodesasdescribedinSection4.1. Wecomparewiththecasewhenthenetworknodesdonotencodeanydatabutinsteadexchangetheoriginalsymbols.Tofacilitateafaircomparison,whennotusinganycoding,thesensornodesbehaveinexactlythesamewayaswhentheyuseGrowthCodesexceptthattheydonottransitiontodegreeshigherthan1.Henceallthecodewordsgeneratedareofdegree1. Wenowcomparehowinarandomlyformednetworkwherethedensityofnodesandlinkswillvaryfromregiontoregion,GrowthCodescanbeusedtodeliverdataatafastratetothesinknode.Weconsidera500nodenetwork.Thesinkisattachedtoarandomnodeinthenetwork. Figure8depictsthefractionofdatarecoveredbythesinkasafunctionofthenumberofreceivedcodewordsinarandomnetworkwithradiusofR=0.3.Theresultsareanaverageof100sim-ulationruns.OntheX-axis,thenumberofcodewordsreceivedbythesinkareplottedwhiletheY-axisisthefractionofsymbolsrecoveredfromthereceivedcodewords. ArandomnetworkwitharadiusofR=0.3isfairlywellcon-nected.Forcomparisonpurposes,weplotthefractionofdatare-coveredasafunctionofnumberofcodewordsreceivedinanet-workwithcliquetopology.TheperformanceofGrowthCodesisroughlythesameinbothtopologies. WenowevaluatethedatarecoveryrateusingGrowthCodeswhenthenetworkhasaradiusofR=0.2implyingthatthenet-workismuchsparser.FromFigure9wecanobservethatthedatadeliveryrateofGrowthCodesdoesnotdeteriorateverymucheveninamuchsparserrandomnetwork. Weobservethatwhenthenumberofreceivedcodewordsissmall, thetwoprotocolsrecoverdataatthesamerate(sinceinthebe-ginning,GrowthCodesproduceonlydegree1codewords).Ontheotherhandwhenasubstantialnumberofcodewordshavebeenreceived,theGrowthCodesprotocolcanachievemuchfasterre-coveryrates.UsingGrowthCodes,thesinkisabletorecoverallsymbolsmuchearlierthanwhennocodingisused. Time to recover 3/4th of the symbols 1000Growth Codes - 3/4 data recovery No Coding - 3/4 data recovery 900s 800lobmys 700 eht fo h 600t4/3 rev 500 ocer ot 400 emiT 300 200 100 0 100 200 300 400 500 600 700 800 Number of nodes (= Number of distinct data units) Figure10:Timetakentorecover75%ofthedataina500nodenetworkwhenthenodesuseGrowthCodesversusnocoding Time to recover all symbols 7000 Growth Codes - complete recoveryNo Coding - complete recovery 6000 s 5000 lobmys lla 4000 revocer 3000 ot emiT 2000 1000 0 0 100 200 300 400 500 600 700 800 Number of nodes (= Number of distinct data units) Figure11:Timetakentorecoverallthedataina500nodenetworkwhenthenodesuseGrowthCodesversusnocodingFigure10depictshowmanyroundsonaveragearerequiredbe-forethesinkisabletorecover75%oftheoriginalNsymbols.OntheX-axis,wevarythenumberofsensornodesinthenetworkwhichisthesameasthetotalnumberofsymbols(sinceeachsensornodegeneratesonesymbol).OntheY-axis,wemeasurethetimetakentorecover75%ofthesymbols.Figure11depictsthetimetakentorecoverallthesymbols. Torecover75%ofthedata,bothprotocolsrequirethenumberofcodewordstobelinearinthenumberofnodesNwiththeGrowthCodesprotocolrequiringasmalleramount.RecoveringallthesymbolsusingGrowthCodesstillappearslinearinthenumberofnodes,however,withoutcoding,thenumberofcodewordsrequiredshowaclearnon-linearincrease.Sincetheunencodedretrievalpro-cessiscloselyrelatedtotheclassicalCouponCollector’sProblem,itisnotsurprisingtoseetheunencodedversionrequirealongtimetoacquirethelastfewsymbols. 9.2GrowthCodesinDisaster-ProneNetworks Time of Disaster=250, Radius of Disaster=0.2, N=500 nodes 1 knis eh 0.8 t ta derevoc 0.6 er atad lanigi 0.4 ro fo noitcarF 0.2 With Coding: r=0.2, t=250 0 Unencoded: r=0.2, t=250 0 100 200 300 400 500 600 700 800 900 1000 Number of codewords received Figure12:Datarecoveredatthesinkina500noderandomnetworkinadisasterscenarioofimpactradiusr=0.2attimet=250 Growthcodesareparticularlyeffectiveforinformationcollec-tionindisaster-proneareaswherethewholenetworkorpartsofitmaybedestroyedoraffectedinsomeway.Forexample,intheeventofaflood,asubsetofthesensornodesmaygetsubmergedandstopfunctioning.Inthecaseofanearthquake,awholeregioncontainingsensornodesmaygetdestroyed.Typically,theeffectofthedisasteronthesensornetworkwillshowstrongspatialcorrela-tioninthesensethatnodesclosetooneanotheraremorelikelytoeithersurvivetogetherorgetdestroyedtogether. Wesimulateadisasterinasensornetworkbydisablingpartofthenetworkatthetimeofthedisaster.Wedefinersuchthatatthetimeofthedisaster,allnodeswithinrdistanceofthecenteroftheimpactaredisabled.Thisineffect,changesthetopologyofthenetworksincethedisablednodesandalllinksconnectingthembecomenon-functional. Wenowdiscusshowthetimeofdisasterandtheradiusofim-pactaffectsthenetwork’sabilitytodeliverdatatothesink.Figure12showshowmuchdatacanberecoveredatthesinkifadisas-terofimpactradiusr=0.2disablespartofthenetworkattimet=250.Allnodeswithinaradiusofr=0.2fromthecenteroftheimpactaredisabled.Thisamountstoabout1/8thofthetotalnodes.Nevertheless,thedatarecoveryrateatthesinkwhenthenodesuseGrowthCodestoencodeanddistributedataisnotseverelyaffected. Ifthedisasteroccurssoonafterthedatagenerationbythesensornodes,thenodesthateventuallygetdisabledmaynothaveachancetospreadtheirdataoutsidetheregionofimpactandthatdatamaygetlost.Evenifthedatafromdisablednodesdoesgettothesurviv-ingnodes,thedistributionofdatafromdisablednodesandthedatafromsurvivingnodesmaybecomeskewed.Ifthenodesarenotus-inganycodingscheme,thisskewwillaffectthedatarecoveryrateatthesink.Ontheotherhand,ifthenodesareusingcodessuchasGrowthCodes,theskewwillnotmattersincehighdegreecode-wordscontainingdatafromdisablednodeswillbeconstructed.InFigure13,wedepicthowmuchdatacanberecoveredbythevariousprotocolsandhowlongdoesittaketorecoverthatdataincaseadisasterdisablesapartofa500nodenetworksoonafterdatagenerationbythenodes.OntheX-axis,wevarytheimpactradiusofthedisaster.Thenumberofdisablednodesisroughlyproportionaltothesquareoftheimpactradiusr.OntheY-axis,wedisplayhowlongittookforthesinktorecoverallsymbolsthatsur- Effect of a disaster on the survivability of data 4000 Growth Codes No Coding 3500 498sl 3000 obmys g 2500 500498n500500ivivrus 2000 re246voc500251er o 1500 t e500miT 1000 500 500 0 0.1 0.2 0.3 0.4 0.5 Radius of disaster impact Figure13:Timerequiredtorecoversurvivingdataforadis-asterattimet=50ofvaryingintensities.Thenumbersnexttothepointsindicatethenumberofsymbolsrecoveredinthatexperiment. vivedthedisaster.Thenumberofsymbolsrecoveredisindicatednexttotheplottedpoint.Notethatittakeslesstimetorecoverallrecoverablesymbolsforthedisasterofsize0.5becauseamuchsmallerfractionofsymbolsisrecovered.Wecanobservethatifthedisasterradiusissmallerthanr=0.4(thatcoversapproximatelyhalfthenodes),mostofthesymbolsdosurvivethedisaster.Onlywhenasubstantialportionofthenetworkisdestroyed,anumberofsymbolsarelostsincealotofnodesaswellastheirstoragemem-oryisdestroyed.Yet,byusingGrowthCodes,thesurvivingdatacanberecoveredreasonablyfastbythesink. 10. NODESTHATPERIODICALLYGENERATENEWDATA Tothispoint,wehaveconsideredanetworksettingwherenodestakeasinglemeasurementoftheirenvironment,thegoalbeingtodeliverasmuchofthatdataaspossibletothesink(s).WenowextendGrowthCodestoanenvironmentwherenodesperiodicallysampletheenvironment.WeassumethatwithperiodG,nodesgeneratedataofsizesd.Wecallthedatageneratedbyanodeinsuccessivetimeperiodsasbelongingtodifferentsuccessivegener-ations.Thefirstdatageneratedbyasensornodeisofgeneration1. WeassumeafixedstoragesizeofCateachnode.Thestoragemustnowbesharedacrossmultiplegenerations.TypicalsensornodeshavealimitonthemaximumpacketsizeStheycansendorreceive.WepartitionthememoryofeachnodeofsizeCintochunksofsizeSsothatthereareC/Schunks. 10.1ClusteringAcrossGenerations OneconcernwhenusingGrowthCodesacrossmultiplegener-ationsisthatthesizeofthecoefficientdescribingthecodewordcouldgrowlargeforlarge-degreecodewords.Letsdbetheamountofspacerequiredforstoringthedataandscforstoringthecoef-ficient.LetγbethenumberofgenerationswewishtostoreinachunkofS.ThisleavesonaveragesizeS/γforeachgeneration,andanaivestorageschemewouldrequirethatγbechosensuchthatS/gm≥sd+sc.Heregmindicatesthenumberofgenera-tionsthatcompriseacluster. Toreducethecoefficientoverheadacrossgenerations,weintro-ducethenotionofclustering.Aclusterisasetofcodewordsacross severalgenerations.Thecodewordshavethesamecoefficients(i.e.,theoriginsofthesymbolsusedthatcomprisethecodewordarethesame),butthedataineachcodewordisfromadifferentgeneration. Cluster 1 Cluster 2 Cluster 3 Cluster 4 CoeffCoeffCoeffCoeffGen 3Gen 4Gen 7Gen 10codeword codewordcodewordcodewordGen 5Gen 8Gen 11codewordcodewordcodeword Gen 6Gen 9codewordcodeword Figure14:StoringClustersinMemory. AnexampleofhowmemoryisusedwithclusteringisdepictedinFigure14inwhichthenumberofgenerationspercluster,gm=3.Acluster’ssmallestnumbered(i.e.,earliest)generationisnum-bered1(mod3),andthelargestnumbered(i.e.,latest)generationisnumbered0(mod3).Inthisexample,thereissufficientmem-orytostore9codewordsand4coefficients(i.e.,S≥9sd+4sc).Tomakeroomforthecodewordscluster4(generation10and11),codewordsforgeneration1and2wereremoved.Whengeneration12’scodewordisgenerated,itsstoragewillnecessitatetheevictionofcodeword3.Hence,cluster1canbecompletelyremovedatthattime.Whengeneration13arrives,cluster5isinitiallyformed,andcodeword4willberemovedatthattime(butgenerations5and6,andhencethecoefficientofcluster3,willremain). Sinceallcodewordswithinaclusterhavethesamecoefficient,thecodewordcannotbemodified(i.e.,“grown”toahigherdegree)untiltheclusterisfullyformed(e.g.,intheexampleabove,thecodewordsforgeneration10and11mustremainastheoriginaldatasymbolsgeneratedbythatnodeforthosegenerationsuntilgeneration12’sdataisalsoavailable).Thisdelayisnotasignifi-cantconcernsinceweknowthattheoptimalgrowthrateofGrowthCodesstaysfixedatdegreeoneforaconsiderableamountoftime.Sinceallgenerationsinaclustersharethesamecoefficient,thepointintimeatwhichthecodewordsgrowtothenextdegreeisthesame.Hence,thetimewilleitherbetoosoonforthemostrecentgenerationinacluster,ortoolatefortheoldestgenerationinacluster.Sinceourapproachistoremainconservativeaboutwhentotransitiontothenextdegree,werecommendtheuseofthetransitiontimeofthemostrecentgenerationinthecluster. Theabovediscussionraisesanissueabouthowmanygenera-tionsofdatacanbeencodedinasinglepacket.Also,transmissionchannelshavetypicallyhaveasmalllimitonthepacketsize(Max-imumTransmissionUnit)whichcanbesentoverthechannel.IncaseapacketcontainingmultiplegenerationsisbiggerthantheMTUofthechannel,asimplefragmentationandreassemblycanbeaddedtotheimplementationtotakecareofthisissue.Wedonotexplorethisissuefurtherinthispaperduetospaceconstraints. 10.2OptimalClusterSize Asclustersizeisincreased,thesizeofthecoefficientpergener-ationdecreases.Ifthespaceallocatedtoeachgenerationisfixed,thenbydecreasingtheoverheadofthecoefficients,datacanre-sidelongerinmemory.However,sincecodewordswithinaclustercannotbegrownuntilallgenerationsareavailableforthatcluster,alargerclustersizereducesthetimeoverwhichacodewordcangrow. Letgmbethemaximumnumberofgenerationsinacluster.Itcanbeshown√thattheoptimalvalueofgmisboundedfrombelow byg2Ssm=c−sc s.IfmemorysizeisS,thecoefficientsizesc, d thecodewordsizeissdandthemaximumgenerationsinaclustercanbegm,thenthemaximumsizeofaclusterissc+gmsd.ThenumberofclustersinmemoryisapproximatelyS/(sc+gmsd).ThenumberofcodewordsofsuccessivegenerationsinmemoryisthengmS/(sc+gmsd).SinceanewgenerationcodewordisaddedaftertimeG(andtheoldestcodewordremovedatthesametime),thetimeforwhichagenerationcodewordstaysinmemoryisgivenbyTg=gmSG/(sc+gmsd). Itcaneasilybeobservedthatthegeneration’scodewordintheclustermustremainfixedforgm−1generations,thesecondoldestgeneration’scodewordforgm−2generationsandsoon.Hence,an“average”codewordmustbefixedforgm−12generations,andthetimeforwhichatypicalcodewordisfixedisthereforeGgm−1Thetimeoverwhichacodewordgrowsuninterruptedaccording2.togthe−Growth1CodesprotocolisthengivenbyTgrowth=Tg−Gm2.Theoptimalvalueofgmisonethatmaximizesthetimeover√whichanaveragecodewordcangrow.Thisisgivenbygm=2Ssc−sc ,whereweomitthederivationduetoTslackofspace. d g,whichisthetimecodewordsofaparticulargenerationstayinmemory,increasesmonotonicallywithgm.ButthetimeforwhichacodewordgrowsuninterruptedaccordingtotheGrowthCodesprotocolisgivenbyTgrowthwhichpeaksattheoptimalvalueofgm.Forvaluesofgmhigherthanthis,Tgrowthdecreasesbuttheextralowdegreecodewordsgeneratedbytheconstantresettingoftheclustersalsogrows,resultinginaslightlossofefficiency. 11.CONCLUSIONS Thegoalofthispaperistoinvestigatetechniquestoincreasethepersistenceofsensornetworks.WeproposeGrowthCodes,anewclassofnetworkcodesparticularlysuitedtosensornetworkswheredatacollectionisdistributed.Unlikepreviouscodingschemes,GrowthCodesemployadynamicallychangingcodeworddegreedistributionthatdeliversdataatamuchfasterratetonetworkdatasinks.Furthermore,thecodewordsaredesignedsuchthatthesinkisabletodecodeasubstantialnumberofthereceivedcodewordsatanystage.Thisisparticularlyusefulinsensornetworksdeployedindisasterscenariossuchasfloods,firesetc.wherepartsofthenetworkmaygetdestroyedatanytime. OursimulationsandexperimentsdemonstratethatGrowthCodesoutperformotherproposedmethodsinsettingswherenodesarehighlypronetofailures.Whilepersistenceinsensornetworkswasoneapplicationwestudied,webelieveGrowthCodeshavewiderapplicability.ThecriticalinsightbehindGrowthCodesistointelli-gentlypreserve“memory”ofanetwork,makingitmorerobustandresilient.Theideaispotentiallyveryusefulinotherdynamicallychangingenvironmentslikefileswarmingp2pframeworks,andweareactivelyexploringothersimilarapplicationsofGrowthCodes. 12. [1]CrossbowREFERENCES micazmotes.[2]TinyOSHomepage. [3]S.Katti,D.Katabi,W.Hu,H.RahulandM.Medard.TheImportanceofBeing Opportunistic:PracticalNetworkCodingForWirelessEnvironments.In AllertonAnnualConferenceonCommunication,ControlandComputing,2005. [4]A.Albanese,J.Bl¨ omer,J.Edmonds,M.Luby,M.Sudan.PriorityEncodingTransmission.InIEEETransactionsonInformationTheory,volume42,1996.[5]A.G.Dimakis,V.PrabhakaranandK.Ramchandran.UbiquitousAcessto DistributedDatainLarge-ScaleSensorNetworksthroughDecentralizedErasureCodes.InInformationProcessinginSensorNetworks,2005.[6]A.Kamra,J.Feldman,V.MisraandD.Rubenstein.DataPersistencefor Zero-ConfigurationSensorNetworks.InTechnicalReport,DepartmentofComputerScience,ColumbiaUniversity,Feb.2006. [7]A.ManjeshwarandD.P.Agrawal.Teen:ARoutingProtocolforEnhanced EfficiencyinWirelessSensorNetworks.InParallelandDistributedProcessingSymposium,2001. [8]A.ScaglioneandS.D.Servetto.Ontheinterdependenceofroutinganddata compressioninmulti-hopsensornetworks.InACMConferenceonMobileComputingandNetworking,2002. [9]C.GkantsidisandP.Rodriguez.NetworkCodingforLargeScaleContent Distribution.InProceedingsofINFOCOM,2005. [10]C.Intanagonwiwat,R.GovindanandD.Estrin.Directeddiffusion:ascalable androbustcommunicationparadigmforsensornetworks.InACMConferenceonMobileComputingandNetworking,2000. [11]C.Y.Wan,S.B.Eisenman,A.T.Campbell,J.Crowcroft.Siphon:Overload TrafficManagementusingMulti-RadioVirtualSinks.InACMConferenceonEmbeddedNetworkedSensorSystems,2005. [12]D.Marco,D.Neuhoff.Reliabilityvs.EfficiencyinDistributedSourceCoding forField-Gathering.InInformationProcessinginSensorNetworks,2004.[13]I.F.Akyildiz,M.C.Vuran,O.B.Akan.OnExploitingSpatialandTemporal CorrelationinWirelessSensorNetworks.InProceedingsofWiOpt2004:ModelingandOptimizationinMobile,AdHocandWirelessNetworks,pages71–80,Mar.2004. [14]J.Byers,J.Considine,M.MitzenmacherandS.Rost.InformedContent DeliveryAcrossAdaptiveOverlayNetworks.InProceedingsofSIGCOMM,2002. [15]J.Considine.Generatinggooddegreedistributionsforsparseparitycheck codesusingoracles.InTechnicalReport,BUCS-TR2001-019,BostonUniversity,2001. [16]J.W.Byers,M.Luby,M.Mitzenmacher,A.Rege.ADigitalFountainApproach toReliableDistributionofBulkData.InProceedingsofSIGCOMM,1998.[17]LinandCostello.ErrorControlCoding:FundamentalsandApplications.1983.[18]M.Luby.LTCodes.InSymposiumonFoundationsofComputerScience,2002.[19]M.Li,D.GanesanandP.Shenoy.PRESTO:Feedback-DrivenData ManagementinSensorNetworks.InACM/USENIXSymposiumonNetworkedSystemsDesignandImplementation,2006. [20]M.Luby,M.Mitzenmacher,M.A.ShokrollahiandD.Spielman.Efficient ErasureCorrectingCodes.InIEEETransactionsonInformationTheory,volume47,pages569–584,2001. [21]M.O.Rabin.EfficientDispersalofInformationforSecurity,LoadBalancing andFaultTolerance.InJournaloftheACM,volume36,pages335–348,1989.[22]M.Perillo,Z.IgnjatovicandW.Heinzelman.AnEnergyConservationMethod forWirelessSensorNetworksEmployingaBlueNoiseSpatialSamplingTechnique.InInformationProcessinginSensorNetworks,pages116–123,2003. [23]M.SartipiandF.Fekri.SourceandChannelCodinginWirelessSensor NetworksusingLDPCCodes.InEEECommunicationsSocietyConferenceonSensorandAdHocCommunicationsandNetworks,2004. [24]N.Cai,S.Y.R.LiandR.W.Yeung.LinearNetworkCoding.InIEEE TransactionsonInformationTheory,volume49,pages371–381,2003.[25]P.Desnoyers,D.GanesanandP.Shenoy.TSAR:ATwoTierStorage ArchitectureUsingIntervalSkipGraphs.InACMConferenceonEmbeddedNetworkedSensorSystems,2005. [26]P.J.M.Havinga,G.J.M.SmitandM.Bos.EnergyEfficientAdaptiveWireless NetworkDesign.InTheFifthSymposiumonComputersandCommunications,2000. [27]R.Ahlswede,N.Cai,S.Y.R.LiandR.W.Yeung.NetworkInformationFlow. InIEEETransactionsonInformationTheory,volume46,pages1004–1016,2000. [28]R.Chandra,C.FetzerandK.Hogstedt.AMesh-basedRobustTopology DiscoveryAlgorithmforHybridWirelessNetworks.InProceedingsofAD-HOCNetworksandWireless,Sept.2002. [29]R.KoetterandM.Medard.AnAlgebraicApproachtoNetworkCoding.In ACM/IEEETransactionsonNetworking,volume11,pages782–795,2003.[30]R.MotwaniandP.Raghavan.RandomizedAlgorithms.CambridgeInternational SeriesonParallelComputation. [31]S.Acedanski,S.Deb,M.MedardandR.Koetter.HowGoodisRandomLinear CodingBasedDistributedNetworkedStorage.InWorkshoponNetworkCoding,TheoryandApplications,2005. [32]S.Pattem,B.KrishnamachariandR.Govindan.TheImpactofSpatial CorrelationonRoutingwithCompressioninWirelessSensorNetworks.InInformationProcessinginSensorNetworks,pages28–35,2004. [33]S.S.Pradhan,J.KusumaandK.Ramchandran.Distributedcompressionina densemicrosensornetwork.InIEEESignalProcessingMagazine,volume19,pages51–60,Mar.2002. [34]T.Arici,B.Gedik,Y.AltunbasakandL.Liu.PINCO:aPipelinedIn-Network COmpressionSchemeforDataCollectioninWirelessSensorNetworks.InInternationalConferenceonComputerCommunicationsandNetworks,2003. [35]T.Ho,M.M´ edard,M.EffrosandD.Karger.OnRandomizedNetworkCoding.InAllertonAnnualConferenceonCommunication,ControlandComputing,Oct.2003. [36]W.Heinzelman,A.ChandrakasanandH.Balakrishnan.Energy-Efficient CommunicationProtocolsforWirelessMicrosensorNetworks.InHawaiiInternationalConferenceonSystemsSciences,2000.
因篇幅问题不能全部显示，请点此查看更多更全内容