無線Mesh網(wǎng)絡(luò)中一種基于剩余時(shí)延的公平調(diào)度策略＊

符 琦，陳志剛，蔣云霞，尹風(fēng)雨，李潤求

（1.中南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410083；2.湖南科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南 湘潭 411201）

1 引言

隨著無線用戶和多媒體業(yè)務(wù)需求的快速增長，無線視頻、話音和數(shù)據(jù)等多媒體業(yè)務(wù)在無線網(wǎng)絡(luò)中的應(yīng)用變得越來越重要。而作為下一代無線寬帶主要接入技術(shù)之一的無線Mesh 網(wǎng)絡(luò) WMNs（Wireless Mesh Networks），以其低成本、高靈活的自組織等特性，為用戶提供無處不在的寬帶接入服務(wù)的同時(shí)，對(duì)上述寬帶應(yīng)用的服務(wù)質(zhì)量提供了良好的技術(shù)支持[1]。目前，WMNs已被廣泛用于樓宇自動(dòng)化網(wǎng)絡(luò)、社區(qū)網(wǎng)絡(luò)、家庭寬帶個(gè)域網(wǎng)絡(luò)、企業(yè)網(wǎng)、無線城市等多層次、多范圍的無線應(yīng)用。國內(nèi)外的研究機(jī)構(gòu)與廠商都對(duì)其相關(guān)實(shí)現(xiàn)技術(shù)及標(biāo)準(zhǔn)進(jìn)行了廣泛研究[2]。

在基于IEEE 802.11標(biāo)準(zhǔn)的WMNs中，由于其 MAC 層中 DCF（Distributed Coordination Function）機(jī)制不能有效地為具有不同屬性（如數(shù)據(jù)包傳輸優(yōu)先級(jí)）的數(shù)據(jù)流提供區(qū)分服務(wù)，從而無法有效保障不同類型多媒體數(shù)據(jù)的QoS需求。為此，802.11e標(biāo)準(zhǔn)作為其補(bǔ)充標(biāo)準(zhǔn)而提出，該標(biāo)準(zhǔn)提供了兩種QoS 機(jī)制：增加型分布式信道訪問EDCA（Enhanced Distributed Channel Access）和混合協(xié)調(diào)功能控制信道訪問HCCA（Hybrid Coordination Function Controlled Channel Access）。其中，EDCA 主要針對(duì)DCF的不足進(jìn)行了擴(kuò)展，可將八類具有不同服務(wù)需求（如最小時(shí)延、丟包率等）的數(shù)據(jù)流映射到四個(gè)具有不同QoS參數(shù)（如競爭窗口CW（Contention Window）、堅(jiān)持因子PF（Persistent Factor）、仲裁幀間間隔AIFS（Arbitration Inter-Frame Space）、傳輸機(jī)會(huì)TXOP（Transmission Opportunity）等）的訪問隊(duì)列AC（Access Category）中，通過不同時(shí)隙大小的AIFS 值和退避定時(shí)器BT（Backoff Timer）來實(shí)現(xiàn)不同優(yōu)先級(jí)多媒體數(shù)據(jù)對(duì)信道的搶占，優(yōu)先級(jí)越高，AIFS 和BT 所用時(shí)隙越小，信道搶占成功率越高[3]。但是，由于其QoS參數(shù)是預(yù)先設(shè)置的，并沒有考慮傳輸路徑上多個(gè)節(jié)點(diǎn)間的參數(shù)自適應(yīng)動(dòng)態(tài)調(diào)整對(duì)數(shù)據(jù)傳輸性能的影響，加之隊(duì)列中數(shù)據(jù)包的調(diào)度采用的是簡單的先進(jìn)先出（FIFO）機(jī)制，因此使得網(wǎng)絡(luò)負(fù)載較大時(shí)，容易導(dǎo)致各優(yōu)先級(jí)數(shù)據(jù)流之間對(duì)帶寬的不公平使用，加劇信道時(shí)間的競爭，大大降低了網(wǎng)絡(luò)吞吐量，增大了各類優(yōu)先級(jí)數(shù)據(jù)包的傳輸時(shí)延，使一些應(yīng)用（如對(duì)時(shí)延敏感度較高的實(shí)時(shí)數(shù)據(jù)流）的QoS需求難以得到有效保障。因此，如何在保障時(shí)延敏感的用戶業(yè)務(wù)數(shù)據(jù)流QoS的同時(shí)，公平調(diào)度不同優(yōu)先級(jí)數(shù)據(jù)，以最大化整個(gè)網(wǎng)絡(luò)的吞吐量，在多類型媒體數(shù)據(jù)流間均衡信道使用率，已成為了無線Mesh網(wǎng)絡(luò)多媒體傳輸技術(shù)的一個(gè)研究熱點(diǎn)問題[4，5]。

