基于图转换的无线接入点关联优化算法

陶雯，沈艳，管昕洁，万夕里

（1．江苏第二师范学院数学与信息技术学院，江苏 南京 210013；2．南京工业大学计算机科学与技术学院，江苏 南京 211816）

基于图转换的无线接入点关联优化算法

陶雯1，沈艳2，管昕洁2，万夕里2

（1．江苏第二师范学院数学与信息技术学院，江苏 南京 210013；2．南京工业大学计算机科学与技术学院，江苏 南京 211816）

无线接入点关联是 Wi-Fi系统中的一个基础问题。已有的研究主要集中在考虑带宽容量约束条件下的各种AP关联问题。这些研究没有从用户的角度考虑带宽需求，从用户的带宽需求出发，以最多带宽分配的AP关联为优化目标，考虑混合型网络架构下的Wi-Fi系统的无线接入点关联优化问题。与已有研究方法不同，通过图转换技术，并将问题转化为流图上的优化问题，提出基于网络流的优化求解算法，并从理论上证明算法的最优性。最后，通过对比实验进一步证明了算法的优越性。

无线接入；图转换；接入点关联

1 引言

IEEE 802.11技术（通常称为Wi-Fi）因其具有高带宽、低成本等优势，随着社会的发展，基于IEEE 802.11协议系列的无线局域网已在校园、工厂等各种场景下不断得到部署。智能设备的普及更进一步推动了 Wi-Fi的普及，并深入人们的生活和工作的各个方面。在企业层面，面向不同应用的 Wi-Fi应用系统不断被推出。尽管 Wi-Fi技术有着很多优点，随着其大规模的应用，其本身也面临很多技术上的挑战，如带宽优化、接入点的最优放置等问题。在这些挑战中，如何在给定 Wi-Fi系统资源的前提下，使得系统能够服务更多用户是实际应用中经常考虑的一个重要问题。对该问题的深入研究，可以进一步提高Wi-Fi系统在实际应用的利用效率。

近年来，随着Wi-Fi的不断普及，Wi-Fi在企业级别也有了广泛的应用。如在机场、校园校区、商场等规模较大的公共区域，Wi-Fi基本实现全覆盖。在这类型的Wi-Fi系统中，多个AP通过高速有线网络连接到中央控制节点，这种混合型结构一般被称为半集中式结构[1]。在这种混合型结构下，多个 AP之间可以通过骨干有线网络来分享接入设备相关信息，这使得系统可以及时集中收集当前在各个 AP信号范围内的用户信息，使得中央控制节点拥有全局视图，为设计 Wi-Fi资源分配提供有利条件。

本文将研究在这一混合型架构下的 Wi-Fi中最大带宽分配的AP关联问题。已有一些研究[1-3]探讨了该AP关联问题。这些研究主要研究在带宽容量约束条件下，如何寻求带宽分配最多的一种AP关联方案。但这些研究并没有考虑到用户的带宽需求，随着移动互联网的发展，为了获得更好的用户网络体验，如上网、打游戏以及看视频等，用户对所分配到的带宽有着一定的要求。基于此，本文考虑从用户带宽需求出发，研究该需求下的最大带宽分配的AP关联优化问题。参考文献[1]首先考虑了该问题，研究了单元带宽需求下的最大带宽分配的 AP关联优化，给出一个贪婪启发式算法来求解该问题，但该算法并不能求得该问题的最优解。已有的关于带宽分配的 AP关联问题基本都是 NP难问题，而且主要是应用线性、非线性规划等相关方法来设计启发式算法或者近似算法。与已有研究的方法不同，本文提出用图的优化理论来解决此类问题，并探讨在某些条件下存在最优解的可能性。本文给出了在每个设备需求是单元带宽的假设下，在基于图的最优化网络流理论基础上，发现最大带宽分配的 AP关联优化存在最优解，理论证明和实验结果也进一步验证了该算法的正确性。

2 相关工作

