WSN網(wǎng)絡(luò)中分段組播路由算法的研究

高江軍

(池州職業(yè)技術(shù)學(xué)院 信息技術(shù)系，安徽 池州 247100)

無(wú)線傳感器網(wǎng)絡(luò)，簡(jiǎn)稱WSN。它是一種由多個(gè)無(wú)線傳感設(shè)備組成的分布式傳感網(wǎng)絡(luò)，這些傳感設(shè)備可以感知和傳輸外部世界信息。WSN中的傳感器通過(guò)無(wú)線方式通信，因此網(wǎng)絡(luò)設(shè)置靈活，設(shè)備位置可以隨時(shí)更改，還可以跟互聯(lián)網(wǎng)進(jìn)行有線或無(wú)線方式的連接。通過(guò)無(wú)線通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)。由于節(jié)點(diǎn)的靈活多變，同樣也帶來(lái)了能量受限[1]、存儲(chǔ)有限[2]的問(wèn)題，在長(zhǎng)時(shí)間大范圍信息轉(zhuǎn)發(fā)的環(huán)境中，組播技術(shù)的應(yīng)用可以減少冗余發(fā)送、降低能耗，從而提升網(wǎng)絡(luò)的傳輸效率。

WSN中組播的研究有很多，主要是無(wú)狀態(tài)組播[3]和分級(jí)分層組播。無(wú)狀態(tài)組播算法的研究有GMR算法[4]和DBOM算法[5]等，GMR算法主要是將所有組播接收節(jié)點(diǎn)的位置信息都存儲(chǔ)在組播分組頭部，中間節(jié)點(diǎn)接收到組播分組后根據(jù)鄰居路由算法來(lái)進(jìn)行分組轉(zhuǎn)發(fā)。DBOM算法主要是為每個(gè)組播接收節(jié)點(diǎn)創(chuàng)建一塊接收區(qū)域，每個(gè)區(qū)域有一個(gè)中心位置，當(dāng)分組投遞時(shí)，sink節(jié)點(diǎn)先將分組投遞到所屬中心位置，再由中心位置投遞到目的節(jié)點(diǎn)，這種劃分區(qū)域的方式一定程度上防止了拓?fù)浣Y(jié)構(gòu)變化帶來(lái)的影響。對(duì)于無(wú)狀態(tài)組播算法，它的優(yōu)點(diǎn)很明顯，就是當(dāng)節(jié)點(diǎn)失效時(shí)，可以根據(jù)路由算法重新選擇路由，可以減弱網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化帶來(lái)的影響，但是它的缺點(diǎn)也很明顯，該算法要求所有組播接收節(jié)點(diǎn)都要存儲(chǔ)在根節(jié)點(diǎn)中，對(duì)于大型WSN時(shí)，過(guò)多的組播接收節(jié)點(diǎn)信息就無(wú)法被分組頭容納，出現(xiàn)網(wǎng)絡(luò)的擴(kuò)展性問(wèn)題。

分級(jí)分層組播路由算法主要是適用大規(guī)模WSN網(wǎng)絡(luò)，解決網(wǎng)絡(luò)擴(kuò)展性問(wèn)題，目前研究的算法主要有HGMR[6]和MRBIN[7]，HGMR算法將網(wǎng)絡(luò)分成多個(gè)一定大小的子樹，每個(gè)子樹通過(guò)地理算法[8]選舉一個(gè)簇頭來(lái)管理各個(gè)子樹節(jié)點(diǎn)，sink節(jié)點(diǎn)將分組投遞給各簇頭，再由簇頭將分組投遞到各個(gè)組播接收節(jié)點(diǎn),雖然通過(guò)分簇的方式解決了分組頭的大小問(wèn)題，但是簇頭要接收所有分組，并進(jìn)行大量的路由轉(zhuǎn)發(fā)，造成簇頭能量的快速耗盡。MRBIN算法在組播樹上的每個(gè)分支節(jié)點(diǎn)上存儲(chǔ)其下各分支節(jié)點(diǎn)的首末節(jié)點(diǎn)位置信息，每個(gè)分支節(jié)點(diǎn)只負(fù)責(zé)和其下分支節(jié)點(diǎn)的分組傳遞，這種分支傳遞的方式減少了匯聚節(jié)點(diǎn)路由能耗過(guò)快的影響，但是每個(gè)分支依然要轉(zhuǎn)發(fā)所有的分組，如果其下分支節(jié)點(diǎn)太多，依然會(huì)造成節(jié)點(diǎn)能量消耗殆盡。

