An on-demanded data broadcasting scheduling considering the data item size

Compared with conventional data broadcasting, on-demand data broadcasting is adaptive and real-time, which can better reflect the actual needs of mobile users. Current researches do not consider the attribute of data item size, and the constantly changing characteristics of data item size in on-demand data broadcasting is non-ignorable. This paper introduces the split strategies and backpacks theories into on-demand data broadcasting scheduling to deal with the inconsistencies of data item size, and proposes two scheduling models under different split strategies: (1) equal split scheduling model ES-LxRxW, which proposes the equal splitting strategy (ES) and a deadline adjust strategy. (2) Unequal split scheduling model US-LxRxW, which proposes the unequal split strategy (US) and two effective scheduling algorithms priority first (PF) and propriety and bandwidth first (PxBF). Extensive experiments shows that ES-LxRxW and US-LxRxW can both improve bandwidth utilization and dynamically adjust to the real-time situation of data item size, which takes into account data item size, bandwidth, cycle and scheduling priority of data item. The two proposed scheduling models could reach or outperform the other state-of-the-art scheduling algorithms without considering data item size in the performance of request drop ratio. US-LxRxW can also better reflect the real-time changes of data items than ES-LxRxW, and the proposed PF and PxBF algorithms can effectively improve the bandwidth utilization and reduce the split times.

     

Adaptive Dissemination of Data in Time-Critical Asymmetric Communication Environments

The proliferation of new data-intensive applications in asymmetric communication environments has led to an increasing interest in the development of push-based techniques, in which the information is broadcast to a large population of clients in order to achieve the most efficient use of the limited server and communication resources. It is important to note that quite often the data that is broadcast is time-critical in nature.Most of the related current research focuses on a pure push-based approach (Broadcast Disks model), where the transmission of data is done without allowing explicit requests from the users. More recently, some bidirectional models incorporating a low-capacity uplink channel have been proposed in order to increase the functionality of the Broadcast Disks model. However, the impact of integration of the uplink channel has been investigated using only static client profiles or ignoring the existence of time-sensitive data. None of the existing models integrates all the characteristics needed to perform effectively in a real-world, dynamic time-critical asymmetric communication environment.In this paper we present an adaptive data dissemination model and the associated on-line scheduling algorithms. These improve the functionality and performance of bidirectional broadcast models, maximizing the total number of satisfied users in asymmetric communication environments with dynamic client profiles and time requirements (e.g., mobile systems). This is achieved by means of dynamic adaptation of the broadcast program to the needs of the users, taking into account the bandwidth constraints inherent in asymmetric communication environments and the deadline requirements of the user requests. Performance is evaluated by simulation of a real-time asymmetric communication environment.     

On real-time databases: concurrency control and scheduling

In addition to maintaining database consistency as in conventional databases, real-time database systems must also handle transactions with timing constraints. While transaction response time and throughput are usually used to measure a conventional database system, the percentage of transactions satisfying the deadlines or a time-critical value function is often used to evaluate a real-time database system. Scheduling real-time transactions is far more complex than traditional real-time scheduling in the sense that (1) worst case execution times are typically hard to estimate, since not only CPU but also I/O requirement is involved; and (2) certain aspects of concurrency control may not integrate well with real-time scheduling. In this paper, we first develop a taxonomy of the underlying design space of concurrency control including the various techniques for achieving serializability and improving performance. This taxonomy provides us with a foundation for addressing the real-time issues. We then consider the integration of concurrency control with real-time requirements. The implications of using run policies to better utilize real-time scheduling in a database environment are examined. Finally, as timing constraints may be more important than data consistency in certain hard realtime database applications, we also discuss several approaches that explore the nonserializable semantics of real-time transactions to meet the hard deadlines     

Client-Side Caching Strategies and On-Demand Broadcast Algorithms for Real-Time Information Dispatch Systems

In this work, we propose a broadcast algorithm called Most Request Served (MRS) and its variants with caching strategies for on-time delivery of data in Real-Time Information Dispatch System. This family of algorithms consider request deadline, data object size and data popularity in making scheduling decisions. Although previous scheduling algorithms also base on some or all of these attributes to choose the most beneficial data to be broadcast, they did not consider the loss brought by their scheduling decisions. However, MRS considers both gain and loss in making a scheduling decision. We have performed a series of simulation experiments to compare the performance of various algorithms. Simulation results show that our proposed broadcast algorithm not only succeeds in providing good on-time delivery of data but at the same time provides 20% of improvement in response time over traditional scheduling algorithms like First-In-First-Out (FIFO) and Earliest-Deadline-First (EDF). Simulation results also show that our proposed caching strategy provides further improvement in terms of percentage of requests finished in time over traditional caching strategy like Least Recently Used (LRU).     

