一種基于核方法的無線傳感器網絡定位算法

林海

摘 要：無線傳感器網絡（WSN）作為一種新興的分布式網絡技術，被認為是21世紀改變世界的十大革新技術之一。定位是無線傳感器網絡的重要支撐技術之一，實現傳感器節點自定位是提供監測目標位置信息的必要條件。而實現高效、可靠、準確的節點定位對目標跟蹤具有重要意義。不幸的是，環境噪聲使得節點的定位精度降低。基于此，該文提出一種基于核方法的無線傳感器網絡定位算法。實驗表明，在WSN中通過采用卡爾曼濾波的核方法定位算法，一定程度上減少了隨機噪聲對節點定位精度的影響，有效的降低了系統定位誤差，實現一定程度的抗干擾。

關鍵詞：卡爾曼濾波 傳感器網絡 定位 核方法

中圖分類號：TP301 文獻標識碼：A 文章編號：1674-098X（2014）09（b）-0051-04

無線傳感器網絡（Wireless Sensor Network，WSN）將邏輯上的信息世界與真實物理世界融合在一起，改變了人與自然的交互方式，是繼Internet之后將對人類生活方式產生重大影響的新興IT技術之一。WSN是集計算機、網絡、通信、傳感器、嵌入式系統、智能計算、微電子等多個領域于一體的交叉學科，可由大量的體積小、種類繁多、價格低廉的傳感器節點（采集、傳感、收發、處理于一體）以自組織的形式形成自治網絡，實現對真實物理世界動態智能協同感知。

隨著無線傳感器網絡的快速發展，傳感器節點的位置信息在WSN的諸多實際應用中將成為不可或缺的一部分，如在火災監控、環境監測、潮汐、生態學等研究領域，采用WSN對物理世界信息的收集和處理。如在火場戰斗員的跟蹤應用中，結合傳感器節點感知目標運動速度和傳感器節點自身位置，可火場戰斗員的運動軌跡并預測目標的運動方向。

全球定位系統（Global Positioning System，GPS）以全天候、高精度、自動化、高效益的特點，應用于眾多的戶外定位領域，但實際應用中，不是所有傳感器節點都能利用GPS來定位，原因如下：（1）GPS和傳感器節點相比，質量較重、功耗較大且價格昂貴，而傳感器節點則質量輕、低功耗且價格低廉；（2）GPS適合在開闊戶外使用，而戶內或有障礙物遮擋等環境卻不適用；（3）在特殊條件下（如GPS系統被摧毀）將無法使用GPS。

綜上所述，在特殊環境下WSN有其獨有的優勢，使得利用WSN進行定位成為一個熱門的研究方向。從提出傳感器網絡這個概念至今，如何設計高效、高精度的定位算法一直是傳感器網絡研究中的熱點問題之一。針對不同的硬件設施和應用環境，學術界提出了眾多的節點定位算法，其主要包括基于測距的定位算法，例如Cricket室內定位系統、RADAR系統、基于AOA的APS（Ad hoc Position System）算法、DPE（Directed Position Estimation）定位算法、凸優化定位算法等，和基于非測距的定位算法，例如質心算法（Centroid Algorithm）、DV-Hop（Distance Vector Hop）算法、基于SVM（Support Vector Machine）定位算法等。

真實物理環境是存在隨機干擾的，在傳統的基于RSSI的WSN定位算法中（例如SVM、DV-Hop等），并未考慮環境隨機噪聲對RSSI信號強度的影響（例如在定位過程中障礙物的隨機游動等），從而導致估算的位置信息在一定位置空間范圍內發生抖動。為了減少和平滑這種位置信息的抖動現象，該文提出了一種基于核方法的無線傳感器網絡定位算法，通過采用卡爾曼濾波的核方法定位算法，一定程度上減少了隨機噪聲對節點定位精度的影響，有效的降低了系統定位誤差，實現一定程度的抗干擾。

1 傳感器網絡建模

考慮由N個傳感器節點組成的無線傳感器網絡部署在二維ROIC中，，各節點ID分別為1，2，…，N。令集合…表示傳感器節點集合，節點的真實坐標為…表示節點坐標矩陣。不失一般性，令集合中的前個元素表示信標節點，其坐標在系統初始化階段已給出，并令…表示信標節點的坐標矩陣。節點定位的目標是計算未知節點坐標的估計值…，使得盡可能地逼近未知節點的真實坐標。

2 核方法定位

2.1 核函數的定義

令c為輸入空間，核函數k隱含地定義了非線性映射：

（1）

使低維輸入空間c中的數據投影到高維特征空間中。核函數定義為特征空間中的內積，即：

（） （2）

核函數的進一步解釋：

