彭樹林 湯可成 高萬明 王翔

摘 要：文章針對NAVDAT數(shù)據(jù)傳輸系統(tǒng)，研究時隙的分配及協(xié)調(diào)方法，實現(xiàn)了一種集中協(xié)調(diào)的時隙分配方案，能夠最大限度地利用所有帶寬資源傳輸數(shù)據(jù)。

關鍵詞：NAVDAT；發(fā)射時隙：協(xié)調(diào)

采用64QAM調(diào)制的NAVDAT數(shù)據(jù)鏈路，以500 kHz的發(fā)射頻率，在100～200海里的范圍內(nèi)為船載移動終端提供19～28 kbps的下行數(shù)據(jù)服務，使航行警告信息、氣象傳真圖以及海圖更新等能夠及時播發(fā)到船舶終端[1]。

由于無線電傳播距離受發(fā)射時的電磁環(huán)境影響較大，各NAVDAT臺站的覆蓋可能交叉重疊，且可能重疊的范圍大小變化。并且在解決全區(qū)域覆蓋時，采用時分或單頻網(wǎng)絡的方式來實現(xiàn)[1]。由于NAVDAT使用的頻點是固定的，為了避免電臺間的發(fā)射干擾（64QAM對干擾比較敏感），必須保證各個交叉覆蓋的NAVDAT臺站傳輸數(shù)據(jù)的時隙互斥。

本文針對NAVDAT數(shù)據(jù)傳輸系統(tǒng)，研究時隙的分配及協(xié)調(diào)方法，實現(xiàn)了一種集中協(xié)調(diào)的時隙分配方案，能夠最大限度地利用所有帶寬資源傳輸數(shù)據(jù)。

本文所述的方法，采用動態(tài)規(guī)劃的方法對時隙進行全局優(yōu)化，通過一個全局時隙分配表，將各NAVDAT發(fā)射臺的發(fā)射協(xié)調(diào)到總帶寬最大的狀態(tài)。

1 時隙協(xié)調(diào)技術

1.1時隙協(xié)調(diào)的目的和意義

NAVDAT數(shù)據(jù)傳輸系統(tǒng)，在不同地理空間時分復用相同的頻點，傳輸不同的業(yè)務數(shù)據(jù)。在保證不相互沖突的情況下，盡可能使每個NAVDAT臺站的每個可用時隙資源都被利用。

時隙協(xié)調(diào)的目的在于最大限度利用各臺站的時隙資源來傳輸數(shù)據(jù)，使系統(tǒng)的總帶寬達到最大的狀態(tài)。

時隙協(xié)調(diào)的重要意義在于，通過時隙協(xié)調(diào)，高優(yōu)先級報文及時播發(fā)的同時，支持多種低優(yōu)先級報文“同時”傳輸。在一個窄帶的數(shù)據(jù)鏈路上“同時”承載多種業(yè)務數(shù)據(jù)。通過時隙協(xié)調(diào)，航行告警、氣象傳真、海圖更新都能夠在短時間內(nèi)快速完成。

1.2時隙協(xié)調(diào)的評價指標

確立時隙協(xié)調(diào)效果的評價指標，對系統(tǒng)的方案設計、優(yōu)化、評審以及時隙協(xié)調(diào)的優(yōu)化算法開發(fā)都有指導意義。

優(yōu)化算法需要優(yōu)化的目標函數(shù)，在NAVDAT數(shù)據(jù)傳輸系統(tǒng)中，目標是可用傳輸帶寬最大?？捎脗鬏攷捠歉鱾€NAVDAT發(fā)射臺站，在，時刻所有可使用帶寬之和。

1.3集中時隙協(xié)調(diào)方法

NAV DAT系統(tǒng)的集中協(xié)調(diào)方法，將系統(tǒng)中每個NAVDAT臺站的發(fā)射時隙視為可調(diào)度、可分配的“資源”，稱為“時隙資源”。該方法將任何一個NAVDAT臺站所需要的時隙資源進行統(tǒng)一的協(xié)調(diào)分配，對不存在交叉覆蓋的臺站，按需自由分配時隙資源；對兩個或兩個以上存在重疊覆蓋區(qū)域的NAVDAT臺站，采用時隙互斥的分配機制來避免重疊覆蓋區(qū)域的干擾。在此基礎上，通過進行全局優(yōu)化的時隙資源分配方法，使系統(tǒng)的無線帶寬資源利用率達到最大。

