王宏志, 武莎莎, 魯曉帆， 胡黃水, 王出航, 郭嫚嫚

(1. 長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春 130012;2. 吉林建筑科技學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院， 長(zhǎng)春 130114；3. 長(zhǎng)春師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130032)

無(wú)線傳感器網(wǎng)絡(luò)(WSNs)是由許多傳感器節(jié)點(diǎn)以多跳或自組織形式組合成的分布式傳感器網(wǎng)絡(luò)[1-2], 在環(huán)境觀察、 軍事應(yīng)用、 建筑監(jiān)控、 醫(yī)療保健、 家居和汽車等領(lǐng)域應(yīng)用廣泛[3]. 無(wú)線傳感器網(wǎng)絡(luò)中由于節(jié)點(diǎn)的工作任務(wù)不同, 因而存在傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗不均勻等問(wèn)題. 無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)在降低網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗、 平衡網(wǎng)絡(luò)能量方面具有重要作用[4-5], 其中分簇算法的設(shè)計(jì)直接影響網(wǎng)絡(luò)能效. 低能量自適應(yīng)聚類層次結(jié)構(gòu)(low-energy adaptive clustering hierarchy, LEACH)[6]是WSNs的第一個(gè)聚類協(xié)議, 其主要思想是通過(guò)節(jié)點(diǎn)輪流充當(dāng)簇頭(cluster head, CH)節(jié)點(diǎn)均衡網(wǎng)絡(luò)能耗, 但CH節(jié)點(diǎn)的選擇未考慮節(jié)點(diǎn)的剩余能量, 將導(dǎo)致網(wǎng)絡(luò)的負(fù)載不均衡. HEED[7](hybrid, energy-efficient, distributed clustering approach for Ad Hoc sensor networks)算法是LEACH算法的一種改進(jìn)算法, 其雖然把節(jié)點(diǎn)的剩余能量作為選擇CH節(jié)點(diǎn)的因素, 但路由階段所需開(kāi)銷較大.

目前, 基于多跳通信及分簇的方法已有很多: 劉志等[8]采用分環(huán)的方式實(shí)現(xiàn)CH節(jié)點(diǎn)間的多跳通信, 但在選取CH節(jié)點(diǎn)時(shí), 未考慮內(nèi)環(huán)CH節(jié)點(diǎn)的剩余能量, 導(dǎo)致某些內(nèi)環(huán)CH節(jié)點(diǎn)的負(fù)荷過(guò)重; 文獻(xiàn)[9]采用一種能量高效的分簇算法, 每輪結(jié)束后都重新選舉CH節(jié)點(diǎn), 減少了能量的浪費(fèi), 但復(fù)雜的參數(shù)限制了網(wǎng)絡(luò)性能; 文獻(xiàn)[10]采用環(huán)形多級(jí)分簇結(jié)構(gòu), 使節(jié)點(diǎn)與基站(base station, BS)間擁有最小的通信能耗; 文獻(xiàn)[11]提出了在不等級(jí)環(huán)模型的最內(nèi)環(huán)引入非均勻分簇的思想, 減少了網(wǎng)絡(luò)中最內(nèi)環(huán)節(jié)點(diǎn)的能量消耗; Sha等[12]提出了基于候選簇頭(CCH)實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā), 不僅減少了CH節(jié)點(diǎn)的負(fù)荷, 也減少了數(shù)據(jù)上傳期間數(shù)據(jù)溢出的可能性, 但增加了網(wǎng)絡(luò)能耗； 文獻(xiàn)[13]的EUSC(energy efficient unequal sector clustering)算法考慮了網(wǎng)絡(luò)中中繼節(jié)點(diǎn)的選擇及節(jié)點(diǎn)的隊(duì)列長(zhǎng)度; 文獻(xiàn)[14]通過(guò)替代技術(shù)為能量受損的CH節(jié)點(diǎn)提供局部補(bǔ)救, 但在循環(huán)選擇替換節(jié)點(diǎn)時(shí), 選為替代節(jié)點(diǎn)的剩余能量閾值是固定的； 文獻(xiàn)[15]通過(guò)使用層間最小能量消耗路由算法建立從CH節(jié)點(diǎn)到BS的路由, 提高了網(wǎng)絡(luò)能效； 文獻(xiàn)[16]以節(jié)點(diǎn)剩余能量和數(shù)據(jù)傳輸能耗為代價(jià)選舉CH節(jié)點(diǎn), 延長(zhǎng)了網(wǎng)絡(luò)生命周期, 但由于距離BS較近的簇較大, 加重了BS附近CH節(jié)點(diǎn)的負(fù)荷.

