孙宝山　刘晟源　刘骁骁

(天津工业大学计算机科学与软件学院　天津 300387)

0　引　言

在物联网IoT中，资料收集、跟踪目标、管理信息、环境监测和基于地理位置的消息路由等大量工作中都要求精准的节点位置信息提供保障[1]。因此，无线定位技术作为物联网的核心支撑技术长时间以来都持续受到了国际学术专家们普遍关注。卫星定位技术目前以全球定位系统GPS为代表，虽然已经可以在较为开阔的室外环境提供精度很高的定位服务，但在封闭环境下，例如室内或者地下环境中，因为障碍物阻挡了卫星定位信号、以及多种途径传播等因素影响，很难对其实现高效定位[2]。而无线传感器网络WSN定位技术因其成本低，易实施，抗干扰性强等优点已经成为大规模室内公共场所定位的一个重要解决方式。

按照测量节点彼此之间长度是否必要，无线传感器网络定位技术基本可以分成必要测距的定位方法[3-4]和不必要测距的定位方法[5]两种方式。必要测距的定位方式是通过检测出在空间之内所有节点彼此的长度距离以及角度信息，如利用未知节点。通过使用未知节点与一定数量的锚节点间的接收信号指示强度RSSI[6]、无线电波从发射结点到接收节点的传播时间TOA[7]、传播时间差 TDOA[8]、信号到达角度AOA[9]等测量数据来获取节点彼此之间的距离，之后使用三边测量法、三角测量法以及极大似然估计法等几何算法从而找到未知节点，因此定位精度相对较高。然而这些算法均需要额外的软硬件资源来对节点距离信息进行测量，这增加了算法在实际应用中的成本以及能耗[10]。基于非测距的定位算法通常根据拓扑关系或者事件的先后顺序来获取未知节点的位置，无需测量节点间的实际距离。这样在一定程度上会增加定位误差，但是大幅度降低了测量成本和能耗，因此它的发展十分迅速。目前以不必要测距的定位为基础的算法主要包括质心定位算法[11]、DV-Hop定位算法[12]和三角形内点测试定位算法(也称APIT 定位算法[13])，凸规划定位算法[14]和MDS-MAP定位算法[15]等。

1　相关研究

DV-Hop算法是在不必要测距的定位算法中比较经典的一种算法[16]。该算法基于距离矢量路由思想。如果网络环境中几点网络连通度较高并且各向同性密集，能取得较好的定位效果，但网络环境中的节点随机分布，锚节点的分布无规律，会造成能耗的浪费与成本的增加。同时因为平均跳距误差大、实际路径被直线路径代替等原因而存在定位误差大的问题。为解决这些问题，目前主要有三个部分对 DV-hop 算法进行改进: (1) 与其他的定位算法相结合，比如文献[17]通过使用RSSI算法增加了一个关于锚节点与未知节点之间的修正值，从而提高了算法的定位精度；(2) 对平均每跳距离进行改进，比如文献[18]对锚节点的平均每跳距离进行算术平均处理；(3) 将定位计算方法做最后一步改进，文献[19]中利用QR分解代替最小二乘法来计算节点坐标以减小误差。这些改进一定程度上减小了节点实际路径与计算路径的误差，但是并没有根本上解决DV-Hop在计算跳距阶段所产生的非线性最小二乘问题，同时又增加了算法的整体复杂度，增加了能耗。为改善这些问题，文献[20]以传统的DV-Hop算法为基础提出了HDV-Hop(Hybrid DV-Hop)算法，对锚节点的部署、洪泛方式以及距离的计算都做出了重大调整。首先在节点的布局方面，将锚节点部署在传感器网络外围形成锚节点环，另外使用基站作为所有节点的数据通信中心，并承担定位算法计算部分的工作。这种布局方式便于部署并且应用性强，同时将后续的计算工作放到基站减少了传感器节点因计算而消耗的能量，让这种算法在大范围内定位无线传感器网络方面更具实用性。在计算阶段，HDV-Hop算法使用非线性最小二乘优化算法估算锚节点与未知节点间的距离，从而使定位精度到一个全新的高度。HDV-Hop算法包含四个阶段，其算法流程图如图1所示。

