基于最優(yōu)簇頭數(shù)和三段路由的改進(jìn)型LEACH算法

糜 昊

(山西師范大學(xué) 物理與信息工程學(xué)院，山西 臨汾 041004)

0 引 言

許多廉價(jià)的微傳感器節(jié)點(diǎn)被放置在指定的監(jiān)控區(qū)域，通過(guò)無(wú)線通信以多跳的方式自發(fā)地形成無(wú)線傳感器網(wǎng)絡(luò)(WSN)[1]。作為一個(gè)新平臺(tái)，WSN被廣泛應(yīng)用于數(shù)據(jù)傳輸、采集和處理[2]。能夠?qū)崟r(shí)監(jiān)測(cè)和收集指定區(qū)域內(nèi)被監(jiān)測(cè)對(duì)象的各種數(shù)據(jù)信息，如溫度、濕度、聲音、壓力、物體位置或化學(xué)濃度等，然后對(duì)收集的信息進(jìn)行處理并傳送至基站(BS)[3]。這可實(shí)現(xiàn)對(duì)傳感器節(jié)點(diǎn)的實(shí)時(shí)檢測(cè)、跟蹤和遙控。由于硬件和物聯(lián)網(wǎng)的發(fā)展[4]以及監(jiān)測(cè)區(qū)域存在不確定性，WSN會(huì)應(yīng)用于環(huán)境傳感、軍事監(jiān)視、國(guó)土防御和其它特殊情況[5]。通常，由傳感器節(jié)點(diǎn)配置的電池能量有限，不能充電或更換[6]，而能耗又決定了網(wǎng)絡(luò)的壽命和價(jià)值。因此，在設(shè)計(jì)路由協(xié)議時(shí)，必須非常注意能耗問(wèn)題。

LEACH(Low-Energy Adaptive Clustering Hierarchy)是一種流行的分簇路由協(xié)議，該協(xié)議周期性地執(zhí)行集群的建立階段和數(shù)據(jù)的傳輸階段，并且一個(gè)循環(huán)可以用輪的概念來(lái)描述[7]。在集群的建立階段，每個(gè)節(jié)點(diǎn)隨機(jī)生成一個(gè)介于0～1之間的數(shù)字，如果生成的隨機(jī)數(shù)小于閾值T(n)，其幸運(yùn)地會(huì)成為簇頭，并廣播其為簇頭的消息[8]。閾值T(n)定義，式(1)如下：

(1)

其中，p是成為簇頭的預(yù)期概率；r是當(dāng)前輪；r*mod(1/p)表示這輪中選為簇頭的節(jié)點(diǎn)數(shù)；G是最近1/p輪中未選為簇頭的節(jié)點(diǎn)集[9]。

在接收到消息后，其它節(jié)點(diǎn)選擇加入離其最近的集群并成為集群內(nèi)的成員。該協(xié)議隨機(jī)選舉簇頭，并不斷循環(huán)集群重建過(guò)程。同一輪中的傳感器節(jié)點(diǎn)不允許重復(fù)被選舉，并且所有節(jié)點(diǎn)成為簇頭的可能性相同。在數(shù)據(jù)傳輸階段，集群成員將收集到的數(shù)據(jù)傳輸?shù)酱仡^，由其接收并融合數(shù)據(jù)，最后將其發(fā)送到基站[10]。LEACH協(xié)議的數(shù)據(jù)路由如圖1所示。

圖1 LEACH協(xié)議的數(shù)據(jù)路由

雖然LEACH協(xié)議非常流行并被廣泛使用，但仍存在一些缺點(diǎn)：

(1)LEACH很難確定最優(yōu)的p值[11]。當(dāng)p太小時(shí)，傳感器網(wǎng)絡(luò)只能選舉數(shù)目很少的簇頭，增加了集群內(nèi)的傳輸距離，從而增加集群內(nèi)傳輸能耗；當(dāng)p太大時(shí)，會(huì)產(chǎn)生多余的簇頭，增加數(shù)據(jù)傳輸?shù)交镜哪芎摹?/p>

(2)LEACH規(guī)定簇頭以單跳模式與基站通信[12]。當(dāng)傳輸距離超過(guò)一個(gè)閾值時(shí)，能量將由2次方衰減變?yōu)?次方衰減，能耗巨大，網(wǎng)絡(luò)壽命急劇下降。

(3)LEACH忽略殘余能量對(duì)簇頭選舉的影響，會(huì)出現(xiàn)殘余能量低的節(jié)點(diǎn)選為簇頭，不利于能量均衡消耗[12]。

