无线传感器网络中的覆盖和节能问题研究

摘要

传感器网络在许多领域得到了广泛应用,例如环境监测、战场监测、健康护理等。一个传感器网络有大量的小的传感器节点组成,这些传感器节点由感知、处理和通信模块等组成。一方面,由于传感器节点可能是随机分布的,所以覆盖问题是传感器网络中一个十分重要的课题。传感器网络的覆盖反映了感兴趣的区域或目标的监测效果的好坏。另一方面,节能也是无线传感器网络中一个重要的问题。首先,大部分传感器节点只有有限的电量并且不可充电。其次,由于在很多情况下,环境恶劣或者是人力不可达到的,很难去更换传感器节点的电池。在本论文中,我们主要考虑以下问题。首先,我们定义并研究了基于目标的有向传感器网络中的寻找一个覆盖集的问题,即有向覆盖集问题(directional cover set problem(DCS))。与传统的具有全向感知能力的全向传感器相比,由于技术的限制以及价格因素的考虑,有向传感器只有有限角度的感知范围。一个有向传感器网络由大量有向传感器节点组成,此类有向传感器可以切换到不同的方向,从而扩展其感知能力以覆盖给定区域内的所有目标。与全向传感器相比,有向传感器的感知角度较小,甚至在布置后不能覆盖任何目标,因此我们需要对网络中的传感器进行调度使之朝向某些方向,从而覆盖所有的目标。DCS问题寻找一个覆盖集,该覆盖集为可以覆盖所有目标的有向传感器的方向的一个子集。我们证明了DCS问题为NP完全问题,提出了两个算法并证明了其正确性。仿真结果表明了这些算法的性能。其次,我们定义并研究了基于目标的有向传感器网络中的寻找多个可相交覆盖集、且为每个覆盖集分配一段工作时间,从而最大化网络寿命的问题,即多重有向覆盖集问题(multiple directional cover sets problem(MDCS))。在MDCS问题中,我们把网络中传感器的方向组织到可相交的子集中,其中每个子集都是一个覆盖集,并且给每个覆盖集分配一段工作时间。我们轮流在每个时刻只使用一个覆盖集。当我们使用一个覆盖集时,有方向在该覆盖集中的传感器处于活跃状态且工作在该方向上,其他所有的传感器都处于睡眠状态。我们证明了MDCS问题为NP完全问题,并提出了多个算法。通过仿真,我们详尽地比较了这些算法的性能。最后,我们为基于面积的全向传感器网络提出了一个精确的节能的覆盖控制算法,即基于面积的协作睡眠算法(area-based collaborative sleeping algo-rithm(ACOS))。该算法基于传感器的净覆盖面积,通过精确控制传感器节点的状态,最大化传感器网络的面积覆盖的同时也最小化能量消耗。传感器网络的面积覆盖用被覆盖区域的大小来衡量。一个传感器的净覆盖面积是指只被该传感器覆盖的区域的面积。同时,传感器节点间的协作也被引入该算法中,以平衡节点间的能量消耗。仿真结果表明在唤醒更少节点的情况下,ACOS算法可以提供比其他睡眠算法更好的覆盖。

目录

中文摘要

英文摘要

第一章 绪论

1.1 无线传感器网络概述

1.1.1 无线传感器网络的体系结构

1.1.2 无线传感器网络的特点

1.1.3 无线传感器网络的关键技术

1.1.4 无线传感器网络的研究分支和进展

1.1.5 无线传感器网络的应用

1.2 本论文的主要研究内容和组织结构

1.2.1 研究内容

1.2.2 主要贡献

1.2.3 组织结构

第二章 传感器网络覆盖和节能问题

2.1 传感器网络中的覆盖问题

2.1.1 全向与有向传感器网络

2.1.2 覆盖对象

2.1.3 传感器节点感知模型

2.1.4 基于节点部署方式的覆盖

2.1.5 覆盖与网络连通性的关系

2.2 传感器网络中的节能问题

2.2.1 能耗分析

2.2.2 节能策略

2.3 相关研究

2.4 评价算法的主要指标

第三章 基于目标的有向传感器网络的覆盖调度

3.1 问题概述

3.2 基于目标的有向传感器网络

3.2.1 基于目标的有向传感器网络定义

3.2.2 基于目标的有向传感器网络示例

3.2.3 符号和假设

3.2.4 问题和挑战

3.3 基于目标的有向传感器网络的覆盖调度

3.3.1 DCS问题陈述

3.3.2 DCS-Search算法

3.3.3 DCS-Greedy算法

3.3.4 时间复杂度分析

3.3.5 DCS问题的性能评估

3.4 本章小结

第四章 基于目标的有向传感器网络的节能调度

4.1 问题概述

4.2 MDCS问题陈述

4.2.1 MDCS问题的简单例子

4.2.2 问题定义

4.2.3 NP完全性证明

4.3 MDCS问题的最优化建模

4.4 Progressive算法

4.4.1 冲突方向的消除过程

4.4.2 方向的选择过程

4.5 Feedback算法

4.6 MDCS-Greedy算法

4.7 分布式算法

4.8 时间复杂度分析

4.9 MDCS问题的性能评估

4.9.1 实验配置

4.9.2 参数设置

4.9.3 通信和计算开销

4.9.4 算法比较

4.10 本章小结

第五章 基于面积的全向传感器网络的覆盖控制

5.1 问题概述

5.2 ACOS算法设计

5.2.1 术语和假设

5.2.2 计算净覆盖面积

5.2.3 基本算法设计

5.2.4 扩展到不规则的感知区域

5.3 ACOS算法优化

5.3.1 状态转化图

5.3.2 死亡节点问题

5.3.3 由醒来节点引起的多重睡眠问题

5.4 ACOS算法性能评估

5.4.1 ACOS算法中的参数设置

5.4.2 与其他算法的比较

5.5 本章小结

第六章 总结与展望

6.1 论文总结

6.2 工作展望

参考文献

致谢

攻读博士学位期间发表(录用)的论文及参加项目情况