王麗俠

（唐山學(xué)院 信息工程系，河北 唐山063000）

1 Dv－h(huán)op算法簡(jiǎn)介

傳感器網(wǎng)絡(luò)中的數(shù)據(jù)采用多跳路由的方式傳送，每一個(gè)節(jié)點(diǎn)只與其鄰居進(jìn)行通信，通過(guò)這種方式，有限的參考節(jié)點(diǎn)能夠被更多的未知節(jié)點(diǎn)利用，從而降低對(duì)參考節(jié)點(diǎn)的依賴。Dv－h(huán)op利用了距離矢量原理，屬于無(wú)需測(cè)距的分布式定位算法［1］。

在Dv－h(huán)op算法中，要實(shí)現(xiàn)最后的定位計(jì)算，每個(gè)未知節(jié)點(diǎn)需要先獲得兩個(gè)基本信息：①不少于3個(gè)參考節(jié)點(diǎn)的坐標(biāo)；②到這些參考節(jié)點(diǎn)的距離。Dv－h(huán)op算法會(huì)將未知節(jié)點(diǎn)到參考節(jié)點(diǎn)之間的距離用網(wǎng)絡(luò)平均每跳距離和兩者之間最短路徑的跳數(shù)乘積表示，因此實(shí)際用于度量距離和參與計(jì)算的最重要的值就是跳數(shù)。在原始的Dv－h(huán)op算法中，除了孤島節(jié)點(diǎn)外（連通度為0的節(jié)點(diǎn)），其余節(jié)點(diǎn)幾乎都能夠獲得網(wǎng)絡(luò)中每一個(gè)參考節(jié)點(diǎn)的信息。利用這大量的冗余信息，絕大部分節(jié)點(diǎn)都能實(shí)現(xiàn)有效的定位，這也是Dv－h(huán)op與其他算法相比的最大優(yōu)勢(shì)。

Dv－h(huán)op算法運(yùn)行過(guò)程如文獻(xiàn)［2］中所述：首先，參考節(jié)點(diǎn)通過(guò)距離矢量協(xié)議，向網(wǎng)絡(luò)中廣播其坐標(biāo)和跳數(shù)信息；然后，參考節(jié)點(diǎn)估計(jì)出所有節(jié)點(diǎn)間單跳的平均距離，任何一個(gè)參考節(jié)點(diǎn)均可向整個(gè)網(wǎng)絡(luò)廣播此距離，將其作為整個(gè)網(wǎng)絡(luò)的修正值；最后，未知節(jié)點(diǎn)就可以利用事先獲得的參考節(jié)點(diǎn)的坐標(biāo)和修正值，通過(guò)三邊計(jì)算等方式完成自身的定位工作。

2 對(duì)Dv－h(huán)op的分析和問(wèn)題的提出

Dv－h(huán)op是目前最典型的多跳定位機(jī)制，它充分利用了有限的參考節(jié)點(diǎn)信息，避免了測(cè)距誤差的引入，簡(jiǎn)單可行，具有很高的實(shí)用性，但是相應(yīng)的，該算法也有不少亟待改進(jìn)的地方（如文獻(xiàn)［3］中所述）。筆者從參考節(jié)點(diǎn)對(duì)精度的影響以及通信量?jī)蓚€(gè)方面，對(duì)Dv－h(huán)op算法的缺陷進(jìn)行分析。該算法具體存在以下兩個(gè)問(wèn)題。

（1）在計(jì)算校正值的階段，距離過(guò)遠(yuǎn)的參考節(jié)點(diǎn)和較近的參考節(jié)點(diǎn)所帶來(lái)的誤差影響是有所不同的，尤其是在具有一定各向異性特點(diǎn)的拓?fù)渲杏葹槊黠@，而Dv－h(huán)op對(duì)全網(wǎng)的所有參考節(jié)點(diǎn)都配以相同的權(quán)重，這往往會(huì)使得到的校值偏小，從而影響最后的坐標(biāo)計(jì)算。

（2）原算法中采用了全網(wǎng)洪泛的方式來(lái)確保每個(gè)節(jié)點(diǎn)都能收到所有參考節(jié)點(diǎn)的信標(biāo)，這樣雖然可以使未知節(jié)點(diǎn)獲得足夠多的參考節(jié)點(diǎn)信息，但是不受控洪泛的方式對(duì)傳感器網(wǎng)絡(luò)來(lái)說(shuō)代價(jià)過(guò)于昂貴，對(duì)于參考節(jié)點(diǎn)數(shù)接近1 000的大規(guī)模網(wǎng)絡(luò)，通信過(guò)程會(huì)帶來(lái)巨大的能耗，使用Dv－h(huán)op算法不可行，這也將這種算法的應(yīng)用范圍限制在了中小型的網(wǎng)絡(luò)。如何在保證未知節(jié)點(diǎn)能獲得足夠的參考節(jié)點(diǎn)信息的前提下降低通信量成了改進(jìn)這種定位算法的最關(guān)鍵問(wèn)題。

3 逐級(jí)分區(qū)和加權(quán)定位算法

下面將針對(duì)Dv－h(huán)op算法存在的兩個(gè)問(wèn)題，提出一種新的定位算法，引入逐級(jí)分區(qū)概念和加權(quán)計(jì)算，與文獻(xiàn)［4］思路類似，首先通過(guò)對(duì)網(wǎng)絡(luò)中的所有參考節(jié)點(diǎn)進(jìn)行分級(jí)，按逐漸縮小本地范圍的方式進(jìn)行信標(biāo)洪泛，以達(dá)到既能使節(jié)點(diǎn)獲得足夠參考節(jié)點(diǎn)信標(biāo)，又能極大降低網(wǎng)絡(luò)通信量的目的；其次在校正值的計(jì)算和傳播階段，通過(guò)對(duì)不同參考節(jié)點(diǎn)加權(quán)并合理選擇參考節(jié)點(diǎn)進(jìn)行坐標(biāo)計(jì)算，來(lái)減小最終的定位誤差。

3.1 參考節(jié)點(diǎn)信標(biāo)的逐級(jí)分區(qū)洪泛

逐級(jí)分區(qū)主要是對(duì)參考節(jié)點(diǎn)進(jìn)行分級(jí)，并通過(guò)各級(jí)分別洪泛來(lái)限制洪泛的范圍，因此，改進(jìn)后的算法可適用于大規(guī)模的傳感器網(wǎng)絡(luò)。算法開(kāi)始運(yùn)行之前，所有參考節(jié)點(diǎn)b和未知節(jié)點(diǎn)u隨機(jī)分布，參考節(jié)點(diǎn)事先劃分為幾個(gè)級(jí)別，劃分的值與參考節(jié)點(diǎn)的ID沒(méi)有關(guān)聯(lián)，采取隨機(jī)劃分或指定。

算法的實(shí)現(xiàn)采用一個(gè)通用的信息包結(jié)構(gòu)：UNI＿M(jìn)ESSAGE，在所有節(jié)點(diǎn)通信中都發(fā)送這樣的數(shù)據(jù)包，包含發(fā)送節(jié)點(diǎn)的ID號(hào)、級(jí)別、坐標(biāo)、校正值（hopsize）和跳數(shù)；消息以結(jié)構(gòu)體實(shí)現(xiàn)，以omnet的消息類進(jìn)行封裝，字段定義如圖1所示。

圖1 消息體UNI＿M(jìn)ESSAGE字段定義

分區(qū)算法分為4個(gè)步驟：

（1）首先，第一級(jí)的節(jié)點(diǎn)向鄰居廣播自己的信標(biāo)。和在Dv－h(huán)op算法中一樣，這個(gè)過(guò)程通過(guò)距離矢量的方式進(jìn)行洪泛，所有節(jié)點(diǎn)記錄下收到的信標(biāo)中的坐標(biāo)位置、ID號(hào)、Hops字段值，然后將Hops加1轉(zhuǎn)發(fā)給自己的鄰居節(jié)點(diǎn)。

