基于核矩陣等距映射的無線傳感網(wǎng)絡(luò)節(jié)點定位算法

楊海 李兵

摘要：針對無線傳感網(wǎng)絡(luò)（Wireless Sensor Network，WSN）中節(jié)點位置信息呈現(xiàn)非線性的問題，基于偏最小二乘法fPartial Least sqHares，PLs）穩(wěn)健的多元線性回歸特點，結(jié)合流形學(xué)習(xí)中的非線性降維方法，提出了一種基于PLs的核矩陣等距映射fIsometric Feature Mapping，IsoMAP）節(jié)點定位算法.通過節(jié)點間測地距離表征節(jié)點非相似性，利用樣本點貢獻(xiàn)率找尋和剔除鄰域中的“短路”邊，經(jīng)質(zhì)心變換和核變換后映射至高維特征區(qū)間，采用PLs方法求得節(jié)點位置.仿真結(jié)果表明，相比IsoMAP和多維尺度（Multidimensional scale Method，MDs）算法，該算法具有良好的拓?fù)浞€(wěn)定性、泛化能力、穩(wěn)健性和定位精度，降低了計算復(fù)雜度.

關(guān)鍵詞：無線傳感網(wǎng)絡(luò);節(jié)點定位;

核矩陣;等距映射

中圖分類號：TN929.5;TP212.9 文獻(xiàn)標(biāo)志碼：A

DOI：10.3969/j.issn.1000-5641.2019.01.013

0.引言

節(jié)點定位是無線傳感網(wǎng)絡(luò)（WSN）應(yīng)用的關(guān)鍵技術(shù)之一.根據(jù)節(jié)點定位算法結(jié)構(gòu).節(jié)點定位分為非學(xué)習(xí)型和學(xué)習(xí)型，后者對信標(biāo)節(jié)點（已知位置節(jié)點）密度要求低且定位精度高，目前應(yīng)用較廣.學(xué)習(xí)型中應(yīng)用較多的多維尺度（MDS）算法是一種線性降維方法，通過節(jié)點間歐氏距離表征節(jié)點非相似性，將高維空間數(shù)據(jù)以圖形形式在低維空間再現(xiàn)，實現(xiàn)維數(shù)約減，進(jìn)而估計節(jié)點位置.但節(jié)點間信號受路徑損耗、多徑傳播、環(huán)境溫濕度及節(jié)點位置的隨機(jī)性等因素影響，節(jié)點位置信息呈現(xiàn)非線性關(guān)系，高維空間中呈現(xiàn)扭曲，線性降維方法難以實現(xiàn)維數(shù)約減，尤其當(dāng)高維數(shù)據(jù)集在歐式空間相應(yīng)的子集非凸時，數(shù)據(jù)集的低維嵌入結(jié)構(gòu)還會產(chǎn)生較大的變形.

ISOMAP算法是在MDS算法框架基礎(chǔ)上，采用節(jié)點間測地距離替代歐式距離，通過雙質(zhì)心變換實現(xiàn)算法降維的非線性擴(kuò)展.但數(shù)據(jù)集中存在噪聲干擾，使得質(zhì)心變換后距離矩陣無法滿足半正定條件，算法泛化能力差.Heeyoul等學(xué)者提出了基于核矩陣的ISOMAP算法KISOMAP，通過構(gòu)建核矩陣保證距離平方矩陣的半正定性，提高了算法泛化能力.但I(xiàn)SOMAP和KISOMAP算法均基于最小二乘法（Least Square，Ls）求解，對數(shù)據(jù)異常點敏感，求解難易度依賴于鄰域大小選擇，限制了算法穩(wěn)健性和拓?fù)浞€(wěn)定性，且樣本增加時，需重新計算全部樣本測地距離，運算復(fù)雜度呈指數(shù)增加.

本文基于PLS的KISOMAP（PLS-KISOMAP）節(jié)點定位算法是在ISOMAP算法基礎(chǔ)上，利用PLS輔助分析方法中的貢獻(xiàn)率找尋和剔除鄰域中的“短路”邊（離群點），提高了算法運算效率和定位精度;通過構(gòu)造核矩陣改進(jìn)了算法泛化能力;在高維特征區(qū)間里，采用PLS求解節(jié)點相對位置，進(jìn)一步提高了其穩(wěn)健性和網(wǎng)絡(luò)拓?fù)湫?與經(jīng)典MDS、ISOMAP和KISOMAP定位方法進(jìn)行了比較，仿真結(jié)果驗證了本文所提出的PLS-KISOMAP定位算法的有效性.

2基于PLS法的KISOMAP節(jié)點定位算法

PLS-KISOMAP節(jié)點定位算法是在ISOMAP算法基礎(chǔ)上，利用PLS方法尋找和剔除鄰域圖中的“短路”邊，再根據(jù)核技術(shù)思想構(gòu)建Mercer核矩陣，最后利用PLS方法求解節(jié)點相對位置.

2.1“短路”邊的確定

