基于網絡流算法的星載轉發器備份環開關切換方法

(中國空間技術研究院通信衛星事業部，北京 100094)

通信衛星有效載荷由天線分系統和轉發器分系統組成，其功能是接收地面發送的上行信號，對信號進行變頻、放大后向地面發送下行信號。為了實現這一功能，轉發器分系統包括接收機、放大器、濾波器和備份環等組件。其中，備份環用于切換通道中的主備份放大器，以保證轉發器分系統在壽命期間內的可靠運行[1-2]。

備份環的設計需要確保轉發器的冗余度和靈活性，通信衛星在軌運營時，需保證盡可能多的轉發器通路可以正常使用，以獲取最大效能。當某一轉發器通路中的放大器出現故障時，通過重新配置備份環的狀態，使得信號可以從備份放大器通過并輸出，且選取的經過路徑最短、損耗最小，并盡可能減少對其它轉發器通路的影響。

如何在最短時間內找到最優開關切換方案，是衛星運營商十分關注的問題，也是通信衛星有效載荷總體設計的任務之一。隨著通信衛星裝載轉發器數量的增多，備份環的規模也變得越來越大。目前國內對備份環進行重新配置仍然是由人工采用枚舉法完成，在實際使用中這是一個困難并且非常耗時的過程。

有一些文獻針對此問題進行了研究，文獻[3]中提出一種通過遞歸算法執行廣度優先搜索，以便找到將通道連接到放大器的所有可行路徑，但此方法需搜索所有的可行路徑，耗時較長，并且無法選擇最優解，不適用于大規模備份環分析。文獻[4-5]提出使用遺傳算法解決這一問題，但其搜索結果取決于初始種群的規模，有一定概率找不到最優解，并且沒有分析開關故障時的切換方法，應用于大規模備份環較為困難。文獻[6-7]提出使用整數線性規劃算法解決這一問題，但其模型非常復雜，用于大規模備份環分析時，變量和限制條件多達數百個，搜索耗時長。文獻[8]在之前的工作中提出了一種轉發器最短路徑的搜索方法，適用于搜索單路轉發器的最短路徑，無法直接應用于搜索全部轉發器的備份環的整體最優配置。

為了克服以上方法分析大規模備份環的限制，本文提出了一種基于網絡流的備份環開關切換搜索算法，可以分析放大器和開關發生故障時的備份環配置方案，模型復雜度較低，搜索耗時短，能夠快速準確的找到最優方案，顯著提升轉發器設計的自動化程度。

1 備份環最優配置問題概述

為提高轉發器可靠性，放大器一般都用10∶8，18∶15，20∶16等的大數對大數的備份，其中分號前的數字為放大器的數量，分號后的數字為轉發器通道的數量。對大數量之間的備份切換，需使用特殊的開關(如T型開關[9]，R型開關[10]等)按照一定的排列，并進行必要的內部連接而組成的開關矩陣備份環。

一個實際應用的放大器輸出端的20∶16備份環如圖1所示。該備份環包含16個輸出多工器通道(下文簡稱通道)、20個放大器和20個R型開關。設備間通過電纜或波導(下文統稱為射頻鏈接)相連，20個R型開關有80個端口，其中有16個端口連接至16個通道，20個端口連接至20個放大器，22個端口連接至另外22個端口。

圖1 20∶16備份環開關結構圖Fig.1 20∶16 switch redundancy ring schematic

通信衛星在軌運營時，需保證盡可能多的轉發器通路可以正常使用，以獲取最大效能。當某一轉發器通路中的放大器出現故障時，通過重新配置備份環，使得信號可以從備份放大器通過，并且盡可能多的轉發器通路可以正常使用，所有通道的插損之和最小。

因此，備份環的最優方案需要滿足以下兩個條件：①連通盡可能多的通道；②所有通路的插損之和最小。實際應用中可以分為兩種情況，第一種是最優主份配置，當所有放大器、通道和開關都可以正常工作時，搜索最優主份配置；第二種是最優備份配置，當一個或多個放大器或者開關出現故障時，搜索當前情況下的最優備份配置。

2 基于網絡流算法的備份環開關切換方法