图1　HDV-Hop算法的流程图

在第一阶段中，锚节点将包含有自身ID，坐标和变量HopCounti(初始为0)的信息洪泛至网络内所有节点。节点在保存锚节点信息之前会根据锚节点的ID检查HopCounti的值，只保留HopCounti最小的值。在第二阶段中，锚节点i计算平均每跳距离，公式如下：

(1)

式中：M表示网络中锚节点的个数，j代表其他锚节点，HopCounti,j代表锚节点i和锚节点j之间的跳数，(xi,yi)和(xj,yj)分别代表锚节点i和锚节点j的坐标。在计算完AvgHopLengthi后，锚节点i将它的ID，坐标以及AvgHopLengthi发送到基站。在第三阶段中，未知节点也将包含有自身ID，到锚节点i的跳数信息HopCounti发送到基站。在第四阶段中，对于每一个未知节点，基站首先根据式(2)估算出未知节点到锚节点i的距离di，然后使用trilateration算法估算出未知节点的坐标位置，从而完成定位。

di=AverageHopLengthi×HopCounti

(2)

2　算法改进

2.1　锚节点的矩形环绕布局

锚节点通常是预先安装了GPS等定位装置的传感器，在室内、地下等环境中，其卫星信号会受到干扰使得位置信息出现较大误差，从而影响后续定位的精确度。另外在HDV-Hop中，对锚节点的布局形状做了多种实验，比如圆形、三角形和矩形，并指出使用相同的定位算法。实验结果是随着锚节点数量的变化，使用矩形布局的误差要明显小于传统的圆形布局，而且是三种布局方式中最稳定的一种，如图2所示。

图2　三种形状布局实验误差比较

由于在对无线传感器网络定位技术具有强烈需求的超市、地下停车场、机场等大型室内公共场所中，绝大部分的监测区域都是矩形的，同时矩形的规则性更加方便我们利用其特点做出改进。因此本文决定将矩形作为新型定位算法的布局方式，如图3所示。为方便后续的实验，我们将圆形的HDV-Hop算法称为HDV-Hop定位算法，矩形的HDV-Hop算法称为RHDV-Hop定位算法RHDV-Hop(Rectangular HDV-Hop)。

图3　在RHDV-Hop分布的传感器节点

和DV-Hop算法中锚节点与未知节点一样随机抛撒在网络区域内不同，RHDV-Hop定位算法中的锚节点是预先部署在大型公共场所的边缘。这样在部署的过程中不需要额外的定位装置就可以获得锚节点的精确位置，减小了锚节点的制造成本，为后续对未知节点的定位提供了保障。另外将锚节点固定在网络边缘还可以为锚节点提供稳定持续的能量，保证了锚节点的存活率，还便于对锚节点进行日常管理与维护。

2.2　平均每跳的距离

在无线传感器网络中，节点间数据的路由并不是沿直线传输的，在节点间的跳数比较多的情况下，通信线路会变得弯曲，平均每跳距离只是笼统的将直线代替弯曲的线路。因此平均每跳距离并不是一个确定的值，它的大小与每个锚节点的拓扑有关。平均每跳距离的不同如图4所示。

(a) A1的拓扑结构

(b) A2的拓扑结构

(c) A3的拓扑结构图4　拓扑结构

在图4中，锚节点A距离锚节点B 20米1跳，距离锚节点C 10米1跳，距离锚节点D40米2跳。在三种情况下使用式(1)计算锚节点A的平均每跳距离分别为：AvgHopLengthA1=(10+20)/2=15 m/hop，AvgHopLengthA2=(10+20+40)/(1+2)=17.5 m/hop，和AvgHopLengthA3=(20+40)/(1+2)=20 m/hop。比较(a)和(b)两种情况，(b)中增加了一个锚节点D，改变了原有的拓扑结构，使得A的平均每跳距离发生变化；比较(a)和(c)两种情况，锚节点的数量一样，但是拓扑不同，A的平均每跳距离也不相同。

