基于不可靠节点序列和面感知路由的目标跟踪*

曾国定，李超良，2，王国军*

(1.中南大学信息科学与工程学院，长沙 410083;2.湖南商学院计算机与电子工程系，长沙 410205)

随着传感器技术、微机电系统、无线通信和现代网络等技术的飞速发展，无线传感器网络(wireless sensor net works，WSN)应运而生。无线传感器网络是由大量的集成了传感、数据收集、处理和无线通信能力的小体积、低成本的传感器节点构成的无线自组织网络，其目的是协作地感知、采集和处理网络覆盖的地理区域内感知对象的信息，并传送给需要这些信息的用户［1］。由于无线传感器网络具有低成本、自组织、体积小和布撒灵活等特性，因此在军事侦察、环境信息检测、空间探索、农业生产、医疗健康监护、建筑与家居、工业生产控制、交通控制以及商业等领域有着广阔的应用前景［2－3］。

基于无线传感器网络的目标跟踪是无线传感器网络中应用研究的重点和热点之一。目标跟踪在军事和民用上都有着广泛的应用，这些应用小到娱乐，大到关系人的生命安全，如机器人足球、犯罪分子的跟踪、消防中的救援、生物学上的动物跟踪、军事上的作战等。目标跟踪需要传感器网络根据结点的侦测信息判断目标是否出现;如果目标出现，需要在一定时间内判断出目标的运动轨迹，这就要求传感器结点对侦测数据进行处理，根据不同的任务需求和有限资源选择合适的算法来对目标进行定位，并且通过网络中的多个结点协同工作、交换侦测信息共同确定目标的运动轨迹，并将跟踪结果发送给网络用户。目前国内外在这方面的研究非常多，已有的目标跟踪算法都存在各自的优点和不足，如何以最低的能量代价实现高质量的目标跟踪一直是各种算法追求的核心问题，然而这个目标却很难实现，因为若要提高目标跟踪精度，必然要融合更多节点的数据，这就会带来较高的能量开销;而若要节省能量，就只能在有限范围内进行通信和计算，那么跟踪精度就会受到影响。

文献［4］提出了一个比较新颖的想法，即基于节点序列的跟踪模式，根据节点监测到目标的时间长短形成节点序列，并把该节点序列同事先划分网络形成的节点序列表进行匹配，从而把求解跟踪路径问题转化为求图中最短路径问题，每条最短路径匹配一个节点序列。该方法有效减少了节点间传送数据量，从而大大降低了通信能量损耗，但方法中提取的节点序列是不可靠的，而且在节点数目达到一定数量后算法复杂度会显著提高。本文在文献［4］的基础上结合文献［5］做进一步改进，在面感知路由的基础上利用基于节点序列的定位算法来跟踪目标，既达到了减少网络中数据传输量的目的，同时也保证把算法的复杂度控制在一定范围内。

在无线传感器的目标跟踪中，最早提出的跟踪算法为Nai’ve［6］。该算法使感应区域内的所有传感器节点一直处于激活状态，保持对区域的监视。文献［7］提出的跟踪算法则是基于预测的思想，对目标下一可能位置进行线性预测，并且激活相应的信标节点，同时目标离开感应区则自动进入睡眠状态。文献［8］研究了层次型WSN目标跟踪的特点，首先加入了双层预测机制。文献［9］提出了DCTC算法，使用一个护卫树来跟踪目标，其中护卫树由一个根节点和其他的围绕在目标周围的节点组成。文献［10］提出了一种自适应的目标跟踪算法，通过设置一定的权值来控制节点的状态。文献［11］则提出了一种被动红外目标跟踪技术算法，采用红外线来定位和跟踪目标。文献［12］提出了基于监视节点和后备节点的目标跟踪协议，能对移动目标进行高效的跟踪和提高目标跟踪协议的容错性。

1 相关定义及网络模型

1.1 节点状态定义及转换

本文中传感器节点设定三个状态:活动状态、睡眠状态、苏醒状态。图1为节点状态转换图。当节点处于睡眠状态时，将关闭所有功能;当节点处于活动状态时，它可以侦测目标、接收和传输数据;当节点在苏醒状态下，节点将开启侦测、接收功能，可以接收其他节点发过来的请求和唤醒信息。网络中所有节点都周期性处于睡眠和苏醒状态。如果某个节点在苏醒状态下侦测到其周围有目标出现，它将自身状态转换为活跃同时向其周围节点发送唤醒信息，邻居节点收到唤醒信息后将也进入活动状态，参与跟踪;如果苏醒周期内没有侦测到目标，则在苏醒周期结束后自动进入睡眠状态。在活跃状态的节点如果发现目标丢失或者目标已经离开自己的侦测区域，节点将转入睡眠状态。

