O(N log K) Restricted Dynamic Programming Algorithm for Data Allocation over Multiple Channels" /> 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." /> O(N log K) Restricted Dynamic Programming Algorithm for Data Allocation over Multiple Channels" />
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

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

Shuoi WANG
Hsing-Lung CHEN

Publication
IEICE TRANSACTIONS on Communications   Vol.E88-B    No.9    pp.3756-3764
Publication Date: 2005/09/01
Online ISSN: 
DOI: 10.1093/ietcom/e88-b.9.3756
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Broadcast Systems
Keyword: 
data broadcast,  data allocation,  dynamic programming,  multiple channels,  

Full Text: PDF(468.6KB)>>
Buy this Article


Summary: 
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.