[硕士论文精品]基于wlan+mesh路由算法的研究与实现

基于WLANMESH路由算法的研究与实现中文摘要基于WLANMESH路由算法的研究与实现中文摘要随着2009年1月国内3G牌照的正式发放和全国各大城市无线城市建设如火如荼的开展，无线MESH网络因其自组织、多跳特性以及在无线覆盖范围上相对无线局域网卓越的优势，在这个时候得到了空前的发展。而作为MESH网络关键技术的路由算法也成了当前无线通信网络领域研究的重要热点。本文首先介绍了MESH网络的概念、优缺点及组网的体系结构，研究了一些常见的MESH路由算法及AODV路由协议的路由运作过程。然后详细叙述了以AODV路由协议为基础，在LINUX24为内核的部分AP代码平台上实现的连接建立、路由建立和路由维护等路由功能的具体设计思想和流程。最后展示了通过使用OMNIPEEK和IXCHARIOT软件完成的路由功能的验证测试和网络吞吐量的性能测试。在这次路由设计过程中，我们对通常的AODV路由协议做了一些符合实际应用的改进，主要为1通常AODV路由协议应用于网络层，为了提高路由运行和数据转发的速度，我们把它移植到了数据链路层。2AODV路由协议中的路由建立、路由维护操作是为MESH节点设计的，而实际应用中，不可避免的还要加入接入到MESH的STATION路由的计算。3AODV路由协议要求定时发送HELLO消息来更新节点的活动路由，这样无疑加大了报文开销，我们选择在查找发送报文路由表时，进行更新。4实际组网时，MESH设备的MESHID、信道等参数都有可能不同，在进行通信连接之前，需要验证这些参数，因此，我们又添加了连接建立功能。关键词MESH网络，无线局域网，AODV路由协议，内核模块，LINUX网桥作者薄大户指导老师朱艳琴RESEARCHANDIMPLEMENTATIONOFMESHROUTINGALGORITHMBASEDONWLANABSTRACTRESEARCHANDIMPLEMENTATIONOFMESHROUTINGALGORITHMBASEDONWLANABSTRACTWITHTHENATIONAL3GLICENSEISSUEDONJANUARY2009ANDWIRELESSCITYCARRYINGOUTTHECONSTRUCTIONINFULLSWINGINTHEMAJORCITIESOFCHINA,WIRELESSMESHNETWORKSHASBEENALLUNPRECEDENTEDDEVELOPMENTATTHISTIMEBECAUSEOFITSSELFORGANIZATION,MULTIHOPANDEXCELLENTADVANTAGEOFWIRELESSCOVERAGECHARACTERISTICTHANWLANASAKEYTECHNOLOGYOFMESHNETWORK，MESHROUTINGALGORITHMHASBECOMETHEIMPORTANTRESEARCHHOTSPOTINTHECURRENTFIELDOFWIRELESSCOMMUNICATIONNETWORKSTHISPAPERFIRSTLYINTRODUCESTHECONCEPT，CHARACTERISTICANDNETWORKINGARCHITECTUREOFMESHNETWORKS，STUDIESSOMECOMMONLYUSEDMESHROUTINGALGORITHMSANDTHEOPERATIONOFAODVROUTINGPROTOCOLROUTINGPROCESSTHENITDESCRIBESTHESPECIFICDESIGNIDEASANDPROCESSESOFCONNECTIONESTABLISHMENT,ROUTEESTABLISHMENTANDROUTEMAINTENANCEFUNCTIONSINDETAILWHICHONTHEBASISOFAODVROUTINGPROTOCOLANDPARTCODEOFAPTHATPLATFORMEDWITHLINUX24KERNELFINALLYTHEPAPERDEMONSTRATESTHEVALIDATIONTESTINGOFROUTINGFUNCTIONSANDPERFORMANCETESTINGOFNETWORKTHROUGHPUTBYMAKINGUSEOFTHEOMNIPEEKANDIXCHARIOTSOFTWAREINTHEPROCESSOFROUTINGDESIGN,WEIMPROVEDTHENORMALAODVROUTINGPROTOCOLTOMEETTHENEEDSOFPRACTICALAPPLICATION，WHICHMALRAYINCLUDE1AODVROUTINGPROTOCOLISUSUALLYAPPLIEDTOTHENETWORKLAYER,INORDERTOIMPROVETHESPEEDOFROUTINGOPERATIONANDDATAFORWARDING，WETRANSPLANTEDITTOTHEDATALINKLAYER2ROUTEESTABLISHMENTANDMAINTENANCEOPERATIONSAREDESIGNEDORAYFORTHEMESHNODEINAODVROUTINGPROTOCOL，BUTONTHEACTUALAPPLICATION，WEINEVITABLLYJOINEDTHECALCULATIONOFROUTINGWHICHSTATIONSACCESSTOMESHDEVICE3AODVROUTINGPROTOCOLREQUESTTOSENDHELLOMESSAGESTOUPDATETHEACTIVITYOFNODEROUTINGFROMTIMETOTIME，WHICHUNDOUBTEDLYINCREASEDPACKETOVERHEAD，SOWECHOSETOUPDATEITBYCHECKINGROUTINGTABLEWHILESENDINGMESSAGE4ONTHEACTUALNETWORK，MESHIDANDCHANNELPARAMETERSARELIKELYTODIFFERABSTRACTRESEARCHANDIMPLEMENTATIONOFMESHROUTINGALGORITHMBASEDOILWLANBETWEENMESHDEVICESANDBEFOREMAKINGCOMMUNICATIONLINKSWENEEDTOVERIFYTHEM，THEREFORE，WEHAVEADDEDTHECONNECTIONESTABLISHMENTFUNCTIONFORROUTINGKEYWORDSMESH，WLAN，AODV,KERNELMODULE，LINUXBRIDGEIIIWRITTENBYBODAHUSUPERVISEDBYZHUYANQIN苏州大学学位论文独创性声明及使用授权的声明学位论文独创性声明本人郑重声明所提交的学位论文是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明韵法律责任。研究生签名暂盘乒日期型学位论文使用授权声明苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布包括刊登论文的全部或部分内容。论文的公布包括刊登授权苏州大学学位办办理。研究生签名錾垄乏日期型F讴基于WLANMESH路由算法的研究与实现第一章绪论第一章绪论11无线MESH网络的背景、现状及发展互联网技术和应用的相互刺激和不断促进，不仅带来了IP网络服务的爆炸式增长，还推动了运营了近百年的传统电路交换技术向分组交换技术的转变。IP覆盖技术和基于IP的各种服务，在过去二十年间，通过实现不同异构网之间的互联，在有线网络的应用上获取了巨大的成功。用户在享受上网带来的便捷和快乐的同时，还执着着对网络设备使用自由度的追求，如让笔记本像手机一样任意移动，在乘坐地铁或荒野有线网铺设不到的地方上网，这又要求了无线移动通信技术的支持。因此，IP网络与无线移动通信技术的结合便成为当前通信领域研究的重点。无线局域网WIRELESSLOCALNETWORK，WLAN【I】技术在距离有线网数百米范围的无线移动和连接接入上取得了丰硕的成果，但在有线网络覆盖不大或覆盖不到的郊区、山区、灾区及荒原等地方，在接入点的接入上完全依赖有线网的WLAN技术便望尘莫及了。需求是创新的根源，时势造英雄，因此，基于自组织、网状、多跳的无线MESH网络WIRELESSMESHNETWORK，WMN技术就应运而生了。WMN这个名词出现在上世纪末期，它源于应用军事领域的移动自组织网络MOBILEADHOENETWORK，MANETT21。由于ADHOE网络的节点移动性强、拓扑变化较快、易部署、自管理、不依赖于基础设施等特点，满足灾害、野战等场景需求，受到各大研究机构组织的强烈关注，但由于性价比的劣势没在民用设施中广泛应用。WMN作为一种新型网络结构形态，它可以与INTERNET、蜂窝网络、IEEE80211、IEEE80215、IEEES0216等网络很好的融合并克服传统无线网络如ADHOE、WLAN存在的一些固有缺陷。因此，WMN技术被纳入了2004年的80216、80216E和即将制定的8021LS标准。WMN优良的性能和广阔的前景，成为各大公司、研究机构关注的重点。2000年初，拥有ADHOC网络核心自主产权技术的ITT公司将专有技术转让给第一章绪论基于WLANMESH路由算法的研究与实现美国的MESHNETWORKS用于商业化产品的开发，该公司在此基础上开发了一系列具有自主知识产权的无线多跳网络民用产品一一WMN全套技术产品，并在市场上获得了极大的成功【31。与此同时，诺基亚、北电网络、摩托罗拉、TROPOS、SKYPILOT和FIRETIDE等多家公司开发的WMN产品相继问世。2005年MESHNETWORKS被摩托罗拉公司收归麾下【3】。2006年9月5日，思科连同IBM，SEAKAY和AZULSTARNETWORKS共同赢得了全美最大的无线网状网络项目一一在加利福尼亚州硅谷的总面积逾3900平方公里的土地上，使用WMN将240万居民连接在一起，为他们提供无处不在的无线网络接入服务以及大量新兴的公众服务【41。在中国，2007年，天津技术开发区采用无线MESH解决方案在全区范围内部署，完成后将实现多达200个监控点，覆盖30平方公里范围的无线视频监控。随着2009年1月3G牌照的正式发放【5】和无线城市建设在北京2008“无线奥运推动下从宏伟蓝图走向现实，广州与佛山的一体化城市建设推进了佛山无线城市建设的步伐，具有关消息透露，朗讯通信和深圳坤宇作为佛山无线城市的主建方之一，将构建中国第一个WIFIMESH无线城市图11中国无线MESH市场规模预测2007年全球MESH市场销售额为45亿美元【61，08年末MESH市场累积收入2基于WLANMESH路由算法的研究与实现第章绪论估计达10亿美元。中国WMN市场也从2005年起得到迅速发展，在30网络和无线城市建设的推动下，2011年累计市场规模将达到9亿人民币【7】【81，经年累计市场规模超过20亿人民币。12无线MESH网络路由协议的研究和开发现状无线MESH网络以其覆盖能力和链路可靠性方面的超强表现以及广阔的市场前景，迅速成为了世界范围内一项重要的研究热点，而作为实现其超强能力基础的WMN路由技术，也获得了国内外学术界和工程界的广泛关注。121国外研究现状当前国外对WMN路由协议的研究主要采用两种做法其一是根据WMN与无线ADHOC网络相似的特征，将ADHOE开发的路由协议直接用于或修改后用于WMN；另一种方法是研究专用于无线MESH网络的路由协议【9】。对于第一种做法，一般理解简单，实现起来也比较快捷，常见的做法是在传统的路由协议中修改或添加新的路由判据条件。例如一纽约州立石溪大学STATEUNIVERSITYOFNEWYORKATSTONYBROOK的ANANDPRABHUSUBRAMANIAN和朗讯贝尔实验室的MILINDMBUDDHIKOT及SCOTTMILLER于2006年提出了一种新的可感知干扰的路由判据条件一IAWARE【10】，最后将该判据条件应用在AODVADHOCONDEMANDDISTANCEVECTOR协议【11】【121中设计了一个增强的AODVMRADHOEONDEMANDDISTANCEVECTORMULTIRADIO路由协议LL引。韩国庆北大学KYUNGPOOKNMIONALUNIVERSITY的ANHNGOELE，DONGWONKUM等人于2007年11月提出了在AODV路由协议基础上采用定向转发策略限制报文洪泛的技术，并命名为DAODVDIRECTIONALAODV14路由协议。爱尔兰都柏林理工学院DUBLININSTITUTEOFTECHNOLOGY的MUSTAFARAMADHAN和MARKDAVIS于2009年6月的N2SNETWORKANDSERVICESECURITY国际会议上，发表了在MESH网络的DSRTL5。17LDYNAMICSOURCEROUTING路由协议中通过跨层设计加入带宽参数18】来和路由跳数共同作为路由判据条件的论文。第二种方法也大多从传统的路由算法中来，但更多地考虑了无线MESH网络自身的性能，比第一种有了更好的路由效果，不过，实现起来也比较繁琐。第一章绪论基于WLANMESH路由算法的研究与实现当然，也有的公司使用自己开发的私有协议。例如微软公司2004年研发的多射频链路质量源路由MULTIRADIOLINKQUALITYSOURCEROUTING，MRLQSR协议T3】【191，是在DSR路由协议基础上改进的，但它采用的在节点多信道传输中加入了加权累计传输时间WEIGHTEDCUMULATIVEEXPECTEDTRANSMISSIONTIME，WCETT的路由判据，就体现了WMN相对ADHOC网络节点移动性较弱【201的特点。总部位于硅谷的阿德利亚AZALEANETWORKS公司于2007年研发出了自己的私有路由协议一一自适应无线路由协议ADAPTIVEWIRELESSROUTINGPROTOCOL，AWR211，AWR是专为无线网状网设计的自适应的、分布式的主动路由协议。122国内研究现状在国内，由于国家政策支持和研究起步都比较晚，对于无线MESH网络的研究还处于初级阶段，目前还没有一家单位或公司研发出自己的私有协议。当然，也有少数的学者对WMN路由算法进行了深入的研究，提出了一些路由协议的改进协议。例如中国科技大学的YUNHU，SHOUBAOYANG等人于2006年提出了关于激励期望传输时间之和的路由判据条件，并基于该条件提出MPDSR22】路由协议【121。中国科技大学的张瑞，洪佩琳等人于2007年7月提出了一种叫做MEILT23】的WMN路由判据条件。该条件通过加权的方式，终合多路由尺度来考虑了无线信道的丢包率、链路干扰和节点的负载等多种重要因素对路径性能的影响。同时，作者提出了基于该判据条件的MEIL路由协议【12】。湘潭大学的PEITINGRUI，ZENGWENLI等人在2009年4月的NSWCTCNETWORKSSECURITY，WIRELESSCOMMUNICATIONSANDTRUSTEDCOMPUTING会议上，提出了将AODV路由协议应用于无线MESH网络混合结构的IHAODVIMPROVEDHIERARCHICALAODVT24】路由协议。123国内外开发现状自从2000年初，拥有ADHOE网络核心自主产权技术的ITT公司将专有技术转让给美国的MESHNETWORKS用于商业化产品的开发后，诺基亚、北电网络、4基于WLANMESH路由算法的研究与实现第一章绪论摩托罗拉、TROPOS及思科等多家公司都不断推出自己的WMN产品。因为无线MESH产品使用的外界环境差异性很大，在不同的环境下同样的MESH设备中可能会升级不同路由协议的软件版本或通过手动配置启用不同的路由协议。这些协议大多都是基于原用于ADHOC网络的路由协议基础上开发的，也有的公司使用自己的私有协议，如TROPOS公司在设计“WIFI蜂窝网络户外系统“时，就使用了自己开发的可预测的无线路由协议PREDICTIVEWIRELESSROUTINGPROTOC01PWRP3】【251。然而，正当国外各大企业在利用改进的或私有的路由协议开发MESH产品大展宏图的时候，国内还没有一家单位或企业MESH产品的成功应用案例。国内无线城市建设使用的MESH设备都依赖进口，这不能不说是一种压力。本人实习所在的公司也正是看到了这一情景和巨大商机，投入进对MESH路由协议的研究和产品的开发的。13本文的主要工作本文在分析和比较WMN常用路由协议基础上，根据所实习公司商用AP适用中小型组网规模的特点，采用了AODV路由协议为本次MESH设计的基本路由协议，又以基于LINUX24内核的APACCESSPOINT部分代码为平台，把AODV路由协议改进为符合无线MESH网络实际应用的算法。本文的主要工作1了解无线MESH网络的背景、现状及发展，分析WMN路由协议的国内外研究和开发现状，揭示在WMN路由协议研发中存在的问题。2研究WLAN及基于WLANMESH网络的应用、WMN的概念及优缺点，分析WMN的网络体系结构，比较并突出WMN相对其它网络的优势。3研究WMN路由协议不同分类的特点及WMN常用路由协议的原理，重点分析RFC3561版本AODV路由协议的具体实现过程，比较和突出AODV相对其它路由协议的性能优势。4分析MESH报文帧格式，思考总体设计方案，以LINUX24内核为平台，在现有AP代码的基础上，把原有应用在网络层的部分AODV代码，移植到链路层，实现连接建立、路由建立和路由维护等路由功能的具体设计。5第一章绪论基于WLANMESH路由算法的研究与实现5在真实环境中，以IXCHARIOT和OMNIPEEK软件为工具，依照实际工程测试标准，完成连接建立、路由建立、路由维护功能的验证性测试和系统吞吐量性能测试，并具体分析报文流程。14课题的意义国内外各大机构在MESH路由协议如火如荼的研究中，产生了一批质量很好的路由算法。但是，把这些路由算法真正应用到实际MESH产品中去的，尤其在国内，是寥寥无几。因此，虽然本文的路由改进设计没有上升到多少理论的高度，但把AODV路由协议，结合AP部分代码的基础，改进成为一种符合实际应用的MESH路由算法，具有了普遍的现实意义和重要的实践意义。又因为使用现有AP的成本低廉，市场广阔，本次设计还具有重大的市场意义。15论文结构全文共分为六章，各章内容安排如下第一章绪论。介绍选题背景、，现状及意义，论文的主要工作和安排。第二章基于WLAN无线MESH网络概述。介绍了基于WLANMESH网络的含义和特点，研究了MESH网络的体系结构，比较了与ADHOC、WLAN等网络的不同。第三章WMN相关路由协议分析。描述了路由环路故障的特点和解决方法，对一些常用的MESH网络路由协议进行分类、研究和比较，重点分析了AODV路由协议。第四章MESH路由算法的设计与实现。介绍设计使用的部分LINUX技术、MESH帧格式及路由设计的总体方案，重点讲述了MESH连接建立、路由建立、路由维护等功能的具体设计方法和流程。第五章测试与分析。搭建真实环境，对MESH的连接建立、路由建立及路由维护功能进行验证性测试和对网络的吞吐量性能进行了测试。第六章结束语。总结了本文的工作，并提出进一步优化路由设计的思想。6基于WLANMESH路由算法的研究与实现第二章基于WLAN无线MESH网络概述第二章基于WLAN无线MESH网络概述21基于WLAN无线MESH网络简介无线局域网WIRELESSLOCALAREANETWORKS，WLAN，顾名思义就是在局部区域内以无线媒介进行通信的无线网络。无线局域网又有广义和狭义之分。广义的无线局域网范围包括无线局域网WEAN、无线个人区域网WPAN、无线城域网WMAN和移动宽带无线接入网MBWA等。狭义的无线局域网主要指遵循IEEE80211系列协议标准的无线局域技术的网络。在这里我们主要讨论狭义的无线局域网，即WLAN。由于WLAN具有可移动性、扩展性强、传输速率高及与传统网络之间兼容性好等特点，使得WLAN在近些年得到了迅速的发展。WLAN在网络架构上可分为【26】基础结构模式、ADHOC网络及WDS模式。基础结构模式是由无线工作站和接入点共同组成的无线局域网模式。基础结构模式也称中心拓扑结构模式。接入点充当中心站，所有工作站对网络的访问均由其控制。每个工作站点都需在中心站覆盖范围内才可与其它站点通信。ADHOC网络是指无线工作站之间不需要使用中心接入点就能够直接相互通信的一种无中心拓扑结构模式，最简单的只要两台装有无线网卡的PC就可以组成一个单独的无线局域网进行通信。WDS架构也是使用中心拓扑结构模式，但与基础结构模式不同的是，它把有线或无线网络的数据，通过无线网络将其当做中继架构，传送到另一个有线网络或无线网络。WDS是无线局域网中一种应用比较广泛的架构模式。1997年6月，IEEE发布了针对无线局域网的IEEE802“标准，这是一个开放的无线局域网标准。最初IEEE80211业务主要限于数据存取，速率最高只有2MBITS，但随后提出的IEEE8021LB和IEEE8021LAG峰值速度分别可达11MBITS和54MBITS，IEEE80211N的速率可以达到300MBITS。虽然WLAN速度与有线局域网的千兆或万兆接入速率相比，还有很大差距，然而这个速率已经达到了用户使用的满意度。随着WLAN在技术层面的不断完善，其应用7第二章基于WLAN无线MESH网络概述基于WLANMESH路由算法的研究与实现也越来越广泛。但由于WLAN发射功率的限制如FCC定义的24GHZISM频段无线设备最大输出功率为1W126】，一个接入点的覆盖范围一般在几百米，因此通常采用增加接入点的办法来扩大网络的覆盖范围。而无线MESH网络通过MESH节点对数据的不断转发，把接入点的覆盖服务延伸了数千米，解决了覆盖问题，在现阶段国内外无线城市如火如荼的建设中颇受青睐。另外，在空旷、缺乏铜线光纤等有线资源的室外环境中，部署传统无线网络时，人们总是苦于难以寻找到合适的有线接入点，而传统WLAN中，每一个AP都需要通过有线接入点连接到有线局域网。MESH路由器的无线中继和用户接入功能轻易地解决了这个问题。在无线MESH网络技术不断发展过程中，国际标准化组织也开始着手在各种无线网络标准中加入对MESH组网方式的支持。目前，IEEE几个标准化小组都分别针对WLAN80211、WPAN80215、WMAN80216和MBWA80220成立了特别任务组。IEEE80211工作组于2004年5月成立了MESH任务组，编号为80211S【3】【271。这个工作组主要是为80211的MESH网络制定标准，扩展IEEE80211体系和协议，提供标准化的扩展服务集EXTENDEDSERVICESET，ESS的MESH功能。IEEE8021LS的目标是突破传统AP功能上的限制，使之具有MESH路由器的功能，业务流转发给邻近的AP进行多跳传输。这种方式决定了WMN具有较高的可靠性、较大的伸缩性和较低的投资成本等特点。这样，在新的WLAN架构中，WLAN的AP自动形成WLAN的WMN骨干网。传统无线局域网中的接入点AP也就变成了基于WLANMESH网络中的无线MESH路由器。22WMN的定义WMN即无线网状网是从移动ADHOC网络分离出来，并承袭了部分WLAN技术的高容量、高速率新型分布式宽带无线网络31，是建设新型公共无线局域网和宽带无线城市的第二代无线网状网。第一代无线网状网是采用交换技术的无线网状网【281，也就是在第二层进行AP和AP之间的数据交换。采用交换技术的无线网状网产品是一个无线交换机8基于WLANMESH路由算法的研究与实现第二章基于WLAN无线MESH网络概述和瘦AP的结合，它本身没有路由功能，必须有一个根节点来进行数据交换。由于这个原因，使第一代的无线网状网有很多缺陷如不能迅速收敛、浪费带宽、所有通信量通往同一网关造成信息阻塞及没有可选择的通路导致长延时熊寸OWMN是基于路由技术的无线网状网，它的拓扑是任意的，就像是渔网一样，从一个点到另一个点有很多路可以走。具有路由能力的无线网状网络反映出有线网络的结构，只是它通过射频而不是有线传输，每个MESH路由器不仅为覆盖区内连接的用户提供互联网接入，同时作为该网络的基本设施将数据通过无线网状网络路由到目的地，这几乎解决了第一代无线网状网上述的全部难题。而它以最少量的网络基础设施和互联成本扩展了网络的覆盖范围，提供移动业务漫游功能和耗费基础设施更少的网络路由功能，又是有线网络望尘莫及的。23WMN的主要优缺点231WMN的优点1可靠性和自愈性因为WMN的网状结构，如果某一条链路出现故障，节点可以自动转向其他可接入的链路，具有较高的传输可靠性和链路自愈能力。2自配置能力WMN是一种自组织网络，不需要或很少需要人工配制网络，因而，网络能够自动判断并更新网络相关配置【291。3非视距传输与发射台有直接视距的用户先接收无线信号，然后再将接收到的信号转发给非直接视距的用户。按照这种方式，信号能够自动选择最佳路径不断从一个用户跳转到另一个用户，并最终到达无直接视距的目标用户。这样，无线MESH网络能够非视距传输的特性大大扩展了无线宽带的应用领域和覆盖范围。4支持多种网络接入WMN即支持INTERNET接入同时又支持对等通信，同时还支持使用不同通信协议网络之间的通信。5网络的覆盖范围增大由于无线路由器和智能路由器的引入，终端用户可以在任何地点接入网络或与其他节点联系，因此接入点的覆盖范围大大增9第二章基于WLAN无线MESH网络概述基于WLANMESH路由算法的研究与实现加，频谱的利用率也大大提高，系统容量得到增大。6投资成本低，风险小。WMN的初建成本低，无线接入点和无线路由器一旦投入使用，其位置基本固定不变，节省了网络资源。WMN具有可伸缩性、易扩容、自动配置和应用范围广等优势，对投资者而言，短期内即可盈利。另外，WMN一般采用非许可证频段，为用户也节省了开支。232WMN的不足1分散管理问题；由于WMN的分散性，很难实现像有线网络那样的集中管理，即使对于低移动性的WMN，网络配置和管理仍然是一个不易解决的问题。2共存干扰问题对于非许可证频段的WMN必然存在与其他共存网络的无线干扰闯题。3安全问题与WLAN的单跳机制相比，无线MESH网络的多跳机制决定了用户通信要经过更多的节点，数据通信经过的节点越多，安全问题就越不容忽视。4互操作性目前影响无线MESH技术迅速普及的一个重要障碍就是互操作性。即因为标准的不统一与其它各种不同类型无线网络的设备接口问题，这个问题目前是影响无线MESH技术推广使用最重要的原因。5通信延迟因为在MESH网络中数据通过中间节点进行多跳转发，每一跳至少都会带来一些延迟，随着无线MESH网络规模的扩大，跳接越多，积累的总延迟就会越大。一些对通信延迟要求高的话音或流媒体应用等，可能面临无法接受的长延迟问题。目前解决这一问题主要是通过增加MESH节点及采用合适的网络协议。随着多无线MESH节点技术的出现这一问题将得到最终解决。24WMN体系结构一般而言，无线MESH网络由客户节点、MESH路由器节点和网关节点组成。根据具体网络配置，并不一定包括所有节点。客户节点可以是笔记本电脑、PDA、WIFI手机、RFID阅读器和无线传感器或控制器等；MESH路由器可以是普通PC，也可以是专用的嵌入式系统，如ARM等。客户节点按照功能可10基于WLANMESH路自算法的研究与实现第章基FWLAN无线MC女目络概连以分为两类；一类只作为普通终端接入网络，不具有转发信息的功能另一类既具有普通节点的接入功能，又具有路由和信息转发功能，即兼具了无线路由器的功能。按照结构层次，无线MESH网络可以分为平面、多级和混合结构13M卅。241平面结构由圈21可见，平面结构L如I中所有节点都是对等的关系，每个节点都包含相同的MAC、路由、管理和安全等协议，既可以接入网络，也可以转发其他节点的消息。网内的节点能够形成任意网状豹拓扑结构，节点也可以任意移动，网络的拓扑结构会动态的发生变化。在这种环境下，由于节点的无线通信覆盖范围有限，两个无法直接通信的用户终端可以借助其他终端的分组转发功能进行数据通信，而不需要借助其他基础设施。石FIR曩、|、昼曼二二二竺圈21WMN平面结构242多级两络结构图22所示为无线MESH网络的典型的多级结构130】，分为上下两层。下层的客户节点可以通过MESH路由器接入到上层MESH结构的网络中，实现网络节点的互连通信。MESH路由器提供路由选择和中继功能，为客户节点提供一条顺利连接到网关节点的无线链路。网关节点通过路由选择和管理控制等功能为移动终端选择与其他网络节点通信的最佳路径。这种结构的优点是可以兼容市场上已经有的设备，降低系统成本，提高了网络覆盖率和可靠性，缺点是任意两个终端节点之间不能直接通信。第章基于WLAN无线MCTDA日络概述基于WLANMCSH路由算法的研究与实现图22WMN多级结构243混合网络结构图23给出了混合网络结构示意图。在混合结构如1中，用户节点增加了具有转发和路由功能的MESH设备，之间可以实现无线互连。即终端节点设备需要同时能够支持接入上层网络MESH路由器和本层网络对等节点的功能。这是无线MESH网络最常见的组网结构，也是最有普遍研究意义的结构。R、嘲矿、一，掣一衢鳟么、目层，昼目一一一了，目习醴一L_直一_曰，、盈了，、，、盘目，。，篇基于WLANMESH路由算J击的研究与实现第二章基于WLA4无线MESH罔络概述，万玲、P8嘲器0、F、J乒J、一器芏塑芝，L，套、A日|一直一昼鱼1蔓二涉2S与其它网络的比较一般地，通信行业把从通信服务提供商的机房交换机到用户计算机等终端设备之间的线路连接叫做接入网，也就是人们常听到的“最后一公里”。对于接入网的研究一直是一个层出不穷的热门话题。接入网根据传输介质可以分为有线接入网和无线接入网。传统的无线接入方式主要有蜂窝网络和无线局域网等。但随着新应用需求不断扩展同传统无线接入网局限性之间矛盾的不断加深，无线MESH网络开始进入人们视野登上无线宽带接入技术的舞台。又由于第二章基于WLAN无线MESH网络概述基于WLANMESH路由算法的研究与实现无线MESH是由移动ADHOC网络转化而来，因此我们在表21中把上述四种无线接入网的特点进行了列举比较，通过表21我们可以对WMN的优势一目了然。表21四种网络特点比较网络吼小蜂窝移动网络WLAN移动ADHOC黼网络拓扑结构网状，多跳星型P2MP，单跳网状，多跳传输速度可达54MBPS3G静态时达8021LB11MBPS可达54MBPS2MBPS8021LG54MBPS8021IN300MBPS控制方式分布式控制集中式控制集中式控制分布式控制设计目的用户接入为用户接入及通信用户接入为主用户间通信为主主移动性移动性较弱固定固定任意移动自愈性强弱弱强投资成本较少较高大范围覆盖较高较少维护方便困难较方便方便应用主要商用商用主要商用军事，其它覆盖范围可覆盖城市视小区而定单AP覆盖数百米据实际应用而定26本章小结本章首先概述了无线局域网的应用及基于WLANMESH网络的特点，接着讲述了WMN的概念、主要优点和不足，然后分析并图示了平面、多级和混合三种WMN网络体系结构的特点，最后以拓扑结构、传输速度、自愈性、投资成本及覆盖范围等因素把WMN同蜂窝等网络相比较，突出了WMN网络的优势。14基于WLANMESH路由算法的研究与实现第三章WMN相关路由协议分析第三章WMN相关路由协议研究WMN路由协议是MESH研究的几项关键技术之一。WLAN是一个单跳网络，工作在链路层，对网络层透明，它的数据分组通过数据链路层进行处理，节点只具有接入功能。与WLAN不同，MESH网络的节点不仅能够覆盖，还要求有中继和转发能力。因此，一个合适的路由算法对于整个MESH网络的连通具有举足轻重地位。路由协议的主要任务是发现和维护从源节点到目的节点的路由，并指引数据分组从源节点正确的到达目的节点。与传统的宽带无线接入网相比，无线MESH网络具有网络拓扑结构动态变化、无中心需采用分布式控制、自组织、多跳路由和安全性差等特点。这些特点的结果带来了路由环路、路由开销大、链路动态变化不稳定等缺陷。我们设计算法时要充分考虑这些因素的影响。对于MESH路由协议的设计，主要是根据WMN与无线ADHOE网相似的特征，将ADHOE开发的路由协议结合MESH网络自身的性能进行改进后再用于WMN。也有公司开发私有的专用无线MESH网络路由协议，但这些协议一般比较繁琐，实现起来很不方便。本章仅就ADHOE及一些有线网络中可用于MESH的路由协议进行研究和分析。31路由环路介绍311路由环路的概念路由环路311是指数据包在一系列路由器之间不断传输却始终无法到达其预期目的网络的一种现象。网络拓扑发生变化时，若网络收敛缓慢产生不协调或矛盾的路径选择，路由器对无法到达预期目的的路由不予理睬，这样就会导致用户的数据包不停地循环发送。如图31所示，R0直接联网，R1与R0相连，假定R0为一目的节点，R1路由表中记录到R0跳数值为1，随后R1要把自己的路由表信息向邻节点广播。R2收到报文后，在自己的路由表中建立相应的路由并以跳数值2广播出去。最后R3得知该路由再以跳数3广播。15第三章WMN相关路由协议分析基于WLANMESH路由算法的研究与实现咽咽咽图31路由运行示意图现在假设R1到R0的连接失效了，如图32所示。那么RL在路由表中立即更新它到R0的距离为无穷大一般为16。在下一次广播时，RL就会通告这一信息。但是，除非协议包含了额外的机制预防此类情况，可能有其他的路由器在R1广播之前就广播了其路由。假设一个特殊的情况，即R2正好在R1与R0连接失效后通告其路由。因此，R1就会收到R2的报文，并对此使用通常的矢量距离算法它注意到R2有到达RO跳数更低的路由，计算得出现在到达R0的距离为3跳R2通告到R0的费用是2跳，R1到R0的距离要再加上到R2的L跳。然后在路由表中装入新的通过R2到达R0的路由。图32描述了这个结果。这样的话，R1和R2中的任一个收到去R0的数据报之后，就会把该报文在两者之间来回传输直到路由生存时间过期。312路由环路的避免囡翊明图32路由环路示意图常见解决路由环路的方法有触发更新、毒性逆转、水平分割和抑制更新时间等技术。DSDV和AODV路由协议采用了加入目的节点序列号的方法来避免路由环路。目的节点序列号由目的节点产生，目的节点每次因位置改变而与相邻节点断开连接后就会把序列号加1，而该相邻节点也会把目的节点序列号加L，并设其到目的节点的距离为无穷大。当节点收到多个不同的矢量表数据包时，采用序列号较大的，即较新的来计算，这样如上述R1与R0断开时，由于R1的目的节点序列号比R2高，R1就丢弃了R2发来的报文，即避免了路由环路，当序列号相同时则看谁的路径更短。因此使用目的节点序列号可以区分新旧路由，避免环路的产生。16基于WLANMESH路由算法的研究与实现第三章WMN相关路由协议分析32WMN路由协议的分类依据不同的标准，WMN路由协议有不同的分类方式。根据网络节点获取路由信息的方法，WMN可以分为表驱动、按需驱动和混合路由协议。按照网络节点使用且用于计算优先路由的信息类型，可以分为链路状态和距离矢量路由协议。根据路径选择中间节点是否参与计算，可以分为源路由和分布式路由协议【321。321表驱动、按需驱动及混和路由协议表驱动协议也称主动式或先应式路由协议，其最大的特点就是采用周期性的路由分组广播来交换路由信息。每个节点都维护一张包含到达节点的路由信息的路由表，并根据网络拓扑的变化随时更新路由表，以尽量实时准确的反映网络的拓扑结构。源节点一旦要发送报文，就可以立即获得到达目的节点的路由信息。但网络节点主动更新网络状态信息，并且通过路由广播和邻居节点探测保持各自路由表信息，这样维持“最新“网络拓扑信息开销巨大。这类协议又可再分为距离矢量类协议和链路状态类协议。前一类有如RIP，DSDV协议，后一类有OSPF，OLSR等协议。按需驱动路由协议又称为反应式路由。在这种路由协议中，节点根据发送数据分组需要进行路由发现，不需要维护及时准确的路由信息，当需要时才查找路由。如果该节点不存在到该目的节点路由，发起路由发现过程。该过程采用泛洪方式，向整个网络广播路由请求分组。当路由请求分组到达目的节点是，目的节点将向源节点发出路由请求应答分组。这样，在该路由中的每个节点建立了分别到源和目的节点的路由条目。按需路由协议包括DSR、AODV、ABR等WMN基本的路由协议。混和式路由协议，一般说来应用于分层网络结构。不同的结构层次比如，不同区域分别应用两种路由协议。这样可将链路变化限定在局部区域内，从而减少全网广播带来的开销。一般在区域内采用主动获取路由方式，而在全局范围内采用按需路由方式。17第三章WMN相关路由协议分析基于WLANMESH路由算法的研究与实现322链路状态和距离矢量路由协议链路状态路由协议是目前使用最广的一类域内路由协议。它采用一种“拼图”的设计策略，即每个路由器将它到其周围邻居的链路状态向全网的其他路由器进行广播。这样，一个路由器收到从网络中其他路由器发送过来的路由信息后，会对这些链路状态进行拼装计算，最终生成一个全网的拓扑视图，进而可以通过SPF算法来计算它到别的路由器的最短路径。距离矢量路由协议主要是基于BELLMANFORD最短路径算法的分布式路由协议。该协议中，每个节点维护一张到网络中已知节点的路由表，每个表项内容包括到已知节点的最小“距离”和下一跳节点，节点也按照邻居节点信息和最小距离原则更新自己的路由表并周期性向邻居节点广播自己的距离矢量表。这种算法适用于小型网络，最大缺点是相关路由协议收敛时间长，可能产生暂时的回路。DSDV协议便是此类协议的典型。323源路由协议与分布式路由协议在源路由协议中，每个数据分组中都添加了源节点到目的节点经过的所有节点的地址序列，中间节点不负责路由计算，而是按照路由序列转发分组。源路由的建立和维护都是由源节点负责。由于无线网状网的拓扑结构可能时常变化，为了使路由的计算节点保持准确的网络拓扑信息，网络将增加大量的更新消息，从而带来比较大的开销。但源路由协议可以避兔分布式路由协议中出现路由环等问题，而且简单、易于实现。因此，此种方式只适合于网络结构相对稳定的有线情况。在分布路由协议中，路由的计算由网络中的节点分布完成，并且路径信息被分布存储在网络各个结点中。网络中的节点根据自己的路由表进行消息的选择转发。分布路由协议的可伸缩性较好。然而，一些分布式路由协议如OSPF仍要求在网络节点中维护网络全局状态信息，这种协议不适合于拓扑结构变化频繁的网络。有一些分布式路由协议如TORA不要求结点维护网络的全局状态信息，但设计这类协议时应避免路由中出现路由环，或应在路由环出现时采取有效措施消除。18基于WLANMESH路由算法的研究与实现第三章WMN相关路由协议分析33WMN路由协议分析331DSR协议DSR是一种典型的按需路由协议【16】【171，它允许节点动态地发现到目的节点的多跳路由，但仅当源节点需要到目的节点的路由信息发送数据时，源节点才发起创建路由。DSR的特点在于使用了源路由机制，在每一个数据分组头部携带要经过的路由，路由器按照该路由序列来转发分组。DSR协议包括两个过程路由发现和路由维护。1DSR路由建立当一个节点欲发送数据到目的节点时，它首先查询自己的路由表看是否存在到达目的节点的路由。如果存在，则采用此路由发送数据。如果不存在，源节点以泛洪方式启动路由发现程序寻找路由。当节点S需要到节点D的路由时，节点S广播“路由请求”分组RREQ，每个请求分组通过序列号和节点S标识惟一确定。收到“路由请求”分组的节点，若不是目的节点或还没有接收过同样的路由请求分组或路由表中还没有到目的节点的路由信息，该节点都将自己的地址附加到“路由请求”分组头部的路由序列中，并将分组转发给所有相邻的节点。若请求分组头部的源路由序列中不包含一节点，而该节点接收过同样的路由请求分组，则节点将删除该请求分组，防止循环处理和出现路由环路。若该节点不是目的节点D，节点自己路由表中记录有到目的节点D的路由信息，节点将发送“路由应答”给节点S，应答中包含了从节点S到节点D的路由。节点S获取路由后，使用源路由进行数据通信。2DSR路由维护DSR支持链路层应答、网络层应答和被动应答三种链路状态监测方法，路由维护通过路由错误分组和确认分组来实现。当路由列表中的一个节点移出无线传输范围或已关机时，就会导致路由不可用。当上游节点通过MAC层协议发现连接不可用时，就会向使用这条路由的上游所有节点包括源节点发送一个错误分组RERR。源节点收到该RERR后，就会从它的路由缓存中删除所有包含该无效节点的路由。如果需要，源节点会重新启用路由发现程序来建立到原目标节点的新路由。除路由错误分组外，确认分组通过验证路由连接运行的正19第三章WMN相关路由协议分析基于WLANMESH路由算法的研究与实现确与否实现路由维护。332DSDV协议基于目的序列号的距离矢量DESTINATIONSEQUENCEDDISTANCEVECTOR，DSDVT33。51被认为是最早的自组网路由协议，它是在传统DV算法基础之上改进的一种路由算法。在DSDV网络中的每一个节点都保存有一个记录所有目的节点和到目的节点跳数的路由表ROUTINGTABLE。表中的每一个条目都有一个由目的节点生成的序列号SEQUENCENUMBER，用于避免路由环路和确保路由信息最新。除了在全网内周期性广播路由表更新分组外，当新加节点或有链路断开时，DSDV会立即发送更新信息到邻居节点。DSDV有两种更新报文方式，一是完全更新，发送路由表中的所有路由信息；二是增量更新，发送路由表中发生变化的表项包含在单独的分组中发送。第一种主要用于链路变化频繁状况，第二种用于节点移动较少情形。DSDV以序列号新和度量值小作为路由选择的准则。最新的路由信息总是序列号最大，当节点收到多个不同矢量表数据包时，总采用序列号最