基于不均等分層分簇的無線傳感器網(wǎng)絡(luò)協(xié)議

張智超

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西西安 710126)

在無線傳感器網(wǎng)絡(luò)(WSNs)中傳感器節(jié)點(diǎn)的能量有限且電池不易更換。因此，如何均衡網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗，延長網(wǎng)絡(luò)使用壽命成為一個(gè)研究熱點(diǎn)。目前分簇結(jié)構(gòu)被認(rèn)為是能夠有效平衡傳感器網(wǎng)絡(luò)能耗的拓?fù)浣Y(jié)構(gòu)［1］。如早期的 LEACH 協(xié)議［2］功耗較低，但簇頭選取較為盲目，會(huì)造成簇內(nèi)節(jié)點(diǎn)能量消耗不均勻。改進(jìn)的分簇協(xié)議，如 HEED協(xié)議［3］提出備用簇頭的選取機(jī)制，并通過簇頭多跳傳輸以盡可能平衡網(wǎng)絡(luò)的能耗。EEUC協(xié)議［4］提出節(jié)點(diǎn)競選半徑選取機(jī)制，且節(jié)點(diǎn)競選半徑大小與節(jié)點(diǎn)到基站距離成正比，這樣既減少了離基站較近的簇內(nèi)節(jié)點(diǎn)數(shù)量又使簇頭有更多能量用于簇間信息的多跳傳輸，因此EEUC協(xié)議具有較好的能耗平衡效果。但對于傳感器節(jié)點(diǎn)數(shù)量較多和監(jiān)控區(qū)域面積較廣的情形，EEUC協(xié)議會(huì)導(dǎo)致距離基站較遠(yuǎn)的簇內(nèi)節(jié)點(diǎn)數(shù)量多，使得簇頭的簇內(nèi)負(fù)擔(dān)較重，因此EEUC協(xié)議不利于長期監(jiān)測。為此，本文進(jìn)一步優(yōu)化EEUC協(xié)議，提出一種不均等分層分簇協(xié)議UHC，依據(jù)節(jié)點(diǎn)到基站距離的不同情況設(shè)置不同的節(jié)點(diǎn)競選半徑，體現(xiàn)出網(wǎng)絡(luò)的分層分簇效果。UHC協(xié)議旨在控制簇內(nèi)節(jié)點(diǎn)密度，并使距離基站較近的簇頭有更多能量用于簇間信息傳遞，同時(shí)又減輕距離基站較遠(yuǎn)簇頭的簇內(nèi)負(fù)擔(dān)，延長簇頭使用壽命。

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

本文在一個(gè)矩形區(qū)域內(nèi)隨機(jī)部署N個(gè)靜態(tài)節(jié)點(diǎn)對該區(qū)域進(jìn)行環(huán)境監(jiān)控。用si表示第i個(gè)節(jié)點(diǎn)，S={s1，s2，…，sN}表示所有節(jié)點(diǎn)的集合，BS表示基站。對網(wǎng)絡(luò)模型作如下假設(shè):(1)網(wǎng)絡(luò)中所有節(jié)點(diǎn)隨機(jī)分布在一個(gè)矩形區(qū)域中。(2)網(wǎng)絡(luò)中只有一個(gè)基站，每個(gè)節(jié)點(diǎn)均了解基站和自身的位置，可通過基站給節(jié)點(diǎn)發(fā)送信息的電波強(qiáng)度進(jìn)行評估節(jié)點(diǎn)與基站的距離，節(jié)點(diǎn)和基站一旦布置好則不發(fā)生移動(dòng)。(3)網(wǎng)絡(luò)中所有節(jié)點(diǎn)信號傳輸半徑是可以進(jìn)行調(diào)整的。(4)節(jié)點(diǎn)的數(shù)據(jù)傳輸滿足對稱性。(5)簇頭對從簇成員收集到的數(shù)據(jù)可進(jìn)行數(shù)據(jù)融合。

本文采用一個(gè)簡單模型來衡量節(jié)點(diǎn)在通信過程中的能量消耗

式(1)中，ETx(l，d)表示與節(jié)點(diǎn)相隔距離為d;傳輸數(shù)據(jù)包大小為l bit所消耗的能量，其中d0是預(yù)先設(shè)定好的傳輸距離;Eelec表示電子能量，∈fsd2和l∈fsd4表示放大器的能量消耗，依賴于傳輸距離。式(2)表示節(jié)點(diǎn)接收一個(gè)l bit數(shù)據(jù)包所消耗的能量。