本文主要針對(duì)以上3個(gè)缺陷對(duì)LEACH協(xié)議進(jìn)行改進(jìn)，提出基于最優(yōu)簇頭數(shù)和三段路由的改進(jìn)型LEACH算法，將其命名為L(zhǎng)EACH-N。該算法刪除了LEACH協(xié)議中的p和簇頭選舉的閾值公式，避免了簇頭的隨機(jī)性。首先，依據(jù)網(wǎng)絡(luò)區(qū)域的節(jié)點(diǎn)總數(shù)計(jì)算出理論上的最優(yōu)簇頭數(shù)，并按照殘余能量由高到低進(jìn)行選舉，保證了每一輪的網(wǎng)絡(luò)節(jié)點(diǎn)能耗的均衡性[13]，完全避免了殘余能量低的節(jié)點(diǎn)被選舉為簇頭；其次，集群內(nèi)傳輸后簇頭殘余能量最高的成為高層簇頭，接收和融合其余普通簇頭的數(shù)據(jù)包最后傳至基站，形成節(jié)點(diǎn)—簇頭—高層簇頭—基站的三段數(shù)據(jù)路由，實(shí)現(xiàn)了用相對(duì)較低的能量傳輸整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)包。本算法應(yīng)用在基站位于傳感器區(qū)域中心或距離區(qū)域較近的網(wǎng)絡(luò)時(shí)，可以最大限度的推遲首節(jié)點(diǎn)死亡時(shí)間，提高信息傳輸量；應(yīng)用在基站距離傳感器區(qū)域很遠(yuǎn)的網(wǎng)絡(luò)時(shí)，可以大幅延長(zhǎng)網(wǎng)絡(luò)壽命、提高傳輸量。

下面這些詞和固定短語(yǔ)的情況又有點(diǎn)兒不同,但也都屬于借代造詞。詞本身都是借體,所包含的詞義部分也都是被代替的本體。

1 LEACH-N算法

1.1 改進(jìn)方案

首先，LEACH中簇頭不僅接收和融合集群中所有節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)，還繼續(xù)將數(shù)據(jù)包發(fā)送到遠(yuǎn)處的基站，因此比普通集群成員節(jié)點(diǎn)的能耗負(fù)擔(dān)更大。此外，殘余能量非常低的傳感器節(jié)點(diǎn)也具有與其它節(jié)點(diǎn)相同的概率成為簇頭，這可能直接加速其死亡。如果這種情況頻繁發(fā)生，那么WSN中幸存的傳感器節(jié)點(diǎn)的數(shù)量將會(huì)迅速減少，導(dǎo)致網(wǎng)絡(luò)壽命縮短。同領(lǐng)域的其它學(xué)者也發(fā)現(xiàn)了這個(gè)問(wèn)題并改進(jìn)了閾值公式，例如Kim、Yong、Min等人在公式中引入節(jié)點(diǎn)的剩余能量來(lái)增加高能量節(jié)點(diǎn)選舉的概率，但其不能完全避免殘余能量低的節(jié)點(diǎn)成為簇頭[12]。因此，LEACH-N首先取消了p值和閾值公式，依據(jù)網(wǎng)絡(luò)區(qū)域中節(jié)點(diǎn)的數(shù)目計(jì)算出理論上最優(yōu)的簇頭數(shù)；在每一輪中，選擇高殘余能量的節(jié)點(diǎn)為簇頭。網(wǎng)絡(luò)區(qū)域中的簇頭數(shù)量保持恒定，在一定程度上可以避免隨機(jī)性造成的能量浪費(fèi)。本算法中如果節(jié)點(diǎn)的殘余能量相對(duì)較低，那么其必須作為集群的成員節(jié)點(diǎn)，所以其只需要消耗更低的能量完成集群內(nèi)通信來(lái)確保其生存。這種基于最優(yōu)簇頭數(shù)的選舉方式可以最大程度的均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗，提高信息傳輸量。

其次，簇頭傳輸數(shù)據(jù)包的能耗一定比接收和融合的能耗大。某些特殊情況下，基站與監(jiān)測(cè)區(qū)域之間的距離遠(yuǎn)大于該區(qū)域的跨度，此時(shí)能量以4次方衰減。為了降低這部分的能耗，本文選舉出高層簇頭，形成節(jié)點(diǎn)—簇頭—高層簇頭—基站的三段數(shù)據(jù)路由，避免所有簇頭和基站之間的直接通信，如圖2所示。這種基于三段路由的傳輸可以適用于傳感器網(wǎng)絡(luò)距離節(jié)點(diǎn)區(qū)域遙遠(yuǎn)的情形，延長(zhǎng)網(wǎng)絡(luò)壽命。

