基于能量模型的多權(quán)值分簇算法

韓 波，鄭 凱

(華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院，上海 200062)

0 引 言

移動(dòng)自組織網(wǎng)絡(luò)(mobile ad-hoc network，MANET)是由若干自由移動(dòng)的節(jié)點(diǎn)組成的一個(gè)多跳、自組織、無(wú)中心、臨時(shí)性的自治系統(tǒng)[1]。MANET網(wǎng)絡(luò)根據(jù)拓?fù)浣Y(jié)構(gòu)的不同分為兩類(lèi)：一類(lèi)是平面結(jié)構(gòu)，該結(jié)構(gòu)所有節(jié)點(diǎn)的地位是平等的，不同節(jié)點(diǎn)之間可存在多條路徑，但網(wǎng)絡(luò)開(kāi)銷(xiāo)會(huì)隨著節(jié)點(diǎn)數(shù)目的增加而急劇增大，所以此類(lèi)網(wǎng)絡(luò)的可擴(kuò)展性較差，適用于小規(guī)模的網(wǎng)絡(luò);另一類(lèi)是層次結(jié)構(gòu)，該結(jié)構(gòu)是由多個(gè)簇組成，節(jié)點(diǎn)被分為簇首和簇成員，簇首節(jié)點(diǎn)具有路由決策和路由轉(zhuǎn)發(fā)功能，簇成員節(jié)點(diǎn)只具備發(fā)送和接收功能。在網(wǎng)絡(luò)中引入分層結(jié)構(gòu)，將網(wǎng)絡(luò)劃分為簇，可以方便網(wǎng)絡(luò)的資源管理，靈活地分配各種資源，可擴(kuò)展性好，適用于大規(guī)模網(wǎng)絡(luò)。分簇機(jī)制減少了節(jié)點(diǎn)之間的控制信息開(kāi)銷(xiāo)和路由開(kāi)銷(xiāo)，拓?fù)浣Y(jié)構(gòu)的變化更加容易控制，降低了節(jié)點(diǎn)能量消耗，增加了網(wǎng)絡(luò)容量和生命周期[2-3]，因此逐漸成為網(wǎng)絡(luò)研究的熱點(diǎn)。

到目前為止，研究人員已經(jīng)提出了多種分簇算法，如最高節(jié)點(diǎn)度啟發(fā)式算法,該算法僅僅根據(jù)節(jié)點(diǎn)的度數(shù)選舉簇頭節(jié)點(diǎn)，算法運(yùn)行速度快，但容易導(dǎo)致單個(gè)節(jié)點(diǎn)負(fù)擔(dān)過(guò)重，減少了簇的生存時(shí)間。加權(quán)分簇算法WCA[4]，考慮節(jié)點(diǎn)的度數(shù)、節(jié)點(diǎn)移動(dòng)性等因素，選擇較優(yōu)的節(jié)點(diǎn)擔(dān)任簇頭，增加了網(wǎng)絡(luò)的穩(wěn)定性，但節(jié)點(diǎn)的計(jì)算復(fù)雜，影響了分簇速度，未考慮簇頭節(jié)點(diǎn)數(shù)量的最小化原則，降低了網(wǎng)絡(luò)的收斂時(shí)間。S-LEACH算法[5]在簇形成階段采用分布式協(xié)商策略，在簇維護(hù)階段采用集中式處理策略，這兩種方式可以避免節(jié)點(diǎn)死亡時(shí)的網(wǎng)絡(luò)中斷。WCACDS算法根據(jù)組合權(quán)值衡量節(jié)點(diǎn)性能，利用改進(jìn)后的連通支配集算法進(jìn)行分簇，減少了簇頭數(shù)量，增強(qiáng)了簇頭性能，提高了網(wǎng)絡(luò)負(fù)載平衡能力。這些算法各有優(yōu)缺點(diǎn)和應(yīng)用場(chǎng)景[6-7]。在上述研究的基礎(chǔ)上，文中提出一種具有通用性的分簇算法：自適應(yīng)按需加權(quán)分簇算法。

