能耗均衡的多跳多路徑認知分層路由算法*

王俊喜,陳桂芬

(長春理工大學電子信息工程學院，吉林 長春 130022)

1 引言

認知無線傳感器網絡是近幾年的研究熱點，它的前身，無線傳感器網絡[1 - 3]是由大量微型傳感器節點構成的，傳感器節點通常由電池供電，密集地部署在所需區域監測環境參數或感測特定數據。傳感器節點將它們感測到的數據以多跳或單跳的方式傳輸給一個或多個數據接收器。

無線傳感器網絡通常是基于多種不同應用環境的網絡，由于傳感器節點配備的是低成本的電池，節點的存儲器有限，處理能力低。而在大多數應用中，更換電池或者為電池充電是不切實際的，所以很多節點會耗盡其自身能量導致部分網絡失去連接。因此，在設計高效率、長壽命的無線傳感器網絡時，擁有適配的高效節能路由算法是至關重要的[4 - 6]。

近年來，相關算法被陸續提出，文獻[7]提出了集中式節能距離CEED(Centralized Energy Efficient Distance)路由算法，旨在改善簇首CH(Cluster Head)的選擇和簇的形成。在CEED中，簇首CH的選擇基于剩余能量和每個節點到接收器的距離。在網絡分簇結構形成中，每個節點都基于剩余能量和距離參數選擇其CH，然后和CH構造一條鏈，用于將數據包以多跳方式傳輸到接收器。

文獻[8]提出了一種新的簇首選擇方案，所有節點根據其自身剩余能量競選成為簇首，形成簇結構之后，剩余能量更高、距離匯聚節點(Sink)更近的簇首將成為其他簇首的數據收集節點，數據收集節點再將數據轉發至匯聚節點。

文獻[9]提出了一種能量感知的多跳多路徑路由EAMMH(Energy Aware Multi-hop Multi-path Hierarchical)算法，該算法通過引入能量感知和簇內多跳功能來降低網絡總能耗。

文獻[10]提出了一種結合節點能耗因子改進協議SEP(Stable Election Protocol)的EC-SEP(Energy Consumption-SEP)算法，該算法根據節點剩余能量不斷更新簇首選舉概率，以此來均衡網絡的能量消耗，延長生命周期。

隨著無線傳感器網絡的廣泛應用，其與ZigBee、WiFi和藍牙等共享頻段的方式導致頻譜資源的日益緊缺[11]。以上算法將不再契合未來發展需要，近幾年來，人們將能夠緩解頻譜資源緊缺問題的認知無線電與無線傳感器網絡進行結合，提出了認知無線傳感器網絡CRSN(Cognitive Radio Sensor Network)這個熱點話題，適用于認知無線傳感器網絡的路由算法成為目前研究方向[11]。

文獻[12]提出了一種適用于CRSN的低能耗自適應非均勻分簇LEAUCH(Low Energy Adaptive Uneven Clustering Hierarchy)算法，其核心是應用認知無線傳感器節點進行數據傳輸，并利用非均勻的簇首競爭半徑均衡簇首能量消耗。

文獻[13]提出了一種改進的能量有效閾值敏感傳感器網絡路由協議A-TEEN(Advanced Threshold Sensitive Energy Efficient Sensor Network Protocol)算法，將路由協議TEEN(Threshold Sensitive Energy Efficient Sensor Network Protocol)應用于CRSN，并根據節點空閑信道數改進了簇首選舉概率公式。

上述算法能夠應用于CRSN，并能結合認知能力緩解頻譜資源緊缺的現狀，但是其網絡能量消耗不夠均衡，認知傳感器節點對接收器靈敏度需求較高，網絡中節點均為認知傳感器節點的鋪設難度較大。無線傳感器網絡節點數目大、分布稠密、維護難度高，節點存儲空間小、能量受限，節點開始工作后，除具備可移動裝置的節點外普遍處于靜止狀態。基于網絡特點研究設計路由算法并不斷推陳出新具有重要意義。

能量受限問題是無線傳感器網絡實際應用的主要瓶頸，能夠提高網絡能量的使用效率并延長網絡壽命是路由算法的基本設計目標[14]，針對該目標并結合緩解頻譜資源日益緊缺的問題，本文提出了一種應用于異構CRSN的能耗均衡多跳多路徑路由EMMCH(Energy-balanced Multi-hop Multi-path Cognitive Hierarchical)算法。

