子图划分优化WSN 节点分布式定位算法

李 斌，赵 娜

（1.东莞职业技术学院计算机工程系，广东 东莞 523808；2.吉林大学计算机科学与技术学院，吉林 长春 130012）

1 引言

机械振动监测及矿井提升机等系统通常采用有线方式传输其采集的信息，成本高、灵活性差且监测范围有限，严重影响信号传输质量，对大型设备尤其是旋转部件，在无振动方向及振动状态时，限制尤为明显[1]。随着物联网的发展和成熟运用，无线传感器网络（Wireless Sensor Network，WSN 技术被应用到提升机等设备检测和振动监测中，并取得良好的效果[2-3]。

WSN 自组织网络已经在环境监测、军事、地质探测及空间探索等方面应用广泛[3]，节点定位是WSN 网络从固定式应用到移动式部署的关键技术之一，节点定位的准确性及其可靠性关系到网络的监测性能和稳定性的重要指标，由于在移动过程中，网络的拓扑是随时变化时，传统基于固定WSN 网络的节点定位算法在实际应用中需要频繁信息交互，并设置繁杂的定位校验方法以提升定位精确性[4]。因此，WSN 中节点定位相关技术的研究对WSN移动部署应用具有重要意义[5]。

文献[6]采用集中式信息存储方式进行WSN 节点定位处理，采用盒式锚区和三角定位的方式对节点位置信息进行捕捉，但通信频繁且适于节点稀疏环境下的定位，高密度节点易产生严重的链路抖动现象；文献[7]针对高变化拓扑环境的快速移动节点定位问题，通过射频覆盖获取最佳性能锚节点坐标，通过拉格朗日插值捕捉节点的轨迹矢量信息，并采用正交覆盖进行优化，取得较好的定位精度；文献[8]将基于最小二乘的迭代预测引入到移动WSN 锚节点定位信息采样中，提高了采样有效性和定位精确度，对低密度网络仍取得较好的结果，但对变化较快节点定位精度有待提高，以减少算法中待优化参数数；文献[9]以新设计的计跳公式计算未知节点的跳距，再通过最小二乘进行矩阵修正，最后由高斯牛顿法进行非线性方程求解，取得较好的未知节点定位精度。

分布式定位通过节点自身的计算进行定位，对计算能力要求不高，相比于依赖中央服务器的集中式定位更适于大规模WSN 中RNR 节点的定位[10]，为此，在已有算法基础上，为减少在大规模WSN 网络中已知节点的需求量，提出了基于误差加权和修正的分布式迭代节点定位算法，算法首先根据已知节点领域将WSN 无向图划分为多个子图，然后通过子图内定位循环迭代方法求解NRN节点的精确位置信息，实现算法的高效精确定位，仿真实验算法的有效性及对不同节点规模的WSN 网络具有较好的适应性。

2 WSN 节点定位

以xi=［x2i-1，x2i］和ai=［a2k-1，a2k］分别表示 WSN 平面内未知位置节点LUi和已知位置的节点LAi的横纵轴位置坐标，则包含N个已知的参考节点（Reference Node，RN）x1，x2，…，xN和M个型需实时重新定位的节点（Need to be Relocated Node，NRN）a1，a2，…，aM的 WSN 节点集为：

其网络中两NRN 节点M及NRN 节点与RN 节点间的欧氏距离可表示为：

式中：A、B、C、D—由单位矩阵生成的列矩阵，通信距离限制使得只有通信半径内的传感器节点可互相通信，即互为邻居节点，对于一个NRN 节点vi其未知邻居节点集和已知邻居节点集为：

式中：ρij、ρik—节点间直接通信的通信半径。

无线传感器网络可以通过节点的发射功率和接收功率差异在无额外测试设备辅助的情况下通过RSS 测距算法计算两节点之间的距离，但受多径及阴影等衰减特性的影响，功率差异测距并不很准确，为此，将衰减特征引入到距离计算，即：

式中：εij、εik—随机噪声，即通过随机噪声的叠加来描述发射信号在传播过程中的衰减特征；τ∈［0，1］—噪声强度控制因子。降低部署成本和功耗，在保证满足定位需求情况下，已知参数的传感器节点的部署量通常尽可能减少。

3 节点分布式定位

以已知具有计算能力的节点为中心，将与其构成邻居节点的所有节点组成图G的子图Gm，Gm=（Vm，Em），则M个 RN 节点可以形成M个子图，根据节点的通信半径可调整RN 节点数及位置，使得每个NRN 节点至少落入两个子图中，以保证子图间的有效重叠，从而减少RN 节点的需求量。

3.1 子图定位算法

根据传统跳距计算试，WSN 的两节点间在通信半径内实现正常通信，则计其跳数为1，但根据RSS 测距原理，传感器节点之间通信距离相对越远，其通信信号受噪声干扰越大，测距精度相对越低，传统计数方式不合理，为此，将其修改为：

式中：N—WSN 网络中锚节点数量；（xi，yi）、（xz，yz）—锚节点与未知节点坐标。根据修改跳数计算式，文中子图内节点定位归结为一个距离误差加权值的无约束优化问题，其目标函数为：

式（7）的求解可以作为非线性方程组采用高斯牛顿法[9]进行求解，但直接使用高斯牛顿法会由于Dij误差导致定位精度不高，为此，采用最小二乘对未知节点到锚节点距离进行距离修正，修改后的距离计算误差为：

式中：（xls_z，yls_z）—最小二乘计算的距离值，则经过最小二乘修正后的锚节点距离值为：

