CN101262701A - A dynamic channel allocation method based on generic algorithm - Google Patents

Abstract

The invention uses genetic algorithms to realize dynamic channel allocation (DMA). By contrast, a nonlinear method is more suitable for nonlinear characteristics of the reality and for parallel arithmetic, can be flexibly transferred to fit various wireless channel allocation technologies; the invention is additionally characterized that channel performance is collectively estimated and channel resources are equally distributed so as to comparatively improve the comprehensive utilization ratio of the channel resource. The invention adopts carrier frequency, time slot, spread spectrum codes and the angle of wave beam as genomes to realize chromosome coding; the operating procedure is that a sliding window is used for filtering a species group to form a vector X which equals (CF3, C, F2, CF1, CF0, TS2, TS1, TS0, SF3 ,SF2, SF1, SF0, BS2, BS1, BS0), and then the genetic algorithms, such as hybridization, variation, etc., are selected to realize the dynamic allocation and optimization of the channel.

Description

A kind of dynamic channel assignment method based on genetic algorithm

Technical field

The present invention relates to wireless communication field, in particularly a kind of radio communication based on the dynamic allocation method of the channel of genetic algorithm.

Background technology

The distribution method of channel is that wireless network capacitance improves major measure in the wireless communication networks.The distribution of channel is decided by the distribution of uniting of frequency domain carrier frequency, time domain time slot, sign indicating number territory spreading code and spatial domain beam angle, under the prerequisite that satisfies the communication quality requirement, realizes the maximization of network capacity simultaneously.

In order to enlarge the capacity of wireless network, all be to adopt dynamic channel assignment method usually.The characteristics of dynamic channel allocation are that the sub-district does not have fixing channel allocation.When call request, system takes channel of strategy distribution in certain from the channel combination, as long as satisfy the least interference tolerance limit, and any one channel that the link in the sub-district just can obtain.The characteristics of this method of salary distribution are to distribute flexibly, the demand of energy random adaptation business.But because the blindness of allocation strategy, be channel utilization rate lower, especially traffic carrying capacity is for a long time.The dynamic channel allocation that adopts mainly is the distance classification of wireless terminal and base station now, channel allocation gives distance nearer relatively link request in the same then code channel, allow different code channels to use the different multiplexing factors simultaneously, also can be in conjunction with call request priority, practical business situation such as service distribution is carried out dynamics of channels and is distributed up and down.

But the characteristics of these dynamic channel assignment methods are based on professional linear method, fail abundance to consider that real communication environment may be non-linear environment such as building area, waters, hills; Communication process is influenced by multipath transmission, Rayleigh decay, Doppler effect etc. also, and what be difficult to dopes location parameter; Former some link request that also may allow of best performance and time priority can't be assigned to channel because of missing the time; And the channel resource that big multilink obtains not is the most reasonable, as the channel capacity surplus, stops using situations such as strong jamming channel, causes some channel resource waste, may have influence on other links and lose line, even be refused.Along with the raising of China's wireless client and traffic carrying capacity, this waste that causes because of channel allocation is improper will be more obvious.

Summary of the invention

Just because of the randomness of calling terminal position, communication environment non-linear, if adopt linear dynamic channel assignment method, utilization rate of channel resources is difficult to ensure.In order to solve the above problems, improve channel allocation efficient, solve the limitation of conventional method, enlarge the capacity of wireless network, satisfy the needs of reality, the present invention proposes a kind of nonlinear method of dynamic channel allocation, the theory origin of this method in the Michigan of U.S. university the genetic algorithm that proposes of J.H.Holland.

Genetic algorithm is a kind of nonlinear intelligent algorithm, is the evolution of the selection that utilizes kind of groups, hybridization, variation, stronger population or the individuality of screening adaptability.Can constantly adjust gene and algebraically according to the variation of environment, conform dynamically.And the optimization of population can avoid local optimum, and then increases operation rate on the whole.

Genetic algorithm is a principle of utilizing Darwin to select the superior and eliminate the inferior, finds the individuality that conforms most by genetic evolution.Form by several steps once specifically:

