摘要: 近几年以来，由于无线传感器网络潜在的广泛应用，无线传感器网络逐渐成为计算机研究领域的一个焦点。同时，无线传感器网络具有的特性给研究提出了许多挑战性的问题，如覆盖、定位、跟踪和布置等。Meguerdichian等首次提出了传感网络中的最优覆盖和最坏覆盖问题。本文主要提出了一个局部化的算法来解决无线传感网络最坏覆盖问题，并将扩展的算法应用到最小暴露问题(Minimal Exposure Problem)。Meguerdichian最先定义了最坏覆盖问题，并提出了基于计算几何的集中式算法解决该问题。不久，他又提出了一个所谓的局部化算法解决该问题，但是因为他假定每个结点已知自身的Delaunary邻居，而这种假定有时是不现实的，所以他的算法最多只是一个伪局部化的算法。本文是首次提出了完全局部化的算法来解决最坏覆盖问题，并对算法的正确性给出了形式化证明。传感网络中，每个结点都具有感应能力，根据已有的研究可知，结点的感应能力随着与结点的距离增加而相应地减小。如果点p处于传感结点s的感应区域内，那么结点s在p点上的感应能力表示为 ，其中 表示结点s与点p的距离， 和 都是常量。当点p与传感结点s的距离超过结点的感应距离时，其感应能力为0。平面内任意一点p，其最近可观察度(closest observability)定义为最近的传感器结点在该点上的感应能力。而一条路径的可观察度定义为路径上所有点的最近可观察度的最大值。因此最坏覆盖问题就是为给定的起点和终点构造具有最小可观察度的一条路径，而最小暴露问题则是固定两点间所有点的最近可观察度之和最小的路径。本文主要提出了一个完全局部化的算法来解决最坏覆盖问题。其主要思想如下：第1步：对于起点s和终点t，首先为它们分别选择最近的传感器结点 和 ；第2步：每个结点u收集单跳邻居的信息，并根据这些信息构造自身的局部Voronoi区域，记为 ，然后计算该区域与自身的管理区域的交集，该交集就是自身的异常Voronoi区域，异常Voronoi图上的顶点和边简称为顶点和边；第3步：结点 和 根据顶点选择算法(Vertex Selection Algorithm)为s和t选择合适的顶点 和 ；第四步：为构造的每条边赋权值（权值定义见文章）；第五步：运行分布式Bellman-Ford算法搜索 与 之间的最短路径，一条路径的权值定义为该路径上权最大的那条边上的权值； 与 间的最短路径是这两点间所有路径之中，权值最小的路径；第6步：连接 、 和 ，便得到了起点和终点之间的路径。本文的第四节给出了算法的正确性证明，即算法构造的路径为最坏覆盖路径。而对于最小暴露问题，其算法与上述算法类似。主要区别是边上的权值定义不同；路径的权值定义也不同，这里的路径权值定义为该路径上所有边的权值之和。为了减少最小暴露问题求解过程中的搜索空间，我们设定一个阈值。当路径的权值超过该阈值时，便舍弃此路径，因此减少能量消耗。