王 軍，丁丕欣，劉鼎坤

（1.沈陽化工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，沈陽 110142；2.遼寧省化工過程工業(yè)智能化技術(shù)重點(diǎn)實(shí)驗(yàn)室，沈陽 110142）

0 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSNs）由許多傳感器節(jié)點(diǎn)組成［1］，負(fù)責(zé)收集監(jiān)測區(qū)域的信息并傳輸給基站（BS）［2］。它是以自組織形式組成的大規(guī)模網(wǎng)絡(luò)，應(yīng)用領(lǐng)域廣泛，如：軍事、航天、救災(zāi)等［3］。雖然無線傳感器網(wǎng)絡(luò)部署方便、成本低，但存在節(jié)點(diǎn)能量有限、網(wǎng)絡(luò)生命周期短等問題［4］。因此，優(yōu)化分簇路由算法已成為延長整個(gè)網(wǎng)絡(luò)生命周期的一個(gè)研究對(duì)象。

針對(duì)WSNs在分簇路由中存在問題，HEINZELMA W R 等學(xué)者最早提出了LEACH 協(xié)議［5］，該協(xié)議通過隨機(jī)數(shù)與閾值比較進(jìn)行簇頭選舉，簇群內(nèi)部普通節(jié)點(diǎn)單跳傳輸給簇頭，簇頭節(jié)點(diǎn)將以單跳方式傳輸給基站，將整個(gè)過程分為簇內(nèi)和簇間傳輸兩個(gè)部分。朱素霞等學(xué)者基于LEACH 協(xié)議進(jìn)行改進(jìn)［6］，充分考慮節(jié)點(diǎn)能量、節(jié)點(diǎn)密度以及與基站距離等因素優(yōu)化閾值函數(shù)，其次通過成本函數(shù)選舉最優(yōu)簇頭，簇間通信根據(jù)距離因素選取單跳或多跳。張慧娟提出禁止擁塞節(jié)點(diǎn)擔(dān)任簇頭［7］，考慮節(jié)點(diǎn)的剩余能量及離匯聚節(jié)點(diǎn)距離選擇簇頭，利用貪婪啟發(fā)式Dijkstra算法構(gòu)建簇頭間的最短路徑，緩解簇頭的能量消耗。MARWAH M A 等采用智能優(yōu)化算法提高無線傳感器網(wǎng)絡(luò)的能量效率［8］，在簇頭選舉過程中用金鷹優(yōu)化算法選舉最后簇頭，黃色馬鞍形山羊算法優(yōu)化簇頭向基站傳輸?shù)穆窂剑档蛿?shù)據(jù)包傳輸?shù)哪芰繐p耗。富立琪等提出用K-means 聚類算法對(duì)整體節(jié)點(diǎn)進(jìn)行分簇［9］，并在每個(gè)簇群內(nèi)部考慮節(jié)點(diǎn)能量和鄰居節(jié)點(diǎn)等因素競選最優(yōu)簇首，數(shù)據(jù)傳輸采用單跳或多跳將數(shù)據(jù)包傳輸?shù)交尽?/p>

上述學(xué)者提出了不同的分簇路由協(xié)議，能有效地降低網(wǎng)絡(luò)能耗并延長網(wǎng)絡(luò)壽命，但在協(xié)議的設(shè)計(jì)過程中對(duì)簇首規(guī)模數(shù)，簇首選舉的局部與全局的尋優(yōu)分配，以及數(shù)據(jù)傳階段的路徑選取缺少針對(duì)性的研究，對(duì)此本文提出一種基于灰狼優(yōu)化和Dijkstra算法的分簇路由協(xié)議（clustered routing protocol based on gray wolf optimization and dijkstra algorithm，CRGWOD）。利用灰狼優(yōu)化算法的收斂速度快，能很好地平衡局部與全局最優(yōu)的特點(diǎn)，求解傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布的最優(yōu)簇首數(shù)，在每個(gè)簇群內(nèi)找出能量高、密度均勻，與基站位置合理以及當(dāng)選簇頭頻率較低的節(jié)點(diǎn)擔(dān)任簇頭節(jié)點(diǎn)。簇間路由階段結(jié)合簇頭節(jié)點(diǎn)能量和距離計(jì)算權(quán)值函數(shù)值，判斷權(quán)值函數(shù)用Dijkstra 算法選取最合理的簇間路由路徑。目的解決節(jié)點(diǎn)分布熱區(qū)現(xiàn)象，全面考慮網(wǎng)絡(luò)壽命延長的問題，提高網(wǎng)絡(luò)節(jié)點(diǎn)能源利用效率。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)結(jié)構(gòu)模型

