基于最優(yōu)簇頭數(shù)的LEACH改進(jìn)算法研究①

丁俊美

(合肥財(cái)經(jīng)職業(yè)學(xué)院人工智能學(xué)院,安徽 合肥 230601)

0 引 言

LEACH算法是一種經(jīng)典的單跳分簇協(xié)議,其算法思想是:LEACH每"輪"(round)都進(jìn)行簇頭的選取,為了能使所有節(jié)點(diǎn)負(fù)載均衡,LEACH算法中傳感器節(jié)點(diǎn)成為簇頭的機(jī)會(huì)均等,并隨機(jī)循環(huán)下去,避免了部分節(jié)點(diǎn)能量消耗過快,造成網(wǎng)絡(luò)過早死亡。但是LEACH協(xié)議沒有將節(jié)點(diǎn)剩余能量考慮進(jìn)簇頭選取中,傳感器種類和分布對(duì)其能耗均有影響,而能量較低的節(jié)點(diǎn)成為簇頭,則影響網(wǎng)絡(luò)的壽命。另外,LEACH協(xié)議隨機(jī)性選擇簇頭,簇頭的個(gè)數(shù)和位置無法達(dá)到最優(yōu)化,成員節(jié)點(diǎn)分布不均勻,部分距離簇頭較遠(yuǎn)的節(jié)點(diǎn)能耗過高。因此,將著重對(duì)這些問題進(jìn)行研究和改進(jìn)。

1 路由策略設(shè)計(jì)

1.1 簇頭數(shù)最優(yōu)算法能量模型

LEACH協(xié)議中簇頭數(shù)是隨機(jī)確定的,簇頭數(shù)過多,造成多余的簇頭節(jié)點(diǎn)能量消耗,加快網(wǎng)絡(luò)死亡速度;簇頭數(shù)過少,則有部分普通節(jié)點(diǎn)未被覆蓋。因此,必須計(jì)算出簇頭的最優(yōu)個(gè)數(shù),使閾值T(N)公式中的P(簇頭數(shù)與節(jié)點(diǎn)總數(shù)之比的百分?jǐn)?shù))值最優(yōu)化。

LEACH協(xié)議使用的能量消耗模式是一階無線通信模式[1],如圖1所示。

在上述模式下,節(jié)點(diǎn)能耗主要發(fā)生在接收和發(fā)送數(shù)據(jù)的過程中。節(jié)點(diǎn)發(fā)送lbit數(shù)據(jù)到距離為d的接收節(jié)點(diǎn)需耗費(fèi)的能量如公式(1)所示:

ETX(l,d)=Eelec(l)+E(TX-mp)(l,d)=

(1)

圖1 無線通信模型

接收lbit數(shù)據(jù),節(jié)點(diǎn)將耗費(fèi)能量如公式(2)所示:

ERX(l)=Eelec×l

(2)

式(2)中,發(fā)送lbit數(shù)據(jù)耗費(fèi)能量為ETX-mp,接收lbit數(shù)據(jù)耗費(fèi)能量為ERX,在多路衰減模型下,功率放大系數(shù)為εmp[2]。在自由空間模型下,功率放大系數(shù)為εfs,εmp和εfs是常數(shù),由發(fā)射距離和接收誤碼率等因素決定,d0是決定何種模型的閾值。當(dāng)d

(3)

式(3)中,L是系統(tǒng)能耗因子,ha是發(fā)送天線高度,hb是接收天線高度,λ是載波波長(zhǎng)。

1.2 最優(yōu)簇頭數(shù)計(jì)算

(1)簇形成階段的能量消耗

1)簇頭節(jié)點(diǎn)能耗

簇頭向普通節(jié)點(diǎn)發(fā)送廣播信息,根據(jù)多路衰減模型[4],即d≥d0,保證簇頭的廣播信息能覆蓋網(wǎng)絡(luò)大部分區(qū)域,簇頭節(jié)點(diǎn)此時(shí)消耗的能量如公式(4)所示:

Eelec·l+εmp·l·dtoBS4

(4)

(5)

在一輪中,簇頭總耗能如公式(6)所示:

(6)

2)普通節(jié)點(diǎn)能耗

普通節(jié)點(diǎn)接收簇頭信消耗能如公式(7)所示:

Eelec·l

(7)

普通節(jié)點(diǎn)向簇頭發(fā)送加入簇信息,這里采用自由空間模型,即d

Eelec·l+εfs·l·dtoCH2

(8)

在一輪中,每個(gè)成員節(jié)點(diǎn)總耗能如公式(9)所示:

Eno-ch=2·Eelec·l+εfs·l·dtoCH2

(9)

3)每個(gè)簇在成簇過程中總的耗能如公式(10)所示:

(10)

4)K個(gè)簇消耗的總能量如公式(11)所示:

(11)

(2)簇頭數(shù)優(yōu)化算法

簇頭位置、簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)和位置實(shí)際上是不確定的,也就是dtoCH的值是不確定的,使用數(shù)學(xué)期望值的方法求得最優(yōu)dtoCH的值,代入能量模型公式中計(jì)算出最優(yōu)簇頭數(shù)K。

?r2ρ(r,θ)rdrdθ

(12)

(13)