图1 节点状态转换图

1.2 网络模型

假定在欧几里德平面上存在一个由n个节点组成的集合V，网络模型给出如下假设:①被跟踪的对象，即目标，位于传感器网络中，可能是入侵者、运动中的野生动物、蔓延的火情或运动车辆等;②节点要时间同步，随机地分布在一个二维的平面上，且节点能量有限，具有全向的监测及通讯能力;③节点能发送广播信号，其他节点收到该广播信号后会发送确认信号;④传感器布撒以后，所有节点都能与其邻居节点通讯，在GPS定位系统和其直接邻居的合作下，节点能知道其所有的邻居节点;⑤传感器网络同构、能量有限，对于所有的节点来说，监测时的能量消耗是一样的;⑥目标如果被一个节点监测到，一段时间后又被另一个节点监测到，则认为是同一个目标。

1.3 面感知路由

为了避免节点序列划分时节点数目过多的问题，采用结合面感知路由的方法，即一种基于地理信息的平面路由策略，这是第一个不需要包副本，也不需要存储过去的路由信息的路由策略，同时还可以有效避免无线传感器网络中容易形成的“黑洞”和“关键路径”问题。面感知路由需要首先将网络平面化，传感器网络可以通过两个著名的分布式平面化协议Gabriel Graph(GG)和Relative Neighborhood Graph(RNG)来平面化。如果G=(V，E)表示一个图，u和v是属于集合V的传感器节点，如果这两个节点处于两者的通讯范围内，则在节点u和v之间有一条边uv，如果以uv为直径的圆内没有其他节点，则把边uv称为Gabriel edge，如果一个图G中只包含Gabriel edges，则该图为 Gabriel Graph(GG)，如图2(a)所示。反之，如图2(b)所示，以uv为直径的圆内有其他节点w，则边uv将在平面化的过程中被删除。在GG和RNG图中，我们可以得到一个连接的且具有较少边的平面子图G'=(V，E')。

图2 Gabriel Graph

图3为一个平面网络的例子，在平面网络图中，没有交叉边。如果一个图中任何两条边都没有交叉边，并且是无向的，就可以称这样的图为平面图。平面图由面构成，面是由多边构成的一个封闭的区间，如式(1)所示:

一般来说，在多维的空间中，GG连接空间中球的直径的两个端点，如式(2)所示:

图3 平面网络图

1.4 基于不可靠节点序列的网络划分

如图4(a)所示，对于一个给定的且知道地理位置节点1和节点2，整个区域将被两个节点连线的垂直平分线Div(1，2)划分为两个部分，位于Div(1，2)下的灰色区域中的点到节点1的距离都比到节点2的距离近，而位于Div(1，2)上的白色区域中的点到节点2的距离则更近。通过这样的划分，整个区域中的每一个点可以通过到节点1和2的距离的远近排列的节点序列来表示，如图中灰色区域就可以用节点序列(1，2)来表示。相应的整个区域被划分为两个面，分别对应两个节点序列f1:Sf1=(1，2)和f2:Sf2=(2，1)。图4(b)中列举了三个节点时的划分情况，可以看到每一个区域都对应一个唯一的由三个节点形成的节点序列。如果在一个区域内有n个节点，采用节点序列划分方法，该区域将被划分成2n个小区域，每一个区域都可以对应一个唯一的由这n个节点形成的节点序列。因此网络中节点数目增加时，这种划分方法所形成的节点序列的复杂度也会明显的增长，所以必须把划分区域的节点数量控制在一定范围内。

图4 网络划分

对于给定的节点序列S1和S2，定义节点序列距离SD(S1，S2)为S1和S2中置换的节点对数。如图2(b)所示，f1和f2两个区域对应的节点序列分别为Sf1=(1，2，3)和Sf2=(2，1，3)，在Sf1和Sf2中，有一对节点置换过来，即(1，2)⇒(2，1)，因此SD(Sf1，Sf2)=1。依此类推，Sf1和Sf3有两对节点置换，因此SD(Sf1，Sf3)=2。具体节点序列间距离的计算算法采用EKT［4］算法进行匹配，找出节点序列距离最小的匹配序列进行定位。

