基于禁忌搜索的密集无线局域网多维资源分配方法

摘要

本发明提出了一种密集无线局域网中的多维资源分配方法，主要解决现有算法没有联合AP组合、AP信道和AP功率进行分配，以及联合分配复杂度高、难以实用的问题。其实现方法是：由网络当前使用的AP组合向量开始，给向量所表示使用的AP分配信道、确定关联用户、在候选功率向量的邻域向量中进行禁忌搜索得到当前AP组合向量的最佳功率向量，在AP组合向量使用最佳功率向量的基础上，再在候选AP组合向量的邻域向量中进行禁忌搜索得到最优AP组合向量，由此得到网络的最优资源分配向量。本发明提高了网络的吞吐量和能效，可用于无线局域网部署规划和网络优化中确定所使用的AP组合、信道和功率。

说明书

技术领域

本发明属于通信技术领域，涉及无线局域网中的资源分配技术，特别涉及一种基 于禁忌搜索的密集无线局域网多维资源分配方法，可用于无线局域网部署规划和网络 优化。

背景技术

近几年来，无线局域网WLAN技术发展迅猛，由于其具有数据速率高和成本低 的特点，WLAN被广泛部署在公司、机场、会议中心等热点区域，为用户提供高速 的数据传输。随着WLAN接入点AP的覆盖越来越密集，造成接入点AP之间的干扰 越来越大，使得WLAN网络的性能下降很大。为了提升WLAN网络的性能，满足用 户的业务需求，对WLAN网络进行合理的资源分配就显得极为重要。

WLAN网络的资源分配方法包括确定网络中使用的接入点AP组合、接入点AP 所使用的信道和接入点AP所使用的功率这三个方面。确定使用的接入点AP组合时， 最基本的要求是保证接入点AP覆盖区域内的用户都能够接入网络，在此之上接入点 AP的部署还应随着用户密度的变化而变化，在用户密集的区域增加接入点AP以保 证服务质量，在用户稀少的区域关闭一些闲置接入点AP以节省能量，降低干扰；在 确定了所使用的接入点AP组合的基础上，通过规划信道和分配功率，可以进一步降 低网络间干扰，提升网络的性能。因此，最优的WLAN资源分配方案应该是在基于 用户需求和密度等动态变化的信息基础上，联合考虑使用的接入点AP组合、信道分 配和功率分配这三个方面得出的。

目前，关于无线局域网联合资源分配技术的研究大多只关注接入点AP组合确定、 信道分配、功率分配这三个方面中的两个方面。如Jia-Liang Lu等在Wireless and Mobile Computing,Networking and Communications,2006《Indoor WLAN Planning with a QoS constraint based on a Markovian Performance Evaluation Model》一文中，提出了 一种基于多目标准则优化的联合接入点AP个数和信道分配算法，此方法将保证无线 覆盖，降低干扰和保证用户QoS需求三个目标准则结合在一起，相比其他单目标的 资源分配算法，能从多个方面指引网络的资源分配，提升网络的性能，但此方法的不 足是所有接入点AP都是等功率发射，没有将功率控制加入其中，整个网络的能效较 低；又如Jun Zhang等在IEEE Transactions on wireless communication，2011《Minimizing Cost of Placement of Multi-Radio and Multi-Power-Level Access Points with Rate Adaptation in Indoor Environment》提出了一种在给定用户位置和用户业务需求的场景 下，通过合并邻近接入点AP，并进行功率分配的方法，使得网络使用的接入点AP 数目和造价最小，但此方法的不足是所有的用户都工作在同一信道下，未将信道分配 问题考虑其中，在实际网络中由于同频干扰较大导致系统吞吐量不高，因而该方法仍 有提升的空间。

发明内容

本发明针对现有技术的不足，提出一种基于禁忌搜索的密集无线局域网多维资源 分配方法，联合确定接入点AP组合、接入点AP信道和接入点AP功率，在保证网 络覆盖、降低用户干扰和保证用户业务需求的前提下，提高了网络的吞吐量和能效。

