刘 小 园

(罗定职业技术学院　广东 罗定 527200)

0　引　言

无线传感网络定位算法有基于测距的三边测量法、三角测量法、极大似然估计法和基于非测距的DV-HoP算法、质心算法、近似三角形内点测试法等,这类算法主要针对二维区域节点定位。在实际工程应用中，传感节点往往随机空投至三维空间，如森林，海洋，高山等。如何在立体空间实现对传感节点的精确定位是目前研究的热点和重点[1]。

Emmons提出一种3D-DVHoP算法，其原理与传统DV-HoP算法相似。首先利用最短通路计算三维区域中各锚节点之间最小跳数，再根据实际距离计算平均每跳长度，将实际跳数与平均跳距相乘得到与附近锚节点之间距离，最后利用四边测量或极大似然估计法计算节点三维坐标。

3D-DVHoP算法将传统的二维区域拓展至立体空间，为节点三维定位提出算法模型。其和传统DV-HoP算法类似，根据网络连通情况使用跳数作为参考距离，实现简单，硬件成本较低，能很好地兼容现有设备。但其定位精度依赖于具体的网络拓扑，当锚节点分布不均时会产生较大定位偏差。因为在三维空间中，非相邻锚节点之间通路并非直线，通过相邻节点之间接力会导致“绕弯”现象[2]，再利用两点弯线跳段替代直通距离势必带来定位偏差，并且在三维空间中表现更为明显。如图1所示。

图1　“绕弯”现象示意图

由于节点绕弯现象无法避免[3-4]，为提高定位精度，业界提出各类改进的3D-DVHoP算法，如基于多重共线性的三维DVHoP定位算法[5]、基于加权的三维DVHoP算法[6]、基于粒子群优化的三维DVHoP算法等[7]，但这类优化算法都容易陷入局部最优解现象[8]，定位精度虽有提高，但在25th、50th和70th定位偏差均在3%以上[9]，难以满足工程应用需求。

有鉴于此，本文提出一种基于量子粒子群改进算法。在寻找邻居节点之间的实际距离与绕弯距离最小误差时，利用3D-DVHoP算法结合量子旋转门变异规则，计算距离矩阵和跳数矩阵函数评价粒子群个体行为。通过交叉变异修正个体粒子速率和状态，增加粒子搜索的广泛性和遍历性,避免粒子陷入盲目搜索和局部最优， 从而导致算法搜索停滞或提前收敛现象。

1　量子粒子群算法

量子粒子群算法是将量子进化算法融合到粒子群中产生的一种新算法[10]。算法中个体粒子位置通过量子比特进行编码，利用量子旋转门更新粒子位置向量和移动速率。在粒子群中，每个粒子代表搜索空间中的每个解。在量子粒子群中，量子旋转门通过量子粒子移位实现对搜索空间中两个位置的同时移动。因此一个量子粒子对应于搜索空间中的两个解，以此釆增加粒子搜索的广泛性和遍历性，提高算法优化效率，避免陷入局部最优现象。

2　3D-DVHoP算法原理

3D-DVHoP算法定位过程分为三个阶段。第一阶段，锚节点向邻居节点广播分组信息，包含自身位置坐标、ID以及跳数字段，获得网路中其他锚节点位置信息和跳数距离，从而估算平均跳离，见式(1)：

(1)

第二阶段，锚节点将平均跳距加入自身分组信息，再次洪泛至整个网络，并计算其与所有锚节点之间的参考跳距。

第三阶段，根据与其他锚节点的参考距离，利用四边测量或极大似然估计法计算节点的三维坐标。

在立体空间中，设未知节点M(x,y,z)附近存在n个锚节点，坐标分别为(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn),与节点M之间距离分别d1,d2,…,dn。如图2所示。

图2　节点空间拓扑图

根据式(1)计算未知节点M与其他锚节点之间参考距离：

(2)

将式(2)中方程组每一行分别减去第n行，并改成“AX=b”线性表达式，其中：

