分治策略在衛(wèi)星數(shù)據(jù)交換控制中的應(yīng)用

胡越欣，張篤周

(北京控制工程研究所，北京100190)

分治策略在衛(wèi)星數(shù)據(jù)交換控制中的應(yīng)用

胡越欣，張篤周

(北京控制工程研究所，北京100190)

基于并行技術(shù)對衛(wèi)星數(shù)據(jù)流控制進(jìn)行了研究，利用分治策略設(shè)計一種并行架構(gòu)的衛(wèi)星數(shù)據(jù)流控制方式.這種并行進(jìn)行的通信方式與以往衛(wèi)星采用的順序輪詢下位機(jī)的通信方式相比，可大大縮短與所有下位機(jī)完成通信所花費的時間，為中心計算機(jī)節(jié)約出大量的系統(tǒng)時間，讓中心計算機(jī)可以利用更多的時間進(jìn)行衛(wèi)星姿態(tài)控制與軌道計算.

并行技術(shù);分治策略;衛(wèi)星數(shù)據(jù)交換

隨著航天技術(shù)的不斷發(fā)展，衛(wèi)星在控制精度和變軌能力、機(jī)動能力等方面的性能要求也隨之提高.性能要求的提高勢必要求衛(wèi)星配備更多的姿態(tài)測量敏感器與執(zhí)行機(jī)構(gòu).目前隨著各部件自身處理信息功能的日益強(qiáng)大，越來越多的部件能夠直接處理姿態(tài)信息并將這些信息通過串口這種簡單的接口形式將數(shù)據(jù)傳送給中心計算機(jī)，目前使用串口通信的部件包括了LTU、星敏感器、加速度計、陀螺等衛(wèi)星部件.如何解決好中心計算機(jī)與這些星上部件通信的實時性并占用最少的系統(tǒng)控制任務(wù)時間成為一個提高衛(wèi)星姿軌控與機(jī)動能力的關(guān)鍵技術(shù).

1 傳統(tǒng)的衛(wèi)星數(shù)據(jù)交換方式

傳統(tǒng)的衛(wèi)星數(shù)據(jù)流通信方式無論是CAN總線、422總線等都為串行通信方式，當(dāng)一個中心計算機(jī)需要與數(shù)個下位機(jī)通信時，采取輪詢的方式，即與一個下位機(jī)通信成功后再與下一個下位機(jī)通信，直至與所有的下位機(jī)通信完成.

這種數(shù)據(jù)流方式的優(yōu)點是硬件結(jié)構(gòu)簡單，通信時序明了，不需要復(fù)雜的硬件資源，對衛(wèi)星這種需要保證高可靠度的工程，串行通信方式體現(xiàn)出很大的優(yōu)勢，但中心計算機(jī)與所有下位機(jī)通信完成使用的時間最少為t=t1+t2+.....+tn(ti為中心計算機(jī)與第i個下位機(jī)通信所需時間).設(shè)備數(shù)量的增加勢必造成數(shù)據(jù)量的猛增，通信時間的增加會占用大量的系統(tǒng)控制任務(wù)時間，這樣很難保證中心計算機(jī)有足夠的時間進(jìn)行姿態(tài)控制與軌道計算，造成中心計算機(jī)效率低下.如何建立一種新的數(shù)據(jù)流交換方式可以有效減少衛(wèi)星數(shù)據(jù)流交換花費的時間是本文的研究重點.

2 一種并行架構(gòu)的數(shù)據(jù)交換系統(tǒng)

傳統(tǒng)的串行通信數(shù)據(jù)流的方式無法有效縮短數(shù)據(jù)交換花費的時間，我們需要設(shè)計一種新的數(shù)據(jù)流方式來縮短數(shù)據(jù)交換花費時間，通過調(diào)研，本文采用一種基于分治策略的并行數(shù)據(jù)交換系統(tǒng).

2.1 并行處理技術(shù)

并行處理技術(shù)是指在同一時間間隔內(nèi)增加操作數(shù)量的技術(shù).我們可以形象地把并行技術(shù)看成是由多個處理單元共同完成一個任務(wù)，從而提高完成任務(wù)的效率，縮短完成任務(wù)的時間[1].

