基于改進離散果蠅優化算法的WSN廣播路由算法

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

貴州大學 大數據與信息工程學院, 貴陽 550025)(*通信作者電子郵箱16353735@qq.com)

基于改進離散果蠅優化算法的WSN廣播路由算法

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

貴州大學 大數據與信息工程學院, 貴陽 550025)(*通信作者電子郵箱16353735@qq.com)

為解決無線傳感網絡(WSN)節點能量限制和廣播路由的能耗問題,提出一種基于改進離散果蠅優化算法(DFOA)的WSN廣播路由算法。首先,將交換子和交換序引入到果蠅優化算法(FOA)中,得到DFOA,拓展FOA的應用領域;然后,利用萊維(Lévy)飛行對果蠅隨機探索的步長進行控制,增加DFOA的樣本多樣性,并用輪盤賭選擇對種群的位置更新策略進行改進,避免算法陷入局部最優;最后利用改進DFOA對WSN路由能耗尋優,找到能耗最小的廣播路徑。仿真結果表明,改進DFOA獲得的廣播能耗更低,在不同的網絡規模下,均優于對比算法(原DFOA、模擬退火遺傳算法(SA-GA)、蟻群優化(ACO)算法和粒子群優化(PSO)算法)。改進DFOA能增加種群多樣性,增強跳出局部最優的能力,提高網絡性能。

無線傳感網絡;廣播路由;離散果蠅優化算法;萊維飛行;輪盤賭選擇

0 引言

無線傳感網絡(Wireless Sensor Network, WSN)[1]由具有傳感器的無線節點構成,每個節點既能采集信息,也能進行數據傳輸,其中,無線數據傳輸能耗較多,影響網絡的生存周期。在WSN廣播中,往往采用泛洪的方式進行路由轉發,極大地消耗了節點的能量,規劃廣播路徑就顯得尤為重要。由于WSN中各節點的位置不同,節點之間轉發數據所需的能耗也就不同,進而,不同的WSN廣播路徑消耗的能量也不相同。在擁有N個節點的WSN中,廣播路徑就有(N-1)!種可能,使用窮舉法嘗試每種路徑,找到最小能耗的路徑,費時且不切實際。因此,本文將WSN廣播路徑選擇當作非確定性多項式(Non-deterministicPolynomial,NP)問題,使用群智能優化算法進行求解。

群智能優化算法是目前尋求全局最優解比較常用的方法,并且求解能力顯著。常用的群智能優化算法有遺傳(GeneticAlgorithm,GA)算法[2]、模擬退火(SimulatedAnnealing,SA)算法[3]、蟻群算法[4]、粒子群優化(ParticleSwarmOptimization,PSO)算法[5]、人工蜂群算法[6]和果蠅優化算法(FruitflyOptimizationAlgorithm,FOA)[7-8]等。目前,已有許多學者將群智能優化算法應用到WSN路由和路徑優化中,并取得了一定的研究成果。白舸[9]將模擬退火(SA)和遺傳算法(GA)進行組合優化，保留SA的降溫過程和GA的交叉、變異，形成模擬退火遺傳算法(SimulatedAnnealingGeneticAlgorithm,SAGA)，并利用SAGA對WSN廣播路徑逐步優化,減小了廣播傳輸的能耗,但是算法尋優效果不好；吳意樂等[10]對SAGA進行改進，利用改進的SAGA優化WSN路徑,降低了數據傳輸的能耗;蘇錦等[11]將遺傳算法和蟻群算法結合,提高了WSN路徑優化的效率,減少了能耗,延長了網絡生存時間,但蟻群算法計算速度慢,耗時較多;袁浩[12]在粒子群算法中引入了變異算子,找到WSN有效的優化路由,提高了解的質量和路由成功率;秦智超等[13]利用粒子群優化環狀簇路由協議,克服節點過早死亡的缺點,延長了網絡壽命,但粒子群算法參數較多,對先驗知識要求較高;鄭振華[14]提出了基于人工蜂群算法的組播路由算法,根據網絡規模自動調整參數,但是人工蜂群算法局部搜索能力不強,對于復雜網絡效果不明顯。

