分布式能量有效成簇路由算法研究

分布式能量有效成簇路由算法研究

1設(shè)置了設(shè)置一個(gè)專門的wsn分簇作為一種新的獲取和處理形式，無線傳感器網(wǎng)絡(luò)（無線傳感器網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)）已成為國內(nèi)外的研究熱點(diǎn)。WSN通過大量部署在監(jiān)測區(qū)域內(nèi)的傳感器節(jié)點(diǎn),采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對象的信息,通過多跳的無線通信方式,將收集、處理后的信息提供給終端用戶。WSN不需要固定的網(wǎng)絡(luò)支持,具有快速展開、抗毀性強(qiáng)等特點(diǎn),可廣泛應(yīng)用于軍事偵察、環(huán)境監(jiān)測、醫(yī)療監(jiān)護(hù)、農(nóng)業(yè)養(yǎng)殖和其他商業(yè)領(lǐng)域,以及空間探索和災(zāi)難搶險(xiǎn)等特殊領(lǐng)域。在WSN體系結(jié)構(gòu)中,網(wǎng)絡(luò)層的路由技術(shù)對WSN的性能好壞有著重要影響。隨著國內(nèi)外WSN的研究發(fā)展,許多路由協(xié)議被提了出來。由于傳感器節(jié)點(diǎn)本身資源的限制,針對adhoc網(wǎng)絡(luò)的分簇算法不能被直接利用,特別是WSN節(jié)點(diǎn)能量更為有限,因此必須研究新的分簇算法。LEACH(low-energyadaptiveclusteringhierarchy)是WSN中最早提出的分簇路由協(xié)議。它的成簇思想貫穿于其后發(fā)展出的很多分簇路由協(xié)議中,如TEEN(thresholdsensitiveenergyefficientsensornetworkprotocol)、HEED(hybridenergy-efficientdistributedclustering)等。另外,還有一些獨(dú)立開發(fā)的分簇路由協(xié)議,如ACE(algorithmforclusterestablishment)、LSCP(lightweightsensingandcommunicationprotocols)等。2相關(guān)研究傳感器網(wǎng)絡(luò)成簇算法發(fā)展迅速,按照成員節(jié)點(diǎn)到基站的跳數(shù),簇的結(jié)構(gòu)一般分為單跳和多跳網(wǎng)絡(luò)。2.1基于剩余能量的分布式聯(lián)合打造LEACH是最早提出的單跳分簇算法,其基本思想是:通過等概率地隨機(jī)循環(huán)選擇簇頭,將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn),從而達(dá)到降低網(wǎng)絡(luò)能量耗費(fèi)、延長網(wǎng)絡(luò)生命周期的目的。近幾年,提出了許多LEACH的改進(jìn)算法,其中包括EECS、LEACH-B等,在不同方面改進(jìn)了LEACH算法的性能。在EECS中,節(jié)點(diǎn)在選擇簇頭時(shí)不是簡單地選擇距離自身最近的簇頭,而是考慮了候選簇頭到基站距離的遠(yuǎn)近,構(gòu)造出相應(yīng)的簇,均衡簇頭的負(fù)載。但該協(xié)議只能平衡簇頭地區(qū)的能量分布,缺乏對全網(wǎng)消耗能量的平衡。文獻(xiàn)提出一種根據(jù)節(jié)點(diǎn)剩余能量選舉簇頭的算法,缺點(diǎn)在于每個(gè)節(jié)點(diǎn)需要知道當(dāng)前網(wǎng)絡(luò)的總能量,而難以分布式實(shí)現(xiàn)。SEP則是針對二級(jí)異構(gòu)網(wǎng)絡(luò)設(shè)計(jì)的,即網(wǎng)絡(luò)中只有2種不同初始能量的節(jié)點(diǎn)。DEEC算法針對一般性的多級(jí)異構(gòu)網(wǎng)絡(luò)設(shè)計(jì),不適用于同構(gòu)傳感器網(wǎng)絡(luò)。DCHS引入了能量閾值,延長了網(wǎng)絡(luò)的生存周期,但該算法未考慮平衡全網(wǎng)能量。HEED也是一種完全分布式的成簇算法,它隨機(jī)選擇簇頭節(jié)點(diǎn),選舉概率與該節(jié)點(diǎn)的剩余能量直接相關(guān)。HEED算法首先根據(jù)節(jié)點(diǎn)的剩余能量來概率性地選取一些候選簇頭,然后以簇內(nèi)部通信代價(jià)的高低來競爭產(chǎn)生最終簇頭。簇生成算法需要在簇半徑內(nèi)進(jìn)行多次消息迭代,由此帶來的通信開銷比較顯著。上述的這些協(xié)議均通過周期性地重新分簇,讓節(jié)點(diǎn)輪流擔(dān)任簇頭,達(dá)到節(jié)點(diǎn)均衡地消耗能量的目的。2.2apteen協(xié)議多跳網(wǎng)絡(luò)的簡介PEGASIS則將節(jié)點(diǎn)組織成鏈的形式,鏈的形成由每一個(gè)節(jié)點(diǎn)或者基站計(jì)算得到,因此需要知道網(wǎng)絡(luò)拓?fù)涞娜种R(shí)。文獻(xiàn)研究了多跳簇結(jié)構(gòu)網(wǎng)絡(luò),并使用一種隨機(jī)成簇方案來組織傳感器節(jié)點(diǎn)。TEEN協(xié)議適用于實(shí)時(shí)性要求較高的應(yīng)用場合,用戶可以及時(shí)獲取感興趣的信息,它設(shè)置了硬、軟2個(gè)閾值,以減少發(fā)送數(shù)據(jù)的次數(shù)。通過調(diào)節(jié)2個(gè)閾值的大小,可以在精度要求和系統(tǒng)能耗之間取得合理的平衡。但TEEN存在3個(gè)缺陷:一是如果閾值不能達(dá)到,節(jié)點(diǎn)不會(huì)傳送任何數(shù)據(jù);二是數(shù)據(jù)一旦符合閾值要求,節(jié)點(diǎn)立即傳送,容易造成信號(hào)干擾,如果采用TDMA,則會(huì)造成數(shù)據(jù)延遲;三是該協(xié)議的閾值選擇是非常困難的。APTEEN協(xié)議的功耗相對降低,增加了網(wǎng)絡(luò)的生命周期。對于實(shí)時(shí)性要求不高的查詢,時(shí)延可以大一些,這可以使生命周期增加近一倍,但APTEEN協(xié)議的實(shí)現(xiàn)難度比較大,給實(shí)際應(yīng)用帶來了困難。ECMR(energy-consciousmessagerouting)是多跳的路由傳輸協(xié)議。ECMR假設(shè)簇頭預(yù)先部署,能量不受限,能與成員節(jié)點(diǎn)直接通信,而成員節(jié)點(diǎn)需多跳路由才能到簇頭。ECMR由簇頭采用Dijkstra算法求解。其中,節(jié)點(diǎn)i和j之間鏈路的權(quán)值定義不僅計(jì)算了它們之間的通信耗費(fèi),也考慮了節(jié)點(diǎn)能量、數(shù)據(jù)延遲和鏈路負(fù)載等因素。ECMR在運(yùn)行過程中具有良好的節(jié)能性能、較高的吞吐量和較低的通信延遲。但是,該協(xié)議擴(kuò)展性較差,需要部署新的簇頭來擴(kuò)展網(wǎng)絡(luò),而且對簇頭依賴性大,不支持節(jié)點(diǎn)移動(dòng)。在文獻(xiàn)中,李成法等人提出了基于競爭的多跳非均勻分簇算法,仿真結(jié)果顯示了較好的效果,但該算法中的參數(shù)選取主要憑經(jīng)驗(yàn)給出,理論分析不夠,需要進(jìn)行深入研究。另外,基于競爭產(chǎn)生簇頭仍然存在能量浪費(fèi)問題,因?yàn)楹蜻x簇頭數(shù)量較多,需要競爭的次數(shù)較多,因此需要繼續(xù)深入研究。M-LEACH針對多跳網(wǎng)絡(luò),算法比較復(fù)雜。文獻(xiàn)引入了能量和距離閾值以均衡全網(wǎng)能量消耗,但算法未考慮全網(wǎng)的能量分布情況。對于單跳成簇算法,操作簡單,時(shí)延小,適合于實(shí)時(shí)性較強(qiáng)的網(wǎng)絡(luò),缺點(diǎn)是向基站傳輸數(shù)據(jù)時(shí)需要消耗更多的能量。多跳成簇算法一般較復(fù)雜,實(shí)現(xiàn)難度較大,時(shí)延較大。本文主要研究單跳成簇算法,試圖尋找一種較為合理的思路延長網(wǎng)絡(luò)的生命周期。然而,從均衡節(jié)點(diǎn)的能量消耗以延長網(wǎng)絡(luò)的存活時(shí)間這個(gè)目標(biāo)看,先前的研究主要集中于均衡簇成員節(jié)點(diǎn)之間的能量消耗,沒有考慮到簇頭間的能量消耗均衡問題。本文提出的DEEUC算法是為同構(gòu)單跳網(wǎng)絡(luò)而設(shè)計(jì)的。它借鑒了LEACH的簇頭輪轉(zhuǎn)思想,同時(shí)讓簇頭節(jié)點(diǎn)的選舉與節(jié)點(diǎn)剩余能量直接相關(guān),避免了同構(gòu)成簇算法所遇到的問題。DEEUC還保留了分布式算法的優(yōu)點(diǎn),不需要中心機(jī)構(gòu)在網(wǎng)絡(luò)操作過程中提供全局信息。3基于平均能量的引領(lǐng)性選舉算法本文引入平均能量閾值的核心思想是根據(jù)節(jié)點(diǎn)的剩余能量來合理選擇簇頭,剩余能量高的優(yōu)先選擇為簇頭,最終能有效地平衡全網(wǎng)能量,基于此,提出了基于全網(wǎng)平均能量的簇頭選舉算法,類似于LEACH-C,但克服了必須向基站傳送剩余能量的問題,引入估計(jì)方法,避免了LEACH-C的能量消耗問題。簇頭選好后,對于加入簇的節(jié)點(diǎn)來說,加入那個(gè)簇是平衡全網(wǎng)能量的關(guān)鍵因素,本文提出了基于距離和能量因子的能量消耗率函數(shù),有效地延長了網(wǎng)絡(luò)的生命周期。3.1有節(jié)點(diǎn)的數(shù)據(jù)融合模型研究的網(wǎng)絡(luò)分布在一正方形區(qū)域內(nèi),由N個(gè)隨機(jī)分布的傳感器節(jié)點(diǎn)組成,其應(yīng)用場景為周期性的數(shù)據(jù)收集。用in表示第i個(gè)節(jié)點(diǎn),相應(yīng)的節(jié)點(diǎn)集合為Node={n1,n2,…,nN},|Node|=N。假設(shè)如下。1)基站位于一個(gè)方形觀測區(qū)域的外側(cè),傳感器節(jié)點(diǎn)和基站BS在部署后均不再發(fā)生位置移動(dòng)。2)所有節(jié)點(diǎn)都是同構(gòu)的且能量有限,具備數(shù)據(jù)融合的功能。每個(gè)節(jié)點(diǎn)都有唯一的標(biāo)識(shí)(ID)。3)所有節(jié)點(diǎn)都能夠一跳到達(dá)基站(BS)。4)每個(gè)節(jié)點(diǎn)沒有位置信息。5)根據(jù)接收者的距離遠(yuǎn)近,節(jié)點(diǎn)可以自由調(diào)整其發(fā)射功率以節(jié)約能量消耗。6)鏈路是對稱的,若已知對方發(fā)射功率,節(jié)點(diǎn)根據(jù)接收信號(hào)強(qiáng)度RSSI計(jì)算出發(fā)送者到自己的距離。采用與文獻(xiàn)相同的無線通信能量消耗模型,如圖1所示。節(jié)點(diǎn)發(fā)射Lbit的數(shù)據(jù)到距離為d的位置,消耗的能量由發(fā)射電路損耗和功率放大損耗2部分組成,即其中,Eelec表示發(fā)射電路損耗的能量。若傳輸距離小于閾值do,功率放大損耗采用自由空間模型;當(dāng)傳輸距離大于等于閾值do時(shí),采用多路徑衰減模型。εfs、εmp分別為2種模型中功率放大所需的能量。節(jié)點(diǎn)接收Lbit的數(shù)據(jù)消耗的能量為數(shù)據(jù)融合也消耗一定的能量,用EDF表示融合單位比特?cái)?shù)據(jù)消耗的能量。假設(shè)鄰近節(jié)點(diǎn)采集的數(shù)據(jù)具有較高的冗余度,簇頭可以將其成員的數(shù)據(jù)融合成一個(gè)長度固定的數(shù)據(jù)包,然后發(fā)送給基站(BS)。3.2成簇算法deeuc在網(wǎng)絡(luò)建立階段,基站(BS)需要用一個(gè)給定的發(fā)送功率向網(wǎng)絡(luò)內(nèi)廣播一個(gè)信號(hào)。每個(gè)傳感器節(jié)點(diǎn)在接收到此信號(hào)后,根據(jù)接收信號(hào)的強(qiáng)度計(jì)算它到基站的近似距離。獲得這個(gè)距離不僅有助于傳感器節(jié)點(diǎn)向基站傳輸數(shù)據(jù)時(shí)選擇合適的發(fā)送功率以節(jié)約能量消耗,而且它還是算法構(gòu)造簇的必要信息之一。圖2給出本文提出的基于平均能量的成簇路由算法的示意圖,其中不規(guī)則的多邊形圍成的小圖形表示簇頭節(jié)點(diǎn)的覆蓋范圍,帶箭頭的直線表示簇頭向基站單跳數(shù)據(jù)傳輸。從圖2可以看出,成簇算法是使遠(yuǎn)離基站的節(jié)點(diǎn)盡量少成為簇頭以減少能量消耗,在每一個(gè)簇頭覆蓋范圍內(nèi)盡量選取能量高的作為簇頭。DEEUC每輪循環(huán)的基本過程是:在簇建立階段,基站(BS)每個(gè)節(jié)點(diǎn)選取一個(gè)介于0和1之間的隨機(jī)數(shù),如果這個(gè)數(shù)小于某個(gè)閾值,該節(jié)點(diǎn)成為候選簇頭。然后,通過競爭算法確定最終的簇頭,簇頭向周圍節(jié)點(diǎn)廣播自己成為簇頭的消息。每個(gè)節(jié)點(diǎn)根據(jù)提出的能量消耗率函數(shù)來確定加入哪個(gè)簇,并回復(fù)該簇簇頭。在數(shù)據(jù)傳輸階段,簇內(nèi)的所有節(jié)點(diǎn)按照TDMA(時(shí)分復(fù)用)時(shí)隙向簇頭發(fā)送數(shù)據(jù)。簇頭將數(shù)據(jù)融合之后把結(jié)果發(fā)給基站。在持續(xù)工作一段時(shí)間之后,網(wǎng)絡(luò)重新進(jìn)入啟動(dòng)階段,進(jìn)行下一輪的簇頭選取并重新建立簇。3.3節(jié)點(diǎn)選取引領(lǐng)性算法候選簇頭的產(chǎn)生是簇形成的基礎(chǔ),產(chǎn)生候選簇頭時(shí),每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0~1之間的隨機(jī)數(shù),如果節(jié)點(diǎn)n產(chǎn)生的隨機(jī)數(shù)小于閾值T(n),則該節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播它是候選簇頭的消息。由于LEACH算法沒有考慮剩余能量和距離因素,因此改進(jìn)了LEACH的T(n)計(jì)算公式,將平均能量因素考慮進(jìn)來,使能量消耗比例較低的節(jié)點(diǎn)優(yōu)先當(dāng)選為候選簇頭。在候選簇頭選舉算法中引入的關(guān)鍵參數(shù)如下:其中,E(i)residual表示第i個(gè)節(jié)點(diǎn)的剩余能量,E(r)表示第r輪網(wǎng)絡(luò)平均剩余能量。Energy因子主要用來平衡全網(wǎng)剩余能量。定義從第一輪選擇簇頭開始到第一個(gè)節(jié)點(diǎn)死亡(能量消耗盡)的輪數(shù),稱為網(wǎng)絡(luò)生命周期。通過以上分析發(fā)現(xiàn),引入Energy閾值因子后,能夠有效地降低全網(wǎng)的能量消耗,延長網(wǎng)絡(luò)的生命周期。式(4)給出了新構(gòu)造的閾值計(jì)算公式T(n)new。其中,p是簇頭占所有節(jié)點(diǎn)的百分比,即節(jié)點(diǎn)當(dāng)選簇頭的概率;r是目前循環(huán)進(jìn)行的輪數(shù);G是最近1/p輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合。從T(n)new可以看出,當(dāng)選過候選簇頭的節(jié)點(diǎn)在接下來的1/p輪循環(huán)中將不能成為簇頭,剩余節(jié)點(diǎn)當(dāng)選簇頭的閾值T(n)new增大,節(jié)點(diǎn)產(chǎn)生小于T(n)new的隨機(jī)數(shù)的概率隨之增大,所以節(jié)點(diǎn)當(dāng)選候選簇頭的概率增大。p值決定了每輪產(chǎn)生的候選簇頭數(shù)量,在應(yīng)用中,最佳p值的確定十分困難,這與網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)密度有關(guān)。3.4傳感器網(wǎng)絡(luò)平均能量平均能量的計(jì)算需要全網(wǎng)節(jié)點(diǎn)的剩余能量信息,這是非常困難的,特別是對于節(jié)點(diǎn)密集型傳感器網(wǎng)絡(luò)。一方面要有相應(yīng)的通信協(xié)議支持該數(shù)據(jù)的傳送,另一方面即使有如此協(xié)議進(jìn)行通信,對于基站(BS)來說,收集如此密集數(shù)據(jù)的開銷也是十分驚人的,因此必須考慮其他途徑獲得平均能量信息。引入估計(jì)方法,對平均能量進(jìn)行相應(yīng)估計(jì)。假設(shè)每輪傳感器網(wǎng)絡(luò)消耗相同的能量,這種假設(shè)是合理的,因?yàn)槊枯喌拇仡^數(shù)量相近,通信開銷相近。假設(shè)傳感器節(jié)點(diǎn)均勻分布在M×M的正方形中,節(jié)點(diǎn)數(shù)設(shè)為N個(gè),初始能量相同。每輪中消耗的能量包括2部分:簇頭消耗的能量ECH和非簇頭消耗的能量Enon-CH,設(shè)傳感器網(wǎng)絡(luò)每輪消耗的能量為Eround,則有對于傳感器簇頭而言,在一輪中消耗的能量ECH為對于傳感器非簇頭節(jié)點(diǎn)而言,在一輪中消耗的能量Enon-CH為其中,k為簇頭的數(shù)量,dtoCH為節(jié)點(diǎn)到簇頭的平均距離,dtoCH為簇頭到基站的平均距離,如果這3個(gè)參數(shù)可以估計(jì),那么每輪的能量Eround就可以估計(jì)。在文獻(xiàn)中,作者已經(jīng)估計(jì)了dtoCH和參數(shù)k分別為在文獻(xiàn)中,作者估計(jì)了參數(shù)dtoCH為把式(6)、式(7)、式(8)、式(9)、式(10)代入式(5),從而可以粗略估計(jì)出全網(wǎng)一輪消耗的能量,進(jìn)而估計(jì)出全網(wǎng)剩余的平均能量為其中,Etotal為全網(wǎng)初始能量,r為輪數(shù)。3.5簇頭選擇過程候選簇頭產(chǎn)生后,引入競爭算法獲得最終的簇頭。首先使每個(gè)候選簇頭以R(R為競爭半徑)為半徑廣播競爭消息,如果si、sj為候選簇頭,設(shè)以sj為核心,R為半徑的特定面積內(nèi)的候選簇頭組成集合sj.ACH,在該面積內(nèi)選擇剩余能量最多的候選簇頭作為最終簇頭(如果最大能量有多個(gè)相同,選擇第一個(gè)候選簇頭作為最終簇頭),然后將此面積內(nèi)的其他候選簇頭刪除(即設(shè)置成簇成員節(jié)點(diǎn)),最后最終簇頭以dn_CH(簇成員節(jié)點(diǎn)到達(dá)特定簇頭的最大距離)為半徑廣播競選成功消息,完成簇頭選擇過程。在競爭過程中,競爭半徑的選取是非常重要的,下面作簡單說明。引入非均勻簇機(jī)制,目標(biāo)是讓靠近基站(BS)的簇的成員較少,使其簇頭能夠預(yù)留部分能量供簇頭與基站間通信使用。遠(yuǎn)離基站的簇頭的成員較多,這樣可以減少簇頭與基站之間的通信次數(shù),降低能量消耗,因?yàn)檫h(yuǎn)距離通信消耗更多的能量。因此,靠近基站(BS)簇頭的競爭半徑應(yīng)該較小。亦即,隨著候選簇頭到基站(BS)距離的減小,其競爭半徑應(yīng)該隨之減小。記候選簇頭競爭半徑的最大取值為Rmax,最小取值為cR。算法需要控制競爭半徑的取值范圍,使得距離基站最遠(yuǎn)節(jié)點(diǎn)的競爭半徑為(1+c)cR,其中c是用于控制取值范圍的參數(shù),取值范圍為,c越大競爭半徑越大,簇頭消耗能量越大,根據(jù)選取的場景,c取值為1。候選簇頭si確定其競爭半徑si.R的計(jì)算公式如式(12)所示。其中,dmax和dmin分別代表網(wǎng)絡(luò)中的節(jié)點(diǎn)到基站(BS)距離的最大值和最小值,d(si,BS)代表節(jié)點(diǎn)si到基站(BS)的距離。競爭半徑與節(jié)點(diǎn)到基站的距離呈線性遞增關(guān)系。3.6獲得能量的需求簇頭選好后,節(jié)點(diǎn)如何加入簇頭是非常關(guān)鍵的,這直接關(guān)系到平衡當(dāng)前簇頭地區(qū)的能量消耗。例如在圖2中節(jié)點(diǎn)i是加入簇頭5還是6,必須由能量消耗率函數(shù)決定。直觀上該節(jié)點(diǎn)加入簇頭5,因?yàn)榫嚯x簇頭5最近,但這不利于平衡全網(wǎng)能量消費(fèi)。定義的能量消耗率函數(shù)f(i,j)為其中,1≤i≤CM,CM為加入第j個(gè)簇頭的簇成員數(shù)量,1≤j≤CH,CH為簇頭數(shù)量。節(jié)點(diǎn)i加入簇頭CHj的條件就是使能量消耗率函數(shù)f(i,j)最小。其中iE表示節(jié)點(diǎn)i的當(dāng)前能量,ECHj表示簇頭j的當(dāng)前能量。其中其中,d(CHj,BS)表示第j個(gè)簇頭到基站(BS)的距離,。d(ni,CHj)為節(jié)點(diǎn)i到簇頭j的距離,。提出的能量消耗率函數(shù)f既引入了距離因素,又引入了能量因素,直觀上更能有效平衡當(dāng)前簇頭區(qū)的能量消耗。簡單說明如下。選擇簇成員的標(biāo)準(zhǔn)是使能量消耗率函數(shù)f(i,j)最小,則有為分析方便將常數(shù)合并,則有由于每輪中簇成員節(jié)點(diǎn)都要與簇頭通信,簇頭都要與基站(BS)通信,因此有等價(jià)變換為下式:上式中εfsd2(ni,CHj)是簇成員消耗能量的關(guān)鍵部分,εmpd4(CHj,BS)是簇頭消耗能量的關(guān)鍵部分。直觀上,只要能量消耗率函數(shù)最小,簇成員和簇頭消耗能量均最低,繼而全網(wǎng)消耗能量最低,因此能有效延長網(wǎng)絡(luò)的生命周期。反之,如果簇成員和簇頭消耗能量均最低,那么能量消耗率函數(shù)f(i,j)必定最小。3.7deeuc算法DEEUC是一個(gè)分布式動(dòng)態(tài)算法,以節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)到簇頭的距離為主要參數(shù)來選取簇頭。在成簇算法中,簇頭是非常重要的,因?yàn)榇仡^在每輪中完成最多的任務(wù),消耗最多的能量。簇頭選舉算法包括2個(gè)階段:候選簇頭產(chǎn)生和最終簇頭產(chǎn)生階段。在選擇候選簇頭時(shí),基站(BS)向每一個(gè)節(jié)點(diǎn)廣播平均能量消息,在選擇候選簇頭過程中用平均能量參數(shù)來約束候選簇頭的選擇,大于平均能量的節(jié)點(diǎn)優(yōu)先選擇為候選簇頭,由于平均能量是全網(wǎng)的信息,因此可以有效地描述全網(wǎng)的能量狀態(tài)。當(dāng)候選簇頭選好后,算法便進(jìn)入最終簇頭產(chǎn)生階段。引入基于競爭機(jī)制的簇頭選舉算法來獲得最終的簇頭,選好的簇頭向它周圍的節(jié)點(diǎn)廣播加入消息,周圍節(jié)點(diǎn)可以根據(jù)所提出的能量消耗率函數(shù)選擇加入的簇頭,隨后節(jié)點(diǎn)向選擇的簇頭發(fā)送應(yīng)答消息,確認(rèn)自己加入該簇,完成簇的建立,最后將完全融合后的數(shù)據(jù)直接發(fā)送給基站,完成一輪的數(shù)據(jù)傳送工作,等待進(jìn)入下一輪。但是對于簇成員的能量消耗也是不能忽略的,因?yàn)榇爻蓡T也有可能成為簇頭。在EECS算法中,選擇簇頭時(shí),主要在候選簇頭里選擇真正的簇頭,但是對于候選簇頭而言并不一定是所有節(jié)點(diǎn)中剩余能量較高的,對于此算法而言由于引入了平均能量閾值,使得選取的候選簇頭是剩余能量最高的,保證了候選簇頭的高能量特性,因此算法具有很好的結(jié)果。算法1給出了整個(gè)算法的偽碼,sj.ACH表示以候選簇頭sj為中心,以sj.R為半徑的所有候選簇頭集合。算法1DEEUC算法偽碼在此算法中,每個(gè)節(jié)點(diǎn)均以同樣的功率發(fā)送廣播消息,為了節(jié)約能量,這個(gè)廣播半徑為Rmax(Rmax為最大簇頭半徑)即可。算法首先根據(jù)閾值大小和節(jié)點(diǎn)的剩余能量狀態(tài),產(chǎn)生候選簇頭;然后通過競爭算法獲得最終簇頭;最后每個(gè)簇頭廣播HEAD_MSG消息,消息的內(nèi)容為節(jié)點(diǎn)的ID、節(jié)點(diǎn)到達(dá)簇頭的最大距離dn_CH(為節(jié)約能量使dn_CH=Rmax即可)。節(jié)點(diǎn)根據(jù)收到的廣播消息計(jì)算能量消耗率函數(shù)f(i,j),選擇f(i,j)最小的簇頭加入,最后發(fā)送加入消息JOIN_ClusterHead_MSG,通知該簇頭。簇頭選擇完成后,節(jié)點(diǎn)根據(jù)能量消耗率函數(shù)選擇加入的簇頭,進(jìn)入簇內(nèi)數(shù)據(jù)傳輸階段,簇頭構(gòu)建TDMA調(diào)度,然后簇成員向簇頭傳輸數(shù)據(jù)。性質(zhì)在所選網(wǎng)絡(luò)中,DEEUC算法的消息復(fù)雜度為O(N)。證明首先,基站(BS)廣播一條平均能量AE_MSG消息給每個(gè)節(jié)點(diǎn)。其次,有N×Threshold個(gè)節(jié)點(diǎn)成為候選簇頭,共廣播N×Threshold條COMPETE_HEAD_MSG消息,然后每個(gè)候選簇頭廣播一條FINAL_HEAD_MSG消息宣布其競選成功,或者廣播一條QUIT_MSG消息宣布其退出競選。假設(shè)共選出k個(gè)簇頭,每個(gè)簇頭廣播一條HEAD_MSG消息,而N-k個(gè)非簇頭節(jié)點(diǎn)廣播一條JOIN_ClusterHead_MSG消息。因此消息開銷為所以消息復(fù)雜度為O(N)。性質(zhì)說明DEEUC算法的消息開銷比較小,進(jìn)而算法具有較好的能量效率。HEED的簇生成算法需要在簇半徑內(nèi)進(jìn)行多次消息迭代,由此帶來的通信開銷比較顯著,一般其消息交換次數(shù)的上界為Niter×N,Niter是消息迭代的次數(shù)。因?yàn)镈EEUC算法避免了消息迭代,因此消息開銷低于HEED。對于EECS算法來說,消息復(fù)雜度也為O(N),與此算法相同,但由于EECS算法在選擇簇頭時(shí)未考慮簇頭到基站(BS)的距離,因此未能有效地平衡簇頭能量的消耗。4deeuc算法的性能比較為了說明算法效果,使用MATLAB對算法進(jìn)行了仿真測試,選擇的仿真場景參數(shù)如表1所示。算法中能量消耗率函數(shù)參數(shù)w的選擇是十分重要的,因?yàn)閣是平衡簇頭和簇成員之間的權(quán)值,從0.1到1范圍內(nèi)進(jìn)行實(shí)驗(yàn),結(jié)果如圖3所示,可以看出,w=0.5或w=0.6效果最好,在文中選擇w=0.6。比較LEACH-C、EECS和DEEUC3種算法。圖4是3種算法生命周期的比較,從圖中可以看出,DEEUC生命周期最長,EECS次之,LEACH-C最差,其中DEEUC比LEACH-C的生命周期至少長45%以上,比EECS的生命周期延長達(dá)到約30%。從死亡節(jié)點(diǎn)的數(shù)量來看,DEEUC在1200輪時(shí)死亡節(jié)點(diǎn)數(shù)量不到20個(gè)節(jié)點(diǎn),約占總節(jié)點(diǎn)數(shù)的2%,EECS死亡約170個(gè)節(jié)點(diǎn),占總節(jié)點(diǎn)數(shù)的17%,LEACH-C最多死亡約390個(gè)節(jié)點(diǎn),至少占39%,死亡節(jié)點(diǎn)數(shù)可以反映出網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡情況,死亡越少說明網(wǎng)絡(luò)的能量使用效率越高。DEEUC不僅顯著地延長了網(wǎng)絡(luò)的生命周期,而且死亡節(jié)點(diǎn)數(shù)也遠(yuǎn)小于其他算法,這說明DEEUC很好地均衡了網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗。EECS已經(jīng)引入了花費(fèi)函數(shù),但其性能略差于DEEUC,原因可能主要有3點(diǎn):一是候選簇頭的選取未充分考慮全網(wǎng)的能量利用情況;二是花費(fèi)函數(shù)中僅注意到了距離因素,未考慮節(jié)點(diǎn)和簇頭的剩余能量因素;三是簇頭選舉時(shí)未考慮候選簇頭到基站(BS)的距離因素。LEACH-C在選取簇頭時(shí)雖然考慮了節(jié)點(diǎn)的剩余能量,但由于其簇頭數(shù)量波動(dòng)較大,因此傳播消息帶來的能量開銷最大,導(dǎo)致其性能最差。圖5是簇頭數(shù)量的比較,從圖中可以看出,DEEUC和EECS算法產(chǎn)生的簇頭數(shù)量穩(wěn)定,LEACH-C簇頭數(shù)量的波動(dòng)范圍最大,這是因?yàn)長EACH-C單純性地采用隨機(jī)數(shù)與閾值的機(jī)制產(chǎn)生簇頭,因此簇頭的數(shù)量變化比較明顯。DEEUC和EECS的簇頭數(shù)量比較集中,這是因?yàn)?種算法均采用了候選簇頭在局部區(qū)域進(jìn)行競爭的方法,有效地控制了算法所生成的簇頭的數(shù)量。但是,DEEUC算法產(chǎn)生的簇頭數(shù)量更集中于簇頭數(shù)量的期望值,主要原因是提出的能量消耗率函數(shù)能更有效地刻劃網(wǎng)絡(luò)性能,使簇頭分布和數(shù)量較為準(zhǔn)確地描述了網(wǎng)絡(luò)特性,因此簇頭分布和數(shù)量能穩(wěn)定更長的時(shí)間。圖6是節(jié)點(diǎn)到簇頭的信息量比較,從圖中可以看出,DEEUC和EECS在第一個(gè)節(jié)點(diǎn)死亡之前的信息量是非常接近的,但是由于EECS生命周期小于DEEUC,當(dāng)存在死亡節(jié)點(diǎn)時(shí),DEEUC的信息量略大于EECS,在約850輪以后,信息量明顯大于EECS,原因是EECS死亡的節(jié)點(diǎn)數(shù)增加很快,導(dǎo)致節(jié)點(diǎn)到簇頭的信息量