基于沖突圖的毫米波無(wú)線個(gè)域網(wǎng)并行調(diào)度方案

王一兵，牛勇，丁瑋光，吳昊

（北京交通大學(xué)電子信息工程學(xué)院，北京 100044）

1 引言

隨著移動(dòng)數(shù)據(jù)業(yè)務(wù)需求的急劇增長(zhǎng)，位于30～300 GHz的毫米波頻段在第五代（5G）移動(dòng)通信系統(tǒng)中逐漸受到了廣泛的關(guān)注。其中，60 GHz毫米波（以下簡(jiǎn)稱毫米波）頻段是研究中使用較多的一個(gè)頻段。一方面，毫米波較大的帶寬和較高的發(fā)射功率，為高清視頻、即時(shí)音樂、高清圖像傳輸?shù)葻o(wú)線個(gè)域網(wǎng)（WPAN, wireless personal area network）中帶寬密集型多媒體服務(wù)的實(shí)現(xiàn)提供了可能[1-2]。另一方面，對(duì)于毫米波的高傳播損耗，實(shí)際中一般采用定向天線和波束賦形技術(shù)加以克服。將發(fā)射機(jī)和接收機(jī)的波束相互對(duì)準(zhǔn)[3]，這種定向通信使不同鏈路之間的干擾大大減小，因此，通過(guò)合適的調(diào)度算法，可以充分利用空分復(fù)用技術(shù)來(lái)進(jìn)行并行傳輸[4]，進(jìn)而提高整個(gè)網(wǎng)絡(luò)的性能。

2 相關(guān)工作

在之前針對(duì)毫米波無(wú)線網(wǎng)絡(luò)調(diào)度問題的研究中，許多基于時(shí)分復(fù)用（TDMA, time division multiple access）的方案被用于傳輸調(diào)度[5-6]。后來(lái)由于定向天線和波束賦形技術(shù)的發(fā)展，傳播損耗對(duì)系統(tǒng)的影響得以改善[7-8]。并且定向通信可以減少鏈路之間的干擾，因此采用并行傳輸?shù)姆绞娇梢蕴岣呦到y(tǒng)吞吐量[9]。在現(xiàn)有的相關(guān)工作中，文獻(xiàn)[5-6]的方案都是基于TDMA提出的，其目的是提高系統(tǒng)的傳輸速率和整個(gè)網(wǎng)絡(luò)的吞吐量，盡管這2種方案在一定程度上提高了網(wǎng)絡(luò)性能，但與并行傳輸所能達(dá)到的傳輸速率和網(wǎng)絡(luò)吞吐量相比，還是遠(yuǎn)遠(yuǎn)不夠的。文獻(xiàn)[10]提出了一種在速率自適應(yīng)無(wú)線網(wǎng)絡(luò)中的雙重更新并行調(diào)度算法，但并未考慮毫米波的特性所帶來(lái)的影響。文獻(xiàn)[4]在毫米波條件下提出了基于最大QoS獨(dú)立集的并行調(diào)度算法，但是該算法是在小小區(qū)回傳網(wǎng)絡(luò)的場(chǎng)景下得出的。文獻(xiàn)[11]提出了一種基于獨(dú)占區(qū)的調(diào)度算法，確保了毫米波無(wú)線個(gè)域網(wǎng)內(nèi)的并行傳輸總是比順序的時(shí)分復(fù)用算法性能更佳。文獻(xiàn)[12]提出了一種在考慮了流的吞吐量需求的前提下，以最大化網(wǎng)絡(luò)中總流數(shù)為目標(biāo)的翻轉(zhuǎn)性算法，但是并未考慮網(wǎng)絡(luò)中關(guān)于流之間沖突干擾的全局性信息。文獻(xiàn)[13]提出了一種分布式傳輸功率控制解決方案，用于設(shè)備到設(shè)備（D2D, device-to-device）鏈路之間的并行傳輸調(diào)度，增大同時(shí)調(diào)度流的速率和并進(jìn)一步提高網(wǎng)絡(luò)吞吐量，但并沒有考慮傳輸效率問題，無(wú)法實(shí)現(xiàn)對(duì)資源的充分有效利用。文獻(xiàn)[14]提出了一種用于毫米波網(wǎng)絡(luò)的能量有效調(diào)度方案，該方案利用并行傳輸來(lái)實(shí)現(xiàn)更高的能量效率，但沒有對(duì)網(wǎng)絡(luò)中的沖突干擾做出應(yīng)對(duì)。因此，在60 GHz的無(wú)線個(gè)域網(wǎng)場(chǎng)景中，如何在時(shí)隙資源有限的情況下實(shí)現(xiàn)對(duì)資源的充分有效利用，以實(shí)現(xiàn)網(wǎng)絡(luò)性能的全局最優(yōu)，仍然存在一定的挑戰(zhàn)。

