计算机科学技术学报 ›› 2019,Vol. 34 ›› Issue (4): 887-900.doi: 10.1007/s11390-019-1948-2

所属专题： Computer Networks and Distributed Computing

• • 上一篇    下一篇

无线网络中切换最小化算法

Mansoor Davoodi1, Esmaeil Delfaraz2, Sajjad Ghobadi2, Mahtab Masoori1   

  1. 1 Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran;
    2 Gran Sasso Science Institute, L'Aquila 67100, Italy
  • 收稿日期:2018-10-10 修回日期:2019-05-21 出版日期:2019-07-11 发布日期:2019-07-11
  • 作者简介:Mansoor Davoodi received his B.S.degree in computer science from ValiAsr University,Rafsanjan,Iran,in 2005,and his M.S.and Ph.D.degrees in computer science in Amirkabir University of Technology (Tehran Polytechnic),Tehran,in 2007 and 2012 respectively.He is currently an assistant professor in the Department of Computer Science and Information Technology,Institute for Advanced Studies in Basic Sciences (IASBS),Zanjan,Iran.His main research area includes algorithms,computational geometry,imprecise data handling and multi-objective optimization.

Algorithms for Handoff Minimization in Wireless Networks

Mansoor Davoodi1, Esmaeil Delfaraz2, Sajjad Ghobadi2, Mahtab Masoori1   

  1. 1 Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran;
    2 Gran Sasso Science Institute, L'Aquila 67100, Italy
  • Received:2018-10-10 Revised:2019-05-21 Online:2019-07-11 Published:2019-07-11

PDF (PC)

203

补充材料

1

本文着重研究无线网络中移动用户的切换最小化问题。该问题通过对在访问接入点容量限制下，用户移动的两种情况进行分析：1）所有的用户一起移动；2）在网内，每个用户可以拥有自己所选择的路径。在第一种情况中，我们为这个问题提出了一个最优竞争比算法。然而，在第二中情况中，基于连通性假设，也就是，"如果一个用户与一个访问接入点相连接，只要该点所收到的信号强度不小于某个特定的阈值，那么该用户应保持这个连接"，我们证明了没有方法可以减少离线设置里非必要切换的数量。然而，没有连通性假设的情况下，我们针对在线设置的此类问题提出了一个竞争比为nΔ的最优确定算法，其中n为用户数，Δ表示环境里覆盖了任意单点的最大访问接入点数。同时，我们证明了算法的随机版本达到了预期竞争比O（logΔ）.

关键词: 竞争比, 交换最小化, 离线算法, 在线算法, 无线网络

Abstract: This study focuses on the problem of handoff minimization for a set of users moving in a wireless network. This problem is analyzed by considering two cases for the user's movement under access point capacity constraints:1) all users move together, and 2) each user can have their chosen path within the network. In the first case, we propose an optimal competitive ratio algorithm for the problem. However, in the second case, having the connectivity assumption, that is, "if a user is connected to an access point so long that the received signal strength of the access point is not less than a specified threshold, the user should continue his/her connection", we prove that no approach can reduce the number of unnecessary handoffs in an offline setting. However, without connectivity assumption, we present an optimal deterministic algorithm with the competitive ratio of nΔ for this problem under online setting, where n is the number of users and Δ is the maximum number of access points which cover any single point in the environment. Also, we prove that the randomized version of the algorithm achieves an expected competitive ratio of O(log Δ).

Key words: competitive ratio, handoff minimization, offline algorithm, online algorithm, wireless network

