許 楠，郝學坤，許 眾

(1.中國電子科技集團公司第五十四研究所，河北石家莊 050081;2.沈陽理工大學，遼寧沈陽 110159)

0 引言

多頻時分多址(MF-TDMA)將頻率分割為多個子信道，在每路載波上劃分時隙，每個用戶在一定的頻率上占用指定的時隙。這種技術(shù)同時具有FDMA和TDMA 2種體制的優(yōu)點，擴展了網(wǎng)絡規(guī)模，能夠靈活分配信道的時隙資源，保證信道的利用率，因此廣泛應用于衛(wèi)星通信系統(tǒng)中。

MF-TDMA衛(wèi)星通信系統(tǒng)對信道時隙資源的分配采取申請/分配機制。各終端站根據(jù)其業(yè)務的特性與變化情況，周期性地向中心站發(fā)送時隙申請信息。中心站接收后，執(zhí)行時隙分配算法，從信道中搜索合適的時隙進行分配，形成時隙分配表，下發(fā)至每一個終端站。各站在接收到時隙分配表后，進行解析，獲得本站的時隙分配情況，在相應的時隙內(nèi)進行業(yè)務數(shù)據(jù)的傳輸。

因此，MF-TDMA衛(wèi)星通信系統(tǒng)具有非常強的實時性。如何高效快速地進行信道分配，使整個通信系統(tǒng)能夠公平、高效的進行業(yè)務傳輸一直是衛(wèi)星通信領(lǐng)域研究的課題。

1 周期輪詢法

1.1 分配約束條件

MF-TDMA系統(tǒng)的信道可以抽象理解為一個二維矩陣，其中行表示不同頻率的載波，列表示一幀內(nèi)劃分的時隙。分配過程可以看作是:在一定的約束條件下，將終端站的時隙申請，以盡快的速度分配到信道矩陣最合適的空閑時隙當中去。約束條件主要有以下3個方面:

①為同一終端站分配的時隙數(shù)量不能超過一個載波的時隙容量;

②為同一終端站分配的時隙資源，在時間上不能沖突;

③同一個時隙資源不能同時分配給2個業(yè)務申請。

1.2 分配過程分析

目前最常見的信道分配算法是周期輪詢法。該方法的分配過程是當中心站接收到各終端站的時隙申請信息后，按照申請業(yè)務的優(yōu)先級，將其從高到低進行排序。然后按照順序依次提取業(yè)務申請，找到對應的載波，從頭至尾進行一次輪詢，檢測時隙是否空閑。如果空閑，該時隙是否與申請沖突，如果未發(fā)生沖突，直接將該申請分配，提取下一個申請;如果發(fā)生沖突，繼續(xù)檢測下一個時隙，直至整個載波全部輪詢完畢，則該申請無法被分配，直接放棄，提取下一個申請，從載波的起始位置繼續(xù)重復這一輪詢過程。

圖1 周期輪詢法的流程圖

1.3 數(shù)學模型

MF-TDMA系統(tǒng)一幀的分配時間用T來表示，則:

式中，m表示一幀內(nèi)分配的時隙個數(shù);i表示分配過程中搜索到的空閑時隙個數(shù);tu表示搜索判斷一個時隙是否空閑的時間;j表示搜索的已分配時隙的個數(shù);k表示檢測沖突時的已分配載波數(shù)量;t'u表示檢測一個已分配時隙是否與申請沖突的時間。

不同tu之間的差值忽略不計，統(tǒng)一表示為t，同理t'u統(tǒng)一表示為t'，則式(1)可以表示為:

式中，t和t'受系統(tǒng)硬件條件的限制，一般來說是固定不可變的。真正決定分配時間的是m、i、j、k，即分配的申請個數(shù)、沖突出現(xiàn)的次數(shù)、對已分配時隙檢測的次數(shù)和已分配的載波數(shù)等因素。

1.4 算法的性能分析

周期輪詢算法的優(yōu)點是過程簡單容易實現(xiàn)，能夠保證優(yōu)先分配優(yōu)先級較高的業(yè)務時隙申請;缺點是分配的效率低下。這是因為該方法對每一個時隙申請，都采取同樣的輪詢操作。在輪詢的過程中，對空閑時隙和已分配時隙不加以區(qū)分，而是統(tǒng)一進行查詢比對，大量時間消耗在對已分配時隙的檢測比對上，即i*t所占T的比例很大。特別是當信道分配的末期，已分配時隙占信道時隙的大多數(shù)，此時進行分配，絕大部分分配時間都消耗在對已分配時隙的檢測上面。

