韩小卫毕业论文（最终版本） - 图文

哈尔滨工业大学工学硕士学位论文

摘要

无线传感器网络，也称感知网，是一种由大量体形小、成本低，具有通信能力的传感器通过ad hoc方式形成的网络。其能够实时获取、分析、融合周边环境信息，反馈给后台用户，在环境监测、设备管理、公共安全、医疗和军事应用等方面有着广泛的用途。其中目标跟踪研究是一个很重要的应用研究分支，在野生动物追踪、智能交通、战场监控等应用中作用举足轻重。本文在改进已有单目标跟踪算法的基础上，提出了一种感知网多目标的跟踪框架。

首先针对高信噪比环境特点，提出了一种新的“距离-量测”定位算法。算法通过对先期目标信息的存储和节点感知区域的划分，对定位精度和计算复杂度以及可靠性进行折中，在满足需要的条件下，提高了定位效率。

如何节省节点能耗，是感知网目标跟踪研究的一个重点问题。本文基于目标动向预测跟踪簇算法，对动态簇簇首的产生机制进行改进，提出了“太子簇首-异常-竞争”算法。算法首先根据历史预测结果对节点进行分类，然后根据分类结果预定最合适的节点作为下一定位时刻的簇首，从而摒弃以往算法中多节点竞争或选举的簇首产生机制，减少信号发送，从而节省了能量。 多目标环境下，目标间距离由远及近，其对节点的共同影响程度将随之增大，从而产生多目标的信号关联问题。本文通过对目标间远近距离的场景分析建立多目标跟踪框架。即“远距离单目标精确跟踪-稀疏多目标类精确跟踪和密集多目标集群跟踪”。

多目标类精确跟踪针对稀疏多目标情况下问题分析，对单目标的“太子簇首-异常-竞争”跟踪算法进行修正。加入时间戳机制，根据预测信息对节点量测进行分解，从而实现目标的量测信号关联，对每个目标区分跟踪。

多目标集群跟踪将所有目标视为一个整体。本文通过对集群簇的形成、定位、持续、合并和分解的条件及具体过程的分析，描述了集群跟踪算法的整体框架以及类精确跟踪与集群跟踪的相互转换过程。

最后，设计和实现了基于Mica2平台的原型系统和仿真系统。原型系统用于目标定位算法和单目标“太子簇首-异常-竞争”跟踪算法的可行性验证；仿真系统验证多目标类精确跟踪和集群跟踪算法的有效性。

关键词 目标定位；多目标跟踪；动态簇；感知网

- I -

哈尔滨工业大学工学硕士学位论文

Abstract

Wireless Sensor Networks is a new kind of ad hoc network platform which is composed by large number of small size, low-cost and wireless communication sensors. It can real-time acquire, analyse and integrate the information of surrounding environment, then feed back to the remote users. Consequently, it has a wide range of use in environment monitoring, equipment management, public security, medical treatment and military affairs. Target tracking is an important research branch in applied research area. It plays a pivotal role in wild-animal tracking, intelligent transportation, and battlefield surveillance and so on. In this article, we improved the single-target tracking algorithm in sensor networks， then based on it, we proposed a multi-target tracking framework.

Firstly we compared many localization algorithms and proposed a new \localization algorithm. In the new algorithm we stored the advanced information of targets and divided the perceptive region of nodes. It can improve the localization accuracy and reliability and reduce the computational complexity. The efficiency of localization has been improved.

To reduce energy consumption of nodes is a very important issue of target tracking in sensor networks. Based on dynamic prediction cluster algorithm, we proposed \classified the nodes based on the historical prediction results, and then according to the classification results to choose the most suitable node as the cluster header for next locate moment. This mechanism avoided the competition and election among the nodes, reduced the signal transmission and saved energy.

Under the circumstances of multiple targets, as the distance between the targets become nearer, the conjunct impact to nodes become larger, thus bringing signal association problems. According to the scene analysis that the distance changes continuously we proposed the multi-target tracking framework: \distance single-target precise tracking—Sparse multi-target close-precise tracking and Dense multi-target group tracking.\

Multi-target close-precise tracking modified the \Cluster Header - Abnormal-Competition\algorithm in single-target tracking. Introduced

- II -

哈尔滨工业大学工学硕士学位论文

timestamp mechanism, based on predictions of information we decomposed the nodes? measure, thus associating the signal measures for each target and tracking each target respectively.

Multi-target group tracking regards all the targets as a whole unit. Based on the group clusters? formation, localization, sustainment, mergence and decomposition process, we described the whole framework of the group tracking algorithm and the conversion process between the close-precision tracking and the group tracking.

Finally, we designed and implemented the prototype system based on Mica2 Platform and the simulation system. The prototype system was used for valida- ting the feasibility of the target location algorithm and the \- Abnormal-Competition\-tem validated the multi-target close-precise tracking algorithm and the multi-tar- get group tracking algorithm.

Keywords Target Localization; Multiple-Target Tracking; Dynamic Cluster;

Sensor Networks

- III -

哈尔滨工业大学工学硕士学位论文

目录

摘要 ............................................................................................................................... I Abstract ....................................................................................................................... II 第1章 绪论 ................................................................................................................ 1 1.1 课题背景 ........................................................................................................... 1 1.1.1 课题来源 .................................................................................................... 1 1.1.2 课题研究目的及意义 ................................................................................ 1 1.2 与课题相关的国内外研究综述 ....................................................................... 2 1.2.1 国内外关于感知网的研究现状 ................................................................ 2 1.2.2 感知网目标定位与跟踪技术的研究现状 ................................................ 3 1.3 本文的主要研究内容 ....................................................................................... 5 1.3.1 感知网单目标定位与跟踪算法研究 ........................................................ 6 1.3.2 感知网多目标跟踪算法的研究 ................................................................ 6 1.3.3 论文结构 .................................................................................................... 7 第2章 感知网单目标定位跟踪算法研究 ................................................................ 8 2.1 距离-量测定位算法 ......................................................................................... 8 2.1.1 基于感知能量的定位算法 ........................................................................ 8 2.1.2 距离-量测定位算法 ................................................................................ 11 2.1.3 仿真验证 .................................................................................................. 19 2.2 “太子簇首-异常-竞争”单目标跟踪算法 .................................................. 21 2.2.1 节点分类机制 .......................................................................................... 21 2.2.2 “太子簇首-异常-竞争”算法 ............................................................... 22 2.2.3 仿真验证 .................................................................................................. 27 2.3 本章小结 ......................................................................................................... 29 第3章 感知网多目标跟踪算法研究 ...................................................................... 30 3.1 多目标场景分析及跟踪框架 ......................................................................... 30 3.2 稀疏多目标类精确跟踪算法 ......................................................................... 31 3.2.1 问题分析 .................................................................................................. 31 3.2.2 时间戳机制 .............................................................................................. 32 3.2.3 基于预测信息的信号分解 ...................................................................... 34 3.2.4 动态簇协议的修正 .................................................................................. 36

- IV -

哈尔滨工业大学工学硕士学位论文

3.2.5 节点触发机制 .......................................................................................... 38 3.2.6 算法仿真结果 .......................................................................................... 41 3.3 多目标集群跟踪算法 ..................................................................................... 42 3.3.1 算法思想描述 .......................................................................................... 42 3.3.2 集群簇的形成 .......................................................................................... 43 3.3.3 多目标定位方法及集群簇的维持 .......................................................... 45 3.3.4 集群簇的合并与分解 .............................................................................. 51 3.3.5 算法实验仿真 .......................................................................................... 57 3.4 本章小结 ......................................................................................................... 58 第4章 感知网多目标跟踪系统设计与实现 .......................................................... 59 4.1 系统总体设计 ................................................................................................. 59 4.2 基于MICA2平台的原型系统设计与实现 .................................................. 60 4.2.1 原型系统总体设计 .................................................................................. 60 4.2.2 节点端系统设计与实现 .......................................................................... 61 4.2.3 基站端跟踪平台设计与实现 .................................................................. 68 4.2.4 跟踪的实现 .............................................................................................. 70 4.3 多目标跟踪仿真系统设计与实现 ................................................................. 72 4.3.1 场景配置功能模块 .................................................................................. 72 4.3.2 模拟系统框架 .......................................................................................... 73 4.3.3 类精确跟踪算法的实现 .......................................................................... 75 4.3.4 集群跟踪算法的实现 .............................................................................. 78 4.4 系统测试案例 ................................................................................................. 80 4.4.1 Mica2平台原型子系统测试 .................................................................... 80 4.4.2 仿真系统测试 .......................................................................................... 82 4.5 本章小结 ......................................................................................................... 82 结论 ............................................................................................................................ 83 参考文献 .................................................................................................................... 85 攻读学位期间发表的学术论文 ................................................................................ 90 哈尔滨工业大学硕士学位论文原创性声明 ............................................................ 91 哈尔滨工业大学硕士学位论文使用授权书 ............................................................ 92 哈尔滨工业大学硕士学位涉密论文管理 ................................................................ 93 致谢 ............................................................................................................................ 94

- V -

哈尔滨工业大学工学硕士学位论文

第1章 绪论

1.1 课题背景

1.1.1 课题来源

本课题来源于某预研基金项目。

随着信息技术的飞速发展，对信息的获取程度越来越决定着一项事业的效率和成功与否。只有掌握了信息权，才能掌握解决问题的主动权。目标跟踪的研究是传感器网络的一个重要研究分支，具有巨大的潜在应用价值。例如，对野生动物追踪，道路交通的实施监控，战场制信息权[1]的获取等等。

由大量体形小、成本低的感知器构成的局域自组网络系统——无线传感器网络，又称感知网，是一种能够部署在多种应用环境下，实时获取、分析、融合环境信息的网络平台，是空、天、地、海一体化的监测系统的重要组成部分。其本身的感知和计算特点能够提供搜索/发现目标，以及跟踪/观测的功能，且随着无线传感器技术的发展，逐渐能够进行复杂的目标识别处理。是应用信息的直接来源。

1.1.2 课题研究目的及意义

