魏德賓,程 健,楊 力,顏佐任
(1. 大連大學(xué)通信與網(wǎng)絡(luò)重點實驗室,遼寧 大連 116622;2. 大連大學(xué)信息工程學(xué)院,遼寧 大連 116622;3. 南京理工大學(xué)自動化學(xué)院,江蘇 南京 210094)
無線Mesh網(wǎng)(Wireless Mesh Networks,WMNs)作為一種寬帶接入技術(shù),與傳統(tǒng)無線網(wǎng)絡(luò)相比,它具有節(jié)點移動靈活、接入方式多樣等優(yōu)勢,近些年備受研究人員關(guān)注[1]。該網(wǎng)絡(luò)主要由三層構(gòu)成,分別是Internet接入層、核心網(wǎng)層和輸出接入層。核心網(wǎng)層介于Internet接入層與輸出接入層之間,是影響WMNs性能的關(guān)鍵,針對核心網(wǎng)性能的分析將為WMNs架構(gòu)設(shè)計、網(wǎng)絡(luò)優(yōu)化等帶來參考。
端到端時延是分析研究核心網(wǎng)網(wǎng)絡(luò)性能的重要指標(biāo),也是衡量網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)和用戶體驗的重要參數(shù),時延上界的求解對WMNs的發(fā)展和應(yīng)用具有現(xiàn)實意義。它主要受到鏈路上各節(jié)點的服務(wù)延遲、鏈路節(jié)點個數(shù)、調(diào)度策略、網(wǎng)絡(luò)拓?fù)?、流量分配方式等綜合因素的影響。端到端時延上界分析的準(zhǔn)確性直接影響到網(wǎng)絡(luò)QoS保障水平,同時也是網(wǎng)絡(luò)接納控制、路由優(yōu)化的重要依據(jù)。
網(wǎng)絡(luò)演算(Network Calculus,NC)是一種有效計算端到端時延上界的數(shù)學(xué)工具,很多學(xué)者對此進行深入研究。文獻[2]基于NC理論對單、多兩種節(jié)點形成兩種不同的到達和服務(wù)曲線模型對時延上界進行緊致計算評估。李慶華等人[3]針對無線自組網(wǎng),基于已存在的鏈路吞吐量模型,運用網(wǎng)絡(luò)演算計算了節(jié)點的端到端時延上界、時延抖動上界等結(jié)果。陳志剛等人[4]利用網(wǎng)絡(luò)演算理論,通過模擬實驗和數(shù)值分析,對無線多跳網(wǎng)進行推導(dǎo),從而確保了無線多跳網(wǎng)絡(luò)的QoS,從而證實了理論結(jié)果的正確性。文獻[5]從降低端到端時延上界的計算復(fù)雜度角度出發(fā),提出LAC(Loacl Arrival Curve)組合分析方法,但是此方法計算的時延上界緊密度卻低于NC理論。在新型應(yīng)用上,文獻[6]利用隨機網(wǎng)絡(luò)演算,推導(dǎo)了物聯(lián)網(wǎng)業(yè)務(wù)流的到達曲線和服務(wù)曲線,求解了機器業(yè)務(wù)流的端到端時延上界。文獻[7]運用NC對軟件定義車聯(lián)網(wǎng)(SD-IoV)中傳輸數(shù)據(jù)建立模型并引入遺傳算法,最終設(shè)計出符合SD-IoV的路由算法進行路徑傳輸。文獻[8]針對5G蜂窩移動通信技術(shù)中的云無線接入網(wǎng),對不同優(yōu)先級的業(yè)務(wù)流計算了其端到端時延及數(shù)據(jù)積壓上界。文獻[9]研究了衛(wèi)星5G一體化網(wǎng)絡(luò)中各組件之間連接關(guān)系的串聯(lián)模型,并基于該模型給出了端到端延遲計算函數(shù)。
無線Mesh網(wǎng)的早期考慮到網(wǎng)絡(luò)易于管理和配置,主要使用單徑傳輸。但由于通信需求的增加,單徑傳輸易導(dǎo)致流量集中在某條路徑形成“熱線”,端到端時延會變得很大。多徑傳輸[10]可規(guī)避形成單路徑“熱線”情況,降低網(wǎng)絡(luò)端到端時延,提高網(wǎng)絡(luò)效率。
為了體現(xiàn)WMNs多徑路由的優(yōu)勢,文獻[11]提出優(yōu)化的Fortified Ant協(xié)議,其創(chuàng)新之處在于將排序算法納入傳統(tǒng)蟻群算法中,同時兼并多徑傳輸協(xié)議,且端到端時延性能提升在仿真中確實得到驗證。與以上研究有異曲同工之妙的是,李偉等人[12]為了提高WMNs全局收斂速度,在傳統(tǒng)蟻群算法中融合細(xì)菌覓食算法,仿真實現(xiàn)了WMNs高可靠低時延和規(guī)避局部最優(yōu)的效果。
文獻[13]基于傳統(tǒng)的隊列模型方法,考慮了無線mesh網(wǎng)絡(luò)的無線特性,分析了網(wǎng)關(guān)節(jié)點的時延,但是未考慮其鏈路不確定性和網(wǎng)絡(luò)演算的理論分析使模擬實驗無法反映網(wǎng)絡(luò)的實際QoS性能。文獻[14]基于網(wǎng)絡(luò)演算理論分析了數(shù)據(jù)包在無線Mesh網(wǎng)絡(luò)單路徑傳輸系統(tǒng)中的端到端時延上界以及多路徑傳輸系統(tǒng)中的不同路徑間時延抖動上界,然而并未考慮并計算多路徑傳輸系統(tǒng)的端到端時延上界性能。劉宴兵等人[15]提出了一種針對云服務(wù)網(wǎng)絡(luò)的參數(shù)建模分析方法,從路徑時延組成上明確給出了端到端時延上界和數(shù)據(jù)積壓上界的定量數(shù)學(xué)解析式,但是并未討論單節(jié)點時延,而且也未與實際仿真值作對比分析。以上文獻都未考慮當(dāng)前節(jié)點的處理時延對下一個節(jié)點的到達曲線產(chǎn)生影響從而導(dǎo)致時延上界計算不緊致的問題。本文主要研究的是無線Mesh網(wǎng)端到端時延近似上界,是對文獻[13-15]等研究的一個拓展。
本文內(nèi)容結(jié)構(gòu)組織如下:第2節(jié)簡介網(wǎng)絡(luò)演算的基本定義、定理;第3節(jié)是無線Mesh網(wǎng)端到端時延上界分析計算過程,從單節(jié)點到單路徑傳輸系統(tǒng),再到多路徑傳輸系統(tǒng)層層遞進分析,計算和驗證端到端時延上界;第4節(jié)是對第3節(jié)結(jié)論的數(shù)值分析;第5節(jié)是結(jié)束語。
由Cruz開創(chuàng)并由Chang和Boudec等人完善的網(wǎng)絡(luò)演算理論是一種新型數(shù)學(xué)工具,是基于最小加代數(shù)理論的一組結(jié)論,主要作用是分析網(wǎng)絡(luò)隊列系統(tǒng)性能,它最初是為了保障網(wǎng)絡(luò)服務(wù)質(zhì)量,解決資源預(yù)留等問題,目前主要應(yīng)用于網(wǎng)絡(luò)的QoS分析和保障。網(wǎng)絡(luò)演算的基本定義以及積壓界限和時延界限等介紹如下[16]:
定義1(廣義增函數(shù)):設(shè)f是一個函數(shù),如果對于任意的0≤x≤y,都有f(x)≤f(y),則稱f為廣義增函數(shù)。
定義2(最小加卷積):設(shè)f和g為廣義增函數(shù),f和g的最小加卷積運算為
其中inf表示函數(shù)的下確界。
用A(t)和A*(t)分別表示(0,t]時間內(nèi)數(shù)據(jù)流相對某一系統(tǒng)的到達過程和離開過程。
定義3(到達曲線):給定一個廣義增函數(shù)α(t),若對于所有的0≤s≤t,若數(shù)據(jù)流到達過程A(t),滿足A(t)-A(s)≤α(t-s),則稱α是A(t)的到達曲線。
定義4(服務(wù)曲線):設(shè)數(shù)據(jù)流具有到達過程A(t)和離開過程A*(t),β(t)為廣義增函數(shù),若對于所有的0≤t0≤t,存在A*(t)-A(t0)≥β(t-t0),則稱系統(tǒng)為數(shù)據(jù)流提供服務(wù)曲線β(t)。
端到端的數(shù)據(jù)流往往經(jīng)過了多個網(wǎng)絡(luò)節(jié)點,這些網(wǎng)絡(luò)節(jié)點作為整體提供的服務(wù)曲線可由各個網(wǎng)絡(luò)節(jié)點的服務(wù)曲線計算得到。
定理1(節(jié)點串聯(lián)):假設(shè)一個數(shù)據(jù)流依次穿過服務(wù)曲線分別為β1(t),β2(t),…,βn(t)的n個網(wǎng)絡(luò)節(jié)點,則這n個網(wǎng)絡(luò)節(jié)點串聯(lián)后提供的總服務(wù)曲線為β=β1?β2?…?βn。
定理2(積壓界限):假設(shè)一個數(shù)據(jù)流受限于到達曲線α,通過一個提供服務(wù)曲線β的系統(tǒng)來傳輸,則系統(tǒng)的積壓上界為到達曲線與服務(wù)曲線之間的最大垂直距離,即
定理3(時延界限):假定一個數(shù)據(jù)流受限于到達曲線α,通過一個提供服務(wù)曲線β的系統(tǒng)來傳輸,則系統(tǒng)的時延上界為到達曲線與服務(wù)曲線之間的最大水平距離,即
d(t)≤h(α,β)
基于定義3,設(shè)ρ是數(shù)據(jù)流的平均到達速率,σ是數(shù)據(jù)流的最大突發(fā)量,以α(t)=ρt+σ為到達曲線的數(shù)據(jù)流量稱為(ρ,σ)模型。此模型形象描繪了信息流傳輸過程中的平均行為,模型的到達曲線數(shù)學(xué)表達式為
(1)
模型的到達曲線如圖1所示。
圖1 到達曲線
基于定義4,采用延遲—速率函數(shù)LR(Latency-Rate)來表示服務(wù)曲線β(t),表示形式如下
(2)
其中R為服務(wù)速率,T是數(shù)據(jù)流在系統(tǒng)中的服務(wù)延遲,可以認(rèn)為是包處理時延,表示如下
T=L/R+L/C
(3)
其中L表示(0,t]內(nèi)的最大包長,C是最大鏈路速率。這里,平均到達速率ρ≤R
與以往計算方式不同,本文時延上界主要從單節(jié)點、單路徑和多路徑層層遞進分析計算,這正是對文獻[13-15]的內(nèi)容擴展,其目的是為了提高時延上界計算的準(zhǔn)確度。
當(dāng)網(wǎng)絡(luò)數(shù)據(jù)流A(t)到達一個節(jié)點,受到達曲線α的約束,并通過服務(wù)曲線β提供服務(wù),單節(jié)點的時延由系統(tǒng)緩存的排隊時延和處理時延構(gòu)成,其中處理時延為延遲參數(shù)T,而排隊時延Dqueue上界看作是最大繁忙間隔[17][18]。
定理4:設(shè)數(shù)據(jù)流到達曲線為α(t)如式(1)所示,服務(wù)能力為β(t)的傳輸服務(wù)系統(tǒng),其單節(jié)點的排隊延遲上界為
(4)
證明:當(dāng)t>0時,此時α(t)=ρt+σ
Dqueue=inf{t≥0:ρt+σ-Rt≤0}
=inf{t≥0:Rt-ρt≥σ}
=inf{t≥0:(R-ρ)t≥σ}
所以,單節(jié)點i的時延上界為
(5)
無線Mesh網(wǎng)單路徑傳輸如圖2所示。假設(shè)網(wǎng)絡(luò)中存在n個節(jié)點,第i個節(jié)點受到達曲線αi(t)=σi+ρit的約束,服務(wù)能力表示為βi=Ri[t-Ti]+,i=1,2,…,n。這里將單路徑的端到端時延計算分為兩部分:一部分是可變時延,主要是系統(tǒng)緩沖區(qū)排隊時延;另一部分是固定時延,主要包括節(jié)點系統(tǒng)處理時延、轉(zhuǎn)發(fā)時延和鏈路傳播時延。而對于固定時延,本文假設(shè)n個節(jié)點相鄰兩個節(jié)點之間的固定時延依次為d1,d2,…,dn-1。
圖2 單路徑傳輸
定理5:設(shè)有一條路徑包含n個節(jié)點,第i個節(jié)點數(shù)據(jù)流的到達曲線為αi(t)=σi+ρit,傳輸服務(wù)系統(tǒng)能力為βi=Ri[t-Ti]+,則節(jié)點1到n的單路徑端到端延遲為
(6)
證明 用數(shù)學(xué)歸納法證明:
由上可證明式(6)成立。
2)假設(shè)當(dāng)n=k-1時,式(6)成立,即
3)當(dāng)n=k時:
圖3 多路徑傳輸
多路徑傳輸系統(tǒng)可看作是單路徑傳輸系統(tǒng)的復(fù)合模式。假設(shè)多路徑傳輸系統(tǒng)中各條路徑產(chǎn)生的時延互不影響,此外本文主要考慮的是時延的上界,因而多路徑傳輸時所產(chǎn)生的時延上界為每條路徑上時延的最大值加上聚合節(jié)點的時延上界。
定理6:假設(shè)網(wǎng)絡(luò)中從節(jié)點g到a有m條路徑,第i條路徑上有ni個節(jié)點,各節(jié)點的服務(wù)能力分別表示為β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。
綜上,結(jié)合(8)和(9),得到多路徑傳輸系統(tǒng)端到端時延上界滿足
本節(jié)分別從單路徑傳輸系統(tǒng)和多路徑傳輸系統(tǒng)兩個角度進行端到端時延上界數(shù)值仿真驗證。在仿真中,針對單路徑傳輸系統(tǒng),從兩方面分析,一是將本文方法與實際仿真時延上界、文獻[15]時延上界進行比較來驗證結(jié)果,二是通過三種不同特征的數(shù)據(jù)流來刻畫本文計算的端到端時延上界在不同條件下的影響。
由上述第二條,三種不同流的長期平均速率和突發(fā)量數(shù)值分別假設(shè)如下:流X為120Mbit/s,200kbits;流Y為200Mbit/s,200kbits;流Z為120Mbit/s,300kbits。其它網(wǎng)絡(luò)參數(shù)采用表1中的設(shè)置參數(shù)。
表1 網(wǎng)絡(luò)實驗參數(shù)設(shè)置
用OPNET仿真工具設(shè)置一個單路徑傳輸系統(tǒng),見下圖4。實驗場景:1000m*1000m,源節(jié)點router1的客戶端發(fā)送速率為120Mbit/s,各路由器router的服務(wù)速率初始值設(shè)為150Mbit/s,每個節(jié)點緩存區(qū)大小固定為64個數(shù)據(jù)包,router1到router7依次相距250m。
仿真過程主要通過發(fā)送一系列的測試數(shù)據(jù)分組來統(tǒng)計端到端時延,首先定義數(shù)據(jù)包格式64bit,然后在全局場景中設(shè)置路由器及客戶端,在Node Module中配置如上實驗參數(shù),最后設(shè)置仿真開始時間為0s,持續(xù)時間為20s,時延上界仿真結(jié)果在View Results中查看。
圖4 單傳輸系統(tǒng)場景仿真圖
圖5表示服務(wù)速率為150Mbit/s時,在模擬時間內(nèi)的單路徑傳輸系統(tǒng)端到端時延。
而為了保持以下仿真分析的一致性,下文統(tǒng)一采用流X中的服務(wù)參數(shù),根據(jù)圖5仿真得到的網(wǎng)絡(luò)端到端時延上界值,與本文計算得到的端到端時延上界、文獻[15]端到端時延上界進行比較,結(jié)果如圖6所示。
圖5 R=150Mbit/s時的端到端時延
圖6 三者端到端時延上界分析
從圖6中可看出,相較于文獻[15]端到端時延上界,本文方法計算的時延上界更接近仿真時延上界,這是因為本文考慮了前一個節(jié)點的處理時延對后一個節(jié)點到達曲線的影響,前后節(jié)點的時延相關(guān)是時間上的連續(xù)關(guān)系,與節(jié)點的服務(wù)規(guī)律和到達規(guī)律獨立并未沖突。另外值得注意的是,當(dāng)網(wǎng)絡(luò)服務(wù)速率相對較小時,端到端時延上界與仿真時延上界結(jié)果偏差較大,這是因為前期較小的網(wǎng)絡(luò)服務(wù)速率會引起節(jié)點數(shù)據(jù)積壓造成排隊時延增大,并經(jīng)過網(wǎng)絡(luò)演算卷積計算后,時延相對偏大。而節(jié)點服務(wù)能力隨著網(wǎng)絡(luò)服務(wù)速率的增大而提升后,兩者偏差會越來越小,驗證了式(7)是成立的。
另外,在單路徑傳輸系統(tǒng)中考慮X,Y,Z三種數(shù)據(jù)流,分別從節(jié)點個數(shù)、服務(wù)速率、權(quán)值分配三方面,考慮對端到端時延上界的影響。
圖7顯示單路徑傳輸系統(tǒng)中鏈路節(jié)點數(shù)對端到端時延上界的影響,可以看出,時延都是隨著鏈路節(jié)點數(shù)增加而增大。從式(6)看,當(dāng)鏈路節(jié)點數(shù)增加時,時延主要受平均速率的約束在不斷增大,因此網(wǎng)絡(luò)演算的卷積計算特點更能反映真實的網(wǎng)絡(luò)性能。
圖7 單路徑端到端時延和鏈路節(jié)點個數(shù)關(guān)系
圖8顯示了端到端時延和網(wǎng)絡(luò)服務(wù)速率之間的關(guān)系,不難看出,兩者呈負(fù)相關(guān),即端到端時延隨著網(wǎng)絡(luò)服務(wù)速率增大而減少,這與實際網(wǎng)絡(luò)情況一致。另外可以看出服務(wù)速率小于350Mbit/s時,端到端時延隨著網(wǎng)絡(luò)服務(wù)速率增大下降的幅度較大,大于350Mbit/s時,下降幅度趨于平穩(wěn)。數(shù)據(jù)流X和Z的端到端時延和網(wǎng)絡(luò)服務(wù)速率之間的曲線幾乎重疊,這是因為兩種服務(wù)有相同的σ,而節(jié)點間的輸入輸出關(guān)系正隨著網(wǎng)絡(luò)演算的卷積值而變化,主要受突發(fā)量的影響,但影響并不大,但是Z的時延要略大一點。而X和Y的端到端時延和網(wǎng)絡(luò)服務(wù)速率之間的曲線有明顯的差別正驗證了這點。
圖8 端到端時延和網(wǎng)絡(luò)服務(wù)速率的關(guān)系
圖9顯示了端到端時延在固定鏈路節(jié)點個數(shù)的情況下與服務(wù)速率權(quán)值分配之間的關(guān)系。假設(shè)總服務(wù)速率800Mbit/s,數(shù)據(jù)流X、Y、Z的服務(wù)速率分配權(quán)值分別為0.2,0.5,0.3。如下圖所示,三者端到端時延整體都呈上升趨勢,其中X端到端時延最高,Y次之,Z時延最低,這與分析的結(jié)果是一致的。因為在相同到達速率情況下,Z分配到的服務(wù)速率大于X分配的速率,雖然突發(fā)量也會對時延造成影響,但是影響卻不大,自然計算出的端到端時延是較小的;而Y與X相比時,到達速率大雖有影響,但對于Y分配到的最高的服務(wù)速率,同樣影響就不那么明顯了。
圖9 端到端時延和三種服務(wù)權(quán)值分配的關(guān)系
多路徑傳輸可看作是單路徑傳輸?shù)膹?fù)合模型,從式(6)和式(7)可看出,不同特征數(shù)據(jù)流對多路徑傳輸系統(tǒng)端到端時延上界的影響與單路徑相同。根據(jù)定理6,多路徑仿真主要從路徑條數(shù)、網(wǎng)絡(luò)服務(wù)速率兩因素分析對端到端時延上界的影響。
由圖3,本文假設(shè)源節(jié)點g輸出的數(shù)據(jù)分為三條鏈路到達節(jié)點a,鏈路服務(wù)速率分別設(shè)置為90Mbit/s,100Mbit/s,110Mbit/s。同時為了對比分析的方便有效,在多路徑下本文只討論分析數(shù)據(jù)流X在不同情況下的端到端時延上界的相應(yīng)變化情況。圖10表明了在多路徑情況下兩種流量分配方式隨著網(wǎng)絡(luò)服務(wù)速率的增加端到端時延上界的變化情況。即時延上界都隨著服務(wù)速率的增加而逐漸減小,且減小幅度也在降低,另外還可看出權(quán)值分配方式對應(yīng)時延更低,說明根據(jù)不同鏈路的服務(wù)需求分配合適的流量效果更好,降低了部分鏈路因過負(fù)荷導(dǎo)致網(wǎng)絡(luò)擁塞從而影響全局端到端時延上界。
圖10 多路徑時延上界和網(wǎng)絡(luò)服務(wù)速率關(guān)系
圖11表示在鏈路服務(wù)速率350Mb/s,源節(jié)點g和節(jié)點a服務(wù)速率都為500Mb/s仿真條件下,多路徑條數(shù)和流量分配方式對端到端時延上界的影響,仿真分析數(shù)據(jù)流X在不同參數(shù)條件下的端到端時延上界的結(jié)果。很明顯兩種流量分配方式的端到端時延上界都隨著多路徑條數(shù)增加而增加,權(quán)值分配獲取到的端到端時延上界比平均分配時延上界低,這同樣歸功于權(quán)值分配方式規(guī)避了平均分配方式予鏈路等量數(shù)據(jù)而導(dǎo)致部分鏈路負(fù)荷過大,造成網(wǎng)絡(luò)擁塞,從而影響多路徑傳輸系統(tǒng)端到端時延上界。
圖11 多路徑時延上界和多路徑條數(shù)的關(guān)系
本文提出的基于網(wǎng)絡(luò)演算的無線Mesh網(wǎng)端到端時延上界分析方法,利用(ρ,σ)模型作為數(shù)據(jù)流到達曲線,延遲-速率函數(shù)LR作為數(shù)據(jù)流服務(wù)曲線,同時考慮前一個節(jié)點的處理時延對后一個節(jié)點到達曲線的影響,推導(dǎo)出了單節(jié)點時延上界、單路徑傳輸系統(tǒng)端到端時延上界和多路徑傳輸系統(tǒng)端到端時延上界表達式。仿真實驗表明,與傳統(tǒng)方法相比,本文方法計算得到的時延上界更接近仿真值。為了更準(zhǔn)確地分析,在本文計算出的時延上界基礎(chǔ)上計算端到端數(shù)據(jù)積壓上界以及時延抖動上界來約束傳輸系統(tǒng)進行負(fù)載均衡是本文下一步的研究方向。