針對(duì)上述問題，研究人員從網(wǎng)絡(luò)的不同角度進(jìn)行了相關(guān)研究[6～13]。其中，（1）文獻(xiàn)[6～8]通過對(duì)現(xiàn)有802.11eMAC層機(jī)制進(jìn)行改進(jìn)滿足多媒體數(shù)據(jù)的傳輸QoS需求。如文獻(xiàn)[6]提出一種基于剩余TXOP 時(shí)間的數(shù)據(jù)分流方案，與原有802.11e機(jī)制以隊(duì)列為調(diào)度對(duì)象不同的是，該方案重新定義基于流調(diào)度的TXOP機(jī)制，并根據(jù)剩余TXOP 時(shí)間值來調(diào)度不同流的數(shù)據(jù)包進(jìn)行傳輸。文獻(xiàn)[7]則通過HCCA 和EDCA 機(jī)制的聯(lián)合調(diào)度來實(shí)現(xiàn)對(duì)速率可變數(shù)據(jù)流的區(qū)分服務(wù)，并通過模型分析了聯(lián)合機(jī)制下TXOP與數(shù)據(jù)傳輸速率、數(shù)據(jù)包長之間的相互關(guān)系。（2）文獻(xiàn)[9～11]則利用Markov模型對(duì)p-Persistent和二進(jìn)制指數(shù)退避BEB（Binary Exponential Backoff）機(jī)制進(jìn)行分析，以推導(dǎo)相關(guān)的QoS參數(shù)（如沖突概率、沖突時(shí)間、成功傳輸時(shí)間、信道空余時(shí)間等）與網(wǎng)絡(luò)傳輸性能的關(guān)系。這些方法的具體實(shí)現(xiàn)通常比較復(fù)雜，且不能反映數(shù)據(jù)流的實(shí)時(shí)特性，因而不能適應(yīng)現(xiàn)實(shí)環(huán)境的需求。（3）文獻(xiàn)[12，13]則通過收集節(jié)點(diǎn)反饋信息來考量多媒體數(shù)據(jù)流的動(dòng)態(tài)行為，然而反饋信息的產(chǎn)生與收集并不能精確、實(shí)時(shí)地反映當(dāng)前節(jié)點(diǎn)所處網(wǎng)絡(luò)的負(fù)載情況，因而也會(huì)導(dǎo)致數(shù)據(jù)包調(diào)度的失效，不能有效地提升網(wǎng)絡(luò)的性能。

上述研究均只考慮了單跳范圍內(nèi)（即終端用戶節(jié)點(diǎn)直接和網(wǎng)絡(luò)接入節(jié)點(diǎn)進(jìn)行通信，且通常假設(shè)不存在隱藏終端）改進(jìn)的802.11eMAC 機(jī)制對(duì)網(wǎng)絡(luò)流量飽和／非飽和情況下的性能分析，而對(duì)多跳傳輸環(huán)境下802.11e協(xié)議性能研究得不多[14～16]。文獻(xiàn)[14]以數(shù)據(jù)流到達(dá)目標(biāo)節(jié)點(diǎn)的跳數(shù)為數(shù)據(jù)包的調(diào)度考量，在中間轉(zhuǎn)發(fā)節(jié)點(diǎn)處優(yōu)先對(duì)跳數(shù)較大的數(shù)據(jù)流進(jìn)行調(diào)度，跳數(shù)相對(duì)較小的數(shù)據(jù)流則分享剩余信道帶寬，同時(shí)估算每跳的數(shù)據(jù)包傳輸時(shí)延，以最小化上行／下行節(jié)點(diǎn)的傳輸時(shí)延，確保最小網(wǎng)關(guān)數(shù)據(jù)開銷的同時(shí)，滿足數(shù)據(jù)流的延遲需求。文獻(xiàn)[15]則提出了一種與現(xiàn)有802.11e協(xié)議兼容的、基于TXOP的數(shù)據(jù)流傳輸公平性恢復(fù)與實(shí)施（Restore／Enforce Fairness）機(jī)制。該機(jī)制利用當(dāng)前節(jié)點(diǎn)的物理層數(shù)據(jù)發(fā)送速度、每個(gè)流的數(shù)據(jù)包轉(zhuǎn)發(fā)數(shù)量及修改的無狀態(tài)公平隊(duì)列SFD（Stateless Fair Queuing）[17]轉(zhuǎn)發(fā)策略（每個(gè)TXOP 周期每一個(gè)數(shù)據(jù)流只發(fā)送一個(gè)數(shù)據(jù)包）來實(shí)現(xiàn)多個(gè)數(shù)據(jù)流之間的傳輸公平性，其實(shí)現(xiàn)相對(duì)簡單且易于應(yīng)用到現(xiàn)有節(jié)點(diǎn)設(shè)備中。上述研究雖然對(duì)不同跳數(shù)環(huán)境中的802.11eMAC 層機(jī)制進(jìn)行分析建模，但并沒有涉及不同數(shù)據(jù)包長對(duì)傳輸沖突及吞吐量的影響，本文將從該角度對(duì)多媒體數(shù)據(jù)傳輸?shù)墓叫赃M(jìn)行分析討論。

本文通過分析802.11eMAC隊(duì)列中不同媒體數(shù)據(jù)包的時(shí)延界限數(shù)據(jù)傳輸沖突帶來的影響，提出了一種基于剩余時(shí)延界限的無線多跳帶寬公平共享調(diào)度策略。通過對(duì)802.11eMAC層中每類隊(duì)列數(shù)據(jù)包在節(jié)點(diǎn)的傳輸時(shí)延的計(jì)算，及時(shí)地調(diào)整隊(duì)列的傳輸機(jī)會(huì)TXOP 值，同時(shí)調(diào)整數(shù)據(jù)包的重傳閾值，以減少節(jié)點(diǎn)內(nèi)部虛擬沖突和節(jié)點(diǎn)間實(shí)際沖突的次數(shù)，提高節(jié)點(diǎn)數(shù)據(jù)成功傳送的概率，在提升網(wǎng)絡(luò)公平傳輸數(shù)據(jù)能力的同時(shí)，增加網(wǎng)絡(luò)各業(yè)務(wù)的吞吐量，滿足不同多媒體業(yè)務(wù)對(duì)數(shù)據(jù)傳輸QoS性能的不同要求。

2 問題描述與網(wǎng)絡(luò)模型

2.1 問題描述

