對抗室外環(huán)境下NLOS誤差的TOA無線定位迭代算法無線定位優(yōu)化

1、. . 裝訂線. . . xxxx 大學畢 業(yè) 論 文題目：對抗室外環(huán)境下 NLOS 誤差的 TOA 無 線定位迭代算法 學 院 信息科學與工程學院 專業(yè)班級 通 信 工 程1班 屆 次 學生姓名 學 號 指導教師 二 O 一四 年 六 月 十四 日XXXXXX 學士學位論文I目 錄1 1 緒論緒論 .1 11.1 無線定位技術(shù)的簡介 .11.1.1 無線定位的概述.21.1.2 無線定位技術(shù)的發(fā)展過程 .22 2 無線定位技術(shù)的原理及算法介紹無線定位技術(shù)的原理及算法介紹 .4 42.1 無線定位技術(shù)的工作原理.42.2 基于 TOA 測距算法介紹.52.2.1 最小均方(LS)算法【1】.6

2、2.2.2 近似最大似然估計(AML)算法【1】.72.2.3 殘差加權(quán)(Rwgh)算法【1】.82.2.4 殘差檢測(RT)算法【1】.93 3 基于基于 T TO OA A 的新算法的思路與設計的新算法的思路與設計.11113.1 新算法的思路 .113.1.1 牛頓迭代算法.113.1.2 高斯牛頓迭代法.113.1.3 最速下降法 .123.2 TOA 新算法設計與說明 .123.2.1 TOA 算法設計 .123.2.2 TOA 算法說明 .124 4 算法仿真與算法仿真與結(jié)結(jié)果分析果分析.14144.1 算法仿真過程.144.2 仿真結(jié)果分析.165 5 TOATOA 算算法法展望

3、展望【2】【2】.1818參考文獻參考文獻.1919致致 謝謝.2020附附 錄錄.2 21 1XXXXXX 學士學位論文IIContents1 Foreword1 1.1The introduction of Wireless positioning technology2 1.1.1 Overview of wireless positioning technology2 1.1.2 The history of wireless positioning technology22 The principle and algorithm of wireless positioning tec

4、hnology5 2.1 The technology indicators of digital oscilloscope5 2.2 Based on TOA ranging algorithm6 2.2.1 LS algorithm6 2.2.2 AML algorithm6 2.2.3 RWGH algorithm6 2.2.4 RT algorithm63 Thinking and design of new algorithm based on TOA13 3.1 The new method of thinking13 3.1.1 Newton-Raphson method13 3

5、.1.2 Gauss-Newton method13 3.1.3 Steepest descent method13 3.2 New algorithm design and description17 3.2.1 Algorithm design13 3.2.2 The simulation software of PROTEUS17 3.2.2 PROTEUS platform using simulation system184 Algorithm simulation and result analysis20 4.1 Algorithm simulation process20 4.

6、2 Simulation result analysis205 TOA algorithm prospect22References24Acknowledgments 25Appendix26對抗室外環(huán)境下 NLOS 誤差的 TOA 無線定位迭代算法【摘要】通過測量基站 3 條以上路徑移動站的信號的到達時間（TOA）,可以對移動站進行定位。然而信道的時間和空間的變化所導致非視距(NLOS)傳輸導致無線定位技術(shù)面臨的巨大困難,信號的非視距傳輸卻極大地影響了 TOA 定位算法的定位精度，不同的定位算法在不同的環(huán)境條件下獲得的定位精度也是不同的。傳統(tǒng)的 TOA 定位算法有包括最小均方算法 、最大似然

7、估計算法 、殘差加權(quán) 和殘111差檢測算法 。本文也提出一種在非視距環(huán)境下克服 NLOS 誤差的新的算法思路。以迭代法為主不斷1逼近準確值，達到減小誤差的目的?！娟P(guān)鍵詞】 非視距，TOA、迭代、凸松弛NLOS Error Mitigation for TOA-Based Localization via Iterative【Abstract】The location of MS can be got according to three or more arrival time of signals from MS to BS . But, the accuracy of TOA (time

8、of arrival) is influenced by the non-line-of-sight (NLOS) transmission. The NLOS transmission of the signal affects the accuracy of the TOA, and the different positioning accuracy of the positioning algorithm is also different in different environment conditions. The traditional TOA localization alg

9、orithm includes LS algorithm, the AML algorithm, the RWGH algorithm and the RT algorithm. This paper also proposes a new algorithm for overcoming the NLOS error in the NLOS environment. Simulation results show that the proposed location algorithm can restrain NLOS error effectively, and has better l

10、ocation accuracy than the traditional location algorithms.【Key words】NLOS, Time of Arrival，Iterative，Convex Relaxation XXXXXXX 學士學位論文11 1 緒論緒論 對移動臺的定位是無線通信業(yè)務提供商的一項基本業(yè)務，自從 1996 年美國 FCC 提出第一個緊急呼救檢測的條款以來，對移動目標的定位已經(jīng)引起了人們的極大關(guān)注。如今，手機等移動終端大量普及，它們的各種應用都有定位的請求。如地圖，團購等客戶端。同時，無線定位技術(shù)在公共安全服務(如緊急醫(yī)療、緊急定位、緊急報警服務)、犯

11、罪偵查、蜂窩系統(tǒng)設計、動態(tài)資源管理、基于位置的信息服務、車輛及船舶管理、導航和智能交通系統(tǒng)等方面的應用非常廣泛【16】。因而定位的準確度是決定此類軟件服務好壞的重要條件。因此，我們迫切的需要找到適合的方法來滿足高度精確定位需求。首先，提高定位的精確度，可以提高民眾生活的便利性，可以精確的指導出行，減少了出行成本;其次，也為野外救援，抗震救災打下了堅實的技術(shù)支持，為生命提供了生存的可能;最后，高精度的定位也為軍事，礦產(chǎn)，農(nóng)業(yè)等領域的提供了便利。使打擊目標更加精確；使井下人員活動情況得到了解；使農(nóng)業(yè)病蟲害更加精確防治。 當前，移動站的無線定位方法主要包括：基于信號到達時間的(TOA)、基于信號到達

