李牧東，熊 偉*，梁 青

(1．空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安710077;2．西安郵電學(xué)院電子與信息工程系，西安710121)

位置信息對傳感器網(wǎng)絡(luò)的監(jiān)測活動至關(guān)重要，沒有位置信息的監(jiān)測消息毫無意義[1]。如何確定無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息，成為了必須解決的關(guān)鍵問題?，F(xiàn)有的無線傳感器網(wǎng)絡(luò)定位技術(shù)大體可分為基于測距和非測距兩類[2]。

DV-Hop算法是目前最受關(guān)注的無需測距的定位算法之一[3－4]。目前，已有很多關(guān)于經(jīng)典 DV-Hop的改進(jìn)算法，文獻(xiàn)[5]提出了通過先計算錨節(jié)點(diǎn)間的平均跳距得出誤差后再對網(wǎng)絡(luò)的平均跳距進(jìn)行修正的方法;文獻(xiàn)[6]通過利用RSSI技術(shù)完成對未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間距離的測量，從而提高了定位精度;文獻(xiàn)[7]對平均跳距進(jìn)行加權(quán)處理并有選擇地選取錨節(jié)點(diǎn)進(jìn)行定位從而減小定位誤差;文獻(xiàn)[8]將人工蜂群算法引入到DV-Hop算法未知節(jié)點(diǎn)計算階段從而提高了定位精度。

本文針對DV-Hop節(jié)點(diǎn)定位算法中采用多邊測量法計算未知節(jié)點(diǎn)坐標(biāo)時產(chǎn)生較大誤差的問題，把節(jié)點(diǎn)定位問題轉(zhuǎn)化為最優(yōu)化求解問題，結(jié)合人工蜂群算法(Artificial Bee Colony，ABC)的特點(diǎn)，在文獻(xiàn)[8]的基礎(chǔ)上，提出了自適應(yīng)蜂群算法并將其應(yīng)用于未知節(jié)點(diǎn)坐標(biāo)的計算階段，以期減小定位誤差。

1 問題描述

DV-Hop算法是由Niculescu等人提出的，其定位過程分為3個步驟[3]:首先，使用典型的距離交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距錨節(jié)點(diǎn)的最小跳數(shù);其次，錨節(jié)點(diǎn)計算網(wǎng)絡(luò)平均跳距，并采用可控洪泛法廣播至整個網(wǎng)絡(luò)中，即每個節(jié)點(diǎn)僅記錄接收到的第1個平均跳距信息，而忽略之后接收到的;最后，通過未知節(jié)點(diǎn)通過所記錄的平均跳距和最小跳數(shù)信息計算自身到相應(yīng)錨節(jié)點(diǎn)的距離，利用三邊測量原理或極大似然估計原理計算自身坐標(biāo)。

在DV-Hop算法中，錨節(jié)點(diǎn)的平均跳距計算公式[4]如下

其中:Shopi是錨節(jié)點(diǎn)i對應(yīng)的平均每跳距離，j為錨節(jié)點(diǎn)i數(shù)據(jù)表中的其他錨節(jié)點(diǎn)號，Shopij為錨節(jié)點(diǎn)i和j之間的跳數(shù)。

未知節(jié)點(diǎn)接收到平均跳距后，跟據(jù)所記錄的跳數(shù)信息，通過式(2)計算其到錨節(jié)點(diǎn)的距離:

通過上述計算后，傳統(tǒng)DV-Hop算法利用多邊測量法求解未知節(jié)點(diǎn)的坐標(biāo)，從而完成定位，如圖1所示。

圖1 多邊測量法示意圖

若已知在n(n≥3)個錨節(jié)點(diǎn)時，U1(x1，y1)，U2(x2，y2)，…，Un(xn，yn)以及它們到未知節(jié)點(diǎn) K(x，y)的測量距離分別為 d1，d2，…，dn，則有

用方程組的前n－1個方程減去第n個方程后，得

用線性方程組表示為AL=b，其中L=(x，y)T，

