通信衛(wèi)星轉(zhuǎn)發(fā)器備份環(huán)開關(guān)最短路徑搜索算法研究

馬強 鐘良玉 柴源 楊博 陳佳

(中國空間技術(shù)研究院通信衛(wèi)星事業(yè)部，北京 100094)

現(xiàn)代地球同步軌道通信衛(wèi)星壽命較長，有的已經(jīng)達到15年甚至更長[1-2]。要在如此長的時間內(nèi)保證轉(zhuǎn)發(fā)器正常工作，需要對轉(zhuǎn)發(fā)器進行冗余設(shè)計，其中的有源單機(通常為接收機和功率放大器)都要進行備份考慮，這樣就要分別在有源單機的輸入端和輸出端設(shè)計一定數(shù)量的微波開關(guān)組成備份環(huán)[3-4]。

驗證每臺轉(zhuǎn)發(fā)器的性能時，其主份和備份通路都要進行測試，包括但不限于接收機和功率放大器采用主份、第一備份和第二備份時的性能，一種主備份組合方式稱為一個配置。隨著通信衛(wèi)星裝載的轉(zhuǎn)發(fā)器數(shù)量越來越多，配置數(shù)量也隨之快速增長，針對通信衛(wèi)星裝載的轉(zhuǎn)發(fā)器數(shù)量達到45臺[1]之多的，其配置數(shù)量已超過400個。如何快速、準確地找到每個配置的備份環(huán)開關(guān)切換方案，是轉(zhuǎn)發(fā)器測試時一個非常重要的問題，也是轉(zhuǎn)發(fā)器測試設(shè)計的任務(wù)之一。目前的研究中很少有關(guān)于這一問題的討論。

傳統(tǒng)上針對這個問題采用人工搜索、判斷備份環(huán)開關(guān)切換的方案，確認是否滿足備份單機切換要求、通路是否連通、路徑是否最優(yōu)。在備份環(huán)開關(guān)規(guī)模較小時，此方法可行，但隨著通信衛(wèi)星容量的增長、轉(zhuǎn)發(fā)器數(shù)量的增多，備份環(huán)開關(guān)規(guī)模迅速增加，導(dǎo)致單次搜索難度增大、搜索次數(shù)增多，人工搜索耗時長且容易出錯，效率很低。

為了解決人工搜索效率低下的問題，本文針對不同應(yīng)用場景提出了路徑開關(guān)最少和路徑損耗最小兩種搜索算法，通過程序執(zhí)行可以快速準確地得到各配置的備份環(huán)開關(guān)切換方案，顯著提高轉(zhuǎn)發(fā)器測試設(shè)計的自動化程度。

1 備份環(huán)開關(guān)最短路徑搜索問題概述

通信衛(wèi)星轉(zhuǎn)發(fā)器主要由接收機、輸入多工器、功率放大器、輸出多工器、備份環(huán)開關(guān)等部件組成[5]，其基本原理如圖1所示。轉(zhuǎn)發(fā)器包含以下5個基本元素：上行波束、接收機、通道(輸入通道、輸出通道)、功率放大器、下行波束。給定以上5個基本元素就可以確定一種主備份組合狀態(tài)，即完成一個配置。

由圖1可以看出，備份環(huán)開關(guān)有4組，分別位于接收機的輸入、輸出端，和功率放大器的輸入、輸出端，用于備份切換。為了提高可靠性，接收機一般都用4∶2備份(4臺設(shè)備保證2臺工作，以此類推)，功率放大器一般都用8∶6，10∶8，18∶15等的大數(shù)對大數(shù)的備份，其中分號前的數(shù)字為功率放大器的數(shù)量，分號后的數(shù)字為轉(zhuǎn)發(fā)器通道的數(shù)量。對大數(shù)量之間的備份切換，需用使用特殊的開關(guān)(如T型開關(guān)，R型開關(guān)等)按照一定的排列，并進行必要的內(nèi)部連接而組成的備份環(huán)開關(guān)。每個開關(guān)有4個端口，分別設(shè)為J1、J2、J3、J4，如圖2所示。T型開關(guān)有3種位置：位置1，代表J1—J2通，J3—J4通；位置2，代表J1—J3通，J2—J4通；位置3，代表J1—J4通，J2—J3通。R型開關(guān)有4種位置：位置1，代表J1—J2通，J3—J4通；位置2，代表J1—J3通，J2—J4斷；位置3，代表J1—J4通，J2—J3通；位置4，代表J1—J3斷，J2—J4通。