（1）由模式可分性定理可知，一個復雜的模式分類問題從低維空間映射到高維空間后，變得更容易線性可分，并且使用經過核函數轉化后的線性分類器可以對線性數據進行分類，且分類效果更優。

（2）滿足Mercer定理的核函數隱含地定義了從輸入空間到高維特征空間的映射。如果直接在高維特征空間內計算內積會面臨維數災難問題。然而，核函數的引入解決了該維數災難問題，并且不會增加計算的復雜度。

（3）核函數可以看成是線性空間中樣本間的相似性的度量，它既可以定義在樣本間的距離上，也可以定義在樣本間的相似度上。

定義1.1（正定核函數（Positive Kernel））：（連續情況）如果對稱函數，使得下式成立：

（3）

則稱函數為正定核函數；（離散情況）或者對于任意的樣本集和系數，對稱函數

滿足：

≥0 （4）

則稱對稱函數為正定核函數。

在數學上，正定核函數有嚴格的定義，其中最著名的是Mercer定理。

定理1.1（Mercer定理）：假設對稱函數使得積分算子

（5）

是正定的，則：

（6）

對稱函數稱作算子對應的正定核函數。endprint

2.2 核函數和定位問題的聯系[1]

在WSN中，節點間都是通過無線的方式進行通訊，無線信號容易受到環境的干擾，測量誤差較大，表現為測量數據的高非線性和不確定性。在以往的研究中發現，測量數據的非線性能夠通過核函數進行捕獲。

傳感器網絡節點間的信號強度與距離之間的關系為：

（7）

其中，P為節點發射電壓，k為比例因子，為節點間的真實距離，μ是信號衰減系數，通常。

基于距離的徑向基核函數具有以下的形式：

（8）

其中，是定義在上的函數。容易驗證，當方程（8）中的時，方程（7）和方程（8）等價。因此，傳感器網絡節點間的信號強度衰減模型和基于距離的徑向基核函數之間必然存在聯系，而且可以通過核函數來度量節點之間的關系。值得注意的是，當無線傳感器網絡工作在理想環境中時，信號強度矩陣是半正定的，因此，信號強度矩陣自身就可以被認為是核函數矩陣。

另外，Sheng等人證明了，在傳感器節點定位問題中，聲波強度衰減模型和高斯核函數相似。

節點信號強度空間和節點坐標空間如圖1所示。如果將網絡中的節點看成是獨立的器件，它們可以和通信半徑內存在視距關系的任意節點雙向通信，那么下面的觀測是成立的：

（1）如果兩個節點的無線信號覆蓋區域存在交集，那么它們可以直接通信。

（2）如果兩個節點接收到的來自網絡中的其余的節點的信號強度形成的信號強度向量之間的距離越小，那么它們之間的真實距離越近，即它們越相似。

（3）如果兩個節點之間的實際距離越遠，那么它們接收到的來自網絡中的其余的節點的信號強度形成的信號強度向量之間的距離就應該越大，即它們之間的不相似性越大。

因此，在節點定位過程中，可以通過相似性或者不相似性在節點的信號強度空間和節點分布的坐標空間之間搭起一座橋梁，進而通過考察節點間的相似性關系或者不相似性關系來估計未知節點的坐標。例如，當選擇相似性度量節點之間的關系時，先通過相似性度量函數和節點間信號強度建立一個映射，然后再通過考察節點間相似性關系和節點真實坐標之間的關系在相似性度量和節點的坐標空間之間建立一個映射。由于正定核函數可以看成是線性空間中樣本間相似性的度量，所以可以通過核函數建立起信號空間和坐標空間之間的關系，即通過正定核函數將信號強度空間中的節點信號強度向量投影到核函數對應的RKHS空間中。由于核函數的引入，使得由于測量誤差造成的信號強度空間中的非線性關系，投影到了中節點間的函數關系，考慮到核函數投影是非線性投影，因此，可能將原來信號強度空間中的非線性關系變成中函數間的線性關系。當選擇不相似性關系信號強度空間和坐標空間時，根據條件正定核函數的定義，可以選擇條件正定核函數來度量節點之間的不相似性。條件正定核函數同樣可能將原來信號強度空間中的非線性關系變成函數間的線性關系。

由上分析可知，當選擇核函數來解決傳感器網絡中的節點定位問題時，核函數的選擇至關重要，如何選擇合適的核函數來設計核函數相關的定位算法是定位機制設計者必須面對的問題。

2.3 核方法定位

在定位算法中，給定n個訓練數據樣本，其中表示輸入空間。表明數據點是否位于區域中，如果數據點位于C中，則，

否則。定位算法需尋求一個判別函數并最小化定位錯誤[2]。

