基于EEUC的改進研究

章康馳

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2018）04-0032-03

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

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

1 LEACH協(xié)議

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

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

2 EEUC協(xié)議

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

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

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

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

3.1 節(jié)點競爭半徑

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

（1）

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

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

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

（2）

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

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

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

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

（3）

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

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

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

4.2 實驗與分析

本文提出的基于最小生成樹的層次型節(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é)點的剩余能量開始出現(xiàn)差異，執(zhí)行T-EEUC的網(wǎng)絡(luò)能量消耗低于執(zhí)行EEUC的網(wǎng)絡(luò)。在運行到500輪左右執(zhí)行EEUC的網(wǎng)絡(luò)所有節(jié)點的能量消耗完畢，網(wǎng)絡(luò)失效。執(zhí)行T-EEUC的網(wǎng)絡(luò)的節(jié)點剩余能量基本在700輪才被消耗完畢。說明本文提出的T-EEUC算法相比EEUC算法可以有效的降低了節(jié)點的能量消耗。

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

5 結(jié)束語

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

參考文獻：

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

[2] 李成法，陳貴海，葉懋等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計算機學(xué)報，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）.