摘要：無線傳感器網(wǎng)絡(luò)（WSN）路由協(xié)議中的LEACH-C協(xié)議是一種集中式的簇頭選擇協(xié)議，不同于LEACH分布式隨機(jī)選擇簇頭的方式。針對(duì)LEACH-C只考慮節(jié)點(diǎn)剩余能量和過度依賴基站等問題，在LEACH-C成簇基礎(chǔ)上進(jìn)行改進(jìn)，主簇頭和路由簇頭的選擇既考慮了節(jié)點(diǎn)的覆蓋率也兼顧節(jié)點(diǎn)的能量剩余和距離，減少頻繁分簇而導(dǎo)致的能量消耗，路由采取雙路徑路由通信方案，提高網(wǎng)絡(luò)的健壯性。通過Matlab仿真實(shí)驗(yàn)平臺(tái)驗(yàn)證了改進(jìn)協(xié)議比LEACH-C更能延長(zhǎng)網(wǎng)絡(luò)壽命。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；LEACH-C協(xié)議；剩余能量；覆蓋率；雙路徑路由通信

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

1 概述

無線傳感器網(wǎng)絡(luò)（WSN）[1]已廣泛用于監(jiān)測(cè)環(huán)境、軍事活動(dòng)和現(xiàn)代農(nóng)業(yè)等方面，具有重要研究意義和價(jià)值。傳感器節(jié)點(diǎn)的能量是有限的，所以高效地利用有限的能量以獲得最大的生命周期是無線傳感器網(wǎng)絡(luò)研究的重要問題之一[2]。

低功耗自適應(yīng)聚類路由協(xié)議（LEACH） [3]是WSN中經(jīng)典的分簇路由協(xié)議，其協(xié)議通過循環(huán)隨機(jī)地選舉簇頭節(jié)點(diǎn)來提高網(wǎng)絡(luò)的能量利用效率和延長(zhǎng)整個(gè)系統(tǒng)的生命周期。LEACH-C[4]采用集中式的簇頭產(chǎn)生協(xié)議。當(dāng)每輪開始時(shí)，每個(gè)節(jié)點(diǎn)向基站報(bào)告自己的剩余能量和位置，基站計(jì)算所有節(jié)點(diǎn)的平均能量，剩余能量高于平均能量的節(jié)點(diǎn)作為候選節(jié)點(diǎn)并從中最優(yōu)的作為簇頭。LEACH-C的不足是每一輪結(jié)束后所有網(wǎng)絡(luò)節(jié)點(diǎn)都要給基站發(fā)送自己的狀態(tài)消息，而且簇頭節(jié)點(diǎn)也是以單跳的形式直接和基站通信[5]。文獻(xiàn)[6]提出了基于粒子群優(yōu)化的LEACH-C算法的改進(jìn)。文獻(xiàn)[7]提出了基于Dijkstra路由策略的LEACH-C改進(jìn)算法，但未考慮中間節(jié)點(diǎn)的能耗問題。

在綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)覆蓋率以及半徑內(nèi)節(jié)點(diǎn)通信代價(jià)因素提出了一種改進(jìn)的LEACH-C成簇算法，引入路由節(jié)點(diǎn)代替簇頭路由的方式來提高簇的生存能力。在路由機(jī)制中采用雙路徑通信方案，提高網(wǎng)絡(luò)健壯性。仿真結(jié)果表明該算法在確保檢測(cè)區(qū)域有較好的覆蓋性條件下延長(zhǎng)了網(wǎng)絡(luò)壽命。

2 相關(guān)參數(shù)的定義與計(jì)算方式

2.1 能量因子定義

在基站選擇簇頭時(shí)，需要考慮節(jié)點(diǎn)的剩余能量，因而能量因子是描述節(jié)點(diǎn)剩余能量與網(wǎng)絡(luò)平均能量的一個(gè)參數(shù)，能量因子越大的節(jié)點(diǎn)表示節(jié)點(diǎn)剩余能量越多，當(dāng)選簇頭的概率應(yīng)該越大。能量因子的確定：

其中，Eir為i節(jié)點(diǎn)的當(dāng)前剩余能量，Ei為能量比值。當(dāng)節(jié)點(diǎn)剩余能量大于平均能量時(shí)Ei大于1。

2.2 覆蓋率因子定義

節(jié)點(diǎn)的被覆蓋因子Ci：傳感器節(jié)點(diǎn)i的覆蓋面積內(nèi)，被其他傳感器節(jié)點(diǎn)覆蓋的面積與本節(jié)點(diǎn)覆蓋區(qū)域面積的比值。假設(shè)有N個(gè)鄰居節(jié)點(diǎn)對(duì)i節(jié)點(diǎn)的監(jiān)測(cè)范圍有重合，若這N個(gè)節(jié)點(diǎn)在去除該區(qū)域的相互重疊面積后總覆蓋面積為Ai，A為i節(jié)點(diǎn)的監(jiān)測(cè)范圍。則節(jié)點(diǎn)i的被覆蓋率Ci的計(jì)算如下：

