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

高江軍

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

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

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

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

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

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

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

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

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

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

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

Et=1Ee+1er2

(1)

Er=1Ee

(2)

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

Ea=Et+Er=2lEe+1er2

(3)

2 CHMR算法描述

2.1 選取存儲節(jié)點的具體方法

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

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

(4)

(1)當(dāng)Kmax

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

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

(5)

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

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

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

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

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

3 仿真比較

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

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

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

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

(6)

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

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

3.2 擴(kuò)展性比較

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

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

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

3.3 吞吐量的比較

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

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

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

4 結(jié)束語

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