一种定向传输武器协同数据链的时分调度信息共享方法*

肖 宇 ，徐任晖 ，朱 军 ，杨建新

（1.陆军工程大学通信工程学院，江苏 南京 210007；2.南京电子技术研究所，江苏 南京 210013）

0 引 言

海上防空反导作战由以往的以平台为中心向协同作战方式演进。为实现武器的协同，需要将多个武器平台的传感器、制导设备等交联在一起，共享目标信息和火力资源信息，从而产生具有武器控制级精度的统一战场态势。由此协调多平台火控系统，实现武器协同，提高联合打击能力。武器协同数据链为协同防空提供了态势共享的手段，不仅在武器平台间交换点迹和航迹等数据，还要实现传感器原始数据的实时共享。在武器协同数据链的应用场景中，网络中各节点所收集的信息能够被网络中所有其他节点收到并处理，即一点发现全网皆知。作为一种提升信息利用效率的信息分发机制，这种通过一定的组网方式，网络内所有节点共享网络其他节点的信息，我们称之为信息共享，抑或所有到所有的广播。

为了保证数据的实时共享，在武器协同数据链的链路接入层一般采用调度式的媒体接入控制（Medium Access Control，MAC）协议。通过对时域、频域、空域、码域的无线资源预先规划调度，每个节点在一定时间内总能获得通信机会，确保实时数据在严格时限要求下完成共享。

另一方面，随着天线技术和射频技术的发展，为武器平台上的无线收发信机配备相控阵天线已经可行。具有定向收发能力的武器协同数据链不仅传输距离远，而且抗截获能力强，还可以充分利用空间复用能力提高网络吞吐量，为战术级的武器协同作战提供了强有力的手段。但是，由于定向天线的收发在实现信号的广播方面具有天然的障碍，信息共享实现的难度更大，机制也更复杂。

美军的CEC（Cooperation Engagement Capability，协同作战能力）[1]就是这样一种既使用相控阵天线实现远距离传输，又要完成传感器数据实时共享的武器协同数据链。为了解决定向传输与信息共享之间的矛盾，CEC系统采用了一种时分成对调度的方法。由于这种调度方法的技术细节没有完全公开，因此我们设计了一种时分半双工节点使用单波束收发实现信息共享的方法，保证单跳簇内共享全部完成且易于工程实现。

1 相关工作

信息共享是一种特殊的全到全的广播，对于无线网络信息共享问题国内外理论研究较少，而无线网络的广播问题则研究较多。另一方面，相对于采用全向天线的无线网络广播问题，采用定向天线的无线网络广播协议的研究也相对较少。文献[2-4]提出了几种采用定向天线的概率转发广播协议。文献[5]提出了一种基于局部拓扑信息的转发节点优化选择方法。文献[6]在文献[5]的基础上，进一步精简了对信道的使用，获得了更高的能量效率。Yang等人[7]考虑了采用定向天线广播时转发节点的优化选择问题，在经典的图的连通支配集问题基础上将该问题建模为有向连通支配集构建问题，并指出该问题是NP（Non Polynominal，非多项式时间）完全问题。文献[8]提出了一种结合定向天线和网络编码的无线网络广播协议，在改进[7]中有向连通支配集构建方法的基础上，提出了一种动态选择转发节点的方法；然后，转发节点在发送报文时，根据邻居节点的接收情况，制定最佳的编码与天线调度策略，使得总的广播能耗最小。

2 系统假设

假设网络中每个节点产生一个数据包，信息共享的目标是当一轮信息共享调度完成后，所有节点都有其他所有节点的数据包。根据武器协同数据链的应用场景确定以下组网条件：

（1）每个节点通信时可在任意水平方向调度天线波束的指向，从而发送或接收；

（2）全网分时隙同步工作，每个节点均有准确的时钟同步脉冲，能准确判断时隙起始位置，不考虑频分或码分的情况；

（3）每个时隙内，每个节点或者发送，或者接收，或者静默，三者状态取其一；

（4）网络拓扑为单跳；

（5）通信是一对一的（即不存在一发多收的情况）；

（6）每时隙数据带宽一定，一个节点在一个时隙内能够发送的数据包的个数及每个数据包的长度须满足每时隙数据带宽限制；