鄰域大小直接決定ISOMAP算法的拓?fù)浞€(wěn)定性、魯棒性及運算效率，鄰域過大將破壞數(shù)據(jù)集流形結(jié)構(gòu)，產(chǎn)生“短路”邊，使得鄰域不能正確地表達(dá)數(shù)據(jù)集結(jié)構(gòu)，鄰域過小則影響流形結(jié)構(gòu)的連續(xù)性.傳統(tǒng)ISOMAP算法鄰域的確定通過預(yù)先設(shè)置鄰域參數(shù)，依靠映射“質(zhì)量”f殘差矩陣）大小判定參數(shù)選取的好壞，運算效率低.通過尋找和剔除鄰域圖中的“短路”邊，使得算法對鄰域大小不再敏感，則可以避開鄰域大小難以有效選取的問題，提高運算效率.空間離群點檢測算法有基于聚類、距離、密度和統(tǒng)計等類型，當(dāng)空間數(shù)據(jù)存在嚴(yán)重自相關(guān)性和異質(zhì)性等約束條件時，基于統(tǒng)計的算法具有較好的效果.

PLS方法是一種適合于回歸和分類研究的第二代建模方法，廣泛運用于機(jī)器學(xué)習(xí)和化學(xué)分析等領(lǐng)域，利用輸入和輸出向量之間的協(xié)方差信息提取數(shù)據(jù)潛在特征，可同時實現(xiàn)多元線性回歸、主成份分析和典型相關(guān)分析，對樣本數(shù)量要求少，運行速度快，易于區(qū)分有效信息和噪聲，適合于自變量存在嚴(yán)重多重相關(guān)性的場合.樣本點貢獻(xiàn)圖利用樣本點中各變量對解釋變量空間中潛變量的貢獻(xiàn)分析其對總趨勢的影響，可以檢測出對模型影響較大的離群點，是PLS方法特有的離群點檢測技術(shù)，具有較強(qiáng)的檢測能力.

2.2核矩陣的構(gòu)建

ISOMAP算法是通過非線性映射將給定空間內(nèi)的線性不可分問題在相應(yīng)高維特征空間內(nèi)轉(zhuǎn)換為線性可分問題，但存在非線性映射形式選擇及特征空間維數(shù)等問題，維數(shù)較高時會產(chǎn)生運算“維數(shù)災(zāi)難”.根據(jù)希爾伯特空間理論（希爾伯特空間下正定核函數(shù)存在和判定的充分必要條件），K需滿足Mercer條件，為半正定矩陣，由于噪聲影響及測地距離近似性，K無法保證其正定性，算法泛化能力差.

核技術(shù)就是利用核函數(shù)替代非線性映射中的內(nèi)積運算，避免映射形式選擇和“維數(shù)災(zāi)難”問題.ISOMAP算法被視為核主成分分析（Principal Component Analysis，PCA）方法，采用增加常量的方法將K變換為Mercer核矩陣，可以同時保證測地距離的不變性及的半正定性，利用核矩陣的對角化獲得高維數(shù)據(jù)的低維嵌入，提高算法的泛化能力.

圖1為節(jié)點規(guī)則部署且位于同一平面網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時，經(jīng)典MDS、ISOMAP、KISOMAP和PLS-KISOMAP算法的定位誤差曲線.從圖1看出，隨著采樣次數(shù)增加，從網(wǎng)絡(luò)結(jié)構(gòu)中獲取的有關(guān)距離信息越多，經(jīng)典MDS算法中重構(gòu)的相似性矩陣誤差越小，ISOMAP算法及其改進(jìn)算法中最短路徑距離替代歐式距離的精度越高，4種算法的定位誤差均呈現(xiàn)下降趨勢.ISOMAP與MDS算法基本框架一致，當(dāng)節(jié)點為規(guī)則平面網(wǎng)絡(luò)結(jié)構(gòu)時，節(jié)點間測地距離近似于歐氏距離，ISOMAP退化成MDS算法.因此4種算法定位誤差相差不大，彼此差異主要來源于Ls和PLs方法求解sDP問題的解偏差.

4結(jié)論

本文提出了一種PLS-KISOMAP節(jié)點定位算法，有效利用了ISOMAP保持?jǐn)?shù)據(jù)集全局結(jié)構(gòu)的特性;通過PLS方法中的樣本點貢獻(xiàn)率尋找并剔除鄰域中的“短路”邊，避免了ISOMAP算法中鄰域大小選擇困難問題;利用PLS方法對樣本分布不敏感和核矩陣的半正定性特點，運用PLS求解節(jié)點位置坐標(biāo)，降低了噪聲分布形式變化對算法影響，提高了算法泛化能力和求解精度;基于分塊核思想求解新增樣本點，進(jìn)一步提高了算法運行速度.PLS-KISOMAP節(jié)點定位算法是在MDS算法框架基礎(chǔ)上發(fā)展而成的一種非線性降維學(xué)習(xí)方法，適合于全部MDS節(jié)點定位算法應(yīng)用場合，同時適應(yīng)于凸區(qū)域和非凸區(qū)域.本文研究中假定節(jié)點通信半徑為定值，而實際網(wǎng)絡(luò)中，由于環(huán)境影響及傳感器自身性能差異，網(wǎng)絡(luò)中節(jié)點通信半徑存在差異，影響著算法定位效果.下一步工作將研究節(jié)點通信半徑改變及節(jié)點位置移動時的定位問題.