分布式排隊中退避樹的深度優先遍歷算法

王文鼐，張延賀，吳煒，柏琛，王斌

（南京郵電大學通信與信息工程學院，江蘇 南京 210003）

1 引言

分布式排隊（DQ,distributed queuing）是綜合了時分復用（TDM,time division multiplex）和隨機多址接入（RMA,random multiple access）2 種手段的媒質訪問控制方法，其最初目標是高效解決有線電視電纜的多站接入沖突[1]。由于DQ 的吞吐性能和重載穩定性接近理想的無沖突M/D/1 排隊系統[2]，其近年來被擴展到各類無線接入網，特別是終端密度高、業務突發性強、功能復雜度低的物聯網（IoT,Internet of things）[3-8]，甚至被視為ALOHA 技術的終結者[9]。

DQ 系統包含一個集中式協調者和2 個分布式虛擬隊列，分別為爭用請求隊列（CRQ,contention request queue）和數據發送隊列（DTQ,data-transmit queue）[1]。CRQ 的離隊站點隨機爭用共享信道，爭用成功時進入DTQ，否則返回CRQ 退避。DTQ 的離隊站點以TDM 方式無沖突地占用信道。共享信道的爭用狀態由協調者監測和反饋，其功能可以由小區制基站或接入點（AP,access point）實現[3-4]，也可以由自組織網絡的簇頭臨時實現[5]。DQ 時隙結構和爭用信號方式有很大的靈活性，能適應不同的應用環境。

文獻[3]針對長期演進技術（LTE,long term evolution）物理隨機接入信道（PRACH,physical random access channel）提出了一種基于前導信號的DQ 應用方案，發現用戶設備的接入阻塞率、吞吐量和能耗都有顯著優勢，尤其是在重載時阻塞率保持為零。文獻[4]發現DQ 用于窄帶物聯網（NB-IoT,narrow band Internet of things）時，在保持100%接入成功率的同時，通過資源分組能進一步減少接入時延。文獻[5]針對IEEE 802.11 WLAN 提出了一種基于請求發送（RTS,request to send）控制幀的DQ爭用時隙方案，發現吞吐量至少能提升25%。文獻[6]將DQ 用于Ad-Hoc 網絡，發現重負載時DQ 吞吐量可比傳統的IEEE 802.11 技術提高85%。文獻[7]針對LoRaWAN 設計了一種DQ 驗證原型，估算發現，在增大TDM 時隙的占比后，相同性能條件下能將接入容量從1 500 個終端提高到5 712 個終端。本文的先期工作提出另一種DQ 結合LoRaWAN 的方案，通過數值仿真發現，與現有技術標準的接入方案相比，吞吐量可增大2.6 倍，500 個終端并發時的平均時延可降低54%[8]。

相比于ALOHA，DQ 表現出全方位的性能優勢，原因有以下2 個方面：1)DQ 將爭用沖突壓縮在相對短時長的爭用時隙；2)DQ 采用樹型退避算法以指數形式遞減并發站點數。相比于早期的樹型隨機多址[10]，DQ 分配了多個爭用時隙。爭用時隙數目m越大，沖突解決時效性越好，但相應的時間開銷也越大，反而會降低有效吞吐量。文獻[2]的理論分析發現，m=3 是較好的折中條件。文獻[8]的數值仿真發現，m=3 這一條件僅適用于中等規模的多站并發。在不增大m的前提下提高沖突解決時效，目前尚未見公開報道。

DQ 調度的重載性能穩定，功能相對簡單，對以ALOHA 技術為基礎的物聯網接入等新型業務有很大的應用潛力[9]，因此受到研究者的關注。本文分析DQ 退避樹遍歷的計算優化，以進一步提高沖突解決時效性，研究用深度優先方法代替傳統的廣度優先方法。

2 DQ 工作機制

2.1 系統組成與時序