（7）从周期性的某时隙开始，全网节点同步进行一次信息共享过程。

3 令牌式信息共享

时分多址（Time-division Multiple Access，TDMA）是指网内节点依次获得发送机会。基于时分多址实现信息共享最简单的一种方法是令牌式信息共享。即，网内只有一个令牌，且网内每时隙只有一个节点获得发送机会；获得令牌的节点向其他节点依次发送数据，发送完毕后将令牌传递给下一个节点；当所有节点都获得过令牌且发送完数据后，令牌失效；下一次信息共享过程，重新产生一个令牌。

令牌式信息共享的最大缺点是没有利用定向传输无线网络的空分复用优势，造成一轮信息共享的时延过长，数据的实时性收到损害。

如果将网络建模为一个无向图G=（V,E），其中V是网内节点的集合，E是链路的集合。假设网内共有|V|=N个节点，且每个时隙长度均为T。全连通拓扑条件下，完成一轮信息共享的时延为N（N-1）T。

4 CEC的时分成对通信

图1所示为四个CEC节点的时分配对共享方法示意图[1]。在第一个时隙，各节点只发自己的数据；从第二个时隙开始，各节点不仅要发自己的数据，还要帮助其他节点转发它们的数据。例如，第1时隙，1号节点给3号节点发1号数据；第2时隙，3号节点给1号节点发3号数据；第3时隙，1号节点从2号节点收到2号和4号数据，此时1号节点收到了所有节点的数据；但第4时隙，1号节点还需转发3号和1号的数据给2号，帮助2号节点完成共享。

时分成对通信方法只需要4个时隙即可完成信息共享，而令牌式通信方法在同频单波束条件下需要3×4=12个时隙。数据的实时性得到了保证。

图1 CEC 系 统时分成对通信示例

5 全连通拓扑下的最优调度方法

将网络建模为图之后，通过枚举E中链路的不同组合来寻找时隙最少的最优调度方法复杂度太高特别是节点数很大时。因此首先确定完成共享所需要的理论最少时隙数，在此基础上讨论最优调度方法。

从某一个特定节点的角度考虑，假设其数据包扩散到整个网络所需要的最少时隙为Tsingle。同时，假设全网所有数据包扩散到整个网络所需的最少时隙为Tall。显然，Tall≥Tsingle。因此，如果Tall=Tsingle，则Tall必为全网完成共享的最少时隙，Tsingle是最优解的一个下界。

引理1：某时隙，第n个节点的第n号数据包，经过t个时隙至多到达包含第n个节点在内的2t个节点。

证明：假设每个时隙，持有该数据包的节点总能有机会与没有该数据包的节点通信（根据前文假设通信是一对一的），且数据包大小不受带宽的限制，则该数据包在每个时隙都得到最大程度的扩散，扩散速度为每时隙持有该数据包的节点数翻番。因此，经过t个时隙后，含有该数据包的节点数最多为2t。

例如：图2所示1号数据包在三个时隙后到达8个节点，即每个时隙带有该数据包的节点数变为原来的两倍。

图2 全连通拓扑下1号数据包的扩 散过程

第二个时隙中，该数据包分别由1、2号节点向3、4号节点传递；第三个时隙中，该数据包分别由1～4号节点向7～8号节点传递。

引理2：假设单跳网络内有N个节点，若一种完成信息共享的调度方案所需时隙数为

则该方案所需的时隙数一定是最少的。

证明：网内N个节点，即有N种不同的数据包要共享给网中所有节点。根据引理1，共享所需的最少时隙数为t≥log2N。则经过t个时隙后：

如果2t＜N，拥有该数据包的节点数为2t；

如果2t≥N，拥有该数据包的节点数量为N。

下面再分两种情况讨论。

（1）当N为偶数时，单跳全连通条件下，每个节点都能找到与之配对的节点进行数据交换。从单个节点角度看，若是有一种方案使得拓扑中的每种数据包都能按照引理1的方式进行扩散，且不冲突，那么该方案完成信息共享所需的时隙数一定是最小的。在全双工通信条件下，t个时隙内，所有类型的数据包都通过交换扩散到2t个节点中；在半双工通信条件下，每时隙要么发要么收，需要的时隙数为2t。因此 t = 2[lo g2N ]。

