提供QoS保障的無(wú)線多跳路徑可用帶寬估計(jì)模型與方法

宋 安 趙海濤 王 杉 魏急波

(國(guó)防科技大學(xué)電子科學(xué)與工程學(xué)院 長(zhǎng)沙 410073)

1 引言

無(wú)線多跳自組網(wǎng)能為布線困難的環(huán)境提供快速便捷的網(wǎng)絡(luò)服務(wù)，在軍事和民用兩方面均得到廣泛應(yīng)用。作為其基本構(gòu)成單位，無(wú)線多跳路徑具備多跳網(wǎng)絡(luò)的兩個(gè)基本特征，即流內(nèi)競(jìng)爭(zhēng)與節(jié)點(diǎn)負(fù)載間存在依賴關(guān)系，因此對(duì)多跳路徑的研究構(gòu)成了研究多跳自組網(wǎng)的基礎(chǔ)。

為了給在網(wǎng)絡(luò)中占據(jù)了越來(lái)越大比重的QoS敏感業(yè)務(wù)提供更好的服務(wù)，對(duì)網(wǎng)絡(luò)剩余通信能力即可用帶寬的研究得到了極大的關(guān)注。可用帶寬的定義為：在不影響網(wǎng)絡(luò)中所有業(yè)務(wù)流的QoS的前提下，網(wǎng)絡(luò)能支持的最大額外負(fù)載。但是現(xiàn)有的可用帶寬估計(jì)方法中，基于測(cè)量的方法[1]和基于感知的方法[2-4]均將網(wǎng)絡(luò)所能支持的最大吞吐量作為可用帶寬，而沒(méi)有考慮估計(jì)結(jié)果被使用后會(huì)給網(wǎng)絡(luò)帶來(lái)何種影響；基于模型的方法能在估計(jì)過(guò)程中考慮業(yè)務(wù)流之間的相互影響，但是文獻(xiàn)[5]僅考慮了業(yè)務(wù)流的MAC層干擾約束而不能為業(yè)務(wù)提供QoS保障。

設(shè)計(jì)基于分析模型的可用帶寬估計(jì)方法的前提是建立一個(gè)滿足需要并且準(zhǔn)確可靠的多跳路徑分析模型。該模型必須具備以下兩個(gè)特點(diǎn)：第一，必須全面考慮流內(nèi)競(jìng)爭(zhēng)帶來(lái)的影響；第二，必須能夠體現(xiàn)路徑性能隨外部負(fù)載的變化關(guān)系。但是在現(xiàn)有的研究中，針對(duì)流內(nèi)競(jìng)爭(zhēng)的研究不夠全面，他們要么假設(shè)了理想調(diào)度而忽略了節(jié)點(diǎn)的相互干擾[6]，要么在進(jìn)行碰撞分析時(shí)僅考慮隱藏節(jié)點(diǎn)的影響，而忽略了鄰節(jié)點(diǎn)間的沖突[7-9]。此外，這些研究大多假設(shè)網(wǎng)絡(luò)處于飽和狀態(tài)，沒(méi)有研究節(jié)點(diǎn)負(fù)載間的關(guān)系以及外部負(fù)載對(duì)網(wǎng)絡(luò)性能的影響。

針對(duì)現(xiàn)有研究工作的不足，本文對(duì)多跳路徑的干擾問(wèn)題進(jìn)行了詳細(xì)分析與定量計(jì)算，并建立了基于排隊(duì)網(wǎng)絡(luò)理論的多跳路徑性能分析模型；基于該分析模型，以業(yè)務(wù)流的時(shí)延、丟包率與吞吐量等QoS需求不被破壞為約束條件設(shè)計(jì)了多跳路徑的可用帶寬估計(jì)方法；通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了分析模型的準(zhǔn)確性與可用帶寬估計(jì)方法的合理性。

2 多跳路徑上的干擾分析

2.1 系統(tǒng)模型與假設(shè)

考慮由N+1個(gè)運(yùn)行 IEEE 802.11協(xié)議的靜止節(jié)點(diǎn)組成的N跳路徑。為了便于分析，假設(shè)理想信道并且所有節(jié)點(diǎn)具有相同的MAC層與物理層參數(shù)。根據(jù) NS2仿真器的默認(rèn)值，設(shè)置節(jié)點(diǎn)的傳輸范圍RTX為250 m，載波偵聽(tīng)范圍RCS為550 m，捕獲門限為 10 dB。根據(jù)參考文獻(xiàn)[7]的場(chǎng)景設(shè)置，取鄰節(jié)點(diǎn)間距d為200 m。典型的多跳路徑如圖1所示。