綜合以上組播路由算法存在的問(wèn)題，本文提出了一種分類分級(jí)組播路由算法(Classification hierarchical multicast routing algorithm，CHMR)。該算法首先是將組播樹按照規(guī)定的節(jié)點(diǎn)數(shù)量分成多個(gè)組播子樹，組播子樹的根節(jié)點(diǎn)存儲(chǔ)該子樹的分支節(jié)點(diǎn)和末梢節(jié)點(diǎn)的位置信息和父子關(guān)系，通過(guò)這種方式可以減小分組頭長(zhǎng)度同時(shí)盡量降低單點(diǎn)失效[9]的可能性。

1 網(wǎng)絡(luò)模型構(gòu)建

(1)假定WSN網(wǎng)中的節(jié)點(diǎn)具有相同的結(jié)構(gòu)和能量，并且能量是受限的。

(2)假定節(jié)點(diǎn)在特定的定位機(jī)制[10]下可獲知其他節(jié)點(diǎn)的地理位置信息。

(3)假定分組可以通過(guò)地理路由到達(dá)目的節(jié)點(diǎn)。

(4)假定組播子樹中節(jié)點(diǎn)可以分成存儲(chǔ)節(jié)點(diǎn)、分支節(jié)點(diǎn)、轉(zhuǎn)發(fā)節(jié)點(diǎn)、末梢節(jié)點(diǎn)四類。存儲(chǔ)節(jié)點(diǎn)為組播子樹的根節(jié)點(diǎn)，存放子樹的路由信息，分支節(jié)點(diǎn)為分組多路轉(zhuǎn)發(fā)經(jīng)過(guò)的非葉節(jié)點(diǎn)，轉(zhuǎn)發(fā)節(jié)點(diǎn)為分支節(jié)點(diǎn)間單播分組轉(zhuǎn)發(fā)的節(jié)點(diǎn)，末梢節(jié)點(diǎn)即子樹的葉節(jié)點(diǎn)。

(5)本文使用無(wú)線傳輸一階射頻能量模型[11]，節(jié)點(diǎn)傳輸一個(gè)分組的能耗表示為Et，接收分組的能耗表示為Er，其他能耗忽略，分組長(zhǎng)度用l表示，射頻傳送距離r,射頻收發(fā)能耗常量Ee,射頻放大器能耗常量e，則有：

Et=1Ee+1er2

(1)

Er=1Ee

(2)

節(jié)點(diǎn)收發(fā)一次分組的總能耗為：

Ea=Et+Er=2lEe+1er2

(3)

2 CHMR算法描述

2.1 選取存儲(chǔ)節(jié)點(diǎn)的具體方法

上述研究中，存儲(chǔ)節(jié)點(diǎn)是用來(lái)存放子樹分支節(jié)點(diǎn)、末梢節(jié)點(diǎn)的位置信息和父子關(guān)系信息。分組投遞的目的節(jié)點(diǎn)包括分支節(jié)點(diǎn)和末梢節(jié)點(diǎn)，而且子樹內(nèi)使用無(wú)狀態(tài)轉(zhuǎn)發(fā)，分組頭部?jī)?nèi)需要存儲(chǔ)所有末梢節(jié)點(diǎn)和分支節(jié)點(diǎn)的位置信息，因此要控制各子樹的規(guī)模。具體方法如下：首先，需要一個(gè)計(jì)數(shù)器Ki來(lái)計(jì)算機(jī)子樹內(nèi)節(jié)點(diǎn)數(shù)量和一個(gè)最大目的節(jié)點(diǎn)數(shù)kmax，當(dāng)Kmax≤Ki,節(jié)點(diǎn)i才可以成為存儲(chǔ)節(jié)點(diǎn)。

組播目的節(jié)點(diǎn)向sink節(jié)點(diǎn)申請(qǐng)加入組播組時(shí)，先置Ki=0，并將Ki和目的節(jié)點(diǎn)位置信息加入組請(qǐng)求中，請(qǐng)求數(shù)用n表示，節(jié)點(diǎn)i獲得下方n≥2請(qǐng)求時(shí)，i節(jié)點(diǎn)成為分支節(jié)點(diǎn)，并計(jì)算自己的Ki值，即