2 時隙列表法

2.1 算法的優(yōu)化目標

對于MF-TDMA系統(tǒng)來說，時隙分配的計算時間是一個非常重要的性能指標，它直接影響申請的響應時間，是通信業(yè)務正常傳輸?shù)谋ＷC。

在時隙分配的初始階段，空閑時隙占信道的大多數(shù)，對其搜索是很容易的，可以快速完成。此時對已分配時隙的檢測非常少，對時間的消耗也不多。隨著信道中的時隙逐漸被分配，空閑時隙數(shù)量越來越少，對其搜索也越來越困難，在搜索的過程中，對已分配時隙的檢測占絕大多數(shù)。尤其是在信道分配過程的最后階段，為了分配一個時隙申請，要將幾乎信道中所有的時隙都檢測一遍。

由式(2)可以看到，周期輪詢法在分配的后期很大一部分時間用來檢測已分配時隙，即i*t。搜索的目的是要找到合適的空閑時隙，這一部分時間消耗對于分配的結(jié)果來說是毫無意義的，因此要盡量減小i*t。由于t是由系統(tǒng)所決定的，不可改變，只能減小搜索的次數(shù)i，盡量減少對已分配時隙的處理，甚至完全不再搜索已分配時隙。

2.2 原理

能夠解決這一問題的是時隙列表法。這種方法是通過創(chuàng)建和維護一個時隙列表，達到分配過程中“屏蔽”已分配時隙的目的。

如圖2所示，當信道分配進行到一定程度時，對空閑時隙的搜索變得困難，通過對信道進行一次輪詢，統(tǒng)計空閑可分配的時隙，創(chuàng)建一個列表，用以存放這些空閑時隙的信息，包括位置、大小和是否連續(xù)等。接下來的分配，中心站提取時隙申請后，不再直接對信道進行輪詢，而是在時隙列表中提取信息，在信道中直接尋找對應的空閑時隙，然后進行沖突檢測等操作。一旦分配成功，立即在時隙列表中將該空閑時隙的信息釋放。隨著分配到進行，時隙列表不斷地被釋放，其大小始終與信道中的空閑時隙數(shù)量是一致的。分配結(jié)束時，由時隙列表的大小可以直接得出該次時隙分配的信道利用率。這一方法借助時隙列表將繁瑣的輪詢搜索過程簡化為直接一步提取查找，對信道中已分配的時隙不再進行空閑檢測，達到了“屏蔽”的目的，能夠有效縮短分配時間。

圖2 時隙列表法的流程圖

該方法的本質(zhì)是將信道中的空閑時隙通過一次提取出來，重新組成新的信道矩陣，繼續(xù)進行分配。但是經(jīng)過時隙列表提取后，信道的規(guī)模大大減小，并且全部是空閑時隙，等同于在全新的信道內(nèi)繼續(xù)進行分配，因此搜索分配的效率大大提升，分配的時間將會得到大幅度縮減。

當然該方法只有在信道分配過程中才會有明顯效果。當信道內(nèi)存在大量空閑時隙時，容易搜索，使用時隙列表法和直接搜索的差別不大，時隙列表的創(chuàng)建和維護反而耗費了一定時間。當分配進行到一定階段，大部分時隙已被占用時，直接搜索的效率大大降低，時隙列表法才能發(fā)揮最大的效用。

2.3 具體實現(xiàn)

當信道開始分配時，可以使用周期輪詢法，在時隙分配一定數(shù)量后，對信道進行輪詢生成時隙列表;也可以直接對信道進行一次輪詢，不斷提取時隙申請進行分配，如果發(fā)生沖突不能分配，將空閑時隙記錄在時隙列表中，這樣經(jīng)過一次輪詢，不僅生成了時隙列表，并且分配了大量的時隙申請，減少了輪詢的次數(shù)m，最大限度地縮短了分配的時間。

具體的實現(xiàn)步驟:

①通過對信道進行一次輪詢，分配時隙申請的同時，根據(jù)信道內(nèi)空閑時隙的分布情況創(chuàng)建時隙列表;

②提取時隙申請，在時隙列表中提取空閑時隙的信息，根據(jù)其在信道中進行沖突的檢測;