并行性的實現(xiàn)方法主要有:資源重復(fù)、資源共享和時間重疊3種方法[2].

(1)資源重復(fù)的方式:也就是把多個任務(wù)分解到多個處理器或多個計算機(jī)中，然后再按照一定的拓?fù)浣Y(jié)構(gòu)來進(jìn)行求解[3].

(2)資源共享的方式:此方式主要應(yīng)用在多機(jī)處理系統(tǒng)中，在多處理機(jī)系統(tǒng)中一般使用共享存儲器[3].

(3)時間重疊的方式:時間重疊指在很高速率的應(yīng)用場合，通過讓2個或多個數(shù)據(jù)轉(zhuǎn)換器并行處理，從而提高系統(tǒng)總體處理速率的一種方法[4].

2.2 衛(wèi)星數(shù)據(jù)交換系統(tǒng)的任務(wù)分析

本課題研究的系統(tǒng)為衛(wèi)星中心計算機(jī)與各個下位機(jī)數(shù)據(jù)流的研究.中心計算機(jī)作為衛(wèi)星控制平臺的控制核心部件，負(fù)責(zé)與各個下位機(jī)完成數(shù)據(jù)交換，交換的內(nèi)容包括一般包括以下兩個部分:1)從姿態(tài)敏感部件獲取當(dāng)前的姿態(tài)信息;2)根據(jù)從姿態(tài)敏感部件獲取的當(dāng)前姿態(tài)信息計算出衛(wèi)星需要的控制量發(fā)送給各個執(zhí)行機(jī)構(gòu)進(jìn)行控制.

通過對衛(wèi)星數(shù)據(jù)交換系統(tǒng)特點的介紹，系統(tǒng)的總?cè)蝿?wù)為控制計算機(jī)完成與各個下位機(jī)的數(shù)據(jù)交換.通過對總?cè)蝿?wù)的分析，可以把總?cè)蝿?wù)分解為幾個子任務(wù)，各個子任務(wù)可以是控制計算機(jī)與某個下位機(jī)完成數(shù)據(jù)交換，或者是控制計算機(jī)與某幾個下位機(jī)完成數(shù)據(jù)交換.這些子任務(wù)間是完全相互獨立的.通過對原系統(tǒng)任務(wù)的分析可以得出以下結(jié)論:

(1)控制計算機(jī)與各個下位機(jī)數(shù)據(jù)流任務(wù)量巨大;

(2)分解的子任務(wù)完全相互獨立;

(3)系統(tǒng)需要完成任務(wù)的時間短.

一個復(fù)雜系統(tǒng)如果任務(wù)量巨大，并且系統(tǒng)任務(wù)之間的關(guān)聯(lián)度不是很高，這樣的系統(tǒng)適合建立成為一個并行系統(tǒng)[5].將系統(tǒng)的任務(wù)分解成為多個相對獨立的子任務(wù)，并行系統(tǒng)同時處理相對獨立的子任務(wù)，當(dāng)所有子任務(wù)處理完成后，系統(tǒng)總?cè)蝿?wù)完成.

通過以上兩點，可以判斷衛(wèi)星數(shù)據(jù)交換系統(tǒng)適合建立并行系統(tǒng).

2.3 基于分治策略建立的并行架構(gòu)

分治策略的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題相互獨立且與原問題性質(zhì)相同.求出子問題的解，就可得到原問題的解[6].當(dāng)求解某些問題時，由于這些問題要處理的數(shù)據(jù)相當(dāng)多，或求解過程相當(dāng)復(fù)雜，使得直接求解法在時間上相當(dāng)長，或者根本無法直接求出.對于這類問題，往往先把它分解成幾個子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個問題的解法.如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止.這就是分治策略的基本思想.

假設(shè)衛(wèi)星控制系統(tǒng)中心計算機(jī)需要完成與M個下位機(jī)的通信任務(wù)，定義這個總?cè)蝿?wù)為A，其中這個總?cè)蝿?wù)下邊包括了M個子任務(wù).重新定義總?cè)蝿?wù)A={(A1，T1);(A2，T2);…;(AM，TM)}其中Ai表示i項子任務(wù)對應(yīng)的任務(wù)量，Ti表示完成對應(yīng)子任務(wù)需要的時間