12、時間差的(TDOA)、基于信號到達角度的(AOA)和基于到達信號強度的(RSSI)4 種方法。基于上述各參量的定位技術(shù)各有其優(yōu)缺點，比如基于信號強度的定位技術(shù)，周圍環(huán)境的變化、墻壁、植被、金屬、玻璃等因素都會嚴重影響其定位精度，而 AOA 技術(shù)則需要在基站架設天線陣列，另外非視距傳播(NLOS)、遠近效應、多用戶干擾都是定位技術(shù)發(fā)展要克服的困難。為了有效提高算法的跟蹤性能，多站協(xié)同、多種測量方式融合是目前定位跟蹤的主要趨勢。定位的環(huán)境的主要分為視距(Lineof-sight，LOS)和非視距(None1ineof-sight，NLOS)【4】。在視距環(huán)境中，可以較為精確的對目標進行定位。干擾因

13、素少，只有測量時產(chǎn)生的高斯白噪聲。但在實際的環(huán)境下，由于高山和建筑物等的影響，信號的傳輸總是沿著非視距(NLOS)道路傳輸，信號的 NLOS 傳輸極大的降低了算法的定位精度。在蜂窩移動通信系統(tǒng)中,常用的基于信號波到達時間(TOA)的方法來定位移動臺。時間的測量精度決定了定位精度。1 ns 延時測量誤差對應距離誤差為 0.3 米【5】。到達時間測量（TOA）誤差主要是由兩部分組成：系統(tǒng)測量誤差和多徑衰落和多址干擾,NLOS 傳播誤差。系統(tǒng)測量誤差服從高斯分布,隨著技術(shù)的發(fā)展將逐漸減少,但其他一些誤差因素受到傳播環(huán)境的干擾始終存在。因此,NLOS 傳播誤差的主要因素之一。為了減少 NLOS 傳播對

14、定位精度的影響,產(chǎn)生了卡爾曼濾波方法【6】、ML 和貝葉斯方法【7】、散射模型方法【8】、BF 參數(shù)方法【9】、高階統(tǒng)計量方法【10】和 MUSIC 方法【11】等。但運用這些方法需要增加一些系統(tǒng)增加了系統(tǒng)成本和復雜性【5】。隨著科技高速發(fā)展，粗略的無線定位的功能已不能滿足人們的要求，較完善的定位算法是以精確的定位，簡易的設備，易于發(fā)展完善為優(yōu)勢?，F(xiàn)在無線定位技術(shù)正朝著精確化、智能化發(fā)向飛速發(fā)展。隨著科學技術(shù)的發(fā)展，無線定位技術(shù)將不斷精確和完善。1.11.1 無線定位技術(shù)的簡介無線定位技術(shù)的簡介XXXXXXX 學士學位論文21.1.1 無線定位的概述無線定位是指利用無線電波直線恒速傳播特性通過

15、測量固定或運動的物體的位置以進行定位的技術(shù)。通過直接或間接測定無線電信號在已知位置的固定點與移動臺之間傳播過程中的時間、相位差、振幅或頻率的變化，確定距離、距離差、方位等定位參數(shù)，進而用位置線確定待定點位置的測量技術(shù)利方法。無線定位系統(tǒng)有雷達、無線電導航系統(tǒng)、無線電測向和全球定位系統(tǒng)等。(1)雷達雷達是利用電磁波探測目標并定位的設備。它對目標發(fā)射電磁波并接收其回波，由此獲得目標的速度、方位角和高度信息。利用雷達對目標定位時，是測定目標相對于雷達的距離和方位。對空中目標進行定位時，須同時測定距離、方位和高度，雷達測量目標距離時，實際是測發(fā)射脈沖間的時間差，因為電磁波以光速傳播，據(jù)此可算出目標的距

16、離；目標的方位利用雷達天線的銳方位波束測量；根據(jù)所測目標的仰角和距離。就可求得目標的高度。雷達定位主要應用在軍亊上，用于搜索和引導、跟蹤測量和火力控制。(2)無線電導航無線電導航是利用電磁波傳播和其他相關(guān)知識,通過相關(guān)參數(shù)的確定,以實現(xiàn)車輛、飛機和其他運動定位和導航。導航和定位密切相關(guān),連續(xù)定位本質(zhì)上是導航。大多數(shù)無線電導航系統(tǒng)是協(xié)作式的,賴于信標導航信號發(fā)射, 使運動中的載體根據(jù)每個導航臺方位以及星辰、地貌以準確判定所處的位置而進行工作。發(fā)射裝置主要在地面，也可以安裝在衛(wèi)星或飛機上。無線電波以導航信息的方法很多，且均以利用無線電波的恒速、直線傳播為基礎。無線電導航技術(shù)的基本要素是測角和測距，

17、因此可以組成測角-測角、測距-測距、測角-測距和測距差（雙曲線）等系統(tǒng)。(3)全球定位系統(tǒng)（GPS，北斗）GPS 系統(tǒng)可以全天候的為全球范圍任何移動臺提供高精度的位置和時間信息。系統(tǒng)由空間(衛(wèi)星)、地面監(jiān)測和用戶接收機由三個部分組成?？臻g部分有 18 顆（或 21 顆）高度為 2 萬公里的導航衛(wèi)星，運轉(zhuǎn)在 6 個傾角為 55的圓軌道平面上，每面相隔 60，軌道周期為 12h，保證在地球上任何地點任何時刻均能看到 4 顆以上仰角大于 5的衛(wèi)星，每顆導航星上均載有穩(wěn)定度為 10-13/日的原子鐘，這是 GPS 之所以能精確定位、授時的基礎。每個衛(wèi)星以 L 頻段的兩個頻率連續(xù)發(fā)送導航信號，并采用擴頻

