基于非均勻分簇的野外觀測儀器網絡路由協議研究

胡 軍，王 磊，火久元，劉 夢，巨 濤

（1.甘肅億網科技網絡技術有限公司，甘肅 蘭州 730000；2.蘭州交通大學 電子與信息工程學院，甘肅 蘭州 730070）

0 引言

野外觀測通過在野外建立觀測站對地球系統的關鍵要素進行長期的監測與分析，是大氣科學、生態學、環境科學等研究的主要數據來源。我國寒旱區面積廣闊，生態環境脆弱復雜，自然資源豐富。寒旱區野外觀測經過50 多年的發展，已經形成覆蓋我國寒旱區主要生態、環境區的野外觀測網絡體系。該觀測系統通過觀測、實驗以及示范，為寒旱區的科學研究提供了重要依據，是我國寒旱區科學研究體系中不可缺少的組成部分［1］。

受到環境限制，寒旱區野外觀測臺站大部分位于高寒、干旱的惡劣環境下，影響了臺站的網絡建設和信息獲取，這些問題嚴重阻礙了寒旱區科學研究工作的進展。因此，需要對寒旱區觀測儀器組網問題進行研究，設計一種高效、穩定的路由協議，實現對寒旱區野外環境長期、有效的觀測。經過前期的調查研究，本文發現野外觀測儀器組網和無線傳感器網絡（Wireless Sensor Network，WSN）具有很高的相似性，例如二者都是自組織網絡，且都是無線傳輸介質等［2-3］。因此，本文將根據野外觀測儀器組網特點，結合WSN 技術對路由協議進行設計與改進。

為了減少網絡的通信能耗，學者們提出多種基于分簇的層次性路由協議［4］。分簇減少了發送的數據包數量和網絡信息冗余，可以降低能耗，延長網絡的生命周期?；诜执氐穆酚蓞f議可分為均勻分簇和非均勻分簇兩種。均勻分簇算法在網絡中構造大小相同的分簇，雖然通過合理的選擇簇頭可以延長網絡生命周期，但無法有效均衡網絡的能量消耗。相比于均勻分簇協議，非均勻分簇協議在均衡網絡能耗方面具有更好的性能。非均勻分簇算法通常在網絡中構造遠大近小的分簇結構，使靠近基站的簇頭在簇內通信上消耗的能量小于遠離基站的簇頭，節省的能量可用來轉發遠離基站的簇頭信息，從而解決能耗不均衡的問題［5］。

因此，為了解決寒旱區野外觀測儀器網絡在多跳路由中能量消耗不均勻的問題，本文基于文獻［5］中的非均勻分簇思想，提出一種能量均衡的非均勻分簇路由協議（Energy-balanced Unequal Clustering Routing Protocol，EBUCR）。該協議簇頭通過局部競爭產生，可以得到數量穩定的分簇數目。每一輪選舉開始時，首先選擇候選簇頭，然后基于時序選舉正式簇頭，減少了簇頭選舉過程中的能量消耗。同時，改進了競爭半徑公式和廣播時間公式。改進后的公式綜合考慮了節點能量、距離基站的距離及周圍節點的密度，使簇頭分布更加合理，從而得到合理的分簇結構。在簇間通信時，使用混合粒子群算法進行最優路徑搜索，以減少和均衡網絡能量消耗，使該算法可適用于大規模網絡。仿真實驗結果表明，該算法能夠有效均衡能量消耗，延長網絡生命周期。

1 相關研究

低功耗自適應集簇分層型（Low Energy Adaptive Clustering Hierarchy，LEACH）協議［6］是最早提出的層次型路由協議，節點分為簇頭節點和成員節點，成員節點將信息發送給簇頭，由簇頭進行數據融合再發送給基站，通過節點輪流擔任簇頭來均衡能量消耗。然而，LEACH 協議仍存在許多不足，例如簇頭與基站之間直接傳輸信息會導致遠離基站的節點過早死亡；隨機選舉簇頭的機制會導致簇頭分布不均、各簇成員數目相差較大等情況，也會將能量較低的節點選舉為簇頭，導致節點快速死亡。文獻［7］在LEACH 協議基礎上對閾值公式進行了修改，修改后的閾值公式考慮了節點的剩余能量與到基站的距離，同時結合多跳路由延長網絡生命周期。但在該算法中，靠近基站的簇頭需要轉發遠離基站簇頭的信息，導致消耗過快而率先死亡，造成“熱點”問題。文獻［8］利用粒子群算法（Particle Swarm Optimization，PSO）來優化分簇，通過適應度函數綜合考慮節點的剩余能量和位置，構建合理的分簇結構。同時，建立基于最小生成樹的多跳數據傳輸路徑，縮短節點的通信距離，減少能量消耗并延長網絡生命周期。

