基于动态分簇的移动目标追踪方法

包 威，毛莺池，王龙宝，陈小丽

(河海大学 计算机与信息学院，南京 211100)

(*通信作者电子邮箱maoyingchi@gmail.com)

基于动态分簇的移动目标追踪方法

包 威，毛莺池*，王龙宝，陈小丽

(河海大学 计算机与信息学院，南京 211100)

(*通信作者电子邮箱maoyingchi@gmail.com)

针对无线传感器网络(WSN)中目标追踪的准确性低、网络能耗过高和网络生命周期短等问题，提出基于动态分簇的移动目标追踪技术。首先，构建了双层环状动态分簇的拓扑模型(TRDC)，并提出了动态分簇的更新算法；其次，在质心定位算法基础上，考虑到节点的能量，提出了基于功率级别的质心定位(CLPL)算法；最后，为了进一步减小网络的能耗，改进CLPL算法，提出了随机性定位算法。在仿真实验中，与静态簇相比，网络周期延长了22.73%；与非环状簇相比，丢失率降低了40.79%；而追踪准确性与基于接受信号强度值(RSSI)算法相差不大。所提的追踪技术能够有效保证追踪准确度，同时降低网络能耗，减小目标丢失率。

无线传感器网络；双层环状；目标追踪；动态簇；质心定位

0 引言

目标追踪是无线传感器网络(Wireless Sensor Network, WSN)最具代表性和基础性的应用之一。大量的微型传感器节点部署在监测区域内，通过无线通信方式形成一个多跳的自组织的网络系统称为无线传感器网络[1-2]。目标追踪在各个领域都有所涉及：如在军事上，对敌人坦克、装甲车进行定位和跟踪；在灾难预测方面，定位泥石流的发生地点以及扩散速度等信息；在动物迁徙监测方面，需要追踪迁徙的动物，获得其位置和种群等信息。移动目标追踪技术几乎涉及到无线传感器网络的各个应用领域，在环境监测[3]、军事监控[4]和基建保护[5]等领域都被广泛应用，体现了巨大的科学意义和应用前景。

目前，移动目标追踪技术采用的拓扑结构，在监测较快的移动目标时，存在着定位不够准确问题，容易出现丢失追踪目标，导致重新定位目标，消耗较大的能量，直接影响追踪目标的及时性，导致较长的网络延迟。现有的质心定位算法，在网络节点部署不均匀时，追踪目标时会出现较大的误差，追踪不够精确，而且网络中能量不同的节点对定位目标有较大的影响。此外，连续不断地定位追踪目标，虽然可以提供较为准确的目标定位，但是付出了较大的能耗代价。总之，无线传感器网络的移动目标追踪都要面对两个挑战：一是设计追踪模型，保证目标定位和移动轨迹描述的准确性；二是尽量减少目标追踪模型的能量消耗，延长整个网络的生命周期。

针对这两个问题，本文主要工作如下：

1)一般的动态分簇监测较快的移动目标时，容易丢失目标，提出双层环状动态分簇的拓扑模型(Two-Ring Dynamic Clustering, TRDC)；为适应目标的随机性移动，提出了动态簇的更新算法。

2)在质心定位算法的基础上进行改进，将节点的能量考虑在内，提出了基于功率级别的质心定位(Centroid Localization based on Power-Level, CLPL)算法；为了减少网络的能耗，进一步优化CLPL算法，结合目标移动的相关性，提出了随机性定位算法。

3)通过实验，得出基于环状动态分簇的移动目标追踪技术，在追踪准确度、能耗和丢失率等方面具有优势。

1 研究现状

传感器监测用户感兴趣的事件，节点间相互协作，计算出移动事件的轨迹，回传给基站。基站根据计算出来的轨迹，对移动事件进行追踪。目前，无线传感器网络的移动目标追踪技术一般可以归纳为：

1)基于二元传感器网络的目标追踪技术。如CTBD(Cooperative Tracking with Binary-Detection)[6]、BPS(Binary Proximity Sensors)[7]。追踪目标处于传感器节点感知范围内或感知范围外，二元传感器节点的功能非常有限，只能根据目标是否在节点的感知范围内作出决策，而无法测量目标与节点的距离。

2)基于节点选择协作的目标追踪技术。通过选择合适的节点协作执行追踪任务，减少网络内工作节点数目，降低数据传输量，从而节省能耗和通信带宽。信息驱动的节点协作机制[8]根据节点通信、获取目标位置信息以及处理监测数据的能耗三方面信息，选择下一时刻的跟踪节点。由于节点可以选择后继追踪节点，因此该机制能够有效减少参与追踪任务的节点数量。

