無線節(jié)點(diǎn)定位技術(shù)

1、l節(jié)點(diǎn)定位技術(shù)概述l節(jié)點(diǎn)定位技術(shù)研究現(xiàn)狀與發(fā)展l節(jié)點(diǎn)定位技術(shù)關(guān)鍵問題l基于測(cè)距的定位技術(shù)l無需測(cè)距的定位技術(shù)l協(xié)作定位技術(shù)無線節(jié)點(diǎn)定位技術(shù)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位：依靠網(wǎng)絡(luò)中少量的位置已知的節(jié)點(diǎn)，通過鄰居節(jié)點(diǎn)間有限的通信和某種定位機(jī)制確定網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)的位置。節(jié)點(diǎn)定位在實(shí)際應(yīng)用中包含兩種含義： 自定位確定節(jié)點(diǎn)自身在系統(tǒng)中的位置 目標(biāo)定位確定目標(biāo)節(jié)點(diǎn)在系統(tǒng)中的位置l節(jié)點(diǎn)定位技術(shù)概述信標(biāo)節(jié)點(diǎn)信標(biāo)節(jié)點(diǎn)：已知自身位置信息的節(jié)點(diǎn)，可通過GPS定位設(shè)備或手工配置、確定部署等方式預(yù)先獲取位置信息，為其他節(jié)點(diǎn)提供參考坐標(biāo)。未知節(jié)點(diǎn)未知節(jié)點(diǎn)：信標(biāo)節(jié)點(diǎn)以外的節(jié)點(diǎn)統(tǒng)稱為未知節(jié)點(diǎn)，也有文獻(xiàn)稱為

2、盲節(jié)點(diǎn)。鄰居節(jié)點(diǎn)鄰居節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)通信距離范圍內(nèi)的所有節(jié)點(diǎn)的集合。跳數(shù)跳數(shù)：兩個(gè)節(jié)點(diǎn)之間跳段的總數(shù)。跳距跳距：兩個(gè)節(jié)點(diǎn)之間各跳段的距離之和。節(jié)點(diǎn)連接度節(jié)點(diǎn)連接度：節(jié)點(diǎn)可以探測(cè)發(fā)現(xiàn)到的鄰居節(jié)點(diǎn)個(gè)數(shù)。網(wǎng)絡(luò)連接度網(wǎng)絡(luò)連接度：所有節(jié)點(diǎn)的鄰居個(gè)數(shù)取平均值，可反映傳感器配置的密集程度l節(jié)點(diǎn)定位技術(shù)概述一些概念傳感器網(wǎng)絡(luò)的定位算法通常需要具備以下特點(diǎn)： 自組織性自組織性：傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)隨機(jī)部署，不依賴于全局基礎(chǔ)設(shè)施協(xié)助定位； 健壯性健壯性：傳感器節(jié)點(diǎn)的硬件配置低，能量有限，可靠性較差，定位算法必須能夠容忍節(jié)點(diǎn)失效和測(cè)距誤差； 節(jié)能性節(jié)能性：盡可能地減少算法中計(jì)算的算法復(fù)雜度，減少節(jié)點(diǎn)間的通信開銷，以盡量延

3、長(zhǎng)網(wǎng)絡(luò)的生存周期； 分布式分布式：無線傳感器網(wǎng)絡(luò)通常是大規(guī)模部署網(wǎng)絡(luò)，節(jié)點(diǎn)數(shù)目多，定位任務(wù)將不會(huì)是單個(gè)節(jié)點(diǎn)所能承擔(dān)的，這就需要定位算法具有一定的分布式，把任務(wù)分派到各個(gè)節(jié)點(diǎn)； 可擴(kuò)展性可擴(kuò)展性：無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目可能是成千上萬甚至更多，為了滿足對(duì)不同規(guī)模的網(wǎng)絡(luò)的適用性，定位算法必須具有較強(qiáng)的可擴(kuò)展性。l節(jié)點(diǎn)定位技術(shù)概述要求要求作為一種全新的技術(shù)，無線傳感器網(wǎng)絡(luò)具有許多挑戰(zhàn)性的研究課題，而定位就是其中之一，定位也是大多數(shù)應(yīng)用的基礎(chǔ)和前提傳感器節(jié)點(diǎn)的微型化和有限的電池供電能力使其在節(jié)點(diǎn)硬件的選擇上受到很大的限制，低功耗是其最主要的設(shè)計(jì)目標(biāo)。必須針對(duì)密集性，節(jié)點(diǎn)的計(jì)算、存儲(chǔ)和通信等能力都有限