上述算法都是基于均勻分簇的思想，無法有效解決能耗不均問題，采用單跳通信時，遠離基站的節點率先死亡，采用多跳通信時，靠近基站的節點由于需要轉發信息而率先死亡。為了解決此問題，Soro 等［5］首次提出非均勻分簇思想，在網絡內構造大小不一的簇，靠近基站的簇規模小，遠離基站的簇規模大，使靠近基站的簇頭在簇內通信上消耗的能量小于遠離基站的簇頭，節省的能量用來轉發遠離基站簇頭的信息，從而解決能耗不均衡問題。但該協議考慮的是一個異構網絡，其中簇頭是預先計算好的，并且能量不受限。文獻［9］提出一個非均勻分簇結合多跳的路由（Energy-Efficient Uneven Clustering，EEUC）協議，每一輪選舉出候選簇頭，然后通過非均勻的競爭半徑競選能量較高的節點成為最終簇頭，形成大小不一的簇。該協議每輪都會產生大量候選簇頭，并且在正式簇頭競爭階段需要廣播和接收大量信息，從而產生額外的能量消耗。文獻［10］提出一種基于位置的非均勻分簇算法（Location-based Unequal Clustering Algorithm，LUCA），該算法類似于EEUC 算法，根據簇頭與基站之間的距離確定簇的大小，遠離基站的簇規模較大，同時對網絡的最佳簇大小進行數學推導與分析，詳細闡述了非均勻分簇的核心思想。文獻［11］提出一種能量均衡的分布式非均勻分簇（Distributed Energybalanced Unequal Clustering Routing Protocol，DEBUC）算法，候選簇頭的廣播時間取決于自身的剩余能量和周圍節點剩余能量大小，根據節點不同的競爭半徑，使得靠近基站的簇規模小，遠離基站的簇規模大。該協議減少了簇頭競爭階段的能量消耗，延長了網絡生命周期。文獻［12］提出一種基于LEACH 協議改進的簇間多跳路由（Cluster Head Multi-hops Routing Algorithm Improved Based on LEACH Algorithm，CMRAOL）協議。根據節點的能量大小和距離基站的距離選舉簇頭，能量越大，距離基站的距離越小，則成為簇頭的概率越大，使靠近基站的簇規模較小，遠離基站的簇規模較大。文獻［13］將網絡進行非均勻分層，在各層依據節點的剩余能量和到層中間線的距離選舉簇頭，同時結合多跳路由減少能量消耗。

為了更好地實現能耗均衡，文獻［14］提出基于分層思想的非均勻分簇協議。不同于其它非均勻分簇協議，該算法將整個網絡分成不同的層，限制兩個簇頭之間的最小距離，使簇頭均勻地分布在同一層中，并且靠近基站的層簇頭間距大，遠離基站的層簇頭間距小，以達到非均勻分簇的效果。當簇頭距離基站較遠時，向基站傳輸數據的能量消耗較大，可通過減少簇內節點的數量均衡能量消耗。然而，該協議采用單跳通信，無法適用于大規模網絡。此外，有些學者將智能優化算法與WSN 的非均勻分簇路由協議設計結合起來。例如文獻［15］基于螢火蟲群優化算法（Glowworm Swarm Optimization，GSO），依據簇頭密度、簇頭距離、簇頭能量、簇的緊湊性來選舉簇頭，形成不均勻的簇。分簇結束后，考慮能量消耗和下一跳節點的剩余能量，在簇間構建轉發樹，將簇頭的信息通過轉發樹傳遞到基站。文獻［16］是一個基于蟻群算法設計的非均勻分簇協議，結合能量因子、距離因子、密度因子改進簇頭選舉過程，并且利用改進的蟻群算法選擇下一跳節點。文獻［17］在簇頭選擇階段使用遺傳算法（Genetic Algorithm，GA）選擇簇頭，選擇剩余能量較高且靠近基站的節點作為簇頭。同時結合多跳路由，降低能耗并延長網絡生命周期。文獻［18］提出一種基于遺傳算法和粒子群算法的路由（GAPSO-based Clustering and Routing，GA-PSO）算法，使用遺傳算法優化聚類以獲得合理的聚類結構，并使用粒子群優化算法優化路由以降低能耗。但是，該算法沒有考慮集群頭部選擇階段節點的殘余能量，從而導致節點的早期死亡。

