一種QACO-LEACH無線傳感器網(wǎng)絡分簇路由算法

楊 佳,顧耀華,許 強

1(重慶理工大學 電氣與電子工程學院,重慶 400054)2(重慶工商大學 計算機科學與信息工程學院,重慶 400067)

1 引 言

無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSNs)是指在一定區(qū)域范圍內(nèi),布撒大量具有信息采集和無線通信傳輸功能的微型智能傳感器而組成的一種無線自組織網(wǎng)絡[1].該網(wǎng)絡可以對指定區(qū)域內(nèi)的待監(jiān)測量進行感知、處理和傳輸,最終將待監(jiān)測量發(fā)送給觀察者,從而可以實現(xiàn)遠程檢測的目的.無線傳感器網(wǎng)絡的這些特點決定了它在人們的日常生活和工農(nóng)業(yè)生產(chǎn)中具有很大的實用價值.然而,無線傳感器網(wǎng)絡的節(jié)點能源大都來自于電池,隨著電池能量的耗盡,很多環(huán)境下無法更換新的.并且當前技術無法對電池容量增大太多,能耗問題已經(jīng)成為無線傳感器網(wǎng)絡發(fā)展的最大制約因素之一.因此,該問題成為了國內(nèi)外學者研究的熱點.其中,采用對無線傳感器網(wǎng)絡分簇路由進行優(yōu)化來節(jié)約網(wǎng)絡能耗是主要解決方式之一.

文獻[2]所提出的LEACH是最早的分簇路由算法.該算法對所有傳感器節(jié)點進行分簇,并在每個簇中選出一個簇頭.這種方式與之前的方法相比,極大的節(jié)約了能耗.但是,該算法中所有簇頭都是通過單跳的方式直接與Sink節(jié)點進行通信,這就會造成遠離Sink節(jié)點的簇頭能量消耗過快.此外,在選擇簇頭的時候,還存在無法保證簇頭均勻分布的問題.近年來,群智能算法被引入到無線傳感器網(wǎng)絡中.其中,文獻[3]在經(jīng)典LEACH協(xié)議的基礎上,引入蟻群優(yōu)化(Ant Colony Optimization,ACO)算法,提出了一種基于蟻群的無線傳感器網(wǎng)絡分簇路由協(xié)議(ACO-LEACH),在一定程度上實現(xiàn)了節(jié)約能耗和延長網(wǎng)絡生命周期的目的.但是,使用蟻群算法搜尋路徑具有盲目性,容易造成局部最優(yōu)解,并且最優(yōu)路徑的收斂速度比較慢.因此,本文在無線傳感器網(wǎng)絡的分簇階段采用改進的LEACH協(xié)議對傳感器進行分簇和簇頭的選擇;在簇間路由階段,引入量子蟻群優(yōu)化(Quantum Ant Colony Optimization,QACO)算法對無線傳感器網(wǎng)絡路由路徑選擇問題進行優(yōu)化,找到全局最優(yōu)解,加快了算法的收斂速度.提出了一種基于量子蟻群優(yōu)化的無線傳感器網(wǎng)絡分簇路由算法(QACO-LEACH).該算法可以更好地節(jié)約節(jié)點的能耗,延長網(wǎng)絡的生命周期.

2 量子蟻群算法

量子進化算法(Quantum Evolutionary Algorithm,QEA)是一種基于量子計算的一些理論和概念,并且模擬了量子態(tài)矢量表示和量子旋轉門運算的概率進化算法[4].QEA在種群多樣性、全局優(yōu)化能力和收斂速度等方面表現(xiàn)出比傳統(tǒng)遺傳算法更好的性能.此外,該算法容易與其他算法融合的特點,也使得其在許多優(yōu)化問題中得到廣泛的應用.在研究量子進化算法的基礎上,文獻[5]和文獻[6]詳細闡述了進化計算和量子計算這兩個概念,并且將這兩個概念融合到蟻群算法中,提出了量子蟻群優(yōu)化算法.在該算法中,量子比特可用于表示每只螞蟻任意時刻的位置信息.在每只螞蟻移動之前,根據(jù)選擇概率來選擇下一時刻的位置.這種選擇概率可依據(jù)每條路徑上的信息素強度和可見度大小判斷得到.而螞蟻位置的改變可以使用量子比特的更新來表示.因此,需要使用量子進化算法中的量子旋轉門來更新代表每只螞蟻此時位置信息的量子比特,從而實現(xiàn)螞蟻的移動.在量子蟻群算法中,可以很好的解決蟻群算法中易于陷入局部最優(yōu)的問題,主要是因為有效的增加了位置的多樣性.所采取的措施之一就是每只螞蟻的位置信息都使用量子比特的兩個概率幅來表示.其次就是引入了量子非門,實現(xiàn)了螞蟻位置的變異.在完成了螞蟻位置變化之后,可根據(jù)螞蟻位置信息的變化數(shù)據(jù),更新路徑的信息素強度和可見度大小.更新之后的信息素強度和可見度大小,又成為接下來其他螞蟻選擇概率的判斷依據(jù).與傳統(tǒng)蟻群算法相比,同樣數(shù)量的螞蟻,量子蟻群算法的搜索空間更大,收斂速度更快,能更好的找到全局最優(yōu)解.

