自建网站 备案,友情链接查询工具,如何创造免费网站,抖音特效开放平台官网移动传感器扫描覆盖摘要#xff1a;关于传感器网络中的地址覆盖问题#xff0c;已经做过很多尝试。他们通常归为两类#xff0c;全覆盖和栅栏覆盖#xff0c;统称为静态覆盖。在这篇论文中#xff0c;我们研究一种新的覆盖方案#xff0c;扫描覆盖#xff0c;一种不同于… 移动传感器扫描覆盖 摘要关于传感器网络中的地址覆盖问题已经做过很多尝试。他们通常归为两类全覆盖和栅栏覆盖统称为静态覆盖。在这篇论文中我们研究一种新的覆盖方案扫描覆盖一种不同于先前的两种静态覆盖的方案。在扫描覆盖中我们只需要定期的监视确定的POIs,因为在每个POI的覆盖是时变的因此我们能够利用少量的移动传感器在大量的POI中实现扫描覆盖。我们研究扫描覆盖的定义和模型。给定一组POI和他们需要的扫描周期我们证明确定所需传感器的最少数量最少扫描覆盖传感器问题为NP-hard并且它不能为近似为2 的一个因数。我们为确定近似比为3的最少扫描覆盖传感器问题提出了一个集中化算法。我们进一步描述问题的非定域性并设计了一个分布式扫描算法DSWEEP,配合传感器尽最大努力提供效率。我们进行了广泛的模拟来研究所提算法的性能。我们的仿真结果表明DSWEEP在有效性和效率方面都优于随机计划。 程序代写源码http://www.xmsydw.com 索引词组扫描覆盖移动传感器动态覆盖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除非PNP。甚至我们能否设计一个多项式算法来获得一个为常数的近似比例都成问题。我们进一步描述扫描覆盖问题的非定域性例如一个独立的移动传感器不能在附近用“是”或“否”来回答一组给定的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除非PNP。我们接着为有不变近似比例的扫描覆盖最少传感器问题提出集中近似算法。在这个部分的最后我们描述扫描覆盖问题的非定域性特性。 4.1扫描覆盖 假定在一个区域中有n个移动传感器S{s1s2···sn}(随机或策略性的)用来检测网络H{h1h 2··· h m}中的m个点。 di,j 为POI hi和hj间的欧几里得距离。我们假定所有的移动传感器以相同的速度υ运动。在一个特定的时间实例中一个POI被一个传感器覆盖即当且仅当这个传感器坐落于这个POI的位置。我们假定所有的传感器都是运动的这样同时包括固定传感器和移动传感器的情况可以轻易的减少成在这些POI中方案移动节点来扫描覆盖而没有固定传感器。 扫描覆盖和以往用户需要一直提供静态和持续覆盖的传统全覆盖或栅栏覆盖不一样。在扫描覆盖中我们仅需要POI节点在确定的时间周期内被覆盖至少一次以便我们可以保证在确定的延迟约束内有事件探查。基于此我们如下定义t扫描覆盖 定义1 t扫描覆盖.在覆盖方案F中一个POI被叫做t扫描覆盖当且仅当它在t个时间单元内被F方案的移动传感器覆盖至少一次 覆盖方案F是一种移动传感器移动在他们的强制移动速度情况下的方案。由于我们假定所以的移动传感器都以固定速度移动覆盖方案F可以简化陈述为所有传感器的移动轨道一个传感器对应一条轨道。如果POI是t扫描覆盖时间周期t被称作POI的扫描周期。实践中不同的POI可能有不同的扫描周期需求。我们假定POI hi 每隔ti时间单元需要被覆盖一次。在这个例子中POI hi 被说是ti扫描覆盖。 定义2全局扫描覆盖. 在方案F中一组POI被称作全局扫描覆盖当且仅当在F中每个POI hi是ti扫描覆盖。 当所有的POI的tit 就简化成一个我们称作全局t扫描覆盖的问题。 4.2 问题难点 我们考虑的最基础问题是给定一组POI U移动速度为υ的移动传感器的最小数量这样有一个覆盖运动方案F能满足每个POI在强制的ti扫描覆盖下所需的全局扫描覆盖。我们把这个问题表示为最少传感器扫描覆盖问题Ut, υ,t是一个表示POI覆盖需求的矢量。我们用定理1展示通过TSP约简最少传感器扫描覆盖问题是个NP难题。让OPTUt, υ中以速度υ运行的移动传感器的数量最少需要让一组POI U以t-扫描覆盖覆盖。 定理1.给定一组POI U和他们的扫描覆盖时间周期需求t和传感器的移动速度υ决定所需的移动传感器最小数量以便问题Ut, υ有一个有效的覆盖方案是一个NP难题。除非PNP否则没有一个多项式时间算法使得总能找到一个覆盖方案在最少传感器扫描覆盖问题Ut, υ中只用2-ξ·OPTUt, υ个传感器。 证明.为了证明最少传感器扫描覆盖问题的NP难度我们约减最少传感器扫描覆盖问题的TSP问题如下 对于TSP问题我们在一个二维空间中给出一组m个点U{u1u2····um}TSP寻找最短的路径来遍历所有点并返回出发点。对应的决策问题TSPUL询问是否有一个环用不超过L的长度连接所有m个点。给出一个决策问题TSPU,L我们相应的定义最少传感器覆盖扫描问题这些POI就是那m个点U{u1u2····um}而各个POI的扫描周期ti 就是L/υ, υ是移动传感器的移动速度。 显然地如果给出的TSP问题U,L有解决方案那么一个传感器就足够提供相应的最少传感器扫描覆盖问题中的L/υ扫描覆盖访问虽有点的环路定义了一个移动方案F这样在每个L/υ时间单元内所有点就将被这些传感器访问至少一次。换句话说如果最少传感器扫描覆盖问题有只用仅仅一个传感器的解决方案TSP的决策问题就有一个行得通的解决方案。注意到对于任何tL/υ时间单元的间隔在覆盖方案F下每个点在这个时间间隔内都必须被传感器访问至少一次。这意味着方案F提供一条路线以致每个点被至少访问一次。显然这条路线的总长度最多为L/υ·υL。 以上约简证明了最少传感器扫描覆盖问题是一个NP难题。我们接着演示这些问题在近似比≤2-ξ常数ξ0没有任何多项式时间算法除非PNP。为了反证假定这样的多项式时间近似算法存在标记为APPR。考虑以L为TSP最有路径长度的TSPU,L决定。然后对应的最少传感器扫描覆盖仍然有只需一个传感器的最优方案。对于这个特定的最少传感器扫描覆盖问题有APPR发现的传感器数量最多为2-ξ·1。注意被用到的传感器数量必须为整数。这意味着最少传感器扫描覆盖问题的最优方案为1并且这个方案可以在多项式时间中计算。这表明原始的TSP问题有一个可行的解决方案。回想一下那是一个NP难题去决定以L作为最优化TSP路径长度的TSP决定是否有一个可行的方案。这个证明就完成了。 4.3 CSWEEP 算法 对于最少传感器扫描覆盖问题全局t扫描覆盖tit是一个简单的实例。对于这样的实例我们设计了集中扫描算法CSWEEP从TSP问题中的近似算法衍生出来的一种算法。 对于欧几里得TSP问题有一个知名的多项式时间算法[4],PTAS,有最好的近似比1ξ。我们从这个算法开始。首先我们用给定的POI作为点创建一个加权的完全图而连线的权重就为两个POI间的距离。我们把这张图输入给解决TSP问题的PTAS算法。然后输出是对应TSP问题的一个次优路径。在这个TSP问题中每个POI在P上只出现一次。如图2a如果 L0υ·t/2小于P的长度我们把路径P划分为长度为L0等长的两部分。否则一个传感器就够了。然后我们让每个传感器如果2b所示的在一个独立的路径部分来回的持续运动。因此坐落在路径一部分的每个POI都将在每个2·L0/υt的时间单元内被至少访问一次。事实上每个传感器并不需要运动在路径线段两个自由端点间以致POI的扫描周期更短。通过这种方式每个POI都被t扫描覆盖而这组POI则是全局t扫描覆盖。因此所需移动传感器的总数量就是细分部分的数量。 在定理2我们进一步演示CSWEEP有一个近似比2ξ。 定理2. 对于最少传感器扫描覆盖问题对任意ξ0 CSWEEP算法的时间复杂度依据1ξ的该CSWEEP算法的近似比最多为2ξ。 图2 图3 证明.首先取最少传感器扫描覆盖中的POI作为TSP中的点我们就有了对应的TSP问题。我们假定对于这个TSP问题的最优路径的长度是L。那么路径P的长度最多为LL·1ξ由于PTAS有一个近似比例1ξξ是任意PTAS中用到的小正整数。由此CSWEEP中的路径P就必须分为⌈L/L⌉⌈2L1ξ/υ·t⌉份。如上所示在CSWEEP中我们分配给每个移动传感器一份独立的路线。那么在CSWEEP中所需要的移动传感器数量就为Ncen2L(1ξ)/( υ·t)。第二步我们假定最少传感器扫描覆盖问题的最优方案为Nopt。 换句话说有个覆盖方案F依据F如果我们用Nopt个传感器以恒定速度υ运动每个POI在在t个时间单元内至少被访问一次。由于L是相应TSP问题的最短路径的长度我们得到以下不等式Nopt·υ·t≥L变换为Nopt≥⌈L/(υ·t) ⌉。最终CSWEEP的近似比例算出来为Ncen/Nopt2ξ。证明完成。 4.4 GSWEEP算法 对于最少传感器扫描交换问题的一般情况不同POI的扫描周期可能不同。因此以上的近似值不能使用所以我们设计了一个一般近似算法GSWEEP用三步实现。 第1步. 复制这些POI。对于每个POI hi我们计算它的监测频率fi1/ti。如果fi不是一个整数我们通过向上取整把它转换为整数。接着我们计算这些频率的最大公约数fgcd(f1,f2,···,fm)。对于每个POI hi我们为其创建k(i)fi/f1个虚拟POI。标记为Hi{hi1,hi2,···,hi k(i)}。如图3a所示两个虚拟POIh11和h12由h1衍生。一个虚拟POI由h2衍生标记为h21。对于所有的POI和他们的虚拟POI我们创建一个带权完全图。首先hi和hj之间的连接权重设为和他们之间的距离di,j相同。所有hi中的圈子和Hi中的POI间的链接权重设为无穷大∞表明这些权重为∞的连接实际上不存在于下面的算法中。鉴于Hi的成员和Hj的成员及hj之间的链接权重只是从hi和hj之间的连接权重复制过来。如图3b中所描绘{h1h11h12}中的相互连接权重设为∞h2和h21之间的连接权重也一样。余下的所有链接权重都设为5从h1和h2之间的链接权重复制过来。在接下来的步骤中我们将虚拟POI和POI看做一样。 第2步.找到一个TSP路径P。由于上面的权重图不是一个几何图我们不能用PTAS中的近似算法来处理这张图中的TSP问题但是我们可以用到Christofides算法[13]的帮助,我们可以为这个问题找到一个近似比为1.5的路径P其时间复杂度为Om3,其中m为POI的数量。注意到路径P只访问每个POI一次并且POI hi在路劲P上有额外的k(i)个复制。 第3步.分割路径P。和CSWEEP相似我们路径P分割成许多相等的部分其长度为L0υ/2f。接着我们分配给每个部分一个来回运动的传感器。结果是我们可以保证路径上的所有的POI包括虚拟POI在1/f个时间段远内将至少被访问一次。由于POI hi在路劲P上有额外的k(i)个复制那么hi在1/f个时间单元内将至少被访问k(i)1 fi/f次。因此在ti个时间单元内hi至少被访问fi/f·ti·f1次。所以GSWEEP能证明所需的扫描交换。 定理3.GSWEEP算法有一个最多为3的近似比。 证明.如GSWEEP算法中所展示的在我们建立的完全图中的相应TSP问题Christofides算法有一个近似比1.5。这表明如果TSP问题的优化长度为L那么由Christofides算法导出的路径P有一个长度L3L/2。那么GSWEEP所需的传感器数量是Ngs L/ L03L·f/υ。同时最少传感器扫描覆盖问题的优化方案为Nopt≥L/(υ·1/f)L·f/υ。由此GSWEEP的近似比为Ngs/Nopt≤3。证明完成。 4.5扫描覆盖的非定域性 在全覆盖中已经证明传感器可以在本地确定一片给定区域是否被完全k覆盖[17]。如果传感器感应圆盘边界上任意一点被少于k个传感器覆盖那么这个传感器就能本地断定这片区域没有被完全k覆盖。 然而在扫描覆盖情况中一个独立的移动传感器对一组给定的POI是否全局扫描覆盖无法本地判断“是”或“否”。我们可以解释如下。 在很多应用中POI的数量巨大而且他们之间的距离很长。一个传感器不足以满足各种应用需求所以两个或更多的传感器是必需的。在这样一个传感器网络中如果没有像GSWEEP这样的中央确定性方案支撑一个传感器si无法知晓所有其他传感器的全部移动路径。那么si无法决定在它自己每个扫描周期中未被它自己监测到的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的平均扫描周期和标准方差。我们设定传感器的数量为n10,而移动传感器的移 图7 图8 动速度为υ0.3m/s。然后对于不同的扫描周期需求t80120和160s分别作以下实验。我们运行DSWEEP和RAND各100000s并计算每个POI的实际扫描周期。 图7说明POI的扫描周期如何不同于所需扫描周期。图a展示了当所需扫描周期为t80s时独立POI不同扫描周期的CDF(累积分布函数)。很明显DSWEEP显著优于RAND。首先平均周期小于所需周期80s的POI部分DSWEEP的结果为78%远远高于RAND的51%。这说明在DSWEEP中更多的POI达到了他们的扫描周期需求。此外DSWEEP的CDF曲线比RAND更快的打到了100%证明那些不能满足所需扫描周期的POI不会延迟太久。图7b展示了所需扫描周期为t120s的模拟。与前面的情况相似首先我们可以发现DSWEEP中的集中于所需扫描周期t120s附近而在RAND中则沿着整个跨度分布。因此在DSWEEP中更多的POI满足需求而对于超过了所需周期的POI也不会延迟太久。图7c中将所需扫描周期提高到160s并显示了相似的结果。以上结果的主要原因在于在RAND方案中移动传感器没有协调合作因此导致在很长时间内某些POI可能被频繁访问而其他POI则很少被访问的事实。然而在DSWEP中如果一个POI hi最近被一个传感器监测过了传感器会禅师通过传染交换发送出这个信息。此后其他得到这个信息的传感器不会扫描覆盖它直到POI的下一个截止期限到来。 我们进一步测量所有POI的平均周期和标准方差。我们计算所有POI的平均周期来看看全局效益计算方差来看看每个独立POI的波动。图8中我们做三组实验来评估RAND和DSWEEP的性能。 图8a使移动传感器的数量变化并绘制了所有POI的全局平均扫描周期。移动速度为υ0.3m/s 所需扫描周期为t80s。如预期一样随着移动传感器数量的增增DSWEEP和RAND的全局扫描周期都呈递减。DSWEEP的曲线比RAND的更低并更快的递减到80s 图9 说明了DSWEEP能保证用更少的传感器让大部分POI达到他们的扫描周期。DSWEEP的标准方差总是比RAND的更小。一个小的方差对于证明多数POI的平均扫描周期接近全局平均差异非常重要因此能满足需求。图8b让传感器的速率变化并绘制了所有POI 的全局平均扫描周期。移动传感器的个数为n10扫描周期为t80s。结果与图8a中相似。随着移动传感器速率的递增DSWEEP和RAND的全局平均扫描周期都呈递减。如预期一样DSWEEP在小平均扫描周期和小方差方面的表现都优于RAND。图8c让所需扫描周期变化。移动传感器的数量为n10,移动速率为υ0.3m/s。如图所示显然RAND和DSWEEP之间的效率不同。RAND在实际需求中平均扫哦么周期变化的很小而DSWEEP的平均扫描周期非常灵敏的满足不同的需求。同时方差下降的非常快保证了大部分POI的独立性 能非常接近于全局性能。因此当全局性能足够时大部分POI能满足所需扫描周期。 通过以上各种模拟通过与随机算法比较DSWEEP用很少的传感器在更低的移动速率提供了所需的扫描覆盖。 6.2.2 不同扫描周期的POI 当POI有不同的重要性他们所需的扫描周期可能不同。在这组实验中我们把POI分成3种类型第一种扫描周期为t80s第二种扫描周期为t120s第三种扫描周期为t160s。每个类型都有相等数量的POI。然后不同数量的传感器和不同速率被测试来评估它们对POI的独立平均周期的影响。我们把满足了所需扫描周期的POI称为可信POI。图9分别展示了三种类型POI的可信部分。 图9a和图9b通过不同数量的移动传感器比较了DSWEEEP和RAND。移动传感器的移 图10 动速率被设为υ0.3m/s。显然DSWEEP有更多数量的可信POI,表现优于RAND。而且在DSWEEP中所有三种类型的POI有类似的小部分可靠POI说明DSWEEP适用于混合扫描周期需求。然而在RAND中三种不同类型POI和彼此差别很大。有着宽松需求(t160s)的POI的有大量的可信POI而有着严格需求(t80s)的POI只有少量的可信POI。相似的结 果在图9c和9d中也有显示其中我们让速率和传感器变化。因此更具以上结果DWSWEEP显示出更适用和通用于混合扫描覆盖需求。 6.3 所需传感器数量 我们在这小节研究最少传感器扫描覆盖问题的效率。最少传感器扫描覆盖问题的目标是用最少数量的传感器保证所需扫描覆盖。如上面提到的没有分布式本地算法保证每个POI满足扫描周期需求即使是DSWEEP。因此我们测试实际的平均扫描周期并把它与扫描周期需求相比。如果想对误差小于10%我们认为移动传感器符合提供所需扫描周期。图10a展示了在所有POI有相同的扫描周期需求t80s的情况下RAND,DSWEEEP和CSWEEP所需的移动传感器数量。图10b展示了在3种POI有不同扫描周期需求t80120和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.转载于:https://www.cnblogs.com/guoyiqi/archive/2013/04/21/3203831.html