对于每一个未知节点到所有锚节点的拓扑，也是不完全相同的，如图5所示。

(a) U1的拓扑结构　(b) U2的拓扑结构　　(c) U3的拓扑结构图5　未知节点到所有锚节点的拓扑

在图5中，锚节点的位置虽然没有发生变化，但是对于未知节点U1、U2和U3来说，它们的拓扑结构却不相同。从拓扑结构上来看，未知节点U1的周围都是一跳锚节点，它的拓扑结构与图4中的A1类似，同样的U2、U3分别与A2、A3的拓扑结构基本一样。如果一个锚节点的拓扑结构与未知节点的拓扑结构相契合，也就是说它们的平均每跳距离相差不大，根据DV-Hop里面的算法，通过选取每一个锚节点的平均每跳距离乘以每一个锚节点到该位置节点跳数计算距离，本文尝试通过选锚节点的平均每跳距离来计算距离，实验结果如图6所示。

图6　DV-Hop算法和RHDV-Hop算法中 使用平均每跳距离误差对比

从图6中可以看出选择平均每跳距离来计算距离有一定的优势，因此选择恰当的平均每跳距离将会是相当关键的一步。在选取平均每跳距离计算未知节点到锚节点的距离时，HDV-Hop算法使用式(2)，因为对于圆形的锚节点拓扑结构来说，每个锚节点的平均每跳距离基本相同，无法进行选取。而在RHDV-Hop定位算法中，矩形增加了锚节点的拓扑结构。

我们定义“AverageHop”作为标准来选取平均每跳距离。

(3)

式中：M代表网络中锚节点的个数，对于锚节点i的平均跳数来说j代表其他锚节点，HopCountj代表其他锚节点j距离锚节点i的跳数，对于未知节点i的平均跳数来说j代表所有锚节点，HopCountj代表所有锚节点j距离未知节点i的跳数。图5中U1的平均跳数(1+1+1+1)/4=1，与图1中A1的平均跳数为(1+1)/2=1相当， U2的平均跳数为(1+1+1+2)/4=1.25，与图2中A2的平均跳数为(1+1+2)/3=1.33较为相当，U3的平均跳数为(1+1+2+2)/4=1.5，与A3的平均跳数为(1+2)/2=1.5较为相当。

2.3　算法描述

“平均跳数”是应用在新型定位算法中的第四阶段，目的是选取一个与未知节点的整体拓扑结构最吻合的锚节点，然后使用该锚节点的平均每跳距离作为全局平均每跳距离进行计算。以下是新型定位算法的详细流程图7，算法的主要步骤如下：

第一步：全部锚节点将自己的坐标与跳数(初始为0)洪泛至所有节点。

第二步：锚节点通过获得的其他锚节点坐标以及之间的跳数计算出每个锚节点的平均每跳距离，同时计算出它们的平均跳数，作为锚节点自身的另一个数据一起发送给基站。

第三步：未知节点将之前获得到达每个锚节点所需要的跳数添加进自身数据发送给基站。

第四步：基站在收到未知节点的数据后，开始根据全部未知节点到所有锚节点的跳数值计算出全局平均跳数。然后与每个锚节点的平均跳数值做对比，选取差别最小的平均跳数对应的锚节点，再使用这个锚节点所对应的平均每跳距离作为全局平均每跳距离进行估算距离。

第五步：通过之前选取到的全局平均每跳距离估算出未知节点到锚节点的距离，然后通过Levenberg-Marquardt 算法估算未知节点位置坐标。

图7　改善RHDV-Hop的流程图

3　仿真试验与结果分析

3.1　仿真环境

本文使用Matlab进行实验仿真，在满足基站存在，并且所有节点都会发送数据到基站的条件下，通过改变传感器网络规模(包括网络面积和网络内传感器节点的个数)，锚节点个数和未知节点个数三种情况对HDV-Hop算法、RHDV-Hop算法和Improved RHDV-Hop算法的定位误差进行比较。仿真结果如图8-图10所示，其中每张图的定位误差为30次实验的平均值。