本课题的研究目的是：在感知网中，建立多节点协作多目标跟踪模型，在模型中融合单目标跟踪技术，在能够提高跟踪精度和节省能量的目标预测方法以及单目标跟踪技术的研究成果下，采取策略建立一个满足层次精度要求、节省能量的分布式多目标跟踪框架。并依靠上述技术及网络模拟器等支撑子系统，实现感知网中基于能量感知的多目标跟踪系统。

多目标跟踪研究具有多重意义。

首先，本系统是感知网项目中的一个重要子系统，属于整个大系统中最顶层的一种面向主要应用的系统。本系统依托感知网项目网络组所提供的利用传感器节点组成ad hoc网，获取到底层传感器节点感知到的环境信息，从中计算出各个目标的类别、位置和移动轨迹等数据，再将其提供给最上层的决策和规划系统。所以它是整个感知网应用系统的基础，是感知网成功应用的关键。

其次，本系统是感知网应用层与网络层的接口，是网络组设计的网络协议

- 1 -

哈尔滨工业大学工学硕士学位论文

和信号处理组处理结果的直接使用者，设计并实现这样一个基于感知网的目标跟踪系统需要无线网络，信号处理，嵌入式系统等多个领域技术的支持，是检验整个感知网系统性能的一个很好的综合应用实例。

最后，本系统承前启后，在当前众多基于单目标的跟踪技术基础上，融合基于预测目标动向的单目标跟踪技术，提出的一种分布式层次性多目标跟踪模型框架。针对于活动目标监控，多目标跟踪更接近实际，任何单目标跟踪的研究最终都要面向多目标应用。

1.2 与课题相关的国内外研究综述

1.2.1 国内外关于感知网的研究现状

感知网的研究起步于上世纪90年代末期。从2000年起，感知网就引起了学术界、军界和工业界的极大关注。美国自然科学基金委员会，美国交通部，美国国防部和各军事部门都对感知网给予高度重视；IT巨头如英特尔公司也开始致力于微型传感器网络领域的研究；在学术领域，在美国自然科学基金委员会的推动下，美国很多大学都开始了感知网的基础理论和关键技术的研究。加州大学伯克力分校就是其中的杰出代表。

加州大学伯克力分校提出了众多感知网研究领域的基础性算法，其最成功的成果是研制了能够一定程度上作为实例应用的mote节点应用系统，以及其相关的传感器操作系统TinyOS[5]。同时，伯克力分校也研究了感知网的数据查询技术，提出了实现可动态调整的连续查询的处理方法以及管理感知网上多查询的方法，提出了在低能源、分布式无线感知网环境下实现聚集函数的方法，并研制了一个感知数据库系统TinyDB。

此外，美国其它一些高校如麻省理工学院、康奈尔大学、加州大学洛杉矶分校等以及英国、日本、意大利等国家的一些大学和研究机构也都纷纷展开了该领域的研究工作，且相互合作联系越来越紧密，2007年1月19日至21日，欧洲第一届“无线传感器网络论坛”在德国首都柏林举行。

在感知网体系机构各个环节的研究上，目前国外特别是美国研究机构有较成熟技术储备。在节点方面有DARPA资助的Smart dust节点[6,7]和加州大学伯克利分校开发的mote节点；在路由协议方面有基于查询的路由、基于位置的路由和能量路由等协议；在感知网数据管理系统方面，有伯克利分校开发的TinyDB和康奈尔大学研制的Cougar系统[8]；在应用方面有Intel的大鸭岛项目

- 2 -

哈尔滨工业大学工学硕士学位论文

[9]

，A Line in sand等项目，据报道，在2003年的伊拉克战争中，感知网得到了有效的应用。

实际上感知网当前的研究工作还处于起步阶段，大量的问题还没有被涉及。引用研究感知网的知名学者Deborah Estrin 的话[10]，“感知网目前所处的研究阶段就相当于Internet二十年前所处的阶段”，从中可见一斑。

在国内，浙江大学、哈尔滨工业大学、清华大学等高校和以中科院计算所、自动化所为代表的许多研究机构也于2001年之后开展相关方面的研究，国家自然科学基金委员会也增加了对感知网的资金支持力度。目前，国内感知网方面的研究主要集中在传感器节点的设计开发，传感器节点定位，网络路由协议和网络数据管理等方面。就研究水平而言，与国外在深度和广度上来说都有相当大的差距。

在节点硬件平台方面，国内目前出现的许多节点都是仿制国外节点，其中中科院上海微系统研究所和计算所主导设计研制的GAINS节点，和中科大正在做的USTC mote处于相对领先水平，其均是仿制 Berkley的mote系列节点，并且都是运行相同的操作系统平台TinyOS。

在感知网数据管理系统方面，国内还落后很多。目前，还没有哪个国内研究机构研制出性能较为稳定成熟的数据管理系统，哈尔滨工业大学在此方面的研究处于相对领先水平。而国外已经有前面提到被广泛投入应用的TinyDB和Cougar系统。

在感知网应用方面，目前国内还没有成功的应用实例，研究基本上都还停留在实验室阶段。

总而言之，国内在感知网方面的研究，尽管起步不晚，但却落后很多，基本上还处于跟随研究阶段，还谈不上太多创新。未来的研究工作任重而道远。

1.2.2 感知网目标定位与跟踪技术的研究现状

目标定位研究是无线传感器网络（WSN）中一个重要研究方向。在目标跟踪中，定位方法与传感器节点的类型和感知精度有着密切的关系。也就是说，不同的节点类型，要求与其感知类型相对应的定位方法。例如具有距离和角度传感器[11],其定位技术采用的是三角测量法，而采用功能较弱的binary模式传感器却只能利用精确度不高的凸壳质心定位法[12] 。不同的节点数量、功能也对应不同的定位技术，多个节点组成的动态簇定位跟踪算法中，每次定位都由若干个距离邻接的节点协同工作完成，而相对于其处理和感知功能更为强大的某些

- 3 -

哈尔滨工业大学工学硕士学位论文

特殊节点，可以采用信号处理及滤波等方式计算定位目标位置。同时，不同的应用环境也对具体的定位方法有很大影响。实际应用领域中，基于声音节点的目标定位跟踪是比较现实且相对容易实现的方法，本文即考虑高信噪比环境下的声音传感器定位[13,14]。

目前，传感器网络根据声源信号进行目标定位的方法主要有三种：TDOA（time delay of arrival）；DOA（direction of arrival）；能量方法（Source signal strength on Energy）。TDOA方法测出信号到达两个节点之间的时间差来求出距离差，根据距离差得出信号的位置，时间差是通过相关函数来确定的[15,16]；DOA 方法运用信号来源方向的不同来定位[17]。能量方法是利用节点接收的能量进行定位的一种方法[23-25]，其主要是根据声音能量在空气中传播与距离成一定比例地衰减，具体有多种定位方法，具体将在第一章中讲述。本文算法中提出的定位算法即是一种能量定位算法。

目前WSN目标跟踪研究主要集中于单目标的跟踪方法研究，在跟踪算法效率上不断改进和深入。无论采用什么跟踪技术，目标跟踪模型主要可分为两种：集中式跟踪模型，分布式跟踪模型。

早期的目标跟踪模型大都是集中式跟踪模型，例如基于binary感知模型的跟踪算法[18-20,29]。这些模型一般都是经过侦测阶段后，发现目标的节点向基站发送消息，由基站进行测量数据融合，确定目标位置，最后根据所有目标位置点，由基站进行结果融合确定轨迹（一般采用线性拟合算法）[30]。集中式跟踪模型较简单，不需要节点间协作，但它的劣势十分明显，它要求所有数据都传回基站，通信量大，能耗高。正是因为这样，分布式跟踪模型正成为研究主流。

分布式跟踪模型中若干个节点参与侦测，将数据发往其中一个计算节点，由计算节点对测量数据融合，并依此预测目标动向，选择开启下一步的节点。该机制也称为动态簇算法[31,33-35]。计算节点定期将数据发回给基站。分布式跟踪模型是以后的发展趋势。其中，基于目标动向预测技术的动态簇方法是最有代表性的一种分布式算法。其基本思想是在融合目标历史轨迹信息的基础上对目标的下一可能位置进行预测，然后根据预测结果唤醒某相邻节点作为下一定位时刻的计算节点，即簇首(cluster header-CH)，由该节点接替对目标的跟踪[27,28]

。 目前，目标动向预测技术主要基于对目标历史轨迹的分析。例如在文献[36]中，跟踪定位由单节点完成，每个节点定位完毕，就将定位信息和历史数据融合，预测并选择接班节点，同时还将数据传给该节点。用于目标预测的信息可以有许多，除了目标历史数据外，还有目标行动意图，地形因素等。但这些全

- 4 -

哈尔滨工业大学工学硕士学位论文

局性信息底层节点很难获得，因此并不适合目前主流的分布式目标跟踪模型。

分布式感知网多目标跟踪由于一些特有的特征条件和限制，比单目标跟踪更复杂，考虑的情况更多。目前，国内外相对于单目标跟踪研究来说，多目标跟踪的研究很少。多目标跟踪主要要解决的问题有两大类：目标的分类和跟踪[38]

。分类是指感知到的多个目标可能是多个不同种类的事物，其不是本文的主要研究内容，因此将不作叙述。同单目标跟踪，多目标跟踪要解决的主要问题是对每个目标通过次序定位，得到目标的尽可能精确的轨迹。由于多个目标之间可能存在相互影响，特别是同类目标的相互影响，因此，要准确一一对应所有目标和所有定位点的关系相当困难。在机动多目标跟踪理论的发展过程中，其研究困难主要来源于两种不确定性，一是目标运动方式的不确定性，二是量测起源的不确定性。目标运动方式的不确定性主要指目标的前进状态，包括方向、速度、加速度的不可判性。

