∗
SchoolofElectricalAnnaandScaglione
ComputerEngineering
CornellUniversity
http://people.ece.cornell.edu/scaglione/ABSTRACT
Weconsideraproblemofbroadcastcommunicationinamulti-hopsensornetwork,inwhichsamplesofarandomfieldarecollectedateachnodeofthenetwork,andthegoalisforallnodestoobtainanestimateoftheentirefieldwithinaprescribeddistortionvalue.Themainideaweexploreinthispaperisthatofjointlycompress-ingthedatageneratedbydifferentnodesasthisinformationtravelsovermultiplehops,toeliminatecorrelationsintherepresentationofthesampledfield.Ourmaincontributionsare:(a)weobtain,us-ingsimplenetworkflowconcepts,conditionsontherate/distortionfunctionoftherandomfield,soastoguaranteethatanynodecanobtainthemeasurementscollectedateveryothernodeinthenet-work,quantizedtowithinanyprescribeddistortionvalue;and(b),weconstructalargeclassofphysically-motivatedstochasticmod-elsforsensordata,forwhichweareabletoprovethatthejointrate/distortionfunctionofallthedatageneratedbythewholenet-workgrowsslowerthantheboundsfoundin(a).Atrulynovelaspectofourworkisthetightcouplingbetweenroutingandsourcecoding,explicitlyformulatedinasimpleandanalyticallytractablemodel—tothebestofourknowledge,thisconnectionhadnotbeenstudiedbefore.
Keywords
Multi-hopnetworks,sensornetworks,sourcecoding,routing,cross-layerinteractions
1.INTRODUCTION1.1
ProblemSetup
Considerthefollowingdatatransmissionproblem.Nnodesviareplacedontheclosedset[0,1]×[0,1],atlocations(xi,yi).EachviobservesasampleSiofsomespatialstochasticprocesswithrate/distortionfunctionRS(D)(seeAppendixB),havingthe∗grantWorkCCR-0227676supportedinpartandbyONRtheContractNationalN00014-00-1-0564.
ScienceFoundationunderPermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.
MOBICOM’02,September23–26,2002,Atlanta,Georgia,USA.Copyright2002ACM1-58113-486-X/02/0009...$5.00.
SchoolofElectricalSergioandD.ComputerServetto
Engineering
CornellUniversity
http://people.ece.cornell.edu/servetto/
propertythatthecorrelationbetweensamplesincreasesasthedis-tancebetweentheminthegriddecreases.Eachviwantstocom-municateanapproximationofitsSitoeveryothernodeinthenet-work.EachvicanonlysendmessagestoandreceivemessagesfromnodeswithindistanceCN,wherethisconnectivityradiusischosensoastoensurethatthenetworkwillbeconnectedwithhighprobability[8].LinkshaveafixedfinitecapacityL,independentofnetworksize.Giventheseassumptions,weareinterestedinde-terminingunderwhatconditionsitispossibleforeachnodevitoobtainanestimateofthesampleobservedateverynetworkloca-tionvk,k=1,...,N,suchthatvihasanestimatefieldofsampleswhosetotaldistortionE(d(S,S
ˆoftheentire
)) i)) findouthowmuchtrafficdoesthisnetworkgenerate.Veryclearlythisquestiondependsonthestatisticsofthesenseddata.Foril-lustrationpurposesandwithoutlossofgenerality,considerasim-pleexample:supposethatSiisuniformintherange[0,1],thateachnodeusesascalarquantizerwithBbitsofresolution(i.e.,thequantizationstepis2−B),andthatdistortionismeasuredinthemean-squaresense.Awellknownresultfrombasicquantizationtheorystatesthattheaveragedistortionachievedbysuchaquan-tizeronthisparticularsourceis1−2B 122[6].Addingdistortions overallnodesinthenetworkwethenhavethatNi=1d(Sij,Sˆi)= 1N2−2B,andhence,solvingforBinD=1−2Bovertheentire12N2,wegetthat12tomaintainatotaldistortionnetworkofDeach samplerequiresB=1log2(N 12)bits.Asaresult,theto-talamountoftrafficgenerated2byDthewholenetworkscaleslikeO(NlogN)innetworksize.Furthermore,itisimportanttoem-phasizethatalthoughwithmoresophisticatedquantizationstrate-giesthanthesimpleuniformquantizerconsideredinthismotiva-tionalexampleonecouldcertainlyreducethenumberofbitsgener-atedforafixeddistortionlevelD,thisreductionwouldonlyaffectconstantshiddenbythebig-ohnotation,buttheO(NlogN)scal-ingbehaviorofnetworktrafficwouldremainunchanged[3](exam-plesofanalysesofthistypecanbefoundin[12,Sec.3]and[14,Sec.7]). Oncewehavedeterminedhowmuchdataourparticularcodingstrategy(independentquantizersateachnode)produces,weneedtoknowifthenetworkhasenoughcapacitytotransportallthatdata.Andtheanswerisno[9].Toseehowthisisso,considerapartitionofthenetworkasshowninFig.1. ∆ Figure1:Nnodesarespreaduniformlyovertheunitsquare[0,1]×[0,1](Nlarge).Takeadifferentialvolumeofsize∆×∆(∆small).Withhighprobability,thenumberofnodesinadifferentialvolumeis≈N∆2,andsothenumberofnodesinastripasshowninthefigureis≈N∆.SincethetotalnumberofnodesisN,wemusthaveN=N∆×N∆(becausethetotalareaoftheunitsquareistheproductoftheareasoftwostripsasshowninthefigure,onehorizontalandonevertical),andhencewe∆=O(√musthavethatthenumberofnodesinastripasshownisNN). Inthesensorbroadcastproblemofinterestinthiswork,allthenodesinthenetworkmustreceiveinformationaboutthemeasure-mentscollectedbyallothernodes.Asaresult,allthetrafficgener-atedontheleftportionofthenetworkmustbecarriedtotheright,andallthetrafficgeneratedontherightportionofthenetworkmustbecarriedtotheleft.Thatis,accordingtoourcalculationabove,thenodeswithinthestripmarkedinFig.1mustsharetheloadofmovingO(NlogN)bitsacrossthisnetworkcut.Butsincelinkshave√finitecapacityL,thecapacityofthiscutcannotbelargerthanO(LN).Butfromthemax-flow/min-cuttheorem[4,Ch.27],weknowthatthevalueofanyflowinthisnetworkisupperboundedbythecapacityofanynetworkcut,andtherefore,theofthisnetworkcannotbehigherthanO(L√totaltransportcapacityN).Andnowweseewhattheproblemis:O(NlogN)bitsmustacrossacutofcapacityO(L√ goN).Thatis,evenoptimalvectorquantizationstrategiescannotcompressthedataenoughsothatthenetworkcancarryit—thenetworkdoesnotscaleup.1 CorrelatedSamples Thescalinganalysisforindependentencoderspresentedaboveignoresonefundamentalaspect:increasingcorrelationsinsensordataasthedensityofnodesincreases.Andindeed,ifthedataissohighlycorrelatedthatallsensorsobserveessentiallythesamevalue,atleastintuitivelyitseemsclearthatalmostnoexchangeofinformationatallisneededforeachnodetoknowallothervalues:knowledgeofthelocalsampleandoftheglobalstatisticsalreadyprovideafairamountofinformationaboutremotesamples.Andthisnaturallyraisesthequestion:arethereothercodingstrategiesthatcancompresssensordataenough? 1.2 RoutingandDataCompression Weconsidertwoapproachestotheproblemofdatacompressionformulti-hopsensornetworks.Oneoftheseistheideaofusing1 reticTechniquesbasedonCh.capacityproblemsflowsinnetworksandcutshavetoanalyzebeenproposedinformationin[1],theo-interpretation14.10],Inforthisthecontext,Gupta/Kumarthosetechniques[5,results[9]. provideanalternativedistributedsourcecodingtechniques,thathasattractedsomeatten-tionrecently[11,12,15],asmulti-hopsensornetworksappeartobethe“killerapplication”forsomeofthesewell-establishedtheo-reticalresults.Thesecondoneisacombinationofclassicalsourcecodingmethodsandroutingalgorithmswhich,tothebestofourknowledge,hasnotbeenexploredbefore. DistributedSourceCoding Undersomemildtechnicalassumptions,recentworkhasestab-lishedthepossibilityofusingdistributedsourcecodingtechniquestoovercometheproblemofvanishingthroughputsof[9],thatren-dersestimationimpossibleinthecaseofindependentsources[12].Thisresultisveryinterestingfromatheoreticalpointofview,sinceitprovesthatitispossibleforeachnodevitogetridofallcorrela-tioninthedatawithoutrequiringnodestoexchangeasinglebitofinformation. Whereascertainlyinterestingintheirownright,fromthepointofviewofanengineerengagedinthedesignofapracticalsensornetwork,theresultsof[12]arenotveryrelevant.Thisisbecausetheproofdevelopedin[12]toshowthatarbitrarilyaccurateesti-mationoftheremotevaluesispossible—evenwithoutanyformofcooperationamongsensingnodes—involvestheuseofcodesfortheproblemofrate/distortionwithsideinformation[5,Ch.14.9].Efficientcodesforthisproblemarecharacterizedbythefactthattheprobabilityofallcodewordsisnearlyuniform,irrespectiveofthestatisticsofthesourceandofthelengthoftheblocksused.Asaresult,forpractical,shortcodes(e.g.,scalarquantizers),gainsduetoentropycodingarenegligible.Fromatheoreticalpointofviewthisisnotaproblem:byconsideringergodicsourcesandlargeblocksofdata,theAsymptoticEquipartitionPropertyguaranteesthattheseblockswillbeuniformlydistributedanyway,andhencenoentropycodingisneeded[5,Ch.3].Butfromapracticalpointofview,high-dimensionalvectorquantizersarenotalwaysfeasi-ble,andsoinpractical,short-blocksettings,itisunclearhowmuchofthegainsobtainedbythesecodesbymeansofexploitingcorre-lationsamongsamplesarelostduetotheinabilityofthesecodestotakefulladvantageofentropycodinggains. RoutingandSourceCoding Whereasrequiringthatnodescompressalltheirdatawithoutex-changinganyinformationatallwouldcertainlybeavalidwaytogoaboutsolvingthisproblem,wesubmitthatthisapproachmaybeneedlesslyrestrictive.Afterall,inmulti-hopnetworks,ames-sagedoesvisitmultiplenodesbeforeitreachesitsdestination,andthereforeonemaywonderwhynotuseclassicalsourcecodes,andthenre-encodethedataasithopsaroundthenetworktoremovecorrelationsamongsamples.Twoexamples(amongmanymorepossibilities)ofsuchaschemeareshowninFig.2. WeseefromtheexamplesinFig.2that,attheexpenseofin-creasedtransmissiondelays,wecancommunicateallsamplestoallnodesgeneratinganamountoftrafficwhichisessentiallythesameasifonenodehadcollectedallthesamplesandencodedthemjointly,andthenthisinformationhadbeenbroadcasttoallothernodes.Alternatively,bysacrificingsomecompressionefficiency,itisalsopossibletoincurinlowertransmissiondelays.Thatis,thereisaninherenttradeoffbetweenbandwidthuseanddecodingdelay,andthesetwoquantitiesarelinkedtogetherbytheroutingstrategyemployed. Contrarytothecomplicatedvectorquantizersrequiredbydis-tributedsourcecoding,whenroutingandsourcecodingarecom-binedtheprocessingateachnodecanbedoneusinganyofthestan-dardcompressiontechniquewhichareusednormallytocompresssequencesfromanalogsources(DPCM,Σ−∆,subband-coding (a) 1(a) 11(e) 3|1,221(b) 2|1(b) 2|12(h) 4|1,2,3(g) 4|1,2,3(d) 3,4|1,2(d) 3,4|1,2(d) 3|1,2(c) 1,2(f) 1,2,3(c) 1,2(c) 1,23(g) 4|1,2,343(a) 3(b) 4|34Figure2:Consideranetworkwith4nodes,eachofwhichobservesa variableXi(i=1...4),withjointentropyH(X1,X2,X3,X4).Twopossiblewaysofschedulingtransmissionsareshown.Thenotationusedinthefigureisthat(a)isthefirsttransmission,(b)thesecond,(c)thethird,andsoon;iftwotransmissionshavethesameletterlabel,theycanbeperformedinparallel;i|jmeansthatthesampleofnodeiisencodedwhenknowledgeofthesampleofnodejisavailable.Us-ingchainrulesforentropies,weseethatinthetransmissionscheduleoftheleftfigurewegenerateatotaltrafficof3H(X1,X2,X3,X4),andittakes8timeslotstocomplete.Inthescheduleoftherightfig-ure,wegeneratemoretraffic(2H(X1,X2,X3,X4)+H(X1,X2)+H(X3,X4)bits),butnowweonlyrequire4timeslotstocompletealltransmissions. suchasJPEG,etc.).Aninterestingalternativeisusingascalarquantizerlocallyandthenforwardthedatainfilescompressedus-inguniversalsourcecodingalgorithms,suchasLempel-Ziv.Thelatteroptionwouldbeeffectiveinmoregeneralcontextsthantheoneofsensorsnetworks:indeed,webelievethattheideaofcom-biningroutingwithdatacompressioniskeytothemostgeneralmulti-hopnetworksnotonlycomposedofsensors.Infact,often-timesdistributedcommunicationandroutingprotocolsthemselvesgeneratecorrelatedandredundantdatathatarebroadcastedthroughthenetworkandthatcaneasilycausecongestion.Clearlythecom-pressionratiowillbehigherasmoreandmoreredundantdataarepooledtogetherateachnode,butthismechanismwouldpreciselybetheonethatpreventscongestion. Ourgoalinthisfirstpaperonthesubjectistoprovideasolidthe-oreticalframeworkbasedonratedistortiontheory(seeAppendixB)whichsupportstheseintuitions. 1.3 MainthePaper ContributionsandOrganizationofIntheframeworkdefinedabove,weseethattherearetwofun-damentalquestionsthatneedanswers: 1.Underwhatconditionsonthestatisticsofthesourcecananetworkofthetypeconsideredinthisworktransportallthedatageneratedbythesources?2.Whatarethetradeoffsbetweenbandwidthrequirementsandtransmissiondelays?Thispaperfocusesonthefirstquestion,andourmainresultsare:(a)ProofoftheexistenceofroutingalgorithmsandsourcecodesthatrequirenomorethanO(R(D))bitsinO(√ S1...SNN)transmissions,whereRS1...SN(D)isthejointrate/distortionfunctionofallsamplesinthefield.Thiswouldprovethat,evenunderdecentralizationconstraints,classicalsourcecodescanstillachieveoptimalcompressionefficiency.Andfur-thermore,attainingthatoptimalperformancerequiresanum-beroftransmissionsthatissub-linearinthenumberofnodesinthenetwork. (b)ProofthatRS1...SN(D)≤O(log(N/D)),undersomeex-tremelymildregularityconditionsontherandomfield.Thatis,iftheaveragedistortionpersampleD/Niskeptcon-stant,thefieldgeneratesaboundedamountofinformation,independentlyofitssize.Andifthetotaldistortioniskeptconstant,thegrowthofRisonlylogarithmicinN,wellbe-lowthetotal√transportcapacityofthenetwork,whichgrowslikeO(LN)(asarguedinSection1.1and[9]).Thesecondquestionhoweverisoutsidethescopeintendedforthispaper,andwillbedealtwithelsewhere. Sincethesensorsarecontinuousandnotdiscretesourcesthethe-oreticaltooltoanalyzetheproblemisRateDistortionTheory[5,Ch.13],whichallowsustodeterminetheminimumnumberofbitsrequiredtorepresentthesourcesamplestoachievethedesiredlevelofaveragedistortion.ThenumberofbitsisobtainedasafunctionofthejointstatisticsoftheprocessSonly,withoutmakingrefer-encetoaspecificquantizationalgorithmandusingthenotionofjointdifferentialentropyratherthanjointentropy.Tokeepthispaperself-containedthereadernotfamiliarwithRateDistortionTheorycanfindasuccinctdescriptionofitinAppendixB. Therestofthispaperisorganizedasfollows.InSection2wecomputeboundsonthetransportcapacityofournetwork,andweusetheseboundstoimposeconstraintsontheratesatwhichtherandomfieldsensedcangenerateinformation.Then,inSection3,weproposeamodelforthegenerationofsensordata,basedonwhichweprovethatindeed,theamountofdatageneratedbythenetworkiswellbelownetworkcapacity.ConcludingremarksarepresentedinSection4. 2.TRANSPORTCAPACITY Usingsimplenetworkflowconcepts,inSection1.1wearguedthatanupperboundonthetransportcapacityofanetworkofsizeNisO(L√ N).Ourgoalinthissectionistoconstructoneparticularflow:fromtheamountofdatathatthisflowneedstopushacrossthenetwork,andfromtheupperboundonthecapacityofthenetwork,wederiveaconstraintontheamountofdatathatthesourcecangenerateifitistobebroadcastoverthewholenetwork. 2.1ANetworkFlowonaRegularGrid Weconsiderfirstthecaseofaregulargrid,asitnaturallypre-cedestheconstructionforageneralrandomgrid. SupposethatwewanttoachieveanaveragedistortionDinthereproductionsofSu.Letq(Si)denoteaquantizedversionofSi,wherethequantizerqissuchthatE(d(Si,q(Si))≤D.Theen-tropyinducedonthecodewordsofqbyquantizationofthesourceSisdenotedbyHq(S). Weconstructaflowrecursively.Forsimplicity,assumeN22k =,forsomeintegerk≥0.Whenk=0,wehavethetrivialcaseofanetworkofsizeN=1,inwhichallnodes(i.e.,v1)knowthevalueofallsamples(i.e.,S1)withoutanytransferofinformation.Considernowapartitionofnodesviinto4groups:PULcon-tainingallthenodesintheupper-leftcornerofsize1×1,Pnodesintheupper-rightcorner,P2P2UR LLlower-left,andLRlower-right.SPdenotesthesetofvariablesobservedbynodesinasetP.ThispartitionisillustratedinFig.3. WehavethatPUL,PUR,PLL,PLRareallsubnetsofsizeN=22(k−1),andsofromourrecursionwegetthatallnodeswithineachsubnetknowthevaluesofallvariableswithintheirsubnettowithindistortionD.Butnow,wehavereducedourproblemtotheproblemwithfournodesconsideredinFig.2,andweknowthatexchangingatotalof3Hq(SPUL,SPUR,SPLL,SPLR)bits,inatotalof8transmissionsacrosscuts(plusO(√ N)transmissionsto ULUR LL LR Figure3:Partitionofanetworkofsize4×4intofoursubnets.spreaddatawithincuts),isenoughtoensurethateverynodeinthenetworkofsizeN=22kknowseveryvaluetowithindistortionD.ThisconstructionisillustratedinFig.4. Figure4:Sinceeachnodeontheboundaryofacuthasknowledgeof allsampleswithinitssubnet,each oneofthemcanencodeallthesesam-plesjointlyandsend2√1N-thofthisdataacrossthecut.Then,inO(√ N)moretransmissions,allthesepiecescanbespreadthroughoutthesubnettoreachallnodes. Forreference,comparetheperformanceofthisflowagainstan idealone,inwhicheachviholds1 N-thofajointencodingofS1...SNcomputedbysome“genie”:thetaskinthiscaseistobroadcastthepieceheldbyeachnodetoallothernodes,sothatallnodescanobtainthevaluesofallmeasurements.Thatidealizedsystemstillmustgenerateatotalof3RS1...SN(D)bitsandstillrequiresO(√ oftraffic,N)transmissionstocompletethebroadcast(bothfollowfromstraightforwardcalculations).Therefore,weseethattheonlypenaltythattheflowconstructedabovetakeswithre-specttothegenie-aidedflowistheneedtore-encodemessagesatintermediatenodes. 2.2TheCaseofaRandomGrid Theonlydifferencebetweenthecaseofarandomgridandthecaseofaregulargridasconsideredaboveisthefactthat,intherandomcasethereisanon-zeroprobabilitythat,intherecursivedefinitionoftheflowabove,wemayencounteranemptysubnet.Butinthatcase,onlytrivialmodificationscantakecareofthisproblem.Forexample,intheleftscheduleofFig.2,ifnode3wasnotthere,anappropriatescheduleoftransmissionswouldbe:(a)X1sentfrom1to2,(b)X2|X1sentfrom2to1,(c)X1,X2sentfrom2to3,(d)X3|X1,X2sentfrom3to2,(e)X3|X1,X2sentfrom2to1.Inthiscase,againusingthechainrulesforentropieswegetthatthetotalnumberofbitssentis2H(X1,X2,X3).So withsimplemodificationslikethisone,thecaseofarandomgridiseasilyreducedtothecaseofaregulargriddescribedabove. 2.3 GeneralConstraints Weknowthefollowingfacts: •Since{SPUL,SPUR,SPLL,SPLR}={S1...SN}, O(Hq(S1...SN))bitsmustgoacrossthe4-waycutdefinedbySUL,SUR,SLL,SLR. •Thecapacityofthe4-waycutisO(L√ N). •Fromrate/distortiontheory[5,Ch.13],weknowthatHq(S1 ...SN)≥RS1...SN(D),sinceqisaquantizerwithmeandistortionD.Therefore,aslongas (R√ OS1...SN(D))≤OLN, (1) thereexistcodesandroutessuchthateverynodecanhaveenoughinformationtoformanestimateofthesampleavailableateveryothernodewithinaprespecifieddistortionvalueD. 3.AMODELFORSENSORDATA InSection2wesawthat,byappropriateroutingandre-encodingalongroutes,wecancompressallthedatageneratedbytheen-tirenetworkdowntoO(RS1...SN(D)).Ourgoalinthissectionistoverifythat,forreasonablemodelsofsensordata,wehavethateqn.(1)issatisfied,sothatthebroadcastproblemcanbeeffectivelysolved. Tobeabletotalkabout“therate/distortionfunctionofthedatageneratedbytheentirenetwork”weneedamodelforthisdata.Themainideathatwewouldliketocaptureinourmodelsforsen-sordataisthat,ifthisdatacorrespondstomeasurementsofaran-domprocesswithsomekindofregularityconditions(aswouldbethecaseforalmostanyphysicalprocessonecouldconceive),thenthesemeasurementshavetobecomeincreasinglycorrelatedasthedensityofnodesbecomeslarge.Weproposetothisendafairlygeneralclassofsuchmodels,undertwoassumptions:(a)thedataareGaussianrandomvariables(b)thecorrelationamongsamplesisanarbitraryspatiallyhomogeneousfunction;and(c),asweletthenumberofnodesinthenetworkgrow,thecorrelationmatrixconvergestoasmoothtwo-dimensionalfunction. Assumption(a)isaworsecasescenarioasfarascompressionisconcerned,asaconsequenceofTheorem4inAppendixB.Spatialstationarity,eventhoughnottotallygeneralisatechnicalassump-tioncommontomanystatisticalanalysisandcaptureswelllocalpropertiesofrandomprocesses. 3.1SourceModel Thissectionestablishesthebasicmodeluponwhichwewillbaseourasymptoticanalysis.LetS(t)denotetherandomvector{S(t)}i=Si(t)ofthesamplescollectedbythesensorsattimet.Ourfirstassumptionis: (a)S(t)isaspatiallycorrelatedrandomGaussianvector∼N(0,R).Thesamplesaretemporallyuncorrelated. Thetemporalindependencecanbeobtainedifweassumethatthepowerspectrumofthedatacollectedintimeisband-limitedandthedataaresampledattheNyquistrate.Inanycase,itisnotarestrictiveassumptionandfurthergainsintermsofcompressioncouldbeobtainedexploitingthetemporaldependenceofthesam-ples.Becauseofthetemporalindependence,wewillfocusonone vectorofsamplesonlyS,andfromnowonwewilldropthetimeindex. Consideringi.e.d(S,S ˆasdistortionmeasurethemeansquareerror(MSE), )=S−Sˆ2,andputtingtheconstraintE(S−S ˆ2) R(D)=N1λn n=12logD(2) nwhere DKifK<λn,n= λ(3) notherwise. andKissuchthat NDn=D.(4) n=1 For N¯≤NsuchthatK<≥λn=1λn≥D,thereexistsannλn¯andKn¯+1,therefore: K=D−Nn=¯n+1λn n¯(5) and R(D)=n¯1λn 2logK. (6) n=1 Assumingagivencorrelationstructureamongsamples,compu-tationoftherate/distortionfunctionjustrequirescalculatingnu-mericallytheeigenvaluesofR.Thecovariancematrixisformed withthesamplesofthecontinuousmultivariatefunctionthatrepre-sentsthecorrelationbetweenthesamplestakentwoarbitrarypointsinthenetwork: {R}i,kE{SiSk}=R(xi,xk,yi,yk). (7) Theeigenvaluesu,withentries{u}i=u(xi,yi)satisfythefol-lowingequation: λ(N)u(N)(xNi,yi)= R(xi,xk,yi,yk)u(N)(xk,yk) (8) k=1 Thechallengesare:1)provingthattheeigenvalueofthecorrela-tionmatrixformedwiththissamplestendtotheeigenvaluesofthecontinuousintegralequation: λ(∞)u(∞)(x,y)=R(x,ξ,y,ν)u(∞)(ξ,ν)dξdν;(9)2)providingareasonablemodelforthecontinuousintegralequa-tionthatallowstoobtaintheasymptoticratedistortionbound.Tothisend,wepostulatethat (b)thecorrelationbetweenpointsin(7)isspatiallyhomogeneous: R(x,ξ,y,ν)=R(x−ξ,y−ν), (10) TheconsequentstructureofRonaregulargridisalsoknownasdoublyToeplitz,i.e.RisablockToeplitzmatrixwithblocksthatareToeplitzthemselves. Assumption(b)impliesthat λ (N)u(N) (x Ni,yi)= R(xi−xk,yi−yk)u(N)(xk,yk)(11) k =1 λ(∞)u(∞)(x,y)=R(x−ξ,y−ν)u(∞)(ξ,ν)dξdν.(12)TheadvantageofthismodelisthattheempiricaldistributionoftheeigenvaluesofRconvergesundermildassumptionstothe2-DFourierSpectrumof(10),asweseenext. 3.2 Asymptoticues DistributionoftheEigenval-Toaddressthefirstissuewehavefirsttorewrite(8)asaquadra-tureformulawhichapproximatetheintegralequation(9).Forageneralintegral,therewillbequadraturecoefficientsαisuchthattheapproximationof(9)holds: NR(xi,xk,yi,yk)u(N)(xk,yk)αk (13) k=1 ≈ R(x,ξ,y,ν)u(∞)(ξ,ν)dξdν. Inourcase,sincewewanttoexploretheconvergenceoftheeigen-valuesof(8)ratherthanhavinganaccuratenumericalintegration, wecansetαi=1/N.Infact,normalizingbyNbothsidesof(8)onecannotethatwhen(13)isvalidalsothefollowingapproxima-tionholds λ(N)/N≈λ(∞). (14) Theassumptionsfortheapproximation(13)thatsetupthelimitsoftheapproximationin(14)arespecifiedinthefollowingtheoremderivedfrom[10,Sec.5.4]: LEMMA1.Denotingbyλ(∞)anarbitraryeigenvalueof(9)andbyu(∞)(ξ,ν)thecorrespondingnormalizedeigenvector,forNsufficientlylargethereexistaneigenvalueofRsuchthat: N|λ(N)−Nλ(∞)|21 ≤Ni=1EN{R(xi,yi,ξ,ν)u(ξ,ν)}1+E{u2(ξ,ν)},(15) NwhereEN{f(x,y)}denotesthequadratureerror,i.e.: Nf(x,y)dxdy= f(xi,yi)αi+EN{f(x,y)}. i=1 Assumingthat: (c.I)Foranycontinuousf(x,y)thegrid(xi,yi)issuchthatwith αi=1/NthequadratureerrorEN{f(x,y)}→0;then(15)impliesthat: Nlim→∞ λ(N)/N=λ(∞). Besideprovidingthenecessaryassumptiononthegridfortheasymptoticanalysistohold,usingthetriangularinequalitythepre-viousLemmaallowsustoeasilyprovethefollowing: COROLLARY1.TheeigenvaluesofRandRcorrespondingtotwodifferentgridsaresuchthat |λ(N)−λ(N)1 N|2≤Ni=1 EN{R(xi,yi,ξ,ν)u(ξ,ν)} 1 1+EN{u2(ξ,ν)}N+NEN{R(xi,yi=1i,ξ,ν)u(ξ,ν)}1+E,(16) N{u2(ξ,ν)} Corollary1impliesthatwecanrelyonanygridthathasthesameasymptoticbehavior,suchasforexamplearegularlattice,andex-trapolatetheasymptoticbehavioroftheeigenvaluesfromthelatter.Undertheassumptionofecandefine: ψ(ξi,k,νi,k)R(xi−xk,yi−yk)={R}i,k, (17) Adoptingaregulargridcoveringthesquare√ofarea1,thespacingbetweenthemisxi−xk=ξi,k=(i−k)/Nandlike-wiseνi,k.Szeg¨o’stheorem[7]establishesthatasymptoticallytheeigenval-uesofaToeplitzmatrixconvergetothespectrumofthecorrelationfunction.Essentially,Szeg¨o’stheoremestablishesthattheeigen-functionsofanhomogeneouskerneltendtobetheFourierbasisofcomplexexponentials.TheresultcanbegeneralizedtothetwodimensionalcasewhenthematrixisdoublyToeplitz,i.e.: limλ(R)=ψ(ξ/√N,ν/√N)e−j2π(fξ+f nν)N→∞ dξdν(18)=NΨ(√Nf,√ Nf).(19)Beforeproceeding,asecondmodelingassumptionthereforeis:(c.II)Ψ(f,f)idbandlimitedwithrespecttof,fbandwidth≤ W,i.e.Ψ(f,f)=0for|f,f|>W. Withthisassumption,wecapturethenotionthatthelimitcovari-ancefunctionvariessmoothlyinspace. 3.3AsymptotictheNetwork RateDistortionFunctionof Theasymptoticrate/distortionfunctionisobtainedreplacingthesummationsin(5)and(6)withintegralsover(fx,fy).Specifically,becausetheeigenvaluesbecometion,therewillbepoints(fx,fyasymptoticallyacontinuous)whereK=NΨ(√Nfx,√func-denotethesetsofpointsf√ Nfy). √Letusxandfywhere0≤NΨ(Nfx,Nfy)≤KasI,i.e.: I{(fNΨ(√Nf√ x,fy):0≤x,Nfy)≤K}(20)andsimilarlyforI.LetusalsointroducethesetI ¯I ¯{(f√ √x,fy):NΨ(Nfx,Nfy)>K}(21)D K≈ N− INΨ(√√Nfx,Nfy)dfxdfy(22) ¯I dfxdf. yTherate/distortionfunctionis:R(D)=N NΨ(√Nf√) x,Nfy2¯log Kdfxdfy.(23) I Becauseof(c.II)theareasofbothIandI ¯aresmallerthan4W2/N.Thus,wehavethefollowinglowerboundonK(alsoillustratedinFig.5): D2 K≥ N−K4W N4W2⇒K≥ D N8W2 ,(24) Togetherwith(c.II),thisjustifiesthefollowingupper-boundontherate/distortionfunction: R(D)≤ N 2logNΨ(√Nf√x,Nfy)dfxdfy.I ¯D/8W2≤ 2W2log(ND−1sup(Ψ(fx,fy))8W2). (25) So,weseethatthetotalrate/distortionfunctionovertheentire networkisO(log(N/D)).Thisisverysignificant.D/Nisthe Ψ( N f)KII2WFigure5:OnedimensionalillustrationofhowthelowerboundonK fromeqn.(24)isobtainedbyboundingtheintegralsthatdefineKineqn.(22). averagedistortionpersample.Ifkeptfixed,thenthetotalamountoftrafficgeneratedbythenetworkisupperboundedbyaconstant,irrespectiveofnetworksize.Alternatively,ifwekeepthetotaldis-tortionDfixed,byconsideringincreasinglylargeNwelettheaveragedistortionD/N→0.Andtheamountoftrafficgener-atedbydoingthisgrows(L√onlylogarithmicallyinN,wellbelowthecapacityboundON)provedineqn.(1). 3.4 CompressiontheNodes Efficiencyvs.ComplexityatMotivatedbyhowmuchbelowcapacityisR(D)in(25),wearepromptedtoconsideraspecialcase:jointcompressiononlyalongroutesconsistingofstraightlines,insteadofjointcompressionovertheentirenetwork(asillustratedinFig.6).Theamountoftrafficgeneratedwillbeclearlyhigher,sincenowweareignoringallcor-relationsacrosslines.Buttheschemeisinherentlylesscomplex,andthereforeofinterestaswell. Figure6:Partitionofthenetworkintoindependentrows.Nodesre-encodetheirmessagesonlyiftheyareinthesamerow—acrossrows,dataisroutedwithoutanyformofprocess-ing.Notethattherowsarerepresentedonaregulargridforsimplicity[cf.Section2.2]. LetRIR(D)denotetherate/distortionfunctionofthedatagen-eratedbythewholenetwork,butundertheconstraintthatjointcompressionisperformedonlyacrossrows,ignoringdependenciesalongcolumns.Clearlywemusthave RIR(D)≤√NR(D)=O(√ N),sinceinthis(necessarilyloose)upperboundwepretendthateachrowproducesasmuchinformationastheentirenetworkdoes,andassumingtheaverageper-sampledistortioniskeptconstant.ThisisinterestingbecausewestillgetthegrowthrateofRIR(D)tomatchthatinthecapacityexpressionofeqn.(1).Therefore,weseethatwecansacrificesomecompressionefficiencytogainapo-tentiallybigreductionincomplexity,byhavingeachnodeprocess atmost√ NsamplesinsteadofN.Notealsothatbesidescom-pressionefficiency,whatweloseaswellistheabilitytoreducetheaverageper-sampledistortionbykeepingDfixedandincreas-ing√N,sincethisresultsinanextralogarithmictermmultiplyingNintheamountoftrafficgenerated,thusviolatingthecapacityconstraint. 4.CONCLUSIONS Inrecentworkonthetransportcapacityoflarge-scalewirelessnetworks,ithasbeenestablishedthattheper-nodethroughputofthesenetworksvanishesasthenumberofnodesbecomeslarge.Thisresultposesaseriouschallengeforthedesignofsuchnetworks—somehaveevenarguedthatlargenetworksarenotfeasible,pre-ciselybecauseofthisreason[9].Previousworkhoweverpointedoutthat,inthecontextofsensornetworks,theamountofinfor-mationgeneratedbyeachnodeisnotaconstant,butinsteadde-caysasthedensityofsensingnodesincreases—thiswasillustratedwithanexamplebasedonthetransmissionofsamplesofaBrow-nianprocess,witharbitrarilylowdistortion(evenwithvanishingper-nodethroughput),bymeansofusingdistributedsourcecodingtechniques[12]. Inthisworkwehaveshownanalternativeapproachtoworkaroundthevanishingper-nodethroughputconstraintsof[9].Thisnewapproachisnotbasedondistributedcodingtechniques,butin-steadisbasedontheuseofclassicalsourcecodescombinedwithsuitableroutingalgorithmsandre-encodingofdataatintermediaterelaynodes.Tothebestofourknowledge,thesearethefirstresultsinwhichinterdependenciesbetweenroutinganddatacompressionproblemsarecapturedinasystemmodelthatisalsoanalyticallytractable.Andakey(andenabling)stepinourderivationwastheconstructionofafamilyofspatialprocessessatisfyingsomefairlymild(andeasilyjustifiablefromaphysicalpointofview)regularityconditions,forwhichwewereabletoshowthattheamountofdatageneratedbythesensornetworkiswellbelowitstransportcapac-ity.Thisprovidesfurtherevidencethatlarge-scalemulti-hopsen-sornetworksareperfectlyfeasible,evenunderthenetworkmodelconsideredin[9]. APPENDIXA. ENTROPYANDCODING TheentropyofarandomvariableXwithprobabilitymassfunc-tionP(x)isdefinedas: H(X)=E{−log 2P(x)}=−P(x)log2P(x).(26) x Formultivariaterandomvariablesthegeneralizationisstraightfor-ward: H(X1,...,Xn)=E{−log2P(x1,...,xn)}. (27) Notealsothat,theentropyofavectorcanbedecomposedaccord-ingtothesocalledchainrule,resultingfromtheiteratedapplica-tionofthechainruleforprobabilityP(x,y)=P(x|y)P(y):H(X1,...,Xn)= H(X1)+H(X2|X1)+...+ H(X,...,X (28) n|X1n−1)≤H(Xi) i whichwasusedinFigure2.Theimportanceofthedefinitionof entropyliesinthefactthatitprovidesaveryaccurateanswertothefollowingquestionregardingdiscretedatasources(i.e.sourcesproducingsymbolsdrawnformadiscretealphabet): Whatistheminimumnumberofbitsnecessarytorep-resentthedatafromadiscretesourcesothattheycanbereconstructedwithoutdistortion? Theanswerisgivenbythethefollowingtheorem[5,Ch.5]:THEOREM1.TheexpectedlengthLofanyinstantaneousD-arycodeforarandomvariableXis: H(X)≤L Theproofofthetheoremisbasedontheexistenceofacodingtech-nique,Huffmancoding,isknowntoachievetheentropywithinonebitifonesymbolisencodedand,ifmultiplesymbolsareencodedtogether,theefficiencyofHuffmancodingtendstobe100%[5].Thistheorycannotbedirectlygeneralizedtohandlethecaseofanalogsourcesbecausetheirentropyisinfiniteevenifthesignalisadiscrete-timesequence.Infact,thesourcesignalcantakeanyrealvaluesothateachsamplestillrequiresinfiniteprecisiontoberepresentedexactly.However,onceacertainlevelofdistortionisaccepted,theminimumnumberofbitsnecessarytorepresentthesourcecanbecalculatedjustasrigorouslyasinthecaseofdiscretesources,resortingtotheparalleltheoryforanalogsourceswhichiscalledRateDistortionTheory. B. RATEDISTORTIONTHEORYINANUT-SHELL RateDistortionisbasedontheseminalcontributionofClaudeShannonwhotriedtoprovidedatheoreticalframeworkfortherep-resentationofacontinuoussourcethroughdiscretesymbols[13].Supposeamemorylesscontinuoussourceproducesarandomsam-pleSwithdensityp(S):thequantizationproblemboilsdownto representingSthroughdiscreteˆsothat,ifourmeasureofthedistortionisd(S,S ˆvaluesS ),ourmappingS→SˆissuchthatE{d(S,S ˆ)}≤D.ToquantifyhowmanybitsareneededtorepresentS ˆ,inhis1959paperShannondefinedthesocalledratedistortionfunction: R(D)= ˆmin I(S,S ˆ)(30) p(S |S):E{d(S,Sˆ)}≤Dwhere: I(S,S ˆ)=p(S,S ˆ)logp(S,Sˆ )S ˆp(S)P(S ˆ)dS(31) istheaveragemutualinformationbetweenSandS ˆ.Inthesamepaperheprovedthefollowingtwofundamentaltheorems:THEOREM2.Theminimuminformationratenecessarytorep-resenttheoutputofadiscrete-time,continuous-amplitudememory-lessGaussiansourcebasedonamean-squaredistortionmeasurepersymbol(singleletterdistortionmeasure)is: 1 Rlog(σ2S/D)if0≤D≤σ2g(D)=2S,0D>σ2(32)S. whereσ2 SisthevarianceoftheGaussiansourceoutput. THEOREM3.ThereexistsanencodingschemethatmapsthesourceoutputintocodewordssuchthatforanygivendistortionD,theminimumrateR(D)bitspersymbol(sample)issufficienttoreconstructthesourceoutputwithanaveragedistortionthatisarbitrarilyclosetoD. TheimplicationofthetwotheoremsaboveisthatR(D)isthemin-imumnumberofbitsthatcanrepresentSwithintheprescribedmean-squareerrorifthediscretecodeS ˆsourceisGaussian.Inotherwordsany thatrepresentsaGaussiansourceSwithamean-quaredistortion≤Dhas H(S ˆ)≥RS(D),(33) andthelowerboundisasymptoticallyachievable.Thefollowing importanttheorem,provenbyBergerin1971[2],generalizestheresultsbyShannon: THEOREM4.Therate-distortionfunctionofamemoryless,con-tinuous-amplitudesourcewithzeromeanandfinitevarianceσ2 Swithrespecttothemean-square-errordistortionmeasureisupper-boundedas: R(D)≤12 2log(σS /D)if0≤D≤σ2S.(34)Berger’stheoremimpliesthattheGaussiansourceistheonethere-quiresthemaximumencodingrate,ifthedistortionfunctionistheMSE.Hence,ifourdistortionmetricisthemean-squareerror,thecaseofaGaussiansourcehastobeseenasaworsecasescenario.Thetheoremsabovehavebeenextendedtomultivariatesourceswhichareanalogoustotheonesweconsiderinthispaper.Inpar-ticular,thesocalledinversewater-fillingresultusedinSection3isthedirectgeneralizationofTheorem2tothemultivariateGaussiansource. 3.REFERENCES [1]R.Ahlswede,N.Cai,S.-Y.R.Li,andR.W.Yeung.Network InformationFlow.IEEETrans.Inform.Theory,46(4):1204–1216,2000. [2]T.Berger.RatedistortionTheory,PrenticeHall,Englewood Cliffs,NJ. [3]J.H.ConwayandN.J.A.Sloane.SpherePackings,Lattices andGroups.SpringerVerlag,3rdedition,1998. [4]T.Cormen,C.Leiserson,andR.Rivest.Introductionto Algorithms.MITPress,1990. [5]T.M.CoverandJ.Thomas.ElementsofInformationTheory. JohnWileyandSons,Inc.,1991. [6]A.GershoandR.M.Gray.VectorQuantizationandSignal Compression.KluwerAcademicPublishers,1992.[7]U.GrenanderandG.Szeg˝o.ToeplitzFormsandtheir Applications.UniversityofCaliforniaPress,1958. [8]P.GuptaandP.R.Kumar.CriticalPowerforAsymptotic ConnectivityinWirelessNetworks.InW.M.McEneany,G.Yin,andQ.Zhang,editors,StochasticAnalysis,Control,OptimizationandApplications:AVolumeinHonorofW.H.Fleming.Birkhauser,1998. [9]P.GuptaandP.R.Kumar.TheCapacityofWireless Networks.IEEETrans.Inform.Theory,46(2):388–404,2000. [10]H.B.KellerNumericalMethodsForTwo-Point Boundary-ValueProblems.DoverPublicationsInc.,1992.[11]S.S.PradhanandK.Ramchandran.DistributedSource Coding:SymmetricRatesandApplicationstoSensorNetworks.InProc.IEEEDataCompressionConf.(DCC),Snowbird,UT,2000. [12]S.D.Servetto.LatticeQuantizationwithSideInformation. InProc.IEEEDataCompressionConf.(DCC),Snowbird,UT,2000.Anextendedjournalversion,withtitleQuantizationwithSideInformation:LatticeCodes, Asymptotics,andApplicationsinWirelessNetworks,hasbeensubmittedforpublication,andisavailablefrom http://people.ece.cornell.edu/servetto/.[13]C.E.Shannon,CodingTheoremsforaDiscreteSourceWith aFidelityCriterionInstituteofRadioEngineers,InternationalConventionRecord,Vol.7(Part4),pp.142–163,1959. [14]V.A.Vaishampayan,N.J.A.Sloane,andS.D.Servetto. MultipleDescriptionVectorQuantizationwithLatticeCodebooks:DesignandAnalysis.IEEETrans.Inform.Theory,47(5):1718–1734,2001. [15]Q.ZhaoandM.Effros.OptimalCodeDesignforLossless andNearLosslessSourceCodinginMultipleAccessNetworks.InProc.DataCompressionConf.(DCC),Snowbird,UT,2001. 因篇幅问题不能全部显示，请点此查看更多更全内容