王文鼐，萬洺瑜，王 斌，吳 煒

(1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003 2.南京郵電大學(xué) 寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點實驗室，江蘇 南京 210003 3.南京郵電大學(xué) 海外教育學(xué)院，江蘇 南京 210023)

共享信道的隨機多址接入（Random Multiple Access，RMA）源自20世紀(jì)60年代的Aloha技術(shù)，目標(biāo)是為一組并發(fā)的無線通信終端提供一種簡單而有效的傳輸控制方法［1］。經(jīng)過約60年的發(fā)展和演進(jìn)，延伸出諸多RMA方法，主要類型有時隙Aloha（Slotted Aloha，SA）［2］、載波偵聽多址（Carrier Sense MA，CSMA）［3］和樹形算法［4］。前3類應(yīng)用十分廣泛，包括3GPP-LTE、LoRaWAN、IEEE 802.3、IEEE 802.11和IEEE 802.15等技術(shù)標(biāo)準(zhǔn)或規(guī)范，而樹形算法僅在已撤消的IEEE 802.14規(guī)范中得到過試用［5］。

1990年，Xu［6］提出了分布式排隊（Distributed Queuing，DQ）方法，采用了與樹形算法相似的調(diào)度手段，但也一直未得到應(yīng)有關(guān)注。近年來，Laya等［7］在研究海量機器類通信（massive Machine Type Communications，mMTC）時發(fā)現(xiàn)，DQ有望成為Aloha的一種終結(jié)技術(shù)。

DQ將時域信道劃分為有沖突的爭用時隙（Contention Slot，CS）和無沖突的數(shù)據(jù)時隙（Data Slot，DS），引入集中式協(xié)調(diào)站和兩個分布式虛擬隊列管控CS和DS的占用［6］，解決隊列（Resolution Queue，RQ）調(diào)度CS的爭用，傳輸隊列（Transmission Queuing，TQ）以無沖突方式分配DS。

通常，CS嵌套m（m＞2）個子時隙（mini slot，mslot），功能等價于多信道SA。相應(yīng)地，RQ可用多服務(wù)員損失返回排隊機來刻畫，且m≥3時，總是先于TQ完成服務(wù)［8］。所以，DQ系統(tǒng)性能主要取決于TQ，近似G/D/1排隊機，重負(fù)載時不會出現(xiàn)Aloha的失穩(wěn)現(xiàn)象，輕負(fù)載時可以避免CSMA低效退避。更為突出的是DQ功能復(fù)雜度低于CSMA，節(jié)能機會多于CSMA，尤其適用于低功耗、高密度的低速物聯(lián)網(wǎng)［9-10］。本文綜合論述DQ機制及性能分析方法，討論DQ技術(shù)實現(xiàn)關(guān)鍵。

1 技術(shù)演進(jìn)與分類

1.1 Aloha方法及性能

Abramson［1］針對夏威夷大學(xué)分布在不同島嶼分校區(qū)的終端接入中心校區(qū)的無線通信，考慮到終端訪問的突發(fā)性和并發(fā)沖突，引入等待確認(rèn)、超時退避重傳的控制方法，并以夏威夷州的別名來命名，也稱純Aloha（Pure Aloha，PA）。

PA終端可以隨時占用共享信道發(fā)送分組。沖突情況有二類，一是當(dāng)前終端占用之前已有終端在持續(xù)占用，二是當(dāng)前終端占用過程中有新終端開始占用。為方便理論分析，假設(shè)所有終端占用信道的時長相同，記為T。則時域重疊的前后二次占用，即沖突時長，亦稱易損期，其最大值為2T。再設(shè)終端占用的具體時間是完全隨機的，在觀察時長τ內(nèi)的并發(fā)分組數(shù)為n，其概率為泊松分布

其中，exp（·）是以自然常數(shù)e為底的指數(shù)函數(shù)；參數(shù)g=（n/τ）｜τ→∞對平穩(wěn)系統(tǒng)而言為有限值，亦稱流入負(fù)載。

易損期（τ=2T）內(nèi)，如果沒有其他分組發(fā)送，則當(dāng)前分組可以無沖突地成功傳輸。因此，吞吐量，即單位時間內(nèi)系統(tǒng)成功傳輸?shù)姆纸M數(shù)可以表示為

定義G=gT，S=sT，代入式（2），得到歸一化的吞吐率