4、的特定場(chǎng)合設(shè)計(jì)有效的低功耗低功耗定位算法近十年來，無線傳感器網(wǎng)絡(luò)自身定位問題研究有了許多新穎的解決方案和思想，但是每種系統(tǒng)和算法都是用來解決不同的問題或支持不同的應(yīng)用的，它們用于定位的物理現(xiàn)象、傳感器設(shè)備的組成、能量需求、基礎(chǔ)設(shè)施和時(shí)空的復(fù)雜性等許多方面有所不同。對(duì)現(xiàn)有的WSN定位研究成果研究比較發(fā)現(xiàn)，沒有一種定位方案能在有效減少通信開銷、降低功耗、節(jié)省網(wǎng)絡(luò)帶寬的同時(shí)獲得較高的定位精度。而且大部分停留在仿真和實(shí)驗(yàn)階段。因此，該領(lǐng)域還有待更多的人提出更好的方法，以求更好地解決定位問題，使得無線傳感器網(wǎng)絡(luò)能夠真正在實(shí)際生活中得到廣泛的應(yīng)用。l節(jié)點(diǎn)定位技術(shù)的研究現(xiàn)狀和發(fā)展目前，在節(jié)點(diǎn)定位應(yīng)用中，由于

5、受傳感器節(jié)點(diǎn)能量有限、可靠性差、網(wǎng)絡(luò)規(guī)模大且節(jié)點(diǎn)隨機(jī)布放、無線模塊的通信距離有限等影響，對(duì)定位算法和定位技術(shù)提出了很高的要求。一般來說我們從定位區(qū)域與精確度、實(shí)時(shí)性和能耗三個(gè)方面來衡量節(jié)點(diǎn)定位技術(shù)的好壞。1定位區(qū)域與精確度定位區(qū)域與精確度定位區(qū)域與精確度是傳統(tǒng)定位方法和無線傳感器網(wǎng)絡(luò)定位都具有的衡量指標(biāo)，而且定位區(qū)域和精度一般都是互補(bǔ)存在的，定位區(qū)域越大，意味著精度越小。2實(shí)時(shí)性實(shí)時(shí)性實(shí)時(shí)性是定位技術(shù)的另外一個(gè)關(guān)鍵指標(biāo)，實(shí)時(shí)性與位置信息的更新頻率密切相關(guān)，位置信息更新頻率越高，實(shí)時(shí)性越強(qiáng)3能耗能耗能耗是無線傳感器網(wǎng)絡(luò)獨(dú)有的一個(gè)衡量指標(biāo)。在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的電能靠電池來供應(yīng)，電池是不可替換

6、的，因此節(jié)省能量就成了無線傳感器網(wǎng)絡(luò)中一個(gè)重要的問題。另外，還有一些小的方面來衡量無線傳感器網(wǎng)絡(luò)定位技術(shù)的好壞，如定位技術(shù)的擴(kuò)展性、魯棒性和節(jié)點(diǎn)帶寬的占用等。l節(jié)點(diǎn)定位技術(shù)的研究現(xiàn)狀和發(fā)展利用信標(biāo)節(jié)點(diǎn)的位置，通過測(cè)量和估計(jì)信標(biāo)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離，我們就能夠利用它們之間的關(guān)系很容易地算出目標(biāo)節(jié)點(diǎn)的位置?；跍y(cè)距的定位技術(shù)涉及幾何中的圖形問題，已知節(jié)點(diǎn)的位置，求另外幾個(gè)節(jié)點(diǎn)的位置，比較常用的方法有：u三邊定位法u角度定位法角度定位需要另外測(cè)量接收信號(hào)夾角，測(cè)量出夾角后使用數(shù)學(xué)幾何條件，確定節(jié)點(diǎn)的位置。因?yàn)闇y(cè)量的信號(hào)夾角不可能很精確，所以AOA的精度不理想。l節(jié)點(diǎn)定位技術(shù)基于測(cè)距的定位1基本思想基

