WSN中最大覆盖集问题的研究

摘要

随着便宜又小型的无线传感器的广泛使用，无线传感器网络(WSN)逐步深入到各个领域之中，但是传感器传感距离、通信距离以及能量方面的缺陷严重影响其应用，本文主要研究能量有限问题，即使用节能算法实现网络寿命的延长。由于当前很多节能研究利用了电池状态转换理论和最大覆盖集的思想，因此本文也是基于以上两个技术展开的算法研究，主要完成的工作为以下几个部分:
　　第一，调研无线传感器网络的节能技术;
　　第二，提出基于Cov策略的Heuristic算法。本文基于MDS-MCC的Heuristic算法建立了自己的网络模型，并且针对该算法中的Greedy策略提出了Cov策略，改善了该算法的两个缺陷，一个是子图的划分，另一个是Greedy策略的局限性，从仿真实验结果可以得知基于新策略的Heuristic算法比之前的在网络寿命值、稳定性和算法运行时间方面都有优势;
　　第三，提出针对单跳网络和多跳网络中的剩余节点所采用的不同算法，即为覆盖调节和网络重构，仿真实验结果可以证明这两种算法能够有效解决网络中被闲置的传感器节点的浪费，更有利于提高网络寿命值，同时保证算法稳定性。
　　总之，本文分别对冗余节点和剩余节点进行了节能算法的研究，仿真实验结果证明新提出的解决方案都是有效的。

目录

声明

摘要

1 绪论

1．1 课题研究背景和意义

1．2 WSN的国内外研究现状

1．2．1 国内研究现状

1．2．2 国外研究现状

1．3 本文研究内容

1．4 本文结构

2 WSN概念和节能算法概述

2．1 WSN的基本元素

2．1．1 连通性

2．1．2 覆盖性

2．1．3 网络寿命

2．2 节能算法

2．2．1 Heuristic算法

2．2．2 Greedy算法

2．2．3 k-覆盖算法

2．3 本章小结

3 基于Cov策略的Heuristic算法

3．1 构建网络模型

3．1．1 模型建立

3．1．2 模型转换

3．1．3 模型数据结构

3．2 Heuristic算法

3．2．1 Greedy策略的缺陷

3．2．2 Cov策略

3．3 算法的实现

3．3．1 Greedy的实现

3．3．2 Cov的实现

3．4 实验结果及分析

3．4．1 实验样本

3．4．2 NF值分析

3．4．3 稳定性分析

3．4．4 算法运行时间分析

3．5 本章小结

4 基于RN的节能算法

4．1 RN问题引入

4．1．1 单跳网络的RN问题

4．1．2 多跳网络的RN问题

4．2 RN节能算法及实现

4．2．1 基于单跳网络的覆盖调节算法

4．2．2 基于多跳网络的网络重构算法

4．3 实验结果及分析

4．3．1 实验样本

4．3．2 NF值分析

4．3．3 稳定性分析

4．3．4 相关因素对NF值影响分析

4．4 本章小结

5 总结与展望

5．1 全文总结

5．2 研究展望

参考文献

攻读学位期间主要的研究成果目录

致谢