无线网络中的频谱资源优化与多信道技术研究
|
摘要
可用的频谱资源是无线网络容量提升的主要瓶颈。有效的频谱资源分配策略可以减小信道之间干扰、提高频谱资源利用率,从而增加网络容量。无线mesh网络(Wireless Mesh Network,WMN)是一种新型宽带无线网络,由于其复杂的组网模式,使其核心技术研究面临诸多理论和实践的挑战,而频谱资源分配和多信道技术也成为影响无线Mesh网络性能的关键问题。
本文阐述了无线网络中频谱资源分配的基本概念和研究现状,具体分析了信道分配问题中的图着色理论,以及固定信道分配方案中在优化目标不同时的具体分类,并给出了相应的数学描述和定义。探讨了信道分配问题在无线蜂窝网络中的应用,包括蜂窝网络中静态信道分配、动态信道分配以及混合信道分配问题。进一步分析了不同着色模型下的蜂窝网络信道分配算法。
本文重点研究了无线mesh网络中的信道分配问题。在分析mesh网络现有主要信道分配方案的基础上,针对863课题中虚拟层次化无线mesh网络架构提出了一种无线信道资源分配的实现方案。方案针对虚拟层次小区所构成的网络拓扑,提出了利用射频防卫度作为信道分配的指标的一种广义集合T-coloring模型,其能够很好的适用于课题中的虚拟层次化网络环境,从而获得了保持网络的连通性、控制无线信道干扰的资源分配的良好效果。
本文进一步开展了多接口-多信道无线mesh网络中信道分配的理论研究,分析了其现状和数学模型,探讨了节点接口数充足的理想状态下无线mesh网络中的信道分配问题。在此基础上提出了一种多接口-多信道无线mesh网络中基于图分解的时隙信道分配策略,该方案考虑了信道分配在时间域的拓展。方案根据连通节点间的传输路径构造对应每个时隙子图,并针对该子图运用图着色算法优化每个时隙的信道分配,从而提高了时隙的链路信道分配效率。进一步在满足无线mesh网络中信道分配节点接口数约束、信道数约束的条件下增加了网络吞吐量。该方法相比各种静态信道分配方案具有明显的优势,仿真结果也验证了其有效性。
In the wireless network, the available spectrum is a bottleneck of network capacity. While, effective spectrum resources assignment strategy can reduce network interference, improve the utilization of spectrum resources. Wireless mesh network (WMN) is a new kind of broadband wireless access networks, spectrum resources assignment and multi-channel technology is essential for wireless mesh network.
First of all, this paper introduces the concepts and overviews of spectrum resources assignment problem, including the classification of channel assignment and the algorithm models. Then, investigate the applications of channel assignment in wireless cellular network, including static channel assignment, dynamic channel assignment and hybrid channel assignment, and analyses channel assignment algorithm with several coloring models for cellular networks.
Secondly, this paper focuses on the channel assignment researching in wireless mesh network, and discusses the constraints conditions of the algorithm, analyses the typical channel assignment schemes also. Under virtual hierarchical wireless mesh network structure, this paper proposed it’s channel resources assignment by introduced RF-based defense degree as the indicator of channel assignment, and proposed a generalized set T-coloring model which could maintain network connectivity and control wireless channel interference for resources assignment.
Finally, this paper proposed a slot channel assignment scheme based on graph decomposition in multi-radio multi-channel wireless mesh networks by extended channel assignment in the time domain. A new algorithm based on of the transmission paths between communication nodes in each time slot corresponds to a sub-graph, and every sub-graph using a certain coloring algorithm optimizes channel assignment in each time slot. Consequently, each time slot more link can be assigned channels and network throughput can be improved. The scheme takes the precedence to other channel assignment schemes. The simulation results show the effectiveness of the algorithm.
本文阐述了无线网络中频谱资源分配的基本概念和研究现状,具体分析了信道分配问题中的图着色理论,以及固定信道分配方案中在优化目标不同时的具体分类,并给出了相应的数学描述和定义。探讨了信道分配问题在无线蜂窝网络中的应用,包括蜂窝网络中静态信道分配、动态信道分配以及混合信道分配问题。进一步分析了不同着色模型下的蜂窝网络信道分配算法。
本文重点研究了无线mesh网络中的信道分配问题。在分析mesh网络现有主要信道分配方案的基础上,针对863课题中虚拟层次化无线mesh网络架构提出了一种无线信道资源分配的实现方案。方案针对虚拟层次小区所构成的网络拓扑,提出了利用射频防卫度作为信道分配的指标的一种广义集合T-coloring模型,其能够很好的适用于课题中的虚拟层次化网络环境,从而获得了保持网络的连通性、控制无线信道干扰的资源分配的良好效果。
本文进一步开展了多接口-多信道无线mesh网络中信道分配的理论研究,分析了其现状和数学模型,探讨了节点接口数充足的理想状态下无线mesh网络中的信道分配问题。在此基础上提出了一种多接口-多信道无线mesh网络中基于图分解的时隙信道分配策略,该方案考虑了信道分配在时间域的拓展。方案根据连通节点间的传输路径构造对应每个时隙子图,并针对该子图运用图着色算法优化每个时隙的信道分配,从而提高了时隙的链路信道分配效率。进一步在满足无线mesh网络中信道分配节点接口数约束、信道数约束的条件下增加了网络吞吐量。该方法相比各种静态信道分配方案具有明显的优势,仿真结果也验证了其有效性。
In the wireless network, the available spectrum is a bottleneck of network capacity. While, effective spectrum resources assignment strategy can reduce network interference, improve the utilization of spectrum resources. Wireless mesh network (WMN) is a new kind of broadband wireless access networks, spectrum resources assignment and multi-channel technology is essential for wireless mesh network.
First of all, this paper introduces the concepts and overviews of spectrum resources assignment problem, including the classification of channel assignment and the algorithm models. Then, investigate the applications of channel assignment in wireless cellular network, including static channel assignment, dynamic channel assignment and hybrid channel assignment, and analyses channel assignment algorithm with several coloring models for cellular networks.
Secondly, this paper focuses on the channel assignment researching in wireless mesh network, and discusses the constraints conditions of the algorithm, analyses the typical channel assignment schemes also. Under virtual hierarchical wireless mesh network structure, this paper proposed it’s channel resources assignment by introduced RF-based defense degree as the indicator of channel assignment, and proposed a generalized set T-coloring model which could maintain network connectivity and control wireless channel interference for resources assignment.
Finally, this paper proposed a slot channel assignment scheme based on graph decomposition in multi-radio multi-channel wireless mesh networks by extended channel assignment in the time domain. A new algorithm based on of the transmission paths between communication nodes in each time slot corresponds to a sub-graph, and every sub-graph using a certain coloring algorithm optimizes channel assignment in each time slot. Consequently, each time slot more link can be assigned channels and network throughput can be improved. The scheme takes the precedence to other channel assignment schemes. The simulation results show the effectiveness of the algorithm.
引文
[1] Arie Koster. Frequency assignment: models and algorithms[J]. PROEFSCHRIFT UNIVERSITEIT MAASTRICHT, 1999.
[2] Ian F.Akyildiz, Xudong Wang and Weilin Wang. Wireless mesh networks: a survey, Broadband and Wireless Networking (BWN) Lab[J]. School of Electrical and Computer Engineering, 2004, 47(4): 445-487.
[3] Kyasanur P and Vaidya N. Routing and interface assignment in multi-channel multi-interface wireless Networks[J]. Proc. of the IEEE WCNC. 2005, 2051-2056.
[4] H. W. Fastert. The mathematical theory underlying the planning of transmitter networks[J]. E.B. U. Rev., no. 60-A, 1960, 60-69.
[5] J. Arthur Zoellner. Frequency assignment games and strategies[J]. ZEEE Trans. on Electromagn. Compat., 1973, 191-196.
[6] W. K. Hale. Frequency assignment: Theory and applications[J]. Proceedings of the IEEE 1980, 1497–1514.
[7] D. Fotakis, S. Nikoletseas, V. Papadopoulou A and P. Spirakis. Hardness Results and Efficient Approximations for Frequency Assignment Problems: Radio Labelling and Radio Coloring[J]. Computing and Informatics 20, 2001, 15(6):121-180.
[8] S. Martello and P. Toth. Heuristic algorithms for the multiple knapsack problem[J]. Journal of Computing, 1981, 27(1): 93-112.
[9] I. Katzela and M. Naghshineh. Channel assignment schemes for cellular mobile telecommunication systems: A comprehensive survey[J]. IEEE Personal Communications, 1996, 3(3):10-31.
[10] L.G. Anderson. A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system[J]. IEEE Transactions on Communications, 1973, 21:1294-1301.
[11] A. Raniwala, K. Gopalan and Chiueh T.-C. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J]. ACM Mobile Computing and Communications Review (MC2R), 2004, 8(2):50-65.
[12] T. R. Jensen and B. Toft, Graph Coloring Problems[M]. New York: Wiley Interscience, 1995, 50-95.
[13] R. Draves, J. Padhye, and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks[J]. in Algoritmica, 1997.
[14] M. Marina and S. R. Das. A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[J]. in Proc. IEEE Broadnets’05, 2005, 381-390.
[15] P. Bahl, R. Chandra, and J. Dunagan. SSCH: Slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks[J]. in Proc. ACM MobiCom, 2004, 216-230.
[16] A. Raniwala and T. Chiueh. Evaluation of a wireless enterprise backbone network architecture[J]. in Proc. 12th Hot-Interconnects, 2004, 98-104.
[17] A. Raniwala and T. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[C]. in Proc. IEEE Infocom, 2007, 2223-2234.
[18] K. Ramachandran, K. Almeroth, E. Belding-Royer, and M. Buddhikot. Interference aware channel assignment in multi-radio wireless mesh networks[C]. in Proc. IEEE Infocom, 2006.
[19] P. Kyasanur and N. Vaidya. Routing and link-layer protocols for multi-channel multiinterface ad hoc wireless networks[J]. Mobile Computing and Communications Review, 2006, 10(1):31-43,.
[20] A. H. M. Rad and V. W. S. Wong. Logical topology design and interface assignment for multi-channel wireless mesh networks[C]. Proc. IEEE Global Telecommunications Conference (Globecom), 2006.
[21] Ulrich Fiedler. Mesh Network Topology Construction and Channel Frequency Allocation in the TOWN Project[J]. Computer Engineering and Networks Laboratory TIK-Report 255, 2006.
[22] Seongho CHO and Chong-kwon KIM. Interference-Aware Multi-Channel Assignment in Multi-Radio Wireless Mesh Networks[J]. IEICE Transactions on Communications, 2007, 1436-1445.
[23] Leiming Xu, Yong Xiang and Meilin Shi. A novel channel assignment algorithm based on topology simplification in multi-radio wireless mesh networks[C]. Performance, Computing, and Communications Conference, 2006.
[24] SeyedAlireza hasem and hiraziand amidreza lllindavar. A Hybrid Method For Channel Assignment Problems in Cellular Radio Networks. Wireless Communications and Networking Conference[C]. 2006, 1260一1265.
[25] Cozzens M B and Roberts F S. T-colorings of graphs and the channel assignment problem[J]. Congressus Numerantium, 1982, 35:191-08.
[26] B. A. Tesman. List T-colorings of graphs[J]. Discrete Applied Math. 45. 1993, 277-289.
[27] M. Yannakakis and F. Gavril. The maximum k-colorable subgraph problem for chordal graphs[J]. Information Processing Letters 24, 1987, 133–137.
?
[28] S.T. McCormick. Optimal Approximation of Sparse Hessians and its Equivalence to a Graph Coloring Problem[J]. Mathematical Programming, 1983, (26):153–171.
[29] M. R. Garey , D. S. Johnson and L. Stockmeyer, Some simplied NP-complete graph problems[J]. Theoretical Computer Science, 1976, 237-267.
[30] Griggs, J. R. and R. K. Yeh. Labeling graphs with a condition at distance 2[J]. SIAM J. Disc. Math. 5, 1992, 586-595.
[31] Chang, G. J. and D. Kuo. The L(2,1)-labeling problem on graphs[J]. SIAM J. Disc. Math. 9 1996, 309-316.
[32] T.A. Lanfear. Graph theory and radio frequency assignment[J]. Technical Report NATO Unclassified, Allied Radio Frequency Agency (ARFA), 1989.
[33] R.M. Karp. Reducibility among combinatorial problems[J]. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, 1972, 85-103.
[34] K.I. Aardal, A. Hipolito, C.P.M. van Hoesel, and B. Jansen. A branch-and-cut algorithm for the frequency assignment problem[J]. Research Memorandum 96/011, Maastricht University, 1996.
[35] J.R. Griggs and D.D.-F. Liu. The channel assignment problem for mutually adjacent sites. Joumal of ComfcinatoriaZ Theory[J]. 1994, 169-183.
[36] M. Kubale. Interval vertex-coloring of a graph with forbidden colors[J]. Discrete Mathematics, 1989, (74):125-136.
[37] M. Kubale. Some results concerning the complexity of restricted colorings of graphs[J]. Discrete Applied Mathematics, 1992, (36):35-46.
[38] D.H. Smith, S. Hurley, and S.U. Thiel. Improving heuristics for the frequency assignment problem[J]. European Journal of Operational Research, 1998, 107:76-86.
[39] R. Mathar and J. Mattfeldt. Channel assignment in cellular radio networks[J]. Transactions on Vehicular Technology, 1993, 42:647-656.
[40] M.G. Kazantzakis, P.P. Demestichas, and M.E. Anagnostou. Optimum frequency reuse in mobile telephone systems[J], International journal of Communications Systems, 1995, 8:185-190,.
[41] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory and Applications[J]. Prentice Hall, New Jersey, 1993.
[42] R. Borndorfer, A. Eisenblatter, M. Grotschel, and A. Martin. Frequency assignment in cellular phone networks[J]. AnnaLs of Operations Research, 1998, 76:73-94.
[43] D. Brelaz. New methods to color the vertices of a graph[J]. Communications of the ACM, 1979, 22:251-256.
[44] D. Costa. On the use of some known methods for t-colourings of graphs[J]. Annais of Operations flesearch, 1993, 41:343-358.
[45] T.J. Kahwa, and N.D. Georganas. A hybrid channel assignment scheme in large-scale cellular-structured mobile communication systems[J]. IEEE Transactions on Communications COM-26, 1978, 432–438.
[46] Betrossi, A.A. , Pinotti, C.M and Tan, R.B. Efficient Use of Radio Spectrum in Wireless Networks with Channel Separation between close Stations[J]. in Proc of the DIAL M for Mobile workshop, 2000, 18-27.
[47] Subramanian A, Krishnan R, Das SR, and Gupta H. Minimum interference channel assignment in multi-radio wireless mesh networks[J]. Sensor, Mesh and Ad Hoc Communications and Networks, 2007, 7(4): 481-490.
[48] H. Skalli, S. Ghosh, S. K. Das, L. Lenzini, and M. Cont. Channel assignment strategies for multi-radio wireless mesh networks: Issues and solutions[J]. IEEE Communications Magazine, Special Issue on“Wireless Mesh Networks”, 2007.
[49] J. So and N. Vaidya. Multi-channel MAC for ad hoc networks: Handling multi-channel hidden terminals using a single transceiver[J]. in Proc. ACM Mobihoc, 2004, 222-233.
[50] S. Wu, C. Lin, Y. Tseng, and J. Sheu. A new multi-channel MAC protocol with ondemand channel assignment for multi-hop mobile ad hoc networks[J]. submitted to the International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN), 2000.
[51] C. L. Barrett, G. Istrate, V. S. A. Kumar, M. V. Marathe, and S. Thite. Strong edge coloring for channel assignment in wireless radio networks[C]. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, 2006.
[52] Chae Y. Lee and Hyon G. Kang. Cell Planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach. Vehicular Technology[J]. IEEE Transactions on. 2000, 49(5) :1678-1691.
[53] Tamura, H.Watanabe, K.Sengoku, M.Shinoda. on a new edge coloring related to multihop wireless networks[J], Circuits and Systems, 2002, 357- 360.
[54] Jain N, Das S, and Nasipuri A. A multi channel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks[J]. IEEE International Conference on Computer Communications and Networks (IC3N), 2001.
[55] H. Skalli, S .K. Das, and L. Lenzini. Traffic and interference aware channel. assignment for multi-radio Wireless Mesh Networks[J]. Technical report, 2006.
[56] Chun-chen Hsu, Pangfeng, Liu,Dawei Wang. Generalized edge coloring for channel assignment in wireless networks[J]. Parallel Processing, 2006, 82-92.
[57] A. Proskurowski, and M. M. Syslo, Efficient vertex and edge coloring of outerplanar graphs[J]. SIAM J. Algebraic and Discrete Methods, 1986, 7:131–136.
[58] S.M. Allen. Frequency assignment problems: subgraph generation for lower bounds[J]. Technical Report UG-M-98-2, Division of Mathematics and Computing, University of Glamorgan, 1998.
[2] Ian F.Akyildiz, Xudong Wang and Weilin Wang. Wireless mesh networks: a survey, Broadband and Wireless Networking (BWN) Lab[J]. School of Electrical and Computer Engineering, 2004, 47(4): 445-487.
[3] Kyasanur P and Vaidya N. Routing and interface assignment in multi-channel multi-interface wireless Networks[J]. Proc. of the IEEE WCNC. 2005, 2051-2056.
[4] H. W. Fastert. The mathematical theory underlying the planning of transmitter networks[J]. E.B. U. Rev., no. 60-A, 1960, 60-69.
[5] J. Arthur Zoellner. Frequency assignment games and strategies[J]. ZEEE Trans. on Electromagn. Compat., 1973, 191-196.
[6] W. K. Hale. Frequency assignment: Theory and applications[J]. Proceedings of the IEEE 1980, 1497–1514.
[7] D. Fotakis, S. Nikoletseas, V. Papadopoulou A and P. Spirakis. Hardness Results and Efficient Approximations for Frequency Assignment Problems: Radio Labelling and Radio Coloring[J]. Computing and Informatics 20, 2001, 15(6):121-180.
[8] S. Martello and P. Toth. Heuristic algorithms for the multiple knapsack problem[J]. Journal of Computing, 1981, 27(1): 93-112.
[9] I. Katzela and M. Naghshineh. Channel assignment schemes for cellular mobile telecommunication systems: A comprehensive survey[J]. IEEE Personal Communications, 1996, 3(3):10-31.
[10] L.G. Anderson. A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system[J]. IEEE Transactions on Communications, 1973, 21:1294-1301.
[11] A. Raniwala, K. Gopalan and Chiueh T.-C. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J]. ACM Mobile Computing and Communications Review (MC2R), 2004, 8(2):50-65.
[12] T. R. Jensen and B. Toft, Graph Coloring Problems[M]. New York: Wiley Interscience, 1995, 50-95.
[13] R. Draves, J. Padhye, and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks[J]. in Algoritmica, 1997.
[14] M. Marina and S. R. Das. A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[J]. in Proc. IEEE Broadnets’05, 2005, 381-390.
[15] P. Bahl, R. Chandra, and J. Dunagan. SSCH: Slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks[J]. in Proc. ACM MobiCom, 2004, 216-230.
[16] A. Raniwala and T. Chiueh. Evaluation of a wireless enterprise backbone network architecture[J]. in Proc. 12th Hot-Interconnects, 2004, 98-104.
[17] A. Raniwala and T. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[C]. in Proc. IEEE Infocom, 2007, 2223-2234.
[18] K. Ramachandran, K. Almeroth, E. Belding-Royer, and M. Buddhikot. Interference aware channel assignment in multi-radio wireless mesh networks[C]. in Proc. IEEE Infocom, 2006.
[19] P. Kyasanur and N. Vaidya. Routing and link-layer protocols for multi-channel multiinterface ad hoc wireless networks[J]. Mobile Computing and Communications Review, 2006, 10(1):31-43,.
[20] A. H. M. Rad and V. W. S. Wong. Logical topology design and interface assignment for multi-channel wireless mesh networks[C]. Proc. IEEE Global Telecommunications Conference (Globecom), 2006.
[21] Ulrich Fiedler. Mesh Network Topology Construction and Channel Frequency Allocation in the TOWN Project[J]. Computer Engineering and Networks Laboratory TIK-Report 255, 2006.
[22] Seongho CHO and Chong-kwon KIM. Interference-Aware Multi-Channel Assignment in Multi-Radio Wireless Mesh Networks[J]. IEICE Transactions on Communications, 2007, 1436-1445.
[23] Leiming Xu, Yong Xiang and Meilin Shi. A novel channel assignment algorithm based on topology simplification in multi-radio wireless mesh networks[C]. Performance, Computing, and Communications Conference, 2006.
[24] SeyedAlireza hasem and hiraziand amidreza lllindavar. A Hybrid Method For Channel Assignment Problems in Cellular Radio Networks. Wireless Communications and Networking Conference[C]. 2006, 1260一1265.
[25] Cozzens M B and Roberts F S. T-colorings of graphs and the channel assignment problem[J]. Congressus Numerantium, 1982, 35:191-08.
[26] B. A. Tesman. List T-colorings of graphs[J]. Discrete Applied Math. 45. 1993, 277-289.
[27] M. Yannakakis and F. Gavril. The maximum k-colorable subgraph problem for chordal graphs[J]. Information Processing Letters 24, 1987, 133–137.
?
[28] S.T. McCormick. Optimal Approximation of Sparse Hessians and its Equivalence to a Graph Coloring Problem[J]. Mathematical Programming, 1983, (26):153–171.
[29] M. R. Garey , D. S. Johnson and L. Stockmeyer, Some simplied NP-complete graph problems[J]. Theoretical Computer Science, 1976, 237-267.
[30] Griggs, J. R. and R. K. Yeh. Labeling graphs with a condition at distance 2[J]. SIAM J. Disc. Math. 5, 1992, 586-595.
[31] Chang, G. J. and D. Kuo. The L(2,1)-labeling problem on graphs[J]. SIAM J. Disc. Math. 9 1996, 309-316.
[32] T.A. Lanfear. Graph theory and radio frequency assignment[J]. Technical Report NATO Unclassified, Allied Radio Frequency Agency (ARFA), 1989.
[33] R.M. Karp. Reducibility among combinatorial problems[J]. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, 1972, 85-103.
[34] K.I. Aardal, A. Hipolito, C.P.M. van Hoesel, and B. Jansen. A branch-and-cut algorithm for the frequency assignment problem[J]. Research Memorandum 96/011, Maastricht University, 1996.
[35] J.R. Griggs and D.D.-F. Liu. The channel assignment problem for mutually adjacent sites. Joumal of ComfcinatoriaZ Theory[J]. 1994, 169-183.
[36] M. Kubale. Interval vertex-coloring of a graph with forbidden colors[J]. Discrete Mathematics, 1989, (74):125-136.
[37] M. Kubale. Some results concerning the complexity of restricted colorings of graphs[J]. Discrete Applied Mathematics, 1992, (36):35-46.
[38] D.H. Smith, S. Hurley, and S.U. Thiel. Improving heuristics for the frequency assignment problem[J]. European Journal of Operational Research, 1998, 107:76-86.
[39] R. Mathar and J. Mattfeldt. Channel assignment in cellular radio networks[J]. Transactions on Vehicular Technology, 1993, 42:647-656.
[40] M.G. Kazantzakis, P.P. Demestichas, and M.E. Anagnostou. Optimum frequency reuse in mobile telephone systems[J], International journal of Communications Systems, 1995, 8:185-190,.
[41] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory and Applications[J]. Prentice Hall, New Jersey, 1993.
[42] R. Borndorfer, A. Eisenblatter, M. Grotschel, and A. Martin. Frequency assignment in cellular phone networks[J]. AnnaLs of Operations Research, 1998, 76:73-94.
[43] D. Brelaz. New methods to color the vertices of a graph[J]. Communications of the ACM, 1979, 22:251-256.
[44] D. Costa. On the use of some known methods for t-colourings of graphs[J]. Annais of Operations flesearch, 1993, 41:343-358.
[45] T.J. Kahwa, and N.D. Georganas. A hybrid channel assignment scheme in large-scale cellular-structured mobile communication systems[J]. IEEE Transactions on Communications COM-26, 1978, 432–438.
[46] Betrossi, A.A. , Pinotti, C.M and Tan, R.B. Efficient Use of Radio Spectrum in Wireless Networks with Channel Separation between close Stations[J]. in Proc of the DIAL M for Mobile workshop, 2000, 18-27.
[47] Subramanian A, Krishnan R, Das SR, and Gupta H. Minimum interference channel assignment in multi-radio wireless mesh networks[J]. Sensor, Mesh and Ad Hoc Communications and Networks, 2007, 7(4): 481-490.
[48] H. Skalli, S. Ghosh, S. K. Das, L. Lenzini, and M. Cont. Channel assignment strategies for multi-radio wireless mesh networks: Issues and solutions[J]. IEEE Communications Magazine, Special Issue on“Wireless Mesh Networks”, 2007.
[49] J. So and N. Vaidya. Multi-channel MAC for ad hoc networks: Handling multi-channel hidden terminals using a single transceiver[J]. in Proc. ACM Mobihoc, 2004, 222-233.
[50] S. Wu, C. Lin, Y. Tseng, and J. Sheu. A new multi-channel MAC protocol with ondemand channel assignment for multi-hop mobile ad hoc networks[J]. submitted to the International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN), 2000.
[51] C. L. Barrett, G. Istrate, V. S. A. Kumar, M. V. Marathe, and S. Thite. Strong edge coloring for channel assignment in wireless radio networks[C]. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, 2006.
[52] Chae Y. Lee and Hyon G. Kang. Cell Planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach. Vehicular Technology[J]. IEEE Transactions on. 2000, 49(5) :1678-1691.
[53] Tamura, H.Watanabe, K.Sengoku, M.Shinoda. on a new edge coloring related to multihop wireless networks[J], Circuits and Systems, 2002, 357- 360.
[54] Jain N, Das S, and Nasipuri A. A multi channel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks[J]. IEEE International Conference on Computer Communications and Networks (IC3N), 2001.
[55] H. Skalli, S .K. Das, and L. Lenzini. Traffic and interference aware channel. assignment for multi-radio Wireless Mesh Networks[J]. Technical report, 2006.
[56] Chun-chen Hsu, Pangfeng, Liu,Dawei Wang. Generalized edge coloring for channel assignment in wireless networks[J]. Parallel Processing, 2006, 82-92.
[57] A. Proskurowski, and M. M. Syslo, Efficient vertex and edge coloring of outerplanar graphs[J]. SIAM J. Algebraic and Discrete Methods, 1986, 7:131–136.
[58] S.M. Allen. Frequency assignment problems: subgraph generation for lower bounds[J]. Technical Report UG-M-98-2, Division of Mathematics and Computing, University of Glamorgan, 1998.