優化聚類分簇結合自適應中繼策略的雙簇首WSNs路由算法

張 晶,高 翔,張 宏

1(昆明理工大學 信息工程與自動化學院,昆明 650500) 2(云南梟潤科技服務有限公司,昆明 650500) 3(昆明理工大學 云南省人工智能重點實驗室,昆明 650500) 4(昆明理工大學 云南省計算機技術應用重點實驗室,昆明 650500)

0 引 言

感知層作為信息物理系統(Cyber-Physical Systems,CPS)中的重要組成部分,主要是通過傳感器獲取環境中的信息.這些傳感器節點通過無線通信方式可以在特定區域內形成分布式的自組織多跳感測網絡,即無線傳感器網絡(Wireless Sensor Networks,WSNs).WSNs中的傳感器節點具有體積小、成本低和易部署等特點.然而節點儲能部件幾乎不可能也沒必要更換或二次供能,網絡的工作時間取決于節點的能量效率,因此如何優化節點的能耗水平、平衡節點的負載始終是WSNs應用中的重要課題之一.針對WSNs網絡層的節能和流量均衡問題,許多節能路由協議被提出,主要通過調整網絡的拓撲結構、提高網絡的能量利用效率延長網絡的生命周期[1].

針對WSNs中的節點能耗問題,Heinzelman等人[2]提出了被公認為最原始的經典層次分簇路由協議LEACH(Low Energy Adaptive Clustering Hierarchy),算法周期性地按輪執行.每輪的簇建立階段,節點隨機競選簇首來均衡作為簇首的高負載,節點基于最小距離原則來入簇.每輪的數據發送階段,簇首負責收集簇內感測信息并單跳傳輸給基站,但隨機當選的簇首存在能量和位置不合理的問題,不利于將整個網絡的能量負載平均分配到每個傳感器節點中,限制了網絡的生命周期.隨著WSNs應用的升級,LEACH協議的性能無法滿足相應的需求,但是分簇路由方法因其能量利用效率、可靠性和可擴展性高等優點,得到了廣泛的研究.Behera等人[3]提出了一種基于剩余能量的LEACH改進算法R-LEACH(Residual energy-based LEACH),該算法通過結合節點的初始能量、剩余能量以及最佳簇首數修改了LEACH協議中節點成為簇首的閾值,來選擇合理的簇首,避免了節點過早死亡,但其沒有考慮節點位置對傳輸能耗的影響.葉繼華等人[4]提出了一種結合相對信息熵的改進LEACH協議,利用相對熵對數據集進行去冗余以降低傳輸數據量,并使用兼顧能量、距離和能耗比的多跳轉發路由來均衡各節點的能耗速率,但其沒有對成簇階段進行進一步的優化設計,可能會導致簇分布的不均勻.Rajput等人[5]提出了一種半分布式分簇協議SDCP(Semi-Distributed Clustering Protocol),基于模糊C均值(Fuzzy C-Means,FCM)算法成簇將節點進行適當的聚類以減少簇內通信距離,并使用模糊邏輯進行簇首選擇以解決WSNs中由環境噪聲造成的不確定性,提高了網絡的穩定性和可持續性,但是該協議未考慮多跳路由,導致與基站距離較遠的簇首能量消耗很大.Panag等人[6]提出了一種雙簇首靜態分簇算法DHSCA(Dual Head Static Clustering Algorithm),初始化階段節點根據位置被劃分到靜態的簇,避免了動態成簇的開銷,該算法每個簇中選出兩個簇首分別用于數據融合和數據傳輸,有助于平衡節點間的能量消耗,并通過輪換的傳輸簇首進行多跳,將傳輸負載分布到節點之間,但是該算法靜態成簇是使用簡單的網格劃分,沒有考慮到節點的分布特性.趙小強等人[7]提出了一種基于虛擬力的能量高效路由協議,從能耗角度對簇首數進行了理論設定,通過構建虛擬簇首和3種虛擬力模型來優化真實簇首的選擇,并且分析了簇間多跳的使用條件,提高了數據傳輸效率,延長了對目標區域進行有效監測的時間,但是該協議中的簇首既負責收集、融合簇成員的感測數據,又負責與基站通信傳輸數據,導致簇首節點負載大、能耗高.

因此,基于以上分析并綜合考慮如下3個方面:對感測區域進行能耗均衡的成簇劃分,選舉能量、位置和分布密度最合理的簇成員為簇首以及規劃最優通信路徑,本文在已有研究的基礎上提出了一種優化聚類分簇結合自適應中繼策略的雙簇首WSNs路由算法(Dual Head WSNs Routing Algorithm Based on Optimized Cluster Analysis for Clustering Combined with Adaptive Relay Strategy,DRCR).該算法的主要內容如下:

1)成簇階段,以通信能耗為依據設置最優成簇規模,使用算術優化算法(Arithmetic Optimization Algorithm,AOA)計算FCM算法的初始聚類中心,并引入最大最小距離積方法改進AOA的種群初始化,基于此進行集中式成簇可以穩定成簇規模、避免頻繁成簇的廣播能耗.