1 自適應(yīng)按需加權(quán)分簇算法

1.1 算法概述

自適應(yīng)按需加權(quán)分簇算法(adaptive on-demand weighting，AOW)[8]依據(jù)節(jié)點(diǎn)度數(shù)、節(jié)點(diǎn)能量、節(jié)點(diǎn)移動(dòng)性和節(jié)點(diǎn)距離等參數(shù)，通過(guò)權(quán)值因子的調(diào)整以適應(yīng)各種網(wǎng)絡(luò)，如式1，因此具有廣泛的適用性。AOW算法要求節(jié)點(diǎn)工作于半雙工模式且每個(gè)節(jié)點(diǎn)具有唯一的ID號(hào)，該算法執(zhí)行期間，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)需要保持穩(wěn)定狀態(tài)。

wn=c1Δn+c2Dn+c3Vn+c4En

(1)

其中，Δn表示節(jié)點(diǎn)的差異度，Dn表示節(jié)點(diǎn)與鄰居節(jié)點(diǎn)距離之和，Vn表示節(jié)點(diǎn)移動(dòng)速率，En表示節(jié)點(diǎn)的能量值，進(jìn)而反映了節(jié)點(diǎn)的能量消耗狀態(tài)；c1、c2、c3和c4為對(duì)應(yīng)不同參數(shù)的權(quán)值因子，并且滿(mǎn)足c1+c2+c3+c4=1。

1.2 AOW算法存在的問(wèn)題

AOW算法雖然綜合考慮了節(jié)點(diǎn)的多個(gè)權(quán)值，使簇頭的選舉更加合理，但仍存在以下問(wèn)題：

(1)AOW算法的權(quán)重選擇沒(méi)有考慮到節(jié)點(diǎn)本身處理能力，節(jié)點(diǎn)的權(quán)重計(jì)算都是假定所有節(jié)點(diǎn)處理能力都一樣這個(gè)前提(即節(jié)點(diǎn)是同構(gòu)的)，而真實(shí)的情況卻是網(wǎng)絡(luò)節(jié)點(diǎn)的處理能力差別很大，即節(jié)點(diǎn)是異構(gòu)的，分簇時(shí)應(yīng)考慮節(jié)點(diǎn)處理能力的差異。

(2)AOW算法計(jì)算節(jié)點(diǎn)移動(dòng)速率是以每個(gè)節(jié)點(diǎn)在一個(gè)時(shí)間周期T內(nèi)的絕對(duì)速率的累積值作為參數(shù)，這種方法僅能說(shuō)明這一節(jié)點(diǎn)相對(duì)于上一個(gè)位置的狀態(tài)變化，不能反映它相對(duì)于整個(gè)簇的穩(wěn)定性情況，因此具有一定的局限性，應(yīng)該考慮相對(duì)于所有鄰居節(jié)點(diǎn)的移動(dòng)更為合理。

(3)AOW算法只考慮了各節(jié)點(diǎn)的剩余能量，沒(méi)有從整體能量消耗最小的角度來(lái)規(guī)劃算法。

2 基于能量模型的多權(quán)值分簇算法

2.1 MANET網(wǎng)絡(luò)的能量模型

為了設(shè)計(jì)一種整體能量消耗最小的分簇算法，引入了MANET網(wǎng)絡(luò)的能量模型。MANET網(wǎng)絡(luò)節(jié)點(diǎn)的總通信能量消耗包括發(fā)送消息能耗、接收消息能耗、偵聽(tīng)能耗和控制報(bào)文能耗。

根據(jù)MANET網(wǎng)絡(luò)能量消耗的組成部分可知，讓節(jié)點(diǎn)處于睡眠狀態(tài)時(shí)，可以降低節(jié)點(diǎn)的能量消耗，因此應(yīng)該在保證網(wǎng)絡(luò)正常運(yùn)行的情況下盡可能地減少節(jié)點(diǎn)發(fā)送和接收消息包的時(shí)間，網(wǎng)絡(luò)的能量浪費(fèi)主要出現(xiàn)在以下幾個(gè)方面：

