刘广聪　郝艳茹　刘　铮

(广东工业大学计算机学院　广东 广州 510006)

0　引　言

无线传感器网络WSN作为国际上备受关注的研究热点，已被广泛应用于农业、医疗、军事等多个领域[1]。在各应用领域中，传感器节点搜集数据并将这些数据和自身的位置信息上传到服务器进行分析处理，使无线传感器网络完成对周围环境的感知、探测和监视的功能。无线传感器网络的定位技术是实现上述应用的重要基础，因此传感器定位技术至关重要[2]。

定位技术分为基于距离的定位算法和距离无关的定位算法[3]。前者的定位精度高，但需测量相邻节点间的绝对距离和角度，对网络中硬件的要求较高[4]。后者根据网络的连通性等信息实现定位、功耗小、成本低、应用范围较广，主要包含有质心算法、APIT算法和DV-Hop算法等[5]。本文主要研究基于距离无关的DV-Hop定位算法。目前已有一些提高DV-Hop定位精度的改进方法，如肖少波等在文献[6]中对信标节点间跳数修正，有效地减少了跳距估算带来的定位误差，提高平均定位精度。顾亦然等在文献[7]中引入信标节点的平均跳距误差并对测距误差进行加权处理，改进后的DV-Hop算法定位误差减小。李娟等在文献[8]中采用两个通信半径广播自身位置信息，从而获得未知节点与信标节点间更精确的跳数，得到未知节点更精确的坐标。谭博等在文献[9]采用最小二乘法优化信标节点的平均单跳距离进而提高DV-Hop算法定位精度。总体来看，上述方法都是分别针对测距误差以及定位求解方法进行研究，主要考察如何减小测距误差对定位结果的影响。虽然对测距误差引起的定位误差有所改进，但对于具有较大误差的测量值，以上方法不能有效减小其对定位结果的影响。基于此，本文提出一种基于离群点检测算法LOF的多边定位算法。该算法减小了较大测距误差产生的对定位精度的影响，经过实验验证本文算法提高了DV-Hop算法的定位精度。

1　DV-Hop定位算法

DV-Hop定位过程分为以下三个阶段：

第一阶段信标节点不断向整个网络广播信息分组{hi,Xi,Yi}，其中hi为跳数且其初始值为0、Xi、Yi表示该信标节点的横纵坐标。未知节点记录来自各个信标节点的位置信息和它与每个信标节点间的最小跳数值hi，然后将hi值加1后转发到邻居节点。以这种方式，未知节点得到与每个信标节点间的最小跳数和信标节点的位置信息[10]。

第二阶段根据式(1)计算网络中所有信标节点的平均单跳距离Ci。设信标节点Bi、Bj的坐标为(Xi，Yi)、(Xj，Yj)，hij为Bi、Bj间的最小跳数。

(1)

信标节点将自身的平均单跳距离广播到传感器网络中，未知节点仅记录收到的第一个信标节点的平均单跳距离。然后未知节点利用记录的跳数信息和接收到的平均单跳距离计算出与各个信标节点的估计距离：

dj=Ci×huj

(2)

式中：Ci为未知节点u收到的第一个的信标节点的平均单跳距离，huj为未知节点u与信标节点Bj间的跳数值，dj为未知节点与信标节点Bj间的距离。

第三阶段未知节点根据到各个信标节点的估计距离dj，采用三边测量法或极大似然估计法计算自身坐标位置[11]。

式(3)中(X1，Y1),(X2,Y2),…,(Xn，Yn)为信标节点坐标，(X，Y)为未知节点坐标。

(3)

式(3)可以表示成线性方程式AX=B求解。

最后使用最小均方差估计法得到未知节点的坐标，如下式所示：

(4)

2　改进的DV-Hop定位算法

2.1　用加权方式求得信标节点的平均单跳距离

设Bi、Bj为信标节点，信标节点Bi的平均单跳距离受到Bi与其余信标节点间的距离影响。若Bi、Bj间的距离较小，则Bj对Bi的平均单跳距离影响大；若Bi、Bj间的距离较大，则Bj对Bi的平均单跳距离影响小。据此提出用加权系数ω对Bi与不同信标节点间的单跳距离加权来求得信标节点Bi的平均单跳距离。

信标节点Bi、Bj间的单跳距离用HopSizeij表示，如下式所示：

(5)

(6)

信标节点Bi的平均跳距用式(7)求得：

(7)

最后未知节点利用最近信标节点修正后的单跳距离HopSizei和与各个信标节点跳数值估计出该未知节点与各个信标节点的距离。

2.2　计算未知节点坐标位置

2.2.1LOF检测法的相关概念

k距离：数据集中的任一点o与其第k个最近邻节点之间的距离被称为点o的k距离，记为k-distance(o)。

