基于網絡演算的無線Mesh網時延上界

魏德賓，程 健，楊 力，顏佐任

(1. 大連大學通信與網絡重點實驗室，遼寧 大連 116622；2. 大連大學信息工程學院，遼寧 大連 116622；3. 南京理工大學自動化學院，江蘇 南京 210094)

1 引言

無線Mesh網(Wireless Mesh Networks，WMNs)作為一種寬帶接入技術，與傳統無線網絡相比，它具有節點移動靈活、接入方式多樣等優勢，近些年備受研究人員關注[1]。該網絡主要由三層構成，分別是Internet接入層、核心網層和輸出接入層。核心網層介于Internet接入層與輸出接入層之間，是影響WMNs性能的關鍵，針對核心網性能的分析將為WMNs架構設計、網絡優化等帶來參考。

端到端時延是分析研究核心網網絡性能的重要指標，也是衡量網絡服務質量(QoS)和用戶體驗的重要參數，時延上界的求解對WMNs的發展和應用具有現實意義。它主要受到鏈路上各節點的服務延遲、鏈路節點個數、調度策略、網絡拓撲、流量分配方式等綜合因素的影響。端到端時延上界分析的準確性直接影響到網絡QoS保障水平，同時也是網絡接納控制、路由優化的重要依據。

網絡演算(Network Calculus，NC)是一種有效計算端到端時延上界的數學工具，很多學者對此進行深入研究。文獻[2]基于NC理論對單、多兩種節點形成兩種不同的到達和服務曲線模型對時延上界進行緊致計算評估。李慶華等人[3]針對無線自組網，基于已存在的鏈路吞吐量模型，運用網絡演算計算了節點的端到端時延上界、時延抖動上界等結果。陳志剛等人[4]利用網絡演算理論，通過模擬實驗和數值分析，對無線多跳網進行推導，從而確保了無線多跳網絡的QoS，從而證實了理論結果的正確性。文獻[5]從降低端到端時延上界的計算復雜度角度出發，提出LAC(Loacl Arrival Curve)組合分析方法，但是此方法計算的時延上界緊密度卻低于NC理論。在新型應用上，文獻[6]利用隨機網絡演算，推導了物聯網業務流的到達曲線和服務曲線，求解了機器業務流的端到端時延上界。文獻[7]運用NC對軟件定義車聯網(SD-IoV)中傳輸數據建立模型并引入遺傳算法，最終設計出符合SD-IoV的路由算法進行路徑傳輸。文獻[8]針對5G蜂窩移動通信技術中的云無線接入網，對不同優先級的業務流計算了其端到端時延及數據積壓上界。文獻[9]研究了衛星5G一體化網絡中各組件之間連接關系的串聯模型，并基于該模型給出了端到端延遲計算函數。

無線Mesh網的早期考慮到網絡易于管理和配置，主要使用單徑傳輸。但由于通信需求的增加，單徑傳輸易導致流量集中在某條路徑形成“熱線”，端到端時延會變得很大。多徑傳輸[10]可規避形成單路徑“熱線”情況，降低網絡端到端時延，提高網絡效率。

為了體現WMNs多徑路由的優勢，文獻[11]提出優化的Fortified Ant協議，其創新之處在于將排序算法納入傳統蟻群算法中，同時兼并多徑傳輸協議，且端到端時延性能提升在仿真中確實得到驗證。與以上研究有異曲同工之妙的是，李偉等人[12]為了提高WMNs全局收斂速度，在傳統蟻群算法中融合細菌覓食算法，仿真實現了WMNs高可靠低時延和規避局部最優的效果。

文獻[13]基于傳統的隊列模型方法，考慮了無線mesh網絡的無線特性，分析了網關節點的時延，但是未考慮其鏈路不確定性和網絡演算的理論分析使模擬實驗無法反映網絡的實際QoS性能。文獻[14]基于網絡演算理論分析了數據包在無線Mesh網絡單路徑傳輸系統中的端到端時延上界以及多路徑傳輸系統中的不同路徑間時延抖動上界，然而并未考慮并計算多路徑傳輸系統的端到端時延上界性能。劉宴兵等人[15]提出了一種針對云服務網絡的參數建模分析方法，從路徑時延組成上明確給出了端到端時延上界和數據積壓上界的定量數學解析式，但是并未討論單節點時延，而且也未與實際仿真值作對比分析。以上文獻都未考慮當前節點的處理時延對下一個節點的到達曲線產生影響從而導致時延上界計算不緊致的問題。本文主要研究的是無線Mesh網端到端時延近似上界，是對文獻[13-15]等研究的一個拓展。

