Cognitive radio engine based on genetic algorithms in a network

A genetic algorithm (GA) approach is used to adapt a wireless radio to a changing environment. A cognitive radio engine implements three algorithms; a wireless channel genetic algorithm (WCGA), a cognitive system monitor (CSM) and a wireless system genetic algorithm (WSGA). A chaotic search with controllable boundaries allows the cognitive radio engine to seek out and discover unique solutions efficiently. By being able to control the search space by limiting the number of generations, crossover rates, mutation rates, fitness evaluations, etc., the cognitive system can ensure legal and regulatory compliance as well as efficient searches. The versatility of the cognitive process can be applied to any adaptive radio. The cognitive system defines the radio chromosome, where each gene represents a radio parameter such as transmit power, frequency, modulation, etc. The adaptation process of the WSGA is performed on the chromosomes to develop new values for each gene, which is then used to adapt the radio settings.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to radio systems providing wireless voice and data links in networks, and more particularly, to a cognitive radio engine architecture which is capable of working under changing and unanticipated circumstances and in the presence of hostile jammers and interferers. The cognitive radio engine is capable of continuously adapting to its environment to conserve resources, such as radio frequency spectrum and battery power, in those applications where those resources are at a premium.

2. Background Description

Most traditional radios have their technical characteristics set at the time of manufacture. More recently, radios have been built that self adapt to one of several preprogrammed radio frequency (RF) environments that might be encountered. Cognitive radios go beyond preprogrammed settings to operate both in known and unknown wireless channels.

A cognitive radio can sense its environment and alter its technical characteristics and operational behavior to benefit both itself and its geographical and spectral neighbors. The ability to sense and respond intelligently distinguishes cognitive radios from fixed or adaptive radios. The characteristics of fixed radios are set at the time of manufacture. An adaptive radio can responds to channel conditions that represent one of a limited set of anticipated events. Adaptive radios use artificial intelligence (AI) algorithms that are basically a series of “IF, THEN, ELSE” algorithms. The radio may fail to take any useful action if it meets conditions that its designers never anticipated.

In contrast, a cognitive radio can respond intelligently to an unanticipated event; i.e., a wireless environment (channel) that it never encountered before. The result is enhanced performance (throughput, quality of service (QOS), and security) for the cognitive radio's network and reduced interference to other networks. TheOxford English Dictionary(OED) defines “cognitive” as “pertaining to cognition, or to the action or process of knowing”, and “cognition” is defined as “the action or faculty of knowing taken in its widest sense, including sensation, perception, conception, etc., as distinguished from feeling and volition”. Given these definitions, the process of sensing an existing wireless channel, evolving a radio's operation to accommodate the perceived wireless channel, and evaluating what happens is appropriately termed a cognitive process. This approach includes both awareness of the wireless channel and judgment of the best possible action to take given this knowledge.

Most cognitive computing systems to date have been based on expert systems and neural networks. Such systems can be quite brittle in the face of unknown environments or else they require extensive training.

SUMMARY OF THE INVENTION

It is therefore an object of the present invention to provide a cognitive radio architecture based on genetic algorithms capable of adapting to unknown and unexpected environments.

According to the invention, there is provided a cognitive radio architecture which is based on biologically based models of cognition inspired by child development theories of two-way associative learning through play. The cognitive model of the invention imitates the ability of young minds to adapt rapidly to new situations. Genetic algorithms are well suited for this task because of their ability to find global solutions to changing solution spaces that are often quite irregular. Genetic algorithms are (a) able to synthesize best practices through the crossover operation and (b) enable spontaneous inspiration and creativity through the mutation operation. The multi-tiered genetic algorithm architecture of the invention allows sensing of a wireless channel at the waveform or symbol level, on-the-fly evolution of the radio's operational parameters, and cognitive functions through use of a learning classifier, meta-genetic algorithm, short and long term memory and control.

The invention has application in military and disaster communications, where radio systems must work under changing and unanticipated circumstances and in the presence of hostile jammers and interferences. The invention also has application in civilian radio communication systems such as cellular telephones, where spectrum and battery power are at a premium and in which the radios must continuously adapt to conserve these resources.

Referring now to the drawings, and more particularly toFIG. 1, there is shown an example of an implementation of the cognitive radio system according to the invention in a network having a broadband wireless RF link. The network comprises a first plurality of broadband users101to10nconnected to a first router11and a second plurality of broadband users121to12nconnected to a second router13. The first and second routers11and13are connected by means of a cognitive radio link15established by a first adaptive radio16controlled by a cognitive radio engine16aconnected to router11and a second adaptive radio17controlled by a cognitive radio engine17aconnected to router13. In this example, the router11is connected to a general internet protocol (IP) network, represented by a cloud18. There is present in the illustrated environment a radio19which is a source of interference to the cognitive radio link15. It is the function of the cognitive radio engines16aand17ato control their respective adaptive radios16and17so as to minimize or eliminate the interference generated by the radio19to maximize performance without obstructing the operation of radio19.

