Broadcasting is an efficient and scalable way of transmitting data over wireless channels to an unlimited number of clients. In this chapter the problem of allocating data to multiple channels is studied, assuming flat data scheduling per channel and the presence of unrecoverable channel transmission errors. The behavior of wireless channels is described by the Bernoulli model, in which each packet transmission has the same probability to fail and each transmission error is independent from the others. The objective is that of minimizing the average expected delay experienced by the clients. Optimal solutions can be found in polynomial time when all data items have unit lengths, while heuristics are presented when data items have non-unit lengths. Extensive simulations, performed on benchmarks whose item popularities follow Zipf distributions, show that good sub-optimal solutions are found.
TopIntroduction
Advances in technology have produced today’s information age. Pervasive connections enable a broad spectrum of novel applications and services. In the present environment, voice services are no longer sufficient to satisfy clients’ requirements. Access to services on the air seems to be the next killer application. Data broadcasting is an efficient way of simultaneously disseminating data items to a large number of clients (Stojmenovic, 2002). In this scenario, a server at the base-station repeatedly transmits data items from a given set over wireless channels, while clients passively listen to the shared channels waiting for their desired item. The server has to pursue a data allocation strategy for assigning items to channels and a broadcast schedule for deciding which item has to be transmitted on each channel at any time instant. The quality of service is measured in terms of the client expected delay, that is, the average amount of time spent by a client before receiving the item the client needs. Therefore, efficient data allocation and broadcast scheduling algorithms have to minimize the client expected delay. Such a delay increases with the size of the set of the data items to be transmitted by the server. Indeed, the client has to wait for many unwanted data before receiving his own data. Moreover, the client expected delay may be influenced by transmission errors because items are not always received correctly by the client. Although data are usually encoded using error correcting codes (ECC) allowing some recoverable errors to be corrected by the client without affecting the average expected delay, there are several transmission errors which still cannot be corrected using ECC. Such unrecoverable errors affect the client expected delay, because the resulting corrupted items have to be discarded and the client must wait until the same item is broadcast again by the server.
Several variants for the problem of data allocation and broadcast scheduling have been proposed in the literature (Acharya, Alonso, Franklin & Zdonik, 1995; Ammar & Wong 1985; Ammar & Wong, 1987; Anticaglia, Barsi, Bertossi, Iamele & Pinotti, 2006; Ardizzoni, Bertossi, Pinotti, Ramaprasad, Rizzi & Shashanka, 2005; Bar-Noy, Bhatia, Naor & Schieber, 1998; Imielinski, Viswanathan & Badrinath, 1994; Kenyon & Schabanel, 1999; Kenyon, Schabanel & Young, 2000; Lo & Chen, 2000; Peng & Chen, 2003; Prabhakara, Hua & Oh, 2000; Vaidya & Hameed, 1997; Yee, 2001; Yee, Navathe, Omiecinski & Jermaine, 2002).
The database community usually partitions the data among the channels and then adopts a flat broadcast schedule on each channel (Ardizzoni et al., 2005; Peng & Chen, 2003; Yee et al., 2002). In such a way, the allocation of data to channels becomes critical for reducing the average expected delay, while the flat schedule on each channel merely consists in cyclically broadcasting in an arbitrary fixed order, that is once at a time in a round-robin fashion, the items assigned to the same channel (Acharya et al., 1995). In order to reduce the average expected delay, a skewed data allocation is used where items are partitioned according to their popularities so that the most requested items appear in a channel with shorter period. Assuming that each item transmitted by the server is always received correctly by the client, a solution that minimizes the average expected delay can be found in polynomial time in the case of unit lengths (Yee et al., 2002), that is when all the items have a unit transmission time, whereas the problem becomes computationally intractable for non-unit lengths (Ardizzoni et al., 2005). In this latter case, several heuristics have been developed in (Anticaglia et al., 2006; Yee et al., 2002), which have been tested on some benchmarks where item popularities follow Zipf distributions. Such distributions are used to characterize the popularity of one item among a set of similar data, like a Web page in a Web site (Breslau, Cao, Fan, Phillips & Shenker, 1999).