王 震，常穎華

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

0 引言

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

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

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

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

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

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

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

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

2.2 傳輸時(shí)間預(yù)測

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

表1 采用符號(hào)列表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分組傳輸時(shí)段內(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ù)時(shí)間，考慮節(jié)點(diǎn)i到節(jié)點(diǎn)j的k次重傳。首先，節(jié)點(diǎn)需要等待使信道空閑，滿足DIFS的要求。這將消耗DIFS/PiDIFS時(shí)間。然后，回退計(jì)數(shù)器選定一個(gè)回退時(shí)隙的隨機(jī)數(shù)。考慮到回退計(jì)數(shù)器的停止所期望的回退時(shí)隙的時(shí)間間隔為

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

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

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

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

M/M/1隊(duì)列的隊(duì)列延遲為

將ε代入到上式，有

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

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

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

由上面獲得每條由源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D的預(yù)測傳輸時(shí)延后，就可以執(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的對(duì)比。MAODV是一種共享樹組播路由協(xié)議，一種典型的組播路由協(xié)議，是在路由協(xié)議AODV基礎(chǔ)上增加了組播功能。

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

圖4 端到端傳輸時(shí)延對(duì)比Fig 4 Comparison of the time delay of end to end transmission

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

圖5 節(jié)點(diǎn)吞吐率對(duì)比Fig 5 Comparison of throughput rate of nodes

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

5 結(jié)論

本文采用預(yù)測時(shí)延算法，通過對(duì)源節(jié)點(diǎn)到目的節(jié)點(diǎn)傳輸數(shù)據(jù)的時(shí)延預(yù)測，獲得源節(jié)點(diǎn)到目的節(jié)點(diǎn)最短時(shí)延的路徑。通過對(duì)路徑進(jìn)行合并，得到組播路由樹。組播路由樹中的路由具有傳輸時(shí)延小、吞吐率高特點(diǎn)。同時(shí)利用保存合并前的路徑，使得路由在受到破壞時(shí)，能夠局部修復(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é)報(bào)，2010，21:1308-1325.

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

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

［9］潘 耘，王行剛，馮煙利，等.求解帶度約束多播路由問題的啟發(fā)式遺傳算法［J］.通信學(xué)報(bào)，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.