FIG. 2shows in block diagram form the conceptual components of the cognitive engine. These include a monitor and control component21, the function of which is to exploit trends, an adaptation and process component22, the purpose of which is learning, and resources components23and24, respectively concerned with the environment and the radio.FIG. 3shows in more detail the architecture of the cognitive engine. The channel30, providing data and RF signals, is connected to the radio hardware32which, in turn, is connected to the cognitive engine34. The radio hardware32, in addition to the usual RF and conversion circuitry, includes a channel estimation process321and a radio baseband processor322. The output of the channel estimation process321is input to the wireless channel genetic algorithm (WCGA) module341of the cognitive engine34. This module generates a Hidden Markov Model (HMM) channel model which is input to the cognitive system monitor (CSM)342. The CSM342also receives radio parameters and performance statistics from the radio baseband processor322. The CSM342generates evaluation functions, associated weights, child chromosomes, and templates which are input to the wireless system genetic algorithm (WSGA) module343. The evaluation functions, weights, child chromosomes, and a template are referred to as the WSGA information packet. The WSGA343generates radio parameters which are applied to the radio baseband processor to adapt the radio to the changing environment.

FIG. 4shows the process implemented by the cognitive engine. The process begins by initializing the radio with default settings in the initialization block401. The WCGA341collects information from the channel estimation process321and models the channel in function block402. A test is made in decision block403to determine if the channel model is complete. If not, the process loops back to function block402, but if the model is complete, the channel model is passed to the CSM342in function block404. In function block405, the CSM342determines if a new radio configuration is needed, builds trends from the WCGA341and radio statistics, and develops a WSGA information packet for the WSGA343. A test is made in decision block406to determine if the system needs a new configuration. If not, the process loops back to function block405; otherwise, a WSGA information packet is passed to the WSGA343in function block407. In function block408, the WSGA343develops a system chromosome and creates fitness from mathematical idealization of radio performance. A test is then made in decision block409to determine if the new system developed by the WSGA343is close to optimization. If not, the process loops back to function block408; otherwise, the new system configuration is passed to the baseband radio system322in function block410. The baseband radio system322then reconfigures itself in function block411. Thereafter, the radio system monitors its performance and collects statistics (bit error rate (BER), data rate, etc.) in function block412. These radio performance parameters are collected in function block413and input to the CSM at function block405. The process shown in this flowchart is cyclical and runs continuously.

FIG. 5is a block diagram of the CSM showing the functional relationships of the several components ofFIG. 3. The radio hardware, here shown as block50, generates radio feedback parameters501which are input to the CSM, here shown as block51. The CSM51is also connected to the WCGA and WSGA, here shown as blocks52and53, respectively. More particularly, the WCGA52, through its TCP/IP (transport control protocol/internet protocol) socket layer521, interfaces with the corresponding socket layer511of the CSM51, while the WSGA53, through its TCP/IP socket layer531with the corresponding socket layer512of the CSM51. The CSM51includes, among other things, a knowledge base (KB) in long term memory (LTM)513. The CSM51classifies observed environment (i.e., the channel model), updates the knowledge base in long term memory, and synthesizes an information packet for the WSGA (e.g., fitness function, initial population, weights, and templates). TCP_KB_PORT is an optional feature to allow socket-layer communications with LTM stored on a remote radio system in a distributed implemenation.

FIG. 6shows in more detail the structure of the CSM51, and in this figure like reference numerals to those inFIG. 5represent the same of similar components. An observed channel and location buffer601receives input from the WCGA52via the TCP/IP socket layer511and radio parameters from the radio and WSGA performance API (application program interface)602. The data in this buffer is supplied to a channel statistics processor603. The statistics computed by the processor603are input to a learning channel classifier604which, in turn, provides outputs to a short term memory (STM)605and a channel updater606. The channel updater606generates a pointer to a TCP/IP link converter in the cognitive knowledge base in the long term memory (LTM)513. The LTM513interfaces with the short term memory (STM)605which, in turn, interfaces with the goal evolver607. The goal evolver607also receives input from the radio and WSGA performance API602and provides an output to the estimated radio goal and location buffer608. The data in this buffer is provided to the WSGA53.

The CSM51is an evolutionary algorithm that is the core of the cognitive radio intelligence and directs all knowledge gained from the sensing processes to the adapting processes. The CSM51is a meta-GA (genetic algorithm), serving as short and long term memory to understand and utilize past trends in system behavior. The CSM51is the creative side of the cognitive radio brain. The WSGA53takes direction from the CSM51and performs its own genetic algorithm (GA) to redesign the radio configuration. The WSGA53is the logical side of the cognitive radio brain. The WSGA53acts upon a chromosome containing parameters like transmitter power, frequency, bandwidth, modulation, channel coding, etc. It understands the regulatory and physical environment and passes a templates to the GA informing the GA what parameters may be legally altered and what parameters should be left alone, based on the knowledge gained from the best trends. The WSGA53also receives the fitness evaluation to direct the algorithm in how it should attempt to evolve. For example, the fitness could be a measure of the minimum BER, minimum power consumption, maximum carrier to noise ratio (C/N), minimum latency, maximum data rate, or a combination of these. The GA will attempt to optimize these fitness functions. Depending on what information the CSM51receives from the system and the WCGA52sensing algorithm, the fitness function may change to achieve new goals. The WSGA53works within the knowledge established by the CSM51to find a configuration that should work. The WSGA53then passes the new radio configuration to the RF and digital baseband equipment, which then reconfigures itself. After the radio tries the new configuration, the CSM51will evaluate the radio's performance to assess the success of the configuration. If the CSM51determines that the radio's performance is not optimum, it will inform the WSGA53that a new configuration is needed.