這些非均勻分簇算法雖然一定程度上延長了網絡生命周期，但協議的簇頭選舉策略仍有很大的改進空間。與已有的非均勻分簇路由協議相比，本文主要做了以下工作：①基于剩余能量、距離和節點密度改進了競爭半徑公式和廣播時間公式，可以得到合理的分簇結構；②建立基于混合粒子群算法的簇間多跳路徑以減少能量消耗；③通過實驗驗證了EBUCR 協議的性能。

2 網絡模型與無線通信消耗模型

2.1 網絡模型

本文考慮觀測網絡是由隨機布置在正方形區域內的節點組成，對網絡進行如下假設：①基站位于網絡外，能量不受限，且儀器組網節點和基站部署完成后，均不可移動；②儀器組網節點是同構的，隨機部署在網絡中，能量受限，每個節點都有自己唯一的ID 編號；③儀器組網節點可根據收到信息的信號強弱判斷到信息發送者之間的距離，并且可以調節自己的發射功率；④儀器組網節點可以對數據進行融合，以減少傳輸的數據量。

2.2 無線通信能量消耗模型

本文使用與LEACH 協議相同的無線通信能耗模型，即一階無線通信模型能量模型，如圖1所示。

Fig.1 Wireless communication energy model圖1 無線通信能量模型

發送者與接收者之間的距離為d時，發射大小為L比特的數據需要消耗的能量如公式（1）所示。式中，Eelec為運行發射電路和接收電路每比特的能量損耗，εfs和εmp取決于本文使用的發射器放大器模型。do為距離閾值，當d≤do時，采用自由空間模型；當d＞do時，采用多路衰減模型。接收一個L比特的消息，無線電需要消耗的能量為ERX（L，d）=L×Eelec。

3 能量均衡的非均勻分簇路由協議

EBUCR 協議采用“輪”的方式運行，每輪分為兩個階段，分別進行簇的建立和數據傳輸。在網絡初始化階段，基站需要以一定的功率向全網路廣播一條信息，然后網絡中每個節點依據接收到信息的信號強弱計算自身到基站的距離。該距離可以用于計算各節點的競爭半徑，并以此達到圖2 所示的非均勻分簇效果。由圖2 可知，距離基站較近的簇規模小于距離基站較遠的簇，簇的規模小，用于簇內通信的能量少，節省的能量可用來轉發遠方簇頭傳遞的信息，達到均衡能耗的效果。每輪開始時，各節點隨機生成一個隨機數，與自身相應的閾值進行比較，若小于閾值，則成為候選簇頭；成為候選簇頭的節點需要廣播自己成為候選簇頭的信息，并生成自身的鄰居簇頭節點信息表，普通節點則進入休眠；然后，候選簇頭依據自身的時間進度廣播成為當選簇頭的信息；簇頭選舉完成后，普通節點結束休眠，加入離自己最近的簇；分簇完成后，簇成員節點給簇頭節點發送信息；簇頭節點接收信息后，將數據進行融合，按照一定的通信路徑發送給基站。

Fig.2 Schematic diagram of unequal clustering routing protocol圖2 非均勻分簇路由協議原理

簇頭的競爭規則定義為：競爭過程中，若候選簇頭Si宣布自己當選簇頭，則其鄰居簇頭節點信息表中的其它所有候選簇頭均不能成為簇頭，并退出競爭。

候選簇頭節點Si的鄰居簇頭節點信息表定義為：neighbori=｛Sj|Sj是候選簇頭，且d（Si，Sj）≤Max（Ri，Rj）｝。

