无线传感器网络中基于自适应网格的多目标定位算法

王天荆，李秀琴，白光伟，沈航

（南京工业大学计算机科学与技术学院，江苏 南京 211816）

1 引言

近年来，基于无线传感器网络（WSN, wireless sensor network）的多目标定位技术已被广泛应用于机器人导航、地理路由、公共安全、环境监测、车辆跟踪等多个领域[1-5]，其中，高精度、高效率的定位算法一直是研究热点之一。传统的多目标定位算法可分为基于测距和基于非测距两类，前者需要节点有测距功能，主要有基于到达时间[6]、基于到达时间差[7]等定位算法；后者通过网络的连通性实现多目标定位，主要有加权质心定位算法[8]、修正权值网格质心定位算法[9]等。上述算法虽简单易行，但需要额外的辅助设备，且定位精度易受到复杂环境下无线电波波动的干扰。为了不增加硬件设施成本，基于接收信号强度(RSS, received signal strength)的多目标定位技术根据传感器节点可以独立测量接收信号强度的特性，通过检测监测区域内RSS来确定目标位置。文献[10]在离线阶段使用核函数特征提取方法获得 RSS 信号特征，构成位置指纹空间；在线定位阶段采集在线位置指纹数据，利用改进的加权k近邻算法匹配位置指纹空间中的数据，估计待测目标位置。但是，基于位置指纹的定位技术需要对大量的数据进行测量、处理和存储，然而传感器节点的能量、内存和通信能力均受限。不同于RSS定位技术，文献[11]提出的语义目标定位算法通过节点间大量的信息交互来探知监测环境，再利用环境信息估计目标位置。这两类方法中大量信息的传递消耗了有限的网络资源，因此减少数据传输和资源消耗是多目标定位亟待解决的问题之一。

近年来，兴起的压缩感知（CS, compressive sensing）技术[12]为多目标定位带来了新的机遇。WSN中的多目标定位问题具有天然的稀疏性，因此可以利用CS理论大幅减少节点采样的数据量，减少资源消耗。文献[13]将WSN的监测区域离散成若干个网格，并依据CS理论将多目标定位问题转化成一个K-稀疏信号的重构问题，由sink节点利用l1最优化从观测向量中重构出目标位置。文献[14]以目标节点与锚节点连通度为观测值，运用最小化l1范数法，通过高计算量的梯度下降法求解目标位置。针对l1最优化重构算法计算复杂度高的问题，文献[15]利用贪婪匹配追踪（GMP, greedy matching pursuit）算法实现多目标定位，但该算法的定位误差需要进一步改善。文献[16]改进了GMP算法，提出使用贪婪匹配残差优化算法重构K-稀疏信号，提高了定位精度。基于贪婪法的定位算法虽计算复杂度低，但需要信号的稀疏度作为先验条件，即需要预知目标个数。然而，实际应用中节点不仅无法获知目标个数，而且无法确定满足CS重构条件所需的采样数据量。因此，如何确定最优观测次数以克服因采样数据量未知而导致的不充分采样或过度采样问题，是多目标定位的挑战之一。

通常，基于CS的定位方法用固定网格划分监测区域[14-17]。为了保证辨识出每个目标的位置，只能将网格划分得十分细小，这大大增加了最优化模型的规模及重构算法的计算复杂度，从而存在加大定位误差的风险。为了解决此问题，文献[17]提出了一种基于稀疏贝叶斯学习的网格自适应多源定位算法，该算法设计的自适应网格能使定位误差低于固定网格划分下定位误差的理论下界。文献[18]提出了一种两阶段的目标定位算法：在粗定位阶段利用l1最优化重构出目标的初始候选网格；在细定位阶段依次四分每个初始候选网格，在越来越小的子网格内确定目标的精确位置。上述定位算法虽解决了在大范围内以高计算代价估计目标位置的问题，但在细定位时依然要求所有节点传输感知数据至sink，这种集中式的定位方法易使节点因通信量大而过早失效，从而导致网络拓扑的不稳定性。根据目标在监测区域内的稀疏性，如何建立分布式的多目标定位方法是热点问题之一。

