基于K-鄰居節點覆蓋的物聯網定位模型①

徐世武

(福建師范大學 協和學院信息技術系, 福州 350117)

基于K-鄰居節點覆蓋的物聯網定位模型①

徐世武

(福建師范大學 協和學院信息技術系, 福州 350117)

針對傳統基于接收信號強度的定位缺陷, 提出一種新型的基于K-鄰居節點覆蓋的物聯網定位模型. 該模型分為選取鄰居節點與定位兩個階段, 未知節點先通過調整發射功率等級來選擇最近的K個鄰居節點, 盡量減少遠距離節點對定位的影響. 定位階段, 未知節點通過與K個信標節點的接收信號強度來計算權重, 通過加權求和算出未知節點的坐標. 采用K-鄰居節點誤差的自校正方法對坐標進行補償. 該定位模型可有效的避免環境因素對定位的影響, 且定位算法簡單, 避免復雜的計算. 實驗表明, 該定位模型定位精度較高.

接收信號強度; 定位; 物聯網; 無線傳感器網絡; 誤差自校正

物聯網(IOT: The Internet of Things)技術是近幾年備受關注的新興研究領域, 物聯網可以實現人與人, 人與物, 物與物的互聯互通, 因此可以廣泛應用于智能醫療, 智能交通, 智能家居, 航空航天等領域[1,2]. 無線傳感器網絡(WSN)作為IOT的核心技術之一, 近幾年也得到不斷的發展, 且針對WSN定位技術的研究也是IOT諸多定位模型研究的主要技術之一[3].

常見的室內測距技術有接收信號強度(RSSI)、到達角度(AOA)以及到達時間(TOA)等[4-6]. AOA技術在規模較大的網絡中計算復雜度相對較高, TOA利用信號的傳播速度與時間計算距離, 精度較高, 前提要求高精度的時間同步, 且硬件成本較高. RSSI技術對節點時間同步要求低, 不需要增加硬件輔助設備, 算法實現簡單, 成本低, 因此主要的室內測距技術采用的是RSSI[6-11].傳統的基于RSSI的定位技術有極大似然定位法與質心定位法等, 極大似然定位法受到無線電傳播路徑損耗模型影響較大, 質心定位法權重相等的情況下, 誤差較大, 因此我們可以采用加權的質心定位法, 未知節點獲取不同信標節點的RSSI值, 根據RSSI值的大小來判斷對應信標節點的權重因子, 不但降低了無線電傳播模型的影響, 也較大提高了質心定位法的精度.

1 傳統的定位模型

傳統的定位模型分為基于測距與無需測距兩種,基于測距定位需要先計算未知節點與信標節點的距離,然后通過三邊定位法或極大似然法計算未知節點的坐標. 采用傳統的無線電傳播路徑損耗模型估算盲節點與信標節點的距離, 如式(1)所示[10]. 在信標節點已知的發射信號強度下, 盲節點根據接收到的信號強度, 通過兩者的信號強度差可以估算出兩者之間的距離. 式(1)中RSSI(d)表示距離為d處的接收信號強度,RSSI(d0)表示距離為d0處的接收信號強度, d0一般取1米[9,10]. λ表示路徑損耗模型, 與實際環境相關. ζσ一般滿足高斯隨機分布.

無線電傳播路徑損耗模型較復雜, 很難得到統一的損耗模型, 不同的環境模型差別較大, 且需要事先大量采集信息獲取模型參數, 能耗較大. 因此采用式(1)估算節點距離極易受到環境因素的影響, 通過極大似然估算的坐標容易產生誤差疊加的情況, 且算法相對較復雜.

無需測距的定位模型主要有質心定位法, 如式(2)所示[9], 當未知節點(xi, yi)獲得N個信標節點后, 取N個信標節點的質心為定位的坐標值, 采用式(2)計算坐標算法簡單, 容易實現, 誤差波動大.

本文采用無需測距的定位模型, 在傳統質心定位法的基礎上, 利用節點接收信號強度隨距離增大而減小這一趨勢, 通過未知節點與信標節點的接收信號強度來計算對應的權重, 提高質心定位法的定位精度.

2 基于K-鄰居節點覆蓋(K-NNC)的加權質心定位算法

2.1 算法描述

N個信標節點有規則的布置在待定位的區域內, 信標節點的坐標與對應的節點編號可以事先獲取. 當未知節點在信標節點構成的定位區域(如大型醫院, 大型地下停車場)內移動的時候, 因為無線傳感器節點的發射功率等級可以調整(本實驗采用八個功率等級), 首先節點以最小的發射功率廣播定位信息, 當收到K個1跳節點的反饋信息, K不滿足4個的時候, 盲節點加大發射功率, 直到K大于等于4個為止. 對盲節點接收到信標節點的信號強度排序, 選取前K個信號最強的節點做為盲節點的最近鄰居節點.