量测起源的不确定性，是指传感器接收到的量测信息与感兴趣的目标对应关系的不确定性， 即多目标跟踪问题中著名的数据关联问题[41,42]。在机动多目标跟踪领域的研究内容中，数据关联是最重要而又最困难的部分。目前提出的多目标跟踪数据关联算法大都针对多雷达传感器环境下多目标的跟踪，其中包括著名的概率数据关联算法[43]、联合概率数据关联算法、广义联合概率数据关联算法[44]以及相关的改进算法等等，以及一些粒子滤波算法[45,46]；而关于无线传感器网络环境下的多目标数据关联的研究相对较少，文献[47-49]对此进行了阐述。目前，传感器网络多目标跟踪相关研究主要集中于节点感知处理能力的基础上，对跟踪策略和方法的研究。文献[50]方法将节点分级，围绕顶层节点形成跟踪簇，通过不同级别节点本地处理后的相互通信，实现多目标的层次化跟踪，使得一定程度上降低能耗，且能纠正低层次节点的计算错误。文献[51]通过目标状态表示相关研究提出了一种多目标跟踪方法，并给出一个跟踪框架，但关于多目标其采用集中式的跟踪方法。文献[52]描述了一种分布式方法，且对目标相遇的几种情况进行了详细剖析并给出了目标分离跟踪算法。

1.3 本文的主要研究内容

本文的研究内容主要包括以下几个方面：首先从提高定位精确度和可靠性出发，提出一种新的单目标定位算法；并基于节省能量消耗考虑，对基于目标动向预测的动态簇跟踪算法进行改进。然后，在此基础上对多目标跟踪的场景进行分析并对相应跟踪算法进行了阐述。最后，在理论研究的基础上，实现了

- 5 -

哈尔滨工业大学工学硕士学位论文

基于Mica2的mote节点原型系统和感知网多目标仿真系统的开发。

1.3.1 感知网单目标定位与跟踪算法研究

单目标定位跟踪算法研究是多目标跟踪算法研究的基础，其研究成果相对丰富且较为成熟。因此本文在已有研究成果的基础上首先对单目标跟踪展开研究。

首先要解决的是目标定位问题。本文所有理论基于声音传感器模型，因此定位算法也是基于声音能量的定位算法。已有的质心定位算法计算简单但定位精确度低，高精确度的信号处理法须进行复杂的计算，方程组法很容易发生无解或虚根情况。本文综合考虑几种定位算法优缺点，提出了距离-量测定位算法。该算法根据量测随着目标距离的增长而指数级下降的关系，将节点感知半径划分为若干区间段，每个区间定义一个“标准”量测或简单的线性计算方法，定位时即以该区间的标准量测代替实际量测去查找对应的距离，或根据实际量测和简单的线性计算方法去计算距离；然后根据多个节点提供的节点-目标距离信息列方程组计算定位点。对于方程无解或虚根的情况，采用最大概率以及误差折中的方法去选取适当的点作为定位点。

目标跟踪算法方面，继承基于目标动向预测的动态簇跟踪算法的已有研究成果[28]，并对其进行改进，提出“太子簇首-距离-量测”定位算法，节省节点能耗。具体地，从簇首的产生机制考虑，已有的算法大多采取无序竞争或时间戳选取的方式获得新簇首，维持跟踪的继续，每个节点都须发送竞争或参与选取消息。本算法从“预定”的角度出发，当前簇首定位完毕后，根据预测结果及周边节点位置选定某个节点作为下一定位时刻的簇首，即“太子簇首”，以避免竞争或选取，从而消除了竞争消息或选取消息的发送，很大程度上节省了节点能量。对于太子簇首选定失败或定位失败情况，采取“异常”进行捕捉，若“异常”也失败，最后再采取“竞争”的方式进行跟踪。因而，既能保证节点及网络能量的节省，又对保证跟踪的完备性和可靠性。

1.3.2 感知网多目标跟踪算法的研究

感知网多目标跟踪以单目标为基础。本文首先对多目标场景进行分析，参考单目标，讨论多目标情况下会出现的种种问题。从多目标跟踪问题复杂性的来源——多个目标的信号混杂出发，针对目标的不同密集程度，提出了“远距离单目标跟踪——稀疏多目标类精确跟踪——密集多目标集群跟踪”框架。远

- 6 -

哈尔滨工业大学工学硕士学位论文

距离单目标跟踪即是目标距离很远时对每个目标采取单目标跟踪，互不影响。

目标分布稀疏但相互噪声混杂，对节点定位产生影响时，我们提出一种稀疏多目标的类精确跟踪算法。该算法主要思路是每个节点维护全局统一时钟，根据预测信息对节点量测进行加权分解。若预测方程足够准确，则某定位时刻，节点量测来源于多个目标，但每个目标到节点的预测距离即可根据预测方程和节点的时钟信息计算得到，然后根据各目标预测距离的比例关系对节点实际量测进行分解，得到每个目标对应的量测大小。即可由上述1.3.1所讲的距离-量测定为算法进行定位。实现了多个目标逻辑上的“独立”跟踪。

若多个目标距离很近，信号混杂严重，或目标运动不具有线性特征，以及预测信息不够准确，都会跟踪失败，丢失目标。此情形下，我们从目标密集的状态属性出发，不再力图对每个目标实现尽可能的精确区分，得到每个目标的跟踪轨迹，而视这些目标为一个整体，采取一种集群跟踪算法。同样，每个集群簇包含簇首，其进行集群定位、预测以及集群通告等动作，只是相关细节机制有所修正。

1.3.3 论文结构

以上就是本文主要研究内容，下面三章将就以上内容展开详细的分析和讨论。第二章首先介绍提出的“距离-量测”定位算法，随后讲解单目标“太子簇首-异常-竞争”动态簇跟踪算法；第三章简要介绍跟踪框架，详细介绍该框架内的稀疏多目标类精确跟踪算法和密集多目标集群跟踪算法；第四章则介绍基于Mica2平台的原型系统和针对本文算法的感知网多目标仿真系统的设计与实现，并给出了系统的测试案例。

- 7 -

哈尔滨工业大学工学硕士学位论文

第2章 感知网单目标定位跟踪算法研究

2.1 距离-量测定位算法

本文所有的理论算法基于声音感知模型的传感器节点，因此，定位算法研究也是基于声强变化的能量算法。本节首先对基于感知能量的定位算法简要阐述，随后给出本文的距离-量测定位算法，最后给出实验验证。

2.1.1 基于感知能量的定位算法

基于感知能量的定位方法主要是根据声音能量在空气中传播与距离成一定比例地衰减，具体有多种定位方法。Binary质心定位方法[18]根据多个节点感知范围重叠将目标定位到一个区域内，最大似然法按照最大似然概率最大的方法搜索目标可能区域，方程法及量测对比法根据节点量测及其之间比值建立相关方程，求解目标位置。Binary质心方法计算简单，快速，实时性强，但定位精度最差；最大似然法通过搜索所有可能区域，定位精确度和可靠性高，但计算复杂度高，计算速度慢，实时性差；方程求解法虽提高了精确度且运算快，但由于误差的存在和不可消除性，很可能会产生无解或虚根情况。本文针对道路交通、战场等高信噪比应用环境，在比较分析该三种方法的基础上，从定位精度、误差大小、计算复杂度的角度出发，将Binary方法与方程法结合，提出了一种新的定位方法——“距离-量测”定位算法。本小节探讨基于能量的定位算法相关内容。

2.1.1.1 声音节点感知模型

声音传感器节点感知模型是指节点收到的感知量测与目标距离的关系。一般情况下，目标声源的能量会随着传播距离的平方成反比例衰减。设C为节点距离目标1米处的量测大小，可以看作目标固有声源能量大小。节点位置和声源目标位置分别用矢量pi和pt表示，则根据信号以与距离平方成反比的方式衰减的原理，第i个传感器接收到的信号能量，即节点量测为Zi：

zi?C?vi2 (2-1) pi?pt2其中，vi表示高斯白噪声干扰，期望值为Evi2?0，均方差为σi。pi?pt- 8 -

哈尔滨工业大学工学硕士学位论文

22为信号源与传感器节点之间的距离， 在二维平面中pi?pt?(xi?xt)?(yi?yt)，

2?i/M)分布，其中M为(xi,yi)、(xt,yt)分别为节点i和目标t的坐标。vi服从N(?，抽样次数。

2.1.1.2 几种能量定位算法

本节简要介绍几种简单的能量定位算法。并概述其优缺点。 (1) 基于Binary感知模型的几何质心定位方法[18,19]

224SS21S3 图2-1 Binary感知模型定位方法 Fig. 2-1 Locate method of binary sense mode

传感器节点只提供“是否发现目标”的信息，每个节点有固定的感知半径，利用多个传感器节点的探测范围有相交的特点，采用几何求质心的方法定位目标，如图2-1。因此，重叠节点数越多、重叠区域越小，越有利于定位精度的提高。虽然通信量和计算量都很小，但该方法的致命缺陷是其始终只能将目标“锁定”到一个区域。特别是当节点感知半径很大，或探测相交节点数很少时，其效果更差。

(2) 最大似然法[21] 由公式(2-1)，有

根据

vi2?zi?C2pi?pt (2-2)

vi22222?4/M)服从N(?，分布，设di?(xi?xt)?(yi?yt)， i?i?Evi2??i2，?'i2?D(vi2)?2?i4/M。M为采样数，则在M足够大的情况下，

zi?C??i2di?i'2服从标准正态分布N(0,1)。共有N个传感器节点，每个vi服从正

态分布且相互独立，则其联合概率，即最大似然函数为（设目标固有声源能量C已知，未知量x,y）：

- 9 -

哈尔滨工业大学工学硕士学位论文

C??zi???Ni????12?di2F(x,y)?(2?)2exp???()?'2?i?1i?? (2-3) ????N设?表示未知量(x,y)，则

??argmaxlnF(x,y)?argminQ(x,y) ??Q(x,y)??Nzi?C2??idi()2i?1?i' (2-4)

要实现似然函数的最大化需要搜索相关节点的感知区域。该方法考虑到噪

声干扰，求似然最优解，定位精度精确且可靠。但该算法计算量复杂，定位时间长且节点能量耗费严重。设想10×10米的场景，若精确到1米，即有100种搜索可能。因此计算量将相当大。即便是一些改良的方法，如非线性最小二乘法和线性最小二乘法、约束最小二乘法等等，也都需要较大的计算及能耗。

(3) 方程法及能量比例法 公式(2-1)中，理论上，在C已知的情况下，若忽略噪声vi干扰，根据节点收到的声音能量量测可以确定目标声源与节点的距离，多个节点交换距离建立方程即可完成定位。如图2-2(a)，

2Sd13Sd21Ta)S2Sd1d13Tb)d2S2