圖1 典型的多跳路徑示意圖

對(duì)于節(jié)點(diǎn)i，其干擾范圍RI是指落在其內(nèi)的競(jìng)爭(zhēng)節(jié)點(diǎn)會(huì)影響i的接收，即出現(xiàn)碰撞的區(qū)域。利用文獻(xiàn)[10]中的干擾范圍計(jì)算方法，可得出當(dāng)捕獲門限為10 dB時(shí)，RI為356 m。為了簡(jiǎn)化分析，假設(shè)節(jié)點(diǎn)工作于基本訪問(wèn)模式，這是因?yàn)樵诙嗵W(wǎng)絡(luò)中，當(dāng)RCS大于兩倍RTX時(shí)，RTS/CTS機(jī)制并不能有效地消除隱藏節(jié)點(diǎn)問(wèn)題[10]。

2.2 干擾的定性分析

與流間競(jìng)爭(zhēng)不同，流內(nèi)競(jìng)爭(zhēng)是多跳網(wǎng)絡(luò)的特有現(xiàn)象。多跳路徑只存在流內(nèi)競(jìng)爭(zhēng)，這是影響路徑中業(yè)務(wù)流性能和路徑可用帶寬的關(guān)鍵因素。流內(nèi)競(jìng)爭(zhēng)體現(xiàn)為路徑上節(jié)點(diǎn)間的相互干擾，我們針對(duì)圖1中由發(fā)送節(jié)點(diǎn)i與接收節(jié)點(diǎn)i+1構(gòu)成的鏈路(i,i+1)對(duì)干擾進(jìn)行分類分析。

(1)對(duì)退避過(guò)程的干擾：對(duì)于正在退避的節(jié)點(diǎn)i，其RCS范圍內(nèi)的干擾會(huì)影響i的退避過(guò)程，具體表現(xiàn)為若i感知到RCS范圍內(nèi)信道忙，會(huì)掛起其退避過(guò)程，直到信道恢復(fù)空閑后才繼續(xù)退避。令CS(i)表示節(jié)點(diǎn)i的RCS范圍內(nèi)節(jié)點(diǎn)的集合，由于載波偵聽(tīng)范圍與節(jié)點(diǎn)間距滿足關(guān)系 2d＜RCS＜ 3d，因此有CS(i)={i± 2,i± 1 }。

(2)來(lái)自鄰節(jié)點(diǎn)的同步碰撞：同時(shí)位于i的RCS范圍與i+1的RI范圍之內(nèi)的節(jié)點(diǎn)與i在同一時(shí)隙進(jìn)行發(fā)送時(shí)，會(huì)與i的發(fā)送發(fā)生碰撞，這樣的碰撞稱為同步碰撞。令SynN(i)表示對(duì)鏈路(i,i+1)造成同步碰撞的節(jié)點(diǎn)的集合，那么SynN(i)={i+ 1,i+ 2 }。

(3)來(lái)自隱藏節(jié)點(diǎn)的異步碰撞：鏈路(i,i+1)的隱藏節(jié)點(diǎn)是指位于i的RCS范圍之外但是i+1的RCS范圍之內(nèi)的那些節(jié)點(diǎn)，即節(jié)點(diǎn)i+3。若i+3向i+ 4 的傳輸早于i向i+1的傳輸，且在i開(kāi)始傳輸時(shí)i+3的傳輸尚未結(jié)束，那么i+1檢測(cè)到信道忙從而不會(huì)對(duì)i的發(fā)送進(jìn)行應(yīng)答，于是i便認(rèn)為此次傳輸出現(xiàn)碰撞。但是，若i+3的傳輸晚于i的傳輸，捕獲效應(yīng)使得i+3不會(huì)干擾(i,i+1)上的傳輸。隱藏節(jié)點(diǎn)造成的碰撞不要求隱藏節(jié)點(diǎn)與發(fā)送節(jié)點(diǎn)的傳輸同時(shí)進(jìn)行，因此稱為異步碰撞。令HN(i)表示(i,i+1)的隱藏節(jié)點(diǎn)的集合，那么HN(i)={i+ 3 }。

