馬威風(fēng)，陳桂芬

(長(zhǎng)春理工大學(xué) 電子信息工程學(xué)院，吉林 長(zhǎng)春 130022)

0　引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量廉價(jià)的微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信方式形成的一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)[1]。隨著傳感器、嵌入式計(jì)算、通信和計(jì)算機(jī)網(wǎng)絡(luò)等技術(shù)的日趨成熟，無(wú)線自組織網(wǎng)絡(luò)的各種應(yīng)用逐漸成為可能，成為21世紀(jì)信息產(chǎn)業(yè)的重要支柱[2]。WSNs節(jié)點(diǎn)作為微小器件只能配備有限電源，而且多數(shù)部署在危險(xiǎn)地帶或人難以到達(dá)的環(huán)境中，后期維護(hù)難以實(shí)現(xiàn)，使節(jié)點(diǎn)壽命很大程度上依賴電池壽命，因此，如何減少節(jié)點(diǎn)的能量消耗對(duì)于傳感器網(wǎng)絡(luò)而言至關(guān)重要[3]，同時(shí)也是設(shè)計(jì)協(xié)議時(shí)面臨的重要問(wèn)題之一。

WSNs中節(jié)點(diǎn)布設(shè)密度大，節(jié)點(diǎn)感知到的數(shù)據(jù)存在大量的冗余信息[4]，而通信耗能為總能耗的主要部分。因此，必須嚴(yán)格控制數(shù)據(jù)包傳輸量來(lái)減少不必要的開(kāi)銷(xiāo)。以LEACH[5]為典型代表的分簇算法將節(jié)點(diǎn)分為簇頭和簇內(nèi)節(jié)點(diǎn)，簇內(nèi)節(jié)點(diǎn)負(fù)責(zé)采集數(shù)據(jù)，而簇頭負(fù)責(zé)管理簇內(nèi)節(jié)點(diǎn)，并進(jìn)行簇內(nèi)節(jié)點(diǎn)信息的采集、融合及轉(zhuǎn)發(fā)[6]。LEACH算法在一定程度上實(shí)現(xiàn)了能耗均衡，但存在簇頭分布位置的隨機(jī)性、選取簇頭未考慮節(jié)點(diǎn)剩余能量以及與基站直接進(jìn)行數(shù)據(jù)傳輸導(dǎo)致能耗過(guò)大的問(wèn)題[7]。

EEUC[8]算法采用非均勻分簇和簇間多跳的方式。網(wǎng)絡(luò)被劃分為大小不等的簇，遠(yuǎn)離基站的簇內(nèi)節(jié)點(diǎn)較多，避免過(guò)快消耗能量，而且簇間多跳路由方式可以進(jìn)一步均衡簇頭能量消耗[9]，較好地解決了“熱區(qū)”問(wèn)題[10]。

DEEUC[11]算法在EEUC基礎(chǔ)上優(yōu)化了簇頭選舉和路由選擇，算法中候選簇頭由上一輪簇頭根據(jù)簇內(nèi)剩余能量選出，再通過(guò)能量因素選出最終簇頭。下一跳路由簇頭選擇正向單位能量消耗最小的鄰簇首，有效地提高簇頭間傳輸數(shù)據(jù)的效率。

本文基于非均勻分簇算法提出一種能量均衡多跳非均勻分簇算法(Energy Balance Multi-hops Uneven Clustering, EBMUC)，算法首先比較節(jié)點(diǎn)剩余能量與鄰節(jié)點(diǎn)平均剩余能量選出候選簇頭，再考慮距離、能量和鄰節(jié)點(diǎn)數(shù)因素選出最終簇頭；簇構(gòu)造在節(jié)點(diǎn)入簇公式[12]中加入簇頭剩余能量；簇間選擇中繼節(jié)點(diǎn)協(xié)助傳輸數(shù)據(jù)，數(shù)據(jù)通過(guò)中繼節(jié)點(diǎn)和鄰簇頭多跳傳輸?shù)交?BS)，進(jìn)一步延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

1　相關(guān)理論

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

