基于空间分布的数据链动态导航时隙分配算法

粟博文 丛丽 汪翔

1.北京航空航天大学电子信息工程学院北京100190 2.广州虎牙信息科技有限公司广东广州510000

数据链是一种在多军联合作战中实现态势估计、精确指挥控制和战术协同的通信链路系统.目前军用较为广泛的Link16 数据链以时分多址(Time Division Multiple Access,TDMA)为基础,采用RS 编码、数据交织、直接序列扩频、跳频、跳时等技术,具有极强的保密抗干扰性能.作战环境中,其可以容纳大量成员,充分利用整个战场的信息资源,实现多平台的联合作战,发挥整体最大的作战能力[1].

现有数据链通常是采用时分多址接入方式.基于TDMA 体制的数据链系统具有良好的抗截获、抗干扰能力,广泛应用于军用系统中.TDMA 的接入协议主要研究多节点之间的时间分配问题,也称为时隙分配协议问题.

相对导航是数据链的一项重要功能,各作战单元之间相对位置的确定是完成协同作战任务的关键.在相对导航中普遍采用卡尔曼滤波作为滤波估计算法,当系统为线性且噪声统计特性满足高斯分布时卡尔曼滤波是最小方差估计器[2].由于武器装备的发展和战场环境的愈加复杂、数据链中成员的动态性不断提高、成员出入网更为频繁等因素,传统的数据链导航时隙分配设计已经不能满足相对导航定位性能的需求.

现有的时隙分配方式分为3 种,固定时隙分配、动态时隙分配和混合时隙分配.

固定时隙分配协议一般根据时隙需求的节点数量提前划分时隙,在时隙充足(或者说节点不多)的情况下可以满足需求.如果没有针对不同节点的通信需求进行合理的资源划分,会导致资源浪费或效率低下.有研究表明最优固定时隙分配问题被认为是经典的NP 完备问题[3-4],因此,一般研究都是尽量寻求较优解,常用的方法大都基于启发式算法[5],如均域退火算法[6]、有序节点染色算法[7]、基于神经网络和遗传算法的时隙分配算法[8]等.

这些固定分配方式的效果可能随着系统环境的动态变化而变差.动态时隙分配的概念主要是相对于静态分配而言,可灵活根据时隙需求调整时隙的分配.

都柏林城市大学的VENKATARAMAN 等提出将每个时隙划分成几个小时隙来增加可用的带宽资源,不同用户分配不同数量的小时隙的动态时隙分割(DTSP)算法[9].曼尼托巴大学的SHRESTHA B提出了一种基于动态队列长度的混合CSMA/TDMA的时隙分配方案,考虑到队列长度的不确定性,提高了信道利用率[10].克利夫兰州立大学的UNK N 提出一种基于介质访问控制的节点动态分配机制,能够避免网络拥塞,提高网络吞吐量[11].在韩国国家基金研究会资助下LEE K 等提出了基于时分多址网络的基于中继的定位方法.其中用于广播导航信号和中继接收消息的时隙被连续地分配以在TDMA 网络应用中继概念,减少时隙间隔期间成员动态性产生的影响[12].

混合时隙分配算法综合前两者的优点,有研究表明综合利用多种接入协议可以提高系统的效率[13-14],典型的混合时隙分配算法思想是一部分节点固定时隙分配,另一部分节点动态时隙分配.具有代表性的混合时隙分配方式有PTDMA协议[15]、ABROAD 协议[16]、Z-MAC协议[17].

可见时隙分配方式的研究大都集中将时隙资源进行合理的划分,使网络中的节点分别占用不同的时隙,在避免了相邻节点之间播发消息的碰撞的同时使网络有较高的通信质量和较大的通信容量[18],从导航定位性能角度进行时隙分配的研究较少,如忠南大学LEE J H 等的研究.他们设计了一个基于Link16 相对导航系统性能分析平台并根据不同时隙分配顺序观察系统成员在同一参考位置下相对导航性能表现[19].

本文在Link16 数据链基础上,提出了一种基于导航源空间分布的数据链动态时隙分配算法,通过计算导航源与成员的方位角,动态地调整成员导航时隙来提高网络整体的相对导航精度.

1 数据链相对导航及时隙分配原理

1.1 数据链相对导航定位

