_無線傳感器網(wǎng)絡(luò)定位算法

1、無線傳感網(wǎng)絡(luò)定位算法目錄一、常用定位技術(shù)11.1 GPS與A-GPS定位11.2 基站定位（cell ID定位）11.3 Wifi AP定位21.4 FRID、二維碼定位2二、定位算法研究的目的和意義2三、WSN定位算法分析23.1 基于錨節(jié)點(diǎn)的定位算法23.1.1 距離相關(guān)定位算法23.1.2 距離無關(guān)定位算法33.2 基于移動(dòng)錨節(jié)點(diǎn)的定位算法43.2.1 基于移動(dòng)錨節(jié)點(diǎn)的距離相關(guān)定位算法43.2.2 基于移動(dòng)錨節(jié)點(diǎn)的距離無關(guān)定位算法6四、總結(jié)6附：組員及分工情況7一、常用定位技術(shù)1.1 GPS與A-GPS定位常見的GPS定位的原理可以簡單這樣理解：由24顆工作衛(wèi)星組成，使得在全球任何地方、

2、任何時(shí)間都可觀測(cè)到4顆以上的衛(wèi)星，測(cè)量出已知位置的衛(wèi)星到用戶接收機(jī)之間的距離，然后綜合多顆衛(wèi)星的數(shù)據(jù)就可知道接收機(jī)的具體位置。在整個(gè)天空范圍內(nèi)尋找衛(wèi)星是很低效的，因此通過 GPS 進(jìn)行定位時(shí)，第一次啟動(dòng)可能需要數(shù)分鐘的時(shí)間。這也是為啥我們?cè)谑褂玫貓D的時(shí)候經(jīng)常會(huì)出現(xiàn)先出現(xiàn)一個(gè)大的圈，之后才會(huì)精確到某一個(gè)點(diǎn)的原因。不過，如果我們?cè)谶M(jìn)行定位之前能夠事先知道我們的粗略位置，查找衛(wèi)星的速度就可以大大縮短。GPS系統(tǒng)使用的偽碼一共有兩種，分別是民用的C/A碼和軍用的P（Y）碼。民用精度約為10米，軍用精度約為1米。GPS的優(yōu)點(diǎn)在于無輻射，但是穿透力很弱，無法穿透鋼筋水泥。通常要在室外看得到天的狀態(tài)下才行。

3、信號(hào)被遮擋或者削減時(shí)，GPS定位會(huì)出現(xiàn)漂移，在室內(nèi)或者較為封閉的空間無法使用。正是由于GPS的這種缺點(diǎn)，所以經(jīng)常需要輔助定位系統(tǒng)幫助完成定位，就是我們說的A-GPS。例如 iPhone 就使用了 AGPS，即基站或 WiFi AP 初步定位后，根據(jù)機(jī)器內(nèi)存儲(chǔ)的 GPS 衛(wèi)星表來快速尋星，然后進(jìn)行 GPS 定位。例如在民用的車載導(dǎo)航設(shè)備領(lǐng)域，目前比較成熟的是 GPS + 加速度傳感器補(bǔ)正算法定位。在日本的車載導(dǎo)航市場(chǎng)是由 Sony 的便攜式車載導(dǎo)航系統(tǒng) Nav-U1 首先引入量產(chǎn)。例如在增加了三軸陀螺儀的iphone4里可以利用三軸陀螺儀來輔助完成定位，具體可以參見這篇文章的介紹，不過三軸陀螺儀

4、定位的誤差會(huì)隨著時(shí)間逐漸積累。1.2 基站定位（cell ID定位）小區(qū)識(shí)別碼（Cell ID）通過識(shí)別網(wǎng)絡(luò)中哪一個(gè)小區(qū)傳輸用戶呼叫并將該信息翻譯成緯度和經(jīng)度來確定用戶位置。Cell ID實(shí)現(xiàn)定位的基本原理：即無線網(wǎng)絡(luò)上報(bào)終端所處的小區(qū)號(hào)（根據(jù)服務(wù)的基站來估計(jì)），位置業(yè)務(wù)平臺(tái)把小區(qū)號(hào)翻譯成經(jīng)緯度坐標(biāo)?；径ㄎ涣鞒蹋涸O(shè)備先從基站獲得當(dāng)前位置（Cell ID） （第一次定位） à設(shè)備通過網(wǎng)絡(luò)將位置傳送給gps位置服務(wù)器 àAgps服務(wù)器根據(jù)位置查詢區(qū)域內(nèi)當(dāng)前可用的衛(wèi)星信息，并返回設(shè)備 à設(shè)備中的GPS接收器根據(jù)可用衛(wèi)星，快速查找可用的GPS衛(wèi)星，并返回GPS定位信息。