7、本思想三邊定位法如圖所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為（x1，y1）、（x2，y2）、（x3，y3）。測(cè)得它們到未知節(jié)點(diǎn)D的距離分別為d1、d2、d3。假設(shè)節(jié)點(diǎn)D的坐標(biāo)為（x，y）。以A、B、C三點(diǎn)為圓心，d1、d2、d3為半徑做圓，三圓的焦點(diǎn)即為節(jié)點(diǎn)D的坐標(biāo)。l基于測(cè)距的定位技術(shù)三邊定位法那么，我們可以列出以下公式：將第一個(gè)方程和第二個(gè)方程同時(shí)減去第三個(gè)方程，得到結(jié)果222222131313131322222223232323232()2()2()2()xx xyy yxxyyddxx xyy yxxyydd將其寫成線性方程的形式，AX=B，其中22222213131313132222

8、2223232323232()2()2()2()xxyyxxyyddxxxyyyxxyydd ABXl基于測(cè)距的定位技術(shù)三邊定位法由此可以得出節(jié)點(diǎn)D的坐標(biāo)為1222222131313131322222223232323232()2()2()2()xxyyxxyyddxyxxyyxxyydd l基于測(cè)距的定位技術(shù)三邊定位法三邊定位技術(shù)的計(jì)算方法比較簡(jiǎn)單，在已知兩點(diǎn)之間距離的情況下，采用單純的數(shù)學(xué)公式就可以計(jì)算出來，節(jié)點(diǎn)之間距離的測(cè)量才是三邊定位技術(shù)的最難點(diǎn)，一般來說，有三種算法可以測(cè)量?jī)蓚€(gè)節(jié)點(diǎn)之間的距離：u根據(jù)接收信號(hào)的強(qiáng)度來計(jì)算距離；u根據(jù)信號(hào)傳播時(shí)間或者時(shí)間差來計(jì)算距離；u根據(jù)接收信號(hào)相位差

9、定位。2主要技術(shù)主要技術(shù)1）根據(jù)接收信號(hào)強(qiáng)度定位，信號(hào)衰減模型如下式：式中，P(d)、P(d0)分別表示在距離基站d、d0處的信號(hào)強(qiáng)度，P(d)是接收節(jié)點(diǎn)實(shí)際測(cè)得的信號(hào)強(qiáng)度RSSI，P(d0)一般可以距天線d0米處的路徑衰減來代替。l基于測(cè)距的定位技術(shù)三邊定位法2）根據(jù)信號(hào)傳播時(shí)間測(cè)距（TOA）該技術(shù)是采用信號(hào)到達(dá)時(shí)間來測(cè)量距離的，是一種基于電波傳輸時(shí)間的定位技術(shù)。己知信號(hào)傳播速度，通過測(cè)量信號(hào)從發(fā)射機(jī)傳播到多個(gè)接收機(jī)所消耗的傳播時(shí)間來確定移動(dòng)用戶的位置TOA測(cè)距的基本思想是測(cè)量移動(dòng)臺(tái)發(fā)射信號(hào)的到達(dá)時(shí)間，并且在發(fā)射信號(hào)中要包含發(fā)射時(shí)間標(biāo)記以便接收基站確定發(fā)射信號(hào)所傳播的距離，該方法要求移動(dòng)臺(tái)和

