CN103415080A - Low-complexity multi-user scheduling method based on replacement - Google Patents

Abstract

The present invention proposes a low-complexity multi-user scheduling method based on replacement. The method first determines a temporary scheduling user set, and then selects users from the candidate user set composed of remaining users to be scheduled to replace the users in the temporary scheduling user set; In each round of replacement selection, select the user with the largest channel quality factor in the candidate user set and the user with the smallest replacement cost factor in the temporary scheduling user set to perform replacement. If the minimum replacement cost factor of the new temporary scheduling user set obtained after replacement is greater than If the minimum replacement cost factor of the temporary scheduling user set before the replacement is considered, the replacement is considered successful, and the next replacement selection is made. The system capacity loss of the method of the invention is small, and the calculation complexity is reduced.

Description

A low-complexity multi-user scheduling method based on permutation

technical field

The invention belongs to the technical field of wireless communication, and in particular relates to a permutation-based low-complexity multi-user scheduling method.

Background technique

The research results of Telatar and Foschini of Bell Labs show that the channel capacity of the wireless communication system can be doubled by using multiple transmitting antennas and receiving antennas in the wireless rich reflection fading environment. This system using multiple transmitting and receiving antennas Often referred to as a multiple-input multiple-output MIMO system, its channel capacity is approximately proportional to the minimum number of transceiver antennas. Studies have shown that MIMO wireless transmission technology can not only double the system capacity without adding additional spectrum bandwidth, but also increase the reliability and coverage of the link.

With the deepening of multi-antenna technology research and the development of multi-user information theory, MIMO technology has been extended from the traditional single-user MIMO (SU-MIMO) system to multi-user MIMO (MU-MIMO) system. The MU-MIMO system means that multiple users send signals to the base station at the same time in the same frequency band, and then the base station distinguishes user data through appropriate methods. Multi-user diversity enables the MU-MIMO system to further improve system performance. Since the number of users that the base station can serve at the same time is limited by the number of transmitting and receiving antennas, it is of great significance to study a reasonable user scheduling technology and select a subset of users from many users for data transmission.

Traditional user scheduling techniques only schedule one user in each transmission slot, such as opportunistic scheduling with the goal of maximizing capacity, round-robin scheduling with the goal of fairness, proportional fair scheduling with a compromise between capacity and fairness, etc. ; In the MU-MIMO system, the base station can exchange data information with multiple users at the same time, and it is usually not optimal to schedule only a single user in each time slot. Therefore, in order to make better use of multi-user diversity gain and provide users with more Good fairness, the scheduling algorithm should simultaneously select multiple non-interfering users for communication in each time slot; in order to eliminate the interference between users, appropriate precoding techniques can be used at the base station, such as based on block diagonalization (Block Diagonal, BD) or Signal to Leakage Noise Ratio (Signal to Leakage Noise Ratio, SLNR) precoding technology.

Using the traversal method, selecting a subset of users to communicate in all the users to be scheduled can maximize the system capacity; however, as the number of users to be scheduled increases, the complexity of this scheduling method increases sharply, which is not suitable for practical systems. . For example, when the number of users to be scheduled is 10 and 15 respectively, and the maximum number of users that the base station can serve at the same time is 4, if it is stipulated that 4 users are selected for each scheduling, the number of traversals to be traversed is 210 and 1365 respectively.

Contents of the invention

The technical problem to be solved by the present invention is to overcome the deficiencies of the prior art, and propose a replacement-based low-complexity multi-user scheduling method. The method utilizes the multi-user diversity gain of the MU-MIMO system, and uses a permutation method to select a subset of users in all user sets to be scheduled for communication; The computational complexity is reduced with little loss of system capacity.

In order to solve the problems of the technologies described above, the technical scheme adopted in the present invention is as follows:

A low-complexity multi-user scheduling method based on permutation, the specific steps are as follows:

Step A, set the number of all users to be scheduled as K, the maximum number of users that the base station can serve at the same time is M, M<K, calculate the channel quality factors of K users to be scheduled, and select M with the largest channel quality factor of the users to be scheduled users to be scheduled as the initial value of the temporary scheduling user set U; the remaining users to be scheduled form the candidate user set

Step B, calculate the replacement cost factor of each user in the temporary scheduling user set U, record the minimum replacement cost factor as γ _min , and mark the user with the minimum replacement cost factor as u _min ;

置换临时调度用户集U中置换代价因子最小的用户u_min；Step C, take out the candidate user set The user with the largest channel quality factor

Replace the user u _min with the smallest replacement cost factor in the temporary scheduling user set U;

Calculate the replacement cost factor of each user in the temporary scheduling user set U after the update, record the minimum replacement cost factor as γ′ _min , and mark the user corresponding to the minimum replacement cost factor as u′ _min ;

U←{U∪{u_min}}；其中，符号“←”表示将其右边变量的值赋予其左边的变量，

