基于综合判据的无线Mesh网路由协议.doc

1、计算机学报 2010，33（12）：2300-23111基于综合判据的无线 Mesh 网路由协议 1沈呈 1,2，陆一飞 1,2，夏勤 1,2（1东南大学计算机网络和信息集成教育部重点实验室，江苏南京 210096；2东南大学计算机科学与工程学院，江苏南京 210096）摘 要： 为用户提供高质量，高性能的通信链路是无线 Mesh 网路由协议所面临的重要挑战，而当前从 Ad Hoc 网络沿袭下来的路由协议并不能够满足无线 Mesh 网的性能要求。本文以 OLSR 协议为原型，结合跨层优化理论，为基础设施架构的无线 Mesh 网提出了一种新颖的、基于综合判据的路由协议。该协议通过跨层操作机制综合

2、考虑无线链接的长度及通信效率对链接性能的影响，从而达到优化路由选择的效果。仿真结果表明，所提出的路由协议能够有效地提高网络中分组的递交率，降低端到端的延时，并且能够在一定程度上达到负载均衡的路由效果。关键词： 无线 Mesh 网；路由协议；跨层设计；先验式路由1 引言无线 Mesh 网（Wireless Mesh Network，简称 WMN）是一种新型的分布式宽带无线网络架构，能够实现家庭宽带个域网、楼宇自动化网络、社区组网、交通医疗系统网络、校园组网、企业组网以及城域组网等多层次、大范围的无线应用。当前，国内外的许多研究机构和相关厂商都对无线 Mesh 网技术进行了广泛的研究，相关的标准也

3、在积极制定中 1。通常来说，无线 Mesh 网有三种拓扑架构，分别为基础设施/骨干 WMN 架构、客户端WMN 架构和混合 WMN 架构。其中，最常见的，也是应用最多的，是基础设施/ 骨干WMN 架构，它被广泛地应用在无线城域网的建设中，本文中所有的论述都是针对这种架构进行的。图 1 显示了基础设施/骨干 WMN 架构的无线 Mesh 网的组成。从图中可以看出，这种架构被分为三层，最低一层为终端用户层，各种终端用户设备，如手机、笔记本电脑、PDA 等通过各种标准接入技术接入到无线 Mesh 网；中间一层为无线 Mesh 层，由无线接入点（Mesh Access Point，MAP）和超网关节点

4、（Super Gateway，SGW）组成，这些节点相互连接形成一个自组织、自配置的无线骨干网。终端用户可以通过该层接入到核心网络，也可以通过该层进行彼此间的通信。为了达到这个目标，需要为该层设计一个高效可靠的路由协议，这也正是本文所关注的问题；最上面一层是核心网络层，主要提供各种网络互联服务 2。作者简介：沈 呈（1982） ，男，博士生，研究方向为移动通信与无线网络技术。联系方式：Email: ， 基金项目：国家自然科学基金重大研究计划项目(90604003)、国家自然科学基金项目 (60603067)、高等学校博士学科专项科研基金资助课题(20090092120029)。计算机学报 20

5、10，33（12）：2300-23112图 1 基础设施/ 骨干 WMN 网络架构如前面所述，基础设施/骨干 WMN 架构的无线 Mesh 网大多被运用在社区组网、城域组网等交互性强、普适性高、性能敏感的应用场合。而且随着互联网的发展，网络服务呈现多元化趋势，特别是具有实时性要求的多媒体业务，如语音、视频等近几年得到了迅猛的发展。这样复杂的应用场景和多样的业务需求也就给无线 Mesh 网，特别是其中无线Mesh 层的路由协议设计提出了更为苛刻的性能要求 3。近年来的研究表明，传统的网络分层设计方法，对于无线 Mesh 网这样的无线网络来说，并不是有效的设计方法。这主要是由于无线信道的开放性和信

6、道参数的时变性使得分层设计方法无法保证网络资源的利用率和用户业务的 QoS 需求。而且传统的路由协议基于“最小跳数”的选路机制，存在许多不足之处，例如无法有效地控制拥塞现象、公平性很差、不能实现负载均衡等等。因此，利用跨层设计的思想来实现新的路由协议，改进上述不足之处，从而进一步提高无线 Mesh网的性能，是本文的主要出发点。本文结合跨层优化理论，提出了一种适用于无线 Mesh 环境的综合判据，并以此为基础，为无线 Mesh 网的无线 Mesh 层设计了基于综合判据的自适应路由协议IMAR（ Integrated Metrics based Adaptive Routing） 。论文的后续部分

