一種協(xié)同進(jìn)化的無線傳感器網(wǎng)絡(luò)多播路由算法

傅彥銘,周 興,黃保華,張小萍,朱杰夫

(廣西大學(xué) 計算機(jī)與電子信息學(xué)院,南寧 530004)

1 引 言

無線傳感器網(wǎng)絡(luò)(WSN)是物聯(lián)網(wǎng)[1]連接物理世界的橋梁,物聯(lián)網(wǎng)的發(fā)展對無線傳感器網(wǎng)絡(luò)提出更高的要求.在物聯(lián)網(wǎng)環(huán)境中,為了獲取更多和更準(zhǔn)確的數(shù)據(jù),無線傳感器網(wǎng)絡(luò)的規(guī)模在不斷增大,同時要求時延、能耗和丟包率更低.因此,無線傳感器網(wǎng)絡(luò)技術(shù)的發(fā)展不僅更加引人關(guān)注,而且更具有挑戰(zhàn)性.

多播[2]是一種高效的點(diǎn)到多點(diǎn)通信方式,一個發(fā)送者只需要發(fā)送一份數(shù)據(jù)然后通過公共鏈路分發(fā)給多個接受者.相較單播[3],多播能夠以更少的代價傳輸數(shù)據(jù),是無線傳感器網(wǎng)絡(luò)中常用的通信方式.在無線傳感器網(wǎng)絡(luò)中,節(jié)點(diǎn)的電源電量有限且電池本身不易更換,發(fā)射功耗跟消耗的電量是正相關(guān)的,發(fā)射功耗越低,消耗的電量越少,但功耗太低會導(dǎo)致信號衰減過快,引發(fā)丟包率、延遲和抖動激增.無線傳感器多播路由應(yīng)該同時滿足這些服務(wù)質(zhì)量(Quality of service,Qos)指標(biāo),只滿足某一個指標(biāo)的多播路由在實(shí)際應(yīng)用中難以提供良好的服務(wù),但滿足多個Qos指標(biāo)的多播路由是一個NP難問題[4],并且無線傳感器網(wǎng)絡(luò)具有節(jié)點(diǎn)移動性、網(wǎng)絡(luò)結(jié)構(gòu)動態(tài)變化的特征,使問題更加的復(fù)雜.

為了解決同時滿足多個Qos指標(biāo)的多播路由問題,Roy等人[5]提出基于多目標(biāo)遺傳算法的移動多播路由協(xié)議(QM2RP),利用Pareto機(jī)制得到滿足多個Qos的多播路由方案的最優(yōu)非支配解集,研究表明該算法求解多Qos的多播路由問題比傳統(tǒng)的單目標(biāo)加約束的算法效果更好,但基于多目標(biāo)遺傳的QM2RP在處理復(fù)雜網(wǎng)絡(luò)的時候容易陷入局部最優(yōu).針對無線傳感器網(wǎng)絡(luò)路由算法容易陷入局部最優(yōu)的問題,Li等人[6]提出一種新型的量子蟻群多目標(biāo)路由算法(QACMOR).QACMOR使用量子位元和量子旋轉(zhuǎn)門等量子計算機(jī)制與量子進(jìn)化算法(QEAs)[7]結(jié)合,可以更好地避免在路由尋優(yōu)過程中早熟收斂,并且在WSN多播路由這種大規(guī)模問題上具有更好的性能,但是該算法的種群多樣性較差.除了使用群體智能算法,Thangaramya等人[8]提出基于能量感知聚類和神經(jīng)模糊的路由算法,并用于優(yōu)化物聯(lián)網(wǎng)中無線傳感器網(wǎng)絡(luò)的多播路由,該算法通過使用一種基于神經(jīng)模糊規(guī)則的聚類算法來進(jìn)行路由決策,提升準(zhǔn)確性的同時降低了效率.為了進(jìn)一步的提升算法的性能以適應(yīng)更加復(fù)雜的問題,越來越多學(xué)者提出使用啟發(fā)式策略和元啟式策略相結(jié)合的算法.Bhardwaj等人[9]提出使用多目標(biāo)分?jǐn)?shù)粒子獅群算法(MOFPL)來解決無線傳感器網(wǎng)絡(luò)的能量感知路由問題.在MOFPL中,結(jié)合了分式理論(FT)、粒子群算法以及獅群優(yōu)化算法[10]來優(yōu)化基于能量、時延、流量、距離和簇密度的多目標(biāo)路由.Chaudhry等人[11]提出支持轉(zhuǎn)發(fā)區(qū)(FZ)的多目標(biāo)粒子群算法(FZMOPSO)解決物聯(lián)網(wǎng)在災(zāi)難管理(DMSs)中的多播路由問題.提出一種有效粒子發(fā)生器FZVPG算子與FZMOPSO相結(jié)合,在FZ中搜索有效解,實(shí)現(xiàn)有效粒子的轉(zhuǎn)化,從而得到具有更好多樣性的DMSs多播路由解集.Shende等人[12]融合Crow搜索算法[13]和Whale優(yōu)化算法[14]提出了CrowWhale-ETR優(yōu)化算法求解無線傳感器網(wǎng)絡(luò)中的能量和信任感知的多目標(biāo)多播路由問題.MOFPL、FZMOPSO和CrowWhale-ETR都是由多種策略相互結(jié)合而得到的算法,其搜索能力和跳出局部最優(yōu)的能力都得到提升,但其時間復(fù)雜度也是原來兩者的之和甚至更高.

