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

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

1 引言

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

2 相關(guān)工作

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

本文提出了一種基于沖突圖的空時分多址接入調(diào)度算法（CB-STDMA, contention graph based spatial-time division multiple access）。該算法對相同級別的流進行調(diào)度，一方面讓所用時隙數(shù)較少的流優(yōu)先被調(diào)度，從而節(jié)省出寶貴的時隙資源來調(diào)度更多的流；另一方面，只有被調(diào)度的流之間沒有沖突，即不是相鄰鏈路且相互干擾小于某個門限值時才能被同時調(diào)度，使被調(diào)度的流保持較高的速率，從而進一步增加了網(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ǎng)場景。場景中包括一個微微網(wǎng)控制（PNC, piconet controller）和幾個無線節(jié)點（WN,wireless node）。無線節(jié)點之間可能有數(shù)據(jù)流需要進行傳輸，每條流都有自己的最低吞吐量需求，即QoS需求。PNC可以對網(wǎng)絡(luò)中的數(shù)據(jù)傳輸進行同步和協(xié)調(diào)[15]，并且可以獲得每條流的QoS需求以及各個無線節(jié)點的位置。每個無線節(jié)點都裝有電子導向定向天線，從而使收發(fā)器之間可以進行定向傳輸來提高天線增益[16]。另外，假設(shè)各無線節(jié)點之間進行視距（LOS, line of sight）傳輸，從而盡量降低路徑損耗。對于無線節(jié)點的發(fā)射機和接收機，則都假設(shè)是半雙工的，即同一時刻只允許一條流進行傳輸（發(fā)送或接收）。

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

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

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

3.2 路徑損耗模型

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

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

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

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

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

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

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

4 問題建立與分析

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

因為用戶之間的相互干擾，只有當調(diào)度向量確定以后，流i的實際傳輸速率才能被確定。因此，根據(jù)式（3）在第s個時隙中流i的實際傳輸速率可以表示為

經(jīng)過T個時隙后，流i已經(jīng)達到的吞吐量可以表示為

其中，Δt代表CTAP中時隙的時長，TBP代表信標周期的時長，TCAP則代表競爭訪問周期的時長。

出于公平與效率的折中考慮，并且考慮到 5G場景中各種帶寬密集型應(yīng)用對服務(wù)質(zhì)量的要求，本文以最大化網(wǎng)絡(luò)中滿足QoS需求的流數(shù)為目標。滿足QoS需求是指，通過調(diào)度滿足了該流的最低吞吐量需求。只有滿足了數(shù)據(jù)流的QoS需求，才能保證各種帶寬密集型應(yīng)用的服務(wù)質(zhì)量。二進制變量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ù)之內(nèi)能夠滿足。如果該流在所有的時隙中都被調(diào)度，但其QoS需求仍無法滿足，則不予調(diào)度。式（9）表示由于發(fā)射機和接收機節(jié)點的半雙工特性，同一節(jié)點在同一時刻只能對一條流進行傳輸（發(fā)射或接收）。當流i和流j有共享節(jié)點（即si=sj或si=rj或ri=sj或ri=rj）時，定義流i和流j是相鄰的。相鄰的流不能被同時調(diào)度。

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

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

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

5.1 相對干擾

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

5.2 沖突圖

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

圖2 沖突圖實例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4）ifξi＞Sthen

5）F = i-1

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

7）end if

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

9）for時隙i（1≤i≤M）

10）ifchange = 1then

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

12）ifSi（f） = 0且i與當前調(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 性能評估

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

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

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

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

6.2 性能指標

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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