惠海波，張玲華

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)[1]是人們用來感知、采集、處理信息的重要工具，而節(jié)點定位技術(shù)[2]是其進行各種應(yīng)用的基礎(chǔ)。該技術(shù)主要包括兩類：即基于測距(range-base)和非測距(range-free)技術(shù)[3-5]。

在非測距技術(shù)的定位算法中，DV-Hop算法因其成本低、開銷小、實現(xiàn)相對簡單等優(yōu)點而廣泛使用。但其定位精度不高，對此國內(nèi)外的許多學(xué)者都提出了改進方法。比如，文獻[6]是利用多通信半徑來修正跳數(shù)，并加權(quán)處理未知節(jié)點平均跳距的改進算法。文獻[7]在計算錨節(jié)點的平均跳距時引入了蛙跳算法，并用遺傳算法求解未知節(jié)點坐標(biāo)。文獻[8]引入加權(quán)系數(shù)修正節(jié)點的平均跳距，并用模擬退火算法代替最小二乘法求解未知節(jié)點坐標(biāo)。文獻[9]在求解未知節(jié)點坐標(biāo)時引入遺傳模擬退火算法，該算法彌補了模擬退火算法全局搜索能力較差的缺陷，有效提高其定位精度，從而減小誤差傳播。然而，目前對模擬退火算法的改進方法大多需要設(shè)定和控制的參數(shù)較多，且各參數(shù)之間的相互作用也會影響算法結(jié)果，因此在應(yīng)用上存在局限性。

因此，本文在基于模擬退火算法研究的基礎(chǔ)上，針對DV-Hop算法存在的一些問題，提出了一種改進算法。該算法先使用多通信半徑來修正最小跳數(shù)，再結(jié)合模擬退火算法的優(yōu)勢，并對其進行改進，用改進后的算法對錨節(jié)點的平均跳距進行優(yōu)化，然后再使用加權(quán)因子處理未知節(jié)點的平均跳距，最后，采用加權(quán)最小二乘法來求解未知節(jié)點的坐標(biāo)，利用解得冗余信息對未知節(jié)點坐標(biāo)進行二次修正。由仿真結(jié)果可知，本文改進算法比傳統(tǒng)DV-Hop算法具有更好的定位精度。

1 傳統(tǒng)DV-Hop算法

1.1 計算過程

DV-Hop定位算法[10]是由美國Niculescu等提出的，一種基于距離矢量交換協(xié)議來獲得跳數(shù)的算法。具體流程如下：

(1)計算錨節(jié)點與未知節(jié)點的最小跳數(shù)。錨節(jié)點通過泛洪方式[11]將自身數(shù)據(jù)包廣播到整個網(wǎng)絡(luò)中，數(shù)據(jù)包內(nèi)含有錨節(jié)點的位置信息以及跳數(shù)值，未知節(jié)點接收到錨節(jié)點發(fā)出的包并更新自身跳數(shù)信息，將數(shù)據(jù)包的跳數(shù)值加1后并進行保存。為確保網(wǎng)絡(luò)中所有節(jié)點都能獲得每個錨節(jié)點的最小跳數(shù)(hui)信息，接收數(shù)據(jù)包的節(jié)點只需保留較小跳數(shù)值的數(shù)據(jù)包。

(2)估算錨節(jié)點與未知節(jié)點間的距離。每個錨節(jié)點收到其余錨節(jié)點坐標(biāo)和最小跳數(shù)后，根據(jù)式(1)計算其平均跳距

(1)

式中： (xi，yi)， (xj，yj) 為錨節(jié)點i，j的坐標(biāo)，hij表示為錨節(jié)點i，j之間的跳數(shù)，Hopsizei代表錨節(jié)點i平均跳距。未知節(jié)點u到錨節(jié)點i的估算距離dui為

dui=Hopsizei×hui

(2)