圖2 LEACH-N算法的數(shù)據(jù)路由

綜合上述兩點(diǎn)，本文提出基于最優(yōu)簇頭數(shù)和三段路由的改進(jìn)型LEACH算法(LEACH-N)，在算法開(kāi)始時(shí)，根據(jù)設(shè)定的參數(shù)值進(jìn)行初始化。該算法預(yù)先計(jì)算理論上最優(yōu)的簇頭數(shù)量，然后是選舉過(guò)程。幸存的節(jié)點(diǎn)根據(jù)從最高到最低的殘余能量排序，序列號(hào)小于或等于理論上最優(yōu)數(shù)目的節(jié)點(diǎn)將成為簇頭。在其它節(jié)點(diǎn)加入集群后，根據(jù)分配的時(shí)間隙發(fā)送數(shù)據(jù)包，由簇頭接收、融合，將剩余能量最高的選為高層簇頭，完成到基站的數(shù)據(jù)傳輸。LEACH-N算法的程序流程圖如圖3所示。

圖3 LEACH-N算法程序流程圖

1.2 能耗模型

該算法采用了與LEACH協(xié)議相同的能耗模型，以更清晰地驗(yàn)證其性能。發(fā)射機(jī)發(fā)送l位數(shù)據(jù)所消耗的能量為式(2)：

(2)

接收機(jī)需要消耗能量來(lái)接收l(shuí)位數(shù)據(jù)，能量計(jì)算為式(3)：

ERx=l×Eelec

(3)

表1 模擬參數(shù)

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

LEACH-N中的簇頭數(shù)是一個(gè)常量，但精確計(jì)算最優(yōu)數(shù)并不容易，因?yàn)閷?shí)際上傳感器節(jié)點(diǎn)是被隨機(jī)放置在監(jiān)測(cè)區(qū)域內(nèi)的。為了便于計(jì)算，希望節(jié)點(diǎn)在該區(qū)域內(nèi)盡可能均勻地分布。使用N表示傳感器節(jié)點(diǎn)的數(shù)量；C表示簇頭的數(shù)量；S表示監(jiān)測(cè)區(qū)域的面積。集群之間的距離小于d0，將自由空間模型用于集群內(nèi)信息傳輸。

節(jié)點(diǎn)到簇頭的傳輸過(guò)程的能耗分析：S/C是每個(gè)集群的平均面積，讓S/C=πd12，其中d1是成員節(jié)點(diǎn)和簇頭之間的平均距離。在此過(guò)程中，發(fā)送數(shù)據(jù)的平均能耗為式(4)：

Es=(N-C)×l×Eelec+(N-C)×l×εfs×d12

(4)

接收和融合數(shù)據(jù)的平均能耗為式(5)：

Er=(N-C)×l×(Eelec+EDA)

(5)

所以此過(guò)程的平均能耗為式(6)：

E1=(N-C)×l×(2Eelec+EDA)+(N-C)×

l×εfs×d12

(6)

E2=(C-1)×l×(2Eelec+EDA)+(C-1)×

l×εfs×d22

(7)

將以上兩個(gè)過(guò)程的能耗相加得到一輪的總平均能耗為式(8)：

Etotal=(N-1)×l×(2Eelec+EDA)-l×εfs×

(8)

只有當(dāng)N/C+C/1為最小值時(shí)，能量才可以最有效的被利用。根據(jù)二元基本不等式，當(dāng)N/C=C/1時(shí)，達(dá)到最小值。最后計(jì)算得最優(yōu)簇頭數(shù)為式(9)：

(9)

這在理論上是一個(gè)最優(yōu)值，而且WSN的狀態(tài)越接近理想，其就越接近真實(shí)的最優(yōu)值。此外，需要指出的是，該數(shù)學(xué)建模并沒(méi)有考慮到高層簇頭向基站發(fā)送信息的能耗，因?yàn)闊o(wú)論監(jiān)測(cè)區(qū)域中的哪個(gè)節(jié)點(diǎn)成為高層簇頭，與節(jié)點(diǎn)到基站之間的距離相比，節(jié)點(diǎn)之間的距離忽略不計(jì)以簡(jiǎn)便計(jì)算。

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

2.1 仿真環(huán)境