在無線Mesh網(wǎng)絡(luò)多媒體傳輸研究中，多媒體業(yè)務(wù)的時(shí)延界限D(zhuǎn)B（Delay Bound）通常是指端到端的數(shù)據(jù)包時(shí)延約束。不同傳輸速率下多媒體業(yè)務(wù)對(duì)時(shí)延界限的要求是不同的，如表1所示，一般來說，實(shí)時(shí)音頻和視頻流時(shí)延都要求不超過125ms～300ms，而對(duì)于非實(shí)時(shí)音頻、視頻流則無延時(shí)限制，F(xiàn)TP 等數(shù)據(jù)的延時(shí)要求則由定時(shí)器或設(shè)備的緩存大小來決定[18]。

Table 1 QoS requirement of multimedia business表1 多媒體業(yè)務(wù)QoS需求

為了更好地度量多跳傳輸對(duì)DB的影響，給出如下剩余時(shí)延界限的定義：

定義1 （剩余時(shí)延界限）多媒體業(yè)務(wù)為每個(gè)數(shù)據(jù)包定義的時(shí)延界限D(zhuǎn)B與數(shù)據(jù)包的當(dāng)前轉(zhuǎn)發(fā)累積時(shí)延Tf（i，j）的差值即為剩余時(shí)延界限RDB

其中，i，j＝1，2.3，…，即第i個(gè)數(shù)據(jù)包在第j 跳時(shí)的剩余時(shí)延界限，Tf（i，j）為數(shù)據(jù)包在當(dāng)前節(jié)點(diǎn)的轉(zhuǎn)發(fā)時(shí)延。由于不同多媒體業(yè)務(wù)對(duì)數(shù)據(jù)包的時(shí)延約束的需要不同；數(shù)據(jù)包在單路徑多跳／多路徑多跳轉(zhuǎn)發(fā)時(shí)的累積時(shí)延不同；源、目的節(jié)點(diǎn)之間的距離等原因，導(dǎo)致了每個(gè)數(shù)據(jù)包的RDB 會(huì)有所差異，即使該數(shù)據(jù)包屬于同一個(gè)多媒體業(yè)務(wù)流。這種時(shí)延約束上的差異使得現(xiàn)有802.11eMAC層機(jī)制難以保障不同多媒體業(yè)務(wù)流的傳輸公平性。具有較大RDB 值的數(shù)據(jù)包將得到更多的重傳機(jī)會(huì)，從而獲得更高的成功傳輸概率，增大了其對(duì)信道的占用時(shí)間，從而導(dǎo)致具有較小RDB 的數(shù)據(jù)包因?yàn)槌瑫r(shí)無效而被丟棄，降低了整個(gè)網(wǎng)絡(luò)的吞吐量。如圖1所示。

Figure 1 Unfair scheduling in RDB圖1 基于RDB的不公平調(diào)度示意圖

假設(shè)轉(zhuǎn)發(fā)節(jié)點(diǎn)的某隊(duì)列中有三個(gè)具有不同RDBi（i＝0，1，2.值的數(shù)據(jù)包Packeti（i＝0，1，2.。Packet0因?yàn)槲挥陉?duì)首而第一個(gè)被嘗試傳給下一跳節(jié)點(diǎn)，由于發(fā)送沖突（節(jié)點(diǎn)內(nèi)部的虛擬沖突或是節(jié)點(diǎn)間的實(shí)際沖突），該數(shù)據(jù)包在其RDB0的時(shí)間內(nèi)被重傳了三次后，在t1時(shí)刻成功搶占信道而被傳輸?shù)较乱惶?jié)點(diǎn)；而在時(shí)間段（t0，t1）內(nèi)，Packet1因?yàn)镽DB1較小導(dǎo)致等待超時(shí)而被丟棄；Packet2因?yàn)槠銻DB2值大于RDB0，在一次發(fā)送沖突結(jié)束后，于t3時(shí)刻成功搶占信道而被傳輸?shù)较乱惶?jié)點(diǎn)。從圖1可以看出，在時(shí)間段（t0，t3）內(nèi)，Packet0和Packet2因?yàn)榫哂休^大的RDB 值，而獲得多次重傳的機(jī)會(huì)，從而具有較高的信道占用概率，Packet1則因?yàn)镽DB 較小而無法獲得傳送與重傳的機(jī)會(huì)，從而影響了其所屬數(shù)據(jù)流的網(wǎng)絡(luò)傳輸性能。當(dāng)網(wǎng)絡(luò)負(fù)載增大時(shí)，隨著數(shù)據(jù)包沖突重傳次數(shù)的增加，這種傳輸不公平的現(xiàn)象也會(huì)隨之加劇。與此同時(shí)，數(shù)據(jù)發(fā)送沖突時(shí)間也隨之增大，從而導(dǎo)致信道空閑時(shí)間增大，使網(wǎng)絡(luò)吞吐量下降。為了減少這種現(xiàn)象出現(xiàn)的頻率，可以考慮通過對(duì)RDB 的度量來減輕數(shù)據(jù)包重傳的次數(shù)和數(shù)據(jù)發(fā)送沖突的頻率，以提高不同RDB 不同優(yōu)先級(jí)數(shù)據(jù)包之間的公平調(diào)度。

2.2 網(wǎng)絡(luò)模型