The first step according to the feature of individuality, makes up some set of possible individuality dyeing (Chromosome) body, i.e. chromosome coding (Encode) processes;

In second step, go out N as population (Population) by certain Rules Filtering;

The 3rd step, select two individual chromosome as father's individuality (Parent) by certain rule of probability again, promptly select;

In the 4th step, two father's individual chromosome are selected a gene in the chromosome at random by rule.According to certain hybridization probability P _c, exchange selected gene and all gene orders afterwards, i.e. hybridization;

The 5th step, in two sub-individual chromosome, select a gene, make a variation according to certain probability P m;

The 6th step repeated the 3rd and goes on foot the 5th step, and it is individual to produce 2M new son, and the scale of population expands N+2M to, selects N individual new population by certain rule;

The 7th step, ask the whole adaptive value of population and judge whether to satisfy threshold values, or reach the evolutionary generation of defined, if satisfy, finish to calculate, will not restart from the 3rd step if do not satisfy, continue the threshold values of circulation up to regulation.

Introduce the specific implementation of genetic algorithm in dynamic channel allocation below.

Have carrier frequency territory carrier frequency, time domain time slot, sign indicating number territory spreading code and spatial domain beam angle in the radio channel allocation.Carrier frequency distribution is the selection to several carrier frequency; The distribution of time slot is the selection of time slot in the subframe; The distribution of code channel is to selecting with the time slot spreading code; The distribution of beam angle is the selection to beam sector in intelligence or the adaptive antenna.As shown in Figure 1, can design wireless planning designing requirement bandwidth is 15M, and the carrier frequency of sub-district (LF) composite factor is 1, and business time-slot (TS) is 6, and the frequency hopping factor (SF) is 1,2,4,8 or 16, and the beam angle number of degrees are 8.Chromosome is the coding that is made of gene (Gene).Chromosome coding according to condition individuality (Individual) is:

X=(X _LF, X _TS, X _SF, X _BF)=(C _F3, C _F2, C _F1, C _F0, T _S2, T _S1, T _S0, S _F3, S _F2, S _F1, S _F0, B _F2, B _F1, B _F0); C wherein _Fi, T _Si, S _Fi, B _Fi∈ I ^T(I is 0,1 vector of forming).X _LFIt is the carrier frequency numbering.The bandwidth of each frequency is pressed 1.6M and is calculated, and 9 frequencies are just arranged, and so just needs bit to represent:, (C _F3, C _F2, C _F1, C _F0), highest order C _F3This position is just selected in expression home cell or nonlocal sub-district when needs are borrowed frequently.X _LFMay make up as Fig. 3.X _TSBe time-gap number, binary representation: (T _S2, T _S1, T _S0), highest order T _S2Represent up link or down link, as Fig. 4.X _SFBe frequency hopping factor figure place numbering, binary representation: (S _F3, S _F2, S _F1, S _F0), as Fig. 5, X _BFBe the beam angle numbering, binary representation: (B _F2, B _F1B _F0), as Fig. 6.

Individual choice (Selection) supposes that current home cell has idle channel, and grade of service requirement is: the high-speed uploading data.As requested, our initial condition is 9 carrier waves of home cell, 4 of ascending time slots, and 2 of descending time slots, the frequency hopping factor is 8.In the selection course of initial population,, can utilize the window back-and-forth method in order to reduce the scope.Promptly, design a window, only the vector that is worth test is comprised to come in as far as possible according to business need.Shown in Fig. 3,4,5,6.Selected population is the amount that window is drawn a circle to approve.Optimize in the selection course of population, many middle algorithms are arranged, we adopt the optimum individual preservation method, promptly eliminate the chromosome dyad of adaptive value minimum with adaptive value the best part chromosome.

