A Transformation Technique for Scheduling Broadcast Programs of Multiple-Item Queries

A Transformation Technique for Scheduling Broadcast Programs of Multiple-Item Queries

Jen-Ya Wang (Hungkuang University, Taichung, Taiwan)
Copyright: © 2012 |Pages: 16
DOI: 10.4018/jghpc.2012100104


In wireless environments, many mobile users may raise queries for accessing multiple data items, e.g., stock information or traffic condition, simultaneously. Most queries are identical. That is, many users may have an interest in some popular data items. Because data broadcast can offer unlimited users shareable information at the same time, a broadcast server is usually employed to disseminate all the data items periodically. Intuitively, popular data items should be scheduled and transmitted to users more efficiently than ordinary ones, so these users can thus save access time. To improve customer satisfaction, the author considers a broadcast program scheduling problem in such an environment and aims to minimize mobile users’ worst access time as well as their battery power consumption by generating near-optimal broadcast programs. The author provides theoretical analysis as a foundation of mapping the problem to another domain (i.e., from unit item to unit fragment) and this transformation makes the problem easy to solve. Moreover, an O(N logN) algorithm is proposed for this NP-hard problem. Finally, experimental results show that access time can be reduced by carefully scheduling broadcast programs. It suggests that other similar optimization problems can be solved similarly.
Article Preview


In wireless environments, allowing mobile users accessing multiple broadcast items (e.g., multiple objects in a web page) at a time is a good idea, because it can simultaneously increase customer satisfaction and save battery power (Chiang, Shih, & Chen, 2011; Huang & Huang, 2010; Jea, Wang, & Chen, 2008; Liu & Lee, 2010; Waluyo, Rahayu, Taniar, & Srinivasan, 2011). Consider a broadcast server broadcasts many data items cyclically. Through an up-link channel or a subscription mechanism, each mobile user can issue a multiple-data-item query (Dewria, Ray, Ray, & Whitley, 2011; Lee & Lo, 2003; Liu & Lee, 2009) for some user-specified data items such as the up-to-date stock information, or some location-dependent information such as the states of the nearest 10 parking areas. Their preferences usually do not change quickly (e.g., minutely), so broadcasting the information periodically becomes meaningful and scalable in user size. Moreover, the answer to a multiple-data-item query can be denoted by a query set, e.g., q1={d1, d4, d12}, where d1, d4, d12 are the keys of the desired data items. These users can download the index information about q1 first and determine where the desired data items locate. Then their mobile devices (e.g., PDA) can enter the doze mode to wait for desired items and later return to the active mode to access them. Note that the battery power that mobile devices consume in the active mode is much more than that they do in the doze mode (Shin, 2011; Waluyo et al., 2011). Therefore, it is important to design a short broadcast program constrained by that all items in a query set should be organized together. The reasons are as follows. First, a short program means less access time. That is, it can improve customer satisfaction. Second, placing all data items in each qi together means that only one index entry for qi is enough. This is because data items in qi will be organized into a consecutive broadcast subprogram. And thus only a small index structure is needed. This signifies we can consume less power to locate a query set.

In such an environment, customer satisfaction and power consuming are measured by two common metrics: tuning time and access time. Tuning time (Huang & Huang, 2010; Shin, Wu, & Chen, 2011; Waluyo et al., 2011; Yang, Shi, Wu, Gao, & Zhong, 2011) is the time spent by a mobile user only in the active mode before downloading all the desired data items. On the other hand, access time (Huang & Huang, 2010; Jea & Wang, 2010; Jea et al., 2008; Wang & Jea, 2009) is the waiting time spent by the user before receiving all desired data items in both modes. Hence, access time is an upper bound of tuning time. Moreover, a program scheduling that generates the optimal tuning time does not mean it also ensures the optimal access time, and vice versa. Few of past schemes paid attention on both issues for multiple-data-item access, so we intend minimizing both of them.

In this paper, we aim to minimize the worst access time by generating a short broadcast program for all users. For example, consider there are two query sets q1={d1, d4, d12} and q2={d4, d7, d12}. The broadcast program π1=[d1, d4, d12, d7] as well as π2=[d1, d4, d12, d4, d7, d12] is of the same function, since both can periodically disseminate the same information. But the former is much more favorable than the latter. This is because the worst access time for π1 is four (i.e., four items) and it is also the optimal. So these overlapped items, e.g., d4, d12, should be well-organized. This is the key to the best scheduling.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing