无线传感器网络中能效优化的自适应节点选择算法*

杨 伊,范馨月,周 非,郭浩田

(重庆邮电大学通信与信息工程学院,重庆 400065)

无线传感器网络是一种能够感知各种物理现象的数字皮肤,其具有体积小、成本低廉、可大规模部署等优点,因此被广泛应用于军事和民用领域,其中多目标跟踪(Multi-Target Tracking,MTT)是基于无线传感器网络的研究热点。对于大规模密集型无线传感器网络,为了提高目标跟踪性能而采用多传感器节点协同工作,但不同的节点协作组提供的跟踪性能各异,当节点选择不恰当时,会增大定位误差,造成节点冗余。因此,为了在保持跟踪精度的同时有效地平衡网络节点剩余能量、延长网络寿命,设计一种能效优化、稳健的节点选择算法至关重要[1-2]。

近年来,对于传感器管理问题国内外学者提出了不同的解决方案。Shen等人[3]提出基于广义信息增益的多级传感器选择策略,推导出用于节点选择的广义信息滤波器。Liu等人[4]考虑在相关测量噪声和能量约束的条件下,通过凸松弛和贪婪算法来优化Fisher信息矩阵的逆矩阵的迹,该算法可有效地处理弱相关噪声的情况。然而基于信息熵的度量准则对于滤波误差的鲁棒性较差,并且计算复杂度高[5-6]。文献[7]以条件后验克拉美罗下界(Posterior Cramer-Rao Lower Bound,PCRLB)为节点选择标准,将传感器选择问题表述为稀疏选择向量的设计,但该算法存在只能获取局部信息、计算复杂度较高等问题。文献[8]提出利用Mahalanobis距离选取传感器节点并最大限度地减少目标后验状态的不确定性,该算法计算复杂度较低,可快速有效地聚类无线传感器网络中的传感器节点,但并未考虑不同传感器节点之间相对几何位置的影响。

现存的多目标跟踪文献中提出的传感器调度方案大多在计算复杂度与跟踪精度之间进行权衡,并未考虑在跟踪精度和平衡节点剩余能量之间进行折衷。文献[9]针对传感器网络中的机动目标,提出一种能量平衡的多传感器协同调度方案。该算法可根据预测协方差矩阵自适应地调整目标跟踪的采样间隔,同时基于预测机制的聚类方式可有效地检测目标、平衡网络能耗。Cai等人[10]提出用于多目标跟踪的传感器动态选择算法(Dynamic Cluster Member Selection,DCMS),该算法充分考虑网络能量消耗和跟踪精度构造出综合性能指标函数,该模型可在一定程度上衡量无线传感器网络跟踪性能。但该算法并未考虑单个节点的能量消耗、剩余能量以及所选节点测量信息对目标定位的贡献度。

本文主要着眼于多目标跟踪节点选择算法的研究,综合考虑目标跟踪精度以及传感器节点的剩余能量,提出了一种能效优化的自适应节点选择算法,其主要贡献有:①利用面积和原理来解决Mahalanobis距离选取传感器节点时存在共线的问题;②分析候选传感器节点的剩余能量以及能量消耗,利用模糊逻辑模(Fuzzy Logic,FL)来实时计算传感器节点的“角色概率”;③利用扩展卡尔曼滤波器(Extend Kalman Filter,EKF)产生的预测状态构建误差椭圆,同时结合启发式遗传算法(Genetic Algorithm,GA)进行优化。

1 节点选择问题描述

假设在一个二维平面监测区域存在N个移动目标,区域内随机部署了M个静态传感器,考虑跟踪的实时性以及传感器节点的存储、计算能力限制,假设同一时刻每个传感器只能跟踪单个目标。

1.1 节点选择模型

当目标在监测区域内不断运动时,需要动态地选择不同节点协作组进行目标跟踪。因此节点选择问题就可以描述为,设计一种能够有效衡量网络能效的节点选择模型,通过选择性激活不同传感器节点来优化网络能效模型。由此看出节点选择的核心问题是节点选择优化模型的建立,并采用高效的优化方式求解模型[11]。MTT传感器节点选择动态闭环反馈结构如图1所示。

图1 目标跟踪闭环反馈结构

1.2 节点选择算法描述

考虑到传感器网络能量、带宽和信息处理能力等限制,通常不可能采用同一组节点跟踪多个移动目标,每个传感器节点不仅需要决定是否感知目标,还需要决定感知的目标,因此MTT的传感器节点选择具有挑战性。

①传统解决方案为了提高目标跟踪精度,通常采用基于复杂度高的PCRLB或者条件PCRLB节点选择模型,因此导致跟踪实时性不高。与此同时,采用多传感器节点协同工作,应充分考虑传感器节点间相对空间位置、测量信息相关性,否则将会引起节点冗余。基于此,本文设计了信息效用精度模型J1来衡量节点对目标的定位贡献度,该模型能有效地描述节点间几何位置对定位精度的影响,以及节点的观测信息量,并且复杂度较低。