ALOHA 完全由數據站組成[10]，而DQ 系統則引入一個集中式協調者站點。為敘述方便，以下假設協調者功能部署在小區中心基站或AP，數據站為小區終端，DQ 的調度對象是并發終端至基站上行的數據傳輸。

DQ 以時分復用方式共享信道，重復的DQ 周期包含上行爭用時隙（CS,contention slot）和數據時隙（DS,data slot），以及協調者至所有終端的下行反饋時隙（FS,feed-back slot）[1]。CS 嵌套m個小時隙/子時隙（MS,mini-slot）。DQ 時域共享信道的時隙劃分結構如圖1 所示。

圖1 DQ 時域共享信道的時隙劃分結構

圖1 中，信標（BCN,beacon）廣播起到定時同步的作用，幀間空隙（IFS,inter-frame space）用于容納上下行傳播時延。N個DQ 調度周期構成一個BCN 周期，N值由BCN 廣播通告或者動態配置。

在一個BCN 周期內新到的終端發送請求，并推至下一個BCN 周期。爭用時隙包含m個子時隙供終端隨機爭用，其中m≥2。一個DQ 調度周期只包含一個數據時隙，多個爭用成功的終端順序排隊占用多個DQ 周期內的DS。

靜態系統配置固定的子時隙數m，以及固定時長的MS、CS、DS 和FS。

2.2 分布式排隊過程

為方便說明，DQ 終端標識記為k，k∈[0,Kn?1]，其中，Kn為第n個DQ 周期內并發爭用DS 的終端總數，n∈[0,N?1]。爭用終端k在m個MS 中以等概率隨機選擇一個發送請求幀或請求信號，選中的MS 索引記為rk，rk∈[0,m?1]。

協調者監聽CS 內所有MS。當僅有一個終端占用MS 時，由于可以正確恢復出請求信息，因此易被判定為爭用成功；當2 個及2 個以上終端占用MS 時，由于存在互干擾，因此易被判定為爭用失敗；當沒有終端占用MS 時，因無載波信號而易被判定為空閑。

協調者在FS 以廣播方式反饋MS 的監聽結果或MS 狀態，記為ai，i∈[0,m?1]。不失一般性地，設ai=0 表示空閑，ai=1 表示爭用成功，ai=2 表示沖突或爭用失敗。

所有爭用終端在每個DQ 周期FS 接收來自協調者的ai反饋結果，獨立計算式(1)。

其中，G為爭用成功的終端個數，C為爭用失敗的終端組的個數，gk為終端k爭用成功時的次序號，ck為終端k爭用失敗時的次序號。當ai=n時δ(ai,n)=1，否則δ(ai,n)=0。

協調者在監聽MS 狀態的同時，同理計算G和C，并分別累加到由其集中維護的DTQ 長度LT和CRQ 長度LC。

如果ai=1，且rk=i在G個成功者中的次序為gk，gk∈[0,G?1]，則終端k進入DTQ 隊尾，并由該終端自身記錄其在DTQ 中的位置為

其中，LT由協調者統計和廣播通告，其隨G遞增、隨DQ 周期遞減；gk是對ai的統計結果；pk隨DQ周期遞減。

如果aj=2，且rk=j在C個失敗組中的次序為ck，ck∈[0,C?1]，則所有選中j的終端返回CRQ 隊尾，并由這些終端自身記錄其在CRQ 中的位置為

其中，LC由協調者按DTQ 相同的方法計算和通告，ck是對ai的統計結果，qk隨DQ 周期遞減。

式(1)～式(3)的計算依賴于協調者在FS 的廣播反饋，FS 和m個MS 的總時長是分布式排隊的系統開銷。

2.3 沖突解決過程

隊列CRQ 和DTQ 在DQ 中并無物理實體，排隊功能分布在各個終端，所以是虛擬的。LT和LC由協調者在FS 中隨ai一起廣播給所有終端。顯然，每個DTQ 位置上最多只能有一個終端，而每個CRQ 位置上的一組終端至少有2 個成員，它們是后繼DQ 周期參與爭占的終端數，即Kn。