一個典型的功率放大器輸入端的10∶8備份環(huán)如圖3所示。該備份環(huán)開關(guān)由8個輸入多工器通道(下文簡稱通道)、10個功率放大器、10個T型開關(guān)和29根射頻電纜組成。10個開關(guān)有40個端口，其中有8個開關(guān)端口通過8根射頻電纜連接8個通道，10個開關(guān)端口通過10根射頻電纜連接10個功率放大器，11個端口通過11根射頻電纜連接另外11個端口。

設(shè)置某一配置對應(yīng)的備份環(huán)開關(guān)時，需要根據(jù)配置中的通道和功率放大器在備份環(huán)開關(guān)中找到連通兩者的一條路徑，這樣的路徑可能有多條，需要從中選取一條最短、損耗最小的路徑。例如，通道1到功率放大器3有多條路徑，其中通道1→開關(guān)1→開關(guān)3→開關(guān)4→功率放大器3這條路徑經(jīng)過射頻電纜最少(4根)、開關(guān)也最少(3個)，是最短路徑。

傳統(tǒng)上由人工憑借經(jīng)驗用枚舉法尋找最短路徑。1個備份環(huán)開關(guān)的潛在路徑數(shù)量與開關(guān)數(shù)量成指數(shù)關(guān)系，備份環(huán)開關(guān)規(guī)模較大時，1條路徑可能經(jīng)過多個開關(guān)，人工搜索、判斷最短路徑效率很低且容易出錯，是轉(zhuǎn)發(fā)器測試設(shè)計耗時較多的一個環(huán)節(jié)。

2 基于圖論最短路徑搜索算法的備份環(huán)開關(guān)切換方案

隨著計算機和數(shù)學(xué)軟件的發(fā)展，圖論越來越多的被應(yīng)用到實際生活和生產(chǎn)中，成為解決眾多實際問題的重要工具。最短路問題是圖論中最重要的最優(yōu)化問題之一[6-7]，也是圖論研究中一個經(jīng)典算法問題，它不僅直接應(yīng)用于解決生產(chǎn)實踐中的眾多問題，如管道的鋪設(shè)、線路的安排、廠區(qū)的選址和布局等，而且也經(jīng)常被作為一種基本工具，用于解決其他的最優(yōu)化問題以及預(yù)測和決策問題[8-9]。

基于最短路徑搜索問題的備份環(huán)開關(guān)切換方案，其主要思想是依據(jù)圖論建立備份環(huán)開關(guān)的數(shù)學(xué)模型，將通道、開關(guān)和功率放大器作為節(jié)點，射頻電纜作為邊，用鄰接矩陣來表示備份環(huán)開關(guān)內(nèi)的連接關(guān)系，再求解備份環(huán)開關(guān)的最短路徑。本文的搜索原則是任意給定一個通道和一個功率放大器，找到一條連通兩者的路徑，且所經(jīng)路徑最短。

下文針對不同應(yīng)用場景構(gòu)建了路徑開關(guān)最少和路徑損耗最短兩種搜索算法，其中后者可以看作是前者的一種變形，并給出了兩種算法的對比。

2.1 路徑開關(guān)最少的搜索算法

2.1.1 建立鄰接矩陣

首先備份環(huán)開關(guān)的數(shù)學(xué)模型。任意一個具有c個輸入通道，s個開關(guān)，p個輸出功率放大器的備份環(huán)開關(guān)，其包含節(jié)點總數(shù)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的節(jié)點集，V(G)中的每個元素vi(i=1，2，…，c+s+p)對應(yīng)于備份環(huán)開關(guān)的一個節(jié)點，節(jié)點包括通道、開關(guān)和功率放大器。E(G)為圖G的邊集，E(G)中每個元素記為ek=vivj=vjvi，對應(yīng)備份環(huán)開關(guān)中的一根射頻電纜，給所有邊賦予相同的權(quán)值1。

建立圖G鄰接矩陣W=w(i，j)(c+s+p)×(c+s+p)，w(i，j)表示節(jié)點i和j之間邊的值，定義如下。

(1)

