بهینه سازی توالی برای اهداف رسانه ای با محدودیت های تاریخ سررسید حساب در ارائه در شبکه چندرسانه ای از کتابخانه های دیجیتال

This study investigates sequence optimization of media objects in a multimedia presentation that is dynamically composed from digital libraries. Each media object can be associated with a due date. The aim is to schedule the media objects in a delay-prone network environment such that the overall presentation lag and the due date penalties of the media objects of presentations can be minimized. We formulate the sequencing problem with buffer constraints in the media player into a flowshop scheduling problem and present a reduction strategy with a branch and bound algorithm to derive optimal sequences. The algorithm can be applied in applications with up to a dozen objects to be scheduled. In addition, we propose a modified NEH-based heuristic algorithm which can provide approximate solutions with an average error rate of less than 4%. The computation-efficient heuristic, when deployed in applications with heavily loaded servers, can obtain near-optimal sequences for problems with more than a dozen objects. The proposed algorithms are embedded into a prototype system for providing digital library services.

In a multimedia digital library system, a query to the database typically retrieves a number of relevant media objects. In general, while most existing systems provide interfaces for users to view the objects by repetitively “clicking, downloading, and playing” the objects one by one, there is a desire of users for a “TV-like” presentation style where the objects are continuously played. A presentation of this kind sequentially combines and continuously presents the media objects such that the user does not have to repetitively click to retrieve and play the media objects. Applications preferring a TV-like presentation would arise from any system that can combine multiple separate media objects into a continuous presentation. Examples include assembling a TV-like documentary based on queries to a multimedia database, continuously showing media items in an online multimedia album, etc. A continuously played TV-like presentation particularly suits hand-held portable devices such as pocket PCs, organizers, and cell phones. The input interfaces of these portable devices usually are more difficult to operate than a mouse. In particular, traditional repetitive “click-and-play” operations are less effective when users are in motion. In practice, to suit more users with different navigation preferences, the design of the navigation interface should provide both click-and-play and TV-like presentations. In a typical online multimedia presentation application, the media objects are retrieved from a server through the Internet. The total latency of a presentation is thus an important factor in the overall quality of the service. To cope with the congestion and delay problems, a commonly used strategy is to “prefetch” the media objects before their presentation due time. In an on-the-fly assembled presentation delivered from digital libraries, there is no pre-defined order for presenting the media objects. Hence, the ordering of the objects is determined dynamically on-the-fly. In a typical multimedia presentation, the modalities of the media objects might include text, images, audio, video, vector graphics, etc. Each media type has its unique data compression capabilities. For the same amount of data transmitted, the expected presentation durations for different media types differ drastically. To reduce the total presentation lag, the delivery and presentation order of the media objects should be properly planned. Media streaming technology is an example application of prefetch technology that aims to reduce the presentation lag. A streaming-based media player prefetches and buffers small chunks of a media object so that the data can be processed before it is rendered. As soon as the buffer is full, the media object starts to play. While the media object is playing, more data is being downloaded. Typically, for a multimedia presentation delivered through a network environment with a reasonable bandwidth, the only playback idle time is the initial download duration for the first chunk, which in general is rather short. Therefore, a practical approach is to present the streamed objects before other non-streamed objects to keep the overall presentation latency low. The main theme of this study is to explore and exploit optimization techniques for ordering the non-streamed media objects of a prefetch-enabled presentation through a slow network such that the presentation lag is minimized. In general, the end-to-end delay of a presentation depends on: access delay in the server side, communication delay due to network transmission, packetization, buffering, depacketization, and rendering overhead at the player site. In an environment where the bandwidth of the communication channel is rather restricted, the communication delay dominates the end-to-end delay. In this study, we assume that the download time of an object is deterministic. This assumption is reasonable for applications where the end-to-end transmission delay is mainly attributed to a last-mile bottleneck or a server-assigned bandwidth quota limit. In these cases, the end-to-end transmission usually does not exhibit significant bandwidth variations. As compared to commonly-adopted approaches that use random sequences, simulation experiments to be presented in Section 7 nevertheless show that optimized sequences based on the deterministic download transmission time significantly reduce the presentation lags in real life network environments with stochastic variations in the transmission rate. In Lin et al. [22] and [23], we provided the essential background and an overview of the prefetch-enabled media object scheduling problems [4] with different real-life constraints. A number of different problem settings have been thoroughly discussed. We identified several problem settings that had never before been explored. In this study, we propose a solution for a specific one of these un-solved problems. Specifically, this study considers the media object scheduling problems with a player-side “buffer constraint” and “due-date” constraints on the media objects. The player-side buffer constraint is common in applications where the multimedia objects are to be presented in small-scale devices, such as pocket PCs and organizers, with restricted memory capacity. The due-date constraints arise from commercial online services in which the media servers are implemented to automatically insert various intermittent media objects for advertisements while the users are viewing a presentation that dynamically combines media objects retrieved from the servers. These advertisement media objects are presented between two neighboring objects in the presentation. Often, an advertisement object is required to be completed within a predetermined time slot in the final presentation, mostly depending on the agreements between service providers and funding supporters. The problems addressed in this paper will be mathematically formulated and computationally solved. Numerical simulations will be described to assess the performance of the proposed algorithms under real-life wireless network conditions.

