基于核矩陣等距映射的無線傳感網絡節點定位算法

楊海 李兵

摘要：針對無線傳感網絡（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節點定位算法應用場合，同時適應于凸區域和非凸區域.本文研究中假定節點通信半徑為定值，而實際網絡中，由于環境影響及傳感器自身性能差異，網絡中節點通信半徑存在差異，影響著算法定位效果.下一步工作將研究節點通信半徑改變及節點位置移動時的定位問題.