糜 昊

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

0 引 言

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

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

(1)

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

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

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

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

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

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

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

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

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

1 LEACH-N算法

1.1 改進方案

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

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

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

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

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

1.2 能耗模型

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

(2)

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

ERx=l×Eelec

(3)

表1 模擬參數(shù)

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

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

節(jié)點到簇頭的傳輸過程的能耗分析：S/C是每個集群的平均面積，讓S/C=πd12，其中d1是成員節(jié)點和簇頭之間的平均距離。在此過程中，發(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)

所以此過程的平均能耗為式(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)

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

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

(8)

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

(9)

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

2 實驗結果與分析

2.1 仿真環(huán)境

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

2.2 不同傳輸距離時的結果分析

2.2.1 傳輸距離d

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

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

表2 1 000輪時節(jié)點殘余能量

2.2.2 傳輸距離d>d0

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

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

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

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

3 結束語

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