实现本发明的技术关键在于准确的衡量网络性能，建立网络资源与网络性能之间 的关系，从而得到网络资源分配的优化目标函数，并能以较低的复杂度得到目标的最 优解，在此过程中实现对接入点AP组合、信道和功率的联合分配。具体实现步骤如 下：

（1）统计得到网络中所有接入点AP个数M和当前使用的接入点AP个数L， L≤M，将所有接入点AP依次编号为AP₁,AP₂...AP_i...AP_M，i∈{1,2...M}，根据网络当 前使用的接入点AP初始化候选接入点AP组合向量a=(a′₁,a′₂...a′_M)，其中a′_i＝1表示 选中使用AP_i，a′_i＝0表示未选中使用AP_i，初始化最优值f_opt为正无穷大，初始化迭 代次数上限NI=1000，初始化迭代次数计数器iter=0；

（2）给候选接入点AP组合向量a选中使用的每个接入点AP分配信道，得到信 道分配向量c_opt；

（3）利用上述信道分配向量c_opt，确定每个用户所连接的接入点AP；

（4）利用上述每个用户和接入点AP的连接关系，得到候选接入点AP组合向量 对应的最佳功率向量：

（4a）初始化当前功率向量p=(p′₁,p′₂...p′_i...p′_M)，p′_i表示AP_i所用功率， i∈{1,2,...,M}，初始时各接入点AP均使用最大功率；

（4b）计算网络使用当前功率向量时，每个用户所受到的最大干扰I_n和每个用户 的信干噪比SINR_n：

$I_n=\underset{i\in A_k,i\ne k}{\Sigma }{p}_i^{\prime }{H}_{\mathrm{in}}$

${\mathrm{SINR}}_n=\frac{p_k^{\prime }{H}_{\mathrm{kn}}}{{\sigma }^2+I_n}$

其中，AP_k代表用户n所连接的接入点AP，A_k表示所有与AP_k同信道的接入点 AP集合，H_in表示AP_i与用户n之间的信道损耗，p′_i表示AP_i所用功率，p′_k表示AP_k所用功率，H_kn表示AP_k与用户n之间的信道损耗，σ²表示背景噪声的功率大小；

（4c）计算取当前功率向量和信道向量时，用户n所获得的吞吐量d_n；

（4d）根据用户所受到的最大干扰I_n，每个用户的信干噪比SINR_n和用户n所获 得的吞吐量d_n，构建目标函数f：

$f=\frac{w_1}{N}\sqrt{\underset{n\in N}{\Sigma }Q{\left({\mathrm{SINR}}_n\right)}^2}+\frac{w_2}{N}\sqrt{\underset{n\in N}{\Sigma }\max {(I_n-{\sigma }^2,0)}^2}+\frac{w_3}{N}\sqrt{\underset{n\in N}{\Sigma }\max {(10\log \left({D^{*}}_n\right)-10\log \left(d_n\right),0)}^2}$

其中，w₁、w₂和w₃分别表示三个权重因子，并且满足0≤w_i≤1,i＝1,2,3，N表 示总用户数，Q(SINR)表示以信干噪比SINR为参数的罚函数值，σ²表示背景噪声功 率的大小，表示用户n的需求吞吐量；

（4e）利用禁忌搜索方法，在功率向量p的邻域向量中搜索目标函数的最小值 f_min，目标函数最小值对应的功率向量即为候选接入点AP组合向量对应的最优功率 向量p_opt；

（5）若目标函数的最小值f_min小于最优值f_opt，则令f_opt=f_min；

（6）若迭代次数计数器iter等于迭代次数上限NI，或最优值f_opt等于0，则当前 候选接入点AP组合向量a即为最优AP组合向量a_opt，从而得到网络最优资源分配向 量S_opt=(a_opt,c_opt,p_opt)，否则，用候选接入点AP组合向量a的邻域向量更新a，转步 骤（2）执行下一次迭代，迭代次数计数器iter自增1；

