无线传感器网络距离无关定位算法研究

2009年第 1O期 计 算 机 与 现 代 化 JISUANJI Y U XIANDAIHUA 总第 170期 文章编号 ：1006-2475(2009)10-0006-04 无线传感器网络距离无关定位算法研究 许秀兰 (常熟理工学院计算机科学与工程学院，江苏 常熟 215500) 摘要 ：网络 自身定位问题是无线传感器网络的基本和重要问题之一。由于range—based定位机制的局限性，无需配置测距 或测角设备，硬件成本低的距 离无关定位算法被提出。根据是否有无锚节点来论述和比较现有的距 离无关定位算法，提 出距离无关定位算法需进一步研究解决的问题。 关键词：无线传感器网络；节点定位；距 离无关定位；定位算法；定位 系统 中图分类号：TP301 文献标识码 ：A doi：10．3969／j．issn．1006-2475．2009．10．003 Research on Range-free Localization Algorithm in Wireless Sensor Networks XU Xiu．1an (School of Computer Science and Engineering，Changshu Institute of Technology，Changshu 215500，China) Abstract：Node localization is a fundamental and crucial issue for Wireless Sensor Network(WSN)．In view of the limitations of range—based techniques，range—free localization scheme is proposed．Existing range—free localization approaches are discussed and presented in detail，and the performance of them are compared．Finally，future works in the field of range—free localization algo— rithm ale pointed out． Key words：Wireless Sensor Networks(WSN)；node localization；range—free localization；localization algorithm；positioning system 0 引 言 随着无线通信技术、嵌入式计算技术和传感器技 术的飞速发展和 日益成熟，具有感知、计算和通信能 力的无线传感器网络也随之产生⋯。无线传感器网 络是由密集型、低成本、随机分布的节点组成的，这些 节点受有限功耗、存储能力和计算处理能力的限制， 且主要是通过飞行器撒播、人工部署或火箭弹射等方 式任意散落在被监测区域内，因此一般传感器节点的 位置都是随机的。 在大多数应用中，传感器节点所采集到的数据必 须结合其位置信息才有意义，所以传感器节点定位在 整个传感器网络中占有重要的地位，在事件观测、目 标跟踪、网络重构等方面都是不可缺少的环节。 无线传感器网络中传感器节点定位问题可分为 三类：节点自身定位、目标定位和定位服务。节点 自 身定位是确定节点自身坐标，即节点物理位置的坐标 信息；目标定位是确定目标位置信息，例如目标跟踪 问题；定位服务主要起到知识库的功能，用于回答一 些类似于“实体 x在什么位置?”的问题。本文主要 讨论前者，即节点 自身定位问题。 无线传感器网络节点自身定位的算法根据定位 机制分为：基于测距算法(range—based)和距离无关算 法(range．free)[21。基于测距算法使用到节点之间的 距离或角度，需特定的硬件设备；距离无关算法仅根 据网络连通性等信息实现，无需配置测距或测角设 备，则硬件成本低。距离无关算法虽然网络密度、通 信开销比较大，但在能量、可扩张性以及对硬件要求 上要优于基于测距的算法，所以在目前的定位算法研 究中倍受关注。 1 无线传感器网络距离无关算法 对于无线传感器网络而言，测量节点间距是一项 较困难的任务。硬件成本(仅用于定位的硬件)、能 收稿 日期：2009-04．15 作者简介：许秀兰(1978-)，女，江苏海安人，常熟理工学院计算机科学与工程学院讲师，硕士，研究方向：无线传感器网络。 2009年第 10期 许秀兰：无线传感器网络距离无关定位算法研究 7 量消耗、构成因素、短距离通信等这些因素都很难一 一 顾全到，并且便宜的、不可靠的和有限的资源设备 很难用在基于距离算法方案中来解决定位。 为了克服基于距离定位方案的限制，许多距离无 关的解决方案被提出。距离无关定位算法利用邻居 节点间的连通信息等或估计距离来实现定位，根据有 无锚节点本文把距离无关定位算法分为：基于锚的定 位算法(假设在网络中存在一些已知其 自身位置的 传感器节点，这些节点称为锚节点)和锚无关定位算 法(即无需特殊传感器节点定位)。 1．1基于锚的定位 锚节点的位置可通过 GPS方式或人工部署 ，而 未知节点则依赖节点间的通信信息，通过锚节点的配 合来确定自身位置。目前 比较典型的这类算法有质 心算 法、APIT算 法、DV．Hop算 法 和 不 定 形 算 法等⋯¨。 质心算法 中，未知节点根据接收到的所有锚 节点位置的质心来确定 自身位置。APIT算法H 根据 锚节点的位置，将被测区域划分为若干三角形区域， 采用栅格法来确定未知节点可能的区域。DV—Hop 算法 刮由3步实现：(1)锚节点根据距离矢量路 由 在整个网络广播其 自身位置和跳数的信息包； (2)锚节点根据获得的其它锚节点位置和相隔跳距 来计算网络平均每跳距离，然后将其作为一个校正值 泛洪广播至网络中；(3)未知节点根据接收到的校正 值和跳数来计算与锚节点的距离，当获得与3个或更 多锚节点距离后就通过三边测量法来确定自身位置。 不定形算法(Amorphous)0 采用类似DV—Hop算法的 原理，不同的是在网络部署前离线计算平均每跳 距离。 1．2锚无关定位 锚无关的定位方案利用已知位置的设备在传感 器节点部署的区域产生事件来确定未知节点的位置。 这类事件包括：文献[12]、文献[13]中的光事件或文 献[14]中的无线信息包事件，利用它们(光和无线信 息包)的时空属性，来定位未知节点，并具较高的定 位精度。 1．2．1 Spotlight Spotlight¨ 定位系统的基本思路是在传感器节 点部署的区域产生可控信号，传感器节点利用自身感 应到信号的时间和信号的时空属性来获得自身的位 置。组成结构见图 1。Spotlight定位系统利用 3个函 数，分4步来完成未知节点的定位： (1)Spotlight设备在节点部署的A区域周期性广 播事件函数 E(t)； (2)在事件广播期间，传感器节点记录检测到的 事件时间序列 Ti={t ti2，⋯，t }； (3)事件广播之后，各传感器节点发送自身的检 测时间序列到 Spotlight设备； (4)Spotlight设备使用时间序列 Ti和已知的 E(t) 函数来估计节点i的位置。 其中事件函数 E(t)是 Spotlight系统使用的核心 技术。文献[10]提出了点扫描、线扫描和区域覆盖 3 种不同方法来实现。实验表明对于不同的扫描速度， Spotlight系统对节点的定位误差为 l0～20cm。 Sensor Node i Spotlight Device Event Distribufion Function E(t) Event Distribution Event Detection ．／ Function E『t1 Function D(e) ＼ j ▲ ＼ J T ：{ll，|2 Localization Function UT) I Pi(X，y'z) 图1 Spotlight定位系统结构 1．2．2 Lighthouse 针对加州大学伯克利分校研究的 Smart Dust传 感器网络，Kay Romer等设计了一种独特的激光定位 系统——Lighthouse Location System_】 。一个基站在 60～70米范围内独立实现定位微小的 dust节点。 dust节点由传感器、处理单元、光接收器和角隅 棱镜反射器(Corner—Cube Retroreflector，CCR)等设备 组成。每个 dust节点拥有一个光电探i贝4器和时钟。 基站(Base Station Transceiver，BST)包括可控激光发 射器和成像接收器。Lighthouse定位系统的基站由3 个相互垂直的灯塔(1ighthouse)组成，每个灯塔发射 两条平行的激光束(带宽已知为 b)，并以恒定速率绕 轴旋转。如图2所示。 A1 图 2 Lighthouse定位示意 基站通过下行链路向节点广播。当节点第一次观 测到激光时记录下时间t ；在 t 后，节点观测不到激光 ． ， 8 计 算 机 与 现 代 化 2009年第10期 时记录下时间 t：；当又可观测到激光时记录下时间t，。 据此计算出节点可观测到激光的时间间隔tk =t2一t 和灯塔旋转一周所需时间 ttum=t。一t 。然后节点使用 公式(1)计算自身与灯塔旋转轴的距离。 d 2 sin( 1／2)一2sin(1rtbc ／t ) 通过上述方法，dust节点可获得与相互垂直的3 个灯塔轴的距离，然后以基站为原点确定自身的坐标 位置。实验表明，在二维原型中，以节点到基站的距 离为标准，定位平均精度为2％。 1．2．3 W alking-GPS Walking—GPS【14]定位方案采用配置者(人或其它 可行工具)携带一周期性广播 自身位置的 GPS设备， 传感器节点根据接收到GPS所广播的位置信息来推 断自身的位置。这种定位方法简单、高效。 Walking—GPS定位系统结构主要由两部分软件 组成：GPS微粒和传感器微粒。GPS微粒运行在 Mi— ca2微粒上，用来连接 GPS设备并周期性间隔输出自 身的位置信息。传感器微粒组成部分运行在网络的 所有传感器节点上，用来接收 GPS微粒广播的位置 信息并根据接收的包来确定自身的位置。这种结构 降低了传感器节点上代码和存储数据的大小。通过 这种装置，单一的 GPS微粒能够为整个传感器网络 节点定位，极大地降低了成本。 Walking—GPS定位系统定位过程由两部分组成： (1)传感器节点部署阶段。配置者配带可行的 GPS微粒；GPS微粒周期性广播 自身位置；传感器节 点根据接收的信息来推断自身的位置。 (2)系统初始化阶段。当传感器节点无法定位 时，将从邻居节点获得它们的位置信息。从邻居节点 接收到的位置信息用三角测量方式来得出自身位置。 这一阶段主要用来提高定位的精度。 实验表明，在5×6栅格中部署 30个 Mica2微粒 的情况下，平均定位误差为0．8M。 2 range-free定位算法比较 上述几种具有代表性的距离无关定位算法中，锚 无关的距离无关定位算法在成本、定位精度和通信开 销方面均优于基于锚的距离无关定算法，但需借助已 知位置的事件 ，如 Spotlight和 Lighthouse中的光事件 或 Walking．GPS中的无线信息包事件。基于锚的距 离无关定位算法无需任何基础设施，但需依赖锚节 点。各算法比较见表 1。 表 1 几种距离无关定位算法的比较 算法 定位精度 节点密度 锚节点密度 网络成本 通信开销 质心 一般 不受影响 影响较大 高 最小 DV—Hop 良好 影响较大 影响较小 低 最大 Amorphous 良好 影响较大 影响较大 中 大 A PlT 良好 影响较小 影响最大 中 小 Spotlight 好 不受影响 无需锚 中 小 Lighthouse 较好 不受影响 无需锚 中 小 Walking—GPS 较好 不受影响 无需锚 低 小 3 展 望 本文主要分析了无线传感器网络距离无关定位 算法，重点对3种锚无关的距离无关定位算法进行详 解，并对几种算法进行了比较分析。对于无线传感器 网络而言，节点定位是一个复杂而重要的问题。随着 无线传感器网络的发展，节点定位具有挑战性研究主 要包括以下几个方面： (1)假设。在假设条件下许多算法才得以实现， 这些假设条件降低了定位实际问题的复杂性，但同时 也存在这些假设并不总能满足实际情况的问题 ，例 如：无线通信圆形范围、对称的无线连通性、额外硬件 (如超声波)、非视线关系、无障碍、无多路径和平坦 地形等这些假设情况。 (2)定位协议设计。定位协议中考虑的大量参 数使得无线传感器网络定位问题更加复杂化了。通 常这些参数包括：传感器网络的配置方法、传感器节 点与远处中心点间存在的视线关系、定位解决的需求 时间、网络中存在的参考节点(即锚节点)和参考节 点密度、额外硬件(形成因素)和能量消耗(信息交换 和定位所需的时间)所需的定位成本。 (3)成本与精度之间的平衡。为每个传感器节 点增加硬件来辅助定位是一个昂贵的解决方案，并且 至今这种方案在实际应用中并不可行。能量和成本 的限制一直是传感器节点存在的问题，精度高则成本 开销就大，成本低则精度方面较差。 (4)性能评价。定位算法的评价现通常使用模 拟仿真的方式。无线传感器网络节点由于严格的硬 件限制，提出的模拟解决方案在实际系统的应用中并 没有得到希望的结果。 (5)安全。定位是无线传感器网络中的一个关键 问题，恶意的攻击将会导致传感器网络的失效。但至 今，定位方案在健壮性和安全性方面的研究还很少。 以上方面说明了对于无线传感器网络节点自身 定位仍有大量的研究工作需去完成，其定位算法在整 体性能上都有待进一步提高。 2009年第lO期 许秀兰：无线传感器网络距离无关定位算法研究 9 参考文献： [1] Akyildizi F，Su W L，Sank Arsubranmaniam Y，et a1．Wire- less Sensor networks：A survey[J]．Computer Networks， 2002，38：393-422． [2] 史龙，王福豹，段渭军．无线传感传感器网络 range-free 自身定位机制与算法[J]．计算机工程与应用，2004，40 (23)：127—130，151． [3] Nirupama Bulusu，John Heidemann，Deborah Estrin．Gps· less low cost outdoor localization for very small devices[J]． IEEE Personal Communications，2000，7(5)：28-34． [4] Tian He，Chengdu Huang，Brian M Blum，et a1．Range-free localization schemes in large scale sensor networks[c]／／ Proceedings of the 9th Annual International Conference on Mobile Computing and Networking(MobiCom)．San Diego， Califomia，USA，2003：81-95． [5] Niculescu D，Nath B．DV based positioning in Ad—Hoe net— works[J]．Journal of Telecommunication Systems，2003， 22：267-280． [6] Nicolescu D，Nath B．Ad—Hoc Positioning Systems(APS) [C]／／Proceedings of 200】IEEE Global Telecommunica． tions Conference．San，Antonio，TX，USA：Springer—Veflag Press．20o1：2926-2931． [7] Radhika Nagpal，Howard Shrebe，Jonathan Bachrach． 一 zing a global coordinate system from local information on An Ad—Hoe~n$or network[C]／／Proceedings of the 2nd Intema- tional Workshop on Information Processing in Sensor Net— works．CA，USA：Sringer-Veflag Press，2O03，4：333—348． [8] Capkun S，Hamdi M，Hubaux J P．GPS—free positioning in mobile Ad．Hoc networks[J]．Cluster Computing Journal， 2oo2．5：157—167． [9】 Niculescu D，Nath B．Ad—Hoc Positioning System(APs)using AOA[C]／／Procee~ngs of The 22nd Annual Joint Conference of the IEEE Computer and CommtmicatiOils Societies(INFO— COM 2003)．San Francisco。CA，USA，2003：1734—1743． [10]Savarese C，Rabaey J M，Beutel J．Locationing in distributed Ad．Hoe wireless sensor networks[c]／／Proc．of 200l IEEE Int’l Conf．Acoustics，Speech and Signal Processing(IC— ASSP 2oo1)．Piscataway，NJ，USA，2001． [11]Savarese C，Rabay J，Langendoen K．Robust positioning algo- rithms for distributed Ad．Hoc wireless sensor networks[c]／／ nD(蒯 in of t}】e US啪 X Technical Annual Conference． Monterey，CA，USA：USENⅨ Press，20O2：317-327． [12]Stoleru R，He T，Luebke p．A hish-accuracy low—cost localiza- tion system for wireless sensor networksfC]／／ACM Confer- enee on Eml~ ded Networked Sensor Systems(Se,~Sys)．2ID ． f 13]R A omer K．The lighthouse location system for smart dust [C 1／／ACM_／USENIx International Conference on Mobile Systems，Applications，and Services(MobiSys)，2003． [14]Stoleru R，He T，Stankovic J A．Walking GPS：A practical localization system for manually deployed wireless sensor networks『C 1／／IEEE Workshop on Embedded Networked Sensors(EmNetS)，20o4． ÷} ·}_{·} ·}_{·} ·卜；·}_{·} ·}_{·}_暑·}_{·} ·}_；·}_{·} ·}_{·} ·}÷} ·} ·}_{·}_{·}_{·}_{·}_{·}_{·}_{·}÷}_{·}_{·}_{·}_{·} ·}÷}_{·} ·}_{·} ·} ·} ·}_{·}_{·} ·}_{．}÷} ．} (上接第5页) [4] 王再明，王宏波．灰色系统理论在港 口吞吐量预测中的 表 4 2009～2010年南京港货物吞吐量预测值 应用[J]．武汉理工大学学报，2005，29(3)：456459 年份 预测值 还原值(十万吨) 2oo9 O．1O458 lO45．8 2Ol0 0．10434 1O43．4 4 结束语 南京港货物吞吐量预测的实例验证表明，用 BP 网络进行预测，全面地考虑了各种因素对港口吞吐量 的影响，实现了影响港口吞吐量的因素与港口货物吞 吐量之间复杂非线性映射，具有 良好的收敛性，能保 证满意的预测精度。 参考文献： [1] 张松兰．神经网络控制应用研究[J]．计算机与现代化， 2009(6)：94-97． [2] 王丹，杨赞．港口吞吐量影响因素分析[J]．水运工程， 2007，32(1)：45-48． [3] 潘文军．基于智能的港口物流预测系统的研究与应用 [D]．武汉：武汉理工大学硕士学位论文，2004． [6] 杨神化，关克平．Spreadsheet方法在港口吞吐量预测中 的运用[J]．武汉理工大学学报(交通科学与工程版)， 2005，29(5)：801—804． [7] 柳艳娇，肖青．组合模型在港 口集装箱吞吐量预测 中的 应用[J]．大连海事大学学报，2006，32(3)：26-28． [8] 周开利．神经网络模 型及其 MATLAB仿真程序设计 [M]．北京：清华大学出版社，2005． [9] 南京统计局．南京统计年鉴(1996—2008)[EB／OL]．ht— tp：／／www．njtj．gov．cn，2009-05—10． [10]孙永 明，郑光平．基于灰理论的港 口吞吐量预测研究 [J]．中国水运，2007(4)：160—162． [11]袁洪春，谢耀峰．港 口吞吐量概率预测模型研究 [J]．水 运工程 ，2007，33(4)：1028。1031． [12]周开利．神经网络模型及其 MATLAB仿真程序设计 [M]．北京：清华大学出版社，2005． [13]张萍，严以新．港口吞吐量的内在因素提取[J]．中国港 湾建设，2006(12)：70-72． [14]钟明霞，孔颖．基于KL变换和神经网络分类的微钙化点 检测新方法[J]．计算机与现代化，2008(9)：101．105．