本文內容結構組織如下：第2節簡介網絡演算的基本定義、定理；第3節是無線Mesh網端到端時延上界分析計算過程，從單節點到單路徑傳輸系統，再到多路徑傳輸系統層層遞進分析，計算和驗證端到端時延上界；第4節是對第3節結論的數值分析；第5節是結束語。

2 網絡演算基礎

2.1 網絡演算的基本定義與定理

由Cruz開創并由Chang和Boudec等人完善的網絡演算理論是一種新型數學工具，是基于最小加代數理論的一組結論，主要作用是分析網絡隊列系統性能，它最初是為了保障網絡服務質量，解決資源預留等問題，目前主要應用于網絡的QoS分析和保障。網絡演算的基本定義以及積壓界限和時延界限等介紹如下[16]：

定義1(廣義增函數)：設f是一個函數，如果對于任意的0≤x≤y，都有f(x)≤f(y)，則稱f為廣義增函數。

定義2(最小加卷積)：設f和g為廣義增函數，f和g的最小加卷積運算為

其中inf表示函數的下確界。

用A(t)和A*(t)分別表示(0，t]時間內數據流相對某一系統的到達過程和離開過程。

定義3(到達曲線)：給定一個廣義增函數α(t)，若對于所有的0≤s≤t，若數據流到達過程A(t)，滿足A(t)-A(s)≤α(t-s)，則稱α是A(t)的到達曲線。

定義4(服務曲線)：設數據流具有到達過程A(t)和離開過程A*(t)，β(t)為廣義增函數，若對于所有的0≤t0≤t，存在A*(t)-A(t0)≥β(t-t0)，則稱系統為數據流提供服務曲線β(t)。

端到端的數據流往往經過了多個網絡節點，這些網絡節點作為整體提供的服務曲線可由各個網絡節點的服務曲線計算得到。

定理1(節點串聯)：假設一個數據流依次穿過服務曲線分別為β1(t)，β2(t)，…，βn(t)的n個網絡節點，則這n個網絡節點串聯后提供的總服務曲線為β=β1?β2?…?βn。

定理2(積壓界限)：假設一個數據流受限于到達曲線α，通過一個提供服務曲線β的系統來傳輸，則系統的積壓上界為到達曲線與服務曲線之間的最大垂直距離，即

定理3(時延界限)：假定一個數據流受限于到達曲線α，通過一個提供服務曲線β的系統來傳輸，則系統的時延上界為到達曲線與服務曲線之間的最大水平距離，即

d(t)≤h(α，β)

2.2 數據流到達曲線

基于定義3，設ρ是數據流的平均到達速率，σ是數據流的最大突發量，以α(t)=ρt+σ為到達曲線的數據流量稱為(ρ，σ)模型。此模型形象描繪了信息流傳輸過程中的平均行為，模型的到達曲線數學表達式為

(1)

模型的到達曲線如圖1所示。

圖1 到達曲線

2.3 數據流服務曲線

基于定義4，采用延遲—速率函數LR(Latency-Rate)來表示服務曲線β(t)，表示形式如下

(2)

其中R為服務速率，T是數據流在系統中的服務延遲，可以認為是包處理時延，表示如下

T=L/R+L/C

(3)

其中L表示(0，t]內的最大包長，C是最大鏈路速率。這里，平均到達速率ρ≤R

3 無線Mesh網端到端時延上界

與以往計算方式不同，本文時延上界主要從單節點、單路徑和多路徑層層遞進分析計算，這正是對文獻[13-15]的內容擴展，其目的是為了提高時延上界計算的準確度。

3.1 單節點時延上界

當網絡數據流A(t)到達一個節點，受到達曲線α的約束，并通過服務曲線β提供服務，單節點的時延由系統緩存的排隊時延和處理時延構成，其中處理時延為延遲參數T，而排隊時延Dqueue上界看作是最大繁忙間隔[17][18]。

定理4：設數據流到達曲線為α(t)如式(1)所示，服務能力為β(t)的傳輸服務系統，其單節點的排隊延遲上界為

(4)

證明：當t>0時，此時α(t)=ρt+σ

Dqueue=inf{t≥0：ρt+σ-Rt≤0}

=inf{t≥0：Rt-ρt≥σ}

=inf{t≥0：(R-ρ)t≥σ}

所以，單節點i的時延上界為

(5)

3.2 單路徑傳輸系統端到端時延上界