5、1.3 Wifi AP定位設(shè)備只要偵聽一下附近都有哪些熱點(diǎn)，檢測(cè)一下每個(gè)熱點(diǎn)的信號(hào)強(qiáng)弱，然后把這些信息發(fā)送給網(wǎng)絡(luò)上的服務(wù)端。服務(wù)器根據(jù)這些信息，查詢每個(gè)熱點(diǎn)在數(shù)據(jù)庫里記錄的坐標(biāo)，然后進(jìn)行運(yùn)算，就能知道客戶端的具體位置了。一次成功的定位需要兩個(gè)先決條件：客戶端能上網(wǎng) ，偵聽到的熱點(diǎn)的坐標(biāo)在數(shù)據(jù)庫里有1.4 FRID、二維碼定位通過設(shè)置一定數(shù)量的讀卡器和架設(shè)天線，根據(jù)讀卡器接收信號(hào)的強(qiáng)弱、到達(dá)時(shí)間、角度來定位。目前無法做到精準(zhǔn)定位，布設(shè)讀卡器和天線需要有大量的工程實(shí)踐經(jīng)驗(yàn)難度大，另外從成本上來講WIFI經(jīng)濟(jì)實(shí)用些。二、定位算法研究的目的和意義定位是大多數(shù)應(yīng)用的基礎(chǔ)。由于節(jié)點(diǎn)工作區(qū)域往往是人類不適合

6、進(jìn)入的區(qū)域，或者是敵對(duì)區(qū)域，甚至有時(shí)傳感器節(jié)點(diǎn)需要通過飛行器拋撒，因此節(jié)點(diǎn)的位置通常是隨機(jī)并且未知的。而傳感器節(jié)點(diǎn)自身的正確定位是提供監(jiān)測(cè)事件位置信息的前提，沒有位置信息的監(jiān)測(cè)消息往往是沒有意義的。傳感器節(jié)點(diǎn)必須明確自身位置才能詳細(xì)說明“在什么位置或區(qū)域發(fā)生了特定事件"，除能報(bào)告事件的發(fā)生地外，還能進(jìn)行目標(biāo)跟蹤，實(shí)時(shí)監(jiān)視目標(biāo)路線，預(yù)測(cè)目標(biāo)軌跡等；實(shí)現(xiàn)對(duì)外部目標(biāo)的定位和追蹤。另一方面，了解傳感器節(jié)點(diǎn)位置信息還可以協(xié)助路由，提高路由效率，為網(wǎng)絡(luò)提供命名空間，向部署者報(bào)告網(wǎng)絡(luò)的覆蓋質(zhì)量，實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡以及網(wǎng)絡(luò)拓?fù)涞淖耘渲玫染W(wǎng)絡(luò)管理。因此，確定事件發(fā)生的位置或獲取消息的節(jié)點(diǎn)位置尤為重要，

7、對(duì)傳感器網(wǎng)絡(luò)應(yīng)用的有效性起著關(guān)鍵的作用。而全球定位系統(tǒng)是目前使用最廣泛最成熟的定位系統(tǒng)，通過衛(wèi)星的授時(shí)和測(cè)距對(duì)用戶節(jié)點(diǎn)進(jìn)行定位，具有精度高、實(shí)時(shí)性好、抗干擾能力強(qiáng)等優(yōu)點(diǎn)，但是定位適應(yīng)于無遮擋的室外環(huán)境，用戶節(jié)點(diǎn)通常能耗高且體積大，成本也比較高，需要固定的基礎(chǔ)設(shè)施等。人工部署和為所有網(wǎng)絡(luò)節(jié)點(diǎn)安裝GPS接收器都會(huì)受到成本、功耗、擴(kuò)展性等問題的限制，甚至在某些場(chǎng)合可能根本無法實(shí)現(xiàn)，這使得它不適用于低成本自組織的傳感器網(wǎng)絡(luò)，因此必須采用一定的機(jī)制與算法實(shí)現(xiàn)WSN的自身定位。 隨著計(jì)算機(jī)技術(shù)、微電子技術(shù)和通信技術(shù)的進(jìn)步，傳感器已朝著集成化、微型化、智能化和低能耗的方向快速發(fā)展，使其能夠在較小體積內(nèi)集成信

