资源描述：
《移动adhoc网络的分簇算法及性能比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2004年2月北京邮电大学学报Feb.2004第27卷第1期JournalofBeijingUniversityofPostsandTelecommunicationsVol.27No.1文章编号:1007-5321(2004)01-0093-05移动Adhoc网络的分簇算法及性能比较王海涛(解放军理工大学通信工程学院,南京210007)摘要:阐述了Adhoc网络的体系结构和存在的问题.讨论了Adhoc网络中几种典型的分簇算法.通过模拟在不同的网络环境下对各种算法进行了性能比较和分析.关键词:移动
2、Adhoc网络;体系结构;分簇算法;服务质量中图分类号:TN393.01文献标识码:AClusteringAlgorithmsofMANETandPerformanceComparisonsWANGHai-tao(CommunicationEngineeringSchool,People'sLiberationArmyUniversityofScienceandTechnology,Nanjing210007,China)Abstract:Thearchitecturesandexistentpr
3、oblemsofAdhocnetworksareexpounded.SeveraltypicalclusteringalgorithmsinAdhocnetworkarediscussed.Performancecomparisonsandanalysisbetweenthosealgorithmsareperformedbysimulationindifferentnetworkenvironments.Asummarizationisgiven.Keywords:mobileAdhocnetw
4、ork;architecture;clusteringalgorithm;qualityofservice移动Adhoc网络(MANET)的体系结构可分为平面式和分级式.平面结构比较健壮,但是控制开销大,可扩展性不佳,主要适用于中小型网络.分级结构中,网络划分成簇,每个簇包[1]含一个簇头和多个簇成员,簇头和网关构成虚拟骨干网.分级结构的优点是网络可扩充性好,容易实现网络的管理和同步.另外,基于分簇结构,MANET可采用类似蜂窝网络的资源[2]分配方法.在簇内,簇头可以控制节点的业务接入请求并合理
5、分配带宽.因此通过分簇算法将网络划分成簇可以提高Adhoc网络的性能,具有重要意义.1分簇算法的目标分簇算法的目标是构造一个能够覆盖整个网络并较好支持资源管理和路由的互连的簇集合.为减少分簇开销,分簇算法应简单高效,当只有很少节点移动和拓扑变化较慢时,网络应尽量保持原有结构,从而减少重新分簇引入的开销并提高网络效能.理想情况下希望以最少的簇收稿日期:2002-11-18作者简介:王海涛(1976—),男,博士,讲师.E-mail:wht_slh@tom.com94北京邮电大学学报第27卷头覆盖整个
6、网络,即簇头的集合为最小统治集(MDS).网络的统治集是由所有簇头组成的集合,并且满足其他节点都是统治集中某节点的邻居节点.进一步还可考虑限制簇头成为邻居节点,即簇头的集合构成网络的统治无关集(DIS).满足MDS的簇头优化问题等价于最小集覆盖问题(MSC),后者是NP完全问题,因此一般采用启发式算法.2几种典型的Adhoc网络分簇算法2.1最高节点度启发式算法[1]最高节点度分簇算法的目标是提高网络的控制能力和减少簇的数目.算法工作过程描述如下:(1)初始时,网络中每个节点标记为白色;(2)当一
7、个白色节点发现它是邻居白色节点中节点度最大的节点时,它成为簇头,并标记自己为黑色(节点度相同时选择ID较小的节点为簇头);(3)簇头的邻居成为簇的普通节点,并标记为灰色;(4)重复(2)和(3),直到网络中不存在白色节点.该算法的特点是簇数目较少,减少了分组投递时延,但也减少了信道空间重用率.由于簇内节点数不受限制,并且信道由节点共享,当簇内节点数量过多时,每个节点的吞吐量急剧下降.此外,当节点移动性较强时,簇头更新频率较高,簇维护开销较大.因此,该算法适合于移动性较弱并且节点密度较低的场合.2.
8、2最小ID启发式算法[3]最小ID启发式算法只依据节点ID选择簇头,即在最高节点度算法的步骤(2)中,相邻白色节点中ID最小的节点为簇头.该算法计算简单,实现方便.在移动环境下,最小ID算法[1]的簇头更新频率较慢,维护簇开销较小,并且网络的吞吐量高于最高度启发式算法.但是该算法倾向选择ID较小的节点为簇头,使这些节点消耗更多的能量,减少了网络出现分割的时间,并且没有考虑负载平衡等因素.2.3节点权重启发式算法[4]节点权重启发式算法基于适合作为簇头的程度来为每个节点分配权重.即在
