無線傳感器網絡定位技術中國科學院信息工程研究所陳永樂

目錄傳感器網絡定位概述測距技術基于測距的定位算法測距無關的定位算法其他相關問題討論總結定位的廣泛需求定位定位是確定目標位置的過程。位置可能是物理坐標（經緯度）或者是邏輯空間（IP地址）應用人員定位（樓宇中人員位置，人員失蹤）車輛定位（物流追蹤，路徑導航）事件定位（森林火災，軍事目標）定位參考地圖和標志建筑GPS指南針和周圍環境定位應用衛星定位美國“GPS”系統（全球運行）1994年，24顆GPS衛星布設完成，21顆工作，3顆備用。“賺足、賺夠”俄羅斯“GLONASS”系統（運行）2011年全球正式運行，24顆工作、3顆維修、3顆備用、1顆測試。“起步早，壽命短”歐洲“伽利略系統”（建設中）2002年啟動，系統計劃由30顆衛星組成，目前只有4顆衛星薩科奇，默克爾親美排中，中國退出。“缺錢！”中國“北斗”系統（建設中）2012年在軌衛星12顆，覆蓋亞太地區。2020年將覆蓋全球。“不差錢”無線定位演進（1）GPS（GlobalPositionSystem）定位為了滿足軍事應用的需求，雷達等無線定位技術相繼出現，直到90年代GPS的民用使得無線定位技術產生了質的飛躍原理理論上3顆衛星就可確定目標的空間位置，但是需要第四顆衛星做精確地時間校準優點具有定位精度高實時性好抗干擾能力強等；缺點無遮擋的室外環境節點能耗高/體積大/成本高需要固定的基礎設施等無線定位演進（2）原理根據基站位置利用三邊定位法來確定移動終端位置

優點室內室外均可定位低成本、低功耗、小體積缺點定位精度低，依賴于基站分布需要固定的基礎設施等蜂窩定位1996年，FCC(FederalCommunicationCommission)強制要求移動服務提供商提供用戶的位置，以便緊急救援(美國E-911/歐盟E-112)無線定位演進（3）區域定位在建筑物內或者功耗受限短距離通信環境中實現對目標的精確定位原理利用Zigbee、WiFi和Bluetooth等通信技術，根據距離和連通度等信息對目標進行定位優點定位精度高部署方便缺點定位范圍有限適應性差，受限于具體應用傳感器網絡為什么需要定位？感知數據的基本要素感知事件需要位置信息，沒有位置信息的感知數據往往毫無價值地理信息路由的需要節點的位置信息是地理信息路由的基礎區域查詢的需要知道節點的位置，才能向特定區域查詢事件是否發生感知覆蓋的需要知道節點的位置，才能判斷區域是否被覆蓋跟蹤目標的基礎確定目標位置是跟蹤目標的前提和基礎傳感器網絡定位傳感器網絡定位分為節點自身定位和目標定位節點自身定位通過人工標定、攜帶GPS模塊或者利用少量已知位置的節點自組織確定節點位置的過程目標定位在節點自身定位完成之后，根據監測到事件或目標的多個傳感器節點的相互協作，通過相應的定位算法確定網絡覆蓋范圍內的事件或目標位置的過程目標坦克位置已知的節點位置未知的節點傳感器網絡節點自身定位節點分類錨節點（Anchor）未知節點節點自身定位利用少量已知位置的錨節點來定位未知節點的過程傳感器網絡定位的研究主體利用少量錨節點對傳感器節點進行自身定位節點自身定位是目標定位的基礎和前提傳感器網絡定位挑戰低廉硬件條件下的精確測距測量節點之間的距離往往是定位的基礎傳感器網絡節點的組件往往采用低端硬件，這將導致測距產生誤差錨節點的部署和選擇錨節點的位置與分布影響未知節點的定位精度錨節點的選擇決定了未知節點的定位參考依據，也會影響定位精度大規模多跳網絡中累積誤差的消除通常未知節點需要錨節點逐跳來迭代計算其位置，在此過程中，定位誤差會逐漸累積，這將會限制定位算法的可擴展性資源受限條件下環境時變性的容忍環境的時變性使得節點之間不可避免會受到障礙物的遮擋，造成測距誤差，這將是資源受限的傳感器節點不易解決的難題基本術語（1）鄰居節點（neighbornodes）：傳感器節點的鄰居節點是指能夠與其直接通信的其它節點；跳數（hopcount）：連接兩個節點的一條路徑上所經過的鏈路個數；跳數距離（hopdistance）：節點間跳數距離是指連接兩個節點路徑上逐跳鏈路的距離之和；視線關系（LineofSight,LoS）：如果兩個節點間沒有障礙物間隔，那么這兩個節點間存在視線關系；

