文档介绍：基于图论的槟夤歉赏惴ㄑ芯方旭明万旭明昵胙镏荽笱Ю硌妒垦宦畚研究方向:无线传感器网络导师:杨云教授,史庭俊副教授培养单位:扬州大学专业方向:计算机软件与理论月
·珹.
摘要由于无线传感器网络具有独特的优点,因此其在军事和民用领域都具有广泛的应用前景。目前,无线传感器网络正在受到越来越多的关注,因此许多与无线传感器网络相关的研究正在成为学术界的研究热点,其中,作为网络路由基础的虚拟骨干网已经成为热门的研究课题之一。由于传感器节点在电池能量、存储空间和运算速度等方面受到严格的约束,因此在设计相关无线传感器网络的算法时应该综合地考虑这些制约因素。本文基于图论分别从能量高效、负载均衡和网络容错这三个方面对无线传感器网络的虚拟骨干网算法进行了研究,主要工作包括:攵约惺叫槟夤歉赏惴ǖ墓乖斐杀竟蠛头植际叫槟夤歉赏惴ǖ骨干网规模过大的问题,本文提出了一种基于连通支配集的虚拟骨干网构造算法。该算法运用图论中的连通支配集理论以极低的成本构造了一个虚拟骨干网络,并且运用修剪规则缩小了虚拟骨干网的规模。算法综合考虑节点的能量和距离,使得虚拟骨干网的寿命更长。理论分析证明了在同构传感器网络环境下虚拟骨干网规模的最大值和算法的消息、时间复杂度。仿真分析显示了该算法在骨干网规模、消息总数和总能耗方面都要好于其它算法。攵孕枰J葑7⒂肴诤系墓歉山诘慊岜确枪歉山诘阋蚰芰肯墓於提早失效的问题,本文提出了一种基于连通坡面划分的多重虚拟骨干网轮换算法。该算法运用图论中的连通坡面划分理论构造了若干个没有公共节点的虚拟骨干网,并且使它们按照轮换周期依次承担数据转发与融合的任务,达到了均衡节点负载的目的。理论分析证明了在同构传感器网络环境下虚拟骨干网个数的最小值和算法的消息、时间复杂度。仿真分析显示了该算法在骨干网平均规模、骨干网总数和网络寿命方面都要好于其它算法。攵栽谝旃勾ǜ衅魍缁肪诚滦槟夤歉赏薷此惴ㄑ芯康牟蛔悖疚奶岢了一种基于连通支配树的异构虚拟骨干网修复算法。该算法运用图论中的连通支配树理论在异构传感器网络环境下构造了一个异构的虚拟骨干网。当失效的骨干节点造成虚拟骨干网不能连通和覆盖其它节点时,算法会对虚拟骨干网进行局部修复以恢复它的连通性和覆盖性。理论分析证明了初始虚拟骨干网规模的最大值、修复虚拟骨干网所需要的最大节点数和算法的消息、时间复杂度。仿真分析显示了该算法在骨干网规模、消息总数和网络寿命方面都要好于其它算法。基于图论的槟夤歉赏惴ㄑ芯
縧●●●●本文虽然对无线传感器网络的虚拟骨干网算法进行了一些研究,也取得了一些成果,但是仍然还有一些尚未解决的问题,需要在今后的工作中进一步地研究。关键词:无线传感器网络;虚拟骨干网;连通支配集;连通坡面划分;连通支配树扬州大学硕士学位论文
,瑃,瑆甋,甌瑃猙方旭明基于图论的槟夤歉赏惴ㄑ芯
..瑃.·:扬州大学硕士学位论文.
无线传感器网络概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..:⋯⋯⋯第绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..研究虚拟骨干网的意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..国内外在该方向的研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..本文主要研究工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯论文组织结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..无线传感器网络的体系结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..网络结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯矗⋯⋯⋯..
.⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..三色算法⋯。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯...纳惴ā评价标准⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.砺奂拗怠.⒏丛佣取时间复杂度⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..畔ⅰ构造技术⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..ù蠖懒⒓.诹ㄖ浼第基于连通支配集的虚拟骨干网构造算法⋯⋯⋯⋯⋯⋯⋯⋯引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.相关工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.惴ū尘啊算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯惴ā惴ā算法描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.;煌肌理论分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯...⒏