基于無線通信基站的室內(nèi)三維定位問題研究

張其明, 張 鑫

(1.湖南科技大學(xué) 商學(xué)院，湘潭 411201;2.湖南科技大學(xué) 信息與電氣工程學(xué)院，湘潭 411201)

?

基于無線通信基站的室內(nèi)三維定位問題研究

張其明1, 張 鑫2

(1.湖南科技大學(xué) 商學(xué)院，湘潭 411201;2.湖南科技大學(xué) 信息與電氣工程學(xué)院，湘潭 411201)

基于地理位置信息的商業(yè)服務(wù)具有巨大的商業(yè)價值和市場潛力，而目前定位服務(wù)主要針對于室外場景的定位，包括諸如GPS導(dǎo)航，微信，滴滴等一系列應(yīng)用軟件，然而，隨著無線通信網(wǎng)絡(luò)和移動互聯(lián)網(wǎng)的發(fā)展，基于無線通信基站的室內(nèi)三維定位將具有重要意義.利用2016年全國研究生數(shù)學(xué)建模競賽所給測試數(shù)據(jù)，采用將多維搜索簡化為分步一維搜索方法，將非線性方程組的最小二乘問題轉(zhuǎn)化為線性方程組的最小二乘問題，在全域內(nèi)搜索轉(zhuǎn)化為在窄域內(nèi)搜索等技術(shù)，在獲取終端坐標以及移動軌跡方面取得了滿意結(jié)果.

無線通信；室內(nèi)三維定位；非視距傳播；TOA定位算法

從傳統(tǒng)的GPS導(dǎo)航，到美團、微信、滴滴打車等一系列基于地理位置信息的商業(yè)服務(wù)(Location Based Service, LBS)目前已成為最具市場前景和發(fā)展?jié)摿Φ男袠I(yè)，其功能的實現(xiàn)主要是通過導(dǎo)航儀、手機、iPad等移動設(shè)備收發(fā)信號，來獲取距離、角度等測量信息，利用定位算法將測量信息轉(zhuǎn)換成坐標信息，以此對移動終端進行精準定位以及測算移動軌跡[1].

雖然商用GPS已隨著智能手機的發(fā)展而得到廣泛應(yīng)用，但是，在高樓林立的城區(qū)，建筑物內(nèi)部、地下停車場等諸多場景中，GPS室內(nèi)定位性能較差，且不能分辨用戶所在樓層等問題，因此基于室內(nèi)實時地理位置信息服務(wù)的定位系統(tǒng)越來越受到運營商重視.

目前從事室內(nèi)定位和導(dǎo)航服務(wù)的方法，大多基于室內(nèi)密集分布的WiFi設(shè)備與手機之間的電子信息流.由于WiFi設(shè)備覆蓋范圍有限，信號容易受到干擾，以及用戶對于接入陌生WiFi設(shè)備的戒備心理等問題，此類室內(nèi)定位方法并沒有得到普遍認可和施行[2].但是，基于運營商無線通信基站的方式對手機進行定位，則可以規(guī)避上述問題，主要是因為通信基站的覆蓋范圍和信號質(zhì)量均優(yōu)于WiFi設(shè)備，且能夠隨時保持對基站的接入，基于無線通信基站的定位技術(shù)有著廣闊的應(yīng)用前景和巨大的商業(yè)價值，因而受到了廣泛關(guān)注.

1 數(shù)據(jù)來源

本文采用2016年全國研究生數(shù)學(xué)建模競賽C題的相關(guān)測試用數(shù)據(jù)，具體而言是指：

針對終端定位問題，采用題中給定的10組LOS或NLOS傳播環(huán)境下從手持終端到基站的TOA測量數(shù)據(jù)和所有基站的三維坐標(測試用數(shù)據(jù)編號為case001～case010)，根據(jù)這些測量數(shù)據(jù)計算終端的三維坐標.

針對移動軌跡問題，采用題中給定的5組對處于移動過程中的一終端采集到的TOA數(shù)據(jù)(測試用數(shù)據(jù)編號為case021～ case025)，描繪終端的運動軌跡.

2 主要假設(shè)及符號說明

在對基于無線定位算法及技術(shù)的理解上，通過對有關(guān)三維定位問題的相關(guān)文獻進行研究和解讀，提出了如下在研究過程中通用的假設(shè)：

(1)假設(shè)電信號強度在傳播過程中保持穩(wěn)定；

(2)假設(shè)所有場景均在地面之上，即三維縱坐標不會出現(xiàn)負值；

(3)假設(shè)電信號傳播速度與光速一致，為c=3×108m/s；