k距离邻域：设o为数据集中的任意点，则数据集中所有到点o的距离小于o的k距离的点所形成的邻域称之为k距离邻域[13]。

Nk(o)：数据集中的任意点o的k距离邻域内所包含的所有点的个数。

Nk(o)={o′|o′∈D,distance(o,o′)≤distance(o)}

distance(p，q)：对象p与q间的欧式距离。

可达距离(reachdistk(q←p))：设p、q为数据集中的任意对象,点p到点q的可达距离为p、q点间的欧式距离和q点k距离的最大值即max{k-distance(q)，distance(p，q)}。

局部可达密度:数据点o的局部可达密度是o点到其邻域内的最大的前k个距离的平均值的倒数。lrdk(o)衡量了数据点o在其最近的k个最近点集合内的稀疏程度。

(8)

局部离群因子LOFk(q):局部离群因子表示数据点q与整体的一种密度差异。若局部离群因子值远大于1，则q点周围的局部密度与整体的密度差异较大，认为q为离群点。若局部离群因子的值接近1，则q点周围的局部密度与整体密度的差异较小，认为q为正常点[14]。

(9)

2.2.2基于离群点检测的多边测量算法

设未知节点能够感受到的信标节点的个数为N,即未知节点能够接收到N个信标节点的距离信息，该距离信息为{d1,d2,…,dN}。处理步骤如下:

1) 对N的值进行判断，如果N<3则无法使用多边测量法，定位结束；如果N≥3,则执行下一步。

3) 输入步骤2)中的集合U，按照以下步骤处理集合U中的数据。

(1) 在集合U中随机选取K个点作为初始化中心点，记为Ui={(Uix,Uiy)|i=1,2,…,K}，各个中心点所对应的聚类为Ui聚类。

(2) 计算集合U中其余点到Ui聚类中各个中心点的距离，根据距离最小原则指派各个数据点到距离最近的聚类中，重新计算每个聚类的均值作为聚类中心点。

(3) 重复步骤(2)直至K个聚类的中心点的坐标不再改变，分别计算K个聚类的中心点坐标，聚类半径，如下式所示：

(10)

(11)

式中：Xi为Ui聚类中的数据对象，ni为Ui聚类中数据对象的个数。

(4) 计算各个Ui聚类中的点到Ui聚类中心点Ci的欧式距离dij，比较dij与对应聚类的聚类半径Ri的大小，若dij大于Ri则将该点标记为离群点的候选集中的点。设候选离群点集为hij。

(12)

Ri为Ui聚类的聚类半径，hij属于Ui聚类,ni为Ui聚类中的数据点的个数，m为预设定的离群点个数。

(5) 计算hij中每个数据对象的利群因子LOF值，然后根据各个数据对象的LOF值对hij中的数据对象排序，选出LOF最大的前m个点作为离群点, 将m个离群点去掉重新计算K个聚类的中心点的坐标(Cix,Ciy)其中i=1,2,…,K。

(6)K个聚类中所含数据点的个数不同，当第i个聚类Ui中所含点的个数越大，未知节点在Ui聚类中出现的几率越大，因此给该聚类越大的权重，未知节点的坐标如下式所示：

(13)

式中：ni为第i个聚类中所含数据点的个数;K为聚类个数。

3　仿真测试与结果分析

为了验证算法的有效性，本文采用MATLAB分别对传统的DV-Hop算法和本算法进行仿真。假设所有的仿真实验所需的环境都在同一网络场景下进行的，节点随机部署在二维监测区域内，所有节点具有一致的通信半径且通信半径为R。

定位精度是衡量定位算法优劣的一个主要指标[15]如下式所示：

(14)

式中：Eav为平均定位误差；(xrel，yrel)和(xest，yest)分别是未知节点的估计坐标和真实坐标；N为总节点数量；n为信标节点的数量；R为节点的通信半径。

如图1是无线传感器节点随机分布图，节点随机分布在100 m×100 m的正方形区域内，其中节点总数设置为100，信标节点数设置为10，未知节点所占比例为90%。

图1　节点分布图

图2显示了某个未知节点定位结果，是通过离群点算法LOF对未知节点的估计坐标进行分析的一个实例图。“×”代表未知节点的坐标，黑色的点代表聚类中的离群点，三角形、圆形、正方形、五角星分别代表密度不同的聚类。从图可以看出，LOF算法能够很好地识别离群点，提高未知节点的定位精度。

图2　聚类优化实例图

