基于M/M/1模型的流量分配算法*

付金鋒 戴小文

西南交通大學電氣工程學院 四川 成都 610097

引言

由于Ad Hoc的易組織和消耗資源低等特性，目前Ad Hoc網絡主要應用在臨時網絡，譬如搶險、救災、軍事等[1-3]。但這些臨時組建的網絡往往資源有限，網絡通信質量偏低，無法滿足實際工作的需要。對于網絡服務質量要求較高，尤其是時延性能要求較高的場景，傳統通信協議無法滿足要求。

針對以上這種情況，本文從多路徑路由協議出發，將多路徑路由過程抽象成M/M/1服務排隊模型，利用拉格朗日方程求得排隊時延最低的流量分配算法，并利用該算法改進按需矢量多路徑路由協議，仿真表明，相比原協議，新協議的時延性能更好。

1 多路徑多跳路由時延模型

Ad Hoc網絡的通信時延包括傳輸時延，處理時延以及排隊時延，針對單個數據包而言，傳輸時延以及處理時延相對固定，而排隊時延受網絡中的擁塞情況影響較大[4]，是本章的主要研究對象。

1.1 多路徑路由時延模型相關研究

多路徑路由是相比單路徑路由而言的，利用多路徑傳輸技術MPT，并行的傳輸數據分組，可以為源節點和目的節點之間提供多條不相交路徑，具有很好的數據分流效果[5]。多路徑路由可以有效減少網絡擁塞和丟包率，降低端到端延遲，提高網絡的穩定性[6-7]，越來越受到大家的重視。

依據網絡流量的測量數據以及中心極限定理[8]，得出了多路經路由中間隊列中大量獨立延遲組成的路徑端到端延遲近似正態分布，并且推理出路徑j對應的端到端時延期望。

針對多路徑路由提出了流量分配模型[9-10]，但這兩篇論文都是假設源節點和目的節點之間的流量平均分配，并沒有考慮最優分配問題。

1.2 基于M/M/1服務模型的流量分配算法

本文對多路徑無線網絡建模參考了多節點M/M/1串聯網絡，網絡模型如圖1所示，其中源節點到目的節點有N條路徑。整個無線網絡可以看成一個有向圖，所有參與多路徑路由的原始節點都是原始圖的一個子圖。

圖1 無線網絡多條多路徑模型

如圖1所示，假定源節點S與目的節點D之間存在N條子路徑，每個子路徑都是M/M/1串聯網絡，用Pi表示，Pi中有L個中繼節點。S到D上存在一個平均到達率為λ的流量，符合泊松分布，平行分布于各條子路徑上的流量為λj，也符合泊松分布，則有：

圖中的μi,j是隊列在路徑上的平均處理速率，bi,j是隊列本身沿路徑發出的流量和路徑間流量之和。假設各條子路徑間的流量也是相對獨立的，即λi,j=λj（i=1...L），由M/M/1排隊服務模型可得：

ρ是服務模型中的排隊強度，即服務器的利用率，Ws,j是流量在隊列中的全部停留時間，Wq,j是流量在隊列中的等待時間，將公式（2）、（3）帶入（4）可得：

式（5）得到的是子路徑λ上的總時延，當優化目標為系統時延時，目標函數如式（6）所示：

此時考慮到式1對λ的約束，可以構建拉格朗日乘數法進一步確定具有最小時延的流量最優分配方案：

式（7）中的γ是拉格朗日乘數。要確定時延最低的流量分配方案即轉換成求式7的最優解。公式（7）對λj求偏導可得：

從式（8）中可以看出，最優解與j的取值無關，繼續轉換可得：

假定流量模型中各子路徑流量相對獨立，各個子路徑處理速率相同，路徑間流量相同，即μi,j=μj(j=1,2,...,N)，bij=bj(j=1,2,...,N)，則由式（9）可知，流量分配最優解只與路徑長度和處理速率有關。假定子路徑j上傳輸時延為dj，根據M/M/1服務模型得出dj=1/(μij-(λj+bj))，代入式（9）得：

由式（10）可知，在不考慮路徑長度差異的情況下，要將最優流量分配給第i條路徑λi，應滿足（λi+bi）di/μi不變。

2 基于流量分配算法的協議改進

