馬 禮,賀建沛,馬東超
(北方工業(yè)大學(xué) 信息工程學(xué)院,北京100144)
本節(jié)對傳播模型進行分析并修正出一個適合本算法的傳播模型,另外,對定位系統(tǒng)中要用到的一些概念、理論、公式等進行推導(dǎo)說明。
在WSN 的傳感器節(jié)點定位過程中造成定位誤差的因素很多,其中,無線電信號傳播模型就是一個,好的模型可以提高定位的精度,因此模型的選擇很重要?,F(xiàn)有的模型通常都是實驗測量修正理想物理模型得到,常用的有Shadowing模型、Free-space模型、Two-ray-ground模型。本文將選擇Shadowing模型;
Shadowing模型
無線電信號傳播具有不規(guī)則性,主要是由各向異性的路徑衰減、不均勻的發(fā)送功率、器件特性等因素導(dǎo)致的,無線電信號不規(guī)則(radio irregularity model,RIM)模型公式如下:
RIM 模型
考慮到信號強度在不同方向存在不可忽略的不規(guī)則性,所以本文使用RIM 模型去修正Shadowing模型[13],即通過Ki修正了各向同性假設(shè)下的不同方向上的通信半徑。
修正之后的公式
式中:Pr(d)是為在距離d處的信號強度;Pr(d0)是在參考距離d0處的信號強度;α是路徑損耗系數(shù);Xdb是一個平均值為0的高斯隨機分布,Ki表示不同方向上路徑損失的不同系數(shù),DOI表示在信號傳方向上單位度變化的最大路徑損失比。虛擬節(jié)點和信標節(jié)點坐標已知,所以可通過距離公式
得出d,帶入式 (3)可計算出虛擬節(jié)點接收到的信標節(jié)點發(fā)出的RSSI值。
若能合理的利用網(wǎng)格陣列,定位精度將得到明顯的提高[14,15]。實際情況是傳感器節(jié)點的通信距離有限,并且都要通過路由把采集到的數(shù)據(jù)上傳到SINK 節(jié)點(匯聚節(jié)點)。同時為了減少如文獻[10]進行劃分時引進的計算量,所以,本文將以SINK節(jié)點為原點建立坐標系,并對整個坐標系進行mesh均分,網(wǎng)格邊長是L,所有的交點都是虛擬節(jié)點,假設(shè)共有M個虛擬節(jié)點,其坐標為(n*L,m*L),其中,n、m∈Z。
貼近度描述了兩個集合的貼近程度,為此本文將未知節(jié)點收到的來自信標節(jié)點的RSSI和虛擬信標節(jié)點相對信標節(jié)點應(yīng)該收到的RSSI分別作為兩個模糊集合A、B (相對信標節(jié)點的順序必須一致),然后,使用貼近度來度量其相近程度??紤]到無線傳感器網(wǎng)絡(luò)的特點,本文使用計算復(fù)雜度較低的最大最小貼近度。
定義1 假設(shè)模糊集合A 包含的元素為Xi,B 包含元素為Yi,i∈Z,則集合A、B對應(yīng)元素的貼近度為
假設(shè)一個未知節(jié)點s,通信范圍內(nèi)有n個信標節(jié)點,m個虛擬信標節(jié)點,則未知節(jié)點s將接收到相對于n個信標節(jié)點對應(yīng)的信號強度組合RS= (RS1,RS2,…,RSn)。同理,對于任一個虛擬節(jié)點g,則有Rg= (Rg1,Rg2,…,Rgn),那么m 個虛擬信標節(jié)點會有矩陣
即求RS與矩陣每行的貼近度。有式 (5)、式 (6)得
求出這m 個虛擬節(jié)點和未知節(jié)點s之間的貼近度。選取貼近度最高的虛擬節(jié)點作為次信標節(jié)點。
如圖1所示,其中,黑色圓點為信標節(jié)點、三角形為虛擬節(jié)點、紅色五角星為未知節(jié)點s。首先計算虛擬節(jié)點 (假設(shè)是g1)相對信標節(jié)點n1、n2、n3的RSSI,然后依次與未知節(jié)點s接收到的n1、n2、n3的RSSI代入式 (7),計算出Degree(Rs,Rg1同理計算出g2、g3、g4、g5、g6、g7、g8、g9與s的貼近度,選取貼近度較大的虛擬節(jié)點 (假設(shè)門限值為4),則最終選出的次信標節(jié)點是g2、g3、g5、g6。
圖1 貼近度
當未知節(jié)點通信范圍內(nèi)有3個或者以上的信標節(jié)點時,以接收到信號的先后順序記錄下這些信標節(jié)點,并按照記錄的順序去為這些信標節(jié)點分組 (3個一組),假設(shè)陸續(xù)接收到 了 A、B、C、D 四 點,分 組 順 序 應(yīng) 是 (ABC)、(ABD)、(BCD)。此處假設(shè)最先接受到A、B、C 這3個信標節(jié)點的信號,未知節(jié)點接收到的信號強度分別為RSSI1、RSSI2和RSSI3 (多次的平均值)。
3個信標節(jié)點組成△ABC,未知節(jié)點相對△ABC 的位置有兩種情況:在三角形內(nèi)部;在三角形外部。
基于三角形內(nèi)測點法進行判斷未知節(jié)點是否在三角形內(nèi)部:假設(shè)s是未知節(jié)點,s1是線段AB 的中點,s2是線段AC的中點,s3是線段BC 的中點,A、B、C 坐標已知,則s1、s2、s3的坐標可通過簡單中點公式計算出來,進而代入式 (4)和式 (3)計算出到A、B、C 的RSSI值,然后分別與s到A、B、C的RSSI比較,根據(jù)內(nèi)測點理論知:如果出現(xiàn)s1、s2、s3中的任意一點的RSSI都比s的RSSI值大或者小,則認為s點在△ABC外部,否則在內(nèi)部。
當判斷在△ABC外,再去尋找第二組三角形組合,直至在三角形內(nèi)部。
對于落在三角形內(nèi)部的情況,如圖2所示,比較RSSI的大小,假如RSSI1≤RSSI2,RSSI1≤RSSI3,RSSI2≤RSSI3,則未知節(jié)點在圖2中的陰影區(qū)域內(nèi),其中E 點是三邊的中垂線的交點,即三角形外心。(證明如下)
證明:使用反證法論證:
根據(jù)信號強度衰減模型知,無線傳感器節(jié)點信號的強度與傳輸距離有關(guān) (由路徑損耗、多徑傳播等因素造成的),因此傳感器節(jié)點距離比較小時,RSSI值就越大;反之,RSSI就越?。?6]。
假若此未知節(jié)點在I區(qū),有上述理論可得到:RSSI1≤RSSI2,RSSI1≤RSSI3,但是RSSI2 (RSSI3,這與已知條件RSSI2 (RSSI3矛盾,因此未知節(jié)點不在I區(qū)。同理,可證明未知節(jié)點也不再II、III、IV、V 區(qū)。所以未知節(jié)點在圖2中的陰影區(qū)域。(注:文中的RSSI值都是多次的平均值)
圖2 節(jié)點初步區(qū)域
終端節(jié)點主芯片使用的是TI的CC2530,具有FFD 功能,匯聚節(jié)點主芯片是CC2531,其運行的程序是基于Zstack開發(fā)的;網(wǎng)關(guān)節(jié)點核心板用的用的是友善的S5PV210,系統(tǒng)是Linux,支持Zigbee協(xié)議到3G/WIFI/以太網(wǎng)的協(xié)議轉(zhuǎn)換,可以實時顯示上傳的數(shù)據(jù),可以進行下行控制。
定位系統(tǒng)的基本思想:當定位一個未知節(jié)點時,其需要向周圍的信標節(jié)點發(fā)送請求信息,未知節(jié)點收到數(shù)據(jù)包后,相應(yīng)地記錄下所接收到的這些信標節(jié)點的信號強度,然后 (根據(jù)1.4節(jié)的初步區(qū)域知識)可計算出未知節(jié)點所在的區(qū)域,又因為虛擬節(jié)點的坐標是已知的,所以,再根據(jù)電磁波衰減模型公式可以計算出每個虛擬節(jié)點相對信標節(jié)點的信號強度,結(jié)合貼近度公式,找到與未知節(jié)點貼近度較高的虛擬節(jié)點,即次信標節(jié)點;最后求這些虛擬節(jié)點的質(zhì)心就是未知節(jié)點的坐標,然后節(jié)點加入網(wǎng)絡(luò),并將位置信息隨采集信息上傳到匯聚節(jié)點。
2.2.1 定位算法步驟
(1)按照1.2節(jié)中所描述的將定位區(qū)域進行網(wǎng)格劃分,并建立坐標系;
(2)按照1.4節(jié)中方法去獲得未知節(jié)點的初步區(qū)域;(3)把未知節(jié)點所在初步區(qū)域內(nèi)的虛擬節(jié)點代入式(3)、式 (4),求出相對信標節(jié)點的RSSI值;
(4)把未知節(jié)點收到的RSSI(多次的平均值)和虛擬節(jié)點的RSSI代入到式 (7),找出與未知節(jié)點s貼近度最高的J(J∈Z)個次信標節(jié)點;
(5)把J個次信標節(jié)點的坐標代入質(zhì)心式 (8)計算出未知節(jié)點坐標
算法流程如圖3所示。
圖3 算法流程
2.2.2 算法分析
算法復(fù)雜度分析
根據(jù)文中第二部分的理論基礎(chǔ)和第三部分的算法步驟可知,未知節(jié)點坐標求解將變成一個空間約束問題和質(zhì)心求解問題,通過求與其貼近度最大的虛擬節(jié)點所組成區(qū)域的質(zhì)心即可,整個計算過程中沒有出現(xiàn)高次方程求解,因此ADLA計算復(fù)雜度是O(n),n是參與計算的次信標節(jié)點個數(shù);
通信開銷分析
通信開銷主要和節(jié)點發(fā)包的數(shù)量和發(fā)包的大小、數(shù)量有關(guān),根據(jù)文中第二部分的理論基礎(chǔ)和第三部分的算法步驟可以看出通信開銷是由網(wǎng)格劃分引入,在次信標節(jié)點的選取過程中體現(xiàn)出來—節(jié)點的通信量增大,因為網(wǎng)格是由虛擬節(jié)點組成的,所以可以用陰影區(qū)域包含網(wǎng)格多少去評價算法的通信開銷,所以本文通過計算參與一個未知節(jié)點定位的網(wǎng)格的個數(shù)去反映算法的開銷。
假設(shè)節(jié)點通信半徑為R,未知節(jié)點到3個信標節(jié)點的距離都是R,即是三角形的外心時,虛擬節(jié)點個數(shù)最多。假設(shè)未知節(jié)點在三角形內(nèi)部的陰影區(qū)域,如圖4所示,CE與坐標Y軸平行,DE與X軸平行,網(wǎng)格寬度是L;3個信標節(jié)點A、B、C的坐標分別是(Xa,Ya),(Xb,Yb),(Xc,Yc);則線段BC中點s3的坐標(Xs3,Ys3)=((Xc+Xb)/2,(Yc+Yb)/2);線段AC中點s2的坐標是(Xs2,Ys2)=((Xa+Xc)/2,(Ya+Yc)/2);如圖4所示,則線段DE的長度d1=|Xs3-Xc|,求得△CES3的面積S0= (R*d1)/2= (R*|Xb-Xc|)/4,因為R2<(Xb-Xc)2+ (Yb-Yc)2<4*R2,所以S0<R2/2,陰影區(qū)域面積S<R2,網(wǎng)格面積是L2,所以陰影區(qū)域包含的網(wǎng)格個數(shù)一定小于(R/L)2。
圖4 算法分析
定位節(jié)點首先要獲得位置信息,然后申請加入網(wǎng)絡(luò),進而發(fā)送采集的數(shù)據(jù),信標節(jié)點通過GPS獲得位置信息,未知節(jié)點通過定位算法獲??;所有節(jié)點都具有全項功能,而且網(wǎng)絡(luò)采用層次組網(wǎng)方式,流程如圖5所示。
為驗證ADLS 系統(tǒng)的性能,利用MATLAB7.13 平臺進行仿真。采用隨機部署模型,將所有無線傳感器節(jié)點隨機的分布在一個在300m×300m 的正方形區(qū)域內(nèi),其中,
DOI=0.1,J=10,β=5。
圖5 定位系統(tǒng)流程
在上述的信號傳輸模型的條件下,將ADLS 系統(tǒng)與Centroid[5]、RN-BP[11]進 行 對 比。在 室 外 的 實 際 情 況 中,節(jié)點的通信半徑會在50—100m 之間,本文在對網(wǎng)格寬度和信標節(jié)點比率對平均定位誤差仿真時的通信半徑R都設(shè)置為70m。所有未知節(jié)點平均定位誤差采用式 (9),其中,節(jié)點的實際坐標為Xi,估計坐標為X*i,相對誤差為Aerror
(1)Centroid算法:未知節(jié)點接收到3 個或更多信標節(jié)點的數(shù)據(jù)包后,這些信標節(jié)點會構(gòu)成一個多邊形,求其質(zhì)心,即為未知節(jié)點坐標,該算法簡單,但對網(wǎng)絡(luò)要求比較苛刻,特別是信標節(jié)點的比例。
(2)RN-BP算法:該算法利用神經(jīng)網(wǎng)絡(luò)的特性,先計算出未知節(jié)點的位置,再利用網(wǎng)絡(luò)中訓(xùn)練的誤差較小的虛擬節(jié)點,如果存在和虛擬節(jié)點到信標節(jié)點有相同最小跳數(shù)的未知節(jié)點,把此未知節(jié)點升級為信標節(jié)點,重新訓(xùn)練網(wǎng)絡(luò)直至所有節(jié)點都定位完成。
3.2.1 網(wǎng)格寬度對平均定位誤差影響
算法中采用了網(wǎng)格陣列的坐標系,故本節(jié)通過改變網(wǎng)格邊長來觀察其對平均定位誤差的影響。信標節(jié)點密度為15%,多次運行ADLS算法,仿真結(jié)果如圖6 所示,網(wǎng)格邊長是4m 到7m 時對平均定位誤差的影響變化不大,但是再繼續(xù)加大網(wǎng)格邊長時,定位出現(xiàn)嚴重偏差,主要是因為參與未知節(jié)點定位的虛擬節(jié)點變稀疏。
圖6 網(wǎng)格邊長對平均定位誤差的影響
3.2.2 信標節(jié)點比率對平均定位會差的影響
本節(jié)通過改變信標節(jié)點比率,觀察它對RN-BP、Centroid、ADLS平均定位誤差的影響,信標節(jié)點的變化范圍是6%—30%,網(wǎng)格寬度為6 m。對3 種算法進行多次仿真,仿真結(jié)果如圖7所示,隨著信標節(jié)點比率的增大,3種定位算法的平均定位誤差都在減小,由于Centroid算法對信標節(jié)點的依賴性比較大,所以其平均定位誤差減小的很快,但這使網(wǎng)絡(luò)成本大大增大。而另外兩種算法對信標節(jié)點的依賴性不是很大,尤其是筆者所提ADLS算法,當比率為5%—17%之間時明顯優(yōu)于RN—BP 算法,但在15%之后兩種算法基本接近,平均定位誤差減小都不明顯。
圖7 信標節(jié)點比率對平均定位誤差的影響
3.2.3 節(jié)點通信半徑對平均定位誤差的影響
本節(jié)通過改變節(jié)點通信半徑,觀察它對RN-BP、Centroid、ADLS平均定位誤差的影響,節(jié)點通信半徑變化范圍是50-100 m,網(wǎng)格寬度為6 m,信標節(jié)點比率為15%。對3種算法進行多次仿真,仿真結(jié)果如圖8所示,隨著通信半徑的增大,3種定位算法的平均定位誤差都在變小,但是R>70m 后質(zhì)心法的誤差反而有所增大,這主要是由于通信半徑的加大會使更多信標節(jié)點參與到未知節(jié)點的定位中,求質(zhì)心時,所有信標節(jié)點占的權(quán)重一樣的,但信標節(jié)點并不是均勻的分布在未知節(jié)點周圍的原因,而RN-BP算法增大的原因是通訊半徑的增大使得一跳的最大距離增大,使得在選取虛擬節(jié)點時出現(xiàn)誤差。ADLS算法在R>70m 后定位精度變化不大,因為算法中是通過比較RSSI來選取次信標節(jié)點的,當R 達到一定值后對定位精度影響不大。
圖8 通信半徑對平均定位誤差的影響
3.2.4 定位時間對比
本節(jié)通過改變節(jié)點的總數(shù),觀察并比較Centroid、ADLS、RN_BP的運行時間,節(jié)點總數(shù)為200、400、600,通信半徑R 為70 m,網(wǎng)格寬度為6 m,信標節(jié)點比率為15%。對3種算法進行多次仿真,仿真結(jié)果如圖9 所示,顯然Centroid算法用時最少,主要是因為該算法僅利用信標節(jié)點進行定位;隨著節(jié)點總數(shù)的增加,定位時間都增加,但是RN-BP增長的速度過快,主要是因為該算法要對節(jié)點進行訓(xùn)練,節(jié)點的數(shù)目越多,需要的時間就越多;另外不管節(jié)點總數(shù)是200、400、600時,Centroid算法用時最短,ADLS算法次之,RN-BP 最長,這也間接的反映了3 種算法的計算復(fù)雜度。
圖9 定位時間對比
圖10 三維拓撲圖
在學(xué)校操場150*150的區(qū)域放置了50個節(jié)點,其中信標節(jié)點6個,節(jié)點間的距離最近為3m,最遠為106m,網(wǎng)格寬度程序中設(shè)定為6m,為便于分析數(shù)據(jù),終端節(jié)點沒有采用自動分配網(wǎng)絡(luò)段地址的方式,而是采用了編號的形式將地址固定,其中0、9、19、29、39、49為信標節(jié)點,其余為未知節(jié)點。
終端節(jié)點通過Zigbee網(wǎng)絡(luò)將位置信息發(fā)送至sink 節(jié)點,再通過sink節(jié)點上的WIFI模塊/3G 模塊/以太網(wǎng),將數(shù)據(jù)上傳到遠端服務(wù)器,由服務(wù)器端的解析程序?qū)⒕W(wǎng)絡(luò)拓撲結(jié)構(gòu)和位置信息展現(xiàn)出來。除sink節(jié)點外,其它每個節(jié)點可掛載子節(jié)點數(shù)設(shè)定為2,節(jié)點隨機均勻分布,服務(wù)器端監(jiān)測到的網(wǎng)絡(luò)拓撲及位置信息如圖10所示。其中,圖中藍色節(jié)點為sink節(jié)點,粉色節(jié)點為傳感器網(wǎng)絡(luò)終端節(jié)點,中間的連接線表示了終端節(jié)點的數(shù)據(jù)傳輸路徑,構(gòu)成了多跳形式的三圍網(wǎng)絡(luò)拓撲結(jié)構(gòu)。圖中為了清晰的顯示經(jīng)緯度,僅顯示有限節(jié)點。圖10是ADLS的效果圖。
此處我們選擇其中10個未知節(jié)點來進行說明3種算法的定位誤差,其中表中的實際坐標是通過GPS測試得到,測量坐標是通過算法計算得到,誤差是通過經(jīng)緯度距離式(10)得出 (適用于北半球),其中,A 點的經(jīng)緯度:ψA、ΦA(chǔ)點的經(jīng)緯度:ψB、ΦB。見表1,白天室外通訊距離是150m 左右Centroid、RN_BP、ADLS的相對定位誤差分別是22.09%、13.35%、9.73%,顯然ADLS定位系統(tǒng)優(yōu)于其它兩種,和仿真效果接近
本文對無線傳感器網(wǎng)絡(luò)的定位算法進行了研究,針對該網(wǎng)絡(luò)中信標節(jié)點比率對定位精度影響較大、定位精度低等定位問題,提出了ADLS定位系統(tǒng),利用最大最小貼近度將RSSI和range-free定位機制相結(jié)合的方法去確定未知節(jié)點坐標,并通過實驗驗證了ADLS系統(tǒng)在定位精度上有較好的性能,適合于WSN 網(wǎng)絡(luò)應(yīng)用。但虛擬節(jié)點的引入增大了網(wǎng)絡(luò)的通信開銷,怎樣在保證定位精度的同時,最大程度的降低通信量將是下一步研究的主要工作。
表1 定位結(jié)果對比
[1]WANG Xiaoping,LUO Jun,SHEN Changxiang.Theory and algorithms on localization in wireless sensor networks [J].Journal of Computer Research and Development,2011,48(3):353-363 (in Chinese).[王小平,羅軍,沈昌祥.無線傳感器網(wǎng)絡(luò)定位理論和算法 [J].計算機研究與發(fā)展,2011,48(3):353-363.]
[2]Bai Yun,Li Chunming,Xue Yuan.A centroid localization algorithm for wireless sensor networks based on RSSI[C]//International Conference on Sensors,Measurement and Intelligent Materials,Applied Mechanics and Materials,2012:303-306.
[3]Rullan-Lara Jose L,Sanahuja Guillaume.Indoor localization of aquadrotor based on WSN:A real-time application regular paper[J].International Journal of Advanced Robotic Systems,2013,10 (48):679-682.
[4]Malajner Marko,Planinsic Peter,Glec h Dusan.Angle of arrival estimation using rssi and omnidirectional rotatable antenas[J].IEEE Sensors Journal,2012,12 (6):1950-1957.
[5]Kumar Shrawan,Lobiyal DK.An advanced DV-HOP localization algorithm for wireless sensor networks[J].Wireless Personal Communications,2013,71 (2):1365-1385.
[6]Zhang Dengyi,Liu Feng,Wang Lei,et al.DV-HOP localization algorithms based on centroid in wireless sensor networks[C]//2nd International Conference on Yichang,Consumer Electronics,Communications and Networks.IEEE,2012:3216-3219.
[7]Chiti F,Pierucci L.APIT2:A bit of improvement for applications in critical scenarios[C]//The 6th International Wireless Communications and Mobile Computing Conference,2010:419-423.
[8]MA Zhen,LIU Yun,SHEN Bo.Distributed locating algorithm for wireless sensor networks MDS-MAP (D)[J].Journal on Communications,2008,29 (6):57-62 (in Chinese).[馬震,劉云,沈波.分布式無線傳感器網(wǎng)絡(luò)定位算法MDSMAP (D)[J].通信學(xué)報,2008,29 (6):57-62.]
[9]SUN Kai,LIU Runjie,SHEN Jinyuan.BP localization algorithm based on virtual nodes in wireless sensor networks [J].Transducer and Technologies,2010,29 (9):122-124 (in Chinese).[孫凱,劉潤杰,申金媛.基于虛擬節(jié)點的BP無線傳感器網(wǎng)絡(luò)定位算法 [J].傳感器與微系統(tǒng),2010,29 (9):122-124.]
[10]ZHU Jian,ZHAO Hai,XU Jiuqiang,et al.Localization model in wireless sensor networks[J].Journal of Software,2011,22 (7):1612-1625 (in Chinese). [朱劍,趙海,許久強,等.無線傳感器網(wǎng)絡(luò)中的定位模型 [J].軟件學(xué)報,2011,22 (7):1612-1625.]
[11]ZHAO Jun,PEI Qingqi,XU Zhanqi.APIT localization algorithms for wireless sensor networks[J].Computer Engineering,2007,33 (5):109-111.
[12]ZHANG Hongjun,MAO Yongyi.Improved algorithm of wireless sensor network node localization [J].Journal of Computer Applications,2012,32 (8):2103-2105.
[13]Zhou Gang,He Tian,Krishnamurthy,et al.Models and solutions for radio irregularity in wireless sensor networks[J].ACM Transactions on Sensor Network Networks,2006,2(2):221-262.
[14]Wang Daifei,Tang Guoming.A new approach of double-level grid-based target localization in wireless sensor networks[C]//Sensors,2012:1-4.
[15]Zhang Xinming,Duan Zhigang,Huang shan.RSS-based efficient grid-scan localization algorithm in wireless sensor networks[C]//4th International Conference on Wireless Communications and Signal Processing,2012:142-146.
[16]Gracioli G,F(xiàn)rohlich A.Evaluation of an RSSI-based location algorithm for wireless sensor networks [J].Latin America Transactions.IEEE,2011,9 (1):830-835.