基于奇偶輪成簇和雙簇首的非均勻分簇協議

李安超，陳桂芬

(長春理工大學 電子信息工程學院,長春 130022)(*通信作者電子郵箱chenguif@163.com)

0 引言

無線傳感器網絡(Wireless Sensor Network, WSN)是由部署在監測區域內的大量微型、低功耗的傳感器節點根據路由協議自組織形成的網絡[1]。由于傳感器節點體積微小，處理能力與攜帶能量有限，因此研究合理高效的路由協議顯得極為重要。合理的路由協議能有效延長網絡生命周期，提高網絡能量效率。路由協議可以根據拓撲結構分為平面型與分簇型路由協議[2]。相比平面型路由協議，分簇型路由協議[3]可拓展性強，網絡性能優異，更適用于大規模網絡。

低能量自適應分群分層(Low Energy Adaptive Clustering Hierarchy， LEACH)協議是一種經典分簇型路由協議，該協議在每輪數據采集中，隨機選取部分節點擔任簇首，通過單跳形式與基站通信。針對其未考慮節點剩余能量的問題，Heinzelman等[4]提出了基于節點能量的改進(Low Energy Adaptive Clustering Hierarchy Enhanced， LEACH-E)協議。Qing等[5]將LEACH協議應用于能量異構無線傳感器網絡并提出了改進的分布式能量有效成簇協議(Distribute Energy-Efficient Clustering protocol， DEEC)，該協議根據節點的剩余能量動態調整節點當選簇首的概率，性能較LEACH協議更加優異；但DEEC未考慮節點的位置因素且魯棒性不高的缺點仍然存在。李安超等[6]改進簇首當選公式，綜合考慮節點能量與位置，設立雙閾值以提高能量利用率；但仍為單跳通信網絡，簇首節點負擔過重。周冬鑫等[7]將分層多跳的思想引入分簇路由協議中，提出了基于分層多跳的無線傳感器網絡分簇路由協議(Layer Based Multi-hop Clustering routing protocol for wireless sensor networks, LBMC)，LBMC根據通信代價分層的基礎計算每層最佳簇首數量，簇首間采用多跳通信，均衡了網絡負載；但仍采用均勻分簇思想，簇首分布不合理。

分簇路由協議中靠近基站的簇首同時執行接收、融合和傳輸數據任務，網絡負擔重，很容易因能量耗盡而失效。這一現象被稱為“能量熱區”問題。為解決這一問題，Soro等[8]經過研究，提出了非均勻分簇的思想。李成法等[9]提出了一種能量有效非均勻分簇(Energy-Efficient Uneven Clustering， EEUC)協議，對解決“能量熱區”問題十分有效。EEUC協議通過設立競爭半徑，使靠近基站的簇規模變小，均衡簇首能量消耗；但簇首隨機選取，很容易使能量較低且遠離基站的節點擔任簇首；同時在簇間多跳階段，僅以距離作為中繼節點的評價標準，很容易產生局部最優整體較差現象。蔣暢江等[10]提出了一種分布式能量均衡非均勻成簇協議(Distributed Energy-Balanced Unequal Clustering routing protocol， DEBUC)。DEBUC基于時間的簇首競爭機制，廣播時間取決于簇首的剩余能量和鄰居節點的剩余能量，同時，控制簇首競爭半徑，使靠近基站的簇群規模較小，以解決“能量熱區問題”，但DEBUC沒有限制簇群規模上限，會導致監測區域邊緣的簇群規模過大，消耗大量能量。文獻[11]提出了一種基于非均勻分簇的無線傳感器網絡分層路由協議(Hierarchical Routing Protocol for wireless sensor networks based on Non-uniform Clustering， HRPNC)，HRPNC通過分層機制改進簇首競爭公式，將簇群規模限定在一定范圍內，避免了簇群規模過大的現象；但HRPNC未能考慮簇首剩余能量和轉發次數，存在能量利用率不高的問題。

