无线传感器网络中的目标跟踪算法

第２８卷第４期　２００７年７月　宇　航　学　报　

Ｊｏｕｒｎａｌ　ｏｆ　Ａｓｔｒｏｎａｕｔｉｃｓ　Ｖｏ１．２８　Ｎ０．４　Ｊｕｌｙ　２００７　

无线传感器网络空中目标跟踪任务分配技术的研究　

刘　梅　，李海昊　，沈毅　

（１．哈尔滨工业大学电子与信息技术研究院，哈尔滨１５０００１；２．哈尔滨工业大学控制科学与工程系，哈尔滨１５０００１）　

摘要：以无线传感器网络对空中飞行Ｈ标跟踪为背景，针对无线传感器网络协同技术中的任务分配问题，　

以降低传感器节点之间的通信能量消耗为Ｈ的，提出了一种基于弹性神经网络的任务分配算法。首先对多动态联　

盟多Ｈ标跟踪问题进行建模，然后依据最小能量准则，采用一种非全连接的环形结构的弹性神经网络模型，解决了　

多Ｈ标跟踪时的任务优化分配问题以及多个动态联盟对传感器资源竞争冲突时系统能耗增加的问题。仿真结果　

表明，该算法与传统的方法相比，大大降低了跟踪系统的能量消耗。　

关键词：无线传感器网络；多Ｈ标跟踪；任务分配；神经网络；动态联盟　

中图分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１０００—１３２８（２００７）０４—０９６ｏ一０６　

Ｏ　引言　

利用现代系统和智能理论对空中飞行目标进行　

跟踪是防空系统设计中的一大热门话题，目前各国　

军方十分重视无线传感器网络对飞行目标跟踪技术　

的研究。无线传感器网络（ＷＳＮ：Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔ—　

ｗｏｒｋ）是由大量功率低、体积小、价格便宜、具有通信　

与计算能力的微小传感器节点构成的“智能”自治测　

控网络系统，一般密集布设在无人值守的监控区域，　

能够根据环境自主完成指定任务，其目的是协同地　

感知、采集、处理网络覆盖范围内的信息并将其提供　

给用户…。无线传感器网络的特性非常适合于军事　

侦察、救援等多个方面，在战场监测等领域的应用十　

分重要　，尤其是对飞机、导弹等空中飞行目标进行　

跟踪。美国《今日防备》杂志更认为无线传感器网络　

的应用和发展，将引起一场划时代的军事技术革命　

１３２　传感器与微系统（Ｔｒａｎｓｄｕｃｅｒ　ａｎｄ　Ｍｉｃｒｏｓｙｓｔｅｍ　Ｔｅｃｈｎｏｌｏｇｉｅｓ）　２０１１年第３Ｏ卷第３期　

基于改进粒子滤波器的ＷＳＮｓ目标跟踪算法　

李　宁　一，徐守坤　，马正华　，石　林　，。　（１．常州大学信息科学与工程学院，江苏常州２１３１６４；　２．常州大学国际普适计算研究院江苏常州２１３１６４）　

摘要：提出了一种适用于无线传感器网络（ＷＳＮｓ）的目标跟踪算法，该算法基于改进型粒子滤波器　（ＰＦ），根据当前的预测值优化ＰＦ的方向值，从而保证精确地预测到目标的移动方向；修改了目标突发变　化引起的粒子滤波器预测误差，能够很好地跟踪目标移动过程中的异常、突发的移动变化。仿真结果表　明：该目标跟踪算法采用新的粒子滤波器之后，可以获得更为精准的目标跟踪性能。　关键词：无线传感器网络；信息粒子滤波；方向预测；目标跟踪　中图分类号：ＴＰ　３９３　文献标识码：Ａ　文章编号：１０００－９７８７（２０１１）０３－０１３２－０３　

Ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ　ｓｃｈｅｍｅ　ｂａｓｅｄ　ｏｎ　ｉｍｐｒｏｖｅｄ　ｐａｒｔｉｃｌｅ　ｆｉｌｔｅｒ　

ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　