本文采用的網(wǎng)絡(luò)結(jié)構(gòu)模型如圖1 所示，為精確計(jì)算節(jié)點(diǎn)間信息，確保基站持續(xù)穩(wěn)定接受數(shù)據(jù)，節(jié)點(diǎn)按照距離自主選擇合適的發(fā)射功率，以及避免節(jié)點(diǎn)遭受惡劣環(huán)境等因素影響，網(wǎng)絡(luò)結(jié)構(gòu)需滿足如下要求［10］：

圖1 網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Network structure

1）傳感器節(jié)點(diǎn)均勻分布、位置固定不變且具有唯一的ID。

2）基站具有無限的能量，且該網(wǎng)絡(luò)周圍無任何信號(hào)干擾。

3）每個(gè)傳感器都具有相同的屬性且位置相對(duì)穩(wěn)定。

4）每個(gè)傳感器節(jié)點(diǎn)發(fā)送與接收功率可控。

1.2 能耗模型

本文采用一階無線通信能耗模型［11］，其分為自由空間模型和多徑衰減模型。具體公式如式（1）～式（4）。

其中，ETX為發(fā)送abit數(shù)據(jù)的能耗；Eelec為收發(fā)1 bit數(shù)據(jù)的能耗；εfs為自由空間模型損耗因子；εmp為多徑衰減模型能量損耗因子；d為傳輸距離，ERx為接受abit 數(shù)據(jù)的能耗；EDA為融合每比特能量消耗；EMx為融合abit 數(shù)據(jù)的能耗。

2 CRGWOD算法

2.1 最優(yōu)簇首規(guī)模

能耗是評(píng)價(jià)網(wǎng)絡(luò)整體性能的其一標(biāo)準(zhǔn)，簇首的數(shù)目以及能量損耗對(duì)整個(gè)網(wǎng)絡(luò)起著至關(guān)重要的作用，本文網(wǎng)絡(luò)能量消耗分為：普通節(jié)點(diǎn)向簇首發(fā)送數(shù)據(jù)，簇首節(jié)點(diǎn)接受并融合數(shù)據(jù)，向中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。則網(wǎng)絡(luò)能耗一輪消耗能量為：

每個(gè)簇內(nèi)普通節(jié)點(diǎn)能耗為：

式中，dtoCH是每個(gè)簇內(nèi)普通節(jié)點(diǎn)到簇首的距離。在M×M模型內(nèi)部署的節(jié)點(diǎn)均勻分布，將N個(gè)節(jié)點(diǎn)平均地分布在K個(gè)呈圓狀的簇內(nèi)，則每個(gè)簇區(qū)域內(nèi)的密度為ρ，如圖2所示。

圖2 節(jié)點(diǎn)假設(shè)分布圖及半徑、密度公式Fig.2 Node assumption distribution diagram and formulas of radius and density

簇首節(jié)點(diǎn)能量消耗為：

整理上述式子，對(duì)網(wǎng)絡(luò)整體能耗Eall最小化，得最優(yōu)簇首數(shù)K與M、N、EELEC、EDA等有關(guān)，計(jì)算出最佳簇首規(guī)模數(shù)K：

式中，NCHs表示簇頭節(jié)點(diǎn)需要中繼的次數(shù)。

