无线传感器网络分布式连通支配集构造方法研究

摘要

无线传感器网络（Wireless Sensor Network，WSN）是21世纪极具应用价值的新兴学科之一。通过WSN人们可以即时监控，收集并分析WSN监测区域内监测对象的各种有效信息，并可将有效信息通过WIFI、GPRS、移动数据网络等多种方式传送到任务管理节点，以此达到对监测目标情况变化的实时监控与及时报警。WSN具有易于布置、监控区域广和环境适应力强等特点，如今，无论在军事、商用还是民用领域，WSN技术都受到越来越多的重视，而有效地构造WSN的虚拟骨干网（Virtual-Backbone）则是当今WSN领域的一个热点研究课题。
　　因为WSN传感器节点体积小，分布范围广，所以对传感器节点的管理和维护十分困难，构造一个高效的虚拟骨干网，可以从软件方面延长网络的生存时间，降低维护成本。本文通过求解性能最优的连通支配集（Connected Dominating Set，CDS）来构造虚拟骨干网。最小连通支配集的求取已经被证明是NP完全问题，现在最通用的手段是通过启发式的方法求得最优解。求取连通支配集的算法主要分为集中式和分布式两种，因为WSN的动态性特点，集中式算法难以适应网络的实时变化，故多采用分布式的求取算法。本文提出了两个优化的分布式CDS求解算法：MI-LCDS（Multi-Initiator Layer Based CDS Construction Algorithm）算法和FNDB（A Forward1-hop neighbor Information set Based Distributed algorithm for Virtual Backbone）算法。
　　MI-LCDS算法提出了基于多发起者的网络分层模型，首先根据网络的规模选取数个源节点，源节点独立地进行各自区域范围内的网络划分，得到分层结构，网络各层分布式地求取本层的CDS。最后，不同源节点的CDS通过桥梁节点连通，完成整个网络CDS的构造。MI-LCDS算法的时间复杂度为O(Δ2)。
　　FNDB算法只需一跳邻居节点信息，在成功求取节点的边界交点集后，再推导出其转发集，通过染色法在转发集中求出支配节点来构造一个CDS。仿真结果表明，FNDB算法产生的额外消息数约等于CDS的大小，而收敛时间约等于WSN的网络直径。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1无线传感器网络

1.2连通支配集构造算法的国内外研究现状

1.3本文的主要研究方向及整体结构

第二章 构造连通支配集的理论基础

2.1基础图论知识

2.2连通支配集理论

2.3典型的连通支配集算法

2.4符号表及相关概念

第三章 基于多发起者网络分层的连通支配集算法

3.1 问题描述

3.2 算法描述

3.3 算法分析

3. 4 仿真设计与结果分析

3.5 本章小结

第四章 基于邻节点集转发信息的分布式支配集算法

4.1 问题描述

4.2 算法描述

4.3算法分析

4.4 仿真设计与结果分析

4.5 本章小结

第五章 结论与展望

致谢

参考文献

攻读硕士期间取得的研究成果