一種融合時(shí)間和剩余能量激發(fā)的分簇優(yōu)化算法

姜 華， 林加華， 周萬(wàn)府

（楚雄師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，云南楚雄675000）

0 引 言

隨著無(wú)線技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）已廣泛應(yīng)用于軍事偵察、智能家居、環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生等領(lǐng)域［1-2］。由于應(yīng)用環(huán)境復(fù)雜多變，節(jié)點(diǎn)無(wú)法進(jìn)行實(shí)時(shí)供電，這使得能量成為制約WSN長(zhǎng)時(shí)間運(yùn)行的瓶頸。并且WSN 以Sink 節(jié)點(diǎn)為中心進(jìn)行數(shù)據(jù)匯聚傳輸，Sink 節(jié)點(diǎn)的能耗往往較大，會(huì)造成轉(zhuǎn)發(fā)數(shù)據(jù)越多的節(jié)點(diǎn)能量消耗越大，節(jié)點(diǎn)也會(huì)越早死亡，形成“節(jié)點(diǎn)空洞”［3-4］。LEACH 協(xié)議作為一種典型的均勻分簇路由協(xié)議［5］，通過(guò)簇頭輪轉(zhuǎn)來(lái)維持節(jié)點(diǎn)能量平衡，但這種輪換也僅僅是局部性的，對(duì)于距離匯聚節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)作用較小。文獻(xiàn)［6］中從節(jié)點(diǎn)入簇和簇間傳輸兩方面設(shè)計(jì)了一種非均勻分簇路由算法；文獻(xiàn)［7］中利用傳統(tǒng)的非均勻分簇路由算法對(duì)無(wú)線網(wǎng)絡(luò)進(jìn)行分簇，采用改進(jìn)蟻群優(yōu)化算法搜索出無(wú)線網(wǎng)絡(luò)簇間多條路徑，提出了一種改進(jìn)多目標(biāo)和聲搜索的無(wú)線網(wǎng)絡(luò)非均勻分簇路由方法；文獻(xiàn)［8］中將改進(jìn)的粒子群優(yōu)化算法應(yīng)用到雙層WSN分簇中，利用粒子群優(yōu)化算法對(duì)分簇多目標(biāo)函數(shù)進(jìn)行求解，以得到的解建立路由樹(shù)；文獻(xiàn)［9］中提出一種改進(jìn)的基于分簇WSN的數(shù)據(jù)聚合算法，解決了多跳模式下簇頭因負(fù)載不同而導(dǎo)致的能耗量差異，但該算法簇間重疊覆蓋率較大，節(jié)點(diǎn)能量額外浪費(fèi)較大；文獻(xiàn)［10］中提出了一種結(jié)合K-means均勻分簇和數(shù)據(jù)回歸的WSN 能量均衡策略，通過(guò)K-means聚類選取簇內(nèi)節(jié)點(diǎn)剩余能量最多者當(dāng)選簇頭，采用數(shù)據(jù)回歸方法減少節(jié)點(diǎn)與簇首間的通信量，能一定程度上降低節(jié)點(diǎn)能耗，但聚類依然以剩余能量多少來(lái)選取簇，“能量空洞”問(wèn)題并沒(méi)有根本性解決；文獻(xiàn)［11］中提出了一種基于時(shí)間激發(fā)的簇頭輪換策略，該策略對(duì)節(jié)點(diǎn)能量同構(gòu)的網(wǎng)絡(luò)有較大能耗提升，對(duì)于異構(gòu)網(wǎng)絡(luò)，因其未考慮節(jié)點(diǎn)間距離能耗而采用統(tǒng)一輪換策略，網(wǎng)絡(luò)的能效不高；文獻(xiàn)［12］中提出了一種基于剩余能量激發(fā)的簇頭輪換策略，根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量多少進(jìn)行簇頭輪換，讓能量剩余多的多承擔(dān)簇頭的轉(zhuǎn)發(fā)任務(wù)，以平衡整個(gè)網(wǎng)絡(luò)的能耗。但當(dāng)被選簇頭能量較低時(shí)，頻繁的激發(fā)簇頭輪換也會(huì)使網(wǎng)絡(luò)浪費(fèi)過(guò)多的能量。

針對(duì)無(wú)線網(wǎng)中節(jié)點(diǎn)能量負(fù)載不均，簇頭輪換激發(fā)機(jī)制單一，分簇算法能效較低等問(wèn)題，本文借鑒文獻(xiàn)［11-12］中的分簇思想，提出了一種融合時(shí)間和剩余能量激發(fā)的分簇算法。

1 網(wǎng)絡(luò)模型與系統(tǒng)能耗計(jì)算

1.1 網(wǎng)絡(luò)模型

假設(shè)N個(gè)節(jié)點(diǎn)隨機(jī)部署在M × M區(qū)域中，匯聚節(jié)點(diǎn)sink負(fù)責(zé)數(shù)據(jù)匯總。為方便后續(xù)計(jì)算，對(duì)無(wú)線網(wǎng)絡(luò)作如下假設(shè)［13-15］：

（1）傳感器節(jié)點(diǎn)能量有限，傳輸鏈路對(duì)稱，且節(jié)點(diǎn)發(fā)射功率因距離可調(diào)；

（2）各節(jié)點(diǎn)有相同的感知半徑Rs和通信半徑Rc，并且能將部署區(qū)域覆蓋和連通，節(jié)點(diǎn)間不需知道自身位置；

（3）網(wǎng)絡(luò)部署后各節(jié)點(diǎn)位置不變，匯聚節(jié)點(diǎn)居于網(wǎng)絡(luò)中心，能量足夠；