以m=2 為例，設初始時K0=18，有LC=0，LT=0。在初始DQ 周期T0，假設2 個MS 各有9 個終端選中，則G=0，C=2，LC=2，LT=0。由式(1)～式(3)可知，協調者將隊列長度LC和LT以及MS 狀態以廣播方式反饋給所有終端，沖突終端依此分為兩組退避重入CRQ。結果是，CRQ 隊首2 個位置各有一組終端，每組各有9 個終端。因此，在DQ 周期T1和T2，有K2=K3=9。

在DQ 周期T1，設2 個MS 各有5 個和4 個站點，可得G=0，C=2，LC=3，依次類推。變量Kn、G、C、LT、LC，以及終端k在隊列中的位置pk和qk，取決于該終端選取MS 的具體情況。圖2 描述了其中一種可能的過程。其中，矩形框表示小時隙，其中數字表示爭用終端的數量，粗邊框表示沖突，細邊框表示成功；細箭頭線表示終端組的樹型分割，粗箭頭線表示樹的遍歷次序。

圖2 DQ 沖突退避與解決的過程示例

圖2 中，2 個一組的矩形框表示2 個MS，中間數值表示并發爭用的終端數。爭用失敗的終端按所選MS 的序號，進入CRQ 隊尾退避等待和重新爭用。從圖2 給出的特定時序可以看出，在第8 個DQ 周期T7，沖突得到部分解決，LC開始減小，DTQ有成功者入隊。

需要說明的是，圖2 對應于終端以大概率平均選擇MS 的情況，如果終端選擇出現隨機偏離，將增加退避樹的深度及調度的遍歷時長。

3 改進算法

3.1 樹遍歷的優化機會

DQ 沖突退避采用了樹型分割方法對一組終端迭代細分，對應的遍歷次序具有寬度優先搜索（BFS,breadth first searching）特點。當初始終端數遠大于MS 配置數，即K0＞＞m時，到達沖突解決的葉節點需要遍歷大量存在沖突的樹的中間節點。

從圖2 可以直觀地看出，在相同MS 配置數的情況下，換用深度優先搜索（DFS,depth first searching）可以更快地到達沖突解決的葉子節點，競選出DTQ的入隊終端。圖3 描述了一個可能的遍歷過程。

圖3 DFS 遍歷沖突解決葉子節點示例

圖3 中，虛邊框表示MS 未被任何終端選中，即空閑狀態。為簡化繪制，圖3 主要給出DFS 搜索至前2 個葉子節點的過程，省略了后繼的遍歷細節。

從圖3 可以直觀地看出，在第4 個DQ 周期（T3）得到2 個DTQ 入隊終端，這比BFS 提前了4 個DQ周期。因此，基于DFS 的CRQ 退避規則能更快地解決爭用沖突。

3.2 算法設計

改進算法沿用與BFS 相同的MS 監聽和DTQ調度規則。協調者在得到MS 狀態后，同樣將LT、LC和MS 的狀態反饋給所有終端，同時進行隊列長度更新。

其中，G是爭用成功的MS 個數，C是沖突失敗的MS 個數，減1 對應于隊首離隊情況。另外，隊列長度減至0 時不再減小。

DFS 的作用主要體現在沖突時終端的CRQ 位置更新和計算。BFS 中，終端返回CRQ 隊尾，而在DFS中則進入CRQ 隊首以獲得優先重試機會。這就要求在CRQ 中排隊的終端后移位置，具體計算式為

其中，C由各終端獨立地從FS 反饋信息計算得出，減1 計算對應于排隊前移。

對于從CRQ 離隊但爭用失敗的終端k，返回CRQ 的位置就是計算前述的變量ck，即終端所選rk在C個沖突MS 中的次序。算法1 給出了分布的終端獨立執行DFS 退避的偽代碼，其中，a[i]=0、1、2 分別表示MS 處于空閑、成功、沖突狀態，r=0,1,…,m?1 表示終端所選MS 的索引號，q表示終端在CRQ 中的位置。

