一種新的無線傳感器網(wǎng)絡(luò)非均勻分簇雙簇頭算法
——PUDCH算法*

戴志強，嚴(yán) 承，武正江

（1.吉首大學(xué)生態(tài)旅游應(yīng)用技術(shù)湖南省重點實驗室，湖南張家界427000；2.黔南民族師范學(xué)院計算機與信息學(xué)院，貴州都勻558000；3.中南大學(xué)軟件學(xué)院，長沙410075）

一種新的無線傳感器網(wǎng)絡(luò)非均勻分簇雙簇頭算法
——PUDCH算法*

戴志強1，嚴(yán) 承2*，武正江3

（1.吉首大學(xué)生態(tài)旅游應(yīng)用技術(shù)湖南省重點實驗室，湖南張家界427000；2.黔南民族師范學(xué)院計算機與信息學(xué)院，貴州都勻558000；3.中南大學(xué)軟件學(xué)院，長沙410075）

能量利用效率問題一直是限制WSN廣泛應(yīng)用的瓶頸，能源容量對各個網(wǎng)絡(luò)節(jié)點產(chǎn)生至關(guān)重要的影響。針對WSN中“能量空洞問題”以及由于簇頭任務(wù)過重所導(dǎo)致的能量消耗過快，同時也為了提高WSN的能量利用效率，提出了一種無線傳感器網(wǎng)絡(luò)非均勻分簇雙簇頭算法——PUDCH。該算法先綜合考慮節(jié)點綜合信息（如節(jié)點剩余能量、節(jié)點到基站的距離），根據(jù)節(jié)點綜合信息通過不同的時間競爭機制來選舉簇頭，將整個網(wǎng)絡(luò)劃分為不均勻的分簇；在規(guī)模大些的簇內(nèi)，為了減輕簇頭的負(fù)擔(dān)再選取副簇頭。最后簇頭再構(gòu)造基于最小生成樹的最優(yōu)傳輸路徑。一系列的仿真表明PUDCH路由算法在WSN節(jié)約平衡節(jié)點能量消耗方面表現(xiàn)優(yōu)良。

無線傳感器網(wǎng)絡(luò)；雙簇頭；非均勻分簇；最小生成樹

無線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Network）是由數(shù)目龐大的傳感器節(jié)點以及基站構(gòu)成，具有低功耗、有限的數(shù)據(jù)傳輸與電源能量限制的特點，節(jié)點通過無線通信來監(jiān)控某一特定地區(qū)，處理數(shù)據(jù)然后向基站傳輸處理過的數(shù)據(jù)［1-2］。然而，在無線傳感器網(wǎng)絡(luò)中由于節(jié)點的分布不均勻等問題導(dǎo)致有些節(jié)點能量消耗過快，造成能量空洞問題，本文提出了一種改善熱點問題的方法，避免因熱點問題導(dǎo)致簇頭節(jié)點能量消耗過快導(dǎo)致簇頭節(jié)點相較其他節(jié)點提前死亡的問題。

1 相關(guān)工作

分簇是改善WSN能量消耗的一種有效的方法。在眾多的低能量自適應(yīng)分簇路由算法中，2000年Heinzelman等人提出的的LEACH［3］算法最為經(jīng)典。LEACH選擇簇頭的機制為隨機選擇，通過這種方式來改善節(jié)點能量消耗。但其缺點也很明顯，簇頭節(jié)點與基站的數(shù)據(jù)傳輸方式為單跳傳輸十分不利于無線傳感器網(wǎng)絡(luò)的擴(kuò)展，進(jìn)一步限制了WSN在實際應(yīng)用中的廣泛應(yīng)用。并且由于簇頭節(jié)點通過單跳路由通信協(xié)議與基站進(jìn)行通信，所以會導(dǎo)致離基站較遠(yuǎn)的簇頭能量消耗過大而較早死亡，導(dǎo)致網(wǎng)絡(luò)出現(xiàn)割裂，從而大大縮減整個無線傳感器網(wǎng)絡(luò)的壽命。

