基于改進SSA優(yōu)化WSN分簇協(xié)議

孫其昌，朱正禮，張福全

(南京林業(yè)大學 信息科學技術學院，江蘇 南京 210037)

0 引言

無線傳感器網(wǎng)絡(Wireless Sensor Networks，WSN)是被廣泛使用的Ad Hoc無線網(wǎng)絡類型之一[1]，它主要由部署在分散目標區(qū)域中的大量微型且廉價的低功耗傳感器節(jié)點組成。無線傳感器網(wǎng)絡的主要限制是傳感器節(jié)點的電源受限。電池供電的傳感器通常部署在惡劣、無人值守的環(huán)境中，在這些環(huán)境中幾乎不可能更換電池，導致傳感器節(jié)點可用的能量受到限制[2]。因此，最小化能耗以延長網(wǎng)絡生命周期是無線傳感器網(wǎng)絡研究的重要課題。由于傳感器節(jié)點的大部分能量消耗是由無線通信引起的，因此選擇有效的路由算法可以顯著降低通信能量[3]。LEACH是目前最流行也是最早的分層路由協(xié)議之一。在典型的分層路由算法中，許多后續(xù)路由協(xié)議中都引用LEACH中的分簇思想。分簇方法減少網(wǎng)絡的能量消耗并改善網(wǎng)絡的壽命。LEACH的核心概念是輪回制，基本思想是周期性地隨機選擇一個簇首節(jié)點，并在傳感器節(jié)點之間平均分配網(wǎng)絡能量負荷[4]。LEACH協(xié)議一直是研究的熱點，事實證明LEACH與一般的平面多跳路由協(xié)議和靜態(tài)分層算法相比，可以將網(wǎng)絡生命周期延長15%。但是，LEACH協(xié)議未指定群集頭節(jié)點如何均勻分布，并且由于成為簇首的每個節(jié)點消耗的能量大致相同，因此該協(xié)議不適用于節(jié)點能量不平衡的網(wǎng)絡[5]。

在本文中，考慮節(jié)點的位置和剩余能量，以及集群中的成員節(jié)點數(shù)量，通過改善簇首選擇機制并進行仿真驗證。提出一種基于改進麻雀搜索算法(Improved Sparrow Search Algorithm,ISSA)的分簇路由協(xié)議，在考慮簇內鄰居節(jié)點數(shù)量、能量和距離分布信息的前提下，優(yōu)化簇首的選擇。

1 問題描述

傳統(tǒng)LEACH協(xié)議將網(wǎng)絡中所有存活的傳感器節(jié)點采用單層模式劃分，把網(wǎng)絡內非死亡傳感器節(jié)點劃分為成員節(jié)點和簇首節(jié)點。成員節(jié)點和簇首節(jié)點進行簇內通信，簇首節(jié)點和Sink節(jié)點進行簇間通信。LEACH協(xié)議按“輪”周而復始直至節(jié)點全部死亡或者達到預設的結束條件，每一輪包括兩個階段，即建立階段和穩(wěn)定階段，對應簇首選舉、簇的劃分和數(shù)據(jù)傳輸階段[6]。

LEACH協(xié)議將網(wǎng)絡劃分層次，可在一定程度上均分能耗，提高網(wǎng)絡生存周期。同時，LEACH協(xié)議減少信息傳輸?shù)臅r耗，且簇的劃分也在一定程度上維系拓撲結構，使得網(wǎng)絡更健壯[7]。隨著對LEACH的深入研究，研究人員發(fā)現(xiàn)LEACH協(xié)議存在以下不足：

① LEACH協(xié)議在選舉簇首時，節(jié)點等概率成簇，沒有考慮到節(jié)點的剩余能量,使得能量小的節(jié)點可能被選為簇首，從而導致能量很快耗盡。

② LEACH協(xié)議在選舉簇首時未考慮節(jié)點位置，使得選出的簇首可能分布在邊緣或聚集在一起，加劇能耗。

③ LEACH協(xié)議每一輪中產(chǎn)生的簇首數(shù)是隨機的，選出的簇首數(shù)可能超出網(wǎng)絡正常運行的需求，從而降低網(wǎng)絡內節(jié)點的生命周期。

