基于迭代協(xié)作的改進(jìn)DV-Hop定位算法

新華社音視頻部 邰劍秋

介紹

在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)準(zhǔn)確地進(jìn)行自身定位對(duì)其有效性起著關(guān)鍵的作用。為了適應(yīng)無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)低能耗的特性要求，充分利用節(jié)點(diǎn)資源，在節(jié)點(diǎn)定位中引入?yún)f(xié)作技術(shù)，以獲得更高定位的性能，即協(xié)作定位[1]。

對(duì)于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法主要可以分為兩大類：基于測(cè)距的定位算法和無需測(cè)距的定位算法。測(cè)距技術(shù)主要包括基于TOA的定位、基于TDOA的定位、基于AOA的定位、基于RSSI的定位等[1][2]。無需測(cè)距的算法主要包括以下幾種：質(zhì)心算法[3]、APIT算法[4]、MDS-MAP算法[5]、DV-Hop算法[6]等。上述算法中，DV-Hop算法具有方法簡(jiǎn)單、定位精度較高等優(yōu)點(diǎn)，但其定位性能受節(jié)點(diǎn)分布影響大，僅在密集網(wǎng)絡(luò)中，才能達(dá)到較高定位精度，當(dāng)網(wǎng)絡(luò)拓?fù)洳灰?guī)則時(shí)，定位誤差較大。

文獻(xiàn)[7]通過加入接收信號(hào)強(qiáng)度指示器（RSSI）測(cè)距模塊輔助定位，對(duì)算法進(jìn)行改進(jìn)，提高了定位精度和系統(tǒng)穩(wěn)定性。但是需要增加額外的測(cè)距模塊，使硬件復(fù)雜度增大，有悖于無需測(cè)距算法簡(jiǎn)單易行、成本低的特點(diǎn)。文獻(xiàn)[8]提出了一種選擇邊界錨節(jié)點(diǎn)的算法，通過減少參與洪泛的錨節(jié)點(diǎn)個(gè)數(shù)來減少能量消耗，但是該方法對(duì)定位精度改善甚小，且網(wǎng)絡(luò)拓?fù)湎∈?、信?biāo)節(jié)點(diǎn)較少或分布不規(guī)則時(shí)，對(duì)算法性能影響較大。文獻(xiàn)[9]從獲得跳數(shù)的方法上對(duì)DV-Hop算法進(jìn)行改進(jìn)，利用節(jié)點(diǎn)接收到的信號(hào)能量對(duì)節(jié)點(diǎn)間跳數(shù)進(jìn)行量化。文獻(xiàn)[10]利用節(jié)點(diǎn)與其鄰近節(jié)點(diǎn)間的測(cè)量距離優(yōu)化定位性能，但其定位精度主要依賴于求精階段節(jié)點(diǎn)間距離測(cè)量的精度，當(dāng)距離誤差較大時(shí)，定位誤差反而增大。同時(shí)，[9][10]還分別需要得到能量和待測(cè)節(jié)點(diǎn)間距離等額外信息，使通信開銷和硬件復(fù)雜度增大。文獻(xiàn)[11]從求平均每跳距離、校正值的選取上對(duì)算法作改進(jìn)，且引入未知節(jié)點(diǎn)到參考節(jié)點(diǎn)的距離作為節(jié)點(diǎn)定位的約束條件，提高了定位性能且節(jié)約了成本。但是，由于DV-Hop算法使用跳段距離代替實(shí)際距離來估算未知節(jié)點(diǎn)的定位坐標(biāo)，跳數(shù)越大則誤差越大。且定位精度還受節(jié)點(diǎn)拓?fù)潢P(guān)系影響，當(dāng)信標(biāo)節(jié)點(diǎn)位置近似于一直線時(shí)，定位誤差較大。同時(shí)，傳統(tǒng)的DV-Hop定位算法覆蓋范圍還受到信標(biāo)節(jié)點(diǎn)個(gè)數(shù)的限制，即當(dāng)信標(biāo)節(jié)點(diǎn)較少時(shí)，將有很大一部分未知節(jié)點(diǎn)無法實(shí)現(xiàn)定位。

