基于二分图匹配的甚高频台站信道资源分配策略

摘 要：在空管系统中，为提供可靠的地空通信服务，对于同一空域扇区，一般需要多重甚高频信号覆盖。但甚高频台站的信道资源是有限的，如何制定合理的甚高频台站信道分配策略，使得扇区信号覆盖最优化，是提升地空通信质量的重点。

本文提出了一种基于二分图匹配的甚高频台站信道分配策略。该方法应用于上海区管36扇区调整工程，能实现台站信道与扇区的自动配对，检索时间达到实时。并且该方法不依赖于扇区和空域的变化，是一种通用的方法。

关键词：地空通信，甚高頻遥控台信道，二分图匹配

1 引言

地空通信是最主要的航空移动通信方式[1]。目前上海区域管制中心所辖空域基本实现对单个扇区频率的多重甚高频信号覆盖[2]。但随着区管新增至36扇区工程启动，需要通过调整现有台站的信道资源以实现对所有扇区的优化覆盖。

以往的方法一般通过经验法结合仿真软件实现甚高频台站信道资源的重新分配，但该类方法仍属经验性质，且要逐一调整。本文提出了一种基于二分图匹配的甚高频台站信道分配策略，能实现信道与扇区的自动配对，检索时间达到实时。

2 甚高频台站信道分配策略

2.1 问题简述

甚高频台站信道分配问题可以描述为：将台站信道资源分配给覆盖范围内的扇区使用，使覆盖的扇区数量最大化，同时必须满足两条限制条件：1）台站信道只能给覆盖范围内的扇区使用；2）一旦某个信道资源已被扇区占用，其他扇区不能使用。下文将对这一问题进行建模，并提出本文方法。

2.2 建图

给定若干扇区和台站信道资源，可以构建图G = （V， E），其中点集合V = VS∪VC。 每个扇区si∈VS，对应可选的信道资源cj∈VC，i，j为编号。线集合E中，每个（si，cj）∈E代表扇区si和台站信道cj之间一个可能的分配，即扇区si有可能使用cj这一信道资源。

图1（a）给出一个例子，s1， s2代表两个管制扇区，c1， c2 ， c3代表可分配的台站信道资源，（s1，c1）代表 s1和c1的一个可能的分配。分配是“线段”的集合，如s1和c1连线，即代表扇区s1可以使用c1信道资源。

接下来的问题就是要在图1（a）中找到最大数量的分配结果，这个分配结果应满足：1）多个cj可同时分配给一个si，即台站信道可以给覆盖范围内的任一扇区使用；2）对于单个cj，只能分配给一个si，即一个信道资源不能同时分配给两个扇区使用。

图1（b）和（c）都是满足以上两个条件的分配结果，由红色线段表示。图1（b）中台站信道c1， c2 ， c3都分配给扇区s2使用；图1（c）中信道c1分配给扇区s1，而c2 ， c3分配给s2使用。可以看出，虽然图1（b）和（c）的结果使所有信道资源都分配完毕，但图1（c）方案明显优于图1（b）方案，因为前者覆盖了更多的扇区。

2.3 基于二分图匹配的甚高频台站信道分配策略

为确保得到最优分配结果，我们引入二分图匹配，实施以下策略：

1.对于图G，可利用匈牙利算法[3]计算二分图最大匹配；

2.对未匹配的cj信道进行信道分配的补全。

还是以图1（a）为例，图2（a）通过匈牙利算法[3]自动计算出二分图匹配结果，该匹配优先确保为每个扇区si分配一个可能的信道cj，图2（b）对未匹配的c3进行手动分配补全，最后得到最优分配结果。

我们通过表格给出信道分配结果，如表1。

3 上海区域分区信道分配结果

目前上海区域管制中心进行区域36扇调整方案的评估，该方案需要在现有信道资源基础上进行优化分配。通过本文方案，我们自动计算出36扇区台站信道分配的可能结果，这里我们给出新增的31-36扇的分配结果。

由表2的数据可以看出，基于二分图匹配的甚高频台站信道分配策略能自动、有效地输出信道分配结果。

5 结束语

本文提出的基于二分图匹配的甚高频台站信道分配策略，不依赖于扇区和信道的变化，可以自动输出信道分配结果，是一种通用、高效的方法。下阶段工作可进一步优化分配结果，如通过精确计算覆盖的接收场强与信噪比等技术要素进行验证，并在此基础上进行调整。

参考文献：

[1] 航空无线电导航台和空中交通管制雷达站设置场地规范（MH/T4003-1996）

[2] 张镪 基于语音比选技术的空管地空通信覆盖优化研究与实现 《上海交通大学》，2011.

[3] D. B. West， Introduction to Graph Theory， 2nd ed. Englewood Cliffs， NJ： Prentice-Hall， 2001.

作者简介：

沈剑伟（1984—），男，上海人，硕士，上海技保中心技术支持室，研究方向为地空通信、雷达自动化。endprint