②大多数的节点选择模型的建立只考虑跟踪精度,或者只分析协作组整体能量消耗,未考虑单个传感器节点剩余能量对整个传感器网络的影响。为达到延长网络使用寿命的目的,本文考虑如何进行能耗平衡,使得各节点剩余能量分布较为均匀,因此建立了能量平衡概率模型J2。

③为了能够提升无线传感器网络的整体性能,本文提出自适应节点选择性能优化模型。通过权重调节的方式来同时优化信息效用精度模型J1和能量平衡概率模型J2,即:

J=α1J1+α2J2,α1+α2=1

(1)

式中:α1,α2分别表示J1,J2的权重,其大小可根据应用要求的不同进行调整。对于优化方式,获取全局最优解最直接的方式就是穷举搜索,这将会导致高组合复杂度和繁重的通信负载。本文采用一种新的优化方式,即首先基于扩展卡尔曼滤波器[12]产生预测协方差矩阵,据此构建3σ误差椭圆[13]来确定候选节点集合,从而可以有效地缩小搜索空间;然后根据候选节点集合产生GA的初始种群,并利用GA可获得全局最优解的特性,可以快速搜索得到最优解。

2 节点选择性能优化模型

为了利用传感器网络有限的资源进行多目标跟踪,在保证一定跟踪精度的同时更好地平衡网络中节点的剩余能量。本文在现有传感器节点选择算法基础上做出改进,设计综合优化指标,提出一种自适应节点选择性能优化模型。

2.1 信息效用精度模型

假设各节点观测独立并给定至k-1时刻累积测量,条件PCRLB提供了基于观测量估计目标j状态的均方差下限[14]:

(2)

(3)

(4)

(5)

式中:Δ为二阶导数算子,由式(4)可得观测信息为各个传感器节点测量贡献之和,增加测量节点数量能更大程度减小目标状态的不确定性。

大多数情况下直接计算条件FIM会涉及高维积分,计算复杂度较高。在目标跟踪应用中,Mahalanobis距离计算简单,从几何上描述了均值位置与传感器节点间的位置矢量和目标协方差矩阵特征向量之间的相关性[8],如式(6)所示:

(6)

式中:p表示传感器位置坐标矢量;μ,Σ分别为目标位置均值和协方差矩阵。

在目标的先验位置协方差区域内,存在两个传感器与目标均值位置间的欧式距离相同,即d1=d2,但是两者与协方差椭圆长轴的角度不同,即θ1>θ2,那么

M1

(7)

(8)

其中M1和M2分别表示两个传感器的Mahalanobis距离,P+表示目标的后验协方差矩阵,因此较小的Mahalanobis距离可以选择测量信息量更大的距离传感器,即选择靠近不确定性椭圆长轴的节点,但是该度量准则并未考虑各节点之间的几何关系。

不同几何位置关系的传感器集合能提供不同的费雪尔信息量,假设目标位置为非随机量,则利用观测获取的FIM为:

(9)

式中:X=[∂xjz1…∂xjzm],Υ=[∂yjz1…∂yjzm],θ是X与Υ的夹角,利用D-优化准则有:

(10)

(11)

(12)

(13)

考虑到传感器节点随机分布的情况,上述条件很难满足。因此,提出用面积和原理来改进Mahalanobis距离节点选择算法,本文以选择三个传感器节点为例,如图2。

图2 节点与目标相对位置

当目标处于三角形ABC内时,△ABC的面积等于△APC、△BPC及△ABP面积之和,即:

ε=S△ABC-(S△ABP+S△APC+S△BPC)=0

(14)

文献[16]验证当目标不处于三角形内时,选取一定节点间隔内的传感器也可取得较好的定位效果,即可以通过减小ε来保证一定的定位精度。因此,k时刻节点选择信息效用精度模型为:

(15)

式中:Mi(k)为第i个传感器的Mahalanobis距离,ε(k)表示各传感器构成的节点间隔。

2.2 能量平衡概率模型

在同时考虑节点的剩余能量以及参与目标跟踪时的能量消耗时,这两个因素可能存在相互冲突的情况,并且与网络性能呈非线性关系。FL具有处理数据冲突情况和非线性问题的能力,因此利用FL在每个采样步长内计算该节点参与跟踪的“角色概率”。图3为FIS输出曲面,从该曲面可以看出节点实时状态对其成为任务节点或休眠节点概率的影响,随着剩余能量增加和能耗减小,其相应的概率便会增加。

图3 FIS输出曲面

模糊推理系统(Fuzzy Inference System,FIS)包含模糊化、模糊规则库、模糊推理方法及去模糊化四个功能模块[17]。本文采用五个模糊集来对输入和输出进行模糊化,用三角隶属度函数表示模糊集合非常低、低、中、高、非常高,该函数定义了将每个输入或输出点映射到0到1之间的隶属度,如式(16)所示:

(16)