算法1 中CRQ-POS 針對退避等待和爭用狀態分別處理。第2)～9)行是已處于退避等待終端的位置后移，第12)～14)行及函數DTQ-POS 是對爭用成功計算DTQ 位置，第15)～22)行針對爭用失敗按序進入CRQ 隊頭。需要注意的是，以上偽代碼省略了MS 為空閉和通信出錯的處理。

CRQ-POS 的唯一預設條件是在調用CRQ-POS之前，當終端CRQ 位置q=0 時，該終端獨立地以一致概率在區間[0,m?1]生成隨機整數，并記錄在參量r中。

算法1 中第13)行調用的函數DTQ-POS 的主要功能是確定爭用成功的終端在DTQ 中的位置，按式(2)計算。

相比于BFS，以上基于DFS 的改進算法的復雜度僅增加了終端在CRQ 隊內排隊等待的后移計算，即算法CRQ-POS 的第2)～9)行。如圖3 所示，這種極小量的計算開銷帶來了改善系統吞吐性能的預期。當然，這里的后移計算，其前提是CRQ 隊內的退避終端要持續不斷地監聽和處理來自協調者的反饋信息。

4 吞吐性能對比分析

4.1 吞吐量最大條件

圖1 表示的DQ 周期中，將MS 的時長記為TM，DS、FS 和IFS 的時長分別記為TDS、TFS和TIFS，則共享信道的吞吐量為

其中，u表示有數據傳輸的DS 總數，v表示無數據傳輸的DS 總數。

設一個BCN 周期正好容納所有終端的數據發送，則u=K0，N=u+v。

從式(7)可知，v和m越小，S越大。但m越小，對應于CS 內嵌的MS 越少，終端爭用的沖突概率越大，導致v越大。所以，以吞吐量最大為目標，最佳m需滿足

4.2 完全樹的對比分析

圖4 給出了K0=32 時沖突退避構成完全二叉樹的特例。圖4(a)對應BFS，圖4(b)對應DFS。

圖4 K0=32 時沖突退避構成完全二叉樹的特例

圖4 中，樹中圓節點表示MS 沖突的情況，方形葉子節點表示沖突解決。樹遍歷過程只涉及圓節點，實心圓表示v的貢獻項，空心圓表示因DS 內有數據傳輸而對v無貢獻的情況。

圖4(a)樹根對應樹的第0 層，初始時DS 無數據發送，v=1，2 個MS 各分16 個終端；第1 層2 個中間節點，對應DS 同樣無數據發送，所以v=1+2=3；第3 層，v=15；第4 層左側第1 個節點仍有沖突，v=16；第5 層為2 個葉子節點，所以第4 層后繼節點遍歷時DS 有數據發送，它們對v無貢獻。因此可得v=16。

圖4(b)樹根至最左側葉子節點，深度為4，其中DS 無數據發送，所以v=4。該樹的后繼遍歷中，所至中間節點均有對應的葉子節點，如圖4(b)中序號為1～16 的節點所示，它們對v無貢獻。因此可得v=4。

以上針對K0=2L的完全二叉樹，從圖4(a)表示的BFS 遍歷可得，v=2L?1=16，從圖4(b)表示的DFS可得，v=L?1=4，其中，L=lbK0為樹的深度。對于m≥2 的一般情況，可得L=logm(K0)，且

對于DFS，從式(13)可知，因為m＞1，所以dvDFS/dm＞0。代入式(8)，左側總是大于0，所以吞吐量最大條件是mDFS_MAX=2，有

因為K0＞＞2，所以K0+lbK0?1≈K0。

定義加率比f=SDFS_MAX/SBFS_MAX，則有

易得，當α=4 時，有最大加速比f=1.5。

4.3 一般隨機樹的對比分析