為了解決距離基站較遠(yuǎn)的簇頭節(jié)點能量消耗過快的問題，國內(nèi)外專家學(xué)者提出了許多改進(jìn)的算法。李成法等人提出了一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［4］，針對距離基站較遠(yuǎn)的簇頭節(jié)點能量消耗過快的問題，該算法采用了簇頭節(jié)點通過多跳路由通信協(xié)議與基站進(jìn)行通信，有效的緩解了距離基站較遠(yuǎn)的簇頭節(jié)點能量消耗過快的問題，但距離基站較近的簇頭則會承擔(dān)更多的數(shù)據(jù)處理與轉(zhuǎn)發(fā)任務(wù)而消耗過多能量，從而形成“熱區(qū)”。為了解決“熱區(qū)”問題，李成法等人又提出一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議--EEUC算法［5］。同樣，蔣暢江等人提出能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議——DEBUC算法［6］，劉鐵流等人基于能量優(yōu)化的無線傳感器網(wǎng)絡(luò)分簇路由算法［7］，嚴(yán)英等人提出一種一種基于LEACH與PEGASIS協(xié)議的分層成鏈優(yōu)化路由算法［8］，三種分簇算法均采用非均勻分簇，距離基站遠(yuǎn)的分簇規(guī)模大一些，距離基站近的分簇規(guī)模小一些有效均衡節(jié)點能量消耗，延長WSN使用周期，但簇頭選擇機制并沒有發(fā)生質(zhì)的改變，其簇頭選擇機制依舊采用的是與LEACH算法的簇頭選擇機制相同的依靠概率和門限值來決定選擇哪些節(jié)點選做簇頭節(jié)點，不能保證所選擇簇頭最為合適。為了改善簇頭隨機選擇機制，盧先順等人提出一種無線傳感器網(wǎng)絡(luò)能量均衡的非均勻分簇算法——EBUCA算法［9］，簇頭選擇門限值綜合考慮了節(jié)點剩余能量、節(jié)點密度、簇頭密度及簇半徑，從而優(yōu)化了簇頭選擇，減小節(jié)點能量消耗，延長了WSN使用壽命，但是還是存在在一些規(guī)模較大的分簇中簇頭消耗的能量過快的問題。針對簇頭節(jié)點承擔(dān)數(shù)據(jù)收集傳輸?shù)呢?fù)擔(dān)過大，徐丹丹等人提出了一種基于最大連通度的雙簇頭分簇算法［10］，簇頭選擇機制是綜合考慮節(jié)點間的最大連通度和能量來選擇主副簇頭，主副簇頭分工合作，有效減小了簇頭所承擔(dān)的數(shù)據(jù)處理傳輸?shù)呢?fù)載，存在的不足就是選擇簇頭時廣播信息較多，導(dǎo)致能量消耗過大。文獻(xiàn)［11-12］雖然提出的算法是在不均勻分簇的基礎(chǔ)上，但競選簇頭路由考慮的因素比較單一。

針對以上文獻(xiàn)中簇頭選取考慮的因素有些單一與不足，本文提出了一種基于時間競爭機制的改進(jìn)的非均勻分簇路由算法。算法在簇頭選擇時考慮到節(jié)點的綜合信息，而不是單單只看一種信息，將整個網(wǎng)絡(luò)劃分為不均勻的簇，然后在規(guī)模較大的簇內(nèi)重新選擇主副簇頭，主簇頭所剩能量要高于副簇頭所剩能量，因為主簇頭需要承擔(dān)數(shù)據(jù)采集，這將消耗大量能量，副簇頭需要承擔(dān)數(shù)據(jù)融合與傳輸。并且在數(shù)據(jù)傳輸階段，該算法優(yōu)化了簇頭路由，減小節(jié)點能量消耗，延長了WSN使用壽命。

2 相關(guān)模型

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

本文假設(shè)傳感器網(wǎng)絡(luò)具有如下性質(zhì)：①基站獨立于節(jié)點分布區(qū)域，各個節(jié)點能夠互相進(jìn)行通信并且每個節(jié)點能與基站直接進(jìn)行通信。②節(jié)點靜止分布在區(qū)域內(nèi)，且地理坐標(biāo)與一些硬件信息未知，用Ni表示第i各節(jié)點，節(jié)點集合N={N1，N2，…，Nn}。③節(jié)點能根據(jù)接收信號的強度來計算發(fā)出者到自己的近似距離，改變自己的功率大小，各個節(jié)點具有相等的初始能量。④為了節(jié)約能量，節(jié)點的收發(fā)器能進(jìn)入休眠模式。