本文提出了一種基于沖突圖的空時(shí)分多址接入調(diào)度算法（CB-STDMA, contention graph based spatial-time division multiple access）。該算法對(duì)相同級(jí)別的流進(jìn)行調(diào)度，一方面讓所用時(shí)隙數(shù)較少的流優(yōu)先被調(diào)度，從而節(jié)省出寶貴的時(shí)隙資源來(lái)調(diào)度更多的流；另一方面，只有被調(diào)度的流之間沒有沖突，即不是相鄰鏈路且相互干擾小于某個(gè)門限值時(shí)才能被同時(shí)調(diào)度，使被調(diào)度的流保持較高的速率，從而進(jìn)一步增加了網(wǎng)絡(luò)中滿足吞吐量需求的流數(shù)以及網(wǎng)絡(luò)的總吞吐量。本文中將最低吞吐量需求稱為服務(wù)質(zhì)量（QoS, quality of service）需求。

3 系統(tǒng)模型

本文考慮基于IEEE 802.15.3c協(xié)議的60 GHz室內(nèi)無(wú)線個(gè)域網(wǎng)場(chǎng)景。場(chǎng)景中包括一個(gè)微微網(wǎng)控制（PNC, piconet controller）和幾個(gè)無(wú)線節(jié)點(diǎn)（WN,wireless node）。無(wú)線節(jié)點(diǎn)之間可能有數(shù)據(jù)流需要進(jìn)行傳輸，每條流都有自己的最低吞吐量需求，即QoS需求。PNC可以對(duì)網(wǎng)絡(luò)中的數(shù)據(jù)傳輸進(jìn)行同步和協(xié)調(diào)[15]，并且可以獲得每條流的QoS需求以及各個(gè)無(wú)線節(jié)點(diǎn)的位置。每個(gè)無(wú)線節(jié)點(diǎn)都裝有電子導(dǎo)向定向天線，從而使收發(fā)器之間可以進(jìn)行定向傳輸來(lái)提高天線增益[16]。另外，假設(shè)各無(wú)線節(jié)點(diǎn)之間進(jìn)行視距（LOS, line of sight）傳輸，從而盡量降低路徑損耗。對(duì)于無(wú)線節(jié)點(diǎn)的發(fā)射機(jī)和接收機(jī)，則都假設(shè)是半雙工的，即同一時(shí)刻只允許一條流進(jìn)行傳輸（發(fā)送或接收）。

3.1 MAC層幀結(jié)構(gòu)

在 IEEE802.15.3c協(xié)議中，網(wǎng)絡(luò)時(shí)間被劃分成一系列的超幀[17]，其介質(zhì)訪問控制層（MAC，media access control）幀結(jié)構(gòu)如圖1所示。每一個(gè)超幀由3部分組成：信標(biāo)周期（BP, beacon period）、競(jìng)爭(zhēng)訪問周期（CAP, contention access period）、信道時(shí)間分配周期（CTAP, channel time allocation period）。在BP中，主要對(duì)來(lái)自PNC的網(wǎng)絡(luò)同步和控制信息進(jìn)行廣播，如將對(duì)各流的調(diào)度決策廣播給網(wǎng)絡(luò)中所有的無(wú)線節(jié)點(diǎn)。在 CAP中，設(shè)備通過(guò)載波監(jiān)聽多點(diǎn)接入/沖突避免（CSMA/CA, carrier sense multiple access with collision avoidance）技術(shù)將自己的傳輸請(qǐng)求發(fā)送給PNC。在CTAP中，劃分出許多時(shí)隙（TS,time slot），在每一個(gè)時(shí)隙，無(wú)線節(jié)點(diǎn)之間可以根據(jù)BP周期中接收到的調(diào)度命令進(jìn)行有效的數(shù)據(jù)傳送。在本文提出的方案中，因?yàn)楹撩撞ǖ亩ㄏ騻鬏斕匦?，每個(gè)時(shí)隙可以選擇對(duì)多個(gè)流進(jìn)行并行調(diào)度，即空時(shí)分多址接入（STDMA, spatial-time division multiple access）[18]。

圖1 IEEE802.15.3c的MAC層幀結(jié)構(gòu)

3.2 路徑損耗模型