(4)假設(shè)給定區(qū)域內(nèi)每一個基站均能接收到每一個終端發(fā)出的電信號；

(5)在誤差分析中，僅考慮時間同步誤差，信號反射、折射誤差，不考慮其他誤差；

(6)假定在非視距傳播環(huán)境下，終端發(fā)射的電信號到達基站的時間(TOA)是在視距傳播環(huán)境下所需時間的函數(shù).

在本文研究過程中，主要符號及其簡要說明如表1所示.

表1 主要符號說明

注：無線電信號在大氣中從A點向B點傳播時，如果傳播路徑為直線，則被稱為視距傳播環(huán)境(Line Of Sight propagation，簡稱LOS)[3]，如圖1(左)所示；如果在傳播過程中，由于建筑物或樹木的遮擋、反射、折射等物理現(xiàn)象，使得從A點到B點之間存在多條無線電信號的傳播路徑，這種環(huán)境被稱為非視距傳播環(huán)境(Non-Line Of Sight，簡稱NLOS)[3]，如圖1(右)所示.

圖1 LOS徑與非LOS徑示意圖

3 TOA的測量及模型設(shè)計

3.1 TOA的基本測量

當無線電信號在基站與用戶手持終端之間互相傳播時，就可以計算基站與手持終端之間的距離，一種常用的測量方式是記錄無線電信號從手持終端發(fā)出，直到基站接收到信號為止的無線電信號傳播時間，將時間乘以無線電信號的傳播速度，即得到基站與終端之間沿某條路徑的距離.其中，信號在基站與終端之間的傳播時間，被稱為無線電信號的到達時間(Time Of Arrival，簡稱TOA).

圖2 TOA示意圖

準確測量TOA需要基站計時與終端計時所使用的時鐘是同步的，即基站與終端處在同一個“時間坐標系”里.而真實的TOA受到電子器件工藝、時區(qū)、帶寬、信噪比、時鐘同步以及NLOS傳播環(huán)境的影響，TOA測量會產(chǎn)生不同的誤差[4].

3.2 TOA的誤差修正模型

在非視距傳播情況下，從移動終端發(fā)出的信號往往不能直接到達通信基站，其傳播路徑必然比直射路徑長，而且通信信號存在多種傳播路徑，一般將所能分離出來的多徑支路中最早到達通信基站的支路的傳輸時延作為信號的TOA[5].經(jīng)過初步處理后的TOA依然存在著誤差，對基于TOA的定位算法會有一定的影響，因此，本小節(jié)將主要針對在非視距傳播環(huán)境下TOA的誤差進行修正，使之對算法的影響達到最小.

3.2.1 一元線性模型

假設(shè)通過Φij的一元線性函數(shù)f1=aijΦij+dij對原始Φij進行修正，使在非視距傳播環(huán)境下的TOA修正為接近在視距傳播環(huán)境下的時間，即修正后的Φij接近于實際傳播時間.

3.2.2 多項式模型

3.2.3 指數(shù)模型

隨著傳播時間Φij的增大，修正后的時間也會增大，但在可控時間范圍內(nèi)，指數(shù)形式的修正模型亦能實現(xiàn)修正后的Φij小于原始的Φij，在一定程度上也能實現(xiàn)對Φij的有效修正，指數(shù)形式的修正模型如下：f3=aΦij+b.

3.2.4 對數(shù)模型

而南唐開國皇帝徐知誥初當宰相時，因擔(dān)心自己不夠老成，不足壓眾，于是服藥變其鬚鬢，一日成霜。后來，徐知誥的做法被宋朝的寇準所效仿。對此，清朝學(xué)人洪亮吉的《北江詩話》有載：“徐知誥輔吳之初，年未強仕，以為非老成不足壓眾，遂服藥變其須鬢，一日成霜。宋寇萊公急欲作相，其法亦然。余見近時公卿，須鬢皓然，而百方覓藥以求其黑者，見又出二公下矣?！贝硕送ㄟ^服藥讓頭發(fā)變白，都是為了裝成熟，扮滄桑，目的是為了在政治上更加穩(wěn)固。

由于非視距環(huán)境的存在，信號在傳播過程中容易受到各類障礙物的反射、折射和吸收的影響，但是隨著信號傳播時間Φij的逐步增大，理應(yīng)對其時間進行的修正效果越不明顯，故其效應(yīng)是以邊際遞減方式進行，因此采用對數(shù)模型具有理論可行性，假設(shè)對數(shù)修正模型為：f4=ln(Φij-a)+b，可對其進行算法驗證.

