一种提高频谱利用率的航空导航台站频率指配算法*

李 锐，周自力，刘松淘，王建强，王 军

(1.中国民用航空局第二研究所，成都 610041；2.电子科技大学 通信抗干扰技术国家级重点实验室，成都 611731)

一种提高频谱利用率的航空导航台站频率指配算法*

李 锐1，周自力1，刘松淘**2，王建强1，王 军2

(1.中国民用航空局第二研究所，成都 610041；2.电子科技大学 通信抗干扰技术国家级重点实验室，成都 611731)

针对多个新建航空无线电导航台站高效频率指配问题，根据美国联邦航空管理局(FAA)的频谱管理规范，研究了在已有多台站场景下的频率指配算法。总结了导航台站频率指配的复用干扰和频率配对两个约束条件，给出了提高频谱利用率的频率指配度量准则，设计了单个新建台站的频率指配算法，给出了多台站频率指配的深度优先递归搜索算法。数值仿真结果表明，所提算法在为多个新建台站同时指配频率时，可有效提高频谱利用率。

航空无线电导航；频率指配；复用干扰；频率配对；深度优先搜索

1 引 言

民用航空无线电导航台站主要有仪表着陆系统(Instrument Landing System，ILS)、甚高频全向信标(Very High Frequency Omnidirectional Range，VOR)和测距仪(Distance Measuring Equipment，DME)等。ILS系统的航向信标(Localizer，LOC)与下滑信标(Glideslope，GS)分别工作在甚高频(108.10～111.95 MHz)和特高频(329.15～335 MHz)，VOR工作在甚高频，DME工作在L频段(962～1213 MHz)[1]。

随着民用航空市场的高速发展，需要新建的ILS、VOR和DME台站不断增加，导致无线频谱资源日益紧张。为此，在保证已有台站安全工作的前提下，有必要对新建台站进行高效的频率指配，提高频谱利用率。在新建台站的频率指配中面临两方面的问题：一是各台站发射的无线电信号可能产生相互干扰，影响航空器的飞行安全；二是不同类型台站配合工作时，需要考虑频率配对要求。

频率指配算法分为确定性算法和优化算法[2]。优化算法包括遗传算法、蚁群算法等，主要用于频谱使用环境动态变化的复杂军用系统，实现设备频率的动态实时改变，其复杂度高。在频谱环境稳定、不需实时改变频谱的民用航空无线电系统中，一般采用复杂度低的确定性算法，如深度优先的搜索算法。文献[3]基于确定性算法的思想，研究了局域增强系统台站的频率指配算法。

针对上述民用导航台站频率的高效指配问题，本文根据美国联邦航空管理局(Federal Aviation Administration，FAA)的频谱管理规范[4]，首先总结了与ILS、VOR和DME频率指配相关的约束条件，以提高频谱利用率为目标，给出了频率指配的频谱利用率准则；在此基础上，设计了单个新建台站的频率指配算法；进一步，针对大量台站频率指配的问题，采用深度优先的搜索方法，给出了多台站频率指配的算法。仿真结果表明，所提算法在大量台站下可实现高频谱利用率的频率指配。

2 导航台频率指配目标和约束条件

将已建LOC、GS、VOR台站所使用的频率和DME台站询问、应答所用频率分别构成5组向量：fLused={fLused,i}、fGused={fGused,i}，fVused={fVused,i}，fDinused={fDinused,i}和fDrepused={fDrepused,i}，其中，i是正整数。根据频率配对规范要求[4]，表1定义了可为新建台站指配的频率向量组。表中，fi,l、fi,g、fi,ILS,din、fi,ILS,drep分别是按规范配对的LOC、GS以及DME的询问和应答频率向量，fi,v、fi,VOR,din、fi,VOR,drep分别是按标准配对的VOR与DME的询问和应答频率向量，fi,DME,l、fi,DME,g、fi,DME,v、fi,DME,din、fi,DME,drep分别是按标准配对的LOC、GS、VOR以及DME的询问和应答频率向量；ωi表示对应该组频率向量的权重，其值等于频率的复用次数。

表1 新建台站频率指配向量组

Tab.1 Frequency allocation vector set for new stations