3 基于量子蟻群算法的WSN分簇路由算法

傳統(tǒng)的WSN分簇路由算法具有周期性,每個周期都包括兩個階段:簇形成階段和簇間路由階段[7].本文所提出的QACO-LEACH與此相同,在每一個周期中,我們將首先把所有節(jié)點劃分成很多簇,然后才是等待數(shù)據(jù)的傳輸.

在簇形成階段,每個簇中簇頭的選擇是需要解決的首要任務,該簇頭節(jié)點將要承擔比普通節(jié)點更多的額外任務,比如數(shù)據(jù)融合和收發(fā)消息等,這就必然會導致簇頭節(jié)點比普通節(jié)點消耗更多的能量[8].因此,節(jié)點的剩余能量毋庸置疑是我們在選擇簇頭節(jié)點時必須要考慮的一個重要因素.此外,為了解決隨機性選擇簇頭導致的簇頭節(jié)點分布過于密集的情況,本文設定一個參數(shù)L,對于臨近的兩個待選簇頭節(jié)點,首先判斷兩者之間的距離大小,若距離小于L,就比較兩者各自的剩余能量大小.選擇剩余能量大的節(jié)點作為簇頭,另一個自然成為普通節(jié)點,從而確保形成的簇更加合理,避免了簇頭“扎堆”現(xiàn)象.

其中,L的表達式為:

(1)

式中,S是檢測區(qū)域的面積,N是傳感器節(jié)點的數(shù)目,P是簇頭節(jié)點占總節(jié)點數(shù)的比例.

在簇間路由階段,主要進行的工作就是數(shù)據(jù)傳輸,而數(shù)據(jù)傳輸主要采用的方式就是在簇頭節(jié)點與Sink節(jié)點之間進行多跳通信.本文在這種多跳通信中引入QACO算法,找出距離較遠的簇頭節(jié)點與Sink節(jié)點之間的最優(yōu)路徑.在該最優(yōu)路徑中進行數(shù)據(jù)傳輸,可以大大降低遠離Sink節(jié)點的簇頭節(jié)點的能耗,從而延長了整個網(wǎng)絡的生命周期.本算法流程圖如圖1所示.

圖1 QACO-LEACH算法流程圖Fig.1 QACO-LEACH algorithm flow chart

4 算法的實現(xiàn)過程

4.1 簇形成階段

簇頭被選定之后,即以廣播的形式向其周圍節(jié)點發(fā)送當選簇頭的消息.周圍節(jié)點隨后判斷自身與簇頭節(jié)點之間的距離大小,選擇距離近的簇頭節(jié)點并加入該簇.以此類推,各個節(jié)點自組織的加入各自的簇,直到所有節(jié)點分簇完成.實現(xiàn)步驟和一些偽代碼如下:

Step 1.對所有參數(shù)值以及用得到的數(shù)據(jù)表進行初始化,同時在N×N的正方形區(qū)域內(nèi)隨機分布適量的節(jié)點,并將每個節(jié)點的坐標(x,y)記錄下來.

Step 2.Q=Rand(0,1)//各個節(jié)點選擇隨機數(shù)

If (Q < T(n)) //T(n)的公式見式(2)

Position=Cluster Head //當選簇頭

Broadcast //以廣播形式向其他節(jié)點發(fā)送當選簇

頭消息

If (Position=Cluster Head)

Listening

If (臨近的兩個簇頭節(jié)點互相接收到對方發(fā)送的消息)