至于在實際過程中采用哪一種模型對原始Φij進行修正，可結(jié)合測試用數(shù)據(jù)對相應(yīng)的算法和模型進行驗證后進行取舍.本文依據(jù)對Φij的修正模型進行算法驗證的效果，決定采用測試效果較好的一元線性模型對后續(xù)問題進行分析和求解.

3.3 基于非視距傳播的TOA定位模型

當通信基站在空間隨機分布時，考慮通信信號在非視線(NLOS)傳播環(huán)境下的TOA算法，其主要思想為用一新變量代替定位估計中的二次項，把非線性估計轉(zhuǎn)化為兩步最大似然(ML)的線性估計[6]，并通過前文所述的構(gòu)建TOA的函數(shù)對原始TOA進行修正，以及逐步迭代的方法確定修正函數(shù)中的參數(shù)，消除NLOS傳播時的時間誤差對定位算法的影響.

當通信基站分布在一條直線上時，定位過程將簡化，目前針對這種情況有許多優(yōu)化的處理技術(shù)[7].而當通信基站在空間隨機分布時情況將比較復(fù)雜，對此也提出了一些處理方法，主要有精度較高的兩步最大似然(ML)TDOA估計方法，它在非視距(NLOS)傳播干擾不十分嚴重時非常有效[8].由于上述的一系列算法都沒有考慮NLOS傳播干擾對定位的影響，在NLOS干擾嚴重時，這些TDOA算法均會失效.因此下文將主要針對通信基站在空間隨機分布的情形提出考慮NLOS傳播影響的TOA定位算法.與其它方法相比較，此方法計算量不大且精度很高[9].

假設(shè)在三維空間中任意地分布著M個通信基站，從標號為i的移動終端ui(x,y,z)發(fā)射的信號到達標號為j的通信基站Aj的時間為TOA(ui,Aj)，同時也等價于前文所述的Φij，在非視距傳播環(huán)境下，終端坐標滿足如下條件：

(1)

將式(1)展開，得到如下方程組：

(2)

在式(2)中，逐一將n*式-1*式，其中，n=2,3，…,M，構(gòu)造一個含有M-1個方程的線性方程組，可得：

(3)

令X=(xyz)T，將式(3)轉(zhuǎn)化為矩陣形式，則有

AX=B；

(4)

其中，

通過最小二乘法解得X=A/B，然后將解向量X代入(2)式，并將等式的右邊項目移至方程左邊，定義誤差向量ξ，ξ=(ξ1，ξ2，…，ξM)T，定義偏差方程組為：

(5)

如前所述，本文采用一元線性模型f1=aijΦij+dij對TOA進行時間誤差修正，并且r=c*f1，c表示信號傳播速度，將每一個對應(yīng)的r代入式(5)，通過逐一迭代的方法確定修正模型中的參數(shù)aij和bij，并可得出對應(yīng)的誤差向量ξj，以范數(shù)為評判標準，求解出使得誤差ξ最小時的修正的終端坐標.

3.4 模型計量結(jié)果及評價

3.4.1 定位算法檢驗及結(jié)果

由給定條件可知，若知道某終端到3個基站之間的直線距離，就可以對該終端進行精準定位，但題目所給終端到達基站的時間可能是視距傳播時間，也可能是非視距傳播時間，因而問題的核心就是找出終端到達基站無障礙直線傳播時間與所測時間(TOA)的關(guān)系.由于在同一場景中，終端與基站之間的信號傳播過程具有一定的相似性，因而我們可以用線性函數(shù)關(guān)系來近似描述終端到達基站無障礙直線傳播時間與所測時間(TOA)的關(guān)系.

基于上述分析，主要步驟如下：

第一步：從1開始，用一維搜索一次多項式的系數(shù)(所測時間的倍數(shù))，使其滿足：修正后的TOA所對應(yīng)的距離與此距離下求得的近似終端到基站的距離的差的平方和最小，即誤差最小.由于誤差最小的點為終端的位置，因此，系數(shù)所對應(yīng)的誤差應(yīng)該是先變小，然后再變大.

第二步：求由修正距離等于假設(shè)終端到基站的距離組成的非線性方程組的最小二乘解.

第三步：把方程組中的第一個方程與其他方程相減，將第二步的非線性方程組的最小二乘問題轉(zhuǎn)變成線性方程組的最小二乘問題.

第四步：迭代一次多項式的一次項系數(shù)，當誤差開始變大時，停止迭代.

第五步：固定一次項系數(shù)，在一次項的一個步長距離內(nèi)，用同樣方法迭代，找到常數(shù)項.

