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

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

2、簇間信息的融合度,此算法適用于大規(guī)模無線傳感器網(wǎng)絡(luò),有良好的可擴(kuò)展性。仿真表明在能量節(jié)省等性能上與傳統(tǒng)簇間路由算法相較有較大提高?！娟P(guān)鍵詞】無線傳感器網(wǎng)絡(luò);網(wǎng)關(guān)節(jié)點(diǎn)模型;簇;簇間路由【中圖分類號】TN92 【文獻(xiàn)標(biāo)識碼】A【文章編號】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ǎng)絡(luò)1-3集成了傳感器技術(shù)、嵌入式計算技術(shù)、無線通信技術(shù)以及分布式信息處理技術(shù)4。無線傳感器網(wǎng)絡(luò)是其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對象的信息,并發(fā)送給觀察者。預(yù)設(shè)監(jiān)測區(qū)域內(nèi)大量傳感器節(jié)點(diǎn)通過自組織的

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

8、通信會使節(jié)點(diǎn)能量迅速損耗,距離Sink節(jié)點(diǎn)較遠(yuǎn)的簇首節(jié)點(diǎn)會很快死亡,從而降低了網(wǎng)絡(luò)的連通性和減少了網(wǎng)絡(luò)的生存周期。(2多跳通信6-7收稿日期:2008-11-06?；痦?xiàng)目:中國水利水電科學(xué)研究院開放研究基金資助(水科科技便函2008010號。作者簡介:朱佳奇(1984-,男,碩士研究生,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò);胡鋼(1958-,男,教授,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò);陳世志(1984-,男,碩士研究生,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。135136 分簇網(wǎng)絡(luò)中各簇的簇首節(jié)點(diǎn)通過多跳方式存儲轉(zhuǎn)發(fā)數(shù)據(jù),向相鄰簇的簇首節(jié)點(diǎn)發(fā)送數(shù)據(jù),通過相鄰簇的簇首節(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)的大量能量,能很好的減少各個簇首在簇間通信時的能量損耗。但是通過簇首轉(zhuǎn)發(fā)數(shù)據(jù)選擇的路徑并不一定是最優(yōu)路徑,簇間通信的能量損耗并不一定最小。2 網(wǎng)絡(luò)模型提出無線傳感器網(wǎng)絡(luò)可以用無向圖來表示:G =(V ,E 。V 表示傳感器節(jié)點(diǎn)的集合,E 表示無線雙向通信鏈路的集合。對于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ò)分簇的過程中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),也就是說在分簇過程中節(jié)點(diǎn)s 同時收到簇首節(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é)點(diǎn)作為下一跳節(jié)點(diǎn)。但是由于節(jié)點(diǎn)只知道局部拓?fù)湫畔?會遇到路由空洞1-2的問題和重復(fù)路徑傳輸問題,反而增加了能量的消耗。算法將重點(diǎn)解決以上問題。 無線傳感器網(wǎng)絡(luò)按照分簇算法進(jìn)行分簇,確定各個簇的簇首節(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)對向它發(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)傳輸信息。在此傳輸過程中,將自己的剩余能量和地理位置坐標(biāo)一并傳

12、輸給簇首節(jié)點(diǎn); 各簇首節(jié)點(diǎn)收到簇內(nèi)成員節(jié)點(diǎn)的剩余能量后,計算其平均值作為該簇的平均能量;之后,簇首節(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)的等待時序。如圖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)制定的,所以可以避免貪婪算法帶來的路 由空洞的問題; 1b圖1簇間通信數(shù)據(jù)轉(zhuǎn)發(fā)示意 解決重復(fù)路由傳輸問題,在簇間通信階段網(wǎng)關(guān)節(jié)點(diǎn)接收到數(shù)據(jù)后引入延時等待機(jī)制。為了實(shí)現(xiàn)各個簇采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合,從距離Sink 節(jié)點(diǎn)最遠(yuǎn)的簇首節(jié)點(diǎn)開始,越靠近Sink 節(jié)點(diǎn)的網(wǎng)關(guān)節(jié)點(diǎn)延時越長。當(dāng)網(wǎng)關(guān)節(jié)點(diǎn)延時結(jié)束后,立刻以下一個網(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ā)來的數(shù)據(jù)后,直接以網(wǎng)關(guān)節(jié)點(diǎn)1b 為目的節(jié)點(diǎn)按貪婪算法制定路由,并多跳傳輸數(shù)據(jù);而當(dāng)1b 收到

14、來自簇首B 發(fā)來的信息時,則等待T (2R 時間,在此時間段中等待下級節(jié)點(diǎn)發(fā)來的數(shù)據(jù),其中R 為無線傳感器節(jié)點(diǎn)的最大通信半徑,T (2R 為數(shù)據(jù)包傳到2R 距離所需要的時間。以此類推1b 的上級網(wǎng)關(guān)節(jié)點(diǎn)1f 等待延時為2T (2R ,1e 為3T (2R ,1d 為2(2T R ,1c 為(2T R 。延時等待機(jī)制減少簇間傳輸時網(wǎng)絡(luò)路由的重復(fù)使用次數(shù),達(dá)到節(jié)約能量的目的。4 網(wǎng)絡(luò)仿真網(wǎng)絡(luò)仿真采用NS2仿真軟件,仿真環(huán)境參考相關(guān)文 獻(xiàn)8。仿真中將101個節(jié)點(diǎn)(1個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 為一個周期,簇首節(jié)點(diǎn)向Sink 節(jié)點(diǎn)傳輸數(shù)據(jù),并忽略多跳通信時存儲轉(zhuǎn)發(fā)帶來的延時,網(wǎng)絡(luò)分簇基于LEACH 路由協(xié)議。改進(jìn)后的簇間通信路由算法通過建立簇間網(wǎng)關(guān)節(jié)點(diǎn)間端到端的虛電路,建立了一條將數(shù)據(jù)發(fā)送到Sink 節(jié)點(diǎn)的邏輯信道。數(shù)據(jù)存儲轉(zhuǎn)發(fā)的路由,由具有全局路由信息的網(wǎng)關(guān)節(jié)點(diǎn)和簇首節(jié)點(diǎn)制定,減少了發(fā)生路由空洞的可能性。通過137引入延時等待機(jī)制,不但可完成簇間數(shù)據(jù)融合,而且減少了重復(fù)路由使用的次數(shù)。從圖2、圖3中可以看出,改進(jìn)后的簇間路由算法比傳統(tǒng)的

16、直接與Sink 節(jié)點(diǎn)通信和局部貪婪算法,在性能上有明顯的提升。圖2 剩余能量圖3 存活節(jié)點(diǎn)5 結(jié)語本文提出了一種基于分簇網(wǎng)絡(luò)的簇間路由算法的改進(jìn)方案,針對傳統(tǒng)的簇間路由算法的不足,建立了帶網(wǎng)關(guān)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)模型,同時在網(wǎng)絡(luò)模型中引入建立了虛電路,增加了延時等待機(jī)制。本改進(jìn)算法不受無線傳感器規(guī)模限制,適用于大規(guī)模無限傳感器網(wǎng)絡(luò),并具有良好的擴(kuò)展性。參考文獻(xiàn)1 孫利民,李建中,陳渝,等.無線傳感器網(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ǎng)絡(luò)LEACH 協(xié)議的研究J.通信技術(shù), 2008,41(12:155-157.5 羅玥,李雷.無線傳感器網(wǎng)

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