一种具有服务质量保证的802.11ax密集WiFi网络AP布置方法，包括以下步骤：1)、问题描述，过程如下：1.1)建立网络模型；1.2)建立干扰模型；2)Procedure I获得STA的吞吐量的步骤如下：2.1)STA‑AP关联；2.2)AP功率调整；2.3)AP信道分配和功率再调整；2.4)STA RU分配；2.5)获取STA的数据速率；2.6)计算STA的吞吐量；3)设计四阶段启发式算法Algorithm_4stages求解优化问题。本发明融合了AP布置和功率‑信道‑RU分配，在满足失效容忍和用户个性化吞吐量需求的前提下减少AP数量，节约802.11ax密集WiFi网络的部署成本。
1.一种具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，所述方法包括以下步骤：
网络服务的目标区域包含VIP区域和普通区域两个子区域，分别以Vvip和V表示，且以AP表示网络接入点，以STA表示网络站点，以Ω表示AP候选位置集合，该集合是事先已知的，即目标区域Vvip∪V被划分为|Ω|个网格，AP只能布置在网格的中心，在每个网格之内，可以根据STA的密度布置0个、1个或多个AP；网络由如下三种设备组成：网络控制器、AP和STA；网络控制器负责网络的管理和协调，在网络控制器的协调之下，AP在传输数据之前不需要退避；以S和A分别表示STA和AP集合，任意STA i∈S只能与一个AP j∈A关联，当一个AP集合Af满足|Af|<|A|失效时，与故障AP关联的STA可以与其他正常的AP重新关联以获取网络服务，网络采用2.4和5GHz两个频段，在这两个频段中，每个信道的带宽为b MHz，b∈B＝{20,40,80,160}MHz，网络采用OFDMA物理层，在OFDMA中，每个STA在传输数据时不占用整个信道，而是由AP向其分配合适的RU以支持多STA并行传输，每个AP只能分配一个信道，所分配的信道属于一个给定的信道集合C，每个STA只能分配一个j‑tone RU，j∈K＝{26,
52,106,242,484,996,2×996}，其中，K是每个RU中所包含的子载波数目的集合，以P表示AP的功率值集合，每个AP可分配属于P的一个功率值，每个STA所采用的功率与其AP相同；
在OFDMA机制之下，TXOP、SIFS、M‑BA 和OFDMA‑BA分别表示传输机会、短帧间间隔、多STA块确认和OFDMA块确认；在OFDMA帧交换过程中，STA仅在接收到触发帧TF之后才开始将上行PPDU传输给其AP，STA在接收到下行PPDU之后，将OFDMA‑BA帧回复给其AP；
以li,j表示节点i和j之间的链路，节点指的是AP或STA；要使节点i通过链路li,j从j正确接收到帧，则节点i从j处的接收信号强度RSS必须不低于帧解码阈值θD，在这种情况下，节点i在j的通信范围内，如果节点i和j位于信道相互重叠的不同链路上且i从j接收到的信号强度大于或等于干扰信号强度阈值θI，则节点i会被j干扰；在这种情况下，节点i在j的干扰范围之内，θD>θI，为了获得AP的通信范围和干扰范围，定义以下路径损耗模型：RSS＝Pj+GTX‑Plost+GRX (1)
在式(1)和(2)中，RSS是接收方的接收信号强度，d是发送方和接收方之间的距离，Pj是发送方j的发射功率，GTX和GRX是发送方和接收方的天线增益，Pref是参照距离处的路径损耗，η是路径损耗指数，χ是与阴影衰落程度相关的标准差；因此，得到：以rj和γj分别表示节点j的通信范围和干扰范围，则：
由式(1)至(4)以及θD和θI的值，可以获得节点的通信范围和干扰范围；
建立网络干扰模型，以li,x和lj,y分别表示AP i和STA x以及AP j和STA y之间的链路，以di,x和dj,y分别表示AP i和STA x以及AP j和STA y之间的距离，以γx和γy分别表示STA x和STA y的干扰范围；
以S(i)和S(j)分别表示与AP i和j相关联的STA集合，定义AP i和j之间的干扰距离为：如果AP i和j之间的距离小于或等于Ii,j且它们的信道彼此重叠，i≠j，则链路li,x和lj,y相互干扰，即链路li,x和lj,y不能同时传输；
以δi表示STA i的吞吐量，表述为以下优化问题：
在约束条件C1中，如果STA i与AP j关联，则指示变量ai,j＝1，否则ai,j＝0，C1表示当|Af|＝n个AP同时失效时，任何STA i∈S都可以与AP j关联以获得WiFi服务，j∈A\Af；在约束条件C2和C3中，STA i既表示第i个STA，也表示该STA位于第i个位置；C2表示当STA i位于VIP区域时，其吞吐量大于或等于ρH；C3表示当STA i位于VIP区域之外时，其吞吐量大于或等于ρL，其中，ρH>ρL；将C1称为失效容忍需求，将C2和C3称为用户个性化吞吐量需求；
2)STA的吞吐量的计算，采用Procedure I获得STA的吞吐量；
Procedure I获得STA的吞吐量的步骤如下：
A表示AP集合，A也可以表示具体的AP布置方案，由四个阶段组成，每个阶段的关键操作是测试当前的AP布置方案A是否可行，设计算法Algorithm_test进行可行性测试；
Algorithm_test:可行性测试，输入：A,S,Ω,P,C,n；输出：指示变量I，I＝TRUE表示A可行，I＝FALSE表示A不可行，测试过程如下：
3.1.2)判断优化问题(6)的约束条件C1是否能满足，若是，则转向3.1.3)；若否，则置I为FALSE并转向3.1.4)；
3.1.3)在A中删除n＝|Af|个AP，表示有n个AP失效，再调用Procedure I以获得STA的吞吐量，然后，判断优化问题(6)的约束条件C2和C3是否能满足，若在 种AP失效情形下方案A都能满足C2和C3，则转向3.1.4)；若 种AP失效情形中有任意一种情形不能满足C2和C3，则置I为FALSE并转向3.1.4)；
设计四阶段启发式算法Algorithm_4stages求解优化问题(6)，过程如下：第一阶段：采用贪婪法生成初始AP布置方案A1；第二阶段：移除A1中多余的AP；第三阶段：迭代地将两个距离最近的AP替换为一个；第四阶段：迭代地将三个邻近的AP替换为两个；
在第三和第四阶段中，计算每对AP或每组AP的STA覆盖密度CD，先给出CD的定义：定义1：每对AP的覆盖密度CDpair
CDpair＝两个AP所覆盖的STA总数量与这两个AP的距离的比值定义2：每组AP的覆盖密度CDgroup
CDgroup＝三个AP所覆盖的STA总数量与这三个AP的坐标所组成的三角形的周长的比值；
第一阶段：采用贪婪法生成初始AP布置方案A1，步骤如下：
3.2.1)放置一个AP到未被覆盖的STA密度最大的区域，并将被该AP所覆盖的STA标记为已覆盖；
3.2.2)调用算法Algorithm_test测试当前方案是否可行，若是，则转向3.2.3)；若否，则转向3.2.1)；
3.3.1)按每个AP所关联的STA的数量进行升序排序，生成AP队列Qb；
3.3.2)按Qb中AP的顺序，逐个尝试删除，每删除一个AP之后，就调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回3.3.1)；若不可行，则将所删除的AP还原并继续尝试删除队列Qb中下一个AP，直至总共|Qb|次删除尝试完成为止；
第三阶段：将两个距离最近的AP替换为一个，步骤如下：
3.4.2)计算每对AP的STA覆盖密度CDpair；
3.4.3)按CDpair的值升序排序以生成替换队列Qc[i]＝{AP i1,AP i2}，其中AP i1和AP i2表示队列Qc中第i对AP中的两个AP，
3.4.4)按Qc中AP对的顺序，逐对尝试替换为一个新AP，新AP的位置可在候选位置集Ω中搜索获得，然后，调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回
3.4.1)，此时A2中的AP数量减少1个；若不可行，则将所替换的AP对还原，继续尝试替换Qc中下一对AP，如此反复，直至总共|Qc|次替换尝试完成为止；
3.5.2)计算每组AP的STA覆盖密度CDgroup；
3.5.3)按CDgroup的值升序排序以生成替换队列Qd[i]＝{AP i1,AP i2,AP i3}，其中AP i1、AP i2和AP i3表示队列Qd中第i组AP中的三个AP， 3.5.4)按Qd中AP组的顺序，逐组尝试替换为两个新AP，两个新AP的位置可在候选位置集Ω中搜索获得，然后，调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回3.5.1)，此时A3中的AP数量减少1个；若不可行，则将所替换的AP组还原，继续尝试替换Qd中的下一对组AP，如此反复，直至总共|Qd|次替换尝试完成为止；
2.如权利要求1所述的具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，所述步骤2.1)中，STA‑AP关联过程如下：为了进行STA‑AP关联，首先需要获得信号可以覆盖STA i的AP集合，以A(i)表示；在最初阶段，可初始化每个AP的功率为功率集合P中的最大值，即AP j的功率初始化为：Pj＝max{pq},q∈{1,2,...,|P|},j∈A (7)其中，pq表示P中的第q个功率值；
如果STA i和AP j之间的距离di,j小于或等于AP j的通信范围rj，则AP j所发出的信号可以覆盖到STAi，因此，得到：A(i)＝{APj|di,j≤rj},i∈S,j∈A (8)在获得集合A(i)之后，将STA i与A(i)中信号最强的AP相关联，在STA‑AP关联之后，可进一步获得与AP j相关联的STA集合S(j)。
3.如权利要求2所述的具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，所述步骤2.2)中，AP功率调整过程如下：每个AP的功率被初始化为集合P中的最大值，向下调整AP的功率以减少它们之间的干扰，以 表示AP j在功率为pq时的通信范围并设p1
在获得Pj之后，j∈A，可以进一步获得AP i和j之间的干扰范围Ii,j，i≠j。
4.如权利要求3所述的具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，所述步骤2.3)中，AP信道分配和功率再调整的过程为：网络可在2.4和5GHz两个频段上进行传输，以N(i)表示AP i的相邻AP的集合，N(i)定义为：N(i)＝{APj|Di,j≤Ii,j},i,j∈A,i≠j (11)其中，Di,j表示AP i和j之间的距离；
对于任何AP i，如果AP j∈N(i)且非重叠信道数量充足，分配一个不与AP j的信道重叠的信道给AP i，当非重叠信道不足时，降低AP i与其相邻AP之间的干扰程度，如果则分配给AP i的信道可以与AP j的相同；
引入了一个信道冲突指标CCI，用于度量AP之间的干扰程度，以CCIi表示AP i的干扰程度，它定义为：与AP i的信道属于同一个重叠信道集合的相邻AP的个数。
5.如权利要求4所述的具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，信道分配的步骤如下：
2.3.1)将每个AP的信道编号和CCI值均初始化为0；
2.3.2)根据每个AP所关联的STA数量对AP进行降序排序，生成信道分配队列Qa，STA数量最高的AP位于队首；
2.3.3)根据队列Qa中AP的顺序逐一为每个AP分配信道，如果当前非重叠信道数量足够多，则将非重叠信道中编号最低的信道分配给当前AP；如果当前非重叠信道不足，则找出使得当前AP及其相邻AP的CCI值增加幅度最小的信道并将之分配给当前AP；
2.3.4)在不引起每个AP的CCI值增加的前提下，根据队列Qa中AP的顺序逐一将已分配给AP的信道更新至具有更大带宽的信道；
在信道分配后，重新调整AP的功率以增加STA的接收信号强度，对于当前功率pq低于p|P|的每个AP i，将其功率从pq提升至pq+1，q∈[1,|P|‑1]，然后判断从AP i以功率pq+1发出的信号是否干扰其他基本服务集，如果是，则不增加该AP的功率；否则，继续将其功率从pq+1调整到pq+2，直到功率值等于p|P|为止。
6.如权利要求5所述的具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，所述步骤2.4)中，STA RU分配的过程如下：
802.11ax定义了七种RU类型，这些RU所组成的集合K＝{26,52,106,242,484,996,2×
996}，每个信道所包含的k‑tone RU的最大个数由信道带宽bi确定，k∈K，i＝1,2,3,4，其中，b1＝20,b2＝40,b3＝80,b4＝160MHz，在每个OFDMA传输中，20、40、80和160MHz信道中分别最多支持9个，18个，37个和74个STA并行传输；
k‑tone RU的最大数量由信道带宽决定，k∈K，进行STA RU分配时，定义mb个RU多重集合用于RU分配，b∈B,m＝1,2,…,mb，其中mb是b MHz信道中26‑tone RU的最大数量；将较大的RU分配给距离AP较远的STA，将较小的RU分配给距离AP较近的STA，对于任何具有信道带宽b的AP i(i∈A)，采取以下步骤将RU分配给与其关联的STA：
2.4.1)将|S(i)|除以mb，得到商为 余数为rem；
2.4.2)当rem不等于零时，将AP i的|S(i)|个STA划分为 组，第x组包含mb个STA，x＝1,2,3,…, 第 组包含rem个STA；当rem等于零时，将AP i的|S(i)|个STA划分为S(i)/mb组，每组包含mb个STA；
2.4.3)当rem不等于零时，将集合RUb,mb中的RU分配给第x组的STA，x＝1,2,3,…,并将RUb,rem中的RU分配给第 组的STA；当rem等于零时，每个STA均分配一个26‑tone RU；
7.如权利要求6所述的具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，所述步骤2.5)中，获取STA的数据速率的过程如下：根据RSS和STA的RU即可获得STA的数据速率，从IEEE 802.11ax草案中，可以获得接收方最小灵敏度MS和数据速率之间的对应关系，如表1所示：最小灵敏度(dBm) 数据速率(Mb/s)
表中，MSb,x表示b MHz信道中的第x个最小灵敏度值，b∈B，x＝1,2,…,X；σk,x表示k‑tone RU中第x个数据速率，k∈K，表1中，MSb,1
以RSSi和Ri分别表示AP j从STA i接收到的信号强度和STA i的上行数据速率，i∈S，根据RSS的值和表1，得到：在AP和STA功率相同的情况下，STA的下行数据速率也等于Ri。
8.如权利要求7所述的具有服务质量保证的802.11ax密集WiFi网络AP布置方法，其特征在于，所述步骤2.6)中，计算STA的吞吐量的过程为：对于信道带宽为b的任意AP j，j∈A，有|S(j)|个STA与之关联，进行Mj次帧交换以完成一轮通信，即S(j)中每个STA完成一次上行数据传输和一次下行数据接收，Mj的表达式如下：以tTF、tSIFS、tUL_PPDU、tM_BA、tDL_PPDU和tOFDMA_BA分别表示TF、SIFS、上行PPDU、M‑BA、下行PPDU和OFDMA‑BA的持续时间，以TUL和TDL分别表示上行和下行传输的持续时间，得到：TUL＝tTF+2tSIFS+tUL_PPDU+tM_BA (14)以及
TDL＝2tSIFS+tDL_PPDU+tOFDMA_BA (15)以Tj表示STA和AP j之间一轮通信的持续时间，则:
式(17)中，CCIj+1表示AP j及其CCIj个相邻AP相互干扰，AP j及其CCIj个相邻AP轮流传输。
一种具有服务质量保证的802.11ax密集WiFi网络AP布置方法
技术领域
[0001] 本发明涉及一种基于IEEE 802.11ax标准的密集WiFi网络接入点(Access Point,AP)布置方法。
背景技术
[0002] 随着互联网进一步普及，越来越多用户通过WiFi访问互联网。近几年来，基于IEEE 802.11ax的密集WiFi网络引起了工业界和学术界的强烈关注。在密集WiFi网络中，许多用户聚集在一个区域，如体育场、会议室或办公室等，这些用户同时接入WiFi网络，对WiFi网络服务提出了巨大的需求，如通过WiFi网络上传/下载音频/视频等。在这种情况下，网络中需要布置许多接入点(Access Point,AP)且相邻AP之间的距离非常接近。在传统802.11密集WiFi网络中，布置数量众多的AP不一定能转化为高吞吐量，主要原因如下：(1)大量用户同时访问WiFi网络容易导致帧冲突频繁发生；(2)大量AP同时工作容易导致基本服务集(Basic Service Set,BSS)之间相互干扰。为了改善用户在密集WiFi网络中的体验，作为下一代WiFi标准的802.11ax引起了科技人员的高度重视。802.11ax支持正交频分多路复用(Orthogonal Frequency Division Multiple Access,OFDMA)技术，该技术将信道中的子载波分为若干组，每组称为资源单元(Resource Unit,RU)，通过合理地将RU分配给网络站点(Station,STA)，多个STA可以并行传输数据；此外，802.11ax还支持2.4和5GHz两个频段，这意味着，我们有更多非重叠信道可供选择，从而减少相邻BSS之间的相互干扰。总之，设计和部署基于802.11ax的密集WiFi网络具有重要性和紧迫性。
[0003] 影响WiFi网络性能的主要因素有两个：其一是AP的布置方案；其二是AP和STA的资源分配，如功率、信道和RU等的分配。此外，为了向用户提供具有服务质量(Quality of Service,QoS)保证的WiFi网络服务，所部署的WiFi网络还需要具有失效容忍能力和满足用户个性化吞吐量需求。遗憾的是，到目前为止，暂未有关于具有QoS保证的802.11ax密集WiFi网络AP布置方面的相关发明。这是本发明的动机。
发明内容
[0004] 为了克服已有技术的不足，本发明提供了一种具有服务质量保证的802.11ax密集WiFi网络AP布置方法，该方法融合了AP布置和功率‑信道‑RU分配，在满足失效容忍和用户个性化吐吞量需求的前提下减少AP数量，从而节约802.11ax密集WiFi网络的部署成本。
[0005] 本发明解决其技术问题所采用的技术方案是：
[0006] 一种具有服务质量保证的802.11ax密集WiFi网络AP布置方法，所述方法包括以下步骤：
[0007] 1)、问题描述，过程如下：
[0008] 1.1)建立网络模型
[0009] 网络服务的目标区域包含VIP区域和普通区域两个子区域，分别以Vvip和V表示，且以AP表示网络接入点，以STA表示网络站点，以Ω表示AP候选位置集合，该集合是事先已知的，即目标区域Vvip∪V被划分为|Ω|个网格，AP只能布置在网格的中心，在每个网格之内，可以根据STA的密度布置0个、1个或多个AP；网络由如下三种设备组成：网络控制器、AP和STA；网络控制器负责网络的管理和协调，在网络控制器的协调之下，AP在传输数据之前不需要退避；以S和A分别表示STA和AP集合，任意STA i∈S只能与一个AP j∈A关联，当一个AP集合Af满足|Af|<|A|失效时，与故障AP关联的STA可以与其他正常的AP重新关联以获取网络服务，网络采用2.4和5GHz两个频段，在这两个频段中，每个信道的带宽为b MHz，b∈B＝{20,40,80,160}MHz，网络采用OFDMA物理层，在OFDMA中，每个STA在传输数据时不占用整个信道，而是由AP向其分配合适的RU以支持多STA并行传输，每个AP只能分配一个信道，所分配的信道属于一个给定的信道集合C，每个STA只能分配一个j‑tone RU，j∈K＝{26,
52,106,242,484,996,2×996}，其中，K是每个RU中所包含的子载波数目的集合，以P表示AP的功率值集合，每个AP可分配属于P的一个功率值，每个STA所采用的功率与其AP相同；
[0010] 在OFDMA机制之下，TXOP、SIFS、M‑BA和OFDMA‑BA分别表示传输机会、短帧间间隔、多STA块确认和OFDMA块确认；在OFDMA帧交换过程中，STA仅在接收到触发帧TF之后才开始将上行PPDU(UL PPDU)传输给其AP，STA在接收到下行PPDU(DU PPDU)之后，将OFDMA‑BA帧回复给其AP；
[0011] 1.2)建立干扰模型
[0012] 以li,j表示节点i和j之间的链路，此处，节点指的是AP或STA；要使节点i通过链路li,j从j正确接收到帧，则节点i从j处的接收信号强度(Received Signal Strength,RSS)必须不低于帧解码阈值θD，在这种情况下，节点i在j的通信范围内，反之亦然；此外，如果节点i和j位于信道相互重叠的不同链路上且i从j接收到的信号强度大于或等于干扰信号强度阈值θI，则节点i会被j干扰；在这种情况下，节点i在j的干扰范围之内，反之亦然；θD>θI，为了获得AP的通信范围和干扰范围，定义以下路径损耗模型：
[0013] RSS＝Pj+GTX‑Plost+GRX (1)
[0014] 其中，
[0015] Plost＝Pref+10lg(dη)+χ (2)
[0016] 在式(1)和(2)中，RSS是接收方的接收信号强度，d是发送方和接收方之间的距离，Pj是发送方j的发射功率，GTX和GRX是发送方和接收方的天线增益，Pref是参照距离(通常为1m)处的路径损耗，η是路径损耗指数，χ是与阴影衰落程度相关的标准差；因此，得到：
[0017]
[0018] 以rj和γj分别表示节点j的通信范围和干扰范围，则：
[0019]
[0020] 由式(1)至(4)以及θD和θI的值，可以获得节点的通信范围和干扰范围；
[0021] 接下来介绍网络干扰模型，以li,x和lj,y分别表示AP i和STA x以及AP j和STA y之间的链路，以di,x和dj,y分别表示AP i和STA x以及AP j和STA y之间的距离，以γx和γy分别表示STA x和STA y的干扰范围；
[0022] 以S(i)和S(j)分别表示与AP i和j相关联的STA集合，定义AP i和j之间的干扰距离为：
[0023]
[0024] 如果AP i和j之间的距离小于或等于Ii,j且它们的信道彼此重叠，i≠j，则链路li,x和lj,y相互干扰，即链路li,x和lj,y不能同时传输
[0025] 1.3)优化问题
[0026] 以δi表示STA i的吞吐量，表述为以下优化问题：
[0027]
[0028] 在约束条件C1中，如果STA i与AP j关联，则指示变量ai,j＝1，否则ai,j＝0，C1表示当|Af|＝n个AP同时失效时，任何STA i∈S都可以与AP j关联以获得WiFi服务，j∈A\Af；在约束条件C2和C3中，在不引起混淆的前提下，STA i既表示第i个STA，也表示该STA位于第i个位置；于是，C2表示当STA i位于VIP区域时，其吞吐量大于或等于ρH；C3表示当STA i位于VIP区域之外时，其吞吐量大于或等于ρL，其中，ρH>ρL；将C1称为失效容忍需求，将C2和C3称为为用户个性化吞吐量需求；
[0029] 2)STA的吞吐量的计算，采用Procedure I获得STA的吞吐量；
[0030] Procedure I获得STA的吞吐量的步骤如下：
[0031] 2.1).STA‑AP关联；
[0032] 2.2).AP功率调整；
[0033] 2.3).AP信道分配和功率再调整；
[0034] 2.4).STA RU分配；
[0035] 2.5).获取STA的数据速率；
[0036] 2.6).计算STA的吞吐量；
[0037] 3)启发式算法
[0038] A表示AP集合，实际上，A也可以表示具体的AP布置方案，这不会引起混淆，由四个阶段组成，每个阶段的关键操作是测试当前的AP布置方案A是否可行，因此，首先设计了算法Algorithm_test进行可行性测试；
[0039] Algorithm_test:可行性测试，输入：A,S,Ω,P,C,n；输出：指示变量I，I＝TRUE表示A可行，I＝FALSE表示A不可行，测试过程如下：
[0040] 3.1.1)将I置为TRUE；
[0041] 3.1.2)判断优化问题(6)的约束条件C1是否能满足，若是，则转向3.1.3)；若否，则置I为FALSE并转向3.1.4)；
[0042] 3.1.3)在A中删除n＝|Af|个AP，表示有n个AP失效，再调用Procedure I以获得STA的吞吐量，然后，判断优化问题(6)的约束条件C2和C3是否能满足，若在 种AP失效情形下方案A都能满足C2和C3，则转向3.1.4)；若 种AP失效情形中有任意一种情形不能满足C2和C3，则置I为FALSE并转向3.1.4)；
[0043] 3.1.4)返回I的值
[0044] 接着，设计四阶段启发式算法Algorithm_4stages求解优化问题(6)，过程如下：第一阶段：采用贪婪法生成初始AP布置方案A1；第二阶段：移除A1中多余的AP；第三阶段：迭代地将两个距离最近的AP替换为一个；第四阶段：迭代地将三个邻近的AP替换为两个。
[0045] 进一步，在第三和第四阶段中，需要计算每对AP或每组AP的STA覆盖密度CD，此处，先给出CD的定义：
[0046] 定义1：每对AP的覆盖密度CDpair
[0047] CDpair≡两个AP所覆盖的STA总数量与这两个AP的距离的比值
[0048] 定义2：每组AP的覆盖密度CDgroup
[0049] CDgroup≡三个AP所覆盖的STA总数量与这三个AP的坐标所组成的三角形的周长的比值。
[0050] 再进一步，第一阶段：采用贪婪法生成初始AP布置方案A1，步骤如下：
[0051] 3.2.1)放置一个AP到未被覆盖的STA密度最大的区域，并将被该AP所覆盖的STA标记为已覆盖；
[0052] 3.2.2)调用算法Algorithm_test测试当前方案是否可行，若是，则转向3.2.3)；若否，则转向3.2.1)；
[0053] 3.2.3)返回初始布置方案A1；
[0054] 第二阶段：移除A1中多余的AP，步骤如下：
[0055] 3.3.1)按每个AP所关联的STA的数量进行升序排序，生成AP队列Qb；
[0056] 3.3.2)按Qb中AP的顺序，逐个尝试删除，每删除一个AP之后，就调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回3.3.1)；若不可行，则将所删除的AP还原并继续尝试删除队列Qb中下一个AP，直至总共|Qb|次删除尝试完成为止；
[0057] 3.3.3)返回A2；
[0058] 第三阶段：将两个距离最近的AP替换为一个，步骤如下：
[0059] 3.4.1)生成 对AP；
[0060] 3.4.2)计算每对AP的STA覆盖密度CDpair；
[0061] 3.4.3)按CDpair的值升序排序以生成替换队列Qc[i]＝{AP i1,AP i2}，其中AP i1和AP i2表示队列Qc中第i对AP中的两个AP，
[0062] 3.4.4)按Qc中AP对的顺序，逐对尝试替换为一个新AP，新AP的位置可在候选位置集Ω中搜索获得，然后，调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回3.4.1)，此时A2中的AP数量减少1个；若不可行，则将所替换的AP对还原，继续尝试替换Qc中下一对AP，如此反复，直至总共|Qc|次替换尝试完成为止；
[0063] 3.4.5)返回A3；
[0064] 第四阶段：将三个邻近的AP替换为两个，过程如下：
[0065] 3.5.1)生成 组AP；
[0066] 3.5.2)计算每组AP的STA覆盖密度CDgroup；
[0067] 3.5.3)按CDgroup的值升序排序以生成替换队列Qd[i]＝{AP i1,AP i2,AP i3}，其中AP i1、AP i2和AP i3表示队列Qd中第i组AP中的三个AP，
[0068] 3.5.4)按Qd中AP组的顺序，逐组尝试替换为两个新AP，两个新AP的位置可在候选位置集Ω中搜索获得，然后，调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回3.5.1)，此时A3中的AP数量减少1个；若不可行，则将所替换的AP组还原，继续尝试替换Qd中的下一对组AP，如此反复，直至总共|Qd|次替换尝试完成为止；
[0069] 3.5.5)返回A4。
[0070] 所述步骤2.1)中，STA‑AP关联过程如下：
[0071] 为了进行STA‑AP关联，首先需要获得信号可以覆盖STA i的AP集合，以A(i)表示；在最初阶段，可初始化每个AP的功率为功率集合P中的最大值以覆盖尽可能多的STA，即AP j的功率初始化为：
[0072] Pj＝max{pq},q∈{1,2,...,|P|},j∈A (7)
[0073] 其中，pq表示P中的第q个功率值；
[0074] 如果STA i和AP j之间的距离di,j小于或等于AP j的通信范围rj，则AP j所发出的信号可以覆盖到STA i，因此，得到：
[0075] A(i)＝{APj|di,j≤rj},i∈S,j∈A (8)
[0076] 在获得集合A(i)之后，将STA i与A(i)中信号最强的AP相关联，在STA‑AP关联之后，可进一步获得与AP j相关联的STA集合S(j)。
[0077] 所述步骤2.2)中，AP功率调整过程如下：
[0078] 每个AP的功率被初始化为集合P中的最大值，但是，最大的功率会导致AP的干扰范围更广，从而使AP之间相互干扰的程度增大，因此，需要向下调整AP的功率以减少它们之间的干扰，以 表示AP j在功率为pq时的通信范围并设p1
[0079]
[0080] 此外，在STA‑AP关联之后，可获得AP和与之关联的STA之间的最大距离为了在覆盖到所有STA的前提下尽可能地降低功率，AP j的功率可调整为：
[0081]
[0082] 在获得Pj之后，j∈A，可以进一步获得AP i和j之间的干扰范围Ii,j，i≠j，这有助于步骤2.3)中的AP信道分配。
[0083] 所述步骤2.3)中，AP信道分配和功率再调整的过程为：
[0084] 网络可在2.4和5GHz两个频段上进行传输，以N(i)表示AP i的相邻AP的集合，N(i)定义为：
[0085] N(i)＝{APj|Di,j≤Ii,j},i,j∈A,i≠j (11)
[0086] 其中，Di,j表示AP i和j之间的距离；
[0087] 对于任何AP i，如果AP j∈N(i)且非重叠信道数量充足，那么我们分配一个不与AP j的信道重叠的信道给AP i，当非重叠信道不足时，分配给AP i的信道可能与AP j的信道重叠，在这种情况下，尽可能降低APi与其相邻AP之间的干扰程度，显然，如果则分配给AP i的信道可以与AP j的相同；
[0088] 引入了一个信道冲突指标CCI，用于度量AP之间的干扰程度，以CCIi表示AP i的干扰程度，它定义为：与AP i的信道属于同一个重叠信道集合的相邻AP的个数。
[0089] 优选的，信道分配的步骤如下：
[0090] 2.3.1)将每个AP的信道编号和CCI值均初始化为0；
[0091] 2.3.2)根据每个AP所关联的STA数量对AP进行降序排序，生成信道分配队列Qa，STA数量最高的AP位于队首；
[0092] 2.3.3)根据队列Qa中AP的顺序逐一为每个AP分配信道，如果当前非重叠信道数量足够多，则将非重叠信道中编号最低的信道分配给当前AP；如果当前非重叠信道不足，则找出使得当前AP及其相邻AP的CCI值增加幅度最小的信道并将之分配给当前AP；
[0093] 2.3.4)在不引起每个AP的CCI值增加的前提下，根据队列Qa中AP的顺序逐一将已分配给AP的信道更新至具有更大带宽的信道；
[0094] 在信道分配后，重新调整AP的功率以增加STA的接收信号强度，对于当前功率pq低于p|P|的每个AP i，我们将其功率从pq提升至pq+1，q∈[1,|P|‑1]，然后判断从AP i以功率pq+1发出的信号是否干扰其他基本服务集，如果是，则不增加该AP的功率；否则，继续将其功率从pq+1调整到pq+2，直到功率值等于p|P|为止。
[0095] 所述步骤2.4)中，STA RU分配的过程如下：
[0096] 802.11ax定义了七种RU类型，这些RU所组成的集合K＝{26,52,106,242,484,996,2×996}，每个信道所包含的k‑tone RU的最大个数由信道带宽bi确定，k∈K，i＝1,2,3,4，其中，b1＝20,b2＝40,b3＝80,b4＝160MHz，在每个OFDMA传输中，20、40、80和160MHz信道中分别最多支持9个，18个，37个和74个STA并行传输；
[0097] k‑tone RU的最大数量由信道带宽决定，k∈K，进行STA RU分配时，需要考虑AP所服务的STA数量以及AP的信道带宽，关注以下两个方面：1)如何尽可能多地利用AP的信道带宽；2)如何尽可能平衡STA的数据速率；对于第一个方面，定义mb个多重RU集合 用于RU分配，b∈B,m＝1,2,…,mb，其中mb是b MHz信道中26‑tone RU的最大数量；每个RU集合中RU的总带宽均尽可能接近于信道带宽b；如对于b＝20MHz，mb＝9的信道，定义RU20,1＝{242}，可分配给1个STA；RU20,2＝{106,106}，可分配给2个STA；…；RU20,9＝{26,26,26,26,26,26,26,26,26}，可分配给9个STA；对于第二个方面，将较大的RU分配给距离AP较远的STA，将较小的RU分配给距离AP较近的STA，对于任何具有信道带宽b的AP i，i∈A，采取以下步骤将RU分配给与其关联的STA：
[0098] 2.4.1)将|S(i)|除以mb，得到商为 余数为rem；
[0099] 2.4.2)当rem不等于零时，将AP i的|S(i)|个STA划分为 组，第x组包含mb个STA， 第 组包含rem个STA；当rem等于零时，将
AP i的|S(i)|个STA划分为S(i)/mb组，每组包含mb个STA；
[0100] 2.4.3)当rem不等于零时，将集合 中的RU分配给第x组的STA，并将RUb,rem中的RU分配给第 组的STA；当rem等于零时，
每个STA均分配一个26‑tone RU；
[0101] 上述各组STA轮流与AP i通信，i∈A。
[0102] 所述步骤2.5)中，获取STA的数据速率的过程如下：
[0103] 根据RSS和STA的RU即可获得STA的数据速率，从IEEE 802.11ax草案中，可以获得接收方最小灵敏度MS和数据速率之间的对应关系，如表1所示：
[0104]最小灵敏度(dBm) 数据速率(Mb/s)
MSb,1 σk,1
MSb,2 σk,2
… …
MSb,X σk,X
[0105] 表1
[0106] 表中，MSb,x表示b MHz信道中的第x个最小灵敏度值，b∈B,x＝1,2,…,X；σk,x表示k‑tone RU中第x个数据速率，k∈K，表1中，MSb,1
[0107] 在WiFi网络中，STA的数据速率由AP的RSS所确定，反之，AP的数据速率由STA的RSS所确定，以RSSi和Ri分别表示AP j从STA i接收到的信号强度和STA i的上行数据速率，i∈S,，根据RSS的值和表1，得到：
[0108]
[0109] 在AP和STA功率相同的情况下，STA的下行数据速率也等于Ri。
[0110] 所述步骤2.6)中，计算STA的吞吐量的过程为：
[0111] 对于信道带宽为b的任意AP j，j∈A，有|S(j)|个STA与之关联，因此，它需要Mj次帧交换以完成一轮通信，即S(j)中每个STA完成一次上行数据传输和一次下行数据接收，Mj的表达式如下：
[0112]
[0113] 以tTF、tSIFS、tUL_PPDU、tM_BA、tDL_PPDU和tOFDMA_BA分别表示TF、SIFS、UL PPDU、M‑BA、DL PPDU和OFDMA‑BA的持续时间，以TUL和TDL分别表示上行和下行传输的持续时间，得到：
[0114] TUL＝tTF+2tSIFS+tUL_PPDU+tM_BA (14)
[0115] 以及
[0116] TDL＝2tSIFS+tDL_PPDU+tOFDMA_BA (15)
[0117] 以Tj表示STA和AP j之间一轮通信的持续时间，则:
[0118] Tj＝(TUL+TDL)Mj (16)
[0119] 因此，得到与AP j关联的STA i的吞吐量为:
[0120]
[0121] 式(17)中，CCIj+1表示AP j及其CCIj个相邻AP相互干扰，也就是说，它们必须轮流传输。
[0122] 本发明中，IEEE 802.11ax是下一代密集WiFi网络标准，该标准采用正交频分多路复用(Orthogonal Frequency Division Multiple Access,OFDMA)技术将无线频谱划分为多个相互独立的资源单元(Resource Unit,RU)，每个RU由不同数量的子载波组成，通过合理分配RU可实现多用户并行传输。为给定区域内的大量用户提供具有服务质量保证的WiFi接入服务，主要目标如下：(1)将AP的数量降至最低；(2)抵抗AP故障；(3)满足用户个性化吞吐量需求。我们将上述内容描述为一个融合AP布置和功率‑信道‑RU分配的优化问题，该问题是NP难的。为了解决该问题，我们首先基于OFDMA机制和基本服务集间的干扰模型，推导出每个用户的吞吐量表达式；然后，设计了一个具有多项式时间复杂度的四阶段启发式算2 2
法，该算法在50×50m的小面积目标区域下可获得问题的最优解；在100×80m的较大面积区域中，与随机法和贪婪法相比，我们的算法所获得的AP数量可减少32～55％。
[0123] 问题可描述为：在一个有许多潜在用户的已知区域中，如体育场，给定一组AP候选位置和一组具有已知位置的STA，通过AP布置和功率‑信道‑RU分配联合设计，找出拟布置AP的位置，同时，所部署的WiFi网络满足以下两个QoS需求：1)失效容忍需求，即当n个AP同时发生故障时，n＝0,1,2,...，与故障AP关联的STA仍可与附近其余AP重新关联以获得WiFi服务；2)个性化吞吐量需求，即位于特定区域，如VIP区域的STA的吞吐量不低于ρH且位于一般区域，如VIP区域之外的STA的吞吐量不低于ρL。此处，ρL和ρH表示吞吐量阈值且ρL<ρH。我们假设ρL是用户可以接受的最低吞吐量，而ρH是令用户满意的最低吞吐量。ρL和ρH的取值可由网络设计人员确定。
[0124] 本发明的主要创新点如下：1)新问题：我们通过融合AP布置和功率‑信道‑RU分配，设计基于802.11ax的密集WiFi网络部署方案。我们将上述问题描述为一个以最小化AP数量为目标，以满足失效容忍和个性化吞吐量需求为约束的优化问题。由于本问题的子问题是NP难的，因此，本问题也是NP难的。2)新解决方案：根据OFDMA机制和信道干扰模型，设计了高效的功率调节、信道分配和RU分配方法，在此基础上，推导出STA的吞吐量表达式。最后，设计一种具有多项式时间复杂度的四阶段启发式算法求解上述优化问题。
[0125] 本发明在满足AP失效容忍需求和用户个性化吞吐量需求的前提下可有效减少802.11ax密集WiFi网络所需的AP数量。
[0126] 本发明的有益效果主要表现在：融合了AP布置和功率‑信道‑RU分配，在满足AP失效容忍和用户个性化吞吐量需求的前提下减少AP数量，从而节约802.11ax密集WiFi网络的部署成本。
附图说明
[0127] 图1是AP与其STA之间的帧交换过程示意图。
[0128] 图2是AP i和j之间的干扰范围示意图。
[0129] 图3是网络使用的信道示意图。
[0130] 图4是CCI示意图。
[0131] 图5是RU的最大数量及其在PPDU中的位置，其中，(a)表示RU的最大数量，(b)表示RU的位置(20MHz)。
[0132] 图6是Algorithm_4stages流程图。
[0133] 图7是目标区域布局和候选AP位置实例。
具体实施方式
[0134] 下面结合附图对本发明作进一步描述。
[0135] 参照图1～图7，一种具有服务质量保证的802.11ax密集WiFi网络AP布置方法，包括以下步骤：
[0136] 1)、问题描述，过程如下：
[0137] 1.1)建立网络模型
[0138] 网络服务的目标区域包含VIP区域和普通区域两个子区域，分别以Vvip和V表示，且以AP表示网络接入点，以STA表示网络站点，以Ω表示AP候选位置集合，该集合是事先已知的，即目标区域Vvip∪V被划分为|Ω|个网格，AP只能布置在网格的中心，在每个网格之内，可以根据STA的密度布置0个、1个或多个AP；网络由如下三种设备组成：网络控制器、AP和STA；网络控制器负责网络的管理和协调，在网络控制器的协调之下，AP在传输数据之前不需要退避；以S和A分别表示STA和AP集合，任意STA i∈S只能与一个AP j∈A关联，当一个AP集合Af满足|Af|<|A|失效时，与故障AP关联的STA可以与其他正常的AP重新关联以获取网络服务，网络采用2.4和5GHz两个频段，在这两个频段中，每个信道的带宽为b MHz，b∈B＝{20,40,80,160}MHz，网络采用OFDMA物理层，在OFDMA中，每个STA在传输数据时不占用整个信道，而是由AP向其分配合适的RU以支持多STA并行传输，每个AP只能分配一个信道，所分配的信道属于一个给定的信道集合C，每个STA只能分配一个j‑tone RU，j∈K＝{26,
52,106,242,484,996,2×996}，其中，K是每个RU中所包含的子载波数目的集合，以P表示AP的功率值集合，每个AP可分配属于P的一个功率值，每个STA所采用的功率与其AP相同；
[0139] 在OFDMA机制之下，AP和STA的帧交换过程如图1所示，其中TXOP、SIFS、M‑BA和OFDMA‑BA分别表示传输机会(Transmission Opportunity,TXOP)、短帧间间隔(Sort Interframe Space)、多STA块确认(Multi‑station Block ACK)和OFDMA块确认(OFDMA Block ACK)；在OFDMA帧交换过程中，STA仅在接收到触发帧(Trigger Frame,TF)之后才开始将上行物理层协议数据单元(Uplink Physical Layer Protocol Data Unit,UL PPDU)传输给其AP，STA在接收到下行PPDU(Downlink PPDU,DL PPDU)之后，将OFDMA‑BA帧回复给其AP；
[0140] 1.2)建立干扰模型
[0141] 以li,j表示节点i和j之间的链路，此处，节点指的是AP或STA；要使节点i通过链路li,j从j正确接收到帧，则节点i从j处的接收信号强度(Received Signal Strength,RSS)必须不低于帧解码阈值θD，在这种情况下，节点i在j的通信范围内，反之亦然；此外，如果节点i和j位于信道相互重叠的不同链路上且i从j接收到的信号强度大于或等于干扰信号强度阈值θI，则节点i会被j干扰；在这种情况下，节点i在j的干扰范围之内，反之亦然；θD>θI，为了获得AP的通信范围和干扰范围，定义以下路径损耗模型：
[0142] RSS＝Pj+GTX‑Plost+GRX (1)
[0143] 其中，
[0144] Plost＝Pref+10lg(dη)+χ (2)
[0145] 在式(1)和(2)中，RSS是接收方的接收信号强度，d是发送方和接收方之间的距离，Pj是发送方j的发射功率，GTX和GRX是发送方和接收方的天线增益，Pref是参照距离(通常为1m)处的路径损耗，η是路径损耗指数，χ是与阴影衰落程度相关的标准差；因此，得到：
[0146]
[0147] 以rj和γj分别表示节点j的通信范围和干扰范围，则：
[0148]
[0149] 由式(1)至(4)以及θD和θI的值，我们可以获得节点的通信范围和干扰范围；
[0150] 接下来介绍网络干扰模型，以li,x和lj,y分别表示AP i和STA x以及AP j和STA y之间的链路。以di,x和dj,y分别表示AP i和STA x以及AP j和STA y之间的距离。以γx和γy分别表示STA x和STA y的干扰范围；图2描述了链路li,x和lj,y的干扰范围，由虚线圆是li,x的干扰范围，实线圆是lj,y的干扰范围；
[0151] 以S(i)和S(j)分别表示与AP i和j相关联的STA集合，根据图2，定义AP i和j之间的干扰距离为：
[0152]
[0153] 如果AP i和j之间的距离小于或等于Ii,j且它们的信道彼此重叠，i≠j，则链路li,x和lj,y相互干扰，即链路li,x和lj,y不能同时传输；
[0154] 1.3)优化问题
[0155] 以δi表示STAi的吞吐量，表述为以下优化问题：
[0156]
[0157] 在约束条件C1中，如果STAi与AP j关联，则指示变量ai,j＝1，否则ai,j＝0。C1表示当|Af|＝n个AP同时失效时，任何STA i∈S都可以与AP j关联以获得WiFi服务，j∈A\Af；在约束条件C2和C3中，在不引起混淆的前提下，STA i既表示第i个STA，也表示该STA位于第i个位置；于是，C2表示当STA i位于VIP区域时，其吞吐量大于或等于ρH；C3表示当STA i位于VIP区域之外时，其吞吐量大于或等于ρL，其中，ρH>ρL；将C1称为失效容忍需求，将C2和C3称为为用户个性化吞吐量需求；
[0158] 2)STA的吞吐量的计算，过程如下：
[0159] 为了求解优化问题(6)需要获得STA的吞吐量，采用Procedure I获得STA的吞吐量；
[0160] Procedure I获得STA的吞吐量的步骤如下：
[0161] 2.1).STA‑AP关联；
[0162] 2.2).AP功率调整；
[0163] 2.3).AP信道分配和功率再调整；
[0164] 2.4).STA RU分配；
[0165] 2.5).获取STA的数据速率；
[0166] 2.6).计算STA的吞吐量；
[0167] 以上6个步骤的具体操作方法如下：
[0168] 所述步骤2.1)中，STA‑AP关联过程如下：
[0169] 为了进行STA‑AP关联，首先需要获得信号可以覆盖STA i的AP集合，以A(i)表示；在最初阶段，可初始化每个AP的功率为功率集合P中的最大值以覆盖尽可能多的STA，即AP j的功率初始化为：
[0170] Pj＝max{pq},q∈{1,2,...,|P|},j∈A (7)
[0171] 其中，pq表示P中的第q个功率值；
[0172] 如果STA i和AP j之间的距离di,j小于或等于AP j的通信范围rj，则AP j所发出的信号可以覆盖到STA i，因此，得到：
[0173] A(i)＝{APj|di,j≤rj},i∈S,j∈A (8)
[0174] 在获得集合A(i)之后，我们将STA i与A(i)中信号最强的AP相关联，在STA‑AP关联之后，可进一步获得与AP j相关联的STA集合S(j)；
[0175] 所述步骤2.2)中，AP功率调整过程如下：
[0176] 如前所述，每个AP的功率被初始化为集合P中的最大值，但是，最大的功率会导致AP的干扰范围更广，从而使AP之间相互干扰的程度增大。因此，我们需要向下调整AP的功率以减少它们之间的干扰，以 表示AP j在功率为pq时的通信范围并设p1
[0177]
[0178] 此外，在STA‑AP关联之后，可获得AP和与之关联的STA之间的最大距离为了在覆盖到所有STA的前提下尽可能地降低功率，AP j的功率可调整为：
[0179]
[0180] 在获得Pj(j∈A)之后，可以进一步获得AP i和j之间的干扰范围Ii,j，i≠j，这有助于步骤2.3)中的AP信道分配；
[0181] 所述步骤2.3)中，AP信道分配和功率再调整的过程为：
[0182] 网络可在2.4和5GHz两个频段上进行传输，所使用的具体信道如图3所示，即信道集合C＝{1，2,...,19}；
[0183] 在图3中，信道12与信道2和3重叠，因此，在2.4GHz频段中定义两个重叠信道集合(Overlapping Channel Set,OCS)，分别以Γ1＝{2,12}和Γ2＝{3,12}表示，类似地，在5GHz频段中定义了8个OCS，分别以Γ3＝{4,13,17,19}、Γ4＝{5,13,17,19},…,Γ10＝{11,16,18,19}等表示，将信道1至11称为基础信道；
[0184] 以N(i)表示AP i的相邻AP的集合，N(i)定义为：
[0185] N(i)＝{APj|Di,j≤Ii,j},i,j∈A,i≠j (11)
[0186] 其中，Di,j表示AP i和j之间的距离；
[0187] 对于任何AP i，如果AP j∈N(i)且非重叠信道数量充足，那么分配一个不与AP j的信道重叠的信道给AP i，当非重叠信道不足时，分配给AP i的信道可能与AP j的信道重叠，在这种情况下，尽可能降低AP i与其相邻AP之间的干扰程度，显然，如果 则分配给AP i的信道可以与AP j的相同；
[0188] 引入了一个信道冲突指标(Channel Conflict Indicator,CCI)，用于度量AP之间的干扰程度，以CCIi表示AP i的干扰程度，它定义为：与AP i的信道属于同一个重叠信道集合OCS的相邻AP的个数；如图4(a)所示，图中，圆表示AP，圆中心的数字表示信道编号，由边连接的两个AP彼此相邻；例如，在图4(a)中，我们拟为AP 1分配信道，其信道编号初始化为0；假设当前信道数量不足，即只能从{5,13,14,17}中选择一个分配给AP 1；考虑到5,13,17∈Γ4，我们可将14分配给AP 1，见图4(b)；原因如下：若将5,13,17中的任意一个信道，如将
17分配给AP 1，则AP 1及其相邻AP的CCI值都将显著增加，这会导致AP之间干扰程度更加严重，见图4(c)；
[0189] 信道分配的步骤如下：
[0190] 2.3.1)将每个AP的信道编号和CCI值均初始化为0；
[0191] 2.3.2)根据每个AP所关联的STA数量对AP进行降序排序，生成信道分配队列Qa，STA数量最高的AP位于队首；
[0192] 2.3.3)根据队列Qa中AP的顺序逐一为每个AP分配信道。如果当前非重叠信道数量足够多，则将非重叠信道中编号最低的信道分配给当前AP；如果当前非重叠信道不足，则找出使得当前AP及其相邻AP的CCI值增加幅度最小的信道并将之分配给当前AP；
[0193] 2.3.4)在不引起每个AP的CCI值增加的前提下，根据队列Qa中AP的顺序逐一将已分配给AP的信道更新至具有更大带宽的信道。
[0194] 在信道分配后，重新调整AP的功率以增加STA的接收信号强度。对于当前功率pq低于p|P|的每个AP i，将其功率从pq提升至pq+1(q∈[1,|P|‑1])，然后判断从AP i以功率pq+1发出的信号是否干扰其他基本服务集BSS，如果是，则不增加该AP的功率；否则，继续将其功率从pq+1调整到pq+2，直到功率值等于p|P|为止。
[0195] 所述步骤2.4)中，STA RU分配的过程如下：
[0196] 802.11ax定义了七种RU类型，这些RU所组成的集合K＝{26,52,106,242,484,996,2×996}。每个信道所包含的k‑tone RU的最大个数如图5(a)所示，k∈K，由信道带宽bi确定，i＝1,2,3,4，其中b1＝20,b2＝40,b3＝80,b4＝160(MHz)。这意味着，在每个OFDMA传输中，20、40、80和160MHz信道中分别最多支持9个，18个，37个和74个STA并行传输。图5(b)显示了20MHz PPDU中各RU的位置。40、80和160MHz PPDU中的RU位置可参见802.11ax草案。
[0197] 如图5所示，k‑tone RU的最大数量由信道带宽决定，k∈K，进行STA RU分配时，需要考虑AP所服务的STA数量以及AP的信道带宽，主要关注以下两个方面：1)如何尽可能多地利用AP的信道带宽；2)如何尽可能平衡STA的数据速率。对于第一个方面，定义mb个RU多重集合 用于RU分配，b∈B,m＝1,2,…,mb，其中mb是b MHz信道中26‑tone RU的最大数量。每个RU集合中RU的总带宽均尽可能接近于信道带宽b；例如，根据图5(b)，对于b＝20MHz，mb＝9的信道，定义RU20,1＝{242}，可分配给1个STA；RU20,2＝{106,106}，可分配给2个STA；…；RU20,9＝{26,26,26,26,26,26,26,26,26}，可分配给9个STA。对于第二个方面，将较大的RU分配给距离AP较远的STA，将较小的RU分配给距离AP较近的STA。具体来说，对于任何具有信道带宽b的AP i，i∈A，采取以下步骤将RU分配给与其关联的STA，STA RU分配的步骤如下：
[0198] 2.4.1)将|S(i)|除以mb，得到商为 余数为rem；
[0199] 2.4.2)当rem不等于零时，将AP i的|S(i)|个STA划分为 组。第x组包含mb个STA， 第 组包含rem个STA；当rem等于零时，将
AP i的|S(i)|个STA划分为S(i)/mb组，每组包含mb个STA；
[0200] 2.4.3)当rem不等于零时，将集合 中的RU分配给第x组的STA，并将RUb,rem中的RU分配给第 组的STA；当rem等于零
时，每个STA均分配一个26‑tone RU。
[0201] 上述各组STA轮流与AP i通信，i∈A。
[0202] 所述步骤2.5)中，获取STA的数据速率的过程如下：
[0203] 根据RSS和STA的RU即可获得STA的数据速率。从IEEE 802.11ax草案中，可以获得接收方最小灵敏度(Minimum Sensitivity,MS)和数据速率之间的对应关系，如表1所示：
[0204]最小灵敏度(dBm) 数据速率(Mb/s)
MSb,1 σk,1
MSb,2 σk,2
… …
MSb,X σk,X
[0205] 表1
[0206] 表中，MSb,x表示b MHz信道中的第x个最小灵敏度值，b∈B,x＝1,2,…,X；σk,x表示k‑tone RU中第x个数据速率，k∈K。上表1中，MSb,1
[0207] 在WiFi网络中，STA的数据速率由AP的RSS所确定，反之，AP的数据速率由STA的RSS所确定，以RSSi和Ri分别表示AP j从STA i接收到的信号强度和STA i的上行数据速率，i∈S，根据RSS的值和表1，得到：
[0208]
[0209] 在AP和STA功率相同的情况下，STA的下行数据速率也等于Ri。
[0210] 所述步骤2.6)中，计算STA的吞吐量的过程为：
[0211] 对于信道带宽为b的任意AP j，j∈A，有|S(j)|个STA与之关联，因此，它需要Mj次帧交换以完成一轮通信，即S(j)中每个STA完成一次上行数据传输和一次下行数据接收，Mj的表达式如下：
[0212]
[0213] 以tTF、tSIFS、tUL_PPDU、tM_BA、tDL_PPDU和tOFDMA_BA分别表示TF、SIFS、UL PPDU、M‑BA、DL PPDU和OFDMA‑BA的持续时间。以TUL和TDL分别表示上行和下行传输的持续时间，根据图1，得到：
[0214] TUL＝tTF+2tSIFS+tUL_PPDU+tM_BA (14)
[0215] 以及
[0216] TDL＝2tSIFS+tDL_PPDU+tOFDMA_BA. (15)
[0217] 以Tj表示STA和AP j之间一轮通信的持续时间，则:
[0218] Tj＝(TUL+TDL)Mj (16)
[0219] 因此，得到与AP j关联的STA i的吞吐量为:
[0220]
[0221] 式(17)中，CCIj+1表示AP j及其CCIj个相邻AP相互干扰，也就是说，它们必须轮流传输。
[0222] 3)启发式算法
[0223] 由于我们的问题的子问题，如最优AP布置和信道分配等是NP难的，因此，我们的问题也是NP难的，因此，设计了一个多项式时间启发式算法求解该问题。
[0224] A表示AP集合，实际上，A也可以表示具体的AP布置方案，这不会引起混淆，由四个阶段组成，每个阶段的关键操作是测试当前的AP布置方案A是否可行，因此，首先设计了算法Algorithm_test进行可行性测试。
[0225] Algorithm_test:可行性测试，输入：A,S,Ω,P,C,n等；输出：指示变量I，I＝TRUE表示A可行，I＝FALSE表示A不可行，测试过程如下：
[0226] 3.1.1)将I置为TRUE；
[0227] 3.1.2)判断优化问题(6)的约束条件C1是否能满足，若是，则转向3.1.3)；若否，则置I为FALSE并转向3.1.4)；
[0228] 3.1.3)在A中删除n＝|Af|个AP，表示有n个AP失效，再调用Procedure I以获得STA的吞吐量，然后，判断优化问题(6)的约束条件C2和C3是否能满足，若在 种AP失效情形下方案A都能满足C2和C3，则转向3.1.4)；若 种AP失效情形中有任意一种情形不能满足C2和C3，则置I为FALSE并转向3.1.4)；
[0229] 3.1.4)返回I的值。
[0230] 接着，设计四阶段启发式算法Algorithm_4stages求解优化问题(6)，过程如下：第一阶段：采用贪婪法生成初始AP布置方案A1；第二阶段：移除A1中多余的AP；第三阶段：迭代地将两个距离最近的AP替换为一个；第四阶段：迭代地将三个邻近的AP替换为两个；
[0231] 在第三和第四阶段中，需要计算每对AP或每组AP的STA覆盖密度(CoverageDensity,CD)，此处，先给出CD的定义。
[0232] 定义1：每对AP的覆盖密度CDpair
[0233] CDpair≡两个AP所覆盖的STA总数量与这两个AP的距离的比值
[0234] 定义2：每组AP的覆盖密度CDgroup
[0235] CDgroup≡三个AP所覆盖的STA总数量与这三个AP的坐标所组成的三角形的周长的比值
[0236] 算法Algorithm_4stages的主要过程如下：
[0237] 输入：S,Ω,P,C,n等
[0238] 输出：AP布置方案A4
[0239] 第一阶段：采用贪婪法生成初始AP布置方案A1
[0240] 3.2.1)放置一个AP到未被覆盖的STA密度最大的区域，并将被该AP所覆盖的STA标记为已覆盖；
[0241] 3.2.2)调用算法Algorithm_test测试当前方案是否可行，若是，则转向3.2.3)；若否，则转向3.2.1)；
[0242] 3.2.3)返回初始布置方案A1；
[0243] 第二阶段：移除A1中多余的AP，步骤如下：
[0244] 3.3.1)按每个AP所关联的STA的数量进行升序排序，生成AP队列Qb；
[0245] 3.3.2)按Qb中AP的顺序，逐个尝试删除，每删除一个AP之后，就调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回3.3.1)；若不可行，则将所删除的AP还原并继续尝试删除队列Qb中下一个AP，直至总共|Qb|次删除尝试完成为止；
[0246] 3.3.3)返回A2。
[0247] 第三阶段：将两个距离最近的AP替换为一个，步骤如下：
[0248] 3.4.1)生成 对AP；
[0249] 3.4.2)计算每对AP的STA覆盖密度CDpair；
[0250] 3.4.3)按CDpair的值升序排序以生成替换队列Qc[i]＝{AP i1,AP i2}，其中AP i1和AP i2表示队列Qc中第i对AP中的两个AP，
[0251] 3.4.4)按Qc中AP对的顺序，逐对尝试替换为一个新AP，新AP的位置可在候选位置集Ω中搜索获得，然后，调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回3.4.1)，此时A2中的AP数量减少1个；若不可行，则将所替换的AP对还原，继续尝试替换Qc中下一对AP。如此反复，直至总共|Qc|次替换尝试完成为止；
[0252] 3.4.5)返回A3。
[0253] 第四阶段：将三个邻近的AP替换为两个，过程如下：
[0254] 3.5.1)生成 组AP；
[0255] 3.5.2)计算每组AP的STA覆盖密度CDgroup；
[0256] 3.5.3)按CDgroup的值升序排序以生成替换队列Qd[i]＝{AP i1,AP i2,AP i3}，其中AP i1、AP i2和AP i3表示队列Qd中第i组AP中的三个AP，
[0257] 3.5.4)按Qd中AP组的顺序，逐组尝试替换为两个新AP，两个新AP的位置可在候选位置集Ω中搜索获得，然后，调用算法Algorithm_test对当前方案进行可行性测试，若可行，则返回步骤1，此时A3中的AP数量减少1个；若不可行，则将所替换的AP组还原，继续尝试替换Qd中的下一对组AP。如此反复，直至总共|Qd|次替换尝试完成为止；
[0258] 3.5.5)返回A4。
[0259] 事实上，可以继续尝试通过替换x个AP为x‑1个以进一步减少AP的数量，x＝4,5,…，但是，这样处理的必要性并不大，原因如下：(1)继续替换下去算法的时间复杂度较高；(2)上述四阶段算法Algorithm_4stages已经能够获得优化问题(6)的近似解。
[0260] 综上所述，所提出的四阶段启发式算法Algorithm_4stages的流程图如图6所示。简单地说，算法Algorithm_4stages包含四个阶段，每个阶段均会调用算法Algorithm_test进行方案可行性测试，而算法Algorithm_test在执行过程中又调用了Procedure I以获得STA的吞吐量。
[0261] 实施实例主要参数设置如表2所示：
[0262]
[0263] 表2
[0264] 此外，目标区域可根据实际情况而定，以一个体育场为例，其区域布局和候选AP位置如图7所示，可知|Ω|＝50。从图7可以看到，为了提供用户个性化服务，我们在VIP区域设置了相对更密集的AP候选位置，这会使算法Algorithm_4stages更倾向于在VIP区域中布置更多的AP以提供个性化吞吐量服务。
[0265] 本说明书的实施例所述的内容仅仅是对发明构思的实现形式的列举，仅作说明用途。本发明的保护范围不应当被视为仅限于本实施例所陈述的具体形式，本发明的保护范围也及于本领域的普通技术人员根据本发明构思所能想到的等同技术手段。