In this study, we formulated the problem of sequencing media objects in a dynamically composed multimedia presentation from digital libraries so as to reduce the overall presentation lag and due date penalties. The addressed problem was mapped to two-machine flowshop scheduling with buffer and due date constraints. Two different bi-criteria objective functions, namely αCmax+(1−α)Tmax and αCmax+(1−α)ΣTi, are considered. Exact and approximation algorithms were proposed and implemented in our system for providing digital library services. Experimental results show that the proposed methods can obtain optimal solutions for problems with up to 14 objects with a small buffer, and 16 objects with a large buffer. Furthermore, the proposed NEH-based heuristic solutions appeared to provide quality approximate solutions with an average error rate of under 4%. The heuristic algorithm can be applied to heavily-loaded servers that require a quick response on the near-optimal sequence of a media set with more than a dozen objects. Experiments with WCDMA wireless networks indicate that the proposed MNEH heuristic algorithm can produce solutions whose objective function values are in general smaller than the solutions yielded by the EDD dispatching rule. Following this study, there are some potential research directions. The studied settings assumed that the end-to-end transmission rate is deterministic. This assumption can be regarded an acceptable approximation for applications in which the end-to-end transmission delay is mainly subject to the last mile bottleneck without significant bandwidth variations. However, many Internet applications provide only best-effort data delivery and cannot guarantee a very consistent transmission rate during a presentation session. In such cases, stochastic variations of the network transmission rate (or the download time of a media object) should be considered in the sequence optimization process. In the literature, stochastic flowshop scheduling problems deal with cases for which the processing times of jobs on each machine are governed by a random variable. In general, the stochastic flowshop scheduling problems are not all that easy to solve. Most of the existing studies focus on problems where the job processing time is a random variable following an “exponential distribution”. The objective is to find the schedule that minimizes the expected makespan E(Cmax). Such a case with exponentially distributed process times has been shown to be, in general, tractable ([34]; Bagga [3]; Cunningham and Dutta [7]; and Ku and Niu [19]). Unfortunately, for Internet multimedia delivery applications, the probability density function of an end-to-end bandwidth is, typically, inverse bell-shaped [14]. The probability density function of the download time of a media object should resemble a truncated normal distribution or an Erlang distribution with high shape parameters. Two-machine flowshop scheduling problems with these two distributions have never been solved and thus are worthy of research attention. In addition, in many applications the media objects in a digital library are subject to different categories of temporal constraints (e.g., sequence, parallel, precedence). Development of exact or approximate algorithms for these problems requires further investigation.