（7）网络中每个接入点AP依照网络最优资源分配向量S_opt重构其配置参数。

本发明与现有技术相比具有如下主要优点：

（1）本发明联合网络覆盖情况、用户干扰情况和用户QoS不满意度情况三个角 度对网络性能进行了衡量，以提升网络性能为导向，通过联合接入点AP组合选择、 信道分配和功率调整降低了网络中的干扰，提升了网络的吞吐量和能效，即单位能量 所能成功传输的比特数。

（2）在联合考虑接入点AP组合选择、接入点AP信道分配和接入点AP功率分 配三个因素后，现有算法复杂度呈指数增长，通过遍历每种可能的组合得到最优解是 难以实现的，而本发明通过采用禁忌搜索的方法，在当前解的邻域迭代执行连续的搜 索，通过选取合理的邻域，设置恰当的禁忌参数，降低了复杂度，可在有限时间内逼 近全局最优解，使得本方法具有很好的实用性。

附图说明

图1是本发明适用的应用场景图；

图2是本发明的流程图；

图3是本发明中得到候选接入点AP组合向量对应的最佳功率向量的子流程图；

图4是本发明与现有资源分配方法关于网络性能的比较图；

图5是本发明与现有资源分配方法关于网络吞吐量的比较图；

图6是本发明与现有资源分配方法关于网络能效的比较图。

具体实施方式

以下对本发明的原理以及技术方案做进一步的描述：

参照图1，本发明的实现场景为一接入点AP密集覆盖的办公室区域，区域内共 有N个用户，每个接入点AP可以选择h个离散功率等级中的一个，各接入点AP和 用户间通信采用的是无线局域网的802.11g协议，为了方便统计，区域被以栅格为单 位进行了划分。

参照图2，本发明的具体实现流程包括以下步骤：

步骤1，统计得到网络中所有接入点AP个数M和当前使用的接入点AP个数L， L≤M，将所有接入点AP依次编号为AP₁,AP₂...AP_i...AP_M，i∈{1,2...M}，根据网络当 前使用的接入点AP初始化候选接入点AP组合向量a=(a′₁,a′₂...a′_M)，其中a′_i＝1表示 选中使用AP_i，a′_i＝0表示未选中使用AP_i，初始化最优值f_opt为正无穷大，初始化迭 代次数上限NI=1000，初始化迭代次数计数器iter=0。

步骤2，利用Riihijarvi J.在Wireless On-demand Network Systems and Services,2005 《Frequency allocation for WLANs using graph coloring techniques》一文中提出的基于 图论着色的方法，给候选接入点AP组合向量a选中使用的每个接入点AP分配信道， 得到信道分配向量c_opt。

步骤3，利用信道分配向量c_opt，根据Mohamed H.Ahmed在IEEE Communications Letters，2005《SINR Threshold Lower Bound for SINR-based Call Admission Control in CDMANetworks with Imperfect Power Control》一文中使用的基于最大信干噪比的接 入选择方法，确定每个用户所连接的接入点AP。

步骤4，利用上述每个用户和接入点AP的连接关系，得到候选接入点AP组合 向量对应的最佳功率向量。

参照图3，本步骤的具体实现如下：

4.1）初始化当前功率向量p=(p′₁,p′₂...p′_i...p′_M)，p′_i表示AP_i所用功率， i∈{1,2,...,M}，p′_i可以取h个功率等级中的任一等级功率值，初始时各接入点AP均 使用最大功率；

4.2）计算网络使用当前功率向量时，每个用户所受到的最大干扰I_n和每个用户 的信干噪比SINR_n：

$I_n=\underset{i\in A_k,i\ne k}{\Sigma }{p}_i^{\prime }{H}_{\mathrm{in}}$

