移動(dòng)WSNs 中基于跳數(shù)矢量的節(jié)點(diǎn)定位算法

張煥生，崔炳德，馮 濤

（河北水利電力學(xué)院計(jì)算機(jī)科學(xué)與信息工程學(xué)院，河北 滄州 061001）

0 引言

隨著電子通信技術(shù)的發(fā)展，無(wú)線傳感網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）［1-2］已在多個(gè)應(yīng)用中廣泛使用。WSNs 是由多個(gè)微型、低功耗的傳感節(jié)點(diǎn)組成，這些傳感節(jié)點(diǎn)具有數(shù)據(jù)感知、數(shù)據(jù)處理和通信能力。傳感節(jié)點(diǎn)先感知環(huán)境數(shù)據(jù)，再通過(guò)多跳通信，將數(shù)據(jù)傳輸至基站。

在所有的應(yīng)用中，收集的所有數(shù)據(jù)都需依賴于傳感節(jié)點(diǎn)的準(zhǔn)確位置。若數(shù)據(jù)離開(kāi)位置信息，該數(shù)據(jù)可能就無(wú)價(jià)值。因此，定位成為基于WSNs 應(yīng)用的關(guān)鍵［3］。

事實(shí)上，定位就是估計(jì)傳感節(jié)點(diǎn)的位置。為了估計(jì)節(jié)點(diǎn)位置，通常先在網(wǎng)絡(luò)內(nèi)部署一些已知位置的節(jié)點(diǎn)，這些節(jié)點(diǎn)也稱為錨節(jié)點(diǎn)。通過(guò)測(cè)量錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間信號(hào)參數(shù)，估計(jì)未知節(jié)點(diǎn)位置［4］。

依定位過(guò)程中是否需要測(cè)距信息，定位算法可分為測(cè)距和非測(cè)距定位。相比于測(cè)距定位，非測(cè)距定位簡(jiǎn)單，易實(shí)施。但非測(cè)距定位精度劣于測(cè)距定位算法。

現(xiàn)存的多數(shù)定位算法是針對(duì)靜態(tài)節(jié)點(diǎn)，并沒(méi)有考慮節(jié)點(diǎn)的移動(dòng)性。事實(shí)上，節(jié)點(diǎn)的移動(dòng)對(duì)節(jié)點(diǎn)位置的估計(jì)提出了挑戰(zhàn)［5-6］。未知節(jié)點(diǎn)的移動(dòng)使節(jié)點(diǎn)位置不斷變化，提高了對(duì)節(jié)點(diǎn)位置估計(jì)的難度，增加了定位算法的復(fù)雜性。此外，WSNs 內(nèi)的部分節(jié)點(diǎn)可能會(huì)發(fā)布虛假數(shù)據(jù)，這些虛假數(shù)據(jù)降低了定位算法的精度。

作為非測(cè)距定位算法，DV-Hop 定位避免了額外的硬件開(kāi)銷，得到較廣泛應(yīng)用［7］。DV-Hop 測(cè)距算法先估計(jì)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的跳數(shù)，然后再估計(jì)網(wǎng)絡(luò)內(nèi)的局部平均跳距，最終將跳距與跳數(shù)相乘，便可估計(jì)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離。然而，通過(guò)跳數(shù)估計(jì)節(jié)點(diǎn)間的歐式距離存在誤差，并且跳數(shù)的估計(jì)值也存在誤差。這些誤差降低了DV-Hop定位精度。

為此，提出基于跳數(shù)矢量的節(jié)點(diǎn)定位算法（Hop Vector-based Node Localization Algorithm，HVLA）。HVLA 算法先通過(guò)跳數(shù)信息構(gòu)建跳數(shù)矢量信息，再利用質(zhì)心定位算法估計(jì)節(jié)點(diǎn)位置。同時(shí)，通過(guò)測(cè)量節(jié)點(diǎn)間的響應(yīng)時(shí)間，丟棄一些虛假數(shù)據(jù)，進(jìn)而提高定位精度。仿真結(jié)果表明，提出的HVLA 算法有效地提高了定位精度，并控制了算法的復(fù)雜性。

1 系統(tǒng)模型