本文針對(duì)以上問題，提出了一種優(yōu)化的DV-Hop定位算法，即ICDV-Hop算法。通過設(shè)置跳數(shù)門限來控制節(jié)點(diǎn)間的距離誤差，并且利用共線度測(cè)試對(duì)信標(biāo)節(jié)點(diǎn)之間、信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間的幾何位置關(guān)系加以約束，以選擇最優(yōu)的信標(biāo)三角形來降低定位誤差，并引進(jìn)了迭代協(xié)作[12]增加定位覆蓋。該算法使用3個(gè)信標(biāo)對(duì)未知節(jié)點(diǎn)進(jìn)行位置估計(jì)，有效降低了定位時(shí)的計(jì)算能耗。仿真結(jié)果表明，ICDV-Hop算法的平均誤差和定位覆蓋均有明顯改善，表現(xiàn)出良好的可靠性，并且有更好的穩(wěn)定性和魯棒性。

系統(tǒng)模型

DV-Hop算法整個(gè)定位過程不依賴于昂貴的測(cè)距方法，利用了多跳信標(biāo)節(jié)點(diǎn)信息來參與節(jié)點(diǎn)定位，使其定位覆蓋率大大提高。其主要思想是采用跳段距離之和代替實(shí)際距離。整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)如圖1，實(shí)線為跳段，說明相應(yīng)節(jié)點(diǎn)間可以實(shí)現(xiàn)通信。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

圖中B1, B2, B3, B4為信標(biāo)節(jié)點(diǎn)(Beacon)，其余為未知節(jié)點(diǎn)。X1, X2代表剩余節(jié)點(diǎn)，即無法實(shí)現(xiàn)位置估計(jì)的節(jié)點(diǎn)。

傳統(tǒng)DV-Hop算法由三個(gè)階段組成。第1階段，使用典型的距離矢量交換協(xié)議，通過節(jié)點(diǎn)間的信息交換，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得與信標(biāo)節(jié)點(diǎn)間的跳數(shù)。如圖1中，節(jié)點(diǎn)A獲得與信標(biāo)節(jié)點(diǎn)B1、B2、B3、B4間的跳數(shù)分別為3、2、3、2.第2階段，在獲得其他信標(biāo)節(jié)點(diǎn)的位置信息和條數(shù)信息后，信標(biāo)節(jié)點(diǎn)計(jì)算節(jié)點(diǎn)間的平均每跳距離，并將其作為一個(gè)校正值（correction）廣播至網(wǎng)絡(luò)中。未知節(jié)點(diǎn)利用校正值和記錄的跳數(shù)計(jì)算與各信標(biāo)節(jié)點(diǎn)的距離。第3階段，根據(jù)未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的距離和信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)，利用多邊測(cè)量或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)坐標(biāo)。

ICDV-hop算法

由于DV-Hop算法節(jié)點(diǎn)間的距離由平均每跳距離與跳數(shù)相乘求得，如圖1所示，定位精度主要由平均每跳距離的精度決定，而跳數(shù)越大估計(jì)得到的平均每跳距離越不準(zhǔn)確，導(dǎo)致節(jié)點(diǎn)間距離誤差過大，最終影響定位精度；定位精度受到節(jié)點(diǎn)間位置關(guān)系影響，當(dāng)用于定位的信標(biāo)節(jié)點(diǎn)處于同一直線時(shí)，定位誤差較大；定位覆蓋范圍受到信標(biāo)節(jié)點(diǎn)個(gè)數(shù)的限制，而實(shí)際網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)往往較少，導(dǎo)致較多未知節(jié)點(diǎn)無法實(shí)現(xiàn)定位。因此本文針對(duì)以上三點(diǎn)對(duì)DV-hop算法作出改進(jìn)，ICDV-Hop算法主要由5個(gè)步驟組成：

1. 通過節(jié)點(diǎn)間信息交換，獲得未知節(jié)點(diǎn)與跳數(shù)門限內(nèi)信標(biāo)節(jié)點(diǎn)的跳數(shù)信息；

2. 根據(jù)信標(biāo)節(jié)點(diǎn)校正值與跳數(shù)信息計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離；

3. 進(jìn)行信標(biāo)節(jié)點(diǎn)共線度測(cè)試，選擇最優(yōu)的信標(biāo)三角形；