2.2 能量模型

無線傳感器網(wǎng)絡(luò)中節(jié)點進(jìn)行數(shù)據(jù)傳輸時所耗的能量與其他功能所消耗的能量相比要大得多。本文采用文獻(xiàn)［3］中的無線通信能耗模型，發(fā)送數(shù)據(jù)時其能耗公式如下：

式中：l為要發(fā)送的數(shù)據(jù)長度（比特），Eelec為節(jié)點發(fā)送或接收每比特數(shù)據(jù)的電路消耗的能量，它取決于信號的編碼形式、過濾以及傳播方式。d為發(fā)送節(jié)點到接收節(jié)點之間的距離，當(dāng)d＜dc，能耗采用自由空間模型；當(dāng)d≥dc，能耗采用多路徑衰減模型。εfs與εtwo-ray分別為功率放大倍數(shù)。

節(jié)點接收lbit數(shù)據(jù)所消耗的能量計算公式為

節(jié)點接收數(shù)據(jù)后進(jìn)行數(shù)據(jù)融合同樣需要消耗能量，但本文的重點不在于此，且現(xiàn)實中節(jié)點的數(shù)據(jù)融合是個復(fù)雜的過程，結(jié)合前人所做的工作以及試驗方法，本文采用同樣的數(shù)據(jù)融合方式即簇頭無論接收了多少數(shù)據(jù)都統(tǒng)一融合成lbit大小的數(shù)據(jù)。

3 PUDCH算法設(shè)計

全部網(wǎng)絡(luò)節(jié)點部署完畢后，基站向網(wǎng)絡(luò)內(nèi)所有節(jié)點發(fā)送一個強信號，每個節(jié)點根據(jù)自身接收到的信號強度大小來計算自身到基站的大體距離，以便節(jié)點根據(jù)自身與基站的距離來確定自身理想的發(fā)射功率，盡可能節(jié)省發(fā)射信息所消耗的能量，并且可以達(dá)到整個無線傳感器網(wǎng)絡(luò)的不均勻分簇的目的，進(jìn)一步減小了節(jié)點能量消耗。

PUDCH路由協(xié)議采用周期方式運行，每輪分為簇頭建立階段和數(shù)據(jù)傳輸階段。在數(shù)據(jù)傳輸階段，以簇頭剩余能量、簇頭與基站間的距離以及傳輸數(shù)據(jù)大小作為權(quán)值，利用權(quán)值建立基于權(quán)值的最小生成樹的最優(yōu)傳輸路徑，進(jìn)一步減小節(jié)點能量消耗，延長WSN使用壽命。圖1是PUDCH協(xié)議基本原理示意圖，圖中半徑不等的的圓圈代表依據(jù)該算法實現(xiàn)的非均勻分簇，圓中黑點代表分簇中的主簇頭，一些規(guī)模大的圓圈中的紅點代表該簇中的副簇頭，主副簇頭節(jié)點之間的連線代表數(shù)據(jù)傳輸路徑，各個主簇頭之間帶箭頭的黑色細(xì)線則代表主簇頭間多跳數(shù)據(jù)傳輸?shù)穆窂健?/p>

圖1 PUDCH協(xié)議基本原理示意圖

3.1 簇頭選舉

PUDCH協(xié)議是一種采用分布式時序的方式競選簇頭的算法，建立主副簇頭階段分為奇數(shù)輪和偶數(shù)輪，考慮節(jié)點綜合信息產(chǎn)生主副簇頭，如偽代碼中所示。假如每一輪都重新選擇簇頭無疑會消耗大量的能量，因為一輪所消耗的能量有限，我們可以把簇頭選擇分為奇數(shù)輪和偶數(shù)輪。奇數(shù)輪時簇頭按正常的流程來選擇，選出的簇頭依據(jù)簇內(nèi)節(jié)點剩余能量來選擇下一輪的簇頭（如圖2中的S1-2，S2-2），到下一輪也就是偶數(shù)輪時，依據(jù)上輪簇頭選擇的簇頭節(jié)點來當(dāng)作本輪的簇頭，如偽代碼中所示。節(jié)省了簇頭選擇所消耗的能量。在一些節(jié)點數(shù)目過多的分簇中簇頭節(jié)點數(shù)據(jù)收集融合傳輸所消耗的能量要比節(jié)點數(shù)目少的分簇簇頭節(jié)點消耗的多，會加速這些負(fù)擔(dān)過重的簇頭節(jié)點提前結(jié)束使用壽命，必須選出一個副簇頭來減小主簇頭負(fù)擔(dān)，延緩其能量消耗。但假如無論大小分簇都產(chǎn)生主副簇頭，無疑也會產(chǎn)生不必要的能量浪費。所以，我們可以依據(jù)簇的規(guī)模、節(jié)點剩余能量與傳輸數(shù)據(jù)的大小設(shè)置一個閥值，當(dāng)產(chǎn)生副簇頭的函數(shù)值大于閥值的時候該分簇就會產(chǎn)生副簇頭。否則，就不產(chǎn)生。