核方法定位的核心是核函數，它描述了輸入空間中兩點和的相似度。一般情況下，核函數需是一個對稱正定核。Mecer定理表明存在特征空間，使得核函數為特征空間中兩個向量和的內積，即。核方法定位算法是在特征空間選擇一個線性函數，對于w滿足≤B并最小化訓練錯誤：

（9）

φ是相應的損失函數，因此f可直接用核函數表達為：

（10）

有許多核函數滿足正定性，例如高斯核函數：

多項式核函數：

3 卡爾曼濾波建模

下面簡述Kalman濾波模型，定義觀測方程：

（11）

系統方程

（12）

是t時刻狀態向量，是從t-1時刻到t時刻的已知狀態轉移矩陣，是t時刻觀測向量，是t時刻觀測數據，為t時刻觀測噪聲，是均值為零協方差矩陣為的時間序列，是t時刻過程轉移矩陣，描述了期望的位置變化，是t時刻輸入噪聲，是均值為零協方差矩陣為的時間序列。

Kalman濾波算法方程集為：

（13）

設在t-1時刻，對應于測試點（未知節點）相對于參考點（信標節點）的m維狀態向量為的各個分量為時間序列。并設t時刻的預測值等于t-1時刻的最優估計值，即。定位系統中無控制量，假設由噪聲驅動，所以狀態轉移矩陣和過程轉移矩陣在任意時刻t都為m階單位陣：

并假設在任意時刻t，過程（輸入）噪聲和觀測噪聲的各分量和分別服從均值為0、方差為和的正太分布，即。由于參考點系統獨立，則的各分量相互獨立、的各分量相互獨立，相應的協方差矩陣為：

則方程集（13）可簡化為：

（14）

過程噪聲的協方差矩陣系數可以通過在實際環境中測量得到，而觀測噪聲的協方差矩陣系數可以適當指定，一般情況下要求，這樣Kalman濾波算法在迭代過程中才能收斂。的初始值可以適當假設，但對角元素不能為0，例如，可設。

4 實驗環境

選擇空曠平坦區域作為仿真實驗場所，在12.8 m×12.8 m=163.84 m2的實驗區域范圍內布置一個（測試）移動節點、七個（參考）信標節點、一個匯聚節點，且保證節點之間無障礙物遮擋，同時保證WSN網絡中信號均勻無縫隙覆蓋，節點布置方式如圖2所示。為使測試節點收到的RSSI向量有良好的區分度，需將參考節點盡可能的放置在角落，且參考點必須保持在同一平面內。endprint

如圖2所示，將實驗區域進行均勻分割，被分割成的子區域作為一個類別，這里我們采用1.6 m的等距分割，將實驗區域分成64個子區域并將其編號為0～63，并在欲定位的子區域內采集測試點指紋（RSSI向量），采集次數為。

5 仿真結果及分析

如圖3所示為待定位區域采集樣本點結果的分布情況，灰色點表示未采用Kalman濾波算法的定位結果，黑色點表示采用Kalman濾波算法的定位結果，通過對比可以得出未采用Kalman濾波算法的定位結果呈現定位數值波動大、數據不穩定，極大影響了定位精度。相反在進行了Kalman濾波之后，數據波動小，較穩定，集中分布在均值附近，提高了定位的穩定性。

如圖4所示為待定位區域內增加了隨機干擾后進行的樣本點采集和定位結果的分布情況，黑色點表示采用Kalman濾波算法并采用高斯核函數的定位結果分布，灰色點表示未采用Kalman濾波并使用其他核函數的定位結果分布。通過對比可以得出采用Kalman濾波和高斯核函數之后，樣本點分布收斂，定位結果波動范圍小，穩定地分布在均值附近，提高了定位的精確性。

6 結語

綜上所述，通過采用Kalman濾波算法，能夠過濾掉定位系統本身和環境所帶來的隨機噪聲，使得對應于特征輸入空間的采集樣本向量各維度波動范圍非常小，提高了采集樣本數據的穩定程度。在核方法定位算法中，通過選取高斯核函數，一定程度提高了定位的精確程度。通過二者的結合，該定位算法一定程度上提高了WSN非測距定位的穩定性和精確性。

參考文獻

[1] 王成群.基于學習算法的無線傳感器網絡定位問題研究[D].浙江大學，2009.

[2] XuanLong Nguyent，Michael I.Jordant，Bruno Sinopolit.A Kernel-based learning approach to ad hoc sensor network localization，2004.

[3] Tarun Dubey， Om Prakash Sahu. Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks. Journal of Electronic Science and Technology，2013.

[4] Huanqing Cui，Chuanai Zhou，Xiaojing Meng，Rong Hua.Mobile Anchor Assisted Localization in Wireless Sensor Networks with Reg ular Polygon Path. Proceedings of 2013 IEEE 4th International Conference on Software Engineering and Service Science，2013.endprint

