基于能耗均衡的改進分簇路由算法研究

張 豪

(哈爾濱工程大學 信息與通信工程學院，哈爾濱 150001)

在無線傳感器分簇網絡中，分簇路由算法通過對無線傳感器網絡的劃分，形成多個簇結構，不同于平面路由算法中的各個節點間功能相同、地位平等，簇結構中的節點被區分為簇頭節點和簇內普通成員節點，簇頭節點又形成更高層級的網絡再進行新的簇結構的構建[1].分簇路由算法的這種構成方法使其具有較好的擴展性和能耗均衡性，面對網絡變化也能更快響應[2].隨著網絡的運行，無線傳感器能量狀態的改變會使得無線傳感器網絡在能耗均衡和網絡內分簇均勻方面出現不均，該現象會對無線傳感器網絡的生存造成影響，那么，如何在簇頭選舉過程中使得簇頭在能量和位置方面更具優勢，進而選舉出合適的簇頭就成為一個重要的問題.

為了選舉出合適的無線傳感器擔任簇頭，越來越多的分簇路由算法在不斷的被提出，其中LEACH路由算法作為WSN中首個被提出的分簇路由算法，很多分簇路由算法都以此作為改進的基礎.在LEACH路由算法中首次提出了分簇的概念，通過分簇的建立和數據的穩定傳輸兩個階段[3]，建立了網絡中的層次從屬關系.在對LEACH改進的基礎上提出的PEGASIS路由算法中，網絡中的各個節點的通信行為只發生在與距離其最近的鄰居節點之間，并通過這種方式形成通信鏈條，構造出唯一的簇[4]，但鏈內距離較遠的節點間的信息傳輸的時效性差，使得PEGASIS算法不適用于大規模的網絡.DEEC算法也是以LEACH算法為基礎改進得到的能量異構分簇路由算法，DEEC適用于網絡中各個節點在能量方面存在差異的能量異構WSN，根據節點初始能量的不同差異的設置節點被選為簇頭的概率，同時根據運行過程中網絡能量剩余情況與節點初始能量關系對閾值函數進行改進，以使得被選為簇頭的節點在能量方面具有更好的表現[5].SEP路由算法也是根據異構WSN中節點初始能量不同的特點，根據能量情況將節點區分為高級節點和普通節點，并對其當選簇頭的概率進行差異化設計，使簇頭在能量方面更具優勢[6].但在DEEC算法和SEP算法中，隨著無線傳感器節點能量狀態的改變，會導致初始的概率設置所帶來的優化效果會變得越來越不明顯，甚至導致初始能量占優的節點因負擔過大提前失效[7].后來提出的GAF算法，根據無線傳感器節點和監測區域的地理位置進行虛擬單元格的劃分，之后節點在劃分好的虛擬單元格內進行分簇選舉[8].但GAF路由算法的簇頭選舉具有隨機性，可能會因簇頭所處位置不佳帶來通信代價的增大，以及因簇頭能量較低，導致節點過早死亡影響網絡的生存周期[9].

為了使無線傳感器網絡在能耗均衡方面具有更好的表現，達到延長網絡的穩定期和生存周期的目的，要從解決分簇不均和簇頭位置的隨機性兩方面進行考慮[10].本文提出動態分區的方法進行網絡分簇，使WSN在運行過程中通過區域劃分在分簇時具有動態性，各節點參與簇頭選舉的優先級在網絡運行過程中隨著所歸屬區域不同而產生動態變化，使網絡內節點能耗更為均衡；
通過論證得到的簇頭位置與簇內通信能耗關系，綜合考慮節點所處位置與當前剩余能量，對簇頭選舉階段進行改進，使選舉出的簇頭能夠使簇內通信能耗情況得到優化，延長無線傳感器網絡的穩定期和生存周期.

在對無線傳感器能量消耗的研究中，通常采用一階無線電模型，本文在對通信消耗進行計算時也選擇對應的能量式[11].一階無線電通信模型主要由無線傳感器節點的數據發送裝置、數據接收裝置組成，信息傳輸及能量消耗主要發生在數據發送、數據接收、數據融合以及數據傳輸向基站傳輸這幾個階段[12].

1.1 能量消耗模型