2.3 干擾的定量計(jì)算

對(duì)多跳路徑上的干擾進(jìn)行建模分析時(shí)，必須考慮非飽和狀態(tài)以及異構(gòu)業(yè)務(wù)源。這是因?yàn)椋?1)只有在非飽和條件下路徑上才存在可用的剩余帶寬；(2)路徑上任意節(jié)點(diǎn)都可能有業(yè)務(wù)流加入或離開(kāi)網(wǎng)絡(luò)，并且節(jié)點(diǎn)的輸入還依賴于其上游節(jié)點(diǎn)的輸出。

非飽和條件下的嘗試速率可使用隊(duì)列利用率ρ對(duì)飽和條件下的嘗試速率進(jìn)行松弛來(lái)獲得。根據(jù)文獻(xiàn)[11]提出的不動(dòng)點(diǎn)方法，飽和時(shí)節(jié)點(diǎn)的嘗試速率為發(fā)送一個(gè)報(bào)文的平均嘗試次數(shù)與平均退避時(shí)隙數(shù)之比，因此非飽和狀態(tài)時(shí)的嘗試速率為

其中下標(biāo)i表示第i個(gè)節(jié)點(diǎn)，為條件碰撞概率，ρi為隊(duì)列利用率，M為最大重傳次數(shù)。退避階段j的退避窗口Wj服從離散均勻分布，其均值與方差分別為

其中CW0是初始競(jìng)爭(zhēng)窗口，m是最大退避階段。

其中，鄰節(jié)點(diǎn)導(dǎo)致的同步碰撞概率為

根據(jù)2.2節(jié)的分析，若隱藏節(jié)點(diǎn)的傳輸早于該鏈路上的傳輸且領(lǐng)先的時(shí)間不超過(guò)報(bào)文的傳輸時(shí)間，那么碰撞就會(huì)發(fā)生，該時(shí)間區(qū)域稱為鏈路的脆弱期。對(duì)于基本訪問(wèn)模式，鏈路的脆弱期V等于報(bào)文傳輸時(shí)間加上短幀間間隔SIFS，即

其中Tdata表示報(bào)文傳輸時(shí)間。V是以系統(tǒng)時(shí)隙長(zhǎng)度σ為單位的整數(shù)值，int(?)表示取整操作。注意到隱藏節(jié)點(diǎn)只有在處于退避過(guò)程時(shí)的那段脆弱期才可能因發(fā)送報(bào)文而引起碰撞。令表示節(jié)點(diǎn)j花在非掛起狀態(tài)的退避過(guò)程中的平均時(shí)間，并令其平均服務(wù)時(shí)間為E[Tst,j]，那么j有報(bào)文傳輸且處于非掛起狀態(tài)的退避過(guò)程的概率為bj/E[Tst,j]，于是隱藏節(jié)點(diǎn)在鏈路脆弱期的任意時(shí)隙進(jìn)行發(fā)送而造成異步碰撞的概率為

給定節(jié)點(diǎn)隊(duì)列利用率ρi，式(1)，式(2)和式(4)構(gòu)成了DCF機(jī)制的不動(dòng)點(diǎn)方程組，并可通過(guò)數(shù)值計(jì)算求解每個(gè)節(jié)點(diǎn)的碰撞概率。我們將在第 3.3節(jié)利用排隊(duì)網(wǎng)絡(luò)理論對(duì)ρi進(jìn)行討論。

最后，節(jié)點(diǎn)i檢測(cè)到RCS范圍內(nèi)信道變忙從而導(dǎo)致退避過(guò)程被掛起的概率為

3 排隊(duì)網(wǎng)絡(luò)模型

假設(shè)路徑上存在K個(gè)流，每個(gè)流均發(fā)送長(zhǎng)度為L(zhǎng)的等長(zhǎng)報(bào)文，其中第k個(gè)流的起始節(jié)點(diǎn)為sk，終止節(jié)點(diǎn)為dk，平均輸入速率為且服從泊松分布。節(jié)點(diǎn)具有無(wú)限長(zhǎng)隊(duì)列。令F(K)表示所有流的集合，N[sk,dk]表示流k所經(jīng)過(guò)的節(jié)點(diǎn)集合，F(xiàn)SRC(i)表示以節(jié)點(diǎn)i∈[1,N]為源節(jié)點(diǎn)的流的集合，F(xiàn)DST(i)表示以節(jié)點(diǎn)i∈[2,N+ 1]為目的節(jié)點(diǎn)的流的集合。于是無(wú)線多跳路徑可建模為開(kāi)放排隊(duì)網(wǎng)絡(luò)，并可通過(guò)擴(kuò)散近似法來(lái)分析這K個(gè)流各自的QoS參數(shù)。

