一種新的分環(huán)多跳均勻分簇協(xié)議分析及NS2仿真

王春梅

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

一種新的分環(huán)多跳均勻分簇協(xié)議分析及NS2仿真

王春梅

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

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；均勻分簇協(xié)議；NS2仿真實驗

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

1問題描述

將N個節(jié)點均勻分布在一個半徑為R的圓形區(qū)域內(nèi)?；疚挥趫A形區(qū)域中心。在這些節(jié)點中，布置了大量的普通節(jié)點用來監(jiān)測收集數(shù)據(jù)，另外布置一些功能更強的、具有更多能量的節(jié)點作為簇頭。普通節(jié)點收集完數(shù)據(jù)后以單跳的形式將其發(fā)送給簇頭，簇頭將融合處理后的數(shù)據(jù)通過內(nèi)環(huán)中的簇頭以多跳的方式發(fā)送給基站。由于和基站的距離不同，導致簇頭節(jié)點的能耗也不同。內(nèi)環(huán)簇頭由于要轉(zhuǎn)發(fā)大量外環(huán)簇頭轉(zhuǎn)發(fā)的數(shù)據(jù)，能量消耗會很大。因此，假設(shè)簇頭節(jié)點的初始能量是相同的，則距離基站較近的內(nèi)環(huán)簇頭就會快速死亡而縮短網(wǎng)絡(luò)壽命。

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

2算法系統(tǒng)模型

2.1　網(wǎng)絡(luò)模型

將圓形的網(wǎng)絡(luò)監(jiān)測區(qū)域劃分成多個寬度相等的環(huán)。在每個環(huán)中劃分很多大小均等的簇，并且各個環(huán)中的簇的規(guī)模也是相等的。將簇頭的位置和所需具備的能量預先計算出來，并放置在對應位置上。每個簇由簇頭和其周圍的普通成員節(jié)點組成。

圖1　圓環(huán)模型

采用如下合理假設(shè)來簡化網(wǎng)絡(luò)模型：

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

2) 簇頭節(jié)點對簇成員發(fā)送的數(shù)據(jù)進行融合的能力相同，對于其他環(huán)中簇頭轉(zhuǎn)發(fā)來的數(shù)據(jù)由于和本環(huán)中的數(shù)據(jù)相關(guān)性不大，所以不再對其進行融合，而是直接轉(zhuǎn)發(fā)給內(nèi)環(huán)簇頭或者基站。

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

4) 網(wǎng)絡(luò)壽命定義為從網(wǎng)絡(luò)部署到第一個節(jié)點死亡的時間。

算法所用到的符號及相關(guān)定義如表1所示。

表1　符號及定義

2.2　能量模型

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

(2)

節(jié)點接收端能量消耗為

(3)

假設(shè)傳感器節(jié)點進行監(jiān)測的能耗為Esen，簇頭對數(shù)據(jù)進行融合的能耗為Ecom。

2.3　相關(guān)參數(shù)的優(yōu)化設(shè)置

2.3.1簇頭間數(shù)據(jù)轉(zhuǎn)發(fā)能耗

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

(4)

第i-1層環(huán)中簇的簇頭到基站的距離為

(5)

第i層環(huán)中簇的簇頭到基站的距離為

(6)

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

(7)

第i層環(huán)中簇的簇頭到第i-1層環(huán)中簇頭的最小的最近距離近似滿足

(8)

取式(7)和式(8)的平均值作為第i層環(huán)中簇頭到第i-1層環(huán)中簇頭的最佳數(shù)據(jù)轉(zhuǎn)發(fā)距離，則

(9)

那么，第i層環(huán)中簇的簇頭到第i-1層環(huán)中簇頭進行一次數(shù)據(jù)轉(zhuǎn)發(fā)每單位時間要消耗的傳輸能量為

(10)

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

(11)

2.3.2普通節(jié)點的傳輸距離

第一層環(huán)內(nèi)的節(jié)點直接與匯點進行傳輸，故第一層環(huán)的普通節(jié)點的最遠傳輸距離為：

