樹型鏈式非均勻分簇混合多跳路由算法*

胡中棟， 張 康， 王振東

(江西理工大學 信息工程學院，江西 贛州 341000)

0 引 言

無線傳感器網絡(wireless sensor networks,WSNs)是一種集傳感器技術、信息處理技術、通信技術等于一體的新型網絡，現已廣泛應用于環境監測[1]、智能家居、國防軍事[2]等多個領域[3]。由于節點初始能量有限[4]，且后期無法補充，因此，充分利用節點有限能量、延長網絡整體壽命成為WSNs的重點研究方向。

層次路由協議中的分簇思想能有效聚合數據，提高網絡連通率[5]，實現負載均衡。文獻[6,7]中簇頭隨機選取未考慮位置分布，簇內節點與簇頭、簇頭與簇頭間均以單跳方式通信，易產生遠距離傳輸；文獻[8]中算法獲取所有節點相關信息會消耗大量能量、占用大量的帶寬；文獻[9]中靜態劃分成鏈區域，有可能使用原本相鄰的節點因劃分區域不同而成鏈不同，造成能耗浪費；文獻[10]中算法如果距離Sink較遠的簇密度較大，就會導致其簇頭負載不均，其在大面積網絡中的表現也較一般。

本文通過引入候選簇頭之間的角度控制優化簇頭選取，構建樹型鏈式非均勻簇結構優化成簇策略，利用混合層次網絡拓撲結構，結合改進后的蟻群算法提出一種樹型鏈式非均勻分簇混合多跳路由算法(a tree-chain uneven cluster hybrid multi-hop routing algorithm,TUCHM)。

1 相關研究

1.1 能耗模型

本文文獻[8]中的無線通信能耗模型[11]，假設每個數據包有kbit的數據，則發送端消耗的能量為

(1)

(2)

接收端消耗的能量為

ERX=KEelec

(3)

數據匯聚融合消耗的能量為

EDA=kEda

(4)

式中Eelec=50 nJ/bit，為收發電路能耗；Eda=5 nJ/bit，為單位數據融合能耗；Efs=10 pJ/bit/m2，Eamp=0.001 3 pJ/bit/m4，d0為能量損耗的界限值。

1.2 蟻群算法

基本蟻群算法[13]路徑選擇概率模型未能考慮節點的剩余能量和位置等因素，會導致位于路徑上的節點因頻繁傳遞數據而過快死亡信息素更新緩慢，且不斷揮發，所以,基本蟻群算法路徑搜索時間長，易出現“停滯”現象。Dorigo M提出的Ant-Cycle模型利用全局信息更新路徑上信息素，運算量大，時間復雜度高，尋找最優路徑的收斂速度較慢。Stutzle T等人提出了最大最小[14]蟻群系統，其每一次循環只對本次循環最優解或到目前為止找出最優解的路徑進行信息素更新，導致較長時間內多條路徑上信息素濃度相同。

2 TUCHM算法

2.1 簇頭選取

為了均衡網絡能耗，TUCHM算法在簇頭選擇時綜合考慮了當前節點的剩余能量和簇頭之間的位置關系，提出了新的閾值函數計算公式

(5)

(6)

式中p為存活節點中簇頭占比；r為當前循環輪數；G為最近1/p輪中未被選為簇頭的節點集合[15]；Ei為當前節點i的剩余能量；Eavg為所有節點的平均剩余能量；χ1，χ2為式(6)兩項的權重值且χ1+χ2=1。

如圖1，以Sink節點為原點建立二維直角坐標系，各簇頭與Sink節點連線，當其中的BS和CS為候選簇頭a與Sink節點連線aS的左右鄰線時，射線l為的角平分線，θ為aS和l的夾角；當網絡中還沒有選取出簇頭時，θ=0°；當a′S只有一側存在簇頭與Sink的連線，另一側為坐標軸時，射線l′為坐標軸X或Y與AS形成的較小夾角的角平分線，θ′為a′S和l′的夾角。

圖1 θ角示意

