基于功率控制和邻居信息的距离无关定位算法

史 昕，张玲华

(1.南京邮电大学通信与信息工程学院，江苏南京 210003；2.南京邮电大学物联网学院，江苏南京 210003)



基于功率控制和邻居信息的距离无关定位算法

史 昕1，张玲华2

(1.南京邮电大学通信与信息工程学院，江苏南京 210003；2.南京邮电大学物联网学院，江苏南京 210003)

针对无线传感器网络节点自定位问题，提出了一种基于锚节点功率控制和邻居信息的距离无关定位算法——AP&NI(Anchor Power-control and Neighbor Information)。该算法可分为距离估计和位置计算两个阶段：在距离估计阶段，未知节点通过锚节点功率控制和邻居节点部署信息获得自身到锚节点的近似距离；在位置计算阶段，未知节点根据得到的近似距离的个数运用不同的方法计算自身的坐标。Matlab仿真结果表明，与DV-Hop算法和部分改进算法相比，AP&NI算法能有效减少近似距离的误差，提高定位精度。仿真还显示在各向异性的网络中，AP&NI算法克服了DV-Hop算法的缺点，依然保持良好的定位精度。

无线传感器网络；定位算法；功率控制；邻居节点信息；定位精度

0 引言

对于绝大多数无线传感器网络应用来说，不携带位置信息的监测数据通常是毫无作用的。但无线传感器网络常常部署在条件恶劣的区域而且网络中的节点随机分布，这使得节点无法预先得知自身的位置信息。因此，研究传感器节点的自定位算法是无线传感器网络技术中一项关键的挑战[1]。

目前，无线传感器网络定位算法可以分为基于距离和距离无关两类。前者通过额外设备获得点到点之间的距离来计算未知节点位置；而后者只通过连通度或跳距数等来实现定位，因此它相比于前者具有实现简单和成本低的优势[2]。

距离无关定位算法中的未知节点通常通过两类主要的方法得到自身的估计位置[3]：一类是找出所有包含未知节点的可能位置区域，将重叠区域的质心作为估计坐标，典型的算法有APIT(Approximate Point-In-Triangulation)、Bounding Box等；另一类方法是在未知节点获得到多个锚节点的近似距离之后，运用极大似然估计等方法计算估计坐标，这一类典型的算法有DV-Hop和Amorphous等。前者方法的定位精度较为依赖于网络中的锚节点密度，后者方法的性能则受网络部署环境的影响较大[4]。文中提出的基于锚节点功率控制和邻居信息的距离无关定位算法AP&NI(Anchor Power- control and Neighbor Information)的中心思想与后者相似，通过使用锚节点功率控制技术以及邻居节点分布信息，AP&NI算法不仅提高了近似距离的估计精度，而且增加了在不同环境下的精度稳定性。仿真显示，AP&NI算法与DV-Hop算法和部分改进算法相比无论是在各向同性还是各向异性的网络中均具有较高的定位精度。

1 相关工作

1.1 基于DV-Hop的改进算法

DV-Hop算法[5]的核心思想是用最小跳数与平均每跳距离的乘积代替未知节点到锚节点的近似距离。该算法在节点密度高，节点分布较均匀的网络中可以得到较高的定位精度。但当网络的部署环境不满足上述条件或运用在各向异性的网络中时，DV-Hop算法的定位精度将会有较大恶化。针对DV-Hop算法的问题，研究人员在传统DV-Hop算法的基础上提出了许多改进算法。文献[6]针对单个锚节点估计的平均每跳距离误差较大的缺点，提出了一种基于加权处理平均每跳距离的算法(Weight-DV-Hop)。该算法根据未知节点距锚节点的跳数进行加权，跳数越小权值越大，增加了平均每跳距离的准确度。文献[7]采用每跳分级和修正平均每跳距离的方法对DV-Hop算法进行了改进。文献[8]从升级未知节点为锚节点、运用二维双曲线算法以及引入量子行为粒子群算法三方面增加了定位精度。文献[9]通过离线建立最小每跳长度表来判断一条路径的可靠性，减少网络的不规则性对距离估计的影响。文献[10]针对DV-Hop算法在各向异性的网络中定位精度恶化的缺点，提出了“友好”锚节点集的概念，未知节点到锚节点的估计距离误差由于“友好”锚节点集的引入而有所降低。

1.2 锚节点功率控制模型

假设传感器节点拥有理想的圆形无线信号传播模型，则节点通过功率控制在不同的功率等级下发射信号，通信区域为若干个半径不同的同心圆。众多新颖的无线传感器网络定位算法都引入了节点功率控制技术，这些算法有的通过缩小未知节点可能位于的区域来达到提高定位精度的目的[11-12]，有的则利用不同的通信半径修正近似距离，从而提高定位精度[13-14]。

