复杂约束对地观测卫星成像调度技术研究

 对地观测卫星成像调度需要考虑卫星动作时间切换、存储容量、星上能量等复杂约束,确定要观测的观测目标序列,是一个具有强NP-Hard特性的组合优化问题,一般研究者都对问题约束进行了不同程度的简化.针对一类可见光对地观测卫星小问题规模下的应用,考虑上述多种约束,建立顶点和边都带权的无环路有向图模型,并基于标记更新最短路径算法,采用分层支配和分治思想,提出了复杂约束成像卫星调度算法(SISACC)进行完全路径搜索,得到问题精确解;在此基础上,给出了算法改进措施,分析了完全算法和改进方法的性质;最后通过大量实验验证了算法的适用条件和可行性.该方法已成功应用于某在轨卫星的日常成像调度任务中.     

Internet中支配延迟的特征行为研究

通过对CAIDA机构授权的原始海量样本数据处理得到单向链路延迟,在此基础上计算了路径上最大的链路延迟对端到端延迟的比例以及路径上链路个数分布,基于此定义了支配延迟.针对链路延迟对端到端延迟的影响进行分析,表明支配延迟之间的差异是导致端到端延迟呈现多峰分布的主要原因.支配延迟更多地出现在路径的中间部分和AS自治域内部,说明延迟瓶颈从网络的接入部分向传输部分转移,得出传输延迟在总延迟中的影响逐渐减小,路径中的支配延迟将主要由传播延迟决定的结论.     

用基于路径的流汇集调度提高延迟性能

文章介绍了基于路径的汇集调度的基本方法，提出了一个新的汇集器算法，分析了路径汇集的延迟性能和影响性能的因素，并用大量的实验考察了基于路径的流汇集调度在性能方面的特点。实验结果表明，基于路径的流汇集调度在提高扩展性的同时，可以为实时应用提供满意的延迟保证，其性能在一定条件下甚至优于每流状态的调度。     

嵌入学习效应的多目标应急伤员手术调度

为了合理高效地解决突发事件后医院手术室资源调度问题,本文在经典车间调度模型的基础上,提出了应急手术调度模型。以手术室救治总成本最低以及伤员的手术完成时间最短为目标,重点考虑了学习效应对手术完成时间的影响,并对比分析了不同学习因子下的调度结果。利用带有精英策略的非支配排序遗传算法求解多目标手术调度问题,并通过仿真对比实验证明了模型和算法的有效性。     

多卫星成像任务规划的冲突消解

分析了多卫星成像任务规划中多卫星之间的任务冲突,印多卫星成像任务冲突和多卫星下传任务冲突,研究了这两类冲突的消解方法;提出了基于拍摄概率的多卫星成像任务冲突消解算法和基于非互斥链的多卫星下传任务冲突消解算法.将多卫星成像任务规划问题转换成各卫星独立的成像调度问题,从而降低了问题的复杂度.实验表明,该方法解决了多卫星之间的冲突问题,使星地资源得到均衡有效的利用.     

最小化延迟的无线传感器网络节点调度算法

如何实现节能和减小延迟一直是无线传感器网络中研究的热点及难点问题。提出一种新的最小化延迟的能量均衡的节点调度（MDS）算法,算法通过对能量以及延迟的分析计算,计算出节点的能量判定阈值,并在选择下一跳的时候,总是选择节点剩余能量在限定范围内且延迟最小的节点,以此实现最小化网络延迟的目的。理论分析及实验结果表明,MDS算法能够较好地把网络的生命周期控制在可接受范围内,同时可以解决在能耗限定条件下的最小化延迟的问题。     

基于有效路径统计网络的群组命令传输模型

Internet在动态环境及资源有限条件下,其尽力而为的服务模式在支持群组命令传输过程中,容易产生路径过期无效及路径竞争问题.对此,定义出有效路径统计网络,并提出基于有效路径统计网络的群组多约束多目标优化问题.针对该问题,提出基于有效路径统计网络的群组命令传输模型.为解决路径无效过期,该模型基于动态追逐解的思想提出基于动态环境下群体激励算法.为解决路径竞争,该模型分别从竞争选择策略以及避让选择策略两个角度分析了路径竞争问题.最后,本文分别证明模型的收敛性和有效性.实验分别从响应延迟率及传输成功率等方面,验证了该模型在支持群组命令传输的合理性.     

基于深度强化学习的医用设备应急调度优化技术研究

针对大型医用设备人工管理效率低、无法满足应急调度需求的问题,文中提出了基于深度强化学习算法的医用设备应急调度优化技术.使用物联网技术采集大型医用设备日常使用的各类参数,作为后续调度优化算法的样本数据.通过对医用设备调度问题的分析,采用马尔可夫决策过程作为调度优化算法的基础模型,并给出了状态空间、动作空间以及奖惩函数的定...     

Internet的访问时间分析

通过CAIDA组织提供的海量样本数据,首先对Internet访问时间进行分析,发现访问时间服从多峰重尾分布。在此基础上对Internet的访问直径与访问时间之间的关系从整体和局部样本进行研究,认为链路延迟是导致相近的访问直径其访问时间相差较大的主要原因,并提出修正算法从样本数据得到链路延迟。对链路延迟样本数据的统计结果表明,超过90%以上的路径其最大的链路延迟占访问时间的1/4以上,并以此定义了支配延迟。最后得出访问时间主要受支配延迟影响,正是由于支配延迟本身导致了相近的访问直径其访问时间存在较大差异的结论。     

基于遗传-启发算法的微动目标认知ISAR成像资源调度

认知逆合成孔径雷达（Inverse Synthetic Aperture Radar,ISAR）将认知雷达理论与ISAR成像技术相结合，利用目标与环境的离线先验知识及在线感知结果，提升ISAR在复杂环境下的成像能力.与传统单脉冲雷达相比较，相控阵ISAR可实现波束的快速扫描，因此具备多目标观测能力.在实际空间微动目标成像场景中，相控阵ISAR很可能存在多波束多目标情况.为实现系统效能的充分发挥，需要在系统能量、时间资源有限条件下实现成像任务有效调度.然而，面向成像任务的资源调度方法主要针对刚体目标，其约束条件及调度模型并不适用于微动目标，并且存在求解方法稳定性差、调度成功率不高等问题.此外，微动目标运动形式复杂，回波非平稳性很强，且方位缺损时难以聚焦成像.因此，迫切需要针对微动目标的特性，研究有效的ISAR资源调度和高分辨成像方法.针对上述问题，本文提出基于遗传-启发算法的微动目标认知ISAR成像资源调度方法 .该方法首先根据微动目标认知结果计算其成像所需的雷达资源及综合优先级；接着基于脉冲交错技术，在时间、能量双重约束下建立微动多目标资源调度模型.在此基础上，本文提出了基于遗传-启发...     

Shortest route mobility assisted packet delivery with soft maximum delay guarantees in mobile ad hoc networks

In delay tolerant Mobile Ad hoc Networks (MANETs) node mobility can be exploited in order to reduce the source–destination path lengths in the expense of higher packet delivery delays. This paper addresses the problem of minimizing the average source–destination path length under a maximum delay constraint for packet delivery which is desirable to certain applications. Imposing packet delivery deadlines results in a certain percentage of multi-hop packet transmissions and poses the practical problem of selecting the optimum moment for the transmission. We propose an Optimal Stopping Rule algorithm for solving this problem and show how this algorithm can be extended in the case that a source–destination route is not always available by relaxing the hard delay constraint to a soft (probabilistic) constraint. The performance of this algorithm is compared to the ideal case of scheduling with perfect knowledge of the future and the trade-off between higher allowable delay and lower average path length is illustrated through several Matlab and ns-2 simulation results. As an application of path length minimization we explain how this can lead to energy consumption minimization in a MANET with light traffic loads (low probability of collisions). Finally, we briefly discuss how this path length minimization algorithm can guide the development of cross-layer throughput maximization algorithms with soft maximum delay guarantees.     

基于离散粒子群算法的数据中心网络流量调度研究

数据中心网络利用多个并行路径为集群计算等网络服务提供高对分带宽.然而,现有的流量调度算法可能会引起链路负载不均衡,核心交换机冲突加剧,造成网络总体性能降低.本文将流调度问题转化成0-K背包问题求解,提出基于离散粒子群的流调度算法DPSOFS（Discrete Particle Swarm Optimization Flow Scheduling）.该算法根据Fat-Tree结构特点定义了粒子速度、位置和运算规则,以两次迭代冲突流个数差值作为目标函数,并限定路径搜索范围,减少随机搜索的盲目性.仿真实验验证了该算法对减少流冲突快速有效,能提高网络对分带宽.     

Energy efficient path selection for mobile sink and data gathering in wireless sensor networks

Mobile sink (MS) has drawn significant attention for solving hot spot problem (also known as energy hole problem) that results from multihop data collection using static sink in wireless sensor networks (WSNs). MS is regarded as a potential solution towards this problem as it significantly reduces energy consumption of the sensor nodes and thus enhances network lifetime. In this paper, we first propose an algorithm for designing efficient trajectory for MS, based on rendezvous points (RPs). We next propose another algorithm for the same problem which considers delay bound path formation of the MS. Both the algorithms use k-means clustering and a weight function by considering several network parameters for efficient selection of the RPs by ensuring the coverage of the entire network. We also propose an MS scheduling technique for effective data gathering. The effectiveness of the proposed algorithms is demonstrated through rigorous simulations and comparisons with some of the existing algorithms over several performance metrics.     

A novel scheme using the information of departure processes fordelay guarantees of distributed VBR traffic

