英语原文共 9 页

无线传感器网络中的凸优化定位算法

摘要

提出了一种基于连接诱导约束的传感器网络未知节点位置估计方法。将网络中已知的点对点通信建模为节点位置上的一组几何约束。对于这些约束的一个可行性问题的全局解决方案产生了对网络中未知节点位置的估计。假设约束足够紧，仿真表明该估计会接近实际节点位置。此外，给出了一种在网络中所有未知节点的可能位置周围设置矩形边界的方法。边界矩形的面积随着附加约束或更紧约束的加入而减小。提出了各向同性和定向通信的具体模型并进行了仿真，分别代表了基于广播和光传输，但所提出的方法并不局限于这些简单的情况。

关键词-位置估计，定位，传感器网络，凸优化

一、引言

集成电路、微机电系统(MEMS)和通信理论的成熟，催生了无线传感器网络的出现，促进了成百上千个自给自足传感器节点网络的经济和计算可行性。每个节点都能够感知其环境的元素，执行简单的计算，并在其对等节点之间或直接与外部观察者通信。较大的节点数允许在更大的地理区域以比以前可能更高的精度进行传感。

本文工作的主要动机是智能尘埃项目，旨在将传感通信平台的规模缩小到立方毫米体积。最有前途的短距离和长距离点对点通信方法分别是射频和光介质。在芯片级集成这两种介质方面正在取得进展，而宏观传感器节点系统已经证明为。研究了自组网路由协议的信息论边界，详细介绍了自组网路由协议。

在成千上万个节点的网络中，设计者不太可能确定每个节点的位置。在极端情况下，节点可能会从空中掉落，并分散在未知区域。然而，要处理传感器数据，必须知道数据来自哪里。节点可以配备一个全球定位系统(全球定位系统)为他们提供绝对位置的知识，但1ldoherty@bsac.eecs.berkeley.edu目前这是一个昂贵的(在数量，金钱和功耗)解决方案。相反，位置信息可以从连接强加的邻近约束中推断出来。在这个模型中，只有几个节点具有已知的位置(可能是安装了全球定位系统或有意放置的)，其余的节点位置是根据关于通信链路的知识计算的。Estrin等人在中提出了解决节点相对于信标位置的不太普遍的尝试，而在文献[9]和文献[10]中描述了硬件实现的系统。

本文描述了使用凸优化的位置估计问题的可行解。如果一个节点可以与另一个节点通信，则它们之间存在邻近约束。作为一个物理示例，如果特定的RF系统可以传输20米并且两个节点进行通信，则它们的间隔必须小于20米。这些约束限制了可行的未知节点位置集。仅考虑平面网络，但将方法扩展为3-D是直截了当的。总结如图1所示：

给定：实体节点的位置

查找：每个开放节点的可能位置

受制于：已知连接强加的邻近约束

形式上，网络是在顶点处具有n个节点（每个节点具有笛卡尔位置）并且具有双向通信约束作为边缘的图。已知前m个节点的位置（x 1，y 1，... xm，ym），并且剩余的nm位置是未知的。然后，可行性问题是找到（xm 1，ym 1，... xn，yn），使得满足接近约束。请注意，虽然开放节点的位置未知，但它们之间存在约束。未报告的连接不会对算法的性能产生不利影响。

这里开发的位置估计方法需要集中计算。即，所有节点必须将其连接信息传递给单个计算机以解决优化问题。Culler等人证明了这种范式的可行性。文献[11]生成一个RF-ad-hoc网络，能够将连接统计信息中继到集中式PC。该系统由在传感器节点上运行的自定义操作系统组成，并在本文的上下文中提出了传感器网络的具体示例。我们专注于位置估计方面，并且没有进一步考虑通信协议，尽管带宽约束可能是传感器网络大小的基本限制。

二、数学公式

基于内点方法的高效多项式时间算法用于求解线性程序和半定程序。线性程序（LP）是以下形式的问题

几何上，这相当于使多面体上的线性函数最小化。

第一个不等式表示正半定矩阵锥上的矩阵不等式，即F（x）的特征值被约束为非正。这被称为线性矩阵不等式（LMI）。同样，目标函数对于SDP必须是线性的。约束可以用任何一种方法堆叠。SDP将足以解决本文中的所有数值问题，尽管LP将在适用的地方使用，因为它具有出色的计算效率。在二维中，每个节点具有位置（x，y）。对于位置估计，形成具有所有位置的单个向量：

前m个条目固定为数据，剩余的（n-m）个由算法计算。

通常，有效的计算方法可用于大多数凸规划问题。在几何上，凸集是集合中的任何两个点可以与完全包含在集合中的线连接的集合。以下部分介绍了RF和光通信系统的Convexconstraint模型。其他凸约束也可以用相同的算法计算。

