石琴琴，周俊杰，張建平

(1.上海應(yīng)用技術(shù)學(xué)院 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，上海 201418;2.科大智能科技股份有限公司，上海 201203)

1 引言

DV－Hop(Distance Vector－ Hop)定位方法［1］是由美國(guó)路特葛斯大學(xué)(Rutgers University)的Dragos Niculescu 等人提出的一種非基于測(cè)距的定位方法，應(yīng)用于無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)自定位。其基本思想是借助網(wǎng)絡(luò)中部分自身位置已知的節(jié)點(diǎn)(稱為信標(biāo))，將未知節(jié)點(diǎn)到信標(biāo)之間的距離用平均每跳距離和兩者之間跳數(shù)的乘積表示，而后通過Lateration 算法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。DV－Hop 方法不需要配備專門的距離測(cè)量設(shè)備，具有易于開展、可擴(kuò)展性強(qiáng)、能量高效等優(yōu)點(diǎn)，適用于分布式定位，且算法過程簡(jiǎn)單，已經(jīng)成為一種經(jīng)典的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法，但是它在節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)環(huán)境下存在定位誤差較大的問題，在滿足實(shí)用需求層面仍然有很大的提高空間。

很多學(xué)者提出了多種基于經(jīng)典DV－Hop 方法的改進(jìn)策略，以期提高其在多樣化應(yīng)用環(huán)境下的定位精度。多數(shù)改進(jìn)策略集中在DV－Hop 方法第1步中的平均跳距修正上面，如文獻(xiàn)［2－4］中所列。這些策略在一定的實(shí)驗(yàn)環(huán)境下對(duì)定位誤差有所改善，但針對(duì)各種可能出現(xiàn)的節(jié)點(diǎn)分布情況，未能從根本上解決節(jié)點(diǎn)間分布不均帶來的估算誤差。文獻(xiàn)［5－6］中提出了針對(duì)DV－Hop 方法第2 步中使用的定位算法的改進(jìn)策略，這些策略執(zhí)行的計(jì)算條件均在默認(rèn)距離估計(jì)值精確的前提下，且計(jì)算量較大，在分布式定位計(jì)算模型中使用存在很大挑戰(zhàn)。

本文提出的改進(jìn)策略主要的貢獻(xiàn)在于:在距離估計(jì)階段對(duì)每個(gè)未知節(jié)點(diǎn)，使用其1 跳內(nèi)最近鄰信標(biāo)與其余各個(gè)信標(biāo)的拓?fù)溥B接關(guān)系近似此未知節(jié)點(diǎn)與各信標(biāo)之間的拓?fù)潢P(guān)系，獨(dú)立確定未知節(jié)點(diǎn)與各信標(biāo)間的平均跳距，以期使得估計(jì)距離盡量接近真實(shí)距離;在節(jié)點(diǎn)位置計(jì)算階段，在使用Lateration 算法獲得節(jié)點(diǎn)初始坐標(biāo)后，將定位問題建模為使用牛頓迭代算法［7］求非線性方程組最優(yōu)解的問題，實(shí)現(xiàn)進(jìn)一步的位置求精計(jì)算，以期達(dá)到提高整體定位精度的目的。

2 DV－Hop 定位方法介紹

2.1 經(jīng)典DV－Hop 方法

DV－Hop 定位方法采用基于多跳距離估計(jì)的節(jié)點(diǎn)自定位模型，其定位步驟可以概括為以下兩步:

(1)使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距離每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。每個(gè)信標(biāo)節(jié)點(diǎn)在獲得其他信標(biāo)節(jié)點(diǎn)位置和相隔跳距之后，采用式(1)計(jì)算網(wǎng)絡(luò)平均每跳距離，然后將其作為一個(gè)校正值廣播至網(wǎng)絡(luò)中:

式中，(xi，yi)、(xj，yj)是信標(biāo)節(jié)點(diǎn)i 和j 的坐標(biāo)，hij是i 和j(i≠j)之間的跳段數(shù)。未知節(jié)點(diǎn)從最近的信標(biāo)節(jié)點(diǎn)處接收校正值，依此估計(jì)自身到各信標(biāo)節(jié)點(diǎn)之間的距離di，計(jì)算公式如式(2)所示:

式中，H 是網(wǎng)絡(luò)平均跳距值的校正值，hi是未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)i 的最小跳數(shù)值;