The task of the WCGA52is to sense the environment and model it as accurately as possible to provide information about the multipath environment or other interferences that can cause errors in the channel. The environmental information is then sent to the CSM51for processing. The CSM51can then use the model to evaluate what functions are applicable to the current channel. Based on the environment, the CSM51can determine how best to analyze the system configuration, what performance to attempt to achieve, and how best to set the fitness evaluation function for the WSGA53so that the fitness of the system chromosome will converge upon the appropriate radio settings.

As an example, consider a radio designed for the Unlicensed National Information Infrastructure (UNII) band. The WCGA52first models the channel and then the CSM51estimates the maximum data rate achievable within the system given its knowledge of that channel. The CSM51will inform the WSGA53to use the data rate as its fitness evaluation and pass the maximum data rate as the fitness goal to achieve. Using chromosome coding and genetic tagging of the information requested, the CSM51will also tell the WSGA53that it is limited by the frequency and bandwidth of the UNII band. The WSGA53will perform the GA to produce new system configurations and test them based on two metrics: does the new configuration meet the regulatory requirements and does it achieve the data rate requirement? When the WSGA53is satisfied that the regulatory requirements are met and that the data rate requirement is close to being achieved based on the fitness evaluation that it was provided by the CSM51, it sends the information to the radio for reconfiguration. Artificial intelligence researchers would consider the WSGA53as working with “simulations”, while the CSM51monitors “reality”, which means that the simulated results will often deviate from the actual radio performance. Therefore, the CSM51will have to monitor how the radio performs so that it can instruct the WSGA53if a new configuration is required.

The process implemented by the CSM51is illustrated in the flowchart ofFIG. 7, to which reference is now made. The process begins in input block701where the observed channel from the WCGA52is read into the observed channel and location buffer601. The channel metric calculator603then calculates the ranking metric of the observed channel in function block702. The ranking metric can be anything that distinguishes the channel like average bit error rate or average burst error length, which is the current metric being used. The learning channel classifier604finds the closest match to the observed channel in long term memory (LTM) in function block703. This is done by GA channel index search by the ranking metric or by binary tree search by the ranking metric. Any change is indicated to the goal evolver607via the short term memory (STM)605. The LTM513is updated in function block704. The STM605is populated in function block705with knowledge base chromosomes in LTM513containing similar channels. In function block706, radio performance parameter and existing WSGA simulation fitness, population, tags and templates are read into the goal evolver607. Goals in the STM605are crossed over or mutated with estimated radio goal for the observed channel in function block707. Then, in decision block708, a test is made to determine if the optimal goal has been chosen. If not, the process loops back to function block707, but if so, the data in estimated radio goal and location buffer608is formatted into an information packet for the WSGA53in function block709. The formatted packet is then transmitted to the WSGA53in output block710, and the process returns to input block701. The algorithm is a never-ending loop while the radio is operational to provide continuous evolution of the radio's settings to either continually search for a more optimal solution, or to adapt the radio in a time-varying channel.

FIG. 8is the flowchart for the learning channel classifier routine of function block703inFIG. 7. The input801is the computed ranking metric from the channel statistics processor603. The channel statistics are converted to channel cluster index j, using best fit weights, in function block802. The statistics of the observed channel are compared with those of the corresponding channel stored in long term memory513in function block803. A test is made in decision block804to determine if the comparison matches within a predetermined difference (delta). If so, the location of the estimated channel j is stored in register m, a pointer in the CSM to a member of LTM513, in function block805; otherwise, a new candidate is selected from LTM513in function block806, and a return is made to function block803.

FIG. 9is the flowchart for the update LTM routine in function block704inFIG. 7. The input901is new member. A ranking metric of the observed channel is calculated in function block902. A test is made in decision block903to determine if the current LTMLength is equal to zero. If it is, the observed channel is placed in the first position of LTM in block904and the function exits at905. Otherwise, the length of LTM is compared the MaxLTMLength, the maximum possible length of the LTM member, in decision block906. If the current length is less than the maximum length, function block907determines what member of the population, pointed to by register m has the closest matching ranking metric to the observed channel. If the metrics are the same as determined in decision block908, there is no need to update LTM, so the function exits909. If the metrics are different, the observed channel is inserted into LTM at position pointed to by m at block910. The current LTM length is then incremented by function block911. It is important to note that the channel that matched closest to the observed channel is not replaced, the new channel is just inserted at this position to maintain proper order based on the ranking metric in LTM.