EMMCH算法為上述問題提供了解決方案，首先EMMCH算法適用于當下研究熱點CRSN，能夠緩解頻譜資源日益緊缺的現狀；其次，算法采用了異構網絡設置，普通節點與認知傳感器節點協作通信，降低了鋪設難度與鋪設成本；最后，算法著重考慮并提高了網絡能耗均衡性，延長了網絡生命周期。

對比仿真結果發現，與EAMMH算法[9]、LEAUCH算法[12]、EC-SEP[10]算法、結合認知能力改進SEP算法的CSEP(Cognitive-SEP)算法等相比，EMMCH算法具有更長的生命周期、更高的穩定性、更多的數據傳輸量和更均衡的網絡能耗。

2 網絡模型的建立

2.1 能量消耗模型

文獻[15]提供了一種經典的無線傳輸能量消耗模型，根據傳輸距離d，該傳輸消耗模型分為2種，其一為自由空間模型，其二為多徑傳輸模型。能量計算公式如式(1)所示：

(1)

其中，k為節點發送字節數，d為數據傳輸距離，εfs為自由空間模型放大倍數，εmp為多徑傳輸模型放大倍數。Eelec為發送或者接收單位比特數據的能耗。其中：

(2)

節點接收數據消耗為：

ERx(k)=ERx-elec(k)=kEelec

(3)

其中,k為接收的數據比特數。

2.2 網絡模型

以隨機的方式在規定區域內部署若干個節點，節點包括普通傳感器節點和認知傳感器節點，認知傳感器節點能夠感知節點空閑信道情況并動態連接。普通傳感器節點能夠獨立感知信息[16]。暫不考慮傳輸誤差，設定節點能量耗盡為節點死亡。為了避免其他因素的影響，對網絡中節點性質進行以下設定：

(1)節點編號唯一且不發生改變，節點在監測區域內隨機部署，部署后不再移動；

(2)匯聚節點能量無限、位置不變；

(3)節點可以根據接收信號強度感知距離、定位其自身位置；

(4)認知傳感器節點均具有與匯聚節點直接通信的能力(即認知傳感器節點均可成為簇首，能耗隨距離的增大而增加)；

(5)節點可以根據通信距離調節通信功率。

3 EMMCH算法

本文提出的EMMCH算法是一種異構認知無線傳感器網絡能量感知多跳多路徑認知分簇路由算法，認知傳感器節點通過感知到的頻譜空閑信息，機會地接入空閑信道，將無線傳感器網絡的監測數據傳輸至匯聚節點。算法通過多跳傳輸降低傳輸消耗。節點通過判別剩余能量、節點距離、節點密度及其頻譜能量等級判別是否成為候選簇首。擔任候選簇首的節點結合競爭半徑和頻譜能量等級判斷其頻譜能量等級在競爭半徑范圍內為最高后，宣布擔任簇首。其競爭半徑內的其余候選簇首退出競選。距離匯聚節點越遠的簇首擁有越大的競爭半徑，匯聚節點附近處可形成比較遠處更多的簇，避免依據節點位置選擇簇首帶來的 “熱區”問題。

首先，在一定大小的檢測區域內隨機鋪設共N個節點，由匯聚節點在監測區域內廣播信號，各個節點根據接收到的信號強度，得到與匯聚節點的大致距離di,1≤i≤N，隨后將距離di和自身的剩余能量返回給匯聚節點。由于在實際應用環境中，節點位置一般不變，這里不討論移動節點，則可得節點距離因子α：

(4)

其中，dmax為節點到匯聚節點的距離最大值，dmin為節點到匯聚節點的距離最小值。

為確保簇首的利用率設置節點密度因子ρ，使鄰居節點較密集的節點較易成為簇首，若鄰居節點密度很小，則該節點不適合成為簇首，以避免相對邊緣的節點成為簇首，造成能量浪費。首先，將與某節點距離小于R的節點定義為該節點的鄰居節點。距離R的定義式如式(5)所示：

(5)

其中，S為檢測區域的面積，Popt為最佳簇首比率(模擬取值0.1)[12]。那么，節點密度因子定義式如式(6)所示：

(6)

其中，Nlj為鄰居節點數。

本文結合節點競爭半徑Rc，采用非均勻分簇的思想，降低靠近匯聚節點的簇的規模，以避免“熱區”問題。競爭半徑Rc計算公式如式(7)所示：

(7)

其中，d(i,Sink)為節點i到Sink的距離，c為取值控制參數。確定了成為簇首的競爭條件，即相鄰簇首互不在對方的競爭半徑內。

