移動WSNs 中基于跳數矢量的節點定位算法

張煥生，崔炳德，馮 濤

（河北水利電力學院計算機科學與信息工程學院，河北 滄州 061001）

0 引言

隨著電子通信技術的發展，無線傳感網絡（Wireless Sensor Networks，WSNs）［1-2］已在多個應用中廣泛使用。WSNs 是由多個微型、低功耗的傳感節點組成，這些傳感節點具有數據感知、數據處理和通信能力。傳感節點先感知環境數據，再通過多跳通信，將數據傳輸至基站。

在所有的應用中，收集的所有數據都需依賴于傳感節點的準確位置。若數據離開位置信息，該數據可能就無價值。因此，定位成為基于WSNs 應用的關鍵［3］。

事實上，定位就是估計傳感節點的位置。為了估計節點位置，通常先在網絡內部署一些已知位置的節點，這些節點也稱為錨節點。通過測量錨節點與未知節點間信號參數，估計未知節點位置［4］。

依定位過程中是否需要測距信息，定位算法可分為測距和非測距定位。相比于測距定位，非測距定位簡單，易實施。但非測距定位精度劣于測距定位算法。

現存的多數定位算法是針對靜態節點，并沒有考慮節點的移動性。事實上，節點的移動對節點位置的估計提出了挑戰［5-6］。未知節點的移動使節點位置不斷變化，提高了對節點位置估計的難度，增加了定位算法的復雜性。此外，WSNs 內的部分節點可能會發布虛假數據，這些虛假數據降低了定位算法的精度。

作為非測距定位算法，DV-Hop 定位避免了額外的硬件開銷，得到較廣泛應用［7］。DV-Hop 測距算法先估計錨節點與未知節點的跳數，然后再估計網絡內的局部平均跳距，最終將跳距與跳數相乘，便可估計錨節點與未知節點的距離。然而，通過跳數估計節點間的歐式距離存在誤差，并且跳數的估計值也存在誤差。這些誤差降低了DV-Hop定位精度。

為此，提出基于跳數矢量的節點定位算法（Hop Vector-based Node Localization Algorithm，HVLA）。HVLA 算法先通過跳數信息構建跳數矢量信息，再利用質心定位算法估計節點位置。同時，通過測量節點間的響應時間，丟棄一些虛假數據，進而提高定位精度。仿真結果表明，提出的HVLA 算法有效地提高了定位精度，并控制了算法的復雜性。

1 系統模型

每個未知節點知曉m 個錨節點的位置信息，并且向基站注冊，獲取自己的證書。此外，令Tr表示錨節點的傳輸距離，其隨應用場景要求［8］變化。由于網絡場景是動態變化，對Tr進行限定，即在最小傳輸距離和最大傳輸距離間變化：式中，Random（0，1）表示隨機產生0 至1 的函數。

2 HVLA 定位算法

2.1 基于Friis 傳播模型的測距

依據Friis 傳播模型，利用式（2）計算節點的接收功率Pr：

式中，Pr表示錨節點的天線所接收的功率，Pt表示發射天線的發射功率，Gr和Gt分別表示發射天線增益和接收天線增益［9］，為波長，d 表示收發兩端間的距離，其可通過接收功率估計發送節點與接收節點間的距離。

當接收到來自未知節點u 的信號，錨節點a 就依式（3）估計離節點u 間的距離：

2.2 控制包的傳輸

為了收集跳數信息，采用兩類控制包：矢量跳數請求包（Vector Hop ReQuest，VHRQ）和矢量跳數響應包（Vector Hop ReSponse，VHRS）。圖1 描述了這兩個控制包的傳輸過程。

圖1 VHRQ 和VHRS 的傳輸過程

錨節點先向鄰居節點廣播VHRQ，其攜帶的信息如式（4）所示：

式中，SADD 表示錨節點的IP 地址，由于節點是移動，錨節點每隔Δt 廣播VHRQ 包，ISEQ 表示VHRQ消息的序列號，通過該序列號，保證VHRQ 包的實時性［10］。ISEQ 值越大，表示所接收的VHRQ 消息越新鮮。

HC 表示該VHRQ 包所遍歷的跳數。最初，HC=0。一旦收到VHRQ，傳感節點就回復VHRS，并將HC 加1。cert 表示節點證書，其有利于判斷發布虛假數據的惡意節點。

未知節點一旦收到VHRQ，就回復VHRS，其格式如式（5）所示：

式中，UADD 表示未知節點的IP 地址。

2.3 VHRS 包的篩選

一旦收到所有VHRS 消息，錨節點j 就構建跳數矢量：

式中，E 為系統測時誤差。

如果某個VHRS 包的VHTT 大于閾值VHTTth，則認為發送該VHRS 包的未知節點是不誠實，其發送了虛假數據。因此，錨節點拒絕接收該VHRS 包。

閾值VHTTth的定義如式（8）所示：

2.4 跳數矢量的產生流程

