Method and apparatus for scheduling broadcast information
Methods and apparatus are disclosed for efficiently scheduling incoming information objects so that objects with the highest utility factors are scheduled for broadcast. The incoming information objects are preferably received from one or more information sources, and can be tagged with attributes that associate each object with one or more classes of information (e.g., sports, news, etc.), and/or can provide a gauge of the utility of the object. The tags can be used, for example, to select and broadcast objects from a variety of classes, and/or to identify the objects that provide the most utility at any given time.
1. A computer-implemented method for delivering objects to one or more receiver units, comprising:
receiving a number of incoming objects at a computing device, each object corresponding to one or more classes;
maintaining objects from a variety of classes in an object schedule at the computing device, wherein each object has a utility factor comprising one or more of the importance of the object, the timeliness of the object, and the number of objects previously transmitted in a same or related class as the current object; and
delivering selected objects from the object schedule to the one or more receiver units associated with one or more display devices;
wherein one or more values for the utility factor for each object are related to an importance factor associated with the object, the importance factor being modified by a predetermined function that decreases with an age of the object to identify the utility factor, and the age of the object being related to the estimated time for delivery.
2. The computer-implemented method of claim 1 , wherein objects from a variety of classes are maintained by determining which of the incoming objects are to be added to the object schedule and which of the cached objects in the object schedule are be evicted, such that objects from a variety of classes are maintained in the object schedule.
3. The computer-implemented method of claim 1 , wherein each object has a utility factor, and the value of the utility factor is based upon on the position of the object in the object schedule.
4. The computer-implemented method of claim 1 , wherein each class has a utility factor that is calculated by combining the utility factors of those scheduled objects that correspond to the class using a sub-linear function.
5. The computer-implemented method of claim 4 , wherein the object schedule has an overall schedule utility factor, the overall schedule utility factor is calculated by combining the utility factors for each of the classes using a schedule function that sums the utility factors.
6. The computer-implemented method of claim 5 , wherein objects from a variety of classes are maintained in the object schedule by:
receiving a new object;
scheduling the new object in an initial position within the object schedule; and
reordering the scheduled objects so that the overall schedule utility factor is increased.
7. The computer-implemented method of claim 1 , wherein each object in the object schedule has an estimated time for delivery based on the position of the object in the schedule and each object in the schedule has an importance factor, and wherein the utility factor for each object is dependent on the estimated time for delivery and the importance factor.
8. The computer-implemented method of claim 1 , wherein the value of the utility factor associated with each object is based on the importance factor of the object weighted by a freshness function, where the freshness function comprises a predetermined function that decreases with an AGE of the object, the AGE of the object being related to the estimated time for delivery.
9. A computer-implemented method for delivering objects to one or more receiver units, comprising:
receiving a number of incoming objects at a computing device, each object corresponding to one or more classes;
maintaining objects from a variety of classes in an object schedule at the computing device, wherein each object has a utility factor comprising one or more importance factors associated with the object, the timeliness of the object, and the number of objects previously transmitted in a same or related class as the current object; and
delivering selected objects from the object schedule to the one or more receiver units associated with one or more display devices;
wherein each object in the schedule is a member of one or more classes, and the utility factor for each object is dependent on a class variety score of each of the member classes, the utility factor for each object comprising the sum over all member classes of a class importance factor of the member class modified by a predetermined function that decreases with the class variety score of the class.
10. The computer-implemented method of claim 9 , wherein the class variety score for each class is a measure of the number of member objects of the class that were previously broadcast and/or are scheduled to be broadcast.
11. The computer-implemented method of claim 10 , wherein the contribution of each object to the class variety score decreases with time.
12. The computer-implemented method according to claim 11 , wherein each class has a class importance factor.
13. A computer-implemented method for scheduling objects for delivery to one or more receiver units, the method comprising:
receiving one or more incoming objects at a computing device, each having a utility factor;
scheduling the objects at the computing device for delivery in an initial scheduling order, the value of the utility factor for each of the objects being dependent, at least to some degree, on the position of the object in the schedule;
calculating an overall schedule utility factor for the schedule at the computing device by combining the utility factors of each of the scheduled objects using a predefined function;
reordering the scheduled objects so that the overall schedule utility factor is increased; and
delivering one or more of the objects from the top of the schedule;
wherein one or more values for the utility factor for each object are related to an importance factor associated with the object, the importance factor being multiplied by a predetermined function that decreases with an age of the object to identify the utility factor, and the age of the object being related to the estimated time for delivery.
14. The computer-implemented method of claim 13 , wherein reordering the scheduled objects includes:
moving a selected object up one position in the schedule;
calculating an updated overall schedule utility factor;
determining if the updated overall schedule utility factor is greater than the previous overall schedule utility factor; and
retaining the new position of the selected object if the updated overall schedule utility factor is greater than the previous overall schedule utility factor.
15. The computer-implemented method of claim 14 , further comprising:
repeating the moving, calculating, determining, and retaining steps until the updated overall schedule utility factor is not greater than the previous overall schedule utility factor; and
returning the selected object to its previous position when the updated overall schedule utility factor is not greater than the previous overall schedule utility factor.
16. The computer-implemented method of claim 15 , wherein reordering the scheduled objects includes:
moving a selected object to a random position in the schedule;
calculating an updated overall schedule utility factor;
determining if the updated overall schedule utility factor is greater than the previous overall schedule utility factor; and
retaining the new position of the selected object if the updated overall schedule utility factor is greater than the previous overall schedule utility factor.
17. The computer-implemented method of claim 16 , further comprising:
repeating the moving, calculating, determining, and retaining steps until the updated overall schedule utility factor is not greater than the previous overall schedule utility factor; and
returning the selected object to its previous position when the updated overall schedule utility factor is not greater than the previous overall schedule utility factor.
18. The computer-implemented method of claim 17 , further comprising:
selecting another object and moving the selected object to a random position in the schedule;
repeating the moving, calculating, determining, and retaining steps until the updated overall schedule utility factor is not greater than the previous overall schedule utility factor; and
returning the selected object to its previous position when the updated overall schedule utility factor is not greater than the previous overall schedule utility factor.
19. The computer-implemented method of claim 13 , wherein the utility factor of an object is higher than another similarly situated object if the object is more timely.
20. The computer-implemented method of claim 13 , wherein the utility factor of an object increases the overall schedule utility factor more than another similarly situated object if the object provides more variety to the object schedule.
21. The computer-implemented method of claim 13 , wherein each object in the schedule has an estimated time for delivery based on the position of the object in the schedule, and the value of the utility factor for the object is dependent on the estimated time for delivery.
22. The computer-implemented method of claim 21 , wherein the estimated time for delivery of each object is calculated by:
estimating a current channel bandwidth for delivery of the scheduled objects; and
calculate an estimated time for delivery for each object using the size of each scheduled object and the estimated channel bandwidth.
23. The computer-implemented method according to claim 22 , wherein each object in the schedule is a member of one or more classes, and the value of the utility factor for each class is dependent on a measure of the objects assigned to the class.
24. The computer-implemented method according to claim 23 , wherein the measure of the objects is the number of objects assigned to the class.
25. The computer-implemented method according to claim 23 , wherein the measure of the objects is the number of object bytes assigned to the class.
26. The computer-implemented method according to claim 23 , wherein the measure of the objects is the sum of the object utility factors assigned to the class.