无线传感网跟踪任务中的目标运动模型估计与节点调度

王祺尧，冯 辉，胡 波，罗灵兵

(1.复旦大学 信息科学与工程学院 电子工程系，上海 200433； 2.复旦大学 信息科学与工程学院智慧网络与系统研究中心，上海 200433)

随着无线通信技术、嵌入式设备技术、片上系统技术等各项技术的高速发展，无线传感器网络(Wireless Sensor Networks, WSN)在军事和民用领域[1-3]发挥着越来越重要的作用.目标跟踪[4-6]是无线传感器网络的重要应用之一.然而，由于能量、带宽和观测范围的限制，打开区域内的所有传感器对目标进行跟踪的开销过高，且带来了不必要的资源浪费.节点调度算法[4，7]在每个决策时间内自适应地打开部分传感器对跟踪区域进行观测，从而有效地应对上述问题，部分文献中也将节点调度算法称为节点选择[8]、节点规划[6]等.对于无线传感器网络来说，为了降低系统功耗，延长工作时间，设计一种跟踪精度高、能量开销低的节点调度算法显得尤为重要.

无线传感器网络的节点调度具有很强的理论与现实意义，许多学者对这一场景进行了研究.一些研究通过选择能够最小化瞬时误差或带来最大信息增益的传感器子集，建立优化函数.优化准则包括熵和相对熵、互信息、最小均方误差、先验克拉美罗下界、条件克拉美罗下界等[8-10].这些算法仅考虑了节点调度算法的瞬时表现，没有考虑当前决策对未来的影响，所以被称为“短视”的策略.

图1 节点调度流程Fig.1 Procedure of sensor scheduling

如图1所示，根据当前时刻的节点调度策略打开部分传感器，得到观测结果，会影响传感器对目标位置的估计，而这一估计又会影响下一时刻的节点调度策略.因此这是一个序贯决策过程，当前决策会对未来的走向产生影响.综合考虑决策的瞬时和长远表现，可以得到整体更优的决策.常见的做法是将该问题建模为部分可观测马尔可夫决策过程(Partially Observable Markov Decision Process, POMDP)[11-13]，即根据历史动作和带噪观测序列，求解使得当前及未来累积代价最小的优化策略.

在POMDP的建模中，需要已知目标的运动模型(即状态转移方程)，其中目标的状态通常包括目标的位置与速度等信息.在文献[14-15]中假设目标速度变化缓慢，使用近似恒定速度(Nearly Constant Velocity, NCV)模型[16]构建了状态转移方程.但是当监控区域中存在障碍物，或目标移动存在趋向性时，例如在楼宇、商场、道路等复杂环境中，不同位置的转移概率均不相同，不能简单使用单个方程刻画目标的状态转移.为了解决这类场景的目标跟踪问题，本文使用状态转移矩阵作为目标运动模型，矩阵中元素为目标状态的转移概率.在传感器观测不够精确的情况下，如果缺乏运动模型的先验知识，将难以在目标跟踪过程中实现高效的节点调度.因此，根据传感器采集的观测，估计监控区域中目标的转移概率，对于提高节点调度过程的目标跟踪精度、降低系统功耗均具有积极的意义.

本文将目标移动和传感器观测过程建模为隐马尔可夫模型(Hidden Markov Model, HMM)[17-18]，提出了HMM-QMDP算法，将无线传感器网络中未知运动模型的目标跟踪问题分解为运动模型估计过程和节点调度过程.首先，在传感器完全开启的条件下，采集目标移动过程的观测序列，使用Baum-Welch算法对区域中目标的状态转移矩阵进行估计.然后，将节点调度问题建模为部分可观测马尔可夫决策过程，根据估计求得的状态转移模型，使用QMDP算法[19]近似求解优化策略，实现目标跟踪过程中的实时节点调度.使用HMM-QMDP算法的优势有以下两点： 1) 将问题分解为运动模型估计过程与节点调度过程并分别求解，可以简化问题的复杂度；2) 将HMM状态转移模型估计的方法引入无线传感器网络的节点调度场景中，可以很好地学习目标运动模型，实现更加有效的节点调度.