图3展现了各未知节点采用本文算法和DH-Hop算法定位后的定位误差连线图。单个节点的定位误差为该节点偏差距离与节点通信半径的比值, 使用本文算法和DV-Hop算法定位后的平均定位误差分别为26.54%、40.13%。本组实验在100 m×100 m的区域中随机分布100个节点，信标节点20个，未知节点80个，节点通信半径为20 m，信标节点所占的比例为20%。从图中可以看出，本文算法的定位精度明显优于DV-Hop算法。

图3　未知节点定位误差对比图

图4表示传感器网络中的节点总数与定位误差之间的关系。本组实验设置信标节点所占比例为10%不变，通信半径为20 m。从图4中可以看出传统DV-Hop算法和本文算法在节点总数增加的情况下，定位误差都有所下降，这是因为在同一区域内节点密度增加进而提高了定位精度。但本文算法平均定位误差率与 DV-Hop 相比降低了约15.73 %。

图4　网络节点总数对定位误差的影响

图5反映了信标节点所占比例与定位误差之间的关系。本组实验中，设置节点总数设为100，节点通信半径R为20 m，信标节点所占比例范围在5%～35%之间变化。从图中可以看出，两种定位算法的平均定位误差都呈递减趋势，都是随着信标节点的增加平均定位误差减小。这是因为随着信标节点数的增加，网络连通度增强，定位精度提高。本文算法平均定位误差率与 DV-Hop 相比降低了约14.65%。

图5　信标节点所占比例对定位误差的影响

图6反映了网络中节点的通信半径与定位误差之间的关系。本组实验设置节点总数为100，信标节点总数为30，节点的通信半径在20～50 m之间递增变化。实验结果显示，随着通信半径的增大，平均定位误差先下降后又有上升的趋势。这是因为当通信半径很小时随着通信半径的增大节点间的连通性增强，整体产生的误差小，所以定位精度提高。当通信半径大于某一临界值时会因为通信半径较大使得节点间跳数太少而导致节点间估计距离产生较大的误差从而导致定位误差有所增高。总体而言，本文算法较传统DV-Hop算法降低了平均定位误差。

图6　通信半径对定位误差的影响

4　结　语

本文利用离群点多边测距算法对DV-Hop算法进行改进。在不增加额外硬件设备的条件下，本算法相比传统的定位算法能够有效提高定位精度，减小定位误差，其定位误差能够维持在一个较小的范围内。本算法增加了传感器网络中节点的计算量，下一步我们将研究进一步提高定位精度的同时如何降低节点的计算量。

[1] 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.

[2] 孙利民,李建中,陈渝,等.无线传感器网络[M].清华大学出版社,2005.

[3] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//International Conference on Mobile Computing and NETWORKING.ACM,2005:81-95.

[4] Müller C,Alves D I,Ucha-Filho B F,et al.Improved solution for node location multilateration algorithms in wireless sensor networks[J].Electronics Letters,2016,52(13):1179-1181.

[5] Nicolescu D,Nath B.Ad-Hoc positioning systems(ASP)[C]//Proc.of the 2001 IEEE Global Telecommunications Conference Vol.5,San Antonio:IEEE Communications Society,2001:2926-2931.

[6] 肖少波,朱晓丽,邹建梅.基于跳数修正的DV-Hop改进算法[J].传感技术学报,2015,28(5):757-762.

[7] 顾亦然,蒋璐璐.一种改进无线传感器网络的DV-Hop定位算法[J].计算机技术与发展,2012,22(10):109-112.

[8] 李娟,刘禹,钱志鸿,等.基于双通信半径的传感器网络DV-Hop定位算法[J].吉林大学学报,2014,44(2):502-507.

[9] 谭博,车进,张成.基于最小二乘法优化的加权DV-Hop改进算法[J].计算机工程与应用,2015,51(2):82-86.

[10] 曹欲晓,严奎,徐金宝.一种最优锚节点集合上的两重粒子群优化DV-Hop定位算法[J].传感技术学报,2015,28(3):424-429.

[11] Cenedese A,Ortolan G,Bertinato M.Low-Density Wireless Sensor Networks for Localization and Tracking in Critical Environments[J].IEEE Transactions on Vehicular Technology,2010,59(6):2951-2962.

[12] 乔欣,常飞,丁恩杰,等.基于跳距修正的WSN拟牛顿迭代定位算法[J].传感技术学报,2014,27(6):797-801.

[13] 王敬华,赵新想,张国燕,等.NLOF:一种新的基于密度的局部离群点检测算法[J].计算机科学,2013,40(8):181-185.

[14] 王习特,申德荣,白梅.BOD:一种高效的分布式离群点检测算法[J].计算机学报,2016,39(1):36-51.

[15] 朱敏,刘昊霖,张志宏,等.一种基于DV-HOP改进的无线传感器网络定位算法[J].四川大学学报(工程科学版),2012,44(1):93-98.