(2)當(dāng)某一未知節(jié)點(diǎn)獲得與3 個(gè)或更多個(gè)信標(biāo)節(jié)點(diǎn)之間的距離時(shí)，采用Lateration 算法實(shí)現(xiàn)定位計(jì)算。文獻(xiàn)［8］對(duì)Lateration 算法的屬性進(jìn)行了研究與分析，結(jié)論為:Lateration 算法對(duì)測(cè)距誤差敏感，而且當(dāng)參與計(jì)算的信標(biāo)節(jié)點(diǎn)數(shù)目大于4 時(shí)，再采用增加參與定位計(jì)算的信標(biāo)數(shù)目并不能起到提高節(jié)點(diǎn)定位精度的作用，故本文實(shí)驗(yàn)采用4 個(gè)信標(biāo)參與節(jié)點(diǎn)位置計(jì)算。

2.2 DV－Hop 方法既有改進(jìn)策略分析

DV－Hop 方法的主要不足在于:當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)布設(shè)時(shí)，其分布的不均勻會(huì)使得通過全網(wǎng)信標(biāo)節(jié)點(diǎn)間距離和與跳數(shù)和平均計(jì)算取得的每跳距離估值不能真實(shí)反映未知節(jié)點(diǎn)與每一個(gè)信標(biāo)之間每跳平均距離值;另外，根據(jù)既有文獻(xiàn)［8］對(duì)Lateration定位算法屬性的研究，當(dāng)距離誤差較大時(shí)，其定位精度是不能保證的，因此，有必要增加求精步驟，以此提高整體的算法魯棒性。

文獻(xiàn)［2－3］在算法設(shè)計(jì)中忽略了RSSI 測(cè)距的不穩(wěn)定性，做了精確測(cè)距的假設(shè)，平均每跳距離修正仍然采用全局的平均值對(duì)局部適用的參數(shù)進(jìn)行修正;文獻(xiàn)［4］可能出現(xiàn)閾值內(nèi)信標(biāo)數(shù)不足以實(shí)現(xiàn)定位的情況，并且增加了網(wǎng)絡(luò)通信量和計(jì)算量。本文綜合上述文獻(xiàn)的優(yōu)缺點(diǎn)，提出相應(yīng)的改進(jìn)策略，并命名為IDV－Hop(Improved DV－Hop)方法。

3 DV－Hop 方法改進(jìn)策略

3.1 IDV－Hop 方法

IDV－Hop 方法相對(duì)于原方法具體的改進(jìn)策略描述如下:

(1)在距離估計(jì)步驟中，針對(duì)每一個(gè)未知節(jié)點(diǎn)P，找出跳段距離最近的信標(biāo)k，若其在1 跳范圍內(nèi)，則計(jì)算P 到其余信標(biāo)i 的距離，采用的平均跳距為

即采用當(dāng)前未知節(jié)點(diǎn)最近的1 跳內(nèi)信標(biāo)與其他信標(biāo)之間的多跳連接關(guān)系來近似未知節(jié)點(diǎn)與其他信標(biāo)之間的多跳連接關(guān)系;若k 不在P 的一跳范圍之內(nèi)，則仍采用式(1)中的平均跳距;

(2)在節(jié)點(diǎn)位置計(jì)算階段，根據(jù)文獻(xiàn)［8］對(duì)信標(biāo)選擇的分析，選擇跳距最近的4 個(gè)信標(biāo)參與定位計(jì)算，使用Lateration 算法獲得未知節(jié)點(diǎn)的初始坐標(biāo)。而后，將定位問題建模為如式(4)所示的非線性方程組求最優(yōu)解的問題:

方程組的待求未知數(shù)為未知節(jié)點(diǎn)的坐標(biāo)x、y，以及未知節(jié)點(diǎn)與4 個(gè)信標(biāo)之間的距離值d1、d2、d3、d4，使用牛頓迭代法求得方程組的解作為最終的節(jié)點(diǎn)定位值。

3.2 牛頓迭代法

本文通過實(shí)驗(yàn)對(duì)比了牛頓迭代法與最速下降法、共軛梯度法等其他常用的求解非線性方程組的方法在算法復(fù)雜度、收斂速度與收斂穩(wěn)定性等方面的指標(biāo)后，選擇其中與Lateration 算法計(jì)算結(jié)果匹配度最好、收斂速度最快、收斂結(jié)果最穩(wěn)定以及精度最高的牛頓迭代法作為初始定位結(jié)果的優(yōu)化算法。牛頓迭代法的運(yùn)算原理與方法步驟如下:

對(duì)式(4)中所列方程組，用fi(i=1，2，3，4)表示方程組中各等式左邊未知數(shù)的函數(shù)表達(dá)式，用X(k)表示一組未知數(shù)x、y、d1、d2、d3、d4的當(dāng)前值組成的列向量，在X(k)處按照多元函數(shù)的泰勒公式展開，并取線性項(xiàng)得到

由此得到的迭代公式為

對(duì)每一個(gè)未知節(jié)點(diǎn)，以IDV－Hop 方法在距離估計(jì)與位置計(jì)算兩個(gè)步驟中獲得的x、y、d1、d2、d3、d4的值組成初始值列向量X(0)，依照公式(7)展開迭代計(jì)算。

4 仿真實(shí)驗(yàn)

為評(píng)估本文改進(jìn)策略的有效性，基于MATLAB7.0 對(duì)傳統(tǒng)的DV－Hop 算法、文獻(xiàn)［4］中的跳數(shù)加權(quán)改進(jìn)算法及本文算法進(jìn)行仿真實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)數(shù)據(jù)分析比較，對(duì)算法性能進(jìn)行評(píng)價(jià)。本節(jié)首先描述仿真實(shí)驗(yàn)中的節(jié)點(diǎn)布設(shè)場(chǎng)景及仿真步驟，并介紹用于評(píng)價(jià)算法表現(xiàn)的參數(shù)，最后根據(jù)實(shí)驗(yàn)結(jié)果對(duì)所使用的算法及系統(tǒng)的整體表現(xiàn)進(jìn)行詳盡分析與評(píng)價(jià)。

4.1 實(shí)驗(yàn)環(huán)境

仿真實(shí)驗(yàn)環(huán)境參照文獻(xiàn)［4］，節(jié)點(diǎn)部署在邊長(zhǎng)為100 單位的正方形區(qū)域內(nèi)，為了取得更客觀、更準(zhǔn)確的實(shí)驗(yàn)數(shù)據(jù)，共設(shè)置兩種實(shí)驗(yàn)場(chǎng)景:場(chǎng)景1 是在區(qū)域內(nèi)隨機(jī)生成100 個(gè)節(jié)點(diǎn)，改變其中信標(biāo)節(jié)點(diǎn)的比例(10%～40%);場(chǎng)景2 是將信標(biāo)節(jié)點(diǎn)個(gè)數(shù)固定為15，改變節(jié)點(diǎn)總數(shù)(100～400)。實(shí)驗(yàn)場(chǎng)景符合如下設(shè)定:網(wǎng)內(nèi)所有節(jié)點(diǎn)都是同構(gòu)的，且彼此之間無通信影響;所有節(jié)點(diǎn)具有相同的通信半徑、相同的通信成功率及相同的路由協(xié)議，通信半徑設(shè)置為20 單位，保證網(wǎng)絡(luò)的連通性;文獻(xiàn)［4］中跳數(shù)加權(quán)改進(jìn)算法仿真時(shí)設(shè)定參與平均每跳距離參數(shù)估計(jì)的信標(biāo)跳數(shù)閾值為原文獻(xiàn)所述定位精度最高的值6。

在上述實(shí)驗(yàn)場(chǎng)景下仿真?zhèn)鹘y(tǒng)DV－Hop 方法、文獻(xiàn)［4］中的跳數(shù)加權(quán)改進(jìn)算法與本文所提改進(jìn)策略IDV－Hop 的定位步驟。網(wǎng)絡(luò)距離估計(jì)精度用所有未知節(jié)點(diǎn)與信標(biāo)之間估計(jì)距離誤差的平均值與標(biāo)準(zhǔn)差來衡量;定位精度用所有未知節(jié)點(diǎn)真實(shí)位置與定位計(jì)算獲得的位置之間的距離，即點(diǎn)位誤差的平均值及其標(biāo)準(zhǔn)差衡量。本文將誤差歸一化為節(jié)點(diǎn)通信半徑的百分比進(jìn)行表示。

