一種新的分環多跳均勻分簇協議分析及NS2仿真

王春梅

(濱州學院信息工程系，山東 濱州　256603)

一種新的分環多跳均勻分簇協議分析及NS2仿真

王春梅

(濱州學院信息工程系，山東 濱州256603)

摘要：針對實際應用中存在的圓形無線傳感器網絡，設計了一種分環多跳的均勻分簇協議CBMBC，理論證明了CBMBC的簇頭異構特性比簇頭同構的情形下節省能量。通過NS2仿真，證明了將網絡劃分成三層環時可以比劃分兩層環時延長網絡的壽命，但是計算復雜度會相應提高。

關鍵詞：無線傳感器網絡；均勻分簇協議；NS2仿真實驗

無線傳感器網絡的一些實際應用中，存在節點均勻分布在圓形區域中，基站位于圓心處的理想網絡模型。其為圓形網絡模型的一個基礎模型，適用于二維的平面區域。為了降低對此類網絡劃分骨干網的難度，很多學者為理想網絡模型設計了很多理想的分簇算法[1-8]。這些分簇算法的主要思想就是將這些圓形的網絡區域劃分成多個同心環，稱這一結構為圓環模型。基于圓環模型提出了很多非均勻分簇的算法，即根據不同的劃分原則來劃分大小規模不等的簇。文獻[6]中第一次提出了非均勻分簇的算法來解決能耗不均問題。文獻[7]中在能量同構的無線傳感器網絡多跳通信模式下提出了一種非均勻分簇算法。文獻[8]在能量同構的無線傳感器網絡單跳通信模式下提出了一種非均勻分簇算法。這兩種算法都沒有考慮普通節點與簇頭節點間能耗的均衡性。針對以上算法的缺陷，設計了一種分環多跳的均勻分簇協議CBMBC。在不同環上設置大小均等的簇規模，使得每一層環中簇頭的能量同構，不同環中簇頭的能量異構，每層環上的普通節點將收集的數據以單跳方式發送給簇中的簇頭，位于外環上的簇頭則通過位于相鄰內環上的簇頭將數據以多跳的方式發送給位于圓環中心的基站，以此來均衡簇頭節點間的能耗。此外，根據普通節點的能耗和每層環上簇頭和基站的相對距離設置簇頭的初始能量，使普通節點的死亡時間和其簇頭節點盡量保持同步，以此來均衡普通節點和簇頭節點間的能耗。因此，網絡中所有節點的能量在網絡死亡的時候都能夠得到充分利用，避免了浪費。

1問題描述

將N個節點均勻分布在一個半徑為R的圓形區域內。基站位于圓形區域中心。在這些節點中，布置了大量的普通節點用來監測收集數據，另外布置一些功能更強的、具有更多能量的節點作為簇頭。普通節點收集完數據后以單跳的形式將其發送給簇頭，簇頭將融合處理后的數據通過內環中的簇頭以多跳的方式發送給基站。由于和基站的距離不同，導致簇頭節點的能耗也不同。內環簇頭由于要轉發大量外環簇頭轉發的數據，能量消耗會很大。因此，假設簇頭節點的初始能量是相同的，則距離基站較近的內環簇頭就會快速死亡而縮短網絡壽命。

解決這種問題的一種可行解決方法是將網絡劃分成很多環，在同一環中，設計規模大小均等的多個簇。根據到基站的不同距離，為不同環中的簇頭設置不同的初始能量，使得內環簇頭的能量較高，而外環簇頭的能量較低，但是在同一環內的簇頭則是能量同構的。根據普通節點的能量以及簇頭所在的位置設置簇頭節點的能量，可以使得整個網絡中所有節點的存活時間盡可能同步，從而可以更好地延長網絡壽命。

2算法系統模型

2.1　網絡模型

將圓形的網絡監測區域劃分成多個寬度相等的環。在每個環中劃分很多大小均等的簇，并且各個環中的簇的規模也是相等的。將簇頭的位置和所需具備的能量預先計算出來，并放置在對應位置上。每個簇由簇頭和其周圍的普通成員節點組成。

圖1　圓環模型

采用如下合理假設來簡化網絡模型：