非視線關系（NoLineofSight,NLoS）：如果兩個節點之間存在障礙物，那么這兩個節點間存在非視距關系；基本術語（2）到達時間ToA（TimeofArrival）：信號從一個節點傳播到另一節點所需要的時間；到達時間差TDoA（TimeDifferenceofArrival）：兩種不同傳播速度的信號從一個節點傳播到另一個節點的時間差，或兩個不同節點同時發送的信號到達同一個接收節點的時間差；接收信號強度RSS（ReceivedSignalStrength）：節點接收到無線信號的功率；到達角度AoA（AngleofArrival）：節點接收信號的方向與軸線方向的角度，軸線方向是人為定義的用來計算與接收信號方向的參考基準線；定位算法分類基于測距的定位和測距無關的定位基于測距的定位：利用ToA、TDoA、AoA等測距技術，測量節點之間的物理距離測距無關的定位：根據節點之間的連通度或跳數等信息來獲得節點之間的邏輯距離遞增式的定位和并發式的定位遞增式的定位：從錨節點開始，各節點逐次向外進行定位并發式的定位：所有的節點同時進行位置計算物理定位和邏輯定位物理定位：確定某個節點的實際坐標位置邏輯定位：只需要確定節點是否在某個房間或者樓層內定位算法評價標準定位誤差定位準度：指估算得到的位置與實際位置的匹配程度定位精度：指滿足定位準度要求的結果占所有結果的百分比定位代價硬件代價：指測距過程中所依賴的特殊硬件開銷算法代價：指完成定位算法所需要的通信開銷和計算開銷錨節點密度錨節點用人工標定或GPS模塊的方式來確定位置，不宜部署太多定位覆蓋率指能夠實現定位的未知節點和全部未知節點總數的比例魯棒性指定位算法對多徑、陰影和節點失效等影響的容忍能力本章節分類標準基于測距定位與測距無關定位目錄傳感器網絡定位概述測距技術TOA測距TDOA測距AoA測距RSS測距基于測距的定位算法測距無關的定位算法其他相關問題討論總結基于ToA的測距ToA測距概念指通過測量兩個節點之間信號的發送和接收時間，根據信號的傳播速度和傳播時間，計算兩個節點之間的實際距離單程ToA測距計算的是單程傳播時間，即發送時間與信號到達時間之間的差值雙程ToA測距發送者和接收者之間發送一次往返信號，分別在兩端計算發送和接受信號的時間差基于TOA測距評價單程ToA測距與雙程ToA測距比較單程ToA測距需要發送者和接收這之間進行時間同步雙程ToA在發送者和接受者兩端分別計算時間差，不需要兩個節點保持時間同步。ToA測距評價：測距準確，但硬件要求較高極其微小的硬件測量誤差可能帶來大的測距誤差例如：1毫秒的無線信號傳輸時間誤差就能帶來300米左右的測距誤差。基于TDoA的測距TDOA測距概念通過測量兩組同時發送的信號到達同一個節點的時間差值來計算兩個節點之間的距離或距離差多信號TDoA測距利用節點同時發射兩種不同傳播速度的信號進行測距多節點TDoA測距利用多個時間同步的錨節點同時發射同一種信號進行測距多信號TDoA測距多信號TDoA測距發射節點同時發射無線射頻信號和超聲波信號接收節點記錄兩種信號到達的時間T1、T2已知無線射頻信號和超聲波的傳播速度為c1、c2發送和接收節點之間的距離為其中多節點TDoA測距多節點TDoA測距三個時間同步的錨節點同時發送同一無線信號未知節點S測量來自三個錨節點的到達時間差任意兩個錨節點的距離差就能夠定義一條雙曲線。如錨節點A，C確定雙曲線為|SA|-|SC|=d，其中d為S到A，B的距離差任意兩條雙曲線TDOAB-A和TDOAC-A的交點即可確定為未知節點S的位置基于TDoA測距評價多信號TDoA測距與多節點TDoA測距比較多信號TDoA測距不需要時間同步，硬件復雜多節點TDoA仍然需要錨節點之間進行時間同步基于TDoA測距評價測距準確，對硬件測量精度要求有所降低只在接收端測量信號到達的時間差，降低了對硬件測量精度要求多信號要求硬件更加復雜，以支持多信號基于AOA的測距AoA測距概念利用多天線陣列測量節點接收信號方向與軸線方向之間的夾角軸線方向用來計算接收信號到達角度的參考基準線如圖,以節點A配有兩個接收天線為例，節點A的軸線方向為兩個接收天線R1、R2之間連線的中垂線。基于AOA的測距原理