第六步：考察此時的誤差，若誤差較大，則可以調(diào)小前面迭代中的步長，使得誤差較小.

第七步：用前面迭代得到的多項式關(guān)系，對終端到基站的測距進行修正，用最小二乘法，得到終端的近似坐標.

第八步：從題中所給基站坐標，以及終端到基站的距離數(shù)據(jù)可知，Z坐標變化對誤差的貢獻遠小于X,Y坐標對誤差的貢獻，而在迭代過程中的最小二乘解是一簇解中的一個，故最后的結(jié)果是Z坐標與基站Z坐標相距(一般很小)太大，處理方法：在Z的某個范圍內(nèi)(實際情況是在基站縱坐標上下)，以所求解的X,Y坐標為中心(微調(diào))，用迭代得到一個最優(yōu)近似解.

根據(jù)基于非視距傳播環(huán)境下TOA的三維定位算法及模型，針對測試用數(shù)據(jù)進行了算法驗證，測算結(jié)果顯示，基于非視距傳播環(huán)境下TOA的三維定位算法有較好的擬合性，能夠較為精準的對測試用移動終端進行有效定位，總體誤差較小.本文分別選取測試用數(shù)據(jù)包sample_case001～005_input.txt文件中前10組數(shù)據(jù)進行算法驗證，分別得出如下擬合結(jié)果，如表2所示.

表2 測試用數(shù)據(jù)擬合效果

下面以sample_case001文件中前10組數(shù)據(jù)為代表，具體列示定位算法的擬合值，如下表3所示：

表3 測試用數(shù)據(jù)擬合值

數(shù)據(jù)來源：測試用數(shù)據(jù)來自數(shù)據(jù)包sample_case001_input.txt文件.

在驗算的三維坐標中，X軸、Y軸和Z軸的擬合數(shù)據(jù)與實際結(jié)果相當接近，由于選取的終端坐標較為隨機，X軸和Y軸的空間范圍較大，而Z軸的數(shù)據(jù)變化幅度不大，較為平緩，便于擬合結(jié)果與實際結(jié)果在圖中的比對，如圖3所示，Z軸坐標擬合效果相當接近實際結(jié)果，由此說明基于非視距傳播TOA的三維定位算法具有良好的擬合效果.

3.4.2 運動軌跡分析與擬合結(jié)果

依據(jù)競賽用數(shù)據(jù)，每一個case文件中給出的一組數(shù)據(jù)表示一個終端在不同時刻的TOA數(shù)據(jù)，在基站坐標為二維時，即可確定終端在不同時刻的平面上的二維坐標(x，y)，序號表示終端坐標出現(xiàn)的時間順序，假定序號i代表終端的Z軸，根據(jù)第一問給出的基于非視距傳播的TOA定位算法，并利用Matlab軟件，可按坐標序號即時間的先后順序逐一在三維空間中畫出坐標的位置(x，y，i)，并通過空中投影可得到終端坐標在平面上的運動軌跡.

通過前文給出的TOA定位算法，分別得出移動終端在不同時間的坐標，并利用Matlab軟件描繪出運動軌跡.下面僅以case21文件中所給數(shù)據(jù)，移動終端的運行軌跡如圖4所示.

注：數(shù)據(jù)來源于sample_case001_input.txt文件前10組數(shù)據(jù)的Z軸數(shù)據(jù)及擬合值.

圖3Z軸坐標擬合效果圖

圖4 case21移動終端軌跡圖(平面)

圖5 case21移動終端軌跡圖(三維)

4 結(jié)論及展望

基于地理位置信息的服務(wù)(LBS)目前在國內(nèi)外都存在著巨大的市場和商業(yè)價值，然而，LBS在室內(nèi)定位方面還存在著很大的缺陷，同時也存在著巨大的發(fā)展?jié)摿?基于無線通信基站的室內(nèi)三維定位相比于傳統(tǒng)的GPS定位而言，在覆蓋廣度和深度上存在明顯優(yōu)勢，而且能夠分辨用戶所在樓層等問題，另一方面，能夠在商場、博物館等應(yīng)用場景，以及智能倉儲、智能工廠、固定資產(chǎn)追蹤等行業(yè)中提供基于室內(nèi)實時地理位置信息的商業(yè)服務(wù)和增值服務(wù)，因此，這一領(lǐng)域是運營商和新興創(chuàng)業(yè)公司爭相實施戰(zhàn)略的方向和重點.