A Cost-Efficient Scheduling Algorithm of On-Demand Broadcasts

In mobile wireless systems data on air can be accessed by a large number of mobile users. Many of these applications including wireless internets and traffic information systems are pull-based, that is, they respond to on-demand user requests. In this paper, we study the scheduling problems of on-demand broadcast environments. Traditionally, the response time of the requests has been used as a performance measure. In this paper we consider the performance as the average cost of request composed of three kinds of costs – access time cost, tuning time cost, and cost of handling failure request. Our main contribution is a self-adaptive scheduling algorithm named LDFC, which computes the delay cost of data item as the priority of broadcast. It costs less compared with some previous algorithms in this context, and shows good adaptability as well even in pure push-based broadcasts.     

Topology-transparent time division multiple access broadcast scheduling in multihop packet radio networks

Many topology-dependent transmission scheduling algorithms have been proposed to minimize the time-division multiple-access frame length in multihop packet radio networks (MPRNs), in which changes of the topology inevitably require recomputation of the schedules. The need for constant adaptation of schedules-to-mobile topology entails significant problems, especially in highly dynamic mobile environments. Hence, topology-transparent scheduling algorithms have been proposed, which utilize Galois field theory and Latin squares theory. We discuss the topology-transparent broadcast scheduling design for MPRNs. For single-channel networks, we propose the modified Galois field design (MGD) and the Latin square design (LSD) for topology-transparent broadcast scheduling. The MGD obtains much smaller minimum frame length (MFL) than the existing scheme while the LSD can even achieve possible performance gain when compared with the MGD, under certain conditions. Moreover, the inner relationship between scheduling designs based on different theories is revealed and proved, which provides valuable insight. For topology-transparent broadcast scheduling in multichannel networks, in which little research has been done, the proposed multichannel Galois field design (MCGD) can reduce the MFL approximately M times, as compared with the MGD when M channels are available. Numerical results show that the proposed algorithms outperform existing algorithms in achieving a smaller MFL.     

Efficient algorithms for scheduling data broadcast

With the increasing acceptance of wireless technology, mechanisms to efficiently transmit information to wireless clients are of interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. It has been proposed that in such systems the server should broadcast the information periodically. A broadcast schedule determines what is broadcast by the server and when. This paper makes the simple, yet useful, observation that the problem of broadcast scheduling is related to the problem of fair queueing. Based on this observation, we present a log‐time algorithm for scheduling broadcast, derived from an existing fair queueing algorithm. This algorithm significantly improves the time‐complexity over previously proposed broadcast scheduling algorithms. Modification of this algorithm for transmissions that are subject to errors is considered. Also, for environments where different users may be listening to different number of broadcast channels, we present an algorithm to coordinate broadcasts over different channels. Simulation results are presented for proposed algorithms.     

Scheduling data broadcast in asymmetric communication environments

With the increasing popularity of portable wireless computers, mechanisms to efficiently transmit information to wireless clients are of significant interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. In such environments, often it is not possible (or not desirable) for the clients to send explicit requests to the server. It has been proposed that in such systems the server should broadcast the data periodically. One challenge in implementing this solution is to determine the schedule for broadcasting the data, such that the wait encountered by the clients is minimized. A broadcast schedule determines what is broadcast by the server and when. In this paper, we present algorithms for determining broadcast schedules that minimize the wait time. Broadcast scheduling algorithms for environments subject to errors, and systems where different clients may listen to different number of broadcast channels are also considered. Performance evaluation results are presented to demonstrate that our algorithms perform well.     

High Performance Data Broadcasting Systems

Data broadcasting as a means of efficient data dissemination is a key technology facilitating ubiquitous computing. For this reason, broadcast scheduling algorithms have received a lot of attention. However, all existing algorithms make the core assumption that the data items to be broadcast are immediately available in the transmitter's queue, ignoring the key role that the disk subsystem and the cache management play in the overall broadcast system performance. With this paper we contribute a comprehensive system's perspective towards the development of high performance broadcast systems, taking into account how broadcast scheduling, disk scheduling, and cache management algorithms affect the overall performance. We contribute novel techniques that ensure an efficient interplay between broadcast scheduling, cache management, and disk scheduling. We study comprehensively the performance of the broadcast server, as it consists of the broadcast scheduling, the disk scheduling, the cache management algorithms, and the transmitter. Our results show that the contributed algorithms yield considerably higher performance. Furthermore, one of our algorithms is shown to enjoy considerably higher performance, under all values of the problem and system parameters. A key contribution is the result that broadcast scheduling algorithms have only a small effect on the overall system performance, which necessitates the definition of different focal points for efforts towards high performance data broadcasting.     