10、基站的時(shí)間精確同步為了測(cè)量移動(dòng)臺(tái)的發(fā)射信號(hào)的到達(dá)時(shí)間，需要在每個(gè)基站處設(shè)置一個(gè)位置測(cè)量單元，為了避免定位點(diǎn)的模糊性，該方法至少需要三個(gè)位置測(cè)量單元或基站參與測(cè)量l基于測(cè)距的定位技術(shù)三邊定位法如圖所示，有A、B、C三個(gè)基站，因?yàn)楣?jié)點(diǎn)間的距離測(cè)量都是一樣的，這里我們就假定先測(cè)量基站A到目的節(jié)點(diǎn)的距離。假設(shè)基站A到目的節(jié)點(diǎn)D的距離為d，聲波傳播速度為v，在T1時(shí)刻基站A發(fā)射機(jī)發(fā)射一個(gè)聲波信號(hào)給目的節(jié)點(diǎn)D，D節(jié)點(diǎn)在T2時(shí)刻接收到該聲波信號(hào)，經(jīng)過短暫的處理之后，在T3時(shí)刻目的節(jié)點(diǎn)D回送一個(gè)聲波測(cè)距信號(hào)給A節(jié)點(diǎn)，在T4時(shí)刻A節(jié)點(diǎn)接收到該信號(hào)。由此可以得出聲波信號(hào)在介質(zhì)中傳播的時(shí)間為：( 21)( 43)t

11、TTTTl基于測(cè)距的定位技術(shù)三邊定位法在這段時(shí)間內(nèi)，聲波傳播的距離為2d，我們就可以得到值得注意的是，這里的T1和T4時(shí)刻是由節(jié)點(diǎn)A測(cè)得的，T2和T3時(shí)刻是由目的節(jié)點(diǎn)D測(cè)得的，由于時(shí)鐘漂移、定位誤差等的存在，兩者的時(shí)間會(huì)有一定的時(shí)間差，但是由于無線采用雙向通信的方式，兩者的時(shí)間差相互抵消，對(duì)結(jié)果沒有太大影響l基于測(cè)距的定位技術(shù)三邊定位法3）根據(jù)到達(dá)時(shí)間差測(cè)距（Time Difference Of Arrival，TDOA）在基于到達(dá)時(shí)間差TDOA的定位機(jī)制中，發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射兩種不同傳播速度的無線信號(hào)，接收節(jié)點(diǎn)根據(jù)兩種信號(hào)到達(dá)的時(shí)間差以及已知這兩種信號(hào)的傳播速度，計(jì)算兩個(gè)節(jié)點(diǎn)之聞的距離，再通過

12、已有基本的定位算法計(jì)算出節(jié)點(diǎn)的位置。l基于測(cè)距的定位技術(shù)三邊定位法如圖所示，發(fā)射節(jié)點(diǎn)在時(shí)刻T0同時(shí)發(fā)射無線射頻信號(hào)和超聲波信號(hào)，接收節(jié)點(diǎn)記錄兩種信號(hào)到達(dá)的時(shí)間T1和T2，己知無線射頻信號(hào)和超聲波的傳播速度分別為c1和c2，那么我們可以知道射頻信號(hào)和超聲波信號(hào)傳播的時(shí)間為：TDOA有一些固有的缺陷需要考慮。首先利用TDOA進(jìn)行定位要求傳感節(jié)點(diǎn)上必須附加特殊的硬件（聲波或者超聲波的收發(fā)器等），這會(huì)增加傳感節(jié)點(diǎn)的成本；其次，聲波或者超聲波在空氣中的傳輸特性和一般的無線電波并不一樣，空氣的溫度、濕度或者風(fēng)速都會(huì)對(duì)聲波的傳輸速度產(chǎn)生很大的影響，這就使得距離的估計(jì)可能出現(xiàn)較大偏差；最后，TDOA測(cè)速的一個(gè)