對式（3）微分并令其為0，可得，當(dāng)Gmax=0.5時，Smax=1/（2e）≈0.184，這是PA的基本特性。由式（3）可知，G＞Gmax時，S快速減至0。沖突終端退避返回時，G以正反饋方式增大，系統(tǒng)進(jìn)入不穩(wěn)定狀態(tài)，這是PA的最大問題。

在PA基礎(chǔ)上引入定時同步，按終端占用時長T將信道劃分為周期性時隙，分組發(fā)送被限制在時隙起始之時，為SA［2］。顯然，SA易損期縮至T。易得，S=Gexp（-G），且Gmax=1，Smax=1/e≈0.368。這是SA的基本特征，吞吐率是PA的2倍，但與PA一樣，重負(fù)載時易失穩(wěn)。

SA的控制開銷是所有通信終端要同步到共同的定時參考。當(dāng)同步偏差達(dá)到T/2時，SA會退化到與PA相同的等級［11］。

1.2 CSMA方法

1973年，Metcalfe受Aloha啟發(fā)，設(shè)計出針對廣播型同軸電纜的媒質(zhì)訪問控制方法，名為帶沖突檢測的CSMA（CSMA with Collision Detection，CSMA/CD）。CSMA是一種高效RMA，是IEEE 802.3以太網(wǎng)的技術(shù)基礎(chǔ)，并在20世紀(jì)90年代被擴(kuò)展用于IEEE 802.11，取名為帶沖突避免的CSMA（CSMA with Collision Avoidance，CSMA/CA）。

與PA/SA不同的是，CSMA有一個重要的先決條件：如果信道正處于占用，新發(fā)終端須推遲至信道空閑為止。早期以太網(wǎng)中，信道空閑的判定條件是，在名為沖突窗口（Collision Window，CW）時長內(nèi)，新發(fā)終端未偵聽到載波信號。CW取決于空間上相距最遠(yuǎn)終端的信號傳播時延，標(biāo)準(zhǔn)規(guī)定為51.2μs。CW是CSMA的易損期［3］，其與終端占用時長T之比，記為a。

易損期內(nèi)，無其他終端占用則無沖突發(fā)生，按式（1）可得相應(yīng)概率

其中，G為歸一化負(fù)載。

當(dāng)前終端占用后的y≤a時長內(nèi)，如有其他終端占用則發(fā)生沖突。沖突持續(xù)時長B=1+y+a，其中，附加a對應(yīng)于沖突后的空閑判定條件。按照式（1），隨機變量y的分布概率為

其中，E［y］表示隨機變量y的統(tǒng)計平均值。在計算吞吐率時還需考慮信道空閑時長，即

因此，CSMA吞吐率為

當(dāng)a→0，或CW遠(yuǎn)小于終端占用時長時，S=G/（1+G），并且當(dāng)G?1時，S接近100%的物理信道容量。但當(dāng)a≥0.4時，Gmax≤1，Smax≤0.3，并有與PA/SA類似的重負(fù)載失穩(wěn)現(xiàn)象［12-13］。

早期10 Mbit/s以太網(wǎng)CW為51.2μs，對應(yīng)于64 Byte分組發(fā)送時長。按以太網(wǎng)最長幀1 520 Byte計，a≈0.04，Smax≈0.7，這是CSMA的典型特征，具有遠(yuǎn)高于PA/SA的吞吐性能。

1.3 Aloha技術(shù)應(yīng)用

以時分多址接入（Time Division MA，TDMA）、頻分多址接入（Frequency Division MA，F(xiàn)DMA）和CDMA（Code Division MA）為代表的多址接入，由小區(qū)中心站分配業(yè)務(wù)數(shù)據(jù)的傳輸信道，避免沖突。但分配本身是基于Aloha的。以窄帶物聯(lián)網(wǎng)（Narrow Band-IoT，NB-IoT）上行分配為例，其典型連接過程如圖1所示［14］。

圖1中，終端（UE）通過名為NPRACH的共享信道發(fā)出接入請求，小區(qū)中心（eNB）為UE分配名為NPUSCH的上行信道，分配信息由名為NPDSCH的下行信道進(jìn)行傳輸。后繼的連接控制和數(shù)據(jù)傳輸，因不同UE占用相互正交的信道，是無沖突的過程。但是，NPRACH的共享接入采用多信道Aloha，重負(fù)載的沖突和穩(wěn)定性仍是亟待解決的問題［15］。