3)可容错的目标追踪技术。由于传感器节点可能失效、感知部件精度有限和环境干扰等因素，WSN存在各种不确定性。容错机制可降低网络不确定性对目标追踪质量的影响，基于不可靠节点序列的目标追踪方法[9]，考虑到感知范围和环境噪声的不规则性等因素，将追踪问题转化为节点序列的最优化匹配问题。此外，引入睡眠调度机制[10]，使活跃节点协同工作对目标进行定位，此方法充分考虑了信息丢失和感知误差带来的非确定性。

4)基于特定网络拓扑结构的目标追踪技术。通过采用特定的网络拓扑结构，协助节点完成目标的监测和追踪任务。如基于分布式动态分簇的目标追踪方法[11]，该方法假设能力较强的特殊传感器节点担当簇头节点，当簇头节点监测到信号强度超过预定义阈值后，即转入活跃状态，并向邻居节点广播数据以召集簇内节点，簇头节点接收簇内成员的感知信息，并估算追踪目标位置。

5)基于预测模型的目标追踪技术。根据目标此时的位置，预测目标下一时刻的位置，调度节点处于工作状态或睡眠状态，节省网络能耗。由于目标的运动轨迹具有连续性，无法从单个时间间隔内预测目标移动轨迹，无缝数据挖掘(Seamless Data Mining, SDM)算法[12]能够发现移动目标的时间运动模式，并提出了基于时间运动模式的目标定位算法，有效减少预测误差。

2 系统模型

目标在区域内移动，能够被传感器节点监测的区域称为追踪区域。为了简化起见，本文对无线传感器网络模型作出了如下假设：

1)追踪区域S为二维平面区域；节点一旦部署不再移动；只有一个sink节点，其存储能力和计算能力不受限制；

2)节点均匀分布，每个节点有一个ID，从1到n标识；

3)节点通过GPS(Global Position System)或其他机制[13]获得自己的坐标信息，每个感知节点都能获得sink节点的坐标信息；

4)节点的感知功率级别是可调的，感知半径随功率级别动态变化[14]；

5)节点有四种状态：休眠(sleep)、等待(wait)、工作(work)和κ级别工作(κ_work)。工作状态的节点可正常感知和通信；休眠状态的节点不工作；等待状态的节点感知半径较小；κ级别工作是感知功率级别增大κ(κ≥1，κ=1时为正常工作状态)倍后的状态，具有较大的感知半径。节点信息表如表1所示。

表1 节点信息表

在目标未进入节点感知范围内，节点采取节能的工作机制[15]。当目标进入感知范围内后，为了提高监测的准确率，应使更多的节点加入监测，但不能监测到目标的节点仍采取节能机制，避免不必要的能耗。因此，在保证监测准确率的同时，又能降低节点的能耗，本文采用动态分簇的拓扑结构。

3 动态分簇

3.1 双层环结构动态簇

在构建动态簇前，先对网络进行初始化。分为两阶段：第一阶段，将节点都设为等待状态，sink节点以最大功率进行广播，给定合适的阈值，若节点收到的信号强度大于阈值，则进入工作状态并置q为1，向sink节点报告其ID和剩余能量，sink节点将这些信息登记到sink候选簇头表中(表2)；反之，则进入休眠状态。第二阶段，工作状态的节点调整通信功率至一跳范围距离(表3)，进行消息广播，收到消息的节点进入工作状态，并将其ID和剩余能量回传，同时调整通信功率至一跳范围距离，进行消息广播，邻居节点互相登记信息到邻居节点信息表。

表2 sink节点候选簇头表

双层环结构动态簇的构建分为以下步骤：

1)等待就绪。目标出现在追踪区域之前，节点以等待状态监测网络中可能出现的移动目标。

2)构建内层环结构。当目标进入追踪区域后，所有能监测到目标出现的节点进入正常工作状态，加入内层环集合，同时根据邻居节点信息表，通知邻居节点，如果邻居节点已经处于内层环集合，则不作回应。

3)构建外层环结构。收到通知的非内层环集合的邻居节点，首先调整至正常工作状态，然后再将功率增大至κ倍，感知范围增大。此时，如果邻居节点能够监测到移动目标，则加入外层环集合，进入κ级别工作状态；反之，邻居节点降低功率，进入等待状态。

表3 i节点一跳范围内邻居节点信息表

如图1所示，1所在的是外环，2所在的是内环。虚线表示内外环之间的一跳关系。

图1 双层环结构动态簇

3.2 簇内工作机制