1 跟踪目标的运动模型估计

在一个监控区域内部署了M个传感器，用于跟踪目标轨迹.由传感器可以获得带噪观测，然后将观测结果回传到中心节点，由中心节点再进行目标跟踪和节点调度.由于区域中有障碍物阻挡，或目标移动具有趋向性，目标的状态转移概率在不同的位置是不同且未知的.假设不同目标在该区域中的运动模型服从同一分布，且状态转移符合一阶马尔可夫性质，可以把目标移动过程建模为隐马尔可夫模型.本节是将监控区域中的传感器完全开启，获得一定长度的观测序列后，根据观测序列估计区域中目标的运动模型，即状态转移矩阵，然后将该运动模型应用于下一节的节点调度中.

1.1 隐马尔可夫模型(HMM)建模

隐马尔可夫模型可用于由状态不可直接观测的马尔可夫链产生的随机观测序列的建模.针对本文场景，隐马尔可夫模型建模如下.

1) 系统状态

系统状态S包含了目标的位置和速度.由于连续状态不便处理，便对状态空间做网格化处理，将目标状态的各个分量在取值范围内等间隔划分，监控区域外的所有位置合并为一个状态.设离散化后目标状态共N个，记为i=1,2,…,N.Sk表示目标在k时刻所在的状态，包含了目标的位置和速度：

基于以上系统状态的定义，根据文献[6，14-15]等，目标的状态转移满足1阶马尔可夫性质是符合实际物理场景的.若假设目标位置的移动满足一阶马尔可夫性质，则系统状态的定义只包含目标的位置，而不影响后续算法求解.

2) 观测模型

观测模型为电子与通信领域常见的接收信号强度指示(Received Signal Strength Indicator, RSSI)定位模型[20-21]，传感器观测由目标辐射的能量信号的强度.假设观测到的能量信号强度随目标与传感器间距离的λ次方(通常λ≥2)成反比，于是，观测模型可以写作：

(1)

Z=[z1,z2,…,zM]T，

其中zm(m=1,2,…,M)表示第m个传感器采集的观测，k时刻的观测矢量可以表示为Zk=[zk,1,zk,2,…,zk,M]T.

本文传感器观测模型使用RSSI模型建模，计算观测概率.当环境中的障碍物对信号进行反射和遮挡导致信道中产生多径、遮挡等干扰时，可以使用其他的观测模型对无线通信信道进行描述，较为典型的模型有瑞利衰落模型[22]和莱斯衰落模型[23].本文算法并不局限于RSSI模型，适用于所有能够给出观测概率分布的观测模型.

1.2 状态转移模型估计

将目标的真实状态序列记作S=(S1,S2,…,ST)，则概率分布P(Z|Φ)可以视为含有隐变量S的概率模型：

(2)

(3)

其中Φ(n)是状态转移矩阵在n时刻的估计值，Baum-Welch算法通过极大化q(Φ,Φ(n))，不断更新对Φ的估计.由于本文观测方程已知，在求解过程中，需要根据本文观测方程，计算目标真实状态处于Sk时，得到观测Zk的似然概率分布P(Zk|Sk).假设不同传感器的观测噪声之间相互条件独立，可得：

(4)

其中I(zk,m)为示性函数，当传感器m的相对接收强度大于阈值时，示性函数值为1，表示该传感器采集的观测可以参与概率计算.示性函数的具体形式为：

(5)

根据式(1)，有

(6)

(7)

将式(7)代入式(4)，即可求得似然概率分布P(Zk|Sk).根据似然概率分布，也称为观测概率分布，可以计算出隐马尔可夫模型的前向概率αt(i)=P(Z1,Z2,…,Zt,St=i|Φ)和后向概率βt(i)=P(Zt+1,Zt+2,…,ZT|St=i,Φ).

