Systems and methods for assigning reference signals using a genetic algorithm

A method for assigning reference signal sequences for communication devices using a genetic algorithm is described. Reference signal sequences are assigned to each cell within a plurality of cells. A fitness function for each reference signal sequence is computed. The fitness function describes the effectiveness of the assignment. A first group of cells is selected to exchange their corresponding assignment information with assignment information corresponding to a second group of cells. The reference signal is assigned to a communications device within the area of one of the plurality of cells.

TECHNICAL FIELD

The present invention relates generally to communications and wireless communications related technology. More specifically, the present invention relates to systems and methods that assign reference signals using genetic algorithms.

BACKGROUND

A wireless communication system typically includes a base station in wireless communication with a plurality of user devices (which may also be referred to as mobile stations, subscriber units, access terminals, etc.). The base station transmits data to the user devices over a radio frequency (RF) communication channel. The term “downlink” refers to transmission from a base station to a user device, while the term “uplink” refers to transmission from a user device to a base station.

Orthogonal frequency division multiplexing (OFDM) is a modulation and multiple-access technique whereby the transmission band of a communication channel is divided into a number of equally spaced sub-bands. A sub-carrier carrying a portion of the user information is transmitted in each sub-band, and every sub-carrier is orthogonal with every other sub-carrier. Sub-carriers are sometimes referred to as “tones.” OFDM enables the creation of a very flexible system architecture that can be used efficiently for a wide range of services, including voice and data. OFDM is sometimes referred to as discrete multi-tone transmission (DMT).

The 3rdGeneration Partnership Project (3GPP) is a collaboration of standards organizations throughout the world. The goal of 3GPP is to make a globally applicable third generation (3G) mobile phone system specification within the scope of the IMT-2000 (International Mobile Telecommunications-2000) standard as defined by the International Telecommunication Union. The 3GPP Long Term Evolution (“LTE”) Committee is considering OFDM as well as OFDM/OQAM (Orthogonal Frequency Division Multiplexing/Offset Quadrature Amplitude Modulation), as a method for downlink transmission, as well as OFDM transmission on the uplink.

Wireless communications systems (e.g., Time Division Multiple Access (TDMA), Orthogonal Frequency-Division Multiplexing (OFDM)) usually calculate an estimation of a channel impulse response between the antennas of a user device and the antennas of a base station for coherent receiving. Channel estimation may involve transmitting known reference signals that are multiplexed with the data. Reference signals may include a single frequency and are transmitted over the communication systems for supervisory, control, equalization, continuity, synchronization, etc. Wireless communication systems may include one or more base stations that each transmits a reference signal that is assigned to a mobile station. However, the number of mobile stations may be greater than the number of reference signals. As such, benefits may be realized by improved systems and methods for assigning reference signals to mobile stations.

DETAILED DESCRIPTION

A method for assigning reference signal sequences for communication devices using a genetic algorithm is described. Reference signal sequences are assigned to each cell within a plurality of cells. A fitness function for each reference signal sequence is computed. The fitness function describes the effectiveness of the assignment. A first group of cells is selected to exchange their corresponding assignment information with assignment information corresponding to a second group of cells. The reference signal is assigned to a communications device within the area of one of the plurality of cells.

The fitness function may be a minimum maximum sum correlation of all sequences assigned to a given sector of a cell with sequences assigned to sectors of adjacent cells. Each reference signal sequence may be partitioned to each sector within a cell. In one embodiment, each reference signal sequence assignment is ranked based on the corresponding fitness function. An assignment with a lower fitness function may be ranked higher than an assignment with a higher fitness function.

In one embodiment, the first group of cells is selected based on the ranking of the first group of cells. The assignment information corresponding to the first group of cells may include a basic core assignment of reference signal sequences. The assignment information corresponding to the second group of cells may include a reference signal sequence re-use pattern.

In one embodiment, a third group of cells is selected to create a new generation. Mutations may be inserted into the third group of cells. The mutations may be random reference signal sequence assignments to the cells within the third group of cells following a pre-defined reference signal sequence re-use pattern. In one embodiment, the method is implemented by a base station.

