基于剩余能量等級(jí)的MANET分簇算法

， ，

(1.中國(guó)電子科技集團(tuán)公司 第五十四研究所，石家莊 050081；2.中國(guó)人民解放軍第96764部隊(duì)，河南 洛陽(yáng) 471000)

0 引言

移動(dòng)自組織網(wǎng)絡(luò)(Mobile Ad Hoc Network，MANET)是一種無(wú)需依賴固有通信基礎(chǔ)設(shè)備的網(wǎng)絡(luò)，它不僅能夠?qū)崿F(xiàn)快速組網(wǎng)，還能夠通過(guò)無(wú)線終端的相互協(xié)作實(shí)現(xiàn)信息傳輸與維護(hù)。MANET具有自組織性、拓?fù)鋭?dòng)態(tài)性、多跳通信和分布式控制等特點(diǎn)[1]，實(shí)用于軍事戰(zhàn)場(chǎng)、地震、水災(zāi)后等場(chǎng)合的緊急通信。MANET研究方向主要包括方面六個(gè)方面：定位技術(shù)、節(jié)能技術(shù)、信道接入技術(shù)、路由協(xié)議、網(wǎng)絡(luò)體系結(jié)構(gòu)和網(wǎng)絡(luò)安全技術(shù)[2]。

MANET的網(wǎng)絡(luò)結(jié)構(gòu)分為平面結(jié)構(gòu)和分級(jí)結(jié)構(gòu)，分級(jí)結(jié)構(gòu)比平面結(jié)構(gòu)的可擴(kuò)展性好，路由和控制開(kāi)銷(xiāo)也相對(duì)較小，更易于實(shí)現(xiàn)網(wǎng)絡(luò)的移動(dòng)性管理和局部同步[3]。目前研究的MANET分級(jí)結(jié)構(gòu)是基于分簇實(shí)現(xiàn)的，如何設(shè)計(jì)簡(jiǎn)單高效的分簇算法來(lái)減少M(fèi)ANET的路由和計(jì)算開(kāi)銷(xiāo)，提高簇間通信效率是MANET研究的一個(gè)重要方向。典型分簇算法包括最小ID算法、最大連接度算法、最低移動(dòng)性算法和加權(quán)分簇算法[4]。由于現(xiàn)有自組織網(wǎng)絡(luò)設(shè)備采用手持或者背負(fù)的攜帶方式，能源通常會(huì)受到限制，然而傳統(tǒng)算法沒(méi)有考慮能量消耗的因素。為了實(shí)現(xiàn)節(jié)能延長(zhǎng)網(wǎng)絡(luò)壽命，節(jié)點(diǎn)剩余能量逐漸成為分簇算法考慮的重要因素。文獻(xiàn)[5]提出了一種基于局部競(jìng)爭(zhēng)和雙權(quán)重通信能量開(kāi)銷(xiāo)的分簇算法，有效延長(zhǎng)網(wǎng)絡(luò)穩(wěn)定工作壽命，提高網(wǎng)絡(luò)節(jié)點(diǎn)能量使用效率。文獻(xiàn)[6]分別建立能量和密度的影響因子，并加上不同的權(quán)重，讓剩余能量多、密度大的節(jié)點(diǎn)當(dāng)簇首，均衡網(wǎng)絡(luò)能耗，有效延長(zhǎng)網(wǎng)絡(luò)壽命。文獻(xiàn)[7]分別考慮了單跳和多跳網(wǎng)絡(luò)，改進(jìn)了現(xiàn)有的分簇算法，在均衡節(jié)點(diǎn)能耗的同時(shí)，提高網(wǎng)絡(luò)的能效和延長(zhǎng)網(wǎng)絡(luò)壽命。