(1)偵聽(tīng)能耗是指節(jié)點(diǎn)處于空閑狀態(tài)時(shí)，為了識(shí)別可能會(huì)傳給自己的數(shù)據(jù)進(jìn)行信道偵測(cè)所消耗的能量。這種偵聽(tīng)的目的是保證需要接收數(shù)據(jù)時(shí)，節(jié)點(diǎn)能夠及時(shí)完成接收狀態(tài)的轉(zhuǎn)換，不過(guò)長(zhǎng)時(shí)間偵聽(tīng)信道會(huì)浪費(fèi)能量，因此可以在節(jié)點(diǎn)不需要發(fā)送和接收消息時(shí)使節(jié)點(diǎn)處于睡眠狀態(tài)以節(jié)省能量消耗。

(2)控制消息的開(kāi)銷(xiāo)：在MANET網(wǎng)絡(luò)的分簇過(guò)程中都需要發(fā)送一定數(shù)量的控制消息包，這些消息包是額外開(kāi)銷(xiāo)，不是最終用戶(hù)或者應(yīng)用所需要的數(shù)據(jù)，因此分簇算法的設(shè)計(jì)過(guò)程中應(yīng)該盡量減少以降低能量損耗。

文中均假設(shè)無(wú)線信道是完全對(duì)稱(chēng)的，即雙向信道的通信能耗相同?？紤]LEACH[9]協(xié)議使用的無(wú)線網(wǎng)絡(luò)能量模型，在這個(gè)模型下節(jié)點(diǎn)總能量消耗主要包括驅(qū)動(dòng)電路的能耗Eelec、發(fā)送能耗ETx(k,d)和接收能耗ERx(k)，其中Eelec與電路的硬件設(shè)計(jì)有關(guān)，例如數(shù)字編碼、信號(hào)調(diào)制解調(diào)、濾波器和帶寬不同，電路的消耗也不同。根據(jù)通信距離d與通信閾值d0之間的關(guān)系，分為自由空間(free space)和多徑衰落(multipath fading)兩種信道模型。在距離d的兩個(gè)節(jié)點(diǎn)間傳輸k比特消息時(shí)，ETx(k,d)和ERx(k)的計(jì)算如式2和式3，節(jié)點(diǎn)的偵聽(tīng)能耗Esense(k)的計(jì)算如式4。

ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)=

(2)

ERx(k)=ERx-elec(k)=kEelec

(3)

Esense(k)=α1k

(4)

在節(jié)點(diǎn)一致的情況下，Eelec是一個(gè)常數(shù)。從式2～4中可以看出，發(fā)送能耗、接收能耗以及偵聽(tīng)能耗與數(shù)據(jù)量成正比。

2.2 基于能量模型的多權(quán)值分簇算法

針對(duì)AOW算法存在的問(wèn)題，結(jié)合節(jié)點(diǎn)能量模型，提出一種基于能量模型的多權(quán)值分簇算法(Energy-AOW，EAOW)。算法中包含五個(gè)參數(shù)：節(jié)點(diǎn)度數(shù)(D)、節(jié)點(diǎn)傳輸功率(P)、節(jié)點(diǎn)移動(dòng)性(M)、節(jié)點(diǎn)剩余能量(E)和節(jié)點(diǎn)處理能力(A)。相比AOW算法有如下改進(jìn)：

(1)結(jié)合節(jié)點(diǎn)的能量消耗模型，使簇頭的選舉更加依賴(lài)于節(jié)點(diǎn)能量這個(gè)關(guān)鍵因素，提高了節(jié)點(diǎn)的生命周期，優(yōu)化了節(jié)點(diǎn)在生命周期的能量消耗，減少了能量的浪費(fèi)。