2.2 改進(jìn)灰狼優(yōu)化算法

2.2.1 灰狼優(yōu)化算法（GWO）

在灰狼優(yōu)化算法中，灰狼呈金字塔形狀，分為4個(gè)等級(jí)：α狼、β狼、δ狼、ω狼［12］。每一只狼都受α 狼的引導(dǎo)，進(jìn)行位置更新，灰狼狩獵的具體過程為：

式中，Xa（t）是經(jīng)過t次迭代后獵物的位置向量；X是灰狼個(gè)體所在的位置向量；A、C均為系數(shù)向量；a為收斂系數(shù)，在［2，0］區(qū)間內(nèi)線性遞減，r1和r2是介于0～1之間的隨機(jī)數(shù)。

狼群中其他狼的位置將會(huì)受α狼、β狼、δ狼所引導(dǎo)：

該算法與分簇路由算法有極大的相似性，其相似關(guān)系如表1 所示，將該算法解決應(yīng)用到簇頭選舉中的算法流程圖如圖3所示。

表1 無線傳感器網(wǎng)絡(luò)與灰狼優(yōu)化相似對(duì)應(yīng)表Table 1 Similar correspondence table between wireless sensor networks and gray wolf optimization

圖3 灰狼優(yōu)化算法解決簇頭選舉流程圖Fig.3 Flowchart of Gray wolf optimization algorithm solving the cluster head election

2.2.2 適應(yīng)值函數(shù)改進(jìn)

為優(yōu)化簇頭選取來提高整體網(wǎng)絡(luò)生命周期，在確定最優(yōu)簇首規(guī)模后，根據(jù)節(jié)點(diǎn)的狀態(tài)設(shè)定適應(yīng)值函數(shù)。簇頭節(jié)點(diǎn)所承擔(dān)的數(shù)據(jù)量大，因此，簇頭的選取應(yīng)具備節(jié)點(diǎn)的能量相對(duì)高，鄰居節(jié)點(diǎn)的密度相對(duì)大，簇頭頻率低等特點(diǎn)。下面從節(jié)點(diǎn)的能量、節(jié)點(diǎn)的密度、節(jié)點(diǎn)的位置以及擔(dān)任簇頭的頻率4 個(gè)方面設(shè)計(jì)適應(yīng)度函數(shù)。

節(jié)點(diǎn)能量水平：即節(jié)點(diǎn)的當(dāng)前剩余能量與節(jié)點(diǎn)的初始能量的比值。能量是節(jié)點(diǎn)處理數(shù)據(jù)必然條件，如果當(dāng)前節(jié)點(diǎn)的剩余能量高，比值就高，在相同條件下所能更好地處理數(shù)據(jù)，就應(yīng)當(dāng)選為簇頭。

節(jié)點(diǎn)的密度級(jí)：節(jié)點(diǎn)在其感知半徑范圍內(nèi)，所具有的鄰居節(jié)點(diǎn)數(shù)量，如果鄰居節(jié)點(diǎn)越多且距離小于感知半徑，周圍節(jié)點(diǎn)的密度就越高，越有可能承擔(dān)簇頭的責(zé)任。

式中，count（）表示返回符合條件的數(shù)量；dist（Ni，Nj）表示節(jié)點(diǎn)之間的距離；Rs表示節(jié)點(diǎn)的感知半徑。

節(jié)點(diǎn)位置：在簇群內(nèi)部，簇頭節(jié)點(diǎn)與每個(gè)節(jié)點(diǎn)之間的距離平均值，以及簇頭節(jié)點(diǎn)與基站之間距離的綜合考慮因素。距離的平均值可以反映出節(jié)點(diǎn)在空間中是否處于簇群內(nèi)部中心位置，可兼容并降低節(jié)點(diǎn)與其通信的能量損耗；在整體網(wǎng)絡(luò)布局中，簇頭與基站的距離短，所需傳輸?shù)南牡哪芰康?，一定程度上降低簇頭的能耗。