${\mathrm{SINR}}_n=\frac{p_k^{\prime }{H}_{\mathrm{kn}}}{{\sigma }^2+I_n}$

其中，AP_k代表用户n所连接的接入点AP，A_k表示所有与AP_k同信道的接入点 AP集合，H_in表示AP_i与用户n之间的信道损耗，p′_i表示AP_i所用功率，p′_k表示AP_k所 用功率，H_kn表示AP_k与用户n之间的信道损耗，σ²表示背景噪声的功率大小；

4.3）利用Xiang Ling等在IEEE Transactions on wireless communications,October 2006《Joint Access Point Placement and Channel Assignment for 802.11Wireless LANs》 一文中提出的方法，估计取当前功率向量和信道向量时，用户所能获得的吞吐量d_n；

4.4）根据用户所受到的最大干扰I_n，每个用户的信干噪比SINR_n和用户n所获得 的吞吐量d_n，构建目标函数f：

$f=\frac{w_1}{N}\sqrt{\underset{n\in N}{\Sigma }Q{\left({\mathrm{SINR}}_n\right)}^2}+\frac{w_2}{N}\sqrt{\underset{n\in N}{\Sigma }\max {(I_n-{\sigma }^2,0)}^2}+\frac{w_3}{N}\sqrt{\underset{n\in N}{\Sigma }\max {(10\log \left({D^{*}}_n\right)-10\log \left(d_n\right),0)}^2}$

其中，代表网络覆盖情况衡量参数，代 表用户干扰情况衡量参数，代表用户QoS不满 意度衡量参数，w₁、w₂和w₃分别表示网络覆盖情况衡量参数、用户干扰情况衡量参 数和用户QoS不满意度衡量参数的权重因子，并且满足0≤w_i≤1,i＝1,2,3，N表示 总用户数，σ²表示背景噪声功率的大小，表示用户n的需求吞吐量，根据用户实 际运行的业务确定的大小，Q(SINR)表示以信干噪比SINR为参数的罚函数值，其 按照信干噪比SINR的范围确定如下：

$Q\left(\mathrm{SINR}\right)=\left(\begin{array}{cc}18.54& \mathrm{SINR}<6.02\\ \mathrm{SINR}-6.02& 6.02\le \mathrm{SINR}<7.78\\ \mathrm{SIRN}-7.78& 7.78\le \mathrm{SINR}<9.03\\ \mathrm{SINR}-9.03& 9.03\le \mathrm{SINR}<10.79\\ \mathrm{SINR}-10.79& 10.79\le \mathrm{SINR}<17.04\\ \mathrm{SINR}-17.04& 17.04\le \mathrm{SINR}<18.80\\ \mathrm{SINR}-18.80& 18.80\le \mathrm{SINR}<24.05\\ \mathrm{SINR}-24.05& 24.05\le \mathrm{SINR}<24.56\\ 0& \mathrm{SINR}\ge 24.56\end{array}\right)$

其中6.02、7.78、9.03、10.79、17.04、18.80、24.05、24.56这八个值分别代表 802.11g系统中要达到6Mbps、9Mbps、12Mbps、18Mbps、24Mbps、36Mbps、48Mbps、 54Mbps这八个速率传输所需的最小信干噪比；

4.5）利用Fred Glover在ORSA Journal on Computing 1989《Tabu Search——Part 1》 提出的禁忌搜索算法，在功率向量p的邻域向量中搜索目标函数的最小值f_min，目标 函数最小值对应的功率向量即为候选接入点AP组合向量对应的最优功率向量p_opt， 其中，功率向量p的邻域向量，是通过对当前选中使用的一个接入点AP进行功率调 整后得到的新功率向量，功率向量p共含有L(h-1)个邻域向量，其中L表示当前使 用的接入点AP个数，h表示接入点AP可选的功率等级数目。

步骤5，若目标函数的最小值f_min小于最优值f_mit，则更新最优值f_opt，令f_opt=f_min。

