基于位置指紋室內(nèi)定位算法研究

關于論文使用授權的說明本學位論文作者及指導教師完全了關于論文使用授權的說明本學位論文作者及指導教師完全了解遼寧工程技術大學有關保留使用學位論文的規(guī)定，同意遼寧工程技術大學保留并向國家有關部門機構送交論文的復印件和磁盤，允許論文被查閱和借閱，學?？梢詫⑽徽撐牡娜炕虿糠謨?nèi)容編入有關數(shù)據(jù)庫進行檢索，可以采用影印、印或掃描等復制手段保存、匯編本學位論文。保密的學位論文在解密后應遵守此協(xié)學位論文作者簽名： 導師簽名： 年月日年月日致謝研究生生活轉(zhuǎn)瞬即逝，這兩年半中我的成長與收獲與老師們的悉心指導和同學們的真心幫助是離不開的，我心中充滿感謝之情。在讀研的期間，我的導師李新春悉心指導我如何學習和創(chuàng)新，李老師淵博的知識和開闊的科研思路使我受益匪淺，讓我在思考問題的層次有了頗大的提高，本篇論文的撰寫也是在李老師的指導下完成。在此特向李老師表達我最美好的祝愿和最真摯的感謝！我還要感謝我實驗室的同學們，也感謝同學們在學習和生活上對我的關心和幫助，致謝研究生生活轉(zhuǎn)瞬即逝，這兩年半中我的成長與收獲與老師們的悉心指導和同學們的真心幫助是離不開的，我心中充滿感謝之情。在讀研的期間，我的導師李新春悉心指導我如何學習和創(chuàng)新，李老師淵博的知識和開闊的科研思路使我受益匪淺，讓我在思考問題的層次有了頗大的提高，本篇論文的撰寫也是在李老師的指導下完成。在此特向李老師表達我最美好的祝愿和最真摯的感謝！我還要感謝我實驗室的同學們，也感謝同學們在學習和生活上對我的關心和幫助，最后，衷心感謝審閱論文和答辯組的老師們！摘要LWR-KNN摘要LWR-KNN算法，在離線階段采集的位置指紋的基礎上通過局部加權回歸得到一個模擬射KNN定位算法的定位精度；針對提高室Robust-KNN定位算法和輔助排查定位系統(tǒng)異常的丟失接入點搜索算法。實驗結果表明，LWR-KNN算法可以在參考點稀疏的情況下顯著改善定位精度，Robust-KNN可以在部分接入點丟失的情況下仍提供較可靠的關鍵詞：-IAsradiofingerprintaccuracy,ithasbecomeenhanceAsradiofingerprintaccuracy,ithasbecomeenhancetheaccuracybasedindoorpositioningapproachissimple,lowcost,highthefocusinindoorpositioningresearchfield.Inordertoindoorpositioningalgorithm,alocallyweightedbasedradiomapargumentapproachisproposed,whichiscalledLWR-KNNalgorithm.LWR-KNNmakeuseoftheradiofingerprintfromcalibrationpointscollectedinofflinephaseandthelocallyweightedregressionalgorithmtogeneratesyntheticpoints.Toimproverobustnessofindoorlocationalgorithm,anaccesspointlostpreventedpositioningalgorithmisproposed.ThedetectionofaccesspointlostisbasedontheKnearestneighborapproachaccordingtothedistortioninsignalspace.Thepossibilityofanaccesspointhasbeenlostisupdatedconstantlyandthedistancemetricismodifiedwhenaccesspointlostisdetected.ExperimentalresultsindicatethattheproposedLWR-KNNalgorithmcansignificantlyimprovetheaccuracyofKNNpositionalgorithm,especiallywhenthecalibrationpointsaresparse.TheRobust-KNNapproachcanprovidereliablelocationestimationevenapartofaccesspointshavebeenlost.Furthermore,alostaccesspointssetcanbedeterminedafterobtainedobservations,whichcanprovideabasisfortheindoorpositioningsystemtoeliminateKeyWords：indoorlost；--目錄摘 TODO: 1緒 基于研究背景及意 室內(nèi)定位目錄摘 TODO: 1緒 基于研究背景及意 室內(nèi)定位的國內(nèi)外研究現(xiàn) 主要研究工 論文結 Wi-Fi的室內(nèi)定位技 2基于Wi-Fi的定位算法分 幾何定位 最大似然估計定位 近似定位 位置指紋定位 基于位置指紋的定位技 基本原 位置指紋數(shù)據(jù)庫預處 位置指紋定位算 室內(nèi)定位技術評價指 本章小 3高精度的Wi-Fi室內(nèi)定位算法研 算法研究基 基于局部加權回歸的射頻指紋地圖校 局部加權線性回歸(LocallyWightedRegression, 留一交叉驗證法(Leave-One-Out-Cross- LWR射頻指紋地圖校 實驗及結果分 實驗環(huán) -III參考點密集情況下的LWR射頻地圖校 參考點密集情況下的LWR射頻地圖校 參考點稀疏情況下的LWR射頻地圖校 3.4本章小 高魯棒性的Wi-Fi室內(nèi)定位算法研 4異常條 傳統(tǒng)算法定位精度變 算法描 接入點篩 異常檢 信號空間距離修 丟失AP搜索算 算法工作流 算法結果及分 非異常條件下算法結 異常條件下算法結 本章小 5參總結與展 考文 者簡 作學位論文原創(chuàng)性聲 學位論文數(shù)據(jù) -IV1緒研究背景及意義基于位置的服務1緒研究背景及意義基于位置的服務(LocationBasedService,LBS)是指由衛(wèi)星定位系統(tǒng)、移動通信網(wǎng)絡、無線局域網(wǎng)(WirelessLocalAreaNetworks,WLAN)等通過一組定位技術獲得待定位節(jié)點的絕對位置(如經(jīng)緯度坐標數(shù)據(jù))或相對位置(如相對某參考位置的數(shù)據(jù))提供給待定位終端本身、通信系統(tǒng)等以實現(xiàn)各種與位置相關業(yè)務的服務[1-3]。廣域定位技術主要包含全球定位系統(tǒng)和蜂窩無線定位系統(tǒng)。20世紀70年代美國軍方為實現(xiàn)陸?？杖箢I域提供全天候、實時的、全球的定位導航服務，研制了全球定位系統(tǒng)(GlobalPositioningSystem,GPS)，并在海灣戰(zhàn)爭中用于實戰(zhàn)，開啟了精準打擊時代[4]。后因GPS的巨大實用價值，美國總統(tǒng)克林頓頒布法令，將GPS免費向民用領域開放。隨之而來的是基于GPS的車輛定位系統(tǒng)、導航系統(tǒng)等服務的廣泛應用。其他國家也陸續(xù)研究開發(fā)了自己的全球定位系統(tǒng)，其中包含俄羅斯的GLONASS定位系統(tǒng)、歐盟的Galileo定位系統(tǒng)以及我國的北斗衛(wèi)星定位系統(tǒng)[5]。但是在室內(nèi)環(huán)境下，GPS衛(wèi)星發(fā)射的電磁信號強度太小、建筑物遮擋衛(wèi)星信號傳播等因素使得在室內(nèi)環(huán)境中GPS無法給出令人滿意的定位精度[6]。另一種廣泛應用的廣域定位系統(tǒng)是基于移動蜂窩網(wǎng)絡的基站定位系統(tǒng)，即蜂窩無線定位，其定位精度依賴于基站信號覆蓋范圍的大小和基站位置的分布，在室內(nèi)環(huán)境下，蜂窩無線定位系統(tǒng)也無法滿足定位精度的要求[7]。基于傳感器設備的定位技術通過將傳感器設備事先部署到待定位區(qū)域中，通過對進入到待定位區(qū)域的待定位節(jié)點進行探測來實現(xiàn)位置的估測，主要包括基于射頻標簽的定位、基于紅外線的定位、基于藍牙的定位、基于地磁感應的定位等[8-17]。利用傳感器設備的定位技術需要專門的感知設備支持，且受室內(nèi)環(huán)境的影響程度頗高。為了滿足一定的定位精度，需要大范圍的傳感器設備部署，實現(xiàn)成本和部署難度較高。因此，該種定位技術適用于范圍較小、對成本控制要求不高的簡單室內(nèi)環(huán)20世紀末開始，WLAN技術作為一種高速無線通信技術發(fā)展起來，其結合了現(xiàn)代社會對辦公、移動娛樂的需求，且具有部署方便、通信快速等優(yōu)點。機場、會展中心、寫字樓、各類型酒店等人們活動的主要室內(nèi)環(huán)境都是Wi-Fi接入點的重點部署場合。Wi-Fi網(wǎng)絡承載了人們的快速Internet接入，并非為定位而生，但是卻在室內(nèi)無線定位中扮演著十分重要的角色。基于Wi-Fi的室內(nèi)定位技術復用已經(jīng)廣泛部-5署的Wi-Fi接入點和正在普及的智能移動終端設備，相較于廣域定位技術和基于傳感器的室內(nèi)定位技術，具有頗高的實用價值。諸多署的Wi-Fi接入點和正在普及的智能移動終端設備，相較于廣域定位技術和基于傳感器的室內(nèi)定位技術，具有頗高的實用價值。諸多知名企業(yè)Google、Apple和Microsoft等，都投入大量資源來研究基于Wi-Fi的室內(nèi)定位技術。現(xiàn)有的Wi-Fi定位技術主要有基于信號到達時間的定位(TOA)、基于信號達到角度的定位(AOA)、基于信號到達時間差的定位(TDOA)以及基于信號強度的定位(RSSI)[18-21]。TOA、AOA、TDOA需要不同程度上改變硬件設備來進行時間同步或角度測量，而基于RSSI的定位只需要利用現(xiàn)有的無線網(wǎng)絡資源并配合定位軟件就可以實現(xiàn)位置估測，降低了成本，得到廣泛定位技術研究者的熱愛。基于RSSI的定位又分為信號傳播模型損耗法和位置指紋定位法，其中傳播模型損耗法難以精確定義信號傳播模型，并受多徑效應影響嚴重，這使得其定位精度受到限制；基于位置指紋的定位法則依靠識別目標位置信號特征來進行位置估測，可以較好地適應復雜的室內(nèi)環(huán)境且不受信號傳播模型準確程度的限制[22-24]。本文就是在這樣的背景下對基于位置指紋的室內(nèi)定位算法進行研究，試圖從定位精度和定位系統(tǒng)的魯棒性兩個不同的角度對室內(nèi)定位技術進行改進。定位精度的提高可以提供更精準的基于位置的服務，而定位系統(tǒng)的魯棒性的改善可以在定位系統(tǒng)基礎設施發(fā)生部分損壞時仍提供可靠的位置服務，這在惡劣的環(huán)境中，如火災現(xiàn)場等，具有非常高的實際意義。室內(nèi)定位的國內(nèi)外研究現(xiàn)室內(nèi)定位技術相較于室外定位技術起步較晚，卻發(fā)展迅速。人們對室內(nèi)環(huán)境下定位、導航的需求越來越大，促使國內(nèi)外學者、研究機構對室內(nèi)定位展開了廣泛的一種室內(nèi)定位方法是將室外定位技術引入到室內(nèi)環(huán)境，但如上一節(jié)所述的那樣，在室內(nèi)環(huán)境下傳統(tǒng)的室外定位技術無法滿足對定位精度的要求。人們開始專注于其他的定位技術，給出了許多適合特定場景下的定位技術解決方案。如在工廠、倉庫和商場中用于物品管理的射頻標簽定位技術，室內(nèi)視距條件下定位精度很高的超聲波定位技術，適用于人體定位的紅外定位技術，適用于短距離定位的藍牙定位技術，覆蓋范圍廣的WLAN定位技術，適用于無線傳感器網(wǎng)絡(WirelessSensorNetwork,WSN)的ZigBee定位技術。此外，還有利用視頻、圖像、地磁、壓力傳感器等的定位技術。下面簡要介紹幾個比較有代表性的室內(nèi)定位技術[25-32]。(1)基于紅外線技術的室內(nèi)定位-6基于紅外線的室內(nèi)定位技術的原理是，部署在室內(nèi)的紅外線接收器接收待定位節(jié)點攜帶的紅外線標識每隔一段時間發(fā)出的紅外線信號并對待定位節(jié)點的位置進行估計，代表的定位系統(tǒng)如AT&TCambridge基于紅外線的室內(nèi)定位技術的原理是，部署在室內(nèi)的紅外線接收器接收待定位節(jié)點攜帶的紅外線標識每隔一段時間發(fā)出的紅外線信號并對待定位節(jié)點的位置進行估計，代表的定位系統(tǒng)如AT&TCambridge設計的ActiveBadge系統(tǒng)[33]。ActiveBadge系統(tǒng)的用戶攜帶的紅外線發(fā)射終端設備每隔15秒向外發(fā)出一個全局標識號，當固定在室內(nèi)的紅外線接收設備收集到此類信號時，即可估計出攜帶著發(fā)射終端設備的用戶所在的房間，因此該系統(tǒng)的定位精度只能達到房間級別?；诩t外線的室內(nèi)定位技術受視線約束，傳播距離較短，易受環(huán)境干擾且需要部署專用于定位的信號發(fā)射設備和信號接收設備，系統(tǒng)的可擴展性較差，總體定位性能較差，應用范圍(2)基于超聲波技術的室內(nèi)定位基于超聲波的室內(nèi)定位技術的原理是，通過測量超聲波來估算信號的傳播距離，進而通過三角定位等方法估計待定位節(jié)點所在的位置，代表的系統(tǒng)如ActiveBat系統(tǒng)、Cricket系統(tǒng)[34-35]。ActiveBat系統(tǒng)致力于結合無線電與超聲波技術的研究，通過測量超聲波的傳播時延來確定傳播距離，需要事先在天花板上設定好信號接收器的位置，然后按照設定好的位置安裝信號接收器，待定位節(jié)點則必須配置相應的ActiveBat標簽。ActiveBat具有非常高的定位精度，定位誤差在9cm以內(nèi)的概率高達95%。Cricket實際上是ActiveBat系統(tǒng)的一種改進，屬于分布式的定位系統(tǒng)。Cricketv2版能夠為移動用戶端提供包括位置標識符、空間坐標和方向的多層次位置信息。在隱私保護方面，Cricket使用移動接收端來承擔計算任務，可以更好的保護用戶隱私。然而，基于超聲波的室內(nèi)定位技術受限于硬件設施和接收器的擺放位置，雖然有較高的定位準確率，但難以部署、不易于擴展、成本高，適用于對定位精度要求很高，但定位范圍較小的特定環(huán)境，如倉儲管理中對貴重物品的精確定基于射頻標簽技術的室內(nèi)定位基于射頻標簽的室內(nèi)定位技術的原理是，射頻標簽與讀寫器以非接觸的方式進行數(shù)據(jù)傳輸，讀寫器通過射頻標簽的位置電子編碼來確定攜帶著該標簽的待定位節(jié)點的位置，代表的系統(tǒng)如ZebraTechnologyCompany設計的WhereNet定位系統(tǒng)[9]。WhereNet系統(tǒng)旨在提供室內(nèi)和室外的實時定位，使用RFID來標識待定位節(jié)點并利用信號到達時間差(DifferentialTimeofArrival,TDOA算法來計算各個標簽的相對位置和絕對位置。基于射頻標簽的室內(nèi)定位技術依賴于專用的基礎設施，系統(tǒng)可擴展性較差?；诔瑢拵Ъ夹g的室內(nèi)定位-7超寬帶技術是基于極窄脈沖的無線電技術，具有GHz量級的帶寬，不受視距傳播約束，代表的系統(tǒng)如由AT&TCambridge超寬帶技術是基于極窄脈沖的無線電技術，具有GHz量級的帶寬，不受視距傳播約束，代表的系統(tǒng)如由AT&TCambridge的工程師建立的UbisenseCompany設計的Ubisense系統(tǒng)[36]Ubisense系統(tǒng)使用信號到達時間差和信號到達角來計算待定位節(jié)點位置，可以在三維空間中提供15cm左右的定位精度?；趫D像處理技術的室內(nèi)定位基于圖像處理的室內(nèi)定位技術可用于在復雜室內(nèi)環(huán)境下識別和定位待定位節(jié)點，不需要待定位節(jié)點攜帶任何特定設備，且能提供更豐富的基于位置的信息，如“張三正在坐在沙發(fā)上喝水”。代表的系統(tǒng)如MicrosoftResearchGroup設計的EasyLiving系統(tǒng)[37]。Wi-Fi技術的室內(nèi)定位基于Wi-Fi的室內(nèi)定位的基本原理是，Wi-Fi接入點(AccessPoint,AP)向周圍周期性地發(fā)射無線信號，標識自己并廣播自身的無線網(wǎng)絡信息，包括無線信號強度、服務集標識碼(ServiceSetIdentifier,SSID)等信息。待定位節(jié)點通過掃描周圍的Wi-Fi信號，獲得周圍AP的無線信號信息，然后根據(jù)定位算法利用這些信息估算處相對位置信息，代表的定位系統(tǒng)如MicrosoftResearchGroup設計的RADAR定位系統(tǒng)。RADAR系統(tǒng)利用已有的Wi-Fi基礎設施，先構建一張射頻指紋地圖(RadioMap)，當待定位節(jié)點采集到一個實時Wi-Fi信號向量后，使用信號空間最近鄰法(NearestNeighborinSignalSpace,NNSS)在射頻指紋地圖中找出與該Wi-Fi信號向量的歐氏距離最小的參考點作為待定位節(jié)點的位置估計。RADAR系統(tǒng)在二維空間上定位精度達到4m的概率約50%[38]。RADAR系統(tǒng)開啟了基于位置指紋室內(nèi)定位的先河，國內(nèi)外諸多學者對這種定位算法進行廣泛而深入的研究。主要研究工先介紹了室內(nèi)定位技術的發(fā)展現(xiàn)狀，對不同定位技術進行了分類并介紹各自的基本原理以及特點。選擇了部署成本低、定位精度較高、復雜度較低的KNN位置指紋定位算法作為本文的研究基礎。針對如何提高基于位置指紋的KNN算法的定位精度，提出基于局部加權回歸射頻指紋地圖校正的LWR-KNN算法。在待定位區(qū)域采集的少量的參考點位置指紋后通過一種搜索算法得出局部加權回歸模型中的參數(shù)，然后通過局部加權回歸對射頻指紋地圖進行校正，以期提高KNN算法的定位精度。針對如何提高基于位置指紋的KNN測以及信號空間距離修正的Robust-KNN-8生故障或被惡意損壞的情況下仍提供較可靠的位置估計。同時提出一種丟失接入點搜索的SLAP算法，在定位系統(tǒng)中部分接入點丟失的情況下，通過SLAP生故障或被惡意損壞的情況下仍提供較可靠的位置估計。同時提出一種丟失接入點搜索的SLAP算法，在定位系統(tǒng)中部分接入點丟失的情況下，通過SLAP算法對丟失接入點進行搜索，以期提供一個丟失接入點集合來輔助定位系統(tǒng)排查異常。在實際的室內(nèi)環(huán)境下采集位置指紋，并在MATLAB中對采集的數(shù)據(jù)進行處理，LWR-KNN算法、Robust-KNN算法以及SLAP算法進行實驗，以期通過實驗結果來論證算法的可靠性。論文結第一章：緒論。先對本文的研究背景及意義進行了簡短說明；緊接著又介紹了本課題國內(nèi)外的研究現(xiàn)狀；最后簡單地介紹了本文的主要工作、文章結構安排以及創(chuàng)新點。第二Wi-Fi室內(nèi)定位概述基Wi-Fi的室內(nèi)定位技術進行分類述各類定位方法的基本原理、技術特點以及適用范圍，指出基于位置指紋的定位技術具有很大的研究和實用價值，并以該技術作為本文的主要研究對象；然后對基于位置指紋的定位技術的基本原理進行詳細分析；最后給出定位技術的評價指標，從中選取定位性能和定位系統(tǒng)魯棒性作為研究方向。Wi-FiWi-Fi室內(nèi)定位系統(tǒng)的精度進行Wi-Fi室內(nèi)定位研究，針對如何提高Wi-Fi室內(nèi)定位系統(tǒng)的魯棒性第五章：全文總結與展望-92Wi-Fi的室內(nèi)定位技基于Wi-Fi的室內(nèi)定位技術以其經(jīng)濟性好、易于部署、使用方便等優(yōu)點，成為目前室內(nèi)定位技術研究的熱點。本章介紹目前該技術的主要原理，為進一步的研究提2Wi-Fi的室內(nèi)定位技基于Wi-Fi的室內(nèi)定位技術以其經(jīng)濟性好、易于部署、使用方便等優(yōu)點，成為目前室內(nèi)定位技術研究的熱點。本章介紹目前該技術的主要原理，為進一步的研究提供理論基礎。本章對基于Wi-Fi的室內(nèi)定位技術進行分類，闡述各類定位方法的基本原理、技術特點以及適用范圍，指出基于位置指紋的定位技術具有很大的研究和實用價值，并以該技術作為本文的主要研究對象；然后對基于位置指紋的定位技術的基本原理進行詳細分析；最后給出定位技術的評價指標，從中選取定位性能和定位系統(tǒng)魯棒性作為研究方向?；赪i-Fi的定位算法分類Wi-Fi幾何定位幾何定位利用待定位節(jié)點與AP之間的距離或AP信號到達待定位節(jié)點的角度，根據(jù)幾何學的原理估算移動終端的位置，包括三邊測量法、三角測量法和混合定位法三類。(1)三邊測量法2-三邊測量法原理圖Figure2-1Diagramofthe-102-1Axaya、B(xb,yb、C(xc,yc，其中(xi,yi為參點的坐標，測得待定位D到2-1Axaya、B(xb,yb、C(xc,yc，其中(xi,yi為參點的坐標，測得待定位D到參考AB、C的距離分別為da、db、dc，設待定位節(jié)點D的坐標為(x,y)。在理想情況下，當測得待定位節(jié)點到一個參考點的距離d時，可認為待定位節(jié)點在以該參考點為圓心半徑為d的圓上，則待定位節(jié)點與三個參考節(jié)點的距離后可以由三個相交xxy 2aaaxxy 2bbbxxy 2ccc由式(2-1)D2xx 2yy xxyyd x ac a 2xbxc yyxxyyd b 由式(2-2)可見，在xiyi已知的情況下，測量得到da、 APAP信號的度量指標進行轉(zhuǎn)換得到的。常用的度量指標包括時間(TOA,TDOA)和接收信號強度RSSI傳播速度即可估算出待定位節(jié)AP之間的距離，進而根據(jù)式(2-2)估算目標位置坐標；RSSI測量的三邊定位則利用測得的接受信號強度，根據(jù)信號傳播模型推算出待定位節(jié)點AP的距離，進而根據(jù)式(2-2)估算目標位置坐標，其關鍵在于如何得到一個普適性可得到如式(2-4)所表示的對數(shù)-常態(tài)分布模型[39]dP(d)P(d 10 0 d0-11P(d P(d 10nlgdP(d P(d 10nlgdd 000，均方差為的高斯隨機變量，其取值范圍為410其中，X為均值為路徑損耗系數(shù)，根據(jù)不同環(huán)境其取值n5。Pr(d)Pr(d0分別表示距離和(d0一般作為參考距離1米處的信號強度值是與硬件相關的，可以根據(jù)實際測量來獲得，然后根據(jù)式(2-4)可以計(2)三角測量ngleofrivl,)來定位，其中參考點預先設定，使用特定方法測量待定位節(jié)點到參考點的角度進而通過角度關系估算出待定位節(jié)點的位置坐標。2-2A、B的坐標xa,ya，xbybD的坐標為xy2-2三角測量法原理圖Figure2-2DiagramoftheDA的角度為DB的角度為yaytan(xa式(2-ytan(xb由式(2-5)D-12y1y2tanx1tantany1y2tanx1tantantanx式(2-y1212tantanAOA的定位方法早已經(jīng)應用在飛機導航等室外定位服務中，但是在室內(nèi)定位方AOAAOAVOR室內(nèi)定位系統(tǒng)基于地面?zhèn)鬏斝盘柕腁OA的測距方法能夠重復廣播兩種信號脈沖，且不依賴于信號采樣的密度AOA值便可以進一步進行位置估計[41]。此外基于AOA的定位算法可以利用陣列天線，在同一個方向上測量陣列天線的RSSI并記錄其角度，利用這RSSI以及角度的分布信息，進一步定位出待定位節(jié)點的位置。這種方法不僅提高了定位的準確度，同時可以減少定位時需要的AP數(shù)目。(3)混合定位方VenkatramanTOAAOA結合的定位方法，研究室內(nèi)環(huán)境下非視距條件下的定位結合TOA和AOA的信息，實現(xiàn)對待定位節(jié)點的位置估計[44]。樊玉鳳等則提出了一種將RSSI和波束切換智能天線相結合的聯(lián)合定位算法[45]。 最大似然估計定位法kAPk3AP坐標為(xiyii1,2,3。設待定位節(jié)點D的坐標為(xy。通過任意一種測距方法測量得到D到各個APdi,i1,23,...k-132-3最大似然估計法原理圖Figure2-3Diagramofthemaximumlikelihoodxxyy222111xxyy2222222-3最大似然估計法原理圖Figure2-3Diagramofthemaximumlikelihoodxxyy222111xxyy222222xxyy222kkkx2y1yky2x2x2y2y2d2d xx2x2y2y2d2d,x,bA xyx y2y2d2 2yk k kk k k k在實際測量中存在測量誤差ex2b對測量誤差exxdex2AATx2Ab1-14近似定位近似法也叫最近AP法，類似于移動蜂窩網(wǎng)絡定位中的Cell-ID近似定位近似法也叫最近AP法，類似于移動蜂窩網(wǎng)絡定位中的Cell-ID定位法，根據(jù)待定位節(jié)點與一個或多個位置已知的物體的臨近關系來進行位置估計。如圖2-4Z1、Z2、Z3均為已知位置的區(qū)域，當待定位節(jié)點DZ1，就可以用Z1的位置來近似D的位置。在WLAN環(huán)境下，接入點是鏈接用戶從無線通訊到有限通訊的橋梁，各接入點都有一定的信號覆蓋范圍，進入這一信號區(qū)域的待定位節(jié)點都可以通過與它連接實現(xiàn)網(wǎng)絡。近似法的實現(xiàn)是通過接入點的位置來大致估計待定位節(jié)點的位置的，所以無需額外的硬件設備，實現(xiàn)簡單，但在定位性能很大程度依賴于接入點的連接性能、覆蓋范圍、接入點位置信息的準確性?，F(xiàn)有的民用的地圖導航類應用，如高德地圖，在已經(jīng)收集到豐富的接入點數(shù)據(jù)庫的基礎上就會使用這種定位技術來對用戶進行位置估計。但是這種定位技術的定位精度較低，通常只能適用于對精確度要求不高的場合或作為其他定位技術的輔助技術進行粗定位。2-4近似法原理圖Figure2-4Diagramofthe位置指紋定位基于位置指紋的定位算法一般分為離線階段(或稱數(shù)據(jù)采集階段)和在線定位階段(或稱實時定位階段)，離線階段定位系統(tǒng)將待定位區(qū)域的某些位置點作為參考點，采集各AP的接受信號強度(RSSI)-15紋都唯一對應一個位置坐標；在線定位階段將待定位節(jié)點獲得的指紋與離線階段建立的指紋庫中的指紋進行匹配，從而估計出待定位節(jié)點的位置坐標。位置指紋定位法可以利用已經(jīng)廣泛部署的Wi-Fi用硬件，不依賴于易受室內(nèi)復雜環(huán)境影響的信號傳播損耗模型，經(jīng)濟成本低，可以使用純軟件的方式實現(xiàn)，定位方法簡單，能夠很好的推廣。 基于位置指紋的定位技術基本原理如圖2-5紋都唯一對應一個位置坐標；在線定位階段將待定位節(jié)點獲得的指紋與離線階段建立的指紋庫中的指紋進行匹配，從而估計出待定位節(jié)點的位置坐標。位置指紋定位法可以利用已經(jīng)廣泛部署的Wi-Fi用硬件，不依賴于易受室內(nèi)復雜環(huán)境影響的信號傳播損耗模型，經(jīng)濟成本低，可以使用純軟件的方式實現(xiàn)，定位方法簡單，能夠很好的推廣。 基于位置指紋的定位技術基本原理如圖2-5lLixiyi,i1,...,lxiyi表示第i個參考點的二維物理空間坐標。n為待定區(qū)域AP總數(shù)，APj在i處測量對各APRSS得到一個參考數(shù)據(jù)AP的信號強度特征，對于掃描不到其烽火信號（不可見AP用一個低于網(wǎng)卡可識別的常量Const（本文使Const-99dBm）填充以保持對齊。然后將iri成一條記錄i,ri存入指紋庫。為了減少噪聲和奇異值的影響，ri通常取在處多次測量的平均。在整個L上重復上述步驟以完成射頻指紋庫的構建。oo1o2on在在線定位階段，在未知位置處獲得一個RSSIo與ri的相似度來獲得位置估 。實質(zhì)上，這是將定位看作基于信號強度特征的模識別[46]圖2-5基于位置指紋的定位原理-16Figure2-5Diagramofthelocationfingerprintbased指紋數(shù)據(jù)庫預處理AP信號的強度特征信息以及對應的參考點的位置信息。而關于信號強度特征信息，信噪比(signaltonoiseratio,SNR)曾被UCLARobinNibble定位系統(tǒng)中[47]BahlRSSI比SNR具有更強的位置相關性。本文采用RSSI作為信號強度特征信息。(1)紋。于是位置指紋庫中第i條指紋數(shù)據(jù)的記錄可以表示為：lixi,yiFigure2-5Diagramofthelocationfingerprintbased指紋數(shù)據(jù)庫預處理AP信號的強度特征信息以及對應的參考點的位置信息。而關于信號強度特征信息，信噪比(signaltonoiseratio,SNR)曾被UCLARobinNibble定位系統(tǒng)中[47]BahlRSSI比SNR具有更強的位置相關性。本文采用RSSI作為信號強度特征信息。(1)紋。于是位置指紋庫中第i條指紋數(shù)據(jù)的記錄可以表示為：lixi,yi其中rji2.12rtj Sample其中Sampleji表示在第i個采樣點處接受到的第j個AP的采樣數(shù)量 表示第i個rAPRSSI3.RSSI，rji表示在第ij直方圖處理也是指紋數(shù)據(jù)庫預處理的常見方法之一，在指紋數(shù)據(jù)庫中可以將第ilixi,yiH1i,H2i,H3i,...,Hniri b, |tB,B / t1i i-17htrmax、r第tjAPjAPRSSI位置指紋定位算法基于位置指紋的Wi-Fi定位算法分為確定型定位算法和概率型定位算法兩大類。確定型的位置指紋定位算法通常利用RSSI采樣數(shù)據(jù)建立指紋庫，主要包含k最近鄰法、人工神經(jīng)網(wǎng)絡法和支持向量機法；概率型的位置指紋定位算法通常通過概率論方法建立指紋映射，并通過概率數(shù)據(jù)分析進行位置估計，主要為貝葉斯決策法。K最近鄰法K最近鄰法(KNearestNeighbors,KNN)算法是機器學習中比較成熟的方法，在模式識別領域中是一種無參數(shù)的分類回歸方法，基于特征空間中的K個最相近鄰的訓練樣本來預測對象值或劃分類成員關系。算法的主要思想是一個對象通過它鄰居的多數(shù)表決來確定分類結果，即該對象會被劃分到與它最相鄰的K個鄰居所屬的類中，當K=1時，即退化為最近鄰法(NearestNeighbor,NN)，選擇最接近的鄰居對象所屬類作為分類結果。人工神經(jīng)網(wǎng)絡法人工神經(jīng)網(wǎng)絡是一種類似于生物體神經(jīng)網(wǎng)絡的構造的計算模型，在機器學習和模式匹配領域廣泛應用[48]。人工神經(jīng)網(wǎng)絡的學習過程就是通過訓練樣本對網(wǎng)絡中每一層的權重進行校正而建立模型的過程，使得所得到的模型最終能夠?qū)o定的輸入獲得預測的結果，其中BP(ErrorBackPropagation)算法是目前最常用的學習算法之一，BP神經(jīng)網(wǎng)絡的典型三層結構模型如圖2-6所示。BP算法主要分為數(shù)據(jù)的正向擴散階段和差值的逆向傳播階段。在數(shù)據(jù)正向擴散階段中，對于輸入層傳入的學習數(shù)據(jù)經(jīng)隱藏層處理后，將由輸出層得到的預測結果與真實結果比較，得到訓練差值，如果訓練差值超過限定值，則進入到差值反向傳播過程。誤差的反向傳播是將訓練差值通過隱藏層向輸入層以某種形式逆向傳播，并將誤差分別分給每一層的網(wǎng)絡單元，這樣就得到每個單元的差值數(shù)據(jù)，該差值數(shù)據(jù)用來不斷完善各個單元的權重。這種數(shù)據(jù)正向擴展、誤差逆向傳播的每一層的權重修改一直循環(huán)進行，直到誤差小于某一個閾值或達到預先設定的學習次數(shù)上限。人工神經(jīng)網(wǎng)絡法將室內(nèi)定位問題看成一個利用位置指紋模型對實時RSSI向量的分類問題，通過對離線階段采樣指紋和位置關系模型的訓練學習來建立指紋庫。人工神經(jīng)網(wǎng)絡法相比于KNN算法的定位精度略高，-18但算法的缺點是對匹配模型的訓練學習時間較長，而且需要大量的樣本數(shù)據(jù)，計算復雜度也較高。2-6BP神經(jīng)網(wǎng)絡三層結構模型Figure2-6Threelayer但算法的缺點是對匹配模型的訓練學習時間較長，而且需要大量的樣本數(shù)據(jù)，計算復雜度也較高。2-6BP神經(jīng)網(wǎng)絡三層結構模型Figure2-6ThreelayerBPneuralnetwork支持向量機法支持向量基(SupportVectorMachine,SVM)是一種基于統(tǒng)計學的機器學習方基于VC維理論來獲得學習機最好的泛化能力，使得在有限的統(tǒng)計樣本量中能得到較準確的統(tǒng)計規(guī)律?；赟VM的室內(nèi)定位算法在離線采樣階段將地圖劃分成網(wǎng)格區(qū)域，將每個網(wǎng)格作為SVM的一類。通過每個網(wǎng)格采集的各APRSSI來構建基于網(wǎng)格的位置指紋庫，并作為SVM的訓練樣本，建立SVM分類模型[49]。在在線定位階段，待定位節(jié)點將接收到的RSSI向量作為輸入，利用SVM在離線階段得到的分類模型得到分類結果從而得到位置估計?；赟VM的定位算法的優(yōu)勢在于能夠在訓練樣本有限的情況下，建立RSS指紋到位置信息的非線性映射關系，且SVM將定位問題看做分類問題，非常適合房間級別的室內(nèi)定位場景[50]。但是SVM理論本身較復雜，實現(xiàn)難度較大。貝葉斯決策法貝葉斯決策法與基于SVM的定位算法類似，將指紋庫按照每個采樣點劃分成若干類，但與其不同的是，貝葉斯決策法用概率性的算法來判斷待定位節(jié)點實時接收到的RSSI向量所屬的類，從而估算待定位節(jié)點的位置坐標。貝葉斯決策法基于貝葉斯定理：PAPPAB式(2-PB-19在基于位置指紋的定位算法中，貝葉斯決策法首先確定在待定位區(qū)域中 Ll1l2l3llRr1r2r3rl，每組樣本lRSS向量樣nAPRSS樣本的均值，可以表示為rr1r2r3rn在基于位置指紋的定位算法中，貝葉斯決策法首先確定在待定位區(qū)域中 Ll1l2l3llRr1r2r3rl，每組樣本lRSS向量樣nAPRSS樣本的均值，可以表示為rr1r2r3rn；在線階段定位時，待定位節(jié)點收到來自nAP值作為一個觀測值葉斯決策法可以計算出觀測值o在指紋庫中每個采樣點出現(xiàn)的概率，即P根據(jù)貝葉斯定理可以推導出：oPoliPliPoPoliPliPo式(2-PoliPlili為在采樣點li處采集到的RSS向量為o的概率，Pli為位置liPAPRSSPoliPo1liPliPli最后將后驗概率最大的采樣點作為位置估計的結果，即位置估計可表示為o在實際復雜場景下，P的計算可能需要通過大量的訓練樣本來得到較為準確Pli[51]1Plexpj1i應用場景定義模型參其中核方法需要確定，而直方圖法中需要確定劃分區(qū)間的大小室內(nèi)定位技術評價指(1)安全性和隱私-20成GPS24Wi-Fi的室內(nèi)定位系統(tǒng)來說，由于可以復用已WLAN基礎設施，基礎設施成本低。用戶端成本通常指的是定位系統(tǒng)提供定位服務Wi-Fi的定位系統(tǒng)不需要額外部署傳感器，使得部署和維護成本較延指的是從采集位置特征到估算出待定位節(jié)點位置再到將位置估計結果返回給用戶所需的總時間。定位時延之所以作為評價定位性能的一個重要指標是因為：如果待定位節(jié)點在常定義為一個定位系統(tǒng)在給定的定位基礎設施下能同時為其提供定位服務的待定位節(jié)點的數(shù)量。魯棒高魯棒性的定位系統(tǒng)指的是在定位系統(tǒng)的部分基礎設施發(fā)生故障或者待定位區(qū)域環(huán)境發(fā)生變化時，仍能夠進行可靠的位置估計的能力。基于紅外線的定位技術依賴于待定位tiveadge-21復雜復雜Wi-Fi的定位系統(tǒng)可以利用已經(jīng)廣泛覆蓋的用于通WLAN環(huán)境，可以通過少量的人工校正，如基于位置指紋的定位技術的離線采樣，定位技術的用戶友好性以及是否已經(jīng)存在商業(yè)化的產(chǎn)品等方面都是評價其優(yōu)劣的指標。如一個定位技術已經(jīng)有較為成熟的商業(yè)化產(chǎn)品，則研究人員可以購買其定位系統(tǒng)并部署，進一步地研究其原理和存在的不足，以改進此定位技術。本章小本章對基于Wi-Fi的室內(nèi)定位技術進行分類，闡述各類定位方法的基本原理、技術特點以及適用范圍?；谖恢弥讣y的定位技術由于其部署容易、定位性能高等特點具有很大的研究和實用價值，本文將這種定位技術作為研究對象。對基于位置指紋的不同定位算法做了簡要介紹，并選取計算復雜度低的KNN算法作為本文的算法研究基礎。定位技術的評價指標包含安全性、成本、性能、魯棒性、復雜度等，各個指標之間存在相互聯(lián)系、相關制約的關系。定位性能和定位系統(tǒng)魯棒性作為最優(yōu)考慮的兩個指標，將成為本文的研究方向。-223高精度的Wi-Fi室內(nèi)定位算法研究算法研究基如式(3-1)，KNN算法通常使用信號空間歐式距離來計算相似度，Di越小相似度越高。根據(jù)Di對指紋庫中的3高精度的Wi-Fi室內(nèi)定位算法研究算法研究基如式(3-1)，KNN算法通常使用信號空間歐式距離來計算相似度，Di越小相似度越高。根據(jù)Di對指紋庫中的i,ri進行升序排序，并取前K個參考點的坐標根據(jù)Di加權平均得到位置估計?，按式(3-2)和式(3-3)計算。noj2Di式(3-jK式(3-Dω式(3- DjjK通過多次實驗選取一個最優(yōu)值。值得一提的是，當K=1時，該算法退化為信號空間最近鄰法(NearestNeighborinSignalSpace,NNSS)[7]；當K1i1K時，該算法退化為非距離加權的KNN；當為一個基于距離的加權函數(shù)時，KNN演進成DW-KNN(DistanceWeightedKNearestNeighbor,DW-KNN)。本文采DW-KNN作為研究基礎，所述KNN均指DW-KNN，且固定K值為一個常數(shù)(K=3)基于局部加權回歸的射頻指紋地圖校正-23AP的位置可以獲得，射頻信號傳播模型的自適應性和可擴AP的位置，且無需構建信號傳播模型，可以局部加權線性回歸(LocallyWightedRegression,xi,yi,i1,2,xiAP的位置可以獲得，射頻信號傳播模型的自適應性和可擴AP的位置，且無需構建信號傳播模型，可以局部加權線性回歸(LocallyWightedRegression,xi,yi,i1,2,xix1,x2,x3,...,xdyixxxx '''y'1234dFxa0ai相關系數(shù)a可以通過式(3-5)Faarg wn,ii ia其中wxquery留一交叉驗證法(Leave-One-Out-Cross-交叉驗證是一種用來評價一個統(tǒng)計分析的結果是否可以推廣到一個獨立的數(shù)據(jù)集上的技術。主要用于預測，即用于估計一個預測模型在實際應用中的準確度。它是一種統(tǒng)計學上將數(shù)據(jù)樣本切割成較小子集的實用方法，可以現(xiàn)在一個子集上做分析，而其他子集用來作為后續(xù)對此分析的確認和驗證[59]。一個交叉驗證將樣本數(shù)據(jù)集合分成兩個互補的子集，一個子集用于訓練分類器或者模型，該子集被稱為訓練集(trainingset)；另一個子集用于驗證分類器或者模型-24分析有效性，該子集被稱為測試集(testingset)。利用測試集來測試通過訓練集得到的分類器或者模型，以此作為分類器或者模型的性能指標，期望得到預測精確度高德預測和低的預測誤差。為了減少交叉驗證結果的可變性，通常將一個樣本數(shù)據(jù)集合進行多次不同的劃分，得到不同的互補子集，進行多次交叉驗證，并取多次驗證的平均值作為驗證結果。在給定的樣本數(shù)據(jù)集合中，拿出大部分的樣本作為訓練集來進行分類器或者模型的構建，留一小部分的樣本作為測試集，用已經(jīng)建立的分類器或模型進行預測，求出測試集的預測誤差，并記錄它們的平方和。留一交叉驗證作為交叉驗證的一種，具體的做法是：假設有N個樣本，則做分析有效性，該子集被稱為測試集(testingset)。利用測試集來測試通過訓練集得到的分類器或者模型，以此作為分類器或者模型的性能指標，期望得到預測精確度高德預測和低的預測誤差。為了減少交叉驗證結果的可變性，通常將一個樣本數(shù)據(jù)集合進行多次不同的劃分，得到不同的互補子集，進行多次交叉驗證，并取多次驗證的平均值作為驗證結果。在給定的樣本數(shù)據(jù)集合中，拿出大部分的樣本作為訓練集來進行分類器或者模型的構建，留一小部分的樣本作為測試集，用已經(jīng)建立的分類器或模型進行預測，求出測試集的預測誤差，并記錄它們的平方和。留一交叉驗證作為交叉驗證的一種，具體的做法是：假設有N個樣本，則做N驗證，每次取一個樣本作為測試集，其余N-1個樣本作為測試集，可以得到N個分類器或模型，N個預測結果。N個預測結果的誤差平均值用于衡量分類型或者模型的性能。LOOCV的每一個分類器或模型都是用幾乎所有的樣本訓練得到的，最接LWR射頻指紋地圖校正如前文所述，給定一個回歸模型：Fqi01xi2相關系數(shù)向量0,1,2通過式(3-7)獲得式(3-arg wq,qFn式(3-iii的序號，w為權重函數(shù)，qx,y為待預測點（模擬參考點其中j為被預測的的坐標。權重函數(shù)通過計算q與各參考點qi之間的距離來分別賦予各參考點不同的權重，越接近 的參考點獲得越大的權重值。本文采用高斯函數(shù)作為權重函數(shù)：wq,qi其中為控制回歸模型的局部性的系數(shù)，值越大，回歸模型的局部性越強，當式(3-0時，該局部回歸模型退化成一個全局的回歸模型；為待預測點q到第i個參考點之間的歸一化距離：dqqi式(3-dqq*d為歐式距離，q*為待預測點與各參考點的距離中的最大值，當q*qi時，1-25對于每一個AP需要確定一個最優(yōu)的值，從而確定一個回歸模型用于預測該AP在某個待預測點的RSS值。本文采用LOOCV來進行最優(yōu)的做法如下：Rli,ri,i1,2,3,...l 將離線階段進行采樣的l個位置指紋分為l其中對于每一個AP需要確定一個最優(yōu)的值，從而確定一個回歸模型用于預測該AP在某個待預測點的RSS值。本文采用LOOCV來進行最優(yōu)的做法如下：Rli,ri,i1,2,3,...l 將離線階段進行采樣的l個位置指紋分為l其中xiyi為各個采樣點的位置坐標，i個采樣點得到的一AP的RSSnAPj1BadStepConst1Const2Step2:jAPl組數(shù)據(jù)作為樣本集Sjliriji1,2,3ljAP在各個采樣點處的RSS值與對應的位置坐標組成的l個樣本，并初始化0 m1Error0；m個樣本作為測試集Testmlmrmjl1Sj作為訓練集Trainmlirij1ilim，并通過與Trainm按照式(3-3)、式(3-4)(3-5)、式(3-6)建立一個回歸模型F，然后將TestmlmF的輸入，得到一個預測2r?F，并計算預測的誤remm Errorl次的平均誤差Step5，直jStep6:Step4AP在控制參數(shù)值為時回歸模型的預測性能指標，越小預測性能越優(yōu)；Step6:記錄迄今為止的最小值及對應的最優(yōu)值，然后自增的值：Step3Step6，直到連續(xù)BadStepStep6中沒有更新最優(yōu)取此時的最優(yōu)值作為第jAP的控制參數(shù)值，然后自增j的值：jj1Step2Step9，直到jn在確定每個AP的最優(yōu)值后，給定一個待預測點的位置坐標，將整個離線階段采集的位置指紋作為訓練集，可以得到每個別得到各個AP在待預測點的RSS值。對于待定位區(qū)域中選定的p個待預測點， 的一個局部加權回歸模型，從而分每個待預測點nAP分別建立局部加權回歸模型，即為了得到一條預測出來的位置指紋(模擬位置指紋)需要進行n次建模和預測，為了在待定位區(qū)域得到p個模擬位置指紋需要進行pn次建模和預測。預測得到的p條位置指紋數(shù)據(jù)組成一張模擬射頻指紋地圖，該地圖與實際采集獲得的射頻指紋地圖的并集作為KNN算法的在線定位階段計算時使用的射頻指紋-26本文稱上述的最優(yōu)值搜索為LWR-LOOCVLWR射頻地圖校正的KNN定位算法為LWR-KNN 實驗及結果分析實驗環(huán)境實驗區(qū)域為一個約900平方米的典型室內(nèi)環(huán)境，包括12本文稱上述的最優(yōu)值搜索為LWR-LOOCVLWR射頻地圖校正的KNN定位算法為LWR-KNN 實驗及結果分析實驗環(huán)境實驗區(qū)域為一個約900平方米的典型室內(nèi)環(huán)境，包括12個辦公室和1個走廊。實驗區(qū)域平面圖如圖3-1所示區(qū)域內(nèi)可見AP總數(shù)為65n65。離線階段MacBook和在線定位階段的數(shù)據(jù)采集使用同一臺簡化起見，數(shù)據(jù)在中進行處理。3-1實驗區(qū)域平面圖3-1Layoutofthetestbed如圖3-1所示，離線階段在實驗區(qū)域內(nèi)共選定了100個參考點即l=100。兩個最近鄰參考點間距最小為1米，最大為4.8米，平均為2.5米。參考點最少有3個可見。在每個參考點以的頻率采集次數(shù)據(jù)取平均得到一條參考數(shù)據(jù)與位置信息組成一條射頻指紋存入射頻指紋庫。離線階段完成后得到一張射頻指紋地圖RM-27在在線定位階段，選取了40個測試點（含測試起點和測試終點）。每次測試由測試起點開始，以一條固定的路徑在實驗區(qū)域內(nèi)移動，每經(jīng)過一個測試點采集一個觀測值并將對應的位置信息保存以便于計算定位誤差，進入房間后均以原路返回。一次測試中所有測試點均被經(jīng)過280個觀測值，共進行了3240個觀測值。 參考點密集情況下的LWR射頻地圖校正3-1LOOCV進行各AP最優(yōu)值的搜索：將65個AP在100個參考點的位置指紋BadStepConst110，IncrementConst2在在線定位階段，選取了40個測試點（含測試起點和測試終點）。每次測試由測試起點開始，以一條固定的路徑在實驗區(qū)域內(nèi)移動，每經(jīng)過一個測試點采集一個觀測值并將對應的位置信息保存以便于計算定位誤差，進入房間后均以原路返回。一次測試中所有測試點均被經(jīng)過280個觀測值，共進行了3240個觀測值。 參考點密集情況下的LWR射頻地圖校正3-1LOOCV進行各AP最優(yōu)值的搜索：將65個AP在100個參考點的位置指紋BadStepConst110，IncrementConst210按照LWR-LOOCVStep1至Step9APAP的最優(yōu)值如表3-13-1參考點密集情況下部分AP的最優(yōu)Table3-ofalphavaluesin123AP0如圖3-152個模擬參考點，各模擬參考點通過選取部分實際采樣參考點之間較稀疏的兩點之間的中點獲得。將每個模擬參考點作為待預測點，將總體樣本集R作為訓練集，根據(jù)Alphas與LWR算法得到模擬參考點的RSS向量。值得一提的是，在通過LWR模型進行預測時，可能會出現(xiàn)預測值小于-99dBm的情況，此時取預測值為-99dBm。將模擬參考點位置信息與通過LWR模型得到的RSS向量建立成一張模擬射頻RMsRMs與離線階段實際采樣得到的RM的并集作為在線定位RMRMRMs。通過KNN算法對所有測試點進行位置估計，得到的結果如圖3-2和表3-2所示。表3-2參考點密集情況下的定位誤差比3-2the定位算法LWR---3-2參考點密集情況下的累積誤差分布Figure3-2Cumulativeerroroftheintensive由圖3-2和表3-2可以看出，LWR-KNN的累積誤差分布在定位誤差3.803-2參考點密集情況下的累積誤差分布Figure3-2Cumulativeerroroftheintensive由圖3-2和表3-2可以看出，LWR-KNN的累積誤差分布在定位誤差3.80米以內(nèi)始KNN，但差別較小LWR-KNN定位算法的平均定位精KNN算法有較小提高，平均定位誤差減小了0.30米。但在參考點密集情況下，LWR-KNN算法對定位精度的改善并不顯著，那是否說明LWR校正對改善定位精度并沒有明顯效果呢？來看接下來對參考點稀疏的情況下KNNLWR-KNN的對比。參考點稀疏情況下的LWR射頻地圖校為了模擬參考點選取較稀疏的情況，將離線階段選取的參考點進行稀疏化。在待定位區(qū)域的各個房間內(nèi)僅保留13個參考點的位置指紋，且優(yōu)先選擇靠近房間幾何中心的參考點進行保留，得到25個保留參考點；將非保留參考點的位置指紋從RM中移除，得到一張僅包含25條位置指紋記錄的射頻指紋地圖RMr若用平均每平方米參考點個數(shù)來描述參考點的密集程度，如式(3-SparityCcalibration_points式(3-SCcalibration_point為待定位區(qū)域總參考點個數(shù)，S為待定位區(qū)域總面積，則在進行參其考點稀疏化前，待定位區(qū)域的參考點密集程度為 ，稀疏化后的密集程度為2.78%，僅為原來的密集程度的25%將稀疏化后得到的射頻指紋地圖RMr的一組新的最優(yōu)Alphasi,i1,2,3,...,n，部AP的最優(yōu)值如表3-3-293-3參考點稀疏情況下部分AP的最優(yōu)Table3-PartthealphavaluesinthespareAP12300003-1中所示的52LWR預測，得到一張新的模擬射頻指紋地圖，記作RMs。將RMs與稀疏化采樣點后得到的3-3參考點稀疏情況下部分AP的最優(yōu)Table3-PartthealphavaluesinthespareAP12300003-1中所示的52LWR預測，得到一張新的模擬射頻指紋地圖，記作RMs。將RMs與稀疏化采樣點后得到的的并集作為在線定位階段的射頻指紋地圖，記作RMRMrRMs。重新對所有測試點進行位置估計，到的結果如圖3-3和表3-4得3-3參考點稀疏情況下的累積誤差分布Figure3-3Cumulativeerrordistributionofthespare3-3可以看出，在參考點稀疏的條件下，LWR-KNN算法較KNN算法的累計誤差分布改善顯著。LWR-KNN算法的定位誤差以高達90%的概率小于5.00米，KNN算法的定位誤差小于5.00米的概率僅為60%，若以5.00米作為最大可接受則LWR-KNN較KNN算法的定位精度提高了50%表3-4參考點稀疏情況下的定位誤差比Table3-4ofthe定位算法LWR-由表3-4可以看出，LWR-定位算法的定位誤差最小值、最大值、平均值、中值以及均方差都小于KNN算法。從平均定位誤差來看，LWR-KNN算法在參考-30點高度稀疏的情況下，仍保持較高的定位精度，平均定位誤差為2.57米，而同等情況下的KNN算法的平均定位誤差高達4.32點高度稀疏的情況下，仍保持較高的定位精度，平均定位誤差為2.57米，而同等情況下的KNN算法的平均定位誤差高達4.32米，相比之下，LWR-KNN算法的定位精度改善了1.75米，高達41%?？梢姡趨⒖键c稀疏的情況下，LWR-KNN算法可以顯著地提高定位精度。作為擴展的，LWR射頻指紋地圖校正可以用于減少離線階段采集位置指紋的工作量，通過少量的實際采樣的參考點位置指紋，可以通過LWR射頻指紋地圖校正來提供模擬參考點位置指紋。本章小本章針對如何提高基于Wi-Fi室內(nèi)定位系統(tǒng)的定位精度進行了研究，以KNN算法作為研究基礎，提出了LWR-KNN定位算法，通過已有指紋庫中的位置指紋數(shù)據(jù)對各個AP進行LWR-LOOCV最優(yōu)回歸模型參數(shù)搜索，然后對模擬參考點進行LWR預測得到多個模擬位置指紋。實驗結果表明，模擬位置指紋的引入，擴大了原有的射頻指紋地圖，在參考點密集的情況下可以較小地提高KNN算法的定位精度，在參考點稀疏的情況下可以顯著地提高KNN算法的定位精度。LWR射頻指紋地圖校正法可以用于改善定位精度的同時，還可以用于減小離線階段采集參考位置指紋-314高魯棒性的Wi-Fi室內(nèi)定位算法研本章針對如何提高Wi-FiAP信號丟失的情況下仍可以提供可靠的位置估計時，認為這種算法是具有強魯棒性的。以KNN算法的基礎上提出增強魯棒性的KNN算法(Robust-KNN)，期望達到以下兩個目的：在部分AP丟失的條件下仍可提供可靠的位置估計；當系統(tǒng)存在異常時，可以確定一個異常AP4高魯棒性的Wi-Fi室內(nèi)定位算法研本章針對如何提高Wi-FiAP信號丟失的情況下仍可以提供可靠的位置估計時，認為這種算法是具有強魯棒性的。以KNN算法的基礎上提出增強魯棒性的KNN算法(Robust-KNN)，期望達到以下兩個目的：在部分AP丟失的條件下仍可提供可靠的位置估計；當系統(tǒng)存在異常時，可以確定一個異常AP集合，為系統(tǒng)排除異常提供參考。異常條自微軟提出RADAR定位算法的精度和減小離線訓練的工作量進行了研究[60-64]，針對如何增強定位系統(tǒng)的魯棒性的研究較少[65-68]。但在某些異常條件下，例如定位階段某些AP的信號發(fā)生大幅度波動甚至丟失（待定位節(jié)點掃描不到 發(fā)出的烽火信號），定位算法的定位精度將發(fā)生明顯衰減，文獻[65]的作者通過實驗證明了這一點，并在文獻[66]中提出通過顯著性檢驗來檢測惡意攻擊，但并未給出在檢測到惡意攻擊后仍提供可靠的位置估計的方法；文獻[67]通過使用基于中值的最近鄰法(Median-NNSS)并引入冗余節(jié)點來防止異常情況下定位精度的大幅下降；文獻[68]提出的系統(tǒng)通Mica2節(jié)點來檢測節(jié)點（接入點）異常，并使用自適應的距離參數(shù)，但該方法依靠接入點來檢測異常，不適用于一般WLAN環(huán)境。本文將異常限定為AP信號的丟如前文所述，KNN算法使用信號空間歐式距離來計算相似度，Di越小相似度越高。根據(jù)Di對指紋庫中的i,ri進行升序排序，并取前K個參考點的坐標根據(jù)Di加權平均得到位置估計?，按式(3-2)和式(3-3)計算。定義觀測值o值不為Const的（可見）Aoi處參考數(shù)RSSConstriAPAriA，可將式(3-AP通常只能覆蓋待定位區(qū)域的一部分，所以重寫為式(4-1)A，iDi2dijdij式(4- dr -32假設在離線階段，在參考點125一個指紋庫如表4-1RSS數(shù)據(jù)，然后建立 表4-1射頻指紋庫舉 12345---------假設在離線階段，在參考點125一個指紋庫如表4-1RSS數(shù)據(jù)，然后建立 表4-1射頻指紋庫舉 12345------------最近鄰的Unknown1處獲得觀測值30304-2，信號空間上的Di將得到一個正確的參考點排序24513最近鄰點為r2，若按式(4-1)后根據(jù)式(3-2)和式(3-3)將得到一個可靠的位置估計。 表4-2觀測值舉 AP2 --- - - Const30,69，若仍按式(4-1)計算Di，AP1將進入AoD22到錯誤的參考點排序3,5,1,4,2，此時將造成定位誤差大幅增大。本文在原始觀測值中將丟失APAP并不會影響所有觀測值，例如處的觀測值為Const60,30AP1丟失對這個觀測值沒有影響。為便于描述，在考慮異常條件對定位算法精度的影響和檢測異常時，將在觀測值的角度上對Ao丟失AP時，將使Unknown1處觀測值中AP1Const而使Unknown2處觀測值中AP2為Const此時對這兩個觀測值來說分別是33%50%AP丟失。傳統(tǒng)算法定位精度變定義定位誤差為實際位置與位置估 在物理空間上的歐式距離，式(4-不為整數(shù)的情況進行高斯取在每個觀測值中引入%的丟失APKNN算法的定位誤差的均值和標準差變化如圖33中的誤差棒表示標準差。4-1KNN在異常條件下定位誤差大幅增大。20%時平均定位誤差增大至4.21米，相比非異常條件下增大了96%AP丟失比例增大-33時，平均定位誤差還在持續(xù)增大，當%時，平均誤差高達14.70米。而對于所有觀測值來說，20%AP丟失最多僅2AP丟失時，平均定位誤差還在持續(xù)增大，當%時，平均誤差高達14.70米。而對于所有觀測值來說，20%AP丟失最多僅2AP丟失（13個可見AP丟失能力的定位算法是必要的。圖4-1異常條件下傳統(tǒng)KNN的定位誤差變化算法描本文提出的Robust-KNN算法先進行接入點篩選，然后在傳統(tǒng)KNN算法基礎上進行異常檢測、信號空間距離修正以及丟失AP搜索。先對各部分分別進行描述，然后給出算法在在線定位階段的工作流程。接入點篩不穩(wěn)定AP不僅不會改善定位精度反而會降低定位精度，所以先對AP進行篩選[6][10]。這里僅根據(jù)AP在指紋庫中出現(xiàn)的次數(shù)進行篩選，給定一個閾值一個AP在指紋庫中出現(xiàn)的次數(shù)小于時，將其在指紋庫中剔除，在線定位階段該AP不參與匹配計算。本文選取8小于參考點個數(shù)的10%)，經(jīng)過篩選后，n34。如圖4-2所示，雖然射頻指紋的維度由原來的6534，但是定位誤差并無明顯衰減（與文獻[6]中得出的結論一致）。-34圖4-2篩選AP前后累積誤差分布AP篩選為搜索丟失AP奠定了一定基礎，因為若一個AP在指紋庫中出現(xiàn)次數(shù)過AP丟失時，將沒有足夠信息來確定該AP是否已經(jīng)丟失。異常圖4-2篩選AP前后累積誤差分布AP篩選為搜索丟失AP奠定了一定基礎，因為若一個AP在指紋庫中出現(xiàn)次數(shù)過AP丟失時，將沒有足夠信息來確定該AP是否已經(jīng)丟失。異常檢測定義在Lo中的最近鄰點，異常狀態(tài)指示變量為S，檢測正確率為所有的異常觀測值中被正確地檢測為異常的比例，誤檢率為所有非異常觀測值中被錯誤地檢測為異常的比例。R中一個元素可視為n維信號空間上的一點，而R可視為信號空間上這些點的集合。假設在信號空間上R被擬合成一個n維曲面Surface（當然，并不需要得到這個曲面），o也對應信號空間一點。因為在L上總可以找到一點與o的獲取位置的距離為零或者在一定范圍內(nèi)，所以非異常條件下o在Surface表面或者到Surface的最短距Dmin在一定范圍內(nèi)；在異常條件下Dmin將增大至超過一定閾值oAP比例越大，Dmin的增大越明顯，本文稱Dmin的這種變化為信號空間畸變，Dmin可o中存在or之間的信號空間距離來近似。當則AP丟失，S 式(4-false,if -35KNN中是已經(jīng)得到了的，于是只需確定閾值即可完成異常檢測機制Dmin的建立，可由實驗手段根據(jù)非異常條件下的累積分布選取。一次測試的個觀測值在非異常條件和異常條件下的KNN中是已經(jīng)得到了的，于是只需確定閾值即可完成異常檢測機制Dmin的建立，可由實驗手段根據(jù)非異常條件下的累積分布選取。一次測試的個觀測值在非異常條件和異常條件下的Dmin4-3所示(AP后)4-3可見，當觀測值中存在APDmin的累積分布曲線向右移動，丟比例越大右移越明顯。若取25dBm，則當觀測值中5%、10%、15%、20%30%、40%、50%的AP丟失時，理論上將分別以28%、50%、81%、96%、100%100%、100%的正確率檢測到，對應的誤檢率為3%。當減小時，檢測正確率將增大，但誤檢率也增大。值得一提的是，文獻[66]惡意放大或衰減，本文所提的AP丟失是信號衰減的一種特例。AP信號被圖4-3AP丟失造成的信號空間畸變本文最終選擇25dBm5%10%AP丟失的檢測正確率較小，但由圖4-1可以看出5%10%AP丟失對定位誤差的影響也相對較小。信號空間距離修正當觀測值中存在AP丟失時，如果仍通過式(4-1)計算信號空間距離Di，則丟失AP將有可能進入集合ArAoDi進行排序得到的K個最近鄰點不再可靠。所以當StrueDi進行修正，修正后的Di如式(4-4)所示。Didij式(4-APjAri式(4-4)將式(4-1)中的第二項移除，防止丟失APDi的排序。Ar\Ao位置估計仍按式(3-2)和式(3-3)計算。雖然式(4-4)對不同位置的射頻指紋的區(qū)分能力-36較式(4-1)oAP丟失比例在一定范圍內(nèi)時，式(4-4)足夠區(qū)分不同位置從而提供可靠的位置估計，代價是修正信號空間距離后需要重新計算一次Di丟失APAPAr\Ao不斷更新各AP的丟失可能性，逐漸確定丟失AP集合，本文稱這種搜索為SLAP(SearchLostAccessPoint,SLAP)算法。值得一提的是，這里是從系統(tǒng)的角度考慮丟失AP。丟失可能性集合Plostp1p2pn在線定位階段開始時初始化一個p較式(4-1)oAP丟失比例在一定范圍內(nèi)時，式(4-4)足夠區(qū)分不同位置從而提供可靠的位置估計，代價是修正信號空間距離后需要重新計算一次Di丟失APAPAr\Ao不斷更新各AP的丟失可能性，逐漸確定丟失AP集合，本文稱這種搜索為SLAP(SearchLostAccessPoint,SLAP)算法。值得一提的是，這里是從系統(tǒng)的角度考慮丟失AP。丟失可能性集合Plostp1p2pn在線定位階段開始時初始化一個pi1AAP均有可能丟A已丟失的可能性。初始化失且丟失可能性相等。oO ,j1,2,...其中 , ,..., 每得到一個觀測值 都需要更 PjjjjSfalse(4-5)Strue?j與前一次位置估計?j1不同時，按式(9)更新。pi0ifAPi式(4-jifAPi0j式(4-ppiifAPA\iijj其中A表示 的信號空間最近鄰點r的可見AP集合jj式(4-5)中僅將本次觀測值的可見APpi置零，因為假定異常檢測機制是有效的，則當Sfalse時，說明oobs沒有受到丟失AP的影響，即oobs沒有攜帶丟失j僅用于確定未丟失AP是合理的。j有關的信息，那么j式(4-6)oobs的可見AP的對應的丟失可能性置零。當Strueoobsjj到了丟失AP的影響，所 \Aobs中的AP已丟失的可能性較大。但是并不能確 AP全都是丟失AP，而且并不能保證式(4-4)一定可以找出正確的r\Aj?j1)來oj1，然后通過多處觀測值?ArAobsAPojPlost中的值，這也使得SLAP算法僅在待定位節(jié)點不斷移動時才有效。給定一個AP丟失確認閾值，則獲取若干不同位置處的觀測值后，可以得到一APi|pi。系統(tǒng)可以通過實時監(jiān)控或者定時查詢AlostAP-37空來輔助排除異常。本文取8，以保證理論上至多在所有參考點均被作為一次最近鄰點后SLAP就可以找到丟失AP算法工作流4-4給出了Robust-KNN算法的流程圖，在提供位置估計的同時，SLAPPlost中元素的值。每獲取一個觀測值，先通過式(4-1)Dmin空來輔助排除異常。本文取8，以保證理論上至多在所有參考點均被作為一次最近鄰點后SLAP就可以找到丟失AP算法工作流4-4給出了Robust-KNN算法的流程圖，在提供位置估計的同時，SLAPPlost中元素的值。每獲取一個觀測值，先通過式(4-1)Dmin新Di，然后通過判SStrue時，通過式(4-4)否大于異常檢測閾值來設置行位置估計。Di圖4-4Robust-KNN 算法結果及分析非異常條件下算法結果在非異常條件下對KNN算法（AP后）Robust-KNN算法的定位誤差進行實驗，得到結果如表4-34-非異常條件下傳統(tǒng)KNN與Robust-KNN定位誤差3數(shù)均值最小值中值最大值Robust-4-3可見，非異常條件下，Robust-KNN算法的定位誤差相比傳統(tǒng)KNNAlostPlost元素除p161-38異常條件下算法結果首先，通過在240個觀測值中引入丟失APKNN異常條件下算法結果首先，通過在240個觀測值中引入丟失APKNN算法（AP后）Robust-KNN算法的平均定位誤差變化如圖4-5所示。每個觀測值發(fā)生%的AP丟失并不等同于系統(tǒng)的%個AP丟失，本文用這種方式來驗證Robust-KNN的魯棒性，而不關心這種設置下SLAP