7、安排如下：第 2 部分讨论了相关的研究工作；第 3 部分给出了综合判据的定义，并且详细介绍了 IMAR 协议的实现；第 4 部分对协议进行了仿真实验及结果分析；最后部分对全文的研究工作进行了总结。2 相关工作2.1 网络层路由协议当前，无线 Mesh 网作为一种新兴的网络技术，其路由协议的研究和设计尚未形成统一的标准，大多数现有的无线 Mesh 网路由协议都是从 Ad Hoc 网络的路由协议发展而来的。因此，和 Ad Hoc 类似，目前无线 Mesh 网的路由协议根据路由的生成时间可以分为先验式和反应式两大类，根据分组的转发机制又可以分为逐跳（hop-by-hop）和源路由两大类。在无线 Me

8、sh 网的无线 Mesh 层中，网络节点相对固定，只有无线接入点的故障、加入和退出以及无线链路的一些不确定性会造成网络拓扑的变化，网络拓扑变化的速率要远远低于数据流的到达速率，并且无线 Mesh 网中的主流业务为存在一定延迟要求的 Internet 业务。基于这样的网络环境，Yaling Yang 等人在文献4中给出论证：先验式的逐跳路由协议最适合无线 Mesh 网。计算机学报 2010，33（12）：2300-23113OLSR5（Optimized Link State Routing）就是一种典型的先验式逐跳路由协议，其融合多点转播技术 6，对传统的链路状态路由协议做了两方面的改进：一是

9、在节点构造拓扑控制分组的时候，对所包含的局部拓扑信息进行有效的压缩，可以减少传输拓扑控制分组所需的带宽开销；二是在拓扑控制分组的广播过程中采用多点转播技术来代替泛洪，能够在达到相同广播效果的同时，大大降低广播操作所造成的开销。这两点改进都旨在减少路由维护操作给网络带来的额外开销，能够在很大程度上减少路由协议所占用的网络资源。然而，OLSR 路由协议在进行路由选择时主要考虑“最小跳数”这个约束条件，却忽略了无线链路的可靠程度以及路径上节点的繁忙程度，这样容易导致如下的问题：（1）协议倾向于选择跳数少的路径以减少其中的转发次数，这样容易导致每跳的距离相应增大，对于无线传输来说，对端节点间的距离一定

10、程度上决定了单跳链接的质量，过大的传输距离势必会导致无线干扰增大，数据传输率降低，所以，好的路由判据需要在跳数和每跳距离间作出权衡；（2）网络中的流量容易集中于某些链路，从而形成一些“热区” ，在这些“热区”中容易出现网络拥塞，导致经过这些区域的数据包经历严重的延迟甚至被丢失，而与此同时，网络中的其它一些节点和链路可能长期处于空闲状态，这些潜在的网络资源没有得到有效的利用。因此，对于无线 Mesh 网来说，OLSR 路由协议的性能还达不到理想的要求。近几年，有不少学者对 OLSR 协议进行了深入的研究，并针对无线 Mesh 网络的特点对其进行了优化。例如：文献7提出了一种新的路由判据，叫做信号

11、噪音比，并将其运用于 OLSR 协议，实验表明，和最小跳数相比，该判据能够提高无线 Mesh 网的整体性能；文献8设计了一种 OLSR 扩展路由协议，其中包含了一套节点信誉管理框架，协议采用节点信誉作为路由判据，能够缩短网络中的端到端延时；文献9对 OLSR 协议进行了改进，使其支持多信道多收发器配置，并在路由选择过程中融入了对路径质量的考量，从而提高了协议的综合性能和可扩展性。上述的这些 OLSR 改进方案，大多已经跳出了以最小跳数作为路由判据的传统套路，且或多或少地引入了跨层设计的思想，但是也存在着一些不足之处，例如：路径的评判标准相对单一；没有考虑节点处理能力对路径质量的影响；缺乏对网络