A base station that is configured to assign reference signal sequences for communication devices using a genetic algorithm is described. The base station includes a processor and memory in electronic communication with the processor. Instructions are stored in the memory. Reference signal sequences are assigned to each cell within a plurality of cells. A fitness function for each reference signal sequence is computed. The fitness function describes the effectiveness of the assignment. A first group of cells is selected to exchange their corresponding assignment information with assignment information corresponding to a second group of cells. The reference signal is assigned to a communications device within the area of one of the plurality of cells.

A computer-readable medium comprising executable instructions is also described. Reference signal sequences are assigned to each cell within a plurality of cells. A fitness function for each reference signal sequence is computed. The fitness function describes the effectiveness of the assignment. A first group of cells is selected to exchange their corresponding assignment information with assignment information corresponding to a second group of cells. The reference signal is assigned to a communications device within the area of one of the plurality of cells.

Several exemplary embodiments are now described with reference to the Figures. This detailed description of several exemplary embodiments, as illustrated in the Figures, is not intended to limit the scope of the claims.

The word “exemplary” is used exclusively herein to mean “serving as an example, instance or illustration.” Any embodiment described as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments.

In the 3GPP Long Term Evolution (LTE) standard, reference signals are assigned to User Equipment (UE) (also referred to as mobile terminals) so that the UEs may perform accurate channel estimation. However, not all of the reference signals assigned to the UEs have a low cross-correlation. This may be the result of the dimensionality of the reference signals being much smaller than the number of UEs in use in any area at any one time. The lack of a low cross-correlation between reference signals brings forth the need for a method to re-use the reference signals.

Current methods of reference signal re-use have not been approached within the3GPP LTE standards. Instead, some forms of sequence hopping have been considered. Current systems may provide N sequences that are divided up amongst L cells. There may also be K sectors per cell. Further, in any sector there may be M sequences to be assigned per sector.

Typically, for 3GPP LTE, the reference signal sequences may be grouped together in blocks of K*M sequences which have low cross-correlation amongst themselves. However, these blocks of sequences may have larger cross-correlation outside of those blocks of sequences. Furthermore, typically it is assumed that each block of sequences are assigned to any one cell. The present systems and methods minimize the average (non-coherently measured) cross-correlation between adjacent sectors of cells. The problem of sequence assignment may be a type of integer programming problem that includes a large number of possible solutions. In one embodiment, a genetic algorithm is implemented to assign reference signal sequences to mobile terminals.

FIG. 1illustrates an exemplary wireless communication system100in which embodiments of the present systems and methods may be practiced. A base station102is in wireless communication with a plurality of user devices104(which may also be referred to as mobile stations, subscriber units, access terminals, etc.). A first user device104a, a second user device104b, and an Nth user device104nare shown inFIG. 1. The base station102transmits data to the user devices104over a radio frequency (RF) communication channel106.

As used herein, the term “OFDM transmitter” refers to any component or device that transmits OFDM signals. An OFDM transmitter may be implemented in a base station102that transmits OFDM signals to one or more user devices104. Alternatively, an OFDM transmitter may be implemented in a user device104that transmits OFDM signals to one or more base stations102.

The term “OFDM receiver” refers to any component or device that receives OFDM signals. An OFDM receiver may be implemented in a user device104that receives OFDM signals from one or more base stations102. Alternatively, an OFDM receiver may be implemented in a base station102that receives OFDM signals from one or more user devices104.

FIG. 2illustrates some characteristics of a transmission band208of an RF communication channel206in accordance with an OFDM-based system. As shown, the transmission band208may be divided into a number of equally spaced sub-bands210. As mentioned above, a sub-carrier carrying a portion of the user information is transmitted in each sub-band210, and every sub-carrier is orthogonal with every other sub-carrier.

FIG. 3illustrates communication channels306that may exist between an OFDM transmitter312and an OFDM receiver314according to an embodiment. As shown, communication from the OFDM transmitter312to the OFDM receiver314may occur over a first communication channel306a. Communication from the OFDM receiver314to the OFDM transmitter312may occur over a second communication channel306b.