2 UHC協(xié)議

EEUC協(xié)議通過調(diào)整節(jié)點(diǎn)競選半徑的大小，使簇結(jié)構(gòu)的大小與節(jié)點(diǎn)到基站距離成正比。對于大規(guī)模傳感器網(wǎng)絡(luò)，其節(jié)點(diǎn)數(shù)量較多并且覆蓋區(qū)域較廣，如果采用EEUC協(xié)議，則會(huì)使得距離基站較遠(yuǎn)的簇結(jié)構(gòu)較大，加快簇頭能量消耗，當(dāng)簇頭能量低于設(shè)定界限時(shí)，則需要進(jìn)行簇頭輪換，在簇頭頻繁輪換后，容易出現(xiàn)能量空洞。為解決這一問題，本文提出的UHC協(xié)議重新設(shè)定節(jié)點(diǎn)競選半徑的選取機(jī)制，對網(wǎng)絡(luò)覆蓋區(qū)域進(jìn)行分層，在分層處節(jié)點(diǎn)競選半徑會(huì)急劇減小，使該層內(nèi)節(jié)點(diǎn)競選半徑由一個(gè)較小值進(jìn)行遞增。在節(jié)點(diǎn)競選半徑計(jì)算中添加一個(gè)參數(shù)α(0＜α＜1)，可將網(wǎng)絡(luò)覆蓋區(qū)域劃分為兩層，假定dmax表示節(jié)點(diǎn)到基站的最遠(yuǎn)距離，d(si，BS)表示節(jié)點(diǎn)si到基站BS的歐氏距離，覆蓋區(qū)域的劃分界限為 α·dmax，即當(dāng) d(si，BS)＜ α·dmax時(shí)，節(jié)點(diǎn) si屬于第一層;當(dāng)d(sj，BS)≥α·dmax時(shí)，節(jié)點(diǎn) sj屬于第二層，分簇示意圖如圖1所示。

圖1 分簇示意圖

在競選節(jié)點(diǎn)中選擇簇頭，簇頭能夠長時(shí)間工作的必要條件是剩余能量相對充足，若只考慮節(jié)點(diǎn)剩余能量，無法保障節(jié)點(diǎn)能量的高效利用，而節(jié)點(diǎn)度密度和能量消耗速度會(huì)影響節(jié)點(diǎn)的能量使用效率和時(shí)間。若節(jié)點(diǎn)能量消耗速度過快，易導(dǎo)致簇頭頻繁輪換，每次競選新簇頭時(shí)，會(huì)增加簇內(nèi)節(jié)點(diǎn)間的通信量，增加不必要的能耗。節(jié)點(diǎn)的度密度能體現(xiàn)節(jié)點(diǎn)在傳輸信息過程中的重要性，選擇合適的度密度，有利于尋找較好的信息傳輸路徑并減小信息傳遞的能耗。本文對此進(jìn)行優(yōu)化，同時(shí)考慮節(jié)點(diǎn)的剩余能量、度密度和能量消耗速度3個(gè)因素，并賦予權(quán)重a，b，c，選出最優(yōu)簇頭，由于每個(gè)節(jié)點(diǎn)只需進(jìn)行除法和加法運(yùn)算，不會(huì)明顯增加節(jié)點(diǎn)的運(yùn)算負(fù)擔(dān)?？紤]無線通信的特性，使簇頭之間通過多跳傳輸具有較高的能量效率［6－8］，本文設(shè)定一個(gè)中轉(zhuǎn)簇頭的選擇機(jī)制，選擇距離基站較近且簇內(nèi)節(jié)點(diǎn)密度較少的簇頭優(yōu)先進(jìn)行中轉(zhuǎn)，促進(jìn)網(wǎng)絡(luò)節(jié)點(diǎn)能量的均衡消耗。UHC協(xié)議主要包括3部分:(1)確立節(jié)點(diǎn)競選半徑。由每個(gè)節(jié)點(diǎn)si生成一個(gè)隨機(jī)數(shù)xi，xi∈(0，1)，i=1，2，L，N。設(shè)定一個(gè)閾值 T，T∈(0，1)。當(dāng) xi＜ T時(shí)，則節(jié)點(diǎn)si參加簇頭競選，成為競選節(jié)點(diǎn)。通過增加T值的大小，可以增加競選節(jié)點(diǎn)的數(shù)量，從而增大競選節(jié)點(diǎn)感知范圍對網(wǎng)絡(luò)區(qū)域的覆蓋。