以上推算雖然只適用于完全樹的特例，但DFS性能優于BFS 的結論適用于一般性情況。這是因為，當K0＞＞m時，終端均勻爭用各小時隙的概率最大，完全樹分布對性能貢獻權重也最大。此外，一般隨機樹的情況可等效于完全樹的隨機重構。

從K0=mL完全樹出發，隨機選取一個葉子節點，將其修減，得到K0?1 的隨機樹；將其移接到其他隨機選取的葉子節點，則得到一個非平衡的隨機樹。修減一個葉子節點，對變量v至多貢獻一次正計數。移接一個葉子節點，將對BFS 的v增加一個計數，而對DFS 的v，只在前驅遍歷LT=0 時才有一次加1 的貢獻。總體上，完全樹隨機重構后，基于DFS 的沖突解決仍然快于BFS。

當然，完全樹隨機重構后，式(16)和式(17)最大吞吐量條件會存在偏離。相應地，式(18)給出的加速比只可視為一個近似估計。下面，通過隨機化網絡仿真說明更一般的情況。

5 數值仿真驗證

5.1 仿真軟件設計

如前文所述，傳統基于BFS 的DQ 調度和本文設計的基于DFS 的改進算法采用相同的時域信道劃分結構和相同的DTQ 排隊規則，而CRQ 排隊規則有所差別。因此，本文基于開源NS-3 離散事件仿真軟件，設計了的狀態機和事件類型，DQ 仿真的狀態遷移與事件如圖5 所示。

圖5 DQ 仿真的狀態遷移與事件

圖5 中的仿真對象類DqChannel 按固定的定時事件分別調用協調者和終端網絡接口的接口函數，完成信標幀的收發、CS 爭用與監聽和反饋幀Fbp的收發。

協調者和終端網絡接口派生于對象類ns3::NetDevice，DqChannel 派生于ns3::Channel。終端在爭用接入（CsAcc）狀態隨機選占一個小時隙（SelectMs），協調者統計爭用請求（RxCres）并在狀態FsBcast 發送反饋幀（TxFbp）。所有終端數據發送完成后，協調者再次發送信標，以支持連續多次仿真。

終端網絡接口在每個BCN 周期內發出一次數據幀，在狀態FsListen 收到反饋幀后，依據DQ 規則進行CRQ排隊（CrqWait）或DTQ排隊（DtqWait）。終端屬性p和q分別記錄終端在DTQ 和CRQ 中的位置，并利用NS3 的變量跟蹤機制提供監測和統計。當p=0 時，終端遷移至數據發送狀態DsTx，在緊隨其后的DQ 周期的DS 發送數據TxData，然后進入狀態BcnListen 等待下一輪仿真。

針對DQ 調度性能的仿真，圖5 設計的簡化模型假設所有數據長度固定不變，時長均為TDS。而共享時域信道的劃分由DqChannel 相應屬性提供配置接口。本文仿真實驗設置TDS=0.3 s，TBCN=TFS=0.1 s，TIFS=2 ms，TM=0.01 s，相應地，TF=0.4 s，α=40。

5.2 爭用時隙優化條件

圖6 和圖7 分別給出了BFS 和DFS 中CRQ 和DTQ 排隊長度隨時間變化趨勢。

圖6 描述了BFS 解決信道爭用的排隊長度變化。初始時刻（T=0），并發終端數K0=1 000，DTQ長度LT=0，CRQ 長度LC=1。

圖6 BFS 中DTQ 和CRQ 排隊長度隨時間變化趨勢

從圖6(a)的LT曲線可以看出，LT隨時間增加先增大，達到最大值后線性遞減至0。m=2 時，210 s左右LT達到最大值，650 s 左右LT減小至0。m=20時，LT達到最大值和0 值的時間分別約為210 s 和600 s，LT達到最大值時間對應于LC=0。這是因為，CRQ 內退避終端清零時，后繼沒有入隊而只有出隊的DTQ 只會隨時間遞減。

