WSN中免測(cè)距距離估計(jì)算法的實(shí)現(xiàn)與比較

摘要 在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)定位技術(shù)是保證其他應(yīng)用有效的基本功能，而定位過(guò)程可分為距離估計(jì)和位置計(jì)算兩個(gè)階段。文中就距離估計(jì)階段介紹了Sum-Dist、DV-Hop以及Euclidean算法，并在Matlab中仿真實(shí)現(xiàn)，最后分析比較其結(jié)果表明，各算法在響應(yīng)的環(huán)境中具有良好的表現(xiàn)，和一定的提升空間。
關(guān)鍵詞 無(wú)線傳感器網(wǎng)絡(luò)；距離估計(jì)；Sum-Dist；DV-Hop；Euclidean

    無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)的出現(xiàn)對(duì)于許多應(yīng)用領(lǐng)域都具有重要意義，因此，其吸引了越來(lái)越多的研究者。近年來(lái)，微電子、無(wú)線通信和計(jì)算等技術(shù)的進(jìn)步推動(dòng)了傳感器的快速發(fā)展，使得已經(jīng)在體積和短距離通信方面有優(yōu)勢(shì)的傳感器又向低成本、低功耗和多功能方面發(fā)展并逐漸成熟，并引起國(guó)際學(xué)術(shù)界和工業(yè)界的重視，被認(rèn)為是對(duì)21世紀(jì)產(chǎn)生巨大影響力的技術(shù)之一。
    無(wú)線傳感器節(jié)點(diǎn)在部署時(shí)往往是不可控制的，如在大型無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)通常被撒播在廣泛的區(qū)域之中，而其中大部分節(jié)點(diǎn)的位置不能事先確定。然而，無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的位置信息對(duì)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)活動(dòng)尤為重要，沒(méi)有位置信息的監(jiān)測(cè)消息是毫無(wú)意義的。對(duì)于一些突發(fā)事件，事件監(jiān)測(cè)到之后所關(guān)心的一個(gè)重要問(wèn)題就是事件發(fā)生的位置信息。如需要告知火災(zāi)的發(fā)生地點(diǎn)、戰(zhàn)場(chǎng)上車輛運(yùn)動(dòng)的區(qū)域、天然氣管道泄漏的具體地點(diǎn)等；又如在環(huán)境監(jiān)測(cè)應(yīng)用中，需要獲取采集信息所對(duì)應(yīng)的物理位置。
    因此，節(jié)點(diǎn)的定位問(wèn)題已成為無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要研究方向。傳感器節(jié)點(diǎn)的自身定位是一種通過(guò)估計(jì)距鄰居節(jié)點(diǎn)的距離或鄰居數(shù)目，并利用節(jié)點(diǎn)間的信息交換來(lái)確定各節(jié)點(diǎn)自身位置的機(jī)制。無(wú)線傳感器網(wǎng)絡(luò)中，根據(jù)定位過(guò)程中是否實(shí)際測(cè)量節(jié)點(diǎn)間的距離，把定位機(jī)制分為：基于測(cè)距的(Range-based)定位和距離無(wú)關(guān)的(Range-free)定位方法。
    由于無(wú)線傳感網(wǎng)絡(luò)不同于傳統(tǒng)網(wǎng)絡(luò)，其能源有限，節(jié)點(diǎn)的通信能力、計(jì)算能力相對(duì)較弱，而節(jié)點(diǎn)數(shù)量較多，導(dǎo)致其定位算法必須考慮能源有效性、生命周期、通信延遲、感知精度、可擴(kuò)展性、魯棒性等指標(biāo)。而Range-free算法則僅利用節(jié)點(diǎn)間距離的關(guān)聯(lián)關(guān)系來(lái)計(jì)算目標(biāo)節(jié)點(diǎn)位置。定位精度較Range-based算法稍差，但由于其降低了對(duì)節(jié)點(diǎn)硬件的要求，相對(duì)更適于無(wú)線傳感器網(wǎng)絡(luò)中的定位。典型算法有：DV-Hop、
Sum-Dist、Euclidean等。這些定位算法都需要經(jīng)過(guò)如圖1所示的定位過(guò)程：