圖1 網(wǎng)絡(luò)模型Fig.1 Network model

為了解決上述問(wèn)題, 提高網(wǎng)絡(luò)能效和擴(kuò)展性, 本文提出一種基于最優(yōu)簇頭數(shù)的環(huán)形無(wú)線傳感器網(wǎng)絡(luò)分簇算法(CAROCN), 該算法主要將網(wǎng)絡(luò)區(qū)域視為若干個(gè)圓環(huán)組成, 以每個(gè)環(huán)中能量消耗最小為原則計(jì)算出每個(gè)環(huán)中的最優(yōu)簇頭數(shù), 然后將每個(gè)環(huán)按相應(yīng)的最優(yōu)簇頭數(shù)分成若干大小不同的網(wǎng)格, 每個(gè)網(wǎng)格形成一個(gè)簇. 環(huán)形網(wǎng)絡(luò)中最外環(huán)的CH節(jié)點(diǎn)不需轉(zhuǎn)發(fā)上一環(huán)的數(shù)據(jù), 所以本文又單獨(dú)考慮了最外環(huán)的最優(yōu)簇頭數(shù), 且在CH節(jié)點(diǎn)選擇時(shí), 考慮了每個(gè)環(huán)的最優(yōu)簇頭數(shù)與相應(yīng)環(huán)中節(jié)點(diǎn)數(shù)目的比值、 節(jié)點(diǎn)的剩余能量及簇成員(cluster member, CM)節(jié)點(diǎn)到簇頭(CH)節(jié)點(diǎn)的最短距離與CH節(jié)點(diǎn)到BS距離的關(guān)系.

1 CAROCN算法

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

假設(shè)在半徑為R的圓形感測(cè)區(qū)域中均勻分布N個(gè)傳感器節(jié)點(diǎn), BS位于感測(cè)區(qū)域的中心. 網(wǎng)絡(luò)模型如圖1所示, 網(wǎng)絡(luò)環(huán)境設(shè)置如下：

1) 網(wǎng)絡(luò)在初始化后節(jié)點(diǎn)的位置不再發(fā)生變化, BS位于圓形網(wǎng)絡(luò)的圓心處, 且BS將自己的位置信息發(fā)送給所有傳感器節(jié)點(diǎn)；

2) 每個(gè)傳感器節(jié)點(diǎn)的初始能量相同并具有唯一的ID；

3) 所有來(lái)自CM節(jié)點(diǎn)的數(shù)據(jù)由CH節(jié)點(diǎn)融合, 且只允許CH節(jié)點(diǎn)與BS通信；

4) 網(wǎng)絡(luò)中鏈路沒(méi)有沖突和重傳, 并具有很好的連接性.

1.2 最優(yōu)簇頭數(shù)

采用文獻(xiàn)[4]中的能量消耗模型, 計(jì)算距離為d的兩個(gè)節(jié)點(diǎn)之間發(fā)送或接收ubit數(shù)據(jù)所消耗的能量. 能量消耗模型為

(1)

ER(u)=u×Eelec,

(2)

(3)

其中:Eelec為一個(gè)傳感器節(jié)點(diǎn)發(fā)送或接收1 bit數(shù)據(jù)時(shí)電子電路所消耗的能量;εfs為采用自由空間模型時(shí)的放大參數(shù)；εmp為采用多路衰減模型時(shí)的放大參數(shù)；d0為距離閾值, 本文采用自由空間模型. 融合Ni個(gè)傳感器節(jié)點(diǎn)發(fā)送的數(shù)據(jù)所消耗的能量為EDA, 表達(dá)式為

(4)

其中:Eda為融合1 bit數(shù)據(jù)所消耗的能量；u為數(shù)據(jù)包的長(zhǎng)度.

1.2.1 第n環(huán)的最優(yōu)簇?cái)?shù) 最外環(huán)的CH節(jié)點(diǎn)僅需接收CM節(jié)點(diǎn)發(fā)送的數(shù)據(jù), 然后將這些數(shù)據(jù)融合成固定長(zhǎng)度的數(shù)據(jù)轉(zhuǎn)發(fā)給下一環(huán)中的某個(gè)CH節(jié)點(diǎn). 假設(shè)最外環(huán)中每個(gè)簇的節(jié)點(diǎn)數(shù)目為Nn(n≥2,n為正整數(shù)),ρ為節(jié)點(diǎn)面密度, 最外環(huán)最優(yōu)簇頭數(shù)為mn, 每個(gè)簇所對(duì)應(yīng)的扇形圓心角為θn, 則

(5)

(6)

(7)

同一環(huán)中每個(gè)簇傳輸數(shù)據(jù)所消耗的能量相等, 用En表示. 一個(gè)簇的能量消耗包括CH節(jié)點(diǎn)的能量消耗Ech和CM節(jié)點(diǎn)發(fā)送數(shù)據(jù)給CH節(jié)點(diǎn)所消耗的能量Ecm.Ech的表達(dá)式為

(8)

其中:l為數(shù)據(jù)包的長(zhǎng)度；dch為CH節(jié)點(diǎn)與下一跳之間的歐氏距離, 如圖2所示, 其數(shù)學(xué)表達(dá)式為

(9)

圖2中,A和C是最外環(huán)某簇的CH節(jié)點(diǎn),B是A的下一跳CH節(jié)點(diǎn),A和B的坐標(biāo)分別為A=(xn,yn),B=(xn-1,yn-1). 本文采用自由空間模型, 所以dch

(10)

(11)

其中dcc表示同一個(gè)簇中CM節(jié)點(diǎn)到CH節(jié)點(diǎn)的距離, 其平方的期望為

(12)

其中dc為一個(gè)簇中CM節(jié)點(diǎn)到CH節(jié)點(diǎn)的最大距離,dc在模型中的表示如圖3所示.

圖2 簇頭節(jié)點(diǎn)與簇頭節(jié)點(diǎn)之間的距離Fig.2 Distance between CH node and CH node

圖3 非簇頭節(jié)點(diǎn)與簇頭節(jié)點(diǎn)之間的距離Fig.3 Distance between CM node and CH node

其中

(14)

因此, 最外環(huán)總能量消耗Etotal為

把式(9)和式(13)代入式(15), 并對(duì)mn求導(dǎo), 可得最外環(huán)的最優(yōu)簇頭數(shù)為

(16)

其中：

(17)

1.2.2 第i環(huán)的最優(yōu)簇頭數(shù) 除最外環(huán)簇的CH節(jié)點(diǎn)外, 其他環(huán)中的CH節(jié)點(diǎn)不僅要接收該簇中CM節(jié)點(diǎn)發(fā)送的數(shù)據(jù), 同時(shí)也要接收上一環(huán)中某CH節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù), 將這些數(shù)據(jù)進(jìn)行融合, 然后轉(zhuǎn)發(fā)到下一跳接收節(jié)點(diǎn). 設(shè)第i(i=1,2,…,n-1)環(huán)中每個(gè)環(huán)扇的節(jié)點(diǎn)數(shù)為Ni, 第i環(huán)的最優(yōu)簇頭數(shù)為mi, 則第i環(huán)中每個(gè)簇所對(duì)應(yīng)的扇形圓心角θi為

(18)

(19)

(21)

(22)

(23)

其中:dcc*為第i環(huán)中CM節(jié)點(diǎn)到CH節(jié)點(diǎn)的距離；dc*為第i環(huán)中CM節(jié)點(diǎn)到CH節(jié)點(diǎn)的最大距離, 由圖3及式(13)可知

(24)

其中

(25)

所以第i環(huán)中總能量消耗ETOTAL為

對(duì)式(26)求導(dǎo), 可得第i環(huán)的最優(yōu)簇頭數(shù)mi為

(27)

其中:

(28)

1.3 CH節(jié)點(diǎn)的選舉

由上述理論可得網(wǎng)絡(luò)中每個(gè)環(huán)的最優(yōu)簇頭數(shù)mi(i=1,2,…,n), 再根據(jù)ω選擇每個(gè)環(huán)中的CH節(jié)點(diǎn),ω=mannual/Nannual表示每環(huán)中的最優(yōu)簇頭數(shù)mannual占相應(yīng)環(huán)中節(jié)點(diǎn)數(shù)目Nannual的比值,ω越大表示當(dāng)前環(huán)中CH節(jié)點(diǎn)數(shù)越多.

為減少CH節(jié)點(diǎn)選擇的隨機(jī)性, 提高網(wǎng)絡(luò)的生命周期, 在選擇CH時(shí)本文考慮了當(dāng)前輪次中節(jié)點(diǎn)的剩余能量與節(jié)點(diǎn)初始能量的關(guān)系, 用參數(shù)α=Ecj/E0表示, 其中：Ecj表示節(jié)點(diǎn)j的當(dāng)前剩余能量；E0表示節(jié)點(diǎn)j的初始能量. 網(wǎng)絡(luò)在成簇后, CM節(jié)點(diǎn)需向CH節(jié)點(diǎn)發(fā)送數(shù)據(jù), CH節(jié)點(diǎn)最終將數(shù)據(jù)發(fā)送到BS. 該過(guò)程中距離CH節(jié)點(diǎn)遠(yuǎn)的CM節(jié)點(diǎn)及距離BS遠(yuǎn)的CH節(jié)點(diǎn)的通信能耗均較大, 所以在CH節(jié)點(diǎn)的選擇上, 本文考慮了CM節(jié)點(diǎn)到CH節(jié)點(diǎn)的最短距離和CH到BS距離的關(guān)系, 用參數(shù)β表示,β=min_djc/dcb, 其中： min_djc表示節(jié)點(diǎn)j到CH節(jié)點(diǎn)c的最短距離;dcb表示CH節(jié)點(diǎn)c到BS的距離. 則CH節(jié)點(diǎn)的選舉閾值V(Nu)為

(29)

其中:r為當(dāng)前網(wǎng)絡(luò)的輪數(shù)；S為當(dāng)前輪開(kāi)始前網(wǎng)絡(luò)中非簇頭節(jié)點(diǎn)集.

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

為了評(píng)估CAROCN算法的性能, 利用MATLAB 2014a軟件在網(wǎng)絡(luò)區(qū)域?yàn)?00 m×100 m和200 m×200 m的仿真環(huán)境中進(jìn)行多次實(shí)驗(yàn), 以網(wǎng)絡(luò)第一個(gè)節(jié)點(diǎn)死亡輪數(shù)、 網(wǎng)絡(luò)總能耗、 網(wǎng)絡(luò)平均節(jié)點(diǎn)剩余能量及存活節(jié)點(diǎn)數(shù)量4個(gè)指標(biāo)分析CAROCN算法的性能, 并與LEACH算法[8]和ACONC算法[16]進(jìn)行比較. 實(shí)驗(yàn)仿真參數(shù)設(shè)置為： 網(wǎng)絡(luò)區(qū)域100 m×100 m, 200 m×200 m; 節(jié)點(diǎn)數(shù)量N=100; 節(jié)點(diǎn)初始能量E0=0.05 J; 網(wǎng)絡(luò)環(huán)數(shù)n=7; 數(shù)據(jù)報(bào)文大小為4 000字節(jié); 自由空間模型參數(shù)εfs=1×10-11J/(bit·m2); 發(fā)送和接收電路的能耗參數(shù)Eelec=5×10-11J/bit.

2.1 網(wǎng)絡(luò)生命周期分析

在網(wǎng)絡(luò)區(qū)域?yàn)?00 m×100 m和200 m×200 m的監(jiān)測(cè)區(qū)域下, 第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)如圖4所示. 由圖4可見(jiàn): 在100 m×100 m的網(wǎng)絡(luò)區(qū)域中, 當(dāng)CH節(jié)點(diǎn)輪換次數(shù)為345輪時(shí), LEACH算法出現(xiàn)節(jié)點(diǎn)死亡, ACONCN算法在498輪時(shí)出現(xiàn)節(jié)點(diǎn)死亡, 而CAROCN算法的第一個(gè)節(jié)點(diǎn)死亡輪數(shù)比上述兩種算法分別晚504輪和351輪； 在200 m×200 m的網(wǎng)絡(luò)區(qū)域中, LEACH算法和ACONC算法的第一個(gè)節(jié)點(diǎn)死亡輪數(shù)比在100 m×100 m的網(wǎng)絡(luò)區(qū)域中分別提前了267輪和338輪, 而CAROCN算法的第一個(gè)節(jié)點(diǎn)死亡輪數(shù)僅提前68輪. 表1為不同算法在2 000輪后的存活節(jié)點(diǎn)數(shù). 由表1可見(jiàn)： CH節(jié)點(diǎn)輪換次數(shù)為2 000輪時(shí), 在100 m×100 m網(wǎng)絡(luò)區(qū)域中, CAROCN算法的存活節(jié)點(diǎn)數(shù)比LEACH算法多182%, 比ACONC算法多100%； 在200 m×200 m網(wǎng)絡(luò)區(qū)域中, CAROCN算法的存活節(jié)點(diǎn)數(shù)基本上無(wú)變化. 因此CAROCN算法的網(wǎng)絡(luò)生命周期更長(zhǎng), 穩(wěn)定性和擴(kuò)展性更好.

圖4 不同網(wǎng)絡(luò)區(qū)域中各算法第一個(gè)節(jié)點(diǎn)的死亡輪數(shù)Fig.4 Number of death rounds of the first node of each algorithm in different network areas

表1 不同算法在2 000輪后的存活節(jié)點(diǎn)數(shù)

2.2 網(wǎng)絡(luò)能耗分析

圖5 100 m×100 m(A)和200 m×200 m(B)的網(wǎng)絡(luò)區(qū)域中網(wǎng)絡(luò)的總能耗曲線Fig.5 Total energy consumption curves of network in network areas of 100 m×100 m (A) and 200 m×200 m (B)

網(wǎng)絡(luò)的生命周期也與網(wǎng)絡(luò)的能耗有關(guān), 在100 m×100 m和200 m×200 m的網(wǎng)絡(luò)區(qū)域中, 網(wǎng)絡(luò)的總能耗和節(jié)點(diǎn)的平均節(jié)點(diǎn)剩余能量變化分別如圖5和圖6所示. 由圖5和圖6可見(jiàn), 隨著網(wǎng)絡(luò)中CH節(jié)點(diǎn)選擇輪數(shù)的增加, 網(wǎng)絡(luò)能耗曲線緩慢上升, 平均節(jié)點(diǎn)剩余能量曲線下降, 而LEACH算法和ACONC算法的網(wǎng)絡(luò)能耗曲線比CAROCN算法下降更快. 網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡后, LEACH算法和ACONC算法的網(wǎng)絡(luò)能耗曲線雖然緩慢減少, 但由于節(jié)點(diǎn)任務(wù)分配不均勻, 負(fù)荷大的節(jié)點(diǎn)能量很快耗盡, 網(wǎng)絡(luò)的平均節(jié)點(diǎn)剩余能量仍不斷減少. 在200 m×200 m的網(wǎng)絡(luò)區(qū)域中, LEACH算法和ACONC算法中平均節(jié)點(diǎn)剩余能量一開(kāi)始就急劇下降, 而CAROCN算法中的平均節(jié)點(diǎn)剩余能量雖略有下降, 但基本上與100 m×100 m的網(wǎng)絡(luò)區(qū)域保持一致, 表明CAROCN算法比其他兩種算法具有更好的可擴(kuò)展性.

