Multiplex communications – Communication over free space – Having a plurality of contiguous regions served by...
Reexamination Certificate
1998-10-01
2001-10-09
Chin, Wellington (Department: 2664)
Multiplex communications
Communication over free space
Having a plurality of contiguous regions served by...
C370S322000, C370S902000, C455S450000
Reexamination Certificate
active
06301233
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Not Applicable
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the allocation of radio frequency channel resources in a partitioned wireless telecommunications system. More particularly, the invention concerns a method for use in a cellular telephone system, personal communications service (PCS) network, or equivalent enterprise for efficiently performing flexible channel allocation to support call origination, termination and handoff.
2. Description of the Prior Art
Modern wireless telecommunications systems employ the concept of a partitioned service area formed by a network of contiguous geographic subdivisions, known as cells. Each cell is served by a base station that communicates with mobile units within the cell via assigned radio frequencies. The base station provides a link between the mobile units and a land-based communications network, such as a public switched telephone network, to which the base station is connected via a Digital Cellular Switch (DCS). Each base station handles call origination and termination requests from mobile units within a cell, and performs the important function of negotiating call handoffs with other base stations on behalf of mobile units transitioning between cells. A computerized Mobile Switching Center (MSC) assists the base stations to perform these functions.
One of the implications of a partitioned wireless telecommunications system is that radio frequency channels may be reused, but this is only true for cells that are relatively remote from each other. Base stations that are three cells apart or less are considered to be potentially mutually interfering and will not be allowed to share channels without restriction. Using the conventional hexagonal cell model, any given cell has thirty-six first, second and third tier cell neighbors that are potential interferers. Considering that each cell may be subdivided into six sectors serviced by individual directional antennas, each sector has seventy-two potentially interfering sector neighbors. For these potentially interfering cells and cell-sectors, available channels must be carefully allocated in a manner that avoids substantial inter-cell or inter-sector interference.
Although channels can be allocated between potentially interfering cells and sectors in mutually exclusive fashion, such that simultaneous channel sharing never occurs, this is inefficient because channels tend to be underutilized. It would be preferable to allocate channels using a flexible channel allocation technique that allows channel sharing under appropriate conditions, yet does not consume excessive processor resources at the computerized mobile switching center. What is required is a system for efficient flexible channel allocation that minimizes processor overhead and system latency, and provides robust service to end users at call setup and handoff time.
BRIEF SUMMARY OF THE INVENTION
An efficient flexible channel allocation method is provided for use in analog and digital wireless telecommunications systems populated by groupings of contiguous cells, each of which communicates with mobile units over the allocated radio frequency channels. In accordance with a preferred embodiment of the invention, an optimum channel is selected for use by a requesting cell from a cost table containing interference values representing the potential total cost (interference) of the requesting cell (or a sector thereof) using one or more candidate channels. The selected channel is allocated to the requesting cell or sector and the cost table is updated to reflect the new channel allocation. For ease of description, the term “cell” as used hereinafter refers to both cells and cell sectors.
The cost table in accordance with the preferred embodiment of the present invention is a cumulative cost table formed as a two dimensional array of N by M values, where N is the number of cells in the telecommunications system and M is the number of candidate channels available for selection by a cell. Each row of the cumulative cost table contains the cumulative costs to one of the cells of using each of the candidate channels, and each column of the cumulative cost table contains the cumulative costs to each of the cells relative to a single channel.
In order to identify an optimum channel candidate for a requesting cell, it is only necessary to consult a single row of the cumulative cost table, i.e., the one corresponding to the requesting cell, and select a candidate channel having the lowest interference. Processing time is saved because channel allocation is based on a simple cost table look-up operation. The more processor intensive operation of updating the cost table is only performed after channel selection has been completed. Moreover, the method uses a highly efficient strategy for cost table updates that involves simple addition operations as a substitute for complex matrix multiplication.
By way of explanation, the cumulative cost table is definable in mathematical terms as the result of a matrix multiplication of an N×N incremental cost table and an N×M busy table, where N and M are the same as defined above. Each row of the incremental cost table contains the incremental costs to one cell resulting from radio transmissions in each of the remaining cells in the telecommunications system. Each column of the incremental cost table contains the incremental costs that one cell imposes on each of the remaining cells as a result of radio transmissions in that cell. The incremental cost values are established when the telecommunications system is placed in service, and may be subsequently updated thereafter.
The busy table is a matrix containing binary values. Each row indicates the channels being used by one cell. Each column indicates the cells that are using a single channel. The busy table acts as a mask which when multiplied by the incremental cost table, produces the values in the cumulative cost table. More specifically, each cumulative cost table entry represents the matrix multiplication of a single row of the incremental cost table and a single column of the busy table. Remembering that a row of the incremental cost table is a series of costs imposed on a single cell by each of the other cells engaging in radio transmissions, and that a column of the busy table denotes which cells are transmitting on a given channel, the cumulative cost table entry represents the cost to a single cell resulting from use of a given channel by all other cells. This is simply a sum of the values in one row of the incremental cost table that are “switched on” by the busy table column values as a result of other cells using the channel.
Rather than engage in time consuming matrix multiplication, the invention adopts an innovative strategy that greatly simplifies the cumulative cost table update calculation. First, it can be shown mathematically that when any channel is allocated to a cell, only a single column of the incremental cost table needs to be added to a single column of the cumulative cost table in order to update the latter. Moreover, although the incremental cost table columns are N members long, many of the cost values therein will be sufficiently insignificant that they can be ignored. Thus, a compressed incremental cost table may be formed. Further processing efficiency is obtained by appending address pointers to each entry in the compressed incremental cost table that index to the corresponding row locations in the cumulative cost table where the incremental cost values are to be added.
To further speed up processing, the compressed incremental cost table is rotated such that each column in the compressed incremental cost table, which would typically be stored in nonsequential memory locations, is rotated and stored as a row in sequential memory locations. These memory locations can be accessed with minimal processor clock cycles and the incremental cost values therein
Chen Shujen
Ku Jeng-Yann Wellington
Chin Wellington
Duft Walter W.
Lucent Technologies - Inc.
Pham Brenda H.
LandOfFree
Efficient flexible channel allocation in a wireless... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient flexible channel allocation in a wireless..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient flexible channel allocation in a wireless... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555260