（4）網(wǎng)絡(luò)周期性收集數(shù)據(jù)，每輪數(shù)據(jù)收集，節(jié)點(diǎn)都要發(fā)送相同數(shù)據(jù)包長(zhǎng)度的數(shù)據(jù)給簇頭；

（5）所有節(jié)點(diǎn)時(shí)鐘同步。

本文選擇如圖1 所示的無(wú)線通信模型，考慮發(fā)送電路、接收電路、放大器以及傳輸?shù)臄?shù)據(jù)字節(jié)數(shù)，一個(gè)無(wú)線射頻收發(fā)器將k bit 數(shù)據(jù)包發(fā)送到距離為d 的另外一個(gè)無(wú)線收發(fā)器。

圖1 無(wú)線通信模型

發(fā)送能耗主要由信號(hào)發(fā)射電路能耗和放大器電路能耗兩部分組成，因此，發(fā)送k bit 數(shù)據(jù)到距離為d 的節(jié)點(diǎn)上的能耗：

式中：Etx表示接收單位比特?cái)?shù)據(jù)所需能耗；εamp1、εamp2表示所采用傳輸信道模型中的參數(shù)；β 表示路徑損耗常數(shù)，與傳播環(huán)境有關(guān)。當(dāng)d ＜d0時(shí)能耗模型采用自由空間模型，此時(shí)β = 2，εamp1= 10 pJ/ bit；當(dāng)d≥d0時(shí)能耗模型采用的是多路衰減模型，此時(shí)β = 4，εamp2=0.001 pJ/ bit。對(duì)于接收節(jié)點(diǎn)，接收k bit數(shù)據(jù)的能耗：

令Eam表示融合單位數(shù)據(jù)所需能量，則將h 個(gè)k bit 數(shù)據(jù)包融合成長(zhǎng)度為k數(shù)據(jù)包所耗能量為

Ecoll表示節(jié)點(diǎn)采集單位數(shù)據(jù)所需能量，則采集k bit 數(shù)據(jù)所耗能量為

1.2 簇頭選舉能耗

在整個(gè)無(wú)線網(wǎng)絡(luò)中，節(jié)點(diǎn)的能耗主要有兩部分：①動(dòng)態(tài)分簇過(guò)程中所消耗的能量；②分簇穩(wěn)定后，數(shù)據(jù)收集與傳輸所耗能量，這部分能耗為正當(dāng)消耗，其所占比例越大，說(shuō)明算法的能效比越高。

設(shè)在動(dòng)態(tài)分簇過(guò)程中所耗能量為Ec，穩(wěn)定階段數(shù)據(jù)收集與傳輸所耗能量Ew，則網(wǎng)絡(luò)能效率為

從上式可以看出，δ越大，穩(wěn)定階段所耗能量占比越大；反之亦然。想要提高整個(gè)無(wú)線網(wǎng)絡(luò)的能效率，就是在保證穩(wěn)定階段必要能耗的前提下盡量降低動(dòng)態(tài)分簇過(guò)程中所耗能量。目前簇頭選取主要以競(jìng)爭(zhēng)型為主。假設(shè)無(wú)線網(wǎng)絡(luò)中所有節(jié)點(diǎn)分為NNum個(gè)簇，則簇內(nèi)節(jié)點(diǎn)數(shù)n = NNum/ N，經(jīng)g 輪簇頭競(jìng)爭(zhēng)后，第i 個(gè)節(jié)點(diǎn)剩余能量為Egi，簇內(nèi)所有節(jié)點(diǎn)的剩余能量為EgAll，則第i個(gè)節(jié)點(diǎn)能選為簇頭的概率

不同簇頭選舉協(xié)議的不同之處在于簇頭選舉所依據(jù)的標(biāo)準(zhǔn)，至于簇頭確定后的能耗相差無(wú)幾。當(dāng)簇頭輪換條件激發(fā)后，簇內(nèi)節(jié)點(diǎn)根據(jù)匯聚節(jié)點(diǎn)sink 對(duì)剩余能量統(tǒng)計(jì)信息計(jì)算自身成為簇頭的概率，廣播候選簇首消息（COMPETE_HEAD_MSG）在第g 輪簇頭選舉階段的一個(gè)時(shí)間片內(nèi)一個(gè)節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)的概率為

任何一個(gè)分簇內(nèi)若有一個(gè)節(jié)點(diǎn)被選為簇頭，則其他節(jié)點(diǎn)會(huì)立馬停止對(duì)簇頭的競(jìng)爭(zhēng)，根據(jù)當(dāng)前簇頭節(jié)點(diǎn)信息進(jìn)行入簇，一個(gè)節(jié)點(diǎn)在第g 輪簇頭選舉階段第t時(shí)間片成為簇頭的概率

根據(jù)式（11）和（12），在第g 輪簇頭選舉階段，簇頭選舉成功所發(fā)送的簇首消息的數(shù)學(xué)期望為

在第g輪簇頭選舉階段若有Ni個(gè)節(jié)點(diǎn)參與過(guò)簇頭競(jìng)爭(zhēng)，則有：

因有Ni個(gè)節(jié)點(diǎn)參與簇頭競(jìng)爭(zhēng)，那么簇內(nèi)接收候選簇首消息的節(jié)點(diǎn)有n - Ni，又因時(shí)間片空閑概率為1 -表示在第g 輪簇頭選舉階段的一個(gè)時(shí)間片空閑內(nèi)平均接收候選簇首消息，則在第g 輪簇頭選舉階段簇頭選舉成功時(shí)分簇節(jié)點(diǎn)接收簇首消息的數(shù)學(xué)期望為

