论文(计算机工程).doc

WSN巡航覆盖二阶段TSP移动策略研究陈燕，张振亚，方潜生安徽省智能建筑重点实验室，合肥，230022摘要：建筑环境中关于能效状态的物理参数可以通过无线传感器网络中的无线传感器节点进行监测。为了减少系统成本以及降低系统复杂度，本文对无线传感器网络巡航覆盖进行了研究。移动传感器移动路径规划是巡航覆盖中的一个重要的问题，本文对巡航覆盖中移动传感器的移动策略进行了研究，并提出了二阶段TSP算法规划移动传感器的移动路径。实验结果表明该方法能够得到较短较均衡的路径。关键词：WSN；巡航覆盖；二阶段TSPResearch on two-stage TSP Method for moving strategy of WSN sweep coverageCHEN Yan1, ZHANG Zhenya2, FANG Qiansheng21.Intelligent building, Anhui University of Architecture,Hefei;2.Key Laboratory of Intelligent Building, HefeiAbstract: Environment physical parameters about the energy efficiency status in building can be monitored with wireless sensor network with mobile node. To reduce the cost and complexity of wireless sensor network, sweep coverage in wsn is studied. The moving path planning for mobile sensors is an important problem, the moving strategy of mobile sensors is researched in the paper, and two-stage TSP method is proposed for moving path planning. Experimental results show that two-stage TSP method can get shorter and balanced moving path.Key words: WSN；sweep coverage; two-stage TSP1、引言建筑能效状态可以用建筑能耗状况以及诸如温度、湿度、风速、气压、空气品质等评估建筑能效必须的建筑环境物理量表示。建筑能效状态监测是建筑节能监管、能效评估、能效审计实施的重要环节。由于建筑空间结构功能繁复而复杂多变，集感知、通信乃至控制功能与一体的无线传感器网络1,2,3可以有效应用于建筑能效状态监测。无线传感器网络应用于建筑能效状态监测时，需要使用无线节点对监测区域内的监测点进行覆盖以实现目标物理量的采集。无线传感器网络地毯式覆盖和栅栏覆盖都可以实现建筑能效监测。无线传感器网络地毯式覆盖4-7是对监测区域的整体连续覆盖，栅栏覆盖是对敏感位置的连续覆盖。这两种覆盖计算具有时间连续性和空间连续性特点。而在以建筑能效状态监测为目标的无线传感器网络应用中，对监测区域内监测点处目标物理量的信息采集具有两个显著的特点：1）监测点在空间中不是连续的；2）监测点处需要感知的物理量不需要实时采集。这两个特点使得在以建筑能效状态监测为目标的无线传感器网络应用中，无论是地毯式覆盖还是栅栏覆盖都会造成传感器信息处理能力的浪费。为提升传感器节点的信息处理能力进而提升监测系统的能效，可以使用移动节点8,9实现需要时刻时监测点处目标物理量的采集，即通过移动节点实现无线传感器网络对监测区域内监测点的信息采集的动态覆盖。无线传感器网络动态覆盖不仅可以显著减少无线节点的数量，也可以实现监测区域内不适合静态部署监测节点处监测点处的物理量的有效采集，具有很大的灵活性。无线传感器网络中采用移动传感器进行数据采集的过程中，移动传感器之间的能耗均衡性决定了整个网络均衡性，同时移动传感器能耗之间的差异决定了网络寿命长短。与此同时，由于移动传感器本身的成本较高，为了进一步减少系统成本、降低系统的复杂性以及延长网络寿命，此时必须合理规划各个移动节点的兴趣点访问路径，均衡各个移动传感器的能量消耗。本文在定义了无线传感器网络巡航覆盖的基础上，定义了网络均衡性问题并提出了解决网络均衡性问题的方法。WSN巡航覆盖模型在第二部分给出，第三部分提出了二阶段TSP算法解决网络均衡性问题，第四部分给出并讨论了实验结果，总结与研究展望在第五部分给出。2、无线传感器网络巡航覆盖模型无线传感器网络可以有效应用于动态环境中的信息感知过程的实现。设是监测区域，是传感器部署位置，即可以使用传感器可以感知附近的目标信息，称是兴趣点，同时，传感器部署在称作被覆盖，简称被覆盖。又设在无线传感器网络应用中，信息采集过程需要在兴趣点位置周期性进行，。对，处的一次信息采集过程需要在T时刻内完成且第k次信息采集过程需要在时刻前完成，称是兴趣点集P的最大访问截止时刻。由于P中兴趣点处的信息采集行为不需要连续发生，可以使用移动传感器在每个兴趣点截止时刻到来之前移动到目标兴趣点并完成信息采集任务。采用移动传感器，一方面可以降低监测系统中传感器的部署数量，另一方面也可以减少传感器的静态部署对监测区域内空间使用的占用时间，同时，移动传感器还适用于无法静态部署传感器的监测区域中兴趣点处信息的感知。设是兴趣点集，是兴趣点集P的最大访问截止时刻，是第个移动传感器节点在最大访问截止时刻内覆盖的兴趣点顺序序列且，则是第个移动传感器节点在最大访问截止时刻内的移动路径。移动传感器在内移动实现各兴趣点目标信息采集的过程是各兴趣点被移动传感器覆盖的过程，特别的，对任意移动传感器，若，且满足命题2的要求则称移动传感器在最大访问截止时刻内对所有兴趣点的一次有效巡航覆盖。命题1：若是兴趣点集的最大访问截止时刻，则是移动传感器节点的最小移动周期。#命题2：设是兴趣点集，是兴趣点、间的距离,是无线传感器网全部移动传感器节点集, 是的移动速度，,是兴趣点集P的最大访问截止时刻，是在最大访问截止时刻内巡航覆盖移动路径，则。#阈于移动传感器的移动性能以及监测区域中兴趣点空间分布的特性，一般需要多个移动传感器节点协作完成截至时间内监测区域中目标兴趣点的巡航覆盖。移动传感器节点通过巡航覆盖可以实现对兴趣点集的周期性访问。为确保这种周期性访问的有效性，无线传感器网络需要对每个移动传感器节点的移动、信息采集行为以及其它辅助行为（如移动节点同步操作）进行维持。设是兴趣点集，是兴趣点集P的最大访问截止时刻，是系统维持移动传感器节点从兴趣点移动到兴趣点付出的移动成本，是系统维持移动传感器节点在兴趣点处信息采集行为付出的信息采集成本，是系统维持移动传感器节点在兴趣点处其它行为付出的成本。又设是第个移动传感器节点在一次有效巡航覆盖过程中的移动路径，显然，故无线传感器网络维持第个移动传感器节点的成本为=+。设是无线传感器网全部移动传感器节点集，则该无线传感器网络维持一次有效巡航覆盖的成本。命题3：一次低成本有效巡航覆盖过程，每个兴趣点被覆盖且仅被覆盖一次。#利用命题3的结论中明确路径规划中可以忽略,这里利用次有效巡航覆盖的成本的表达式说明降低一次有效巡航覆盖成本的关键指标：移动节点数+路径规划。这两个指标之间也是相互制约的，较优的路径规划可以减少移动节点数，对于固定的移动节点数，路径规划结果要满足有效巡航覆盖的条件。本文在移动节点数固定的情况下，优化移动节点的访问路径在保证访问路径长度较短同时也要达到均衡性要求，得到的移动传感器访问路径同时也可以验证给定的移动节点数是否满足有效巡航覆盖条件。3、二阶段TSP算法规划均衡路径负载均衡性是无线传感器网络中的一个关键问题，在部署静态传感器节点的网络中，通过优化设计无线传感器网络路由协议解决网络路由中的负载均衡问题。在完全移动传感器网络中，移动传感器移动比通信及感知消耗更多的能量。一般情况下，移动成本比其它成本高很多。因此，规划出m条负载均衡且移动距离最短的访问路径可以有效节省网络能耗且延长网络寿命。为了衡量网络负载均衡性，我们引用了均衡度的概念。均衡度的意义在于评价移动节点间负载均衡性，本文中主要考虑移动距离，故将均衡度定义如下：其中为第个移动传感器节点的移动距离，值能够很好地表达各移动节点移动路径均衡性。值越接0，表示每条路径长度越接近。但是在无线传感器巡航覆盖中，由于以下两种性质导致移动节点移动路径不可能达完全的均衡即，（1）兴趣点的分布不均匀性，以致兴趣点之间距离大小不一；（2）优化移动节点访问路径是一TSP（MTSP），这是典型的NP-Hard问题，很难得到最优解，即在有限时间内只能得到次优移动路径。尽管如此，的下界是存在的，设该下界值为（），当时，移动节点的访问路径均衡度最小，即达到最佳均衡状态。其中可通过实验获得。无线传感器网络巡航覆盖中移动传感器节点从各自起点出发访问监测区域中所有兴趣点，每个兴趣点在一个巡航覆盖周期只能被一个移动节点访问且只访问一次。这是一MTSP，一般监测区域兴趣点较多，直观地可以采用各种近似优化算法如智能优化算法得到次优访问路径，目标函数为各移动节点移动路径的总长度。而在实际应用中往往对移动路径均衡性有较高的要求。这种情况可将上述问题归结为多目标优化问题，即在满足各移动节点移动路径总和最短的同时也要保证移动路径的均衡性达到要求。对于这种问题一般地在目标函数中添加均衡因素。对于监测区域较大，兴趣点很多的情况，这种方式无疑给已经相当复杂的问题带来了更大的求解难度。同时由于算法需要同时处理两个优化目标，且这个优化目标之间存在制约关系，很难协调二者得到较优的结果，特别在问题规模较大的情况下，相比较只有一个目标函数算法需要迭代更多的次数才能得到一较优解。因此，如何高效的、快速的求解该问题并得到一个“折中解”显得尤为重要。本文采用二阶段TSP算法规划移动节点的移动路径同时保证访问路径最短及均衡性要求。该算法在保留了TSP路径最优的情况下，同时满足均衡这一目标。算法1：二阶段TSP算法输入：兴趣点集，兴趣点距离矩阵，是兴趣点、间的距离，移动节点数k输出：无线传感器网络巡航覆盖中各移动传感器节点的移动路径1) 利用算法2得到一个移动节点访问所有兴趣点优化路径2) s=n/k 3) 按中的访问顺序将整个路径分成k段，前k-1段中兴趣点的个数为s，第k段中兴趣点至少为s，则（其中,）为第个移动传感器访问兴趣点的集合，()为最后一个移动传感器访问兴趣点的集合4) While()5) 按路径调整每段中兴趣点的数目6) 利用算法2优化每个移动节点的访问路径7) 8) 得到每个移动节点均衡的移动路径算法2：基于遗传操作的广义粒子群优化算法输入： 被访问的兴趣点集，距离矩阵，是、间的距离输出：移动传感器的移动路径1) 初始化粒子种群2) While（未达到迭代停止条件）3) For 种群中每个粒子4) 5) 6) 与个体极值进行交叉7) 7) 8) 与领域极值进行交叉 9) 中与之间的部分进行反转 无线传感器网络巡航覆盖基于二阶段TSP移动路径规划方法分别由算法1给出。在算法1中调用了算法2，其中的算法2的适应度函数为路径长度，解的编码采用基于顺序表达的编码，兴趣点顺序按自然数排列，算法2用于得到单个移动节点的最佳移动路径。另外，由算法1所得到的每个移动节点的访问路径可以依据命题2判断所给移动节点数k值的是否满足有效巡航覆盖的要求，如果不满足可以相应增加k值，直至k值满足命题2中有效巡航覆盖的要求，如果所给移动节点数k满足，同样也可以相应减少k值，如此在保证有效巡航覆盖的同时减少移动节点数可以降低系统成本及复杂度，同时依据命题2，所获得的每个移动传感器节点的访问序列是一次低成本巡航覆盖。4、实验结果为了验证算法1的有效性及快速性，本文分别采用算法1以及采用算法3的多目标优化问题（以下称为适应度函数法）进行移动节点的访问路径优化，其中适应度函数法中适应度函数为：，其中为调节目标函数中两个组成部分之间比例系统（k0）。当k值较大时，总目标受总行程距离影响较大，得到的总路径距离较小但是路径之间长度差异较大，k较小时路径差较小，但总路径距离较大。本文实验的监测区域为一10*10的正方形区域，移动传感器的速度为0.5， = 5，适应度函数法迭代5000次，算法1兴趣点数为30，50时迭代500次，兴趣点为100，1000时迭代2000次，兴趣点为1000时为加快求解速度，初始化种群时采用最近邻法得到的解作为粒子。本文分别对兴趣点数不同的场景进行了访问路径规划，表1所示为不同兴趣点数分别采用算法1以及适应度函数法得到的路径总长度、均衡度及移动节点数。表1中第一列是监测区域内兴趣点的数目，第二列是采用的算法，每三列是通过各种算法得到的访问路径总长度，第四列是根据路径长度计算出的移动节点数，第五列为通过各种算法得到路径的均衡度，最后一列是巡航覆盖一周所用的时间。表1中，使用了算法1以及适应度函数法进行路径规划，由表1可以看出二阶段TSP算法相比较适应度函数法在移动节点数相同的情况下能够快速地得到长度更短更均衡的路径。图1所示为兴趣点为100时分别采用算法1以及适应度函数法得到的兴趣点的移动路径。表1 两种方法所得结果兴趣点数算法路径总长度移动节点数均衡度巡航覆盖一周时间t30算法149.1320.06450.78适应度函数法59.8720.5582.450算法165.3830.0745.7适应度函数法124.2430.45112.27100算法196.1750.2545.86适应度函数法300.2550.92281.371000算法1574.1180.3788.84适应度函数法8045.44180.987998.2a.适应度函数法获得的移动节点访问路径b.算法1获得的移动节点访问路径图1 两种方法获得的移动节点的访问路径5、总结本文对无线传感器网络巡航覆盖中移动传感器移动路径进行规划，采用二阶段TSP算法规划移动节点的访问路径。实验表明该方法相比较常规的适应度函数法能够快速得到均衡且距离最短的访问路径。无线传感器网络巡航覆盖中移动节点路径规划无论对网络成本、寿命、复杂度对有重大的影响。均衡且距离短的移动路径不仅可以降低系统成本及复杂度同时还可以延长网络寿命，在实际应用中，其具有重要意义。参考文献1 I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Computer Networks, 2002.38:393-422.2 Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, A survey on sensor networks, IEEE Communications Magazine, 2002, 40(8):102-1143 Ian F. Akyildiz, Xudong Wang ,Weilin Wang, Wireless Mesh Networks: A Survey, Computer Networks Journal, 2005,47(4): 445-4874 S. Kumar, T. H. Lai, and J. Balogh, On k-Coverage in a Mostly Sleeping Sensor Network, proceedings of ACM MobiCom, 2004.5 C.