Research On The Graph Labeling For Frequency Assignment Problems Inwireless Networks

With the rapid development of wireless communication services, the contradiction between limited frequency resources and the increasing demand of users has become more and more prominent. Frequency assignment problem in wireless networks studies how to optimize the assignment of frequency resources for the wireless network nodes, making the entire wireless network with minimum communication bandwidth is one of the most important approaches to solve this problem, and also one of the basic scientif-ic issues which is a common concern of both domestic and international academia and industry. In order to improve the signal to noise ratio of the received signal, it requires that the closer the distance between the transmitting antenna, the greater the frequency difference of the frequencies they use should be, then we can transform the frequency assignment problem into the following graph labeling problem:each antenna is repre-sented by the vertex of undirected graph; connect the vertices that may have possible interference with edges, adjacent vertices cannot use the same frequency that is to say they cannot use the same color so that the frequency assignment problem is transferred into the graph coloring problem; furthermore, each frequency is represented by a number, requiring that not only each antenna should be assigned with different frequencies, but also the frequency difference between adjacent nodes should meet certain constraints so that frequency assignment problem is transformed into a graph labeling problem.As for the frequency resources configuration issues in cases where distance between the base station is small and the frequency resources is insufficient and so on, this thesis studies the corresponding graph labeling problem and grid graph labeling problem and has made some valuable theoretical and simulation results. The main research results and innovations are as follows:1. Research on frequency assignment problems under relaxed conditionsUnder the condition of a frequency resource shortage, the optimal frequency assign-ment plan that satisfies all the constraint conditions may not be got, hence it is necessary to sacrifice some communication quality (i.e., to allow some nodes that do not fully satis-fy the constraints) as a precondition to find a frequency assignment plan that satisfies the most constraint conditions. It is called the frequency assignment under relaxed conditions by using relaxed graph labeling model to assign frequency with the minimum conflict-s between pairs of nodes. The contribution of this thesis to this problem is as follows: â‘  By constructing two special 3-regular graph, as for the conjecture posed by Lin etc. on the relationship between the wireless communication network minimum bandwidth consumption and the max degree of corresponding graph under relaxed condition, this thesis gives a counter-example of the two conjectures and mathematical proof to prove that the conjecture does not hold; â‘¡ The frequency assignment problem of 8-regular net-work modeled by 8-regular grid graph is studied. Moreover, the relationship between the minimum frequency bandwidth and relaxed condition in 8-regular grid graph is analyzed by using computer search and mathematical proof. As a result, many optimum frequen-cy assignment schemes under various conditions of relaxation are obtained; â‘¢ A new backtracking algorithm is proposed and it is applied to calculate the frequency optimized assignment scheme of two and three dimensional balanced hypercubes. The simulation result shows the relationship between the minimum bandwidth and relaxation conditions is consistent with that from 8-regular grid graph.2. Research on the frequency assignment problem with the distance 4 con-straintsIn some wireless networks, the distance between nodes may be very close, It is required to consider the interference problem between not only the neighboring nodes (distance 1) and the little further nodes (distance 2), but also the further node interference problems. In this paper, we use the distance 4 graph labeling model to solve the frequen-cy assignment problem in the network with a distance between nodes no more than 4 constraints. Contributions include:â‘ As for the high computational complexity of the distance 4 labeling problem, a satisfiability problem model with inequality constraints based on the Boolean variable is proposed, solving some minimum frequency bandwidth of grid graph under the distance 4 constraints through the way of computer searches and mathematical proof;â‘¡As for the minimum frequency bandwidth of some loop graph under the distance 4 constraints is unknown, a dynamic algorithm based on the auxiliary graph is proposed and the distance 4 labeling number of cycles with arbitrary length are obtained.â‘¢The distance 4 labeling number of a path or a cycle, or prismatic grid graph is still unknown, and it is researched by using mathematical proof together with a Pseudo-Boolean SAT model. Moreover, a greedy label algorithm of graph is applied to search the distance 4 labeling number of a graph. As a result, the upper bound of the distance 4 labeling numbers of prismatic and torodial grid graphs are given. Finally, experimental simulation is carried out to show the performance of the algorithm described above.3. Research on classification of the labeled graph based on graph isomorphismIn the frequency assignment problem in wireless networks based on the graph la-beling, some performance indicators of frequency assignment algorithm (such as the maximum number of frequency reuse, the minimum frequency reuse distance, etc.) is closely related to the structure and location of the nodes of the graph. In this paper, an isomorphic labeled graph search algorithm is proposed to obtain the classification results of grid labeled graphs which has the identical structure as equivalence classes, and the graph symmetrical results are presented and analyzed. By using this algorithm, the clas-sification results of the labeled graphs are given. Computational results show that some graphs have a specific number of classifications. Simulation results show that frequen-cy assignment results corresponding to the same type of the labeled graphs have some similar performance characteristics.