无线传感器覆盖

1、利用多种算法在三维地形上部署传感器使得覆盖度与工作时间双目标最优化1、 引言 无线传感器网络（WSNs）是一种分布式传感网络，被广泛应用于军事、智能交通、环境监控、医疗卫生等多个领域。如今，无线传感器面临的最大问题就是如何合理地部署传感器用最少的传感器达到最大的覆盖度。关于这方面的研究大多数都是考虑二维平面上的传感器部署，而现实实践中传感器部署发生在三维环境中，所以不同三维地形上最优传感器部署是本文考虑的重点。同时，大多数研究对目标函数的设置往往只有无线传感器覆盖率，没有对其所消耗的能量进行研究。而在现实应用中，传感器网络的节点在电池能量上有所限制，而且由于物理限制难以给节点更换电池，所以传感

2、器节点的电池消耗是整个传感器网络设计最为关键的约束之一，他直接决定了传感器网络的工作寿命。因此，本文在目标函数中加入了传感器网络运行时间这一监测量。 本论文的组织形式如下：第二部分，介绍一些准备工作。第三部分，介绍本文涉及到的算法。第四部分，进行性能评估。该论文在第五部分进行总结。二、准备工作 本论文的主要目标是通过比较不同算法的性能来确定最优算法。在这一部分，我们简要介绍在该论文中用到的感知模型、工作时间模型与多目标函数的整合。A.感知模型 无线信道是指发射源向接收源发送电磁辐射的假象通道，发射源和接收源天线之间的障碍物密度很大程度上取决于物理环境，信道上的障碍物将直接对信道可联通性产生影响

3、1。WSNs中的概率感知模型描述了传感器覆盖率与距离和其他环境的关系2。在该模型中，我们定义了传感器s的两个检测范围，一个不确定的传感器检测范围Ur和一个传感器可检测范围Sr（Ur<Sr）。我们把于(Sr-Ur)和(Sr+Ur)的圆环范围称为模糊环。如果像素点p处于（Sr-Ur）范围内而且在s和p之间满足LOS，那p确定可以被检测到。如果p处于(Sr+Ur)范围之外，或者s和p之间没有视线，那么p肯定不能被检测到。此外，如果p处于(Sr-Ur)和(Sr+Ur)范围之间而且s和p之间满足LOS，那么检测概率可以被表示为exp(-.dist)。概率感知模型可表示为： 表示传感器s与像素点p间

4、的三维欧式距离。和的值反映了地形的环境特征，调整这些变量可以模拟出不同的地形。LOS表示s和p在三维地形所连接的直线不被任何障碍物阻碍，即如图所示 上图展示了一种简单的LOS情形，如图所示，如果传感器s和像素点p至今对应的任何一个像素点的高度没有切到连接s和p的线段，那么s和p之间有视线（LOS），否则s和p之间没有视线（NLOS）3。由于直线是连续存在的，而地形数据是由离散的点集构成，在模拟LOS过程中可能会出现的情况是直线穿过两点之间的空间，即如下图所示情况， 图中，直线SP穿过坐标A与B之间的C点，而由于地形数据中并无C点的高度坐标，为应对这种情况，我们的策略是令 其中分别代表点A，B，

5、C的高度坐标。在概率感知模型下，由于传感器节点的不确定性，目标区域内的像素点并不是以均一概率被覆盖。节点距离目标位置越近，其采集的信息越精确可靠；反之，离节点越远，感知能力越弱。若像素点p只被单一传感器覆盖或者距离其它传感器很远，则需对该像素点实施多点协同覆盖策略，以降低p成为盲点的可能性。设组成传感器集合为，为所有传感器对像素点p的融合覆盖强度，在概率空间下，可进行如下推导： 经典测量是一种可加性测度，然而在客观实际中，对事物的度量并不满足可加性。为此，基于Sugno测度的信息分析方法被提出4-6: 其中N代表传感器数量,，该融合算子表现为弱可加性，根据真实情况，可通过选择适当的参数来跟好地

6、估计传感器网络的覆盖度。 使用表示像素点p的覆盖率门限，由于的数值在0-1之间变化，因此为了评价感知模型下的网络覆盖率，定义： 经研究，我们发现当=0.7时比较符合实际情形。 QoC反应了每次部署操作后地形被覆盖的程度，QoC计算如下： 其中P代表像素点数量。B.时间模型传感器进行感应和通信时需消耗能量，所消耗能量E包含通信能量消耗和其他能量消耗两部分。在这个模型中，我们定义了一个传感器的通信距离。如果两传感器间的距离小于通信距离，则两传感器将进行通信，需要为通信消耗能量，否则不需要消耗能量。考虑到传感器节点交换信息的目的在于提高位于传感器模糊环处的覆盖率，同时出于节能的目的，我们将通信距离设