Individual hybridization (Crossover) is composed to a reproductive probability P by the size of its adaptive value to each individuality in the population _i(behind 0＜i＜N+1), select two individualities as father's individuality (parent) by the probability size.The benefit of doing like this is the optimum gene of selecting of maximum possible.At random crosspoint of selection (Crossover Point) in two fathers base individual chromosome coding is by the crossover probability P that configures _c, determine whether and to intersect.Will produce two sons individual (Offspring) if intersect.The mode of intersecting selects single-point to intersect, and can guarantee that like this some outstanding genes are not eliminated

Individual variation (Mutation) is selected a gene, at random by the variation probability P that designs in the chromosome coding of two son individualities _m, determine whether to make a variation, promptly 1 becomes 0 or 0 change 1.Judge that the individual adaptive value of son reaches the requirement of regulation.If no, just continue M hybridization and variation, the scale of population also can expand N+2M to.Carry out then and optimize the population selection course.

Adaptive value function (Fitness Function), so the adaptive value function is not only relevant with interference in this paper, and also relevant with blocking rate.

Adapt to function: F (X)=μ ₁SINR+ μ ₂P _b(X) μ wherein ₁, μ ₂Be penalty factor, and μ ₁+ μ ₂=1; SINR is a signal to noise ratio: $\mathrm{SINR}=\frac{I_{\mathrm{signal}}}{(1-\mathrm{\β})I_{\mathrm{intracell}}+I_{\mathrm{intercell}}+N_{\mathrm{noise}}},$ I wherein _SignalThe power of acknowledge(ment) signal, I _IntracellLocal area disturbs, I _IntercellDisturb the adjacent area, N _NoiseBe thermal noise power, β is the evaluation factor of joint-detection.Second is the blocking rate algorithm that is proposed by people such as Cimini: P _b=1-C (ρ)/ρ, C (ρ) is a saturated density, ρ is a traffic carrying capacity.During interference analysis was analyzed, what consider the modern communications employing was associated detection technique, had reduced the multiple access in the sub-district greatly and had disturbed, so the interference that exists mainly is the interference of minizone.The minizone time slot is divided main other base stations of interference when consistent to the interference of travelling carriage, and time slot is divided when inconsistent, and disturbing mainly is the interference of base station to the base station, close together with the influence of mobile terminal to the mobile terminal.Correlation model can be with reference to relevant wireless communication capacity simulation model.Certainly, the selection of concrete adaptive value strategy can be fixed according to the actual needs of network, and along with the development of related wireless communication technology such as radio frequency, can update.

Description of drawings

Fig. 1 multi-carrier district bunch schematic diagram

Fig. 2 implementing procedure figure

The carrier frequency window schematic diagram that Fig. 3 frequency domain distributes

Fig. 4 time domain distributed time slot window schematic diagram

The spread spectrum window schematic diagram that Fig. 5 sign indicating number territory is distributed

The beam angle window schematic diagram that Fig. 6 spatial domain is distributed

Embodiment

Below in conjunction with accompanying drawing invention is described further.

As accompanying drawing 1, at the communication network of the TD-SCDMA of multicarrier cell cluster.Seven sub-districts of only drawing for convenience of explanation, carrier number is N1=9, and the business time-slot number is N2=6, and a sign indicating number territory spread spectrum is counted N3=16, beam angle number of degrees N4=8.Implementing procedure such as accompanying drawing 2, step is as follows:

Step 1: earlier 9 carrier frequency in the cell cluster are numbered, min (2 ^m＞=9)=16, so need 4 binary representations.All carrier frequency can be formed one 16 * 4 carrier frequency channel matrix X thus _LF=(C _F3, C _F2, C _F1, C _F0).Can draw 8 * 3 time slot channel matrix X successively _TS=(T _S2, T _S1, T _S0), 16 * 4 spreading channel matrix X _SF=(S _F3, S _F2, S _F1, S _F0), 8 * 3 beam angle channel matrix X _BF=(B _F2, B _F1, B _F0);

