梁 爽，趙偉光

（空軍工程大學(xué) 理學(xué)院，陜西 西安 710051）

時(shí)隙分配算法對充分提高系統(tǒng)資源利用率，縮短系統(tǒng)響應(yīng)時(shí)間、提高整個(gè)網(wǎng)絡(luò)的運(yùn)行效率均具有重要意義[1-3]。本文在VHF/UHF數(shù)據(jù)鏈系統(tǒng)的基礎(chǔ)上，首先通過對常用時(shí)隙分配策略的分析和比較，提出了一種新型時(shí)隙分配高層算法——漸變分配策略，之后，給出了算法所用競爭信道的優(yōu)化方案，并證明它優(yōu)于另外兩種優(yōu)化方案。

1 常用時(shí)隙分配策略的比較

目前，常用時(shí)隙分配策略有固定、動(dòng)態(tài)、競爭以及預(yù)約等分配策略。

固定分配，根據(jù)用戶最大需求量，通信前將所有時(shí)隙一次性分配給用戶。它適用于信道容量足夠大或用戶數(shù)量不多的情況。該方法實(shí)現(xiàn)簡單，且不會出現(xiàn)多址干擾。但信道利用率過低。動(dòng)態(tài)分配，則是根據(jù)用戶容量和業(yè)務(wù)量的大小變化來實(shí)時(shí)改變其時(shí)隙分配的多少，以提高資源使用效率。但實(shí)現(xiàn)比較復(fù)雜，并要為傳輸新的分配而開銷信道。競爭分配就是用戶在每時(shí)隙內(nèi)采用ALOHA方式搶占該時(shí)隙，如果只有一個(gè)用戶發(fā)送信息則發(fā)送成功，反之產(chǎn)生碰撞。用戶檢測到碰撞后，各自隨機(jī)延遲后重發(fā)。由于采用吞吐率不高的ALOHA方式，該方法不適合較大規(guī)模網(wǎng)絡(luò)使用。預(yù)約分配，是對競爭分配的改進(jìn)。用戶需要發(fā)送信息時(shí)，首先在專用信道中向網(wǎng)管中心預(yù)約，網(wǎng)管中心按照收到預(yù)約申請的先后順序給各申請用戶分配特定時(shí)隙。但這種分配策略實(shí)現(xiàn)起來較復(fù)雜[6-10]。

基于上述分析可見，預(yù)約分配策略對地空通信的可靠性要求過高，不適用于當(dāng)前時(shí)隙分配策略。固定分配策略相對不夠靈活，容易造成時(shí)隙浪費(fèi)或信息阻塞的可能。動(dòng)態(tài)分配雖然可以提高用戶時(shí)隙的使用率，但實(shí)現(xiàn)過于復(fù)雜，所消耗的額外開銷太多（因?yàn)樾枰獜?qiáng)運(yùn)算能力以應(yīng)對隨時(shí)出現(xiàn)的時(shí)隙釋放和時(shí)隙再分配）；同時(shí)，該策略還將占用很多通信資源來通知用戶新分配的時(shí)隙塊。而競爭分配策略在競爭用戶過多時(shí)，碰撞概率將大大增高，因而不適合較大規(guī)模的網(wǎng)絡(luò)使用。

2 漸變策略的基本思想

漸變分配策略預(yù)先利用固定分配方式為用戶分配時(shí)隙塊，同時(shí)再分配一個(gè)時(shí)隙塊作為所有用戶的公共信道，該信道所用時(shí)隙塊的大小可根據(jù)突發(fā)性信息的多少來確定，所有用戶可以采用競爭方式來使用該公共信道。由于競爭信道的存在，在分配時(shí)隙塊時(shí)，僅提供該用戶分配一個(gè)較小的時(shí)隙塊，將其他的信息傳輸任務(wù)交由競爭信道完成。如果用戶的信息傳輸高峰只持續(xù)較短時(shí)間，并且出現(xiàn)高峰概率較低時(shí)，這兩種分配方式便有機(jī)地結(jié)合在一起。但是，在某些特殊情況下，用戶的信息傳輸量需要大于設(shè)定量，且傳輸時(shí)間較長，如果有多個(gè)用戶出現(xiàn)這種情況，這時(shí)的競爭信道可能就會因碰撞概率過大而無法正常工作。鑒于此，再引入動(dòng)態(tài)分配策略的思想：如果用戶使用競爭信道的時(shí)間越過一定值時(shí)，將給它動(dòng)態(tài)地增加時(shí)隙；否則，將動(dòng)態(tài)地減小其所屬時(shí)隙塊的尺寸。由于有競爭信道作緩沖，不必頻繁地動(dòng)態(tài)調(diào)整用戶的時(shí)隙塊尺寸，進(jìn)而克服了動(dòng)態(tài)分配策略使用資源過多的缺點(diǎn)。

3 競爭信道

在漸變分配策略中，采用了競爭分配技術(shù)，利用競爭信道可以為多個(gè)用戶提供臨時(shí)的信息傳輸通道。

