论文研究-Ad Hoc网络中分簇算法的研究.pdf

Ad Hoc网络是一种多跳的自组织网络，网络是由移动的节点组成。Ad Hoc网络的许多应用都依赖层次结构的支持，簇结构是Ad Hoc网络中应用最为广泛的层次结构，而这种层次结构的形成和维护依赖于某种分簇算法。在研究已有分簇算法的基础上，提出了一种新的基于权值的分簇算法（NWCA），通过对算法进行分析和仿真测试，证明了该算法的有效性。
杨卫东: Ad hoc网终中分簇算法的研究 2010,46(21)113 值得注意的是:按照(6)中的分簇策略,得到的网络结构 10000 LOW 为互不交叠的簇结构。 9000 HCDA 8000 NWCA 2.5网络的初始化和簇维护策略 7000 在这里考虑的 Ad hoc网络中的节点是同质的,在初始化 回6000 5000 时网络中所有节点的处理能力和电池量都是相同的,且簇头 4000 旳选举不是周期性的,而是按需自适应进行选举。初始时,网 300 2000 络中的所有节点都处于未决定状态,并周期地广播其ID号, 1000 位于每个节点传输范围內的邻居节点将收到此消息,故每个 5101520253035 节点都能了解其邻居节点的数量和及其权值。一旦节点获得 节点ID 了邻居节点的信息,NwCA算法就开始工作并将网络划分为 图2节点充当簇头的时间 簇。在此过程中,每个节点根据其的权值,通过比较应该知道为该算法对选择充当簇头的节点没有任何倾向性,各节点充 它所扮演的角色(簇头或普通节点),若是普通节点它还需要当簇头的时间分布更加均匀。在NWCA算法中,因NwCA算 知道它所属的簇和簇头。 法对簇头的选择考虑了移动节点的最佳连接度和电池能量两 由于普通节点和簇头的移动都会影响系统的稳定性,因个因素,故使得所有节点充当簇头的机会更均等。 此系统需要不断地更新,即进行簇维护。维护或更新的结果 表1列出了各分簇算法的LBF的平均统计值,这里节点数 可能为下面两种情况:一是产生新簇和删除旧簇,一是不需要N=32,节点最大的移动速度为=5m/s,节点的传输范围分 重新分簇。第一种情况是指由于普通节点或簇头的移动,使别为20m、30m和40m。模拟结果表明,NWCA算法的LBF最 目前所分的簇不能覆盖所有节点,这时就要启动分簇算法进大,其次为 LOWID而HDA的LBF最小,说明NWCA的负载 行重新分簇。对于第二种情况是指普通节点只是从一个簇移平衡持性最好而HCDA的负载平衡特性最差。这是因为NWCA 动到另个簇,可能不需要重新分簇,只是简单地改变·下该算法采用最佳连接度对簇头的节点连接度进行制约,且还考虑 节点的隶属关系而已 了各节点的能量状态因素,使簇头的分布比较均匀,故使得簇头 的负载平衡特性较好。而HCDA侧重于选择节点度较高的节 3算法的性能仿真及其结果分析 点成为簇头,对簇头的连接度不加以限制,使得各簇中成员节点 31模拟环境和性能指标 数的分布很不均匀,故该算法的负载平衡特性最差。 模拟环境如下:仿真软件为 OPNET10.5:节点的移动模 表1三种分簇算法LBF的统计值(平均) 4型采用的是自组网经常使用的移动模型 Random Waypoint模 算法 LOWID HCDA NWCA 型,在这种模式中,节点朝一个任意目的地运动,带有周期性 0.523 0.1710882 的停顿行为,节点的移动速度可以在(0,V之间随机选择, 0.233 0.089 0.396 其中V表示节点移动的最大速度,单位是m/;节点的移动区 0.116 0.062 0.333 域为一个100m×100m的区域;各节点初始时的能量均为 从图3中可以看岀,簇头数随节点传输范围的増加而减 10000,单位时间内簇头相对于每个普通节点所消耗的能量少,当传输范围大于30时,簇头数减少的速度逐渐变慢,但最 e=1;模拟时间为10000时间单位;权重因子:c1=05,c2=终都收敛到1。图3中可以看出HCDA得到的平均簇头数最 0.5。权重因子c1、c2可以根据网络的实际情况进行调整。 少,因为它侧重于选择节点度较高的节点成为簇头,这样每个 到目前为止研究人员已经提出了多种分簇算法,但有几簇内所包含的节点数就较多,可以产生较少的簇,从而降低分 种分簇算法受到了广泛的认可,最小ID算法和最大连接度算组投递的延迟,但该算法对簇内节点数没有限制因而无法适 法就是受到广泛认可的分簇算法。为了准确地说明算法的特应于某些对节点能力有限制的网络(如蓝牙协议);另外簇中 点,借助于仿真模拟的方法对这3种算法进行了比较。在此的资源通常由簇内节点按照轮洵的方式共亨,所以当簇内节 选取采用了下列指标:簇头数C、网络的负载平衡因(LBF)点过多时,每个节点的平均吞吐量会急剧下降,且簇头的数目减 和节点充当簇头时间。 少了也意味着减少了信道的空间重用率。 LOWID和NWCA 32模拟结果 的曲线走向相对接近。从图3中可以看出,相对于其他两种 在仿真测试中,节点数M=32,节点最大的移动速度为算法,NWCA算法得到的簇头分布较均匀。 、=5m/s,节点的传输范围/在5-60m之间变化(图2中,r= LOWID 25m);W1,兩2分别代表簇内、簇间的通信带宽,W2=1.2W1。图 SIICD NWCA 2中 LOWID表示最小ID算法,HCDA表示最高节点度算法, NWCA表示文中所提出的分簇算法。 从图2可以看出 LOWID算法中各节点担任簇头的时间 差异很大,ID号小的节点充当簇头的时间非常多(如节点1 ID号大的节点充当簇头的时间则非常少,因为这种算法本身 就是侧重于选择ID较小的节点充当簇头,这会使得ID号小的 10203040 节点负担较重,易过早地耗尽其电池能量而使它成为內络通 传输距离/m 信的瓶颈。CDA则倾向于选择具有最大连接度的节点作为 图3簇头数与传输距离的关系图 簇头,虽有所改善,但改善不大。NwCA算法则改善较大,因 在仿真实验中采用了W2=1.2W1,根据最佳连接度大小B 1142010,46(21) Computer Engineering and Applications计算机工程与应用 的计算:B=M-1=m2N-1=1.2×32-1=5.78860图4次伤真时间6005节点移动速率从0m和10ms之间分布, W 数据包大小取为定长512Byte 可以看出:与 LOWID和HCDA相比,NWCA算法中个簇的43性能指标 平均连接度非常接近最佳连接度β,这主要是因为NWCA算 (1)数据包传送率:源节点应用层产生的数据包数目和目 法中限制了簇头的节点度所致 的节点应用层接收到的分组数目的比值。该指标反应了协议 适应网络变化的性能好坏和网络所能支持的最大吞吐量。 LOWID HCDA (2)路由协议开销( Routing overhead(%)=所有路由开 112后NWCA 销控制分组(包括路由寻找分组和路由响应分组)的总数/所 有路由开销控制分组与数据分组的总数。该指标是衡量不同 协议性能的重要指标,对于无线信道,该性能指标尤其重要。 44仿真结果及分析 为了说明方便,文中仍沿用NWCA、 LOWID和HCDA分 s060 别代表相应的分层路由协议,仿真结果如图5~7所示。 传输距离/m 图5仿真了数据包传送率与网络中节点移动性的关系,仿 图4一个簇的平均节点数与 真节点50个,源节点为30个,节点的暂停时间为:0s、205、60s、 传输距离的关系图 120s、300s和600s,仿真时间为600s,其中0s代表节点一直 处于运动状态,而600s代表网络为一静态网络,即节点处于 路由算法的设计与仿真 静止状态。从图5中可以看出,3种算法分层路由协议的数据 41酱由算法的设计 包传送率都较高,并随着节点移动性的减小,数据包传送率呈 基于上述3种分簇策略,采用了CBP( Cluster Based Rout-上升趋势。三者相比,NWCA的数据包传送率略高于其他两 ing Protocol)的设计思想进行了基于“簇”的层次化路由算种,这主要是因为NWCA考虑了最佳连接度和节点能量状态 法设计,该算法策略是属于将先应式(预先路由)与反应式(按两种因素,能够有效地平衡负载 需路由)相结合的综合型的路由算法:即在簇内采用先应式而 图6为数据包传送率与仿真节点数目之间的关系图,仿 在簇间采用反应式。 真节点个数分别为:25、50、75、100和150,相应的源节点数分 每一个簇由簇头来管理簇内所有节点的全部信息及行别为:15、30、45、60和90。仿真结果表明:数据包传送率随着 中为,簇头节点通过网关节点发现吡邻簇并山此来寻找路山。仿真节点数目的增加而降低。当仿真节点数目较小时(小于 网络中的每个节点周期性地向外广播 Hello message(周期性50),三者的数据包传送率相仿,但随着网络中移动节点数量 握手信息),各节点通过 Hello Message E交换得知自己周围的增加, LOWID和HCDA的数据包传送率明显低于NWCA, 分布的一跳及二跳节点,进一步可知自身所在冈络分布的局这主要是因为随着移动节点数量的增加,簇内节点数亦随之 城冈拓扑信息,这些信息形成了寻找路由的基础。当某一节加大,簇头的负载亦随之增加,由于NWCA采用了最佳连接 点发岀路由请求后,该节点将向周围节点发出RREQ控制包,度策略,且对簇头节点的选择没有倾向性,从而能够有效抑制 各节点根据自身所在网络分布的拓扑结构及自身所处的角色各簇的移动节点数,减轻了簇头的负担和平衡了网络的负载, 采取不同的处理方式:簇头节点将RREQ转发至目的节点或防止了网络性能的下降。而 LOWID和HDA对簇头的选择 网关节点;网关节点将RREQ转发至目的节点或毗邻簇头节具有倾向性,尤其是HCDA侧重于选择连接度较高的节点成 点;普通成员节点将RREQ发往日的节点或作丢弃处理。 为簇头,故随着节点数目的增加,簇内节点的数过多,使得每 4.2仿真环境 个节点的吞吐量下降,从而影响了系统的整体性能,仿真结果 仿真软件为 OPNET10.5;节点的移动模型采用的是Ran曲线充分说明了这一点。 don Waypoint模型,仿真区域设置为150mx150m,节点在区 图7为路山协议开销与网络中节点数目的关系图,仿真 域内随机分配,恒定比特速率(CBR)的信源,包发送速率定为节点个数分别为:25、50、75、100和150,相应的源节点数分别 4包/s,每个节点的无线传输范围25m,信道容量为2Mb/s,每为:15、30、45、60和90。仿真结果表明:路由协议开销随节点 50个节点的数据包传送率 (30个CBR信源,数据包大小51 1.005 HCDA 0.75 0.99 LOWID 0.990 静0.94 E0.65 LOWID 0985 60 百090 0.97 #E 0.0FNWCA 盗 0.970 0.84, HCDA 0.965 0.82 LOWIT 0.96 0.80 0100200300400500600 0406080100120140160 20406080100120140160 暂停时间 节点数H 节点数日 图5数据包传送率与节点 图6数据包传送与网络中 图7路由协议开销与网络中 移动性的关系图 节点数目的关系图 节点数目的关系图 杨卫东: Ad hoc网终中分簇算法的研究 2010,46(21)115 数的増加而提高。当仿真节点数目较小时(小于50),路由协[4]胡光明,蒋杰,龚正虎移动自组网络分簇算法综述计算机工程 议开销相仿,三者相比,HCDA稍优于其他两种,主要是因为 与科学,2005,27(1):48-50 HCDA优点在于可使网络中簇的数目减少,且在移动节点数5] Gerla M, Tsai jt C Multicluster, mobile, multimedia radio net 较小的情况下,簇内的节点数不多,簇头的负载较小;但随着 work[J]. Wireless Networks, 1995, 1(3): 255-265 网络中移动节点数量的增加,HCDA反而略高于其他两者,主6inCR, Gerla M. Adaptive clustering for mobile wireless net- 要是当网络中节点数増加的同时簇内节点数亦随之加大,簇 works[J].IEEE Journal on Selected Areas in Communications 头的负载亦随之増加所致;而NwCA路由协议开销略低于 1997,15(7):1265-1275 LOWID和HCDA是因为NWCA考虑了最佳连接度和节点能 [7 Parekh A K Selecting routers in Ad-Hoc wireless networks[C]// 量状态因素,平衡了网络负载所致。仿真结果曲线充分体现 Proceedings of the SBT/IEEE International Telecommunications 了这一点。 Symposium, 1994 18] Jain A, Sengupta P RGeographical routing using partial infor mation for wireless Ad Hoc networks[J].IEEE Personal Commu 5结论 nication,2001,8(1):48-57 在分析现有分簇算法的基础上,提出了一种新的基于权 9吴迪,李晴.一种基于地理定位信息的AdHo分簇算法J计算机 值的分簇算法一NWCA,该算法考虑了移动节点的最佳连接 工程与应用,2005,41(14):138-141 度和能量状态两个因素,与 LOWID算法和HCDA算法一样具[10蒋毅,史浩山.种基于移动预测的自适应 Ad hoc网络分簇算 有算法计算简单、实现方便和算法收敛快的特点;与 LOWID 法[计算机科学,2007,34(3):27-29 算法和HCDA算法相比,在其他性能指标不改变的情况下,具[11 chatterjee M, Das s K, Turgut D. WCA: a weighted clustering 有较奷的负载平衡特性和节点充当簇头的公平性。正因为 algorithm for mobile Ad Hoc networks[J]Journal of Cluster NwCA具有较好的负载平衡特性,因此它也具有较好的数据 ing Computing IEEE, 2002, 5(2): 193-204 包传输率和较少的路由协议开销。通过对NWCA算法和基12]吴迪,刘英学 Ad hoc网络中一种基于权值的分簇算法[小型 于NWCA的分层路由协议的仿真测试和分析,证明了这种算 微型计算机系统,2006,27(2):202-206 法的有效性和特点。 [13]王钢,单琦.一种新型的 ad hoc网络按需加权分簇算法[网终 技术 参考文献 14]王钢,单琦,贾世楼,等 Ad hoc网络按需加权分簇算法及其性能 [1 Nocetti F G, Gonzalez J S, Stojmenovic I Connectivity based K- 分析[南京理工大学学报,2006,30(5):599-602 hop clustering in wireless networks[J]. Telecommunication Sys 15许润萍,王盼卿,何谓AdHc分算法探讨河北省科学院4 tem,2003,22(1/4):205-220 学报,2006,23(2):41-44 [2] Yang Wei-dong, Zhang Guang-zhao. A weight-based clustering al- [16] Xu Kai-xin, Hong Xiao-yan, Gcrla M An Ad Hoc network with gorithm for mobile Ad Hoc network[C]/Proceedings of the 3rd mobile backbones[c]/IEEE International Conference on Com International Conference on Wireless and Mobile Communica- munications. 2002-05 tions ICWmc 07, 200 [17 Jiang M L, Li J Y, Tay Y C Cluster Base Routing Protocol [3]杨卩东,张光昭 Ad hoc网络在紧急救援中的应用电信科学 (cbRp)[Eb/oL].(2009).http://www.math.nus.edu.sg/mattyc 2008,24(4):101-105 cbrp. txt (上接65页) 出版社.2003 的数据发送方案使带宽利用率有了较大程度的提高,特别是2]宋玮弹性分组环技术研究[D]杭州:浙江工业大学,2006:40.44 对于数据流F(2,3),它占用的链路带宽几乎提高了五倍多,[3]张便利,常胜实现虚拟输出队列调度的神经网络方法门光电子 该方案充分发挥了弹性分组环的空间复用特性。 激光,2005,16(11):1316-1320 [4 IEFE Std 802. 17TM-2004 TEFF standard for information tech 5小结 nology telecommunications and information exchange between 改进了IEEE80217标准建议的数据发送方案,将原有的基 systems local and metropolitan area networks specific require 于数据类型的数据发送方案改进为基于流的数据发送方案,改 ments Part 17: Resilient Packet Ring(rPR) access method and ohysical layer specifications[S]. New York: IEEE Computer So 进的数据发送方案在硬件上需要虚拟输出队列的支持,这在一 ety,2004 定程度上增加了硬件的复杂度。新方案采用基于帧的动态加权 「5]李慧玲,周继成.加杈轮询算法在TCP非对称网络屮的应用及其性 轮询调度算法,保证了各个数据流的公平性,同吋时克服了传统轮 能分析[计算札工程与应用,2000,36(3):10-1l 询调度算法中长帧占用较大带宽的缺陷。仿真结果表明算法提61 Chao h J, Liu Bin. High performance switches and routers[M 高了RPR的带宽利用率。综上所述,改进的方案以提高硬件复 Hoboken, New Jersey, John Wiley Sons, Inc, 2007: 138-142 杂度为代价,増强了弹性分组环空间复用的性能。 [7]FallK,VaradhanK.Thensmanual[eb/Ol].(2008).http://www.isi edu/ nsnam/ns/ns-documentation 参考文献 [8]方路平,刘世华,陈盼,等NS-2网络模拟基础与应用[M]北京:国 [陶智勇,张继军,包立明,等弹性分组环M]北京:北京邮电大学 防工业出版社,2008:62-63

...展开详情

论文研究 分簇算法 csdn