8、息采集、數(shù)據(jù)處理和信息的傳輸?shù)榷喾N功能，這為無線傳感網(wǎng)(Wireless Sensor Networks WSN)的產(chǎn)生和發(fā)展奠定了基礎(chǔ)。無線傳感網(wǎng)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量廉價(jià)微型的具有有限數(shù)據(jù)處理能力和裝備有低能耗無線信號(hào)收發(fā)器的傳感器節(jié)點(diǎn)通過無線通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)，其目的是利用網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作地感知和采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感興趣的信息，并發(fā)送給觀察者。它通過大量隨機(jī)部署在監(jiān)測(cè)區(qū)域的傳感器節(jié)點(diǎn)來監(jiān)測(cè)和感知周圍的物理環(huán)境。無線傳感網(wǎng)具有布線成本低、監(jiān)測(cè)精度高、系統(tǒng)容錯(cuò)性好、可遠(yuǎn)程監(jiān)控以及便于診斷與維護(hù)等眾多的優(yōu)點(diǎn)，它的產(chǎn)生解決了傳統(tǒng)傳感器網(wǎng)絡(luò)在應(yīng)用中遇到的安裝、維護(hù)等方面的種種困難。其在

9、軍事、工業(yè)、醫(yī)療、交通、環(huán)保等領(lǐng)域有著廣闊的應(yīng)用前景。如果說互聯(lián)網(wǎng)改變了人與人之間的信息交流方式，那么，無線傳感網(wǎng)的產(chǎn)生將改變?nèi)伺c自然界的交互方式。三、WSN定位算法分析3.1 基于錨節(jié)點(diǎn)的定位算法3.1.1 距離相關(guān)定位算法距離相關(guān)定位算法一般利用一定的測(cè)距技術(shù)得到節(jié)點(diǎn)間距離，再利用三邊測(cè)量法、三角測(cè)量法或極大似然估計(jì)法計(jì)算出未知節(jié)點(diǎn)的位置。常用的測(cè)距技術(shù)包括接收信號(hào)強(qiáng)度(RSSI)技術(shù)、信號(hào)傳輸時(shí)間(TOA)技術(shù)、信號(hào)到達(dá)時(shí)間差(TDOA)技術(shù)和信號(hào)到達(dá)角度(AOA)技術(shù)。它們需要一些昂貴的輔助測(cè)量設(shè)備來測(cè)量節(jié)點(diǎn)間的距離，且受環(huán)境影響較大。如RSSI產(chǎn)生的測(cè)量誤差較大；TDOA需要節(jié)點(diǎn)具有

10、超聲波發(fā)送與接收功能；AOA容易受到環(huán)境影響，功耗較大等。但距離相關(guān)定位算法的一個(gè)突出優(yōu)點(diǎn)是定位精度高，因此對(duì)定位精度要求比較高的場(chǎng)合都用基于測(cè)距的定位算法實(shí)現(xiàn)定位。典型算法：接收信號(hào)強(qiáng)度指示法（RSSI）通過信號(hào)在傳播中的衰減來估計(jì)節(jié)點(diǎn)之間的距離。假設(shè)已知發(fā)射功率，在接收節(jié)點(diǎn)測(cè)量接收功率，計(jì)算傳播損耗，使用理論或經(jīng)驗(yàn)的信號(hào)傳播模型將傳播損耗轉(zhuǎn)化為距離。在自由空間中，距發(fā)射機(jī)d處的天線接收到的信號(hào)強(qiáng)度由下面的公式給出：prd=ptGtGr2422L其中，pt為發(fā)射機(jī)功率，prd是距離d處的接收功率，Gt、Gr分別是發(fā)射天線和接收天線的增益，d是距離，單位為米（m），L為與傳播無關(guān)的系統(tǒng)損耗因子

