徐世武

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

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

徐世武

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

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

接收信號(hào)強(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)可以實(shí)現(xiàn)人與人, 人與物, 物與物的互聯(lián)互通, 因此可以廣泛應(yīng)用于智能醫(yī)療, 智能交通, 智能家居, 航空航天等領(lǐng)域[1,2]. 無線傳感器網(wǎng)絡(luò)(WSN)作為IOT的核心技術(shù)之一, 近幾年也得到不斷的發(fā)展, 且針對(duì)WSN定位技術(shù)的研究也是IOT諸多定位模型研究的主要技術(shù)之一[3].

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

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

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

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

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

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

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

2.1 算法描述

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

圖1 不同節(jié)點(diǎn)編號(hào)的誤差E分布圖(K=4)

圖2 不同K值的誤差E分布圖(節(jié)點(diǎn)編號(hào)3)

表3 不同K值的誤差E(節(jié)點(diǎn)編號(hào)3)

4 結(jié)束語

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

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

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

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

9韓東升, 楊維, 劉洋, 等. 煤礦井下基于RSSI的加權(quán)質(zhì)心定位算法. 煤炭學(xué)報(bào), 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é)點(diǎn)覆蓋的物聯(lián)網(wǎng)定位模型.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(7):269–272. http://www.c-s-a.org.cn/1003-3254/5866.html

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

2016-11-04; 收到修改稿時(shí)間: 2017-01-04