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

(1. 長春工業(yè)大學 計算機科學與工程學院, 長春 130012;2. 吉林建筑科技學院 計算機科學與工程學院， 長春 130114；3. 長春師范大學 計算機科學與技術學院, 長春 130032)

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

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

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

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

1 CAROCN算法

1.1 網(wǎng)絡模型

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

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

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

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

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

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

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

(1)

ER(u)=u×Eelec,

(2)

(3)

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

(4)

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

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

(5)

(6)

(7)

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

(8)

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

(9)

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

(10)

(11)

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

(12)

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

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

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

其中

(14)

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

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

(16)

其中：

(17)

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

(18)

(19)

(21)

(22)

(23)

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

(24)

其中

(25)

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

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

(27)

其中:

(28)

1.3 CH節(jié)點的選舉

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

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

(29)

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

2 仿真實驗分析

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

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

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

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

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

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

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

圖6 100 m×100 m(A)和200 m×200 m(B)網(wǎng)絡區(qū)域中平均節(jié)點剩余能量曲線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é)點數(shù)目分析

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

圖7 100 m×100 m(A)和200 m×200 m(B)網(wǎng)絡區(qū)域中存活節(jié)點數(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)

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