圖2 簇頭競爭示意圖

競選規(guī)則如下：

規(guī)則1在WSN中，如果一個節(jié)點通過時間競爭機制競選為簇頭，那么在它的競選半徑內(nèi)的所有候選節(jié)點都不能成為簇頭，如圖2所示，S1與S2可以成為簇頭，但S3不可以成為簇頭，因為S3所在位置已經(jīng)在S2競選半徑內(nèi)。

節(jié)點競爭半徑為：

規(guī)則2在PUDCH路由協(xié)議中，候選簇頭s.i的鄰居節(jié)點集合NTi為

NTi={s.i|s.i是候選簇頭，且d（s.i，s.j）＜max（Ri，Rj）}

規(guī)則3節(jié)點根據(jù)鄰居表中鄰居節(jié)點的剩余能量計算出平均剩余能量。

規(guī)則4節(jié)點根據(jù)鄰居表中鄰居節(jié)點與該節(jié)點的距離計算出平均距離，測距的原理是根據(jù)根據(jù)節(jié)點接收基站發(fā)送的信號的強度來判斷距離σ為人為設(shè)置參數(shù)，大小可根據(jù)具體應(yīng)用環(huán)境來進(jìn)行調(diào)節(jié)。

規(guī)則5本節(jié)點接收到DS發(fā)出的簇頭選擇消息后發(fā)出簇頭競爭消息的時間。

當(dāng)節(jié)點滿足ei＞Eavg

當(dāng)節(jié)點滿足ei≤Eavg：

式中：α為［0，1］之間的隨機數(shù)，Tch為預(yù)先要求的競選簇頭所需時間，ei為節(jié)點剩余能量，β為參數(shù)調(diào)整因子。由式（6）可知，簇頭競爭時間t根據(jù)節(jié)點剩余能量、到基站的距離以及鄰居節(jié)點與該節(jié)點的距離來定義的，從而節(jié)點剩余能量越低、到基站越遠(yuǎn)、鄰居節(jié)點平均距離越大的節(jié)點，t就越大，成為節(jié)點的概率就越小，從而保證了節(jié)點選取的合理性。由式（7）可知，當(dāng)大部分區(qū)域簇頭節(jié)點選出來以后，對一些暫時未能覆蓋的“縫隙”區(qū)域，利用式（7）在后Tch/2時間內(nèi)并行產(chǎn)生了剩余的簇頭。由于“縫隙”區(qū)域包含的節(jié)點較少，所以，節(jié)點競爭簇頭的參數(shù)因子ei/Emax大大降低了了低能量的節(jié)點成為簇頭的概率。規(guī)則六：副簇頭選取函數(shù)T

在分簇中數(shù)據(jù)密度越大節(jié)點剩余能量越低，簇頭節(jié)點的負(fù)擔(dān)就越重，能量消耗就越嚴(yán)重，基于此，當(dāng)簇頭節(jié)點負(fù)擔(dān)高于某一個特定的數(shù)值時必須選取副簇頭節(jié)點。α為人為設(shè)置參數(shù)，大小可調(diào)。n為簇中節(jié)點數(shù)目，S為數(shù)據(jù)量。

PUDCH路由協(xié)議簇頭選取偽代碼如下所示：

