【作者】 伍微；

【导师】 王飞雪；

【作者基本信息】 国防科学技术大学 ， 信息与通信工程， 2009， 博士

【摘要】 在我国新一代卫星导航接收机研发过程中,为了满足各种应用需求,接收机种类较多,不仅必须具备多频多通道卫星信号接收的基本功能,通常还需要具备多径抑制、抗干扰、高动态载体导航、信息加解密等功能,某些高端接收机更是集上述功能于一身,功能模块繁多,时序调度控制复杂。同时在研发及试验过程中,设计需求难免会发生变更,需要增加新的功能模块。传统开发方法关注模块级设计,将功能测试正确的模块直接整合到接收机任务集中;对接收机整体调度设计则是较多地停留在方案层,缺少定量的可操作性强的实时调度优化设计方法和性能评估方法,其后果是不能及时发现潜在的时序冲突,在研发中后期需要花费大量的人力时间成本,从而导致开发效率低下。在接收机设计阶段对实时调度进行规划可以有效地提高开发效率。随着不断发展的嵌入式处理器逐渐具备成熟的静态优先级调度内核,接收机设计人员已不再需要自己设计任务调度内核,而是重点对接收机任务的执行时间、优先级、周期和相对截止时间进行离线优化设计,确保调度内核中运行的所有任务实时可调度,并尽可能降低接收机功耗——这正是论文研究的重点。论文针对上述特点,着重研究导航接收机任务集调度优化技术和调度性能评估方法,主要工作和创新如下:系统地研究导航接收机任务参数离线优化技术。论文提出静态优先级实时调度性能评估方法,全面考虑了接收机任务执行时间、优先级、周期和相对截止时间的定量分析。提出并解析证明了接收机有限优先级情况下的可调度判定准则。传统开发中欠缺定量的可操作性强的接收机实时调度优化设计方法,主观决断往往导致开发效率低下。针对上述不足,提出最大允许执行时间均衡二分寻优的离线数值计算方法,指明了使得任务集可调度的最大允许执行时间,有利于解决设计需求变化引发的调度时序冲突;提出并论证了截止期单调保序饱和分配算法能够得到最少优先级,指明系统最少需要分配的优先级数目,有利于设计阶段处理器选型;提出降频节能调度方法,在保障导航任务可调度前提下尽可能降低接收机功耗。研究成果为接收机任务调度、时序分配和功耗规划提供了理论依据。优化设计常用的导航函数是保障任务集可调度、降低接收机功耗的重要手段。对基带信号估计、鉴相、定位解算等常用非线性导航运算进行系统地优化,提出使用差分进化算法离线寻求逼近多项式最优系数的方法,解决了直接运算调度开销太大和传统级数逼近类优化方法精度不够的弱点。以锁相环鉴相为例,在运算精度相同的前提下,本文方法运算量约是Chebyshev级数逼近的1/2,约是Taylor级数逼近的1/1700。在设计阶段关注接收机外围设备调度可以有效地提高接收机开发效率。论证了循环缓冲区可调度充要条件是外围设备总响应时间占总时间的比率小于1,提出求解开辟缓冲区最小空间的离线数值计算方法。提出改进的基于字的行进测试方法,用于快速诊断接收机外设存储器的静态非链接故障。研究成果为保障导航接收机外围设备实时调度提供了重要依据。针对导航任务多精度分档调度问题,提出基于截止期错失率可预测的时间冗余调度方法,消除了传统冗余方法可能引起的多个任务截止期连续错失的多米诺效应。进一步地在本文方法中融合传统时间冗余方法的优点,提出了求解检测点上界位置的离线快速算法,有效降低了截止期错失率。本文研究成果已成功应用于我国导航接收机实时调度设计。更多还原

【Abstract】 In the process of R&D(Researching and Developing) our new generation satellite navigation receivers, which are classified into different categories in order to meet different requirements in applications, receivers must not only have multi-frequency and multi-channel satellite signal receiving functions, but also be inevitably of applicable functions, such as multipath suppression, antijamming, high dynamic carrier navigation, information encryption and decryption, and so on. Some top-class receiver even has all the above functions and need complicated timing control. Also, design demand often changes, which requires adding new modules. Traditional R&D methods focus on module-stage design. Adding tested modules directly into receiver task set lacks for controllable quantificational scheduling optimization and performance evaluation methods. This cannot troubleshoot the potential task timing conflict in time, which costs much especially at the late stage, and results in low efficiency.Considering real-time scheduling at the design stage can greatly improve the R&D efficiency. Navigation receivers adopt well-appointed fixed priority scheduling kernel. Designers only need to use it, and then pay attention to the off-line optimization of task execution time, priority, period and deadline, so that every task is scheduable, and reduce receiver’s power consumption, which is just the key of this dissertation. This dissertation focuses on navigation receiver task set scheduling optimization method and performance evaluation technology. The main contributions of this dissertation are as follows:The off-line optimization technology of navigation receiver task parameters is studied. The fixed priority scheduling performance evaluation method is proposed, where the quantitative analyses of task execution time, priority, period and deadline are considered. The determinant rule for receiver scheduling with limited priority levels is proposed and proved analytically. Traditional R&D methods lack for controllable quantificational scheduling optimization, subjective decision often results in low efficiency. An execution time dichotomy optimization off-line method is proposed based on equilibrium rule, aimed at troubleshooting timing conflict potentially aroused by demand changes. Deadline monotonic ordered saturated assignment is proved to have the least priority levels, which is much quicker than those tradional priority assignment algorithms. An energy-saving scheduling method based on decreasing frequency is proposed to reduce receivers’power consumption, still maintaining taskset schedulability. The above researches provide important theoretical principle for receiver task scheduling. Optimization design of common navigation functions is one of the important methods to guarantee task set schedulable and reduce receiver’s power consumption. As for execution time optimization design of navigation tasks, an optimizing method based on Differential Evolution is proposed to find optimal approximating polynomial coefficients of baseband digital signal processing tasks, such as signal estimation, discriminator, and navigation calculation. In contrast, direct calculation of the above processing costs too much, and tradional progression approximating methods need to improve their computing precision. Take arc tangent PLL discriminator as an example, the calculation complexity of our method is approximately 1/2 of Chebyshev progression approximating, and 1/1700 of Taylor progression approximating, with the same precision.Checking peripheral device scheduling at the design stage can greatly improve receiver’s R&D efficiency. This dissertation analytically proves that the circular buffer schedulablity requires the ratio of the total response time of the peripheral device to total time be less than 1, which is the sufficient and necessary condition. An off-line numerical method is proposed to calculate the minimal space of the circular buffer. And an improved word-oriented march test algorithm is proposed to diagnose all the static unlinked fault of the peripheral memory. The above researches provide important principle for receiver peripheral device scheduling.As for multi-precision redundancy scheduling of navigatin task, a time redundancy scheduling method with predictable Deadline Miss Ratio is proposed, which eliminates the domino effect of continuous deadline missing. Further improving approach is presented, and Deadline Miss Ratio can be effectively reduced by adopting traditional time redundancy techniques based on off-line checkpointing analysis. The techniques studied in this dissertation have been successfully applied to the real-time scheduling design of high quality navigation receivers.更多还原