面向异构计算的能效感知调度研究

异构调度可使大规模计算系统采用并行方式聚合广域分布的各种资源以提高性能.传统调度目标追时限约束求高性能而忽视高效能,远不能适应绿色计算科学发展要求.因此,本文在理论上一方面建立融合能效感知的调度模型;另一方面提出适于超计算机混合体系的多学科背景的元启发式优化算法.从技术上解决了面向不同环境目标的调度实施条件界定及调度指标(时间、能耗)实时变化描述等问题.大量仿真实验结果表明:与三个元启发式调度器相比,论文方法在能效及可扩展等方面优势明显;对于高维实例,整体性能改善分别达到8%,15%和17%.     

Performance analysis of data scheduling algorithms for multi‐item requests in multi‐channel broadcast environments

Nowadays querying multiple‐dependent data items in a request is common in many advanced mobile applications, such as traffic information enquiry services. In addition, multi‐channel architectures are widely deployed in many data dissemination systems. In this paper, we extend a number of data productivity‐based scheduling algorithms and evaluate their performance in scheduling multi‐item requests in multi‐channel broadcast environments. We observe from the experimental results two performance problems that render these algorithms ineffective. Lastly, we discuss possible causes of these problems to give insights in the design of a better solution. Copyright © 2009 John Wiley & Sons, Ltd.     

Real-time multimedia processing in video sensor networks

Video sensor networks (VSNs) has become the recent research focus due to the rich information it provides to address various data-hungry applications. However, VSN implementations face stringent constraints of limited communication bandwidth, processing capability, and power supply. In-network processing has been proposed as efficient means to address these problems. The key component of in-network processing, task mapping and scheduling problem, is investigated in this paper. Although task mapping and scheduling in wired networks of processors has been extensively studied, their application to VSNs remains largely unexplored. Existing algorithms cannot be directly implemented in VSNs due to limited resource availability and shared wireless communication medium. In this work, an application-independent task mapping and scheduling solution in multi-hop VSNs is presented that provides real-time guarantees to process video feeds. The processed data is smaller in volume which further releases the burden on the end-to-end communication. Using a novel multi-hop channel model and a communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously with a dynamic critical-path scheduling algorithm. Dynamic voltage scaling (DVS) mechanism is implemented to further optimize energy consumption. According to the simulation results, the proposed solution outperforms existing mechanisms in terms of guaranteeing application deadlines with minimum energy consumption.     

基于机会式网络编码的高效广播传输算法

为了提高无线网络广播传输的效率,针对单跳无线网络提出了采用编码方法的广播传输算法。在传统的无线广播传输模型的基础上,分别实现了基于机会式网络编码的单组合分组广播传输算法和多组合分组广播传输算法。它们采用不同的策略选择多个丢失分组编码组合成重传分组,并通过从编码组合数据分组中恢复丢失分组的方式来提高广播传输的吞吐量。仿真结果表明,新算法在不同无线信道传输模型下相比已有的算法有效地降低了广播传输所需的传输带宽。     

NEST: novel eMBMS scheduling technique

In order to meet the growing demand for mobile multimedia broadcast services 3GPP includes evolved multimedia broadcast and multicast (eMBMS) services in LTE systems. The high data rates, low latency and QoS provisioning makes LTE systems more suitable for mobile broadcast and multicast services than legacy wireless networks. However, the 3GPP standards has not specified any scheduling strategy for this broadcast and multicast services. In this paper, we propose a novel eMBMS scheduling technique (NEST) which focuses on reducing the average waiting time (latency) of the broadcast services offered by LTE system. This paper has twofold contributions. We proffer NEST considering two types of impatience that is user equipment (UE) departure and UE request repetition. Our proposed scheduling strategy estimates the effects originating from the departure of the mobile UEs and UE request repetition case. It intelligently combines the advantages of both flat scheduling and on-demand scheduling in such a way that the overall latency of the system is reduced. We design a suitable modeling framework to analyze the performance of the system. Simulation experiments on typical LTE systems support the performance analysis and demonstrates 10 % gains while comparing with existing eMBMS scheduling available in present LTE systems.     

On Searching Continuous k Nearest Neighbors in Wireless Data Broadcast Systems