（2）收到了第一級(jí)參考節(jié)點(diǎn)的信標(biāo)后，未知節(jié)點(diǎn)記錄下數(shù)據(jù)包中的ID號(hào)和坐標(biāo)；同時(shí)，收到信標(biāo)的每一個(gè)節(jié)點(diǎn)包括其他參考節(jié)點(diǎn)，都計(jì)算出一個(gè)自己所屬的區(qū)域，這個(gè)區(qū)域的序號(hào)即是它所收到的信標(biāo)中跳數(shù)值（Hops字段）最小的那個(gè)參考節(jié)點(diǎn)的ID號(hào)，如果有兩個(gè)或兩個(gè)以上信標(biāo)中的跳數(shù)值相同，則取最先收到的一個(gè)。這樣形成的結(jié)果就是，第一級(jí)的參考節(jié)點(diǎn)在它的附近一定范圍內(nèi)，劃分出了一個(gè)以自己的ID號(hào)為序號(hào)的“虛擬”本地區(qū)域，這幾個(gè)區(qū)域也是對(duì)全局的一個(gè)完整劃分。

（3）從第二級(jí)的參考節(jié)點(diǎn)開(kāi)始，均設(shè)置計(jì)時(shí)器，以收到上一級(jí)的信標(biāo)起開(kāi)始計(jì)時(shí)，當(dāng)計(jì)時(shí)器溢出后，即認(rèn)為上級(jí)節(jié)點(diǎn)的洪泛已經(jīng)結(jié)束，然后開(kāi)始自己的洪泛。第二級(jí)開(kāi)始的參考節(jié)點(diǎn)在發(fā)送信標(biāo)前，先根據(jù)前面收到的所有參考節(jié)點(diǎn)的信息（坐標(biāo)值、跳數(shù)）計(jì)算校正值（與原算法不同，新校正值的計(jì)算方式在3.2節(jié)闡述），然后將計(jì)算出的校正值置入 UNI＿M(jìn)ESSAGE的hopsize字段，以“捎帶”的方式與它的信標(biāo)一起發(fā)送出去。與前一級(jí)參考節(jié)點(diǎn)不同，后一級(jí)參考節(jié)點(diǎn)信標(biāo)的洪泛范圍將被限制在它當(dāng)時(shí)所處的區(qū)域內(nèi)部，這也是算法能保證通信量大幅降低的關(guān)鍵。

對(duì)于來(lái)自同一區(qū)域的信標(biāo)，判斷是否需要更新自己當(dāng)前所處區(qū)域的依據(jù)是：如果當(dāng)前保存的Region＿h(yuǎn)op值大于新參考節(jié)點(diǎn)到自己的跳數(shù)，就執(zhí)行更新，然后將Region更新為新收到的參考節(jié)點(diǎn)ID。這樣，新的參考節(jié)點(diǎn)就在它原來(lái)所屬區(qū)域里面劃分出了一個(gè)子區(qū)域。這個(gè)過(guò)程重復(fù)執(zhí)行，直到各級(jí)的洪泛全部完成。最后的結(jié)果是，如果網(wǎng)絡(luò)中分布了n個(gè)參考節(jié)點(diǎn)，網(wǎng)絡(luò)將被劃分為n個(gè)子區(qū)域，每個(gè)區(qū)域逐漸縮小，并且以一個(gè)相應(yīng)的參考節(jié)點(diǎn)為中心。

（4）洪泛全部結(jié)束后，參考節(jié)點(diǎn)已經(jīng)將信標(biāo)和校正值廣播到了網(wǎng)絡(luò)中，未知節(jié)點(diǎn)在一段時(shí)間沒(méi)有收到信標(biāo)后，計(jì)時(shí)溢出，并開(kāi)始坐標(biāo)計(jì)算：首先將收到的校正值進(jìn)行計(jì)算，得到最終的校正值，并選取參考節(jié)點(diǎn)，通過(guò)公式dn≈hopsizen×Hn將跳數(shù)距離轉(zhuǎn)換為估計(jì)距離，然后采用三邊計(jì)算或最大似然估計(jì)法求得坐標(biāo)值。