13、很大的假設(shè)是發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間是沒有障礙物阻隔的，在有障礙物的情況下會(huì)出現(xiàn)聲波的反射、折射和衍射，此時(shí)得到的實(shí)際傳輸時(shí)間將變大，在這種傳輸時(shí)間下估算出來的距離也將出現(xiàn)較大的誤差。2120102121() ()ddttTTTTTTccl基于測(cè)距的定位技術(shù)三邊定位法可以得出 即：接收信號(hào)相位（接收信號(hào)相位（PDOA）通過測(cè)相位差，求出信號(hào)往返的傳播時(shí)間，計(jì)算出往返距離 其中，fc是信號(hào)頻率，是信號(hào)的波長(zhǎng)，是發(fā)送信號(hào)和反射信號(hào)的相位差。由上式可知d的范圍是0, 。不同的距離如果相差倍，則測(cè)量獲得的相位相同。222ccfcfcdl基于測(cè)距的定位技術(shù)三邊定位法常用的角度定位方法有：已知兩個(gè)頂點(diǎn)和夾角

14、的射線確定一點(diǎn)，以及已知三點(diǎn)和三個(gè)夾角確定一點(diǎn)。1已知兩個(gè)頂點(diǎn)和夾角的射線確定一點(diǎn)如圖所示，測(cè)得參考點(diǎn)A(x1,y2)和B(x2,y2)收到的信號(hào)夾角分別是和，根據(jù)可以計(jì)算出待測(cè)節(jié)點(diǎn)N的位置坐標(biāo)(x,y)。這是一種參考節(jié)點(diǎn)A和B自身在坐標(biāo)系已經(jīng)矯正的情形，如果參考點(diǎn)A和B方向沒有校正，需要在計(jì)算時(shí)補(bǔ)償方向偏差。l基于測(cè)距的定位技術(shù)三角定位法22112211(tan) (tan)tantan(cot) (cot)cotcotyxyxxxyxyy如圖所示，在測(cè)量出角、角和角后，可以使用三角定位的方法計(jì)算出N點(diǎn)的位置(x,y)。對(duì)于參考點(diǎn)A(x1,y1)、B(x2,y2)和夾角，根據(jù)圓的內(nèi)接四邊形對(duì)

15、角互補(bǔ)和弦所對(duì)的圓周角等于它所對(duì)的圓心角的性質(zhì)，得到弦AB所對(duì)應(yīng)的圓心角=22?？梢杂葾、B和N確定一個(gè)內(nèi)接圓O的圓心C1（xc1,yc1）和半徑rc1，同理由A、C和N三點(diǎn)就可以確定O2(xc2,yc2,rc2)，由B、C和N三點(diǎn)就可以確定O3(xc3,yc3,rc3)。根據(jù)圓O1、O2、O3，再根據(jù)如下方程組，就可以確定點(diǎn)D(xD,yD)的坐標(biāo)。222221111122222222233333()()()()()()cccccccccxxyyrxxyyrxxyyrl基于測(cè)距的定位技術(shù)三角定位法在無線傳感器網(wǎng)絡(luò)中，基于測(cè)距的定位技術(shù)往往具有很大的優(yōu)勢(shì)，算法比較簡(jiǎn)單，實(shí)現(xiàn)容易，研究人員一般從幾

16、個(gè)方面來評(píng)判這些定位技術(shù)的優(yōu)略。（1）定位精度，即測(cè)距誤差，為測(cè)得的距離與實(shí)際距離的差值，一般來說采用超聲波的TDOA協(xié)議最小，而采用功率衰減來判別距離的RSSI測(cè)距誤差最大。（2）覆蓋范圍。GPS是全球定位系統(tǒng)，一次覆蓋范圍最好，其次是采用功率衰減的RSSI。而TOA和TDOA定位技術(shù)采用超聲波短波，傳播距離最短，因此覆蓋范圍最小。（3）抗干擾能力。當(dāng)有干擾如電磁干擾，多徑干擾等存在時(shí)，節(jié)點(diǎn)是否能夠正常穩(wěn)定工作成為測(cè)距定位技術(shù)性能的一個(gè)重要指標(biāo)。（4）實(shí)現(xiàn)成本。l測(cè)距定位技術(shù)比較1基于連通性的定位基于連通性的定位連通性（Connectivity）是指兩個(gè)節(jié)點(diǎn)是否連通。基于連通性的定位基于連通