無線Mesh網單路徑傳輸如圖2所示。假設網絡中存在n個節點，第i個節點受到達曲線αi(t)=σi+ρit的約束，服務能力表示為βi=Ri[t-Ti]+，i=1，2，…，n。這里將單路徑的端到端時延計算分為兩部分：一部分是可變時延，主要是系統緩沖區排隊時延；另一部分是固定時延，主要包括節點系統處理時延、轉發時延和鏈路傳播時延。而對于固定時延，本文假設n個節點相鄰兩個節點之間的固定時延依次為d1，d2，…，dn-1。

圖2 單路徑傳輸

定理5：設有一條路徑包含n個節點，第i個節點數據流的到達曲線為αi(t)=σi+ρit，傳輸服務系統能力為βi=Ri[t-Ti]+，則節點1到n的單路徑端到端延遲為

(6)

證明 用數學歸納法證明：

由上可證明式(6)成立。

2)假設當n=k-1時，式(6)成立，即

3)當n=k時：

3.3 多路徑傳輸系統端到端時延上界

圖3 多路徑傳輸

多路徑傳輸系統可看作是單路徑傳輸系統的復合模式。假設多路徑傳輸系統中各條路徑產生的時延互不影響，此外本文主要考慮的是時延的上界，因而多路徑傳輸時所產生的時延上界為每條路徑上時延的最大值加上聚合節點的時延上界。

定理6：假設網絡中從節點g到a有m條路徑，第i條路徑上有ni個節點，各節點的服務能力分別表示為βa=Ra[t-Ta]+，β(i，j)=R(i，j)[t-T(i，j)]+，βg=Rg[t-Tg]+，i=1，2，…，m；j=1，2，…，ni，則從g到a的延遲為

(7)

證：由定理5每條路徑上的時延最大值

(8)

(9)

其中Ta=L/Ra，ρa=ρ1+ρ2+…+ρm。

綜上，結合(8)和(9)，得到多路徑傳輸系統端到端時延上界滿足

4 仿真

本節分別從單路徑傳輸系統和多路徑傳輸系統兩個角度進行端到端時延上界數值仿真驗證。在仿真中，針對單路徑傳輸系統，從兩方面分析，一是將本文方法與實際仿真時延上界、文獻[15]時延上界進行比較來驗證結果，二是通過三種不同特征的數據流來刻畫本文計算的端到端時延上界在不同條件下的影響。

由上述第二條，三種不同流的長期平均速率和突發量數值分別假設如下：流X為120Mbit/s，200kbits；流Y為200Mbit/s，200kbits；流Z為120Mbit/s，300kbits。其它網絡參數采用表1中的設置參數。

表1 網絡實驗參數設置

4.1 單路徑傳輸系統端到端時延上界

用OPNET仿真工具設置一個單路徑傳輸系統，見下圖4。實驗場景：1000m*1000m，源節點router1的客戶端發送速率為120Mbit/s，各路由器router的服務速率初始值設為150Mbit/s，每個節點緩存區大小固定為64個數據包，router1到router7依次相距250m。

仿真過程主要通過發送一系列的測試數據分組來統計端到端時延，首先定義數據包格式64bit，然后在全局場景中設置路由器及客戶端，在Node Module中配置如上實驗參數，最后設置仿真開始時間為0s，持續時間為20s，時延上界仿真結果在View Results中查看。

圖4 單傳輸系統場景仿真圖

圖5表示服務速率為150Mbit/s時，在模擬時間內的單路徑傳輸系統端到端時延。

而為了保持以下仿真分析的一致性，下文統一采用流X中的服務參數，根據圖5仿真得到的網絡端到端時延上界值，與本文計算得到的端到端時延上界、文獻[15]端到端時延上界進行比較，結果如圖6所示。

圖5 R=150Mbit/s時的端到端時延

圖6 三者端到端時延上界分析

從圖6中可看出，相較于文獻[15]端到端時延上界，本文方法計算的時延上界更接近仿真時延上界，這是因為本文考慮了前一個節點的處理時延對后一個節點到達曲線的影響，前后節點的時延相關是時間上的連續關系，與節點的服務規律和到達規律獨立并未沖突。另外值得注意的是，當網絡服務速率相對較小時，端到端時延上界與仿真時延上界結果偏差較大，這是因為前期較小的網絡服務速率會引起節點數據積壓造成排隊時延增大，并經過網絡演算卷積計算后，時延相對偏大。而節點服務能力隨著網絡服務速率的增大而提升后，兩者偏差會越來越小，驗證了式(7)是成立的。

另外，在單路徑傳輸系統中考慮X，Y，Z三種數據流，分別從節點個數、服務速率、權值分配三方面，考慮對端到端時延上界的影響。