(3)估算未知節(jié)點位置。由式(2)求出估算距離dui，再結(jié)合最小二乘法來估算未知節(jié)點的位置。

1.2 誤差分析

(1)傳統(tǒng)的DV-Hop算法是通過最小跳數(shù)來衡量節(jié)點之間的距離，即在錨節(jié)點的通信半徑范圍內(nèi)，無論未知節(jié)點距離錨節(jié)點多遠，跳數(shù)都記為1跳。而未知節(jié)點與錨節(jié)點之間的跳數(shù)越多，則所求節(jié)點的平均跳距誤差也越大，從而影響其定位精度。

(2)在計算錨節(jié)點的平均跳距時，傳統(tǒng)DV-Hop算法利用實際總距離與總跳數(shù)的比值得到，即直線距離表示跳段距離，隨著節(jié)點間跳數(shù)增加，得到的跳段距離誤差也會增大。然后未知節(jié)點采用最近錨節(jié)點的平均跳距作為自身的平均跳距，也會導(dǎo)致較大的定位誤差。

(3)估算未知節(jié)點的定位坐標(biāo)通常采用最小二乘法，但該方法未考慮測量信息而直接使用，并且會產(chǎn)生殘差影響定位精度，造成定位誤差偏大。

因此，針對上述定位誤差產(chǎn)生的原因，本文分別從節(jié)點的最小跳數(shù)、錨節(jié)點和未知節(jié)點的平均跳距、估算未知節(jié)點坐標(biāo)等角度對DV-Hop算法進行改進。

2 改進的DV-Hop算法

2.1 多通信半徑改進最小跳數(shù)

由DV-Hop定位算法計算跳數(shù)的方法可知，若兩點間的歐式距離小于通信半徑，則將其跳數(shù)當(dāng)作1跳。若節(jié)點的分布狀態(tài)如圖1所示，則錨節(jié)點O分別到節(jié)點A、B、C、D的跳數(shù)都為1跳，但圖中明顯可以看出OA的距離小于OD的距離，因此，使用該方法計算節(jié)點間的最小跳數(shù)會產(chǎn)生誤差，并在節(jié)點的定位過程中逐漸積累誤差。

基于以上分析，本文采用4個通信半徑的方式來細化跳數(shù)，從圖1可以看出，未知節(jié)點A、B、C、D到錨節(jié)點O的跳數(shù)分別記為0.25、0.5、0.75、1，從而使得最小跳數(shù)的獲取更加精確，平均跳距的計算也更加準(zhǔn)確。

2.2 改進的模擬退火算法優(yōu)化錨節(jié)點的平均跳距

2.2.1 改進的模擬退火算法

模擬退火算法[12](simulated annealing， SA)利用Metropolis抽樣準(zhǔn)則，在解空間中有一定概率尋找到目標(biāo)函數(shù)的最優(yōu)解。在重點抽樣時，若新解更好，則接受；若更差，則以一定的概率接受。隨著溫度T逐漸趨于0時，則不再接受任何惡化解。同時該算法存在一些問題，即計算時間過長、初始溫度難以確定,且沒有記憶功能導(dǎo)致重復(fù)搜索。

模擬退火算法步驟：

(1)選取合適的目標(biāo)函數(shù)。

(2)初始化參數(shù)：設(shè)置初始解狀態(tài)X0、初試溫度T0、迭代次數(shù)的初始值k=0。

(3)產(chǎn)生新解并計算其目標(biāo)函數(shù)S2。然后計算增量Δ=S2-S1。

(4)根據(jù)Metropolis準(zhǔn)則，若Δ<0，則接受當(dāng)前新解為最優(yōu)解；若Δ≥0，則以概率e-Δ/T接受新解為當(dāng)前最優(yōu)解

(3)

(5)若k小于終止次數(shù)，令k=k+1，然后轉(zhuǎn)向(3)，否則轉(zhuǎn)向(6)。