當(dāng)前的研究表明,WSN的Qos多播路由問題較為復(fù)雜,單純地將群體智能算法用于解決WSN的Qos多播路由容易陷入局部最優(yōu),難以取得較好的效果.大部分研究者使用多策略、多種群體智能算法相結(jié)合改善求解WSN的Qos多播路由效果,但這些研究主要是單純針對算法的優(yōu)化策略進(jìn)行改進(jìn),并未從優(yōu)化多播樹本身結(jié)構(gòu)角度進(jìn)行研究.競爭協(xié)同進(jìn)化算法是模擬自然界生物種群之間相互影響、相互促進(jìn)的進(jìn)化關(guān)系而提出的一類算法,這種通過多種群交互,保持種群多樣性,并且可以同時考慮多種優(yōu)化方向的算法,能夠以相同的時間復(fù)雜度將多種策略相結(jié)合,從而相對其他算法能夠以更少的計算代價跳出局部最優(yōu),獲得性能更好的解集[15].因此,本文將競爭協(xié)同進(jìn)化算法種群的每個個體用目標(biāo)WSN的一顆多播樹初始化,并將種群劃分為兩個子種群,每個子種群用不同的策略更新種群個體多播樹的結(jié)構(gòu),通過種群內(nèi)部和種群之間的競爭和協(xié)作來搜索目標(biāo)WSN的最優(yōu)QoS多播樹.針對無線傳感器網(wǎng)絡(luò)多跳、能量有限的特點(diǎn)以及多播樹的結(jié)構(gòu)特征,本文提出一個基于競爭協(xié)同進(jìn)化的多目標(biāo)多播路由算法(Competitive Coevolution Multicast Route Algorithm,CCMRA),該算法可以很好的適用于物聯(lián)網(wǎng)這類大規(guī)模網(wǎng)絡(luò)環(huán)境.本文的主要工作包括以下幾個方面.

1)根據(jù)多播樹的結(jié)構(gòu)特征設(shè)計了兩種多播樹構(gòu)建方法.第1種方法合并同一個目標(biāo)WSN的兩顆多播樹,充分利用這個并集的公共邊來構(gòu)造新的多播樹.第2種方法對同一個目標(biāo)WSN的兩顆多播樹,提取同源和目標(biāo)點(diǎn)的路徑,選擇帶權(quán)路徑Pareto更優(yōu)的一條路徑,這些路徑集合構(gòu)造新的多播樹.

2)競爭性協(xié)同進(jìn)化算法種群個體是目標(biāo)WSN的一顆多播樹,種群劃分為兩個子種群.子種群內(nèi)部分別使用上述兩種多播樹策略更新.子種群之間通過選擇、融合等機(jī)制交換信息,從而促進(jìn)算法的收斂和保持整體種群的多樣性.

3)實(shí)驗(yàn)從兩方面驗(yàn)證算法的性能.首先測試算法在功耗、時延和丟包率3個指標(biāo)的表現(xiàn),評估算法在WSN上的Qos性能效果.其次,通過超體積、反向世代距離和世代距離等多目標(biāo)評價指標(biāo)測試算法在多目標(biāo)求解上的性能.

2 無線傳感器網(wǎng)絡(luò)多播路由問題模型

無線傳感器網(wǎng)絡(luò)構(gòu)成帶權(quán)圖G={V,E},其中V={v1,v2,…,vn} 表示無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)集,E={e1,e2,…,ek} 表示無線傳感器網(wǎng)絡(luò)的鏈路集合.每個節(jié)點(diǎn)的傳輸功耗在最大值Pmax和最小值Pmin之間選擇,傳輸功耗越大可通信的距離越遠(yuǎn),可通信的節(jié)點(diǎn)也就越多.Power(e)、Delay(e)和PL(e)分別表示在實(shí)際傳輸過程中鏈路e∈E的傳輸功耗、延遲和丟包率.

