Dynamic generation of data broadcasting programs for a broadcast disk array in a mobile com.pdf

Dynamic Generation of Data Broadcasting Programs for a Broadcast Disk Array in a Mobile Computing Environment Wen-Chih Peng and Ming-Syan Chen Department of Electrical Engineering National Taiwan University Taipei, Taiwan, ROC E-mail:{mschen@.tw, wcpeng@.tw} ABSTRACT We explore in this paper the problem of generating hierar- chical broadcast programs with the data access frequencies and the number of broadcast disks in a broadcast disk ar- ray given. Specifically, we first transform the problem of generating hierarchical broadcast programs into the one of constructing a channel allocation tree with variant-fanout. By exploiting the feature of tree generation with variant- fanout, we develop a heuristic algorithm VFK to minimize the expected delay of data items in the broadcast program. Performance of these algorithms is analyzed. It is shown by our simulation results that by exploiting the feature of variant-fanout in constructing the channel allocation tree, the solution obtained by algorithm VFK is of very high qual- ity and is in fact very close to the optimal one. Keywords: Broadcast disks, mobile computing, broadcast programs, multiple broadcast channels. 1. INTRODUCTION Several applications in a mobile computing environment, such as stock activities, traffic reports and weather forecast, have become increasingly popular in recent years [17][18]. It is noted that mobile computers use small batteries for their operations without directly connecting to any power source, and the bandwidth of wireless communication is in general limited. As a result, an important design issue in a mobile system is to conserve the energy and communication bandwidth of a mobile unit while allowing mobile users of the ability to access information from anywhere at anytime [3][5][10]. In order to conserve the energy and communication band- width of a mobile computing system, a data delivery ar- chitecture in which a server continuously and repeatedly broadcasts data to a client communi