基于能量和距離的非均勻分簇路由算法

金 彤，曾子維，王 剛

（遼寧科技大學(xué) 計(jì)算機(jī)與軟件工程學(xué)院，遼寧 鞍山 114051）

無線傳感器網(wǎng)絡(luò)（Wireless sensor network，WSN）是由眾多的傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)［1］，在智能交通、環(huán)境檢測(cè)、工業(yè)控制等領(lǐng)域都有很好的發(fā)展優(yōu)勢(shì)。通常情況下WSN中的節(jié)點(diǎn)采用蓄電池供電，但由于網(wǎng)絡(luò)實(shí)際情況復(fù)雜，更換節(jié)點(diǎn)電池較為困難。因此設(shè)計(jì)一個(gè)高效節(jié)能的路由協(xié)議尤為重要。

WSN路由協(xié)議主要分為平面路由和分簇路由。其中應(yīng)用最為廣泛的就是低能量自適應(yīng)聚簇分層協(xié)議（Low energy adaptive clustering hierarchy，LEACH）［2］，該協(xié)議引入“輪”概念，網(wǎng)絡(luò)在運(yùn)行中的每一輪都會(huì)進(jìn)行簇頭節(jié)點(diǎn)的更換，基于概率選舉簇頭，普通成員節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度來選擇加入簇。在選舉過程中，如果忽略節(jié)點(diǎn)的剩余能量，會(huì)導(dǎo)致選舉過程中出現(xiàn)網(wǎng)絡(luò)能耗分布不均勻，部分節(jié)點(diǎn)過早死亡等問題。針對(duì)此問題有很多改進(jìn)算法，趙小強(qiáng)等［3］提出一種基于模擬退火算法和改進(jìn)灰狼優(yōu)化器的異構(gòu)WSN路由協(xié)議，算法定義適應(yīng)度函數(shù)，利用模擬退火確保網(wǎng)絡(luò)中最優(yōu)簇群，均衡網(wǎng)絡(luò)能耗，但距基站較近的簇能耗過大，產(chǎn)生的“熱區(qū)”問題并未有效解決。Gachhandar等［4］提出基于K-means的分簇路由算法，但在選舉簇頭時(shí)只考慮節(jié)點(diǎn)的能量和距離，依然存在“熱區(qū)”問題。吉訓(xùn)生等［5］為解決“熱區(qū)”問題，引入雙簇頭思想，有效均衡節(jié)點(diǎn)能耗。韓廣輝等［6］提出基于能量均衡和分簇的LEACH-E節(jié)能算法，該算法在初始階段綜合考慮節(jié)點(diǎn)的剩余能量和網(wǎng)絡(luò)平均剩余能量，使剩余能量比網(wǎng)絡(luò)平均能量高的節(jié)點(diǎn)優(yōu)先選為簇頭，改進(jìn)閾值計(jì)算式，使選舉階段的能耗問題得到解決，但沒有解決簇頭分布不均的問題。

本文針對(duì)已有路由算法存在的問題，為提高整體網(wǎng)絡(luò)的能量效率，延長(zhǎng)網(wǎng)絡(luò)的生存周期，提出一種新的非均勻分簇路由算法，即ONCH-LEACH算法，依靠網(wǎng)絡(luò)能耗模型確定最佳簇頭數(shù)目，根據(jù)網(wǎng)絡(luò)的實(shí)際情況，改進(jìn)簇頭選擇概率，將節(jié)點(diǎn)剩余能量、簇內(nèi)節(jié)點(diǎn)覆蓋率和地理位置引入簇頭選舉閾值函數(shù)中，解決節(jié)點(diǎn)因能量過低提前死亡從而造成網(wǎng)絡(luò)部分癱瘓的問題。簇頭節(jié)點(diǎn)選擇之后，每個(gè)簇頭節(jié)點(diǎn)根據(jù)距離基站的距離以及剩余能量產(chǎn)生自身的成簇規(guī)模的動(dòng)態(tài)半徑，使越靠近基站的簇，簇的規(guī)模越小，整體網(wǎng)絡(luò)實(shí)現(xiàn)非均勻分簇，以解決“熱區(qū)”問題。在傳輸數(shù)據(jù)階段，提出新的數(shù)據(jù)分發(fā)機(jī)制，綜合考慮節(jié)點(diǎn)的距離和傳輸數(shù)據(jù)量以及前簇頭節(jié)點(diǎn)的剩余能量，根據(jù)路徑代價(jià)函數(shù)動(dòng)態(tài)選擇最優(yōu)的中繼節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，從而減少傳輸過程中的能耗。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