针对以上问题，本文提出了一种基于自适应网格的多目标定位算法，该算法分为2个阶段：在大尺度网格定位阶段，采用序贯压缩感知（SCS,sequential compressed sensing）原理选择最优观测次数，通过lp最优化重构出目标所在的初始网格位置；在小尺度网格定位阶段，根据CS重构要求自适应划分目标所在的初始网格，再次采用SCS原理选择最优观测次数，通过lp最优化确定目标在初始网格中的精确位置。本文主要贡献如下。

1) 基于大尺度网格的定位方法在监测区域内区分目标存在和不存在的子区域；基于小尺度网格的定位方法在目标存在的子区域估计目标的位置，使目标定位更有针对性和高效性。

2) 利用 SCS数据采集方法和lp最优化稀疏重构方法共同减少节点的观测数据量，从而大大降低网络资源开销。

3) 实验仿真结果表明，与传统的基于CS的多目标定位算法相比，在保证定位精度的同时，本文算法所需的观测次数大大减少，定位的时间开销显著降低。

2 相关背景及准备工作

2.1 压缩感知

CS技术可用远低于奈奎斯特采样率(Nyquist sampling frequency)的速率对K-稀疏信号进行采样，并利用如式(1)所示的l0最优化问题重构出K-稀疏信号*

x。

其中，观测矩阵P满足有限等距性质（RIP, restricted isometry property）[19]。正交匹配追踪算法（OMP, orthogonal matching pursuit）[20]、分段正交匹配追踪算法（StOMP, stagewise orthogonal matching pursuit）[21]等贪婪算法都可求解式(1)问题，但是它们均需要信号稀疏度作为先验条件，且重构误差较大。于是，文献[22]将l0最优化问题松弛为l1最优化问题，如式(2)所示。

式(2)所示的问题可由梯度投影法（GPM, gradient projection method）、基追踪算法（BP, basis pursuit）[23]、子空间追踪算法（SP, subspace pursuit）[24]、迭代收缩阈值法（ISTA, iterative shrinkage-thresholding algorithm）等求解，但易于收敛到次优稀疏解，且计算复杂度高。

2.2 CS定位问题描述

假设在WSN监测区域内随机部署了M个位置已知的传感器节点和K个位置未知的目标，则基于CS的多目标定位系统将此区域离散为N(N=n×n)个网格，并设每个目标只出现在某个网格的中心位置，如图1所示。

不妨定义K个目标的位置向量为x=(x1, … ,xN)，其中，若第j个网格存在目标，则xj=1，否则xj= 0 。根据强度-距离损耗模型[25]，第i个节点在理想情况下接收到第j个网格中目标发出的RSS值为其中，pt表示在参考距离d0处的接收信号强度，dij为第i个节点与第j个目标之间的欧式距离，路径衰减指数η一般为 2～5。监测区域内M个节点采用观测矩阵获得观测向量y=Px，并将之传输给sink；接收到y后，sink可以由观测信息重构出K-稀疏向量x*来估计目标的位置，因为x*中非零元素的位置对应着K个目标在N个网格中的位置。

图1 基于CS的多目标定位系统模型

传统的基于CS的定位方法主要利用l0最优化或l1最优化来重构目标位置，很少考虑利用lp(0 ＜p＜ 1 )最优化[26]完成定位任务；而lp范数对向量稀疏性的度量优于l0范数和l1范数，因此本文通过求解如式(4)所示的lp(0 ＜p＜ 1 )最优化问题实现多目标定位。

充分的观测数据量是求解问题式(4)的前提条件，然而在实际场景下，定位系统无法预知目标个数，即无法获知向量x的稀疏度，因此无法确定重构所需的观测次数。若观测次数过多，对提高重构精度的贡献有限，但增加了采样成本；若观测次数过少，则无法精确重构出*x。

2.3 基于SCS的最优采样

SCS技术克服了因观测数据量未知而导致的不充分或过度采样问题，其基本思想是在初始m个观测值上叠加T个观测值，使以的概率得到的重构误差满足式(5)。

于是，当重构误差的估计值Est(m,T)小于门限值τ时，停止接受新的观测值；否则，以T为步长，序贯增加观测次数直至Est(m,T)满足门限要求，获得最优观测向量m+STy。