11、，是波長，單位為米（m）。由公式可知，在自由空間中，接收機(jī)功率隨發(fā)射機(jī)與接收機(jī)距離的平方衰減。這樣，通過測(cè)量接收信號(hào)的強(qiáng)度，再利用上述公式即可計(jì)算出收發(fā)節(jié)點(diǎn)間的大概距離。3.1.2 距離無關(guān)定位算法利用節(jié)點(diǎn)間的連通情況來估測(cè)自己的位置。其中一部分距離無關(guān)算法采用集中式計(jì)算模式，用一些優(yōu)化方法來提高定位精度，但是集中計(jì)算方式需要網(wǎng)絡(luò)中有計(jì)算中心支持，且計(jì)算中心附近節(jié)點(diǎn)通信量大，很快能量耗盡，使整個(gè)網(wǎng)絡(luò)不可用。絕大多數(shù)距離無關(guān)定位算法采取分布式計(jì)算模式，可擴(kuò)展性好；由于位置估測(cè)基于節(jié)點(diǎn)間的連通情況，計(jì)算簡單而且容易實(shí)現(xiàn)；計(jì)算在節(jié)點(diǎn)本地進(jìn)行，通信量小。因?yàn)榛诠罍y(cè)距離，距離無關(guān)算法定位精度不如距離相

12、關(guān)算法好。典型算法：DV-hop算法距離向量跳段( distance vector-hop，DV-Hop)定位機(jī)制非常類似于傳 統(tǒng)網(wǎng)絡(luò)中的距離向量路由機(jī)制，DV-Hop 算法的定位過程主要分為 3 個(gè)階段：1) 計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，錨節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息的分組，其中，包括跳數(shù)字段，初始化為 0。接收節(jié)點(diǎn)記錄具有到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一個(gè)錨節(jié)點(diǎn)的較大跳數(shù)的分組。然后，將跳數(shù)值加 1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。通過這種方法，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能夠記錄下到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)。2) 計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的實(shí)際跳段距離每個(gè)錨節(jié)點(diǎn)根據(jù)第一階段中記錄的其它錨節(jié)點(diǎn)的位置信息和相

13、距跳數(shù),并利用下式估算平均每跳的實(shí)際距離i=xi-xj2+yi-yj2hj式中(xi, yi)，(xj, yj) 為錨節(jié)點(diǎn) i, j 的坐標(biāo); hj 為錨節(jié)點(diǎn) i 與 j( i j) 之間的跳段數(shù)，然后，錨節(jié)點(diǎn)將計(jì)算的平均每跳距用帶有生存期字段的分組廣播至網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄接收到的第一個(gè)平均每跳距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。 這個(gè)策略確保了絕大多數(shù)節(jié)點(diǎn)從最近的錨節(jié)點(diǎn)接收平均每跳距離值。未知節(jié)點(diǎn)接收到平均每跳距離后，根據(jù)記錄的跳數(shù)，計(jì)算到每個(gè)錨節(jié)點(diǎn)的跳段距離。3) 利用三邊測(cè)量法計(jì)算自身位置未知節(jié)點(diǎn)利用第二階段中記錄的到各個(gè)錨節(jié)點(diǎn)的跳段距離，利用三邊測(cè)量法計(jì)算自身位置。 已知 A,B,C 3 個(gè)節(jié)

14、點(diǎn)的坐標(biāo)分別為(xa, ya ) , (xb，yb ) ,( xc，yC ),以及它們到未知節(jié)點(diǎn) D 的距離分別為 a，b，c,假設(shè)節(jié)點(diǎn) D 的坐標(biāo)為( x, y) 。那么，有下列公式: x-xa2+y-ya2=a (1) x-xb2+y-yb2=b (2) x-xc2+y-yC2 =c (3) 由式(1) 、式(2) 、式(3)可得未知節(jié)點(diǎn) D 的坐標(biāo)為:3.2 基于移動(dòng)錨節(jié)點(diǎn)的定位算法目前移動(dòng)錨節(jié)點(diǎn)定位算法一般包括以下兩類：第一類是同時(shí)采用移動(dòng)錨節(jié)點(diǎn)和靜態(tài)錨節(jié)點(diǎn)協(xié)作來完成未知節(jié)點(diǎn)的定位過程；另一類則是只通過移動(dòng)錨節(jié)點(diǎn)來獲得未知節(jié)點(diǎn)的坐標(biāo)。利用移動(dòng)錨節(jié)點(diǎn)替代傳統(tǒng)的靜態(tài)錨節(jié)點(diǎn)不但降低了無線傳感