本文主要考量了如圖2所示的無線多跳Mesh網(wǎng)絡(luò)G＝（N，E），其中N 為自組織模式節(jié)點(diǎn)集合，即網(wǎng)絡(luò)中的節(jié)點(diǎn)既可以是數(shù)據(jù)的源節(jié)點(diǎn)（Mesh Client，Mesh用戶端），也可以是轉(zhuǎn)發(fā)和接收數(shù)據(jù)的中間或目的節(jié)點(diǎn)（Mesh Router／GateWay，Mesh路由器／網(wǎng)關(guān)）；E 為邊的集合（若兩節(jié)點(diǎn)i、j 間存在邊ei，j∈E，則兩節(jié)點(diǎn)一定處在彼此的通信半徑內(nèi)）。由于在EDCA 中，四個(gè)AC 隊(duì)列最終只有一個(gè)隊(duì)列的數(shù)據(jù)能成功搶占信道并被傳送出去，因此在本文中，數(shù)據(jù)源節(jié)點(diǎn)（如圖2中的MR7、MR10、MR11等Mesh節(jié)點(diǎn)）不考慮EDCA 的虛擬沖突情況，即每個(gè)源節(jié)點(diǎn)只產(chǎn)生具有一個(gè)優(yōu)先級(jí)的多媒體數(shù)據(jù)，且數(shù)據(jù)源節(jié)點(diǎn)不具有轉(zhuǎn)發(fā)數(shù)據(jù)的功能；EDCA 隊(duì)列數(shù)據(jù)的虛擬沖突與實(shí)際沖突同時(shí)發(fā)生且只出現(xiàn)在轉(zhuǎn)發(fā)節(jié)點(diǎn)當(dāng)中（如MR1、MR2 等）。因此，本文所提出的基于剩余時(shí)延的自適應(yīng)EDCA機(jī)制主要工作在轉(zhuǎn)發(fā)節(jié)點(diǎn)當(dāng)中。

Figure 2 Scene of NS2simulation圖2 NS2仿真場景示意圖

在上述網(wǎng)絡(luò)模型中，轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)據(jù)發(fā)送沖突的減少，無疑會(huì)提高單個(gè)節(jié)點(diǎn)的吞吐能力，從而提升整個(gè)網(wǎng)絡(luò)的性能。為了推導(dǎo)網(wǎng)絡(luò)性能與數(shù)據(jù)沖突之間的關(guān)系，我們用Ui（xi）來表示單個(gè)節(jié)點(diǎn)數(shù)據(jù)傳輸效用函數(shù)，其中xi表示第i 個(gè)節(jié)點(diǎn)的平均吞吐量，其定義如下[3]：

其中，L 表示第i個(gè)節(jié)點(diǎn)的數(shù)據(jù)包大??；E[Li]為時(shí)間周期E[T]內(nèi)成功發(fā)送的數(shù)據(jù)量大小。這兩個(gè)值分別定義如下：

即在數(shù)據(jù)成功傳送的情況下，最大化所有節(jié)點(diǎn)數(shù)據(jù)傳輸效用之和。當(dāng)U（·）為可微且嚴(yán)格凹函數(shù)時(shí)，公式（5）存在最優(yōu)解的必要條件為：

本文主要討論所有節(jié)點(diǎn)具有相同數(shù)據(jù)傳輸速率的網(wǎng)絡(luò)性能，因此，將公式（2）～公式（4）代入公式（6），可得公式（6）的全局近似最優(yōu)解為：

其中，i∈N。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量較大時(shí)，有pi?P，因此，E[T]可以近似等于：

在此基礎(chǔ)上，為了能夠以分布式方式來解決全局性能最優(yōu)問題，我們給出了基于擁塞因子λ的節(jié)點(diǎn)平均吞吐量優(yōu)化問題描述：

其存在最優(yōu)解的必要條件為：

當(dāng)所有節(jié)點(diǎn)的效用函數(shù)相同時(shí)，有U′＝λ，將其代入公式（10），可得總的節(jié)點(diǎn)傳輸概率P：

公式（11）表明，當(dāng)節(jié)點(diǎn)具有相同的效用函數(shù)和相同的數(shù)據(jù)傳輸速率時(shí)，最大化無線信道的使用效率的最優(yōu)總傳輸概率值不依賴于特定的節(jié)點(diǎn)效用函數(shù)和數(shù)據(jù)成功傳輸時(shí)間，而僅僅與被規(guī)范化成信道空閑時(shí)間槽數(shù)的數(shù)據(jù)發(fā)送沖突時(shí)間Tcol相關(guān)。由此說明，數(shù)據(jù)發(fā)送沖突時(shí)間的減少，將有效地提升單個(gè)及整個(gè)網(wǎng)絡(luò)的傳輸性能，而沖突的減少也將進(jìn)一步影響數(shù)據(jù)重傳次數(shù)的減少，反之亦然。基于此種考量，本文利用無線多跳環(huán)境中數(shù)據(jù)包的剩余時(shí)延約束，對(duì)節(jié)點(diǎn)的重傳次數(shù)及無競爭突發(fā)傳輸機(jī)制進(jìn)行了優(yōu)化處理，以在一定程度上減少節(jié)點(diǎn)的重傳次數(shù)，提高節(jié)點(diǎn)及整個(gè)網(wǎng)絡(luò)的吞吐量。

3 基于剩余時(shí)延的EDCA傳輸機(jī)制

3.1 相關(guān)定義

為了有效地計(jì)算和利用每個(gè)數(shù)據(jù)包的RDB，我們先給出了EDCA 機(jī)制中數(shù)據(jù)包的信道訪問時(shí)延TCAD的相關(guān)定義：

Figure 3 RDB-based CFB transmission process圖3 基于RDB的CFB數(shù)據(jù)塊傳輸示意圖