3.2 基于權(quán)重的校正值計(jì)算和傳播

在校正值的計(jì)算過(guò)程中應(yīng)該考慮到參考節(jié)點(diǎn)的距離遠(yuǎn)近問(wèn)題，對(duì)于過(guò)遠(yuǎn)的節(jié)點(diǎn)，在校正值的計(jì)算中要進(jìn)行修正，配以較小的權(quán)重加以限制，使跳距過(guò)遠(yuǎn)的參考節(jié)點(diǎn)對(duì)校正值的影響迅速減小。

在3.1節(jié)分區(qū)算法步驟（3）中所述，從第二級(jí)的參考節(jié)點(diǎn)開(kāi)始計(jì)算校正值，并且以“捎帶”的方式將校正值隨信標(biāo)一起發(fā)送。假設(shè)第i個(gè)參考節(jié)點(diǎn)計(jì)時(shí)溢出后（Time＿up函數(shù)返回true）在其參考節(jié)點(diǎn)鏈表anchor＿list中有j個(gè)上級(jí)節(jié)點(diǎn)的信標(biāo)，相應(yīng)的跳數(shù)值分別為 Hij，相應(yīng)坐標(biāo)表示為（Xj，Yj），校正值hopsizei的計(jì)算公式為：

Hin為參考節(jié)點(diǎn)n到i的跳數(shù)。通過(guò)這種改進(jìn)的校正值計(jì)算方式，可以提供更符合實(shí)際的校正值，從而提高最終的節(jié)點(diǎn)定位精度。

在新算法中，參考節(jié)點(diǎn)的信標(biāo)和校正值是放在同一個(gè)數(shù)據(jù)包UNI＿M(jìn)ESSAGE里一起洪泛到網(wǎng)絡(luò)中的，所以不存在第二次通信開(kāi)銷的問(wèn)題，另外，當(dāng)未知節(jié)點(diǎn)收到第一個(gè)校正值時(shí)，發(fā)出這個(gè)值的參考節(jié)點(diǎn)必然與它處于同一個(gè)子區(qū)域內(nèi)（即一級(jí)節(jié)點(diǎn)劃分的區(qū)域），后續(xù)節(jié)點(diǎn)也是如此，而且會(huì)逐漸靠近收到該值的未知節(jié)點(diǎn)，所以此算法可以確保校正值均來(lái)自未知節(jié)點(diǎn)附近。在本算法中，未知節(jié)點(diǎn)會(huì)接收到多個(gè)來(lái)自附近的校正值，最后通過(guò)取平均的方式進(jìn)行處理，以充分利用這些冗余信息：hopsize＝，hopsize即未知節(jié)點(diǎn)用來(lái)估算到參考節(jié)點(diǎn)距離的校正值，n為節(jié)點(diǎn)最終收到的校正值數(shù)目。通過(guò)將校正值取平均，避免了因某個(gè)參考節(jié)點(diǎn)的值出現(xiàn)嚴(yán)重失真帶來(lái)的影響。

3.3 參考節(jié)點(diǎn)的選取

新算法中，在坐標(biāo)值計(jì)算方面，采取不同的策略：洪泛完成之后，節(jié)點(diǎn)首先在一級(jí)參考節(jié)點(diǎn)當(dāng)中排除自己所屬區(qū)域以外的其他幾個(gè)節(jié)點(diǎn)，利用所有剩下的節(jié)點(diǎn)信標(biāo)計(jì)算其坐標(biāo)值；如果剩下的信標(biāo)總數(shù)小于等于3，再在排除的參考節(jié)點(diǎn)中依照跳數(shù)值，按從小到大的順序選擇其他參考節(jié)點(diǎn)，直到信標(biāo)數(shù)大于3為止。這樣做可以保證定位計(jì)算只基于本地網(wǎng)絡(luò)拓?fù)?，目的同樣是避免網(wǎng)絡(luò)的非均勻性對(duì)坐標(biāo)計(jì)算帶來(lái)的影響，而且一級(jí)節(jié)點(diǎn)數(shù)目越多，用于坐標(biāo)計(jì)算的參考節(jié)點(diǎn)離得越近，網(wǎng)絡(luò)的不均勻性帶來(lái)的影響也就越小。

