With voltage frequency islanding (VFI) we are able to change the voltage and frequency of the processors to save power within a certain performance constraint. In this work we want to maximize potential power savings ...
详细信息
ISBN:
(纸本)9781509001736
With voltage frequency islanding (VFI) we are able to change the voltage and frequency of the processors to save power within a certain performance constraint. In this work we want to maximize potential power savings and minimize time penalty by means of efficient task scheduling in VFIs. A new scheduling algorithm is presented which schedules the tasks onto the processing cores in the VFI by ranking them based on the computation load and communication load among other tasks. The mapping of the tasks is relevant to the processing speed of the cores and the simulation results show improvements compared to the default task scheduler of Linux.
For designing a general scheduling platform, this part of paper discusses logic and process abstraction that can be implemented to different kind of space missions. A logic model extension solution is given to allow d...
详细信息
ISBN:
(纸本)9781467391054
For designing a general scheduling platform, this part of paper discusses logic and process abstraction that can be implemented to different kind of space missions. A logic model extension solution is given to allow defining specific mission related data patterns with custom manipulation methods. The scheduling elements, requirement, inputs and outputs are organized in one solution for estimation and verification. All the scheduling constrains are abstracted into expressions for simplification. A protocol is proposed for reinforcement heuristic algorithms besides internal ones, with which the process of problem solving is controllable. With the basic abstraction methods, a common framework capable for general space mission scheduling is set up, ensuring the general mission scheduling platform with great flexibility and extensibility.
Fixed priority scheduling is used in many real-time systems, however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algori...
详细信息
Fixed priority scheduling is used in many real-time systems, however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP), which since it matches a recently published upper bound gives the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, i.e., there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive upper and lower bounds on the speed-up factor required to guarantee FP-P feasibility of any FP-NP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speed-up factor in this case.
In this paper, we propose a utility-based scheduling framework to maximize and improve the users' quality-of-service (QoS) satisfaction in broadband wireless access system. The scheduling framework comprises of th...
详细信息
In this paper, we propose a utility-based scheduling framework to maximize and improve the users' quality-of-service (QoS) satisfaction in broadband wireless access system. The scheduling framework comprises of three novel radio resource allocation (RRA) techniques; delay-based scheduling policy for real-time (RT) services using a sigmoid-like utility function, minimum-rate-based scheduling policy for non-real-time (NRT) services which obeys the law of diminishing marginal utility and a throughput-based scheduling policy for best-effort (BE), also based on the law of diminishing marginal utility but without a minimum rate requirement. The proposed algorithm, called maximum QoS satisfaction (MQS), is efficient and of low complexity as it specifies only a single parameter for different class of services. To prove its efficiency, we compare it with the delay-based satisfaction maximization and throughput-based satisfaction maximization (DSM/TSM), which exhibits similar characteristics in terms of resource allocation objectives. System-level simulation results demonstrate that the MQS achieves superior user call satisfaction performances in a multi-user heterogeneous traffic scenario.
Mixed-criticality systems emerged with the aim of reconciling safety requirements and efficient use of multi-processor or uniprocessor platforms. On multi-processors, recent works on mixed-criticality have produced im...
详细信息
Mixed-criticality systems emerged with the aim of reconciling safety requirements and efficient use of multi-processor or uniprocessor platforms. On multi-processors, recent works on mixed-criticality have produced impressive results in terms of speed-up factor. But these solutions, based on Pfair-like scheduling algorithms, entail too many preemptions and migrations to be effectively used in real systems. As RUN is an optimal scheduling algorithm that is known to limit this problem, we propose MxC-RUN, an adaptation of RUN to mixed-criticality systems. We redefine RUN's primal servers as modal servers that allocate the overestimated time budget of their higher criticality tasks to execute lower criticality ones. These servers can be handled by RUN without any modification and preserve its performances in terms of preemptions and migrations. MxC-RUN earns a speed-up factor smaller than other multi-processors EDF-based mixed-criticality scheduling algorithms.
A Body Area Network (BAN) is a radio standard for wireless connectivity of wearable and implantable sensors located inside or in close proximity to the human body. Medical and some other applications impose stringent ...
详细信息
A Body Area Network (BAN) is a radio standard for wireless connectivity of wearable and implantable sensors located inside or in close proximity to the human body. Medical and some other applications impose stringent constraints on battery powered BAN reliability, quality of service, and power consumption. However, lack of coordination among multiple colocated BANs in the current BAN standard may cause unacceptable deterioration of BAN reliability and quality of service due to high levels of inter-BAN interference. Assuming Time Division Multiple Access (TDMA), this paper proposes inter-BAN interference mitigation using several novel uncoordinated transmission scheduling algorithms. These algorithms use patterns of past and current interference for implicit coordination across multiple BAN transmissions. Simulation results demonstrate improvement in the performance and potential benefits of the proposed strategies.
The crucial issue in the design of resource allocation algorithms for wireless mesh network is computational complexity. A high capacity algorithm with low computational complexity is desired, especially for dynamic t...
详细信息
The crucial issue in the design of resource allocation algorithms for wireless mesh network is computational complexity. A high capacity algorithm with low computational complexity is desired, especially for dynamic topology adaptation in mobile mesh networks and also for the issue of low energy consumption. This paper proposes a new approach in the designing of a low complexity spatial time division multiple access link scheduling algorithm for wireless mesh network. In this paper, link scheduling is considered as a decision-making problem. This approach is contrary to physical interference model that requires SINR evaluation in global network. We propose the mesh coverage probability as a new performance metric in the design of mesh link scheduling algorithm. Based on this approach, we provide the tradeoff between spatial reuse and mesh coverage probability, which can be used as a benchmark in the design of scheduling algorithms for wireless mesh network.
Content-Centric Networking (CCN) facilitates the content distribution for static Web applications due to its in-network caching. However, when it comes to dynamic Web request, the original fair scheduling of Interest ...
详细信息
ISBN:
(纸本)9781467396899
Content-Centric Networking (CCN) facilitates the content distribution for static Web applications due to its in-network caching. However, when it comes to dynamic Web request, the original fair scheduling of Interest packets on the CCN Web server (i.e. without differentiating a new service request and the service requests being processed) increases the mean response time, resulting in a decrease of service performance. To address this problem, we present a Priority-based Dynamic Web Requests scheduling (called PBDRS) for CCN Web server. We first increase the priority of the subsequent Interest packet requests belonging to dynamic Web requests being processed, based on the first-come-first-served strategy. Then, services with small-size response data are also scheduled to a higher priority, leveraging the shortest remaining processing time (SRPT) scheduling policy. To validate the proposed approach, we implemented the proposed PBDRS mechanism in our existing CCN Web server and conducted the performance evaluation experiments based on a real dataset crawled from three popular dynamic Web sites of China in a trace-driven way. Experimental results indicate that PBDRS outperforms existing fair scheduling approach of Interest packets in terms of the mean response time.
Machine Type Communication (MTC) is gaining an enormous interest among communication industry and academia all around the world. The variety of services offered by MTC is expected to significantly increase the number ...
详细信息
Machine Type Communication (MTC) is gaining an enormous interest among communication industry and academia all around the world. The variety of services offered by MTC is expected to significantly increase the number of MTC Devices (MTCD) on wireless networks. The huge number of MTCD poses several challenges to cellular network operators such as efficient radio resource management, energy efficiency (EE) etc. Two main radio resource management techniques to support MTC over 4G Long Term Evolution (LTE) were proposed in the literature: Group Based scheduling (GBS) and Time Granularity scheduling (TGS). In this paper, we compare the EE of GBS and TGS by formulating a general expression for the downlink transmit power by eNodeB. The numerical results show that the GBS is more energy efficient that TGS under given quality of service constraints.
This paper studies the link scheduling problem in multihop wireless networks without future packet arrivals, with an aim of minimizing the time interval needed for evacuating all the existing packets. We consider the ...
详细信息
ISBN:
(纸本)9781479984299
This paper studies the link scheduling problem in multihop wireless networks without future packet arrivals, with an aim of minimizing the time interval needed for evacuating all the existing packets. We consider the scenario with single-hop traffic flows under the one-hop interference model. In this setting, the minimum evacuation time problem is equivalent to the classic multigraph edge coloring problem, which is generally NP-hard. Although many approximation algorithms have been studied, almost all of them require computing the schedules (or the colors) all at once, and thus have a complexity that is dependent on the number of packets in the network. This, however, renders these algorithms unsuitable for the considered application of link scheduling for packet evacuation, as they typically incur an impractically high complexity when there are a large number of initial packets waiting to be transmitted, even if the underlying network has a small size (i.e., the node count and the link count). Instead, it is desirable to compute the schedules (or the colors) in an online fashion, i.e., to quickly compute one schedule at a time. Unfortunately, none of the existing online algorithms can guarantee an approximation ratio better (or smaller) than 2. To that end, in this paper we suggest two scheduling algorithms using a node-based approach, and prove that their approximation ratios are both no worse (or greater) than 3/2. In addition, these scheduling algorithms can also serve as an alternative for achieving Shannon's bound, which is well known in the graph coloring literature.
暂无评论