假設(shè)在一個(gè)M×M的區(qū)域內(nèi)，有N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布，且該網(wǎng)絡(luò)具有以下性質(zhì)：

（1）節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域中隨機(jī)分散，每個(gè)節(jié)點(diǎn)的初始能量由電池提供。

（2）所有傳感器節(jié)點(diǎn)具有相同的結(jié)構(gòu)，并且每個(gè)節(jié)點(diǎn)有唯一的標(biāo)識(shí)（ID）［7］，初始能量是相同的，節(jié)點(diǎn)和基站的位置在部署后是靜止的。

（3）網(wǎng)絡(luò)中節(jié)點(diǎn)之間的通信鏈路是對(duì)稱的，節(jié)點(diǎn)的通信距離可控，已知對(duì)方發(fā)射功率，節(jié)點(diǎn)可根據(jù)RSSI（Received signal strength indicator）信號(hào)值計(jì)算出發(fā)送者到自身的近似距離，同時(shí)感知自己的剩余能量。

（4）網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)可以控制發(fā)送和接收的功率，即節(jié)點(diǎn)可根據(jù)需要調(diào)整自身發(fā)射功率。

（5）在節(jié)點(diǎn)的通信半徑范圍內(nèi)，節(jié)點(diǎn)可以相互通信。

1.2 能量消耗模型

本文所選擇的能耗模型主要基于LEACH算法［8］。算法根據(jù)發(fā)送者和接收者之間的距離d選擇對(duì)應(yīng)的模式：如果距離小于d0限值，使用自由空間模式計(jì)算能量消耗；當(dāng)距離大于d0，選擇多徑衰減模式［9］。節(jié)點(diǎn)發(fā)送l比特?cái)?shù)據(jù)的能耗為

接收消耗的能量為

閾值d0的定義式為

式中：Eelec表示發(fā)送和接收電路每傳輸1 bit數(shù)據(jù)的耗能；l為傳送數(shù)據(jù)的長(zhǎng)度；εfs為自由空間傳播模型能耗；εamp為多路徑衰減傳播模型的能耗。

2 ONCH-LEACH算法

2.1 最優(yōu)簇頭數(shù)目

簇頭節(jié)點(diǎn)的能量消耗主要來源于接收簇內(nèi)普通節(jié)點(diǎn)收集來的數(shù)據(jù)信息，融合簇內(nèi)信息和發(fā)送融合后的數(shù)據(jù)信息給基站。令最優(yōu)簇頭數(shù)為COPT，采用多路徑衰減模型，每一輪中簇頭的能量消耗為

式中：l為傳送數(shù)據(jù)的長(zhǎng)度；N為網(wǎng)絡(luò)的隨機(jī)分布的節(jié)點(diǎn)數(shù)；C為網(wǎng)絡(luò)中的簇頭數(shù)目；dtoBS為簇頭和基站BS的距離；EDA是數(shù)據(jù)融合率。

其他普通成員節(jié)點(diǎn)的能量消耗為

式中：dtoCH為網(wǎng)絡(luò)中非簇頭節(jié)點(diǎn)與簇頭節(jié)點(diǎn)間的距離。

