无线mesh网络中一种路由算法及其容错性的研究

《无线mesh网络中一种路由算法及其容错性的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、lSSN1o09—3O44E—mail：info@CCCC．net．enComputerKnowledgeandTechnology电脑知识与技术http：／／www．dnzs．net．CllVo1．6，No．28，October2010，PP．7988-7989Tel：+86—551-56909635690964无线Mesh网络中一种路由算法及其容错性的研究龙艳(贵阳学院计算机科学系，贵州贵阳550005)摘要：该文研究了无线网状网络(WMN)中的路由算法及其容错性能。考虑到网络中位置固定的节点，我们建议采

2、用准固定式的路由。这是一个基于并行计算，其鲁棒性和性能都优于传统Ad—hoc路由协议的路由形式我们还讨论了传输权力控制以及网络连接问题和网关的选择。关键词：无线网状网络(WMN)；无线Mesh网络：路由算法：容错性中图分类号：TP301文献标识码：A文章编号：1009—3044(2010)28—7988—02随着移动设备，诸如笔记本电脑，蜂窝电话和掌上电脑存互联网中的广泛应用，无线接人已经成为一个重要的需求。无线局域网已引起产业界和学术界的极大关注。各种标准已经建立起来了，尤其足IEEE802．11，还有一些

3、标准仍在制定中。在IEEE802．11标准中，有两个无线接入方式：基础结构模式和Ad—Hoc模式。在前一个模式中，局域网有一个集中的网络设备，我们称为接入点．它使用有线介质直接连接到互联网(通常是以太网双绞线)，它作为互联网各个节点问数据包收发的一个无线接口。而在Ad—hoc的模式中则没有这种集中化的设备，全部站或节点都以对等模式运行，并且争夺共享的无线带宽。通过这种方式，它们在所属区域内能够相互进行交流，但却无法访问外部网络。在实际使用中，另一种情况会出现：在区域网络中的所有用户需要在本地尝试连接到互联网，

4、但其中有一些又超出了接人点一跳传输的范围。这种情况通常发生在有线上网太贵以至于网络难以覆盖，像利用率低或布线费用高等种种情形之下。在这种情况下，已经接人Internet的接人点由于频繁的被访问更类似于网关，这种网络就被称为无线网状网络(WMN)。无线网状网络是一种网络中的节点可通过一个或者多个网关接人互联网的移动Ad—hoc网络。尽管传统的那些像DSR和AODV协议等Ad—hoe路由算法可在无线网状网络中使用，但其性能比通常不够理想。其存在的问题是这些算法中的假设在WMN中不是正确的。而且这些假设在无线网状网

5、络环境中对传输性能导致了明显的弊端。1WMN中的路由分析我们可以采用准XY无线网状网络路由算法。xY路由通常使用计算机网或环面拓扑以避免虫洞路由的死锁iJjc在使用这类网格拓扑结构的无线网状网络中，每个节点直接路由至其邻节点。例如，图l中的一个节点(x，Y)，其直接的相邻节点为x一1，y)，(x+1，y)，(x，y-1)，x，y+1)，每个节点都为其相邻节点与网关执行数据包收发的任务。分组延迟是由于多种原因造成的，然而在WMN中最关键的原因是路径长度。在相同流量条件下，一个较小的数日的跳数能够导致较短的包延迟

6、。对于在网格网络中S(x，ys)和D(xyo)两个节点，其最短路径如下：d=Ixs—xd+lys—yDI(1)为了尽量减少包的延迟，我们希望使用最短路径。然而这必须在最小范围的碰撞内，因为作为最短路径的高竞争路径往往不一定是理想的。因此，我们提出了一个最短路径负荷平衡的不同路由。我们的协议如下：Step1：如果下一跳是网关，则传输与之竞争：否则：Step2：确定相邻节点的负荷：Step3：选择其中较轻负荷的路径为下一跳路径并传输：Step4：回到Step1。通过这种方式我们的协议实现了不同的路由。可用的路径数

7、量的确定可以根据下列定理得出：定理1：在WMN中，对于任何给定的两个节点S(x，ys)和D(xD，Yo)，都存在：Sllll如图1中不同路径都有距离dO)。证明：我们通过归纳来证明定理。如果没有一般性的损失，假设XS≤x。andY≤y．，。3jStep1：由于S(xs，ys)到xs'。)只有唯一一条路径，同样S(xs，Ys)~lJ(xys)也只有唯一一3l0l5jl条路径，则S(xs,ys)到xys+。)的最短路径数为2；3556Step2：假设从S到T(XT,yT)，最短路径数目为：l15∞l姑l62l56

8、l2652．(等]D又假设xs≤XTandys≤YT图1互异路由计算收稿日期：2010—08-177988，·网络■讯硬安全本栏目责任编辑：冯蕾第6卷第28期(2010年10月)ComputerKnowledgeandTechnology电脑知识与技术Step3：从SN(XT+，yT)，最短路径数目可被递归计算得：一Xs+1+—sI一Xs+1ilsyr—Ysj!从SN(x-r．y)，路径数为：‘一X