摘要

针对传感器的覆盖，提出*********。

引言

无线传感器网络被广泛应用，如医疗、环境、军事方面。无线传感器网络存在两大问题：覆盖控制和节点能量。覆盖能够延长网络生存时间，国内外许多学者在这个方面做了大量的工作。有向传感器网络是无线传感器网络的一种，本文针对有向传感器网络的覆盖做研究。

近年来，许多专家学者提出了有向传感器网络覆盖控制问题和解决方法。Ma等首次提出了有向传感其网络的概念，设计了一种二维有向感知模型，并研究了覆盖问题[8]。陶丹等[4]提出了一种基于虚拟势场的有向传感器网络覆盖增强算法，引入“质心”的概念，通过质心点在虚拟力的作用下，实现节点的运动，消除重叠区和盲区，从而提高整个网络的覆盖率，但是质心所受合力的计算较复杂。符祥等[5]基于全局贪心原则，提出了一种有向传感器网络覆盖算法。以节点各方向下一重覆盖区域的大小为优先级，优先确定一重覆盖区域面积最大的传感器节点方向，减少重叠覆盖区域。解决控制问题的方法还有很多，如覆盖控制算法[13]，粒子群算法等。粒子群算法具有较快的收敛速度，但容易进入“早熟”状态。

顾等[1]混沌算法能很快的找到全局覆盖最优值，只能迭代60次，但混沌搜索式的随机性，遍历性不如junxiao等[6]圆映射公式好，junxiao等考虑了移动节点的能量，很好地实现了覆盖，但是只针对全向传感器。李靖等[11]的粒子群算法融入了模拟退火和轮盘赌的思想，很好地解决了粒子群算法易陷入局部解，但此算法的覆盖提高率并不高。

在本文只针对覆盖问题，在顾[1]的基础上，寻找全局最优值，对混沌粒子群算法进行改进，进一步提高网络覆盖性。与顾和李靖的模拟退火相比此算法具有更好的优越性。该算法利用粒子群算法较快的收敛速度和混沌搜索的遍历性、随机性，不仅保证了算法的收敛速度，而且有效避免了基本粒子群算法的“早熟”现象。仿真实验证明，该算法能有效地优化节点布局，扩大网络覆盖率。

本文章节如下：第2节介绍网络模型，第3节详细介绍混沌粒子群覆盖优化算法；第4节是仿真实验和仿真分析。

2网络模型

2.1 有向感知模型

通常把感知模型抽象为一个四元组，其中L(x,y)：节点位置，对应于二维直角坐标系下的坐标；R：节点感知半径；θ：感知区域视角FOV=2θ，θ称为感知偏向角，0≤θ≤π；β：FOV中线相对于水平正方向的角度，可看作是有向传感器节点的方向参数，0≤β＜2π。 ..pθßsv

图一

假设网络中所有节点同构，即所有节点感知半径、传感夹角参数规格相同，且满足有向感知模型。节点一经部署，位置不再改变，但感知方向可调。

在监测区域A中，部署N个节点，传感器节点集合S={S1,S2,S3,...SN}，其中Si表示第i个节点，i= 1, 2, „, N；若点P(x,y)被Si覆盖，则满足下列公式：

22(,),(,)()()(,)cosiiiiiidsprdspxxyyspvdsp其中(1)

2.2有向传感器覆盖面积

解决有向传感器网络覆盖问题，要使初始部署的传感器不断调节感知方向，使覆盖面积增大，减少盲区，从而增加覆盖面积，达到最优覆盖。

理想状态下在区域A内按均匀随机部署有向传感器节点，任意2个节点不在同一位置，且所有节点一经部署后，位置固定不变，方向可调。忽略边界效应，任一节点si对整个区域的监测(即覆盖)概率为22RA，其中‖A‖代表区域A的面积。A被N个有向传感器节点覆盖的概率P0的计算公式为 2021(1)NRPA (2)