12、负载平衡特性的关注等。因此，针对这些不足之处进行改进，从而进一步提高无线Mesh 网路由协议的性能，成为下一步研究的一种可行思路。2.2 跨层优化设计网络协议跨层设计的核心思想在于：维持层间分离准则的同时，放松对分层结构的严格要求，允许不同层的算法共享网络的状态信息，这样有利于层内和层间操作的优化，从而使得网络的整体性能，如运行效率、资源利用、QoS 保证、安全协作和能量管理等，有较大程度的促进（如图 2（a）所示） 。应用层数据链路层物理层网络层传输层系统分层约束跨层设计应用层数据链路层物理层网络层传输层系统分层约束参数调用模块参数采集模块I M A R 中的跨层设计(a) 网络协议的跨层设

13、计 (b) IMAR 协议中的跨层设计图 2 跨层设计示意图计算机学报 2010，33（12）：2300-23114至于跨层设计思想在网络层路由协议中的应用，主要体现在网络层与数据链路层之间的跨层设计上，映射到实际应用中，这种跨层设计又直接反映到跨层路由判据的设计上来。如前面所述，在无线 Mesh 网中，采用传统的“最小跳数”作为路由判据，不足以达到良好的路由效果，即网络吞吐量、端到端延时和可靠性等性能指标达不到理想的要求。原因在于“最小跳数”路由判据没有考虑到物理层无线信道参数的变化对 MAC 层接入性能的影响，造成所选路径无法适应链路质量和节点状态的变化，从而导致路由性能的衰减。而融合了跨

14、层设计的路由判据，由于其收集了低层的链路质量信息来作为路由决策时的依据，所以和“最小跳数”相比，有较为明显的性能优势。例如：文献10利用 IEEE802.11 的自适应速率切换机制，节点建立路由时以物理层的数据传输速率作为判据，从而建立高速率、低延时的路由；文献11通过减少干扰来找到高吞吐量的路径，并通过最优化传输功率的方法增加路径的可靠性；文献12 ，13 综合考虑节点的剩余带宽，当前负载，以及缓冲队列饱和度等因素，对无线 Mesh 网络中的反应式路由协议进行优化，从而提高网络的吞吐率和负载均衡能力；文献14将跨层设计的思想扩展到多信道无线 Mesh 网络中。以上的方法有一个共同特点：它们在

15、进行跨层设计时，都是从“节点”的角度出发，对单个节点的性能指标进行衡量和优化。但是，在实际的数据传输过程中，单跳传输的质量和性能是由发送方和接收方两者共同决定的，因此，从“链接”的角度来优化跨层设计，是一个值得探索的研究方向。3 基于综合判据的自适应路由协议 IMAR如前面所述，OLSR 协议具有较高的运算效率，但是路由判据先天的不足使得其无法满足无线 Mesh 网的性能需求，而跨层优化机制在改进算法机理，提高协议性能方面有着显著的效果。因此，本文基于 OLSR 协议的优点，融合跨层设计思想，为无线 Mesh 网的无线 Mesh 层提出了一种易于实现、性能优良并能够动态处理网络变化的基于综合判

16、据的自适应路由协议 IMAR。首先给出网络模型：考虑一个由 N 个无线接入点组成的无线 Mesh 层，在这里，为了简化模型，讨论路由问题时，将超网关节点（SGW ）当作普通的无线接入点来对待，忽略其网关作用。同时，在路由计算过程中，只考虑具有双向性的无线链接，忽略其它不对称的单向链接。对应到图论中，该无线 Mesh 层可以用二维平面内的无向图 G（ V， E） 来表示，其中 V 为图中的顶点集合， vV 表示网络中的一个无线接入点，E 为图中边的集合，e E 表示网络中 v 和 v 之间的一条无线链接。我们假设网络中的无线接入点均是同ijij构的，对于每个无线接入点都增加了两个跨层模块，如图

17、2（b）所示。参数采集模块负责在数据链路层上收集无线接入点的状态信息，例如负载情况等。参数调用模块负责为网络层路由协议提供各种统计信息的数据接口。3.1 综合判据从节点层面来看，无线接入点的负载情况反映了其当前的繁忙程度，网络流量应该尽量选择相对空闲的无线接入点，从而避免出现网络拥塞；从链接层面来看，对端无线接入点之间的距离决定了通信链接的质量，距离过大会加剧链接上的信道干扰并导致较低的数据传输率，另一方面，对端无线接入点都相对空闲的通信链接将会拥有较高的传输保障，从而表现出更高的通信效率。因此，无线 Mesh 网路由协议应该采纳自适应负载均衡设计，尽量选择对端无线接入点距离近且相对空闲的通信

