Network Coding Capacity of Random Wireless Network

arXiv:0804.4284v1[cs.IT]27Apr2008SUBMITTEDTOIEEETRANSACTIONSONINFORMATIONTHEORY1NetworkCodingCapacityofRandomWirelessNetworksunderaSINRModelZhenningKong,StudentMember,IEEE,SalahA.Aly,StudentMember,IEEE,EminaSoljanin,SeniorMember,IEEE,EdmundM.Yeh,Member,IEEE,AndreasKlappeneckerMember,IEEEAbstractPreviousworkonnetworkcodingcapacityforrandomwiredandwirelessnetworkshavefocusedonthecasewherethecapacitiesoflinksinthenetworkareindependent.Inthispaper,weconsideramorerealisticmodel,wherewirelessnetworksaremodelledbyrandomgeometricgraphswithinterferenceandnoise.Inthismodel,thecapacitiesoflinksarenotindependent.Byemployingcouplingandmartingalemethods,weshowthat,undermildconditions,thenetworkcodingcapacityforrandomwirelessnetworksstillexhibitsaconcentrationbehavioraroundthemeanvalueoftheminimumcut.I.INTRODUCTIONTraditionally,informationflowinnetworkedsystemswastreatedlikefluidthroughpipes,andindepen-dentinformationflowswereprocessedseparately.Underthisassumption,foraunicasttransmission(onesourcenodetransfersinformationtoonedestinationnode),themaximumtransmissionrateisboundedbythesizeoftheminimumcutbetweenthesourceandthedestination.ThisresultisknownastheMin-CutMax-FlowTheorem,whichwasprovedbyMenger[1],FordandFulkerson[2]andEliasetal.[3].However,foramulticasttransmission(onesourcenodetransfersinformationtomultipledestinationnodes),thismaximumflowratecannotalwaysbeachievedbytraditionalstore-and-forwardroutingalgorithms,evenifeachsource-destinationpairhastheminimumcutwiththesamesize.Thatisbecauseinamulticasttransmission,somelinksinthenetworkmaybesharedbytheroutingpathsfordifferentsource-destinationpairs.Intheirseminalpaper[4],Ahlswedeetal.proposedanetworkcodingscheme,andshowedthatifweallowintermediatenodestoencodetheirreceivedmessagesandforwardthecodedmessagestotheirnext-hopneighbors,themaximumflowratecanbeachievedformutilcasttransmissions.Inadditiontotheinformationtheoretictreatmentof[4],networkcodinghasalsobeenstudiedinanalgebraicframeworkdevelopedbyKoetterandM´edardin[5],andacombinatorialframeworkproposedbyFragouliandSoljaninin[6].Codedesignfornetworkcodingschemeshasalsoattractedintenseinterest.In[7],LietThisresearchissupportedinpartbyNationalScienceFoundation(NSF)grantCNS-0626882,ArmyResearchOffice(ARO)grantW911NF-07-1-0524.Z.KongandEdmundM.YeharewiththeDepartmentofElectricalEngineering,YaleUniversity,NewHaven,CT06520,USA,(email:[e-mail],[e-mail]).S.A.AlyandA.KlappeneckerarewiththeDepartmentofComputerScience,TexasA&MUniversity,CollegeStation,TX77843,USA,(email:[e-mail],[e-mail]).E.SoljaniniswithBellLaboratories,Alcatel-Lucent,MurrayHill,NJ07974,USA,(email:[e-mail]).SUBMITTEDTOIEEETRANSACTIONSONINFORMATIONTHEORY2al.showedthatlinearcodesaresufficienttoachievethemaximumflowrateforaone-sourcemulticasttransmission.KoetterandM´edard,andJaggietal.constructedlinearmulticastcodesfornetworkcodingschemesin[5]andin[8],respectively.TheapproachofconstructinglinearcodesinarandomizedwayformulticasttransmissionswasproposedbyHoetal.in[9].Foradetailedreviewofnetworkcodinganditsapplicationsinmanyfields,e.g.,wirelesscommunication,contentdistribution,security,pleaseseethebookbyFragouliandSoljanin[10].Inmoststudiesonnetworkcoding,networktopologiesareassumedtobeknown.In[11],[12],Ramamoorthyetal.studiednetworkcodingcapacityforweightedrandomgraphsandrandomgeometricgraphs.Intherandomgraphmodel,eachpairofnodesareconnectedbyabidirectionallinkwithprobabilityp1independently[13],[14].Thecapacityofeachlinkisassumedtobei.i.d.accordingtosomeprobabilitydistribution.Intherandomgeometricgraphmodel,twonodesareconnectedtoeachotherbyabidirectionallinkonlywhentheirdistanceislessthanorequaltoapredefinedpositivevaluer,thecharacteristicradius[15].Eachlinkhasaunitcapacity.Forthesetwotypesofrandomnetworks,theauthorsshowedthatthenetworkcodingcapacityisconcentratedatthe(weighted)meandegreeofthegraph,i.e.,the(weighted)meannumberofneighborsofeachnode.Essentially,theresultsrevealaconcentrationbehaviorofthesizeoftheminimumcutbetweentwonodesinrandomgraphsorrandomgeometricgraphs.Relatedproblemshavebeenstudiedintheliterature,e.g.,[16]andreferencestherein.In[17],theauthorsstudiedageneralizedrandomgeometricgraphmodel,wheretwonodesareconnectedbyabidirectionallinkwithprobability1iftheirdistancedislessthanorequaltor00,andwithprobabilityp1ifr0d≤r1.Theyobtainedsimilarconcentrationresults.Thegeometricmodelsin[11],[12],[17]assumethatalinkexists(possiblywithaprobability)betweentwonodeswhenthenodesarewithineachother’stransmissionrange.Althougheachlinkhasadirection,asalllinksarebidirectional(i.e.,thelink(i,j)impliestheexistenceofthelink(j,i)),themodelinfactleadstoanundirectedgraphandconsiderablysimplifiestheresultinganalysis.Inaddition,interferenceamongwirelessterminalswasnotconsideredin[11],[12],[17].Nevertheless,inwirelessnetworks,duetonoise,interference,andtheheterogeneityoftransmissionpowers,significantlymoresophisticatedmodelsforlinkconnectivityareneeded.Forinstance,awidely-usedmodelforwirelesscommunicationchannelsistheSignal-to-Interfer