数据链通常指定一个成员作为导航控制者(Navigation Controller,NC)建立起整个网络的相对坐标系,以时间基准的时间为网络时间,以地理基准的位置为网络的准确地理位置,如图1所示为以Link16 数据链为基础的网络示意图.

相对导航定位就是实时确定网中成员在该相对坐标系中的位置.这对集团作战而言,比准确的地理位置更加重要.

为保证系统正常工作,各成员间应保持时间同步.当一个用户接收到另一个作为源的成员辐射的信号时,通过测量出信号传输时间可以得知两者之间的距离.同时,在用户接收这一源的信号时,在其信息段内传送有这一源的位置数据.这样,用户根据源的位置数据和测出的距离,可以确定出自己处在的以源为中心的球面,对3 个不同的源可确定3 个具有不同球心和半径的圆球位置面,原理上这样3 个位置面的交点就是用户在三维空间中的位置.

在时分多址工作的情况下,各源是按一定的时间顺序轮流辐射的,并且源和用户都是在运动着的,不可能在同一时刻同时测出到3 个源的距离.因此,采用卡尔曼滤波技术,按照成员运动规律外推下一滤波时刻的位置,用测距信息对位置进行修正.经过多次测量,逐步修正,就可得到精度较高的用户实时位置.

图1 一种数据链网络

实现导航定位功能的工作原理是将导航源和成员之间测得的TOA 值和P 消息(包含导航源位置信息)中源的状态数据,或有源校时得到的导航源与成员时钟的钟差,气压高度表测量的气压高度,加上惯导系统(Inertial Navigation System,INS)测定的用户位置等,一并输入导航信息处理器中,在其中将这些观测数据结合用户(或INS)的运动动力学方程,用卡尔曼滤波定位算法,先计算用户预测状态值和信息,然后计算预测状态的协方差阵和增益矩阵,最后进行滤波修正,得到滤波估计值及其协方差阵.随着新的测量值的不断输入,计算过程循环进行,不断进行滤波估计,得到状态量的估计值和状态量的协方差矩阵.具体工作原理如图2所示.

1.2 数据链时隙分配原理

数据链网络采用时分多址的接入方式,即将时间轴分成一个个等长的片段,每个片段分给一个成员播发消息,其他成员在这个片段中只能接收消息.借鉴Link16 数据链时间系统,将时间轴从大到小依次分成周期、帧、时隙,时隙即为分给单个成员的片段.周期、帧、时隙长度以及时隙的组成如图3所示.

其中每个周期的长度是12.8 min.一个周期可以分为长度为12 s 的64 个帧,每一个帧又可以分为长度为7.812 5 ms 的1 536 个时隙,每一个时隙分为3.354 ms 信息段和4.458 5 ms 的时间保护段.时隙指定播发信号的成员在信息段中播发信号,信号保护段用来保证下一个时隙开始前本时隙内播发的信号已到达所有接收信号的成员.

各成员按照时隙分配表在规定的时隙中播发自身消息,但数据链网络中大多数时隙是用于通信信息的交互.抽取少部分时隙作为导航时隙,播发导航定位需要的P 消息.

P 消息采用特定的信号格式,其中包含导航定位需要的基本信息,具体包括位置信息、速度信息、角度信息、高度信息、导航源位置质量和导航源时间质量等,如图4所示.

以Link16 数据链为基础从导航性能角度分析时隙分配方法,数据链时隙分配通常也可分为混合时隙分配、固定时隙分配和动态时隙分配.混合时隙分配是指部分特殊身份的成员时隙固定,余下时隙采用动态方式分配给其他成员.固定时隙分配是指成员按照预先设计好的时隙分配表依次获得时隙.动态时隙分配是指网络所有成员的时隙分配表是可以变动的,在网络运行过程中可以重新分配时隙的所有权.

动态时隙分配可以依照导航源空间分布、质量等因素调整时隙分配表,从而提高数据链的导航定位精度.

2 数据链动态时隙分配

2.1 动态时隙分配原则

在数据链相对导航定位中,定位精度与成员自身传感器精度、导航源误差和导航源空间分布相关.为了提高导航定位精度,成员在接收到导航源的P消息后,根据导航源位置质量以及时间质量信息,选择导航源进行定位.在导航源位置质量和时间质量一定的情况下,成员定位精度主要受导航源空间分布的影响.因此,本文提出的动态时隙分配的原则是改善导航源的空间分布.

