Towards Ubiquitous Multihop Wireless Networks Addr

UNIVERSITYOFCALIFORNIASantaBarbaraTowardsUbiquitousMultihopWirelessNetworks:AddressingCapacityandSecurityChallengesADissertationsubmittedinpartialsatisfactionoftherequirementsforthedegreeofDoctorofPhilosophyinComputerSciencebyKimayaMittalCommitteeinCharge:ProfessorElizabethBelding,ChairProfessorKevinAlmerothProfessorSubhashSuriDecember2006TheDissertationofKimayaMittalisapproved:ProfessorKevinAlmerothProfessorSubhashSuriProfessorElizabethBelding,CommitteeChairpersonDecember2006TowardsUbiquitousMultihopWirelessNetworks:AddressingCapacityandSecurityChallengesCopyrightc2006byKimayaMittaliiiAcknowledgementsIwouldrstliketothankmyadvisor,Prof.ElizabethBelding,forguidingandencouragingmeovertheyears,havingcondenceinmyabilities,andgivingmethefreedomtoworkatmyownpaceonprojectsofmychoice.IfeelluckytohaveanadvisorwhohasnotjustbeenagreatmentorbutalsoafriendthatIcanalwaysapproachtotalkaboutanything.Thankyoualsoforbeingunderstandingandsupportivethroughdifculttimesinmylife,forintroducingmetoDAWG,andforbeingthecatalystinmakingmeavegetarian.Ithanktheothermembersofmydissertationcommittee,Prof.KevinAlmerothandProf.SubhashSuri,forallthetimeandefforttheyhaveinvestedinme.Thankyouforyouradditionalguidanceandresearchinsightsthroughtheyears,andforalwaysbeingtherewheneverIneededanyhelporadvice.IthankFredBaker,mymentorduringmyinternshipatCiscoSystems.Thankyouforsharingyourwealthofknowledgeandreal-worldnetworkingexperience,foralwaystakinginterestinmyresearchandprogress,andforofferingvaluableadviceandinsights.Iamfortunatetohavehadtheopportunitytoworkwithyou.IthankProf.BrianLevinefromtheUniversityofMassachusetts,Amherst,andProf.ClayShieldsfromGeorgetownUniversityfortheirhelpandguidanceinmyworkonsecurerouting.Itwasagreatexperienceworkingwithyou.ivIthankthefacultyoftheComputerSciencedepartmentfortheirteachingandsup-port,particularlyduringmyearlygraduateschoolyears.Igivespecialthankstotheadministrativeandtechnicalstafffornotjustalwaysbeingreadytohelp,butdoingsowithawarmsmile.ToallmypastandpresentcolleaguesattheMOMENTLab,thankyouforbeingsuchenthusiasticresearchersandgreatfriends.Youhaveprovidedafunandstimulat-ingworkenvironment,andcontributedsignicantlytomylearningthroughcountlessdiscussions,reviews,andbrainstormsovertheyears.Inparticular,IthankIanChak-eres,withwhomIhaveworkedcloselyonvariousresearchprojects.Thankyouforyourcontributiontowardstheresearchpresentedinthisdissertation,andforalwaysbeingtheretohelpwithanythingIneeded.Onthemorepersonalside,Ithankmyparentsfortheirlove,encouragement,andsupportallthroughmylife.Mumma,thankyouforallthesacricesyouhavemadetohelpmebewhereIamtoday.Daddy,thankyouforalwaysinspiringmetoexcel.Iwishmorethananythingthatyoucouldhavebeenheretoday,Daddy.Imissyouverymuch.TomyhusbandVishal,thankyouforbelievinginme,standingrmlybymysidethroughfairandfoulweather,alwaysencouragingmetodobetter,andlovingmenomatterwhat.Withoutyourlove,support,andsacrice,Iwouldnotbeheretoday.vIthankallofmyfamily-theSanzgiris,Mittals,Nagarsekars,Neurekars,andSing-hanias-fortheirconstantloveandsupport.Specialthanksareduetomygrandfather,SatishNagarsekar,forhiswordsofadviceandinspirationthroughtheyears.IamhappytohavenallyfullledyourdreamofseeingmegraduatewithaPh.D.Ialsogivespecialthankstomyparents-in-law.Yourunconditionallove,acceptance,andwhole-heartedsupportoverthepasttwoyearshasmeantmoretomethanIcanex-press.Finally,IwanttoacknowledgemybelovedcaninefriendsattheDogAdoptionandWelfareGroup(DAWG),whohaveaddedagenerousextra-helpingofloveandmeaningtomylifeinSantaBarbara.viCurriculumVitæKimayaMittalEducation2006MasterofScienceinComputerScience,UniversityofCalifornia,SantaBarbara.1999BachelorofEngineering(Honors)inComputerScience,BirlaInstituteofTechnologyandScience,Pilani,India.PublicationsKimayaMittal,ElizabethM.Belding,andSubhashSuri.”AGame-TheoreticAnalysisofWirelessAccessPointSelectionbyMobileUsers”.TechnicalReport2006-14,UniversityofCalifornia,SantaBarbara,November2006.KimayaMittalandElizabethM.Belding.”RTSS/CTSS:MitigationofExposedTermi-nalsinStatic802.11-BasedMeshNetworks.”Proceedingsofthe2ndIEEEWorkshoponWirelessMeshNetworks(WiMesh),Reston,VA,September2006.AmitP.Jardosh,KimayaMittal,KrishnaN.Ramachandran,ElizabethM.Belding,andKevinC.Almeroth.”IQU:PracticalQueue-BasedUserAssociationManagementforWLANs.”Proceedingsofthe12thACMAnnualInternationalConferenceonMobileComputingandNetworking(MobiCom),MarinadelRey,CA,September2006.viiKimayaSanzgiri,IanD.Chakeres,andElizabethM.Belding-Royer.”TheUtilityofPer-ceptiveCommunicationBetweenDistantWirelessNodes.”Proceedingsofthe2ndAnnualInternationalIEEE/CreateNetConferenceonTestbedsandResearchInfrastructures(Tri-dentCom),Barcelona,Spain,March2006.KimayaSanzgiri,IanD.Chakeres,andElizabethM.Belding-Royer.”Pre-ReplyProbeandRouteRequestTail:ApproachesforCalculationofIntra-owContentioninMultihopWirelessNetworks.”ACM/KluwerMobileNetworksandApplications(MONET)Journal,11(1),pp.21-35,February2006.HenrikLundgren,IrfanSheriff,PrashanthAravindaKumar,AndersonLam,JoshuaMiller,KimayaSanzgiri,andElizabethM.Beldin