(4)

(1)當(dāng)Kmax

(2)當(dāng)Kmax=Ki時(shí)，i節(jié)點(diǎn)成為存儲(chǔ)節(jié)點(diǎn)，置Ki=0,m值不變，繼續(xù)向sink發(fā)送。

(3)當(dāng)Kmax>Ki時(shí)，i節(jié)點(diǎn)從其下Ki≤Kmax分支節(jié)點(diǎn)中選擇值最大作為存儲(chǔ)節(jié)點(diǎn)，定義為x節(jié)點(diǎn)，如果有多個(gè)值相等的都可以選擇為存儲(chǔ)節(jié)點(diǎn)，并執(zhí)行一下操作：

(5)

(4)如圖1，該組播樹只顯示了sink節(jié)點(diǎn)、分支節(jié)點(diǎn)和末梢節(jié)點(diǎn)，假定Kmax=4，根據(jù)算法計(jì)算出了各節(jié)點(diǎn)的Ki值，由于節(jié)點(diǎn)1和3值為5>4,只能選擇節(jié)點(diǎn)9和節(jié)點(diǎn)3作為存儲(chǔ)節(jié)點(diǎn)，而節(jié)點(diǎn)2的值剛好為4，所以節(jié)點(diǎn)2即為存儲(chǔ)節(jié)點(diǎn)。

圖1存儲(chǔ)節(jié)點(diǎn)的選取過(guò)程圖2組播分組的轉(zhuǎn)發(fā)過(guò)程

2.2 組播分組的分段轉(zhuǎn)發(fā)過(guò)程

如圖2，A、B、C、D為轉(zhuǎn)發(fā)節(jié)點(diǎn)，2、3、9為存儲(chǔ)節(jié)點(diǎn)，1、6為分支節(jié)點(diǎn)，具體轉(zhuǎn)發(fā)過(guò)程如下(只畫出右側(cè)的轉(zhuǎn)發(fā)節(jié)點(diǎn)):

sink節(jié)點(diǎn)將其存儲(chǔ)的子樹節(jié)點(diǎn)(1(3,4),2)加入到組播分組的頭部中向下通過(guò)地理路由，經(jīng)A、B節(jié)點(diǎn)無(wú)狀態(tài)轉(zhuǎn)發(fā)到節(jié)點(diǎn)1、2，節(jié)點(diǎn)2收到分組時(shí)，由于節(jié)點(diǎn)2是存儲(chǔ)節(jié)點(diǎn)，將分組頭替換成(5,6(10,11))，提取出下級(jí)目的節(jié)點(diǎn)5、6，通過(guò)C、D使用地理路由轉(zhuǎn)發(fā)到5、6,6節(jié)點(diǎn)收到分組繼續(xù)轉(zhuǎn)發(fā)到末梢節(jié)點(diǎn)10、11。同理，節(jié)點(diǎn)1收到分組轉(zhuǎn)發(fā)到3、4節(jié)點(diǎn)，由于3是存儲(chǔ)節(jié)點(diǎn)，分組頭替換成(7，8,9)，分組到達(dá)節(jié)點(diǎn)9，分組頭又替換成(12,13)，最終完成所有節(jié)點(diǎn)的轉(zhuǎn)發(fā)，該轉(zhuǎn)發(fā)過(guò)程很清楚地顯示出分組頭通過(guò)多次的替換，大大減少了分組頭的大小，在大規(guī)模網(wǎng)絡(luò)中可以很好提高擴(kuò)展性。

3 仿真比較

3.1 參數(shù)設(shè)置

仿真環(huán)境：在50×50m2的正方形區(qū)域內(nèi)均勻分布無(wú)線傳感器節(jié)點(diǎn)。

3.1.1 常量設(shè)置 射頻傳送距離r=5m；數(shù)據(jù)傳輸速率v=400bits/s；組播分組有效數(shù)據(jù)長(zhǎng)度la=400bits；節(jié)點(diǎn)初始能量Et=100000μJ；射頻收發(fā)能耗常量Ee=50nJ/bits；射頻放大器常量e=100pJ/b/m2

3.1.2 網(wǎng)絡(luò)密度設(shè)置 節(jié)點(diǎn)射頻傳送范圍r內(nèi)所包含的鄰居節(jié)點(diǎn)的個(gè)數(shù)的平均值,設(shè)為ρ，設(shè)置傳感器所分布的區(qū)域面積為s，分布節(jié)點(diǎn)的數(shù)量為n，則有：