本文主要針對(duì)手持型自組織網(wǎng)絡(luò)的節(jié)點(diǎn)能源受限、快速移動(dòng)以及網(wǎng)絡(luò)變化隨機(jī)性強(qiáng)的特點(diǎn)，研究出一種基于節(jié)點(diǎn)剩余能量的分簇算法。根據(jù)節(jié)點(diǎn)位置信息進(jìn)行自適應(yīng)分簇，建立節(jié)點(diǎn)能量等級(jí)模型選取最優(yōu)簇頭，動(dòng)態(tài)構(gòu)造分級(jí)結(jié)構(gòu)的自組織網(wǎng)絡(luò)，從而達(dá)到延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間和平衡簇頭負(fù)載的目的。

1 MANET網(wǎng)絡(luò)結(jié)構(gòu)

MANET拓?fù)浣Y(jié)構(gòu)可分為平面結(jié)構(gòu)和分級(jí)結(jié)構(gòu)。圖1(a)所示的為MANET的平面結(jié)構(gòu)，網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的功能和地位相等，網(wǎng)絡(luò)結(jié)構(gòu)具有較強(qiáng)的健壯性。但是由于在大規(guī)模組網(wǎng)和節(jié)點(diǎn)移動(dòng)性強(qiáng)的網(wǎng)絡(luò)中，平面結(jié)構(gòu)網(wǎng)絡(luò)的時(shí)延長(zhǎng)、路由維護(hù)和管理開(kāi)銷(xiāo)大，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增加，吞吐量也會(huì)急劇下降，所以它只適用于移動(dòng)性低的中小型網(wǎng)絡(luò)。

MANET的分級(jí)結(jié)構(gòu)如圖1(b)所示，此結(jié)構(gòu)是將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行分簇，將位置比較近的幾個(gè)節(jié)點(diǎn)，按照某種算法合并成一個(gè)簇，從而將整個(gè)網(wǎng)絡(luò)分成若干個(gè)簇。在每個(gè)簇中使用簇頭對(duì)簇內(nèi)的節(jié)點(diǎn)進(jìn)行集中化管理。同時(shí)處于多個(gè)簇頭節(jié)點(diǎn)覆蓋范圍內(nèi)的節(jié)點(diǎn)叫做網(wǎng)關(guān)節(jié)點(diǎn)，或者跨簇節(jié)點(diǎn)[8]。分簇結(jié)構(gòu)的優(yōu)勢(shì)是可擴(kuò)展性好，網(wǎng)絡(luò)規(guī)模不受限制，而且路由和控制開(kāi)銷(xiāo)較小，易于實(shí)現(xiàn)移動(dòng)性管理和網(wǎng)絡(luò)的局部同步；劣勢(shì)是簇頭節(jié)點(diǎn)消耗能量大，容易成為網(wǎng)絡(luò)生存的瓶頸，而且分簇結(jié)構(gòu)的安全性較差。

圖1 MANET網(wǎng)絡(luò)結(jié)構(gòu)

1.1 簇頭功能

簇頭主要負(fù)責(zé)管理和維護(hù)簇結(jié)構(gòu)與節(jié)點(diǎn)信息，轉(zhuǎn)發(fā)簇成員之間的數(shù)據(jù)[9]。簇頭是每個(gè)簇的管理者，一般用作網(wǎng)絡(luò)的管理與調(diào)度。簇頭可以預(yù)先設(shè)定，也可以根據(jù)預(yù)設(shè)的優(yōu)先級(jí)自動(dòng)產(chǎn)生。當(dāng)簇內(nèi)的節(jié)點(diǎn)同時(shí)處于多個(gè)簇頭的覆蓋范圍內(nèi)時(shí)，某一時(shí)刻只能屬于一個(gè)簇。

1.2 性能評(píng)價(jià)

分簇算法的性能優(yōu)劣可以從以下幾個(gè)方面做出評(píng)價(jià)。

1.1.1 簇個(gè)數(shù)

MANET中的簇個(gè)數(shù)較多或者較少時(shí)，分簇算法性能都會(huì)下將。簇個(gè)數(shù)多會(huì)增加端到端時(shí)延，簇個(gè)數(shù)少會(huì)導(dǎo)致簇內(nèi)平均普通節(jié)點(diǎn)數(shù)目增多，吞吐率下降。

