基于混沌粒子群與蟻群算法的WSN路由協議

鄭 波，崔寶同

（江南大學 物聯網工程學院，江蘇 無錫 214122）

無線傳感器網絡是將傳感器技術、微機電系統技術、無線通信技術、分布式信息處理技術集成使用的一種網絡[1]，能廣泛的應用在軍事、民用等各個領域。無線傳感器網絡與傳統網絡最大的區別是網絡能量有限。因此，如何減少網絡能量消耗，延長網絡生存周期，就成為無線傳感器網絡的研究重點之一。采用分簇路由協議和多跳通信路由是如今比較常用的方式。

LEACH協議是最早提出的分簇協議[2]，該協議采用隨機的簇頭選擇方式。節點成為簇頭的條件是它所產生的隨機數小于預設的閥值。LEACH協議的簇頭選擇是周期性進行的，為了延長網絡的生命周期，高效地利用網絡中所有的能量。LEACH協議最大的缺陷在于簇頭選擇過程中沒有考慮節點剩余能量，而這會引起網絡能量的消耗不均衡。而且簇頭到基站，簇頭到簇成員節點的通信都是采用單跳的方式，如果傳輸距離較遠，就會使節點能量迅速耗盡。此后，很多學者在這兩方面進行了研究改進。文獻[3]首次將剩余能量作為簇頭選擇的一個依據，使剩余能量多的節點成為簇頭的概率增加；文獻[4]在此基礎上進一步要求當選為簇頭的節點剩余能量必須高于網絡的平均能量。智能算法在解決簇頭選擇問題中有其獨特的優勢。文獻[4]就在基站采用模擬退火算法來改進協議。通過對蟻群算法的研究發現，蟻群算法對路徑尋優有著獨特的優勢。因此，本文首先用新的混沌粒子算法優化簇頭選擇，然后采用蟻群算法優化多跳路徑，綜合優化無線傳感器網絡的能量利用。

1 簇頭選擇機制

經典的分簇路由算法——LEACH算法，沒有考慮節點的剩余能量和簇成員之間的緊密度。簇頭在無線傳感器網絡中會承擔更多的任務，如果被選為簇頭的節點剩余能量少，能量就會很快耗盡，導致節點早亡。如果簇內節點通信距離較短即較為密集，則在數據傳輸過程中能量消耗就少。本文在考慮上述兩個因素后提出基于節點剩余能量和簇間緊密度的適應度函數，適應度函數定義如式（1）。

其中，f1代表能量消耗，f2代表簇間距離，α1，α2是影響因素的權重，α1+α2=1，c 代表特定的群，E，E′分別代表能量消耗和剩余能量，|Cc|代表群c中的節點數目。

1.1 新的混沌粒子群算法

粒子群算法易陷入局部最優，因此可以利用混沌變量的遍歷性，解決因為粒子停滯導致的算法早熟問題。

基本的粒子群算法的描述如下：

設搜索空間為D維，種群數為m，第i個粒子（i=1，2，…，m）的位置表示為 Zi=（zi1，zi2，ziD），Vi=（vi1，vi2，viD）為粒子 i的位置移動距離，Pi=（pi1，pi2，…，piD）表示第 i個粒子“飛行”歷史中最優位置，Pg=（pg1，pg2，…，pgD）表示整個種群歷史最優位置，t表示迭代次數。粒子根據以下公式更新速度和位置：

c1，c2為學習因子，其值高低對收斂速度有一定影響，但不大，一般取（0，2）之間的隨機值。 rand（）是[0，1]之間的隨機數。ω是慣性權重，起著權衡局部最優能力和全局最優能力的作用。當慣性權值較小時，算法的收斂速度很快，但是容易陷入局部最優；當慣性權值較大時，雖然不會陷入局部最優，但收斂速度很慢。所以一般采用公式（6）的慣性權重函數，使慣性權值隨線性減少。

其中，ωmax為初始權重；ωmin為最終權重；tmax為最大迭代次數；t為當前迭代次數。

