基于竞争时隙的空间飞行器快速组网策略

宋兆涵，张德智

(中国运载火箭技术研究院，北京 100076)

0 引言

随着航天技术的发展，空间飞行器组网通信模式已经逐步成为了新的研究热点[1]。空间飞行器自组织网络具有极强的自组织、自配置和管理能力，以适应通信任务的变化，增强网络灵活性[2]。当前多数空间飞行器数据链采用预先分配时隙的TDMA 协议和固定时间基准终端进行组网通信，以Link16 数据链为例[3]，要建立网络同步，系统必须单独设定一个终端为网络提供时间基准，这个终端被称为网络时间基准(Network Time Reference，NTR)。由这个选定终端保持的时间定义为系统网络时间。以这个时间为基准,再来定义时隙的起点与终点,并确保多重网络中“时分”的校准[4]。网络时间基准终端周期性地发送入网报文,帮助系统其他终端与网络同步并获得系统时间[5]。在此过程中，若时间基准终端受到打击，丧失通信能力，则组网过程失败[6]。因此，单独设定某一飞行器终端作为NTR 无法保证网络建立过程的可靠性[7]。

同时，对于临时收到组网要求，需要快速建立自组织网络协同执行任务的空间飞行器网络，预先分配时隙的方式显然并不适用[8]。因此，本文设计了一种无初始时隙分配信息且无固定NTR 的飞行器初始组网策略，通过节点竞争占用时隙，完成网络自主的初始时隙分配，保证网络中各节点掌握网络拓扑信息，后续进行稳定通信。在此过程中，节点之间通过信息交互快速完成时钟同步建立网络通信链路，缩短了组网时间，提高了组网灵活性。

1 基于竞争时隙的组网策略设计

1.1 竞争占用时隙

由于各空间飞行器节点在进入网络前并未预先完成时间同步和时隙分配，因此节点需通过竞争的方式占用时隙。在组网过程中，各节点通过竞争过程完成时帧周期内时隙无冲突分配和时间同步，直至所有节点均可稳定占用时隙进行通信，认为组网过程完成。

组网开始时，节点初始化为未分配状态，持续监听信道，节点存储时隙分配表为空，因此时帧中所有时隙均为空闲时隙。空闲时隙到来时，节点有一定的概率P 对当前时隙发起竞争，广播自身拓扑信息和时隙占用信息。

由于网络中无时间基准终端(NTR)，节点在广播时将自身时刻信息写入广播信息告知其他节点，节点根据收到的时刻信息调整自身时间，直至与网络中最晚时刻信息保持一致。由于时帧起始时刻为节点已知信息，因此实际时刻信息最晚的节点最早进入组网进程。在此过程中，不存在一个节点i 作为网络中的NTR，其余节点不需等待节点i 周期性广播完成时间同步，而是通过节点在竞争过程中进行信息交互，不断向较晚时刻信息进行调整，直至完成时间同步。若时刻信息最晚的节点遭受打击，只要其时刻信息已转发至网络中其他节点，则此时刻信息已成为网络中的时间基准，其余节点依旧可以同步至此时刻，网络节点时间同步可照常进行；若其遭受打击前尚未广播时刻信息，则网络时间同步至剩余节点中最晚时刻。时隙竞争流程如图1 所示。

图1 节点竞争时隙流程图

1.2 普通冲突避免机制

各节点在监听过程中，根据收到的广播信息完成时间同步，同时更新自身存储的网络拓扑信息表和时隙分配表。本文所讨论的飞行器自组网场景中，所有飞行器节点相互独立，没有主从之分，各节点独立发起竞争，因此可能存在多个节点在同一空闲时隙同时广播占用信息[9]，因此需建立冲突判决机制。

若多个节点同时对当前时隙发起竞争，当前节点各自的一跳邻节点获得不同的时隙占用信息，并在不同时隙分别广播告知第三方节点，第三方节点先后收到冲突占用信息后采用冲突判决机制判定时隙归属，并更新时隙分配表，将判决结果广播告知网络中其他节点，从而避免时隙重复占用。冲突避免机制如图2 所示。

图2 普通冲突避免机制流程图

1.3 绝对冲突避免机制

当多个节点同时发起竞争，且网络中其他节点均由于同时收到多个冲突信号或未收到广播信息而无法更新时隙分配表，则当前时隙始终被两节点同时占用，无法完成所有节点无冲突时隙分配，将此冲突称为导致组网过程失败的绝对冲突。出现绝对冲突的条件为多个节点同时发起竞争，具有相同的子节点，同时不存在第三方节点对时隙分配进行判决。当绝对冲突发生，同时申请时隙的节点会持续在相同子节点发出的广播信息中检索到时隙占用失败。基于此特点，为避免出现绝对冲突，需令节点对收到的广播信息中对时隙占用是否成功进行判决，若持续10 次在同一节点的广播信息中检索到占用失败，则清空时隙占用信息，重新对其他时隙发起竞争。因此，算法加入判决机制，如图3 所示。

图3 绝对冲突避免机制流程图

2 最优竞争概率分析

2.1 马尔可夫决策过程

根据马尔可夫决策过程＜S，A，P，R，γ＞建立数学模型，获取网络节点时隙分配状态的最优策略，从而计算出最优竞争概率。

