Approximation Algorithms for Time-Constrained Scheduling on Line Networks

We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints.     

线性网络上分布式任务调度算法

针对一种已有的分布式计算理论模型(单位长度的任务由处理器独立产生，没有全局控制，彼此通信需要花费时间)，研究了在线性网络上的任务有效调度问题．通过考虑算法中任务处理时间和通信时间之间的平衡，给出了一个近似比为5．88的分布式算法，该算法无需全局信息，且处理策略简单．对该问题的近似比下界也做了研究，证明了该问题不存在近似比小于1．16的算法．     

时间约束调度中功能单元的下限估算

针对高层次综合中时间约束下的调度问题,提出了对功能单元的2种下限估算算法：单位长度调度法和最大网络流法．其主要思想是将原调度问题的不同约束放松,得到多项式可解的新问题,并使得新问题的最优解是原调度问题的下限值．将2种算法与已有的最小重叠法和整数线性规划给出的最优解做了理论和实验上的比较．实验结果表明：2种估算算法运行时间合理,并且单位长度调度法比最小重叠法更准确．最后总结了各种约束对下限估算准确性的影响．     

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes

Abstract. The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multinode network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline. The objective is to schedule the maximum number of packets subject to deadline constraints. This problem is studied in [1], where it is shown that the problem is NP-Complete even when the underlying topology is a linear array. Approximation algorithms are also provided in [1] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be. In this paper we extend the results of [1] in two directions. First, we consider the more general network topologies of trees and two-dimensional meshes. Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are scheduled subject to their timing constraints. For the bufferless case, we provide constant factor approximation algorithms for the time-constrained scheduling problem with weighted packets on trees and meshes. We also provide logarithmic approximations for the same problems in the buffered case. These results are complemented by new lower bounds, which demonstrate that we cannot hope to achieve the same results for general network topologies. For example, we show that if k packets are required to follow prescribed paths in an arbitrary graph, then unless NP = ZPP, there is no polynomial-time k ^1-ε -approximation, for any ε > 0 , to the optimal set of packets that can be scheduled.     

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes

The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multinode network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline. The objective is to schedule the maximum number of packets subject to deadline constraints. This problem is studied in [1], where it is shown that the problem is NP-Complete even when the underlying topology is a linear array. Approximation algorithms are also provided in [1] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be. In this paper we extend the results of [1] in two directions. First, we consider the more general network topologies of trees and two-dimensional meshes. Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are scheduled subject to their timing constraints. For the bufferless case, we provide constant factor approximation algorithms for the time-constrained scheduling problem with weighted packets on trees and meshes. We also provide logarithmic approximations for the same problems in the buffered case. These results are complemented by new lower bounds, which demonstrate that we cannot hope to achieve the same results for general network topologies. For example, we show that if k packets are required to follow prescribed paths in an arbitrary graph, then unless NP = ZPP, there is no polynomial-time k1-ε -approximation, for any ε > 0 , to the optimal set of packets that can be scheduled.     

无线网络中的在线信道分配问题

研究一个无线网络中信道分配的最大化问题.对该问题的离线版本给出了一个O(n2)时间的算法.对在线问题的一般情况,证明了k-look-ahead算法的下界至少为(k 2)*/(k 1);还给出了一个竞争比为2的1-look-ahead算法.     

具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则Flowshop问题可以转化为单机问题.     

Time-Constrained Keyframe Selection Technique

In accessing large collections of digitized videos, it is often difficult to find both the appropriate video file and the portion of the video that is of interest. This paper describes a novel technique for determining keyframes that are different from each other and provide a good representation of the whole video. We use keyframes to distinguish videos from each other, to summarize videos, and to provide access points into them. The technique can determine any number of keyframes by clustering the frames in a video and by selecting a representative frame from each cluster. Temporal constraints are used to filter out some clusters and to determine the representative frame for a cluster. Desirable visual features can be emphasized in the set of keyframes. An application for browsing a collection of videos makes use of the keyframes to support skimming and to provide visual summaries.     

传感器网络中数据驱动的睡眠调度机制

在能量受限的传感器网络中,尽量延长网络寿命同时保证服务质量(如感知覆盖和数据完整)是关键的研究问题.节点睡眠调度能有效延长网络寿命.研究数据驱动的睡眠调度机制,利用感知数据的时空相关性识别冗余节点.核心思想是用非参数回归方法为节点建立预测模型,求解最大支配数的节点支配集,调度多个支配集轮流工作.睡眠节点的数据可以由支配集节点恢复.分别给出集中式、半分布式和分布式3个睡眠调度方法.据知,这是第1个将统计回归模型用于睡眠调度并扩展到大规模网络的研究.实验结果表明,该方法能够有效地减少活跃节点个数,节省能耗从而延长网络寿命,同时在用户指定误差范围内保证数据的完整性.     

面向延迟容忍网络的传输调度算法

由于延迟容忍网络(DTN)的两个节点之间路径呈间歇性且每个节点的存储量有限,使得传统网络中广泛使用的协议大多不适用于延迟容忍网络(DTN)。为了避免DTN中的节点出现缓存溢出现象,通过建立DNT结构模型并定义了数据流与网络节点最大占用的比率,提出了一种基于改变节点之间接触时间长度的传输调度算法,利用较小比率的传输路径来限制传输,以便为较大比率的传输路径腾出更多的传输空间,通过实验仿真表明,所提算法可以有效避免节点的缓存溢出且增加了网络吞吐量,进而提高了整体的网络性能。     

无线网络冲突感知广播调度算法*

