Uplink scheduling in wireless systems is gaining importance due to arising uplink intensive data services (ftp, image uploads
etc.), which could be hampered by the currently in-built asymmetry in favor of the downlink. In this work, we propose and
study algorithms for efficient uplink packet-data scheduling in a CDMA cell. The algorithms attempt to maximize system throughput
under transmit power limitations on the mobiles assuming instantaneous knowledge of user queues and channels. However no channel
statistics or traffic characterization is necessary. Apart from increasing throughput, the algorithms also improve fairness
of service among users, hence reducing chances of buffer overflows for poorly located users.
The major observation arising from our analysis is that it is advantageous on the uplink to schedule “strong” users one-at-a-time,
and “weak” users in larger groups. This contrasts with the downlink where one-at-a-time transmission for all users has shown
to be the preferred mode in much previous work. Based on the optimal schedules, we propose less complex and more practical
approximate methods, both of which offer significant performance improvement compared to one-at-a-time transmission, and the
widely acclaimed Proportional Fair (PF) algorithm, in simulations. When queue content cannot be fed back, we propose a simple modification of PF, Uplink PF (UPF), that offers similar improvement.
Hereafter, we refer to users with low recieved power at the base even when transmitting at peak transmit power as “weak” users,
and the strongly recieved users at the base as “strong” users.
Krishnan Kumaran is currently a member of the Complex Systems Modeling section in the Corporate Strategic Research of ExxonMobil Corp., Clinton,
NJ. Formerly, he was a Member of Technical Staff in the Mathematics of Networks and Systems Research Department at Bell Labs
in Murray Hill, NJ, where his research interests were in modeling, analysis and simulation of design, resource management
and scheduling issues in telecommunication networks.
Lijun Qian is an assistant professor in the Department of Electrical Engineering at Prairie View A&M University. He received his B.S.
from Tsinghua University in Beijing, M.S. from Technion-Israel Institute of Technology, and Ph.D. from WINLAB, Rutgers University,
all in electrical engineering. Before joining PVAMU, he was a researcher at Networks and Systems Research Department of Bell
Labs in Murray Hill, NJ. His major research interests are in wireless communications and networking technologies, especially
in radio resource management, protocol design, TCP/RLP optimization and MPLS traffic engineering. 相似文献
Future generation wireless multimediacommunications will require efficient Medium AccessControl (MAC) protocols able to guarantee suitable Qualityof Service (QoS) levels for different traffic classes whileachieving a high utilization of radio resources. This paperproposes a new scheduling technique to be adopted at the MAClevel in wireless access systems, named Dynamic Scheduling-Time DivisionDuplexing (DS-TDD), that efficiently managesvideo, voice, Web and background traffics. A theoretical approachis proposed in this paper to evaluate the DS-TDD performance withvoice and Web traffics. Simulation results have permitted tohighlight the following promising characteristics of the DS-TDDscheme: (i) a high capacity of real-time traffics isattained with a QoS insensitive to Web and background trafficloads; (ii) a high throughput can be guaranteed whilepreserving the QoS levels of the different traffic classes;(iii) heavier downlink traffic loads do not modify the QoSof uplink traffics. Finally, extensive comparisons with differentscheduling schemes proposed in the literature have permitted tohighlight the better performanceof DS-TDD. 相似文献
Power-aware systems are those that must exploit a widerange of power/performance trade-offs in order to adapt to the power availabilityand application requirements. They require the integration of many novel powermanagement techniques, ranging from voltage scaling to subsystem shutdown.However, those techniques do not always compose synergistically with eachother; in fact, they can combine subtractively and often yield counterintuitive,and sometimes incorrect, results in the context of a complete system. Thiscan become a serious problem as more of these power aware systems are beingdeployed in mission critical applications.To address the problem of technique integration for power-aware embedded systems, we propose a new design tool framework called IMPACCT and the associated design methodology. The system modeling methodology includes application model for capturing timing/powerconstraints and mode dependencies at the system level. The tool performs power-awarescheduling and mode selection to ensure that all timing/power constraintsare satisfied and that all overhead is taken into account. IMPACCT then synthesizesthe implementation targeting a symmetric multiprocessor platform. Experimentalresults show that the increased dynamic range of power/performance settingsenabled a Mars rover to achieve significant acceleration while using lessenergy. More importantly, our tool correctly combines the state-of-the-arttechniques at the system level, thereby saving even experienced designersfrom many pitfalls of system-level power management. 相似文献
Cancer immunotherapy aims at stimulating the immune system to react against cancer stealth capabilities. It consists of repeatedly injecting small doses of a tumor-associated molecule one wants the immune system to recognize, until a consistent immune response directed against the tumor cells is observed.
We have applied the theory of optimal control to the problem of finding the optimal schedule of injections of an immunotherapeutic agent against cancer. The method employed works for a general ODE system and can be applied to find the optimal protocol in a variety of clinical problems where the kinetics of the drug or treatment and its influence on the normal physiologic functions have been described by a mathematical model.
We show that the choice of the cost function has dramatic effects on the kind of solution the optimization algorithm is able to find. This provides evidence that a careful ODE model and optimization schema must be designed by mathematicians and clinicians using their proper different perspectives. 相似文献
We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space. 相似文献
This paper presents a new scheduling method for manufacturing system based on the Timed Petri Net model and a reactive fast graph search algorithm. The following two typical problems are addressed in this paper. (1) Minimization of the maximum completion time. (2) Minimization of the total tardiness. As for the problem (1), a new search algorithm which combines the RTA∗ and a rule-based supervisor is proposed. As for problem (2), the original Petri Net model is converted to its reverse model and the algorithm developed for the problem (1) is applied, regarding the due date as the starting time in the reverse model. Some numerical experiments are carried out to demonstrate usefulness of our algorithm. 相似文献
We consider the generalization of the classical P||Cmax problem (assign n jobs to m identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2. We briefly survey lower and upper bounds from the literature. We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria. 相似文献
In wireless sensor networks that consist of a large number of low-power, short-lived, unreliable sensors, one of the main design challenges is to obtain long system lifetime without sacrificing system original performance (sensing coverage and sensing reliability). To solve this problem, one of the potential approaches is to identify redundant nodes at the sensing interface and then assign them an off-duty operation mode that has lower energy consumption than the normal on-duty mode. In our previous work [J. Wireless Commun. Mobile Comput. 3 (2003) 271; Processing of ACM Wireless Sensor Network and Application Workshop 2002, September 2002], we proposed a node-scheduling scheme, which can provide a 100% sensing coverage preservation capability. This, however, requires each node to be aware of its own and its neighbors’ location information. Also, in that scheme, each node has to do accurate geometrical calculation to determine whether to take an off-duty status. In this paper, we propose and study several alternative node-scheduling schemes, which cannot completely preserve the original system coverage, but are nonetheless light-weighted and flexible compared with the previous one. Our simulation results compare these schemes with the previous one and demonstrate their effectiveness. 相似文献