定向传感器网络中的覆盖问题研究.pdf

摘要 集成计算技术、微电子技术、无线通信技术和分布式信息处理技术的无线传 感器网络（WSN， wireless sensor networks）是当前信息技术的前沿之一， 也 是当今的研究热点,受到了各界的广泛关注。 网络覆盖是无线传感器网络研究的最重要和最基本问题之一，它是指通过网 络中传感器节点的空间位置分布实现对被监测区域或目标对象物理信息的感 知，从根本上反映了网络对物理世界的感知能力。由于传感器网络通常布置在 人们无法接近的恶劣甚至危险的远程环境中，传感器电池无法进行更换或者充 电。因此，设计有效的策略延长网络的生命周期成为无线传感器网络的核心问 题。近来，定向传感器方面的研究和开发取得了一定的成果。与全向传感器相 比，定向传感器有助于节约能量消耗，从而延长网络生命时间。本文研究了定 向传感器网络中的覆盖问题并设计了能有效利用能量从而最大化网络生命时间 的算法。文章着重考虑了如下两种情形的覆盖问题。第一，部分覆盖情形。在 许多应用中提供完全目标覆盖没有必要，也难以实现。当覆盖子集不能完全覆 盖所有目标时就会产生覆盖间隙。文章第二部分着重研究了定向传感器网络中 的最小化覆盖间隙和最大化网络生命时间问题。第二，目标具有不同覆盖质量 要求的覆盖情形。在网络某些实际应用情形中，不同的目标具有不同级别的重 要性。在这种情况下每个目标都具有与自身重要性相对应的覆盖质量要求。重 要的目标在网络覆盖中就需要更高的覆盖质量。即同时需要多个点来覆盖才能 达到它的覆盖质量。文章第三部分着重研究了定向传感器网络中基于目标覆盖 质量要求的覆盖问题。 本文的内容可分如下几个部分： 第一部分总结了与覆盖问题相关的研究工作和目前的研究现状。 第二部分研究了定向传感器网络中的最小化覆盖间隙和最大化网络生命时 间问题。最大化网络生命时间和最小化覆盖间隙是两个冲突的目标。为了在两 者之间做出权衡，文章研究了在生命时间受约束的情况下最小化覆盖间隙问题 （MCBLC ）和在覆盖间隙受约束的条件下最大化网络生命时间问题（MLCBC ）。 对于 MCBLC 问题，首先将它模型化为整数规划问题，并提出两个启发式算法 (MCBLC-G 和 MCBLC-G-1) 。基于 MCBLC-G (MCBLC-G-1)算法，利用二分搜 索技术得到解决 MLCBC 问题的算法。 第三部分研究了定向传感器网络中基于目标覆盖质量要求的覆盖问题。在该 问题中，每个目标具有不同的覆盖质量要求。因为在定向传感器网络延长网络 寿命时间仍然是一个重要的问题，文章提出了最大化网络寿命时间调度问题 （MNLS ）。为解决MNLS 问题，本文采取将传感器方向划分为一些可以相交的 方向子集合策略，其中每个方向子集合能提供所有目标的覆盖质量要求。文章 将 MNLS 问题表示为一个整数规划问题并证明MNLS 问题是一个NPC 问题， 即在多项式时间内不能得到最优解。文章提出了两个有效的启发式算法。 第四部分针对前两部分提出的算法，通过实验模拟加以比较，并对其性能进 行评估和分析。实验结果不仅验证了本文提出的算法的正确性和有效性，而且 为其应用于实际网络提供了重要的依据和指导。 最后对本文的研究内容进行总结，提出该研究工作的创新点和难点，指出其 在理论和实际应用中的价值与意义，并提出将来需要解决的其它问题。 关键词：无线传感器网络，能量有效，覆盖问题，定向天线，调度策略， 启发 式算法 Abstract Wireless sensor networks(WSN) ， which integrate computing technology, microelectronic technology, wireless communication technology and distributed information processing technology, is one of the current cutting edge of information technology and also have become todays research focus and received wide attention.