18、技術(shù)來提高抗干擾能力。這兩個信號分別稱為粗測碼（C/A 碼）和精測碼（P 碼）。前者可供民用，定位25m 以內(nèi)；后者專供軍用，定位精度在 110m 內(nèi)。兩種信號均含有可向用戶接收機提供所需的衛(wèi)星情況、系統(tǒng)時間、接收機正在跟蹤的衛(wèi)星的星歷（目前和將來的位置）等信息。北斗定位系統(tǒng)原理和 GPS 大致相同,只是略有不同1.1.2 無線定位技術(shù)的發(fā)展過程無線定位在軍事和民用技術(shù)中已獲得了廣泛應用。最初，對地面移動用戶的定位來XXXXXXX 學士學位論文3說，以 GPS 最為重要。但是把 GPS 功能集成到移動臺上需全面更改設備和網(wǎng)絡，增加成本；且用戶同時持有移動電話和 GPS 手機很不方便，所以移動用

19、戶及設備生產(chǎn)商和網(wǎng)絡運營商希望能直接由移動臺實現(xiàn)定位。近年來，由于對移動臺用戶定位的需求增加，進一步推動了無線定位的研究。1996年美國聯(lián)邦通信委員會(FCC)頒布了 E-911【15】法規(guī)，要求 2001 年 10 月 1 日起蜂窩網(wǎng)絡必須能對發(fā)出緊急呼叫的移動臺提供精度在 125m 內(nèi)、準確率達到 67的位置服務【12】。1998 年又提出了定位精度為 400m、準確率不低于 90%的服務要求?！?2】1999 年 FCC 對定位精度提出新的要求：對基于網(wǎng)絡定位的精度為 100m、準確率達 67% ，精度 300m、準確率達 95%；對基于移動臺的定位為精度 50m、準確率 67% ，精度

20、 150m、準確率 95%。FCC的規(guī)定大大推動了蜂窩無線定位技術(shù)的發(fā)展。 12如今，已經(jīng)實現(xiàn)了蜂窩網(wǎng)絡定位和 GPS 定位的融合。如智能手機，如今的移動臺既可以用蜂窩基站定位，也可以實現(xiàn) GPS 定位。但由于定位需求的不斷增加，對精度要求越來越高，仍需要設計新的方式，新的算法去滿足要求。XXXXXXX 學士學位論文42 2 無線定位技術(shù)的原理及算法介紹無線定位技術(shù)的原理及算法介紹2.12.1 無線定位技術(shù)的工作原理無線定位技術(shù)的工作原理無線定位方法就是利用信標節(jié)點間信號的到達時間、到達時間差、到達信號角度、和到達信號強度信息確定位置坐標的方法。 到達時間法到達時間法（TOA，Time of

21、Arrival）定位的原理是：測量待定位節(jié)點（,）0X0Y與已知至少 3 個信標節(jié)點（，）之間的信號到達時間，再乘以信號速度 v，計算出iXiYiT待定位節(jié)點與各信標節(jié)點之間的距離，分別以信標節(jié)點（，）為圓心，為半徑iRiXiYiR做圓，各圓的交點為待定位節(jié)點（,）的坐標。0X0YBS2BS1 BS3 R R2 2R R1 1R R3 3MS圖圖2.12.1 基于基于TOATOA定位的基站、移動臺幾何關(guān)系定位的基站、移動臺幾何關(guān)系( (理想情況下理想情況下) )根據(jù)幾何原理如圖 2.1 所示，設 BS1，BS2，BS3分別為已知節(jié)點，MS 為未知節(jié)點。則得到方程組式為： 22200112220

22、202222203033()()()()()()IXXYYRXXYYRXXYYR（1）求解方程組（1）【13】，得待定位節(jié)點的坐標位置（,） 。對于 TOA 定位方法，影0X0Y響精度的主要因素是時鐘同步誤差和到達時間的測量誤差。如果信標節(jié)點與待定位節(jié)點iT無法做到精確的時鐘同步，則所測得的信號到達時間會有時間誤差，導致存在偏差，iR使三個圓無法交匯，或交匯處不是一點而是一片區(qū)域，造成定位誤差【13】。XXXXXXX 學士學位論文5到達時間差法（TDOA）由于 TOA 定位方法中信標節(jié)點與待定位節(jié)點間時間同步要求非常嚴格，需要增加硬件成本，因此采用到達時間差法（TDOA，Time Differ

23、ence of Arrival）定位方法。TDOA 定位方法不要求嚴格的時間同步，相對簡化了定位系統(tǒng)，應用更加廣泛。TDOA 法通常有兩種實現(xiàn)方式。一種是發(fā)射節(jié)點同時發(fā)射兩種不同傳播速度的無線信號，接收節(jié)點根據(jù)已知的這兩種信號的傳播速度以及兩種信號的到達時間差，計算待定位節(jié)點和信標節(jié)點之間的距離，通過計算待定位節(jié)點和至少 3 個信標節(jié)點之間的距離，用三圓相交法確定待定節(jié)點的坐標位置。另一種實現(xiàn)方式，待定位節(jié)點（,）向兩個信標節(jié)點（） 、 （）同時0X0Y11,X Y22,XY發(fā)射信號，由于待定位節(jié)點與兩個信標節(jié)點之間的距離不同，通過已知信號的傳播速度v 和兩個信標節(jié)點接收到信號時間差 t 相乘

