基于沖突圖的毫米波無線個域網并行調度方案

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

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

1 引言

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

2 相關工作

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

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

3 系統模型

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

3.1 MAC層幀結構

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

圖1 IEEE802.15.3c的MAC層幀結構

3.2 路徑損耗模型

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

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

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

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

3.3 數據傳輸速率

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

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

4 問題建立與分析

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

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

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

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

出于公平與效率的折中考慮，并且考慮到 5G場景中各種帶寬密集型應用對服務質量的要求，本文以最大化網絡中滿足QoS需求的流數為目標。滿足QoS需求是指，通過調度滿足了該流的最低吞吐量需求。只有滿足了數據流的QoS需求，才能保證各種帶寬密集型應用的服務質量。二進制變量iF表示流i的 QoS需求是否被滿足。Fi= 1表示流i的QoS需求已經被滿足，Fi= 0則表示尚未滿足。據此，最優調度問題可以被定式化為問題 P，如式（6）～式（9）所示。

約束條件為

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

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

5 基于沖突圖的STDMA并行調度算法

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

5.1 相對干擾

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

5.2 沖突圖

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

圖2 沖突圖實例

5.3 預調度集與調度集

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

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

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

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

5.4 調度算法設計

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

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

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

本文調度算法為了實現式（6）中的優化目標，即盡可能提高滿足QoS需求被調度流的個數，除了選擇并行傳輸的傳輸方式本身就可以提高性能外，算法中選擇了不間斷的數據流調度方案也是實現優化的關鍵。在每一個時隙結束時，都要檢查是否有某些流的QoS需求已經被滿足。當一個流的QoS需求已經被滿足時，就將調度向量Hs中對應的元素設為-1，表示該流在以后的時隙中都不能被調度，并在下一時隙選擇滿足條件的新的流加入調度集合。對于沒有完成其QoS需求的流，下一時隙中則繼續調度。這一過程如算法1中 20）行～22）行所示。算法中調度向量Hs中值為-1的元素越多，表示有越多的被調度流已經滿足QoS需求，越能體現出算法的優越性。

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

算法1CB-STDMA并行調度算法

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

2） 初始化調度矩陣HF×S=0

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

4）ifξi＞Sthen

5）F = i-1

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

7）end if

8） 構建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與當前調度集中其他流沒有沖突then

13）if加入流f可以增加網絡總吞吐量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 性能評估

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

6.1 仿真參數設置

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

在不同任務數時都是影響系統性能的關鍵因素。而存儲服務器CPU性能和磁盤性能則在不同任務數時對系統 I/O響應時間的影響都很小，屬于非關鍵性能影響因素。上述網絡RAID存儲系統因素的一種有效手段，在優化系統性能時，可基于上述分析結果著重考慮改善關鍵性能影響因素，忽略非關鍵性能影響因素，以達到事半功倍的效果。

6.2 性能指標

為了驗證所提出的調度方案的性能，本文主要從滿足QoS需求的流數以及系統的吞吐量這2個方面進行評估。系統的吞吐量是指網絡中所有流的吞吐量總和。

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

6.3 仿真結果與分析

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

圖3 不同流數下滿足QoS需求的流數

圖4 不同流數下的系統吞吐量

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

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

2） 在CB-STDMA算法中，按照所需時隙數由少到多的優先級順序對流進行選擇調度，并不是所有請求傳輸的流都可以被調度，若CTAP中所有時隙都不夠滿足該流的傳輸需求，則直接舍棄該流不予調度，這樣便能節省出時隙，供給那些可以實現其 QoS需求的流利用，使整個網絡的傳輸效率得到明顯提高。綜上所述，CB-STDMA算法在優化問題，即被調度流的數量和網絡總吞吐量方面有著明顯的優勢。

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

圖5 不同時隙數下滿足QoS需求的流數

圖6 不同時隙數下的系統吞吐量

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

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

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

圖8 不同門限值下的系統吞吐量

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

7 結束語

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