基于人工魚群算法的dv-hop定位算法改進研究

韋世雄

摘要：隨著無線網(wǎng)絡傳感器在各行各業(yè)的廣泛應用，實際應用場景中的許多問題逐漸浮現(xiàn)出來，尤其是定位算法缺陷。文章主要從無線傳感器定位的dv-hop算法局限性出發(fā)，指出其用跳段距離代替直線距離的顯著缺點，并基于各項研究，提出應用人工魚群算法的全局密集網(wǎng)絡特點對dv-hop定位算法進行改進。經(jīng)驗證，基于人工魚群算法改進后的dv-hop定位算法能顯著弱化無線傳感器節(jié)點定位誤差大，減少節(jié)點硬件開銷，提升無線傳感器的定位精度和效率。

關(guān)鍵詞：人工魚群算法；dv-hop；定位算法；無線網(wǎng)絡傳感器

中圖分類號：TN915.03

文獻標志碼：A

0 引言

隨著定位技術(shù)的發(fā)展，在計算機視覺領(lǐng)域中，位置信息作為重要的數(shù)據(jù)挖掘依據(jù)與問題處理過程參照，受到越來越多的學者關(guān)注。無線網(wǎng)絡傳感器的重要內(nèi)容之一就是定位算法。傳統(tǒng)的定位算法主要是dv-hop算法，其具有實現(xiàn)簡單、節(jié)點無需額外增加硬件要求的優(yōu)勢。

在具體的應用和發(fā)展過程中，dv-hop的一些缺陷也逐漸隨著應用場景的增加和需求的變換浮現(xiàn)，這些問題嚴重影響著無線網(wǎng)絡傳感器的定位精度、連接效率和應用體驗。

1 dv-hop定位算法在當前應用場景中出現(xiàn)的問題

dv-hop作為定位算法中的經(jīng)典代表之一，其節(jié)點定位是基于非測距的，即用跳段距離代替直線距離。應用這種定位方式的不足是定位精度低，即在計算平均跳距和定位坐標的時候容易產(chǎn)生誤差。

2 dv-hop定位算法精度不佳的原因分析

這種誤差主要出現(xiàn)于估算位置節(jié)點坐標的場景下，未知節(jié)點在估算距離時常常依賴最近錨節(jié)點的平均跳距，對網(wǎng)絡中節(jié)點位置密度有很大的限制要求。研究人員可先從dv-hop定位算法的具體步驟特點展開討論。

2.1 dv-hop定位算法的定位步驟

關(guān)于dv-hop定位算法的誤差分析要先了解dv-hop定位的具體步驟。其定位過程一般分為以下幾個步驟。

第一步，錨節(jié)點通過無線網(wǎng)絡傳感器向全網(wǎng)節(jié)點發(fā)送數(shù)據(jù)信息，相應的節(jié)點在接收到信息后，會通過更新最小值來獲得錨節(jié)點的最小跳數(shù)。

第二步，測算錨節(jié)點和未知節(jié)點之間的距離。不同的節(jié)點都會通過周圍通信錨節(jié)點的坐標信息和位置數(shù)據(jù)來計算自身的平均跳距。

第三步，在估算自身節(jié)點位置的時候，普通節(jié)點往往使用的方式是三邊測量法或者最小二乘法。

2.2 誤差分析

本研究提出的對dv-hop定位算法的誤差分析側(cè)重從其定位步驟展開^［1］。

首先，通信半徑內(nèi)節(jié)點的值恒定。不論采用何種定位算法，其節(jié)點都是隨機分布的。在通信半徑之內(nèi)，節(jié)點之間所有的距離都被記為1跳，經(jīng)過不斷疊加，節(jié)點越少，誤差就越大。

其次，考慮平均距離的影響。這種定位算法將平均跳距和最小跳數(shù)的乘積作為節(jié)點間實際距離的計算方式。如果平均距離原本就存在誤差，那么誤差就越大。

最后，計算未知節(jié)點坐標。dv-hop定位算法對于初始值較為敏感，應用三邊測量法計算節(jié)點之間的位置，必然會受到初始值的深刻影響，致使定位精度出現(xiàn)極大偏差。

3 dv-hop定位算法誤差減小的策略——人工魚群算法的應用

通過上述分析，本文從dv-hop定位算法的距離估算角度出發(fā)，提出了基于人工魚群算法來對改進dv-hop定位誤差的解決策略。

3.1 人工魚群算法的概念

3.1.1 人工魚群算法提出背景

人工魚群算法是根據(jù)魚群集體覓食的特點而模擬的一種尋求最優(yōu)解的定位算法。這是因為魚群在尋找食物時，常常會將食物濃度作為食物來源和方向的判斷依據(jù)。當食物的濃度達到一定程度，魚群就會自覺朝著食物的來源方向游去，同時許多覓食的魚之間還會出現(xiàn)追尾情況，這樣多個魚群就能都找到食物，也可以認為這是魚群之間的一種分布式合作覓食策略。這種群體性的合作方式算法智能性較強，有助于解決一些最優(yōu)解問題。

3.1.2 人工魚群算法的具體內(nèi)容

人工魚群算法將需要解決的定位無線網(wǎng)絡空間假設為一個求解空間。將不同節(jié)點間的定位看做一種協(xié)作和競爭。當需要求解定位距離的時候，求解空間的變換會對節(jié)點估測結(jié)果產(chǎn)生重要的影響。同時，不同節(jié)點之間的位置變換也會對求解空間產(chǎn)生相應的影響。在人工魚群算法中，個體活動會對整個無線網(wǎng)絡空間傳感器的定位坐標產(chǎn)生關(guān)鍵作用，也就是各節(jié)點位置和整體的求解空間相互作用，才能使整體的傳感器定位數(shù)值獲得全局最優(yōu)解，而不是局部的最優(yōu)解。

3.2 人工魚群算法在改進 dv-hop定位算法中的應用

3.2.1 加入RSSI加權(quán)質(zhì)心算法

假設某一求解空間中有n個錨節(jié)點，其坐標分別設為（x₁，y₁），（x₂，y₂）……（x_n，y_n）^［2］，這些錨節(jié)點與需要定位的節(jié)點之間距離用RSSI來測量，其距離分別假設為d₁，d₂，d₃……d_n。本研究利用三邊測量法求得需要定位的節(jié)點坐標為（x，y），二者關(guān)系如公式（1）所示：

對于與需要定位的節(jié)點周圍相關(guān)的n個錨節(jié)點而言，其誤差函數(shù)如公式（2）所示：

在具體的應用過程中，不同的情況需要調(diào)整不同錨節(jié)點的加權(quán)值。如果距離較遠，則考慮應用較小的權(quán)值；如果距離較近，則可使用較大的權(quán)值。此外，采用待定位節(jié)點與錨節(jié)點距離的倒數(shù)作為誤差函數(shù)的加權(quán)系數(shù)，是一種構(gòu)造人工魚群算法的適應度函數(shù)。具體計算過程如公式（3）所示：

基于人工魚群算法結(jié)合加權(quán)質(zhì)心算法，對傳統(tǒng)的dv-hop定位算法進行改進，可以通過記錄未知節(jié)點與錨點之間的估測距離，并將所得數(shù)值與實際的距離進行比較，獲得誤差最小、精度較高的數(shù)值，這樣配合的方式在全網(wǎng)求解空間內(nèi)獲取的節(jié)點位置更為精準^［3-4］。

3.2.2 建立仿真實驗環(huán)境Matlab平臺