解决方法不是近似的; 假设实验者相信约束模型的有效性，这里开发的位置估计是可以实现的最好的。表明特定应用的性能低于期望水平的结果反映了约束模型中的不确定性而非位置估计方法所施加的限制。

三、凸约束模型

A.连接作为凸约束

假设网络的连通性可以表示为一组凸位置约束，则可以利用前一部分中概述的数学方法来为网络中的所有节点生成可行位置。单独考虑连接约束就足够了，因为两种编程方法都允许将约束收集到单个问题中。问题变成：“给定节点A的位置，节点B的可能位置集是什么？”本节的其余部分专门讨论这个可行集的两个模型。

B.Radial约束- RF通信

无线传感器节点的RF发射器可以被建模为具有旋转对称范围，如图4a所示。这不是通常是高度各向异性和时变通信范围的精确物理表示，但是始终可以使用限制最大范围的圆。此外，如果明显椭圆通信模型更相关，则前进方法同样适用于椭圆而不增加复杂性。

在该对称模型中，节点之间的连接可以由节点位置上的2范数约束表示。具体而言，对于最大范围R和节点位置a和b，等效LMI由下式给出：

对于二维问题，使用Schur补集[14]将二次不等式转换为（3）中具有3times;3矩阵的LMI，其中I 2表示二维身份。多个LMI可以堆叠在对角线块中，以形成整个网络的一个大SDP。因此，每个双向接近约束为系统贡献一个凸的3x3 LMI。

此问题的一个变体是使用节点之间的精确距离作为上述LMI中的外部距离：

为了强调，在前一种情况下，所有约束都以具有相同半径R的圆为界，在后一种情况下，每个约束被赋予可能的最小半径r ab（图2）。物理上，在初始化阶段期间改变其输出功率的发射器可以获得r ab的估计。如果首先以功率P o获得连接，则接收器计算在P o处接收的最大可能间隔。该最大间隔r ab lt;R可用于确定网络中每个单独连接的更严格的上限。

请注意，以下两个都不是凸约束

后者在“推开”算法中未连接的节点时非常有用，如图3所示。这种约束在物理上也不现实- 由于物理屏障或传输各向异性，某个范围内的节点可能无法通信。如果已知分离的一些下界并且（5）中的前一约束被公式化为一组稳健的凸约束，则可以获得更高的精度。

C.角度约束- 光通信

考虑具有激光发射器和接收器的传感器节点，其扫描一定角度。接收器粗略地旋转其检测器直到获得信号，然后精细地获得最大信号强度。通过观察最佳接收发生的角度，我们可以形成对发射机的相对角度的估计以及它们之间的最大距离的模糊估计。这导致可行组的锥形（2D中的三角形），如图4b所示。该圆锥可以表示为三个半空间的交点- 两个用于限制角度，一个用于设置距离限制。半空间的交集仍然是LP。

连接到多个邻居的节点将具有指向适当方向的锥形foreach邻居，但是所有锥体具有相同的半角和长度。

D.其他凸约束

SDP和LP约束的任何组合可用于定义各个可行的位置集。一些研究致力于涉及一个LMI和两个标量线性约束的象限检测器方案（图4c）。在更一般的情况下，对于具有可变角度和宽度的梯形（图4d），四个线性约束可以近似环形的一段，其可以表示位置和角度的不确定知识。还有其他非LMI约束也可能有用。

E.结合个体约束

网络中的节点位置通常受到与其他几个节点的连接的约束。满足多个约束意味着可行集合成为各个约束集合的交集，必然使得可行区域随着每个附加约束而变小，如图5所示。该减小区域恰好是位置估计背后的机制。凸集的交集本身就是一个凸集，因此我们的搜索方法仍然足够。

虽然图5中仅说明了已知位置和未知位置之间的连接，但未知未知连接对问题解决方案同样重要。在这种情况下，a和b都是SDP或LP中的变量。使用单个全局程序同时解决所有未知位置。

四、仿真

A.计算时间

所有仿真均在具有64 MB RAM的AMD K6-2 400 MHz处理器上计算。使用Mosek Optimization Toolbox [15]从MATLAB环境执行代码以解决LP和SDP问题。当限制在圆形区域时，径向情况可以解决为二阶锥问题（SOCP）。该软件使用内点方法有效地解决了LP和SOCP。稀疏数组用于存储变量和连接信息。

