孫其昌，朱正禮，張福全

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

0 引言

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

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

1 問題描述

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

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

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

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

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

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

2 麻雀搜索算法

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

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

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

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

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

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

(1)

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

(2)

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

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 預(yù)警者位置更新

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

(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ù)，在麻雀位置更新時引入自適應(yīng)t分布的變異策略，借此來提高收斂速度并避免算法陷入局部最優(yōu)。

3.2 自適應(yīng)t分布策略

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

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

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

(6)

(7)

算法流程如下：

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

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

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

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

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

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

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

3.3 測試函數(shù)驗證

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

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

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

(a) F1

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

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

步驟1：初步成簇

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

(8)

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

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

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

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

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

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

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

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

(9)

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

(2) 簇首間距因子f2

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

(10)

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

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

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

(11)

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

fitness=αf1+βf2+λf3，

(12)

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

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

5 仿真與結(jié)果分析

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)為自由空間模型或多路衰減模型?？紤]距離的影響因素，采取設(shè)定傳輸距離閾值d0，將節(jié)點的發(fā)送能耗劃分為自由空間能耗和多徑衰減能耗兩種模式。閾值公式如式(13)，如果傳輸距離小于d0，采用前者；如果傳輸距離大于d0，則采用后者。接收節(jié)點的能耗公式不變。

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

表2 實驗參數(shù)表

5.2 仿真結(jié)果和分析

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

圖4、圖5為整個區(qū)域內(nèi)存活節(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)絡(luò)生存周期的目的。

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

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

圖7為網(wǎng)絡(luò)中簇首每輪消耗能量的比較，因為在整個網(wǎng)絡(luò)運行中，節(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

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

6 結(jié)論

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