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

徐世武

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

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

徐世武

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

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

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

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

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

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

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

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

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

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

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

2.1 算法描述

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

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

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

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

表1 距離與接收信號強(qiáng)度關(guān)系

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

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

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

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

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

3 實驗分析

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)束語

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

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顧晶晶, 陳松燦, 莊毅. 基于無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的物聯(lián)網(wǎng)定位模型. 計算機(jī)學(xué)報, 2010, 33(9): 1548–1556.

4肖竹, 譚光華, 李仁發(fā), 等. 無線傳感器網(wǎng)絡(luò)中基于超寬帶的TOA/AOA聯(lián)合定位研究. 計算機(jī)研究與發(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. 無線網(wǎng)絡(luò)定位綜述. 計算機(jī)學(xué)報, 2016, 39(6): 1237–1256. [doi: 10.11897/SP.J.1016.2016.01237]

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

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

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

10崔法毅, 邵冠蘭. 基于RSSI多邊定位誤差的加權(quán)質(zhì)心定位算法. 紅外與激光工程, 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)網(wǎng)定位模型.計算機(jī)系統(tǒng)應(yīng)用,2017,26(7):269–272. http://www.c-s-a.org.cn/1003-3254/5866.html

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

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