(6)若沒有到達冷卻狀態(tài)，令T=T×α，α為降溫系數(shù)，α∈(0,1)。 并轉(zhuǎn)向(4)；當(dāng)滿足終止條件，則輸出當(dāng)前的最優(yōu)解，算法結(jié)束。

捕食搜索算法定義請參見文獻[13]，該算法搜索效率高，能夠調(diào)節(jié)搜索區(qū)域的范圍，可與模擬退火算法結(jié)合使用，即基于捕食搜索策略的模擬退火優(yōu)化算法。

該算法主要從以下3個方面改進：

(1)初始溫度改進

溫度T在模擬退火算法中決定了退火走向。而T的初值大小與最優(yōu)解的獲取幾率成正相關(guān)，同時，函數(shù)自身的復(fù)雜程度對T的初值也有較大的影響，因此，為使算法有更高的概率獲取最優(yōu)解，本文引用參考文獻[14]的初值定義

T=T0×ln(1+ρ)

(4)

ρ=log10(f-g)+(m+n)

(5)

T0代表溫度初始值；ρ代表函數(shù)的復(fù)雜程度；f、g分別為函數(shù)的最大值和最小值；m、n分別為函數(shù)的波峰數(shù)和波谷數(shù)。

(2)降溫系數(shù)改進

降溫系數(shù)決定了溫度下降的快慢。為提高算法的搜索效率，需要使初期的退火速率保持較高的數(shù)值，并在退火后期保持下降平緩的特性。新的降溫系數(shù)定義如下

(6)

α為降溫系數(shù)，α∈(0,1)，j代表當(dāng)前的迭代次數(shù)。從式(6)分析可知，若令h=α1/sqrt(j)， 則迭代次數(shù)j與h成正比關(guān)系，當(dāng)?shù)螖?shù)j逐漸增加，h的值也逐漸增大，但取值范圍仍在(0,1)內(nèi)，從而滿足其在初期降溫速度快，且在后期下降平緩的要求。

(3)增加記憶功能

由于傳統(tǒng)的模擬退火算法在進行最優(yōu)解搜索時，有一定的概率會接受當(dāng)前較差的解而遺失最優(yōu)解；并且對訪問過的解還會重復(fù)搜索，造成運行時間增加，因此，本文引入禁忌搜索算法的禁忌表功能，將最優(yōu)解存入禁忌表中，從而避免一些重復(fù)性的數(shù)值搜索。禁忌表中的元素被稱為禁忌對象，禁忌長度是指被禁忌對象不能被選取的迭代次數(shù)。

在實際的操作過程中，給禁忌表中的被禁對象Y一個數(shù)t(禁忌長度)，即被禁對象Y在t步范圍內(nèi)被禁。該禁忌表可以用tabu(Y)=t來記憶，每進行一次迭代，即做運算tabu(Y)=t-1， 當(dāng)tabu(Y)=0 時解禁。其中，禁忌長度的大小十分關(guān)鍵，若禁忌長度過小，很容易造成搜索循環(huán)，過早陷入局部最優(yōu)，若禁忌長度過大，會造成計算時間過長，也會導(dǎo)致計算無法繼續(xù)下去。因此，在本文的改進算法中，禁忌長度t被賦值為10。

2.2.2 優(yōu)化錨節(jié)點的平均跳距

在傳統(tǒng)的DV-Hop算法中，平均跳距的算法是基于無偏估計準(zhǔn)則的。然而，一般情況下的誤差服從高斯分布，由參數(shù)估計理論可知，使用均方誤差準(zhǔn)則[15]比無偏估計更加合理。因此，構(gòu)造計算平均跳距的數(shù)學(xué)模型要基于最小均方誤差準(zhǔn)則，并且利用改進的模擬退火算法進行求解。

由于錨節(jié)點的位置信息已知，根據(jù)兩點間的距離公式可求出錨節(jié)點i到j(luò)的實際距離為

(7)