步骤6，若迭代次数计数器iter等于迭代次数上限NI，或最优值f_opt等于0，则 当前候选接入点AP组合向量a即为最优接入点AP组合向量a_opt，从而得到网络最优 资源分配向量S_opt=(a_opt,c_opt,p_opt)，否则，用候选接入点AP组合向量a的邻域向量 更新a，转步骤（2）执行下一次迭代，迭代次数计数器iter自增1，其中，AP组合 向量a的邻域向量，是通过对a选中使用的接入点AP执行替换操作、或者增加操作、 或者删除操作后，形成的新候选接入点AP组合向量，其中替换操作是指用一个未选 中使用的接入点AP替换当前选中使用的一个接入点AP，增加操作是指增加一个接 入点AP选中使用，删除操作是指去掉一个选中使用的接入点AP。

步骤7，网络中每个接入点AP依照网络最优资源分配向量S_opt重构其配置参数， 即根据候选接入点AP组合向量a_opt得到网络选中使用的接入点AP组合，根据信道向 量c_opt配置选中使用的接入点AP的信道，根据功率向量p_opt配置选中使用的接入点 AP的功率。

本发明的效果可通过仿真进一步说明：

1)仿真参数

仿真场景如图1所示，设区域内共含有M＝12个接入点AP，各接入点AP位置 如图所标，考虑网络的下行链路场景，每个栅格内随机分布着0~3个用户，每个栅格 的大小为15m×15m，权重因子w₁、w₂、w₃都等于1，在仿真中认为用户的QoS需求为 用户的吞吐量需求，设区域内各用户的吞吐量需求为512Kbps，接入点AP存在三 个功率等级可选，即h=3，分别为20dBm，17dBm和14dBm，背景噪声功率大小 σ²=-94dBm，接入点AP和用户之间的信道衰减模型采用改进的Two-Ray Ground Reflection模型：

P_r=P_t+10log₁₀(G_tG_r)+20log₁₀(h_th_r)-40log₁₀(x)-ψ₁-ψ₂

其中，G_t和G_r分别表示发射机增益和接收机增益，h_t和h_r分别表示发射机天线 高度和接收机天线高度，x表示接收机距发射机的距离，ψ₁和ψ₂分别表示无线信号 的穿墙损耗和在转角处的损耗。在仿真中G_t=1，G_r=1，h_t=1，h_r=1，ψ₁取15dB， ψ₂取10dB。

2)仿真内容与结果

仿真1，对本发明方法与联合接入点AP个数和信道分配方法随着接入点AP数 目的变化所能达到的最优目标函数值进行仿真，得到仿真图4。如图4所示，目标函 数值越小，表示网络的性能越优。由图4可以看出，在使用不同数目的接入点AP时， 采用本方法进行资源分配后的网络性能优于采用联合接入点AP个数和信道分配方法 进行资源分配后的网络性能，还可以看出整个网络使用6个接入点AP时目标函数值 最小，网络性能最优，由此也可以确定使网络性能最优所使用的接入点AP个数。

仿真2，对本发明方法与联合接入点AP个数和信道分配方法随着用户吞吐量需 求的不同所能达到的网络总吞吐量进行仿真，得到仿真图5。由图5可以看出，在不 同的用户吞吐量需求下，与联合接入点AP个数和信道分配方法相比，本发明方法均 可以提升网络的总吞吐量。

仿真3，对本发明方法与联合接入点AP个数和信道分配方法随着用户吞吐量需 求的不同所能达到的网络能效进行仿真，得到仿真图6。由图6可以看出，在不同的 用户吞吐量需求下，与联合接入点AP个数和信道分配方法相比，本发明方法均可以 提高整个网络的能效。通过仿真可以看出使用本发明方法在对网络进行资源分配时可 以更好的提升网络的性能，不仅可以提高网络的吞吐量，还可以提高网络的能效，达 到节能环保的效果。