徐世武

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

基于K-鄰居節(jié)點覆蓋的物聯(lián)網定位模型①

徐世武

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

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

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

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

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

1 傳統(tǒng)的定位模型

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

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

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

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

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

2.1 算法描述

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

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

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

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

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

2.2 K-鄰居節(jié)點誤差的自校正

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

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

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

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

3 實驗分析

3.1 實驗環(huán)境

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

3.2 實驗結果分析

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

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

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

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

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

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

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

4 結束語

物聯(lián)網技術在很多應用場合中, 不知道節(jié)點的位置信息是沒有意義的, 因此對定位系統(tǒng)的研究非常重要. 本文在傳統(tǒng)質心定位法的基礎上, 提出一種基于鄰居信標節(jié)點誤差自校正的K-NNC定位算法. K-NNC定位算法根據盲節(jié)點與信標節(jié)點的接收信號強度來決定權重的大小. K-NNC定位算法選舉的信標節(jié)點為最近鄰的K個信標節(jié)點, 因此可以有效避開不同環(huán)境對結果的影響. 在相同的實驗環(huán)境中, 通過對K個信標節(jié)點擬合出最優(yōu)的線性, 通過擬合出來的線性關系對計算坐標進行補償, 最大程度避免了環(huán)境因素的影響. 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顧晶晶, 陳松燦, 莊毅. 基于無線傳感器網絡拓撲結構的物聯(lián)網定位模型. 計算機學報, 2010, 33(9): 1548–1556.

4肖竹, 譚光華, 李仁發(fā), 等. 無線傳感器網絡中基于超寬帶的TOA/AOA聯(lián)合定位研究. 計算機研究與發(fā)展, 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-鄰居節(jié)點覆蓋的物聯(lián)網定位模型.計算機系統(tǒng)應用,2017,26(7):269–272. http://www.c-s-a.org.cn/1003-3254/5866.html

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

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