分治策略在卫星数据交换控制中的应用

2011-11-27胡越欣张笃周

空间控制技术与应用 2011年5期

关键词：任务量轮询下位

胡越欣，张笃周

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

分治策略在卫星数据交换控制中的应用

胡越欣，张笃周

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

基于并行技术对卫星数据流控制进行了研究，利用分治策略设计一种并行架构的卫星数据流控制方式.这种并行进行的通信方式与以往卫星采用的顺序轮询下位机的通信方式相比，可大大缩短与所有下位机完成通信所花费的时间，为中心计算机节约出大量的系统时间，让中心计算机可以利用更多的时间进行卫星姿态控制与轨道计算.

并行技术;分治策略;卫星数据交换

随着航天技术的不断发展，卫星在控制精度和变轨能力、机动能力等方面的性能要求也随之提高.性能要求的提高势必要求卫星配备更多的姿态测量敏感器与执行机构.目前随着各部件自身处理信息功能的日益强大，越来越多的部件能够直接处理姿态信息并将这些信息通过串口这种简单的接口形式将数据传送给中心计算机，目前使用串口通信的部件包括了LTU、星敏感器、加速度计、陀螺等卫星部件.如何解决好中心计算机与这些星上部件通信的实时性并占用最少的系统控制任务时间成为一个提高卫星姿轨控与机动能力的关键技术.

1 传统的卫星数据交换方式

传统的卫星数据流通信方式无论是CAN总线、422总线等都为串行通信方式，当一个中心计算机需要与数个下位机通信时，采取轮询的方式，即与一个下位机通信成功后再与下一个下位机通信，直至与所有的下位机通信完成.

这种数据流方式的优点是硬件结构简单，通信时序明了，不需要复杂的硬件资源，对卫星这种需要保证高可靠度的工程，串行通信方式体现出很大的优势，但中心计算机与所有下位机通信完成使用的时间最少为t=t1+t2+.....+tn(ti为中心计算机与第i个下位机通信所需时间).设备数量的增加势必造成数据量的猛增，通信时间的增加会占用大量的系统控制任务时间，这样很难保证中心计算机有足够的时间进行姿态控制与轨道计算，造成中心计算机效率低下.如何建立一种新的数据流交换方式可以有效减少卫星数据流交换花费的时间是本文的研究重点.

2 一种并行架构的数据交换系统

传统的串行通信数据流的方式无法有效缩短数据交换花费的时间，我们需要设计一种新的数据流方式来缩短数据交换花费时间，通过调研，本文采用一种基于分治策略的并行数据交换系统.

2.1 并行处理技术

并行处理技术是指在同一时间间隔内增加操作数量的技术.我们可以形象地把并行技术看成是由多个处理单元共同完成一个任务，从而提高完成任务的效率，缩短完成任务的时间[1].

并行性的实现方法主要有:资源重复、资源共享和时间重叠3种方法[2].

(1)资源重复的方式:也就是把多个任务分解到多个处理器或多个计算机中，然后再按照一定的拓扑结构来进行求解[3].

(2)资源共享的方式:此方式主要应用在多机处理系统中，在多处理机系统中一般使用共享存储器[3].

(3)时间重叠的方式:时间重叠指在很高速率的应用场合，通过让2个或多个数据转换器并行处理，从而提高系统总体处理速率的一种方法[4].

2.2 卫星数据交换系统的任务分析

本课题研究的系统为卫星中心计算机与各个下位机数据流的研究.中心计算机作为卫星控制平台的控制核心部件，负责与各个下位机完成数据交换，交换的内容包括一般包括以下两个部分:1)从姿态敏感部件获取当前的姿态信息;2)根据从姿态敏感部件获取的当前姿态信息计算出卫星需要的控制量发送给各个执行机构进行控制.

通过对卫星数据交换系统特点的介绍，系统的总任务为控制计算机完成与各个下位机的数据交换.通过对总任务的分析，可以把总任务分解为几个子任务，各个子任务可以是控制计算机与某个下位机完成数据交换，或者是控制计算机与某几个下位机完成数据交换.这些子任务间是完全相互独立的.通过对原系统任务的分析可以得出以下结论:

(1)控制计算机与各个下位机数据流任务量巨大;

(2)分解的子任务完全相互独立;

(3)系统需要完成任务的时间短.

一个复杂系统如果任务量巨大，并且系统任务之间的关联度不是很高，这样的系统适合建立成为一个并行系统[5].将系统的任务分解成为多个相对独立的子任务，并行系统同时处理相对独立的子任务，当所有子任务处理完成后，系统总任务完成.

通过以上两点，可以判断卫星数据交换系统适合建立并行系统.

2.3 基于分治策略建立的并行架构

分治策略的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同.求出子问题的解，就可得到原问题的解[6].当求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出.对于这类问题，往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法.如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止.这就是分治策略的基本思想.

假设卫星控制系统中心计算机需要完成与M个下位机的通信任务，定义这个总任务为A，其中这个总任务下边包括了M个子任务.重新定义总任务A={(A1，T1);(A2，T2);…;(AM，TM)}其中Ai表示i项子任务对应的任务量，Ti表示完成对应子任务需要的时间