AP&NI算法中的锚节点功率控制模型如下：

(1) 假定传感器节点拥有理想的圆形无线信号传播模型，未知节点的通信半径为r。

(2) 锚节点在部署前预先设置1、2、3三个不同的发射功率等级，相对应的通信半径分别为r，2r，3r。

2 AP&NI算法的定位原理

AP&NI定位算法由两个阶段组成：第一阶段是基于锚节点功率控制和邻居信息的距离估计阶段；第二阶段是基于不同近似距离个数的位置计算阶段。

2.1 距离估计阶段

在距离估计阶段，网络中的锚节点依次以1、2、3功率等级发送信标信号，其中含有锚节点自身的ID、坐标信息以及功率等级p，接收到的邻居节点只记录对应锚节点的最小功率等级，抛弃来自相同锚节点的较大功率等级。如图1所示，对应锚节点A，未知节点B只记录功率等级2而抛弃功率等级3。

图1 距离估计阶段原理图

在AP&NI算法中，一个未知节点到一锚节点的近似距离由最小距离MinDis和相对距离RelaDis两部分组成，如图1所示，其中最小距离为未知节点相对该锚节点的功率等级p减1后与通信半径r的乘积。则在图1中，未知节点B到锚节点A的近似距离dBA为：

dBA=MinDisBA+RelaDisBA=r×(pBA-1)+RelaDisBA

(1)

式中：pBA为未知节点B相对锚节点A的功率等级;r为未知节点的通信半径。

同理可得：

dCA=MinDisCA+RelaDisCA=r×(pCA-1)+RelaDisCA

(2)

当多个未知节点相对一锚节点的功率等级均为p时，如果一个未知节点拥有越多的相对该锚节点功率等级为p+1的邻居节点，则从概率上可以认为该未知节点距离锚节点越远，即相对距离RelaDis越大。在图1中，未知节点B和C相对锚节点A的功率等级均为2，但节点B的邻居节点中有4个节点相对锚节点A的功率等级为3，而节点C的邻居节点中只有2个节点相对锚节点A的功率等级为3，因此可以得出RelaDisBA大于RelaDisCA。

文中将功率等级为p+1的邻居节点个数称为外环点数OuterNode，于是找出外环点数与RelaDis之间的对应关系成为计算近似距离的重点。一个网络的部署参数在部署前很容易得知，AP&NI算法根据预知的网络部署参数通过计算机仿真的方法得到一张OuterNode与RelaDis之间的对应表，并将该表储存到每个未知节点中供其距离估计阶段使用。根据不同的网络部署参数，AP&NI算法需在部署前仿真不同的对应表。表1给出了对应表的一个范例，该表的仿真参数如下：部署区域为100 m×100 m的正方形，总节点数为100个，r为20 m，表中的RelaDis值是500次仿真的平均。

表1 OuterNode与RelaDis对应表

如果图1中的传感器节点实际部署的区域范围、总节点数、以及未知节点通信半径均与表1的仿真参数相同，则RelaDisBA的值为表中4对应的14.100 0 m，RelaDisCA的值为表中2对应的11.373 0 m，即近似距离dBA和dCA分别为：

(3)

2.2 位置计算阶段

未知节点在位置计算阶段根据储存的近似距离个数被分为以下4种情况：

(1)当拥有到3个或3个以上锚节点的近似距离时，未知节点利用极大似然估计法计算自身坐标。

(2)当拥有到2个锚节点的近似距离时，未知节点首先计算出两个候选坐标，然后利用已经定位的邻居未知节点通过质心算法计算出一个参考坐标，未知节点将离参考坐标较近的候选坐标作为自身的估计坐标。

(3)当拥有到1个锚节点的近似距离d时，未知节点的坐标计算如图2所示。未知节点首先利用已经定位的邻居未知节点通过质心算法计算出一个参考点R，然后在射线AR上取距离锚节点A长度为d的点，未知节点将该点作为自身的估计坐标。估计坐标(xe,ye)可由式(4)得到：

(4)

式中：xR,yR为参考点R的坐标；xA，yA为锚节点A的坐标。

图2 近似距离数为1的位置计算原理图

(4)当储存的近似距离个数为0时，未知节点将已经定位的邻居未知节点坐标的质心作为自身的估计坐标。

2.3 算法步骤

第一步：在网络部署前，依据网络部署参数运用计算机仿真得出OuterNode与RelaDis对应表，每个未知节点储存该表。