The first communication channel306aand the second communication channel306bmay be separate communication channels306. For example, there may be no overlap between the transmission band of the first communication channel306aand the transmission band of the second communication channel306b.

In addition, the present systems and methods may be implemented with any modulation that utilizes multiple antennas/MIMO transmissions. For example, the present systems and methods may be implemented for MIMO Code Division Multiple Access (CDMA) systems or Time Division Multiple Access (TDMA) systems.

FIG. 4illustrates a block diagram400of certain components implemented in conjunction with a transmitter404. Other components that are typically included with the transmitter404may not be illustrated for the purpose of focusing on the novel features of the embodiments herein.

Data symbols may be modulated by a modulation component414. The modulated data symbols may be analyzed by other subsystems418. The analyzed data symbols416may be provided to a reference processing component410. The reference processing component410may generate a reference signal that may be transmitted with the data symbols. The modulated data symbols412and the reference signal408may be communicated to an end processing component406. The end processing component406may combine the reference signal408and the modulated data symbols412into a signal. The transmitter404may receive the signal and transmit the signal to a receiver through an antenna402. In one embodiment, the reference signal is assigned to a mobile terminal to enable the mobile terminal to perform channel estimation.

FIG. 5is a diagram500illustrating one embodiment of a plurality of cells502-538that illustrates a sequence assignment pattern and a sequence re-use pattern. An example cell540is provided for simplicity. The example cell540includes three sectors; sector A542, sector B544and sector C546. Each cell within the plurality of cells502-538may include three sectors in a manner similar to the three sectors included in the example cell540.

In one embodiment,84sequences may be assigned to the plurality of cells502-538. As illustrated, the plurality of cells502-538includes 19 cells. Each of the 19 cells includes three sectors arranged in a manner similar to the sectors of the example cell540. Each cell includes a number that represents the first sequence out of 12 sequences assigned to a given cell. For example, an inner cell502includes the number “13.” In other words, the inner cell502is assigned sequences13-24. As another example, a first outer cell518includes the number “37” and a second outer cell536includes the number “73.” In one embodiment, the first outer cell518is assigned sequences37-48and the second outer cell536is assigned the sequences73-84.

The diagram500also illustrates one embodiment of a reference signal re-use pattern. As stated above, the inner cell502is assigned sequences13-24. In addition, a third outer cell520is also assigned sequences13-24. In other words, the sequences13-24are re-used from the inner cell502to the third outer cell520.

FIG. 6is a block diagram illustrating one embodiment of a base station602that may assign reference signal sequences to mobile terminals. The base station602may also be referred to as a NodeB, an Evolved NodeB (eNB), etc. In one embodiment, the base station602implements a genetic algorithm to obtain a plurality of possible solutions relating to the assignment of sequences. The base station602may execute one or more iterations of the algorithm. As a result, the iterations cause the plurality of possible solutions to converge to an optimum solution.

In a genetic algorithm, a population P of possible solutions to an optimization problem evolves toward more optimum solutions. The possible solutions that are included in the population may be referred to as members of the population. A fitness function f is defined for each member of the population. The fitness function f may describe the effectiveness of a member in achieving a particular objective. The algorithm may include a reproduction strategy in which features of certain members of the population are exchanged with features of other members of the population to create a subset of a new generation of the population. The fitness function may be used to determine which members exchange features. Further, random mutations may be introduced into the new generation of the population. The new generation of the population may be used in the next iteration of the genetic algorithm.

A sequence assigner604may randomly assign blocks of sequences to cells. In one embodiment, a sequence partitioner606partitions a block of sequences assigned to an individual cell to the sectors of that cell. A fitness function generator608may generate a fitness function f for each assignment of the blocks of sequences. The possible assignments of the blocks of sequences may be referred to as a population. The fitness function f may describe how effective a particular solution is. For example, the fitness function f may indicate that a particular assignment is not effective because the cross-correlation between the blocks of sequences with adjacent sectors is high.