18、链接组成路由。IMAR 路由协议中提出了一种描述无线接入点 v 和 v 之间通信链接性能优劣的综合ij判据 ，其值越小，表示链接的综合性能越好。给出 启发式的定义，如公式（1）ijIMiIM所示：计算机学报 2010，33（12）：2300-23115（1）)(), 2jijiij LjdIM其中， 、 为预设的指数， 表示 v 和 v 之间的距离， 和 分别表示 v 和 v(ij iji的空闲度，其反映了无线接入点当前的繁忙程度，它的启发式定义借鉴了文献15中对于j节点空闲度的定义，如公式（2）所示：= iL2iRcvTx（2）其中， 称为无线接入点的发送率（Transmission Rat

19、e） ，代表无线接入点 MAC 层数据iTxR帧的发送速率； 称为无线接入点的接收率（Receiving Rate） ，代表无线接入点 MACicv层数据帧的接收速率。由于接收是发送的前提，所以在公式（2）中赋予 更高的阶数iRcv以体现这种主导作用。在算法中，这两个参数是通过跨层操作机制获得的，每隔 T 秒的采样时间，协议计算无线接入点发送和接收数据帧的速率。在我们的工作中，T 被设置为6s。在实际的应用场景中，可以使用指数加权移动平均法对 和 进行平滑处理，iTxi如公式（3）和（4）所示：sampleoldi RTxR)1(（3）slli cvcvcv（4）为了更好地反映无线接入点的当前

20、状态，上式中的 设置为 0.3，从而给当前的采样值更高的权重。由公式（1）可知，综合判据由 和 两部分组成，前者间接反),(jid2jijiL映了链接上的通信干扰及数据传输率，后者表述了无线接入点之间链接的通信效率。在本文中，当一条链接的两端无线接入点的空闲度处于较高或平衡的状态时，我们认为这两个无线接入点当前的处理能力都较强或者至少相互匹配，这样的链接拥有较高的传输保障，从而表现出较高的通信效率。反之，如果链接两端无线接入点的空闲度差异过大，由于传输质量由发送方和接收方共同决定，所以空闲度大的节点会被空闲度小的节点所拖累，导致资源的浪费，链接的通信效率降低。从下面定理 1 的证明可知表达式确

21、实能够用来表示本文所定义的链接通信效率。2jijiL定理 1 当一条链接的两端无线接入点的空闲度处于较高或平衡的状态时，的值较大。2jiji证明：假设网络中存在两条链接分别为（v ，v ）和（v ，v ） ，分别比较以下两种pqmn情况下两条链接所对应的 取值，分别用 和 表示：2jijiLpqU(a) 当 且 时，令 。在此)()(nmqpLnmqpnLL前提下，也即mnmqp 4)()(4 2222 。将无线接入点对的空闲度乘积视为新的参数 ，显然有 ，nqp e,0计算机学报 2010，33（12）：2300-23116此时， 可以表示为函数 ，由于其一阶导数在定2jijiLeef2)(

22、1义域内取正值，所以 呈单调递增，由此可知必有 。这说明：当链接两)(1ef mnpqU端的无线接入点空闲度的平衡状态（这里体现为两者的差值）一定时，空闲度较高的链接对应的 值较大。2jiji(b) 当 且 时，令 。与)()(nmqpLLnmqpLCLnmqp)()(（a）部分类似，可qpCC4)(4 2222 以得到 。同样，将无线接入点对的空闲度乘积视为新的参数 ，nmqpC2 e此时， 可以表示为函数 ，由其一阶导数可知 2jijiLeef)(22在区间 呈单调递增，因此有 。这说明：当链接两端的无线接入点e2,0mnpqU空闲度的高低水平（这里体现为两者之和）一定时，空闲度较为平衡的

23、链接对应的值较大。jijiL综合上述（a） 、 （b）两种情况可知：当一条链接的两端无线接入点的空闲度处于较高或平衡的状态时，其所对应的 的值较大。定理 1 得证。2jijiL对于图 G（ V， E） 中的任何一条路径 ，定义该路径的判据值为路径kvr,.10上所有链接的判据值之和，如公式（5）所示：01kiirIMI（5）我们的路由选择机制可以描述为：对于给定的源节点 S 和目的节点 D，有一个所有可能的路由组成的集合 R，如果 R ，我们选择满足 的路由 r 作为 S 到 D 的路由。)(minrRrI3.2 IMAR 协议实现描述IMAR 协议采用完全分布式的操作模式，无线 Mesh 层

24、中的每个无线接入点通过分布式的协作机制实现与其它无线接入点的信息交互，然后利用这些信息独立地进行路由路径的计算。图 3 显示了单个无线接入点上 IMAR 路由协议的大致执行过程。邻居表拓扑表 路由表M S 表多点转播路由计算M P R 选择 一跳广播满足多点转播H E L L OT CT CH E L L O更新Y4 44更新2 133331331输入输出2 ： M P R 选择 3 ： M P R 信息分发 4 ： 路由计算1 ： 邻居发现计算机学报 2010，33（12）：2300-23117图 3 单个无线接入点上 IMAR 路由协议的执行示意图从图中可以看出，每个无线接入点产生两种输出

25、，用于和网络中的其它无线接入点进行必要的信息交互：1) HELLO 分组：包含了该无线接入点当前所知道的所有一跳邻居的信息，另外，HELLO 分组中还记录了该无线接入点当前的空闲度（通过跨层操作得到） 。2) 拓扑控制分组（Topology Control，简称 TC）：包含了该无线接入点当前的 MPR Selector（Multipoint Relay Selector6）集合的信息，并且，对于该集合中的每个MPR Selector 节点，TC 都记载了当前无线接入点与该 MPR Selector 节点之间的链接的综合判据权值。相应的，每个无线接入点也会接收到周围一跳邻居发送的 HELLO