由于測距誤差、環(huán)境因素、通信等影響，測量距離總存在一定誤差，因此合理的線性方程組應(yīng)該是AL+ε=b，ε為n－1維隨機(jī)誤差向量。使用標(biāo)準(zhǔn)的最小二乘法可以得到方程組的最小二乘解為L=(ATA)－1ATb。由于向量b中的每個元素都包含dn，而dn是帶有誤差的測量距離，因此所計算出結(jié)果的準(zhǔn)確程度受制于dn。如果dn的誤差足夠小，那么求得的向量L還能滿足要求;若dn的誤差本來就很大，則求得的解的誤差也將很大。該方法雖然簡化了求解非線性方程組的過程，卻有可能犧牲解的精度，針對此情況，本文把問題轉(zhuǎn)化為全局最優(yōu)化求解問題。

假設(shè)fn為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的測距誤差，則再由式(3)可知，對于未知節(jié)點(diǎn)坐標(biāo)(x，y)滿足下式:

求解(x，y)，使得

求解過程中，當(dāng)由式(6)計算出來f(x，y)取最小值時，總誤差最小，則(x，y)的解最接近真實(shí)值，而此時的坐標(biāo)(x，y)為最優(yōu)解。由式(5)可知，f(x，y)的解不受限于某個方程，即當(dāng)某個錨節(jié)點(diǎn)的測距誤差較大時，對于(x，y)的最終解影響也不大。

如上所述，便把節(jié)點(diǎn)定位問題轉(zhuǎn)化成全局最優(yōu)化求解問題。對于式(6)的求解是個非線性最優(yōu)化問題，如果用傳統(tǒng)的數(shù)學(xué)方法求解是很困難的。而人工蜂群算法是用來解決最優(yōu)化問題中較為高效的方法，實(shí)驗(yàn)結(jié)果表明，用人工蜂群算法求解最優(yōu)化問題是行之有效的[9]。

2 改進(jìn)人工蜂群算法求解最優(yōu)化定位

2．1 ABC算法描述

人工蜂群算法ABC(Artificial Bee Colony)是由土耳其埃爾吉耶斯大學(xué)Karaboga在2005年提出的一種基于蜜蜂群智能搜索行為的優(yōu)化算法[9]。在蜂群算法中，按照分工可將蜂群分為3類，即引領(lǐng)蜂、跟隨蜂和偵查蜂，其中引領(lǐng)蜂和跟隨蜂各占一半，并且引領(lǐng)蜂與蜜源的數(shù)量相等，用SN表示。首先，ABC算法初始化生成含有SN個蜜源(解)的初始蜂群;然后，引領(lǐng)蜂對所有的蜜源進(jìn)行循環(huán)次數(shù)為C(C=1，2，…，N)的循環(huán)搜索，如果搜索到的蜜源的花蜜數(shù)量(適應(yīng)度)優(yōu)于以前的，則用新的蜜源位置代替舊的蜜源位置，否則保持舊的蜜源位置不變;最后，所有的引領(lǐng)蜂完成搜索之后，回到舞蹈區(qū)把蜜源上的信息分享給跟隨蜂，跟隨蜂則根據(jù)得到的信息依據(jù)貪婪機(jī)制選擇較優(yōu)的蜜源。跟隨蜂選中蜜源后，也進(jìn)行一次鄰域搜索，并保留較好的解。式(7)為引領(lǐng)蜂和跟隨蜂進(jìn)行蜜源位置更新的公式:

其中k為不同于i的蜜源，j為隨機(jī)選擇的下標(biāo)，且k不等于 i，rij∈[－1，1]是一個隨機(jī)數(shù)，它控制 xij鄰域的生成范圍，隨著搜索接近最優(yōu)解，鄰域的范圍會逐漸減小。ABC算法中跟隨蜂對蜜源的選擇是通過判斷蜜源的收益率大小來確定的，收益率通過適應(yīng)度值來表示，選擇概率Pi按照式(8)確定，其中fiti是第i個解的適應(yīng)度值，SN是解的個數(shù)。

假定蜜源連續(xù)經(jīng)過限定次數(shù)循環(huán)之后仍沒有得到改善，表明這個解陷入局部最優(yōu)，那么這個位置就要被放棄，該位置的引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹榉?。限定次?shù)是ABC算法中重要的控制參數(shù)，用來控制對偵查蜂的選擇[10]。假設(shè)被放棄的解是xi，偵查蜂發(fā)現(xiàn)新位置并代替xi的操作如下。

2．2 人工蜂群算法改進(jìn)

