粒子群APIS-3D算法在三维传感网络中的定位研究

李 锋

(广东交通职业技术学院计算机工程学院 广东 广州 510650)

粒子群APIS-3D算法在三维传感网络中的定位研究

李 锋

(广东交通职业技术学院计算机工程学院 广东 广州 510650)

无线传感网络三维空间定位算法大都是将二维向量转化为三维空间，其原理与平面定位基本相同，实现简单，没有考虑节点移动对定位偏差的影响。提出一种基于粒子群APIS-3D定位算法，利用粒子模拟节点移动状态，并根据RSSI信号指纹的动态反馈过程建立适应度函数，通过定位球体交集区域重心以计算节点坐标。仿真实验证明，新算法在保持抽样概率不变情况下，对移动节点平均定位偏差在2.42%以内，能很好满足工程应用要求。

无线传感网络 三维定位 APIS-3D RSSI

0 引 言

无线传感网络是一种由大量传感节点构成的分布式网络系统。由于传感节点采集到的信息通常与其自身位置相关，因此对节点定位是无线传感网络首要解决的基础问题。在实际工程中，传感器往往会随机空投至三维区域，如对高地森林、海洋湖泊和太空的观测等，并会随洋流和空间的变化而移动。对三维空间移动节点定位成为无线传感网络研究的难点和热点。

与二维平面相比，三维空间节点定位更为复杂，定位精准度和稳定性亟待提高。其中3D DV-Hop算法、3D DV-Distance算法和3D Centorid算法只是简单地将二维向量转化为三维空间，其原理与二维平面定位基本相同，算法简单，但定位精度较低[1,2]。基于球壳交集的APIS定位算法以节点为球心，以邻居节点距离为半径，将三维空间划分成不同大小的同心球体，通过判断定位节点是否在球体区域并计算区域重心以定位节点坐标，定位精确程度与其邻居节点位置相关。Landscape 3D算法通过接收邻居节点位置信息和RSSI指纹转换为参考距离完成节点定位。受环境影响较大，定位稳定性不高[3]。APIS-3D算法结合APIS和Landscape 3D两者思想[4]，通过交换邻居节点位置信息并根据RSSI接收信号强度计算邻居节点参考距离，然后将周边区域划分成多个互相重叠的球体，根据判断节点位于哪个球体内部和利用穷尽组合方式计算球体交集区域重心实现节点定位，算法复杂，但定位精度较高，对环境依赖程度较小，见图1所示。

图1 APIS-3D 节点定位图

然而，上述三维空间定位过程都没有考虑到节点移动问题，在实际工程中传感节点往往会因洋流和空气对流影响而漂移。邻居之间交换的RSSI信号指纹是一个动态变化过程。假如算法利用RSSI信号指纹形成动态反馈机制，不仅可以适应节点位置变化，减少对节点密度依赖程度，还可以有效提高定位精准度和标识移动轨迹。因此本文提出一种基于粒子群的APIS-3D 定位算法，利用粒子模拟节点移动状态，并根据RSSI信号指纹的动态反馈过程建立适应度函数，发挥粒子群快速收敛优势找出四个邻居节点向量，最后通过定位球体交集区域重心以计算节点坐标。

1 标准粒子群算法

粒子群PSO算法是基于鸟类群体觅食行为研究的模拟算法。在封闭空间中，鸟群随机搜索食物，假如所有的鸟都知道当前位置与食物节点之间距离，找到全局最优解的方法则可以转换为从其最近的鸟周围区域方向搜寻[5，6]。在标准粒子群算法中，搜索空间的每只鸟对应寻找全局最优的每个解，称为粒子，每个粒子的初始状态代表鸟的当前位置和飞行速度。每个粒子通过搜寻附近粒子最优信息以改变当前位置和方向，直到找出全局最优解。算法思想如下：

在一个d维搜索空间，存在由n个粒子组成的粒子群X[7-9]，X=(X1，X2，…，Xn)T。定义第i个粒子位置信息为Xi=(Xi1，Xi2，…，Xid)T，速率为Vi=(Vi1，Vi2，…，Vid)T，第i个粒子的极值为Pi=(Pi1，Pi2，…，Pid)T，粒子群全局极值为Pg=(Pg1，Pg2，…，Pgd)T，则每个粒子以全局最优解出发，按式(1)-式(3)更新当前位置和速度：

