Research On Graph Coloring And Applications In Wireless Network Channel Resource Allocation

With the rapid development of communication technology and the increasing demand for a variety of applications, next generation wireless communication networks are expected to provide ubiquitous high data rate coverage in the most cost effective manner. Because of the scarcity of radio spectrum resource in wireless communications networks, how to efficiently utilize spectrum resources is an important research topic.Graph theory is an important part of discrete mathematics and operations research, and it is an important branch of modern applied mathematics. Graph coloring is one of the main problems in graph theory, and it has essentially theoretical and practical significance. Graph coloring is closely related with assignment problem, and it is a useful tool in modeling a wide variety of frequency assignment problem (also known as channel assignment problem) in communication area. This thesis presents the basic concepts of graph coloring and introduces several variants of graph coloring, such as set coloring, set T-coloring, incidence coloring, adjacent vertex distinguishing edge coloring and adjacent vertex distinguishing equitable edge coloring, and their applications are studied in wireless network channel resource allocation.The main research work and innovations are as follows:(1) Radio frequency identification (RFID) as a significant branch of automatic identification technology has been developing rapidly for the last few years. RFID has been an essential and widespread infrastructure technology in Internet of Things, supply chain management, intelligent traffic service, and many other areas. In multiple reader RFID environments, multiple readers are deployed in a predetermined place to provide high read rate while keeping the correctness of reading. However, several collision problems might occur when multiple readers are used within close vicinity, affecting the performances of the system. This thesis discusses the RFID interference and reader collision problem, and develops a multi-graph model. The set coloring and set T-coloring are proposed to alleviate reader collision problem in the multiple reader environments. Compared to other existing methods, the proposal adopts time division technique to solve the tag interference and frequency division technique to solve the frequency interference. The proposal can effectively avoid reader conflict problem and improve the performance of system with assignment of a lower amount of frequency and slot resources.(2) In wireless communication networks, multiple hop relay technology can enhance the system capacity and coverage with a lower network cost; improve the cell edge users’ Quality of Service (QoS). However, multiple hop relay network must allocate some additional resources to the relay links compared with the traditional single hop network. Thus, an efficient resource allocation scheme needs to be designed to improve system performances. In this thesis, a novel channel assignment framework is presented based on incidence coloring for orthogonal frequency division multiple access (OFDMA)-based multiple hop cellular networks, which aims at suppressing multi-links interference and enhancing spectral efficiency. The concept of incidence coloring from modern graph theory is utilized to recast the original frequency assignment problem and guide the solution from graph theory perspective. In addition, a novel cellular architecture is designed, and an efficient frequency assignment scheme based on incidence coloring is proposed. System level simulation results demonstrate that the frequency assignment scheme can effectively mitigate inter-cell interference (ICI) and significantly improve spectral efficiency and system performances.(3) With global informatization and the development of the wireless network, the rural wireless network is a key technology in the development of rural informatization and sustainable realization. Wireless mesh network is easy to be set up with low cost, and has a flexible organizational structure and scalability, which will become an effective solution for rural informatization construction. In this thesis, a new channel assignment framework based on graph coloring is presented for rural wireless mesh networks. The goal of the framework is to allow synchronously transmitting or receiving data from multiple neighbor links at the same time, and continuously doing full-duplex data transfer on every link, creating an efficient rural mesh network without interference. This channel allocation problem is framed in terms of adjacent vertex distinguishing edge coloring. The issue of joint utilization and balance in channel assignment for rural wireless mesh networks is addressed. A new channel assignment framework is designed with the goal of optimizing the channel resource utilization across the entire network while taking balanced allocation into account. This optimization problem is formulated as an adjacent vertex distinguishing equitable edge coloring. The proposed framework is then evaluated on some Cartesian product graphs and Join graphs. The results show that the channel allocation framework proposed is feasible and effective in standards such as IEEE802.11a.