簇内成员节点监测移动目标，实时向簇头节点汇报数据和剩余能量。簇头节点的工作主要是：

1)估计移动目标当前位置。簇头节点收到数据后，执行数据处理，估算目标的位置。

2)更新簇内信息。簇头节点收到簇内成员的能量信息后，将数据登记到临时簇成员信息表(由成员ID和剩余能量组成)，每隔一段时间后，广播临时簇成员信息表数据，簇内成员收到数据后，查询临时簇成员信息表，在邻居节点信息表中更新此邻居节点信息。

3)向sink节点传送数据。簇头节点通过单跳或多跳的路由方式[16]将目标位置数据和能量信息发送到sink节点， sink节点收到信息后，查询sink节点候选簇头信息表，如果存在此簇头节点信息，则更新sink节点候选簇头信息表；否则只接收位置数据。

3.3 分簇动态更新

随着目标的随机移动或追踪区域的改变，簇结构也发生变化，因此动态簇需要定期更新，主要考虑以下三方面：新监测到移动目标的节点加入、不能监测到移动目标的节点退出和簇头节点移交。

3.3.1 新节点加入动态簇

目标在不停地移动，追踪区域内处于等待状态的节点会监测到目标，将这些节点加入动态簇。

对于任意一个非簇内节点i，即i∉Cdyn，当目标进入感知范围内，节点i发送加入动态簇的广播请求REQin。等待Δt时间后，如果收到簇头节点j的同意信息ANSin，则节点i加入簇Cj，簇头节点j将节点i信息登记到临时簇成员信息表；如果没有收到任何信息，则进入构建动态簇的步骤。节点i根据邻居节点信息表，通知一跳范围内的邻居节点k，节点k进入κ级别工作状态，如果能监测到移动目标，则申请加入簇Cj，否则进入等待状态。

新节点加入动态簇算法如算法2所示。

算法1intJoin(i,j)算法。

输入：节点i，当前簇头节点j的动态簇Cj。 输出：节点i加入Cj。

1)

/*Si表示节点i是否监测到目标：值0表示未监测到，值1表示监测到；i.id、i.energy分别为节点i的编号和剩余能量；Cdyn为动态簇；T_CM为临时簇成员信息表*/

2)

IfSi=1

3)

NodeisendREQinto sink nodej

4)

Wait for Δttime

5)

If nodeireceive theANSinfrom sinkj

6)

Then

7)

Cj=Cj+i

//加入动态簇Cj

8)

Sinknodejrecordi.id,i.energyto T_CM

9)

Return 1

10)

Else

11)

Create a dynamic cluster

12)

Return 0

13)

End

14)

End

算法2 新节点加入动态簇算法。

输入：移动的目标、新节点和动态簇。 输出：新节点加入动态簇。

1)

//i.state为节点i的状态

2)

Foreachnodei(i∉Cdyn)

3)

Join(i,j)

//节点i加入动态簇成功或构建动态簇

4)

Nodeiinform neighbors in T_NET

5)

For eachkofi’s neighbors

6)

k.state←κ_work

//进入κ级别工作状态

7)

If(Join(k,j)==0)

8)

k.state←wait

9)

End

10)

End

11)

End

3.3.2 失效节点退出动态簇

处于工作状态的簇内节点，当目标移出其感知范围，不能监测到移动目标，这些节点退出动态簇。

对于任意一个簇内节点i，即i∈Cdyn,当目标移出其感知范围，向簇头j发送退出动态簇的请求REQout。簇头节点j收到请求后，在临时簇成员信息表中删除相关信息，返回同意信息ANSout。节点i收到同意信息后，进入等待状态，退出簇Cj；如果等待Δt时间后，没有收到信息，则自动退出簇Cj。

失效节点退出动态簇算法如算法3所示。

算法3 失效节点退出动态簇算法。

输入：移动的目标，动态簇Cj。 输出：失效节点退出动态簇。

1)

ForeachnodeiinCj,i∈Cdyn:

2)

IfSi=0

3)

SendREQoutto sink nodej

4)

If sink nodejreceive theREQout

5)

Delete the items ofifrom T_CM

6)

Sink nodejsend backANSoutto nodei

7)

End

8)

IfnodeireceivetheANSout

9)

Then

10)

i.state←wait

11)

Cj=Cj-i

//节点i退出

12)

Else

13)

WaitforΔttime

14)

Cj=Cj-i

15)

End

16)

End

17)

End

3.3.3 簇头节点移交

簇头节点可能因为监测不到目标而失效，使整个动态簇失效，导致追踪结束，因此，簇头节点的移交是非常重要。对于目前以i为簇头的动态簇Ci中：

