無(wú)線傳感器網(wǎng)絡(luò)簇間節(jié)能路由算法

1、2009年第11期,第42卷 通 信 技 術(shù) Vol.42,No.11,2009 總第215期Communications Technology No.215,Totally無(wú)線傳感器網(wǎng)絡(luò)簇間節(jié)能路由算法胡 鋼, 朱佳奇, 陳世志(河海大學(xué) 計(jì)算機(jī)及信息工程學(xué)院,江蘇 常州 213000【摘 要】針對(duì)基于分簇網(wǎng)絡(luò)的無(wú)線傳感器網(wǎng)絡(luò)簇間路由協(xié)議,讓簇首和Sink節(jié)點(diǎn)直接通信或通過(guò)簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)造成能耗不均,節(jié)點(diǎn)過(guò)早死亡的缺陷。文中提出一種基于網(wǎng)關(guān)節(jié)點(diǎn)模型的無(wú)線傳感器網(wǎng)絡(luò)簇間路由算法,通過(guò)簇頭與網(wǎng)關(guān)節(jié)點(diǎn)、網(wǎng)關(guān)節(jié)點(diǎn)自身建立虛電路,制定存儲(chǔ)轉(zhuǎn)發(fā)路由,將數(shù)據(jù)轉(zhuǎn)發(fā)給Sink節(jié)點(diǎn)。并引入延時(shí)等待機(jī)制,增強(qiáng)了