15、器網(wǎng)絡(luò)定位技術(shù)實(shí)現(xiàn)的成本，而且提高了定位精度和定位覆蓋率。3.2.1 基于移動(dòng)錨節(jié)點(diǎn)的距離相關(guān)定位算法基于測(cè)距的移動(dòng)錨節(jié)點(diǎn)發(fā)送的信標(biāo)信號(hào)中包含距離信息，然后未知節(jié)點(diǎn)通過接受到的距離信息通過特定的計(jì)算方法實(shí)現(xiàn)定位。典型算法：MBAL 算法MBAL(mobile beacon assisted localization scheme)定位方法是典型的將移動(dòng)錨節(jié)點(diǎn)定位算法與靜態(tài)錨節(jié)點(diǎn)定位算法相結(jié)合的一種方法，移動(dòng)錨節(jié)點(diǎn)在移動(dòng)的同時(shí)更新其坐標(biāo)并周期的廣播自身的位置信息。未知節(jié)點(diǎn)通過 RSSI 測(cè)距方法獲得與錨節(jié)點(diǎn)之間的距離，當(dāng)接收到 3 個(gè)以上不共線的虛擬錨節(jié)點(diǎn)信息包時(shí)，就可以使用三邊測(cè)量法來計(jì)算自身

16、的位置。未知節(jié)點(diǎn)定位完成以后，就轉(zhuǎn)換成為其他未知節(jié)點(diǎn)提供坐標(biāo)信息的靜態(tài)錨節(jié)點(diǎn)。MBAL 算法假設(shè)錨節(jié)點(diǎn)始終能知道自身的位置，未知節(jié)點(diǎn)可以利用 3 個(gè)及更多的來自移動(dòng)錨節(jié)點(diǎn)或靜態(tài)錨節(jié)點(diǎn)的數(shù)據(jù)包計(jì)算出自身的位置。MBAL 定位可分為以下 3 個(gè)階段：錨節(jié)點(diǎn)初始移動(dòng)階段：為了保證在傳感器網(wǎng)絡(luò)中存在交叉區(qū)域，將移動(dòng)錨節(jié)點(diǎn)的初始位置設(shè)置在網(wǎng)絡(luò)的中心附近。如圖 3.16 所示，交叉區(qū)域是一個(gè)邊長為 R的等邊三角形。錨節(jié)點(diǎn)運(yùn)動(dòng)結(jié)束后，節(jié)點(diǎn)移動(dòng)的距離長度為 2R，參考節(jié)點(diǎn)的數(shù)目是 3 個(gè)。經(jīng)過這個(gè)步驟，處于交叉區(qū)域的未知節(jié)點(diǎn)能夠計(jì)算出自身位置，從而轉(zhuǎn)化為廣播自身位置數(shù)據(jù)包的靜態(tài)錨節(jié)點(diǎn)，進(jìn)行遞增式定位。錨節(jié)點(diǎn)初

17、始運(yùn)動(dòng)路徑（The initial path of a mobile beacon）未知節(jié)點(diǎn)定位階段：靜態(tài)參考節(jié)點(diǎn)為其他未知節(jié)點(diǎn)提供包括自身位置的數(shù)據(jù)包，使更多的節(jié)點(diǎn)被定位，從而遞歸的產(chǎn)生更多的靜態(tài)參考節(jié)點(diǎn)。三邊測(cè)量法至少需要 3 個(gè)錨節(jié)點(diǎn)的位置信息，但 MBAL 使用距離檢查技術(shù)（The range check technique）來計(jì)算接收到兩個(gè)數(shù)據(jù)包的節(jié)點(diǎn)位置。如下圖所示，一個(gè)未知節(jié)點(diǎn)接收到來自參考節(jié)點(diǎn) A 和 B 的兩個(gè)數(shù)據(jù)包，估計(jì)自身到 A 和 B 的距離，從而可以得到兩個(gè)可能的位置1P 和2P 。圖中灰色點(diǎn)是參考節(jié)點(diǎn) A 和 B 的鄰居節(jié)點(diǎn)，也是未知節(jié)點(diǎn)的兩跳節(jié)點(diǎn)。這個(gè)未知節(jié)點(diǎn)只有