与第i个新建ILS台站关联Fi,ILS={fi,l,fi,g,fi,ILS,din,fi,ILS,drep,ωi,ILS}与第i个新建VOR台站关联Fi,VOR={fi,v,fi,VOR,din,fi,VOR,drep,ωi,VOR}与第i个新建DME台站关联Fi,DME={fi,DME,l,fi,DME,g,fi,DME,v,fi,DME,din,fi,DME,drep,ωi,DME}

为了提高频谱的整体利用率，定义如下频率复用因子：

(1)

式中：t为台站类型；np,t为该类台站的第p个已用频率的复用次数；q为该类台站已用频点的个数。本文采用两类频率指配的目标：

(1)最大化式(1)定义的频率复用因子。显然，当复用次数较多的频率被再次指配给新建台站时，频率复用因子的增量就会大于指配复用次数较少的频率。

(2)频率负载均衡。在指配频率时，首先指配频率复用因子小的频率，以使得所有频率复用因子尽可能接近。

在进行频率指配时，需要考虑如下两个约束条件：

约束条件1(C1)：频率复用干扰约束。在进行频率复用时，必须通过合理的频率规划，利用足够的地理间隔将同频或邻频的干扰抑制到可容忍的范围内[5]。文献[4]的附录3第2、3部分给出了具体的射频保护要求，文献[6]给出了具体的信号保护比。

约束条件2(C2)：频率配对约束。ILS、VOR、DME的频率需要根据文献[3]附录3给出的频率配对表进行配对。每一组配对频率可以构成如下向量:

fj={fj,l,fj,g,fj,v,fj,din,fj,drep}。

(2)

式中：fj,l、fj,g、fj,v、fj,din、fj,drep分别为配对表中第j组的LOC、GS、VOR以及DME的询问和应答频率。由于给定频率的DME只会和ILS或VOR之一配对，令式(2)中元素没有取值的时候为0，则{fj,l,fj,g}和fj,v不同时为正值。当新建ILS或VOR台站时，无论它们是否与DME台站合建，都要考虑与之配对的DME台站的频率保护[7]。

根据规范要求[4]，对应3类导航设备频率指配的具体约束关系如下：

(1)VOR

(3)

(2)ILS

(4)

(3)DME

(5)

本文的目标是在已有大量已建ILS、VOR和DME台站的情况下，为多个新建的ILS、VOR或DME台站指配频率，在满足干扰约束和频率配对约束的前提下，提高频谱利用率或使频谱负载均衡。

3 单台站频率指配算法

单台站频谱指配算法包括两个步骤：首先根据上一节中的频率指配约束C1(即式(3)～(5)中的第一个约束条件)对可用频率进行第一次筛选，保留满足频率复用干扰约束的备选频率；然后针对频谱指配约束C2(即式(3)～(5)中的第二个约束条件)对可用频率进行第二次筛选，保留满足频率配对约束的备选频率。

3.1 基于频率复用干扰约束C1的频率筛选

3.1.1 VOR频率复用(CVOR1)筛选

根据规范[4]，两个VOR台站之间的最大保护距离为406 n mile，故对第i个新建VOR台站，采用下面所述算法对406 n mile内的每一个已建VOR台站进行处理，分别去掉不满足VOR和与之配对的LOC同频及邻频干扰的备选频率:

(1)计算第k个已建VOR台站与新建VOR台站的距离Dv,v[8]，和第m个已建LOC台站与新建VOR台站的距离Dl,v，令fi,v=fVused,k；

(2)若Dv,v≤Sv,v(Sv,v是文献[4]附录3给出的与台站功率差有关的VOR台站间的最小保护距离)，则从fi,v中去掉fi,v，跳转到步骤1。

(3)遍历新建VOR台站181 n mile内所有LOC台站，若存在Dl,v≤Sv,l(Sl,v是文献[4]附录3给出的与台站功率差有关的VOR台站与LOC台站间的最小保护距离)，则从fi,v中去掉fi,v；

(4)令fi,v=fVused,k±50 kHz和fi,v=fVused,k±100 kHz，重复步骤2。

3.1.2 ILS的频率复用(CILS1)筛选

根据规范[4]，LOC台站之间的保护距离最大值为157 n mile，对第i个新建LOC台站，与VOR类似，采用下述算法，对157 n mile内每一个已建LOC台站进行频率筛选：