1.1.2 穩(wěn)定性

MANET中節(jié)點(diǎn)的移動(dòng)會(huì)導(dǎo)致簇中節(jié)點(diǎn)的離開(kāi)與新節(jié)點(diǎn)的加入，從而會(huì)引起簇結(jié)構(gòu)的變化。可以通過(guò)增強(qiáng)簇結(jié)構(gòu)的穩(wěn)定性，使分簇算法性能更好。

1.1.3 負(fù)載均衡度

簇頭因?yàn)橐S護(hù)簇的拓?fù)浣Y(jié)構(gòu)，能量消耗會(huì)遠(yuǎn)遠(yuǎn)大于簇其它節(jié)點(diǎn)。通過(guò)式(1)計(jì)算LBF值得到簇首的負(fù)載均衡度[10]。

(1)

式中，n表示簇首的數(shù)目，xi表示簇首節(jié)點(diǎn)i的成員節(jié)點(diǎn)數(shù)，u表示所有簇首節(jié)點(diǎn)的平均成員節(jié)點(diǎn)數(shù)，N表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)數(shù)目，LBF值是xi到xn方差的倒數(shù)，LBF值越大說(shuō)明分簇算法的負(fù)載越均衡。

1.1.4 節(jié)能能力

MANET要充分利用現(xiàn)有的能源，降低簇的能量消耗，延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。

2 MANET節(jié)點(diǎn)能量等級(jí)模型

為實(shí)現(xiàn)對(duì)節(jié)點(diǎn)剩余能量的評(píng)估，建立能量級(jí)別評(píng)估模型。設(shè)節(jié)點(diǎn)i接收數(shù)據(jù)功率為P1，發(fā)送數(shù)據(jù)功率為P2；接收數(shù)據(jù)分組時(shí)長(zhǎng)為T(mén)1，發(fā)送數(shù)據(jù)分組時(shí)長(zhǎng)為T(mén)2；接收數(shù)據(jù)分組包長(zhǎng)為L(zhǎng)1，發(fā)送數(shù)據(jù)分組包長(zhǎng)L2；數(shù)據(jù)接收速率為V1，數(shù)據(jù)發(fā)送速率為V2，則可以將節(jié)點(diǎn)消耗能量Ei用以下的計(jì)算公式[11]表示：

Ei=P1T1+P2T2=P1L1/V1+P2L2/V2

(2)

當(dāng)初始能量為E0時(shí)，則節(jié)點(diǎn)的剩余能量表示為：

Er=E0-Ei

(3)

由于簇首節(jié)點(diǎn)比普通節(jié)點(diǎn)消耗的能量要高，因此每輪要選擇剩余能量相對(duì)較高的節(jié)點(diǎn)擔(dān)當(dāng)簇頭。為衡量每個(gè)節(jié)點(diǎn)剩余能量在子網(wǎng)絡(luò)中所有節(jié)點(diǎn)能量的相對(duì)水平，引入?yún)⒘喀吮硎竟?jié)點(diǎn)剩余能量的級(jí)別：

(4)

在上式(4)中，E(i,t)表示i節(jié)點(diǎn)第t次簇頭選擇時(shí)的剩余能量，Eave(t)表示簇內(nèi)存活節(jié)點(diǎn)的平均能量。舍去λ<1的節(jié)點(diǎn)，將剩余的節(jié)點(diǎn)設(shè)為4個(gè)等級(jí)，如表1所示。

表1 剩余能量級(jí)別

3 MANET分簇設(shè)計(jì)

3.1 自適應(yīng)分簇