人工蜂群算法中引領(lǐng)蜂對蜜源的搜索階段是影響整個算法全局及局部搜索能力的重要階段，在傳統(tǒng)人工蜂群算法中，由于rij的設(shè)置僅是在[－1，1]之間的隨機(jī)數(shù)，而沒有考慮引領(lǐng)蜂與跟隨蜂在位置更新時存在的聯(lián)系，具有較大的隨機(jī)性，從而導(dǎo)致在尋優(yōu)求解過程中存在收斂速度慢、搜索精度低的缺點(diǎn)，嚴(yán)重影響了算法的性能。文獻(xiàn)[8]提出的基于人工蜂群算法的DV-Hop改進(jìn)算法雖然在一定程度上提高了定位精度，但由于人工蜂群算法本身的局限性，算法的定位精度還有待進(jìn)一步提高。本文在受到文獻(xiàn)[11]的啟發(fā)，對式(7)即引領(lǐng)蜂和跟隨蜂進(jìn)行蜜源位置更新的公式，在文獻(xiàn)[8]的基礎(chǔ)上，引入自適應(yīng)思想，提出了自適應(yīng)人工蜂群算法AABC(Adaptive Artificial Bee Colony Algorithm)。

在引領(lǐng)蜂與跟隨蜂進(jìn)行位置更新時，較大的rij有利于跳出局部極小值點(diǎn)，而較小的rij有利于算法的收斂[12]。對全局搜索通常較好的方法是在算法的初期使用較大的rij以通過較高的探索能力得到較優(yōu)的蜜源，提高其搜索的精度，而在后期則需要較小的rij值，來提高算法的局部搜索能力以加快其收斂速度。因此將rij設(shè)計為迭代次數(shù)的函數(shù)，且隨著迭代次數(shù)逐漸遞減，并考慮到引領(lǐng)蜂與跟隨蜂的關(guān)系，將rij設(shè)置如下:

其中，rmin、rmax分別為初始和終止權(quán)重，Cmax為最大迭代次數(shù)，C為當(dāng)前迭代次數(shù)。則引領(lǐng)蜂與跟隨蜂進(jìn)行蜜源位置的更新公式改為:

由此對蜜源位置的搜索趨勢起到了一定的引導(dǎo)作用，克服了算法本身隨機(jī)性強(qiáng)、收斂速度慢的缺陷。因此根據(jù)式(6)，定義本文適應(yīng)度函數(shù)為:

其中，M為錨節(jié)點(diǎn)個數(shù)，則AABC算法主要步驟如下:

步驟1:設(shè)置主要初始參數(shù):種群數(shù)、最大循環(huán)次數(shù)、參數(shù)維數(shù)、閾值等，其中引領(lǐng)蜂和跟隨蜂各占50%，偵查蜂1個;

步驟2:隨機(jī)產(chǎn)生SN個初始蜜源;

步驟3:引領(lǐng)蜂搜索蜜源，并根據(jù)式(12)計算蜜源適應(yīng)度值，進(jìn)入循環(huán);

步驟4:跟隨蜂分享蜜源信息，由式(8)選擇其中一個蜜源，然后按式(11)搜索臨近新蜜源;

步驟5:對新蜜源計算適應(yīng)度值，并根據(jù)貪婪機(jī)制選擇更優(yōu)的蜜源;

步驟6:若循環(huán)至限定次數(shù)后，蜜源適應(yīng)度值仍不達(dá)標(biāo)則放棄，引領(lǐng)蜂變成偵查蜂繼續(xù)搜索，由式(9)更新位置;

步驟7:存儲此時的最優(yōu)解;

步驟8:循環(huán)次數(shù)加1;

步驟9:滿足終止條件，達(dá)到最大循環(huán)次數(shù)。

2．3 結(jié)合AABC算法的DV-Hop改進(jìn)

假設(shè)在一個無線傳感器網(wǎng)絡(luò)中總共存在N個節(jié)點(diǎn)，其中M個錨節(jié)點(diǎn)、N－M個未知節(jié)點(diǎn)，且錨節(jié)點(diǎn)坐標(biāo)已知。根據(jù)DV-Hop算法原理，結(jié)合其定位過程，將AABC算法引入到 DV-Hop算法中，記為ADV-Hop，則基于AABC算法的DV-Hop算法定位流程如圖2所示。