If (它們之間的距離

比較它們的剩余能量大小,大的即為簇頭,小的自動成為

成員節(jié)點

End

(2)

其中,p表示簇頭數(shù)量占總節(jié)點個數(shù)的百分比;Ecurrent是節(jié)點此時的能量;r表示此時的輪數(shù);Emax是節(jié)點的初始能量值;G是在最后1/p輪中仍然沒有當選簇頭的節(jié)點集合.

簇頭選擇完成.

Step 3.剩余的所有未當選簇頭的普通節(jié)點,判斷自身與簇頭節(jié)點之間的距離大小,選擇距離近的簇頭節(jié)點并加入該簇.以此類推,各個節(jié)點自組織的加入各自的簇,直到所有節(jié)點分簇完成.

4.2 簇間路由階段

4.2.1 初始種群產(chǎn)生

在QACO中,螞蟻種群初始化時,以隨機的方式對代表每只螞蟻當前位置的信息進行初始化編碼.可以使用如下方案進行編碼:

(3)

其中,θij=2π×rand;(i,j=1,2,…,m),m是種群規(guī)模,n是空間維數(shù),rand是(0,1)之間的隨機數(shù).由該方案可知,兩個量子態(tài) |0>和|1>的概率幅各自代表了每只螞蟻在空間中所占據(jù)的兩個位置信息.因此,當螞蟻的數(shù)量相同時,螞蟻的搜索空間增大為原來的兩倍,這一特點自然會使得收斂速度大大加快[8].

qi0=(cos(θi1),cos(θi2),…,cos(θin))

(4)

qi1=(sin(θi1),sin(θi2),…,sin(θin))

(5)

qi0為|0>態(tài)位置,qi1為|1>態(tài)位置.在選擇路徑時,分別使用一個染色體基因的因子代表每一個待選路徑.當某條路徑被選中時,其因子將被置1,若未被選中,則置0.在完成了這些工作之后,即可進行量子進化算法的操作.

4.2.2 螞蟻位置更新與變異處理

在蟻群算法中,種群在搜索空間中多樣性的丟失,容易導致陷入局部最優(yōu)[9].因此,為了避免出現(xiàn)局部最優(yōu)的情況,我們就需要提高種群多樣性.本文采用的方式是將變異算子引入到進化算法中.在量子蟻群算法中,將傳統(tǒng)ACO中螞蟻經(jīng)過之后路徑信息素強度的增加量轉變?yōu)榱孔有D門旋轉角的更新.該方式可以保證信息素向最優(yōu)目標解的方向坍縮,信息素的更新以及量子旋轉門的使用如式(6)(7).

(6)

(7)

其中:Δθ是旋轉的角度大小,這里使用自適應的方式來調(diào)整量子旋轉角Δθi的方向和大小,可以避免采用查詢表的方式所帶來的不便.調(diào)整方式如式(3)所示,容易得出對于旋轉角的每一次調(diào)整,一定可以讓信息素的更新趨勢朝著目標最優(yōu)解的方向調(diào)整.

Δθij=-sgn(A)×Δθ

(8)

(9)

其中:G是設置好的最大迭代次數(shù),t是當前的迭代次數(shù).最初執(zhí)行算法時Δθ的值相對較大,這樣可以保證搜索的范圍更大,使算法的搜索空間更大,同時可以更好的跳出局部最優(yōu),防止過早陷入局部最優(yōu).隨著迭代次數(shù)不斷增加,Δθ的值會變得越來越小,因此可以確保算法在局部的更新能力.

然后,利用更新后的量子旋轉門,對代表螞蟻此時位置信息的量子比特進行更新,即完成了螞蟻位置的移動.自此,只須改變每只螞蟻的量子位概率幅,就可實現(xiàn)螞蟻位置的變動.螞蟻轉移概率方程為:

(10)

(11)

式中dij為相鄰兩個簇頭節(jié)點之間的距離,β(β≥0)為期望的啟發(fā)式因子,μj為節(jié)點j的量子信息強度,其表達式為

(12)

式中|αj|2表示第j個量子位的量子態(tài)坍縮到|0>的概率,γ(γ≥0)為量子比特啟發(fā)式因子.

4.2.3 路徑信息素強度更新規(guī)則

在QACO中,信息素強度越高的地方,表明路徑越好,因此需要及時更新信息素強度[10].在每個螞蟻分別完成對各個路徑的搜索選擇之后,將所有單個螞蟻的搜索結果映射到最優(yōu)解空間中,從而完成螞蟻當前位置信息素強度τij的局部更新.路徑信息素強度的更新方程為:

(13)

4.2.4 具體實現(xiàn)步驟

1)times←0(times表示迭代次數(shù)或搜索次數(shù));對每個τij和Δτij進行初始化;將每個螞蟻各自放在待搜索區(qū)域的中心位置,待搜索區(qū)域的大小可根據(jù)螞蟻的數(shù)量和所占空間大小來確定;

