基于人工魚群算法的dv-hop定位算法改進(jìn)研究

韋世雄

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

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

中圖分類號(hào)：TN915.03

文獻(xiàn)標(biāo)志碼：A

0 引言

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

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

1 dv-hop定位算法在當(dāng)前應(yīng)用場(chǎng)景中出現(xiàn)的問題

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

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

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

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

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

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

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

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

2.2 誤差分析

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

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

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

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

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

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

3.1 人工魚群算法的概念

3.1.1 人工魚群算法提出背景

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

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

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

3.2 人工魚群算法在改進(jìn) dv-hop定位算法中的應(yīng)用

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

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

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

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

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

3.2.2 建立仿真實(shí)驗(yàn)環(huán)境Matlab平臺(tái)

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

4 應(yīng)用人工魚群算法后dv-hop定位算法的改進(jìn)效果

在仿真實(shí)驗(yàn)平臺(tái)中，當(dāng)總節(jié)點(diǎn)數(shù)量為100，節(jié)點(diǎn)的通信半徑為30 m時(shí)，同時(shí)錨節(jié)點(diǎn)的數(shù)量由12個(gè)增加至30個(gè)的場(chǎng)景下，可獲得不同錨節(jié)密度下具體的定位誤差對(duì)比。

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

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

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

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

5 dv-hop的定位算法改進(jìn)前景

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

6 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

［10］熊歡，毛永毅.基于跳數(shù)修正和改進(jìn)粒子群優(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