以LoRaWAN為代表的非授權(quán)頻段低功耗廣域網(wǎng)（Low Power Wide Area Network，LPWAN），出于功能簡單性要求，大多基于PA技術(shù)［7］。針對可能存在重負(fù)載不穩(wěn)定情況，LoRaWAN通過占空比參數(shù)限制并發(fā)數(shù)。文獻(xiàn)［16］提出一種SA方案，其預(yù)期與SA一致，但同樣存在失穩(wěn)問題。

1.4 終端分組接入方法

IEEE 802.11ah制定了一種將終端集合進(jìn)行分組的RMA方法，名為受限接入窗［17］（Restricted Access Window，RAW）。終端接入的典型時序如圖2所示。

圖2中，終端STA1和STAn被接入點AP分配到組0的slot0和slot1，STA2被分配到組m-1的slot0。這些分配由AP決策并隨BCN廣播通告。STA1在（組0，slot0）啟用CSMA/CA爭占信道，STAn在（組0，slot1）嘗試占用。終端分組、組內(nèi)slot數(shù)量和BCN周期內(nèi)的RAW組數(shù)，可按負(fù)載大小動態(tài)調(diào)整。

RAW減小了組內(nèi)并發(fā)終端數(shù)和沖突概率，能提高系統(tǒng)吞吐性能［16］。RAW的優(yōu)勢還在于，BCN給出的終端分配信息，有可預(yù)測的工作時段和休眠機會，簡化的終端功能可滿足低復(fù)雜度需求。

Kawamoto等［18］針對衛(wèi)星收集地面?zhèn)鞲衅鲾?shù)據(jù)的系統(tǒng)，設(shè)計了名為分治的征詢與分配算法，該算法基于二分樹對終端進(jìn)行預(yù)分組，具體機制如圖3所示。

圖3（a）中，實心圈表示并發(fā)終端，空心圈表示空閑終端。示例針對32個終端，按樹劃分成組Gi，j，其中，i為樹的層次，j為組序號。例如，最小組G3，j包括4個終端。衛(wèi)星S依樹層次i遍歷，向組內(nèi)終端Ts廣播詢問，新發(fā)終端做出響應(yīng)。分治步驟為：

（1）如果僅有一個新發(fā)終端，則為其分配傳輸時隙，如圖3（b）的7，10和29的標(biāo)示；

（2）如果有多個新發(fā)終端，如圖3（b）符號“X”的標(biāo)示，則分枝迭代處理；

（3）如果迭代至樹葉組仍有沖突，如圖3（b）的G3，3和G3，6的標(biāo)示，則為該組滿配4個時隙；

（4）如果新發(fā)終端，如圖3（b）符號“E”的標(biāo)示，則退加分枝上層。

以上終端搜索得到的次序，對應(yīng)于信道占用序號。從圖3可知，當(dāng)并發(fā)終端較少時，分治搜索有較好的信道利用效率。而并發(fā)終端數(shù)較大時，沖突解決的開銷較重，信道利用效率很難得到提高。以下討論樹形算法，其性能要遠(yuǎn)好于上述RAW和分治算法。

1.5 樹形二分算法

RMA的樹形算法：假設(shè)并發(fā)終端的沖突訪問可得到即時反饋，以遞歸迭代方式將沖突終端集合進(jìn)行二分。算法的作用是減少退避后的并發(fā)量，直至單終端爭用為止，如圖4所示［4］。

圖4中圓圈表示終端，其中數(shù)值表示終端編號。樹根T00包含所有4個并發(fā)終端隨機分配到時隙S00的2個子時隙。占用子時隙的終端，如有沖突則劃分到子樹，如圖4（a）的T10和T11所示。后繼按深度優(yōu)先，先遍歷T10子樹，再遍歷T11子樹。遍歷的回溯條件是，2個子時隙均無沖突發(fā)生。

顯然，以時隙為單位，所有終端完成無沖突占用的時長為

其中，K=KL+KR是當(dāng)前樹節(jié)點的終端數(shù)，KL和KR分別為左子樹和右子樹的終端數(shù)；LK是與K有關(guān)的隨機變量，并有L0=L1=1。