(1)计算第k个已建LOC台站与新建LOC台站的距离Dl,l，第m个已建VOR台站与新建LOC台站距离Dv,l，令fi,l=fLused,k；

(2)若Dl,l≤Sl,l(Si,l是文献[4]附录3所给的与台站功率差有关的LOC台站间最小保护距离)，则从fi,l去掉fi,l，跳转到步骤4；

(4)遍历与新建LOC台站相距74 n mile内所有VOR台站，若存在Dv,l≤Sl,v(Sl,v是文献[4]附录3所给的与台站功率差有关的VOR与LOC最小保护距离)，则从fi,l中去掉fi,l；

(5)令fi,l=fLused,k±50 kHz，重复步骤2。

3.1.3 DME的频率复用(CDME1)筛选

采用与VOR台站相同的方法，考虑第i个新建DME台站，对411 n mile内已有DME台站采用下述算法进行频率筛选:

(1)计算第k个已建DME台站与新建DME台站距离Dd,d，令fi,drep=fDrepused,k;

(2)对于Dd,d≤15 n mile的已建DME台站，从fi,DME,drep去掉与它们fDrepused值相等的频率；

(3)若Dd,d≤Sd,d(Sd,d是文献[4]附录3所给的与台站功率差有关的DME台站间最小保护距离)，则从fi,DME,drep中去掉fi,drep；

(4)令fi,drep=fDrepused,k±1 MHz，重复步骤2。

3.2 基于频率配对约束C2的频率筛选

在上述基于干扰约束的频率筛选后，进一步采用下述算法对得到的可用频率进行满足频率配对约束的频率筛选，最终得到各类台站的可用频率。下述算法以提高频谱利用率为优化目标，若以负载均衡为目标，则将“最大频率复用次数”改为“最小频率复用次数”。

(1)新建VOR：若fi,v中的第j个频率对应的fj,din不在fi,DME,drep中，则从fi,v中剔除该频率。遍历fi,v中所有值后得到可用频率向量Fi,VOR，则新建VOR台站的频率指配为Fi,VOR中具有最大频率复用次数的频率。

(2)新建ILS：若fi,l中的第j个频率对应的fj,din不在fi,DME,drep中，则从fi,l中剔除该频率。遍历fi,l中所有值后得到可用频率向量Fi,ILS，则新建VOR台站的频率指配为Fi,ILS中具有最大频率复用次数的频率。

(3)新建DME：若与fi,DME,drep,j配对的fj,l和fj,v分别均不在fi,l、fi,v中，则从fi,DME,drep中剔除fi,DME,drep,j。遍历fi,DME,drep中所有值后得到可用频率向量Fi,DME，则新建VOR台站的频率指配为Fi,DME中具有最大频率复用次数的频率。

4 多个导航设备的频谱指配算法

根据第3节的算法，每一个台站可能有多个可用频率，对多个台站均需要指配频率的情况，先指配频率的台站将会影响后指配频率台站的频率指配。为此，本文采用深度优先搜索算法进行多台站频率指配[2]。深度优先搜索算法是把最近产生的结点优先扩展，直到达到一定的深度限制。若未找到目标或无法再扩展时，再回溯到前一个结点继续扩展[9]。

以VOR为例，设一共有N个新建台站，采用深度优先搜索的频率指配算法如下(ILS和DME台站的频率指配算法类似，此处不再赘述)：

(1)对第i个新建VOR台站，统计频率复用次数得到ωi,VOR,通过第3节算法得到Fi,VOR，记可用频率个数为ni；

(2)当以最大化频率复用因子为目标时，为第i个新建VOR台站指配权重ωi,VOR为正值且最大的频率，并令ωi,VOR=0，ni=ni-1，将其作为已建台站加入fVused，将其配对DME加入fdrepused，令i=i+1;

(3)当以频率负载均衡为目标时，为第i个新建VOR台站指配权重ωi,VOR为正值且最小的频率，并令ωi,VOR=0，ni=ni-1，将其作为已建台站加入fVused，将其配对DME加入fdrepused，令i=i+1；

(4)若fi+1,v为空，则回溯k层，找到ni-k>0的层，从fLused、fGused、fVused、fDinused、fDrepused中删除i-k层及以后加入的台站信息，令i=i-k，重复步骤2；

(5)重复步骤1，直到i=N，完成N个台站的频率指配，或前i-1个台站的可用频率个数为0，不能同时为所有新建台站的频率指配。

5 数值结果与分析

5.1 频率指配仿真

仿真参数均为虚拟参数。已有台站信息和新建VOR台站信息如表2～4所示。

表2 已有ILS/DME台站信息表

Tab.2 ILS/DME information list

ILS台站LOC纬度(N)/(°)LOC经度(E)/(°)LOC频率/MHzGS频率/MHzDME频率/MHzILS128.47104.34109.90333.801060ILS231.09104.22111.15331.551072ILS329.35106.33111.55332.751076ILS425.30103.48108.90329.301050ILS534.20108.43108.30334.101044

表3 已有VOR/DME台站信息表

Tab.3 VOR/DME information list

VOR台站VOR纬度(N)/(°)VOR经度(E)/(°)VOR频率/MHzDME频率/MHzVOR124.27118.06108.201043VOR225.04102.42108.401045VOR325.34100.13109.401055VOR426.05119.18109.651057VOR526.34101.43109.801059VOR626.35106.42113.201103VOR726.35104.50109.651057VOR827.42106.55112.601097VOR928.54105.24108.401045VOR1029.18106.16109.401055VOR1129.35106.33111.201073VOR1229.59102.59110.801069VOR1330.40104.04108.401045VOR1431.52117.17109.801059VOR1534.22107.09110.851069VOR1636.04103.51108.601047VOR1736.38101.48108.401045VOR1836.40117.00108.401045VOR1939.55116.24108.201043

表4 新建VOR/DME台站信息表

Tab.4 New applied VOR/DME information list

新建VOR台站VOR纬度(N)/(°)VOR经度(E)/(°)New_VOR128.12112.59New_VOR230.35114.17New_VOR321.37108.20New_VOR422.48108.19

图1是各台站地理位置示意图，距离计算采用WGS84模型。

图1 台站经纬度示意图

Fig.1 Sketch map of stations

图2 以提高频谱利用效率为目标的指配频率后的复用统计直方图

Fig.2 Statistical histogram of frequency multiplexing aiming to enhance spectrum efficiency after spectrum allocation

当优化目标为使频谱负载更均衡时，采用本文算法可得4个台站指配结果为108.25 MHz、108.45 MHz、108.65 MHz、108.8 MHz，复用统计如图3所示，指配的频率均为未被已有台站使用的频率。

图3 以均衡频谱负载为目标的指配频率后的复用统计直方图

Fig.3 Statistical histogram of frequency multiplexing aiming to balance spectrum load after spectrum allocation

综上可见，本文所提的频率指配算法可以获得高于顺序和随机指配的频率利用效率或使频谱负载更均衡。

5.2 与我国现有航空导航频率指配方法的比较

我国目前正在使用的航空导航频率指配方法与本文方法相比较，存在两点不足：一是没有考虑台站间的功率差，而是取同类型台站最大保护距离进行比较，比如新建VOR台站，则VOR/VOR台站间的保护距离全为800 km，新建LOC台站时，保护距离全为150 km；二是一次只考虑一个新建台站，由于先指配频率的台站可能对后续台站造成影响，所以不能同时为多个新建台站进行频率指配。

5.3 与基于欧洲频率管理规范的指配方法的比较

与FAA的频率管理规范不同，欧洲频率管理手册[10]简单地规定：LOC台站半径92.5 n mile范围内不能有同频LOC台站，半径18 n mile内不能有邻频LOC台站。本文算法根据FAA频率管理规范[4]规定的不同K值，划分了同频、第一邻频多个保护区域。此外，由于ILS设备使用方向性天线，欧洲的半径标准会造成资源浪费，而本文算法明确区分了LOC台站正反方向的保护半径，可以降低复用距离，提高频谱利用率。例如：表2中ILS1台站位于北纬28.47°，东经104.34°，朝向正北方，其LOC工作频率109.90 MHz；若另一计划新建LOC台站位于北纬26.92°，东经104.34°，计划工作频率109.90 MHz，根据欧洲标准[10]，两同频LOC台站距离小于92.5 n mile，该新建台站将不符合频率保护要求，而根据本文算法，该已有LOC台站正向航道的保护半径为95.5 n mile，反向航道的保护半径为85.5 n mile，由于新建台站在反向航道上，则允许布设，从而提高了频率资源的利用效率。

6 结 论

本文根据FAA的频率管理规范，建立了ILS、VOR和DME可用频率向量组的数学描述，考虑频率复用干扰和频率配对约束两个条件，设计了单台站的频率指配算法，然后对各层频率组合进行深度优先的搜索，得到了高频谱利用率的频率指配方案。数值仿真结果表明，本文所提算法在为多个新建台站同时指配频率时，能提高频谱利用率或使频谱负载更均衡。在实际应用中，本文算法为在已有大量导航台站的复杂环境中基于不同优化目标新增部署多导航台站提供了便利。此外，由于实际情况更为复杂，后续还可针对算法复杂度进行优化。

[1] 王世锦，王湛.机载雷达与通信导航设备[M].北京：科学出版社，2009：111-123,130-147,252-266. WANG Shijin,WANG Zhan.Airborne radar and communication navigation equipment[M].Beijing:The Science Publishing Company,2009:111-123,130-147,252-266.(in Chinese)

[2] 王强，沙斐.频谱管理关键技术———频率指配算法研究[D].北京：北京交通大学，2009. WANG Qiang,SHA Fei.Research on key technique of spectrum management——frequency assignment algorithms[D].Beijing:Beijing Jiaotong University,2009.(in Chinese)

[3] 周自力，李锐，王建强，等.局域增强系统台站最小保护间隔的计算[J].电讯技术，2016，56(9)：995-999. ZHOU Zili,LI Rui,WANG Jianqiang,et al.Calculation of minimum protected distance between navigation facilities for local area augmentation system[J]. Telecommunication Engineering,2016,56(9)：995-999.(in Chinese)

[4] Department of Transportaion Federal Aviation Administration.FAA order 6050.32b spectrum management regulations and procedures manual[S].Montreal,Canada:International Civil Aviation Organization,2008:1-24,7-132.

[5] 李映雪，钟士元，雷静，等.认知无线电中OFDM协作频谱感知技术及其优化[J].北京邮电大学学报，2015，38(5)：96-98. LI Yingxue,ZHONG Shiyuan,LEI Jing,et al.Optimization of cooperative spectrum sensing based on OFDM for cognitive radio networks[J].Journal of Beijing University of Posts and Telecommunications,2015,38(5):96-98.(in Chinese)

[6] International Civil Aviation Organization.ICAO handbook on radio frequency spectrum requirements for civil aviation[S].Montreal,Canada:International Civil Aviation Organization,2013:1-7.

[7] International Civil Aviation Organization.Aeroautical telecommunication[S].Montreal,Canada:International Civil Aviation Organization,2006:1-11.

[8] 黎珍惜，黎家勋.基于经纬度快速计算两点间距离及测量误差[J].测绘与空间地理信息，2013，36(11)：235-237. LI Zhenxi,LI Jiaxun.Quickly calculate the distance between two points and measurement error based on latitude and longitude[J].Geomatics & Spatial Information Technology,2013,36(11):235-237.(in Chinese)

[9] 乐美龙，李贞.基于深度优先搜索算法的机组复原研究[J].武汉理工大学学报，2012，34(9)：63-68. LE Meilong,LI Zhen.Solving the crew recovery problem by depth first search[J].Journal of Wuhan University of Technology,2012,34(9):63-68.(in Chinese)

[10] ICAO.European and North Atlantic Office.EUR Doc 011 frequency management manual[S].Paris:European and North Atlantic Office,2014:27-33.

LI Rui was born in Chengdu,Sichuan Province,in 1968.She received the M.S. degree from Institute of Computer Application,Chinese Academy of Sciences in 1999.She is now a senior engineer. Her research concerns aviation communication,navigation and surveillance technology.

Email:sharplr@atmb.net.cn

周自力(1971—)，男，重庆人，1993年于上海交通大学获双学士学位，现为中国民用航空局第二研究所高级工程师，主要从事航空通信导航监视技术研究工作;