2.2 構建簇結構

設全網共N個節點，構建簇結構的步驟如下：

Di=φi

(7)

式中φ為長距離系數。根據文獻[15]可知，φ初始值一般取1.5，但當遇到以下兩種情況時，長距離系數的取值應該適當增大：WSNs稀疏、節點密度低時，長距離較多，此時應增大長距離系數以適應TUCHM算法;在WSNs運行的中后期，由于出現了大量節點死亡，導致網絡節點間距增大，此時應適當增大長距離系數以加快TUCHM算法收斂速度。

2)以簇頭CHi為簇中心，半徑在Di內的鄰居節點以單跳形式加入簇，若同一鄰居節點在多個簇頭的成簇范圍內，則選擇距離最近的簇頭加入。

δ用來控制建簇階段的收斂速度，如圖2，節點d,e和f各自尋找到距離自身最近的已成簇節點b和c，但節點e和f并不位于以b或c為中心、D4為半徑的范圍內，則節點d首先加入簇4；然后節點e，f再次尋找到距離自身最近的已成簇節點d，但只有節點f位于以d為中心、D4為半徑的范圍內，所以節點f加入簇4；經過多次循環，節點e連續δ次尋找到距離自身最近的已成簇節點d，卻仍然沒有加入簇4，此時令節點e直接以單跳方式與節點d建立連接加入簇4。δ定義為

(8)

式中Nalive為當前存活節點數，成簇完成后，確定一個T時隙，以降低數據冗余和傳輸沖突，簇內節點根據T時隙將數據傳輸到簇頭節點。如圖2所示，簇內產生樹型鏈式結構，距離簇頭較遠的節點通過鏈中其它節點中轉，降低了數據傳遞路徑長度。

圖2 混合層次網絡多跳路由

2.3 路徑選擇概率模型

如圖2，TUCHM算法采用平面網絡結構與層次網絡結構相結合的混合層次網絡拓撲結構，普通節點間可以直接進行通信，不需要通過簇頭節點轉發數據，因此，穩定性更好，魯棒性更高[16]；結合改進后的蟻群算法，將簇頭的數據通過其它簇頭或普通節點多跳傳遞至Sink節點。算法首先修改路徑選擇概率模型，當螞蟻k位于節點i時，計算到下一跳節點j的概率

(9)

式中τ為信息素濃度；η，ψ為啟發式因子

(10)

(11)

式中α和β分別為信息素和期望啟發式因子的相對重要程度；Jk(t)為螞蟻還未經過的節點集合。

可以看出，啟發式因子η主要考慮當前節點i的剩余能量Ei、向下一跳節點j發送數據需要的能量Ecost(i,j)、節點間距離dij與傳感器節點通信半徑R的比值等參數；啟發式因子ψ主要考慮下一跳節點j的剩余能量Ej與節點初始能量Einit的比值、dij與節點j到Sink的距離diS之和以γ角等參數。γ表示當前節點到Sink的連線與當前節點到下一節點的連線的夾角，夾角越小，下一節點越有可能在當前節點到Sink的傳輸路徑上，啟發式因子ψ通過γ角引導螞蟻方向以降低經過的節點數量。通過設置合理的權重值ξ1,ξ2,ξ3和ξ4可有效降低傳輸路徑長度和節點能耗。

2.4 信息素更新

TUCHM算法在路徑信息素更新前，螞蟻先按照信息傳遞路徑長度進行排名，排名靠前的螞蟻在每次循環中額外釋放更多的信息素，給予已知最優路徑最強的正反饋，加快路徑尋找速度，根據式(12)、式(13)更新路徑ij的信息素濃度值

τij(t+n)=(1-ρ)·τij(t)+Δτij

(12)

(13)

(14)

3 算法仿真與分析

3.1 仿真參數設置