針對負(fù)載為G的泊松到達(dá)過程，按照式（1），系統(tǒng)平穩(wěn)的條件是，在LK時長內(nèi)到達(dá)的終端數(shù)G·E［LK］小于系統(tǒng)服務(wù)的終端數(shù)E［K］，即

其中，K的概率P（K）=GKexp｛-G｝/K！，并且

分析發(fā)現(xiàn)［19］，當(dāng)K＞13時，有近似關(guān)系LK=αK，其中，α=1.878 4。所以，式（10）可以轉(zhuǎn)化為

計算可得，式（12）右側(cè)為0.429 5≈0.430。該值是樹形算法的最大吞吐率，所以得名“0.430算法”。

基于二分法沖突解決的樹形算法，其吞吐率優(yōu)于PA的0.184和SA的0.368，并有進(jìn)一步優(yōu)化提升的空間。但該算法本身忽略了沖突檢測和反饋的開銷。對近距離的射頻標(biāo)簽（RFID）應(yīng)用，可在時隙結(jié)束時安排短時長反饋信號。但對于在一定空間范圍內(nèi)分布的通信終端，引入DQ成為必然。

2 分布式排隊機制

2.1 時隙結(jié)構(gòu)及功能

DQ系統(tǒng)由共享同一時域信道的協(xié)調(diào)站和多個終端組成，協(xié)調(diào)站與終端的信號相互可達(dá)，如圖5所示。出于敘述方便，以下使用與文獻(xiàn)［7］略有不同的命名。

圖5左側(cè)表示時隙結(jié)構(gòu)，協(xié)調(diào)站通過BCN廣播提供定時參考，啟動一組周期性DQ超幀（0～N-1）。每個超幀包含CS和DS兩個上行時隙，以及一個下行的FS（Feed-back Slot）時隙。DS與FS之間的保護(hù)時隙，用于容納上下行傳播延時、定時偏差和避免收發(fā)干擾。CS由m個mslot組成，終端隨機選取其中一個發(fā)送請求。

協(xié)調(diào)站只偵聽mslot的爭用狀態(tài)，并在反饋時隙（FS）廣播通告。協(xié)調(diào)站不處理請求，不涉及信道分配，也不收發(fā)信息數(shù)據(jù)，其功能復(fù)雜度遠(yuǎn)低于傳統(tǒng)小區(qū)基站或AP。在小區(qū)制結(jié)構(gòu)中，協(xié)調(diào)站既可部署在基站內(nèi)，也可獨立設(shè)置。在無中心結(jié)構(gòu)的Ad-hoc網(wǎng)絡(luò)中，協(xié)調(diào)站可選取普通終端臨時擔(dān)當(dāng)［20］。

終端是數(shù)據(jù)的源宿站點，也可以是數(shù)據(jù)轉(zhuǎn)發(fā)的中間站點，比如AP。終端在固定分配的CS發(fā)出占用請求，接收并記錄協(xié)調(diào)站的反饋信息，判定爭用成功時按序排隊占用DS以發(fā)送分組，判定失敗時退避重試。終端的退避重試是DQ的技術(shù)關(guān)鍵，功能集中在沖突解決隊列RQ。

與傳統(tǒng)CSMA相比，終端功能的復(fù)雜度得到大幅度降低；與PA相比，終端需要具備定時同步功能；與SA相比，終端要增加爭用信號發(fā)送和爭用狀態(tài)的接收與判定。總體上，DQ終端的實現(xiàn)復(fù)雜度與SA相當(dāng)。

2.2 沖突退避排隊

DQ協(xié)調(diào)站在FS廣播反饋信息，包括每個mslot的爭用狀態(tài)。不失一般性，設(shè)第n超幀的mslot狀態(tài)為sn（i），i∈［0，m-1］，sn（i）=1表示無沖突，sn（i）=2表示有沖突，sn（i）=0表示空閑。依據(jù)sn（i），各終端計算得到

分別為有沖突mslot的累計數(shù)和無沖突mslot的累計數(shù)。初始時，R（0）=T（0）=0，且保持為非負(fù)。

設(shè)終端在第n超幀所選mslot的序號為j，如果sn（j）=1，則其等待發(fā)送分組的超幀序號為

如果sn（j）=2，則終端退避重試，需要等待的超幀數(shù)為

以上計算由分布的終端獨立進(jìn)行。計數(shù)P和Q隨超幀序號的增加而遞減。當(dāng)P=0時，只會有一個終端占用DS發(fā)送數(shù)據(jù)，形式上構(gòu)成一個虛擬的先進(jìn)先出排隊，即TQ。