根據(jù)式（13）和（15），結(jié)合式（1），則簇頭競(jìng)爭(zhēng)階段建立簇頭所耗能量估算為

上式等式右邊第1 部分表示廣播簇頭通告幀所耗能量；第2 部分表示接收簇頭通告幀所耗能量，這里能耗模型采用自由空間模型，β = 2，εamp1= 10 pJ/ bit。dC表示簇內(nèi)節(jié)點(diǎn)到簇頭的平均距離。理想狀態(tài)下各簇均勻分布，分簇大小為M2/ NNum，分簇半徑R = M/

式中：ρ（r，θ）表示節(jié)點(diǎn)分布密度，對(duì)于節(jié)點(diǎn)均勻分布的無(wú)線網(wǎng)絡(luò)，分布密度函數(shù)為常量，則

簇頭選舉成功后，簇內(nèi)剩余節(jié)點(diǎn)就會(huì)放棄競(jìng)爭(zhēng)簇頭，轉(zhuǎn)而申請(qǐng)加入該簇，新選定的簇頭節(jié)點(diǎn)在收到其他節(jié)點(diǎn)申請(qǐng)入簇的消息后，以發(fā)送確認(rèn)消息并分配TDMA，這些系統(tǒng)幀也要消耗一定的能量，則在整個(gè)簇頭競(jìng)爭(zhēng)階段最低能耗為：

2 時(shí)間和剩余能量激發(fā)的分簇算法

2.1 時(shí)間激發(fā)的分簇算法能效率

文獻(xiàn)［11］是基于時(shí)間激發(fā)的簇頭輪換算法，在簇頭競(jìng)爭(zhēng)結(jié)束后，新簇頭按照時(shí)分多址（TDMA）機(jī)制對(duì)簇內(nèi)節(jié)點(diǎn)分配時(shí)間片段，簇內(nèi)節(jié)點(diǎn)在簇頭分配的時(shí)間片內(nèi)將需要發(fā)送的數(shù)據(jù)發(fā)送給簇頭，發(fā)送數(shù)據(jù)幀結(jié)構(gòu)如圖2 所示。

圖2 TDMA數(shù)據(jù)幀結(jié)構(gòu)

在穩(wěn)定階段，節(jié)點(diǎn)會(huì)在分配時(shí)間片內(nèi)連續(xù)發(fā)送s個(gè)等長(zhǎng)數(shù)據(jù)幀，在這種簇頭時(shí)分多址的調(diào)度中，未被分配時(shí)間片的節(jié)點(diǎn)就會(huì)進(jìn)入休眠中，以節(jié)省自身能量。分簇在經(jīng)過(guò)s輪數(shù)據(jù)發(fā)送后，自動(dòng)激發(fā)簇頭輪換，那么一輪數(shù)據(jù)傳輸簇頭所耗能量為

式中：dS表示簇頭節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離。簇內(nèi)所有節(jié)點(diǎn)將數(shù)據(jù)傳輸給簇頭所耗能量為

無(wú)線網(wǎng)絡(luò)在傳輸s 輪數(shù)據(jù)后進(jìn)行簇頭輪換，則在穩(wěn)定階段分簇所耗能量為

根據(jù)式（5）、（19）、（20）、（22）可得文獻(xiàn)［11］的能效率：

基于時(shí)間激發(fā)的簇頭輪換有兩個(gè)瓶頸：一是分簇算法若是應(yīng)用于異構(gòu)無(wú)線網(wǎng)絡(luò)中，簇頭的輪換是機(jī)械的依時(shí)間為基準(zhǔn)，這種不貼近時(shí)間情況的簇頭輪換勢(shì)必會(huì)增大簇頭競(jìng)爭(zhēng)階段的能耗，降低無(wú)線網(wǎng)絡(luò)的能耗率；二是在無(wú)線網(wǎng)絡(luò)的整個(gè)壽命周期內(nèi)，基于時(shí)間激發(fā)的簇頭輪換算法其能效率基本不變。這就無(wú)法通過(guò)改進(jìn)算法來(lái)提高能效率。

通過(guò)簡(jiǎn)單推導(dǎo)來(lái)證明文獻(xiàn)［11］中的能效率，將式（23）進(jìn)行歸一化可得：

無(wú)線網(wǎng)絡(luò)中，在網(wǎng)絡(luò)節(jié)點(diǎn)部署完后，簇頭在競(jìng)爭(zhēng)階段的能耗Ecluster_setup是一定的，而穩(wěn)定階段數(shù)據(jù)的傳輸所耗能量跟網(wǎng)絡(luò)模型和節(jié)點(diǎn)的通信距離相關(guān)，那么在網(wǎng)絡(luò)模型既定，節(jié)點(diǎn)分布均勻的網(wǎng)絡(luò)里，Ecluster+ Enode可以認(rèn)為其變化不大。由此可知能效率δTime是一個(gè)與數(shù)據(jù)傳輸輪數(shù)相關(guān)的函數(shù)，無(wú)線網(wǎng)絡(luò)中，穩(wěn)定階段的數(shù)據(jù)傳輸輪數(shù)也是既定的，這就說(shuō)明文獻(xiàn)［11］的能效率隨著傳輸輪數(shù)的增大而降低。

2.2 剩余能量激發(fā)的分簇算法能效率