WSN選出候選節(jié)點后，普通節(jié)點進(jìn)入休眠狀態(tài)直到簇頭選舉完畢，以節(jié)省能量。每個候選簇頭節(jié)點廣播Prepare_Message（ID，Rc，Ei）消息，候選簇頭節(jié)點接收Prepare_Message（ID，Rc，Ei）消息后更新鄰居節(jié)點信息表，如第1行～第14行所示。接下來UDCH協(xié)議通過計時廣播的方法來競選簇頭，根據(jù)簇頭接受信號強度的大小來計算出簇頭與基站的大體距離Di，后面簇間路由的建立用得到。對于一般規(guī)模的分簇，主簇頭根據(jù)其余節(jié)點與它的距離以及節(jié)點的剩余能量來選擇第二簇頭（在下一輪作為簇頭），對于一些大規(guī)模的分簇則主簇頭除選出第二簇頭還要根據(jù)各個節(jié)點的具體信息來分別選擇式（7）或者式（8）選出副簇頭（負(fù)責(zé)向基站或其他簇頭節(jié)點傳輸經(jīng)過主簇頭處理過的數(shù)據(jù)），選出的副簇頭節(jié)點更加的科學(xué)合理。比其他一些算法通過單純比較剩余能量來競選簇頭要節(jié)省能量，因為候選節(jié)點通過這種方式來競選簇頭的話需要接受發(fā)出大量的消息，造成能量消耗過大，在一些密度較大的WSN中這個問題尤為嚴(yán)重。在奇數(shù)輪根據(jù)簇的大小來選舉主副簇頭以及下一輪的簇頭，在偶數(shù)輪直接利用上一輪所選的節(jié)點作為簇頭，如第30行～第42行所示。

3.2 數(shù)據(jù)傳輸路徑

經(jīng)過網(wǎng)絡(luò)分簇以及選取簇頭以后，節(jié)點采集的數(shù)據(jù)通過多跳最小生成樹的路由方式向基站進(jìn)行傳輸。先將網(wǎng)絡(luò)中的簇抽象為一個點，連接相鄰的點，這樣就構(gòu)造成了一個帶權(quán)值的有向連通圖G=（V，E），V代表簇頭節(jié)點與基站的集合，E代表簇頭連線間的權(quán)值。權(quán)值計算公式如式（8）所示，綜合考慮簇頭間距離、簇頭剩余能量以及簇的規(guī)模，計算出的權(quán)值更加的合理。

其中：wij為簇頭i、j之間抽象連線的權(quán)值，dij則表示簇頭i、j之間的距離，ei、ei則分別代表簇頭i、j的剩余能量，S代表簇的規(guī)模大小a，b則代表人為可調(diào)節(jié)參數(shù)，從式（9）中可以看出，權(quán)值的計算綜合考慮了簇頭間距離、簇頭剩余能量以及簇的規(guī)模，計算出的權(quán)值更加的合理。當(dāng)一個簇頭剩余能量低、簇頭間距離遠(yuǎn)并且簇的規(guī)模越大時，它的wij的取值就越大，那么該簇頭當(dāng)選負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)的概率就會降低，這樣就會使整個網(wǎng)絡(luò)節(jié)點的能量消耗更加均衡。

PUDCH算法簇間路由建立流程如下所示：

Step 1 傳輸數(shù)據(jù)的簇頭/副簇頭根據(jù)上面簇頭選擇時記錄的簇頭與基站的距離Di，在Di＜D0范圍內(nèi)的簇頭節(jié)點依據(jù)式（9）計算簇頭與基站之間邊的權(quán)值w，當(dāng)w＜w0時，簇頭向基站直接發(fā)送數(shù)據(jù)。

Step 2 有向連接圖G=（V，E）中，將向基站傳輸數(shù)據(jù)的簇頭歸入集合V1中，簇頭與基站的邊歸入集合T1中。

Step 3 各傳輸數(shù)據(jù)簇頭向周圍發(fā)送W_MSG信息，其他不能向簇頭直接發(fā)送數(shù)據(jù)的簇頭節(jié)點根據(jù)自己接收W_MSG信息的強度大小來計算兩簇頭節(jié)點之間的距離dij、自己的剩余能量以及分簇規(guī)模大小依據(jù)式（9）計算出兩簇頭之間連線所形成的“邊”的權(quán)值wij。

Step 4 選取兩簇頭之間wij最小的“邊”，然后將這條邊兩端的簇頭歸入到集合V1中，將此邊歸入集合E1中。

Step 5 重復(fù)執(zhí)行Step 4，直至集合V1=V。此時，E1中的元素構(gòu)成了最小生成樹。