圖2 ADV-Hop算法的定位流程

3 性能分析

本文的實(shí)驗(yàn)在Matlab平臺上進(jìn)行，由于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)受到體積、能量的限制，為了最大程度地減小本文改進(jìn)算法ADV-Hop的定位誤差及能量消耗，設(shè)置循環(huán)次數(shù)C=30，引領(lǐng)蜂和跟隨蜂總數(shù)SN為50，且各占總數(shù)的一半，控制參數(shù)限定次數(shù)為10，rmin=0．4，rmax=1．2，r初始值設(shè)為 1，閾值 ε =10－6。假設(shè)所有錨節(jié)點(diǎn)坐標(biāo)已知，節(jié)點(diǎn)隨機(jī)分布在邊長為100 m的方形區(qū)域內(nèi);未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的坐標(biāo)隨機(jī)產(chǎn)生;每個節(jié)點(diǎn)的通信半徑R=21 m。

假設(shè)各次仿真時的網(wǎng)絡(luò)區(qū)域、節(jié)點(diǎn)總數(shù)、錨節(jié)點(diǎn)總數(shù)、節(jié)點(diǎn)通信半徑等網(wǎng)絡(luò)參數(shù)相同，仿真次數(shù)為k=500，錨節(jié)點(diǎn)個數(shù)為m，節(jié)點(diǎn)個數(shù)為N，定位節(jié)點(diǎn)的真實(shí)坐標(biāo)為，用統(tǒng)計的歸一化平均定位誤差、平均定位誤差均方差作為定位算法精度和穩(wěn)定性的衡量指標(biāo)。設(shè)ej、σj分別為仿真1次時的平均定位誤差和定位誤差均方差[13]。則基于k次仿真結(jié)果統(tǒng)計的歸一化平均定位誤差及歸一化的平均定位誤差的均方差分別為:

為了客觀地分析本文改進(jìn)算法的定位性能，本實(shí)驗(yàn)將文獻(xiàn)[8]提出的基于ABC算法的DV-Hop改進(jìn)算法(記為BDV-Hop)，與利用最小二乘法計算未知節(jié)點(diǎn)的DV-Hop算法[4]一起，通過500次仿真實(shí)驗(yàn)，與本文改進(jìn)算法ADV-Hop進(jìn)行比較。

圖3給出了100個節(jié)點(diǎn)隨機(jī)分布在方形區(qū)域內(nèi)錨節(jié)點(diǎn)比例在5% ～40%變化時，歸一化平均定位誤差變化情況;圖4給出了相同條件下錨節(jié)點(diǎn)比例變化時，歸一化的定位誤差均方差的變化情況。從圖3、圖4可以看出:在節(jié)點(diǎn)總數(shù)和節(jié)點(diǎn)通信半徑不變的情況下，3種算法的平均定位誤差和均方差都隨著錨節(jié)點(diǎn)比例的增加而減小;另外，在相同條件下，ADV-Hop的平均定位誤差和均方差都明顯小于DV-Hop和BDV-Hop，具體的本文改進(jìn)算法 ADVHop分別比DV-Hop歸一化的平均定位誤差平均減小了34．37%，較BDV-Hop平均減小了17．95%;而對應(yīng)的歸一化的定位誤差均方差平均減小了21.58% 和 7．83%。

圖3 錨節(jié)點(diǎn)比例與歸一化的平均定位誤差關(guān)系

圖4 錨節(jié)點(diǎn)比例與歸一化的定位誤差均方差關(guān)系

圖5和圖6是在網(wǎng)絡(luò)區(qū)域內(nèi)隨機(jī)選取10個錨節(jié)點(diǎn)，節(jié)點(diǎn)總數(shù)分別取 100、150、200、250、300、350、400時，各個算法的定位性能比較。從圖5、圖6可以看出，在錨節(jié)點(diǎn)不變的情況下，3種定位算法的定位誤差、定位誤差均方差都隨節(jié)點(diǎn)個數(shù)的增多而逐漸減小。ADV-Hop的定位誤差較DV-Hop平均減小了25．68%，較 BDV-Hop減小了10．15%，相應(yīng)的誤差均方差分別平均減小了20．27%和7．38%。

圖5 節(jié)點(diǎn)個數(shù)與歸一化的平均定位誤差關(guān)系