第二步：网络部署后，所有锚节点依次发送1、2、3三个不同功率等级的信标信号，其中包括锚节点ID、坐标信息以及功率等级p，接收节点只记录对应锚节点的最小功率等级，抛弃来自相同锚节点的较大功率等级。

第三步：未知节点计算相对不同锚节点的外环点数并根据预先储存的OuterNode与RelaDis对应表通过式(1)计算到不同锚节点的近似距离。

第四步：未知节点根据记录的近似距离的个数，按照从大到小的顺序分别通过2.2节描述的方法计算自身估计坐标。

3 算法仿真与性能分析

为了全面分析AP&NI定位算法的性能，本节在各向同性的网络和各向异性的网络两种环境下进行了仿真实验。对于各向同性的网络，仿真区域为100 m×100 m的正方形；对于各向异性的网络，仿真采用C型网络和S型网络[10]。为了确保数据的说服力，仿真中每组参数运行300次，仿真结果为300次实验的平均值。

3.1 各向同性网络

在各向同性网络中，本文将DV-Hop算法、Weight-DV-Hop算法、文献[13]中的LPC(Localization with the Power Control)算法以及AP&NI算法进行了仿真对比。LPC算法中的传感器节点配置2种通信半径，分别为r和1.5r。当100个传感器节点随机部署在正方形区域内时，图3给出了在未知节点通信半径固定为20 m，锚节点密度增加的情况下4种算法的定位误差。从图3可以看出，4种算法的定位误差均随着锚节点密度的增加而有所下降且AP&NI算法的定位误差明显低于DV-Hop算法、Weight-DV-Hop算法和LPC算法。以锚节点密度为10%为例，此时AP&NI算法的定位误差为0.40，相比DV-Hop算法，Weight-DV-Hop算法和LPC算法定位误差分别降低了24.1%、19.7%和10.9%。此外，从图3可以看出，当锚节点密度大于15%后，AP&NI算法的定位精度受锚节点密度的影响程度明显减弱，相对其他3种算法的优势也趋于稳定。

图3 不同锚节点密度下的定位误差对比图

图4和图5分别是不同总节点数和不同未知节点通信半径对定位误差的影响。图4中锚节点密度为10%，未知节点通信半径为20 m；图5中总节点数为100，锚节点密度为10%。从图4和图5可以看出，随着总节点数或未知节点通信半径的增加，AP&NI算法的定位误差始终低于DV-Hop算法、Weight-DV-Hop算法和LPC算法，且当总节点数或通信半径较小时，AP&NI算法的优势相比DV-HOP算法和Weight-DV-Hop算法尤为显著。这是因为当网络中总节点数或通信半径较小时，网络的连通性变差，使得DV-Hop和Weight-DV-Hop算法的距离估计精度出现恶化，但AP&NI算法有效地避免了这一不足。经计算可得，随着总节点数的增加，AP&NI算法的定位误差相比DV-Hop算法、Weight-DV-Hop算法和LPC算法分别对应降低了49.6%～23.5%、43.0%～18.5%和25.6%～10.7%。随着未知节点通信半径的增加，定位误差分别对应降低了36.0%～11.4%、32.7%～8.4%和18.7%～6.4%。

图4 不同总节点数下的定位误差对比图

图5 不同通信半径下的定位误差对比图

3.2 各向异性网络

在各向异性的网络中，本文将DV-Hop算法、文献[10]算法以及AP&NI算法进行了仿真对比。当总节点数为100，未知节点通信半径固定为20 m，锚节点数从10增加到35时，图6和图7分别给出了在C型网络和S型网络两种情况下3种算法的定位误差。从这两幅图可以看出，在C型网络和S型网络中，DV-Hop算法的定位误差明显增大，分别达到了120%和200%左右。但AP&NI算法依然保持良好的定位精度，与各向同性的网络相比基本持平。这时因为AP&NI算法没有使用最小跳数，避免了路径迂回带来的精度恶化。经计算得知，AP&NI算法与DV-Hop相比定位误差在C型网络和S型网络中分别平均下降约69%和83%。此外，文献[10]的算法虽然一定程度上能降低DV-Hop算法在各向异性网络中的定位误差，但定位精度明显低于AP&NI算法，AP&NI算法与文献[10]算法相比定位误差在C型网络和S型网络中分别平均下降约41%和61%。

图6 C型网络中的定位误差对比图

图7 S型网络中的定位误差对比图

4 结束语

