基于序列贪婪优化的分布式无线传感器网络定位算法

基于序列贪婪优化的分布式无线传感器网络定位算法摘要：节点的定位对大多数无线传感器网络的应用来说是非常必要的。在本文中，我们要考虑在测量距离、无线电范围以及信标节点位置都不确定时，基于测距的节点定位和无需测距的节点定位这两种定位方式的定位情况。首先，我们将这个贪婪优化算法命名为序列贪婪优化(SGO)算法，因为这个算法跟传统的非线性高斯-赛德尔算法相比更适合分布式网络优化。其次，我们提出一个统一的优化框架，可用于基于测距的定位和无需测距的定位，并且在半定规划(SDP)松弛技术的基础上获得两个凸定位规划。第三，我们一方面将SGO算法应用到基于边缘的SDP松弛规划中去，通过分析得出了一个以二阶锥规划(SOCP)为基础的分布式节点定位算法；另一方面，我们将SGO算法应用到非凸定位规划中去，同样也得出了两个分布式细化SGO算法。以上这些定位算法都可以实现网络的部分异步。最后，通过大量的模拟演示可以展现所提出的这些分布式定位算法的效率和准确性1。关键词：分布式优化、基于测距的节点定位、无需测距的节点定位、二阶锥规划(SOCP)、半定规划(SDP)、序列贪婪优化算法(SGO)、无线传感器网络(WSN)。1、引言无线传感器网络(WSN)由大量微小的、低功耗的、随机部署的传感器节点组成，这些节点都具有传感、处理和通信能力。大多数无线传感器网络的应用，比如说环境监测、搜索和救援、目标追踪等等，都需要传感器节点的位置信息。一般情况下，出于经济上的考虑，在这些大量的传感器节点当中，只有一小部分节点的位置信息是通过全球定位系统(GPS)测量得出的或是由手动配置得到的(这些节点通常被称为信标节点)，而其它节点的位置信息都是通过定位算法测算出来的，这种方式尤其适合在大规模的传感器网络中使用。因此，开发出一套高效的节点自定位算法是无线传感器网络应用的必要条件。传感器网络中的节点定位，主要包括基于测距的定位和无需测距的定位。基于测距的定位需要获得节点之间的测量距离，这个测量距离可以通过接收到的信号强度(RSS)或到达时间(TOA)等测距方式获得，而无需测距的定位只需使用连接信息(例如，一个节点是否是在另一个节点的传输范围内)就可以实现，相应地，定位算法就可以分为基于测距的定位算法和无需测距的定位算法。基于测距的定位算1QingjiangShi，ChenHe，HongyangChen，etal.DistributedWirelessSensorNetworkLocalizationViaSequentialGreedyOptimizationAlgorithm[J].IEEETransactionsonSignalProcessing，2010，58(6)：3328-3340.法跟无需测距的定位算法相比，定位精度更高，但是无需测距的定位算法更加便宜、简单，因为它不需要配备特殊的硬件来完成测距。另一方面，根据计算模式的不同，可以将定位算法分为集中式算法和分布式算法。集中式算法要求将所有的测量距离或者节点之间的连通信息都传送到一个融合中心(例如，汇聚节点)进行处理，这样一来就会产生大量的通信能耗和带宽消耗，从而缩短整个网络的寿命。分布式算法能源的有效性高，并且随着网络的大小可进行扩展，分布式节点定位的总体任务就是让所有节点跟它相邻的节点进行信息交换。因此，对大规模的传感器网络而言，分布式定位算法更具吸引力。目前针对传感器网络的定位，人们提出了很多定位算法。在无需测距的定位算法中，就存在启发式的、操作简单的、允许分布式实现的定位算法，但是这些算法一般都是不精确的，并且只在信标节点的定位中使用。Y.Shang,W.Ruml,Y.Zhang,andM.Fromherz三个人在经典多维尺度(MDS)技术的基础上，提出了一组定位算法，这组算法可以同时适用于基于测距的定位和无需测距的定位，并且明显地优于启发式的定位算法。在他们所提出的所有这些算法中，MDS-MAP(P，R)算法对不规则网络的定位能力是最好的，但是这种算法却非常复杂、昂贵，最复杂也最贵的就是它的核心战略，即首先为每个节点建立一个本地地图，然后将这些本地地图合并起来形成一个全局地图，在形成本地地图的过程中需要用到集中式算法，所以尽管MDS-MAP(P，R)算法可以在网络中实现，但是却不适合在大规模的网络中使用。因此，另外一个算法—度量MDS算法随之被提出，主要适用在基于测距的定位当中，而且这个算法特别适合用分布式实现，但是，度量MDS算法是局部收敛的，这就意味着它的定位性能很差，除非能够提供一个很好的初始化条件才能提高它的定位性能。在这种情况之下，J.Liu,Y.Zhang和F.Zhao提出来一个强大的基于多边的迭代定位算法，这种算法适用在基于测距的定位中，它的权重很小，因而很适合分布式实现，但是，这种算法的收敛性没有理论保障。基于凸优化的定位算法具有很好的全局收敛性，所以在传感器网络定位中很受欢迎。这种定位算法大部分都用在基于测距的定位中，只有少数用于无需测距的定位中。但是这些定位算法都有一个相同的处理方式，那就是将定位问题看成非线性优化问题，将由此产生的问题看成是凸优化问题，最后利用高效的内点算法来求解。凸松弛技术涉及到两个算法：二阶锥规划(SOCP)算法和半定规划(SDP)算法。在大规模网络(成千上万个节点)中使用基于SDP的算法是非常昂贵的，因为它有着非常复杂的结构，这就要求它需要必须进行集中式计算。为了减少计算负荷，有人提出一种基于集群的SDP定位算法，虽然这种算法可以在网络中实现，但是它并不是一个很好的分布式算法，原因在于：1、这种算法首先要求形成集群，但是这样会产生额外的通信费用；2、每个集群都要使用集中式算法；3、如果没有足够的信标节点，这种算法就会失效。而减少计算负荷的另外一种方法就是近一步让基于测距的定位问题松弛化，在这个基础上提出基于节点的SDP松弛算法和基于边缘的SDP松弛算法，虽然这两个松弛算法比一般的SDP松弛算法的定位效果要差，但是它们都能保证计算的有效性和精确性。跟SDP松弛算法相比，SOCP松弛算法虽然定位效果较弱(因此不准确)，但是它的结构更简单，而且允许有效的分布式方式实现。有人想出了一种基于SOCP算法的完全异步的分布式定位算法，适用于基于测距的定位，很快地，这个算法就被扩展到无需测距的定位中去。但是，提出完全异步的分布式定位算法的作者只在数值上展示了这个算法的收敛性，而没有展示理论上的收敛性。考虑到测量距离和节点之间的连通信息会产生各种约束限制条件，新的基于不可微优化的定位规划被提出，可以用在基于测距的定位和无需测距的定位中。不同于基于凸优化的定位算法，基于不可微优化的定位算法产生的不可微问题都可以利用规范化的递增梯度(NIS)算法得到有效解决。基于NIS的定位算法跟以往的算法（例如由dwMDS方法细化的非常强大的SDP方法、MDS-MAP方法等）相比，定位性能更好，但是，这种算法的分布式实现要求预先构建一条能连通所有节点的路径。上述这些定位算法都有准确的信标节点位置信息，但是事实上，信标节点位置不能精确得到，原因有两个方面，一是民用GPS的精度是有限的，二是人工观测会带来一定的误差。另一方面，节点的最大无线电范围存在不确定性，这是由无线电的不规则性决定的。在本文中，我们考虑当测量距离、无线电范围及信标节点位置存在不确定性时，对基于测距的定位产生的问题和无需测距的定位产生的问题进行研究。在贪婪优化算法的基础上，我们提出了两种分布式定位算法用于基于测距的定位和无需测距的定位，这两种分布式定位算法都可以实现部分的网络异步。最后，通过大量的模拟演示可以展现所提出的这两种分布式定位算法的效率和准确性。我们主要的贡献在于以下三个方面：（1）提出序列贪婪优化（SGO）算法，并对它的收敛性进行了证明和分析。SGO算法是非线性高斯-赛德尔算法的自然延伸，而且它更适应网络中的分布式优化。（2）为无线传感器网络提出一个统一的优化框架，并在半定规划（SDP）松弛技术的基础上得到两个凸定位规划。利用SGO算法，我们首次表明基于边缘的SDP（ESDP）松弛规划在网络中产生的问题可以用分布式的方法解决，主要就是通过解决一系列的二阶锥规划问题。（3）我们提出的分布式细化算法可以进一步提高定位精度，它将SGO算法运用到非凸定位规划中，适用于基于测距的定位和无需测距的定位。本文的其余部分安排如下：在下一节我们将展示SGO算法并证明它的收敛性。在第三节中，我们提出用于传感器网络定位的统一的优化框架，在此基础上得到两个凸规划；另一方面，利用ESDP公式和细化算法提出分布式定位算法。第四节提供了多组实验数值形象展示所提出的定位算法的性能，第五部分对整篇论文进行总结。在本文中，我们用大写黑体字表示向量矩阵，小写黑体字表示矢量，普通字体表示标量。n¡表示n维欧式空间，1niiXS表示笛卡尔积集。S表示S集的基数。下标T表示转置，0表示零矢量，ie表示由i个元素组成的一个单位列向量，它的大小根据上下文可知。mI表示mm大小的单位矩阵。对于一个对称矩阵A,,ijA表示矩阵A的第,ij项，12,,......,kiiiA表示从12,,......kiii行列中提取的主子矩阵。对于对称矩阵A和对称矩阵B，AB表示AB是正定的，AB表示矩阵A和矩阵B的Frobenius内积。对于向量a和向量b来说，ab表示的是判断不等式，ab表示向量a和向量b的分支乘法。2.序列贪婪优化算法对多变量问题人们已经提出了很多优化算法，但是这些优化算法中大多数还是属于基于搜索方向范畴的迭代算法。跟一般的迭代优化算法相比，存在一种特殊的迭代算法，这种迭代算法中，决策变量被划分为一个个独立的块，在每次迭代过程中，目标函数被最小化在区域中某一个独立块中，而其余的独立块依旧固定不动。这种类型的算法有时也被称为交替最小化算法、协调下降算法、或非线性高斯—赛德尔（NGS）算法。值得注意的是，前两个算法(交替最小化算法、协调下降算法)是最后一个算法(NGS算法)的特殊情况，因此，我们只讨论NGS算法。NGS算法适用于无约束最优化问题或笛卡尔积集约束问题，它之所以是贪婪的优化算法主要表现在它可以保证目标函数在每一次迭代之后不增加，最重要的一点是，使用NGS算法，一个复杂的多变量问题可以分解成一系列小规模的子问题，而且这个分解实施过程也很容易实现，即使是在分布式算法中（把子问题分配给不同的处理器）也很容易实现。在本节中，我们将NGS算法扩展为一个更一般的形式，也就是把生成算法当做SGO算法。在SGO算法中，决策变量并没有被严格地分割成独立的模块，换句话说，也就是SGO算法允许一些决策变量在不同的子问题中独立扩展，这个扩展是很自然的，因为它使SGO算法变得更适合分布式网络优化。本节的另外一项重要工作就是使用一阶的Karush—Kuhn—Tucker(KKT)条件，但是不对凸目标函数和约束集进行假设，在这种条件下对SGO算法的收敛性进行分析和证明。除此之外，我们还讨论在约束耦合(即不是笛卡尔乘积型)条件下，SGO算法在一般优化问题中的应用。A、算法如果一个优化问题可以写成以下形式，我们就说它属于稀疏约束。mins.t.g0,,1,2,......iiiifxxhxoin（1）其中12,,......,idnnxxxxx¡，id是一个正整数，1,2,......in；:,1DinfDdi　；:,:,0,1,2......,iiiidmdliighin　　是可微函数；im和il，1,2,......,in，是非负整数。我们假设fx的最小值存在，并且是有限的。请注意，00iiml意味着ix没有不等式（等式）条件的约束；尤其当所有的im和il都是0的情况下，公式（1）可以理解为一种特殊的稀疏约束问题，即一个无约束的优化问题。在NGS算法中，将子问题依次最小化，假设fx是每一个ix的严格凸函数。但是，如果给定一个fx，就很难获得子问题的全局最优解。在这里，我们将使用一个新的运算符