论文部分内容阅读
本学位论文的工作来源于国家自然科学基金项目“基于同调理论的无线传感器网络k重覆盖若干算法研究”(批准号:61601122)。论文针对节点位置信息以及节点间距离信息未知的场景,对无线传感器网络(WSNs,Wireless Sensor Networks)中的覆盖空洞修复和优化等问题展开研究,提出了基于波达角(AOA,Angle of Arrival)的空洞修复算法和基于同调理论的覆盖优化算法。在本论文提出的空洞修复算法ABHH(AO A Based Hole Healing)中,利用波达角和节点间连通信息,调动移动节点进行空洞修复,付出尽可能少的节点移动消耗以实现目标区域全覆盖。本论文提出的覆盖优化算法SE(Simplex Extension based Optimization)针对目标区域全覆盖的情况,最大化冗余节点的休眠数量以降低维持全覆盖的能量消耗,从而延长网络寿命,此外算法中给出了实现k重覆盖的节点调度方法。本论文的主要贡献如下:(1)提出了基于AOA和同调理论的空洞修复算法。算法基于现有算法得到的空洞边界,根据节点权重选择修复节点,利用AOA信息判断修复节点所处位置并计算出前进方向引导节点进入空洞。在空洞中,修复节点根据节点间连通信息和AOA信息移动至理想位置进行修复并更新空洞边界,不断迭代进行以上过程直至空洞消失。仿真结果表明,本算法在节点密度大的情况下能够稳定地将目标区域覆盖率提高到99.5%以上,且节点的总移动距离较小。本算法的计算复杂度为O(n2),其中n为节点的平均邻节点数。(2)提出了基于同调理论的覆盖优化算法。本算法不依赖节点的位置信息和节点间距离信息,在实现了全覆盖的WSNs中通过单形扩张算法判断节点冗余,删除冗余节点以构建尽可能多的一重独立覆盖集合实现轮替覆盖以延长网络生命或共同作业完成k重覆盖。仿真结果表明本算法构建1重独立覆盖集时能够在不改变网络拓扑特性的前提下休眠接近于理论上限数量的冗余节点,且在不同条件下结果稳定有效。本算法的计算复杂度为O(n2),其中n为节点的平均邻节点数。