如果采用顺序轮询方式完成任务A=A1+A2+…+AM;

所花费的时间是T=T1+T2+…+TM.

现在这种方式是所需要时间最长的.

先假设拥有一个具有并行处理能力的系统，系统的并行处理能力为N，所谓并行系统的并行处理能力N，就是指系统有N个独立的处理单元可以在时间上与空间上并行处理问题.

如果采用分治策略的思路，把任务总任务分解为N个子任务{(B1，t1);(B2，t2);…;(BN，tN)}，其中B1+B2+……+BN=A1+A2+……+AM.并且并行处理系统同时处理N个子任务，这样处理总任务A所需要的时间是Max(ti，i=1，2…，N)，要使Max(ti，i=1，2…，N)最小，即系统用最快的任务完成任务，显然当N=M时(N=子任务数量)，总任务被拆分成为最小子任务单元，所以完成总任务需要的时间最短，但是一个并行处理能力是N=M的系统，需要巨大数量的硬件资源作为基础，数量巨大的硬件资源，导致系统在重量、功耗、成本、可靠性的性能上都要有牺牲，这种并行处理能力的系统应用在卫星上使用是十分不现实的，所以现在以一个并行处理能力N=3，子任务数量M=n的系统为基础进行研究.

本课题基于分治策略建立的并行系统架构类似于SIMD改进的串口交换机系统架构.串口交换机技术是在控制单元与通信子模块间加入可并行处理通信事务的多串口交换机，达到并行传输数据的目的.因卫星体积限制，不能设置独立的串口交换机，故本文将该串口交换机做了较大改进:将串口交换机与主控单元集成在一块母板上，称为集成式控制-串口交换机结构.考虑到卫星系统可用资源的限制，本并行系统设计3个并行通信模块.卫星控制系统中心计算机与3个通信模块组成一个并行处理能力为3的并行系统，能够同时处理与多个下位机通信的任务.

系统的构成

本系统结构包含以下几个模块:

1)中心计算机模块(CU):主要负责模拟卫星中心计算机采集各下位机信息的功能;

2)通信模块(PU):每个通信模块作为一个独立的单元，负责完成与制定下位机通信的任务，并将数据提供给中心控制计算机采集;

3)并行控制模块:用于中心计算机并行控制通信模块，实现几个通信模块并行工作的功能;

4)共享内存模块(MM):作为中心计算机与通信模块交换数据的桥梁，完成中心计算机模块与通信模块的数据交换;

5)切换模块:负责联通通信模块与某个下位机.

系统的基本机构框图如1所示.

图1 并行通信系统组成框图

2.4 基于并行架构的任务分配的算法

受卫星本身资源的限制，我们不可能设计一个并行处理能力无限大的并行系统，结合卫星自身特点，设计合理数量的并行处理单元，本系统采用并行处理能力为3的并行架构.使用3个并行处理模块处理你n个下位机通信任务，如何合理分配给每个并行处理模块相应的任务量是提高系统处理效率的关键.

问题描述.设系统中n个下位机的最大数据传输量为W(w1，w2，…，wn)，对于系统处理能力M，采取何种策略寻找这样一个子集I⊆{1，2，…，n}使得Σwi，=M，i∈I.显然这是一个背包问题，本文提出基于二表法的最优并行算法来求解背包问题[7].

理论分析.为叙述方便，首先对二表法给予简单叙述.二表法分为两个步骤-表的生成步骤和搜索步骤.设串行端口交换机中处理机的数量为P，则两个步骤分别为:

a、表生成步骤

(1)将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))

(实际工程应用中，在M上下的一定范围内进行匹配，增加配对成功率，a为分配裕度依据实际任务分配量设计)，

停止;

找到解;

停止;

无解;

(5)转向(2)

任务的分配:现在以一个卫星中心计算机完成与10个下位机通信为总任务，中心计算机与每个下位机完成数据交换需要的任务量如表1所示.

表1 系统任务表

系统需要完成的总任务量为:T=下位机1+下位机2+…+下位机10=T1+T2+…+T10，将总任务按照分治策略分配任务的基本准则，将任务尽可能平均分配到3个独立的处理单元中取，每个单元应处理T/3内容使得系统完成任务的总时间最短.

现设控制计算机与下位机1、下位机2、下位机5完成数据交换的任务量为T/3;控制计算机与下位机3、下位机6、下位机10完成数据交换的任务量为T/3;控制计算机与下位机4、下位机7、下位机8、下位机9完成数据交换的任务量为T/3;

系统采用二表法对任务量的分配具体算法如下:

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

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

找到解;

停止;

无解;

JUMP AAA

通过二表法可以得到解

故处理单元1完成B1={下位机1;下位机2;下位机5};处理单元2完成B2={下位机3;下位机6;下位机10};处理单元3完成B3={下位机4;下位机7;下位机8;下位机9}.当总任务A不能完全被并行处理单元平均分配时，应尽可能的平衡并行处理单元处理的任务量，使每个并行处理单元处理的任务量基本相同，以达到最高使用效率.处理流程图见图2.

