一種基于核方法的無線傳感器網(wǎng)絡定位算法

林海

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

關鍵詞：卡爾曼濾波 傳感器網(wǎng)絡 定位 核方法

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

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

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

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

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

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

1 傳感器網(wǎng)絡建模

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

2 核方法定位

2.1 核函數(shù)的定義

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

（1）

使低維輸入空間c中的數(shù)據(jù)投影到高維特征空間中。核函數(shù)定義為特征空間中的內(nèi)積，即：

（） （2）

核函數(shù)的進一步解釋：

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

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

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

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

（3）

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

滿足：

≥0 （4）

則稱對稱函數(shù)為正定核函數(shù)。

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

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

（5）

是正定的，則：

（6）

對稱函數(shù)稱作算子對應的正定核函數(shù)。endprint

2.2 核函數(shù)和定位問題的聯(lián)系[1]

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

傳感器網(wǎng)絡節(jié)點間的信號強度與距離之間的關系為：

（7）

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

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

（8）

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

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

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

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

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

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

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

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

2.3 核方法定位

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

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

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

（9）

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

（10）

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

多項式核函數(shù)：

3 卡爾曼濾波建模

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

（11）

系統(tǒng)方程

（12）

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

Kalman濾波算法方程集為：

（13）

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

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

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

（14）

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

4 實驗環(huán)境

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

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

5 仿真結(jié)果及分析

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

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

6 結(jié)語

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

參考文獻

[1] 王成群.基于學習算法的無線傳感器網(wǎng)絡定位問題研究[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所示，將實驗區(qū)域進行均勻分割，被分割成的子區(qū)域作為一個類別，這里我們采用1.6 m的等距分割，將實驗區(qū)域分成64個子區(qū)域并將其編號為0～63，并在欲定位的子區(qū)域內(nèi)采集測試點指紋（RSSI向量），采集次數(shù)為。

5 仿真結(jié)果及分析

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

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

6 結(jié)語

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

參考文獻

[1] 王成群.基于學習算法的無線傳感器網(wǎng)絡定位問題研究[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所示，將實驗區(qū)域進行均勻分割，被分割成的子區(qū)域作為一個類別，這里我們采用1.6 m的等距分割，將實驗區(qū)域分成64個子區(qū)域并將其編號為0～63，并在欲定位的子區(qū)域內(nèi)采集測試點指紋（RSSI向量），采集次數(shù)為。

5 仿真結(jié)果及分析

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

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

6 結(jié)語

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

參考文獻

[1] 王成群.基于學習算法的無線傳感器網(wǎng)絡定位問題研究[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