一種基于時間延遲機制的WSNs非均勻分簇算法

王志勇， 孫順遠， 徐保國

(江南大學 物聯網工程學院，江蘇 無錫 214122)

一種基于時間延遲機制的WSNs非均勻分簇算法

王志勇， 孫順遠， 徐保國

(江南大學 物聯網工程學院，江蘇 無錫 214122)

為減少無線傳感器網絡分簇路由協議中節點競爭簇首時多余的能耗，解決簇首能耗不均的問題，提出一種基于時間延遲機制的非均勻分簇算法。該算法使能量較多的節點被優先選為簇首，并提出了簇首競爭半徑的計算方法，確保其數目穩定且位置均勻分布。成簇過程中，節點根據最小消費函數選擇簇首，簇內成員加入時考慮簇首能量、二者距離以及簇首和匯聚節點角度等因素來均衡簇首能耗。仿真結果表明：算法能有效地均衡節點能耗，延長網絡壽命，分別比CHTD和EEUC算法延長了35.1 %和12.9 %。

無線傳感器網絡； 時間延遲； 非均勻分簇； 能量消耗函數

0 引 言

無線傳感器網絡 (wireless sensor networks,WSNs)是由大量具有一定計算和通信能力的傳感器相互協作而形成的自組織網絡系統。它能夠感知或采集監測對象的相關信息并進行處理，目前已被廣泛應用于軍事、環境、工業、家庭等許多方面。由于節點的能量、計算能力和帶寬資源有限，因此，如何均衡節點能耗和延長網絡壽命是WSNs路由協議首要設計目標和研究熱點。

成簇算法是WSNs中減少能量消耗的一種關鍵技術,它能夠提高網絡的生存時間,可以減少路由算法和洪泛廣播的開銷。近年來，大量關于傳感器網絡分簇的協議被提出，Leach算法[1]提出以輪為工作周期，每輪根據閾值選擇簇首，減少節點與基站的直接通信量從而節約能耗，但是簇首的選擇完全依賴隨機數并不合理?；贚each的思想，文獻[2]提出了DCHS算法，引入能量閾值，延長了網絡生存周期，但是未考慮到全網能量的均衡消耗。文獻[3]提出了HEED算法，根據依賴于節點剩余能量的主參數和依賴于簇內通信代價的次參數選擇簇首，能量消耗較均衡，但是簇內多次消息迭代帶來的通信開銷較為巨大。

針對多跳網絡，文獻[4]引入了能量和距離閾值以均衡全網能量消耗，但簇首之間多跳通信的能耗問題沒有得到很好地解決。文獻[5]提出來一種多跳均勻分簇路由算法，即通過候選簇首的競選半徑和節點剩余能量來確定分布相對均勻的簇首，簇首之間采用以簇首節點剩余能量和鏈路傳輸代價的權值建立多跳路由算法。但是均勻分簇仍然會導致簇負載的不平衡，且距離Sink節點近的簇首會因轉發大量數據而能耗較大。為了解決熱區問題，文獻[6]提出了EEUC算法，可以很好地解決多跳網絡中的熱區問題，但其簇首為隨機產生，負載能力并非最優，根據閾值選擇的候選簇首數量過多，導致節點間競爭簇首通信產生大量多余的能量消耗，并且成簇階段節點依據最近原則加入簇首，沒有考慮形成的簇的能耗問題。

文獻[7,8]提出了一種關于定時器的時間延遲機制，但是對于簇首數目和節點加入簇的方式并沒有深入研究，不穩定的被動簇首個數導致局部負載不均衡，文獻[9]提出了一種新的等待時間與剩余能量之間關系。考慮了簇首的個數問題，但是對于多跳傳輸網絡，同一的競爭半徑會導致簇首能耗不均衡，遠離匯聚點的節點過早死亡。

針對以上問題，結合CHTD和EEUC算法，本文提出了一種新的WSNs多跳路由算法。選擇簇首時，在時間延遲機制的基礎上結合了非均勻分簇的思想，并給出競爭半徑計算公式。在成簇過程中，提出了一種新的消費函數，簇內成員加入時考慮簇首能量，二者距離和通過添加定位節點得出的角度等因素。多跳傳輸過程中給出了是否需要中繼節點的衡量標準。

1 系統模型

1.1 網絡模型

假設傳感器節點隨機均勻分布在一個M×M的方形區域中，用si表示第i個節點，相應的節點集合為S={s1,s2,…,sN}；并具有如下性質：

1)WSNs是一個高密度網絡，由一個匯聚節點,一個定位節點和n個同構普通傳感器節點構成，匯聚節點位于方形區域的外側且位置坐標為(M/2,1.25M)，定位節點坐標為(M/2,0)，且所有節點在部署后就不在移動；