ＬＩ　Ｎｉｎｇ　一，ＸＵ　Ｓｈｏｕ—ｋｕｎ　，ＭＡ　Ｚｈｅｎｇ．ｈｕａ　，ＳＨＩ　Ｌｉｎ　，　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈａｎｇｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｚｈｏｕ　２１３１６４，Ｃｈｉｎａ；　２。Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｕｂｉｑｕｉｔｏｕｓ　Ｃｏｍｐｕｔｉｎｇ，Ｃｈａｎｇｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｚｈｏｕ　２１３１６４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｎ　ｉｍｐｒｏｖｅｄ　ｐａｒｔｉｃｌｅ　ｆｉｌｔｅｒ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ＷＳＮｓ　ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ　ｉｓ　ｐｒｏｐｏｓｅｄ．ＰＦ’Ｓ　ｄｉｒｅｃｔｉｏｎ　ｖａｌｕｅ　ｉｓ　ｏｐｔｉｍｉｚｅｄ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｃｕｒｒｅｎｔ　ｐｒｅｄｉｃｔｉｏｎ　ｖａｌｕｅ　ｔｏ　ｐｒｅｄｉｃｔ　ｍｏｖｉｎｇ　ｄｉｒｅｃｔｉｏｎ　ｏｆ　ｔｈｅ　ｔａｒｇｅｔ　ａｃｃｕｒａｔｅｌｙ．Ｐｒｅｄｉｃｔｉｏｎ　ｅｒｒｏｒ　ｐｒｅｃｉｓｉｏｎ　ｏｆ　ｐａｒｔｉｃｌｅ　ｆｉｌｔｅｒ　ｔｈａｔ　ｉｓ　ｐｏｓｓｉｂｌｙ　ｐｒｏｄｕｃｅｄ　ｂｙ　ｓｕｄｄｅｎ　ｃｈａｎｇｅｓ　ｉｎ　ｄｉｒｅｃｔｉｏｎ　ｉｓ　ｍｏｄｉｆｉｅｄ．Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｎｅｗ　ｐａｎｉｃｌｅ　ｆｉｌｔｅｒ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ａｃｈｉｅｖｅ　ｂｅｔｔｅｒ　ｔｒａｃｋｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ　ｔｈａｎ　ｏｔｈｅｒ　ｆｉｌｔｅｒ　ａｌｇｏｒｉｔｈｍｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ（ＷＳＮｓ）；ｉｎｆｏｒｍａｔｉｏｎ—ｐａｒｔｉｃｌｅ　ｆｉｌｔｅｒ（Ｉ－ＰＦ）；ｐｒｅｄｉｃｔｉｏｎ　ｏｆ　ｄｉｒｅｃｔｉｏｎ；ｔａｒｇｅｔ　ｔｒａｃｋｉｎｇ　

第章 无线传感器网络定位、跟踪与时间同步技术 91 4

络节点。一般需要在连续时间内产生两个跟踪目标的位置才能够计算出其运动速度和方向，

利用3个连续时间点上的位置估计出结果将有效减小误差。跟踪目标的运动记录越多，对其

运动速度和轨迹预测越准确，但是计算代价和通信代价也相应会越大。

3．通告阶段

计算出跟踪目标的运动轨迹后，传感器网络要通知跟踪目标周围的节点启动进入跟踪状

态。所有利用3个位置估算出的跟踪目标的轨迹节点均广播一个通告消息，该消息包含了本

节点的位置信息和跟踪目标的轨迹。收到消息的节点计算本身到跟踪目标预测轨迹的距离，

如果该距离小于预定的阈值d，则节点启动进入跟踪状态，同时转发该通告消息。否则节点

保持原状态并丢弃该消息。由于可能出现多个节点发送通告消息，所以规定节点在转发一个

通告消息后的一段时间内不再转发任何节点的通告消息，这样可以节省网络资源。

4.3 无线传感器网络时间同步技术

4.3.1 时间同步模型

1．时钟模型

传感器网络中节点的本地时钟依靠对自身晶振中断计数实现。晶振的频率误差和初始计