正方形監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)分布N個(gè)周期性收集數(shù)據(jù)的WSNs節(jié)點(diǎn)，假設(shè)：(1)BS位于監(jiān)測(cè)區(qū)域邊緣，BS和節(jié)點(diǎn)部署后位置不再變動(dòng)；(2)節(jié)點(diǎn)具有全網(wǎng)絡(luò)唯一的標(biāo)識(shí)ID號(hào)，節(jié)點(diǎn)同構(gòu)且具備一定的存儲(chǔ)能力，可以由信號(hào)強(qiáng)度估算距離；(3)BS能夠與全網(wǎng)絡(luò)的節(jié)點(diǎn)通信，通信方式為半雙工；(4)無(wú)線信道對(duì)稱，數(shù)據(jù)傳輸過(guò)程中融合數(shù)據(jù)減少數(shù)據(jù)量，融合單位數(shù)據(jù)耗能相同；(5)忽略外界影響，節(jié)點(diǎn)周期性采集數(shù)據(jù)并始終有數(shù)據(jù)傳輸?shù)紹S。

1.2　能量模型

本文采用文獻(xiàn)[13]中的無(wú)線通信能耗模型，kbit的數(shù)據(jù)包發(fā)送到距離d的一個(gè)節(jié)點(diǎn)，能耗主要由無(wú)線信號(hào)收發(fā)和功率放大產(chǎn)生，功放器件的耗能與環(huán)境和距離密切相關(guān)，可分為自由空間模型和多徑衰落模型。發(fā)送模塊能耗計(jì)算如式(1)所示：

(1)

ERx(k)=kEelec

(2)

1.3　最優(yōu)簇?cái)?shù)目和最優(yōu)簇通信半徑

采用文獻(xiàn)[13]中的方法計(jì)算最優(yōu)簇?cái)?shù)目(mopt)，假定在一個(gè)M×M的區(qū)域內(nèi)均勻部署N個(gè)節(jié)點(diǎn)，產(chǎn)生m個(gè)簇，m個(gè)簇的總能耗如式(3)所示：

(3)

對(duì)式(3)中m求導(dǎo)并令式等于0, 求出mopt，由mopt計(jì)算均勻分簇情況下最優(yōu)簇通信半徑ropt、最優(yōu)跳數(shù)τopt，如式(4)所示，式中為向上取整。

(4)

2　EBMUC協(xié)議算法設(shè)計(jì)

(1)簇頭選擇：BS首先廣播初始化消息(包括mopt、ropt和d0)。節(jié)點(diǎn)收到消息后由信號(hào)強(qiáng)度估算到BS的距離dtoBS(i)，然后節(jié)點(diǎn)以ropt為半徑向周?chē)徆?jié)點(diǎn)廣播消息(包括節(jié)點(diǎn)剩余能量和到BS距離)，節(jié)點(diǎn)收到鄰節(jié)點(diǎn)消息后建立鄰節(jié)點(diǎn)信息表并統(tǒng)計(jì)鄰節(jié)點(diǎn)個(gè)數(shù)，計(jì)算其鄰節(jié)點(diǎn)平均剩余能量。若節(jié)點(diǎn)剩余能量大于鄰節(jié)點(diǎn)平均剩余能量，則當(dāng)選候選簇頭并廣播消息，反之節(jié)點(diǎn)進(jìn)入休眠。候選簇頭收到鄰候選簇頭的消息后建立鄰候選簇頭信息表，然后計(jì)算并廣播適應(yīng)值(如式(5)所示)，通過(guò)交換適應(yīng)值選擇值最大的候選簇頭為最終簇頭并廣播當(dāng)選消息，休眠中的節(jié)點(diǎn)收到最終簇頭的消息后喚醒。

f(i)=w1N+w2E+w3D

(5)

(2)簇結(jié)構(gòu)形成：①簇內(nèi)結(jié)構(gòu)。節(jié)點(diǎn)收到最終簇頭當(dāng)選消息后建立簇頭信息表并估算到各簇頭距離，對(duì)每個(gè)簇頭的飽和度進(jìn)行判斷(即表達(dá)式P2)，由式(6)選擇值大于0的簇頭發(fā)送加入消息(包括剩余能量和基站距離)。

Add(i, CHj)=αP1+(1-α)P2

(6)

