Scheduling algorithm based on critical tasks in heterogeneous environments

Heterogeneous computing is one effective method of high performance computing with many advantages. Task scheduling is a critical issue in heterogeneous environments as well as in homogeneous environments. A number of task scheduling algorithms for homogeneous environments have been proposed, whereas, a few for heterogeneous environments can be found in the literature. A novel task scheduling algorithm for heterogeneous environments, called the heterogeneous critical task （HCT） scheduling algorithm is presented. By means of the directed acyclic graph and the gantt graph, the HCT algorithm defines the critical task and the idle time slot. After determining the critical tasks of a given task, the HCT algorithm tentatively duplicates the critical tasks onto the processor that has the given task in the idle time slot, to reduce the start time of the given task. To compare the performance of the HCT algorithm with several recently proposed algorithms, a large set of randomly generated applications and the Gaussian elimination application are randomly generated. The experimental result has shown that the HCT algorithm outperforms the other algorithm.     

基于信息增量的多被动传感器资源分配算法

针对多被动传感器多目标跟踪中的传感器资源分配问题进行研究。讨论了多被动传感器跟踪误差的克拉美-罗下限,在此基础上分析了多被动传感器系统跟踪误差的几何分布。为解决多目标跟踪中的传感器资源分配问题,通过先验信息熵与后验信息熵之间的差值获得信息增量;在此基础上针对多被动传感器系统的特点构建最优化分配模型,将被动传感器组合在不同时刻动态地分配给不同目标。仿真实验表明,与不考虑资源分配的固定跟踪模式相比,该方法能够高效合理地利用有限资源,并且使多被动传感器多目标跟踪系统的整体跟踪性能得到提高。     

大规模网络中基于HDHT的病毒疫苗分发算法

目前,反病毒系统防御病毒的主要方法是依靠反病毒中心服务器定期更新各个节点上的病毒定义文件和安装系统补丁,这种被动应对策略常常不够及时,且容易使服务器节点成为系统的性能瓶颈,具有较大的滞后性,也不能适应大规模网络系统。针对大规模网络环境提出了一种高效的基于层次式分布散列表(hierarchical distributed Hash table, HDHT)的反病毒疫苗分发算法。算法基于一种新型层次式分布散列表网络拓扑结构HDHT,利用网络边缘节点直接通信来提高病毒疫苗分发效率,从而有效分担服务器负载。为了增强算法的性能,算法还引入一种简洁的节点信誉评估机制。从分发效率、系统开销等方面,对病毒疫苗分发算法的性能进行实验验证和性能分析。结论表明,该算法可有效实现病毒疫苗在网络中快速分发和部署,同时减轻了网络和服务器的负载。     

Improved spectrum sharing algorithm based on feedback control information in cognitive radio networks

In order to avoid the system performance deterioration caused by the wireless fading channel and imperfect channel estimation in cognitive radio networks, the spectrum sharing problem with the consideration of feedback control information from the primary user is analyzed. An improved spectrum sharing algorithm based on the combination of the feedback control information and the optimization algorithm is proposed. The relaxation method is used to achieve the approximate spectrum sharing model, and the spectrum sharing strategy that satisfies the individual outage probability constraints can be obtained iteratively with the observed outage probability. Simulation results show that the proposed spectrum sharing algorithm can achieve the spectrum sharing strategy that satisfies the outage probability constraints and reduce the average outage probability without causing maximum transmission rate reduction of the secondary user.     

基于自适应遗传算法的战场资源动态调度模型及算法

研究了战场平台资源的动态调度问题,首先分析了该问题在动态调度过程中的约束条件,构建了以最小化使命完成时间为目标函数的数学模型,然后针对问题模型的特点,基于自适应遗传算法提出求解算法,最后结合具体算例对平台资源动态调度模型及其求解算法进行了仿真验证,仿真结果表明,求解方法可以有效应对处理任务新增和平台失效等突发事件并且具有较高的时间效率。     

基于非合作博弈模型的跨层资源分配算法

针对多用户多输入多输出 正交频分复用(multiple input multiple output-orthogonal frequency division multiple, MIMO-OFDM)系统的上行链路提出一种基于非合作博弈模型的跨层资源分配算法。基站为用户分配初始上行速率后,各用户间通过非合作博弈方式实现功率最小化。功率未饱和的用户向基站申请增加吞吐量,基站在调整用户吞吐量时综合考虑用户信道条件与媒体访问控制（media access control, MAC）层缓存的状态。仿真表明,算法既降低了用户终端的功率开销,同时兼顾了多用户间的公平性。     

基于混合遗传-粒子群算法的相控阵雷达调度方法