Using the fitness functions for the various assignments (solutions) of the blocks of sequences, a population organizer610ranks each solution. A sequence exchanger612exchanges features of certain solutions with other solutions. In one embodiment, the sequence exchanger612determines which solutions should exchange features based on the rankings provided by the population organizer610. The exchange of features may create a subset of a new generation of the population. A mutations component614may introduce random mutations into the new generation. The mutations may be introduced with random assignments of blocks of sequences to cells according to a pre-defined re-use pattern.

FIG. 7is a flow diagram illustrating one embodiment of a method700for assigning reference signal sequences using a genetic algorithm. The method700may be implemented by the base station602. A population representing possible assignments of sequences to cells may be provided. For example, a population with approximately500members (i.e. solutions) may be provided. Each member of the population may represent an assignment of sequences to one of 19 cells (as illustrated inFIG. 5). In one embodiment, sectors within a cell are identified702that share a common edge with another cell. The cell/sector geometry may be similar to the cell/sector geometry illustrated inFIG. 5. However, other cell/sector geometries may also implement the method700.

Blocks of sequences may be assigned704to each of the 19 cells. In one embodiment, the blocks of sequences are assigned randomly to each of the 19 cells. The random assignment may follow a prescribed re-use pattern. For example, for 84 sequences allocated with four sequences per sector, a re-use pattern as depicted in Table 1 might be used.

TABLE 1Re-Use Patterns for Base SequencesCellRe-Use Pattern #1Re-Use Pattern #2112 and 1711 and 17214133161548, 15 and 1816 and 195199 and 1869 and 118 and 12710 and 1310 and 14

Each block of sequences may be further partitioned706to each sector within the cells. In one embodiment, a fitness function f is computed708for each member of the population. The fitness function f may be the minimum maximum sum correlation of all sequences assigned to a given sector with sequences assigned in adjacent sectors. The fitness function f for a given population may be given by:
f(Pk)=maxsectorsΣall adjacent sectors(cross-correlations of all sequences in adjacent sector assignments)^2
where the term “Σall adjacent sectors” denotes the sum over all adjacent sectors to a given sector.

Each member of the population may be ranked710based on their corresponding fitness function f. In one embodiment, the members with the highest ranking are those for whom f(Pk) is the smallest. In other words, the members of the population are ranked710according to the lowest f(Pk).

A first number of cells may be selected712to exchange their blocks of sequences assignment with a second number of cells. The cells may be selected712based upon the rankings of the members of the population associated with the cells. In one embodiment, the first number of cells is 25% of the cells. For example, using the cell/sector geometry ofFIG. 5, the inner cell502and the first outer cells504-514are selected to exchange their blocks of sequences assignment with the blocks of sequences assignments of the outer cells516-538. In one embodiment, the features exchanged include a basic core assignment of blocks of sequences to cells is exchanged with a re-use assignment in adjacent cells.

In one embodiment, this exchange of assignments creates two “children” per parent which may make up 50% of a next generation of the population. In addition, a third number of cells are maintained714to create a part of the next generation of the population. In one embodiment, the lowest ranked 25% of cells are maintained714for the next generation of the population. Further, another 25% of the population may be randomly chosen to create the next generation. As previously explained, mutations may be introduced with random assignments of blocks of sequences to cells according to a pre-defined re-use pattern.

A determination716may be made whether a set number of iterations have been completed. If not, steps708-714may be repeated. The fitness function f may not decrease from iteration to iteration. In an assignment of108sequences with four sequences per cell a similar process may be implemented with the core assignment involving the inner cell502and the first outer cells504-514as well as some of the second outer cells520-524,532-536. The re-use pattern may vary amongst the remaining second outer cells516,518,526,528,530,538. In an assignment of84sequences with two sequences per cell, the assignment may be done in a similar manner.

In one embodiment, the method700may assign704sequences of different lengths statically as well. The short sequences may be concatenated into longer sequences. The fitness function f and rankings may be computed in a similar manner as previously explained. Accordingly, the method700assigns sequences of shorter lengths and longer lengths to a set of cells/sectors.