簇頭記錄節(jié)點(diǎn)發(fā)送的加入消息(若收到競(jìng)選簇頭失敗的候選簇頭的消息則將其標(biāo)記為副簇頭)，根據(jù)成員節(jié)點(diǎn)數(shù)分配發(fā)送數(shù)據(jù)幀間隔。成員數(shù)較少的簇對(duì)應(yīng)幀時(shí)間間隔較大，反之，幀時(shí)間間隔較小，以此來(lái)保證單位時(shí)間內(nèi)不同簇內(nèi)數(shù)目不同的節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)次數(shù)相同。最后，簇頭采用TDMA方式向簇內(nèi)成員廣播工作時(shí)隙。

②簇間結(jié)構(gòu)。簇頭收到周?chē)渌罱K簇頭當(dāng)選消息后建立鄰簇頭信息表，計(jì)算并廣播簇間數(shù)據(jù)轉(zhuǎn)發(fā)代價(jià)值(如式(7)所示)，通過(guò)比較代價(jià)值來(lái)決定下一跳簇頭。

(7)

下一跳簇頭確定后，若簇頭間距離大于d0，則在傳輸數(shù)據(jù)的簇內(nèi)選擇靠近下一跳簇頭的中繼節(jié)點(diǎn)輔助傳輸數(shù)據(jù)，反之則簇頭間傳輸數(shù)據(jù)。中繼節(jié)點(diǎn)由節(jié)點(diǎn)剩余能量與到兩簇頭間的距離兩因素確定(如式(8)所示)，其中Erel、drel to CHj分別為中繼節(jié)點(diǎn)剩余能量和到下一跳簇頭距離。

(8)

(3)數(shù)據(jù)傳輸：簇成員節(jié)點(diǎn)在分配的時(shí)隙段向距離自己最近的副簇頭傳輸數(shù)據(jù)(若無(wú)副簇頭，則通過(guò)鄰節(jié)點(diǎn)，若無(wú)鄰節(jié)點(diǎn)則增大功率與簇頭之間通信，將數(shù)據(jù)多跳傳輸至簇頭)，副簇頭收集并融合數(shù)據(jù)后向簇頭轉(zhuǎn)發(fā)，每次多跳傳輸過(guò)程中都有數(shù)據(jù)融合，數(shù)據(jù)傳輸后簇成員節(jié)點(diǎn)進(jìn)入休眠狀態(tài)；對(duì)于簇間數(shù)據(jù)傳輸則根據(jù)簇頭間的距離情況選擇中繼節(jié)點(diǎn)輔助數(shù)據(jù)傳輸。同樣，到BS距離小于d0的節(jié)點(diǎn)以單跳形式向BS傳輸數(shù)據(jù)，大于則多跳傳輸?shù)紹S。此外，靠近BS的簇頭或普通節(jié)點(diǎn)并不是有數(shù)據(jù)就立即向BS傳輸，而是等待數(shù)據(jù)量匯聚到一定程度后再向BS傳輸，這樣階段地一次性向BS傳送數(shù)據(jù)，大大減少了數(shù)據(jù)包的發(fā)送次數(shù)，從而使得距離BS較遠(yuǎn)的節(jié)點(diǎn)可以向基站附近匯聚更多信息量的數(shù)據(jù)。網(wǎng)絡(luò)整體示意圖如圖1所示。

圖1　EBMUC協(xié)議節(jié)點(diǎn)示意圖

3　仿真實(shí)驗(yàn)與分析

3.1　仿真實(shí)驗(yàn)

在1 000 m×1 000 m區(qū)域中仿真比較了LEACH、EEUC、DEEUC和EBMUC，節(jié)點(diǎn)數(shù)為1 000個(gè)，初始能量為0.5 J，BS坐標(biāo)為(1 000,500)。成簇權(quán)值α=0.6，w1、w2與w3分別取0.3、0.4和0.3，距離常數(shù)d0為87 m。其他參數(shù)見(jiàn)表1。

表1　仿真相關(guān)參數(shù)

3.2　仿真實(shí)驗(yàn)結(jié)果分析

通過(guò)仿真網(wǎng)絡(luò)的生存時(shí)間、BS接收數(shù)據(jù)量和網(wǎng)絡(luò)剩余能量來(lái)研究本文算法的性能。

3.2.1網(wǎng)絡(luò)生存時(shí)間

網(wǎng)絡(luò)生存時(shí)間是衡量網(wǎng)絡(luò)性能的重要指標(biāo)之一[14]，表2統(tǒng)計(jì)了圖2中四種算法的第一個(gè)死亡節(jié)點(diǎn)(FND)和死亡一半節(jié)點(diǎn)(HND)的輪數(shù),若是以HND作為網(wǎng)絡(luò)生存時(shí)間評(píng)判標(biāo)準(zhǔn)，四種算法網(wǎng)絡(luò)生存時(shí)間分別為215、273、297和362，與LEACH比較，EEUC采用了非均勻分簇的方式，很好地解決了“熱區(qū)”問(wèn)題，延遲了FND的出現(xiàn)；DEEUC在EEUC的基礎(chǔ)上優(yōu)化了簇頭選取以及最小正向單位路由選擇，能耗比EEUC算法得到進(jìn)一步降低；而本文的EBMUC算法在由候選簇頭選取簇頭時(shí)，考慮了能量、距離以及鄰節(jié)點(diǎn)數(shù)等因素，比DEEUC由候選簇頭通過(guò)能量因素競(jìng)爭(zhēng)選取出的簇頭更為合理，出現(xiàn)FND輪數(shù)也更遲。EEUC、DEEUC以及本文算法會(huì)在某個(gè)時(shí)間段出現(xiàn)節(jié)點(diǎn)迅速死亡，產(chǎn)生這種現(xiàn)象的原因是由于這三種算法覆蓋面積遠(yuǎn)大于LEACH，網(wǎng)絡(luò)中節(jié)點(diǎn)能量得到均衡消耗，會(huì)在某一刻存活的節(jié)點(diǎn)少于LEACH中的節(jié)點(diǎn)數(shù)。EBMUC由于中繼節(jié)點(diǎn)的加入，數(shù)據(jù)多跳傳輸?shù)紹S，更好地均衡了簇間能量消耗，所以后期節(jié)點(diǎn)死亡速度略快于DEEUC。

圖2　存活節(jié)點(diǎn)數(shù)對(duì)比圖

算法名稱FND輪數(shù)HND輪數(shù)LEACH34215EEUC201273DEEUC236297EBMUC298362

3.2.2基站BS接收數(shù)據(jù)量

圖3為四種算法BS接收數(shù)據(jù)量對(duì)比圖，在FND之前，EBMUC中基站收到的數(shù)據(jù)包總量約是LEACH算法的1.5倍，約是EEUC與DEEUC的1.3、1.1倍。這是因?yàn)镋BMUC改進(jìn)的簇頭選擇與簇間通信方式，延長(zhǎng)了網(wǎng)絡(luò)的生命周期，使數(shù)據(jù)量有所增加，在EBMUC的HND之前，LEACH、EEUC和DEEUC中的大部分節(jié)點(diǎn)已經(jīng)死亡，網(wǎng)絡(luò)存在覆蓋率低的區(qū)域，節(jié)點(diǎn)難以將數(shù)據(jù)傳輸?shù)紹S。

圖3　基站BS接收數(shù)據(jù)量對(duì)比圖

3.2.3網(wǎng)絡(luò)剩余能量

圖4比較了四種算法的網(wǎng)絡(luò)剩余能量隨運(yùn)行輪數(shù)的變化情況。EEUC、DEEUC和EBMUC的多跳非均勻策略比單跳均勻的LEACH有明顯的節(jié)能優(yōu)勢(shì)。EBMUC網(wǎng)絡(luò)剩余能量在700輪之前大于其他三種算法，體現(xiàn)了本文算法的能量利用高效性。之后，由于EBMUC覆蓋面積較大，消耗了一定的網(wǎng)絡(luò)剩余能量，因此小于LEACH算法，同樣地，EEUC和DEEUC也出現(xiàn)了這種情況。EEUC、DEEUC和EBMUC相比，DEEUC中簇頭指定能量最高的節(jié)點(diǎn)為下輪的簇頭，均衡了節(jié)點(diǎn)間能耗同時(shí)也避免多個(gè)節(jié)點(diǎn)成為候選簇頭參與最終簇頭競(jìng)爭(zhēng)，節(jié)省了網(wǎng)絡(luò)能量。而EBMUC是先選擇候選簇頭，再由候選簇頭綜合考慮能量、距離以及鄰節(jié)點(diǎn)數(shù)來(lái)競(jìng)爭(zhēng)最終簇頭，得到的簇頭更為合理，同時(shí)在節(jié)點(diǎn)入簇時(shí)考慮了簇頭能量與簇規(guī)模，有效地減輕了簇頭負(fù)擔(dān)，降低了網(wǎng)絡(luò)能耗。