本文使用LEACH算法作為L(zhǎng)EACH-N算法的比較，仿真工具為MATLAB。模擬系統(tǒng)的主要參數(shù)設(shè)置見(jiàn)表1。其他參數(shù)設(shè)置如下：傳感器節(jié)點(diǎn)總數(shù)為100，分布在100×100 m的區(qū)域中，區(qū)域4個(gè)頂點(diǎn)坐標(biāo)分別為(0,0)、(0,100)、(100,0)和(100,100)，閾值距離d0=87.7 m，LEACH算法中使用的p值為0.05。經(jīng)計(jì)算該傳感器網(wǎng)絡(luò)區(qū)域的最優(yōu)簇頭數(shù)為10。

2.2 不同傳輸距離時(shí)的結(jié)果分析

2.2.1 傳輸距離d

傳輸距離為60 m時(shí)，兩種算法存活節(jié)點(diǎn)數(shù)和數(shù)據(jù)包傳輸量隨時(shí)間的變化如圖4所示。可看出雖然此時(shí)LEACH-N算法在網(wǎng)絡(luò)壽命方面不如LEACH，但是其使得首節(jié)點(diǎn)死亡時(shí)間落后于LEACH，提高了信息傳輸量。首節(jié)點(diǎn)死亡時(shí)間與所有節(jié)點(diǎn)殘余能量有關(guān)，故隨機(jī)選取了網(wǎng)絡(luò)中的10個(gè)節(jié)點(diǎn)，將其在1 000輪時(shí)的殘余能量記錄在了表2中。從10組結(jié)果中可看出使用LEACH的傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)之間殘余能量相差較大，如4號(hào)和9號(hào)之間相差值達(dá)到了0.109 4 J，能量利用很不均衡。而使用LEACH-N算法的傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)殘余能量全部為0.274J左右，相差最大值僅僅為0.001 1 J，均衡性明顯提高，所有節(jié)點(diǎn)幾乎是同時(shí)死亡，這保證了網(wǎng)絡(luò)在存活期間始終以恒定的信息傳輸速率工作，故信息傳輸量可達(dá)最大。

圖4 距離60 m時(shí)網(wǎng)絡(luò)壽命和數(shù)據(jù)包傳輸量的對(duì)比

表2 1 000輪時(shí)節(jié)點(diǎn)殘余能量

2.2.2 傳輸距離d>d0

能耗隨著距離增加呈4次方衰減，實(shí)驗(yàn)分別測(cè)試了當(dāng)距離為100，150，200，250和300 m時(shí)的網(wǎng)絡(luò)壽命和信息傳輸量，結(jié)果見(jiàn)表3、表4。可以看出，隨著距離逐漸增加，LEACH-N的提高率越來(lái)越大。相比LEACH協(xié)議，當(dāng)基站距離最近的傳感器節(jié)點(diǎn)300 m時(shí)，網(wǎng)絡(luò)壽命延長(zhǎng)了285.1%，信息傳輸量提高了336.5%，優(yōu)勢(shì)明顯。距離300 m時(shí)兩種算法存活節(jié)點(diǎn)數(shù)和數(shù)據(jù)包傳輸量隨時(shí)間的變化如圖5所示。

表3 不同傳輸距離時(shí)的網(wǎng)絡(luò)壽命提高率

表4 不同傳輸距離時(shí)的數(shù)據(jù)包傳輸量提高率

圖5 距離300 m時(shí)網(wǎng)絡(luò)壽命和數(shù)據(jù)包傳輸量的對(duì)比

3 結(jié)束語(yǔ)

本文提出了一種基于最優(yōu)簇頭數(shù)和三段路由的改進(jìn)型LEACH算法。當(dāng)傳輸距離小于閾值時(shí)，雖然使用LEACH-N算法的網(wǎng)絡(luò)壽命延長(zhǎng)效果不如LEACH協(xié)議，但是選舉最優(yōu)數(shù)目的簇頭可以使網(wǎng)絡(luò)節(jié)點(diǎn)消耗能量的均衡性最強(qiáng)，推遲首節(jié)點(diǎn)死亡時(shí)間，信息傳輸量得到提高。當(dāng)傳輸距離大于閾值時(shí)，高層簇頭形成的三段路由的作用開(kāi)始體現(xiàn)，LEACH-N算法的提高效果會(huì)隨著傳輸距離的增加而愈來(lái)愈好，傳感器網(wǎng)絡(luò)壽命明顯被延長(zhǎng)，信息傳輸量也被最大化。本算法對(duì)于不同的傳輸距離均有其優(yōu)勢(shì)，可應(yīng)用于基站處于不同位置時(shí)的WSN。但是三段路由會(huì)增加網(wǎng)絡(luò)的通信延遲，故論文的未來(lái)工作將集中于尋找網(wǎng)絡(luò)壽命和通信延遲之間的平衡點(diǎn)，提升WSN的綜合性能。