7、置为 即让两传感器间恰好能交换位于模糊环边缘的像素点的信息。两传感器间的通信能量消耗可表示为7： 其中k和n（）为系数，和表示传感器，表示两传感器间的距离。则某一个传感器s的耗能可表示为： 假设每个传感器的初始能量为e，则节点s可正常工作的生命周期为： 若网络中的部分节点提前耗尽能量，则网络联通性将受到影响，整个网络将处于瘫痪，因此通常将第一个“失败”的节点的生命周期定义为整个网络的生命周期： C.目标函数 本文有两个目标函数，即部署方案的覆盖率QoC与工作时间T。我们将两个目标函数进行整合，以适应度函数来替代目标函数。公式如下： 其中为系数。三、实验中所用到的算法A.CSO-AVE算法 群智

8、能概念是通过观察生物的行为发展起来的，并用于解决组合优化问题。通过对猫科动物的观察，人们提出了猫群优化算法（CSO）。 在猫群算法中，猫被分为跟踪和搜索两种模型，在搜索模式中猫观察四周并寻找下一个要移动的位置。在跟踪模式中，猫跟踪一些目标。CSO的其中一个重要特征是猫花费大多数时间在搜索模式。它们一旦找到一个好的猎物，就会立即进入跟踪模式。CSO算法很简单，它首先创建大量的猫并将其置为搜索模式。将猫随机洒到M维解空间中，并在预定义的值范围内随机选择值。然后根据一个选择标准，随机地将一部分猫置为跟踪模式。每次移动之后，猫的适应度值都被重新计算，最好的结果将被存储起来。这个算法的所有过程都被重复执

9、行，直到满足终止条件时，循环结束。CSO-WT由Samil Temel，Numan Unaldi，和Okyay Kaynak8提出。该算法在传统猫群算法的基础上，加入了离散小波变换技术，对QoC矩阵进行小波变换得到其DWT值用于检测Qoc矩阵的覆盖漏洞。变换后得到的逼近系数矩阵包含了QoC矩阵的能量压缩，且较QoC矩阵来说有更少的维数，但它仍然提供了关于覆盖漏洞的足够信息，来确定部署新传感器的候选像素位置。 基于这一思路，我们用插空均值法替代小波变换，提出了CSO-AVE算法。所谓插空均值法，即对于二维矩阵lon,wid中每个纬度从第一个下标其每隔4个下标作为首坐标截取一个4×4的矩

10、阵，计算该子矩阵的平均值形成新的压缩矩阵。算法如下：AVE压缩 for（int i=0;i<lon;i+=4） for（int j=0;j<wid;i+=4） for（int p=0;i<4;i+） for（int q=0;j<4;i+） sum+=QoCi+pj+q; Avei/4j/4=sum/(4*4); 在算法中，我们将一个32×32的QoC矩阵进行AVE运算，得到了一个8×8的压缩矩阵。这一做法有助于降低压缩QoC矩阵所需的计算量，并能保持QoC矩阵总体特征。CSO-AVE算法如下：算法 1 CSO-AVE算法 加载 地形T；设置 Ns；

11、%初始化模式第一步：在地形上部署限制数量的传感器并计算该部署情况下的QoC值第二步：对QoC矩阵进行AVE运算来检测QoC矩阵中的覆盖漏洞。将剩 余的传感器部署到未被覆盖的区域。称每个部署为一个Dv，Dv代 表了一个猫。第三步：计算该部署情况的适应度值并将其追加到对应的Dv上。第四步：保存Dv。跳转到第一步，重复k次。 重复执行根据比例MR将部分猫置为跟踪模式。 %搜索模式If 猫在搜索模式 then第一步：将猫Dv（k）复制SMP份第二步：对于复制出的猫，根据比例CDC，选择部分猫作为要改变的候 选猫 第三步：对于第二步中选择出的Dvs，随机改变其中SRD的传感器的位 置，传感器根据SMR值

12、移动。第四步：计算所有猫的适应度值并将这些值追加到对应的Dv。第五步：选择具有最高适应度值的Dv，让其替换原始猫。End if %跟踪模式If 猫在跟踪模式 then第一步：对于Dvs中的每个猫，百分之MRT的传感器将被移动。AVE揭 示了传感器周围覆盖率最低的区域（覆盖漏洞），传感器移动 正是利用了AVE。根据AVE值移动传感器到周围的对应区域。第二步：计算所有猫的适应度值，如果移动后Dv的适应度值大于原始 猫的，则用移动后的Dv替换原始猫。End ifUntil 满足终止条件 B.PSO算法 粒子群算法由J.Kennedy和R.C.Eberhart于1995年首次提出，其基本思想是：每一个

