通信衛星轉發器備份環開關最短路徑搜索算法研究

馬強 鐘良玉 柴源 楊博 陳佳

(中國空間技術研究院通信衛星事業部，北京 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