本发明公开了基于Barzilai‑Borwein梯度法的无线传感器网络分布式定位方法，其特征在于，包括如下步骤：1）定义网络；2）将WSN中节点定位问题归结为无约束的优化问题；3）重新构造无约束优化问题，进而给出子图中的无约束优化问题；4）采用极大似然估计法估计出未知位置节点的初始位置；5）采用分布式方法对优化问题进行迭代求解，获取最终定位。这种方法能解决大规模无线传感器网络中节点难以定位的问题，且定位精度高、计算复杂度低。
1.基于Barzilai-Borwein梯度法的无线传感器网络分布式定位方法，其特征在于，包括如下步骤：
1)在需要检测的区域内随机部署N个传感器节点，构成无线传感器网络，对其中m个节点添加BDS或GPS模块作为已知位置节点，剩余的n个节点作为未知位置节点，即待定位节点；
2)假定无线传感器网络中部署的所有传感器节点为一个集合，如果传感器节点之间可以直接相互通信，则可看作有一条边连接，从而可将整个无线传感器网络看做为一个全局的无向图，并将传感器节点的定位问题归结为无约束优化问题，即：在监控区域 维空间中部署传感器节点，这些节点构成WSN，WSN中共有N个节点，其中有m个LA节点，n个LU节点，LA节点位置表示为aλ，λ＝1，2，3，…，m；LU节点位置表示为xi，i＝1，2，3，…，n，LU节点i与节点j之间的欧式距离表示为dij；LU节点i与LA节点λ之间的欧式距离表示为diλ，假设传感器节点的最大通信半径为R，则对于每个LU节点i定义两个集合： 和其中 表示在通信半径R内，可以直接和节点i通信的
LU节点邻居集合； 表示在通信半径R内，可以直接和节点i通信的LA节点邻居集合，则将WSN中节点定位问题可以归结为一个无约束的优化问题：其中，ωij和ωiλ是权重，dij和diλ是带噪声的测距；
3)设与未知位置节点直接相连的节点为邻居节点，以未知位置节点为中心，以未知位置节点的通信半径作圆，将圆内所有节点和节点之间的边记为一个子图，从而将无线传感器网络构成的全局无向图分解为n个部分重叠的子图，然后对步骤2)中归结出的无约束优化问题进行重新构造，进而给出子图中的无约束优化问题：WSN可由无向图 来描述，其中， 表示WSN中LU节点集合， 表
集合，其中，eiλ表示LU节点i与LA节点λ之间可以直接通信，eij表示LU节点i和LU节点j之间可以直接通信，传感器节点只能与通信半径R内的节点直接通信，采用以LU节点为中心将WSN划分为部分重叠的子图：其中， 表示子图Gs中LU节点的集合， 表示子图Gs中LA节点集合，表示集合 中节点之间边的集合，然后，将定位问题公式(1)重新构造为：其中，dij和diλ分别为子图Gs中，采用测距方式获得的LU节点之间，以及LU节点与LA节点之间的距离，测得的距离并非节点之间的真实距离，而是带噪声测距，噪声模型如公式(5)、公式(6)所示，LA节点即使加上GPS模块，得到的LA位置也是有噪声的，噪声模型如公式(7)所示，dij＝||xi-xj||2·|1+τ1εij| (5)，diλ＝||xi-aλ||2·|1+τ1εiλ| (6)，其中，τ1∈[0，1]是距离噪声因子，用于控制测距之间的噪声强度； 是LA节点的真实位置；τ2∈[0，1]是LA节点位置噪声因子，用于控制LA节点位置的噪声强度；εij、εiλ和ελ是随机噪声，是一个正态随机变量N(0，1)，公式(4)中ωij和ωiλ是子图Gs中根据节点之间距离的反比取的归一化权重，权重分别为：将WSN构成的全局无向图分解为部分重叠的子图后，根据公式(4)，可以将定位问题分解为一系列子图Gs内的定位问题，采用分布式方法进行求解，子图Gs内的定位问题如公式(10)所示：其中， 为子图Gs中LU节点的集合； 为子图Gs中节点之间边的集合；dij为子图Gs中LU节点i和j之间的带噪声测距；diλ为子图Gs中LU节点i和LA节点λ之间的带噪声测距，使用表示子图Gs中LU节点数目； 表示子图Gs中LA节点数目；xi＝[xi1，xi2]表示LU节点xi的坐标；aλ＝[aλ1，aλ2]表示LA节点aλ的坐标； 表示子图Gs中所有LU节点坐标构成的列向量； 表示子图Gs中所有LA节点坐标构成的列向量； 表示2n1×2n1的单位矩阵； 表示2n2×2n2的单位矩阵；ei1和ei2分别表示 的第2i-1列和第2i列；eλ1和eλ2分别表示 的第2λ-1列和第2λ列，根据上述定义， 则传感器节点间的真实距离可写为：
A＝(ei1-ej1)(ei1-ej1) +(ei2-ej2)(ei2-ej2) (13)，公式(10)可以写为：
4)采用极大似然估计法，估计出未知位置节点的初始位置p(t)，将初始位置p(t)作为步骤3)中未知位置节点的初始值，其中，t表示迭代次数，令t＝0：假设D点为LU节点，坐标为(xy，在D点的通信半径R内有m个LA节点，坐标分别为(x1，y1)，(x2，y2)，(x3，y3)，…，(xm，ym)，采用测距法测得D点至m个LA节点的带噪声测距分别为d1，d2，d3，…，dm，则测得的距离与D点坐标和m个LA节点坐标之间有以下关系：将前m-1个方程与第m分方程相减，得到以下方程组：
1-4)当LU节点有3个或3个以上的LA邻居时，使用最大似然估计法计算LU节点的初始位置；
2-4)当LU节点有1-2个LA邻居时，将距离LU节点最近的LA节点的位置作为其初始位置；
3-4)当LU节点没有LA邻居时，将传感器节点分布区域的中心作为LU节点的初始位置；
5)采用分布式方法对步骤3)中归结出的优化问题公式(4)进行迭代求解，过程为：
1-5)采用Barziiai-Borwein梯度法对步骤3)中归结出的子图Gs中的优化问题即公式(10)进行求解，梯度法计算步长公式如下：
如果k＝0，则通过回溯直线搜索法确定步长α0，设置参数μ＝0.2，β＝0.5，α0＝1，若下式成立，则令α0＝βα0，循环直到下式不成立：子图中使用Barzilai-Borwein梯度法进行优化求解的过程如下：
1-1-5)使用极大似然估计法，粗略获得LU节点的初始值，提取子图Gs中LU节点的位置xk，作为初始值，设k＝0，表示第k次迭代；
3-1-5)计算步长：如果k＝0，通过回溯直线搜索法确定步长α0；否则通过公式(27)计算步长αk；
4-1-5)更新子图Gs中LU节点位置：xk+1＝xk+αkqk；
5-1-5)判断迭代终止条件：如果满足 ε是一个正数，或k＞100，则终止迭代，xk+1即为迭代结果，否则令k＝k+1返回到步骤2-1-5)；
2-5)采用子图融合的方法，对部分重叠的子图进行融合，得到第t+1次迭代的未知位置(t+1)节点的估计位置p ，具体为：子图融合公式如下：
其中， 表示包含LU节点i的子图索引集合；xi，s表示子图Gs中LU节点i的坐标； 表示LU节点i融合之后的坐标；
3-5)迭代终止：若 δ是正数，δ取1e-2，则p(t+1)为最终估计出的未知位置节点的位置，否则，将p(t+1)作为新的初始值，并令t＝t+1，返回至步骤1-5)继续迭代，其中，i＝1，2，3，…，n表示无线传感器网络中未知位置节点的标号； 表示未知位置节点i在第t+1次迭代的估计值，p(t)表示未知位置节点i在第t次迭代的估计值。
基于Barzilai-Borwein梯度法的无线传感器网络分布式定位
方法
技术领域
[0001] 本发明涉及无线传感器网络技术领域，具体涉及一种基于Barzilai-Borwein梯度法的无线传感器网络分布式定位方法。
背景技术
[0002] 无线传感器网络(Wireless Sensor Networks，简称WSN)是由大量微小的传感器构成的自组织网络。WSN中传感器节点可以检测监控区域中的物理信息并进行数据处理，将处理后的数据以无线通信的方式传送到基站。近年来，无线通信技术，纳米技术和微机电系统(Micro-Electro-Mechanical Systems，简称MEMS)技术得到了快速发展，这些技术降低了传感器的体积、功耗和成本，使传感器可以大规模部署。WSN有许多应用，如医学应用中的病人检测，环境应用中火山检测，家庭应用中用水检测等。
[0003] 在上述广泛应用中，检测到的信息需要与传感器节点的位置结合起来，才能提供更有效的数据信息，因此，WSN中传感器节点的定位方法受到了广泛关注。例如可以在传感器中嵌入中国北斗卫星导航系统(BeiDou Navigation Satellite System，简称BDS)模块或全球定位系统(Global Positioning System，简称GPS)模块进行定位，但这些模块成本高，功耗大，无法适用于大规模的WSN，因此，选择少量的传感器节点嵌入BDS或GPS模块，这些节点称为锚节点或已知位置(Location-Aware，简称LA)节点，可以获得较精确的位置信息，其它传感器节点则称为未知位置(Location-Unaware，简称LU)节点，之后采用测距技术，如：接收信号强度(Received-Signal-Strength，简称RSS)等测得WSN中传感器节点之间的距离，最后使用定位方法估计出WSN中LU节点的位置。
[0004] 目前，已有许多定位方法，从数据处理角度，可以将定位方法分为集中式定位方法和分布式定位方法。集中式定位方法将定位所需信息通过多跳的方式传递给存储、计算能力较强的中央处理器进行处理，赵海兵和蒋俊正提出了一种基于图模型的集中式定位方法，将定位问题归结为无约束的优化问题，之后采用修正牛顿法进行求解，得到了较好的定位精度和定位速率，但该方法需要对Hessian矩阵求逆，导致计算复杂度较高；而分布式定位方法使用传感器节点自带的处理器，对收集到的局部信息进行处理，分布式定位方法有效降低了通信代价和计算复杂度，具备良好的扩展性，可用于大规模WSN，但缺点是利用的信息较少，定位精度会降低。Srirangarajan S，Tewfik A H，和Luo Z Q将非凸的定位问题松弛为凸的二阶锥规划(Second-Order Cone Programming，简称SOCP)问题，利用LU节点及其邻居信息，设计分布式SOCP定位方法进行求解，该方法可用于大规模WSN中，但定位精度较低；Soares C，Xavier J，和Gomes J提出了一种分布式定位方法，在每个LU节点上，将非凸的定位问题松弛为凸的定位问题，并使用梯度法进行求解，在通信半径较小的情况下也有较好的定位效果，降低了通信代价，但该方法部署的LU节点需要在LA节点形成的凸包中，才能有好的定位效果；Sanyal R,Jaiswal M,and Chaudhury K N.将WSN划分为子图，每个子图需要满足文中提出的刚性条件，使用多维标度方法对每个子图进行定位，然后将局部坐标映射到全局坐标系统，该方法所需的LA节点数目较少，且划分的子图数目较少，定位精度较高，但该方法当通信半径较小，子图无法满足刚性条件时，无法定位。
发明内容
[0005] 本发明的目的是针对现有技术的不足，而提供一种基于Barzilai-Borwein梯度法的无线传感器网络分布式定位方法。这种方法能解决大规模无线传感器网络中节点难以定位的问题，且定位精度高、计算复杂度低。
[0006] 实现本发明目的的技术方案是：
[0007] 基于Barzilai-Borwein梯度法的无线传感器网络分布式定位方法，包括如下步骤：
[0008] 1)在需要检测的区域内随机部署N个传感器节点，构成无线传感器网络，对其中m个节点添加BDS或GPS模块作为已知位置节点，剩余的n个节点作为未知位置节点，即待定位节点；
[0009] 2)假定无线传感器网络中部署的所有传感器节点为一个集合，如果传感器节点之间可以直接相互通信，则可看作有一条边连接，从而可将整个无线传感器网络看做为一个全局的无向图，并将传感器节点的定位问题归结为无约束优化问题，即：在监控区域维空间中部署大量的传感器节点，这些节点构成WSN，WSN中共有N个节点，其中有m个LA节点，n个LU节点，LA节点位置表示为aλ，λ＝1，2，3，…，m；LU节点位置表示为xi，i＝
1，2，3，…，n，LU节点i与节点j之间的欧式距离表示为dij；LU节点i与LA节点λ之间的欧式距离表示为diλ，假设传感器节点的最大通信半径为R，则对于每个LU节点i定义两个集合:
和 其中 表示在通
信半径R内，可以直接和节点i通信的LU节点邻居集合； 表示在通信半径R内，可以直接和节点i通信的LA节点邻居集合，利用这些信息可将WSN中节点定位问题可以归结为一个无约束的优化问题：
[0010]
[0011] 其中，ωij和ωiλ是权重，因为dij和diλ是带噪声的测距，因此给可信度较高的测距设置较大的权重；反之，给可信度较低的测距设置较小的权重；
[0012] 3)设与未知位置节点直接相连的节点为邻居节点，以未知位置节点为中心，以未知位置节点的通信半径作圆，将圆内所有节点和节点之间的边记为一个子图，从而将无线传感器网络构成的全局无向图分解为n个部分重叠的子图，然后对步骤2)中归结出的无约束优化问题进行重新构造，进而给出子图中的无约束优化问题：WSN可由无向图来描述，其中， 表示WSN中LU节点集合， 表
示WSN中LA节点集合， 表示节点之间边的
集合，其中，eiλ表示LU节点i与LA节点λ之间可以直接通信，eij表示LU节点i和LU节点j之间可以直接通信，传感器节点只能与通信半径R内的节点直接通信，采用以LU节点为中心将WSN划分为部分重叠的子图：
[0013]
[0014]
[0015] 其中， 表示子图Gs中LU节点的集合， 表示子图Gs中LA节点集合， 表示集合 中节点之间边的集合，然后，将定位问题公式(1)重新构造为：
[0016]
[0017] 其中，dij和diλ分别为子图Gs中，采用测距方式获得的LU节点之间，以及LU节点与LA节点之间的距离，测得的距离并非节点之间的真实距离，而是带噪声测距，噪声模型如公式(5)、公式(6)所示，而且LA节点即使加上GPS模块，由于受到电离层误差、对流层误差、接收机钟差等多种误差的影响，得到的LA位置也是有噪声的，噪声模型如公式(7)所示，[0018] dij＝||x-xj||2·|1+τ1εij| (5),
[0019] dλ＝||xi-αλ||2·|1+τ1εiλ| (6),
[0020]
[0021] 其中，τ1∈[0，1]是距离噪声因子，用于控制测距之间的噪声强度； 是LA节点的真实位置；τ2∈[0，1]是LA节点位置噪声因子，用于控制LA节点位置的噪声强度；εij、εiλ和ελ是随机噪声，是一个正态随机变量N(0，1)，
[0022] 公式(4)中ωi和ωiλ是子图Gs中根据节点之间距离的反比取的归一化权重，两个节点之间相距越近，测得的距离可信度越高，应该赋予较高的权重，反之，应该赋予较低的权重，权重分别为：
[0023]
[0024]
[0025] 将WSN构成的全局无向图分解为部分重叠的子图后，根据公式(4)，可以将定位问题分解为一系列子图Gs内的定位问题，采用分布式方法进行求解，子图Gs内的定位问题如公式(10)所示：
[0026]
[0027] 其中， 为子图Gs中LU节点的集合； 为子图Gs中节点之间边的集合；dij为子图Gs中LU节点i和j之间的带噪声测距；diλ为子图Gs中LU节点i和LA节点λ之间的带噪声测距，使用 表示子图Gs中LU节点数目； 表示子图Gs中LA节点数目；xi＝[xi1，xi2]表示LU节点xi的坐标；aλ＝[aλ1，aλ2]表示LA节点aλ的坐标； 表示
子图Gs中所有LU节点坐标构成的列向量； 表示子图Gs中所有
LA节点坐标构成的列向量； 表示2n1×2n1的单位矩阵； 表示2n2×2n2的单位矩阵；ei1和ei2分别表示 的第2i-1列和第2i列；eλ1和eλ2分别表示 的第2λ-1列和第2λ列，根据上述定义， 则传感器节点间的真实距离可写
为：
[0028]
[0029]
[0030] 其中，
[0031] A＝(ei1-ej1)(ei1-ej1)T+(ei2-ej2)(ei2-ej2)T (13)，
[0032]
[0033]
[0034]
[0035]
[0036] 公式(10)可以写为：
[0037]
[0038] fs(x)的梯度向量 为：
[0039]
[0040] 4)采用极大似然估计法，估计出未知位置节点的初始位置p(t)，将初始位置p(t)作为步骤3)中未知位置节点的初始值，其中，t表示迭代次数，令t＝0：采用极大似然估计法获得LU节点的估计值，目的是为了得到更好的初始值，假设D点为LU节点，坐标为(x，y)，在D点的通信半径R内有m个LA节点，坐标分别为(x1，y1)，(x2，y2)，(x3，y3)，…，(xm，ym)，采用测距法测得D点至m个LA节点的带噪声测距分别为d1，d2，d3，…，dm，则测得的距离与D点坐标和m个LA节点坐标之间有以下关系：
[0041]
[0042] 将前m-1个方程与第m分方程相减，得到以下方程组：
[0043]
[0044] 公式(21)可写为矩阵形式：
[0045] AX＝b (22)，
[0046] 其中，
[0047]
[0048]
[0049]
[0050] 最小二乘解即为LU节点D的估计值：
[0051]
[0052] 在实际情况中，传感器节点随机部署，难以保证每个LU节点都有3个或3个以上的LA邻居，采用以下规则估计LU节点的初始位置：
[0053] 1-4)当LU节点有3个或3个以上的LA邻居时，使用最大似然估计法计算LU节点的初始位置；
[0054] 2-4)当LU节点有1-2个LA邻居时，将距离LU节点最近的LA节点的位置作为其初始位置；
[0055] 3-4)当LU节点没有LA邻居时，将传感器节点分布区域的中心作为LU节点的初始位置；
[0056] 5)采用分布式方法对步骤3)中归结出的优化问题公式(4)进行迭代求解，过程为：
[0057] 1-5)采用Barzilai-Borwein梯度法对步骤3)中归结出的子图G中的优化问题即公式(10)进行求解，将WSN划分为部分重叠的子图后，子图中定位问题公式(10)规模远小于原定位问题公式(1)的规模，因此，可以用简单的梯度法进行优化求解，梯度法计算步长公式如下：
[0058]
[0059] 如果k＝0，则通过回溯直线搜索法确定步长α0，设置参数μ＝0.2，β＝0.5，α0＝1，若下式成立，则令α0＝βα0，循环直到下式不成立：
[0060]
[0061] 综上所述，子图中使用Barzilai-Borwein梯度法进行优化求解的步骤如下：
[0062] 1-1-5)使用极大似然估计法，粗略获得LU节点的初始值，提取子图G中LU节点的位置xk，作为初始值，设k＝0，表示第k次迭代；
[0063] 2-1-5)计算搜索方向qk：
[0064] 3-1-5)计算步长：如果k＝0，通过回溯直线搜索法确定步长α0；否则通过公式(27)计算步长αk；
[0065] 4-1-5)更新子图Gs中LU节点位置：xk+1＝xk+αkqk；
[0066] 5-1-5)判断迭代终止条件：如果满足 ε是一个正数，或k＞100，则终止迭代，xk+1即为迭代结果，否则令k＝k+1返回到步骤2-1-5)；
[0067] 2-5)采用子图融合的方法，对部分重叠的子图进行融合，得到第t+1次迭代的未知位置节点的估计位置p(t+1)，具体为：同一个LU节点会位于不同的子图中，因此，对每个子图优化求解后，对于相同的LU节点会有不同的估计值，对子图进行融合，进而得到每个LU节点的估计值，子图融合可以提高整体WSN的定位精度，子图融合公式如下：
[0068]
[0069] 其中， 表示包含LU节点i的子图索引集合；xi，s表示子图Gs中LU节点i的坐标；表示LU节点i融合之后的坐标；
[0070] 3-5)迭代终止：若 δ是正数，δ取1e-2，则p(t+1)为最终估计出的未知位置节点的位置，否则，将p(t+1)作为新的初始值，并令t＝t+1，返回至步骤1-5)继续迭代，其中，i＝1，2，3，…，n表示无线传感器网络中未知位置节点的标号； 表示未知位置节点i在第t+1次迭代的估计值，p(t)表示未知位置节点i在第t次迭代的估计值。这种方法能解决大规模无线传感器网络中节点难以定位的问题，且定位精度高、计算复杂度低。
附图说明
[0071] 图1为实施例中节点分布示意图；
[0072] 图2为实施例中子图划分示意图；
[0073] 图3为实施例中极大似然估计法示意图；
[0074] 图4为实施例中本例方法和现有方法1、现有方法2、现有方法3在不同锚节点比例下的定位整体性能对比示意图。
具体实施方式
[0075] 下面结合附图和实施例对本发明的内容作进一步的阐述，但不是对本发明的限定。
[0076] 实施例：
[0077] 基于Barzilai-Borwein梯度法的无线传感器网络分布式定位方法，包括如下步骤：
[0078] 1)在需要检测的区域内随机部署N个传感器节点，构成无线传感器网络，对其中m个节点添加BDS或GPS模块作为已知位置节点，剩余的n个节点作为未知位置节点，即待定位节点，如图1所示，传感器节点分布在[-0.5，0.5]2单位区域内，其中圆圈表示LU节点，实心菱形表示LA节点；
[0079] 2)假定无线传感器网络中部署的所有传感器节点为一个集合，如果传感器节点之间可以直接相互通信，则可看作有一条边连接，从而可将整个无线传感器网络看做为一个全局的无向图，并将传感器节点的定位问题归结为无约束优化问题，即：在监控区域维空间中部署大量的传感器节点，这些节点构成WSN，WSN中共有N个节点，其中有m个LA节点，n个LU节点，LA节点位置表示为aλ，λ＝1，2，3，…，m；LU节点位置表示为xi，i＝1，2，3，…，n，LU节点i与节点j之间的欧式距离表示为di；LU节点i与LA节点λ之间的欧式距离表示为diλ，假设传感器节点的最大通信半径为R，则对于每个LU节点i定义两个集合：
和 其中 表示在通
信半径R内，可以直接和节点i通信的LU节点邻居集合； 表示在通信半径R内，可以直接和节点i通信的LA节点邻居集合，利用这些信息可将WSN中节点定位问题可以归结为一个无约束的优化问题：
[0080]
[0081] 其中，ωij和ωiλ是权重，因为dij和diλ是带噪声的测距，因此给可信度较高的测距设置较大的权重；反之，给可信度较低的测距设置较小的权重；
[0082] 3)设与未知位置节点直接相连的节点为邻居节点，以未知位置节点为中心，以未知位置节点的通信半径作圆，将圆内所有节点和节点之间的边记为一个子图，从而将无线传感器网络构成的全局无向图分解为n个部分重叠的子图，然后对步骤2)中归结出的无约束优化问题进行重新构造，进而给出子图中的无约束优化问题：WSN可由无向图来描述，其中， 表示WSN中LU节点集合，
表示WSN中LA节点集合，
表示节点之间边的集合，其中，eiλ表示LU节点i与LA节点λ之间可以直接通信，eij表示LU节点i和LU节点j之间可以直接通信，传感器节点只能与通信半径R内的节点直接通信，采用以LU节点为中心将WSN划分为部分重叠的子图：
[0083]
[0084]
[0085] 其中， 表示子图Gs中LU节点的集合， 表示子图Gs中LA节点集合， 表示集合 中节点之间边的集合，如图2所示，传感器节点分布在[-0.5，0.5]2单位区域内，其中圆圈表示LU节点，实心菱形表示LA节点，通信半径R＝0.3，虚线圆表示以LU节点为圆心，R为半径，划分出的部分重叠的子图，然后，将定位问题公式(1)重新构造为：
[0086]
[0087] 其中，dij和diλ分别为子图Gs中，采用测距方式获得的LU节点之间，以及LU节点与LA节点之间的距离，测得的距离并非节点之间的真实距离，而是带噪声测距，噪声模型如公式(5)、公式(6)所示，而且LA节点即使加上GPS模块，由于受到电离层误差、对流层误差、接收机钟差等多种误差的影响，得到的LA位置也是有噪声的，噪声模型如公式(7)所示，[0088] dij＝||xi-xj||2·|1+τ1εij| (5)，
[0089] diλ＝||xi-aλ||2·|1+τ1εiλ| (6)，
[0090]
[0091] 其中，τ1∈[0，1]是距离噪声因子，用于控制测距之间的噪声强度； 是LA节点的真实位置；τ2∈[0，1]是LA节点位置噪声因子，用于控制LA节点位置的噪声强度；εij、εiλ和ελ是随机噪声，是一个正态随机变量N(0，1)，
[0092] 公式(4)中ωij和ωiλ是子图Gs中根据节点之间距离的反比取的归一化权重，两个节点之间相距越近，测得的距离可信度越高，应该赋予较高的权重，反之，应该赋予较低的权重，权重分别为：
[0093]
[0094]
[0095] 将WSN构成的全局无向图分解为部分重叠的子图后，根据公式(4)，可以将定位问题分解为一系列子图Gs内的定位问题，采用分布式方法进行求解，子图Gs内的定位问题如公式(10)所示：
[0096]
[0097] 其中， 为子图Gs中LU节点的集合； 为子图Ga中节点之间边的集合；dij为子图Gs中LU节点i和j之间的带噪声测距；diλ为子图Gs中LU节点i和LA节点λ之间的带噪声测距，使用 表示子图Gs中LU节点数目；s 表示子图Gs中LA节点数目；xi＝[xi1，xi2]表示LU节点xi的坐标；aλ＝[aλ1，aλ2]表示LA节点aλ的坐标； 表示
子图Gs中所有LU节点坐标构成的列向量； 表示子图Gs中所有
LA节点坐标构成的列向量； 表示2n1×2n1的单位矩阵； 表示2n2×2n2的单位矩阵；ei1和ei2分别表示 的第2i-1列和第2i列；eλ1和eλ2分别表示 的第2λ-1列和第2λ列，根据上述定义， 则传感器节点间的真实距离可写
为：
[0098]
[0099]
[0100] 其中，
[0101] A＝(ei1-ej1)(ei1-ej1)T+(ei2-ej2)(ei2-ej2)T (13)，
[0102]
[0103]
[0104]
[0105]
[0106] 公式(10)可以写为：
[0107]
[0108] fs(x)的梯度向量 为：
[0109]
[0110] 4)采用极大似然估计法，估计出未知位置节点的初始位置p(t)，将初始位置p(t)作为步骤3)中未知位置节点的初始值，其中，t表示迭代次数，令t＝0：采用极大似然估计法获得LU节点的估计值，目的是为了得到更好的初始值，其定位原理如图3所示，假设D点为LU节点，坐标为(x，y)，在D点的通信半径R内有m个LA节点，坐标分别为(x1，y1)，(x2，y2)，(x3，y3)，…，(xm，ym)，采用测距法测得D点至m个LA节点的带噪声测距分别为d1，d2，d3，…，dm，则测得的距离与D点坐标和m个LA节点坐标之间有以下关系：
[0111]
[0112] 将前m-1个方程与第m分方程相减，得到以下方程组：
[0113]
[0114] 公式(21)可写为矩阵形式：
[0115] AX＝b (22)，
[0116] 其中，
[0117]
[0118]
[0119]
[0120] 最小二乘解即为LU节点D的估计值：
[0121]
[0122] 在实际情况中，传感器节点随机部署，难以保证每个LU节点都有3个或3个以上的LA邻居，采用以下规则估计LU节点的初始位置：
[0123] 1-4)当LU节点有3个或3个以上的LA邻居时，使用最大似然估计法计算LU节点的初始位置；
[0124] 2-4)当LU节点有1-2个LA邻居时，将距离LU节点最近的LA节点的位置作为其初始位置；
[0125] 3-4)当LU节点没有LA邻居时，将传感器节点分布区域的中心作为LU节点的初始位置；
[0126] 5)采用分布式方法对步骤3)中归结出的优化问题公式(4)进行迭代求解，过程为：
[0127] 1-5)采用Barzilai-Borwein梯度法对步骤3)中归结出的子图G中的优化问题即公式(10)进行求解，将WSN划分为部分重叠的子图后，子图中定位问题公式(10)规模远小于原定位问题公式(1)的规模，因此，可以用简单的梯度法进行优化求解，梯度法计算步长公式如下：
[0128]
[0129] 如果k＝0，则通过回溯直线搜索法确定步长α0，设置参数μ＝0.2，β＝0.5，α0＝1，若下式成立，则令α0＝βα0，循环直到下式不成立：
[0130]
[0131] 综上所述，子图中使用Barzilai-Borwein梯度法进行优化求解的步骤如下：
[0132] 1-1-5)使用极大似然估计法，粗略获得LU节点的初始值，提取子图G中LU节点的位置xk，作为初始值，设k＝0，表示第k次迭代；
[0133] 2-1-5)计算搜索方向qk：
[0134] 3-1-5)计算步长：如果k＝0，通过回溯直线搜索法确定步长α0；否则通过公式(27)计算步长αk；
[0135] 4-1-5)更新子图GS中LU节点位置：xk+1＝xk+αkqk；
[0136] 5-1-5)判断迭代终止条件：如果满足 ε是一个正数，或k＞100，则终止迭代，xk+1即为迭代结果，否则令k＝k+1返回到步骤2-1-5)；
[0137] 2-5)采用子图融合的方法，对部分重叠的子图进行融合，得到第t+1次迭代的未知位置节点的估计位置p(t+1)，具体为：同一个LU节点会位于不同的子图中因此，对每个子图优化求解后，对于相同的LU节点会有不同的估计值，对子图进行融合，进而得到每个LU节点的估计值，子图融合可以提高整体WSN的定位精度，子图融合公式如下：
[0138]
[0139] 其中， 表示包含LU节点i的子图索引集合；xi，s表示子图Gs中LU节点i的坐标；表示LU节点i融合之后的坐标；
[0140] 3-5)迭代终止条件：若 δ是正数，本例为1e-2，则p(t+1)为最终估计出的未知位置节点的位置，否则，将p(t+1)作为新的初始值，并令t＝t+1，返回至步骤
1-5)继续迭代，其中，i＝1，2，3，…，n表示无线传感器网络中未知位置节点的标号； 表示未知位置节点i在第t+1次迭代的估计值，p(t)表示未知位置节点i在第t次迭代的估计值。
[0141] 仿真验证例1：
[0142] 在相同的仿真环境下，本次仿真将改变LA节点数目在网络中占总结点数目的比例进行仿真，并与现有方法进行对比，如图4所示，其中，现有方法1为蒋俊正和赵海兵提出的集中式定位方法；现有方法2为Srirangarajan S，Tewfik A H，和Luo Z Q提出的一种分布式定位方法；现有方法3为Soares C，Xavier J，和Gomes J提出的另一种分布式定位方法，可以看出，随着LA数目所占比例的增加，采用本例方法的定位精度会得到提高，这是因为LA数目的增加，能够提供更多的已知位置的信息，使得LU节点有更好的初始位置和更多更准确的邻居信息，从而提高了定位精度，本例方法与现有方法1相比，在相同的LA数目下，有近似的定位精度；与现有方法2和现有方法3相比，在相同的LA数目下，本例方法的平均定位误差更小，定位精度更高，这意味着，在大规模WSN中，本例方法可以利用较少的LA节点数目，达到较好的定位效果，从而降低WSN的部署成本。
[0143] 仿真验证例2：
[0144] 在相同的仿真环境下，本次仿真改变各个参数，并与现有方法进行对比，表1展示了本例方法与现有方法1、现有方法2和现有方法3的对比结果，其中，“*”表示内存溢出，无法定位，可以看出，在相同规模的WSN中，对LA节点位置添加噪声后，各方法的定位精度均会下降；在小规模WSN(N＜500)中，本例方法与现有方法1提出的集中式定位方法相比，有接近的定位精度，但在大规模WSN(N≥500)中，集中式定位方法便无法定位，而本例方法仍有较好的定位精度，而且与现有方法2和现有方法3提出的分布式定位方法相比，在相同的仿真参数下，始终有更好的定位精度，综上所述，本例分布式定位方法有良好的扩展性，可有效用于大规模的WSN中，并且有较高的定位精度。
[0145] 表1本例方法与现有方法在不同参数下仿真结果对比
[0146]
[0147]
