第３４卷 第２４期 Ｖｏ１．３４ ・计算机工程 ２００８年１２月 Ｄｅｃｅｍｂｅｒ ２００８ Ｎｏ．２４ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ 网络与迢ｉ信・ 文章编号：１０ｌｌＩｌ—３４２８（２００８）２４—ｏｏ９６＿＿＿０４ 文献标识码：Ａ 中圈分类号：ＴＮ９１５．０４ 基于ＡＯＤＶ的贪婪路由协议 朱鸿，单洪，黄郡 （电子工程学院网络工程系，合肥２３００３７） 摘要：针对ＡＯＤＶ路由协议在节点高速移动环境中存在的低性能问题，提出一种利用贪婪算法并充分考虑节点移动状态的路由协议 ＧＡＯＤＶ。该协议涉及扩展Ｈｅｌｌｏ报文、控制分组数量、建立稳定路由以及禁用本地路由修复。仿真分析表明，ＧＡＯＤＶ比ＡＯＤＶ具 有更高的吞吐量，在节点移动速度达８０ ｍ／ｓ时，端到端的平均时延减少了５５％。 关健词：Ａｄ Ｈｏｃ网络；贪婪路由协议；按需距离向量路由协议 Ｇｒｅｅｄｙ Ｒｏｕｔｉｎｇ Ｐｒｏｔｏｃｏｌ Ｂａｓｅｄ ｏｎ ＡＯＤＶ ＺＨＵ Ｈｏｎｇ，ＳＨＡＮ Ｈｏｎｇ，ＨＵＡＮＧ Ｊｕｎ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｎｅｔｗｏｒｋ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ Ｉｎｓｔｉｔｕｔｅ，Ｈｅｆｅｉ ２３００３７） ［Ａｂｓｔｒａｃｔｌ Ａｉｍｉｎｇ ａｔ ｔｈｅ ｃａｐａｂｉｌｉｔｙ ｄｅｆｉｃｉｅｎｃｙ ｏｆ ＡＯＤＶ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｉｎ ｓｉｔｕａｔｉｏｎ ｗｈｅｒｅ ｎｏｄｅｓ ｍｏｖｅ ａｔ ｈｉｇｈ ｓｐｅｅｄ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｃａｌｌｅｄ ＧＡＯＤＶ ｗｈｉｃｈ ｕｓｉｎｇ ｔｈｅ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ａｎｄ ｃｏｎｓｉｄｅｒｉｎｇ ｎｏｄｅｓ’ｍｏｖｉｎｇ ｓｔａｔｅ ｆｕｌｌｙ．Ｔｈｉｓ ｐｒｏｔｏｃｏｌ ｉｎｃｌｕｄｅｓ ｅｘｔｅｎｄｉｎｇ Ｈｅｌｌｏ ｐａｃｋｅｔ，ｒｅｓｔｒｉｃｔｉｎｇ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｏｎｔｒｏｌ ｐａｃｋｅｔ，ｅｓｔａｂｌｉｓｈｉｎｇ ｓｔｅａｄｙ ｒｏｕｔｅ ａｎｄ ｆｏｒｂｉｄｄｉｎｇ ｌｏｃａｌ ｒｏｕｔｉｎｇ ｒｅｐａｉｒ．Ｓｉｍｕｌａｔｉｏｎ ａｎａｌｙｓｉｓ ｓｈｏｗｓ ｔｈａｔ ｃｏｍｐａｒｅｄ ｗｉｔｈ ＡＯＤ Ｖ’ＧＡＯＤＶ ｈａｓ ｂｅｔｔｅｒ ｔｈｒｏｕｇｈｐｕｔ，ａｎｄ ｔｈｅ ａｖｅｒａｇｅ ｅｎｄ—ｔｏ—ｅｎｄ ｄｅｌａｙ ｉｓ ｄｅｃｒｅａｓｅｄ ｂｙ ５５％ｗｈｅｎ ｔｈｅ ｎｏｄｅ’Ｓ ｓｐｅｅｄ ｃｏｍｅｓ ｔＯ ８０ｍ／ｓ． ［Ｋｅｙ ｗｏｒｄｓｌ Ａｄ Ｈｏｃ ｎｅｔｗｏｒｋ；ｇｒｅｅｄｙ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ；ｏｎ－ｄｅｍａｎｄ ｄｉｓｔａｎｃｅ ｖｅｃｔｏｒ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ １概述 无线Ａｄ Ｈｏｃ网络是由一组不依赖基础网络设施、带有 无线收发装置的移动节点组成的无线通信网络…，由于其节 点结构简单，具有较强适应性和生存能力，因此被大量用于 军事、抢险救灾等紧急任务场合。 路由技术一直是Ａｄ Ｈｏｃ网络研究的重点和热点，目前 较成熟、典型的路由协议有ＤＳＤＶ，ＤＳＲ，ＡＯＤ ＺＲＰ等 】。 节点；１和２代表中问节点。 Ａｄ Ｈｏｃ网络拓扑结构动态变化的特性给路由协议设计带来 了一定困难，现有协议不能适应所有网络状况。尤其是在节 点移动性增强的情况下，有效路由上链路断开的几率增大， 图１ ＡＯＤＶ报文交换 目前对ＡＯＤＶ协议进行改进的研究很多。文献［４】提出在 Ａｄ Ｈｏｃ网络中依靠一些可靠（计算能力强、电池能量充足）节 数据包丢失率上升，导致网络性能急剧下降，无法保证实时 性要求较高业务的服务质量。 点来提高路由生存能力。将可靠节点放置在网络中有利于通 信的优化位置，并根据网络状态的变化，动态改变可靠节点 的位置和运动轨迹，以增加在网络中找到从源节点到目的节 点之间可靠路由的几率。但上述算法较复杂，且需要一些可 靠节点的支持。文献［５】提出一种基于链路状态的自愈路由协 议，基本思想是节点测量接收到的数据包或路由请求包的信 ２研究现状 按需距离向量路由协议ＡＯＤＶ是一种经典的反应式路 由协议，已标准化并得到广泛应用。该协议由路由发现和路 由维护２个阶段组成。在路由发现阶段，通过有效控制洪泛 ＲＲＥＱ路由请求包、目的节点回复ＲＲＥＰ路径应答包，源节 点找到一条到目的节点的路由后，采用单播发送数据分组。 噪比，并根据事先设定的阈值判定链路状态，以便在链路彻 底断开前重新发起路由请求或修复路由，从而加速路由恢复、 避免不必要的数据丢失和重传。文献【６］的方法与文献【５］类 在路由维护阶段，由断链处上游节点负责路由的本地修复或 向上游节点发起ＲＥＲＲ路由错误通告，源节点收到ＲＥＲＲ通 告后重新启动路由发现过程 ｊ。 似，主要思想是通过观察接收到的数据分组的能量值，判断 链路状态，提前告知所有正在使用即将失效链路的节点，使 这些节点及时删除缓存中即将失效的路由，并进行新的路由 发现，进而减少网络中的分组丢失率。 本文假定利用ＧＰＳ或其他手段来获得节点的位置、速度、 作者简介：朱单在使用ＡＯＤＶ协议的Ａｄ Ｈｏｃ网络中，移动节点在需要 时才维护路由条目，网络开销少；节点间周期性地向邻居发 送Ｈｅｌｌｏ消息以进行本地连通性管理，能够快速应对有效路 由中链路断开的情况。该协议通过维护一系列序列号和标识 ＩＤ号，能有效防止路由循环。它具有一定可扩展性，在节点 移动性不强的情况下能适应大规模网络。图１描述了ＡＯＤＶ 协议的报文交换方式，其中，ｓ和Ｄ分别代表源节点和目的 鸿（１９８２一），男，硕士研究生，主研方向：无线网络； 郡，硕士研究生 洪，教授、博士生导师；黄收稿日期：２００８—０３—０２ Ｅ－ｍａｉｌ：ｈｏｎｇ＿Ｏｏｌ一９１６—８２＠１６３．ｃｏｒｎ ９６一 运动方向等信息，在ＡＯＤＶ路由协议基础上提出贪婪路由协 议ＧＡＯＤＶ，以提高传统ＡＯＤＶ协议在节点高速移动、网络 拓扑变化频繁情况下的性能。 ３移动参数 节点的高速移动导致网络拓扑结构不断变化，给自组网 路由带来不良影响。如果网络中的节点可以相互通信，那么 节点之间必定存在有效路径，如果能从这些路径中找出一条 最稳定的，就能降低链路失效的几率，进而减少丢包率。 在Ａｄ Ｈｏｃ网络中，由于各个节点移动方向不同，导致 某些节点间的通信链路在很短时间（由节点的高速运动决定） 之后就会断开，因此选择这种链路组成的路由不是好路由， 而传统ＡＯＤＶ协议在路由发现时无法对链路状态作出预测， 因此，无法对上述链路进行筛选。本文利用移动参数ｍｐ来 反映相邻节点问的相对运动趋势，在路由发现阶段尽量选择 不易断开的链路，建立相对稳定的路由，以减少分组丢失率。 设ｉ√为网络中２个相邻节点，ｍｐ ，根据式（１）来计算。 ｍｐｑ＝（ 一ｚｘｘｊ）２＋（△ 一ａｙ ） （１） 其中， △薯＝Ｖｉ×ｃｏｓ￣／； △ ｆ＝Ｖ ７×ｃｏｓＯ； ｚｘｙｉ＝ｖｉ×ｓｉｎ ； ａｙｊ ｖｊ ｍ ，。其中，ｖ表示节点移动速度；０表示节点移 动方向；Ａｘ表示ｔ＝ｌ Ｓ内节点在ｘ轴方向上的位移；Ａｙ表示 ｔ＝ｌ Ｓ内节点在ｙ轴方向上的位移。由于节点在高速移动情况 下运动方向一旦确定，短时间内不会有太大变动，因此规定 移动时间为１ Ｓ以方便计算，此时２个节点在ｘ轴和ｙ轴方 向上位移之差的平方正好反映了节点间的相对运动趋势，由 式（１）可以看出， ｆ值越大，节点 和．／之间距离随着时间增 加而增大的可能性越大。 ４ ＧＡＯＤＶ路由协议算法描述 本文提出的ＧＡＯＤＶ路由协议利用贪婪算法对ＡＯＤＶ路 由协议进行改进。通过ＧＰＳ系统或其他手段辅助提供节点移 动信息，网络中的节点可以获得相邻节点和目的节点的坐标。 与ＡＯＤＶ类似，整个协议分为路由发现和路由维护２个阶段。 设ｓ表示源节点，Ｄ表示目的节点，ｍｐ为移动参数。 ４．１算法可行性 在将算法应用于ＡＯＤＶ协议前，先进行简要的方案论 证，从链路稳定度的角度说明本文算法的可行性。 ４．１．１接收信号强度 在Ａｄ Ｈｏｃ网络中，接收节点能否正确接收来自发送方 的信息取决于接收节点接收到的信号强度大小 Ｊ，接收信号 强度定义为 Ｎ （２） ｒ 其中，Ｐ，为发送功率；Ｎ是天线常数；ｒ是节点之间的距离。 可见，在发送功率Ｐ 一定的情况下，由于节点移动引起 ｒ的细微增加会使信号强度Ｐ，的值快速减小，因此当Ｐ，小于 某个阈值时，节点间不能正常通信，即它们之间的通信链路 断链。这说明在节点做高速移动的网络环境中，移动性对链 路稳定性有较大影响。下文将对链路稳定性进行量化，并说 明算法的可行性。 ４．１．２链路稳定度 观察网络中２个高速移动节点ｉ和／，它们的移动状态和 位置关系如图２所示。设 为节点间的最大有效通信距离。 在图２描述的场景中，虚线圆圈表示节点 的最大通信范围。 ２个节点在ｔ０时刻的坐标分别为（Ｘｎ Ｙｉｏ），（ｘｊｏ．）， ０）。经过时间ｔ 后，２个节点的坐标分别为（一 ．ｙ ｆ），（ ），，，）。在（ｔｏ＋ｆ）时刻，节 点间距离为 ，且下一时刻节点ｉ和 之间的距离将超过 （假定 和 做相互远离的运动），即节点间链路断开，则 ２个节点在最大有效通信距离范围内的运动时间ｔ可用式（３） 估算。 一一一一～／、＼ ／ ＼ ，，ｔ ■ ］ 『，（Ｘ／ｏ， ．／／‰ ｊ （ｘｉ…Ｙｉ） 、 ， ＼ ／ 、、 ／／ ＼／ ＼ ／、一一 ～一一一图２节点移动模型 （ —ｘｊ ） ＋（ 一Ｙｊｆ） ＝ Ｌ Ｊ 其中，Ｘｉｒ＝Ｘｉ。－］－－１Ｊｉ ｃｏｓＯｉｔ；Ｘｊｒ＝Ｘｊ。＋Ｖ，ｃｏｓＯ／；Ｙｉｆ＝ｙ［（１＋ ￣ｓｉｎＯｉｔ：Ｙｊｆ Ｙｊｏ＋ＶＪ ｓｉｎＯｆｆ。 代入式（３）得 ［（ Ｘｊｏ）＋ｖ ＣＯＳＯｉ—ｖ，ｃｏｓ０，）ｆ］ ＋ ［（ｙ 一Ｙ ）＋（ｖ ｓｉｎ ０ 一ｖ ｓｉｎ 】 ＝Ｒ （４） ｛殳ａ＝ 。一Ｘｍ，ｂ＝ｖ ＣＯｓ — ｃｏｓ ，，Ｃ＝Ｙ ｏ—Ｙ，ｏ，ｄ＝ ｓｉｎ 一 ｓｉｎ 。 代入式（４）得 （ａ＋６ ） ＋（ｃ＋ｄ ）。＝ 解得 （ｃｄ—ａｂ）＋￣（ｂ２＋ｄ２）Ｒ２ａｘ一（ａｄ＋ｂｃ） （５） ｂ２＋ｄ２ 其中，ｔ称为链路稳定度，由于假定节点作相互远离的运动， 因此只考虑ｔ为正实根的情况，对于正实根，ｔ值越大，表示 ２个节点在有效通信范围内活动的时间越长，即节点间链路 越稳定，反之相反；ｂ２＋ ＝％ｃｏｓＯ￣一￣＃ｏｓＯｐ ｑ－（Ｖｉｓｉｎ０ｉ— ｖｊ ｓｉｎ０ 。上文提到，当节点高速移动时，其移动方向在短 时间内不会发生太大变化，且式（２）说明ｔ应是一个较小的值 （由于节点高速移动，因此节点间距离变化较快，在很短时间 之后接收强度就可能低于闽值），由式（１）可得ｂ２＋ｄ２ ｍＰ１．。 因为ｌｉｗ ｔ＝０，所以当ｍｐ 值很大（节点相对运动趋势很 ＋ｄ — 。ｏ 大）时，节点间链路稳定度趋近于０。本文算法始终选择州， 值最小的节点作为下一跳转发节点，从而保证了有效路径上 节点间的链路具有最优链路稳定度，即保证了断链几率最小。 ４．２路由发现阶段 文献［８ Ｊ给出了单个路由寻找代价的计算公式： １＋ＦｗＲｅｑ＋ＯｇＲｅｐ＋ＦｗＲｅｐ （６） 其中，１表示起始路由请求分组的传输；ＦｗＲｅｑ表示所转发 的路由请求分组数量；ＯｇＲｅｐ表示路由应答分组产生节点的 个数；ＦｗＲｅｐ表示所转发的路由应答分组数量。传统ＡＯＤＶ 采用洪泛ＲＲＥＱ的方式寻找路由，根据式（６）可知，大范围的 洪泛分组会增加协议开销，导致网络性能降低。 节点移动性造成的协议负载与断链数成正比 Ｊ，每条链 路断链产生的协议负载为Ｏ（Ｌｌｇ（ｎ）／ｒ２），其中，ｎ为网络中的 节点数；，为节点的传输半径；Ｌ是与路径跳数有关的值（ 的函数）。可见，随着网络规模扩大，断链产生的协议开销也 会增加，而传统ＡＯＤＶ协议选出的最终用于转发数据分组的 路由没有考虑链路状态，在节点高速移动的情况下断链几率 高，随着网络规模的扩大，其协议开销也会增大，因此，网 络可扩展性不强。 在ＧＡＯＤＶ路由协议中，节点之问通过周期性地互通携 带运动参数信息的Ｈｅｌｌｏ报文，利用移动参数 来 ＲＲＥＱ的洪泛，极大减小了寻由代价，并能建立起稳定的路 由，可以较好地适应网络规模的扩大。具体扩展部分的伪代 码如下： （１）在Ｈｅｌｌｏ报文中加入节点移动参数信息： ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ｛ … ｄｏｕｂｌｅ ｘ，ｙ；／／节点当前坐标 ｄｏｕｂｌｅ ｎｅｘｔｘ，ｎｅｘｔｙ；／／节点下一点坐标 ｄｏｕｂｌｅ ａｖｇＳｐｅｅｄ；／／节点移动速度 ）ＡＯＤＶ—ＲＲＥＰ—Ｐａｃｋｅｔ； （２）在邻居列表表项中加入移动参数信息： ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＮＴＥ ｛ … ｄｏｕｂｌｅ ｎｂｘ，ｎｂｙ；／／节点当前坐标 ｄｏｕｂｌｅ ｎｂｎｅｘｔｘ，ｎｂｎｅｘｔｙ；／／节点下一点坐标 ｄｏｕｂｌｅ ｎｂａｖｇＳｐｅｅｄ；／／节点移动速度 ｄｏｕｂｌｅ ｎｂｄｉｓｔａｎｃｅ；／／邻居节点到目的节点距离 Ｊ ＡＯＤＶ—ＮＴ—Ｎｏｄｅ； 在上述扩展部分中，根据三角公式（式（７）），节点坐标信 息可用于估算ｓｉｎ０和ｃｏｓ０。 ｒ ｒ—————■■—————— ｛ｌ ｓｉｎ ＝（ｙ２一Ｙ１）／√（ｙ２一ＹＪ） ＋（ 一 １） ，Ｌ Ｊ ｒ—————ｉ————— ｌ ＣＯＳＯ＝（ｘ２一 ），√（），２一Ｙ１） －｝－（Ｘ２－－ １） 当节点ｓ有数据包向节点Ｄ发送时，本文协议的具体处 理过程如下： （１）如果ｓ自身有到Ｄ的有效路由，则直接发出数据包， 否则执行贪婪算法，转（２）； （２）ｓ根据自身维护的邻居表，先选出邻居节点（一跳节点） 中距离目的节点Ｄ比自己近的节点，设为（，ｚ１，，ｚ２，ｎ３，…），然 后求出ｍｉｎ（ｍｐ川，ｍｐ舢，ｍｐ蚰，…），选择具有该最小ｍｐ值的 节点作为下一跳并转发ＲＲＥＱ，其中，ｍｐ 表示源节点ｓ和 邻居节点ｎ 之间的ｍｐ值； （３）中间节点收到ＲＲＥＱ后，若本地有到Ｄ的有效路由， 则直接沿反向路径向ｓ发送ＲＲＥＰ，否则利用相同方法，计 算与邻居节点（比自己离Ｄ近的节点）的ｍｐ值，选择 值最 小的节点作为下一跳转发ＲＲＥＱ； （４）Ｄ收到ＲＲＥＱ后，沿反向路径向ｓ发出ＲＲＥＰ。 上述过程较ＡＯＤＶ协议的主要不同如下：节点不采用洪 泛ＲＲＥＱ的方式，而是贪婪地向与自己具有最小相对运动趋 势的邻居节点转发ＲＲＥＱ。 本文算法存在一种特殊情况，即局部优化问题问题 …， 如图３所示。 图３局部优化问题 一９８一 在图３中，虚线表示节点的最大通信范围，Ｆ在一跳范 围内找不到比自己距离Ｄ更近的节点，根据贪婪算法，Ｆ会 选择自己作为分组转发的下一跳，而使分组无法到达目的节 点Ｄ（此时存在到Ｄ的路径，如图３箭头所示），此时，Ｆ称 为最佳主机 …。为防止局部优化的产生，本文协议采用与 ｆ－ＧＥＤＩＲ… 协议相同的处理方式：最佳主机洪泛ＲＲＥＱ，邻 居节点收到ＲＲＥＱ分组后先检查是否收到过该ＲＲＥＱ，若是 则丢弃该ＲＲＥＱ，否则继续使用贪婪算法寻找下一跳。 ４．３路由维护阶段 本文协议扩展了ＡＯＤＶ路由维护过程中使用的Ｈｅｌｌｏ报 文，邻居节点问交换Ｈｅｌｌｏ消息时捎带了坐标、速度、运动 方向等信息，节点通过邻居列表维护这些信息以便路径发现 时使用。此协议禁用了本地路由修复功能，若某条路由在使 用过程中出现了断链，则断链处上游节点不再负责本地修复， 而是采用直接向源节点ｓ发送ＲＥＲＲ的方式，使其重启路由 发现过程，这样做原因在于：节点移动性强，本地修复失败 几率大，使用本地路由修复反而会导致分组传输时延增加、 传输效率降低。 ５仿真分析 ５．１仿真环境 为了验证ＧＡＯＤＶ协议的有效性，本文使用在无线网络 仿真中应用较广泛的ＧｌｏＭｏＳｉｍ作为仿真平台，它提供了传 统ＡＯＤＶ协议的源代码，仿真参数设置如表１所示。 表１仿真参数 参数 值 节点数／个 １００ 最大运动速度／（ｍ ｓ。。） ２Ｏ，４Ｏ，６Ｏ，８０，１００ 信号衰减模型 ＴＷＯ—ＲＡＹ 发包率／（ｐａｃｋｅｔ ｓ ） ｌ 区域大ｄ，／ｍ ５ ０００ｘ５ ０００ ＭＡＣ协议 ＩＥＥＥ８０２ ｌ１ ＤＣＦ 业务类型 ＣＢＲ 节点传输半径ｒａ／ｍ ２５０ 移动模型 Ｒａｎｄｏｍ Ｗａｙｐｏｉｎｔ 带宽／（Ｍｂ．ｓ ） ２ 数据包大ｔｊ￣／Ｂｙｔｅ ５１２ 仿真时间／ｍｉｎ １０ ５．２仿真结果及性能评估 本文提取ＣＢＲ业务吞吐量及数据分组端到端平均时延 作为协议性能比较的依据。对ＡＯＤＶ协议和ＧＡＯＤＶ协议， 分别在节点最大移动速率为２０ ｍ／ｓ，４０ ｍ／ｓ，６０ ｍ／ｓ，８０ ｍ／ｓ和 １００ ｍ／ｓ时进行仿真实验。 图４给出了吞吐量与节点最大移动速度的关系。实验结 果表明，当节点移动速度增大时，由于节点间链路失效率的 增加，导致引起协议耗费较多信道资源在路由发现和错误报 告上，因此２种协议数据业务吞吐量都有下降趋势，但 ＧＡＯＤＶ的吞吐量比ＡＯＤＶ高，原因是虽然链路失效率增加， 但ＧＡＯＤＶ采用的贪婪算法仍然有效了路由控制报文的 数量，使网络能更多地传递数据分组，尤其当速度大到一定 程度时，该优势会更明显。 兰 伽伽姗 瑚瑚 删 茸 纰 态调整网络拓扑、传输战场实时信息等任务。本文提出基于 ＡＯＤＶ的贪婪路由协议，利用节点运动参数，在节点高速运 动的环境下建立较稳定的路由，提高了网络吞吐量，减小了 分组传输的端到端平均时延，且具有较小路由控制开销，在 延长节点工作时间、提高节点生存能力方面具有一定参考价 值。后继工作将进一步简化路由算法，以提高协议的数据业 务吞吐量。 圈４ ＣＢＲ业务吞吐量 参考文献 ［１］于宏毅．无线移动组织网【Ｍ］．北京：人民邮电出版社，２００５． ［２】洪锡军．无线自组网路由协议研究［Ｊ】＿计算机工程，２００５，３１（８）： 图５比较了ＧＡＯＤＶ和ＡＯＤＶ的端到端平均时延，可见， 随着节点移动速度的不断增大，ＧＡＯＤＶ的平均时延低于 １０５。１０７． ＡＯＤＶ，原因如下：（１）由于ＧＡＯＤＶ利用了贪婪算法，节点 ［３］Ｃｈａｒｌｅｓ Ｅ，Ｅｌｉｚａｂｅｔｈ Ｍ Ｅ Ａｄ—ｈｏｃ Ｏｎ—ｄｅｍａｎｄ Ｄｉｓｔａｎｃｅ Ｖｅｃｔｏｒ 在路由发现阶段尽量选择运动方向大致相同的节点作为下一 Ｒｏｕｔｉｎｇ［Ｓ］．ＩＥＴＦ ＲＦＣ ３５６１，２００３． 跳，因此容易找到较稳定的路由，减少了重启路由发现的次 ［４】Ｙｅ Ｚｈｅｎｑｉａｎｇ，Ｓｒｉｋａｎｔｈ Ｋｒｉｓｈｎａｍｕｒｔｈｙ Ｓ Ｋ，ｅｔ １ａ．Ｆｒａｍｅｗｏｒｋ ｏｆｒ 数，进而减少数据分组的丢失，因此，对整个网络而言，降 Ｒｅｌｉａｂｌｅ Ｒｏｕｔｉｎｇ ｉｎ Ｍｏｂｉｌｅ Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ 低了数据分组传递的端到端时延。（２）ＧＡＯＤＶ禁用了本地路 ＩＮＦＯＣＯＭ’０３．Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ：Ｉｓ．ｎ．］，２００３：２７０—２８０． 由修复。当节点移动速度足够大时，链路失效率的增加将引 ［５］冯玉美．Ａｄ ｈｏｃ网络中自愈路由协议研究【Ｊ］．北京邮电大学学报 起本地修复失败的几率增加，因此，ＡＯＤＶ采用的本地修复 ２００５，２８（２）：４６—４９． 将消耗大量路由修复和重建时间，导致数据分组传输的端到 ［６］年梅．通过链路失效预测机制提高ＡＯＤＶ协议的性能［Ｊ］． 端时延增大。 计算机应用，２００５，２５（６）：１２５１—１２５６． ［７］Ｒａｐｐｏｒｔ Ｔ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎ：Ｐｒｉｎｃｉｐｌｅｓ Ａｎｄ Ｐｒａｃｔｉｃｅ［Ｍ］． Ｎｅｗ Ｊｅｒｓｅｙ，ＵＳＡ：Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ／Ｐｅａｒｓｏｎ，１９９６． 酒 翟 ［８］Ｍａｌｔｚ Ｄ Ａ．Ｔｈｅ Ｅｆｆｅｃｔｓ ｏｆ Ｏｎ—ｄｅｍａｎｄ Ｂｅｈａｖｉｏｒ ｉｎ Ｒｏｕｔｉｎｇ 霹 Ｐｒｏｔｏｃｏｌｓ ｏｆｒ Ｍｕｌｔｉｈｏｐ Ｗｉｒｅｌｅｓｓ Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ Ｊｏｕｍａｌ 释 赢 ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，１９９９，１７（８）：１４３９—１４５３． 骡 【９］Ｊａｉｎ Ｒ．Ｇｅｏｇｒａｐｈｉｃａｌ Ｒｏｕｔｉｎｇ Ｕｓｉｎｇ Ｐａｒｔｉａｌ Ｉｎｆｏｒｍａｔｉｏｎ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ Ｐｅｒｓｏｎａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００１，８（１）： ４８—５７． 图５数据分组靖刭靖平均时廷 ［１０］于宏毅．无线移动组织网【Ｍ】．北京：人民邮电出版社，２００５： ２２７ ２２８． ６结束语 ［１１】Ｓｔｏｊｍｅｎｏｖｉｃ Ｉ，Ｘｕ Ｌｉｎ．Ｌｏｏｐ—ｆｒｅｅ Ｈｙｂｒｉｄ Ｓｉｎｇｌｅ—ｐａｔｈ／Ｆｌｏｏｄｉｎｇ 由于移动Ａｄ Ｈｏｃ网络中节点的能量、存储容量有限， Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｗｉｈｔ Ｇｕａｒａｎｔｅｅｄ Ｄｅｌｉｖｅｒｙ ｆｏｒ Ｗｉｒｅｌｅｓｓ 因此必须在完成任务的同时提高协议效率和性能。例如在军 Ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ 事应用方面，将无线传感器节点置于己方车辆、坦克等装备 Ｓｙｓｔｅｍｓ，２００１，１２（１０）：１０２３—１０３２． 上，节点在随高速移动的同时，需要完成自动组网、动 （上接第９５页） ５结束语 ｏｎ Ｃｏｍｐｕｔｅｒｓ，２０００，４９（２）：１８２—１８８． 本文提出的ＭＣＦ．ＬＤＬＰ混合调度算法丰富了优先级确 【４】Ｇｒｅｇｏｒｙ Ｃ．Ｓｃｈｅｄｕｌｉｎｇ ｏｆ Ｎｅｔｗｏｒｋｅｄ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ［Ｊ］．ＩＥＥＥ 立的依据，在一定程度上提高了控制系统的整体性能，尤其 Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍ Ｍａｇａｚｉｎｅ，２００１，２１（１）：５７・６５． 是在网络负载较重时，仍能使系统保持较好的控制性能。下 【５】Ｇｒｅｇｏｒｙ Ｃ．Ｓｔａｂｉｌｉｔｙ Ａｎａｌｙｓｉｓ ｏｆ Ｎｅｔｗｏｒｋｅｄ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ［Ｊ］． 一步工作将研究如何更好地建立优先级与控制系统性能之间 ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ Ｔｅｃｈｎｏｌｏｇｙ，２００２，１０（３）：４３８—４４６． 的映射关系，以期进一步提升ＮＣＳ的整体性能。 【６】Ｊｏｓｅ Ｍａｒｔｉ Ｊｏｓｅｐ Ｍ．Ｃｏｎｔｒｏｌ Ｌｏｏｐ Ｓｃｈｅｄｕｌｉｎｇ Ｐａｒａｄｉｇｍ ｉｎ 参考文献 Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ ｈｔｅ ２９ｔｈ Ａｎｎｕａｌ Ｃｏｎｆ．ｏｆ ［１】Ｏｃｔａｖｉａｎ Ｖ．Ｎｅｔｗｏｒｋｅｄ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ［Ｄ］．Ｄｕｒｈａｍ，ＮＣ，ＵＳＡ： ｈｔｅ ＩＥＥＥ．Ｒｏａｎｏｋｅ，ＵＳＡ：［Ｓ．ｎ．］，２００３． Ｄｕｋｅ Ｕｎｉｖｅｒｓｉｔｙ，２００１． ［７】Ｓｅｕｎｇ Ｈ．Ｓｃｈｅｄｕｌｉｎｇ Ａｌｇｏｒｉｈｔｍ ｏｆ Ｄａｔａ Ｓａｍｐｌｉｎｇ Ｔｉｍｅｓ ｉｎ ｔｈｅ ［２】Ｚｈａｎｇ Ｗｅｉ，Ｂｒａｎｉｃｋｙ Ｍ Ｓ，Ｐｈｉｌｉｐｓ Ｓ Ｍ．Ｓｔａｂｉｌｉｔｙ ｏｆ Ｎｅｔｗｏｒｋｅｄ Ｉｎｔｅｇｒａｔｅｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ［Ｊ］．Ｃｏｎｔｒｏｌ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ［Ｊ］．ＩＥＥＥ Ｃｏｎｔｒｏｌ Ｍａｇａｚｉｎｅ，２００１，２１（１）：８４—９９． Ｓｙｓｔｅｍｓ Ｔｅｃｈｎｏｌｏｇｙ，１９９５，３（２）：２２５—２３０． ［３】Ｚｕｂｅｒｉ Ｋ Ｍ，Ｓｈｉｎ Ｋ Ｇ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｅｆｉｆｃｉｅｎｔ ［８］Ｓｅｕｎｇ Ｈ．Ｂａｎｄｗｉｄｔｈ Ａｌｌｏｃａｔｉｏｎ Ｓｃｈｅｍｅ ｆｏｒ Ｃｙｃｌｉｃ—ｓｅｒｖｉｃｅ Ｆｉｅｌｄｂｕｓ Ｍｅｓｓａｇｅ Ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ Ｃｏｎｔｒｏｌｌｅｒ Ａｒｅａ Ｎｅｔｗｏｒｋ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ． Ｎｅｔｗｏｒｋｓ［Ｊ］．Ｍｅｃｈａｔｒｏｎｉｃｓ，２００１，６（２）：１９７—２０４．