(1)

(2)

(3)

2 粒子群算法在节点定位中的作用

2.1 初始化节点和搜索空间

在RSSI指纹信号定位中，粒子群中的每个粒子代表传感网络中的每个节点，定义由n个粒子组成的粒子群X，X=(X1，X2，…，Xn)T，令第i个粒子位置信息为Xi=(Xi1，Xi2，…，Xid)T，速率是Vi=(Vi1，Vi2，…，Vid)T，第i个粒子极值为Pi=(Pi1，Pi2，…，Pid)T，例子种群全局极值是Pg=(Pg1，Pg2，…，Pgd)T。

定义与目的节点相邻的四个特征节点向量A(xa,ya,za)、B(xb,yb,zb)、C(xc,yc,zc)和D(xd,yd,zd)。初始化搜索空间与粒子状态，选出最小值和最大值构成矩形搜索边界区域，边界点分别为T1(xmin,ymin,zmin)、 T2(xmax,ymin,zmin)、T3(xmin,ymax,zmin)、T4(xmax,ymax,zmin)、T5(xmin,ymax,zmax)、T6(xmax,ymin,zmax)、T7(xmin,ymax,zmax)、T8(xmax,ymax,zmax)。粒子将在此该闭空间按照适应度大小迭代搜索四个特征向量。

2.2 构建适应度函数

搜集邻居之间交换的RSSI动态信号指纹形成反馈机制以建立适应度评价函数，其中RSSI信号传播损耗模型公式为：

(4)

其中RSSI(d)为距离源节点d处接收到的信号强度，RSSI(d0)为距离d0处测得的信号强度，β为路径衰减指数，Xδ为标准偏差为δ的正态随机变量。

建立适应度函数是为了迭代搜索特征向量坐标，寻找四个邻居节点特征向量的过程通过PSO算法转变为求解与目的节点距离最小的方程组近优解。适应度函数为：

(z-zi)2-dn2)]

(5)

每个粒子找到下一粒子后按式(1)-式(3)更新当前位置和速率，从而找出全局四个近优解。粒子群搜索空间和位置更新过程见图2所示。

图2 粒子搜索空间和位置更新图

2.3PSO算法流程

(1) 初始化粒子种群和搜索空间，定义惯性权重W和最大迭代次数m；

(2) 根据式(5)适应度评价函数计算当前每个粒子适应值；

(3) 更新个体最优值点和全局最优点。对每个粒子而言，比较下一位置点的适应值Fi和当前最优值Pibest，如果Fi< Pibest,则更新Pibest；

(4) 计算当前Fi适应度值Fibest，如果Fibest

(5) 判定是否满足结束条件，若超出迭代次数m或者Fgbest小于阈值δ，则计算特征点向量坐标，算法终止，否则返回步骤(2)。

3 定位过程

3.1 特征点都在同心球体区域的定位过程

(6)

由lAB和lAC可求出内切圆O1圆心S1，其坐标为：

(7)

内切圆O2圆心S2坐标为：

(8)

(9)

(10)

取直线l1与l2交点计算球心坐标，定位节点位置：

(11)

图3 相同球体区域节点定位图

3.2 特征点在不同球体区域的定位过程

(12)

目的节点S在球S1、S2和S3交集区域重心，则S在平面N1与N2的交线l上，由式(11)求出交线l方向向量为：

(xd-xc,yd-yc,zd-zc)=(i,j,k)

(13)

其中，i、j、k是直线l的方向向量。

令直线l上任意一点p坐标为(xp,yp,zp)，代入式(13)得出直线l对称方程：

(14)

则经过点p并且垂直于直线l的平面Nr(r=1,2,3)为：

Nr:i(x-xp)+j(y-yp)+k(z-zp)=0

(15)

计算三个平面交点区域重心坐标:

(16)

图4 不同球体区域节点定位图

4 仿真测试

4.1 测试环境

仿真环境设为100×100×100三维空间，未知节点数量200，锚节点数量20，其中锚节点统一均匀放置，其他节点随机放置，节点通信半径为10m，初始化粒子群规模300，最大迭代次数m=500。

4.2 静止节点定位误差比较

新算法和APIS-3D算法定位误差见图5所示。在APIS-3D算法中，节点定位最大误差0.771米，平均定位误差0.306米，定位比例为98.381%。新算法节点定位最大误差0.427米，平均定位误差0.162米，定位比例为99.57%。由于节点静止，PSO适应度函数的动态反馈机制得不到有效发挥，两者定位结果差别不大，但新算法更为精确。