w(i，j)含義為：節(jié)點i和j重合，w(i，j)=0；節(jié)點i和j之間存在一條邊，w(i，j)=1；節(jié)點i和j之間不存在一條邊，w(i，j)=∞。

2.1.2 計算最短距離矩陣

以上述鄰接矩陣為基礎(chǔ)，使用Warshall-Floyd算法求解最短路徑。Warshall-Floyd算法簡稱Floyd算法，它利用了動態(tài)規(guī)劃算法的基本思想[7]：對于每一對節(jié)點u和v，看看是否存在一個節(jié)點w，使得從u到w再到v比已知的路徑更短，如果是則更新它。Floyd算法的優(yōu)點容易理解，可以算出任意兩個節(jié)點之間的最短距離，實現(xiàn)簡單。

首先，用迭代法計算圖G中任意兩個節(jié)點間的最短距離。

(1)用d(i，j)表示一條從節(jié)點i到節(jié)點j的路徑的距離；

(2)選定一個節(jié)點，記為k，對于每一對節(jié)點i和j(i=1，2，…，n，j=1，2，…，n)，如果i到k再到j(luò)的距離比已知的路徑更短，則更新已知路徑，即如果d(i，j)>d(i，k)+d(k，j)，則令d(i，j)=d(i，k)+d(k，j)；

(3)選定下一個節(jié)點，重復(fù)步驟(2)，直至搜索完全部節(jié)點；

(4)計算完成后，d(i，j)是從節(jié)點i到節(jié)點j的最短距離，d(i，j)組成的矩陣D稱為最短距離矩陣。

計算D的過程是三層循環(huán)嵌套迭代，因此計算量正比于節(jié)點總數(shù)n的立方。

2.1.3 計算最短路徑

任意給定起始節(jié)點k1和終止節(jié)點k2，利用D從終止節(jié)點向前逆向搜索可以得到最短路徑。

(1)從終止節(jié)點k2開始搜索；

(2)對于一個節(jié)點i(i=1，2，…，n)，如果節(jié)點i和k2之間存在一條邊(w(i,k2)≠0且w(i,k2)≠∞)，并且節(jié)點k1和k2間的最短距離與節(jié)點k1和i間的最短距離的差恰好等于節(jié)點i和k2間邊的值(d(k1,k2)-d(k1,i) =w(i,k2))，那么說明節(jié)點i就是k2的前一個節(jié)點；

(3)重復(fù)步驟(2)，直到找到的前一個節(jié)點是k1，則表示已經(jīng)回退到了起始節(jié)點，搜索完成，將依次找到的各個節(jié)點逆序排列即是從起始節(jié)點到終止節(jié)點的最短路徑所順序經(jīng)過的各個節(jié)點。

給定一對起始和終止節(jié)點，計算最短路徑的過程是一層循環(huán)，因此計算量正比于節(jié)點數(shù)n。

上述方法在建立鄰接矩陣W時，將所有的邊賦予相等的權(quán)值1，一條路徑的距離表示路徑中邊的數(shù)量，因此求出的最短路徑表示路徑中的邊的數(shù)量最少，而一條路徑中開關(guān)的數(shù)量n(s)和邊的數(shù)量n(e)的關(guān)系為

n(s)=n(e)-1

(2)

因此，路徑中的邊最少等價于路徑中的開關(guān)最少，搜索得出的經(jīng)過邊最少路徑即為經(jīng)過開關(guān)最少的路徑。

給出一個備份環(huán)開關(guān)的原理框圖，按照上述方法即可建立W并計算D。之后任意給定起始節(jié)點和終止節(jié)點，都可以求解它們間的最短路徑，具有一般性。

2.1.4 方法簡化

隨著備份環(huán)開關(guān)規(guī)模增大，節(jié)點總數(shù)n隨之增加，鄰接矩陣規(guī)模增大。根據(jù)上文分析，最短距離矩陣計算量正比于n3，每條最短路徑計算量正比于n，n的增加也會增大搜索路徑時的計算量。下文中將結(jié)合備份環(huán)開關(guān)的特點縮小鄰接矩陣的規(guī)模，以減小計算量。

此時圖G′的鄰接矩陣為W′=w′(i，j)s×s，w′(i，j)的定義如下。

(3)

搜索某通道到某功率放大器間的最短路徑等價于搜索某通道相連開關(guān)到某功率放大器相連開關(guān)間的最短路徑。之后的計算步驟與前述相同，不再重復(fù)。