把式(13)代入式(11)中,結(jié)果如公式(14)所示:

EZ=l·[(3N-2K)·Eelec+K·εmp·

(14)

對(duì)EZ求導(dǎo)數(shù),并令其等于0,產(chǎn)生式如公式(15)所示:

(15)

對(duì)式(15)進(jìn)行分解得到最優(yōu)簇頭數(shù)K的如公式(16)所示:

(16)

1.3 簇頭選擇算法

在每輪中,LEACH協(xié)議將節(jié)點(diǎn)的隨機(jī)數(shù)與T(N)進(jìn)行比較,如果大于T(N),則為成員節(jié)點(diǎn),否則為簇頭。算法在簇頭選取時(shí)可以將能量比例加入LEACH算法中,即在閾值T(N)公式中加入剩余能量Er與初始能量Ei的比值,優(yōu)先選取剩余能量多的節(jié)點(diǎn)成為簇頭,能量比例參數(shù)如公式(17)所示:

(17)

LEACH協(xié)議中,簇頭分布不均會(huì)使成員節(jié)點(diǎn)能耗加快?？梢栽贚EACH協(xié)議閾值公式中加入節(jié)點(diǎn)度參數(shù),節(jié)點(diǎn)可以根據(jù)接收信號(hào)強(qiáng)度值,計(jì)算出節(jié)點(diǎn)間距離,從而可以確定該節(jié)點(diǎn)的度Nd,節(jié)點(diǎn)度參數(shù)如公式(18)所示:

(18)

式(18)中最合適簇頭數(shù)量為K,所有存活的節(jié)點(diǎn)數(shù)為Nr。Nd為節(jié)點(diǎn)n的節(jié)點(diǎn)度。將參數(shù)S(n)代入到T(N)公式中,對(duì)于節(jié)點(diǎn)度較小的節(jié)點(diǎn),參數(shù)S(n)也較小,降低該節(jié)點(diǎn)成為簇頭的概率,反之,概率增大。改進(jìn)后LEACH協(xié)議的T(N) 如公式(19)所示:

(19)

式(19)中τ為常量,表示能耗比例和節(jié)點(diǎn)度比例在T(N)式中占的比重。通過上面閾值T(N)計(jì)算公式,可以使節(jié)點(diǎn)的能耗更加均衡,使網(wǎng)絡(luò)生存周期得到延長(zhǎng)。

2 仿真實(shí)驗(yàn)與結(jié)果分析

使用MATLAB進(jìn)行仿真分析,實(shí)驗(yàn)仿真參數(shù)如下:監(jiān)測(cè)區(qū)域100m*100m、節(jié)點(diǎn)數(shù)100個(gè)、Sink節(jié)點(diǎn)坐標(biāo)(50,50)m、數(shù)據(jù)包長(zhǎng)度4000Bytes、初始能量0.5,Eelec為50 nJ/bit·m2,εmp為0.0013 pJ/bit·m4,εfs為10 pJ/bit·m2。經(jīng)過簇頭數(shù)最優(yōu)算法計(jì)算后得到4≤K≤5,則p的最優(yōu)值為0.04-0.05之間。這里為便于比較,將改進(jìn)后的LEACH算法稱為NEW算法,兩種算法的簇頭數(shù)都選取5個(gè),即P值為0.05。

在計(jì)算T(N)的公式中,τ的取值對(duì)實(shí)驗(yàn)結(jié)果有一定的影響,經(jīng)過綜合比較,當(dāng)τ=6時(shí),網(wǎng)絡(luò)能耗最低、網(wǎng)絡(luò)數(shù)據(jù)發(fā)送量達(dá)到最大、首個(gè)節(jié)點(diǎn)和全部節(jié)點(diǎn)死完時(shí)間最長(zhǎng)。因此選取τ=6,分別對(duì)LEACH和NEW兩種算法發(fā)送數(shù)據(jù)量、能量消耗、存活節(jié)點(diǎn)數(shù)進(jìn)行比較,仿真結(jié)果如表1所示。

表1 LEACH與改進(jìn)LEACH(NEW)數(shù)據(jù)對(duì)比表

通過仿真,在開始階段LEACH和改進(jìn)后LEACH協(xié)議能量消耗、節(jié)點(diǎn)存活和數(shù)發(fā)送量相差較小,但是在中期過后,改進(jìn)后的LEACH算法降低了網(wǎng)絡(luò)能耗,增長(zhǎng)了網(wǎng)絡(luò)存活時(shí)間,增多了發(fā)送的總數(shù)據(jù)量。

3 結(jié) 語

基于LEACH協(xié)議進(jìn)行修改,加入了簇頭數(shù)最優(yōu)算法,解決了LEACH算法中隨機(jī)選擇簇頭數(shù)問題,使能量耗費(fèi)更加均衡。并在簇頭選取算法中加入了能量因子和節(jié)點(diǎn)度因子,使剩余能量和節(jié)點(diǎn)度較大的節(jié)點(diǎn)優(yōu)先成為簇頭,并使簇頭分布更加均勻。經(jīng)過對(duì)LEACH算法的改進(jìn),使各類傳感器節(jié)點(diǎn)能量消耗更加均衡,延長(zhǎng)了網(wǎng)絡(luò)的存活時(shí)間。