賈銀亮，張馳宇，梁康武

(南京航空航天大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210016)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是由部署在監(jiān)測(cè)區(qū)域內(nèi)的大量傳感器節(jié)點(diǎn)，通過(guò)無(wú)線通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)[1]。其依賴于傳感器、無(wú)線通信、嵌入式系統(tǒng)等技術(shù)，具有低功耗、低成本、分布式和自組織等特點(diǎn)。隨著節(jié)點(diǎn)體積的縮小、能耗的降低和性能的提升，無(wú)線傳感器網(wǎng)絡(luò)已開(kāi)始投入實(shí)用。

在無(wú)線傳感器網(wǎng)絡(luò)的研究中，能效一直是熱點(diǎn)問(wèn)題。為了延長(zhǎng)網(wǎng)絡(luò)生存周期，相關(guān)的軟硬件得到了大量的研究。分簇算法可以有效延長(zhǎng)網(wǎng)絡(luò)生存周期，而分簇算法中，簇頭的選擇對(duì)網(wǎng)絡(luò)能耗有較大影響[2]。本文對(duì)分簇算法的簇頭選擇進(jìn)行研究，提出了一種新的算法。

1 相關(guān)工作

LEACH算法[2,3]使用輪的概念，一輪由所有節(jié)點(diǎn)分簇的建立階段，和數(shù)據(jù)采集、傳遞、處理的穩(wěn)定階段組成。在建立階段，各個(gè)節(jié)點(diǎn)產(chǎn)生0～1之間的隨機(jī)數(shù)。對(duì)節(jié)點(diǎn)i而言，若該數(shù)小于閾值T(i)，則該節(jié)點(diǎn)成為簇頭

(1)

式中p為簇頭對(duì)存活節(jié)點(diǎn)的占比；r為當(dāng)前循環(huán)的輪次；G為在最近 1/p輪中未成為簇頭的節(jié)點(diǎn)集合[4]。LEACH算法隨機(jī)性較強(qiáng)，實(shí)際工作中,由于簇頭的能耗各不相同，仍會(huì)帶來(lái)節(jié)點(diǎn)能耗不均問(wèn)題[5]。

針對(duì)LEACH算法的缺點(diǎn)，國(guó)內(nèi)外的研究者提出了許多改進(jìn)方案。根據(jù)節(jié)點(diǎn)剩余能量來(lái)選擇簇頭可以延長(zhǎng)網(wǎng)絡(luò)生存周期。文獻(xiàn)[6]引入仿生學(xué)，模仿蜜蜂的行為來(lái)選擇簇頭；文獻(xiàn)[7]根據(jù)平均能量預(yù)測(cè)和歷史能耗來(lái)選擇簇頭；文獻(xiàn)[8]通過(guò)對(duì)節(jié)點(diǎn)剩余能量的估算實(shí)現(xiàn)對(duì)簇頭選舉機(jī)制的優(yōu)化，并提出“生命游戲”睡眠調(diào)度模型和利用鄰居節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的多跳通信方式；文獻(xiàn)[9]通過(guò)簇內(nèi)進(jìn)一步細(xì)分將整個(gè)網(wǎng)絡(luò)劃分為3個(gè)層次。上述算法在不同程度上提高了網(wǎng)絡(luò)生存周期，但較為復(fù)雜，增加了節(jié)點(diǎn)的負(fù)擔(dān)。

由于LEACH協(xié)議分簇的隨機(jī)性，不同輪簇頭數(shù)量不同，簇頭的能耗也不同。LEACH-MAC從減少能耗的角度研究了最佳簇頭數(shù)k，在選擇簇頭時(shí)逐個(gè)選擇，直到簇頭數(shù)量達(dá)到k[10]，從而提高了網(wǎng)絡(luò)生存周期。

文獻(xiàn)[11]提出了WRECS(weighted residual energy-based cluster head selection)算法，根據(jù)簇內(nèi)節(jié)點(diǎn)數(shù)量的不同，使簇頭節(jié)點(diǎn)在之后若干輪不能再次成為簇頭，從而達(dá)到了平衡節(jié)點(diǎn)能耗的目的。

本文提出了一種基于多重競(jìng)爭(zhēng)的簇頭(multiple competitive cluster head,MCCH)選擇算法，根據(jù)簇頭的剩余能量、鄰節(jié)點(diǎn)數(shù)、到已選定簇頭的距離等因素選擇簇頭，提高了網(wǎng)絡(luò)的生存周期。

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

對(duì)無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)假設(shè)如下:

1)節(jié)點(diǎn)隨機(jī)布設(shè)在邊長(zhǎng)為L(zhǎng)的正方形區(qū)域內(nèi)，位置信息未知。節(jié)點(diǎn)能量有限，并能感知自身的剩余能量。

2)節(jié)點(diǎn)可以收發(fā)數(shù)據(jù)，發(fā)送信號(hào)的強(qiáng)度可變。節(jié)點(diǎn)可以感知接收信號(hào)的強(qiáng)度，通過(guò)與發(fā)送信號(hào)的強(qiáng)度比較，可以估算到發(fā)送節(jié)點(diǎn)的距離。

3)節(jié)點(diǎn)工作相互獨(dú)立，各個(gè)節(jié)點(diǎn)具有唯一的ID，均可成為簇頭。簇頭直接發(fā)送信息到匯聚節(jié)點(diǎn)。

4)匯聚節(jié)點(diǎn)位置固定，具有較強(qiáng)的處理能力。相對(duì)于一般節(jié)點(diǎn)，匯聚節(jié)點(diǎn)的能量可以認(rèn)為無(wú)限。

文獻(xiàn)[12]采用的能量模型比較典型，即當(dāng)傳輸距離為d，發(fā)送數(shù)據(jù)長(zhǎng)度為qbit時(shí)，能量消耗如式(2)

(2)

式中ETx,ERx分別為收、發(fā)能耗；Eelec為發(fā)送或接收電路每完成1 bit數(shù)據(jù)收發(fā)消耗的能量。dcorssover為閾值，若d

3 MCCH選擇算法

MCCH是一種分簇算法，將網(wǎng)絡(luò)的工作狀態(tài)劃分成輪，一輪包括建立階段和穩(wěn)定階段。建立階段的主要工作是選舉本輪的簇頭。

(3)

ηi=1-min[ni×p,1]

(4)

為了使ni大的節(jié)點(diǎn)優(yōu)先成為簇頭，設(shè)置延時(shí)時(shí)間

ti=(ηi+γ)×t0

(5)

式中t0為選定的時(shí)間;γ為隨機(jī)數(shù)且γ∈[0,1]。對(duì)于節(jié)點(diǎn)i，若其可以成為簇頭，則在簇頭選取時(shí)首先延時(shí)ti。ti到時(shí)若簇頭選取仍未結(jié)束，則i成為簇頭。

一般來(lái)說(shuō)，簇頭均勻分布可以減少能耗[13]，本文通過(guò)調(diào)整ti來(lái)促使簇頭均勻分布。若一個(gè)節(jié)點(diǎn)成為簇頭，則以事先選定的強(qiáng)度發(fā)送建簇信息。其他節(jié)點(diǎn)接收該信息，根據(jù)接收信號(hào)的強(qiáng)度估算到該簇頭的距離l。并按式(6)更新延時(shí)時(shí)間

(6)

算法步驟如下：

3)延時(shí)結(jié)束時(shí)該節(jié)點(diǎn)成為簇頭，廣播建簇信息，信息中包含自身的ID。其他節(jié)點(diǎn)接收建簇信息，估算距離，按式(6)更自身延時(shí)時(shí)間。

4)匯聚節(jié)點(diǎn)接收建簇信息，當(dāng)收到P×N個(gè)建簇信息后廣播簇頭選舉結(jié)束信息。未成為簇頭的節(jié)點(diǎn)收到該信息后，根據(jù)收到的信號(hào)強(qiáng)度，加入最近的簇頭，向其發(fā)送入簇信息并附上自身ID。簇頭接收入簇信息，向發(fā)出請(qǐng)求的節(jié)點(diǎn)返回一確認(rèn)信息，完成簇的建立。

5)節(jié)點(diǎn)采集信息，通過(guò)時(shí)分多址(time division multiple access,TDMA)方式送給簇頭并附上自身剩余能量信息。簇頭進(jìn)行數(shù)據(jù)融合后發(fā)給匯聚節(jié)點(diǎn)。

6)匯聚節(jié)點(diǎn)接收采集的信息數(shù)據(jù)并收集和各個(gè)節(jié)點(diǎn)的剩余能量信息。一輪結(jié)束后返回步驟(1)循環(huán)執(zhí)行。

4 系統(tǒng)仿真

使用NS2進(jìn)行仿真，比較了LEACH，WRECS，LEACH-MAC和MCCH 4種算法的效果。仿真的具體環(huán)境為100個(gè)節(jié)點(diǎn)分布在邊長(zhǎng)100 m的正方形區(qū)域內(nèi)，匯聚節(jié)點(diǎn)在正方形中心，其他參數(shù)設(shè)置：εfs為10 pJ/bit/m2，εmp為0.001 3 pJ/bit/m4，Eelec為50 nJ/bit，dcorssover為87 m，p為0.05。

圖1通過(guò)仿真數(shù)據(jù)比較了4種算法在隨機(jī)選取的10輪中每一輪的能耗。LEACH算法在簇頭數(shù)量、位置上存在較大的隨機(jī)性，且未考慮剩余能量，所以，能耗最大且不同輪的能耗差異較大。WRECS算法優(yōu)先選擇剩余能量高的節(jié)點(diǎn)做簇頭，在一定程度上實(shí)現(xiàn)了節(jié)點(diǎn)間的能耗均勻，但該算法不能降低能耗。LEACH-MAC算法可以確保合適的簇頭數(shù)量，從而減少了能耗和不同輪之間的能耗差異。MCCH算法根據(jù)剩余能量、鄰節(jié)點(diǎn)數(shù)、簇頭位置等因素進(jìn)行競(jìng)爭(zhēng)，在一定程度上實(shí)現(xiàn)了簇頭的均勻分布，所以能耗較小。

圖1 網(wǎng)絡(luò)能耗對(duì)比

圖2為4種算法網(wǎng)絡(luò)生命周期的仿真結(jié)果。從圖中可見(jiàn)，LEACH算法的生命周期最短。WRECS算法考慮了節(jié)點(diǎn)能耗的均勻，在一定程度上延遲了節(jié)點(diǎn)開(kāi)始死亡的時(shí)間，但由于該算法不能降低能耗，所以,節(jié)點(diǎn)全部死亡的時(shí)間早于LEACH算法。LEACH-MAC算法穩(wěn)定了簇頭數(shù)量，從而減少了能耗，但由于簇頭分布不均勻等因素，網(wǎng)絡(luò)壽命提高幅度有限。MCCH算法在剩余能量較多的節(jié)點(diǎn)中選擇簇頭，并優(yōu)先選擇鄰節(jié)點(diǎn)多且到已選定簇頭距離合適的節(jié)點(diǎn)成為新的簇頭，從而提高了網(wǎng)絡(luò)的生存周期。

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

5 結(jié) 論

提出了MCCH算法,算法中節(jié)點(diǎn)根據(jù)多種因素進(jìn)行競(jìng)爭(zhēng)成為簇頭，剩余能量較多，選擇鄰節(jié)點(diǎn)多，到已選定簇頭距離合適的節(jié)點(diǎn)成為簇頭的可能性更大。通過(guò)仿真證明了該算法能延長(zhǎng)網(wǎng)絡(luò)生存周期。下一步的工作可以研究簇覆蓋范圍與能耗的關(guān)系，根據(jù)能耗動(dòng)態(tài)的調(diào)整簇覆蓋范圍。

[1] Kulkarni R V,F?Rster A,Venayagamoorthy G K.Computational intelligence in wireless sensor networks:A survey[J].IEEE Communications Surveys & Tutorials,2011,13(1):68-96.

[2] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2000,1(4):660-670.

[3] Al-Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].IEEE Wireless Communications,2004,11(6):6-28.

[4] Nayebi A,Sarbazi-Azad H.Performance modeling of the LEACH protocol for mobile wireless sensor networks[J].Journal of Parallel & Distributed Computing,2011,71(6):812-821.

[5] Roseline R A,Sumathi P.Local clustering and threshold sensitive routing algorithm for wireless sensor networks[C]∥2012 International Conference on Devices,Circuits and Systems(ICDCS),IEEE,2012:365-369.

[6] Saleem M,Ullah I,Farooq M.BeeSensor:An energy-efficient and scalable routing protocol for wireless sensor networks[J].Information Sciences,2012,200(2):38-56.

[7] 洪 榛,俞 立,張貴軍.多級(jí)異構(gòu)無(wú)線傳感網(wǎng)高效動(dòng)態(tài)聚簇策略研究[J].自動(dòng)化學(xué)報(bào),2013,39(4):454-460.

[8] 楊永健,賈 冰,王 杰.無(wú)線傳感器網(wǎng)絡(luò)中LEACH協(xié)議的改進(jìn)[J].北京郵電大學(xué)學(xué)報(bào),2013,36(1):105-109.

[9] Chen Y L,Wang N C,Shih Y N.Improving low-energy adaptive cllustering hierarchy architectures with sleep mode for wireless sensor networks[J].Wireless Personal Communications，2014,75(1)：349-368.

[10] Batra P K,Kant K.LEACH-MAC:A new cluster head selection algorithm for wireless sensor networks[J].Wireless Networks,2016,22(1):1-12.

[11] Bao X,Xie J,Nan L,et al.WRECS:An improved cluster heads selection algorithm for WSNs[J].Journal of Software,2014,9(2):78-89.

[12] Kumar D, Aseri T C, Patel R B.EEHC:Energy efficient heterogeneous clustered scheme for wireless sensor networks[J].Computer Communications, 2009, 32(4):662-667.

[13] Su J S,Guo W Z,Yu C L,et al.Fault-tolerance clustering algorithm with load-balance aware in wireless sensor networks[J].Chinese Journal of Computers,2014,37(2):445-456.