An O(N log K) Restricted Dynamic Programming Algorithm for Data Allocation over Multiple Channels(Broadcast Systems)

スポンサーリンク

概要

• 論文の詳細を見る

• Data broadcast has become a promising approach to achieving information dissemination in wireless environments due to the limited channel bandwidth and the power constraints of portable devices. In this paper, a restricted dynamic programming approach which generates broadcast programs is proposed to partition data items over multiple channels near optimally. In our approach, a function to predict the optimal average expected delay, in terms of the number of channels, the summation of the access frequencies of data items, and the ratio of the data items is developed by employing curve fitting. Applying this function, we can find a cut point that may be very close to the optimal cut. Thus, the search space in dynamic programming can be restricted to the interval around a determined cut point. Therefore, our approach only takes O(N log K) time, where N is number of data items and K is the number of broadcast channels. Simulation results show that the solution obtained by our proposed algorithm is near-optimal.

• 一般社団法人電子情報通信学会の論文
• 2005-09-01

著者

• Chen Hsing‐lung

  National Taiwan Univ. Sci. And Technol. Taipei Twn

• WANG Shuoi

  Department of Computer Science and Information Engineering, National Taiwan University of Science an

• CHEN Hsing-Lung

  Department of Electronic Engineering, National Taiwan University of Science and Technology

• Wang Shuoi

  Department Of Computer Science And Information Engineering National Taiwan University Of Science And

• Chen Hsing-lung

  Department Of Electronic Engineering National Taiwan University Of Science And Technology

関連論文

• A Borrowing-Based Call Admission Control Policy for Mobile Multimedia Wireless Networks(Mobile Multimedia Communications)
• A Traffic-Based Bandwidth Reservation Scheme for QoS Sensitive Mobile Multimedia Wireless Networks(Mobility Management)(Mobile Multimedia Communications)
• An O(N log K) Restricted Dynamic Programming Algorithm for Data Allocation over Multiple Channels(Broadcast Systems)

スポンサーリンク