Multiplex communications – Channel assignment techniques – Messages addressed to multiple destinations
Reexamination Certificate
1998-05-21
2001-06-05
Ton, Dang (Department: 2732)
Multiplex communications
Channel assignment techniques
Messages addressed to multiple destinations
C370S408000
Reexamination Certificate
active
06243389
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to wireless data broadcast systems, and more particularly to efficient information retrieval in such systems.
BACKGROUND OF THE INVENTION
Cellular phones, no more than a curiosity less than a decade ago, are now commonplace. In addition to their wide spread use in developed counties, cellular phones are popular in developing countries as well, where wireless telecommunications systems for supporting such cellular service can be implemented much more quickly than a conventional wireline system.
The acceptance and growth of wireless systems for data communications, as opposed to voice communications, has been relatively slow. It is believed, however, that such wireless data communications systems are ready for significant growth. Factors portending such growth include the ever-decreasing size of computers and the increasing regularity with which such computers are fitted with receivers for receiving wireless signals. Such small size and wireless capabilities facilitates mobile access to data networks, such as the Internet. See, Hills, “Terrestial Wireless Networks,” vol. 278, no. 4
, Scientific American
, pp. 86-88, (April 1998).
Designers of wireless data networks will face certain challenges in making information readily accessible to mobile clients. One problem relates to the efficient retrieval of desired information by the client Such a problem is inherent in an “asymmetric” communication environment, such as a data communications network. A communication environment is described as “asymmetric” if the available or required communication capacity from the information source (“server”) to the information recipient (“clients”) is much larger than that available or required in the reverse direction.
FIG. 1
depicts an example of such an asymmetric environment wherein numerous mobile clients, five of which are pictured as mobile clients
104
a
-
104
e
, retrieve information from a server base station
102
that broadcasts such information over a wireless channel. Mobile clients
104
a
-
104
e
may be, for example, lap-top computers that include a receiver for receiving wireless communications. In the present example, such computers are assumed to be running on batteries, as may be required, for example, if the computer is in the possession of a user travelling in an automobile.
There are two fundamental models by which clients can retrieve information from a server. One is the “pull-based” model, used in traditional client-server information-retrieval systems, wherein multiple clients retrieve information by making individual requests to the server. Such a model is poorly suited for the asymmetric environment under consideration. First, since each “terminal” (i.e., client) is assumed to be a weak transmitter, a variety of signal strength/interference problems may arise. Secondly, an enormous volume of requests would be received by the server, making the processing of such requests problematic.
A second model is the “push-based” model, wherein the server broadcasts its information over a communication medium to multiple clients who receive such information simultaneously (ignoring time delays). Each of such clients then actively retrieves information of interest from the universe of information received. While the “push-based” model is effective in disseminating massive amounts of information to numerous clients, such an approach has associated with it potentially significant shortcomings.
In particular, an individual client looking for certain items of information may have to actively listen to the communication medium for a long time to receive such information. The “cost” to a client of information retrieval may be viewed as comprising two distinct components: (1) the time elapsed in retrieving information of interest, and (2) the time elapsed in actively listening to the communications medium for the information of interest. The first component is referred to as the “access time” and the second component is referred to as the “tuning time.” The distinction between access time and tuning time is based on an assumption that the clients are able to switch between a resource-consuming (e.g, battery power) “active mode” and a resource-conserving “sleep mode.” Such modes are commonly used in computers.
Listening to the communications medium requires that a client be in the active mode. To decrease time spent in the active mode, a server may provide information indicative of when various items of information will be broadcast (“indexing information”). Thus, knowing that for at least a certain period of time no relevant information will be broadcast, the client is able to lapse into the resource-conserving sleep mode. Tuning time thus forms a measure of the efficient utilization of certain important resources, such as the limited power supply of mobile lap-top computers, in the process of information retrieval.
A substantial amount of work in the prior art has addressed the issue of minimizing access time in the classical pull-based model. There is a fundamental difference, however, between efficient information retrieval in pull-based models and in push-based models. In particular, in the pull-based model, an information search can always begin at a certain well-defined location, such as the “root” of a “balanced search tree,” for example. In a push-based broadcast model, the client begins its information search based only on the information that is being broadcast at the moment it tunes in. This aspect of the push-based broadcast model makes the problem of minimizing access and tuning time particularly difficult
The prior art has addressed the issue of information retrieval in push-based broadcast models, but mainly towards the end of minimizing access time, not tuning time, and typically in models in which the broadcast consists solely of data items, not indexing information. Information retrieval in an indexed data broadcast was first addressed by lmielinsli et al. in “Energy Efficient Indexing on Air,” Proc. ACM SIGMOD Conf., May 1994. lmielinski et al. considered a simple case where the distribution over data items is uniform (i.e., each data item appears the same number of times as all other data items in the broadcast).
It would be desirable then, to have a broadcasting method that seeks to minimize a client's expected access time (“mean access time”) and expected tuning time (“mean tuning time”), and for an information repository comprising arbitrarily distributed data items.
SUMMARY OF THE INVENTION
In some embodiments, the present invention provides a method for scheduling an indexed data broadcast such that both mean access time and mean tuning time are reduced to a practical minimum. In one embodiment of such a method, data items are first scheduled for broadcast. Such data items are advantageously scheduled to provide a “feasible” data schedule wherein: (1) all data items to be broadcasted are equally spaced; and (2) when indexed with appropriate “indexing keys,” the indexing information can be efficiently stored and broadcasted in a way that requires relatively few bits and therefore does not substantially lengthen the mean access time of the broadcast.
A feasible data schedule is contrasted from an “optimal” data schedule, which has the theoretically lowest mean access time. Such an optimal data schedule is based on readily calculable optimal distances between repeat occurrences of data items. For reasons described later in this specification, it is typically not possible to design an “optimal” data schedule using such “optimal” spacing values. Thus, the “feasible” data schedule is instead developed
In one embodiment, a feasible data schedule is provided by shifting the value of the optimal distance between repeat occurrences of data items to the closest power of 2 that is bigger than or equal to said optimal distance value. In those embodiments, the distance between shifted data items j is, at most, 2× the optimal distance. Such a schedule results in a mean access time that is about 2×
Khanna Sanjeev
Zhou Shiyu
Breyer Wayne S.
DeMont Jason Paul
DeMont & Breyer LLC
Lucent Technologies - Inc.
Ton Dang
LandOfFree
Method and apparatus for indexed data broadcast does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for indexed data broadcast, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for indexed data broadcast will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497967