Link16時隙固定分配算法的時延分析

(空軍工程大學 電訊工程學院，西安 710077)

1 引 言

數據鏈是鏈接數字化戰場上的各種傳感器、指揮中心、武器平臺和作戰部隊的一種信息處理、交換和分發系統。在數據鏈系統中，各種信息按照規定的格式，實時、自動、保密地進行傳輸和交換，從而實現信息資源共享，最大限度地提高作戰效能。

時分多址(TDMA)作為一種有效的多址接入方式在數據鏈中得到廣泛應用。TDMA系統中主要的時隙分配算法有固定分配、競爭分配、預約分配和動態再分配[1]。固定分配，也稱為靜態分配或預分配，指在通信前根據對用戶業務量的統計，給每個用戶一次性分配一定量的時隙資源。用戶在每幀中分配給自己的專用時隙上無沖突的發送信息，在其它時隙中接收有用信息。固定分配的優點在于實現比較簡單，并且可以保證每個用戶之間的“公平性”(每個用戶都分配了固定專用的時隙資源)以及報文的平均時延。因此，固定分配在數據鏈中得到了廣泛應用。例如，數據鏈Link16的多址接入方式采用TDMA，其最常用的時隙分配算法就是固定分配，只有在時隙容量不足或特殊條件下才使用競爭分配或動態再分配[2]。

2 固定分配算法建模分析

2.1 模型建立

在Link16中，將一天24 h劃分為112.5個時元，每時元持續時間為12.8 min。每時元再劃分為64個時幀，幀長為12 s。時幀中總共包含m=1 536個時隙，每個時隙寬度為τ=7.812 5 ms。在一個時幀中，時隙被編入3個時隙組，即A組、B組、C組。每組共包含512個時隙，編號為0～511。時幀結構如圖1所示[3]。

圖1 時幀結構示意圖Fig.1 Structure of time frame

Link16的J系列消息總共有91類消息，但每個用戶在作戰過程中不一定收發所有類型的消息，而是只能或只需處理特定類型的消息。為此，把J系列消息按照功能進行分組，這些分組稱為網絡參與組(NPG)。因此，首先將系統的時隙資源分配給各NPG，不同的NPG分配到不同的時隙數量。NPG再將時隙分配給各用戶，用以發送和接收該NPG上的消息。

時隙以時隙塊的形式進行分配。采用二叉樹法劃分時隙塊，這樣時隙塊中的時隙等間隔地分布在整個時幀之中。

時隙塊的表示方法為：時隙組-起始時隙號-重現率。例如，時隙塊A-2-11表示屬于時隙組A，起始時隙是2，重復率為11(每個時幀中含有211-6=32個時隙，在時隙組A中時隙間隔為16個時隙)，時隙編號可用(2+16n)來表示，即包含時隙：A-2，A-18，A-34，…，A-498。

表1 4種消息封裝結構及特性Table 1 Four data packing formats and their features

在Link16中，根據支持的消息類型、吞吐量需求和抗干擾性能需求，用戶端機可以產生4種消息封裝結構，它們是由抖動(STDP、P2SP中有抖動，P2DP、P4SP中沒有抖動)、粗精同步頭、報頭、消息本體(含有消息字，每個消息字包含70 bit的用戶數據)和傳輸保護段構成的，如表1和圖2所示。

圖2 時隙結構示意圖Fig.2 Structure of timeslot

2.2 模型分析與求解

2.2.1 指標分析

時延指報文從源節點發送到目的節點所需要的延遲時間。該指標體現了系統傳輸信息的時效性。

按照發生的順序，時延主要包括4個部分：

(1)處理時延：指當報文在源節點產生到該報文進入到發送隊列之間的時間差；

(2)等待時延：指當報文進入到發送隊列到該報文開始被傳輸之間的時間差。在這個時延階段，該報文首先要等待比其先到發送隊列的報文傳輸完畢，然后再等待時幀內可用的服務時隙的到來；

(3)傳輸時延：指當報文開始被傳輸第一個比特到傳輸完最后一個比特之間的時間差；

(4)傳播時延：指報文最后一個比特被傳輸完到該比特被目的節點接收之間的時間差。

處理時延和傳輸時延主要與硬件性能及一些設置相關，傳播時延是物理距離的函數，所以三者基本上都是固定值。而等待時延與選擇的時隙分配方式有密切關系，并且是影響消息響應時間的主要因素[4]。因而，在接下來的分析求解過程中，主要討論用戶報文的平均等待時延。

2.2.2分析與求解

由于各用戶的報文平均到達率λi和服務速率μCi都不相同，故各用戶的平均等待時延各不相同。設用戶i的報文的平均等待時延為Ti，那么Ti由兩部分組成：

(1)報文的平均排隊時延Wi，包括等待比其先到發送隊列的報文傳輸完畢的時延和正在接受服務的報文的剩余服務時間；

(2)報文等待時幀內服務時隙的平均時延。

由排隊論中的P-K(Pollaczek-Khinchin)公式知[5-8]，用戶i的報文的平均排隊時延為

(1)

(2)

ρi為其排隊系統的負荷率，即報文的平均到達率和服務速率之比，所以：

(3)

因此，可求得報文的排隊時延為

(4)

綜上所述，可求得用戶i的平均等待時延為

(5)

利用Little定理，可求得用戶i的發送隊列中的平均報文數為

(6)

3 數值計算與仿真

3.1 數值計算

因此，可求得該用戶的平均等待時延為

利用Little定理，該用戶的發送隊列中的平均報文數為