24、，可確定待定位節(jié)點在以兩個信標節(jié)點為焦點、距離差為 vt 的雙曲線上。通過測量至少三個信標節(jié)點之間的信號到達時間差，構(gòu)成一組關(guān)于待定位節(jié)點坐標的雙曲線方程組（2） ，求解該雙曲線方程組可得到移動臺的估計位置。 22221122122222332232()()()()()()()()()()xxyyxxyyv ttxxyyxxyyv tt（2）到達角度法到達角度法（AOA，Angle of Arrival）定位原理是：待定位節(jié)點向信標節(jié)點發(fā)射信號，通過信標節(jié)點測定信號到達的角度，解算出待定位節(jié)點的坐標。在二維空間中，測得兩個信號到達信標節(jié)點的到達角度 AOA，信標節(jié)點根據(jù)各測得的 AOA 直線方

25、向取其交點，解出待定位節(jié)點的坐標。假設信標節(jié)點（） 、 （）測得待定位節(jié)點信號到達角度分別為、，根11,X Y22,XY12據(jù)幾何關(guān)系可求出待定位節(jié)點位置（,） 。AOA 法定位精度受天線測角精度影響，增0X0Y加信標節(jié)點布點密度或使用天線陣列可提高定位精度。信號強度法信號強度法（RSSI，Received Signal Strength Indication）定位原理為：通過檢測信號接收端接收功率，通過傳播損耗模型，計算節(jié)點間的距離 d，根據(jù)三邊定位方法tP（如圖 2.1） ，解出信標節(jié)點的位置坐標。2.22.2 基于基于 TOATOA 測距算法介紹測距算法介紹 首先，我們討論一下，噪聲對定

26、位的影響。室外 NLOS 環(huán)境中，存在的噪聲主要有兩種。一種是 NLOS 噪聲，另一種是測量計算噪聲。NLOS 噪聲是由于高大建筑物、高山等引起的信號非直線傳播造成的。由于高大物體的阻擋，信號必須進行繞射，此時信號在空氣中衰減程度會進一步加劇。繞射對信號的強度，到達目標的傳輸時間，傳播的角XXXXXXX 學士學位論文6度都有極大的影響。以 TOA 為基礎的算法中，到達接收基站的傳輸時間的延遲對定位產(chǎn)生極大的影響。同樣，若以 RSSI 為基礎的算法則對接收信號的強度要求較高。若以 AOA為基礎的算法則對接收信號的角度要求較為準確。測量計算噪聲則是由設備測量估算造成的。若以 TOA 為例，發(fā)送基站

27、與接收基站的時間必須同步。若不同步則會產(chǎn)生測量誤差，即測量的時間差不準確，若此不準確的時間差乘以光速，會產(chǎn)生更大的誤差對定位精確度產(chǎn)生干擾。在 RSSI 系統(tǒng)中，用來測量信號強度的設備也可造成測量計算誤差。若測量的精度的不準確就會對定位精度產(chǎn)生較大的影響。同樣，以 AOA 基礎的測量方法也存在類似的問題。為此，我們用 MATLAB 仿真一下噪聲的影響，matlab 程序見（附錄一） 。仿真結(jié)果如圖 2.2圖圖 2.22.2 NLOSNLOS 環(huán)境中噪聲對定位精度的影響環(huán)境中噪聲對定位精度的影響根據(jù)仿真的數(shù)據(jù)顯示移動臺準確位置的坐標為（13.8537，-4.7766） 。在加入均值為1，方差為

28、2 的高斯噪聲以后，有三個基站進行定位的結(jié)果是（14.0578，-2.9345） 。移動臺的定位坐標與準確位置坐標的歐式距離相差 1.8534。由此可見，噪聲對定位精確度有較大的影響。這里，我們只是假設基站在最佳的固定位置。在現(xiàn)實生活中，基站的位置是不定的，隨著地域的變化而變化，定位精度會進一步降低，誤差會進一步加大。在蜂窩移動通信系統(tǒng)中，常以測量信號到達時間（TOA）為基礎的方法對移動臺進行定位。對時間差的測量準確度決定了此方法的定位精度。資料顯示，1 ns 的時延測量誤差對應 03 m 的距離誤差【5】。TOA 測量誤差主要是由系統(tǒng)測量誤差和多徑衰落、多址干擾、NLOS 傳播以及遠近效應等

29、產(chǎn)生的誤差組成【5】。系統(tǒng)測量誤差服從高斯分布，隨著技術(shù)的發(fā)展會逐漸減小，而其他一些誤差因素受電波傳播環(huán)境的影響始終存在。因而，NLOS 傳播誤差是其中的主要因素【13】。如何運用基于 TOA 的各種算法來減少 NLOS 傳播對XXXXXXX 學士學位論文7定位的干擾，是本文重點要解決的問題。對于 TOA 定位方法，常用的定位算法有最小均方算法(LS)【1】，似然最大似然估計算法(AML)【1】，殘差加權(quán)算法【1】和殘差檢測算法（RT）【1】等2.2.1 最小均方(LS)算法【1】設移動臺的位置坐標是，基站的位置及其坐標分別為 A(,)，B(),Tdx y0X0Y11,X YC()?；镜臄?shù)目

30、要大于等于 3.假設移動臺與第 n 個基站之間的測量距離為。22,XYnR則 （1）222nnnRxxyy多個基站運用式（1）整理后寫成矩陣形式為： A=B (2) 其中，1122330.50.50.5xyAxyxyTxyR22Rxy22211122222222233312xyrBxyrxyr列出方程組即可算出的值。 通過仿真程序見（附錄二） 。得仿真結(jié)果如下圖： 圖圖 2.32.3 無無 NLOSNLOS 噪聲定位原理圖噪聲定位原理圖 圖圖 2.42.4 NLOSNLOS 噪聲下基于噪聲下基于 LSLS 定位原理圖定位原理圖圖中所示的情況是基站（BS）數(shù)目為 3，移動臺（MS）數(shù)目為 1 的