式中，Ncluster代表簇群內(nèi)節(jié)點(diǎn)數(shù)量；dist（Ni，BS）代表節(jié)點(diǎn)與基站的距離。

簇頭頻率：一個(gè)節(jié)點(diǎn)多次擔(dān)任簇頭，必要在下一次選擇中降低被選中擔(dān)任簇頭的幾率，簇頭節(jié)點(diǎn)需要處理接受、融合、轉(zhuǎn)發(fā)等任務(wù)，能量消耗速率大大增加，避免多次擔(dān)任可提高網(wǎng)絡(luò)整體的壽命，用Ncount表示當(dāng)選簇頭次數(shù)，具體公式如下：

基于節(jié)點(diǎn)能量、密度、位置以及簇頭頻率4個(gè)因素，通過權(quán)值控制的方式對(duì)適應(yīng)值函數(shù)進(jìn)行改進(jìn)：

式中，t1，t2，t3，t4為權(quán)重因子并對(duì)每一部分的權(quán)重比例呈遞減趨勢選取，且滿足

對(duì)于位置更新策略調(diào)整，本文采用文獻(xiàn)［13］中所提出的采用適應(yīng)度值去衡量變化情況，將式（15）中X（t+1）進(jìn)行更新，具體更新如式（21）和式（22）：

式中F1，F(xiàn)2，F(xiàn)3是改進(jìn)后的位置權(quán)重因子；Fα、Fβ、Fδ是每個(gè)簇內(nèi)的前三優(yōu)的適應(yīng)度函數(shù)值。根據(jù)改進(jìn)的適應(yīng)度函數(shù)，對(duì)每一個(gè)灰狼的適應(yīng)度函數(shù)進(jìn)行計(jì)算，選出最終的簇首，其算法流程如表2所示。

表2 改進(jìn)后選取簇頭算法表Table 2 Improved cluster head selection algorithm table

2.3 基于Dijkstra簇間路由

在簇間路由過程中，采用Dijkstra算法進(jìn)行選擇傳輸路徑，本文將距離與能量進(jìn)行權(quán)重分配后，再作為Dijkstra算法的權(quán)值進(jìn)行最短路徑選取，從而完成路由設(shè)計(jì)，獲得最合理的傳輸路徑。將簇頭節(jié)點(diǎn)與基站節(jié)點(diǎn)分成兩個(gè)集合，由基站節(jié)點(diǎn)擔(dān)任Dijkstra算法的初始節(jié)點(diǎn)，尋找合適的簇頭與基站的傳輸路徑。將簇頭節(jié)點(diǎn)與權(quán)值函數(shù)值構(gòu)建帶權(quán)圖G=（V，W），V代表簇頭節(jié)點(diǎn)與基站節(jié)點(diǎn)的集合，W代表權(quán)值函數(shù)值。在頂點(diǎn)集合中，需要先將頂點(diǎn)分為兩類，引入集合S和集合H，集合S中記錄基站節(jié)點(diǎn)和最小權(quán)值簇頭，集合H內(nèi)記錄未出現(xiàn)在最短權(quán)值路徑中的頂點(diǎn)集合，初始情況下集合S和集合H分別用S｛s0｝、H｛a1，a2，…，ak｝表示，s0表示基站，ai-K表示簇頭節(jié)點(diǎn)。集合H中的節(jié)點(diǎn)若想加入到集合S中需要滿足的權(quán)值函數(shù)如下：

式中，c1、c2為權(quán)重影響因子且滿足c1+c2=1，dis（t，BS）表示簇頭節(jié)點(diǎn)與基站的距離，表示當(dāng)前輪次簇頭的平均能量與待加入集合S的簇頭能量比重。算法詳細(xì)流程如下：

Step 1 初始化參數(shù)，將基站作為起點(diǎn)S｛s0｝，其他簇頭節(jié)點(diǎn)記為H｛a1，a2，…，ak｝。

