一种无线传感器网络二维目标覆盖的改进方法

卢 毅，周 杰，万连城

(1. 石河子大学 信息科学与技术学院，新疆维吾尔自治区 石河子 832003；2. 西安电子科技大学 期刊中心，陕西 西安 710071)

随着技术的进步，无线传感器网络越来越多地被用于工业、农业、国防和教育等社会经济发展的方方面面[1-5]。目标覆盖是无线传感器网络部署过程中的一个关键问题，近年来吸引了许多研究人员和研究团队的关注[6-8]。通过合理的设置无线传感器的监测目标，可以有效增加监测水平，提升检出的目标数[9-14]。

目标覆盖直接决定了无线传感器网络对区域内目标的监测能力。因为无线传感器网络的覆盖类别较多，包括定点设置和空中撒布等，在覆盖过程中不但需要考虑怎样借助位置优化完成传感器的目标监测，还要考虑目标被多少个传感器同时监测才能够完成任务。在监测范围为二维平面的无线传感器网络中，目标覆盖率是无线传感器网络中的一个关键指标，直接影响到对目标的监测效果。由于传感器节点的监测范围有限，每个传感器通常只能覆盖一定范围内的有限个目标，整个网络中的所有节点需要协同完成目标覆盖任务。如何提高无线传感器网络的有效监测的目标数，保证对目标的监测效果，是二维目标覆盖中的一个关键问题。

针对无线传感器网络目标覆盖问题，文献[15]给出了一种动态规划算法，但并没有针对被监测目标进行选择。文献[16]给出了一种混合遗传算法，能够有效避免节点布置中的路径暴露问题，但给出的混合遗传算法容易陷入进化停滞，导致得到的解集质量较低。文献[17]给出了一种蚁群算法，能够有效降低网络能耗，但蚁群算法很容易迭代停滞。

笔者给出了一种基于量子退火算法，并与粒子群算法、蚁群算法进行了仿真比较。仿真结果显示，提出的量子退火算法能够有效解决二维目标覆盖问题，检出的目标数较粒子群算法、蚁群算法有较大提高。

1 二维目标覆盖问题的系统模型

拥有N个传感器节点和M个被监测目标的二维无线传感器网络模型用矩阵R可表示为

(1)

在矩阵R中，rm,n为第m个目标和第n个节点的覆盖关系，rm,n为1表明被覆盖。目标监测矩阵L可表示为

(2)

lm,n=1，表示第m个被监测目标被第n个传感器节点监测。二维目标覆盖问题的数学模型可以用如下的方程组来表示：

(3)

s.t.lm,n≤rm,n,

(4)

(5)

式(3)中，目标函数fit表示最大化检出目标数，检出目标至少被G个节点监测。式(4)表示监测不能超过覆盖范围，式(5)表示由于每个节点能力有限，最多只能选择H个目标进行监测。

2 基于量子退火算法的无线传感器网络二维目标覆盖

2.1 解集的量子位编码

在大规模无线传感器网络中，感知节点数和目标数量较多。为了能够进行多点并行搜索和分布式计算，量子退火算法的解集中包含多个量子位编码形式的解。在传统的进化算法中，解通常被表示成一个确定的二进制字符串，即只能代表解空间中的某个固定状态。在量子退火算法的解集中，每个解包含多个量子位，每个量子位可以处于|0〉态、|1〉态或|0〉和|1〉态之间的叠加态。如果解的长度为s，则每个解能够同时表示2s个状态。在量子退火算法中，每个量子位状态可以表示为

|ψ〉=α|0〉+β|1〉 。

(6)

式(6)表示如果需要对系统的状态进行观测，系统将坍缩为一个确定的状态。当对量子态进行测量时，|0〉态被观测到的概率是|α|2，|1〉态被观测到的概率为|β|2，两者满足的归一化条件为

|α|2+|β|2=1 。

(7)

(8)

其中，t代表退火温度；j代表解在解集中的序号；M×N代表解中的量子位个数，分别对应如式(2)所示的目标监测矩阵L中的M×N个元素{l1,1,l1,2,…,lM,N}。

2.2 初始解集的生成

为了保证生成解的均匀随机性，量子退火中每个量子位上对应态|0〉和态|1〉的概率幅度χk+1由Chebyshev混沌映射生成，可表示为

χk+1=cos(φarccosχk),k=0,1,…,M×N,

(9)

其中，φ为Chebyshev混沌映射的阶数，当φ>2时，映射具有正的李雅普诺夫(Lyapunov)指数，能够生成随机的混沌序列，在文中取φ=6。在生成初始解集的过程中，首先需要选择一个(-1,1)之间的随机数作为初始值χ0，以保证随机性。在文中，Chebyshev混沌映射的初始值χ0=0.9。然后，按照式(9)所示的迭代方式生成余下的M×N个初始化值，并按如下公式完成量子位的初始化：

(10)

2.3 量子位状态的测量

(11)

2.4 目标函数值的计算

lm,n=z(m-1)×N+n，m=1,2,…,M,n=1,2,…,N。

(12)

在二维目标覆盖问题中，优化目标为最大化检出的目标数。将式(2)中的矩阵L根据规则式(12)替换矩阵Z的形式，则目标函数可表示为

(13)

在计算目标函数值时，首先验证生成的解是否满足约束条件式(4)和式(5)。如果不满足约束条件，则应当运用贪婪算法等方式对矩阵Z中元素进行相应调整，使之符合两个约束条件。

2.5 解集的量子旋转门更新

(14)

表1 量子旋转门中旋转角查询表

在表1中，φ为量子旋转门中旋转角与当前温度值的比例参数，文中取参数φ=0.000 1π/℃。

3 仿真及结果分析

仿真中设置传感器及目标随机分布在600 m×600 m的范围内，每个节点最多可以监测5个目标，而单个目标需要被3个节点监测。量子退火算法的初温为600 ℃，退火系数设置为0.8。粒子群算法和蚁群算法中个体数目均设置为50，算法重复次数为100。

图1为节点感知半径为80 m时获得的单次运行仿真结果。从图1可以看出，蚁群算法的运行陷入了早熟收敛，导致最终检出的目标数不高。粒子群算法比蚁群算法稍好，但迭代后不久即出现进化停滞现象，导致检出的目标数较低。量子退火算法根据Metropolis规则动态调整旋转角方向，避免了进化停滞问题，在50次迭代后就寻找到了较优解，相比其他两种方法有效地提高了检出的目标数，增强了监测效果。

图2为在传感器节点数为200时，不同半径的情况下，粒子群算法、蚁群算法和量子退火算法目标检出率随待检测目标数的变化曲线图，仿真结果为50次运行的均值。如图2所示，蚁群算法由于未动态调整参数，收敛较慢，导致检出率较低。粒子群算法的运行结果优于蚁群算法的，但由于存在进化停滞现象，导致最终的检出率少于量子退火算法的。量子退火算法相比其他两种启发式算法有效地提高了目标检出率，增强了无线传感器网络的监测效果。

4 结束语

文中提出了一种量子退火算法来解决二维目标覆盖问题，设计了相应的系统模型，并给出了二维目标覆盖优化的目标函数。针对二维目标覆盖问题，将基于量子退火算法的方法与粒子群算法、蚁群算法进行了仿真比较。仿真结果显示，提出的量子退火算法能够有效解决二维目标覆盖问题，检出的目标数较粒子群算法、蚁群算法有较大提高。