評價角度測量需要高復雜的天線陣列，增加硬件成本天線陣列需要一定的空間來提供空間差異性以精確測量信號角度，傳感器節點體積較小，很難滿足這些限制條件基于RSS的測距基于RSS測距概念已知發射節點的信號發射功率，接收節點根據收到信號的功率計算出信號的傳播損耗，利用理論或經驗模型將傳輸損耗轉化為距離。自由空間信號衰減模型（Friis衰減模型）Pr和Pt是接收功率與發送功率，Gt和Gr是發送和接收天線的天線增益，R為發送節點與接收節點之間的距離常用模型(Log-Nomal模型)RSS測距原理與評價許多無線模塊都具有測量RSS的功能德州儀器公司的CC2420/CC2530等無線模塊均能通過信號強度指示器（RSSI,ReceivedSignalStrengthIndicator）來獲得接收信號的功率值，計算公式為：

優點模型簡單，無需額外硬件適合視距測量缺點受多徑、陰影衰落影響較大不同環境衰減因子差別很大目錄傳感器網絡定位概述測距技術基于測距的定位算法定位方法定位系統測距無關的定位算法其他相關問題討論總結基于測距的定位算法基于測距的定位算法在測距完成后用于計算未知節點位置的方法定位算法三邊定位法三角定位法多邊定位法混合定位法定位系統Cricket系統Beep系統AHLoS系統槍聲定位系統目錄傳感器網絡定位概述測距技術基于測距的定位算法定位方法定位系統測距無關的定位算法其他相關問題討論總結三邊定位法三邊定位法（Trilateration）指在測得未知節點和周圍錨節點的距離的基礎上，利用未知節點和錨節點的幾何關系確定未知節點位置的方法。三邊定位法舉例二維空間中，已知

A、B、C三個節點坐標分別為(xa,ya)、(xb,yb)、(xc,yc)它們到未知節點O的距離分別為ra，rb，rc假設未知節點O的坐標為(x,y)三角定位法三角定位法（Triangulation）在基于AoA測距獲得的信號到達角度的基礎上，利用三角形的幾何特性來計算未知節點位置的方法三角定位法舉例已知

節點A、B、C的坐標分別為(xa,ya)，(xb,yb)，(xb,yb)

節點

D相對于

A、B、C的夾角分別為：∠ADB,∠ADC,∠BDC如果弧段AC在ΔABC內，那么能夠利用下面公式唯一確定一個圓，圓心為O1(xo1,yo1)，半徑為r1同理確定其他兩個圓，三個圓的交點即所求D點多邊定位法（1）多邊定位法多邊定位法是指根據多個錨節點（>3）和相應的測距結果，尋找一個使測距誤差對定位精度影響最小的點，并以該點作為未知節點的位置多邊定位法舉例假設錨節點數量為n（n>3），其坐標分別為Xi=(xi,yi)(i=1…n)錨節點與未知節點（x，y）間的距離分別為ri(i=1…n)根據錨節點位置和測距結果，建立以下方程組問題：如何求解該方程組？多邊定位法（2）