設(shè)s∈V是G={V,E}上多播路由的源節(jié)點(diǎn),D={d1,d2,…,dm}={V-s} 是多播路由的目標(biāo)節(jié)點(diǎn)集.每一條源節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)d的路徑p(s,d)的并集構(gòu)成了一棵由源節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)集D的多播樹T(s,D).

(1)

通過T(s,D)來計算WSN多播路由中的傳輸功耗、延遲和丟包率這3個目標(biāo)函數(shù).多播樹T(s,D)的傳輸功耗PT為多播樹上每一條邊的傳輸功耗Power(e)之和.

PT(T(s,D))=∑e∈T(s,D)Power(e)

(2)

在T(s,D)一條路徑p(s,d)上的丟包率PLP等于1減去該路徑剩下的保有率.p(s,d)剩下的保有率等于路徑上每條邊e的保有率1-PL(e)的乘積.

PLP(p(s,d))=1-∏e∈p(s,d)(1-PL(e))

(3)

多播樹T(s,D)的總丟包率PLT等于其每一條路徑p(s,d)的丟包率之和.

PLT(T(s,D))=∑p∈T(s,D)PLp(p(s,d))

(4)

多播樹T(s,D)上一條路徑p(s,d)的延遲Delayp等于p(s,d)上每一條鏈路e的延遲Delay(e)之和.

Delayp(p(s,d))=∑e∈p(s,d)Delay(e)

(5)

T(s,D)的總延遲DelayT等于其單一路徑延遲Delayp中的最大值.

(6)

傳輸功耗、延遲和丟包率最小化的無線傳感器網(wǎng)絡(luò)多目標(biāo)多播路由問題,就是要尋找該WSN的多播樹,使得多播樹在目標(biāo)函數(shù)(1)、(2)和(6)上獲得的三維解最優(yōu).最優(yōu)多播樹往往不止一顆,因此構(gòu)成最優(yōu)多播樹解集,該最優(yōu)多播樹解集構(gòu)成的三維解集應(yīng)該處于或者盡量接近Pareto最優(yōu)前沿[16].無線傳感器網(wǎng)絡(luò)多目標(biāo)多播路由問題的數(shù)學(xué)模型可以表示如下:

minimize:f(T(s,D))={f1,f2,f3}

(7)

其中f1,f2,f3如下:

f1(T(s,D))=PT(T(s,D))

f2(T(s,D))=DelayT(T(s,D))

f3(T(s,D))=PLT(T(s,D))

滿足以下約束:

Delayp<=QD

其中的最大延遲應(yīng)該小于或等于延遲的閾值QD.

3 基于競爭協(xié)同進(jìn)化的多目標(biāo)多播路由算法

多播樹之間存在公共路徑,因此最優(yōu)多播樹并不等于多條從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)單播路徑的簡單組合.多播路由問題是一個不可劃分問題,在給定的網(wǎng)絡(luò)結(jié)構(gòu)中尋找最優(yōu)多播樹是一個NP難問題,而且一個網(wǎng)絡(luò)的最優(yōu)多播樹往往不止一顆.在求解最優(yōu)多播樹的搜索過程中保持種群多樣性,使得搜索能夠跳出局部最優(yōu),從而加快搜索的速度、提高搜索的精度.保持種群多樣性的關(guān)鍵是盡量維持種群中多播樹結(jié)構(gòu)的多樣化.

根據(jù)對公共鏈路的利用情況,多播樹大致有兩種結(jié)構(gòu).圖1(a)是一個目標(biāo)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),圖1(b)和圖1(c)都是該網(wǎng)絡(luò)中的最優(yōu)多播樹,但其多播樹的結(jié)構(gòu)完全不同.圖1(b)中從節(jié)點(diǎn)1到目的節(jié)點(diǎn)7的鏈路(1→2→5→7)和節(jié)點(diǎn)1到目的節(jié)點(diǎn)8的鏈路(1→2→5→6→8)存在公共鏈路(1→2→5),圖1(b)的總邊數(shù)不是兩條鏈路簡單相加的7而是去掉重復(fù)的公共鏈路后的5;圖1(c)中到從節(jié)點(diǎn)1到目的節(jié)點(diǎn)7(1→4→7)和到目的節(jié)點(diǎn)8(1→3→6→8)都是其最短路徑,但其鏈路沒有公共鏈路,總邊數(shù)也為5.在目標(biāo)網(wǎng)絡(luò)的多播樹中,存在類似圖1(b)利用公共邊的最優(yōu)多播樹結(jié)構(gòu),也存在類似圖1(c)的由源其到目的節(jié)點(diǎn)的最短路徑集合構(gòu)成的最優(yōu)多播樹結(jié)構(gòu).種群初始化時存在上述兩種多播樹結(jié)構(gòu)的多樣性,隨著種群迭代增加,如果種群的多播樹結(jié)構(gòu)過于單一,算法就容易陷入局部最優(yōu)并且難以跳出.