基于通信基站的定位問題研究，還在科研和工業(yè)界吸引了極高的關(guān)注.一方面，定位問題與統(tǒng)計信號處理、最優(yōu)估計理論、優(yōu)化算法等諸多領(lǐng)域都有密切的聯(lián)系，諸如數(shù)據(jù)擬合、最小二乘估計、半正定規(guī)劃、流形學(xué)習(xí)等諸多數(shù)學(xué)工具都能夠被用于求解上述問題.另一方面，工業(yè)界對于如何高精度地在現(xiàn)有通信設(shè)備上完成上述功能也表現(xiàn)出了濃厚的興趣，我國除了服務(wù)業(yè)已廣泛部署商用的北斗導(dǎo)航系統(tǒng)之外，也在積極推進基于室內(nèi)室外融合定位的羲和導(dǎo)航系統(tǒng).

本文結(jié)合國內(nèi)外已有的相關(guān)研究對室內(nèi)定位算法進行了深入分析和探討，進一步改造和創(chuàng)新了基于非視距傳播環(huán)境下TOA的定位算法，并對測試用數(shù)據(jù)進行了驗算，結(jié)果表明，本文采用的基于非視距傳播的TOA定位算法具有良好的擬合效果，能夠使得在盡可能少的基站數(shù)目下，實現(xiàn)移動終端的最優(yōu)三維定位精度.

我們相信，此模型和算法能夠符合運營商提出的基站定位的相關(guān)要求，基于此算法的定位系統(tǒng)能夠?qū)︳撕蛯?dǎo)航系統(tǒng)的技術(shù)手段和進一步完善有所助益，同時，也希望基于此算法的室內(nèi)定位系統(tǒng)能夠在現(xiàn)代商業(yè)通信網(wǎng)絡(luò)中發(fā)揮作用，進一步發(fā)揮出巨大的經(jīng)濟和社會效益.

[1] 王 昕,王宗欣,劉 石.一種考慮非視線傳播影響的TOA定位算法[J].通信學(xué)報,2001(3):1-8.

[2] 段凱宇,張力軍.一種在NLOS環(huán)境下提高精度的TDOA定位方法[J].南京郵電學(xué)院學(xué)報,2005(5):15-17.

[3] 李海蓮.基于移動終端的室內(nèi)三維定位及跟蹤技術(shù)研究[D].北京:北京郵電大學(xué)碩士學(xué)位論文,2013.

[4] 石高濤,王伯遠,吳 斌.基于WiFi與移動智能終端的室內(nèi)定位方法綜述[J].計算機工程,2015(9):39-44+50.

[5] 劉 林.非視距環(huán)境下的無線定位算法及其性能分析[D].成都:西南交通大學(xué)碩士學(xué)位論文,2007.

[6] 史 龍.無線傳感器網(wǎng)絡(luò)自身定位算法研究[D].西安:西北工業(yè)大學(xué)碩士學(xué)位論文,2005.

[7] 李 莉.基于時間測量值的無線定位算法研究[D].成都:西南交通大學(xué)碩士學(xué)位論文,2002.

[8] 徐鳳燕.室內(nèi)無線定位算法研究[D].上海:復(fù)旦大學(xué)碩士學(xué)位論文,2008.

[9] 張保峰,劉同佩,韓 燕,等.基于TOA的三維空間定位算法研究[J].計算機工程與設(shè)計,2007,14:364-366.

Research on Indoor Three Dimensional Localization Based on Wireless Communication Base-station

ZHANG Qi-ming1,ZHANG Xin2

(1. Business School of Hunan University of Science and Technology, Xiangtan 411201, China; 2. School of Information and Electrical Engineering, Hunan University of Science and Technology, Hunan University of Science and Technology, Xiangtan 411201, China)

The commercial service based on location information has great commercial value and market potential. But at present, the main needle positioning services are mainly for outdoor scene positioning, including a series of applications such as GPS navigation, We Chat, Drops Taxi and so on. However, with the development of wireless communication network and mobile Internet, indoor 3D localization based on wireless communication base-station will be of great significance. In this paper, the test data is given by the national graduate student mathematical modeling contest in 2016, adopting the methods; multidimensional search is simplified as a step-by-step dimension search; the least squares problem of the nonlinear equations is transformed into the linear equations, and global search is transformed into narrow domain search. Finally, satisfactory results have been obtained in the acquisition of the terminal coordinates and trajectories.

wireless communication; indoor 3D localization; non line of sight transmission; TOA location algorithm

2017-02-22

張其明(1992-)，男，碩士研究生，研究方向：公司財務(wù)管理.

TN929

A

1671-119X(2017)02-0013-06