13、粒子都在空间中依据两类重要的信息来不断更新飞行的速度和方向，即自身经验信息和整个群体的经验信息。 基于这一思想，粒子群优化算法的基本流程如下。设群体的规模为N，在一个n维的空间内，每个粒子维持着其位置向量和速度向量，i代表种群中第i个粒子。PSO算法如下：算法 2 PSO算法 加载 地形T；设置 Ns；第一步：对每个粒子i初始化粒子的速度和位置，并将该粒子的历史最 优位置设置为当前位置，整个群体 中最优个体位置记为。 重复执行第二步：每个粒子根据该粒子的历史最优位置和整体最优位置来更新粒子的 飞行速度，即 第三步：根据更新的飞行速度，粒子进一步更新所处的位置 第四步：评估每个粒子位置的适应度，

14、如果适应度优于该粒子的历史最优位 置pbest，则更新pbest；如果适应度优于整个群体的历史最优位 置gbest，则更新gbest。 Until 满足终止条件 本文还对CLPSO9、DE等算法进行了比较C.算法优化由于地形的大小固定，为避免发生传感器越界的现象，需要对算法进行边界处理。此外，考虑到将传感器部署到边界附近时，传感器感知范围将大幅度降低，因此在边界处理的同时应避免传感器与边界靠近，即传感器与边界应保持距离d，我们让d恰好为传感器感知模糊环的内径，边界处理算法 while（判断传感器坐标值a是否在地形内）/超过边界部分关于边界对称 if (a<0) a=|a| else if

15、 (a>lon) /lon为边界 a=lon-(a-lon) end while if(a<d)/避免靠近边界 a=d else if(lon-a)<d) a=lon-d return a 四、性能评估 首先，我们对CSO-AVE、PSO、CLPSO、DE等算法进行测试，每隔20代抽样一次，结果如下表所示： 我们可以发现，在迭代次数相同条件下，算法性能为PSO>CSO-AVE>CLPSO。迭代次数csopsoclpso最大值0.7120.7190.7030中位值0.6850.6690.667平均值0.686280.670680.67228标准差0.01293097

16、10.016677630.032843721最大值0.7730.7830.77520中位值0.740.7520.729平均值0.740.753320.72972标准差0.0125399360.0171189950.017331378最大值0.7870.8240.7840中位值0.7560.780.734平均值0.75780.777880.73932标准差0.0130958010.0218523840.016960051最大值0.80.8430.7860中位值0.7660.7890.742平均值0.767240.79260.74504标准差0.0127255650.0258618120.0145

17、75893最大值0.8030.8930.7880中位值0.7730.8050.742平均值0.77460.80960.74696标准差0.013702190.0290516780.014432256最大值0.820.8950.78100中位值0.7820.8220.746平均值0.784360.82160.74896标准差0.0152147950.027937430.013645756最大值0.820.8980.78120中位值0.790.8320.748平均值0.789480.831040.75016标准差0.0135096260.0291425810.013030989最大值0.820.9

18、070.78140中位值0.7950.8410.748平均值0.792840.840160.7502标准差0.0122054630.0294557290.012980755最大值0.820.9130.78160中位值0.7990.8430.751平均值0.797440.847080.75168标准差0.011722770.029856490.013113987最大值0.820.9170.78180中位值0.80.8570.751平均值0.801080.855320.75216标准差0.0096476250.0313551170.012788928最大值0.8210.9730.78200中位值0

19、.8020.860.751平均值0.80380.867520.75268标准差0.0097638790.0380691480.0121061975、 总结 在WSNs中，如何部署传感器使其具备较好的覆盖度、可以被接受的工作时长是一个具有挑战性的任务。相较二维地形，在三维地形上部署传感器需要更多的从视觉、图像等角度入手进行研究，具有现实性与实用性等特点。本文基于种群进化算法并进行适当改进，通过实验我们发现在三维地形部署传感器问题上，类似于PSO以全局最优值来优化个体的全局性算法收敛性快、效果较好，而类似于CSO这种基于物理方式探索的局部性算法也具有较好效果，而CLPSO由于收敛性较慢，导致可行行

20、差。今后，我们将尝试将PSO算法与CSO算法结合成一个新算法，使算法保证粒子向最优解收敛的同时也重视粒子的局部多样性。参考文献：1 D.Tse and P.Viswanath, Fundamentals of Wireless Communication, Cambridge, U.K.: Cambridge Univ.Press, 2005.2 H.Chizari, M.Hosseini, T.Postonm, S.A.Razak,and A.H.Abdullah,”Delaunay triangulation as a new coverage measurement method in

21、wireless sensor network,” Sensors, vol.11, no.3, pp. 3163-3167,Mar.2011.3 D.Hearn and M.P.Baker,”Computer Graphics”,Englewood Cliffs, NJ, USA: Prentice Hall, 1994.4 M Sugeno. Theory of fuzzy integrals and its applicationsD. Tokyo: Tokyo Institude of Technology,1974.5 Michel Grabisch,Toshiaki Murofushi, Michio Sugeno. Fuzzy Measures and Intergrals Theory and ApplicationM. Germany :Physica-Verlag Heidelb