2008年第3期 20O8.No.3 电子对抗 总第120期 Series No.12O ELECrrRONIC WARFARE 一种基于AODV路由协议的分簇算法研究 刘长牙1 徐 秭 (电子工程学院,合肥230037) 摘 要基于距离向量的按需路由协议AODV是Ad Hoc网络研究的热点之一。该协议 有效减少了建立和维护路由所需要的开支,但是随着网络节点发送数据量的增加,网络性 能会迅速下降。为了提高Ad Hoc网络的路由效率和可靠性,文章提出了一种基于AODV 路由协议的分簇算法。经仿真研究分析表明,该算法提高了网络节点的平均每跳吞吐率, 减少了节点的平均每跳时延。 关键词Ad Hoc AODV分簇算法研究 Research on the Clustering Algorithm Based on AODV Routing Protocol Liu Changli Xu Yi (Electronic Engineering Institute,Hefei 230037,China) Abstract:The lagorithm of Ad Hoc On—Demand Distance Vector(AODV)Routing protocol is one of the research hotspots in wireless Ad Hoc netwDrk.This protocol reduces routing effectively overhead in dynamic maintenance of routes.However,with AODV,network performance degrades rapidly iwth the increase of offered load.In order to improve routing efifciency and reliability,a clustering algorithm based on AODV routing protocol is proposed in this paper.The result of simulation shows that the clustering algorithm improves mean throughput per hop of node and increases mean latency epr hop of node. Keywords:Ad Hoc;AODV;clustering algorithm;research 开销、路由控制开销都比较低,因而广泛应用于 0引言 Ad Hoc网络路由协议中。 AODV路由协议计算组成网络的移动节点之 Ad Hoe[ ]按需距离矢量(A0Dv[1])路由协议 间的动态、自启动、多跳路由,以便用这些移动节 是为Ad Hoc网络的节点设计的。AODV路由协 点建立和维护一个Ad Hoc网络。AODV路由协 议能够对动态链路快速自适应,提供到达网络内 议能够处理低速、中速,以及相对高速的移动速 目的节点的单目标传输路由。其处理开销、存储 率,还能够处理各种级别的数据通信[ 。目前 收稿日期:2007年12月24日 维普资讯 http://www.cqvip.com
电子对抗 2008年第3期 AODV路由协议研究的移动节点从几十个到数千 1.2路由维护【5 J 个不等,主要集中在如何改进和提高AODV路由 协议,从而减小时延,提高数据成功传送率以及降 低开销等方面,并且已经取得了较好的效果。但 是针对网络中收发数据量大、容易产生拥塞的节 点的处理还存在着不足,其时延和控制开销比较 大。为了解决这个问题,本文通过把分簇的方法 引入到AODV路由协议中去,有效的降低了网络 的时延和控制开销,提高了效率。 1 AoDV路由协议的描述 AODV路由协议具有给移动节点提供快速获 取到达新目的节点的路由的能力,不要求节点维 护那些没有处在通信状态中的目的节点的路由。 AODV路由协议的操作是开环的,在Ad Hoe网络 拓扑变化时,通过避免Bellman.F0Id“无穷计算”问 题 J来提供快速收敛。当链路中断的时候,AODV 路由协议可使受到影响的那些节点能够得到有关 链路的中断信息通知,这样,这些受影响节点就能 够中断链路,使路由无效。另外,在AODV路由协 议中,在通往目的节点路径中的节点建立和路由 表维护过程中,数据报文头部不再需要携带完整 路径,减少了数据报文头部路由信息对信道的占 用,提高了系统的效率。 AODV路由协议一共定义了三种控制信息: 路由请求(Route Request,RREQ)、路由应答(Route Reply,RREP)、路由错误(Route Err,RERR) J。这 三种控制信息通过UDP进行传输,实现对路由发 现和路由维护的控制。具体情况如下: 1.1路由发现 J 当节点要发送数据的时候首先查找路由表, 如果有到目的节点的路径,则按路由表的下一跳 转发,若没有则源节点向邻居广播路由请求,收到 非重复RREQ的节点建立或更新逆向路由后再把 RREQ广播出去,直到目的节点或是有到目的节 点的有效路由的中间节点收到RREQ后,沿着逆 向路径回复一个路由应答到源节点。当RREP沿 着逆向路径回传时建立前向路由条目,这样源节 点收到RREP时,从源节点到目的节点的路由就 建立了。 AODV通过hello包,在链路修复及链路断开 后发送路由错误包来进行路由的维护。具体过程 如下:每个节点周期性的只传给相邻节点hello 包。如果一定的时间后,邻节点还收不到再次确 认连接的hello包,就会开始链路修复过程,即广 播一个RREQ给不可达节点,当有到不可达节点 有效路由的中间节点或不可达节点本身收到此 RREQ后就回复一个RREP给源节点,直到不可达 节点的路由重新建立。若链路修复失败,节点向 所有的邻节点广播RERR包,RERR包中的不可 达节点列表不仅包括了链路断开的邻节点,还包 括了以此邻节点为下一跳的路由条目的目的节 点。通过RERR的广播,其它节点就知道链路断 开了。 1.3 AODV路由协议的特点 在网络负载(收发数据量)并不繁重的时候, AODV的路径发现和路径维护表现出较好的全局 探察性质,对于整体网络而言,AODV的优势在于 它可以依据需要所探测方向的最新信息动态的维 护最优路径,并不会导致过大的开销。但是由于 移动Ad Hoc网络自身的特征,如:动态拓扑,链路 带宽受限,容量时变,能量受限,物理上安全有限 等[ ,使得网络的数据量分布不均匀,其结果就是 导致网络中有的节点数据量较少,或者没有数据 量,而有的节点数据量集中,从而导致数据包丢 失,端到端的延迟,以及数据包的无序到达。 AODV本身处理这类节点的办法是宣布路径失 效,需要寻求新的路径。因此需要寻找这样一种 新的路径的方法,来达到减少数据包的丢失、提高 节点的吞吐率、降低节点的延迟时间。 2基于AODV路由协议的分簇算法 2.1分簇算法的特点 为了解决AODV路由协议对负载重节点处理 上的不足,提高节点的吞吐率、降低节点时延,在 这里将分簇的策略引入到AODV路由协议中。对 网络节点密集,数据传送集中,易发生拥塞的区域 进行分簇;选择其中负载最轻的节点做为簇头,以 该节点和其周围的一跳邻居节点建簇。由簇头负 维普资讯 http://www.cqvip.com 总第120期 刘长利,等:一种基于AODV路由协议的分簇算法研究 45 责管理簇内节点数据量的传输,对簇内比较繁忙 节点的数据包通过簇头进行管理,合理将数据量 给簇内其它节点,将本来需要该节点承担的数据 该簇,从而使簇内的每个节点重新成为独立的 AODV节点。其具体描述如下: 2.2.1簇的构建 量由簇内的所有节点共同承担,实现让那些后到 的本来需要通过比较繁忙节点的数据包,部分分 给簇内其它数据量相对较少的节点,这样既减少 了数据量集中节点的负载压力,又增加了数据量 首先选出负载重节点和其周围能够在一跳范 围内达到的邻居节点,以其中负载最轻的节点做 为簇头,负载重的节点和其它的邻居节点做为簇 成员进行建簇。这样簇内部的每个节点除了有自 较少的节点的数据流量,从而有效缓解了网络的 局部拥塞,使得网络节点的负载分布更加均衡。 而对数据量传送较少的区域,不进行分簇,这样可 以避免无谓的增加整个网络中簇的个数,从而减 少了建簇和维护簇的开销,达到合理利用资源的 目的。如果该网络中存在多个簇,簇与簇之间是 相邻簇,则簇与簇之间的数据包通过簇头间传输 后分配给簇内的其它节点;簇与簇之间是非相邻 簇存在中间节点,则簇与簇之间的数据包由一个 簇头通过中间节点到达另一个簇头后再分给簇内 的其它节点进行传输。这样通过分簇,路由寻址 变得更加简单。在簇内部,由簇头负责合理分配 资源,在簇外部,通过AODV路由协议将各个簇联 系起来,有效增强了节点间的传输效率,提高Ad Hoe网络的性能。 本文假定网络中各节点的传输功率相同,并 且在每个簇内,节点彼此至多能在两跳远的范围 内通信。另外该分簇算法所形成的是相互不重叠 的簇。同时满足以下假设_3j: (1)在网络初始化时,每个节点可以通过交互 控制消息知道其邻居节点的ID号。 (2)一个节点发出的消息能够被其所有的邻 居节点在很短的时间内正确收到。 (3)在分簇算法执行期间,网络的拓扑不能发 生改变。 2.2算法的具体描述 这种基于AODV协议的Ad Hoe网络分簇算 法要实现建簇,首先建立簇相关的数据结构,其数 据结构中有两个表:一个AODV路由表,一个簇路 由表。在节点不属于任何一个簇时,簇路由表置 空;当节点属于某一个簇时,才建立簇路由表。当 建立了簇后,需要对这些簇进行维护,检测是否有 新节点加人某个簇,或者原簇内部的节点移出了 该簇,然后根据变化情况对簇数据结构进行更新。 如果簇内节点负载情况得到缓解的情况下,撤销 己的路由表外,还有一个簇路由表,所以在建簇的 时候,需要构造簇路由表。簇路由表的路由信息 从包含簇内除了自身外的其它节点的路由信息中 抽取来组成。如果有到同一目的地的多条路由信 息,则需要在这多条路由信息中做出选择。我们 在选择时,在考虑路径序列号和从当前节点到达 目的节点跳数的基础上,加人节点负载情况。然 后根据计算出的优先级对其进行排序,然后保留 优先级最高点那条路径作为簇路由表中到该目的 节点的路由信息。 2.2.2簇的维护 在进行分簇之后,需要定期对簇进行维护。 有新的节点移动进人到当前某簇传输范围内,可 以与该簇内部所有节点直接进行通信时,需要将 该节点加入到该簇。而在某簇内的节点移动出了 簇的传输范围时,又要将该节点从该簇中删除,并 更新簇路由表。 2.2.3簇的消亡 当节点检测到负载不再重时,就不再需要原 来所建立的簇了,从而可以减小维护簇的开销。 首先,检测簇内节点到负载,如果簇内负载不再重 时,通知簇内的所有节点,该簇取消。簇内各个节 点然后将簇号置零,并释放簇路由表的空间,完成 撤簇。 3算法性能仿真和分析 3.1环境配置和性能指标 为了描述基于AODV协议的Ad Hoe网络分 簇算法的特点,在这里借助于模拟的方法来实现 对该算法的仿真。我们在一个6OO×400单位距 离的区域内随机放置20个节点,节点的移动方向 可以在(0,2丌)随机运动,并且不对各个节点的运 动施加控制。无线传输的物理层和MAC层采用 维普资讯 http://www.cqvip.com 电子对抗 2008年第3期 IEEE802.II协议,数据信息速率为10Mbit/s,无线 传输为理想的,即无差错和延时。业务信息为等 长的数据包均为512bit,发送间隔服从正态分布, 平均每秒每个节点发送5个数据包。 3.2仿真结果和分析 吞吐率和时延是网络性能的两个重要参数。 吞吐率用数据包长度除以到达目的节点所花费的 时间来计算。时延是数据包在网络中的传输时 间,包括数据包的网络中的传输时间和在中间节 点缓存中的处理时间。在这里根据网络性能比较 的需要,采用节点平均每跳吞吐率和节点平均每 跳时延这两个参数,对采用分簇算法的AODV路 由协议和的原来的AODV路由协议进行性能比 较。得出的性能比较参数图,如图1、图2所示。 图1节点平均每跳吞吐率曲线 图2节点平均每跳的时延曲线 比较仿真结果可以得出: 从图1可以看出采用AODV路由协议产生的 曲线,节点平均每跳吞吐率的波动变化比较大,部 分节点的平均每跳吐率比较大,而大部分节点的 平均每跳的吞吐率都比较小;而对AODV路由协 议采用了分簇算法后所产生的曲线,总体来看,节 点的平均每跳吞吐率分布的比较平均,没有太大 的波动,而且吞吐率也比较大,集中在3Mb/s上 下。这说明对AODV路由协议采用了分簇算法之 后,在容易产生拥塞的节点处进行分簇,使本来需 要一个节点来承担的任务,可以由簇内的其它节 点共同承担,从而很好的缓解了易拥塞节点的压 力,提高了AODV路由协议的吞吐率。 从图2可以看出在采用AODV路由协议下产 生的曲线中,网络中所有节点平均每跳时延的分 布,同图1类似,节点的平均时延分配的不够均 衡,部分节点平均每跳时延大,部分节点平均每跳 时延小;而采用了分簇算法后的AODV路由协议 的曲线,节点平均每跳时延的分布比较均匀,没有 太大的波动,节点的平均每跳时延集中在0.036s 上下。这也是由于对AODV路由协议采用了分簇 算法之后,在容易产生拥塞的节点处进行分簇,使 本来需要一个节点来承担的任务,可以由簇内的 其它节点共同承担,减少了后续节点的等待时间, 换句话说就是减小了节点的时延,从而提高了网 络的效率。 4结束语 Ad Hoc网络是一种特殊的无线移动通信网 络。Ad Hoc网络中所有节点地位平等,具有很强 的抗摧毁性,在野外考察、偏远矿山作业、抢险救 灾等临时性场合具有广泛的应用。但是不同的应 用环境对Ad Hoe网络性能及其相应的网络协议 要求会有所不同。本文针对具有适应网络拓扑结 构快速变化性能的AODV路由协议,结合Ad Hoe 网络分簇算法的特点,提出了一种基于AODV路 由协议的Ad Hoc网络分簇算法。仿真结果表明 在网络节点容易产生拥塞的情况下,这种基于 AODV路由协议的分簇算法提高了节点的平均吞 吐率,减少了节点的平均时延,网络的性能得到了 改善,具有实用价值。 参考文献 1 Elizabeth M.Belding-Royer,Ch ̄es E.Perkins.Evolution and Future Direction of the Ad Hoc On-demandDis! Vector Routing Protoco1.Ad Hoc Networks joumad,2003,1(7):125一 l50 维普资讯 http://www.cqvip.com
总第120期 刘长利,等:一种基于AODV 由 坌篮篁塑塞 47 2 V.D.Park,M.S.Corson.A Hi fly Adaptive Distributed 2003,(4):15—18 Routing Algorithm for Mobile Wireless Networks.in:Proceedings ofIEEE FOCOM’97,Kobe:1EEE Press,Japan,April 1997: l405~l4l3 5陈林星,曾曦,曹毅编著.移动Ad Hoe网络.北京:电子 工业出版社,2007:210~229 3 S.Banerjee,S.Khuller.A Clustering Scheme for Hierarchical Control in Multi.hop Wireless Network.in:Bauer F,Cavendish D.eds.Proe.of the INFOCOM 2001.Vol 2,New York:IEEE Press,200l:1028~1037 作者简介 刘长利(1979.9~),男,辽宁本溪人,硕士研究生/助理 工程师,主要研究方向:Ad Hoe网络。 徐样 (1959.12~),男,江苏盐城人,大学本科/副教 #}话串}串亭簪}#}串}话#}串}簪}佟 串}簪}*每}错 4方旭明.移动Ad Hoe网络研究与发展现状.数据通信, 跆, 睾}#亡, 授,主要研究方向:通信与通信对抗。 苷}最}母}簪}簪}串}错 }孚亡母}睾}争}阜}串} 美国陆军航空部队对重型旋翼机发展的思考 美国陆军航空部队自部队建制以来,担负的作战任务日益繁重,部队操纵的无人机数量巨大,作战 环境日益严苛。现在,是时候为部队调整和现代化建设选择方向了。 除去无人机,陆军航空部队现在拥有的作战平台都是遗留下来的旧平台,只是传感器和其他设备是 新研制的或是经过了改进。 陆航相关官员指出,他们的目标主要是:发展重型和多用途飞机,旋翼机具有超过200节的巡航速 度,扩展有人机与无人机编队执行任务的概念。该官员还说:“我们正在为现在还不存在的任务做准备, 要采用的技术现在也还没有发明。”或许这正是陆军航空部队面临的最大挑战,新型、速度更快、能力更 强的旋翼机的发展远远落后于需求。 不久前,美国空军和陆军联合签署了一份初始能力文件,描述了旋翼机和固定翼飞机在承重能力方 面的区别。虽然重型旋翼机的发展已经得到了重视,但至少在2025年前,下一代重型旋翼机还不会出 现。 国防科学委员会在2007年7月的一份报告中指出,由于工程上的挑战,重型旋翼机或许根本就不 可得。很显然,如果选择垂直起降(VTOL)飞机,必须研制一种新型涡轮发动机;如果选择短距离起降 (STOL)飞机,就必须发明一种完全不同的起落装置,使得飞机可以从非常狭小而且不平整的地方起降。 那样一来,制造原型机的费用将达到25亿美元。 陆军与空军在无人机方面的合作非常成功,陆军新型“空中勇士”增程多用途(ERMP)无人机源自空 军的“捕食者”MQ一1无人机,但它的研制进展已经超越了空军的同类无人机。2007年9月,国防部已 经把这2个计划合并,这个决定也得到陆军和空军的完全支持。陆军减慢了对“空中勇士”无人机的采 购速度,采购计划更加深思熟虑,这样做自然会获得更好的飞机。 在一份有关无人机的简报中,陆军官员认为“空中勇士”无人机不过是一款普通的大型无人机系统, 它和其他的无人机系统一样,缺乏态势感知能力,在很多方面仍然离不开人的干预。 在陆军军械库中,真正具有灵巧的平台内通信能力的是AH一64“长弓阿帕奇”直升机。首次改进型 第三批次直升机预计2008年7月首飞,这种攻击型直升机将被改进成多用途平台。人们对它寄予了较 高的期望:它被设计成中央处理节点,处理在各军种间交换的数据,既是空中平台,也是陆上平台还是 ,作战单元。在即将举行的联合远征部队试验演习2008(JEFX08)中,人们计划验证“长弓阿帕奇”直升机 相互间的通信能力,但有关通信方面的下一步工作暂时还没有透露。 “阿帕奇”直升机已经被接纳进入有人驾驶一无人驾驶的编队中,借助于被称为VUIT一2的新系统, “阿帕奇”直升机能够从无人机接收实时的视频数据流进入它的座舱。但是,“阿帕奇”直升机无法同时 协调地操纵火控雷达(rCR)系统和VuIrr一2系统。在第三批次的订单中,9架飞机将只装备FCR,9架只 装备VUIT一2系统,6架将装备2种系统。 在美国陆军思考对重型、中型以及多用途飞机的需求的时候,我们认识到,美国陆军航空部队在21 世纪需要解决的难题是,他们在追求一种全新的垂直机动能力。(肖霞提供)
因篇幅问题不能全部显示,请点此查看更多更全内容