${\mathrm{<figure-callout\; id="0"\; label="C\; F"\; filenames="A20081003644200111.png,A20081003644200113.png"\; state="\{\{state\}\}">C</figure-callout>}}_F=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ ${\mathrm{<figure-callout\; id="1"\; label="C\; F"\; filenames="A20081003644200091.png,A20081003644200111.png"\; state="\{\{state\}\}">C</figure-callout>}}_F=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ $C_{F2}=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ $C_{F3}=\left(\begin{array}{c}0\\ 0\\ 0\\ 0\\ 1\\ .\\ .\\ .\\ 1\end{array}\right);$ ${\mathrm{<figure-callout\; id="0"\; label="T\; S"\; filenames="A20081003644200111.png,A20081003644200113.png"\; state="\{\{state\}\}">T</figure-callout>}}_S=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ ${\mathrm{<figure-callout\; id="1"\; label="T\; S"\; filenames="A20081003644200091.png,A20081003644200111.png"\; state="\{\{state\}\}">T</figure-callout>}}_S=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ $T_{S2}=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\\ 0\\ .\\ .\\ .\\ 1\end{array}\right);$

${\mathrm{<figure-callout\; id="0"\; label="S\; F"\; filenames="A20081003644200111.png,A20081003644200113.png"\; state="\{\{state\}\}">S</figure-callout>}}_F=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ ${\mathrm{<figure-callout\; id="1"\; label="S\; F"\; filenames="A20081003644200091.png,A20081003644200111.png"\; state="\{\{state\}\}">S</figure-callout>}}_F=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ $S_{F2}=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ $S_{F3}=\left(\begin{array}{c}0\\ 0\\ 0\\ 0\\ 1\\ .\\ .\\ .\\ 1\end{array}\right);$ ${\mathrm{<figure-callout\; id="0"\; label="B\; F"\; filenames="A20081003644200111.png,A20081003644200113.png"\; state="\{\{state\}\}">B</figure-callout>}}_F=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ ${\mathrm{<figure-callout\; id="1"\; label="B\; F"\; filenames="A20081003644200091.png,A20081003644200111.png"\; state="\{\{state\}\}">B</figure-callout>}}_F=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ .\\ .\\ .\\ 1\end{array}\right),$ $B_{F2}=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\\ 0\\ .\\ .\\ .\\ 1\end{array}\right);$

Step 2: the method for utilizing the smooth window selection is selected N=6 channel vector in carrier frequency, time slot, spread spectrum, beam angle channel matrix; Vector format is X=(C _F3, C _F2, C _F1, C _F0, T _S2, T _S1, T _S0, S _F3, S _F2, S _F1, S _F0, B _F2, B _F1, B _F0), as accompanying drawing 3, Fig. 4, Fig. 5, Fig. 6; Wherein:

N＝min(N ₁、N ₂、N ₃、N ₄)

Equal the size of window, the origin coordinates of window is the first address of channel group resultant vector.Determine N and original position, also just determined window.If sufficient operational capability is arranged, I can adopt young waiter in a wineshop or an inn all just to estimate to reduce many through disturbing; Adopt the little NLOS error of weighted least-squares method; Adopting the power features analysis to reduce multiple access disturbs.

Step 3:, select two to select two vectors then at random at the phase scale according to the adaptability of channel numbering; And do not select optimum two channels, is to avoid locally optimal solution;

Step 4: in channel vector, select an element, and by carry out probability P c exchange this element and after vector element, but keeping intact before.The value of Pc is 0.4～0.9;

Step 5: in two new channel vectors, element of selection at random again, and by carrying out probability P m this element is negated.The value of Pm is 0.1～0.5.；

Step 6: recirculation step M-1 time, population scale expands 2M+N=10 to; Select the channel vector make new advances according to gambling dish method.Wherein, M=EVEN (R*Q), R are current just at linking number R ₁With request linking number R ₂Summation.Q reserves the factor, and Q＞=1.

Step 7: judge whether the overall performance of this N=6 channel vector meets or exceeds the optimal solution of expection.If, begin to distribute, finish computing; If not then continuing;

Step 8: judge whether to surpass default cycle-index W=100 (can adjust) according to the processor calculating performance.If do not surpass, replace old channel vector with new channel vector, and return step 4; If surpass, select current best channel vector group, keep or begin distributing, and finish computing.