自適應(yīng)分簇過(guò)程是將整個(gè)網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域內(nèi)的所有節(jié)點(diǎn)按照一定原則，劃分為若干個(gè)子區(qū)域，每個(gè)子區(qū)域中的節(jié)點(diǎn)組成一簇。自適應(yīng)分簇過(guò)程可以根據(jù)設(shè)定的子區(qū)域的節(jié)點(diǎn)密度范圍，不斷調(diào)整每個(gè)子區(qū)域內(nèi)節(jié)點(diǎn)規(guī)模，實(shí)現(xiàn)每個(gè)簇的均勻分布，避免部分節(jié)點(diǎn)的能量消耗過(guò)快。圖2為某個(gè)監(jiān)測(cè)區(qū)內(nèi)節(jié)點(diǎn)的分布圖，當(dāng)單個(gè)子區(qū)域內(nèi)節(jié)點(diǎn)密度過(guò)大時(shí)，可以通過(guò)細(xì)化方式組成新的簇，如圖3所示。

圖2 節(jié)點(diǎn)分布圖

圖3 區(qū)域細(xì)化

自適應(yīng)分簇具體過(guò)程如下：第一步將監(jiān)測(cè)區(qū)域分成4個(gè)相等的子區(qū)域，根據(jù)每個(gè)子區(qū)域內(nèi)節(jié)點(diǎn)數(shù)，計(jì)算出LBF值；第二部開(kāi)始細(xì)化節(jié)點(diǎn)數(shù)較多的子區(qū)域，設(shè)第t輪的子區(qū)域個(gè)數(shù)為L(zhǎng)t，第i個(gè)子區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)為Ni；每輪設(shè)定子區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)上限值Nmax，當(dāng)Ni≥Nmax時(shí)將該區(qū)域一分為二，按照基數(shù)輪豎向分、偶數(shù)輪橫向分的順序依次從左到右，從上向下的順序直至所有區(qū)域滿足Ni≤Nmax。求出每次細(xì)化后的LBF值，選擇最大時(shí)的分簇方法作為最終的分簇方案。

3.2 簇頭選擇

確定簇?cái)?shù)目和各個(gè)簇的規(guī)模后，就需要進(jìn)行簇頭選擇過(guò)程。以某個(gè)簇為例，首先根據(jù)剩余能量等級(jí)模型，計(jì)算出子區(qū)域內(nèi)網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量和平均剩余能量。通過(guò)比較各自的能量等級(jí)，選出具有最高等級(jí)的節(jié)點(diǎn)最為簇頭。如果處于最高等級(jí)的節(jié)點(diǎn)不會(huì)是一個(gè)，需要再通過(guò)比較這些節(jié)點(diǎn)在子區(qū)域內(nèi)到達(dá)最遠(yuǎn)節(jié)點(diǎn)的跳數(shù)，選取跳數(shù)最小的節(jié)點(diǎn)作為簇頭，既可以保障網(wǎng)絡(luò)的穩(wěn)定性，同時(shí)又考慮了拓?fù)浣Y(jié)構(gòu)。

圖4 簇頭選擇流程圖

3.3 簇維護(hù)

簇頭選擇完成后，隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)能量在不斷消耗，需要定期對(duì)簇頭進(jìn)行維護(hù)。

圖5 簇維護(hù)流程圖

由于位置的移動(dòng)，節(jié)點(diǎn)離開(kāi)了原來(lái)簇頭的覆蓋區(qū)域進(jìn)入其他簇頭覆蓋的區(qū)域，將重新發(fā)起簇頭選擇過(guò)程。如果是兩個(gè)簇頭節(jié)點(diǎn)移動(dòng)到對(duì)方的覆蓋區(qū)域時(shí)，具有較低能量等級(jí)的簇頭將成為具有高能量簇頭的節(jié)點(diǎn)成員。當(dāng)通過(guò)對(duì)能量的計(jì)算，如果原簇頭能量低于本輪最高節(jié)點(diǎn)剩余能量等級(jí)兩級(jí)時(shí)，需要重新發(fā)起簇頭選擇過(guò)程。