由Link16的時隙結構可知，在一個時隙內既包含了傳輸時間也包含了傳播時間，即兩者之和小于7.812 5 ms，而數據鏈的處理時延一般都比較小。因此通過數值計算可知，它們都遠遠小于等待時延，即用戶報文的總時延主要是由等待時延部分構成，等待時延是影響消息響應時間的主要因素。

3.2 仿真結果與分析

通過對前面建立的固定分配算法模型進行仿真，可以得到用戶i報文的平均等待時延Ti和隊列中的平均報文數Ni隨著負荷率ρi的變化規律，分別如圖4和圖5所示。

圖4 平均等待時延與負荷率的關系Fig.4 Average waiting time delay vs load rate

圖5 平均報文數與負荷率的關系Fig.5 Average message number vs load rate

由圖4可以看出：

(1)當負荷率ρi在(0，1)范圍內增大時，Ti隨之增大。當負荷率ρi趨于1時，Ti將趨于無窮大。因此，在進行時隙固定分配時，應根據網絡規劃等要求使數據鏈工作在合適的負荷率。如果選取的負荷率過小，就會造成時隙資源的浪費，降低系統的吞吐量；相反，如果選取的負荷率過大(接近于1)，那么吞吐量接近飽和，造成時延急劇惡化，此時無法滿足系統規定的消息響應時間的通信要求；

(2)比較圖4中的3條曲線可知，在負荷率ρi相同的情況下，Ti隨著分配給用戶的時隙數ni的增大而減小。因此，采用時隙固定分配算法時，系統必須根據事先對用戶業務量的統計，給用戶分配足夠的時隙來降低時延，從而確保達到系統規定的消息響應時間的要求；

(3)當給用戶分配定量時隙之后，如果用戶的業務量突然增大，即負荷率增大，由圖可知時延也將隨之增大，從而可能無法滿足系統規定的消息響應時間的要求，此時應當視消息發送失敗。由此可以看出，固定分配算法適用于用戶業務量比較穩定的情況，這樣負荷率能夠在維持在一個合適的小范圍內。如果用戶業務量不穩定或者時隙資源不夠分配，那么將會使時延增大，無法滿足系統規定的消息響應時間等要求，這體現了固定分配算法不夠靈活。

由圖5可以看出：用戶的發送隊列中的報文數隨著負荷率ρi的增大而增大，即ρi反映了排隊系統的繁忙程度。但實際上用戶的緩存器容量是有限的，如果發送隊列中的報文過多而超過了緩存器容量，那么將會出現丟棄報文的情況。

4 結束語

時隙分配是數據鏈網絡規劃管理的一個重要部分，它影響到網絡能否高效、可靠地運行，必須針對不同的應用場合選取合適的時隙分配算法，從而達到提高網絡性能的目的。本文通過運用排隊論理論，建立了Link16的時隙固定分配算法的排隊模型，并對其時延特性進行了具體的分析和求解。數值計算和仿真結果表明，時隙固定分配算法適用于用戶業務量比較穩定且時隙資源充足的情況，必須選取合適的負荷率，才能夠滿足系統規定的消息響應時間的要求，使系統達到良好的吞吐量。本文為研究其它時隙分配算法提供了對比和參考。

參考文獻：

[1] 梁爽.地空數據鏈中越區切換和時隙動態分配的應用與研究[D].西安：空軍工程大學，2005.

LIANG Shuang. Application and Study of Handover and Timeslot Allocation in Ground to Air Data Link[D].Xi′an: Air Force Engineering University, 2005. (in Chinese)

[2] 駱光明，楊斌，邱致和，等.數據鏈[M].北京：國防工業出版社，2008.

LUO Guang-ming,YANG Bin,QIU Zhi-he,et al.Data Link[M].Beijing: National Defense Industry Press,2008.(in Chinese)

[3] 梅文華，蔡善法.JTIDS/Link16數據鏈[M].北京：高等教育出版社，2004.

MEI Wen-hua,CAI Shan-fa. JTIDS/Link16 Data Link[M].Beijing: Higher Education Press, 2004. (in Chinese)

[4] 侯新宇.數據鏈時隙動態分配及其網絡規劃技術研究[D].成都：電子科技大學，2008.

HOU Xin-yu. Reseach on Dynamic Timeslot Allocation and Network Layout Technique for Data Link[D].Chengdu: University of Electronic Science and Technology of China, 2008. (in Chinese)

[5] 李建東，盛敏.通信網絡基礎[M].北京：高等教育出版社，2004.

LI Jian-dong,SHENG Ming. Base of Communication Network[M].Beijing: Higher Education Press, 2004. (in Chinese)

[6] 仝海波，梁俊，呂娜.戰術數據鏈時延特性的仿真分析[J].電光與控制，2009,16(8):53-55,64.

TONG Hai-bo,LIANG Jun,LV Na. Simulation and Analysis on Delay Performance of Tactical Data Link[J].Electronics Optics and Control, 2009,16(8): 53-55,64. (in Chinese)

[7] 汪榮鑫.隨機過程[M].西安：西安交通大學出版社，2006.

WANG Rong-xin.Stochastic Process [M].Xi′an: Xi′an Jiaotong University Press, 2006. (in Chinese)

[8] 張軍，李忠孝.自組織時分多址甚高頻數據鏈的延時分析[J].北京航空航天大學學報，2004,30(3):222-226.

ZHANG Jun,LI Zhong-xiao. Delay Analysis of Self-Organized TDMA VHF Datalink[J].Journal of Beijing University of Aeronautics and Astronautics, 2004,30(3):222-226.(in Chinese)