基于EEUC的改進(jìn)研究

章康馳

摘要： 基于對(duì)無線傳感器網(wǎng)絡(luò)典型層次型路由協(xié)議LEACH協(xié)議與高效的非均勻分簇協(xié)議EEUC協(xié)議的研究，針對(duì)EEUC算法中簇頭選舉機(jī)制沒有考慮節(jié)點(diǎn)的剩余能量因素以及簇頭競(jìng)爭(zhēng)半徑只考慮節(jié)點(diǎn)與匯聚節(jié)點(diǎn)距離的問題，提出改進(jìn)的基于最小生成樹的層次型節(jié)能路由算法，首先優(yōu)化候選簇頭的競(jìng)爭(zhēng)半徑，然后在節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)碾A段，采用Kruskal算法構(gòu)建最小生成樹路由，得到最佳的數(shù)據(jù)傳輸方式，保證穩(wěn)定性傳輸數(shù)據(jù)的同時(shí)選擇能耗較低的鏈路。通過實(shí)驗(yàn)仿真的結(jié)果可以得出本算法能夠有效的提升網(wǎng)絡(luò)的性能并延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，緩解無線傳感網(wǎng)中“熱節(jié)點(diǎn)”問題。

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；剩余能量；最小生成樹；存活時(shí)間

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）04-0032-03

無線傳感器網(wǎng)絡(luò)是一種集信息采集、數(shù)據(jù)處理與傳輸功能于一體的網(wǎng)絡(luò)信息系統(tǒng)。涵蓋微電子系統(tǒng)、網(wǎng)絡(luò)通信與嵌入式計(jì)算等多方面技術(shù)，是實(shí)現(xiàn)物聯(lián)網(wǎng)的重要基礎(chǔ)，也是當(dāng)下國(guó)際上備受關(guān)注的、多學(xué)科交叉的一個(gè)熱點(diǎn)研究方向。傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)往往體積小，自身攜帶的能量有限，所以在設(shè)計(jì)路由協(xié)議時(shí)，降低節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間是當(dāng)前無線傳感器網(wǎng)絡(luò)的主要研究方向之一。

無線傳感器網(wǎng)絡(luò)的路由協(xié)議根據(jù)網(wǎng)絡(luò)的邏輯結(jié)構(gòu)可以分為平面型路由協(xié)議和層次型路由協(xié)議。所有的平面型路由協(xié)議里全網(wǎng)中所有節(jié)點(diǎn)地位相等，都需要儲(chǔ)存其他節(jié)點(diǎn)的路由信息，需要維護(hù)龐大的路由表，導(dǎo)致網(wǎng)絡(luò)可擴(kuò)展性較差，控制開銷隨網(wǎng)絡(luò)規(guī)模指數(shù)增長(zhǎng)，出現(xiàn)節(jié)點(diǎn)處理能力弱、網(wǎng)絡(luò)經(jīng)常出現(xiàn)中斷等狀況，所以平面型路由只適用于小型網(wǎng)絡(luò)。而層次型路由協(xié)議通過分簇的方式對(duì)節(jié)點(diǎn)進(jìn)行分層處理，在一定程度上解決了這些問題。本文對(duì)層次型路由協(xié)議中兩種典型的路由協(xié)議：LEACH協(xié)議與EEUC協(xié)議進(jìn)行分析，針對(duì)其不足，基于EEUC協(xié)議提出改進(jìn)方案。

1 LEACH協(xié)議

LEACH協(xié)議[1]是首個(gè)對(duì)無線傳感器網(wǎng)絡(luò)提出分簇的路由協(xié)議。它設(shè)計(jì)的主要目的是盡量均衡全網(wǎng)節(jié)點(diǎn)的能耗，從宏觀上節(jié)省能量，延長(zhǎng)網(wǎng)絡(luò)生命周期。LEACH協(xié)議主要實(shí)現(xiàn)方式是以周期循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn)，而節(jié)點(diǎn)在擔(dān)任簇頭的時(shí)間里負(fù)責(zé)傳遞簇內(nèi)的數(shù)據(jù)給匯聚節(jié)點(diǎn)，這樣從整體上將數(shù)據(jù)傳輸導(dǎo)致的能量消耗平均分配給每個(gè)節(jié)點(diǎn)。LEACH協(xié)議在啟發(fā)性地提出了“輪”的思想，每一輪為一個(gè)周期，每個(gè)周期可以分成兩個(gè)階段：簇的建立階段和傳輸數(shù)據(jù)階段。在簇的建立階段，依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點(diǎn)總數(shù)和每個(gè)節(jié)點(diǎn)已成為簇頭節(jié)點(diǎn)的次數(shù)來決定，再依據(jù)隨機(jī)數(shù)選擇節(jié)點(diǎn)成為簇頭，節(jié)點(diǎn)成為簇首之后，與其最近的一些普通節(jié)點(diǎn)動(dòng)態(tài)的連接，從而形成簇。在數(shù)據(jù)傳輸階段，主要是傳感器節(jié)點(diǎn)把采集到的數(shù)據(jù)向簇頭傳輸，以及簇頭把接收到的數(shù)據(jù)融合后再傳送給基站。

