基于QoS约束的感知网络覆盖研究

贾海云

(合肥财经职业学院,安徽 合肥 230601)

0 引言

工业生产各领域中传感器相互协作形成的感知网络的部署发挥了不可替代的作用。由于单一个体的传感器在不同环境中的感知能力有限,要扩展整个感知网络的感知范围,提升全网感知能力使之具备服务质量(Quality of Service,QoS)级网络服务能力,就必须科学规划每一个传感器的部署方位。这不仅有利于解决传感器重复感知的问题,也有助于优化整个感知网络的能效。因此,针对感知网络中传感器的方位部署问题,业界展开了一系列相关研究。GHOLAMI等[1]提出了高密度部署感知节点方案。感知节点被大量撒布在待检目标附近以确保目标数据被稳定精确地广播,然而该部署方案下的大量感知节点可能存在同时覆盖感知某一个区域内的多个待测目标。这将导致感知网络浪费大量能耗用于维持待测目标数据的冗余传输,同时网络资源的过度开销势必弱化感知网络的生存性和感知性能。并且成本也是一个制约该部署方案的瓶颈。GURUPRIYA等[2]提出了基于睡眠的感知节点部署方案,该方案根据感知节点差异化的感知性能为异构感知网络设计了评估算法。算法通过评估待测目标是否已处于感知节点监测之下,来控制相邻感知节点的睡眠状态以及睡眠时长。虽然该睡眠方案下的评估算法规避了重复覆盖和成本控制的问题,但是此类静态部署方案下的感知节点无法适时更新方位信息,导致感知节点无法自适应地解决覆盖漏洞问题。OTMAN等[3]考虑引入粒子群算法(Particle Swarm,PS),该算法下的粒子解均可作为科学部署感知节点方位坐标值的有效依据。虽然这一特征解决了文献[1]和文献[2]关于部署密度不均衡和静态感知所导致的覆盖漏洞、效能度低等QoS问题,但PS算法在粒子空间内开展搜索计算时存在收敛过早的问题,导致该算法的搜索值并不具备全局普适性,进而弱化了PS算法的部署成效。基于此,本文考虑通过调整PS算法在局部空间内的搜索权重,并引入变异评估机制来规避因算法陷入早熟导致搜索的粒子值缺乏全局普适性。根据普适性提升后的粒子值来部署感知节点,可有效地兼顾部署成本和服务覆盖的QoS,从而达到基于QoS约束的感知网络覆盖算法(QoS Constrained Aware Network Coverage Algorithm,ANC)目标成效。

1 数学计算模型

假设在一个N×K的目标区域范围内共有像素点[4]规模N×K个,且随机部署K个感知节点。感知节点的方位数据、感知半径范围以及工作能耗均可通过广播方式向感知全网共享。定义每个节点在感知网络内的坐标和感知半径范围分别为sk(Xk,Yk)和r。其中,感知节点坐标即为PS算法的初始参数。感知全网内的感知节点集合记作S={s1,s2,…,sk}。感知节点sk(Xk,Yk)和待测目标节点R(XR,YR)的间距表征为:

(1)

其中,k=1,2,…,K。

引入覆盖[5]判断机制F(sk,R)。当该值置为0时,代表待测目标节点R(XR,YR)不在感知节点sk(Xk,Yk)的感知范围内,此时满足条件rD(sk,R)。由于同一个待测目标可能同时被多个感知节点感知,故待测目标节点R(XR,YR)被感知节点集合S感知的概率为:

(2)

同理,当f(S,R)的值置为0时,代表待测目标节点R(XR,YR)不在感知节点集合S的感知范围之内。反之,当f(S,R)的值置为1时,代表待测目标节点R(XR,YR)已在感知节点集合S的感知范围之内。求得被覆盖的像素点规模为:

(3)

根据公式(3)可得到运行PS算法后最终获得的具有全局普适性的粒子目标适应值,即待测目标节点被整个感知网络覆盖的概率,将其表征为:

(4)

2 覆盖算法模型

PS算法在粒子求解空间内搜索出来的值是否具有良好的普适性[6],与PS算法搜索权重存在一定的关系。通常搜索权重越小,PS算法在求解空间内搜索出来的值越具备良好的局部普适性。反之,搜索权重越大,PS算法在求解空间内搜索出来的值越具备良好的全局普适性。为使PS算法能够在最短时间内快速地对局部网络范围内的求解空间进行强有力的目标值搜索,本文针对搜索权重做了优化设计。假设PS算法开展迭代计算的频次为d,允许迭代计算的最高频次为dH。为了实现随迭代计算频次的持续增加,搜索权重曲线的斜率下降幅度有所减慢,将部署算法搜索权重设计为:

I=0.5d/dH-0.2.

(5)

(6)

粒子移动后的新的方位矢量为:

(7)

公式(6)和公式(7)的优势在于通过优化算法在粒子求解空间的搜索权重,进一步强化迭代计算值在局部范围内的自适应性,以提升算法在局部范围内的最优适应解的搜索能力。

(8)

同时引入适应度标准差A,用于评估PS算法迭代计算出来的值是否逼近于最优解。

(9)

若评估出来的适应度标准差的值较小,则表示PS算法收敛出来的值逼近于全局最优适应解和局部最优适应解。当适应度标准差的值为0时,判断当前迭代频次是否小于允许的最高迭代计算频次。若是,则启动变异操作,即根据公式(6)和公式(7)更新粒子的方位矢量和搜索速度,再次开展计算得出该粒子的个体历史最优适应值;反之,则无需启动变异操作。

3 算法部署

在PS算法基础上引入搜索权重自适应调整机制,并借鉴遗传算法变异处理机制科学地开展QoS级自适应粒子群求解计算。通过频繁迭代计算出来的全局历史最优适应解,可视为感知节点在感知网络范围内的最佳方位部署方案。优化后的算法实施流程如图1所示。

图1 ANC算法流程图

4 算法测试

本文构思的ANC算法是由PS算法优化而来,故在算法测试环节将ANC算法的测试数据与PS算法展开对比。测试前首先在MATLAB平台构建一个边长为200 m的正方形区域作为感知网络的模拟环境,并投放80个传感器和30个粒子。其中,传感器节点所能感知的半径范围在4 m至12 m之间,粒子突变概率设为0.01,且粒子开展迭代计算的最高频次为600。然后在传感器感知半径范围内,通过调整传感器数量及感知半径大小来收集测试数据,并对比两种算法方案下粒子解的普适性。进而验证ANC算法覆盖的服务成效[9]。

根据算法模型可知,感知节点的网络覆盖程度高低与感知节点自身感知范围大小成正比,即当感知节点的感知半径扩大时,全网覆盖率必然提升。基于此,第一组实验引入80个传感器作为感知节点,通过逐步扩大传感器感知范围来考察两种算法下的网络覆盖性能。观察图2曲线走势可知,随着传感器感知半径的扩大,两种算法下的网络覆盖率均有不同程度提升,尤其在扩大感知半径的初期,两条曲线斜率均线性递增,这表明两种算法的覆盖优势均得到发挥。但随着感知半径进一步扩大,PS算法曲线的斜率持续走低,增量逐渐减少,这意味着PS算法的覆盖率接近于极限。相反,ANC算法由于在粒子搜索权重设计方面引入了优化机制,在本组覆盖率测试中算法曲线斜率依然表现出良好的线性递增趋势,且与PS算法曲线走势形成鲜明对比。

图2 感知半径对覆盖率的影响力 图3 感知节点数量对覆盖率的影响力

第二组实验主要考察传感器节点数量的变化对覆盖率的影响力,实验结果如图3所示。从两条算法曲线走势不难看出,传感器数量可在一定程度上助力提升覆盖率。在传感器数量递增初期,由于传感器节点数量不多,ANC算法优势未能得到发挥,所以未表现出明显的相对优势。随着传感器数量增至50个,两种算法下的网络覆盖指标开始出现差异,ANC算法下的覆盖率曲线持续走高,相比之下PS算法曲线的覆盖率曲线走势有所减缓。这是由于在设计ANC算法时为粒子个体引入了目标适应值这一考察指标,该指标有助于确保粒子解兼顾局部普适性和全局自适应性,这是PS算法所不具备的优势。因此根据ANC算法计算得到的粒子解来部署传感器的方位,可具备更有效的感知性能和覆盖能力。因此,在传感器节点数量较多的复杂环境下,ANC算法覆盖优势越得到发挥,越能表现出差异化优势。

从上述两个实验结果可知,通过优化设计搜索权重和引入基因突变处理机制的ANC算法,在复杂感知环境中能够科学地保障粒子解同时具备全网普适性和局部网络普适性,从而使该算法在实验中表现出了良好的科学性。

5 结语

本文从普适性出发总结了传统PS算法在粒子空间内搜索解的过程中存在的问题,提出了优化的迭代计算机制和粒子解的评估机制。该机制主要通过自适应重置粒子搜索权重和普适性目标函数来解决传统PS算法在求解空间内的收敛瓶颈。将针对传统PS算法提出的两个优化机制进行实验测试,结果表明,本文算法具备良好的覆盖成效。