若節(jié)點(diǎn)Ci為1時(shí)，則稱為完全覆蓋，該節(jié)點(diǎn)的死亡不會(huì)影響整個(gè)網(wǎng)絡(luò)的覆蓋范圍和覆蓋率。若節(jié)點(diǎn)Ci不為1時(shí)，則稱非完全覆蓋或無覆蓋。

2.3 節(jié)點(diǎn)半徑內(nèi)通信代價(jià)因子

選擇出來的簇頭不應(yīng)該偏離簇內(nèi)大部分成員太遠(yuǎn)，如果位于整個(gè)簇的幾何中心位置附近，有利于降低簇內(nèi)成員與簇頭的通信，因?yàn)榇仡^要擔(dān)任與基站的路由通信功能，所以還要考慮簇頭與基站距離的因素。所以通信代價(jià)因子的定義為：

其中，ri為節(jié)點(diǎn)i為未當(dāng)選簇頭的輪數(shù)，一旦當(dāng)選簇頭或副簇頭則重置為0。r為系統(tǒng)當(dāng)前運(yùn)行的輪數(shù)。輪是以基站規(guī)定的時(shí)間段為標(biāo)準(zhǔn)，在這時(shí)間段內(nèi)所有節(jié)點(diǎn)都至少能向基站傳送一次數(shù)據(jù)。由公式可知在開始的階段簇頭的選擇主要依靠覆蓋率、剩余能量以及通信代價(jià)，在多輪以后逐步以剩余能量和通信代價(jià)為主要選擇依據(jù)，這樣也增強(qiáng)了簇頭選擇的合理性。

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

主要剩余能量、節(jié)點(diǎn)覆蓋率以及半徑內(nèi)節(jié)點(diǎn)通信代價(jià)因素來進(jìn)行網(wǎng)絡(luò)分簇，提高能量利用效率。首先描述簇頭選擇公式，然后根據(jù)公式提出具體選擇協(xié)議。

3.1 簇頭的選擇

步驟一：首輪所有節(jié)點(diǎn)發(fā)送自己的能量以及位置信息，距離遠(yuǎn)的節(jié)點(diǎn)以多跳方式發(fā)送給基站，以后節(jié)點(diǎn)以信息捎帶的方式發(fā)送剩余能量即可。BS根據(jù)所有節(jié)點(diǎn)的信息計(jì)算網(wǎng)絡(luò)平均能量，各個(gè)節(jié)點(diǎn)覆蓋率以及通信代價(jià)因子。

步驟二：判斷節(jié)點(diǎn)的剩余能量是否大于平均能量，如果大于平均能量則有機(jī)會(huì)競(jìng)爭(zhēng)簇頭。

步驟三：BS在選擇簇頭時(shí)盡量選擇Ci為1的節(jié)點(diǎn)。如果一個(gè)簇范圍內(nèi)有多個(gè)符合條件的節(jié)點(diǎn)，則根據(jù)S因子選擇主簇頭。其他符合條件的節(jié)點(diǎn)BS可根據(jù)需要讓其睡眠。若某區(qū)域內(nèi)沒有Ci為1的節(jié)點(diǎn)，則根據(jù)S因子利用擬退火算法選擇出主簇首。

步驟四：BS把簇首信息廣播給相應(yīng)的簇節(jié)點(diǎn)，節(jié)點(diǎn)接收廣播信息確定自己是否當(dāng)選為簇頭節(jié)點(diǎn)，是則根據(jù)廣播半徑廣播自己的簇頭消息，不是則根據(jù)接收到的簇頭消息加入離自己最近的簇中，完成簇的建立。

3.2 路由節(jié)點(diǎn)的選擇和成簇通信方式

在路由點(diǎn)選擇中，BS可根據(jù)簇的分布情況，在網(wǎng)絡(luò)中選擇出多個(gè)節(jié)點(diǎn)擔(dān)任路由節(jié)點(diǎn)，負(fù)責(zé)整個(gè)網(wǎng)絡(luò)中信息的專遞工作。這樣通過簇的管理節(jié)點(diǎn)與路由傳送節(jié)點(diǎn)的分離，降低簇頭節(jié)點(diǎn)的能量消耗，延長(zhǎng)簇頭的壽命。路由節(jié)點(diǎn)的選擇方式是根據(jù)能量因子以及與基站的距離因素利用擬退火算法來選擇。在穩(wěn)定階段，簇內(nèi)的所有普通節(jié)點(diǎn)都按照時(shí)分復(fù)用（Time Division Multiple Access，TDMA）時(shí)隙將采集到的信息傳送到簇頭節(jié)點(diǎn)。所有簇頭在收集數(shù)據(jù)時(shí)都進(jìn)行數(shù)據(jù)融合才向路由節(jié)點(diǎn)或基站發(fā)送，減少通信量。

3.3 簇間路由選擇