1 免測(cè)距距離估計(jì)算法
1．1 Sum-Dist算法
    Sum-Dist算法是距離估計(jì)算法中較簡(jiǎn)單的方法，其主要思想是將網(wǎng)絡(luò)泛洪過(guò)程中的每跳距離相加，以此作為兩個(gè)節(jié)點(diǎn)間的距離。從錨節(jié)點(diǎn)開(kāi)始，該錨節(jié)點(diǎn)會(huì)廣播一條包含自身標(biāo)志、位置信息、并將路徑長(zhǎng)度置為0的消息。每個(gè)接收該消息的節(jié)點(diǎn)都會(huì)將測(cè)量距離加到路徑長(zhǎng)度上，并在泛洪限制許可的情況下，將該消息再次在網(wǎng)絡(luò)中廣播。如果關(guān)于同一個(gè)錨節(jié)點(diǎn)的消息兩次或多次廣播至未知節(jié)點(diǎn)，即僅在當(dāng)前路徑長(zhǎng)度小于以前路徑長(zhǎng)度時(shí)，才允許繼續(xù)廣播。這樣，最終結(jié)果就是每個(gè)節(jié)點(diǎn)都儲(chǔ)存了每個(gè)錨節(jié)點(diǎn)的位置以及到達(dá)該錨節(jié)點(diǎn)跳數(shù)最少的距離。

    圖2是一個(gè)簡(jiǎn)單的Sum-Dist算法模型，節(jié)點(diǎn)A到錨節(jié)點(diǎn)1只有一條路徑，且僅有一跳，距離為5；到錨節(jié)點(diǎn)2也只有一條路徑，距離為5+6+6= 17；到錨節(jié)點(diǎn)3有兩條路徑：A-D-3以及A-D-E-3，需選擇跳數(shù)最少的路徑，即A-D-3，距離為7+7=14。
1．2 DV-Hop算法
    DV-Hop定位算法測(cè)距過(guò)程分為兩個(gè)階段：
    第一階段首先計(jì)算待定位節(jié)點(diǎn)與錨節(jié)點(diǎn)的最小跳數(shù)。為獲得節(jié)點(diǎn)問(wèn)的跳數(shù)，錨節(jié)點(diǎn)向所有鄰居節(jié)點(diǎn)廣播一個(gè)包含其自身標(biāo)志、位置信息、跳數(shù)被置為0的消息。當(dāng)未知節(jié)點(diǎn)接收到該消息時(shí)，將跳數(shù)加1，并在泛洪限制許可的情況下，將消息繼續(xù)向它的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，此過(guò)程一直持續(xù)下去，直至網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都獲得每個(gè)錨節(jié)點(diǎn)的位置信息和相應(yīng)的跳數(shù)值。為了保證能得到最小跳數(shù)，未知節(jié)點(diǎn)收到消息時(shí)，會(huì)查看是否已經(jīng)收到過(guò)關(guān)于該錨節(jié)點(diǎn)的消息，若已經(jīng)存在，則比較當(dāng)前跳數(shù)是否比之前收到的小，若不是則丟棄該消息，這樣就能保證得到的跳數(shù)最小跳數(shù)。
    第二階段計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的實(shí)際跳距。每個(gè)錨節(jié)點(diǎn)根據(jù)第一階段中得到的其它錨節(jié)點(diǎn)的位置信息和相距跳數(shù)，利用式(1)估算平均跳距
   
    DV-Hop算法能夠計(jì)算出離錨節(jié)點(diǎn)很遠(yuǎn)未知節(jié)點(diǎn)的位置。而且其不需要額外信息，但是其誤差與其路徑的彎曲程度成正比。由于一個(gè)未知節(jié)點(diǎn)只能通過(guò)一條路徑得到跳數(shù)，所以它需要通過(guò)每跳平均距離來(lái)計(jì)算自身的位置，這樣導(dǎo)致計(jì)算出位置的誤差量大。