設節點間距離即數據傳送距離為d，當d小于傳輸距離閾值d0時，使用自由空間模型對數據傳送能耗進行計算，當d大于距離閾值d0時，則在計算數據傳送能耗時選擇多路徑衰落模型[13].

當傳輸距離為d，節點發送和接收kbit數據時，根據式(1)對通信所消耗的能量進行計算：

ET(k,d)=ETE+ETA=

(1)

其中：Eelec表示各個節點在發送或接收每比特數據時的能耗，ETE表示發送電路發送kbit數據所消耗能量，ETA表示在距離為d時，放大器發送kbit數據所需能耗，εfs和εmp為能量消耗系數，取決于發射機放大器模型，d0為判斷采用何種信道模型進行傳輸的距離閾值[14].

由上述能量消耗式可以看出，在WSN中，能量消耗主要發生在數據的無線傳輸過程中[15].進行數據發送時，所消耗的能量ETE與傳輸距離d呈正相關關系，收發端距離d越大對應的能量消耗也越高.

1.2 簇內位置與簇內通信能耗關系

為方便進行計算說明，在此處定義以圓形區域作為虛擬單元格，且傳感器節點在該區域內以密度ρ進行均勻分布，且每個節點需要發送的數據包數量也是相同的.同時，使用一階無線電能量模型來計算節點的行為消耗，即發送和接收的消耗通過式(2)進行計算：

ES(k,d)=kEelec+kd2εfs

(2)

其中：εfs為信號放大器的放大系數(由節點間通信距離所決定)，Eelec為節點發送或接收每比特數據時的能耗，d為傳輸距離，k為發送的數據包大小.

在以上假設下，可以根據上述條件計算得出該網格區域中節點的能耗期望值.如圖1所示，C為網格中位置距離中心較遠的簇頭位置，M點為此網格內一個成員節點位置.圖中簇頭與成員節點之間距離d可根據式(3)求得：

(3)

在此圓形單元格內，節點任務是將監測數據發給簇頭節點，規定區域內節點間通信距離均在距離閾值內，因此采用自由空間模型，則在圖中位置條件下，成員節點M向簇頭節點C發送kbit數據包時對應消耗的能量通過式(4)進行計算：

ES(k,d)=kEelec+kd2εfs=

kEelec+kεfs(r2-2lrcosα+l2)

(4)

位于陰影區域的節點的概率為ρ×Δa×a×Δα，進一步可以推導出網格內能量消耗的期望值Eepct：

圖1 簇頭最佳位置證明

(5)

從推導式(5)中可以看出，Eepct為單調函數，即在此單元格內進行數據傳輸的預期能量消耗Eepct與簇頭C所在位置到單元格中心的距離的平方成線性關系，因此，在進行簇頭選擇時，選擇距離虛擬單元格中心點近的簇頭能帶來更低的簇內通信能耗.

2.1 虛擬單元格動態劃分

網簇頭節點主要負責簇內通信、數據匯集及簇頭間的路由中繼.通過簇頭位置與簇內通信能耗關系推導可知，按照靠近網格中心位置作為簇頭選舉依據，可以降低單元格內預期能耗，本文采用如圖2所示的正方形網格形式對改進算法進行性能分析.

根據單元格內節點地理位置，賦予其節點ID信息Ni(x,y,i)，通過x,y值對節點所屬單元格進行判定，i為節點對應的唯一序號標識,如E和F為某一輪同屬一個虛擬單元格內的兩點，在圖2中，假定E點的節點ID信息為Ne(3,1,ie)，F點的節點ID信息為Nf(2,1,if)，兩點y值相同則判斷為同屬一列，再根據x判斷是否為相鄰單元格內節點.

在網絡運行過程中，周期性的執行虛擬單元格的動態劃分，在單元格內按如圖2所示進行區域劃分，以圖2中相鄰單元格A、B為例進行說明，a、b為對應單元格內中心區域，該區域內節點為中心區域節點.在下一輪網絡中，如圖3所示.

圖2 節點所處區域說明

圖3 虛擬單元格動態劃分

動態生成新的相鄰單元格A′、B′ ，其中a′、b′為新的中心區域，通過這種方式，實現虛擬單元格的動態劃分，使單元格中心區域動態變換，假設當前網絡運行輪次為r，具體執行過程如下：

