基于最小包含圆的无线传感器网络定位算法.doc

第11期周全等：基于最小包含圆的无线传感器网络定位算法91基于最小包含圆的无线传感器网络定位算法周全1, 3，朱红松1, 3，徐勇军2，李晓维1（1. 中国科学院 计算技术研究所 计算机系统结构重点实验室，北京 100190；2. 中国科学院 计算技术研究所 传感器网络实验室，北京 100190；3. 中国科学院 研究生院，北京100039）摘 要：提出一种新的无需测距定位算法基于最小包含圆的定位（SECL）。该算法根据目标周围的锚节点所决定的最小包含圆来估计目标位置。基于最小包含圆的算法考虑的不是坐标系中所有锚节点位置的平均值，而是覆盖所有锚节点区域的几何中心，能够有效地控制锚节点分布不均匀给定位带来的负面影响。仿真结果显示，相对于质心算法平均定位精度能提高10%以上。SECL在锚节点拓扑不均匀情况下，精度提升更高。关键词：无线传感器网络；最小包含圆；定位；无需测距中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)11-0084-07Smallest enclosing circle based localizationapproach for wireless sensor networksZHOU Quan1, 3, ZHU Hong-song1, 3, XU Yong-jun2, LI Xiao-wei1（1. Key Laboratory of Computer System and Architecture, Institute of Computing Technology, Chinese Academy of Science, Beijing 100190,China; 2. Laboratory of Sensor Network, Institute of Computing Technology, Chinese Academy of Science, Beijing 100190, China; 3. Graduate School, Chinese Academy of Science, Beijing 100039,China）Abstract: A novel range-free localization approach-smallest enclosing circle based localization (SECL) has been proposed. This approach estimates the position of target by the center of smallest enclosing circle of neighboring anchor nodes. Comparing to centroid, SECL considers the geometrical coverage center of anchors rather than the geometrical mass center of them. Consequently, SECL is more robust when the topology of anchors is not uniform. Simulation results show that SECL outperforms centroid by an average of 10%, and even better when the topology is not uniform.Key words: wireless sensor networks; smallest enclosing circle; localization; range-free1 引言收稿日期：2008-06-28；修回日期：2008-10-22基金项目：国家高技术研究发展计划（“863”计划）基金资助项目(2006AA01Z223, 2006AA01Z225)；国家自然科学基金重点资助项目（60633060）Foundation Items: The National High Technology Research and Development Program of China (863 Program)(2006AA01Z223, 2006AA01Z225); The National Natural Science Foundation of China (NSFC)(60633060)无线传感器网络（WSN, wireless sensor network）通过更深层的嵌入、更广泛的采集和更自由的部署，弥补了计算机与真实世界的鸿沟，使人们可以在任何时间对任何地点进行监控。对环境的监控通过信息的采集完成，采集到的数据只有在能够确定感知对象的位置时才有意义。因此，定位是一项必备的网络服务13。除了数据需要打上位置标签以外，位置信息可以优化路由协议。例如，基于地理信息的路由协议47依赖执行“存储转发”工作的路由节点位置信息作出路由决策。本文提出一种新的无需测距定位算法基于最小包含圆的定位（SECL, smallest enclosing circle-based localization）算法。该算法根据目标周围处于通信范围内的锚节点构建最小包含圆（SEC, smallest enclosing circle），使用SEC圆心估计目标节点的位置。SECL算法的基本思想是采用几何空间上覆盖所有锚节点的区域来估计目标位置。这种以几何覆盖为依据的定位方法，可以有效地控制由于锚节点分布不均匀给定位精度带来的波动。扩展版本的基于最小包含圆的定位（E-SECL, extended SECL）算法增加了调节通信半径的功能。在目标落入锚节点分布不均的区域时，根据锚节点的拓扑形态调节通信半径，克服小范围内锚节点不均匀的问题。2 以往的工作无线传感器网络定位方法分为基于测距的（range-based）和无需测距的（range-free）定位两类，或者叫做细粒度（fine-grained）和粗粒度（coarse grained）定位8。2.1 基于测距的定位基于测距的定位通过测量距离进行定位，如接收信号强度（RSSI）、信号传播时间（TOA、TDOA、RTOF）、接收信号方向（AOA）等。基于测距的定位一般精度较高，但是需要额外的测量设备。RSSI定位需要检测信号强度的电路和信号与距离的关系模型。以信号传播时间作为测距手段需要配备低速度信号的收发设备（如超声波收发器等）。接收信号方向的测距方法需要定向天线或者天线阵列。2.2 无需测距的定位Cell-ID、Centroid8、DV-HOP9,10、E-CDL11和APIT12等定位机制，实现了无需测距的粗粒度定位。这些定位机制使用相邻接节点之间的连通关系进行定位，而不是使用测量的距离或者方向数据。例如，Cell-ID是用最靠近移动终端的基站所处的位置估计移动终端的位置。无需测距的定位方法定位精度较低并且与锚节点密度有关，某些场合需要大量的节点才获得满意的定位精度。一般认为提高节点的密度，定位精度会随之提高。但是，成本、功耗和通信开销呈指数级上升，下面的仿真结果显示，参与的节点达到一定数量后定位精度不再增长甚至降低。2.3 介于测距与不测距之间的定位一些无需测距的定位方法，如DV-HOP 9、MDS等，使用RSSI作为辅助手段增强算法的能力，衍生出新的算法，如RADAR RSSI Map13、DV-Distance10、Amorphous14、NMDS15、LeManCoR16、W-Centroid 17和基于MeanShift的定位算法18。RSSI除了用来计算距离外，也用来比较距离远近。Yedavalli等提出Ecolocation算法19，考察不同参考节点的RSSI测量序列，确定未知节点的位置。基于Voronoi的定位算法（VBLS）20对k个工作锚节点jk感知的RSSIjk信号强弱进行排序RSSIj1 RSSIj2 RSSIjk。由此推断理想情况下，锚节点与目标的距离与RSSI呈反比关系，有0 Lj1 Lj2Ljk R。以这个距离大小关系作为约束条件进行目标定位。RADAR和LeManCoR属于Manifold流形学习方法。Manifold算法由两个阶段构成：离线模型训练和在线空间搜索。离线模型训练通过位置对应的信号生成模型函数。在线空间搜索阶段根据已经建立的模型函数和在线获得的数据，根据目标函数搜索最优解。RADAR使用“指纹技术”进行定位，建立x, y, d, SS, snri五元组构成的RSSI Map，定位精度达到23m。RADAR方法适用于静态系统，而LeManCoR考虑环境的动态特性。由于重建RSSI Map开销巨大，LeManCoR使用Manifold co-Regularization学习方法重建RSSI map，降低校正模型的开销。无需测距的定位方法除了使用节点的邻接关系以外，还使用链路的其他属性来提高定位精度。这些属性包括锚节点链路上连通度、信噪比、误码率等特性。虽然这些属性无法直接映射成距离，但是通常可以由此得出距离远近的关系。传统上这类定位方法归于无需测距定位一类，如Centroid的连通性矩阵8。总之，充分利用RSSI提供的信号强度信息，在无需测距的粗粒度定位算法基础上，研究具有更高精度和顽健性的算法具有较大的实用价值。3 基于最小包含圆的定位算法良好的定位算法能够适应无线传感器网络拓扑结构的动态特性。本文提出的基于最小包含圆的定位算法根据锚节点的几何覆盖推断目标位置。通过评估当前网络中锚节点的状态，选择足够数量的节点参与定位。在有较多锚节点可选择的时候，根据节点的位置，挑选最合适的部分节点，获得较高的定位精度的，同时消耗较少的电能。3.1 最小包含圆最小包含圆 21是指给定一个平面中n个点的集合S，找出包围它们的最小圆（最小包含圆是惟一的）。它是集合S中三点的外接圆或者是两点作为直径确定的圆。传感器网络中SEC由锚节点位置分布决定，而不是由锚节点的密度决定。SEC对拓扑均匀度不敏感，这是与质心法等以往定位算法最大的区别。这个特性使得基于最小包含圆的定位算法更加适合锚节点分布疏密不均的无线传感器网络场合。暴力方式计算SEC的运算复杂度是O(n4)。Wang等提出算法复杂度为O(|lg(d/8R)|n) 22。SEC算法是利用最远点Voronoi图（FPVD, farthest point voronoi diagram）计算SEC，计算复杂度为O(n log n)。算法程序如下。function SEC(S) if |S| 1 then finish false repeat find p in S maximizing radius(before(p), p, next(p) and angle(before(p), p, next(p) in the lexicographic order if angle(before(p),p,next(p)/2then finish true else remove p from S end if until finish end if return Send function3.2 SECL算法流程SECL计算目标周围通信半径内的工作锚节点（WA, working anchor）决定的最小包含圆，使用最小包含圆的圆心估计目标位置。如图1所示，通信范围内所有的锚节点的一个凸包决定惟一的最小包含圆。SECL算法流程如下。1) 从工作锚节点集合WA计算构成最小包含圆的节点集合S。2) 计算由节点集合S确定的外接圆CC(C, R)。图1 通信范围内工作锚节点决定的最小包含圆3) 外接圆圆心C是目标位置的估计。SECL算法是SECL的伪代码，算法程序如下。function CCC(S) if sizeof(S) = 2 then C center of S R |C S| return (C, R) else Compute Circumcircle CC(C, R) of S return (C, R) end if end function function LOC(S, p) S SEC(WA) (C, R) CCC(S) return C end function3.3 E-SECL算法流程增强的SECL（E-SECL, enhanced SECL）算法在SECL基础上，使用SECL初步计算目标位置，评估目标位置周围的WA分布均匀程度，根据情况考虑扩大通信半径，以获得更高的精度。胡东红等23根据王元、方开泰24提出的均匀性判定准则，定义了节点间f距离、g距离和理想布点情况下的标准半径，由此定义最大空穴半径和最小孔穴半径，并提出了密集性和稀疏性偏差(discrepancy)的概念。E-SECL采用密集性和稀疏性偏差评估局部锚节点的均匀度。SECL算法流程如下。1) 执行SECL算法，得到位置估计C。2) 根据C计算均匀性参数Dd、Ds、D。3) 若D Dbound，计算结束。否则，根据Ds找到最大空穴Ccav(Ccav, Rcav)。4) 增大通信半径， 保证C到Ccav方向上在Ccav的距离为R处有邻居节点。5) 重新执行SECL算法，得到位置估计C。E-SECL考察工作锚节点WA的均匀性，当自偏差高于Dbound的时候，找出最大的空穴Ccav(Ccav, Rcav)，增大通信半径引入更多WA，并且使锚节点覆盖到最大空穴的外侧。重新运行SECL后，计算出新的位置估计值。参数Dbound默认值是0.3，表示自偏差是0.3，最小空穴半径与最大空穴半径比是3:10。参数Dbound可以根据精度要求和节点实际部署条件调节。在节点拓扑结构和数量不变的时候，可以离线计算Dd、Ds、D，提高算法速度。3.4 算法分析SECL算法表达了锚节点在平面空间的覆盖，比Centroid等算法更好地反映目标所在的位置。本文选择一个典型的非均匀拓扑形态来说明不同算法对锚节点均匀程度的影响。图2显示了不同通信半径的定位结果。目标处于一个锚节点不均匀的环境，左上部锚节点分布密集，右下部锚节点分布稀疏，有较大的空穴。图2(a)与图2(b)显示了通信半径140m和160m的定位情况。通信半径为140m时，SEC圆心与质心估计的目标位置接近，最小包含圆完整地覆盖了目标周围的区域，SEC圆心对目标的估计明显优于Centroid估计。这个例子说明了SEC克服了参考节点不均匀影响，提高了定位精度。图2 不同行通信范围对定位算法的影响扩大通信半径是提高Centroid定位精度的一种常用方法。但是扩大通信半径，引入更多的锚节点并不是总能够提高精度，有时甚至出现相反效果。如图3所示，通信半径分别是100m、120m、一直到200m条件下Centroid和SECL的定位结果。图3(a)显示了随着通信半径递增，Centroid定位结果逐步远离目标，定位精度不但没有提高，反而降低了。图3(a)的现象是因为Centroid扩大通信半径的时候，原先锚节点密集的左上部引入了更多锚节点，而右下部孔穴处没有锚节点加入，或者有一两个锚节点加入，但是对于整个锚节点的质心位置贡献不明显。锚节点的中心出现了向左上部移动的趋势。图3(b)显示了随着通信半径递增，SECL定位算法对目标的估计位置经历了逐步远离目标实际位置，再逐步靠近目标的过程。图3(b)的情况可以通过图2解释。如图2(a)所示，通信半径开始增大的时候，决定最小包含圆的参考节点集中在目标的右上方。随着通信半径增大，右下部孔穴外侧逐步有新的锚节点成为工作锚节点。如图2(b)所示，虽然右下角的参考节点对于质心影响不大（Centroid估计精度不会发生较大改善），但是可以很好地修正覆盖的不均衡，迅速提高了SECL的定位精度。图3 扩大通信半径的定位效果4 仿真结果4.1 信号的传输模型无线电传播信号传输模型通常根据实际测量修正理想物理模型得到。常用的模型有三类：Free-space模型、Two-ray ground reflection模型和Shadowing模型。其中最常用的是Shadowing模型（Okumura-Hata模型）。在d0m处的功率是PLd0dBm，则在dm的功耗是 (1)其中，是射频信道衰减指数，由大量的现场测量确定。在自由空间， = 2。在城市或者郊区，的值一般在3到6之间。X是方差为的对数功率误差。两类因素导致无线电的不规则性：器件特性和传播介质。器件特性的因素包括：天线类型、发送功率、天线增益、接收灵敏度和信噪比阈值等。介质特性的因素包括：介质类型、背景噪声和其他环境因素，如温度、障碍物等，其中最主要的因素是各向异性的路径衰减、不均匀的发送功率。由于存在误差，式（1）定义的各向同性理想模型与实际测量信号之间存在很大的偏差。节点的信号强度在不同方向存在不可忽略的不规则性。当这种不规则性比较严重的时候，对MAC层协议、路由层协议、定位精度都有很大的影响，甚至是关键因素。Zhou等在文献25介绍了的相应的无线电信号不规则（RIM, radio irregularity model）模型如下：(2)式(3)根据式(1)和式(2)修正了各向同性假设下的不同方向上的通信半径。因此，式(1)修正为(3)如图4所示的拓扑，显示了DOI=0.1，通信半径为160m时的通信范围。本节的仿真实验使用这个更加精细的模型来评估各种定位算法的性能。图4 不规则无线电模型（通信半径160m, DOI=0.1）文献25介绍了随着DOI的增加，Centroid定位误差呈线性增加。DOI=0.015时，16个参考节点定位的精度与DOI=0.005时8个参考节点定位的精度大致相等。无线电的不规则性导致了参考节点在信号模型意义下的空间分布与欧氏空间分布不一致，地理上靠近的节点，信号强度未必大，反之亦然。由此引入的误差抵消了增加参考节点的优势。真实环境下的无线电不规则性，是基于RSSI的定位算法和其他相关定位算法都不可忽视的因素。尤其在精度、参与定位参考节点数目、功耗等方面进行权衡的时候，只有采用最贴近实际情况的无线电信号模型，才能保障算法的有效性和顽健性。4.2 仿真环境假定信道衰减模型符合Shadowing模型，为了更加精确地描述信道特性，使用式(3)定义的Shadowing模型和RIM模型的组合。在800m800m的范围内随机撒布200个锚节点，构成如图1所示的拓扑。图2显示了选择140m和160m通信半径，采用多种定位算法的定位结果。4.3 仿真结果图5显示了三种无需测距的定位：Cell-ID、Centroid和SECL/E-SECL的800m800m范围内随机挑选200个位置放置目标的平均定位精度。Cell-ID是蜂窝电话系统中最简单的定位方法，使用最靠近的基站位置估计移动终端的位置。将这种方法引入无线传感器网络，使用RSSI信号最强的锚节点的位置估计目标的位置。Centroid方法采用锚(a) 定位绝对误差(b) 定位相对误差图5 定位误差比较(根据参考节点半径归一化)节点几何重心估计目标位置。SECL/E-SECL方法采用锚节点几何覆盖中心估计目标位置。仿真结果显示，Cell-ID在100m以后精度不随通信半径变化。Centroid和SECL在160m附近取得最优定位精度，在到达最优定位精度后相对定位精度不再提高，绝对定位精度下降。SECL定位精度明显优于Centroid，平均超过Centroid达到10%以上。5 结束语由于传感器节点随机地部署到现场，部署受到地理环境的制约，WSN网络中的锚节点通常不能做到均匀分布。随着时间的推移，电池供电的节点逐渐耗尽电能，偶然出现的干扰源，会使网络节点暂时失效。这些因素决定了WSN网络运行过程中节点拓扑处于非稳定状态。现有的定位方法使用位置已知或者部分位置已知的锚节点，对位置未知的节点或者目标进行定位。当锚节点在通信范围内分布不均匀的时候，定位算法精度因为这个原因产生很大波动。本文提出了SECL算法基于锚节点完全覆盖的几何中心估计目标位置，对锚节点拓扑的非均匀特性不敏感，适合节点拓扑具有动态特性的无线传感器网络和其他自组织网络。定位精度优于Centroid等方法。SECL和Centroid一样需要足够的通信范围才能达到最优的定位精度，超过这个最优通信半径后出现绝对定位精度恶化。因此，未来需要设计决定最优通信半径的算法，保证SECL在定位过程中选择合理的通信半径，达到精度和功耗的最优化。参考文献：1任丰原, 黄海宁, 林闯. 无线传感器网络J. 软件学报, 2003,14(7): 1282-1291.REN F Y, HUANG H N, LIN C. Wireless sensor networksJ.Journal of Software, 2003,14(7): 1282-1291.2王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法J. 软件学报, 2005,16(5): 857-868.WANG F B, SHI L, REN F Y. Self-localization systems and algorithms for wireless sensor networksJ. Journal of Software, 2005,16(5): 857-868.3崔莉, 鞠海玲, 苗勇等. 无线传感器网络研究进展J. 计算机研究与发展, 2005,42(1): 163-174.CUI L, JU H L, MIAO Y, et al. Overview of wireless sensor networksJ. Journal of Computer Research and Development, 2005,42(1): 163-174.4KO Y B, VAIDYA N H. Location-aided routing (LAR) in mobile ad hoc networksJ. Wireless Networks, 2000,4(4): 307-321.5XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routingA. Proceedings of MobiCom01C. Rome, Italy, 2001.70-84.6KARP B, KUNG H T. GPSR: greedy perimeter stateless routing for wireless networksA. Proceedings in MobiCom00C. New York, NY, USA, 2000.243-254.7YU Y, GOVINDAN R, ESTRIN D. Geographical and Energy Aware Routing: a Recursive Data Dissemination Protocol for Wireless Sensor NetworksR. UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023, 2001.8BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less low cost outdoor localization for very small devicesJ. IEEE Personal Communications Magazine, 2000,7(5): 28-34.9NICULESCU D, NATH B. Ad hoc positioning system (APS)A. Proceedings in GLOBECOM 2001C. Texas, USA, 2001.2926-2931.10NICULESCU D, NATH B. DV-based positioning in ad hoc networksJ. Kluwer Journal of Telecommunication Systems, 2003,22(1): 267-280.11CHANG T C, WANG K, HSIEH Y L. Enhanced color-theory-based dynamic localization in mobile wireless sensor networksA. Proceedings in WCNC 2007C. Hong Kong, China, 2007. 3064-3069.12HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networksA. Proceedings in MobiCom03C. San Diego, CA, USA, 2003.81-95.13BAHL P, PADMANABHAN V N. RADAR: an in-building RF-based user location and tracking systemA. Proceedings of IEEE INFOCOM 2000C. Aviv, Israel, 2000.775-784.14RADHIKA N, HOWARD S, JONATHAN B. Organizing a global coordinate system from local information on an ad hoc sensor networkA. Proceedings of IPSN03C. Palo Alto, CA, USA, 2003. 333-384.15肖玲, 李仁发, 罗娟. 基于非度量多维标度的无线传感器网络节点定位算法J. 计算机研究与发展, 2007,44(3): 399-405.XIAO L, LI R F, LUO J. A sensor localization algorithm in wireless sensor networks based on nonmetric multidimensional scalingJ. Journal of Computer Research and Development, 2007,44(3): 399-405. 16PAN S J, KWOK J T, YANG Q, PAN J J. Adaptive localization in a dynamic WiFi environment through multi-view learningA. Proceedings in AAAI 2007C. Vancouver, British Columbia, 2007.1108-1113.17SHEN X, WANG Z, JIANG P, et al. Connectivity and RSSI based localization scheme for wireless sensor networksA. Proceedings of ICIC 2005, Advances in Intelligent ComputingC. LNCS 3645, Hefei, China, 2005. 578-587.18周全, 徐勇军, 李晓维. 一种分布式无需测距的定位算法A. CWSN 2007论文集C. 中国哈尔滨, 2007.93-96.ZHOU Q, XU Y J, LI X W. A distributed range-free localization mechanism for wireless sensor networksA. CWSN 2007C. Harbin, China, 2007.93-96.19YEDAVALLI K, KRISHNAMACHARI B, RAVULA S, et al. Ecolocation: a sequence based technique for RF localization in wireless sensor networksA. Processings of IPSN 2005C. Los Angeles, CA, USA, 2005.285-292.20王继春, 黄刘生, 徐宏力等. 基于voronoi图的无需测距的无线传感器网络节点定位算法J. 计算机研究与发展, 2008,45(1): 199-125.WANG J C, HUANG L S, XU H L, et al. A novel range free localization scheme based on voronoi di