而錨節(jié)點i與j之間的估計距離可由式(1)和式(2)可得，即d′ij=hij×Hopsizei， 再令δ=|dij-d′ij| 代表實際距離與估計距離之間的誤差，當(dāng)誤差δ越小，代表估計距離越接近實際距離，即所求的Hopsizei越接近最優(yōu)解，因此，要求解合適的自變量Hopsizei，則需要選擇合適的目標(biāo)函數(shù)來進行最小值問題的求解，該目標(biāo)函數(shù)為

(8)

基于以上分析，在利用改進的模擬退火算法求解Hopsizei時，先在解空間 [0,max(dij)] 內(nèi)隨機產(chǎn)生初始解，并根據(jù)式(8)對所求解進行評價，然后再結(jié)合該改進算法的搜索策略來找出Hopsizei的最優(yōu)解。求錨節(jié)點平均跳距的計算步驟如下：

步驟1 初始化各參數(shù)，在解空間 [0,max(dij)] 內(nèi)隨機產(chǎn)生初始解。

步驟2 在當(dāng)前溫度下，根據(jù)初始解的鄰域隨機取5個解，并且代入目標(biāo)函數(shù)(8)中求其相應(yīng)的目標(biāo)值，按照升序排列并加入限制，即restriction[1-5]，初始解的目標(biāo)值存放在restriction[0]，并設(shè)best=restriction[0]，將其放入禁忌表中。此外，設(shè)限制等級L=0，counter=0。

步驟3 若L

步驟4 在當(dāng)前限制等級下產(chǎn)生鄰域解，選擇鄰域最優(yōu)解，并判斷是否在禁忌表中出現(xiàn)過，若出現(xiàn)則重新產(chǎn)生鄰域解；設(shè)Δ為當(dāng)前值與目標(biāo)值之差，根據(jù)Metropolis準(zhǔn)則，若Δ<0，則接受當(dāng)前新解為最優(yōu)解；若Δ>0，則以概率e-Δ/T接受新解為當(dāng)前最優(yōu)解。接受轉(zhuǎn)步驟5，不接受轉(zhuǎn)步驟6。

步驟5 設(shè)限制等級L=0，counter=0，重新計算限制，并將新解加入禁忌表中，轉(zhuǎn)步驟4。

步驟6 令counter=counter+1，如果counter>Cthreshold(用于增大限制等級L的指針閾值)，則轉(zhuǎn)步驟7，跳出當(dāng)前限制等級，否則，轉(zhuǎn)步驟4。

步驟7 令L=L+1，counter=0，如果L=2，則令L=LhighThreshold(LhighThreshold表示較高的適應(yīng)等級，該值設(shè)為4)，此時由鄰域限制搜索轉(zhuǎn)為廣域搜索，同時轉(zhuǎn)步驟3。

步驟8 隨著溫度降低，該過程會產(chǎn)生新的解，并把新解與禁忌表中的對象對比，若沒有相同解，則轉(zhuǎn)步驟2；若有相同解，則重新產(chǎn)生新解，若多次產(chǎn)生的解在禁忌表中都能找到，則代表已無最優(yōu)解，結(jié)束當(dāng)前循環(huán)，否則，轉(zhuǎn)步驟2。

步驟9 重復(fù)步驟3～步驟8，直到收斂條件滿足時結(jié)束。

步驟10 在禁忌表中尋找最優(yōu)解，并輸出最優(yōu)跳距Hopsizei。

2.3 未知節(jié)點平均跳距的加權(quán)處理

在傳統(tǒng)DV-Hop算法中，未知節(jié)點是把距離最近的錨節(jié)點的平均跳距值作為自身的平均跳距，但是在實際的網(wǎng)絡(luò)中，節(jié)點分布在不同的區(qū)域其自身的狀況也是不同的，且平均每跳距離也不相同，這明顯會導(dǎo)致較大的誤差，因為網(wǎng)絡(luò)中單個錨節(jié)點的平均跳距并不能反映網(wǎng)絡(luò)的真實屬性。因此，可以采用多個錨節(jié)點來計算其平均跳距的方式，即引用加權(quán)系數(shù)來減小誤差。加權(quán)系數(shù)公式如下