1)新加入簇的节点j，簇头节点i查询sink节点的候选簇头信息表。如果节点j属于sink候选簇头集合，则选择节点j为新的簇头。节点i将所有信息移交给簇头节点j，然后作为簇内成员节点继续工作。簇头节点j向簇内成员广播簇头信息。至此，动态簇成为以节点j为簇头的簇Cj。

2)如果节点j不属于sink候选簇头集合，则节点i继续作为簇头。同时，簇头节点i将节点j登记到簇内候选簇头信息表中。当簇头节点i不能监测到目标时，立即查找簇内候选簇头信息表，选择剩余能量Ek(0

簇头节点移交算法如算法4所示。

算法4 簇头节点移交算法。

输入：移动的目标、动态簇Ci。 输出：失效节点退出动态簇。

1)

/*CM为簇内成员，CH为簇头；T_S_CH为sink节点候选簇头表；T_CM_CH为簇内候选簇头信息表*/

2)

//情况1：选取新节点为簇头节点

3)

Instageone：

4)

ForeachnewCMjinCi(j∈Cdyn)：

5)

Ifj∈T_S_CH

6)

Then

7)

Nodejis elected to the CH

8)

Nodeisend T_CM，T_CM_CH to nodej

9)

Ci←Cj

//动态簇变为Cj

10)

CHjbroadcast the message inCj

11)

Else

12)

CH record nodejto the T_CM_CH

13)

End

14)

End

15)

//情况2：选取簇内候选簇头里的节点为簇头

16)

In stage two：

17)

IfSi=0

18)

Choose nodekfor the CH from T_CM_CH whose energy is the most

19)

Nodeisend T_CM，T_CM_CH to nodek

20)

i.state←wait

21)

Ck←Ci

//动态簇变为Ck

22)

Ck=Ck-i

23)

CHkbroadcast the message inCk

24)

End

分簇动态更新如图2所示，虚线圈是前一个时刻的簇情况，实线圈是当前时刻的簇情况。随着目标的移动，节点1，2，3和4失效，退出了动态簇。节点5加入了动态簇，并通知一跳范围内的三个邻居节点，进入κ级别工作状态。

图2 动态簇更新示意图

4 基于环状分簇的目标追踪技术

4.1 基于功率级别的质心定位算法

质心定位算法将质心作为移动目标的位置，容易实现且成本低。但在本文的应用场景中，各节点与目标之间距离差异较大，节点能量也会影响定位精确度，针对这些问题，在质心定位算法上改进，提出了基于功率级别的质心定位算法。

定义1 质心O(x,y)。规则多边形的几何中心称为质心。假设一个规则多边形的顶点坐标为(x1,y1)，(x2,y2)，…，(xn,yn)，则：

(1)

定义2 内环集合SIR(Inner Ring Set, IRS)。对于任意的节点i，i∈Cdyn，若节点i主动监测到移动目标，则i∈SIR，SIR⊂Cdyn。

定义3 外环集合SOR(Outer Ring Set, ORS)。对于任意的节点i，i∈Cdyn，若节点i被动进入工作状态，即节点j通知节点i进入工作状态，j∈SIR，则i∈SOR，SOR⊂Cdyn。

外环节点的功率是内环节点的功率的κ倍，由于功率的不同，内外环节点的感知范围和初始发射能量也不同。对质心定位算法进行改进，结合功率因素，提出基于功率级别的质心定位算法。公式如下：

(2)

其中：k是内环节点的数目，q是外环节点的数目，β是内外环节点的权值，由于内环节点离移动目标更近，内环节点得出的位置坐标占有较大的权重，所以β取值范围：1/2≤β<1。式(2)还可以进一步简化，令α=β/(1-β)，可以得到：

基于功率级别的质心定位(CLPL)算法如算法5所示。

算法5 基于功率级别的质心定位算法。

输入：内环集合SIR，外环集合SOR，动态簇Cdyn。 输出：目标位置。

1)

//CH为簇头；μIR存放内环集合结果； μOR存放外环集合结果；

2)

ForeachnodeiinSIR

3)

CHcalculateasbelow

4)

μIRx=μIRx+xi

5)

μIRy=μIRy+yi

6)

k++

7)

End

8)

ForeachnodejinSOR

9)

CHcalculateasbelow

10)

μORx=μORx+xj

11)

μORy=μORy+yj

12)

q++

13)

End

14)

CHgetthetarget’sposition:

//结合两层集合，得出目标位置

4.2 随机性定位算法

Trace=(TS(1),TS(2),…,TS(n))

