許 楠，郝學(xué)坤，許 眾

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

0 引言

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

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

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

1 周期輪詢(xún)法

1.1 分配約束條件

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

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

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

③同一個(gè)時(shí)隙資源不能同時(shí)分配給2個(gè)業(yè)務(wù)申請(qǐng)。

1.2 分配過(guò)程分析

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

圖1 周期輪詢(xún)法的流程圖

1.3 數(shù)學(xué)模型

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

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

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

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

1.4 算法的性能分析

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

2 時(shí)隙列表法

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

對(duì)于MF-TDMA系統(tǒng)來(lái)說(shuō)，時(shí)隙分配的計(jì)算時(shí)間是一個(gè)非常重要的性能指標(biāo)，它直接影響申請(qǐng)的響應(yīng)時(shí)間，是通信業(yè)務(wù)正常傳輸?shù)谋ＷC。

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

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

2.2 原理

能夠解決這一問(wèn)題的是時(shí)隙列表法。這種方法是通過(guò)創(chuàng)建和維護(hù)一個(gè)時(shí)隙列表，達(dá)到分配過(guò)程中“屏蔽”已分配時(shí)隙的目的。

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

圖2 時(shí)隙列表法的流程圖

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

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

2.3 具體實(shí)現(xiàn)

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

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

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

②提取時(shí)隙申請(qǐng)，在時(shí)隙列表中提取空閑時(shí)隙的信息，根據(jù)其在信道中進(jìn)行沖突的檢測(cè);

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

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

⑤信道搜索完畢后，仍無(wú)法分配，放棄該時(shí)隙申請(qǐng)，提取下一申請(qǐng)重復(fù)②;

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

3 仿真優(yōu)化

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

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

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

③時(shí)隙申請(qǐng)為8*128的矩陣，發(fā)出申請(qǐng)的終端站隨機(jī)分布;

④每次分配前信道清零。

3.1 信道分配的過(guò)程分析

在信道分配的不同時(shí)期，分配相同數(shù)量的時(shí)隙申請(qǐng)，耗費(fèi)的時(shí)間是不相同的。

圖3中的4條曲線分別表示分配的起始、進(jìn)行和結(jié)束的不同階段，分配32個(gè)時(shí)隙申請(qǐng)所耗費(fèi)的時(shí)間。

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

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

此外，在網(wǎng)絡(luò)規(guī)模較小時(shí)，時(shí)隙分配的時(shí)間會(huì)相對(duì)長(zhǎng)一些，這是因?yàn)榇藭r(shí)發(fā)出時(shí)隙申請(qǐng)的終端站分布較為集中，出現(xiàn)時(shí)隙沖突的概率較大，因此搜索的空閑時(shí)隙和檢測(cè)沖突的次數(shù)較多，從而導(dǎo)致分配的時(shí)間較長(zhǎng)。

3.2 時(shí)隙列表法

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

圖4 時(shí)隙列表法的比較

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

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

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

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

［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)時(shí)隙分配算法的研究［C］∥第23屆全國(guó)通信與信息技術(shù)發(fā)展研討會(huì)，2006:313-316.

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

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

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

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