③如果沒有發(fā)生沖突，直接將申請分配到信道中相應的空閑時隙中，同時在時隙列表中釋放該時隙，提取下一申請重復②;

④如果發(fā)生沖突，繼續(xù)在時隙列表中提取空閑時隙;

⑤信道搜索完畢后，仍無法分配，放棄該時隙申請，提取下一申請重復②;

⑥時隙申請全部提取或者信道全部被占用，釋放時隙列表，分配過程結(jié)束。

3 仿真優(yōu)化

針對MF-TDMA系統(tǒng)，對時隙分配的過程和時隙列表法進行模擬和仿真。仿真的具體條件設(shè)定如下:

① 網(wǎng)絡中的終端站規(guī)?！?，256】遞增;

②信道矩陣包含8個載波，一幀內(nèi)包含128個時隙;

③時隙申請為8*128的矩陣，發(fā)出申請的終端站隨機分布;

④每次分配前信道清零。

3.1 信道分配的過程分析

在信道分配的不同時期，分配相同數(shù)量的時隙申請，耗費的時間是不相同的。

圖3中的4條曲線分別表示分配的起始、進行和結(jié)束的不同階段，分配32個時隙申請所耗費的時間。

圖3 不同階段分配相等數(shù)量時隙耗費的時間

由仿真的結(jié)果，可以看到在分配過程的不同時期，分配同等數(shù)量的申請，分配的效率差別很大。在分配的初期，信道內(nèi)空閑時隙較多，分配的效率很高;隨著分配的進行，空閑時隙的搜索愈加困難，分配的效率越來越低。因此需要針對分配的不同時期，采取相應的策略以優(yōu)化分配的時間。

此外，在網(wǎng)絡規(guī)模較小時，時隙分配的時間會相對長一些，這是因為此時發(fā)出時隙申請的終端站分布較為集中，出現(xiàn)時隙沖突的概率較大，因此搜索的空閑時隙和檢測沖突的次數(shù)較多，從而導致分配的時間較長。

3.2 時隙列表法

圖4中的第1條曲線是原始的周期輪詢法;第2條曲線是首先使用原始輪詢法，在信道被分配50%的時候，采用時隙列表法;最后一條曲線，是在分配初始階段，采取一次輪詢分配多個申請，然后采用時隙列表法。

圖4 時隙列表法的比較

由仿真的結(jié)果可以看到，時隙列表法可以大幅度縮短時隙分配的時間。而在信道絕大部分時隙為空閑的時候，一次輪詢分配多個申請和時隙列表法相結(jié)合，可以極大地增強時隙列表法的優(yōu)化效果。

時隙列表法是對空閑時隙的搜索操作進行簡化，優(yōu)化了分配時間，對分配的結(jié)果沒有任何的影響，3種方法最終的信道利用率都是一致的。

4 結(jié)束語

通過對MF-TDMA系統(tǒng)時隙資源分配的周期輪詢法進行分析，提出時隙列表法，通過一次輪詢分配時隙并生成時隙列表，在列表中進行接下來的分配，避免了對已分配時隙的反復輪詢，簡化了分配操作，通過仿真分析，表明這一方法可以有效地縮短MFTDMA系統(tǒng)的時隙分配時間。

［1］PARK J M，CHONG E K P，SIEGEL H J.Allocation of QoS Connections in MF-TDMA Satellite Systems:A Two-Phase Approach［J］.IEEE Transactions on Vehicular Technology，2005，54(1):177-190.

［2］劉麗宏，孫晨華.MF-TDMA系統(tǒng)時隙分配算法的研究［C］∥第23屆全國通信與信息技術(shù)發(fā)展研討會，2006:313-316.

［3］董啟甲，張軍，張濤.星上MF-TDMA系統(tǒng)信道管理方法［J］.電子與信息學報，2009(10):2378-2384.

［4］董啟甲，張軍，張濤，等.高效MF-TDMA系統(tǒng)時隙分配策略［J］.航空學報，2009(9):1718-1726.

［5］郝學坤，孫晨華，李文鐸.MF-TDMA衛(wèi)星通信系統(tǒng)技術(shù)體制研究［J］.無線電通信技術(shù)，2006，32(5):224-228.

［6］劉麗宏，李維，劉海建.TDMA幀結(jié)構(gòu)研究［J］.無線電通信技術(shù)，2007，33(4):5-7.