4.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)場(chǎng)景1 模擬網(wǎng)絡(luò)節(jié)點(diǎn)布設(shè)拓?fù)渑c信標(biāo)比例變化，3 種算法的距離估計(jì)誤差對(duì)比如圖1 所示，距離估計(jì)誤差標(biāo)準(zhǔn)差對(duì)比如圖2 所示，定位誤差對(duì)比如圖3 所示，定位誤差標(biāo)準(zhǔn)差對(duì)比如圖4 所示。從圖1 與圖2 可知，3 種算法的距離估計(jì)誤差都隨著信標(biāo)節(jié)點(diǎn)比例的增長(zhǎng)而減小，本文改進(jìn)算法可取得較低的距離估計(jì)誤差，且當(dāng)網(wǎng)內(nèi)信標(biāo)比例較低時(shí)，優(yōu)勢(shì)更為明顯，并保持最低的距離估計(jì)誤差標(biāo)準(zhǔn)差，因此可獲得更穩(wěn)定的距離估計(jì)精度。從圖3 與圖4 可知，3 種算法的定位誤差都隨著信標(biāo)節(jié)點(diǎn)比例的增長(zhǎng)而減小，且當(dāng)信標(biāo)比例超過25%時(shí)，減小的趨勢(shì)趨于平緩，總體看來，本文算法對(duì)網(wǎng)絡(luò)拓?fù)浜托艠?biāo)比例變化的適應(yīng)性最強(qiáng)，相對(duì)于原算法和文獻(xiàn)［4］算法，定位精度平均提高約18%和10%，表現(xiàn)出較為平穩(wěn)的定位誤差與相對(duì)穩(wěn)定的定位精度。

圖1 距離估計(jì)誤差與信標(biāo)比例的關(guān)系Fig.1 Range error vs.beacon proportion

圖2 距離估計(jì)誤差標(biāo)準(zhǔn)差與信標(biāo)比例的關(guān)系Fig.2 Range error standard deviation vs.beacon proportion

圖3 定位誤差與信標(biāo)比例的關(guān)系Fig.3 Position error vs.beacon proportion

圖4 定位誤差標(biāo)準(zhǔn)差與信標(biāo)比例的關(guān)系Fig.4 Position error standard deviation vs.beacon proportion

實(shí)驗(yàn)場(chǎng)景2 模擬網(wǎng)絡(luò)節(jié)點(diǎn)布設(shè)拓?fù)渑c節(jié)點(diǎn)布設(shè)密度變化，3 種算法的距離估計(jì)誤差對(duì)比如圖5 所示，距離估計(jì)誤差標(biāo)準(zhǔn)差對(duì)比如圖6 所示，定位誤差對(duì)比如圖7 所示，定位誤差標(biāo)準(zhǔn)差對(duì)比如圖8 所示。從圖5 與圖6 可知，3 種算法的距離估計(jì)誤差都隨著節(jié)點(diǎn)布設(shè)密度的增長(zhǎng)而減小，但整體變化趨勢(shì)較平緩，本文改進(jìn)算法與文獻(xiàn)［4］算法相對(duì)原算法有較大改善，約為20%，兩者之間的平均距離估計(jì)誤差相差約4%，本文改進(jìn)算法可取得較低的距離估計(jì)誤差，并保持更穩(wěn)定的距離估計(jì)精度。從圖7 與圖8 可知，3 種算法的定位誤差都隨著節(jié)點(diǎn)布設(shè)密度的增長(zhǎng)而減小，總體看來，本文算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)布設(shè)密度的變化最為敏感，相對(duì)于原算法和文獻(xiàn)［4］算法，定位精度平均提高約15%和10%，并可保持更穩(wěn)定的定位精度。

圖5 距離估計(jì)誤差與節(jié)點(diǎn)總數(shù)的關(guān)系Fig.5 Range error vs.number of nodes

圖6 距離估計(jì)誤差標(biāo)準(zhǔn)差與節(jié)點(diǎn)總數(shù)的關(guān)系Fig.6 Range error standard deviation vs.number of nodes

圖7 定位誤差與節(jié)點(diǎn)總數(shù)的關(guān)系Fig.7 Position error vs.number of nodes

圖8 定位誤差標(biāo)準(zhǔn)差與節(jié)點(diǎn)總數(shù)的關(guān)系Fig.8 Position error vs.number of nodes

本文改進(jìn)策略相對(duì)于原DV－Hop 方法未增加任何通信量，使用的牛頓迭代法對(duì)全部未知節(jié)點(diǎn)的計(jì)算都收斂，且平均迭代次數(shù)約為4 次，因此在不降低原DV－Hop 算法定位覆蓋率的基礎(chǔ)上以增加較小的計(jì)算量為代價(jià)可獲得網(wǎng)絡(luò)整體定位精度的提高。相對(duì)于文獻(xiàn)［4］所述改進(jìn)算法，本文改進(jìn)策略節(jié)約了未知節(jié)點(diǎn)反算信標(biāo)節(jié)點(diǎn)位置并廣播誤差修正值的計(jì)算量與通信量，且取得了較高且穩(wěn)定的定位精度。