1) 每個節點都有唯一的節點標識(id)和其所在的環標識(Ci,i=2,3,…,k)。

2) 簇頭節點對簇成員發送的數據進行融合的能力相同，對于其他環中簇頭轉發來的數據由于和本環中的數據相關性不大，所以不再對其進行融合，而是直接轉發給內環簇頭或者基站。

3) 每個普通節點每單位時間向簇頭發送長度為l的包。

4) 網絡壽命定義為從網絡部署到第一個節點死亡的時間。

算法所用到的符號及相關定義如表1所示。

表1　符號及定義

2.2　能量模型

為簡化模型，這里假設傳輸距離小于dcrossover，采用自由空間模型。即

(2)

節點接收端能量消耗為

(3)

假設傳感器節點進行監測的能耗為Esen，簇頭對數據進行融合的能耗為Ecom。

2.3　相關參數的優化設置

2.3.1簇頭間數據轉發能耗

因為簇頭的位置決定著簇內普通節點的能耗，一般分簇時，會將簇頭盡量安置在簇的中心以使得所有成員節點到簇頭的傳輸距離最短。因此，把簇頭放置在簇區域的重心的位置。由于本文采取的是簇間多跳的通信方式，外環簇頭將收集處理后的數據通過內環發送至基站，假設第i層環中簇頭總是將數據轉發給距離該簇頭最近的第i-1層環中簇頭，下面介紹相互通信的兩層環中簇頭的平均距離。

(4)

第i-1層環中簇的簇頭到基站的距離為

(5)

第i層環中簇的簇頭到基站的距離為

(6)

因此，第i層環中簇的簇頭到第i-1層環中簇頭的最大的最近距離近似滿足

(7)

第i層環中簇的簇頭到第i-1層環中簇頭的最小的最近距離近似滿足

(8)

取式(7)和式(8)的平均值作為第i層環中簇頭到第i-1層環中簇頭的最佳數據轉發距離，則

(9)

那么，第i層環中簇的簇頭到第i-1層環中簇頭進行一次數據轉發每單位時間要消耗的傳輸能量為

(10)

第i層環中簇的簇頭向第i-1層環中簇頭轉發數據的同時會收到第i+1層環中簇頭轉發來的數據，因此，當最外層即第k層環中的簇頭發送了一個數據包時，第i層就會發送k-i個數據包。由此，可以得出，第i層簇頭的每單位時間轉發能耗為

(11)

2.3.2普通節點的傳輸距離

第一層環內的節點直接與匯點進行傳輸，故第一層環的普通節點的最遠傳輸距離為：

(12)

第i(i=2,3,…,k)層環內普通節點的最大傳輸距離為

(13)

為延長網絡壽命，使普通節點的能耗盡量均衡，這里普通節點的最大傳輸距離應滿足下面的等式

(14)

又由于

(15)

通過上面的式(4)到式(15)，已知內層環的簇數目mi，便可求得dchi、R1和mi+1等參數的最優值。

2.3.3簇頭節點能耗

由于N個節點隨機分布在半徑為R的圓形區域內，則第i層環內一個簇內的節點數為

(16)

結合式，第層簇頭單位時間的能耗為

(17)

普通節點單位時間的最大能耗為

(18)

設普通節點的初始能量EiniNon已知，則各層簇頭的初始能量可通過如下公式求得

(19)

2.4　理論分析

本文的網絡模型中，網絡在最初的階段被劃分成簇，這些簇在整個網絡生命周期中保持不變，這樣便節省了簇頭選舉和成簇過程消耗的能量。并將監測區域劃分為多個同心圓環，最內層為半徑為R1的圓，其余各層環寬度為r，每層環均分為mi，通過調整mi與R1可使層環內普通節點的最大傳輸距離dfuri近似相等，最終達到普通節點間的能耗盡可能的均衡。部署一些能量較多的節點作為簇頭節點，且不同環上的簇頭的能量是異構的。因為內環簇頭需要對外環簇頭的數據進行轉發，會比外環簇頭更快地消耗能量，采用這種簇頭能量異構的方法，根據普通節點的初始能量和簇頭所在的環的層數設置不同環上的簇頭的初始能量，使簇頭與普通節點的能量相當，盡量使得網絡中所有的節點的存活時間是同步的，充分利用了網絡中的能量資源，避免浪費。