此算法的優(yōu)勢(shì)為可以選擇最優(yōu)的簇個(gè)數(shù)，在保障簇內(nèi)的吞吐量時(shí)，盡量減少端到端的時(shí)延。由于考慮了節(jié)點(diǎn)的剩余能量，能夠避免個(gè)別節(jié)點(diǎn)過(guò)度消耗能量，平衡簇首節(jié)點(diǎn)的負(fù)載。在簇頭剩余能量等級(jí)相差兩級(jí)及以上時(shí)才進(jìn)行簇頭重選，適當(dāng)避免了簇頭的頻繁更換，保障了網(wǎng)絡(luò)的穩(wěn)定性。

3.4 網(wǎng)關(guān)選擇

當(dāng)兩個(gè)節(jié)點(diǎn)處于同一個(gè)簇時(shí)，可以通過(guò)簇頭轉(zhuǎn)發(fā)實(shí)現(xiàn)通信；屬于不同簇時(shí)需要通過(guò)簇頭和網(wǎng)關(guān)節(jié)點(diǎn)中繼通信。網(wǎng)關(guān)節(jié)點(diǎn)選取的主要方向：保障跨簇通信時(shí)延的同時(shí)提高通信的穩(wěn)定性。現(xiàn)有的網(wǎng)關(guān)選擇方法包括隨機(jī)算法、最大連接度算法、最小ID優(yōu)先算法以及鏈路穩(wěn)定優(yōu)先算法等[12]，各有優(yōu)勢(shì)卻難以避免節(jié)點(diǎn)移動(dòng)引起的網(wǎng)關(guān)節(jié)點(diǎn)頻繁更換。因此選擇連接度大且運(yùn)動(dòng)范圍較小的節(jié)點(diǎn)最為網(wǎng)關(guān)。

4 仿真計(jì)算與分析

Opnet仿真工具是一種網(wǎng)絡(luò)仿真技術(shù)軟件包，能夠準(zhǔn)確的分析復(fù)雜網(wǎng)絡(luò)的性能，在1986年被首次創(chuàng)建后很快應(yīng)用于各種領(lǐng)域[13]。本文采用Opnet網(wǎng)絡(luò)仿真工具對(duì)設(shè)計(jì)的分簇算法進(jìn)行仿真，并利用Matlab軟件對(duì)其性能進(jìn)行分析。

4.1 分簇過(guò)程

運(yùn)用opnet軟件，設(shè)定節(jié)點(diǎn)數(shù)目為40個(gè)，實(shí)驗(yàn)區(qū)域設(shè)定為10 km*10 km的方形區(qū)域，將40個(gè)節(jié)點(diǎn)隨機(jī)分布在目標(biāo)區(qū)域，如圖6所示。

圖6 節(jié)點(diǎn)分布圖

首先將目標(biāo)區(qū)域分成四個(gè)子區(qū)域，每個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)目分別為12、8、6和14。根據(jù)自適應(yīng)分簇過(guò)程，求出不同簇?cái)?shù)目時(shí)的LBF值如表2所示。經(jīng)過(guò)比較10個(gè)簇時(shí)LBF值最大，分簇性能最好。

表2 不同簇?cái)?shù)的LBF值

當(dāng)簇個(gè)數(shù)為10時(shí)，根據(jù)自適應(yīng)分簇算法對(duì)目標(biāo)區(qū)域的節(jié)點(diǎn)進(jìn)行細(xì)化，得到40節(jié)點(diǎn)的各個(gè)簇中的節(jié)點(diǎn)數(shù)目。

4.2 端到端時(shí)延

影響網(wǎng)絡(luò)時(shí)延性能的參數(shù)包括網(wǎng)絡(luò)的規(guī)模、網(wǎng)絡(luò)中的簇首節(jié)點(diǎn)個(gè)數(shù)、簇內(nèi)成員節(jié)點(diǎn)的傳輸能力與傳輸范圍、簇首節(jié)點(diǎn)的傳輸能力和傳輸范圍、數(shù)據(jù)包的長(zhǎng)度與數(shù)據(jù)包的到達(dá)率、節(jié)點(diǎn)的干擾模型和MAC層協(xié)議[14]。