對(duì)于毫米波WPAN來(lái)說(shuō)，本文假設(shè)節(jié)點(diǎn)之間可以進(jìn)行視距傳輸，采用文獻(xiàn)[14]中的路徑損耗模型。流i的接收機(jī)ir接收到的來(lái)自對(duì)應(yīng)發(fā)射機(jī)si的信號(hào)功率可以表示為

其中，k是與成正比的常數(shù)因子，P代表發(fā)t射機(jī)的發(fā)射功率，代表發(fā)送天線增益，代表接收天線增益，dii代表流i的發(fā)射機(jī)與接收機(jī)之間的距離，n為路徑損耗指數(shù)。

類似地，流j的發(fā)射機(jī)對(duì)流i的接收機(jī)造成的干擾則可以表示為

其中，m是與不同用戶信號(hào)間的互相關(guān)有聯(lián)系的多用戶干擾因子（MUI, multi-user interference）。

3.3 數(shù)據(jù)傳輸速率

在高斯加性白噪聲（AWGN, additive white Gaussian noise）信道中，流i可達(dá)的數(shù)據(jù)傳輸速率可以根據(jù)香農(nóng)公式得到，如式（3）所示。

其中，η是描述收發(fā)機(jī)設(shè)計(jì)效率的因子，取值范圍為（0,1）；W為信道帶寬；N0為高斯白噪聲的單邊功率譜密度。

4 問題建立與分析

假設(shè)網(wǎng)絡(luò)中PNC一共收到F條流的傳輸請(qǐng)求，每條流i都有自己的QoS需求qi。每個(gè)超幀的CTAP中包含S個(gè)時(shí)隙，每個(gè)時(shí)隙可以同時(shí)對(duì)多個(gè)流并行調(diào)度。在第s個(gè)時(shí)隙中，用一個(gè)調(diào)度向量Hs來(lái)表示在該時(shí)隙有哪些流被調(diào)度。全部時(shí)隙共S個(gè)調(diào)度向量構(gòu)成調(diào)度矩陣HF×S，若該矩陣中與流i對(duì)應(yīng)的元素則代表流i在第s個(gè)時(shí)隙中被調(diào)度；若則代表流i在第s個(gè)時(shí)隙中未被調(diào)度。

因?yàn)橛脩糁g的相互干擾，只有當(dāng)調(diào)度向量確定以后，流i的實(shí)際傳輸速率才能被確定。因此，根據(jù)式（3）在第s個(gè)時(shí)隙中流i的實(shí)際傳輸速率可以表示為

經(jīng)過(guò)T個(gè)時(shí)隙后，流i已經(jīng)達(dá)到的吞吐量可以表示為

其中，Δt代表CTAP中時(shí)隙的時(shí)長(zhǎng)，TBP代表信標(biāo)周期的時(shí)長(zhǎng)，TCAP則代表競(jìng)爭(zhēng)訪問周期的時(shí)長(zhǎng)。

出于公平與效率的折中考慮，并且考慮到 5G場(chǎng)景中各種帶寬密集型應(yīng)用對(duì)服務(wù)質(zhì)量的要求，本文以最大化網(wǎng)絡(luò)中滿足QoS需求的流數(shù)為目標(biāo)。滿足QoS需求是指，通過(guò)調(diào)度滿足了該流的最低吞吐量需求。只有滿足了數(shù)據(jù)流的QoS需求，才能保證各種帶寬密集型應(yīng)用的服務(wù)質(zhì)量。二進(jìn)制變量iF表示流i的 QoS需求是否被滿足。Fi= 1表示流i的QoS需求已經(jīng)被滿足，F(xiàn)i= 0則表示尚未滿足。據(jù)此，最優(yōu)調(diào)度問題可以被定式化為問題 P，如式（6）～式（9）所示。

約束條件為

式（8）表示該流的QoS需求必須在CTAP中給定的時(shí)隙數(shù)之內(nèi)能夠滿足。如果該流在所有的時(shí)隙中都被調(diào)度，但其QoS需求仍無(wú)法滿足，則不予調(diào)度。式（9）表示由于發(fā)射機(jī)和接收機(jī)節(jié)點(diǎn)的半雙工特性，同一節(jié)點(diǎn)在同一時(shí)刻只能對(duì)一條流進(jìn)行傳輸（發(fā)射或接收）。當(dāng)流i和流j有共享節(jié)點(diǎn)（即si=sj或si=rj或ri=sj或ri=rj）時(shí)，定義流i和流j是相鄰的。相鄰的流不能被同時(shí)調(diào)度。