3.1 簇的建立

與EEUC 協議類似，EBUCR 協議簇頭節點依靠局部競爭產生。在EEUC 協議中，候選簇頭的產生是每個節點隨機生成一個隨機數。當該隨機數小于提前設置好的閾值時，則成為候選簇頭。但是該閾值是固定的，每個節點的閾值相等，因此可能將能量較低的節點選為候選簇頭，并且每輪都產生大量簇頭，在競爭過程中會耗費大量能量。

在EBUCR 協議中，利用文獻［19］中的正式簇頭選舉方法來選舉候選簇頭。在每一輪開始階段，首先根據存活節點的剩余能量值計算網絡中節點的平均能量，然后比較每個節點的剩余能量與平均能量大小，當節點剩余能量大于等于平均能量時，節點加入節點集合G。集合G中的節點隨機生成一個0～1 之間的隨機數，如果隨機數小于節點對應的閾值T（n），則該節點成為候選簇頭。T（n）計算公式如公式（3）所示：

式中，p表示候選簇頭節點占全部節點的比值，r表示當前所處的輪數。采用該方式選擇候選簇頭，能夠將網絡中剩余能量較高的節點選為候選簇頭，從而避免能量較低的節點當選候選簇頭。同時避免了產生大量候選簇頭，可以有效減少正式簇頭競爭過程中的能量消耗。

候選簇頭產生后，要在一定范圍內廣播自己成為候選簇頭的消息，周圍的候選簇頭依據收到的消息產生自己的鄰居簇頭節點信息表，然后按照一定的規則競爭產生正式簇頭。如公式（4）所示，原有的競爭半徑公式僅考慮了候選簇頭與基站的距離大小，當網絡運行了一段時間后，網絡中節點的能量產生異構，此時若僅根據距離計算競爭半徑會導致個別節點能量損耗過快。EBUCR 協議考慮節點的剩余能量，對競爭半徑公式作了修改。在候選簇頭距離基站相同距離的情況下，節點剩余能量越大，競爭半徑越大，節點剩余能量越小，競爭半徑越小，更有利于網絡全局的能耗均衡。改進后的競爭半徑如公式（5）所示。

式中，Emax代表當前的最大剩余能量，Emin代表當前的最小剩余能量，dmax表示節點到基站的最大距離，dmin表示節點到基站的最小距離，Rmax表示最大競爭半徑。

EBUCR 協議在簇頭局部競爭階段不同于EEUC 協議的協商機制，而是基于時序選舉簇頭。每個候選簇頭有自己的廣播時間ti，在時間ti未到達之前，如果接收到其它鄰居節點當選為簇頭的消息，則退出競選并廣播退出競選的消息，如果未收到其它鄰居節點當選簇頭的消息，等時間ti到達，則廣播自己成為簇頭的消息。等待時間ti如公式（6）所示：

式中，k為0.9～1 之間的隨機數，以避免等待時間發生沖突，Tch表示簇頭競爭需要的最大等待時間，Eni_avg為鄰居節點的平均剩余能量，Qi表示節點密度（距離當前節點距離Rmax內的節點數量），Qmin為最小節點密度，α、β、γ為能量因子、距離因子和密度因子的加權系數，通過大量實驗，取α=0.5，β=0.2，γ=0.3。根據上述公式，廣播時間不僅取決于節點剩余能量，而且需要考慮節點到基站的距離和節點密度。剩余能量大、距離基站近、節點密度大的節點等待時間就越少。簇頭競選流程如圖3所示。

3.2 數據傳輸

在分簇完成之后，網絡進入數據傳輸階段，分為簇內通信和簇間通信。簇內通信時，采用單跳方式進行通信，成員節點將數據直接發送給簇頭，由簇頭進行數據融合后發送到基站；簇間通信時，采用多跳方式進行通信，基站根據每個簇頭節點的位置計算簇頭的最佳傳輸路徑。

本文的目標是既要減少多跳消耗的能量，又要使各個簇頭消耗的能量均衡，因此引入混合粒子群算法計算簇頭的多跳路徑。適應度函數如公式（7）所示，其中Econsume為簇頭消耗的總能量，D為簇頭消耗能量的方差，適應度值越大，代表粒子對應的路徑越優。

