Multi-Channel Wireless Networks Capacity and Proto

Multi-ChannelWirelessNetworks:CapacityandProtocolsTechnicalReportApril2005PradeepKyasanurDept.ofComputerScience,andCoordinatedScienceLaboratory,UniversityofIllinoisatUrbana-ChampaignEmail:[e-mail]ngineering,andCoordinatedScienceLaboratory,UniversityofIllinoisatUrbana-ChampaignEmail:[e-mail]—Wirelesstechnologies,suchasIEEE802.11a,provideformultiplenon-overlappingchannels.Typicalmulti-hopwirelessnetworkconfigurationshaveonlyusedasinglechannelforthenetwork.Theavailablenetworkcapacitycanbeincreasedbyusingmultiplechannels,andnodescanbeequippedwithmultipleinterfacestoutilizetheavailablechannels.However,thenumberofinterfacespernodeisexpectedtobesmallerthanthenumberofchannels.Weestablishthecapacityofmulti-channelnetworksunderthisscenario.Wedevelopnovellinklayerandroutingprotocolsthataredesignedspecificallyformulti-channeloperation.Simulationresultsdemonstratetheeffectivenessoftheproposedapproachinsignificantlyincreasingnetworkcapacity,byutilizingalltheavailablechannels,evenwhenthenumberofinterfacesissmallerthanthenumberofchannels.I.INTRODUCTIONWirelesstechnologies,suchasIEEE802.11[1],pro-videformultiplenon-overlappingchannels.Multiplechannelshavebeenutilizedininfrastructure-basednet-worksbyassigningdifferentchannelstoadjacentaccesspoints,therebyminimizinginterferencebetweenaccesspoints.However,typicalmulti-hopwirelessnetworkconfigurationshaveusedasinglechanneltoensureallnodesinthenetworkareconnected.Formeetingtheever-increasingthroughputdemandsofapplications,itisnecessarytoutilizealloftheavailablespectrum,andthisrequiresthedevelopmentofnewprotocolsspecificallydesignedformulti-channeloperation.ThisresearchwassupportedinpartbyNSFgrantANI-0125859andaVodafoneGraduateFellowship.Wirelesshostshavetypicallybeenequippedwithonewirelessinterface.However,arecenttrendofreducinghardwarecosts[2]hasmadeitfeasibletoequipnodeswithmultipleinterfaces.Nevertheless,itisstillexpensivetoequipanodewithonededicatedinterfaceforeachchannel,asthenumberofchannelsmaybelarge.Evenifeachchanneldoesnothaveadedicatedinterface,currentlyavailablecommoditywirelessinterfaces(suchasIEEE802.11wirelessinterfacecards)canbeswitchedfromonechanneltoanother,albeitatthecostofaswitchinglatency,therebyallowingallchannelstobepotentiallyutilized.Thus,itisofpracticalinteresttodevelopanarchitectureandprotocolsforthescenariowhereinthenumberofinterfacespernodeissmallerthanthenumberofchannels.Pastresearchonwirelessnetworkcapacity[3],[4]hastypicallyconsideredwirelessnetworkswithasinglechannel,althoughtheresultsareapplicabletoawirelessnetworkwithmultiplechannelsaswell,providedthatateachnodethereisadedicatedinterfaceperchannel.Whennodesarenotequippedwithadedicatedinterfaceperchannel,thencapacitydegradationmayoccur,com-paredtousingadedicatedinterfaceperchannel.Inthispaper,wecharacterizetheimpactofnumberofchannelsandinterfacespernodeonthenetworkcapacity,andshowthatincertainscenarios,evenwithonlyasingleinterfacepernode,thereisnocapacitydegradation.Thisimpliesthatitmaybepossibletobuildcapacity-optimalmulti-channelnetworkswithasfewasoneinterfacepernode.Wheninterfaceswitchinglatencyisaccountedfor,capacity-optimalperformancecanbeachievedbyusingafewinterfacespernodeinsteadofjustasingleinterface.2Wealsodeveloplinklayerandroutingprotocolsformulti-channelnetworks.Oursolutionrequiresatleasttwointerfacespernodetosimplifyprotocoldesign.Weproposeanovelinterfaceassignmentstrategythatkeepsoneinterfacefixedonaspecificchannel,whileotherinterfacescanbeswitched,asnecessary,amongtheremainingchannels.Theuseofafixedinterfacesimplifiescoordination,whiletheswitchableinterfacesenabletheutilizationofalltheavailablechannels.Traditionalroutingprotocolsdonotaccountforchan-neldiversity.Forexample,whenshortest-pathroutingisused,akhoproutethattraversesallthehopsonasinglechannelhasthesamecostasanalternatekhoproutethatusesdifferentchannelsforeachhop.However,thethroughputofaroutethatusesasinglechannelonallhopscanbesubstantiallysmallerthanaroutethatusesmultiplechannels,onaccountofselfinterferencealongtheroute.Furthermore,whentheswitchinglatencyisnon-negligible,theroutingprotocolhastoaccountforthecostofinterfaceswitchingwhenselectingroutes.Ourproposedroutingprotocolisdesignedtochoosechannel-diverseroutes,whileaccountingforthecostofswitchinglatency.Evaluationsshowthatourproposaliseffectiveinutilizingmultiplechannels.Forexample,ourresultsshowthatevenwithtwointerfaces,afivechannelnetworkcanoffermorethanfive-foldimprovementoverasinglechannelnetwork.Theproposedlinklayerandroutingprotocolsaresimilartothealgorithmsusedintheconstructiveproofthatachievestheupperboundformulti-channelcapacity.Hence,theproposalsarevalidatedtobeaneffectivechoicebytheoryaswell.Therestofthepaperisorganizedasfollows.WedescriberelatedworkinSectionII.WepresentourtheoreticalresultsinSectionIII.CertaindesignissuesaredescribedinSectionIVandassumptionsmadearediscussedinSectionV.SectionsVIandVIIdescribethedetailsoftheproposedlinkandroutingprotocols.WeevaluateourprotocolsinSectionVIII.Wediscusspossib