2)簇首選舉階段,設計了分布式動態雙簇首選舉機制進行簇首輪換.在感測區域已經劃分成簇的基礎上,對內外簇首的工作特性、影響簇首能耗的因素進行分析,分別為內外簇首設計獨立的簇首評價函數,并根據節點能量水平實時調整因子的權重,使簇內的負載更加均衡.事先成簇以及低復雜度簇首評價函數保證節點可以分布式完成評價值計算,無需處理大量廣播消息.

3)數據傳輸階段,為了避免出現多跳中繼比單跳直發能耗高的現象,對外簇首間中繼轉發策略的距離適用條件進行分析.為了避免節點提前過載,將能量消耗速率作為選擇中繼節點的依據.此外,令距離基站比距離內簇首更近的簇成員直接將感測數據發送給基站,以提高基站周圍節點的能量利用效率.

1 系統模型與設定

1.1 網絡模型

本文設定的WSNs分簇路由網絡模型如圖1所示,感測區域內的節點被劃分成簇,簇內有選舉出的內、外兩簇首,感測數據通過節點間的轉發到達基站.同時考慮網絡模型中涉及的約束為以下幾點:

圖1 WSNs分簇路由網絡模型Fig.1 Network model for WSNs clustering routing

1)N個節點在面積為M×M的感測區域內隨機靜態分布,基站位置處于區域中心且資源不設限.

2)所有節點同構,初始能量相同,且具有專屬的編號.

3)每個節點都可獨立地運作以進行分布式處理,運行期間不發生故障.

4)節點可以通過計算得到自身的相對位置[8],并且通信功率可調.

5)周期性執行時間驅動的數據采集,一次完整的數據采集過程記為一輪,網絡中首個節點能量用盡的輪次定義為網絡的生命周期[9].

1.2 能量模型

圖2 無線通信模型Fig.2 Wireless communication model

(1)

節點接收lbit數據和將δ個lbit的數據包融合為一個消耗的能量分別為:

ERX(l)=lEelec

(2)

EAGG(δ,l)=δlEda

(3)

其中,Eelec為設備運行能耗系數,Eda為節點融合1 bit數據所需能耗.

本文仿真實驗中設定能耗模型參數如表1所示.

表1 能耗模型參數Table 1 Parameters of the energy consumption model

2 DRCR

本文提出的DRCR算法將時間離散為輪,網絡工作輪次決定網絡壽命.如圖3所示在算法運行的第1輪,基站將收集所有節點信息進行集中式成簇,在之后的輪次中只有當網絡中的存活節點數改變導致最優成簇規模改變時才會重新成簇;每輪數據傳輸前都會分布式動態更新簇首,簇首選舉前的狀態廣播可以讓節點獲取并存儲所屬簇內節點的狀態信息[11].本節將對DRCR中簇的形成、簇首選舉和數據傳輸的具體實現細節進行闡述.

圖3 DRCR按輪工作流程Fig.3 DRCR round-by-round workflow

2.1 集中成簇

網絡初始化完成后,首先通過分析成簇規模與網絡能耗之間的對應關系,設置最優成簇規模以最小化網絡總能耗.成簇初始階段,節點將自身的實時狀態信息編碼進控制信息廣播數據包發送給基站,基站接收所有節點的數據包后按照約定的格式解碼,然后利用基站強大的處理能力集中運行下述成簇步驟.成簇時,將AOA個體編碼為聚類中心組合,并基于最優成簇規模使用最大最小距離積方法改進AOA的種群初始化,然后AOA以FCM算法的目標函數作為適應度函數計算聚類分析前的初始聚類中心,再將其帶入FCM算法進行集中式成簇,最終將整個網絡劃分為C個簇.基站計算完成后,將成簇結果在整個感測區域內廣播.以上成簇過程不需要每輪都重新計算,只在最優簇數發生改變時才重新成簇,可以避免頻繁成簇的廣播能耗.同時,在簇首選舉前先成簇,可以使得簇首選舉只在簇內分布式進行,避免了簇首隨機分布有時會過于集中、簇成員與簇首距離較大的問題.

2.1.1 最優成簇規模

為給FCM算法指定聚類數目,本小節利用簇數與網絡能耗之間的對應關系,以最小化網絡總能耗為目標來設置最優成簇規模,可以得到更加合理的分簇以改善簇數過多導致的分簇效率及簇首利用率較低、控制信息廣播泛濫問題和簇數過少導致的簇首負載增大問題[7].設定的網絡模型中,N個節點在面積為M×M的感測區域內被均勻地劃分為個C簇,則每個簇內約有N/C個節點,包括2個簇首節點和N/C-2個簇成員節點.假設基站處于感測區域的中心,在分簇和簇首選舉合理的情況下,外簇首到下一跳外簇首(或基站)距離dON、節點到內簇首距離dtoICH、內外簇首之間的距離dIOCH均小于d0.