基站計算得到簇頭的最佳路徑后，將路徑發送給簇頭，然后簇頭沿著路徑將信息發送到基站。

Fig.3 Cluster head selection flow圖3 簇頭競選流程

4 協議分析及仿真實驗

本文使用MATLAB 編寫EBUCR 協議仿真程序，將其與LEACH［6］、EEUC［9］、DEBUC［11］、CMRAOL［12］、GAPSO［18］協議進行對比，以驗證EBUCR 協議的性能，仿真實驗相關參數設置如表1所示。

Table 1 Parameter setting of simulation experiment表1 仿真實驗相關參數設置

4.1 簇頭分布分析

在網絡拓撲固定的情況下，一個穩定的分簇協議應該生成數量比較一致的簇頭來優化網絡的能量消耗。在網絡運行過程中隨機抽取100 輪，在沒有任何節點死亡的情況下，統計6 種協議簇頭數目分布情況，結果如圖4 所示。從圖4 可以看出，LEACH、CMRAOL 與GA-PSO 協議的簇頭數目波動較大，這是因為LEACH、CMRAOL 與GA-PSO協議均采用隨機選舉簇頭的方法，無法控制簇頭數量，往往會造成簇頭分布密集的情況，導致耗費大量能量。DEBUC、EEUC 與EBUCR 協議均采用局部競爭的方式選舉簇頭，產生的簇頭數目波動較小?？傮w來說，EBUCR 協議可以產生穩定的分簇數量，有助于網絡穩定，并延長網絡壽命。

Fig.4 Distribution of the number of cluster head produced by six protocols圖4 6種協議生成的簇頭數目分布統計

4.2 網絡能量效率分析

4.2.1 網絡生命周期分析

網絡的生命周期是指網絡開始工作到第一個節點死亡的時間。在網絡生命周期內，整個網絡區域可以得到有效監控，一旦生命周期結束，節點開始死亡。雖然網絡內仍有節點在繼續工作，但對于整個網絡而言，監控存在漏洞，因此無法做到對整個網絡的有效監控。尤其是對于一些對監控信息準確性要求極高的應用，生命周期顯得格外重要。圖5（彩圖掃OSID 碼可見，下同）顯示了EBUCR 協議與CMRAOL、DEBUC、GA-PSO、EEUC 和LEACH 協議的生命周期對比。從圖中可以看出，相比于其它幾種協議而言，EBUCR 協議明顯延長了網絡生命周期。EBUCR 協議第一個節點在544 輪死亡，CMRAOL、DEBUC、GA-PSO、EEUC 與LEACH 協 議 第 一 個 節 點 分 別 在476 輪、452 輪、309 輪、228 輪和95 輪死亡，EBUCR 協議第一個節點死亡的時間比其他4 種協議分別延長了14%、20%、76%、139%和473%；EBUCR 協議最后一個節點在641 輪死亡，CMRAOL、DEBUC、GA-PSO、EEUC 與LEACH 協議最后一個節點分別在560 輪、607 輪、546 輪、447 輪和480 輪死亡，EBUCR 協議最后一個節點死亡的時間比其他4 種協議分別延長了14%、6%、17%、43%和34%，數據對比如表2 所示。這是因為EBUCR 協議的簇頭選擇綜合考慮了剩余能量、距離基站距離和周圍節點密度，再結合能量和距離優化后的非均勻競爭半徑，使得簇頭分布更加合理，可以均衡靠近基站的簇頭與遠離基站簇頭的能量消耗，延長網絡生命周期。

Fig.5 Network lifetime comparison of the six protocols圖5 6種協議網絡生命周期比較

在文獻［20］中，采用網絡的有效性作為評估無線網絡生命周期的指標，而不是僅用存活節點數量衡量網絡生命周期。因為具有相同數量存活節點的網絡節點分布不同，所以在監測覆蓋方面具有不同性能。如圖6 所示，網絡中雖然都只有8 個存活節點，但網絡的監測覆蓋面積有很大差異。