Step 2 在集合H中計(jì)算出W值最小的頂點(diǎn)ai，把a(bǔ)i放入集合S中，此時(shí)需要更新中繼節(jié)點(diǎn)，以ai計(jì)算與集合H內(nèi)其余節(jié)點(diǎn)的W值，更新W值作為新的權(quán)值，如果W值變小就更新，否則，保留原始W值。

Step 3 在更新過程中記錄最小的權(quán)值路徑，當(dāng)W值不再變化并H集合仍有簇頭，則返回Step 1，重新記錄新的路徑。

Step 4 當(dāng)集合H內(nèi)沒有簇頭節(jié)點(diǎn)時(shí)，輸出最終的最小權(quán)值路徑，該路徑就是簇頭在數(shù)據(jù)傳輸過程中將數(shù)據(jù)傳輸?shù)交镜穆窂健?/p>

3 實(shí)驗(yàn)仿真分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)定

為檢驗(yàn)本文算法在延長網(wǎng)絡(luò)壽命方面的仿真效果，在MATLAB R2019a 平臺(tái)進(jìn)行算法對(duì)比分析，對(duì)LEACH 協(xié)議、PEGASIS 協(xié)議、文獻(xiàn)［14］中的ABC算法，以及本文算法在網(wǎng)絡(luò)系統(tǒng)能量、節(jié)點(diǎn)數(shù)量變化、1 100～1 500 輪死亡節(jié)點(diǎn)數(shù)量3 個(gè)方面驗(yàn)證本文算法的優(yōu)化性。擬定100 m×100 m 的實(shí)驗(yàn)仿真區(qū)域，均勻分布100 個(gè)節(jié)點(diǎn)，基站位于區(qū)域中心，具體參數(shù)如表3所示。

表3 實(shí)驗(yàn)參數(shù)表Table 3 Experimental parameter table

3.2 節(jié)點(diǎn)數(shù)量變化分析

死亡節(jié)點(diǎn)數(shù)量體現(xiàn)出網(wǎng)絡(luò)的整體穩(wěn)定性，如圖4 所示，600 輪之后幾種算法出現(xiàn)死亡節(jié)點(diǎn)，死亡的節(jié)點(diǎn)越多對(duì)網(wǎng)絡(luò)整體的影響越大，同時(shí)死亡速度也影響網(wǎng)絡(luò)收集信息的效率。LEACH 協(xié)議約在800輪之后出現(xiàn)明顯的節(jié)點(diǎn)死亡，1 300輪節(jié)點(diǎn)死亡數(shù)幾乎達(dá)到最值，而PEGASIS 算法1 050 輪后死亡節(jié)點(diǎn)增加并大約僅用200 輪就達(dá)到最大值，雖然前期死亡節(jié)點(diǎn)較少，但局部死亡速率較快的情況，對(duì)無線傳感器網(wǎng)絡(luò)整體的影響不容忽略，相比之下，LEACH 的整體變化比PEGASIS 好。相比傳統(tǒng)的分簇路由算法，文獻(xiàn)中提到的ABC 算法有了明顯的提升，進(jìn)行1 500 輪節(jié)點(diǎn)死亡率達(dá)84%，本文算法節(jié)點(diǎn)相對(duì)穩(wěn)定，比ABC 算法的能量消耗更加均勻，進(jìn)行1 500輪節(jié)點(diǎn)死亡率未達(dá)到80%，顯著地提高了網(wǎng)絡(luò)的生命周期。

圖4 節(jié)點(diǎn)數(shù)量變化圖Fig.4 Change diagram of the number of nodes

3.3 系統(tǒng)能量變化分析

