高动态移动自组网路由协议研究

82 通信电子技术 Communications Electronics 高动态移动自组网路由研究 朱晓芳 华 蓓 （中国科学技术大学计算机科学与技术学院） 摘 要：目前的移动自组网研究主要针对运动速度较慢的地面网络。本文研究由高速节点组成的高动态移动自组 网的路由协议，提出了一个结合驱动路由和地理位置路由的混合路由协议TOPOS，在局部使用表驱动路由加快数据 包的转发，而在全局使用地理位置路由以适应快速变化的网络拓扑。在OPNET仿真平台上对TOPOS和已有的AODV及 GRP协议的性能比较表明，TOPOS对于节点的运动速度和网络规模具有更好的适应性。 关键词：高动态移动自组网；路由协议；仿真 Research on Routing Protocol in Highly-Dynamic Mobile Ad-Hoc Networks Zhu Xiaofang Hua Bei (School of Computer Science and Technology, University of Science and Technology of China) Abstract：Existing research on mobile ad-hoc networks mainly focuses on low-speed ground networks. This paper studies on the routing protocol of the highly-dynamic mobile ad-hoc networks that consist of very-high-speed nodes, and comes up with a hybrid routing protocol, TOPOS, by combining the table-driven routing protocol and geographical position-based routing protocol, in which table-driven routing is used for local forwarding, and geographical position-based routing is used for finding route to remote nodes. Simulation is performed on OPNET platform to compare TOPOS with two representative routing protocols (AODV and GRP) embedded in OPNET. The results show that TOPOS has the best adaptability to the movement speed and network scale among the three protocols. Key words：highly-dynamic MANET; routing protocol; simulation 0 引言 移动自组网是由移动节点通过无线链路形成的一种 多跳临时性自治系统，因组网灵活和不需要固定的通信基 础设施而在军事及民用领域有着广泛的应用。 目前已提出的移动自组网路由协议，按照路由决策 所依据的信息分为基于拓扑的路由和基于地理位置的路由 两大类[1]。基于拓扑的路由协议收集节点间的连接关系 和链路特性，按照最小跳数或最小延迟原则计算路由，并 保存到路由表中[6]。基于地理位置的路由协议收集节点 的位置坐标，按照距离最短或方向最接近的原则确定下一 跳节点[3]。地理位置路由协议不需要建立基于全局链路 状态的路由，可以实现无状态、分布式的数据转发，因而 对网络拓扑变化的适应性更好。 现阶段研究的移动自组网主要是地面移动自组网。 受地面条件所限，节点运动速度一般较慢，且通信距离较 短。随着网络向空天领域延伸，未来将出现一类高动态的 移动自组网，例如临近空间网络。临近空间是在现有飞机 最高飞行高度和卫星最低轨道高度之间的一块空域，在现 代战争和民用通信领域均有重要应用。应用于空天作战的 临近空间网络，节点的运动速度可能极高，如高速战机、 导弹等的速度可高达几个马赫，节点间的通信距离一般很 长，如几十到上百公里。在由高动态节点构成的移动自组 网中进行路由是一个难题。节点的高速运动使得全局链路 状态及节点位置不断改变，频繁触发路由更新或位置更新 过程，不仅在网络中产生大量的控制开销，而且路由收敛 困难，数据转发延迟增大，丢包严重。 本文提出一种适合高动态移动自组网的路由协议 TOPOS，并在OPNET平台上与目前典型的基于拓扑的路 由和基于位置的路由进行比较。实验表明，TOPOS对节 点速度和网络规模具有更好的适应性。 1 问题描述与分析 本文考虑的高动态移动自组网由一定数量的高速节 点组成，且每个节点的通信距离较长。与一般地面移动 自组网不同，节能不是首要考虑的因素。 对于由高动态节点构成的网络而言，若节点通信距 离很短，即节点间链路的存在时间很短，则只有扩散法 是唯一可用的路由协议，但扩散法只能应用于小规模网 络。注意到这类网络中节点通信距离较长这一特点，这 意味着节点间的链路可保持一小段时间，从而在一个较 小的时间和空间范围内网络拓扑的变化并不是高度随机 的，这是一个可以利用的特性。 为了验证这种猜测的合理性，我们通过简单的仿真 实验来估测网络中n-跳连接的平均持续时间。取节点的 通信距离为100km，节点运动速度为10马赫(现阶段最高 速度)。在以节点O为中心、半径100km的圆内随机均匀 分布10个节点，这些节点即为节点O的一跳邻居。所有节 点(包括节点O)均随机运动，记录各节点与节点O断开连 接的时间。取100次实验结果的平均值，得到节点O的剩 余邻居个数随时间的变化曲线(图1)，以及一跳连接的平 均保持时间27.72s。从图1看到，经过15s之后，仍然有一 半的节点与节点O保持连接。 为测试两跳连接的平均持续时间，取一条直线上的 两个节点A和C，B位于A和C的覆盖范围之内，且为A和 C的一跳邻居。三个节点均随机运动，记录两跳连接断开 的时间。取100次实验结果的平均值，得到两跳连接平均 保持时间约为12.2s。使用同样的方法可以测试n-跳连接 的平均保持时间，如图2所示。从图中看到，n-跳连接的 平均保持时间随n的增大而急剧下降，这也表明了基于拓 扑的路由不适合高度动态的网络。 图1 节点O的剩余邻居个数-时间曲线(参见下页) 图2 n-跳连接的平均保持时间(参见下页) 以上实验假设节点以最高速度运动，且节点间的运动 83 通信电子技术 Communications Electronics 图1 节点O的剩余邻居个数-时间曲线 图2 n-跳连接的平均保持时间 独立无关，考虑到实际节点的速度没有这么高，且节点之 间存在一定程度的协同，则一跳和两跳连接的保持时间还 会更长一些。 利用网络中这种暂时的局部稳定性，我们提出一种 局部基于拓扑信息而全局基于地理位置信息的路由协议 TOPOS(TOpology-and-POSition based routing protocol)。两 跳距离内使用基于拓扑的路由，这是因为两跳以内连接的 稳定性相对较好，从而维护局部路由的开销较小，基于位 置的路由协议则因为需要频繁更新节点位置而开销较大； 另外在转发数据包时，基于拓扑的路由只需查找路由表即 可转发，而基于位置的路由需要对每个包计算下一跳节点。 两跳距离之外使用基于位置的路由，这是因为两跳以上的 连接持续时间短，路由失效概率大，基于拓扑的路由算法 在全局范围内很难收敛；基于位置的路由协议因不需要在 全局范围内维护显式路由，适合拓扑变化的能力较强。 然而由于节点一直处在高速运动之中，基于位置的 路由协议在全局范围内进行位置更新的开销很大。考虑到 高动态网络中节点位置信息失效很快，越远的节点其位置 信息的准确性越差，我们提出一种基于簇的两层路由结构。 节点首先被组织到若干簇中，簇头作为簇中所有节点的代 表，对外只发布簇头位置及簇中成员节点集合。在远距离 转发数据包时，以目的节点所在簇的簇头作为目标进行转 发决策。由于簇的成员关系在短时间内较为稳定(图1)， 因此以簇头位置作为其成员节点的位置估计是可行的，这 样就避免了在全局范围内交换所有节点的位置信息，也可 以适当降低位置更新频率。由于位置更新总是从发生地向 四周扩散，越近的节点拥有越准确的位置信息，因此在转 发过程中可允许每个簇头根据自己所掌握的最新目标位置 进行转发，从而不断修正数据包的传输方向，直至到达目 的节点。 2 TOPOS协议设计要点 TOPOS协议的设计要点包括三个方面：分簇，局部 路由建立，全局位置更新。 2.1 分簇 网络中的所有节点被划分成簇。簇头到每个成员节 点的距离为一跳，位于两个簇交界区域的节点为网关节点， 其余为普通节点。簇头和网关节点构成网络的骨干，形成 基于簇的两层网络结构。 簇的初始化包括邻居发现、簇头选举、簇加入、簇 通告四个阶段。在邻居发现阶段，各个节点通过交换 hello消息收集一跳邻居的信息以及到各邻居节点的链路 延迟，建立邻居节点表。在簇头选举阶段，各节点向邻 居节点通报本节点的度(一跳邻居的个数)，度最大的节点 成为簇头。在簇加入阶段，簇头宣告自己为簇头，其它 节点选择最近的簇头加入。在簇通告阶段，每个节点向 邻居节点通告自己所在簇的簇头，以便下一步寻找网关 节点。 簇初始化完成后，每个节点通过周期性的hello消息 交换更新邻居节点表。 2.2 两跳局部路由表的建立 在建立了邻居节点表后，各成员节点检查自己的邻 居中是否有相邻簇的簇头。如有，则给自己的簇头 ，以及本节点到相邻簇头的链路延迟。簇头收集这些报 告后，根据最小延迟原则计算到相邻簇头的最佳路由， 保存到局部路由表中，并通知该路径上的下一跳节点为 网关节点。因此，两跳局部路由表实际上维护了当前时 刻本簇头到各个相邻簇头的最佳路由，这种路由方法在 基于拓扑的路由分类法中称为表驱动路由(table-driven routing)。 在每次邻居节点表更新完成后，成员节点向簇头发 送新的邻居簇头及链路延迟信息，簇头据此更新局部路 由表。 2.3 全局位置更新 全局位置更新采用周期性更新的方法，簇头定期将 自己的位置信息和簇内的成员节点集合通报给其它簇头 节点。 2.4 数据包转发过程 当节点需要发送或转发数据包时，先查找邻居节点 表；若目的节点为一跳邻居，则直接发送给目的节点； 否则，普通节点和网关节点将数据包发送给自己的簇头 节点，簇头节点按照以下流程转发。 首先利用目的节点查找全局位置表，得到目的节点 所在簇的簇头的位置，将该位置作为目标位置；计算距 此目标位置最近的下一跳簇头节点；利用该下一跳簇头 查找局部路由表，得到下一跳网关节点；将数据包转发 给该网关节点。这个过程重复进行，直到数据包到达目 的节点的某个一跳邻居(目的簇头或其它节点)，然后再 转发给目的节点。 3 仿真实验 我们在OPNET网络仿真平台上实现了TOPOS协议， 并与OPNET自带的AODV协议(基于拓扑的路由协议)[4]和 GRP协议(基于地理位置的路由协议)[2]进行了比较，重点 考察节点运动速度与网络规模对系统吞吐量的影响。吞吐 量定义为网络中所有节点单位时间内成功接收的数据量。 为了便于与AODV及GRP进行比较，我们采用802.11 作为MAC层协议，并采用目前文献中较常见的实验场景 设置。节点活动区域的大小设为1200m×1200m，节点通 信距离300m，目前文献中节点的运动速度最高为30m/s。 设置网络中的负载（每秒钟产生的数据量）为6.4Mb/s。 每次实验的仿真时间为500s，取5次实验结果的算术平均 值作为最终的实验结果。 3.1 节点速度对吞吐量的影响 84 通信电子技术 Communications Electronics 设置节点个数为50个，运动速度从0增大至80m/s。图3为 三种算法下系统吞吐量随节点速度的变化曲线。 图3 吞吐量－运动速度曲线 随着节点运动速度的提高，三种算法的吞吐量都是 下降的。这是因为运动速度的增大加剧了网络拓扑和节点 位置的变化，触发更多的拓扑或位置更新消息的传播，增 加了网络的负载，另一方面路由失效或位置信息无效使得 数据包投递失败的概率增大，这两方面因素都引起丢包率 的增加。 从图中可以看到，TOPOS的表现是最好的。这是因 为AODV要在全局范围内维护链路状态路由，其信令开销 很大，路由失效对数据包投递的影响也最大。相比于GRP 在全局范围内交换节点位置信息，TOPOS只交换簇头位 置及各簇的成员节点集合，信令流量较小；加之在两跳之 内采用表驱动路由，加快了数据包的转发速度，因而其表 现要好于GRP。 3.2 网络规模对吞吐量的影响 令节点个数从25增大至100，节点运动速度为30m/s。 图4是三种算法下系统吞吐量随节点个数的变化曲线。 图4 吞吐量－节点个数曲线 随着节点个数的增加，三种算法的吞吐量都是下降 的。这是因为网络中的信令开销随节点个数的增加而迅速 增大，同时节点密度也增加了，这两个因素都导致MAC 层通信冲突加剧，丢包率增大。但由于TOPOS的信令开 销最小，其性能表现也最好。 4 结束语 本文针对一类高动态移动自组网提出了一种分簇的 地理位置路由协议TOPOS，在全局范围使用基于地理位 置的路由协议，而在拓扑相对稳定的局部使用表驱动路由， 结合了地理位置路由对拓扑变化适应性好和表驱动路由转发 数据包迅速的优点。仿真实验表明，TOPOS对节点运动 速度和网络规模均有较好的适应性，比单纯的基于拓扑的 路由和基于位置的路由更适合高动态网络。 实验中也发现，由于采用了竞争型的MAC层协议， 通信冲突比较严重，网络吞吐量不够理想。下一步拟采用 跨层设计的思想联合设计MAC层协议和路由协议，以提 高网络的整体性能。 参考文献： [1] Mauve M, Widmer J.A survey on position-based routing in mobile ad hoc networks[J].IEEE Network,2001, 15(6):30-39. [2] Karp B, Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C].Proc.Of ACM/IEEE International Conference on Mobile Computing and Networking,2000. [3] Stojmenovic I.Position based routing in ad-hoc networks [J]. IEEE Communications Magazine,2000,40(7):128-134. [4] Perkins C,Royer E.Ad-hoc on-demand distance vector (AODV) routing[EB/OL]. http://www.ietf.org/rfc/rfc3561.txt [5] Royer E, Lee S -J,Perkins C.The Effects of MAC protocols on ad hoc network communication[C].Proc.of the IEEE Wireless Communications and Networking Conference (WCNC '00),2000. [6] Boukerche A,PhD.Algorithms and protocols for wireless and mobile ad hoc networks[M].Wiley-IEEE Press, 2008,11:141-175. 作者简介： 朱晓芳，1983年生，硕士研究生，主要研究方向为移动 自组网 电话：0551-3607043；15151531518 电子信箱：zxfang@mail.ustc.edu.cn 联系地址：安徽省合肥市中国科学技术大学西校区9#306 朱晓芳 （230027） 华 蓓，1966年生，教授，博士生导师，主要研究方向 为计算机网络、移动计算 电子信箱：bhua@ustc.edu.cn