当目标进入侦测区域后，节点根据侦测到目标的时间长短形成一个侦测节点序列，随着目标的不断移动时，会形成一系列侦测节点序列，监测目标的节点把这些侦测信息发送到基站，基站把这些侦测节点序列与划分网络时形成的节点序列进行匹配，找到序列距离最小的匹配序列，即可把目标该时刻的位置定位于匹配序列所对应区域的几何中心。通过这一系列的匹配，这一系列侦测节点序列可以一一对应一个几何中心，这些几何中心就可以构成跟踪目标路径。

本文将不可靠节点序列和面感知路由结合在一起，不仅继承了节点序列划分的优点，同时有效控制节点序列划分中节点的数目。如图5所示，将图3中的平面网络图采用节点序列划分方法进行进一步划分。由于平面网络图中构成每一个面的节点数目是有限的，因此可以对平面网络图中的每一个面都分别采取节点序列划分的方法进行划分，由于构成每一个面的节点数目是有限的，因此划分时候节点序列长度都控制在了一定范围内，基于节点序列划分的算法复杂度也得到了有效控制。划分完成后，采用不规则多边形的质心算法将每一个区域的质心计算出来，形成一个全网络的节点序列表，与跟踪目标得到的节点序列进行匹配，达到定位的目的。

图5 平面网络划分图

2 目标跟踪

无线传感器网络部署成功后，网络中的节点周期性处于睡眠和苏醒状态，当某个节点ni在苏醒状态下侦测到有目标进入其侦测区域时，它把自身的状态转变为活跃状态，并发出唤醒包唤醒所侦测目标所在面Fi中其他节点参与跟踪。Fi中节点根据收到信号的时间长短形成一个节点序列，将形成的节点序列与划分网络时的节点序列匹配，根据匹配结果找到对应的多边形的质心作为目标该时刻所在位置。

发现和定位目标之后，还需要跟踪目标。考虑到无线传感器网络能量有限，算法采用基于预测的方案。根据当前侦测到的目标的运动方向和速度，对目标的下一步运动进行预判，我们需要提前唤醒它即将进入的下一个面中的节点，做好跟踪准备。图6显示了一次跟踪过程。假设在T时刻有目标在F1中。节点n1是所有能侦测到目标的节点中离目标最近并最先发现目标的节点，节点n1发现目标后会将目标所在面F1中的所有节点唤醒参与跟踪。如图6(a)所示，节点n1在侦测状态下发现目标进入跟踪区域，n1转变自身为活跃状态并发送唤醒信息给所在面F1中的其他节点n2、n3、n4，这些节点收到唤醒信息后也将转入活跃状态参与跟踪。而在T+1 时刻，目标有可能会进入 F2、F3、F4、F5中，距离目标最近的节点n1根据收集到的目标运动方向和速度对目标下一步运动进行预测，提前唤醒目标即将进入的面中的节点。如图3－7(b)所示，假设目标在T+1时刻进入的是F4，节点n1就给离自己最近的F4中节点n4发送消息，让其提前唤醒F4中的节点n5、n6来参与跟踪。目标离开F1后，F1中节点将其收到的侦测到目标所需时间发送给离基站最近节点，该节点收集到所有信息后，根据时间长短形成一个节点序列发送到基站，基站采用节点序列匹配算法EKT对目标进行定位。基于不可靠节点序列和面感知路由的跟踪Target tracking based on Node Sequences and Face Strategy(NSFS)算法如算法1所示。

图6 跟踪示意图

算法1:NSFS

图7则为一个采用该算法计算出来的相对完整的跟踪实例。根据图中所示的跟踪路径来看，虽然和目标的实际运动路径存在一定的误差，但还是具有一定的跟踪精度。

图7 跟踪移动目标

3 模拟分析

能量问题是目标跟踪中考虑得最多的问题。为了有效计算节点的能耗，下面将对本章中所采用的耗能模型进行介绍。节点的能量消耗主要为通信能量消耗，因此主要设计节点的通信能量模型，如公式

1所示，ET表示节点每发送一个包的数据所消耗的能量，这部分能量消耗主要包括发射电路损耗和功率放大损耗。

其中，ET-elec表示发射电路损耗的能量，d为两个节点间的距离。考虑到无线网络通信时信号随着距离增加而衰减，给节点的距离设置一个阈值d0，当传输距离小于阈值时，采用自由空间模型，当传输距离大于等于阈值时，采用多路径衰减模型。而节点每接收一个包的数据消耗能量为

ER-elec包含是传输电路和接收电路消耗的能量。

模拟实验中，传感器节点随机部署，建立了一个200 m×200 m的基本网络。所有节点的初始能量为50 J。依据目标运动模型，目标节点速度为2 m/s～20 m/s。时间建模为一个离散变量，所有的传感器节点时间同步。从每个传感器节点的能量消耗以及目标跟踪时整个时间的角度来研究算法的性能。设计多个实验评价不同参数对该协议的性能影响，这些参数包括目标速度、距离、方向和节点的数目。具体参数如表1所示。

模拟实验采取引入目标移动方向的概率模型来对目标的移动速度和方向的变动进行考虑。根据图8所示，NSFS协议和不可靠节点序列的在节点数目比较小时，平均能耗相差无几，但随着节点数目增加，NSFS协议明显比不可靠节点序列的平均能耗明显要低。由于不可靠节点序列算法在节点数目较多时算法复杂度太高，对运行实验的硬件要求很高，因此在实验中只节点数目最高只设置到了90个。如图9所示。在模拟实验中，将目标移动速度从5 m/s提高至20 m/s，可以看出，NSFS协议的能耗比DOT和基于泛洪的跟踪算法节点的平均能耗明显要少，主要是因为在NSFS算法中，由于网络中通信数据量大大减少，因此通信所消耗的能量也大大减少。为了能对算法中包开销的总数进行对比，通过计算路由维护，目标跟踪以及信息交换包，如请求信息和响应信息，得到包开销的数目。结果如图10所示。从实验结果来看，在目标速度比较小的时候，TF比DOT，甚至是NSFS协议的包开销都要少。但当目标的移动速度增大时，它的包开销就会急剧增大。在目标速度很大时，NSFS的性能比其他的都要好。当目标的速度增大时，与DOT协议相比，NSFS协议的包开销逐渐增大。在目标丢失率上，平均丢失率由总的丢失率估算得到，总的丢失率产生在实验的不同阶段，基于目标跟踪节点的感应半径，定义为节点没有探测到移动目标的百分率。如图11所示，相比移动目标的移动方式是随机的DOT协议，NSFS算法具有较小的丢失率，因为NSFS算法中传感器节点是在较小的感应范围内相互协作探测目标。

表1 模拟参数表

图8 不同节点数目时的平均能量消耗

图9 节点平均能量消耗

图10 不同目标速度下的包开销

图11 目标丢失率

4 结束语

本文提出一种基于不可靠节点序列和面感知路由的目标跟踪算法，该算法同其他跟踪算法相比，由于减少了网络中数据的传输量，因此在能量节约方面具有较大优势。但是牺牲了一定的跟踪精度，未来还需要在这方面提出改进，同时可以考虑把该算法扩展至三维空间。

［1］韩红彦，张西红，张晓.无线传感器网络研究［J］.科学技术与工程，2007，7(8):1701－1706.

［2］马祖长，孙怡宁，梅涛，无限传感器网络综述［J］.通信学报，2004，25(4):114－123.

［3］孙利民，李建中.无线传感器网络［M］.北京:清华大学出版社.

［4］Ziguo Zhong，Ting Zhu，Dan Wang，et al.Tracking with Unreliable Node Sequences［C］//IEEE INFOCOM 2009:1215－1223.

［5］H-W Tsai，C-P Chu，T-S Chen.Mobile Object Tracking in Wireless Sensor Networks［J］.Computer Communications(Elsevier)，2007，30:1811－1825.

［6］D Mc Erlean，S Narayanan.Distributed Detection and Tracking in Sensor Networks［C］//Signals，Systems and Computers，2002.Conference Record of the Thirty-Sixth Asilomar Conference on，2002，2:1174－1178.

［7］He Tian，Huang Chengdu，Blum BM.Range-Free Localization Schemes in Large Scale Sensor Networks［C］//MobiCom，2003:81－95.

［8］黄仑，徐昌庆.无线传感器网络目标跟踪机制的研究与改进［J］.计算机工程与应用，2006，42(16):140－142，149.

［9］Wensheng Zhang，Guohong Cao，DCTC:Dynamic Convey Tree-Based Collaboration for Target Tracking in Sensor Networks［J］.IEEE Transactions on Wireless Communications，2004，11(5):1689－1701.

［10］彭勇，王国军，邢萧飞.无线传感器网络中一种自适应目标跟踪协议［J］.传感技术学报，2009，22(3):427－432.

［11］王森，陈颖文，徐明，等.无线传感器网络被动红外目标跟踪技术研究［J］.传感技术学报，2008，21(11):1929－1934.

［12］Md.Zakirul Alam Bhuiyan，Guojun Wang，Jie Wu.Target Tracking with Monitor and Backup Sensors in Wireless Sensor Networks［C］//ICCCN，2009，8:1－6.