問題 P是一個(gè)整數(shù)非線性規(guī)劃問題，它是NP-hard問題[4]。每條流在每個(gè)時(shí)隙都可以被調(diào)度或者不被調(diào)度，如果使用窮舉法來(lái)計(jì)算它的解，當(dāng)流數(shù)為F且時(shí)隙數(shù)為S時(shí)，計(jì)算的復(fù)雜度為2F×S。當(dāng)流數(shù)較多時(shí)，采用窮舉法是非常耗時(shí)的。因此，本文提出了一種基于沖突圖的并行調(diào)度算法來(lái)解決這個(gè)問題，以降低它的復(fù)雜度。

5 基于沖突圖的STDMA并行調(diào)度算法

本節(jié)提出了一種基于沖突圖的 STDMA調(diào)度算法，即CB-STDMA算法，用來(lái)提高被調(diào)度的流的數(shù)量。首先定義了相對(duì)干擾、沖突圖、預(yù)調(diào)度集和調(diào)度集的概念。

5.1 相對(duì)干擾

為了最大化被調(diào)度流的數(shù)量，盡可能地使被調(diào)度的數(shù)據(jù)流保持一個(gè)較高的速率，從而使調(diào)度更加有效，在對(duì)流i進(jìn)行調(diào)度決策時(shí)，如果已經(jīng)決定要調(diào)度的流中存在流j對(duì)流i的干擾大于給定的門限σ,則對(duì)流i不予調(diào)度。2條流之間的相對(duì)干擾RIji可以定義為

5.2 沖突圖

以圖2為例，圖中4個(gè)節(jié)點(diǎn)代表4條流，流1與流2之間有邊，代表流1與流2之間存在沖突，可能是由于2條流之間有共享節(jié)點(diǎn)或2條流之間干擾超過(guò)門限值導(dǎo)致的，所以流1與流2不能同時(shí)調(diào)度。流1與流4同理。而流1與流3之間沒有邊，說(shuō)明不存在共享節(jié)點(diǎn)和干擾等問題，可以同時(shí)調(diào)度。此時(shí)對(duì)應(yīng)沖突圖的鄰接矩陣A中對(duì)應(yīng)元素a12、和a14均為1，其余元素為0。

圖2 沖突圖實(shí)例

5.3 預(yù)調(diào)度集與調(diào)度集

在本文的算法中，并不是所有請(qǐng)求傳輸?shù)牧鞫伎梢员徽{(diào)度。為了解決式（6）中的最優(yōu)調(diào)度問題，使大多數(shù)流的QoS需求得以滿足，提高整個(gè)網(wǎng)絡(luò)傳輸效率，會(huì)有很小一部分流被舍棄不參與調(diào)度。因?yàn)镃TAP中時(shí)隙的個(gè)數(shù)是有限的，如果該流在所有的時(shí)隙中都被調(diào)度時(shí)，仍然不能滿足它的QoS需求，則對(duì)該流的調(diào)度實(shí)際上是一種對(duì)時(shí)隙資源的浪費(fèi)。因此，對(duì)這部分流不予調(diào)度，從而把時(shí)隙用于對(duì)其他流進(jìn)行有效的調(diào)度。為了增加調(diào)度的流數(shù)，在剩余的流中應(yīng)當(dāng)優(yōu)先對(duì)所用時(shí)隙數(shù)少的流進(jìn)行調(diào)度。當(dāng)某條流的QoS需求被滿足后，就認(rèn)為它的服務(wù)質(zhì)量已經(jīng)得到保證，繼續(xù)調(diào)度該流，對(duì)服務(wù)質(zhì)量的增加也不明顯。因此，需求被滿足的流在以后的時(shí)隙中都不會(huì)再被調(diào)度，從而把時(shí)隙資源供給更多的流使用。然后，將那些可以在給定的S個(gè)時(shí)隙內(nèi)滿足其 QoS需求的流按照傳輸所用時(shí)隙數(shù)的從小到大進(jìn)行排序，這樣得到的可以被調(diào)度的流的集合稱為預(yù)調(diào)度集（PSS, pre-schedule set），即準(zhǔn)備調(diào)度的流的集合。具體地，流i傳輸所用的時(shí)隙數(shù)可以按照式（12）進(jìn)行計(jì)算。

需要注意的是，式（12）中Ri是在沒有其他流干擾情況下得到的自身傳輸速率，即式（3）中去掉項(xiàng)得到的速率；Δt代表每個(gè)時(shí)隙的時(shí)長(zhǎng)。