In this paper, we consider the problem of providing delay guarantees in a distributed environment, e.g., a wireless network or a cable network. In a distributed environment, the information of the arrival process is, in general, not available to the network. Due to the lack of such information, traffic regulators and scheduling policies discussed in the literature cannot be directly applied. To cope with the problem, we propose a distributed traffic regulator (DTR) that uses the information of the departure process. Based on such DTRs, we propose the distributed earliest deadline first (DEDF) scheduling policy. For the DEDF scheme, we derive an admission-control criterion and show that the maximum delay can be guaranteed if the criterion is satisfied     

分簇拓扑下backpressure算法的延迟性改进研究

Backpressure算法是一种自适用的路由调度算法,它从理论上解决throughput-optimal问题,但是在实际网络部署中,存在节点维护数据队列的数量繁多和数据路由繁长问题,致使数据传输延迟较长。文中就此问题出发,把backpressure算法应用到分簇拓扑上,使用shadow算法实现backpressure算法下的路由调度,采用LIFO策略调度队列,同时又对路径选择了做了优化。仿真结果表明,数据传输的延迟性大大降低。     

两约束路由问题的近似解法

首先回顾了一些重要的QOS路由算法，然后对关于两约束路由问题(BCP,bi—constraint path problem)的线性搜索算法进行了数学分析，确定了搜索因子的范围和最佳搜索因子的值。基于以上分析，我们给出了BCP和单约束最短路径问题(RSP,restricted shortest path problem)的近似算法，并对算法性能进行了分析；最后，本文研究了采用非线性链路代价函数求解BCP。测试结果表明本文提出的算法是求解BCP和RSP的有效算法。     

区域多任务安全隐患排除的机器人调度策略

针对灰狼优化算法易陷入局部最优且单一算法不易解决障碍物空间多机器人隐患搜排的调度问题,提出了一种分步引导式多机器人安全隐患协同排除调度策略。首先引入非线性收敛因子调整策略和静态加权平均权重策略改进灰狼优化算法以避免算法陷入局部最优;随后通过改进的灰狼优化算法先后两次求解遍历顺序,引导机器人规划搜索路径与排除隐患点路径;最后在领航者-跟随者模型的基础上多机器人编队与队形变换避障,逐一到达隐患点位置实现多机器人的调度策略。通过国际通用6个基准函数进行测试,改进的灰狼优化算法在收敛速度、搜索精度及稳定性上均有明显提高,验证了区域多任务安全隐患排除的分步引导式多机器人协同调度策略的有效性。     

Local Coordination Based Routing and Spectrum Assignment in Multi-hop Cognitive Radio Networks

Although Cognitive Radio technology brings efficient spectrum usage and effective interference avoidance, it also brings new challenges to routing in multi-hop Cognitive Radio Networks. Firstly, spectrum assignment is required for each hop in routing; secondly, new delay is introduced during multi-frequency scheduling and frequency switching in each node; thirdly, the intersecting nodes serving multi-frequency traffic is easy to be bottleneck in neighborhood region. In this paper, we analysis and model the per-node delay and the path delay in multi-hop Cognitive Radio Network. Then we propose a framework of local coordination based routing and spectrum assignment to solve above problems, which consists of one protocol for routing path and one scheme for neighborhood region. A on-demand Routing and Spectrum Assignment Protocol is proposed to exchange the local spectrum information and interact with multi-frequency scheduling in each node. A local coordination scheme is presented to support flow redirection at an intersecting node and distribute heavy multi-frequency workload to its neighborhood. We prove the correctness and effectiveness of the protocol by thorough simulations, and find that the proposed solution provides good adaptability to varying spectrum distribution. The end-to-end delay when adaptive relay is cooperating with routing protocol outperforms traditional bare-routing solutions.     

Nonpreemptive Scheduling of Optical Switches

Many high-speed routers today use input-queuing (IQ) architectures with a crossbar switching fabric based on optical technology. Packets in the input queues are divided into cells of unit length, and the goal is to find a schedule of minimum makespan that forwards all packets to the output ports. The problem is complicated since, in optical switches, so-called configuration delay, that is the time required to reconfigure the switching fabric, is non-negligible with respect to the cell transmission time. We aim to design a scheduler whose complexity does not depend on the number of packets in the input queues. Thus, we focus on the nonpreemptive bipartite scheduling (NPBS) problem, where each input queue is connected to each output port in at most one configuration. We demonstrate that the NPBS problem is NP-hard for any value of the configuration delay, and approximation within a ratio smaller than 7/6 is NP-hard as well. For the offline version of the NPBS problem, we show that a simple greedy algorithm achieves an approximation factor of 2 for arbitrary configuration delay. Then, we consider the online version of the NPBS problem, where the switch gathers the incoming traffic periodically and then schedules the accumulated batches. We propose a scheduling algorithm that guarantees strict delay for any admissible traffic, provided that the switch has a moderate speed-up of two. Finally, we extend our results to the nonbipartite scheduling problem.