基于預(yù)測時延的無線mesh網(wǎng)絡(luò)組播路由算法*

王 震，常穎華

(重慶大學(xué)通信工程學(xué)院，重慶400044)

0 引言

無線mesh網(wǎng)絡(luò)作為最有潛力的下一代網(wǎng)絡(luò)［1］。mesh拓撲結(jié)構(gòu)能夠提供高的可靠性、覆蓋和穩(wěn)定性。滿足用戶隨時隨地獲得高質(zhì)量的無線寬帶服務(wù)是無線mesh網(wǎng)絡(luò)設(shè)計目標(biāo)之一，組播作為一種能有效節(jié)約網(wǎng)絡(luò)資源的通信服務(wù)成為發(fā)展方向［2］。研究有效的組播路由算法是實現(xiàn)這些功能的基礎(chǔ)，這已成為無線Mesh網(wǎng)絡(luò)研究的熱點。研究人員提出了多種路由算法，主要分為兩類:一是基于樹，如AMRoute［3］，AMRIS［4］，它們在源節(jié)點與接收節(jié)點之間提供一條路由;另外一類是基于格網(wǎng)的，如 ODMRP［5］，CAMP，它們在源節(jié)點和目的節(jié)點形成多條路由，從而提高路由的可靠性?；诰W(wǎng)格的路由算法盡管在可靠性方面提高，但算法復(fù)雜度、路由形成機制上比基于樹的復(fù)雜［6］。組播路由算法為了達到QoS要求，提出了很多改進措施，如采用遺傳算法、退火算法等啟發(fā)式算法［7～10］。這些算法復(fù)雜度高?；诖颂岢鲆环N具有滿足低時延QoS保障組播路由算法。這種路由算法具有傳播時延小，高可靠性。

1 基于預(yù)測時延的組播路由算法基本思想

首先，采用預(yù)測時延的算法獲得源節(jié)點S到目的節(jié)點D的最短傳輸時延路徑。從而保障源節(jié)點到目的節(jié)點間具有最短的傳輸時延，使得組播業(yè)務(wù)獲得低時延的QoS保障。根據(jù)預(yù)測時延算法獲得每條路由的傳輸時延算法后，將路由路徑按照傳輸時延從高到低排列，同時按照源節(jié)點到目的節(jié)點的跳數(shù)分層。將距離源節(jié)點到目的節(jié)點第一跳設(shè)置為第一層，依次類推。接著由低時延路徑的高層次節(jié)點向高時延節(jié)點尋找距離一跳的節(jié)點，如果存在就刪除低時延路徑的從源節(jié)點到此節(jié)點的路徑。從而獲得路徑復(fù)用，同時獲得最短時延的組播樹T。如果有節(jié)點離開組播樹T，由于保存了已刪除的路徑，只需要重新采用路徑，使得路由算法不需要重新執(zhí)行。如果有新的節(jié)點加入到組播樹T，節(jié)點首先建立到源節(jié)點的最短時延路徑P，接著合并路徑。這種路由算法能夠保障無線mesh網(wǎng)絡(luò)的業(yè)務(wù)QoS具有高可靠性。路由算法具有局部更新的能力，使得路由算法具有高效性。那么這個路由算法最基礎(chǔ)的是尋找預(yù)測傳輸時間的路徑。下面詳細介紹這種方法。

2 基于傳輸預(yù)測時間的路徑選擇

2.1 傳輸時間預(yù)測的基本思路

根據(jù)節(jié)點位置將干擾通信量分為相鄰節(jié)點通信量CS和隱含節(jié)點通信量HT。CS通信量是處于鏈路發(fā)射機載波偵聽范圍內(nèi)所有節(jié)點積累的通信量。在無線網(wǎng)絡(luò)中，當(dāng)發(fā)送節(jié)點要通過鏈路發(fā)送一個數(shù)據(jù)幀時，它必須與處于CS范圍內(nèi)的節(jié)點競爭接入到網(wǎng)絡(luò)，這樣較大的CS通信量將導(dǎo)致較長的接入時間。HT通信量是由于鏈路接收節(jié)點偵聽范圍內(nèi)節(jié)點累積的通信量，但是其鏈路發(fā)送節(jié)點不在載波偵聽范圍。較大的HT通信量將導(dǎo)致較多的碰撞發(fā)生，這將導(dǎo)致較長的傳輸時間。為了預(yù)測通信傳輸時間，就必須要對其位置進行區(qū)分。