4. 未知節(jié)點(diǎn)利用信標(biāo)三角形進(jìn)行位置估計(jì)；

5. 判斷每個(gè)已定位節(jié)點(diǎn)的定位誤差，若其小于設(shè)定的閾值，則轉(zhuǎn)化成信標(biāo)節(jié)點(diǎn)；

6. 重復(fù)第1-4步對(duì)剩余的未知節(jié)點(diǎn)進(jìn)行定位，直至沒有新的信標(biāo)節(jié)點(diǎn)產(chǎn)生。

3.1 未知節(jié)點(diǎn)獲得跳數(shù)信息

通過節(jié)點(diǎn)間的信息交換，能使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)。但由于DV-Hop算法采用跳段距離之和代替實(shí)際距離，跳段數(shù)增加將使累計(jì)誤差增大，所以一般情況下，未知節(jié)點(diǎn)若只接收距離較近的局部范圍內(nèi)的信標(biāo)節(jié)點(diǎn)信息，將會(huì)減少這種累計(jì)誤差的疊加，提高定位精度并從整體上降低網(wǎng)絡(luò)通信量。因此，我們?cè)O(shè)置一個(gè)跳數(shù)門限N，限制未知節(jié)點(diǎn)接收大于此門限跳數(shù)的信標(biāo)節(jié)點(diǎn)信息。

如圖1所示，信標(biāo)節(jié)點(diǎn)Bi向鄰居節(jié)點(diǎn)廣播自身位置信息，包括跳數(shù)字段(Hops)、坐標(biāo)值和ID號(hào)。當(dāng)未知節(jié)點(diǎn)與信標(biāo)存在不同路徑時(shí)，選取最小的跳數(shù)值計(jì)算。未知節(jié)點(diǎn)收到某一信標(biāo)節(jié)點(diǎn)的跳數(shù)值后，將其與門限N比較，若小于門限N，節(jié)點(diǎn)將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，否則丟棄此分組。

門限N與節(jié)點(diǎn)傳播半徑、網(wǎng)絡(luò)區(qū)域面積和信標(biāo)節(jié)點(diǎn)個(gè)數(shù)有關(guān)?？梢愿鶕?jù)(1)式計(jì)算N值

其中，area為正方形網(wǎng)絡(luò)的邊長(zhǎng)，R為節(jié)點(diǎn)傳播半徑，BeaconAmount為信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)，m為每個(gè)未知節(jié)點(diǎn)定位需要的信標(biāo)數(shù)。

3.2 計(jì)算跳距

利用跳數(shù)和平均每跳距離，計(jì)算未知節(jié)點(diǎn)與限定跳數(shù)內(nèi)的信標(biāo)節(jié)點(diǎn)的距離。

首先計(jì)算每個(gè)信標(biāo)節(jié)點(diǎn)的校正值。設(shè)信標(biāo)節(jié)點(diǎn)共有k個(gè)，位置信息坐標(biāo)為(xi, yi) (i=1,2,…,k)，每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)記錄的與其它信標(biāo)節(jié)點(diǎn)的位置信息和相距跳數(shù)，估算如圖1所示的平均每跳距離HopSize，即每個(gè)信標(biāo)的校正值。信標(biāo)間的距離為

其中h i , j是對(duì)應(yīng)信標(biāo)節(jié)點(diǎn)間的跳數(shù)值。

信標(biāo)節(jié)點(diǎn)得到自身校正值后，將其作為一個(gè)跳距校正值(correction)廣播至網(wǎng)絡(luò)中。未知節(jié)點(diǎn)僅記錄收到的第一個(gè)校正值作為平均每跳距離或跳段數(shù)最小的作為平均每跳距離。使用這種方法可以使未知節(jié)點(diǎn)從最近的信標(biāo)接收校正值。未知節(jié)點(diǎn)獲得該校正值后，根據(jù)(4)式計(jì)算第n個(gè)未知節(jié)點(diǎn)到各信標(biāo)節(jié)點(diǎn)的距離：

其中cn為未知節(jié)點(diǎn)n接收到的校正值，hn , j為未知節(jié)點(diǎn)n與信標(biāo)節(jié)點(diǎn)j間的跳數(shù)。

3.3 信標(biāo)三角形的選擇

