基于自適應ABC/FOA融合定位算法研究*

徐同偉，何 慶，吳意樂，顧海霞

(貴州大學大數據與信息工程學院，貴陽550025)

基于自適應ABC/FOA融合定位算法研究*

徐同偉，何 慶*，吳意樂，顧海霞

(貴州大學大數據與信息工程學院，貴陽550025)

針對傳統無線傳感網絡(WSN)節點定位算法定位慢、誤差大的問題，提出了一種基于自適應ABC/FOA融合定位算法。該算法既吸收了ABC算法的全局尋優能力強的優點，又保留了FOA算法局部搜索能力強的特點;同時，引入自適應概念，對果蠅步長進行控制，提高種群多樣性;接下來，對節點定位誤差函數進行改進，提高了節點定位誤差的區分度。仿真結果表明，利用自適應ABC/FOA融合定位算法以后，定位時間明顯縮短，定位誤差明顯減小，能夠滿足工程領域對于定位精度的要求。

無線傳感網絡;定位算法;果蠅優化算法;人工蜂群算法;自適應

無線傳感網絡WSN(Wireless Sensor Network)是由傳感器、單片機和無線通信設備共同組成的短距離無線通信技術［1］，因其成本低、功耗小、組網簡單，被廣泛應用于無線數據采集中。無線節點定位是實現數據采集的關鍵技術，然而，定位誤差是影響無線節點定位的首要因素［2－3］。定位算法［4－5］一般分為基于測距的定位算法(Range-Based)和無需測距的定位算法(Range-Free)。基于測距的定位算法精度較高，在目前的工程領域應用較多，常用的定位方法有三邊測量法、三角測量法和最大似然估計法。其中，WSN節點間的距離根據信號傳輸的時間(TOA)、信號傳輸的時間差(TDOA)、信號到達的角度(AOA)和節點接收到的信號強度(RSSI)等方法進行測量。張遠［6］針對節點定位僅限于2D中，對鄰節點的距離和角度信息研究，詳細闡述了基于角度和信號強度的測距方法，將節點定位擴展到3D定位中;楊文鉑等［7］為提高節點定位精度和環境適應性，修正了定位誤差，使RSSI測距方法更精確;郄劍文等［8］將RSSI和TDOA測距方法組合，并進行一定的改進，提高節點定位精度。本文采用RSSI測距方法進行測距，對三邊測量法的定位誤差進行優化，提高定位誤差區分度和定位精度。

群智能優化算法［9］是模仿生物界進化或者尋找食物原理提出的，研究學者常常用它來求解全局最優問題，常用的有遺傳算法、蟻群算法、粒子群算法、人工蜂群算法、果蠅優化算法。趙雁航等［10］用改進的粒子群算法對定位算法中多邊測量法進行迭代尋優，提高了定位精度，但是粒子群算法容易陷入局部最優，而且計算量大，增加網絡節點的開銷;吳意樂等［11］對粒子群算法進行自適應改進，提高種群的多樣性，并對WSN覆蓋策略進行優化，提高網絡資源的利用率;梁美玉等［12］用蟻群算法對三邊測量法的誤差函數進行優化，來獲得更高的定位精度，但是蟻群算法計算速度慢，易陷入局部最優，不適合WSN定位算法簡單、高效的環境;李牧東等［13］將改進的人工蜂群算法運用到DV-Hop算法中，對未知節點的估計坐標進行優化，得到更精確的估計坐標，但是人工蜂群算法局部搜索能力不足，影響定位算法的精度;虞繼敏等［14］將果蠅優化算法應用到節點定位中，通過迭代尋優，縮小未知節點與信標節點之間的距離誤差，提高定位精度，但是果蠅算法容易陷入局部最優且誤差函數區分度小，造成定位誤差增大。

本文提出了一種基于自適應ABC/FOA融合定位算法進行WSN節點定位，該算法將人工蜂群算法和果蠅優化算法融合，在保留果蠅優化算法局部搜索能力的基礎上，提高算法全局尋優的能力;同時，依據最優解未更新次數對果蠅步長自適應控制，并將改進的算法應用到三邊測量法［15］中，找到定位誤差最小的估計坐標;接下來，對三邊測量法的定位誤差函數進行改進，將定位誤差進行分段處理，提高了不同估計坐標誤差的區分度。通過仿真結果證明，改進的算法能較好的跳出局部最優，能較為高效的進行節點定位;同時證明，改進的誤差函數使得節點定位更精確。

