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

Introduction

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., q₁={d₁, d₄, d₁₂}, where d₁, d₄, d₁₂ are the keys of the desired data items. These users can download the index information about q₁ 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 q_i together means that only one index entry for q_i is enough. This is because data items in q_i 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 q₁={d₁, d₄, d₁₂} and q₂={d₄, d₇, d₁₂}. The broadcast program π₁=[d₁, d₄, d₁₂, d₇] as well as π₂=[d₁, d₄, d₁₂, d₄, d₇, d₁₂] 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 π₁ is four (i.e., four items) and it is also the optimal. So these overlapped items, e.g., d₄, d₁₂, should be well-organized. This is the key to the best scheduling.