If the current LTM length equals the maximum LTM length from block912, block913finds the closest matching member of LTM like block907did. The differences in the metrics between the observed channel and the two surrounding channels of LTM member m is calculated in block914as ε0and the difference between LTM member m and its two surrounding neighbors is calculated as εm, where μ is the Euclidean distance between the LTM members surrounding m. Decision block915determines if ε0is less than εm, whereby the current member of LTM at position m is replaced by the new channel in block916and the function exits at917; otherwise, the current LTM member is not replaced and the function exits at917. This algorithm ensures that LTM exists of observed channels that maximize the distance between any two members to provide as wide a scope of the possible channels as possible.

FIG. 10is the flowchart for the populate STM routine in function block705inFIG. 7. The register m as developed in block704is passed to this function in block1001. If the current LTM length is less than MaxSTMLength, the maximum number of members short term memory (STM) can hold, as decided in block1002, then block1003sets CurrentSTMLength, the current length of STM, to the current length of LTM. Otherwise, block1004sets the current STM length to the maximum STM length. Block1005begins a loop which takes LTM members at m minus i, an index value that starts at 0 and increments in steps of 1 to CurrentSTMLength/2, and places them into STM in block1006. Block1007initializes j, another index value, to zero. Index i is then set in block1008to the middle of the current STM member to populate the upper half of STM. If the index i is less than CurrentSTMLength, as determined in decision block1009, block1010populates the upper half of STM by member of LTM at m plus j. Block1011increments index j. When loop1009exits, STM is fully populated with the LTM members surrounding the closest matching member of LTM to the observed channel, m and the routine exits at1012.

FIG. 11is the flowchart for the read radio performance parameters routine in function block706inFIG. 7. The inputs1101are the radio feedback parameters read by the radio performance API (application program interface). These include such things as BER (bit error rate) power, battery life, etc. The radio performance API stores the radio parameters in a buffer to be read by the goal evolver607in function block1102. The output1103is a signal to the goal evolver607that new radio performance values are available.

FIG. 12is the flowchart for the goal optimizer routine in function block707and decision block708inFIG. 7. The inputs1201are the radio performance parameters and existing WSGA simulation fitness, population, and templates. Block1202compares the simulated meters, ƒWSGAwith the actual observed parameters from the radio, ƒradio. The differences shows how far the WSGA simulation was from the actual operation of the radio. From here, it can be determined how necessary a new configuration is required, or learn about behavior to avoid or promote in the future. Block1203ranks the members of STM in respect to two objectives: similarity and utility (drawing from decision theory vocabulary). The similarity functions determine how close the observed channel is to each member in the short term memory, and the utility function determines how successful each member of STM has been in the past. Poor performing members of memory lose worth over time and successful members gain worth. The candidate member of STM is that member who maximizes both similarity and utility. In the terms ofFIG. 12, the goal vectors refer to the information sent to the WSGA about what the channel is and how it should be evaluated (fitness functions, weights, template, and child chromosomes).

The STM then undergoes manipulation through a genetic algorithm in block1204, which is an evolutionary process that attempts to alter the goal vectors of the poor performing channels by combining successful pieces of goal vectors from other members of STM. Block1205illustrates how a member of STM may look, with the channel on the left, which is used to determine the similarity function, and goals in the vector on the right. In this case, the genetic algorithm in1204attempts to alter the goal vectors of the listed channel by combining goals A, B, C, and D from different members of STM. These become the new goal vector associated with that channel, which will hopefully produce a better utility function than the previous goal vector. This process attempts to “play” with past behavior to learn better ways of behaving in the future.

The STM member that was chosen for the highest similarity and utility is then sent to the WSGA to create a new set of radio parameters in block1206. Block1207shows the WSGA sending the new system chromosome back to the CSM as well as the simulated parameters. Block1208shows the radio transmitting the actual parameters associated with the new system chromosome back to the CSM. Blocks1207and1208run independent of the CSM, and so they must be asynchronously timed where the information coming from either entity (the WSGA or the radio) can come at any given time. When the radio parameters are returned, they are compared to the simulated parameters by observing the differences between the simulated and the actual parameters at function block1209. This information is then used by block1210to update the worth associated with the STM member used to generate the current system chromosome. If the real system performs worse than the simulation, it indicates a problem with the STM goal vector, and the worth of that STM member is decreased. If the simulated and actual meters are the same, or the actual meters work better than the simulated meters, the worth of the associated STM member is increased. This method is slightly counter-intuitive, because an STM member can be rewarded if the real system performs better than expected, which indicates that the simulation environment failed; however, in actual operation, it does not matter if the simulation is wrong as long as the values it produces works, so the reward is allowed.

Note that there is no exit to this routine. As stated above, it runs asynchronously and constantly takes in information from the radio, the WSGA, and the rest of the CSM to continually update and adjust the members' goal vectors in memory.

FIG. 13is the flowchart for the transmit goal routine in output block710inFIG. 7. The input1301is goal in buffer608. A TCP (transport control protocol) socket packet with WSGA information is built in function block1302. A socket is created in function block1303, and the created socket is bound to an unused local port in function block1304. The socket is then connected to a remote port in function block1305, and the TCP packet is sent with the WSGA information to the remote system in function block1306. The process ends by closing the connection in function block1307and exiting at block1308.