而实际假设在待测区域A中，离散的分布着传感器节点集合为S，将待测区域离散化为mn个像素，像素点P(x,y)被传感器节点集Si覆盖的概率为：

covcov1,0,(1){PP公式(1)成立不成立 (3)

被集合S覆盖的像素点总和cov1()mniPi，网络的区域覆盖率areaP为A中被Si覆盖的像素点总和与监测区域总面积之比：cov1()mniareaPiPmn

(4)

3混沌粒子群覆盖优化算法

混沌是一种非线性系统的特点,论证了对初始条件的依赖和无限的不稳定的周期性运动,由于它的非重复性，它可以进行全面的搜索。混沌粒子群算法即结合了混沌和PSO算法，利用粒子群算法较快的收敛速度和混沌搜索的遍历性、随机性，不仅保证了算法的收敛速度，而且有效避免了基本粒子群算法易陷入局部极小值。

3.1粒子群算法

假设在数据集合中包含的粒子群数目是n，而各个粒子包含节点的数目是N，每个粒子都可以描述一种空间位置关系。假设每个粒子中节点的位置保持不变，但感知方向可调，即每个粒子的空间位置的方向不一样。d维搜索空间中的第i个粒子的位置和速度可分别表示为Xi = [xi,1, xi,2, „, xi,d]和Vi = [vi,1, vi,2, „, vi,d]。迭代t次每个粒子的最佳位置(pbest) ，以及群体最佳位置(gbest)，每次迭代按如下公式分别更新各粒子的速度和位置。

,,11,,22,,(1)()[()()][()()]ijijijijgjijvtwvtcrptxtcrptxt (6)

,,,(1)()(1), 1,2,,ijijijxtxtvtjd

(7)

其中，w惯性权重系数(AIWF，adaptive inertia weight coefficient),c1和c2为正的加速常数，r1和r2在[0, 1]之间均匀分布的随机数xi,j(t+1)、vi,j(t+1)分别为迭代后粒子群的位置和速度。

3.2基于混沌粒子群的有向传感器网络覆盖优化算法

本文中提出的基于混沌搜索的粒子群优化算法是以基本粒子群优化算法的运算流程作为主体流程，把混沌搜索机制引入其中，以此来增强全局搜索能力，摆脱局部极值点的吸引，同时又不降低收敛速度和搜索精度．其基本的执行过程是先随机产生初始群体，然后开始随机搜索，通过基本的粒子群优化算法（式（6），（7））来产生一组新的个体,gbest为中心的一定范围内进行混沌搜索，将混沌搜索得到的最优解ｘ′作为新的gbest继续原粒子群算法的求解。

混沌映射公式采用Yan[4]中的圆映射:

n+1nnn1mod40.2sin4π,18xxxx（8）

其中xn的取值范围[0,2]。若xn大于2，对xn进行取模去算，即mod(2)

此混沌序列有更好的均匀性，遍历性。

基本算法步骤如下：

步骤1 初始化粒子群的个数，节点的个数,半径，传感方向，感知视角，速度。

步骤2 通过公式(2)、(3)和(4)计算网络的初始覆盖率为p0。

步骤3 初始化gbest和pbest为p0，其中，gbest用来存储全局最优传感器感知方向，pbest存储各粒子群的感知方向。 步骤4 计算各个粒子群的覆盖率，（每一个粒子群代表的是可能的一组解）比较每个粒子群的当前的覆盖率和pbest的覆盖率，若当前的覆盖面积大，则更新pbest。

步骤5 比较pbest的覆盖率和gbest的覆盖率，若pbest的覆盖率大，则更新gbest，使gbest=pbest；否则，gbest不变。

步骤6 对gbest的粒子群，根据公式（8）进行混沌优化

步骤7 再次计算当前覆盖率，和混沌前的覆盖率进行比较，如果现在的覆盖值大，则更新gbest。不好，则舍弃。当前值，就是覆盖率，也存在两个极值点。把当前值与两个极值点进行比较，再决定是否更新。

步骤8根据公式(6)、(7)更新粒子群的速度，感知方向，并对其速度和方向进行mod（2）。

步骤11如迭代没结束，返回步骤4。

算法流程图

初始化计算个粒子群的覆盖率更新pbest，gbset对gbest混沌扰动计算当前覆盖率gvalue1gvalue1>gvalue更新gbest更新粒子群速度和感知方向迭代次数

4仿真实验

为了验证本文算法******的有效性和优越性，用matlab进行实验仿真，实验参数设置如下：

节点个数N 50~200

感知半径R 5~15m

感知偏向角θ π/6, π/5, π/4, π/3, π/2, π

粒子个数W 30

加速常数c1, c2 1.05

粒子群更新

w采用参考文献[6]中函数定义如下： maxminminminmin()avgavgwPPwPPPwwotherwisewP，，（6）

其中，f为当前的覆盖率，fmin为粒子群的最小覆盖率，favg粒子群的平均覆盖率，wmax=0.9，wmin=0.4。w为线性递减函数，使种群具有多样性和维持良好的收敛能力,即使得算法能较快集中到全局最优解附近,以致得到全局最优解。

4.1 实例分析

假设在100 m ×100 m的监测区域中随机部署200个方向可调的传感器节点，感知半径为r=10m，传感区域视角为2θ，感知偏向角θ= π/8。根据式(1)，理想状态下粒子群的的覆盖率为200202π101179.34%4100p。如图2所示，记录了*****算法运行迭代次数不同有向传感器网络覆盖质量情况。初始覆盖仅为52.72%

从图2(a)中可以看出，因为部署的随机性，网络中存在很大的重叠区和盲区。图(a)至图(f)可以看出随着时间的推移，各节点方向不断调节，此算法网络覆盖程度逐步得到提高，图(b)至图(d)和图(e)至图(f)的覆盖率保持不变，能够使覆盖率快速收敛到最优。当时间的推移，网络的覆盖程度达到54.34%，与初始覆盖相比提高了1.62个百分点，如图2所示。

图2 ******算法的覆盖优化 4.2仿真分析

通过一系列的仿真，并与文献[11]中的HIACO算法和文献[1]中CPSO算法进行比较，说明本文中提出的HIACO算法的优越性。

图3是在节点感知半径为10m、偏向角为π/4的条件下，网络覆盖质量与节点个数之间的关系。从图中可以看出，随着节点个数N的增加，网络覆盖程度呈持续上升趋势。当N很小(≤55)或者很大(≥190)时，覆盖质量较之初始部署的提高量并不大(≤8.5%)。这是因为前者区域中节点较少，相对分散，致使相邻多传感器节点间形成的覆盖重叠的概率相对较低；后者区域中节点较多，网络节点密度(NA)较大，使得网络中存在覆盖盲区的概率较低。所以只有在网络中N适中的情况，HIACO算法效果明显。例如当N = 90时，网络覆盖程度提高13.6%。

同样地，如图4和图5所示，感知半径R和感知偏向角α对HIACO算法性能的影响与上述类似。随着R或α的增大，网络覆盖逐步提高。当网络中N一定时，R或α取值较小时，单个节点覆盖域相对较小，使得相邻节点间形成的覆盖重叠的可能性也就较小；R或α取值较大时，网络中存在的覆盖盲区的概率较低，这些同样使得HIACO算法对网络覆盖质量提高不显著。

从图3~图5中可以看出，较之文献[18]中的贪心算法和文献[16]中的集中式算法，在参数取值相同的情况下，本文提出的HIACO算法对初始部署网络优化后覆盖质量提高最大，说明了该算法性能的优越性。

图3 网络覆盖程度与节点个数的关系(R = 10m, α = π/4)

图4 网络覆盖程度与节点半径之间的关系(N = 200, α = π/4)