(9)

式中：n為未知節(jié)點可以通信的錨節(jié)點個數(shù)；hi為錨節(jié)點i與未知節(jié)點的最小跳數(shù)值。由此獲取的未知節(jié)點的加權(quán)平均跳距為

(10)

通過對式(9)、式(10)的處理，每個與未知節(jié)點進行通信的錨節(jié)點，其平均跳距都可以參與未知節(jié)點平均跳距的計算，即每個錨節(jié)點的平均跳距都是按照與未知節(jié)點的距離遠近來進行加權(quán)，從而使每個未知節(jié)點在依據(jù)平均跳距來計算其自身坐標(biāo)時使之更加貼近真實的網(wǎng)絡(luò)情況。

2.4 求解未知節(jié)點的坐標(biāo)

如圖2所示，假設(shè)未知節(jié)點U的坐標(biāo)為(x，y)，錨節(jié)點A1、A2、…、An的坐標(biāo)為 (x1，y1)， (x2，y2)， …， (xi，yi) (i=1，2，…，n)，di為錨節(jié)點Ai與未知節(jié)點U間估算的距離。

由兩點間的距離公式可得方程組

(11)

由于di的獲取本就存在誤差，若再進行平方運算，會使其誤差增大，使得定位精度下降。因此直接使用開平方的方式，從而避免因取平方造成的誤差加大，然后再將上式的前(n-1)行全部減去最后一行，如方程組(12)所示

(12)

(13)

(14)

(15)

(16)

在求解未知節(jié)點坐標(biāo)的過程中，每個參數(shù)的設(shè)置都采用了相同的權(quán)值，也就是說有一樣的定位精度，若此時采用最小二乘法[16]直接計算未知節(jié)點坐標(biāo)，所造成的誤差會積累到最終的結(jié)果中。因此，本文采用加權(quán)最小二乘法來進一步減小定位誤差，即引入權(quán)重矩陣W，該矩陣為對稱的正定矩陣，如式(17)所示

(17)

其中，Wr,i表示未知節(jié)點r與錨節(jié)點i的權(quán)重因子，hr,i表示未知節(jié)點r到錨節(jié)點i的最小跳數(shù)。公式如下

(18)

最后結(jié)合普通最小二乘法可得

X=(ATWA)-1ATWB

(19)

2.5 修正未知節(jié)點的坐標(biāo)

由式(19)解得未知節(jié)點坐標(biāo)(x，y)和r后，則應(yīng)該判斷是否滿足r=x2+y2， 若滿足條件，該解即為所求坐標(biāo)，若不滿足該條件，則令

(20)

將式(20)帶入r=x2+y2中，求出參數(shù)a，然后得出x1和y1的值，最后修正的未知節(jié)點坐標(biāo)為

(21)

3 仿真實驗與分析

3.1 仿真實驗

為驗證該改進算法的性能，在MATLAB2016b環(huán)境下進行仿真實驗。先設(shè)置100m×100m的正方形區(qū)域，再將100個節(jié)點隨機分布在該區(qū)域中。本文改進算法將與傳統(tǒng)DV-Hop算法、文獻[6]所提算法、文獻[8]所提算法就錨節(jié)點數(shù)、通信半徑兩方面性能進行比較。

改進模擬退火算法的默認參數(shù)為：設(shè)定溫度T的初始值為200，衰減因子設(shè)為0.96，限制等級為restriction[0]到restriction[5]，指針閾值Cthreshold設(shè)為1，為使算法更加穩(wěn)定，每種算法循環(huán)運算50次并取平均值來當(dāng)作最后的定位誤差。假設(shè)總結(jié)點數(shù)為100個，錨節(jié)點數(shù)為10個，該節(jié)點的初始分布如圖3所示。