(12)

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

(13)

為延長網(wǎng)絡(luò)壽命，使普通節(jié)點的能耗盡量均衡，這里普通節(jié)點的最大傳輸距離應滿足下面的等式

(14)

又由于

(15)

通過上面的式(4)到式(15)，已知內(nèi)層環(huán)的簇數(shù)目mi，便可求得dchi、R1和mi+1等參數(shù)的最優(yōu)值。

2.3.3簇頭節(jié)點能耗

由于N個節(jié)點隨機分布在半徑為R的圓形區(qū)域內(nèi)，則第i層環(huán)內(nèi)一個簇內(nèi)的節(jié)點數(shù)為

(16)

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

(17)

普通節(jié)點單位時間的最大能耗為

(18)

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

(19)

2.4　理論分析

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

針對本文提出的模型，如果假設(shè)其各層環(huán)上的簇頭是能量同構(gòu)的，稱這個假設(shè)模型為簇頭能量同構(gòu)分簇模型CHEH。在提出的網(wǎng)絡(luò)模型中，第二層環(huán)的簇頭能耗是最大的，其能耗為ECH2。因此，初始能量最大的簇頭也位于第二層環(huán)，其初始能量為

(20)

網(wǎng)絡(luò)中節(jié)點的總能量為

(21)

其中，Enontotal為網(wǎng)絡(luò)中普通節(jié)點的總能量。為了使得假設(shè)模型CHEH與本文提出的網(wǎng)絡(luò)模型壽命相同，其各層環(huán)上的簇頭的初始能量最小也要EiniCHk，則CHEH中節(jié)點的總能量為

(22)

所以，由式(20)到式(22)得出，本文提出的網(wǎng)絡(luò)模型和假設(shè)模型CHEH相比，可節(jié)省的能量為

(23)

3CBMBC協(xié)議仿真

測試場景為：200個節(jié)點均勻分布在半徑為50的圓形區(qū)域.將圓形區(qū)域劃分成等寬的圓環(huán)，在劃分好的每個環(huán)中適當?shù)奈恢貌渴鹨欢〝?shù)量的有較高能量的節(jié)點作為簇頭。

3.1　仿真參數(shù)設(shè)置

具體仿真參數(shù)如表2所示。

表2　仿真參數(shù)的設(shè)置

對于有兩層環(huán)的網(wǎng)絡(luò)，將m2分別取值為：4，6，8,…,20。當m2取不同值時，計算其他各項參數(shù)的最優(yōu)值，結(jié)果如表3所示。

表3　仿真參數(shù)最優(yōu)值

3.2　仿真結(jié)果及其分析

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

圖2　二層環(huán)上簇數(shù)不同時網(wǎng)絡(luò)壽命

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

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

圖3所示為3種協(xié)議的網(wǎng)絡(luò)生存時間對比曲線圖。

圖3　不同協(xié)議網(wǎng)絡(luò)壽命比較

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

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

圖4　兩層環(huán)網(wǎng)絡(luò)和三層環(huán)網(wǎng)絡(luò)的壽命比較

如圖4所示，為網(wǎng)絡(luò)劃分三層環(huán)時網(wǎng)絡(luò)的壽命較長。但需要以增加簇頭的能量且提高算法設(shè)計的復雜度為代價。

4結(jié)束語

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

參考文獻：

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

[2]毛曉峰,楊眠,毛迪林.無線傳感器網(wǎng)絡(luò)應用綜述[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]袁輝勇,王志和,劉永逸.基于不均勻圓環(huán)模型的無線傳感器網(wǎng)絡(luò)分簇算法[J].信息與控制,2008,7(4):509-512.

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

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

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

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

(責任編輯楊繼森)

收稿日期：2015-02-20

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

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

doi:10.11809/scbgxb2015.07.027

中圖分類號：TP393

文獻標識碼：A

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

本文引用格式：王春梅.一種新的分環(huán)多跳均勻分簇協(xié)議分析及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

【信息科學與控制工程】