无线传感器网络基于2阶段聚合的目标跟踪算法

任倩倩 刘红阳 刘 勇 李金宝 王 楠

(黑龙江大学计算机科学技术学院 哈尔滨 150080) (黑龙江省数据库与并行计算重点实验室(黑龙江大学) 哈尔滨 150080)

无线传感器网络基于2阶段聚合的目标跟踪算法

任倩倩 刘红阳 刘 勇 李金宝 王 楠

(黑龙江大学计算机科学技术学院 哈尔滨 150080) (黑龙江省数据库与并行计算重点实验室(黑龙江大学) 哈尔滨 150080)

(renqianqian@hlju.edu.cn)

研究无线传感器网络中能量有效的移动目标跟踪问题.1)定义了一个基于网格的网络模型，该模型使处于网格顶点附近的节点工作、其他节点睡眠以节省能量,同时保证跟踪质量.2)分析了目标出现位置与网格单元的关系，针对每种位置关系给出了一个通用的定位算法.在此基础上，设计了一个基于2阶段聚合的目标定位算法，对单个网格内定位结果进行优化.3)提出了一个基于顺逆时针机制的最短路径选择算法传输目标定位的结果，保证最小化参与传输的节点数目.4)通过大量实验验证了所提出算法在能源节省和跟踪质量方面的有效性.

移动目标跟踪；聚合；网格；定位；时钟规则

无线传感器网络在人们日常生活中扮演着不可或缺的角色，它广泛地应用于战场监测、生态环境监测、灾难预测和智能交通等诸多领域[1-2].在传感器网络的诸多应用中，移动目标跟踪都是一项基本功能.在监测战场上敌军车辆运动轨迹、野生动物生活习性、森林火灾的蔓延程度，以及高速公路上车辆的运行状态等应用中都需要用到目标跟踪功能[3-4].然而，传感器网络能量供应有限的特性使得基于传感器网络的目标跟踪研究面临着许多挑战.基于移动目标跟踪的应用往往需要网络持续工作，为了尽量延长传感器网络的工作时间，节省并平衡节点能耗，最大化网络生命周期是一个关键问题.许多文献介绍了一系列能源有效的方法来减少传感器网络的能源消耗[5-7].在这些方法中，使节点轮流工作是一个有效的方法.其核心思想是在给定的时间内，使小部分节点工作而其他节点睡眠.

在目标跟踪的过程中，保证目标周围的节点工作而其他节点睡眠是一种直观有效的节能方式，然而目标运动轨迹的随意性使得很难事先获得目标位置信息从而确定工作节点.本文在目标跟踪的过程中引入了节点睡眠调度机制，所提方法不需要通过预测目标位置确定工作节点，而是构建了一个基于网格的网络模型.该模型使处于网格顶点的节点工作、其他的节点进入睡眠状态.为了平衡节点能耗，可以周期性重新构建网格，使网络内节点轮流成为网格顶点.网格的尺寸设计保证目标在网格的任意位置都有足够节点为目标定位.考虑到目标可能出现在单个网格单元内或2个网格单元公共边上，本文系统分析了目标与网格单元的位置情况，给出了通用的定位算法.针对目标处于网格单元公共边上定位的情况，本文对算法进行优化，设计了一个基于2阶段聚合的定位方法，以缓解每个网格单元内的部分定位结果误差对整体定位结果的影响.为了及时有效地传输定位结果，本文设计了一个基于顺逆时针的最短路径选择机制，该方法可以与目标跟踪过程相结合，不需要较多的额外工作量，同时最小化参与路由的节点数目.

本文的主要贡献有4点：1)构建了一个基于网格的网络模型，在目标跟踪的过程中引入睡眠调度机制；2)设计了一个基于2阶段聚合的移动目标跟踪算法，分析目标在网格内出现的各种情况，给出了通用的目标定位算法，并采用聚合方法对定位结果进行优化；3)设计了一个基于顺逆时针的转发节点选择策略，在网格中使用最短路径选择机制传输目标定位的结果到Sink；4)搭建了一个大规模的实验室环境模拟平台，验证了所提出算法的有效性，并与其他优秀目标跟踪算法进行比较.