ZHOU Zili was born in Chongqing,in 1971. He received the dual B.S. degrees from Shanghai Jiaotong University in 1993. He is now a senior engineer. His research concerns aviation communication,navigation and surveillance technology.

刘松淘(1993—)，男，重庆人，2016年于电子科技大学获学士学位，现为电子科技大学通信抗干扰重点实验室研究生，主要从事无线通信算法及其实现的研究工作;

LIU Songtao was born in Chongqing,in 1993. He received the B.S. degree from University of Electronic Science and Technology of China in 2016. He is now a graduate student. His research concerns signal processing alogrithms and correponding implemntation for wireless communication systems.

Email:303413956@qq.com

王建强(1977—)，男，山西沁县人，2001年于四川大学获工学学士学位，现为中国民用航空局第二研究所工程师，主要从事计算机应用、航空无线电导航频率工程等方面的研究;

WANG Jianqiang was born in Qinxian,Shanxi Province,in 1977. He received the B.S. degree from Sichuan University in 2001. He is now an engineer. His research concerns computer application,aeronautical navigational aid frequency engineering.

王 军(1974—)，男，四川人，2009年于电子科技大学获工学博士学位，现为电子科技大学通信抗干扰技术国家级重点实验室教授、博士生导师，主要从事无线与移动通信技术方面的研究。

WANG Jun was born in Sichuan Province,in 1974. He received the Ph.D. degree from University of Electronic Science and Technology of China in 2009. He is now a professor and also the Ph.D. supervisor. His research concerns signal processing for wireless communications,air-to-ground communication systems,and cognitive radio.

An Efficient Frequency Allocation Algorithm for Improving Spectrum Utilization of Aeronautical Navigation Aid Facilities

LI Rui1,ZHOU Zili1,LIU Songtao2,WANG Jianqiang1,WANG Jun2

(1.The Second Research Institute of Civil Aviation Administration of China,Chengdu 610041,China;2.National Key Laboratory of Science and Technology on Communications,University of Electronic Science and Technology of China,Chengdu 611731,China)

In order to efficiently allocate spectrum resource for aeronautical navigational aid(NAVAID) facilities under the scenario with many stations,spectrum allocation algorithms are proposed based on the spectrum management regulation of Federal Aviation Administration(FAA).With the constraints of frequency reuse interference and frequency pairing,a spectrum efficiency oriented metric is first proposed,and on this base,a spectrum allocation algorithm is provided for the case of a single-station. Then,a depth-first searching based spectrum allocation method is further proposed for the case of multi-stations. Numerical simulation results show that the proposed spectrum allocation algorithms can assign frequencies for all applied stations with high spectrum utilization.

aeronautical radio navigation；frequency allocation；reuse interference；frequency pairing；depth-first searching

10.3969/j.issn.1001-893x.2016.12.010

李锐，周自力，刘松淘，等.一种提高频谱利用率的航空导航台站频率指配算法[J].电讯技术，2016,56(12):1359-1364.[LI Rui,ZHOU Zili,LIU Songtao,et al.An efficient frequency allocation algorithm for improving spectrum utilization of aeronautical navigation aid facilities[J].Telecommunication Engineering,2016,56(12):1359-1364.]

2016-03-30；

2016-10-25 Received date:2016-03-30；Revised date：2016-10-25

国家高技术研究发展计划(863计划)项目(2015AA01A705)；国家自然科学基金资助项目(61471099)；民航安全能力建设项目(TMSA1510)；高等学校博士学科点专项科研基金资助课题(博导类)(20130185110005)；四川省应用基础研究计划项目(2016JY0104)

Foundation Item:The National High-tech R&D Program(863 Program) of China(2015AA01A705)；The National Natural Science Foundation of China(No.61471099)；The Civil Aviation Safety Capacity Build Project(TMSA1510)；The Specialized Research Fund for the Doctoral Program of Highe Education of China(20130185110005)；The Application Oriented Fundamental Research Project(2016JY0104)

TN965

A

1001-893X(2016)12-1359-06

李 锐(1968—)，女，四川成都人，1999年于中国科学院成都计算所获工学硕士学位，现为中国民用航空局第二研究所高级工程师，主要从事航空通信导航监视技术等领域的研究工作;

**通信作者：303413956@qq.com Corresponding author：303413956@qq.com