移动传感器扫描覆盖 摘要：关于传感器网络中的地址覆盖问题，已经做过很多尝试。他们通常归为两类，全覆盖和栅栏覆盖，统称为静态覆盖。在这篇论文中，我们研究一种新的覆盖方案，扫描覆盖，一种不同于先前的两种静态覆盖的方案。在扫描覆盖中，我们只需要定期的监视确定的POIs,因为在每个POI的覆盖是时变的，因此我们能够利用少量的移动传感器在大量的POI中实现扫描覆盖。我们研究扫描覆盖的定义和模型。给定一组POI和他们需要的扫描周期，我们证明，确定所需传感器的最少数量（最少扫描覆盖传感器问题）为NP-hard，并且它不能为近似为2 的一个因数。我们为确定近似比为3的最少扫描覆盖传感器问题提出了一个集中化算法。我们进一步描述问题的非定域性，并设计了一个分布式扫描算法DSWEEP,配合传感器尽最大努力提供效率。我们进行了广泛的模拟来研究所提算法的性能。我们的仿真结果表明DSWEEP在有效性和效率方面都优于随机计划。 程序代写源码：
索引词组：扫描覆盖，移动传感器，动态覆盖，DSWEEP。
1. 引言 无线传感器网络在环境监测应用中广泛研究。在这样的应用中，实现特定的覆盖要求是基本的。在传感器网络的两种主要覆盖情景，全覆盖和栅栏覆盖中，需要为不同的覆盖问题做大量的工作。在全覆盖[17], [21], [23], [25],传感器部署在区域上持续不断的监视整片区域。区域中的任何一点都必须确保被至少一个或K个传感器覆盖。一个全覆盖通常在用户需要完全监视整片环境时用到。在栅栏覆盖[5], [11], [20],传感器被部署成一个屏障来检测任何穿过指定带状区域的入侵者。传感器以覆盖穿越路径的方式来合作保卫栅栏覆盖。栅栏覆盖通常在防卫入侵者的防护装置中用到。 在以上两种覆盖情景的任何一种中，监控区域需要在所有的时间段内被覆盖，称作静态覆盖。相反，一些应用在时间维度上有更多的动态需求。在一个典型的巡逻检查应用中，我们只需要保证定期而不是持续的检测确定的兴趣点（POI），这就是扫描覆盖。扫描覆盖不同于静态覆盖，就扫描覆盖的意义上来说，在每个POI的覆盖上是时变的，只要覆盖周期是有保证的。因此直接应用在静态覆盖中的传统工作来扫描覆盖场景是不可行的，会遭遇低效率和不必要的额外开销。 扫描覆盖的概念最初来自于机器人的环境。在这项工作中，我们研究传感器网络中的扫描覆盖。由于不同的目标和不同的限制使得在机器人领域里提出的技术不适用于我们这项工作中研究的问题，我们提出了轻量级、完全分布式的传感器网络解决方案。 我们为传感器网络提出一种模型，其中每个POI在某个特定时刻都被一个传感器覆盖，举例来说当且仅当传感器位于POI的位置是。如果一个POI每隔t时间单元至少被覆盖一次就是一个t-sweep覆盖，并且t就是这个POI的扫描周期。不同的POI可以有不同的扫描周期。对于定期监控，我们可以利用少量的移动传感器节点来实现扫描覆盖大量的POI。如果部署静止传感器，将需要更多的传感器并且它们大多数时间并不需要工作，造成明显的传感器节点浪费。在这个情景中，我们假定所有的传感器都是移动的，因为情况包括静态和移动传感器，可以很容易减少到方案移动传感器节点在这些POI中做扫描覆盖而不是用静态传感器。 给出一组POI的扫描覆盖模式和它们的扫描周期，一个自然的问题是决定扫描覆盖所需要的最少传感器，我们定义为最少传感器扫描覆盖。不幸的是我们证明出这个最少传感器扫描覆盖问题是个NP-hard并且它不能近似于因数2，除非P=NP。甚至我们能否设计一个多项式算法来获得一个为常数的近似比例都成问题。我们进一步描述扫描覆盖问题的非定域性，例如，一个独立的移动传感器不能在附近用“是”或“否”来回答一组给定的POI是否全局t-sweep覆盖。因此，怎样设计一个健全的分布式算法来结合所有的传感器有效的实 图1 现扫描覆盖是非凡的。 我们首先锁定一个简单的最少传感器扫描覆盖问题，假定所有POI的扫描周期都是一样的。我们提出一个集中的扫描算法，CSWEEP，来调度这些传感器，在一个任何所需最少传感器数量为ξ>0，其近似比例为2+ξ。然后我们延伸到一半最小传感器覆盖扫描问题，并且为近似比例为3提出GSWEEP算法。无论CSWEEP还是GSWEEP，每个移动传感器的移动路径都是预定的以便保证覆盖。对于实用性和可扩展性，我们提出一种分布式扫描算法，DSWEEP，用来尽最大努力有效的结合传感器保证所需覆盖。在DSWEEP中，每个传感器依据其他传感器的轨迹实时的独立决定他的移动路径。因此，每个传感器管理一个扫描表用来存储扫描过的POI的ID和扫描时间。传感器通过流行性的交换传播他们的交换表到网络。一个过滤过的表交换机制被用来省略传播大量冗余的表项。我们的模拟表明，DSWEEP在效益和效率上都优于随机计划。 这篇论文的剩余部分安排如下：第2部分介绍这篇论文的背景和动机应用。第3部分讨论相关工作。第4部分介绍扫描覆盖的准备工作。我们同时证明最少传感器扫描覆盖问题的NP困难，并介绍集中式算法。第5部分，我们家少DSWEEP的设计，包括信息交换和本地决策过程。我们在第6部分评估性能，最后在第7部分总结工作。
2 背景和应用 人类在过去的几十年对地球的环境和气候变化有着持续递增的关注。特别是被称作地球之肺的森林，是在对抗全球变暖战役中的主要力量。有鉴于此，森林管理和监督成为当今的重要任务。目前，一个我们已经启动的项目就是GreenOrbs,一个森林中的可持续的大规模的无线传感器网络系统。GreenOrbs的目标是全年生态监测天目山的森林，收集各种可用数据，比如温度、湿度、照度和二氧化碳含量。所收集的信息可以用来支持如下各种林业应用：
2.1 林冠郁闭度估计 林冠郁闭定义为上方树冠垂直投影面积占林地面积的百分比。它是一种官方使用的显著的林业指标，但传统的方法技术测量精度低、成本高昂。基于照度传感器读数和蒙特卡洛理论，GreenOrbs实现对广袤森林精确和有效的林冠郁闭度估计。
2.2 生物多样性研究 传感器关于温度、湿度、光照及二氧化碳的读数，精确的表征了森林的小气候。这些数据量化了生物活性和多物种竞争，可以用来支持生物多样性研究。
2.3 碳固存 为了最大限度的利用森林碳固存，不同树种的碳固存容量需要被精确测量。这可以在3D森林空间中二氧化碳传感器实现。比较不同高度传感器的读数，一棵树的树荫吸收的二氧化碳数量就可以持续监测了。
2.4 火险警报 用森林中的传感器数据，也就是温度和湿度，GreenOrbs持续不断的监视环境，支持细粒度实时的火险预警。 GreenOrbs第一次部署在2008年7月进行。自那时起，GreenOrbs经历了大量不同地方，不同规模，不同时期的部署。最近的一次部署包括近330个节点，至今已经连续工作了近一年。图1a描绘了该系统在天目山的部署区域。图1b描绘了我们在林地部署的固定传感器节点。这些传感器节点一起合作工作，持续监测森林的关键参数。除了基本的监测需求，我们正在规划一个集成了固定传感器和其他普遍技术的框架，来使GreenOrbs系统更为普遍。 特别的，对于火险预警的应用，我们不仅仅使用固定的传感器节点。我们目前也计划雇佣数百名装备移动手持设备的护林员，让他们在森林中四处巡视。图1c描绘了他们目前正在使用的移动设备。这些设备可以提供护林员从GPS得来的位置信息并提供相互之间的长距离通信。这些护林员在监测火险预警的早期迹象方面高度专业。由于装备了移动设备，他们实际上也可以被当做移动传感器。森林中有些重要地点是严重或很有可能引发火险。让护林员定期的探访这些地方很明显可以早期监测任何可能的麻烦，保卫森林远离火灾。这实际上就是个扫描覆盖问题的实例。这样的应用驱动了我们的研究。
3 相关工作 覆盖问题已经成为无线传感器网络中的一个热点问题。在全覆盖问题上已经做过很多尝试，比如区域覆盖[29]和点覆盖[9]。已经有些工作用移动传感器协助混合网络架构[33],[36]中的静态覆盖。王等人调查移动传感器的优化移动来保证移动传感器网络和混合传感器网络[36]都是k覆盖。论文[33]的作者提出一个分布式重定位算法，让每个值需要当地信息就获得优化的重定位。他们探索移动传感器的潜力来延长网络的生命周期。也有很多研究者研究移动传感器网络的覆盖。霍华德等人[16]提出一个基于势场的算法，确保节点的初始配置迅速的传播到最大化的覆盖区域。王等人[34]描绘了基于虚拟力的传感器移动策略，来在传感器初始随机定位后强化网络覆盖。传感器节点依据虚拟力的计算来部署。他们还考虑了网络中的漏洞并移动传感器到预期的目标位置一边提高覆盖[35]。以上算法致力于在固定配置中传播传感器到整个区域来最大化覆盖区域。一个关于全覆盖问题的完整调查由Cardei和Wu提供。 Kumar等人广泛的研究研究了栅栏覆盖问题[5][11][20],其中传感器形成一个屏障阻止入侵者穿越一片稀疏的地带。文献[20]中的工作是第一个研究栅栏覆盖中理论基础的。一个本地化算法提供本地栅栏覆盖在文献[11]中提出。Balister等人[5]进一步得到可靠的密度估计来达到栅栏覆盖和薄带间的连通性。 现存的大部分工作都关注于传感器固定配置的静态覆盖。即使是移动传感器，他们也主要关注于通过其流动性达到一个优化的部署而不是探索动态覆盖。明显这些工作的结果和方法都不能直接应用于扫描交换网络场景。一项以前的工作[24]研究了移动传感器网络中覆盖的动态方面。这表明，当区域覆盖在任何给定时间实例需要保持不变，在时间周期中一个更大的区域将被覆盖。在固定传感器网络忠未能监测的目标现在将被移动中的传感器监测到。然而，它只关注给全部区域提供覆盖而不考虑扫描交换场景。 扫描覆盖的概念最初来自于机器人的环境[6][15]。其主要考虑覆盖频率的度量，例如，覆盖每个点的频率。机器人同等的或者随机的在场地内移动并在环境中部署通信坐标来标记先前访问过的区域。机器人接着通过这些坐标通信用他们的运动策略做出本地决定。这些机器人领域里提出的技术由于高度智能集成和昂贵的机器人硬件需求而无法直接应用到传感器网络。有些工作关注于基于多机器人的覆盖[7][12][14]。虽然在覆盖项目上目标相近，这些工作主要考虑用机器人在地域中来完成区域覆盖。基于多机器人覆盖的目标通常用多个机器人在同一时间详尽的探索目标区域。其提出的方法还未完全发表。他们中的一些人假定所有机器人间的两两通信总是可用的而没有任何物理限制。他们中一些人根据不同区域把机器人分成独立的两组，同组间的机器人共享所有的覆盖信息[19][22]。不同的目标和不同的限制使得这些工作不适用于这片文章中研究的问题。据我所知，这项工作是一个介绍传感器网络中扫描覆盖问题，建立了理论基础并提出了使用的协议。 在机器人技术社区中有些研究努力致力于处理机器人路径规划或运动规划问题，和本工作有一些相似[8][18][28][31]。其提出的加爵方案尝试最小化机器人从初始点到目标点的路径长度同时避免区域内的任何障碍。有些工作认为在多个机器人存在于同一场地中并且机器人的运动被仔细考虑以避免与另一个机器人碰撞的多机器人系统[27]。然而，这些工作的关注点与我们将要在这篇文章中处理的从本质上不一样。机器人路径规划的目标是在一片有障碍物的场地中引导机器人从出发点到目标点，而这项工作的目标是在一组POI中传递无线传感器是得这些POI的覆盖需求得到履行。机器人路径规划问题的主要研究挑战归于机器人如何找到优化的路径即绕过所有障碍的最短路径，而本文中的主要研究问题是找到移动传感器的优化方案使得少量的传感器节点足够给所有的POI提供扫描覆盖。在机器人路径规划中，地域内的全面知识通常马上呈现给决策者，而这篇论文中的移动传感器通过分布式的方式操作。移动传感器节点需要通过信息交换获得POI的即时扫描覆盖状态，而这些知识通常是不完整的。所有这些不同使得机器人路径规划中已存的解决方案很难适用于我们的问题。
4. 扫描覆盖问题 在这个部分，我们首先给出扫描覆盖问题的一些定义。我们决定支撑扫描覆盖所需最少传感器数量（扫描覆盖最少传感器问题）为NP难度。我们发现这个问题不能近似于因数2除非P=NP。我们接着为有不变近似比例的扫描覆盖最少传感器问题提出集中近似算法。在这个部分的最后，我们描述扫描覆盖问题的非定域性特性。
4.1 扫描覆盖 假定在一个区域中有n个移动传感器S={s
1，s
2，···，s
n}(随机或策略性的)用来检测网络H={h
1，h
2，···， h
m}中的m个点。 d
i,j 为POI h
i和h
j间的欧几里得距离。我们假定所有的移动传感器以相同的速度υ运动。在一个特定的时间实例中，一个POI被一个传感器覆盖，即当且仅当这个传感器坐落于这个POI的位置。我们假定所有的传感器都是运动的，这样同时包括固定传感器和移动传感器的情况可以轻易的减少成在这些POI中方案移动节点来扫描覆盖而没有固定传感器。 扫描覆盖和以往用户需要一直提供静态和持续覆盖的传统全覆盖或栅栏覆盖不一样。在扫描覆盖中我们仅需要POI节点在确定的时间周期内被覆盖至少一次，以便我们可以保证在确定的延迟约束内有事件探查。基于此，我们如下定义t扫描覆盖：
定义 1 （ t 扫描覆盖） .在覆盖方案F中一个POI被叫做t扫描覆盖当且仅当它在t个时间单元内被F方案的移动传感器覆盖至少一次 覆盖方案F是一种移动传感器移动在他们的强制移动速度情况下的方案。由于我们假定所以的移动传感器都以固定速度移动，覆盖方案F可以简化陈述为所有传感器的移动轨道，一个传感器对应一条轨道。如果POI是t扫描覆盖，时间周期t被称作POI的扫描周期。实践中，不同的POI可能有不同的扫描周期需求。我们假定POI h
i 每隔t
i时间单元需要被覆盖一次。在这个例子中，POI h
i 被说是t
i扫描覆盖。
定义 2 （全局扫描覆盖） . 在方案F中一组POI被称作全局扫描覆盖当且仅当在F中每个POI h
i是t
i扫描覆盖。 当所有的POI的t
i=t ，就简化成一个我们称作全局t扫描覆盖的问题。
4.2 问题难点 我们考虑的最基础问题是，给定一组POI U，移动速度为υ的移动传感器的最小数量，这样，有一个覆盖运动方案F能满足每个POI在强制的t
i扫描覆盖下所需的全局扫描覆盖。我们把这个问题表示为最少传感器扫描覆盖问题（U，t, υ）,t是一个表示POI覆盖需求的矢量。我们用定理1展示通过TSP约简最少传感器扫描覆盖问题是个NP难题。让OPT（U，t, υ）中以速度υ运行的移动传感器的数量最少需要让一组POI U以t-扫描覆盖覆盖。
定理 1. 给定一组 POI U 和他们的扫描覆盖时间周期需求 t ，和传感器的移动速度υ，决定所需的移动传感器最小数量，以便问题（ U ， t, υ）有一个有效的覆盖方案是一个 NP 难题。除非 P=NP ，否则没有一个多项式时间算法使得总能找到一个覆盖方案在最少传感器扫描覆盖问题（ U ， t, υ）中只用（ 2- ξ）· OPT （ U ， t, υ）个传感器。 证明 .为了证明最少传感器扫描覆盖问题的NP难度，我们约减最少传感器扫描覆盖问题的TSP问题如下： 对于TSP问题，我们在一个二维空间中给出一组m个点U={u
1，u
2，····，u
m}，TSP寻找最短的路径来遍历所有点并返回出发点。对应的决策问题TSP（U，L）询问是否有一个环用不超过L的长度连接所有m个点。给出一个决策问题TSP（U,L），我们相应的定义最少传感器覆盖扫描问题：这些POI就是那m个点U={u
1，u
2，····，u
m}，而各个POI的扫描周期t
i 就是L/υ, υ是移动传感器的移动速度。 显然地，如果给出的TSP问题（U,L）有解决方案，那么一个传感器就足够提供相应的最少传感器扫描覆盖问题中的L/υ扫描覆盖：访问虽有点的环路定义了一个移动方案F，这样在每个L/υ时间单元内所有点就将被这些传感器访问至少一次。换句话说，如果最少传感器扫描覆盖问题有只用仅仅一个传感器的解决方案，TSP的决策问题就有一个行得通的解决方案。注意到对于任何t=L/υ时间单元的间隔，在覆盖方案F下，每个点在这个时间间隔内都必须被传感器访问至少一次。这意味着方案F提供一条路线以致每个点被至少访问一次。显然，这条路线的总长度最多为L/υ·υ=L。 以上约简证明了最少传感器扫描覆盖问题是一个NP难题。我们接着演示这些问题在近似比≤2-ξ（常数ξ＞0）没有任何多项式时间算法，除非P=NP。为了反证，假定这样的多项式时间近似算法存在，标记为APPR。考虑以L为TSP最有路径长度的TSP（U,L）决定。然后，对应的最少传感器扫描覆盖仍然有只需一个传感器的最优方案。对于这个特定的最少传感器扫描覆盖问题，有APPR发现的传感器数量最多为（2-ξ）·1。注意被用到的传感器数量必须为整数。这意味着最少传感器扫描覆盖问题的最优方案为1，并且这个方案可以在多项式时间中计算。这表明原始的TSP问题有一个可行的解决方案。回想一下，那是一个NP难题去决定以L作为最优化TSP路径长度的TSP决定是否有一个可行的方案。这个证明就完成了。
4.3 CSWEEP 算法 对于最少传感器扫描覆盖问题，全局t扫描覆盖t
i=t是一个简单的实例。对于这样的实例，我们设计了集中扫描算法（CSWEEP），从TSP问题中的近似算法衍生出来的一种算法。 对于欧几里得TSP问题，有一个知名的多项式时间算法[4],PTAS,有最好的近似比1+ξ。我们从这个算法开始。首先，我们用给定的POI作为点创建一个加权的完全图，而连线的权重就为两个POI间的距离。我们把这张图输入给解决TSP问题的PTAS算法。然后，输出是对应TSP问题的一个次优路径。在这个TSP问题中每个POI在P上只出现一次。如图2a如果 L
0=υ·t/2小于P的长度，我们把路径P划分为长度为L
0等长的两部分。否则，一个传感器就够了。然后我们让每个传感器如果2b所示的在一个独立的路径部分来回的持续运动。因此，坐落在路径一部分的每个POI都将在每个2·L
0/υ=t的时间单元内被至少访问一次。事实上，每个传感器并不需要运动在路径线段两个自由端点间，以致POI的扫描周期更短。通过这种方式，每个POI都被t扫描覆盖而这组POI则是全局t扫描覆盖。因此所需移动传感器的总数量就是细分部分的数量。 在定理2，我们进一步演示CSWEEP有一个近似比2+ξ。
定理 2. 对于最少传感器扫描覆盖问题，对任意ξ >0 ， CSWEEP 算法的时间复杂度依据 1+ ξ的，该 CSWEEP 算法的近似比最多为 2+ ξ。 图2 图3 证明.首先，取最少传感器扫描覆盖中的POI作为TSP中的点，我们就有了对应的TSP问题。我们假定对于这个TSP问题的最优路径的长度是L。那么路径P的长度最多为L'=L·（1+ξ），由于PTAS有一个近似比例1+ξ，ξ是任意PTAS中用到的小正整数。由此，CSWEEP中的路径P就必须分为⌈L'/L⌉=⌈2L（1+ξ）/（υ·t）⌉份。如上所示，在CSWEEP中我们分配给每个移动传感器一份独立的路线。那么在CSWEEP中所需要的移动传感器数量就为N
cen=2L(1+ξ)/( υ·t)。第二步，我们假定最少传感器扫描覆盖问题的最优方案为N
opt。 换句话说，有个覆盖方案F，依据F，如果我们用N
opt个传感器以恒定速度υ运动，每个POI在在t个时间单元内至少被访问一次。由于L是相应TSP问题的最短路径的长度，我们得到以下不等式N
opt·υ·t≥L，变换为N
opt≥⌈L/(υ·t) ⌉。最终，CSWEEP的近似比例算出来为N
cen/N
opt=2+ξ。证明完成。
4.4 GSWEEP 算法 对于最少传感器扫描交换问题的一般情况，不同POI的扫描周期可能不同。因此，以上的近似值不能使用，所以我们设计了一个一般近似算法GSWEEP，用三步实现。
第 1 步 . 复制这些POI。对于每个POI h
i，我们计算它的监测频率f
i=1/t
i。如果f
i不是一个整数，我们通过向上取整把它转换为整数。接着，我们计算这些频率的最大公约数f=gcd(f
1,f
2,···,f
m)。对于每个POI h
i ，我们为其创建k(i)=f
i/f－1个虚拟POI。标记为H
i={h
i1,h
i2,···,h
i k(i)}。如图3a所示，两个虚拟POI，h
11和h
12，由h
1衍生。一个虚拟POI由h
2衍生标记为h
21。对于所有的POI和他们的虚拟POI，我们创建一个带权完全图。首先，h
i和h
j之间的连接权重设为和他们之间的距离d
i,j相同。所有h
i中的圈子和H
i中的POI间的链接权重设为无穷大∞，表明这些权重为∞的连接实际上不存在于下面的算法中。鉴于H
i的成员和H
j的成员及hj之间的链接权重只是从h
i和h
j之间的连接权重复制过来。如图3b中所描绘，{h
1，h
11，h
12}中的相互连接权重设为∞，h
2和h
21之间的连接权重也一样。余下的所有链接权重都设为5，从h
1和h
2之间的链接权重复制过来。在接下来的步骤中，我们将虚拟POI和POI看做一样。
第 2 步 .找到一个TSP路径P。由于上面的权重图不是一个几何图，我们不能用PTAS中的近似算法来处理这张图中的TSP问题，但是我们可以用到Christofides算法[13]的帮助,我们可以为这个问题找到一个近似比为1.5的路径P，其时间复杂度为O（m
3）,其中m为POI的数量。注意到路径P只访问每个POI一次，并且POI h
i在路劲P上有额外的k(i)个复制。
第 3 步 .分割路径P。和CSWEEP相似，我们路径P分割成许多相等的部分，其长度为L
0=υ/2f。接着，我们分配给每个部分一个来回运动的传感器。结果是，我们可以保证路径上的所有的POI包括虚拟POI在1/f个时间段远内将至少被访问一次。由于POI h
i在路劲P上有额外的k(i)个复制，那么h
i在1/f个时间单元内将至少被访问k(i)+1= f
i/f次。因此，在t
i个时间单元内，h
i至少被访问f
i/f·t
i·f=1次。所以，GSWEEP能证明所需的扫描交换。
定理 3.GSWEEP算法有一个最多为3的近似比。
证明 .如GSWEEP算法中所展示的，在我们建立的完全图中的相应TSP问题，Christofides算法有一个近似比1.5。这表明如果TSP问题的优化长度为L，那么由Christofides算法导出的路径P有一个长度L'=3L/2。那么，GSWEEP所需的传感器数量是N
gs= L'/ L
0=3L·f/υ。同时，最少传感器扫描覆盖问题的优化方案为N
opt≥L/(υ·1/f)=L·f/υ。由此，GSWEEP的近似比为N
gs/N
opt ≤3。证明完成。
4.5 扫描覆盖的非定域性 在全覆盖中，已经证明，传感器可以在本地确定一片给定区域是否被完全k覆盖[17]。如果传感器感应圆盘边界上任意一点被少于k个传感器覆盖，那么这个传感器就能本地断定这片区域没有被完全k覆盖。 然而，在扫描覆盖情况中，一个独立的移动传感器对一组给定的POI是否全局扫描覆盖，无法本地判断“是”或“否”。我们可以解释如下。 在很多应用中，POI的数量巨大而且他们之间的距离很长。一个传感器不足以满足各种应用需求，所以两个或更多的传感器是必需的。在这样一个传感器网络中，如果没有像GSWEEP这样的中央确定性方案支撑，一个传感器s
i无法知晓所有其他传感器的全部移动路径。那么，s
i无法决定在它自己每个扫描周期中未被它自己监测到的POI，在相应时间周期中是否已经被其他传感器访问了。因此，一个传感器无法本地决定是否所有的POI被t扫描覆盖。这样，t扫描覆盖无法被任何没有全局信息的确定方案F所保证。换句话说，没有分布式本地算法能保证所需的t扫描覆盖。 不幸的是，集中化全局算法对大规模网络不具扩展性。在实践中，被扫描覆盖的POI可能随时间改变。此外，移动传感器的移动速度可能不同，而且移动传感器在旅途中甚至可能失败。因此，CSWEEP和GSWEEP在实际情况中都不具可扩展性和适应性。为了处理这些问题，我们提出一个分布式扫描覆盖算法DSWEEP,只用本地信息让移动传感器尽最大的努力来提供适应性和可靠的覆盖。
6. 性能评估 我们在3D机器人模拟器测量工具[3]上进行模拟实验来测试我们算法的性能。我们将在这一部分呈现我们的模拟结果。
6.1 模拟计划 对于模拟，我们在测量工具[3]上执行一个扫描覆盖实例。数以百计的POI随机的部署在一个10米乘10米的的正方形场地上。传感器的固定通信范围设为2米。移动传感器的缺省移动速率为0.3m/s。由于所提出的扫描覆盖完全是一个全新覆盖方案，传感器覆盖中已经发布的算法不能直接应用到这个方案中。因此，我们为我们在第5部分中描述的DSWEEP算法提出一个简单的随机方案。在这个随机方案中，每个移动传感器提前知道了所有POI的位置。当某个传感器到达了一个POI，他独立的选择一个随机的相邻POI作为他的下一个目的地。为了简化，我们在下文中将这个随机方案命名为RAND。
6.2 覆盖效率 我们在扫描覆盖的两种不同需求下比较DSWEEP和RAND的覆盖效率。一种是所有的POI有同样的扫描周期需求。另一种是不同的POI有不同的周期。
6.2.1 所有 POI 有相同的扫描周期需求 在这个部分中，我们为所有的POI设定相同的扫描周期。每个独立POI的实际扫描周期是反应覆盖效率的标准。我们首先评估所有POI平均扫描周期的累积分布函数。我们同时测试所有POI的平均扫描周期和标准方差。我们设定传感器的数量为n=10,而移动传感器的移 图7 图8 动速度为υ=0.3m/s。然后，对于不同的扫描周期需求t=80；120，和160s，分别作以下实验。我们运行DSWEEP和RAND各100000s，并计算每个POI的实际扫描周期。 图7说明POI的扫描周期如何不同于所需扫描周期。图７a展示了当所需扫描周期为t=80s时，独立POI不同扫描周期的CDF(累积分布函数)。很明显，DSWEEP显著优于RAND。首先，平均周期小于所需周期80s的POI部分，DSWEEP的结果为78%远远高于RAND的51%。这说明，在DSWEEP中更多的POI达到了他们的扫描周期需求。此外，DSWEEP的CDF曲线比RAND更快的打到了100%，证明那些不能满足所需扫描周期的POI，不会延迟太久。图7b展示了所需扫描周期为t=120s的模拟。与前面的情况相似，首先我们可以发现DSWEEP中的集中于所需扫描周期t=120s附近，而在RAND中则沿着整个跨度分布。因此，在DSWEEP中更多的POI满足需求，而对于超过了所需周期的POI也不会延迟太久。图7c中将所需扫描周期提高到160s并显示了相似的结果。以上结果的主要原因在于，在RAND方案中，移动传感器没有协调合作，因此导致在很长时间内，某些POI可能被频繁访问而其他POI则很少被访问的事实。然而，在DSWEP中如果一个POI h
i最近被一个传感器监测过了，传感器会禅师通过传染交换发送出这个信息。此后，其他得到这个信息的传感器不会扫描覆盖它直到POI的下一个截止期限到来。 我们进一步测量所有POI的平均周期和标准方差。我们计算所有POI的平均周期来看看全局效益，计算方差来看看每个独立POI的波动。图8中，我们做三组实验来评估RAND和DSWEEP的性能。 图8a使移动传感器的数量变化并绘制了所有POI的全局平均扫描周期。移动速度为υ=0.3m/s ，所需扫描周期为t=80s。如预期一样，随着移动传感器数量的增增，DSWEEP和RAND的全局扫描周期都呈递减。DSWEEP的曲线比RAND的更低并更快的递减到80s， 图9 说明了DSWEEP能保证用更少的传感器让大部分POI达到他们的扫描周期。DSWEEP的标准方差总是比RAND的更小。一个小的方差对于证明多数POI的平均扫描周期接近全局平均差异非常重要，因此能满足需求。图8b让传感器的速率变化并绘制了所有POI 的全局平均扫描周期。移动传感器的个数为n=10，扫描周期为t=80s。结果与图8a中相似。随着移动传感器速率的递增，DSWEEP和RAND的全局平均扫描周期都呈递减。如预期一样，DSWEEP在小平均扫描周期和小方差方面的表现都优于RAND。图8c让所需扫描周期变化。移动传感器的数量为n=10,移动速率为υ=0.3m/s。如图所示，显然，RAND和DSWEEP之间的效率不同。RAND在实际需求中平均扫哦么周期变化的很小，而DSWEEP的平均扫描周期非常灵敏的满足不同的需求。同时，方差下降的非常快，保证了大部分POI的独立性 能非常接近于全局性能。因此，当全局性能足够时，大部分POI能满足所需扫描周期。 通过以上各种模拟，通过与随机算法比较，DSWEEP用很少的传感器在更低的移动速率提供了所需的扫描覆盖。
6.2.2 不同扫描周期的 POI 当POI有不同的重要性，他们所需的扫描周期可能不同。在这组实验中，我们把POI分成3种类型，第一种扫描周期为t=80s，第二种扫描周期为t=120s，第三种扫描周期为t=160s。每个类型都有相等数量的POI。然后，不同数量的传感器和不同速率被测试来评估它们对POI的独立平均周期的影响。我们把满足了所需扫描周期的POI称为可信POI。图9分别展示了三种类型POI的可信部分。 图9a和图9b通过不同数量的移动传感器比较了DSWEEEP和RAND。移动传感器的移 图10 动速率被设为υ=0.3m/s。显然，DSWEEP有更多数量的可信POI,表现优于RAND。而且，在DSWEEP中，所有三种类型的POI有类似的小部分可靠POI，说明DSWEEP适用于混合扫描周期需求。然而，在RAND中，三种不同类型POI和彼此差别很大。有着宽松需求(t=160s)的POI的有大量的可信POI，而有着严格需求(t=80s)的POI只有少量的可信POI。相似的结 果在图9c和9d中也有显示，其中我们让速率和传感器变化。因此，更具以上结果，DWSWEEP显示出更适用和通用于混合扫描覆盖需求。
6.3 所需传感器数量 我们在这小节研究最少传感器扫描覆盖问题的效率。最少传感器扫描覆盖问题的目标是用最少数量的传感器保证所需扫描覆盖。如上面提到的，没有分布式本地算法保证每个POI满足扫描周期需求，即使是DSWEEP。因此，我们测试实际的平均扫描周期并把它与扫描周期需求相比。如果想对误差小于10%，我们认为移动传感器符合提供所需扫描周期。图10a展示了在所有POI有相同的扫描周期需求t=80s的情况下，RAND,DSWEEEP和CSWEEP所需的移动传感器数量。图10b展示了在3种POI有不同扫描周期需求t=80，120和160s的情况下,RAND,DSWEEP和GSWEEP所需的移动传感器数量。随着移动传感器速率的递增，所有算法需要更少的传感器。全局集中化算法CSEEEP和GSWEEP是设低界限的SWSEEP，然而，DSWEEP总是优于RAND. 所有上述实验表明所提出的分布式算法DSWEEP无论在效率还是有效性上都优于方案，然而，所提出的集中化算法在所需传感器数量上优于DSWEEP。 7 总结 用移动传感器巡检在多种有特定延迟变节的环境监测应用中都是有效的方案。这种应用中，我们定义扫描覆盖的概念来塑造在周期性监测一组POI的需求。我们对给定的扫毛覆盖需求，讨论决定所需传感器最少数量问题。我们证明了这个最骚传感器扫描覆盖问题是一个NP难题，并且它不可能近似于因数2。于是我们提出了一个普遍的集中化算法GSWEEP，其对于这个问题有一个恒定的近似比3.我们进一步设计了一个分布式扫描算法DSWEEP，它能协调传感器尽最大努力对给定的POI和他们的扫描周期需求提供有效的扫描覆盖。模拟结果显示DSWEEP无论在有效性还是效率方面都优于直截了当的随机方案。 扫描覆盖对于传感器网络监察纯粹是个新的概念。在这篇论文中仍然有很多问题没有讨论。这个问题的一个重要延伸是对于给定的区域而不是一组离散的POI，怎样决定扫描覆盖的标准并研究适用性？怎样对一个有节的分布式算法工作并在扫描覆盖的一个实际协议中减少通信代价同样是个挑战。在我们未来的工作中，我们打算研究这些问题并得到更多有用的结果。
感谢 这项工作的部分支持来自于，新加坡的南洋科技大学的SUG COE_SUG/RSS_20Aug2010_13/14，美国国家科学基金会授权CNS-0832120 和CNS-1035894，中国国家自然科学基金会批准60828003和60903224，一个浙江省重点创新研究团队的项目，一个浙江省海外高级人才的一个项目(100个天才项目)，和清华信息科学技术国家实验室(TNList).
引用文献 [1] “GreenOrbs,” http://www.greenorbs.org, 2011. [2] “Robocar,” http://www.esi.ust.hk/projects.html, 2011. [3] “Simbad,” http://simbad.sourceforge.net, 2011. [4] S. Arora, “Polynomial-Time Approximation Schemes for Eucli- dean TSP and Other Geometric Problems,” Proc. IEEE 37th Ann. Symp. Foundations of Computer Science (FOCS ’96), 1996. [5] P. Balister, B. Bollobas, A. Sarkar, and S. Kumar, “Reliable Density Estimates for Achieving Coverage and Connectivity in Thin Strips of Finite Length,” Proc. ACM MobiCom, 2007. [6] M.A. Batalin and G.S. Sukhatme, “Multi-Robot Dynamic Coverage of a Planar Bounded Environment,” Proc. IEEE/RSJ Int’l Conf. Intelligent Robots and Systems, 2002. [7] M.A. Batalin and G.S. Sukhatme, “Multi-Robot Dynamic Coverage of a Planar Bounded Environment,” Univ. of Southern California, CRES-03-011, 2003. [8] M. Bennewitz, W. Burgard, and S. Thrun, “Optimizing Schedules for Prioritized Path Planning of Multi-Robot Systems,” Proc. IEEE Int’l Conf. Robotics and Automation (ICRA ’01), 2001. [9] M. Cardei and D.-Z. Du, “Improving Wireless Sensor Network Lifetime through Power Aware Organization,” ACM Wireless Networks, vol. 11, pp. 333-340, 2005. [10] M. Cardei and J. Wu, “Energy-Efficient Coverage Problems in Wireless Ad Hoc Sensor Networks,” J. Computer Comm. Sensor Networks, vol. 29, pp. 413-420, 2005. [11] A. Chen, S. Kumar, and T.H. Lai, “Designing Localized Algorithms for Barrier Coverage,” Proc. ACM MobiCom, 2007. [12] H. Choset, “Coverage for Robotics—A Survey of Recent Results,” Annals of Math. and Artificial Intelligence, vol. 31, pp. 113-126, 2001. [13] N. Christofides, “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem,” Technical Report 388, Carnegie MellonUniv., 1976. [14] P. Fazli, “On Multi-Robot Area Coverage,” Proc. Ninth Int’l Conf. Autonomous Agents and Multiagent Systems (AAMAS ’10), 2010. [15] D.W. Gage, “Command Control for Many-Robot Systems,” Proc. AUVS Technical Symp., 1992. [16] A. Howard, M.J. Mataric, and G.S. Sukhatme, “Mobile Sensor Network Deployment Using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem,” Proc. Int’l Conf. Distributed Autonomous Robotic Systems 5 (DARS ’02), 2002 [17] C.F. Huang and Y.C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” Proc. Second ACM Int’l Conf. Wireless Sensor Networks and Applications (WSNA ’03), 2003. [18] F.A. Kolushev and A.A. Bogdanov, “Multi-Agent Optimal Path Planning for Mobile Robots in Environment with Obstacles,” Proc. Third Int’l Andrei Ershov Memorial Conf. Perspectives of System Informatics (PSI ’99), 1999. [19] C. Kong, A. New, and I. Rekleitis, “Distributed Coverage with Multi-Robot System,” Proc. IEEE Int’l Conf. Robotics and Automation (ICRA ’06), 2006. [20] S. Kumar, T.H. Lai, and A. Arora, “Barrier Coverage withWireless Sensors,” Proc. ACM MobiCom, 2005. [21] S. Kumar, T.H. Lai, and J. Balogh, “On K-Coverage in a Mostly Sleeping Sensor Network,” Proc. ACM MobiCom, 2004. [22] D. Latimer, S. Srinivasa, V. Shue, S. Sonne, and H. Choset, “Towards Sensor Based Coverage with Robot Teams,” Proc. IEEE Int’l Conf. Robotics and Automation (ICRA ’02), 2002. [23] L. Lin and H. Lee, “Distributed Algorithms for Dynamic Coverage in Sensor Networks,” Proc. 26th Ann. ACM Symp. Principles of Distributed Computing (PODC ’07), 2007. [24] B. Liu, P. Brass, and O. Dousse, “Mobility Improves Coverages of Sensor Networks,” Proc. ACM MobiHoc, 2005. [25] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava, “Coverage Problems in Wireless Ad-Hoc Sensor Networks,” Proc. IEEE INFOCOM, 2001. [26] L. Mo, Y. He, Y. Liu, J. Zhao, S. Tang, X. Li, and G. Dai, “Canopy Closure Estimates with GreenOrbs: Sustainable Sensing in the Forest,” Proc. Seventh ACM Conf. Embedded Networked Sensor Systems (SenSys ’09), 2009. [27] M. Ryan, “Graph Decomposition for Efficient Multi-Robot Path Planning,” Proc. 20th Int’l Joint Conf. Artifical Intelligence (IJCAI ’07), 2007. [28] M.R.K. Ryan, “Exploiting Subgraph Structure in Multi-Robot Path Planning,” J. Artificial Intelligence Research, vol. 31, pp. 497-542, 2008. [29] S. Slijepcevic and M. Potkonjak, “Power Efficient Organization of Wireless Sensor Networks,” Proc. IEEE Int’l Conf. Comm. (ICC ’01), 2001. [30] B. Sundararaman, U. Buy, and A.D. Kshemkalyani, “Clock Synchronization in Wireless Sensor Networks: A Survey,” Ad- Hoc Networks, vol. 3, pp. 281-323, May 2005. [31] P. Svestka and M.H. Overmars, “Coordinated Path Planning for Multiple Robots,” Robotics and Autonomous Systems, vol. 23, pp. 125-152, 1998. [32] A. Vahdat and D. Becker, “Epidemic Routing for Partially Connected Ad hoc Networks,” Technical Report CS-200006, Duke Univ., 2000. [33] D. Wang, J. Liu, and Q. Zhang, “Field Coverage Using a Hybrid Network of Static and Mobile Sensors,” Proc. IEEE Int’l Workshop Quality of Service (IWQoS ’07), 2007. [34] G. Wang, G. Cao, and T.L. Porta, “Sensor Deployment and Target Localization Based on Virtual Forces,” Proc. IEEE INFOCOM, 2003. [35] G. Wang, G. Cao, and T.L. Porta, “Movement-Assisted Sensor Deployment,” Proc. IEEE INFOCOM, 2004. [36] W. Wang, V. Srinivasan, and K.C. Chua, “Trade-Offs between Mobility and Density for Coverage in Wireless Sensor Networks,” Proc. ACM MobiCom, 2007.专业程序代写