表2 重新分配后的任务表见

图2 处理流程图(本系统中n=3)

2.5 并行系统与原系统的比较

通过以上分析，我们比较两种系统的各种性能，见表3所示.

表3 系统性能比较表

说明:加速比:串行执行时间为Ts，使用q个并行处理机并行执行的时间为Tq(q)，则加速比为:Sp(q)=Ts/Tq(q).

效率:设q个处理机的加速比为Sp(q)，则系统的效率Ep(q)=Sp(q)/q.

性能:求解一个问题的计算量为W，执行时间为T，则性能(FLOP/s)为Perf=W/T[8].

按照这种分治策略建立的并行系统，可以有效缩短卫星数据交换花费时间，以本并行系统为例，完成总任务A需要的时间是串行方式的1/3.

3 系统的实现

现在针对上章设计的并行架构的数据交换系统进行实现.

本系统配置89C51 CPU一块，作为并行处理系统的CU，配置FPGA(FLEX10K系列)一块，FPGA内部设计3个可以并行通信的通信模块并配置相应的接口芯片，每个通信模块对应并行系统中的一个PU，每个通信模块配备一定数量的FIFO，对应并行系统中的一个MM.系统配置如图3所示.其中核心部分为FPGA实现的并行通信模块，采用FPGA实现时间重叠方式的并行技术，并且采用VHDL语言对FPGA进行设计开发.考虑到本课题针对的对象为航天器，所以在元器件的选择上要尽可能选择与航天元器件产品目录中提供的元器件接近的元器件，优化设计，减小FPGA使用的门数.下位机采用PC机配备多串口卡模拟多个下位机.

4 仿真

仿真的基本思路是，把并行数据交换系统与安装好4个422串口的PC连接起来，其中3个串口负责模拟下位机与控制计算机星上数据流的传输，另一个串口负责调整89C51的定时器中断，用来测试星上数据流传输需要的时间长度.

仿真系统基本构成如下:

图3 系统配置图

图4 仿真系统结构示意图

串口1、串口2、串口3分别模拟3个下位机与控制计算机89C51通信，89C51每次向各个下位机发送3个字节的轮询命令，下位机判断接收到正确的轮询命令后向控制计算机发送64字节的数据，控制计算机接受到64字节数据口在相应的位口输出高低电平，地面通过示波器观察相应位口判断控制计算机是否正确接收到下位机数据.

由上述描述可知，3个串口需传递的数据包括轮询命令和数据共201个字节，本系统采用通信波特率38400、11位传输位(奇校验)的传输模式.若采用按顺序轮询的方式，理论上花费在数据传输上的时间t最少为(11/38400)×67×3=58ms.

第一次仿真采用的轮询周期为100ms，通过示波器观察89C51位口P1^0、P1^1、P1^2的输出(注P1^0、P1^1、P1^2高低电平变化一次各表示串口1、串口2、串口3各正确接受数据一次)，示波器显示串口1、串口2、串口3各串口正确接受数据，并不存在丢失数据的现象.

第二次仿真采用的轮询周期为50ms，通过示波器观察89C51位口P1^0、P1^1、P1^2的输出，示波器显示串口1、串口2、串口3各串口正确接受数据，并不存在丢失数据的现象.如果采用的是按顺序轮询方式，50ms不能满足花费在串口通信的时间，所以本次仿真证明，并行通信的方式确实提高了星上数据流的传输速度.

第三次仿真采用的轮询周期为25ms，通过示波器观察89C51位口P1^0、P1^1、P1^2的输出，示波器显示串口1、串口2、串口3各串口正确接受数据，并不存在丢失数据的现象.

第四次仿真采用的轮询周期为20ms，通过示波器观察89C51位口P1^0、P1^1、P1^2的输出，示波器显示串口1、串口2、串口3不能正确接受数据.

通过仿真试验证明，采用分治策略建立的并行数据交换系统大大缩短了数据交换花费的时间.

5 结论

本文基于分治策略的思想，使用“背包问题”中二表法的方法解决了并行通信模块的任务分配问题，建立了一个并行数据交换系统.最后通过仿真验证，这种并行架构在提高卫星数据交换速度方面是确实可行.

[1] 王鹏，吕爽，聂治，等.并行计算应用及实战[M].北京:机械工业出版社，2008

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

[3] 李学干，徐甲同.并行处理技术[M].北京:北京理工大学出版社，1994

[4] 谭杰·霍夫纳，吴忠.利用时间重叠技术提高数据转换器采样速率[J].电测与仪表，2001，38(8):12-14

[5] 包桂秋，王彦平，刘永和.基于并行技术的电力系统综合补偿方法[J].电力系统自动化，2002，26(7):38-41

[6] 赵春红，高希龙，王柠，等.一种应用分治策略的中文分词方法[J].燕山大学学报，2009，33(5):23-27

[7] 李庆华，李肯立，蒋盛益，等.背包问题的最优并行算法[J].软件学报，2003，14(5):891-896

[8] 杨晓东，陆松，牟胜海.并行计算机体系结构[M].北京:科学出版社，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