引入虚拟节点的无线传感器网络ELM定位算法*
2018-04-09刘国繁赵天霓
刘国繁， 赵天霓
(1.湖南工程学院 电气信息学院，湖南 湘潭 411104；2.湘潭大学 信息工程学院，湖南 湘潭 411105)
0 引 言
无线传感器网络节点自身位置信息的获取是大多数应用的基础，节点定位技术是无线传感器网络的关键支撑技术。依据是否测量距离，定位算法可划分为基于测距的算法和非测距的算法[1]。前者[2]对距离进行直接测量，通常定位精度相对较高，但节点需要额外硬件的支持，并且定位过程会消耗大量的能量。非测距算法[3]则依靠网络连通度等信息即可计算未知节点的位置，对节点的硬件要求小。
反向传播(back propagation,BP)定位算法是将BP神经网络用于节点定位的一类算法，但传统BP神经网络需要人为设置大量训练参数，存在训练速度慢并且容易陷入局部最优解等问题。极限学习机(extreme learning machine，ELM)的输入权值和隐含层阈值均随机产生，仅需要设置网络的隐含层节点个数，即可产生唯一最优解，并且无需迭代，因而学习速度快，具有良好的泛化性能[4～6]。将ELM应用于节点定位可有效避免BP定位算法存在的问题，改善定位性能。
现有的定位算法均表明，锚节点比例越高，定位的精度越高[3]，但是锚节点的增多会使无线传感器网络的成本增加。引入虚拟节点[7～9]及次锚节点[10,11]等于虚拟地增加锚节点比例，在不增加硬件成本情况下，提高了无线传感器网络节点定位精度。本文将ELM用于无线传感器网络的节点定位，引入虚拟节点进一步提高定位精度，仿真结果表明：使用ELM定位具有较小的定位误差，且结合虚拟节点可进一步减小定位误差。
1 基于ELM的定位算法
1.1 ELM
对于N个样本数组(xi,ti),xi=[xi1,xi2,...,xin]T∈Rn,ti=[ti1,ti2,...,tim]T∈Rm,隐含层节点数为L，激活函数为g(x),ELM模型可表示为
(1)
式中wj=[wj1,wj2,…,wjn]T为连接输入节点与第j个隐含层节点的权值向量；βj为连接第j个隐含层节点与输出节点间的权值向量；bj为第j个隐含层节点的阈值；g(wjxi+bj)是在输入为xi时第j个隐含层节点的输出。SLFNs模型能以零误差逼近这N个样本，上述N个等式可以写为
(2)
式中H为隐含层输出矩阵，H的第i列为第i个隐含层的节点对应于输入x1,x2,…,xN的输出。求解式(2)，可以得到网络参数为
β=H*T=(HTH)-1HTT
(3)
式中H*为隐含层输出矩阵H的Moore-Penrose广义逆。
1.2 最小跳数获取
每个锚节点将自己的位置坐标、自身ID信息、跳数(初值为0) 作为一个数据包发送给通信半径内的邻居节点。邻居节点接收数据包后,记录下到锚节点的跳数,当接收到来自同一个锚节点的多个跳数信息时，删除较大的跳数信息，保存最小的跳数信息，跳数值加1继续转发至邻居节点。网络中的所有节点(包括锚节点)记录了距每个锚节点间的最小跳数。
1.3 ELM估算节点位置
设Si=(xi,yi)表示第i个节点的坐标(位置)。Bi=[bi1,bi2,…,bim,…,biM]为各个锚节点间的最小跳数，bim为第i个锚节点与第m个锚节点间最小跳数，i=1,2,…,M，m=1,2,…,M，当i=m，有bim=0。Bj=[bj1,bj2,…,bjm,…,bjM]为各未知节点到各锚节点之间的最小跳数，bjm为第j个未知节点与第m个锚节点间最小跳数，j=M+1,M+2,…,N，m=1,2,…,M。则估算步骤为：
1)无线传感器网络中随机放置N个节点，其中前M个为锚节点，剩余N-M个为未知节点。锚节点向周围邻居节点发送坐标、ID、跳数信息，网络中所有节点记录下最小跳数信息。
2)建立各节点与锚节点间最小跳数与对应节点位置的ELM关系模型。以各节点与锚节点间最小跳数为输入，对应节点位置为输出，将实验数据划分为训练集和测试集。
3)将Bi=[bi1,bi2,…，bim，…,biM]作为训练集的输入，对应锚节点的位置Si=(xi,yi)为训练集的输出，i=1,2,…,M，m=1,2,…,M，对ELM算法进行训练，保存训练获得的参数H和β。
4)将Bj=[bj1,bj2,…,bjm,…,bjM]作为测试集，测试结果为对应未知节点的位置Sj=(xj,yj)。输入测试集，获取测试结果并分析。
2 引入虚拟节点的ELM定位算法
2.1 次锚节点
文献[8]将一部分未知节点升级为次锚节点实现了未知节点的定位问题。即网络部署阶段的部分未知节点，在定位过程得到较为精确的位置信息，升级为次锚节点，进一步对未知节点进行定位。节约了网络成本并且使网络定位精度得到了有效提高。
次锚节点的选择，是在对未知节点进行定位后，从中选出定位精度较为准确的未知节点升级为次锚节点。次锚节点的位置信息是未知节点定位后得到的估计位置，由于未知节点的实际位置是未知的，从而无法判断未知节点的实际位置与估计位置的误差。本文使用虚拟节点来解决这一问题，在所有未知节点中选出定位误差相对较小的未知节点作为次锚节点。
2.2 虚拟节点定位
虚拟节点没有节点间的通信和信息交互能力，不能直接获取虚拟节点到各锚节点之间的最小跳数，但是可以将距离转化为跳数。假设虚拟节点的位置已知，可先求出虚拟节点与锚节点间距离，再将距离信息转化为跳数信息。
如图1，节点O为锚节点，节点A和B为虚拟节点，O的通信半径为R，可知虚拟节点A和锚节点O之间距离DOA
图1 跳数分析
获取虚拟节点与各锚节点之间最小跳数信息后，用训练好的ELM估计虚拟节点的位置信息。
2.3 次锚节点的选取
将虚拟节点估计位置与实际位置进行比较，选出误差足够小的虚拟节点，删除其余的虚拟节点，并记录虚拟节点到各锚节点的最小跳数。
为了确定次锚节点，设到所有锚节点最小跳数相同的点位置相近。筛选出虚拟节点到各锚节点最小跳数与到各锚节点最小跳数相同的未知节点，其坐标即对应虚拟节点坐标，将之升级为次锚节点。
2.4 引入虚拟节点的ELM定位算法流程
1)随机放置N个节点，其中前M个为锚节点，剩余N-M个未知节点。锚节点向周围邻居节点发送坐标、ID、跳数信息，网络中所有节点记录下最小跳数信息。Si=(xi,yi)表示第i个节点的坐标(位置)。Bi=[bi1,bi2…bim…,biM]为各个锚节点间的最小跳数。Bj=[bj1,bj2,…bjm…,bjM]为各未知节点到各锚节点之间的最小跳数。
2)建立各节点与锚节点间最小跳数与对应节点位置的ELM关系模型。以各节点与锚节点间最小跳数为输入，对应节点位置为输出，将实验数据划分为训练集和测试集。
3)将Bi作为训练集的输入，对应锚节点的位置Si为训练集的输出。对ELM算法进行训练，保存训练获得的参数H和β。
4)在网络中设置C个虚拟节点，其位置表示为Tp=(xp,yp)，将虚拟节点与锚节点间距离转化为跳数。各虚拟节点到各锚节点之间的最小跳数Bp=[bp1,bp2,…,bpm,…,bpM]，bpm为第p个虚拟节点与第m个锚节点间最小跳数，p=1,2,…,C，m=1,2,…,M。
6)筛选出Bj=[bj1,bj2,…,bjm,…,bjM]与Bq=[bq1,bq2,…bqm,…,bqM]相同的未知节点，将这P个未知节点确定为次锚节点，P≤D。
7)将次锚节点和锚节点均作为无线传感器网络的锚节点为其余未知节点提供定位信息。此时网络中锚节点个数为M+P个，未知节点N-M-P个。
8)重新构建各节点与锚节点间最小跳数与对应节点位置的ELM关系模型。以Bi=[bi1,bi2,…,bim,…,bi(M+P)]，i=1,2…,M+P，m=1,2,…,M+P，为训练集的输入，对应锚节点的位置Si=(xi,yi)为训练集的输出训练ELM。
9)令Bj=[bj1,bj2,…,bjm,…,bjM]为测试集，测试结果为对应未知节点的位置Sj=(xj,yj)，j=M+P+1,M+2,…,N，m=1,2,…,M+P。输入测试集，获取测试结果并分析。
3 仿真分析
为验证所述方法的性能，对传统基于距离矢量跳(distance vector-based hop,DV-Hop)定位算法，BP定位算法改进的加权质心定位算法基于次级锚节点(improved weighted centroid localization algorithm for WSNs based on secondary anchor nodes,，IWCLA-SAN)算法[11]，ELM定位算法，以及引入虚拟节点的ELM算法分别在MATLAB平台上进行仿真。设所有节点均随机分布在100 m×100 m的区域内，每组不同条件的均仿真运行100次，对结果取平均值进行分析比较。
3.1 锚节点比例对定位误差的影响
对不同的锚节点比例进行仿真对比，共随机分布200个节点，通信半径设为40 m，其如图2所示。仿真结果中每种算法的定位误差均随锚节点所占比例的提升而减小。在锚节点比例小于10 %时，IWCLA-SAN算法误差最小。但在锚节点比例大于等于10 %的情况下，引入虚拟节点的ELM定位算法较IWCLA-SAN，BP算法及DV-Hop算法误差小。引入虚拟节点的ELM算法较ELM算法定位误差平均下降了3.76 %，说明在锚节点所占比例不同的情况下，引入虚拟节点升级次锚节点对于降低节点定位误差有效。
图2 锚节点所占比例和定位误差关系
3.2 对定位误差影响
对不同通信半径进行仿真，仿真中共随机分布200个节点，锚节点比例为10 %，仿真结果如图3所示。在通信半径小于35 m的情况下，IWCLA-SAN算法的定位误差最小，但在通信半径大于等于35 m的情况下，ELM算法较IWCLA-SAN、BP算法和DV-Hop算法误差小，且引入虚拟节点的ELM算法较ELM算法定位误差平均降低了4.22 %，表明在通信半径不同的情况下，引入虚拟节点升级次锚节点对于降低节点定位误差有效。
图3 通信半径和定位误差的关系
3.3 总节点数对定位误差的影响
对不同总节点数目进行仿真，仿真通信半径为40 m，锚节点比例为10 %，仿真结果如图4所示。当总节点数小于300个时，IWCLA-SAN算法的定位误差最小，但当总节点数大于等于300个时，ELM算法较IWCLA-SAN算法，BP算法及DV-Hop算法误差都要小，且引入虚拟节点的ELM算法较ELM算法定位误差平均降低了3.56 %，亦说明在总节点数目不同的时，引入虚拟节点升级次锚节点对于降低节点定位误差有效。
图4 总节点数和定位误差的关系
4 结 论
采用虚拟节点和ELM算法结合的算法选出次锚节点来提高锚节点比例，降低定位误差。在锚节点所占比例，通信半径，总节点数目变化的情况下，均可以减小定位误差，说明本文算法可以有效减小定位误差。算法总体较DV-Hop算法和BP定位算法的误差小，适用于无线传感器网络的定位，但对于锚节点比例和通信半径以及总节点数目有一定的要求。
参考文献:
[1] 彭 宇，王 彤.无线传感器网络定位技术综述[J].电子测量与仪器学报，2011,25(5):389-399.
[2] 莫宏伟，董会元，基于光电传感器的移动机器人室内定位[J].自动化技术与应用，2014,33(10)：33-36.
[3] 杨石磊,樊晓平,刘少强,等.一种改进的无线传感器网络DV-Hop定位算法[J].计算机测量与控制,2008,16(9):1356-1358.
[4] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine:A new learning scheme of feedforward neural networks[C]∥2004 Proceedings of IEEE International Joint Conference on Neural Networks,IEEE,2005:985-990.
[5] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine: Theory and applications[J].Neurocomputing,2006,70(1-3):489-501.
[6] 王 雷，沈龙云，孙毅刚.基于ELM的航空发动机传感器故障诊断方法研究[J].传感器与微系统,2015,34(4):16-18.
[7] Liu R,Sun K,Shen J.BP localization algorithm based on virtual nodes in wireless sensor networks[C]∥Proceedings of the 6th International Conference on Wireless Communications,Networking and Mobile Computing,WiCOM’10,2010:351-355.
[8] Zhao L Z,Wen X B,Li D.Amorphous localization algorithm based on BP artificial neural network[C]∥International Confe-rence on Software Intelligence Technologies and Applications & International Conference on Frontiers of Internet of Things,IET,2015.
[9] 龙 佳,卑璐璐,张 申,等.基于虚拟信标节点的改进加权质心定位修正算法[J].微电子学与计算机,2017,34(3):74-78.
[10] 衣 晓，王梓有，薛兴亮.一种基于次锚节点的无线传感器网络质心定位算法[J].计算机应用与软件，2013,30(6):116-120.
[11] 张先超,刘兴长,张春园.基于次锚节点的无线传感器网络改进加权质心定位算法[J].传感器与微系统,2015,34(2):143-146.