針對以上協議的缺點，本文提出了一種基于奇偶輪成簇和雙簇首的非均勻分簇協議(Uneven Clustering protocol based on Odd-even round clustering and Double cluster head, UCOD)：UCOD設立雙簇首和奇偶輪不同的入簇機制，提高網絡數據傳輸效率；對網絡節點進行分級，簇首根據能量、位置、轉發次數和周圍節點數選擇多跳中繼節點。實驗結果表明，與DEBUC和HRPNC相比，UCOD能夠有效地優化網絡負載，提高系統魯棒性，延長網絡生命周期。

1 相關工作

1.1 異構無線傳感器網絡

傳統分簇路由協議的應用環境為同構無線傳感器網絡，要求部署的節點所有屬性完全一致，協議要求十分嚴格。在近幾年的無線傳感器網絡研究中，異構無線傳感器網絡逐漸走進人們的視野。異構無線傳感器網絡是指由不同類型的傳感器節點所組成的網絡，可以根據節點的感測、計算、能量和通信能力劃分為4種類型：計算能量異構型、節點能量異構型、鏈路異構型和網絡協議異構型[12]。在實際中，由于運輸、電池批次、存儲等問題，節點配置的初始能量不可能完全相同，因此節點能量異構型傳感器網絡更易實現且更符合實際。

多級能量異構網絡能量模型如下。

在多級能量異構傳感器網絡中，為每個節點分配一個不同的能量增益倍數ai，假設初始最低能量為Eo，則所有節點的能量被限制在最小值Eo、最大值Eo(1+amax)的范圍內，其中amax為所有能量增益倍數ai的最大值。

本文采用文獻[13]中的無線通信能量消耗模型。節點發送數據所消耗的能量可分為發送數據能耗ETX(l,d)和接收數據能耗ERX(l)兩部分。能耗公式如式(1)：

(1)

其中：d為兩節點間的通信距離；當d

ERX(l)=lEelec

(2)

Ec=(M+1)lEDA

(3)

(4)

其中：EDA為單位數據融合的能耗；M為簇內成員的節點數。在數據融合階段，目前已經有很多性能優異的融合協議[14]，本文中假設采集的數據具有一定的冗余性，簇首節點可以將簇內采集的數據融合成一定長度的數據包并進行轉發。

1.2 網絡模型

為了避免其他因素產生影響，本文對無線傳感器網絡中的節點設定以下性質：

1)節點具有唯一的編號(ID)，在監測區域內隨機分布，且部署后不再移動；

2)基站位置固定且處理能力與能量無限；

3)節點具有位置感知能力，可根據接收信號的強度RSSI定位各自位置[15]；

4)每個節點具有與基站直接通信的能力；

5)節點通信功率可以根據通信距離進行調節。

2 基于奇偶輪成簇的非均勻分簇機制

針對無線傳感器網絡存在“能量熱區”和系統魯棒性較差的問題，提出了一種基于奇偶輪成簇和雙簇首的非均勻分簇路由協議(UCOD)。該協議實現步驟包括兩個部分，簇首選取算法及簇間多跳路由算法。圖1為非均勻分簇網絡模型示意圖。

圖1 非均勻分簇網絡模型示意圖

2.1 簇首選取算法

在簇首選取階段，根據節點節點的剩余能量、位置分布及競爭半徑確定主副簇首節點。算法1給出了節點參與簇首競爭選取階段的算法偽代碼。

算法1 簇首競爭選取算法。

1)μ← RAND(0,1)

2) Ifμ

3)beViceHead← true

4) End if

5) IfbeViceHead=true then

6) Broadcast VICE_HEAD_MSG(ID,Rc,Er)

7) Else

8) Exit

9) End if

10) On receiving a VICE_HEAD_MSG formsi

11) Ifd(si,sj)

12) Addsjtosi .CH

13) End if

14) WhilebeViceHead=true do

15) Ifsj∈si .CH,mj=max(mi .CH) then

16) Broadcast MAIN_HEAD_MSG(ID) and then exit

17) End if

18) On receiving a MAIN_HEAD_MSG formsj

19) Ifsk∈si .CHthen

20) Broadcast QUIT_ELECTION_MSG(ID) and then exit

21) End if

22) End while

下面對算法1進行解釋。算法第1)～9)行是副簇首(ViceHead)當選過程。由于副簇首節點主要負責傳送數據至基站，所以副簇首距離基站的遠近顯得格外重要，副簇首當選概率公式如式(5)：