4 定位算法的仿真驗(yàn)證與分析

分區(qū)加權(quán)算法主要針對(duì)定位精度和通信開(kāi)銷問(wèn)題進(jìn)行了改進(jìn)。下面在OMNet＋＋和Matlab組成的環(huán)境下，對(duì)算法的相對(duì)定位誤差、通信量，以及在各向異性拓?fù)湎碌男阅苓M(jìn)行對(duì)比仿真。

4.1 定位精度

為了檢驗(yàn)算法的定位精度，采用隨機(jī)分布的網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真，參考節(jié)點(diǎn)的分級(jí)均采用3.1中的劃分方式，一級(jí)節(jié)點(diǎn)都為4個(gè)。下面各圖中每一個(gè)數(shù)據(jù)點(diǎn)是在相同參數(shù)下5次仿真的平均值。

圖2為Dv－h(huán)op算法和改進(jìn)算法的定位誤差曲線，參考節(jié)點(diǎn)的比例從5%到30%。從圖中可以看到，在參考節(jié)點(diǎn)僅為5%時(shí)，改進(jìn)算法的定位精度不如Dv－h(huán)op算法，平均相對(duì)誤差達(dá)到了140%以上；參考節(jié)點(diǎn)多于10%時(shí)，改進(jìn)算法的誤差明顯小于Dv－h(huán)op算法，且相對(duì)誤差隨參考節(jié)點(diǎn)增加而下降的趨勢(shì)略快于Dv－h(huán)op算法；在參考節(jié)點(diǎn)取15%時(shí)，其誤差平均值為47．9%。圖2表明，根據(jù)參考節(jié)點(diǎn)的跳數(shù)遠(yuǎn)近決定其權(quán)重的大小來(lái)計(jì)算校正值的方式，明顯改善了節(jié)點(diǎn)定位的精度。

圖2 不同參考節(jié)點(diǎn)比例下的定位精度比較

4.2 通信量

對(duì)分區(qū)加權(quán)算法通信開(kāi)銷的仿真分兩步，首先要驗(yàn)證通信量與參考節(jié)點(diǎn)的關(guān)系。圖3中上面為Dv－h(huán)op的通信量曲線，虛線為其理論值；下面為分區(qū)加權(quán)算法通信量，虛線是其理論值。由仿真可見(jiàn)，Dv－h(huán)op中總節(jié)點(diǎn)數(shù)不變，參考節(jié)點(diǎn)從5%到30%變化時(shí)，通信量呈線性增加，增幅較大。

圖3 不同參考節(jié)點(diǎn)比例下的通信量

圖4為不同節(jié)點(diǎn)總數(shù)時(shí)的通信量曲線，參考節(jié)點(diǎn)比例固定為15%，節(jié)點(diǎn)每增加100，分布區(qū)域相應(yīng)增加100，其他參數(shù)與前面相同，仿真次數(shù)均為1次。對(duì)于Dv－h(huán)op算法，其理論通信量計(jì)算為pn2＋n，p為參考節(jié)點(diǎn)比例。從仿真結(jié)果可以看到，其實(shí)際的通信量基本呈指數(shù)級(jí)增加；而分區(qū)加權(quán)算法中，通信量與理論值相近，呈對(duì)數(shù)特性，增加非常緩慢，在網(wǎng)絡(luò)達(dá)到1 000個(gè)節(jié)點(diǎn)時(shí)，發(fā)送包數(shù)仍然小于10 000，而Dvhop算法的相應(yīng)值卻是它的14倍。

4.3 各向異性拓?fù)湎碌膶?duì)比仿真