圖1 多播樹結(jié)構(gòu)圖Fig.1 Multicast tree structure

考慮到這些問題,本文提出一個基于競爭性協(xié)同進(jìn)化的多播路由算法(CCMRA).CCMRA的種群分為兩個子種群,種群的每一個體是目標(biāo)網(wǎng)絡(luò)其中一顆多播樹.其中一個子種群GP構(gòu)造如圖1(b)具有公共邊的多播樹,這種更新方式稱為Global操作,原理在3.2節(jié)中介紹.另一個子種群LP構(gòu)造如圖1(c)結(jié)構(gòu)的多播樹,盡可能使該多播樹源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑更短,這種更新方式稱為Local操作,原理在3.3中介紹.兩個子種群之間通過選擇和融合機(jī)制來交流信息.通過這兩個種群內(nèi)部和種群之間相互學(xué)習(xí)、相互競爭,CCMRA的種群在進(jìn)化過程中能夠保持多樣性和隨機(jī)性,從而提升搜索能力,避免陷入局部最優(yōu),使算法更快地收斂.

CCMRA的原理見算法1.首先CCMRA兩個子種群GP和LP的每一個體使用算法2生成的目標(biāo)網(wǎng)絡(luò)多播樹初始化.其次分別使用以GP和LP為主種群的競爭交配選擇方式選取交配父代Parent1和Parent2,然后分別用Global操作和Local操作更新Parent1和Parent2種群,這兩個種群沿著兩種多播樹結(jié)構(gòu)方向進(jìn)化,構(gòu)成新的子代種群Off1和Off2.合并Off1,Off2和GP 構(gòu)成新的GP種群,新種群融合多個子種群來交換種群信息、保持種群的多樣性.用類似的方法生成新的LP種群.最后GP和LP分別采用多目標(biāo)優(yōu)化機(jī)制篩選N/2個較優(yōu)個體構(gòu)成下一代的GP和LP種群.本文的多目標(biāo)優(yōu)化機(jī)制采用NSGAII的所提出的非支配排序方式和擁擠度計算的多目標(biāo)環(huán)境選擇方式來更新種群的Pareto解集[17].非支配排序方式在非支配解較少的時候,通過對被支配集進(jìn)行進(jìn)一步的優(yōu)劣排序保證足夠的精英解,可以增加在多目標(biāo)優(yōu)化過程的搜索能力,同時通過擁擠度計算可以增加多目標(biāo)優(yōu)化的多樣性,使解集分布更加均勻.迭代結(jié)束時GP和LP種群中的個體即為算法獲得的最優(yōu)多播樹.

算法1.競爭性協(xié)同進(jìn)化多播路由算法(CCMRA)

輸入:網(wǎng)絡(luò)G,源節(jié)點(diǎn)S,目的節(jié)點(diǎn)集D,最大迭代次數(shù)Itmax,種群個體數(shù)N.

輸出:最優(yōu)多播樹集合MT.

1.begin

2.GP←用算法2生成G的N/2顆多播樹構(gòu)成GP的個體.

3.LP←用算法2生成G的N/2顆多播樹構(gòu)成LP的個體.

4.Iter←0.

5.WhileIter

6. Parent1←使用以GP為主種群的競爭交配選擇方式從GP和LP種群中選擇N/2個個體.

7. Parent2←使用以LP為主種群的競爭交配選擇方式從LP和GP種群中選擇N/2個個體.

8. Off1←Parent1通過Global操作生成子代種群.

9. Off2←Parent2通過Local操作生成子代種群.

10. GP←合并Off1,Off2和GP.

11. LP←合并Off1,Off2和LP.

12. GP←通過多目標(biāo)優(yōu)化機(jī)制在GP篩選N/2個體.

13. LP←通過多目標(biāo)優(yōu)化機(jī)制在LP篩選N/2個體.

14. Iter←Iter+1.

15.endwhile

16.MT←合并GP和LP.

17.end

在算法迭代進(jìn)化的早期,多播樹中的鏈路多且長,LP操作針對單條鏈路的趨優(yōu)性可以使LP種群快速地收斂,在GP種群加入LP種群的個體,可以加快GP種群收斂速度,從而提升整體的收斂速度.隨著算法深入迭代進(jìn)化,GP和LP種群多樣性變得單一,導(dǎo)致容易陷入局部最優(yōu),這是群體智能和進(jìn)化算法都難以避免的問題.由于GP和LP種群具有一定的互斥性,所以在GP種群中加入LP種群的個體,在LP種群中加入GP種群的個體,可以幫助GP和LP種群在進(jìn)化過程中保持種群多樣性.通過在兩個子種群內(nèi)部使用Global和Local兩種操作,在兩個子種群之間相互選擇、相互交叉融合的協(xié)同進(jìn)化策略,可以保持整個種群的多樣性,使得種群能夠跳出局部最優(yōu),提高算法的收斂速度和精度.