混合定位法混合定位法當未知節點能夠同時測量到錨節點的距離和方向角時，可以利用距離/角度混合定位法來進行定位估計如圖（a）錨節點只有一個時，未知節點可能定位到兩個位置兩個錨節點時，可以對未知節點唯一定位，如圖（b）所示計算公式如下：目錄傳感器網絡定位概述測距技術基于測距的定位算法定位方法定位系統測距無關的定位算法其他相關問題討論總結Cricket系統Cricket系統簡介MIT為Oxygen項目研發的節點定位系統，Oxygen項目是一個普適計算項目，其寓意是使未來的計算像氧氣一樣無處不在并可自由獲取系統組成節點固定在每個房間內的天花板和墻壁上未知節點部署在需要定位的人或物體上每個節點具有一個超聲波模塊，用于接收和發送超聲波信號Cricket系統Cricket系統定位過程每個錨節點都周期性的同時廣播無線射頻信號和超聲波信號未知節點在收到無線射頻信號時，及時打開超聲波接收模塊未知節點根據兩種信號到達的時間差和各自傳播速度，計算出到該錨節點的距離未知節點選擇距離自己最近的三個錨節點，利用三邊定位法計算出自己的位置定位性能評價Cricket系統定位精度高，具有較好的可擴展性錨節點周期性發送射頻信號和超聲波信號，需要避免錨節點之間發送信號時發生碰撞。Beep系統Beep系統簡介加州大學提出的一種基于聲音的定位系統目標是在辦公室等環境中，對攜帶移動設備的用戶準確定位Beep系統的體系架構由移動設備、聲音傳感器節點、服務器和WiFi網絡組成用戶攜帶的移動設備能夠進行WiFi通信和發送聲音信號位置固定的聲音傳感器節點是錨節點，能夠檢測到聲音信號服務器負責收集相關信息，確定用戶位置。Beep系統定位流程協商發送時間當用戶需要定位時，用戶移動設備通過無線網絡跟周圍的錨節點進行時間同步，協商確定聲音信號的發送時間計算聲音到達時間周圍的聲音傳感器節點收到移動設備發出的聲音信號后，利用特殊的數字濾波器計算出聲音信號的到達時間計算出聲音傳感器節點和移動設備間的距離并發送到服務器服務器定位服務器根據聲音傳感器節點的位置以及接收到的距離信息利用多邊定位方法計算出移動設備的位置移動設備通過無線網絡從服務器獲得其位置信息Beep性能評價Beep系統是采用聲音測距且利用多邊測量的定位系統，具有較好的定位精度在20m*9m的室內空間內，Beep系統能夠以90%的概率獲得0.4m的精度，受環境噪音和障礙物的影響Beep系統的定位精度將下降6-10%聲音信號的穿透能力不強，Beep系統的應用可能局限于一個較小的空間范圍內