隨著計算機和數學軟件的發展，圖論越來越多的被應用到實際生活和生產中，成為解決眾多實際問題的重要工具[11-12]。網絡流理論是圖論中極其重要的分支，得到了廣泛應用，運輸問題、分派問題、通信問題等均可轉化為網絡流來解決[13]。

所謂網絡就是規定了發點和收點，并且每條有向邊上都賦了非負整數權的賦權有向圖，可記為N=(V,A,C,b)，其中V是網絡中頂點的集合，A是網絡中有向邊的集合，C是有向邊集A上定義的非負整數函數，稱為容量函數，對于任意的a∈A，C(a)為有向邊a上的容量，b是費用函數，b(a)是有向邊a上單位流量的費用。

基于網絡流的備份環分析方法，其主要思想是依據網絡流問題的理論建立備份環的數學模型，將放大器、開關和通道作為頂點，射頻鏈接作為邊，依據備份環的拓撲關系建立網絡模型，之后使用求解網絡流的算法搜索備份環的最優方案。

轉發器在地面設計、制造階段和在軌壽命初期，各放大器、開關和通道均可以正常工作，此時的最優方案稱為備份環的最優主份配置。當一個或多個放大器或者開關出現故障時，與之相連的通道無法正常工作，需要切換備份，使轉發器恢復工作，此時的最優方案稱為最優備份配置。最優方案的目標是：①連通盡可能多的通道；②所有通路的插損之和最小。

2.1 備份環建模

在網絡中，用頂點表示備份環中的放大器、開關和通道等組件，用邊表示組件間的射頻鏈接。放大器輸出信號，稱為發點；通道接收信號，稱為收點；開關是中間點。根據網絡的定義，對于任意一個有多個收、發點的網絡，可通過一個簡單的方法轉換成只有一個發點s和一個收點t的網絡，便于后續處理[11]。

用vivj表示表示起點為i，終點為j的有向邊，vivj∈A，C(i,j)表示有向邊vivj的容量。放大器和其相鄰開關，以及通道和其相鄰開關間的信號流向是確定的，因此對應的邊是有向邊；開關間的信號流向是不確定的，因此對應的邊是無向邊，可以表示為兩條有向邊。由于轉發器中每個射頻鏈接內最多只能通過1個通道的信號，因此相應有向邊的容量為1。如果起點i和終點j之間不存在射頻鏈接，即vivj?A，則C(i,j)=0。綜上，C(i,j)的取值如下：

(1)

用b(i,j)表示有向邊vivj上的費用，對應連接點i和點j的射頻鏈接的插損。發點s和收點t連接的有向邊并沒有實際的射頻鏈接，因此費用為0。綜上，b(i,j)的取值如下：

(2)

式中:l(i,j)表示起點為i，終點為j的射頻鏈接的插損。

實際應用中，為了近似處理，可以假設所有射頻鏈接的損耗相等。不失一般性，本文在下文中采用這一近似。此時b(i,j)的取值為

(3)

至此，完成求解最優主份配置時網絡模型N=(V,A,C,b)的建立。

當備份環中的某些組件出現故障時，需要對網絡模型N進行相應修改。

下面分別對備份環中的3種頂點(放大器、通道和開關)的故障進行分析。

1)當放大器故障時，則此放大器無信號流出

這種情況下，將網絡中此放大器連接的有向邊的容量修改為0，即C(i,j)=0(vivj∈A,i為故障放大器節點)。

2)通道故障時，則此通道無信號流入

這種情況下，將網絡中此通道連接的有向邊的容量修改為0，即C(i,j)=0(vivj∈A,j為故障通道節點)。需要說明的是，由于輸出多工器可靠性遠高于放大器和開關，因此實際使用中一般不會出現通道故障的情況。

3)開關故障

開關故障又可以分為兩種情況：

(1)開關徹底損壞，無法通過任何信號。則將網絡中開關連接的有向邊的容量修改為0，即C(i,j)=0(vivj∈A,i或j為故障開關節點)。

(2)開關位置固定，能夠工作在當前位置下，但無法切換至其它位置。以圖2中的開關連接示意圖為例，當開關固定在不同位置時，其網絡模型的修改方式如圖所示。

圖2 開關網絡模型修改示意圖