17、性的定位可以根據(jù)一個(gè)節(jié)點(diǎn)能否成功解調(diào)其他節(jié)點(diǎn)傳來的數(shù)據(jù)包作為依據(jù)。如果節(jié)點(diǎn)i和節(jié)點(diǎn)j連通，則表示節(jié)點(diǎn)i能夠通過感知、通信等途徑，確定節(jié)點(diǎn)j在自己周圍的一定范圍內(nèi)，但不知道具體的距離和方向。確切地說，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的連通性測(cè)量Qij，可以依據(jù)接收信號(hào)強(qiáng)度表示成0或1的二元變量模型，即： 式中，Pij是節(jié)點(diǎn)i收到的從節(jié)點(diǎn)j發(fā)出的信號(hào)的強(qiáng)度，單位是dBm；Pi是數(shù)據(jù)包剛好能被解調(diào)所需的最小接收信號(hào)閾值強(qiáng)度。l無需測(cè)距的定位技術(shù)基于連通性2基于跳數(shù)的定位基于跳數(shù)的定位在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)間最基本的通信方式是洪泛，所以很多節(jié)點(diǎn)定位機(jī)制都是采用兩個(gè)節(jié)點(diǎn)之間的跳數(shù)（Hop）來估計(jì)節(jié)點(diǎn)之間的距離的。跳

18、數(shù)原理就是對(duì)信標(biāo)節(jié)點(diǎn)信息洪泛的過程進(jìn)行跳數(shù)統(tǒng)計(jì)，通過統(tǒng)計(jì)未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)，然后根據(jù)信標(biāo)節(jié)點(diǎn)之間的距離和跳數(shù)估算出全網(wǎng)每一跳的平均距離，二者相乘，即可得到兩個(gè)節(jié)點(diǎn)之間的距離。l無需測(cè)距的定位技術(shù)基于跳數(shù)質(zhì)心定位算法質(zhì)心定位算法的核心思想是：全網(wǎng)約定一段時(shí)間t為定位時(shí)間。時(shí)間t為(1)tST 式中，T為發(fā)信號(hào)的時(shí)間間隔；S為t時(shí)間內(nèi)要發(fā)送的消息個(gè)數(shù)；為小于1、大于0的常數(shù)。在這段時(shí)間t內(nèi)，信標(biāo)節(jié)點(diǎn)每隔時(shí)間T向鄰居節(jié)點(diǎn)廣播一個(gè)信標(biāo)信號(hào)，信號(hào)中包含自身的位置信息。未知節(jié)點(diǎn)記錄從每個(gè)發(fā)來信號(hào)的信標(biāo)節(jié)點(diǎn)接收到的信標(biāo)信號(hào)數(shù)量。i時(shí)間結(jié)束后，未知節(jié)點(diǎn)計(jì)算與各個(gè)信標(biāo)節(jié)點(diǎn)之間的通信成功率指標(biāo)CMi，即

19、： l無需測(cè)距的定位技術(shù)質(zhì)心定位算法假設(shè)這些坐標(biāo)分別為（x1，y1）、（x2，y2）、（xk，yk），則未知節(jié)點(diǎn)的坐標(biāo)（xest，yest）可用質(zhì)心公式計(jì)算為：11estest(,),kkxxyyxykkl無需測(cè)距的定位技術(shù)質(zhì)心定位算法APIT定位算法的理論基礎(chǔ)是最佳三角形內(nèi)點(diǎn)測(cè)試法PIT。PIT理論為判斷某一點(diǎn)M是否在三角形ABC內(nèi)，假如存在一個(gè)方向，沿著這個(gè)方向M點(diǎn)會(huì)同時(shí)遠(yuǎn)離或接近三角形ABC的三個(gè)頂點(diǎn)A、B、C，那么點(diǎn)M位于三角形ABC外；否則，點(diǎn)M位于三角形ABC內(nèi)。l無需測(cè)距的定位技術(shù)APTI定位算法在圖（a）中,位置未知節(jié)點(diǎn)M通過與鄰居節(jié)點(diǎn)1交換信息，得知自身如果運(yùn)動(dòng)至節(jié)點(diǎn)1，將遠(yuǎn)

