Media Object Sequence Optimization for Reducing Presentation Lags in Automatically-Assembled Multimedia Presentations

[[abstract]]在數位圖書/博物館展示系統中，媒體的播放是最後重要的一環，亦是直接觸及影響使用者的一項任務。然而，如何正確有效率地將多媒體素材傳輸到使用者的播放端，進而減少使用者的等候時間(wait latency)，是此階段要優先被考慮的議題。在眾多的各類的播放方式之中，類似電視播放的方式，藉由自動依序播放媒體物件的方式，免除了使用者一再重複下載與播放的動作，是一種使用者喜歡的媒體自動播放模式，稱之為(TV-like Presentation)。在此方式之下，?減少使用者的等候時間(wait latency)，找出一個合適的排程演算法，並運用於主機端將使用者們所需要的媒體物件，能有效率地依序傳輸到不同使用者端電腦上。 本論文的主要目的就在探討在各類限制與真實需求，藉由預載機制，達成媒體傳輸及播放順序的最佳化技術。首先，本研究嘗試將傳統最為廣泛探討的排程問題，應用到多媒體檔案傳輸與播放問題上，目的在最短時間完成媒體元素播放順序的問題。 針對自動組合媒體展示，本文調查與探討播放延遲最小化相關議題，考慮在各種不同的限制式下，其中在多媒體應用中兩個常見的限制式，包含時序限制與優先權限制。並且也研究了數個重要議題: 內部元素時序關係，物件優先權，物件時間到期限制，用戶端緩衝區限制式(buffer limitation)等等。更進一步，提出相關的系統實作雛型。 接著探討緩衝區限制式對於多媒體播放的影響。播放端的緩衝特性是"時間相依"，不同於傳統的流程型排程問題研究中，所提到的個數為主的緩衝區。文中證明此問題是strongly NP-hard。 基於上述的證明，在buffer有限的情形之下，加入排程理論中兩個重要的限制式:優先順序(precedence)與到期時間限制(due date)分別詳述於第四、五章。針對這些限制，論文首先提出了相對應的演算法，可以用來設計有效率的媒體傳輸及播放順序。從理論與實際上3G傳輸實驗證明，較佳的排程演算法可以有效率的降低等候時間; 並且也在第六章比較與實作數種啟發式演算法來解buffer限制問題。 最終，將這些媒體排序功能實作以整合到本實驗開發中的智慧型超媒體展示系統之中。此系統提供使用者端之展示系統效能，可減少使用者等待時間。[[abstract]]In a Digital Library/Museum system, the media presentation is the last important task which directly affects and contacts with a user. But how to transmit several media items effectively and correctly then reduce user's waiting time (wait latency), is considerable issue of this stage. In many kinds of showing mechanisms, the way which is similar with television broadcasts by automatically broadcasting the media items in order and this mechanism avoids the user to duplicate downloading and the playback repeatedly. This behavior called TV-like Presentation is media automatic presentation pattern which one kind of a user liked. Under TV-like Presentation, for reducing user's waiting time (wait latency), the server must have be capable of deciding a good order of media items (by scheduling algorithm), and the media items will have effectiveness which carries these items to the different user. This dissertation focuses on using media transmission and playback in order optimization technology by the Prefetch mechanism under limited and the real demand environment. Firstly, research attempts to apply the traditional widespread scheduling problem into the multimedia file transmission and the playback problem. This multimedia problem seeks a shortest time to arrange the sequence of media item. For the use of automatically-assembled multimedia presentation, this thesis survey and discuss the issues of reducing presentation latency under various constraints; there are two commonly found constraints in such online multimedia application, including temporal constraints and precedence constraints. Also, this research has researched several important issues: inter-object temporal relations, object priorities, objective due dates, and client-side buffer limitations etc. Furthermore, a system prototype considering those issues of media delivery also is proposed. This research continues to discuss the effects of buffer size constraint for multimedia presentation based on the survey study above. The player-side buffer is “processing time-dependence” and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studious. Then the problem is proven to be strongly NP-hard. Based on the proof, buffer limitation with two important constraints from scheduling theory are considered, “Precedence Constraint” and “Due Date Constraint”, which are depicted in Chapter 4 and 5 respectively. For these constraints, we first propose the relative algorithms to design the transmission of media items and its ordering efficiently. From theoretical and practical 3G transmission experiment, it is observed that a better scheduling algorithm can reduce the wait latency efficiently. Therefore, we studied and modified various heuristic algorithms to solve buffer constraint in Chapter 6. Finally, the functions of media ordering algorithms are realized in an intelligent hypermedia presentation system which was established by Digital Archive Lab of National Chi-Nan University. The system provides end-users an environment with high presentation efficiency and lower user wait latency.[[note]]博