為改進LEACH協(xié)議存在的不足，本文提出一種新的路由協(xié)議——LEACH-ISSA。LEACH-ISSA采用集中式控制策略，每輪各階段與LEACH 協(xié)議相同，LEACH-ISSA 相較于LEACH協(xié)議的改進之處在于利用ISSA優(yōu)化WSN分簇過程采用LEACH-ISSA協(xié)議在簇首選舉過程中會根據(jù)節(jié)點的能量和位置以及簇內成員節(jié)點數(shù)等信息選擇簇首。

2 麻雀搜索算法

麻雀搜索算法(Sparrow Search Algorithm,SSA)[8]是根據(jù)麻雀覓食并逃避捕食者的行為而提出的群智能優(yōu)化算法。SSA主要模擬麻雀群覓食的過程。麻雀覓食過程也是發(fā)現(xiàn)者-跟隨者模型的一種，同時還疊加偵查預警機制[9-10]。麻雀群中找到食物較好的個體作為發(fā)現(xiàn)者，其他個體作為跟隨者，同時種群中選取一定比例的個體進行偵查預警，如果發(fā)現(xiàn)危險則放棄食物。

SSA中每個個體為麻雀，它們只有一個屬性“位置”——代表它找到的食物的位置。每只麻雀有3種可能的行為：

① 作為發(fā)現(xiàn)者，持續(xù)搜索食物，不斷更新位置，尋找最優(yōu)位置；

② 作為跟隨者，跟隨發(fā)現(xiàn)者覓食；

③ 作為預警者，有危險則放棄食物。

在d維解空間內每只麻雀的位置為適應度值。這群麻雀中有n只麻雀，每代選取種群中位置最好的pn只麻雀作為發(fā)現(xiàn)者，剩余的n-pn只麻雀作為跟隨者。麻雀的位置X可以用以下矩陣表示：

(1)

式中，n為麻雀的數(shù)量，d表示要優(yōu)化的變量的維數(shù)。麻雀的個體適應度值可以用以下向量表示：

(2)

式中，n表示麻雀的數(shù)量，F(xiàn)x中每行的值表示個體的適應度值。

2.1 發(fā)現(xiàn)者位置更新

在每次迭代過程中，發(fā)現(xiàn)者的位置更新如下：

(3)

當R2

2.2 跟隨者位置更新

在每次迭代過程中，跟隨者的位置更新如下：

(4)

式中，XP為發(fā)現(xiàn)者當前最佳位置，Xworst表示當前種族最差位置。另外，A表示1×d維矩陣，其中每個元素隨機分配1或-1，并且A+=AT(AAT)-1。

當i>n/2時，其值為一個標準正態(tài)分布隨機數(shù)與一個以自然對數(shù)為底數(shù)的指數(shù)函數(shù)的積，當種群收斂時其取值符合標準正態(tài)分布隨機數(shù)。(其值會收斂于0)。

當i≤n/2時，其取值為當前最優(yōu)的麻雀的位置加上該麻雀與最優(yōu)位置每一維距離隨機加減后，將總和均分到每一維上。可以描述為在當前最優(yōu)位置附近隨機找一個位置，且每一維距最優(yōu)位置的方差將會變得更小，即不會出現(xiàn)在某一維上與最優(yōu)位置相差較大，而其他位置相差較小(其值收斂于最優(yōu)位置)。

2.3 預警者位置更新

種群覓食時，會選取部分麻雀負責警戒，當天敵靠近時，無論是發(fā)現(xiàn)者還是跟隨者，都將會放棄當前的食物而飛到另一個位置。每代從種群中隨機選取SD(一般取10%～20%)只麻雀負責預警行為。其位置更新公式為：

(5)

3 改進的SSA優(yōu)化算法

3.1 SSA改進方向

SSA在求解最優(yōu)解在原點附近的問題時，其性能非常好，而當待求解的最優(yōu)解距原點較遠時，其性能將會迅速下降，收斂速度較慢。

