NAVDAT台站发射时隙集中协调与实现

彭树林 汤可成 高万明 王翔

摘 要：文章针对NAVDAT数据传输系统，研究时隙的分配及协调方法，实现了一种集中协调的时隙分配方案，能够最大限度地利用所有带宽资源传输数据。

关键词：NAVDAT；发射时隙：协调

采用64QAM调制的NAVDAT数据链路，以500 kHz的发射频率，在100～200海里的范围内为船载移动终端提供19～28 kbps的下行数据服务，使航行警告信息、气象传真图以及海图更新等能够及时播发到船舶终端[1]。

由于无线电传播距离受发射时的电磁环境影响较大，各NAVDAT台站的覆盖可能交叉重叠，且可能重叠的范围大小变化。并且在解决全区域覆盖时，采用时分或单频网络的方式来实现[1]。由于NAVDAT使用的频点是固定的，为了避免电台间的发射干扰（64QAM对干扰比较敏感），必须保证各个交叉覆盖的NAVDAT台站传输数据的时隙互斥。

本文针对NAVDAT数据传输系统，研究时隙的分配及协调方法，实现了一种集中协调的时隙分配方案，能够最大限度地利用所有带宽资源传输数据。

本文所述的方法，采用动态规划的方法对时隙进行全局优化，通过一个全局时隙分配表，将各NAVDAT发射台的发射协调到总带宽最大的状态。

1 时隙协调技术

1.1时隙协调的目的和意义

NAVDAT数据传输系统，在不同地理空间时分复用相同的频点，传输不同的业务数据。在保证不相互冲突的情况下，尽可能使每个NAVDAT台站的每个可用时隙资源都被利用。

時隙协调的目的在于最大限度利用各台站的时隙资源来传输数据，使系统的总带宽达到最大的状态。

时隙协调的重要意义在于，通过时隙协调，高优先级报文及时播发的同时，支持多种低优先级报文“同时”传输。在一个窄带的数据链路上“同时”承载多种业务数据。通过时隙协调，航行告警、气象传真、海图更新都能够在短时间内快速完成。

1.2时隙协调的评价指标

确立时隙协调效果的评价指标，对系统的方案设计、优化、评审以及时隙协调的优化算法开发都有指导意义。

优化算法需要优化的目标函数，在NAVDAT数据传输系统中，目标是可用传输带宽最大。可用传输带宽是各个NAVDAT发射台站，在，时刻所有可使用带宽之和。

1.3集中时隙协调方法

NAV DAT系统的集中协调方法，将系统中每个NAVDAT台站的发射时隙视为可调度、可分配的“资源”，称为“时隙资源”。该方法将任何一个NAVDAT台站所需要的时隙资源进行统一的协调分配，对不存在交叉覆盖的台站，按需自由分配时隙资源；对两个或两个以上存在重叠覆盖区域的NAVDAT台站，采用时隙互斥的分配机制来避免重叠覆盖区域的干扰。在此基础上，通过进行全局优化的时隙资源分配方法，使系统的无线带宽资源利用率达到最大。

1.4集中时隙协调过程

首先，NAVDAT台站将数据传输的任务载荷经过包拆分，变为若干待数据块，每个数据块具有应用识别码以及序列号。将这些数据块按序号编成一个数据传输任务的队列。

再次，NAVDAT台站向协调服务器申请发射时隙，在申请时应当向协调服务器说明任务的优先级PT、数据发送所需的时隙数NTS。 接下来，协调服务器根据申请，进行全局优化计算时隙的分配结果，并将时隙分配结果发送给申请时隙的台站。时隙分配的结果分为两种：批准时隙、拒绝申请。

最后，申请时隙的台站，根据批准的时隙安排数据的传输，将传输任务队列转移到发射队列，等待自动发射。若申请被否决，应等待60 s后尝试重新申请。

若申请过程中协调服务器的响应超时，应尝试5-7次，间隔时间为10～30s。若尝试5-7次仍然失败，就激活故障保护模式，以故障保护方式自授权发射时隙。

1.5基本技术术语定义

1.5.1时隙

将每分钟的60 s，等分为2 250个时隙，每个时隙为26.667 ms （NAVDAT的OFDM调制的每个符号长度24 ms及其保护长度2.667 ms合计26.667 ms）。

1.5.2时隙协调服务器

时隙协调服务器接受NAVDAT台站的时隙申请并为其分配所需时隙，并实现时隙优化。