3 基于自适应网格的多目标定位算法

由上述讨论可知监测区域的网格划分影响着式(4)所示问题的求解。若网格划分的尺度过小，则使式(4)所示问题中欠定线性方程组的规模急剧增加，从而大大增加重构算法的计算量，延长定位时间；若网格划分的尺度过大，则一个网格中可能存在多个目标，定位时容易出现目标丢失。由此，设置合理的网格尺度可提高定位的准确性、及时性及降低系统的计算复杂度。通常，网格尺度的划分依赖于目标的先验信息，但WSN无法获知这些信息。不过某些实际场景下多个目标会分别聚集在小区域内，如图2所示。于是，本文分别采用大尺度网格划分和小尺度网格划分这2个阶段实施多目标定位，具体过程如下。

图2 实际的多目标定位场景

3.1 大尺度网格定位

WSN启动多目标定位任务时，为了减少感知开销，首先用大尺度划分监测区域，以确定存在目标的子区域，如图3所示。假设面积为S=a0×a0的监测区域被划分为N0=n0×n0个初始网格, 第i(i∈{ 1,…,N0})个初始网格的状态向量定义为其中为初始网格的中心位置，或分别表示该初始网格中存在或不存在目标。根据SCS原理，在区域内随机选择m0+T0个节点进行目标感知，且将观测值传送给sink；sink计算重构误差的估计值 E st(m0,T0)确定是否继续接收新的观测值，经过S0-1次的序贯接收，最终获得最优观测向量利用式(6)所示的l最优p化重构出稀疏向量

对预设的门限值γ，当时，说明第i个初始网格中可能存在着多个目标，且元素的幅值是多个目标位置信息的累加；反之，不存在目标，此时只需簇头周期性地监测子区域，成员节点暂时休眠，以减少网络资源开销。

图3 大尺度网格划分下多目标定位模型

下面，本文重点对存在目标的K0个子区域进行基于自适应网格的目标定位。

3.2 自适应网格定位

为了在第i(i∈ {L1, … ,LK0})个初始网格中进一步确定目标的精确位置，需要自适应调整尺度来重新划分初始网格，其中，子列 {L1, …,LK0} ⊂ {1,…,N0}是存在目标的初始网格的序号。

因为此网格中目标个数未知，第一步假设只存在一个目标，记个数为由 CS原理可知，通常精确重构出稀疏解所需的观测次数应至少满足M=4K[27]，则划分初始网格后的小尺度网格个数需满足即（如图 4(a)所示）。sink随机激发初始网格中的个节点进行聚类和感知，成员节点将观测值发送给簇头。如果簇头由SCS计算的估计值 E st(mi,Ti1)＜τ，则增加新的观测值。如果每次固定增加T个观测值，则由SCS无法较快地确定最终的观测次数。为了快速分析出所需增加的观测值，不妨定义比值如式(7)所示。

ii例如，在图4(a)中计算得到Δ(mi,Ti1) ＞ 0 ，为了提高定位效率，需将初始网格重新划分成个小网格，且需满足图 4(b)显示3× 3的网格被划分为5× 5，而非4×4的网格。由CS重构条件可知，使用3× 3的网格至多可识别出2个目标，即3× 3 ＞ 8 = 4 × 2 ；而使用5×5的网格至多可识别出6个目标，即5× 5 ＞ 2 4 = 4 × 6 。因CS中压缩比不易过高，考虑5× 5 ＞ 1 6 = 4 × 4 。于是，簇头新接收Ti2= 1 2个观测值，总观测次数为

图4 第i个初始网格的自适应划分示意

第二步，簇头计算重构误差的估计值Est(m,T1+T2)，若此估计值仍大于τ，则重新划

iii分网格且接收Ti3个观测值；反之，则停止接收新的观测值。簇头由式(8)所示的lp最优化重构出稀疏向量

传统的 CS定位方法一般采用集中式处理方式，消耗了大量的信道资源和传输开销。同时，节点实时感知不存在目标的子区域会产生过多的感知开销。本文设计的定位方法较好地解决了上述问题，初始阶段基于大尺度网格的集中式定位方法在监测区域内区分目标存在和不存在的子区域，后续阶段基于小尺度网格的分布式定位方法并行地对存在目标的多个子区域进行精细定位。这种全局与局部结合、集中式与分布式结合及粗定位与细定位结合的方式为高精度、高效率的多目标定位提供了一种新的思路，更易应用于现行的分层结构的WSN，并推广至不同场景下的多目标定位问题。

