基于能耗均衡的改進(jìn)分簇路由算法研究

張 豪

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

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

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

為了使無(wú)線(xiàn)傳感器網(wǎng)絡(luò )在能耗均衡方面具有更好的表現，達到延長(cháng)網(wǎng)絡(luò )的穩定期和生存周期的目的，要從解決分簇不均和簇頭位置的隨機性?xún)煞矫孢M(jìn)行考慮[10].本文提出動(dòng)態(tài)分區的方法進(jìn)行網(wǎng)絡(luò )分簇，使WSN在運行過(guò)程中通過(guò)區域劃分在分簇時(shí)具有動(dòng)態(tài)性，各節點(diǎn)參與簇頭選舉的優(yōu)先級在網(wǎng)絡(luò )運行過(guò)程中隨著(zhù)所歸屬區域不同而產(chǎn)生動(dòng)態(tài)變化，使網(wǎng)絡(luò )內節點(diǎn)能耗更為均衡；
通過(guò)論證得到的簇頭位置與簇內通信能耗關(guān)系，綜合考慮節點(diǎn)所處位置與當前剩余能量，對簇頭選舉階段進(jìn)行改進(jìn)，使選舉出的簇頭能夠使簇內通信能耗情況得到優(yōu)化，延長(cháng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的穩定期和生存周期.

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

1.1 能量消耗模型

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

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

ET(k,d)=ETE+ETA=

(1)

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

由上述能量消耗式可以看出，在WSN中，能量消耗主要發(fā)生在數據的無(wú)線(xiàn)傳輸過(guò)程中[15].進(jìn)行數據發(fā)送時(shí)，所消耗的能量ETE與傳輸距離d呈正相關(guān)關(guān)系，收發(fā)端距離d越大對應的能量消耗也越高.

1.2 簇內位置與簇內通信能耗關(guān)系

為方便進(jìn)行計算說(shuō)明，在此處定義以圓形區域作為虛擬單元格，且傳感器節點(diǎn)在該區域內以密度ρ進(jìn)行均勻分布，且每個(gè)節點(diǎn)需要發(fā)送的數據包數量也是相同的.同時(shí)，使用一階無(wú)線(xiàn)電能量模型來(lái)計算節點(diǎn)的行為消耗，即發(fā)送和接收的消耗通過(guò)式(2)進(jìn)行計算：

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

(2)

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

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

(3)

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

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

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

(4)

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

圖1 簇頭最佳位置證明

(5)

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

2.1 虛擬單元格動(dòng)態(tài)劃分

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

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

在網(wǎng)絡(luò )運行過(guò)程中，周期性的執行虛擬單元格的動(dòng)態(tài)劃分，在單元格內按如圖2所示進(jìn)行區域劃分，以圖2中相鄰單元格A、B為例進(jìn)行說(shuō)明，a、b為對應單元格內中心區域，該區域內節點(diǎn)為中心區域節點(diǎn).在下一輪網(wǎng)絡(luò )中，如圖3所示.

圖2 節點(diǎn)所處區域說(shuō)明

圖3 虛擬單元格動(dòng)態(tài)劃分

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

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

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

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

通過(guò)節點(diǎn)ID信息的更新，隨著(zhù)網(wǎng)絡(luò )的運行不斷進(jìn)行虛擬單元格的動(dòng)態(tài)劃分，再在新的單元格中進(jìn)行簇頭的選擇和成簇過(guò)程，進(jìn)而實(shí)現動(dòng)態(tài)分簇，使得網(wǎng)絡(luò )中的節點(diǎn)簇頭選舉優(yōu)先級動(dòng)態(tài)變化，以解決固定劃分單元格帶來(lái)的簇頭選舉過(guò)于集中的問(wèn)題.

2.2 簇頭選舉改進(jìn)算法和流程

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

2.2.1 簇頭選舉位置調節因子

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

(6)

得到總調節系數α值為：

(7)

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

(8)

2.2.2 節點(diǎn)剩余能量因子

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

(9)

對調節參數進(jìn)行標準化后，最終節點(diǎn)對應的節點(diǎn)剩余能量因子為：

(10)

2.2.3 改進(jìn)后的簇頭選舉式

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

(11)

其中：G為競選簇頭節點(diǎn)候選集合.

圖4 EBDPR算法流程圖

2.2.4 改進(jìn)算法流程

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

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

在網(wǎng)絡(luò )運行過(guò)程中，如圖5(A)為節點(diǎn)初始分布圖，圖5(B)～(D)為EBDPR算法在網(wǎng)絡(luò )運行過(guò)程中的虛擬單元格動(dòng)態(tài)劃分情況，以顏色差異來(lái)表示節點(diǎn)分屬于不同的虛擬單元格內.

圖5 虛擬單元格動(dòng)態(tài)劃分

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

相較于LEACH、SEP、DEEC算法EBDPR算法在首個(gè)節點(diǎn)失效發(fā)生時(shí)間分別延后了128.7%、62.2%、23.2%.不難看出，本文算法能夠很好的延長(cháng)網(wǎng)絡(luò )的穩定傳輸時(shí)間，同時(shí)，也可以看到EBDPR算法全部節點(diǎn)失效輪數也得到了有效的延后，提高了網(wǎng)絡(luò )的生存周期.

圖6 網(wǎng)絡(luò )內節點(diǎn)存活數目

在進(jìn)行節點(diǎn)剩余能量標準差仿真實(shí)驗對比時(shí)，為了方便統計，設置初始能量為0.5 J的節點(diǎn)數目為10個(gè)，初始能量為0.2 J的節點(diǎn)數目為90個(gè)，即網(wǎng)絡(luò )初始狀態(tài)下節點(diǎn)剩余能量標準差為0.09，并對網(wǎng)絡(luò )運行輪次為150、300、450、600輪時(shí)的節點(diǎn)剩余能量標準差進(jìn)行統計.仿真結果如圖7所示.

圖7 節點(diǎn)剩余能量標準差

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

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