3.1 隨機(jī)多播樹生成方法

對于一個節(jié)點(diǎn)眾多的WSN,使用深度遍歷或廣度遍歷尋找其多播樹較為困難.因此,本文采用一種更高效的多播樹生成算法,其原理見算法2.首先選擇一條從源節(jié)點(diǎn)到任意目的節(jié)點(diǎn)的路徑加入多播樹.對于其余的目的節(jié)點(diǎn),不用重新尋找一整條到源節(jié)點(diǎn)的路徑,只需要找到一條連通多播樹的路徑即可.因?yàn)槎嗖涫且粋€源節(jié)點(diǎn)到目的節(jié)點(diǎn)的連通圖,這樣能保證構(gòu)成一顆不含環(huán)路的多播樹,并且還可以選中更多公共鏈路,使得生成的整個多播樹質(zhì)量更好.

算法2.多播樹生成算法

輸入:網(wǎng)絡(luò)G,源節(jié)點(diǎn)S,目的節(jié)點(diǎn)集D.

輸出:多播樹MT.

1.cur←隨機(jī)選擇一個目的節(jié)點(diǎn).

2.whilecur!=sdo

3. cur←隨機(jī)選擇相鄰節(jié)點(diǎn).

4.whilecur 在MT中then

5. cur←隨機(jī)選擇其它鄰節(jié)點(diǎn);#避免成環(huán).

6.endwhile

7. MT←MT∪cur;#添加到MT中.

8.endwhile

9.while還有目的節(jié)點(diǎn)沒有添加到MT中do

10. cur←從剩余的目標(biāo)節(jié)點(diǎn)隨機(jī)選擇一個目的節(jié)點(diǎn).

11.whilecur不在MT中do

12. cur←隨機(jī)選擇鄰結(jié)點(diǎn).

13. MT←MT∪cur.

14.endwhile

15.endwhile

3.2 競爭交配選擇方式

用交配選擇方式實(shí)現(xiàn)GP和LP種群之間信息共享,在進(jìn)化過程中增加種群之間密切聯(lián)系,保持種群多樣性.本文使用了一種競爭交配選擇方式[18],這種方式從兩個輸入種群A和B中選出種群C,其中種群A為主種群.首先將種群A和B合并成種群H,然后分別計算A和B的中非支配解數(shù)量在整個H的非支配解總數(shù)中的所占比例pa和pb.若C的種群數(shù)量為N,則每次取兩個個體,一共循環(huán)N/2次,則最終取得C種群的N個個體.下面說明每次取兩個個體的方式的原理.

為了保持主種群的種群優(yōu)勢,在主種群A中用二元錦標(biāo)賽選擇方式選擇第一個個體.若pa>pb,說明A的收斂效果更好,否則,說明B的收斂效果更好,效果更好的種群具有更高的機(jī)率被選擇.設(shè)置一個(0,1)之間的隨機(jī)數(shù)rand,因pa+pb=1,故pa越大,pb越小.若rand=pa,在B中用二元錦標(biāo)賽選擇方式選擇第2個個體.競爭交配選擇方式可以動態(tài)調(diào)節(jié)下一代種群的多樣性,充分利用各種群之間的優(yōu)勢,提高算法的收斂.

本文使用了二元錦標(biāo)賽選擇方式來選擇配對的父代,與文獻(xiàn)[17]中所使用的方法相同,二元錦標(biāo)賽選擇方式是通過隨機(jī)選擇兩個個體,然后根據(jù)其Pareto支配關(guān)系選擇這兩者中較優(yōu)的一個,如果無法區(qū)分優(yōu)劣程度則隨機(jī)選擇其中一個,二元錦標(biāo)賽選擇方式是一種概率選擇方式,較優(yōu)的個體被選中的概率更大,但不會穩(wěn)定選擇較優(yōu)個體,可以同時提供一定的趨優(yōu)性和多樣性.

3.3 Global操作

決定多播樹整體代價的主要因素是鏈路的多少和長短,公共鏈路多,就可以重復(fù)利用鏈路來減少鏈路數(shù)量.GP種群的進(jìn)化充分考慮公共鏈路對最優(yōu)多播樹搜索的影響,以此來獲取更加收斂的多播樹.GP的進(jìn)化不僅使用算法2的多播樹生成方式,且提出一種新的Global操作來生成子代種群.