3.1 使用方式

通過載波監(jiān)聽多址接入（CSMA）使用競爭信道，但在目前現(xiàn)有設(shè)備的條件下，用戶采取CSMA方式使用競爭信道的同時(shí)會出現(xiàn)這樣的問題：飛機(jī)上的設(shè)備無法同時(shí)發(fā)送與接收信號。這就意味著用戶在發(fā)送信息時(shí)，無法檢測是否發(fā)生碰撞。為此，利用處于競爭信道某一發(fā)送時(shí)隙及其下一發(fā)送時(shí)隙之間的時(shí)隙，來負(fù)責(zé)檢測碰撞。如果一旦出現(xiàn)碰撞，則在它的消息尾部加一標(biāo)識符，該標(biāo)識符表明是否處于碰撞狀態(tài)。

3.2 優(yōu)化方案

為了降低競爭信道的碰撞概率，在文獻(xiàn)[4-5]中提出了兩種方案：優(yōu)先級檢測方案和優(yōu)先級預(yù)分配方案。

對于前者，如果用戶有信道可以通告其他用戶自身優(yōu)先級的話，那么它完全可以直接利用該信道發(fā)送消息而不必再使用競爭信道，鑒于此，其優(yōu)先級檢測部分無法實(shí)現(xiàn)。

對于后者，可通過如下證明來說明它不可能同時(shí)降低兩個(gè)優(yōu)先級的碰撞概率，而只能是：在提高其中一個(gè)競爭信道碰撞概率的同時(shí)，降低另一競爭信道的碰撞概率。

證明：為了簡化證明過程，作如下假設(shè)：競爭信道中的時(shí)隙間隔是均勻的，在兩個(gè)競爭時(shí)隙之間突發(fā)信息產(chǎn)生的概率遠(yuǎn)遠(yuǎn)小于1。

設(shè)Ai= {在第i-1個(gè)時(shí)隙到第i個(gè)時(shí)隙期間產(chǎn)生突發(fā)信息的事件}；

Di= {在第i-1個(gè)時(shí)隙到第i個(gè)時(shí)隙期間所產(chǎn)生的突發(fā)信息發(fā)生傳輸碰撞的事件}；

Fi={第i個(gè)時(shí)隙產(chǎn)生傳輸碰撞的事件}；

Ei= {第i個(gè)時(shí)隙的前k個(gè)競爭時(shí)隙有沖突發(fā)生并有1個(gè)突發(fā)信息順延到第i個(gè)時(shí)隙的事件}；

Pk表示第i個(gè)時(shí)隙產(chǎn)生沖突后，后k個(gè)競爭時(shí)隙中任選一個(gè)時(shí)隙被作為下一次發(fā)送時(shí)隙的概率。

由式（3）～式（6）可以看出，在第i個(gè)時(shí)隙發(fā)生傳輸碰撞的概率只與兩個(gè)競爭時(shí)隙間突發(fā)信息產(chǎn)生的概率P{Ai}有關(guān)：當(dāng)P{Ai}減小時(shí)，P{Fi}減??；而當(dāng) P{Ai}增大時(shí)，P{Fi}也增大。

將競爭信道按圖1所示劃分為高低優(yōu)先級兩個(gè)信道，假設(shè)高低優(yōu)先級的突發(fā)信息產(chǎn)生概率P{A1i’}和P{A2i’}是相同的，則：

圖1 競爭信道的優(yōu)先級劃分Fig.1 Priority partition of competation channel

雖然，通過將突發(fā)信息劃分為高低兩類將它們的發(fā)生概率降低了一倍，但是競爭的劃分又將時(shí)隙間隔增大了一倍。所以劃分后的兩個(gè)競爭信道，其時(shí)隙間突發(fā)信息產(chǎn)生的概率分別為P{A1i}和P{A2i}，它們與劃分前的競爭信道，其時(shí)隙間突發(fā)信息產(chǎn)生的概率P{Ai}是完全相同的，即：

而第i個(gè)時(shí)隙發(fā)生碰撞的概率只與兩個(gè)競爭時(shí)隙間突發(fā)信息產(chǎn)生的概率P{A1i}或P{A2i}有關(guān)，因此，將信道劃分為高低兩個(gè)優(yōu)先級并不能降低碰撞的概率。

如果高低優(yōu)先級的突發(fā)信息的產(chǎn)生概率不同，可以證明：劃分后用于傳輸突發(fā)信息產(chǎn)生概率低的競爭信道，其碰撞概率將比劃分前低，而劃分后用于傳輸突發(fā)信息產(chǎn)生概率高的競爭信道，其碰撞概率將比劃分前高。綜上所述，通過優(yōu)先級的劃分無法同時(shí)降低兩個(gè)劃分后信道的碰撞概率。