LEACH路由協(xié)議的優(yōu)點(diǎn)是能保證所有節(jié)點(diǎn)都有機(jī)會(huì)成為簇頭，從網(wǎng)絡(luò)整體來說，節(jié)點(diǎn)消耗的能量得到均衡，起到了節(jié)能的效果。缺點(diǎn)是網(wǎng)絡(luò)對(duì)簇頭的選舉是依據(jù)隨機(jī)生成數(shù)大小決定，導(dǎo)致位置差，前期耗能大的節(jié)點(diǎn)也可以成為簇首，加快這類節(jié)點(diǎn)的死亡速度。同時(shí)由于簇首與匯聚點(diǎn)之間是采用單跳的傳輸方式，使簇首的能量消耗過快導(dǎo)致節(jié)點(diǎn)死亡。同時(shí)由于簇首離匯聚點(diǎn)距離的不同，在傳遞等量數(shù)據(jù)時(shí)，節(jié)點(diǎn)消耗能耐不均等，使得離匯聚點(diǎn)遠(yuǎn)的節(jié)點(diǎn)死亡過快。所以LEACH協(xié)議一般只適用于小型網(wǎng)絡(luò)。

2 EEUC協(xié)議

EEUC協(xié)議[2]是無線傳感網(wǎng)中一種典型的基于非均勻分簇思想的層次型絡(luò)路由協(xié)議，與LEACH協(xié)議簇首與匯聚點(diǎn)之間采用單跳傳輸方式相比，EEUC協(xié)議采用多跳的方式防止離匯聚點(diǎn)遠(yuǎn)的簇首過早死亡，均衡了網(wǎng)絡(luò)中簇首能耗，延長(zhǎng)了網(wǎng)絡(luò)生命周期。EEUC協(xié)議整體上沿用了LEACH協(xié)議的工作流程，也是將網(wǎng)絡(luò)工作過程劃分為輪，每輪分為建簇和傳輸兩個(gè)階段組成，其中建簇階段包括簇首的選舉和簇的形成兩個(gè)階段。不同的是EEUC協(xié)議在簇首選舉時(shí)采用二次選舉的方式推選最終簇首。首先在網(wǎng)絡(luò)中通過隨機(jī)數(shù)產(chǎn)生候選簇首，再根據(jù)候選簇首剩余能量產(chǎn)生最終簇首，完成簇首在網(wǎng)絡(luò)中均勻分布以及均衡節(jié)點(diǎn)能耗的工作。

EEUC算法采用非均勻分簇的思想，根據(jù)節(jié)點(diǎn)與匯聚節(jié)點(diǎn)之間的距離，縮小靠近匯聚節(jié)點(diǎn)的成簇規(guī)模，使得簇內(nèi)節(jié)點(diǎn)傳輸時(shí)能耗降低，節(jié)點(diǎn)可以將更多能量用于簇間傳遞數(shù)據(jù)。提升網(wǎng)絡(luò)性能并夠緩解“熱節(jié)點(diǎn)”現(xiàn)象。但EEUC算法還是仍有一些不足：首先在簇首的選舉階段，推舉候選簇頭節(jié)點(diǎn)僅依據(jù)隨機(jī)生成數(shù)大小決定，對(duì)于剩余能量少的節(jié)點(diǎn)任然存在被選為候選簇頭的可能。然后決定候選節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑的參考因素只有節(jié)點(diǎn)與匯聚節(jié)點(diǎn)之間的距離，沒有考慮剩余能量低的節(jié)點(diǎn)。另外在數(shù)據(jù)傳輸階段，選擇可能成為下一跳的簇頭時(shí)，不考慮數(shù)據(jù)傳輸可靠性，導(dǎo)致丟包、重發(fā)，進(jìn)而造成網(wǎng)絡(luò)能耗不均衡。