圖6 100 m×100 m(A)和200 m×200 m(B)網(wǎng)絡(luò)區(qū)域中平均節(jié)點(diǎn)剩余能量曲線Fig.6 Average node residual energy curves in network areas of 100 m×100 m (A) and 200 m×200 m (B)

2.3 存活節(jié)點(diǎn)數(shù)目分析

圖7為網(wǎng)絡(luò)在100 m×100 m的檢測(cè)區(qū)域中網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)目的變化曲線. 由圖7可見(jiàn), 在網(wǎng)絡(luò)的初始工作階段, 網(wǎng)絡(luò)中的存活節(jié)點(diǎn)數(shù)目不變, 但由于LEACH算法、 ACONC算法和CAROCN算法中節(jié)點(diǎn)的工作負(fù)荷不同, 存活節(jié)點(diǎn)數(shù)在CH節(jié)點(diǎn)的不同輪換次數(shù)開(kāi)始減少. LEACH算法和ACONC算法在出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡后, 存活節(jié)點(diǎn)數(shù)量急劇減少, 尤其在200 m×200 m的網(wǎng)絡(luò)區(qū)域中較明顯, 但200 m×200 m的網(wǎng)絡(luò)區(qū)域中CAROCN算法的存活節(jié)點(diǎn)數(shù)目與100 m×100 m的網(wǎng)絡(luò)區(qū)域中的存活節(jié)點(diǎn)數(shù)目基本相同.

圖7 100 m×100 m(A)和200 m×200 m(B)網(wǎng)絡(luò)區(qū)域中存活節(jié)點(diǎn)數(shù)目變化曲線Fig.7 Change curves of number of surviving nodes in network areas of 100 m×100 m (A) and 200 m×200 m (B)

綜上所述, 針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的能效問(wèn)題, 本文提出了一種CAROCN算法, 首先基于每個(gè)環(huán)中能量消耗最小原則計(jì)算出每個(gè)環(huán)的最優(yōu)簇頭數(shù); 然后每個(gè)環(huán)按相應(yīng)的最優(yōu)簇頭數(shù)分成若干不同大小的簇, 同時(shí)又單獨(dú)考慮了最外環(huán)的最優(yōu)簇頭數(shù), 使網(wǎng)絡(luò)的能量消耗更均勻； 最后在簇頭選擇時(shí), 考慮了每個(gè)環(huán)的最優(yōu)簇頭數(shù)與相應(yīng)環(huán)中節(jié)點(diǎn)數(shù)目的比值、 當(dāng)前輪次中節(jié)點(diǎn)的剩余能量與節(jié)點(diǎn)初始能量的關(guān)系以及CM節(jié)點(diǎn)到CH節(jié)點(diǎn)的最短距離, 均衡了網(wǎng)絡(luò)的能量消耗, 延長(zhǎng)了網(wǎng)絡(luò)的生命周期. 仿真實(shí)驗(yàn)結(jié)果表明, CAROCN算法在平衡網(wǎng)絡(luò)能耗和延長(zhǎng)網(wǎng)絡(luò)生命周期上比LEACH算法和ACONC算法性能更好, 且在不同規(guī)模網(wǎng)絡(luò)中具有更好的擴(kuò)展性.