State-Aware Re-configuration Model for Multi-Radio Wireless Mesh Networks = State-Aware Re-configuration Model for Multi-Radio Wireless Mesh Networks

다국어 초록 (Multilingual Abstract)

Joint channel assignment and routing is a well-known problem in multi-radio wireless mesh networks for which optimal configurations is required to optimize the overall throughput and fairness. However, other objectives need to be considered in order to provide a high quality service to network users when it deployed with high traffic dynamic. In this paper, we propose a re-configuration optimization model that optimizes the network throughput in addition to reducing the disruption to the mesh clients` traffic due to the re-configuration process. In this multi-objective optimization model, four objective functions are proposed to be minimized namely maximum link-channel utilization, network average contention, channel re-assignment cost, and re-routing cost. The latter two objectives focus on reducing the re-configuration overhead. This is to reduce the amount of disrupted traffic due to the channel switching and path re-routing resulted from applying the new configuration. In order to adapt to traffic dynamics in the network which might be caused by many factors i.e. users` mobility, a centralized heuristic re-configuration algorithm called State-Aware Joint Routing and Channel Assignment (SA-JRCA) is proposed in this research based on our re-configuration model. The proposed algorithm re-assigns channels to radios and re-configures flows` routes with aim of achieving a tradeoff between maximizing the network throughput and minimizing the re-configuration overhead. The ns-2 simulator is used as simulation tool and various metrics are evaluated. These metrics include channel-link utilization, channel re-assignment cost, re-routing cost, throughput, and delay. Simulation results show the good performance of SA-JRCA in term of packet delivery ratio, aggregated throughput and re-configuration overhead. It also shows higher stability to the traffic variation in comparison with other compared algorithms which suffer from performance degradation when high traffic dynamics is applied.

참고문헌 (Reference)

1 I. Akyildiz, "Wireless mesh networks" John Wiley & Sons 2009

2 A. Iyer, "What is the right model for wireless channel interference?" 8 (8): 2662-2671, 2009

3 I. I. CPLEX, "V12. 1: User’s Manual for CPLEX" 46 (46): 157-, 2009

4 W. Pak, "Traffic Flow Estimation based Channel Assignment for Wireless Mesh Networks" 5 (5): 68-82, 2011

5 J. Wellons, "The robust joint solution for channel assignment and routing for wireless mesh networks with time partitioning" 13 : 210-221, 2014

6 C. Spearman, "The proof and measurement of association between two things" 15 (15): 72-101, 1904

7 H. W. Kuhn, "The Hungarian method for the assignment problem" 2 (2): 83-97, 1955

8 J. J. Galvez, "TCP flow-aware Channel Re-Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks" 262-271, 2010

9 A. Musaddiq, "Survey of channel assignment algorithms for multi-radio multi-channel wireless mesh networks" 32 (32): 164-182, 2015

10 X. Bao, "Robust topology construction method with radio interface constraint for multi-radio multi-channel wireless mesh network using directional antennas" 12 (12): 2016

11 H.A. Mogaibel, "Review of channel assignment approaches in multi-radio multi-channel wireless mesh network" 72 : 113-139, 2016

12 J. J. Galvez, "Responsive Online Load-Balancing Routing and Load-aware Channel Re-Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks" University of Murcia, Spain, Tech. Rep 2011

13 Y. Zhou, "Reconfiguring Multi-Rate Wi-Fi Mesh Networks with Flow Disruption Constraints" Springer 2013

14 A.U. Chaudhry, "Realistic interference-free channel assignment for dynamic wireless mesh networks using beamforming" 51 : 21-35, 2016

15 J. Wang, "Partially overlapped channels-and flow-based end-to-end channel assignment for multi-radio multi-channel wireless mesh networks" 13 (13): 1-13, 2016

16 C. Cicconetti, "PaMeLA: A joint channel assignment and routing algorithm for multi-radio multi-channel wireless mesh networks with grid topology" 199-207, 2009

17 A. A. Franklin, "Online reconfiguration of channel assignment in multi-channel multi-radio wireless mesh networks" 35 (35): 2004-2013, 2012

18 S. Arkoulis, "On the optimal, fair and channel-aware cognitive radio network reconfiguration" 57 (57): 1739-1757, 2013

19 H. Li, "Multi-dimensional conflict graph based computing for optimal capacity in MR-MC wireless networks" 774-783, 2010

20 X. Shao, "Load Balanced Coding Aware Multipath Routing for Wireless Mesh Networks" 24 : 8-12, 2015

21 X. Y. Li, "Joint throughput optimization for wireless mesh networks" 8 (8): 895-909, 2009

22 X. Meng, "Joint routing and channel assignment in multi-radio wireless mesh networks" 3596-3601, 2006

23 A. Mohsenian-Rad, "Joint logical topology design, interface assignment, channel allocation, and routing for multi-channel wireless mesh networks" 12 (12): 4432-4440, 2007

24 J. J. Gálvez, "Joint link rate allocation, routing and channel assignment in multi-rate multi-channel wireless networks" 29 : 78-98, 2015

25 N. Sadeghianpour, "Joint channel assignment and routing in multiradio multichannel wireless mesh networks with directional antennas" 28 (28): 1521-1536, 2015

26 O. M. Zakaria, "Joint Channel Assignment and Routing in Multiradio Multichannel Wireless Mesh Networks: Design Considerations and Approaches" 2016 : 24-, 2016

27 M. Alicherry, "Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks" 24 (24): 1960-1971, 2006

28 M. Nekoui, "Iterative cross layer schemes for throughput maximization in multi-channel wireless mesh networks" 1088-1092, 2007

29 P. Li, "How to effectively use multiple channels in wireless mesh networks" 20 (20): 1641-1652, 2009

30 V. Gardellin, "G-PaMeLA: A divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks" 71 (71): 381-396, 2011

31 E.N. Maleki, "Fault-tolerant interference-aware topology control in multi-radio multi-channel wireless mesh networks" 110 : 206-222, 2016

32 J. J. Gálvez, "Efficient rate allocation, routing and channel assignment in wireless mesh networks supporting dynamic traffic flows" 11 (11): 1765-1781, 2013

33 A.R. Ulucinar, "Distributed joint flow-radio and channel assignment using partially overlapping channels in multi-radio wireless mesh networks" 22 (22): 83-104, 2016

34 X. Huang, "Cross-layer fair resources allocation for multi-radio multi-channel wireless mesh networks" 1-5, 2009

35 M. Kodialam, "Characterizing the capacity region in multi-radio multi-channel wireless mesh networks" 73-87, 2005

36 M. Yun, "Channel-assignment and scheduling in wireless mesh networks considering switching overhead" 1-6, 2009

37 A.A. Al Islam, "Channel Assignment Techniques for Multi-Radio Wireless Mesh Networks: A Survey" 18 (18): 988-1017, 2016

38 Saleem Iqbal, "Channel Allocation in Multi-radio Multi-channel Wireless Mesh Networks: A Categorized Survey" 한국인터넷정보학회 9 (9): 1642-1661, 2015

39 A. Raniwala, "Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks" 8 (8): 50-65, 2004

40 T. Y. Lin, "Applying genetic algorithms for multi-radio wireless mesh network planning" 61 (61): 2256-2270, 2012

41 W. Si, "An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks" 70 (70): 505-524, 2010

42 F. Herzel, "An integrated CMOS RF synthesizer for 802.11 a wireless LAN" 38 (38): 1767-1770, 2003

43 S. Avallone, "An experimental study of the channel switching cost in multi-radio wireless mesh networks" 51 (51): 124-134, 2013

44 A. Kanagasabapathy, "An adaptive channel reconfiguration algorithm for multi-channel multi-radio wireless mesh networks" 9 (9): 3064-3071, 2010

45 S. Avallone, "A traffic-aware channel re-assignment algorithm for wireless mesh networks" 683-688, 2010

46 S. Avallone, "A traffic-aware channel and rate reassignment algorithm for wireless mesh networks" 12 (12): 1335-1348, 2013

47 Y. Qu, "A survey of routing and channel assignment in multi-channel multi-radio WMNs" 65 : 120-130, 2016

48 R. Jain, "A quantitative measure of fairness and discrimination for resource allocation in shared computer systems" Eastern Research Laboratory, Digital Equipment Corporation 1984

49 J. Avonts, "A framework to compare topology algorithms in multi-channel multi-radio wireless mesh networks" 98 : 89-108, 2016

50 L. Farzinvash, "A cross-layer approach for multi-layer multicast routing in multi-channel multi-radio wireless mesh networks" 21 (21): 26-40, 2016

51 S. Avallone, "A channel assignment and routing algorithm for energy harvesting multiradio wireless mesh networks" 34 (34): 1463-1476, 2016

52 S. Avallone, "A channel assignment and routing algorithm for energy harvesting multiradio wireless mesh networks" 34 (34): 1463-1476, 2016

53 S. Avallone, "A channel and rate assignment algorithm and a layer-2.5 forwarding paradigm for multi-radio wireless mesh networks" 17 (17): 267-280, 2009

54 S. Zhuo, "A Traffic Adaptive Multi-channel MAC Protocol with Dynamic Slot Allocation for WSNs" 15 (15): 1600-1613, 2016

55 Yi-Han XU, "A Routing Metric to Improve Route Stability in Mobile Wireless Sensor Networks" 한국인터넷정보학회 10 (10): 2245-2266, 2016

56 Md. Kamal Hossain, "A Dynamic Channel Switching Policy Through P-learning for Wireless Mesh Networks" 한국인터넷정보학회 10 (10): 608-627, 2016

57 D.G. Narayan, "A Cross-Layer Framework for Joint Routing and Resource Management in Multi-radio Infrastructure Wireless Mesh Networks" 1-17, 2016