1 相关工作

在传感器网络中，移动目标跟踪技术已经有了广泛的研究[7-18].下面将简单地介绍与本文最相关的工作.

文献[7]定义了一个基于覆盖率模型的“覆盖范围”定义，在此基础上该文给出2个划分传感器节点的方法，使得划分后的节点满足覆盖集条件，并且采用覆盖集中的节点轮流工作方式以达到最大化系统寿命的目的.文献[12]提出了一个2层的数据传输模型，此模型适用于大规模无线传感器网络和多个移动Sink的场景中.随着目标的每次运动，模型将建立1个新的网格实施目标跟踪和信息传输.该机制能够平衡网络中能量负载，然而维护网络拓扑需要耗费一定的能量.文献[13]提出了一个基于2层网格的移动目标定位方法.该方法简单又节省能量，然而该文并没有给出目标监测数据的收集方法和数据传输方法.

MCTA给出了一个最小轮廓跟踪算法，在最小化工作节点数量的同时，保证目标跟踪的质量[14].文献[15]在目标跟踪过程中使用节点选择方法，选择最有利的节点参与跟踪.文献[16]设计了一个协作信号处理机制跟踪目标，其主要思想是使用被监测区域内4个网格中被激活的节点监测目标，并且这些节点发送传感数据给管理节点，管理节点负责定位目标并且预测目标未来的位置.

文献[17]提出了一个基于预测的能量有效的目标跟踪算法，首先预测目标的轨迹以及目标即将出现的位置，然后激活网络中的这部分节点用于目标跟踪，同时保持其他节点睡眠以节省节点的能量.文献[18]提出了一个适用于分布式传感器网络定位的融合机制.该机制首先将网络分为若干个小的子网，每个子网尽可能地在自己区域内定位目标.该机制不参考全局坐标基准，因此计算复杂度较低.

上述方法都考虑了在移动目标跟踪的过程中节省能量，使节点轮流工作是一个非常有效的节能方法.然而目标轨迹具有一定的随机性，因此很难提前预测出目标即将出现的区域，从而确定参与工作节点.本文采用基于网格的睡眠调度机制，该机制在网络中构建网格模型，使处于网格顶点附近的节点工作而其他的节点睡眠来节省能量，从而避免预测目标轨迹.网格的设计保证目标在任意位置都能够有工作的节点监测到，并且工作的节点数目尽量小.

2 系统模型

2.1 网络模型

Fig. 1 An example of network model图1 网络模型的一个示例

2.2 感知模型

当跟踪目标出现在传感器网络的监测区域内，位于目标周围的传感器节点会产生感知数据.用di表示传感器节点i与跟踪目标的距离(1≤i≤N,N为网络内节点个数).用“1”表示节点i作出“监测到跟踪目标”的决策，而“0”表示节点i作出“未监测到跟踪目标”的决策.由于网络内的节点独立作出决策，因此传感器节点i的决策si可以表示为

(1)

作出决策为“1”的节点进一步向其管理节点传送信息，第3节将详细说明.

3 基于2阶段聚合的移动目标跟踪算法

本文将给出目标跟踪算法的详细设计.根据目标在网格内出现的位置，分3种情况进行讨论，即目标出现在1个网格单元内部、目标出现在2个网格单元的公共边上和目标出现在网格单元顶角附近.

定义1. 跟踪管理节点.即参与本次移动目标定位的管理节点.

3.1 预备知识

当目标进入网络的时候，它可能出现在网络的任意位置.即目标可能出现在一个网格单元内部，或者出现在相邻2个网格单元的公共边上(目标位于4个网格单元的公共边的情况也包含在内)，如图2所示.目标出现在网络的不同位置，使得监测到目标的节点的数目不同.在下面篇幅中，我们将讨论目标位置和监测到目标节点数目的关系.

Fig. 2 Target location examples in different cases图2 不同情况下的目标位置示例

定理1. 如果目标只被4个边界节点监测到，那么这些边界节点是同一个网格单元的4个边界点.

证明. 由于目标只能位于网格单元内，或者位于2个网格单元的公共边上，我们将分别针对每种情形给出此定理的证明.

情形1. 目标位于1个网格单元内部，如图2(a)所示.根据感知范围的定义，目标所在网格单元内的4个边界节点一定能够监测到目标.

情形2. 目标不位于1个网格单元内部，则目标位于2个网格单元的公共边上，如图2(b)(c)所示.目标所在公共边上的2个节点一定可以监测到目标.1条公共边连接2个网格单元，根据节点感知范围定义可知这2个网格单元内的剩余4个边界节点也可以监测到目标.此时监测到目标的节点数目为6，这与假设目标只被4个边界节点监测到矛盾.所以情形2不满足定理条件.

证毕.

定理2. 如果监测到目标的节点数目超过4个，那么这些节点一定来自于多个(2个或2个以上)网格单元.

证明. 因为1个网格单元只有4个边界节点，此定理显然正确.

证毕.

定理3. 目标位于2个网格单元公共边上，并且距离此边上任意节点A的距离满足如下条件：

(2)

则目标能够被6个节点监测到.

证明. 使用反证法来证明.

假设满足式(2)的条件，那么此公共边连接的2个网格内所有边界节点(如图2(b)所示总计6个节点)都能够监测到目标.假定另外有一个最近的节点C能够监测到目标，则节点C和跟踪目标的距离可定义为

distance(C,target)=distance(C,A)+

(3)

根据假设有：

(4)

推导得到：

(5)

证毕.

定理4. 目标位于2个网格单元公共边上，并且距离此边上任意节点A的距离满足如下条件：

(6)

或者

(7)

则监测到目标的节点数量是7.

证明. 首先考虑式(6)的情况.此时假定距离目标较近的节点C能够监测到目标(如图2(c))，那么节点C到目标的距离满足：

distance(C,target)≤distance(C,A)+

(8)

进一步假设距离目标较远的节点D和节点E也能够监测到目标(如图2(c))，它们到目标的距离分别为

(9)

(10)

式(7)的情况与式(6)类似，除了目标所在公共边连接的2个网格上6个节点能够监测到目标外，只有节点F可以监测到目标，因此能够监测到目标的节点数量是7.

证毕.

3.2 移动目标监测和定位

本节将给出目标监测算法，分3种情况讨论目标的定位问题，并给出定位算法.

定义2. 代理节点.距离Sink最近的管理节点称为代理节点.代理节点可以直接与Sink通信.

情况1. 目标在1个网格单元内.

根据定理1，网格单元的4个边界节点能够监测到目标，如图2(a)所示.这些节点监测到目标后作出决策“1”，并将决策传输给它们的管理节点.管理节点根据决策进行目标定位(3.3节算法1)，并传输定位结果给代理节点，代理节点最终发送数据给Sink.

情况2. 目标在网格公共边上.

根据定理2～4，如果目标出现在网格的公共边上，那么多个网格的边界节点将监测到目标，如图2(b)和图2(c)所示.这些节点作出决策“1”并将自己的决策传输给所在网格的管理节点.每个管理节点独立地定位目标.所有管理节点向距离代理节点最近的管理节点发送定位结果，该管理节点聚合部分定位结果得到最终定位结果，并经过代理节点发送定位结果给Sink.

情况3. 目标在网格单元的顶角附近.

如图2(d)所示，目标处于阴影扇形区域内(近似于扇形)，目标被它所在网格内的4个边界节点监测到，同时目标被邻居网格内的最近的一个节点监测到.定位过程与情况2相同.

3.3 移动目标定位

一旦接收到了感知数据，管理节点执行定位算法进行目标定位.现存的许多定位算法都适用于本文的跟踪过程中.本文实验以简单灵活的质心算法为例[19]，实验结果表明质心算法在本文所提出网络模型上具有很好的定位效果，而且无额外硬件需求.

定义3. 聚合管理节点.执行聚合操作的跟踪管理节点为聚合管理节点.通常，选择距离代理节点较近的跟踪管理节点作为聚合管理节点.