傳統(tǒng)算法中，與未知節(jié)點(diǎn)通信的信標(biāo)達(dá)到三個(gè)時(shí)，即可實(shí)現(xiàn)位置估計(jì)。然而當(dāng)信標(biāo)節(jié)點(diǎn)接近于同一直線時(shí)，會(huì)導(dǎo)致較大的位置估計(jì)誤差。因此將信標(biāo)節(jié)點(diǎn)的位置關(guān)系引入到ICDV-Hop算法中，提出共線度概念，如圖2所示。

圖2 共線度

其中，設(shè)平面上任意三點(diǎn)所形成的三角形中最長(zhǎng)邊的邊長(zhǎng)為lmax，該邊所對(duì)應(yīng)的高即為hmin，定義hmin與lmax的比值為該三角形的共線度，用DC表示為：

共線度的取值范圍為[0,1]，共線度值越小表示3個(gè)點(diǎn)越接近共線，而當(dāng)三點(diǎn)完全共線時(shí)，三角形退化，此時(shí)的共線度為0。在實(shí)際的信標(biāo)節(jié)點(diǎn)選擇過程中，可以通過設(shè)定某一閾值來約束信標(biāo)節(jié)點(diǎn)之間的拓?fù)潢P(guān)系，即DC< thre_c。其中thre_c為設(shè)置的共線度閾值。

盡管通過信標(biāo)節(jié)點(diǎn)的坐標(biāo)可以方便地計(jì)算出它們之間的拓?fù)潢P(guān)系，但是僅僅考慮信標(biāo)節(jié)點(diǎn)之間的關(guān)系是不夠的，在未知節(jié)點(diǎn)的位置估算過程中，還需要考慮信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的關(guān)系。圖1中，對(duì)于未知節(jié)點(diǎn)A，若信標(biāo)三角形B1B2B3與B1B3B4共線度相等且最優(yōu)，但A處于三角形B1B2B3中，因此應(yīng)選擇其作為信標(biāo)。

為了約束未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的關(guān)系，需要在設(shè)置共線度閾值時(shí)考慮未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的位置關(guān)系。ICDV-Hop算法通過判斷未知節(jié)點(diǎn)是否在信標(biāo)三角形內(nèi)，選擇合適的信標(biāo)三角形。即先根據(jù)共線度測(cè)試找出所有可用的信標(biāo)三角形組合；接著根據(jù)步驟2中得到的未知節(jié)點(diǎn)到信標(biāo)三角形各頂點(diǎn)的距離和信標(biāo)三角形各邊長(zhǎng)，可以判斷出該未知節(jié)點(diǎn)是否在相應(yīng)的信標(biāo)三角形內(nèi)，找出符合條件的信標(biāo)三角形；若此時(shí)符合條件的組合有多個(gè)，則選取未知節(jié)點(diǎn)到信標(biāo)三角形三個(gè)頂點(diǎn)跳數(shù)和最小的組合，此做法也與步驟1中增加跳數(shù)門限相對(duì)應(yīng)，目的也在于盡可能的減小距離誤差。按照這種規(guī)則，圖1中將選擇使用信標(biāo)B1B2B3來估計(jì)A點(diǎn)位置。

3.4 位置估計(jì)

當(dāng)信標(biāo)節(jié)點(diǎn)通過共線度驗(yàn)證后，進(jìn)行位置估計(jì)。

設(shè)未知節(jié)點(diǎn)A坐標(biāo)為(x, y),可與其通信的所有k個(gè)信標(biāo)節(jié)點(diǎn)的位置信息用(x1, y1), (x2, y2),…,(xk, yk)表示，未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離分別為r1,r2,…,rk,則可建立線性方程組：

其中，