基站在選擇完路由節(jié)點(diǎn)以后，為每個(gè)路由節(jié)點(diǎn)在通往基站的方向上利用Dijkstra算法選擇出兩條最短路徑，但一次只使用一條路徑，另一條作為備用路徑保存。每個(gè)路由節(jié)點(diǎn)無需保存路徑的全部節(jié)點(diǎn)信息，只需保持路由節(jié)點(diǎn)的下一跳的兩個(gè)后繼節(jié)點(diǎn)（每一個(gè)后繼節(jié)點(diǎn)代表一條路徑）和需要通過本路由節(jié)點(diǎn)向基站傳遞消息的所有前驅(qū)節(jié)點(diǎn)（代表有多少簇頭節(jié)點(diǎn)需要通過本節(jié)點(diǎn)給基站傳遞消息），這樣就可以實(shí)現(xiàn)較遠(yuǎn)的路由節(jié)點(diǎn)以多跳的方式傳送數(shù)據(jù)給基站。每個(gè)路由節(jié)點(diǎn)收到消息后都進(jìn)行數(shù)據(jù)融合以減少不必要的能量消耗。為每個(gè)路由節(jié)點(diǎn)設(shè)置一個(gè)通信閾值，如果通信量超過這個(gè)閾值，便可通知自己的部分前驅(qū)節(jié)點(diǎn)選擇第二條路徑傳送數(shù)據(jù)，從而達(dá)到減少某個(gè)路由節(jié)點(diǎn)能量過度消耗而提前死亡的危險(xiǎn)，增強(qiáng)網(wǎng)絡(luò)的健壯性。

4 仿真實(shí)現(xiàn)

4.1 模擬實(shí)驗(yàn)環(huán)境設(shè)置和參數(shù)

用Matlab作為仿真實(shí)驗(yàn)平臺(tái)，仿真環(huán)境是在200m*200m的正方形區(qū)域內(nèi)隨機(jī)的部署200個(gè)傳感器節(jié)點(diǎn)，初始能量為E=1J，基站處于正方形的左下角（0，0）m位置，并使用與文獻(xiàn)[8]相同的無線通信能量消耗模型。發(fā)送數(shù)據(jù)和接收數(shù)據(jù)的無線通信模型分別為：

Leach協(xié)議在100輪時(shí)出現(xiàn)死亡節(jié)點(diǎn)，Leach-c協(xié)議在127輪出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)，而本協(xié)議在將近250輪才出現(xiàn)，有效延長(zhǎng)了第一個(gè)節(jié)點(diǎn)死亡時(shí)間。不過本協(xié)議在出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)以后網(wǎng)絡(luò)的節(jié)點(diǎn)死亡速度很快，在后面的六十輪中死亡節(jié)點(diǎn)數(shù)目急劇上升，幾乎全部死亡。通過三種協(xié)議的比較，顯示了改進(jìn)協(xié)議在確保網(wǎng)絡(luò)有較好覆蓋率條件下延長(zhǎng)了網(wǎng)絡(luò)。

5 結(jié)束語

通過對(duì)Leach協(xié)議和Leach-c協(xié)議的分析研究，綜合考慮了兩個(gè)協(xié)議的優(yōu)缺點(diǎn)，提出一種基于節(jié)點(diǎn)覆蓋率、剩余能量和位置信息的Leach-c協(xié)議的改進(jìn)協(xié)議。協(xié)議在Leach-c的基礎(chǔ)上改進(jìn)了簇頭選擇條件，加入路由節(jié)點(diǎn)改進(jìn)簇首節(jié)點(diǎn)路由方式，采取了雙路徑方式，不僅保證了簇消息的發(fā)送成功概率，又優(yōu)化了簇首節(jié)點(diǎn)的能耗過快問題，保證了網(wǎng)絡(luò)在有較好的覆蓋性條件下延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。實(shí)驗(yàn)表明在確保網(wǎng)絡(luò)覆蓋率的條件下很好的延長(zhǎng)了網(wǎng)絡(luò)的生存壽命，但還有些可以改進(jìn)的地方，如中繼簇頭能耗較大問題，對(duì)基站的依賴程度還比較大，不夠獨(dú)立等。

參考文獻(xiàn)：

[1] 廖明華，張華，王東.基于LEACH協(xié)議的簇頭選舉改進(jìn)算法[J].計(jì)算機(jī)工程，2011，37（7）：112-114.

[2] 底欣，張百海.一種改進(jìn)的WSN成簇算法[J].計(jì)算機(jī)工程，2011，37（1）：110-112.

[3] Heinzelman W， Chandrakasan A， Balakrishnan H. Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]// Proc. of the 33rd Annual Hawaii Intl Conf. on System Sciences. [S.l.]： IEEE Computer Society， 2000.

[4] Siva DMG， Ma DCF. A Centralized Energy efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications， 2005， 43（3）： 8-13.

[5] 何傳波.無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究[D].廣西大學(xué)，2014.

[6] 閆效鶯，程國(guó)建.基于改進(jìn)粒子群優(yōu)化的WSN均衡能量消耗路由算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012， 10（33）：3692-3696.

[7] 蔣華，劉偉強(qiáng)，王鑫.無線傳感器網(wǎng)絡(luò)中Leach-c路由協(xié)議的研究與改進(jìn)[J].微電子學(xué)與計(jì)算機(jī)，2014，12（31）：43-47.

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