由于每個(gè)節(jié)點(diǎn)知道基站和自己的位置，可估計(jì)出與基站之間的歐氏距離，根據(jù)如下方法確定每個(gè)節(jié)點(diǎn)的競選半徑:

設(shè)置一個(gè)參數(shù)α(0＜α＜1)，節(jié)點(diǎn)si的競選半徑為

當(dāng) d(si，BS)≥α·dmax時(shí)，令 Di=dmax－ α·d(si，BS)。

當(dāng) d(si，BS)＜ α·dmax時(shí)，令 Di=dmax－ d(si，BS)。

式(3)中，R是提前設(shè)定的一個(gè)競選半徑，C是一個(gè)常數(shù)，0＜C＜1。dmax是傳感器節(jié)點(diǎn)到基站的最大距離，dmin是傳感器節(jié)點(diǎn)到基站的最小距離。

(2)簇頭選取。每個(gè)節(jié)點(diǎn)需要記錄上一輪分簇時(shí)的剩余能量，在第一輪分簇時(shí)，記錄節(jié)點(diǎn)的初始能量。每個(gè)競選節(jié)點(diǎn)按式(4)計(jì)算Pi(i)值，在節(jié)點(diǎn)si的競選半徑內(nèi)，將si的P(i)值與其他競選節(jié)點(diǎn)sj(i≠j)內(nèi)的Pj(j)值進(jìn)行比較，若Pi(i)＜Pj(j)，則節(jié)點(diǎn)si變?yōu)槠胀ü?jié)點(diǎn)，否則節(jié)點(diǎn)sj變?yōu)槠胀ü?jié)點(diǎn)。重復(fù)操作，最終每個(gè)節(jié)點(diǎn)的競選半徑內(nèi)只有一個(gè)競選節(jié)點(diǎn)，該節(jié)點(diǎn)作為簇頭并向競選半徑內(nèi)的其他節(jié)點(diǎn)發(fā)送一個(gè)競選成功信息，表明競選簇頭成功，其他節(jié)點(diǎn)接收到信息后加入該簇

這里Ei是節(jié)點(diǎn)si當(dāng)前的剩余能量;Eti是上一輪分簇時(shí)節(jié)點(diǎn)si的剩余能量;Nneig是節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)數(shù)目;N是所有節(jié)點(diǎn)總數(shù);Eti－Ei表示節(jié)點(diǎn)上一輪的能量消耗，系數(shù) a，b，c∈(0，1)且 a+b+c=1。對于節(jié)點(diǎn)分布較稀疏的網(wǎng)絡(luò)，節(jié)點(diǎn)度密度一般較小，重點(diǎn)考慮節(jié)點(diǎn)剩余能量和能量消耗速度，即選取較大的a，c值。對于節(jié)點(diǎn)分布較集中的網(wǎng)絡(luò)，節(jié)點(diǎn)度密度較高，高度密度的節(jié)點(diǎn)能量消耗速度一般較快，此時(shí)重點(diǎn)考慮節(jié)點(diǎn)剩余能量和度密度，即選取較大的a，b值。由此根據(jù)網(wǎng)絡(luò)側(cè)重點(diǎn)靈活選擇比重，本文對簇頭的選取相對注重節(jié)點(diǎn)的剩余能量和能量消耗速度，選取權(quán)重為a=0.5，b=0.2，c=0.3。

(3)簇頭骨干結(jié)構(gòu)。簇頭與基站之間通過多跳傳輸信息能夠提高能量效率，簇頭骨干結(jié)構(gòu)示意圖已在圖1中給出，簇頭的下一跳中轉(zhuǎn)簇頭的選擇機(jī)制如下:1)首先選擇距離基站較近的鄰居簇頭，即中轉(zhuǎn)簇頭到基站的距離小于其上一跳簇頭到基站的距離，保證簇頭信息傳輸方向指向基站。2)當(dāng)出現(xiàn)多個(gè)可選擇中轉(zhuǎn)簇頭時(shí)，考慮中轉(zhuǎn)簇頭的剩余能量、節(jié)點(diǎn)度密度和到基站的距離，計(jì)算一個(gè)概率值P'i(i)，由P'i(i)值最大的作為中轉(zhuǎn)簇頭。

其中各符號所表示的含義與式(4)一致，本文對中轉(zhuǎn)簇頭的選取相對注重節(jié)點(diǎn)的度密度，選取權(quán)重為a=0.4，b=0.4，c=0.2。

3 仿真結(jié)果