The wireless channel genetic algorithm (WCGA) is, in general, a mechanism by which the channel is observed and modeled for use in the CSM. The current instantiation of the WSGA involves the modeling of any wireless channel error using the compact form of a Hidden Markov Model (HMM).FIG. 14is a block diagram of the WCGA. A channel capturing device1401(i.e., the channel estimation process321inFIG. 3) provides the input to the WCGA52. The channel capturing device can be any known method of modeling a channel using devices such as a channel sounder, a frequency domain capturing device (Fast Fourier Transform device), training data, etc. The WCGA creates a machine-usable model of the radio channel. This is transmitted via the TCP/IP socket layer521to the corresponding TCP/IP socket layer511of the CSM51.

A specific instantiation of the WCGA is shown inFIG. 15. This instantiation models burst errors with GA-trained HMMs. The WCGA uses an error stream for the input, which is a train of symbols representing the number of bit errors per symbol. For the WCGA to produce an accurate model, many thousands of error symbols must be collected, which would require a long training sequence, taking both time and bandwidth. A more compact and efficient approach to channel modeling is to utilize the information collected by the channel sounder. While the channel sounder response can provide an immediate understanding of the channel, the data received from the sounder is large and bulky. By using the channel sounder response, a model of the channel is derivable by simulating the channel as a filter with an impulse response derived from the channel sounder. A random bit sequence passed through the simulated channel will produce an error sequence. Because we are interested in a statistical model of the channel, we can use the simulated channel instead of the error sequence. The Hidden Markov Model (HMM) of the channel developed by either a true error sequence or a simulated error sequence is still a statistical representation of the channel. However, this representation is very small compared to the channel sounder data and is capable of representing the channel equally well.

The channel,1501, is received by a channel sounder1502, in this case the broadband channel sounder developed at the Center for Wireless Telecommunications. This channel sounder uses impulse transmitted from one radio and is captured by the sounder on another radio using a sliding correlator sounding technique, which captures a small amount of energy from the pulse at different offsets. Because the transmitted pulse is repetitious and the channel is assumed stationary, after K number of pulses (in this case, 40000), the entire pulse has been properly sampled. This method is a way to use narrowband receiver techniques and parts to capture a broadband signal.

The channel sounder response is in the form of a waveform representative of the transmitted impulse, and which contains information about the channel. Block1503takes this impulse and converts it to a linear time invariant (LTI) model of the channel, h(t), by down-converting the signal to baseband. Simulated data is then convolved through the LTI model in block1504, out of which an error stream comes. The error stream represents what transmitted symbols would be received as good symbols and which would be error symbols. Block1505takes the error stream and calculates statistics stored in Observed_Histogram of block1506.

Block1507then generates a randomly initialized WCGA chromosome population according toFIG. 18, which is used to start the genetic algorithm (GA) of block1508. The GA performs standard crossover and mutation operations and evaluates each chromosome against the observed channel histogram in block1508by creating a channel histogram from the HMM and finding the sum of the differences between each point in the histogram as described inFIG. 19. The best fitness is the one closest to zero. After so many generations, the GA exits and transmits the final HMM model to the CSM via the TCP/IP socket layer of block521.

FIG. 16is a flow chart of the process implemented by the WCGA. The input1601is the channel information. The CWT's Broadband sounder in block1602, as described by block1502, is used to create a channel impulse response, from the sampled pulse. Like blocks1503and1504, block1603develops the mathematical representation, h(t), of the channel and block1604uses h(t) to generate an error stream. Block1605, like1505, calculates the channel statistics as described inFIG. 17, and the histogram from the channel statistics is stored in block1606as the Observed_Histogram. Block1607randomly initializes a population of HMM chromosomes according to the routine ofFIG. 18.

Block1608starts the genetic algorithm loop, which runs until a specified stopping criteria like a limited number of generations (the currently used method), or a certain minimum desired fitness value. A selection process is used in block1609, which can be any GA selection process such as tournament or roulette wheel, to choose parents for mating. The parents are then genetically manipulated through crossover, block1610, and mutation, block1611, to create a new set of offspring. The offspring are then evaluated in block1612according to the routine inFIG. 19. The worst members of the current generation are then replaced by more fit offspring in block1613, and the entire population is evaluated in block1614based on the fitness values developed in block1612. The best fit member of the population can then be used in1608to determine if the stopping criteria is met. If the stopping criteria is met, the GA exits and the best fit member of the population is the channel model transmitted to the CSM in block1615, which exits the WCGA routine.

FIG. 17is the flowchart for the calculate channel statistics routine of function block1605inFIG. 16. The input1701is the error steam from the observed channel and location buffer1701. A loop1702is initiated which cycles from i=0 through the entire length of the error stream. The number of symbols in the stream is counted1703, and loop1704is used to count the number of bits represented in the error stream1705by counting from j=0 to the total number of bits per symbol. If the current symbol contains an error as tested by1706, the number of symbol error and the current burst length are incremented by1707. The loop initiated in1708tests if any bit in each symbol is an error through decision block1709; all errors are added to the total number of bit errors1710. If the symbol does not contain any errors as determined in1706, the current symbol is compared to the previous symbol1711. If they are different, the burst histogram for the specified burst length is incremented by block1712. Block1713decides if the current burst length is the longest burst length observed; if so, the longest burst length observed, as stored in MaxBurstLength, is updated with the new maximum burst length in block1714. Block1715resets the burst length value to1for the next burst. This algorithm is used to develop statistics of the channel including the maximum burst length, the number of symbols and bits, the number of symbol and bit errors, the symbol error rate, the bit error rate, and the histogram of bursts in the channel as stored in block1716.