1.4集中時隙協(xié)調(diào)過程

首先，NAVDAT臺站將數(shù)據(jù)傳輸?shù)娜蝿蛰d荷經(jīng)過包拆分，變?yōu)槿舾纱龜?shù)據(jù)塊，每個數(shù)據(jù)塊具有應用識別碼以及序列號。將這些數(shù)據(jù)塊按序號編成一個數(shù)據(jù)傳輸任務的隊列。

再次，NAVDAT臺站向協(xié)調(diào)服務器申請發(fā)射時隙，在申請時應當向協(xié)調(diào)服務器說明任務的優(yōu)先級PT、數(shù)據(jù)發(fā)送所需的時隙數(shù)NTS。 接下來，協(xié)調(diào)服務器根據(jù)申請，進行全局優(yōu)化計算時隙的分配結(jié)果，并將時隙分配結(jié)果發(fā)送給申請時隙的臺站。時隙分配的結(jié)果分為兩種：批準時隙、拒絕申請。

最后，申請時隙的臺站，根據(jù)批準的時隙安排數(shù)據(jù)的傳輸，將傳輸任務隊列轉(zhuǎn)移到發(fā)射隊列，等待自動發(fā)射。若申請被否決，應等待60 s后嘗試重新申請。

若申請過程中協(xié)調(diào)服務器的響應超時，應嘗試5-7次，間隔時間為10～30s。若嘗試5-7次仍然失敗，就激活故障保護模式，以故障保護方式自授權發(fā)射時隙。

1.5基本技術術語定義

1.5.1時隙

將每分鐘的60 s，等分為2 250個時隙，每個時隙為26.667 ms （NAVDAT的OFDM調(diào)制的每個符號長度24 ms及其保護長度2.667 ms合計26.667 ms）。

1.5.2時隙協(xié)調(diào)服務器

時隙協(xié)調(diào)服務器接受NAVDAT臺站的時隙申請并為其分配所需時隙，并實現(xiàn)時隙優(yōu)化。

1.5.3數(shù)據(jù)傳輸任務

等待傳輸?shù)臄?shù)據(jù)源構成一個數(shù)據(jù)傳輸任務，具有應用分類識別碼及優(yōu)先級等屬性。

1.5.4任務隊列

數(shù)據(jù)傳輸任務的數(shù)據(jù)源，經(jīng)過拆分為若干數(shù)據(jù)塊并加上包頭，構成一系列用于傳輸?shù)臄?shù)據(jù)包序列，等待分配時隙逐個傳輸。這些數(shù)據(jù)包就構成數(shù)據(jù)傳輸?shù)娜蝿贞犃小?/p>

1.5.5發(fā)射隊列

當任務隊列的包被批準后，就從任務隊列轉(zhuǎn)移到發(fā)射隊列，在批準的時刻進行傳輸。

1.5.6消極站與積極站

一個NAVDAT臺站，若發(fā)射隊列為空，稱為消極站，否則稱為積極站。

1.5.7待協(xié)調(diào)站和休眠站

一個NAVDAT臺站，若任務隊列都不為空，稱為待協(xié)調(diào)站。待協(xié)調(diào)站會主動向協(xié)調(diào)服務器申請時隙，將待傳輸?shù)臄?shù)據(jù)傳輸?shù)揭苿咏K端。

一個NAVDAT臺站，若發(fā)射隊列和任務隊列均為空，稱為休眠站。休眠站不占用任何資源，優(yōu)化算法的計算過程中，忽略休眠站。

1.5.8全局時隙分配表

全局時隙分配表是一張時隙資源的描述表，該表用于描述NAVDAT系統(tǒng)中每個臺站未來各個時隙的分配狀況。當時隙分配導致表格內(nèi)容發(fā)生變化，時隙協(xié)調(diào)服務器將廣播這個變化，使全局時隙分配表在各個NAVDAT臺站的副本進行同步。

