陳玲君

（紹興職業(yè)技術(shù)學(xué)院，浙江紹興　312000）

一種改進的DV-HOP算法在無線傳感網(wǎng)中的定位研究

陳玲君

（紹興職業(yè)技術(shù)學(xué)院，浙江紹興312000）

WSN中的信息傳遞主要通過傳感器來進行傳遞信號，針對無線傳感中DV-Hop算法在節(jié)點定位上存在精度低的問題，首先提出建立雙曲線二維模型用來確定錨節(jié)點與未知節(jié)點的距離關(guān)系，其次設(shè)定誤差系數(shù)使得傳感器節(jié)點之間的誤差降低，最后采用斯蒂芬森迭代法（Steffensen）定位方法對傳感器節(jié)點進一步進行定位修正；仿真實驗表明算法的在遠程控制的中定位精度提高，傳感器之間能量消耗降低，具有一定的推廣價值。

無線傳感網(wǎng)絡(luò)；雙曲線二維模型；誤差系數(shù)；斯蒂芬森

0　引言

伴隨著微電子技術(shù)和計算無線通信技術(shù)的發(fā)展，無線傳感網(wǎng)絡(luò) （wireless sensor network，WSN）得到了迅速的發(fā)展。傳感器之間的信息傳遞主要依賴于節(jié)點位置的分布，因此節(jié)點的準確定位是目前研究的主要的問題［1］。WSN中的節(jié)點定位主要是指錨節(jié)點定位和未知節(jié)點定位，其中錨節(jié)點是指少量的帶有GPS定位裝置的節(jié)點，未知傳感器節(jié)點位置的定位需要通過錨節(jié)點來進行自身的定位。國內(nèi)外學(xué)者對于DV-HOP算法進行了廣泛的研究，文獻［2－3］提出采用智能算法來對DV-Hop的定位結(jié)果進行了優(yōu)化具有很好的穩(wěn)定性；文獻［4］提出一種基于加權(quán)的三維DV-Hop定位算法，該算法降低定位誤差，但是權(quán)值的設(shè)置需要進一步討論；文獻［5］提出了將接收信號強度指示的改進算法，降低了誤差30%～45%；文獻［6］提出根據(jù)鄰居節(jié)點間的距離對跳數(shù)進行加權(quán)處理，修正平均跳距，縮小未知節(jié)點被包圍的三角形區(qū)域，篩選出最終進行坐標計算的錨節(jié)點，其缺點是區(qū)域的設(shè)置受到其他條件的影響；文獻［7］提出了一種普適性反饋機制，引入位置調(diào)整因子和基于RSSI的跳距優(yōu)化算法，實驗表明，在資源變化的網(wǎng)絡(luò)計算環(huán)境中，所提出的定位算法能夠顯著地提高定位精度，且具有更強的穩(wěn)定性；文獻［8］提出了對DV-Hop算法中的平均跳距值進行調(diào)整，使得錨節(jié)點與未知節(jié)點之間的距離誤差變小，缺點是實際環(huán)境難以應(yīng)用；文獻［9］提出了一種綜合考慮所有信標節(jié)點的平均跳距并引入權(quán)值修正，該算法使得網(wǎng)絡(luò)平均跳距和節(jié)點位置估計值更加準確。文獻［10］提出從錨節(jié)點組合的有效性和節(jié)點早定位能減少因等待錨節(jié)點信息所耗的時間和能量兩方面考慮，并進行改進，仿真實驗表明算法效果良好。

為了進一步提高傳感器定位的精度，本文在DV-HOP算法的基礎(chǔ)上引入斯蒂芬森迭代法（Steffensen）對傳感器節(jié)點定位進行修正。分析DV-Hop算法存在的不足，建立雙曲線二維方程，通過設(shè)定誤差系數(shù)降低偏差，采用Steffensen迭代法對DV-Hop算法定位結(jié)果進行檢驗和修正，仿真實驗表明本文的算法能夠有效的提高定位性能。

1　DV-Hop算法及誤差分析

1.1DV-Hop定位算法

DV-Hop算法的具體步驟如下：

1）錨節(jié)點向周圍的節(jié)點廣播數(shù)據(jù)包，未知節(jié)點收到錨節(jié)點的最小跳數(shù)，進行加1后轉(zhuǎn)發(fā)給下一個節(jié)點。

