2004年2月第27卷第1期北京邮电大学学报Journal of Beijing U niversity of Po sts and T elecomm unicati ons Feb.2004V o l .27N o.1 文章编号:100725321(2004)0120093205移动Ad hoc 网络的分簇算法及性能比较王海涛(解放军理工大学通信工程学院,南京210007)摘要:阐述了A d hoc 网络的体系结构和存在的问题Ζ讨论了A d hoc 网络中几种典型的分簇算法Ζ通过模拟在不同的网络环境下对各种算法进行了性能比较和分析Ζ关 键 词:移动A d hoc 网络;体系结构;分簇算法;服务质量中图分类号:TN 393101 文献标识码:ACluster i ng A lgor ithm s of M ANET and Performance Com par ison sW AN G H ai 2tao(Comm unicati on Engineering Schoo l ,Peop le’s L iberati on A r m y U niversity of Scienceand T echno logy ,N anjing 210007,Ch ina )Abstract :T he arch itectu res and ex isten t p rob lem s of A d hoc netw o rk s are expounded .Several typ ical clu stering algo rithm s in A d hoc netw o rk are discu ssed .Perfo r m ance com parison s and analysis betw een tho se algo rithm s are perfo r m ed by si m u lati on in differen t netw o rk environm en ts .A summ arizati on is given .Key words :m ob ile A d hoc netw o rk ;arch itectu re ;clu stering algo rithm ;quality of service收稿日期:2002211218作者简介:王海涛(1976—),男,博士,讲师Ζ E 2m ail :w h t _slh @tom .com 移动A d hoc 网络(M AN ET )的体系结构可分为平面式和分级式Ζ平面结构比较健壮,但是控制开销大,可扩展性不佳,主要适用于中小型网络Ζ分级结构中,网络划分成簇,每个簇包含一个簇头和多个簇成员,簇头和网关构成虚拟骨干网[1]Ζ分级结构的优点是网络可扩充性好,容易实现网络的管理和同步Ζ另外,基于分簇结构,M AN ET 可采用类似蜂窝网络的资源分配方法[2]Ζ在簇内,簇头可以控制节点的业务接入请求并合理分配带宽Ζ因此通过分簇算法将网络划分成簇可以提高A d hoc 网络的性能,具有重要意义Ζ1 分簇算法的目标分簇算法的目标是构造一个能够覆盖整个网络并较好支持资源管理和路由的互连的簇集合Ζ为减少分簇开销,分簇算法应简单高效,当只有很少节点移动和拓扑变化较慢时,网络应尽量保持原有结构,从而减少重新分簇引入的开销并提高网络效能Ζ理想情况下希望以最少的簇49北京邮电大学学报第27卷 头覆盖整个网络,即簇头的集合为最小统治集(M D S)Ζ网络的统治集是由所有簇头组成的集合,并且满足其他节点都是统治集中某节点的邻居节点Ζ进一步还可考虑限制簇头成为邻居节点,即簇头的集合构成网络的统治无关集(D IS)Ζ满足M D S的簇头优化问题等价于最小集覆盖问题(M SC),后者是N P完全问题,因此一般采用启发式算法Ζ2 几种典型的Ad hoc网络分簇算法211 最高节点度启发式算法最高节点度分簇算法[1]的目标是提高网络的控制能力和减少簇的数目Ζ算法工作过程描述如下:(1)初始时,网络中每个节点标记为白色;(2)当一个白色节点发现它是邻居白色节点中节点度最大的节点时,它成为簇头,并标记自己为黑色(节点度相同时选择I D较小的节点为簇头);(3)簇头的邻居成为簇的普通节点,并标记为灰色;(4)重复(2)和(3),直到网络中不存在白色节点Ζ该算法的特点是簇数目较少,减少了分组投递时延,但也减少了信道空间重用率Ζ由于簇内节点数不受限制,并且信道由节点共享,当簇内节点数量过多时,每个节点的吞吐量急剧下降Ζ此外,当节点移动性较强时,簇头更新频率较高,簇维护开销较大Ζ因此,该算法适合于移动性较弱并且节点密度较低的场合Ζ212 最小I D启发式算法最小I D启发式算法[3]只依据节点I D选择簇头,即在最高节点度算法的步骤(2)中,相邻白色节点中I D最小的节点为簇头Ζ该算法计算简单,实现方便Ζ在移动环境下,最小I D算法的簇头更新频率较慢,维护簇开销较小,并且网络的吞吐量高于最高度启发式算法[1]Ζ但是该算法倾向选择I D较小的节点为簇头,使这些节点消耗更多的能量,减少了网络出现分割的时间,并且没有考虑负载平衡等因素Ζ213 节点权重启发式算法节点权重启发式算法[4]基于适合作为簇头的程度来为每个节点分配权重Ζ即在最高节点度算法的步骤(2)中,相邻白色节点中权重最高的节点为簇头(权重相同时,选择I D较小的节点)Ζ一种方法是根据节点的移动速率为节点分配权重,移动速度越快,分配的权重越低,可以看作是最低移动性分簇算法Ζ在移动性较强时,该算法可以明显减少簇头更新频率Ζ它的缺点是节点权重的更新较频繁,簇头计算开销较大,并且未考虑负载平衡和节点的能量损耗问题Ζ214 自适应按需加权算法(AOW)以上算法选择簇头时只考虑某方面的因素,簇头选择不够优化Ζ为此,可采用一种组合加权算法来选举簇头以改善分簇网络的性能Ζ每个节点分配一个权值(W)指示它适合充当簇头的程度,W=am+bd+cp+d e+xΖ其中,m表示节点的移动性;d表示节点度;p表示节点的传输功率;e表示节点剩余的能量;x表示其它可能的因素对组合权重的影响Ζ参数a、b、c为权重因子,可动态调整Ζ自适应按虚加权(AOW)算法选举簇头时综合考虑4种因素[5]:节点度、节点的传输功率、节点的移动性和节点的剩余能量Ζ另外,簇的维护采用按需更新簇头的策略:只有当节点移出统治集覆盖范围时才重新选举簇头ΖAOW算法与上述算法的区别主要在于簇头的选举,这里将选举簇头的过程描述如下: (1)节点n计算其度数d n与理想度数M之差,即D n= d n-M Ζ(2)节点n计算其到所有邻居节点的距离总和P nΖ(3)根据节点n的平均移动速度来表示其移动性M nΖ(4)统计节点n 作为簇头的时间T n来表示已经消耗的电池能量Ζ(5)计算每个节点n的组合权重I n=c1D n+c 2P n +c 3M n +c 4T n Ζ其中,c 1～c 4为权重因子,某个参数越重要,权重因子越大,并满足c 1+c 2+c 3+c 4=1Ζ(6)选择相邻白色节点中I n 最小的白色节点为簇头,如果I n 相同,选择I D 较小的节点为簇头Ζ215 分簇算法示例表1 网络中某一时刻各节点的M n 和T n 节点I D M n T n 节点I D M n T n 133722222833345912453100252111416111252假设一个网络有12个节点,节点的理想度数D ideal =2,c 1=017,c 2=012,c 3=c 4=0105,各个节点的M n 和T n 如表1所示Ζ在相同网络条件下,采用以上4种算法得到的分簇网络结构分别如图1中的(a )～(d )所示Ζ从图中可以看出,4种算法得到的簇结构中,簇头数和充当簇头的节点数各不相同:最高节点度算法的簇头数较少(4个),最小I D 算法的簇头数最多(7个),而最低移动性和AOW 算法的簇头数介于两者之间(6个)Ζ图1 相同条件下4种分簇算法的分簇结果3 分簇算法的性能比较311 性能指标和模拟环境对以上4种算法比较时采用以下指标:簇头数C 、单位时间内节点重入簇的次数J (即簇间转移的次数)和统治集更新的次数U 、节点充当簇头的公平性指数(H F I )ΖH F I 为E { [t i -E (t i )] },i ∈V Ζt i 表示节点i 担当簇头的时间,E (t i )表示节点作簇头的平均时间ΖH F I 越小,节点充当簇头的公平性越好,从而延长网络分割的时间Ζ在具体模拟实现时,未考虑背景噪声、分组传输差错和冲突的影响Ζ因为模拟环境对各算法是公平的,简化模拟不会影响分簇算法的比较结果Ζ在一个100×100单位距离的区域内随机放置N 个节点,节点移动方向在[0,2Π]内随机分布,移动速度在[0,m ax V ]内随机选择,单位是距离 时间Ζ当节点到达区域边界时,它向区域内反射Ζ节点的数量、传输范围和移动速度均可根据要求动态调整Ζ为了更好地比较,在此4种算法均采用按需更新簇头的簇维护策略Ζ59 第1期王海涛:移动A d hoc 网络的分簇算法及性能比较312 模拟结果比较和分析首先比较簇头数随节点传输范围的变化Ζ固定节点数n =30,节点最大移动速度v =5,节点传输范围r 从5～70变化Ζ模拟结果如图2所示,其中LOW I D 表示最小I D 算法,H IGHD 表示最高节点度算法,WM 表示基于速率的节点权重算法,AOW 和AOW 1均表示自适应按需加权算法Ζ但前者中,M =10,c 1=017,c 2=012,c 3-c 4=0105;后者中,M =4,c 1=c 2=011,c 3=c 4=014Ζ从图中看出,簇头数随节点传输范围的增加而减少,当传输范围大于30后,速度逐渐变慢,最终收敛到1Ζ此外,H IGHD 的簇头数明显偏低,与前面分析吻合ΖAOW 的簇头数略大于WM 和LOW I D ,并且AOW 稍大于AOW 1,因为AOW 限制了节点度,簇的分布更加合理,并且AOW 中的权重c 1略大Ζ另外,模拟结果(如图3所示)表明,当节点传输范围较低时,簇数较多,簇内节点数很少,节点离开原簇的概率很小Ζ当传输范围增大时,J 逐渐增加并在传输范围为25左右达到最大值,随后J 开始下降Ζ并且可以看到,对于指标J ,各算法的性能差别较小,可比性较差Ζ图2 簇头数随节点传输范围的变化图3 重入簇次数随传输范围的变化图4 统治集更新数随传输范围的变化节点在簇间转移引入的开销较小,而统治集更新会带来较大开销,因此更加关心指标U的大小Ζ模拟结果表明(如图4所示),当节点传输范围较小时,统治集的覆盖范围(统治域)较小,节点容易移出统治域,当节点的传输范围增加时,统治域随之增加,节点移出统治域的概率减小Ζ此外可以看到H IGHD 算法的U 明显偏大,因为它选择簇头只考虑节点的度数,簇头的分布不合理,移动环境下,节点度数变化较频繁,簇头更新较多ΖAOW 的簇头较稳定,分布较均匀,并能根据节点分布自适应调节;LOW I D 的簇头较稳定,但是簇头分布不均匀;WM 能够较好适应移动性,但对其它因素(节点的分布和电池能量)考虑较少;AOW 1更加强调电池能量和节点移动性,性能略低于AOW ,但是可以减少网络分割的概率,并且簇头移动性较低,增强了骨干网络的稳定性Ζ模拟结果(图略)还表明,节点的运动速度对簇头数几乎没有影响,因为簇头的多少是由节点的传输范围决定的Ζ但是,J 和U 均随节点速度的增加而增大Ζ69北京邮电大学学报第27卷 图5 各算法的H F I 随传输范围的变化下面比较各算法下H F I 的区别Ζ节点数为30,节点最大移动速度为5,传输范围从5到150变化,模拟时间为1000Ζ从模拟结果(如图5所示)可以看出,LOW I D 和WM 的H F I 较大,AOW 的H F I 较小,而H IGHD 介于其间,并且AOW 1的H F I 略小于AOW Ζ此外,H F I基本上随传输范围的增加先增加后减小Ζ模拟结果分析如下:LOW I D 中I D 较小的节点倾向充当簇头,导致各节点作为簇头的时间偏差较大ΖWM 仅考虑节点的移动性来计算权重,因此速度较低的节点将成为簇头,导致H F I 较大ΖH IGHD 算法中节点度随节点的运动不断变化,各节点都可能为簇头,H F I 较小ΖAOW 中,节点的权重随时间不断改变,各节点都可能作簇头,H F I 较小Ζ当传输范围很小时,大多节点都是簇头,H F I 很小Ζ当传输范围增大时,簇头数减少,H F I 增大Ζ传输范围继续增加时,簇头数迅速减少,各节点作簇头的平均时间较小,H F I 也较小Ζ由于节点移出统治集时才更新簇头,当传输范围很大时,一个节点被选为簇头,它将永远是簇头,而其他节点为簇头的时间为0,所以各算法的H F I 都等于6414Ζ这也意味着传输范围过大时,各算法下节点充当簇头的公平性都不好,因此需要控制节点的传输功率Ζ4 结束语分簇结构有利于移动管理、资源分配和提高可扩展性Ζ但是分簇算法会带来计算、通信和维护开销,为此,必须设计合理的分簇算法Ζ本文比较分析了4种分簇算法的优缺点,尽管各算法都有适用场合,AOW 算法具有较低的簇维护开销和较高的自适应性ΖAOW 算法的实现复杂度稍高于只考虑单个因素的分簇算法,但是可以通过牺牲微不足道的计算开销来获得较好的系统性能Ζ在某些情况下,簇头可能成为网络瓶颈,可以考虑采用无簇头分簇算法[2]Ζ实际生成的簇中,各簇的节点数仍可能相差较大,为此,还可以借助簇分裂 合并机制来优化簇结构Ζ参考文献:[1] Gerla M ,T sai J T C .M ulticluster ,mobile ,m ulti m edia radi o netw o rk [J ].W ireless N etw o rk s ,1995,1(3):2552265.[2] L in C R ,Gerla M .A dap tive clustering fo r mobile w ireless netw o rk s [J ].IEEE Journal on SelectedA reas in Comm unicati ons ,1997,15(7):126521275.[3] L in C H R ,Gerla M .A distributed arch itecture fo r m ulti m edia in dynam ic w ireless netw o rk s [A ].IEEE Globecom [C ].1995.146821472.[4] Basagni S .D istributed clustering fo r A d hoc netw o rk s [A ].Internati onal Sympo siun on ParallelA rch itectures ,A lgo rithm s and N etw o rk s ,Perth [C ].1999.3102315.[5] M ainak Chatterjee ,Sajal K D as ,D am la T urgut .A n w eigh ted clustering algo rithm (W CA )fo r A d hocnetw o rk s [A ].IEEE Globecom 2000[C ].169721701.79 第1期王海涛:移动A d hoc 网络的分簇算法及性能比较。