由于SSA的各麻雀收斂于當前最優(yōu)解的方式是直接跳躍到當前最優(yōu)解附近，不是像其他進化算法那樣向最優(yōu)解移動，這就導致SSA容易陷入局部最優(yōu)，且全局搜索能力較弱。為避免SSA的局部收斂，改進其全局優(yōu)化函數(shù)，在麻雀位置更新時引入自適應t分布的變異策略，借此來提高收斂速度并避免算法陷入局部最優(yōu)。

3.2 自適應t分布策略

t分布又稱學生分布(Student’s t-distribution)，含有參數(shù)自由度n，它的曲線形態(tài)與自由度n的大小有關，n值越小，其曲線越平坦，曲線中間越低，曲線雙側尾部翹得越高[11]。高斯分布(Gaussian)、柯西分布(Cauchy)與t分布的對比如圖1所示。

圖1 3種分布對比圖Fig.1 Comparison of three distributions

對麻雀位置利用自適應t分布進行更新如式(6)所示：

(6)

(7)

算法流程如下：

步驟1：初始化參數(shù)，包括種群數(shù)量N、最大迭代次數(shù)、發(fā)現(xiàn)者比例PD、預警者比例SD、預警閾值R2；

步驟2：計算麻雀種群個體適應度值，找出當前最優(yōu)適應度值和最差適應度值以及二者對應的位置；

步驟3：從適應度值較優(yōu)的麻雀中，選取部分麻雀作為發(fā)現(xiàn)者，按照式(7)重新更新位置；

步驟4：步驟3余下的麻雀作為跟隨者；

步驟5:從麻雀種群中隨機選擇部分麻雀作為預警者；

步驟6：再次計算麻雀個體適應度值并更新麻雀位置；

步驟7：是否滿足停止條件，滿足則退出，輸出結果；否則，重復執(zhí)行步驟2～6。

3.3 測試函數(shù)驗證

本小節(jié)通過使用4個標準測試函數(shù)如表1所示，驗證所提出的ISSA的可行性和有效性。

表1 測試函數(shù)及參數(shù)

如圖2所示，SSA和ISSA應用在4個基準函數(shù)上的收斂曲線(y軸為當前最佳收斂值)。從圖中可以看出，ISSA在收斂速度和收斂精度上均優(yōu)于 SSA。

(a) F1

4 應用ISSA優(yōu)化WSN分簇

基于ISSA優(yōu)化的分簇路由協(xié)議(LEACH-ISSA),通過優(yōu)化簇首的選擇來避免部分節(jié)點能量過度損耗，從而降低死亡節(jié)點的出現(xiàn)概率。算法主要步驟如下：

步驟1：初步成簇

使用LEACH協(xié)議對目標網(wǎng)絡進行簇的初步劃分，形成的簇首集稱為候選簇首集,設定能量閾值E0，排除低能量節(jié)點后，有M個節(jié)點被選為候選簇首組成新的候選簇首集[8]。E0為網(wǎng)絡中所有存活節(jié)點能量的平均值：

(8)

式中，N為網(wǎng)絡中節(jié)點的總數(shù)，Ei為節(jié)點i當前的剩余能量，D為死亡節(jié)點數(shù)，剩余能量大于閾值E0的節(jié)點才可作為候選簇首節(jié)點。此時只考慮節(jié)點剩余能量，并未考慮各節(jié)點的位置、鄰居節(jié)點數(shù)、與基站的距離等因素，所以候選簇首只負責收集、發(fā)送節(jié)點信息，不進行數(shù)據(jù)傳輸。

步驟2：候選簇首信息收集

簇內節(jié)點將自身的位置、當前能量、鄰居節(jié)點數(shù)等信息傳遞給候選簇首，候選簇首將各自包含的節(jié)點信息發(fā)送到基站。

步驟3：LEACH-ISSA算法優(yōu)化并確定簇首