(2)在簇頭選舉成功后，選舉權(quán)值僅小于簇頭的節(jié)點(diǎn)擔(dān)任候選簇頭，當(dāng)簇區(qū)域發(fā)生變化時(shí)，候選簇頭節(jié)點(diǎn)可以迅速擔(dān)任新的簇頭，劃分新的簇區(qū)域，通過(guò)這種替代機(jī)制可以減少節(jié)點(diǎn)間的消息傳遞次數(shù)，縮短節(jié)點(diǎn)成簇時(shí)間。

(3)通過(guò)優(yōu)化權(quán)值的計(jì)算方法，提高了分簇的效率和準(zhǔn)確性，使分簇的統(tǒng)治集更加均勻，每個(gè)簇的節(jié)點(diǎn)數(shù)目保持在合理水平，采用相對(duì)移動(dòng)性，使簇頭的選擇更加合理，節(jié)點(diǎn)剩余能量參數(shù)可以使能量最高的節(jié)點(diǎn)成為簇頭，提高簇的整體生存時(shí)間。

2.3 算法描述

EAOW算法選舉簇頭時(shí)根據(jù)節(jié)點(diǎn)的五個(gè)權(quán)值，并在這五個(gè)權(quán)值賦上相應(yīng)的權(quán)值因子，權(quán)值因子可以根據(jù)環(huán)境系統(tǒng)的變化進(jìn)行動(dòng)態(tài)調(diào)整，然后計(jì)算每個(gè)節(jié)點(diǎn)的綜合權(quán)重，與鄰居節(jié)點(diǎn)的權(quán)重值進(jìn)行比較，依據(jù)選舉規(guī)則，最后選出簇頭節(jié)點(diǎn)和候選簇頭節(jié)點(diǎn)，從而劃分成不同的簇區(qū)域。

2.3.1 簇頭選舉算法流程

算法流程如圖1所示。

圖1 算法流程

具體權(quán)值計(jì)算如下描述：

(1)節(jié)點(diǎn)度數(shù)的計(jì)算。

每個(gè)節(jié)點(diǎn)v根據(jù)其相鄰節(jié)點(diǎn)的數(shù)目確定相應(yīng)的度數(shù)值，在實(shí)際計(jì)算過(guò)程中，計(jì)算其節(jié)點(diǎn)度數(shù)與理想度數(shù)σ之間的差值作為參數(shù)，記為：

Dv=|dv-σ|

(5)

其中，dv為節(jié)點(diǎn)的平均度數(shù)，表示相鄰范圍內(nèi)鄰居節(jié)點(diǎn)的數(shù)目，計(jì)算如式6：

(6)

其中，T表示節(jié)點(diǎn)總數(shù);H(v,v′)表示節(jié)點(diǎn)收到不同鄰居消息包的次數(shù)。

(2)節(jié)點(diǎn)相對(duì)移動(dòng)性的計(jì)算。

(7)

其中

(8)

(3)節(jié)點(diǎn)功率的計(jì)算。

節(jié)點(diǎn)功率可能在運(yùn)行過(guò)程中發(fā)生變化，所以考慮使用節(jié)點(diǎn)覆蓋范圍表示節(jié)點(diǎn)的發(fā)射和接收功率，覆蓋范圍為節(jié)點(diǎn)到所有鄰居節(jié)點(diǎn)的總和的均值，故節(jié)點(diǎn)功率Pv的計(jì)算公式為：

(4)節(jié)點(diǎn)剩余能量的計(jì)算。

節(jié)點(diǎn)剩余能量是簇頭選舉的關(guān)鍵參數(shù)，對(duì)于簇頭節(jié)點(diǎn)，它的能量消耗遠(yuǎn)遠(yuǎn)大于普通節(jié)點(diǎn)，能量值的變化會(huì)影響簇頭選舉過(guò)程，節(jié)點(diǎn)剩余能量Ev計(jì)算公式為：