果蠅優化算法(FOA)[7-8]是潘文超在2011年提出的新型啟發式群智能優化算法,因其參數少、實現簡單、計算速度快,受到各個領域研究學者的歡迎。本文將果蠅優化算法進行離散化處理,得到離散果蠅優化算法(DiscreteFOA,DFOA),使用萊維飛行(Lévyflights)和輪盤賭選擇對DFOA進行改進,利用改進DFOA對WSN廣播路由進行優化,尋求能耗最小的廣播路徑,以提高WSN廣播路由的性能,節省網絡傳輸的能量消耗。

1 WSN廣播路由模型

WSN廣播路由算法是指廣播信息從首節點出發,遍歷網絡中每一個節點,使傳輸的能耗最小,即改進DFOA對WSN廣播路由尋優。

在實際的無線網絡環境中,WSN節點的位置和周圍網絡環境可能隨時都會發生變化,本文假設在一個廣播通信周期內,WSN拓撲結構不變,將WSN拓撲結構簡化為圖論模型,用圖G=(V,E)表示。其中:集合V={v1,v2,…,vn}為WSN中的n個節點；集合E={e1,e2,…,en}為WSN中n個節點之間的鏈路。在二維平面內,節點v1和v2的坐標分別為(x(v1),y(v1))和(x(v2),y(v2)),可以得到v1到v2的距離。

(1)

WSN廣播消耗的能量根據文獻[15]提出的能量模型確定。節點vi發送單位信息的能耗為Ce(vi)=ld(vi)α+ce。其中:ld(vi)α為節點發送無線信息的能耗;l為節點發送無線信息的能耗系數,由無線發送模塊決定;d(vi)為vi到下一節點的傳輸距離;α為環境影響系數,是3～5的常量；ce是節點處理信息的能耗,一般為常數。節點vi接收點位信息的能耗為Cr(vi)=cr,取cr=2/3ce。

所以,擁有N個節點的WSN廣播消耗的總能耗由式(2)確定:

(2)

2 基于改進DFOA的WSN廣播路由算法

2.1 交換子和交換序

文獻[16-17]給出了交換子和交換序的定義和運算過程。

交換子的作用為交換序列中的指定位置。假設序列S=1，2，3，4，5,交換子為SO(3,4),則S′=S+SO(3,4)=1，2，4，3，5。

交換序為一個或多個交換子有序排列的集合,即多個交換子依次作用在序列上。

兩個不同序列的差為元素個數最少的交換序,即基本交換序。

兩個不同序列的距離為基本交換序的元素個數。

針對FOA[18]僅適用于解空間為連續的情況,本文將交換子和交換序引入到FOA中,得到DFOA,使得FOA能夠應用到離散環境中,求解能耗最小的WSN廣播路由。

2.2 種群更新方式的改進

果蠅在尋找食物的過程中,也像鳥類一樣,飛行軌跡符合萊維飛行。萊維飛行[19-21]是服從Lévy分布的非高斯平穩過程,飛行的步長滿足一個重尾的萊維穩定分布,較短的步長與偶爾較長的步長相互交替,以發現更好的食物源。

文獻[19-21]中給出了Lévy分布的計算過程:

(3)

其中:Lévy(β)是一個萊維隨機數,服從Lévy分布；u、v服從標準正態分布；β為一個常數,其取值區間一般為0<β<2。φ的計算公式如式(4)所示:

其中:Γ()是標準Gamma函數。

通過萊維飛行的概念對果蠅隨機探索食物源的步長公式R=R0×rand(1)進行改進,多數的較短步長實現算法對局部探索能力的控制,偶爾的較長步長使得算法能夠跳出局部最優,增加樣本多樣性。

R=abs(R0×Lévy(β))

(5)

其中:R0為隨機搜索半徑范圍。

在FOA中,如果找到新的最優點,全部的果蠅個體都飛往這個最好的位置,這就導致算法極易陷入局部最優,本文利用輪盤賭選擇對果蠅的視覺尋優行為進行改進,使得全部的果蠅個體選擇較優點,而不是最優點,避免算法陷入局部最優,增加樣本多樣性。