(5)

在選取副簇首時，每個節點產生0到1的隨機數，若該隨機數小于設定的閾值，則該節點成為副簇首節點。閾值如式(6)：

(6)

pi可以從式(5)確定。從式(5)～(6)中可以看出，節點距離基站越近且剩余能量越大，節點當選副簇首的概率越高。當節點當選副簇首后，廣播副簇首信息VICE_HEAD_MSG，簇首信息包括當選節點的ID、競爭半徑Rc和當前剩余能量Er。

算法第10)～13)行是副簇首競選過程。從能量模型的角度分析，當兩個副簇首節點距離很近時，會造成簇內節點分布不均，浪費網絡能量，因此，本文在副簇首的選取上引入了非均勻的競爭半徑。如圖2所示。S1、S3可以當選副簇首，而S2不能當選，因為S2位于S1的競爭半徑范圍內。

當第一個副簇首節點確定，在其淘汰半徑內的所有節點均失去競爭簇首的機會。競爭半徑公式如式(7)：

Rc=[μ(di-dmin)/(dmax-dmin)+

(7)

其中：Rmax是競爭半徑的最大取值；di表示當前副簇首節點距離基站距離，dmin和dmax分別代表節點距離基站最近與最遠距離；μ代表一個可變參數，可以根據檢測區域的面積及節點能量進行適當調節。在非均勻分簇協議中，靠近基站的簇首不僅需要接收簇內節點數據，還需接收來自簇首間的數據，因此靠近基站的簇首的競爭半徑應較小；同時大的競爭半徑意味著簇內節點數目較多，需要較大的能量以支撐。

圖2 節點競爭示意圖

副簇首選定后，普通節點根據最近的副簇首進行入簇。在簇內，進行主簇首的選取過程。見算法第14)～17)行。由于主簇首主要收集簇內節點采集的數據，因此，選擇距離所有簇內節點距離最近且能量較高的節點當選主簇首最為合理，同時，主簇首還需將壓縮數據傳送至副簇首，主副簇首節點間的距離也是影響主簇首當選的因素。綜合上述分析，設定的主簇首當選公式如式(8)：

(8)

(9)

圖3 UCOD系統模型

從第二輪循環開始，為減少節點頻繁參與簇首選取過程，設定奇數輪中全局節點選取簇首，偶數輪中簇首從奇數輪簇內選取，這樣，將減少一半節點因入簇選擇所消耗的能量。在偶數輪中，副簇首選取的機制可以簡化為式(10)：

(10)

其中：dmax′表示該簇內節點距離基站的最遠距離；davg′表示該簇內所有節點距離基站的平均值。

主簇首的選擇可以利用式(8)選出。簇首選取算法流程如圖4所示。

圖4 簇首選取算法流程

2.2 簇間多跳路由協議

當主副簇首選定后，將執行數據采集和傳輸過程；同時副簇首間采用多跳通信方式最終將數據匯聚到基站。傳統的多跳路由協議(如EEUC協議)主要考慮兩個指標：節點距離中繼節點的位置d2(si,sj)和中繼節點到基站的位置d2(sj,BS)，并最終使評價指標Erelay=d2(si,sj)+d2(sj,BS)獲得最小的待選節點作為中繼節點。這樣的機制，很容易造成局部評價指標最好而整體評價指標較差的局部最優現象，因此，本文將網絡劃分為多級同心圓網絡，對每一級圓環內節點采用不同的多跳方式，分層考慮中繼節點的選擇。網絡劃分如圖5所示。

圖5 網絡劃分示意圖

假定Δd如式(11)：

(11)

其中c為待定系數，可以根據檢測區域的面積進行調整。假設檢測區域邊長為D，基站位于檢測區域外，共劃分為K級同心圓網絡。為了使K級同心圓網絡能完全覆蓋檢測區域，需滿足KΔd≥D，對上述公式進行求解可以得出c系數的公式：

c≥D/(Kd0)

(12)

同時，當Δd≥d0的情況下，會導致內環節點負擔過重，不利于網絡能量均衡，因此，最終確定的c系數的公式如式(13)：

1≥c≥D/(Kd0)

(13)