2)每個傳感器節點都有一個事先安排好的唯一ID；

3)傳感器節點發射功率可調，即能夠根據與接收者的距離調節發射功率，且節點間能根據接收信號強度(received signal strength，RSS)計算相互間的距離；

4)網絡中節點的時間是同步的。

1.2 能量模型

采用和文獻[6]相同的無線通信能量消耗模型,如將kbit信息從節點i傳送至節點j，則節點i的發射能耗為

(1)

式中Eelec為發射電路損耗的能量。若傳輸距離小于閾值d0，功率放大損耗采用自由空間模型；當傳輸距離大于等于閾值d0時，采用多路徑衰減模型。Efs,Emp分別為2種模型中功率放大所需要的能量，節點接收kbit數據的能耗為

ERX(k)=Eelec×k.

(2)

數據融合也消耗一定的能量，用Edf表示融合單位比特數據消耗的能量，假設鄰近節點采集的數據具有較高的冗余度，簇首可以將其成員的數據融合成一個長度固定的數據包，然后發送給匯聚節點。

2 UCTD算法

UCTD算法是一種分布式的競爭算法，要先根據本節點的剩余能量生成一個定時器，擁有較短延遲時間的節點將贏得競爭權并有可能成為簇首。算法通過競爭半徑來構造大小不等的簇，靠近匯聚點的簇的規模小于遠離匯聚點的簇,使其保留能量用于簇間中繼轉發。普通節點依據最小消費函數選擇簇首加入成簇。簇內成員節點按分配好的TDMA時隙將數據發送至簇首，簇首將數據融合后通過多跳方式傳送至匯聚節點。

2.1 時間延遲機制

假設Er(i)為節點i第r輪后所剩能量，E0為節點初始能量，K為決定延遲大小的比例系數，則設定節點時延為

Ttimer(i)=K·e1-Er(i)/E0+rand(0,α).

(3)

前半部分起到時間延遲的主要作用，后半部分生成一個隨機數，主要是為了避免同樣能量的節點相互干擾，這里,α取值0.1。從前半部分來看，這是一個關于剩余能量值Er(i)的減函數，即剩余能量越大的節點延遲時間越短，從而使得其成為簇首的機會更大。

2.2 簇首的選舉

采用分簇的多跳傳輸網絡中,簇首消耗能量占每輪能量消耗的主要部分。因為它在簇內通信時需要管理所屬簇成員并與其通信進行數據傳輸,還要融合簇成員收集的數據；在簇間通信時作為中繼節點間接或直接的將處理后的數據發送給匯聚點。簇首能量的消耗平衡與否直接關系著WSNs的生命周期長短。UCTD算法在每個數據收集周期的開始重新構造簇,選擇剩余能量較高的節點作為簇首。下面闡述競爭選取簇首的算法：

WSNs中傳感器節點部署后，所有節點以同樣的信號強度向匯聚點依次發送信息，匯聚點計算出最大最小距離后和定位節點以一定的功率先后向全網廣播一個信號。所有節點根據接收到的信號強度計算出它到匯聚點和定位點的近似距離，分別由公式(4)得到節點自身競爭半徑,公式(5)得到和匯聚節點形成的角度。在收到匯聚節點競選命令后，本輪簇首競選開始，各節點按式(3)計算各自時延時間Ttimer(i)，節點si超時后向全網廣播消息成為第1個簇首。消息包括自身標識ID、剩余能量Er(i)、競選半徑Rc(i)和匯聚節點的距離d(CHi,BS)及其根據公式(5)計算得到cosβ。未超時的普通節點收到接收其他候選簇首發送來的消息，將其計算自己和它的距離dis，若dis小于簇首的競爭半徑，那么節點將定時器清零，放棄競選簇首。其余的節點將繼續競爭，成為簇首的節點依次向全網廣播。時間到達最大延遲時間后，簇首選舉結束。

普通節點收到簇首發來的消息后選擇簇首發送加入請求消息，為了能夠讓靠近匯聚節點的簇規模較小，保留能量用于中繼轉發，算法提出了競爭半徑的一種計算方法

(4)

式中dmax，dmin分別為網絡中為的節點到基站的距離的最大值和最小值，d(si,BS)為節點到匯聚點的距離,c為控制取值范圍的參數，競爭半徑R與節點到匯聚點的距離呈遞減關系，當c取值0.5時，網絡中覆蓋半徑為1.5R。

2.3 簇的生成