[1] Kim M, Liu Z, Parthasarathy S, Pendarakis D, Yang H. Association control algorithms for handoff frequency minimization in mobile wireless networks. Wireless Networks, 2012, 18(5):535-550.
[2] Eppstein D, Goodrich M T, Löffler M. Tracking moving objects with few handovers. In Proc. the 12th Int. Symp. Algorithms and Data Structures, August 2011, pp.362-373.
[3] Zhao Y, Li W, Hong J, Li Z, Lu S, Chen D. On handoff minimization in wireless networks:From a navigation perspective. In Proc. the 2010 IEEE Wireless Communications and Networking Conference, April 2010, Article No. 336.
[4] Kim M, Liu Z, Parthasarathy S, Pendarakis D, Yang H. Association control in mobile wireless networks. In Proc. the 27th IEEE Int. Conf. Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, April 2008, pp.1256-1264.
[5] Mishra A, Shin M, Arbaush W A. Context caching using neighbor graphs for fast handoffs in a wireless network. In Proc. the 23rd Annual Joint Conf. the IEEE Computer and Communications Societies, March 2004, Article No. 33.
[6] Shin M, Mishra A, Arbaugh W A. Improving the latency of 802.11 hand-offs using neighbor graphs. In Proc. the 2nd ACM International Conference on Mobile Systems, Applications, and Services, June 2004, Article No. 8.
[7] Pack S, Choi Y. Fast inter-AP handoff using predictive authentication scheme in a public wireless LAN. In Proc. IEEE Networks Conference, August 2002, pp.15-26.
[8] Ramani I, Savage S. SyncScan:Practical fast handoff for 802.11 infrastructure networks. In Proc. the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, March 2005, pp.675-684.
[9] Bejerano Y, Han S J, Li L E. Fairness and load balancing in wireless LANs using association control. In Proc. the 10th Annual Int. Conf. Mobile Computing and Networking, Sept. 2004, pp.315-329.
[10] Balachandran A, Bahl P, Voelker G M. Hot-spot congestion relief in public-area wireless networks. In Proc. the 4th IEEE Workshop on Mobile Computing Systems and Applications, June 2002, pp.70-80.
[11] Tsai T C, Lien C F. IEEE 802.11 hot spot load balance and QoS-maintained seamless roaming. In Proc. the 2003"National" Computer Symposium, December 2003.
[12] Bejerano Y, Han S J. Cell breathing techniques for load balancing in wireless LANs. IEEE Transactions on Mobile Computing, 2009, 8(6):735-749.
[13] Ye Q, Rong B, Chen Y, Al-Shalash M, Caramanis C, Andrews J G. User association for load balancing in heterogeneous cellular networks. IEEE Transactions on Wireless Communications, 2013, 12(6):2706-2716.
[14] Chen J, Wang Y, Li Y, Wang E. QoE-aware intelligent vertical handoff scheme over heterogeneous wireless access networks. IEEE Access, 2018, 6:38285-38293.
[15] Goudarzi S, Hassan W H, Anisi M H et al. ABC-PSO for vertical handover in heterogeneous wireless networks. Neurocomputing, 2017, 256:63-81.
[16] Goudarzi S, Hassan W H, Anisi M H, Soleymani S A. MDP-based network selection scheme by genetic algorithm and simulated annealing for vertical-handover in heterogeneous wireless networks. Wireless Personal Communications, 2017, 92(2):399-436.
[17] Shidrokh G, Wan Haslina H, Mohammad H A, Ahmad S. A comparative review of vertical handover decisionmaking mechanisms in heterogeneous wireless networks. Indian Journal of Science and Technology, 2015, 8(23):Article No. 52.
[18] Mir U, Munir A. An adaptive handoff strategy for cognitive radio networks. Wireless Networks, 2018, 24(6):2077-2092.
[19] Ertürk M A, Vollero L, Aydin M A. Optimal joint load balancing and EDCA configuration of IEEE 802.11 wireless hotspots. International Journal of Communication Systems, 2018, 31(2):Article No. e3455.
[20] Soo W K, Ling T C, Maw A H, Win S T. Survey on loadbalancing methods in 802.11 infrastructure mode wireless networks for improving quality of service. ACM Computing Surveys, 2018, 51(2):Article No. 34.
[21] Aghazadeh Y, Kalbkhani H, Shayesteh M G, Solouk V. Cell selection for load balancing in heterogeneous networks. Wireless Personal Communications, 2018, 101(1):305-323.
[22] Sun Q, Huang L, Zhang H, Xu H. Handoff optimization and load balancing in wireless LANs using association control. International Journal of Communication Systems, 2015, 28(4):682-704.
[23] Li W Y, Zhang X, Jia S C, Gu X Y, Zhang L, Duan X Y, Lin J R. A novel dynamic adjusting algorithm for load balancing and handover co-optimization in LTE SON. Journal of Computer Science and Technology, 2013, 28(3):437-444.
[24] Ghica O, Trajcevski G, Zhou F et al. Selecting tracking principals with epoch awareness. In Proc. the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, November 2010, pp.222-231.
[25] He G, Hou J C. Tracking targets with quality in wireless sensor networks. In Proc. the 13th IEEE Int. Conf. Network Protocols, November 2005, pp.63-74.
[26] Pattem S, Poduri S, Krishnamachari B. Energy quality tradeoffs for target tracking in wireless sensor networks. In Proc. the 2nd International Workshop on Information Processing in Sensor Networks, April 2003, pp.32-46.
[27] Yi K, Zhang Q. Multidimensional online tracking. ACM Transactions on Algorithms, 2012, 8(2):Article No. 12.
[28] Zhao F, Shin J, Reich J. Information-driven dynamic sensor collaboration. IEEE Signal Processing Magazine, 2002, 19(2):61-72.
[29] Gu Y, Zhao B H, Ji Y S, Li J. Theoretical treatment of target coverage in wireless sensor networks. Journal of Computer Science and Technology, 2011, 26(1):117-129.
[30] Evans W, Kirkpatrick D, Löffler M, Staals F. Minimizing co-location potential of moving entities. SIAM Journal on Computing, 2016, 45(5):1870-1893.
[31] Tekinay S, Jabbari B. Handover and channel assignment in mobile cellular networks. IEEE Communications Magazine, 1991, 29(11):42-46.
[1] Jie Wu. 协同移动收费和覆盖[J]. , 2014, 29(4): 550-561.
[2] Peyman Teymoori, and Nasser Yazdani. 高速无线网络中延时约束下最优的数据包聚合机制[J]. , 2013, 28(3): 525-539.
[3] Hua-Zheng Du, Na Xia, Jian-Guo Jiang, Li-Na Xu, and Rong Zheng. 多信道无线网络中最优QoM的MC-PSO算法[J]. , 2013, 28(3): 553-563.
[4] Zhuo Li (李卓), Wen-Zhong Li (李文中), Member, CCF, ACM, IEEE, Song Guo (郭嵩), Senior Member, IEEE, Member, ACM, Sang-Lu Lu, (陆桑璐), Senior Member, CCF, Member, ACM, IEEE, and Dao-Xu Chen (陈道蓄), Senior Member, CCF, Member, ACM, IEEE. 面向异构无线移动网络的时延与容量分析[J]. , 2012, (2): 328-340.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[2] 刘健; 陈治明; 严百平; 杜忠;. A Switched Capacitor Harmonic Compensation Part for Switching Supplies[J]. , 1997, 12(2): 189 -192 .
[3] 沈理;. Fuzzy Logic Control ASIC Chip[J]. , 1997, 12(3): 263 -270 .
[4] . 以客户端为核心的面向服务应用的适应性调度[J]. , 2006, 21(4): 537 -546 .
[5] Chao Cai Zong-Yan Qiu Hong-Li Yang Xiang-Peng Zhao. 一种从全局到局部严格开发有异常处理的分布式系统的方法[J]. , 2009, 24(2): 238 -249 .
[6] . [J]. , 2010, 25(4): 864 -873 .
[7] Jun-Cheng Huang (黄俊成), Member, ACM, IEEE, Xiu-Qi Li (李秀琦), Member, ACM, IEEE and Jie Wu (吴杰), Member, ACM, Fellow, IEEE. 一个用于点对点网络的基于语义的多样化内容搜索模型[J]. , 2011, 26(6): 925 -941 .
[8] Pei-Chann Chang1 (张百栈), Wei-Hsiu Huang1 (黄伟修), and Zhen-Zhen Zhang2 (张真真). 以区块探勘及重组技术发展拼图式基因算法求解旅行者问题[J]. , 2012, 27(5): 937 -949 .
[9] Ticiana L. Coelho da Silva, Mario A. Nascimento, José Antônio F. de Ma. 云中的非入侵式弹性查询处理[J]. , 2013, 28(6): 932 -947 .
[10] Ke Liu, Zhi-Yong Liu. 前言[J]. , 2014, 29(5): 737 -739 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：