图2-2 距离方程定位算法

Fig. 2-2 Locate algorithm of distance equation

两个节点S1、S2分别到目标T的距离d1、d2确定了两个圆。理论上，若d1、d2足够准确，则两个圆相切于一点，该切点即为目标位置。同样，三个节点的情况下，三个圆相切于一点，图2-2(b)。该方法计算量小，运算速度快，但由于节点感知能力以及实际中噪声的不可消除性，节点提供的距离不可能十分准确，有可能误差非常大。从而导致定位误差偏大，有时噪声能量对信号的影响过大甚至会导致方程无解或出现虚根。而此方法一般也需要对量测信号进行采样，

- 10 -

哈尔滨工业大学工学硕士学位论文

根据量测平均值对公式(2-1)求解得到距离d。

有的方程法是利用两个节点接收的能量的比例来计算[22]，得到几个圆的方程，然后根据最小均方或其他数据处理方式求交点，这种方法在于基于比例的运算，消二次项，得到线性方程等，但由于比例系数的误差，会导致误差的传递，使最终的结果精度相对来说不高。

上述三种定位方法是声音感知节点基于能量定位的典型方法，其各有利弊。总体上来说，每一种方法都是对节省能耗、运算速度、定位精度的一种选择，只是侧重点不同而已。

2.1.2 距离-量测定位算法

2.1.2.1 算法整体思路及距离-量测表

定义2-1 距离区间：节点根据自身量测，确定其到目标的距离。由于噪声及误差的存在，该距离不会十分准确。因此，将该距离值改成一个范围区间，见图2-3。每个节点提供的不是一个具体的距离值，而是一个范围，[d1,d1')和

')[d2,d2，称为距离区间。距离区间表示节点到目标的距离在该区间范围内。

算法基本思路：针对Binary质心方法的“区域性”和方程法的“误差敏感性”，采取一种折中的思路，将两种算法结合，本质上即是将Binary的“重叠区域”缩小，将方程法的“可容忍误差”范围增大，形成一种新的定位算法，使得相对于Binary方法定位更准确，相对于方程法噪声及计算误差更可容忍。如图2-3所示。根据距离区间定义，图2-3(a)中，将目标范围缩小到两个更小的子区域（阴影处），再根据第三个节点信息即可确定；2-3(b)表示了另一种情形。

d'11d2'2d'11d22'2dS1a)S2ddS1b)Sd

图2-3 距离区间重叠图

Fig. 2-3 Sketch map of distance-interval overlap

定义2-2 距离-量测表：根据公式(2-1)，节点到目标的不同距离对应不同的量测值，根据先验信息，建立该距离与量测的对应关系。存储于节点上，称为距离-量测表。

- 11 -

哈尔滨工业大学工学硕士学位论文

考虑到目标声源所提供的高信噪比以及节点的存储能力，将节点的感知区域划分为多个区间，对应定义2-1的距离区间，建立距离-量测表，存储在节点上。如图2-4（以二维平面示例）。2-4(a)为节点感知区间的划分，图中将此节点的感知范围划分为4个区间，最大的距离d4对应节点的感知半径。2-4(b)为距离

d4d3d2距离d1d2d3d4量测n1n2n3n4Sd1

a)节点感知区间划分 b)距离-量测表

图2-4 距离-量测表的建立

Fig. 2-4 Construction of distance-measure table

-量测表。ni表示目标距离为di时，节点收到的量测大小，是一种先验信息。

在求取节点到目标的距离（区间）时，根据当前量测值查找距离-量测表，通过简单运算，获得估计距离。根据精度的要求以及区间的划分密度不同，具体的方法有多种。一种方法是将di到di+1的能量衰减视为线性的：设n为节点当前量测，ni?n?ni?1，则选取距离

ni?1?nid?d? id?d?(n?ni) (2-5)

ii?1另一种简单的方法是选取对应区间的中点作为目标距离，如图2-5中的变

换。节点感知量测为n。

距离量测感知强度选定距离d1d2d3d4a)n1n2n3n4n <= n1d1n1< n <=n2(d1+d2)/2n2< n <=n3(d2+d3)/2n3< n <=n4(d3+d4)/2b)

图2-5 距离-量测表的查找 Fig. 2-5 Search of distance-measure table

距离区间的划分越小、区间数越多，目标距离选定的精度越高。实际中，

- 12 -

哈尔滨工业大学工学硕士学位论文

可以根据应用场景对定位精度的具体要求对节点感知区间进行划分。具体地，此处给出目标距离概率方程。

i表示传感器节点i的感知半径，?表示距离区间大小，n为距离区间设Rdi

i?di，n?Ri/?。z为节点当前量测，di表示根据量测z查表数。则?i?dkziiid?1k得到的目标距离，dT表示随机给定的目标距离，Fi(dT)z表示在当前量测zi的条

i件下，目标距离为dT的概率。ri是一个与节点自身相关的值，?(ri,?i)是与节

i同一距离区间内的点概率值算且根据距离-量测表的查找方法选定，我们取与dz相同且值为1：

i,?(r,?))分布。为简化计点自身属性及距离区间相关的函数。则有dT服从N(dziiF(dT)zii

??1,其中(dT%?i)?(dzi%?i)(1)???1??(dT?dzi)2????'?12?fi(dT)??i(2?)exp??2?'2?,(dT%?i)?(dZ%?i),??i??? (2-6) '2?f(d)为概率密度方程,???(r,?)(2)iii?iT即目标处于与dZ同区间的所有点处的概率值同为1，其他区间的所有点服从公式(2-6(2))的正态分布。

通过上述分析，该算法有效工作的前提条件如下：

条件2-1：目标声源恒定，且预先已知。感知节点是根据收到的量测大小和先验数据来判断目标距离的，变化或者预先未知的声源目标无法进行跟踪。

条件2-2：网络满足不小于两度覆盖。即任一位置都同时处于至少两个节点的感知范围内。由上述分析，此条件显然很重要。且最好是满足三度覆盖。否则，虽然通过两个节点信息可以大致求出目标位置，但偏差很大。 2.1.2.2 定位场景分析

定义2-3 感知圆：节点S根据当前量测Z查找距离-量测表得到量测距离dZ，则以S为圆心，dZ为半径形成一个圆，称为感知圆。其含义表示目标当前最有可能处于该圆线上或其周围区域。参考公式(2-5)。

算法根据多个节点的感知圆信息对不同场景建立不同方程，求解交点得到目标位置。其会产生两个可能问题：若感知圆不相交则导致方程无解，多个感知圆相交于多点会有多种可能解。针对这些问题，兼顾定位精确度和误差考虑，对多个场景下的定位进行了分析，并给出了相应的近似解方程。设参与定位的节点数为N，已知Fi(dT)z表示节点i距离目标为dT的概率（参考公式(2-6)），定

i义联合概率方程

- 13 -

哈尔滨工业大学工学硕士学位论文

F(dT)Z??NiTFi(dT)z,iZ???z1,z1,...zN??T (2-7)

则目标定位点的选取应使d满足F(dT)Z最大。因此，对于方程无解的情况，

可以根据使该联合概率最大的原则去选取定位点。对于多个可能解的情况，将依据该规则以及误差最小要求和运算的复杂性小的策略去折中选取定位点。每个节点提供的目标距离信息精确的说应该是一个区间，即应该是一个圆环，见图2-3。但在具体计算时，需要定位出一个具体点，因此在分析场景及求解方程时，我们应用量测距离dZ来表示该区间，进行场景分析及方程求解。2.1.2.3节将给出该方法合理性证明，也即证明该距离-量测算法的正确性和可行性。图2-6和图2-7分别对两个节点和三个节点进行了场景分析。

dz12dzS1a)相切S22S1ABdzS2d1zDCd1zS1AB2dzS2b)相交c)相离

图2-6 两个节点下的定位 Fig. 2-6 Localization of two sensor nodes

图2-6描述了两个节点情况下的定位。节点S1和S2提供的目标量测距离分

i)表示节点i的感知圆，Si为节点坐标，2别为d1形成两个感知圆。用r(Si,dzz和dz，

idz为目标量测距离。目标定位点pT，Si、pT都为矢量值。二维空间下，

Si??x,ys??s???T??pT??x,y?。两个圆的几何位置关系，存在三种可能。 ,TTi??Ta) 两圆相切。图2-6(a)。这是最理想的情况，取切点为目标定位点。

2pT?r(S1,d1z)r(S2,dz) 2b) 两圆相交。图2-6(b)。交点r(S1,d1z)r(S2,dz)?{C,D}。则按照联合概率最大规则，应该选取点C或D。但根据当前已有信息，无法确定具体哪个点。相对

于其它点，虽然选定其中某个点可能更精确，但若选错，误差也更大。因此，进行一种折中。设A、B分别为弧CAD和CBD的顶点。则选取A、B连线中点作为目标位置。

pT?(pA?pB)/2 c) 两圆相离。图2-6(c)。点S1、S2连线与两圆分别交于点A、B。根据联合概率最大及误差最小的折中，取A、B连线中点作为目标位置。同2-6(b)。

参与定位的节点越多，则定位交叠区域越小，定位精度越高，但通信量和计算量也越大。一般情况下，三个节点的定位精度可以满足大多数要求。图2-7

- 14 -

哈尔滨工业大学工学硕士学位论文

对三个节点定位进行了概括分析。

S3S1d1zdz33S3dzBCAa)2dzS1BC2dzS2d1zTAS2b)3S3dzS1d1zAB2S2dzS3d3zc)3S3dzd1zS1CABS2d)3S3dzdz1ABS22dzdzS1AB1C2dzS1e)S22dzf)

图2-7 三个节点下的定位

Fig. 2-7 Localization of three sensor nodes

三个节点情况下，目标距离信息形成的三个感知圆的几何关系有多种，本文主要分析了其中6种典型情况。其他的都可以类比到这些当中，采取相同或

相似方法。

