基于维诺图和二分图的水面移动基站路径规划方法研究

摘要

近年来，随着相关研究的不断深入，无线传感器网络已成为一种十分重要的信息技术，目前已被广泛应用于生产、监测、通信以及军事等领域。水面传感器网络作为无线传感器网络的一个重要分支，具有节点稀疏布置的特点，因此难以通过节点间的多跳路由汇聚数据，主要通过移动基站来收集网络中数据。在水面传感器网络中，如何规划出一条最优的移动基站路径成为一个关键问题。本文针对这一问题进行研究，提出了一种基于维诺图和二分图的水面移动基站路径规划方法。大量实验结果表明该方法可以有效规划出水面传感器网络中移动基站的路径，不仅可以完成全网数据收集任务，而且具有路径长度短、能量效率高和节点能耗均衡的优点。
　　本文研究的主要内容及主要创新之处在于:
　　(1)将维诺图理论引入水面传感器网络的移动基站路径规划问题中。应用维诺图理论对水面传感器网络进行建模，由传感器节点集合构造出相应的维诺图，利用维诺图的性质得到一系列数据收集“候选点”，即维诺图顶点。与传统方法中移动基站前往传感器节点处收集数据的模式相比较，本文创新性的设计了移动基站前往维诺图顶点处收集传感器节点数据的方法。通过理论和实验证明了在维诺图顶点处收集传感器节点数据，可以使传感器节点能耗均衡。
　　(2)将图论中的二分图和支配集理论引入建立的维诺图模型中。由维诺图顶点和传感器节点的关系构造出二分图，并定义了支配的概念，然后通过二分图的形式来描述维诺图顶点和传感器节点间的支配关系;同时在借鉴支配集定义和求解方法的基础上，定义了“最小有效支配集”的概念，并给出了最小有效支配集的精确求解方法和快速近似求解方法，从而将水面移动基站的路径规划问题转化为基于最小有效支配集的TSP问题。最后通过大量仿真实验验证了方法的有效性和先进性。
　　本文的研究工作和成果对于提高水面移动基站路径规划问题的理论和工程水平具有一定的参考价值。

目录

声明

致谢

摘要

第一章 绪论

1．1 课题研究背景

1．2 国内外研究现状

1．3 课题来源、研究目的及意义

1．3．1 课题来源

1．3．2 课题目的

1．3．3 课题意义

1．4 论文研究内容及章节安排

1．4．1 论文研究内容

1．4．2 论文章节安排

第二章 维诺图、二分图、支配集相关知识

2．1 维诺图

2．1．1 维诺图定义

2．1．2 维诺图性质

2．1．3 维诺图构造方法

2．1．4 维诺图应用

2．2 二分图

2．2．1 二分图定义

2．2．2 二分图判定

2．2．3 二分图匹配

2．2．4 二分图应用

2．3 支配集

2．3．1 支配集定义

2．3．2 支配集性质

2．3．3 支配集算法

2．4 本章小结

第三章 基于维诺图和二分图的水面移动基站路径规划方法

3．1 网络和通信模型

3．2 路径规划方法设计

3．2．1 生成数据收集候选点

3．2．2 描述维诺图顶点与节点的支配关系

3．2．3 求解最小有效支配集

3．2．4 形成优化路径

3．3 复杂度分析

3．4 性能评价指标

3．4．1 路径长度

3．4．2 网络总能耗

3．4．3 能量效率

3．5 本章小结

第四章 仿真实验分析

4．1 可行性分析

4．2 与相关方法的性能比较

4．2．1 路径长度比较

4．2．2 网络总能耗比较

4．2．3 能量效率比较

4．3 节点能耗均衡性分析

4．4 本章小结

第五章 总结与展望

5．1 总结

5．2 对未来工作的展望

参考文献

攻读硕士学位期间的学术活动及成果情况