當開關處于位置1時，將頂點p連接的所有邊的容量修改為0；在頂點q1和q2間構造一條新的邊，容量為1，即C(q1,q2)=C(q2,q1)=1；在頂點q3和q4間構造一條新的邊，容量為1，即C(q3,q4)=C(q4,q3)=1，見圖2(a)。

當開關處于位置2時，將頂點p連接q2,q4的邊的容量修改為0，即C(p,q2)=C(q2,p)=0,C(p,q4)=C(q4,p)=0，見圖2(b)。

當開關處于位置3時，將頂點p連接的所有邊的容量修改為0；在頂點q1和q4間構造一條新的邊，容量為1，即C(q1,q4)=C(q4,q1)=1；在頂點q2和q3間構造一條新的邊，容量為1，即C(q2,q3)=C(q3,q2)=1，見圖2(c)。

當開關處于位置4時，將頂點p連接q1,q3的邊的容量修改為0，即C(p,q1)=C(q1,p)=0,C(p,q3)=C(q3,p)=0，見圖2(d)。

需要說明的是，如果與開關p相連的某個頂點是放大器或者通道，則此時邊的方向是確定的(從放大器流出，流入通道)，因此新構造的邊是有向邊，只有單向容量。例如當開關p固定在位置1時，若頂點q1為放大器，則構造一條起點是q1和終點是q2的有向邊，容量為1，即C(q1,q2)=1；此時不存在起點是q2和終點是q1的有向邊，即C(q2,q1)=0。

至此，完成了求解最優備份配置時網絡模型N=(V,A,C,b)的建立。

2.2 網絡流的最小費用最大流計算

對于網絡N=(V,A,C,b)，定義在有向邊集A上的函數f為網絡N上的流，流f(i,j)表示有向邊vivj中實際通過的流量。一個網絡的可行流需滿足：①容量限制條件，即0≤f(i,j)≤C(i,j),?vivj∈A；②平衡條件，即對于除發點和收點外的中間點，流進與流出該頂點的總流量相等，即保持中間點的流量平衡。

對于備份環，流f(i,j)表示有向邊vivj中實際通過的信號的流量。網絡可行流的兩個限制條件變為：①射頻鏈接上的信號的流量不能超過此射頻鏈接的容量(每個射頻鏈接最多通過一個通道的射頻信號)；②對于每個開關，流進和流出該開關的信號流量相等。以上兩個條件均符合備份環的實際工作情況。備份環網絡的一個可行流對應著備份環的一種通路狀態，可行流上的費用對應著通路的插損。因此，建立備份環的網絡模型后，備份環的優化問題可以轉化為求解網絡的最小費用最大流問題。

網絡的最小費用最大流可以采用Busacker-Gowan迭代法求解[12]，其主要步驟如下：

(1)設網絡N=(V,A,C,b)，取初始可行流f為零流。

(2)構造有向賦權圖Nf=(V,Af,F)，對于任意的vivj∈A，Af和F的定義如下：

當fij=0時，vivj∈Af,F(vivj)=bij

當fij=Cij時，vivj∈Af,F(vjvi)=-bij

當0

轉向(3)。

(3)求出有向賦權圖Nf=(V,Af,F)中發點vs到收點vt的最短路μ，若最短路μ存在，則轉向(4)；否則f是所求出的最小費用最大流，停止。

(4)

轉向(2)。

計算得到流f即為網絡N=(V,A,C,b)的最小費用最大流，流量Wf是網絡N的最大流量，費用ZWf是網絡N在最大流量時的最小費用。對于備份環，最大流量Wf表示備份環能夠連通的最多通道的數量，最小費用ZWf表示備份環連通最多通道時所有通道的最小插損和。

2.3 結果分析

2.2節中求出了備份環的最優解流f，本節根據流f判斷此時備份環各頂點(放大器、通道和開關)的狀態。

由流f的定義可知，若f(i,j)=0(vivj∈A)，表示vi至vj的流量為0，即沒有信號從vi流向vj；若f(i,j)>0(vivj∈A)，則表示有信號從vi流向vj。因為備份環各有向邊的容量C(i,j)=1(vivj∈A,i≠s,j≠t)，f(i,j)≤C(i,j)(vivj∈A)，

因此f(i,j)>0(vivj∈A)等價于f(i,j)=1(vivj∈A)，即

(5)

根據流f判斷各頂點的狀態如下：

