黃 曼,程良倫
(廣東工業(yè)大學自動化學院,廣州 510006)
隨著無線網(wǎng)絡技術的突破以及因特網(wǎng)業(yè)務的飛速發(fā)展,人們對通信業(yè)務的需求不再是單純的語音通話,越來越多地傾向于圖像、音頻、視頻等復雜的混合業(yè)務,迫切需要將信息豐富的多媒體技術引入到無線傳感器網(wǎng)絡中,因此無線多媒體傳感器網(wǎng)絡(Wireless Multiple Sensor Networks,WMSNs)應運而生[1]。但是,目前的無線傳感器網(wǎng)絡仍存在嚴重的能量受限、帶寬資源約束、鏈路不穩(wěn)定、以及節(jié)點處理能力不夠強大等問題,而多媒體數(shù)據(jù)的傳輸需要網(wǎng)絡具有更強的媒體傳輸能力,能否有效解決多媒體數(shù)據(jù)實時的傳輸問題,是 WMSNs實用化的關鍵[2]。
無線多媒體傳感器網(wǎng)絡傳送的信息中包含實時的圖像、音頻或視頻等多媒體信息,必須提供一定的服務質(zhì)量(QoS)保證。QoS是網(wǎng)絡將用戶數(shù)據(jù)從源端傳到目的端的過程中必須滿足的一系列的服務要求,包括可用性、吞吐量、時延、時延抖動、丟包率、能耗等參數(shù)[3]。無線多媒體傳感器網(wǎng)絡中,不同數(shù)據(jù)包重要性差別很大,應該為不同應用提供不同的QoS支持。目前支持QoS的路由協(xié)議可以分為非跨層協(xié)議和跨層協(xié)議。如 ACOGA[4]、TMQODR[5]、SPEED[6]均為非跨層協(xié)議。ACOGA協(xié)議結(jié)合了ACO和 GAS兩個算法,實現(xiàn)了動態(tài) QoS路由。TMQODR協(xié)議具有QoS選路功能,根據(jù)業(yè)務流的QoS偏好選擇最合適的路徑,體現(xiàn)了區(qū)分服務的思想。但是這兩個協(xié)議均未考慮網(wǎng)絡的能量有效性問題??鐚訁f(xié)議有 QSAP[7]、QBDSR[8]等。QSAP 協(xié)議是在多天線系統(tǒng)中,根據(jù)數(shù)據(jù)流的大小來自適應地調(diào)節(jié)天線陣列,產(chǎn)生相應數(shù)量的空間信道,從而達到QoS中的能耗要求。QBDSR協(xié)議將QoS策略、延時、丟包率、帶寬等參數(shù)加到RREQ包的包頭,節(jié)點可以根據(jù)這些信息選擇路由。跨層路由協(xié)議相對于非跨層協(xié)議,在節(jié)點物理結(jié)構(gòu)和路由機制上的復雜性都有所增加,但是性能較好。
本文在研究SPEED協(xié)議的基礎上,改善設計了一種QoS保證的無線多媒體傳感器網(wǎng)絡實時路由協(xié)議(WMSNRR),主要保證QoS的實時性要求,在實時性和能量成本之間進行有效折衷。該協(xié)議在路由發(fā)現(xiàn)過程中,充分考慮兩跳鄰居節(jié)點的剩余能量,避免“速率空洞”和“路由空洞”。同時,采用一種基于緩存隊列長度和節(jié)點收發(fā)數(shù)據(jù)率的控制方法,對不同業(yè)務進行區(qū)分擁塞控制。該協(xié)議在能量有效性和數(shù)據(jù)實時傳輸性方面比SPEED協(xié)議有所提高,更適合無線多媒體傳感器網(wǎng)絡。
SPEED協(xié)議[6]是一個實時路由協(xié)議。在一定程度上實現(xiàn)了端到端的傳輸速率保證、網(wǎng)絡擁塞控制以及負載平衡機制。SPEED協(xié)議首先交換節(jié)點的傳輸延遲,以得到網(wǎng)絡負載情況,并判斷網(wǎng)絡是否發(fā)生擁塞。然后節(jié)點利用局部地理位置信息和傳輸速率信息作出路由決策。當SNGF路由協(xié)議找不到滿足傳輸速率的下一跳節(jié)點時,則通過鄰居反饋機制(neighborhood feedback loop,NFL)保證網(wǎng)絡傳輸速率在一個全局定義的傳輸速率閾值之上。同時,SPEED協(xié)議還通過反向壓力路由變更機制來避免擁塞和路由空洞,使節(jié)點重新選擇合適的下一跳路由。
SPEED協(xié)議主要由以下四部分組成:
(1)延遲估計機制。延遲估計機制是用來得到網(wǎng)絡的負載情況,判斷網(wǎng)絡是否發(fā)生擁塞。將單跳延時來近似模擬當前節(jié)點負載情況,而延遲主要分為兩部分,包括廣播延遲和單播延遲。通常使用單播數(shù)據(jù)包的延時來決定下一跳節(jié)點的選擇。單播數(shù)據(jù)包的延時是指發(fā)送節(jié)點將數(shù)據(jù)分組加上時間戳后發(fā)送給鄰居接收節(jié)點,鄰居節(jié)點記錄收到數(shù)據(jù)分組到發(fā)出ACK的時間間隔,并將其作為一個字段加入ACK報文。發(fā)送節(jié)點接收到ACK報文后,從收發(fā)時間中減去接收節(jié)點的處理時間。由于數(shù)據(jù)包在空中傳播的時間很短,因此將其忽略不計。延時計算公式為:
式(1)中,α(0<α<1)為當前延時的權重,用來權衡當前測得的延時和前一時刻的延時的比重,從而求得當前的平均延時。
(2)SNGF協(xié)議。SNGF協(xié)議用來選擇滿足傳輸速率要求的下一跳節(jié)點。該協(xié)議將下一跳候選節(jié)點分為兩組,第一組中節(jié)點的轉(zhuǎn)播速度大于給定的轉(zhuǎn)播速度Ssetpoint,第二組中節(jié)點的轉(zhuǎn)播速度則小于給定的轉(zhuǎn)播速度Ssetpoint。Ssetpoint依賴于應用層的QoS要求以及節(jié)點自身的通訊能力,其范圍為:
式(2)中,R為節(jié)點的有效通訊半徑,T為網(wǎng)絡帶寬,L為數(shù)據(jù)包長。
在選擇下一跳節(jié)點時,通常使用第一組中的節(jié)點作為候選節(jié)點。選擇節(jié)點j(j為第一組中的節(jié)點)的概率為:
式(3)中,Speedj為節(jié)點j的轉(zhuǎn)播速度,k為節(jié)點負載和傳輸延遲的折衷系數(shù)。K值越大,端到端的延遲越小。
(3)鄰居反饋策略。鄰居反饋策略是當SNGF路由協(xié)議中找不到滿足傳輸速率的下一跳節(jié)點時采取的補償機制。定義當傳輸一個數(shù)據(jù)包給鄰居節(jié)點的速率小于給定的轉(zhuǎn)播速度Ssetpoint,或者是由于碰撞造成的數(shù)據(jù)丟失為鄰居節(jié)點丟失率。數(shù)據(jù)鏈路層將鄰居節(jié)點丟失率信息反饋給轉(zhuǎn)播率控制器,由轉(zhuǎn)播率控制器給出決策。
(4)反向壓力路由變更機制。反向壓力路由變更機制用來避免擁塞和路由空洞。當某個局部的節(jié)點負載較重時,該局部節(jié)點的候選節(jié)點也將進行標記,在路由選擇時,這些節(jié)點與負載較重的節(jié)點一樣,不作為路由的被選節(jié)點,從而減小擁塞度。
(1)SPEED協(xié)議在路由發(fā)現(xiàn)時,只考慮了節(jié)點的實時轉(zhuǎn)播速度,并沒有考慮到節(jié)點的剩余能量問題。在選擇下一跳節(jié)點時,通常只選擇轉(zhuǎn)播速度大于給定的轉(zhuǎn)播速度Ssetpoint的節(jié)點作為候選節(jié)點。這樣容易使得某些轉(zhuǎn)播速度較大的節(jié)點被選擇為傳播節(jié)點的次數(shù)較多,能量消耗過快,從而過早死亡,引起網(wǎng)絡拓撲變化。
(2)SPEED協(xié)議在選擇下一跳節(jié)點時,只考慮數(shù)據(jù)從當前節(jié)點傳輸?shù)较乱惶?jié)點的速率大小。采用這種方式可能存在下面的這種情況:下一跳節(jié)點的鄰居節(jié)點集中所有的節(jié)點的數(shù)據(jù)傳輸速率非常小,小到幾乎為零時,就會出現(xiàn)“速率空洞”現(xiàn)象。
(3)SPEED協(xié)議在出現(xiàn)擁塞現(xiàn)象時,使用反向壓力信標消息向上一跳節(jié)點報告擁塞,上一跳節(jié)點在路由時盡量避開出現(xiàn)擁塞的節(jié)點,另辟路徑。但是由于多媒體傳感器網(wǎng)絡主要針對的是大數(shù)據(jù)量、復雜媒體信息的獲取、處理和傳輸,需要對用戶的需求業(yè)務進行區(qū)分。因此,SPEED中的反向壓力變更機制并不能完全直接應用到無線多媒體傳感器網(wǎng)絡中。
考慮一個隨機部署的多媒體傳感器節(jié)點形成的網(wǎng)絡,多媒體傳感器節(jié)點隨機部署在監(jiān)測區(qū)域內(nèi),其采集的數(shù)據(jù)沿著其他多媒體傳感器節(jié)點逐跳進行傳輸,經(jīng)過多跳路由傳送到匯聚節(jié)點,最后通過Internet網(wǎng)絡或通信衛(wèi)星到達控制中心。假設:①匯聚節(jié)點位于一個方形觀測區(qū)域的外側(cè),節(jié)點和匯聚點部署后均不再移動;②所有節(jié)點同構(gòu),每個節(jié)點都有一個唯一的標識;③節(jié)點已知自己和匯聚節(jié)點的地理位置信息。
傳感器節(jié)點的絕大部分能量消耗在無線通信模塊,為了減少節(jié)點的通信能量消耗,WMSNRR協(xié)議在路由轉(zhuǎn)發(fā)策略中考慮兩跳鄰居節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)速率、剩余能量、地理位置等信息。除此之外,采用一種基于緩存隊列長度和節(jié)點收發(fā)數(shù)據(jù)率的擁塞控制方法。該協(xié)議在能量有效性和數(shù)據(jù)實時傳輸性方面比SPEED協(xié)議有所提高。
定義1節(jié)點物理距離:節(jié)點間的實際直線距離。
定義2鄰居節(jié)點:在節(jié)點i有效通信范圍內(nèi),且到目的節(jié)點Sink的物理距離小于節(jié)點i到Sink的物理距離。
為滿足WMSNs的特殊要求,WMSNRR協(xié)議主要在SPEED協(xié)議的路由決策和擁塞控制兩個方面進行改善。
2.3.1 路由決策
WMSNRR協(xié)議在路由決策時仍先進行延遲估計,但是路由決策時不再只是將轉(zhuǎn)播速率作為唯一的參考標準。而是綜合考慮兩跳節(jié)點的數(shù)據(jù)轉(zhuǎn)播速率、剩余能量,地理位置等方面。在尋找路由時,節(jié)點i首先廣播一個探測包,探測包包含該節(jié)點自身的位置信息和需要轉(zhuǎn)播的數(shù)據(jù)包的大小等,然后等待其鄰居節(jié)點的回復信息。回復信息包括每個鄰居節(jié)點的ID號、剩余能量、延時、地理位置等。
假設當前節(jié)點為i,目的節(jié)點為s,節(jié)點i的一跳鄰居節(jié)點j。dis為節(jié)點i到目的節(jié)點為s的物理距離,djs為節(jié)點j到目的節(jié)點的物理距離。節(jié)點j的轉(zhuǎn)播速率Speedj可表示為:
式(4)中,Delayij為節(jié)點i和節(jié)點j之間的單跳延遲估計值。在Speed協(xié)議中,根據(jù)式(4)中的速率值來計算選擇節(jié)點j作為下一跳的概率。Speedj越大,選擇節(jié)點j的概率越大。但是,可能存在這種情況:節(jié)點j的轉(zhuǎn)播速率很大,因此選擇節(jié)點j作為下一跳節(jié)點。而節(jié)點j的所有鄰居節(jié)點鏈路質(zhì)量較差或者擁塞較嚴重,這時將沒有滿足節(jié)點j要求的下一跳節(jié)點,會出現(xiàn)較嚴重的延時。
因此本文考慮兩跳節(jié)點的速率信息,即考慮節(jié)點j轉(zhuǎn)播速率的同時,還考慮節(jié)點j的鄰居節(jié)點k的轉(zhuǎn)播速率。與式(4)原理相同,節(jié)點k的轉(zhuǎn)播速率為:
如果節(jié)點j和節(jié)點k的單跳延時一直處于較小狀態(tài),節(jié)點j和節(jié)點k可能一直被選擇為轉(zhuǎn)播節(jié)點。同時,如果轉(zhuǎn)播的數(shù)據(jù)量較大,節(jié)點j和節(jié)點k攜帶的能量將很快被消耗完,處于死亡狀態(tài),甚至引起路由“空洞”。在延時參數(shù)限度內(nèi),當數(shù)據(jù)包數(shù)量較大時,不必要每次都選擇最大速度,可以對能耗和延時兩個參數(shù)進行折衷考慮。因此,選擇節(jié)點j作為下一跳時,不僅要考慮節(jié)點j自身的轉(zhuǎn)播速率、節(jié)點j的下一跳節(jié)點k的轉(zhuǎn)播速率,同時還要考慮節(jié)點j、k的剩余能量。選擇節(jié)點j的度量標準如下:
式(6)中,cj為選擇節(jié)點j作為下一跳的度量標準。w1為節(jié)點j的速率權重,w2為節(jié)點k的的速率權重,w1、w2滿足:w1+w2=1,且w1>w2。由于在第一跳鄰居節(jié)點轉(zhuǎn)播數(shù)據(jù)時間段內(nèi),第二跳鄰居節(jié)點可能出現(xiàn)被其它節(jié)點提前占用、或者自身感知到事件發(fā)生需要發(fā)送數(shù)據(jù)等新任務,導致節(jié)點轉(zhuǎn)播速率降低,所以通常選擇第一跳鄰居節(jié)點的權重較大。Speedj、Speedk分別是通過式(4)、式(5)計算出來的節(jié)點j和節(jié)點k的轉(zhuǎn)播速率。Ej、Ek分別是節(jié)點j和節(jié)點k的剩余能量。α和β可以調(diào)整節(jié)點的剩余能量在節(jié)點度量標準函數(shù)中的比重。當業(yè)務對延時要求非常高時,α和β值應調(diào)整到很小。反之,α和β值較大時,網(wǎng)絡節(jié)點的能量消耗較均勻,出現(xiàn)路由空洞的情況減少。
節(jié)點j被選擇為下一跳節(jié)點的概率為:
式(7)中,Nj為鄰居節(jié)點集。k為節(jié)點負載和傳輸延遲的折衷系數(shù)。
圖1中,A為源節(jié)點,F(xiàn)為Sink節(jié)點,B、D為節(jié)點A的下一跳鄰居節(jié)點,節(jié)點C為節(jié)點B的鄰居節(jié)點,節(jié)點E為節(jié)點D的鄰居節(jié)點。根據(jù)上述路由機制,出現(xiàn)圖(1)所示的網(wǎng)絡狀況時,節(jié)點 B、C、D、E的轉(zhuǎn)播速率分別為:
取w1=0.6,w2=0.4,α、β 和k均為 0.5。計算得:
節(jié)點B和節(jié)點 D分別將以0.43和0.57的概率被選擇為下一跳節(jié)點。
圖1 基于兩跳節(jié)點信息的路由
2.3.2 擁塞控制
擁塞導致的數(shù)據(jù)多次重傳,不僅使得網(wǎng)絡傳輸能力的下降,同時增加了網(wǎng)絡流量和節(jié)點的能耗[9]。因此,有效的擁塞控制策略是系統(tǒng)節(jié)能和減少延時的一個重要因素。相對于普通無線傳感器網(wǎng)絡而言,多媒體傳感器網(wǎng)絡由于其需要對大數(shù)據(jù)量、復雜媒體信息的獲取、處理和傳輸?shù)忍厥庑?,對網(wǎng)絡擁塞控制的要求更加嚴格[10-11]。
本文采用了一種基于緩存隊列長度和節(jié)點收發(fā)數(shù)據(jù)率的擁塞控制方法。該方法使用的前提是數(shù)據(jù)在發(fā)送之前,需要根據(jù)用戶需求進行優(yōu)先級劃分,優(yōu)先級按照實時性到非實時性依次遞減。采用文獻[12]中的反饋機制,通過調(diào)整不同優(yōu)先級數(shù)據(jù)包的發(fā)送速率和丟包概率來達到預防和控制擁塞的目的。如果當前節(jié)點緩沖器中的隊列長度L小于Lmin,則說明沒有任何的擁塞情況發(fā)生,通知上游節(jié)點,將不同優(yōu)先級的數(shù)據(jù)發(fā)送速率按照同一比例增大。如果隊列長度L處于Lmin和Lmax之間,屬于正常情況,這時上游節(jié)點按照優(yōu)先級的順序依次減少數(shù)據(jù)發(fā)送速率。當隊列長度L大于Lmax時,說明即將出現(xiàn)擁塞,應按照一定比例減小兩種數(shù)據(jù)發(fā)送節(jié)點的發(fā)送速率。不同優(yōu)先級的分組數(shù)據(jù)發(fā)送速率可表示為式(8):
式(8)中,N表示優(yōu)先級數(shù)目;Pi(i=0,1…,N-1)表示分組的優(yōu)先級,且優(yōu)先級高低順序為P0>P1>…>PN-1;V為數(shù)據(jù)包的平均發(fā)送速率;L為節(jié)點當前緩沖區(qū)隊列長度;Lmin:為緩沖區(qū)的下限閥值;Lmax為緩沖區(qū)的上限閥值;k和α均為速率參數(shù),1<k<vmax/v,0<α<1,vmax為最大發(fā)送速率。當節(jié)點當前的隊列長度L>Lmax+l時(l為緩沖隊列裕量),節(jié)點出現(xiàn)了擁塞。如果該節(jié)點的數(shù)據(jù)發(fā)送速率大于數(shù)據(jù)接收速率,則減小上游節(jié)點的發(fā)送速率仍達不到消除擁塞的目的。此時,采用一定概率進行丟包。優(yōu)先級為Pi的分組丟包概率為i/N,優(yōu)先級越高,丟包概率越小。反之,優(yōu)先級越低,丟包概率越大。
仿真工具采用 NS2和 MATLAB,仿真平臺在Linux系統(tǒng)下搭建。由于實際應用中,受到監(jiān)測環(huán)境、監(jiān)測要求等因素的影響,視頻、音頻等多媒體信號采集節(jié)點通常是隨機的非均勻部署。因此,本實驗將50個節(jié)點非均勻地分布在100×100的區(qū)域內(nèi),節(jié)點的坐標使用正太分布產(chǎn)生的隨機數(shù)確定。節(jié)點的通信范圍為40 m,每個節(jié)點的初始能量為1 J。在相同的節(jié)點分布條件下,對SPEED協(xié)議和WMSNRR協(xié)議進行實驗對比分析。主要從以下2個方面來評估WMSNRR協(xié)議的性能。
從圖2可以看出,在能量開銷方面,WMSNRR協(xié)議比SPEED協(xié)議更加節(jié)能。原因在于WMSNRR協(xié)議在路由選擇過程中,因考慮了兩跳節(jié)點的信息,及時發(fā)現(xiàn)路由空洞,避免了一些因路由空洞造成的數(shù)據(jù)丟失或重傳帶來的能量開銷。其次,采用了基于分組優(yōu)先級的丟包策略,在發(fā)生數(shù)據(jù)擁塞時,減少了可丟棄的分組多次重傳消耗的能量。
圖2 能量消耗
圖3中,WMSNs網(wǎng)絡使用 WMSNRR協(xié)議比SPEED協(xié)議時壽命更長,節(jié)點死亡時間延長。WMSNRR協(xié)議在選擇路由時,將節(jié)點的剩余能量作為一個考慮因素,避免速率較大的節(jié)點一直處于數(shù)據(jù)分組的接收與轉(zhuǎn)發(fā)狀態(tài)。因為部分關鍵路徑上的節(jié)點過早死亡,對后續(xù)的重要數(shù)據(jù)的傳輸以及整個網(wǎng)絡的壽命影響較大。
圖3 網(wǎng)絡壽命
WMSNRR協(xié)議與SPEED協(xié)議在時延性能方面比較結(jié)果如圖4,在數(shù)據(jù)分組較小時,WMSNRR協(xié)議的優(yōu)越性并不十分明顯,而在數(shù)據(jù)分組超過一定值后,WMSNRR協(xié)議的時延性能大幅度提高。因為在數(shù)據(jù)包發(fā)送速率增大到一定數(shù)值后,部分節(jié)點會出現(xiàn)擁塞現(xiàn)象,WMSNRR協(xié)議的擁塞控制發(fā)揮了明顯的作用。基于分組優(yōu)先級信息的丟包控制策略,及時丟棄低優(yōu)先級的數(shù)據(jù)分組,保證重要數(shù)據(jù)及時達到目的節(jié)點。
圖4 數(shù)據(jù)傳輸延遲
本文提出了一種QoS保證的無線多媒體傳感器網(wǎng)絡實時路由協(xié)議(WMSNRR)。該協(xié)議在路由決策時,在保證端到端的傳輸速率基礎上,不僅充分考慮兩跳鄰居節(jié)點的轉(zhuǎn)播速率信息,盡量避免“路由空洞”和“速率空洞”的發(fā)生,同時還考慮兩跳鄰居節(jié)點的剩余能量,避免一些關鍵路徑上的轉(zhuǎn)播速率大的節(jié)點過早死亡,造成網(wǎng)絡拓撲發(fā)生變化。此外,本文還采用一種基于緩存隊列長度和節(jié)點收發(fā)數(shù)據(jù)率的擁塞控制方法,對不同業(yè)務進行區(qū)分管理和擁塞控制,保證QoS的實時性和準確性等要求。仿真實驗表明,該路由協(xié)議在實時服務和能量開銷等方面具有較好的性能。
[1]Wang Chong-gang,LiBo,Kazem Sohraby,etal.Upstream Congestion Control in Wireless Sensor Networks Through Cross-Layer Optimization[J].IEEE Journal on Selected Areas in Communications,2007,25(4):786-795.
[2]張正宜,金心宇.無線多媒體傳感器網(wǎng)絡實時任務分配算法[J].傳感技術學報,2009,22(5):688-693.
[3]Luis Cobo,Alejandro Quintero,Samuel Pierre.Ant-Based Routing for Wireless Multimedia Sensor Networks Using Multiple Qos Metrics[J].Computer Networks,2010,54(17):2991-3020.
[4]崔夢天,鐘勇,趙海軍,等.ACOGA算法的多媒體網(wǎng)絡QoS實現(xiàn)[J].電子科技大學學報,2009,38(2):266-269.
[5]郭攀紅,楊揚,唐先明,等.基于業(yè)務流偏好的多QoS目標決策分層路由研究[J].計算機科學,2010,37(6):56-59.
[6]He Tian,Stankovic J A,Lu Chenyang,et al.A Spatiotemprol Communication Protocol for Wireless Sensor Networks[J].IEEE Trans.on Parallel and Distributed Systems,2005,16(10):995-1006.
[7]Mundarath J C,Ramanathan P,Van Veen B D.A Quality of Service AwareCross-LayerApproach forWirelessAd Hoc Networks with Smart Antennas[J].Ad Hoc Networks,2009,7(5):891-903.
[8]Keming Du,Yilin Chang,Bin Li.DSR-Based Cross-Layer QoS Design in Ad Hoc Networks[C]//Communications and Intelligence Information Security(ICCIIS),2010,224-227.
[9]趙永輝,史浩山.基于云模型的無線傳感器網(wǎng)絡擁塞及速率控制策略[J].傳感技術學報,2010,23(1):133-138.
[10]Mohammad Hossein Yaghmaee,Donald A.Priority-Based Rate Control for Service Differentiation and Congestion Control in Wireless Multimedia Sensor Networks[J].Computer Networks,2009,53(11):1798-1811.
[11]Sinan Isik,Mehmet Yunus Donmez,Cem Ersoy.Cross Layer Load Balanced Forwarding Schemes for Video Sensor Networks[J].Ad Hoc Networks,2011,9(3):265-284.
[12]吳國偉,張巖.無線傳感器網(wǎng)絡中的逐跳跨層擁塞控制[J].計算機工程,2010,36(16):108-115.