每個(gè)簇在一幀內(nèi)的能量消耗為

假設(shè)在面積為M×M的區(qū)域中隨機(jī)分布N個(gè)傳感器節(jié)點(diǎn)，簇頭位于每個(gè)簇的中心，由于感知區(qū)

在整個(gè)區(qū)域內(nèi)WSN的總能耗為

對(duì)Etotal求C導(dǎo)數(shù)，得出網(wǎng)絡(luò)中最優(yōu)簇頭數(shù)目公式

2.2 改進(jìn)的簇頭選舉概率公式

為了最大化利用節(jié)點(diǎn)能量，確定最優(yōu)簇頭數(shù)COPT后，在簇頭選舉概率公式中，引入當(dāng)前參與競(jìng)選簇頭節(jié)點(diǎn)的剩余能量與所有節(jié)點(diǎn)的平均剩余能量的比值，從而降低能量較低的節(jié)點(diǎn)當(dāng)選簇頭的概率，緩解因簇頭能量較低導(dǎo)致的部分網(wǎng)絡(luò)癱瘓的問題。本文提出的新的簇頭選舉概率公式為

式中：Eicu-avg為當(dāng)前節(jié)點(diǎn)平均剩余能量；Eicu-resi為當(dāng)前節(jié)點(diǎn)剩余能量。

2.3 剩余能量參數(shù)

WSN中各個(gè)節(jié)點(diǎn)的初始儲(chǔ)存能量是相同的。隨著網(wǎng)絡(luò)的循環(huán)，符合條件的一部分節(jié)點(diǎn)被選為簇頭，其余普通節(jié)點(diǎn)則選擇加入適合的簇群。為了使能量更大的節(jié)點(diǎn)當(dāng)選簇頭，本文提出剩余能量參數(shù)Ei，綜合考慮了節(jié)點(diǎn)剩余能量、存活節(jié)點(diǎn)的能量平均值以及節(jié)點(diǎn)的初始能量之間的比值，Ei值隨著循環(huán)輪數(shù)而變化，使閾值的定義具有實(shí)時(shí)性。Ei定義式

式中：E0為初始能量。

2.4 間距參數(shù)

在WSN中，節(jié)點(diǎn)距離基站越遠(yuǎn)，接收到的信號(hào)越弱。在初始階段，各個(gè)節(jié)點(diǎn)通過接收基站發(fā)送信號(hào)的強(qiáng)弱，得到自身的距離d，并返回給基站。距離基站越遠(yuǎn)的節(jié)點(diǎn)，傳輸過程中能量消耗越大。因此，節(jié)點(diǎn)與基站的距離在簇頭的選舉中有著至關(guān)重要的作用。本文提出的節(jié)點(diǎn)間距參數(shù)定義式

式中：Dicu-avg為網(wǎng)絡(luò)中節(jié)點(diǎn)到基站距離平均值。

2.5 密度覆蓋率參數(shù)

WSN的節(jié)點(diǎn)隨機(jī)分布在區(qū)域內(nèi)，所以網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目存在一定差異。簇頭的選舉應(yīng)該考慮其周圍的節(jié)點(diǎn)分布率，選擇節(jié)點(diǎn)匯聚度較高的節(jié)點(diǎn)成為簇頭，從而降低能耗。簇頭的鄰居節(jié)點(diǎn)為該簇頭最大可覆蓋通信范圍內(nèi)所有節(jié)點(diǎn)的集合。本文引入密度覆蓋率，定義式為

式中：Nρ為密度覆蓋率參數(shù)；Nneig為節(jié)點(diǎn)在其通信半徑內(nèi)的鄰居節(jié)點(diǎn)的數(shù)量。

Nρ值大，說明實(shí)際鄰居節(jié)點(diǎn)更密集，信息處理量大。

2.6 簇頭選舉閾值公式