3.1 擴(kuò)散近似法

擴(kuò)散近似法[12]可用來(lái)求解開(kāi)放 G/G/1排隊(duì)網(wǎng)絡(luò)。考慮由N個(gè)節(jié)點(diǎn)構(gòu)成的排隊(duì)網(wǎng)絡(luò)，其外部輸入負(fù)載是一個(gè)更新過(guò)程，報(bào)文到達(dá)間隔的平均值與變異系數(shù)分別為1/λe與cA。令節(jié)點(diǎn)i的服務(wù)時(shí)間的均值與變異系數(shù)分別為1/μi與cBi。定義排隊(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的訪問(wèn)率為一個(gè)報(bào)文被該節(jié)點(diǎn)轉(zhuǎn)發(fā)的平均次數(shù)，那么節(jié)點(diǎn)i的訪問(wèn)率ei為

其中p0i表示報(bào)文經(jīng)由節(jié)點(diǎn)i進(jìn)入網(wǎng)絡(luò)的概率，pji表示報(bào)文在節(jié)點(diǎn)j服務(wù)完畢后轉(zhuǎn)發(fā)到節(jié)點(diǎn)i的概率。到達(dá)節(jié)點(diǎn)的報(bào)文包括節(jié)點(diǎn)自己產(chǎn)生的報(bào)文和其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的報(bào)文，因此我們用有效到達(dá)速率λi來(lái)表示實(shí)際到達(dá)節(jié)點(diǎn)i的報(bào)文速率。

節(jié)點(diǎn)i的隊(duì)列利用率ρi可表示為

節(jié)點(diǎn)i的報(bào)文到達(dá)間隔時(shí)間的平方變異系數(shù)可以近似表示為

其中

于是節(jié)點(diǎn)i隊(duì)列中的平均報(bào)文數(shù)為

3.2 排隊(duì)網(wǎng)絡(luò)的參數(shù)

為了能夠使用擴(kuò)散近似法來(lái)求解排隊(duì)網(wǎng)絡(luò)，我們需要將擴(kuò)散近似法所需的參量表示為多跳路徑的網(wǎng)絡(luò)參數(shù)。

引理 1 在處于穩(wěn)定狀態(tài)的多跳路徑上，報(bào)文在節(jié)點(diǎn)i服務(wù)完畢后轉(zhuǎn)發(fā)到節(jié)點(diǎn)j的路由概率為

其中pi0表示報(bào)文在節(jié)點(diǎn)i處理完畢后離開(kāi)網(wǎng)絡(luò)的概率；I(x)為指示函數(shù)；為鏈路(i,i+1)的吸收

A概率即i的所有輸出報(bào)文中，因i+1是目的節(jié)點(diǎn)而在i+1離開(kāi)網(wǎng)絡(luò)，從而不會(huì)進(jìn)入i+1的隊(duì)列的概率，且

證明 穩(wěn)定狀態(tài)時(shí)，節(jié)點(diǎn)i輸出報(bào)文的聚合速率為所有經(jīng)過(guò)i的流在此之前所經(jīng)過(guò)的節(jié)點(diǎn)中未因超過(guò)重傳限制而損失的速率之和，即式(17)的分母。而分子表示因i+1是目的節(jié)點(diǎn)而離開(kāi)網(wǎng)絡(luò)的流的聚合速率，后者與前者之比即鏈路(i,i+1)的吸收概率。i的輸出報(bào)文離開(kāi)網(wǎng)絡(luò)的原因包括：(1)以概率在i處因超過(guò)重傳限制而被丟棄；(2)在i處沒(méi)有被丟棄但是i+1是目的節(jié)點(diǎn)，其概率為于是報(bào)文在i處理完畢后離開(kāi)網(wǎng)絡(luò)的概率為

受路徑拓?fù)湎拗疲琲的報(bào)文只能直接傳輸給i+1，于是報(bào)文由i轉(zhuǎn)發(fā)給i+1的概率為

