ad hoc网络中连通支配集算法研究

《ad hoc网络中连通支配集算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、兰州理工大学硕士学位论文AdHoc网络中连通支配集算法研究姓名：张冰燕申请学位级别：硕士专业：计算机软件与理论指导教师：张远平20080501硕十学位论文摘要AdHoc网络是一组带有无线收发设备的移动节点组成的多跳的临时性无中心网络，可以在任何时刻、任何地点快速构建起一个移动通信网络，并且不需要现有网络基础设施的支持。在AdHoc网络中移动节点不仅要负责通信任务，同时还要担当路由功能。而基于全网的洪泛机制会引起广播风暴问题，这将消耗大量的网络资源。由于网络拓扑结构动态变化性、多跳通信特性和资源的有限性，

2、合理的路由设计成了一个挑战性的问题。对此，许多学者提出通过构造虚拟骨干网，将网络分级来实现网络的稳定性和高效性。通过在AdHoc网络构建虚拟骨干网即可将网络中节点进行分级，而这一过程正是图论中连通支配集理论的一个应用。可以将路由简化到由最小连通支配集构造成的虚拟骨干网中去。消息从源节点沿着CDS中的节点传递到离目的节点最近的支配节点，最终到达目的节点。本文以支配集做为研究问题的理论基础，对传统的构造连通支配集方法进行深入研究，针对以上所列举的技术的不足，提出了改进的算法。在构造连通支配集的算法时，有以下

3、四个方面的因素度量算法的性能：算法的近似比、局部性、时间复杂度和消息复杂度、以及稳定性。因此，考虑到主机的剩余能量的大小、节点度大小、以及移动速度等因素对于所构建的连通支配集稳固性起着重要的作用，提出了一种改进的基于权值的最小连通支配集构造虚拟骨干网的改进算法。并给出了权值的计算公式，确保了性能强的主机优先担当支配节点。另外，还针对节点移动的情况下，如何维护连通支配集提出了维护策略。证明了该算法具有较低的时间复杂度和算法复杂度。关键词：AdHoc网络：虚拟骨干网；连通支配集：分布式算法；权值AdHoc网

4、络中连通支配集算法研究AbstractHoci8aspecial乜旧eofwirele鹤mobilenetwDrkinwhichacoUectionofmobilehostswithwirele蹈networki玎．terfacesfornlsatempor龇ynetwork，withouttheaid0fanyestablishediⅡf}astructureorcentrauzedadministration．InHocnetwork出lroutingandnetworkmanageInentfun

5、ctio璐删lstbeperformedbyordinarynod储．Duetothef色atllr鹤ofdynamictopolognInulti．hopcommuIlic扣tion，and8trictresollrcelimitatio璐，AdHocroutingbecomesthem08tchallengeproblem．AlIIlostaUe)【istingtopol0母厂-b嬲edroutingprotocolsiIlvol、retheglobal丑ooding，whichsuⅡ-ersf而m

6、thenotoriousbroadcaststormproblem．Thiscaus鹤highprotocolo、，erheada以diIlterfhencetoongoingtramcs．IIlspiredbythep11y争icalbackboneiIlthe耐Ded咖rk，manyre8E搬chersproposedtheconceptof讥rtualbackbonei11f}鹄tmcture，谢hichorganizesthe11ier甜chic址stmctureofor-dina珂node8t

7、0achievescdabilityandemciency．Inordertoachievethat，玳脚aJ90ritllI瑚hayee刀∞rgedthatrelyonavi卜tualnetworkiI血嬲tructure，wllichorganize8ordinaryn．埘esintoahierarchyTheco璐tmction0fthisinh鹄tructureistheprima巧印plicationofCo彻胱tedDom-inatingSets(CDSs)in而re蛔8ne七worl【s．

8、ACDScancreatea们rtualnetworkbackboneforpaucketrouting舡ldC0ntr01．Me8sag邸canberouted丘omthesourcetoaneighbori11thedominating踯t，alongtheCDStothedominatingsetmem-berclosesttothedestinationnode，andthenfinaIllyt0thedestination．Int