圖4　網(wǎng)絡(luò)剩余能量對(duì)比圖

4　結(jié)論

本文在研究現(xiàn)有的非均勻分簇算法基礎(chǔ)上，設(shè)計(jì)了一種能量均衡的多跳非均勻分簇算法，算法考慮了節(jié)點(diǎn)的距離、能量以及鄰居數(shù)等因素來(lái)選取最終的簇頭節(jié)點(diǎn)。節(jié)點(diǎn)入簇階段考慮了簇頭的能量與距離，同時(shí)也考慮了簇頭的鄰節(jié)點(diǎn)數(shù)，避免形成的簇結(jié)構(gòu)規(guī)模過(guò)大。為了防止簇頭間出現(xiàn)遠(yuǎn)距離傳輸數(shù)據(jù)的情況，采取選擇待傳輸數(shù)據(jù)簇內(nèi)最遠(yuǎn)處的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)來(lái)輔助數(shù)據(jù)傳輸，縮短數(shù)據(jù)傳輸路徑，最小化簇間數(shù)據(jù)通信開(kāi)銷(xiāo)。與LEACH、EEUC和DEEUC算法相比，本文算法平衡了節(jié)點(diǎn)能耗，延緩了網(wǎng)絡(luò)中死亡節(jié)點(diǎn)的出現(xiàn)輪數(shù)，從而延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

[1] 蘇兵,張鈺婧.基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)測(cè)量與控制,2016, 24(2):325-327.

[2] 劉半藤,周瑩,陳友榮,等.基于移動(dòng)-能量代價(jià)函數(shù)的無(wú)線自組織網(wǎng)絡(luò)路由策略研究[J].傳感技術(shù)學(xué)報(bào), 2017,30(2):302-305.

[3] 林德鈺,王泉,劉伎昭.無(wú)線傳感網(wǎng)的移動(dòng)與靜態(tài)sink相結(jié)合的節(jié)能策略[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2016,48(11):162-168.

[4] 張策,張霞,李鷗,等.基于CS的無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)分簇?cái)?shù)據(jù)收集算法[J].計(jì)算機(jī)研究與發(fā)展,2016, 53(9):2000-2008.

[5] ZHANG X L, LI Q, FU Y, et al. An energy balancing LEACH algorithm for wireless sensor network[C]. International Conference on Electrical, Computer Engineering and Electronics, 2015:752-756.

[6] 張軍強(qiáng),王汝傳,黃海平.基于分簇的無(wú)線多媒體傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合方案研究[J].電子與信息學(xué)報(bào), 2014,36(1):8-14.

[7] SALMABADI H, ADIBNIA F, SARRAM M A. An improvement on LEACH protocol (EZ-LEACH)[C]. International Conference on Knowledge-Based Engineering and Innovation(KBEI)，2015:956-970.

[8] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]. IEEE International Conference on Mobile Ad-hoc and Sensor Systems Conference， IEEE, 2005:597-604.

[9] 劉洲洲,王福豹,張克旺.基于混合蛙跳算法的非均勻分簇WSNs路由協(xié)議[J].計(jì)算機(jī)應(yīng)用研究,2013,30(7):2173-2176.

[10] 岳麗穎, 戴月明, 吳定會(huì). 一種能量?jī)?yōu)化WSNs非均勻分簇路由協(xié)議[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015(15)： 80-85.

[11] 曾華圣, 熊慶宇, 杜敏,等. 一種分布式能量高效的WSNs非均勻分簇路由協(xié)議[J]. 傳感器與微系統(tǒng), 2014, 33(3):146-149.

[12] 江禹生, 李萍, 馬超. 一種能量高效的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J]. 傳感器與微系統(tǒng), 2014, 33(2):146-149.

[13] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[14] 劉半藤, 周瑩, 陳友榮,等. 基于加權(quán)路由思想的無(wú)線自組織網(wǎng)絡(luò)生存時(shí)間優(yōu)化算法研究[J]. 傳感技術(shù)學(xué)報(bào), 2017,30(3):463-466.