報(bào)文在節(jié)點(diǎn)j處進(jìn)入網(wǎng)絡(luò)的聚合速率可表示為整個(gè)路徑的外部輸入負(fù)載的聚合速率者之比即報(bào)文經(jīng)由j進(jìn)入網(wǎng)絡(luò)的概率為

聯(lián)立式(18)~式(20)即得式(16)。 證畢

引理 2 穩(wěn)定狀態(tài)時(shí)，多跳路徑中節(jié)點(diǎn)的訪問(wèn)率由式(21)給出

證明 路徑的源節(jié)點(diǎn)只有來(lái)自排隊(duì)網(wǎng)絡(luò)外部的輸入，因此e1=p01；而路徑上的其他節(jié)點(diǎn)的輸入除了可能的外部輸入外，還包括來(lái)自上一跳節(jié)點(diǎn)輸出，因此通過(guò)節(jié)點(diǎn)訪問(wèn)率的相互關(guān)系式(9)容易得出證畢

引理3 穩(wěn)定狀態(tài)時(shí)，節(jié)點(diǎn)i的有效到達(dá)速率λi為

證明 根據(jù)訪問(wèn)率的定義式(10)，即λi=λeei，反復(fù)運(yùn)用引理2中的式(21)即得式(22)。 證畢

定理 1 當(dāng)輸入負(fù)載均服從泊松分布時(shí)，節(jié)點(diǎn)的報(bào)文到達(dá)間隔時(shí)間的SCV為

證明 由于泊松流的合成仍為泊松流，因此任意節(jié)點(diǎn)i的外部輸入服從參數(shù)為的泊松分布。根據(jù)泊松分布的性質(zhì)，i的外部輸入過(guò)程的報(bào)文到達(dá)間隔時(shí)間服從負(fù)指數(shù)分布，其均值與方差均為 1 /λe,i，因此其 SCV 為由于路徑源節(jié)點(diǎn)只有來(lái)自排隊(duì)網(wǎng)絡(luò)外部的輸入，根據(jù)式(12)，可計(jì)算源節(jié)點(diǎn)的報(bào)文到達(dá)間隔時(shí)間的SCV為

而對(duì)于路徑上的其他節(jié)點(diǎn)，利用引理2的結(jié)論可得其報(bào)文到達(dá)間隔時(shí)間的SCV為

聯(lián)立式(24)與式(25)即得式(23)。 證畢

3.3 服務(wù)時(shí)間的平方變異系數(shù)

服務(wù)時(shí)間是指報(bào)文從到達(dá)隊(duì)首到其離開(kāi)隊(duì)列為止之間的時(shí)間間隔，而不管報(bào)文是否成功傳輸?shù)侥康墓?jié)點(diǎn)。為了符號(hào)表示方便，除非特別說(shuō)明，本節(jié)省略代表節(jié)點(diǎn)i的下標(biāo)。令Tst_s表示成功傳輸?shù)膱?bào)文的服務(wù)時(shí)間，受文獻(xiàn)[13]的啟發(fā)，可計(jì)算Tst_s的均值和方差分別為

其中Ts與Tc分別為報(bào)文成功傳輸與發(fā)生碰撞的時(shí)間，E[Wj]與Var[Wj]分別由式(2)和式(3)給出。ξ代表節(jié)點(diǎn)在每個(gè)退避時(shí)隙實(shí)際花費(fèi)的時(shí)間，由于節(jié)點(diǎn)檢測(cè)到其RCS范圍內(nèi)信道變忙的概率為pb(見(jiàn)式(8))，于是有

類似地，令Tst_d表示因超過(guò)重傳限制而丟棄的報(bào)文的服務(wù)時(shí)間，有

于是，節(jié)點(diǎn)i發(fā)送報(bào)文的服務(wù)時(shí)間的SCV為

節(jié)點(diǎn)i的隊(duì)列利用率為

3.4 多跳路徑中業(yè)務(wù)流的QoS參數(shù)

根據(jù)Little定律，報(bào)文在鏈路(i,i+1)的平均時(shí)延為那么流k的平均時(shí)延，即其經(jīng)過(guò)的鏈路的時(shí)延之和為