2）錨節(jié)點收到其他節(jié)點的信息和跳數(shù)后，計算平均每跳的距離進行估算，按照公式（1）。

式中，分別是錨節(jié)點i和j的坐標，hop Sij是兩個錨節(jié)點i和j間的最小跳數(shù)。

3）錨節(jié)點與未知節(jié)點之間估計距離為：

Li=Si×Hop Size（2）

根據(jù)未知節(jié)點與各錨節(jié)點間的距離，采用多邊法計算未知節(jié)點的坐標，具體為：

式中，（xi，yi）為未知節(jié)點的坐標；（x1，y1），（x2，y2），…（xj，yj）為該未知節(jié)點所記錄錨節(jié)點的坐標。因此未知節(jié)點（xi，yi）通過公式（4）得到1.2誤差分析在DV-HOP算法中主要采用錨節(jié)點之間的距離來近似估算未知節(jié)點到錨節(jié)點之間的距離，但具有一定的局限性，主要是因為取決于錨節(jié)點是否分布均勻，但實際情況恰恰相反，錨節(jié)點的定位受到很多因素的影響，當網(wǎng)絡(luò)中的錨節(jié)點之間分布密集的時候，網(wǎng)絡(luò)中的未知節(jié)點之間的距離接近于實際距離，但當錨節(jié)點分布稀疏的時候，偏差就容易產(chǎn)生，如圖1所示。

圖1　節(jié)點分布造成的誤差

因此DV-Hop算法測量所得到距離L與實際距離之間必然存在一定誤差，假設(shè)fn為未知節(jié)點到錨節(jié)點之間的測距誤差系數(shù)，則未知節(jié)點到錨節(jié)點的距離為公式（5）所示（xi-xj）2+（yi-yj）2=L2j+fj（5）根據(jù)公式（3）得到未知節(jié)點坐標滿足下式：

求解未知節(jié)點坐標（xi，yi），使得

當（7）式取得最小值時，總誤差最小，未知節(jié)點的定位就能接近真實值。即滿足下式的未知節(jié)點坐標：

通過上述方式把DV-Hop定位誤差問題成功地轉(zhuǎn)化一個非線性優(yōu)化問題，通過斯蒂芬森迭代法對式（8）進行求解，進一步優(yōu)化傳感器定位精度。

2　WSN中的改進的DV-Hop算法

2.1基于雙曲線的二維平面

為了降低研究的復(fù)雜度，本文選擇在二維平面作為研究對象，假設(shè)在有M個傳感器節(jié)點，第i個未知節(jié)點坐標為Mi，j =［xi，yi］T（i=1，2，…，n，j=1，2，……，n），錨節(jié)點的坐標為Sp=［a，b］T，因此每一個節(jié)點發(fā)送源與傳感器之間的距離為||Mi-Sp||。以選取其中第j個未知節(jié)點作為參考節(jié)點，通過觀測值κi，j（i=1，……N）用來表示在錨節(jié)點與未知節(jié)點之間的關(guān)聯(lián)關(guān)系，設(shè)定關(guān)于錨節(jié)點與未知節(jié)點之間的關(guān)系為雙曲線方程，如圖2所示。

圖2　WSN中的雙曲線定位

設(shè)定信號之間的傳播速度為v，則錨節(jié)點與未知節(jié)點之間的距離為d=vκi，j，構(gòu)建以錨節(jié)點為中心的構(gòu)建N個雙曲線方程di，j=di-dj，通過對N個方程求解得到定位的節(jié)點坐標。由于該方程式非線性方程，所以，需要對其進行線性處理，由d2i=（di，j+dj）2進行拓展得到如下：

d2i，j+2di，jdj+3d2i=M2i，j+Sp-2SMi，j（9）對公式（9）進行局部處理，得到公式（10）

將公式（10）帶入公式（9）得到如下：

M2i，j-S2p-2（Mi，j-M1，1）TSp=d2i，j+2di，jdj（11）通過公式（11），將問題轉(zhuǎn)換為線性方程的求解，代入（8）進行求解。

2.2誤差系數(shù)設(shè)定

由于錨節(jié)點與未知節(jié)點的實際距離與理論距離肯定存在誤差，因此通過設(shè)定誤差系數(shù)來減少，之前描述了未知節(jié)點與錨節(jié)點之間的實際距離為Di，j，