（2）当N为奇数时，每个时隙至少有一个节点无法与其它节点进行数据交换。

假设每一种数据包在节点成功配对且通信的情况下，均能按照引理1的最优方式扩散。然而在第一个时隙中，至少有一种数据包无法扩散到其他节点，因此，在其余数据包扩散到2t个节点时，该数据包最多扩散到2t-1个节点。因此，当其他所有节点完成共享时，至少还需再分配一个时隙给该数据包才能完成整个网络的信息共享。因此，需要的时隙数为

图3所示为根据式（1）所计算的全连通拓扑下信息共享所用的最少时隙数。

图3 全连通拓扑下信息共享所需最少时隙数

6 可嵌套实现的时分调度信息共享算法

全连通 拓扑情况下，如果N恰好是2的整数次幂，就可以递归地使用二分法进行时隙分配（如图4所示）。先把N个节点划分成两个相同大小的子集，利用2个时隙在子集的节点间进行成对数据交换，然后再递归地划分子集，完成子集内的数据共享。由于在逐对数据交换后，子集内的每个节点都包含着另一个子集节点的数据，当子集的节点嵌套执行划分子集并交换数据后，全网都完成了数据共享。

用函数f（N）表示完成一次全网信息共享需要的时隙数，当N=2k，其中k是大于0的整数，则f（N）满足递推式：

当节点个数不是2的整数幂时，可以把节点分为两个元素数量不等的子集A、B，其中元素较多的子集A具有的元素个数是：

图4 子集间配对示意图

另一个子集B内的元素个数n较少，元素数量为：

数据共享分3步完成。

（1）首先，选择A子集内的任意n个元素，与B子集内的n个元素配对交换。

（2）然后，A子集内的元素进行嵌套划分子集并共享。

（3）最后，选择A子集内的任意n个元素，与B子集内的n个元素配对交换。该时隙内数据从A单向流向B，但过滤掉第一次A、B间交换已送给B的数据。B子集的所有元素完成共享。算法伪代码如下所示：

两元素配对交换

7 算法性能

7.1 算法复杂度分析

假设一次数据交换所需的算法复杂度是O（1）的。对于令牌式共享，需要O（N2）次数据交换。而对于嵌套实现的信息共享算法，当网络规模为2的整数次幂时只需要O（log2N）次数据交换；即使网络规模不是2的整数次幂，复杂度也不大于O（log2N+N）。因此算法复杂度大大降低。

另外，在前文已经提到，本文提出的算法在共享时延这一指标上明显低于令牌式共享。

7.2 数据吞吐量

本文通过仿真评估使用信息共享算法的网络的吞吐量。仿真时假设时隙长度为50 ms，点到点链路带宽为1.5 Mbit/s。

通过仿真给出了一轮共享完成时网内数据吞吐量的统计，其中有各节点原生的数据量统计、各节点转发的数据量统计和最终各节点接收到的数据量的统计。2个节点是特殊情况，需要转发的数据量是0，每个节点接收的数据量和发送的数据量相等。从图5中可以看出，为了完成共享，各节点都承担了大量的转发任务。当节点数为9和13时，由于个别节点一次转发的其他节点的数据包数量较大，在带宽受限的情况下各节点能传输自己原生数据包的大小反而小，因此9个节点相对于8个节点、13个节点相对于12个节点产生的原生数据总量要小。

图5 全网完成一轮数据共享后的数据吞吐量

7.3 负载公平性

共享算法还要顾及各节点的公平性，即尽可能让每个节点都有一样的转发负荷。通过仿真统计了每种情况下最繁忙的一个节点的收发数据量。从图6中可以看到最繁忙的节点在不同节点数情况下转发的数据量相对于发送自己报文的数据量基本保持在同一比例，因此可以推断其他节点的情况类似，网络负载基本保持公平。

图6 全网完成一轮数据共享后最繁忙节点的数据吞吐量

8 结 语

通过嵌套实现的时分调度算法能够保证在接近最优时延性能的情况下完成全网信息共享，而且算法易于计算机实现。仿真表明算法达到了信息共享的目的，且保证全网节点的负载基本公平。本文提出的方法为实现类似美军CEC的武器协同数据链提供了可行性方案。