1 自適應ABC/FOA融合算法

人工蜂群算法ABC(Artificial Bee Colony Algorithm)［16］計算簡潔、收斂速度快，且具有較強的全局尋優能力;果蠅優化算法FOA(Fruit Fly Optimization Algorithm)［17－18］具有參數少、算法簡單、容易實現等優點。目前主要應用于神經網絡參數訓練、支持向量機參數優化、TSP路徑優化、WSN路由算法優化、WSN定位算法優化等方面。

本文針對果蠅優化算法易陷入局部最優的缺點，結合人工蜂群算法較強的全局尋優能力，并使用最優解未更新次數Flag對果蠅步長進行自適應控制，提出了自適應人工蜂群/果蠅優化融合算法(ABC/FOA)。本文利用自適應ABC/FOA融合算法對WSN節點定位誤差進行優化，具體優化策略將在3.2節進行詳細闡述。算法流程如下:

S1:初始化 隨機初始化果蠅群體位置(X_axis，Y_axis)，設定迭代次數Maxgen、種群規模Sizipop、隨機搜索半徑R、最優解未更新次數閾值mFlag，并置最優解未更新次數標志Flag為零。

S2:隨機搜索 果蠅個體(Xi，Yi)在自適應搜索半徑范圍內，利用嗅覺隨機搜索食物源，即對問題的可行解進行自適應隨機搜索。

S3:計算味道濃度判定值 首先計算果蠅個體到原點的距離Di，然后求味道濃度判定值Si。

S4:計算適應度值 利用味道濃度判定值，計算味道濃度函數或適應度函數Function()中，得到果蠅個體坐標的味道濃度Smelli。

S5:找出當代最優 通過貪婪選擇法找出果蠅群體中味道濃度最小的果蠅。

S6:判斷味道濃度是否優于上一代的味道濃度值，若是則執行步驟S7，否則跳到步驟S8。

S7:更新最優點 保留最小的味道濃度值和果蠅種群位置，果蠅群體利用視覺飛往該位置，并將最優解未更新次數標志Flag置為零，跳到步驟S10。

S8:記錄最優解未更新次數，并保留上一代最優值，果蠅群體位置不變。

S9:判斷次數標志是否達到閾值mFlag，若是，則在可行解范圍內生成果蠅群體位置(偵察蜂變異)，并置最優解未更新次數標志Flag為零，執行步驟S10，否則，直接跳到步驟S10。

S10:判斷是否達到算法最大迭代次數，若達到，則算法結束，輸出最優值，否則繼續迭代執行算法。

自適應ABC/FOA融合算法流程圖如圖1所示。

圖1 自適應ABC/FOA融合算法流程圖

在自適應ABC/FOA融合算法中，引入人工蜂群算法中的產生偵察蜂的閾值mFlag與最優解未更新次數標志Flag和偵察蜂的變異方式，共同對算法陷入局部最優的次數進行限制，能有效解決FOA算法易陷入局部最優的問題。閾值mFlag由算法應用的對象決定，如果mFlag設定過大則算法改善甚微，設定過小則局部搜索能力減弱，需要根據具體情況確定mFlag的值，本文根據經驗值將mFlag設定為種群規模和問題維數的乘積［19］。在大多數文獻中，為了增強算法的局部搜索能力，由適應度值來改變進化的步長;為了提高算法的全局尋優能力，會根據迭代次數來控制步長;針對本算法的情況，為提高種群多樣性，避免算法陷入局部最優，本文提出使用Flag對步長進行控制，對步長自適應處理。

2 定位誤差函數改進與算法實現

本文將自適應ABC/FOA融合算法應用到三邊測量法中，將未知節點的估計坐標(即可行解)作為食物源，對定位誤差進行迭代尋優，提高定位精度。三邊測量法是利用幾何方法計算的定位方法，根據錨節點的位置和未知節點到各錨節點的距離，對未知節點的位置進行估計。其中，錨節點位置已知，未知節點到各錨節點的距離利用RSSI測距方法進行測量。