1.5.3数据传输任务

等待传输的数据源构成一个数据传输任务，具有应用分类识别码及优先级等属性。

1.5.4任务队列

数据传输任务的数据源，经过拆分为若干数据块并加上包头，构成一系列用于传输的数据包序列，等待分配时隙逐个传输。这些数据包就构成数据传输的任务队列。

1.5.5发射队列

当任务队列的包被批准后，就从任务队列转移到发射队列，在批准的时刻进行传输。

1.5.6消极站与积极站

一个NAVDAT台站，若发射队列为空，称为消极站，否则称为积极站。

1.5.7待协调站和休眠站

一个NAVDAT台站，若任务队列都不为空，称为待协调站。待协调站会主动向协调服务器申请时隙，将待传输的数据传输到移动终端。

一个NAVDAT台站，若发射队列和任务队列均为空，称为休眠站。休眠站不占用任何资源，优化算法的计算过程中，忽略休眠站。

1.5.8全局时隙分配表

全局时隙分配表是一张时隙资源的描述表，该表用于描述NAVDAT系统中每个台站未来各个时隙的分配状况。当时隙分配导致表格内容发生变化，时隙协调服务器将广播这个变化，使全局时隙分配表在各个NAVDAT台站的副本进行同步。

1.5.9全局瞬时带宽

任意时刻t，所有积极站的带宽之和，即，时刻的可用传输带宽之和。

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

（1）

式（1）中，A/（t）是第i个NAVDAT台站状态的二值函数，积极站是取值为l，消极站取值为0。bi（t）是第i个NAVDAT台站在t时刻的带宽，与其调制模式有关。取值为以下值之一：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时隙协调方法

2.1时隙协调规则

（1）两个不相互交叉覆盖的NAVDAT台站，可以使用重叠的发射时隙。

（2）两个相互重叠覆盖的NAVDAT台站，使用的发射时隙必须互斥，不可使用重叠的发射时隙。

（3）两个相互重叠覆盖的NAVDAT台站，发射任务饱满时，一般也不采用平均分配策略来分配时隙，要考虑任务的优先级及数据的长度。

（4）台站内部可根据自行调整己分配的时隙，将高优先级的任务所获得的时隙在发射队列中与其他低优先级任务的发射时隙交换，以便实时完成航行警告等高优先级的数据传输任务。

（5）全局优化的指标。全局优化时，不仅要考虑全局瞬时带宽的最大化，还要考察各个NAVDAT台站任务饱和时的平均帶宽最大化（按优先级）。