Step 6 最小生成樹構(gòu)造完畢后，傳輸節(jié)點調(diào)整發(fā)射功率，使其能到達(dá)下一跳的鄰居節(jié)點為止。

由以上可以看出，本文路由選擇綜合考慮了簇頭節(jié)點剩余能量、簇頭節(jié)點之間以及簇頭與基站之間的距離、簇的規(guī)模大小，使數(shù)據(jù)傳輸路徑更加的合理化，能量消耗更加均衡合理，提高了無線傳感器網(wǎng)絡(luò)的健壯性，延長了網(wǎng)絡(luò)生存周期。

4 算法分析與仿真

消息的復(fù)雜度直接影響著WSN的能量消耗，因此，消息復(fù)雜度對于WSN來說非常重要，我們首先分析UDCH算法中的消息復(fù)雜度。

4.1 PUDCH算法復(fù)雜度分析

性質(zhì) 在整個WSN的簇頭競爭階段中，UDCH路由協(xié)議的消息復(fù)雜度為O（N）.

證明 在WSN的候選簇頭產(chǎn)生階段，在奇數(shù)輪中，網(wǎng)絡(luò)產(chǎn)生N×T個候選簇頭節(jié)點而參與競選，每個候選簇頭節(jié)點廣播一條Prepare_Message消息，共廣播N×T條。然后在簇頭競爭階段，假設(shè)一共有K個候選簇頭節(jié)點被選為主簇頭，那么一共發(fā)射K條FinalHead_Message消息，選取第二節(jié)點的時候普通節(jié)點一共發(fā)送N-K條消息。在偶數(shù)輪第二節(jié)點向簇內(nèi)發(fā)送消息，告知其他節(jié)點自己成為簇頭，總消息數(shù)為N-K。因此，WSN中總消息平均條數(shù)為：

所以消息復(fù)雜度為O（N）。

由性質(zhì)可知，在WSN簇頭競爭整個階段，PUDCH路由協(xié)議中的消息總數(shù)為N×T/2+（N-K）/2+K，遠(yuǎn)遠(yuǎn)小于總消息數(shù)為（2T+N）的EEUC路由協(xié)議以及總消息數(shù)為（T+1）N+K的DEBUC路由協(xié)議，大大節(jié)省了系統(tǒng)消息能量開銷，能量利用更加高效。

4.2 采用PUDCH路由協(xié)議的WSN節(jié)點能量消耗分析

設(shè)節(jié)點隨機分布M×M的區(qū)域內(nèi)，節(jié)點總數(shù)目為N，有k個簇，則每個簇內(nèi)有N/k個節(jié)點，即普通節(jié)點的個數(shù)為N/k-1，簇頭所消耗能量計算的公式為：

其中，l是每次傳輸數(shù)據(jù)的比特數(shù)，EDA是單位比特數(shù)數(shù)據(jù)融合所消耗能量，dS是簇頭節(jié)點到基站的距離。普通節(jié)點所消耗的能量只是用來向簇頭傳輸感知數(shù)據(jù)。dC是簇內(nèi)節(jié)點到簇頭節(jié)點的距離。

簇內(nèi)總的能量消耗為：

由以上公式可知，簇內(nèi)節(jié)點總能量消耗跟節(jié)點間距離與傳輸數(shù)據(jù)大小有關(guān)，PUDCH算法相較其他算法進(jìn)一步優(yōu)化了節(jié)點與簇頭之間的距離，且優(yōu)化了數(shù)據(jù)傳輸路徑，進(jìn)而理論上大大減小了節(jié)點數(shù)據(jù)采集與數(shù)據(jù)融合的能耗。

4.3 實驗仿真與結(jié)果分析

采用OMNET4.0仿真軟件對本文算法、EEUC協(xié)議、EBUCA協(xié)議進(jìn)行比較仿真模擬。實驗仿真參數(shù)如圖3所示，傳感器節(jié)點隨機分布，簇點融合數(shù)據(jù)的能量忽略不計［13］，簇間轉(zhuǎn)發(fā)策略采用文中提出的最小二叉樹方法。Heinzelman W等前人已經(jīng)對簇頭節(jié)點任務(wù)過重以及能量空洞問題進(jìn)行了詳細(xì)的探討，基于篇幅限制本文將重點研究本文提出的分簇算法與其他分簇算法之間的對比實驗。