將所提出的剩余能量參數(shù)、間距參數(shù)和密度覆蓋率參數(shù)融入閾值公式中，同時(shí)引入加權(quán)因子α，定義為能量距離因子，取值為2或4，取決于節(jié)點(diǎn)間距離d。β為密度覆蓋率加權(quán)因子，γ為節(jié)點(diǎn)間距加權(quán)因子，兩個(gè)加權(quán)因子取值為0～1之間的常量，取決于實(shí)際環(huán)境對(duì)位置間距和密度的要求。簇頭選舉閾值定義式

2.7 非均勻成簇機(jī)制

選舉簇頭后，不同簇頭節(jié)點(diǎn)剩余的能量不同，簇內(nèi)能容納的節(jié)點(diǎn)數(shù)目不同。因此，根據(jù)簇頭節(jié)點(diǎn)的剩余能量和距離，設(shè)置動(dòng)態(tài)通信半徑

式中：Rmax為初始最大通信距離；Eicu-avg為節(jié)點(diǎn)平均剩余能量；Eicu-resi為該節(jié)點(diǎn)剩余能量。

隨后，節(jié)點(diǎn)根據(jù)接收到的信息，選擇適合的簇加入，成簇規(guī)則為

式中：V表示簇頭集合；d(i,CH)表示節(jié)點(diǎn)i到簇頭的距離。

E(i,nj)表示當(dāng)有nj節(jié)點(diǎn)加入某簇后，每個(gè)節(jié)點(diǎn)分配的能量。計(jì)算式為

式中：Ech(i)表示當(dāng)前簇的節(jié)點(diǎn)能量；nj表示當(dāng)前加入該簇的節(jié)點(diǎn)數(shù)目；Emin表示節(jié)點(diǎn)存活的最小能量。

當(dāng)節(jié)點(diǎn)滿足成簇規(guī)則時(shí)，接收到多個(gè)簇頭節(jié)點(diǎn)發(fā)來的信息，節(jié)點(diǎn)會(huì)選擇E(i,nj)值最大的簇加入。若沒有滿足成簇規(guī)則，則選擇最近的簇加入。因此，通過剩余能量和距離的引入可以均衡簇內(nèi)的能耗，使剩余能量較小和距離基站較近的簇頭成簇規(guī)模較小，實(shí)現(xiàn)網(wǎng)絡(luò)的非均勻分簇，有效緩解網(wǎng)絡(luò)的“熱區(qū)”問題。

2.8 數(shù)據(jù)傳輸階段

在WSN節(jié)點(diǎn)能耗模型［10］中，通信能耗占主要部分。當(dāng)簇結(jié)構(gòu)構(gòu)造完成后，網(wǎng)絡(luò)進(jìn)入數(shù)據(jù)傳輸階段。在這個(gè)過程中，當(dāng)簇頭節(jié)點(diǎn)傳輸距離較遠(yuǎn)時(shí)，選出適合的簇頭節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，將數(shù)據(jù)逐步轉(zhuǎn)發(fā)到基站。以最佳的路徑進(jìn)行數(shù)據(jù)傳輸，從而達(dá)到提升網(wǎng)絡(luò)性能的目的。

本文將數(shù)據(jù)分發(fā)規(guī)則進(jìn)行改進(jìn)，提出一種綜合考慮數(shù)據(jù)量和節(jié)點(diǎn)距離以及節(jié)點(diǎn)剩余能量的多跳數(shù)據(jù)分發(fā)方式。當(dāng)簇頭有數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)時(shí)，查看鄰居節(jié)點(diǎn)與基站的距離，選擇比自身更接近基站的前鄰居簇頭節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)的路徑轉(zhuǎn)發(fā)代價(jià)函數(shù)，選擇函數(shù)值最低的節(jié)點(diǎn)進(jìn)行下一跳傳輸。

定義前向鄰居節(jié)點(diǎn)

定義前向簇頭鄰居節(jié)點(diǎn)