节点竞争过程中，随着网络中已成功占用时隙的节点数增长，抽象出马尔可夫有限状态 集：S={s1，s2，s3，…，sn}。其中n 为网络中所有节点数目，状态si表示网络中有i个时隙被成功占用，状态sn为最终状态。

节点相互独立地对时隙发起竞争，定义状态转换图中有限动作集：A={a1，a2，a3，a4}，给定状态动作分布如图4所示。

图4 给定状态动作分布

动作分布策略π 定义如下：

式中，a1为无冲突竞争行为，a2为发生普通冲突竞争行为，a3为无竞争行为，a4为发生绝对冲突竞争行为。

由动作集和动作对组网时间的影响，定义马尔可夫决策过程奖励函数如下：

以状态值函数表征竞争组网的效率，状态值函数取最大时，组网效率最高，状态值函数贝尔曼最优方程为：

式中，取折扣因子γ=1/2，且：

经过价值迭代算法易得到当最优状态值收敛时，输出最优策略为π*={a1，a1，a1，…，a1}，组网效率最高。

2.2 最优竞争概率理论值

为满足组网效率最高，需保证时帧周期内被成功占用的时隙状态按照最优策略π*进行转移，因此需求得最优竞争概率p，使动作a1分布概率达到最大。状态以动作a1进行转移，可推论节点发起竞争的概率p 随着剩余节点数目的减少而增大，且与剩余节点数目的倒数呈线性相关，设系数为k，则：

利用MATLAB 对动作a1的分布概率P 与k 值的关系进行分析：

得到结果如图5 所示，k=1 时，动作a1分布概率达到最大。因此，根据马尔可夫决策模型分析和理论计算，可得到最优竞争概率p 理论值为：

图5 k 值与动作概率关系图

3 组网策略仿真验证

3.1 仿真环境

本文采用OPNET 仿真平台，搭建网络模型对组网策略进行仿真分析，仿真参数设置如表1 所示。

表1 算法运行时间比较

3.2 不同竞争概率下初始组网时间分析

在高速移动的空间网络中，飞行器间是否能实现快速组网是衡量自组网中媒体接入协议性能的一项非常重要的指标。

通过OPNET 对组网过程进行仿真，网络节点数目为10，改变竞争概率系数k 值，得到不同竞争概率下的组网完成时间的5 次平均值，仿真结果如图6 所示。可以看出，当节点竞争概率与剩余可发起竞争的节点数目呈线性相关，且斜率值k 在1～1.5 之间时，组网时间最短，约140 ms，组网效率最高，与理论值k=1 大致相符。

3.3 组网过程中的时间同步

组网过程开始前，节点间初始时刻可能存在一定程度的误差，因此在组网过程中，需对节点时间进行同步。在节点初始时刻相差较大的场景，最早进入组网进程的节点可优先发起多次竞争，其余节点处于静默状态，收到此节点信息后迅速调整时差完成时间同步，时间同步完成时间基本一定。当节点间时差小于1 s 时，时间同步过程以时隙为5 ms 为单位精细调整，仿真结果如图7所示。节点1 存储最晚时刻信息，纵坐标为其余节点与节点1 时差绝对值。随仿真时间的增加，以2 s 时刻作为第一个时帧起始时间，各节点在组网过程中不断调整时差，于0.14 s 后全部完成时间校准，与基准时间的时差均调整为0。

图7 时间同步过程

在图7 对应仿真参数基础上，在组网开始0.04 s 时刻摧毁节点1。由图8(a)看出，节点1 被摧毁前，尚未发送时刻信息，因此网络时间同步至剩余节点中最晚时刻，网络节点正常完成时间同步。若在组网开始0.1 s 时刻摧毁节点1，由图8(b)看出，节点1 被摧毁前，其时刻信息已转发至节点2 和节点10，则节点1 时刻信息已进入网络成为时间基准，因此网络时间可以正常同步至此时刻。

图8 摧毁初始时间基准节点

仿真结果表明，即使在组网过程中摧毁网络中初始的时间基准节点，快速组网和时间同步依旧可以正常完成，证明了无固定时钟基准模式组网策略的灵活性和安全性。

3.4 组网完成时间与时差、节点数目的关系

图9 显示了网络拓扑组网完成时间随节点间时差范围的变化，可以看出，随节点数目的增加，网络组网时间逐渐增加。同时，随节点时差范围增加，时间同步完成时间趋于一定，组网完成时间逐渐趋于稳定，与上述研究相符。由图可以看出，本文提出的快速组网策略满足6～10 个节点数目的空间飞行器组网需求，组网时间在400 ms 以内。

图9 组网完成时间与时差、节点数目的关系

4 结论

本文设计了一种无初始时隙分配和无固定时间基准终端的分布式空间飞行器自组网的初始组网策略，主要实现了飞行器网络快速组网和时钟同步。本文提出了竞争式组网策略，建立马尔可夫决策模型计算出最优竞争概率，并进行了仿真验证，验证了组网效率最高时节点竞争概率与理论值大致相符。同时提出无NTR 时钟同步策略，仿真结果表明，本文提出的时间同步策略提高了飞行器组网过程中网络的抗毁性和灵活性。因此，本文研究的快速组网策略适用于协同组网任务具有临时性、可靠性要求高的空间飞行器自组网。