全局优化时，采用以下两个指标：（1）全局瞬时带宽最大，MAX[B（t）]。（2） NAVDAT台站平均带宽最大，MAX[B/*（t1，t2）]。

2.2 NAVDAT台站发射时隙协调算法

NAVDAT台站发射时隙仂调算法是一种合作分配算法，借助动态规划手段进行全局优化。并采用全局一致的故障保护模式处理网络通信故障。

2.2.1初始条件 时隙分配表TS[N][60000]清零，表示所有站的所有时隙未分配。故障保护模式时隙分配表TSE [N][60000]初始化，装入预设值。表格Distance_S2S[N][N]装入预设值，表示台站之间的空间最短距离。

2.2.2限制条件

时隙分配的限制条件主要包括台站与台站的时隙互斥关系、任务的优先级以及任务的时隙需求量等。

（1）台站与台站的时隙互斥关系。特定条件下NAVDAT台站间的互斥关系，由台站的覆盖距离以及台站到台站的最短空间距离共同决定。若某个NAVDAT台站的覆盖距离因电磁环境或发射机功率出现调整或台站的发射模式改变，需要重新计算台站与台站的时隙互斥关系。计算结果存放到互斥关系表Mutex_S2S[N] [N]中，以便控制时隙分配。

台站到台站的最短空间距离由表格Distance_S2S[N][N]决定，初始化时装入预设值。表示任意两个NAVDAT台站发射天线之间的空间最短距离（曲线距离而非直线距离）。

台站的覆盖距离由发射功率、天线辐射效率、天线安装高度、地理位置以及天气条件等因素共同决定，不是一个精确值，只是一个大概数。由计算调整结果存入表格Coverage[N]。若NAVDAT台站发射电磁波的电磁环境发生较大变化，或则发射机输出功率出现调整，或台站的发射模式改变，都需要重新计算台站的覆盖距离。

（2）任务的优先级PT。任务的优先级决定时隙分配的优先程度。当一个高优先级的数据传输任务（例如搜救信息播发）需要立即执行时，时隙协调的分配算法必须马上安排发射时隙。

（3）任务的时隙需求量NTS。对数据传输任务的数据量没有限制，但在申请时隙时，需要申明所需要的时隙数，即时隙需求量。223时隙申请链表

时隙申请链表REQ_LINK[N]记录各个NAVDAT台站提出的申请中未处理的申请链表。当REQ_LINK[N]为空指针（NULL）时，表示第N个NAVDAT台站的申请已处理完毕。

台站申请时隙，会动态生成一个申请表REQ，在REQ中记录任务的优先级、所需的时隙数，还有一个链表指针指向该NAVDAT台站的下一个申请表。申请表插入在时隙申请链表REQ_LINK[N]对应台站链表的尾部。申请表REQ中还包含动态优先数和等待延时数量个数据记录项，用于协调算法更新等待中的任务状态。

时隙协调时，先处理链表中的高优先数任务，然后再处理低优先数任务，不保旺顺序处理（不按照先进先出的方式处理）。

2.2.4时隙的协调分配

若时隙申请链表REQ_LINK[N]指针非空，根据互斥关系表Mutex_S2S[N] [N]查找互斥的台站，建立互斥站时隙分配链表Mutex_Link[N]。根据Mutex_Link[N]中已经分配的时隙，计算互斥条件下相应台站的时隙分配。当没有时隙可供分配时，否决申请，让提出时隙申请的台站等待。

若时隙分配成功，将批准的时隙申请发送给申请者，并更新全局的时隙分配表并通知存所有台站更新本地的全局时隙分配表。

2.2.5时隙的协调分配的优化计算

集中式的时隙协调分配优化，采用动态规划方法。在给定时隙的时刻点上，可将动态规划转换为线性规划。

一般的，使用线性规划求最优解的数学模型为： AX=b

（3） X>O

（4）

时隙协调，在内部按照任务的优先数进行动态计算。一个任务的优先数由以下公式计算得到：P=PTXPD

（5）

式（5）中，P表示优先数，PT表示任务优先级，PD表示动态优先数。

式（5）中动态优先数PD由以下公式计算得到：

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

（6）

PD（0）=1+60 000÷NTS

式（6）中，PD（n）表示当莳状态的动态优先数，PD（n -1）表示前一个状态的动态优先数，TD表示任务等待的延迟时间（时隙数）。

式（7）中，PD（O）表示初始动态优先数，NTS表示任务的时隙需求量。

3 集中协调方法下网络崩溃的保护处理

3.1崩溃处理概述

当网络故障导致集中的协调无法完成时，协调服务器以及NAVDAT台站均应对执行网络崩溃的保护处理，存在通信故障的台站进入故障保护模式。

故障保护模式下，NAVDAT台站使用事先预先定义的时隙分配方案来自主分配时隙，使存在互斥关系的台站能够继续互斥地工作。

故障保护模式下的时隙分配方案，是在事先调查、统计计算的基础上制定的。与台站的地理位置、发射功率、覆盖范围、电磁波辐射特性、船舶交通流特性、通航环境等数据以及互斥台站的特征数据有关。

故障保护模式时隙分配方案中，为紧急报文保留时隙，当无紧急的报文传输任务时，其他任务可以占用这些保留的时隙。

两个NAVDAT互斥台站，故障保护模式时隙分配方案中的时隙分配采用平均分配的方法（见图1）。平均时隙分配方案的最小时隙数为400 （400 ms），至少保证搜救以及告警信息等重要的任务能在Is的任务响应时间内完成。

3.2台站的网络崩溃处理

网络通信朋溃的NAVDAT台站，在本地从缓冲的历史全局时隙分配表中，了解互斥台站的己分配时隙。通过互斥等待历史已分配时隙的工作完成后，台站进入故障保护模式，使用预先定义的时隙分配方案使用发射时隙。

在故障保护模式下，时隙的批准由本地完成，不再寻求协调服务器的帮助。

通信恢复后，自动向协调服务器报告故障期间的时隙分配状态，之后，台站自动退出故障保护模式，时隙申请的批准由协调服务器来执行。

3.3协调服务器的网络崩溃处理

当某个NAVDAT台站出现网络通信故障时，等待互斥台站的己分配时隙完成后，协调服务器使用预先定义的时隙分配方案进行时隙分配。

通过预先定义的时隙分配方案，为存在通信故障的NAVDAT台站保留时隙，可以保证其他台站的时隙分配能够正常工作。

通信恢复后，协调服务器收到故障期间的实际时隙分配结果后，更新全局状态。并取消内部为该站的保留预分时隙。

4 协调通信

4.1时隙协调通信概述

全局集中协调的时隙分配方法，依赖于台站与协调服务器之间的可靠通信。在系统构架以及设计通信子系统时，重点考虑到以下几个方面的问题：（1）时隙申请的通信协议。（2）时隙分配结果（批准申请）的传输的通信协议。（3）全局时隙分配表更新的通信协议。（4）全局状态一致性。（5）数据复制与一致性。

4.2全局状态一致性

为保证网络通信中断条件下系统仍能够正确运行（降额），NAVDAT台站使用时隙协调服务器全局时隙分配表的副本。当全局时隙分配表发生变更时时，更新消息将发送给所有台站。NAVDAT台站可通过查询时隙协调服务器的全局时隙分配表来主动进行本地副本的同步。

NAVDAT系统是一个以网络通信为基础的分布式系统。分布式系统的一个敏感问题就是全局状态一致性。

全局状态不一致问题，主要是关于传输途中的时隙资源的描述。因此，将传输途中的时隙资源视为一种标记，仅在传输开始和传输结束的时刻进行一致性处理。

如图2所示，传输途中的时隙资源d是一种独立的资源。传输开始时，时隙协调服务器G不再认为该资源d属于自己，将其标记“待定”。传输结束时，根据传输的结果进行一致性处理，当传输成功，传输途中的时隙资源d归属于接收方B，将“待定”资源删除；传输失败，传输途中的时隙资源d被时隙协调服务器回收，将“待定”标记取消。

为保证分布式系统各进程通信及事务处理逻辑正确、结果一致，NAVDAT系统的使用时间戳来标记事件的发生时刻以及数据打包传输的时刻。

4.3台站与时隙协调服务器的通信

4.3.1时隙申请与批准

NAV DAT发射台站申请时隙，需要向时隙协调服务器递交申请。时隙协调服务器收到申请时将反馈ACK确认回执（见图3）。

时隙协调服务器处理台站提交的时隙申请，若具有可分配的时隙并满足申请的时隙需求，将批准申请并分配时隙资源；若无法满足申请的时隙需求，将拒绝申请。无论批准还是拒绝NAVDAT台站的时隙申請，都视为时隙分配的结果，时隙协调服务器将把时隙分配的结果发送到申请方。

4.3.2全局时隙分配表更新

当时隙协调服务器批准一个时隙申请时，全局时隙分配表发生更新。这个更新的状态变化需要通知所有NAVDAT台站。这样才能保证故障保护模式下，己分配的时隙继续有效，不会被通信故障状态的NAVDAT台站破坏。

当全局时隙分配表更新后，时隙协调服务器首先向受影响的NAVDAT台站播发更新消息，然后向其他站播发消息。

时隙协调服务器发送给任何NAVDAT台站的更新消息都需要相应台站的ACK确认回执。

5 分级的集中协调

在分级的集中时隙协调中，低层级的时隙协调服务器向高层级的时隙协调服务器申请时隙资源，处理边界上的时隙互斥分配。

对于低层级的时隙协调服务器来讲，边界区域互斥NAVDAT台站的时隙申请被提交到高层级的时隙协调服务器。本层级的其他NAVDAT台站的时隙申请，受到这些边界互斥台站己分配时隙的约束。

高层级的时隙协调服务器协调低层级系统边界互斥台站的时隙申请，而不是低层级所有台站的时隙申请（见图4）。

高层级的全局时隙分配表，是低层级全局时隙分配表的一个约束，边界上的变化保持全局一致。

6 结语

利用本文所述的集中协调方法，能够解决台站交叉覆盖时的时隙冲突干扰，并能使整个系统的利用效率达到最大化。通过故障保护模式下的时隙分配方案，能够消除集中协调应用中网络通信中断的影响，使各NAV DAT台站的发射既高效又可靠，无时隙冲突干扰。该方法可分级实施，组建由地区到国家时隙集中协调，进而组建国际级的时隙集中协调。保证所有的NAVDAT台站发射时隙无冲突。

[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.