采用Matlab軟件進(jìn)行仿真實(shí)驗(yàn)，首先將UHC協(xié)議的分簇效果示意圖與EEUC協(xié)議進(jìn)行比較，檢驗(yàn)簇分布的改變情況。然后比較不同參數(shù)對網(wǎng)絡(luò)分簇結(jié)果的影響，再比較EEUC協(xié)議與UHC協(xié)議的分簇結(jié)果和網(wǎng)絡(luò)壽命，評估UHC協(xié)議是否有效延長網(wǎng)絡(luò)壽命。網(wǎng)絡(luò)參數(shù)如表1所示。

表1 網(wǎng)絡(luò)參數(shù)表

UHC協(xié)議中對EEUC協(xié)議的節(jié)點(diǎn)競選半徑和簇頭選取機(jī)制進(jìn)行了改進(jìn)，文中將分層后節(jié)點(diǎn)的競選半徑與原EEUC協(xié)議進(jìn)行作差比較

在設(shè)定相同參數(shù)α=0.3的條件下，將EEUC協(xié)議和UHC協(xié)議的仿真分簇效果進(jìn)行對比，其中分層參數(shù)。如圖2和圖3所示，分別表示EEUC協(xié)議和UHC協(xié)議的分簇結(jié)果。在橫坐標(biāo)區(qū)間(250，400)內(nèi)，圖2和圖3的分簇結(jié)果基本相同，但在區(qū)間(0，200)中，圖2中各簇內(nèi)節(jié)點(diǎn)數(shù)量較多，而在圖3中簇內(nèi)節(jié)點(diǎn)數(shù)量較少，出現(xiàn)分層，驗(yàn)證UHC協(xié)議有效控制了簇內(nèi)節(jié)點(diǎn)密度。

圖2 EEUC分簇示意圖

圖3 UHC分簇示意圖

根據(jù)UHC協(xié)議中對節(jié)點(diǎn)競選半徑的設(shè)定，節(jié)點(diǎn)競選半徑的大小與參數(shù)R和C的取值有關(guān)。當(dāng)R值不變時(shí)，隨著C值的增大，由(3)式可知節(jié)點(diǎn)競選半徑將減小，這樣將導(dǎo)致每個(gè)競選節(jié)點(diǎn)的競選半徑內(nèi)的競選節(jié)點(diǎn)數(shù)量減少，使得能夠有更多的競選節(jié)點(diǎn)成為簇頭，增加簇頭數(shù)量。當(dāng)C值不變時(shí)，隨著R值的增大，可判斷出Ri將增大，使得競選半徑內(nèi)競選節(jié)點(diǎn)數(shù)量增加，由于競選半徑內(nèi)最終只會(huì)有一個(gè)競選節(jié)點(diǎn)成為簇頭，導(dǎo)致簇頭數(shù)量減少。如圖4所示，分別設(shè)定3個(gè)不同的C值，記錄分簇個(gè)數(shù)隨著R值增大的變化情況，圖中分簇個(gè)數(shù)的整體趨勢均隨R的增大而減少，圖中當(dāng)C=0.6時(shí)，分簇個(gè)數(shù)比其他兩種情況多。在實(shí)際檢驗(yàn)應(yīng)用中，簇頭個(gè)數(shù)在總節(jié)點(diǎn)數(shù)的5%左右較好，若簇頭個(gè)數(shù)過多，則可能出現(xiàn)孤立的簇頭節(jié)點(diǎn)，造成能量消耗過快，不利于網(wǎng)絡(luò)的長期運(yùn)行，本網(wǎng)絡(luò)中有600個(gè)隨機(jī)節(jié)點(diǎn)，為控制簇頭個(gè)數(shù)為總節(jié)點(diǎn)數(shù)的5%左右，可設(shè)定 R=50，C=0.6。

圖5為EEUC和UHC分簇個(gè)數(shù)的比較圖，圖中UHC協(xié)議分簇后簇頭個(gè)數(shù)多于EEUC算法，因?yàn)樵赨HC協(xié)議中，距離基站距離超過分層界限的節(jié)點(diǎn)，其競選半徑相對于EEUC中的減小，使得距離基站較遠(yuǎn)的節(jié)點(diǎn)有更多機(jī)會(huì)當(dāng)選簇頭，使簇內(nèi)節(jié)點(diǎn)密度降低，從而使網(wǎng)絡(luò)出現(xiàn)分層現(xiàn)象。

圖4 簇個(gè)數(shù)示意圖

圖5 簇個(gè)數(shù)比較