該階段為LEACH-ISSA優(yōu)化算法的核心階段，由基站進行集中式控制[12]。每輪基站先接收當前候選簇首集，簇首集中每個候選簇首節(jié)點包含對應簇內節(jié)點的信息[13]。基站依據(jù)定義的適應值函數(shù)，使用LEACH-ISSA算法評價簇首集中每個候選簇首，并不斷更新尋找最優(yōu)適應值，對應找到食物的麻雀位置為該種群的最優(yōu)位置，即該簇的最優(yōu)簇首。優(yōu)化后的最優(yōu)簇首位置可能和實際節(jié)點信息有差別，取最近節(jié)點位置為實際最優(yōu)簇首節(jié)點位置。最終得到M個最優(yōu)簇首組成最佳簇首集。

為選取最優(yōu)簇首建立對應的適應函數(shù)，本文主要設計如下幾個決策因子：

(1) 簇首剩余能量因子f1

將各節(jié)點的剩余能量引入適應值函數(shù)，作為簇首剩余能量因子。簇首剩余能量因子表示網(wǎng)絡內所有存活節(jié)點的能量與簇首能量的比值，公式為：

(9)

式中，ECHj表示簇首節(jié)點的能量。若簇首節(jié)點的剩余能量越高，則f1值越小，表示該函數(shù)傾向于選擇剩余能量高的節(jié)點為簇首，從而均衡網(wǎng)絡負載，延長網(wǎng)絡壽命。

(2) 簇首間距因子f2

初始分簇時可能出現(xiàn)分簇不均勻的情況，使得簇首過于靠近，且簇首會處于簇內邊緣位置。由于簇內采用單跳通信，加大了簇內節(jié)點到簇首的通信消耗。因此引入簇首之間距離因子，公式為：

(10)

式中，d(CHi,CHM)表示簇首i～M的距離，用于調整簇首間距。d(CHi,BS)表示簇首i到基站的距離，用于調整簇首到基站的距離。當每輪初始分簇得到對應M值時，為使f2越小，需減小簇首與基站的距離,同時增大簇首之間距離，使簇首在整個網(wǎng)絡中分布更分散。

(3) 鄰居節(jié)點數(shù)因子f3

引入鄰居節(jié)點數(shù)因子，選簇時應該給予簇內鄰居節(jié)點數(shù)多的節(jié)點更多成為簇首的機會，減少通信距離。當與整個網(wǎng)絡平均鄰居節(jié)點數(shù)相近時，簇首分布更均勻，公式為：

(11)

式中，|Ci_avg|表示第i個簇內所有節(jié)點的鄰居節(jié)點數(shù)的平均鄰居節(jié)點數(shù)，|Cavg|表示整個網(wǎng)絡的N個節(jié)點的平均鄰居節(jié)點數(shù)。二者值越接近，每個簇的簇內平均節(jié)點數(shù)越均勻，對應f3的值越小。綜上所述，適應值函數(shù)如下所示：

fitness=αf1+βf2+λf3，

(12)

式中，α，β，λ為用戶定義的常數(shù)，表示3組因子對適應值函數(shù)的影響程度。α+β+λ=1，依據(jù)需要可調整相應權重，對應權重取值越高表示相對應的影響因子在選取簇首時起到的作用越大。LEACH-ISSA算法流程如圖3所示。

圖3 LEACH-ISSA每輪算法流程圖Fig.3 LEACH-ISSA algorithm flow chart for each round

5 仿真與結果分析

5.1 仿真環(huán)境

本文實驗采用Matlab2018b作為實驗平臺，對LEACH算法和LEACH-ISSA算法進行仿真實驗比較。實驗的能量模型采用文獻[14]使用的一階無線通信模型。d0為固定值，公式如下：

(13)

式中，εfs表示自由空間損耗，εamp表示多徑衰落損耗。節(jié)點在距離d上傳輸kbit時，若傳輸距離大于d0時,采用自由空間模型；小于等于d0時，采用多路徑消耗模型。

在能耗計算上，以k表示一個數(shù)據(jù)分組的比特數(shù),Eelec表示每傳輸1 bit數(shù)據(jù)的能耗，EDA表示每融合1 bit數(shù)據(jù)的能耗。距離為d的兩節(jié)點間傳輸kbit數(shù)據(jù)的發(fā)送能耗ETX(k,d)和接收能耗ERX(k,d)，以及融合kbit數(shù)據(jù)的融合能耗EDA(k,d)計算方法分別為：