在Global操作中,將種群的兩個個體合并成一個連通圖,使得兩個個體的公共鏈路盡量被選中,構(gòu)成一顆新多播樹的一部分,然后選擇其它鏈路組成這顆完整的多播樹.Global操作的原理見算法3.Global操作首先將種群兩個個體合并成一個連通圖,使用算法2生成該連通圖的多播樹.這顆多播樹繼承了這兩個父代個體的相同鏈路,然后隨機(jī)選擇剩下的鏈路,剩下的鏈路相互交換而獲得新的多樣性.合并后的連通圖更容易形成公共鏈路,并且兩個個體合并的連通圖的可供選擇范圍更加精準(zhǔn),所以Global操作可以較大概率獲得具有公共鏈路的多播樹,Global操作得到的子代個體,其鏈路都繼承于雙親,不會出現(xiàn)非法或不存在的路徑.為了抵消因此降低的多樣性,變異機(jī)制必不可少,Global操作用算法2引入一個新的多播樹個體,將新的個體和GP中的個體合并,再使用算法2生成新的多播樹個體,將多樣性引入種群.

算法3.Global操作算法

輸入:網(wǎng)絡(luò)G,源節(jié)點(diǎn)S,目的節(jié)點(diǎn)集D,父代種群Parent,父代種群個體的數(shù)目N.

輸出:子代Offspring.

1.Parent1,Parent2←將Parent 種群對半劃分成兩種群.

3.fori = 1 to N/2do

4. Pool←將Parent1[i]和Parent2[i]合并成一個連通圖.

5. Off1,Off2←分別用算法2在Pool上生成兩顆多播樹.

6.ifrand

7. newPop←用算法2隨機(jī)生成G的多播樹.

8. Pool←將Parent1[i]和newPop合并成一個連通圖.

9. Off1←用算法2生成Pool的多播樹.

10.endif

11. Offspring[i] ←Off1.

12. Offspring[i+N/2]←Off2.

13.endfor

3.4 Local操作

公共鏈路并非越多越好,鏈路的長短也很重要,因此Local操作構(gòu)造源節(jié)點(diǎn)到各目的節(jié)點(diǎn)帶權(quán)路徑盡量短的多播樹.使用Local操作更新LP種群,能夠搜索GP種群很難搜索到的區(qū)域.Local操作隨機(jī)取出種群的兩個個體,將個體拆分成源節(jié)點(diǎn)到每個目的節(jié)點(diǎn)的路徑,從兩個個體分別獲得的兩條同源到目的節(jié)點(diǎn)的路徑,然后利用多目標(biāo)優(yōu)化機(jī)制對這兩條路徑進(jìn)行優(yōu)劣篩選,選擇其中更優(yōu)的一條路徑用于構(gòu)造新的多播樹.這樣得到的多播樹其每條源到目的節(jié)點(diǎn)路徑是兩個個體中最優(yōu)的一條.Local操作構(gòu)造的多播樹,傾向于單播路徑的優(yōu)化,雖不能保證整體上最優(yōu),但每一條源節(jié)點(diǎn)到單個目的節(jié)點(diǎn)的路徑較優(yōu),可以使多播樹的各分支快速收斂.

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)均是在一臺配有Intel(R)Core(TM)i7-10750H CPU @2.60GHz和16GB RAM的電腦上進(jìn)行,操作系統(tǒng)配置Windows 10.算法在Matlab R2019a上編寫和運(yùn)行.使用Waxman隨機(jī)網(wǎng)絡(luò)生成器[19]生成8個不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),模擬真實(shí)情況下的無線傳感器網(wǎng)絡(luò),網(wǎng)絡(luò)的各項(xiàng)參數(shù)列于表1.為了模擬真實(shí)環(huán)境,各節(jié)點(diǎn)之間的傳輸功耗(Transmission Power)取決于節(jié)點(diǎn)之間的歐幾里得距離,延遲(Delay)設(shè)置為10ms～100ms之間的隨機(jī)數(shù),每條鏈路的丟包率(Packet Loss)在0～1之間隨機(jī)產(chǎn)生,最大延遲QD設(shè)置為2000ms.

表1 網(wǎng)絡(luò)參數(shù)Table 1 Network parameters

CCMRA與3個經(jīng)典的多目標(biāo)算法CrowWhale-ET、FZMOPSO和MOMR-DE[20]在上述8個WSN網(wǎng)絡(luò)上進(jìn)行對比實(shí)驗(yàn),驗(yàn)證CCMRA的可行性和優(yōu)越性.CrowWhale-ETR和FZMOPSO在第1節(jié)已經(jīng)介紹過,MOMR-DE是一種多目標(biāo)差分多播路由算法.