在Baum-Welch算法中，为了根据式(3)更新对转移矩阵Φ的估计，定义Γt(i)=P(St=i|Z,Φ)，可得：

(8)

定义ξt(i,j)=P(St=i,St+1=j|Z,Φ)，可得：

(9)

由文献[17]和[18]，将式(3)展开后应用拉格朗日乘子法，状态转移矩阵的更新公式为：

(10)

定义b0(S)表示目标处于状态S的先验概率分布，更新公式为：

(11)

迭代至收敛后，即可求得区域中目标状态转移矩阵的估计.算法过程如下所示：

输入： 观测序列Z=(Z1,Z2,…,ZT)

输出： 状态转移矩阵Φ

1： 初始化Φ(0)

2：forn=1,2,…,do

7：end

2 节点调度算法

节点调度算法在每一时刻根据传感器回传的观测更新对目标状态的估计，综合考虑了跟踪精度与能量消耗，并动态选取传感器子集参与观测.这里需要解决两个方面的问题： 1) 如何更新目标状态的估计，跟踪目标；2) 如何根据目标状态的估计采取相应的节点调度动作.

2.1 POMDP建模

一个POMDP模型由状态集S、动作集A、观测集Z、状态转移模型Φ、置信状态b、瞬时代价L组成.置信状态b表示基于历史动作和观测序列得到的目标状态的后验分布，k时刻置信状态记作bk=P(Sk|Z1∶k,A0∶k-1).在k时刻可根据Φ、Zk和bk-1通过贝叶斯滤波求得置信状态bk，然后根据bk采取决策Ak并获得瞬时代价Lk.POMDP的目标是在每个时刻根据bk采取合适的动作Ak，使得整个过程的瞬时代价累积值最小.对于本文场景，状态S、观测Z的建模如1.1节，状态转移模型Φ由1.2节算法求得.其余变量建模如下：

动作A表示中心节点对传感器网络中的观测节点发出开启或关闭的指令：

A=[a1,a2,…,aM]Tam∈{0,1}，

其中：M为传感器网络中节点的个数;am∈{0,1}表示关闭/打开第m个传感器.

2) 瞬时代价函数

瞬时代价函数衡量目标在状态转移过程中每一步所产生的瞬时代价.瞬时代价包括两个方面： 跟踪误差和传感器的能量消耗.使用常数α权衡跟踪误差和传感器功耗对决策影响的重要程度，于是代价函数可以写作：

(12)

算法的目标是找到最优策略，即一个置信状态到动作的映射π.由最优策略π，可以根据每一时刻的置信状态b采取动作A，使得在整个跟踪过程中，目标转移的每一步累积的总代价的期望最小.k时刻累积损失的期望U可记作：

(13)

式(13)中：L(bk,Ak)表示在置信状态bk下采取动作Ak所产生的瞬时代价，E(U(bk+1,π)|bk,Ak)表示采取动作Ak后未来代价的期望.0≤β<1为递减因子，使累积损失函数有界，用来权衡瞬时代价和未来代价.定义Q(bk,A)表示置信状态bk时采取动作A，未来采取最优策略时的总期望代价，称为Q-value，于是有：

1.从社会经济发展的角度来看待教育供给侧结构性改革的必然性。以殷宝庆为代表的一批学者认为，教育的供给侧结构性改革是新时代下、新常态下的必然要求［3］。提升社会经济总量水平、优化经济结构、促进社会经济产出的质量和数量等都需要一批高职业素养的产业工人作为支撑。在整个经济发展过程中，随着生产力水平的不断提升，必然导致结构性失业的产生，进而影响经济发展并导致因失业等引起的社会不稳定情况。教育的供给体系对解决当前经济结构转型升级中高技能人才的需求起着重要的不可或缺的供给作用。

Q(bk,A)=L(bk,A)+βE(V*(bk+1)|bk,A)，

(14)