針對本文提出的模型，如果假設其各層環上的簇頭是能量同構的，稱這個假設模型為簇頭能量同構分簇模型CHEH。在提出的網絡模型中，第二層環的簇頭能耗是最大的，其能耗為ECH2。因此，初始能量最大的簇頭也位于第二層環，其初始能量為

(20)

網絡中節點的總能量為

(21)

其中，Enontotal為網絡中普通節點的總能量。為了使得假設模型CHEH與本文提出的網絡模型壽命相同，其各層環上的簇頭的初始能量最小也要EiniCHk，則CHEH中節點的總能量為

(22)

所以，由式(20)到式(22)得出，本文提出的網絡模型和假設模型CHEH相比，可節省的能量為

(23)

3CBMBC協議仿真

測試場景為：200個節點均勻分布在半徑為50的圓形區域.將圓形區域劃分成等寬的圓環，在劃分好的每個環中適當的位置部署一定數量的有較高能量的節點作為簇頭。

3.1　仿真參數設置

具體仿真參數如表2所示。

表2　仿真參數的設置

對于有兩層環的網絡，將m2分別取值為：4，6，8,…,20。當m2取不同值時，計算其他各項參數的最優值，結果如表3所示。

表3　仿真參數最優值

3.2　仿真結果及其分析

下面圖2給出了兩層環的網絡中將第二層環分為4，6，8,…,20個簇的情形下，網絡中的第一個節點死亡時的網絡壽命曲線圖(用輪表示)。

圖2　二層環上簇數不同時網絡壽命

如圖2所示，當逐漸增加第二層環上簇頭的數目時，網絡的生命周期也是逐漸增加的，且4~6、6~8，8~10的曲線斜率大于后面階段。因為隨著第二層環上簇頭數目的增加，相應地，R1會減小，也就是普通節點和簇頭之間的最遠距離會減小，因此減少了普通節點向簇頭發送數據時的傳輸能耗，從而延長了網絡的壽命。

前面理論部分已經分析，與LEACH等經典的動態分簇協議比較，本文提出的靜態分簇算法CBMBC避免了周期性的簇輪轉，避免了不必要的能耗。在相同的場景，設置相同的仿真參數配置，選取m2=16情形下(此時dch2=35.8，dfur2=16.4，R1=16.4，)，運行LEACH協議，LEACH-C協議與CBMBC協議。用alive.awk提取需要的存活節點隨運行時間變化的信息。

圖3所示為3種協議的網絡生存時間對比曲線圖。

圖3　不同協議網絡壽命比較

如圖3所示，LEACH協議運行時，網絡中大多數節點很快就死了，原因是LEACH協議沒有考慮節點的異構問題，能量較少的節點很快就死亡了，而此時能量較高的節點還會剩余很多的能量且不能再被充分利用，因此造成了能量的浪費。集中式算法LEACH-C相比LEACH可以獲取比較均衡的簇頭分布，網絡中節點能耗可以得到一定的均衡，但是LEACH-C同樣沒有考慮節點能量的異構性，因此網絡壽命仍然很短。CBMBC將簇頭節點設置成較高能量，可以充分利用簇頭節點的高能量。從圖2中明顯看出，與LEACH和LEACH-C協議相比，CBMBC可以有效延長網絡的壽命。

對有三層環的網絡的仿真中，設置第二層環上的簇頭數m2=6，可計算此時dch2=25.2，dfur2=17.2，R1=17.2，r=16.4，m3的最優整數值為10。通過計算可得EiniCH2和EiniCH3最優值分別為12.3和11.8，因此將第二層環和第三層環上的簇頭初始能量分別設為12.3J和11.8J。圖4所示為三層環的網絡與兩層環的網絡中網絡壽命的比較。

圖4　兩層環網絡和三層環網絡的壽命比較

如圖4所示，為網絡劃分三層環時網絡的壽命較長。但需要以增加簇頭的能量且提高算法設計的復雜度為代價。

4結束語