3 基于最小生成樹改進(jìn)算法設(shè)計(jì)

針對(duì)EEUC算法存在的問題，EEUC協(xié)議基礎(chǔ)上的改進(jìn)，因此本部分從優(yōu)化節(jié)點(diǎn)競(jìng)爭(zhēng)半徑和最小生成樹的建立兩個(gè)方面對(duì)改進(jìn)部分進(jìn)行詳細(xì)描述。

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

本文針對(duì)EEUC算法中的節(jié)點(diǎn)競(jìng)爭(zhēng)半徑的不足之處進(jìn)行改進(jìn)，將節(jié)點(diǎn)的剩余能量因素考慮在其中，使設(shè)定的候選節(jié)點(diǎn)競(jìng)爭(zhēng)半徑更加合理。

（1）

上式中，為節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑；為網(wǎng)絡(luò)中距離匯聚節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離；則為網(wǎng)絡(luò)中距離匯聚節(jié)點(diǎn)最近節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離；為節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離；為節(jié)點(diǎn)最大競(jìng)選的半徑；為調(diào)節(jié)因子的參數(shù)；為第輪時(shí)的平均剩余能量；為節(jié)點(diǎn)在第輪時(shí)的剩余能量。

3.2 構(gòu)造最小生成樹

與EEUC相同，在建簇階段結(jié)束后，簇間采用多跳的方式傳輸數(shù)據(jù)。本文采用Kruskal算法思想構(gòu)造最小生成樹。為了使簇間節(jié)點(diǎn)在傳遞數(shù)據(jù)時(shí)的能量消耗更加均衡，本文將發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)兩者相距的距離、兩者的剰余能量和接收節(jié)點(diǎn)到匯聚節(jié)點(diǎn)兩者間的距離三個(gè)參考因素作為權(quán)值的參數(shù)帶入計(jì)算。公式如下。

（2）

其中，為本文設(shè)立的簇頭與簇頭相連的權(quán)值；為簇頭到簇頭之間的距離；為簇頭到匯聚節(jié)點(diǎn)的距離；為簇頭到匯聚節(jié)點(diǎn)之間的距離；為簇頭的剩余能量，為簇頭的剩余能量；為節(jié)點(diǎn)傳輸數(shù)據(jù)所需要消耗的能量，具體的得出方式將在后文提出。

4 網(wǎng)絡(luò)仿真

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

本文通過Matlab對(duì)經(jīng)典EEUC協(xié)議與本文提出的改進(jìn)分簇協(xié)議T-EEUC進(jìn)行模擬仿真。實(shí)驗(yàn)中采用與文獻(xiàn)[3]中一致的無線通信能量消耗模型。設(shè)定發(fā)射距離閾值。發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)間距離小于時(shí)，采用自由空間傳播模型，發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)間距離大于等于時(shí)，采用多路徑模型。則當(dāng)發(fā)送節(jié)點(diǎn)距離接收節(jié)點(diǎn)距離為時(shí)發(fā)送 bit的數(shù)據(jù)所消耗的能量為

（3）

（3）式中： 為表示射頻能耗系數(shù)； 和 為不同放大功率下所需要消耗的能量。是節(jié)點(diǎn)接收 bit數(shù)據(jù)所需要消耗的能量。實(shí)驗(yàn)有關(guān)參數(shù)設(shè)置如下表1所示。

表1 實(shí)驗(yàn)仿真相關(guān)參數(shù)表

[參數(shù)名稱 參數(shù)值 參數(shù)名稱 參數(shù)值 網(wǎng)絡(luò)覆蓋范圍 （200m，200m） 節(jié)點(diǎn)初始能量 1J 匯聚節(jié)點(diǎn)位置 （100m，100m） 射頻能耗系數(shù) 50nJ/bit 節(jié)點(diǎn)數(shù)量 400個(gè) 信道空閑模式系數(shù) 10pJ/bit/ 數(shù)據(jù)包大小 4000bits 多路徑模式系數(shù) 0.0013pJ/bit/ 控制包大小 400bits 簇頭節(jié)點(diǎn)融合能耗 5nJ/bit 距離閾值 ]

4.2 實(shí)驗(yàn)與分析

