Binary-tree multiplexing scheduling

This application is a continuation of U.S. patent application Ser. No. 11/122,538, filed on May, 05, 2005, which is a continuation of U.S. patent application Ser. No. 10/314,691, filed on Dec. 9, 2002, which is a continuation of U.S. patent application Ser. No. 10/010,868, filed on Dec. 7, 2001 and claims priority from Provisional Patent Application No. 60/297,807, filed on Jun. 13, 2001.

This application is related to wireless communications.

In wireless communications, there may be multiple blocks of information from multiple sources required to be scheduled for periodic access of single channel. Due to constraints of the physical layer of the channel, such as limited transmission rate or power level, each block of information may need to be segmented into several segments, with each segment scheduled at a position for accessing the channel.

While scheduling the different sources of information, several requirements must be considered. The single channel is divided into multiple addresses or positions to which information segments are assigned or scheduled. As multiple sources of information have their associated information block segments scheduled along the channel positions, the scheduled information is considered multiplexed onto the channel. Therefore, conflicts of positions between different segments of information must be avoided, i.e., a channel position cannot be shared by segments of two different information blocks. Thus, the first requirement is that each position can be assigned to only one segment of information.

Second, since the repetition period required by each source of information is based on functions associated with the information, the different sources of information require different periods for accessing a single channel. For example, in 3G UMTS, a Broadcast Channel (BCCH) having System Information Blocks (SIBs) with different periods signifies various latency of system functions, such as Power Control or Cell Selection. Shorter repetition periods lead to shorter latency since User Equipment (UE) can receive system information faster than required to perform system functions. However, this requirement compromises efficient use of limited bandwidth of the channel. Shorter repetition periods also imply heavier loading to the single channel and limit the possibility to allocate the bandwidth for other usages.

Third, in order to maximize channel efficiency, unassigned positions on the channel should be kept to a minimum in order to maximize the utilization of the channel.

Fourth, segments of the same block of information should be scheduled as consecutively as possible, since information often cannot be read until all segments of the same source of information arrive at the receiver.

One solution to this problem has been to use a first come first service (FCFS) assignment method. In this method, the scheduler begins scheduling with a first source\'s block of information. Once the first source of information is scheduled, the scheduler then assigns positions to the block of information of a second source of information on to the single channel. While scheduling the second source of information, the scheduler needs to avoid assigning channel positions that are already assigned to the first source\'s block of information. Thus, while scheduling the subsequently scheduled blocks of information, the scheduler needs to keep track of all positions that are already assigned to previously scheduled blocks of information.

FIGS. 1A and 1B show an example in which three sources of information are scheduled to access a single channel, CHANNEL A. Three blocks of information, SOURCE 1, SOURCE 2, and SOURCE 3 are shown having varying segment counts and repetition periods. FIG. 1B shows the scheduling of the red, blue and green information segments to positions on CHANNEL A based on the segment counts and required repetition periods of SOURCE 1, SOURCE 2 and SOURCE 3. As evident in CHANNEL A shown in FIG. 1B, there are unassigned positions remaining after the scheduling of the SOURCE 1, SOURCE 2 and SOURCE 3 information blocks (8, 9, 18, 19, 20 . . . ). As more blocks of information with different segment count and repetition period constraints are added for scheduling on CHANNEL A, a scheduling method that does not compromise one or more of the above requirements becomes difficult to achieve.

Using the FCFS approach results in several compromises, such as segments belonging to the same source\'s block of information cannot be scheduled consecutively since the solution does not reserve enough consecutive positions available that can satisfy information with large segment counts. This compromise is shown in FIG. 1B for SOURCE 3, as the green information segments are not scheduled consecutively on CHANNEL A. This delays the reading of the SOURCE 3 block of information as the receiver awaits for all segments of the information block to arrive. Also, due to the periodic nature of the scheduling, two sources of information may conflict with each other at some future position, thus creating the need to perform global searches each time an information segment is to be assigned to a position in order to avoid the possible conflict.

What is needed is a method and system that determines the required bandwidth for a given set of information blocks and that efficiently schedules information while optimizing for the above requirements.

A method for multiplexed scheduling of information blocks from multiple sources on a single communication channel divided into multiple address positions is disclosed. The information block from each source has a repetition period and is divided into a number of segments. Once the total number of positions on the channel to be scheduled is determined, positions are mapped in a non-sequential order corresponding to nodes in a binary tree, whereby each layer of the binary tree corresponds to a particular repetition period. The blocks of information are assigned in the order of ascending repetition period. The information segments of each block are scheduled to unassigned positions at the associated binary tree layer as well as to all corresponding child nodes.

BRIEF DESCRIPTION OF THE DRAWINGS

A more detailed understanding may be had from the following description, given by way of example and to be understood in conjunction with the accompanying drawings.

Continue reading about Binary-tree multiplexing scheduling...
Full patent description for Binary-tree multiplexing scheduling

Brief Patent Description - Full Patent Description - Patent Application Claims

Click on the above for other options relating to this Binary-tree multiplexing scheduling patent application.
###


How KEYWORD MONITOR works... a FREE service from FreshPatents
1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored.
3. Each week you receive an email with patent applications related to your keywords.  
Start now! - Receive info on patent apps like Binary-tree multiplexing scheduling or other areas of interest.
###


Previous Patent Application:
Technique for achieving connectivity between telecommunication stations
Next Patent Application:
Method for bandwidth recovery of communication system
Industry Class:
Multiplex communications

###

Design/code © 2009 FreshContext LLC/Freshpatents.com. Website Terms and Conditions - Also read: About this Page
Patent data source: patents published by the United States Patent and Trademark Office (USPTO)
Information published here is for research/educational purposes only (and in conjunction with our Keyword Monitor) and is not meant to be used in place of the full USPTO patent document/images or a comprehensive patent archive search. Complete official applications are on file at the USPTO and often contain additional data/images (Freshpatents is currently text-only). FreshPatents.com is not affiliated with or endorsed by the USPTO or firms/individuals or products/designs/ideas related to listed patents.

FreshPatents.com Support
Thank you for viewing the Binary-tree multiplexing scheduling patent info.
IP-related news and info


Results in 2.01044 seconds


Other interesting Feshpatents.com categories:
Canon USA , Celera Genomics , Cephalon, Inc. , Cingular Wireless , Clorox , Colgate-Palmolive , Corning , Cymer , paws