Ev=Ei-ETx(k,d)-ERx(k)-Esense(k)

(10)

其中，Ei為節(jié)點(diǎn)的初始能量；ETx(k,d)為節(jié)點(diǎn)發(fā)送的能量消耗；ERx(k)為節(jié)點(diǎn)接收的能量消耗；Esense(k)為節(jié)點(diǎn)偵聽(tīng)的能量消耗。

(5)節(jié)點(diǎn)處理能力的計(jì)算。

節(jié)點(diǎn)的處理能力與多種因素相關(guān)，在仿真試驗(yàn)中人為將節(jié)點(diǎn)的處理能力劃分為不同的等級(jí)，其中最低等級(jí)配置的節(jié)點(diǎn)處理能力Av設(shè)為1，其他節(jié)點(diǎn)的處理能力值隨性能指標(biāo)的提高依次遞增。

(6)計(jì)算每個(gè)節(jié)點(diǎn)v在多權(quán)值條件下，根據(jù)權(quán)值因子得到的組合權(quán)值：

Wv=w1Dv+w2Mv+w3Pv+w4Ev+w5Av

(11)

(7)每個(gè)節(jié)點(diǎn)計(jì)算出自己的組合權(quán)值，然后相鄰間節(jié)點(diǎn)的權(quán)值做比較，權(quán)值最大的作為簇頭節(jié)點(diǎn)，權(quán)值次大的作為候選簇頭節(jié)點(diǎn)，當(dāng)有多個(gè)最大權(quán)值相等時(shí)，比較節(jié)點(diǎn)度數(shù)，以節(jié)點(diǎn)度數(shù)大的作為簇頭節(jié)點(diǎn)，本簇內(nèi)的成員節(jié)點(diǎn)為與簇頭相鄰的一跳節(jié)點(diǎn)，已經(jīng)劃分到簇內(nèi)的普通節(jié)點(diǎn)不能成為簇頭節(jié)點(diǎn)，但可以成為簇間網(wǎng)關(guān)節(jié)點(diǎn)。

(8)依次進(jìn)行上述過(guò)程，直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)劃分完畢，產(chǎn)生簇頭節(jié)點(diǎn)、簇成員節(jié)點(diǎn)、候選簇頭節(jié)點(diǎn)或者簇間節(jié)點(diǎn)。

2.3.2 簇結(jié)構(gòu)的形成與更新維護(hù)過(guò)程

該算法是一種動(dòng)態(tài)變化、分步計(jì)算的加權(quán)分簇算法，每一個(gè)節(jié)點(diǎn)都有唯一的ID號(hào)，作為節(jié)點(diǎn)的標(biāo)識(shí)。節(jié)點(diǎn)Vi使用CH(Vi)作為簇頭節(jié)點(diǎn)宣告消息，使用Jo(Vi,Vj)請(qǐng)求加入簇頭節(jié)點(diǎn)Vi的簇內(nèi)，成為該簇的簇成員節(jié)點(diǎn)。當(dāng)Vi為簇頭節(jié)點(diǎn)時(shí)，則用Ac(Vi,Vj)消息接受節(jié)點(diǎn)Vi的入簇請(qǐng)求，或者使用Re(Vi,Vj)消息拒絕節(jié)點(diǎn)Vj的入簇請(qǐng)求，以下為分簇算法的具體階段。

(1)簇結(jié)構(gòu)的初始化階段。

首先，由于所有節(jié)點(diǎn)處于初始化狀態(tài)，此時(shí)所有節(jié)點(diǎn)的狀態(tài)位為未決定狀態(tài)(Undecide)，由于節(jié)點(diǎn)的相對(duì)移動(dòng)性無(wú)法立即計(jì)算出來(lái)，所以在初始化階段使用最小節(jié)點(diǎn)ID分簇算法，通過(guò)Hello消息包中的ID號(hào)判斷簇頭節(jié)點(diǎn)，初始化完成以后，當(dāng)無(wú)線網(wǎng)絡(luò)中的節(jié)點(diǎn)出現(xiàn)變化時(shí)，各個(gè)節(jié)點(diǎn)通過(guò)Hello消息包向相鄰節(jié)點(diǎn)傳遞本節(jié)點(diǎn)的相關(guān)信息，各個(gè)節(jié)點(diǎn)之間通過(guò)權(quán)值的比較來(lái)執(zhí)行相應(yīng)的子過(guò)程。