FIG. 18is a flowchart of the initialize population routine,1801, in function block1603inFIG. 16. First, a loop of i=0 to length N, the number of states in the HMM, is run from block1802. Block1803sets a counter to 0, and a second loop in1804runs from j=0 to the number of states, N, in order to generate the N×N matrix A of the HMM,2101. Each index j of row i is set to a random floating point number from 0 to 1 in block1805and block1806increments the counter by the random value generated in block1805. Upon completion of this routine, the entire row i in the A matrix has been filled with values. Since this is a probability matrix, all of the elements in each row must sum to 1; therefore, block1807divides all elements of row i by the sum of all the elements in that row. The final row vector now sums to 1.

A similar process occurs starting with block1808, which again sets the counter to 0. Loop1809this time runs from j to M, the number of outputs possible at all states (i.e., good symbols and bad symbols for an M of 2). Block1810sets the elements of row i of matrix B,2102, to a randomly generated number from 0 to 1, and, again, the counter is incremented in block1811. Once loop1809finishes, the vector rows of matrix B are then normalized in block1816to 1 by dividing all the elements by the sum of all the row elements.

Loop1802ends, and thePiinitialization vector of the HMM,2103, is then initialized. The counter is again set to 0 at block1812, and loop1813cycles for j to N to fill all elements of the N-lengthPivector. Each element is set to a random number from 0 to 1 at block1814, and the counter is incremented in block1815. After each element has been set, block1817normalizes the vector so that the elements sum to 1. Block1818simply converts all matrices of the HMM, A, B, andPi, into a single vector to represent the chromosome.FIG. 21shows the HMM in terms of matrices,2101,2102, and2103, and as a chromosome,2104. Block1819evaluates the chromosome's fitness according to the routine ofFIG. 19, and finally, block1820exits this routine.

FIG. 19is a flowchart of the evaluate member routine in function block1608inFIG. 16. The evaluate routine,1901, first deconstructs the chromosome back into its HMM form in block1902so the HMM can be used to generate the error stream properly in block1903. The channel statistics are then calculated in block1904according toFIG. 18. Loop1905loops from i to MaxBurstLength, which was calculated in block1904and corresponds to the longest length of successive burst errors for the error stream. For each burst length, the HMM currently being evaluated is compared to an observed vector, which is the actual channel. Fitness in block1906is calculated as the sum of the differences between the current channel and the observed channel. When loop1905ends, the fitness is returned at block1907, where a smaller fitness is desired.

FIG. 20is a flowchart of the deconstruct chromosome routine of1902. The routine takes in a chromosome at block2001and sets an index value to 0 in block2002. Loop2003cycles through the A matrix of the HMM,2101, going from i=0 to N, the number of HMM states, where an internal loop,2004, cycles from j=0 to N. Each element in matrix A, A[i][j], is placed into the chromosome vector at position index, which is then incremented, in block2005. When loop2003exits, the routine enters loop2006, which cycles through the B matrix,2102. Loop2006cycles from i=0 to N, and the internal loop,2007, cycles through j=0 to M, the number of output symbols for the HMM. Each element of matrix B, B[i][j], is then sequentially placed after the A matrix into the chromosome at position index, which is then incremented, in block2008. Loop2006exits, and the remaining conversion is to put thePivector,2103into the chromosome. SincePiis a vector, it only requires a single loop,2009, from i=0 to N, when each element,Pi[i], is placed into the chromosome after the B matrix at position index, which is again incremented, in block2010. After the A, B, andPimatrices are properly placed into the chromosome, the routine exits at block2011, which returns the chromosome.

Several chromosome structures were devices that allow the representation of wireless channels. An example of an HMM and the equivalent WCGA chromosome is shown inFIG. 21. Matrix A,2101, is the N×N state transition matrix of the HMM. Give a current state, there is a certain probability of moving to any other of the states or of staying in the same state. The columns set the current state and the row sets the state being transitioned to. For example, element A21is the probability of going from state 1 to state 2.

Matrix B,2102, is the N×M state output matrix of the HMM. At any given state, represented by the row, there is a probability of outputting a certain output symbol, represented by the column. The output values can represent a good or bad bit, or a good or bad symbol (where a symbol can represent many bits). For example, an output of zero represents a good symbol and an output of one represents a bad symbol, so given that the HMM is in state 1 at a given time, there is a probability of B11of outputting a 0, or good symbol, and a probability of B12of outputting a 1, or bad symbol.

The chromosome representation in2104shows how the HMM is converted into a chromosome for manipulation by the genetic algorithm. Each row and matrix is lined up back to back to create a single vector that can then be used in genetic operations such as crossover and mutation.