雖然劃分高低優(yōu)先級別無法同時(shí)降低兩個(gè)劃分后信道的碰撞概率，但劃分優(yōu)先級別可對劃分后兩個(gè)信道的碰撞概率進(jìn)行調(diào)整。本文利用該特性對競爭信道進(jìn)行了優(yōu)化：首先，將競爭信道劃分為高低優(yōu)先級兩種競爭信道，高優(yōu)先級別的競爭信道用于傳輸高優(yōu)先級別的消息，而低優(yōu)先級別的競爭信道用于傳輸?shù)蛢?yōu)先級別的消息。因?yàn)楦邇?yōu)先級別的消息發(fā)生概率小于低優(yōu)先級別，所以高優(yōu)先級競爭信道的碰撞概率小于低優(yōu)先級，進(jìn)而使高優(yōu)先級消息能更快地發(fā)送出去。其次，還須對競爭時(shí)隙塊的尺寸引入動(dòng)態(tài)調(diào)整機(jī)制，進(jìn)而實(shí)現(xiàn)競爭信道的動(dòng)態(tài)優(yōu)化：當(dāng)競爭信道的碰撞概率長時(shí)間大于某一門限值時(shí)或長時(shí)間小于某一門限值時(shí)，將相應(yīng)地調(diào)整競爭時(shí)隙塊尺寸的大小，其實(shí)現(xiàn)流程如圖2所示。

4 結(jié) 論

本文針對地空數(shù)據(jù)鏈系統(tǒng)的特點(diǎn)，在比較常用時(shí)隙分配策略優(yōu)缺點(diǎn)的基礎(chǔ)上，提出了一種新的高層時(shí)隙分配算法——漸變分配策略。它主要是以固定分配方式為主，以競爭分配和動(dòng)態(tài)分配為輔的一種新的時(shí)隙分配策略，兼有固定分配、競爭分配以及動(dòng)態(tài)分配的優(yōu)點(diǎn)，同時(shí)又盡可能地避免它們的缺點(diǎn)，以最小代價(jià)換來最大成效。同時(shí)，在競爭信道方面，給出了競爭信道的使用方式及其優(yōu)化的具體方案，并且通過證明得出兩種方案的缺陷。參考文獻(xiàn):

圖2 競爭信道的優(yōu)化方案Fig.2 Priority method of competition channel

[1]張軍，李忠孝，胥青.一種新的S-TDMA系統(tǒng)的時(shí)隙分配方案[J].航空學(xué)報(bào)，2008，22（6）：98-102.

ZHANG Jun，LI Zhong-xiao，XU Qing.New slot allocation scheme in Self-organized TDMA systems[J].Acta Aeronautica Et Astronautica Sinica，2008，22（6）：98-102.

[2]張軍.VHF空地?cái)?shù)據(jù)鏈的應(yīng)用與研究[D].北京：航空航天大學(xué)，2007.

[3]孔紅偉，阮方，馮重熙.一種動(dòng)態(tài)時(shí)分窄帶多業(yè)務(wù)接入新方案[J].電子學(xué)報(bào)，2009，30（4）：587-590.

KONG Hong-wei，RUAN Fang，F(xiàn)ENG Chong-xi.A novel dynamic time-slot allocation solution for narrow-band multiservicesccess[J].ActaElectronicaSinica，2009，30（4）：587-590.

[4]丁銳，鄭龍，等.動(dòng)態(tài)TDMA時(shí)隙分配算法在數(shù)據(jù)鏈中的仿真[J].通信技術(shù)，2011（2）：105-107.

DING Rui，ZHENG Long，et al.Modeling of TDMA-based dynamic slotassignmentalgorithm for data link[J].Communications Technology，2011（2）：105-107.

[5]高強(qiáng)，嚴(yán)俊，等.CDM機(jī)制下航空公司時(shí)隙分配優(yōu)化決策[J].交通運(yùn)輸系統(tǒng)工程與信息，2011（5）：94-98.

GAO Qiang，YAN Jun，et al.Airlines optimization decision of slot allocation in CDM[J].Journal of Transportation Systems Engineering and Information Technology，2011（5）：94-98.

[6]盧正星.一種基于時(shí)隙交換的CDMA/TDD時(shí)隙分配算法[J].北京郵電大學(xué)學(xué)報(bào)，2008，27（2）：108-112

LU Zheng-xing.An time slot allocation algorithm based on slot switch for CDMA/TDD[J].Journal of Beijing University of Posts and Telecommunications，2008，27（2）：108-112.

[7]Wie S H，Cho D H.Time slot allocation scheme based on a region division in CDMA-TDD systems[C]//Proceeding of VTC2006/Fall，2006：2445-2449.

[8]Roorda P，Victor C.M.Leung.Dynamic time slot assignment in reservation protocols for multiaccess channels[C]//IEEE Pac Rim2007，2007：451-454.

[9]孫曉陽.空域與流量協(xié)同管理策略研究[D].南京：南京航空航天大學(xué)，2010.

[10]趙磊.飛機(jī)進(jìn)港時(shí)隙分配機(jī)制的有效性與公平性研究[C]//2008第四屆中國智能交通年會論文集，2008.