根据上述讨论，本文提出的基于自适应网格的多目标定位算法的流程如图5所示。

图5 基于自适应网格的多目标定位算法流程

3.3 初始网格的合并与定位

初始阶段，sink由重构向量x0确定了每个初始网格的状态向量并获得了位置向量ID0= (L1, … ,LK0)，其中，所在的网格位置序号。如前文所述，监测子区域内聚集着多个目标，所以不难发现ID0中目标所在的初始网格常常相互邻近。如果联合这些相邻网格一起进行基于自适应网格的细定位，相比于单个初始网格各自进行定位可以大大减少感知、传输和计算开销。

如图6所示，大尺度网格定位将监测区域划分为N0= 5× 5 个初始网格，并确定了存在目标的初始网格，其中存在3种初始网格相邻情况。下面分别讨论合并初始网格后的自适应网格定位方法。

Case 1 3个初始网格相邻。将图6 (a)中c1区域扩展为4个初始网格且假设目标个数为首先，由SCS将子区域划分为个小网格，并在子区域及周围随机选择个节点进行观测，计算估计值及比值此时有需要接收较多的观测值。于是将子区域重新划分为个小网格，获取新的次观测。然后，簇头重新计算估计值及比值此时有簇头从观测向量中由最优化重构出稀疏向量个非零系数所在的网格中心即为个目标的估计位置，坐标为其中

图6 合并且自适应划分目标所在的相邻初始网格

Case 2 2个初始网格直接相邻。将图6(a)中c2区域扩展为 2个初始网格且假设目标个数为首先，由SCS将子区域内每个初始网格划分为3× 3个小网格，共个小网格，并在子区域及周围随机选择m+T1=8个节点进行观测，计算估计c1c2值及 比值此 时有只需接收少量新的观测值，取次观测。然后，簇头重新计算估计值及比值此时有不需要再接收新的观测值。簇头从观测向量中由最优化重构出稀疏向量个非零系数所在的网格中心即为个目标的估计位置，坐标为

Case 3 2个初始网格对角相邻。将图6(a)中c3区域扩展为 4个初始网格且假设目标个数为首先，由SCS将子区域划分为个小网格，并在子区域及周围随机选择个节点进行观测，计算估计值和比值此时时，需要接收较多的观测值，于是将子区域重新划分成个小网格, 再接收次观测。然后，簇头计算估计值和比值此时有簇头从观测向量中由最优化重构出稀疏向量其中，个非零系数所在的网格中心即为个目标的估计位置，坐标记为

4 实验仿真及结果分析

下面对本文提出的WSN中基于自适应网格的多目标定位算法进行仿真实验，主要分为两部分：首先，分别与基于CS的多目标定位算法和基于两阶段的多目标定位算法进行对比，验证本文算法具有更优的定位性能；然后，对比不合并和合并初始网格的定位性能，验证合并初始网格的高效性。

4.1 仿真场景

在Matlab中进行仿真实验。假设在正方形监测区域内随机高密度部署大量的传感器节点，K个待定位的目标随机分布在区域内的任意位置。参照文献[18]，仿真参数的设置如表1所示。

表1 仿真参数设置

为了评估定位性能，定义多目标定位误差为

其中，tcen为大尺度网格划分下的定位时间，tdis为小尺度网格划分下的定位时间；若ti为自适应划分第i个初始网格的定位时间，则tdis=max{t1, … ,ti,…,tK0}。

4.2 基于自适应网格的多目标定位算法的性能分析

4.2.1 大尺度网格的定位性能分析

WSN启动多目标定位后，大尺度网格的设置影响着后续自适应网格的设置。下面实验分析不同的大尺度网格划分对定位性能的影响。将K=7个目标和M=50个节点随机部署在不同面积的监测区域内，定义平均定位时间作为评估指标，其中，Nt= 5 0表示蒙特卡洛实验的次数，TIi为第i次实验的多目标定位时间。