(4)

其中，TS(i)∈TSet，序列Trace是有序的，代表移动路径，起点是TS(1)，终点是TS(n)。

在基于功率级别定位算法中，簇头节点持续性定位，不间断计算位置信息，并传送给sink节点，能耗较大。本文提出了改进的算法——随机性定位算法，簇头节点能够随机性定位移动目标。

无线传感器网络中存在着时空相关性[17]，可以根据目标移动的相关性，随机性定位。随机不是无规律状态，而是随目标情况而定。例如某一时刻，目标移动缓慢，则位置信息可以默认为上一时刻的信息，簇头不进行定位；而在目标移动较快时，簇头开始不间断定位。目标的移动相关性可以通过动态簇的改变获取，动态簇的改变体现在簇内成员节点加入或退出。在此，给出一个动态簇改变的狭义定义。

定义5ε-threshold簇改变。在一个时间序列T{t1,t2,…,tn}中，在Δt时间段内，在簇头没有移交的情况下，有τ1个节点退出动态簇，有τ2个节点加入动态簇，如果τ1+τ2>ε，则认为动态簇改变。

根据定义5，提出随机性定位算法如下：

1)在簇头节点中定义一个计数值count，置初值为0。

2)在簇头节点没有移交情况下，有簇内成员节点退出，count++；同样，新节点加入动态簇，count++。

3)如果count>ε，则认为动态簇改变，簇头节点进行定位计算，并将相关信息发送给sink节点。同时，置count为0。

4)如果簇头节点进行了移交，则动态簇改变，新的簇头节点进行定位计算，并将相关信息发送给sink节点，同时，置count为0。

随机性定位算法如算法6所示。

算法6 随机性定位算法。

输入：移动的目标，动态簇Cdyn；给定的阈值ε；CH簇头节点。 输出：目标位置。

1)

//计数器count

2)

While(there is node join into theCdynor exit theCdyn)

3)

count++

4)

Ifcount>ε

5)

CHexecuteCLPL

6)

CHsendresulttosinknode

7)

count=0

8)

End

9)

If CH is changed

10)

New CH execute CLPL

11)

New CH send result to sink node

12)

count=0

13)

End

14)

End

4.3 算法分析

4.3.1 能耗分析

根据能耗模型[18]，本文假设追踪区域中节点的平均分布密度为ρ，则节点感知区域内的节点个数为ρπr2。内环节点在监测目标过程中，单位时间消耗的能量为δ；外环节点单位时间消耗的能量为κδ。

由于一个分簇内，节点之间的距离基本上在一跳之内，所以簇内成员节点与簇头通信的能耗基本上忽略不计。在单位时间内，簇头节点与sink节点通信消耗的能量为ES。

因此，每次分簇定位目标位置所需要的总能耗为：

E=δρπr2+κδρπr2+ES

(5)

4.3.2 能耗均衡性分析

从动态分簇和数据传输两个阶段分别分析能耗均衡性。

在动态分簇阶段，为了能够对移动目标进行实时监测，本文提出了分簇动态更新算法。随着目标移动，分簇结构动态更新，必然会使整个网络达到良好的能耗均衡性。在网络初始化过程中，为了保护低能量节点，sink节点备选了通信良好的候选簇头，避免产生多余的跳距，消耗过多能量。

在数据传输阶段，处于内环节点监测负担比较重，能耗较高。为了均衡分簇的能量结构，外环节点工作功率调为κ级别。在基于功率级别的定位算法中，外环节点分担内环监测的任务，均衡整个分簇的能量结构，同时扩大了对移动目标的追踪范围，避免因目标移动较快而丢失的情况。

4.3.3 网络延迟和监测概率分析

目标监测延迟定义为在网络中一个移动目标o从发生到被监测到的时间长度的期望值。目标监测概率定义为在网络中一个移动目标o至少被一个工作节点监测到的概率。

在LEACH(Low Energy Adaptive Clustering Hierarchy)协议[16]中，假设在网络生命周期里，事件发生概率相等且持续时间大于(m-1)×T(T表示LEACH协议运行一轮的时间长度，m表示节点状态进行一个调度循环所经需的轮数)。若一个事件e发生在监测区域中某点p，点p可以被s个传感器节点所覆盖。在此网络场景下，一个事件的监测延迟受到三个因素影响：时间长度T、轮数m和覆盖节点数s。如果T增大或m增加，事件平均监测延迟也增加；相反，点数s增加，事件平均监测延迟就减少。