在傳統(tǒng)DV-Hop算法中，未知節(jié)點(diǎn)在實(shí)現(xiàn)自身定位時(shí)使用了所有可以與它通信的信標(biāo)。而由于未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離通過跳數(shù)估計(jì)得出，多個(gè)距離方程構(gòu)成的超定方程組，當(dāng)方程個(gè)數(shù)增加時(shí)，它的解并不一定最接近真實(shí)坐標(biāo)值。相反，當(dāng)跳數(shù)過大時(shí)，用多個(gè)信標(biāo)定位反而有可能造成誤差的擴(kuò)大，且計(jì)算復(fù)雜度增加。而ICDV-Hop算法利用跳數(shù)門限結(jié)合共線度測(cè)試，挑選出最優(yōu)的三個(gè)信標(biāo)節(jié)點(diǎn)組合，有效避免了上述情況，且定位誤差受網(wǎng)絡(luò)拓?fù)溆绊懶?。同時(shí)，改進(jìn)算法只使用三個(gè)信標(biāo)節(jié)點(diǎn)進(jìn)行位置估計(jì)，與傳統(tǒng)算法相比，可以大大節(jié)省定位時(shí)的計(jì)算能耗。

3.5 迭代協(xié)作

信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)直接影響算法定位覆蓋范圍，而實(shí)際網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)往往較少，致使很大一部分未知節(jié)點(diǎn)無法實(shí)現(xiàn)定位。針對(duì)此問題，本文在ICDVHop算法中引入迭代協(xié)作技術(shù)。即對(duì)于收到足夠多信息的節(jié)點(diǎn)，用現(xiàn)有算法直接定位；然后已定位節(jié)點(diǎn)轉(zhuǎn)化為信標(biāo)節(jié)點(diǎn)，并將自己的位置信息廣播出去，剩余節(jié)點(diǎn)可以利用該信息定位。

該方法能有效提高定位覆蓋，使原本不在信標(biāo)節(jié)點(diǎn)傳播范圍內(nèi)的未知節(jié)點(diǎn)也能被定位。但是若定位出的未知節(jié)點(diǎn)位置與實(shí)際位置誤差較大，則在將它轉(zhuǎn)化成信標(biāo)節(jié)點(diǎn)供其他節(jié)點(diǎn)使用并進(jìn)行多次迭代時(shí)會(huì)造成誤差傳播，使整個(gè)網(wǎng)絡(luò)的定位性能受影響。因此本文在將定位出的未知節(jié)點(diǎn)轉(zhuǎn)化成信標(biāo)節(jié)點(diǎn)時(shí)加入一定的限制。即：設(shè)定一個(gè)閾值err_thred，在某未知節(jié)點(diǎn)實(shí)現(xiàn)自身定位后，計(jì)算其歸一化定位誤差，若誤差小于這一閾值，則可轉(zhuǎn)化為信標(biāo)節(jié)點(diǎn)以供下一輪定位，若誤差超過這一閾值，則不轉(zhuǎn)化。

迭代協(xié)作過程如下：

1. 定位出所有收集到足夠信息的未知節(jié)點(diǎn)；

2. 計(jì)算出上一步中每一個(gè)已定位未知節(jié)點(diǎn)的定位誤差，與閾值err_thred比較，將定位誤差小于該值的節(jié)點(diǎn)轉(zhuǎn)化為信標(biāo)節(jié)點(diǎn)，其余不轉(zhuǎn)化；

3. 利用轉(zhuǎn)化的信標(biāo)節(jié)點(diǎn)結(jié)合原有信標(biāo)節(jié)點(diǎn)，重復(fù)1、2對(duì)剩下的未知節(jié)點(diǎn)再次進(jìn)行定位，直至沒有新的信標(biāo)節(jié)點(diǎn)可以轉(zhuǎn)化。

算法仿真

本文基于圖1的系統(tǒng)模型用Matlab軟件對(duì)ICDV-Hop算法進(jìn)行蒙特卡洛仿真。仿真過程中網(wǎng)絡(luò)區(qū)域?yàn)?00m×l00m的矩形區(qū)域，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的坐標(biāo)隨機(jī)產(chǎn)生，隨機(jī)分布。在相同條件下，分別通過改變信標(biāo)節(jié)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)密度、節(jié)點(diǎn)傳播半徑等條件來實(shí)現(xiàn)對(duì)新算法的性能評(píng)估。

本文對(duì)算法的評(píng)估指標(biāo)主要有兩個(gè)：歸一化平均定位誤差err和定位剩余。其中err由節(jié)點(diǎn)平均定位誤差與傳播半徑R的比值得出，即