節(jié)點到數(shù)據(jù)中心都選擇最短路徑，那么，每個節(jié)點到數(shù)據(jù)中心的傳輸時間預(yù)測定義為分組進入鏈路發(fā)送終端隊列的時刻開始到其發(fā)送成功到達數(shù)據(jù)中心或被丟棄的時間，其中包含隊列延遲和分組服務(wù)時間。使用M/M/1模型來計算隊列延遲。那么，特定的鏈路傳輸時間與現(xiàn)存的CS通信量、HT通信量和自通信量相關(guān)。鏈路傳輸時間表示為(τCS，τHT，τ)，其中，τCS和 τHT分布表示平均 CS 通信速率和HT通信速率。使用2個參數(shù)來表示，即載波偵聽因子(CSF)和隱含端因子(HTF)來表示自通信的干擾。鏈路的CSF是CS接收機范圍內(nèi)相同信道中的鏈路數(shù)量，但不處于發(fā)送節(jié)點范圍內(nèi)。對于從節(jié)點i到節(jié)點j的鏈路，由其通信量干擾增加的HT通信量為CSFij·τ，而由自通信量干擾增加的HT通信量為HTFij·τ。其中，τ為沿著最短路徑的通信量速率。

對于鏈路(i，j)，考慮到自身通信量干擾，CS通信量變?yōu)?τCS+CSFij·τ，而 HT 通信量變?yōu)?τHT+HTFij·τ。因此，考慮自身干擾通信量的前提下，兩節(jié)點間預(yù)測通信時間為(τCS+CSFij·τ，τHT+HTFij·τ，τ)。對于 n 條路徑，根據(jù)每天鏈路在路徑中的位置來獲得CSF和HTF。將每條鏈路的預(yù)測傳輸時間求和，可以得到整個最短路徑的預(yù)測傳輸時間。從每個節(jié)點域中找出時間最短節(jié)點。

2.2 傳輸時間預(yù)測

基于IEEE 802.11協(xié)議的流量引入一個新的MAC模型，根據(jù)給定的和干擾的通信量來估計分組碰撞概率。假定網(wǎng)絡(luò)中所有節(jié)點按照指數(shù)規(guī)律發(fā)送數(shù)據(jù)，采用泊松通信量模型。為了進行下一步分析，引入表1的符號。

表1 采用符號列表Tab 1 The list of symbol

其中，τnormCS(i，j)為鏈路(i，j)歸一化的 CS 通信量。

圖1 兩種情況引起的信道忙Fig 1 Arousing the channel being busy in two conditions

引起DATA分組碰撞的可能情況如圖2所示。DATA分組的成功發(fā)送概率PiDATA分組傳輸時段內(nèi)CHij中沒有鏈路傳輸任意分組的概率相等，即

其中，τnormht(i，j)為鏈路(i，j)歸一化的 CS 通信量。

圖2 導(dǎo)致DATA分組沖突的2種情況Fig 2 Arousing the collision of data packets in two conditions

為了獲得分組服務(wù)時間，考慮節(jié)點i到節(jié)點j的k次重傳。首先，節(jié)點需要等待使信道空閑，滿足DIFS的要求。這將消耗DIFS/PiDIFS時間。然后，回退計數(shù)器選定一個回退時隙的隨機數(shù)?？紤]到回退計數(shù)器的停止所期望的回退時隙的時間間隔為

在IEEE 802.11中，回退計數(shù)器的值在0與競爭窗口CW之間隨機選取。CW典型值最大為1023，最小為31.初始化是選擇最小值，不成功時，CW被加倍，直到達到最大CW。在k次重傳回退時隙的平均數(shù)為

如果DATA分組在k次發(fā)送沒有成功，則花費的全部時間為

如果DATA分組在第k次發(fā)送時被成功傳送，則花費的全部時間為

為了獲得隊列延遲時間，使用M/M/1隊列模型。令φ表示分組由鏈路(i，j)傳輸?shù)乃俾?，而分組服務(wù)速率為ε，其中，ε =1/TMAC。

M/M/1隊列的隊列延遲為

將ε代入到上式，有

將隊列延遲為分組服務(wù)時間求和，得到預(yù)測傳輸時延T(τCS，τHT，τ)為

因此，通過上述相關(guān)公式的推證和式(7)，式(10)可以獲得從源節(jié)點S到目的節(jié)點D的最短傳輸時延路徑。

3 基于傳輸預(yù)測時間的組播路由算法

由上面獲得每條由源節(jié)點S到目的節(jié)點D的預(yù)測傳輸時延后，就可以執(zhí)行組播路由算法。

路由算法的執(zhí)行流程如圖3所示。