图2 数据链网络相对导航工作原理图

图3 系统的时间结构

图4 P 消息结构

动态数据链网络中导航源可以视为卫星定位中的卫星,因此,导航源的空间分布采用卫导中的精度因子(Dilution of precision,DOP)来描述,DOP值越小表示导航源空间分布越好.

在动态数据链相对导航中,高度方向使用气压高度表的结果进行约束,因此,计算空间分布只需要获得导航源的二维平面坐标,则权系矩阵H和水平位置精度因子(Horizontal dilution of precision,HDOP)的表达式如下:

从式(1)可以看出,在计算单个成员的HDOP时,权系矩阵H中的值只与各导航源与成员的方位角αi有关系,当α1,α2,···,αi满足一定关系时,HDOP的值较小,从而具有较好的空间分布.因此通过分析导航源方位角的大小与HDOP的关系,使用相邻导航源与成员的夹角作为判断导航源对该成员空间分布好坏的标准.

1)当导航源数目为2 个时,假设第1 个导航源到成员的方位角为0°,第2 个导航源到成员的方位角为α.HDOP表达式为:

易得当α=90°时,HDOP最小,空间分布最好,随着α 的减小或者增大,HDOP都会逐渐增大空间分布变差.

2)当导航源数目为3 个时,假设第1 个导航源到成员的方位角为0°,第2 个导航源到成员的方位角为α,第3 个导航源到成员的方位角为β.HDOP表达式为:

从式(4)可以看出当α=60°,β=120°时,HDOP最小,空间分布最好,随着α、β 的减小或者增大,HDOP都将增大,空间分布变差.

3)当导航源数目为4 个时,设一个导航源的方位角为0°,一个导航源的方位角为α,一个导航源的方位角为β,一个导航源的方位角为γ.假设α、β、γ的大小成等差数列,α=θ,β=2 θ,γ=3 θ.成员的权系矩阵H表达式如式(5),HDOP的表达式如式(6).

图5 导航源最优空间分布图

当sin2θ=0.5 时,HDOP最小,此时α=45°,β=90°,γ=135°.

固定α,β,改变γ,即γ=(135+σ)°,将α,β,γ 的值代入式(6)得

当σ=0°时HDOP取最小值.同理依次固定α和γ、β 和γ,可以得α=45°,β=90°,γ=135°时HDOP最小.

通过上述分析可知导航源与成员的HDOP最小,导航源二维最优空间分布如图5所示.

2.2 动态时隙分配算法设计

采用导航源的方位角大小作为动态时隙分配算法的准则,进而决定哪些成员作为导航源以及导航源成员按照怎样的顺序播发消息.

在动态时隙分配算法中选择连续n个导航源计算成员的HDOP值,如果n的值选择太大,那么统一到同一个时刻的导航源就较多,最先播发消息的导航源和最后一个导航源之间的时间间隔会较大.动态数据链网络导航源的动态性很高,太长的时间间隔会使HDOP计算不准确.如果n的值太小则不能反映一段时间内导航源的空间分布对定位结果的影响.综合考虑上述因素使用连续4 个时隙的导航源计算HDOP.

2.2.1 单成员动态时隙分配

单成员动态时隙分配算法针对单个成员的空间分布设计出较好的时隙分配表.由导航源方位角与HDOP的关系可得,当相邻源与成员构成的方位角为45°时,HDOP最小,空间分布最好.

单成员动态时隙分配算法具体流程如下:

1)建立导航源备选集合包含所有的可以作为导航源的成员.

2)第1 个时隙导航控制者播发消息.

3)计算导航源备选集合中剩下的所有导航源与前一个时隙的导航源与待定位成员构成的方位角,方位角最接近45°的导航源作为当前时隙的导航源.

4)在导航源备选集合中删去该导航源,在时隙分配表中加入该导航源,时隙递增,返回第3 步,直到时隙分配表填满时停止循环.

5)在新的一帧中按照新建立的时隙分配表播发消息.

单成员动态时隙分配算法流程图如图6所示.

图6 单成员动态时隙分配算法流程图

2.2.2 全网动态时隙分配