(3)

最后根据最小方差估计法计算节点M三维坐标:

(4)

3　优化算法思想和定位过程

3.1　粒子群优化算法和不足

要寻找目的节点与邻居锚节点之间实际距离与估算绕弯距离的最小误差，根据式(4)可以转换为函数最优化问题。在粒子群算法中，每个粒子位置代表函数优化的每个可行解，粒子根据目标函数修正当前位置和飞行方向，找出全局最优解，完成搜索过程。然而，粒子群算法是一个正向反馈的过程，当局部信息过优时容易产生大量粒子聚集导致算法提早收敛，陷入局部最优的问题。另外，惯性权重W为(0,1)之间随机数，使得算法早期粒子速度更新没有规律，后期收敛缓慢。因此利用单纯的粒子群优化求解效果不佳，定位精度有待提高。

3.2　建立目标函数

新算法基于3D-DVHoP第三阶段获得的距离矩阵和跳数矩阵，采用量子粒子群算法修正节点估算距离以减少偏差，提高定位精度。为更好地描述量子粒子群算法节点部署，找到实际距离与估算绕弯距离之间的最小误差，建立优化目标函数为:

(5)

其中，ci是传感网络节点路径成本，C为监测区域部署的传感器路径成本。

3.3　算法定位过程

新算法首先对粒子群进行量子编码，利用量子旋转门调整个体粒子速率和方向从而确定搜索空间，避免粒子过早收敛造成局部最优。为得到目标函数最优解，需要确定量子旋转门变异规则和适应度函数(适应度函数是与3D-DVHoP算法中得到的距离矩阵和跳数矩阵相关的函数)以评价粒子群个体行为，得到寻优群体。最后通过粒子群迭代优化寻找到目标函数的最优解，从而修正节点最优坐标值。新算法具体流程如下：

第二步确定粒子位置状态。在一个n维搜索空间，有m个粒子(表示目标函数的可能解)组成的群体，其中在t时刻第i个粒子位置为：

Xi(t)=⎣xi,1(t),xi,2(t),…,xi,n(t)」

(6)

在t时刻粒子最好个体位置为：

Pi(t)=⎣Pi,1(t),Pi,2(t),…,Pi,n(t)」

(7)

整个粒子群最好全局位置为：

G(t)=⎣G1(t),G2(t),…,Gn(t)」

(8)

第三步对粒子群进行量子化编码。定义量子比特，其状态可为:

|τ〉=αij|0〉+βij|1〉

(9)

(10)

其中，αij,βij表示为种群中所有染色体基因。

第四步建立适应度函数评价个体粒子行为状态。适应度函数值越小，表示适应度越好。适应度评价函数为：

(11)

其中，Dij为传感网络中相邻节点i与j之间真实距离，dij是相邻节点i与j之间估算的参考距离;djk是相邻节点j与k之间估算的参考距离。由式(10)得到粒子i最好个体位置为：

(12)

整个粒子群最好全局位置为：

g=argmin{f[Pi(t)]}

G(t)=Pg(t)

(13)

第五步计算个体粒子位置。将粒子个体最佳位置和整个粒子群体最佳全局位置进行比较，从而更新个体粒子位置：

Xi,j(t+1)=pi,j(t)+|Cj(t)-|Xi,j(t)

(14)

其中：

(15)

第六步利用量子旋转门修正个体粒子速率和状态，避免陷入局部最优。定义量子旋转门U(θ)，利用量子旋转门不同旋转角度对量子染色体实施变异操作，并对个体粒子行为状态进行修正。令：

(16)

(17)

重复第五步和第六步，粒子通过判断群体最佳全局位置，结合量子旋转门的变异操作不断更新当前位置和飞行速率，最终找到全局最优解，完成搜索过程，根据目标函数寻找到未知节点与锚节点之间实际距离与估算绕弯距离的最小误差。

第七步根据3D-DVHoP算法，利用最小方差计算节点M三维坐标。

