劉 靜，荊瑞俊

(山西農(nóng)業(yè)大學軟件學院，山西 晉中 030801)

基于分層結(jié)構的WSN路由算法改進*

劉 靜，荊瑞俊

(山西農(nóng)業(yè)大學軟件學院，山西 晉中 030801)

為了延長無線傳感網(wǎng)絡(Wireless Sensor Network)的生命周期，提出一種基于分層結(jié)構的WSN路由算法改進。在著名的LEACH算法基礎上,提出其中關于簇頭選擇所存在的問題，將原算法中的簇頭節(jié)點占比p變?yōu)橐粋€隨節(jié)點與基站距離變化的動態(tài)比率(通過two-ray模型計算得出)，并通過參考節(jié)點剩余能量與原始能量比值優(yōu)化了簇頭選擇的閾值；接著修改了路由算法的單跳為多跳，并且以基于虛擬柵格的路由算法得以實現(xiàn)，從而使得整個改進算法得以在更大的網(wǎng)絡里應用。

WSN路由算法；分層結(jié)構；LEACH；多跳；虛擬柵格

在當今社會中，由于越來越多的現(xiàn)象需要人們?nèi)z測, 使得無線傳感網(wǎng)絡(Wireless Sensor Network)得到了空前的發(fā)展。到現(xiàn)在，WSN已被人們廣泛應用于環(huán)境監(jiān)測，健康檢查，工業(yè)控制，干擾探測，以及地震監(jiān)測等眾多領域[1]。

一個標準的WSN網(wǎng)絡通常由許多傳感器節(jié)點組成，這些節(jié)點一般都是依靠電池提供能量，但是經(jīng)過一段時間的使用之后，電池的更換一般都很難實現(xiàn)，除了電能資源稀少珍貴之外，包括處理能力，無線通信帶寬，儲存空間都十分有限， 所以傳感器節(jié)點的節(jié)能工作就成為延長WSN生命周期最主要的部分。在任何一種網(wǎng)絡中，路由算法的優(yōu)劣在一定程度上決定了整個網(wǎng)絡系統(tǒng)的性能，一個好的路由算法能夠有效地降低網(wǎng)絡節(jié)點的能耗[2]。

本文旨在通過改進路由算法降低WSN網(wǎng)絡的能耗。首先簡單分析了基于分層結(jié)構的路由算法，然后重點分析了LEACH算法，對其中關于簇頭選擇上的問題提出改進算法，再針對傳感器節(jié)點之間的通信模式提出改進方案，最后在Matlab進行了仿真驗證。

1 路由協(xié)議

1.1 傳統(tǒng)路由協(xié)議

經(jīng)過多年的研究發(fā)展人們已經(jīng)開發(fā)出了多種WSN路由協(xié)議，傳統(tǒng)路由協(xié)議的代表是洪泛法，這種簡單的方法存在很多的問題，比如信息爆炸和信息重疊，由于這些原因這種簡單的方法也很難被應用于實踐[3]?，F(xiàn)在人們應用較多的路由協(xié)議基本可以分為三大類：平面路由協(xié)議，分層路由協(xié)議和基于地理位置的路由協(xié)議[4]。平面路由協(xié)議的代表為SPIN，DD，Rumor，基于地理位置的路由協(xié)議則以GEAR和GEM為代表。

1.2 基于分層結(jié)構的路由協(xié)議

在實踐中，人們應用更多的是分層的WSN路由協(xié)議，在這項路由協(xié)議中通過簇的劃分，使整個系統(tǒng)的能量消耗得以降低，并且使能耗分布也更加均勻，而由于減少了參與運算的傳感器節(jié)點數(shù)，整個通信的開銷也降低了。并且基于簇形成的策略網(wǎng)絡，拓撲結(jié)構的變化對于網(wǎng)絡的影響也會降低，使網(wǎng)絡整體變得更加穩(wěn)定。在目前的分層路由算法中，低功耗自適應集簇分層型協(xié)議LEACH(Low Energy Adaptive Clustering Hierarchy)是最早最成熟的算法，也是幾乎所有分層路由協(xié)議的基礎。

2 LEACH算法改進

LEACH在執(zhí)行過程中不停的循環(huán)執(zhí)行簇的重構過程，一個簇的重構過程可以理解為一個回合，每個回合可以分為建立階段和數(shù)據(jù)傳輸?shù)姆€(wěn)定階段。簇的建立過程可分成四個階段：簇頭節(jié)點的選擇、簇頭節(jié)點的廣播、簇頭節(jié)點的建立和調(diào)度機制的生成[5]。在簇頭建立的過程中，優(yōu)化簇頭節(jié)點的選擇是重要也是最能有效延長WSN生命周期的手段。