26、分组和网络中其它无线接入点广播的拓扑控制分组作为输入。同时，每个无线接入点上还保存了四张表，用于在协议执行过程中保存网络中的相关信息：1) 邻居表：保存了该无线接入点周围两跳链接范围内的邻居节点信息，此信息是通过与周围一跳邻居节点交互 HELLO 分组得到的。2) MS（Multipoint relay Selector）表：保存了该无线接入点当前所有的 MPR Selector节点的信息。此信息是通过对接收到的 HELLO 分组进行分析得到的。3) 拓扑表：保存了网络中所有无线接入点的 MPR Selector 集合信息，这些信息组成了一个经过压缩的全局子网拓扑，是实际全局子网拓扑的一个重要

27、框架，此信息是通过对接收到的拓扑控制分组进行分析得到的。4) 路由表：保存了协议计算所得到的到达网络中任意目标无线接入点的下一跳路由信息。如图 3 所示，整个 IMAR 路由协议的执行过程大致可以分为邻居发现、MPR 选择、MPR 信息分发和路由计算四个子操作，下面就分别针对这四个子操作进行描述。3.2.1 邻居发现邻居发现子操作如图 3 中标有记号 1 的箭头所示，每个无线接入点定期根据当前的邻居表构造并广播一个 HELLO 分组（其中也包含了当前自身的空闲度） ，处在发送节点无线电范围内的邻居节点可以接收到此 HELLO 分组，但不再对其进行继续转发。相应的，经过上面的 HELLO 分组发

28、布过程，每个无线接入点都能够接收到周围一跳邻居节点发送的HELLO 分组，通过对这些分组进行综合分析，该无线接入点不断地对自己的邻居表进行更新调整，更新调整后的邻居表又作为下一轮将要发布的 HELLO 分组的基础。这样可以形成一个持续的邻居信息更新和发布过程，使得无线接入点上的邻居表保持最新。与此同时，每个无线接入点接收到其周围一跳邻居节点发送的 HELLO 分组时，都会获得该邻居节点当前的空闲度，这样，结合自身的空闲度就可以计算出两无线接入点之间的链接的综合判据权值，并将此信息保存在邻居表相应的表项内。3.2.2 MPR 选择MPR 选择子操作如图 3 中标有记号 2 的箭头所示，其本质是对

29、多点转播机制提供结构上的支持，具体操作为：网络中的每个无线接入点根据自身的邻居表信息，从其一跳邻居节点中选择一组无线接入点作为它的 MPR，只有这组 MPR 节点对该无线接入点传输过来的广播分组进行转发，其它的邻居节点只对广播分组所包含的内容进行读取和处理，而不再对其做进一步的转发操作。当然，为了保证多点转播机制的完备性，MPR 节点的选择必计算机学报 2010，33（12）：2300-23118须满足下面的条件：一个无线接入点的所有 MPR 节点所组成的 MPR 集合必须能够覆盖（无线电传输范围）该无线接入点的所有两跳邻居节点，也就是说该无线接入点的 MPR集合和它的每个两跳邻居节点之间都必

