劉 靜，荊瑞俊

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

基于分層結(jié)構(gòu)的WSN路由算法改進(jìn)*

劉 靜，荊瑞俊

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

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

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

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

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

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

1 路由協(xié)議

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

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

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

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

2 LEACH算法改進(jìn)

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

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

(1)

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

(2)

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

(3)

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

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

圖1 基于柵格的多跳算法

3 算法仿真

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

表1 仿真參數(shù)

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

圖2 原LEACH算法

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

圖3 改進(jìn)的算法

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

圖4 基于柵格的改進(jìn)算法

4 結(jié)論

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

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

[2] 尚興宏.無(wú)線傳感器網(wǎng)絡(luò)若干關(guān)鍵技術(shù)的研究[D].南京：南京理工大學(xué),2013.

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

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

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

[6] 胡艷華，張建軍.LEACH協(xié)議的簇頭多跳(LEACH-M)改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,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ú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用與軟件,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è)大學(xué)科技創(chuàng)新基金(2016004)

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

1674- 4578(2016)06- 0045- 03

TN929.5；TP 212.9

A