3.4　定位偏差评价方式

算法采用平均定位偏差对三维节点定位精度进行评价，公式为：

(18)

4　仿真测试

4.1　仿真环境

仿真环境采用基于网格节点放置模型，节点在100×100×100三维区域内随机分布，未知节点数量70，锚节点数量30，节点通信半径20，初始化粒子群规模200，加速系数c1=1，c2=1，最大迭代次数k=800，利用MATLAB7.0软件对算法仿真比较。

4.2　三维定位偏差测试

三维空间中新算法与3D-DVHoP经典算法定位偏差见图3所示。由于锚节点非均匀分布，3D-DVHoP在计算平均跳距时会产生误差，并且锚节点密度越小，定位偏差越大。图3中某些区域锚节点密度较低，3D-DVHoP计算的最大偏差高达23.87%。新算法利用量子粒子群寻找实际距离与估算距离之间的最小误差值，从而修正定位结果，平均定位偏差明显小于3D-DVHoP算法。

图3　定位偏差测试图

4.3　节点密度定位偏差测试

锚节点密度与定位偏差测试结果见图4所示。所有优化算法定位偏差都随节点密度增大而减小，满足共性规律，但当锚节点数量小于40时算法差异明显。其中3D-DVHoP直接将弯线跳段距离替代直通距离，算法定位偏差最大。基于多重共线性的三维DVHoP定位算法、基于加权的三维DVHoP算法和基于粒子群优化的三维DVHoP算法，采用不同技术修正非相邻节点之间的“绕弯”误差，但找到的解并非全局最优解，陷入局部最优问题。新算法平均定位偏差最小，当节点数量大于55时偏差趋于收敛，在25th、50th和70th距离偏差值分别是1.25米、0.6米和0.5米，均在1.5%以内。

图4　节点密度定位偏差测试图

5　结　语

3D-DVHoP在三维空间利用弯线跳段距离替代直通距离，因节点“绕弯”现象导致较大定位偏差，已有改进算法在修正偏差时已无法找到全局最优解，或多或少的存在算法提前收敛现象。本文提出一种基于量子粒子群改进算法，通过判断粒子群体最佳全局位置和量子旋转门变异操作修正个体粒子速率和状态，找出节点实际距离与估算绕弯距离之间的最小误差以提高定位精度，算法相对复杂，但定位结果更为精确。

[1] 曾子维,张超.一种质心与DV-Hop算法相结合的WSN节点定位算法[J].计算机应用与软件,2015,32(11):130-133.

[2] 刘士兴,黄俊杰,刘宏银,等.基于多通信半径的加权DV-Hop定位算法[J].传感技术学报,2015,28(6):883-887.

[3] 涂巧铃,牟小燕,宋佳.一种改进的DV-Hop改进算法[J].重庆理工大学学报(自然科学版),2014,28(11):84-88.

[4] 高文根,陈其工,江明,等.基于距离补偿模型的改进DV-Hop定位算法[J].计算机工程,2015,41(3):32-36.

[5] 刘文远,王恩爽,陈子军.无线传感器网络中DV-Hop定位算法的改进[J].小型微型计算机系统,2011,32(6):1071-1074.

[6] 陈三风,陈万明.基于RSSI误差分析的无线传感器网络定位研究[J].计算机工程与应用,2011,47(14):10-12,75.

[7] 沈军,黄春华,罗护,等.基于RSSI优化的模型参数实时估计定位算法[J].计算机工程与设计,2012,33(2):464-468.

[8] Chen H,Sezaki K,Deng P,et al.An improved DV-Hop localization algorithm with reduced node location error for wireless sensor networks[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Science,2008,E91-A(8):2232-2236.

[9] Savarese C,Rabaey J M,Langendoen K.Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks[C]//Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference,2002:317-327.

[10] Sun G,Qiao G,Xu B.Corrosion monitoring sensor networks with energy harvesting[J].IEEE Sensors Journal,2011,11(6):1476-1477.