Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (4): 887-900.doi: 10.1007/s11390-019-1948-2

Special Issue: Computer Networks and Distributed Computing

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

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

Supplement

1

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. Collaborative Mobile Charging and Coverage [J]. , 2014, 29(4): 550-561.
[2] Peyman Teymoori, and Nasser Yazdani. Delay-Constrained Optimized Packet Aggregation in High-Speed Wireless Networks [J]. , 2013, 28(3): 525-539.
[3] Hua-Zheng Du, Na Xia, Jian-Guo Jiang, Li-Na Xu, and Rong Zheng. A Monte Carlo Enhanced PSO Algorithm for Optimal QoM in Multi-Channel Wireless Networks [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. Delay and Capacity Trade-offs in Mobile Wireless Networks with Infrastructure Support [J]. , 2012, (2): 328-340.
[5] Chun-Lin Xin, Wei-Min Ma, and Lei Yang. Competitive Analysis of Two Special Online Device Replacement Problems [J]. , 2008, 23(2): 203-213 .
[6] Min Liu, Zhong-Cheng Li, and Xiao-Bing Guo. An Efficient Handoff Decision Algorithm for Vertical Handoff Between WWAN and WLAN [J]. , 2007, 22(1): 114-120 .
[7] Yi-Wei Jiang and Yong He. Semi-Online Algorithms for Scheduling with Machine Cost [J]. , 2006, 21(6): 984-988 .
[8] Heng-Chang Liu and Bao-Hua Zhao. A Near-Optimal Optimization Algorithm for Link Assignment in Wireless Ad-Hoc Networks [J]. , 2006, 21(1): 89-94 .
[9] Weisong Shi , Sharun Santhosh, and Hanping Lufei. Secure Application-Aware Service Differentiation in Public Area Wireless Networks [J]. , 2005, 20(5): 676-688 .
[10] Yuan Zhou, Guang-Sheng Li, Yong-Zhao Zhan, Qi-Rong Mao, and Yi-Bin Hou. DRMR: Dynamic-Ring-Based Multicast Routing Protocol for Ad Hoc Networks [J]. , 2004, 19(6): 0-0.
[11] Qing-Hua Zheng, David L. Pepyne, and Qing Wang. New Approach to WLAN Security with Synchronized Pseudo Random [J]. , 2004, 19(6): 0-0.
[12] Yong He and Yi-Wei Jiang. Preemptive Semi-Online Scheduling with Tightly-Grouped Processing Times [J]. , 2004, 19(6): 0-0.
[13] ZHOU BoSheng (周伯生), WU JieYi (吴介一), FEI Xiang (费 翔) and ZHAO Jian (赵 键). PCBA: A Priority-Based Competitive Broadcasting Algorithm in Mobile Ad Hoc Networks [J]. , 2003, 18(5): 0-0.
[14] HE Yong (何勇) and CAI Shengyi (蔡圣义). Semi-Online Scheduling with Machine Cost [J]. , 2002, 17(6): 0-0.
[15] SUI Yuefei（眭跃飞）. Two Online Algorithms for the Ambulance Systems [J]. , 2001, 16(2): 0-0.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[2] Liu Jian; Chen Zhiming; Du Zhong; Yan Baiping;. A Switched Capacitor Harmonic Compensation Part for Switching Supplies[J]. , 1997, 12(2): 189 -192 .
[3] Shen Li;. Fuzzy Logic Control ASIC Chip[J]. , 1997, 12(3): 263 -270 .
[4] Jing Wang, Li-Yong Zhang, Yan-Bo Han. Client-Centric Adaptive Scheduling of Service-Oriented Applications[J]. , 2006, 21(4): 537 -546 .
[5] Chao Cai, Zong-Yan Qiu, Senior Member, CCF, Member, IEEE, Hong-Li Yang, and Xiang-Peng Zhao. Global-to-Local Approach to Rigorously Developing Distributed System with Exception Handling[J]. , 2009, 24(2): 238 -249 .
[6] Zhi-Feng Yu(余志峰) and Wei-Song Shi(施巍松), Senior Member, IEEE. Queue Waiting Time Aware Dynamic Workflow Scheduling in Multicluster Environments[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. A Semantic Searching Scheme in Heterogeneous Unstructured P2P Networks[J]. , 2011, 26(6): 925 -941 .
[8] Pei-Chann Chang, Wei-Hsiu Huang, and Zhen-Zhen Zhang. A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem[J]. , 2012, 27(5): 937 -949 .
[9] Ticiana L. Coelho da Silva, Mario A. Nascimento, José Antônio F. de Macêdo, Flávio R. C. Sousa, and Javam C. Machado. Non-Intrusive Elastic Query Processing in the Cloud[J]. , 2013, 28(6): 932 -947 .
[10] Ke Liu, Zhi-Yong Liu. Preface[J]. , 2014, 29(5): 737 -739 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved