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

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

基于改進(jìn)離散果蠅優(yōu)化算法的WSN廣播路由算法

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

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

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

無線傳感網(wǎng)絡(luò);廣播路由;離散果蠅優(yōu)化算法;萊維飛行;輪盤賭選擇

0 引言

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

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

果蠅優(yōu)化算法(FOA)[7-8]是潘文超在2011年提出的新型啟發(fā)式群智能優(yōu)化算法,因其參數(shù)少、實(shí)現(xiàn)簡單、計(jì)算速度快,受到各個(gè)領(lǐng)域研究學(xué)者的歡迎。本文將果蠅優(yōu)化算法進(jìn)行離散化處理,得到離散果蠅優(yōu)化算法(DiscreteFOA,DFOA),使用萊維飛行(Lévyflights)和輪盤賭選擇對DFOA進(jìn)行改進(jìn),利用改進(jìn)DFOA對WSN廣播路由進(jìn)行優(yōu)化,尋求能耗最小的廣播路徑,以提高WSN廣播路由的性能,節(jié)省網(wǎng)絡(luò)傳輸?shù)哪芰肯摹?/p>

1 WSN廣播路由模型

WSN廣播路由算法是指廣播信息從首節(jié)點(diǎn)出發(fā),遍歷網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn),使傳輸?shù)哪芎淖钚?即改進(jìn)DFOA對WSN廣播路由尋優(yōu)。

在實(shí)際的無線網(wǎng)絡(luò)環(huán)境中,WSN節(jié)點(diǎn)的位置和周圍網(wǎng)絡(luò)環(huán)境可能隨時(shí)都會發(fā)生變化,本文假設(shè)在一個(gè)廣播通信周期內(nèi),WSN拓?fù)浣Y(jié)構(gòu)不變,將WSN拓?fù)浣Y(jié)構(gòu)簡化為圖論模型,用圖G=(V,E)表示。其中:集合V={v1,v2,…,vn}為WSN中的n個(gè)節(jié)點(diǎn)；集合E={e1,e2,…,en}為WSN中n個(gè)節(jié)點(diǎn)之間的鏈路。在二維平面內(nèi),節(jié)點(diǎn)v1和v2的坐標(biāo)分別為(x(v1),y(v1))和(x(v2),y(v2)),可以得到v1到v2的距離。

(1)

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

所以,擁有N個(gè)節(jié)點(diǎn)的WSN廣播消耗的總能耗由式(2)確定:

(2)

2 基于改進(jìn)DFOA的WSN廣播路由算法

2.1 交換子和交換序

文獻(xiàn)[16-17]給出了交換子和交換序的定義和運(yùn)算過程。

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

交換序?yàn)橐粋€(gè)或多個(gè)交換子有序排列的集合,即多個(gè)交換子依次作用在序列上。

兩個(gè)不同序列的差為元素個(gè)數(shù)最少的交換序,即基本交換序。

兩個(gè)不同序列的距離為基本交換序的元素個(gè)數(shù)。

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

2.2 種群更新方式的改進(jìn)

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

文獻(xiàn)[19-21]中給出了Lévy分布的計(jì)算過程:

(3)

其中:Lévy(β)是一個(gè)萊維隨機(jī)數(shù),服從Lévy分布；u、v服從標(biāo)準(zhǔn)正態(tài)分布；β為一個(gè)常數(shù),其取值區(qū)間一般為0<β<2。φ的計(jì)算公式如式(4)所示:

其中:Γ()是標(biāo)準(zhǔn)Gamma函數(shù)。

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

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

(5)

其中:R0為隨機(jī)搜索半徑范圍。

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

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

圖2 不同廣播路徑的對比

2.3 算法描述

本文利用改進(jìn)的離散果蠅優(yōu)化算法尋求WSN廣播通信中能耗最小的廣播路徑,以提高網(wǎng)絡(luò)性能,延長網(wǎng)絡(luò)生存的時(shí)間。

假設(shè)在一個(gè)廣播通信周期內(nèi),WSN的N個(gè)節(jié)點(diǎn)位置不變,并為節(jié)點(diǎn)進(jìn)行編號。廣播算法步驟如下:

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