本文提出的中繼節(jié)點(diǎn)路徑轉(zhuǎn)發(fā)代價(jià)函數(shù)

式中：dis(i,BS)是備選的中繼節(jié)點(diǎn)i與基站之間的距離；Eicu-resi(i)是節(jié)點(diǎn)i的當(dāng)前剩余能量；χ為加權(quán)參數(shù)，經(jīng)過反復(fù)實(shí)驗(yàn)，設(shè)置為0.4。

本文提出的路由代價(jià)函數(shù)，可以動(dòng)態(tài)選擇下一跳簇頭，減緩單個(gè)簇頭節(jié)點(diǎn)承擔(dān)轉(zhuǎn)發(fā)數(shù)據(jù)量過大的問題，也分擔(dān)了整體網(wǎng)絡(luò)的能量消耗。

3 算法設(shè)計(jì)與實(shí)現(xiàn)

本文提出的ONCH-LEACH算法分為兩個(gè)階段。在分簇階段，首先利用網(wǎng)絡(luò)模型確定最優(yōu)簇頭數(shù)目，網(wǎng)絡(luò)區(qū)域中所有節(jié)點(diǎn)通過rand（0，1）函數(shù)產(chǎn)生一個(gè)［0，1］間的隨機(jī)數(shù)。其次將節(jié)點(diǎn)的剩余能量、間距以及節(jié)點(diǎn)密度覆蓋率引入閾值公式中，當(dāng)自身產(chǎn)生的隨機(jī)數(shù)小于閾值公式時(shí)，該節(jié)點(diǎn)就當(dāng)選為簇頭節(jié)點(diǎn)。隨后，競(jìng)選成功的簇頭在通信范圍內(nèi)廣播競(jìng)選成功的消息。其余節(jié)點(diǎn)若同時(shí)收到多個(gè)簇頭競(jìng)選成功的消息，則對(duì)比接收到的信號(hào)強(qiáng)弱，選擇信號(hào)較強(qiáng)、距離較近且被簇頭平均分配的能量較大的簇申請(qǐng)加入。若普通節(jié)點(diǎn)未收到簇頭發(fā)來的消息，則自己當(dāng)選簇頭。當(dāng)節(jié)點(diǎn)全部入簇成功后，進(jìn)入數(shù)據(jù)傳輸階段。當(dāng)簇頭有數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)時(shí)，簇頭選擇代價(jià)函數(shù)較低的節(jié)點(diǎn)進(jìn)行下一跳的數(shù)據(jù)傳輸。本文算法流程圖如圖1所示。

圖1 算法流程圖Fig.1 Flow chart of algorithm

4 仿真實(shí)驗(yàn)分析

4.1 仿真環(huán)境及參數(shù)

采用MATLAB進(jìn)行仿真實(shí)驗(yàn)，在100 m×100 m的監(jiān)控區(qū)域內(nèi)，隨機(jī)部署400個(gè)節(jié)點(diǎn)，分別在區(qū)域內(nèi)和區(qū)域外部署基站，區(qū)域外基站的位置設(shè)為（50，150），區(qū)域內(nèi)基站設(shè)置為（50，50）。具體參數(shù)：節(jié)點(diǎn)初始能量0.5 J，發(fā)送和接受數(shù)據(jù)的能耗Eelec=50 nJ/bit，自由空間模型參數(shù)εfs=10 pJ/（bit·m2），多路徑衰落空間模型參數(shù)εamp=0.001 3 pJ/（bit·m4），EDA=50 nJ/bit，d0=87 m，數(shù)據(jù)信息包4 000 bit，循環(huán)次數(shù)2 500輪，β=0.3，γ=0.7，Rmax=15，Emin=0.001 J。

4.2 仿真結(jié)果分析