针对相控阵雷达中的任务调度问题,提出一种融合了粒子群算法、遗传算法和启发式交错调度算法的混合算法。采用混沌理论优化粒子群算法的飞行参数,设计递减的动态惯性权重,以及引入遗传算法中的交叉、变异操作,使得算法能够快速收敛,并跳出局部最优实现全局最优。在智能算法的框架下,提出一种启发式的任务交错算法,使得雷达任务中等待期的时间资源进一步得到利用。仿真结果表明,相比于遗传算法,所提算法的收敛速度更快,结果更优;相比于传统的启发式算法,所提算法的调度成功率提升了42%,时间利用率提升了40%,实现价值率提升了33%,时间偏移率减少了73%。     

基于多目标遗传算法的卫星成像任务调度技术

针对成像卫星的任务调度问题,考虑多种约束条件,提出了成像任务约束图模型。基于多目标优化和遗传算法思想,提出了一种应用于卫星成像任务调度的多目标遗传算法,详细分析了算法的各个关键步骤的设计思想,能够求得基于成像约束图模型的满意解,生成卫星的优化拍摄计划。卫星成像任务调度原型系统的实现和实验结果验证了该模型和算法的合理性和有效性。     

LTE中基于排队机制的动态资源预留接纳控制算法

长期演进(long term evolution,LTE)系统中,接纳控制是保证用户服务质量(quality of service,QoS)要求的重要技术之一。针对现有资源预留算法受预留门限值影响较大,且掉线率较高的缺点,提出一种适用于LTE系统的基于排队机制的动态资源预留算法。首先该算法通过设置门限预留部分资源,让切换呼叫直接接入,新呼叫以新定义的请求概率动态接入。其次在系统资源耗尽时,对切换呼叫采取排队机制,等待系统有剩余资源时接入。仿真结果表明,所提算法能有效降低切换呼叫掉线率,提高资源利用率,并且算法受预留门限值的影响较小。     

基于公平原则的应急物资分配模型与算法

灾害发生后,灾区第一时间的自救和互救对于救灾工作至关重要.本文考虑自然灾害发生后,外界的救灾物资没有到达受灾地区的这段时间内,灾区的各个地区基于相互救援的应急物资分配问题.在考虑地区之间物资分配公平性的基础上,本文建立了一个双目标优化模型,模型的目标函数是最大化地区的物资的满足量,以及最小化最大运送时间.进一步地,本文提出了一个改进的差分进化算法求解该双目标优化模型,计算结果从计算时间和解的质量两个方面验证了算法的有效性;同时,本文通过一组例子验证了公平性约束的合理性.最后,本文通过一组算例分析,验证了改进的差分进化算法对大规模问题的有效性,说明救灾物资的最大允许运输时间和地区间合作的关系.论文的研究成果对基于属地管理的灾区自救和互救决策具有重要的理论和实践指导价值.     

Image segmentation algorithm based on high-dimension fuzzy character and restrained clustering network

An image segmentation algorithm of the restrained fuzzy Kohonen clustering network （RFKCN） based on high- dimension fuzzy character is proposed. The algorithm includes two steps. The first step is the fuzzification of pixels in which two redundant images are built by fuzzy mean value and fuzzy median value. The second step is to construct a three-dimensional （3-D） feature vector of redundant images and their original images and cluster the feature vector through RFKCN, to realize image seg- mentation. The proposed algorithm fully takes into account not only gray distribution information of pixels, but also relevant information and fuzzy information among neighboring pixels in constructing 3- D character space. Based on the combination of competitiveness, redundancy and complementary of the information, the proposed algorithm improves the accuracy of clustering. Theoretical anal- yses and experimental results demonstrate that the proposed algorithm has a good segmentation performance.     

Target distribution in cooperative combat based on Bayesian optimization algorithm

1 .INTRODUCTIONThe target distributionis one of difficult content incooperation air combat . The missionis fully exertsthe whole advantage of all firepower units . Thedistributionis finding the best schedule which ac-cord with distribution principles at the moment ofgiven conditions .It can make finitely weapons gainthe best effective through opti mizing method. Theresult is that the effective of weaponis best andthewhole benefits are highest .But the target distribu-tionis restricted wi…     

802.11ax系统中基于OFDMA调度接入的公平性资源分配算法

针对802.11ax系统中基于正交频分多址接入(orthogonal frequency division multiple access, OFDMA)调度接入的上行多用户传输链路, 提出了基于能量效率的公平性子信道匹配和功率分配算法。根据基于能量效率的上行链路模型, 提出资源块(resource unit, RU)数量确定算法和独立子信道匹配与功率分配算法; 进而针对独立分配中频谱利用不足和功率分配不合理的问题, 提出改进的联合子信道和功率迭代分配算法, 通过应用广义分式规划, 改写约束条件并在目标函数中加入惩罚项来松弛整型变量, 进一步用序列凸规划(sequential convex programming, SCP)来求解。仿真结果表明, 通过独立和联合迭代分配功率和子信道, 系统中用户的能量效率相对原有算法得到提升的同时兼顾了用户间的公平性。     