根據M/M/1串聯網絡模型得到流量分配最優解后，發送端節點需要根據算法結果將業務流量分配到各個子路徑上。由上述分析可知，流量分配與隊列在路徑上的平均處理速率μj，隊列本身沿路徑發出的流量和路徑間流量之和bj，子路徑上傳輸時延dj有關。其中，μj和bj都是定值，所以最優流量分配即根據各個子路徑的傳輸時延進行流量分配。

2.1 路徑傳輸時延測量

目前測量路徑上的端到端時延最通用的方法是利用ICMP報文記錄數據包沿路徑從源節點發出到返回所花費的時間。假設源節點收到ICMP探測包與發送ICMP探測包的時間差值為RTT，則該路徑上的傳輸時延即為RTT/2。由于單次測量數據具有不確定性，通常會對RTT進行整形處理，整形公式如下：

式（11）中的α是整形參數。根據馮美玉等學者指出當整形參數α為0.2時，整形效果較好，波動幅度較小。

2.2 流量分配策略

由式（11）可以得到各個子路徑的傳輸時延RTTpt，又由上述的流量分配算法得可以出當流量分配與隊列在路徑上的平均處理速率μj，隊列本身沿路徑發出的流量和路徑間流量之和bj，子路徑上傳輸時延dj滿足(λi+bi)di/μi(di=RTTpt)不變時，時延最小。假定路徑j上的流量分配權值歸一化值為Wj，則有：

由式（12）和式（10）得出當時延最小時，路徑j的流量分配權值如下：

假定Gj為流量開始分配時子路徑j上已分配的流量，則各個子路徑上已分配的權重Wh為：

為控制數據包發送速率，應優先將流量分配給已分配權值Wh值較小的路徑。

2.3 算法流程

求得流量最優分配方案后，源節點需將業務流量按照計算所得的最優分配權值分配給各條子路徑。假定業務流量的最小分配單元是數據包，流量分配算法描述如下：

Step1：利用AOMDV協議，獲取多條源節點到目的節點的不相交路徑；

Step2：利用ICMP探測包獲取各條子路徑上的傳輸時延RTT并通過式（11）對RTT進行整形處理；

Step3：根據Step2整形處理后得到的RTT和式（14）計算子路徑已分配權值，優先將流量分配給Wh值較小的路徑；

Step4：重復上述步驟直至流量分配完畢。

按照上述算法分配流量不僅能降低排隊時延，還能控制數據包的發送速率，減小突發流量的影響。

3 仿真結果與分析

為了驗證新算法的時延性能，本文利用NS3仿真軟件進行仿真，將新算法與傳統算法進行比較，部分仿真參數見表1。

表1 部分仿真參數列表

按照表1所示參數搭建好仿真模型后，利用AOMDV協議獲取源節點到目的節點的3條不相交路徑，有效帶寬均為2Mbps,背景流量為CBR業務，數據傳輸速率分別為40/60/80 bits/s，數據包最大長度為256 Bytes，數據包產生速率為100packages/s，源節點與目的節點隨機，測量時間間隔T為5s。假設仿真開始時，3條路徑上的流量分配采用平均分配的策略。新算法與傳統算法在3條路徑上的流量分配如圖2、圖3所示。

從圖2和圖3可以看出，新算法給3條路徑分配的流量比較平穩，而傳統算法的流量基本都集中在其中1條路徑上，這是因為新算法在分配流量時會優先將流量分配給流量不飽和的路徑，不會出現某條路徑流量過大的情況。合理的分流可以有效地防止網絡中出現擁塞，從而降低時延。

圖2 新算法歸一化流量分配

圖3 傳統算法歸一化流量分配

新算法和舊算法的平均分組傳輸時延如圖4所示。

圖4 兩種算法的平均分組傳輸時延

從圖4可以看出，總體上新算法的平均分組時延要低于傳統算法，這是因為新算法分配流量時是按照系統排隊時延最低的方案進行分配的，同時對網絡中的流量進行了分流，防止某條路徑出現流量過多，阻塞網絡的情況。綜上，新算法的時延性能明顯優于傳統算法。

4 結束語

本文基于傳統多路徑路由協議，利用排隊服務模型M/M/1搭建多路徑多跳網絡時延模型，通過拉格朗日方程求出排隊時延最優解，并利用結果提出了基于流量分配的新算法，仿真結果表明，該算法相比傳統算法，時延性能有較大提高，同時中和了網絡的流量分配，防止網絡中出現擁塞，對于時延性能要求較高的場景有一定參考意義。