30、须存在双向链接，当然，所选择的 MPR 集合越小，多点转播的优化效果越明显。下面的图 4 显示了网络中无线接入点 N 的一种可能的 MPR选择结果。N点MPRN图 4 MPR 选择示例传统的 MPR 选择机制通常采用基于贪婪策略的启发式算法 6，这样的算法存在以下的问题：1.算法中没有考虑链接性能的优劣；2.为了得到较小的 MPR 集合，算法优先选择邻居节点多的一跳邻居节点作为 MPR，但这样操作容易导致流量的集中从而引起网络拥塞等问题。针对上述问题，本文提出了一种新的 MPR 选择策略，在进行 MPR 选择时，综合考虑所选无线接入点与原点（进行 MPR 选择操作的无线接入点）之间链接的综合判

31、据权值，以及该无线接入点对于两跳邻居集合（操作过程中，可能是两跳邻居集合的子集）的连通度。假设原点为 ，对于一个特定的两跳邻居集合的子集 ，定义一跳邻居节点 的优先选择ov iv因子 如公式（6）所示：ioii IMtyconeiv)(（6）其中， 表示 对于集合 的连通度，也就是 中与 存在双向链接的无线)(tyconeiviiv接入点的个数， 表示无线接入点 和 之间链接的综合判据权值。按公式（6）计算oiIMovi所得的值越大，无线接入点越是优先考虑。MPR 选择算法的伪代码表示如下：MPR 选择算法：MPR_selection（n ，N1，N2）输入：n：任意无线接入点；N1 ：n 的

32、一跳邻居节点的集合，它们与 n 之间存在双向链接；N2：n 的两跳邻居节点的集合，它们与 N1 中的无线接入点存在双向链接，且 N2 不包含 N1 中的无线接入点。输出：无线接入点 n 的 MPR 集合1 Begin2 MPR 初始化为空3 如果 N1 中存在这样的节点 a：它是 N2 中某个节点的唯一一跳邻居，将 a 加入 MPR4 从 N1 中删除 a，从 N2 中删除与 a 存在双向链接的所有两跳邻居节点5 while N2 非空计算机学报 2010，33（12）：2300-231196 从 N1 中选择节点 b，满足：对于当前的 N2 来说， b 的优先选择因子最大，将 b 加入 MP

33、R7 从 N1 中删除 b，从 N2 中删除与 b 存在双向链接的所有两跳邻居节点8 End实际上，上一小节的邻居发现子操作还有一个重要的附带功能，那就是实现了 MPR节点的指派。基于邻居表中的邻居拓扑信息，无线接入点进行了 MPR 集合的选择，选择的结果又将作用于邻居表上，相应的链接将被标记为 MPR，并且这种选择结果会随着下一轮发送的 HELLO 分组传播出去。所以每个无线接入点只需要对接收到的 HELLO 分组进行分析，就可以获知哪些邻居节点选择了自己作为它的 MPR 节点，并将这些信息保存在MS 表中。这里需要注意的是： MS 表的每个表项中也记录了与之对应的链接的综合判据权值。3.2

34、.3 MPR 信息分发MPR 信息分发子操作如图 3 中标有记号 3 的箭头所示。经过邻居发现和 MPR 选择两步操作，无线接入点的 MS 表中保存了当前最新的 MPR Selector 集合信息，可以认为这个集合是该无线接入点周围局部拓扑信息的一个经过压缩的子集。无线接入点定期地根据MS 表中的这些信息构造一个拓扑控制分组，并利用多点转播机制在全网中进行广播以确保网络中的每个无线接入点都能够接收到一个副本。每当网络中的无线接入点接收到其它无线接入点发送的拓扑控制分组，它就根据分组中包含的信息对拓扑表进行更新，并依据自身的 MS 表决定是否对其进行进一步的转发。这里需要说明的是：由于拓扑控制分

35、组中记载了链接的综合判据信息，所以拓扑表的每个表项中也记录了与之对应的链接的综合判据权值。3.2.4 路由计算路由计算子操作如图 3 中标有记号 4 的箭头所示。经过前面三步子操作，网络中的每个无线接入点上都保存了对自己来说最新的邻居表和拓扑表，其中，邻居表保存了该无线接入点周围详尽的局部拓扑，拓扑表保存了网络中精简的全局拓扑，而且，这两个表中也都记录了相应链接的综合判据信息。无线接入点定期根据这两个表中的拓扑信息，以链接的综合判据作为路由的选择标准，利用 Dijkstra 算法计算出路由路径，并将这些路由信息保存在路由表中。3.2.5 路由减震机制IMAR 协议采用综合判据作为路由选择的标准

36、，而众所周知，这类对网络负载敏感的路由判据容易导致路由表的不稳定，即所谓的路由震荡问题。为此，需要在 IMAR 协议中引入路由减震机制，这样可以在充分利用网络资源的同时，从很大程度上消除负载敏感的路由判据所带来的这种副作用。本文中的路由减震机制分为两个层面，第一个层面如公式（3）和（4）所示，在计算无线接入点的空闲度时，使用指数加权移动平均法对 和 进行了平滑处理，这样iTxRicv可以消除网络中流量的突发性和偶然性，缓和了链接的综合判据权值变化的灵敏度，从而在一定程度上削弱负载敏感的路由判据所容易导致的路由震荡现象；至于第二个层面，我们对无线接入点上的拓扑表的更新操作进行控制。每当无线接入点

37、接收到网络中的其它无线接入点发送的拓扑控制分组，它就根据分组中包含的信息对拓扑表进行更新（包括了链接的综合判据权值的更新） ，在这里，我们规定：对于拓扑表中的某条链接，只有当此链接当前的综合判据权值较原先的综合判据权值的变化超过一个预先设置的阈值，才对此链接计算机学报 2010，33（12）：2300-231110的综合判据权值进行更新，否则，保持原先的值不变。这样的更新机制，使得网络中微小的负载变化所带来的影响被限制在节点周围的局部范围内，而只有当负载的变化达到一定程度时，这种影响才会在全网范围中体现出来，从而进一步缓和了负载敏感的路由判据所容易导致的路由震荡现象。3.3 IMAR 协议性质

38、分析Sobrinho 在文献16，17中给出证明：路由判据的可加性是 Dijkstra 算法能够成功执行的充要条件。IMAR 是基于 Dijkstra 算法的路由协议，所以，为了确保 IMAR 协议的可行性，需要证明综合判据满足可加性。性质 1 综合判据满足可加性，也即路由判据 IM 满足：对于网络中任意合适的路径 、a、 和 ，如果 成立，则可以推出 和 同时bc baIMcbcaIMbcacII成立，其中 表示路径 和路径 按序串联所形成的新路径，其它同理。c证明：假设路径 和路径 满足： ，则显然可得：baI（7）ccII而由公式（5） 的定义 ，可知：路径的综合判据权值为路径上所I10

39、kiir有的链接的综合判据权值之和，进而可得： cacaIMI（8）cbcbIMI（9）将(8)、(9)两式代入(7) 式，可得： a（10）同理可证： bcacII（11）综上所述可知，综合判据 满足：如果 成立，则 和IMbaIba同时成立，所以综合判据 满足可加性。性质 1 得证。bcacIIM性质 2 IMAR 路由协议所选择的路由路径是无环的。证明：Sobrinho 在文献16中给出证明：如果路由判据 M 和采用 Dijkstra 算法的逐跳路由协议结合使用，则 M 满足可加性是该路由协议满足无环性的充要条件。而由性质1 可知，综合判据满足可加性，且 IMAR 为采用 Dijkstra 算法的逐跳路由协议，所以IMAR 路由协议所选择的路由路径是无环的。性质 2 得证。同时，为了证明 IMAR 协议的优越性，我们针对分组成功递交率和端到端平均延时两个指标对 IMAR 协议的性能进行分析。对于分组成功递交率 PDR，它的定义为单位时间内网络中接收端成功接收的数据分组数量与发送端发送的数据分组总量的比值，即：（12）VvvRPD其中 表示节点 数据发送的平均速率， 表示节点 数据分组发送的平均成功率。vR在无线网络中，有两个因素可能会造成数据分组的丢失，分别为无线链路的不可靠性