随着当前接入 Wi-Fi用户数目大量增长以及多层次结构的 Wi-Fi系统的部署，提升系统利用效率和接纳更多用户请求的问题越发具有挑战性。为解决此问题，学术界提出了各种场景下，面向不同优化目标的资源调度和分配关联算法。参考文献[1]提出了面向带宽分配的 AP关联分配算法。参考文献[2]建模 AP关联问题，并考虑负载均衡因素，通过松弛和取整的方法，设计了一个具有常数倍逼近度的分配算法。参考文献[4]提出了基于最少负载优先设备关联的启发式算法，也就是设备优先选择负载最小的 AP接入。参考文献[5]考虑了 AP可以再关联的优化问题，提出了在迁徙约束条件下的面向最大吞吐量的优化算法。参考文献[6]提出了基于可用容量的负载均衡的AP关联算法。

其他学者从均衡用户分配的资源的思路出发，提出了多种关联算法。参考文献[3]研究了多种异构客户场景（IEEE 802.11a/b/g/n）下，通过二维马尔可夫模型预测设备的上下行吞吐量，在此基础上，以提高 MAC效率为目标，考虑平衡带宽和速率，建模在线 AP关联问题并提出一种在线 AP关联方法。参考文献[7]考虑了单个设备可关联多个 AP的情况，并提出最优的面向多个AP传输速率策略，并从理论上证明该算法的逼近度为4+∈。参考文献[8]提出了度量驱动的WLAN设计原则，并以此为指导优化信道分配、AP关联和AP功率控制等。参考文献[9, 10]研究了在软件定义的WLAN框架下的AP关联问题，考虑了帧延迟、数据分组丢失等多种因素，提出面向服务质量保证的AP关联方法。参考文献[11]提出集中式的AP关联策略模型，并应用蚁群算法求解AP关联解。

3 网络模型与问题描述

3.1 网络模型与定义

图1 3个AP和4个移动设备

假设 APi的带宽容量为 Ci，并且任何移动设备只需要 AP能满足其最小的带宽即可关联该AP。定义Li为第i个AP的负载。为了方便，与已有研究一样[1]，本文假设每个移动设备只需要候选AP满足1个单元的带宽要求，即可关联该AP。因此，第APi的负载Li为该AP关联的移动设备的数目，而每个 APi的容量 Ci则为该APi能关联的移动设备最大数目。因此，在此假设下，最终所有关联上的设备所获得的总带宽与设备总的连接数等价。

如果设备dj关联到APi，定义aij=1，否则aij=0。此外，本文也用 〈uj,vi〉 配对来表示设备j关联到APi。

3.2 问题描述

定义1（最大AP关联问题）给定一个混合型Wi-Fi网络，该网络有n个AP节点和m个移动设备节点。假设每个移动设备候选的AP节点是已知的，最大AP关联问题就是求解一种AP关联算法使得最终网络中AP所关联的设备数目最多。

图2 图1对应的流图G′

定义3如果一个AP关联方案满足式（2）、式（3），则称该关联方案为最大 AP关联问题的可行解。

4 算法设计与分析

本节给出求解最大关联问题的最优算法以及相关最优性的证明和分析。该算法的思路是将该AP关联问题转化为图上的优化问题，从而应用图的优化理论来求解最优解。首先将最大 AP关联问题转化为二分图上的优化问题，然后给出优化算法来求解该优化问题。

值得注意的是，本文中的最大AP关联问题不能采用经典的二分匹配算法来求解，因为对于每一个AP节点（即二分图中U中的节点）是可以关联多于一个的移动设备（即二分图中V中的一个节点），而二分匹配问题中 U有且仅能与 V中一个节点匹配。未解决此问题，本文提出一种图转换方法，将最大AP关联优化问题转化为对应的图优化问题，从而可以应用网络流优化算法取得最优解。

4.1 基于网络流的AP关联算法

首先本文给出如何构造最大 AP关联问题二分图：创建一个二分图，对每个APi节点和移动设备dj，分别在U和D中创建一个节点i和j。如果移动设备j在APi的覆盖范围内，也就是APi是移动设备dj的候选节点，则在E中创建一条从i 到j的有向边(i, j)，并设置(i, j)的权重为

下面给出基于网络流的最大AP关联算法。

算法1 基于网络流的AP关联算法

输入：AP集合U，移动设备集合U，每个移动设备的候选AP集合。

输出：一组移动设备关联AP的解＜aij＞。