通過萊維飛行和輪盤賭選擇分別對FOA的步長和位置更新方式進行改進,萊維飛行控制的步長與原算法相比,只是隨機數的生成方面略有區別,對于算法復雜度影響不大。然而,輪盤賭選擇較好的果蠅位置,而不僅僅是最好的果蠅位置,這就使得果蠅位置更新時,保留更多的可行解,需要進行局部探索的點也較多,在一定程度上增加了算法的復雜度,但是,總的果蠅數量是不變的,所以計算量變化不大。原算法僅保留一個最優點極易陷入局部最優,改進后算法就很好地解決了這個問題,增加了樣本的多樣性,避免算法陷入局部最優,才能夠找到更好的可行解,增加算法復雜度是值得的。

圖2 不同廣播路徑的對比

2.3 算法描述

本文利用改進的離散果蠅優化算法尋求WSN廣播通信中能耗最小的廣播路徑,以提高網絡性能,延長網絡生存的時間。

假設在一個廣播通信周期內,WSN的N個節點位置不變,并為節點進行編號。廣播算法步驟如下:

1)初始化。設定迭代次數Maxgen、種群規模Sizepop。隨機生成Sizepop條長度為N+1的廣播序列Si,對果蠅群體位置進行初始化。其中:首先將迭代次數Maxgen、種群規模Sizepop設定一個數值,然后根據實驗中算法收斂情況改變Maxgen和Sizepop的值,使其適用于WSN廣播。

(6)

3)計算味道濃度。根據果蠅個體Si和式(2),確定味道濃度函數Smell(Si),并計算每個果蠅個體味道濃度Smelli。

(7)

其中:vj(j∈[1,N])為組成果蠅個體Si的網絡節點。

4)選擇當代最優。找出全部果蠅個體中味道濃度最小的果蠅。

[bestSmellbestIndex]=min(Smell)

(8)

5)更新全局最優。比較味道濃度是否更好,如果是,則保留最優值和最優果蠅位置;否則執行下一步。

SmellBest=bestSmell

(9)

S_best=SbestIndex

(10)

6)輪盤賭選擇。利用輪盤賭選擇,使果蠅個體向較優點附近靠攏。

7)進行迭代尋優。判斷是否達到迭代次數Maxgen,如果是,算法結束,輸出最優結果;否則,重復執行步驟2)～7)。

3 實驗仿真與分析

本章使用Matlab對基于改進DFOA的WSN廣播路由算法進行仿真,首先,與未改進的DFOA進行WSN廣播路徑優化的演化過程進行比較,體現改進DFOA的有效性;然后將本文算法與經典的模擬退火遺傳算法、蟻群算法和粒子群算法用于WSN廣播路由進行比較,分析改進DFOA對WSN廣播路徑進行優化的優越性。

3.1 改進算法有效性分析

為體現對比實驗的公平性,盡可能使改進DFOA和未改進DFOA相關的參數相同:最大迭代次數Maxgen=200;種群規模Sizepop=30;隨機搜索半徑范圍R0=5;Lévy分布中β=1.5;WSN節點位置是在80 m×80 m的范圍內隨機生成的50個節點;環境影響因素α=2;能耗系數l=1 J/m2;節點處理信息的能耗ce=10 J。

圖1是將改進前后的DFOA對相同WSN節點位置的廣播能耗進行尋優的演化過程對比。從圖1可以看出,改進的DFOA最終獲得的廣播能耗明顯優于未改進的DFOA,雖然改進DFOA收斂速度變慢,但是能跳出局部最優,更好地進行WSN廣播路由。

圖1 改進DFOA與DFOA演化過程對比

圖2是在80 m×80 m的范圍內,WSN中50個節點經過未優化、DFOA優化、改進DFOA優化得到的廣播路徑圖。從圖2可看出：DFOA能找到較優的WSN廣播路徑；但是,改進的DFOA找到的廣播路徑更為優異,消耗的能量更少。

因此,利用萊維飛行和輪盤賭選擇對DFOA進行改進,種群的步長不再單一,增加了跳出局部最優的機會,種群樣本多樣性得到提高,保留了更多較優的可行解,對其進行局部探索,解決了DFOA易陷入局部最優的缺陷,能找到最好的WSN廣播路由策略,圖1和圖2(c)表明本文對算法的改進是有效的。

改進DFOA中引入了萊維飛行,對種群局部搜索的步長進行控制,相對于單一步長的DFOA增加了步長的計算過程,這一階段,增加了算法的時間復雜度,但通過萊維飛行獲得的步長同樣使用變量R來保存,因此,算法的空間復雜度在這一階段并未增加;與DFOA僅保留最優點相比,改進的算法利用輪盤賭選擇對迭代過程中的果蠅位置進行更新,保留了種群中的較優點,時間復雜度并沒有增加,但保留較優點的內存開銷增加,算法空間復雜度有所提高。綜上所述,改進DFOA在時間復雜度和空間復雜度上都有所增加,但是從圖1和圖2(c)可以看出,改進前后的算法性能相差較大,因此,算法的復雜度增加是可以接受的。

3.2 本文算法優越性分析

本節利用改進DFOA在不同網絡規模下對WSN廣播路由進行尋優,并與SAGA[9]、改進蟻群優化(AntColonyOptimization,ACO)算法[11]和自適應離散PSO算法[12]進行對比,驗證本文算法的優越性。WSN規模設定6種,隨機生成網絡中節點的位置,同時,保證每個算法的初始值相同,對不同算法進行對比仿真。

圖3是不同WSN網絡規模下的本文改進DFOA和SAGA[9]、PSO算法[12]、ACO算法[11]求得的廣播能耗的對比圖。從圖3可看出,在WSN網絡規模較小時,四種算法的能耗相差不大,但是,隨著WSN網絡規模的增大,SAGA陷入局部最優,因此,其獲得的廣播能耗大幅度增加,而自適應離散PSO算法和改進ACO算法在跳出局部最優方面較SAGA具有一定的優勢,但是相對于本文提出的改進DFOA,卻還是有一定的不足,獲得的廣播能耗稍大于本文算法的能耗。

圖3 不同算法能耗對比

在3.1節的仿真實驗結果表明改進DFOA在跳出局部最優方面具有較高的優越性,而圖3的曲線顯示,改進DFOA對廣播路由進行優化,隨著網絡規模增大,其獲得的廣播能耗增幅較小,說明與其他算法相比,其跳出局部最優的能力也較為出眾。

4 結語

本文針對FOA僅適用于連續型問題,引入交換子和交換序的概念,提出了適用于WSN廣播路由尋優的DFOA;同時,為避免DFOA陷入局部最優,利用萊維飛行對算法步長進行控制,提高樣本的多樣性;接下來,為解決果蠅個體都飛向最優點產生下一代個體使得樣本多樣性降低、易陷入局部最優的問題,使用輪盤賭選擇產生下一代個體,保留較優的多數個體,而不是僅保留最優點,以發現更多的可行解。通過改進DFOA對WSN廣播路由進行優化,找到最好的廣播路由策略,減小了廣播的能耗,提升了網絡的生存時間,增強了網絡性能。仿真結果表明,與未改進的DFOA進行對比,改進DFOA對WSN廣播路由進行尋優時,能夠跳出局部最優,找到最好的廣播路徑,明顯減小了廣播能耗,對算法的改進是有效的;與SAGA、改進ACO算法和自適應離散PSO算法進行仿真對比,在不同的網絡規模下,改進DFOA對廣播路由進行優化時,能夠避免算法陷入局部最優,得到能耗更低的廣播路徑,因此,改進DFOA對廣播路由進行優化的優越性更明顯。

)

[1] 孫利民, 李建中, 陳渝, 等. 無線傳感器網絡[M]. 北京:清華大學出版社, 2005.(SUNLM,LIJZ,CHENY,etal.WirelessSensorNetworks[M].Beijing:TsinghuaUniversityPress, 2005.)

[2]GOLDBERGDE,SASTRYK.GeneticAlgorithms[M].Berlin:Springer, 2015.

[3]HABIBSJ,MARIMUTHUPN.RestoringcoverageareaforWSNthroughsimulatedannealing[J].InternationalJournalofPervasiveComputing&Communications, 2011, 7(3):205-219.