AHLoS系統AHLoS系統（Ad-HocLocalizationSystem）簡介加州大學研發的應用于大規模傳感器網絡系統中的定位機制目標：通過確定大規模傳感器網絡中的節點位置，為網絡部署、拓撲控制和路由輔助等提供支持AHLoS系統定位原理AHLoS系統首先利用超聲波進行測距，然后根據未知節點周圍錨節點的分布情況，設計了三種不同定位策略原子多邊策略（AtomicMultilateration）迭代多邊策略（IterativeMultilateration）協作多邊策略（CollaborativeMultilateration）AHLoS定位策略原子多邊策略（AtomicMultilateration）當鄰居中錨節點多于3個時，未知節點利用多邊定位法計算自身位置迭代多邊策略（IterativeMultilateration）當鄰居中錨節點少于3個時，經過一段時間后，部分未知節點在計算出自身位置后轉化為錨節點當鄰居中錨節點等于或大于3個時，未知節點根據原始錨節點和轉化的錨節點，利用多邊定位法計算自身位置協作多邊策略（CollaborativeMultilateration）經過多次迭代定位以后，部分未知節點的鄰居中的錨節點仍然少于3個，此時根據節點的拓撲結構，通過其它節點的協助來計算自身位置未知節點S1，S2的鄰居節點中都只有兩個錨節點，均無法確定自己位置。節點S1可以通過節點S2的協作估算到錨節點A3和A4的多跳距離，再利用多邊定位法計算自身位置。PinPtr槍聲定位系統PinPtr槍聲定位系統簡介范德比爾特大學在美國軍方項目支持下研制開發的基于聲音定位狙擊手位置的反狙擊系統網絡結構槍聲定位系統包含了基站和聲音傳感器節點兩部分多個聲音傳感器節點負責檢測槍聲信號，與基站時間同步基站通常為士兵攜帶的PDA或者筆記本電腦，負責執行傳感器數據融合和槍聲定位算法。PinPtr槍聲波定位原理槍口爆炸波是球面波，它從槍口A點處以速度VS向聲音傳感器所處的位置S傳播彈道震動波在子彈以超聲速飛行的彈道軌跡上形成的波，波峰呈圓錐形定位原理槍口爆炸波為聲波，該定位僅采用槍口爆炸波聲音傳感器節點測量槍口爆炸波的到達時刻，并將數據傳回基站假設狙擊手坐標為（x,y,z），檢測到爆炸聲音信號的傳感器節點位置為（xi,yi,zi），射擊時間為t，聲音傳感器節點獲得的到達時刻ti(x,y,z,t)可表述為：利用4組聲音傳感器節點測得的槍口爆炸波到達時數據建立一個四元方程組通過求解四元方程組解出射擊時間t和狙擊手坐標，確定狙擊手位置性能評價定位平均誤差為1米，從狙擊手射擊到定位其位置不超過2秒鐘。槍口爆炸聲音遠高于背景的噪聲，該系統能夠應用在周圍噪聲復雜的環境中。該系統最早需要靜態部署，一旦聲音傳感器節點被布撒完畢，只能覆蓋一個特定的區域，當布撒的區域不被關注后，傳感器很難再被收集起來重新利用。目前作者又設計了士兵可攜帶的槍聲定位系統，用于部隊行軍過程中的狙擊手定位，但是同時也引入了GPS能量控制的新難題。目錄傳感器網絡定位概述測距技術基于測距的定位算法測距無關的定位算法基于質心的定位算法基于估計距離的定位算法基于指紋的定位算法其他相關問題討論總結測距無關的定位算法測距無關定位算法根據節點之間的連通度或跳數等信息來獲得節點之間的邏輯距離，在此基礎上利用相應算法定位節點無需直接測量節點間的物理距離，降低了對節點硬件的要求，定位的誤差也相應有所增加主要分為三類一類是通過錨節點確定包含未知節點的區域，然后把這個區域的質心作為未知節點的坐標，如質心算法、APIT算法、MSP算法等第二類是先對未知節點和錨節點之間的（連通）距離進行估計，然后利用三邊定位法進行定位，如DV-Hop算法、MDS算法等第三類是通過采集區域中各個位置的指紋特征建立歷史數據庫，利用實時測量值與數據庫中的歷史值進行匹配定位，如RADAR算法等目錄傳感器網絡定位概述測距技術基于測距的定位算法測距無關的定位算法基于質心的定位算法基于估計距離的定位算法基于指紋的定位算法其他相關問題討論總結質心算法（1）質心算法概念質心定位算法是南加州大學的NirupamaBulusu等學者所提出的一種基于網絡連通性的測距無關定位算法質心算法思想首先確定包含未知節點的區域，計算這個區域的質心，并將其作為未知節點的位置

質心算法（2）算法流程錨節點周期性向鄰近節點廣播錨分組，錨分組中包含錨節點的標識號和位置信息；當未知節點接收到來自不同錨節點的錨分組數量超過某一個門限k或接收一定時間后，就確定自身位置為這些錨節點所組成的多邊形的質心。評價簡單：基于網絡連通性，無錨節點和未知節點協調；假設節點擁有球型傳播模型，而實際無線信號傳播模型并非球型；位置估計精確度受限于錨節點的密度和分布。