步骤2在G的基础上建立流图G'（如图2所示），在上额外添加一个虚拟源点S和终点T，对U中的每个顶点i，连接源点S与顶点i形成有向边(S, i)，设置该边的权重为Ci；对V中顶点j，连接j与终点T形成有向边 (j,T) ，并设置该边的权重为W(j,T)=1。

步骤 3应用经典最大网络流 Push-Relabel算法[14,15]在新构造的流图G'上，求解出G'上的最大流 f'。用表示最大流解f'在边(i, j)最大流。

步骤4如果则赋值aij=1，即将移动设备dj关联到APi。

4.2 算法分析

引理1在图2中，若所求得的从源点S到终点T 的最大流经过边则该边对应的最大流必定为1，即

证明：根据网络流整数流性质[12]，如果网络中所有边的权重（或者容量）为整数，则该网络的最大流一定为整数流。算法1中所构造的流图G'的边的权重均为整数，因此最大流经过一定是整数。又因为(ui, dj)边的权重均为 1，所以(ui, dj） 若有最大流经过，其最大流必定为1，即

引理2对于任何dj∈D节点，若一个从源点 S到终点 T 的流经过该节点，则

证明：对于任何dj∈D 节点, 因为 (dj,T)的权重为 1，根据网络流平衡性质[13]，任何流入 dj的流的总和一定为1，因此引理得证。

定理1如果有一个可行性解Γ中，有k个移动设备与APi节点关联，则对应流图G'上存在一个从源点S到终点t的流，且该流值为k。反之亦成立。

证明：一个可行解Γ中有k个移动设备与APi关联，则在流图G'上可以存在k条边的流值为1。因为源点S与每个ui相连，并且每个dj与终点T相连，根据网络流平衡性质[13]，必定存在从源点S到终点T的流f，且f通过这k条边，且该流值为f( s, t)。又因为可行解Γ满足式（2），也就是可行解满足每个 AP的容量约束条件，而边上的权重则对应AP 的容量，因此，该流f一定满足流图G'上的权重限制条件。

反之，对于一个流值为k的从源点S到终点T的流值f( s, t)，结合引理1和引理2，可知对于任何dj∈D节点，只有一条从ui∈D出发的边的流经过 dj，且 f( ui, dj)=1。因为 f(s,t)=k，根据流平衡性质，则必定有k条(ui, dj)边的流值为1。也就是有k条 f( ui, dj) =1，对应于k个移动设备与AP节点关联的方案，并且该方案满足式（3）。又因为(s, ui)边的权重对应于AP的容量约束，所以该关联方案满足式（2），因此该关联方案是一个有k个移动设备被关联的可行解。

定理 2最大 AP关联问题可以转化为流图G'上的最大网络流问题。

证明：定理1揭示了单个AP关联问题的可行解与流图G'上的单源单汇流一一对应关系，并且可行解的值对应于图G'的流值。值得注意的是，最大AP关联问题的解是由一系列可行解构成，且最大带宽AP关联问题的设备连接数值是这些可行解相应的设备连接数值之和。从而，最大AP关联问题的解值（设备连接数目）对应于流图G'上的所有的单源单汇流值之和，也就是对应于流图G'上的从源点S出发到终点T的网络流。因此，最大AP关联问题解的最大值对应流图G'上的最大网络流。定理3最大AP关联问题可以在时间内求的最优解。

证明：算法1的复杂度是由最大网络流算法主导，因此网络流算法的复杂度决定了算法1的复杂度。如果采用经典的Push-Relabel算法[14,15]，则算法1复杂度为中，r为流图G'中节点的个数。因此算法1的复杂度为

4.3 示例

本节给出一个示例来演示算法 1。针对图 1中的部署场景，假定每个AP的容量为2，也就是根据算法步骤1和步骤2，可以得到图2中的流图G'。在图2中，分别对应于3个AP，则对应于4个移动设备。G'中依附在边上的数值对应于边的权重，其中对每个其他边的权重均为1。

应用最大网络流算法，可求得该流图G'的最大流f =4，如图3所示，加粗的边为网络最大流经过的边，依附在边上加粗的数字则表示最大流经过该边的流值，如边(s, u1)的流的值为2，也就是根据算法1的步骤4，任何边上流的值为1，则关联APi和移动设备dj。因此，从最大流流经边的结果可以得到：AP1与移动设备d1和d2关联，AP2和移动设备d3关联， AP3和移动设备d4关联。