在簇頭的選擇中，LEACH以輪為周期工作，在每一輪，所有的節(jié)點都會生成一個介于0到1范圍內(nèi)的隨機數(shù)，然后將隨機數(shù)跟閾值T(n)做比較[6]：

(1)

式中的P是簇頭節(jié)點占整個節(jié)點的比率，r代表輪數(shù)，G是在最后的1/P輪中沒有成為簇頭的節(jié)點的集合。如果隨機數(shù)小于T(n)，這個節(jié)點則成為一個簇頭，產(chǎn)生簇頭之后其他的節(jié)點會根據(jù)距離關系選擇加入最近的簇，在形成的簇內(nèi)，非簇頭節(jié)點將會向簇頭發(fā)送信息，由簇頭進行數(shù)據(jù)融合再與基站通信，到此就完成了簇頭的選擇過程。對比與其他的路由協(xié)議，LEACH在很大程度上提高了效率，但是它依舊存在一些問題，在簇頭的選擇過程中，由于選擇的隨機性，使得簇頭節(jié)點的分布不均勻，整個系統(tǒng)的能耗就不均勻，而剩余能量大的節(jié)點不能獲得比低能節(jié)點更高的概率來成為一個簇頭，這樣將會大大地縮短網(wǎng)絡的生命周期。所以需要修改原先的閾值T(n)為[7]：

(2)

式中的Ec代表節(jié)點的剩余能量，Ei代表節(jié)點的初始能量。很明顯通過添加這個比值，高能的節(jié)點將獲得更高的成為簇頭的概率，而Phead在這里也不再是一個定值，而是一個隨著節(jié)點距基站距離變化的值(通過two-ray模型計算得出)，具體關系為：

(3)

選擇了簇頭之后，就進入通信階段，在傳統(tǒng)的LEACH算法中傳感器節(jié)點的通信通常為單跳，這意味著簇頭只能直接與基站進行通信，這就帶來了很多問題，且不說當網(wǎng)絡的規(guī)模很大時，節(jié)點的傳輸能力不能達到那樣的距離，就算是可以做到也需要消耗大量的能量，所以必須要修改路由算法的單跳為多跳，相比于單跳，多跳可以降低節(jié)點上能量的消耗。在選擇了簇頭之后，各個傳感器節(jié)點會根據(jù)地理位置關系選擇加入最近的簇(在這里設定距離基站最近的節(jié)點會自動成為簇頭)以TDMA形式完成簇內(nèi)的通信。

在之后的通信階段就需要引入一個新的通信模式——基于柵格的多跳模式[8]。這種算法的基本思想是將整個系統(tǒng)區(qū)域劃分為一個一個的柵格，并對這些柵格進行標號，每個柵格內(nèi)部都有一些傳感器節(jié)點?，F(xiàn)在設定一個通信機制，先計算節(jié)點的數(shù)目盡量保證一個柵格內(nèi)由LEACH算法選出的簇頭數(shù)目大于等于1，然后根據(jù)剩余能量大小選出一個剩余能量大的傳感器節(jié)點作為此柵格的簇頭，接著根據(jù)地理位置關系和鄰居柵格簇頭剩余能量大小選擇中繼來進行多跳傳輸。實現(xiàn)多跳的方式有很多，選擇柵格的方式可以在網(wǎng)絡內(nèi)部運算上節(jié)省大量的開支，更加便于應用于實踐。在實際的操作中可根據(jù)經(jīng)驗設定柵格數(shù)，或設定一個最大柵格數(shù)，如果柵格內(nèi)不存在傳感器節(jié)點，再逐步縮小柵格數(shù)直至每個柵格內(nèi)都有傳感器節(jié)點存在。實現(xiàn)多跳的過程如圖1所示，例如基站位于3號柵格，則周圍2、5、6號柵格成為第一圈柵格，柵格內(nèi)能量最大的簇頭先進行數(shù)據(jù)融合再與基站進行通信，之后的1、4、7、8、9便成為第二圈柵格，第二圈柵格要與基站通信必須通過第一圈，且下一跳的柵格為所有鄰區(qū)柵格內(nèi)距離基站最近的柵格，以此類推，直至與基站通信。

圖1 基于柵格的多跳算法

3 算法仿真

在M為100 m的范圍內(nèi)隨機放置100個節(jié)點，每個節(jié)點的原始能量為0.5 J，仿真原LEACH算法的p為0.08，其他功耗數(shù)據(jù)見表1[9]。

表1 仿真參數(shù)

圖2表示原LEACH的仿真結(jié)果，以半數(shù)節(jié)點的消亡輪數(shù)和全部節(jié)點消亡輪數(shù)為參考，大約在500輪左右有半數(shù)的節(jié)點耗盡了能量，而在1 000輪之前幾乎所有的節(jié)點已經(jīng)耗盡能量。