每個(gè)未知節(jié)點(diǎn)知曉m 個(gè)錨節(jié)點(diǎn)的位置信息，并且向基站注冊(cè)，獲取自己的證書(shū)。此外，令Tr表示錨節(jié)點(diǎn)的傳輸距離，其隨應(yīng)用場(chǎng)景要求［8］變化。由于網(wǎng)絡(luò)場(chǎng)景是動(dòng)態(tài)變化，對(duì)Tr進(jìn)行限定，即在最小傳輸距離和最大傳輸距離間變化：式中，Random（0，1）表示隨機(jī)產(chǎn)生0 至1 的函數(shù)。

2 HVLA 定位算法

2.1 基于Friis 傳播模型的測(cè)距

依據(jù)Friis 傳播模型，利用式（2）計(jì)算節(jié)點(diǎn)的接收功率Pr：

式中，Pr表示錨節(jié)點(diǎn)的天線所接收的功率，Pt表示發(fā)射天線的發(fā)射功率，Gr和Gt分別表示發(fā)射天線增益和接收天線增益［9］，為波長(zhǎng)，d 表示收發(fā)兩端間的距離，其可通過(guò)接收功率估計(jì)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)間的距離。

當(dāng)接收到來(lái)自未知節(jié)點(diǎn)u 的信號(hào)，錨節(jié)點(diǎn)a 就依式（3）估計(jì)離節(jié)點(diǎn)u 間的距離：

2.2 控制包的傳輸

為了收集跳數(shù)信息，采用兩類控制包：矢量跳數(shù)請(qǐng)求包（Vector Hop ReQuest，VHRQ）和矢量跳數(shù)響應(yīng)包（Vector Hop ReSponse，VHRS）。圖1 描述了這兩個(gè)控制包的傳輸過(guò)程。

圖1 VHRQ 和VHRS 的傳輸過(guò)程

錨節(jié)點(diǎn)先向鄰居節(jié)點(diǎn)廣播VHRQ，其攜帶的信息如式（4）所示：

式中，SADD 表示錨節(jié)點(diǎn)的IP 地址，由于節(jié)點(diǎn)是移動(dòng)，錨節(jié)點(diǎn)每隔Δt 廣播VHRQ 包，ISEQ 表示VHRQ消息的序列號(hào)，通過(guò)該序列號(hào)，保證VHRQ 包的實(shí)時(shí)性［10］。ISEQ 值越大，表示所接收的VHRQ 消息越新鮮。

HC 表示該VHRQ 包所遍歷的跳數(shù)。最初，HC=0。一旦收到VHRQ，傳感節(jié)點(diǎn)就回復(fù)VHRS，并將HC 加1。cert 表示節(jié)點(diǎn)證書(shū)，其有利于判斷發(fā)布虛假數(shù)據(jù)的惡意節(jié)點(diǎn)。

未知節(jié)點(diǎn)一旦收到VHRQ，就回復(fù)VHRS，其格式如式（5）所示：

式中，UADD 表示未知節(jié)點(diǎn)的IP 地址。

2.3 VHRS 包的篩選

一旦收到所有VHRS 消息，錨節(jié)點(diǎn)j 就構(gòu)建跳數(shù)矢量：

式中，E 為系統(tǒng)測(cè)時(shí)誤差。

如果某個(gè)VHRS 包的VHTT 大于閾值VHTTth，則認(rèn)為發(fā)送該VHRS 包的未知節(jié)點(diǎn)是不誠(chéng)實(shí)，其發(fā)送了虛假數(shù)據(jù)。因此，錨節(jié)點(diǎn)拒絕接收該VHRS 包。

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

2.4 跳數(shù)矢量的產(chǎn)生流程

接收到VHRS 包后，就判斷VHTT 是否大于VHTTth；若大于VHTTth，就丟棄；否則，就存儲(chǔ)該節(jié)點(diǎn)的信息。直到接收到所有未知節(jié)點(diǎn)發(fā)送的VHRS包。整個(gè)流程如圖2 所示。每個(gè)錨節(jié)點(diǎn)均依據(jù)圖2產(chǎn)生自己的跳數(shù)矢量。

2.5 定位階段

