無線傳感器網絡分簇拓撲控制算法*

龍昭華， 陳丹丹， 蔣貴全

(重慶郵電大學 計算機科學與技術學院，重慶 400065)

0 引 言

1 HEED與EEUC拓撲控制算法

HEED[5](hybrid energy-efficient distributed)算法是一種使用固定簇半徑的分簇協議[6]，該協議中給出了無線傳感器網絡中的3個最重要的需求：延長生命周期、可擴展性和負載均衡，并通過將能量消耗均勻分布到整個網絡中來達到延長網絡生命周期的目的。HEED協議中簇首選舉主要依據主、次2個參數。主參數依賴于剩余能量，用于隨機選取初始簇首節點集合，擁有較多剩余能量的節點將有較大的概率暫時成為簇首節點，而最終該節點能否成為簇首取決于剩余能量是否比周期內其他節點的能量多，即迭代過程是否比周圍節點收斂的快。次參數依賴于簇內通信代價，用來確定落在多個簇范圍內的節點最終選擇哪個簇首加入，以及平衡簇首之間的負載[7]。

EEUC[8]算法是一種基于非均勻分簇的無線傳感器網絡路由協議，它采用多跳通信方式防止離基站遠的簇首節點過早死亡，并且以主動方式均衡節點能耗[9]，該協議會預先設置一個是否成為候選簇首的閾值T，普通節點根據此閾值決定自身是否成為候選簇首。未參與競選的節點則進入休眠模式，直到簇首競選過程結束。令Si為任意的一個候選簇首節點，Si根據自身到基站的距離信息來計算其自身競爭區域的大小，區域半徑記為Ri。候選簇首節點之間按照規則1進行競爭簇首。

規則1：在競選簇首節點過程中，如果候選簇首Si宣告其競選成功，那么，在其競爭半徑Ri之內的所有候選簇首節點需退出競選過程。

2 雙簇首能量均衡算法

通過對經典的分簇算法進行研究與分析，盡量避免其不足之處，提出了一種基于雙簇首能量均衡(DCHEB)的無線傳感器網絡分簇拓撲控制算法，本算法引進了雙簇首的思想，每個簇有主簇首節點(MCH)和副簇首節點(VCH)。主簇首負責簇內的數據采集，副簇首節點負責簇間的數據傳輸。這樣一來就使得原來單個簇首節點的簇內數據采集和簇間數據傳輸的2個任務分給現在的主副簇首節點去完成，這大大降低了簇首的能量消耗，可以達到延緩簇的重組的目的。

2.1 基本思想

1)在網絡初始化的時候建立一個圓形的網絡，基站位于其中心[10]；然后以基站為中心按照本文算法提供的方案進行層次的劃分并計算出每層的簇的個數和層間距，傳感器節點均勻地分布在整個網絡中，節點根據自身的坐標、剩余能量以及所在的層次來確定該層的主副簇首節點。這樣可以確保每個簇的節點個數相對平均，主簇首節點位于合適的位置上，從而可以在一定程度上均衡簇內和簇間的能量消耗，進而可以延長整個網絡的生命周期。

2) 進行主副簇首節點選舉時，首先基站廣播簇首選擇消息，各節點會把自身的相關信息(坐標、剩余能量)發送給基站，基站根據節點的信息和已劃分好的層次通過集中式的策略來進行主副簇首節點的選舉[11]。通過這種方式可以使主簇首節點位于較為合適的位置上，從而達到簇內的各節點的能量消耗相對均衡。

2.2 DCHEB算法通信模型簡介

設r為傳感器節點單跳通信的最大距離，本文采用的通信模型分2種情況：當傳輸距離小于r時，發送節點的能耗與傳輸距離的平方呈正比；大于r時，則與傳輸距離的四次方呈正比。這2種情況分別為：自由空間傳輸模型和多路衰減模型。所以，根據傳輸距離的大小，發送節點傳輸kbit的信息所消耗的發送能量如式(1)[12]所示，接收kbit的信息所消耗的能量由式(2)所示

由表2可以看出，該數據為平衡面板數據，截面數為31，跨期為11，屬于短面板。被解釋變量中，人均教育支出均等化指數均值為0.972，人均醫療衛生和人均社會保障與就業均等化指數均值都為0.999，接近于1，說明教育、醫療衛生和社會保障與就業基本公共服務均等化供給程度相對較高。

(1)

ERx(k)=Eelec·k,

(2)

式中Eelec為射頻電路和接收電路每發送或接收單位數據所消耗的能量，J/bit；εfs為自由空間傳輸參數，εamp為多路衰減傳輸參數，它們的單位是J/(bit·m2)。

r為一個門限距離，亦即接收電路和發送電路之間距離的臨界值，當兩者間的距離小于r時，使用自由空間模型；當兩者間的距離大于r時，使用多路徑衰減模型。本文的通信模型將統一采用自由空間模型，假定每個簇首的節點通信范圍都能包含所劃分好的簇，使得網絡中的每個節點都至少有一個簇加入。

2.3 簇的劃分方案

本文提出了一種新的簇的劃分方案，此方案有利于使得主副簇首節點位于合適的位置，而且使得每個簇的節點個數相對平均，這樣會使得簇間和簇內的節點的能量消耗相對均勻和延長邊緣節點的死亡時間，可以有助于延長網絡的生存周期。

1)算出網絡中的最佳簇首個數，計算公式如下

(3)

2)將網絡區域平均分為K個簇域，簇域采用扇形區域，第n層簇的個數設為Pn，如圖1所示，可以得到下面等式

(4)

圖1 層間距Rn與層簇數Pn示意圖

式中S為傳感器網絡區域面積；K為最優簇首數目；Pn為第n層簇的數目；Ri為第i層的間距。