由于分區(qū)加權(quán)方式的采用，算法對(duì)網(wǎng)絡(luò)拓?fù)涞囊蕾囆员菵v－h(huán)op算法要小?，F(xiàn)對(duì)一個(gè)“C”形的網(wǎng)絡(luò)進(jìn)行仿真，其代表了各向異性網(wǎng)絡(luò)拓?fù)洹D5為對(duì)網(wǎng)絡(luò)取不同的參考節(jié)點(diǎn)比例時(shí)，分別運(yùn)行Dv－h(huán)op算法和分區(qū)加權(quán)算法得到的定位精度曲線圖。最上面為Dv－h(huán)op算法的誤差曲線，其相對(duì)誤差都在110%以上，平均誤差值為138．6%，并且沒(méi)有隨參考節(jié)點(diǎn)增加而降低?？梢?jiàn)Dv－h(huán)op算法的確僅適用于各向同性網(wǎng)絡(luò)拓?fù)洌?］，在“C”形網(wǎng)絡(luò)結(jié)構(gòu)中，拓?fù)涑拭黠@的各向異性，“空洞”效應(yīng)在這里非常明顯。中間的曲線為分區(qū)加權(quán)算法，一級(jí)節(jié)點(diǎn)數(shù)目為4時(shí)的結(jié)果，在所有參考節(jié)點(diǎn)比例下，定位精度都有明顯的提高。最下邊一條曲線為一級(jí)節(jié)點(diǎn)數(shù)目為6時(shí)的結(jié)果，即按照6，6，12，24…的方式劃分，可以看到，在這種情況下，當(dāng)參考節(jié)點(diǎn)比例增加到20%時(shí)，定位精度有非常明顯的提高，其相對(duì)誤差降低到了53．2%，與Dv－h(huán)op算法在各向同性網(wǎng)絡(luò)中的性能相近。但圖中曲線也同時(shí)表明，要在這種完全各向異性的拓?fù)渲腥〉幂^高的定位精度，需要更高的參考節(jié)點(diǎn)比例。

圖4 不同節(jié)點(diǎn)總數(shù)下的通信量（15%Anchor）

圖5 “C”形網(wǎng)絡(luò)的定位精度

5 仿真總結(jié)

以上的仿真實(shí)驗(yàn)表明，在節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)中，分區(qū)加權(quán)算法的定位精度優(yōu)于Dv－h(huán)op算法，更關(guān)鍵的是，它極大地降低了定位過(guò)程中的通信開(kāi)銷，因此從這個(gè)方面講，它能夠應(yīng)用于節(jié)點(diǎn)數(shù)目較多的大規(guī)模傳感器網(wǎng)絡(luò)，是對(duì)Dv－h(huán)op算法的有效擴(kuò)展。另外，在各向異性網(wǎng)絡(luò)中，分區(qū)加權(quán)算法的定位精度與Dv－h(huán)op算法相比有非常明顯的提高，在仿真中采用的“C”形網(wǎng)絡(luò)，當(dāng)參考節(jié)點(diǎn)數(shù)目達(dá)到20%以上時(shí)，其定位相對(duì)誤差降低到了53．2%。

［1］ 張品，孫巖．一種新的無(wú)線傳感器網(wǎng)絡(luò)DV－Hop算法［J］．電子器件，2010，33（1）：117－120．

［2］ Niculescu D，Nath B．DV based positioning in Ad Hoc networks［J］．Telecommunication Systems，2003，22（1－4）：267－280．

［3］ 石為人，賈傳江，梁煥煥．一種改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)DV－Hop定位算法［J］．傳感技術(shù)學(xué)報(bào)，2011，24（1）：83－87．

［4］ 戴瑩，王建平，張崇?。疅o(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研 究 與 改 進(jìn) ［J］．傳 感 技 術(shù) 學(xué) 報(bào)，2010，23（4）：567－570．

［5］ 衛(wèi)開(kāi)夏，田金鵬，王克謙．無(wú)線傳感器網(wǎng)絡(luò)DV－Hop定位 改 進(jìn) 算 法 ［J］．傳 感 技 術(shù) 學(xué) 報(bào)，2010，23（12）：1820－1824．