运动模型与Ad Hoc路由协议性能仿真

1、运动模型与 Ad Hoc路由协议性能仿真董杰北京邮电大学电信工程学院,北京(100876E-mail :摘 要:移动 Ad Hoc路由协议性能研究中主要使用随机停留点模型进行仿真,但是该模型 并不能全面模型移动 Ad Hoc路由协议的应用场景。 本文列举几种节点运动模型并进行仿真, 指出运动模型对移动 Ad Hoc路由协议性能仿真的影响。关键词:移动 Ad Hoc网络,运动模型,路由协议,性能仿真中图分类号:TN921. 引言有线网络在时间和空间的灵活性上受到极大束缚, 随着网络技术的高速发展, 移动无线 通信网络应运而生。 传统的移动无线通信网络以蜂窝移动通信网络和无线局域网两种方式为 主,

2、 它们都需要在现有的基础设施条件下建网, 这两种方式都不适用于无基础设施可利用的 临时或紧急组网。移动 Ad Hoc网络的出现使人们随时随地进行通信的愿望成为现实,它具 有组网速度快、 抗毁自愈能力强等优点, 适用于军事作战系统, 也适用于需要紧急部署通信 网络的突发事件现场。Ad Hoc网络是一种没有有线基础设施支持的移动网络,网络中的节点均可由移动主机 构成。该网络的拓扑结构、通信模式与以往的网络都有所不同,因此,移动 Ad Hoc网络路 由协议成为近年来研究的一个热点。路由协议性能仿真是 Ad Hoc路由协议研究中采取的最直接的方式,但是,纵观以往的 性能仿真研究可以看出,仿真往往都是基

3、于简单的节点运动模型,比如随机停留点模型 (Random Waypoint Mobility Model来进行的。这些模型往往不能正确模拟该网络中的节 点拓扑和运动规律。本文对移动 Ad Hoc路由协议性能仿真中使用的节点运动模型进行了研究,针对移动 Ad Hoc网络的特点提出几种适合的网络模型, 论证节点运动模型对移动 Ad Hoc路由协议性 能仿真带来的影响2. 节点运动模型在移动 Ad Hoc网络技术研究中,仿真是对新想法、新概念、新路由协议进行评价的重 要方式。在协议用于真实网络之前,往往都要经过数据仿真和分析。为了对移动 Ad Hoc网络技术进行仿真测试和性能评价,在仿真软件中需要创

4、建具有一 定特性参数 (场景形状,场景尺寸,场景内部特征,节点数量,节点特性,仿真时间 的测试 环境,该环境被称为仿真场景。其中在仿真场景中, 节点的运动模型描述节点的无线信号传输半径、 节点移动速度、 节 点移动模型等属性;场景内部特征描述区域内部地形特征及内部特殊子区域等信息 (如节点 不能进入或不能离开的区域等属性 。根据节点类型和场景内部特征, 仿真场景可以分为简单仿真场景和复杂仿真场景。 若仿 真场景中所有节点都属于同一类型, 并且场景内部无特殊区域, 节点可以位于场景中的任意 位置, 这样的仿真场景称为简单仿真场景。 若仿真场景中具有几种不同类型的节点, 或者场 景内部有特殊区域,

5、这样的仿真场景称为复杂仿真场景。在移动 Ad Hoc路由协议研究过程中,提出新协议时,一般要与先前协议进行比较。为了提高比较结果的可信度, 所建立的仿真场景一般要与先前所用的仿真场景一致。 所以, 无 线自组网仿真研究中形成了几个典型场景, 这些场景均为矩形区域。 由于其它形状的场景区 域并没有特殊优越性, 并且场景越复杂, 在仿真器中仿真时对机器资源的消耗越大, 效率越 低,所以其它形状场景很少应用。在无线网络中,移动终端 (mobile hosts会以多种不同的方式运动。因此,运动模型被大 量用于蜂窝网络的拓扑和移动 Ad Hoc网络的路由协议的性能分析。在蜂窝无线通信网中, 对移动模型展

6、开的研究主要集中于在特定区域 (蜂窝 内用户的移动性,移动用户的移动模式 被用来优化蜂窝的大小、位置和动态信道分配策略。在移动 Ad Hoc网络中,研究更侧重于 微观层面上, 包括单个节点的位置、 速率与其他节点的相关性, 因为这些因素直接决定节点 间链路的建立与断开,影响网络拓扑变化和通信。在无线 Ad Hoc的多跳网络中,相关联结点的很轻微的运动都会对整个网络的拓扑造成 很大的改变, 并影响到上层协议的性能, 比如端到端流量和延迟。 与蜂窝网络相比, Ad Hoc网络对节点的移动更加敏感,因为在 Ad Hoc网络中,节点也要同时承担路由的工作。以下对移动 Ad Hoc路由协议性能仿真中常用

7、的节点运动模型做介绍。2.1 随机停留点模型 (Random Waypoint Mobility Model随机停留点模型首先由卡耐基 -梅隆大学(CMU , Carnegie-Mellon University提出,该 模型中的移动节点采取 go-sit-go 的方式。初始时,节点在仿真区域的某个地点静止停留一 段确定的时间 pause T (Pause Time,然后选择区域中的一个目的地点,并确定到该地点的 行进速度 t V 。 t V 的选择服从 (0, max V 的均匀分布。 当节点到达目的地点后, 将停留 pauseT 长的时间,然后重复以上的动作。图 1是随机停留点模型中某个节

8、点的运动轨迹的示例。 0200400600800100002004006008001000图 1随机停留点模型中某节点的运动轨迹 从以上描述中可以看出,在随机停留点模型中,节点最大速度 max V 和停留时间 pauseT 是两个关键参数,并且这两个参数决定了节点的运动行为。如果节点最大速度 max V 的值很小,同时停留时间 pause T 很长,该 Ad Hoc网络趋于稳定。相反,如果节点移动速度很快 (max V 的值很大并且停留时间 pause T 很小,该网络的拓扑将是非常动态的。改变这两个 参数,特别是 max V ,该模型可以衍生出多种移动场景。2.2 参考点组移动模型 (Ref

9、erence Point Group Mobility Model前面提到,在 Ad Hoc网络的研究兴起之前,对运动模型的研究都是基于蜂窝网络结构 来进行的,提出很多运动属性用于度量运动模型,比如网络切换 (handoff,地址管理 (location management , 调度 (paging, 网络注册 (registration, 呼叫时间 (calling time, 网络负荷 (traffic load 等 1。蜂窝网络中,通信主要发生在移动节点和中央天线之间,而非组成员之间的互 换,因此,移动模型的性能仿真主要关注移动节点的个体运动,在这种情况下,随机停留点 模型(Rando

10、m Waypoint就成为该类仿真中最常用的节点运动模型。但是在移动 Ad Hoc网络中,通信发生在节点和节点之间,并且会因其应用场景的不同 而有很大改变, 在这种情况下, Random Waypoint模型并不能准确的描述这种场景中的节点 移动。因此,在以后的研究中,很多学者提出各种适合移动 Ad Hoc网络仿真的节点运动模 型。其中,参考点组移动模型 (Reference Point Group Mobility Model 1就是其中应用最广泛 的。在该模型中,移动节点以组的形式存在,每组节点都有一个逻辑中心 (logical center, 该中心的移动决定整个分组的运动行为,包括位置

11、、速度、加速度等。通常,节点均匀分布 (uniformly distributed在所属分组的地理区域内。模型会为分组中的每个节点分配一个参考 点 (Reference Point,参考点的移动与逻辑中心节点的移动保持一致 (速度向量相同 。 在仿真过 程中的每一步,每个节点都会随机选择其参考节点的附近的某个地点作为其在该步中的位 置。这样,通过 “ 参考点 ” 机制,就将组移动和独立节点间的随机移动行为结合起来。 图 2 参考点组运动模型示例图 2是该模型的一个实例,简便起见,模型中只有一个分组,且该组中只有三个节点。通过该实例可以看到分组移动过程中各节点的移动特点, 其中, 由逻辑中心的移

12、动决定整个 分组的移动, 各参考点始终与逻辑中心保持相同的相对位置, 而各个移动终端则围绕其各自 参考点随机分布。RPGM 模型能够通过显式赋予每个分组移动路径,从而确定该分组的移动。在实际操 作中,可以在每个时间间隔 (Time Interval处定义一系列的检查点 (Check Points,随仿真的 进行, 分组从一个检查点移动到另一个检查点。 每当分组到达一个新的检查点时, 模型根据 该相邻两检查点的距离和时间间隔计算其在该过程中的运动向量。除此之外, 通过适当的选择分组检查点, 该模型可以很容易的模拟很多实际的群组运动, 特别是模拟那种在规定时间内到达某预订地点去完成任务的情况, 比

13、如军事行动时各单位的 运动。3.3 高斯 -马尔可夫运动模型 (Gauss Markov mobility model高斯 -马尔可夫运动模型 2中,节点在运动间隔 t 时节点的运动是由该节点在 t-1间隔时 的位置、移动速度和方向来决定的。在该模型中,对于每个移动节点,系统每隔一个时间片 都会更新其速度和行进方向: 式 (2-1 其中 n s 和 n d 是时间片 n 时的速度和方向; (01 是控制该模型随机性的参 n 后该节点的平均速度及运行方向。 1n x s 和 1n x d 都是符合高斯分布的随机变量。从式 (2-1中可以看到, 节点速度与运行方向与前一时间片时的速度和运行方向有关

14、, 所 以该模型具有记忆特性。通过改变 的值,可以得到不同随机度的模型。该节点移动模式是一种较为实际的随机模式, 节点在整个过程中的运动速度和方向的改 变是很平滑的。3.4 曼哈顿移动模型 (ManhattanGrid Mobility Model曼哈顿移动模型是一种用于城市街道环境的用户移动性模型。 在此模型中, 假定用户为 均匀分布,每条街道有两个方向 (垂直方向:北和南;水平方向:东和西 。移动节点只允许 在水平和垂直街道的线路上移动。 在交叉点位置, 设定移动节点的转向概率, 分三种运动情 况:以 P=0.5的概率向前,以 P=0.25的概率向左或向右。移动节点在每个时间间隔的速度 是

15、独立的,同时又受到同一街道内最大速度的限制。该移动模式具有较高的时空独立性,但仍然是一种受到移动线路局限的节点移动方式。3.5 其他仿真场景在以上各节中分别介绍了四种常用的节点运动模型, 其中, 随机停留点模型具有完全的 随机性,不存在任何时空限制,且最容易实现;参考点移动模型引入了节点间的群组性,各 节点不再独立运动,而是具有了相关性;高斯 -马尔可夫模型引入了运动的时间相关,某时 刻节点的运动特征与其前一时刻的运动有关; 曼哈顿模型则加入了模型地理空间限制, 节点的运动受到地理约束。除此之外, 还有其它常用的节点运动模型, 这些模型往往只是以上模型的变种, 通过改 变以上模型中的某些参数而

16、达到某种要求。3. 运动模型影响协议性能评价前面多次讲到, 运动模型会对移动 Ad Hoc路由协议的性能产生很大的影响, 在本节中, 我们将使用 NS-2仿真工具,分别对 DSR 和 AODV 两种常见的 Ad Hoc路由协议基于不同 的运动模型进行仿真。协议控制开销(Routing Overhead是比较移动 Ad Hoc路由协议性能的一个重要参数, 该参数可以度量协议的适用能力, 比如该协议用于阻塞网络或窄带环境中; 也可以度量其效 率,特别是移动节点具有电源限制(battery power。如果某个路由协议会发送大量的控制 数据包,则会增加包碰撞(packet collisions的可能

17、性,甚至会在网络中无处不在的发送对 列中延缓数据包的发送。在本文中 Overhead 由传送数据的字节数除以协议控制数据的字节 数得到的。吞吐量(Throughput 用于度量仿真过程中到达目的节点的数据的多少,该参数可以明 确的表明采用测试协议时的数据通信量。 在本文中, 吞吐量是将所有目的节点收到的数据相 加得到的。本文仿真时节点之间的通信模式如下:即所有的通信都是点对点的, CBR 数据包,发 送速度为 4包 /秒,仿真时间为 3000秒 3,路由协议分别应用 AODV 和 DSR ,运动模型路 径由上节提到的 BonnMotion 工具生成,分别为随机停留点模型(RWP 、参考点组移动模 型(RPGM 、高斯 -马尔可夫模型(GaussMarkov 和曼哈顿移动模型(ManhattanGrid , 并将生成的模型路径前 1000秒的数据去除。通信模式文件由 NS-2中工具 “cbrgen” 生成。其 中,对于 RWP 模型,分别对 10、 20、 30个 CBR 源进行仿真,对于其它模型,只针对 10个 CBR 源进行仿真。该仿真中没有采用 TCP 连接,因为 TCP 会预先估计网络的性能并根据结果改变发包的 时间。因