假設(shè)一個(gè)DV-Hop模型如圖3所示。

    其中，A1，A2，A3，是錨節(jié)點(diǎn)；A是一個(gè)未知節(jié)點(diǎn)，A1，A2，A3之間的距離已知，分別為30，30和40。A點(diǎn)到A1點(diǎn)為8，跳數(shù)為1；根據(jù)最小跳數(shù)原則，A點(diǎn)到A2，A3的跳數(shù)分別為3和2。
    首先，錨節(jié)點(diǎn)廣播包括位置信息、自身標(biāo)志及開(kāi)始跳數(shù)為0的消息，當(dāng)消息廣播至另一個(gè)節(jié)點(diǎn)，跳數(shù)根據(jù)最小跳數(shù)的原則變化，最終，每個(gè)節(jié)點(diǎn)都可得到離錨節(jié)點(diǎn)的最小跳數(shù)，而錨節(jié)點(diǎn)得到與其他錨節(jié)點(diǎn)的最小跳數(shù)后便可以計(jì)算平均跳距。在圖3中，A1、A2、A3的平均跳距如下
    A1：(30+30)÷(4+3)=8．6      (2)
    A2：(30+40)÷(4+5)=7．8      (3)
    A3：(30+40)÷(4+5)=7．8      (4)
    在計(jì)算出平均跳距后，錨節(jié)點(diǎn)將在網(wǎng)絡(luò)中廣播該信息，未知節(jié)點(diǎn)將平均跳距與最小跳數(shù)的乘積作為與錨節(jié)點(diǎn)的間距。即，A1、A2、A3將廣播8．6、7．8、7．8的3個(gè)平均跳距。如，A收到A1、A2、A3這3點(diǎn)廣播的跳距后，即能計(jì)算A到各錨節(jié)點(diǎn)的距離AA1=8．6；AA2=7．8×3= 23．4；AA3=7．8×2=15．6。
1．3 Euclidean算法
    如果網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不規(guī)則，DV-Hop算法的測(cè)距誤差會(huì)較大。針對(duì)這些問(wèn)題，Niculescu和Nath提出了另一種方法，即為Euclidean。該方法依靠錨節(jié)點(diǎn)周圍節(jié)點(diǎn)的幾何關(guān)系進(jìn)行計(jì)算，若一個(gè)節(jié)點(diǎn)的兩個(gè)鄰居節(jié)點(diǎn)已知各自到錨節(jié)點(diǎn)的距離等于彼此之間的距離，這時(shí)，即可計(jì)算該節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離了。
    如圖4是一個(gè)Euclidean算法的模型。

    在圖4中，A有兩個(gè)鄰節(jié)點(diǎn)B、C，已知B、C與錨節(jié)點(diǎn)ANC的距離分別是a和b，結(jié)合已知的節(jié)點(diǎn)間距c、d、e，Euclidean算法得到兩個(gè)解：r1和r2。為確定哪個(gè)解為正解，可采用鄰居節(jié)點(diǎn)投票的方法：若存在第3個(gè)鄰居節(jié)點(diǎn)D，與B或C相連，且已知它到錨節(jié)點(diǎn)的距離。這時(shí)，可用D替換C或B，再重新計(jì)算A的位置，得到另一對(duì)解，正解必然在這兩對(duì)解中，如此，用簡(jiǎn)單的選擇法便可得到正解。當(dāng)然，若是有更多的鄰居節(jié)點(diǎn)參與計(jì)算，最終結(jié)果會(huì)更精確。