在無(wú)限隊(duì)長(zhǎng)與理想信道假設(shè)下，超過(guò)重傳限制是報(bào)文丟棄的唯一原因。由于當(dāng)報(bào)文在其經(jīng)過(guò)的每跳鏈路上都不被丟棄時(shí)才能成功傳輸?shù)侥康墓?jié)點(diǎn)，因此流k的丟包率為

對(duì)于鏈路(i,i+1)，吞吐量Si等于單位時(shí)間內(nèi)所有在i服務(wù)完畢而離隊(duì)的報(bào)文中成功傳輸?shù)絠+1的報(bào)文數(shù)。當(dāng)i非飽和時(shí)，報(bào)文的平均到達(dá)速率小于平均服務(wù)速率，所有報(bào)文均接受 MAC層的服務(wù)，吞吐量依賴于負(fù)載的大小；而當(dāng)i飽和后，吞吐量只受其服務(wù)時(shí)間的約束。由于式(10)只適用于穩(wěn)定狀態(tài)下的排隊(duì)網(wǎng)絡(luò)，因此引理3不能反映飽和狀態(tài)時(shí)節(jié)點(diǎn)負(fù)載間的關(guān)系。例如，當(dāng)i-1飽和后，其輸出不再依賴輸入，而此時(shí)i的負(fù)載中來(lái)自i-1的部分受制于其服務(wù)速率。注意到無(wú)論i-1是否飽和，其向i的輸出都是其吞吐量Si-1，于是用式(38)的遞推式來(lái)計(jì)算鏈路(i,i+1)的吞吐量：

其中S0=∑k∈FSRC(1)λe為路徑源節(jié)點(diǎn)的聚合輸入負(fù)載。經(jīng)過(guò)鏈路(i,i+1)的流k在(i,i+1)上的輸入速率等于其在上一跳鏈路的吞吐量。如果i非飽和，那么該流在(i,i+1)的吞吐量是其輸入速率中不被丟棄的部分；反之，若i飽和，那么等于在(i,i+1)的飽和吞吐量中，屬于流k的輸入速率占所有進(jìn)入i的隊(duì)列的輸入速率的比例。即

注意式(39)中i∈[s,d- 1],代表流k的

kk外部輸入速率。而流k的吞吐量Sk就等于它經(jīng)過(guò)最后一跳鏈路時(shí)的吞吐量，即

4 可用帶寬估計(jì)原則與方法

根據(jù)可用帶寬的定義，給定帶寬可用的前提是該帶寬被使用后網(wǎng)絡(luò)中所有業(yè)務(wù)流的QoS不能受到破壞。于是判斷給定帶寬是否可用，或者說(shuō)判定帶寬需求的可行性，可轉(zhuǎn)變?yōu)槭紫韧ㄟ^(guò)網(wǎng)絡(luò)分析模型計(jì)算帶寬需求被滿足后所有業(yè)務(wù)流的QoS參數(shù)，然后將這些參數(shù)與預(yù)先定義的門限值進(jìn)行比較，如果所有參數(shù)都不超過(guò)其門限值，那么認(rèn)為QoS不會(huì)受到影響，于是判定該帶寬需求可行；否則，如果任何一個(gè)參數(shù)超過(guò)了門限值，那么判定該帶寬需求不可行。在本文的分析中，我們使用時(shí)延，丟包率與吞吐量這3個(gè)被廣泛接受的QoS度量。令λAB表示帶寬需求，于是求路徑的可用帶寬轉(zhuǎn)變?yōu)槭?41)所示的非線性規(guī)劃問(wèn)題

其中LossThd與DelayThd分別表示業(yè)務(wù)能容忍的最大丟包率與最大端到端時(shí)延，與分別表示在所需求的帶寬被使用前與使用后流k的吞吐量，ThpDegThd為業(yè)務(wù)能容忍的最大歸一化吞吐量跌幅，最后一個(gè)約束意味著當(dāng)所需求的帶寬被使用后，路徑中之前已經(jīng)存在業(yè)務(wù)流各自的吞吐量歸一化跌幅不能超過(guò)門限值ThpDegThd。