3)對每個螞蟻下一步的前向目標函數(shù)Zk進行計算,并記錄此時的最優(yōu)解;

4)根據(jù)量子進化算法中表示量子行為的迭代方程,對螞蟻所在區(qū)域周圍路徑進行區(qū)域搜索,并對目標函數(shù)進行優(yōu)化;

5)針對螞蟻周圍的各個路徑信息素濃度的改變,可使用更新方程對各個軌跡強度進行更新;

6)每只螞蟻k的數(shù)據(jù)變化:Δτij← 0;times←times+1;

7)如果times< 預期的搜索次數(shù)而且沒有退化行為(即搜索到的都是相同解),則轉回步驟(2);

8)輸出當前的最優(yōu)解.

5 仿真實驗與結果分析

為了驗證本文提出的QACO-LEACH算法在無線傳感器網(wǎng)絡尋找最優(yōu)路徑和節(jié)約能耗中的優(yōu)勢,在Matlab2016a平臺上分別對最優(yōu)路徑、分簇效果和能量消耗進行了仿真對比.

5.1 QACO-LEACH與ACO-LEACH搜尋最優(yōu)路徑效果對比

在100m×100m的正方形范圍中,隨機分布50個簇頭節(jié)點.算法中參數(shù)分別設置為:α=0.9,β=1.8,ρ=0.8,γ=0.9.其中設置兩個固定點:起始節(jié)點A(10,20),目的節(jié)點B(25,45).分別使用ACO算法和QACO算法選擇從A點到B點的最優(yōu)路徑,仿真結果如圖2所示.

圖2 最優(yōu)路徑長度收斂曲線Fig.2 Optimal path length convergence curve

由圖2明顯看出,本文提出的QACO-LEACH最小路徑長度始終小于ACO-LEACH,仿真結果表明,該算法在尋找最優(yōu)路徑方面具有更好的優(yōu)勢,達到了預期目標.

QACO的性能優(yōu)于ACO是因為,對于基本蟻群算法來說,其在某一路徑上不斷增加的信息素含量,使得運行的結果更容易陷入局部最優(yōu).這種情況必定會導致無法更好的在整個網(wǎng)絡中找尋到最優(yōu)路徑.相比之下,量子進化算法中,一個量子可以有三種狀態(tài):|0>態(tài)、|1>態(tài)以及|0>和|1>之間的任意疊加態(tài).所以一個量子位所處的狀態(tài)可以表述成|ψ>=α|0>+β|1>,α、β是實數(shù),表示一個量子位所處狀態(tài)的概率幅,同時此概率幅滿足歸一化的條件,即為|α|2+|β|2=1.因為量子比特可以處于|0>和|1>之間的任一連續(xù)狀態(tài)中,因此量子優(yōu)化算法可以表現(xiàn)出更多的狀態(tài)和更多的多樣性.所以QACO融合了量子進化算法和蟻群算法的優(yōu)點,將信息素用量子編碼來表示,可以解決搜尋最優(yōu)路徑時,信息素聚集過快的問題.通過使用量子旋轉門,達到跳出局部最優(yōu)進而使搜索繼續(xù)進行下去的目的,最終搜尋到全局最優(yōu)路徑.

5.2 QACO-LEACH協(xié)議與其他協(xié)議分簇和節(jié)能效果對比

現(xiàn)分別在同一場景中對比LEACH協(xié)議、ACO-LEACH協(xié)議和QACO-LEACH協(xié)議在分簇和節(jié)能方面的表現(xiàn)效果.具體仿真環(huán)境與參數(shù)如表1所示.

表1 仿真環(huán)境與參數(shù)
Table 1 Simulation environment and parameters

5.2.1 QACO-LEACH與其它協(xié)議的分簇效果對比

在同樣實驗場景中,對LEACH協(xié)議、ACO-LEACH協(xié)議和QACO-LEACH協(xié)議在分簇階段的效果進行對比.圖3-圖5分別為同一輪中三種協(xié)議的分簇結果.

圖3 LEACH分簇結果仿真圖Fig.3 LEACH clustering result simulation diagram

由以上各分簇仿真圖看出,LEACH和ACO-LEACH分簇結果不太均勻, 很多簇頭之間距離過近, 甚至出現(xiàn)兩個臨近簇頭“重疊”現(xiàn)象.而QACO-LEACH的分簇結果相對更加均勻,未出現(xiàn)簇頭“扎堆”現(xiàn)象,表明本文在LEACH基礎上,加入的L參數(shù)有效的避免了簇頭距離過近的現(xiàn)象,增加了簇頭的整體分布合理性,達到了預期分簇效果.