31、定位結(jié)果。理想狀態(tài)下，以基站為中心的三個圓是相較于一點的，即此點為移動臺的位置。但在 NLOS 環(huán)境下是不可能達到理想情況的。由于非視距的傳播造成的誤差，以參考基站為圓心的三圓不會相交于一點，誤差必定存在。通過 LS 算法會減小誤差，但不會消除誤差。由圖 2.3 可以看出，移動臺的準確坐標為 A（30,30） ，同時由程序也可以看出XXXXXXX 學士學位論文8“MS_ini”所表示的為原坐標。由 2.4 可以看出在 NLOS 環(huán)境下定位的估計坐標為B（29.6495，31.4237） 。 。A 和 B 點相差的歐式距離為 1.4662。這只是其中一次定位產(chǎn)生的誤差。不能說明每次定位的誤差都只

32、是 1.4662。定位誤差甚至會更大。2.2.2 近似最大似然估計(AML)算法【1】 設移動臺的坐標是 。n 個基站的坐標分別為 。測量距離可, x y00,xy,nnx y表示為： (3)0iiiRRN其中， 表示存在誤差的測量距離。 則表示 LOS 距離，也就是位移距離。 表示iR0iRiN測量誤差（包括 NLOS 誤差和測量計算誤差） 。其服從均值為零的高斯分布的白噪聲。其協(xié)方差矩陣為： （4）222(,)TCOVE NNdiag a aa 利用最大似然估計法求使最大似然函數(shù)（消耗函數(shù) J）最小的 的值。iN (5)222222()2()iiiiiiiiiiiiiiiig xg yg

33、RxyRxh RxyRyhxh y 其中，R 是移動臺 MS 以圓心為原點的半徑，其次。 （6）00iiiiixxgRRR （7）00iiiiiyyhRRR 求解過程：首先，從矩陣中解出R（其中R是x和y的函數(shù)） ，其次，將其關(guān)系式帶入式 22Rxy（8）中，將其兩方程式聯(lián)立方程組，則可解出移動臺的坐標 。此外由于基站的數(shù)目增多，( , )x y可能會出現(xiàn)多個的值，此時的選取原則為：如果兩個根中只有一個根為正值，則取( , )x y正值，如果兩個根都為正值，則選取可使R值最小的根，如果兩個根都為負值，則選取絕對值再進行選擇。2.2.3 殘差加權(quán)(Rwgh)算法【1】 XXXXXXX 學士學位論

34、文9最小均方 LS 算法可以表示為 2arg min()iixr sXrXX（9）其中， 為范數(shù)運算，s 為不同的基站。 是關(guān)于某特定 x 值所獲得的殘差。iirxx若以 表示殘差的平方，則必定滿足下式sR 2(, )()siii sR X Srxx（10） 其中，x 的最小均方估計對應于。其值為。由于測量過程中，不同的分( , )sR x s( , )sR x s組中基站的數(shù)目是不同的，為了數(shù)據(jù)的處理，所以要將各組數(shù)據(jù)進行歸一化處理。因而設歸一化后的最小均方值為 (, )( , )ssR X SR x ssizeofs（11）假設計算過程中一共有 M 個基站，這 M 個基站可以得到 N 種組

35、合，當然每種基站組合中基站的個數(shù)一定大于等于 3.我們運用排列組合的知識即可得出 N 的值 3MiMiNC（12） 對于每一種組合，我們都計算出他們的最小均方值的估計值。即和 ，其kX(,)skkR XS中 k=1，2，。則移動臺的位置可通過下式獲得： 1111(,)(,)NkskkkNskkkXR XSXR XS（13） 此時即可獲得較為準確的X的估計值 。X2.2.4 殘差檢測(RT)算法【1】 設。我們可以通過前面2.2.3節(jié)所講的方法評估出多個 的值。設有N個。( , )x y進而我們可以計算出歸一化殘差的平方為XXXXXXX 學士學位論文10 ， 22( )()( )( )xxx k

36、x NkB k（14） 22( )()( ),1,2,3,( )yyy ky NkkNB k（15） 其中， 和 為不同基站組合對應的CRLB（Cramer-Rao low bound 誤( )xB k( )yB k差性能下界）的下界。 ，由統(tǒng)計學的知識可以推測到，變量是服從參數(shù)為1的卡方分布，2因此，我們可以設定一個合理的判決門限，使得 變量大于判決門限的概率為0.02，因2此，查表可得此判決門限為271。 接下來，我們分析一下具體的求解步驟：設基站可以接周到的視距信號個數(shù)為M，首先計算N個估計值，然后計算出 ， ，和。然后計算 標( )k( )xB k( )yB k2( )xk2( )yk

37、2量大于最佳判決門限的個數(shù)。我們設此數(shù)目為n。n應該滿足以下條件。因此0.2(1)nN我們可以判斷出視距信號的數(shù)目M。若M值不成立，則可進而計算M-1的n的值。進而再次重復上述步驟。以此類推，直到判斷條件即可。此外要特殊說明，當判斷視距信號數(shù)目為3時，可以采用delt檢測算法【1】。XXXXXXX 學士學位論文113 3 基于基于 TOATOA 的新算法的思路與設計的新算法的思路與設計3.13.1 新算法的思路新算法的思路由于NLOS作用，預示著根本無法極為準確的求出準確的位置坐標，只能不斷逼近。類似于二分法。從根本上講就是迭代法。迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程，跟迭代

38、法相對應的是直接法，即一次性解決問題。迭代法又分為精確迭代和近似迭代。 “二分法”和“牛頓迭代法”屬于近似迭代法。迭代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值【14】。不管移動臺還是基站，隨著科學技術(shù)的不斷發(fā)展，運算速度會不斷的加快，這也使迭代法的運用有了根本保證。不僅是計算機，手機，平板電腦，基站等都可以滿足基站的要求。因而我們可以利用計算的速度優(yōu)勢來減少NLOS環(huán)境下的誤差。達到不斷提高定位精度的目的。接下來的幾節(jié)里介紹幾種迭代法。3