1)根據地理位置獲得節點位置ID：Ni(x,y,i)，根據位置ID信息xmod3=0，的節點聲明自己為單元格中心區域節點，標注此時其對應x為xc，y為yc，該中心區域與相鄰區域組成本輪虛擬單元格，對應的節點在本輪網絡中為同簇，同簇節點判斷方式為：通過節點ID信息，y=yc的節點為同屬一列且x=xx+1或x=xc-1即判斷在本輪網絡中為同一個虛擬單元格內同簇節點；

2)輪次r=r+1，各節點更新節點ID信息，x=x+r，y保持不變，根據新的節點ID信息，xmod3=0的節點成為新的中心區域節點，y=yc且x=xc+1或x=xc-1的節點對應區域同屬于此輪網絡內同一虛擬單元格；

3)對處于網絡邊緣的區域，在某些網絡輪次中可能會出現孤立現象，即該區域非中心區域或未與任何中心區域相鄰，此時，該區域為獨立的虛擬單元格，區域內節點獨立成簇.

通過節點ID信息的更新，隨著網絡的運行不斷進行虛擬單元格的動態劃分，再在新的單元格中進行簇頭的選擇和成簇過程，進而實現動態分簇，使得網絡中的節點簇頭選舉優先級動態變化，以解決固定劃分單元格帶來的簇頭選舉過于集中的問題.

2.2 簇頭選舉改進算法和流程

傳統WSN分簇路由算法對簇頭選舉改進時，通常設置固定的能量閾值作為節點能否擔任成為簇頭節點的判斷[13].這種方法能夠有效的提升剩余能量較高的節點當選簇頭節點的概率，但容易造成大部分節點過早失去簇頭選舉資格.因此，為了解決這一問題，在本節將綜合考慮中心區域內節點的當前總平均剩余能量以及節點的當前剩余能量，設置節點剩余能量因子；
同時綜合考慮節點到單元格中心位置因素，設置簇頭選舉位置調節因子，盡可能的使得簇頭距離各個簇成員節點的距離總和最短，降低簇內通信代價，使虛擬單元格內簇頭及成員節點的能量消耗更加均衡，延長網絡生命周期.

2.2.1 簇頭選舉位置調節因子

節點在單元格中的位置是不同的，定義節點距中心點相對位置區間為[L0,L0(1+α)]，L0為節點在中心區域四角的節點到中心點處的距離，即中心區域內處于距離中心點的最遠處的節點，通過此方式對節點與區域中心點距離進行量化，其中α=(L0-d)/L0，d為節點距離中心點的距離，節點距離中心點越近，調節系數α值越大.可得中心區域內所有節點的總距離量化值為：

(6)

得到總調節系數α值為：

(7)

在WSN中，節點所處位置不同，則與中心點的距離也不一樣，因此，可以根據節點在中心區域內的相對位置，來差異化的設置節點被選舉為簇首的概率，以使得位置更佳的節點有更大的概率被選舉為簇頭節點，定義網絡內節點i的簇頭選舉位置調節因子為：

(8)

2.2.2 節點剩余能量因子

定義節點在當前輪次的剩余能量為Er，r為當前輪次，當前單元格內中心區域剩余總能量為ErTotal，能量調節因子為CE，當前單元格中心區域內節點總數為M，得到能量調節因子為：

(9)

對調節參數進行標準化后，最終節點對應的節點剩余能量因子為：

(10)

2.2.3 改進后的簇頭選舉式

綜合節點在區域內的相對位置和自身當前能量與總剩余能量均值關系，改進后的簇頭選舉式如式(11)所示：

(11)

其中：G為競選簇頭節點候選集合.

圖4 EBDPR算法流程圖

2.2.4 改進算法流程