2.1 定位誤差函數改進

在大多數文獻中，將未知節點的估計坐標(^x，^y)到各錨節點的距離與測得距離之間的差值求平均后，當作誤差函數，如式(14)所示。當定位精度要求較高，則對計算工具的要求較高;并且，當分別代表著局部最優和全局最優的估計坐標的定位誤差都很小時，可能因未發現這細小的誤差，而使算法陷入局部最優，這就需要提高定位誤差的區分度，避免算法陷入局部最優。為了提高定位誤差的區分度，本文對誤差函數進行改進，如式(15)所示。當誤差小于1時，不同估計坐標的定位誤差可能很小，因此，求定位誤差的倒數，提高定位誤差的區分度;當誤差大于1時，不同的定位誤差相對大一些，求定位誤差的負數，這樣就將求解函數的最小值，變為求解最大值問題。改進的誤差函數，對于不同定位誤差的差別很小時，加大了不同定位誤差的區分度，提高了定位精度和探索能力。

式(15)中ε'值與定位誤差負相關，當ε'取得最大值，即定位誤差函數最小時，未知節點的估計坐標最精確，本文利用自適應ABC/FOA融合算法，對誤差函數進行迭代尋優，找到定位誤差最小的估計坐標。

2.2 自適應ABC/FOA融合定位算法

在自適應ABC/FOA融合算法中，將到源節點的距離求倒數后作為味道濃度判定值，然后代入適應度函數，尋求最優味道濃度。在WSN節點定位算法中，對距離Di、味道濃度判定值Si和味道濃度函數Smelli進行相應的改變，以適應WSN節點定位算法。設Dij為果蠅個體i的估計坐標(^xi，^yi)到錨節點j的定位誤差，則

本文將未知節點的估計坐標到錨節點j的定位誤差Dij代入到式(14)的定位誤差中，得到果蠅個體i的節點定位誤差Si，即新的味道濃度判定值Si。

式中:n(n≥3)為錨節點個數，i(1≤i≤Sizepop)為果蠅個體i。

將新的味道濃度判定值Si，代入適應度函數，求解味道濃度Smelli，使節點定位誤差最小，找到精確的定位坐標;同時，為了解決不同定位誤差之間區分度小的缺陷，根據式(15)，適應度函數可表述為:

式中:i(1≤i≤Sizepop)為果蠅個體i。

自適應ABC/FOA融合定位算法對式(18)進行迭代尋優，即基于改進誤差函數的自適應ABC/FOA融合算法。該算法通過尋找Smell()函數的最大值，即定位誤差的最小值，得到定位精度最高的未知節點估計坐標。

3 實驗仿真與分析

本文采用MATLAB對算法進行仿真，通過對比分析不同算法的定位精度和性能，來驗證自適應ABC/FOA融合算法的優越性、改進誤差函數的有效性和自適應ABC/FOA融合定位算法的高效性。

3.1 改進算法的優越性分析

文獻［14］將果蠅優化算法應用到WSN節點定位算法中，但果蠅優化算法容易陷入局部最優，本節將自適應ABC/FOA融合算法與其進行對比，評價自適應ABC/FOA融合算法的優越性。

本節利用節點定位算法，對節點P(1.5，1.5)進行仿真定位，假設3個錨節點的坐標為A(0，0)、B(3，1)、C(1.5，3)，則定位節點到錨節點的距離分別為rA=在實際定位中通過RSSI等測距方法得到)。自適應ABC/FOA融合算法中，種群規模Sizepop=30，算法迭代次數Maxgen=300，隨機搜索半徑R=1 m，次數標志閾值mFlag=60，采用式(15)的定位誤差進行對比。仿真結果如下:

如圖2所示，上半部分為利用FOA算法求得的最小定位誤差的仿真曲線，下半部分為自適應ABC/FOA融合算法的仿真曲線。從圖2可以看出，自適應ABC/FOA融合算法當定位誤差不進行更新時，跳出局部最優，尋求更好的定位節點坐標。所以，自適應ABC/FOA融合定位算法減小了定位誤差，較為精確地獲得未知節點的坐標。

圖2 FOA算法與自適應ABC/FOA融合算法對比

