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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 相關(guān)模型

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

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

2.2 能量模型

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

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

節(jié)點(diǎn)接收l(shuí)bit數(shù)據(jù)所消耗的能量計(jì)算公式為

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

3 PUDCH算法設(shè)計(jì)

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

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

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

3.1 簇頭選舉

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

圖2 簇頭競(jìng)爭(zhēng)示意圖

競(jìng)選規(guī)則如下：

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

節(jié)點(diǎn)競(jìng)爭(zhēng)半徑為：

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

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

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

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

規(guī)則5本節(jié)點(diǎn)接收到DS發(fā)出的簇頭選擇消息后發(fā)出簇頭競(jìng)爭(zhēng)消息的時(shí)間。

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

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

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

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

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

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

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

經(jīng)過(guò)網(wǎng)絡(luò)分簇以及選取簇頭以后，節(jié)點(diǎn)采集的數(shù)據(jù)通過(guò)多跳最小生成樹(shù)的路由方式向基站進(jìn)行傳輸。先將網(wǎng)絡(luò)中的簇抽象為一個(gè)點(diǎn)，連接相鄰的點(diǎn)，這樣就構(gòu)造成了一個(gè)帶權(quán)值的有向連通圖G=（V，E），V代表簇頭節(jié)點(diǎn)與基站的集合，E代表簇頭連線間的權(quán)值。權(quán)值計(jì)算公式如式（8）所示，綜合考慮簇頭間距離、簇頭剩余能量以及簇的規(guī)模，計(jì)算出的權(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)值的計(jì)算綜合考慮了簇頭間距離、簇頭剩余能量以及簇的規(guī)模，計(jì)算出的權(quán)值更加的合理。當(dāng)一個(gè)簇頭剩余能量低、簇頭間距離遠(yuǎn)并且簇的規(guī)模越大時(shí)，它的wij的取值就越大，那么該簇頭當(dāng)選負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)的概率就會(huì)降低，這樣就會(huì)使整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗更加均衡。

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

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

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

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

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

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

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

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

4 算法分析與仿真

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

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

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

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

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

由性質(zhì)可知，在WSN簇頭競(jìng)爭(zhēng)整個(gè)階段，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)消息能量開(kāi)銷(xiāo)，能量利用更加高效。

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

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

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

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

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

4.3 實(shí)驗(yàn)仿真與結(jié)果分析

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

［2］李建洲，王海濤，陶安.一種能耗均衡的WSN分簇路由協(xié)議［J］.傳感技術(shù)軟件學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（1）：27-36.

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

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

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

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

［9］徐丹丹，章勇.一種基于最大連通度的雙簇頭分簇算法［J］.傳感技術(shù)學(xué)報(bào)，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.

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

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

武正江（1991-），男，中南大學(xué)碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(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

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（61572526）；湖南省自然科學(xué)基金項(xiàng)目（13JJ3007）；湖南省哲學(xué)社會(huì)科學(xué)基金項(xiàng)目（14YBA318）

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