假定所有锚节点平均分布在网络边缘，未知节点随机分布在网络中央，所有节点的通信半径为100 m。目前室内定位技术通常使用Zigbee通信技术，其通信距离一般为100 m左右[21]。使用平均误差来作为衡量定位误差的标准，公式为:

(4)

3.2　仿真结果分析

3.2.1不同网络规模的仿真结果比较

在图8的仿真实验中，将无线传感器网络区域面积设置从50 000增加到500 000 m2，这与车库、超市、机场等大型公共场所面积相吻合，另外在面积增加的同时，我们也相应的增加未知节点数和锚节点数。

图8　不同区域值的平均定位误差

从图8中可以看出，将布局方式改为矩形的HDV-Hop算法的定位误差和HDV-Hop算法相比较并没有增加。而无论网络面积以及节点密度的增加，新型的RHDV-Hop算法的定位误差一直都是最低的。这就意味着新型RHDV-Hop算法的定位精确度要好于HDV-Hop算法和RHDV-Hop算法。

3.2.2不同锚节点数量的仿真结果比较

在图9的仿真实验中，我们分别把网络面积和未知节点数固定为200 000 m2和1 000，将锚节点的数量从50增加到200，每次增加25个。

图9　在不同数量的锚点上的平均定位误差

从图9可以看出RHDV-Hop算法的定位误差和HDV-Hop算法相比较并没有增加。而无论锚节点怎样增加，改进RHDV-Hop算法的定位误差一直都是最低的。这就意味着新型RHDV-Hop算法的定位精确度较HDV-Hop算法和RHDV-Hop算法要更好。另外我们能够得到的是不管锚节如何变化，三种算法的定位精确度变化都不是很大，可以说明在实际环境中没有必要部署过多的锚节点就可以达到同样的定位效果。

3.2.3不同未知节点的仿真结果比较

在图10的仿真实验中，我们分别把网络面积和锚节点数固定为200 000 m2和100，将未知节点的数量从500增加到2 000，每次增加250个。

从图10可以看出，RHDV-Hop算法的定位误差和HDV-Hop算法相比较并没有增加。而无论未知节点怎样变化，新型的RHDV-Hop算法的定位误差一直都是最低的。这就意味着新型RHDV-Hop算法的定位精确度要比HDV-Hop算法和RHDV-Hop算法更优。我们还能发现，在未知节点的增加的同时，三种算法的定位精确度也在逐渐提高。在实际环境中，节点对应着用户，说明在一个公共场所里，用户密度越大，算法定位精度越好。

图10　不同数量传感器的平均定位误差

4　结　语

本文针对大型公共场所对无线传感器网络定位技术的需求，在现有的HDV-Hop定位算法的基础上进行改进。首先将锚节点部署在大型公共场所中比较常见的矩形边缘，同时利用得出的平均每跳距离的不同与节点拓扑结构相关的结论，使用平均跳数作为比较拓扑结构相似程度的标准来选取合适的平均每跳距离，然后将其作为全局平均每跳距离进行计算。理论分析与算法仿真显示，在相同环境下，新型定位算法可以明显提高节点定位精度，并且更具实用性。

较RHDV-Hop相比，本论文算法虽然在一定程度上提升了定位精确度，但是对于大型公共场所的实际定位需求还有一定距离。另外在现有的布局方式上还有其他的改进之处。比如可以有选择性地控制锚节点的开闭来调整它们的拓扑结构使之更加匹配未知节点的拓扑结构。同时并非所有的大型公共场所都是矩形形状，如何根据本算法的现有成果提出一种适用于所有形状的解决方案也是一个要面对的问题。

[1] Mao G, Fidan B, Anderson B D O. Wireless sensor network localization techniques[J]. Computer Networks, 2007, 51(10):2529-2553.

[2] Liu H, Darabi H, Banerjee P, et al. Survey of Wireless Indoor Positioning Techniques and Systems[J]. IEEE Transactions on Systems Man & Cybernetics Part C, 2007, 37(6):1067-1080.

