【正文】 4．4．3 錨節(jié)點組的選定和位置估計這一階段計算未知節(jié)點的位置坐標。錨節(jié)點通過這條路徑到錨節(jié)點的跳數(shù)為，未知節(jié)點, 的平均跳距為。最短路徑和未知節(jié)點平均跳距知道后根據(jù)文獻利用距離誤差進一步改進節(jié)點之間的距離。未知節(jié)點利用()和(()式計算錨節(jié)點的跳數(shù)權值和自身的平均跳距如下: () ()這里是錨節(jié)點的數(shù)量，,為錨節(jié)點的平均跳距，是未知節(jié)點和錨節(jié)點之間的最小跳數(shù)。3．最后錨節(jié)點廣播到網(wǎng)絡中所有的節(jié)點。2．然后，錨節(jié)點計算錨節(jié)點的平均跳距權值和錨節(jié)點的平均跳距:通過（）和（）式估算每個錨節(jié)點的平均跳距 ()這里是節(jié)點的通信距離。表示錨節(jié)點和之間的平均跳距。1． 首先通過（）式和（）式算出每個錨節(jié)點的臨時平均跳距。最后再算出相距每個錨節(jié)點的距離。4．4．2 節(jié)點距離的計算這一階段具體又需要三步:第一步是計算每個錨節(jié)點的平均跳距。4．4 新的DVhop算法的設計及其實現(xiàn)傳統(tǒng)DVhop算法有三個階段，改進后的算法也按三個階段進行。在 DVhop中，往往假設距離未知節(jié)點最近的錨節(jié)點能為其提供最精確的平均跳距，但在網(wǎng)絡中有許多錨節(jié)點，這些錨節(jié)點每一個都包含有特定的平均跳距信息，但是在定位過程中大多數(shù)錨節(jié)點的平均跳距信息沒有得到充分的利用而被浪費掉了。隨著網(wǎng)絡中錨節(jié)點數(shù)量的增加網(wǎng)絡覆蓋率也將得到相應的增長。c．定位覆蓋率受網(wǎng)絡連通性影響。因此，DVhop算法的定位精度跟錨節(jié)點的密度有很大的關系。b．節(jié)點之間的估算距離誤差是隨著兩點間跳數(shù)的增加而增加的。對于DVhop算法錨節(jié)點數(shù)量對其性能的影響也是巨大的。2．節(jié)點密集度和錨節(jié)點比例的影響。這種情況將會給節(jié)點的估計位置帶來很大的定位誤差。DVhop算法的估計位置誤差在節(jié)點分布的嚴重不均勻的情況下將有顯著增加。如果在計算平均跳距時，某些錨節(jié)點由于相距太近而分不出彼此時，將會嚴重影響平均跳距的精度。，錨節(jié)點, ,距離很近，而未知節(jié)點O的位置又距離此三個錨節(jié)點很遠，如果節(jié)點間的估算誤差較大，那么未知節(jié)點O到這三個錨節(jié)點的估算距離就很可能幾乎一樣，此時如果利用這三個錨節(jié)點進行位置估算，很可能將得到無解的結果或者定位誤差很大。，錨節(jié)點、位置離得很近，而與未知節(jié)點O卻相距較遠，這就會出現(xiàn)與和到口的距離相比，:之間的距離幾乎可以忽略不計，因此，就可能導致D的估算位置出現(xiàn)在口處，造成很大的定位誤差。，當錨節(jié)點、在一條直線上時，它們通信圓周的交點將會出現(xiàn)不確定性，即圖中所示的O和Q兩點，這勢必會導致估算位置與實際位置存在很大的誤差。事實上，錨節(jié)點之間的拓撲關系和錨節(jié)點與未知節(jié)點之間的拓撲關系在很大程度上將影響未知節(jié)點的定位。一般來講，未知節(jié)點選擇的錨節(jié)點越多，估計的精度應該越高。這些都在一定程度上影響DVhop算法的定位性能。其次，網(wǎng)絡節(jié)點是隨機部署的，網(wǎng)絡拓撲會對定位性能產(chǎn)生相當大的影響。用試表示第個錨節(jié)點到未知節(jié)點的距離，可得到下面的公式: ()未知節(jié)點位置X可通過()式求得(此處M表示錨節(jié)點個數(shù)): ()（）式可展開為 ()用矩陣形式表示如下: ()此處 的最小二乘估計是 ()4．3 傳統(tǒng)DVhop算法誤差分析DVhop算法把用兩點間的最小跳數(shù)表示的兩點間最短路徑看作一條直線，利用網(wǎng)絡平均跳距計算節(jié)點間的距離進行定位。這一步的最后，未知節(jié)點基于平均跳距和距離錨節(jié)點的最小跳數(shù)可計算出到錨節(jié)點的距離為: ()第三步，每個未知節(jié)點計算它的位置坐標。每個未知節(jié)點將收到的第一個平均跳距值作為它的平均跳距并拋棄來自其它錨節(jié)點的其它平均跳距值。當未知節(jié)點收到平均跳距和距離其它錨節(jié)點的跳數(shù)后，它們將用平均跳距乘以跳數(shù)從而估計出到它們所能收到的所有錨節(jié)點的距離。通過這種機制，網(wǎng)絡中所有的節(jié)點將得到距離每個錨節(jié)點的最小跳數(shù)值。第一步，每個錨節(jié)點廣播一個信標信息到整個網(wǎng)絡中，此信標信息包含了一個初始化為1的跳數(shù)值。然后，計算網(wǎng)絡平均每跳的距離(簡稱平均跳距)，并將其作為一個校正值廣播到整個網(wǎng)絡，當未知節(jié)點收到這個值的時候計算出到錨節(jié)點的距離。4．2 傳統(tǒng)DVhop算法D Vhop算法由三部分組成。本章將在前人研究基礎上，對DVhop定位算法做出進一步改進，提出了一種新的D Vhop算法，即引入權值改進計算平均跳距的方法，使其更加合理，利用拓撲關系對錨節(jié)點進行選取，最后用加權質心算法進行位置估計。共線度引入到了DVhop中從而提出一種基于共線度的DVhop算法。為了提高定位精度，已經(jīng)有許多改進的DVhop算法被提出來，例如:加權DVhop算法，該算法通過計算距離權值而得出較精確的位置估計。DVhop算法是由Niculescu and NatP2在Navigate項目中提出的一種分布式基于非測距的定位算法。通過本章可以知道，每種定位系統(tǒng)或算法都有各自的特點和適用范圍，不存在絕對最優(yōu)的情況，因此在實際應用中，應該根據(jù)具體情況綜合考慮來選擇合適的定位算法或系統(tǒng)。然后又重點介紹了幾種現(xiàn)有的典型定位算法和定位系統(tǒng)。3．4 本章小結本章主要對無線傳感網(wǎng)絡定位技術進行了全面的討論。得出質心算法定位誤差最大，但其性能不受節(jié)點密度影響，實現(xiàn)最簡單，通信開銷最小。但是該算法在實施定位以前需要事先預知網(wǎng)絡平均連通度，并且其定位效果受到節(jié)點密度的制約。未知節(jié)點到錨節(jié)點的距離可以通過來計算。 (3 .18)式中，和分別是節(jié)點和在第一步中獲得的跳數(shù)值。 ()這里:是通信半徑，是本地鄰節(jié)點數(shù)即平均連通度。第三個階段，利用三邊定位算法或其它定位方法，實現(xiàn)未知節(jié)點的定位。采用與DVhop類似的方法獲取距錨節(jié)點的最小跳數(shù)路徑，稱為梯度值，不同的是Amorphous將通信半徑作為平均跳距，具體定位過程可以分為以下三個階段:第一個階段，未知節(jié)點計算與每個錨節(jié)點之間的最小跳數(shù)路徑，這一階段與DVhop算法相同。相對于計算簡單的類似的質心定位算法，APIT算法定位精度高且性能穩(wěn)定，對錨節(jié)點的分布要求較低，但是APIT測試對網(wǎng)絡連通性有著很高的要求。最后計算所有包含目標節(jié)點的三角形的重疊區(qū)域，重疊區(qū)域的質心即為目標定位節(jié)點的估計位置。APIT算法的定位過程大體可描述如下:首先目標定位節(jié)點收集其臨近錨節(jié)點的信息，然后從這些錨節(jié)點組成的集合中任意選取三個錨節(jié)點組成三角形。 C，就可判定節(jié)點對在4ABC內(nèi)幾?？赏ㄟ^鄰節(jié)點交換各自接收到的信號強度，判斷距離某一錨節(jié)點的遠近來模仿PIT中的節(jié)點移動方向，假如在節(jié)點M的鄰節(jié)點中，相對于節(jié)點M沒有。為了在無線傳感網(wǎng)絡中實現(xiàn)三角形內(nèi)點測試，近似三角形內(nèi)，點測試法被提了出來。否則，位于其內(nèi)。3)APIT定位算法APIT算法[ys}的理論基礎就在于如何判斷一點位于三角形內(nèi)部，即最佳三角形內(nèi)點測試法PIT Cperfect pointintriangulation test。另外，該算法的定位精度與錨節(jié)點的分布和密度密切相關，錨節(jié)點分布越均勻，密度越大，定位精度就越高，而在實際部署中，錨節(jié)點也不能夠保證是均勻分布的。例如，假設未知節(jié)點接收到信標信號的錨節(jié)點組的位置向量表示為: ()則該未知節(jié)點的坐標就可表示為:(3 .15) ()質心算法的優(yōu)點就在于不需要錨節(jié)點和未知節(jié)點之間相互協(xié)調(diào)，完全利用網(wǎng)絡連通性，簡單易行。算法中，錨節(jié)點周期性地向網(wǎng)絡中廣播一個包含自身的位置和ID信息的信標信號。2)質心算法質心算法是Nirupama Bulusu等提出的一種基于網(wǎng)絡連通性的定位算法。然而，其在利用平均跳距計算節(jié)點間距離的時候，會產(chǎn)生較大誤差，從而降低了定位精度。最后，未知節(jié)點通過三邊定位或多邊定位計算它們的位置。DVhop算法類似于傳統(tǒng)網(wǎng)絡中的距離矢量路由機制，大體由以下三部分組成:首先，利用典型的距離矢量交換協(xié)議使網(wǎng)絡中所有節(jié)點獲得距離錨節(jié)點的最小跳數(shù)。1)DVhop算法Rutgers University的Dragos Niscules等人利用距離矢量路由(Distance VectorRouting)和GPS定位原理提出的DVhop, Euclidean, DV distance, DV Bearing ,DV coordinate和DV Radial六種分布式定位算法，合稱為APS。1．基于非測距定位算法相對于基于測距的定位算法，非測距定位算法無需測量節(jié)點間的距離或角度，僅需利用節(jié)點之間連通關系從而實現(xiàn)定位，對硬件的要求大大降低，非常適合于大規(guī)模無線傳感網(wǎng)絡的應用。但該算法會產(chǎn)生大量的運算和通信開銷。相對TOA定位算法，該算法在時間同步方面全網(wǎng)時間同步代價要小的多。首先未知節(jié)點利用TDOA測距技術測量到錨節(jié)點的距離。雖然該定位算法具有較高定位精度的優(yōu)點，但要求其錨節(jié)點與未知節(jié)點間必須保持高度精確的時間同步，要求傳感器節(jié)點具有很高的硬件和功耗，這極大的限制了其在實際中的應用。首先未知節(jié)點利用TOA測距技術測量到錨節(jié)點的距離。劣勢在于AOA測距技術易受外界環(huán)境影響，且需要額外的測量硬件，在功耗和硬件尺寸上并不適用于大規(guī)模的網(wǎng)絡應用。當未知節(jié)點在測量出到達三個以上錨節(jié)點的距離后，利用三角定位法或其它方法估算出自身的位置坐標。2)基于AOA的定位算法基于AOA的定位算法[[9,10]是指通過利用AOA測距技術測量節(jié)點之間角度而實現(xiàn)定位。雖然在實驗環(huán)境中該定位算法具有良好的特性。首先未知節(jié)點利用RSSI測距技術測量到錨節(jié)點的距離。較典型的基于測距的定位算法主要有基于RSSI的定位算法、基于AOA的定位算法、基于TOA的定位算法和基于TDOA的定位算法等。 ()3．3 無線傳感網(wǎng)絡典型定位算法和定位系統(tǒng)3．3．1 幾種典型的定位算法1．基于測距的定位算法基于測距的定位機制是通過測量節(jié)點間的實際距離或角度而實現(xiàn)定位。這樣的誤差在實際應用中是不可避免的，為了克服這種情況排除多余的節(jié)點取得最優(yōu)解，通常采用以下幾種估計方法。根據(jù)兩點之間的距離公式可以列出如下式子: (3 .10)上式可展開為 ()用矩陣形式，如下： ()此處 因此可以得出未知節(jié)點F的坐標: ()4．最優(yōu)位置估計法上述三種基本的定位方法在理想情況下已經(jīng)可以實現(xiàn)未知節(jié)點的定位，然而，在實際應用中由于各種誤差的存在使得定位更加的復雜。三邊定位本質上是多邊定位的特例只不過其多次測量方程的個數(shù)等于變量的個數(shù)，而多邊定位則是多次測量方程的個數(shù)大于變量的個數(shù)。在計算出這些數(shù)據(jù)后，可以利用三邊定位方法，算出未知節(jié)點的位置坐標。 ()由上式就可以計算出圓的圓心坐標和半徑,上式中。它到錨節(jié)點的角度分別為創(chuàng)。另外，該方法可以通過方向性天線，利用AOA方法測量角度來定位。根據(jù)檢測的結果可以確定出未知節(jié)點的大致位置。因此可列出下式 （）有以上公式就可以得到點的坐標： （）2．三角定位三角測量法是一種利用三角形的幾何關系進行位置估算的方法。，已知平面上三點個節(jié)點的坐標，以及它們到未知節(jié)點的距離分別為: 和。1．三邊定位三邊定位是適用于包含多個錨節(jié)點的定位系統(tǒng)，也是使川的較為廣泛的一種定位方法。分別表示之間的距離，的最小跳數(shù)分別表示為。其基本思想是用網(wǎng)絡平均跳距與兩者之間最小跳數(shù)的乘積表示節(jié)點間的距離。不同的距離如果相差倍，則測量獲得的相位相同。5．接收信號相位測距接收信號相位測距技術是通過測相位差，求出信號往返的傳播時間，計算出往返距離 ()其中，是信號頻率，是信號的波長，是發(fā)送信號和反射信號的相位差。由于該技術受外界環(huán)境的影響比較明顯，所以，測距精度會產(chǎn)生較大偏差，同時該技術還需要額外的硬件設備完成測角。所以:在成本和能耗方面，該方法不一定適用于無線傳感網(wǎng)絡的應用。該技術的測距精度可以達到厘米級，但受到超聲波信號的限制(超聲波信號傳播距離69米)和非視距問題的影響，網(wǎng)絡需要密集部署，會產(chǎn)生大量運算和通信開銷。，發(fā)射節(jié)點同時發(fā)射射頻信號和超聲波信號兩種信號(射頻信號的發(fā)射時間為，超聲波信號的發(fā)射時間為，接收節(jié)點記錄的射頻信號的到達時間為，超聲波信號到