綜上,可以得出Rn的解為

(5)

2.4 主副簇首的選舉

在對簇首節點選舉策略的選擇時，則應考慮以下幾個方面：

1)簇首選舉策略應該盡量采取分布式的方案[13],網絡中的各個節點都可以根據本地地信息進行自主選擇簇首節點，并且簇首節點的選舉算法應該盡量簡單，以節約能量消耗。

2)盡量使被選擇擔當簇首的節點均勻地分布在整個網絡中，并且可以監測整個網絡的運行情況。

3)網絡中被選舉出擔當簇首的節點數目應該盡可能接近于最佳簇首個數。

4)簇首選舉過程中應使能量消耗盡可能的少。

主副簇首選舉的流程如圖2所示。

圖2 主副簇首節點選舉流程圖

通過此階段的選舉，可以確保被選舉成為簇首節點的節點比較均勻地分布在整個網絡中，并且能夠監測整個網絡的運行情況。在此階段之后，被選舉出的主簇首節點會發送廣播消息來組建自己的簇。簇一旦建立完成后，這種簇結構就不會再發生改變。當簇首發生異常，不再適合繼續擔當簇首節點時(包括主、副簇首節點)，不需要再通過基站在全網中進行選舉了，而是在自己所在簇的周圍(也包括簇內)，即在小范圍內按照一定的方式選舉出新任的簇首節點，亦即網絡運行階段中的簇首選舉[14]。

3 仿 真

本文設置的仿真環境：以基站為中心，坐標為原點(0，0)m，把300個傳感器節點均勻分布到半徑為200 m的圓形感知區域的4個象限中。

在上面仿真環境中全部的普通節點負責收集信息，并且按照固定的周期進行數據傳輸，每個數據包均設置為2 000 bit，全部節點的原始能量都設置為0.5 J。其他參數設置為εelec=50 nJ/bit，εfs=10 pJ/bit/m2，εmp=0.001 3 pJ/bit/m4。

3.1 網絡生存時間對比

HEED協議在接近20 s的時候網絡中的全部節點死亡，EEUC協議在接近100 s的時候網絡中的全部節點死亡，而DCHEB在接近160 s的時候網絡中的全部節點才會死亡,如圖3。

圖3 網絡的生存時間對比圖

3.2 網絡能耗的對比

HEED協議在接近20 s的時候整個網絡的能量消耗完，EEUC協議在接近100 s的時候整個網絡的能量消耗完，而DCHEB協議在將近160 s的時候整個網絡的能量才消耗完，如圖4。

圖4 網絡的能量消耗對比圖

本節采用Matlab仿真工具對HEED,EEUC和DCHEB 3種算法，分別從整個網絡的生存時間、整個網絡的能量消耗2個方面進行仿真分析。分析表明:DCHEB協議的性能總體上要優越于HEED,EEUC。

4 結束語

本文引入了雙簇首的思想，由于每個簇內有主副簇首2個簇首節點，則可以使簇首節點的數據采集和轉發數據2項工作平均分配到主副簇首節點上去，從而使主副簇首節點的能量消耗要比一個簇首節點時慢很多，從而可以延緩簇首重構的時間，減少簇首重構的次數，達到節約網絡

能量，延長網絡的生存時間的作用。但是DCHEB算法仍然存在一些不足之處，比如：會導致距離基站較近的節點也會因為要轉發相對較多的數據量而消耗大量的能量，導致整個網絡中能量消耗不均勻，出現比距離基站較遠節點提前死亡的情況，這也是以后研究中需要考慮的主要方面之一。

參考文獻:

[1] Xie X,Zhang H.Topology algorithm research based on energy and power control for topdisc algorithm[C]∥Second International Conference on Computer Modeling and Simulation,2010:37-40.

[2] Shirali M,Meybodi M R,Tarigh H D.Topology control scheduling:Based on the distributed learning automata[C]∥2010 IEEE 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM),2010:1-4.

[3] Hu X,Ren D R,Wang H,et al.Adaptive clustering algorithm based on energy restriction[C]∥2011 IEEE International Conference on Intelligent Computation Technology and Automation(ICICTA),2011:949-951.

[4] 胡 靜，沈連豐.基于博弈論的無線傳感器網絡分簇路由協議[J].東南大學學報:自然科學版,2010,40(3):441-445.

[5] Younis Ossama,Fahmy Sonia.HEED,A hybrid,energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):336-379.

[6] 崔 英.無線傳感器網絡分簇路由協議的研究與實現[D].北京：北京交通大學,2012.

[7] 呂 濤，朱清新，朱玉玉.一種能耗均衡的無線傳感器網絡分簇算法[J].計算機應用,2012,32(11):3107-3111.

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

[9] 柴寶杰,馬寶英,范書平,等.無線傳感器網絡中改進的 EEUC 路由算法[J].微計算機信息,2012(9):149.

[10] 戴世瑾，李樂民.高能量有效的基于分簇的無線傳感器網絡路由協議倡[J].計算機應用研究,2010,27(6):2201-2203.

[11] 楊 軍，張德運，張云翼，等.基于分簇的無線傳感器網絡數據匯聚傳送協議[J].軟件學報,2010,21(5):1127-1137.

[12] 徐小良，裘君娜.異構傳感器網絡中一種能量有效的簇頭選擇算法[J].傳感技術學報,2009，22(3):395-400.

[13] 何永剛，徐汀榮，彭 俊.無線傳感器網絡分簇方法的優化[J].計算機工程與應用，2011,47(1):92-95.

[14] 唐一梅，李志軍，胡 江，等.一種低能耗層次型傳感器網絡拓撲控制算法[J].自動化學報，2010,36(4):543-549.