網絡劃分確定后，在Ⅰ級內節點(d(sj,BS)<Δd)直接與基站進行通信；在Ⅱ級以上的節點(d(sj,BS)>Δd)選擇多跳通信方式與基站通信。

網絡中節點最大轉發跳數公式如式(14)：

T=floor(d(sj,BS)/Δd)

(14)

其中floor()函數代表向上取整函數。

在多跳執行階段，中繼節點的選擇按照逐級遞減的方式進行，如Ⅲ級內節點與基站通信的路線為Ⅲ→Ⅱ→Ⅰ。中繼節點的選擇可以根據下一跳節點的位置、剩余能量、轉發次數和周圍節點數決定。評價指標如式(15)所示：

(15)

2.3 算法復雜度分析

假設無線傳感器網絡中共有N個節點，每輪選取K個主簇首和K個副簇首，下面分析整體算法的復雜度。

首先由K個副簇首節點當選，廣播K條VICE_HEAD_MSG消息；然后簇內選取主簇首，同樣廣播K條MAIN_HEAD_MSG消息；接著競爭失敗的簇首廣播N-2K條QUIT_ELECTION_MSG消息和N-2K條JOIN_CLUSTER_MSG入簇消息。在偶數輪，由于節點不需要入簇選擇，所以算法整體消息開銷為：

K+K+0.5×(N-2K)+0.5×(N-2K)=N

(16)

算法整體復雜度為O(N)，說明算法開銷較小。

3 仿真分析

在仿真分析環節，硬件環境為Intel Core i5- 3337U處理器，4 GB內存；軟件環境為Windows 10 x64；仿真軟件為Matlab R2013b。為了驗證UCOD的性能，通過與DEBUC和HRPNC進行比較，從簇首生成數量、能量效率和系統穩定性方面進行性能分析。為了保持實驗數據的一致性，將三種協議置于多級能量異構無線傳感器網絡下進行仿真。仿真參數如表1所示。

3.1 簇首特性

UCOD改進了DEBUC所提出的競爭半徑公式。從式(7)可以看出，UCOD的競爭半徑主要由參量μ和最大競爭半徑Rmax所決定。圖6為不同μ參數下生成的簇首數對比。

圖6為不同μ參數下UCOD簇首生成數對比。從圖6中可以看出，隨著最大競爭半徑的增大，簇首數不斷減少。這是因為越大的競爭半徑意味著網絡需要越少的簇首來覆蓋整個監測區域。UCOD中μ參量對簇首數也產生著很大的影響，當μ=0.25、0.75時，整體簇首數少于當μ=0.45時生成的簇首數。這是因為UCOD中競爭半徑由兩因素構成：位置與能量，當μ取值較小時，競爭半徑著重考慮節點剩余能量，剩余能量較大的簇首擁有更大的競爭半徑和更多的簇內節點，充足的能量可以保證簇內正常的數據傳輸；當μ取值較大時，競爭半徑著重考慮節點位置，距離基站較近的簇首擁有較小的競爭半徑，可以預留能量轉發其他簇首傳輸的數據。μ值偏大或偏小都會導致競爭半徑考慮單一因素，不能綜合位置與能量進行分析。

表1 仿真參數

圖6 簇首生成數與μ、Rmax關系

3.2 能量效率

在能量效率比較環節，將UCOD與DEBUC、HRPNC相比較，以網絡生命周期、網絡能量消耗、網絡數據傳輸為指標進行分析。

圖7為三種協議能量效率對比。無線傳感網絡中，當節點數量小于10%時，網絡不能繼續工作，因此，無線傳感器網絡的有效生命周期應以剩余10%節點為基準。從圖7(a)網絡生命周期對比中可以看出，UCOD能有效地延長網絡生命周期。DEBUC網絡生命周期為1 241輪，UCOD網絡生命周期為1 594輪，比DEBUC提高了28.4%。這是由于UCOD采用了奇偶輪不同的成簇機制，使全局節點減少入簇選擇所消耗的能量；多跳機制中，簇首根據剩余能量、位置、轉發次數和周圍節點數確定中繼節點，數據傳輸更加高效。