在本文的網絡和能耗模型中,節點將感測數據發送給內簇首,內簇首接收簇成員數據并融合后將其轉發給外簇首,外簇首接收內簇首傳來的數據、接收TR組中繼數據后與自身感測數據融合并繼續中繼轉發至基站.那么內簇首、外簇首、簇成員節點每輪的能耗分別約為[12,13]:

(4)

(5)

(6)

(7)

由文獻[14]可知對于半徑為R的圓內任意兩點間距離r的概率密度函數為:

(8)

從而數學期望(r的均值)為:

(9)

則dIOCH的期望值可以按照式(10)計算:

(10)

所以網絡運行一輪,單個簇所需能耗ECluster和整個網絡所需能耗ETotal=CECluster分別為:

(11)

(12)

令ETotal對C求偏導為0,可以求得最優成簇規模為:

(13)

2.1.2 模糊C均值算法

FCM算法是一種軟聚類算法[15],通過優化目標函數來獲得所有節點對每個聚類中心的隸屬度矩陣,再根據隸屬度值對節點進行聚類.FCM算法對于嘈雜環境中的非確定信號參數具有穩定性,因此適用于為WSNs聚類[5].在本文網絡模型中,記被隨機部署在感測區域內的N節點集合為X={x1,x2,…,xN},FCM就用以這N個節點的地理位置信息作為數據集進行聚類分析,將其劃分為C個簇(2≤C≤N),記V={v1,v2,…,vC}為C個簇的聚類中心集合,根據節點位置聚類可以減少簇成員的簇內通信距離.

(14)

m為控制成簇模糊重疊程度的指數,m越高最終成簇結果越模糊.U=uij,i=1,…,N,j=1,…,C(uij∈[0,1])為隸屬度矩陣.FCM聚類分析過程中的步驟如下:

1)確定C、m的值,初始化隸屬度矩陣U.

2)計算聚類中心集合V:

(15)

3)更新隸屬度矩陣U:

(16)

4)根據式(14)計算目標函數值Jm(U,V).

5)重復步驟2～步驟4,直到連續兩次迭代之間的目標函數值改進小于給定的最小閾值或達到最大迭代次數.

當迭代停止時,可以得到使Jm(U,V)取到最小值的隸屬度矩陣U和聚類中心集合V.本文中FCM算法的參數設置如表2所示.

表2 FCM算法的參數設置Table 2 Parameter setting of FCM algorithm

2.1.3 算術優化算法

AOA是由Laith Abualigah等人于2021年提出的元啟發式搜索算法[16],該算法模擬加減乘除4種基本算術運算的分布特征進行模型優化,具有收斂快、復雜度低等特性,已被用于解決一些現實世界的優化問題.本文中AOA的參數設置如表3所示.

表3 AOA的參數設置Table 3 Parameter setting of AOA

設r1、r2、r3為值域[0,1]上均勻分布的隨機數,如式(17)所示,該算法定義了加速系數MOA,在每輪迭代過程中,當MOA

(17)

全局探索階段,利用除法和乘法運算符的高分布決策值進行探索,提高解的分散性,實現全局尋優.在此階段,當r2<0.5時執行除法搜索策略,當r2≥0.5時執行乘法搜索策略,搜索代理i在第j維的位置更新公式如式(18)所示:

τj=((UBj-LBj)×μ+LBj)

(18)

(19)

(20)

其中,α是一個敏感參數,定義了迭代過程中的開發精度.

局部開發階段,利用減法和加法運算符的高密度決策值進行開發,在密集區進行深入探索以實現局部尋優.在此階段,當r3<0.5時執行減法搜索策略,當r3≥0.5時執行加法搜索策略,搜索代理i在第j維的位置更新公式如式(21)所示:

(21)

2.1.4 改進AOA優化FCM算法成簇

FCM算法的聚類分析過程簡單、收斂快,但傳統的FCM算法會對隸屬度矩陣U進行隨機初始化,導致計算得到的初始聚類中心也是隨機的,存在容易陷入局部極小值和對初始化敏感的缺點[17].為了提高聚類準確率和魯棒性,本文引入智能尋優算法AOA來優化初始聚類中心,同時使用最大最小距離積方法改進AOA種群初始化.此問題可以描述為:基于最優成簇規模使用改進的AOA在感測區域這整個解空間內尋找最優的C個初始聚類中心組合,使得FCM算法基于優化的初始聚類中心進行成簇可以避免陷入局部最優并得出最優聚類結果,AOA中的每個搜索代理表示一個潛在的最優初始聚類中心集合,FCM算法最終輸出的每個聚類代表一個簇.

下面對利用最大最小距離積方法改進種群初始化的AOA優化FCM算法成簇的關鍵環節進行詳細闡述:

1)編碼:使用基于聚類中心的地理位置信息格式對AOA中的搜索代理進行編碼.由于共有C個初始聚類中心,每個聚類中心有D維的參數,則每個搜索代理的位置可以用一個C×D的矩陣表示:

(22)

本文中每個節點維度D=2,即感測區域為二維平面.矩陣中的值Posij∈[LBj,UBj],表示第i個聚類中心在第j維的值.對AOA種群中的每個個體的位置矩陣解碼可以得到一個合法的聚類中心集合.

2)種群初始化:如果初始化種群時隨機設定每個個體的位置矩陣,會使得其距離最優聚類中心集合有較大的差距,而且會導致AOA的收斂速度較慢,因此將AOA種群按個體數量2∶1的比例分為2個子群,對第1個子群中的個體依然采用在感測區域上隨機初始化以保證種群的多樣性;對第2個子群中的個體按照最大最小距離積方法初始化[18],用一些局部密度較大并且相距較遠的點組成初始集W來初始化個體位置矩陣,使其盡可能代表解空間的分布特性,具體步驟如下:

1.隨機初始化節點集X={x1,x2,…,xN},設初始集W=?.

2.從節點集X中隨機選取點w1作為初始點,同時令W=W+{w1},X=X-{w1}.

3.計算X中所有點與w1的距離Dxw(j,1)=‖xj-w1‖,其中j=1,…,N-1,令j*=argmax(Dxw(j,1)),w2=xj*,則w2為W中與w1距離最大的節點.

4.將該點加入初始集W并從節點集X中刪除.

5.計算X中每個點xj到W中各個點的距離Dxw(j,i),其中i=1,…,C*,j=1,…,N-C*.C*表示初始集W當前的元素個數.

6.對于每個點xj記錄maxv(j)=max(Dxw(j,i)),i=1,…,C*和minv(j)=min(Dxw(j,i)),i=1,…,C*.然后計算Vx(j)=maxv(j)×minv(j),表示xj與W中所有節點的最大距離和最小距離乘積,令j*=argmax(Vx(j)),wC*+1=xj*,則xj*為X中令Vw(j)取得最大值的點.

7.若C*

8.得到具有C個節點的初始集W.

3)適應度函數的確定:本文用改進AOA來優化初始聚類中心,是為了將節點更合理的劃分成簇.而FCM算法中聚類結果越好時目標函數值Jm(U,V)越小,所以適應度函數的值應為Jm(U,V),即fitnessAOA=Jm(U,V).本文中的適應度函數將AOA種群中個體的位置矩陣解碼為C個初始聚類中心集合V,把其帶入公式(16)得出隸屬度矩陣U,最后將U和V帶入公式(14)求出目標函數值作為適應度值來更新最優搜索代理位置.

4)解碼:將表示AOA種群中個體位置的C×D矩陣(矩陣中的每一行對應一個D維的聚類中心)解碼為C個初始聚類中心集合V={v1,v2,…,vC}.

綜上所述,利用最大最小距離積方法改進種群初始化的AOA優化FCM算法的具體步驟如下:

1.設置AOA和FCM算法各參數,結合最大最小距離積法初始化AOA種群.

2.將AOA種群中個體的位置矩陣解碼為C個初始聚類中心集合V.

3.根據式(16)計算該聚類中心集合對應的隸屬度矩陣U.

4.將步驟2中的聚類中心集合和步驟3中的隸屬度矩陣帶入式(14)得到對應的目標函數值Jm(U,V),并將其作為AOA種群中當前個體的適應度值.

5.重復步驟2～步驟4,直到遍歷完AOA種群中所有個體,并記錄最優解.

6.根據式(17)和式(20),更新AOA加速系數MOA和概率系數MOP.

7.根據式(19)和式(21),更新AOA種群的搜索空間.

8.判斷是否達到AOA最大迭代次數,如果沒有達到則返回步驟2,如果達到則執行步驟9.

9.解碼AOA迭代的最優解來代替FCM算法隨機設置的初始聚類中心.

10.執行FCM算法得到使Jm(U,V)取到最小值的隸屬度矩陣U和聚類中心集合V.

2.2 分布式動態雙簇首選舉

考慮到內外簇首的能耗普遍高于成員節點,需要綜合評估節點的能量、距離和節點的中心度等影響因子設計分布式動態雙簇首選擇機制進行簇首輪換.在第2.1節成簇劃分的基礎上,該機制根據當前輪次簇內節點狀態信息,以不同簇首評價函數選舉負責簇內數據收集、融合的內簇首和負責簇間傳輸的外簇首,使簇內通信距離得到降低、負載更加均衡.不同于基站收集所有節點信息進行統一處理后任命簇首,由節點在本地分布式競爭簇首可以避免處理大量控制數據包的能耗.

由第2.1.1節中對節點每輪能耗分析可知,內簇首的工作任務是接收簇成員的感測數據并融合然后轉發給外簇首,外簇首的工作任務是接收內簇首傳來的數據、接受其它外簇首的中繼數據以及將數據融合后中繼轉發至基站,內外簇首的主要能耗由其工作任務決定.顯然,不論內外簇首,均需要剩余能量較高的節點擔任.

