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

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

1 引言

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

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

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

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

DQ 調(diào)度的重載性能穩(wěn)定，功能相對簡單，對以ALOHA 技術(shù)為基礎(chǔ)的物聯(lián)網(wǎng)接入等新型業(yè)務(wù)有很大的應(yīng)用潛力[9]，因此受到研究者的關(guān)注。本文分析DQ 退避樹遍歷的計算優(yōu)化，以進一步提高沖突解決時效性，研究用深度優(yōu)先方法代替?zhèn)鹘y(tǒng)的廣度優(yōu)先方法。

2 DQ 工作機制

2.1 系統(tǒng)組成與時序

ALOHA 完全由數(shù)據(jù)站組成[10]，而DQ 系統(tǒng)則引入一個集中式協(xié)調(diào)者站點。為敘述方便，以下假設(shè)協(xié)調(diào)者功能部署在小區(qū)中心基站或AP，數(shù)據(jù)站為小區(qū)終端，DQ 的調(diào)度對象是并發(fā)終端至基站上行的數(shù)據(jù)傳輸。

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

圖1 DQ 時域共享信道的時隙劃分結(jié)構(gòu)

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

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

靜態(tài)系統(tǒng)配置固定的子時隙數(shù)m，以及固定時長的MS、CS、DS 和FS。

2.2 分布式排隊過程

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

協(xié)調(diào)者監(jiān)聽CS 內(nèi)所有MS。當僅有一個終端占用MS 時，由于可以正確恢復(fù)出請求信息，因此易被判定為爭用成功；當2 個及2 個以上終端占用MS 時，由于存在互干擾，因此易被判定為爭用失?。划敍]有終端占用MS 時，因無載波信號而易被判定為空閑。

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

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

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

協(xié)調(diào)者在監(jiān)聽MS 狀態(tài)的同時，同理計算G和C，并分別累加到由其集中維護的DTQ 長度LT和CRQ 長度LC。

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

其中，LT由協(xié)調(diào)者統(tǒng)計和廣播通告，其隨G遞增、隨DQ 周期遞減；gk是對ai的統(tǒng)計結(jié)果；pk隨DQ周期遞減。

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

其中，LC由協(xié)調(diào)者按DTQ 相同的方法計算和通告，ck是對ai的統(tǒng)計結(jié)果，qk隨DQ 周期遞減。

式(1)～式(3)的計算依賴于協(xié)調(diào)者在FS 的廣播反饋，F(xiàn)S 和m個MS 的總時長是分布式排隊的系統(tǒng)開銷。

2.3 沖突解決過程

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

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

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

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

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

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

3 改進算法

3.1 樹遍歷的優(yōu)化機會

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

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

圖3 DFS 遍歷沖突解決葉子節(jié)點示例

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

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

3.2 算法設(shè)計

改進算法沿用與BFS 相同的MS 監(jiān)聽和DTQ調(diào)度規(guī)則。協(xié)調(diào)者在得到MS 狀態(tài)后，同樣將LT、LC和MS 的狀態(tài)反饋給所有終端，同時進行隊列長度更新。

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

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

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

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

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

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

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

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

4 吞吐性能對比分析

4.1 吞吐量最大條件

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

其中，u表示有數(shù)據(jù)傳輸?shù)腄S 總數(shù)，v表示無數(shù)據(jù)傳輸?shù)腄S 總數(shù)。

設(shè)一個BCN 周期正好容納所有終端的數(shù)據(jù)發(fā)送，則u=K0，N=u+v。

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

4.2 完全樹的對比分析

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

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

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

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

圖4(b)樹根至最左側(cè)葉子節(jié)點，深度為4，其中DS 無數(shù)據(jù)發(fā)送，所以v=4。該樹的后繼遍歷中，所至中間節(jié)點均有對應(yīng)的葉子節(jié)點，如圖4(b)中序號為1～16 的節(jié)點所示，它們對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)，左側(cè)總是大于0，所以吞吐量最大條件是mDFS_MAX=2，有

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

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

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

4.3 一般隨機樹的對比分析

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

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

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

5 數(shù)值仿真驗證

5.1 仿真軟件設(shè)計

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

圖5 DQ 仿真的狀態(tài)遷移與事件

圖5 中的仿真對象類DqChannel 按固定的定時事件分別調(diào)用協(xié)調(diào)者和終端網(wǎng)絡(luò)接口的接口函數(shù)，完成信標幀的收發(fā)、CS 爭用與監(jiān)聽和反饋幀F(xiàn)bp的收發(fā)。

協(xié)調(diào)者和終端網(wǎng)絡(luò)接口派生于對象類ns3::NetDevice，DqChannel 派生于ns3::Channel。終端在爭用接入（CsAcc）狀態(tài)隨機選占一個小時隙（SelectMs），協(xié)調(diào)者統(tǒng)計爭用請求（RxCres）并在狀態(tài)FsBcast 發(fā)送反饋幀（TxFbp）。所有終端數(shù)據(jù)發(fā)送完成后，協(xié)調(diào)者再次發(fā)送信標，以支持連續(xù)多次仿真。

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

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

5.2 爭用時隙優(yōu)化條件

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

圖6 描述了BFS 解決信道爭用的排隊長度變化。初始時刻（T=0），并發(fā)終端數(shù)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達到最大值時間對應(yīng)于LC=0。這是因為，CRQ 內(nèi)退避終端清零時，后繼沒有入隊而只有出隊的DTQ 只會隨時間遞減。

從圖6(b)的LC曲線可以看出，隨著時間增加，LC先增大，達到最大值后再逐漸減小到0。m值越大，最大值和0 值出現(xiàn)時間越小。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個終端全部完成數(shù)據(jù)發(fā)送的時間最少。根據(jù)式(15)，吞吐量最大的理論條件是mBFS_MAX≈6，這與仿真結(jié)果是吻合的。

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

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

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

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

5.3 吞吐性能對比

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

圖8 歸一化吞吐量隨并發(fā)終端數(shù)的變化

圖8 所示的仿真中，DFS 中設(shè)置m=3，BFS 中設(shè)置m=4。仿真總時長設(shè)為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。對應(yīng)ALOHA，按G=K0(Ttot/TDS)?1計算歸一化負載分別為0.96 和0.69。依文獻[10]，可得歸一化吞吐量分別為0.141和0.173，均小于理論上的最大值0.184。

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

表1 BFS 和DFS 算法下所有終端完成數(shù)據(jù)發(fā)送的總時長及加速因子計算結(jié)果

6 結(jié)束語

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