基于dv-hop定位算法的幾個步驟，在Matlab平臺建立一個基于人工魚群質(zhì)心算法在不同錨節(jié)點密度、不同節(jié)點密度和不同的節(jié)點通信半徑場景下的求解區(qū)域空間。將求解空間設定為100 m×100 m的正方形場域。將所有的未知節(jié)點和錨節(jié)點都隨機分布在這個區(qū)域內(nèi)。將人工魚群算法的群內(nèi)解的個數(shù)設定為50，記為N，迭代次數(shù)設為100，記為IT，擁擠度因子設定為1，記為δ，視野visual設定為10，步長step為8。為最大限度減少實驗中受到的誤差干擾，本次實驗將每組參數(shù)獨立運行50次^［5］，其定位誤差將以50次運行的結(jié)果平均值為準，其定位誤差error計算過程如公式（4）所示：

4 應用人工魚群算法后dv-hop定位算法的改進效果

在仿真實驗平臺中，當總節(jié)點數(shù)量為100，節(jié)點的通信半徑為30 m時，同時錨節(jié)點的數(shù)量由12個增加至30個的場景下，可獲得不同錨節(jié)密度下具體的定位誤差對比。

隨著區(qū)域內(nèi)錨節(jié)點密度的不斷增加，應用不同的算法定位誤差都與錨節(jié)點個數(shù)呈現(xiàn)負相關(guān)關(guān)系，即定位誤差隨著錨節(jié)點密度的增加而降低。由此可知，增加錨節(jié)點數(shù)量，可以使dv-hop的算法誤差降低。

這也是基于dv-hop定位只計算平均跳距和定位坐標產(chǎn)生誤差而提出的算法?；谌斯~群算法是將平均跳距擴展為全域的平均跳距，而不再是單個錨節(jié)點的平均跳距。利用人工魚群算法，可以克服dv-hop定位算法跳距默認為1的缺陷，當未知節(jié)點和錨節(jié)點都處于1跳區(qū)域時，能保持平均跳數(shù)精度不變^［6］。

在作用域擴大到不再局限于錨節(jié)點周圍半徑時，如果錨節(jié)點和未知節(jié)點之間節(jié)點密度差異較大，那么二者的平均跳距差別會變得更大。如果僅采用未知節(jié)點的平均跳距顯然是不科學的。基于此，本研究提出的擴大平均跳域作用范圍是一個不錯的解決方案。根據(jù)錨節(jié)點和未知節(jié)點之間的跳距參數(shù)，在計算二者之間距離時，如果將靠近未知節(jié)點的1/2跳數(shù)按照未知節(jié)點平均跳距來計算，那么剩下的1/2則取錨節(jié)點的平均跳距可以作為參考。

經(jīng)驗證，改進后的dv-hop定位算法在錨節(jié)點數(shù)量適合、比例適中和通信半徑相對小的場景中，可以最大限度減小定位誤差，提升定位的精度。這種方式非常適用于功耗低、范圍大的無線傳感器網(wǎng)絡環(huán)境^［7］。

5 dv-hop的定位算法改進前景

除了以上方法外，不少學者針對dv-hop的定位算法改良提出了不同見解。例如：李牧東等^［8］提出基于人工蜂群算法的dv-hop定位改進法。該方法是利用節(jié)點見的距離和錨節(jié)點的位置信息來建立目標優(yōu)化函數(shù)，從而實現(xiàn)在保持不增加傳感器節(jié)點的硬件開銷優(yōu)勢的同時，有效降低定位誤差。王亞民等^［9］在《基于RSSI的改進加權(quán)質(zhì)心定位算法》中提出基于三角質(zhì)心定位、改進信號強度比值的加權(quán)質(zhì)心混合定位算法。該方法以近似點代替信標節(jié)點作為頂點，節(jié)點之間的距離比值作為權(quán)值，有效降低了路徑損耗指數(shù)對定位精度的影響，在實現(xiàn)區(qū)域定位方面有一定突破。熊歡等^［10］在《基于跳數(shù)修正和改進粒子群優(yōu)化dv-hop定位算法》中指出修正錨節(jié)點廣播跳數(shù)，讓隨機靜態(tài)分布的錨節(jié)點移動，從而優(yōu)化迭代過程，可明顯提升傳統(tǒng)算法的定位精度和算法的穩(wěn)定性。隨著dv-hop的定位算法的廣泛應用與研究熱度的上升，未來將會有更多更好的改進方式，促使其獲得更好的應用效果。

