传感器网络定位的高效ADMM方法：集中式与分布式方法

《Ad Hoc Networks》：Efficient ADMM for sensor network localization: Centralized and distributed approaches

　　

## 摘要

交替方向乘子法（ADMM）通过将复杂问题分解为若干子问题，已被广泛应用于分布式优化中。本文利用带扰动的近端梯度ADMM（PPG-ADMM）框架来解决传感器网络定位（SNL）问题，方法是引入辅助位置变量。对于集中式定位，我们首先提出一种PPG-ADMM解决方案，称为集中式定位ADMM（CL-ADMM），用于求解最大似然（ML）定位模型。在合适的参数条件下，CL-ADMM的收敛性讨论可基于已建立的PPG-ADMM理论得出。此外，我们将基于PPG-ADMM的方法扩展到分布式定位，并通过消息传递提出了一种分布式定位ADMM（DL-ADMM）。得益于其有效的结构设计，CL-ADMM和DL-ADMM的解决方案能够达到接近克拉美–罗下限（CRLB）精度的定位性能。在DL-ADMM中，计算任务分配给各个传感器，因此与CL-ADMM相比，DL-ADMM在计算时间方面具有优势。仿真结果进一步表明，CL-ADMM和DL-ADMM在广泛的噪声水平范围内均可接近CRLB精度。

## 引言

传感器网络定位（SNL）在其广泛应用中发挥着关键作用，例如监控、追踪和控制[1]、[2]、[3]。SNL问题也是完成这些应用的关键技术，已成为传感器网络领域的经典课题。通过部署若干已知位置的锚节点，传感器位置可借助与距离相关的信号传播唯一确定。典型的与距离相关的信号传播包括到达时间（TOA）测量[4]、[5]、到达时间差（TDOA）[6]、[7]、到达角度（AOA）[8]、[9]以及接收信号强度（RSS）[10]、[11]。其中，基于TOA的距离测量因其高效性和低复杂度实现而被广泛用于SNL问题。在非协作定位中，仅使用传感器与锚节点之间的测量来确定传感器位置[12]。由于成本原因，锚节点稀疏部署，非协作方法通常无法确定传感器位置。为解决这一问题，提出了协作定位来处理SNL[13]、[14]。在协作定位中，除了传感器与锚节点之间的测量外，还利用传感器之间的测量来确定位置[15]、[16]、[17]。即使锚节点数量较少，协作定位在SNL问题中仍展现出巨大优势。与非协作方法相比，协作定位为传感器位置提供了更精确的估计[18]、[19]。

传统方法通过将所有测量信息收集到中心处理器进行处理集中式定位[20]。对于大规模传感器网络，集中式定位（CL）的计算开销急剧增加。此外，CL对单个节点的故障十分脆弱。与CL不同，分布式定位（DL）通过将计算过程分配给每个节点，利用消息传递来实现[21]。与CL相比，DL显著降低了复杂度和存储开销。因此，开发DL成为处理SNL的一项重要工作。

在传感器网络中，SNL确实是一个具有挑战性的问题，因为存在大量变量。此外，当SNL使用最大似然（ML）估计器表述为优化问题时，本质上是非凸且非光滑的[22]。寻找高效解决方案是一项富有挑战性的工作，因为需要同时考虑收敛性、复杂度和精度。一种可行方法是通过将非凸问题松弛为凸形式来追求近似解。因此，提出了半定规划（SDP）松弛方法来处理集中式SNL[23]、[24]。SDP解决方案确保了SNL问题的全局收敛性。遗憾的是，由于松弛过程中产生了大量变量，SDP的复杂度相当高[25]、[26]。因此，SDP不适合大规模SNL问题。