圖4 ACO-LEACH分簇結果仿真圖Fig.4 ACO-LEACH clustering result simulation diagram

5.2.2 QACO-LEACH與其它協(xié)議的節(jié)能效果對比

在QACO-LEACH完成分簇之后,繼續(xù)進行簇間路由,得到剩余存活節(jié)點個數(shù)仿真曲線,并與LEACH、ACO-LEACH和QACO-LEACH進行實驗對比.仿真對比結果如圖6所示.

圖5 QACO-LEACH分簇結果仿真圖Fig.5 QACO-LEACH clustering result simulation diagram

圖6 剩余存活節(jié)點個數(shù)曲線圖Fig.6 Curve of the number of remaining surviving nodes

由圖6可以看出,在仿真時間為100輪附近,LEACH協(xié)議已有節(jié)點開始死亡;在190輪附近,ACO-LEACH協(xié)議有節(jié)點開始死亡;而在240輪附近,QACO-LEACH協(xié)議才有節(jié)點開始死亡.LEACH協(xié)議和ACO-LEACH協(xié)議的節(jié)點死亡一半的時間分別發(fā)生在180輪和390輪,而在QACO-LEACH協(xié)議中的節(jié)點在420輪死亡一半.當網(wǎng)絡運行相同時間后,本文提出的QACO-LEACH比LEACH和ACO-LEACH剩余節(jié)點個數(shù)都多,表明通過本文算法的使用,有效的降低了簇頭節(jié)點的能耗.

QACO-LEACH對無線傳感器網(wǎng)絡節(jié)點能耗的改善效果比LEACH和蟻群算法好,主要是因為LEACH協(xié)議中所有簇頭都是通過單跳的方式直接與Sink節(jié)點進行通信,另一方面在選擇簇頭的時候,還存在無法保證簇頭均勻分布的問題,容易造成簇頭“扎堆”現(xiàn)象,這些缺陷會造成遠離Sink節(jié)點的簇頭能量消耗過快,導致網(wǎng)絡壽命大大減少.而本文的QACO-LEACH,在分簇階段引入一個參數(shù)L,從而解決了簇頭分布不均勻的問題.ACO-LEACH在LEACH基礎上引入了蟻群算法,一定程度上實現(xiàn)了節(jié)約能耗和延長網(wǎng)絡生命周期的目的,但是使用蟻群算法搜尋路徑具有盲目性,容易造成局部最優(yōu)解,并且最優(yōu)路徑的收斂速度比較慢.針對這種現(xiàn)象,本文的QACO-LEACH利用量子蟻群算法的全局尋優(yōu)能力好和收斂速度快的優(yōu)點,很好的解決了簇間路由階段出現(xiàn)的問題,找到了全局最優(yōu)路徑,從而降低網(wǎng)絡能耗.

綜上所述,本文算法分別在分簇階段和簇間路由階段解決了LEACH的分簇不均勻以及傳統(tǒng)蟻群算法容易陷入局部最優(yōu)和收斂速度慢的問題,并能更好地找到最佳路徑.最終實現(xiàn)了預期結果,無線傳感器網(wǎng)絡生命周期延長效果明顯,對以后的研究具有很好的參考價值.

6 結束語

量子蟻群算法綜合了蟻群算法和量子進化算法的優(yōu)勢,克服了傳統(tǒng)蟻群算法的缺點,簡易的操作和相對成熟的理論研究,使算法更容易實現(xiàn),從而可以在一些優(yōu)化問題中達到更好的效果.本文在無線傳感器網(wǎng)絡中引入量子蟻群算法,對于螞蟻位置的改變,選用了量子進化算法中的量子旋轉門對代表螞蟻當前位置的量子比特進行更新來實現(xiàn).然后,依據(jù)位置的更新,實現(xiàn)蟻群信息素強度的更新.仿真結果表明,該方法提高了收斂速度,并增加了解的多樣性,從而找尋到最優(yōu)路由路徑,節(jié)約了網(wǎng)絡能耗,使網(wǎng)絡生命周期得以延長.在無線傳感器網(wǎng)絡節(jié)能優(yōu)化領域,提供了一個很好的解決方案.本文中算法在中小規(guī)模無線傳感器網(wǎng)絡中優(yōu)化效果明顯,在大規(guī)模乃至超大規(guī)模無線傳感器網(wǎng)絡中的效果有待實驗驗證.下一步將考慮在大規(guī)模無線傳感器網(wǎng)絡中進行優(yōu)化實驗,使其在大規(guī)模網(wǎng)絡中達到相同優(yōu)化效果.