基于最優(yōu)簇頭數的環(huán)形無線傳感器網絡分簇算法

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

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

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

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

圖1 網絡模型Fig.1 Network model

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

1 CAROCN算法

1.1 網絡模型

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

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

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

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

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

1.2 最優(yōu)簇頭數

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

(1)

ER(u)=u×Eelec,

(2)

(3)

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

(4)

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

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

(5)

(6)

(7)

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

(8)

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

(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)簇頭數為

(16)

其中：

(17)

1.2.2 第i環(huán)的最優(yōu)簇頭數 除最外環(huán)簇的CH節(jié)點外, 其他環(huán)中的CH節(jié)點不僅要接收該簇中CM節(jié)點發(fā)送的數據, 同時也要接收上一環(huán)中某CH節(jié)點轉發(fā)的數據, 將這些數據進行融合, 然后轉發(fā)到下一跳接收節(jié)點. 設第i(i=1,2,…,n-1)環(huán)中每個環(huán)扇的節(jié)點數為Ni, 第i環(huán)的最優(yōu)簇頭數為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)簇頭數mi為

(27)

其中:

(28)

1.3 CH節(jié)點的選舉

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

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

(29)

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

2 仿真實驗分析

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

2.1 網絡生命周期分析

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

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

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

2.2 網絡能耗分析

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

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

圖6 100 m×100 m(A)和200 m×200 m(B)網絡區(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é)點數目分析

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

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

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