另一种方法是将SNL分解为若干子问题，从而简化计算过程。这样，解决方案的复杂度得以降低。文献[27]中提出了交替最小化（AM）方法，通过将SNL转化为等价的平滑问题来处理，并设计了完全集中式的AM方案（AM-FC）。最近，交替方向乘子法（ADMM）被推荐应用于大规模分布式优化问题[28]。ADMM方法将复杂优化问题分解为若干子问题，并交替求解。对于凸问题，两分块ADMM已被证明全局收敛。然而，经典ADMM的收敛性保证不能直接适用于非凸且非光滑的SNL模型。最近，针对线性约束非凸复合优化问题发展了近端ADMM框架，并在合适的参数条件下提供了收敛性保证[29]、[30]。得益于ADMM的高效性，它也被提出并用于处理定位问题。在[31]、[32]中，引入辅助方向变量将非光滑定位问题转化为平滑问题，从而开发了求解单源定位问题的ADMM。在[14]中，ADMM也被应用于协作SNL，该方法通过利用每个节点上的实现实现了完全分布式运算。此外，分布式缩放近端ADMM（SP-ADMM）在处理SNL时展现出更低的复杂度和收敛性。

上述提出的ADMM解决方案属于非标准形式，这意味着其收敛性无法得到保证。在[14]、[33]中，通过引入辅助方向变量将非光滑SNL问题转化为平滑优化问题。遗憾的是，方向变量是传感器位置的非线性函数，方向变量与传感器位置之间的约束关系难以纳入优化问题。因此，尽管这些ADMM解决方案以分布式方式运行，但其性能不佳。

如前所述，这些ADMM方法利用辅助方向变量来建立平滑优化问题，导致其属于非标准形式。此外，由于方向变量的约束关系未被包含，这些ADMM方法表现不佳。本文应用现有的PPG-ADMM框架[30]来处理协作SNL问题，将ML定位模型重新表述为线性约束非凸复合优化问题。引入辅助相对位置变量以获得与PPG-ADMM更新结构兼容的线性约束模型。此外，辅助位置变量的引入相比方向变量提供了更紧凑的形式。因此，在广泛的噪声水平范围内，性能得到显著提升。在合适的参数条件下，CL-ADMM的收敛性讨论可基于已建立的PPG-ADMM理论得出。所提出的ADMM解决方案是ML估计器的近似等价最优解。本文的主要贡献可概述如下：

1. 我们将协作SNL问题重新表述为与PPG-ADMM框架兼容的线性约束非凸复合优化问题，并推导出具有闭式逐边更新的集中式定位ADMM，称为CL-ADMM。在合适的参数条件下，CL-ADMM的收敛性讨论可通过李雅普诺夫下降论证，基于已建立的PPG-ADMM理论得出。

2. 我们进一步开发了一种分布式定位ADMM，称为DL-ADMM，通过将局部PPG-ADMM更新与邻居一致性校正和消息传递相结合来实现。

3. 我们通过量化常数设计了存储空间缩减的CL-ADMM和DL-ADMM解决方案，并分析了所提出解决方案的通信成本和复杂度。

4. 所提出的CL-ADMM和DL-ADMM基于位置差变量提供了解析ADMM更新，从而实现了更紧凑的优化模型和直接的更新过程。与代表性SNL方法相比，其性能优势总结于表1中。

后续各节的组织如下：第2节介绍SNL问题的模型和PPG-ADMM模型。第3节介绍CL-ADMM解决方案。第4节介绍分布式DL-ADMM。第5节提供存储、通信和计算开销的分析。第6节评估仿真结果。最后，第7节总结全文。