式中，α1j表示錨節(jié)點(diǎn)j 離第1 個(gè)未知節(jié)點(diǎn)的跳數(shù)，αnj表示錨節(jié)點(diǎn)j 離第n 個(gè)未知節(jié)點(diǎn)的跳數(shù)。網(wǎng)絡(luò)內(nèi)m 個(gè)錨節(jié)點(diǎn)就有m 個(gè)多項(xiàng)式。通過(guò)這些多項(xiàng)式構(gòu)成m×n 維的跳數(shù)矢量矩陣（Hop Vector Matrix，HVM），如式（10）所示：

矩陣HVM 中第i 列HVM［；，i］包含第i 個(gè)未知節(jié)點(diǎn)離m 個(gè)錨節(jié)點(diǎn)的跳數(shù)。一旦構(gòu)建了HVM，未知節(jié)點(diǎn)i 就選擇第i 列（HVM［；，i］），然后從HVM［；，i］中選擇5 個(gè)最小值。這5 個(gè)值表示未知節(jié)點(diǎn)i離m 個(gè)錨節(jié)點(diǎn)中最近的5 個(gè)錨節(jié)點(diǎn)的跳數(shù)。隨后，依據(jù)五邊形質(zhì)心算法估計(jì)未知節(jié)點(diǎn)的位置。具體過(guò)程如下：

圖3 五邊形質(zhì)心定位算法

3 性能分析

3.1 仿真環(huán)境

為了更好地分析HVLA 算法的性能，利用NS-2 仿真器建立仿真平臺(tái)。引用Mica2 作為節(jié)點(diǎn)模型。在區(qū)域內(nèi)部署200 個(gè)節(jié)點(diǎn)，其中，錨節(jié)點(diǎn)數(shù)為30個(gè)、未知節(jié)點(diǎn)數(shù)為150 個(gè)，發(fā)布虛假數(shù)據(jù)的節(jié)點(diǎn)（惡意節(jié)點(diǎn)）數(shù)為20 個(gè)，具體的仿真參數(shù)如表1 所示。

表1 仿真參數(shù)

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

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

3.2 平均定位誤差

首先，分析平均定位誤差隨未知節(jié)點(diǎn)的數(shù)變化情況，其中未知節(jié)點(diǎn)數(shù)從10～150 變化，如圖4 所示。

圖4 平均定位誤差率

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

SR-DH-W 和S-DH-W 算法分別在未知節(jié)點(diǎn)達(dá)到80 個(gè)和60 個(gè)后，平均定位誤差快速上升。但是，SR-DH-W 算法在未知節(jié)點(diǎn)數(shù)較少時(shí)，其定位性能與HVLA 算法相近。然而，當(dāng)未知節(jié)點(diǎn)數(shù)增加后，其定位誤差快速增加。

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

3.3 平均時(shí)延

圖5 顯示了HVLA 定位算法的平均時(shí)延，即估計(jì)未知節(jié)點(diǎn)位置所消耗的時(shí)間。平均時(shí)延越低，定位算法復(fù)雜度越低，定位性能越好。

圖5 平均時(shí)延

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

3.4 剩余能量率

最后，分析在不同未知節(jié)點(diǎn)數(shù)環(huán)境下的剩余能量率。

圖6 剩余能量率

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

未知節(jié)點(diǎn)數(shù)在15～55 變化期間，SR-DH、SR-DH-W 和S-DH-W 算法的能耗速度加快。相比之下，HVLA 算法的能耗速度在未知節(jié)點(diǎn)數(shù)的變化期間比較穩(wěn)定。

4 結(jié)論

針對(duì)移動(dòng)WSNs 的節(jié)點(diǎn)定位問(wèn)題，提出了基于網(wǎng)格的DV-Hop 安全定位算法（HVLA）。HVLA 算法引用網(wǎng)格策略，通過(guò)錨節(jié)點(diǎn)構(gòu)建跳數(shù)矢量，再利用質(zhì)心定位估計(jì)未知節(jié)點(diǎn)的位置。同時(shí)，丟棄一些虛假數(shù)據(jù)，進(jìn)而估計(jì)定位精度。仿真結(jié)果表明，提出的HVLA 算法提高了定位精度，并降低了定位復(fù)雜度。