目标追踪是无线传感器网络(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所示。
在目标未进入节点感知范围内,节点采取节能的工作机制[15]。当目标进入感知范围内后,为了提高监测的准确率,应使更多的节点加入监测,但不能监测到目标的节点仍采取节能机制,避免不必要的能耗。因此,在保证监测准确率的同时,又能降低节点的能耗,本文采用动态分簇的拓扑结构。
3 动态分簇 3.1 双层环结构动态簇在构建动态簇前,先对网络进行初始化。分为两阶段:第一阶段,将节点都设为等待状态,sink节点以最大功率进行广播,给定合适的阈值,若节点收到的信号强度大于阈值,则进入工作状态并置q为1,向sink节点报告其ID和剩余能量,sink节点将这些信息登记到sink候选簇头表中(表 2);反之,则进入休眠状态。第二阶段,工作状态的节点调整通信功率至一跳范围距离(表 3),进行消息广播,收到消息的节点进入工作状态,并将其ID和剩余能量回传,同时调整通信功率至一跳范围距离,进行消息广播,邻居节点互相登记信息到邻居节点信息表。
双层环结构动态簇的构建分为以下步骤:
1) 等待就绪。目标出现在追踪区域之前,节点以等待状态监测网络中可能出现的移动目标。
2) 构建内层环结构。当目标进入追踪区域后,所有能监测到目标出现的节点进入正常工作状态,加入内层环集合,同时根据邻居节点信息表,通知邻居节点,如果邻居节点已经处于内层环集合,则不作回应。
3) 构建外层环结构。收到通知的非内层环集合的邻居节点,首先调整至正常工作状态,然后再将功率增大至κ倍,感知范围增大。此时,如果邻居节点能够监测到移动目标,则加入外层环集合,进入κ级别工作状态;反之,邻居节点降低功率,进入等待状态。
4) 选取簇头。如果有且只有一个节点的标记位为1,则此节点为簇头节点;否则查询sink节点候选簇头表,选择剩余能量最多的节点为簇头;若不存在以上节点,则选取簇内剩余能量多的节点为簇头。其余节点成为簇头的成员节点,对于任意簇头节点i,其簇内成员节点可用集合表示为Ci={jj∈Cdyn,0<j≤N,j≠i},Cdyn表示动态簇,在t时刻,簇头节点为i,则Cit=Cdyn。
如图 1所示,1所在的是外环,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所示。
算法1 int Join(i,j)算法。
输入:节点i,当前簇头节点j的动态簇Cj。
输出:节点i加入Cj。
1) /*Si表示节点i是否监测到目标:值0表示未监测到,值1表示监测到;i.id、i.energy分别为节点i的编号和剩余能量;Cdyn为动态簇;T_CM为临时簇成员信息表*/
2) If Si=1
3) Node i send REQin to sink node j
4) Wait for Δt time
5) If node i receive the ANSin from sink j
6) Then
7) Cj=Cj+i//加入动态簇 Cj
8) Sink node j record i.id,i.energy to 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) For each node i(i∉Cdyn)
3) Join(i,j)//节点i加入动态簇成功或构建动态簇
4) Node i inform neighbors in T_NET
5) For each k of i'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) For each node i in Cj,i∈Cdyn:
2) If Si=0
3) Send REQout to sink node j
4) If sink node j receive the REQout
5) Delete the items of i from T_CM
6) Sink node j send back ANSout to node i
7) End
8) If node i receive the ANSout
9) Then
10) i.state←wait
11) Cj=Cj-i//节点i退出
12) Else
13) Wait for Δt time
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<k<N)最大的节点作为新的簇头节点k,并将所有信息发送给簇头节点k,然后进入等待状态,退出动态簇。新的簇头节点k在收到临时簇成员信息表后,向簇内成员广播簇头信息。至此,动态簇成为以节点k为簇头的簇Ck。
簇头节点移交算法如算法4所示。
算法4 簇头节点移交算法。
输入:移动的目标、动态簇Ci。
输出:失效节点退出动态簇。
1) /*CM为簇内成员,CH为簇头;T_S_CH为sink节点候选簇头表;T_CM_CH为簇内候选簇头信息表*/
2) //情况1:选取新节点为簇头节点
3) In stage one:
4) For each new CM j in Ci(j∈Cdyn):
5) If j∈T_S_CH
6) Then
7) Node j is elected to the CH
8) Node i send T_CM,T_CM_CH to node j
9) Ci←Cj//动态簇变为Cj
10) CH j broadcast the message in Cj
11) Else
12) CH record node j to the T_CM_CH
13) End
14) End
15) //情况2:选取簇内候选簇头里的节点为簇头
16) In stage two:
17) If Si=0
18) Choose node k for the CH from T_CM_CH whose energy is the most
19) Node i send T_CM,T_CM_CH to node k
20) i.state←wait
21) Ck←Ci//动态簇变为Ck
22) Ck=Ck-i
23) CH k broadcast the message in Ck
24) End
分簇动态更新如图 2所示,虚线圈是前一个时刻的簇情况,实线圈是当前时刻的簇情况。随着目标的移动,节点1,2,3和4失效,退出了动态簇。节点5加入了动态簇,并通知一跳范围内的三个邻居节点,进入κ级别工作状态。
质心定位算法将质心作为移动目标的位置,容易实现且成本低。但在本文的应用场景中,各节点与目标之间距离差异较大,节点能量也会影响定位精确度,针对这些问题,在质心定位算法上改进,提出了基于功率级别的质心定位算法。
定义1 质心O(x,y)。规则多边形的几何中心称为质心。假设一个规则多边形的顶点坐标为(x1,y1),(x2,y2),…,(xn,yn),则:
$O(x,y)=(\sum\limits_{i=1}^{n}{{{x}_{i}}}/n,\sum\limits_{i=1}^{n}{{{y}_{i}}}/n)$ | (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。
外环节点的功率是内环节点的功率的κ倍,由于功率的不同,内外环节点的感知范围和初始发射能量也不同。对质心定位算法进行改进,结合功率因素,提出基于功率级别的质心定位算法。公式如下:
$\begin{align} & O(x,y)= \\ & \left( \left( \beta \sum\limits_{i=1}^{k}{{{x}_{IRi}}}+(1-\beta )\sum\limits_{i=1}^{q}{{{x}_{ORi}}} \right)/\left( \beta k+(1-\beta )q \right) \right., \\ & \left. \left( \beta \sum\limits_{i=1}^{k}{{{y}_{IRi}}}+(1-\beta )\sum\limits_{i=1}^{q}{{{y}_{ORi}}} \right)/\left( \beta k+(1-\beta )q \right) \right) \\ \end{align}$ | (2) |
其中:k是内环节点的数目,q是外环节点的数目,β是内外环节点的权值,由于内环节点离移动目标更近,内环节点得出的位置坐标占有较大的权重,所以β取值范围:1/2≤β<1。式(2) 还可以进一步简化,令α=β/(1-β),可以得到:
$\begin{align} & O(x,y)=\left( \left( \alpha \sum\limits_{i=1}^{k}{{{x}_{IRi}}}+\sum\limits_{i=1}^{q}{{{x}_{ORi}}} \right)/\alpha k+q \right., \\ & \left. \left( \alpha \sum\limits_{i=1}^{k}{{{y}_{IRi}}}+\sum\limits_{i=1}^{q}{{{y}_{ORi}}} \right)/\left( \alpha k+q \right) \right) \\ \end{align}$ | (3) |
此时,α是内环节点关于质心方程式的权值,α取值范围:α≥1。
基于功率级别的质心定位(CLPL)算法如算法5所示。
算法5 基于功率级别的质心定位算法。
输入:内环集合SIR,外环集合SOR,动态簇Cdyn。
输出:目标位置。
1) //CH为簇头;μIR存放内环集合结果; μOR存放外环集合结果;
2) For each node i in SIR
3) CH calculate as below
4) μIRx=μIRx+xi
5) μIRy=μIRy+yi
6) k++
7) End
8) For each node j in SOR
9) CH calculate as below
10) μORx=μORx+xj
11) μORy=μORy+yj
12) q++
13) End
14) CH get the target's position:
$O(x,y)=(\frac{\alpha {{\mu }_{IRx}}+{{\mu }_{ORx}}}{\alpha k+q},\frac{\alpha {{\mu }_{IRy}}+{{\mu }_{ORy}}}{\alpha k+q})$ |
//结合两层集合,得出目标位置
4.2 随机性定位算法定义4 路径集合(Trace Set,TS)。由时间序列上的位置坐标组成的集合,TSet={(ti,Oti(x,y))ti∈T{t1,t2,…,tn}}。那么,目标在追踪区域内的移动路径,可以用序列表示为:
$Trace=\left( {{T}_{S}}(1),{{T}_{S}}(2),...,{{T}_{S}}(n) \right)$ | (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 the Cdyn or exit the Cdyn)
3) count++
4) If count>ε
5) CH execute CLPL
6) CH send result to sink node
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=\delta \rho \pi {{r}^{2}}+\kappa \delta \rho \pi {{r}^{2}}+{{E}_{S}}$ | (5) |
从动态分簇和数据传输两个阶段分别分析能耗均衡性。
在动态分簇阶段,为了能够对移动目标进行实时监测,本文提出了分簇动态更新算法。随着目标移动,分簇结构动态更新,必然会使整个网络达到良好的能耗均衡性。在网络初始化过程中,为了保护低能量节点,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所示。
在100 m×100 m的二维追踪区域内,随机均匀部署了100个传感器节点,在追踪区域内,模拟目标随机移动的一种路径,轨迹方程为:
$\eqalign{ & Trace(x,y,t) = \cr & \left\{ \matrix{ x = {\rm{50}}*{\rm{cos(}}t{\rm{/1}}{\rm{.05)}} + {\rm{50}}*{\rm{sin(1}}{\rm{.35}}t{\rm{)}} \hfill \cr y = {\rm{40}}*{\rm{sin(}}t{\rm{)}}*{\rm{cos(}}t{\rm{)}} + {\rm{45}}*{\rm{cos(3}}t{\rm{)}} + {\rm{35}} \hfill \cr t = {\rm{ }}[{\rm{ 0}}{\rm{.01:0}}{\rm{.01:2 }}]{\rm{ }} \hfill \cr} \right. \cr} $ | (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之后,外环节点的数目较多,从而起到主导作用,目标定位误差增大。
κ值对追踪准确性有较大的影响,当取值不合理时,误差甚至超过1.2 m。在κ值为1时,内外环节点具有相同的能量,此时的定位误差为1.2 m,产生较大的误差,对比κ值为1.7时,误差不到0.6 m,在可接受范围内,可见κ值对定位误差有较大影响;当κ值超过2时,误差超过1 m,对定位精度产生很大的影响。
因此,不是功率级别κ越大,移动目标的定位越准确;但功率级别越大,分簇的结构越大,移动目标的丢失率越小。
5.2.3 速度对追踪的影响如图 5所示,对于环状分簇和非环状分簇模型,当目标的移动速度越大,移动目标追踪的丢失率越大,准确度越低。在目标的移动速度相等时,环状分簇模型比非环状分簇模型丢失率低,追踪的准确度高。当目标的移动速度低于4 m/s的时候,采用环状分簇模型对移动目标追踪,丢失率可以忽略不计;高于4 m/s时,丢失率急剧增加。与非环状簇相比,在速度小于4 m/s时丢失率降低了61.09%,速度大于4 m/s时丢失率降低了34.02%,总体平均降低了40.79%。
由此可知,基于环状分簇的目标追踪算法,目标的丢失率较低,可以减少因目标丢失而重构分簇带来的能耗。
5.2.4 定位算法的误差图 6显示,CLPL算法和基于接受信号强度值(Received Signal Strength Indicator,RSSI)定位算法[20]误差比较。目标在追踪区域移动时间为40 s,分簇每秒对移动目标定位一次。CLPL算法得出的定位误差,是外环节点为1倍功率级别的情况。最小误差是0.2 m,最大误差是3.1 m,平均误差是1.29 m。基于RSSI定位算法,最小误差是0.8 m,最大误差是1.6 m,平均误差是1.16 m。
由此可知,基于RSSI的定位算法,路径精确度稍微高点,误差值比较稳定。但是,基于RSSI的定位算法,需要获取详细精确的距离与角度信息,对硬件的要求比较高。CLPL算法,对硬件要求可以忽略不计,相较于基于RSSI定位算法1.16 m的误差,1.29 m的误差也是比较乐观的。
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为分界点,在之前平均误差增大趋势较缓,之后误差增大趋势较陡。
由此可知,设定合适的ε阈值,对于追踪的影响还是比较明显的,需寻求能耗代价与追踪精确度的折中点。
6 结语本文提出双层环状动态分簇的拓扑模型,并给出了动态分簇的更新算法,以解决目标移动随机性很大和分簇的监测任务较重等问题。在质心定位算法的基础上,提出了基于功率级别的质心定位算法。考虑到网络的能耗问题,对基于功率级别的质心定位算法进行改进,提出了随机性定位算法。最后通过仿真实验验证了基于环状动态分簇的移动目标追踪技术,在追踪准确度、能耗和丢失率等方面的优势。
[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. doi: 10.1007/s10115-011-0474-5 |
[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. doi: 10.1145/1138127 |
[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. doi: 10.1109/TPDS.2013.30 |
[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. doi: 10.1109/79.985685 |
[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. doi: 10.1016/j.swevo.2011.06.004 |
[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. doi: 10.1016/j.eswa.2009.09.011 |
[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. doi: 10.1016/j.jnca.2012.12.001 |
[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. doi: 10.1109/JPROC.2003.814923 |
[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. ) |