(11)

算法1. 基于2阶段聚合的移动目标跟踪算法.

输入：节点的决策、时刻t；

输出：时刻t目标位置.

步骤1. 每个监测到目标的节点传输自己决策给所在网格的管理节点；

步骤2. 收到决策的管理节点独立地计算目标的位置，得到部分定位结果；

步骤3. 所有计算得到部分定位结果的管理节点广播自己的结果给邻居管理节点；

步骤4. 判断是否接收到邻居管理节点发送给自己的定位结果；

IF没有接收到

传输定位结果给Sink；

ELSE

找出聚合管理节点k，并且把自己的部分定位结果发给k；

END IF

步骤5. 节点k对收到的结果执行加权定位，计

3.4 最短路径选择算法

当管理节点获得目标的最终位置信息后，将通过路由发送位置信息给代理节点，最终到达Sink.本节将提出一个基于顺逆时针的最短路径选择算法.算法的核心思想是向代理节点发送数据的管理节点使用时针机制选择下一跳转发节点，重复这一个过程直到数据到达代理节点.

例如图3中代理节点在当前管理节点的右下方，管理节点选择右圆为参考圆，阴影节点为转发节点.

Fig. 3 Clockwise scheme diagram图3 顺时针机制示意图

Fig. 4 Anticlockwise scheme diagram图4 逆时针机制示意图

定义5. 逆时针机制.管理节点i按照逆时针方向构造3个直径为d的圆，分别称作上圆、左圆和下圆；i选择圆心距离代理节点最近的圆为参考圆.沿着参考圆边缘逆时针方向出发遇到的第1个邻居节点即为转发节点.该机制称为逆时针机制.

当代理节点位于管理节点右边的时候，管理节点采用顺时针机制选择下一跳传输节点.当代理节点位于管理节点左边的时候，管理节点采用逆时针机制选择下一跳传输节点.

步骤1. 当前需要传输数据的管理节点i首先检查自己或者自己的邻居管理节点是否是代理节点.如果是，算法跳到步骤4.

步骤2.i检查代理节点与自己的位置关系.如果代理节点在自己的左侧，i采用逆时针机制选择转发节点.如果代理节点在自己的右侧，i采用顺时针机制选择转发节点；否则，i与代理节点在同一列，直接选择同列距离代理节点更近的节点为转发节点.

Fig. 5 The distribution of energy consumption图5 总能量消耗示意图

步骤3.i向转发节点j传输数据.节点j收到数据后，执行步骤1继续选择转发节点.

步骤4. 如果管理节点i是代理节点，它直接传输数据给Sink；否则管理节点i的邻居是代理节点，i传输数据给邻居代理节点k，k再传输数据给Sink.

最短路径选择算法的伪代码如算法2所示.

算法2. 最短路径选择算法.

输入：当前管理节点位置、代理节点位置.

步骤1. 判断当前节点或者其邻居是否代理节点：

IF是

转入步骤2;

ELSE

② 发送数据给转发节点;

③ 转发节点接收到数据后转入步骤1;

END IF

步骤2. 传输数据给Sink或代理节点.

4 节点能量消耗分析

本节将分析网络中节点的能量消耗.用E表示节点的初始总能量，在目标跟踪的过程中发送、接收数据包以及其他部分的能量消耗(例如初始化能耗)分别表示为Esend，Ercv，Eoth.节点总能量消耗如式(12)所示：

(12)

每个传感器节点将1 b的信息传输100 m消耗的能量等同于传感器节点执行3 000条CPU指令的能量消耗[19-20].考虑到简单信息处理对整体能量消耗影响不大，我们在分析节点整体能耗时主要考虑通信的能耗而忽略掉信息处理的能量消耗.

式(12)中，Esend是移动目标跟踪的过程中发送数据包的总能量消耗.如式(13)所示，Esend主要包括以下3个方面的能量消耗：1)每个监测到目标的边界节点发送一个数据包给它们的管理节点的能量消耗Esre；2)这些管理节点向聚合管理节点发送定位结果，并且为了获得更好的定位精度聚合管理节点聚合这些结果的能量消耗Esagg；3)聚合节点采用本文提出的最短路径选择算法传输最终的定位结果给Sink的能量消耗:

(13)

同理，接收数据包的能量消耗Ercv定义与Esend类似，如式(14)所示.

(14)

式(12)中最后一项Eoth是初始化的能量消耗，它由3个部分组成：1)Sink选择代理节点的能量消耗；2)选择管理节点的能量消耗；3)构造网格的能量消耗.假定每个节点接收或发送1个数据包都消耗1个单位的能量.

在本文后面的实验中，我们比较了不同网格大小和目标在不同运动速度下目标定位和传输的能量消耗.图5显示了连续执行2次移动目标跟踪时，节点分别执行定位、路由和其他操作所消耗能量占总能耗的百分比.

从图5可以看出，目标定位和目标沿着最短路径传输的能耗非常相近，它们总计占总能耗的65%;其余35%的能量消耗在其他部分.这说明本文的定位算法和最短路径传输算法具有很高的能量利用率，特别适用于网络需要长期工作的应用.

Fig. 7 The influence of grid size on tracking performance with velocity 30 cells图7 目标移动速度为30cells时网格尺寸对跟踪性能的影响

5 实验和评估

为了验证算法，本文在Win7系统上使用VC++ 6.0搭建了一个模拟平台.实验评估了网格大小和目标运行的速度等参数对算法性能的影响，并就跟踪准确性和能量消耗情况与文献[21]提出的算法(以下记为dis算法)进行对比.该算法是一个高效的能源有效移动目标定位算法.本实验中，400个节点均匀部署在一个1300×600单元的区域.图6显示了节点部署的一种情况.

Fig. 6 Plan view of simulation laboratory with node deployment图6 部署节点下的模拟实验室平面图

5.1 系统参数对跟踪准确性的影响

本组实验分析了目标移动速度和网格大小对目标跟踪性能的影响.我们分别设置目标运动速度是30cells和50cells.图7和图8显示了网格的大小在45～80个单位区间内变化时本文定位算法和dis定位算法的性能变化情况.所有实验结果示意图中横纵坐标分别代表目标在二维空间的位置坐标，其中横轴代表x轴，纵轴代表y轴.

Fig. 8 The influence of grid size on tracking performance with velocity 50 cells图8 目标移动速度为50cells时网格尺寸对跟踪性能的影响

从图7可以看出，在绝大多数情况下本文算法的定位误差要小于dis算法.本文算法在目标速度为30cells、网格大小在45个单位的运动轨迹定位时可以实现0误差，并且本文算法的最小定位误差始终不超过3个单位.

从图7和图8也可以看出，随着网格的增大，本文定位算法的精度略微降低.然而网格大小为50个单位时的定位精度要比其他网格大小(包括网格大小是45)的定位精度更好，这主要是由节点的布置不同以及聚合步骤所决定.

从图7和图8中我们还可以发现目标做随机游走运动时(图7和图8中的折线部分)，本文算法更优于dis算法，尤其dis算法在左侧折线部分定位误差很大.这是由于dis算法选取监测到目标的传感器节点感知范围相交弧的中点作为目标的估算位置，当目标在网络边缘时该方法存在较大弊端.

5.2 算法能量消耗对比

图9比较了使用本文提出的最短路径算法传输数据的能量消耗和其他基于网格的路由算法能量消耗[13]，该方法是目前最好的直接应用于目标跟踪过程而不需要过多额外工作量的路由方法.从图9可以看出本文的最短路径算法比其他网格路由算法节省了五分之一甚至更多的能量.从图9可以看出，随着网格增大,本文提出算法能量消耗减少.这是因为较大的网格所配置管理节点数目更少，传输路径中的传输跳数也越少.

Fig. 9 Transmission energy consumption图9 传输能量消耗图

图10比较了本文所提出定位算法(简称为our localization)和dis算法定位目标的能量消耗.从图10可以看出，本文所提出算法在能耗节约上具有更好的效果，尤其目标移动速度较快的情况比目标移动速度较慢时消耗的能量更少.在采样频率固定的情况下，固定时间间隔内目标移动速度快导致被定位的次数变少，从而定位消耗的能量也相应地减少.