此外，把第s個(gè)時(shí)隙中被調(diào)度的流的集合叫作第s個(gè)時(shí)隙的調(diào)度集（SS, schedule set），即調(diào)度向量Hs中等于 1的元素對(duì)應(yīng)的流所組成的集合。CB-STDMA 算法對(duì)于第s個(gè)時(shí)隙調(diào)度的流的數(shù)量沒有明確的限制，只要滿足可以同時(shí)傳輸?shù)臈l件，便可以同時(shí)使用第s個(gè)時(shí)隙傳輸。

事實(shí)上，根據(jù)5.2節(jié)中的沖突圖來(lái)確定單個(gè)時(shí)隙調(diào)度的流，雖然沒有確定的條數(shù)限制，但相對(duì)干擾的門限值會(huì)對(duì)流的數(shù)量進(jìn)行制約，同一時(shí)隙調(diào)度的流的條數(shù)不會(huì)太多。因?yàn)橥瑫r(shí)調(diào)度數(shù)量過(guò)多時(shí)，必然無(wú)法滿足相對(duì)干擾低于門限值的條件。所以單個(gè)時(shí)隙調(diào)度的流的個(gè)數(shù)無(wú)法確定，要由本文提出的算法根據(jù)實(shí)際情況來(lái)計(jì)算。

5.4 調(diào)度算法設(shè)計(jì)

下面對(duì) 60 GHz無(wú)線個(gè)域網(wǎng)中的 CB-STDMA算法進(jìn)行詳細(xì)描述。該調(diào)度算法的偽代碼見算法1，其中第1）行～第8）行是初始化工作，第9）行～第23）行是算法的主要部分。

首先，在某一超幀的 CAP中，各個(gè)無(wú)線節(jié)點(diǎn)將自己的位置以及數(shù)據(jù)流的傳輸請(qǐng)求發(fā)送給PNC，每條流都有自己的QoS需求qi。PNC收到各條流的傳輸請(qǐng)求后，計(jì)算各條流傳輸所用的時(shí)隙數(shù)iξ，將iξ大于CTAP中最大時(shí)隙數(shù)S的流舍棄，剩下的流按照iξ從小到大的順序排序，作為預(yù)調(diào)度集。然后，判斷可進(jìn)行同時(shí)調(diào)度的流。上述過(guò)程如算法 1中的 1）～8）行所示。

CB-STDMA算法判斷可同時(shí)調(diào)度的流是由PNC根據(jù)5.2節(jié)所描述的方法，生成包含預(yù)調(diào)度集中所有流的沖突圖即生成預(yù)調(diào)度集的對(duì)應(yīng)沖突圖的鄰接矩陣，根據(jù)式（10）計(jì)算流之間的相對(duì)干擾，然后考慮流之間是否存在共享節(jié)點(diǎn)和相對(duì)干擾是否超過(guò)門限值，來(lái)判斷能否同時(shí)調(diào)度，確定矩陣中各個(gè)元素的值。

本文調(diào)度算法為了實(shí)現(xiàn)式（6）中的優(yōu)化目標(biāo)，即盡可能提高滿足QoS需求被調(diào)度流的個(gè)數(shù)，除了選擇并行傳輸?shù)膫鬏敺绞奖旧砭涂梢蕴岣咝阅芡猓惴ㄖ羞x擇了不間斷的數(shù)據(jù)流調(diào)度方案也是實(shí)現(xiàn)優(yōu)化的關(guān)鍵。在每一個(gè)時(shí)隙結(jié)束時(shí)，都要檢查是否有某些流的QoS需求已經(jīng)被滿足。當(dāng)一個(gè)流的QoS需求已經(jīng)被滿足時(shí)，就將調(diào)度向量Hs中對(duì)應(yīng)的元素設(shè)為-1，表示該流在以后的時(shí)隙中都不能被調(diào)度，并在下一時(shí)隙選擇滿足條件的新的流加入調(diào)度集合。對(duì)于沒有完成其QoS需求的流，下一時(shí)隙中則繼續(xù)調(diào)度。這一過(guò)程如算法1中 20）行～22）行所示。算法中調(diào)度向量Hs中值為-1的元素越多，表示有越多的被調(diào)度流已經(jīng)滿足QoS需求，越能體現(xiàn)出算法的優(yōu)越性。

