学位论文 > 优秀研究生学位论文题录展示

无线传感器网络中k-连通k-支配集的集中式构造研究

作　者: 张瑞宏
导　师: 孙立山
学　校: 哈尔滨工业大学
专　业: 电工理论与新技术
关键词: 无线传感器网络 连通支配集 集中式算法 2-连通图
分类号: TP212.9
类　型: 硕士论文
年　份: 2008年
下　载: 37次
引　用: 0次
阅　读: 论文下载
 

内容摘要


无线传感器网络是计算、通信和传感器这三项技术相结合的产物,它随着微处理器和无线通信技术的发展,在军事、医疗、环境等方面具有广泛的应用潜力。由于传感器节点能量有限,节点的失效会导致网络链路失败,因此在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网进行分层路由,对重要的目标或环境需要构造容错性高,可靠性好的虚拟骨干网。本文采用集中式算法研究连通支配集的构造,主要适用于具有中心控制或管理节点的无线传感器网络。对于1-连通1-支配集的构造,本文详细系统地比较了单方向搜索和多方向搜索两种集中式算法。通过比较得出,单方向搜索算法运行的时间短,多方向搜索算法构造的连通支配集小。为了提高网络的容错性和可靠性,本文提出两种2-连通2-支配集的集中式构造算法,分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路,然后以此回路为基础不断地扩充此回路,直到不在回路中的节点为2-被支配为止;后一种算法是首先保证每个非支配点的状态都为2-被支配,然后再使图中所有支配点构成回路。仿真结果表明算法先回路后支配适用于节点密度较低的网络,而算法先支配后回路适用于节点密度较高的网络。在某些特殊领域,需要构造容错性更高和可靠性更好的网络,本文提出k -连通k -支配集的集中式构造算法, k适用于任意自然数。该算法被称作先支配后连通,即首先保证图中所有节点都变为支配点或k-被支配点,其次选择一个边缘支配点着色,然后对其它支配点逐点着色,着色的条件是该点是已着色节点的邻接点,且和已着色节点均为k-连通,若不满足此条件,添加适当的支配点再接着着色,直到图中所有支配点均被着色为止。最后通过计算机编程实现,证明了该算法的有效性。

全文目录


相似论文

  1. 基于本体的语义查询扩展研究,TP391.3
  2. 无线传感器网络覆盖控制的研究,TP212.9
  3. 无线传感器网络中基于连通图的分簇路由协议（CRPCG）的研究,TP212.9
  4. 6连通图中的可收缩边,O157.5
  5. 基于无线传感器网络的覆盖与连通问题的研究,TN929.5
  6. 频繁子图挖掘算法的研究,TP311.13
  7. 图的临界群和染色唯一性的研究,O157.5
  8. Ad hoc网络可生存性研究,TN929.5
  9. 图的低阶限制边连通度的研究,O157.5
  10. 基于无线传感器网络的粮库粮情监测系统设计,TP274.4
  11. 图的k-限制边连通度的最优性和超级性,O157.5
  12. 城市轨道交通联络线规划布局研究,U239.5
  13. 移动Ad hoc网络中文件广播分发算法的研究与实现,TN929.5
  14. 图的群着色数,O157.5
  15. 超宽带技术及其在无线传感器网络的应用研究,TN925
  16. 基于NWCA和测度函数的Ad Hoc分簇算法研究,TN929.5
  17. 连通性、邻域、路和圈,O157.5
  18. 汽车线束图纸的自动布局研究,TP391.72
  19. 混合P2P网络基于后备超级节点的容错机制研究,TP393.02
  20. 异构系统故障诊断研究,TP332

中图分类: > 工业技术 > 自动化技术、计算机技术 > 自动化技术及设备 > 自动化元件、部件 > 发送器（变换器）、传感器 > 传感器的应用
© 2012 www.xueweilunwen.com