有向传感器网络中若干目标覆盖问题研究

摘要

无线传感器网络是微机电系统、无线通信和低功耗嵌入式技术不断发展的产物，在国际上被认为是继互联网之后的第二大网络。它是一种由大量传感器以自组织和多跳的方式构成的分布式无线网络，能够感知、采集和处理网络感应区域内被感知对象的信息，并将这些信息通过网络传输给终端。目前无线传感器网络广泛应用于入侵检测、环境监测、智能交通、工业控制和灾难管理等各个领域。在无线传感器网络中，覆盖问题反映了传感器对目标的监控能力和信息获取能力，是判断传感器网络服务质量的一项重要指标。有向传感器网络是更一般的传感器网络，本文将研究有向传感器网络中的目标覆盖问题，通过对传感器进行调度实现覆盖性能的最大化。本文的主要工作如下:
　　1.有向传感器网络中基于公平的目标覆盖最大化问题:在有向传感器网络中，采用具有P个工作方向的有向传感器对目标进行覆盖时，因为传感器的自身特征，每个传感器在同一个时间槽最多只能激活一个工作方向，这会导致相同传感器不同工作方向覆盖的目标之间存在覆盖冲突。在此背景下，我们研究有向传感器网络中基于公平的目标覆盖最大化问题，目的是激活最少的传感器，通过对传感器的工作方向进行调度，使目标被覆盖的最小累积时间最大。首先我们选择数目最少的传感器保证所有目标位于所选传感器的传感圆内，该问题是NP-困难问题，我们提出了一个多项式时间的（1+lnγ）-近似算法，其中γ为传感器传感圆内目标数目的最大值。其次将传感器和目标之间的覆盖关系以矩阵和向量的形式表示。基于最大需求优先服务原则、有向传感器单方向工作的限制以及传感器和目标之间的覆盖关系，我们设计了算法，通过在每个时间槽计算与累积覆盖时间最小的目标无覆盖冲突的最大的目标集合，来解决该问题。最后通过仿真实验证实了该方法的有效性。
　　2.有向传感器网络生命周期最大化问题:在有向传感器网络中，与具有确定工作方向的传感器相比，连续旋转的传感器有机会覆盖更多的目标。我们采用具有连续旋转能力的有向传感模型，以基于特定需求的目标节点为背景进行建模，研究有向传感器网络生命周期最大化问题，目的是通过对有向传感器的工作方向进行调度，使传感器网络能够满足所有目标的覆盖需求且网络的生命周期最大。连续旋转的有向传感器具有无数个工作方向，我们通过研究有向传感器和目标之间的覆盖关系,将连续的工作方向离散化，删除冗余的工作方向，从而把无限的工作方向有限化，实现了工作方向数目的有效降维。基于对有向传感器的特点和目标节点的需求分析，我们设计了解决该覆盖问题的贪婪算法，并得到该问题最优解的一个上界。最后通过仿真实验证实了算法的有效性。
　　3.摄像头传感器网络中全视角目标覆盖最大化问题:摄像头传感器网络是有向传感器网络中的一种，它在传感器工作方向的基础上，考虑了目标的面朝方向。全视角覆盖是指对于目标的任意面朝方向，总有摄像头传感器可以捕捉到它的正面信息。与一般意义的覆盖不同，全视角覆盖能够提高目标的覆盖质量，实现对目标的识别。然而由于传感器部署的随机性，实现所有目标的全视角覆盖往往需要部署高密度的摄像头传感器，这需要很高的成本。在此背景下，我们研究摄像头传感器网络中全视角目标覆盖最大化问题，为了提高摄像头传感器的利用率，我们采用具有P个工作方向的摄像头传感器，通过对传感器的工作方向进行调度，使监控区域内摄像头传感器全视角覆盖的目标数目最大。我们证明了该问题是NP-困难问题，并提出了一个基于管输舍入的（1-1/e）-近似算法以及一个有效的贪婪算法。最后通过仿真实验证实了这两种算法的有效性。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 目标覆盖问题的研究现状

1．2．1 全向感知的目标覆盖

1．2．2 定向感知的目标覆盖

1．2．3 视角感知的目标覆盖

1．3 研究内容与创新

1．3．1 主要内容

1．3．2 主要创新

1．4 论文的组织结构

1．5 本章小结

第二章 有向传感器网络覆盖概述

2．1 有向传感器网络概述

2．1．1 有向传感器

2．1．2 有向传感器网络的体系结构

2．1．3 有向传感器网络的主要特征

2．2 覆盖问题概述

2．2．1 覆盖问题的分类

2．2．2 覆盖控制算法的评价指标

2．3 本章小结

第三章 有向传感器网络中基于公平的目标覆盖最大化问题

3．1 研究背景

3．2 传感模型及问题定义

3．2．1 模型描述及问题定义

3．2．2 FTCM问题的挑战

3．3 算法

3．3．1 SSA算法

3．3．2 传感器和目标之间的覆盖关系

3．3．3 MCFTS算法

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 MSC问题的整数规划形式

4．2．4 MCS问题的挑战

4．3 算法

4．3．1 SDP算法

4．3．2 HMSC算法

4．4 实验分析

4．4．1 传感器数目对算法的影响

4．4．2 目标数目对算法的影响

4．4．3 传感半径对算法的影响

4．4．4 传感角度对算法的影响

4．4．5 目标覆盖需求对算法的影响

4．4．6 HMSC算法与MNLS-H-T算法比较

4．5 本章小结

第五章 摄像头传感器网络中全视角目标覆盖最大化问题

5．1 研究背景

5．2 传感模型及问题定义

5．2．1 模型描述及问题定义

5．2．2 MFTC问题的挑战

5．3 算法

5．3．1 FindBFCSs算法

5．3．2 ConstructNFCSs算法

5．3．3 PRA算法

5．3．4 HA算法

5．4 实验分析

5．4．1 摄像头传感器数目对算法的影响

5．4．2 目标数目对算法的影响

5．4．3 传感半径对算法的影响

5．4．4 PRA算法与HA算法比较

5．5 本章小结

第六章 总结与展望

6．1 研究工作总结

6．2 未来工作展望

参考文献

攻读学位期间已发表和待发表的学术论文

致谢