上述非線性規(guī)劃問(wèn)題很難求出閉合解，但是考慮到 802.11網(wǎng)絡(luò)具有下述性質(zhì)[14]：如果帶寬需求λAB可行(即滿足式(41)中的約束)，那么所有小于λAB的需求也可行；反之，若λAB不可行，那么所有大于λAB的需求也不可行。于是可通過(guò)嘗試的方法，逐步增大λAB來(lái)尋找不破壞QoS約束的最大帶寬需求。我們采用具有對(duì)數(shù)復(fù)雜度的二分查找法以減少搜索次數(shù)。當(dāng)相鄰兩次搜索結(jié)果小于規(guī)定的精度時(shí)，搜索過(guò)程結(jié)束，此時(shí)的λAB即為路徑的可用帶寬。

5 仿真驗(yàn)證

通過(guò)數(shù)值分析與NS2仿真實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的分析模型和可用帶寬估計(jì)方法。數(shù)值分析和仿真均采用IEEE 802.11b的標(biāo)準(zhǔn)設(shè)置，數(shù)據(jù)速率為11 Mbps。采用 NOAH靜態(tài)路由協(xié)議以避免動(dòng)態(tài)路由協(xié)議帶來(lái)的干擾。

我們?cè)?跳路徑中采用不同的場(chǎng)景配置來(lái)驗(yàn)證本文提出的可用帶寬估計(jì)原則。設(shè)置報(bào)文長(zhǎng)度為1024 byte,QoS約束為單向時(shí)延不超過(guò)150 ms且丟包率不超過(guò)0.5%。場(chǎng)景1：當(dāng)100 kbps的背景流只經(jīng)過(guò)路徑中第3與第4跳鏈路時(shí)分析經(jīng)過(guò)整個(gè)路徑的目標(biāo)流的帶寬需求的可行性。從圖2(a)中可以看出，當(dāng)帶寬需求達(dá)到1.06 Mbps后，目標(biāo)流的時(shí)延約束首先被打破，因此只有小于1.06 Mbps的帶寬需求才是可行的。場(chǎng)景2：當(dāng)100 kbps的背景流經(jīng)過(guò)整個(gè)路徑時(shí)分析只經(jīng)過(guò)第2至第4跳鏈路的目標(biāo)流的帶寬需求的可行性。圖2(b)中，隨著帶寬需求的增加，首先被打破的是背景流的丟包率約束，因此只有小于1.55 Mbps的帶寬需求才是可行的。而由圖2(c)可以看出，在目標(biāo)流的吞吐量達(dá)到其最大值之前，背景流的丟包率已經(jīng)超過(guò)了0.5%，這說(shuō)明目標(biāo)流的可用帶寬小于其最大可達(dá)吞吐量。以上事實(shí)也證明了文獻(xiàn)[1-5]的估計(jì)方法不夠準(zhǔn)確，因?yàn)樗麄儍H考慮了吞吐量而忽略了背景業(yè)務(wù)的QoS需求。

同樣采用上述實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)渑c參數(shù)設(shè)置。令路徑上存在兩個(gè)背景流，背景流1經(jīng)過(guò)第1與第2跳鏈路而背景流2經(jīng)過(guò)第4至第6跳鏈路。當(dāng)其中一個(gè)背景流的負(fù)載固定為100 kbps時(shí)，通過(guò)改變另一個(gè)背景流的負(fù)載來(lái)分析整個(gè)路徑上的可用帶寬。圖3所示實(shí)驗(yàn)結(jié)果與預(yù)期相符，即可用帶寬隨著背景負(fù)載的增大而下降。此外，背景流2對(duì)路徑可用帶寬的影響大于背景流 1，這是因?yàn)楸尘傲?1和背景流2分別經(jīng)過(guò)路徑前部和后部節(jié)點(diǎn)，由于路徑前部節(jié)點(diǎn)受到的干擾更大，因此背景流2帶來(lái)的影響也就更大。圖3同時(shí)證明了可用帶寬估計(jì)方法的準(zhǔn)確性。

最后我們研究可用帶寬與路徑長(zhǎng)度的關(guān)系。為了便于分析，設(shè)置路徑上無(wú)背景負(fù)載，此時(shí)的估計(jì)結(jié)果等價(jià)于全局QoS保障約束條件下的路徑容量。實(shí)驗(yàn)結(jié)果如圖4所示，當(dāng)路徑長(zhǎng)度小于6跳時(shí)，可用帶寬隨跳數(shù)增加而明顯下降；當(dāng)路徑長(zhǎng)度超過(guò) 6跳后，可用帶寬無(wú)明顯變化。上述現(xiàn)象的原因在于，前一種情況下路徑的瓶頸鏈路受到的干擾隨跳數(shù)增加而變大，而后一種情況下瓶頸鏈路受到的干擾不再因跳數(shù)增加而增加。