本文采用文獻[5]的混沌粒子群算法，該算法是將混沌融入到粒子群過程中，能產生優于其他混沌粒子群優化算法的結果。

本文的簇頭選擇算法模型如下式[5]：

其中式（7）是用來更新粒子的速度公式。式（8）是混沌變量，對粒子的混沌程度產生影響。當cid（t）→0時，依舊采用粒子群算法進行位置更新，當cid（t）→1時，主要是粒子群個體的混沌在起作用。rid表示第i個粒子的第d維的混沌因子，是一個大于0.5小于1的值。式（9）是將混沌引入到粒子位置更新中。ψd定義為搜索測度。

根據文獻[6]的結論映射不依賴初始值位置，且比logistic或Tent映射的平均搜索效率分別提高了71.6%和62.6%。因此，文中采用Fuch映射，公式如（10）所示。

對于尋優而言，系統一直處于穩定或者混沌狀態都是不利的，只有在混沌與穩定之間相互交替才能尋找到最優值。就是在穩定時引入混沌，幫助粒子跳出局部最優；在不穩定時，加速向最優值靠近，加快收斂速度。通過下述兩個式子來判斷粒子所處的狀態：

當m<10-6且s<10-6且k<0.9tmax時，粒子處于穩定狀態，此時引入混沌，令 cid（t）=0.99；當 s>10-6且 k<0.9tmax時，粒子不穩定，為了加快收斂速度，令 Zid（t）=Pid（t）。

1.2 基于新的混沌算法的簇頭選擇

產生簇頭步驟：

假設初始的無線傳感器網絡，節點帶有相同的初始能量，第一輪采用LEACH算法的簇頭選舉機制。

第一輪簇頭選擇與LEACH算法相同，簇頭選舉出來后，采用蟻群算法計算簇頭到基站的多跳路徑。經過一輪運行以后各個節點的剩余能量產生了變化，不再相等了，第二輪以后采用混沌粒子群優化算法選舉簇頭。

基于混沌粒子群優化算法的簇頭選舉步驟：

1）初始化N個粒子，每個粒子代表一種分簇可能；

2）通過適應度函數計算粒子適應值，記錄全局最優解和粒子歷史最優解；

3）通過新的混沌粒子群算法更新粒子，并記錄個體最優解和全局最優解；

4）重復步驟 2）、3），直到最大迭代次數；

5）發布簇頭信息。

簇頭確定后向非簇頭節點發布廣播，非簇頭節點根據接收信號的強度選擇強度最大的簇頭，發送加入請求。

2 基于蟻群算法的多跳路由

與數據融合、計算等相比，無線傳感器網絡的主要能耗是發生在通信過程中，因此要節約網絡能量，就要改進通信方式，采用高效率的路由。在LEACH協議中，簇頭與其他節點包括基站通信，都是采用單跳通信的方式。因為簇頭到基站的距離往往比較遠，距離較遠的數據傳輸采用多徑衰落模型，會使簇頭能量快速耗盡，因此通過尋優方法來改進簇頭到基站的路由。

2.1 基于蟻群優化的多跳路由

蟻群算法只是單純的尋找從源到目的的最短路徑，在該路徑上螞蟻的數量將是最大的，這會導致這條路徑上的能量消耗最大，然而螞蟻在選擇下一跳時沒有考慮節點剩余能量。螞蟻運行可能會偏離基站。本文采用文獻[7]中采用的基于蟻群優化的LEACH路由協議。

位于簇頭i的螞蟻k選擇下一跳的簇頭j的概率為：

Ej-current是簇頭j的剩余能量，重新定義為允許螞蟻k訪問的下一跳簇頭的集合。在文獻[7]中沒有對能量對比的參數進行明確定義，本文中，Ep-current為當前無線傳感器網絡節點平均能量。通過該設定使節點在選擇下一跳是能夠選擇能量較多的節點。設定的規則是簇頭j在簇頭i的通信半徑內，簇頭j還沒被螞蟻k訪問過，簇頭j到基站的距離小于簇頭i到基站的距離。該設定規則是為了防止螞蟻k朝偏離基站的方向運行。ηij重新定義為：