Conclusion (Conclusion), genetic algorithm is utilized chromosome coding, and channel resources such as carrier frequency, time slot, spreading code, beam angle are coordinated configuration, and realization RNC that can maximum possible is at globally optimal solution.Satisfying under the prerequisite of quality of service, improving business to greatest extent, improving utilization rate of channel resources.Solved among the current DMA because pursue individual optimal solution and reduced the overall utilization rate of channel resource simply.Utilize the window back-and-forth method can dwindle query context simultaneously, improve the convergence rate of genetic algorithm.As table 1, search area is dwindled more than 80%, improved computational speed greatly.If select concurrent operation again, speed can be faster.So not only can use among the DMA at a slow speed, and can use among the DMA fast.

Table 1 window is selected

	No window is selected	There is window to select
			Population scale	9×6×16×8＝6912	6×6×6×6＝1296

The triggering that DMA adjusts is to move the interference that causes, sub-district total capacity load variations automatically or according to terminal request according to the client, realizes redistribute resources and resource consolidation.RRM (RRM) algoritic module is adopted in reallocation.Triggering is adjusted program with DMA.The adaptability factor of judgment comprises the computational burden of portable terminal and power down rate etc., also can be with reference to the QoS business need.

By simulation analysis, adopt the DMA of genetic algorithm, during 3 times/S of call volume, blocking rate obviously reduces.

For the method that rope of the present invention proposes, those skilled in the art are readily appreciated that and use indirectly the method.So other nonlinear methods that change out based on this kind method are all in the scope of protection of present invention.

Claims (3)

1, a kind of dynamic channel assignment method based on genetic algorithm is characterized in that may further comprise the steps:

The carrier frequency number is N in step 1, cell cluster of acquisition wireless network _C, to the N in the cell cluster _CIndividual carrier frequency is numbered, and uses Log ₂N ₁Individual binary representation, wherein N ₁=min (2 ^m＞=N _C), m is the positive integer that makes that described formula is set up, all carrier frequency are formed a N ₁* Log ₂N ₁Carrier frequency channel matrix X _LF, same, for time slot, spreading code and beam angle, can draw N successively ₂* Log ₂N ₂Time slot channel matrix X _TS, N ₃* Log ₂N ₃Spreading code channel matrix X _SF, N ₄* Log ₂N ₄Beam angle channel matrix X _BF

Step 2, utilize method that window selects in carrier frequency, time slot, spreading code, beam angle channel matrix, select N channel vector (N＜N ₁, N ₂, N ₃, N ₄), vector format is X=(C _F3, C _F2, C _F1, C _F0, T _S2, T _S1, T _S0, S _F3, S _F2, S _F1, S _F0, B _F2, B _F1, B _F0);

Step 3, according to the adaptability of channel numbering, select two to select two vectors then at random at the phase scale;

Step 4, in channel vector, select an element, and by carrying out probability P c, exchange this element and after vector element, but keeping intact before;

Step 5, in two new channel vectors, element of selection at random, and, this element being negated by carrying out probability P m;

Step 6, M-1 step 3 of circulation are to step 5, and population scale expands 2M+N to, here,

The value of M be in the current area bunch the linking number of terminal and network add behind the request linking number with certain preset value and, N is the new channel vector number of selecting according to gambling dish method;

Step 7, judge whether the overall performance of this N channel vector meets or exceeds the optimal solution of expection, if not then continuing execution in step eight, if, the distribution of beginning channel and finish the computing of whole channel allocation;

Step 8, judge whether to surpass default cycle-index, if do not surpass, replace old channel vector, and return step 4,, select current best channel vector group, keep or begin allocated channel and finish computing if surpass with new channel vector.

2, a kind of dynamic channel assignment method based on genetic algorithm according to claim 1 is characterized in that, in the described step 4, the span of carrying out probability P c is 0.4～0.9.

3, a kind of dynamic channel assignment method based on genetic algorithm according to claim 1 is characterized in that, in the described step 5, the value of carrying out probability P m in scope 0.1～0.5.

Images