如果采用順序輪詢方式完成任務(wù)A=A1+A2+…+AM;

所花費的時間是T=T1+T2+…+TM.

現(xiàn)在這種方式是所需要時間最長的.

先假設(shè)擁有一個具有并行處理能力的系統(tǒng)，系統(tǒng)的并行處理能力為N，所謂并行系統(tǒng)的并行處理能力N，就是指系統(tǒng)有N個獨立的處理單元可以在時間上與空間上并行處理問題.

如果采用分治策略的思路，把任務(wù)總?cè)蝿?wù)分解為N個子任務(wù){(diào)(B1，t1);(B2，t2);…;(BN，tN)}，其中B1+B2+……+BN=A1+A2+……+AM.并且并行處理系統(tǒng)同時處理N個子任務(wù)，這樣處理總?cè)蝿?wù)A所需要的時間是Max(ti，i=1，2…，N)，要使Max(ti，i=1，2…，N)最小，即系統(tǒng)用最快的任務(wù)完成任務(wù)，顯然當(dāng)N=M時(N=子任務(wù)數(shù)量)，總?cè)蝿?wù)被拆分成為最小子任務(wù)單元，所以完成總?cè)蝿?wù)需要的時間最短，但是一個并行處理能力是N=M的系統(tǒng)，需要巨大數(shù)量的硬件資源作為基礎(chǔ)，數(shù)量巨大的硬件資源，導(dǎo)致系統(tǒng)在重量、功耗、成本、可靠性的性能上都要有犧牲，這種并行處理能力的系統(tǒng)應(yīng)用在衛(wèi)星上使用是十分不現(xiàn)實的，所以現(xiàn)在以一個并行處理能力N=3，子任務(wù)數(shù)量M=n的系統(tǒng)為基礎(chǔ)進(jìn)行研究.

本課題基于分治策略建立的并行系統(tǒng)架構(gòu)類似于SIMD改進(jìn)的串口交換機(jī)系統(tǒng)架構(gòu).串口交換機(jī)技術(shù)是在控制單元與通信子模塊間加入可并行處理通信事務(wù)的多串口交換機(jī)，達(dá)到并行傳輸數(shù)據(jù)的目的.因衛(wèi)星體積限制，不能設(shè)置獨立的串口交換機(jī)，故本文將該串口交換機(jī)做了較大改進(jìn):將串口交換機(jī)與主控單元集成在一塊母板上，稱為集成式控制-串口交換機(jī)結(jié)構(gòu).考慮到衛(wèi)星系統(tǒng)可用資源的限制，本并行系統(tǒng)設(shè)計3個并行通信模塊.衛(wèi)星控制系統(tǒng)中心計算機(jī)與3個通信模塊組成一個并行處理能力為3的并行系統(tǒng)，能夠同時處理與多個下位機(jī)通信的任務(wù).

系統(tǒng)的構(gòu)成

本系統(tǒng)結(jié)構(gòu)包含以下幾個模塊:

1)中心計算機(jī)模塊(CU):主要負(fù)責(zé)模擬衛(wèi)星中心計算機(jī)采集各下位機(jī)信息的功能;

2)通信模塊(PU):每個通信模塊作為一個獨立的單元，負(fù)責(zé)完成與制定下位機(jī)通信的任務(wù)，并將數(shù)據(jù)提供給中心控制計算機(jī)采集;

3)并行控制模塊:用于中心計算機(jī)并行控制通信模塊，實現(xiàn)幾個通信模塊并行工作的功能;

4)共享內(nèi)存模塊(MM):作為中心計算機(jī)與通信模塊交換數(shù)據(jù)的橋梁，完成中心計算機(jī)模塊與通信模塊的數(shù)據(jù)交換;

5)切換模塊:負(fù)責(zé)聯(lián)通通信模塊與某個下位機(jī).

系統(tǒng)的基本機(jī)構(gòu)框圖如1所示.

圖1 并行通信系統(tǒng)組成框圖

2.4 基于并行架構(gòu)的任務(wù)分配的算法

