分布式排隊(duì)中退避樹的深度優(yōu)先遍歷算法

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

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

1 引言

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

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

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

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

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

2 DQ 工作機(jī)制

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

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

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

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

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

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

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

2.2 分布式排隊(duì)過程

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

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

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

所有爭(zhēng)用終端在每個(gè)DQ 周期FS 接收來(lái)自協(xié)調(diào)者的ai反饋結(jié)果，獨(dú)立計(jì)算式(1)。

其中，G為爭(zhēng)用成功的終端個(gè)數(shù)，C為爭(zhēng)用失敗的終端組的個(gè)數(shù)，gk為終端k爭(zhēng)用成功時(shí)的次序號(hào)，ck為終端k爭(zhēng)用失敗時(shí)的次序號(hào)。當(dāng)ai=n時(shí)δ(ai,n)=1，否則δ(ai,n)=0。

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

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

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

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

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

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

2.3 沖突解決過程

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

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

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

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

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

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

3 改進(jìn)算法

3.1 樹遍歷的優(yōu)化機(jī)會(huì)

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

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

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

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

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

3.2 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

4 吞吐性能對(duì)比分析

4.1 吞吐量最大條件

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

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

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

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

4.2 完全樹的對(duì)比分析

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

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

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

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

圖4(b)樹根至最左側(cè)葉子節(jié)點(diǎn)，深度為4，其中DS 無(wú)數(shù)據(jù)發(fā)送，所以v=4。該樹的后繼遍歷中，所至中間節(jié)點(diǎn)均有對(duì)應(yīng)的葉子節(jié)點(diǎn)，如圖4(b)中序號(hào)為1～16 的節(jié)點(diǎn)所示，它們對(duì)v無(wú)貢獻(xiàn)。因此可得v=4。

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

對(duì)于DFS，從式(13)可知，因?yàn)閙＞1，所以dvDFS/dm＞0。代入式(8)，左側(cè)總是大于0，所以吞吐量最大條件是mDFS_MAX=2，有

因?yàn)镵0＞＞2，所以K0+lbK0?1≈K0。

定義加率比f(wàn)=SDFS_MAX/SBFS_MAX，則有

易得，當(dāng)α=4 時(shí)，有最大加速比f(wàn)=1.5。

4.3 一般隨機(jī)樹的對(duì)比分析

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

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

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

5 數(shù)值仿真驗(yàn)證

5.1 仿真軟件設(shè)計(jì)

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

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

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

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

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

針對(duì)DQ 調(diào)度性能的仿真，圖5 設(shè)計(jì)的簡(jiǎn)化模型假設(shè)所有數(shù)據(jù)長(zhǎng)度固定不變，時(shí)長(zhǎng)均為TDS。而共享時(shí)域信道的劃分由DqChannel 相應(yīng)屬性提供配置接口。本文仿真實(shí)驗(yàn)設(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 爭(zhēng)用時(shí)隙優(yōu)化條件

圖6 和圖7 分別給出了BFS 和DFS 中CRQ 和DTQ 排隊(duì)長(zhǎng)度隨時(shí)間變化趨勢(shì)。

圖6 描述了BFS 解決信道爭(zhēng)用的排隊(duì)長(zhǎng)度變化。初始時(shí)刻（T=0），并發(fā)終端數(shù)K0=1 000，DTQ長(zhǎng)度LT=0，CRQ 長(zhǎng)度LC=1。

圖6 BFS 中DTQ 和CRQ 排隊(duì)長(zhǎng)度隨時(shí)間變化趨勢(shì)

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

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

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

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

圖7 DSF 中DTQ 和CRQ 排隊(duì)長(zhǎng)度隨時(shí)間變化趨勢(shì)

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

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

5.3 吞吐性能對(duì)比

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

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

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

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

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

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

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

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