節(jié)點(diǎn)隨機(jī)拋灑在網(wǎng)絡(luò)區(qū)域內(nèi)，分別考慮基站在節(jié)點(diǎn)區(qū)域內(nèi)和區(qū)域外兩種情況進(jìn)行分析，整體網(wǎng)絡(luò)分布如圖2所示。

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)分布圖Fig.2 Distribution of network nodes

將本文的ONCH-LEACH算法與LEACH算法、LEACH-E算法分別在存活節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)能耗方面進(jìn)行對(duì)比。

（1）存活節(jié)點(diǎn)個(gè)數(shù)對(duì)比。存活節(jié)點(diǎn)數(shù)的仿真結(jié)果如圖3所示。在循環(huán)2 500輪時(shí)，無論基站部署在區(qū)域內(nèi)還是區(qū)域外，本文提出的ONCHLEACH算法存活節(jié)點(diǎn)個(gè)數(shù)明顯增多?；驹趨^(qū)域內(nèi)部署時(shí)，ONCH-LEACH算法到1 990輪網(wǎng)絡(luò)中的節(jié)點(diǎn)全部死亡，LEACH和LEACH-E分別在1 351輪和1 642輪全部死亡。基站在區(qū)域外部署時(shí)，ONCH-LEACH算法到2 189輪網(wǎng)絡(luò)中的節(jié)點(diǎn)全部死亡，LEACH和LEACH-E分別在1 654輪和1 861輪全部死亡。這說明本文算法能極大地延緩節(jié)點(diǎn)死亡時(shí)間，使網(wǎng)絡(luò)中的存活節(jié)點(diǎn)數(shù)明顯增多，延長(zhǎng)了網(wǎng)絡(luò)的生存周期。

圖3 存活節(jié)點(diǎn)數(shù)目與循環(huán)輪數(shù)對(duì)比圖Fig.3 Comparison between number of surviving nodes and number of loop rounds

（2）網(wǎng)絡(luò)消耗總能量對(duì)比。網(wǎng)絡(luò)總能量仿真結(jié)果如圖4所示。相比其他兩種協(xié)議，ONCHLEACH系統(tǒng)總能量最高，即能耗最低。因?yàn)镺NCH-LEACH算法充分考慮節(jié)點(diǎn)的地理位置，減少普通節(jié)點(diǎn)到簇首的網(wǎng)絡(luò)消耗，減少簇中和簇間網(wǎng)絡(luò)能耗，均衡全局節(jié)點(diǎn)的能耗。

圖4 系統(tǒng)總能量與循環(huán)輪數(shù)對(duì)比圖Fig.4 Comparison between total system energy and number of loop rounds

5 結(jié)論

本文提出ONCH-LEACH分簇算法，引入最優(yōu)簇頭數(shù)目，改進(jìn)簇頭選擇概率，綜合考慮節(jié)點(diǎn)的能耗以及生存周期問題，將剩余能量、間距、密度覆蓋率三個(gè)參數(shù)加入閾值計(jì)算式中，從而得出新的閾值選舉計(jì)算方法。在分簇階段，綜合考慮簇頭與節(jié)點(diǎn)之間的雙向選擇，將簇頭的剩余能量和簇頭節(jié)點(diǎn)距基站的距離引入其中，使剩余能量較低和距離基站較近的簇頭成簇規(guī)模較小，從而實(shí)現(xiàn)非均勻分簇，均衡網(wǎng)絡(luò)的能耗。在數(shù)據(jù)傳輸階段，綜合考慮節(jié)點(diǎn)的數(shù)據(jù)量以及節(jié)點(diǎn)間距離，提出新的多跳數(shù)據(jù)傳輸方式，根據(jù)代價(jià)函數(shù)動(dòng)態(tài)選擇中繼節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸。仿真對(duì)比發(fā)現(xiàn)，無論基站部署在區(qū)域內(nèi)還是區(qū)域外，本文提出的算法能夠降低網(wǎng)絡(luò)總能耗，提高節(jié)點(diǎn)存活率，延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。