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

陳玲君

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

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

陳玲君

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

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

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

0　引言

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

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

1　DV-Hop算法及誤差分析

1.1DV-Hop定位算法

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

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

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

式中，分別是錨節(jié)點(diǎn)i和j的坐標(biāo)，hop Sij是兩個(gè)錨節(jié)點(diǎn)i和j間的最小跳數(shù)。

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

Li=Si×Hop Size（2）

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

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

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

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

求解未知節(jié)點(diǎn)坐標(biāo)（xi，yi），使得

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

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

2　WSN中的改進(jìn)的DV-Hop算法

2.1基于雙曲線的二維平面

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

圖2　WSN中的雙曲線定位

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

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

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

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

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

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

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

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

2.3Steffensen算法

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

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

Steffensen迭代公式為：

Steffensen算法流程如下：

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

2）計(jì)算yk=φ（xk），zk=φ（yk），。

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

2.4Steffensen修正DV-Hop定位誤差

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

其中：

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

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

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

2）根據(jù)式（17）對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行更新迭代操作：

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

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

3　算法仿真與分析

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

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

圖3　節(jié)點(diǎn)密度對(duì)定位誤差的影響

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

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

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

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

4　結(jié)束語(yǔ)

圖5　錨節(jié)點(diǎn)的比例對(duì)定位誤差的影響

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

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

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

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

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

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

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

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

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

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

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

［10］鄭遠(yuǎn)，蔡宇，趙銳.一種兼顧性能與能耗的DV-Hop改進(jìn)算法 ［J］.計(jì)算機(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。

國(guó)防預(yù)先研究項(xiàng)目（51327030104）。

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