针对不同的大网格尺度划分，图7显示不同监测区域面积下平均定位时间随着网格尺度变小而减小，但当初始网格数量达到一定规模时，平均定位时间又会增加。这是因为初始网格尺度设置过大时，自适应网格定位阶段会进行多次网格细划分操作，增加了计算时间；而初始网格尺度设置过小，存在目标的初始网格就过多，增加了自适应网格定位的计算时间。可以看出，4种监测区域面积对应的最佳大网格划分分别为8× 8、9×9、9×9、10× 10，则网格划分尺度n0与监测区域边长a0比值分别约为 16%、13%、10%、9%，因此可以按照8%～18%比例来确定大网格的尺度。

4.2.2 对比基于CS的多目标定位算法

在上述实验的基础上，本文分析了50 m×50 m的监测区域内不同CS定位算法的性能。传统的基于CS的定位算法直接将监测区域细划分成20×20的网格，应用BP算法、OMP算法或GMP算法对K个目标进行定位，而本文算法在8× 8的初始网格划分下实施自适应网格定位，估计K个目标的精确位置。定义平均定位误差来评估不同定位算法的定位性能。

图7 不同监测区域面积下平均定位时间与初始网格规模的关系

由图8(a)可知，随着目标个数的增加，本文算法均获得了最佳定位结果，其平均定位误差远远小于BP算法、OMP算法和GMP算法。例如，当K=8时，本文算法的定位精度比BP算法、OMP算法和GMP算法分别提高了85%、89.6%和83.6%。这不仅因为基于lp最优化的稀疏重构精度优于l0最优化和l1最优化，而且分为全局和局部2个阶段定位目标比直接全局定位目标更精确、更符合实际场景。图 8(b)显示本文算法的平均定位时间少于 BP算法和GMP算法，虽高于OMP算法，但为了提高定位精度，可容忍增加37%的平均定位时间。图8(c)显示了感知节点个数随着目标个数变化的情况，与其他3种算法相比，本文算法可大大减少感知节点个数，即重构所需的观测次数。

图9给出了K=7时4种算法的定位示意，可以看出，本文算法的定位准确性最高。利用BP算法、OMP算法和GMP算法重构稀疏解时，其非零元素的位置都出现了偏差，因而出现了漏检目标和虚假目标的情况。

基于CS 的多目标定位易受环境的影响，为验证本文算法的抗噪性能，将K=10个目标和M=60个传感器节点随机部署在监测区域内。图10(a)显示随着信噪比的增加，节点接收的目标信号强度准确性显著提高，因此4种定位算法的平均定位误差均呈下降趋势，其中，本文算法的定位精度明显优于其他3种算法。当SNR从-6 dB变化到24 dB时，本文算法的平均定位误差分别比BP算法、OMP算法和GMP算法最多降低了77.0%、82.5%、65.0%；当SNR大于20 dB时，本文算法的定位精度在0.5 m以内，而此时其他3种算法的定位精度分别在2 m、3 m和1.8 m以内。图10(b)显示随着信噪比的增加，4种定位算法的平均定位时间均逐渐减少，本文算法的平均定位时间明显小于BP算法和GMP算法，但大于OMP算法。为了提高定位精度，可以容忍一定程度上增加定位时间。因此，本文算法的抗噪性能优于传统的CS定位算法。

图8 不同目标个数下4种定位算法的定位性能比较

图9 4种定位算法的多目标定位示意

图10 不同信噪比下4种定位算法的定位性能

随着“万物相连”的物联网的广泛应用，WSN作为其基础设施，规模越来越大，因此传统的多目标定位算法不再适用于大规模的 WSN。当监测区域面积不断增加时，传统的基于CS的定位算法划分出的网格数量急剧增加，使重构算法的计算复杂度大大增加，从而影响了目标定位精度。例如，在K= 1 5，M=90，SNR=20 dB情况下，分别将50m× 50m、80m× 80m、100m× 100m、120m× 120m的监测区域划分为20×20、25×25、30× 30、35× 35的网格。图 11(a)显示随着监测区域面积的增加，BP算法、OMP算法和GMP算法的平均定位误差均有大幅增长。然而，本文算法首先大尺度划分监测区域，避免了在大范围内以高计算代价重构目标位置，然后对存在目标的小区域进行自适应网格定位，大幅提高了定位精度，减少了平均定位时间，如图 11(b)所示。例如，监测区域为120 m× 120 m时，本文算法的平均定位误差比 BP算法、OMP算法和GMP算法分别降低了77.2%、81.8%和 87.2%；相应的平均定位时间分别减少了81.4%、56.2%和86.3%。