[4]AROLKARHA,SHETHSP,TAMHANCEVP.AntcolonybasedapproachforintrusiondetectiononclusterheadsinWSN[C]//ICCCS2011:Proceedingsofthe2011InternationalConferenceonCommunication,Computing&Security.NewYork:ACM, 2011:523-526.

[5]TANGT,GUOQ,YANGM.SupportvectormachinebasedparticleswarmoptimizationlocalizationalgorithminWSN[J].JournalofConvergenceInformationTechnology, 2012, 7(1):497-503.

[6]KARABOGAD,AKAYB.Acomparativestudyofartificialbeecolonyalgorithm[J].AppliedMathematics&Computation, 2009, 214(1):108-132.

[7] 潘文超. 果蠅最佳化演算法[M]. 臺北:滄海書局, 2011.(PANW-T.FruitFlyOptimizationAlgorithm[M].Taipei:TsangHaiBookPublishing, 2011.)

[8]PANW-T.Anewfruitflyoptimizationalgorithm:takingthefinancialdistressmodelasanexample[J].Knowledge-BasedSystems, 2012, 26(2):69-74.

[9] 白舸. 無線傳感器廣播路由算法研究[D]. 洛陽:河南科技大學, 2013.(BAIK.Researchofwirelesssensornetworkbroadcastroutingalgorithm[D].Luoyang:HenanUniversityofScienceandTechnology, 2013.)

[10] 吳意樂, 何慶. 基于改進遺傳模擬退火算法的WSN路徑優化算法[J]. 計算機應用研究, 2016, 33(10):2959-2962.(WUYL,HEQ.WSNpathoptimizationbasedonimprovedgeneticsimulatedannealingalgorithm[J].ApplicationResearchofComputers, 2016, 33(10):2959-2962.)

[11] 蘇錦, 張秋紅, 楊新鋒. 改進蟻群算法的無線傳感器網絡路徑優化[J]. 計算機仿真, 2012, 29(8):112-115.(SUJ,ZHANGQH,YANGXF.Pathoptimizationofwirelesssensornetworkbasedonimprovedantcolonyalgorithm[J].ComputerSimulation, 2012, 29(8):112-115.)

[12] 袁浩. 基于粒子群算法的WSN路徑優化[J]. 計算機工程, 2010, 36(4):91-92.(YUANH.Wirelesssensornetworkpathoptimizationbasedonparticleswarmalgorithm[J].ComputerEngineering, 2010, 36(4):91-92.)

[13] 秦智超, 周正, 趙小川. 利用粒子群優化的WSN環狀簇路由協議[J]. 北京郵電大學學報, 2012, 35(5):26-30.(QINZC,ZHOUZ,ZHAOXC.Aring-basedclusteringroutingprotocolforWSNusingparticleswarmoptimization[J].JournalofBeijingUniversityofPostsandTelecommunications, 2012, 35(5):26-30.)

[14] 鄭振華. 基于人工蜂群算法的組播路由優化與仿真[D]. 濟南:山東大學, 2012.(ZHENGZH.Multicastroutingoptimizationandsimulationbasedonartificialbeecolonyalgorithm[D].Jinan:ShandongUniversity, 2012.)

[15] 唐勇, 周明天. 無線傳感器網絡中最小化能量廣播算法[J]. 通信學報, 2007, 28(4):80-86.(TANGY,ZHOUMT.Minimumenergybroadcastingalgorithminwirelesssensornetworks[J].JournalonCommunications, 2007, 28(4):80-86.)

[16]WANGK-P,HUANGL,ZHOUC-G,etal.Particleswarmoptimizationfortravelingsalesmanproblems[C]//Proceedingsofthe2003InternationalConferenceonMachineLearningandCybernetics.Piscataway,NJ:IEEE, 2003, 3:1583-1585.

[17] 馬曉慧, 王紅. 改進的PSO在TSP中的應用[J]. 計算機與現代化, 2011(9):5-7.(MAXH,WANGH.ApplicationofimprovedPSOinTSP[J].ComputerandModernization, 2011(9):5-7.)

[18] 霍慧慧. 果蠅優化算法及其應用研究[D]. 太原:太原理工大學, 2015.(HUOHH.Researchomfruitflyoptimizationalgorithmanditsapplications[D].Taiyuan:TaiyuanUniversityofTechnology, 2015.)