定義2 （信道訪問時(shí)延）數(shù)據(jù)包進(jìn)入某優(yōu)先級(jí)隊(duì)列開始，到其成功搶占信道的時(shí)間段稱為數(shù)據(jù)包的信道訪問時(shí)延TCAD。TCAD包括了數(shù)據(jù)包在隊(duì)列中的等待時(shí)延Tq和信道空閑檢測與沖突退避時(shí)延Tch，如圖3所示。為了獲得當(dāng)前的TCAD值，CAD 將在數(shù)據(jù)包成功搶占信道后被更新，第n 次瞬時(shí)TCAD（n）值將通過加權(quán)的滑動(dòng)平均窗口WMAW（Weighted Moving Averaging Window）方式來進(jìn)行估算，以防止其統(tǒng)計(jì)值偏差較大：

其中，TCAD（n-1）為第n-1次的TCAD值，w 為平滑因子，取值范圍為[0，1]，通常該值取[0.9，1]時(shí)，其統(tǒng)計(jì)結(jié)果更能反映真實(shí)情況。

與此同時(shí)，為了使多媒體數(shù)據(jù)具有不同的RDB 值，同時(shí)限制較大RDB 值數(shù)據(jù)包的重傳次數(shù)，我們需要估算數(shù)據(jù)包當(dāng)前的剩余時(shí)延DM（Delay Margin），并將其攜帶在包頭信息中，以便轉(zhuǎn)發(fā)節(jié)點(diǎn)對(duì)相關(guān)時(shí)延參數(shù)、TXOP 值等QoS 參數(shù)進(jìn)行動(dòng)態(tài)估算與設(shè)置。DM 定義如下：

定義3 （剩余時(shí)延）數(shù)據(jù)包的RDB與信道訪問時(shí)延TCAD，以及數(shù)據(jù)被傳送到下一跳節(jié)點(diǎn)的時(shí)間Ttrans差即為數(shù)據(jù)包的剩余時(shí)延DM：

為了提升數(shù)據(jù)傳輸?shù)男阅埽珽DCA 機(jī)制提供了一種無競爭突發(fā)CFB（Contention Free Bursting）傳輸策略，如圖4所示。該策略使得某個(gè)優(yōu)先級(jí)的隊(duì)列一旦搶占了信道時(shí)間，則可在TXOP 時(shí)間內(nèi)連續(xù)發(fā)送隊(duì)列中的多個(gè)數(shù)據(jù)，而不需要重新競爭信道的使用權(quán)，只有在TXOP 超時(shí)后才重新競爭信道。由于CFB階段傳輸?shù)臄?shù)據(jù)包可能有多個(gè)，也可能只有一個(gè)，為了更好地估算CFB 階段結(jié)束后的剩余時(shí)延，我們引入塊剩余時(shí)延界限BRDB（Block RDB）概念。如圖3 所示，如果數(shù)據(jù)塊中：（1）每個(gè)數(shù)據(jù)包的RDB 均大于Ttxop，則BRDB 被設(shè)為min（RDBi）（i＝0，1，2.…）；（2）某個(gè)數(shù)據(jù)包的RDB 大于其自身的成功傳送時(shí)間，小于數(shù)據(jù)塊的傳送的結(jié)束時(shí)間，則BRDB 為CFB的TXOP時(shí)間；（3）某個(gè)數(shù)據(jù)包的RDB 小于其自身傳輸所需要的時(shí)間，則BRDB 為該數(shù)據(jù)包的RDB 時(shí)間。因此，在啟動(dòng)了CFB 機(jī)制的EDCA 策略中，第k 個(gè)AC隊(duì)列中第i個(gè)數(shù)據(jù)塊傳輸?shù)氖Ｓ鄷r(shí)延為（k 為AC隊(duì)列的數(shù)量，k＝1，2.3，4；i為數(shù)據(jù)塊編號(hào)）：

Figure 4 CFB transmission process圖4 CFB數(shù)據(jù)突發(fā)傳輸示意圖

由圖4可知，CFB持續(xù)發(fā)送時(shí)間Tblock＿txop由數(shù)據(jù)包的傳送時(shí)間、ACK 接收時(shí)間和SIFS（Short Inter Frame Space）組成（本文不考慮RTS／CTS／DATA／ACK 四次握手的CFB傳輸情況），即：

其中，N 為CFB 期間一次突發(fā)傳送數(shù)據(jù)塊所包含的數(shù)據(jù)包數(shù)量，Ldata和Lack分別為數(shù)據(jù)包的長度，dataRate和basicRate 分別為傳送數(shù)據(jù)型數(shù)據(jù)包和應(yīng)答型數(shù)據(jù)包的物理層傳輸速率，SIFS 為最短的幀間間隔（用于為某些幀提供最高的介質(zhì)訪問優(yōu)先級(jí)）。

3.2 算法描述

為了便于描述，我們把本文提出的時(shí)延自適應(yīng)機(jī)制稱為DM-EDCA 機(jī)制。由以上定義與計(jì)算方法可以得到四個(gè)AC隊(duì)列中所有塊的BDM。為了利用該參數(shù)來提高網(wǎng)絡(luò)中各業(yè)務(wù)流的吞吐量，減少數(shù)據(jù)包的重傳次數(shù)，將BDM 轉(zhuǎn)換成剩余重傳機(jī)會(huì)ROM（Retransmission Opportunity Margin），即：

