无线传感网络因其采用多个传感器节点能够不间断地完成数据采集、事件检测、事件标识、位置监测和节点控制,而引起了广大学者的广泛关注,其应用范围包括军事领域、智能交通、辅助农业生产、生态环境监测和预报、基础设施状态监测与医疗卫生等。无线传感网[1](wireless sensor networks, WSN)信号处理中,目标精确定位是一个基本而又极具挑战性的问题,对于由WSN提供的许多服务来说都是非常关键的,因为没有位置信息,就不知道收集的数据与环境位置的对应关系,从而使得收集的数据毫无意义。针对无线传感器的定位问题,常规的算法有基于信号强度(received signal strength, RSS)定位[2]、测向交叉定位(angle of arrival, AOA)定位[3]、波达时间差(time difference of arrival, TDOA)定位[4]。与其他常规方法相比,基于RSS定位算法因其不需要额外的硬件支持,系统构建成本低,使得该类方法应用较广。在WSN中,大多数传感器都是功率受限的,因为它们配备了小型电池,尤其是在恶劣的环境下,这些电池很难或不可能被替换。在多目标定位的应用中,由于无线通信能耗巨大,导致传感器节点板载能量消耗迅速。因此,如何优化WSN能耗,提高其生存周期,成为WSN的研究热点方向。
压缩感知技术(compressed sensing, CS)的发展为设计节能的WSN提供了新的思路。CS是一种有效的稀疏信号采集新方式。稀疏性是诸多信号(包括音频信号、视频信号和雷达、声呐信号)中显示的低维结构之一。当系数向量在已知正交基中只包含几个非零元素,则称信号是稀疏的。在信号处理和逼近理论中,稀疏性一直被用于诸如压缩、去噪、模型选择和图像处理等[5]任务。在WSN定位问题中,由于目标数目通常是有限的,因此可以应用压缩感知方法以更少的样本实现定位。近年来,提出了许多基于压缩感知的定位方法[6-9]。在这些方法中,通常将二维空间分为离散网格,假设所有的目标都精确地落在预定义的网格上,通过对应于网格的过冗余字典中原子系数来表示其对应测量值,这些系数对应了目标的位置。最终通过重构的稀疏表示系数来实现目标的精确定位。从而将定位问题转化为稀疏重构问题。
在稀疏重构方法中,贪婪稀疏近似算法通常是计算量小的一类算法,适用于实时和大规模稀疏逼近应用场合。最基本的贪婪算法称为匹配追踪(matching pursuit, MP)算法[10],它通过迭代将字典中最相关元素(称为原子)添加到所选原子集来构建信号的稀疏表示。MP的缺点是该算法找到的稀疏表示并非所选原子的最佳表示,该算法可能会在其后的迭代计算过程中重新选择已经选择的原子,降低了算法的收敛速度。文献[11-12]中提出正交匹配追踪(orthogonal matching pursuit, OMP)算法以牺牲计算量为代价来补偿这些问题。为解决计算OMP的计算复杂度问题,提出了一些改进OMP算法,如正则化OMP(regularized orthogonal matching pursuit, ROMP)[13-14],该算法通过正则化每次迭代所选择的若干列向量,使得算法收敛较快,但同时降低了重构精度。另一种分段OMP(stagewise orthogonal matching pursuit, StOMP)[15-16]通过一次迭代搜索选择多个原子,在计算时可不用知道稀疏性参数K,其原子选择门限准则适用于测量矩阵为随机矩阵,该方法虽然在计算速度上有些提升,但其存在重构精度差,稳定性不高,使得其应用受限。
上述OMP算法中都存在矩阵求逆问题,而矩阵求逆又随着其维度增加运算复杂度大为增加,鉴于此,本文研究了WSN中基于网格的RSS多目标定位系统,使用列满秩矩阵QR分解思想对所选原子矩阵间接求逆,从而实现对多目标快速定位。该定位方法首先利用不同位置目标相对于传感器节点具有不同的能量这一特点,将传感器网络中的多目标定位问题转化为信号的稀疏表示问题,然后通过快速正交匹配追踪算法来估计目标的位置和能量。通过数值仿真验证,在不同传感器数目,不同网格数以及目标个数不同的情况下的估计精度和计算效率,结果表明,相较于传统的OMP算法,快速正交匹配追踪算法在不损失目标定位精度的同时,能够降低计算量,提高运算效率。
1 问题描述与系统模型考虑无线传感器网络覆盖的二维正方形区域中的多目标定位问题。这些目标装备有定期广播信号的无线信号发射装置。区域内部署一定数量传感器来接收这些目标发射的信号,所有目标信号将会叠加在接收传感器上。为了解决这一定位问题,将每次RSS测量建模为来自所有目标的接收信号强度之和,这个模型称为信号叠加模型。
假设传感器和目标位于位置{tm}m=1M和{τk}k=1K, 其中M和K分别表示传感器和目标的数量, tm和τk分别表示第m个传感器和第k个目标的位置。根据信号叠加模型, 第m个传感器的RSS测量值可表示为
(1) |
式中: ak表示第k个目标的发射功率;εm表示第m个传感器的测量噪声。f(t, τ)为能量衰减函数, 该衰减函数模型参照文献[15]给出如下
(2) |
式中: d=‖τ-t‖2为目标与接收传感器间的距离; d0为参考距离; γ为衰减系数, 由环境决定, 典型取值范围为2~5之间。
为了简单起见, 假设所有目标的发射功率都是已知的。目标是从混有噪声的测量向量z=[z1, z2, …, zM]T估计多个目标的数目K和位置Γ={τk}k=1K。为了便于书写, 将信号叠加模型可表示为向量矩阵形式
(3) |
式中,s=[s1, s2, …, sM], ε=[ε1, ε2, …, εM]T。
由于观测域内的目标数量有限, 定位得益于压缩感知技术使得测量数量可以大大减少。为了实现压缩感知, 将正方形区域划分成等间距网格, 如图 1所示, 这些网格中的点称为网格点。这些网格点从1到N编号, 从下往上,第1行格点序号为1, 2…n, 第n行为n2-n+1, n2-n+2, …, N, 网格点的位置坐标由x=[x1, x2, …, xN]T和y=[y1, y2, …, yN]T来表示; 为表示方便, 用θi=(xi, yi), i=1, …N表示第i个网格点坐标。且这些网格点位置构成的向量Θ={θi}i=1N是预先已知的。
定义M维向量
(4) |
作为由第i个格点形成的原子, 其中f(tm, θi)表示第m个传感器从第i个格点处目标获得的RSS值。因此, 形成的稀疏字典可以写为
(5) |
传统的基于CS的定位方法假设所有的目标精确落在固定网格上, 则测量矢量可以表示为
(6) |
式中,w=[w1, w2, …, wN]T表示通过稀疏字典D(Θ)中的测量向量z形成的表示系数。如果第k个目标落在第i个网格点上, 则它的元素wi=ak; 否则wi=0。由于目标的数量K远小于网格点的数量N, 表示系数w是完全稀疏的。因此, 该定位问题成为稀疏信号恢复问题。一旦确定了稀疏信号, 目标的位置就在与表示系数向量中非零元素对应的网格点上。
2 基于稀疏表示定位对于(6)中的问题, z为感知信号矢量, 稀疏字典D(Θ)可通过(5)式求得, 该问题的线性稀疏逼近就是要找到一个最稀疏解向量w∈RN可精确逼近z, 即使得w中有最少的非零元素个数。该问题求解可归结为求解如下数学问题
(7) |
该问题的求解采用标准的OMP方法有较高的逼近精度, 但标准OMP算法在每次迭代过程中感知信号都要正交投影到所选支持集上, 投影过程为
(8) |
式中,Ds与ws分别是子字典与对应支持集上的系数向量。由于残差信号在减掉当前原子的贡献之后与所选原子正交, 因此后面迭代过程中不再选择这些原子。
在稀疏重构问题方法中, 贪婪类稀疏近似算法因其计算量小, 具有优良的重构效率, 因而受到广泛关注。而正交匹配追踪算法是贪婪类算法中具有优良的稀疏信号重构的典型方法, 本文以正交匹配追踪算法为基本重构算法来完成无线传感器网络中目标的定位。首先介绍正交匹配追踪算法。
2.1 正交匹配追踪算法匹配追踪算法是一种连续迭代过程, 每次迭代中会在原子字典D中寻找与残差信号相关性最大的原子。随着分解和迭代深入, 残差信号能量逐渐降低, 整个分解过程能量守恒。若分解采用的原子字典是过完备的, 在不限制分解迭代次数情况下, 分解得到的原子能量之和可以以任意精度逼近原始信号。
影响匹配追踪算法收敛速度的2个重要因素是过匹配现象和非正交投影。这2个因素的出现归因于过完备字典的冗余性和匹配追踪算法的贪婪性。匹配追踪算法的一个明显特点是每次迭代均选取原子字典中与残差信号最匹配的原子来逼近残差信号, 这种方法追求每次迭代后的残差信号能量下降最大。假设已经得到一组匹配原子, 对残差信号继续用该方法进行匹配将会得到和新残差信号最匹配的原子。匹配追踪算法每次迭代过程中得到新的原子和原支持集所张成的空间并不正交, 因而会引入冗余分量, 在随后的迭代追踪和补偿这些引入的分量需要引入更多的原子而增加计算复杂度。正交匹配追踪算法通过修正已经匹配得到的原子使得支撑集中原子形成一组正交基, 下次得到的原子属于该正交基张成空间的补空间。正交匹配追踪算法克服了基本匹配追踪算法的非正交投影和过匹配现象。
算法1 标准正交匹配追踪 |
输入:z, K, D 输出: w 初始化 s=Ø, k=0, w=0, r0=z 当k < K & max(DTrk)>C进入循环 (ζ, t)←max(DTrk) s←s∪t ws←argminθ‖z-Dsws‖ rk+1←z-Dsws k=k+1 循环结束 |
在匹配追踪算法迭代过程中, 每次选择的最佳匹配原子sk与前面已经匹配到的原子构成的支撑集元素{sk}0≤k≤K并不一定满足正交关系。正交匹配追踪算法中通过采用Gram-Schmidt正交化过程, 利用已得到的原子对迭代得到的新原子正交化。标准正交匹配算法如算法1所示。
2.2 快速正交匹配追踪在标准的OMP算法实现中, 每次迭代时需要求解最小二乘问题(8)。该式可以通过计算Ds的Moore-Penrose伪逆Dsϕ, 通过
为了降低计算复杂度, 提出了对所选子字典进行列满秩QR因子分解(见附录1)。设字典D中所选的k个原子的QR因子分解为
(9) |
子字典Dk列正交, 并且Rk是在其主对角线上具有正对角线元素的上三角矩阵。设在第k次迭代中, Dk的列是采用迭代次数进行排序, 即di(1≤i≤k)是第i个选择的原子。将(9)式代入(8)式可得
(10) |
由于Dk和Ψk列空间等价, 令ck=Rkwk, 则上式变为
(11) |
由QR分解知, Ψk为正交矩阵, 则有
(12) |
从而避免了矩阵的求逆问题, 使得可以快速求得
尽管如此, 在算法更新Ψk, Rk与Rk-1过程中, 随着迭代次数k的增加, 求Rk-1的计算代价会显著增加, 因此低复杂度OMP算法的关键在于如何高效地更新Ψk, Rk与Rk-1。
首先可以利用Gram-Schmidt正交化过程来更新Ψk。由于Dk+1的前k列具有QR分解ΨkRk, 只需要通过Gram-Schmidt过程来寻找Ψk+1的最后一列。在这种情况下, 有
(13) |
式中,
(14) |
式中,v=ΨkTdk+1, μ=‖qk+1‖2。
用同样的方法计算得到Rk-1后, 可用矩阵分块求逆可得到Rk+1-1更新公式如下
(15) |
对于中到大的数据维度k值, 此方法实现的OMP算法比标准伪逆实现更快。注意到该方法在中间迭代过程中不需要计算wk, 只需要在每次迭代时计算ck并在最后第k次迭代之后找到w。即w=Rk-1ck, 其中ck为c在第k次迭代的值。另外该算法在迭代过程中也无需计算Rk, 只需对Ψk与Rk-1进行更新。
算法2 基于QR分解的快速正交匹配跟踪算法 |
输入: z, K, D 输出: w 初始化 s=Ø, k=0, r0=z, Ψ0=[], R=[]p0={<r0, dn>}n=1, 2, …, N 当k < K 进入循环 循环结束 cK=ΨKTz w=RK-1cK |
基于网格化定位系统中, 目标可能位于区域内任意位置而不在网格中心。这种情况下, 重构信号w就不是一个1稀疏信号, 为近似稀疏信号, 存在少数的非零元素。为了提高定位精度, 有必要对w中这些非零元素所含目标信息进行处理。通常是采用质心算法[17], 设在第k个目标附近有J个格点对应的值wk(i)大于某一个门限λ, 将这些点组成集合可表示为
(16) |
式中,i与格点坐标(xi, yi)对应, 则第k个目标的位置估计值可通过计算集合sk的质心来估计
(17) |
式中,centroid表示计算点的质心。
2.3 运算复杂度分析标准OMP算法的在原子选择步骤计算复杂度为O(MN), 在选择到一个新的原子后计算残差过程中, 存在矩阵求逆运算。第k次迭代时就会存在对k×k阶矩阵求逆, 其计算复杂度至少为O(k3), 求残差的计算复杂度为O(Mk+Mk2+k3)。因此, 在忽略掉一些低复杂度运算后, 每次迭代总的计算复杂度为O(MN+Mk+Mk2+k3)。经过K次迭代后, 标准正交匹配追踪算法总计算量约为
基于QR分解的OMP算法与标准OMP具有显著不同的计算复杂性。算法中每次迭代中求最大相关原子计算复杂度与标准OMP相同, 即O(MN); 在更新Rk+1-1时计算复杂度为O(Mk); 在更新ψk+1与qk+1时计算复杂度O(M+Mk2)。K次迭代后, 忽略掉一些低复杂项后, 总的计算量约为(MN+M)K+
基于QR分解OMP算法在迭代过程中避免了直接对矩阵求逆, 使得算法的运算量大为降低。
3 仿真分析本节中, 验证正交匹配追踪, 基于矩阵求逆引理OMP[18], 提出的基于QR分解的快速OMP方法配合质心算法在传感器网络的目标定位性能和计算效率。
仿真中, 若没有特别说明时仿真条件均为:传感器覆盖范围为一个尺寸为100 m×100 m的二维定位区域, 目标的RSS叠加由区域内随机分布的M个传感器来采集; 稀疏表示算法中的网格区域均匀划分为10×10的网格。
为了不失一般性, 传感器接收信号的路径损耗模型的参数设置为:所有目标发射功率均为a0=100 mW, 参考距离为d0=1 m, 衰减系数γ=2, 并选择δ=10-8作为迭代的终止条件。多个目标的定位性能由平均误差(e)反映, 定义如下
(18) |
式中,(xk, yk)与(
在实际定位问题需要考虑测量噪声, 传感器接收信号的信噪比定义为:每个传感器的测量中施加一个加性高斯噪声N(0, σ2)。信噪比(RSN)定义如下
(19) |
式中,t表示M个传感器的RSS测量值。
3.1 无噪情况下定位性能对比首先考虑了一个理想的定位场景, 忽略传感器位置不确定性和测量噪声的影响。4个目标完全落在划分好的网格上。这些目标的真实位置分别为(20, 20), (40, 60), (60, 80)和(80, 40)。使用不同算法通过30个传感器来定位4个源。其中传感器随机分布在100 m×100 m的二维定位区域内。
图 2给出了在无噪情况下, 常规正交匹配追踪方法、基于矩阵逆定理的正交匹配追踪方法以及基于QR分解的正交匹配追踪方法在无噪情况下的表示系数以及位置估计结果。图 2a)中给出了稀疏表示系数与格点序号之间的关系。由第1节中稀疏表示模型知, 当第k个目标落在第i个网格点上时, 则表示wi=ak=a0, 仿真时设定功率为100 mW=0.1 W, 因此目标所在网格的表示系数为0.1, 没有目标的格点对应的表示系数为0。仿真时格点间距设定为10 m, 在100 m×100 m区域分成100个格子, 格点数就为11×11为121个。图 2b)中给出了真实位置与仿真位置关系图。从图中可以看出, 在无噪情况下基于QR分解的快速OMP与其他OMP算法有相同的表示系数与定位精度, 非零表示系数个数与目标个数相同, 对目标信号重构性能也比较理想。
3.2 传感器个数对于定位性能和计算效率的影响在本仿真试验中, 网格大小为5 m, 目标个数为4, 目标随机分布, 最终估计采用质心算法进行去偏差处理。图 3给出了目标数目, 网格大小一定情况下, 传感器个数与估计精度的关系, 图 4给出了传感器个数与计算速度的关系。
图 3表明, 基于QR分解的OMP算法与其他2种OMP算法相比定位精度不相上下, 在目标个数不变的情况下, 3种方法定位精度都随传感器数量的增加而定位误差变小。由图 4可知, 在计算性能方面, 随着传感器数目的增加计算时间越来越长, 其中常规OMP算法最耗时, 基于矩阵求逆引理OMP算法次之, 推荐的算法性能最优。
3.3 目标个数对于定位性能和计算效率的影响该仿真中, 传感器个数为25, 网格大小为5 m, 目标个数为从4个变化以2个目标为步进到10个目标。图 5给出了传感器个数, 网格大小一定情况下, 目标数目与估计精度的关系, 图 6给出了目标数目与计算时间的关系。
由图 5可以看到, 目标数目越多, 定位误差越大, 即随着稀疏度的变小定位误差变大, 3种算法定位精度变化趋势一致, 精度基本保持相同。图 6中可看到, 随着目标数的增多, 基于QR分解的OMP方法运算效率更有优势, 也说明了矩阵维度越大, 推荐的方法计算复杂度更低, 这也与前面运算复杂度分析的结论相符。
3.4 网格大小对于定位性能和计算效率的影响该仿真中, 传感器个数为25, 目标个数为4, 随机分布, 网格大小分别为2.5, 5, 10, 20。图 7给出了传感器个数, 目标数目一定情况下, 网格大小与估计精度的关系。图 8给出了网格大小与计算时间的关系。
通过图 7可看出, 在网格比较密集时, 3种方法精度接近, 随着网格变大, 推荐的方法定位精度更高, 这是由于推荐算法中采用了质心算法, 在目标不在格点上时能更准确地定位出目标位置。图 8中在网格划分比较密集时推荐的算法与基于矩阵求逆引理的算法计算时间接近, 标准OMP算法最耗时。
4 结论提出一种基于接收信号强度的基于QR分解快速正交匹配追踪的传感器网络多目标定位方法。该方法将无线传感网中基于RSS的多目标定位问题转换为稀疏重构问题, 通过列满秩矩阵QR分解矩阵求逆替代传统OMP方法中对矩阵直接求逆, 使得运算量大为降低, 从而降低无线传感网的能耗, 提高其生存周期。与传统的正交匹配追踪压缩感知重构方法相比, 仿真结果表明该方法并不损失定位精度, 再配合质心算法还能获得更优的定位精度, 运算效率受目标个数影响较大, 在典型稀疏无线传感网条件下有较好的计算效能。
附录1 满列秩矩阵QR分解
定理 若A∈Rm×n(m>n), 且A的秩为n(rank(A)=n), 则有Am×n=Qm×nRn×n, 其中Qm×n=[q1, q2, …, qn], q1, q2, …, qn为A的列向量张成空间span(A)上的一组标准正交基, Rn×n为对角线元素为正数的满秩上三角矩阵。
证明 令p1, p2, …, pn-1为一组由Gram-Schmidt正交得到的投影矢量, a1, a2, …, an为A的列向量, 定义
式中,k=1, 2…n, p0=0。
rik=qiTak, 其中i=1, 2, …k-1, k=1, 2…n
由Gram-Schmidt正交化可得
式中,k=2, …, n。
上式整理得到
式中,k=2, …, n。
令R为上三角矩阵
则QR乘积的第j列为
对于j=1, 2, …, n有
[1] | NAYAK P, DEVULAPALLI A. A Fuzzy Logic-Based Clustering Algorithm for WSN to Extend the Network Lifetime[J]. IEEE Sensors Journal, 2016, 16(1): 137-144. DOI:10.1109/JSEN.2015.2472970 |
[2] | TOMIC S, BEKO M, DINIS R. RSS-Based Localization in Wireless Sensor Networks Using Convex Relaxation:Noncooperative and Cooperative Schemes[J]. IEEE Trans on Vehicular Technology, 2015, 64(5): 2037-2050. DOI:10.1109/TVT.2014.2334397 |
[3] | TOMIC S, BEKO M, DINIS R. Distributed RSS-AoA Based Localization with Unknown Transmit Powers[J]. IEEE Wireless Communications Letters, 2016, 5(4): 392-395. DOI:10.1109/LWC.2016.2567394 |
[4] | LIU Y, GUO F, YANG L, et al. An Improved Algebraic Solution for TDOA Localization with Sensor Position Errors[J]. IEEE Communications Letters, 2015, 19(12): 2218-2221. DOI:10.1109/LCOMM.2015.2486769 |
[5] | ELDAR Y C, KUTYNIOK G. Compressed Sensing:Theory and Applications[M]. Cambridgeshire: Cambridge University Press, 2012. |
[6] | LIU L, CUI T, LV W. A Range-Free Multiple Target Localization Algorithm Using Compressive Sensing Theory in Wireless Sensor Networks[C]//2014 IEEE 11th International Conference on Mobile Ad Hoc and Sensor Systems, 2014: 690-695 |
[7] | WANG J, CHEN X, FANG D, et al. Transferring Compressive-Sensing-Based Device-Free Localization Across Target Diversity[J]. IEEE Trans on Industrial Electronics, 2015, 62(4): 2397-2409. DOI:10.1109/TIE.2014.2360140 |
[8] | XIE R, JIA X. Transmission-Efficient Clustering Method for Wireless Sensor Networks Using Compressive Sensing[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(3): 806-815. DOI:10.1109/TPDS.2013.90 |
[9] | LAGUNAS E, SHARMA S K, CHATZINOTAS S, et al. Compressive Sensing Based Target Counting and Localization Exploiting Joint Sparsity[C]//Proc IEEE Int Conf Acoust, Speech Signal Process, 2016: 3231-3235 |
[10] | TAO Q, JINXUN W, YAN Y. Matching Pursuits Among Shifted Cauchy Kernels in Higher-Dimensional Spaces[J]. Acta Mathematica Scientia, 2014, 34(3): 660-672. DOI:10.1016/S0252-9602(14)60038-2 |
[11] | YOU C, ROBINSON D, VIDAL R. Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016: 3918-3927 |
[12] | TROPP J A, GILBERT A C. Signal Recovery from Random Measurements via Orthogonal Matching Pursuit[J]. IEEE Trans on Information Theory, 2007, 53(12): 4655-4666. DOI:10.1109/TIT.2007.909108 |
[13] | DAVENPORT M A, WAKIN M B. Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property[J]. IEEE Trans on Information Theory, 2010, 56(9): 4395-4401. DOI:10.1109/TIT.2010.2054653 |
[14] | SAJJAD M, MEHMOOD I, BAIK S W. Sparse Coded Image Super-Resolution Using K-Svd Trained Dictionary Based on Regularized Orthogonal Matching Pursuit[J]. Bio-Medical Materials and Engineering, 2015, 26(suppl 1): S1399-S1407. |
[15] | LEE D. MIMO OFDM Channel Estimation via Block Stagewise Orthogonal Matching Pursuit[J]. IEEE Communications Letters, 2016, 20(10): 2115-2118. DOI:10.1109/LCOMM.2016.2594059 |
[16] | WU F, YANG K, SUN Q, et al. Stage-Wise Orthogonal Matching Pursuit for Estimation of Time Delay and Doppler Doubly Spreading of Underwater Acoustic Channels[J]. The Journal of the Acoustical Society of America, 2018, 144(3): 1736-1736. |
[17] | KAUR A, KUMAR P, GUPTA G P. A Weighted Centroid Localization Algorithm for Randomly Deployed Wireless Sensor Networks[J]. Journal of King Saud University-Computer and Information Sciences, 2019, 31(1): 82-91. DOI:10.1016/j.jksuci.2017.01.007 |
[18] | STURM B L, CHRISTENSEN M G. Comparison of Orthogonal Matching Pursuit Implementations[C]//2012 Proceedings of the 20th European Signal Processing Conference, 2012: 220-224 |