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

doi:10.11959/j.issn.1000-0801.2017310

电信科学 ›› 2017, Vol. 33 ›› Issue (11): 83-92.doi: 10.11959/j.issn.1000-0801.2017310

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

陶雯¹,沈艳²,管昕洁²,万夕里²

¹ 江苏第二师范学院数学与信息技术学院，江苏南京 210013
² 南京工业大学计算机科学与技术学院，江苏南京 211816

修回日期:2017-09-19 出版日期:2017-11-01 发布日期:2017-12-08
作者简介:陶雯（1979-），女，江苏第二师范学院数学与信息技术学院讲师、CCF会员，主要研究方向为无线网络协议。|沈艳（1984-），女，南京工业大学计算机科学与技术学院硕士生，主要研究方向为网络优化。|管昕洁（1984-），女，博士，南京工业大学计算机科学与技术学院讲师，主要研究方向为云计算和软件定义网络。|万夕里（1982-），男，博士，南京工业大学计算机科学与技术学院讲师，主要研究方向为网络优化和算法设计。
基金资助:
国家自然科学基金资助项目(61602235);江苏省自然科学基金资助项目(BK20161007)

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

Wen TAO¹,Yan SHEN²,Xinjie GUAN²,Xili WAN²

¹ College of Mathematics and Information Technology,Jiangsu Second Normal University,Nanjing 210013,China
² College of Computer Science and Technology,Nanjing Tech University,Nanjing 211816,China

Revised:2017-09-19 Online:2017-11-01 Published:2017-12-08
Supported by:
The National Natural Science Foundation of China(61602235);The National Natural Science Foundation of Jiangsu Province of China(BK20161007)

摘要/Abstract

摘要：

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

关键词: 无线接入, 图转换, 接入点关联

Abstract:

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.

Key words: wireless access, graph transformation, AP association

中图分类号:

TP301

陶雯,沈艳,管昕洁,万夕里. 基于图转换的无线接入点关联优化算法[J]. 电信科学, 2017, 33(11): 83-92.

Wen TAO,Yan SHEN,Xinjie GUAN,Xili WAN. An association optimization algorithm for wireless access points based on graph transformation[J]. Telecommunications Science, 2017, 33(11): 83-92.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

参考文献 15

[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 Management, 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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 15

相关文章 15

Metrics

推荐阅读 0

[1]	甄岩,余梦月,赵海波. 电力异构无线通信网络切片方案[J]. 电信科学, 2020, 36(2): 76-82.
[2]	张贤,曹雪妍,刘炳宏,艾元,刘晨熙. 6G智慧雾无线接入网：架构与关键技术[J]. 电信科学, 2020, 36(1): 3-10.
[3]	贾海宇,陈佳,王铭鑫. 无线接入网络中网络功能虚拟化研究综述[J]. 电信科学, 2019, 35(1): 97-112.
[4]	项弘禹,张欣然,朴竹颖,彭木根. 5G移动通信系统的接入网络架构[J]. 电信科学, 2018, 34(8): 10-18.
[5]	夏骋宇,蒋雁翔. D2D集成雾无线接入网中的双层分布式缓存[J]. 电信科学, 2018, 34(4): 49-56.
[6]	王燚,罗凤娅,孙国林. 面向5G RAN的网络切片技术[J]. 电信科学, 2018, 34(3): 124-131.
[7]	程锦堃,陈巍,石远明. 5G室内密集立体覆盖的计算通信：架构、方法与增益[J]. 电信科学, 2017, 33(6): 41-53.
[8]	尹博南,艾元,彭木根. 雾无线接入网：架构、原理和挑战[J]. 电信科学, 2016, 32(6): 20-27.
[9]	彭木根,艾元. 异构云无线接入网络：原理、架构、技术和挑战[J]. 电信科学, 2015, 31(5): 41-45.
[10]	默罕莫德·默森,毛云川,张瑞,沈连丰. 一种适用于车联网的无线接入多模网关系统[J]. 电信科学, 2014, 30(4): 74-81.
[11]	闫实,王文博. 云无线接入网的系统架构和技术演进[J]. 电信科学, 2014, 30(3): 49-53.
[12]	王哲,许洪东,赵丽敏. 4G核心网和无线网协同的端到端跟踪实现方法[J]. 电信科学, 2014, 30(12): 128-133.
[13]	沈洁. 第5代移动通信系统展望[J]. 电信科学, 2013, 29(9): 98-101.
[14]	雷晓东. PTN技术在全球运营网中的典型应用案例分析[J]. 电信科学, 2012, 28(7): 101-109.
[15]	陈运清,史凡,聂世忠. 发展以IP RAN为代表的多业务承载MBH网络[J]. 电信科学, 2012, 28(7): 119-123.