綜上所述，原始搜索算法鄰接矩陣中的節(jié)點和邊的物理含義明確，包含備份環(huán)開關(guān)的完整信息，便于理解，但鄰接矩陣規(guī)模較大，計算量也較大。簡化搜索算法鄰接矩陣規(guī)模小，計算量小，但丟失了一部分備份環(huán)開關(guān)的信息，需要額外補充起始節(jié)點和終止節(jié)點，使用中需要注意。

2.2 路徑損耗最小的搜索算法

2.1節(jié)中建立鄰接矩陣時，給所有的邊賦予了相同的權(quán)值，因此一條路徑的距離表示此路徑所經(jīng)過的邊的總數(shù)。如果用射頻電纜的實際損耗作為各條邊的權(quán)值，那么一條路徑的距離就表示路徑中所有射頻電纜的損耗的總和，此時求出的最短路徑代表路徑的損耗最小。

建立鄰接矩陣為W=w(i，j)(c+s+p)×(c+s+p)，w(i，j)表示節(jié)點i和j之間邊的值。

(4)

式中：l(i，j)表示連接節(jié)點i和節(jié)點j的射頻電纜的實際損耗。

w(i，j)含義為：節(jié)點i和j重合，記為0；節(jié)點i和j之間存在一條邊，記為所用射頻電纜的實際損耗l(i,j)；節(jié)點i和j之間不存在一條邊，記為∞。

接下來的計算步驟與2.1節(jié)相同，仍然為：

(1)計算最短距離矩陣D；

(2)根據(jù)D和起始節(jié)點k1，終止節(jié)點k2求最短路徑經(jīng)過節(jié)點的順序。

此時D中的d(i，j)是節(jié)點i和節(jié)點j之間的最小損耗(此處忽略了開關(guān)的插入損耗，因同一型號和批次開關(guān)的損耗基本一致，而電纜由于長短不一導(dǎo)致?lián)p耗區(qū)別很大，路徑間損耗的差別主要取決于電纜)。

搜索算法的簡化與2.1節(jié)相同，不再重復(fù)。

2.3 算法比較

2.1和2.2節(jié)分別介紹了路徑開關(guān)最少和路徑損耗最小兩種搜索算法，本節(jié)對兩種算法做進一步比較。兩種算法都基于動態(tài)規(guī)劃的基本思想，使用了迭代算法，計算過程完全相同，區(qū)別在于鄰接矩陣的建立過程，其優(yōu)缺點也體現(xiàn)在這一點上。

路徑開關(guān)最少算法中，所有邊的權(quán)值相同，只反映兩個節(jié)點間是否存在一條邊，較為簡單，通過備份環(huán)開關(guān)原理框圖就可以建立鄰接矩陣并解出經(jīng)過開關(guān)最少的路徑。在轉(zhuǎn)發(fā)器測試設(shè)計時，路徑開關(guān)最少搜索算法能夠滿足實際需求，得到的路徑是最優(yōu)路徑，可以據(jù)此設(shè)置備份環(huán)開關(guān)的狀態(tài)。

路徑損耗最小算法在路徑開關(guān)最少算法的基礎(chǔ)上，將每條邊的權(quán)值改為其對應(yīng)的射頻電纜的損耗，最終求解出實際損耗最小的路徑，更為精確。但因為需要測量并錄入所有射頻電纜的損耗，前期準備工作量較大。適用于做鏈路預(yù)算時計算最小路徑損耗，或者對最短路徑做更精確的判斷。

兩種搜索算法適用于不同的應(yīng)用場景。路徑開關(guān)最少算法準備工作少，鄰接矩陣錄入簡單，根據(jù)備份環(huán)開關(guān)原理框圖即可進行搜索，得到的結(jié)果能夠滿足各配置的備份環(huán)開關(guān)切換需求，適用于轉(zhuǎn)發(fā)器測試設(shè)計；路徑損耗最小算法準備工作多，還需要測量射頻電纜的實際損耗，鄰接矩陣錄入復(fù)雜，得到的結(jié)果更為精確，適用于鏈路預(yù)算。