為圓形網絡設計的一種分環多跳的均勻分簇協議CBMBC。算法對具體的設置進行了精確的計算和分析，并理論證明了CBMBC的簇頭異構特性比簇頭同構的情形下節省能量。通過NS2仿真，證明了將網絡劃分成三層環時可以比劃分兩層環時延長網絡的壽命，但是計算復雜度會相應提高。

參考文獻：

[1]孫利民,李建中,陳渝.無線傳感器網絡[M].北京:清華大學出版社,2005:3-24.

[2]毛曉峰,楊眠,毛迪林.無線傳感器網絡應用綜述[J].計算機應用與軟件,2008,25(3):179-181.

[3]MuruganathanSD,MaDCF,BhasinPI,etal.Acentralizedenergy-efficientroutingprotocolforwirelesssensornetworks[J].IEEECommunicationsMagazine,2005,43 (3):8-13.

[4]YounisO,FahmyS.HEED:Ahybrid,energy-efficient,distributedclusteringapproachforAdhocsensornetworks[J].IEEETransactionsonMobileComputing,2004,3(4):366-379.

[5]DhiaMahjoub,DavidW.Matula.Employing(1-)dominatingsetpartitionsasbackbonesinwirelesssensotnetworks[C]//ProceedingofALENEX’11.[S.l.]:[s.n.],2010:98-111.

[6]SoroS,HeinzelmanW.Prolongingthelifetimeofwirelesssensornetworksviaunequalclustering[C]//InProceedingofthe19thIEEEInternationalParallelandDistributedProcessingSymposium.Colorado,USA,2005(13):236-243.

[7]XiangM.Energyefficientclusteringalgorithmformaximizinglifetimeofwirelesssensornetworks[J].IntJElectron(AUE),2009(5):1-4.

[8]袁輝勇,王志和,劉永逸.基于不均勻圓環模型的無線傳感器網絡分簇算法[J].信息與控制,2008,7(4):509-512.

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

[11]WangY,ZhaoQ,ZhengD.Energy-drivenadaptiveclusteringdatacollectionprotocolinwirelesssensornetworks[C]//InProceedingsoftheInternationalConferenceonIntelligentMechatronicsandAutomation.Chengdu:[s.n.],2004:599-604.

[12]黃河清,沈杰,姚道遠,等.無線傳感器網絡自適應能量驅動簇頭輪換算法研究[J].電子與信息學報,2009,31(5):1040-1044.

[13]柯志亨，程榮祥，鄧德雋.NS2仿真實驗一多媒體和無線網絡通信[M].北京:電子工業出版社，2009:1-104.

(責任編輯楊繼森)

收稿日期：2015-02-20

基金項目：山東省自然科學基金項目“基于FPGA的分數階切換混沌系統的網絡視頻信息保密技術研究”(ZR2012FM034);山東省自然科學基金項目“分數階混沌系統的特性及同步研究”(2014ZRB019UP)

作者簡介：王春梅(1982—)，女，碩士，講師，主要從事計算機應用技術研究。

doi:10.11809/scbgxb2015.07.027

中圖分類號：TP393

文獻標識碼：A

文章編號：1006-0707(2015)07-0104-05

本文引用格式：王春梅.一種新的分環多跳均勻分簇協議分析及NS2仿真[J].四川兵工學報，2015(7):104-108.

Citation format:WANG Chun-mei.New Ring Based Multi-Hop Equal Clustering Protocol Analysis and NS2 Simulation[J].Journal of Sichuan Ordnance,2015(7):104-108.

New Ring Based Multi-Hop Equal Clustering
Protocol Analysis and NS2 Simulation

WANG Chun-mei

(Information Engineering Department, Binzhou University, Binzhou 256603, China)

Abstract:Aiming at the circular wireless sensor networks (WSN) in practical applications, a new ring based multi-hop equal clustering protocol CBMBC was proposed, the heterogeneous cluster head can save energy than the cluster head isomorphic by theoretical proof. The NS2 simulation results prove that WSN divided into three layers can prolong the lifetime of WSN compared to WSN divided into two layers, but the computational complexity will be increased.

Key words:wireless sensor networks; equal clustering protocol; NS2 simulation experiment

【信息科學與控制工程】