Fig. 10 Localization energy consumption图10 定位的能量消耗

6 结束语

本文设计并实现了一个能量有效的移动目标跟踪算法.1)在移动目标跟踪的过程中引入网格模型，使处于网格顶点附近的节点工作、其他节点睡眠以此节省能量.2)分析了目标在网格内出现的各种位置关系，针对每种位置关系给出适用的定位算法.为了优化目标定位结果，本文进一步给出了一个基于2阶段聚合的移动目标跟踪算法，以缓解单个网格内定位误差对整体定位结果的影响.3)提出了一个基于顺逆时针机制的最短路径选择算法传输目标跟踪结果，该算法可以很好地融入到本文所提出目标跟踪过程，不必增加过多的额外能耗，同时保证参与路由的节点数目最少.4)进行了大量的实验验证了系统参数包括网格大小、目标运动速度对跟踪性能的影响.

[1]Li Zhanqing, Nadon S, Cihlar J. Satellite detection of canadian boreal forest fires: Development and application of the algorithm[J]. International Journal of Remote Sensing, 2000, 21(16): 3057-3069

[2]Gupta V, Kim J, Pandya A, et al. Nano-CF: A coordination framework for macro-programming in wireless sensor networks[C]Proc of the 8th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks. Piscataway, NJ: IEEE, 2011: 467-475

[3]Duarte M, Hu Yuhen. Vehicle classification in distributed sensor network[J]. Journal of Parallel & Distributed Computing, 2004, 64(7): 826-838

[4]Spenza D, Magno M, Basagni S, et al. Beyond duty cycling: Wake-up radio with selective awakenings for long-lived wireless sensing systems[C]Proc of IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2015: 522-530

[5]Aslam M, Shah T, Javaid N, et al. CEEC: Centralized energy efficient clustering a new routing protocol for WSNs[C]Proc of the 9th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks. Piscataway, NJ: IEEE, 2012: 103-105