傳統(tǒng)人工枚舉搜索最短路徑非常依賴人的經(jīng)驗，搜索大規(guī)模備份環(huán)開關(guān)時耗時長，且容易出錯。本算法通過數(shù)學(xué)建模計算的方法搜索最短路徑，利用程序完成搜索工作，耗時短，結(jié)果準確。備份環(huán)開關(guān)的節(jié)點越多，本算法相比人工搜索的優(yōu)勢越大，能夠滿足大規(guī)模備份環(huán)開關(guān)最短路徑搜索的需求。

3 實例分析

根據(jù)上文提出的算法，編寫了最短路徑搜索程序，并以圖3所示備份環(huán)開關(guān)為例在電腦上進行了仿真。

圖3的簡化鄰接矩陣W′為

由此計算得到最短距離矩陣D′為

搜索通道1至功率放大器7間的最短路徑，通道1與開關(guān)1直接相連，功率放大器7與開關(guān)7直接相連，因此計算v1至v7的最短路徑，得最短路徑d(1，7)=5，節(jié)點順序為v1→v3→v5→v6→v8→v7，即通道1→開關(guān)1→開關(guān)3→開關(guān)5→開關(guān)6→開關(guān)8→開關(guān)7→功率放大器7。經(jīng)驗證，此路徑是最短路徑。

另一個例子是搜索通道5至功率放大器10間的最短路徑，計算v2至v10的最短路徑，得最短路徑d(2，10)=5，節(jié)點順序為v2→v3→v5→v6→v8→v10，即通道5→開關(guān)2→開關(guān)3→開關(guān)5→開關(guān)6→開關(guān)8→開關(guān)10→功率放大器10。經(jīng)驗證，此路徑是最短路徑。

對于圖3中的10∶8備份環(huán)(8個通道，10個功率放大器)，人工搜索每個組合的最短路徑所需時間取決于路徑復(fù)雜程度，為1～5 s；而使用最短路徑搜索程序計算全部80種組合的最短路徑所需總時間小于1 s。當(dāng)備份環(huán)規(guī)模增大時，人工和程序相比搜索時間的差距會進一步增加。

實際應(yīng)用中，給出起始節(jié)點和終止節(jié)點，通過本算法計算出最短路徑經(jīng)過的節(jié)點順序后，就能得到路徑中每一個開關(guān)的位置，進而得到設(shè)置開關(guān)狀態(tài)的指令，整個過程由程序自動執(zhí)行，不需要人工參與。通道1至功率放大器7經(jīng)過的各開關(guān)狀態(tài)見表1。

表1 開關(guān)狀態(tài)表Table 1 Position of switches

4 結(jié)束語

隨著民商用通信衛(wèi)星朝著大容量的方向發(fā)展，有效載荷技術(shù)不斷進步。大容量通信衛(wèi)星要求有更多的轉(zhuǎn)發(fā)器，所用的備份環(huán)開關(guān)規(guī)模不斷增大，開關(guān)切換也更加復(fù)雜。針對傳統(tǒng)人工設(shè)置備份環(huán)開關(guān)耗時耗力而且容易出錯的問題，本文提出了一種備份環(huán)開關(guān)狀態(tài)搜索方法，通過建立備份環(huán)開關(guān)的鄰接矩陣和迭代計算找出最短路徑，從而得到開關(guān)切換方案。通過對一個典型10∶8備份環(huán)的計算結(jié)果，證明該方法快速準確有效，耗時少于人工搜索的1%。此方法可以應(yīng)用于轉(zhuǎn)發(fā)器測試設(shè)計階段，能夠?qū)⒃斯づ袛?、設(shè)置備份環(huán)開關(guān)的工作交給計算機完成，提高測試設(shè)計效率。

參考文獻(References)

[1] 魏強, 石明, 王益紅. 東方紅-4衛(wèi)星平臺應(yīng)用的新突破——中星11衛(wèi)星[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] 謝瑞強. 我國成功發(fā)射亞太九號通信衛(wèi)星[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] 陳道明. 通信衛(wèi)星有效載荷技術(shù)[M]. 北京：中國宇航出版社，2001

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

[6] 徐俊明. 圖論及其應(yīng)用[M]. 合肥：中國科學(xué)技術(shù)大學(xué)出版社, 2010

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

[7] 王海英, 黃強, 李傳濤, 等. 圖論算法及其MATLAB實現(xiàn)[M]. 北京：北京航空航天大學(xué)出版社, 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