MSP(Multi-SequencePositioning)算法（1）MSP算法是一種基于事件驅動的定位策略算法流程首先，在區域中從不同法相產生事件觸發，不同位置的節點將依次感知到事件，節點的順序可形成多組一維節點序列然后，MSP算法處理每一組節點序列，確定序列中未知節點的邊界為前后兩個相鄰錨節點位置，根據獲得的多個邊界信息收縮未知節點的位置區域，最后，通過質心算法將縮小區域的質心作為目標節點的估計位置。MSP(Multi-SequencePositioning)算法（2）舉例下圖展示了一個擁有9個未知節點和3個錨節點的傳感器網絡從上到下進行直線掃描后得到一組節點序列為（8，1，5，A，6，C，4，3，7，2，B，9）從左到右進行直線掃描后得到一組節點序列為（3，1，C，5，9，2，A，4，6，B，7，8）錨節點A，B，C位置已知，能夠把區域劃分為16個子區域利用質心算法計算子區域的質心作為未知節點位置APIT算法（1）近似三角形內點測試算法(APIT-ApproximatePoint-In-TriangulationTest)基本思想首先，確定多個包含未知節點的三角形區域；然后，這些三角形區域的交集是一個多邊形，它確定了更小的包含未知節點的區域；最后，計算這個多邊形區域的質心，并將質心作為未知節點的位置關鍵問題確定有多少三角形確定未知節點是否在三角形內部？

APIT算法（2）算法流程未知節點首先收集其鄰近錨節點的位置信息；如位置、標識號、接收到的信號強度等；從這些錨節點組成的集合中任意選取三個節點，假設集合中有n個元素，那么共有Cn3種不同選取方法，確定Cn3個不同三角形，逐一測試未知節點是否位于每個三角形內部，直到窮盡所有Cn3種組合或達到定位所需精度；計算包含目標節點所有三角形的重疊區域，并求質心；APIT定位的核心問題PIT：最佳三角形內點測試法PIT的工作原理PIT（PointinTriangulation）假如存在一個方向，節點M沿著這個方向移動會同時遠離或接近頂點A、B、C，那么節點M位于⊿ABC外；否則，節點M位于⊿ABC內；APIT-實際判斷方法假如在節點M所有鄰居節點中，相對于節點M沒有同時遠離或靠近三個錨節點A、B、C，那么節點M在⊿ABC內；否則，節點M在⊿ABC外；說明：利用網絡中相對較高的節點密度來模擬節點移動，利用無線信號的傳播特性來判斷是否遠離或靠近錨節點；評價相比簡單的質心算法，APIT算法定位精度高，對錨節點的分布要求低，但是對網絡的連通性要求較高目錄傳感器網絡定位概述測距技術基于測距的定位算法測距無關的定位算法基于質心的定位算法基于估計距離的定位算法基于指紋的定位算法其他相關問題討論總結DV-Hop定位算法DV-Hop定位概念采用距離向量路由的原理設計的基于跳數距離的定位算法基本思想首先：計算未知節點與錨節點的最小跳數；然后：估算平均每跳的距離，利用最小跳數乘以平均每跳距離，得到未知節點與錨節點之間的估計距離，最后：利用三邊定位法或多邊定位法計算未知節點的坐標問題如何計算跳數如何估算每跳距離未知節點到錨節點最小跳數步驟1：計算到錨節點最小跳數的流程所有錨節點向鄰居節點洪泛自身信息分組，其中包括錨節點的位置信息和初始值為0跳數。接收節點記錄到每個錨節點的最小跳數，忽略來自同一個錨節點的較大跳數的分組。然后將跳數值加1，并轉發給鄰居節點。基于此方法，網絡中的所有節點均記錄下到每個錨節點的最小跳數。如圖所示，錨節點A廣播的分組以近似于同心圓的方式在網絡中逐次傳播，圖中的數字代表距離錨節點A的跳數。DV-Hop算法的定位過程（2）步驟2：計算未知節點與錨節點的實際跳段距離首先，每個錨節點根據記錄的其它錨節點的位置信息和相距跳數，利用上面的公式計算平均每跳的實際距離，這樣每個錨節點保存一個計算距離然后，錨節點將計算的每跳平均距離用帶有生存期（TTL）字段的分組廣播至網絡中，以減少大規模網絡中的通信開銷，未知節點僅記錄接收到的最近錨節點每跳平均距離，并轉發給鄰居節點；最后，未知節點接收到最近錨節點平均每跳距離，根據記錄的到該錨節點最小跳數，計算到每個錨節點的跳段距離；DV-Hop算法的定位過程（3）步驟3：利用三邊定位法或多邊定位法計算自身位置未知節點利用步驟2中記錄的到各個錨節點的跳段距離，利用三邊定位法或多邊定位法計算自身坐標例子錨節點L2計算的每跳平均距離為(40+75)/(2+5)=16.42A從L2獲得每跳平均距離，則節點A與三個錨節點之間的距離分別為L1：3×16.42，L2：2×16.42，L3：3×16.42；評價優點：對節點的硬件要求低，實現簡單。缺點：利用跳數距離代替直線距離，存在較大的測距誤差MDS-MAP定位算法MDS算法簡介MDS-MAP定位算法是哥倫比亞大學的YiShang等人提出的一種集中式定位算法。多維尺度分析(MultiDimensionalScaling，MDS)源自心理學專業，是一種能夠將具有距離關系的數據轉化為幾何圖形的數據分析技術MDS-MAP算法原理第一步是計算定位區域內所有節點對之間的最短路徑。構建節點之間的距離平方矩陣第二步是對距離平方矩陣采用MDS分析算法原理進行處理，通過多個最大特征值或者特征向量來構造相對坐標圖第三步通過足夠多已知位置的錨節點將節點的相對坐標圖轉換為基于錨節點絕對坐標的實際拓撲圖。MDS分析算法原理