(2)簇結(jié)構(gòu)的建立階段。

①如果節(jié)點(diǎn)Vi通過(guò)Hello消息包中的權(quán)值信息判斷出自己比相鄰節(jié)點(diǎn)Vj的權(quán)值大時(shí)，則向鄰居節(jié)點(diǎn)Vj發(fā)送CH(Vi)消息，同時(shí)將節(jié)點(diǎn)狀態(tài)位標(biāo)為簇頭狀態(tài)(ClusterHead)，并向相鄰的鄰居節(jié)點(diǎn)發(fā)送入簇請(qǐng)求Jo(Vi,Vj)，直到所有節(jié)點(diǎn)都加入簇，即Ac(Vi,Vj)=N(v)。

②如果節(jié)點(diǎn)Vi通過(guò)Hello消息包中的權(quán)值信息判斷自己比相鄰節(jié)點(diǎn)Vj的權(quán)值小且節(jié)點(diǎn)Vj發(fā)送了CH(Vj)消息包，則節(jié)點(diǎn)Vi可知Vj為簇頭節(jié)點(diǎn)，然后向節(jié)點(diǎn)Vj發(fā)送Jo(Vi,Vj)入簇請(qǐng)求，如果節(jié)點(diǎn)Vi收到節(jié)點(diǎn)Vj發(fā)送的Ac(Vj,Vi)允許加入消息或者在節(jié)點(diǎn)Vj的Hello消息中找到了本節(jié)點(diǎn)的ID標(biāo)識(shí)號(hào)，則表示節(jié)點(diǎn)Vi可以加入以節(jié)點(diǎn)Vj為簇頭的簇中，此時(shí)節(jié)點(diǎn)Vi會(huì)在發(fā)出的Hello消息中設(shè)置其為成員節(jié)點(diǎn)和簇頭節(jié)點(diǎn)的ID號(hào)，同時(shí)節(jié)點(diǎn)Vi的狀態(tài)位設(shè)置為簇成員狀態(tài)(Member)。

③如果節(jié)點(diǎn)Vi通過(guò)Hello消息包中的權(quán)值判斷自己比相鄰節(jié)點(diǎn)Vj的權(quán)值大，可是所有鄰居節(jié)點(diǎn)所在簇可用度數(shù)為零時(shí)，或者沒(méi)有成員節(jié)點(diǎn)加入該簇時(shí)，則節(jié)點(diǎn)Vi會(huì)發(fā)出CH(Vi)消息表明自己?jiǎn)为?dú)成為簇頭，同時(shí)節(jié)點(diǎn)Vi的狀態(tài)位設(shè)置為簇頭狀態(tài)(ClusterHead)。

(3)簇結(jié)構(gòu)的更新維護(hù)階段。

①如果一個(gè)新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)，它首先要向鄰居節(jié)點(diǎn)廣播Hello消息，Hello消息中包含了節(jié)點(diǎn)的所有權(quán)值信息，依據(jù)分簇算法計(jì)算節(jié)點(diǎn)的組合權(quán)值，同時(shí)與簇內(nèi)的簇頭節(jié)點(diǎn)和候選簇頭節(jié)點(diǎn)的權(quán)值相比較，如果新節(jié)點(diǎn)權(quán)值比簇頭節(jié)點(diǎn)權(quán)值大，則宣告自己成為新的簇頭節(jié)點(diǎn)；否則，與候選簇頭節(jié)點(diǎn)權(quán)值進(jìn)行比較，如果大于候選簇頭節(jié)點(diǎn)權(quán)值，則宣告自己成為候選簇頭節(jié)點(diǎn)；否則，新節(jié)點(diǎn)為普通簇成員節(jié)點(diǎn)。