时时刻不同，使得节点之间本地时钟不同步。如果能估算出本地时钟与物理时钟的关系或本

地时钟之间的关系，就可以构造对应的逻辑时钟以达成同步。目前的逻辑时钟同步算法，如

下文提到的有些同步算法同步精度已达到1μs，可以满足传感器网络中绝大部分应用的需求。

如果要达到纳秒级精度，则要采用锁相环等硬件实现物理时钟同步。

（1）节点本地时钟模型

在计算机系统中，时钟通常用晶体振荡器脉冲来度量[12]，即

（4-20） 00()()d()ttctkctωττ=+∫

式中，ω(τ)是晶振的频率，k是依赖于晶振物理特性的常量，t是真实时间变量，c(t)是构造的本地时钟，间隔被用来作为度量时间。对于理想的时钟有0()()ctct−()d()/d1rtctt==，也就

是说，理想时钟的变化速率为1。晶振频率在短时间内相对稳定，节点时钟又可表示为 ()rt

欢迎网上投稿《微型机与应用》2010年第29卷第21期随着计算机网络技术、通信技术、嵌入式技术和传感器技术的飞速发展和日益成熟，具有感知能力、计算能力和通信能力的微型传感器及其构成的无线传感器网络WSN(WirelessSensorNetwork)引起了人们的极大关注。这种传感器网络具有低功耗、低成本、自组织的能力，能够自动进行配置和适应环境的变化，具有动态可重构性等特点，能够通过协作实时监测、感知和采集网络，分布区域内的各种环境或监测对象的信息并传送到控制中心，因而被广泛应用于国防军事、国家安全、精细农业、环境监测、智能家居、城市交通以及预防与减灾、人员营救、目标跟踪等方面，适用于在人们无法接近的极端恶劣或特殊环境下监测事件发生的地点[1]。传感器节点通过飞行器撒播、人工埋置和火箭弹射等方式任意撒落在被监测区域内。节点的位置信息都是随机的，节点所采集到的数据，若没有位置信息几乎没有应用价值[1]。所以在无线传感器网络应用中，节点的定位一直是关键问题，同时也是人们研究的热点。由于传感器节点采用电池供电，节点数量巨大，成本太高，能量有限。因而利用GPS或其他方式先对网络中的少量节点(锚节点)进行定位，其他大部分节点以锚节点位置为参考，应用各种定位算法实现自身定位。根据目前出现的定位算法对节点位置估测机制的不同可以分为两大类：基于距离相关的定位算法(Range-BasedLocalizationSchemes)和基于距离无关的定位算法(Range-FreeLocalizationSchemes)。前者需要测量相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置；后者不需要自己与锚节点之间的距离或角度信息，而是根据网络连通性等信息估算出自己与锚节点间的距离。基于距离相关的定位算法使得传感器节点造价增高，消耗了有限的电池资源，而且在测量距离和角度的准确性方面需要大量的研究。基于距离无关的定位算法则不需要知道未知节点到锚节点的距离或者不需要直接测量此距离，在成本和功耗方面比基于测距的方法具有优势[1]。如质心算法、DV-Hop、Amorphous和近似三角形内点测试法APIT等。其中，APIT定位算法的基本思想简单，实现容易。而且由于其定位功耗小、成本低、节点定位精度高等特点得到广泛应用和研究，其中有不少改进算法的效果更优。本文将无线传感器网络APIT定位算法唐明虎，张长宏，昝风彪(青海民族大学计算机学院，青海西宁810007)摘要：无线传感器网络节点定位机制的研究中，基于距离无关的定位技术得到快速发展，其中基于重叠区域的APIT定位算法在实际环境下定位精度高，被广泛研究和应用。对APIT定位算法及其改进措施进行了总结，并给出性能比较结果。关键词：无线传感器网络；APIT；定位算法中图分类号：TP393文献标识码：A文章编号：1674-7720(2010)21-0001-04APITlocalizationalgorithminwirelesssensornetworksTANGMingHu，ZHANGChangHong，ZANFengBiao(CollegeofComputerScience，QinghaiUniversityforNationalities，Xining810007，China)Abstract：Localizationalgorithmbasedonrange-freehasdevelopedrapidlyinwirelesssensornetworknodelocalizationmechanism.EspeciallybasedonoverlappingtheregionAPITlocalizationalgorithminrealenvironment，highpositioningaccuracycanbewidelyusedbyresearch.ThispositioningtechnologyoftheAPITalgorithmanditsimprovedalgorithmarereviewed，anditsperformanceanalysisandcomparisonofsimulation.Keywords：wirelesssensornetworks；APIT；localizationalgorithm综述与评论ReviewandComment1《微型机与应用》2010年第29卷第21期基于距离无关的定位算法APIT的相关改进算法进行综述，以便使APIT算法的研究和应用得到进一步推广。1基于区域的APIT算法无线传感器网络定位机制中，APIT算法属于距离无关、区域相关的定位策略。其实现简单、定位成本低、传感器节点功耗小、定位精度高，因而得到广泛应用。它的基本算法是从待定位节点周围的锚节点中任意选取三个，组合成一个三角形，判断该点是否位于该三角形内。如果在三角形内，则将其标记，依次对待定位节点周围的锚节点进行各种不同组合并检测，最终找出所有满足要求的三角形重叠区域，求其质心位置以替代待定位节点在网络中的具体位置坐标。算法原理见图1。该算法的基本理论依据是最佳三角形内点测试法(PIT)[2]。1.1PIT原理介绍APIT算法在进行定位之前，首先要明确未知节点M是否处于已知的三个锚节点所连成的三角形内。因此，对于随机分布在某区域内的无线传感器网络，在需要确定位置信息的未知节点M的无线射程范围内随机选取三个已知位置信息的锚节点：A(xa，ya)，B(xb，yb)，C(xc，yc)，确定M节点是否在锚节点构成的△ABC内。命题1：将节点M向任意一个方向移动，如果节点M至少与锚节点A、B、C当中的任何一个之间远离或接近，则表明节点M处于该△ABC内，见图2(a)。命题2：存在一个方向，使得节点M沿该方向移动时，将同时远离或接近三个锚节点A、B、C，则表明节点M处于该△ABC外，见图2（b)。按上述命题判断节点M是否处于三个锚节点包围的三角形之内，条件足够，但由于实际无线传感器网络中撒布的节点规模庞大，而且大部分实际网络中，节点处于静止或移动非常缓慢的状况，因此上述判断方法不能用于待定位节点的测试。在实际网络操作中采用近似PIT原理测试。近似PIT原理(APIT原理)：如果在待定位节点M的邻居节点中，没有同时远离或接近三个锚节点A、B、C的点，则表明节点M位于该△ABC内，否则节点M位于△ABC外(见图3)。对于具有N个锚节点的规模网络，用锚节点间的通信能够连成C3N个三角形。1.2APIT算法实现步骤在实际无线传感器网络中实现APIT算法可简要分为四个步骤：(1)各节点获取在其无线射程之内所有锚节点的信息，包括位置坐标、信号强度等信息。(2)根据PIT原理进行测试。(3)聚集所有满足条件的三角形，找出其交集。(4)计算交集的重心，以其估计待定节点位置。根据实现APIT算法的四个步骤，可以写出其伪代码：Receivelocationbeacons(Xi，Yi)fromNanchors；//取得N个锚节点的位置坐标InsideSet=Ф；//对设定用来存放包含待定节点区域的变量InsideSet初始化for(eachtriangleTi∈triangles){//穷尽锚节点组成的所有三角形if(Point-In-Triangle-Test(Ti)==TRUE)//判断如果待定位节点位于该三角形内InsideSet=InsideSet∪{Ti}；//则将其区域标记，并调用网络扫描算法if(accuracy(InsideSet)>enough)break；//如果定位精度已达要求可提前结束循环}EstimatedPosition=CenterOfGravity(∩Ti∈InsideSet)；//计算包含待定位节点的公共区域的重心，以其代替待定//位节点的位置1.3APIT算法性能分析通过与常见几种基于距离无关定位算法之间的