文獻(xiàn)［11］是基于時(shí)間激發(fā)的簇頭輪換算法，沒(méi)有考慮節(jié)點(diǎn)自身情況，刻板地以時(shí)間單位作為簇頭輪換的觸發(fā)條件，這不適用于節(jié)點(diǎn)能量異構(gòu)的網(wǎng)絡(luò)。而文獻(xiàn)［12］中以節(jié)點(diǎn)剩余能量作為簇頭輪換的激發(fā)條件，讓剩余能量多的節(jié)點(diǎn)承擔(dān)簇頭，這有利于平衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗不均。在文獻(xiàn)［12］中設(shè)置一個(gè)觸發(fā)簇頭輪換的能量閾值

式中：σ∈［0，1］為調(diào)節(jié)參數(shù)；Erem（i）表示節(jié)點(diǎn)當(dāng)選簇頭時(shí)所剩能量值。當(dāng)簇頭節(jié)點(diǎn)剩余能量低于能量閾值αi時(shí)，簇頭輪換被激發(fā)，無(wú)線網(wǎng)絡(luò)根據(jù)節(jié)點(diǎn)剩余能量值開(kāi)始重新選舉簇頭，此時(shí)簇頭傳輸數(shù)據(jù)所需能量為

式中：Eelec表示節(jié)點(diǎn)在競(jìng)爭(zhēng)簇頭階段所耗能量，在沒(méi)有網(wǎng)絡(luò)堵塞時(shí)，其主要包括廣播候選簇首消息、接收各節(jié)點(diǎn)入簇消息、分配時(shí)分多址時(shí)間片消息等，其下限值

通過(guò)上式可以看出，數(shù)據(jù)傳輸?shù)妮啍?shù)隨著節(jié)點(diǎn)剩余能量而變化，分簇在βg，i輪的數(shù)據(jù)傳輸所耗能量為

通過(guò)上式可以看出，能效率δrem_Dr不僅與調(diào)節(jié)參數(shù)σ有關(guān)，還與節(jié)點(diǎn)的剩余能量Egi有關(guān)，這樣的能效率能實(shí)時(shí)反映無(wú)線網(wǎng)絡(luò)能耗情況。

但隨著被選簇頭能量的逐漸降低，簇頭輪換的次數(shù)將越來(lái)越頻繁，致使網(wǎng)絡(luò)浪費(fèi)過(guò)多的能量。下面對(duì)簇頭輪換前數(shù)據(jù)傳輸輪數(shù)βg，i進(jìn)行推導(dǎo)，設(shè)

式中：Ea、（Etx+ εamp1dβ）、Eam在無(wú)線網(wǎng)絡(luò)初始化完畢后都是定值，所以數(shù)據(jù)傳輸輪數(shù)βg，i與（1 - σ）Egi正相關(guān)。當(dāng)節(jié)點(diǎn)剩余能量Egi越小，用于穩(wěn)定階段數(shù)據(jù)傳輸?shù)哪芰吭缴伲瑪?shù)據(jù)傳輸?shù)妮啍?shù)也會(huì)變少，簇頭輪換的頻率將加大，簇頭競(jìng)爭(zhēng)階段的能耗將增多，整個(gè)無(wú)線網(wǎng)絡(luò)的能耗率會(huì)隨著節(jié)點(diǎn)能量的減少而降低。這是基于剩余能量激發(fā)的分簇算法的重要弊端。

2.3 分簇算法流程

通過(guò)分析可知，基于時(shí)間和剩余能量激發(fā)的分簇算法各有利弊。在節(jié)點(diǎn)生命的初期能量充足，基于剩余能量激發(fā)的分簇策略能取得較好的能效率；當(dāng)節(jié)點(diǎn)剩余能量不足時(shí)，為避免頻繁激發(fā)簇頭輪換而浪費(fèi)能量，啟用基于時(shí)間激發(fā)的分簇策略更有利于提高無(wú)線網(wǎng)絡(luò)的能效率。

為此，本文融合兩者的優(yōu)點(diǎn)，以兩者的能效率大小為界，分別激發(fā)簇頭競(jìng)爭(zhēng)的不同策略。當(dāng)δrem_Dr≥δTime時(shí)，融合分簇算法采用剩余能量激發(fā)分簇；δrem_Dr＜δTime時(shí)，融合分簇算法切換到基于時(shí)間激發(fā)分簇。δrem_Dr=δTime時(shí)：

式中，簇頭競(jìng)爭(zhēng)所耗能量Ecluster和單輪節(jié)點(diǎn)數(shù)據(jù)傳輸是無(wú)線網(wǎng)系統(tǒng)性能耗，其值在網(wǎng)絡(luò)模型建立后基本不變，那么剩余能量的臨界值Ecri的大小僅與調(diào)節(jié)參數(shù)σ和數(shù)據(jù)傳輸輪數(shù)s 有關(guān)，顯然這兩個(gè)參數(shù)的大小決定著分簇算法切換的時(shí)機(jī)。

在網(wǎng)絡(luò)模型既定，其他參數(shù)確定的情況下，各分簇算法的分簇初始建立和穩(wěn)定數(shù)據(jù)發(fā)送兩個(gè)階段都大同小異，主要的區(qū)別在簇頭競(jìng)爭(zhēng)階段。