所有認知傳感器節點按隨機次序進行判決，判決思想繼承了EAMMH算法輪的概念。簇首數根據文獻[17]提供的動態選舉思想進行確定。簇首選舉概率公式結合了節點剩余能量、節點密度因子ρ和節點距離因子α，選舉較優候選簇首。簇首選舉概率計算公式如式(8)所示：

(1-β)[τρ+(1-τ)α]

(8)

其中，β為能耗因素占比權重系數，τ為節點密度因素占比系數，β與τ可以根據實際需求更改，本文算法均取值0.5。根據式(8)，剩余能量多、鄰居節點密度大、距離匯聚節點近的節點有更高的候選簇首當選概率。E(i)為節點剩余能量，Ei(0)為該節點的初始能量，Etotal為節點能量和，Ea為當前輪次節點理論剩余能量平均值，Etotal和Ea的計算方法分別如式(9)和式(10)所示：

(9)

Ea=Etotal(1-r/rmax)/N

(10)

其中，r為網絡當前測試輪次，rmax為最大測試輪次。在選舉候選簇首時，節點生成一個0～1的隨機數，若該隨機數小于該節點閾值，則該節點擔任候選簇首。EMMCH算法中的節點閾值計算公式如式(11)所示：

(11)

k=P(t)×N

(12)

其中，G(t)為當前普通傳感器節點集合，即，擔任過簇首的節點不重復成為簇首。

將全部通過判決的節點定義為候選簇首。隨后，認知傳感器節點獨立監測無線傳輸環境并通過頻譜感知方法中的能量檢測算法找到頻譜空穴信息。設可用信道數為C，Vi(t)為t時刻節點i的信道可用性向量：

i≤c≤C

(13)

對特定信道中的主用戶活動的預測會為該信道提供更準確的判決信息，因此節點i在t時刻的預期信道可用性定義如式(14)所示：

(14)

(15)

其中，Ni是節點i的鄰居節點集合，ei是其剩余能量，γij(t)是在時刻t節點i的鄰居節點j的相對頻譜可用性，其計算公式如式(16)所示：

(16)

其中，min是最小值運算符，*表示內積。據此，頻譜能量等級最高的候選簇首擔任簇首。

每個非簇首節點根據其到各個簇首(CHs)的距離入簇。在確定CH并形成簇之后，啟動路徑建立過程。每個CH在公共控制信道上廣播CH路由請求(CH-RREQ)消息。當成員節點si從其CH接收到CH-RREQ消息時，若該消息是重復的，則丟棄該消息;否則，若滿足以下條件，則廣播該消息：

(1)成員節點si到接收器的距離比發送節點ss到接收器的距離短，即d(si，Sink)

(2)剩余能量高于平均水平，即E(si)>Eth,保護低能量的節點不參與路由過程。

(3)發送節點ss和接收節點si之間至少有一個公共空閑頻率信道。

如果滿足上述所有條件，則si將CH-RREQ轉發給其鄰居節點;否則，丟棄該消息。 以這種方式，其他簇結構的成員在公共控制信道上接收CH-RREQ，并且如果滿足以上條件則將其轉發到其CH。重復此過程，直到接收器收到消息。接收器收到消息后，將路由應答(RREP)消息返回原CH，此消息包含組成路徑的節點的ID號以及這些節點之間的距離。

隨后，CH在所有接收到的可用路徑中選擇最佳路徑。選擇依據為路徑的通信成本D：

D=Cost×Unbalance

(17)

其中，Cost表示傳輸成本，由于能量消耗取決于發射器和接收器之間的距離，因此傳輸成本可以定義為：

(18)

其中,Wj是節點sj-1和sj之間距離的平方，L是由集合{s0，s1，…，sL}表示的路徑中的節點總數，sL表示接收器。Unbalance表示路徑的不均衡程度，代表路徑上的節點之間能量消耗的變化，其定義如式(19)所示：

(19)

CH選擇D最小的路徑為傳輸數據包的路徑，使整體能量消耗更小、更均衡。

定義φ為節點死亡收斂速率，在保證網絡生命周期的前提下，在某一段時間內，節點的死亡速率越高，網絡的穩定性越好。節點死亡收斂速率如式(20)所示：

(20)

其中，ω和θ表示在網絡運行時間tω和tθ內死亡的節點比率。在θ不變的情況下，越長的tθ代表越長的網絡生命周期。若ω和θ不變，tω和tθ之間的差值越小，網絡能量消耗越均衡。