(1)若vi是放大器，則f(i,j)=1(vivj∈A)表示此放大器有信號流出，反之表示此放大器沒有信號流出，即沒有使用此放大器；

(2)若vj是通道，則f(i,j)=1(vivj∈A)表示此通道有信號流入，反之表示此通道沒有信號流入，即此通道沒有連通；

(3)若vi是開關，根據信號的流向可以判斷開關的位置。以圖3所示的開關的連接關系示意圖為例，圖中頂點p表示某一開關，頂點q1,q2,q3,q4分別表示與開關J1，J2，J3，J4端口相連接的4個頂點。開關是中間點，流進和流出開關的總流量相等，流進開關的總流量可能為0，1或2。表1給出了根據流函數判斷開關位置的結果。

圖3 開關連接關系示意圖

得出各放大器、通道和開關的狀態后，即確定了備份環的狀態。

表1 開關位置表

3 實例分析

根據本文提出的算法，編寫了備份環最優解搜索程序，并以圖1所示的20∶16備份環開關為例在PC機上(配置CPU@2.66 GHz，內存2 GB)進行了仿真。

首先，令備份環內所有頂點正常工作，搜索最優主份配置。程序運行時間約為0.033 s，網絡的最大流Wf=16，最小費用ZWf=32，表示有16個通道可以工作，所有通道插損之和為32。各通道的放大器和插損見表2。結果表明此時16個通道均可連通，16個放大器有信號輸出(放大器A-07、A-08、A-17、A-18沒有輸出)，開關S-02、S-07、S-12、S-18沒有信號經過，其余開關的位置詳見圖4。經對比，此方案與人工搜索得到的最優主份配置一致。將無信號流出的4個放大器作為備份放大器，其余作為主份放大器；沒有信號經過的4個開關稱為二級開關，其余開關稱為一級開關。

表2 最優主份配置各通道的放大器和插損

然后，模擬在實際工作中可能出現的故障，如放大器損壞，開關損壞，放大器和開關都損壞等，見表3，搜索此時備份環的最優備份配置。

表3 故障實例

根據表3中的幾類典型故障情況，搜索相應的最優備份配置，單次程序運行時間均小于0.035 s，結果如下：

(1)放大器損壞。當任意1～4個放大器損壞時，能夠找到一種最優備份配置，使得16個通道都可以連通。

(2)放大器損壞。當n個以上放大器損壞時((4

(3)開關損壞。二級開關單獨損壞并不影響主份配置，此時16個通道都可以連通。

(4)開關損壞。某個一級開關損壞時，與其直接相連的通道無法連通。

(5)放大器損壞，同時開關位置不可改變。舉例說明：2個主份放大器(A-06，A-09)損壞，同時1個開關(S-03)位置不可改變。計算此時的最優備份配置結果，得到網絡的最大流Wf=16，最小費用ZWf=37，表示有16個通道可以工作，所有通道插損之和為37。各通道的放大器和插損見表4，各開關位置詳見圖5。

經對比，對于以上的故障情況，所得方案與人工搜索得到的最優備份配置一致。

圖4 最優主份配置Fig.4 Optimal initial configuration

通道C-01AC-02AC-03AC-04AC-05AC-06AC-07AC-08A放大器A-04A-05A-07A-03A-08A-02A-10A-01插損22424232通道C-01BC-02BC-03BC-04BC-05BC-06BC-07BC-08B放大器A-14A-12A-16A-11A-19A-13A-20A-15插損22222222

圖5 故障5的最優備份配置Fig.5 Optimal redundant configuration of fault 5

4 結束語

針對傳統人工枚舉法尋找轉發器備份環最優配置越來越耗時不實用的問題，本文根據備份環的特點，提出了一種基于網絡流的備份環分析方法。該方法根據備份環的拓撲關系建立網絡模型，通過迭代搜索得到備份環最優切換方案，可用于搜索備份環的最優主份配置和放大器、開關發生故障時的最優備份配置。通過一個20∶16的備份環對方法進行了驗證，結果表明該方法快速準確有效，能夠找到當前狀態下的最優配置，單次搜索耗時少于0.04 s。此方法可以用于通信衛星轉發器設計階段，也可以應用于在軌維護階段，可以快速準確根據故障現象搜索當前情況下的備份環最優配置。