6 結(jié)語

無線網(wǎng)絡傳感器的廣泛應用使其獲得了學界的高度關(guān)注，同時其缺陷也成為改進方案討論的熱點。本文闡述了dv-hop算法中存在的問題，依據(jù)其算法步驟指出問題存在的根本原因，并給出一種基于人工魚群算法的改進策略，即通過加入RSSI加權(quán)質(zhì)心算法來提高陣列節(jié)點間鄰居個數(shù)并優(yōu)化相鄰節(jié)點的聚類效果；同時利用仿真實驗平臺，在原始二維平面建立仿真求解空間，通過多次運行獲取的數(shù)值平均數(shù)，以最大限度提升實驗數(shù)據(jù)的可參考性，進而順利找到目標點，從而解決定位過程中的最優(yōu)尋找、相似性度量以及最小化鄰域長度等問題。

參考文獻

［1］汪晨，張玲華.基于人工魚群算法的改進質(zhì)心定位算法［J］.計算機技術(shù)與發(fā)展，2018（5）：103-106.

［2］余修武，秦曉坤，劉永，等.基于全局人工魚群算法優(yōu)化的DV-Hop定位算法［J］.四川大學學報（工程科學版），2022（4）：54.

［3］王浩.基于優(yōu)先節(jié)點定位和人工魚群優(yōu)化的DV-Hop算法研究［D］.徐州：中國礦業(yè)大學，2016.

［4］張愛清，葉新榮，胡海峰，等.基于RSSI每跳分級和跳距修正的DV-HOP改進算法［J］.儀器儀表學報，2012（11）：2552-2559.

［5］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡節(jié)點迭代定位算法［J］.通信學報，2009（10）：107-113.

［6］夏正龍，鄧斌.一種基于人工魚群算法的LCL濾波器參數(shù)優(yōu)化方法：110442995A［P］.2019-11-12.

［7］李鳳超，高美鳳.無線傳感器網(wǎng)絡中改進的dv-hop定位算法［J］.傳感器與微系統(tǒng)，2018（2）：124-126.

［8］李牧東，熊偉，郭龍.基于人工蜂群算法的dv-hop定位改進法［J］.計算機科學，2013（1）：33-36.

［9］王亞民，王海英，何佩倫.基于RSSI的改進加權(quán)質(zhì)心定位算法［J］.計算機工程與設計，2016（11）：2865-2868.

［10］熊歡，毛永毅.基于跳數(shù)修正和改進粒子群優(yōu)化DV-Hop定位算法［J］.現(xiàn)代電子技術(shù)，2018（18）：76-79.

（編輯 王永超）

Improvement of dv-hop localization algorithm based on artificial fish algorithm

Wei Shixiong^1，2

（1.Guangxi Houpu Digital Technology Co.， Ltd.， Nanning 530009， China;

2.Wuzhou Vocational College， Wuzhou 543002， China）

Abstract： With the wide application of wireless network sensors in all walks of life， many problems in the practical application scenarios gradually emerge， especially the defects of the positioning algorithm. This paper starts from the limitations of dv-hop algorithm for wireless sensor positioning， points out the significant disadvantages of using jump distance instead of straight line distance， and improves the dv-hop positioning algorithm by using the dense network characteristics of artificial fish swarm algorithm based on various studies. It has been proved that the improved dv-hop positioning algorithm based on the artificial fish group algorithm can significantly weaken the node positioning error of wireless sensors， reduce the hardware cost of nodes， and improve the positioning accuracy and efficiency of wireless sensors.

Key words： artificial fish swarm algorithm; dv-hop; positioning algorithm; wireless network sensor