2 仿真實(shí)現(xiàn)與結(jié)果分析
    默認(rèn)環(huán)境如下：在100個(gè)單位的正方形場(chǎng)景中，有300個(gè)節(jié)點(diǎn)，通信距離設(shè)為15，錨節(jié)點(diǎn)比例設(shè)為5％，通信誤差是通信距離的10％，以下從不同參數(shù)進(jìn)行仿真比較。
    圖5是不同通信誤差下，DV-Hop、Sum-Dist、Euclidean算法執(zhí)行距離估計(jì)得到的標(biāo)準(zhǔn)方差，圖6和圖7則分別是在不同的通信距離、錨節(jié)點(diǎn)比例下所得到的方差。

    (1)Sum-Dist是3種方法中通信量最少、計(jì)算量最小的測(cè)距算法。但在通信誤差<10％時(shí)，其測(cè)距結(jié)果仍是理想的。實(shí)際上，有兩個(gè)完全不同的趨勢(shì)影響著Sum-Dist的測(cè)距精度。其一，如果完全沒(méi)有通信誤差，多條路徑上的距離總和大于實(shí)際距離，這樣就導(dǎo)致估計(jì)值過(guò)大；其二，由于Sum-Dist算法尋找的是最短路徑，所以當(dāng)存在通信誤差時(shí)，其所選的路徑就會(huì)比實(shí)際距離小。因?yàn)橛羞@兩個(gè)影響，通信距離的小誤差反而提高了Sum-Dist的測(cè)距精度。最初，由于路徑存在彎曲，導(dǎo)致距離估計(jì)值過(guò)大，但在最短路徑的影響下，通信距離誤差的增大反而使距離估計(jì)值更小。
    當(dāng)通信距離增大時(shí)，更多的節(jié)點(diǎn)可以直接通信，這樣就可以得到更多的直線路徑，并為最短路徑提供了更多選擇。所以，對(duì)于Sum-Dist算法來(lái)說(shuō)，提高測(cè)距精度并不一定要增加錨節(jié)點(diǎn)比例。
    (2)DV-Hop算法是相對(duì)較穩(wěn)定、可預(yù)測(cè)的算法，由于并不需要實(shí)際測(cè)量距離，所以它對(duì)誤差源并不敏感。DV-Hop算法的路徑是跳數(shù)最少的路徑，所以其平均跳距接近通信距離。然而，從錨節(jié)點(diǎn)到未知節(jié)點(diǎn)路徑上的最后一跳往往比通信距離短，這也會(huì)導(dǎo)致對(duì)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)間距的少許高估。在短路徑的情況下，高估的情況更為明顯，正因如此，通信距離越大，錨節(jié)點(diǎn)比例越高，跳數(shù)越少，而其測(cè)距誤差反而越大。
    (3)Euclidean算法在精確測(cè)量錨節(jié)點(diǎn)和未知節(jié)點(diǎn)距離方面明顯有效，但僅在沒(méi)有通信距離誤差和高連通的網(wǎng)絡(luò)中。而這些條件一旦放松，Euclidean算法的性能會(huì)急速下降。Euclidean算法在一般情況下對(duì)距離的估計(jì)均過(guò)低，這是由于在選擇時(shí)，被迫在兩個(gè)相隔較遠(yuǎn)的位置間選擇。而大部分情況下，最短距離是不正確的。圖6所示，較短距離r2落在錨節(jié)點(diǎn)的通信范圍內(nèi)。如果r2是正確距離，那么該未知節(jié)點(diǎn)應(yīng)該能夠與錨節(jié)點(diǎn)直接通信，避免選擇的需要。未知節(jié)點(diǎn)距錨節(jié)點(diǎn)有多跳距離時(shí)也同樣存在上述情況。因此，在通信距離誤差較小的情況下，相對(duì)于高估距離，未知節(jié)點(diǎn)更可能會(huì)低估其與錨節(jié)點(diǎn)的距離。

    如圖7所示，Euclidean算法對(duì)于錨節(jié)點(diǎn)比例并不敏感。縮小通信距離的主要影響是Euclidean算法無(wú)法廣播其錨節(jié)點(diǎn)間距。在之前描述Euclidean算法的選擇方法中，需要至少3個(gè)已經(jīng)與錨節(jié)點(diǎn)之間僅有一跳，且已經(jīng)得到距離估計(jì)值的鄰居節(jié)點(diǎn)。在低連通的網(wǎng)絡(luò)中，僅有少量鏈路連接的兩部分往往共享一些錨節(jié)點(diǎn)，這也導(dǎo)致在定位階段只能計(jì)算更少的一些節(jié)點(diǎn)位置。

3 結(jié)束語(yǔ)
    文中實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)中3種免測(cè)距距離估計(jì)算法：Sum-Dist、DV-Hop和Euclidean，在無(wú)線傳感器網(wǎng)絡(luò)中，由于節(jié)點(diǎn)的通信距離有限，為能夠與更遠(yuǎn)的節(jié)點(diǎn)進(jìn)行通信，節(jié)點(diǎn)間采用多跳的方式進(jìn)行數(shù)據(jù)傳遞，這種方式提高了整個(gè)網(wǎng)絡(luò)的通信能力，也為免測(cè)距算法帶來(lái)了執(zhí)行的可能性，實(shí)驗(yàn)結(jié)果表明，免測(cè)距算法更適合應(yīng)用于能源攜帶有限、通信能力弱、計(jì)算能力弱的無(wú)線傳感器網(wǎng)絡(luò)網(wǎng)絡(luò)中。