本節(jié)針對(duì)4 種算法的網(wǎng)絡(luò)能量變化進(jìn)行分析。下頁圖5 中LEACH 算法在1 320 輪消耗了所有能量，PEGASIS 算法在第1 210 輪消耗了所有能量，ABC算法在第1 500輪能量還剩余14%，本文算法在第1 500 輪能量剩余23%，在1 300 輪前消耗速率較慢。可見，本文算法相比于其他3個(gè)算法，通過改進(jìn)灰狼優(yōu)化算法選舉最優(yōu)簇頭，將能量、節(jié)點(diǎn)密度作為首要考慮因素，將簇頭的位置和簇頭的當(dāng)選頻次作為輔助因素，簇間路由不再將單一的距離作為權(quán)值，采用能量距離作為權(quán)值的迪杰斯特拉路徑規(guī)劃，可以更好地平衡網(wǎng)絡(luò)整體能耗，延長網(wǎng)絡(luò)能耗，實(shí)驗(yàn)結(jié)果與理論預(yù)想相符。

圖5 系統(tǒng)剩余能量變化圖Fig.5 Residual energy change diagram of the system

3.4 關(guān)鍵期節(jié)點(diǎn)數(shù)量分析

本節(jié)將1 100～1 500 輪節(jié)點(diǎn)死亡數(shù)量進(jìn)行對(duì)比，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)一般處于環(huán)境惡劣，地勢偏僻，以及軍事勘測過程中，不會(huì)經(jīng)常性地更換，同時(shí)受到節(jié)點(diǎn)的能量受限，所以，對(duì)于同等環(huán)境下，輪數(shù)越多，死亡節(jié)點(diǎn)數(shù)量越少，所收集的數(shù)據(jù)就越多。認(rèn)為1 100 輪之后的節(jié)點(diǎn)整體情況是評(píng)價(jià)一個(gè)網(wǎng)絡(luò)性能的關(guān)鍵。從圖6 中可以看到，LEACH 算法和PEGASIS 算法在1 200 輪后節(jié)點(diǎn)幾乎死亡，而ABC算法和本文提出的算法有明顯優(yōu)勢，死亡節(jié)點(diǎn)數(shù)量少且均衡變化，同時(shí)本文算法的相比較ABC 算法，死亡節(jié)點(diǎn)數(shù)量相差近100 輪，從而提升了數(shù)據(jù)傳輸效率，穩(wěn)定性適合在特殊軍事勘測等環(huán)境中的信息數(shù)據(jù)收集，充分發(fā)揮了灰狼優(yōu)化算法的尋優(yōu)能力，適應(yīng)度函數(shù)的改進(jìn)更進(jìn)一步優(yōu)化簇頭選舉的精確性，Dijkstra 算法在簇間路由構(gòu)建中減少簇頭的能耗，避開路徑近節(jié)點(diǎn)能量少的情況，在關(guān)鍵時(shí)期充分發(fā)揮傳感器收集信息的能力。

圖6 1 100～1 500輪節(jié)點(diǎn)死亡數(shù)量對(duì)比圖Fig.6 Comparison chart of the number of deaths at 1 100～1 500 round nodes

4 結(jié)論

本文提出一種基于灰狼優(yōu)化和Dijkstra 最小權(quán)值路徑的分簇路由算法。通過能量、節(jié)點(diǎn)密度、位置、簇頭頻次來改進(jìn)適應(yīng)度函數(shù)，用灰狼優(yōu)化算法基于適應(yīng)度值進(jìn)行位置更新選舉最優(yōu)簇首，充分發(fā)揮了全局搜索性和收斂性的優(yōu)勢，均衡每個(gè)簇群內(nèi)的網(wǎng)絡(luò)能量消耗，簇間路由通信階段，采用基于權(quán)值函數(shù)的Dijkstra路徑通訊，降低簇頭節(jié)點(diǎn)的能量消耗。最后將本文算法與LEACH、PEAGASIS、ABC 算法仿真對(duì)比，通過結(jié)果分析，本文算法在收集數(shù)據(jù)過程中節(jié)點(diǎn)死亡速率降低，網(wǎng)絡(luò)整體的能量消耗降低，關(guān)鍵期節(jié)點(diǎn)仍保持均衡的狀態(tài)，有效地提高了網(wǎng)絡(luò)生命周期。