對(duì)于每一個(gè)時(shí)隙，如果是第一個(gè)時(shí)隙或者在上一個(gè)時(shí)隙中有新的流達(dá)到了其QoS需求，就開始一輪新的調(diào)度決策。對(duì)預(yù)調(diào)度集中的每一條流按順序進(jìn)行判斷，如果這條流以前沒有被調(diào)度過(guò)，并且與當(dāng)前調(diào)度集中的流（即已經(jīng)決定被調(diào)度的流）之間沒有沖突，則接著對(duì)調(diào)度這條流的收益進(jìn)行評(píng)估。評(píng)估的標(biāo)準(zhǔn)是，如果把它加到當(dāng)前調(diào)度集中可以增加網(wǎng)絡(luò)的總吞吐量，就把該流添加進(jìn)來(lái)，否則放棄對(duì)該流的調(diào)度，繼續(xù)對(duì)下一條流進(jìn)行判斷。這一部分如算法1中的11）行～17）行所示。直到所有時(shí)隙都做出了調(diào)度決策，從而得出了S個(gè)時(shí)隙的調(diào)度矩陣HF×S。

算法1CB-STDMA并行調(diào)度算法

1） PNC接收各個(gè)節(jié)點(diǎn)的位置以及帶有QoS需求qi的F個(gè)流的傳輸請(qǐng)求，并初始化F×1的預(yù)調(diào)度集PSS = 1

2） 初始化調(diào)度矩陣HF×S=0

3） 計(jì)算每個(gè)流傳輸所用的時(shí)隙數(shù)iξ,并將PSS中的流按所用時(shí)隙數(shù)從小到大順序排列，I= 排序后的序號(hào)

4）ifξi＞Sthen

5）F = i-1

6） 更新F×1 的 PSS 以及HF×S

7）end if

8） 構(gòu)建F個(gè)流的沖突圖G，初始化change = 1

9）for時(shí)隙i（1≤i≤M）

10）ifchange = 1then

11）for流f（1≤f≤F）do

12）ifSi（f） = 0且i與當(dāng)前調(diào)度集中其他流沒有沖突then

13）if加入流f可以增加網(wǎng)絡(luò)總吞吐量then

14）Si（f） = 1

15）end if

16）end if

17）end for

18）end if

19） change= 0,Hs+1=Hs

20）if存在Ti≥qithen

21） change = 1,Hs+1（i） = -1

22）end if

23）end for

6 性能評(píng)估

本節(jié)對(duì)本文提出的調(diào)度算法進(jìn)行了仿真，并與文獻(xiàn)[4]提出的MQIS并行調(diào)度算法、文獻(xiàn)[12]中提出的STDMA并行調(diào)度算法和TDMA調(diào)度算法進(jìn)行了對(duì)比。在TDMA算法中，CTAP的每一個(gè)時(shí)隙中只允許一條流進(jìn)行傳輸。

6.1 仿真參數(shù)設(shè)置

假設(shè)60 GHz 無(wú)線個(gè)域網(wǎng)中有10個(gè)無(wú)線節(jié)點(diǎn)隨機(jī)分布在10 m×10 m的方形區(qū)域內(nèi)，PNC位于區(qū)域的中央。每個(gè)節(jié)點(diǎn)所配置的定向天線產(chǎn)生的波束寬度為60°，并且使用文獻(xiàn)[15]中的實(shí)際定向天線模型。每條流的源節(jié)點(diǎn)和目的節(jié)點(diǎn)都是隨機(jī)選擇的，節(jié)點(diǎn)之間的平均距離是1 m。每條流的QoS需求是在1 Gbit/s到3 Gbit/s之間均勻分布的隨機(jī)變量。仿真中其他的一些主要參數(shù)如表1所示。

在不同任務(wù)數(shù)時(shí)都是影響系統(tǒng)性能的關(guān)鍵因素。而存儲(chǔ)服務(wù)器CPU性能和磁盤性能則在不同任務(wù)數(shù)時(shí)對(duì)系統(tǒng) I/O響應(yīng)時(shí)間的影響都很小，屬于非關(guān)鍵性能影響因素。上述網(wǎng)絡(luò)RAID存儲(chǔ)系統(tǒng)因素的一種有效手段，在優(yōu)化系統(tǒng)性能時(shí)，可基于上述分析結(jié)果著重考慮改善關(guān)鍵性能影響因素，忽略非關(guān)鍵性能影響因素，以達(dá)到事半功倍的效果。

6.2 性能指標(biāo)

為了驗(yàn)證所提出的調(diào)度方案的性能，本文主要從滿足QoS需求的流數(shù)以及系統(tǒng)的吞吐量這2個(gè)方面進(jìn)行評(píng)估。系統(tǒng)的吞吐量是指網(wǎng)絡(luò)中所有流的吞吐量總和。

分別改變網(wǎng)絡(luò)中發(fā)出傳輸請(qǐng)求的總流數(shù)、CTAP中時(shí)隙的個(gè)數(shù)以及判斷相對(duì)干擾時(shí)所用的判決門限σ，觀察滿足QoS需求的流數(shù)和系統(tǒng)吞吐量的變化情況。所有仿真結(jié)果圖中的每個(gè)點(diǎn)是100次隨機(jī)仿真后的平均值。