根据式（9）的修正距离计算可以构建WSN 网络中未知节点xz=（xz，yz）到锚节点xi=（xi，yi）的距离求解迭代式为：

式中：‖·‖—求矩阵范数。根据式（10）可得到修改后的比较精确的节点距离，则子图内未知节点定位目标函数式（7）可以转化最式（11）所示的非线性方程求解问题，即：

式中：dz—最小二乘对式（10）计算的距离值的进一步优化值，则未知道节点的坐标值为：

式中：λ—迭代步长；J—雅克比矩阵。其定位方法，如图1 所示。图中A、B、C为三个已知信息的节点，其坐标分别为（xA，yA）、（xB，yB）和（xC，yC），P为待定位的 NRN 节点。

图1 基于RN 节点的初始定位示意图Fig.1 Schematic Diagram of Initial Positioning Based on RN Nodes

进而根据节点间的位置相对关系，可以求解坐标（x，y）值。可以看出，（x，y）的计算需要最邻近的三个RN 节点的RSS 距离信息，但其值不精确，距离误差的存在使得图2 中三圆难以保证恰好交于一点，因而其计算的定位坐标仅作为初始值，以便进一步迭代计算更精确值，为避免NRN 节点内仅有两个RN 节点情况的存在，将两RN 节点中心连线的中点作为精确定位算法的初始值。其计算过程为：

（1）以图2 所示方法计算NRN 节点的初始值，即xm.0，设置迭代初始值p=0；

（2）判断一阶参数是否满足‖△Jm，p‖＞ε，其中 ε，为一个非常小的值，文中取ε=10-10，如果满足，则进行一维迭代搜索，并计算搜索步长λp；

（3）判断p与维度n之间大小：（1）当p＜n时，计算dm，p+1=-△Jm，p+1+βdm，p，其中 βp=‖△Jm，p+1‖2/‖△Jm，p‖2为两次迭代之间的目标函数差异，令p：=p+1，转到（2）；（2）当p≥n时，令xm，0=xm，p+1，dm，0=-△Jm，p+1及p=0，转到（2）；

在（2）中，步长 λp应满足：

令 φ（λ）=J（xm，p+λp dm，p），则 φ（λ）取极小值即时的 λ，为所要计算的 λp。计算式（9）在xm，p+1=xm，p+λpdm，p处的梯度并取△φ（λ）=0，可得到λp值，如式（13）所示。

3.2 分布式算法流程总结

文中分布式节点定位算法，通过以RN 节点为中心构建其领域子图而将整个无线传感器网络无向图划分为多个子图，并通过构建合适的误差加权和目标函数将节点定位转换为子图内距离误差的无约束优化问题；在目标函数迭代优化过程中，采用共轭梯度法及粗定位信息作为迭代初始值，以确保算法迭代时以最速方向渐近局部最优解。其过程，如图2 所示。

4 仿真分析

为验证文中算法有效性，采用定位距离的均方根（RMSD）作为评价指标，采用松弛SOCP 算法[9]、同步凸松弛算法[10]及异步凸松弛算法[10]作为性能比较算法，实验环境HQ CPU@2.9G Hz，内存32G，仿真软件为matlab 2016a，WSNs采用正方形区域，包含M个已知节点和N个待定位的节点，添加强度为τ=0.25 的随机均匀噪声。

图2 分布式节点定位算法流程图Fig.2 Flow Chart of Distributed Node Positioning Algorithm

4.1 RN 节点占比对算法性能影响

为验证文中算法在不同占比下的定位性能，实验过程中，节点总数固定为M+N=800，节点间的通信半径设置为固定值dmax=0.30，实验已知节点不同占比下各算法得到的RMSD，如图3 所示。图中为多次实验结果的平均值。

图3 不同占比下各算法的RMSDFig.3 RMSD of Each Algorithm Under Different Proportions

图3 距离均方根均值可以看出，随着η 增大，松弛SOCP 算法的RMSD 变化最为剧烈，一直在在减小，这里算法与凸松弛算法的变化不大，而文中算法的稳定性最好，这主要因为算法初始定位时，只需要三个RN 节点计算初始值即可，而后期则更多领先迭代优化，因而节点比的增大、RN 节点数量的增加，对初始定位和后续迭代优化影响不明显。

4.2 节点规模对算法性能影响

固定WSN 中参考节点比例为η=0.25，不断增大网络节点规模，分析各算法的定位性能，实验结果均值，如表1 所示。

表1 不同节点规模下算法的定位性能Tab.1 Localization Performance of the Algorithm

表1 实验结果可以看出，文中算法在不同节点规模，取得较好的RMSD，这与3.1 和3.2 两节实验结果相似，而松弛SOCP 算法与凸松弛算法随着节点规模增大，其参考节点数据增多，RMSD 减少，但当节点达到4000 以上时，由于节点规模太大，算法的RMSD 反而开始增大，且凸松弛算法计算量增大而出现定位时间过长或无法定位情况。整体结果表明，文中算法在大规模节点WSN 网络中，仍能取得较好的定位精度和定位时间。

5 结语

针对大规模WSN 节点定准精度和效率不高的问题，提出子基于误差加权和修正的分布式节点定位算法，算法首先根据参考节点邻域范围将WSN 无向图划分为多个子图，然后在子图内构建距离误差加权和目标函数，以迭代计算节点位置信息。仿真实验表明，与现有算法相比，文中算法在较少的参考节点需求下可以取得最优的定位精度和时间，且对不同节点规模的WSN 网络具有较好的适应性。