表示除去集合U中的元素U∪{u_min}表示将元素u_min加入集合U；Step D, if γ _min <γ′ _min , the replacement is successful, set γ _min ←γ′ _min , u _min ←u′ _min ; otherwise, restore the user subset:

U←{U∪{u _min }}; among them, the symbol "←" means to assign the value of the variable on the right to the variable on the left,

Represents the removal of elements in the set U U∪{u _min } means adding the element u _min to the set U;

Step E, check the set of alternative users is empty set, if alternative user set is an empty set, then end the replacement, and determine the temporary scheduling user set U as the final scheduling user set; otherwise, return to step C to continue execution.

The beneficial effects of the present invention are: the present invention proposes a replacement-based low-complexity multi-user scheduling method, the method first determines a temporary scheduling user set, and then selects user replacement from the candidate user set composed of remaining users to be scheduled Users in the temporary scheduling user set; each round of replacement selection, select the user with the largest channel quality factor in the candidate user set and the user with the smallest replacement cost factor in the temporary scheduling user set for replacement, if the new temporary scheduling user obtained after replacement If the minimum replacement cost factor of the set is greater than the minimum replacement cost factor of the temporary scheduling user set before replacement, it is considered that the replacement is successful, and the next replacement selection is performed. The system capacity loss of the method of the invention is small, and the calculation complexity is reduced.

Description of drawings

FIG. 1 is a flowchart of a permutation-based low-complexity multi-user scheduling method in the present invention.

FIG. 2 is a block diagram of a multi-user multiple-input multiple-output MU-MIMO system.

Fig. 3 is a comparison chart of system capacity curves using the scheduling method of the present invention and the existing scheduling method.

Detailed ways

其中，下标R表示接收端，j表示用户序号，满足

M<K，第j个用户每接收天线上加性复高斯白噪声方差为

信号功率归一化为1，第j个用户到基站天线之间的信道矩阵为H_j，第j个用户的归一化预编码向量为w_j。A permutation-based low-complexity multi-user scheduling method proposed by the present invention will be described in detail below in conjunction with the accompanying drawings and specific examples: In a multi-user multiple-input multiple-output (MU-MIMO) system as shown in Figure 2, the base station The terminal first uses the user channel state information through the multi-user scheduler to select a group of users in the user queue; then precodes the data to be sent to this group of users; finally transmits the data to the user via the downlink channel through the transmitting antenna end. Assume that the number of transmitting antennas at the base station is n _T , the subscript T represents the transmitting end, the maximum number of users that can be served at the same time is M, the number of all users to be scheduled in the system is K, and the number of receiving antennas of the jth user is

Among them, the subscript R represents the receiving end, and j represents the user serial number, which satisfies

M<K, the variance of the additive complex white Gaussian noise on each receiving antenna of the jth user is

The signal power is normalized to 1, the channel matrix between the jth user and the base station antenna is H _j , and the normalized precoding vector of the jth user is w _j .

Fig. 1 is a flow chart of a specific embodiment of the low-complexity multi-user scheduling method based on replacement in the present invention, and its specific steps are:

1) Calculate the channel quality factor of these K users to be scheduled. In this example, the Frobenius norm of the channel is taken as the channel quality factor, and the M users with the largest channel Frobenius norm are selected as the initial temporary scheduling user set, denoted as Set U, the remaining users to be scheduled are sorted according to the Frobenius norm of the user channel from large to small, and the ordered set of candidate users is recorded as a set

2) In this example, the base station adopts the criterion of maximizing the signal-to-leakage-to-noise ratio (SLNR) to design the precoding vector w _j , and the specific calculation formula is:

${\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Proportional;</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; eigenvector</span>}<span\; class="notranslate">\; (</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; no</span>}}_{{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; I</span>}}_{{\mathrm{<span\; class="notranslate">\; no</span>}}_{\mathrm{<span\; class="notranslate">\; T</span>}}}<span\; class="notranslate">\; +</span>{\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; h</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; *</span>}{\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; h</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{<span\; class="notranslate">\; *</span>}{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

的最大特征值对应的特征向量。其中，

为第j个用户的接收天线数，

为第j个用户每接收天线上加性复高斯白噪声的方差，n_T为基站端发射天线数，

为n_T×n_T的单位矩阵，H_j为第j个用户的信道矩阵，(·)^-1表示矩阵的逆，(·)^T表示矩阵的转置，(·)^*表示矩阵的共轭转置，

为扩展的信道矩阵，由除H_j之外的各用户信道矩阵组成，即：Its meaning is: w _j is a matrix

The eigenvector corresponding to the largest eigenvalue of . in,

is the number of receiving antennas of the jth user,

is the variance of additive complex Gaussian white noise on each receiving antenna of the jth user, n _T is the number of transmitting antennas at the base station,

is the identity matrix of n _T ×n _T , H _j is the channel matrix of the jth user, (·) ^-1 represents the inverse of the matrix, (·) ^T represents the transpose of the matrix, (·) ^* represents the conjugate of the matrix Transpose,

is the extended channel matrix, which is composed of each user channel matrix except H _j , namely:

${\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; h</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; ]</span>}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

3) In this example, the user's signal-to-leakage-to-noise ratio (SLNR) is selected as the replacement cost factor, and the specific calculation formula is:

${\mathrm{<span\; class="notranslate">\; \&gamma;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\frac{{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}_{\mathrm{<span\; class="notranslate">\; f</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{{\mathrm{<span\; class="notranslate">\; no</span>}}_{{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}_{\mathrm{<span\; class="notranslate">\; f</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

Among them, w _j is the precoding vector obtained by formula (1), and ||·|| _F is the Frobenius norm of the matrix.

4) Calculate the replacement cost factor γ _j (j=1…M) of each user in the set U according to formula (3), record the smallest replacement cost factor as γ _min , and mark the user with the smallest replacement cost factor is u _min .

中信道Frobenius范数值最大的用户

置换临时调度用户集U中置换代价因子最小的用户u_min。5) Take out the candidate user set

The user with the largest Frobenius norm value in the middle channel

Replace the user u _min with the smallest replacement cost factor in the temporary scheduling user set U.

Update collection: $u\&LeftArrow;\{u-\{u_{\min }\left\}\right\},u\&LeftArrow;\{u\&cup;\{{\stackrel{\&OverBar;}{u}}_{\max }\left\}\right\},\stackrel{\&OverBar;}{u}\&LeftArrow;\{\stackrel{\&OverBar;}{u}-\{{\stackrel{\&OverBar;}{u}}_{\max }\left\}\right\}$

表示除去集合

中的元素

表示将元素

加入集合U。Among them, the symbol "←" means to assign the value of the variable on the right to the variable on the left,

means to remove the set

elements in

Indicates that the element

Join the set U.

同时标记具有该最小置换代价因子对应的用户为

i表示第i次置换；Calculate the replacement cost factor of each user in the temporary scheduling user set U after the update, and record the minimum replacement cost factor as

At the same time, mark the user corresponding to the minimum replacement cost factor as

i represents the i-th replacement;

否则，恢复用户子集： $U\&LeftArrow;\{U-\{{\stackrel{\&OverBar;}{u}}_{\max }\left\}\right\},$ U←{U∪{u_min}}。6) If , then the replacement is successful, so that

Otherwise, restore a subset of users: $u\&LeftArrow;\{u-\{{\stackrel{\&OverBar;}{u}}_{\max }\left\}\right\},$ U←{U∪{u _min }}.

是否为空集

如果是，结束置换选择，得到最终调度用户子集U；否则，返回步骤5)。7) Check collection

Is it an empty set

If yes, end the permutation selection and obtain the final scheduled user subset U; otherwise, return to step 5).

When the number of users to be scheduled is 15, each user has 2 receiving antennas, the base station has 8 transmitting antennas, and the maximum number of users that can be served at the same time is 4, the scheduling method (RBS) of the present invention is adopted, and the signal-leakage-to-noise ratio is selected as the replacement cost factor ) and the system capacity curves obtained by the traversal-based capacity maximization scheduling method (MC), ergodic-based maximum minimum signal-to-leakage-noise ratio scheduling method (MMSLNR) and random scheduling method (Random) are shown in Figure 3. Figure 3 shows that the system capacity obtained by the scheduling method of the present invention is far greater than the system capacity obtained by the random scheduling method, and compared with the system capacity obtained by the scheduling method based on the traversal method to maximize the system capacity, the loss can be ignored.

Claims (1)

1. A low-complexity multi-user scheduling method based on permutation, characterized in that, the concrete steps are as follows: Step A, set the number of all users to be scheduled as K, the maximum number of users that the base station can serve at the same time is M, M<K, calculate the channel quality factors of K users to be scheduled, and select M with the largest channel quality factor of the users to be scheduled users to be scheduled as the initial value of the temporary scheduling user set U; the remaining users to be scheduled form the candidate user set

Step B, calculate the replacement cost factor of each user in the temporary scheduling user set U, record the minimum replacement cost factor as γ _min , and mark the user with the minimum replacement cost factor as u _min ; Step C, take out the candidate user set

The user with the largest channel quality factor

Replace the user u _min with the smallest replacement cost factor in the temporary scheduling user set U; Calculate the replacement cost factor of each user in the temporary scheduling user set U after the update, record the minimum replacement cost factor as γ′ _min , and mark the user corresponding to the minimum replacement cost factor as u′ _min ; Step D, if γ _min <γ′ _min , the replacement is successful, set γ _min ←γ′ _min , u _min ←u′ _min ; otherwise, restore the user subset: U←{U∪{u _min }}; Step E, check the set of alternative users

is empty set, if alternative user set

is an empty set, then end the replacement, and determine the temporary scheduling user set U as the final scheduling user set; otherwise, return to step C to continue execution.

Images