18、兩個(gè)鄰居節(jié)點(diǎn)，不能成為兩跳節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，而其中一個(gè)可能的位置2P 是在節(jié)點(diǎn) C 的范圍內(nèi)被定位。因此，1P 是未知節(jié)點(diǎn)唯一的位置。 距離檢查技術(shù)（The range check technique）錨節(jié)點(diǎn)移動(dòng)路徑?jīng)Q策階段：經(jīng)過前兩個(gè)步驟之后，有些未知節(jié)點(diǎn)接收到的位置信息仍然少于 3 個(gè)，這些節(jié)點(diǎn)被稱為請(qǐng)求節(jié)點(diǎn)，向移動(dòng)錨節(jié)點(diǎn)請(qǐng)求更多的位置信息。根據(jù)請(qǐng)求節(jié)點(diǎn)已接收到的數(shù)據(jù)包個(gè)數(shù)，可將這些節(jié)點(diǎn)分為 0-型（已接收到參考節(jié)點(diǎn)信息的個(gè)數(shù)為 0）、1-型（已接收到參考節(jié)點(diǎn)信息的個(gè)數(shù)為 1）和 2-型（已接收到參考節(jié)點(diǎn)信息的個(gè)數(shù)為 2）。根據(jù)不同類型未知節(jié)點(diǎn)的請(qǐng)求，移動(dòng)錨節(jié)點(diǎn)選擇合適的路徑來完成整個(gè)網(wǎng)絡(luò)的

19、定位。MBAL 算法提出的路徑規(guī)劃方法比隨機(jī)路徑規(guī)劃的定位效果好，但它在盡可能減小錨節(jié)點(diǎn)移動(dòng)路徑的同時(shí)，也降低了定位的精度。對(duì)于小規(guī)模傳感器網(wǎng)絡(luò)，MBAL 算法通過上述的路徑規(guī)劃方法縮短了移動(dòng)錨節(jié)點(diǎn)運(yùn)動(dòng)的路徑，減小了錨節(jié)點(diǎn)能耗；采用遞增式的定位算法，降低了定位實(shí)現(xiàn)的成本；使用距離檢查技術(shù)，減少網(wǎng)絡(luò)中不能定位的節(jié)點(diǎn)。但對(duì)于大規(guī)模的網(wǎng)絡(luò)，MBAL 算法會(huì)產(chǎn)生嚴(yán)重的累積誤差且全網(wǎng)定位的執(zhí)行周期較長；網(wǎng)絡(luò)中節(jié)點(diǎn)分布均勻且密度較大時(shí)，采用遞增式定位能夠滿足所有未知節(jié)點(diǎn)都被定位的需求，不需要再使用距離檢查技術(shù)。因此，MBAL 算法不適用于大規(guī)模無線傳感器網(wǎng)絡(luò)定位。 3.2.2 基于移動(dòng)錨節(jié)點(diǎn)的距離無關(guān)定位

20、算法距離無關(guān)的移動(dòng)錨節(jié)點(diǎn)定位算法，無需測(cè)距。典型算法：LMAP 算法LMAP 算法是根據(jù)“圓的任何一條弦的垂直平分線都經(jīng)過該圓的圓心”這個(gè)理論提出的，它是一種非基于測(cè)距的算法，在定位的過程中不需要任何距離或者角度的信息。LMAP 定位原理如圖 3.18 所示，圓心是未知節(jié)點(diǎn)所在的位置，圓的半徑是未知節(jié)點(diǎn)能夠與錨節(jié)點(diǎn)之間進(jìn)行通信的最大距離，移動(dòng)錨節(jié)點(diǎn)經(jīng)過弦的中點(diǎn)。未知節(jié)點(diǎn)接收到 3 個(gè)虛擬參考節(jié)點(diǎn)的信息后，就在以未知節(jié)點(diǎn)為圓心的圓中產(chǎn)生了兩條弦。如上圖所示，Bi，Bj，Bk分別表示3個(gè)虛擬錨節(jié)點(diǎn)，假設(shè)它們的坐標(biāo)為 （xi，yi），（xj，yj）和（xk，yk），未知節(jié)點(diǎn)S的坐標(biāo)設(shè)為（x，y） 。BiBj 和 BjBk 是3個(gè)錨節(jié)點(diǎn)產(chǎn)生的兩條弦，Lij 和 Lik 分別是兩條弦的垂直平分線，通過數(shù)學(xué)運(yùn)算，可以得到以下的方程組：Lij:aijx+bijy=cijLjk:ajkx+bjky=cjk （1）其中，aij=xi-xj ，bij=yi-yj ajk=xj-xk ，bjk=yj-yk cij=xj-xixj+xi2+（yj-yi）yi+yi2 cjk=xk-xjxk