图11 不同监测区域面积下4种定位算法定位性能比较

4.2.3 对比基于两阶段的多目标定位算法

为了提高定位精度，文献[18]设计了基于两阶段的多目标定位算法（下文中称为对比算法），该算法按次对每个候选网格进行多次四分操作来确定目标位置，花费较长的定位时间。本文算法并行地对所有存在目标的子区域进行自适应网格定位，大大减少了定位时间。下面的实验比较了在50 m×50 m的监测区域内不同信噪比下 2种分阶段定位算法的性能。图 12(a)显示随着信噪比的增加，2种定位算法的平均定位误差均逐渐减小，然而在所有 SNR下本文算法的平均定位误差均远远小于对比算法，约减少了72%～88%。相应地，随着信噪比的增加，图12(b)中2种定位算法的平均定位时间均逐渐减少，但本文算法的平均定位时间比对比算法减少了约 83%～94%。当K=8， S NR为- 6 ～ - 2 dB时，本文算法的平均定位误差比对比算法降低了 62%～60%，而平均定位时间比对比算法减少了90%～88%。因此在低SNR下本文算法仍然可以及时、精准地确定出多个目标的位置，为复杂无线环境下的多目标定位提供有力的保障。

目标个数的增加（即位置向量x的稀疏度降低）直接影响着从观测向量中重构目标位置的性能，所以本文分析信噪比为5 dB和-5 dB下目标个数对定位结果的影响。在监测区域内随机部署M= 9 0个传感器，图 13(a)显示随着目标个数的增加，2种分阶段定位算法的平均定位误差均逐渐增大，但本文算法的平均定位误差远远小于对比算法，最多减少了 73%。同时，图 13(b)显示其平均定位时间也远远小于对比算法，最多减少了93%。这是因为对比算法按次对每个候选网格进行多次四分定位，随着目标个数的增加，定位时间必然会大大增加。然而，本文算法对存在目标的初始网格并行地进行自适应网格定位，可大大减少定位时间。可见在目标个数较多时，本文算法具有更好的准确性、及时性。

图12 不同信噪比下2种分阶段多目标定位算法的定位性能

4.3 自适应合并初始网格的性能分析

对每个初始网格进行自适应定位，必然使WSN出现较多的分簇，引起过多的资源开销。如果将相邻的初始网格合并，可以更高效地实现子区域的目标定位。为此，将K=10个目标随机分布在图14中40 m×40 m的监测区域内，并将之先划分成6×6的网格。sink根据SCS收集m+3T= 3 0(m=6,T=8)个观测值，利用lp最优化确定出存在目标的初始网格，并依据稀疏解中非零元素的位置合并初始网格，如图14中黑色线框所示。自适应网格定位阶段，表2显示合并初始网格的定位方法比不合并初始网格的定位方法在定位时间上具有明显优势，而且当合并的初始网格个数越多，定位时间的减少越明显。例如，c1区域合并 3个相邻的初始网格后，其定位时间比不合并初始网格减少了71.5%。

图13 不同目标个数下2种分阶段多目标定位算法的定位性能比较

图14 自适应合并目标所在初始网格的实景

表2 2种小尺度网格定位方法的定位时间比较

5 结束语

本文提出了一种WSN中基于自适应网格的多目标定位算法，将大尺度网格确定目标大致位置与小尺度网格确定目标精确位置相结合。与传统的基于CS的定位算法相比，本文算法减少了网络的采样开销，且具有良好的抗噪性能。仿真实验表明本文算法在保证定位精度的同时有效地降低了定位时间开销。目前，尚没有在OPNET或OMNET++等仿真平台上进行实验，因此对于本文算法在实际传感器网络中的验证有待下一步解决。