目錄傳感器網絡定位概述測距技術基于測距的定位算法測距無關的定位算法基于質心的定位算法基于估計距離的定位算法基于指紋的定位算法其他相關問題討論總結指紋定位算法研究動機室內定位時，環境噪聲非常大，尤其是使用RSSI信號強度進行距離估計時，RSSI和距離的關系非常復雜。用直觀的測距方法無法得到高精度的位置信息基本思想在目標區域中建立觀察特征和位置之間的映射庫判定的時候，根據觀察值和特征庫中的信息比對，找到最像的指紋定位思想離線階段，建立觀察特征和位置之間的映射指紋庫在線階段，根據觀察值和特征庫中的信息進行最佳匹配優點依賴現有公共WiFi網絡，全球通用性好缺點動態性強的環境、不同設備，設備佩戴位置影響指紋適應性弱指紋學習工作量極大指紋定位算法目錄傳感器網絡定位概述測距技術基于測距的定位算法測距無關的定位算法其他相關問題討論總結在有些情況下，即使知道節點之間的精確距離，也無法對未知節點唯一定位a圖中節點A，B可能定位到多個位置b圖中節點A可能定位到兩個對稱位置剛性圖概念滿足節點間距離關系不變的條件下，如果一個圖不能被連續的扭曲和變形，只能通過旋轉、平移和翻轉進行變化，那么該圖被稱為剛性圖（如圖b）如果一個剛性圖刪掉任何一條邊之后，仍然是剛性圖，那么該圖稱為冗余剛性圖(如圖c)節點可定位性（1）節點可定位性（2）節點可定位必要條件如果一個節點是可定位的，那么這個節點有3條互不相交的獨立路徑分別連接到3個不同的錨節點（3P條件

）滿足3P條件不能保證節點可定位如圖，節點u滿足3P條件，由于節點i和j的位置不確定，使得節點u也無法唯一定位如果一個節點是可定位的,那么這個節點滿足既滿足3P條件又滿足冗余剛性圖條件（RR-3P條件）如下圖，節點u滿足RR-3P條件，既屬于冗余剛形圖，又存在三條獨立路徑到三個