2、簇間信息的融合度,此算法適用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò),有良好的可擴(kuò)展性。仿真表明在能量節(jié)省等性能上與傳統(tǒng)簇間路由算法相較有較大提高。【關(guān)鍵詞】無(wú)線傳感器網(wǎng)絡(luò);網(wǎng)關(guān)節(jié)點(diǎn)模型;簇;簇間路由【中圖分類號(hào)】TN92 【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】1002-0802(200911-0135-03Study on Power-Scant Cluster-Level Routing Algorithm of WSNbased on Clustered NetworkHU Gang, ZHU Jia-qi, CHEN Shi-zhi(Computer & Engineering College, Hoha

3、i University, Changzhou Jiangsu 213000, China【Abstract】Cluster-level routing protocol of WSN based on clustered network forces cluster head nodes to directly communicate with Sink nodes or makes cluster head nodes transmit data, thus causing unequal energy consumption and early death of the nodes. T

4、his paper proposes a gateway nodes model-based cluster-level routing algorithm of WSN. In this model, the virtual circuit is built between cluster head nodes and gateway nodes, and in gateway nodes itself. The store-send routing is established by cluster head nodes and gateway nodes, so the data cou

5、ld transmit to Sink node efficiently. The time-delay mechanism is also introduced in this algorithm, thus to enhance interfusion degree of the cluster-level information. This algorithm is applicable to great-scale wireless sensor network, and has good expansibility. The simulation shows that the new

6、 algorithm is of great improvement on energy consumption as compared with traditional cluster-level routing protocol.【Key words】WSN; gateway nodes model; cluster; cluster-level routing0 引言無(wú)線傳感器網(wǎng)絡(luò)1-3集成了傳感器技術(shù)、嵌入式計(jì)算技術(shù)、無(wú)線通信技術(shù)以及分布式信息處理技術(shù)4。無(wú)線傳感器網(wǎng)絡(luò)是其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息,并發(fā)送給觀察者。預(yù)設(shè)監(jiān)測(cè)區(qū)域內(nèi)大量傳感器節(jié)點(diǎn)通過(guò)自組織的

7、形式構(gòu)成無(wú)線傳感器網(wǎng)絡(luò),感知被測(cè)對(duì)象、采集監(jiān)測(cè)數(shù)據(jù)并且進(jìn)行處理后以無(wú)線的方式逐步發(fā)送到匯聚節(jié)點(diǎn)(Sink 節(jié)點(diǎn),然后通過(guò)Sink節(jié)點(diǎn)連接至internet5。由于無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)能量有限且能量不可補(bǔ)充,設(shè)計(jì)節(jié)能有效的路由機(jī)制能延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存周期,因此合理的路由協(xié)議是無(wú)線傳感器網(wǎng)絡(luò)研究的重點(diǎn)問(wèn)題。1 現(xiàn)有算法分析傳統(tǒng)的基于分簇網(wǎng)絡(luò)的簇間通信方式有以下兩種:(1單跳通信6-7分簇網(wǎng)絡(luò)中各簇的簇首節(jié)點(diǎn)和Sink節(jié)點(diǎn)直接通信,提高自己的發(fā)射功率,擴(kuò)大自己的通信半徑將一段時(shí)間內(nèi)收集的數(shù)據(jù)直接發(fā)送到Sink節(jié)點(diǎn)。簇間單跳通信方式要求所有節(jié)點(diǎn)都有與簇首直接通信的能力,這不利于大規(guī)模網(wǎng)絡(luò)的建立。遠(yuǎn)距離

8、通信會(huì)使節(jié)點(diǎn)能量迅速損耗,距離Sink節(jié)點(diǎn)較遠(yuǎn)的簇首節(jié)點(diǎn)會(huì)很快死亡,從而降低了網(wǎng)絡(luò)的連通性和減少了網(wǎng)絡(luò)的生存周期。(2多跳通信6-7收稿日期:2008-11-06。基金項(xiàng)目:中國(guó)水利水電科學(xué)研究院開(kāi)放研究基金資助(水科科技便函2008010號(hào)。作者簡(jiǎn)介:朱佳奇(1984-,男,碩士研究生,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò);胡鋼(1958-,男,教授,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò);陳世志(1984-,男,碩士研究生,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。135136 分簇網(wǎng)絡(luò)中各簇的簇首節(jié)點(diǎn)通過(guò)多跳方式存儲(chǔ)轉(zhuǎn)發(fā)數(shù)據(jù),向相鄰簇的簇首節(jié)點(diǎn)發(fā)送數(shù)據(jù),通過(guò)相鄰簇的簇首節(jié)點(diǎn)將數(shù)據(jù)轉(zhuǎn)發(fā)至Sink 節(jié)點(diǎn)。多跳通信方式,不

9、需要簇首節(jié)點(diǎn)有直接與Sink 節(jié)點(diǎn)通信的能力,避免了直接與Sink 節(jié)點(diǎn)通信所耗費(fèi)的大量能量,能很好的減少各個(gè)簇首在簇間通信時(shí)的能量損耗。但是通過(guò)簇首轉(zhuǎn)發(fā)數(shù)據(jù)選擇的路徑并不一定是最優(yōu)路徑,簇間通信的能量損耗并不一定最小。2 網(wǎng)絡(luò)模型提出無(wú)線傳感器網(wǎng)絡(luò)可以用無(wú)向圖來(lái)表示:G =(V ,E 。V 表示傳感器節(jié)點(diǎn)的集合,E 表示無(wú)線雙向通信鏈路的集合。對(duì)于i s V ,R 為其最大通信半徑,i S A 表示i s 的射頻覆蓋范圍。發(fā)送節(jié)點(diǎn)i s 和接收節(jié)點(diǎn)j s 之間的距離,用(,i j d s s 表示。在節(jié)點(diǎn)i s 的射頻覆蓋范圍i S A 內(nèi)節(jié)點(diǎn)的集合用(,i i s i S RF s A =

10、表示。簇首(CH的集合用H 表示,H V 。簇首i h 所在簇節(jié)點(diǎn)的集合用(,i i h i h C h M =表示,其中i h M 表示簇內(nèi)成員節(jié)點(diǎn)的集合。根據(jù)以上的描述,在網(wǎng)絡(luò)分簇的過(guò)程中s V ,j h i k h h s C s RF s RF 其中,k j h h H 。即s 是簇首i h 所在簇的成員節(jié)點(diǎn),且其在簇首節(jié)點(diǎn),.k j h h 的射頻通信覆蓋范圍以內(nèi),也就是說(shuō)在分簇過(guò)程中節(jié)點(diǎn)s 同時(shí)收到簇首節(jié)點(diǎn),.k j h h 發(fā)出的簇首申明,并以相應(yīng)判斷準(zhǔn)則最終選擇加入簇首i h 所在的簇,成為其成員節(jié)點(diǎn)。定義這樣的節(jié)點(diǎn)s 為簇,k j h h 的網(wǎng)關(guān)節(jié)點(diǎn),定義網(wǎng)關(guān)節(jié)點(diǎn)的集合為GT

11、 V 。3 算法描述為減少簇內(nèi)通信能量消耗,采用貪婪算法1,7進(jìn)行多跳通信,節(jié)點(diǎn)在鄰居節(jié)點(diǎn)中選擇到事件區(qū)域代價(jià)最小的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。但是由于節(jié)點(diǎn)只知道局部拓?fù)湫畔?會(huì)遇到路由空洞1-2的問(wèn)題和重復(fù)路徑傳輸問(wèn)題,反而增加了能量的消耗。算法將重點(diǎn)解決以上問(wèn)題。 無(wú)線傳感器網(wǎng)絡(luò)按照分簇算法進(jìn)行分簇,確定各個(gè)簇的簇首節(jié)點(diǎn)和相應(yīng)的成員節(jié)點(diǎn); 按照上述網(wǎng)絡(luò)模型,確定分簇后的網(wǎng)關(guān)節(jié)點(diǎn)集合,這些網(wǎng)關(guān)節(jié)點(diǎn)對(duì)向它發(fā)送簇首申明的所有簇首節(jié)點(diǎn)發(fā)送通知,申明其網(wǎng)關(guān)節(jié)點(diǎn)的身份; Sink 節(jié)點(diǎn)廣播興趣到達(dá)事件區(qū)域,節(jié)點(diǎn)集數(shù)據(jù),并按照分簇網(wǎng)絡(luò)的結(jié)構(gòu)向簇首節(jié)點(diǎn)傳輸信息。在此傳輸過(guò)程中,將自己的剩余能量和地理位置坐標(biāo)一并傳

12、輸給簇首節(jié)點(diǎn); 各簇首節(jié)點(diǎn)收到簇內(nèi)成員節(jié)點(diǎn)的剩余能量后,計(jì)算其平均值作為該簇的平均能量;之后,簇首節(jié)點(diǎn)將簇內(nèi)各成員節(jié)點(diǎn)的位置信息、剩余能量以及該簇平均能量信息,備份并發(fā)送給網(wǎng)關(guān)節(jié)點(diǎn)。這樣網(wǎng)關(guān)節(jié)點(diǎn)就擁有了相鄰簇的簇內(nèi)信息; 事件區(qū)域內(nèi)的簇首節(jié)點(diǎn),在其射頻通信范圍內(nèi)尋找距Sink 節(jié)點(diǎn)最近的網(wǎng)關(guān)節(jié)點(diǎn)作為目的節(jié)點(diǎn),并按照貪婪算法多跳發(fā)送數(shù)據(jù);按此方法在網(wǎng)關(guān)節(jié)點(diǎn)之間建立一條虛電路。之后根據(jù)虛電路建立網(wǎng)關(guān)節(jié)點(diǎn)的等待時(shí)序。如圖1所示,簇首節(jié)點(diǎn)A、B、C、D、E、F 分別選擇符合條件的網(wǎng)關(guān)節(jié)點(diǎn)111111a b c d e f 、各自目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)。而在網(wǎng)關(guān)節(jié)點(diǎn)之間建立起端到端的邏輯信道1111a b f

13、 e ,111c d e 同樣按照貪婪算法多跳發(fā)送數(shù)據(jù)。由于多跳路由,是由具有全局拓?fù)湫畔⒌墓?jié)點(diǎn)制定的,所以可以避免貪婪算法帶來(lái)的路 由空洞的問(wèn)題; 1b圖1簇間通信數(shù)據(jù)轉(zhuǎn)發(fā)示意 解決重復(fù)路由傳輸問(wèn)題,在簇間通信階段網(wǎng)關(guān)節(jié)點(diǎn)接收到數(shù)據(jù)后引入延時(shí)等待機(jī)制。為了實(shí)現(xiàn)各個(gè)簇采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合,從距離Sink 節(jié)點(diǎn)最遠(yuǎn)的簇首節(jié)點(diǎn)開(kāi)始,越靠近Sink 節(jié)點(diǎn)的網(wǎng)關(guān)節(jié)點(diǎn)延時(shí)越長(zhǎng)。當(dāng)網(wǎng)關(guān)節(jié)點(diǎn)延時(shí)結(jié)束后,立刻以下一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)為目的節(jié)點(diǎn),多跳傳輸數(shù)據(jù)。如圖1中,當(dāng)網(wǎng)關(guān)節(jié)點(diǎn)1a 收到距離Sink 節(jié)點(diǎn)最遠(yuǎn)的簇首節(jié)點(diǎn)A 發(fā)來(lái)的數(shù)據(jù)后,直接以網(wǎng)關(guān)節(jié)點(diǎn)1b 為目的節(jié)點(diǎn)按貪婪算法制定路由,并多跳傳輸數(shù)據(jù);而當(dāng)1b 收到

14、來(lái)自簇首B 發(fā)來(lái)的信息時(shí),則等待T (2R 時(shí)間,在此時(shí)間段中等待下級(jí)節(jié)點(diǎn)發(fā)來(lái)的數(shù)據(jù),其中R 為無(wú)線傳感器節(jié)點(diǎn)的最大通信半徑,T (2R 為數(shù)據(jù)包傳到2R 距離所需要的時(shí)間。以此類推1b 的上級(jí)網(wǎng)關(guān)節(jié)點(diǎn)1f 等待延時(shí)為2T (2R ,1e 為3T (2R ,1d 為2(2T R ,1c 為(2T R 。延時(shí)等待機(jī)制減少簇間傳輸時(shí)網(wǎng)絡(luò)路由的重復(fù)使用次數(shù),達(dá)到節(jié)約能量的目的。4 網(wǎng)絡(luò)仿真網(wǎng)絡(luò)仿真采用NS2仿真軟件,仿真環(huán)境參考相關(guān)文 獻(xiàn)8。仿真中將101個(gè)節(jié)點(diǎn)(1個(gè)Sink 節(jié)點(diǎn)隨機(jī)分布在500 m×500 m 的區(qū)域中.,節(jié)點(diǎn)的默認(rèn)通信半徑100 m,節(jié)點(diǎn)的最大傳輸半徑為500 m,節(jié)

15、點(diǎn)的初始能量為1J,傳輸功率設(shè)置為37.2e J/bit,接收功率設(shè)置為33.5e J/bit,空閑等待功率消耗為0.0025J/s,規(guī)定每10s 為一個(gè)周期,簇首節(jié)點(diǎn)向Sink 節(jié)點(diǎn)傳輸數(shù)據(jù),并忽略多跳通信時(shí)存儲(chǔ)轉(zhuǎn)發(fā)帶來(lái)的延時(shí),網(wǎng)絡(luò)分簇基于LEACH 路由協(xié)議。改進(jìn)后的簇間通信路由算法通過(guò)建立簇間網(wǎng)關(guān)節(jié)點(diǎn)間端到端的虛電路,建立了一條將數(shù)據(jù)發(fā)送到Sink 節(jié)點(diǎn)的邏輯信道。數(shù)據(jù)存儲(chǔ)轉(zhuǎn)發(fā)的路由,由具有全局路由信息的網(wǎng)關(guān)節(jié)點(diǎn)和簇首節(jié)點(diǎn)制定,減少了發(fā)生路由空洞的可能性。通過(guò)137引入延時(shí)等待機(jī)制,不但可完成簇間數(shù)據(jù)融合,而且減少了重復(fù)路由使用的次數(shù)。從圖2、圖3中可以看出,改進(jìn)后的簇間路由算法比傳統(tǒng)的

16、直接與Sink 節(jié)點(diǎn)通信和局部貪婪算法,在性能上有明顯的提升。圖2 剩余能量圖3 存活節(jié)點(diǎn)5 結(jié)語(yǔ)本文提出了一種基于分簇網(wǎng)絡(luò)的簇間路由算法的改進(jìn)方案,針對(duì)傳統(tǒng)的簇間路由算法的不足,建立了帶網(wǎng)關(guān)節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)模型,同時(shí)在網(wǎng)絡(luò)模型中引入建立了虛電路,增加了延時(shí)等待機(jī)制。本改進(jìn)算法不受無(wú)線傳感器規(guī)模限制,適用于大規(guī)模無(wú)限傳感器網(wǎng)絡(luò),并具有良好的擴(kuò)展性。參考文獻(xiàn)1 孫利民,李建中,陳渝,等.無(wú)線傳感器網(wǎng)絡(luò)M. 北京:清華大學(xué)出版社,2006.2 Holger Karl, Andreas Willig. Protocols and Architectures forWireless Sens

17、or NetworkM. 第一版,北京:電子工業(yè)出版社,2007.3 Di Wu, Gang Hu. Research and Modifications on ClusteringAlgorithm of Routing Protocols for Wireless Sensor NetworksR. 深圳: International Conference on Informatics and Control Technologies ,2006.4 郭強(qiáng),孫強(qiáng),李雪,等.無(wú)線傳感器網(wǎng)絡(luò)LEACH 協(xié)議的研究J.通信技術(shù), 2008,41(12:155-157.5 羅玥,李雷.無(wú)線傳感器網(wǎng)

18、絡(luò)路由問(wèn)題探討J.通信技術(shù),2007,40(12:361-362.6 吳迪,胡鋼.無(wú)線傳感器網(wǎng)絡(luò)多路徑簇頭鏈分簇式路由算法J.計(jì)算機(jī)工程與科學(xué),2008,30(06:101-105.7 劉志杰,張華忠,于鵬程.WSN 中能耗均衡的自組織多跳聚類協(xié)議研究J.計(jì)算機(jī)工程與應(yīng)用,2007,43(26:129-131.8 王春雷,柴喬林.基于分簇的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能路由算法J.計(jì)算機(jī)應(yīng)用, 2007,27(02:342-345.(上接第134頁(yè)服務(wù)率圖1 平均時(shí)延分析服務(wù)率圖2 丟包率分析3 結(jié)語(yǔ)聯(lián)系理論公式和仿真結(jié)果,得出:在緩沖區(qū)既定的情況下,要有效地減少平均時(shí)延和丟包率,就必須提高服務(wù)率的結(jié)論。這就為提高多媒體服務(wù)的QOS 及改善丟包現(xiàn)象提供了很好的理論依據(jù)。對(duì)于本課題而言,今后可以在以下方面加強(qiáng)與創(chuàng)新: 在各種新興的ATM 交換網(wǎng)絡(luò)的結(jié)構(gòu)以及新興的業(yè)務(wù)前提下,