[6]Peng Yang, Li Zi, Qiao Daji, et al. I2C: A holistic approach to prolong the sensor network lifetime[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2013: 2670-2678

[7]Liu Xuefeng, Cao Jiannong, Tang Shaojie, et al. A generalized coverage-preserving scheduling in WSNs: A case study in structural health monitoring[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2014: 718-726

[8]Zheng Zhongming, Liu Anfeng, Cai Lin et al. ERCD: An energy-efficient clone detection protocol in WSNs[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2013: 2436-2444

[9]Liu Xiang, Luo Jun, Vasilakos A. Compressed data aggregation for energy efficient wireless sensor networks[C]Proc of the 8th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks.Piscataway, NJ: IEEE, 2011: 46-54

[10]Luo Yu, Pu Li, Zheng Peng, et al. Effective relay selection for underwater cooperative acoustic networks[C]Proc of the 10th Int Conf on Mobile Ad-Hoc and Sensor Systems. Piscataway, NJ: IEEE, 2013: 104-112

[11]Wang Yi, Krishnamachari B, Annavaram M. Semi-Markov state estimation and policy optimization for energy efficient mobile sensing[C]Proc of the 9th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks. Piscataway, NJ: IEEE, 2012: 533-541

[12]Ye Fan, Luo Haiyun, Cheng Jerry, et al. A two-tier data dissemination model for large-scale wireless sensor networks[C]Proc of the 8th Annual Int Conf on Mobile Computing and Networking. New York: ACM, 2002: 148-159

[13]Tang Guoming, Xie Yi, Tang Daquan. An adaptive grid division algorithm for target location in wireless sensor networks[C]Proc of Conf on Anthology. Piscataway, NJ: IEEE, 2013: 1-6

[14]Jeong J, Hwang T, He Tian, et al. MCTA: Target tracking algorithm based on minimal contour in wireless sensor networks[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2007: 2371-2375

[15]Arienzo L, Longo M.Energy-efficient collaborative tracking in wireless sensor networks[J]. International Journal of Sensor Networks, 2011, 9(3): 124-138

[16]Li Dan, Wong K, Hu Yuhen, et al. Detection, classification and tracking of targets in distributed sensor networks[J]. IEEE Signal Processing Magazine, 2002, 19(2): 17-29

[17]Deldar F, Yaghmaee M. Energy efficient prediction-based clustering algorithm for target tracking in wireless sensor networks[C]Proc of Conf on Intelligent Networking and Collaborative Systems. Piscataway, NJ: IEEE, 2010: 315-318

[18]Motevallian S, Xia Lu, Anderson B. A new splitting-merging paradigm for distributed localization in wireless sensor networks[C]Proc of Int Conf on Communication. Piscataway, NJ: IEEE, 2013: 1454-1458

[19]Kim W, Kirill M, Jeung Y. On tracking objects with binary proximity sensors[C]Proc of Conf on Information Processing in Sensor Networks. Piscataway, NJ: IEEE, 2005: 301-308

[20]Iyer R, Kleinrock L.QoS control for sensor networks[C]Proc of Int Conf on Communications. Piscataway, NJ: IEEE, 2003: 517-521

[21]Wang Zijian, Bulut E, Szymanski B. Distributed energy-efficient target tracking with binary sensor networks[J]. ACM Trans on Sensor Networks, 2010, 6(4): 2084-2095

Ren Qianqian, born in 1980. Associate professor at Heilongjiang University. Member of CCF. Her main research interests include database and wireless sensor networks.

Liu Hongyang, born in 1991. Master from Heilongjiang University. Her main research interests include wireless sensor networks and target tracking.

Liu Yong, born in 1975. Associate professor at Heilongjiang University. Member of CCF. His main research interests include data mining and social network.

Li Jinbao, born in 1969. Professor and PhD supervisor at Heilongjiang University. Senior member of CCF. His main research interests include sensor networks, mobile social network and big data.

Wang Nan, born in 1980. PhD candidate at Heilongjiang University. Her main research interests include sensor networks and social network.

A Two-Tier Aggregation Based Tracking Algorithm in Wireless Sensor Networks

Ren Qianqian，Liu Hongyang，Liu Yong，Li Jinbao，and Wang Nan

(SchoolofComputerScienceandTechnology,HeilongjiangUniversity,Harbin150080) (KeyLaboratoryofDatabaseandParallelComputingofHeilongjiangProvince,Harbin150080)

Mobile target tracking is an important issue in wireless sensor networks. This paper discusses the energy efficient tracking problem in networks. We first construct a grid based network model, which makes nodes near the vertexes of grid cells work and others sleep to save energy with tracking quality guarantee. We analyze the relationship between target appearance position and grid cells in the network, classify the three cases of target detection and give a general target localization method applied to each case. Then, We propose a two-tier aggregation based target tracking algorithm. The algorithm implements aggregation on partial localization results to obtain the optimized final localization result. After that, a clockwiseanticlockwise scheme based shortest path selection algorithm is presented to transmit localization result to sink with minimum involved sensor nodes. Finally, a comprehensive set of simulations are presented and the experimental results show that the proposed target tracking algorithm can yield excellent performance in terms of tracking accuracy and energy saving in wireless sensor networks.

mobile target tracking; aggregation; grid; localization; clock scheme

2016-08-22；

2016-12-29

国家自然科学基金项目(61300225,61370222,81273649)；黑龙江省自然科学基金项目(F2017022,F201430,F201434)；黑龙江省高校青年创新人才基金项目(UNPYSCT-2015017)；哈尔滨市科技创新人才专项基金项目(2016RAQXJ028) This work was supported by the National Natural Science Foundation of China(61300225, 61370222, 81273649), the Natural Science Foundation of Heilongjiang Province (F2017022, F201430, F201434), the Innovation Talents Foundation of Heilongjiang Educational Committee (UNPYSCT-2015017), and the Science Innovation Talents Foundation of Harbin (2016RAQXJ028).

刘勇(acliuyong@sina.com)

TP391