AP&NI算法将未知节点到锚节点的近似距离分为最小距离和相对距离两部分，最小距离由锚节点功率控制技术确定，相对距离由外环点数与相对距离对应表确定。但该距离估计方法并不能保证每个未知节点均获得到多个锚节点的近似距离，因此需要引入不同的位置计算方法来进一步提高定位精度和定位覆盖率。仿真结果表明，在各向同性和各向异性的网络中，AP&NI算法均具有明显的优势。但对于部署区域中的边缘节点，由于外环点数信息的不准确，因此这类节点的定位精度还有待提高，如何解决这一问题是今后研究的重点。

[1] YANG Z,LIU Y.Understanding node localizability of wireless ad hoc and sensor networks.IEEE Transactions on Mobile Computing,2012,11(8): 1249-1260.

[2] 冀常鹏，陈美玲，刘巧.无线传感网络APIT定位算法的改进.仪表技术与传感器,2012(8): 84-86.

[3] CHEN C C,CHANG C Y,LI Y N.Range-free localization scheme in wireless sensor networks based on bilateration.International Journal of Distributed Sensor Networks,2013: 1-10.

[4] LEE J,CHUNG W,KIM E.A new range-free localization method using quadratic programming.Computer Communications,2011,34(8): 998-1010.

[5] NICULESCU D,NATH B.DV based positioning in ad hoc networks.Journal of Telecommunication Systems,2003,22(14): 267-280.

[6] 刘峰,张翰,杨骥.一种基于加权处理的无线传感器网络平均跳距离估计算法.电子信息学报,2008,30(5): 1222-1225.

[7] 张爱清,叶新荣,胡海峰,等.基于RSSI每跳分级和跳距修正的DV-HOP改进算法.仪器仪表学报,2012,33(11): 2552-2559.

[8] 赵吉,傅毅,王瀚波.改进的DV-Hop无线传感器网络定位算法.仪表技术与传感器,2013(6): 111-114.

[9] XIAO B,CHEN L,XIAO Q,et al.Reliable anchor-based sensor localization in irregular areas.IEEE Transactions on Mobile Computing,2009,9(1): 60-72.

[10] LIU X,ZHANG S,WANG J,et al.Anchor supervised distance estimation in anisotropic wireless sensor networks.Proceedings of IEEE Wireless Communications and Networking Conference,Cancun Mexico,2011.

[11] VIVEKANANDAN V,WONG V W S.Concentric anchor beacon localization algorithm for wireless sensor networks.IEEE Transactions on Vehicular Technology,2007,56(5): 2733-2744.

[12] 闫斌,周小佳,王厚军，等.无线传感器网络功率控制的质心定位算法.电子科技大学学报,2010,39(3): 416-419.

[13] LIAO W H,SHIH K P,LEE Y C.A localization protocol with adaptive power control in wireless sensor networks.Computer Communications,2008,31(10): 2496-2504.

[14] AHN H,HONG J.DV-hop Localization Algorithm with Multi- Power Beacons under Noisy Environment.Proceedings of 2011 Third International Conference on Ubiquitous and Future Networks,New York,2011.

Range-free Localization Algorithm Based on Power-control andNeighbor Information

SHI Xin1,ZHANG Ling-hua2

(1.College of Telecommunications & Information Engineering,Nanjing Universityof Posts and Telecommunications,Nanjing 210003,China;2.College of Internet of Things,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

To solve the node self-localization problem in Wireless Sensor Network (WSN),a range-free localization algorithm using anchor power-control and neighbor information (AP&NI) was proposed.AP&NI algorithm can be divided into distance estimation phase and position calculation phase.In distance estimation phase,unknown node gets the approximate distances between itself and anchors by anchor power-control and deployment information of neighbor nodes.In position calculation phase,unknown node uses different approaches to calculate its own coordinate,according to the number of approximate distances.Matlab simulation results show that,compared with DV-Hop and some improved algorithms,AP&NI algorithm reduces the error of approximate distance effectively and improves localization accuracy.AP&NI algorithm overcomes the shortcomings of DV-Hop algorithm and maintains good localization accuracy in anisotropic network.

wireless sensor network;localization algorithm;power-control;neighbor node information;localization accuracy

江苏省普通高校研究生科研创新计划项目(CXLX13_461)

2014-02-12 收修改稿日期：2014-10-09

TP393

A

1002-1841(2015)03-0074-04

史昕(1990— )，硕士研究生，主要研究领域为无线传感器网络。E-mail:sx839075741@163.com 张玲华(1964— )，教授，博士生导师，主要研究领域为语音处理与现代语音通信、无线通信中的信号处理。 E-mail:zhanglh@njupt.edu.cn