另一方面，HRPNC的網絡生命周期為1 401輪，UCOD比HRPNC提高了13.7%。這是因為UCOD引入了雙簇首并改進簇首競爭半徑公式，提高了能量效率，延長了網絡生命周期。

圖7(b)為網絡傳輸數據對比。UCOD傳輸12×104b數據，HRPNC傳輸10×104b數據，DEBUC傳輸6×104b數據。UCOD傳輸數據量分別比HRPNC和DEBUC提高了20%和100%，一方面，UCOD擁有更長的生命周期，意味著可以傳輸更多的數據；另一方面，UCOD引入主副簇首機制，使簇內數據傳輸更加高效。

圖7(c)為網絡能量消耗對比。可以看出，在相同的初始網絡能量下，三種協議消耗的網絡總能量曲線最終重合，與初始設定相符；但從三種協議能量消耗曲線斜率來看，DEBUC>HRPNC>UCOD，能量消耗曲線斜率代表網絡能耗的高低，表明UCOD相比另兩種協議能耗更低。UCOD改進了主副簇首選取公式：主簇首選取上著重考慮簇間各節點間距離與剩余能量；副簇首選取上著重考慮剩余能量與到基站的距離，相比DEBUC和HRPNC優化了網絡負載，提高了網絡能量效率。

圖7(d)為節點剩余能量方差對比。由于采用能量異構無線傳感器網絡，在初始階段三種協議節點剩余能量方差相同且不為零。隨著實驗的進行，可以看出，UCOD節點剩余能量方差明顯小于DEBUC和HRPNC，這說明UCOD通過構建合理的多跳機制，平均節點剩余能量，均衡網絡整體負載。

圖7 三種協議能量效率對比

3.3 系統穩定性

在這一環節，分別以丟包率和不同參數δ下網絡生命周期為指標研究UCOD的系統穩定性。

在丟包率對比環節，人為毀壞部分簇首節點來模擬網絡拓撲結構突變情況。設定單簇首網絡中簇首節點損壞時，簇內節點直接將數據傳送至基站，UCOD中副簇首節點擔任主副簇首任務繼續執行工作。

圖8為不同簇首損壞率下的丟包率對比。

圖8 三種協議的丟包率對比

從圖8中可以看出隨著簇首損壞率的上升，三種協議的丟包率也隨之上升，在簇首損壞率50%的條件下，UCOD丟包率為18.0%，DEBUC為57.1%，HRPNC為45.5%，UCOD丟包率比DEBUC和HRPNC分別減少了39.1和27.5個百分點。這是由于DEBUC和HRPNC簇首損壞后，節點只能被迫選擇直接與基站通信，部分節點因大量耗能而死亡，從而使丟包率上升；而UCOD采用雙簇首機制，在部分簇首節點損壞后網絡仍能以單簇首網絡的形式正常工作。

圖9為不同參數δ下UCOD的生命周期變化。δ參數直接決定主簇首開始休眠時的能量門限，對網絡的整體運作影響很大。由于DEBUC與HRPNC并無參數δ，本次仿真僅作單獨實驗。

圖9 不同參數δ下生命周期對比

從圖9中可以看出：當δ取0.3時，UCOD網絡生命周期最長；在δ小于0.3時，會導致主簇首節點剩余能量不足以支撐一輪數據采集所消耗的能量而導致死亡；而δ過大會導致主簇首大部分時間處于休眠狀態，影響網絡能量效率。隨著δ的不斷增大，生命周期趨于平穩，這是由于此時網絡大部分副簇首執行主副簇首功能，類似單簇首網絡。

4 結語

針對無線傳感器網絡設計中“能量熱區”和系統魯棒性較差的問題，本文設計了一種基于奇偶輪入簇和雙簇首的非均勻分簇路由協議(UCOD)。該協議引入雙簇首和奇偶輪不同的入簇機制，改進簇首競爭半徑公式，并基于節點分級實現多跳傳輸。實驗結果表明，UCOD比起DEBUC和HRPNC能有效地提高網絡生命周期、數據傳輸、能量效率和系統穩定性。由于本文對節點空間定位技術只是簡單引用，并未考慮空間定位算法對路由協議的影響，下一步工作中將對空間定位技術進行研究，使UCOD在均衡網絡負載上更加完善。