根據(jù)公式 （12）和公式 （3）得到未知節(jié)點到錨節(jié)點之間的總誤差ε，如公式（13），誤差系數(shù)的確定如公式（14）

式 （14），n*（n-1）/2表示n個節(jié)點之間的跳數(shù)總和，fij表示誤差系數(shù)

2.3Steffensen算法

對于非線性方程f（x）=0，可化成等價的方程：x=φ（x）（15）式中，φ（x）稱為迭代函數(shù)。

Steffensen迭代法是一種改進的不動點迭代法，具有二階收斂速度、計算精度等優(yōu)點，迭代函數(shù)為：

Steffensen迭代公式為：

Steffensen算法流程如下：

1）設(shè)置最大迭代次數(shù)N和精度ε，令k=0。

2）計算yk=φ（xk），zk=φ（yk），。

4）若k=N，則停止計算；否則，置k=k+1，轉(zhuǎn)到步驟2）。

2.4Steffensen修正DV-Hop定位誤差

除了對誤差系數(shù)進行設(shè)定之外，還需要（8）取得最小值的必要條件是：

其中：

則求min（fitness（））的最優(yōu)解問題轉(zhuǎn)化為求使得Δi取到最小值時未知節(jié)點的坐標（xi，yi）的問題。具體步驟為：

1）按照Steffensen迭代公式（17）的第一步，對變量xi和yi進行迭代，有：

式中，xi和yi為采用DV-Hop算法的傳感器節(jié)點估計位置，將其作為迭代初值。

2）根據(jù)式（17）對未知節(jié)點坐標進行更新迭代操作：

3）將新的未知傳感器節(jié)點的坐標（xi，yi）代入式（20）中，算出Δi的值。

4）當?shù)螖?shù)達到所設(shè)的最大值，迭代算法停止，求出最接近真實值的未知節(jié)點的坐標，使得定位誤差最小。

3　算法仿真與分析

進行仿真實驗的硬件選擇CPU為酷睿i3，4GDDR3和硬盤為500 G，軟件采用matlab2012。采用本文算法與基本DVHOP算法以及文獻［2］算法進行比較。選擇100 m*100 m的區(qū)域，選擇1000個節(jié)點，其中220個為錨節(jié)點，780為未知節(jié)點，所有節(jié)點都進行隨機分布。采用誤差計算公式（24）作為比較的標準，其中（x′i，y′i）和（xi，yi）分別表示估算未知和實際未知，R為節(jié)點通信半徑，N為節(jié)點個數(shù)，結(jié)果如下

圖3表示在不同的節(jié)點密度與定位誤差關(guān)系。從圖中發(fā)現(xiàn)3種算法伴隨著節(jié)點密度的增大都對定位誤差進行了優(yōu)化，從中發(fā)現(xiàn)本文算法所產(chǎn)生的誤差是的最小，相比與DV-HOP算法平均優(yōu)化了21.2%，相比與文獻［2］算法優(yōu)化了7.23%，這說明本文算法能夠獲得更精確的定位結(jié)果。

圖3　節(jié)點密度對定位誤差的影響

圖4表示在不同的節(jié)點通信半徑與定位誤差的關(guān)系。節(jié)點通信半徑關(guān)系到未知節(jié)點定位準確性，選擇節(jié)點半徑從5到15米的范圍，從圖中可以發(fā)現(xiàn)3種算法定位誤差都伴隨著節(jié)點通信半徑不斷增大而減少，這說明3種算法都的改進都改善了與節(jié)點通信半徑之間的關(guān)系，本文算法曲線平緩，說明節(jié)點半徑的增大不影響算法的穩(wěn)定性，因此本文算法的的定位誤差相比與其他兩種算法能夠更好的完成更精確定位。

圖4　節(jié)點通信半徑對定位誤差的影響

圖5表示錨節(jié)點比例與定位誤差的關(guān)系。3種算法中錨節(jié)點的比例按照2%到20%的順序增加，從圖中發(fā)現(xiàn)本文的算法相比于其他兩種算法在錨節(jié)點比例不斷增大的情況下，定位誤差相比與DV-HOP算法降低了12.3%，相比與文獻［2］算法降低了5.2%，這說明錨節(jié)點的數(shù)量增多的情況，本文算法具有更加明顯的定位優(yōu)勢。