(23)

(24)

(25)

(26)

(27)

(28)

在內外簇首評價函數中加入各影響因子的均值,是為了使得各因子的整體權重大致相當.下面對α1、β1、α2、β2的取值進行自適應設計.在網絡運行的前期,節點的能量充足,此時剩余能量因子的權重應該較小.節點的能量隨著通信輪次的增加而減少,若剩余能量小的節點被選為簇首,則會降低網絡的能源利用效率,此時應增加剩余能量因子的權重.經過實驗驗證,可以讓剩余能量因子的權值隨著能量的減小從0.4線性增長至0.6,具體計算方法如式(29)所示:

(29)

其中,Einit為節點的初始能量,則β1、β2的值從0.6下降至0.4.

相較于文獻[19]中使用元啟發式算法選舉簇首或者文獻[5]中使用模糊邏輯選舉簇首的方式,本文中簇首評價函數復雜度低而且節點事先成簇,節點可以用微量的運算開銷在本地直接計算簇內所有節點的內外簇首評價值,評價值大的節點直接當選為對應的內外簇首.而且本文這種處理方式相較于文獻[11]中節點需要與鄰節點頻繁交流決策值依次進行競爭當選簇首的方式,減少了選舉簇首時需要廣播和接收的大量消息.接下來,內外簇首廣播當選成功的控制信息包.外簇首廣播范圍覆蓋3倍簇半徑以使得周圍其余外簇首節點能夠接收到.內簇首廣播范圍覆蓋本簇并為簇成員節點安排簇內通信的TDMA(Time Division Multiple Access)調度,簇內成員節點根據廣播消息中的簇編號匹配入簇,簇內成員節點按照內簇首劃分的TDMA時隙,在自己的時間槽內將感測數據單跳發送給內簇首.

2.3 自適應中繼數據傳輸

本文中的簇內通信采用單跳直發的方式,簇間通信則在文獻[4]和文獻[7]中關于單簇首模型研究的基礎上,針對雙簇首多跳模型進行分析:首先計算了外簇首間中繼轉發策略的距離適用條件,避免出現多跳中繼比單跳直發能耗高的現象;在滿足上訴距離條件的基礎上給出外簇首分布式選擇中繼節點的依據,即能量消耗速率,來避免出現外簇首過載的現象.除此之外,為了減輕基站附近簇首的能耗負擔,使其可以將更多的能量用于中繼數據轉發,簇成員如果距離基站比距離內簇首更近則將感測數據直接發送給基站,否則仍然傳輸給內簇首.

2.3.1 簇間多跳策略的距離適用條件

在較大規模的網絡模型中,與基站距離較遠的外簇首與基站通信時將使用多徑衰落模型通信,產生高額能耗.然而盲目采用多跳通信,而不考慮轉發過程帶來的成本,有可能會導致多跳策略能耗高于單跳的情況.針對這一問題,對外簇首采用多跳中繼和直接與基站通信的能耗進行分析,進而討論簇間多跳策略的適用條件.

對于分簇路由協議而言,中繼多跳路由僅與簇間通信有關,與簇內通信無關,所以在分析多跳中繼策略時僅針對外簇首進行分析,而且僅考慮節點在傳輸數據時的能耗.由對外簇首在第2.1.1節的分析可知,外簇首的能耗分為接收能耗、融合能耗、轉發能耗3個部分.

以某一外簇首向基站傳輸lbit數據為例,設外簇首直接向基站通信的能耗為ENon_Relay、外簇首通過下一跳中繼轉發的總能耗為ERelay(包括當前外簇首向下一跳外簇首的發送能耗和下一跳外簇首的接收、融合能耗),而中繼策略對能耗產生的主要影響可以表示為上述兩者的差值ENon_Relay-ERelay.設dBS和dR分別表示外簇首與基站距離、外簇首到下一跳外簇首距離,則dBS和dR的大小有式(30)中所示的4種情況:

(30)

則ENon_Relay-ERelay的值也對應4種不同的情況:

(31)

顯然,當ENon_Relay-ERelay>0時說明本次傳輸通過其余外簇首多跳轉發可以使能耗被減少,對此不等式求解得出對應情況下dR的取值即為簇間多跳策略的適用條件.需要注意,對于第2種情況,即當dBS≤d0,dR>d0時:

(32)

可見,該式大于0時無解,說明此情況下不適合使用多跳.其余3種情況下解出的dR的取值如式(33)所示:

(33)

在上述距離條件下通過其余外簇首多跳轉發,不僅可以降低簇間通信能耗,還可以將能耗分攤在外簇首之間.

2.3.2 中繼節點選擇

3 仿真測試與分析