圖3是分別利用文獻［10］中的算法和本文中的算法，不同錨節點的情況下，對節點進行定位，得到的錨節點的定位誤差曲線。因此，在WSN定位算法中，自適應ABC/FOA融合算法比FOA算法定位精度更高。

圖3 不同算法、不同錨節點定位對比

3.2 改進誤差函數的有效性分析

本節將改進的誤差函數和未改進的誤差函數分別帶到自適應ABC/FOA融合算法中，對仿真結果進行比較，驗證改進的誤差函數的有效性。

圖4 誤差函數改進前后對比

從圖4可以看出，基于改進誤差函數的自適應ABC/FOA融合算法，即自適應ABC/FOA融合定位算法，定位誤差區分度高，收斂速度快，能夠較快找出更小的定位誤差，所以，改進的誤差函數是有效的，并且提高了定位精度。

3.3 改進算法的高效性分析

本節將從定位誤差、定位時間兩個方面對算法的高效性進行分析，使用多個錨節點進行仿真，并將蟻群算法(ACO)、粒子群算法(PSO)、FOA算法和自適應ABC/FOA融合算法獲得的最小定位誤差進行對比，分析改進的定位算法的優越性。

對上述4種算法多次仿真，得到定位誤差對比表(表1)。從表1可以看出，自適應ABC/FOA融合定位算法誤差最小，且隨著錨節點個數的增加，定位誤差有一定改善，在圖3中也有體現。在仿真實驗中，只有一個未知節點，錨節點個數對于定位誤差影響不大，在實際網絡環境中，未知節點個數多于錨節點個數，隨著錨節點個數的增加，定位誤差將明顯減小，后期將做進一步研究。

表1 定位誤差對比表

從表2可以看出，FOA算法的定位時間明顯優于ACO和PSO算法;自適應ABC/FOA融合定位算法定位時間雖然稍高于FOA算法，但還是明顯優于其他兩個算法;而且定位精度比FOA算法提高了1倍，所以，毫秒級的時間損失還是可以接受的。

表2 定位時間對比表

4 結束語

本文針對FOA算法易陷入局部最優的缺點，綜合考慮ABC算法全局尋優能力強和FOA算法簡單高效的優點，同時，為增加種群多樣性，利用最優解未更新次數Flag對果蠅步長自適應控制，提出了自適應ABC/FOA融合算法。在WSN節點定位算法中，三邊測量法的誤差函數由于區分度不高，影響定位精度，本文對誤差函數進行改進，提高了不同估計坐標間定位誤差的區分度。本文將改進的誤差函數作為自適應ABC/FOA融合算法的適應度函數，得到自適應ABC/FOA融合定位算法，找到最小定位誤差的估計坐標，減小了定位誤差，提高了定位算法的精確度。仿真結果表明，自適應ABC/FOA融合算法具有較強的跳出局部最優的能力，并且算法簡單、計算速度快、容易實現，應用到WSN節點定位算法可行性高，對硬件要求低;改進的誤差函數增加了定位誤差的區分度，對于定位精度的提高是有效的。自適應ABC/ FOA融合定位算法具有較好的優越性和高效性，不僅定位時間明顯縮短，而且定位誤差明顯減小，能夠滿足工程領域對于定位精度的要求。

［1］ 青島東合信息技術有限公司.無線傳感器網絡技術原理及應用［M］.西安:電子科技大學出版社，2013.

［2］ 王晟.無線傳感網絡節點定位與覆蓋控制理論及技術研究［D］.武漢:武漢理工大學，2006.

［3］ Xu L，Deng Z，Ren W，et al.A Location Algorithm Integrating GPS and WSN in Pervasive Computing［C］//Third International Conference on Pervasive Computing and Applications，2008.ICPCA 2008.IEEE，2008:461－466.

［4］ 田孝華.無線電定位理論與技術［M］.北京:國防工業出版社，2011.

［5］ 彭宇，王丹.無線傳感器網絡定位技術綜述［J］.電子測量與儀器學報，2011，25(5):389－399.

［6］ 張遠.基于距離和角度信息的無線傳感網節點定位問題研究［D］.山東大學，2012.