公式（8）給出了網絡有效性的定義，其中TotalArea表示網絡總面積，TotalNodes表示節點總個數，AreaCovered表示存活節點覆蓋面積，SurvivingNodes表示存活節點個數。網絡的生命周期為網絡開始運行到網絡有效性不低于70%的時間，圖7 給出了用有效性表示的網絡生命周期對比圖。結果表明，與LEACH、CMRAOL、DEBUC、EEUC 和GA-PSO 協議相比，EBUCR 協議可以延長網絡生命周期，EBUCR 協議的生命周期相比CMRAOL、DEBUC、GA-PSO、EEUC、LEACH 協議分別延長了13%、11%、18%、47%和160%。

Fig.6 The possible distribution of eight surviving nodes圖6 8個存活節點的可能分布

Fig.7 Effectiveness of six protocols圖7 6種協議的有效性

4.2.2 網絡能量消耗分析

本文通過網絡剩余能量、網絡總耗能和簇頭總耗能3個方面對6 種協議進行能量消耗對比分析。圖8 為6 種協議網絡剩余總能量隨著運行周期變化的對比圖。可以清楚地看出，隨著運行輪數的增加，EBUCR 協議的網絡剩余能量明顯大于其它幾種協議，且斜率基本保持不變，說明EBUCR 協議可以明顯減少能量消耗。圖9、圖10 為6 種協議網絡消耗能量對比圖，在網絡運行過程中，隨機抽取100輪并計算每輪網絡消耗的總能量和簇頭消耗的能量。其中，圖9 為網絡總消耗能量對比圖，圖10 為簇頭消耗能量對比圖。從網絡消耗的總能量來看，EBUCR 協議網絡消耗總能量明顯低于LEACH 和EEUC 協議，與CMRAOL、DEBUC 及GA-PSO 協議相比，EBUCR 協議消耗的總能量相差不大，但波動較小，協議穩定性更強。從簇頭消耗的能量來看，EBUCR 協議簇頭每輪消耗的能量均低于其它幾種協議，說明相比于其它幾種協議，EBUCR 協議能有效減少能量消耗，延長網絡壽命。

4.2.3 網絡吞吐量分析

Fig.8 Residual energy of six protocols圖8 6種協議剩余能量

Fig.9 Energy consumption of total network圖9 網絡總耗能

Fig.10 Total energy consumption of cluster heads圖10 簇頭總耗能

圖11 為6 種協議簇頭接收到數據包數量的對比圖。從圖11 可以看出，6 種協議接收到數據包的數量均隨著時間的增加而增加。算法剛開始運行時，幾種協議簇頭接收到的數據包數量相差不大。隨著算法的運行，其余幾種協議的節點開始死亡，其接收到的數據包數量小于EBUCR協議。并且在其他協議簇頭停止接收數據時，EBUCR 協議簇頭仍能從成員節點接收到監測數據，表明該協議能夠延長網絡對監控區域的監控時間。

4.3 能量均衡分析

Fig.11 Throughput energy of six protocols圖11 6種協議吞吐量

能量均衡分析也是評價路由協議性能的一項重要指標。圖12 使用剩余能量方差對6 種協議進行能量均衡方面的對比分析。圖中曲線為隨著運行時間增加，網絡中所有節點剩余能量方差的變化趨勢。相比于其他幾種協議，EBUCR 協議的方差數值基本保持最小，且波動較小，說明EBUCR 協議能夠有效均衡能量消耗，能量均衡性最好。

Fig.12 Variance of residual energy of nodes圖12 節點剩余能量方差

5 結語

針對大規模的野外觀測儀器組網網絡，為了均衡網絡能量消耗、延長網絡生命周期，本文提出一種能量均衡的非均勻分簇路由協議。該路由協議在簇頭競爭階段基于時序來競爭簇頭，并綜合考慮節點的剩余能量、到基站的距離、周圍節點密度實現非均勻分簇。同時，將混合粒子群算法應用到多跳路徑搜索中，選擇最優路徑完成簇頭間的信息傳輸。實驗結果表明，EBUCR 協議相比LEACH、DEBUC、CMRAOL 和EEUC 協議能節省更多能量，具有更強的穩定性，可以延長網絡生命周期，并有效均衡能量消耗。然而，本文致力于設計能量高效且均衡的分簇路由協議，并未對整個協議運行時間的收斂性方面進行深入研究，而這在實際應用中是必須解決的問題，希望在未來作進一步研究。