20、離信標(biāo)節(jié)點(diǎn)B和C，但會(huì)接近信標(biāo)節(jié)點(diǎn)4，與鄰居節(jié)點(diǎn)2、3、4的通信和判斷過程類似，最終確定自身位于三角形ABC中；而在圖（b）中，當(dāng)節(jié)點(diǎn)4可知自身運(yùn)動(dòng)至鄰居節(jié)點(diǎn)2處，將同時(shí)遠(yuǎn)離信標(biāo)節(jié)點(diǎn)A、B、C，故判斷自身不在ABC中。l無需測(cè)距的定位技術(shù)APTI定位算法APIT定位的具體步驟如下：（1）收集信息：未知節(jié)點(diǎn)收集鄰近信標(biāo)節(jié)點(diǎn)的信息，如位置、標(biāo)識(shí)號(hào)、接收到的信號(hào)強(qiáng)度等，鄰居節(jié)點(diǎn)之間交換各自接收到的信標(biāo)節(jié)點(diǎn)的信息。（2）APIT測(cè)試：測(cè)試未知節(jié)點(diǎn)是否在不同的信標(biāo)節(jié)點(diǎn)組合的三角形內(nèi)部。（3）計(jì)算重疊區(qū)域：統(tǒng)計(jì)包含未知節(jié)點(diǎn)的三角形，計(jì)算所有三角形的重疊區(qū)域。（4）計(jì)算未知節(jié)點(diǎn)位置：計(jì)算重疊區(qū)域的質(zhì)心位置，

21、作為未知節(jié)點(diǎn)的位置。l無需測(cè)距的定位技術(shù)APTI定位算法DV-Hop算法算法的基本思想是將未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離用網(wǎng)絡(luò)中節(jié)點(diǎn)的平均每跳距離和兩節(jié)點(diǎn)之間跳數(shù)的乘積來表示，然后再使用三邊測(cè)量法或極大似然估計(jì)法來獲得未知節(jié)點(diǎn)的位置信息。DV-Hop算法的定位過程分為以下三個(gè)階段：1）計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)首先使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)。在算法開始的時(shí)候，每個(gè)信標(biāo)節(jié)點(diǎn)都發(fā)出一個(gè)包括自己位置信息、地址和跳數(shù)值為0的位置信息包，它們周圍所有跳數(shù)為1的鄰居都收到這樣的信息，將信標(biāo)節(jié)點(diǎn)的位置信息和跳數(shù)記錄下來，并將收到信息包的跳數(shù)值加1，再向自己的

22、鄰居節(jié)點(diǎn)廣播。這個(gè)過程一直持續(xù)下去，直到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都獲得每個(gè)信標(biāo)節(jié)點(diǎn)的位置信息和相應(yīng)的跳數(shù)值為止。l無需測(cè)距的定位技術(shù)DV-Hop定位算法2）計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的平均每跳距離在第二階段，每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)第一階段獲得的其他信標(biāo)節(jié)點(diǎn)位置和相隔跳數(shù)之后，根據(jù)下式計(jì)算網(wǎng)絡(luò)平均每跳距離HopSize。式中，（xi，xj）、（yi，yj）是信標(biāo)節(jié)點(diǎn)i 和j 的坐標(biāo)，hji是信標(biāo)節(jié)點(diǎn)i和j（ij）之間的跳段數(shù)。在實(shí)驗(yàn)中，我們發(fā)現(xiàn)，當(dāng)總跳數(shù)大于一定的值之后，每個(gè)節(jié)點(diǎn)所計(jì)算的平均每跳距離基本一樣。l無需測(cè)距的定位技術(shù)DV-Hop定位算法3）利用三邊測(cè)量法計(jì)算自身位置在未知節(jié)點(diǎn)獲得與3個(gè)或3個(gè)以上信標(biāo)節(jié)點(diǎn)