對比算法的運(yùn)行參數(shù)全部參照原文獻(xiàn),算法的種群大小和迭代次數(shù)分別設(shè)置為100和1000次,CCMRA的GP和LP子種群大小各為50,總迭代次數(shù)為1000次.

4.1 WSN的Qos指標(biāo)對比分析

實(shí)驗(yàn)結(jié)果表明,隨著網(wǎng)絡(luò)規(guī)模增大,網(wǎng)絡(luò)變得更加復(fù)雜,相應(yīng)地也會影響算法的性能.在圖2、圖3和圖4中,從Net 1到Net 8網(wǎng)絡(luò)規(guī)模增加和目的節(jié)點(diǎn)的增加,多播路由問題變得更加復(fù)雜,算法的尋優(yōu)能力的變?nèi)鹾妥顑?yōu)多播樹的本身的擴(kuò)張都會使得傳輸功耗、延遲和丟包率隨之增加,但也會存在波動,如圖2中Net 4和Net 6、圖3中的Net 2和圖4中的Net4,這是由于網(wǎng)絡(luò)都是隨機(jī)生成的,目標(biāo)節(jié)點(diǎn)也是隨機(jī)選者,會存在個別網(wǎng)絡(luò)雖然其網(wǎng)絡(luò)復(fù)雜度增加,但其網(wǎng)絡(luò)的Qos性能指標(biāo)不一定會增加的情況,在這部分實(shí)驗(yàn)中,主要驗(yàn)證算法在不同復(fù)雜度的網(wǎng)絡(luò)結(jié)構(gòu)中與對比算法的性能對比,所以該波動不影響算法的性能分析.

圖2 平均傳輸功耗Fig.2 Mean transmission power

圖3 平均延遲Fig.3 Mean delay

圖4 平均丟包率Fig.4 Mean packet loss

在圖2,圖3 和圖4中,CCMRA在各個網(wǎng)絡(luò)環(huán)境下的傳輸功耗、延遲和丟包率都更低,在Net 1 到Net 5上各算法的性能比較接近,在Net 5 到Net 8上CCMRA相較其他對比算法有較明顯的優(yōu)勢.CCMRA的種群劃分為GP和LP兩個子種群,兩個子種群組成的競爭協(xié)同進(jìn)化策略能夠保持種群的多樣性和隨機(jī)性,使得種群在進(jìn)化過程中能跳出局部最優(yōu),加快種群的收斂.這種競爭性的協(xié)同策略顯著提升了算法的性能,從而可以在相同的種群大小和迭代次數(shù)下,獲得更加高質(zhì)量的解.

此外,在圖3中,CCMRA比其它算法獲得了更低的延遲,除了協(xié)同進(jìn)化策略的作用,也得益于LP種群,多播樹的延遲與其單播鏈路的最大延遲有關(guān),以最優(yōu)單播鏈路為主要考慮目標(biāo)的LP種群有助于CCMRA算法獲得更小的延遲.

圖5 、圖6和圖7分別表示了各算法在Net4、Net6和Net8上獲取的Pareto 前沿,結(jié)果顯示,CCMRA 算法的解集優(yōu)于其他算法,更加接近理想的Pareto真實(shí)前沿.相比圖6和圖7,在圖5中MOMRDE、CrowWhale-ETR、FZMOPSO和CCMRA獲得Pareto解都比較少、分散且接近.這是因?yàn)镹et4節(jié)點(diǎn)數(shù)比Net6和Net8少,網(wǎng)絡(luò)復(fù)雜度低,因此整個網(wǎng)絡(luò)的可行解少且容易搜索得到所致的,但在Net4中依舊發(fā)現(xiàn)CCMRA和FZMOPSO獲取的Pareto解更加逼近理想Pareto前沿.圖6中,CCMRA獲取的Pareto解集明顯優(yōu)于FZMOPSO的Pareto解集,更加的貼近真實(shí)前沿,同時分布也更加的均勻.圖7中,顯然CrowWhale-ETR和MOMRDE已經(jīng)無法獲取令人滿意的解集,CCMRA和FZMOPSO仍能獲取較優(yōu)的Pareto解集,CCMRA和FZMOPSO的Pareto解集收斂性相當(dāng),但CCMRA的Pareto前沿面覆蓋更廣,綜合性能表現(xiàn)CCMRA優(yōu)于FZMOPSO.這是因?yàn)?隨著網(wǎng)絡(luò)規(guī)模和復(fù)雜程度的增大,多播路由問題變得更加難以求解.而CCMRA由于其強(qiáng)關(guān)聯(lián)的兩個種群提供的搜索能力,可以在復(fù)雜的網(wǎng)絡(luò)環(huán)境下,不容易陷入局部最優(yōu),以更少的代價加強(qiáng)收斂.