簇首選擇好后，節點如何加入簇首直接關系到平衡當前簇首地區的能量消耗。節點加入簇首不能僅僅以和簇首的距離大小來決定，還考慮加入的簇首剩余能量的多少；并且從網絡多跳傳輸的角度來看，節點應該盡量選擇距離匯聚節點遠些的簇首加入，使靠近匯聚節點的簇內成員相對減少，徹底解決熱區問題。在圖1中，對于普通節點3該加入簇首1還是簇首2的問題，從距離上來看，簇首1比簇首2到匯聚節點的距離遠，如果在二者剩余能量相等并且和節點3距離相同的條件下，按照上面的理論，節點3將加入簇首1，這樣會導致邊緣節點負荷過重，不利于平衡全網能量消耗。因此，節點還應該考慮加入與匯聚節點角度小的簇首。

圖1 簇首與定位節點角度Fig 1 Angle between cluster head and location node

綜上，可以添加度量標準cosβ，為了計算出節點與匯聚節點所成角度值，網絡模型中添加了定位節點，節點與匯聚節點在同一直線上，這里稱作BS2，由于節點不移動，所以,定位點只需在通信開始時以固定功率發送一次消息即可，每個節點接收到后各自計算和它的距離后根據余弦公式(5)計算獲得自己與匯聚節點形成角度的大小

(5)

考慮以上因素，由此提出了節點i加入簇首j的消耗函數公式

(6)

其中，Ei為節點i的當前能量，ECHj為簇首j的當前能量，γ為權值，并且

(7)

(8)

式中d(ni,CHj),dn_CH_max分別為節點i到簇首j的距離及其最大值,d(CHj，BS)分別為簇首j到匯聚節點的距離及其最大值，cosβ為簇首和匯聚節點所成角度的余弦。

2.4 多跳路徑的選擇

文獻[6]中EEUC算法在中繼節點的選擇上定義了開銷指標

Erelay=d2(si,sj)+d2(sj,DS).

(9)

取指標最小的2個簇首并從中選取剩余能量高的作為中繼節點。使得網絡能量開銷較小，剩余能量較大簇首成為下一跳節點，均衡了簇首間的能量。在此基礎上，算法提出了簇首衡量是否需要中繼節點的標準。假設節點i選擇j作為中繼節點，由能量消耗模型得

Ehop=ETX(k,d(i,j))+ERX(k)+ETX(k,d(j,DS)) =kεfs(d2(i,j)+d2(j,DS))+3kEelec.

(10)

若采用單跳傳輸則消耗能量為

Edirect=ETX(k,d4(i,BS))=k(Eelec+εmpd2(i,BS)).

(11)

若Ehop

2Eelec+εfs(d(i,j)2+d(j,BS)2)<εmpd(i,BS)4.

(12)

當滿足式(12)時，簇首j被選為中繼節點才能有效節省能耗;否則,節點i將不再選擇中繼點，直接與匯聚節點通信。

3 仿真分析

為了進一步驗證UCTD算法的性能，算法運用Matlab平臺進行模擬實驗，假設采用理想MAC協議，忽略無線鏈路中發生丟包的錯誤。實驗中統計傳感器節點發送，接收數據包與控制包，融合數據消耗的能量。仿真參數如下：網絡面積200 m×200 m，基站位置為(100,250)m，定位節點位置為(100,0)m，節點總數400，節點初始能量0.5 J,數據包大小為4 000 bit，控制包大小為200 bit，εfs為10 pJ/(bit·m-2)，εmp為0.001 3 pJ/(bit·m-4)，Eelec為50 nJ/bit,Edf為5 nJ/bit·signal-1。

UCTD擁有良好的自適應性，每輪都能讓局部能量最高的節點成為簇首，為了能夠自動調整與匯聚節點距離相關的簇首的疏密程度，確保分布均勻，競爭半徑的選擇尤為重要。由前面分析可知，參數c和半徑R決定著簇首的數量。圖2顯示了當c取值0和0.5時,前200輪中平均簇首數目與R之間的關系，即當R不變時，c越大節點半徑越大，簇首數目也會越少，這里，取值R=50 m，c=0.5時簇首數目較為合理，基本穩定在7～11之間。

圖2 UCTD簇首數目Fig 2 Number of UCTD cluster head

算法中能量消耗函數的參數γ的選擇是均衡節點成簇能量的關鍵，通過仿真觀察網絡中權值γ對節點死亡時間的影響，從0.3～1范圍內進行實驗，網絡中第一個節點的死亡時間和γ的關系如下圖3所示，可以看出γ=0.8時效果最好。

圖3 能量消耗權值γ與輪數的關系Fig 3 Relationship between energy consumption weight and rounds

由于簇首消耗能量占每輪能量消耗的主要部分，因此,比較3種協議生成的簇首在一輪中所消耗能量之和，從實驗中隨機選取10輪統計各輪種中所有簇首消耗的能量如圖4，CHTD由于是單跳通信方式傳輸到匯聚節點，長距離的傳輸導致能量消耗過大，而EEUC和UCTD采用多跳傳輸方式，能量消耗都小于CHTD。UCTD采用時間延遲選擇出能量最高的簇首，通過競爭半徑確保了簇首間的分布均衡并通過最小消費函數使節點選擇最優簇首加入，使得每輪簇首的能量更小且更平均。