a) 两个圆相切，分别与第三个圆相交。图2-7(a)。距离较近的两个交点和切点形成三段圆弧，为使联合概率尽可能大和误差尽可能小，理论上应该选取到三段圆弧距离相等的一点作为定位点。具体计算时，考虑到降低计算复杂性，视圆弧外接三角形的边为圆弧的近似，取该三角形的内切圆圆心为目标定位点。

ni[,(,G])rsd如图2-7(a)，三角形ABC。设m表示点集合G中距离圆r(s,d)最近的点，

inscribedcircle(ABC)表示三角形ABC的内切圆。则此种情况下目标定位点

2pT?inscribedc(iABCrcle)A?r(S1,d1。其中，z)r(S2,dz)23132B?min[r(S1,d1 z)r(S3,dz),r(S2,dz)]，C?min[r(S2,dz)r(S3,dz),r(S1,dz)]。

b) 三个圆两两相切。图2-7(b)。三个切点A、B、C形成三角形ABC。同

2-7(a)，选定其内切圆圆心为目标定位点。pT?inscribedcircle(ABC)。

c) 一个与另外两个分别相交，另外两个圆相离。图2-7(c)。同样为了使联

2合概率最大且误差最小，理论上应选取圆弧AB上距离圆r(S1,d1z)和r(S2,dz)相等且最小的一点作为目标定位点。考虑到计算要求，我们取线段AB中点作为

- 15 -

哈尔滨工业大学工学硕士学位论文

3)2]r(S1,d13d,z,r(S2d,z)目标定位点。即pT?(pA?pB)/2。其中，A?min[，z)r(S2)r(S3,d3),r(S1,d1)]B?min[r(S2,dzzz。

d) 三个圆两两相交。图2-7(d)。类似于2-7(a)，选取圆弧外接三角形的内切

圆圆心为目标定位点，区别只是此处三角形的三个顶点都为圆的交点，而2-7(a)

dcABCirc)l。e其中，中有一个为切点。因此，目标定位pT?inscribe(1,]，32),r1(Sdz)B?min[r(S1,d1，z)r(S3,dz),r(S2,dz)]23C?min[r(S1,d1z)r(S2,dz),r(S3,dz)]。

e) 两个圆相交，都与另一个相离。图2-7(e)。

3)23B?min[r(S1,d1连接点B和S3的直线与圆r(S3,dz交于点A。z)r(S2,dz),r(S3,dz)]，

即A为圆r(S3,d3)上到B最近的点。综合联合概率、误差、计算复杂度的考虑，取线段AB中点为目标定位点。设min[G,p]表示点集合G中距离点p最近的点，

23则目标定位点pT?(pA?pB)/2。B?min[r(S1,d1z)r(S2,dz),r(S3,dz)]，2)r(S3A?minr([S2d,z3d,z3)},B]A?min[{p|p?r(S3,dz。

f) 三个圆两两相离。图2-7(f)。选取三个圆的最小公共外切圆圆心为目标定位点。也即到每个定位圆距离相等且最小的一点。设dis[p,r(S,d)]表示点p

3)])距离。则目标定位点pT?min[G,r(S3,dz到圆r(S,d的，其中

1G?{p|dr[i(Ss1,,pd?)z2r[d2S(i,zsd,p?)]r3[S3d,idz。

(s,p)]}表面上，上述几种场景定位点的选取策略基本上都是选取到每个节点感知

圆距离均等的点作为目标定位点。其本质上都是对三种定位属性的折中：联合概率最大、误差最小以及计算复杂度尽可能低。理论上还有其它几种可能的位置关系情况，但出现的可能性很小，即使出现，也都类似于上述情况，采取同样的选区策略即可。

2.1.2.3 算法有效性证明及误差分析

(1) 距离-量测的有效性 由公式(2-1)，有

2C2di?pi?pt? zi?vi2 (2-8)

应用公式i求目标距离，在条件目标源C，节点量测zi以及噪声vi2已知的

情况下，理论上可以求出目标的距离。但该应用还包括一个“隐性”条件：噪

22?4/M)声vi2的期望、方差及稳定性。一般情况下，vi2服从N(?，，对于方差，i理论上采样次数M无限大，其可以无限小，从而使di2计算趋于稳定，误差很小。但实际中，噪声固有方差?i有可能很大，且目标跟踪的实时性要求使得采样数

4- 16 -

哈尔滨工业大学工学硕士学位论文

M不可能很大。同样，若噪声期望?2相对于目标声源过大，即会使得分母zi?vi2随噪声变化十分敏感，从而使di2计算变化剧烈，误差增大。因此在实际应用中，应该充分考虑这些条件。而本文的距离-量测算法基于高信噪比应用环境，使得

4即使噪声?2或?i比较大，任意时刻目标对节点的量测“贡献”仍远大于噪声对量测的影响，即

C??vi2C2，因此有zi≈即可以在误差允许的范2。pi?ptpi?pt围内，忽略噪声对节点的影响，依据公式（2-1）来计算距离。

(2) 近似方程法的有效性

在2.1.2.2节中，我们应用感知圆近似目标所在圆环来分析场景，来建立并求解方程，得到目标位置。其中，每一种场景近似及目标位置的选定，都是对联合概率最大、方差最小、计算复杂度最低的一种折中。本小节以两个节点为例，分析这种感知圆近似方法以及此种折中方法的正确性和可行性。

图2-8、2-9、2-10描述了在两个圆环的位置关系。如图中圆环，内外径分别为din和dout。类似于圆的定义，我们用r(S,[din,dout])表示圆环。其含义表示目标处于该圆环内的概率为1（见公式2-6），中间圆r(S,dZ)即为感知圆。

dZ?[din,dout]，具体由选定算法确定。假设此处采用图2-5中的量测距离选定

办法，即dZ?(din?dout)/2。图中阴影部分为圆环交叠区域，其联合概率最大，为1。下面对比图2-6的感知圆r(S,dZ)相切、相交、相离的位置关系，具体分析实际场景。

dindoutS1S22dzd1z 图2-8 两感知圆相切

Fig. 2-8 Tangency of two sense circles

D1S1d1zTS22dzS1S22dzS1TS22dzd1zb)d1zD2c)a)

图2-9 两感知圆相交 Fig. 2-9 Intersect of two sense circles

- 17 -

哈尔滨工业大学工学硕士学位论文

① 感知圆相切。如图2-8。显然，切点处于阴影部分，因此，其联合概率也为1，满足联合概率最大的要求。见图2-6(a)。 ② 感知圆相交。如图2-9。由于每个感知圆都处于节点感知圆环中。因此，感知圆相交情形，对于感知圆环而言实际上有图2-9中的三种情形。 a) 图2-9(a)。相当于图2-8中的两个圆环相互靠近，距离缩小。此时，两个感知圆相交，但圆环的交叠区域仍为一体。同样，类似于①，基于联合概率及误差的综合考虑，选取交叠区域（图中阴影部分）

的中心点作为目标定位点是最优的。图2-6(b)中选取感知圆圆弧顶点连线中点的方法即是选取该叠交区域中心点。因此，图2-6(b)的方法可用，且其考虑了计算复杂度。

b) 图2-9(b)。两圆环继续靠近，使得圆环的内环形成的圆r(S1,din)、

r(S2,din)相切。同样，若[din,dout]i相同，图2-6(b)的中点方法即是对

该切点的选取。

c) 图2-9(c)。两圆环距离继续缩小，交叠区域被“分割”成两部分D1和D2。两部分的联合概率都为1，选择任一部分的一点都可使联合概率最大。然而若目标实际位置处于D1，而选择D2中一点，虽满足联合概率最大要求，但误差会很大。实际中，可以牺牲部分概率，与误差折中，选择区域中间一点作为定位点。图2-6(b)的中点选取方法即是该概率和误差的折中。

S1S22dzS1Td1za)d1zb)2dzS2S1TS22dzd1zc)

图2-10 两感知圆相离 Fig. 2-10 Partition of two sense circles

③ 感知圆相离。如图2-10。与图2-9相反，两个圆环相互远离，距离变大。

同样，其有三种情形。图2-10(a)中两圆环部分相交。2-10(b)中两圆环外环形成的圆r(S1,dout)、r(S2,dout)相切。2-10(c)中两圆环完全相离。三种情形分别对应图2-9种的三种情形。因此，根据②中对图2-9的分析，综合联合概率及误差的折中考虑，图2-6(c)的中点方法同样是可行和有效的。

上述详细分析了两个节点情况下，本文距离-量测算法及方程近似法的工作

- 18 -

哈尔滨工业大学工学硕士学位论文

情况。说明论证了算法的合理性及可行性。三个节点的具体情形更复杂一些，但类似于两个节点情况，其定位点具体选定都是对联合概率、误差和计算复杂度的一种有效折中。此处不再详述。

(3) 算法误差分析

本文整体的定位方法包括距离-量测和方程近似两部分，因此误差也来源于此两部分。

根据距离区间的定义，其表示节点到目标的距离在该区间范围内。理论上目标应处于某个圆线上，而该距离区间将该圆线“放大”到一个圆环区间。根据上两小节对两个圆环相交的分析，该区间越小，则圆环交叠区域越小，定位精确度越高。用erange表示该距离区间的误差，?表示距离区间大小，dcirque表示

rnge两个圆环距离，具体地，dcirque=dis[r(S1,[din,dout]),r(S2,[din,dout])]。则ea是?和

dcirque的函数erange??(?,dcirque)，每次具体计算时，r(S1,[din,dout]),r(S2,[din,dout])已知。因此，?(?,dcirque)是关于?的增函数。实际中，节点感知半径Rd固定，距离区间?越小，则误差erange越小，但区间数会增多。需要根据实际情况具体调整。

方程近似法选取目标定位点的误差分析。根据dZ的含义以及F(dT)Z的定义（公式2-6），有F(dZ)z?1。dT表示目标到节点的距离。另F(dT)z?1处的点表示目标精确位置，误差为零，这样的点可能有几个，但理想情况下，如图2-6（a)两个节点即可确定出唯一一点。因此，可以根据选定点的联合概率F(dT)z到F(dT)z?1的点的相对概率距离来表示定位误差。设eformular表示方程近似产生的误差，dS表示图2-6和图2-7中选定的定位点：