(6)

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

(7)

其中:vj(j∈[1,N])為組成果蠅個(gè)體Si的網(wǎng)絡(luò)節(jié)點(diǎn)。

4)選擇當(dāng)代最優(yōu)。找出全部果蠅個(gè)體中味道濃度最小的果蠅。

[bestSmellbestIndex]=min(Smell)

(8)

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

SmellBest=bestSmell

(9)

S_best=SbestIndex

(10)

6)輪盤賭選擇。利用輪盤賭選擇,使果蠅個(gè)體向較優(yōu)點(diǎn)附近靠攏。

7)進(jìn)行迭代尋優(yōu)。判斷是否達(dá)到迭代次數(shù)Maxgen,如果是,算法結(jié)束,輸出最優(yōu)結(jié)果;否則,重復(fù)執(zhí)行步驟2)～7)。

3 實(shí)驗(yàn)仿真與分析

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

3.1 改進(jìn)算法有效性分析

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

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

圖1 改進(jìn)DFOA與DFOA演化過程對比

圖2是在80 m×80 m的范圍內(nèi),WSN中50個(gè)節(jié)點(diǎn)經(jīng)過未優(yōu)化、DFOA優(yōu)化、改進(jìn)DFOA優(yōu)化得到的廣播路徑圖。從圖2可看出：DFOA能找到較優(yōu)的WSN廣播路徑；但是,改進(jìn)的DFOA找到的廣播路徑更為優(yōu)異,消耗的能量更少。

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

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

3.2 本文算法優(yōu)越性分析

本節(jié)利用改進(jìn)DFOA在不同網(wǎng)絡(luò)規(guī)模下對WSN廣播路由進(jìn)行尋優(yōu),并與SAGA[9]、改進(jìn)蟻群優(yōu)化(AntColonyOptimization,ACO)算法[11]和自適應(yīng)離散PSO算法[12]進(jìn)行對比,驗(yàn)證本文算法的優(yōu)越性。WSN規(guī)模設(shè)定6種,隨機(jī)生成網(wǎng)絡(luò)中節(jié)點(diǎn)的位置,同時(shí),保證每個(gè)算法的初始值相同,對不同算法進(jìn)行對比仿真。

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

圖3 不同算法能耗對比

在3.1節(jié)的仿真實(shí)驗(yàn)結(jié)果表明改進(jìn)DFOA在跳出局部最優(yōu)方面具有較高的優(yōu)越性,而圖3的曲線顯示,改進(jìn)DFOA對廣播路由進(jìn)行優(yōu)化,隨著網(wǎng)絡(luò)規(guī)模增大,其獲得的廣播能耗增幅較小,說明與其他算法相比,其跳出局部最優(yōu)的能力也較為出眾。

4 結(jié)語

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

)

[1] 孫利民, 李建中, 陳渝, 等. 無線傳感器網(wǎng)絡(luò)[M]. 北京:清華大學(xué)出版社, 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]. 洛陽:河南科技大學(xué), 2013.(BAIK.Researchofwirelesssensornetworkbroadcastroutingalgorithm[D].Luoyang:HenanUniversityofScienceandTechnology, 2013.)

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

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

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

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

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

[15] 唐勇, 周明天. 無線傳感器網(wǎng)絡(luò)中最小化能量廣播算法[J]. 通信學(xué)報(bào), 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] 馬曉慧, 王紅. 改進(jìn)的PSO在TSP中的應(yīng)用[J]. 計(jì)算機(jī)與現(xiàn)代化, 2011(9):5-7.(MAXH,WANGH.ApplicationofimprovedPSOinTSP[J].ComputerandModernization, 2011(9):5-7.)

[18] 霍慧慧. 果蠅優(yōu)化算法及其應(yīng)用研究[D]. 太原:太原理工大學(xué), 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ìn), 尹義龍, 鐘一文.逐維改進(jìn)的布谷鳥搜索算法[J]. 軟件學(xué)報(bào), 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。

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

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

1001- 9081(2017)04- 0965- 05

10.11772/j.issn.1001- 9081.2017.04.0965

TP301.6

A