基于优化资源流约束的模具多项目反应调度算法

针对模具多项目执行过程中由于任务拖期而导致的调度计划变更,提出了一种基于优化的资源流约束的反应调度算法. 首先利用基于优先规则的微粒群算法构建一个项目加权工期之和最小的初始调度计划,采用启发式算法建立并优化初始调度计划的资源流网络,并将关键链技术与资源流网络相结合,对初始调度计划进行合理的时间缓冲设置. 然后建立了以调度计划扰动费用最小为优化目标的反应调度模型,并用基于优先规则的微粒群算法进行求解. 最后,通过仿真计算分析了算法的可行性与可靠性,结果表明该反应调度算法在模具多项目动态调度中具有一定的应用价值.     

基于IP-ACO算法的航天器测控资源调度技术

采用多目标蚁群优化算法对航天器测控资源调度问题进行研究。在分析中低轨道航天器测控特点的基础上,综合考虑包括测控时间窗口约束和设备切换时间约束在内的多类复杂约束条件,建立多目标航天器测控资源调度模型。在Pareto蚁群优化算法的基础上,引入蚁群社会中的分工协作思想并构建测控任务时间约束有向图,设计基于任务选择期望的状态转移规则和基于自适应网格技术的权重更新策略,从而提高算法求解性能。仿真实验结果表明该方法能有效解决多目标航天器测控资源调度问题。     

改进差分进化算法求解化工间歇与连续混合生产过程调度问题

采用统一时间离散化方法,用改进的差分进化算法求解带有限中间存储的连续生产过程和间歇生产过程混合的化工生产调度问题.提出随机产生符合容量约束的任务队列组成染色体的新的编码方式,采用块交叉和块变异进化操作. 为了提高算法全局收敛能力,该文对算法的选择操作进行了改进,并通过Logisic混沌映射方法获得交叉算子CR的取值. 最后,通过化工算例仿真来说明模型和算法的有效性.     

基于特征值极限分布的双门限频谱感知算法

针对传统频谱感知算法在较低信噪比和存在噪声不确定度时,检测性能降低的问题,提出了一种基于特征值极限分布的双判决门限频谱感知算法。由于利用了双门限和信号采样协方差矩阵的特征值进行判决,这种算法不但可以有效地克服噪声不确定度对检测性能的影响,而且不需要预先知道主用户信号的任何信息。与已有的最大最小特征值频谱感知算法相比,由于采用了双判决门限,因此该算法的检测性能更优。仿真结果表明,该方法不但可以有效地克服噪声不确定度,而且检测性能也优于最大最小特征值算法。     

基于机会约束规划的机会阵雷达功率资源管理算法

研究了在进行多目标跟踪时机会数字阵列雷达(opportunistic digital array radar, ODAR)的功率资源管理问题。针对复杂多变的环境和未知的目标信息所导致的不确定性,建立了基于随机和模糊机会约束规划(chance constraint programming, CCP)的多目标稳健功率资源管理模型。模型引入随机变量表征雷达总发射功率,引入模糊变量表征每个目标的RCS,以贝叶斯克拉美罗界(Bayesian Cramer Rao lower bound, BCRLB)作为目标跟踪精度的衡量标准,将随机模拟和模糊模拟都嵌入到遗传算法(genetic algorithm,GA)当中,从而预测出下一时刻满足给定置信水平的各目标最优的功率分配,然后根据求解出来的功率分配情况,利用无迹卡尔曼滤波器(unscented Kalman filter, UKF)进行目标跟踪。最后,通过仿真实验验证了算法的有效性和稳定性。     

基于改进遗传算法的多类测控资源调度方法

为了研究一类利用不同测控(telemetry, track and command, TT&C)网联合执行TT&C任务的多类TT&C资源联合调度问题, 首先对国有和商业TT&C网的不同特点进行归纳总结。其次,对问题中的约束条件进行分析和规范化描述, 并在满足所选约束的前提下, 建立问题的数学模型。进而根据问题特点, 以遗传算法为基础, 通过设计适当的编码方法和交叉、变异算子以及约束冲突处理方法, 提出一种改进遗传算法。最后,实例仿真表明, 引入的多类TT&C资源联合调度方法较传统未引入联合调度的方法能有效提高TT&C资源利用效率, 证明了所提算法求解此类TT&C调度问题具有较好的性能。     

限制图上的局内出租车调度与竞争算法

经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解）,其最优性在条件发生变化时就会失去．局内问题与竞争算法则是针对特定的优化问题来研究这样的方法,它在变化因素的每一个特例中都能给出一个方案,使得这一方案所得到的解离最优方案给出的解总在一定的比例之内．本文应用复位策略给出限制图上局内ｋ 出租车调度问题竞争比为１＋ （ｎ－ ｋ）λ的竞争算法．