其中，函數(shù)Floor（x）用于對(duì)x 值進(jìn)行下取整，EIFS-DIFS 值則是當(dāng)數(shù)據(jù)包發(fā)生重傳時(shí)需要額外等待的時(shí)間。如果存在某個(gè)ROMi，k≤0，表明該數(shù)據(jù)塊數(shù)據(jù)的重傳將導(dǎo)致其轉(zhuǎn)發(fā)時(shí)延的增加而超過其BRDB 閾值，并因此而被丟棄。為此，DMEDCA 將數(shù)據(jù)包的重傳次數(shù)設(shè)為0，以避免數(shù)據(jù)包的重傳；反之，如果所有數(shù)據(jù)塊的ROM 值均大于0，則DM-EDCA 將分別計(jì)算每個(gè)隊(duì)列的平均ROM 值：

并將min1≤k≤4｛ROMavg（k）｝值設(shè)為新的數(shù)據(jù)包重傳閾值，以滿足確保具有較小RDB 值的數(shù)據(jù)包也能在其剩余時(shí)延界限內(nèi)獲得一定的重傳機(jī)會(huì)。具體算法描述如下：

算法1 基于剩余時(shí)延界限的自適應(yīng)傳輸算法

輸入：AC 隊(duì)列數(shù)據(jù)包的時(shí)延界限，CFB 數(shù)據(jù)塊大小，EDCA 參數(shù)（AIFSN，CWmin，CWmax，TXOP）；

輸出：數(shù)據(jù)包的重傳次數(shù)、TXOP 值。

步驟1 設(shè)置數(shù)據(jù)包，CFB數(shù)據(jù)塊大小及EDCA 相關(guān)參數(shù)。

步驟2 記錄數(shù)據(jù)包入隊(duì)時(shí)間；若成功占用信道，轉(zhuǎn)到步驟3；否則繼續(xù)等待信道空閑。

步驟3 計(jì)算數(shù)據(jù)包的信道訪問時(shí)延TCAD，當(dāng)前數(shù)據(jù)塊的TXOP 傳送時(shí)間Tblock＿txop，并利用WMAW 對(duì)瞬時(shí)Tblock＿txop值進(jìn)行更新。

步驟4 計(jì)算當(dāng)前數(shù)據(jù)塊的BDM 及每個(gè)數(shù)據(jù)塊的ROM。

步驟5 若ROM≤0，設(shè)置重傳閾值為0，并轉(zhuǎn)至步驟2；否則轉(zhuǎn)到步驟6。

步驟6 計(jì)算數(shù)據(jù)塊的平均ROM，并取min（ROMavg）為新的數(shù)據(jù)包重傳閾值，返回新的重傳閾值和TXOP 值。

在步驟3中，考慮到轉(zhuǎn)發(fā)節(jié)點(diǎn)的同一AC 隊(duì)列中可能緩存了不同多媒體數(shù)據(jù)流中不同大小的數(shù)據(jù)包，因此最初設(shè)定的CFB 數(shù)據(jù)塊大小不能及時(shí)反映隊(duì)列中數(shù)據(jù)包的平均大小，從而影響了CFB的傳輸效率。因此，DM-EDCA 執(zhí)行過程中，將根據(jù)當(dāng)前隊(duì)列中數(shù)據(jù)包大小的平均值來更新當(dāng)前的Tblock＿txop大小，并利用WMAM 對(duì)其進(jìn)行加權(quán)平滑操作，以真實(shí)反映當(dāng)前隊(duì)列中數(shù)據(jù)包的數(shù)量，及時(shí)調(diào)整CFB的持續(xù)突發(fā)時(shí)長。

4 性能仿真與分析

為了驗(yàn)證DM-EDCA 機(jī)制的性能，我們?cè)贜S-2開源仿真軟件和TKN 的802.11e 擴(kuò)展模型[19]的基礎(chǔ)上實(shí)現(xiàn)了本文所提數(shù)據(jù)包公平調(diào)度策略。由于本文的DM-EDCA 沒有針對(duì)某個(gè)具體的路由協(xié)議，因此很容易在不同類型的路由協(xié)議中進(jìn)行擴(kuò)展，實(shí)現(xiàn)簡單。

此外，我們定義了一個(gè)自組織模式的仿真場景（如圖2所示），即仿真場景中的所有節(jié)點(diǎn)均為對(duì)等通信模式，所有節(jié)點(diǎn)既可以是產(chǎn)生業(yè)務(wù)數(shù)據(jù)的終端節(jié)點(diǎn)，也可以是Mesh路由器／網(wǎng)關(guān)節(jié)點(diǎn)，因而可以對(duì)數(shù)據(jù)進(jìn)行路由和轉(zhuǎn)發(fā)。該場景中的節(jié)點(diǎn)將產(chǎn)生四組業(yè)務(wù)數(shù)據(jù)流，分別與802.11e中的AC 優(yōu)先級(jí)相對(duì)應(yīng)（Flow1：AC＿VO，F(xiàn)low2：AC＿VI，F(xiàn)low3：AC＿BE，F(xiàn)low4：AC＿BK）。為了測試DM-EDCA在不同優(yōu)先級(jí)情況下的性能，我們進(jìn)行了兩組仿真實(shí)驗(yàn)：第一組中，F(xiàn)low1／3為音頻數(shù)據(jù)流（優(yōu)先級(jí)為0），F(xiàn)low2／4為視頻數(shù)據(jù)流，其初始CFB 持續(xù)傳輸數(shù)據(jù)包的個(gè)數(shù)為3；第二組則為每一個(gè)業(yè)務(wù)數(shù)據(jù)流分配一個(gè)不同的優(yōu)先級(jí)，其中音視頻流的CFB 持續(xù)傳輸數(shù)據(jù)包個(gè)數(shù)為1，背景流的CFB 持續(xù)傳輸數(shù)據(jù)包個(gè)數(shù)為1，以便仿真音（視）頻和背景數(shù)據(jù)流同時(shí)存在的情況下DM-EDCA 的網(wǎng)絡(luò)性能。在場景一中，F(xiàn)low1至Flow4分別從第5秒、10 秒、15秒和20秒開始產(chǎn)生數(shù)據(jù)流，每個(gè)流持續(xù)20秒，數(shù)據(jù)包的產(chǎn)生速率為640Kb／s。在場景二中，F(xiàn)low1和Flow2分別為音頻和視頻流，且從第5 秒和第10秒開始產(chǎn)生數(shù)據(jù)流量（流速為640Kb／s）；Flow3和Flow4分別是優(yōu)先級(jí)隊(duì)列為AC＿BE 和AC＿BK的背景流，且從第15秒和第20秒出現(xiàn)在仿真網(wǎng)絡(luò)場景中（流速為320Kb／s），所有流在第40秒結(jié)束數(shù)據(jù)包的產(chǎn)生。相關(guān)仿真結(jié)果如圖5至圖8所示，其他具體仿真參數(shù)如表2所示。