同理，當(dāng)Q=0時，有一組終端再次發(fā)出爭用請求，重復(fù)以上過程，形式上構(gòu)成一個多服務(wù)員排隊系統(tǒng)，即RQ。RQ的服務(wù)規(guī)則是，爭用成功者離開RQ進(jìn)入TQ隊尾，沖突失敗者返回RQ隊尾。RQ服務(wù)員數(shù)目是m，即CS中mslot的配置數(shù)。參數(shù)R/T為RQ/TQ隊列長度，P/Q為終端在RQ/TQ的位置。

2.3 樹形分組退避過程

當(dāng)m=3、初始有K=5個終端并發(fā)接入時，RQ和TQ計算過程如圖6所示。

圖6中CS配置3個mslot，用方框表示?？蛑袛?shù)值為爭占終端數(shù)量，粗邊表示沖突失敗，細(xì)邊表示爭占成功，虛邊表示空閑。

在第（0）超幀，3個mslot各有3、0、2個終端選中，所以R=2，T=0。在第（1）超幀，RQ隊首3個終端爭用，3個mslot各有0、1、2個終端選中，結(jié)果是R=2，T=1。如此至第（5）超幀，R=0，T=2，后續(xù)過程從略。

從圖6可見，RQ沖突解決過程實質(zhì)是一種樹形退避計算。對于m=3的情況得到隨機三叉樹，樹深度log3（K）對應(yīng)于沖突解決時長。

3 性能分析

3.1 排隊模型

文獻(xiàn)［8］將N個DQ超幀構(gòu)成的BCN周期記為ETI（Enable Transmission Time Interval），期內(nèi)其后到達(dá)的終端需要等待下一個ETI。所以，完整的DQ系統(tǒng)包含3個串聯(lián)的排隊機，如圖7所示。

在ETI累計到達(dá)的K個終端進(jìn)入RQ。如圖7所示中間過程，RQ有R個終端，隊首3個終端其Q=0，其中2個因沖突而返回到RQ隊尾（實心圓表示），相應(yīng)的Q=R；空心圓表示的終端因無沖突而進(jìn)入TQ隊尾，相應(yīng)的P=T。

在一個DQ超幀內(nèi)，RQ和TQ各調(diào)度一次。RQ調(diào)度一次，就是一組終端爭用的一次解決過程。K個終端全部完成爭用解決的次數(shù)LK，既是ETI和BCN周期設(shè)置的參考條件，也是ETI排隊等待時長的計算依據(jù)。

3.2 沖突解決時長

顯然，如果進(jìn)入RQ的終端數(shù)為0或1，因無沖突發(fā)生，所以

其中，沖突時長以DQ超幀為單位。

如果并發(fā)終端數(shù)為2，同時選中第i個mslot的概率為1/m2，0≤i≤m-1。選中相同mslot時，這2個終端需要再經(jīng)過一次RQ調(diào)度重新爭用。所以

如果終端數(shù)為K，經(jīng)m個mslot分組后得到k（i）個并發(fā)爭用終端，分別在后繼第i個DQ超幀內(nèi)調(diào)度，所以

其中，k（i）=0/1，因mslot無沖突而無需計入，m個k（i）為獨立隨機變量，二項式系數(shù)C（n，K）=K！/n?。↘-n）！，定義a=1/m。易得，K＞2時，LK的一般迭代式為

文獻(xiàn)［8］中表1計算出沖突解決次數(shù)平均值，發(fā)現(xiàn)K＞1且m≥3時，總有LK＜K，即RQ先于TQ清空。m≥3為DQ最佳工作條件。

3.3 穩(wěn)定性與吞吐率

從圖6描述可見，RQ沖突解決過程實質(zhì)是一種樹形算法［21］，沖突解決的穩(wěn)定條件為

其中，＜K＞為ETI內(nèi)新發(fā)終端，＜T＞為沖突解決的平均時長。以固定時長的DQ超幀為單位，有，概率分布P（ETI，K）采用式（1）表示，LK表示為式（21）。

式（22）得到的G與ETI是相關(guān)的，其最大值Gmax不僅是DQ穩(wěn)定調(diào)度的流入負(fù)載上限，也是系統(tǒng)最大吞吐量的工作條件。文獻(xiàn)［8］中表2給出了2≤m≤16時的Gmax和ETI的數(shù)值計算結(jié)果，繪制成圖如圖8所示。