圖6表示節(jié)點能量消耗與定位誤差的關(guān)系。從圖中發(fā)現(xiàn)，本文算法相比于DV-Hop、文獻［2］算法的網(wǎng)絡(luò)能量消耗都伴隨著節(jié)點數(shù)量的不斷增多而降低，DV-Hop算法的能量消耗曲線振幅最大，說明能量消耗不穩(wěn)定，并且消耗最快，文獻［2］算法次之，本文算法的能量消耗曲線平緩。說明本文算法在一定程度上可以有效提高網(wǎng)絡(luò)能量利用率。

4　結(jié)束語

圖5　錨節(jié)點的比例對定位誤差的影響

圖6　節(jié)點能量能量消耗比

針對WSN中的DV-Hop算法定位的問題，本文在DVHOP算法的基礎(chǔ)上，引入雙曲線二維平面方程來定位錨節(jié)點與未知節(jié)點的關(guān)系，其次通過引入誤差定位系數(shù)降低距離誤差，采用Steffensen迭代法對DV-Hop算法定位結(jié)果進行分析和修正，實現(xiàn)精確定位。通過在仿真實驗中3種算法的比較，本文的算法能夠有效的提高了定位精度，具有一定的實用性。

［1］黃毅，胡愛群.無線傳感器網(wǎng)絡(luò)定位算法綜述［J］.電信科學(xué)，2010，20（7）：69-74.

［2］曹欲曉，張倩，李艷冰.基于蝙蝠算法的DV-Hop定位改進［J］.計算機測量與控制，2015，23（4）：1273-1275.

［3］張萬禮，宋啟祥.遺傳算法的DV-Hop算法改進［J］.重慶大學(xué)學(xué)報，2015，38（3）：159-166.

［4］李琳，趙可，林志貴.基于加權(quán)的三維DV-Hop定位算法［J］.控制工程，2015，22（4）：761-764.

［5］鄔春明，張金強，焦龍龍.基于RSSI跳數(shù)連續(xù)的DV-HOP改進算法［J］.重慶郵電大學(xué)學(xué)報（自然科學(xué)版），2015，27（2）：184-187.

［6］蔡麗萍，蔣晶晶，洪利.一種改進的DV-HOP定位算法［J］.微電子學(xué)與計算機，2015，32（4）：120-124.

［7］柳飛，酆廣增.基于RSSI和反饋機制的無線傳感器網(wǎng)絡(luò)定位優(yōu)化算法［J］.南京郵電大學(xué)學(xué)報（自然科學(xué)版），2015，35（2）：108-113.

［8］蘇兵，薛偉杰，王洪元.一種WSN非測距定位DV-Hop算法的誤差改進方法［J］，計算機測量與控制，2013，215）：1357-1359.

［9］周杭霞，崔晨，葉佳駿.一種基于加權(quán)處理和誤差修的DV-Hop定位算法研究［J］.感技術(shù)學(xué)報，2014，27（12）：1699-1703.

［10］鄭遠，蔡宇，趙銳.一種兼顧性能與能耗的DV-Hop改進算法 ［J］.計算機應(yīng)用與軟件，2014，31（4）：269-272.

Research on Positioning of an Improved DV-HOP Algorithm in Wireless Sensor Networks

Chen Lingjun
（Shaoxing Vocational&Technical College，Shaoxing312000，China）

In information transfer in WSN，signals are transferred mainly through the sensor.Aiming at the low accuracy of DV-Hop algorithm in node positioning in wireless sensor，this paper first proposes establishing hyperbolic two-dimensional model to determine the distance between anchor nodes and unknown nodes.Then，set the error coefficient to reduce errors between nodes of the sensor.Finally，Steffensen positioning method is used to modify the positioning of sensor's nodes.Simulation experiment shows that algorithm in this paper improves the positioning accuracy in remote control，and energy consumption between sensors is reduced，so it has certain promotion value.

wireless sensor network；hyperbolic two-dimensional model；error coefficient；Steffensen

1671-4598（2016）05-0305-04

10.16526/j.cnki.11-4762/tp.2016.05.084

TP212.9

A

2015-11-30；

2015-01-04。

國防預(yù)先研究項目（51327030104）。

陳玲君（1983-），女，講師，碩士，主要從事智能控制方向的研究。