其中(x0, y0)為節(jié)點(diǎn)實(shí)際位置坐標(biāo)，($x,$y)為估計(jì)坐標(biāo)。定位剩余是指定位完成后無法定位的未知節(jié)點(diǎn)個(gè)數(shù)占未知節(jié)點(diǎn)總個(gè)數(shù)的比例。值得注意的是最終實(shí)驗(yàn)結(jié)果通過將多次仿真的數(shù)據(jù)求平均得到。

圖3、圖4中區(qū)域內(nèi)總節(jié)點(diǎn)數(shù)為150，可見在相同信標(biāo)個(gè)數(shù)條件下，ICDVHop算法與傳統(tǒng)算法相比定位誤差降低了約30%，定位剩余也明顯減少，表現(xiàn)出優(yōu)越的定位性能。圖3中隨著信標(biāo)節(jié)點(diǎn)的增加，定位誤差所受影響較小，并逐漸趨于穩(wěn)定。因?yàn)镈V-Hop算法使用跳段距離代替節(jié)點(diǎn)間的實(shí)際距離進(jìn)行定位估計(jì)，信標(biāo)節(jié)點(diǎn)個(gè)數(shù)增加并不一定能提高定位精度。ICDV-Hop算法只選取3個(gè)信標(biāo)節(jié)點(diǎn)用于最后位置估計(jì)，當(dāng)信標(biāo)節(jié)點(diǎn)個(gè)數(shù)增加到一定程度后，對(duì)所選擇的信標(biāo)三角形的優(yōu)越性影響很小，即定位精度也逐漸趨于穩(wěn)定。

圖3 歸一化平均定位誤差

圖4 剩余節(jié)點(diǎn)比例

圖5、圖6顯示了定位精度與節(jié)點(diǎn)密度的關(guān)系。圖5是保持信標(biāo)節(jié)點(diǎn)個(gè)數(shù)不變（15個(gè)）的情況，改變節(jié)點(diǎn)密度相當(dāng)于只增加未知節(jié)點(diǎn)個(gè)數(shù)；圖6是保持信標(biāo)百分比不變（10%）的情況，改變節(jié)點(diǎn)密度相當(dāng)于信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)均按比例增加。總體上，改進(jìn)算法比原算法有更小的平均定位誤差，尤其是在節(jié)點(diǎn)密度較低即網(wǎng)絡(luò)較稀疏情況下，改進(jìn)程度尤為明顯。在節(jié)點(diǎn)密度為0.01而其他條件均相同的情況下，平均定位誤差減小了約50%。隨著節(jié)點(diǎn)密度的增加，傳統(tǒng)算法和改進(jìn)算法定位精度均隨之改善，因?yàn)楣?jié)點(diǎn)的增加能提高跳段距離估計(jì)精度，從而降低定位誤差。且改進(jìn)算法隨著節(jié)點(diǎn)密度增加其定位誤差相對(duì)穩(wěn)定，表現(xiàn)出良好的魯棒性，這是由于跳數(shù)門限的應(yīng)用限制了未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的條數(shù)，從而減小了節(jié)點(diǎn)密度對(duì)定位性能的影響。

從圖7可以看出，隨著R的增大，傳統(tǒng)算法和改進(jìn)算法定位誤差都隨之減小。而在相同條件下，改進(jìn)算法比傳統(tǒng)算法表現(xiàn)出更優(yōu)越的性能，尤其在R較小時(shí)，定位誤差改進(jìn)程度尤為明顯。因?yàn)樵赗較小的情況下，使用傳統(tǒng)算法定位時(shí)，未知節(jié)點(diǎn)必須通過較多跳數(shù)獲得與信標(biāo)節(jié)點(diǎn)的信息，跳段距離誤差大導(dǎo)致定位誤差過大。而改進(jìn)算法中由于使用了跳數(shù)門限，避免了這種情況。且根據(jù)公式（1），條數(shù)門限N隨著R的增大而減小，限制了節(jié)點(diǎn)通信半徑對(duì)定位精度的影響，因此ICDV-Hop算法具有良好的穩(wěn)定性。

圖5 歸一化平均定位誤差（信標(biāo)不變）

圖6 歸一化平均定位誤差（信標(biāo)10%）

圖7 歸一化平均定位誤差

結(jié)論