從圖8的變化趨勢可見，當(dāng)m≥3時，RQ的歸一化吞吐量總是大于1；ETI（BCN周期包含DQ超幀數(shù)）設(shè)置在2～3是較佳條件。

結(jié)合圖7給出的排隊機串聯(lián)結(jié)構(gòu)，TQ的穩(wěn)定條件是歸一化流入負(fù)載小于1，所以DQ的總體吞吐性能接近G/D/1?？紤]mslot開銷，吞吐率為

其中，δ表示一個mslot與DQ超幀的時長比。以m=3，δ≤0.1為例，Smax≥0.77，其值遠(yuǎn)大于PA/SA，與a=0.04的CSMA可比。

4 應(yīng)用與擴(kuò)展方案

4.1 CDMA隨機接入信道

有線電視電纜是樹形算法及DQ的最初應(yīng)用對象［5-6］。文獻(xiàn)［22］將DQ擴(kuò)展到無線接入網(wǎng)，提出名為DQRUMA（DQ Request Update MA）控制方法。文獻(xiàn)［23］則為CDMA移動通信的隨機接入信道（RACH）設(shè)計了一種聯(lián)合擴(kuò)頻碼和時域mslot的DQRAP/CDMA，其接入時序如圖9所示。

圖9中，位于4終端中間的二維信道，縱向表示3個正交擴(kuò)頻碼C1～C3，橫向表示時域3個mslot和1個數(shù)據(jù)時隙。時隙內(nèi)數(shù)值表示終端編號，黑色填充的信道時隙表示沖突。

在n=1周期中，終端STA1、STA2、STA3均用C1編碼爭用3個mslot，同時在數(shù)據(jù)時隙均發(fā)送各自分組。STA2選占的第2個mslot無沖突，但數(shù)據(jù)時隙發(fā)生沖突，因此在n=2周期，STA2使用C1編碼重復(fù)發(fā)送分組。

n=1的mslot沖突狀態(tài)由協(xié)調(diào)站/基站采用帶外方式反饋給所有終端，所以在n=2時，STA4使用C2編碼爭占和傳輸，與STA1～STA3的C1編碼正交，因此STA4以無沖突方式完成分組傳輸。

在n=2周期中，STA1與STA3的沖突得到解決，所以在n=3時分別使用C1和C2編碼發(fā)送各自分組。而完成第1個分組傳輸后的STA2和STA4，開始第2個分組，分別對應(yīng)2’和4’，但使用了相同的C1編碼爭用mslot，相同的C3編碼占用數(shù)據(jù)時隙，產(chǎn)生沖突。

在n=4周期中，STA2和STA4繼續(xù)爭用了同一mslot。與此同時，STA1和STA3開始第2個分組的爭用和傳輸，也發(fā)生了沖突。所以，在n=5周期中，2對終端按RQ規(guī)則退避重試，但數(shù)據(jù)時隙空閑未用。后繼過程從略。

從操作流程可見，同樣是3個mslot，DQRAP/CDMA的沖突解決時效和吞吐性能都優(yōu)于經(jīng)典DQ，這是因為正交擴(kuò)頻碼提供了額外的信道容量。而數(shù)據(jù)時隙的占用無需等待沖突完全解決，這在輕負(fù)載時與SA接近，而隨負(fù)載增加又可平滑切換到DQ。由于標(biāo)準(zhǔn)規(guī)范的限制，DQRAP/CDMA未得到實際使用。

4.2 LTE隨機接入信道

與CDMA類同，LTE的RACH采用時頻聯(lián)合的資源分片方式，供終端發(fā)送接入請求。LTE支持2種接入方式：爭用方式和無沖突方式，爭用方式與圖1相似，終端通過RA前導(dǎo)（RA Preamble，RAP）編碼請求。

RAP包含多個RA時隙，小區(qū)基站（eNB）負(fù)責(zé)配置和廣播通告，提供最多64個正交序列。采用Aloha時，UE終端隨機選擇一個前導(dǎo)序列表示接入請求，eNB在下行信道反饋RA響應(yīng)（RA Response，RAR）［24］。