（1）分簇建立。匯聚節(jié)點(diǎn)根據(jù)掌握的全網(wǎng)節(jié)點(diǎn)信息計(jì)算剩余能量并廣播給各個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)根據(jù)自身剩余能量計(jì)算參與簇頭競(jìng)爭(zhēng)的概率Pgi，剩余能量多的節(jié)點(diǎn)參與簇頭競(jìng)爭(zhēng)的概率就大，優(yōu)先廣播候選簇首消息（COMPETE_HEAD_MSG）和確認(rèn)簇頭消息（FINAL_HEAD_MSG），對(duì)比自身剩余能量后，對(duì)于不參與簇頭競(jìng)爭(zhēng)的節(jié)點(diǎn)來(lái)說(shuō)，廣播退出簇頭競(jìng)爭(zhēng)的消息（QUIT_ELECTION_MSG），這就將自身標(biāo)記為普通節(jié)點(diǎn)，等待新簇產(chǎn)生；依據(jù)網(wǎng)絡(luò)初始化設(shè)置所建立的簇?cái)?shù)，候選簇頭節(jié)點(diǎn)繼續(xù)廣播候選簇頭消息，一旦周圍沒(méi)有候選節(jié)點(diǎn)廣播信息，候選簇頭就會(huì)普通節(jié)點(diǎn)根據(jù)接收候選簇頭消息信號(hào)的強(qiáng)弱決定加入哪個(gè)簇，并向其發(fā)送入簇消息（JOIN_REQ_MSG）或拒絕入簇消息（JOIN_DENY_MSG）。簇頭確定后，周圍節(jié)點(diǎn)不斷向簇頭節(jié)點(diǎn)發(fā)送入網(wǎng)申請(qǐng)，直至分簇成立。

（2）數(shù)據(jù)發(fā)送。在數(shù)據(jù)發(fā)送階段，簇頭匯集簇內(nèi)成員的感知信息發(fā)送到匯聚節(jié)點(diǎn)sink。簇頭節(jié)點(diǎn)在進(jìn)行數(shù)據(jù)發(fā)送前，會(huì)將自身剩余能量與剩余能量臨界值Ecri進(jìn)行對(duì)比，以確定之后采取何種簇頭輪換協(xié)議。然后簇頭節(jié)點(diǎn)廣播簇內(nèi)系統(tǒng)幀，按照時(shí)分多址（TDMA）機(jī)制對(duì)簇內(nèi)節(jié)點(diǎn)分配時(shí)間片段，簇內(nèi)節(jié)點(diǎn)在簇頭分配的時(shí)間片內(nèi)將需要發(fā)送的數(shù)據(jù)發(fā)送給簇頭。完成數(shù)據(jù)收集后，簇頭節(jié)點(diǎn)將所有數(shù)據(jù)進(jìn)行處理經(jīng)路由傳至匯聚節(jié)點(diǎn)sink。

（3）簇頭輪換。激發(fā)簇頭輪換的條件不僅有簇頭節(jié)點(diǎn)的剩余能量還包括網(wǎng)絡(luò)故障或匯聚節(jié)點(diǎn)異常，任何一種條件被激發(fā)后，簇頭節(jié)點(diǎn)都會(huì)立即將此消息通知匯聚節(jié)點(diǎn)sink。接下來(lái)算法啟動(dòng)簇頭競(jìng)爭(zhēng)輪換，簇頭會(huì)廣播簇頭重建消息（CLUSTER_REBUILD_MSG）到簇內(nèi)各節(jié)點(diǎn)和匯聚節(jié)點(diǎn)sink；簇內(nèi)節(jié)點(diǎn)接收到簇頭重建廣播消息后將自身剩余能量信息發(fā)送給簇頭，簇頭將收集到的簇內(nèi)節(jié)點(diǎn)剩余能量信息發(fā)送給匯聚節(jié)點(diǎn)sink，匯聚節(jié)點(diǎn)在接收各分簇簇內(nèi)節(jié)點(diǎn)剩余能量的同時(shí)廣播簇頭解除消息（CLUSTER_DISMISS_MSG）到全網(wǎng)，全網(wǎng)啟動(dòng)簇頭競(jìng)爭(zhēng)輪換。簇頭競(jìng)爭(zhēng)輪換偽代碼如下：

Step1：Setup（）；/ /初始化無(wú)線網(wǎng)絡(luò)參數(shù)

Step2：if（round = 1）then

計(jì)算Pgi；/ /如果是第一輪計(jì)算節(jié)點(diǎn)為簇頭的概率Pgi

endif

Step3：廣播簇頭選擇命令；

Step4：CH_Selection（COMPETE_HEAD_MSG，F(xiàn)INAL_HEAD_MSG，QUIT_ELECTION_MSG）；/ /簇頭選擇

Step5：CH _ Constrution（CH-ADV-MSG，JOIN _ CLUSTER _MSG）；/ /簇頭建立

Step6：計(jì)算剩余能量的臨界值Ecri；

Step7：if（Egi≥Ecri）

｛while（Erem（i）≥σEgi）

Data_Collection（）；/ /接收簇內(nèi)數(shù)據(jù)

Data_Transmission（）；/ /簇內(nèi)數(shù)據(jù)傳輸

當(dāng)前簇頭向匯聚節(jié)點(diǎn)Sink發(fā)起輪換簇頭的請(qǐng)求；

當(dāng)前簇頭發(fā)送各節(jié)點(diǎn)剩余能量到匯聚節(jié)點(diǎn)Sink；

goto Step2；

｝

Step8：else執(zhí)行下一步；

Step9：節(jié)點(diǎn)Sink啟動(dòng)基于時(shí)間激發(fā)的簇頭輪換；

Step10：if（round = 1）then

計(jì)算Pgi；/ /如果第一輪計(jì)算節(jié)點(diǎn)為簇頭概率Pgi

endif

Step11：CH_Selection（）；/ /分簇選擇

Step12：CH_Constrution（）；/ /簇頭建立

Step13：Time_Round = s；/ /設(shè)定時(shí)間分簇輪數(shù)

Step14：

while（Time_Round ＞0）

｛

Data_Collection（）；/ /接收簇內(nèi)數(shù)據(jù)