從圖6(b)的LC曲線可以看出，隨著時間增加，LC先增大，達到最大值后再逐漸減小到0。m值越大，最大值和0 值出現時間越小。m=2 時，250 s 左右LC達到最大值，650 s 左右LC減小至0。m=20 時，LC達到最大值和0 的時間分別約為30 s 和210 s。

從圖6 可見，當m=4、5、6 時，LT=0 的時間最小，即K0個終端全部完成數據發送的時間最少。根據式(15)，吞吐量最大的理論條件是mBFS_MAX≈6，這與仿真結果是吻合的。

圖7 描述了相同初始條件下DFS解決信道爭用的排隊長度變化，其中LT的變化趨勢與圖6 相似，但LC的變化幅度比圖6 小一個數量級。因曲線重疊，圖7(b)分別給出了m=2、3、20 的LC時變曲線。同樣的規律是，當LC=0 時，LT達到最大；當LT=0時，K0個終端全部完成數據發送。

圖7 DSF 中DTQ 和CRQ 排隊長度隨時間變化趨勢

從圖7 可以看出，m=3 的DTQ 排隊長度LT最先減少至0，這與式(17)的估算結果吻合。

文獻[2]在忽略CRQ 與DTQ 的相互耦合的情況下，為傳統DQ 給出的樂觀估計是，吞吐量最大條件是小時隙配置m=3。依據仿真實驗，傳統DQ 最佳條件應為m=4，基于DFS 的改進算法的最佳條件為m=3。這是因為，DFS 能更快地搜索到退避樹葉子節點，為沖突解決提供同時進行數據傳輸的機會，減少DS 空轉概率。

5.3 吞吐性能對比

本節以小時隙最佳配置為條件，對DQ 吞吐性能隨并發終端數的情況進行隨機實驗，統計結果如圖8 所示。

圖8 歸一化吞吐量隨并發終端數的變化

圖8 所示的仿真中，DFS 中設置m=3，BFS 中設置m=4。仿真總時長設為8×105s，針對K0=16 384，得到10 組BCN 周期；針對K0=16，得到9 000 組以上BCN 周期。歸一化吞吐量為，其中Ttot為所有BCN 周期完成的仿真時間。

當K0=16 384 時，DFS 和BFS 仿真中的Ttot平均值分別為7 085.291 s 和7 537 s。對應ALOHA，按G=K0(Ttot/TDS)?1計算歸一化負載分別為0.96 和0.69。依文獻[10]，可得歸一化吞吐量分別為0.141和0.173，均小于理論上的最大值0.184。

從圖8 可見，DQ 的歸一化吞吐量大于0.55，重負載時超過0.65，反映出遠好于ALOHA 的穩定性。當并發終端數K0＞64 時，相比于DQ 原有算法，改進算法的吞吐量有最大6%的提升，接近信道物理容量的70%。表1 給出了BFS 和DFS 算法下所有終端完成數據發送的總時長及加速因子計算結果。

表1 BFS 和DFS 算法下所有終端完成數據發送的總時長及加速因子計算結果

6 結束語

分布式排隊綜合了ALOHA 隨機多址和時分復用的技術手段，通過樹型退避方法壓縮多終端接入的連續沖突概率，使共享信道的有效利用率得到大幅提高。共享信道的爭用時隙配置與優化是DQ 技術的應用關鍵。本文分析了DQ 工作機制，針對爭用請求隊列采用的寬度優先遍歷樹，設計了基于深度優先的改進算法，并給出了理論和仿真的分析結果，證明了改進算法可以進一步提高吞吐性能。此外，本文采用了隨機樹分析法估算出DQ 爭用時隙數的最佳配置條件，并通過仿真實驗進行了驗證。本文預設DQ 系統具有理想的定時同步性能，這在實際應用中，特別是應用于因休眠節能而不能持久同步的物聯網時，是值得進一步深入探索的問題。