6.3 仿真結(jié)果與分析

滿足 QoS需求的流數(shù)和系統(tǒng)吞吐量隨著網(wǎng)絡(luò)中總流數(shù)的變化分別如圖3和圖4所示。此時(shí)時(shí)隙數(shù)為2 000，判決門限為10-1。

圖3 不同流數(shù)下滿足QoS需求的流數(shù)

圖4 不同流數(shù)下的系統(tǒng)吞吐量

從圖3和圖4可以看出，當(dāng)網(wǎng)絡(luò)中流的總數(shù)增長(zhǎng)時(shí)，本文提出的CB-STDMA算法、MQIS算法和STDMA算法滿足QoS需求的流數(shù)和系統(tǒng)吞吐量這2個(gè)指標(biāo)都隨之增長(zhǎng)，但是TDMA算法的2個(gè)指標(biāo)卻幾乎不變。這是因?yàn)門DMA算法在每個(gè)時(shí)隙只能對(duì)一個(gè)流進(jìn)行調(diào)度，所以不管流的總數(shù)如何變化，它所能滿足的流數(shù)是有限的。而CB-STDMA算法、MQIS算法和STDMA算法允許多條流之間的并行傳輸，所以流的總數(shù)越多，進(jìn)行并行調(diào)度的機(jī)會(huì)越大，能滿足需求的流數(shù)和系統(tǒng)吞吐量也越大。但由于系統(tǒng)容量和時(shí)隙資源的限制，增長(zhǎng)趨勢(shì)逐漸趨于平緩。此外，CB-STDMA算法比MQIS算法和STDMA算法性能更優(yōu)越。特別地，當(dāng)流總數(shù)為90時(shí)，MQIS算法能成功滿足 13條流，吞吐量約為 24 Gbit/s，STDMA算法能成功滿足約10條流，吞吐量約為25 Gbit/s，CB-STDMA算法則可以成功滿足約16條流，吞吐量達(dá)到約 30 Gbit/s。與 MQIS和STDMA相比，CB-STDMA滿足QoS需求的流數(shù)分別增長(zhǎng)了約23%和60%，吞吐量分別增長(zhǎng)了約25%和 20%。造成這種現(xiàn)象的原因主要來(lái)自于以下2個(gè)方面。

1） MQIS算法中，只利用并行傳輸和QoS需求來(lái)判定優(yōu)先級(jí)，沒有舍棄部分需求過(guò)大的流，也沒有考慮調(diào)度流的條數(shù)和傳輸效率，會(huì)造成部分資源浪費(fèi)。STDMA算法中，只要將流加入調(diào)度集可以增加網(wǎng)絡(luò)的吞吐量，就決定調(diào)度該流，沒有考慮調(diào)度集中其他流對(duì)該流的干擾。而 CBSTDMA中，將網(wǎng)絡(luò)中所有流的沖突關(guān)系都用沖突圖表示出來(lái)，根據(jù)流之間的沖突關(guān)系進(jìn)行調(diào)度，使得調(diào)度集中不同流間相互干擾減小，從而增加了所調(diào)度的流的傳輸速率。