為了驗證TUCHM算法的性能，應用MATLAB軟件與LEACH和DEEC算法進行仿真實驗。假設100個同構無線傳感器節點在仿真區域內隨機分布且不能移動，當節點剩余能量低于1 %后,則認為該節點死亡，每個節點的初始能量為0.5 J，廣播包大小為25 bit，數據包大小為4 000 bit，Sink節點坐標位于(0,0)m處。

3.2 仿真結果分析

圖3(a)～(d)給出了在不同大小的正方形仿真區域下存活節點數的對比，其邊長分別為100,200,300,400 m。隨著仿真區域的不斷變大，LEACH算法越來越早出現斷崖式的節點死亡，這是因為其簇內節點到簇頭、簇頭到Sink節點皆以單跳形式傳遞數據，DEEC算法由于在簇頭層采用路由樹多跳傳輸數據而比LEACH算法節約能量，但隨著仿真面積的加大，簇頭間的距離越來越遠。由圖3(c)、(d)可知在大面積仿真環境下，網絡后期LEACH算法存在許多節點未完全死亡，只有個別節點在收集數據，但此時網絡已經失效。

圖3 不同仿真區域下存活節點曲線對比

可以看出TUCHM算法可以在更長的時間內保證所有的節點都存活，這是由于非簇頭層的節點參與中轉數據。

從WSNs開始運行到第一個節點死亡時所經歷的輪數稱為網絡的穩定周期。如圖4(a)所示，TUCHM算法的穩定周期在邊長100,200,300,400 m的正方形仿真區域下比LEACH算法分別提升大約32 %,63 %,193 %,286 %，比DEEC算法分別提升大約14 %,17 %,27 %,39 %。設網絡開始運行到50 %的節點死亡所經歷的輪數稱為網絡的生命周期。如圖4(b)所示，TUCHM算法的生命周期在邊長100～400 m的正方形仿真區域下比LEACH算法分別提升大約66 %，67 %，86 %，197 %，比DEEC算法分別提升大約14 %，15 %，46 %，123 %。這是因為TUCHM算法簇內遠距離節點借助鏈內節點中轉傳遞數據，簇頭到Sink節點借助普通節點多跳傳遞數據，有效避免了部分節點因遠距離單跳傳遞能耗過高而失效過快。

圖4 不同仿真區域下網絡的穩定周期和生命周期

圖5為網絡在200 m×200 m的仿真區域下消耗總能量以及網絡節點剩余能量方差隨輪數變化的對比圖。

圖5 網絡消耗總能量與節點剩余能量方差曲線

由圖5(a)可知，LEACH和DEEC算法的曲線斜率均比TUCHM算法高，說明LEACH和DEEC算法每輪傳輸數據消耗能量要比TUCHM高，TUCHM算法借助改進的蟻群算法多跳傳遞數據，優化各簇頭到Sink節點之間的路徑因此更加節約能量。由圖5(b)看出：LEACH算法剩余能量方差變化幅度較大，DEEC算法剩余能量方差比較穩定但整體比TUCHM高，TUCHM算法剩余能量方差一直較低且穩定，表明TUCHM算法能夠更好地均衡網絡能量，這是因為簇頭選取同時考慮了節點剩余能量和節點之間的位置關系，避免了螞蟻路徑重疊過多。

4 結束語

TUCHM算法在以下三點進行改進：1)在選取簇頭時，綜合考慮了候選節點的剩余能量及其位置對傳輸階段網絡能耗均衡的影響，使剩余能量大和螞蟻路徑重合率低的節點更容易當選為簇頭；2)優化了成簇策略，由原來的簇內單跳、均勻分簇變為樹型鏈式多跳、非均勻分簇，合理定義了成簇區域半徑，減少了遠距離單跳傳遞的能量浪費；3)采用混合層次網絡拓撲結構，打通網絡下層節點之間的聯系，改進路徑選擇概率模型和信息素更新模型，更好發揮蟻群算法優化路徑的優勢，消除了簇頭直接與Sink節點單跳傳遞的缺點。仿真結果表明：TUCHM算法在節點存活數量、網絡的穩定周期和生命周期、均衡網絡能量消耗等方面有明顯的提升。