1.5.9全局瞬時帶寬

任意時刻t，所有積極站的帶寬之和，即，時刻的可用傳輸帶寬之和。

B（O=∑Ai（t）bi（t）

（1）

式（1）中，A/（t）是第i個NAVDAT臺站狀態(tài)的二值函數(shù)，積極站是取值為l，消極站取值為0。bi（t）是第i個NAVDAT臺站在t時刻的帶寬，與其調(diào)制模式有關。取值為以下值之一：6.36 kbps， 9.56 kbps， 12.76 kbps， 19.16 kbps， 28.76 kbpS。

1.5.10 NAVDAT臺站平均帶寬

第；個NAVDAT臺站，給定的時間段（t1，12），可用帶寬積分值除以時長：

Bi**（t1，t2）=（∫Ai（t）bi（t）÷（t2-t1）

（2）

2 NAVDAT時隙協(xié)調(diào)方法

2.1時隙協(xié)調(diào)規(guī)則

（1）兩個不相互交叉覆蓋的NAVDAT臺站，可以使用重疊的發(fā)射時隙。

（2）兩個相互重疊覆蓋的NAVDAT臺站，使用的發(fā)射時隙必須互斥，不可使用重疊的發(fā)射時隙。

（3）兩個相互重疊覆蓋的NAVDAT臺站，發(fā)射任務飽滿時，一般也不采用平均分配策略來分配時隙，要考慮任務的優(yōu)先級及數(shù)據(jù)的長度。

（4）臺站內(nèi)部可根據(jù)自行調(diào)整己分配的時隙，將高優(yōu)先級的任務所獲得的時隙在發(fā)射隊列中與其他低優(yōu)先級任務的發(fā)射時隙交換，以便實時完成航行警告等高優(yōu)先級的數(shù)據(jù)傳輸任務。

（5）全局優(yōu)化的指標。全局優(yōu)化時，不僅要考慮全局瞬時帶寬的最大化，還要考察各個NAVDAT臺站任務飽和時的平均帶寬最大化（按優(yōu)先級）。