圖7顯示單路徑傳輸系統中鏈路節點數對端到端時延上界的影響，可以看出，時延都是隨著鏈路節點數增加而增大。從式(6)看，當鏈路節點數增加時，時延主要受平均速率的約束在不斷增大，因此網絡演算的卷積計算特點更能反映真實的網絡性能。

圖7 單路徑端到端時延和鏈路節點個數關系

圖8顯示了端到端時延和網絡服務速率之間的關系，不難看出，兩者呈負相關，即端到端時延隨著網絡服務速率增大而減少，這與實際網絡情況一致。另外可以看出服務速率小于350Mbit/s時，端到端時延隨著網絡服務速率增大下降的幅度較大，大于350Mbit/s時，下降幅度趨于平穩。數據流X和Z的端到端時延和網絡服務速率之間的曲線幾乎重疊，這是因為兩種服務有相同的σ，而節點間的輸入輸出關系正隨著網絡演算的卷積值而變化，主要受突發量的影響，但影響并不大，但是Z的時延要略大一點。而X和Y的端到端時延和網絡服務速率之間的曲線有明顯的差別正驗證了這點。

圖8 端到端時延和網絡服務速率的關系

圖9顯示了端到端時延在固定鏈路節點個數的情況下與服務速率權值分配之間的關系。假設總服務速率800Mbit/s，數據流X、Y、Z的服務速率分配權值分別為0.2，0.5，0.3。如下圖所示，三者端到端時延整體都呈上升趨勢，其中X端到端時延最高，Y次之，Z時延最低，這與分析的結果是一致的。因為在相同到達速率情況下，Z分配到的服務速率大于X分配的速率，雖然突發量也會對時延造成影響，但是影響卻不大，自然計算出的端到端時延是較小的；而Y與X相比時，到達速率大雖有影響，但對于Y分配到的最高的服務速率，同樣影響就不那么明顯了。

圖9 端到端時延和三種服務權值分配的關系

4.2 多路徑傳輸系統端到端時延上界

多路徑傳輸可看作是單路徑傳輸的復合模型，從式(6)和式(7)可看出，不同特征數據流對多路徑傳輸系統端到端時延上界的影響與單路徑相同。根據定理6，多路徑仿真主要從路徑條數、網絡服務速率兩因素分析對端到端時延上界的影響。

由圖3，本文假設源節點g輸出的數據分為三條鏈路到達節點a，鏈路服務速率分別設置為90Mbit/s，100Mbit/s，110Mbit/s。同時為了對比分析的方便有效，在多路徑下本文只討論分析數據流X在不同情況下的端到端時延上界的相應變化情況。圖10表明了在多路徑情況下兩種流量分配方式隨著網絡服務速率的增加端到端時延上界的變化情況。即時延上界都隨著服務速率的增加而逐漸減小，且減小幅度也在降低，另外還可看出權值分配方式對應時延更低，說明根據不同鏈路的服務需求分配合適的流量效果更好，降低了部分鏈路因過負荷導致網絡擁塞從而影響全局端到端時延上界。

圖10 多路徑時延上界和網絡服務速率關系

圖11表示在鏈路服務速率350Mb/s，源節點g和節點a服務速率都為500Mb/s仿真條件下，多路徑條數和流量分配方式對端到端時延上界的影響，仿真分析數據流X在不同參數條件下的端到端時延上界的結果。很明顯兩種流量分配方式的端到端時延上界都隨著多路徑條數增加而增加，權值分配獲取到的端到端時延上界比平均分配時延上界低，這同樣歸功于權值分配方式規避了平均分配方式予鏈路等量數據而導致部分鏈路負荷過大，造成網絡擁塞，從而影響多路徑傳輸系統端到端時延上界。

圖11 多路徑時延上界和多路徑條數的關系

5 結論

本文提出的基于網絡演算的無線Mesh網端到端時延上界分析方法，利用(ρ，σ)模型作為數據流到達曲線，延遲-速率函數LR作為數據流服務曲線，同時考慮前一個節點的處理時延對后一個節點到達曲線的影響，推導出了單節點時延上界、單路徑傳輸系統端到端時延上界和多路徑傳輸系統端到端時延上界表達式。仿真實驗表明，與傳統方法相比，本文方法計算得到的時延上界更接近仿真值。為了更準確地分析，在本文計算出的時延上界基礎上計算端到端數據積壓上界以及時延抖動上界來約束傳輸系統進行負載均衡是本文下一步的研究方向。