其中V*(bk)表示置信状态为bk时采取最优策略所能达到的最小代价的期望.因此在置信状态为bk时，只需计算每个动作A对应的Q-value，选择Q-value最小的动作作为当前决策即可.然而，Q-value的精确求解十分困难，计算复杂度很高，往往采取近似求解的手段.

2.2 求解当前时刻瞬时代价

根据Baum-Welch算法最大化观测序列的期望后，求得了状态转移矩阵Φ.在置信状态为bk时，采取动作Ak，得到观测Zk+1，则bk+1可由贝叶斯滤波(Bayesian Filter)[24]求得：

bk+1(Sk+1)=P(Sk+1|Zk+1,Ak,bk)=

γP(Zk+1|Sk+1,Ak,bk)P(Sk+1|Ak,bk)=

(15)

其中：γ为归一化因子；bk(Sk)表示置信状态为bk时，目标真实状态处于Sk的概率；P(Sk+1|Sk)根据状态转移矩阵Φ可得；P(Zk+1|Sk+1,Ak)根据式(4)可得.基于式(15)，能够迭代计算跟踪过程中置信状态的迁移.于是，可以计算置信状态bk时采取动作Ak瞬时代价：

(16)

(17)

2.3 基于QMDP算法求解未来代价

精确求解未来损失E(V*(bk+1)|bk,A)是十分困难的，由于置信状态是取值连续的后验分布，因此置信状态可能的转移路径有无穷多种.当代价函数关于置信状态是线性函数时，可以使用一些近似算法[25]，例如PBVI、PEMA、Perseus等启发式算法，但是这些算法不适用于本文中代价函数非线性的情况.

(18)

将式(18)代入式(14)，此时Q-value可以写作：

(19)

求解未来代价后，根据式(19)，可以对每一个动作A计算出置信状态为bk时，采取该动作对应的Q-value的近似值.此时，可以选择Q-value最小的动作作为当前的节点调度策略.当传感器网络中节点较多时，动作集中A的选择随着节点数呈指数增长.为了进一步降低计算量，可以先固定传感器子集中的节点数，然后逐个增加或减少，选择优化的传感器子集.

算法过程如下所示：

输入： 置信状态bk

输出： 最优动作A

1：functionQMDP(bk)

3：forall control actionsAdo

4：bk+1←Bayesian_filter(bk,A)

6：endfor

8：endfunction.

3 仿真结果

仿真中，将M=20个不同观测精度的传感器随机分布在160m×120m的平面区域中，其中横坐标范围为[-80,80]，纵坐标范围为[0,120].观测方程中，目标的初始能量强度E0=1000，衰减指数λ=2.对状态进行离散化后，将观测范围内的所有状态记作Sin.观测范围外合并为1个状态Sout.使用传感器网络对区域中的目标转移过程进行一段时间的观测和记录后，获得了很多条不同目标在区域中的完整轨迹，一条完整轨迹记录了目标从观测范围外进入观测范围移动一段时间后离开的过程，即Sout→Sin→Sout.假设目标的转移概率只与监控区域本身有关，与目标无关，于是可将这些目标的运动轨迹拼接为一条完整轨迹Sout→Sin→Sout→…→Sin→Sout.根据拼接后的轨迹对区域中的转移概率进行估计，轨迹总长度记作T.

通过仿真验证HMM-QMDP算法的跟踪性能，使用长度为T=500000的观测序列对目标的状态转移概率进行估计后，目标跟踪结果如图3所示.可见，当目标在监控区域中随机移动时，HMM-QMDP算法可以在一定的误差范围内，实现对目标的实时跟踪.

图2 状态转移矩阵估计误差Fig.2 Estimating error of state transition matrix

图3 估计轨迹与目标真实轨迹比较Fig.3 Comparison between estimated and real trajectory