(14)

ERX(k,d)=kEelec，

(15)

EDA(k,d)=kEDA。

(16)

式(14)為自由空間模型或多路衰減模型。考慮距離的影響因素，采取設定傳輸距離閾值d0，將節(jié)點的發(fā)送能耗劃分為自由空間能耗和多徑衰減能耗兩種模式。閾值公式如式(13)，如果傳輸距離小于d0，采用前者；如果傳輸距離大于d0，則采用后者。接收節(jié)點的能耗公式不變。

在仿真實驗中，無線傳感器網(wǎng)絡由100個具有定位功能的節(jié)點組成，節(jié)點在指定大小區(qū)域內隨機分布，基站BS位于坐標(x=150,y=150)，每個節(jié)點初始能量相同為0.1 J，實驗參數(shù)如表2所示。

表2 實驗參數(shù)表

5.2 仿真結果和分析

為評價LEACH-ISSA協(xié)議的效果，實驗將從網(wǎng)絡剩余能量、生存時間以及簇首能量消耗與LEACH、LEACH-SSA協(xié)議進行對比。為更符合實際，設定當死亡節(jié)點數(shù)在80%以上，仿真結束。

圖4、圖5為整個區(qū)域內存活節(jié)點數(shù)隨著輪次增加的變化，圖中顯示LEACH協(xié)議第一個死亡節(jié)點在57輪，LEACH-SSA協(xié)議為469輪次， LEACH-ISSA協(xié)議在706輪。LEACH協(xié)議達到80%死亡節(jié)點在558輪，LEACH-SSA為875輪次，LEACH-ISSA為911輪次。由此說明，經(jīng)LEACH改進的LEACH-ISSA算法可有效避免節(jié)點過早死亡，減少損耗，達到延長整個網(wǎng)絡生存周期的目的。

圖4 存活節(jié)點數(shù)對比圖Fig.4 Comparison of the number of surviving nodes

圖5 死亡節(jié)點數(shù)1%、10%、80%輪次對比圖Fig.5 Comparison of 1%,10%,and 80% of the number of dead nodes

圖6為整個網(wǎng)絡剩余總能量的比較，從圖中可以看出，相同初始能量下LEACH-ISSA協(xié)議中網(wǎng)絡剩余總能量大于LEACH協(xié)議和LEACH-SSA協(xié)議，表明整個網(wǎng)絡的能量消耗得到有效降低。

圖6 剩余能量對比圖Fig.6 Comparison of remaining energy

圖7為網(wǎng)絡中簇首每輪消耗能量的比較，因為在整個網(wǎng)絡運行中，節(jié)點作為簇首時的能耗最大，所以對簇首選擇的改進最有效。通過對比3種協(xié)議在每輪簇首節(jié)點消耗的能量，發(fā)現(xiàn)LEACH-ISSA協(xié)議每輪簇首消耗的總能量明顯小于LEACH協(xié)議，表示LEACH-ISSA協(xié)議排除不必要的簇首節(jié)點，減少簇首數(shù)量。另外從圖中可以看出LEACH-ISSA協(xié)議簇首整體消耗相比于LEACH協(xié)議更均衡。

圖7 簇首能耗圖Fig.7 Energy consumption diagram of cluster head

結果顯示，在80%節(jié)點死亡仿真結束前提下， LEACH-ISSA算法生命曲線明顯優(yōu)于其他兩種算法。與LEACH 算法相比，本文算法節(jié)點存活率提高63%左右，與使用LEACH-SSA相比，本文算法節(jié)點存活率提高4%左右，有效均衡網(wǎng)絡中的能量。

6 結論

針對LEACH協(xié)議的不足，提出LEACH-ISSA協(xié)議。首先對SSA進行改進；然后利用ISSA，兼顧節(jié)點剩余能量、位置及相鄰節(jié)點等因素，使LEACH協(xié)議的簇首選擇分布更加合理，成簇效果得到優(yōu)化。有效降低網(wǎng)絡的整體能耗，延長網(wǎng)絡的生命周期。下一步工作重點將考慮結合WSN路由路徑規(guī)劃進行優(yōu)化。