運(yùn)用opnet軟件對(duì)網(wǎng)絡(luò)進(jìn)行仿真，網(wǎng)絡(luò)中的節(jié)點(diǎn)分布如圖7所示，設(shè)置傳輸功率為0.4 mW，節(jié)點(diǎn)數(shù)據(jù)包發(fā)送到達(dá)符合0.2秒的指數(shù)分布，數(shù)據(jù)包長(zhǎng)度為1024字節(jié)，傳輸速率為1 Mbit/s。路由協(xié)議選擇AODV協(xié)議，MAC層協(xié)議選擇CSMA/CA協(xié)議。圖8為總節(jié)點(diǎn)數(shù)為40個(gè)時(shí)，分別比較簇個(gè)數(shù)分別為6、8、10、12時(shí)端到端時(shí)延。由圖8可知，當(dāng)簇頭數(shù)目為10個(gè)時(shí)端到端時(shí)延最小，同分簇過(guò)程得出的結(jié)果一致。

圖7 不同簇?cái)?shù)的端到端時(shí)延

4.3 節(jié)點(diǎn)生存時(shí)間

仿真環(huán)境與參數(shù)設(shè)置如下：設(shè)節(jié)點(diǎn)原始能量隨機(jī)處于0.8到1.0 J之間某值，每輪簇頭消耗的能量為0.001～0.002 J隨機(jī)數(shù)，普通節(jié)點(diǎn)消耗能量為0.0001～0.0002 J隨機(jī)數(shù)，節(jié)點(diǎn)總數(shù)為100個(gè)。

實(shí)驗(yàn)一：參加對(duì)比的三種簇頭選擇方式分別為指定簇頭方式、能量較低時(shí)隨機(jī)選擇其余節(jié)點(diǎn)作為簇頭的方式以及本文設(shè)計(jì)的基于剩余能量等級(jí)的簇頭選擇方式。通過(guò)比較三種方式下每輪簇頭的剩余能量值，反映出網(wǎng)絡(luò)節(jié)點(diǎn)的生存時(shí)間。

圖8 剩余能量變化圖

由圖8可知，指定簇頭方式在第918輪指定簇頭就會(huì)死亡；輪換簇頭方式在第5680輪出現(xiàn)節(jié)點(diǎn)死亡；基于剩余能量等級(jí)分配簇頭的方式在7640輪才會(huì)出現(xiàn)有節(jié)點(diǎn)死亡。因此本文設(shè)計(jì)的方法對(duì)網(wǎng)絡(luò)生存時(shí)間相比其他方法有很大延長(zhǎng)。

實(shí)驗(yàn)二：比較上述三種方式下100個(gè)節(jié)點(diǎn)，每輪剩余能量方差變化，可以反映出每輪節(jié)點(diǎn)的剩余能量消耗的整體趨向。

圖9 每輪節(jié)點(diǎn)剩余能量值方差變化

通過(guò)比較在3000輪過(guò)程中剩余能量值得方差變化得出，輪換選擇節(jié)點(diǎn)作為簇頭的方式和本文設(shè)計(jì)的分簇算法都可以均衡節(jié)點(diǎn)的能量損耗，達(dá)到均衡網(wǎng)絡(luò)能量的目的，然而本文設(shè)計(jì)自適的方法更為優(yōu)越。

5 總結(jié)

本文提出一種自適應(yīng)分簇算法，根據(jù)節(jié)點(diǎn)位置劃分網(wǎng)格，通過(guò)計(jì)算不同簇?cái)?shù)目下LBF值，得到最合理的分簇結(jié)構(gòu)。通過(guò)對(duì)指定簇頭、輪換簇頭和自適應(yīng)分簇三種算法下的100個(gè)節(jié)點(diǎn)時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)生存時(shí)間和每輪節(jié)點(diǎn)的能量方差進(jìn)行仿真，得出自適應(yīng)分簇算法可以明顯將網(wǎng)絡(luò)生存時(shí)間延長(zhǎng)，并平衡簇頭的負(fù)載。