Algebraic data retrieval algorithms for multi-channel wireless data broadcast
Algebraic data retrieval algorithms for multi-channel wireless data broadcast
复制标题
DOI：
10.1016/j.tcs.2011.12.070
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Xiaofeng Gao;Zaixin Lu;Weili Wu;B. Fu
中科院分区：
文献类型：
--
作者：
Xiaofeng Gao;Zaixin Lu;Weili Wu;B. Fu
无线数据广播是向移动用户发布公共信息的重要数据传播方式。由于移动网络用户数量呈指数级增长，有必要开发高效的数据检索协议，以便最终用户有效地下载数据项。在本文中，我们集中研究从多通道无线数据广播系统检索一组数据项的调度算法。众所周知，移动计算中最重要的问题是能源效率和查询响应效率。然而，在数据广播中，减少访问延迟和能源成本的目标可能是相互矛盾的。因此，我们定义了一个名为最小约束数据检索问题（MCDR）的新问题。我们证明了MCDR是NP-hard的，然后给出了一种可以平衡两个因素的固定参数易处理算法。它的计算时间为 O (2 k (h n t) O (1))，其中 n 是通道数，k 是所需数据项的数量，t 是最大时隙，h 是通道切换的最大次数。
Wireless data broadcast is an important data dissemination method for distributing public information to mobile users. Due to the exponentially increasing number of mobile network users, it is necessary to develop efficient data retrieval protocols for end users to download data items effectively. In this paper, we concentrate on investigating scheduling algorithms for retrieving a set of data items from a multichannel wireless data broadcast system. As we know, the most important issues in mobile computing are energy efficiency and query response efficiency. However, in data broadcast the objectives of reducing access latency and energy cost can be contradictive to each other. Consequently, we define a new problem named Minimum Constraint Data Retrieval Problem (MCDR). We prove that MCDR is NP-hard, and then show a fixed parameter tractable algorithm which can balance two factors together. It has computational time O (2 k (h n t) O (1)), where n is the number of channels, k is the number of required data items, t is the maximal time slot, and h is the maximal number of channel switches.