通信卫星转发器备份环开关最短路径搜索算法研究

马强 钟良玉 柴源 杨博 陈佳

(中国空间技术研究院通信卫星事业部，北京 100094)

现代地球同步轨道通信卫星寿命较长，有的已经达到15年甚至更长[1-2]。要在如此长的时间内保证转发器正常工作，需要对转发器进行冗余设计，其中的有源单机(通常为接收机和功率放大器)都要进行备份考虑，这样就要分别在有源单机的输入端和输出端设计一定数量的微波开关组成备份环[3-4]。

验证每台转发器的性能时，其主份和备份通路都要进行测试，包括但不限于接收机和功率放大器采用主份、第一备份和第二备份时的性能，一种主备份组合方式称为一个配置。随着通信卫星装载的转发器数量越来越多，配置数量也随之快速增长，针对通信卫星装载的转发器数量达到45台[1]之多的，其配置数量已超过400个。如何快速、准确地找到每个配置的备份环开关切换方案，是转发器测试时一个非常重要的问题，也是转发器测试设计的任务之一。目前的研究中很少有关于这一问题的讨论。

传统上针对这个问题采用人工搜索、判断备份环开关切换的方案，确认是否满足备份单机切换要求、通路是否连通、路径是否最优。在备份环开关规模较小时，此方法可行，但随着通信卫星容量的增长、转发器数量的增多，备份环开关规模迅速增加，导致单次搜索难度增大、搜索次数增多，人工搜索耗时长且容易出错，效率很低。

为了解决人工搜索效率低下的问题，本文针对不同应用场景提出了路径开关最少和路径损耗最小两种搜索算法，通过程序执行可以快速准确地得到各配置的备份环开关切换方案，显著提高转发器测试设计的自动化程度。

1 备份环开关最短路径搜索问题概述

通信卫星转发器主要由接收机、输入多工器、功率放大器、输出多工器、备份环开关等部件组成[5]，其基本原理如图1所示。转发器包含以下5个基本元素：上行波束、接收机、通道(输入通道、输出通道)、功率放大器、下行波束。给定以上5个基本元素就可以确定一种主备份组合状态，即完成一个配置。

由图1可以看出，备份环开关有4组，分别位于接收机的输入、输出端，和功率放大器的输入、输出端，用于备份切换。为了提高可靠性，接收机一般都用4∶2备份(4台设备保证2台工作，以此类推)，功率放大器一般都用8∶6，10∶8，18∶15等的大数对大数的备份，其中分号前的数字为功率放大器的数量，分号后的数字为转发器通道的数量。对大数量之间的备份切换，需用使用特殊的开关(如T型开关，R型开关等)按照一定的排列，并进行必要的内部连接而组成的备份环开关。每个开关有4个端口，分别设为J1、J2、J3、J4，如图2所示。T型开关有3种位置：位置1，代表J1—J2通，J3—J4通；位置2，代表J1—J3通，J2—J4通；位置3，代表J1—J4通，J2—J3通。R型开关有4种位置：位置1，代表J1—J2通，J3—J4通；位置2，代表J1—J3通，J2—J4断；位置3，代表J1—J4通，J2—J3通；位置4，代表J1—J3断，J2—J4通。

一个典型的功率放大器输入端的10∶8备份环如图3所示。该备份环开关由8个输入多工器通道(下文简称通道)、10个功率放大器、10个T型开关和29根射频电缆组成。10个开关有40个端口，其中有8个开关端口通过8根射频电缆连接8个通道，10个开关端口通过10根射频电缆连接10个功率放大器，11个端口通过11根射频电缆连接另外11个端口。

设置某一配置对应的备份环开关时，需要根据配置中的通道和功率放大器在备份环开关中找到连通两者的一条路径，这样的路径可能有多条，需要从中选取一条最短、损耗最小的路径。例如，通道1到功率放大器3有多条路径，其中通道1→开关1→开关3→开关4→功率放大器3这条路径经过射频电缆最少(4根)、开关也最少(3个)，是最短路径。

传统上由人工凭借经验用枚举法寻找最短路径。1个备份环开关的潜在路径数量与开关数量成指数关系，备份环开关规模较大时，1条路径可能经过多个开关，人工搜索、判断最短路径效率很低且容易出错，是转发器测试设计耗时较多的一个环节。

2 基于图论最短路径搜索算法的备份环开关切换方案

随着计算机和数学软件的发展，图论越来越多的被应用到实际生活和生产中，成为解决众多实际问题的重要工具。最短路问题是图论中最重要的最优化问题之一[6-7]，也是图论研究中一个经典算法问题，它不仅直接应用于解决生产实践中的众多问题，如管道的铺设、线路的安排、厂区的选址和布局等，而且也经常被作为一种基本工具，用于解决其他的最优化问题以及预测和决策问题[8-9]。

基于最短路径搜索问题的备份环开关切换方案，其主要思想是依据图论建立备份环开关的数学模型，将通道、开关和功率放大器作为节点，射频电缆作为边，用邻接矩阵来表示备份环开关内的连接关系，再求解备份环开关的最短路径。本文的搜索原则是任意给定一个通道和一个功率放大器，找到一条连通两者的路径，且所经路径最短。

下文针对不同应用场景构建了路径开关最少和路径损耗最短两种搜索算法，其中后者可以看作是前者的一种变形，并给出了两种算法的对比。

2.1 路径开关最少的搜索算法

2.1.1 建立邻接矩阵

首先备份环开关的数学模型。任意一个具有c个输入通道，s个开关，p个输出功率放大器的备份环开关，其包含节点总数n=c+s+p，将其定义为图G，标记为G=(V(G),E(G))。其中V(G)={v1,v2,…,vc,vc+1,…,vc+s,vc+s+1,…,vc+s+p}为图G的节点集，V(G)中的每个元素vi(i=1，2，…，c+s+p)对应于备份环开关的一个节点，节点包括通道、开关和功率放大器。E(G)为图G的边集，E(G)中每个元素记为ek=vivj=vjvi，对应备份环开关中的一根射频电缆，给所有边赋予相同的权值1。

建立图G邻接矩阵W=w(i，j)(c+s+p)×(c+s+p)，w(i，j)表示节点i和j之间边的值，定义如下。

(1)

w(i，j)含义为：节点i和j重合，w(i，j)=0；节点i和j之间存在一条边，w(i，j)=1；节点i和j之间不存在一条边，w(i，j)=∞。

2.1.2 计算最短距离矩阵

以上述邻接矩阵为基础，使用Warshall-Floyd算法求解最短路径。Warshall-Floyd算法简称Floyd算法，它利用了动态规划算法的基本思想[7]：对于每一对节点u和v，看看是否存在一个节点w，使得从u到w再到v比已知的路径更短，如果是则更新它。Floyd算法的优点容易理解，可以算出任意两个节点之间的最短距离，实现简单。

首先，用迭代法计算图G中任意两个节点间的最短距离。

(1)用d(i，j)表示一条从节点i到节点j的路径的距离；

(2)选定一个节点，记为k，对于每一对节点i和j(i=1，2，…，n，j=1，2，…，n)，如果i到k再到j的距离比已知的路径更短，则更新已知路径，即如果d(i，j)>d(i，k)+d(k，j)，则令d(i，j)=d(i，k)+d(k，j)；

(3)选定下一个节点，重复步骤(2)，直至搜索完全部节点；

(4)计算完成后，d(i，j)是从节点i到节点j的最短距离，d(i，j)组成的矩阵D称为最短距离矩阵。

计算D的过程是三层循环嵌套迭代，因此计算量正比于节点总数n的立方。

2.1.3 计算最短路径

任意给定起始节点k1和终止节点k2，利用D从终止节点向前逆向搜索可以得到最短路径。

(1)从终止节点k2开始搜索；

(2)对于一个节点i(i=1，2，…，n)，如果节点i和k2之间存在一条边(w(i,k2)≠0且w(i,k2)≠∞)，并且节点k1和k2间的最短距离与节点k1和i间的最短距离的差恰好等于节点i和k2间边的值(d(k1,k2)-d(k1,i) =w(i,k2))，那么说明节点i就是k2的前一个节点；

(3)重复步骤(2)，直到找到的前一个节点是k1，则表示已经回退到了起始节点，搜索完成，将依次找到的各个节点逆序排列即是从起始节点到终止节点的最短路径所顺序经过的各个节点。

给定一对起始和终止节点，计算最短路径的过程是一层循环，因此计算量正比于节点数n。

上述方法在建立邻接矩阵W时，将所有的边赋予相等的权值1，一条路径的距离表示路径中边的数量，因此求出的最短路径表示路径中的边的数量最少，而一条路径中开关的数量n(s)和边的数量n(e)的关系为

n(s)=n(e)-1

(2)

因此，路径中的边最少等价于路径中的开关最少，搜索得出的经过边最少路径即为经过开关最少的路径。

给出一个备份环开关的原理框图，按照上述方法即可建立W并计算D。之后任意给定起始节点和终止节点，都可以求解它们间的最短路径，具有一般性。

2.1.4 方法简化

随着备份环开关规模增大，节点总数n随之增加，邻接矩阵规模增大。根据上文分析，最短距离矩阵计算量正比于n3，每条最短路径计算量正比于n，n的增加也会增大搜索路径时的计算量。下文中将结合备份环开关的特点缩小邻接矩阵的规模，以减小计算量。

此时图G′的邻接矩阵为W′=w′(i，j)s×s，w′(i，j)的定义如下。

(3)

搜索某通道到某功率放大器间的最短路径等价于搜索某通道相连开关到某功率放大器相连开关间的最短路径。之后的计算步骤与前述相同，不再重复。

综上所述，原始搜索算法邻接矩阵中的节点和边的物理含义明确，包含备份环开关的完整信息，便于理解，但邻接矩阵规模较大，计算量也较大。简化搜索算法邻接矩阵规模小，计算量小，但丢失了一部分备份环开关的信息，需要额外补充起始节点和终止节点，使用中需要注意。

2.2 路径损耗最小的搜索算法

2.1节中建立邻接矩阵时，给所有的边赋予了相同的权值，因此一条路径的距离表示此路径所经过的边的总数。如果用射频电缆的实际损耗作为各条边的权值，那么一条路径的距离就表示路径中所有射频电缆的损耗的总和，此时求出的最短路径代表路径的损耗最小。

建立邻接矩阵为W=w(i，j)(c+s+p)×(c+s+p)，w(i，j)表示节点i和j之间边的值。

(4)

式中：l(i，j)表示连接节点i和节点j的射频电缆的实际损耗。

w(i，j)含义为：节点i和j重合，记为0；节点i和j之间存在一条边，记为所用射频电缆的实际损耗l(i,j)；节点i和j之间不存在一条边，记为∞。

接下来的计算步骤与2.1节相同，仍然为：

(1)计算最短距离矩阵D；

(2)根据D和起始节点k1，终止节点k2求最短路径经过节点的顺序。

此时D中的d(i，j)是节点i和节点j之间的最小损耗(此处忽略了开关的插入损耗，因同一型号和批次开关的损耗基本一致，而电缆由于长短不一导致损耗区别很大，路径间损耗的差别主要取决于电缆)。

搜索算法的简化与2.1节相同，不再重复。

2.3 算法比较

2.1和2.2节分别介绍了路径开关最少和路径损耗最小两种搜索算法，本节对两种算法做进一步比较。两种算法都基于动态规划的基本思想，使用了迭代算法，计算过程完全相同，区别在于邻接矩阵的建立过程，其优缺点也体现在这一点上。

路径开关最少算法中，所有边的权值相同，只反映两个节点间是否存在一条边，较为简单，通过备份环开关原理框图就可以建立邻接矩阵并解出经过开关最少的路径。在转发器测试设计时，路径开关最少搜索算法能够满足实际需求，得到的路径是最优路径，可以据此设置备份环开关的状态。

路径损耗最小算法在路径开关最少算法的基础上，将每条边的权值改为其对应的射频电缆的损耗，最终求解出实际损耗最小的路径，更为精确。但因为需要测量并录入所有射频电缆的损耗，前期准备工作量较大。适用于做链路预算时计算最小路径损耗，或者对最短路径做更精确的判断。

两种搜索算法适用于不同的应用场景。路径开关最少算法准备工作少，邻接矩阵录入简单，根据备份环开关原理框图即可进行搜索，得到的结果能够满足各配置的备份环开关切换需求，适用于转发器测试设计；路径损耗最小算法准备工作多，还需要测量射频电缆的实际损耗，邻接矩阵录入复杂，得到的结果更为精确，适用于链路预算。

传统人工枚举搜索最短路径非常依赖人的经验，搜索大规模备份环开关时耗时长，且容易出错。本算法通过数学建模计算的方法搜索最短路径，利用程序完成搜索工作，耗时短，结果准确。备份环开关的节点越多，本算法相比人工搜索的优势越大，能够满足大规模备份环开关最短路径搜索的需求。

3 实例分析