式中:a取值为0,0,0.25,0.5,0.75,b取值为0,0.25,0.5,0.75,1,c取值为0.25,0.5,0.75,1,1。为了计算节点的“角色概率”,需要分析节点的能量消耗情况。通常在每个采样步长内节点能耗主要由四部分组成:①从候选节点集合选取任务节点;②任务节点感知目标;③任务节点和头结点之间的信息交换;④当前头结点与下一任务集群间的信息交换。如从节点sj传送bbits数据到节点si的能耗为:

(17)

式中:et,ed主要取决于传感器的发射机特性,rij为节点i和j的距离,αc取决于信道特征。

当输入节点能量消耗和剩余能量清晰值触发推理系统时,采用Mamdani推理并行处理多条规则。利用模糊推理系统的优势可以合理地综合节点能耗和剩余能量两个指标,得到节点的“角色概率”。为了达到平衡网络整体能量分布的目的,本文采用标准差来描述整体的概率分布情况,因此在上述得到的概率基础上构建能量平衡概率模型为:

J2(k)=std(pCM,pS), CM=1,…,Nm;S=1,…,NS

(18)

式中:pCM,pS,Nm,Ns分别表示任务节点、睡眠节点的概率以及数量,std(·)表示标准差函数。较小的标准差表明整体概率波动小,在此标准下选择的节点能量分布更均匀。

本文所提改进算法流程如图4所示。

图4 本文算法流程图

3 仿真分析

3.1 性能指标和仿真环境设置

本节主要从跟踪误差、节点剩余能量分布来验证本文所提算法的有效性。跟踪误差为:

(19)

本文采用主频3.70 GHz的PC机进行MATLAB仿真。无线传感器网络设置为100 m×100 m的正方形区域,随机部署500个传感器节点,每个节点的初始能量均为1 J。目标采用CA模型[18],数目为2,运动模型采样间隔T=1 s,初始协方差矩阵均为P0|0=diag[10 10 1 1 0.1 0.1],系统观测方程为:

(20)

表1 GA参数

3.2 仿真结果分析

图5为本文所提算法的目标跟踪轨迹图,*为目标的估计位置,□为目标的实际位置,图中只显示了跟踪目标1所构建的误差椭圆。从图中可以直观地看出,两个目标的位置误差均较小,跟踪效果较好。

图6为目标1的平均跟踪误差。从图6中三条曲线可以看出,当基于能量平衡指标时,为了使节点剩余能量分布更均匀,所选传感器节点会远离目标,使得某些信息效用更大的节点不会被重复选择,因此该曲线波动最大,而基于信息效用指标的情况正好相反。当采用综合优化指标时,也即本文提出的自适应节点选择性能优化模型时,目标的跟踪曲线较为平稳。因为该指标可以根据网络的实时情况去调整,当节点的工作节点概率较小、但信息效用较大时,该节点将不会充当任务节点。因此目标1的跟踪误差总体较为平稳,并且略大于基于信息效用指标的跟踪误差。图7为目标2的平均跟踪误差,从图中三条曲线也可以得出与目标1跟踪结果相同的结论。

图6 目标1平均位置误差

图7 目标2平均位置误差

表2为采样时刻t=30 s时任务节点的剩余能量。表中9、37、497号节点跟踪目标1,347、112、328号节点跟踪目标2。

表2 任务节点剩余

从表2中可以看出,基于综合优化指标所选的节点与另两个指标所选的节点有重合部分,例如第497号节点,位置坐标为(52.130 4,87.698 6),其Mahalanobis距离为2.541 1,第356号节点,位置坐标为(47.703 9,82.923 9),其Mahalanobis距离为13.734 3。因此,基于本文提出的优化模型,则会选择497号节点。本文所提算法在跟踪过程中不会重复选取能量低、但定位贡献度高的节点,也不会选取能量高、定位贡献度低的节点。由表中最后一列的标准差可以看出,基于综合优化指标所产生的所有节点剩余能量的标准差最小。

图8为在基于三种不同指标下,无线传感器网络中所有节点的剩余能量标准差。从图中可以看出,在目标跟踪前期,网络中节点的剩余能量标准差均呈上升趋势。分析其原因为初始时刻误差椭圆搜索区域较大,参与的候选节点数量增多,因此曲线上升。在跟踪的中后期,如图5目标轨迹跟踪图所示,随着目标后验状态的位置协方差矩阵的减小,误差椭圆面积相应减小,因此候选节点数量减少,曲线上升减缓。并且基于综合优化指标的剩余能量标准差优于其他两个指标,这与表2得出的结论也一致。

图8 节点剩余能量标准差

4 结论

本文研究了无线传感器网络中多目标跟踪的节点选择问题。通过构建误差椭圆确定候选节点集合,可以有效地防止目标丢失;运用面积和原理来改善所选传感器节点共线的情况,与此同时采用Mahalanobis距离来确定节点的定位贡献度;采用FL来确定各个节点参与跟踪过程的概率,通过权重调节的方式来同时优化两个节点选择模型。实验仿真表明,本文所提算法能够有效地在跟踪精度和网络寿命之间进行折衷选择,有效地选取最佳节点集合,实现网络的能效优化。在未来的研究工作中,主要考虑激活节点个数与网络跟踪性能的关系,灵活改变激活节点个数。