圖5 網(wǎng)絡(luò)4的Pareto前沿Fig.5 Pareto front of network 4

圖6 網(wǎng)絡(luò)6的Pareto前沿Fig.6 Pareto front of network 6

圖7 網(wǎng)絡(luò)8的Pareto前沿Fig.7 Pareto front of network 8

4.2 多目標(biāo)指標(biāo)對比分析

通過超體積(Hyper Volume,HV)、反向世代距離(Inverted Generational Distance,IGD)和世代距離(Generational Distance,GD)等多目標(biāo)指標(biāo)[21]評估CCMRA在求解多目標(biāo)問題的收斂和解集多樣性保持上的性能.HV,IGD和GD指標(biāo)的實(shí)驗(yàn)結(jié)果分別見表2、表3和表4.全部數(shù)據(jù)都是單獨(dú)運(yùn)行30次得到的均值.

表3 不同算法的GD 指標(biāo)Table 3 GD metric for different algorithms

HV指標(biāo)表示所獲得的Pareto解集在目標(biāo)空間上覆蓋范圍的大小,Pareto覆蓋面越寬、分布越均勻或越接近真實(shí)Pareto前沿,HV指標(biāo)都會變大.從表2中看出, CCMRA的HV指標(biāo)平均值都比其它算法大,說明CCMRA在收斂性和多樣性保持上都具有一定的優(yōu)越性.主要得益于GP和LP子種群更新策略在協(xié)同進(jìn)化過程中起的重要作用.

表2 不同算法的HV指標(biāo)Table 2 HV metric for different algorithms

GD評價指標(biāo)可以評價算法的收斂性,GD指標(biāo)越小,算法的收斂性越好,IGD評價指標(biāo)可以綜合評價算法的收斂性和多樣性,IGD指標(biāo)越小,算法的收斂性和多樣性越好.在表3中,CCMRA 的GD指標(biāo)在各個網(wǎng)絡(luò)上都優(yōu)于對比算法.在表4中,CCMRA在Net3,Net4的IGD指標(biāo)略差于其他算法,對于其它網(wǎng)絡(luò)CCMRA全都以較大差距優(yōu)于對比算法.整體而言,實(shí)驗(yàn)表明,CCMRA算法得到的非支配解更接近真實(shí)的Pareto前沿,可以獲得分布更加均勻的非支配解.

表4 不同算法的IGD 指標(biāo)Table 4 IGD metric for different algorithms

上述實(shí)驗(yàn)結(jié)果表明,CCMRA所采用的種群更新機(jī)制和協(xié)同進(jìn)化策略保持了種群進(jìn)化過程中的多樣性和隨機(jī)性,使得算法在全局搜索和局部搜索之間能夠達(dá)到良好的平衡,因此算法獲得更好的收斂性能,此外通過不同網(wǎng)絡(luò)之間的性能對比,可以得知較復(fù)雜的網(wǎng)絡(luò)環(huán)境下,CCMRA的性能相較其他對比算法可以仍然可以獲得更好的性能,因此CCMRA算法可以適用于網(wǎng)絡(luò)規(guī)模較大的場景.

5 總 結(jié)

同時考慮傳輸功率、延遲和丟包率的無線傳感器網(wǎng)絡(luò)多目標(biāo)多播路由問題屬于復(fù)雜的NP問題.為了有效地解決該問題,本文提出一種基于競爭協(xié)同進(jìn)化的多播路由算法(CCMRA).CCMRA使用協(xié)同進(jìn)化算法框架,算法種群的每一個體是目標(biāo)WSN的一顆多播樹,把種群分成GP和LP兩個子種群.GP子種群內(nèi)部通過Global操作更新子種群.Local子種群內(nèi)部通過Local操作更新子種群.LP和GP子種群之間通過交叉選擇和融合機(jī)制在整個種群之間共享和交換信息.上述的協(xié)同進(jìn)化策略能夠保持種群多樣性和隨機(jī)性,使算法在迭代進(jìn)化過程中跳出局部最優(yōu),從而提高算法的收斂精度和速度.CCMRA與NSGA-II、MOPSO和MOMR-DE在8個WSN上分別進(jìn)行Qos多播路由實(shí)驗(yàn)和多目標(biāo)求解性能實(shí)驗(yàn).結(jié)果顯示CCMRA在傳輸功耗、延遲和丟包率3個Qos指標(biāo)上優(yōu)于對比算法.CCMRA的多目標(biāo)求解性能實(shí)驗(yàn)證實(shí),該算法在多目標(biāo)指標(biāo)HV、GD、IGD上都有比較明顯的優(yōu)勢.此外,CCMRA在處理復(fù)雜WSN的良好性能表明該算法能很好地應(yīng)用于大規(guī)模的WSN多播路由問題.