圖5顯示了在隨機選取的10輪中，各輪簇首消耗能量的方差。從圖中可以看出UCTD方差最小且波動平穩，說明算法均衡了簇首之間的能量消耗，EEUC算法也相對均衡但是方差略大，CHTD的方差最高而且有明顯的波動，簇首能耗不均會導致節點過早死亡。

圖4 簇首消耗能量之和Fig 4 Sum of energy consumption of cluster heads

圖5 簇首消耗能量的方差Fig 5 Variance of energy consumption of cluster heads

比較3種協議的網絡存活時間，如圖6所示，CHTD，EEUC，UCTD協議中第一個節點死亡輪次分別為361，493，546；網絡中50 %節點死亡輪次分別為465，597，680；節點全部死亡輪次分別為532，636，718。UCTD都要優于其他2種算法，節點全部死亡的時間比CHTD和EEUC分別延長35.1 %和12.9 %。從曲線的下落趨勢來看，EEUC和UCTD算法節點的死亡輪數跨度很小，曲線下落趨勢和斜率相近，說明節點能量消耗均衡，但UCTD減少了EEUC協議中候選簇首競爭簇首消耗的部分能量，并提出了更合理的成簇方式，所以,網絡壽命得到了延長。

圖6 各種協議網絡存活時間Fig 6 Network lifetime of various protocols

4 結束語

本文結合CHTD和EEUC算法提出了一種適用于多跳傳輸網絡的基于時間延遲機制的非均勻分簇算法UCTD,節點成簇過程中根據消費函數選擇簇首，多跳傳輸過程中給出是否需要中繼節點的判斷標準。算法良好的自適應性每輪選擇出局部能量最高的節點充當簇首，能夠很好地減少候選簇首競爭簇首時的多余的能耗。仿真表明：算法能有效地平衡能量負載并且充分地延長了網絡生命周期。

[1] Heinzelman W R,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2] Handy M J,Haase M,Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]∥Proc of the 4th IEEE Conf on Mobile and Wireless Communications Networks:Stockholm IEEE Communications Society,2002:368-372.

[3] Younis O,Fahmy S.Heed: A hybrid,energy-efficient,distributed clustering approach for ad-hoc sensor networks[J].IEEE Trans on Mobile Computing,2004,3(4):660-669.

[4] Hsu H L,Liang Q L.An energy-efficient protocol for wireless sensor networks[C] ∥Proceedings of Vehicular Technology Confe-rence,Texas,2005:2321-2325.

[5] 徐久強,畢偉偉,朱 劍.WSNs中多跳均勻分簇路由算法的設計與仿真[J].系統仿真學報,2011,23(5):992-997.

[6] 李成法,陳貴海.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,2007,30(1):27-36.

[7] Cui Xiaoyan.Research and improvement of LEACH protocol in wireless sensor networks [C] ∥IEEE 2007 International Symposium on Microwave,Antenna,Propagation and EMCMAPE,Technologies for Wireless Communications,2007:8.

[8] 曹涌濤,何 晨,蔣鈴鴿.無線傳感器網絡中基于自適應定時器策略的分簇算法[J].電子學報,2007,35(9):1719-1723.

[9] 任東海,尚鳳軍,王 寅.一種基于時間延遲機制的無線傳感器網絡分簇算法[J].傳感技術學報,2009,22 (11):1646-1649.

An uneven clustering algorithm for WSNs based on time delay mechanism

WANG Zhi-yong， SUN Shun-yuan， XU Bao-guo

(School of IOT Engineering,Jiangnan University,Wuxi 214122,China)

To reduce energy consumption while nodes are competitiving cluster head in WSNs clustering routing protocol and solve the problem of unbalanced energy consumption,present a novel uneven clustering algorithm based on time delay mechanism.This algorithm can guarantee the node with high remaining energy to be chosen as the cluster head nodes in priority,besides this,propose computation method of cluster head competitive radius,to ensure a constant number of cluster heads and the cluster heads are well scattered.In cluster process,nodes select cluster heads according to least consumption function,while in cluster member is joining in,consider factors of energy of cluster head ,distance and clusher head and sink node angle.Simulation results show that the algorithm can effectively balance energy consumption of nodes,prolong network lifetime,it prolongs 35.1 % and 12.9 % lifetime compared with CHTD and EEUC algorithm.

wireless sensor networks(WSNs); time delay; uneven clustering; energy consumption function

2013—09—02

TP 393

A

1000—9787(2014)04—0146—04

王志勇(1989-)，男，江蘇徐州人，碩士研究生，主要研究領域為無線傳感器網絡路由算法與節能策略研究。