基于多背包问题的聚合频谱分配方法

摘要

本发明公开了一种基于多背包问题的聚合频谱分配方法。主要解决传统分配方法频谱利用率低的问题，其实现过程为：基站收集用户的服务请求信息和系统频带中的空闲频段，并从低频到高频段对系统频带中的空闲频段进行聚合，获得可利用的M个聚合频段，依据最大化频谱利用效率准则，基站对M个聚合频段分配的判决过程模拟为多背包问题MKP，然后根据多背包问题MKP的求解原理，求解得到最终的分配结果，最后由基站将该分配结果发送给用户，完成当前的聚合频谱分配。本发明具有能够充分利用离散空闲频段的优点，可应用于支持频谱聚合SA的无线通信系统中，在满足用户宽带需求的同时，极大地提升频谱的使用效率。

主权项

一种基于多背包问题的聚合频谱分配方法，包括如下步骤：(1)基站收集用户的服务请求信息，得到当前用户需求的带宽集合Q＝{q₁,q₂,…,q_r,…,q_N}，同时收集当前系统频带中的空闲频段，得到离散的空闲频段集合其中，q_r为第r个用户需求的带宽，r＝1,2,…,N,N为不小于1的自然数，表示并集，[f_cL,f_cU]表示第c个空闲频段，f_cL、f_cU分别表示第c个空闲频段的起始频点和终止频点，第c+1个空闲频段的起始频点大于第c个空闲频段的终止频点f_cU<f_(c+1)L，c＝1,2,…,H,H表示系统频带包含的空闲频段数；(2)根据无线电设备的聚合跨度，基站对上述的空闲频段集合A，从低频到高频带进行聚合，得到聚合频段集合F：F＝{B₁,B₂,…,B_j,…,B_M}，其中，表示第j个聚合频段，j＝1,2,…,M，M为不小于1的自然数，表示并集，表示聚合频段j中的第s个空闲频段，分别表示它的起始频点和终止频点，t_j为不小于1的自然数，它表示第j个聚合频段包含的空闲频段数目，任意两个不同的聚合频段的交集为空符号∩表示交集，下标i≠j，第j+1个聚合频段的起始频点不小于第j个聚合频段的终止频点$f_{jU}^{t_j}\le f_{(j+1)L}^1;$(3)根据最大化频谱的使用效率准则，基站将收集到的N个用户分配到步骤2得到的聚合频段集合F中，用公式表示为：$max\underset{j=1}{\overset{M}{\Sigma }}\underset{i=1}{\overset{N}{\Sigma }}{q}_i{x}_{ij}$$s.t.\underset{j=1}{\overset{M}{\Sigma }}\underset{i=1}{\overset{N}{\Sigma }}{q}_i{x}_{ij}\le \left|B_j\right|,j=1,...,M,---<1>$$\underset{j=1}{\overset{M}{\Sigma }}{x}_{ij}\le 1,i=1,2,...,N,$x_ij∈{0,1},i＝1,2,…,N,j＝1,2,…,M,其中，目标函数表示将N个用户最优地分配到M个聚合谱段中，使得分配获得的总带宽最大，式中，q_i表示用户i需求的带宽，i＝1,2,…,N，x_ij为二元判决变量，若x_ij＝1，则表示用户i被分配到聚合频段B_j中；若x_ij＝0，则用户i未分配到聚合频段B_j中；约束条件一表示每个聚合频段所分配的用户总带宽不超过其大小，式中，|B_j|表示聚合频段B_j的带宽，j＝1,2,…,M；约束条件二表示每个用户只可能被分配到一个聚合频段中，i＝1,2,…,N；(4)根据多背包问题MKP的求解原理确定<1>式的解，得到分配结果：4a)从聚合频段集合F中选择带宽最小的可利用的聚合频段B_j，j∈{1,2,…,M}，对未分配的用户进行最优分配，用公式表示为：$max\underset{i=1}{\overset{{\tilde{N}}_j}{\Sigma }}{q}_i{x}_{ij}$$s.t.\underset{i=1}{\overset{{\tilde{N}}_j}{\Sigma }}{q}_i{x}_{ij}\le \left|B_j\right|,j\in \{1,2,...,M\}---<2>$$x_{ij}\in \{0,1\},i=1,2,...,{\tilde{N}}_j,j\in \{1,2,3,...,M\}$式中，表示未分配带宽的用户数量，x_ij为二元判决变量，|B_j|表示可分配的聚合频段B_j的带宽；4b)基于动态规划方法求解<2>式，得到当前聚合频段B_j的最优分配，其相应的判决向量为相应的目标函数值为其中，为二元判决值，若二元判决值则表示将用户i分配到聚合频段B_j中，若二元判决值表示将用户i未分配到聚合频段B_j中，[ ]^T表示向量转置；4c)判断聚合频段集合F中是否还存在可利用的聚合频段，如果存在，返回执行步骤4a)；否则，分配结束，得到<1>式的一个次优解矩阵X和相应的目标函数值v分别为：X＝[x₁,x₂,…,x_j,…,x_M]，其中，表示对聚合频段B_j的判决向量，为二元判决值，若二元判决值则表示用户i被分配到聚合频段B_j中；若二元判决值则表示用户i未分配到聚合频段B_j中，[ ]^T表示向量转置，解矩阵X为频谱分配的结果，目标函数值v为分配得到的总带宽；(5)基站将步骤4的分配结果发送给用户，完成当前的聚合频谱分配。