本文提出的基于最小生成樹的層次型節(jié)能路由算法T-EEUC與EEUC算法在相同的網(wǎng)絡(luò)配置環(huán)境下的仿真得出剩余能量的比較結(jié)果如圖2所示。

圖2 剩余能量比較

從圖2可以得知，在網(wǎng)絡(luò)建立的起始階段執(zhí)行T-EEUC的網(wǎng)絡(luò)能量消耗與執(zhí)行EEUC的網(wǎng)絡(luò)基本相同，從20輪開始，兩種網(wǎng)絡(luò)的節(jié)點(diǎn)的剩余能量開始出現(xiàn)差異，執(zhí)行T-EEUC的網(wǎng)絡(luò)能量消耗低于執(zhí)行EEUC的網(wǎng)絡(luò)。在運(yùn)行到500輪左右執(zhí)行EEUC的網(wǎng)絡(luò)所有節(jié)點(diǎn)的能量消耗完畢，網(wǎng)絡(luò)失效。執(zhí)行T-EEUC的網(wǎng)絡(luò)的節(jié)點(diǎn)剩余能量基本在700輪才被消耗完畢。說明本文提出的T-EEUC算法相比EEUC算法可以有效的降低了節(jié)點(diǎn)的能量消耗。

在無線傳感器網(wǎng)絡(luò)中，由于靠近匯聚節(jié)點(diǎn)容易出現(xiàn)“熱節(jié)點(diǎn)”，過快的消耗完自己的能量，導(dǎo)致網(wǎng)絡(luò)無法正常工作，縮短網(wǎng)絡(luò)壽命。因此，評(píng)價(jià)無線傳感網(wǎng)中網(wǎng)絡(luò)性能的一項(xiàng)重要的指標(biāo)就是存活節(jié)點(diǎn)數(shù)。圖3對(duì)比了分別執(zhí)行T-EEUC算法與EEUC算法的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)。可以明顯的看出，執(zhí)行EEUC算法的網(wǎng)絡(luò)在第220輪左右出現(xiàn)了第一個(gè)失效節(jié)點(diǎn)，在第300-400輪網(wǎng)絡(luò)中大部分節(jié)相繼失效，在第500輪左右執(zhí)行EEUC算法的網(wǎng)絡(luò)節(jié)點(diǎn)全部死亡，網(wǎng)絡(luò)停止工作。而執(zhí)行T-EEUC算法的網(wǎng)絡(luò)在第350輪左右出現(xiàn)了第一個(gè)失效節(jié)點(diǎn)。在第400-500輪網(wǎng)絡(luò)中大部分節(jié)相繼失效，在第700輪左右節(jié)點(diǎn)才全部死亡。所以與EEUC算法相比，使用T-EEUC算法的網(wǎng)絡(luò)壽命更長(zhǎng)，可以更好的應(yīng)指定場(chǎng)景的數(shù)據(jù)收集任務(wù)。

5 結(jié)束語

本文基于EEUC算法，在建簇階段加入節(jié)點(diǎn)剩余能量作為因素考量，提出了一種基于最小生成樹的改良層次型節(jié)能路由算法T-EEUC。在本文算法中，優(yōu)化候選簇頭的競(jìng)爭(zhēng)半徑，使簇頭的選取更加合理。在節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)碾A段，采用Kruskal算法構(gòu)造最小生成樹，得到最佳的數(shù)據(jù)傳輸路徑，使數(shù)據(jù)傳輸時(shí)節(jié)點(diǎn)的能耗更合理。實(shí)驗(yàn)結(jié)果表明，在相同的條件下T-EEUC算法在節(jié)點(diǎn)的能量消耗和網(wǎng)絡(luò)的生存時(shí)間兩個(gè)方面都優(yōu)于EEUC算法。證明了T-EEUC可以對(duì)網(wǎng)絡(luò)性能和均衡整體網(wǎng)絡(luò)的能耗進(jìn)行優(yōu)化提升。

參考文獻(xiàn)：

[1] 鄭軍，張寶賢.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京：機(jī)械工業(yè)出版社，2012（2）：55-56.

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

[3] Heinemann W B，Anantha P.Chandrakasan， Hari Balakrishnan. An Application Specific Protocol Architecture for Wireless Microsensor Networks. IEEE TRANSACTION ON WIRELESS COMMUNICATIONS 1，2002（4）.