5 結(jié)束語

本文以經(jīng)典DV－Hop 定位方法為研究對(duì)象，針對(duì)其在實(shí)際應(yīng)用場(chǎng)景中存在的定位精度較低的問題進(jìn)行算法改進(jìn)。本文的改進(jìn)策略不需要額外的硬件支持，也不需要額外的通信負(fù)荷來獲得更多的計(jì)算條件。仿真實(shí)驗(yàn)表明:通過搜索最佳逼近路徑，獨(dú)立計(jì)算未知節(jié)點(diǎn)到每一信標(biāo)節(jié)點(diǎn)的平均每跳距離，可有效提高網(wǎng)路的距離估計(jì)精度，從而獲得提高節(jié)點(diǎn)定位精度的必要條件;在此基礎(chǔ)上，為定位算法增加求精步驟，可提高算法對(duì)距離估計(jì)誤差的魯棒性，從而提高網(wǎng)絡(luò)整體的定位精度。本文研究成果為在低造價(jià)、低能耗要求下解決無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位問題提供了新的解決思路與方案，為無線傳感器網(wǎng)絡(luò)在多樣化的應(yīng)用環(huán)境下有效地實(shí)現(xiàn)節(jié)點(diǎn)自定位提供方法選擇與策略指導(dǎo)，具有良好的實(shí)用價(jià)值與應(yīng)用前景。

既有的研究工作主要針對(duì)DV－Hop 方法第2步所采用的定位算法進(jìn)行了改進(jìn)，本文改進(jìn)策略則漸次對(duì)兩個(gè)步驟的算法進(jìn)行了改進(jìn)，在研究層面進(jìn)行了細(xì)化與綜合。后續(xù)的研究將在搜索實(shí)際節(jié)點(diǎn)連接路徑的最佳逼近策略與具體算法方面深入，以期提高測(cè)距精度，進(jìn)一步增強(qiáng)方法的實(shí)用性。

［1］NICULESCU D，NATH B.DV based positioning in ad hoc networks［J］.Telecommunications Systems，2003，22(1):267－280.

［2］吳楠，劉方愛，王淑嫻.基于跳數(shù)修正和跳距調(diào)整的DV－Hop 定位改進(jìn)算法［J］.微電子學(xué)與計(jì)算機(jī)，2015，32(1):91－95.WU Nan，LIU Fangai，WANG Shuxian.Algorithm for locating nodes in WSN based on modifying hops and hopping distances［J］.Microelectronics ＆ Computer，2015，32(1):91－95.(in Chinese)

［3］夏少波，朱曉麗，鄒建梅，等.基于跳數(shù)修正的DV－Hop 定位改進(jìn)算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28(5):757－762.XIA Shaobo，ZHU Xiaoli，ZOU Jianmei，et al.The improved dv－h(huán)op algorithm based on hop count［J］.Chinese Journal of Sensors and Actuators，2015，28(5):757－762.(in Chinese)

［4］HU Y，LI X M.An improvement of DV－Hop localization algorithm for wireless sensor networks［J］.Telecommunication Systems，2013，53(1):13－18.

［5］李牧東，熊偉，梁青.基于人工蜂群改進(jìn)算法的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26(2):241－245.LI Mudong，XIONG Wei，LIANG Qing.Wireless sensor networks node localization algorithm based on improved ABC algorithm［J］.Chinese Journal of Sensors and Actuators，2013，26(2):241－245.(in Chinese)

［6］ZHANG Y，XIANG S，F(xiàn)U W，et al.Improved normalized collinearity DV－ Hop algorithm for node localization in wireless sensor network［J］.International Journal of Distributed Sensor Networks，2014(2):1－14.

［7］張德豐.MATLAB 實(shí)用數(shù)值分析［M］.北京:清華大學(xué)出版社，2012:254－260.ZHANG Defeng.MATLAB numerical analysis and simulation examples［M］.Beijing:Tsinghua University Press，2012:254－260.(in Chinese)

［8］LANGENDOEN K，REIJERS N.Distributed localization in wireless sensor networks:a quantitative comparison［J］.Computer Networks，2003，43(4):499－518.