采用MATLAB R2017a平臺對本文設計的算法DRCR進行仿真實驗,以評估其有效性.本節將在3個網絡模型場景中,根據成簇結果、簇內節點數量、平均簇首能耗、網絡生命周期、能量效率等不同性能評價指標分析DRCR與文獻[3]中的R-LEACH、文獻[5]中的SDCP和文獻[6]中的DHSCA 3種對比算法的性能差異,并討論導致性能差異的原因.由于R-LEACH作為對經典分簇路由協議LEACH的改進,顯著提升了LEACH的性能,所以考慮與其對比;SDCP使用原始的FCM算法成簇,為驗證本文使用改進AOA優化FCM算法成簇的效果,考慮與其對比;DHSCA針對分簇路由的各個階段進行了完整的優化設計,是一種高效的雙簇首靜態分簇算法,所以考慮與其對比.

3.1 實驗參數設定

3.1.1 網絡模型設置

如表4所示,本文設置了3組不同的網絡模型場景.其中,場景1與場景2的區域面積和基站位置不同,記為對照組1;場景2與場景3的節點密度不同,記為對照組2.

表4 網絡模型參數Table 4 Parameters of the network model

3.1.2 最優成簇規模確定

由式(13)可知,最優成簇規模與dON和TR的取值有關.根據3個場景的參數設定可知,在場景1、2、3中dON取值范圍分別為0～71、0～141與0～141m.假設TR取值范圍為1～5次,基于式(13)可計算出3種場景下的最優成簇規模C的取值范圍分別為3～13、4～19與6～25個.如圖4所示,通過在上述區間內對C的取值進行嘗試,統計3種場景中首個節點能量用盡前平均每輪的總能耗值,可以得出3種場景下的最優成簇規模分別為7、10與12.從圖4中還可以看出,成簇數量較少導致簇首承擔任務過重、成簇數量較多導致簇間通信增多,都會增加每輪的能耗.

圖4 成簇規模對能耗的影響Fig.4 Effect of the number of clusters on energy consumption

3.2 成簇結果和簇首選舉的優化效果

以場景1為例,隨機初始化AOA個體位置的結果如圖5(a)所示,使用最大最小距離積方法初始化個體位置的結果如圖5(b)所示,可以看出使用最大最小距離積方法能夠使得個體初始位置更合理,以提高迭代尋優過程的效率和解的精度.

圖5 AOA個體的不同初始化方式Fig.5 Different initialization methods for AOA individuals

如圖6所示,圖6(a)和圖6(b)分別為使用SDCP中的原始FCM算法單簇首成簇方式和DRCR中的改進AOA優化FCM算法雙簇首成簇方式在場景1中運行至第200輪時的成簇結果,對比兩者發現,圖6(b)中成簇結果在簇分布和簇規模方面都更合理.此外,圖6(b)中的內簇首處于接近簇質心的位置、外簇首處于更靠近基站的位置,這是因為圖6中的成簇輪次較小、網絡剩余能量較多,節點能量對簇首評價值影響較小,所以簇首選舉結果符合兩者工作特性和預期要求.如表5所示,統計上述兩種成簇結果中每個簇的節點數量,結合圖6(a)和圖6(b)可以發現DRCR的成簇結果更均勻,簇內節點數目更穩定,有效地優化了原始FCM聚類的準確性,更有利于實現簇首負擔的均衡.

表5 簇內節點數量對比Table 5 Comparison of the number of nodes in the cluster

圖6 成簇結果對比Fig.6 Comparison of clustering results

圖6(c)和圖6(d)分別是R-LEACH和DHSCA在場景1中運行至200輪時的成簇結果.從圖6(c)中可以看出,由于R-LEACH沒有優化成簇設計,導致簇首位置不合理、成簇結果不均勻.從圖6(d)中可以看出DHSCA成簇結果較合理,但是其成簇基于靜態網格劃分,按照節點數的10%來確定分區個數,此個數并不一定是使網絡通信能耗降低的最優解,并且DHSCA不能根據節點分布特性動態成簇,導致當節點死亡或網絡拓撲發生改變時有可能出現孤立節點現象,而DRCR基于最優成簇規模的動態成簇可以有效避免上述問題.

表6為4種算法的簇首在前500輪中平均每輪的能耗.其中DRCR內外簇首平均每輪的能耗是最低的,并且相較于R-LEACH、SDCP和DHSCA分別降低了23.01%、14.91%和12.79%.綜上所述,DRCR中的成簇方式可以顯著優化成簇效果;為簇首選舉設置的簇首評價函數符合內外簇首的工作特性,保證了選出的簇首能量、位置和中心性更合理,從而有較小的工作能耗;基站集中成簇、節點間分布式簇首選舉的策略可以進一步降低決策成本、均衡簇首負載.

表6 簇首能耗對比Table 6 Comparison of energy consumption of cluster heads

3.3 網絡生命周期