定義1. 鄰居節點, 表示未知節點在對應發射功率等級下, 1跳通信內的信標節點集合.

定義2. 接收信號強度Sij, 表示第i個未知節點接收到第j個鄰居信標節點的信號強度. 如式(3)所示.

如果采用傳統的質心定位算法來求解, 雖然不用估算距離, 但可能盲節點偏離質心較遠, 計算誤差會非常大. 因此我們應該采用加權求和方式求解, 如式(4)與式(5)所示. 表1為本文在真實的室內環境下測得的未知節點與不同距離信標節點的接收信號強度平均值. 從表1可以看出對于未知節點測得與信標節點的接收信號強度S越大, 間接反應了未知節點與對應的信標節點越近, 接收信號強度越大的節點通過式(5)可以獲得越大的權重. 采用式(5)的缺陷是當未知節點與信標節點較遠時, 未知節點接收到的信號強度dBm會出現負值,可以利用單位轉換, 將接收信號強度dBm轉換為功率mW計算權重wi. 采用式(4)的加權求和無需測距, 算法復雜度低, 功耗低.

表1 距離與接收信號強度關系

2.2 K-鄰居節點誤差的自校正

因在實際的環境中, 無線電傳播路徑損耗會受到多徑衰落、障礙物等影響, 因此不同區域的路徑損耗模型不一樣, 即使同樣的區域也可能受到環境變化, 如雨天等影響. Sij未必能夠準確的反映出信號的衰減程度, 因此應該對式(4)計算的坐標進行修正補償, 為了降低區域性對定位結果的影響, 可以將選舉出來的K(本文實驗采用4個)個鄰居信標節點當成未知節點進行定位. 因信標節點的位置以及之間的距離事先知道, 可以根據K鄰居節點的實際坐標與采用式(4)計算的坐標進行最優線性擬合, 通過擬合的方程對盲節點的定位結果進行補償.

定義3. 坐標(Xi, Yi), i=1, 2…, K, 表示選舉出來K個信標節點的實際坐標.

定義4. 坐標(Xi’, Yi’), i=1, 2…, K, 表示選舉出來K個信標節點當成盲節點, 并通過式(4)計算的坐標.

通過定義3與定義4, 我們可以對選舉出來的K個信標節點的X坐標與Y坐標分別進行線性擬合. 給出K對實驗數據, 將這些數據帶入式(6)然后做差, 如式(7)所示. 要使偏差R最小, 即所有數據偏差的平方和R2最小, 分別對aj與mj求導, 整理公式后得到式(8). 通過式(8)可以得到K個信標節點X坐標的補償系數aj與mj.我們可以采用同樣的方式對K個信標節點的Y坐標進行線性擬合. 得到K個信標節點Y坐標的補償系數bj與nj.則我們可以得到盲節點經過K鄰居信標節點自校正補償后的坐標(x, y)如式(11)所示, 式(11)中是盲節點通過式(4)加權求和的坐標.

3 實驗分析

3.1 實驗環境

硬件: 采用德州儀器(TI)的CC2530為主控芯片的節點. 操作系統: TinyOS(加州大學伯克利分校開發的專為嵌入式無線傳感網絡設計的開放源代碼操作系統). 語言: nesC語言. 編譯環境: cygwin.

3.2 實驗結果分析

定義5. 定位誤差E, 假設定位節點的實際坐標為(x0, y0), 計算坐標為(x, y), 則定位誤差E如式(12)所示.

表2 定位算法性能比較(K=4)

從表2可以看出, 在相同的實驗環境下, 當K等于4的時候, K-NNC算法定位誤差E明顯小于傳統加權質心定位算法, 傳統加權質心定位算法當盲節點偏移質心較遠時誤差將非常大. 而K-NNC算法雖然誤差也會隨盲節點偏移質心而變大, 但K-NNC算法考慮了權重,因此增大并不明顯. 在相同實驗環境中, K-NNC算法經過選舉出來的K個鄰居信標節點誤差自校正后, 可以有效的降低環境因素的影響, 相比于校正前, 誤差E明顯降低. 為了更加直觀的比對算法, 我們采用MATLAB軟件繪制了5個盲節點的誤差E, 如圖1所示. 從圖1可以看出采用自校正補償的K-NNC算法性能得到顯著提高.為了更加充分的比對幾種算法, 我們取不同的K值進行比對E, 通過節點編號3進行試驗測試, 從表三可以看出經過修正后的K-NNC算法