图3 图2对应的流图G′的最大网络流

5 实验与分析

5.1 实验参数设置

为进一步验证本文所提算法的性能，通过实验与参考文献[1]中提出的贪婪算法对比，通过对AP的关联设备数目、AP关联数目的分布以及AP的利用率对比，对算法性能进行实验分析和评估。

实验中有n个AP节点，m个移动设备。每个AP节点的容量是C，实验中假设每个AP节点的带宽容量相同。本实验通过 AP关联移动设备数目来判断本文所提出的算法的有效性和合理性。

为了更全面地突出本文算法的有效性，从以下几个方面进行了仿真实验。

（1）固定AP节点的数量为5，且每个AP节点的带宽容量为5，设置不同的移动设备数量，分别为10、15、20，随机运行10次，比较本文算法与贪婪算法的实验结果。

（2）固定移动设备数为10，每个AP节点的带宽容量为5，设置不同的AP节点数，分别为5、6、7，随机运行10次，将本文提出的算法与贪婪算法进行比较。

（3）固定AP节点数量为5，且每个AP节点的带宽容量为5，改变移动设备的数量，分别为5、10、15、20、25、30、35、40、45、50，比较这两个算法的结果。

（4）固定AP节点数为6，设置不同的AP节点的带宽容量，分别为5、6、7，随着移动设备逐次增加的情况下（移动设备数量分别为5、10、15、20、25、30、35、40、45、50），比较本文提出的算法与贪婪算法的实验结果。

（5）比较两算法在3种不同的 AP节点数和移动设备数的条件下，AP节点与移动设备连接分布情况。

（6）在AP节点数为5，容量为5的条件下，随着移动设备数量逐次增加，对两个算法中 AP节点的利用率进行了比较。

5.2 实验结果

根据要求设置参数，进行仿真实验。在实验中将本文的优化算法与已有的贪婪算法进行比较。针对本文求最大AP联结数的问题，使用贪婪算法将其分成每个AP节点尽可能多地连接移动设备的子问题。在给定的一个部署场景中，将每个AP节点与移动设备连接的数量按降序排列，在确保每个移动设备只连接一个AP节点的条件下，按之前排列的顺序依次留下原部署场景中的AP节点与移动设备的连接状态，最后计算得到AP联结数。

本文首先设置AP节点的数量为5，每个AP节点的容量为5。然后，设置不同的移动设备数量，分别运行基于网络流的AP关联算法和贪婪算法。运行10次，并且将每次这两个算法生成的AP关联设备的数目进行比较。图4给出了当移动设备数量为10、15、20时的比较结果，可以看出，使用基于网络流AP关联算法得到的AP关联数普遍高于贪婪算法。

图4 AP节点数为5，不同移动设备数量下运行10次的AP关联数

接下来，设置移动设备数量为10，每一个AP节点的容量为5，对不同数量的AP节点分别运行基于网络流 AP关联算法和贪婪算法，每一组实验运行10次，对两个算法生成的AP关联设备的数目进行比较。图5给出了AP节点数为5、6、7时的比较结果。从图5可以看出，基于网络流AP关联算法生成的 AP关联设备的数目总是大于贪婪算法的，且大多数时候是远大于贪婪算法的。这个结果与本文算法结论一致，有效验证了本文算法的性能高于贪婪算法性能。

图5 移动设备数为10、AP节点数不同时运行10次的AP关联数

为了更进一步验证本文算法的有效性，还进行了如下实验，设置AP节点数为5，且每个AP节点的容量为 5，移动设备数量依次为 5、10、15、20、25、30、35、40、45、50，分别观察两种算法运行下生成的 AP关联设备的数目，结果如图6所示。可以看到，在相同的AP数量和移动设备数量下，基于网络流 AP关联算法得到的AP关联数始终大于贪婪算法得到的AP关联数，如此进一步验证了所提算法更为有效性。