图5 静止节点定位误差图

4.3 移动节点定位误差比较

对200节点在[0,5]区间内随机初始化移动速度，平均定位误差评价公式为：

(17)

测试结果见图6所示。其中三角形表示节点物理位置，圆圈表示APIS-3D估算位置，星号是新算法估算位置。从图中可以看出，APIS-3D算法对移动节点定位不理想，节点移动对定位结果产生较大影响，平均偏差达5.316%。而新算法在保持抽样概率不变的情况下，通过适应度函数动态反馈机制更新粒子当前位置和速率，快速收敛找到全局近优解计算节点坐标，平均偏差为2.42%。新算法对移动节点定位优势明显。

图6 移动节点定位误差图

5 结 语

本文提出一种基于粒子群APIS-3D定位算法，能有效发挥粒子群正向反馈和快速收敛优势定位节点坐标。下一步工作将计算和仿真节点运动轨迹，并对算法收敛性进行细致分析，从而提高算法性能，降低节点功耗。

[1] 张荣磊,刘琳岚,舒坚,等.基于多维定标的无线传感器网络三维定位算法[J].计算机应用研究，2009,26(8):3100-3104.

[2] 朱红霞,陈曙.一种新的基于非测距的无线传感器网络三维定位算法[J].传感技术学报，2009,22(11):1655-1660.

[3] 金卫民,神显豪.基于RSSI的室外无线传感网络自定位算法[J].计算机工程,2008,34(13):89-91.

[4] 吕良彬，曹阳，高洵，等.基于球壳交集的传感器网络三维定位算法[J].北京邮电大学学报,2006,29(Sup.):48-51.

[5]HeT,HuangCD,BlumBM,etal.Range-freelocaliza-tionschemesforlargescalesensornetworks[C]//Proceedingsofthe9thAnnualInternationalConferenceonMobileComputingandNetworking，2003:81-95.

[6]GaneriwalS,KumarR,SrivastavaMB.Timing-SyncProtocolforSensorNetwork[C]//Proceedingsofthe1stinternationalconferenceonEmbeddednetworkedsensorsystems，2003:138-149.

[7]PoJenChuang,ChengPeiWu.AnEffectivePSO-BasedNodeLocalizationSchemeforWirelessSensorNetworks[C]//the2008NinthInternationalConferenceononParallelandDistributedComputing,ApplicationsandTechnologies，2008:187-194.

[8]SzynkiewiczEN,MarksM.OptimizationSchemesforWirelessSensorNetworksLocalization[J].InternationalJournalofAppliedMathematicsandComputerScience，2009,19(2):291-302.

[9]DenisB,PierrotJB,RjeilyCA.JointdistributedsynchronizationandpositioninginUWBAdhocnetworksusingTOA[J].IEEETransactionsonMicrowaveTheoryandTechniques，2006,54(4):1896-1911.

RESEARCH ON LOCATION OF PSO AND APIS-3D ALGORITHM IN 3D WSN

Li Feng

(SchoolofComputerEngineering,GuangdongCommunicationPolytechnic,Guangzhou510650,Guangdong,China)

3D space location algorithms of wireless sensor networks are mostly to convert the 2D vector into 3D space,its principle is basically the same as plane location and is simple in implementation,but does not consider the impact of node mobility on location errors.This paper puts forward a new PSO and APIS-3D-based location algorithm,it uses particles to simulate node mobility status, sets up fitness function according to the dynamic feedback process of RSSI signal fingerprint, and calculates the coordinate of nodes by locating the centre of gravity of sphere intersection region.Simulation experimental results show that the new algorithm achieves the average location error less than 2.42% on mobile nodes under the condition of keeping the sampling probability unchanged,and can well meet the requirements of engineering applications.

Wireless sensor networks 3D location APIS-3D RSSI

2015-07-21。全国交通运输职业教育教学指导委员会2015年交通运输职业教育科研项目(2015B21)；广东省高等职业技术教育研究会重点课题(GDGZ15Z007)；中国交通教育研究会教育科学研究课题(1402-136)。。李锋，讲师，主研领域：计算机系统结构和网络安全。

TP393

A

10.3969/j.issn.1000-386x.2017.03.059