在場景一中（如圖5a所示），在時(shí)段[15～35]秒內(nèi)，采用了DM-EDCA 機(jī)制的四個(gè)數(shù)據(jù)流中，新增數(shù)據(jù)流（15秒后出現(xiàn)的數(shù)據(jù)流）的吞吐量峰值略小于原有EDCA 的仿真結(jié)果，但四條數(shù)據(jù)流均能完成對(duì)信道的占用，并完成各自數(shù)據(jù)包的傳送；而在采用了EDCA 機(jī)制的數(shù)據(jù)流（如圖5b所示）中，只有兩條數(shù)據(jù)流（AC＿VO＿1和AC＿VI＿1）能占用信道并完成數(shù)據(jù)的傳送，其他兩條音視頻流分別因?yàn)榫W(wǎng)絡(luò)中兩條新的音視頻數(shù)據(jù)流的出現(xiàn)（第15秒和第20秒）及其對(duì)信道的搶占，在完成數(shù)據(jù)傳輸任務(wù)之前，因?yàn)镈B 超時(shí)和沖突丟包，吞吐量銳減至0，未能在其任務(wù)時(shí)間（20 秒）段內(nèi)公平地使用帶寬。由此可知，DM-EDCA 雖然使得部分?jǐn)?shù)據(jù)流的吞吐量有所下降，但整個(gè)網(wǎng)絡(luò)中所有業(yè)務(wù)流的吞吐量和時(shí)延界限都能得到一定的保證，在單信道單路徑傳輸?shù)沫h(huán)境中，有效地實(shí)現(xiàn)了對(duì)信道帶寬的公平使用，提升了整個(gè)網(wǎng)絡(luò)帶寬的利用率。

Table 2 Parameters in DM-EDCA simulation表2 DM-EDCA仿真參數(shù)

Figure 5 Results of simulation scene 1圖5 場景一仿真結(jié)果示意圖

在場景二中（如圖6a所示），在時(shí)段[25～36]秒內(nèi)，隨著背景流數(shù)據(jù)的注入，原有的兩條音視頻數(shù)據(jù)雖然具有較高的優(yōu)先級(jí)，但因?yàn)檗D(zhuǎn)發(fā)跳數(shù)較大，時(shí)延界限閾值相對(duì)較小而失去了信道的占用權(quán)，直到背景流數(shù)據(jù)減少時(shí)（第38秒之后），視頻流數(shù)據(jù)才重新獲得信道的部分占用。而在采用了DM-EDCA 機(jī)制的數(shù)據(jù)流轉(zhuǎn)發(fā)場景中（如圖6b所示），音視頻數(shù)據(jù)流的吞吐量并沒有隨著背景數(shù)據(jù)流的注入而出現(xiàn)為0的情況。雖然新注入的背景流的吞吐量要小于EDCA 機(jī)制中的峰值，但網(wǎng)絡(luò)中的所有多媒體業(yè)務(wù)流都能獲得信道的占用權(quán)，大大地提升了整個(gè)網(wǎng)絡(luò)的性能。由此可知，DM-EDCA 雖然犧牲了部分優(yōu)先級(jí)數(shù)據(jù)流的吞吐量，但有效地均衡了信道帶寬在各優(yōu)先級(jí)業(yè)務(wù)流中的使用率，從而達(dá)到了信道公平共享的目的。

Figure 6 Results of simulation scene 2圖6 場景二仿真結(jié)果示意圖

5 結(jié)束語