定義平均定位誤差[17]

(22)

3.2 錨節(jié)點個數(shù)對定位算法的影響

在圖4中，DWDV-Hop為文獻[6]的改進算法；SA+WDV-Hop為文獻[8]的改進算法；SAPS+WDV-Hop為本文改進的DV-Hop算法?？偣?jié)點數(shù)為100個，錨節(jié)點的通信半徑為50 m，錨節(jié)點數(shù)從10個增長到50個(每次增長5個)。4種算法在相同條件下，隨著錨節(jié)點數(shù)量的增加，相應(yīng)的定位誤差都在逐漸減小并趨于平緩，這是因為錨節(jié)點的增多使得定位節(jié)點的信息更詳細，從而使得定位誤差降低。由圖4可知，在較低密度錨節(jié)點的網(wǎng)絡(luò)中，本文所改進的DV-Hop算法明顯優(yōu)于傳統(tǒng)DV-Hop算法，并且與文獻[6]、文獻[8]所提算法相比，其定位精度分別提升約7%和4%。

3.3 通信半徑對定位算法的影響

在圖5中，總節(jié)點數(shù)為100個，錨節(jié)點數(shù)為30個，隨機分布在100m×100m的正方形區(qū)域中，并且通信半徑從20 m增長到50 m(每次增長5 m)，其它條件保持不變。觀察發(fā)現(xiàn)，隨著通信半徑R的逐漸增大，這4種算法的平均定位誤差都在逐漸減小，但通信半徑在大于40 m之后出現(xiàn)了一定程度的上升，經(jīng)過分析可知，由于通信半徑的增大會使網(wǎng)絡(luò)連通性變好，所以定位誤差一開始會降低，但當(dāng)通信半徑過大，會使平均跳距誤差增大從而導(dǎo)致定位精度下降。由圖5可知，本文算法的定位精度明顯優(yōu)于傳統(tǒng)DV-Hop算法，并且與文獻[6]所提算法相比，在定位精度上提升約8%，與文獻[8]相比，定位精度提升約3%。

3.4 算法的復(fù)雜度分析

與傳統(tǒng)DV-Hop算法相比，改進算法在運算量上增加了一些額外開銷，該額外開銷主要來源于在計算錨節(jié)點的平均跳距時，使用改進的模擬退火算法來優(yōu)化錨節(jié)點的平均跳距，該改進算法繼承了捕食搜索算法的區(qū)域精密搜索和廣域搜索方式，增加了內(nèi)外雙循環(huán)運算，即每個限制等級下都要尋找最優(yōu)解，此外，模擬退火算法本身隨著溫度下降產(chǎn)生的新解也要參與循環(huán)運算，直至滿足收斂條件時結(jié)束，這些都在一定程度上導(dǎo)致運行時間增加。因此，改進算法是以一定的額外運算開銷為代價取得更高的定位精度。

4 結(jié)束語

針對DV-Hop算法存在的誤差，本文提出一種改進算法，先使用多通信半徑來修正最小跳數(shù)，再引入改進的模擬退火算法計算錨節(jié)點的平均跳距，并使用加權(quán)因子處理未知節(jié)點的平均跳距，從而減小平均跳距引起的誤差，最后在估算未知節(jié)點坐標(biāo)采用不直接對方程進行平方運算的方式，并采用加權(quán)最小二乘法來求解未知節(jié)點的坐標(biāo)，以及利用解得冗余信息對未知節(jié)點坐標(biāo)進行二次修正。仿真實驗證實，本文提出的改進算法在定位精度上有較大幅度的提升，并且具有良好的穩(wěn)定性，但是，由于改進算法在錨節(jié)點計算平均跳距引入了改進的模擬退火算法，增加了一部分計算量，導(dǎo)致能耗增大。因此，下一步的研究將考慮在保持定位精度的條件下如何減少能耗。