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

孫其昌，朱正禮，張福全

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

0 引言

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

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

1 問題描述

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

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

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

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

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

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

2 麻雀搜索算法

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

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

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

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

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

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

(1)

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

(2)

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

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

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

(3)

當(dāng)R2

2.2 跟隨者位置更新

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

(4)

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

當(dāng)i>n/2時(shí)，其值為一個(gè)標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)與一個(gè)以自然對數(shù)為底數(shù)的指數(shù)函數(shù)的積，當(dāng)種群收斂時(shí)其取值符合標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)。(其值會(huì)收斂于0)。

當(dāng)i≤n/2時(shí)，其取值為當(dāng)前最優(yōu)的麻雀的位置加上該麻雀與最優(yōu)位置每一維距離隨機(jī)加減后，將總和均分到每一維上?？梢悦枋鰹樵诋?dāng)前最優(yōu)位置附近隨機(jī)找一個(gè)位置，且每一維距最優(yōu)位置的方差將會(huì)變得更小，即不會(huì)出現(xiàn)在某一維上與最優(yōu)位置相差較大，而其他位置相差較小(其值收斂于最優(yōu)位置)。

2.3 預(yù)警者位置更新

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

(5)

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

3.1 SSA改進(jìn)方向

SSA在求解最優(yōu)解在原點(diǎn)附近的問題時(shí)，其性能非常好，而當(dāng)待求解的最優(yōu)解距原點(diǎn)較遠(yuǎn)時(shí)，其性能將會(huì)迅速下降，收斂速度較慢。

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

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

t分布又稱學(xué)生分布(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分布進(jìn)行更新如式(6)所示：

(6)

(7)

算法流程如下：

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

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

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

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

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

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

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

3.3 測試函數(shù)驗(yàn)證

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

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

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

(a) F1

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

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

步驟1：初步成簇

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

(8)

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

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

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

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

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

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

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

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

(9)

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

(2) 簇首間距因子f2

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

(10)

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

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

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

(11)

式中，|Ci_avg|表示第i個(gè)簇內(nèi)所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)的平均鄰居節(jié)點(diǎn)數(shù)，|Cavg|表示整個(gè)網(wǎng)絡(luò)的N個(gè)節(jié)點(diǎn)的平均鄰居節(jié)點(diǎn)數(shù)。二者值越接近，每個(gè)簇的簇內(nèi)平均節(jié)點(diǎn)數(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)的影響因子在選取簇首時(shí)起到的作用越大。LEACH-ISSA算法流程如圖3所示。

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

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

5.1 仿真環(huán)境

本文實(shí)驗(yàn)采用Matlab2018b作為實(shí)驗(yàn)平臺(tái)，對LEACH算法和LEACH-ISSA算法進(jìn)行仿真實(shí)驗(yàn)比較。實(shí)驗(yàn)的能量模型采用文獻(xiàn)[14]使用的一階無線通信模型。d0為固定值，公式如下：

(13)

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

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

(14)

ERX(k,d)=kEelec，

(15)

EDA(k,d)=kEDA。

(16)

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

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

表2 實(shí)驗(yàn)參數(shù)表

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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