文章在协议干扰模型下,通过证明、计算、仿真实验等方法,提出了一个冲突感知广播调度算法（简称CBS算法）,以解决无线网络中的广播调度延迟问题。研究结果表明,CBS算法能够保证节点在广播调度过程中不会相互干扰,避免冲突产生;只需发送少量消息,就能完成网络广播调度;能够同时调度广播树中多个层的节点进行传输,有效地提高了网络信道的利用率。仿真实验结果表明,CBS算法能在较短的时间内完成广播调度,有效地降低了广播延迟。     

Many-to-Many Communication in Radio Networks

Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both undirected and directed networks, working in time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks working in time with high probability (whp), and we show that any deterministic protocol requires time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the m2m ad hoc problem requires expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network on which the protocol requires time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n). The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science 4305, Springer, Heidelberg, pp. 258–272. The work of B.S. Chlebus was supported by NSF Grant 0310503.     

资源约束网络的优化带宽调度

在资源约束的网络控制系统中, 控制性能和服务质量之间的折衷是不可避免的. 为了寻求它们的最佳结合点, 提出了结合约束条件的多目标规划问题来优化控制性能和网络带宽需求. 考虑算法的非线性逼近能力和计算速度, 采用了神经网络作为优化求解器. 它提供的优化解对每一个控制回路的带宽需求进行动态分配, 使得全局系统性能最大化的同时使带宽需求最小化. 仿真表明在网络控制应用中该优化策略对控制性能和网络带宽需求之间是一种有效的折衷方法.     

线性规划算法在车辆调度中的应用

本文首先介绍了线性规划理论及其在一般运输问题中的应用;然后将其推广到车辆调度问题,提出并建立了一个动态的、开放的现代智能车辆管理调度系统模型;最后对各种模型求解算法进行了比较和分析,并给出了计算结果。     

有向传感器网络最大覆盖调度算法

与传统的全向传感器不同,有向传感器可以切换到不同的方向,并且每个方向覆盖有限角度的感应范围.针对有向传感器网络的区域覆盖问题,研究了“最大有向区域覆盖”MDAC(maximum directional area coverage)问题,期望通过调度传感器的工作方向,最大化覆盖区域面积.首先给出了MDAC 的问题定义,使用整数线性规划描述MDAC 问题,并且证明其是NP 完全的.然后提出一种分布式贪心算法DGreedy(distributed greedy algorithm)解决MDAC 问题.在此基础上,通过计算可能的覆盖贡献比例来反映网络拓扑信息.还提出了一种增强的算法PGreedy(distributed probability-enhanced greedy algorithm)使覆盖区域更大.证明了所提算法的收敛性,并通过详细的模拟实验验证了其有效性.     

线型无线传感器网络中的节点调度算法

线型无线传感器网络是一种较为特殊的无线传感器网络类型,其传感器节点的分布区域接近线型区域。在满足监控性能的要求下,通过调度节点,让部分节点工作,其余节点休眠,可有效延长系统生命期。现有的调度算法在线型无线传感器网络下的性能不是很好,针对线型无线传感器网络的特点,提出了异步调度算法和同步调度算法。仿真实验表明,同步调度算法得到的覆盖集的大小为异步调度算法的76%左右,平均覆盖度接近理想最优情况。     

AD hoc网络中的机会分组调度算法

无线多跳Ad hoc网络中节点在业务发送过程中需要竞争共享信道,容易发生局部拥塞导致网络性能下降,而且节点内部采用的先入先出(FIFO)队列容易使队头阻塞,影响队列中后续分组的发送。本文提出了一种机会分组调度算法CBOS,发送节点采用多播RTS的方式同时指向多个接收节点,可以支持可变长分组,提高了Ad hoc网络的空间重用率,接收节点根据拥塞程度按照一定概率返回CTS,有利于节点网络的拥塞控制。仿真结果表明,该算法提高了网络端到端的饱和吞吐量和信道利用率,并提高了业务流之间的公平性。     

视觉传感器网络节点方向调度算法

视觉传感器网络中节点感知模型为有向感知模型,感知范围被限定在节点的视野范围内.节点拥有多个感知方向,在一个工作时刻,节点只能工作于一个方向.针对视觉传感器网络的有向感知模型的点目标覆盖问题,提出一种贪婪算法(GreedyAlgorithm),在优化网络对于目标点覆盖的同时,解决了节点自身覆盖冲突的问题.在此基础上,引入贡献率概念反映节点在其感知方向上对于覆盖的贡献,提出了基于贡献率的贪婪算法(Contribution Rate Greedy Algorithm)以增大网络覆盖率.仿真实验表明了该算法的有效性.     

Effective Routing and Scheduling in Adversarial Queueing Networks

In an adversarial queueing network, the incoming traffic is decided by an adversary, who operates under a reasonable rate restriction. This model provides a valuable, complementary point of view to that of the traditional queueing network model in which arrivals are modeled by stochastic processes. As a result, the adversarial queueing network model has attracted much attention in recent years, especially as a way of modeling packet injections into a communication network. Our main result is a simple, effective packet routing and scheduling algorithm with a provably good performance. Specifically, our algorithm keeps the system stable (bounded number of packets in the system), with the bound on the number of packets in the system that is O((1 - r)^-1), where r can be interpreted as the arrival rate of the packets into the communication network. This improves upon the work of Gamarnik, who designed an algorithm for which the number of packets in the system is O((1 - r)^-2); moreover, our result matches the traditional queueing-theoretic number-in-system bound.