FIG. 22is a detailed block diagram of the WSGA53. It receives input from the CSM51via the TCP/IP socket layer531. Information about the WSGA is stored in a structure called WSGAInfo, and the member chromosomes of the genetic algorithm are stored in2201. Block2202initializes the member chromosomes as shown inFIG. 24. Block2203is the genetic algorithm used to determine the new radio system parameters as shown inFIG. 23, which links to a dynamic link library (DLL) to retrieve the mathematical fitness functions in block2204. The final solution from the genetic algorithm is transmitted to the radio via a radio-specific Application Programmable Interface (API) of block2205.

The WSGA chromosome structure is shown in the following table.

Chromosome Parameters0Power1fc2Bandwidth3Symbol Rate4Modulation5FEC6Payload/frame length7ARQ8Dynamic Range9Equalization10Encryption11Antenna Configuration12Voice13Noise Cancellation (limiting)14Interference Temperature15TDD16Proprietary 1......31Proprietary
This table is viewed as a vector in the algorithm and operated upon as a chromosome through genetic algorithm crossover and mutation procedures. The values of these table parameters determine the fitness of the chromosome and the behavior of the radio.

FIG. 23is a flowchart showing the operation of the WSGA. The input2301is a packet from the CSM51which is temporarily stored at2302. The population of chromosomes is initialized in2303according to the routine ofFIG. 24. Decision block2304controls the genetic algorithm loop and exits the loop upon a stopping criteria, which could be a certain number of generations or after a decrease in performance gain per generation is detected (that is, the fitness of the current generation did not differ significantly from the previous generation). While the loop is running, block2305selects parent chromosomes that will be used to generate offspring chromosomes to replace the population the next generation. Blocks2306and2307perform standard genetic algorithm techniques of crossover and mutation, respectively. Block2308evaluates the fitness values for each chromosome, both parent and offspring. Block2309determines which members of the population to replace using a relative fitness evaluation method ofFIG. 26. Once the genetic algorithm loop has exited, block2310transmits the system parameters as defined in the best fit chromosome of the final generation to the radio via an API. Block2311also transmits the best fit chromosome along with the simulated fitness values to the CSM so the CSM can compare the simulated fitness values to the real fitness values read from the radio after the new radio settings have been set.

FIG. 24is the flowchart of the initialize population routine of function block2303inFIG. 23. This routine first fills the initial population of the WSGA with children received from the CSM and then randomly generates any more children required to fill the population. Block2401initializes the routine. Loop2402cycles through all child chromosomes received from the CSM, where block2403inputs the child into the population and block2404evaluates the chromosomes fitness values. Loop2405then cycles through the remaining populated indices where block2406randomly generates chromosomes to fill the population and block2407evaluates the fitness of the new chromosomes. Once the population is filled, the routine exits2408.

FIG. 25is a flowchart of the evaluate member routine of function block2308. Starting at block2501, the chromosome is translated to absolute radio parameters (power in terms of dBm, frequency in Hz, etc.) stored in structure data through the radio-specific API at block2502. Loop2503cycles through all of the current fitness functions used to evaluate the members using an index variable i. During the loop, each fitness function is evaluated by calling the function out of the “WSGAFitFunc.dll” dynamic link library (DLL) in block2504. The DLL is useful for dynamic linking because the radio system may be updated in real-time with new or improved fitness evaluation functions without altering the rest of the system. Block2505uses the function from the DLL to calculate the fitness for each fitness function, called an objective by passing the data structure to the function as well as a meters structure, which is updated inside the DLL function to contain simulated meters of the radio's performance. When loop2503has finished evaluating all of the fitness functions, the routine exits2506.

FIG. 26is a flowchart of the replace population member routine2601based on a relative tournament selection scheme. Loop2602cycles through by incrementing index i from 0 to the total population size. Each cycle, 2 members, designated as member[n] and member[k], are chosen from the population of parents and offspring at block2603. Loop2604then uses index j to cycle through all of the fitness functions. Decision blocks2605,2606and2607decide which of the two members won by comparing the fitness values associated with each objective. If the objective of member[n] is greater than the objective of member[k] in block2605, then member[n] wins and block2608increments the fitness value by adding the amount of weight associated with the current fitness function being compared to the member's fitness. Else, if the objective of member[k] is larger than the objective of member[n] in block2606, than member[k] wins and block2609increments member[k]'s fitness value according the amount of weight on the function. If the two members' objectives are equal, a uniformly random number is generated between 0 and 1, and if it is less than 0.5, member[n] wins the tournament; otherwise, member[k] wins and block2610updates the fitness value of the winning member.

After all objectives have been compared and the fitness values properly incremented and loop2604has ended, members [n] and [k]'s fitness is compared in block2611, and if member[n]'s fitness is larger than member[k]'s fitness, then member[k] is removed from the population and member[n] survives in the population to be a part of the next generation in block2612; otherwise, member[n] is killed and member[k] survives to the next generation in block2613. After the entire population of parents and offspring have been compared and the next population chosen, the routine exits2614. This relative tournament selection mechanism is a way to compare population members and choose the best fit members for survival to the next generation when there are multiple objectives to consider. The weights allow the system to adjust its priorities when it thinks one fitness function is more important than another (e.g., minimizing the bit error rate may be more important than maximizing the data rate, so the weights can help determine how much each matters).