圖2 原LEACH算法

圖3表示改進簇頭選擇方式后的仿真結(jié)果，可以看出通過對閾值的改變，簇頭的分布和能耗的分布更加均勻，大約在1 200輪左右耗盡了一半的節(jié)點能量，而全部節(jié)點消亡輪數(shù)也達到了2 500輪以上，比原LEACH提高了1.5倍的網(wǎng)絡生存時間。

圖3 改進的算法

圖4表示基于柵格多跳的改進后算法仿真結(jié)果， 這里設定最大柵格數(shù)為16，如果相鄰柵格內(nèi)沒有已生成簇頭，則自動減小柵格數(shù)直到每個柵格內(nèi)至少包含一個簇頭。由于在圖3的基礎上添加了基于柵格的多跳之后半數(shù)節(jié)點消亡輪數(shù)增加到了約1 800輪，全部節(jié)點消亡輪數(shù)更是達到了5 000輪左右，相比于單跳提高了近1倍的網(wǎng)絡生存時間。

圖4 基于柵格的改進算法

4 結(jié)論

改進后的LEACH算法在原算法基礎上使得剩余能量高且距離基站近的傳感器節(jié)點更容易成為一個簇頭，從而使得整個網(wǎng)絡能耗分布更加均勻，提高了網(wǎng)絡生存時間。在實際的傳感網(wǎng)中由于網(wǎng)絡較大造成了過多的網(wǎng)絡通信能耗，將節(jié)點通信方式從單跳改為多跳更加節(jié)能，使網(wǎng)絡具有更好的擴展性，使得該算法得以應用在更大的網(wǎng)絡里。而基于柵格的多跳相比于其他多跳方式在網(wǎng)絡內(nèi)部運算上開銷較小，更容易應用于實踐當中。

[1] 尹湘源.無線傳感器網(wǎng)絡低能耗分簇路由算法關鍵技術研究[D].上海：華東理工大學,2014.

[2] 尚興宏.無線傳感器網(wǎng)絡若干關鍵技術的研究[D].南京：南京理工大學,2013.

[3] 施家煌，趙成林.無線傳感器網(wǎng)絡(WSN)路由協(xié)議的分析與比較[A].中國通信學會，2008通信理論與技術新發(fā)展——第十三屆全國青年通信學術會議論文集(下)[C].中國通信學會,2008:4.

[4] 趙強利，蔣艷凰，徐明.無線傳感器網(wǎng)絡路由協(xié)議的分析與比較[J].計算機科學,2009(2):35-41.

[5] 鄭顧平，朱維.基于LEACH協(xié)議的安全性改進與建模分析[J].軟件導刊,2014(7):131-133.

[6] 胡艷華，張建軍.LEACH協(xié)議的簇頭多跳(LEACH-M)改進算法[J].計算機工程與應用,2009(34):107-109.

[7] Xu Jia,Jin Ning,Lou Xizhong,et al.2012 9th Improvement of LEACH Protocol for WSN[C].International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2012),2012.

[8] 云春峰，王培康.基于虛擬柵格的無線傳感器網(wǎng)絡路由協(xié)議[J].計算機應用與軟件,2009(9):200-202+218.

[9] Saini P,Sharma A K.E-DEEC-enhanced Distributed Energy Efficientclustering Scheme for Heterogeneous WSN[C].2010 1st InternationalConference on Parallel,Distributed and Grid Computing，2010：205-210.

Research on Routing Algorithm for WSN Based on Hierarchical Architecture

Liu Jing, Jing Ruijun

(SchoolofSoftware,ShanxiAgriculturalUniversity,JinzhongShanxi030801,China)

In order to prolong the life cycle of WSN (Wireless Sensor Network), an improved WSN routing algorithm based on hierarchical architecture is proposed. On the basis of famous LEACH algorithm, the problem about cluster head selection is pointed out. It changes the proportion p of cluster nodes in the original algorithm into a dynamic proportion varying along with the distance between node and sink (calculated by two-ray model), and optimizes the threshold of cluster head selection using the ratio between residual energy and original energy. Then the routing algorithm is modified from single hop to multiple hop that realized by using the virtual grid routing algorithm, so that the improved algorithm can be used in larger networks.

WSN routing algorithm; hierarchical architecture; LEACH; multi-hop; virtual grid

2016-11-09

山西農(nóng)業(yè)大學科技創(chuàng)新基金(2016004)

劉 靜(1990- )，女，山西榆社縣人，助教，碩士，研究方向：無線通信及物聯(lián)網(wǎng)。

1674- 4578(2016)06- 0045- 03

TN929.5；TP 212.9

A