改進后的算法流程圖如圖4所示，通過動態劃分虛擬單元格和定義中心區域，使得網絡內的分簇更加均勻能量消耗更加均衡；
通過添加位置和能量因素對簇頭選舉方法進行改進，使相對位置和剩余能量更具優勢的節點有更大的概率當選為簇頭，避免節點因能量耗盡而過早失效；
在路由建立數據傳輸階段，通過當前輪次簇頭收到的成員節點ID信息和剩余能量信息，統計本輪次結束時節點狀態，以選出下一輪網絡內的簇頭，并向其發送簇頭當選指令，避免了隨機數方式選取簇頭帶來的隨機性.同時，設置避空定時器Te和Td，當節點在定時器結束時未入簇，則根據簇頭信息強弱選擇簇頭入簇或直接與基站通信，避免孤立節點.

為了驗證算法的有效性，本文設置節點被隨機的分布在100 m×100 m的方形區域內，設置基站位于(50，50)處，對EBDPR算法進行仿真時，設置虛擬單元格邊長為r=33 m，節點初始能量在[E0,e0(1+λ)]內取值，設置能量異構參數 ，設置高級節點比例為0.1，對LEACH、SEP、DEEC算法設置簇頭選舉概率為0.1，網絡內節點平均初始能量為0.2J，各個算法內節點初始分布情況相同.

在網絡運行過程中，如圖5(A)為節點初始分布圖，圖5(B)～(D)為EBDPR算法在網絡運行過程中的虛擬單元格動態劃分情況，以顏色差異來表示節點分屬于不同的虛擬單元格內.

圖5 虛擬單元格動態劃分

通過動態劃分虛擬單元格和定義中心區域，使得網絡內的分簇更加均勻能量消耗更加均衡；
通過添加位置和能量因素對簇頭選舉方法進行改進，使相對位置和剩余能量更具優勢的節點有更大的概率當選為簇頭，避免節點因能量耗盡而過早失效；
在路由建立數據傳輸階段，通過當前輪次簇頭收圖6對幾種算法在網絡運行過程中的節點存活數目進行了對比，EBDPR算法首個節點失效發生在485輪，LEACH、SEP、DEEC算法首個節點失效分別發生在212、299、379輪.

相較于LEACH、SEP、DEEC算法EBDPR算法在首個節點失效發生時間分別延后了128.7%、62.2%、23.2%.不難看出，本文算法能夠很好的延長網絡的穩定傳輸時間，同時，也可以看到EBDPR算法全部節點失效輪數也得到了有效的延后，提高了網絡的生存周期.

圖6 網絡內節點存活數目

在進行節點剩余能量標準差仿真實驗對比時，為了方便統計，設置初始能量為0.5 J的節點數目為10個，初始能量為0.2 J的節點數目為90個，即網絡初始狀態下節點剩余能量標準差為0.09，并對網絡運行輪次為150、300、450、600輪時的節點剩余能量標準差進行統計.仿真結果如圖7所示.

圖7 節點剩余能量標準差

可以看到，隨著網絡的運行，LEACH算法由于簇頭的選取具有太大的隨機性，其節點剩余能量標準差曲線具有較大的波動性；
其余三個算法由于在進行簇頭選擇和分簇時，對簇頭的剩余能量進行了考慮，在網絡運行剛開始時，由于初始能量高的節點在能量方面仍然占有較大的優勢，而隨著網絡的運行，高初始能量節點的優勢逐漸減弱，節點間剩余能量值也逐漸趨于接近，因此，節點剩余能量標準差曲線總體呈現先上升后下降的趨勢.同時，可以看到EBDPR算法的節點剩余能量標準差曲線隨著網絡的運行，后期一直居于最下方，表明其對于平衡網絡內節點能耗有更好的效果.

本文基于能耗均衡和延長無線傳感器網絡生存周期進行研究，提出實現了一種EBDPR算法，在LEACH算法的實現基礎上結合動態分區思想，提出節點ID信息方法，實現虛擬單元格的動態劃分，避免“熱區”現象，達到簇頭選舉區域的動態變換.在簇頭選舉階段通過考慮當前網絡下節點的相對位置和能量情況，以降低簇內代價和避免簇頭節點過早失效.通過仿真結果可以看出，EBDPR算法能夠使網絡在運行過程中的穩定傳輸階段更為長久，生存周期得到延長，對異構網絡有較好的適應性，同時通過對網絡運行過程中網絡內節點間標準差的比較，也能體現其在能耗方面的均衡性，實現了對WSN在能量消耗和生存周期方面的優化.