圖3 試驗參數(shù)列表

圖4為存活節(jié)點數(shù)隨運行輪數(shù)的變化情況，圖5為節(jié)點剩余能量隨運行輪數(shù)的變化情況。

圖4 網(wǎng)絡(luò)中節(jié)點存活數(shù)目統(tǒng)計

采用3種協(xié)議時的網(wǎng)絡(luò)生命周期對比如圖4所示。3種協(xié)議在500輪左右時都開始有節(jié)點死亡。運行800到1 500輪左右時，相比于其他2個協(xié)議，使用PUDHC協(xié)議傳輸?shù)木W(wǎng)絡(luò)節(jié)點死亡變緩，這是因為隨著時間的推移，PUDCH算法進(jìn)一步優(yōu)化了分簇算法以及簇頭的選擇，平衡了簇頭數(shù)據(jù)傳輸?shù)呢?fù)擔(dān)，進(jìn)而平衡了各簇頭節(jié)點的能量消耗，提高了無線傳感器網(wǎng)絡(luò)的健壯性。

圖5 網(wǎng)絡(luò)中節(jié)點剩余能量對比

采用3種協(xié)議時的網(wǎng)絡(luò)節(jié)點剩余能量對比如圖5所示。PUDCH算法采用了不均勻分簇并且優(yōu)化了簇頭（以及副簇頭節(jié)點）的選擇，同時優(yōu)化了簇間多跳路由，平衡了網(wǎng)絡(luò)中節(jié)點的能量消耗。并且PUDCH協(xié)議輪換簇頭的通信成本以及通信復(fù)雜度都比EEUC協(xié)議以及EBUCA協(xié)議低得多，進(jìn)一步平衡了網(wǎng)絡(luò)中各簇頭節(jié)點的能量消耗。

圖6為3種協(xié)議能量方差隨時間變化的對比結(jié)果，PUDCH由于采取不同的時間競爭機制導(dǎo)致其網(wǎng)絡(luò)節(jié)點能量方差數(shù)值相較其他兩種分簇算法要小一些并且變化幅度不大，這表明PUDCH協(xié)議能夠有效地均衡網(wǎng)絡(luò)節(jié)點能量.從圖5和圖6可以看出，PUDCH協(xié)議的能量均衡性能較好，有效的延長了WSN使用壽命。

圖6 網(wǎng)絡(luò)節(jié)點剩余能量方差對比

5 結(jié)束語

針對現(xiàn)今已經(jīng)提出的的無線傳感器網(wǎng)絡(luò)路由算法以及它們存在的一些不足，本文提出了一種基于時間競爭機制的無線傳感器網(wǎng)絡(luò)非均勻分簇雙簇頭算法。本文算法在簇頭選擇階段考慮網(wǎng)絡(luò)節(jié)點綜合信息通過時間競爭機制選擇簇頭，完善了網(wǎng)絡(luò)中簇頭的選擇，各簇頭的能量消耗更加的合理均衡；在數(shù)據(jù)傳輸階段，通過節(jié)點以及節(jié)點之間的連線構(gòu)造有向圖，進(jìn)而通過加權(quán)的方式構(gòu)造數(shù)據(jù)傳輸路徑最小生成樹，綜合了考慮剩余能量和簇頭到基站距離以及簇的規(guī)模大小，最后節(jié)點所收集融合的數(shù)據(jù)通過多跳的方式進(jìn)行傳輸。仿真實驗結(jié)果表明，本文算法可以有效延長節(jié)點的死亡時間，均衡網(wǎng)絡(luò)節(jié)點的能量消耗，延長了網(wǎng)絡(luò)生命周期。

［1］龍勝春，盧定乾，池凱凱.基于同構(gòu)傳感器網(wǎng)絡(luò)的能量空洞避免策略［J］.傳感技術(shù)學(xué)報，2016，29（1）：103-108.

［2］李建洲，王海濤，陶安.一種能耗均衡的WSN分簇路由協(xié)議［J］.傳感技術(shù)軟件學(xué)報，2013，26（3）：396-401.

［3］Heinzelman W.Energy-Efficient Communication Protocols for Wireless Microsensor Networks［C］//Proceedings of the Hawaii International Conference on Systems Sciences，Hawai.2000：3005-3014.