圖2 可用帶寬估計(jì)原則的合理性

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

本文研究了無(wú)線多跳路徑的性能分析模型與可用帶寬估計(jì)問(wèn)題。詳細(xì)分析了多跳路徑中的干擾現(xiàn)象，并建立了干擾的定量計(jì)算模型。在此基礎(chǔ)上，基于排隊(duì)網(wǎng)絡(luò)理論建立了路徑性能分析模型，并利用此分析模型得出路徑的時(shí)延、丟包率和吞吐量等QoS指標(biāo)。基于分析模型設(shè)計(jì)了能提供QoS保障的可用帶寬估計(jì)方法。本文提出的估計(jì)方法的主要優(yōu)點(diǎn)在于，當(dāng)估計(jì)結(jié)果被使用后不會(huì)破壞網(wǎng)絡(luò)中業(yè)務(wù)流的QoS需求。本文的工作可應(yīng)用于設(shè)計(jì)接納控制方案、速率控制算法與QoS路由協(xié)議。

圖3 路徑可用帶寬估計(jì)結(jié)果

圖4 不同路徑長(zhǎng)度下的路徑可用帶寬

[1]Strauss J,Katabi D,and Kaashoek F.A measurement study of available bandwidth estimation tools[C].3rd ACM SIGCOMM Conference on Internet Measurement,Miami Beach,FL,USA,2003: 39-44.

[2]Sarr C,Chaudet C,Chelius G,et al..Bandwidth estimation for IEEE 802.11-based Ad hoc networks[J].IEEE Transactions on Mobile Computing,2008,7(10): 1228-1241.

[3]Zhao H,Garcia-Palacios E,Wei J,et al..Accurate available bandwidth estimation in IEEE 802.11-based Ad hoc networks[J].Computer Communications,2009,32(6):1050-1057.

[4]Tursunova S,Inoyatov K,and Kim Y-T.Cognitive estimation of the available bandwidth in home/office network considering hidden/exposed terminals[J].IEEE Transactions on Consumer Electronics,2010,56(1): 97-105.

[5]Zhao H,Wang S,Wei J,et al..Model-based approach for available bandwidth prediction in multi-hop wireless networks[J].Science China:Information Sciences,2011,54(9):1916-1927.

[6]Mao G.The maximum throughput of a wireless multi-hop path[J].Mobile Networks and Applications,2011,16(1):46-57.

[7]Ng P C and Liew S C.Throughput analysis of IEEE802.11 multi-hop Ad hoc networks[J].IEEE/ACM Transactions on Networking,2007,15(2): 309-322.

[8]Zhao H,Wang S,Xi Y,et al..Modeling intra-flow contention problem in IEEE 802.11 wireless multi-hop networks[J].IEEE Communications Letters,2010,14(1): 18-20.

[9]Zhao H,Garcia-Palacios E,Song A,et al..Calculating end-to-end throughput capacity in wireless networks with consideration of the hidden nodes and multi-rate terminals[C].Vehicular Technology Conference (VTC Spring),Budapest,Hungary,2011: 1-5.

[10]Xu K,Gerla M,and Bae S.How effective is the IEEE 802.11 RTS/CTS handshake in Ad hoc networks?[C].Proceedings of IEEE GLOBECOM,Taipei,China,2002: 72-76.

[11]Kumar A,Altman E,Miorandi D,et al..New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[J].IEEE/ACM Transactions on Networking,2007,15(3):588-601.

[12]Belch G,Greiner S,Meer H D,et al..Queueing Networks and Markov Chains[M].New York: USA,John Wiley ＆ Sons,Inc.,1998: 423-430.

[13]Sakurai T and Vu H L.MAC access delay of IEEE 802.11 DCF[J].IEEE Transactions on Wireless Communications,2007,6(5): 1702-1710.

[14]Wang K,Yang F,Zhang Q,et al..Modeling path capacity in multi-hop IEEE 802.11 networks for QoS services[J].IEEE Transactions on Wireless Communications,2007,6(2):738-749.