A continuous nearest neighbor (CNN) search, which retrieves the nearest neighbors corresponding to every point in a given query line segment, is important for location-based services such as vehicular navigation and tourist guides. It is infeasible to answer a CNN search by issuing a traditional nearest neighbor query at every point of the line segment due to the large number of queries generated and the overhead on bandwidth. Algorithms have been proposed recently to support CNN search in the traditional client- server systems but not in the environment of wireless data broadcast, where uplink communication channels from mobile devices to the server are not available. In this paper, we develop a generalized search algorithm for continuous k-nearest neighbors based on Hilbert Curve Index in wireless data broadcast systems. A performance evaluation is conducted to compare the proposed search algorithms with an algorithm based on R-tree Air Index. The result shows that the Hilbert Curve Index-based algorithm is more energy efficient than the R-tree-based algorithm.     

On Improving the Performance of Cache Invalidation in Mobile Environments

Many cache management schemes designed for mobile environments are based on invalidation reports (IRs). However, IR-based approach suffers from long query latency and it cannot efficiently utilize the broadcast bandwidth. In this paper, we propose techniques to address these problems. First, by replicating a small fraction of the essential information related to cache invalidation, the query latency can be reduced. Then, we propose techniques to efficiently utilize the broadcast bandwidth based on counters associated with each data item. Novel techniques are designed to maintain the accuracy of the counter in case of server failures, client failures, and disconnections. Extensive simulations are provided and used to evaluate the proposed methodology. Compared to previous IR-based algorithms, the proposed solution can significantly reduce the query latency, improve the bandwidth utilization, and effectively deal with disconnections and failures.     

Three-Phase Algorithms for Task Scheduling in Distributed Mobile DSP System with Lifetime Constraints

A distributed mobile DSP system consists of a group of mobile devices with different computing powers. These devices are connected by a wireless network. Parallel processing in the distributed mobile DSP system can provide high computing performance. Due to the fact that most of the mobile devices are battery based, the lifetime of mobile DSP system depends on both the battery behavior and the energy consumption characteristics of tasks. In this paper, we present a systematic system model for task scheduling in mobile DSP system equipped with Dynamic Voltage Scaling (DVS) processors and energy harvesting techniques. We propose the three-phase algorithms to obtain task schedules with shorter total execution time while satisfying the system lifetime constraints. The simulations with randomly generated Directed Acyclic Graphs (DAG) show that our proposed algorithms generate the optimal schedules that can satisfy lifetime constraints.     

Guaranteed Dynamic Priority Assignment Schemes for Real‐Time Tasks with (m,k)‐Firm Deadlines

We present guaranteed dynamic priority assignment schemes for multiple real‐time tasks subject to (m, k)‐firm deadlines. The proposed schemes have two scheduling objectives: providing a bounded probability of missing (m, k)‐firm constraints and maximizing the probability of deadline satisfactions. The second scheduling objective is especially necessary in order to provide the best quality of service as well as to satisfy the minimum requirements expressed by (m, k)‐firm deadlines. We analytically establish that the proposed schemes provide a guarantee on the bounded probability of missing (m, k)‐firm constraints. Experimental studies validate our analytical results and confirm the effectiveness and superiority of the proposed schemes with regard to their scheduling objectives.     

流量自适应的移动僵尸网络云控机制研究

僵尸网络从传统恶意代码进化而来,随着智能手机的计算能力与移动互联网接入技术的快速发展,构建移动僵尸网络已成为一种潜在的威胁。针对移动互联网,提出一种具有流量自适应性的移动僵尸网络云控机制,通过分析用户的流量使用情况,在3G和Wi-Fi不同网络环境下采取不同的流量使用策略,使用自适应的调度算法执行僵尸指令。仿真实验证明,在确保僵尸网络命令有效执行的情况下,流量自适应调度算法可有效增强移动僵尸网络的隐蔽性和实时性。     

Fast data access and energy‐efficient protocol for wireless data broadcast

In wireless mobile computing environments, broadcasting is an effective and scalable technique to disseminate information to a massive number of clients, wherein the energy usage and responsiveness are considered major concerns. Existing air indexing schemes for data broadcast have focused on energy efficiency (reducing tuning time) only. On the other hand, existing broadcast scheduling schemes have aimed at reducing access latency through nonflat data broadcast to improve responsiveness only. Not much work has addressed the energy efficiency and responsiveness issues concurrently. In this paper, we propose a fast data access scheme concurrently supporting energy saving protocol that constructs the broadcast channels according to the access frequency of each type of message in order to improve energy efficiency in mobile devices (MDs). The pinwheel scheduling algorithm (PSA) presented in this paper is used to organize all types of messages in the broadcast channel in the most symmetrical distribution in order to reduce both the tuning and access time. The performance of the proposed mechanism is analyzed, and the improvement over existing methods is demonstrated numerically. The results show that the proposed mechanism is capable of improving both the tuning and access time due to the presence of skewness in the access distribution among the disseminated messages. Copyright © 2011 John Wiley & Sons, Ltd.