基于核矩阵等距映射的无线传感网络节点定位算法

杨海 李兵

摘要：针对无线传感网络（Wireless Sensor Network，WSN）中节点位置信息呈现非线性的问题，基于偏最小二乘法fPartial Least sqHares，PLs）稳健的多元线性回归特点，结合流形学习中的非线性降维方法，提出了一种基于PLs的核矩阵等距映射fIsometric Feature Mapping，IsoMAP）节点定位算法.通过节点间测地距离表征节点非相似性，利用样本点贡献率找寻和剔除邻域中的“短路”邊，经质心变换和核变换后映射至高维特征区间，采用PLs方法求得节点位置.仿真结果表明，相比IsoMAP和多维尺度（Multidimensional scale Method，MDs）算法，该算法具有良好的拓扑稳定性、泛化能力、稳健性和定位精度，降低了计算复杂度.

关键词：无线传感网络;节点定位;

核矩阵;等距映射

中图分类号：TN929.5;TP212.9 文献标志码：A

DOI：10.3969/j.issn.1000-5641.2019.01.013

0.引言

节点定位是无线传感网络（WSN）应用的关键技术之一.根据节点定位算法结构.节点定位分为非学习型和学习型，后者对信标节点（已知位置节点）密度要求低且定位精度高，目前应用较广.学习型中应用较多的多维尺度（MDS）算法是一种线性降维方法，通过节点间欧氏距离表征节点非相似性，将高维空间数据以图形形式在低维空间再现，实现维数约减，进而估计节点位置.但节点间信号受路径损耗、多径传播、环境温湿度及节点位置的随机性等因素影响，节点位置信息呈现非线性关系，高维空间中呈现扭曲，线性降维方法难以实现维数约减，尤其当高维数据集在欧式空间相应的子集非凸时，数据集的低维嵌入结构还会产生较大的变形.

ISOMAP算法是在MDS算法框架基础上，采用节点间测地距离替代欧式距离，通过双质心变换实现算法降维的非线性扩展.但数据集中存在噪声干扰，使得质心变换后距离矩阵无法满足半正定条件，算法泛化能力差.Heeyoul等学者提出了基于核矩阵的ISOMAP算法KISOMAP，通过构建核矩阵保证距离平方矩阵的半正定性，提高了算法泛化能力.但ISOMAP和KISOMAP算法均基于最小二乘法（Least Square，Ls）求解，对数据异常点敏感，求解难易度依赖于邻域大小选择，限制了算法稳健性和拓扑稳定性，且样本增加时，需重新计算全部样本测地距离，运算复杂度呈指数增加.

本文基于PLS的KISOMAP（PLS-KISOMAP）节点定位算法是在ISOMAP算法基础上，利用PLS辅助分析方法中的贡献率找寻和剔除邻域中的“短路”边（离群点），提高了算法运算效率和定位精度;通过构造核矩阵改进了算法泛化能力;在高维特征区间里，采用PLS求解节点相对位置，进一步提高了其稳健性和网络拓扑性;与经典MDS、ISOMAP和KISOMAP定位方法进行了比较，仿真结果验证了本文所提出的PLS-KISOMAP定位算法的有效性.

2基于PLS法的KISOMAP节点定位算法

PLS-KISOMAP节点定位算法是在ISOMAP算法基础上，利用PLS方法寻找和剔除邻域图中的“短路”边，再根据核技术思想构建Mercer核矩阵，最后利用PLS方法求解节点相对位置.

2.1“短路”边的确定

邻域大小直接决定ISOMAP算法的拓扑稳定性、鲁棒性及运算效率，邻域过大将破坏数据集流形结构，产生“短路”边，使得邻域不能正确地表达数据集结构，邻域过小则影响流形结构的连续性.传统ISOMAP算法邻域的确定通过预先设置邻域参数，依靠映射“质量”f残差矩阵）大小判定参数选取的好坏，运算效率低.通过寻找和剔除邻域图中的“短路”边，使得算法对邻域大小不再敏感，则可以避开邻域大小难以有效选取的问题，提高运算效率.空间离群点检测算法有基于聚类、距离、密度和统计等类型，当空间数据存在严重自相关性和异质性等约束条件时，基于统计的算法具有较好的效果.

PLS方法是一种适合于回归和分类研究的第二代建模方法，广泛运用于机器学习和化学分析等领域，利用输入和输出向量之间的协方差信息提取数据潜在特征，可同时实现多元线性回归、主成份分析和典型相关分析，对样本数量要求少，运行速度快，易于区分有效信息和噪声，适合于自变量存在严重多重相关性的场合.样本点贡献图利用样本点中各变量对解释变量空间中潜变量的贡献分析其对总趋势的影响，可以检测出对模型影响较大的离群点，是PLS方法特有的离群点检测技术，具有较强的检测能力.

2.2核矩阵的构建

ISOMAP算法是通过非线性映射将给定空间内的线性不可分问题在相应高维特征空间内转换为线性可分问题，但存在非线性映射形式选择及特征空间维数等问题，维数较高时会产生运算“维数灾难”.根据希尔伯特空间理论（希尔伯特空间下正定核函数存在和判定的充分必要条件），K需满足Mercer条件，为半正定矩阵，由于噪声影响及测地距离近似性，K无法保证其正定性，算法泛化能力差.

核技术就是利用核函数替代非线性映射中的内积运算，避免映射形式选择和“维数灾难”问题.ISOMAP算法被视为核主成分分析（Principal Component Analysis，PCA）方法，采用增加常量的方法将K变换为Mercer核矩阵，可以同时保证测地距离的不变性及的半正定性，利用核矩阵的对角化获得高维数据的低维嵌入，提高算法的泛化能力.

图1为节点规则部署且位于同一平面网络拓扑结构时，经典MDS、ISOMAP、KISOMAP和PLS-KISOMAP算法的定位误差曲线.从图1看出，随着采样次数增加，从网络结构中获取的有关距离信息越多，经典MDS算法中重构的相似性矩阵误差越小，ISOMAP算法及其改进算法中最短路径距离替代欧式距离的精度越高，4种算法的定位误差均呈现下降趋势.ISOMAP与MDS算法基本框架一致，当节点为规则平面网络结构时，节点间测地距离近似于欧氏距离，ISOMAP退化成MDS算法.因此4种算法定位误差相差不大，彼此差异主要来源于Ls和PLs方法求解sDP问题的解偏差.

4结论

本文提出了一种PLS-KISOMAP节点定位算法，有效利用了ISOMAP保持数据集全局结构的特性;通过PLS方法中的样本点贡献率寻找并剔除邻域中的“短路”边，避免了ISOMAP算法中邻域大小选择困难问题;利用PLS方法对样本分布不敏感和核矩阵的半正定性特点，运用PLS求解节点位置坐标，降低了噪声分布形式变化对算法影响，提高了算法泛化能力和求解精度;基于分块核思想求解新增样本点，进一步提高了算法运行速度.PLS-KISOMAP节点定位算法是在MDS算法框架基础上发展而成的一种非线性降维学习方法，适合于全部MDS节点定位算法应用场合，同时适应于凸区域和非凸区域.本文研究中假定节点通信半径为定值，而实际网络中，由于环境影响及传感器自身性能差异，网络中节点通信半径存在差异，影响着算法定位效果.下一步工作将研究节点通信半径改变及节点位置移动时的定位问题.