根据上文提出的算法，编写了最短路径搜索程序，并以图3所示备份环开关为例在电脑上进行了仿真。

图3的简化邻接矩阵W′为

由此计算得到最短距离矩阵D′为

搜索通道1至功率放大器7间的最短路径，通道1与开关1直接相连，功率放大器7与开关7直接相连，因此计算v1至v7的最短路径，得最短路径d(1，7)=5，节点顺序为v1→v3→v5→v6→v8→v7，即通道1→开关1→开关3→开关5→开关6→开关8→开关7→功率放大器7。经验证，此路径是最短路径。

另一个例子是搜索通道5至功率放大器10间的最短路径，计算v2至v10的最短路径，得最短路径d(2，10)=5，节点顺序为v2→v3→v5→v6→v8→v10，即通道5→开关2→开关3→开关5→开关6→开关8→开关10→功率放大器10。经验证，此路径是最短路径。

对于图3中的10∶8备份环(8个通道，10个功率放大器)，人工搜索每个组合的最短路径所需时间取决于路径复杂程度，为1～5 s；而使用最短路径搜索程序计算全部80种组合的最短路径所需总时间小于1 s。当备份环规模增大时，人工和程序相比搜索时间的差距会进一步增加。

实际应用中，给出起始节点和终止节点，通过本算法计算出最短路径经过的节点顺序后，就能得到路径中每一个开关的位置，进而得到设置开关状态的指令，整个过程由程序自动执行，不需要人工参与。通道1至功率放大器7经过的各开关状态见表1。

表1 开关状态表Table 1 Position of switches

4 结束语

随着民商用通信卫星朝着大容量的方向发展，有效载荷技术不断进步。大容量通信卫星要求有更多的转发器，所用的备份环开关规模不断增大，开关切换也更加复杂。针对传统人工设置备份环开关耗时耗力而且容易出错的问题，本文提出了一种备份环开关状态搜索方法，通过建立备份环开关的邻接矩阵和迭代计算找出最短路径，从而得到开关切换方案。通过对一个典型10∶8备份环的计算结果，证明该方法快速准确有效，耗时少于人工搜索的1%。此方法可以应用于转发器测试设计阶段，能够将原人工判断、设置备份环开关的工作交给计算机完成，提高测试设计效率。

参考文献(References)

[1] 魏强, 石明, 王益红. 东方红-4卫星平台应用的新突破——中星11卫星[J]. 国际太空, 2013(6):32-36

Wei Qiang, Shi Ming, Wang Yihong. A new breakthough of DFH-4：Chinasat-11 [J]. Space International, 2013(6):32-36 (in Chinese)

[2] 谢瑞强. 我国成功发射亚太九号通信卫星[J]. 中国航天, 2015(11):12

Xie Ruiqiang. Apstar-9 communication satellite is launched successfully by China[J]. Aerospace China, 2015(11): 12 (in Chinese)

[3] I Ju, I Yom. Qualification model 4×4 micro switch matrix for the COMS Ka-band communication payload[C]// 25th International Communications Satellite Systems Conference. Washington D.C.:AIAA, 2007

[4] Liang Sunliang, Murdock G. Integrated redundancy ring based on modular approach[C]// 26th International Communications Satellite Systems Conference. Washington D.C.:AIAA, 2008

[5] 陈道明. 通信卫星有效载荷技术[M]. 北京：中国宇航出版社，2001

Chen Daoming. Telecommunication satellite payload techniques[M]. Beijing: China Astronautics Press, 2001 (in Chinese)

[6] 徐俊明. 图论及其应用[M]. 合肥：中国科学技术大学出版社, 2010

Xu Junming. Graph theory and its application[M]. Hefei: University of Science and Technology of China Press, 2010 (in Chinese)

[7] 王海英, 黄强, 李传涛, 等. 图论算法及其MATLAB实现[M]. 北京：北京航空航天大学出版社, 2010

Wang Haiying, Huang Qiang, Li Chuantao, et al. Graph theory algorithm and its implement of MATLAB[M]. Beijing: Beijing University of Aeronautics and Astronautics Press, 2010 (in Chinese)

[8] E D Kyriakis-Bitzaros, C E Goutis. A space-time representation method of iterative algorithms for the design of processor arrays[J]. The Journal of VLSI Signal Processing, 1999(22): 151-162

[9] A V Sadovsky. Application of the shortest-path problem to routing terminal airspace air traffic[J]. Journal of Aerospace Information Systems, 2014(11): 118-130