eformular?(1?F(dS)z)?dZ (2-9)

综上两部分误差，距离区间误差的产生是由于距离区间的“范围性”，方程近似误差的产生是由于基于概率和误差以及计算复杂度的折中，近似选取定位点产生的。因此，算法的总误差应是两种误差的最大值，设etotal为算法总误差：

etotal?max(erange,eformular) (2-10) 注意，上述误差分析结果etotal只是表明目标定位的一个最大可偏差范围。即每次定位的误差应属于区间[0,etotal]内一值，而并非etotal。

2.1.3 仿真验证

本节对本文算法进行仿真验证。对比Binary质心定位，给出本算法误差统计，并对不同距离区间情况下的误差给出对比分析。

- 19 -

哈尔滨工业大学工学硕士学位论文

a) 质心定位b) 量测-距离区间定位(4个区间)c) 量测-距离区间定位(8个区间)d) 量测-距离区间定位(40个区间)定位点目标实际轨迹目标跟踪轨迹

图2-11 定位精度对比

Fig. 2-11 Comparison of localization precision

如图2-11，模拟场景为1000×1000m 区域，节点感知半径为40m，无线通讯半径为140m。2-11(a)为采用Binary三角形质心定位算法定位跟踪结果。其余为本文中提出的距离-量测区间算法跟踪结果。分别将感知半径分为4、8、40个区间。即距离区间分别精确到10m、5m和1m。定位误差采用定位点到目标实际位置的平均距离来表示。

n22?(xloc?xreal)?(yloc?yreal)error?i (2-11) n(xreal,yreal)为目标真实坐标，(xloc,yloc)为定位坐标。实验结果见表2-1。

表2-1 Binary及不同参数下的距离-量测定位(DM)误差 Table 2-1 Error of localization of Binary algorithm and DM algorithm

定位方法 error(m) 质心定位 距离-量测 (4区间) 9.47 4.94 距离-量测 (8区间) 3.68 距离-量测 (40区间) 3.15 如表2-1。距离-量测区间法的定位精度较质心定位有很大提高，且算法本身的定位精度随着距离区间划分密集化而提高。实际中，这当然也得考虑到节点的存储和查询能力。且较之传统方程法，该算法不会出现无解或虚根情况。

- 20 -

哈尔滨工业大学工学硕士学位论文

2.2 “太子簇首-异常-竞争”单目标跟踪算法

本节详细叙述基于改进预测动态簇方法的“太子簇首-异常-竞争”跟踪算法，绪论中对预测动态簇方法已有所描述。本算法对节点进行分类，从簇首的选取机制进行改进，达到减少消息发送，节省能量的目的。

2.2.1 节点分类机制

任何一个定位时刻，当前簇首定位出目标位置后，对目标轨迹进行预测，根据预测结果对整个跟踪区域进行划分，如图2-12所示。

L0S5S3douter外区域dborderdinnerL4R1AS1S2S4S4S6L3边缘区域L2内区域L1内区域R2边缘区域外区域A：当前定位点 S1：当前簇首 S4：预定“太子簇首”

图2-12 节点分类机制

Fig. 2-12 Diagram of sensor classification mechanism

两个圆分别为目标当前的触发区域和下一时刻的预测触发区域，圆心即为当前的定位坐标和下一时刻的预测坐标。S1为当前簇首，A点为S1定位出的目标当前位置。L1为S1根据历史定位信息计算出的预测方程。过当前簇首S1作预测方程的垂线L0，将感知区域划分为两个子区域：R1和R2。在R2区域作一组平行线L2、L3、L4对R2进行细分，其到预测方程L1的距离分别为dinner ,dborder 和douter。给出区域和节点分类定义：

定义2-4 非通告候选区域：区域R1。在目标转向不超过90度的假设前提下，该区域传感器节点无需唤醒。

定义2-5 通告候选区域：区域R2。在目标转向不超过90度的假设前提下，被唤醒传感器节点位于该区域。进一步，该区域又被分为三个区域：

定义2-6 内区域：Rinner。Rinner?{p|dis(p,L1)?dinner- 21 -

p?R2}，dis(p,L)

哈尔滨工业大学工学硕士学位论文

表示点p到直线L的距离（下同）。

定义2-7 边缘区域：Rborder。Rborder?{p|dis(p,L1)?(dinner,dborder]p?R2}。 定义2-8 外区域：Router。Router?{p|dis(p,L1)?(dborder,douter]p?R2}。

如图2-12所示，L1，L2之间区域属于内区域Rinner，L2，L3之间区域属于边缘区域Rborder，L3，L4之间区域属于外区域Router。

定义2-9 节点类别：内区域内的节点为内节点，边缘区域内的节点称为边缘节点，外区域内节点称为外节点。

节点类型的确定紧密依赖于三个相关值：dinner ,dborder 和douter。其大小根据不同感知模型节点的属性动态调整，获得最优值。本文中的声音传感器节点，其感知模型：

ifRdetect?r?dis(Si,T)?0,?????P(Si)??e,ifr?Rdetect?dis(Si,T) (2-12)

?1,ifRdetect?r?dis(Si,T)?其中，dis(Si, T)表示目标点T (x, y)到传感器Si的距离；α= dis(Si, T)- (Rdetect-r)，

β和λ为经验常数，Rdetect为节点感知半径，r是一个与节点自身相关的值。则P(Si)表示节点Si发现位于该点目标的概率公式[18]。因此，根据该公式，可以选取dinner = Rdetect – r, dborder = Rdetect, douter = Rdetect + r。使得从内区域到外区域，节点发现目标的概率从大到小。具体地，内节点发现目标概率为1，外节点发现目标概

?率为0，边缘节点为e???。

2.2.2 “太子簇首-异常-竞争”算法

2.2.2.1 算法描述

定义2-10 太子簇首：由当前簇首确定的预测方向上有可能成为下一定位时刻簇首的节点。

算法的基本思想：从新簇首的产生以及新簇的确立过程考虑，突破CH一般情况下采用 “选举”或“竞争”的思想，而是采取“太子簇首”的方法。即当前CH根据预测方向上的邻居节点分布以及节点分类情况，选取最适合的节点预订为下一定位时刻的簇首。从而避免“选举”或“竞争”带来的通信负载和无线信号冲突，节省能耗且提高跟踪效率。对于预测误差过大或目标偏离带来的“太子簇首”选取失败的情况，则采取传统的“竞争”方法。

算法要解决几个主要问题是“太子簇首”选取、唤醒通告和新簇的形成。 (1) 太子簇首的选取

- 22 -

哈尔滨工业大学工学硕士学位论文

太子簇首由当前簇首确定。选取的方法有多种，主要依据跟踪精度和目标运动速度。例如，在当前簇首可直接通信的范围内，选取距离最远的那个内节点为太子簇首节点，如图2-12中节点S4。这样可以减少定位点，从而降低整体能耗，但可能带来定位点密度的减小，从而有一定的跟踪精度损失。选取距离较近的节点如S2可以提高定位密度和跟踪精度，又增加了能量消耗。因此，实际中，应在满足跟踪精度要求的情况下选取距离尽可能远的节点。此外，还需考虑目标运行速度。若目标速度很快，而选取距离又相对过小，则会造成目标的丢失。此时需要选取远距离的节点作为“太子簇首”，但该节点有可能超出当前簇首的无线通讯距离，因此需要多跳通讯[28]。

(2) 唤醒通告

簇首完成预测、节点分类、“太子簇首”选取的工作后，即开始唤醒预测方向上的睡眠节点，使其进入工作状态。具体地，发送唤醒消息AwakeMsg到通告候选区域。消息AwakeMsg封装了节点分类以及太子簇首选取的结果。睡眠节点收到AwakeMsg消息后，开始监听，且知道自身的节点类型以及是否是太子簇首。

(3) 新簇的形成

为了保证对移动目标的持续跟踪，在目标即将离开当前簇感知范围时要及时形成新簇，以便由新簇接续负责对目标的跟踪。新簇的形成主要有三种情形： ? 太子簇首“晋升”为正式簇首并形成新簇

如果预测方程足够准确，且能够找到符合要求的节点作为太子簇首。则该太子簇首收到触发时，开始定位：发送定位查询消息LocateMsg到周边节点。收到此定位查询信号的周边节点如果处于发现目标状态，即发送回复消息ReplyMsg到簇首，内含该节点对目标的量测。簇首即根据收到的ReplyMsg提供的信息和自身量测信息完成对目标的定位。若定位成功，太子簇首正式成为簇首。首先向上一簇首发送“承接”信号，表示新簇已经建立，目标没有丢失，上一簇首收到该信号，放弃簇首地位。然后该新簇首进入新的预测、节点分类、太子簇首选取、唤醒通告的新一轮循环。该过程称为太子簇首跟踪模式。若定位失败，则广播定位失败信号FailMsg。FailMsg消息通知其他节点当前太子簇首定位失败，开始进入“竞争”跟踪模式。

? “异常”节点成为簇首并形成新簇

定义2-11 异常：目标实际轨迹与预测轨迹发生较大误差，使得外节点受到目标触发，这种情况称为异常。受到触发的外节点称为异常节点。对应的定位称为异常定位。该跟踪模式称为异常跟踪模式。

- 23 -

哈尔滨工业大学工学硕士学位论文

根据节点分类，在预测足够准确且目标运动方向不发生大的偏转情况下，外节点不会受到目标触发。因此，若是普通内节点（非太子簇首）和边缘节点受到触发，则只是简单标志节点为发现目标状态，然后继续监听，并等待接受太子簇首的定位查询信号。若是外节点受到触发，则立即“篡位”成为异常节点。广播发送异常定位查询消息ExceptionMsg，其他节点收到ExceptionMsg后，回复ReplyMsg到该异常节点。原来的太子簇首收到ExceptionMsg后，放弃太子簇首地位，成为普通节点。异常节点根据收到的ReplyMsg及自身量测进行异常定位。若定位失败发送FailMsg进入竞争跟踪模式。