各節點間的剩余能量差別的大小可直接反映網絡能耗的均衡程度。定義節點剩余能量標準差σ如式(21)所示。σ越小，說明各節點之間剩余能量差別越小，即網絡能耗越均衡。

(21)

4 仿真結果分析

本節將EMMCH算法與EAMMH算法、LEAUCH算法、結合能量改進SEP算法的EC-SEP算法和適用于CRSN的改進算法CSEP進行仿真實驗并對比討論。仿真對比了網絡的生命周期、節點平均剩余能量、節點死亡收斂速率、傳輸數據量及網絡監測范圍大小的影響等方面。

設置仿真模擬節點數為100，節點隨機部署在監測區域內。其他仿真參數設置如表1所示。

Table 1 Simulation parameter settings

首先，設置各算法節點總數、總能量相同，討論監測區域范圍大小對EMMCH算法及其他算法的網絡生命周期影響程度，仿真結果如圖1所示。

Figure 1 Comparison of the influence of the monitoring area

從圖1中可見，EMMCH算法在監測區域邊長為80 ～140 m時，始終有較長的網絡生命周期且受檢測區域面積變化影響不大。檢測區域邊長的增加意味著數據傳輸距離的增加，代表著更高的傳輸消耗。在監測區域為60 m×60 m時，EMMCH算法網絡生命周期要短于LEAUCH算法；在監測區域為200 m×200 m時，EMMCH算法網絡生命周期與CSEP算法的接近；在監測區域邊長為80～140 m時，EMMCH算法的網絡生命周期約為CSEP算法的1.22倍，約為EC-SEP算法的1.54倍，約為LEAUCH算法的2.86倍。

設置相對均衡的網絡監測區域為100 m×100 m，網絡生命周期仿真對比如圖2所示。

Figure 2 Comparison of network life cycle

如圖2所示，在不考慮延遲和可靠性的情況下，保持各算法參數一致，EMMCH算法具有更長的網絡生命周期，節點能量耗盡輪次最為接近，說明網絡消耗均衡性更高。可見，EMMCH算法具有更高的網絡實用性和穩定性。

Figure 3 Comparison of average remaining energy of nodes

節點平均剩余能量仿真結果如圖3所示。從圖3可見，各算法中節點初始總能量一致，EMMCH算法的節點平均剩余能量最高，說明能耗最低。為討論算法的穩定性，本文仿真對比了節點死亡收斂速率及節點剩余能量標準差，結果分別如圖4～圖6所示。

Figure 4 50% node death convergence rate

Figure 5 80% node death convergence rate

Figure 6 Comparison of node residual energy standard deviation

節點死亡收斂速率代表了各節點能量消耗的均衡性。如圖4和圖5所示，EMMCH算法具有最高的節點死亡收斂速率，說明有節點能量耗盡時開始，EMMCH算法節點死亡速率最大，即各節點能耗更均衡。圖6為網絡中普通傳感器節點的剩余能量標準差對比圖。節點剩余能量標準差表示各節點剩余能量的差異，差異越小，消耗越均衡，網絡越穩定。由圖6可知，EMMCH算法的節點剩余能量標準差最小，說明EMMCH算法具有最高的網絡穩定性。

網絡中數據傳輸量對比如圖7所示。從圖7可知，EMMCH算法具有更長的網絡生命周期、更強的網絡實用性和更高的數據傳輸量。

Figure 7 Comparison of data transmission volume

5 結束語

本文基于EAMMH算法提出了一種適用于認知無線傳感器網絡的分層路由算法——EMMCH算法。該算法根據節點剩余能量、節點的位置因子和鄰居節點密度因子改進了簇首選舉概率，降低了能量低、位置差、鄰居節點少的節點成為簇首的可能性。根據節點的信道可用性向量、預期信道可用性向量和節點剩余能量設計的頻譜能量等級選舉最優簇首，使簇首選舉更為合理。結合節點競爭半徑的概念，平衡了“熱區域”簇首能量消耗。簇首數依據動態變化的思想，減少了資源浪費。數據傳輸階段，簇首節點選取節點剩余能量在平均值之上、距離匯聚節點更近且存在空閑信道的節點進行多跳傳輸路徑規劃，再結合由路徑消耗和不均衡程度定義的通信成本選取最優路徑進行數據傳輸，使網絡中能量消耗更為均衡。

仿真結果表明，EMMCH算法可延長網絡生命周期，提高系統穩定性，增加數據傳輸量，均衡網絡能耗。