2） 在CB-STDMA算法中，按照所需時(shí)隙數(shù)由少到多的優(yōu)先級(jí)順序?qū)α鬟M(jìn)行選擇調(diào)度，并不是所有請(qǐng)求傳輸?shù)牧鞫伎梢员徽{(diào)度，若CTAP中所有時(shí)隙都不夠滿足該流的傳輸需求，則直接舍棄該流不予調(diào)度，這樣便能節(jié)省出時(shí)隙，供給那些可以實(shí)現(xiàn)其 QoS需求的流利用，使整個(gè)網(wǎng)絡(luò)的傳輸效率得到明顯提高。綜上所述，CB-STDMA算法在優(yōu)化問題，即被調(diào)度流的數(shù)量和網(wǎng)絡(luò)總吞吐量方面有著明顯的優(yōu)勢(shì)。

滿足QoS需求的流數(shù)和系統(tǒng)吞吐量隨著CTAP中時(shí)隙數(shù)目的變化如圖4和圖5所示。此時(shí)網(wǎng)絡(luò)中的總流數(shù)為90，門限值仍取10-1。

圖5 不同時(shí)隙數(shù)下滿足QoS需求的流數(shù)

圖6 不同時(shí)隙數(shù)下的系統(tǒng)吞吐量

從圖5和圖6中可以看出，CB-STDMA算法的2種指標(biāo)仍然都優(yōu)于MQIS算法、STDMA算法和TDMA算法。特別地，在時(shí)隙數(shù)為5 000時(shí)，CB-STDMA與MQIS相比，成功滿足的流數(shù)增加了超過(guò) 23%，系統(tǒng)吞吐量增加了約 25%；而CB-STDMA比 STDMA成功滿足的流數(shù)增加了超過(guò)60%，系統(tǒng)吞吐量增加了約20%。但是，這4種算法都只在時(shí)隙數(shù)為500到2 000時(shí)性能有增長(zhǎng)趨勢(shì)，當(dāng)時(shí)隙數(shù)超過(guò)2 000時(shí)，性能幾乎沒有變化。這是因?yàn)樵跁r(shí)隙資源較少時(shí)，時(shí)隙數(shù)是影響網(wǎng)絡(luò)性能的主要限制因素，有限的資源無(wú)法滿足較多流的QoS需求，因此增加時(shí)隙數(shù)使更多的流成功調(diào)度并且增加網(wǎng)絡(luò)的吞吐量。而時(shí)隙數(shù)目繼續(xù)增加時(shí)，由式（5）可知，吞吐量與時(shí)隙數(shù)的關(guān)系不大，因此總吞吐量并沒有太大變化，滿足最小吞吐量需求的流數(shù)也沒有太大變化。所以，想要達(dá)到理想的優(yōu)化目標(biāo)，獲得更多被調(diào)度的流，并且保證資源的充分利用，必須選擇合適的時(shí)隙數(shù)目。在本文其他仿真中，只要選擇時(shí)隙數(shù)在2 000時(shí)就足夠得到接近最優(yōu)的性能。

改變沖突圖中的干擾判決門限σ，相應(yīng)的指標(biāo)變化如圖7和圖8所示。圖中的橫坐標(biāo)是將門限值以10為底取對(duì)數(shù)的值（如門限值為10-1時(shí)，則橫坐標(biāo)為-1）。此時(shí)流的總數(shù)取90，時(shí)隙數(shù)取2 000。

圖7 不同門限值下滿足QoS需求的流數(shù)

圖8 不同門限值下的系統(tǒng)吞吐量

從圖7和圖8中可以看出，TDMA與STDMA因?yàn)椴簧婕皼_突圖中的干擾判斷門限，因此網(wǎng)絡(luò)性能并不隨著門限值變化。而對(duì)于 CB-STDMA和MQIS，若門限設(shè)置過(guò)小，則2條流之間有很小干擾時(shí)就認(rèn)為它們之間有沖突，不利于對(duì)流進(jìn)行充分的調(diào)度。此時(shí)，門限值是限制網(wǎng)絡(luò)性能的主要因素，增大門限值有利于增加滿足 QoS需求的流數(shù)和網(wǎng)絡(luò)的總吞吐量，因此曲線在門限值為10-4～10-1時(shí)呈上升趨勢(shì)。當(dāng)門限值繼續(xù)增大時(shí)，即使各條流之間有較大的干擾，也認(rèn)為它們之間不存在沖突，這時(shí)將受到干擾較大的流加入調(diào)度集中，對(duì)于增加網(wǎng)絡(luò)的性能是不利的，因此門限值為10-1～1時(shí)，曲線出現(xiàn)下降。在門限值10-1時(shí)，本文提出的CB-STDMA算法性能最優(yōu)，這也是在之前仿真中將門限值設(shè)為 10-1的原因。門限值大于10時(shí)，由于流之間的相對(duì)干擾根本達(dá)不到這么大，門限值失去了它的約束作用，因此CB-STDMA的相應(yīng)指標(biāo)曲線也變得平坦。

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

本文為毫米波無(wú)線個(gè)域網(wǎng)場(chǎng)景設(shè)計(jì)了一種基于沖突圖的并行調(diào)度算法。在進(jìn)行調(diào)度決策時(shí)，考慮了網(wǎng)絡(luò)全局的沖突條件，包括流之間的互干擾條件和半雙工限制條件，并優(yōu)先調(diào)度容易滿足QoS需求的流，從而最大化滿足QoS需求的流數(shù)和網(wǎng)絡(luò)吞吐量。仿真結(jié)果表明，本文提出的CB-STDMA算法與STDMA算法和TDMA算法相比，在滿足QoS需求的流數(shù)和網(wǎng)絡(luò)吞吐量方面均有大幅提升。此外，通過(guò)仿真還發(fā)現(xiàn)，通過(guò)優(yōu)化沖突判決時(shí)的門限值可提升算法的性能。