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

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

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

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

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

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

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

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

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

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