目前，研究人員已提出2種DQ結(jié)合LTE的方案，分別為DQAL（DQ Access Protocol）和DQRA（DQ-based RA）。相比而言，后者的復(fù)雜度較低且易于實現(xiàn)［25］，以下重點說明其工用機制［26］。

初始時，UE隨機選擇一個RA時隙，等該時隙空閑后發(fā)出RAP，然后接收RAR。如果爭用成功，UE解碼RAR并按eNB指示轉(zhuǎn)至無沖突的上行信道。如果反饋為空閑或沖突則返回RQ重試。DQRA的精巧設(shè)計主要體現(xiàn)在LTE-RAR消息結(jié)構(gòu)的擴(kuò)展，如圖10所示。

在3GPP中，RAR消息封裝在MAC幀凈荷部分，而MAC頭部可有一個或多個子頭，圖10（a）和圖10（b）分別給出2種類型子頭編碼格式，其中E比特置1表示有后繼子頭，置0表示為最后一個子頭。圖10（c）是擴(kuò)展的DQ爭用狀態(tài)子頭，P1～P6對應(yīng)6個RAP序列反饋。更多序列的情況可擴(kuò)展到多個子頭［27］。

RAR消息頭最多包含一個BI，表示DQ爭用狀態(tài)的類型可以結(jié)合E比特復(fù)用BI類型，對于UE可以容易區(qū)分。

圖10（c）的P1～P6比特表示6個DQ的mslot，其值為1，表示沖突；其值為0時，由RAPID表示成功、否則為空閑。如此，RAR可替代經(jīng)典DQ的FS功能。

文獻(xiàn)［26-27］利用擴(kuò)展的NS-3仿真了DQRA性能，發(fā)現(xiàn)RAP序列數(shù)在6～56配置下，UE數(shù)量在0～250范圍變化時，接入請求的阻塞率全部為0。而3GPP規(guī)范采用的Aloha方案，在RAP序列數(shù)為6～18時，其阻塞率可至0.3～0.4。另外，在接入延時、能耗和退避重占次數(shù)方面，DQRA均優(yōu)于Aloha。文獻(xiàn)［25］則對能耗以外的DQRA性能給出了理論證實。

4.3 WLAN沖突避免方案

IEEE802.11制定的分布式協(xié)調(diào)功能（Distributed Coordination Function，DCF），采用RTS/CTS握手避免數(shù)據(jù)傳輸沖突，形成CSMA/CA方法。DQRAP/CDMA方案的研究小組最早提出一種簡單設(shè)計、依RTS幀構(gòu)造DQ的mslot，重構(gòu)CTS充當(dāng)FS反饋，稱為DQCA［27］。

圖11描述了DQCA的幀結(jié)構(gòu)，包含m=3個RTS表示的mslot，源端占用數(shù)據(jù)幀，接收到無沖突數(shù)據(jù)的收端發(fā)送ACK，DQ協(xié)調(diào)站反饋CTS。

圖11中RTS和數(shù)據(jù)幀的信號傳輸方向一致，所以不設(shè)幀間間隙，但與反向ACK與CTS幀之間配置WLAN的最小幀間間隙（Short Inter-Frame Spacing，SIFS）。

DQCA的操作流程基本延用了經(jīng)典DQ方法，其吞吐性能很容易計算。文獻(xiàn)［28］針對可變速率應(yīng)用環(huán)境，考慮2個和20個終端在空間的隨機分布，以及100～2 312 Bytes長分組的持續(xù)爭用，仿真結(jié)果顯示，相對于CSMA/CA，DQCA有最小25%的吞吐量提升。

提出DQCA的研究人員進(jìn)一步對DQCA幀結(jié)構(gòu)進(jìn)行了細(xì)化設(shè)計，以便納入QoS功能［29］。但是，DQCA與WLAN標(biāo)準(zhǔn)的兼容性較低，未得到更多發(fā)展。

4.4 LPWAN擴(kuò)展方案

非授權(quán)頻段LPWAN以能耗敏感的物聯(lián)網(wǎng)應(yīng)用為導(dǎo)向，在快速發(fā)展的同時暴露出規(guī)模化接入的性能瓶頸，引入DQ正當(dāng)其時。文獻(xiàn)［30］基于IEEE 802.15.4的硬件成品，設(shè)計實現(xiàn)了一種低功耗DQ（Low Power DQ，LPDQ）方案，并與主流基于幀的SA（Frame SA，F(xiàn)SA）進(jìn)行了對比實驗，發(fā)現(xiàn)LPDQ在提高信道有效利用率的同時，可獲得10%以上的節(jié)能效果，并有很大的優(yōu)化空間。