接收到VHRS 包后，就判斷VHTT 是否大于VHTTth；若大于VHTTth，就丟棄；否則，就存儲該節點的信息。直到接收到所有未知節點發送的VHRS包。整個流程如圖2 所示。每個錨節點均依據圖2產生自己的跳數矢量。

2.5 定位階段

式中，α1j表示錨節點j 離第1 個未知節點的跳數，αnj表示錨節點j 離第n 個未知節點的跳數。網絡內m 個錨節點就有m 個多項式。通過這些多項式構成m×n 維的跳數矢量矩陣（Hop Vector Matrix，HVM），如式（10）所示：

矩陣HVM 中第i 列HVM［；，i］包含第i 個未知節點離m 個錨節點的跳數。一旦構建了HVM，未知節點i 就選擇第i 列（HVM［；，i］），然后從HVM［；，i］中選擇5 個最小值。這5 個值表示未知節點i離m 個錨節點中最近的5 個錨節點的跳數。隨后，依據五邊形質心算法估計未知節點的位置。具體過程如下：

圖3 五邊形質心定位算法

3 性能分析

3.1 仿真環境

為了更好地分析HVLA 算法的性能，利用NS-2 仿真器建立仿真平臺。引用Mica2 作為節點模型。在區域內部署200 個節點，其中，錨節點數為30個、未知節點數為150 個，發布虛假數據的節點（惡意節點）數為20 個，具體的仿真參數如表1 所示。

表1 仿真參數

此外，選擇文獻［13］提出的安全和強健的DVHop 定位算法（Secure and Robust DV-Hop Localization algorithm，SR-DH），文獻［14］提出防御蟲洞攻擊的安全DV-Hop 定位算法（Securing DV-Hop Localization algorithm against wormhole attacks，S-DH-W）和文獻［15］提出的面向蟲洞攻擊安全DV-Hop 定位算法（Secure DV-Hop localization scheme against wormhole，S-DH-W）作為參照，并分析它們的平均定位誤差、定位所消耗時間（平均時延）以及剩余能量率。

式（13）給出了平均定位誤差（Average Localization Error，ALE）的定義：

3.2 平均定位誤差

首先，分析平均定位誤差隨未知節點的數變化情況，其中未知節點數從10～150 變化，如圖4 所示。

圖4 平均定位誤差率

從圖4 可知，在未知節點數較低時，HVLA 算法的平均定位誤差性能與SR-DH-W、S-DH-W 的平均定位誤差性能相媲美，并且當未知節點數增加后，HVLA 算法的平均定位誤差性最低，且在未知節點數達到100 個后，其平均定位誤差性幾乎保持常數。在未知節點數從10～150 間變化期間，最小的平均定位誤差為5.33%，最大的平均定位誤差率達到13.77%。

SR-DH-W 和S-DH-W 算法分別在未知節點達到80 個和60 個后，平均定位誤差快速上升。但是，SR-DH-W 算法在未知節點數較少時，其定位性能與HVLA 算法相近。然而，當未知節點數增加后，其定位誤差快速增加。

SR-DH 算法的平均定位誤差性能隨未知節點數的增加而變化的趨勢與SR-DH-W 和S-DH-W算法相反。在未知節點數較小時，定位誤差較大，但是隨著未知節點數的增加，其定位誤差逐步減少，原因在于：SR-DH 算法采用反饋機制。未知節點數越多，其反饋的信息越豐富，越有利于降低定位誤差。

3.3 平均時延

圖5 顯示了HVLA 定位算法的平均時延，即估計未知節點位置所消耗的時間。平均時延越低，定位算法復雜度越低，定位性能越好。

圖5 平均時延

從圖5 可知，相比于SR-DH、SR-DH-W 和S-DH-W 算法，HVLA 定位算法的平均時延約11.474 ms，SR-DH 算法的平均時延最高，達到85.846 ms。這也說明，SR-DH 算法是以復雜度為代價，換取高的定位精度。此外，SR-DH-W 和S-DH-W 算法的平均時延約26.71 ms 和37.52 ms。

3.4 剩余能量率

最后，分析在不同未知節點數環境下的剩余能量率。

圖6 剩余能量率

從圖6 可知，在未知節點數為10 時，HVLA、SR-DH、SR-DH-W 和S-DH-W 算法均獲取最高的剩余能量。然而，隨著未知節點數的增加，SR-DH、SR-DH-W 和S-DH-W 算法的剩余能量的下降速度快于HVLA 算法。

未知節點數在15～55 變化期間，SR-DH、SR-DH-W 和S-DH-W 算法的能耗速度加快。相比之下，HVLA 算法的能耗速度在未知節點數的變化期間比較穩定。

4 結論

針對移動WSNs 的節點定位問題，提出了基于網格的DV-Hop 安全定位算法（HVLA）。HVLA 算法引用網格策略，通過錨節點構建跳數矢量，再利用質心定位估計未知節點的位置。同時，丟棄一些虛假數據，進而估計定位精度。仿真結果表明，提出的HVLA 算法提高了定位精度，并降低了定位復雜度。