DV-Hop算法是一種無需測(cè)距的分布式節(jié)點(diǎn)定位算法，受環(huán)境因素的影響小，且節(jié)點(diǎn)不用附加額外的測(cè)距模塊，因而節(jié)點(diǎn)簡(jiǎn)單、費(fèi)用低、易于實(shí)現(xiàn)，適合大規(guī)模的無線傳感器網(wǎng)絡(luò)應(yīng)用。但是由于未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離用網(wǎng)絡(luò)平均每跳距離和兩者之間跳數(shù)的乘積表示，在密集的規(guī)則布局的網(wǎng)絡(luò)中可以得到合理的平均每跳距離,從而能夠達(dá)到適當(dāng)?shù)亩ㄎ痪?，但在稀疏或不?guī)則的網(wǎng)絡(luò)中精確度不高。

本文針對(duì)無線傳感器網(wǎng)絡(luò)特點(diǎn)和傳統(tǒng)DV-Hop定位算法的局限性，對(duì)其提出了3點(diǎn)改進(jìn)措施。通過設(shè)置跳數(shù)門限來控制節(jié)點(diǎn)間的平均每跳距離誤差；并且利用共線度測(cè)試對(duì)信標(biāo)節(jié)點(diǎn)、信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間的幾何位置關(guān)系加以約束，以選擇最優(yōu)的信標(biāo)三角形來降低定位誤差；引進(jìn)了迭代協(xié)作技術(shù)，將定位誤差小于設(shè)定閾值的已定位節(jié)點(diǎn)轉(zhuǎn)化成信標(biāo)，進(jìn)行多次迭代定位，從而避免誤差傳播并增加定位覆蓋。從分析與仿真結(jié)果可以看出，改進(jìn)算法在平均定位誤差及算法覆蓋等方面比傳統(tǒng)的DV-Hop方法有較大改善，表現(xiàn)出了更加優(yōu)越的性能，在網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)比率較低及網(wǎng)絡(luò)稀疏的情況下，改進(jìn)程度尤為明顯。且改進(jìn)算法性能受網(wǎng)絡(luò)條件影響較小，具有良好的魯棒性。

[1] Patwari N, Ash J N, Kyperountas S,et al. Locating the Nodes: Cooperative localization in wireless sensor networks.IEEE Signal Proccesing Magazine, 2005,22(4):54-89

[2] Della R F, Ardhy W S, Gianluca S, et al. Experimental Activity on Cooperative Mobile Positioning in Indoor Environments. In: IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks. Espoo, Finland: 2007. 1-6[3] Bulusu N, Heidemann J, Estdn D.GPS-less Low-cost Outdoor Localization for Very Small Devices. IEEE Personal Communications, 7(5): 28-34

[4] Tian H, Chengdu H, Blum B M,et al. Range-free Localization Scheme for Large Scales sensors Networks.In: Proceedings of the 9th Annual International Conference on Mobile Networking. New York, USA: 2003.81-95

[5] Shang Y, Ruml W. Improved MDS-based localization. IEEE Computer and Communications Societies, 2004, 4: 2640-2651

[6] Nicolescu D, Nath B. DV based positioning in ad-hoc Telecom.Systems. Telecom. System, 22(1),2003: 267-280

[7] 劉艷文，王福豹，段渭軍等.基于DV—Hop定位算法和RSSI測(cè)距技術(shù)的定位系統(tǒng).計(jì)算機(jī)應(yīng)用，2007，27(3):516-518

[8] 姜山，李建波.一種改進(jìn)的DV-Hop傳感器網(wǎng)絡(luò)定位算法.計(jì)算機(jī)工程與應(yīng)用，2007，43(34): 141-143

[9] Li X, Shi H, Shang Y. A partialrange-aware localization algorithm for ad-hoc wireless sensor networks.In: Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN). Tampa,USA: 2004. 77-83

[10] Savarese C, Rabaey J, Langendoen K. Robust positioning algorithm for distributed ad-hoc wireless sensor networks. In: Proceedings of the USENIX Technical Annual Conference.Monterey, California: 2002. 317-327

[11] 嵇瑋瑋，劉中.DV-Hop 定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究.電子與信息學(xué)報(bào)，2008，30(4):970-974

[12] Savvides A, Han C C, Srivastava M B. Dynamic fine-grained localization in ad-hoc networks of sensors.In: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. New York, USA: 2001. 166-179