[19]YANGX-S,DEBS.CuckoosearchviaLevyflights[C]//NaBIC2009:Proceedingsofthe2009WorldCongressonNature&BiologicallyInspiredComputing.Piscataway,NJ:IEEE, 2010:210-214.

[20]YANGX-S,DEBS.Engineeringoptimisationbycuckoosearch[J].InternationalJournalofMathematicalModelling&NumericalOptimisation, 2010, 1(4):330-343.

[21] 王李進, 尹義龍, 鐘一文.逐維改進的布谷鳥搜索算法[J]. 軟件學報, 2013, 24(11):2687-2698.(WANGLJ,YINYL,ZHONGYW.Cuckoosearchalgorithmwithdimensionbydimensionimprovement[J].JournalofSoftware, 2013, 24(11):2687-2698.)

ThisworkispartiallysupportedbytheGuizhouProvincialEducationDepartment’Project(KY[2016]124),theGuizhouProvincialScienceandTechnologyDepartment’Project(LH[2014]7628),theDoctoralFoundationofGuizhouUniversity([2010]010),theGraduateInnovationFoundationofGuizhouUniversity(2016066).

XU Tongwei, born in 1991, M. S. candidate. His research interests include wireless sensor network, cognitive radio network, swarm intelligence optimization algorithm.

HE Qing, born in 1982, Ph. D., associate professor. His research interests include wireless network, swarm intelligence optimization algorithm, data analysis.

WU Yile, born in 1991, M. S. candidate. His research interests include wireless sensor network, swarm intelligence optimization algorithm.

GU Haixia, born in 1993, M. S. candidate. Her research interests include wireless sensor network, swarm intelligence optimization algorithm, data analysis.

Broadcast routing algorithm for WSN based on improved discrete fruit fly optimization algorithm

XU Tongwei, HE Qing*, WU Yile, GU Haixia

(College of Big Data and Information Engineering, Guizhou University, Guiyang Guizhou 550025,China)

In Wireless Sensor Network (WSN), to deal with the energy limitation of nodes and the energy consumption of broadcast routing, a new WSN broadcast routing algorithm based on the improved Discrete Fruit fly Optimization Algorithm (DFOA) was proposed. Firstly, the swap and swap sequence were introduced into the Fruit fly Optimization Algorithm (FOA) to obtain DFOA, which expands the applications field of FOA. Secondly, the step of fruit fly was controlled by the Lévy flight to increase the diversity of the samples, and the position updating strategy of population was also improved by the roulette selection to avoid the local optimum. Finally,the improved DFOA was used to optimize the broadcast routing of WSN to find the broadcast path with minimum energy consumption. The simulation results show that the improved DFOA reduces the energy consumption of broadcast and has better performance than comparison algorithms including the original DFOA, Simulated Annealing Genetic Algorithm (SAGA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) in different network. The improved DFOA can increase the diversity of the samples, enhance the ability of escaping from local optimum and improve the network performance.

Wireless Sensor Network (WSN); broadcast routing; Discrete Fruit fly Optimization Algorithm (DFOA); Lévy flight; roulette selection

2016- 08- 30;

2016- 12- 24。

貴州省教育廳項目基金資助項目(黔教合KY字[2016]124);貴州省科技廳項目基金資助項目(黔科合LH字[2014]7628);貴州大學博士項目基金資助項目(貴大人基合字[2010]010);貴州大學研究生創新基金資助項目(研理工2016066)。

徐同偉(1991—),男,山東滕州人,碩士研究生,主要研究方向:無線傳感網絡、認知無線網絡、群智能優化算法; 何慶(1982—),男,貴州甕安人,副教授,博士,主要研究方向:無線網絡、群智能優化算法、數據分析; 吳意樂(1991—),男,江蘇蘇州人,碩士研究生,主要研究方向:無線傳感網絡、群智能優化算法; 顧海霞(1993—),女,江蘇泰州人,碩士研究生,主要研究方向:無線傳感網絡、群智能優化算法、數據分析。

1001- 9081(2017)04- 0965- 05

10.11772/j.issn.1001- 9081.2017.04.0965

TP301.6

A