ηij這樣定義是為了考慮傳輸路徑上的能耗。使離簇頭i近的簇頭有更大的機會成為下一跳簇頭。從（13）和（14）式中可以看出簇頭j的剩余能量越多，離簇頭i越近，被選為下一跳的概率就越大。

每一個簇頭上螞蟻按照下面的偽隨機碼規則決定下一跳選擇哪個簇頭：

q是一個服從[0，1]均勻分布的隨機數，q≤q0時按照先驗知識選擇路徑，否則就是按照一定的概率（t）選擇路徑。 q0是一個常數，可以通過設定q0的大小來使螞蟻以一定的概率開辟新路徑，防止陷入局部最優。l是一個服從蟻群算法的概率選擇的隨機數。

全局信息素更新：采用ASC信息素規則，信息素的揮發或釋放只在最優邊上進行。全局更新是在所有螞蟻完成它們路徑后執行使用下式對所建立的路徑進行更新：

其中，Lb為最優路徑的總長度。

局部信息素更新公式如下：

τ0為初始信息素濃度，ξ為局部每條邊上信息素蒸發率。在尋找最優路徑過程中，螞蟻每經過一條邊就運用式（17）更新這條邊上的信息素濃度。

假設基站為螞蟻的食物目的地，螞蟻從所在的簇頭開始尋找食物。螞蟻k到達基站后停止本次搜索，基站為終點。

1）初始化。設置最大迭代次數Nmax，計算簇頭間的距離dij，并用距離遠近排序；

2）將m個螞蟻均勻的放在簇頭，螞蟻是同構的。每個螞蟻攜帶出發簇頭的ID，所經過的中間簇頭的ID和剩余能量，中間簇頭間的距離。螞蟻開始循環；

（4）按照式（15）選擇下一跳簇頭 j；

5）螞蟻訪問過一個簇頭后就按式（17）立即更新該路徑上的信息素；

6）當 m只螞蟻都達到基站后，計算最優的 Lb，Lb=Σdij，用式（16）對最優的螞蟻路徑上進行信息素更新，使螞蟻主要集中在當前已找到的最優路徑領域內；

7）如果沒有停滯，或沒達到最大迭代次數就返回步驟2）；停滯是指在迭代范圍內3次搜索到相同的值；

8）輸出最優值。

3 系統模型

3.1 網絡模型

本文采用分層次網絡拓撲結構。網絡由簇成員節點、簇頭節點和基站組成。分簇算法將網絡節點分成多個簇。每個簇有一個簇頭節點和若干簇成員節點組成，簇成員節點將采集到的數據傳給簇頭節點，簇頭節點將自身采集到的信息與接收到的簇成員節點采集到的信息經過數據融合再傳給基站。基站能量不受限，擁有較強的處理能力、存儲能力和通信能力，起到連接無線傳感器網絡和外部網絡的作用。在本文中假設節點所攜帶的能量是有限的且能感知節點的剩余能量，有GPS定位功能能獲取自己相對基站的位置信息。

3.2 能耗模型

節點的主要能量消耗是產生在信息收發和處理過程，其他的能量消耗與之相比可忽略不計。本文所采用的能耗模型是由Heinzelman等在信道能量損耗模型基礎上提出的改進模型[8]。

該模型考慮了不同傳輸距離時無線信號對數據傳輸的影響，根據信號強度的衰落與傳輸距離的遠近分成了自由空間信道模型和多徑衰落信道模型。設定一個閥值d0，當傳輸距離d

接收節點消耗的能量為：

其中，Eelec是發送電路和接收電路的能量消耗；εfs和εmp分別是自由空間模型和多徑衰減模型中功率放大器的能量消耗；閥值