圖6 分層參數(shù)影響

圖7 網(wǎng)絡(luò)壽命比較

分層參數(shù)個(gè)數(shù)和大小的選取也會(huì)影響簇頭個(gè)數(shù)，本文添加一個(gè)分層參數(shù)α(0＜α＜1)，將網(wǎng)絡(luò)劃分成兩層，若再設(shè)置一個(gè)參數(shù)β(α＜β＜1)可將網(wǎng)絡(luò)劃分成3層，以此類推，可設(shè)置多個(gè)參數(shù)，將網(wǎng)絡(luò)劃分成多個(gè)層次。但將網(wǎng)絡(luò)劃分的層次過多，會(huì)造成簇內(nèi)節(jié)點(diǎn)密度過小，容易出現(xiàn)孤立節(jié)點(diǎn)的簇，這樣在簇頭輪換中，并無替代節(jié)點(diǎn)，容易出現(xiàn)能量空洞，所以需根據(jù)實(shí)際網(wǎng)絡(luò)規(guī)模選擇是否進(jìn)行分層和具體劃分為幾層，以此選擇合適的參數(shù)個(gè)數(shù)。分層參數(shù)α的大小對網(wǎng)絡(luò)簇頭個(gè)數(shù)的影響如圖6所示，這里取參數(shù)C=0.6，α分別取值0.1、0.3、0.5、0.7、0.9，隨著參數(shù) R 的增大，分簇個(gè)數(shù)呈現(xiàn)遞減的變化趨勢，但是根據(jù)本網(wǎng)絡(luò)，簇頭的適宜個(gè)數(shù)約為35，可以取參數(shù)α=0.5，具有較大的調(diào)整空間。

在圖7中分析比較了參數(shù)C對網(wǎng)絡(luò)壽命的影響，取R=40，采用UHC協(xié)的網(wǎng)絡(luò)壽命基本上比EEUC明顯延長，起始部分網(wǎng)絡(luò)壽命隨著C值增大而增加，在C=0.6時(shí)，網(wǎng)絡(luò)壽命達(dá)到最大，當(dāng)C＞0.6時(shí)，網(wǎng)絡(luò)壽命出現(xiàn)減少，所以并非C值越大對網(wǎng)絡(luò)越好，這里選擇C－0.6為最優(yōu)。

4 結(jié)束語

提出的UHC協(xié)議對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行分層分簇，促進(jìn)了能量消耗均衡，延長網(wǎng)絡(luò)使用壽命。UHC協(xié)議在節(jié)點(diǎn)數(shù)量較大時(shí)效果明顯，對于小規(guī)模傳感器網(wǎng)絡(luò)，可選擇不進(jìn)行分層。由于競選節(jié)點(diǎn)是隨機(jī)產(chǎn)生的，帶有不確定性，競選節(jié)點(diǎn)感知范圍對網(wǎng)絡(luò)的覆蓋不一定達(dá)到較高覆蓋率，所以未來進(jìn)一步的研究方向?yàn)榭紤]參加競選簇頭的節(jié)點(diǎn)感知范圍對網(wǎng)絡(luò)的覆蓋情況，希望覆蓋率可達(dá)80%以上，這樣較符合網(wǎng)絡(luò)的實(shí)際應(yīng)用需求。

［1］Yournis O，F(xiàn)ahmy S.Distributed clustering in ad － hoc sensor networks:a hybrid，energy － efficient approach［J］.In Proceedings of IEEE Transactions on Mobile Computing，2004，3(4):366－379.

［2］Heizelman W B，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.

［3］Ossama Y，Sonia F.Heed:A hybrid energy－ efficient distributed clustering approach for ad － hoc sensor networks［J］.IEEE Transactions on mobile computing，2004(4):660 －669.

［4］Guihai C，Chengfa L.An unequal cluster－ based routing protocol in wireless sensor networks［J］.Wireless Netw，2009，15:193－207.

［5］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks:communication，clustering and aggregation［J］.Ad Hoc Networks，2004，2(1):45 －63.

［6］韋然.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的設(shè)計(jì)與實(shí)現(xiàn)［J］.電子科技，2012，25(1):31 －35.

［7］馬玨.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)［J］.電子科技，2012，25(12):34 －36，39.

［8］徐振峰，尹晶晶，陳小林，等.基于ZigBee協(xié)議棧的無線傳感器網(wǎng)絡(luò)的設(shè)計(jì)［J］.電子設(shè)計(jì)工程，2012，20(5):75－77，81.