将本文节点调度算法与全部开启，最近点方法(Closest Point of Approach, CPA)[28]，CO-Rollout[15]等算法进行比较.全部开启的方法表示在所有时刻开启所有传感器用于目标跟踪，CPA表示在每个决策时间根据对目标位置的估计，选择离目标最近的m个传感器参与观测.CO-Rollout算法同样适用于观测方程与代价函数非线性的场景，将节点调度问题建模为POMDP并近似求解.对这些算法进行仿真比较，结果如图4所示，其中横坐标为用于模型估计的观测序列长度T，纵坐标为平均跟踪误差Δ.可见，随着模型估计的观测序列长度的增加，对区域中目标转移概率估计更加精确，各算法性能均有一定提升.其中本文的节点调度算法能够在每一时刻综合考虑短期和长期表现进行节点调度，跟踪误差更加接近全部开启时的跟踪误差.CO-Rollout算法采用蒙特卡洛模拟的方法评估动作优劣，近似未来代价时使用基策略而不是最优策略，跟踪误差略高于本文算法.CPA算法贪婪地选取离估计位置最近的传感器进行观测，没有考虑不同传感器观测误差、功耗的区别，以及当前决策对未来的影响，因此跟踪误差较本文算法更大.不过该算法实现简单，易于使用.

对综合考虑跟踪误差和传感器功耗的跟踪过程中的平均总代价进行仿真比较，结果如图5所示，其中横坐标为用于模型估计的观测序列长度T，纵坐标为平均总代价L.可见虽然全部开启的跟踪精度较高，但是能量开销很大，导致权衡了跟踪精度和能量开销的总代价很高.CO-Rollout算法使用基策略代替最优策略，对于Q-value近似精度不够高，因此总代价高于本文算法.CPA算法通过贪婪方法选择传感器子集，虽然跟踪不够精确，但是由于降低了能量开销，总代价低于全部开启的方法.本文节点调度算法每一时刻选择比CPA方法更优的传感器子集对目标进行观测，在较低能量开销的同时保证了不错的跟踪精度，因此总代价较全部开启方法和CPA方法更低.

图4 目标跟踪过程中的跟踪误差Fig.4 Tracking error during target tracking

图5 目标跟踪过程中的总代价Fig.5 Total cost during target tracking

综合图4和图5可见，当用于估计运动模型的观测序列长度T小于105时，跟踪误差和总代价呈现快速下降的趋势；当估计样本长度T大于105时，下降速度趋于缓慢.因此可以认为，当估计运动模型的观测序列长度T在105左右时，本文算法可以较为准确地对运动模型进行估计，为了权衡采集样本的代价和跟踪过程的收益，可以当样本长度在105左右时停止观测序列采集过程.同时，图2中状态转移矩阵的估计误差在与图4和图5大致相同的位置出现拐点，共同验证了以上结论.

4 结 语

本文将目标运动和传感器观测建模为隐马尔可夫模型，提出了HMM-QMDP算法，将无线传感器网络中未知目标运动模型的目标跟踪问题分解为运动模型估计和节点调度两个阶段.在运动模型估计阶段，采集足够的观测样本后应用Baum-Welch算法估计监控区域中的目标运动模型.仿真结果表明，随着观测样本的增多，估计的目标运动模型会越来越接近真实的运动模型.在节点调度阶段，将目标跟踪中的节点调度问题建模为部分可观测马尔可夫决策过程，综合考虑短期和长期代价，可以求得长期更优的节点调度策略.当估计的状态转移模型接近真实模型，学习到的运动模型先验知识更加准确时，无线传感器网络进行目标跟踪时可以具有更高的跟踪精度和更优的节点调度策略.

本文算法可以有效地解决无线传感器网络中运动模型未知情况下的目标跟踪问题.未来可以进一步考虑将运动模型估计和节点调度联合建模，应用强化学习算法，在节点调度进行目标跟踪的同时估计和更新区域中目标的状态转移概率.这样可以不需要预先打开所有传感器采集样本进行转移概率估计，并且能够在目标跟踪过程中不断地估计和逼近真实的转移概率.