②當(dāng)一個(gè)節(jié)點(diǎn)要退出簇時(shí)，如果是簇首節(jié)點(diǎn)，則候選簇頭節(jié)點(diǎn)直接成為新的簇頭節(jié)點(diǎn)，并向簇內(nèi)其他節(jié)點(diǎn)廣播；如果是非簇頭節(jié)點(diǎn)，只需要它的所有鄰居節(jié)點(diǎn)在鄰居表中刪除該節(jié)點(diǎn)即可；如果是候選簇頭節(jié)點(diǎn)，則需要在簇成員節(jié)點(diǎn)中重新選舉候選簇頭節(jié)點(diǎn)。

③當(dāng)一個(gè)簇成員節(jié)點(diǎn)發(fā)生移動(dòng)時(shí)，如果該節(jié)點(diǎn)收到新簇頭發(fā)出的宣告消息，但失去了原簇頭的消息，則直接加入該簇，此時(shí)與新節(jié)點(diǎn)入簇情況相同；若仍能收到原簇頭消息，則該節(jié)點(diǎn)成為簇間網(wǎng)關(guān)節(jié)點(diǎn)，同時(shí)在新簇內(nèi)選舉簇頭節(jié)點(diǎn)和候選簇頭節(jié)點(diǎn)。

3 算法性能仿真

結(jié)合兩種廣泛應(yīng)用的最小節(jié)點(diǎn)ID算法[11](LOWID)和最高節(jié)點(diǎn)度算法[12](HIGHD)，通過(guò)相應(yīng)的比較，驗(yàn)證EAOW算法的有效性和可行性。

3.1 性能評(píng)價(jià)指標(biāo)

分簇算法的性能評(píng)估指標(biāo)用于評(píng)估算法運(yùn)行的效率，主要有以下幾種[13]：

(1)簇頭節(jié)點(diǎn)變化頻率：表示單位時(shí)間內(nèi)簇頭節(jié)點(diǎn)的更新變化次數(shù)。

(2)節(jié)點(diǎn)狀態(tài)變化頻率：表示單位時(shí)間內(nèi)節(jié)點(diǎn)位置移動(dòng)后在簇間產(chǎn)生切換的次數(shù)。

(3)統(tǒng)治集更新頻率：表示簇結(jié)構(gòu)的變化頻率。

(4)節(jié)點(diǎn)成簇時(shí)間：表示所有節(jié)點(diǎn)完成分簇所花費(fèi)的時(shí)間成本，代表了分簇算法的效率。

3.2 仿真參數(shù)配置

為了獲知分簇算法的性能，將使用NS2[14]進(jìn)行仿真實(shí)驗(yàn)，參數(shù)配置如表1所示。

表1 節(jié)點(diǎn)參數(shù)設(shè)置

3.3 仿真結(jié)果的比較與分析

根據(jù)以上節(jié)點(diǎn)參數(shù)，使用仿真軟件對(duì)算法進(jìn)行仿真實(shí)驗(yàn)。

測(cè)試一：簇頭變化率與通信范圍。

不同通信范圍下的簇頭變化率如圖2所示。

圖2 不同通信范圍下的簇頭變化率

從仿真實(shí)驗(yàn)可以看出，隨著節(jié)點(diǎn)通信范圍的擴(kuò)大，簇頭變化率呈現(xiàn)先增大后減少的趨勢(shì)，這是由于通信距離增加后，簇頭的選舉競(jìng)爭(zhēng)減少，簇頭的數(shù)目會(huì)減少，簇頭之間的距離增加，因此簇頭的變化率減少。通過(guò)四種分簇算法的對(duì)比，顯示EAOW算法相比于其他三種算法有一定的提高，減少了簇頭的變化率，提高了簇的穩(wěn)定性。