［4］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機學(xué)報，2007，30（1）：27-36.

［5］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.軟件學(xué)報，2012，23（5）：1222-1232.

［6］盧先順，王瑩瑩，王洪斌，等.無線傳感器網(wǎng)絡(luò)能量均衡的非均勻分簇算法［J］.計算機科學(xué)，2013，40（5）：78-81.

［7］劉鐵流，巫永群.基于能量優(yōu)化的無線傳感器網(wǎng)絡(luò)分簇路由算法研究［J］.傳感技術(shù)學(xué)報，2011，24（5）：764-770.

［8］嚴(yán)英，郭麗，許建真.一種基于LEACH與PEGASIS協(xié)議的分層成鏈優(yōu)化路由算法［J］.傳感技術(shù)學(xué)報，2011，24（9）：1311-1316.

［9］徐丹丹，章勇.一種基于最大連通度的雙簇頭分簇算法［J］.傳感技術(shù)學(xué)報，2008，21（11）：1909-1912.

［10］Dongfeng Xie，Qianwei Zhou，Xing You.A Novel Energy-Efficient Cluster Formation Strategy：From the Perspective of Cluster Members.IEEE Communications Letters，2013，17（17）：2044-2047.

［11］Yihui Li，Gaoxi Xiao，Gurpreet Singh，et al.Algorithms for Finding Best Locations of Cluster Heads for Minimizing Energy Consumption in Wireless Sensor Networks［J］.Wireless Networks，2013，19（7）：1755-1768.

［12］Changsoo Ok，Seokcheon Lee，Prasenjit Mitrea，et al.Distributed Routing in Wireless Sensor Networks Using Energy Welfare Metric［J］.Information Sciences an International Journal，2010，180（9）：1656-1670.

［13］Zhang D G，Li G，Zheng K，et al.An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Network［J］.IEEE Transactions on Mobile Computing，2014，10（1）：766-773.

戴志強（1981-），男，碩士，吉首大學(xué)旅游與管理工程學(xué)院講師，研究方向為無線傳感器網(wǎng)絡(luò)大數(shù)據(jù)，39166427@qq.com；

嚴(yán) 承（1982-），男，碩士，黔南民族師范學(xué)院計算機與信息學(xué)院講師，研究方向為無線傳感器網(wǎng)絡(luò)，數(shù)據(jù)挖掘，信息安全，2915557139@qq.com；

武正江（1991-），男，中南大學(xué)碩士研究生，研究方向為無線傳感器網(wǎng)絡(luò)，zhengjiangwu@csu.edu.cn。

New Uneven Double Cluster Head Clustering Algorithm for WSN—PUDCH Algorithm*

DAI Zhiqiang1，YAN Cheng2*，WU Zhengjiang3
（1.Hunan Application Technology of Ecotourism Key Laboratory，Jishou University，Zhangjiajie Hunan427000，China；2.School of Computer and Information，Qiannan Normal University for Nationalities，Duyun Guizhou558000，China；3.School of Software，Central South University，Changsha410075，China）

Energy utilization efficiency problem has been a bottleneck restricting the wide application of WSN，and the energy capacity of each network node is very important.In view of the WSN"energy hole problem"and due to the cluster head role overload caused by excessive energy consumption and to improve the energy efficiency of WSN proposed non uniform clustering algorithm of dual cluster head—PUDCH a wireless sensor network.The algorithm first considering node comprehensive information such as the distance of the residual energy of node，the node to the base station，according to the comprehensive information of the node through the mechanism of competition in different time to elect cluster heads，the whole network is divided into uneven clustering；in the larger clusters，in order to reduce the burden of light cluster head then select vice cluster head.Finally，the cluster head is then constructed based on the optimal transmission path of the minimum spanning tree.A series of simulations show that the PUDCH routing algorithm has excellent performance in the energy consumption of WSN saving and balancing nodes.

wireless sensor networks；double cluster head；parity；uneven clustering；minimum spanning tree

TP393

A

1004-1699（2016）12-1912-07

??7230

10.3969/j.issn.1004-1699.2016.12.022

項目來源：國家自然科學(xué)基金項目（61572526）；湖南省自然科學(xué)基金項目（13JJ3007）；湖南省哲學(xué)社會科學(xué)基金項目（14YBA318）

2016-05-26修改日期：2016-07-16