趙榮陽,李小龍,梁家海
1(北部灣大學(xué) 電子與信息工程學(xué)院,廣西 欽州 535011) 2(湖南工商大學(xué) 新零售虛擬現(xiàn)實技術(shù)湖南省重點實驗室,長沙 410205)
室內(nèi)定位能在室內(nèi)環(huán)境下為指定對象和用戶提供有效的跟蹤[1]、定位和導(dǎo)航服務(wù),停車場、商場、火車站等場所對定位和導(dǎo)引的需求日趨強(qiáng)烈.這些需求為室內(nèi)定位系統(tǒng)[2](Indoor Positioning System,IPS)提供了巨大的機(jī)會.對比于其它的室內(nèi)定位技術(shù),如視頻分析定位[3]、基于可見光通信的定位[4]等,無線定位技術(shù)具有覆蓋區(qū)域廣、定位精度高[5]、成本低等特點[6].目前,不同的無線室內(nèi)定位系統(tǒng)(Wireless Indoor Positioning System,WIPS)依賴于不同的無線基礎(chǔ)設(shè)施[7],如ZIGBEE、藍(lán)牙[8](Bluetooth)、WIFI[9]和RFID等.為了促進(jìn)無線室內(nèi)定位技術(shù)的快速發(fā)展和推廣應(yīng)用,關(guān)鍵的問題是在保持定位準(zhǔn)確性的同時、盡可能地降低系統(tǒng)成本,以促進(jìn)無線室內(nèi)定位行業(yè)的快速推廣和健康發(fā)展.
對于WIPS中的無線節(jié)點來說,系統(tǒng)芯片的價格在其生產(chǎn)成本上占據(jù)著較高的比例.目前,常見的通信芯片有Nordic Semiconductor公司的nRF24系列芯片,廣泛應(yīng)用于藍(lán)牙產(chǎn)品、兼容于IEEE 802.15的Texas Instruments公司的CC2540系列芯片,廣泛應(yīng)用于WIFI產(chǎn)品、兼容于IEEE 802.11協(xié)議的Atmel公司的Atmel?Smart Connect WIFI系列芯片等.通過比較這些廣泛應(yīng)用于無線產(chǎn)品的商業(yè)芯片,運(yùn)行在2.4GHz的nRF24系列芯片,如nRF24L01+,在價格成本上最有優(yōu)勢[10].這種芯片具有能耗低、傳輸速率快、數(shù)據(jù)幀的有效載荷比高等優(yōu)點,然而這些芯片存在著如下的功能限制:沒有RSSI(Received Signal Strength Indicator)的感知能力,也就是無法測量收到的信號強(qiáng)度[11],僅提供多個無線射頻輸出功率來調(diào)節(jié)信號的傳輸范圍,并且接收節(jié)點收到發(fā)送節(jié)點的最小離散輸出功率(Received Minimum Discrete Output Power,RMDOP)與其傳輸范圍之間不服從均勻分布[12].
圖1 芯片功率檔位關(guān)系示意圖Fig.1 Schematic diagram of the relationship between chip power and distance
如圖1所示,假設(shè)此類芯片的L個離散輸出功率的檔位從P1~PL逐漸增大,相應(yīng)功率檔位的最大傳輸距離為r1,r2…rL(rL-1 考慮弱信號感知能力通信芯片的功能限制,當(dāng)芯片作為無線定位系統(tǒng)參考節(jié)點,隨機(jī)部署在二維平面的待定位區(qū)域內(nèi)時,區(qū)域內(nèi)的接收點無法預(yù)先確定其接收到的各參考節(jié)點的RMDOP值,故對弱感知芯片無線定位系統(tǒng)做如下性質(zhì)假設(shè): 1)僅考慮RMDOP與其傳輸范圍(距離)之間的關(guān)系,忽略環(huán)境對信號傳輸?shù)母蓴_; 2)數(shù)量為n的弱感知芯片作為定位系統(tǒng)的參考節(jié)點,隨機(jī)部署之后,參考節(jié)點的物理位置已知且靜止; 3)弱感知芯片具有P1~PL+1,共L+1個離散功率輸出檔位,其中P1~PL功率檔位為接收點能夠收到的功率值,各檔位對應(yīng)呈遞增關(guān)系的最大傳輸距離:r1,r2,rl…rL(rl-1 4)待定位區(qū)域以網(wǎng)格方式劃分,每一個單元網(wǎng)格的物理位置由其中心點的坐標(biāo)表示; 5)待定位區(qū)域內(nèi)每一個單元網(wǎng)格的指紋向量,由其中心點的指紋向量表示; 弱感知芯片的離散功率輸出特性,是產(chǎn)生本文所研究問題的主要原因之一.在提出具體問題模型之前,首先給出相關(guān)定義. 定義1.最小接收功率(RMDOP):假設(shè)參考節(jié)點i的物理坐標(biāo)為(xi,yi),i∈(1,2,…,n),待定位的二維平面區(qū)域,被劃分為邊長為d的G個正方形單元網(wǎng)格,其中網(wǎng)格j的中點物理坐標(biāo)為(xj,yj),j∈G,rij表示參考節(jié)點i到網(wǎng)格j中心點的距離,那么在此距離范圍下,網(wǎng)格j接收能夠接收到參考節(jié)點i的功率最小值,稱為最小接收功率(RMDOP),記為:Pij. 定義2.單元網(wǎng)格指紋:單元網(wǎng)格中心點接收各參考節(jié)點發(fā)送的RMDOP值序列,稱為單元網(wǎng)格指紋,即:Fj= 定義3.高差異度指紋:假設(shè)任意兩個單元網(wǎng)格j與g的中心點之間的物理距離,等于兩個單元網(wǎng)格邊長之和的1/2,稱它們?yōu)橄噜従W(wǎng)格;當(dāng)采用歐式距離判斷Fj與其所有的相鄰網(wǎng)格指紋Fg存在的差異程度時,若存在一個較大的標(biāo)量δ,使得不等式:|Fj-Fg|≥δ均成立,即滿足公式(1)時,則稱Fj為高差異度指紋;其中,設(shè)Nj為單元網(wǎng)格j的相鄰網(wǎng)格數(shù)目,F(xiàn)g= Min(|Fj-Fg|)≥δ,j∈G,g∈Nj (1) 考慮任意此類室內(nèi)定位系統(tǒng)的指紋庫內(nèi),皆可能存在高差異度指紋,本文針對存在的高差異度指紋采用迭代分割的方法,即將高差異度指紋的單元網(wǎng)格,分割成若干個邊長更小的子網(wǎng)格,當(dāng)子網(wǎng)格序列獲得定義2的單元格指紋之后,構(gòu)成了定位系統(tǒng)的一個具有動態(tài)精度的指紋庫,以達(dá)到提高系統(tǒng)定位精度的目的. 假設(shè)待定位區(qū)域的總面積為S,初始指紋網(wǎng)格的邊長為d0;通過迭代調(diào)度、動態(tài)分割高差異度指紋的單元網(wǎng)格后,未被分割的非高差異度指紋的單元網(wǎng)格總面積記為S0,指紋網(wǎng)格邊長為d0,僅實現(xiàn)迭代一次的高差異度指紋的單元網(wǎng)格分割面積為S1,分割后的子網(wǎng)格邊長為d1;實現(xiàn)二次迭代的高差異度指紋的單元網(wǎng)格分割面積為S2,分割后的子網(wǎng)格邊長為d2;以此類推,實現(xiàn)K次迭代的高差異度指紋的單元網(wǎng)格分割面積為SK,分割后的子網(wǎng)格邊長為dK;其中,d1,d2,…,dK之間的符合如下關(guān)系:d1=α×d2…dK=α×dK-1α<1.因此,此類室內(nèi)無線定位系統(tǒng)的動態(tài)定位精度模型,如公式(2)所示,其中A為動態(tài)定位精度值. (2) 針對基于弱感知通信芯片的定位系統(tǒng),一般情況下動態(tài)精度方法的迭代次數(shù),取決于某次迭代后,重構(gòu)的指紋庫內(nèi)是否存在高差異度指紋.通常迭代次數(shù)越多,動態(tài)精度將越高,但是迭代次數(shù)的增加,將會增大指紋庫建立階段的采樣耗時及系統(tǒng)開銷.設(shè)有一個較小的系統(tǒng)定位精度標(biāo)量值ε,當(dāng)動態(tài)定位精度值符合條件A<ε時,停止迭代,稱ε為動態(tài)精度無線定位方法的截止精度. 定義4.動態(tài)指紋庫:設(shè)在初始指紋庫建立之后,所有單元網(wǎng)格的邊長均相等,為靜態(tài)指紋庫;當(dāng)靜態(tài)指紋庫內(nèi)存在定義3所述的高差異度指紋,并實現(xiàn)了高差異度指紋的K次迭代分割后,重構(gòu)的含有不同單元格網(wǎng)格邊長、具有動態(tài)定位精度的新指紋庫,稱為動態(tài)指紋庫. 隨機(jī)部署的弱感知芯片作為室內(nèi)無線定位系統(tǒng)參考節(jié)點,考慮芯片的功能限制,系統(tǒng)有如下特點: 1)參考節(jié)點芯片僅提供若干傳輸范圍可調(diào)節(jié)的輸出功率檔位,具有離散性; 2)接收節(jié)點收到發(fā)送節(jié)點的RMDOP值與其傳輸范圍之間不服從均勻分布; 3)芯片作為參考節(jié)點的部署情況隨機(jī),即:在芯片部署之前,參考節(jié)點的位置坐標(biāo)、參考節(jié)點之間的距離等是不確定的. 4)室內(nèi)定位系統(tǒng)的平均定位精度,取決于待定位區(qū)域網(wǎng)格化的單元網(wǎng)格劃分情況; 因此,在網(wǎng)格化的待定位區(qū)域內(nèi),當(dāng)任意單元網(wǎng)格j的指紋Fj為高差異度指紋時,可以通過迭代的方法,動態(tài)分割此高差異度指紋的單元網(wǎng)格,將其劃分為m×m個子網(wǎng)格,以提高基于弱感知芯片隨機(jī)部署的室內(nèi)定位系統(tǒng)的定位精度.動態(tài)精度指紋庫的調(diào)整策略,包括如下步驟: 步驟1.在待定位的MM二維區(qū)域內(nèi),根據(jù)起始點的物理坐標(biāo)、待定位區(qū)域面積、靜態(tài)指紋單元網(wǎng)格邊長、面積,計算待定位區(qū)域內(nèi)的靜態(tài)指紋網(wǎng)格總數(shù)G、各單元網(wǎng)格中心點的位置坐標(biāo); 步驟2.計算待定位區(qū)域內(nèi)任意單元網(wǎng)格j的中心點與參考節(jié)點i之間的距離,并比較參考節(jié)點傳輸功率的距離范圍序列r1,r2,rl…rL(rl-1 步驟3.依據(jù)單元網(wǎng)格指紋與其相鄰網(wǎng)格之間的指紋差異程度,判別指紋庫內(nèi)的高差異度指紋,通過迭代法動態(tài)分割高差異度指紋的單元網(wǎng)格,并重構(gòu)一個含有不同單元網(wǎng)格邊長的動態(tài)指紋庫G1; 步驟3.1.遍歷靜態(tài)指紋庫G,依據(jù)定義3,當(dāng)單元網(wǎng)格的指紋Fj滿足公式1時,記錄Fj為高差異度指紋;將高差異度指紋的單元網(wǎng)格j,重新劃分為m×m的子網(wǎng)格,每一個子網(wǎng)格的邊長,為原高差異度指紋的單元網(wǎng)格邊長的α倍,并根據(jù)定義2計算子網(wǎng)格的指紋,其中m≥2,0<α<1;當(dāng)所有高差異度指紋的單元網(wǎng)格均被重新劃分之后,全部指紋重新構(gòu)建為一個,含有不同單元網(wǎng)格邊長的動態(tài)指紋庫G1; 步驟3.2.遍歷動態(tài)指紋庫G1,迭代執(zhí)行步驟3.1,直到當(dāng)前被遍歷的動態(tài)指紋庫G1內(nèi)不存在高差異度指紋,或者定位精度小于精度標(biāo)量ε,終止算法,從而獲得室內(nèi)定位系統(tǒng)最優(yōu)的動態(tài)指紋庫G1. 靜態(tài)指紋庫是定位系統(tǒng)采用動態(tài)精度定位方法時的初始指紋庫,根據(jù)定義2可知,單元網(wǎng)格指紋是其中心點接收各參考節(jié)點發(fā)送的RMDOP值序列,即:Fj= (3) 圖2 靜態(tài)指紋庫建立流程圖Fig.2 Chart of static radio map building 重復(fù)上述操作直至獲得單元網(wǎng)格j與所有參考節(jié)點的RMDOP值,并以j接收到的各個參考節(jié)點的RMDOP值序列,構(gòu)成單元網(wǎng)格j的指紋向量Fj,當(dāng)待定位區(qū)域內(nèi)的所有單元網(wǎng)格均被賦值后,獲得定位系統(tǒng)的靜態(tài)指紋庫.靜態(tài)指紋庫建立的算法程序流程圖,如圖2所示. 動態(tài)指紋庫的構(gòu)建過程中,首先遍歷靜態(tài)指紋庫G,若存在Fj,jG,滿足公式(1),則靜態(tài)指紋庫G內(nèi)存在高差異度指紋,然后記錄高差異度指紋,并迭代分割其單元網(wǎng)格.每一個高差異度指紋的單元網(wǎng)格被劃分為m×m的子網(wǎng)格序列,以dj表示高差異度指紋Fj的單元網(wǎng)格j的邊長,d表示分割后的子網(wǎng)格邊長,其中d=αdj,m≥2,0<α<1.本文取m=2,d=1/2dj,算法執(zhí)行的過程中,將根據(jù)高差異度指紋的單元網(wǎng)格中心點位置坐標(biāo)、子網(wǎng)格邊長,重新計算子網(wǎng)格的中心點坐標(biāo),然后利用靜態(tài)指紋庫的構(gòu)建方法,生成高差異度指紋Fj的子網(wǎng)格指紋序列;最后,將新生成的各高差異度指紋的子指紋序列與靜態(tài)指紋庫,重構(gòu)為一個含有不同單元網(wǎng)格邊長的新指紋庫-動態(tài)指紋庫,指紋同樣記為Fk= 依據(jù)動態(tài)指紋庫的構(gòu)建步驟3.2,迭代遍歷、重構(gòu)動態(tài)指紋庫G1.當(dāng)動態(tài)指紋庫G1內(nèi)不存在高差異度指紋,或者動態(tài)定位精度值符合條件A<ε,即定位精度A小于系統(tǒng)的截止精度標(biāo)量ε時,得到的指紋庫G1被認(rèn)為是系統(tǒng)的最優(yōu)動態(tài)指紋庫,終止迭代算法.動態(tài)指紋庫的構(gòu)建程序流程圖,如圖3所示. 圖3 動態(tài)指紋庫構(gòu)建流程圖Fig.3 Chart of dynamic radio map building 目標(biāo)點的位置估計,是室內(nèi)無線定位系統(tǒng)最終的目標(biāo),即當(dāng)系統(tǒng)獲得目標(biāo)點T的指紋向量FT后,在動態(tài)指紋庫G1內(nèi)尋找FT的匹配指紋Fg,g∈G1.在眾多的指紋序列匹配方法中,本文選擇了歐式距離函數(shù),來求解兩個指紋的匹配度,計算如公式(4). (4) 公式(4)中dist表示目標(biāo)指紋FT與G1內(nèi)指紋Fg的匹配程度,當(dāng)dist=0時,F(xiàn)T與Fg完全匹配;當(dāng)dist0時,使得dist取最小值的Fg為FT的最優(yōu)匹配值.因為指紋向量是由芯片參考節(jié)點的離散輸出功率檔構(gòu)成,采用距離最鄰近(NN)方法進(jìn)行位置估計時,可能存在不唯一的最優(yōu)匹配值,即:目標(biāo)節(jié)點T可能存在k個估計值,k≥1.因此,本文在遍歷動態(tài)指紋庫、計算所有單元網(wǎng)格指紋與目標(biāo)指紋FT的距離時,將目標(biāo)點T的匹配指紋Fg以dist值的升序,存儲于候選估計隊列Q中,并選擇k最近鄰(KNN)匹配方法,計算k個最優(yōu)匹配指紋的單元網(wǎng)格中心點平均坐標(biāo),作為目標(biāo)點的位置估計結(jié)果,計算如公式(5).其中(xT,yT)為目標(biāo)點的位置估計坐標(biāo),(xg,yg)為最優(yōu)匹配指紋Fg的單元網(wǎng)格中心點坐標(biāo),k的值由候選估計隊列Q內(nèi),最優(yōu)匹配指紋Fg的數(shù)目決定. (5) 設(shè)參考的接收功率為1-5檔,傳輸距離分別為[3,5,7,8,9],仿真模擬弱感知通信芯片作為參考節(jié)點,隨機(jī)部署在20×20的二維平面;選取了各接收功率傳輸距離的均方差,作為高差異度指紋判別標(biāo)量δ;靜態(tài)指紋庫邊長的初始值d0=4;在參考節(jié)點數(shù)目n=7、n=10、n=20的條件下,分別完成15次獨(dú)立實驗.實驗以動態(tài)指紋庫的一次、二次迭代定位精度為考察目標(biāo),主要從參考節(jié)點數(shù)目與高差異度指紋的迭代次數(shù)、動態(tài)定位精度之間的關(guān)系;動態(tài)指紋庫、靜態(tài)指紋庫的系統(tǒng)精度、節(jié)點定位誤差等方面評估動態(tài)精度定位算法的性能. 在動態(tài)精度定位算法的15次獨(dú)立實驗中,當(dāng)參考節(jié)點數(shù)目n=7時,出現(xiàn)了1次不迭代(未出現(xiàn)高差異度指紋)、5次只進(jìn)行一次迭代的情況;當(dāng)n=10時,僅出現(xiàn)1次只進(jìn)行一次迭代的情況;當(dāng)n=20時,15次實驗均進(jìn)行了二次迭代.算法的一次、二次迭代精度如表1、表2所示. 表1 一次迭代定位精度Table 1 Resolution for positioning in the first iteration 表2 二次迭代定位精度Table 2 Resolution for positioning in the second iteration 在參考節(jié)點數(shù)目分別為n=7、n=10、n=20時,動態(tài)指紋庫的一次、二次迭代分割后,定位精度的對比情況,如圖4(a)-(c)所示.圖4(a)是n=7時的精度對比、圖4(b)是n=10時的精度對比,可以看出當(dāng)n=7與n=10的條件下,根據(jù)公式(2)的計算方法,發(fā)現(xiàn)二次迭代與一次迭代相比較,對于系統(tǒng)定位精度的提高效果并不明顯;但在圖4(c)n=20時的精度對比圖中,15次實驗中,二次迭代后的定位精度均小于2,并隨著迭代次數(shù)的增加,定位精度有較為明顯的提高. 因此可知,在動態(tài)精度算法中,高差異度指紋的出現(xiàn)概率,隨著參考節(jié)點數(shù)目的增加而增大;算法的迭代效果、定位精度,也隨著參考節(jié)點數(shù)目的增加而提高,圖4(d)是參考節(jié)點數(shù)目n=7、n=10、n=20條件下,算法二次迭代的定位精度效果對比圖. 由上述分析可知,待定位區(qū)域面積、初始的靜態(tài)指紋網(wǎng)格邊長固定時,高差異度指紋的出現(xiàn)概率、數(shù)目,將隨著參考節(jié)點數(shù)目增加而增大,在動態(tài)分割高差異度指紋后,系統(tǒng)的動態(tài)精度提高也更為顯著. 圖4 定位精度對比圖Fig.4 Chart of resolution comparing 文獻(xiàn)[12]中詳細(xì)介紹了一種基于弱感知芯片固定部署的室內(nèi)定位技術(shù)—TrackCC,并在文中給出了TrackCC、LANDMARC、SAIL三種定位方法的位置評估誤差CDF函數(shù)圖,其中,基于弱感知芯片的TrackCC,定位誤差小于0.5米的概率達(dá)到68%,而SAIL小于0.5米的定位誤差的約為5%,LANDMARC則約為2.5%. 圖5 位置估計誤差對比圖Fig.5 Chart of error comparing for position estimating 本文的仿真實驗中,在參考節(jié)點數(shù)目n=10、n=20的條件下,待定位區(qū)域內(nèi)隨機(jī)生成目標(biāo)節(jié)點,分別通過傳統(tǒng)的靜態(tài)指紋庫方法、動態(tài)精度方法完成目標(biāo)節(jié)點的位置估計,其定位誤差的累積概率(CDF)、單個節(jié)點定位誤差情況,如圖5所示. 圖5(a)是當(dāng)參考節(jié)點n=10時的位置估計CDF分布圖,其中動態(tài)精度方法的定位誤差小于0.5的概率可達(dá)到約20%,定位誤差小于1的概率可達(dá)到約40%,并且定位誤差小于3的概率可達(dá)到85%以上.圖5(b)是當(dāng)參考節(jié)點數(shù)目n=20時的位置估計CDF,動態(tài)精度方法的定位誤差小于0.5的概率可上升至約40%,定位誤差小于1的概率可達(dá)到70%以上,并且在定位誤差小于2.5時,概率逼近100%.與此同時,在圖5(a)、(b)中可以看出靜態(tài)指紋庫方法的定位誤差小于0.5米的概率可達(dá)到10%左右,定位誤差小于1米的概率可達(dá)到約20%,而且當(dāng)參考節(jié)點由n=10增加到n=20之后,動態(tài)精度定位方法與靜態(tài)指紋庫方法相比較,其定位精度的提升更為顯著. 此外,仿真實驗中選取了20個隨機(jī)目標(biāo)節(jié)點,觀察單個節(jié)點的定位誤差精度,如圖5(c)、(d)所示.圖5(c)為當(dāng)n=10時的節(jié)點位置估計誤差對比,圖5(d)為n=20時的節(jié)點位置估計誤差對比.通過單個目標(biāo)節(jié)點采用動態(tài)精度法與靜態(tài)指紋庫方法,進(jìn)行位置估計的單點誤差對比,可以看出在參考節(jié)點數(shù)目n=20時,動態(tài)精度法的單個節(jié)點定位誤差精度,相較于傳統(tǒng)的靜態(tài)指紋庫方法,也有顯著的提高. 仿真實驗表明,在待定位區(qū)域面積、初始指紋單元格邊長固定的條件下,動態(tài)精度的定位效果與參考節(jié)點的數(shù)目有較為重要的關(guān)聯(lián),增加參考節(jié)點的數(shù)目,使得指紋庫內(nèi)高差異度指紋的數(shù)目增大,進(jìn)而提高了動態(tài)精度方法的迭代次數(shù)和迭代效果,但同時也增加了動態(tài)精度指紋庫建立階段的采樣耗時.因此,適當(dāng)?shù)膮⒖脊?jié)點數(shù)目、適當(dāng)?shù)南到y(tǒng)定位精度,對于本算法的應(yīng)用效果較為重要.如圖5所示,本文仿真環(huán)境下,當(dāng)參考節(jié)點數(shù)目n=20時,動態(tài)精度方法獲得了較好地定位效果.因此,動態(tài)精度的定位方法較靜態(tài)指紋庫方法,更適合弱感知通信芯片作為參考節(jié)點,在隨機(jī)部署的情況,能夠獲得更高的定位精度. 定位精度是評價室內(nèi)無線定位系統(tǒng)的主要指標(biāo)之一.目前,關(guān)于低成本、弱感知能力傳感器芯片,用于無線定位系統(tǒng)的研究,鮮有動態(tài)定位精度的相關(guān)文獻(xiàn).文獻(xiàn)[12]中基于固定部署的弱感知芯片,提出了一種室內(nèi)定位技術(shù)—TrackCC,雖然獲得了較高的定位精度,但其精度并沒有動態(tài)提高的特性,且芯片部署的人力投入較高.因此,本文提出了一種基于弱感知芯片的動態(tài)精度無線定位方法,考慮該類芯片存在的功能限制,通過接收點的最小接收功率建立指紋數(shù)據(jù)庫,利用物理相鄰指紋之間的差異程度,記錄并重新劃分高差異度指紋,構(gòu)建動態(tài)精度指紋庫,旨在提高此類傳感器芯片,在隨機(jī)部署的情況下,獲得較高地系統(tǒng)定位精度.2 問題描述
2.1 網(wǎng)絡(luò)模型
2.2 問題建模
3 動態(tài)指紋庫調(diào)整策略
4 動態(tài)精度定位算法描述
4.1 靜態(tài)指紋庫的構(gòu)建
4.2 動態(tài)指紋庫的構(gòu)建
4.3 位置估計方法描述
5 實驗仿真
5.1 定位精度分析
5.2 位置估計誤差評估
6 結(jié) 論