全网动态时隙分配算法针对全网所有成员设计出较好的时隙分配表.因此,对全网成员来说,需要让相邻导航源对尽可能多的成员夹角接近45°.设置一个角度范围,统计相邻导航源与其他所有成员的夹角在这个范围内的成员个数.这样就可以选择出相对大多数成员具有较好空间分布的导航源.具体的全网动态时隙分配算法如下:

1)建立导航源备选集合包含所有的可以作为导航源的成员.

2)时隙分配表第1 个时隙导航控制者播发消息.

3)计算导航源备选集合中剩余导航源与前一个时隙的导航源与所有成员构成的方位角,记录方位角在指定范围内的次数.选择次数最多的导航源作为当前时隙的导航源,插入时隙分配表.

4)在导航源备选集合中去掉该导航源,在时隙分配表中加入该导航源,时隙递增,返回第3 步,直到时隙分配表填满时停止循环.

5)在新的一帧中按照新建立时隙分配表播发消息.

图7 全网动态时隙分配算法流程图

3 仿真及结果分析

3.1 单成员动态时隙分配仿真及分析

使用140 个成员进行组网仿真,在动态时隙分配算法中设置导航源备选集合包括序号1 ～64 的64个成员,时隙分配表长度为50,即每一帧开始时从64个备选导航源里选出对指定成员空间分布较好的50个导航源创建时隙分配表.

分别对一级成员中的21号成员和二级成员中的76号成员采用单成员动态时隙分配算法,成员传感器参数设置如表1所示.成员运动轨迹为前50 s为匀速直线运动,后50 s 为半径10 000 m 的圆周运动.采用单成员动态时隙分配算法前后成员东北天3个方向的位置误差比较曲线如图8、图9所示,统计结果如表2所示.

表1 系统参数设置

表2 有无动态时隙分配位置误差统计结果

1)采用单成员动态时隙分配算法后,21号成员和76号成员在经度和纬度方向的定位误差都大大减小.21号成员三维定位误差从67.8 m 下降到26.3 m,定位精度提升了61.2%,76号成员三维定位误差从174.1 m 下降到113.7 m,定位精度提升了34.7%.

2)高度方向使用高度表结果进行约束,设计的动态时隙分配算法不考虑高度方向,因此,成员在高度方向定位精度无明显提升.

图8 21号成员有无动态时隙分配定位结果比较图

图9 76号成员有无动态时隙分配定位结果比较图

3.2 全网动态时隙分配仿真及分析

使用140 个成员进行组网仿真,在动态时隙分配算法中设置导航源备选集合包括序号1 ～64 的64个成员,时隙分配表长度为50,相邻导航源与成员的方位角的选择范围是30°～60°.每一帧开始时从64个导航源备选集合里选出对最多数目的成员空间分布较好的50 个导航源创建时隙分配表.

采用全网动态时隙分配算法前后,分别统计网络内一级成员和二级成员的三维定位误差均值,如图10、图11所示.

图10 一级成员有无动态时隙分配定位结果比较图

1)使用全网动态时隙分配算法后,全网成员的定位精度整体得到提高.其中一级成员平均定位误差从42.4 m 下降到31.7 m,定位精度提高了25.3%,二级成员的平均定位误差从130.5 m 下降到92.1 m,定位精度提高了29.5%.

2)全网动态时隙算法并不是使所有成员精度都得到提高,使用全网动态时隙分配算法后9号、18号、93号等成员定位精度下降.

3)由于一级成员有RTT 校时并且具有较高的时间质量和位置质量,无论是否采用动态时隙分配,相较二级成员都具有较好的定位精度.

4)将全网动态时隙分配算法与单成员动态时隙分配算法定位结果进行比较,可以看出在全网动态时隙分配算法下21号成员定位精度提高了23.4%,76号成员的定位精度提高了29.7%,均低于采用单成员动态时隙分配算法精度的提升.

图11 二级成员有无动态时隙分配定位结果比较图

4 结论

为了提高数据链网络内成员整体的相对导航精度,在不考虑高度方向精度调整下,本文提出一种基于导航源空间分布的数据链动态导航时隙分配算法,并使用导航源方位角表征导航源空间分布,针对全网和单成员设计了不同的动态时隙分配算法.仿真结果表明,使用单成员动态时隙分配算法后,单成员的定位精度得到比较大的提高；全网动态时隙分配算法对单个成员的定位精度不如单成员动态时隙分配算法,但能够使网络内成员的整体定位精度得到提高.