受衛(wèi)星本身資源的限制，我們不可能設(shè)計一個并行處理能力無限大的并行系統(tǒng)，結(jié)合衛(wèi)星自身特點，設(shè)計合理數(shù)量的并行處理單元，本系統(tǒng)采用并行處理能力為3的并行架構(gòu).使用3個并行處理模塊處理你n個下位機(jī)通信任務(wù)，如何合理分配給每個并行處理模塊相應(yīng)的任務(wù)量是提高系統(tǒng)處理效率的關(guān)鍵.

問題描述.設(shè)系統(tǒng)中n個下位機(jī)的最大數(shù)據(jù)傳輸量為W(w1，w2，…，wn)，對于系統(tǒng)處理能力M，采取何種策略尋找這樣一個子集I?{1，2，…，n}使得Σwi，=M，i∈I.顯然這是一個背包問題，本文提出基于二表法的最優(yōu)并行算法來求解背包問題[7].

理論分析.為敘述方便，首先對二表法給予簡單敘述.二表法分為兩個步驟-表的生成步驟和搜索步驟.設(shè)串行端口交換機(jī)中處理機(jī)的數(shù)量為P，則兩個步驟分別為:

a、表生成步驟

(1)將W中子任務(wù)按照任務(wù)量大小非降序排序后，平均分成兩部分W1和W2，W1=(w1，w2，…，wn/2)，W2=(wn/2+1，wn/2+2，…，wn);

(2)生成W1的所有N個可能的子集之和，并將它們按非降序存放在表T=(T1，T2，…，TN)中;

(3)生成W2的所有N個可能的子集之和，并將它們按非升序存放在表Q=(Q1，Q2，…，QN)中.

b、搜索步驟

(1)k=1，p=1.

(2)((M-a)≤Tk+Qp≤(M+a))

(實際工程應(yīng)用中，在M上下的一定范圍內(nèi)進(jìn)行匹配，增加配對成功率，a為分配裕度依據(jù)實際任務(wù)分配量設(shè)計)，

停止;

找到解;

停止;

無解;

(5)轉(zhuǎn)向(2)

任務(wù)的分配:現(xiàn)在以一個衛(wèi)星中心計算機(jī)完成與10個下位機(jī)通信為總?cè)蝿?wù)，中心計算機(jī)與每個下位機(jī)完成數(shù)據(jù)交換需要的任務(wù)量如表1所示.

表1 系統(tǒng)任務(wù)表

系統(tǒng)需要完成的總?cè)蝿?wù)量為:T=下位機(jī)1+下位機(jī)2+…+下位機(jī)10=T1+T2+…+T10，將總?cè)蝿?wù)按照分治策略分配任務(wù)的基本準(zhǔn)則，將任務(wù)盡可能平均分配到3個獨立的處理單元中取，每個單元應(yīng)處理T/3內(nèi)容使得系統(tǒng)完成任務(wù)的總時間最短.

現(xiàn)設(shè)控制計算機(jī)與下位機(jī)1、下位機(jī)2、下位機(jī)5完成數(shù)據(jù)交換的任務(wù)量為T/3;控制計算機(jī)與下位機(jī)3、下位機(jī)6、下位機(jī)10完成數(shù)據(jù)交換的任務(wù)量為T/3;控制計算機(jī)與下位機(jī)4、下位機(jī)7、下位機(jī)8、下位機(jī)9完成數(shù)據(jù)交換的任務(wù)量為T/3;

系統(tǒng)采用二表法對任務(wù)量的分配具體算法如下:

生成W1的所有N個可能的子集之和，并將它們按非降序存放在表T=(T1，T2，…，TN)中;

生成W2的所有N個可能的子集之和，并將它們按非升序存放在表Q=(Q1，Q2，…，QN)中.

找到解;

停止;

無解;

JUMP AAA

通過二表法可以得到解

故處理單元1完成B1={下位機(jī)1;下位機(jī)2;下位機(jī)5};處理單元2完成B2={下位機(jī)3;下位機(jī)6;下位機(jī)10};處理單元3完成B3={下位機(jī)4;下位機(jī)7;下位機(jī)8;下位機(jī)9}.當(dāng)總?cè)蝿?wù)A不能完全被并行處理單元平均分配時，應(yīng)盡可能的平衡并行處理單元處理的任務(wù)量，使每個并行處理單元處理的任務(wù)量基本相同，以達(dá)到最高使用效率.處理流程圖見圖2.