The CSM evolutionary algorithm consists of a learning classifier function that classifies the observed channel model received from the WCGA or broadband channel sounder and a meta-genetic algorithm that determines the appropriate fitness function, chromosome structure, and templates using the crossover operator based on knowledge from its short and long term memories as well as the creative new solutions generated from its mutation functions.

The genetic algorithm (GA) approach to adapting a wireless radio according to the present invention provides many benefits. First, it is a chaotic search with controllable boundaries that allow it to seek out and discover unique solutions efficiently. In unknown channels, chaotic behavior could produce a solution that is absolutely correct but may be counter-intuitive. By being able to control the search space by limiting the number of generations, crossover rates, mutation rates, fitness evaluations, etc., the cognitive system can ensure legal and regulatory compliance as well as efficient searches.

Another major benefit of the GA approach is the versatility of the cognitive process to any radio. While a software radio is an ideal host system for a cognitive processor, any legacy radio with the smallest amount of adaptability can benefit from our cognitive processes. The cognitive system defines the radio chromosome, where each gene represents a radio parameter such as transmit power, frequency, modulation, etc. The adaptation process of the WSGA is performed on the chromosomes to develop new values for each gene, which is then used to adapt the radio settings. If a radio cannot adjust a particular parameter, then the adaptation process will ignore the gene representing the parameter. Also, if there are certain parameters unique to a particular adaptable radio, a few genes can be left unused so as to be used for such proprietary purposes. See, again the Chromosome Parameters table above.

Because each radio will have a unique method of adapting the radio parameters and each parameter will mean something different, a small hardware interface is required to connect the WSGA to the radio. The hardware interface will take the chromosome from the WSGA and use the gene values to properly update the radio. The hardware interface is a small piece of software required for each radio while the cognitive processing engine remains system-independent. While the independence of the WSGA and the cognitive processor to the radio allows any adaptable radio to become a cognitive radio, it should be clear that the more adaptable a radio is, the more powerful the cognition becomes.

Each of the three main algorithms (CSM, WSGA and WCGA) can be co-located or distributed. “Co-located” means that the three algorithms exist in the same radio with shared memory and processing. “Distributed” means that one or more of the algorithms exists on another radio with separate memory and processing. The knowledge base developed in long term memory may also be distributed, allowing for physically distributed cognitive consciousness that appear logically the same to the CSM.

For example, a base station unit (BSU) may have both the WCGA and CSM in its system to model the radio environment and maintain the long term memory that the subscriber units can access for their independent WSGA algorithms running locally. This scenario allows for a common memory bank and associated realization of the radio environment, but each system can adapt independently. If a radio adapts to a set of parameters that are more successful in the radio environment, it can then communicate its successful adaptation back to the BSU for better future adaptation by all radios. Another scenario could be that the radio has its own sensing mechanism, but sends the channel model to another radio for CSM and WSGA processing. The output of the WSGA could then be sent back to the original radio for adaptation. In both examples, the long term memory could be mapped to a local device or set of devices. This distributed knowledge base concept allows the power of the GA approach to be realized, because as the network becomes more complex, the knowledge base has a mechanism to scale with it.

The method of exchanging data between the algorithms must allow for both co-located and distributed systems. We therefore chose to use a socket-driven TCP/IP protocol stack as illustrated inFIG. 27, with the WCGA52, CSM51and WSGA53algorithms connected as shown. The interface between the systems is all packet based and is sent using TCP to a specific socket in the system. The basic TCP datagram is illustrated inFIG. 28. The socket-based communications is convenient because it has a common port to connect to but is also related to the IP address of the radio system. For co-located algorithms, the IP address can be simply set to the system's ow!n IP address or the internal loopback address (usually defined as 127.0.0.1). To communicate the information between distributed systems, a change in the IP address is all that is required.

When the WCGA has a channel model for the CSM, it opens a TCP socket connected to port WCGA_CSM_TCP_PORT. A packet of information is then sent from the WCGA to the CSM and the connection closed. The sequence of events for passing the data between the WCGA and the CSM is shown inFIG. 29. The WCGA-CSM packet for passing channel statistics and a burst error histogram is shown inFIG. 30.

The CSM to WSGA communications is very similar to the WCGA to CSM communications; however, now the CSM opens the communications when the packet is ready. The CSM opens a TCP socket in the WSGA on part WSGA_TCP_PORT. The packet is sent, and the connection is closed. The sequence of events for passing the data between the CSM and the WSGA is shown inFIG. 31. The CSM-WSGA packet for passing the WSGA control information is shown inFIG. 32.

The WSGA then passes information back to the CSM regarding the new system chromosome developed. Again, the communications are very similar to the previous method, only the WSGA opens a TCP socket on the CSM on port WSGA_CSM_TCP_Port. The packet is sent, and the connection is closed. The sequence of events for passing the data between the WSGA and the CSM is shown inFIG. 33. The WSGA-CSM packet for passing the WSGA final information is shown inFIG. 34.