圖6 節(jié)點(diǎn)個數(shù)與歸一化的定位誤差均方差關(guān)系

從以上的結(jié)果分析中可以看出BDV-Hop算法在定位精度和穩(wěn)定性方面都優(yōu)于傳統(tǒng)DV-Hop算法，說明了將人工蜂群算法應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位是一種可行的方案，另外相比于BDV-Hop算法，改進(jìn)的ADV-Hop算法在定位精度和精度穩(wěn)定性方面都有較大改善，有效地提高了算法的全局搜索能力以及收斂速度。

4 結(jié)束語

節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)的應(yīng)用基礎(chǔ)。本文在詳細(xì)分析DV-Hop算法中定位階段利用多邊測量法計算未知節(jié)點(diǎn)坐標(biāo)過程的基礎(chǔ)上，成功將節(jié)點(diǎn)定位問題轉(zhuǎn)化為最優(yōu)化求解問題，并利用ABC算法在解決最優(yōu)化問題的優(yōu)勢，結(jié)合定位具體問題，對ABC算法進(jìn)行了改進(jìn)，提出了基于改進(jìn)ABC算法的ADV-Hop算法。該定位算法實(shí)現(xiàn)簡單，運(yùn)行穩(wěn)定，并且能夠有效地解決傳統(tǒng)DV-Hop算法采用多邊測量法估計未知節(jié)點(diǎn)坐標(biāo)時定位誤差較大的問題，提高了算法在定位過程中的定位精度以及穩(wěn)定性。仿真結(jié)果表明，ADV-Hop算法在不增加硬件開銷及略微增加計算開銷的基礎(chǔ)上，相比于傳統(tǒng)DV-Hop算法及BDV-Hop算法，在不同錨節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)個數(shù)的條件下，明顯改善了算法的定位性能。

[1]Akyildiz I F，Weilian Su，Sankarasubramaniam Y，et al．A Survey on Sensor Networks[J]．IEEE Communications Magazine，2002，40(8):102－114．

[2]張震，閆連山，劉江濤，等．基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究[J]．傳感技術(shù)學(xué)報，2011，24(10):1469－1472．

[3]姜鈞，程良倫．采用虛擬錨節(jié)點(diǎn)的高精度VAD-Hop定位算法[J]．傳感技術(shù)學(xué)報，2011，24(7):1048－1052．

[4]Niculescu D，Nath B．Ad-Hoc Positioning System(APS)[C]//Proceedings of the 2001 IEEE Global Telecommunications，2003，1734－1743．

[5]Dongxiao Liu，Yujun Kuang，Wei Wei．Research and Improvement of DVHOP Localization Algorithm in Wireless Sensor Networks[C]//Proceedings of International Conference on Computational Photography，2010，47－50．

[6]Fang Wangsheng，Yang Guangyu．Improvement Based on DV-Hop Localization Algorithm ofWirelessSensorNetwork[C]//Proceedings of International Conference on Mechatronic Science，Electric Engineering and Computer，2011，2421－2424．

[7]劉文遠(yuǎn)，王恩爽，陳子軍．無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J]．小型微型計算機(jī)系統(tǒng)，2011，6(6):1071－1074．

[8]李牧東，熊偉，郭龍．基于人工蜂群算法的DV-Hop定位改進(jìn)[J]．計算機(jī)科學(xué)，2013，40(1):33－36．

[9]Karaboga D．An Idea Based on Honey Bee Swarm for Numerical Optimization，Technical Report-TR06[R]．Kayseri:Erciyes University，Engineering Faculty，Computer Engineering Department，2005．

[10]Karaboga D，Basturk B．On the Performance of Artificial Bee Colony(ABC)Algorithm[J]．Applied Soft Computing，2008，8(1):687－697．

[11]陳貴敏，賈建援，韓騏．粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究[J]．西安交通大學(xué)學(xué)報，2006，40(1):53－56．

[12]Lei Xiujuan，Huang Xu，Zhang Aidong．Improved Artificial Bee Colony Algorithm and Its Application in Data Clustering[C]//Proc．of 2010 IEEE Fifth International Conference on Bio-Inspired Computing:Theories and Applications，2010，514－521．

[13]林金朝，陳曉冰，劉海波．基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法[J]．通信學(xué)報，2009，30(10):107－113．