本文使用的符号定义如下：粗体小写字母和粗体大写字母分别表示向量和矩阵。$\mathbf{A}^{-1}$表示矩阵$\mathbf{A}$的逆，$\mathbf{A}^T$表示$\mathbf{A}$的转置。符号$\|\cdot\|$表示$\ell_2$范数。$[\mathbf{a}]_i$表示向量$\mathbf{a}$的第$i$个元素。$[\mathbf{a}]_{i:j}$构成包含$\mathbf{a}$第$i$个到第$j$个元素的子向量。$[\mathbf{A}]_{i,j}$表示矩阵$\mathbf{A}$的第$(i,j)$个元素。$\mathbf{I}_n$表示$n\times n$的恒等矩阵。$\mathbf{O}_{n\times m}$表示$n\times m$的全零矩阵。$\text{diag}\{\mathbf{a}\}$表示对角矩阵，其对角元素为$\mathbf{a}$的元素。符号$\otimes$和$\odot$分别表示Kronecker积和Hadamard积。此外，算子$\text{vec}\{\mathbf{x}_i|i\in\mathcal{N}\}$构成所有$i\in\mathcal{N}$的$\mathbf{x}_i$的拼接向量。另外，$\|\mathbf{x}\|^2_{\mathbf{W}}$表示由$\mathbf{W}$诱导的缩放范数，即$\|\mathbf{x}\|^2_{\mathbf{W}}=\mathbf{x}^T\mathbf{W}\mathbf{x}$。

## 问题建模

考虑一个由$N$个节点组成的传感器网络，部署在$n$维空间中。该网络包括$M$个坐标未知的传感器和$N-M$个坐标已知的锚节点。传感器和锚节点可以与其邻居通信，形成一个无向图$\mathcal{G}=(\mathcal{N},\mathcal{E})$。$\mathcal{N}=\{1,2,\ldots,N\}$表示所有节点（包括传感器和锚节点）的集合。此外，$\mathcal{E}$表示所有相邻节点之间的通信链路集合。节点集中第$i$个节点的位置记为$\mathbf{x}_i\in\mathbb{R}^n$，$i=$

## CL-ADMM解决方案

在CL-ADMM中，复杂的优化问题同样通过将其分为三个步骤来求解，有效简化了计算过程。对于集中式CL-ADMM，所有测量数据被收集到计算中心，在该中心执行解决方案的迭代步骤。下面，我们提出利用PPG-ADMM形式解决SNL问题的详细CL-ADMM方案。

## DL-ADMM解决方案

与集中式方法不同，分布式定位在每个传感器上执行。因此，ADMM计算应分配给每个传感器。为了在每个传感器上本地执行更新步骤，需要通过消息传递方案共享位置信息。下面，我们提出解决SNL问题的DL-ADMM方案。首先，我们将增广拉格朗日函数改写为各传感器之和的形式。

## 性能分析

在ADMM解决方案中，存在大量必须存储的变量和常数以完成迭代计算步骤。消息传递是完成ADMM更新过程、交换信息的必要手段。遗憾的是，传感器通常具有有限的存储、计算和通信能力。本节提供存储空 间、通信成本和复杂度的详细分析。

## 评估

本节利用仿真来评估所提出ADMM解决方案的性能。采用2D场景，3D场景的评估类似。我们使用斯坦福计算优化实验室[34]的两个大规模网络，包括一个具有10个锚节点的$N=500$节点网络和一个具有20个锚节点的$N=1000$节点网络。此外，我们还根据均匀分布$[-0.5, 0.5]$ m生成两个小规模网络，网络几何结构为

## 结论与未来工作

本文将PPG-ADMM框架应用于协作传感器网络定位，通过将SNL问题重新表述为线性约束非凸复合优化问题。基于该模型，我们推导了集中式CL-ADMM算法，其中$x$子问题通过线性化近端梯度步进行更新，$z$子问题允许逐边闭式更新。由于CL-ADMM遵循PPG-ADMM的结构，其收敛性分析可以借鉴已建立的

## CRediT作者贡献声明

Xiaoping Wu：撰写——原始草稿、方法论、概念化。Lianshi Zhang：软件、数据管理。Shenghui Wang：验证、资金获取、形式分析。

## 利益冲突声明

作者声明不存在可能影响本文工作的已知竞争性经济利益或个人关系。

Xiaoping Wu | Lianshi Zhang | Shenghui Wang