23、的距離后，執(zhí)行三邊測(cè)量定位。該算法只需要較少的信標(biāo)節(jié)點(diǎn)，計(jì)算和通信開銷適中，不需要節(jié)點(diǎn)具備測(cè)距能力，是一個(gè)可擴(kuò)展的算法，但是該算法對(duì)信標(biāo)節(jié)點(diǎn)的密度要求較高，對(duì)于各向同性的密集網(wǎng)絡(luò)，才可以得到合理的平均每跳距離，從而能夠達(dá)到適當(dāng)?shù)亩ㄎ痪取無需測(cè)距的定位技術(shù)DV-Hop定位算法將節(jié)點(diǎn)間點(diǎn)到點(diǎn)的通信連接視為節(jié)點(diǎn)位置的幾何約束，把整個(gè)網(wǎng)絡(luò)模型化為一個(gè)凸集，從而將節(jié)點(diǎn)定位問題轉(zhuǎn)化為凸約束優(yōu)化問題，然后使用線性矩陣不等式、半判定規(guī)劃或線性規(guī)劃方法得到一個(gè)全局優(yōu)化的解決方案，確定節(jié)點(diǎn)位置。同時(shí)也給出了一種計(jì)算未知節(jié)點(diǎn)有可能存在的矩形空間的方法。l無需測(cè)距的定位技術(shù)凸優(yōu)化方法第八章 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位

24、技術(shù)無線傳感器網(wǎng)絡(luò)自身定位算法的性能對(duì)其可用性有直接的影響，如何評(píng)價(jià)定位算法是一個(gè)需要研究的問題?？蓮氖欠裥枰艠?biāo)節(jié)點(diǎn)、信標(biāo)節(jié)點(diǎn)布置方式、計(jì)算模式、定位原理和節(jié)點(diǎn)外加設(shè)備等角度對(duì)上述無須測(cè)距節(jié)點(diǎn)定位技術(shù)進(jìn)行了分析和比較，如下表所示。l無需測(cè)距的定位技術(shù)分析比較剛性體理論概述剛性體理論概述剛性，即在不考慮物質(zhì)特性的理想條件下任何兩個(gè)連接點(diǎn)之間的歐氏距離不隨其運(yùn)動(dòng)狀態(tài)改變的特性。普通剛性理論是一種定義在光滑軌道上的運(yùn)動(dòng)特性。當(dāng)圖沿著光滑軌道運(yùn)動(dòng)時(shí)，任意兩個(gè)節(jié)點(diǎn)qi(t)和qj(t)間的歐氏距離不隨時(shí)間函數(shù)變化，則qi(t)和qj(t)具有普通剛性特性。用數(shù)學(xué)描述，即當(dāng)幾何圖沿著軌道q(0, )做剛性運(yùn)動(dòng)時(shí)，則任意時(shí)刻的節(jié)點(diǎn)集qi(t)和qj(t)是全等的?？捎脭?shù)學(xué)公式表示為( )0q Rq式中， R(q)是一個(gè)mn型的矩陣，稱為剛體矩陣。l協(xié)作定位技術(shù)定理1：在二維的平面空間中，圖形G=(v,L)擁有n個(gè)頂點(diǎn)，如果L（L為圖形的邊集）存在一個(gè)有2n3條邊的子集E，且對(duì)任意一個(gè)非空邊集E中有n個(gè)頂點(diǎn)且E中元素?cái)?shù)量不超過2n3，那么圖形G=(V,L)在二維平面空間中具有普通剛性。定理2：在一個(gè)二維平面空間中圖G內(nèi)包含n4個(gè)定點(diǎn)，如果圖G中某個(gè)點(diǎn)具有3-連接（3-Connected）結(jié)構(gòu)且該圖形