文獻(xiàn)［31］受LPDQ啟發(fā)，為LPWAN的眾包模式組網(wǎng)設(shè)計了名為DQ-N的MAC方案，其中字母N表示DQ超幀可包含多個數(shù)據(jù)時隙，以使終端獲得更多信道占用時長，縮小分組投送延時。圖12描述了DQ-N的時隙結(jié)構(gòu)。

圖12中，TR表示上行的發(fā)送請求，ID表示4 bit長的終端標(biāo)識符，MSF表示mslot狀態(tài)反饋，DSN表示計劃占用的DS數(shù)量，下行標(biāo)幟F指示網(wǎng)關(guān)是否有數(shù)據(jù)發(fā)送，RQ和TQ分別表示DQ的2個分布式隊列的長度。

與經(jīng)典DQ相比，DQ-N不僅允許可變的DS數(shù)量，還專門針對網(wǎng)關(guān)向終端發(fā)送的數(shù)據(jù)配置了優(yōu)先占用功能。DQ-N的作者進(jìn)一步以商用LoRa傳感開發(fā)板和Raspberry Pi3基站為基礎(chǔ)，開發(fā)了可行性驗證原型［9］。

從以上討論的應(yīng)用情況看，DQ有可期的RMA性能。在技術(shù)實現(xiàn)方面，受標(biāo)準(zhǔn)化限制，DQ未得到應(yīng)有的關(guān)注。隨著非授權(quán)和開源物聯(lián)網(wǎng)技術(shù)的發(fā)展，DQ技術(shù)表現(xiàn)出相當(dāng)?shù)母偁巸?yōu)勢。

5 DQ定時同步問題

DQ技術(shù)的前提條件是接入的定時同步。文獻(xiàn)［30］在對LPDQ協(xié)議進(jìn)行初步設(shè)計時，分析了低成本終端實時鐘性能，其定時脈沖頻率為32.768 kHz，周期為30.51μs。按每2 s執(zhí)行1次同步的要求，1 500 mAh電池供電終端，其同步待機壽命可達(dá)5年。在此條件下，終端同步的分辨精度為62μs，這是mslot的最小時長，對應(yīng)于250 kbit/s的數(shù)據(jù)速率，接近16 bit。

考慮小區(qū)制環(huán)境，設(shè)平面空間覆蓋距離為30 km，對應(yīng)信號傳播延時差約為150μs，同樣按250 kbit/s速率計，接近38 bit。合計得到一個mslot的最小開銷為54 bit。再按m=3的最佳DQ方案，爭用時隙開銷大于162 bit。這對于常規(guī)數(shù)據(jù)為數(shù)十字節(jié)的物聯(lián)網(wǎng)應(yīng)用而言，DQ預(yù)期效益將大打折扣。文獻(xiàn)［31］提出的DQ-N方案理論上可以改善信道利用效率，但前提是終端有較長的數(shù)據(jù)待發(fā)。

針對以上問題，一種可行的解決思路是引入多個分布式的協(xié)調(diào)站及協(xié)調(diào)區(qū)，縮小同步區(qū)以壓縮mslot開銷。當(dāng)然，多個協(xié)調(diào)站之間存在額外的計算處理開銷，需要通過精細(xì)的方案設(shè)計與理論分析，在性能與復(fù)雜度之間探索折中手段。

6 結(jié)束語

分布式排隊（DQ）技術(shù)具有相當(dāng)優(yōu)越的隨機多址接入性能，主要表現(xiàn)在吞吐性能接近于統(tǒng)計時分復(fù)用系統(tǒng)，穩(wěn)定性不受流入負(fù)載影響，可預(yù)測的終端接入時序提供了節(jié)能機會，操作功能相對簡單，特別適合于能耗敏感的物聯(lián)網(wǎng)應(yīng)用。本文綜合論述了DQ的典型工作機制和性能分析方法，以便為DQ技術(shù)應(yīng)用提供工程設(shè)計參考。DQ協(xié)調(diào)站扮演至關(guān)重要的作用，決定了定時同步精度和性能提升效益，是進(jìn)一步研究與開發(fā)的焦點之一。