當K值為4的時候誤差E就很小. 從表3與圖2可以看出, 當K取4的時候誤差E明顯小于K取3的值, 而當K取更大值的時候, 傳統加權質心算法并不會因為K值變大精度而提高, K-NNC算法雖然修正前, 修正后的誤差E有所改善, 但并沒有比K取4的時候有明顯提高. 反而但K值取過大的時候增加通信代價與通信干擾. 因此當K的值取4的時候為較理想的值.

圖1 不同節點編號的誤差E分布圖(K=4)

圖2 不同K值的誤差E分布圖(節點編號3)

表3 不同K值的誤差E(節點編號3)

4 結束語

物聯網技術在很多應用場合中, 不知道節點的位置信息是沒有意義的, 因此對定位系統的研究非常重要. 本文在傳統質心定位法的基礎上, 提出一種基于鄰居信標節點誤差自校正的K-NNC定位算法. K-NNC定位算法根據盲節點與信標節點的接收信號強度來決定權重的大小. K-NNC定位算法選舉的信標節點為最近鄰的K個信標節點, 因此可以有效避開不同環境對結果的影響. 在相同的實驗環境中, 通過對K個信標節點擬合出最優的線性, 通過擬合出來的線性關系對計算坐標進行補償, 最大程度避免了環境因素的影響. K-NNC定位算法的定位復雜度低, 定位精度高.

1Atzori L, Iera A, Morabito G. From “smart objects” to“social objects”: The next evolutionary step of the Internet of Things. IEEE Communications Magazine, 2014, 52(1):97–105. [doi: 10.1109/MCOM.2014.6710070]

2Xu LD, He W, Li SC. Internet of things in industries: A survey. IEEE Trans. Industrial Informatics, 2014, 10(4):2233–2243. [doi: 10.1109/TII.2014.2300753]

3顧晶晶, 陳松燦, 莊毅. 基于無線傳感器網絡拓撲結構的物聯網定位模型. 計算機學報, 2010, 33(9): 1548–1556.

4肖竹, 譚光華, 李仁發, 等. 無線傳感器網絡中基于超寬帶的TOA/AOA聯合定位研究. 計算機研究與發展, 2013, 50(3):453–460. [doi: 10.7544/issn1000-1239.2013.20110029]

5Li B, Wang WJ, Yin QY. A distributed localization in wireless sensor networks utilizing AOD estimation and synthetical uniform circular array. Science China Information Sciences, 2015, 58(6): 062307.

6錢志鴻, 孫大洋, Leung V. 無線網絡定位綜述. 計算機學報, 2016, 39(6): 1237–1256. [doi: 10.11897/SP.J.1016.2016.01237]

7周艷, 李海成. 基于RSSI無線傳感器網絡空間定位算法. 通信學報, 2009, 30(6): 75–79.

8羅炬鋒, 邱云周, 付耀先, 等. 研究片內多徑分離技術在基于RSSI定位中的應用 .電子與信息學報 ,2011 ,33(4) :891–895.

9韓東升, 楊維, 劉洋, 等. 煤礦井下基于RSSI的加權質心定位算法. 煤炭學報, 2013, 38(3): 522–528.

10崔法毅, 邵冠蘭. 基于RSSI多邊定位誤差的加權質心定位算法. 紅外與激光工程, 2015, 44(7): 2162–2168.

11Moragrega A, Closas P, Ibars C. Potential game for energyefficient RSS-based positioning in wireless sensor networks.IEEE Journal on Selected Areas in Communications, 2015,33(7): 1394–1406. [doi: 10.1109/JSAC.2015.2430172]

Location Model Based on K-Neighbor Node Coverage for IOT

XU Shi-Wu
(Concord College Department of Information Technology, Fujian Normal University, Fuzhou 350117, China)

In view of the traditional positioning defects based on

signal strength, a new K-NNC location algorithm is proposed for IOT, based on K- neighbor node coverage (K-NNC). K-NNC is divided into two stages, select neighbor nodes and positioning stage. In order to reduce the influence of long distance nodes on the positioning, by adjusting the transmit power to select the nearest K neighbor node. In positioning stage, the node calculates the weight by the received signal strength of the K beacon node. The coordinates of the nodes are calculated by the weighted sum. Using the self-correcting method the position coordinates are compensated. The K-NNC positioning model can effectively avoid the influence of environmental factors on the positioning, and the positioning algorithm is simple. Experiment shows the K-NNC positioning model positioning is highly accurate.

received signal strength; location; IOT; WSN; error self-correction

徐世武.基于K-鄰居節點覆蓋的物聯網定位模型.計算機系統應用,2017,26(7):269–272. http://www.c-s-a.org.cn/1003-3254/5866.html

福建省教育廳科技項目(JA13368, JAT160667, JB13263); 福建師范大學協和學院教學改革研究項目(JG20140207)

2016-11-04; 收到修改稿時間: 2017-01-04