基于CC2510 的DV-Hop 定位算法的改进*

裴菊静，王经卓，许红艳

(1.中国矿业大学 信息与电气工程学院，江苏 徐州221116;2.淮海工学院 电子工程学院，江苏 连云港222005)

0 引 言

无线传感器网络是是由大量未知节点随机部署形成的自组织网络。由于这些未知节点的位置是未知的，如果要采集、处理未知节点的信息，必须要知道它们的位置，因此，定位技术是无线传感器网络现在研究的重点。

在定位算法中根据定位过程是否需要测量节点之间的实际距离，把定位算法分为无需测距(range－free)的定位算法和基于测距［1］(range－based)的定位算法。前者不需要测量节点间的实际距离，而是利用节点间的估计距离计算节点间的实际距离，后者需要测量相邻节点间的实际距离来计算未知节点的位置。基于测距的定位算法虽然定位精度较高，但它并不适用于低功耗、低成本的应用领域。距离无关的定位算法精度较低，但能满足大部分无线传感器网络的要求，因此，在实际应用中普遍使用。常用的无需测距的定位算法有质心定位算法、DV－Hop 算法、MDS－MAP 算法、Bounding－Box 定位算法、近似三角形内点测试法(APIT)等。

1 DV-Hop 和改进的算法

1.1 DV－Hop 算法

DV－Hop［2］算法是由 Niculescu 和 Nath 提出来的，它的基本思想是通过运用节点间的跳数和每跳的距离来估计节点间的实际距离。具体算法分为3 个步骤:1)使用经典的距离矢量交换协议，信标节点发送自己的位置信息和跳数，是所有节点获得信标节点的最小跳数;2)信标节点根据自身记录的其他信标节点的位置和跳数根据公式计算平均每跳距离，则未知节点可以计算到相对应的信标节点之间的距离;3)当未知节点收到不小于3 个到信标节点的距离时，可以根据三边定位或最小二乘法计算自身坐标

式中 ci为平均每跳距离;(xi，yi)，(xj，yj)为锚节点 i 和 j的坐标，hi为跳数。

1.2 改进的算法

Chipcon 公司的CC2510 芯片是一种内嵌8051 单片机的低功耗的芯片，内部具有无线定位引擎，它的定位功能是基于接收信号强度指示(RSSI)测距［3］。在RSSI 定位过程中，未知节点根据接收到的信号强度值计算信号的传播损耗，根据对应的传播模型可以将传播损耗转换成距离。未知节点可以把自己获得的坐标和RSSI 值传送到CC2510 组成的定位模块，然后由内部的定位引擎计算得到自身坐标。在改进的算法中，用CC2510 设计硬件节点［4］。

在DV－Hop 算法的第一阶段中要用到洪泛法，使节点能量开销很大，在估算未知节点到信标节点之间跳数时，当跳数为1 跳时，可以直接通过RSSI 测距法来计算1 跳距离，这样会降低整个网络的功耗和减小定位误差。在第二阶段中，信标节点广播自己的位置信息，未知节点收到不小于3个信标节点的位置信息时，通过RSSI 测距法［5］的信号强度值选取离自己最近的3 个信标节点存入自己的数据包，当信标节点继续发送信息，未知节点从接收到的信息中比较，当RSSI 值大于自己存储的数据时，则存入数据包;否则，丢弃。然后选取3 个最大RSSI 值的信标节点计算平均每跳距离。在第三阶段当用三边测量计算自身坐标时，未知节点就用第二阶段获得的3 个信标节点计算。

改进的算法降低了第一阶段洪泛法的能量损耗，当距离为1 跳距离时直接用测得的RSSI 求出距离。还可以减小第二阶段求平均每条距离带来的误差，因为未知节点计算距离时不再统一用固定的平均每跳距离，而是根据自身储存的信息选取合适的信标节点来计算。改进的算法流程［6］如图 1。

图1 改进算法的流程图Fig 1 Flow chart of improved algorithm

2 仿真实验

为了验证上述改进算法的有效性，用CC2510 设计的节点硬件进行了模拟实验，并且对定位算法进行了Matlab 仿真［7］，在100 m×100 m 的正方形区域随机部署100 个节点，其中，信标节点为10 个，通信半径为50 m。图2 和图3 分别为节点的随机分布和未知节点的定位误差，实验结果可以得到定位误差降低到20%左右，证明了本算法可以适当减小定位误差。

图2 节点的分布Fig 2 Distribution of nodes

图3 节点的定位误差Fig 3 Localization error of nodes

通过改变信标节点的数目，再次验证算法的精确度，测量改进算法的误差和原来的算法相比较得到图4。从图中可以看出:随着信标节点的增加，定位误差逐渐减小，并且改进后的DV－Hop 算法对于信标节点的变化具有较好的稳定性［8］。

图4 改进算法前后的定位误差图Fig 4 Localization error diagram before and after the algorithm is improved

3 结 论

针对DV－Hop 算法的特点，本文提出了基于 CC2510 定位引擎的RSSI 测距技术的改进的定位算法，在第一阶段当跳数为1 时，直接采用RSSI 测距，减少了第二阶段的能量开销，降低了误差，在第二阶段采用RSSI 测距技术选取合适的信标节点求平均每跳距离，并且在三边测量求未知节点的坐标时，可以参照第二阶段选取的信标节点。仿真结果表明:改进的定位算法比传统的DV－Hop 显示出了优越的性能，且定位的精度得到提高。

［1］ 王汝传，孙力娟.无线传感器网络技术及其应用［M］.北京:人民邮电出社，2011.

［2］ 刘文远，王恩爽，陈子军.无线传感器网络中DV－Hop 定位算法的改进［J］.小型微型计算机系统，2011，6(6):1072 －1073.

［3］ Wu Lingfei，Meng Qinghu，Liang Huawei.A collinearity－based localization algorithm for wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2009，22(5):722 －727.

［4］ Yang Zheng，Liu Yunhao.Quality of trilateration:Confidencebased iterative localization［J］.IEEE Transactions on Parallel and Distributed Systems，2009，99(2):631 － 640.

［5］ Huw W，Qin H B，Huang H Y.A mobile beacon－based method for wireless sensor networks localization［C］//Proceedings of The 11th IEEE International Conference on Communication Technology，2008:1 －4.

［6］ 史洪宇，燕 莎.WSNs 中一种改进的DV－Hop 节点定位算法电光与控制［J］.电光与控制，2011，18(4):93 －95.

［7］ Wu Xiaobing，Chen Guihai，Das S K.The energy hole problem of non－uniform sensor distribution［J］.Chinese Journal of Computers，2008，31(2):253 －261.

［8］ Chen H，Kaoru S，Deng P，et al.An improved DV－Hop localization algorithm with reduced node location error for wireless sensor networks［J］.Communications and Computer Sciences，2008，91(8):2232 －2236.