? 普通节点通过“竞争”成为簇首并形成新簇 上述两种情形下，在定位失败时开始进入竞争跟踪模式。所有节点通过“竞争”形成新的簇首。任何节点受到触发，即发送定位查询信号LocateMsg进行定位查询，定位成功则晋升为簇首[28]。

定理2-1 上述三种跟踪模式不会同时发生，即不会相互冲突。

证明：首先，太子簇首跟踪和竞争跟踪是互斥的。在太子簇首定位失败的情况下，才会采取“竞争”的方式生成下一个簇和相应的簇首，而该新簇若定位成功，又会采取“预测-节点分类-太子簇首选取-唤醒通告”一系列步骤“回归”到太子簇首跟踪模式。其次，竞争跟踪和异常跟踪是互斥的。同太子簇首跟踪，异常跟踪在定位失败的情况下才会开始竞争跟踪模式。最后，异常定位和太子簇首定位也是互斥的。显然，该“异常”本身就是相对于太子簇首的“正常”情况而言的，在收到异常定位查询消息ExceptionMsg后，原来的太子簇首节点立即放弃其“地位”，成为普通节点，所以不会与异常定位跟踪相冲突。因此，三种跟踪模式两两互斥，不会同时发生。 2.2.2.2 算法设计与分析

根据上述算法描述，给出该算法流程：

算法2-1. “Prince-Exception-Competition” algorithm running at each sensor 算法输入：触发/无线信号，算法输出：定位结果/无线信号 1: while(节点在工作){

2： event1 ：受到触发 3: switch(节点类型)

4: { case ?太子簇首?：

5: send(LocateMsg); //发送定位查询消息LocateMsg; 6: receive(ReplyMsg); //接收回复消息ReplyMsg 7: locate(); //定位

- 24 -

哈尔滨工业大学工学硕士学位论文

8: if(定位成功)

9: { 成为正式簇首；

10: 预测目标未来状态； 11: 节点分类；

12: 选取下一太子簇首；

13: send(AwakeMsg); //发送唤醒通告消息AwakeMsg 14: }else //定位失败

15: send(FailMsg); //发送定位失败消息FailMsg 16: break;

17: case ?外节点?：

18: send(ExceptionMsg); //发送异常定位查询消息 19: goto 6; //回到第6行 20: case ?边缘节点或普通内节点?：

21: detected = true; //detected标志是否发现目标22: }

23: event2：收到消息

24: switch(消息类别)

25: { case ?AwakeMsg?： //通告唤醒消息

26: 根据AwakeMsg消息初始化自身类型，开始监听。 27: break;

28: case ?LocateMsg?： //定位查询消息

29: if( detected == true) //如果该节点发现目标 30: send(ReplyMsg); //发送回复消息Reply 31: break;

32: case ?ExceptionMsg?： //异常定位查询消息

33: if( 该节点为太子簇首) 放弃太子簇首地位； 34: goto 29;

35: case ?FailMsg?： //定位失败消息 36: 开始竞争簇首； 37: } 38: }

接下来，通过与另外两种方法的对比分析，来说明本算法的低能耗特点。假设定位方法采用三角形质心定位，网络需满足三度覆盖，每个簇首须收到至

- 25 -

哈尔滨工业大学工学硕士学位论文

少两个回复才能够成功定位，否则定位失败。设当前网络满足三度覆盖的感知区域占总感知区域的比例为p。具体分析时，对于满足三度覆盖的区域，每个簇就确定为三度覆盖，即有3个节点；小于三度覆盖的区域，确定每个簇为两度覆盖，有2个节点。因此，平均每个跟踪簇内的节点数为：

n?p?(1?p)?2?2?p (2-13)

基于“竞争”的方法，每个节点在受到触发后，都会发送查询定位信号，收到回复满足定位条件即成簇首。且该算法假定在理想情况下，忽略密集的信号冲突。平均每生成一簇每个簇内节点需要发送2次信号。一次竞争信号，一次定位回复信号（簇首一次竞争信号，一次定位查询信号），簇首进行一次定位计算。平均每簇能量消耗为：

Ecluster?n?2?Etran?Ecompute?(2?p)?2?Etran?Ecompute (2-14)

式中n表示平均簇内节点个数，2表示每个节点发送2次信号。Ecompute表示簇首定位计算能耗。Etran表示一次信号发送的能耗。

如果采用文献[33]中的时间戳竞争机制，每个簇平均发送3+(n-1)次消息（簇首三次：DETECTION、SUPPRESSION和UNSUPPRESSION，其余n-1个节点各一次）。平均每簇能量消耗为：

Ecluster?[3?(n?1)]?Etran?Ecompute?(4?p)?Etran?Ecompute (2-15)

本文提出的“预定太子簇首-异常-竞争”机制在太子簇首跟踪和异常跟踪两种模式下，簇内每个节点1次信号发送，竞争模式下簇内每个节点2次信号发送。如果网络三度覆盖率为p，则太子簇首跟踪和异常跟踪模式比例为p，竞争模式比例为1-p，平均每簇能耗为：

Ecluster?p?nEtran?(1?p)?2nEtran?Ecompute?(4?p2)?Etran?Ecompute (2-16)

公式(2-14)、(2-15)、(2-16)分别描述了三种跟踪算法的能量消耗，都是网络三度覆盖率p的函数。从能量消耗的角度看，无线信号的发送能耗远远大于计算的能耗，因此，可以忽略能耗Ecompute。图2-13给出了三种算法能耗的直观比较。由图2-13可得出两个结论：首先，三度覆盖率为0时，即每个簇假设都只有两个节点的极端情况，三种算法能耗相同。但此时跟踪毫无意义，因为任何一个簇都会定位失败；三度覆盖率为1时，本文算法相对于时间戳竞争算法能量节省了40%，相对于竞争算法节省了50%。其次，前两种算法的每簇能耗随着覆盖率增加而增加，主要是由于每簇的节点数的增加引起的；而本文算法每

- 26 -

哈尔滨工业大学工学硕士学位论文

算法能耗对比图7平均每簇能耗(单位:Etran)654321000.10.20.30.40.50.60.70.80.9三度覆盖率1本文算法竞争时间戳竞争

图2-13 算法能耗对比图示

Fig. 2-13 Chart of different algorithm energy consuming

簇能耗随着覆盖率增加而下降，主要由于随着覆盖率的增加，太子簇首跟踪和异常跟踪模式比重相应增大，竞争跟踪模式比重下降而导致的。

2.2.3 仿真验证

本节通过仿真实验，验证本算法低能耗特征，同时验证在目标出现偏转的情况下本文的跟踪算法仍可以保持对目标的跟踪，不会出现目标丢失现象。

模拟场景为1000×1000m 区域，传感器节点感知半径为40m，无线通讯半径为140m。目标移动距离1000米。

(1) 能量消耗验证

由于三度覆盖率小于60%时，每个算法的定位失败率都很大，很容易发生目标丢失，而导致跟踪失败，对于跟踪算法的能耗分析没有太大意义。因此，实验只对三度覆盖率大于60%的情况进行了仿真分析。实验数据重复100次求平均值。

图2-14即为三种算法能耗对比仿真结果。可以看出，其与图2-13的单簇平均能耗对比图形状基本一致。不同的是，竞争算法和时间戳竞争算法的总能耗与本文算法的总能耗比例大于平均单簇的能耗比例，这是因为本算法的太子簇首机制可以根据具体精度要求来控制定位点密度，从而减少定位次数，即减少总的簇数。因此可以进一步降低总体能量消耗。这也是本算法的另一个优点。

- 27 -

哈尔滨工业大学工学硕士学位论文

能耗仿真结果120100累计能耗(单位:Etran)8060402000.60.70.8三度覆盖率0.91本文算法竞争时间戳竞争

图2-14 算法能耗仿真结果

Fig. 2-14 Simulation results for energy consuming of different algorithm

(2) 目标轨迹偏转情况下的跟踪

因为本算法利用目标运动预测进行目标跟踪，因此需要验证当目标实际运动方向和预测方向出现偏转时本算法的有效性。大量仿真实验结果表明，当目标轨迹发生偏转时，本算法能够及时捕获到目标并维持对其跟踪。图2-15是大量仿真实例中的两次仿真的跟踪过程。实线为目标实际轨迹，虚线为跟踪结果，圆点为定位点。可以看出，即便目标轨迹发生突然偏转，本算法的“异常”跟踪机制仍然能够保证迅速捕捉到目标，避免目标的丢失，维持对目标的继续跟踪。

a)b)定位点目标实际轨迹目标跟踪轨迹

图2-15 目标轨迹偏转情况下的跟踪 Fig. 2-15 Tracking results for target deviation

- 28 -

哈尔滨工业大学工学硕士学位论文

2.3 本章小结

本章首先针对声源信号高信噪比跟踪环境，通过基于对能量的Binary质心定位和方程定位方法的优缺点分析，提出一种距离-量测定位方法。在满足实际应用的条件下，既提高了Binary质心定位精度，又消除了方程法带来的无解和虚根问题。仿真实验表明，此算法有效、可行。

随后，基于目标动向预测的跟踪簇算法，从节省节点能耗和提高跟踪效率角度考虑，对簇首的产生算法进行了改进。通过对传感器节点进行分类，采取一种“太子簇首-异常-竞争”机制，预定节点为太子簇首，尽可能地减少了节点信号发送次数，达到了节省能量的目的。仿真实验表明，此算法简单、节能、有效，同时满足目标跟踪的完备性要求。

- 29 -

哈尔滨工业大学工学硕士学位论文

第3章 感知网多目标跟踪算法研究

3.1 多目标场景分析及跟踪框架

多目标跟踪的所有问题来源归根结底只有一个——多个目标情况下，目标声音信号混杂，处理能力有限的无线传感器节点无法区分其量测的来源以及各目标对该量测的“贡献”大小。而多目标信号的混杂与其相互间的距离大小有着直接的关系。本节即从目标间距离远近出发，给出本文多目标跟踪的的总体思路和跟踪框架。如图3-1。

多目标类精确跟踪target1target2target3单目标跟踪多目标集群跟踪距离很远目标稀疏目标密集

图3-1 多目标跟踪框架

Fig. 3-1 Framework of multi-target tracking

(1) 远距离单目标跟踪。图3-1左右两侧。当目标间距离很远时，对于基于声音感知的节点，其相互影响可以忽略。因此，在此情形下，可以采用多个单目标分别跟踪的方法，对每个目标进行单目标跟踪。

(2) 稀疏多目标类精确跟踪。图3-1虚线之间部分。目标的数目较少、相互影响较小时，采用类精确跟踪算法。所谓类精确跟踪，也就是近似精确的跟踪，是一种try-best方法，其尽可能地区分开各个目标，得到每个目标的精确轨迹。

(3) 密集多目标集群跟踪。图3-1中间部分。随着目标数增多、目标密集

- 30 -

哈尔滨工业大学工学硕士学位论文

程度增大，相互影响复杂，或者目标相互交错，运动线形特征不明显时，类精确跟踪也无法区分目标。此时，我们采取多目标集群跟踪的方法，不去区分每个目标，对每个目标进行考虑，而是将所有目标视为一个整体，对该整体进行跟踪定位。

该跟踪框架中，(1)即为单目标跟踪方法，第二章已详细描述，本章不再赘述；(2)类精确跟踪算法以第二章中的单目标“太子簇首-异常-竞争”算法为基础，对其进行修正，实现稀疏多目标的分离跟踪，本章第二部分3.2节将详细论述；(3)集群跟踪算法同样借鉴单目标跟踪的思想，实现了密集情况下的跟踪，将在第三部分3.3节中讨论。

3.2 稀疏多目标类精确跟踪算法

3.2.1 问题分析

随着目标的移动，当多个目标移动到相互距离较小，相互干扰时，处理能力有限的声音传感器节点无法区分其当前收到的感知信号来自于哪个目标，从而无法进行定位或者出现很大的定位误差。如图3-2是两个目标的情形分析。

Target 1S2S1S3S2S4S5a)b)Target 1S3S1S4Target 2Target 2Target 1S2S1S4S3Target 1S2S1S3Target 2c)Target 2d)