本文提出了一種基于剩余時(shí)延界限的CFB數(shù)據(jù)包轉(zhuǎn)發(fā)機(jī)制，該機(jī)制在現(xiàn)有802.11eEDCA 機(jī)制的基礎(chǔ)上，針對(duì)由于具有較大時(shí)延界限的數(shù)據(jù)流長期占用傳輸信道，而導(dǎo)致具有較低時(shí)延界限數(shù)據(jù)流出現(xiàn)大量丟包、重傳，從而影響整個(gè)網(wǎng)絡(luò)吞吐量及多數(shù)據(jù)流傳輸?shù)墓叫詥栴}，通過估算數(shù)據(jù)包的剩余時(shí)延，以及動(dòng)態(tài)調(diào)整TXOP的時(shí)長及CFB 突發(fā)數(shù)據(jù)塊的大小，來自適應(yīng)網(wǎng)絡(luò)中多優(yōu)先級(jí)業(yè)務(wù)流量的變化。該機(jī)制仿真結(jié)果表明了該策略比原有802.11e機(jī)制具有更高的效率，且與原來802.11e標(biāo)準(zhǔn)兼容，實(shí)現(xiàn)簡單，對(duì)無線Mesh網(wǎng)絡(luò)中多媒體業(yè)務(wù)數(shù)據(jù)傳輸有一定的針對(duì)性和適應(yīng)性，能較好地滿足不同業(yè)務(wù)QoS的需求。與此同時(shí)，由于多媒體業(yè)務(wù)流具有自相似性，在這種情況下一旦網(wǎng)絡(luò)擁塞發(fā)生便更加難以恢復(fù)，如何在自相似特性的業(yè)務(wù)模型中進(jìn)行數(shù)據(jù)流公平共享調(diào)度的保障及CFB調(diào)控仍是一個(gè)要深入探討的課題；另外，由于該機(jī)制并沒有考慮數(shù)據(jù)轉(zhuǎn)發(fā)路徑上不同節(jié)點(diǎn)的EDCA 參數(shù)（如CW、AIFS、PF）及數(shù)據(jù)傳輸相關(guān)概率（如成功傳輸概率、沖突概率等）對(duì)隱藏終端及其傳輸沖突對(duì)網(wǎng)絡(luò)性能的影響，因此，如何動(dòng)態(tài)調(diào)整和分配不同節(jié)點(diǎn)的EDCA 相關(guān)QoS參數(shù)，以提高傳輸成功率和整個(gè)網(wǎng)絡(luò)的帶寬共享分布也是一個(gè)需要深入討論的問題。

[1]Shen Cheng，Lu Yi-fei，Xia Qin.An integrated metrics based routing protocol for wireless mesh networks[J].Chinese Journal of Computers，2010，33（12）：2300-2311.（in Chinese）

[2]Li X Y，Nusairat A，Wu Y W，et al.Joint throughput optimization for wireless mesh networks[J].IEEE Transactions on Mobile Computing，2009，8（7）：895-909.

[3]Hamdaoui B，Elaoud M，Ramanathan P.A delay-based admission control mechanism for multimedia support in IEEE 802.11e wireless LANs[J].Wireless Networks，2009，15（7）：875-886.

[4]Lin C H，Shieh C K.An unequal error protection mechanism for video streaming over IEEE 802.11e WLANs[J].Computer Network，2012，56（11）：2590-2599.

[5]Liao Y，Gibson J D.Routing-aware multiple description video coding over mobile Ad-Hoc networks[J].IEEE Transactions on Multimedia，2011，13（1）：132-142.

[6]Deng Q，Cai A.A TXOP-based scheduling algorithm for video transmission in IEEE 802.11enetworks[C]∥Proc of the 6th International Conference on ITS Telecommunications，2006：573-576.

[7]Ruscelli A L，Cecchetti G，Alifano A，et al.Enhancement of QoS support of HCCA schedulers using EDCA function in IEEE 802.11enetworks[J].Ad Hoc Networks，2010，10（2）：147-161.

[8]Kim S，Huang R，F(xiàn)ang Y.Deterministic priority channel access scheme for QoS support in IEEE 802.11ewireless LANs[J].IEEE Transactions on Vehicular Technology，2009，58（2）：855-864.

[9]Zhu J，F(xiàn)apojuwo A.A new call admission control method for providing desired throughput and delay performance in IEEE 802.11ewireless LANs[J].IEEE Transactions on Wireless Communications，2007，6（2）：701-709.

[10]Chen X，Zhai H，F(xiàn)ang Y.Supporting QoS in IEEE 802.11ewireless LANs[J].IEEE Transactions on Wireless Communications，2006，5（8）：2217-2227.

[11]Rashwand S，Misic J.IEEE 802.11eEDCA under bursty traffic-how much TXOP can improve performance[J].IEEE Transactions on Vehicular Technology，2011，60（3）：1099-1115.

[12]Boggia G，Camarda P，Grieco L A，et al.Feedback-based control for providing real-time services with the 802.11e MAC[J].IEEE／ACM Transactions on Networking，2007，15（2）：323-333.

[13]Kim S，Cho Y J.Channel time allocation scheme based on feedback information in IEEE 802.11ewireless LANs[J].Elsevier Computer Networks，2007，51（10）：2771-2787.

[14]Zou Jun，Zhao Dong-mei.Connection-based scheduling for supporting real-time traffic in wireless mesh networks[J].IEEE Transactions for Wireless Communications，2009，8（3）：1182-1187.

[15]Li Tian-ji，Leitth D J.Achieving end-to-end fairness in 802.11ebased wireless multi-hop mesh networks without coordination[J].Mobile Networks Applications，2011，16（1）：17-34.

[16]Chu Xiao-wen.Provisioning of parameterized quality of service in 802.11ebased wireless mesh networks[J].Mobile Networks Applications，2008，13（1-2）：6-18.

[17]Stanojevic R，Shorten R.Beyond CHOKe：Stateless fair queueing[C]∥Proc of NET-COOP'07，2.07：43-53.

[18]Xie Kun，Gong Chuang，Sun Jia-qi，et al.Qos-sensitive packet scheduling algorithm for IEEE 802.11e[J].Journal of Chinese Computer Systems，2012，33（1）：32-37.（in Chinese）

[19]Fall K，Varadhan K.The NS manual[EB／OL].[2008-09-01].http：／／www.isi.edu／nsnam／ns／doc／index.html.

附中文參考文獻(xiàn)：

[1]沈呈，陸一飛，夏勤.基于綜合判據(jù)的無線Mesh網(wǎng)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（12）：2300-2311.

[18]謝鯤，龔闖，孫家奇，等.QoS敏感的802.11e分組調(diào)度算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（1）：32-37.