定義FND表示首個節點能量用盡輪次、HND表示半數節點能量用盡輪次、AND表示全部節點能量用盡輪次,并使用這3個指標來衡量網絡的工作時間[20].網絡在首個節點能量耗盡后,會出現對感測區域的覆蓋空洞,使得感測數據有效性降低.因此將FND作為網絡生命周期標準,在此標準下需要讓流量均勻分配,使數據在所有路徑上均勻地傳輸,從而避免因部分節點負載過高導致的網絡壽命縮短[9].

在場景1中,本文算法DRCR和對比算法的能量用盡節點數與網絡運行輪次的關系如圖7(a)所示.可以發現,4種算法的能量用盡節點數都隨著網絡的運行而增加,但是DRCR的首個能量用盡節點出現輪次最晚,R-LEACH、SDCP、DHSCA和DRCR的FND分別為647、793、852和1045,DRCR相較于前三者將網絡生命周期分別延長了61.51%、31.78%與22.65%.此外,在第1045輪DRCR中首個節點能量用盡時,R-LEACH、SDCP和DHSCA已經分別有79、64和61個節點能量耗盡,這已經超過了三者對應的HND,充分表明DRCR能夠對感測區域進行更持久的有效感測.

圖7 網絡生命周期對比Fig.7 Comparison of the network life cycle

如圖7(b)所示,對4種算法的3種工作時間指標FND、HND和AND進行對比,其中R-LEACH、SDCP、DHSCA和DRCR的AND分別為1228、1309、1202和1378,DRCR比前三者分別延長了12.21%、5.27%與14.55%.相較于DRCR對FND的延長比例,DRCR對AND的延長比例并不高,這是因為AND的值要結合FND的值一起觀察,單獨考慮AND的值沒有意義,因為在出現能量耗盡的節點之后會出現網絡覆蓋空洞.值得注意的是,算法的FND值越大并且FND與AND差值越小,說明在首個節點能量耗盡后其余節點的剩余能量也無法支撐過多的輪次,從而證明節點能量得到了更均勻的利用,此情況對應圖7(a)的曲線也應越陡峭[6].計算R-LEACH、SDCP、DHSCA和DRCR的FND與AND差值分別為581、516、350和333,結合FND和圖7(a)中的曲線斜率,可以得知DRCR能夠在延長網絡生命周期的同時實現更均衡的節點能量消耗,這是因為DRCR基于最優成簇規模使用改進AOA優化FCM算法成簇可以均衡簇內能耗,而雙簇首和自適應多跳路由策略可以均衡簇間能耗,從而避免了節點提前過載.DHSCA由于合理的雙簇首輪轉策略也有較好的能量均衡效果,但是其將傳輸簇首的下一跳限定在自身所在列,導致了不必要的傳輸能耗,縮短了網絡壽命.R-LEACH和SDCP由于沒有多跳路由設計,導致傳輸能耗高、能耗均衡效果較差.

3.4 能量效率

圖8(a)為在場景1中,DRCR和對比算法的網絡總剩余能量與網絡運行輪次的關系.由圖8(a)可知,4種算法的網絡總剩余能量都隨著網絡運行輪次的增大而降低,但是DRCR的網絡總剩余能量在相同輪次下相較于對比算法更高,即DRCR每輪消耗能量最少.從圖8(a)中還可以得到一個值得注意的信息:SDCP的網絡總剩余能量在第913輪之前比DHSCA低,但是在第913輪之后比DHSCA高,甚至在第1155輪～第1233輪比DRCR還要高,這是由于SDCP成簇效果較差、沒有優化傳輸路徑導致部分節點提前過載造成的,不利于對目標區域的長時間有效感測.

圖8 能量效率對比Fig.8 Comparison of energy efficiency

如表7所示,統計在網絡運行至第500、700和900輪時,R-LEACH、SDCP、DHSCA和DRCR的網絡總剩余能量,以及DRCR相較于前三者的提升倍數.可以看出,隨著網絡的運行,DRCR的網絡總剩余能量相較于對比算法的提升越來越大.在第900輪時,DRCR的網絡總剩余能量甚至比R-LEACH提升了3.5倍,幾乎比SDCP和DHSCA提升了1倍.

表7 網絡總剩余能量統計Table 7 Total remaining network energy statistics

由此可以得知,DRCR相較于對比算法具有最高的能量利用效率,這是因為:DRCR的優化集中成簇方式縮短了簇內、簇間的通信距離,降低了數據傳輸成本;分布式動態簇首選舉進一步降低了決策成本;簇間中繼基于能量最小化條件,避免了數據回傳以及多跳能耗高于單跳的情況.

如圖8(b)所示,統計隨著網絡總能耗值的增長網絡中剩余的存活節點個數.可以看出,場景1中網絡初始總能量為50J,DRCR在出現首個能量耗盡節點時,網絡總能耗已經達到45.3J,而R-LEACH、SDCP和DHSCA分別在網絡總能耗達到36.3J、39.8J和42.1J時出現首個能量耗盡節點,進一步證明了DRCR有較高的能量效率.此外,當網絡消耗了45.2J的能量后,4種算法的存活節點數量分別為81個、71個、93個與100個,可知當網絡總能量即將耗盡時,DRCR仍可保持更多的存活節點數,保證了感測能力的穩定性,與第4.3節中關于DRCR可以延長網絡生命周期和具有較好的能耗均衡效果的結論相符.