另外，还改变 AP节点的容量值进行两个算法的对比实验。实验中设置AP节点的数量为6。然后设置不同的 AP节点容量，分别运行基于网络流AP关联算法和贪婪算法，在移动设备数量逐次增加的情况下比较两种算法生成的 AP关联设备的数目。图7给出了当AP节点容量为5、6、7时的比较结果。可以看到，在 AP节点数为6，且移动设备数量相同的时候，基于网络流AP关联算法得到的AP联结数大多数时候大于贪婪算法得到的AP联结数。另外还可以发现，在同一场景部署下，当该环境中的AP节点容量增大时，本文所提出的算法的性能明显优于贪婪算法。

图6 AP节点数为5，随着移动设备数量增加生成的AP关联数

图7 AP节点数量为6时，不同容量下随着移动设备数量增加生成的AP关联数

接下来，分别运行基于网络流AP关联算法和贪婪算法，比较3种不同的AP节点数和移动设备数的条件下 AP节点与移动设备连接分布情况。图8给出了AP节点数为5，且每个AP节点的容量为5，移动设备数为10的情况下，AP连接数的分布情况。从图8中可以看出，在基于网络流AP关联算法中每个AP节点都连接着相应数量的移动设备，而贪婪算法下第 3个AP节点、第4个AP节点和第5个AP节点都没有与移动设备相连接。所以很明显地得出本文提出的算法更为有效。另外，本文还分别进行了AP节点数为6，且每个AP节点的容量为5，移动设备数为15和AP节点数为7，且每个AP节点的容量为5，移动设备数为20的实验。结果分别显示在图9和图10中。结果与上述结论保持一致。

图8 AP节点数为5，移动设备数为10的AP连接数分布

图9 AP节点数为6，移动设备数为15的AP连接数分布

此外，本文还对两个算法中AP节点的利用率进行了比较。图11给出了AP节点为5，且每个 AP节点的容量为5，移动设备数量逐量递增的条件下两算法中AP 节点的利用率情况。可以看出，基于网络流的AP关联算法下所得到的AP利用率一直高于贪婪算法，而且大部分情况下，AP利用率为100%。由此可以看出，本文提出的算法在AP利用情况上比贪婪算法更为高效。

图10 AP节点数为7，移动设备数为20的AP连接数分布

图11 AP节点数量为5，容量为5时随着移动设备数量增加生成的AP利用率

6 结束语

本文提出了在混合型架构下的一种面向最大连接数的AP关联算法。与已有AP关联方法不同，本文应用图优化方法来设计 AP关联算法，提出图转换技术，设计流图，将该 AP关联优化问题转化为流图上网络流优化问题，并从理论上证明了两个问题的等价性。在此基础上，应用网络流算法，提出基于网络流算法的最优AP关联算法。通过仿真实验，验证了该算法的有效性。

[1] DANDAPAT S K, MITRA B, CHOUDHURY R R, et al. Smart association control in wireless mobile environment using max-flow[J]. IEEE Transactions on Network and Service Man-agement, 2012, 9(1): 73-86.

[2] BEJERANO S J Y, HAN S J，LI L E. Fairness and load balancing in wireless LAN using association control[M]. New Jersey: IEEE Press, 2007: 560-573.

[3] GONG D, YANG Y. On-line AP association algorithms for 802.11n WLANs with heterogeneous clients [J]. IEEE Transactions on Computers, 2014, 63(11): 2772-2786.

[4] GONG H, KIM J. Dynamic load balancing through association control of mobile users in Wi-Fi networks[J]. IEEE Transactions on Consumer Electronics, 2008, 54(2): 342-348.

[5] WONG W. THAKUR A, CHAN S H G. An approximation algorithm for AP association under user migration cost constraint[C]//The 35th Annual IEEE International Conference on Computer Communications, April 10-15, 2016, San Francisco,USA. New Jersey: IEEE Press, 2016: 56-62.

[6] MURTY R , PADHYE J, CHANDRA R, et al. Designing high performance enterprise Wi-Fi networks[C]//The 5th USENIX Symposium on Networked Systems Design and Implementation,Alaska, USA, 2008: 342-349.

[7] ABUSUBAIH M, WOLISZ A. An optimal station association policy for multi-rate IEEE 802.11 wireless Lans [C]//The 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, October 22-26, 2007, Chania,Crete Island, Greece. New York: ACM Press, 2007: 34-40.

[8] BROUSTIS I, PAPAGIANNAKI K, KRISHNAMURTHY S,et al. Measurement-driven guidelines for 802.11 WLAN design[J]. IEEE/ACM Transactions on Networking, 2010,18(3): 722-735.

[9] SOOD K, LIU S, YU S, et al. Dynamic access point association using software defined networking[C]//2015 International Telecommunication Networks and Applications Conference, Nov 18-20, 2015, Sydney, Australia. New Jersey: IEEE Press, 2015:230-238.

[10] CHEN J, LIU B, ZHOU H, et al. QoS-driven efficient client association in high-density software defined WLAN [J]. IEEE Transactions on Vehicular Technology, 2017, PP(99): 1-2.

[11] 李克, 王换招, 张鹏, 等.一种用户需求感知的无线接入点关联策略[J]. 软件学报, 2015, 26(2): 100-110.LI K, WANG H Z, ZHANG P, et al. User-demand-aware wireless access point association strategy[J]. Journal of Software,2015, 26(2): 100-110.

[12] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity[M]. New Jersey: Prentice-Hall, 1998.

[13] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms: 3rd edition[M]. Cambridge: MIT Press,2009: 60-73.

[14] WAN X, WU J, SHEN X. Maximal lifetime scheduling for roadside sensor networks with survivability k[J]. IEEE Transactions on Vehicular Technology, 2015, 64(11): 5300-5313.

[15] CHERKASSKY B V, GOLDBERG A V. On implementing push-relabel method for the maximum flow problem[J]. Integer Programming and Combinatorial Optimization, 1995, 35(10):157-163.

An association optimization algorithm for wireless access points based on graph transformation

TAO Wen1, SHEN Yan2, GUAN Xinjie2, WAN Xili2
1.College of Mathematics and Information Technology, Jiangsu Second Normal University, Nanjing 210013, China 2. College of Computer Science and Technology, Nanjing Tech University, Nanjing 211816, China

Wireless access point association problem is one of the fundamental problems for Wi-Fi systems. Existing studies focus on the AP association problems under the bandwidth capacity constrain, without considering bandwidth demand for users. Considering the user bandwidth demands, the access point association problem for a Wi-Fi system under hybrid network architecture was studied, with the objective of maximum bandwidth allocation. Different from existing studies, by utilizing graph transformation techniques, this optimization problem was transformed to a network flow optimization problem on a flow graph. Then, an algorithm was proposed based on the maximum network flow problem. Theoretic proof for the optimality of the algorithm was presented and simulations results further validated the superiority of the proposed algorithm.

wireless access, graph transformation, AP association

s: The National Natural Science Foundation of China (No.61602235), The National Natural Science Foundation of Jiangsu Province of China (No.BK20161007)

signal strength indication，RSSI）判断Wi-Fi接入点（access point，AP）的信号强度，并选择信号强度最强的AP与之关联。这种方法不能合理分配用户到不同的AP上，容易造成部分AP过载，而其他AP关联的用户偏少，从而造成系统资源不能被充分利用，降低了系统整体关联的用户数目。此外，这种方法只是以信号强度来关联用户和AP，而没有考虑到每个 AP的容量是有限的，即所能容纳的用户数是一定的。因此，如何在 AP容量有限的前提下，合理调度分配系统资源，从而提升系统整体可接入用户数量是 AP关联领域的一个重要问题[1]。

TP301

A

10.11959/j.issn.1000−0801.2017310

2017−08−05；

2017−09−19

国家自然科学基金资助项目（No.61602235）；江苏省自然科学基金资助项目（No.BK20161007）

陶雯（1979−），女，江苏第二师范学院数学与信息技术学院讲师、CCF会员，主要研究方向为无线网络协议。

沈艳（1984−），女，南京工业大学计算机科学与技术学院硕士生，主要研究方向为网络优化。

管昕洁（1984−），女，博士，南京工业大学计算机科学与技术学院讲师，主要研究方向为云计算和软件定义网络。

万夕里（1982−），男，博士，南京工业大学计算机科学与技术学院讲师，主要研究方向为网络优化和算法设计。