全局優(yōu)化時，采用以下兩個指標：（1）全局瞬時帶寬最大，MAX[B（t）]。（2） NAVDAT臺站平均帶寬最大，MAX[B/*（t1，t2）]。

2.2 NAVDAT臺站發(fā)射時隙協(xié)調(diào)算法

NAVDAT臺站發(fā)射時隙仂調(diào)算法是一種合作分配算法，借助動態(tài)規(guī)劃手段進行全局優(yōu)化。并采用全局一致的故障保護模式處理網(wǎng)絡通信故障。

2.2.1初始條件 時隙分配表TS[N][60000]清零，表示所有站的所有時隙未分配。故障保護模式時隙分配表TSE [N][60000]初始化，裝入預設值。表格Distance_S2S[N][N]裝入預設值，表示臺站之間的空間最短距離。

2.2.2限制條件

時隙分配的限制條件主要包括臺站與臺站的時隙互斥關系、任務的優(yōu)先級以及任務的時隙需求量等。

（1）臺站與臺站的時隙互斥關系。特定條件下NAVDAT臺站間的互斥關系，由臺站的覆蓋距離以及臺站到臺站的最短空間距離共同決定。若某個NAVDAT臺站的覆蓋距離因電磁環(huán)境或發(fā)射機功率出現(xiàn)調(diào)整或臺站的發(fā)射模式改變，需要重新計算臺站與臺站的時隙互斥關系。計算結(jié)果存放到互斥關系表Mutex_S2S[N] [N]中，以便控制時隙分配。

臺站到臺站的最短空間距離由表格Distance_S2S[N][N]決定，初始化時裝入預設值。表示任意兩個NAVDAT臺站發(fā)射天線之間的空間最短距離（曲線距離而非直線距離）。

臺站的覆蓋距離由發(fā)射功率、天線輻射效率、天線安裝高度、地理位置以及天氣條件等因素共同決定，不是一個精確值，只是一個大概數(shù)。由計算調(diào)整結(jié)果存入表格Coverage[N]。若NAVDAT臺站發(fā)射電磁波的電磁環(huán)境發(fā)生較大變化，或則發(fā)射機輸出功率出現(xiàn)調(diào)整，或臺站的發(fā)射模式改變，都需要重新計算臺站的覆蓋距離。

（2）任務的優(yōu)先級PT。任務的優(yōu)先級決定時隙分配的優(yōu)先程度。當一個高優(yōu)先級的數(shù)據(jù)傳輸任務（例如搜救信息播發(fā)）需要立即執(zhí)行時，時隙協(xié)調(diào)的分配算法必須馬上安排發(fā)射時隙。

（3）任務的時隙需求量NTS。對數(shù)據(jù)傳輸任務的數(shù)據(jù)量沒有限制，但在申請時隙時，需要申明所需要的時隙數(shù)，即時隙需求量。223時隙申請鏈表

時隙申請鏈表REQ_LINK[N]記錄各個NAVDAT臺站提出的申請中未處理的申請鏈表。當REQ_LINK[N]為空指針（NULL）時，表示第N個NAVDAT臺站的申請已處理完畢。

臺站申請時隙，會動態(tài)生成一個申請表REQ，在REQ中記錄任務的優(yōu)先級、所需的時隙數(shù)，還有一個鏈表指針指向該NAVDAT臺站的下一個申請表。申請表插入在時隙申請鏈表REQ_LINK[N]對應臺站鏈表的尾部。申請表REQ中還包含動態(tài)優(yōu)先數(shù)和等待延時數(shù)量個數(shù)據(jù)記錄項，用于協(xié)調(diào)算法更新等待中的任務狀態(tài)。

時隙協(xié)調(diào)時，先處理鏈表中的高優(yōu)先數(shù)任務，然后再處理低優(yōu)先數(shù)任務，不保旺順序處理（不按照先進先出的方式處理）。

2.2.4時隙的協(xié)調(diào)分配

若時隙申請鏈表REQ_LINK[N]指針非空，根據(jù)互斥關系表Mutex_S2S[N] [N]查找互斥的臺站，建立互斥站時隙分配鏈表Mutex_Link[N]。根據(jù)Mutex_Link[N]中已經(jīng)分配的時隙，計算互斥條件下相應臺站的時隙分配。當沒有時隙可供分配時，否決申請，讓提出時隙申請的臺站等待。

若時隙分配成功，將批準的時隙申請發(fā)送給申請者，并更新全局的時隙分配表并通知存所有臺站更新本地的全局時隙分配表。

2.2.5時隙的協(xié)調(diào)分配的優(yōu)化計算

集中式的時隙協(xié)調(diào)分配優(yōu)化，采用動態(tài)規(guī)劃方法。在給定時隙的時刻點上，可將動態(tài)規(guī)劃轉(zhuǎn)換為線性規(guī)劃。

一般的，使用線性規(guī)劃求最優(yōu)解的數(shù)學模型為： AX=b

（3） X>O

（4）

時隙協(xié)調(diào)，在內(nèi)部按照任務的優(yōu)先數(shù)進行動態(tài)計算。一個任務的優(yōu)先數(shù)由以下公式計算得到：P=PTXPD

（5）

式（5）中，P表示優(yōu)先數(shù)，PT表示任務優(yōu)先級，PD表示動態(tài)優(yōu)先數(shù)。

式（5）中動態(tài)優(yōu)先數(shù)PD由以下公式計算得到：

PD（n）= PD（n-l）X TD

（6）

PD（0）=1+60 000÷NTS

式（6）中，PD（n）表示當蒔狀態(tài)的動態(tài)優(yōu)先數(shù)，PD（n -1）表示前一個狀態(tài)的動態(tài)優(yōu)先數(shù)，TD表示任務等待的延遲時間（時隙數(shù)）。

式（7）中，PD（O）表示初始動態(tài)優(yōu)先數(shù)，NTS表示任務的時隙需求量。

3 集中協(xié)調(diào)方法下網(wǎng)絡崩潰的保護處理

3.1崩潰處理概述

當網(wǎng)絡故障導致集中的協(xié)調(diào)無法完成時，協(xié)調(diào)服務器以及NAVDAT臺站均應對執(zhí)行網(wǎng)絡崩潰的保護處理，存在通信故障的臺站進入故障保護模式。

故障保護模式下，NAVDAT臺站使用事先預先定義的時隙分配方案來自主分配時隙，使存在互斥關系的臺站能夠繼續(xù)互斥地工作。

故障保護模式下的時隙分配方案，是在事先調(diào)查、統(tǒng)計計算的基礎上制定的。與臺站的地理位置、發(fā)射功率、覆蓋范圍、電磁波輻射特性、船舶交通流特性、通航環(huán)境等數(shù)據(jù)以及互斥臺站的特征數(shù)據(jù)有關。

故障保護模式時隙分配方案中，為緊急報文保留時隙，當無緊急的報文傳輸任務時，其他任務可以占用這些保留的時隙。

兩個NAVDAT互斥臺站，故障保護模式時隙分配方案中的時隙分配采用平均分配的方法（見圖1）。平均時隙分配方案的最小時隙數(shù)為400 （400 ms），至少保證搜救以及告警信息等重要的任務能在Is的任務響應時間內(nèi)完成。

3.2臺站的網(wǎng)絡崩潰處理

網(wǎng)絡通信朋潰的NAVDAT臺站，在本地從緩沖的歷史全局時隙分配表中，了解互斥臺站的己分配時隙。通過互斥等待歷史已分配時隙的工作完成后，臺站進入故障保護模式，使用預先定義的時隙分配方案使用發(fā)射時隙。

在故障保護模式下，時隙的批準由本地完成，不再尋求協(xié)調(diào)服務器的幫助。

通信恢復后，自動向協(xié)調(diào)服務器報告故障期間的時隙分配狀態(tài)，之后，臺站自動退出故障保護模式，時隙申請的批準由協(xié)調(diào)服務器來執(zhí)行。

3.3協(xié)調(diào)服務器的網(wǎng)絡崩潰處理

當某個NAVDAT臺站出現(xiàn)網(wǎng)絡通信故障時，等待互斥臺站的己分配時隙完成后，協(xié)調(diào)服務器使用預先定義的時隙分配方案進行時隙分配。

通過預先定義的時隙分配方案，為存在通信故障的NAVDAT臺站保留時隙，可以保證其他臺站的時隙分配能夠正常工作。

通信恢復后，協(xié)調(diào)服務器收到故障期間的實際時隙分配結(jié)果后，更新全局狀態(tài)。并取消內(nèi)部為該站的保留預分時隙。

4 協(xié)調(diào)通信

4.1時隙協(xié)調(diào)通信概述

全局集中協(xié)調(diào)的時隙分配方法，依賴于臺站與協(xié)調(diào)服務器之間的可靠通信。在系統(tǒng)構架以及設計通信子系統(tǒng)時，重點考慮到以下幾個方面的問題：（1）時隙申請的通信協(xié)議。（2）時隙分配結(jié)果（批準申請）的傳輸?shù)耐ㄐ艆f(xié)議。（3）全局時隙分配表更新的通信協(xié)議。（4）全局狀態(tài)一致性。（5）數(shù)據(jù)復制與一致性。

4.2全局狀態(tài)一致性

為保證網(wǎng)絡通信中斷條件下系統(tǒng)仍能夠正確運行（降額），NAVDAT臺站使用時隙協(xié)調(diào)服務器全局時隙分配表的副本。當全局時隙分配表發(fā)生變更時時，更新消息將發(fā)送給所有臺站。NAVDAT臺站可通過查詢時隙協(xié)調(diào)服務器的全局時隙分配表來主動進行本地副本的同步。

NAVDAT系統(tǒng)是一個以網(wǎng)絡通信為基礎的分布式系統(tǒng)。分布式系統(tǒng)的一個敏感問題就是全局狀態(tài)一致性。

全局狀態(tài)不一致問題，主要是關于傳輸途中的時隙資源的描述。因此，將傳輸途中的時隙資源視為一種標記，僅在傳輸開始和傳輸結(jié)束的時刻進行一致性處理。

如圖2所示，傳輸途中的時隙資源d是一種獨立的資源。傳輸開始時，時隙協(xié)調(diào)服務器G不再認為該資源d屬于自己，將其標記“待定”。傳輸結(jié)束時，根據(jù)傳輸?shù)慕Y(jié)果進行一致性處理，當傳輸成功，傳輸途中的時隙資源d歸屬于接收方B，將“待定”資源刪除；傳輸失敗，傳輸途中的時隙資源d被時隙協(xié)調(diào)服務器回收，將“待定”標記取消。

為保證分布式系統(tǒng)各進程通信及事務處理邏輯正確、結(jié)果一致，NAVDAT系統(tǒng)的使用時間戳來標記事件的發(fā)生時刻以及數(shù)據(jù)打包傳輸?shù)臅r刻。

4.3臺站與時隙協(xié)調(diào)服務器的通信

4.3.1時隙申請與批準

NAV DAT發(fā)射臺站申請時隙，需要向時隙協(xié)調(diào)服務器遞交申請。時隙協(xié)調(diào)服務器收到申請時將反饋ACK確認回執(zhí)（見圖3）。

時隙協(xié)調(diào)服務器處理臺站提交的時隙申請，若具有可分配的時隙并滿足申請的時隙需求，將批準申請并分配時隙資源；若無法滿足申請的時隙需求，將拒絕申請。無論批準還是拒絕NAVDAT臺站的時隙申請，都視為時隙分配的結(jié)果，時隙協(xié)調(diào)服務器將把時隙分配的結(jié)果發(fā)送到申請方。

4.3.2全局時隙分配表更新

當時隙協(xié)調(diào)服務器批準一個時隙申請時，全局時隙分配表發(fā)生更新。這個更新的狀態(tài)變化需要通知所有NAVDAT臺站。這樣才能保證故障保護模式下，己分配的時隙繼續(xù)有效，不會被通信故障狀態(tài)的NAVDAT臺站破壞。

當全局時隙分配表更新后，時隙協(xié)調(diào)服務器首先向受影響的NAVDAT臺站播發(fā)更新消息，然后向其他站播發(fā)消息。

時隙協(xié)調(diào)服務器發(fā)送給任何NAVDAT臺站的更新消息都需要相應臺站的ACK確認回執(zhí)。

5 分級的集中協(xié)調(diào)

在分級的集中時隙協(xié)調(diào)中，低層級的時隙協(xié)調(diào)服務器向高層級的時隙協(xié)調(diào)服務器申請時隙資源，處理邊界上的時隙互斥分配。

對于低層級的時隙協(xié)調(diào)服務器來講，邊界區(qū)域互斥NAVDAT臺站的時隙申請被提交到高層級的時隙協(xié)調(diào)服務器。本層級的其他NAVDAT臺站的時隙申請，受到這些邊界互斥臺站己分配時隙的約束。

高層級的時隙協(xié)調(diào)服務器協(xié)調(diào)低層級系統(tǒng)邊界互斥臺站的時隙申請，而不是低層級所有臺站的時隙申請（見圖4）。

高層級的全局時隙分配表，是低層級全局時隙分配表的一個約束，邊界上的變化保持全局一致。

6 結(jié)語

利用本文所述的集中協(xié)調(diào)方法，能夠解決臺站交叉覆蓋時的時隙沖突干擾，并能使整個系統(tǒng)的利用效率達到最大化。通過故障保護模式下的時隙分配方案，能夠消除集中協(xié)調(diào)應用中網(wǎng)絡通信中斷的影響，使各NAV DAT臺站的發(fā)射既高效又可靠，無時隙沖突干擾。該方法可分級實施，組建由地區(qū)到國家時隙集中協(xié)調(diào)，進而組建國際級的時隙集中協(xié)調(diào)。保證所有的NAVDAT臺站發(fā)射時隙無沖突。

[1]ITU.Utilization of the 495-505 kHz band by the maritime mobile service for the digital broadcasting of safety and security relatedinformation from shore-to-ships[R].Report ITU-R M.2201， 2010.

[2]ITU.Characteristics of a digital system，named Navigational Data for broadcasting maritime safety and security related information fromshore-to-ship in the 500 kHz band[R].Recommendation ITU-R M.2010， 2012.