[3] Lee J, Chung W, Kim E. A new range-free localization method using quadratic programming[J]. Computer Communications, 2011, 34(8):998-1010.

[4] Sun B, Dong L. Dynamic Model Adaptive to User Interest Drift Based on Cluster and Nearest Neighbors[J]. IEEE Access, 2017, 5(99):1682-1691.

[5] Shi Q, He C, Chen H, et al. Distributed Wireless Sensor Network Localization Via Sequential Greedy Optimization Algorithm[J]. IEEE Transactions on Signal Processing, 2010, 58(6):3328-3340.

[6] Barsocchi P, Lenzi S, Chessa S, et al. Virtual calibration for RSSI-based indoor localization with IEEE 802.15.4[C]//IEEE International Conference on Communications. IEEE, 2009:1-5.

[7] Geiger D J. High Resolution Time Difference of Arrival Using Timestamps for Localization in 802.11b/g Wireless Networks[C]//Wireless Communications and NETWORKING Conference. IEEE, 2010:1-6.

[8] Lee J X, Lin Z W, Chin P S, et al. A Scheme to Compensate Time Drift in Time Difference of Arrival Localization Among Non-Synchronized Sensor Nodes[C]//Vehicular Technology Conference, 2009. Vtc Spring 2009. IEEE. IEEE, 2009:1-4.

[9] Souden M, Affes S, Benesty J. A Two-Stage Approach to Estimate the Angles of Arrival and the Angular Spreads of Locally Scattered Sources[J]. IEEE Transactions on Signal Processing, 2008, 56(5):1968-1983.

[10] Basagni S, Carosi A, Melachrinoudis E, et al. Protocols and model for sink mobility in wireless sensor networks[J]. Acm Sigmobile Mobile Computing & Communications Review, 2006, 10(4):28-30.

[11] Rappapport T S. Wireless Communications: Principles and Practice[M]. Prentice Hall: New Jersey, 1996:50-143.

[12] Tomic S, Mezei I. Improved DV-Hop localization algorithm for wireless sensor networks[C]//2012 IEEE 10th Jubilee International Symposium on Intelligent Systems and Informatics. IEEE, 2012:389-394.

[13] Zhou Y, Ao X, Xia S. An improved APIT node self-localization algorithm in WSN[C]//Intelligent Control and Automation, 2008. Wcica 2008. World Congress on. IEEE, 2008:7582-7586.

[14] Shang Y, Ruml W. Improved MDS-Based localization[C]//Proceedings of 23th Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE INFOCOM04, 2004:2640-2651.

[15] Shang Y, Ruml W, Zhang Y, et al. Localization from Connectivity in Sensor Networks[J]. Journal of IEEE Transactions on Parallel and Distributed Systems, 2004(15):961-974.

[16] Niculescu D, Nath B. Ad hoc positioning system (APS) using AOA[C]//Joint Conference of the IEEE Computer and Communications. IEEE Societies. IEEE, 2003, 3:1734-1743.

[17] Zhang J, Yang R, Li J. An Enhanced DV-Hop Localization Algorithm using RSSI[J]. International Journal of Future Generation Communication & Networking, 2013, 6(6):91-98.

[18] Song G, Tam D, Xue Y, et al. RDV-hop localization algorithm for randomly deployed Wireless Sensor Networks[C]//International Conference on Software Intelligence Technologies and Applications & International Conference on Frontiers of Internet of Things. IET, 2015:190-195.

[19] Zhang D, Fang Z, Wang Y, et al. A new improved range free algorithm based on DV-Hop in Wireless Sensor Network[J]. Journal of Communications, 2015(10):589-595.

[20] Safa H. A novel localization algorithm for large scale wireless sensor networks[J]. Computer Communications, 2014, 45(3):32-46.

[21] Wheeler A. Commercial Applications of Wireless Sensor Networks Using ZigBee[J]. IEEE Communications Magazine, 2007,45(4):70-77.