摘要：傳統(tǒng)的截斷二進(jìn)制指數(shù)后退沖突算法解決沖突問題時，每次都將初始窗口設(shè)為2個時隙，而不管可能存在的沖突端數(shù)。已有學(xué)者基于已知沖突端口數(shù)而提出了一種動態(tài)改進(jìn)算法，然而確定沖突端口數(shù)是很困難的。針對上述問題，本文提出了一種基于概率的動態(tài)設(shè)置初始窗口的改進(jìn)算法，仿真實(shí)臉表明該算法是能有效降低沖突分解次數(shù)和分解時隙。

關(guān)鍵詞：二進(jìn)制指數(shù)后退算法；動態(tài)沖突分解算法；時隙

中圖分類號：TN914.5 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599 （2012） 24-0123-02

1 引言

多址訪問（multi-access）技術(shù)是一種多用戶共享公共信道的接入控制協(xié)議，它主要遵循固定分配、按需分配和隨機(jī)爭用三種通信協(xié)議模型。其中隨機(jī)爭用模型在一定條件下作為有效利用信道資源、減小轉(zhuǎn)接時延的技術(shù)而被廣泛應(yīng)用[1，2]。而時隙ALOHA是其典型的隨機(jī)爭用系統(tǒng)模型。在時隙式ALOHA系統(tǒng)中，公共信道被離散為若干固定長度的時間片，稱為時隙（slot）。用戶終端在每個時隙的起始處開始發(fā)送數(shù)據(jù)包，且一個時隙內(nèi)僅可以傳輸一個數(shù)據(jù)包。如果在某個時隙兩個及兩個以上用戶同時申請發(fā)送信息時，沖突就產(chǎn)生了。卷入沖突的用戶終端需要按照一定的沖突分解規(guī)則在后續(xù)的時隙中重發(fā)信息，直到所有沖突用戶終端數(shù)據(jù)發(fā)送成功。

沖突分解規(guī)則[3]描述：若用 表示終端的退避延時值，則此規(guī)則可用公式（1）所描述：

（1）

公式（1）中，τ是與系統(tǒng)有關(guān)的時間常數(shù)，R是以其地址為初始值產(chǎn)生的一個隨機(jī)數(shù)。當(dāng)系統(tǒng)發(fā)生沖突時，發(fā)生沖突的終端必須在算法每次提供的時隙窗口范圍內(nèi)隨機(jī)地選擇一個值，這個隨機(jī)值就是該終端在重發(fā)信息前必須“放過”的時隙數(shù)。根據(jù)公式（1），文獻(xiàn)[4]提出了時隙窗口范圍計(jì)算公式，通過時隙窗口范圍計(jì)算公式，我們知道了基本算法的沖突分解過程。由于基本算法的每次沖突分解開始時的初始窗口數(shù)都為2，因此它延遲了沖突分解成功所需的時隙值。為了減少所需的時隙值，本文提出了一種新的沖突分解算法。

2 動態(tài)截斷二進(jìn)制指數(shù)后退沖突分解算法

由于基本算法沖突分解所需的時隙值較大，故為了提高系統(tǒng)的利用率，本文提出了一種動態(tài)的沖突分解算法，此算法與基本算法的主要區(qū)別在于改進(jìn)算法是根據(jù)預(yù)測沖突終端數(shù)動態(tài)地設(shè)置初始窗口數(shù)。而不像基本算法那樣，無論沖突終端數(shù)為多少，初始窗口數(shù)始終為2，其他分解過程改進(jìn)算法與基本算法基本一致。而改進(jìn)算法的初始窗口大小應(yīng)包括前面窗口的時隙值，則該算法的初始窗口數(shù)如公式（2，3，4）所示：

（2）

（3）

（4）

其中M為預(yù)測出的沖突終端數(shù)，k為在基本算法中需要的分解次數(shù)，Yk和Zk為在動態(tài)算法中M個沖突終端數(shù)下設(shè)定的初始窗口數(shù)，其中Y0=0，Z0=2046。

3 仿真分析

為了驗(yàn)證本文提出的動態(tài)設(shè)置初始窗口數(shù)的算法的有效性，我們進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)中基于兩個參數(shù)進(jìn)行，即沖突分解成功時的分解次數(shù)和沖突分解成功所需的時隙值。本實(shí)驗(yàn)結(jié)果為取10000次仿真的平均值。實(shí)驗(yàn)結(jié)果如表1所示：

表1 基本算法和改進(jìn)算法的仿真實(shí)驗(yàn)結(jié)果（單位：時隙）

在線終端數(shù)Np=0.005p=0.01

基本算法改進(jìn)算法基本算法改進(jìn)算法

countmaxslotcountmaxslotcountmaxslotcountmaxslot

303.6124.401.6118.404.0833.952.0827.95

505.0366.352.0352.356.09139.442.09109.44

706.15145.902.11115.907.15293.682.15231.68

907.11283.312.15221.317.53390.702.28328.70

1107.38351.282.38289.288.28655.412.40529.41

1307.73442.162.40380.168.59814.642.53688.64

1508.40715.312.67589.318.88967.222.59841.22

1708.67856.622.73730.629.401429.552.631175.55

1908.87957.492.87831.499.531664.052.881410.05

（下轉(zhuǎn)第149頁）