无线传感器网络中连通支配集的构造算法研究

摘要

无线传感器网络(Wireless Sensor Networks, WSNs)通常是指由数目众多的传感器节点大规模布局而形成的网络系统,节点利用无线通讯、多跳和自组织的方式把收集的信息传递到基站。在现实生活中,它被广泛地运用于战场侦测、家居智能和管理自动化等众多领域。WSNs因在应用方面有很多优点而成为了众多高校和机构研究的热门方向。由于传感器节点具备体积小、能量低、处理和存储能力较低等特点,且它一般地处人类无法抵达的地方(不能对它进行人为补充能量),因此怎样高效利用网络中的节点能量从而使它的寿命最长,从一开始就成为了WSNs中值得研究的热点课题。而连通支配集作为WSNs的虚拟主干网在高效利用网络能量上具有良好的表现。
　　本研究为了解决WSNs中无固定的基本设施和节点能量消耗不均衡的问题,设计了构建连通支配集的分布式近似方案,此算法综合考虑了节点的剩余能量、连通支配集规模和连通支配集重构等因素。我们从理论上证明了算法的正确性,实验结果表明,与相关的分布式算法相比,此算法构造的连通支配集在规模上更优,可使网络寿命更长。此外,为了解决因节点失效或节点间无法通信而引起的连通支配集要经常重新构建的问题,本文还设计了一种构建具有容错性的连通支配集分布式近似算法,即在网络中构造一个k-连通m-支配的集合(也称为(k, m)-连通支配集)。该算法综合考虑了(k, m)-连通支配集的规模和节点的剩余能量等因素,且本文从理论上证明了算法的正确性。仿真实验结果与相关算法比较,该算法得到的(k, m)-连通支配集在规模上更小,且其节点的平均剩余能量更高。这样,(k, m)-连通支配集在网络中工作的时间会更长,从而减少了因频繁重新构造连通支配集而额外耗费的能量,延长了网络的生存时间。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.2 国内外研究现状

1.4 本文的组织结构

第二章 背景知识

2.1 无线传感器网络

2.2 网络的拓扑结构与路由算法

2.3 网络模型

2.4 相关图论知识

2.5 本章小结

第三章 一种能量有效的连通支配集构造近似算法

3.1 引言

3.2 相关工作

3.3 网络模型和相关定义

3.4 连通支配集的构造算法

3.5 理论分析

3.6 仿真实验

3.7 结束语

第四章 一种容错性的连通支配集构造近似算法

4.1 引言

4.2 相关工作

4.3 相关定义

4.4 (k, m)-连通支配集的构造算法

4.5 理论分析

4.6 仿真实验

4.7 结束语

第五章 总结与展望

5.1 本文工作总结

5.2 工作展望

参考文献

攻读学位期间本人的科研论文

致谢