Data_Transmission（）；/ /簇內(nèi)數(shù)據(jù)傳輸

Time_Round - -；

｝

Step15：goto Step10；

2.4 分簇算法的復(fù)雜性

無(wú)線傳感網(wǎng)絡(luò)中節(jié)點(diǎn)的能量是有限的，過(guò)于復(fù)雜的算法會(huì)加快消耗節(jié)點(diǎn)的能量，縮短整個(gè)傳感網(wǎng)絡(luò)的生命周期。根據(jù)網(wǎng)絡(luò)模型中的假設(shè)，匯聚節(jié)點(diǎn)的能量是足夠的，這里可以將復(fù)雜的信息處理和計(jì)算交給匯聚節(jié)點(diǎn)，而算法的復(fù)雜度主要由節(jié)點(diǎn)間的信息量決定的。

在基于剩余能量激發(fā)的簇頭輪換中，匯聚節(jié)點(diǎn)首先要廣播分簇重建幀，然后N 個(gè)廣播候選簇首消息（COMPETE_HEAD_MSG）和確認(rèn)簇頭消息（FINAL_HEAD_MSG），對(duì)比自身剩余能量后，對(duì)于不參與簇頭競(jìng)爭(zhēng)的普通節(jié)點(diǎn)來(lái)說(shuō)，廣播退出簇頭競(jìng)爭(zhēng)的消息（QUIT_ELECTION_MSG）。因此Num - N個(gè)普通節(jié)點(diǎn)要發(fā)送Num - N個(gè)入簇消息JOIN_REQ_MSG，因此信息量總和為Num + N + N + N + Num - N = 2（Num +N），所以每輪分簇輪換的復(fù)雜度為O（Num）。

在切入時(shí)間激發(fā)的簇頭輪換后，無(wú)線網(wǎng)絡(luò)中不再需要判別簇頭輪換，而是以時(shí)間片作為驅(qū)動(dòng)，其信息量復(fù)雜度與基于時(shí)間激發(fā)的分簇協(xié)議無(wú)異。由此可見(jiàn)，本文基于時(shí)間和剩余能量激發(fā)的分簇協(xié)議不會(huì)增加整個(gè)算法的復(fù)雜度O（Num）。

3 參數(shù)設(shè)置與仿真對(duì)比

在本文混合分簇協(xié)議中，節(jié)點(diǎn)的臨界剩余能量值Ecri與剩余能量分簇的調(diào)節(jié)參數(shù)σ 和時(shí)間激發(fā)的分簇傳輸中數(shù)據(jù)傳輸輪數(shù)s 息息相關(guān)，這兩個(gè)關(guān)鍵參數(shù)決定著時(shí)間和剩余能量激發(fā)的分簇協(xié)議啟動(dòng)切換的時(shí)機(jī)。為了計(jì)算本文協(xié)議中的關(guān)鍵參數(shù)，設(shè)節(jié)點(diǎn)分布在（100 × 100）m2的區(qū)域內(nèi)，匯聚節(jié)點(diǎn)sink 默認(rèn)坐標(biāo)為（50，50），節(jié)點(diǎn)總數(shù)為200，簇頭比例為5%，數(shù)據(jù)和命令幀的長(zhǎng)度為256 bits，εamp1= 10 pJ/ bit，Eam= 5 nJ/ bit，Etx= 50 nJ/ bit。

3.1 時(shí)間激發(fā)分簇中傳輸輪數(shù)s值

假設(shè)從基于剩余能量分簇協(xié)議切換到基于時(shí)間激發(fā)分簇協(xié)議的節(jié)點(diǎn)剩余能量最小值為Emin，簇頭節(jié)點(diǎn)在一輪數(shù)據(jù)傳輸中所耗能量為Ecluster，普通簇內(nèi)節(jié)點(diǎn)一輪數(shù)據(jù)傳輸中所耗能量為Enode，那么簇頭和簇內(nèi)節(jié)點(diǎn)在整個(gè)傳輸節(jié)點(diǎn)所耗能量為：

在一輪傳輸中Ecluster包括接收簇內(nèi)節(jié)點(diǎn)信息、融合所接收數(shù)據(jù)信息以及將融合信息發(fā)送到匯聚節(jié)點(diǎn)的所有能耗；而在一輪傳輸中Enode包括簇內(nèi)節(jié)點(diǎn)發(fā)送數(shù)據(jù)到簇頭節(jié)點(diǎn)所有能耗，故：

根據(jù)文獻(xiàn)［16］的證明可知，在一個(gè)含有n 個(gè)節(jié)點(diǎn)的分簇中，若一個(gè)節(jié)點(diǎn)僅充當(dāng)過(guò)一次簇頭和n - 1 次普通節(jié)點(diǎn)，那么存在一個(gè)最大傳輸輪數(shù)s，滿足：

節(jié)點(diǎn)剩余能量最小值E由匯聚節(jié)點(diǎn)統(tǒng)計(jì)得，無(wú)min線網(wǎng)絡(luò)既定的情況下，式（40）其他參數(shù)很容易確定，由此可以大體計(jì)算出時(shí)間激發(fā)分簇中傳輸輪數(shù)s值。

3.2 剩余能量激發(fā)分簇中調(diào)節(jié)參數(shù)σ