測(cè)試二：統(tǒng)治集更新頻率與節(jié)點(diǎn)速率。

不同節(jié)點(diǎn)速率下的統(tǒng)治集更新頻率如圖3所示。

圖3 不同節(jié)點(diǎn)速率下的統(tǒng)治集更新頻率

當(dāng)節(jié)點(diǎn)速率增加時(shí)，簇的穩(wěn)定性降低，導(dǎo)致簇頭的競(jìng)爭(zhēng)選舉概率增大，統(tǒng)治集更新頻繁，從而統(tǒng)治集更新的頻率增加。隨著節(jié)點(diǎn)速率的增大，簇頭之間選舉頻繁，簇頭的變化率提高，統(tǒng)治集的更新加快。從實(shí)驗(yàn)結(jié)果可以看出，EAOW算法的統(tǒng)治集更新頻率低于其他分簇算法，因?yàn)樵撍惴紤]了節(jié)點(diǎn)的相對(duì)移動(dòng)性，使分簇更加合理，從而優(yōu)于其他三種算法。

測(cè)試三：節(jié)點(diǎn)狀態(tài)變化率與節(jié)點(diǎn)速率。

不同節(jié)點(diǎn)速率下的節(jié)點(diǎn)狀態(tài)變化率如圖4所示。

從仿真結(jié)果看，EAOW算法在節(jié)點(diǎn)速率增大的過(guò)程中，節(jié)點(diǎn)狀態(tài)變化率低于前三種算法，說(shuō)明此算法具有良好的分簇結(jié)構(gòu)，能適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)變化，由于EAOW算法充分考慮了節(jié)點(diǎn)的相對(duì)移動(dòng)性，當(dāng)節(jié)點(diǎn)出現(xiàn)動(dòng)態(tài)移動(dòng)時(shí)，能夠保持較低的節(jié)點(diǎn)狀態(tài)變化率，說(shuō)明了改進(jìn)算法的有效性。

圖4 不同節(jié)點(diǎn)速率下的節(jié)點(diǎn)狀態(tài)變化率

測(cè)試四：節(jié)點(diǎn)成簇時(shí)間與節(jié)點(diǎn)數(shù)目。

不同節(jié)點(diǎn)數(shù)目下的節(jié)點(diǎn)成簇時(shí)間如圖5所示。

圖5 不同節(jié)點(diǎn)數(shù)目下的節(jié)點(diǎn)成簇時(shí)間

從實(shí)驗(yàn)可以看出，當(dāng)節(jié)點(diǎn)數(shù)目較少時(shí)，四種分簇算法的成簇時(shí)間差別很小，當(dāng)節(jié)點(diǎn)數(shù)目增多時(shí)，成簇時(shí)間明顯增加。由于EAOW算法的分簇過(guò)程使用了候選簇頭節(jié)點(diǎn)的策略，所以節(jié)點(diǎn)的成簇時(shí)間低于AOW算法，這體現(xiàn)了候選簇頭在分簇中的優(yōu)勢(shì)，驗(yàn)證了改進(jìn)算法的有效性。

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

提出了一種基于能量模型的多權(quán)值分簇算法EAOW，該算法是對(duì)AOW算法的改進(jìn)，通過(guò)考慮網(wǎng)絡(luò)的整體能量消耗，增加和調(diào)整了簇頭選擇時(shí)考慮的條件因子，通過(guò)組合權(quán)值的計(jì)算，優(yōu)化了簇頭選舉策略，提高了分簇的性能和效率，減少了節(jié)點(diǎn)的能量消耗，提高了節(jié)點(diǎn)的生存時(shí)間，并通過(guò)仿真驗(yàn)證了該算法的優(yōu)越性。

目前的工作只涉及分簇算法本身，尚未與路由結(jié)合。因此結(jié)合路由選擇算法，基于分簇的路由將是下一步的研究工作。