表2 重新分配后的任務(wù)表見

圖2 處理流程圖(本系統(tǒng)中n=3)

2.5 并行系統(tǒng)與原系統(tǒng)的比較

通過以上分析，我們比較兩種系統(tǒng)的各種性能，見表3所示.

表3 系統(tǒng)性能比較表

說明:加速比:串行執(zhí)行時間為Ts，使用q個并行處理機(jī)并行執(zhí)行的時間為Tq(q)，則加速比為:Sp(q)=Ts/Tq(q).

效率:設(shè)q個處理機(jī)的加速比為Sp(q)，則系統(tǒng)的效率Ep(q)=Sp(q)/q.

性能:求解一個問題的計算量為W，執(zhí)行時間為T，則性能(FLOP/s)為Perf=W/T[8].

按照這種分治策略建立的并行系統(tǒng)，可以有效縮短衛(wèi)星數(shù)據(jù)交換花費時間，以本并行系統(tǒng)為例，完成總?cè)蝿?wù)A需要的時間是串行方式的1/3.

3 系統(tǒng)的實現(xiàn)

現(xiàn)在針對上章設(shè)計的并行架構(gòu)的數(shù)據(jù)交換系統(tǒng)進(jìn)行實現(xiàn).

本系統(tǒng)配置89C51 CPU一塊，作為并行處理系統(tǒng)的CU，配置FPGA(FLEX10K系列)一塊，F(xiàn)PGA內(nèi)部設(shè)計3個可以并行通信的通信模塊并配置相應(yīng)的接口芯片，每個通信模塊對應(yīng)并行系統(tǒng)中的一個PU，每個通信模塊配備一定數(shù)量的FIFO，對應(yīng)并行系統(tǒng)中的一個MM.系統(tǒng)配置如圖3所示.其中核心部分為FPGA實現(xiàn)的并行通信模塊，采用FPGA實現(xiàn)時間重疊方式的并行技術(shù)，并且采用VHDL語言對FPGA進(jìn)行設(shè)計開發(fā).考慮到本課題針對的對象為航天器，所以在元器件的選擇上要盡可能選擇與航天元器件產(chǎn)品目錄中提供的元器件接近的元器件，優(yōu)化設(shè)計，減小FPGA使用的門數(shù).下位機(jī)采用PC機(jī)配備多串口卡模擬多個下位機(jī).

4 仿 真

仿真的基本思路是，把并行數(shù)據(jù)交換系統(tǒng)與安裝好4個422串口的PC連接起來，其中3個串口負(fù)責(zé)模擬下位機(jī)與控制計算機(jī)星上數(shù)據(jù)流的傳輸，另一個串口負(fù)責(zé)調(diào)整89C51的定時器中斷，用來測試星上數(shù)據(jù)流傳輸需要的時間長度.

仿真系統(tǒng)基本構(gòu)成如下:

圖3 系統(tǒng)配置圖

圖4 仿真系統(tǒng)結(jié)構(gòu)示意圖

串口1、串口2、串口3分別模擬3個下位機(jī)與控制計算機(jī)89C51通信，89C51每次向各個下位機(jī)發(fā)送3個字節(jié)的輪詢命令，下位機(jī)判斷接收到正確的輪詢命令后向控制計算機(jī)發(fā)送64字節(jié)的數(shù)據(jù)，控制計算機(jī)接受到64字節(jié)數(shù)據(jù)口在相應(yīng)的位口輸出高低電平，地面通過示波器觀察相應(yīng)位口判斷控制計算機(jī)是否正確接收到下位機(jī)數(shù)據(jù).

由上述描述可知，3個串口需傳遞的數(shù)據(jù)包括輪詢命令和數(shù)據(jù)共201個字節(jié)，本系統(tǒng)采用通信波特率38400、11位傳輸位(奇校驗)的傳輸模式.若采用按順序輪詢的方式，理論上花費在數(shù)據(jù)傳輸上的時間t最少為(11/38400)×67×3=58ms.