4 仿真分析

將本文算法在無線傳感器網絡中的性能進行matlab仿真，并與LEACH協議在相同條件下進行比較。參數設置如表1所示。

混沌粒子群優化算法的各參數為：初始化粒子數為20，c1=c2=2，ωmax=0.9，ωmin=0.4，α1=0.6，α2=0.4，ψd=200，rid=0.5+（0.005）rand。

蟻群算法約束參數設置為：α=0.1，β=3，ρ=0.1，m=K。

取200 m×200 m的區域，隨機部署200個節點，選用網絡生命周期和能耗兩個技術指標來評價算法的性能。

仿真圖1顯示了本文的協議與LEACH協議整個網絡總能耗的對比。縱軸代表網絡的總能量，橫軸代表仿真的時間。可見，從整個網絡能耗來看，本文的協議大大節省了能量消耗，延長了近400輪的網絡生存時間。而且由斜率來看，本文的協議能量消耗比較均衡。

表1 參數設置Tab.1 Parameters

圖1 能耗對比Fig.1 The energy consumption contrast

下面的圖2顯示了本文的協議與LEACH協議網絡生存周期的對比。從圖2中可以看出，LEACH協議第一個死亡節點出現在119輪，本文的協議的第一個死亡節點出現在800輪，延長了572%。一半節點的死亡，LEACH協議發生在540輪左右，本文的協議則在1 120輪左右，到1 110輪，LEACH協議節點基本已經死亡，而本文的協議則到了1 580輪。一半節點死亡時間延長了106.8%，網絡生存周期延長了41.99%，可以明顯看出延長了網絡壽命。

圖2 網絡生存周期對比Fig.2 The network lifetime comparison

5 結 論

本文提出了一種基于混沌粒子群和蟻群相結合的路由協議。利用混沌粒子群算法在簇頭選擇中的優勢，結合對節點剩余能量和簇的緊密性的考慮，改進了簇頭選舉策略。同時利用蟻群算法的尋優能力，優化多跳路由。兩種方法的結合有效的延長了網絡生命周期。下一步的研究主要針對智能算法優化多跳路徑。

[1]彭力.無線傳感器網絡技術 [M].北京:冶金工業出版社，2011.

[2]Heinzelman W，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless microsensor netwo-rks[C]//Proc.of the 33rd Annual Hawaii Internatioal Conf.on System Younis Scie-nces.Maui:IEEE Computer Society，2000:3005-3014.

[3]Handy M J，Haase M，Timmerrnann M D.Low energy adaptive clustering hiera-rchy with deterministic cluster-head sel-ection[C]//Proc.of the 4th IEEE Conf.on Mobile and Wireless Communications Ne-tworks.Stockholm:IEEE Communications Society，2002:368－372.

[4]Heinzelman W，Chandrakasan A，Balakr-ishnan H.An application-specific protocol architecture for wireless microsensor ne-tworks[J].IEEE Trans on Wireless Comm-unications，2002，1（4）:660－670.

[5]胥小波，鄭康鋒，李丹，等.新的混沌粒子群優化算法[J].通信學報，2012，33（1）:24-37.XU Xiao-bo，ZHENG Kang-feng，LI Dan，et al.New chaosparticle swarm optimization algorithm[J].Journal on Communications，2012，33（1）:24-37.

[6]傅文淵，凌朝東.自適應折疊混沌優化算法[J].西安交通大學學報，2013，47（2）:33-38.FU Wen-yuan，LING Chao-dong.An adaptive lterative chaos optimization method[J].Journal of Xi’An Jiaotong University，2013，47（2）:33-38.

[7]吳麗君.無線傳感器網絡LEACH協議的研究與改進[D].上海：華東理工大學，2010.

[8]Heunzelman W B，Chandrakasan A P，Balakrishnan.An application-specific protocol architecture for Wireless Microsensor Networks[J].IEEE Trans on Wireless Communications，2002，1（4）:660-670.