图3-2 多目标跟踪问题分析

Fig. 3-2 Problem analyses for multi-target tracking

- 31 -

哈尔滨工业大学工学硕士学位论文

S3、S4分别为当前时刻目标1和目标2的跟踪簇簇首。3-2(a)中节点S1同时受到目标1和2的触发。根据2.1中的距离-量测区间定位算法，S1须向S3发送回复消息，提供其到目标1的距离d1，以便簇首S3对目标1进行定位。同样，S1须向S4发送回复消息，提供其到目标2的距离信息d2，以便簇首S4对目标2进行定位。而实际中，S1的量测信号有多少来自于目标1的贡献，多少来自于目标2的贡献，S1根本无法得知。因此，簇首S3、S4将无法定位。同理，3-2(b)中，两个簇内普通节点处于跟踪门的相交区域。S1、S2都无法提供节点-目标距离。3-2(c)中两个太子簇首都在相交区域，对于2.1中的受到触发时发送定位查询信号的定位机制，太子簇首根本无法判断是哪个目标使其受到了触发。从而不能确定何时发送对应目标的定位查询信号。3-2(d)中，两个目标的跟踪门此刻完全重合。节点S3既是目标1的太子簇首，也是目标2的太子簇首。当节点受到触发时发送定位查询信号，不仅有前三种情况中的问题。即使能够正确进行定位过程，由于目标相距过近，会发生轨迹混淆。从而无从区分开目标与其对应轨迹。即两个目标若在交点相互交换路线，对于依靠声音信息定位的传感器节点来说是，无法觉察到。

根据上述分析，为了承接2.2中的“太子簇首-异常-竞争”的跟踪思想，使其能够在稀疏多目标的情况下进行定位跟踪，必须对其进行改进。

下面三小节即针对这些问题，从解决的角度阐述类精确跟踪算法思想。总体思路是：将信号混合的多目标跟踪分解为逻辑上信号独立的多个单目标跟踪，对每一个采用单目标跟踪算法，进行定位跟踪。逻辑上的独立是指一个节点可能维持两个目标的信息，即一个节点可能同时属于两个不同的动态簇，参与不同目标的跟踪，簇与簇逻辑上根据标志符区分。如图3-2(d)，节点S3同时是两个簇的簇首，这两个簇对应两个目标，由簇标志符区分。

3.2.2 时间戳机制

现实中，目标的运动是一个“时间-空间”过程。具体地，S1何时只处于目标1的跟踪门内，何时同时处于两个目标的跟踪门，何时又只处在目标2的跟踪门内等等问题都是应该考虑到的。因此，需考虑时间因素。每个节点维持全局统一时钟，并且增加两个本地变量time_in和time_out。如图3-3。

- 32 -

哈尔滨工业大学工学硕士学位论文

tt??tt??t??t'S3预测轨迹AS1S2S4A：当前定位点 S1：当前簇首 S4：预定“太子簇首”

图3-3 时间戳的引入 Fig. 3-3 Introduction of time stamp

三个圆为目标在三个时刻的跟踪门。S1为当前簇首，当前时刻为t。考虑节点S2，经过△t时间后，在t+△t时刻S2开始进入目标的跟踪门，即开始感知到目标，称此刻时间为time_in；再经过△t?时间后，在t+△t+△t?时刻，目标远离S2，S2离开目标的跟踪门，无法感知到目标，称此刻时间为time_out。节点S2即在[time_in,time_out]的时间段内处于目标的跟踪门内。

预测轨迹AS1dS2d’

图3-4 时间戳的初始化 Fig. 3-4 Initialization of time stamp

仍然以S2为例。见图3-4。S2收到唤醒消息，根据最后定位点和目标预测轨迹方程，通过几何关系可以求得其到目标当前跟踪门的距离d（跟踪门半径即为节点感知半径）。即要使S2受到触发，目标需要移动的预计距离。再根据目标速度v，可以求出目标移动距离d所需时间△t =d/v。考虑到通告唤醒信号的传输延迟t?，可以求出该节点的预测触发时间time_in = t_current + △t + t?。同理，也可以根据几何信息计算出弦长d?。而d?/v即为S2处于目标跟踪门内的时长△t?。从而可以得到目标离开S2感知范围的预计时间time_out = time_in + △t?。

每个节点在被唤醒时初始化time_in和time_out两个时间戳。时间戳机制需要节点全局统一时钟，具体可见有关文献[32]。

- 33 -

哈尔滨工业大学工学硕士学位论文

3.2.3 基于预测信息的信号分解

本小节基于预测信息讨论节点量测信号的分解。首先，对单目标跟踪中的节点数据结构进行改动。单目标跟踪中，每个节点维持单独的一些本地变量，如太子簇首、节点自身分类类型，而在多目标跟踪中，每个目标对应这样的一组变量。因此，每个节点应维持一个目标信息表，记录多个目标的预测信息，且加入上节的time_in和time_out信息：

目标ID 目标预测信息 time_in time_out 在某时间段，节点可能同时处于多个目标的跟踪门内，收到的量测信号是混杂的。如果预测足够准确，则意味着表中有多个目标的触发时间区间[time_in,time_out]i有交集存在。因此要从总量测信号中“分离”出各个目标“贡献”的那一部分。

公式(3-1)给出了基于声音的节点量测和目标距离的关系（同公式(2-1)）。公式(3-2)为多目标的情况。Z为节点收到的总量测信号大小，N为背景噪声。总共n个目标。Ci为目标i声源大小，pi为目标i的实际坐标，lsensor为节点的坐标。各个分母即为目标i到节点的距离的平方。节点的量测信号为各目标的“贡献”之合。忽略背景N（或者N已知），在已知Z和Ci的情况下，要求各个距离di。可以看出单目标的情况下，给定任何两个量，可以求出第三个。而多目标情况下，存在多个距离di。因此，需要对不同的目标i分解出对应的量测zi，然后应用公式(3-1)，求出距离di（通过查量测-距离区间表得到的）。分解方法就是根据各目标的预测轨迹和预测速度，结合时间信息，求出各目标在当前时刻的预测位置pi’，进而求的各目标到节点的预测距离di’，而目标i对z量测“贡献”

n11比例可以根据其2在所有?2中的比例而定。即以预测距离“贡献”比例

di'i?1dn'表示实际的“贡献”比例。

C1?N (3-1)

(p1?lsensor)2C1C2Cnz???... (3-2) (p1?lsensor)2(p2?lsensor)2(pn?lsensor)2z?设zi为目标i对节点量测的“贡献”大小，ki为“贡献”比例。则根据预测

距离，有公式(3-3)，(3-4)：

zi?(z?N)?ki (3-3)

- 34 -

哈尔滨工业大学工学硕士学位论文

1di'2 (3-4) ki??n1111?'2?...?'2?'2'2d1d2dnj?1dj从而求出各目标对应的zi，注意：这里的zi和di都是根据预测信息求得的。

下面描述预测距离di’的求法。

1di'2

图3-5 预测距离的计算

Fig. 3-5 Computing for predicted distance

如图3-5，圆为节点的感知范围，Rdetect为感知半径，圆心S为节点位置坐标。A点为目标进入节点感知区域的点，根据3.2.2描述可知，在预测理想的情况下，目标i到达A点的时间为time_ini，i的预测速度为vi。图中di’即为要计算的节点到目标i的预测距离。目标i进入节点的感知区域的时间为△t，当前时刻t = time_ini + △t。

图中，di’为三角形ABS的一条边。根据三角形余弦公式，有

22di'?Rdetect?(vi??t)?2Rdetect(vi??t)cos? (3-5)

夹角θ可根据对应的几何位置计算得到。

设时刻t，节点收到目标i的簇首定位查询消息。根据公式(3-5)，计算出每个目标的di?，然后由公式(3-4)求得ki，进而根据公式(3-3)，计算出zi。实际上，不必计算出每个目标的预测距离di’，只需计算当前时刻对节点产生触发作用的目标的预测距离。即需要计算的目标为以下集合：

T??j|t?[time_in,time_out]j,j?1,2,...n? (3-6)

由公式(3-3)、(3-4)、(3-6)，时刻t，目标i的对应量测zi计算为：

- 35 -

本文来源：https://www.bwwdw.com/article/jmf3.html