圖3 算法執(zhí)行流程Fig 3 Execution flow chart of algorithm

4 算法仿真與分析

在NS—2中，設(shè)置在IEEE 802.11 Ad Hoc組網(wǎng)環(huán)境下，分別采用新路由協(xié)議和MAODV的對比。MAODV是一種共享樹組播路由協(xié)議，一種典型的組播路由協(xié)議，是在路由協(xié)議AODV基礎(chǔ)上增加了組播功能。

1)平均端到端時延:該參數(shù)包括了所有可能的時延:源節(jié)點路由發(fā)現(xiàn)時延、路徑中斷修復(fù)時延、多跳轉(zhuǎn)發(fā)時延、數(shù)據(jù)報文處理時延、接口排隊時延、MAC層分組重傳時延、鏈路傳播時延等。通過分析證明在同樣條件下，新路由協(xié)議的傳輸時延要低于MAODV，這是由于新協(xié)議對傳輸時延進行預(yù)測，得到最短時延路徑，從而使得傳輸時延要低于MAODV。端到端傳輸時延對比如圖4。

圖4 端到端傳輸時延對比Fig 4 Comparison of the time delay of end to end transmission

2)節(jié)點吞吐率:新協(xié)議通過傳輸時延預(yù)測尋找最短時延路徑的同時，也避免了節(jié)點間干擾。如圖5所示，組播樹節(jié)點吞吐率隨著時間變化，節(jié)點吞吐率沒有較大變化。新的路由算法要比MAODV的吞吐率高，新算法能夠提高網(wǎng)絡(luò)的吞吐性能。在節(jié)點密度較小的情況下，網(wǎng)絡(luò)的吞吐率要比節(jié)點密度大時高，如圖6。隨著節(jié)點密度的增加，節(jié)點吞吐率下降，這是由于節(jié)點間干擾增大。在節(jié)點密度較小的情況下，算法能夠獲得較高的吞吐率。

圖5 節(jié)點吞吐率對比Fig 5 Comparison of throughput rate of nodes

圖6 不同節(jié)點密度下節(jié)點吞吐率對比Fig 6 Comparison of throughput rate in different nodes density

5 結(jié)論

本文采用預(yù)測時延算法，通過對源節(jié)點到目的節(jié)點傳輸數(shù)據(jù)的時延預(yù)測，獲得源節(jié)點到目的節(jié)點最短時延的路徑。通過對路徑進行合并，得到組播路由樹。組播路由樹中的路由具有傳輸時延小、吞吐率高特點。同時利用保存合并前的路徑，使得路由在受到破壞時，能夠局部修復(fù)，路由具有高可靠性。通過仿真證明這種算法的性能是優(yōu)越的。

［1］Akyildiz I F，Wang Xudong.Wireless mesh network:A survey［J］.Computer Networks，2005，47:445-487.

［2］Huang Jun，LiuYanbing.MOEAQ:A QoS-aware multicast routing algorithm for MANET［J］.Expert Systems with Applications，2010，37(3):1391-1399.

［3］Jason X，Rajesh R T.AM route:Ad Hoc multicast routing protocol mobile networks and applications［J］.Multipoint Communication in Wireless Mobile Networks，2002，12:429-439.

［4］Wu CW，Tay Y C.AMRIS:A multicast protocol for Ad Hoc wireless networks proceedings［C］∥IEEE Military Communications(MILCOM)Conference，1999:25-29.

［5］Jabbehdari S，Shamaei M，Darehshoorzadeh A.IQoS-ODMRP:A novel routing protocol considering QoS parameter in MANET［C］∥2010 IEEE Symposium on Industrial Electronics and Applications，2010:126-130.

［6］方藝霖，李方敏，吳 鵬，等.無線 mesh網(wǎng)絡(luò)組播路由協(xié)議［J］.軟件學(xué)報，2010，21:1308-1325.

［7］葛連升.基于蟻群優(yōu)化的組播路由算法研究［M］.濟南:山東大學(xué)，2010:4.

［8］王新紅，王光興.基于遺傳算法的時延受限代價最小組播路由選擇方法［J］.通信學(xué)報，2002，3(3):112-117.

［9］潘 耘，王行剛，馮煙利，等.求解帶度約束多播路由問題的啟發(fā)式遺傳算法［J］.通信學(xué)報，2007，28(1):134-141.

［10］Wang X W，Cao JN，Cheng H，et al.QoSmulticast routing formulize diagraph communications using intelligential positional methods［J］.Computer Communications，2006，29:2217-2229.