3.5 不同場景下的比較

為驗證本文算法DRCR的性能穩定性,本小節進一步地在場景2和場景3中進行對比實驗,得到圖9.

圖9 不同場景下的性能對比Fig.9 Comparison of performance in different scenarios

結合圖7(a)、圖8(b)與圖9(a)、圖9(b)考察對照組1發現,當感測區域面積增大而節點數量不變時,由于節點間傳輸距離的增加,4種算法在場景2中的能量消耗速率都比在場景1中更快、網絡生命周期也更短.結合圖9(a)、圖9(b)與圖9(c)、圖9(d)考察對照組2發現,當感測區域面積不變而節點數量增多時,由于需要傳輸數據包數量的增加,4種算法在場景3中的能量消耗速率都比在場景2中更快、網絡生命周期也更短.但是在不同場景中DRCR相較于R-LEACH、SDCP和DHSCA仍有更好的能量利用效率以及更長的網絡生命周期.這得益于DRCR的最優成簇規?？梢愿鶕煌木W絡參數以能量最小化為依據進行確定,從而優化了對應場景下的成簇效果,并且DRCR的自適應中繼策略在通信距離改變時,仍然可以根據簇間多跳策略的距離適用條件選擇對應距離下的能耗最低路徑,所以DRCR擁有較好的魯棒性.

3.6 時間復雜度分析

時間復雜度是體現算法運行效率的重要指標,為探索以及驗證DRCR的時間代價,對于節點數為N、最優成簇規模為C的網絡,將算法按照流程進行如下分析:1)種群規模為S、迭代次數為IT1的AOA:種群初始化中最大最小距離方法的時間復雜度為Ο(SNC2),更新適應度的時間復雜度為Ο(SNC),更新種群位置的復雜度為Ο(SC);對于迭代次數為IT2的FCM算法,時間復雜度Ο(IT2NC2)[21].所以集中成簇的復雜度為:Ο(IT1SNC+IT2NC2).2)記單個簇中平均存活節點數為K,分布式動態雙簇首選舉的時間復雜度為Ο(K2).3)自適應中繼數據傳輸的時間復雜度為Ο(C).所以,DRCR在需要成簇的輪次里時間復雜度為Ο(IT1SNC),在大部分不需要成簇的輪次里時間復雜度為Ο(K2+C)=Ο(K2).需要注意,集中成簇是由基站收集數據集中處理再將結果廣播給節點,此部分復雜度由基站承擔.而分布式動態雙簇首選舉、自適應中繼數據傳輸由節點分布式完成,且其復雜度較低,顯著節省了計算時間.

對比算法R-LEACH和DHSCA的時間復雜度均為Ο(N2)[6,7],與之相比,DRCR的時間復雜度在需要成簇的輪次里稍顯劣勢,在其余大部分輪次里存在優勢,并且DRCR的性能得到了明顯提升.對比算法SDCP在成簇階段時間復雜度為Ο(IT2NC2),在簇首選舉階段時間復雜度為模糊邏輯系統運行復雜度[5],與之相比,DRCR時間復雜度在簇首選舉時存在優勢、在需要成簇的輪次復雜度相當.綜上所述,DRCR在性能得到優化的同時,沒有顯著增大算法的時間復雜度.

4 結束語

為了提升節點能量利用效率并延長網絡生命周期,本文提出了一種優化聚類分簇結合自適應中繼策略的雙簇首WSNs路由算法DRCR,針對成簇結構、簇首選取和通信路徑選擇分別進行優化設計.DRCR使用改進種群初始化的AOA優化FCM成簇的方法保證了簇分布的均勻性;基于節點位置、能量和中心性動態選舉出的雙簇首符合其工作特性,在最大化節點能量利用效率的同時顯著平衡了節點間的負載,并且分布式選舉方式降低了決策成本;自適應中繼策略優化了數據傳輸路徑,使得首個節點能量用盡的輪次被推遲,實現了對目標區域更持久有效的監測.由于DRCR中的成簇規模是在不同網絡參數下以節點總能耗最小化為目標設定的最優值,并且DRCR可以根據通信距離以及節點能量消耗速率自適應地選擇能耗最低的傳輸策略,使得DRCR面對不同網絡場景擁有較好的魯棒性.

經實驗驗證,在不同感測區域面積和節點密度的網絡場景中,DRCR相較于對比算法R-LEACH、SDCP和DHSCA更有效地均衡了節點能耗、提升了能量利用效率并延長了網絡生命周期.由于未考慮到傳輸鏈路的端到端丟包率和延時問題,因此今后工作將圍繞滿足WSNs中的路由服務質量展開.