第一次仿真采用的輪詢周期為100ms，通過示波器觀察89C51位口P1^0、P1^1、P1^2的輸出(注P1^0、P1^1、P1^2高低電平變化一次各表示串口1、串口2、串口3各正確接受數(shù)據(jù)一次)，示波器顯示串口1、串口2、串口3各串口正確接受數(shù)據(jù)，并不存在丟失數(shù)據(jù)的現(xiàn)象.

第二次仿真采用的輪詢周期為50ms，通過示波器觀察89C51位口P1^0、P1^1、P1^2的輸出，示波器顯示串口1、串口2、串口3各串口正確接受數(shù)據(jù)，并不存在丟失數(shù)據(jù)的現(xiàn)象.如果采用的是按順序輪詢方式，50ms不能滿足花費在串口通信的時間，所以本次仿真證明，并行通信的方式確實提高了星上數(shù)據(jù)流的傳輸速度.

第三次仿真采用的輪詢周期為25ms，通過示波器觀察89C51位口P1^0、P1^1、P1^2的輸出，示波器顯示串口1、串口2、串口3各串口正確接受數(shù)據(jù)，并不存在丟失數(shù)據(jù)的現(xiàn)象.

第四次仿真采用的輪詢周期為20ms，通過示波器觀察89C51位口P1^0、P1^1、P1^2的輸出，示波器顯示串口1、串口2、串口3不能正確接受數(shù)據(jù).

通過仿真試驗證明，采用分治策略建立的并行數(shù)據(jù)交換系統(tǒng)大大縮短了數(shù)據(jù)交換花費的時間.

5 結(jié) 論

本文基于分治策略的思想，使用“背包問題”中二表法的方法解決了并行通信模塊的任務(wù)分配問題，建立了一個并行數(shù)據(jù)交換系統(tǒng).最后通過仿真驗證，這種并行架構(gòu)在提高衛(wèi)星數(shù)據(jù)交換速度方面是確實可行.

[1] 王鵬，呂爽，聶治，等.并行計算應(yīng)用及實戰(zhàn)[M].北京:機(jī)械工業(yè)出版社，2008

[2] Culler D E，Singh JP，Gupt A.Parallel computer architecture，a hardware/software approach(second edition)[M].China Machine Press，1999

[3] 李學(xué)干，徐甲同.并行處理技術(shù)[M].北京:北京理工大學(xué)出版社，1994

[4] 譚杰·霍夫納，吳忠.利用時間重疊技術(shù)提高數(shù)據(jù)轉(zhuǎn)換器采樣速率[J].電測與儀表，2001，38(8):12-14

[5] 包桂秋，王彥平，劉永和.基于并行技術(shù)的電力系統(tǒng)綜合補(bǔ)償方法[J].電力系統(tǒng)自動化，2002，26(7):38-41

[6] 趙春紅，高希龍，王檸，等.一種應(yīng)用分治策略的中文分詞方法[J].燕山大學(xué)學(xué)報，2009，33(5):23-27

[7] 李慶華，李肯立，蔣盛益，等.背包問題的最優(yōu)并行算法[J].軟件學(xué)報，2003，14(5):891-896

[8] 楊曉東，陸松，牟勝海.并行計算機(jī)體系結(jié)構(gòu)[M].北京:科學(xué)出版社，2008

Application of Divide-and-Conquer Strategy to the Data Stream Control of Satellite

HU Yuexin，ZHANG Duzhou
(Beijing Institute of Control Engineering，Beijing 1000190，China)

A research on the data stream control of AOCS is presented on the basis of the concurrent configuration in this paper.A divide-and-rule strategy is a doptal to design a mode of the data stream control for a satellite and communicates information concurrently.Compared with the traditional data stream control for a satellite which communicates information one by one，this mode can smartly reduce the time for communication and more time will be provided for AOCC to use for the attitude and orbit determination for the satellite.

concurrent technique，divide-and-rule strategy，data stream control of satellite

TP1

A

1674-1579(2011)05-0036-06

10.3969/j.issn.1674-1579.2011.05.007

2011-05-10

胡越欣(1980—)，男，浙江人，工程師，研究方向為航天系統(tǒng)控制(e-mail:neaihyc@sina.com).