本文提出的基于环状分簇移动目标追踪模型，与上述模型类似。唯一区别的是，如果移动目标的瞬时速度v较快，分簇定位到目标的概率较低，目标定位的时间较长。

5 实验与分析

5.1 实验环境

为了观察基于环状动态分簇的目标追踪技术的执行效率，本文通过Matlab仿真平台进行仿真实验。

目标在刚进入追踪区域时，定位误差会比较大，这是不可避免的情况，在实验仿真中，不考虑目标进入或退出追踪区域的情况。假设移动目标是一个圆点，不考虑其大小。基本参数设置如表4所示。

表4 仿真参数设置

在100m×100m的二维追踪区域内，随机均匀部署了100个传感器节点，在追踪区域内，模拟目标随机移动的一种路径，轨迹方程为：

Trace(x,y,t)=

(6)

其中，参数t从0.01增至2，间隔为0.01。

5.2 实验结果与分析

本文从环状分簇结构和追踪算法两方面进行实验仿真，环状结构方面包括：动态簇与静态簇比较、功率κ值分析及速度对追踪的影响；追踪算法方面包括：权值α比较与定位算法误差。

5.2.1 动态簇与静态簇比较

图3展示了本文的动态簇模型和一种静态簇模型——网格模型[19]在生存时间上对比结果。实验假定，当网络中能够工作的节点数小于总节点数一半时，整个网络的生命周期完结。静态簇是一种在网络运作前选好簇头的模型，每一个簇的地位是平等的。

由图3可知，动态簇模型在生存周期的长度上显然要好于静态簇，动态簇比静态簇能够节省更多的能量消耗。从图3可以看出，在相同的追踪区域内，部署的节点越多，网络的生存时间越长；在相同节点数情况下，动态簇的生存时间是明显长于静态簇。与静态簇相比，动态簇的平均网络周期延长了22.73%。

5.2.2 功率κ值分析

如图4所示，节点的功率级别不一样，感知半径也不同，那么感知覆盖的区域也不一样，定位的精确度也会受到影响。在κ值小于1.7时，移动目标的定位平均误差随着功率级别κ值增大而降低；在κ值大于1.7时，平均误差随着功率级别κ值呈增大趋势。在κ值为1.1的时候，误差值有个上升，这是由于外环节点的加入，此时，外环节点的数目相对于内环节点来说比较少，定位结果以内环节点为主导。随着功率级别κ值增大，越来越多的外环节点加入分簇，定位结果更具有均衡性；在κ值增至1.7之后，外环节点的数目较多，从而起到主导作用，目标定位误差增大。

图3 动态簇与静态簇生存时间

图4 功率级别κ与追踪误差关系

κ值对追踪准确性有较大的影响，当取值不合理时，误差甚至超过1.2 m。在κ值为1时，内外环节点具有相同的能量，此时的定位误差为1.2 m，产生较大的误差，对比κ值为1.7时，误差不到0.6 m，在可接受范围内，可见κ值对定位误差有较大影响；当κ值超过2时，误差超过1 m，对定位精度产生很大的影响。

因此，不是功率级别κ越大，移动目标的定位越准确；但功率级别越大，分簇的结构越大，移动目标的丢失率越小。

5.2.3 速度对追踪的影响

如图5所示，对于环状分簇和非环状分簇模型，当目标的移动速度越大，移动目标追踪的丢失率越大，准确度越低。在目标的移动速度相等时，环状分簇模型比非环状分簇模型丢失率低，追踪的准确度高。当目标的移动速度低于4m/s的时候，采用环状分簇模型对移动目标追踪，丢失率可以忽略不计；高于4m/s时，丢失率急剧增加。与非环状簇相比，在速度小于4m/s时丢失率降低了61.09%，速度大于4m/s时丢失率降低了34.02%，总体平均降低了40.79%。

由此可知，基于环状分簇的目标追踪算法，目标的丢失率较低，可以减少因目标丢失而重构分簇带来的能耗。

图5 目标移动速度与丢失率关系

5.2.4 定位算法的误差

图6显示，CLPL算法和基于接受信号强度值(ReceivedSignalStrengthIndicator,RSSI)定位算法[20]误差比较。目标在追踪区域移动时间为40s，分簇每秒对移动目标定位一次。CLPL算法得出的定位误差，是外环节点为1倍功率级别的情况。最小误差是0.2m，最大误差是3.1m，平均误差是1.29m。基于RSSI定位算法，最小误差是0.8m，最大误差是1.6m，平均误差是1.16m。