如圖2所示，將實驗區域進行均勻分割，被分割成的子區域作為一個類別，這里我們采用1.6 m的等距分割，將實驗區域分成64個子區域并將其編號為0～63，并在欲定位的子區域內采集測試點指紋（RSSI向量），采集次數為。

5 仿真結果及分析

如圖3所示為待定位區域采集樣本點結果的分布情況，灰色點表示未采用Kalman濾波算法的定位結果，黑色點表示采用Kalman濾波算法的定位結果，通過對比可以得出未采用Kalman濾波算法的定位結果呈現定位數值波動大、數據不穩定，極大影響了定位精度。相反在進行了Kalman濾波之后，數據波動小，較穩定，集中分布在均值附近，提高了定位的穩定性。

如圖4所示為待定位區域內增加了隨機干擾后進行的樣本點采集和定位結果的分布情況，黑色點表示采用Kalman濾波算法并采用高斯核函數的定位結果分布，灰色點表示未采用Kalman濾波并使用其他核函數的定位結果分布。通過對比可以得出采用Kalman濾波和高斯核函數之后，樣本點分布收斂，定位結果波動范圍小，穩定地分布在均值附近，提高了定位的精確性。

6 結語

綜上所述，通過采用Kalman濾波算法，能夠過濾掉定位系統本身和環境所帶來的隨機噪聲，使得對應于特征輸入空間的采集樣本向量各維度波動范圍非常小，提高了采集樣本數據的穩定程度。在核方法定位算法中，通過選取高斯核函數，一定程度提高了定位的精確程度。通過二者的結合，該定位算法一定程度上提高了WSN非測距定位的穩定性和精確性。

參考文獻

[1] 王成群.基于學習算法的無線傳感器網絡定位問題研究[D].浙江大學，2009.

[2] XuanLong Nguyent，Michael I.Jordant，Bruno Sinopolit.A Kernel-based learning approach to ad hoc sensor network localization，2004.

[3] Tarun Dubey， Om Prakash Sahu. Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks. Journal of Electronic Science and Technology，2013.

[4] Huanqing Cui，Chuanai Zhou，Xiaojing Meng，Rong Hua.Mobile Anchor Assisted Localization in Wireless Sensor Networks with Reg ular Polygon Path. Proceedings of 2013 IEEE 4th International Conference on Software Engineering and Service Science，2013.endprint

如圖2所示，將實驗區域進行均勻分割，被分割成的子區域作為一個類別，這里我們采用1.6 m的等距分割，將實驗區域分成64個子區域并將其編號為0～63，并在欲定位的子區域內采集測試點指紋（RSSI向量），采集次數為。

5 仿真結果及分析

如圖3所示為待定位區域采集樣本點結果的分布情況，灰色點表示未采用Kalman濾波算法的定位結果，黑色點表示采用Kalman濾波算法的定位結果，通過對比可以得出未采用Kalman濾波算法的定位結果呈現定位數值波動大、數據不穩定，極大影響了定位精度。相反在進行了Kalman濾波之后，數據波動小，較穩定，集中分布在均值附近，提高了定位的穩定性。

如圖4所示為待定位區域內增加了隨機干擾后進行的樣本點采集和定位結果的分布情況，黑色點表示采用Kalman濾波算法并采用高斯核函數的定位結果分布，灰色點表示未采用Kalman濾波并使用其他核函數的定位結果分布。通過對比可以得出采用Kalman濾波和高斯核函數之后，樣本點分布收斂，定位結果波動范圍小，穩定地分布在均值附近，提高了定位的精確性。

6 結語

綜上所述，通過采用Kalman濾波算法，能夠過濾掉定位系統本身和環境所帶來的隨機噪聲，使得對應于特征輸入空間的采集樣本向量各維度波動范圍非常小，提高了采集樣本數據的穩定程度。在核方法定位算法中，通過選取高斯核函數，一定程度提高了定位的精確程度。通過二者的結合，該定位算法一定程度上提高了WSN非測距定位的穩定性和精確性。

參考文獻

[1] 王成群.基于學習算法的無線傳感器網絡定位問題研究[D].浙江大學，2009.

[2] XuanLong Nguyent，Michael I.Jordant，Bruno Sinopolit.A Kernel-based learning approach to ad hoc sensor network localization，2004.

[3] Tarun Dubey， Om Prakash Sahu. Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks. Journal of Electronic Science and Technology，2013.

[4] Huanqing Cui，Chuanai Zhou，Xiaojing Meng，Rong Hua.Mobile Anchor Assisted Localization in Wireless Sensor Networks with Reg ular Polygon Path. Proceedings of 2013 IEEE 4th International Conference on Software Engineering and Service Science，2013.endprint