(6)

3.1.3 節(jié)點(diǎn)轉(zhuǎn)發(fā)分組能耗設(shè)置 假定分組頭長(zhǎng)度為lh，根據(jù)公式3得出，節(jié)點(diǎn)轉(zhuǎn)發(fā)一次分組的能耗為Ea=2lEe+ ler2=l(2Ee+ er2)=102.5×(400+ lh),可以看出相同參數(shù)下轉(zhuǎn)發(fā)分組的能耗取決于分組頭長(zhǎng)度。

3.1.4 仿真節(jié)點(diǎn)數(shù)量設(shè)置 下文的仿真比較主要從擴(kuò)展性和吞吐量?jī)煞矫孢M(jìn)行比較，設(shè)定Kmax=10,網(wǎng)絡(luò)密度ρ=10,每個(gè)仿真重復(fù)500次，隨機(jī)分布節(jié)點(diǎn)，平均值顯示結(jié)果，并通過(guò)與無(wú)狀態(tài)組播HGMR、分支組播MRBIN方案對(duì)比。

3.2 擴(kuò)展性比較

擴(kuò)展性即能耗隨接收節(jié)點(diǎn)數(shù)量變化情況，綜上所述，能耗取決于分組頭的長(zhǎng)度，因此可以通過(guò)觀察分組頭長(zhǎng)度隨接收節(jié)點(diǎn)數(shù)量變化情況，見圖3。

圖3擴(kuò)張性的比較圖4吞吐量的變化

從圖3可以明顯看出，當(dāng)有效數(shù)據(jù)長(zhǎng)度相同時(shí)，HGMR的分組長(zhǎng)度隨著目的節(jié)點(diǎn)的增多，組播分組的長(zhǎng)度不斷地增大，由于分組頭長(zhǎng)度是有限的，當(dāng)網(wǎng)絡(luò)規(guī)模增加到一定程度而分組頭無(wú)法容納時(shí)，擴(kuò)展性就非常差。MRBIN和CHMR算法下的分組長(zhǎng)度一直保持在一定的大小，擴(kuò)展性很好。

3.3 吞吐量的比較

網(wǎng)絡(luò)吞吐量即生存時(shí)間內(nèi)傳輸有效數(shù)據(jù)的總量，生存時(shí)間內(nèi)，傳輸?shù)臄?shù)據(jù)量越大，則吞吐量越大，網(wǎng)絡(luò)的綜合性能就越好，見圖4。

從圖4可以看出，MRBIN算法的吞吐量一直維持在一定的水平，但是HGMR和CHMR的吞吐量開始處在一個(gè)較高的水平，但是隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，吞吐量在不斷下降，HGMR的下降趨勢(shì)比較快，改進(jìn)的算法CHMR由于控制了有效數(shù)據(jù)的量，下降趨勢(shì)則相對(duì)要緩慢一些。

綜合上述兩項(xiàng)比較，可以得出，CHMR的算法在擴(kuò)展性和吞吐量的綜合性能上，相比較無(wú)狀態(tài)組播和分支組播上有了一定性能的提升。

4 結(jié)束語(yǔ)

本文主要針對(duì)大規(guī)模無(wú)線傳感網(wǎng)而展開的組播研究，通過(guò)分析多種組播路由算法，找出無(wú)狀態(tài)組播和分支組播當(dāng)中存在的分組頭長(zhǎng)度和節(jié)點(diǎn)路由轉(zhuǎn)發(fā)負(fù)載過(guò)大的問(wèn)題，結(jié)合地理路由和WSN的網(wǎng)絡(luò)特性，提出一種基于存儲(chǔ)空間控制和路由分段的CHMR算法，通過(guò)對(duì)該算法的各節(jié)點(diǎn)的分類描述以及存儲(chǔ)節(jié)點(diǎn)選取方法進(jìn)行設(shè)計(jì)，最終將該算法在仿真環(huán)境下進(jìn)行實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果以圖表的形式和其他組播路由算法在擴(kuò)展性和吞吐量上進(jìn)行比較，得出CHMR算法在大規(guī)模WSN網(wǎng)絡(luò)數(shù)據(jù)傳輸性能提升上有一定的效果。