作为确定计算时间和缩放的实验，解决了两个玩具问题：一个用于径向约束方法，一个用于角度约束（图6）。第一个由n个节点组成，这些节点排列在由距离R分开的垂直链中，仅有已知位置的顶部和底部节点。在径向情况下，唯一可行的解​​​​决方案是实际解决方案。第二个将n个节点置于阶梯模式中，同样将第一个和最后一个节点置于已知位置。在角度情况下，可行解决方案与实际解决方案非常接近（并且取决于theta;）。每个未知节点都连接到其他两个节点。

在所有情况下，固定节点的数量，m = 2，而估计中间节点位置。计算时间如图7所示，仅包括在求解器中花费的时间，而不包括模拟网络连接的时间。

B.网络仿真

除非另有说明，否则通过将节点随机且均匀地放置在边长10R的正方形区域中来形成模拟中使用的网络。放置200个节点，然后通过检查每个成对距离来确定连接性; 如果两个节点之间的距离小于R，则节点标记为已连接。最后，提取200节点网络中最大的连接子网，并随机置换节点标签，如图8所示.10个这样的网络用于模拟，平均节点数为194，每个节点的平均连接数为5.7。

C.评估指标

如第二部分所述，SDP和LP都只允许线性目标（c T x）。然而，没有明显的线性目标可以为放置问题提供任何种类的“最佳”解决方案。相反，目标函数在求解器中保留为空白。这具有从解空间中选择随机可行点x est =（x est，y est）的效果- 该点表示（x，y）对的（nm）条目集，每个未知位置一个。可以做出的节点位置的最精确的陈述是节点位于允许区域的交叉点中的某处。假设这些区域足够小，为所有节点找到可行位置可能足够接近所需的估计。

算法的性能定义为从计算到实际未知位置的平均误差。该平均误差提供了可行集的大小的度量。

径向和角度问题都使用相同的度量。虽然对角度情况不是最直观的满意，但我们感兴趣的问题是位置估计，因此实际位置的偏差仍然是最小化的最佳变量。

D.界定可行集

为了有效地利用目标函数c T x的效用，算法可以多次运行。这提供了一种机制，用于将可行集与一个平行于轴的矩形区分开来。对于每个未知位置k，计算如下进行：

1）设置c 2k-1 = 1并且所有其他ci = 0用于c in（1）或（2）

2）求解原始SDP / LP→得到xk min

3）设置c 2k-1 = -1和所有其他ci = 0

4）求解原始SDP / LP→得到xk max

5）对c 2k重复步骤1-4得到yk min和yk max

这个过程定义了最小的这样的矩形，它限定了可行集，如图9所示。通过选择这个矩形的中心作为最可能的解决方案，我们可以预期随机选择的情况下平均误差有所改善。

对于解决的问题数量增加4（nm）倍的价格，获得了估计性能的增加和解决方案的外部界限。

另一种可能性是在[14]中讨论的每个未知位置的解空间上找到最小量度椭圆界。通常，这不会由于问题松弛而提供紧密的上限，但是可以提供数值上类似的结果，需要针对每个未知位置而不是四个来解决单个SDP。但是，问题不再是更简单的SOCP框架。

五、径向约束结果

A.两种径向约束方法的比较

本节分析并解释了固定半径和可变半径RF定位方法之间的性能差异。使用n节点网络，执行以下测试：

1）选择节点1作为已知位置（m = 1）

2）求解剩余的nm未知位置

3）用实际网络计算这些nm位置的平均误差（6）

4）增加已知位置的数量1（因此将未知数减少1，m = m 1）

5）重复步骤2-4直到m = 100

由于在一半以上的节点中实施位置校准可以避免预期的成本节省，因此试验在m = 100时停止。这些试验的结果总结在图10中。

在m的低值处，估计执行与节点位置处的随机猜测一样差。将性能与天然信标系统进行比较是有用的，其中环境由已知节点位置的网格覆盖。如果节点在信标的通信范围内，则在该半径R内的随机猜测将导致网络的平均误差为2/3 R. 对于我们的10 R x10 R网络，此性能需要超过100个信标节点; 这种精度通过可变半径情况下的26个节点和具有随机选择的已知位置的固定半径的33个节点来实现。

可变半径方法有显着的性能提升，这表明通过直接测量功率或通过几个不连续的步骤调制传输功率来改善距离传感的努力将改善位置估计。误差随m单调减小，已知位置越多，性能越好。

B.智能选择已知节点

如第III.B部分所述，径向约束不具有推动节点的倾向。在此估算方法中，未知位置不会放置在已知位置的凸包之外。因此，当在网络的周边找到已知的节点位置时，尤其是在角落处，应该获得最佳结果。

在该实验中，选择最靠近测试网络角落的4个节点作为已知位置。参考图8，这是节点集{17,34,119,153}。在10个测试网络上平均，角节点选择将可变半径情况

资料编号：[4801]