［7］ 楊文鉑，邢鵬康，劉彥華.一種基于自適應RSSI測距模型的無線傳感器網絡定位方法［J］.傳感技術學報，2015(1):137－141.

［8］ 郄劍文，賈方秀，李興隆，等.基于組合測距的無線傳感器網絡自定位算法［J］.傳感技術學報，2016(5):739－744.

［9］ 梁艷春.群智能優化算法理論與應用［M］.北京:科學出版社，2009.

［10］趙雁航，錢志鴻，尚小航，等.基于跳距修正粒子群優化的WSN定位算法［J］.通信學報，2013，34(9):105－114.

［11］吳意樂，何慶，徐同偉.改進自適應粒子群算法在WSN覆蓋優化中的應用［J］.傳感技術學報，2016，29(4):559－565.

［12］梁美玉，李莉，陳坤.基于蟻群算法的井下無線傳感器網絡節點定位研究［J］.煤礦機械，2010，31(12):48－50.

［13］李牧東，熊偉，梁青.基于人工蜂群改進算法的無線傳感器網絡定位算法［J］.傳感技術學報，2013，26(2):241－245.

［14］虞繼敏，王海云，唐賢倫.改進果蠅優化算法的WSNs節點定位方法［J］.微電子學與計算機，2014(11):111－115.

［15］高雷，鄭相全，張鴻.無線傳感器網絡中一種基于三邊測量法和質心算法的節點定位算法［J］.重慶工學院學報(自然科學版)，2009，23(7):138－141.

［16］Karaboga D.An Idea Based on Honey Bee Swarm for NumericalOptimization［R］.Technical Report－tr06，Erciyes University，Engineering Faculty，Computer Engineering Department，2005.

［17］潘文超.果蠅最佳化演算法［M］.臺北:滄海書局，2011.

［18］Wen-Tsao P.A New Fruit Fly Optimization Algorithm:Taking the Financial Distress Model as an Example.Knowledge-Based Systems，2012，26:69－74.

［19］張超群，鄭建國，王翔.蜂群算法研究綜述［J］.計算機應用研究，2011，28(9):3201－3205.

徐同偉(1991－)，男，山東滕州人，貴州大學碩士生，主要研究方向為認知無線網絡、無線傳感網絡、群智能優化算法;

吳意樂(1991－)，男，江蘇蘇州人，貴州大學碩士生，主要研究方向為無線傳感網絡、群智能優化算法;

何 慶(1982－)，男，貴州都勻人，博士，貴州大學副教授，主要研究方向為認知無線網絡、無線傳感網絡、群智能優化算法，16353735@qq.com;

顧海霞(1993－)，女，江蘇泰州人，貴州大學碩士生，主要研究方向為無線傳感網絡、認知無線網絡、群智能優化算法。

Research on the Localization Algorithm Based on Adaptive ABC/FOA Fusion*

XU Tongwei，HE Qing*，WU Yile，GU Haixia
(College of Big Data and Information Engineering，Guizhou University，Guiyang 550025，China)

In order to solve the tardiness and big error of traditional node localization algorithm in wireless sensor network(WSN)，a new localization algorithm based on adaptive ABC/FOA fusion is proposed.In this algorithm，not only is the global optimizing capacity of ABC algorithm absorbed，but also the strong local searching ability of FOA algorithm is remained.At the same time，the adaptive concept is introduced to control the step size of fruit fly and to improve the diversity of the population.And then，to increase the partition degree of node localization error，the error function of node localization is improved.The simulation shows the promising results:This algorithm can shorten the localization time significantly，decrease the localization error obviously，satisfy the engineering requirement of localization accuracy，and so on.

wireless sensor network;localization algorithm;fruit fly optimization algorithm;artificial bee colony algorithm;adaptive

C:6150P;7230

10.3969/j.issn.1004－1699.2017.02.019

TP393;TP301.6;TN92

A

1004－1699(2017)02－0278－06

項目來源:貴州省教育廳青年科技人才成長項目(黔教合KY字［2016］124);貴州省科技廳項目貴州省科技計劃課題項目(黔科合LH字［2014］7628);貴州大學引進人才科研項目(貴大人基合字［2010］010);貴州大學研究生創新基金項目(研理工2017012)

2016－05－28 修改日期:2016－07－14