基于剩余能量的分簇輪換受能量閾值α 的直接影響，而閾值α的取值不僅與當(dāng)選簇頭的剩余能量有關(guān)還與調(diào)節(jié)參數(shù)息息相關(guān)。將能量閾值α 按照文獻(xiàn)［18］中進(jìn)行設(shè)置，即α = 0.1 J，從剩余能量的分簇輪換所耗能量可以看出，調(diào)節(jié)參數(shù)的大小與簇頭通信所耗Ecluster有關(guān)。當(dāng)簇頭節(jié)點(diǎn)與匯聚節(jié)點(diǎn)相近時(shí)，Ecluster就小，反之簇頭通信所耗Ecluster就大，為了計(jì)算調(diào)節(jié)參數(shù)σ與簇頭、匯聚節(jié)點(diǎn)距離關(guān)系，這里設(shè)定匯聚節(jié)點(diǎn)處于兩種不同的位置：一種是處于無(wú)線網(wǎng)絡(luò)區(qū)域的中心，即坐標(biāo)（50，50）；另一種是處于無(wú)線網(wǎng)絡(luò)區(qū)域的外圍，即坐標(biāo)（150，50）。以第1 個(gè)節(jié)點(diǎn)死亡時(shí)間來(lái)計(jì)算無(wú)線網(wǎng)絡(luò)生命周期，考察數(shù)據(jù)傳輸輪數(shù)與調(diào)節(jié)參數(shù)σ的關(guān)系，結(jié)果如圖3 所示。

圖3 數(shù)據(jù)傳輸與調(diào)節(jié)參數(shù)的關(guān)系

從圖3 可以看出，不論匯聚節(jié)點(diǎn)處于中心還是無(wú)線區(qū)域外，σ與數(shù)據(jù)轉(zhuǎn)發(fā)輪數(shù)的關(guān)系大致相當(dāng)。都是隨著σ的增大，數(shù)據(jù)傳輸輪數(shù)先增大后減少。當(dāng)匯聚節(jié)點(diǎn)處于網(wǎng)絡(luò)中心，σ = 0.614 時(shí)，取得最大數(shù)據(jù)傳輸輪數(shù)；當(dāng)匯聚節(jié)點(diǎn)處于網(wǎng)絡(luò)外，σ = 0.568 時(shí)取得最大數(shù)據(jù)傳輸輪數(shù)。根據(jù)對(duì)網(wǎng)絡(luò)模型的假定，本文主要考慮匯聚節(jié)點(diǎn)處于無(wú)線網(wǎng)絡(luò)的中心，所以這里設(shè)置σ =0.568。

為了檢驗(yàn)和對(duì)比各分簇算法的性能，應(yīng)用本文分簇算法改進(jìn)LEACH協(xié)議，在NS2 仿真環(huán)境下，將本文改進(jìn)后的算法與文獻(xiàn)［11-12，17］進(jìn)行對(duì)比分析。其中文獻(xiàn)［11］中的最優(yōu)數(shù)據(jù)傳輸輪數(shù)參考其文章設(shè)定，文獻(xiàn)［12］的最優(yōu)最優(yōu)能量閾值參照文獻(xiàn)［18］設(shè)置。仿真是在Windows 7 系統(tǒng)的NS2 平臺(tái)上，CPU：i5-7500@3.4 GHz，RAM：8 GB。根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)能量的不同設(shè)置節(jié)點(diǎn)能量同構(gòu)和節(jié)點(diǎn)能量異構(gòu)兩種實(shí)驗(yàn)環(huán)境：

Env1 無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布在（100 × 100）m2的區(qū)域內(nèi)，各節(jié)點(diǎn)能量值為0.5 J，匯聚節(jié)點(diǎn)能量足夠，分布于網(wǎng)絡(luò)中心；

Env2 無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布在（100 × 100）m2的區(qū)域內(nèi)，各節(jié)點(diǎn)能量值隨機(jī)在［0.1 J，1 J］，匯聚節(jié)點(diǎn)能量足夠，分布于網(wǎng)絡(luò)中心。

3.3 網(wǎng)絡(luò)生存時(shí)間對(duì)比

網(wǎng)絡(luò)生存時(shí)間是衡量分簇協(xié)議的一個(gè)重要指標(biāo)，但對(duì)網(wǎng)絡(luò)生存時(shí)間的定義也不同：一種是以第1 個(gè)節(jié)點(diǎn)死亡時(shí)間為網(wǎng)絡(luò)生存時(shí)間［19］；另一種以低于存活節(jié)點(diǎn)比例的時(shí)間為網(wǎng)絡(luò)生存時(shí)間［20］。這里以第2 種定義形式計(jì)算網(wǎng)絡(luò)生存時(shí)間。圖4 顯示了4 種算法在能量同構(gòu)和能量異構(gòu)環(huán)境上的網(wǎng)絡(luò)生存時(shí)間。

圖4 4種算法在不同環(huán)境下的網(wǎng)絡(luò)生存時(shí)間

在能量同構(gòu)還是在能量異構(gòu)中，本文分簇算法對(duì)比文獻(xiàn)［11-12，17］均取得更好的網(wǎng)絡(luò)生存時(shí)間。在能量同構(gòu)環(huán)境下，以剩余能量作為激發(fā)簇頭輪換的文獻(xiàn)［12］反而節(jié)點(diǎn)存活數(shù)下降的更快，這是由于各節(jié)點(diǎn)的能量是相同的，節(jié)點(diǎn)剩余能量差別較小，頻繁的簇頭輪換加劇了節(jié)點(diǎn)能量的消耗；而文獻(xiàn)［11］是以時(shí)間片激發(fā)簇頭輪換，這種策略本身就忽略了節(jié)點(diǎn)能量的差異，節(jié)點(diǎn)的能耗相對(duì)平均，節(jié)點(diǎn)存活數(shù)的降幅和網(wǎng)絡(luò)生存時(shí)間相較于文獻(xiàn)［12］有較好的結(jié)果；文獻(xiàn)［17］以“能者多勞”原則選擇簇頭，意在均衡節(jié)點(diǎn)的能耗，在同構(gòu)環(huán)境下結(jié)果與文獻(xiàn)［11］相近，但到網(wǎng)絡(luò)生存后期，剩余能量多的節(jié)點(diǎn)工作時(shí)間更長(zhǎng)，一定程度上延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間；本文分簇算法前期以時(shí)間片激發(fā)分簇為主，后期以剩余能量激發(fā)分簇，較大程度上延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