39、.1.1 牛頓迭代算法 牛頓迭代法（Newtons method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method） ，它是牛頓在 17 世紀提出的一種在實數(shù)域和復數(shù)域上近似求解方程的方法。多數(shù)方程不存在求根公式，因此求出精確根非常困難，甚至不可能，從而尋找方程的近似根就顯得特別重要。方法使用函數(shù) f(x）的泰勒級數(shù)的前面幾項來尋找方程 f(x) = 0 的根。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點是在方程 f(x) = 0 的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根，此時線性收斂，但是可通過一些方法變成超線性收斂。該方法廣泛用于計算機編程

40、中。 設 r 是 的根，選取（已知）作為 r 的近似初始值。過點作曲線( )0f x 0 x00,()xf xXXXXXXX 學士學位論文12 。 的切線。則方程為( )yf x1L 000()()()yf xfxxx（1）求出與 x 軸交點的橫坐標：1L 0100()()f xxxfx（2）稱 x1 為方程 r 的一次近似值。同理。再次過點 作的切線，并求該切11( ,( )xf x( )yf x線與 x 軸交點的橫坐標為 (3)1211( )( )f xxxfx稱為 r 的二次近似值。重復以上過程，即可得 r 的近似值序列，迭代值會不斷逼近 r2x的真實值。需要說明的是 1()()nnnn

41、f xxxfx（4）為 r 的 n+1 次估計值。不斷地重讀上述的計算方法，即為牛頓迭代法。3.1.2 高斯牛頓迭代法高斯牛頓迭代法（Gauss-Newton）的基本思想是使用泰勒級數(shù)展開式去近似地代替非線性回歸模型，然后通過多次迭代，多次修正回歸系數(shù)，使回歸系數(shù)不斷逼近非線性回歸模型的最佳回歸系數(shù)，最后使原模型的殘差平方和達到最小。由以往的參考文獻里可以看出，高斯牛頓迭代法具有收斂快，精確度高的優(yōu)點，二次迭代就使精確度高達 99.97%，相關(guān)指數(shù)也明顯提高。理論上可以證明高斯牛頓迭代法經(jīng)過數(shù)次迭代后，估計回歸系數(shù)將逼近最佳的待估回歸系數(shù)，使殘差平方和達到最小，從而明顯地克服了最小平方法的不足

42、。其缺陷是計算量較大，但隨著電子計算機的日益普及，這點計算就顯得微不足道了。3.1.33.1.3 最速下降法最速下降法最速下降法（steepest descent method）是一種利用高等數(shù)學中梯度和極值的性質(zhì)，結(jié)合數(shù)值計算的方法而形成的一種尋找局部極值的方法。最速下降法是求解無約束優(yōu)化問題最簡單和最古老的方法之一，雖然現(xiàn)在已經(jīng)不具有實用性，但是許多有效算法都是以它為基礎進行改進和修正而得到的。最速下降法是用負梯度方向為搜索方向的，最速下降法越接近目標值，步長越小，前進越慢。它是一個最優(yōu)化算法，常用于機器學習和人工智能當中用來遞歸性地逼近最小偏差模型。理論上也屬于一種無限逼近的迭代法。梯度

43、下降下法的計算過程就是沿遞度下降的方向求解極小值（也可以沿遞度上升方向求解極大值） 。其迭代公式為 1( )kkkaas k（5）XXXXXXX 學士學位論文13其中 為梯度的負方向，表示梯度方向上的搜索步長。我們可以通過對函數(shù)求( )s kk導得到梯度方向，步長的確定比較麻煩，太大了的話可能會發(fā)散，太小收斂速度又太慢。一般情況下，確定步長的方法是由線性搜索算法來確定。 因為一般情況下，梯度向量為 0 的即 說明是到了一個極值點，此時梯度的幅值也為 0。因而采用梯度下降算法進行最優(yōu)化求解時，算法迭代的終止條件是梯度向量的幅值接近 0 即可。3.23.2 TOATOA 新算法設計與說明新算法設計

44、與說明3.2.1 TOA 算法設計由第二章我們指出，之前很多方法都采用殘差的思想。迭代法只有一個 AML 算法。殘差加權(quán)是根據(jù)殘差不同的比重，算出殘差的加權(quán)平均值，進而評估出較為準確的定位坐標。減少了 NLOS 誤差帶來的影響。殘差檢測則是從接收的所有有用信號中檢測出視距信號，然后用視距信號進行評估定位。但這兩種方法運算較為復雜。我們也可以使用另一種方法，就是迭代法，好處是不需要復雜的處理器，只需定位設備有一定的運算速度即可。以上所講的三種方法都可以運用到定位算法中去。既然我們不能得到 100%的定位精確度，為什么不去不斷逼近呢。3.2.2 TOA 算法說明在這里，首先我們假定基站的數(shù)目，同時

45、確定參考基站的位置。此時我們隨機產(chǎn)生移動臺（MS）的位置。則我們此時可以確定距離方程 R 為 R= d + err(t,s)（6）其中 R 為移動臺到基站的檢測距離（包括 NLOS 誤差） ，d 為移動臺到基站的真實距離（即 LOS 檢測距離） 。是誤差函數(shù)，是時間和位置的二元函數(shù)，函數(shù)本身會隨著時( , )err t s間和空間不斷變化。R 的值越逼近與某一值，NLOS 測量誤差越小。因此我們要充分利用迭代法來無限逼近與 R 的最小值。即無限逼近于 LOS 距離。(1)牛頓迭代算法根據(jù)牛頓迭代算法的原理，我們可以知道，通過不斷地建立函數(shù) R-grad(R)的切線,來確定 R 函數(shù)梯度為零的點

46、，即為 R 的極值。切線 L=0 的根會不斷地逼近就，且近似的等于方程 R-grad（R）的根。這里我們要借助海塞矩陣來進行牛頓迭代法。(2)高斯牛頓迭代算法根據(jù)高斯牛頓迭代算法，我們可以知道，通過調(diào)整回歸系數(shù)，達到非線性擬合的目的。進而逼近真實距離 d。這里我們要借助雅克比矩陣來進行計算。在向量微積分中，雅可比矩陣是一階偏導數(shù)以一定方式排列成的矩陣，其行列式稱為雅可比行列式。雅可比矩陣的主要作用是對給出點的最優(yōu)線性逼近。雅可比矩陣類似于多元函數(shù)的導數(shù)。(3)最速下降法 根據(jù)最速下降法的原理，我們可以了解到，對于方程 R。我們可以計算它的梯度，只XXXXXXX 學士學位論文14要順著方程 R

47、梯度減小的方向?qū)ふ液退阉?，必定會找到方?R 梯度為零的地方。此時，此點即為方程 R 的極值點。我們只需判斷其是最小值即可。進而得到最小距離 R。也就是近似等于視距距離。4 4 算法仿真與結(jié)果分析算法仿真與結(jié)果分析4.14.1 算法仿真過程算法仿真過程根據(jù)前一節(jié)所述的運算方法，在這里，我們假定基站的數(shù)目為 4，同時確定參考基站的位置。坐標分別為， ，。隨機產(chǎn)生移動臺（MS）的位置，(0,0)(0,10)(10,0)(10,10)設坐標為。進行維度為二維的 matlab 定位仿真。分別使用牛頓迭代算法，高斯牛頓(2,3)迭代算法和最速下降法進行逼近運算。仿真出結(jié)果圖進行分析比較。程序見（附錄三）

48、 。仿真結(jié)果如下：XXXXXXX 學士學位論文15圖圖 4.14.1 對于指定的對于指定的 BSBS 和和 MSMS 定位結(jié)果圖定位結(jié)果圖 圖圖 4.24.2 基站對移動臺定位的結(jié)果放大圖基站對移動臺定位的結(jié)果放大圖XXXXXXX 學士學位論文16圖圖 4.34.3 橫坐標的估計值與迭代次數(shù)的關(guān)系橫坐標的估計值與迭代次數(shù)的關(guān)系圖圖 4.44.4 縱坐標的估計值與迭代次數(shù)的關(guān)系縱坐標的估計值與迭代次數(shù)的關(guān)系XXXXXXX 學士學位論文174.24.2 仿真結(jié)果分析仿真結(jié)果分析仿真結(jié)果：結(jié)論一，由圖 4.3，圖 4.4 可知，仿真的出的橫縱精確度隨著迭代次數(shù)的增加而提高。結(jié)論二，最速下降法的收斂速

49、度最慢，也就是說，需要多次迭代才能達到穩(wěn)定。牛頓迭代法與高斯牛頓法收斂都是較快的，收斂效果最好的是牛頓迭代法。收斂速度排序為：牛頓迭代法高斯牛頓法 最速下降法結(jié)論三，效率最高的是高斯牛頓法。由程序可以看出，牛頓迭代法運算程序比較復雜，相對需要更多的時間和能耗。而最速下降法收斂慢，效率最低。效率的排序為：高斯牛頓法牛頓迭代法最速下降法結(jié)論四，從算法的簡易程度來說，最速下降法最優(yōu)，算法最為簡易。由仿真程序可以看出牛頓迭代法最為復雜。復雜程度順序為：最速下降法 高斯牛頓法 牛頓迭代法。結(jié)論五，從算法的作用范圍來講，高斯牛頓迭代法只能用于求解非線性最小二乘問題，而牛頓迭代法可用于求解任意連續(xù)函數(shù)的最優(yōu)

50、化問題。結(jié)論六，由圖 4.1 及其放大圖(圖 4.2)可以了解到，高斯牛頓發(fā)和牛頓迭代法精度相當，最速下降法定位精度較低。此種情況下，定位精度的順序大致為：高斯牛頓法=牛頓迭代法 最速下降法。結(jié)論：每種方法各有各的優(yōu)缺點。梯度下降法和高斯牛頓法都是最優(yōu)化方法。但是梯度下降法的缺點之處在于：在遠離極小值的地方下降很快，而在靠近極小值的地方下降會越來越慢。高斯牛頓法的缺點在于：若初始點距離極小值點過遠，迭代步長過大會導致迭代下一代的函數(shù)值不一定小于上一代的函數(shù)值。所以為了更好的減小 NLOS 噪聲和提高效率，減少復雜程度。可以采用最速下降法和高斯牛頓法的混合算法。要在高斯牛頓法中加入因子 ，當 大

51、時相當于梯度下降法， 小時相當于高斯牛頓法。這樣可以克服雙方的缺點，充分體現(xiàn)二者的優(yōu)點。XXXXXXX 學士學位論文185 5 TOATOA 算法展望算法展望【2】【2】 在室外NLOS環(huán)境下，若運用傳統(tǒng)方法，最重要的是知道NLOS誤差的分布。然而，要在實際情況中統(tǒng)計出分布情況是非常困難的。為了減緩這種困難，有人采用WLS (weighted least squares) 方法，只在幾個時刻處測量噪聲和NLOS誤差。另外有人采用RW (residual weighting)方法，不需要統(tǒng)計出NLOS誤差。在最近幾年，凸松弛方法【2】已經(jīng)廣泛的運用到定位系統(tǒng)中去。因而，我們可以利用凸松弛【2】的

52、算法去減少NLOS誤差。由于NLOS誤差分布很難統(tǒng)計，所以我們需要設計一種不需要預知NLOS誤差分布的算法去解決不同環(huán)境下不同誤差分布的問題。不單單要使用單一的孤立的方法，要使用多種算法的混合算法?；旌纤惴梢韵嗷パa充，克服自己的缺點，達到優(yōu)勢互補的目的。如今處理器的發(fā)展速度非?？?，處理器的性能會有很大的剩余。處理器的速度已經(jīng)遠超兆赫茲。這也為迭代法的實施提供了可能。隨著處理器的發(fā)展，處理速度已經(jīng)不成問題。雖然迭代法會隨著預測點的變化而發(fā)生迭代次數(shù)的改變。對于高速處理器來說，雖然運算次數(shù)和步驟增加，延遲的時間只會在 ns 級別。對于人的感知來說，是沒有差別的。另外，利用基站對移動臺的定位的另一

53、個影響因素是網(wǎng)速。但如今隨著 4G 時代的來臨，無線通信的傳輸速度也達到兆級別。傳輸速度對定位延時，定位精度和用戶體驗方面影響會越來越小?？傮w來說，處理器速度和網(wǎng)絡速度都不會成為定位精度的致命問題。即處理器，網(wǎng)絡速度都不會阻礙迭代法的使用和發(fā)展。我們不可能得到絕對精準的定位，無限逼近是滿足定位需求的最好方法。換句話說，迭代法是滿足定位需求的最好方法。當然，迭代法也受網(wǎng)絡速度和處理器速度的制約?？茖W技術(shù)需要同步發(fā)展。XXXXXXX 學士學位論文19參考文獻參考文獻1 程相波、馮光焰等 .NLOS 環(huán)境下幾種 TOA 定位算法的性能比較, 武警石家莊指揮學院,(4)2 Gang Wang, Mem

54、ber, IEEE, H. NLOS Error Mitigation for TOA-BasedLocalization via Convex Relaxation20143 CHAN Yiu-tong，TSUI WingyueTime-of-arrival Based localization Under NLOS ConditionsJIEEE TransVehicular Technology，2006，55(1)：17244 徐彤陽.NLOS 誤差模型下的無線傳感網(wǎng)定位方法與仿真. 山西財經(jīng)大學.20135 常戎、呂善偉等.提高 NLOS 環(huán)境下定位精度的 TOA 數(shù)據(jù)處理方法，北京

55、航空航天大學學報.2006， （32）6 Thomas N J，Cruickshank D G M，Laurenson D IA robust location estimator architecture with biased Kalman filtering of TOA data for wireless systems.IEEE Press，2000：2963007 Jazzar S A1，Caffery J JrMLBayesian TOA location estimators for NLOS environments. IEEE Press，2002：1178 11818 E

56、rtel R B，Reed J HAngle and time of arrival statistics for circular and elliptical scattering modelsIEEE Journal on Selected Areas in XXXXXXX 學士學位論文20Communications, 1999,182918409 He Yan，Hu Hanying，Zhou ShanA TOA based believable factor mobile location algorithm .IEEE Press，2004：260 26310 Liu Ying，W

57、ang ShuxunTOA estimation method using fourthorder cumulants. Publishing House of Electronics Industry，2000：210 21411 Winter J，Wengerter CHigh resolution estimation of the time of arrival for GSM location IEEE Press，2000：1343134712 孫國林.TOA/TDOA 蜂窩網(wǎng)絡定位算法研究.電子科技大學，200313 張凡、陳典鋮等.淺析室內(nèi)定位原理及應用.中國電信股份有限公司廣

58、州研究院.201314 陳鑫.化工工藝數(shù)據(jù)挖掘中數(shù)據(jù)預處理技術(shù)的研究與應用.上海交通大學.2010 15 FCC,Revision of the commissions rules to insure compatibility with enhanced 911 emergency caling systemsTechnical Report RM 199616 甄杰、馬曉紅等. 非視線傳播環(huán)境下基于 TOA 的綜合無線定位算法. 大連理工大學學報。2005.致致 謝謝 大學四年來，我取得的每一點成績都離不開身邊許多人的關(guān)心與幫助，在此論文完成之際，謹向他們表示誠摯的感謝！本文的設計及寫作過

59、程是在蘭鵬老師的指導和監(jiān)督下完成的，再次要特別感謝蘭鵬老師四年來對我的幫助與教導。大學四年，我從一個初出茅廬的毛頭小子成長為山東農(nóng)業(yè)大學的畢業(yè)生。深深感謝感謝山農(nóng)大給我了這個平臺，去鍛煉，去發(fā)展。更要感謝各位老師對我的悉心培養(yǎng)。在這里，我要真心的感謝孫豐剛老師和蘭鵬老師，在學習上和生活上都給我了莫大的幫助。各位老師嚴謹?shù)闹螌W態(tài)度，嚴格的做人標準，給我們這些學生做出了積極的表率。我們都以各位老師為榜樣。俗話說：“一日為師，終身為父” ，即使我走出學校這座象牙塔，我不會忘記各位老師對我的教誨。最后，我也將深深的感謝給我的家人、朋友和工作上的領導、同事，是大家的支持給了我繼續(xù)求學奮進、勇攀高峰的動力

60、，讓我在求學的道路上勇往直前。最后，再一次向曾經(jīng)關(guān)心我、支持過我的親朋好友致以深深的謝意，感謝大家的慷慨幫助!XXXXXXX 學士學位論文21我會時刻懷揣著對學校，對各位老師感恩的心走向未來。XXXXXXX 學士學位論文22附附 錄錄通信工程 王偉 附錄一注釋:此程序主要功能是指出噪聲對定位精確度的影響 clear; theta=linspace(0,2*pi,7);theta1=linspace(0,2*pi,4);clc;d=50;D=d/sqrt(3); %邊長X=D; %中心橫坐標Y=0;x2 = d*cos(pi/6);y2 = d*sin(pi/6);x3 = d*cos(pi/6);y3