多Sink动态传感器网络主动式分层定位方法.doc

第11期韩鹏等：多Sink动态传感器网络主动式分层定位方法51多Sink动态传感器网络主动式分层定位方法韩鹏，吴华锋，任久春，高传善（复旦大学 计算机科学与工程系，上海 200433）摘 要：针对多Sink动态无线传感器网络，提出一种主动式分层定位方法，采用事件驱动的主动式分层定位，不但能减少传感器节点的定位开销、延长网络的寿命，而且能够适应节点动态移动的场景。关键词：无线传感器网络；定位；通信中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)11-0044-07Active layered localization method for dynamic muti-sinks wireless sensor networksHAN Peng, WU Hua-feng, REN Jiu-chun, GAO Chuan-shan(Department of Computer Science and Engineering, Fudan University, Shanghai 200433, China)Abstract: An active layered localization method was proposed. The method was event-driven and divided into two layers (sensor layer and sink layer). The method not only supported the movement of nodes, but also reduced the localization cost of sensors and extended the network lifetime.Key words: wireless sensor networks; localization; communication1 引言收稿日期：2006-04-12；修回日期：2007-07-28无线传感器网络（WSN, wireless sensor networks）研究受到越来越多的重视。在大多数WSN应用中，传感器节点往往通过飞行器抛撒等方式随机布置到工作区域1，就需要采用定位技术来确定传感器节点的实际位置，因此，这成为无线传感器网络研究中一个重要的分支。近年来，研究者已经提出了很多的无线传感器网络定位方法，一般都基于2个前提：网络是同构的，即网络除了一个中心控制点外，全部由相同的传感器节点组成；网络是静态的，即节点一旦被布置后，位置就不再改变。但是，近年来传感器网络的应用发现，如果成千上万个节点的网络中只有一个Sink节点（基站或网络控制点）作为数据的会聚点，对系统的稳定性、有效性都是巨大的威胁。针对这种情况，研究者提出多Sink传感器网络模式2,3。此外，节点移动的动态传感器网络也纷纷涌现，比如加州大学伯克利校部实施的“智能灰尘”研究4，是一个由具有电脑功能的低成本、低功率的超微型传感器所组成的网络。这些微型传感器装在气球或浮空器内，像灰尘一样漂浮在空气中，可以监测周边环境的温度、光亮度和振动程度。在动态传感器网络中，传感器节点的位置会随时间而变化。异构的、动态的无线传感器网络模式对定位提出了新的要求，已有定位方法并不能简单移植到新的应用中来。本文针对多Sink动态无线传感器网络，提出一种主动式分层定位方法。本文的贡献主要包括以下几个方面：1)针对多Sink动态无线传感器网络，提出采用主动式、层次型定位的思想； 2)对定位方法进行了详细的设计，比如功能分层、限制广播等，这些措施能降低传感器节点的定位能耗、延长网络的寿命、支持节点的移动；3)通过模拟实验对定位方法的性能进行了分析和比较；最后，讨论了未来可能的研究方向。本文其余部分按如下方式组织：第2节介绍了相关工作和存在问题；第3节定义多Sink动态传感器网络模型；第4节详细介绍了本文提出的定位方法并提供必要的分析；第5节使用模拟实验对本文提出的方案进行了评估；第6节是结束语。2 相关工作下面首先介绍几种流行的无线传感器网络定位方法。Centroid5是GPS不可用环境中的一种近似定位方法。在网络中存在多个具有重叠覆盖面积、位置已知的参考点，参考点射频传播范围是一个规则的圆域。参考点周期性在网络中广播定位信息，该信息包含参考点自身的位置。如果传感器节点收到某个参考点的定位信号的次数和该参考点发送信号总次数的比值超过某个阈值（比如90%），则认为自己和参考点是连通的，自己的位置在该参考点的覆盖圆域内。如果一个传感器节点判定自身在多个参考点的覆盖圆域内，那么它就用这些参考点覆盖重叠区域的中心作为自己的位置。明显地，在Centroid中，参考点的数目对定位的精度有很大的影响。DV_Hop6技术也是一种range-free定位方法。它通过用网络中需要定位的节点到参考点（landmark）的跳数，乘以估计的平均每跳距离得出需定位节点到参考节点的距离，再根据三角计算得出目标节点的位置。DV_Hop方法的缺陷在于，首先，为了估算单跳距离，参考点洪泛它们的位置信息，网络中的节点都需要中继这些数据包，这将引起巨大的能量消耗；其次，所有传感器节点需要分配固定的内存来保存参考点的位置信息、到参考点的跳数以及单跳距离；更为重要的是，由于在hop-by-hop的传输方式中，从源端到目的端的传输不可能是直线的，所以，这样的距离估计往往误差很大。APIT7是针对无线传感器网络设计的一种近似定位方法。在APIT中，所有的参考点广播其位置信息，节点保存所有收到的参考点的位置信息，并和邻居节点合作来判断其是否在某个由任意3个参考点组成的三角形内部。目标节点用所有其在内部的三角形的重叠区的中心来近似其自身的位置。APIT的缺陷在于参考节点的位置广播要求所有的网络节点参与，对系统的能量是个巨大的消耗，并且要判断节点是否在三角形内部也要求复杂的计算能力。最后APIT算法得到的是目标节点的近似估计，其精度往往达不到要求。DLS8是针对节点移动的动态传感器网络设计的一种定位方法。在DLS中，参考点周期广播定位信息，当节点需要确定自身位置时，其等待接收参考点的位置信息并向参考点发送定位反馈信息，最后参考点根据定位反馈信息计算需定位节点的位置。这种方法对动态传感器网络的定位问题进行了初步的探索，但是由于方法十分简单，DLS有其局限性：1）参考点定期广播定位信息极大消耗它们的能量；2）DLS方法可能由于需定位节点等待接受定位信息而引起较大的定位时延；3）由于方法的简单性，DLS的定位开销比较大。上面列出了一些有代表性的无线传感器网络定位方法，它们大都属于先应式平面型定位方法（proactive flat localization method），先应式是指当网络布置下来后，网络中的节点随即运行定位算法，计算位置信息并保存，需要时再从内存中取出位置信息使用的机制；平面型是指定位操作全部由传感器节点完成的机制。3 网络模型图1 是多Sink无线传感器网络的示意图，在一个感应区域（sensor field）内，随机分布着一些传感器（sensor）节点，这些节点执行监测任务，并把结果通知Sink，然后Sink把消息传递给控制中心，控制中心根据这些监控信息采取相应的行动。Sensor节点由能量系统、传感系统、处理系统、通信系统以及移动系统组成，它们的计算能力、通信能力、电源能量都十分有限。Sensor节点通过电池供电，不能进行能量补充，一旦电池电量耗光，则Sensor节点失效。受体积、成本、能量等限制，Sensor节点也没有装备功能强大的定位设备，比如GPS，它只能通过传感器网络自身定位方法来获取位置信息。此外，相邻的Sensor节点可以通过无线电（radio）直接通信，而非相邻的传感器节点只能通过hop-by-hop的方式交换数据。Sink节点的结构如图2所示，在硬件组成上除了具有Sensor的5大系统外，Sink节点增加了GPS和发电2个系统。GPS系统通过GPS设备为Sink节点提供即时的位置信息。发电系统为Sink节点提供持续不断的能量（发电系统可以是太阳能装置或者热能装置）。Sink节点在计算能力、存储能力和通信能力上都比Sensor节点功能更强。Sink没有资源的限制，Sink间可以直接通信。另外，假设无论是传感器节点还是参考节点，都可以在网络中自由移动，它们的移动或者是自发的，或者是由于载体（比如海水或者空气）的流动而引发。图1 多Sink异构无线传感器结构示意图2 Sink硬件组成4 多Sink动态传感器网络主动式分层定位方法 多Sink动态传感器网络不同于单Sink静止传感器网络，它既为定位方法提供了改进的机遇，也使得定位方法面临巨大的挑战。首先，异构的Sink节点为提出不同的、能量有效的定位方法提供了条件，定位方法可以充分利用Sink强大功能完成节点定位，减少Sensor节点的定位开销；其次，对移动节点的定位更加复杂，而且由于位置可能随时改变，刚获得位置的节点也不能作为下一次定位的参考点。针对传统传感器网络先应式平面型定位方法的缺陷和多Sink网络的特点，提出了一种主动式分层定位机制ALLM（active layered localization method for multi-sink dynamic wireless sensor networks）。首先，ALLM采用事件驱动的主动式定位。对大多数无线传感器网络监测应用，使用者构建网络的目的是为了监测区域中的突发事件、并对突发事件进行报告和处理。对这种类型的应用，在范围广大的监测区域内，只有事件发生的位置是十分重要的，也就是说，只有监测到事件发生的传感器节点的位置信息对系统来说是有用的。从而，定位方法只需确定监测到突发事件的传感器节点的位置，而没有必要对网络中所有的节点进行定位，这种事件驱动的定位机制我们称为主动定位（active localization）。其次，ALLM利用Sink充当位置参考点。在已有无线传感器网络的定位方法中6,7,9，参考节点都采用普通的传感器节点，为系统提供位置参考。在ALLM中，充分利用网络的异构性，用功能强大的Sink作为位置参考点，采用功能分层的定位方法，把定位操作更多的让Sink来完成，从而减少Sensor节点定位负担，节省能量消耗。下面给出主动式分层定位方法ALLM的详细设计，并对它进行分析和说明。ALLM定位方法主要分下面几步：1) 侦测到突发事件的Sensor节点打开Radio发送设备，发出定位请求。定位请求数据包（LRP, localization request packet）的格式如图3所示。图3 定位请求包LRP身份域（ID）标识请求被定位的Sensor节点的全局惟一身份；类型域（type）标识该数据包的类型。用来监测的无线传感器网络中有多种多样的数据包，比如维护路由的包、应用层的包。对不同的数据包，节点有不同的处理办法。在本章中，为定位操作定义了2种类型的包，一种就是这里的定位请求包LRP，它被监测到事件的Sensor节点用来请求对自己定位；最大跳数（max-hops）域给定位请求包设置一个传递的最大跳数。定位请求包以广播的方式在网络中扩散，所有接收到LRP的节点都需要中继该包。为了限制LRP包的传播范围，给它设置一个最大跳数域，当LRP在网络中传播时，达到最大跳数或遇到Sink节点时， LRP的传递被终止。我们把这种机制称为“限制广播”。Max-hop值通过下面的方法来估计：所有Sink交换彼此的位置信息，然后通过图算法把监测区域分为多个定位参考域（如图4所示），每个域以一个Sink为中心，每个定位参考域的面积除以Sensor节点的平均密度作为该定位参考域的最大跳数（max-hops），Sink计算出该值后把它广播出去，Sensor把自己归入最早收到的Max-hop值的定位参考域中；信息域（INFO）包含一些对监测到事件的描述，它随应用的不同而变化。这个域是可选的。图4 定位参考域的划分2) 定位请求包传播范围（由Max-hop决定）的设置确保它至少能够到达一个Sink节点，当定位请求包LRP到达一个Sink后，该Sink立刻和网络中其它至少3个Sink协同，这些协同的Sink立刻发出定位确认包（LACK ,localization ACK）。定位确认包的格式如图5所示。“身份（ID）” 域是发出定位确认包的Sink节点的全局惟一身份标示符；“位置（Loc）”域是Sink节点的位置，假设Sink可以通过GPS获知自己当前的位置信息；“信号强度（SS）”域是LACK信号的初始强度值；“信息（INFO）”域可以封装一些相关的信息，这个域的是可选的。图5 定位确认包LACK在ALLM定位的第一步中采取了“限制广播”的策略，这使得Sensor节点的定位请求可能仅仅到达一个Sink，而根据三角定位原理，必须有3个参考点才能定位一个Sensor。这时必须请求其余Sink的合作，Sink协同就是收到定位请求的Sink请求其余Sink节点协助定位的过程。例如，定位请求包LRP在传播范围内只被SinkA接收到，通过A请求Sink B与Sink C协同，Sink A、B、C发出各自的定位确认数据包LACK_A，LAC_B，LACK_C ，最后监测到事件的Sensor节点能收到A、B、C发出的定位信息并计算出自己的位置。此外，在ALLM中，Sink节点间的通信不通过Sensor节点的中转；而且定位确认包LACK也由Sink以大功率发出，以确保它能被网络中的节点接收。实际上网络通信被划分成了2个层次，这种方式把大量的定位操作放在Sink上，极大地节省普通Sensor节点的能量。3) 监测到事件的Sensor节点收到定位确认信息LACK之后，根据LACK到达时的信号强度以及LACK包中SS域指示的初始信号强度，通过信号随传播距离增加而强度衰减的公式计算出到Sink的距离。信号强度测量的方法简单易行，绝大多数的无线电组件都提供了接收信号强度指示（RSSI，received signal strength indicator)功能。预测室外环境传播损耗的最常用方法是经验公式，它基于某一特定环境下的实际测量结果。实际中，发射和接收机被置于特定环境中不同的位置，测量其功率损耗，通过收集大量的数据导出功率损耗曲线及其函数。4) 监测到事件的Sensor节点根据3）中得到的到Sink的距离，以及LACK包中Loc域包含的Sink的位置，通过三角计算得出自身的物理位置。如事件侦测点收到多个Sink定位信号，它可以多次计算其位置，取平均值作为最终估计位置，以减少系统的误差。5 模拟与性能分析本节对ALLM进行了模拟检验，并对实验结果进行分析。模拟实验主要目的有2个：一是考察提出的定位方法的可行性和各方面的性能；二是考察定位方法在节点移动的动态场景下的表现。在NS-210上进行了仿真实验。在仿真实验中，首先做如下假设：传感器节点的信号半径为1m；节点在监测区域内呈随机Poisson均匀分布；Sink节点没有资源限制，其单跳无线传播范围可以覆盖整个网络。定位误差是定位方案中考察的关键指标。图6反映了随Sink数目的增加，ALLM、APIT、DV_Hop 3种定位方法的平均定位误差，图中定位误差用传感器节点的Radio range为单位。从图7可以看出，3种定位方法的定位误差都随Sink数目的增加而下降，当Sink数目较少时，ALLM和DV_Hop的定位效果均好于APIT，但在APIT中，Sink的增多能把Sensor限制到更小的三角区域，所以其定位精度随Sink的增多而持续改善。对DV_Hop，估计精度当Sink数目从3到8时，改善最为明显，而当Sink数目超过8后，变化并不大。对ALLM，由于通过信号强度衰减测距来定位其位置，其定位精度基本不受Sink数目的影响。但是在信号强度测距的误差存在的情况下，图中ALLM+是假设Radio信号每传播50m的距离，信号测距的平均误差为一个Radio range时的定位误差效果图。图6 定位误差与Sink数目的关系图7 定位误差与 Sensor密度另一个影响定位误差的重要因素是Sensor密度，图7调查了各种方法的定位误差受Sensor密度影响的情况（本实验中Sink数设为16）。从图中可以看出，对于APIT和DV_Hop，它们的定位误差随节点的密度的增大而有所下降；而ALLM定位基本不通过邻居节点信息的交互，所以节点密度对其影响很小，其定位精度在节点密度改变的情况下基本是一常量。图8反映了定位误差和协同定位Sink数目之间的关系。分别测量了当网络中有不同数目的Sink时，协同定位一个节点的Sink数目对定位误差的影响。尽管原则上3个Sink即可确定一个Sensor的位置，但是从图中可以发现，协同定位一个Sensor的Sink数目越多，定位的误差也越小。在网络中有30个Sink时，当协同定位的Sink数目从3增加到6时，定位误差显著下降，超过6之后，改善不太明显；当Sink总数为12时，协同定位的Sink数在11之前对定位误差的改善比较明显，而当Sink总数为18时，协同定位的Sink临界值在9或10之间。这个结果说明，适当的定位Sink冗余，有助于提高精度，但超过某个临界值后，协同定位Sink数的增加对定位精度的改善不再有太大的意义。图8 定位误差与协同Sink个数的关系定位开销是衡量定位方法优劣的一个重要指标。用定位过程中Sensor节点交换数据包的数目来衡量定位开销。模拟实验比较了ALLM、APIT、DV_Hop在定位开销上的性能。在APIT，DV-Hop中，Sink也充当位置参考点。实验中的参数为监测面积1 000m2、无线传感器节点1 000个。图9给出了当网络中Sink节点的数目增加时，在一次定位过程中3种定位方法在定位开销的比较。从图中可以看到，随着Sink数目的增加，ALLM的定位开销逐渐下降，而APIT，DV_Hop的定位开销却持续增加。这是因为在ALLM中，Sink把监测区域分为不同的定位参考域，Sink越多，参考域的范围越小，定位请求包LRP的广播范围越小，从而网络中传递数据包的数目也越小。而对APIT和DV_Hop，Sink越多，需要中继的消息也越多，定位开销也越大。图9 定位开销与Sink数目的关系定位时延（本文定义为从Sensor感应到事件到Sink节点获得Sensor报告的时间）也是衡量定位方法的一个重要指标。在动态传感器网络中，节点的移动使得前一次保存的位置信息失效，监测到事件的Sensor需要重新定位，这时本文提出的定位方法ALLM在定位时延上就要比APIT和DV-Hop短得多。图10是定位时延随Sink数目变化的实验结果。从图中可以看出，PIT和DV-HOP受Sink数目影响较小，而随Sink数目增加，ALLM定位时延减小。这是因为Sink增多把监测面积划分为更小的参考域，从而使Sink到Sensor的距离缩短。图10 定位时延与Sink数目的关系在动态无线传感器网络中，由于节点位置不停变动，保存的位置信息是无效的，为了得到其即时位置信息，APIT或DV-Hop定位方法需要不停地在网络中运行，即使只为求得一个Sensor的位置，也需要网络的整体参与，从而定位开销巨大；对ALLM，定位一个Sensor只需少部分节点参与，所以主动式的定位方法要优于先应式的定位方法。6 结束语本文根据多Sink动态传感器网络的特点，提出了一种主动式分层定位方法，并对其做了详细设计。该方法通过一些独特的设计，比如限制广播、划分定位参考域、Sink协同等，使得部分定位操作由资源充足的Sink完成，从而减少Sensor节点的定位开销，而且，该方法还对节点的移动提供了很好的支持。最后，通过模拟实验检验了该定位方法的性能，和几种经典的定位方法相比，本文方法在定位误差、定位时延、定位开销上都有其优势。但是，在本文研究的基础上，还有一些需要进一步研究的的问题，比如：对噪声环境的适应。本文中的模拟实验是在假设的无噪声的环境中进行的，但是在实际的环境中，由于噪声的存在，基于无线电衰减的距离测量会受到影响。如何克服噪声的影响，是正探询的方向；事件报告冲突避免。在实验中，假设只有一个Sensor节点侦测到事件发生。但实际环境中，往往有多个Sensor节点侦测到事件发生。如果这些节点都发出事件报告信息，必然会导致信息的冲突。因此，如何协调事件的报告是我们需要面临的问题。一种可行的方式就是节点之间合作选举一个点作为事件报告者；新技术的影响。当前，出现了一些可能对无线传感器网络造成巨大影响的新技术，比如定向天线等。这些都会对无线传感器的定位问题产生深远的影响，这是我们正深入研究的领域。参考文献：1AKYILDIZ I F, SU W, SANKARASURBRAMANIAM Y, et al. Wireless sensor networks: a surveyJ. Computer Networks(Elsevier) Journal，2002,38(4):393-422.2AKYILDIZ L F, KASIMOGLU I H. Wireless sensor and actor networks: research challenges A. Ad hoc Networks(Elsevier)C. 2004.393-422.3GRILO A, MACEDO M, NUNES M. An energy-efficient low-latency multi-sink MAC protocol for alarm-driven wireless sensor networksA. Wireless and Mobility, LNCS 4396C. 2007. 87-101.4Smart dust: autonomous sensing and communication in a cubic millimeterEB/OL. / p