在異構(gòu)環(huán)境下，4 種分簇算法所獲得的網(wǎng)絡(luò)生存時(shí)間長(zhǎng)短不一，差距較大。本文分簇算法和文獻(xiàn)［17］相較于文獻(xiàn)［11，12］一定程度上提升了網(wǎng)絡(luò)生存時(shí)間。以時(shí)間片激發(fā)簇頭輪換的文獻(xiàn)［11］效果最差，這是由于節(jié)點(diǎn)能量不一，固定的時(shí)間片激發(fā)輪換過(guò)早使能量低的節(jié)點(diǎn)早死；文獻(xiàn)［12］以剩余能量大小為激發(fā)條件，較好均衡了節(jié)點(diǎn)能量不一的現(xiàn)實(shí)，但在后期節(jié)點(diǎn)能量普遍較低時(shí)，頻繁的更換簇頭會(huì)加快節(jié)點(diǎn)能量消耗；而文獻(xiàn)［17］中剩余能量多的節(jié)點(diǎn)當(dāng)簇頭的次數(shù)和時(shí)間越多，這雖然能使節(jié)點(diǎn)能耗均衡，但也會(huì)造成剩余能量多的節(jié)點(diǎn)死在當(dāng)簇頭的過(guò)程中。

3.4 網(wǎng)絡(luò)能效率對(duì)比

提高無(wú)線網(wǎng)絡(luò)的能效率一定程度上可以延長(zhǎng)無(wú)線網(wǎng)絡(luò)生存時(shí)間。圖5 為4 種算法在能量同構(gòu)和能量異構(gòu)上的能效率。從圖可以看出，隨著數(shù)據(jù)傳輸輪數(shù)的加大，各算法的網(wǎng)絡(luò)能效率都呈現(xiàn)下降的趨勢(shì)，總體上本文分簇算法比文獻(xiàn)［11-12，17］有較高的網(wǎng)絡(luò)能效率。在圖5（a）節(jié)點(diǎn)能量同構(gòu)環(huán)境下，數(shù)據(jù)傳輸前期，文獻(xiàn)［11］的能效率要高于文獻(xiàn)［12］，但隨著節(jié)點(diǎn)能量的耗盡，機(jī)械的依靠時(shí)間片激發(fā)分簇會(huì)增加網(wǎng)絡(luò)無(wú)用的能量消耗，所以在數(shù)據(jù)傳輸后期，文獻(xiàn)［12］的能效率反而高于文獻(xiàn)［11］，本文分簇綜合文獻(xiàn)［11-12］的思想，平均能效率相較于文獻(xiàn)［11-12，17］分別提高了至少28.62%、39.91%和13.94%。

在圖5（b）節(jié)點(diǎn)能量異構(gòu)環(huán)境下，隨著數(shù)據(jù)傳輸輪數(shù)的加大，各算法的網(wǎng)絡(luò)能效率都呈現(xiàn)下降的趨勢(shì)，由于節(jié)點(diǎn)的能量不一，文獻(xiàn)［11］依靠時(shí)間片激發(fā)分簇會(huì)增加網(wǎng)絡(luò)無(wú)用的能量消耗使剩余能量少的節(jié)點(diǎn)早死，所以數(shù)據(jù)傳輸后期無(wú)線網(wǎng)絡(luò)失效，能效率變?yōu)?；隨著節(jié)點(diǎn)剩余能量降低，文獻(xiàn)［12］分簇頻率加大，無(wú)用消耗也隨之增加，能效率會(huì)在傳輸后期下降更快，但總體上要強(qiáng)于文獻(xiàn)［11］；文獻(xiàn)［17］是以固定的網(wǎng)絡(luò)延時(shí)Tm為基準(zhǔn)，剩余能量越多的簇頭工作時(shí)延越長(zhǎng)，這種設(shè)計(jì)在異構(gòu)環(huán)境中與文獻(xiàn)［12］思想相似，在網(wǎng)絡(luò)運(yùn)行前期，簇頭轉(zhuǎn)換次數(shù)較少，能效率較高，但到后期能效率也會(huì)較快降低；在本文分簇算法平均能效率相較于文獻(xiàn)［11-12，17］分別提高了至少48.22%、37.14%和20.23%。

圖5 4種算法在不同環(huán)境下的網(wǎng)絡(luò)能效率

4 結(jié) 語(yǔ)

本文提出了一種融合時(shí)間和剩余能量激發(fā)的分簇算優(yōu)化算法。分析了基于時(shí)間和剩余能量激發(fā)分簇算法能效率受限的原因，重新定義剩余能量閾值，并以此作為激發(fā)簇頭競(jìng)爭(zhēng)的臨界條件，避免網(wǎng)絡(luò)后期節(jié)點(diǎn)能量降低時(shí)簇頭頻繁競(jìng)爭(zhēng)帶來(lái)的能耗，從而整體上提高整個(gè)無(wú)線網(wǎng)絡(luò)的能效率。仿真實(shí)驗(yàn)表明，與其他3 種簇頭輪換算法相比，本文算法不僅有較高的能效率，還大大延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。