由此可知，基于RSSI的定位算法，路径精确度稍微高点，误差值比较稳定。但是，基于RSSI的定位算法，需要获取详细精确的距离与角度信息，对硬件的要求比较高。CLPL算法，对硬件要求可以忽略不计，相较于基于RSSI定位算法1.16m的误差，1.29m的误差也是比较乐观的。

图6 CLPL与RSSI目标定位误差

5.2.5 权值α与平均误差分析

图7显示了在外环节点感知半径设为9.9 m的情况下，权值α对应移动目标定位的平均误差值。如图7所示，α值在2～2.5，移动目标定位的平均误差值较小。由式(3)可知，α值较大，得到的定位结果偏向于内环节点；α较小，得到的定位结果偏向于外环节点。当α值为1时，内外环节点具有相同的权重，此时误差较大，接近1.4 m，可见不合适的α值，对定位精确度影响较大。

由此可知，α值直接影响移动目标的定位准确度，合适的α值很重要。

5.2.6 随机性定位算法对平均误差的影响

图8展示了随机性定位算法对目标追踪平均误差的影响。当ε值为0的时候，随机性定位算法未介入追踪算法，此时平均误差即为CLPL算法得出的定位误差，为1.29 m；当ε值大于0的时候，随机性定位算法开始介入追踪算法，随着ε值增大，平均误差也在增大，以ε值为2为分界点，在之前平均误差增大趋势较缓，之后误差增大趋势较陡。

由此可知，设定合适的ε阈值，对于追踪的影响还是比较明显的，需寻求能耗代价与追踪精确度的折中点。

图7 权值α对应的平均误差

图8 ε值与平均误差关系

6 结语

本文提出双层环状动态分簇的拓扑模型，并给出了动态分簇的更新算法，以解决目标移动随机性很大和分簇的监测任务较重等问题。在质心定位算法的基础上，提出了基于功率级别的质心定位算法。考虑到网络的能耗问题，对基于功率级别的质心定位算法进行改进，提出了随机性定位算法。最后通过仿真实验验证了基于环状动态分簇的移动目标追踪技术，在追踪准确度、能耗和丢失率等方面的优势。

References)

[1] 孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005:135-155.(SUN L M, LI J Z, CHEN Y, et al.Wireless Sensor Network [M].Beijing: Tsinghua University Press, 2005:135-155.)

[2] BRANCH J W, GIANNELLA C, SZYMANSKI B, et al.In-network outlier detection in wireless sensor networks [J].Knowledge and Information Systems, 2013, 34(1): 23-54.

[3] MO L, HE Y, LIU Y, et al.Canopy closure estimates with GreenOrbs: sustainable sensing in the forest [C]// Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems.New York: ACM, 2009: 99-112.

[4] HE T, KRISHNAMURTHY S, LUO L, et al.VigilNet: an integrated sensor network system for energy efficient surveillance [J].ACM Transactions on Sensor Networks, 2006, 2(1):1-38.

[5] HACKMANN G, GUO W, YAN G, et al.Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks [J].IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 63-72.

[6] MECHITOV K, SUNDRESH S, KWON Y, et al.Cooperative tracking with binary-detection sensor networks [C]// Proceedings of the 1st International Conference on Embedded Networked Sensor Systems.New York: ACM, 2003: 332-333.

[7] KIM W, MECHITOV K, CHOI J Y, et al.On target tracking with binary proximity sensors [C]// IPSN 2005: Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks.Piscataway, NJ: IEEE, 2005: 301-308.

[8] ZHAO F, SHIN J, REICH J.Information-driven dynamic sensor collaboration for tracking applications [J].IEEE Signal Processing Magazine, 2002, 19(2): 61-72.

[9] ZHONG Z, ZHU T, WANG D, et al.Tracking with unreliable node sequences [C]// INFOCOM 2009: Proceedings of the 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ: IEEE, 2009: 1215-1223.

[10] WANG Z J, BULUT E, SZYMANSKI B K.Distributed energy-efficient target tracking with binary sensor networks [J].ACM Transactions on Sensor Networks, 2010, 6(4): Article No.32.

[11] KHALIL E A, ATTEA B A.Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks [J].Swarm and Evolutionary Computation, 2011, 1(4): 195-203.

[12] LIN K W, HSIEH M H, TSENG V S.A novel prediction-based strategy for object tracking in sensor networks by mining seamless temporal movement patterns [J].Expert Systems with Applications, 2010, 37(4):2799-2807.

[13] SUN K, NING P, WANG C.Secure and resilient time synchronization in wireless sensor networks [C]// Proceedings of the 13th ACM Conference on Computer and Communications Security.New York: ACM, 2006: 264-277.

[14] JEONG J, HWANG T, HE T, et al.MCTA: target tracking algorithm based on minimal contour in wireless sensor networks [C]// INFOCOM 2007: Proceedings of the 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ: IEEE, 2007: 2371-2375.

[15] VICAIRE P, HE T, CAO Q, et al.Achieving long-term surveillance in VigilNet [J].ACM Transactions on Sensor Networks, 2009, 5(1): Article No.39.

[16] TYAGI S, KUMAR N.A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks [J].Journal of Network and Computer Applications, 2013, 36(2): 623-645.

[17] BROOKS R R, RAMANATHAN P, SAYEED A M.Distributed target classification and tracking in sensor networks [J].Proceedings of IEEE, 2003, 91(8):1163-1171.

[18] YANG H, SIKDAR B.A protocol for tracking mobile targets using sensor networks [C]// Proceedings of the 2003 IEEE International Workshop on Sensor Network Protocols and Applications.Piscataway, NJ: IEEE, 2003: 71-81.

[19] BULUSU N, ESTRIN D, GIROD L, et al.Scalable coordination for wireless sensor networks: self-configuring localization systems [C]// ISCTA 2001: Proceedings of the 6th International Symposium on Communication Theory and Applications.Ambleside, UK: [s.n.], 2001: 1-6.

[20] 陈维克,李文锋,首珩,等.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报(交通科学与工程版),2006,30(2):265-268.(CHEN W K, LI W F, SHOU H, et al.Weighted centroid localization algorithm based on RSSI for wireless sensor networks [J].Wuhan Science University of Technology (Transportation Science and Engineering), 2006, 30(2): 265-268.)

This work is partially supported by the National Natural Science Foundation of China (U1301252), the National Science and Technology Support Program (2013BAB06B04), the Technology Project of China Huaneng Group Company Headquarters (HNKJ13-H17-04), the Science and Technology Project of Yunnan Province (2014GA007), the Special Fund for Basic Scientific Research of Central Universities (2015B22214).

BAO Wei, born in 1990, M.S.candidate.His research interests include wireless sensor network, distributed computing, parallel processing.

MAO Yingchi, born in 1976, Ph.D., associate professor.Her research interests include distributed computing and parallel processing, distributed data management.

WANG Longbao, born in 1977, lecturer.His research interests include intelligent data processing, project management.

CHEN Xiaoli, born in 1993, M.S.candidate.Her research interests include wireless sensor network, distributed computing.

Moving target tracking scheme based on dynamic clustering

BAO Wei, MAO Yingchi*, WANG Longbao, CHEN Xiaoli

(CollegeofComputerandInformation,HohaiUniversity,NanjingJiangsu211100,China)

Focused on the issues of low accuracy, high energy consumption of target tracking network and short life cycle of network in Wireless Sensor Network (WSN), the moving target tracking technology based on dynamic clustering was proposed.Firstly, a Two-Ring Dynamic Clustering (TRDC) structure and the corresponding TRDC updating methods were proposed; secondly, based on centroid localization, considering energy of node, the Centroid Localization based on Power-Level (CLPL) algorithm was proposed; finally, in order to further reduce the energy consumption of the network, the CLPL algorithm was improved, and the random localization algorithm was proposed.The simulation results indicate that compared with static cluster, the life cycle of network increased by 22.73%; compared with acyclic cluster, the loss rate decreased by 40.79%; there was a little difference from Received Signal Strength Indicator (RSSI) algorithm in accuracy.The proposed technology can effectively ensure tracking accuracy and reduce energy consumption and loss rate.

Wireless Sensor Network (WSN); two-ring clustering; target tracking; dynamic cluster; centroid localization

2016-07-20;

2016-08-05。

国家自然科学基金资助项目(U1301252)；国家科技支撑计划项目(2013BAB06B04)；中国华能集团公司总部科技项目(HNKJ13-H17-04)；云南省科技计划项目(2014GA007)；中央高校基本科研业务费专项资金资助项目(2015B22214)。

包威(1990—)，男，江苏淮安人，硕士研究生，主要研究方向：无线传感器网络、分布式计算、并行处理； 毛莺池(1976—)，女，上海人，副教授，博士，CCF会员，主要研究方向：分布计算与并行处理、分布式数据管理； 王龙宝(1977—)，男，江苏盐城人，讲师，主要研究方向：智能数据处理、项目管理； 陈小丽(1993—)，女，河南洛阳人，硕士研究生，主要研究方向：无线传感器网络、分布式计算。

1001-9081(2017)01-0065-08

10.11772/j.issn.1001-9081.2017.01.0065

TP393.02

A