FIG. 8is a block diagram of a base station808in accordance with one embodiment of the disclosed systems and methods. The base station808may be an eNB, a base station controller, a base station transceiver, etc. The base station808includes a transceiver820that includes a transmitter810and a receiver812. The transceiver820may be coupled to an antenna818. The base station808further includes a digital signal processor (DSP)814, a general purpose processor802, memory804, and a communication interface806. The various components of the base station808may be included within a housing822.

The processor802may control operation of the base station808. The processor802may also be referred to as a CPU. The memory804, which may include both read-only memory (ROM) and random access memory (RAM), provides instructions and data to the processor802. A portion of the memory804may also include non-volatile random access memory (NVRAM). The memory804may include any electronic component capable of storing electronic information, and may be embodied as ROM, RAM, magnetic disk storage media, optical storage media, flash memory, on-board memory included with the processor802, EPROM memory, EEPROM memory, registers, a hard disk, a removable disk, a CD-ROM, etc. The memory804may store program instructions and other types of data. The program instructions may be executed by the processor802to implement some or all of the methods disclosed herein.

In accordance with the disclosed systems and methods, the antenna818may receive reverse link signals that have been transmitted from a nearby communications device902, such as a mobile terminal illustrated inFIG. 9. The antenna818provides these received signals to the transceiver820which filters and amplifies the signals. The signals are provided from the transceiver820to the DSP814and to the general purpose processor802for demodulation, decoding, further filtering, etc.

The various components of the base station808are coupled together by a bus system826which may include a power bus, a control signal bus, and a status signal bus in addition to a data bus. However, for the sake of clarity, the various busses are illustrated inFIG. 8as the bus system826.

FIG. 9illustrates various components that may be utilized in a communications device902such as a mobile terminal, in accordance with one embodiment. The device902includes a processor906which controls operation of the device902. The processor906may also be referred to as a CPU.

Memory908, which may include both read-only memory (ROM) and random access memory (RAM), provides instructions and data to the processor906. A portion of the memory908may also include non-volatile random access memory (NVRAM). The memory908may include any electronic component capable of storing electronic information, and may be embodied as ROM, RAM, magnetic disk storage media, optical storage media, flash memory, on-board memory included with the processor906, EPROM memory, EEPROM memory, registers, a hard disk, a removable disk, a CD-ROM, etc. The memory908may store program instructions and other types of data. The program instructions may be executed by the processor906to implement some or all of the methods disclosed herein.

The device902may also include a housing922that includes a transmitter912and a receiver914to allow transmission and reception of data between the communications device902and a remote location. The transmitter912and receiver914may be combined into a transceiver924. An antenna926is attached to the housing922and electrically coupled to the transceiver924.

The communications device902also includes a signal detector910used to detect and quantify the level of signals received by the transceiver924. The signal detector910detects such signals as total energy, power spectral density and other signals.

A state changer916of the device902controls the state of the device902based on a current state and additional signals received by the transceiver924and detected by the signal detector910. The device902is capable of operating in any one of a number of states.

The various components of the device902are coupled together by a bus system920which may include a power bus, a control signal bus, and a status signal bus in addition to a data bus. However, for the sake of clarity, the various busses are illustrated inFIG. 9as the bus system920. The device902may also include a digital signal processor (DSP)918for use in processing signals.

FIG. 9illustrates only one possible configuration of a communications device902. Various other architectures and components may be utilized.

Information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals and the like that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles or any combination thereof.

Functions such as executing, processing, performing, running, determining, notifying, sending, receiving, storing, requesting, and/or other functions may include performing the function using a web service. Web services may include software systems designed to support interoperable machine-to-machine interaction over a computer network, such as the Internet. Web services may include various protocols and standards that may be used to exchange data between applications or systems. For example, the web services may include messaging specifications, security specifications, reliable messaging specifications, transaction specifications, metadata specifications, XML specifications, management specifications, and/or business process specifications. Commonly used specifications like SOAP, WSDL, XML, and/or other specifications may be used.

While specific embodiments have been illustrated and described, it is to be understood that the claims are not limited to the precise configuration and components illustrated above. Various modifications, changes and variations may be made in the arrangement, operation and details of the embodiments described above without departing from the scope of the claims.