Professor Abdel Lisser

Jin-Kao Hao

Keywords:

Their

comments are so valuable and so essential

Chapter 1

Introduction

This chapter aims to provide a thorough overview of the contents in this thesis. Firstly it introduces the context of our research topic focusing on new graph coloring method and its corresponding applications. Then the objectives and contributions are demonstrated to present the general idea of our topic. Finally, the organization of all the thesis is briefly shown providing a guide for the following chapters.

Context

The graph coloring problem originates from a practical problem in 1852, when Francis Guthrie was trying to color the map of the counties of England [START_REF] Kubale | Graph colorings[END_REF]. He found an interesting thing that four colors are sufficient to color the map such that all adjacent counties have different colors. So the famous conjecture called the four color problem was born stating that "every planar graph is four-colorable" [START_REF] Wilson | Four colors suffice: how the map problem was solved[END_REF]. After more than 120 years, in 1976, Kenneth Appel and Wolfgang Haken proved the conjecture using a computer. Nowadays, although the computer's computing capability increases dramatically, the old graph coloring problem is still mysterious and fascinating.

The reason that researchers have never been stopped exploring this traditional problem is mainly because of its hardness. Graph coloring problem is a well-known NP complete problem, which has been proposed for more than 160 years but it is still intractable.

Up to now, no algorithm can get the proper coloring solution for an arbitrary graph in a polynomial time. However, graph coloring has been ubiquitously used in plenty of practical applications. In a lot of cases, it is so useful that it can greatly increase the efficiency of our industrial production.

Although there have been a large number of graph coloring algorithms in the former articles, including exact algorithms and heuristic algorithms, the algorithm complexity is still the bottleneck for its application. Besides, different practical problems are supposed to be modeled as different graph coloring problems according to different constraints.

So far, it is really necessary to study the traditional graph coloring problem from new perspectives.

To some extent, the solution of graph coloring largely relies on graph structure. For instance, for some special graphs such as complete graphs, even the greedy algorithm is able to get the best solution benefiting from their peculiar structure. A graph can be decomposed into maximal cliques and vertices inside each maximal clique should be colored differently. The connection between these maximal cliques leads to different graph coloring solutions. From this point of view, a new graph coloring strategy is proposed, called graph-structure-based coloring strategy. The Total solutions Exact graph Coloring algorithm (TexaCol), proposed by Jean-noel MARTIN, is based on this strategy. However, it has a lot of limitations which directly confines its application.

Despite the ability of getting all proper coloring solutions, TexaCol can only deal with very small graphs, and it costs a lot of time and computer's memory. Thus, further improvement of TexaCol is interesting and meaningful, which is possible to greatly increase its application ability.

Device-to-Device (D2D) technique has great potential in the mainstream telecommunication systems, such as Long-Term Evolution (LTE), LTE-Advanced and 5th generation wireless systems (5G). Not only can it provide the facility for proximity communication and increase the network coverage, but it is also able to increase the data rate and traffic offloading for the base station. However, the resource allocation problem is a bottleneck to influence the performance of D2D networking. How to design effective resource allocation algorithm for D2D network in LTE system is a challenging problem.

In order to well organize large quantity of devices in the LTE network, some clustering mechanism is used to group numerous D2D links into clusters. Under this circumstance, the systematic resource allocation scheme involves two parts: the intercluster resource allocation and the intra-cluster resource allocation. By calculating the interference range for inter-cluster or intra-cluster, these two kinds of resource allocation problem can be modeled as two different graph coloring problems respectively. Note that the graph coloring problem here is different from the traditional one, as it either has new optimization objective or incorporates new constraints. For the inter-cluster resource allocation, clusters can be dynamically formed or deleted. Corresponding to their interference topology graph, the vertices can be added or deleted. So the graph coloring problem here is based on a dynamic topology with which the traditional graph coloring method cannot be used directly. It requires a new graph coloring mechanism to be well adapted to the topology change. As for the intra-cluster resource allocation, it is necessary to decide the power allocation and Resource Block (RB) allocation for each D2D link, making a trade-off between the throughput and the number of RBs.

Actually, it is a joint optimization problem. To simplify the case, we design a mechanism to choose the topology while coloring the graph each step in order to get a solution with good throughput and resource utilization.

Since these two resource allocation algorithms are based on topology, they can also be considered as graph-structure-based, which is the inherent characteristic of our graph coloring algorithms. So, naturally, our graph-structure-based coloring algorithm is suitable for solving the cluster-based resource allocation problem. Effective new algorithms are expected based on our graph-structure-based algorithms to optimize the resource allocation for D2D links in LTE system.

Objectives and contributions

Our work aims to study the graph coloring problem from a new perspective and to apply it to solve some practical problems in LTE systems. The main object of our research is to design effective graph coloring algorithms from a graph-structure point of view.

Since graph structure can greatly influence on graph coloring, some new graph coloring algorithms can be designed besides the traditional methods. The second goal of our work is to use the proposed graph coloring algorithms to solve the realistic problems.

Because of its tight relationship with graph topology, our graph coloring algorithms are suitable to solve the inter-cluster and intra-cluster resource allocation problem in D2D network in LTE system.

Generally, there are three main contributions in this thesis, which are listed as follows.

• First, as the basis of the following research, TexaCol is deeply studied. By implementing TexaCol in C++, plenty of tests are carried out and its performance is comprehensively evaluated. The test results with TexaCol on a great number of graphs are shown in the thesis. From the results, it is shown that TexaCol is extremely limited due to its high computational complexity and it can just deal with very small graphs. The analysis of TexaCol is a motivation for its further improvement.

• Second, two main improvements of TexaCol are proposed, called Partial best solutions Exact graph Coloring algorithm (PexaCol) and All best solutions Exact graph Coloring algorithm (AexaCol) respectively. PexaCol utilizes the backtracking method to choose the best column to calculate each step until one best column for all the graph is obtained. So it is able to get partial best solutions with a much faster speed. AexaCol will not stop the calculation until all best columns of the graph are achieved, thus it can get all best coloring solutions. By comparing with TexaCol, these two algorithms are able to deal with larger graphs and run much faster than it. Especially, given a graph, AexaCol is able to get all best solutions much faster than the famous solver Gurobi. Furthermore, the impact of node's coloring sequence on the number of columns is investigated providing some theoretic foundation for the further heuristic improvement.

• Third, the proposed graph coloring algorithms are used in solving resource allocation problems for D2D communication in LTE cellular network. A systematic architecture of D2D networking is proposed, which uses the clustering to manage all the devices in a cell. Thus the resource allocation problem contains two parts:

inter-cluster resource allocation and intra-cluster resource allocation. As for the inter-cluster resource allocation problem, a dynamic cluster resource allocation algorithm is proposed to assign time-frequency resources to the dynamic cluster.

This algorithm can achieve higher resource utilization compared with some other algorithms and can be well adapted to the cluster generation and deletion. For the intra-cluster resource allocation problem, a topology control related graph coloring method is proposed to allocate RBs to D2D links within a cluster. In this method, a suboptimal solution for power and time-frequency resource allocation is achieved by locally choosing the best power for each node to maximize the throughput and minimize the number of time-frequency resource. Based on different graph coloring mechanisms, four resource allocation algorithms are designed. The result analysis shows their superiority for different scenarios.

Outline

In Chapter 2, some background knowledge about graph coloring problem are presented. The relevant concepts about graph coloring are introduced. Then, the state of art of two kinds of algorithms, exact algorithm and heuristic algorithm, is provided in detail. Especially, the related works on graph coloring correlated with graph structure are summarized, as the background knowledge for our algorithms.

In Chapter 3, firstly, we introduce the definition and the algorithm process of TexaCol, which is the base for this thesis. Then, further studies about TexaCol are presented, including the difference between other traditional graph coloring algorithms, the C++ implementation and the limitation analysis. Since it is really complicated, some useful examples are provided to illustrate the algorithm process.

Chapter 4 is engaged on the improvement of TexaCol. Two algorithms, PexaCol and AexaCol, are proposed in this chapter to obtain partial and all best solutions for the input graph. This chapter includes the strategy of the improvement, algorithm process, example and the result analysis. Moreover, to further develop the possible heuristic strategies based on PexaCol, the impact of the node's coloring sequence on the number of columns is introduced.

Chapter 5 is devoted to apply the proposed graph coloring algorithms to solve the practical problems in the LTE or LTE-Advanced system. A systematic method of resource allocation for D2D communication in LTE system is proposed on the basis of clustering mechanism. The method contains two parts: the inter-cluster resource allocation and the intra-cluster resource allocation. For the first part, a dynamic cluster resource allocation algorithm is proposed, which has advantage in resource utilization, runtime and scalability. For the second part, a topology-based resource allocation scheme is designed to locally choose the best topology while doing the resource allocation to achieve a suboptimal solution for the power and RB allocation. Based on this scheme, four resource allocation algorithms are designed with different graph coloring methods.

Chapter 6 is the conclusion of all the thesis and some future works are proposed.

Chapter 2

Graph Coloring Problem

This chapter is dedicated to state the traditional graph coloring problem with strict mathematical definitions. It is necessary to present relevant concepts of graph coloring which are important for the aftermentioned chapters. Then, the classification for graph coloring is summarized to well define the type of graph coloring problem studied in this thesis. The graph coloring algorithms, including exact algorithms and the heuristic algorithms, are reviewed in this part, as the related work of our algorithms. Finally, the applications of graph coloring are stated.

Introduction

Graph coloring is one of the most important parts in graph theory since it was born more than 160 years ago. Although apparently the formulation of the graph coloring problem is simple, it is the abstract of the realistic world, which reflects the intricate relationship between different things. By exploring various graph coloring methods, graph coloring is capable of solving a great number of practical problems just like an effective or even powerful tool.

This chapter aims to provide some basic knowledge of graph coloring, which is the foundation of the aftermentioned chapters. First of all, the definitions of graph and graph coloring are given providing a fundamental mathematical framework. These definitions not only constitute the mathematical base for graph coloring, but also can help to well confine the discussion to our topic. To further clarify the type of graph coloring problem researched in this thesis, different ways of classification are presented.

Then existing graph coloring algorithms, including exact algorithms and heuristic algorithms, are introduced as the related works for our graph coloring algorithms. In this part, various categories of graph coloring methods are stated and compared, providing a basic view of the field.

Finally, we focus on the graph coloring applications. In the past several years, graph coloring problem has been widely used in the industrial or commercial fields. In spite of this, only the most popular applications are displayed.

Definitions of graph Definition 2.1.

A graph G is a pair (V, E), noted as G = (V, E). V is a non-empty set called vertex set, including all vertices. |V | denotes the number of vertices. E is the edge set including all edges, i.e., pairs of vertices. Note that the same pair of vertices can appear more than once in E. If edges have the direction, the graph is called directed graph; otherwise, it is called undirected graph.

Note that in this thesis, vertex is also called node and they can mutually substitute.

Definition 2.2.

A simple graph G is an undirected graph which has neither loops nor multiple edges.

Definition 2.3.

A complete graph G is a simple graph in which there is an edge between arbitrary two vertices.

Definition 2.4. If V (G ) ⊆ V (G), E(G ) ⊆ E(G), and if the number of multiple edges for each edge in G is no more than that for each edge in G, G is called a subgraph of G.

Definition 2.5. The degree of the vertex v in the graph G is the number of edges associated to v. For the graph with loops, each loop should be counted twice.

Definition 2.6. If the vertices of graph G are marked by the numbers 1, 2, ..., n, the adjacent matrix of G is a square matrix, noted as A = (a ij ), 1 i, j n. If the vertex v i is adjacent to the vertex v j , a ij = 1; otherwise a ij = 0.

Definition 2.7. The clique is a subset of vertices in which the vertices are mutually connected.

Definitions for graph coloring problem

Definition 2.8. Given an undirected graph G(V, E) with V , the vertex set, and E, the edge set, a k-coloring of G is an allocation of one color to each vertex such that each vertex has a color from the color set {1, 2, . . . , k}.

Definition 2.9. The vertex coloring of a graph G is a proper coloring if all nodes are colored and all neighboring nodes are colored differently. If at most k colors are used for the proper coloring, it is called proper k-coloring.

Definition 2.10. The graph coloring problem is to find the minimum k, satisfying that a proper k-coloring for a given graph G can be obtained.

Definition 2.11. The chromatic number is k, denoted by χ, if at least k colors are required for the proper coloring. The chromatic polynomial is a function of k, denoted by P G (k), which counts the number of different proper coloring solutions for a given graph G.

Classification of graph coloring

Based on the concepts in [START_REF] Lewis | A Guide to Graph Colouring[END_REF], graph coloring can be classified into two types: complete graph coloring and partial graph coloring. Meanwhile, it can be classified into two other categories: proper graph coloring and improper graph coloring.

Definition 2.12. If all vertices have been colored, it is called complete graph coloring; otherwise, it is partial graph coloring.

Definition 2.13. If all adjacent vertices are colored differently, it is called proper coloring; otherwise, it is improper coloring.

Therefore, there are four kinds of graph coloring approaches: complete proper graph coloring, complete improper graph coloring, partial proper graph coloring and partial improper graph coloring. These approaches differ in solution space contributing to different heuristic methods, as shown in [START_REF] Lewis | A Guide to Graph Colouring[END_REF]. In this thesis, only the complete proper graph coloring is researched without mentioning that all middle steps in the process can be reckoned as a partial proper graph coloring.

Another way to do the classification depends on the object to which the color is assigned. Generally, the graph coloring is categorized into two classes: vertex coloring and edge coloring.

Definition 2.14. If the colors are allocated to the vertices, it is the vertex coloring; On the other hand, if the colors are allocated to the edges, it is the edge coloring.

In these thesis, the graph coloring problem discussed is only confined to vertex coloring.

Graph coloring algorithms

In general, there are two kinds of methods for coloring a graph: the exact methods and the heuristic methods. The exact methods are capable of attaining the best solution for a given graph while the graph's size is small [START_REF] Malaguti | An exact approach for the vertex coloring problem[END_REF][START_REF] Mehrotra | A column generation approach for graph coloring[END_REF], however, it is really limited to solve practical problems which are often modeled as larger graphs. The heuristic methods can deal with much larger graphs, nevertheless, they cannot guarantee to get an optimal solution. So far, in order to solve graph coloring problem, a lot of heuristic algorithms have been proposed while there are very few exact algorithms.

As a matter of fact, many heuristic algorithms make use of certain exact algorithms to search the local optimal solution whereas the global optimization is managed by their specific heuristic strategy. Thus, in these kind of heuristic algorithms, both exact methods and heuristic strategies are indispensable.

Exact algorithms

As a simple and direct exact method for combinatorial optimization problems, the enumeration method can get exactly the best coloring solution for a graph. Nevertheless, as it is mentioned before, the graph coloring problem is a NP-complete problem. In other words, the best result cannot be found with the simple enumeration method in a polynomial time for an arbitrary input graph. Searching the best solution with the enumeration method is almost impossible while the number of vertices becomes large enough. In spite of this, studying different enumeration methods can make a worthwhile contribution to some useful exact methods, such as the backtracking method [START_REF] Émi | On the analysis of backtrack proceduresfor the colouring of random graphs[END_REF].

Backtracking is a traditional exact algorithm, which gradually constructs and evaluates a feasible partial solution until it becomes a feasible complete solution. During the process, if no further extention for a feasible partial solution can be achieved, the algorithm will backtrack to a smaller feasible partial solution and continue the extending operation. So the backtracking method always ensures that a solution is feasible during the expanding phase by the feasibility judgement. This process can be called a gradual "decision and optimization" process. On the basis of the backtracking method, plenty of exact algorithms are proposed by reducing the search space, such as the Branch-and-Bound method. In [START_REF] Mehrotra | A column generation approach for graph coloring[END_REF], a Branch-and-Bound method based on a column generation model is proposed to efficiently color the graph. It utilises some specific branching rules to guarantee the tractability of the subproblem for each branch while no extra constraints are added.

Another exact method uses integer programming, which is an algebraic method frequently used for the optimization problem. The graph coloring problem can be formulated as an optimization objective and several constraints in a certain manner.

Then, it can be solved by the algebraic operation or the optimization software packages, such as CPLEX, Gurobi and XPRESS. In this process, different methods of mathematical modeling form different graph coloring algorithms. Some relevant papers can be found in [MT96, CF96, CCF04, MDZ06, MDZ08]. It is possible that some methods integrate backtracking and integer programming together. In [START_REF] Isabel M Éndez-Díaz | A branch-and-cut algorithm for graph coloring[END_REF],

a Branch-and-Cut method based on linear integer programming is designed to prune branches. In this method, the solution set is recursively divided into subsets and the problem becomes dealing with each subset. Corresponding to this process, an enumeration tree is formed in which each parent node representing the solution set has some offspring nodes representing all its subsets. With good strategy for the bound, the relaxation and branching rules, some nodes in the tree can be removed.

In this thesis, the graph coloring algorithms are designed based on a new exact graph coloring method, called TexaCol, which is proposed in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF]. This method is proposed from the graph-structure point of view and it is able to get all graph coloring solutions by gradually partitioning the coloring cases. It is similar to the enumeration method but uses a new data structure to well deal with the coloring process. Although it is also unefficient for large graphs, it provides a new exact approach to do the graph coloring.

Heuristic algorithms

The heuristic method seems to be the mainstream of current research on graph coloring. Substantive works dedicate to develop various heuristic strategies in order to enhance the algorithm capacity of graph coloring. Although heuristic methods cannot get the optimal solution, they are able to obtain a suboptimal solution in an acceptable time. Thus, they are dominant in numerous applications.

The most basic heuristic algorithm is the greedy method. The greedy method tries to assign the used colors which is usable to the uncolored vertices in a certain coloring sequence. This algorithm is so powerful that it is even the basis for a lot of other heuristic methods. It has very low worst-case computational complexity O(n) [START_REF] Lewis | A Guide to Graph Colouring[END_REF],

that is to say, it can always get the coloring result in a polynomial time. However, the result is sometimes so bad that the gap with the optimal solution is large. Hence the improvement of greedy method becomes necessary. It is known that the node coloring sequence in the greedy algorithm plays a vital role in enhancing its performance, since at least one of these node coloring sequences leads to the best coloring solution. A significant impetus for greedy method is to find a good coloring sequence. But the traverse of all node coloring sequences is almost impossible as the number of nodes increases. A simple method is to arrange the coloring sequence in the decreasing order of the nodes' degree, which can apparently improve the result of the greedy algorithm.

Nevertheless, this method cannot get the best coloring solution, so further improvement of greedy algorithm is expected.

In [Br é79], a famous heuristic method, called DSATUR, is proposed using the saturation degree to decide the node coloring sequence based on greedy algorithm. The saturation degree of a vertex is the number of different colors in its neighboring vertices which have been colored. The first node to color is the one with the maximal degree.

Then, the node coloring sequence is determined in the decreasing order of the nodes' saturation degree. Due to the improvement of the node coloring sequence, DSATUR performs much better than the simple greedy method. It becomes an essential submodule for several heuristic methods.

More recently, it is a trend that the heuristic graph coloring algorithm uses local search or the hybrid method combining local search with the population based algorithm [START_REF] Galinier | A survey of local search methods for graph coloring[END_REF]. These kind of methods include tabu search, genetic algorithm, ant colony optimization, simulate annealing, artificial neural networks and so on [HdW87, MS13, HY12, SE08, HZ06, KSB17, CHDW87, HHK10]. Moreover, as shown in [START_REF] Daniel Cosmin | Heuristic algorithms and learning techniques: applications to the graph coloring problem[END_REF], machine learning is successfully used in solving the graph coloring problem.

Graph coloring applications

Graph coloring problem has immense industrial and commercial applications, especially in the case of dealing with interference and conflict. Below only some traditional applications are listed while the potential applications of graph coloring are much more than these.

Frequency allocation: In the telecommunication networks, one of the key problems is the frequency allocation because of the limited physical frequency spectrum resource.

In general, the optimization problem for frequency allocation is to use minimum number Register allocation: Register allocation aims to use a large quantity of variables on the Central Processing Unit (CPU) which has only a limited number of registers [START_REF] Koes | An analysis of graph coloring register allocation[END_REF].

Supposing each variable is represented by a vertex, if the variables cannot use the register simultaneously, there will be an edge connecting their corresponding vertices.

Thus, a conflict graph is formed well defining the relationship of interference between variables. Then the graph coloring algorithm is used to get the minimum number of registers required.

Conclusion

In this chapter, the graph coloring problem is introduced from a mathematical viewpoint and related concepts are defined. The classification of graph coloring problem is presented and the graph coloring algorithms are reviewed, including exact algorithms and heuristic algorithms. Despite of its intractability, graph coloring has numerous real world applications, which further emphasizes the significance of studying in this topic.

Still, it demonstrates great potential both in the development of new algorithms and applications.

Chapter 3

Texacol

As a new exact algorithm, TexaCol provides a different perspective to color the graph. It is a graph-structure-based method and it is able to get all proper coloring solutions by partitioning the coloring cases. This chapter aims to introduce the graph-structure-based graph coloring strategy and the TexaCol algorithm, which are the foundation of our work. Then, the implementation of TexaCol in C++ is stated and the performance analysis are presented.

TexaCol is extremely limited due to its high computational complexity, so its further improvement is really indispensable. As TexaCol is the foundation for our following algorithms, in this part, the TexaCol is introduced in detail, including mathematical terms, data structure, graph-structurebased strategy, algorithm process and performance analysis. Note that in the aftermentioned parts of this thesis, the word "partial" is the counterpart of "all", but not the counterpart of "complete", differing from that in some papers. The skeleton is the initial coloring constraint for a node, which reflects the connection between a node to color and all nodes colored, and it also reflects the connection between maximal cliques. In the algorithm, each layer of skeleton is written in a bracket.

Definitions

Data structure

We use a specific data structure called column to deal with the coloring solutions. we gradually add an uncolored node's coloring constraint to the column until all nodes are colored. In Figure 3.1, the coloring result for a graph with 4 nodes is shown, which contains two columns. All coloring solutions are included in these two columns and each column is a coloring solution subset. The coloring constraint for each node is written in the corresponding bracket. For instance, in the first column, the constraint of the node 2 is [1 4], that means the node 2 is colored differently with the node 1 and the node 4.

1 2 3 4 [ ] [1] [1 4] [1 2] 1 4 2 3 Coloring sequence Solution subset 1 [ ] [-1] [1] [1 2] Solution subset 2 2 ( 1)( 2) k k k ( 1)( 2) k k k Chromatic polynomial
In the second column, the constraint of the node 4 is [-1], that means the node 4 is colored the same as the node 1. The number of colors for both columns equals 3, i.e., the chromatic number. The chromatic polynomial of both columns is indicated in the figure and each column contains 6 best solutions.

Graph-structure-based method

Graph structure analysis

For a graph G(V, E) with n vertices, apparently, the enumeration method is able to get all coloring solutions. Supposing the number of colors is k, each vertex chooses a color from the color set leading to k n coloring possibilities. After judging each possibility, all complete proper coloring solutions can be obtained. Nonetheless, searching all valid solutions in a search space of size k n can be hardly finished as n grows even when n is very small. Meanwhile, as the number of all solutions can also be extraordinarily large, it is hard to tackle them without being well arranged. Hence designing new efficient strategies to do that is a necessity.

A graph-structure-based method is proposed in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF], which is capable of getting all coloring solutions by gradually analyzing the graph structure. In this method, it is considered that a graph is composed of maximal cliques and the coloring process is conducted clique by clique. In each maximal clique, since vertices are mutually connected, they should be colored differently. So the main focus is on the coloring constraints between these maximal cliques, which leads to various coloring cases.

For instance, in Figure 3.2, the structure of a graph with thirteen vertices is illustrated, utilizing each circle with dotted line to indicate each clique. Within each circle, the vertices should be colored differently as they are connected with each other. Therefore, from the coloring point of view, the main focus is on the connections between these maximal cliques. In the figure, the connection between two maximal cliques can be considered as the vertices in the intersection of their corresponding circles. The graph coloring mostly relies on the connecting vertices between these maximal cliques. One the one hand, these connecting vertices between maximal cliques largely determine the coloring constraint for vertices in the maximal cliques. On the other hand, as they are not obligatory to be mutually connected, they are really the source bringing different coloring cases. Among these connecting vertices, some vertices can colored the same while some of them should be colored differently. In the figure, supposing it is the turn to color the vertex 5 and supposing the maximal cliques {1,2,3,4} and {6,7,8,9,10} have been colored, the coloring process is typical. Note that the vertex 5 is in the clique {3,4,5} and {4,5,6} at the same time. If the clique {4,5,6} has been colored, {3,4,5} has been colored synchronously. So the clique {3,4,5} is the satellite clique of the clique {4,5,6}. As for the maximal clique {3,4,5}, the common vertices 3 and 4 connect it to the maximal clique {1,2,3,4} and meanwhile, the vertex 6 connects the maximal clique {4,5,6} to the maximal clique {6,7,8,9,10}. Among these connecting vertices between these maximal cliques, as the vertex 3 and the vertex 6 are not connected by an edge, they lead to different coloring cases. Thus, we cannot simply say that the coloring constraint of the vertex 5 is [3 4 6], because the vertex 3 and the vertex 6 can be colored the same or differently. Two columns should be used to separately represent two coloring cases of the vertex 3 and the vertex 6.

Coloring case partition

According to the above graph structure analysis, the connection between the maximal cliques leads to different coloring cases. Actually, all these coloring cases for a graph constitute all coloring solutions. The problem becomes how to get all these coloring cases for an input graph.

The specific data structure column is used to do the coloring case partition until all coloring cases are traversed without repetitions. Each column is a coloring solution subset for the subgraph including all colored vertices. By gradually adding the coloring constraint of an uncolored vertex to each column, new coloring cases are partition based on the old columns. In this way, until all vertices have been colored, all proper coloring solutions are obtained in the form of columns. In other words, all proper coloring solutions are partitioned into solution subsets, each of which represents a coloring case.

The coloring case partition combining with the graph structure analysis is the essence of TexaCol. It is able to do the coloring clique by clique while partitioning the coloring cases.

Algorithm of TexaCol

The graph-structure-based algorithm TexaCol includes three steps: maximal clique decomposition, suite construction and vertex coloring. The first two steps are the prerequisite for the third step, which is the most complicated and most essential part in TexaCol. Note that the implementation of the first two steps here are not exactly the same as that in the original edition of TexaCol in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF], which has no influence on understanding the essence of TexaCol. The main algorithm process of TexaCol is shown in Algorithm 1. For each phase and the key functions, they are introduced in detail in the following subsections.

Maximal clique decomposition

This step reflects the basic idea of coloring based on graph structure, which decomposes a graph into maximal cliques. It can be done by searching from each vertex recursively until all maximal cliques have been obtained. Starting from the vertex with the minimum index, to simplify the search process, it is confined that only the vertices whose index is larger than that of the vertices added in the clique are considered as the candidate vertices (see Algorithm 2 and 3).

Suite construction

In this phase, the purpose is to determine an advantageous sequence of maximal cliques, so that the cliques having more connection relationship with the others can be colored first. This coloring sequence for the maximal cliques is called the suite. There are two criterions to evaluate the connection relationship: maximal contact and maximal constraint. The maximal contact is obtained by comparing the number of vertices in the intersection between vertices in each remaining clique and all the colored vertices. The maximal constraint reflects the relationship between cliques by the degree of vertices in the clique. Formally, the constraint for each clique is calculated by Formula 3.1. Let D(G) be the set of all cliques {c 1 , c 2 , ..., c n }, c i ∈ D(G), i = 1, 2, ..., n. d(v) is the degree of vertex v and |c i | is the number of vertices in clique c i .

constraint(c i ) = v∈c i d(v) -|c i | (|c i | -1)/2 (3.1)
The algorithm description of suite construction is shown in Algorithm 4. The first clique in the suite is chosen having the maximal constraint and then the cliques are gradually chosen having the maximal contact. The nodes' coloring sequence is determined by the sequence of their appearance in the suite.

Vertex coloring

The purpose of the vertex coloring is to divide the coloring cases by analyzing each node's skeleton. If there is only one layer for one node's skeleton, the new coloring constraint of this node is the same as its skeleton and no other different possibilities of coloring. If one node's skeleton has two layers, there are different possibilities of coloring. For instance, some nodes in layer 2 may have the same color with some nodes in layer 1. So in this case, by adding this node's skeleton to a column and treating it, it will generate multiple new columns, in which the new coloring constraint of this node is attained and the relevant colored nodes' coloring constraints are changed according to different coloring cases. A simple example is given to explain this process. Suppose in the coloring process, the node to color is the node d, whose skeleton is the update for the corresponding nodes' coloring constraint is necessary ensuring that the node e and the node a are colored differently. For the second column, as the node c and the node a have different colors, the coloring constraint of the node c is changed to [e a] and this change implies that the node e and the node a are colored differently.

The main function for vertex coloring is the function skeletonT reatment(), which is used to get the new solution after adding a new node's skeleton (see Algorithm 5).

The input of this function is a column for some colored vertices and the output is new columns newColumns. It has two phases: the pretreatment and the treatment. In the pretreatment phase, the skeleton is modified according to the coloring constraints of the input column. In the treatment phase, we deal with the solution to treat, i.e., solutionT reat, in which the coloring constraint for each vertex is called a cell. The cell can possibly have two layers as that in the skeleton. The essence of this algorithm is to gradually transfer the two-layer cell into one layer, until the final solution without two-layer cells can be achieved, corresponding to the process of gradually partitioning coloring cases. In order to do this, all vertices which can possibly be colored the same are searched. If one pair of vertices can have the same color, i.e., there is no conflict between them, two coloring solutions can be attained. One of them corresponds to the case that they have the same color, while the other one means they have different colors. By continuously partitioning the case that some vertices have the same color or not, the convergence of this algorithm is guaranteed.

C++ implementation

For the original TexaCol in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF], the TexaCol is implemented with MATLAB. For the sake of more efficient implementation and the convenience for further improvement, it is recommended to implement this complicated algorithm in C++. Generally, under the same hardware circumstance, the algorithm runs faster with C++ than with MATLAB.

Example

In Figure 3.4, an example is shown illustrating the algorithm process of TexaCol. The graph has six maximal cliques and after the suite construction, the node's coloring sequence is determined, as shown in Table 3.1. Then based on the coloring sequence, the skeleton for each node is obtained according to the graph structure. For the first 7 nodes, since their skeletons have only one layer which implies no coloring case partition exists, their coloring constraints are simply equal to that in their skeletons. The coloring result for the first 7 nodes is shown at the right side in Table 3.1.

When we attempt to color the vertex 7, the coloring becomes more complicated since its skeleton has tow layers leading to multiple coloring cases. In the skeleton, the vertex 3 in layer 2 can possibly have the same color with the vertex 8 or the vertex 6 in layer 1. Thus, the skeleton treating procedure starts to get the columns correlated with these coloring cases. Supposing the first case is that the vertex 3 has the same color with the vertex 8, based on the old column including coloring constraints for the first 7 colored nodes, the coloring constraint of the vertex 8 is changed into [-3]. Since the old coloring constraint of the vertex 8 is [6 4 2], if the vertex 8 is colored the same as the vertex 3, the vertex 3 should also have different colors with vertices in [6 4 2]. With this implicit rule, the coloring constraints in the old column is updated following the coloring sequence. For instance, as the vertex 6 is colored before the vertex 3, the vertex 6 is added in the coloring constraint of the vertex 3. After all coloring constraints in this column have been updated, if there are no two-layer cells, the column will be output to the coloring result; otherwise, the process of skeleton treatment for the two-layer cells will continue. For the case when the vertex 3 is colored differently from the vertex 6 and the vertex 8, the coloring constraint of the vertex 7 is changed by simply moving the vertex 3 from the second layer to the first layer in its skeleton, i.e., from [8,6,4][3] to [8,3,6,4]. Then the coloring constraint for other related vertices should also be updated. Specially, in this case, by moving the vertex 3 from the layer 2 to the layer 1, it signifies that the color of vertex 3 is colored differently from all vertices in the layer 1. For instance, as the vertex 8 is colored after the vertex 3, at the beginning, the vertex 3 is added to the layer 2 of the coloring constraint of the vertex 8. Since in the coloring constraint of the vertex 8, the vertex 3 has different color from all vertices in the layer 1, it is then added to the layer 1. The column representing this coloring case is shown at the right side in Table 3.2.

Finally, as shown in Table 3.2, the coloring result for this graph includes three columns.

Note that the coloring case that the vertex 3 has the same color with the vertex 6 and the vertex 8 is impossible, because the vertex 6 and the vertex 8 are connected by an edge.

[ ] [ ] [ ] 4 [2] [2] [2] 5 [4 2] [4 2] [4 2] 6 [5 4 2] [5 4 2] [5 4 2] 3 [6 5 4 2] [-6] [6 5 4 2] 8 [-3] [6 4 2] [3 6 4 2] 1 [3 4 2] [6 4 2] [3 4 2] 7 [3 6 4] [8 6 4] [8 3 6 4]

Performance analysis

The performance of TexaCol is evaluated and analyzed by implementing a great number of graphs. The tests are carried out with C++ on a computer with CPU Intel Core(TM) i7-4790 (3.60 GHZ, 3.60 GHZ) and RAM 8 Go.

The first test intends to verify the number of all solutions with TexaCol, which is not evidently shown in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF]. The test graph gr n7 0 is a random graph with 7 vertices, which can be found in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF]. As the exhaustive search method is capable of enumerating all solutions instinctively, it is used to verify the result of TexaCol. As shown in Table 3.3, when the number of colors k ranges from 4 to 11, the number of all proper coloring solutions is obtained for both algorithms. As they have exactly the same result, it is experimentally verified that TexaCol is able to get all coloring solutions for gr n7 0. Further, the same experiment is executed for a large number of other randomly generated graphs, no difference for the results with these two algorithms. Another test focus on the computational capacity of TexaCol, mainly including the graph size and the runtime. In Table A.1 and Table A.2, the results for some graphs are shown.

All graphs whose name begins with "gr " are created randomly by ourselves, while all other graphs are DIMACS benchmark graphs. To provide an overview of the graph structure, the clique size as well as the frequency of its appearance for each graph are shown. V denotes the number of nodes, χ is the chromatic number and t is the runtime with the unit second.

From the result, we can see that TexaCol can deal with most of the small-scale graphs.

However, as the size of the graph becomes larger, it is incapable of finishing the algorithm because it will crash due to the memory shortage. The reason for that is as the size of the graph grows, generally more columns are generated representing more coloring case partitions. As shown in the table, even if the number of nodes is 10, the number of columns is enormous. Thus, more memory is required to store these columns causing to the abortion of the algorithm.

Concentrating on the runtime, the limitation of TexaCol is much obvious. For the graph with only 15 nodes, it costs 2 seconds. Actually, if the graph becomes much larger, the time consuming will also increase dramatically. However, this case will not appear, as it will crash first due to the memory shortage.

Conclusion

The graph-structure-based graph coloring method is introduced, which is able to get the proper coloring solutions by gradually partitioning the coloring cases. Then, as the base of our following work, the algorithm TexaCol is introduced in detail. This algorithm is composed of three parts: maximal clique decomposition, suite construction and vertex coloring. Among them, the vertex coloring is the most essential part dedicated to divide the coloring cases, which embodies the essence of the graph-structure-based method.

However, from the result analysis, the limitation of TexaCol is shown. TexaCol can only deal with the graph coloring for very small graphs (e.g., graphs with about 15 nodes).

As the number of nodes increases, getting all coloring solutions becomes intractable, since the traverse of all coloring cases can hardly be finished in a polynomial time. On the other hand, by providing a new perspective of exact graph coloring method with TexaCol, the exploration of its improvement becomes necessary.

Chapter 4

Improvement of TexaCol

Introduction

TexaCol can get all graph coloring solutions as well as the chromatic polynomial.

Although it is a graph-structure-based algorithm, it is rather cumbersome and it is incapable of rapidly obtaining multiple or all best solutions.

In the existing literatures, graph coloring algorithms to get all best solutions can be rarely found. To get only one best graph coloring solution, there have already been studies by means of analyzing the graph structure or by decomposing the graphs.

In [START_REF] Ël | Coloring a graph using split decomposition[END_REF], the graph coloring is conducted using the split decomposition tree, in which a graph is recursively partitioned into smaller graphs until they cannot be split anymore. Then, after coloring the prime graphs which cannot be split, the solutions are combined gradually to get the solutions for all the graph. In [START_REF] Bhasker | The clique-partitioning problem[END_REF], the authors research the clique-partitioning for a graph based on the principle that the graph coloring and the clique-partitioning are equivalent to some extent. Two methods are presented to partition cliques, which perform better in runtime than some efficient graph coloring algorithms. In [START_REF] Lucet | An exact method for graph coloring[END_REF], an exact graph coloring algorithm is proposed by linearly decomposing a graph, which can run faster than other exact algorithms when the linearwidth is small. The graph is dynamically decomposed into subgraphs and the corresponding boundaries between these subgraphs. Then the coloring results can be obtained by analyzing different coloring cases from these boundaries.

Another aspect is about the number of best solutions for a graph. One of the common ways to get the number of best solutions is to use chromatic polynomial.

By substituting the number of colors with the chromatic number in the chromatic polynomial, the number of best solutions is attained. There are plenty of papers that work on the chromatic polynomial. In [START_REF] Ronald | An introduction to chromatic polynomials[END_REF], the traditional method called the deletion-contraction is presented to get the chromatic polynomial which utilizes the characteristic of chromatic polynomial to do the operations to the graph. In [START_REF] Lin | Approximating the chromatic polynomial of a graph[END_REF],

an approximation algorithm is proposed to calculate the chromatic polynomial after obtaining its upper bound and lower bound, which has good performance in time complexity. From all these works, we see that our algorithm is very well suited for dealing with multiple solutions, now we need to improve its calculation performance.

In this chapter, mainly, the improvement of TexaCol is studied. Based on this graphstructure-based algorithm, an algorithm called PexaCol has been designed to get partial best solutions. Each step, instead of dealing with all solution subsets, PexaCol utilizes backtracking method to choose only the best solution subset for subgraphs to calculate until a best solution subset for all the graph is obtained. Based on PexaCol, we proposed another algorithm called AexaCol which is capable of getting the number of best solutions as well as all best solutions for a graph. Different from PexaCol, this algorithm will not stop the calculation until all best solutions are acquired. By calculating a lot of graph instances, the performance of these two algorithms has been evaluated.

Result analysis shows that PexaCol and AexaCol are able to deal with larger graphs and can run faster than TexaCol. In addition, AexaCol can run much faster than the famous solver Gurobi in getting all best solutions.

Besides, the possible heuristic improvement is studied, focusing on the influence of the node coloring sequence on the performance of our algorithm. The statistical analysis with different node coloring sequences is done seeking to get some rules for developing the heuristic strategy. Moreover, the characteristics of columns with different node coloring sequences are investigated.

PexaCol

General idea

From TexaCol, we have a simple method to get the best solution. After all columns for the graph have been obtained, we can choose the columns with the minimum number Let m be the total number of columns for subgraphs with different number of nodes and N be the total number of nodes. S i represents the column i, i = 1, 2, ..., m.

V j is the node's index, j = 1, 2, ..., N . For each column i, the number of colors is c i , and the number of nodes is n i , i = 1, 2, ..., m. The minimum number of colors required for these columns is minColor we choose again the best column among these columns, implying that if new columns require more number of colors, we go back and choose one among the old columns with less number of colors. So we call it the backtracking method. The reason why this method helps to get a best column for all the graph is explained as follows. Firstly, among columns of the subgraphs, the one requiring the minimum number of colors are more likely to cause a best column for all the graph. Then, if two columns have the same number of colors, the column with the maximal number of nodes can accelerate the coloring of all the graph. If we choose the column with less nodes, the number of colors will be more than or equal to that with more nodes, as shown in the example in the column 1, there will be two possibilities, all of which cannot be better than column 2 itself which need only 3 colors for 5 nodes. For the case of choosing column 2, it will also be two possibilities: one with 3 colors and 6 nodes, which is much better than the old column 1 and column 2; the other one with 4 colors and 6 nodes, which is no better than that while choosing the old column 1. If we choose the column 2, it is really possible that we can get a much better new column; if the better column has not been obtained, we can also do the backtracking and choose the old column 1 to continue.

= {c i |c i ≤ c j , i = j}, i = 1, 2, ..., m, j = 1,

Algorithm description

Based on TexaCol, the main flow graph for PexaCol is shown in As it is shown in Figure 4.5, after the vertex 4 has been colored, we get two columns (columns at left side), representing the case that the vertex 3 and the vertex 5 have different colors and the same color respectively. Then, after calculating each column's numColor and numN ode, the column with 3 colors is chosen, because it has the minimum number of colors. Based on this column, by treating the skeleton of the node 6 (in the dashed rectangle at the left side), two new columns are obtained (columns in the middle). Then, numColor and numN ode for these new columns are calculated.

Example

Because the column with 3 colors and 7 nodes is obviously better, it is chosen to continue. At the end, the best column for all the graph is obtained, which only requires 3 colors, i.e., the chromatic number (columns at right side).

{1,2,3} 1 [ ] [ ] {1,2,8} 2 [1] [1] {1,2,5} 3 [2 1] [2 1] {3,4} 8 [2 1] [2 1] {4,5} 5 [2 1] [2 1] {3,6} 4 [3][5] {6,8} 6 [3][8] {7,8} 7 [8][4] {4,7} [ ] [1] [2 1] [2 1] [3 2 1] [5 3] [ ] [1] [2 1] [2 1] [-3] [3] [ ] [1] [2 1] [3 2 1] [-3] [3] [8 3] [ ] [1] [2 1] [-3] [-3] [3] [3] [ ] [1] [2 1] [3 2 1] [-3] [3] [8 3] [ ] [1] [2 1] [-3] [-3] [3] [3] [4 3] 1 2 3 8 5 4 6 7 [ ] [1] [2 1] [2 1] [3 2 1] [5 3] [ ] [1] [2 1] [2 1] [3 2 1] [ 5

AexaCol

Instead of getting only a part of best solutions, AexaCol is able to get all best solutions for a given graph. Here the number of all best solutions equals the value of the chromatic polynomial when k is the chromatic number. For PexaCol, it will stop while getting a best column in which all nodes are colored, so only partial best solutions are obtained. However, to get all best solutions, we need to obtain all columns whose minColor equals the chromatic number.

It can be done in this way. After obtaining the first best column for the graph, we know the chromatic number. Then, all columns whose numColor is larger than the chromatic number will be deleted, because it is sure that they cannot be the best columns. Each step before choosing a best column to continue, all columns whose numColor is larger than the chromatic number are also deleted. Until no columns left in allColumns, all best solutions are obtained.

Algorithm description

The algorithm process of AexaCol is shown in Figure 4.6. It will not stop the calculation until all best solutions have been searched out. After the first best column has been obtained, the chromatic number is known. So the columns whose number of color is more than the chromatic number in allColumns will be deleted, which can save the computational memory and improve the algorithm efficiency. Then the calculation will continue based on allColumns, which is the same process as PexaCol.

Example

In Figure 4.7, there is an example of AexaCol. In Table 4.2, the result of allColumns is shown. Without deleting columns, there are five columns in allColumns while the algorithm is finished. The minimum number of colors for the columns is 4, i.e., the chromatic number. In allColumns, it is obvious that the column 2, the column 4 and the column 5 are best columns constituting all best columns for this graph. While for PexaCol, it will stop after getting one of these best columns.

Performance analysis

The result analysis is conducted in this section. To evaluate the performance of our algorithms, we mainly focus on the number of best solutions achieved, the number of columns and the runtime. The experiment has been implemented under the system Ubuntu 14.4 on a computer with CPU Intel Core(TM) i7-4790 (3.60 GHZ, 3.60 GHZ) and RAM 8 Go.

Comparison between TexaCol, AexaCol and PexaCol

Furthermore, the comparison has been conducted between TexaCol, AexaCol and PexaCol, as shown in

Statistical analysis of node coloring sequence impact

As the number of nodes grows, still, these two exact algorithms PexaCol and AexaCol are limited. Thus, developing some heuristic strategies to further improve their performance is truly necessary. With proper heuristic strategies, the capacity of the algorithm can be largely increased while its complexity can be effectively controlled. In this section, some heuristic explorations have been done focusing on the node coloring sequence.

For the greedy method, the coloring sequence is really significant to determine the graph coloring result. Likewise, it largely influences on the complexity of our graphstructure-based algorithms. To investigate this influence, some tests are implemented based on TexaCol, which is the original algorithm of PexaCol and AexaCol. On the basis of the statistic results, some rules are further summarized.

First of all, the statistic is given concentrating on the influence of the coloring sequence on the number of columns. In Figure 4.8, it is a graph with seven nodes, called gr n7 0, which can also be found in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF]. Some basic information about this graph is shown in The test result for gr n7 0 with different permutations of maximal cliques is shown in Figure 4.9, and that with different permutations of nodes is shown in Figure 4.10.

As the graph is pretty small, in this test, the results comprise all permutations of maximal cliques or nodes. From the result, different coloring sequence leads to different distribution of number of columns. The number of columns is nonuniformly distributed in a certain range for both the permutations of cliques and the permutations of nodes.

In the Table 4.5, we can see the comparison between these two tests. In this case, the total number of permutations for cliques is more than that for the nodes. The range of the number of columns with the permutations of nodes is larger than that with the permutations of cliques. As some permutations of nodes in coloring sequence cannot be generated only by permutations of cliques, the statistic data with the permutations of cliques is actually included in that with the permutations of cliques. In Figure 4.12, the test result with different permutations of nodes is shown for a DIMACS graph called myciel3.col, which has 11 nodes and 20 edges. Only one million of the permutations of nodes are randomly chosen to do the statistics. From the result, we can see that the number of columns varies from 51 to 3157. This phenomenon provides a significant clue of improving our algorithm. Due to large number of columns created during the coloring process, our algorithm is confined by the computational ability. As the number of columns varies according to the coloring sequence, if we can develop some heuristic schemes to determine a good coloring sequence leading to fewer number of columns, the computational complexity can be largely reduced.

Different coloring sequence leads to different number of columns, the reason of this is analyzed and some rules are concluded.

• • Rule 2: For the same graph, if we color it with two different coloring sequences and we get two different results (they have different number of columns), these two results can be also transformed between each other by the combination and decomposition of columns.

• Rule 3: Basically, for the case with different coloring sequences, the number of different columns largely relies on the number of different coloring cases in the skeleton.

In practice, to examine whether two columns are the same, it can be done by the following procedure: first fix the node coloring sequence, then transfer the second column to the first column by updating the node's coloring constraint. After the transformation of the second column, if it is not equal to the first column, signifying that they actually represent different coloring cases. For very small graphs with two different node coloring sequences, by comparing their skeleton directly, we can judge whether the corresponding columns represent the same coloring case or not.

To clearly understand the explanation above, a simple example is illustrated in Figure 4.13. For this graph with 4 nodes, with different coloring sequences, the statistics on the number of columns is shown in Table 4.6. We study the case when the number of columns equals two. Regarding the rule 1, in

[ ][ ] [ ] [ ] 4 [ ][ ] [1] [-1] 2 [1][4] [1 4] [1] 3 [1][2] [1 2] [1 2] S2 4 [ ][ ] [ ] [ ] 1 [ ][ ] [4] [-4] 2 [1][4] [1 4] [4] 3 [1][2] [1 2] [4 2] S3 3 [ ][ ] [ ] [ ] 4 [ ][ ] [3] [-3] 2 [3][4] [3 4] [3] 1 [2][3] [2 3] [2 3] S4 4 [ ][ ] [ ] [ ] 3 [ ][ ] [4] [-4] 2 [3][4] [3 4] [4] 1 [2][3] [2 3] [2 4]
Corresponding to the rule 2, the result S1 can also be transferred into S3 indirectly.

The process is shown in the Figure 4.14. We start with S1, which has two columns.

Then we use the coloring sequence of S3, and we rewrite the result of S1. From each column of S1, we get two columns, according to the case whether node 4 has the same color as node 3 or not. So, we get four columns which have the new coloring sequence.

Among them, there are two columns that can be combined together, and there is one invalid column. At last, we get two columns, which are exactly the same as that in S3

with the same coloring sequence.

[ ]

[1] [1 4] [1 2] 1 4 2 3 Coloring sequence Solution subset 1 [ ] [-1] [1] [1 2] Solution subset 2 [ ] [3] [3 4] [2 3 4] [ ] [-3] [3] [2 3] [ ] [3] [3 4] [-4] [ ] [-3] [3] [-3] 3 4 2 1 3 4 2 1 [ ] [3] [3 4] [2 3] [ ] [-3] [3] [2 3] 3 4 2 1
This column is invalid, because node 1 should have a different color with node 3. Note that the combination of two columns in one column can happen when only one of the node's coloring constraints in these two columns is different and they represent two absolutely opposite cases. To decompose a column to two columns, the process is just reversed.

With respect to the rule 3, the columns of S1 and S2 are actually identical because their skeletons have exactly the same coloring constraints. In the skeleton of S1, the coloring constraint of node 2 is [1][4], which determines specific coloring cases considering whether the vertex 1 and the vertex 4 are colored the same or not. After the node coloring sequence is changed as shown in S2, the coloring constraint of node 2 is still [1][4], and the coloring constraints for other nodes have no influence on the coloring cases. In this way, it is possible to calculate how many results are exactly the same with different coloring sequences.

From the analysis above, the node coloring sequence is a crucial factor to influence on the number of columns. Thus, by exploring the characteristics of the columns with different coloring sequences, the summarized rules have theoretical significance in devising some heuristic methods concerning the node coloring sequence and the number of columns. We did several tests on different benchmarks and observed these rules, but that was not possible from statistical analysis to obtain a systematical learning procedure which deterministically improves the performance of PexaCol and AexaCol.

Conclusion

In conclusion, the improvement of TexaCol are studied in this chapter. Two algorithms, PexaCol and AexaCol, have been proposed, which are able to get partial and all best coloring solutions respectively. Instead of calculating all columns for each subgraph, these two algorithms only choose the best column to continue the calculation each step. The result analysis shows that these two algorithms run faster than TexaCol and can deal with larger graphs. Furthermore, the proposed algorithm AexaCol can run much faster than the famous solver Gurobi to get all best solutions.

In addition, some heuristic explorations are summarized regarding the node coloring sequence's impact on the result. The coloring sequence greatly influences on the complexity of the algorithm, thus, heuristic methods based on coloring sequence is expected to develop. Meanwhile, the characteristics of columns with different coloring sequences are discussed, providing some idea of other possible heuristic methods.

Nevertheless, from the statistic analysis, it was not possible to identify a deterministic learning rule to improve the result further.

Introduction

In light of the concept of future networking, everything can be connected in a network, which incurs immense data transmission and networking coordination. For the next generation of mobile network, e.g., LTE-Advanced and 5G, D2D is quite promising to guarantee network performance, such as better network coverage, high network capacity, improved resource efficiency and low latency [START_REF] Gandotra | Device-to-device communication in cellular networks: A survey[END_REF]. However, because of the limited radio spectrum for communication, interference management and resource allocation become one of the most crucial problems for this technology [START_REF] Noura | A survey on interference management for device-to-device (d2d) communication and its challenges in 5g networks[END_REF].

Graph theory, such as graph coloring, has been widely used to solve the frequency resource allocation problems in traditional cellular networks and particularly, it has the advantage of dealing with network connection, interference and conflict. As for D2D networks, the graph theory is also appealing to model the mutual interference and optimize the RB allocation. Nonetheless, how to model the D2D resource optimization problem as well as the design of effective graph coloring algorithm determine the D2D network performance.

In this chapter, the D2D network is modeled as a series of clusters, which can be dynamically deleted and formed as that in the real scenario. Each device belongs to one cluster, otherwise a new cluster will be generated including the device. Based on this network architecture, a systematic resource allocation scheme is proposed based on D2D clusters, including inter-cluster and intra-cluster resource allocation. With the two-level resource management, this scheme is capable of well organize the resource allocation and interference coordination in the D2D networks.

For the inter-cluster resource allocation problem, the interference range and resource reuse distance are calculated as the resource allocation constraint. The dynamic cluster topology is modeled as the dynamic graph and naturally, the dynamic cluster resource allocation problem is formulated as the dynamic graph coloring problem. In order to get the coloring solution with the minimum number of colors while the graph itself is changing, a dynamic graph coloring algorithm is designed on the basis of studying the graph structure, which is capable of obtaining a sub-optimal solution and can be effectively adapted to the cluster adding and deleting. The performance of this algorithm is evaluated by numerical analysis, which shows that the proposed approach has advantage in resource utilization, runtime and scalability.

Based on cluster resources, the intra-cluster resource allocation problem engages in assigning RBs to D2D links. In a certain channel environment, since the D2D pair can communicate using different powers and the distance between two paired devices varies, the topology of the interference graph is not invariable. Thus, a topology associated resource allocation algorithm is proposed to maximize the network throughput while minimizing the number of assigned RBs. For each D2D pair, after trying different powers, it will choose the optimal power by using a specific optimal index. This optimal index is in direct proportion to the total network throughput and in inverse proportion to the number of RBs used. In this process, the graph coloring algorithm is used to get the number of RBs required. Depending on different graph coloring algorithms, four resource allocation algorithms are proposed. Typically, based on PexaCol, a special algorithm is designed which is able to dynamically assign RBs and power resource. The performance of the proposed resource allocation algorithms are compared and analyzed by some implementations with the D2D channel model. In this thesis, our resource allocation method can be available for both LTE-TDD and LTE-FDD. the bandwidth and the number of RBs in LTE system is shown in

LTE system

LTE network architecture

LTE resource

Clustering mechanism

D2D communication facilitates the proximity wireless transfer which enables wider network coverage and higher speed data transmission. In the forthcoming 5G era, it is possible that thousands of device pairs communicate mutually using D2D mode, leading to the hardness of management and coordination for the base station.

As

Applications

Since its numerous advantages, D2D technique has considerable potential applications, thus it is able to greatly improve the productivity. Some representative applications are stated in this section.

D2D resource allocation problem

Related work

Recently the resource allocation problem in D2D networks draws more and more attention, not only because it has great practical significance, but also because it is a problem of great complexity. As the network condition varies, different D2D resource allocation problems are formed considering different factors. For each formed problem, diverse methods exist. The current state of the art of D2D resource allocation problem is reviewed in this section.

Firstly, the main focus is on different sorts of D2D resource allocation problems depending on which aspects are emphasized. In the following statement, even though some aspects may be attributed to more than one category, they are classified according to their dominant characteristics. One of the D2D resource allocation problems are dedicated to join RB allocation and power allocation or interference control. In [START_REF] Yu | Power optimization of device-to-device communication underlaying cellular communication[END_REF], the optimal power assignment is conducted to well control the mutual interference between the traditional cellular links and the D2D links, thus the sum rate can be largely increased. In [START_REF] Zulhasnine | Efficient resource allocation for device-to-device communication underlaying lte network[END_REF], with the control of the eNodeB, an intelligent spectrum sharing method is designed to reduce the interference caused by DUEs to uplink and downlink communication in the cellular. By doing this, the total throughput including the CUE links and DUE links increases while the performance of the traditional cellular communication is guaranteed. In [JKR + 09], a practical interference-aware resource allocation method is proposed to mitigate the D2D-todownlink and uplink-to-D2D interference taking advantage of multi-user diversity. In [NN16, YZY + 16, FJD + 12], more literatures regarding interference management and power allocation in D2D networks can be found. In our resource allocation method, the RB allocation is tightly associated with power allocation to achieve a good tradeoff between network throughput and RB resource efficiency while the interference is well controlled.

There are also some investigations concentrating on cluster-based D2D resource allocation problem. In [SYSB16], a cluster-based resource allocation method is presented in the scenario of the D2D-based safety-critical Vehicle-to-X (V2X) communication.

The DUEs are grouped into clusters and the RBs are shared between clusters while orthogonal RBs are used for intra-cluster D2D communication. Then a heuristic algorithm using the matching theory is proposed to allocate RBs and power separately to maximize the throughput of CUEs subject to the reliability and latency constraints for DUEs. In [START_REF] Chen | Resource allocation for intra-cluster d2d communications based on kuhn-munkres algorithm[END_REF], an intra-cluster D2D resource allocation algorithm is proposed, in which the relationship of interference is modeled as a maximum weighted matching problem and the Kuhn-Munkres algorithm is employed to maximal the cluster capacity with the reusable cluster resources. Although cluster-based methods are favorable for the improvement of system throughput and the facility of device management, effective resource allocation algorithm for clusters have not been extensively studied yet. Our D2D resource allocation algorithm is also based on clusters, which comprises two part: the inter-cluster resource allocation and the intra-cluster resource allocation. For the former, the dynamic clustering mechanism is taken into account and we mainly focus on the resource efficiency, runtime and scalability. The intra-cluster resource allocation problem is dedicated to assign power and cluster RBs to D2D links to maximize the throughput while minimizing the number of RBs.

Furthermore, other D2D resource allocation problems incorporate a variety of factors.

In some studies, the RB allocation is combined with energy optimization to enhance RBs and energy efficiency [WXS + 12, WWH + 14, JLZ + 16]. In [WZZY13, ZWC + 12], the network traffic is integrated to do the RB allocation such that the Quality of Service (QoS) requirements are satisfied. Besides, as the scale of D2D network becomes very large, it is difficult to construct and maintain the graph topology, and meanwhile, the resource allocation method is hard to expand. To overcome this shortcoming, a distributed resource allocation scheme is illustrated in [START_REF] Ye | Distributed resource allocation in device-to-device enhanced cellular networks[END_REF], by employing a signaling mechanism to manage interference, as a result, the throughput of D2D links is maximized while the computational complexity is reduced. However, even with signaling, the distributed methods encounter the challenging problem of mutual coordination when the scale of D2D network is large. Other distributed resource allocation schemes can be found in [PHK13, BFA11, YYZZ13]. Although these mentioned D2D resource allocation problems are not directly related to our work, they exhibit the potential of using our method and some of them may be considered as our future works.

To solve the problems discussed above, different methods are employed in the literatures. A typical optimization method is to use the graph theory, particularly the graph coloring. Since the interference relationship between D2D links is by nature suitable to be modeled as a graph, the graph coloring can be applied to find the minimum number of RBs required when each RB is represented by a color. This kind of method appears in some existing papers. In [ZCYJ15], R.

Cluster-based D2D resource allocation scheme

Instead of allocating RBs to D2D links, for the cluster-based D2D networks, a layered resource allocation method is utilized. Generally, it comprises two levels: inter-cluster resource allocation and intra-cluster resource allocation.

The inter-cluster resource allocation is aimed at assigning RBs to clusters in order to achieve the maximal resource reuse efficiency and the minimum inter-cluster interference. The total number of RBs for D2D communication can be divided into several RB groups which are considered as the resource reuse units. The number of RBs assigned to a cluster conforms to the traffic requirement and the scale of the cluster. This part of the resource allocation can be regarded as the first layer resource allocation, or the preparation for the D2D link resource allocation.

Based on the assigned cluster's RBs, intra-cluster resource allocation is dedicated to assign these RBs to D2D links with the objective of maximizing the throughput while minimizing the required number of RBs. As the transmit power of devices varies, the interference range of D2D pairs changes correspondingly. In general, larger interference range causes larger resource reuse distance leading to lower resource reuse efficiency, while the lower interference range is favorable for resource reuse. Thus the power allocation is not negligible, which greatly influences on the performance. In short, the intra-cluster resource allocation should take into account the RB assignment and the power allocation simultaneously to fulfill the requirements of resource optimization.

Complying with the differences between these two classes of resource allocation, disparate resource allocation algorithms should be designed. Different mathematical models and optimization methods ought to be adopted to accord with their inherent characteristics.

Cluster-based D2D resource allocation algorithm

D2D dynamic cluster resource allocation algorithm

Problem formulation

To well organize numerous device links, the cluster mechanism is used by means of assembling geographically adjacent devices as a cluster to facilitate the communication between each other. In this thesis, the range of a cluster is supposed as a circle and the size of a cluster is defined as the radius of this circle. To simplify the case, the size of clusters is supposed to be fixed, which permits direct one-hop communication between the devices. Note that different cluster size can only lead to different interference range which will not change the essence of the resource allocation problem. With the identical cluster size, the network architecture is shown in Figure 5.4. Thus, inside a cell, the D2D network is composed of clusters, which can communicate with each other via the relay of the eNodeB. At the same time, devices in a cluster can directly communicate with each other. Considering the case that devices can move inside a cell, we use the dynamic cluster mechanism to conform with this movement. A cluster can be dynamically formed or deleted. If a device is in the range of an established cluster, it will be automatically enrolled in this cluster. Otherwise, a new cluster including this device will be generated. Moreover, if all devices have moved out of a cluster, the cluster will be deleted promptly. Based on the system model, we study the RB assignment from a cluster point of view. Because the intra-cluster resource allocation is relatively simple, e.g., each D2D link can share the resource block by turns as done by the well-known roundrobin scheduling algorithm, we only focus on allocating resource to clusters in this section. Note that in this part, only one RB is allocated to each cluster, although they can be allocated with a RB group sometimes, which will not change the essence of this problem. In other words, one RB in our inter-cluster resource allocation can be equivalent to a RB group. The limited dedicated resource blocks, which cannot be used by CUEs at the same time, are allocated to clusters. The question becomes how to efficiently assign resource to these clusters such that the total number of resource blocks is minimum and the mutual interference is minimum, as the clusters are dynamically formed and canceled. Therefore, the resource assignment here is not a static assignment, which is required to dynamically allocate resource as the cluster topology changes.

In order to get the resource allocation constraints, at the beginning, it is necessary to study the interference range of each cluster. Supposing that the maximum transmission range between two devices in a cluster is d max , the range of a cluster can be described as a circle with radius r, d max = 2r. When two devices are transferring data to each other, each of them can be a transmitter and a receiver simultaneously. So, as shown in Figure 5.5, the interference range will be a circle, whose radius equals 3r, i.e., the radius of a cluster r plus the maximal communication range of a device 2r. In this interference range, for instance, if the device A and the device B in cluster 1 communicate with each other by using a specific RB, the communication for other devices using the same RB, such as device C and device D, will be greatly interfered. To avoid the conflict, this RB can only be assigned to other clusters out of this interference range. According to the interference range, the resource reuse distance can be obtained. As shown in Figure 5.5, the resource reuse distance is equal to 4r, i.e., if the distance between two clusters is strictly larger than 4r, they can be allocated with the same resource without interference. With this constraint, the cluster topology graph can be constructed. Let each vertex represent a cluster, if the distance between two clusters is not strictly larger than 4r, there is an edge connecting these two vertices. For the dynamic scenarios, if some new clusters are generated or deleted, the topology graph will be updated by adding or deleting the corresponding vertices and edges. This

k c=1 x vc (t) = 1, v ∈ V (t), v / ∈ V (t -1) (5.2)
x vc (t) + x nc (t) ≤ y c , (v, n) ∈ E(t), c = 1, ..., k (5.3)
x vc (t) = 0, v / ∈ V (t), v ∈ V (t -1), c = 1, ..., k (5.4) to binary variables. Note that in our algorithm we do not reallocate colors to the old vertices which do not change at all in the new graph each time, but sometimes the colors of few old vertices can be changed in order to allocate the minimum number of resources.

x vc (t) ∈ {0, 1}, v ∈ V (t), c = 1, ..., k (5.5

Algorithm description

The dynamic graph coloring algorithm is designed in this part to dynamically assign RBs to clusters, whose intuition is to color the changing graph with the minimum number of colors from a graph structure point of view (see Algorithm 7). This dynamic algorithm is based on the static graph coloring algorithm in [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF]. Instead of coloring a static graph, we set dynamic components to move from a graph G(V (t), E(t)) to a graph G(V (t + 1), E(t + 1)), t is an integer and t ≥ 1, and the graph coloring is done dynamically.

The input of this algorithm is the dynamic graph G(V (t), E(t)) and the old best column S t-1 , t is an integer and t ≥ 1. For short, G t is used to represent the graph in time t. And the output is the best column S t with the minimum number of colors, which indicates the coloring constraint for all vertices in the graph. Note that the best column obtained by the dynamic graph coloring algorithm corresponds to the best solution for the cluster resource allocation. Generally, the algorithm contains three parts: the maximal clique decomposition, the suite construction and the vertex coloring (see Algorithm 7). The process of the first two parts are similar to that in TexaCol, but they only deal with the new generated nodes.

For the phase of vertex coloring, it aims to color each new added vertex according to the coloring sequence s v , which is determined by the sequence of their appearance in the suite. At first the skeleton is obtained for all new cliques in cliqueSuite. Then, the function skeletonT reatment() is engaged on partitioning all coloring cases, i.e., to determine which vertices can have the same color and which vertices must have different colors. Each time before this treatment, the column with minimum number of colors is chosen as the best column in column set, i.e., allColumns, to continue the calculation. If there are some vertices deleted, before continuing, the old best column is renewed in this way: first clear the coloring constraint of all deleted vertices in old column, then if some vertices have the same color with deleted vertices, also update the coloring constraints of these vertices.

Example

An example is given to illustrate this dynamic algorithm. In Figure 5.7, the graph is changing: at the beginning, it contains 7 vertices; after, it adds 5 new vertices and deletes 2 old vertices.

Considering to color the old graph, there are eight old clique suites, i.e., suite, and from that, the coloring sequence of vertices s v and the skeleton have been obtained

(see Table 5.3). By treating the cells in skeleton one by one, coloring constraints for the corresponding vertices can be attained. For instance, while coloring the vertex 6, it means, it is the turn to color the clique {2, 3, 6}. Note that vertices in the set {1, 3, 4, 2}

has been colored before and the skeleton of the vertex 6 contains two layers: [2 3] and

[4].
As it is possible that in these two layers, the vertex 2 and the vertex 4 can have the same color or not, the column s 1 and the column s 2 can be obtained. In s 1 , these two vertices have different colors and in s 2 , they have the same color. The minus sign here is used to denote that two vertices are allocated the same color. In s 2 , the coloring constraint of the vertex 2 is [-4], that is to say, the vertex 2 has the same color with the vertex 4. After coloring the vertex 6, the next vertex to color is the vertex 5. Because s 2 requires less number of colors than s 1 , i.e., 3 colors, so s 2 is chosen as the old best column. It will add the skeleton of the vertex 5 to continue the treatment. Thus, after coloring the vertex 5, s 2a and s 2b have been obtained and s 2b is chosen as the best column to continue. In this way, the algorithm can get the best column for the old graph until all vertices are colored.

G 0 ← ∅, S 0 ← ∅, S t ← S t-1 , s v ← ∅, cliqueSet ← ∅, cliqueSuite ← ∅, solutionSize ← 0. /* Phase 1: maxCliqueDecomposition */ for each vertex v ∈ V (t), v / ∈ V (t -
Similarly, the new graph can be colored. Because the vertex 1 and the vertex 6 have

suite sv skeleton s 1 s 2 s 2a s 2b {1,3,4} 1 [ ] [ ] [ ] [ ] [ ] {1,2,3} 3 [1] [1] [1] [1] [1] {2,3,6} 4 [3 1] [3 1] [3 1] [3 1] [3 1] {3,4,6} 2 [3 1] [4 3 1] [-4] [-4] [-4] {1,4,5} 6 [2 3][4] [2 4 3] [4 3] [4 3 1] [-1] {4,5,6} 5 [4 1][6] [6 4 1] [4 1] {1,5,7} 7 [5 1][2] {1,2,7}
been deleted, firstly we change the old best column and get the updated column S t . This process is done by deleting the coloring constraints of the vertex 1 and the vertex 6 and update the coloring constraint for other related vertices. By means of getting the new clique suites suiteN ew and treating the skeleton for the new vertices, finally, the new best column S t+1 can be obtained, which requires 4 colors (see Table 5.4).

[ ] {2,3,10} 1 [deleted] 1 [deleted] 3 [1] {2,9,10} 3 [ ] 3 [ ] 4 [3 1] {8,9,10} 4 [3] 4 [3] 2 [-4] {4,8} 2 [-4] 2 [-4] 6 [-1] {7,8} 6 [deleted] 6 [deleted] 5 [4 1] {3,10,11} 5 [4] 5 [4 3] 7 [5 4 1] {10,11,12} 7 [5 4] 7 [-3] {5,12} 10 [5 4 3] 9 [-3] 8 [10 4 3] 11 [-5] 12 [10 5]
Another example is provided which shows the dynamic graph coloring process following the successive 6 topology changes. The initial interference topology graph for clusters is shown in Figure 5.8 and the topology change process is shown in Figure 5.9. The basic information for the initial topology is shown in Table 5.5. This topology graph has 6 maximal cliques and its skeleton is shown in the table. After coloring it, two columns are obtained: s 1 and s 2 . As s 2 is the complete column including all nodes' coloring constraints, it is the best column for the initial topology. TABLE 5.5: The basic information for the initial topology.

suite sv skeleton s 1 s 2 {1,3,4} 1 [ ] [ ] [ ] {1,4,5} 3 [1] [1] [1] {2,4,5} 4 [3 1] [3 1] [3 1] {2,3,4} 5 [4 1] [4 3 1] [-3] {4,5,6} 2 [5 4][3] [5 4 3] [4 3] {3,4,6} 6 [5 4][3] [4 3]
As shown in Figure 5.9, for each topology change, some new nodes are added with some new edges connecting to the old nodes, while some old nodes as well as their associated edges are deleted. Corresponding to each topology change, the graph coloring result with our dynamic algorithm is shown in Table 5.6. When the topology changes, our algorithm only focuses on the changed part of the graph and the best coloring result for the new topology S t+1 is calculated based on the old best column for the old topology S t . If there are some deleted nodes, the old best column S t is updated to S t before the coloring process for new added nodes.

Result analysis

The performance of the inter-cluster resource allocation algorithm is evaluated in this part, in which, mainly, the resource utilization, the runtime and the scalability have been investigated. In Figure 5.10, the comparison has been conducted between our dynamic resource allocation algorithm with another two algorithms: the greedy algorithm and the static algorithm [START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF]. The greedy algorithm here is the classical Welch Powell algorithm, which allocates as much as possible the used RBs to the new vertices if no conflict exists [START_REF] Dominic | An upper bound for the chromatic number of a graph and its application to timetabling problems[END_REF]. Thus, it can color a graph with the acceptable result and with low complexity. The static algorithm can always get the best solution, but it need to color the new graph completely with the exact method even if the graph has little changes.

Nodes in old graph

Additional nodes in new graph

Nodes to delete

Edges in old graph

Additional edges in new graph

] [ ] 1 [ ] {1,3,4,11} [ ] [ ] 3 [1] {5,6,7} [1] [1] 3 [1] {1,4,5,11} [1] [1] 4 [3 1] {1,3,10} [3 1] [3 1] 4 [3 1] {3,11,13} [3 1] [3 1] 5 [-3] {7,8} [-3] [-3] 5 [-3] {3,6,13} [-3] [-3] 2 [4 3] {9,10} [deleted] [deleted] 2 [deleted] {5,11,13} [deleted] [deleted] 6 [4 3] {5,9} [4 3] [-1] 6 [-1] {5,6,13} [-1] [-1] 7 {8,9} [3 1] 7 [3 1] {11,12} [3 1] [4 3 1] 10 [-7] 10 [-7] {10,12} [-7] [-7] 8 [-3] 8 [-3] [deleted] [deleted] 9 [7 3] 9 [ 7
] [ ] 1 [ ] No new suite [ ] [ ] 3 [1] {4,5,6,15} [1] [1] 3 [1] [1] [1] 4 [3 1] {1,10,15} [3 1] [3 1] 4 [3 1] [3 1] [3 1] 5 [-3] {6,7,14} [-3] [-3] 5 [-3] [deleted] [deleted] 2 [deleted] {6,13,14} [deleted] [deleted] 2 [deleted] [deleted] [deleted] 6 [-1] {1,14} [-1] [-1] 6 [-1] [-1] [-1] 7 [4 3 1] [4 3 1] [4 3 1] 7 [4 3 1] [4 3 1] [4 3 1] 10 [-7] [-7] [-7] 10 [-7] [deleted] [deleted] 8 [deleted] [deleted] [deleted] 8 [deleted] [deleted] [deleted] 9 [deleted] [deleted] [deleted] 9 [deleted] [deleted] [deleted] 11 [-7] [-7] [-7] 11 [-7] [-7] [-7] 13 [7 3 1] [7 3 1] [7 3 1] 13 [7 3 1] [7 3 1] [7 3 1] 12 [7] [7] [7] 12 [7] [7] [7] 15 [7 4 3 1] 15 [7 4 3 1] [deleted] [
[ ] {1,16} [ ] [ ] 1 [ ] {1,11,18} [ ] [ ] 3 [1] {7,16} [1] [1] 3 [1] {1,16,18} [1] [1] 4 [3 1] [3 1] [3 1] 4 [3 1] {11,13,18} [deleted] [deleted] 5 [deleted] [deleted] [deleted] 5 [deleted] {6,7,17} [deleted] [deleted] 2 [deleted] [deleted] [deleted] 2 [deleted] {1,17} [deleted] [deleted] 6 [-1] [-1] [-1] 6 [-1] [-1] [-1] 7 [4 3 1] [4 3 1] [4 3 1] 7 [4 3 1] [3 1] [3 1] 10 [deleted] [deleted] [deleted] 10 [deleted] [deleted] [deleted] 8 [deleted] [deleted] [deleted] 8 [deleted] [deleted] [deleted] 9 [deleted] [deleted] [deleted] 9 [deleted] [deleted] [deleted] 11 [-7] [-7] [-7] 11 [-7] [-7] [-7] 13 [7 3 1] [7 3 1] [7 3 1] 13 [7 3 1] [7 3 1] [7 3 1] 12 [7] [deleted] [deleted] 12 [deleted] [deleted] [deleted] 15 [deleted] [deleted] [deleted] 15 [deleted] [deleted] [deleted] 14 [13 7 1] [deleted] [deleted] 14 [deleted] [deleted] [deleted] 16 [7 1] 16 [7 1] [ 7
The test compares the resource allocation result while the cluster topology changes for 10 times. Each topology change occurs in a time unit (second, minute or hour, etc.). Initially, there are 20 D2D clusters generated randomly and the corresponding cluster interference graph is formed. Then, in each time unit, there are 2 new clusters generated in the network. The test has been implemented for 10 times independently and the average number of RBs, i.e., numRBs, and the average runtime have been obtained for these three algorithms. The scalarization has been done for the runtime, which ranges from 0 to 1 after being divided by the maximal value of runtime among them. As shown in Figure 5.10, our dynamic algorithm always need much less runtime than other two algorithms, because it just considers the changed part in the new graph each time. As the number of clusters is increasing, the runtime of the static algorithm increases dramatically while the runtime of the dynamic algorithm is really stable and can even be about 3% of the static one at the end. For the number of RBs, the dynamic algorithm has nearly the same performance with the greedy algorithm, but it requires much less time, i.e., about 10% of the runtime of the greedy algorithm. The average performance gap on 10 runs between our dynamic algorithm (the suboptimal solution)

and the static algorithm (the optimal solution) has been shown in Table 5.8 in terms of the percentage increase of the number of RBs and the percentage decrease of the runtime. In the table, the plus sign before the percentage sign indicates the percentage increase while the minus sign before that indicates the percentage decrease. Another performance analysis is about the scalability, by which we can know whether our algorithm is well adapted to the frequent change of network topology. In Figure 5.11, the resource allocation is conducted while the cluster topology is changed by randomly adding and deleting clusters at the same time. In this figure, numAdd denotes the number of randomly added clusters and numDelete is the number of randomly deleted clusters. The test is implemented for 10 times and the average number of RBs, i.e., numRBs, has been obtained when the total number of clusters, numCluster, is increasing. The time unit here depends on when the cluster topology changes. The result shows that our algorithm is capable of assigning resource to clusters which are dynamically added and deleted. Specially, when the clusters are deleted, their allocated RBs will be released, that is the reason why the number of RBs decreases sometimes.

D2D intra-cluster resource allocation algorithm

Intra-cluster resource allocation problem

Supposing devices have been grouped into clusters and each cluster has some available RBs, the intra-cluster resource allocation problem is dedicated to allocating these RBs to each D2D links inside the cluster.

The system architecture for intra-cluster resource allocation is shown in Figure 5.12. In this architecture, clusters have different cluster size. It is supposed that the diameter of each cluster can be larger than the maximal communication distance between devices.

Thus, for certain device pairs inside a cluster, there are no possible links if they are far away from each other. For instance, in Figure 5.12, there are no links between some devices in cluster 1 and cluster 3, because the distance between them is larger than the maximal communication range.

On the basis of the system architecture, the intra-cluster resource allocation problem is formulated as follows. In a cluster, let n denote the number of devices. Supposing the number of RBs is K, the RB available for the cluster is = {RB 1 , RB 2 , ..., RB K }.

Two devices can match in pairs automatically if there are close enough or if they want to transfer data mutually while they are situated in each other's communication range.

Suppose the number of D2D pairs is N . The distance between each D2D pair is d i , i = 1, 2, ..., N . The power of each D2D pair is p min < p i < p max , i = 1, 2, ..., N .

The minimum power p min can guarantee the communication for all D2D pairs. That is to say, two devices in a D2D pair whose distance is maximum among all D2D pairs can normally transmit or receive data packets with p min . p max is the maximal power available for the device. It is confined that each device in a D2D pair use the same power to transmit data packets. Considering a D2D pair, if the device A is the transmitter which uses power p A to send packets to the device B, i.e., the receiver, the Signal-to-Interference-plus-Noise Ratio (SINR) at the device B is given in Formula 5.7:

SIN R B = p A h AB I AB + σ 2 (5.7)
h AB is the channel gain which is given as

h AB = Cβ AB ς AB (d AB ) -α = Cβς(d AB ) -α (5.8)
where C is the path loss constant, d AB denotes the distance between these two devices, σ 2 is the variance of the thermal noise power and I AB represents the interference from other D2D pairs using the same RB. α denotes the pathloss factor.

β AB and ς AB are factors representing the small-scale fading and shadow fading between device A and device B, respectively. Let γ be the minimum SINR threshold for communication. Thus, the SINR for device B should satisfy Formula 5.9 for the communication.

SIN R B

= p A Cβ AB ς AB (d AB ) -α I AB + σ 2 γ (5.9)
So the minimum power is calculated by Formula 5.10, where k is the index for each D2D pair, 0 k N . d k is the distance of the kth D2D pair and I k is the interference from other D2D pairs using the same RB. β k and ς k denote small-scale fading and shadow fading on the kth D2D pair, respectively.

p min min( γ(I k + σ 2 )(d k ) α Cβ k ς k ) (5.10)
According to the Shannon-Hartley theorem, the throughput between device A and device B is calculated shown in Formula 5.11.

R AB = B AB log 2 (1 + SIN R AB ) = B AB log 2 (1 + p A Cβ AB ς AB (d AB ) -α I AB + σ 2 ) (5.11)
B AB is the channel bandwidth of the allocated RB on the link between device A and device B. From Formula 5.11, it can be seen that the throughput mainly depends on p A , I AB and B AB . B AB is considered as the same for all RBs. p A and I AB are essential to improve the throughput, which are decided by power allocation and RB resource allocation.

Thus, the throughput for all D2D pairs in the cluster, denoted by R all , is expressed in Formula 5.12.

R all = N i=1 B i log 2 (1 + SIN R i ) (5.12)
B i and SIN R i are the channel bandwidth and the SINR for each D2D pair, respectively.

Finally, the intra-cluster resource allocation can be formulated as an optimization problem. The objective is to maximize the total throughput and to minimize the number of RBs. It is actually a multiple objective optimization problem. To simplify the case, an optimization index is defined to transfer this multiple objective optimization problem into a single objective optimization problem, which leads to the suboptimal solution. In the following part, the optimization index is also called optimal index. The optimization index is shown in Formula 5.13, which is directly proportional to R all and inversely proportional to N RB . The parameter a and b are used to adjust the proportion between the total throughput and the number of colors, a 0, b 0. The larger a is, the more proportion is for N RB . Likewise, the larger b is, the more proportion is for R all . If a = 0, the optimization object is to get the solution with maximal throughput and if b = 0, the object is to get the solution with minimum number of colors.

optimalIndex = R b all N a RB (5.13)
With the formulation above, the Formula 5.13 can be rewritten as Formula 5.14. The optimization problem for intra-cluster resource allocation is formulated as follows.

arg max

C N ×K ,P N ×K ( K k=1 N i=1 B log 2 (1 + p i,k Cβ i,k ς i,k (d i,k ) -α I i,k +σ 2 )α i,k ) b N a RB (5.14) s.t. K k=1 α i,k = 1 (5.15) p min p i,k p max (5.16)
N RB K (5.17)

I i,k = 0 (5.18)
K is the number of RBs, N is the number of D2D pairs, C N ×K is the set containing all possibilities of RB allocation and P N ×K is the set containing all possibilities of power allocation. α i,k equals 1 while RB k is allocated to D2D link i. N RB is the number of RB used. B is the channel bandwidth, which is considered as the same for all RBs. The Formula 5.15 indicates each D2D link will be and will only be allocated with one RB. The Formula 5.16 confines the power range. The Formula 5.17 requires the number of RBs used is less than the total number of RBs for the cluster. The Formula 5.18 ensures that with proper RB allocation and power allocation, there are no mutual interference in the cluster.

Different RB allocation and power allocation lead to different optimal index; therefore, it is important to design effective RB allocation and power allocation mechanism to solve this optimization problem.

Topology-based resource allocation mechanism

A topology-based resource allocation mechanism is proposed using graph coloring, which naturally combines RB allocation and power allocation to get a suboptimal solution.

In a cluster, the interference relationship of D2D pairs can be modeled as a graph G(V, E), where V is the set of nodes representing each D2D pair and E is the set of edges denoting the interference relationship between D2D pairs. If there are interference between two D2D pairs while using the same RB, there will be an edge connecting their corresponding nodes in graph G(V, E).

The interference between D2D pairs largely depends on the power they used. For a certain D2D pair, different transmit power used leads to different transmission range and interference range. As the interference range grows, the interference to adjacent D2D pairs becomes larger; thereby it causes more edges connecting to the neighboring nodes. In other words, different power allocation leads to different topology of the graph G(V, E). For instance, in Figure 5.13, the distance between the device A and the device B is d and if they communicate mutually using the minimum power, the radius of their transmission range is also d. As shown in Figure 5.13, their radius of interference range will be 3d/2. At this moment, the communication between the device C and the device D will not be influenced, since they are not located in the interference range of the device A and the device B. Consequently, in the graph G(V, E), there will be no edges connecting the corresponding nodes of these two D2D pairs. Nevertheless, as shown in Figure 5.14, if the device A and the device B use larger power to increase their data rate which causes their radius of transmission range to be d , their interference range will be a circle with radius d/2+d . As the device C is in this range using the same RB, it is not able to rightly decode the received data packets from the device D. Accordingly, an edge is added in the graph G(V, E) connecting the corresponding nodes of the D2D pair (A, B) and the D2D pair (C, D). Since the number of RBs, represented by the number of colors, largely relies on the graph topology, it is also greatly influenced by the power allocation. While allocating RB and power to a D2D pair, there are some choice for the topology associated with this node, according to different selected power. Different topology choice leads to different result of the required number of RBs. Taking the case in Figure 5.15 for example, when the node 1, the node 2 and the node 3 have been allocated with the minimum power p 0 , we try to choose a power for the node 4. If the node 4 is allocated with the power p 0 , the topology graph is shown at the left side, which only need two colors to satisfy the proper coloring condition. But if the node 4 uses the larger power p 1 to increase its data rate, it forms a different topology with more edges which requires at least 3 colors. As a matter of fact, the optimal index seeks to strike a balance between the larger power and the smaller power allocated to D2D pairs, which indirectly corresponds to the tradeoff between the higher throughput achieved and less number of RBs used. On the one hand, larger power for each D2D pair is desired to attain larger throughput. On the other hand, larger power leads to larger interference between D2D pairs causing more number of RBs. Besides, as the proper coloring is used to allocate RBs ensuring that the neighboring nodes are allocated with different RBs, no interference occurs for D2D pairs in the cluster, i.e., I i,k equals 0 in Formula 5.14, 1 i N , 1 k K.

Intra-cluster resource allocation strategies

In view of the topology-based resource allocation mechanism above, the algorithm is designed to jointly assign RB and power resource for D2D pairs inside the cluster. Because the RB allocation exactly corresponds to the graph coloring, in the aftermentioned part of this thesis, the RB and color are considered equivalent and can mutually substitute. Likewise, the D2D pair and the node in the graph are reckoned as the same thing.

In Figure 5.16, different strategies is shown to solve the intra-cluster resource allocation.

There are generally two sorts of methods: the global optimization method and the local optimization method. The global method is capable of obtaining the global optimal solution for the problem formulated in Formula 5.14. A simple global method is to directly use the exhaustive search, which traverses all possibilities of power and color for each D2D pair.

Supposing the number of D2D pair is N , the number of power to choose is M , and the number of color is K, the size of the search space for exhaustive method equals (M K) N . It will be extremely large even for small graphs, which will cause very high computational complexity. Therefore, the exhaustive method is pretty limited to allocate intra-cluster resource. Even though some heuristic strategies may be developed based on global method, how to reduce the computational complexity is till a tough problem.

Another method is the local optimization method, which seeks to allocate power and color node by node ensuring the local optimal optimalIndex until all nodes have been assigned with a power and color. In this thesis, only the local methods are discussed.

In Figure 5.17, the flow graph of the resource allocation based on local optimization is shown. The input of the algorithm is the coordinates of the D2D pairs, and the output is the solution of RB and power resource allocation. The coordinate of a D2D pair is defined as the midpoint's coordinate of the D2D link. At the beginning, the treating sequence of D2D pairs, denoted by treatSequence, is determined. Note that different treatSequence will lead to different resource allocation result. So some strategies may be developed to determine the treatSequence. In this thesis, by default, the treating sequence is in the ascending order of distance between node's location and the center of the cluster. With this sequence, nodes situated in the center area of the cluster will firstly do the resource allocation. For each node, different powers are tried and the best power is chosen. This process includes the topology constructing, graph coloring and the topology selecting. The corresponding function is explained in detail below.

topologyConstruct(): After selecting a new node to treat, this function will generate the new possible topology according to the input power. As is stated in the topology-based resource allocation mechanism, the topology is determined by the interference range which relies on the input power. According to the interference range with the input power, this function will judge the coordinate of other nodes in order to construct the new topology. If one node is situated in this interference range, there will be an edge connecting to this node. Specially, for the untreated nodes, even though they have not been assigned resource yet, it is possible that they are located in the interference range of certain treated nodes. Consequently, there are some edges connecting to them.

graphColoring(): On the basis of the new constructed topology, the graph coloring function will get the proper coloring solution. Since graph coloring problem is a NP-complete problem, getting the optimal coloring solution cannot be achieved in a polynomial time. The result of the graph coloring algorithm is the basis for power allocation each step while treating a new node. As a result, the performance of the graph coloring algorithm occupies a crucial role in ensuring the performance of the proposed resource allocation algorithm. As it is reckoned that the topology does not change for the traditional graph coloring algorithms, it is challenging to directly use the traditional method to design effective resource allocation algorithms to conduct color allocation and topology selection synchronously.

topologySelect(): This function will choose the best power that can achieve the local best optimalIndex. The input of the function is the chosen power and the number of colors given by the graph coloring algorithm. With these input parameters, this function will calculate the optimal index according to Formula 5.14. Each step the best power, its corresponding optimal index and the coloring solution are stored. Until a better power arrives with better optimalIndex, the better power will replace the old best power and the corresponding optimal index and coloring solution will be updated. When all powers are tried, the best power will be allocated to the treating node and the RB allocation solution is its corresponding coloring solution. Then, the algorithm moves to the new node according to the treating sequence.

As is stated above, different graph coloring methods are used leading to different resource allocation strategies for the local optimization method. In this thesis, four strategies are proposed with different graph coloring algorithms, as shown in Figure 5.16. Generally, these strategies can be divided into two categories: the static strategy and the dynamic strategy.

In the static strategy, while trying a new power for a certain node, all the topology information will be input to do the graph coloring. Each step, based on the new topology, the minimum number of colors will be calculated again in order to make the power selection decision. Two static strategies are proposed: the static greedy algorithm and the static PexaCol. The static greedy algorithm uses the greedy graph coloring algorithm in [START_REF] Dominic | An upper bound for the chromatic number of a graph and its application to timetabling problems[END_REF], which is able to get the suboptimal graph coloring solution. In this greedy algorithm, the coloring sequence of nodes is in the descending order of their degree, so its performance has been greatly improved. As for the static PexaCol, the PexaCol method proposed in Chapter 4 is used to color the graph. As an exact method, PexaCol can get the best graph coloring solution, which is favorable to achieve a higher optimalIndex due to less number of colors.

With respect to the dynamic strategy, only the changed part of the graph will be considered as the input while choosing a new power for a certain node. The solution for the new topology will be calculated based on the old solution. In this thesis, two dynamic algorithms are proposed: the dynamic PexaCol and the dynamic PexaCol approximate.

The dynamic PexaCol can well combine the graph coloring and the power allocation together to get a suboptimal solution. It stores allColumns of the old best topology and continue to calculate the new skeleton while choosing a new power for a certain node.

Different from PexaCol and the dynamic cluster algorithm, it will use optimal index to choose the best column and some new mechanisms are designed to do the RB and power allocation. On the basis of dynamic PexaCol, the dynamic PexaCol approximate method only choose a part of the old best solutions for the old best topology to continue to calculate. Thus, it is able to get an approximate optimal solution by largely reducing the runtime, which is suitable to deal with larger graphs.

As the dynamic PexaCol algorithm and the dynamic PexaCol approximate algorithm are both dynamic local optimization algorithms, in the following part of this thesis, they are called Dynamic Local Optimization Algorithm (DLOA) and the Dynamic Local Optimization Approximate Algorithm (DLOAA), respectively. The details of DLOA will be discussed in the Section 5.5.2.4. For DLOAA, it will only use the old best column instead allColumns for each best topology to continue the skeleton treating. Thus, it is able to get an approximate solution but it can largely simplify the algorithm complexity.

Dynamic local optimization algorithm (DLOA)

To well deal with the color and the power allocation, the DLOA has different data structure and algorithm process. Firstly, the number of colored nodes in each column is considered as the same and to facilitate the coloring process, the coloring sequence of nodes is the same as their treating sequence. Since the topology of the untreated nodes can be changed while treating a certain node, their coloring constraint should be added in the column. That is to say, even if one node has not been treated, it can have its coloring constraint in the column.

Moreover, to avoid treating repeatedly some nodes' coloring constraints in the skeleton while the topology is changed, it uses two sorts of skeleton to store the connection relationship of the nodes: the skeleton 1 and the skeleton 2. The skeleton 2 only stores the coloring constraint of the node to treat and the nodes untreated. The skeleton 1 combines the skeleton of the old best topology and the skeleton 2 together. They will be added to the column to treat at different moment.

Another difference between DLOA and the proposed algorithms before is that each column has three attributes: the number of colors, the throughput and the next skeleton ID. The number of colors is the minimum number of colors for this column and the throughput is calculated by the power of the treated nodes. Further the optimal index for each column can be obtained by using the Formula 5.14. The next skeleton ID Finally, the definition of the best column in DLOA is changed, which satisfies two conditions: the best column has the maximal optimal index and it has the maximal absolute value of the next skeleton ID if the first condition has been satisfied. In the algorithm process, the best column is chosen out to do the skeleton treating. Then it will use the corresponding skeleton and treat the nodes' coloring constraint according to the nextSkeletonID. Note that more than one node's coloring constraint will be treated in the skeleton, it is really necessary to use nextSkeletonID to indicate which one has been treated and which one to treat.

The algorithm process of DLOA is shown in Algorithm 8. The resource allocation is conducted according to the treating sequence. For each node, the result of optimal index for each power is compared to find the best power. The larger power is tried first, since its corresponding throughput generally increases faster than the number of colors, which makes it easier to reach a higher optimal index. In all the process, the graph coloring algorithm of DLOA is inseparable from the power allocation and topology selection, which naturally combines all of these functions together to find the best solution for the resource allocation. The algorithm process of the graph coloring in DLOA is shown in Figure 5.18. The whole process is similar to PexaCol, but all the functions are different from that in PexaCol. The functions are explained as follows.

initialNextSkeletonID(): This function will initialize the nextSkeletonID for each column in the oldColumns. The nextSkeletonID plays an significant role in organizing the skeleton treatment for columns coming from different phase of the topology changing. For each column, it indicates which kind of skeleton to add and from which node the skeleton treatment starts. In the function, the vector nextSkeletonID will equal nextSkeletonIDOld at the beginning. Then, for each column i, the skeleton 1 of the old best topology oldSkeleton1. Then, the skeleton 2 is obtained according to the new topology. Finally, the skeleton 1 will incorporate all nodes' coloring constraint in skeleton 2. In this algorithm, by default, a node's coloring constraint is added to the second layer of this node's coloring constraint in the skeleton.

1 i m, if |nextSkeletonIDOld[i]| > |V |,
chooseBestColumnDynamic(): Based on allColumns and nextSkeletonId, this function is dedicated to choose the best column. The best column should have the maximal absolute value of nextSkeletonID while it has the maximum optimal index. Although it is possible that more than one best columns exist, the algorithm will stop searching until one of them has been found. When a best column is found whose nextSkeletonId is |V + 1|, the algorithm is finished, since it implies that all nodes have been colored

with minimum number of colors.

skeletonTreatDynamic(): After getting the best column, this function will use the corresponding skeleton and treat the column. From its nextSkeletonId, we can decide which skeleton to use. If nextSkeletonId < 0, it will use skeleton 2, otherwise it will use skeleton 1. The location of the coloring constraint is indicated by |nextSkeletonId|, from which the next node to do the skeleton treating is known. The following process of the treatment is the same as that in TexaCol. The nodes in layer 2 will be gradually treated to form different columns according to the coloring cases.

Each time after the skeletonTreat, the nextSkeletonId will be updated to indicate the next node to treat in a column. If nextSkeletonId > 0, nextSkeletonId will be changed to nextSkeletonId+1, otherwise if nextSkeletonId < 0, nextSkeletonId will be updated to -nextSkeletonId -1.

To well understand the whole algorithm process, DLOA is illustrated in detail. Supposing in a cluster, there are m D2D pairs and there are two different powers to choose for D2D communication: p 1 and p 2 . The interference range of p 1 is larger than that of p 2 . The treating sequence is v 1 , v 2 , ..., v m-1 , v m . While treating the node v i with power p 1 , the topology graph is shown in Figure 5.19. To simplify the calculation in a certain geographical region with coordinates, suppose the interference range is a square. The node v i is connected to two colored nodes v 2 and v i-1 , and meanwhile, it is connected to two other uncolored nodes v m-1 and v m .

1 m v 2 m v 1 i v m v 1 v 2 v 3 v 1 i v 4 v i v FIGURE 5

Old best column

1 v 2 v 3 v n-1 v n v . . . . . . i v i+1 v V +1 R R R R R FIGURE 5
.20: Skeleton 1 and all columns for the old best topology.

First, because allColumns is the result for the old best topology, the nextSkeletonID will be initialized. If nextSkeletonID > |V |, we change it to -i, such as the nextSkeletonID of the column 3 and the column i + 2. For the nextSkeletonID of the column 1, since it is less than i, it will be changed to the absolute value of its nextSkeletonID, i.e., |n 1 | = i -1.

Second, the new skeleton will be created based on the old skeleton 1. Note that in this algorithm, there are two kinds of skeletons to choose: skeleton 1 and skeleton 2.

Skeleton 1 accumulates all coloring constraint information for the old topologies as well as the current topology, while skeleton 2 is only for the current topology. Thus, the skeleton 2 is obtained according to the new topology. Then, the new skeleton 1 is the one combining the old skeleton 1 and the skeleton 2. As for the skeleton treatment, if a column's nextSkeletonID > 0, skeleton 1 will be used, otherwise skeleton 2 will be used.

After the initialization of nextSkeletonID and the construction of new skeletons, allColumns while coloring v i in column 3 is shown in Figure 5.21. Note that the colored part in skeleton 1 means this part has integrated the skeleton 2. As the nextSkeletonID of column 3 is larger than 0, it will use skeleton 2 to calculate. According to its nextSkeletonID, it will add the coloring constraint of node i in skeleton 2 to do the skeleton treatment and then its nextSkeletonID will be changed to -i -1. Old best column

1 v 2 v 3 v n-1 v n v . . . . . . i v i+1 v 1 i i i i i i
Rc Rc Rc Rc Rc Rc Then, supposing the best column is the column 1, the information of allColumns, nextSkeletonID and skeletons is shown in Figure 5.22. Because the nextSkeletonID of column 1 is larger than 0, it will use skeleton 1. The coloring constraint of the node i-1 in skeleton 1 will be added to do the skeleton treatment. After treating this skeleton, supposing the best column is still the column 1, the node to do the skeleton treatment is v i , as shown in Figure 5.23.

If power p 2 is chosen by the node v i , the topology is different, as shown in Figure 5.24.

There are only two nodes in the interference range of the node v i : the node v i-1 and the node v m . To color this graph, the same old allColumns, the same nextSkeletonID and the same old skeleton 1 for the old best topology are used. The same process of initialization for the nextSkeletonID and the skeleton creating are conducted. As the column 3 is the old best solution whose nextSkeletonID equals -i, the coloring constraint of v i in skeleton 2 will be added to that in column 3 to do the skeleton treatment. This process is shown in Figure 5.25.

After treating the skeleton of v i in column 3, suppose that there are some new columns generated which are added at the right side of allColumns, as shown in Figure 5.26.

Note that the nextSkeletonID for these new columns is -i -1. Then, the best solution procedure starts to select the column with maximal optimization index. Supposing the column i + 3 is the best, it will add the coloring constraint of v i+1 in skeleton 2 to that

i i i i-1 v 1 v 2 v 3 v n-1 v n v . . . . . . i v i+1 v i-1 v i Rc Rc Rc Rc Rc Rc 1 cc FIGURE 5
.23: Skeleton treatment of v i in column 1 while allocating power p 1 to v i .

in column i + 3 to continue the calculation. Until the nextSkeletonID for one of the columns is larger than |V |, the best solution for this topology is obtained.

Supposing the optimal index using power p 2 is better than that while using the power p 1 and supposing the column i + 3 is the best column, the old best topology and allColumns are that while using power p 2 for the node v i . According to the treating sequence, the next node to treat is the node v i+1 and it will try the power p 1 first.

1 m v 2 m v 1 i v m v 1 v 2 v 3 v 1 i v 4 v i v FIGURE
1 i i i i i i Rcc Rcc Rcc Rcc Rcc Rcc
With the power p 1 , the skeleton 2 will be created according to the new topology. The skeleton 1 integrates the skeleton 2 and the old skeleton 1. Meanwhile, the vector of nextSkeletonID is initialized, as shown in Figure 5.27. The coloring constraint of the node v i+1 in column i + 3 will incorporate the corresponding elements in skeleton 2 to Old best column

1 i 1 i 1 i 1 v 2 v 3 v n-1 v n v . . . . . . i v i+1 v ... 1 i i i i i 1 i 3 i s Rcc Rcc Rcc Rcc Rcc Rcc Rcc Rcc Rcc FIGURE 5
.26: Skeleton treatment of v i+1 in column i + 3 when v i uses power p 2 .

start the calculation. Until all nodes have been treated sequentially according to the treating sequence, the algorithm ceases and the result of the best power allocation and coloring solution are achieved.

Old best column

1 i 1 v 2 v 3 v n-1 v n v . . . . . . i v i+1 v i i i 1 i ... ...

Rccc Rccc Rccc Rccc Rccc Rccc Rccc

Running example of DLOA

In this section, there is an example of DLOA. As shown in Figure 5.28, 10 D2D pairs are uniformly distributed in a square area with side length 1000 m. Each node has a label and its coordinate is listed in the corresponding bracket. The LTE D2D channel model proposed in 3GPP TR 36.843 is used [TR 14]. The test condition and the related parameters are exactly the same as that in the Section 5.5.2.6. The available powers and their corresponding interference range are shown in Table 5.19 in Section 5.5.2.6.

With these condition, the resource allocation problem is how to allocate power and resource blocks ensuring that the optimal index in Formula 5.14 is optimal. The treating sequence is obtained in the ascending order of the nodes' distance from the center and then the resource allocation is conducted one by one according to the treating sequence. The best topology after treating the first six nodes (6, 10, 5, 9, 4, 1) is given in Figure 5.29 and the relevant information can be found in Table 5.9. As shown in the table, the coloring sequence equals the treating sequence and the old skeleton 1 is given which will be used for the following allocation. There are only two columns in allColumns and the column 2 where the node 1 and the node 5 have the same color is better, which only requires four colors after coloring all nodes while the column 1 requires five colors. Complying with the topology, the power allocated for the first six treated nodes are shown at the right side in Table 5.9, which can attain the maximal optimal index. The result of this resource allocation is shown in Table 5.10 which achieves 580.097 Mbit/s throughput with 4 colors. So its optimal index equals 145.024. According to the coloring sequence, the next node to color is the node 7. The first power to choose is the power 20 dBm. The new topology is shown in Figure 5.30, where the dashed line indicates the new generated edges of the node 7. From this topology, the skeleton 2 is obtained and then the skeleton 1 integrates the skeleton 2 and the old skeleton 1, as shown in Table 5.11. Before the skeleton treatment, the initialization of skeleton ID is done. As the old skeleton ID of the column 2 is -11, it will be changed to -7 and uses the skeleton 2. Meanwhile, the skeleton ID of the column 1 is changed to 7 and it will use the skeleton 1. Then the skeleton treatment starts from the node 7 in the column 2 with the skeleton 2. From Table 5.11, we can see the change of the next skeleton ID for each columns after treating node 7 using power 20.

The result for this topology is shown in Table 5.12. The column 3 is the best achieving the minimum number of colors, i.e., 5 colors, and the corresponding optimization index equals 138.007. Then, all other powers will be tried to be allocated to the node 7. While allocating the power 14 to the node 7, the result is better. The information for treating the node 7 using power 14 is shown in Table 5.13 and the result is shown in Table 5.14. With this power, the topology is exactly the same as the old best topology in Figure 5.29, as no new edges generated by the node 7 with power 14. The minimum number of colors is still 4 and its optimal index is 167.531, which is larger than that while allocating the power 20 to the node 7. The result of treating the node 7 using different powers is shown in Table 5.15. As its optimization index is the best among all power choices, the power 14 is the best for the node 7. After all nodes are allocated with the power and RB, the final topology graph is shown in Figure 5.31 and the final result is shown in Table 5.16. The topology graph requires 4 colors and the optimization index is 230.103. Using this example, the comparison between different strategies is drawn and the result is shown in Table 5.17. N s denotes the number of columns and N RB is the number of RBs. From the table, we can see that different strategies lead to different results.

Generally, the greedy method has the lowest optimization index, since its performance of the graph coloring performs less better. For other three strategies, they have the same power allocation and graph coloring result, thus they have the same optimal index. In fact, for local PexaCol and DLOA, their result is always the same and for DLOAA, it can get the same result as them for most of the case while dealing with small graphs. With regard to the number of columns, DLOA has the most number of columns, because it stores all columns for the best topology each step. DLOAA has always one column, as it only chooses one best column of the old best topology to calculate. As this graph is small and simple, the results of runtime for all these four algorithms are very small. Although their runtime should be different, the comparison between their runtime is not presented in this example, which exceeds our computer's measure ability. For simplicity, the cluster range and the interference range are considered as squares rather than circles. Each of the following tests is implemented independently for the randomly generated coordinates for 10 times and the average result is used to compare.

The scalarization has been done for the runtime, which ranges from 0 to 1 after being divided by the maximal value of runtime among them. In the tests, the treating sequence is fixed as the node sequence in the ascending order of the node's distance from the center of the cluster.

The first comparison is about the resource allocation result between four strategies for the small graphs. The number of nodes ranges from 4 to 22. The comparison of throughput and the number of RBs are shown in Figure 5.32 and that of the optimal index and runtime are shown in Figure 5.33. From the figure, we can see that s1 and s2 are able to get the better optimization index than the other two algorithms. For the algorithms s1, s2 and s3, their results are the same for most of the cases. As s3 is not an exact method, sometimes its result is little different from that of s1 and s2, such as the case when the number of nodes is 18. However, for s0, it generally requires more number of RBs than the other three strategies while their throughput is approximately the same, so the optimal index of s0 is lower than the other three strategies. As for the runtime, s2 costs the most of time, which is far more than the other three algorithms, because it stores all solutions for all the chosen topologies leading to more runtime to choose the best column. For the small graphs, s3 runs faster than the others, as it largely simplifies the process of s2 and dynamically allocates resource. Then, since s1 and s2 are limited to deal with small graphs, the comparison for larger graphs are drawn between s0 and s3. From Figure 5.34, it can be seen that the throughput for s3 is larger than that of s0, while their number of RBs are approximately the same. Thus, the optimal index of s3 is larger than that of s0, as shown in advantage in runtime and computational complexity, it can still be a good backup for the scenarios when the runtime is a critical factor or when the computational complexity for s3 is high. as the number of nodes increases.

The second comparison is about the performance with different cluster range. In the test, the number of nodes is 100 and the cluster range changes from 100 m to 2000 m.

According to Figure 5.36, as the cluster range increases, the throughput of s3 is much larger than that of s0, and its number of RBs is slightly less than that of s0.

Thus, as shown in Figure 5.37, the optimal index of s3 becomes larger than that of s0 as the cluster range increases. Meanwhile, the runtime of s3 decreases as the cluster range is expanding, while the runtime of s0 is always stable. That is because the graph becomes relatively simpler as the cluster range increases, which makes it easier to do the graph coloring with s3.

With different power levels, another comparison is done between s0 and s3. The number of power available in the given power range leads to different resource allocation results. In this test, the number of nodes is 100 and the cluster range is 1000 m. The number of powers ranges from 2 to 20 and the results are shown in Figure 5.38 and Figure 5.39. As the number of powers increases, s3 performs better both in throughput and number of colors. Thus, its optimal index is much larger than that of s0. As the number of powers increases, the runtime for both strategies increases.

Although s3 takes more runtime than s0, its runtime also increases linearly. As the value a and the value b in Formula 5.14 can influence the throughput and the number of RBs, the test is done to show their relationship. In this test, the number of nodes is 100 and the cluster range is 1200 m. Both value a and value b range from 0 to 4. Each step they will increase by 0.4. For each pair of value a and value b, the random coordinates will generate for 10 times and the average result is obtained. The throughput using s3 with different value a and value b is shown in Figure 5.40 and the corresponding number of RBs is shown in Figure 5.41.

From the result, it can be seen that as the value a increases, the number of RBs decreases and the throughput decreases, which can be explained as that the number of RBs in this case becomes more important than the throughput. Likewise, as the value b increases, both of the throughput and the number of RBs increase, because the throughput is more important now. However, this trend only occurs in a certain range of the value a and value b. For a graph, if the value a or the value b exceeds a certain range, no matter how large it is, the number of RBs and the throughput will stay the same.

Conclusion

In this chapter, the LTE system and the D2D network are introduced as the background.

Then the D2D network is modeled with clusters and a systematic resource allocation method is presented based on clusters, including inter-cluster resource allocation problem and intra-cluster resource allocation problem. In the inter-cluster resource allocation problem, the clusters can be dynamically generated or deleted. On the basis of the topology graph of clusters, the cluster resource allocation problem is formulated into a dynamic graph coloring problem. A dynamic graph coloring algorithm is designed, which is able to obtain a suboptimal resource allocation solution while the topology is changing. The numerical results

show that our algorithm can get a suboptimal solution in terms of resource utilization but it requires much less runtime (even about 10% of the greedy algorithm and 3% of the static algorithm), while the number of D2D clusters is dynamically increasing.

Furthermore, this dynamic algorithm is well adapted to the change of cluster topology, including cluster generating and deleting.

For the intra-cluster resource allocation problem, the topology-based resource allocation scheme is proposed to allocate power and RBs to D2D links to maximize the network throughput and minimize the number of RBs used. An optimization index is used to make a balance between the network throughput and the number of RBs. Four resource allocation algorithms are designed: local greedy algorithm, local PexaCol, DLOA and DLOAA. Among them, DLOA can naturally integrate the resource allocation with the power selection, which uses special mechanism to do the graph coloring while choosing the best power locally with maximal optimization index. Based on DLOA, the approximate DLOAA is proposed to expand its calculation ability. The result analysis

shows that for small-scale D2D cluster, the local PexaCol and DLOA perform better than the other two algorithms in optimization index. DLOAA runs the fastest and for most cases, it is able to get the same optimization index as the local PexaCol and DLOA which is better than that with the local greedy. For large-scale D2D cluster, given certain treating sequences, DLOAA performs better than the local greedy algorithm within an acceptable runtime.

Chapter 6

Conclusions and Future Work

This chapter summarizes all the thesis by stating the main idea of each chapter. Then, the possible future works are presented, as an extention for our previous works.

Conclusions

As a traditional NP-complete problem, the graph coloring problem still cannot be solved, even though the development of the science and the technology nowadays is much faster than ever before. It has so extensive applications in the real world that the exploration for its secret can never stop. Researches on it will continue mathematically and algorithmically leading to more potential applications. In this thesis, the graph coloring problem is studied from a new point of view and some new exact graph coloring algorithms are proposed. Then these algorithms are effectively applied to solve the resource allocation problems in the cluster-based D2D network in LTE system.

Firstly, a survey about graph coloring is illustrated with related definitions. The classification of graph coloring problem and the existing algorithms are presented as the background of our research. The common graph coloring applications are introduced.

Further, the exact graph coloring algorithm TexaCol is illustrated in detail, including algorithm process analysis, C++ implementation and performance analysis. TexaCol plays a fundamental role in this thesis for it uses the special data structure, i.e., the column, to deal with all the coloring process and it partitions the coloring cases based on the graph structure. Given an input graph, it is capable of getting all solutions as well as the chromatic number and the chromatic polynomial by partitioning different coloring cases. However, the performance of TexaCol is extremely limited. It can only get the result for very small graphs due to its high computational complexity. TexaCol has the disadvantage in runtime and computational memory, which greatly confines its application to the reality leading to its further improvement.

Then, as the critical part of our research, two exact algorithms PexaCol and AexaCol are proposed on the basis of TexaCol. Among them, PexaCol uses the backtracking method and only chooses the best column to calculate instead of choosing each columns, which can largely improve the algorithm efficiency. It can gradually expand the search space by generating new columns and by calculating with the best solution, it also searches the result in the deeper direction. PexaCol can get partial best solutions rapidly, substantially increasing its ability for the applications. Based on PexaCol, AexaCol will continue to get all best solutions. The performance analysis shows that these two algorithms can run much faster than TexaCol and deal with much larger graphs. Especially, PexaCol runs the fastest among all these algorithms and AexaCol runs much faster than the famous solver Gurobi to get all best solutions. One of an advantageous of these new exact graph coloring algorithms is that they are able to get multiple best solutions instead of getting only one best solution. So, in some cases, they can provide multiple choices for the application. Another significant superiority of these algorithms is that during the coloring process, they do the coloring by utilizing the coloring constraint of each nodes. Thus, they are suitable to solve the coloring problem while the graph topology or the graph structure is changing.

Furthermore, some applications of our algorithm is presented based on D2D network and LTE system. D2D technology is potential in the future mobile communication system, such as 5G, to provide the proximity communication. Due to its considerable merits, D2D is thought to be an important technique to support the various intelligent networks, like V2V, IoT, smart grid, and so forth. Despite of this, the resource allocation in D2D network plays a pivotal role in its performance in the D2D network. Thus, in this thesis, the resource allocation problem for D2D network in LTE system is studied, which shows profound application significance. The resource allocation scheme for the cluster-based D2D network is proposed, which comprises two parts: the inter-cluster resource allocation and the intra-cluster resource allocation. The former is formulated as a dynamic graph coloring problem to assign RBs to the dynamic cluster such that the minimum number of RBs is used while there is no interference between clusters.

This algorithm can well adapt to the case while adding or deleting the clusters as that in the reality. The result analysis shows that it can run fast to get the suboptimal solution while the topology is changing.

For the intra-cluster resource allocation problem, the goal is to assign RBs and the power to the D2D links. Larger transmit power leads to higher throughput but causes more required RBs. Since the intra-cluster resource allocation problem aims to get the maximal throughput with the minimum number of RBs, it is a joint optimization problem.

A topology-based graph coloring strategy is proposed to get a suboptimal solution, which uses the local topology information to decide the best power and coloring solution for each node. Based on this strategy, four algorithms are proposed: local greedy algorithm, local PexaCol, DLOA and DLOAA. Among them, DLOA is an algorithm which can well integrate the power allocation and the graph coloring to achieve a good optimization index. On the basis of this method, DLOAA is able to obtain the result for larger graphs within an acceptable time. The result analysis shows that among these local methods, the local PexaCol and DLOA can achieve better optimization index for small-scale D2D cluster than the other two algorithms. For most cases, DLOAA can achieve the same optimization index as the local PexaCol and DLOA, which is better than that with the local greedy algorithm. For large-scale D2D cluster, with certain treating sequences, DLOAA performs better than the local greedy algorithm in optimization index within an acceptable runtime.

Future work

For the future works based on our graph coloring algorithms are still interesting. There are mainly two directions: the further improvement of the algorithm efficiency and the new exploration for the applications.

The first direction can be achieved by designing new heuristic algorithms. As aforementioned in this thesis, the coloring sequence and the way of choosing the best column are two potential directions. For the simple greedy algorithm, its coloring sequence depends on the nodes' degree. As an improvement of that, the DSATUR algorithm changes its coloring sequence by using the saturated degree. Similarly, for our algorithm, it is possible to improve it by choosing the good coloring sequence.

On the other hand, the way of choosing the best column will be an effective way to improve the algorithm efficiency, such as the non-dominated column selection of the best columns. This strategy utilizes the same idea as the algorithm Nondominated Sorting Genetic Algorithm (NSGA) in solving the multiobjective optimization problem in [START_REF] Srinivas | Muiltiobjective optimization using nondominated sorting in genetic algorithms[END_REF][START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF]. In PexaCol or AexaCol, each step the best column satisfies the condition that it has the minimum number of colors and if the first condition is satisfied, it should have the maximal number of colored nodes. For each column, the number of colors and the number of nodes are two key parameters to decide whether it is a best column or not. This is actually a multiobjective optimization problem. To simplify the case, this problem is transferred into a single objective problem by using some index, such as numN ode/numColor implying that columns with less number of colors and more number of nodes are expected. These kind of columns are chosen to continue each step while other columns will be deleted from allColumns. By doing this, the computational complexity can be reduced while the suboptimal columns can be obtained. Depending on how many columns are chosen to continue each step, the balance between the computational complexity and the quality of the solution can be well controlled. In our dynamic cluster algorithm, only the old best column is retained to continue the calculation enabling this algorithm to get the suboptimal solution, which is a special case of the column selection.

For other improvements, the parallelized calculation and proper memory mechanism can also be used to improve the algorithm efficiency. As the special data structure, i.e., the columns, is used in our algorithms to deal with the coloring process and each column can be independently calculated by adding the skeleton, the parallelized calculation mechanism using the Graphics Processing Unit (GPU) is suitable to deal with that. If each column is treated by an independent core, the runtime will be largely reduced. Besides, as a possible improvement, our algorithms can be combined with the machine learning to decide the good coloring sequence or to choose the best column.

Another future research point is to explore new applications on the basis of these graphstructure-based methods. Because our graph coloring method is special, it can have comprehensive applications as the traditional graph coloring problem. Note that the applications of our algorithm are not limited to the telecommunication field. They may be used in manufacturing, economics, management, civil engineering, and so on. The premier advantage of our algorithms is that they use the coloring constraint of each node to color the graph, so they can be well used to solve the problems while the topology is changing.

Contents 1 . 1 2 1. 2

 1122 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Objectives and contributions . . . . . . . . . . . . . . . . . . 3 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1

1 . 3 . 5 .

 135 Consequently, partial solutions means a part of complete proper graph coloring solutions, but not means some uncomplete proper graph coloring solutions. So are the partial best solutions, which means a part of best solutions. Definition 3.3. A maximal clique is a maximal vertex set in which all vertices are connected with each other. If all maximal cliques are searched out, we say a graph is decomposed into the maximal cliques. It is possible that one node belongs to more than one maximal cliques. A graph can be decomposed into maximal cliques and all vertices in each maximal clique should be colored differently. In the graph-structure-based algorithm, the coloring is conducted clique by clique, and the connection between cliques leads to different coloring solutions. Definition 3.4. If one maximal clique c 1 has been colored, some other maximal cliques c 2 , ..., c m , m > 1, m ∈ N , have been colored synchronously. Cliques c 2 , ..., c m are called satellite cliques of c Definition While coloring a new vertex v, v ∈ V , all neighboring vertices of v which have been colored are called the skeleton of v. It is composed of two layers: the first layer is the largest set of vertices in skeleton connecting with each other; the second layer contains all other vertices in skeleton. The skeleton for each vertex, including the layer 1 and the layer 2, is also called a cell.

FIGURE 3 . 1 :

 31 FIGURE 3.1: Example of the coloring data structure.

FIGURE 3 . 2 :

 32 FIGURE 3.2: Structure of a graph.

[

  a b][c] and the node a and the node c can be colored the same or not. Suppose in the column to treat treatingColumn, the node a is colored before the node c and the coloring constraint for the node c is [e]. The first column is generated representing the case that the node a and the node c have the same color. In this column, the coloring constraint of the node c is changed into [-a], where the minus sign indicates that these two nodes have the same color. Since the old coloring constraint for the node c is [e],

Algorithm 5 :

 5 FIGURE 3.3: UML class graph for the implementation of TexaCol.

FIGURE 3 . 4 :

 34 FIGURE 3.4: Coloring example for a graph with 8 vertices.

  Figure 4.1. Let m be the total number of columns for subgraphs with different number of

2 ,

 2 ..., m, and the columns with the minimum number of colors are included in the candidate set {s i |c i = minColor}, i = 1, 2, ..., m. Then, the best column is the column in the candidate set who has the maximal number of nodes. If more than one column satisfy the conditions of best column, we can choose one of them randomly.

FIGURE 4. 1 :

 1 FIGURE 4.1: Choose the best column at each step.

Figure 4 . 2 .

 42 Figure 4.2. Note that after coloring a new node, the number of colors will stay the same or increase by 1 at most, for the worst case is equivalent to give the new node a new color. In Figure 4.2, there are two columns to choose: the column 1 with 3 colors and 4 nodes, and the column 2 with the same number of colors and 5 nodes. If we choose

2 FIGURE 4 . 2 :

 242 FIGURE 4.2: The possibility of choosing different columns when the number of colors is equal.

  Figure 4.3. It also contains three steps: maximal clique decomposition, suite construction and node coloring. Note that even the first two steps and the function of treating the skeleton are the same as that in TexaCol, PexaCol utilizes the backtracking method to do the node coloring, in which only the best column for subgraphs rather than each column is chosen out to continue the skeleton treating each step. The functions are explained in detail as follows. chooseBestColumn(): After skeleton treating, this function chooses the best column to continue (see Algorithm 6). The input is allColumns, denoting the old columns for subgraphs. Two indicators are calculated for each column: numColor and numN ode. Then, a best column, which has the minimum numColor and has the maximal numN ode among the columns with the minimum numColor, is chosen from all columns.

  FIGURE 4.3: Flow graph of PexaCol.

5 FIGURE 4

 54 FIGURE 4.4: The input graph and its adjacent matrix.

FIGURE 4 . 5 :

 45 FIGURE 4.5: Example of choosing the best column.

FIGURE 4 . 6 :

 46 FIGURE 4.6: Flow graph of AexaCol.

FIGURE 4

 4 FIGURE 4.7: Example of AexaCol.

FIGURE 4

 4 FIGURE 4.9: Test result for gr n7 0 with different permutations of maximal cliques.

FIGURE 4 .

 4 FIGURE 4.10: Test result for gr n7 0 with different permutations of nodes.

FIGURE 4 .

 4 FIGURE 4.14: Illustration of transfer process between columns in S1 and S3.

LTE is a standardFIGURE 5 . 1 :

 51 FIGURE 5.1: The LTE network architecture.

  FIGURE 5.2: OFDMA and the LTE resource.

1 FIGURE 5 . 3 :

 153 FIGURE 5.3: The architecture of D2D in LTE network.

  the number of DUE pairs explosively increases, the organization and the resource management of the D2D communication become much difficult. The eNodeB will directly coordinate the communication of large numbers of D2D links, which greatly challenges its processing capacity. An alternative mechanism is to organize the D2D network with clusters, and in this way, as a great number of devices can be well organized, the eNodeB's control overhead is substantially reduced. Besides, clustering of DUEs is beneficial to effective resource management and allocation. If RBs are allocated directly to thousands of D2D links, the optimization problem of resource allocation is exceptionally tough to solve. Whereas if RBs are allocated to some clusters and the resource allocation is managed based on clusters, this manner of resource allocation is more practicable. Meanwhile, it assists in reusing the RBs, which is similar to the frequency reuse for the traditional cellular communication. In a word, with better interference control and resource management, the clustering mechanism is appealing to improve the system capacity of D2D network.There are some researches on clustering of D2D communication. In[START_REF] Zhibo | Device-to-device resource allocation for qos support using a graphic theory[END_REF], Z. Wang et al. proposed a clustering algorithm for D2D networks, and then a resource allocation scheme is put forward to maximize the throughput of D2D networks, considering the cluster as the frequency reuse unit for D2D links. In[START_REF] Koskela | Clustering concept using device-to-device communication in cellular system[END_REF], the cluster-based scheduling strategies in D2D network are presented and the result is shown demonstrating its superiority in increasing the network capacity over that in conventional cellular communication. The cluster is formed by using the UE's dual-radio interface, and the game theory method is adopted to assist the clustering process. Other articles about cluster mechanism in D2D networks can be found in [AM13, ZHHC13, KHCL10].

D2D provides a fast

  and reliable approach transferring information between various adjacent devices or entities. With certain commonalities, D2D communication can be an effective enhancement for the Internet-of-Things (IoT). The D2D technique can be naturally incorporated into the Wireless Sensor Network (WSN) so as to facilitate the proximity communication. To some extent, it can contribute to the realization of the future smart cities[START_REF] Usman | A software-defined device-to-device communication architecture for public safety applications in 5g networks[END_REF]. In Machine-to-Machine (M2M) communication, D2D enables proximal machines to exchange information to improve the industrial productivity [LLKC12]. Due to its merits of wide coverage, high data rate and low latency, D2D can support various traffic and safety applications for the Vehicular Adhoc NETwork (VANET) [POC + 15]. Besides, as it accelerates data transfer between local devices, D2D can be a strong support for local services, such as social network applications [FLYW + 14]. In addition to speed up the information transmission, D2D strengthens cooperation for devices. It can assist Multi-User MIMO (MU-MIMO) in the network, by means of serving as the cooperative relaying to form virtual MIMO links [KD17]. D2D can also play a significant role in cooperative localization in 5G networks [DSW15, ZLWW17]. What's more, D2D can bring the data and energy benefits for wearable devices, such as smart health monitoring devices [Sha15]. Another benefit is that D2D can support the emergency communication in the scenarios of some disasters, such as earthquake or other emergency scenarios without access to base stations [HMO + 13]. Due to its flexibility, D2D can survive like ad hoc network to maintain the communication without any infrastructure.

FIGURE 5 . 4 :

 54 FIGURE 5.4: The system architecture based on clusters with identical cluster size.

2 FIGURE 5 . 5 :

 255 FIGURE 5.5: The interference range for clusters.

process has been shown in Figure 5 FIGURE 5 . 6 :

 556 FIGURE 5.6: Resource reuse distance and cluster topology graph.

  ) y c ∈ {0, 1}, c = 1, ..., k (5.6) Formula 5.1 means the minimum number of colors are used. Constraint 5.2 requires that all new vertices are colored. Constraint 5.3 confines that the endpoints of each edge are assigned with different colors. Constraint 5.4 makes sure that the allocated colors for deleted old vertices are released. Constraint 5.5 and 5.6 restrict x and y

FIGURE 5

 5 FIGURE 5.7: Example of dynamic graph coloring algorithm. TABLE 5.3: The skeleton and the coloring case partition.

FIGURE 5 . 8 :

 58 FIGURE 5.8: The initial topology for the example.

FIGURE 5 . 9 :

 59 FIGURE 5.9: The process of the topology change for 6 times.

FIGURE 5 .

 5 FIGURE 5.10: Comparison of three algorithms in the number of RBs and the runtime.

FIGURE 5 .

 5 FIGURE 5.11: Number of RBs required while randomly adding and deleting clusters.

FIGURE 5 . 12 :

 512 FIGURE 5.12: System architecture for intra-cluster resource allocation.

FIGURE 5 .

 5 FIGURE 5.13: D2D link communication with minimum power.

FIGURE 5 .

 5 FIGURE 5.14: D2D link communication with larger power and its interference range.

FIGURE 5 .

 5 FIGURE 5.15: Different powers lead to different topologies.

FIGURE 5 .

 5 FIGURE 5.16: Different strategies for intra-cluster resource allocation problem.

FIGURE 5 .

 5 FIGURE 5.17: Flow graph of the resource allocation algorithm based on local optimization.

  is a number used to indicate the location of the coloring constraint in the skeleton for next node to treat, denoted by nextSkeletonID. If a column will add a node's coloring constraint in skeleton 2 to treat, there is a minus sign in the next skeleton ID to indicate that. Then, this column's absolute value of the next skeleton ID indicate the location of the coloring constraint for the next node to treat.

FIGURE 5 .

 5 FIGURE 5.18: Algorithm flow graph for graphColoringDLOA().

  FIGURE 5.19: The topology graph while treating v i with power p 1 .

FIGURE 5 .

 5 FIGURE 5.21: Skeleton treatment of v i in column 3 while allocating power p 1 to v i .

FIGURE 5 .

 5 FIGURE 5.22: Skeleton treatment of v i-1 in column 1 while allocating power p 1 to v i .

  FIGURE 5.24: The topology graph while treating v i with power p 2 .

FIGURE 5 .

 5 FIGURE 5.25: Skeleton treatment of v i in column 3 while allocating power p 2 to v i .

FIGURE 5 .

 5 FIGURE 5.27: Skeleton treatment of v i+1 in column i + 3 when v i+1 uses power p 1 .

FIGURE 5 .

 5 FIGURE 5.28: Distribution of nodes and their coordinates.

FIGURE 5 .

 5 FIGURE 5.29: The best topology after treating the first six nodes.

FIGURE 5 .

 5 FIGURE 5.30: The best topology after treating node 7 using power 20.

FIGURE 5 .

 5 FIGURE 5.31: The best topology after treating all nodes.

FIGURE 5 .

 5 FIGURE 5.32: The comparison of throughput and number of RBs between four strategies as the number of nodes increases.

Figure 5 .FIGURE 5 .

 55 Figure 5.35. It can be seen from Figure5.35 that the runtime of s3 is more than that of s0. However, considering that s0 has almost constant time complexity, the runtime of s3 is still acceptable compared to that of s0. Note that in the practical application, it is unnecessary to organize a cluster containing a very large number of devices which may contradict the motivation of clustering. This further shows the competence of s3 in dealing with the resource allocation for D2D cluster in practice. Since s0 has the

FIGURE 5 .

 5 FIGURE 5.34: The comparison of throughput and number of RBs between s0 and s3as the number of nodes increases.

FIGURE 5 .FIGURE 5 .

 55 FIGURE 5.35: The comparison of optimal index and runtime between s0 and s3 as the number of nodes increases.

FIGURE 5 .FIGURE 5 .

 55 FIGURE 5.37: The comparison of optimal index and runtime between s0 and s3 for different cluster range.

FIGURE 5 .FIGURE 5 .

 55 FIGURE 5.39: The comparison of optimal index and runtime between s0 and s3 for different power levels.

FIGURE 5 .

 5 FIGURE 5.41: The number of RBs using s3 for random graphs as the value a and b change.

Contents 6. 1

 1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

For the future work 2 :

 2 of the resource allocation problem in D2D network, it is possible to propose new algorithms based on new clustering mechanisms. Meanwhile, new resource allocation algorithms are expected combining with mode selection, QoS requirement, energy and so forth. In addition, other optimization indices are anticipated to evaluate the performance of the D2D resource allocation.TABLE A.1: Result of TexaCol for some graphs (part 1) Result of TexaCol for some graphs (part 2)

  TexaCol is an exact graph coloring algorithm proposed by Jean-noel Martin[START_REF] Martin | No Free Lunch et recherche de solutions structurantes en coloration[END_REF]. It is a graph-structure-based algorithm, which studies the graph coloring from the graph structure point of view. Based on the fact that the graph structure has significant influence on graph coloring, this algorithm decomposes a graph G into maximal cliques and colors the graph clique by clique considering the connection between these maximal cliques. In the algorithm, a special data structure is used to deal with all the coloring process, and finally all proper coloring solutions of G are partitioned into several solution subsets according to different coloring cases. For instance, if two nodes can have the same color, this gives rise to one solution subset, representing the case

Contents 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Graph-structure-based method . . . . . . . . . . . . . . . . . 19 3.4.1 Graph structure analysis . . . . . . . . . . . . . . . . . . . . . . 19 3.4.2 Coloring case partition . . . . . . . . . . . . . . . . . . . . . . . 20 3.5 Algorithm of TexaCol . . . . . . . . . . . . . . . . . . . . . . . 21 3.5.1 Maximal clique decomposition . . . . . . . . . . . . . . . . . . 21 3.5.2 Suite construction . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.5.3 Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.5.4 C++ implementation . . . . . . . . . . . . . . . . . . . . . . . 24 3.5.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.6 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . 28 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1 Introduction that they are colored the same; meanwhile, another solution subset can be obtained, which means the case that they are colored differently. This algorithm can obtain all proper coloring solutions for a given graph G by listing all solution subsets without repetition. Furthermore, given the number of colors k, the chromatic polynomial for graph G can be achieved according to the structure of these solution subsets. Generally, TexaCol is composed of three steps: maximal clique decomposition, suite construction and node coloring. The first two steps, as the prerequisite for node coloring, are engaged in decomposing the input graph into maximal cliques and getting a suitable sequence of them to conduct the coloring process. The third step attains all the proper coloring solutions by means of analyzing the relationship between these maximal cliques while coloring them one by one. Compared with other exact graph coloring algorithms, TexaCol has no advantages in the computational complexity, however, it provides a new perspective of graph coloring by analyzing the graph structure, which shows great theoretical significance. In TexaCol, all coloring solutions are divided into solution subsets according to the graph structure, which distinguishes it from other algorithms. On the other hand, TexaCol is capable of getting the chromatic polynomial, which is impossible for most of the existed graph coloring algorithms.

  If the chromatic number is k, each proper k-coloring solution is called one best solution. All best solutions is the set of all proper k-coloring solutions when k is the chromatic number. If not all but a part of the best solutions are found, we call that partial best solutions, i.e., a best solution subset.

	Definition 3.1. For the proper coloring of graph G, each proper coloring solution is
	called one solution and all proper coloring solutions are called all solutions. Partial
	solutions are defined as a proper coloring solution subset and all of these subsets
	compose all solutions.
	Definition 3.2.

  Given the coloring sequence, a column denotes a proper coloring solution subset and they are equivalent in the aftermentioned part. All this kind of columns compose all graph coloring solutions. In each column, each node's coloring constraint is indicated, containing either the set of nodes which should have different colors or the same color with this node. The minus sign means two nodes have the same color. Specially, if a new node can have the same color with some colored nodes, we find the first colored node among them and add a minus sign before it as the coloring constraint of this new node. Given the number of colors k, a factor representing the number of optional colors

for each node, can be obtained from each node's coloring constraint. The chromatic polynomial for a column, indicating the number of solutions included in this column, is the product of all nodes' factors. Then the chromatic polynomial for the graph is the sum of all column's chromatic polynomials. The number of colors for a column equals the maximal number of nodes in all nodes' coloring constraint plus 1. While coloring,

Algorithm 2: Maximal clique decomposition algorithm Input: graph matrix G Output: maximal cliques cliqueSet

	Initialization: cliqueSet ← ∅, cliqueV ector ← ∅, candidateSet ← ∅,
	maximalClique ← ∅.
	for i from 1 to numN odes do
	cliqueV ector ← ∅;
	add i to cliqueV ector;
	for j from i + 1 to numN odes do
	if node i and node j are connected then
	add j to the candidateSet;
	if candidateSet = ∅ then
	maximalClique ← judgeClique(cliqueV ector, candidateSet);
	add maximalClique to cliqueSet;
	else
	if node i has no adjacent nodes then
	add i to cliqueSet as the clique of size 1;
	output cliqueSet;
	Algorithm 3: Algorithm process for judgeClique()
	Input: cliqueV ector, candidateOld
	Output: maximal clique maximalClique
	sizeCandidateOld ← sizeof (candidateOld);
	for i from 1 to sizeCandidateOld do
	if candidateOld[i] is larger than all values in cliqueV ector then
	if candidateOld[i] is adjacent to all vertices in cliqueV ector then
	add candidateOld[i] to candidateN ew;

if candidateN ew = ∅ then output maximalClique; else maximalClique ← judgeClique(cliqueV ector, candidateN ew);

for i from 1 to numCliqueRest do if maxContact(cliqueRest[i]) > maximalContact then

	Algorithm 4: Suite construction algorithm
	Input: maximal cliques cliqueSet
	Output: clique suite cliqueSuite
	Initialization:cliqueSuite ← ∅, maximalConstraint ← 0.
	numM aximalCliques ← sizeof (cliqueSet);
	cliqueRest = cliqueSet;
	/* Phase 1: choose the clique with maximal constraint	*/
	for i from 1 to numM aximalCliques do
	if constraint(cliqueSet[i]) > maximalConstraint then
	maximalConstraint = constraint(cliqueSet[i]);
	cliqueM aximalConstraint = cliqueSet[i];
	add cliqueM aximalConstraint to cliqueSuite;
	delete cliqueM aximalConstraint in cliqueRest;
	/* Phase 2: choose the clique with maximal contact	*/
	while sizeof (numCliqueRest) > 0 do
	numCliqueRest ← sizeof (cliqueRest);
	maximalContact ← 0;
	maximalContact = maxContact(cliqueRest[i]);
	cliqueM aximalContact = cliqueRest[i];
	add cliqueM aximalContact to cliqueSuite;
	delete cliqueM aximalContact in cliqueRest;

TABLE 3 . 1 :

 31 Basic information and coloring result for the first 7 nodes.

	Maximal cliques	Suite	Coloring sequence	Skeleton	Color constraint for the first 7 nodes
	{1,2,3,4}	{2,4,5,6}	2	[ ]	[ ]
	{2,3,4,5}	{2,3,4,5}	4	[2]	[2]
	{2,4,5,6}	{2,4,6,8}	5	[4 2]	[4 2]
	{2,4,6,8}	{1,2,3,4}	6	[5 4 2]	[5 4 2]
	{4,6,7,8}	{4,6,7,8}	3	[5 4 2]	[5 4 2]
	{3,4,7}	{3,4,7}	8	[6 4 2]	[6 4 2]
			1	[3 4 2]	[3 4 2]
			7	[8 6 4][3]

TABLE 3 .

 3 2: Final coloring result for the example.

	Coloring sequence	Column 1 Column 2 Column 3
	2

TABLE 3

 3

		k=4	k=5	k=6	k=7	k=8	k=9	k=10	k=11
	TexaCol	144	2280 16560 78120 278880 819504 2086560	4759920
	Exhaustive search 144	2280 16560 78120 278880 819504 2086560	4759920

.3: Number of different proper coloring solutions for gr n7 0.

Algorithm 6 :

 6 Function chooseBestColumn() best column S best Initialization: numColor ← ∅, numN ode ← ∅, minColor ← 0, maxN ode ← 0, S best ← ∅. /* Phase 1: get numN ode and numColor */ for each new generated column in allColumns do get the corresponding numN ode and numColor;

	Input: allColumns
	Output: /* Phase2: choose the best column	*/
	minColor ← numColor[1];
	maxN ode ← numN ode[1];
	numColumns ← sizeof (allColumns);
	for i from 1 to numColumns do
	if numColor[i + 1] < minColor /* If columns with less colors have been found	*/
	then
	S best ← allColumns[i + 1];
	minColor ← numColor[i + 1];
	maxN ode ← numN ode[i + 1]; /* Update minColor and maxN ode	*/
	else if numColor[i + 1] = minColor then
	if numN ode[i + 1] > maxN ode/* Choose the column with more nodes	*/
	then
	S

best ← allColumns[i + 1]; maxN ode ← numN ode[i + 1];

TABLE 4 .

 4

1: Basic information for coloring the input graph.

Suite

Coloring sequence Skeleton Column for the first 5 nodes

TABLE 4 .

 4 2: allColumns for the the example of AexaCol.

	Coloring sequence Column 1 Column 2 Column 3 Column 4 Column 5
	4	[ ]	[ ]	[ ]	[ ]	[ ]
	5	[4]	[4]	[4]	[4]	[4]
	6	[4 5]	[4 5]	[4 5]	[4 5]	[4 5]
	7	[4 5 6]	[-6]	[4 5 6]	[4 5 6]	[-6]
	8	[4 5 7 6]	[4 5 6]	[4 5 7 6]	[-6]	[4 5 6]
	3	[4 6 7]	[4 6]	[4 6 7]	[4 6 7]	[4 6]
	1	[5 6 8]	[5 6 8]	[-8]	[5 6]	[-8]
	9	[1 6 8]	[1 6 8]	[8 6]	[1 6]	[8 6]
	2		[1 6]		[1 6]	[8 6]
	Number of colors	5	4	5	4	4
	4.4.1 Comparison with Gurobi

Firstly, as there are really few algorithms who are engaged in getting all best solutions, our algorithm AexaCol is compared with the famous solver Gurobi in getting all best coloring solutions

[START_REF]Gurobi Optimization[END_REF]

. Both Gurobi and our algorithm are implemented in C++.

We let Gurobi to get the chromatic number first with the objective of using the minimal number of colors and the constraints that each node has one color and all adjacent nodes are colored differently. Then we use it to get all best solutions based on the same objective and constraints by setting the model parameter "PoolSearchMode". As Gurobi cannot finish most of the small DIMACS graphs, in order to draw the comparison, a lot of random graphs are used. All graphs whose name begins with "gr " are created randomly by ourselves, while all other graphs are DIMACS benchmark graphs. The result is shown in Table

4

.3. V denotes the number of nodes and E denotes the number of edges. χ is the chromatic number. N a is the number of all best coloring solutions, and t is the runtime, whose unit is second. While Gurobi and AexaCol can both get all best solutions for the instances, the comparison is drawn on runtime. As shown in the table, AexaCol can run much faster than Gurobi. For all these graphs, AexaCol can get all best coloring solutions very quickly. However, Gurobi costs a lot of time. Taking gr n23 e80 for example, Gurobi's runtime is 193190 times of that with AexaCol.

  Table A.3. N c is the minimum number of colors required for the best columns in each algorithm. Because the number of all best solutions N

a can be really large, its decimal is rounded off. For example, for the DIMACS graph myciel4.col, N a is 2.84566e+09. After being rounded off, it is written as 2.85e+09. N s represents the number of columns in allColumns when the algorithm is finished. In our result,

TABLE 4 .

 4 3: Comparison between AexaCol and Gurobi.

	Graph name	V	E	χ	Na	Gurobi	t(s) AexaCol
	queen5 5.col 25	160	5	240	0.303		0.011
	gr n15 e25	15	25	4	147456 102.335	0.003
	gr n15 e30	15	30	4	36864	7.111		0.002
	gr n20 e87	20	87	5	2880	0.362		0.006
	gr n17 e20	17	20	3	52488	15.442		0.002
	gr n18 e35	18	35	4	24576	4.428		0.002
	gr n18 e64	18	64	5	61919	24.417		0.026
	gr n17 e65	17	65	5	127200 101.460	0.017
	gr n15 e28	15	28	4	150523 123.103	0.002
	gr n19 e47	19	47	4	24576	4.449		0.002
	gr n19 e49	19	49	4	18432	2.985		0.003
	gr n22 e80	22	80	5	150000 124.792	0.004
	gr n23 e80	23	80	5	300000 579.571	0.003

it has counted the best columns for the subgraph each step. That means, we do not delete them in the data structure after having chosen and treated them. Generally, it will consume more computer's memory with larger N s . The backslash means the result cannot be obtained.

From the table, it can be seen that TexaCol is unable to get the solutions for a lot of graphs, for it calculates all columns of each subgraph rather than the best column, which has very high computational complexity. Here the space complexity is the key problem. For TexaCol, it often crashes due to the memory shortage because it has extremely large N s . As shown in the Table A.3, even for very small graphs, TexaCol has larger N s than two other algorithms and PexaCol always has the least N s . So TexaCol fails to get the result for a lot of graphs and AexaCol fails for few graphs while PexaCol can get the result. On the other hand, N s reflects the range of choosing the best column, signifying that the less N s , the less runtime. In general, PexaCol runs much faster than AexaCol and AexaCol runs much faster than TexaCol. For instance, for the graph gr n15 e51, PexaCol's runtime is about 12% of AexaCol's and 0.7% of TexaCol's.

Moreover, for TexaCol and AexaCol, they are always able to get all best solutions while PexaCol can only get a part of best solutions, which obviously shows that finding more best solutions costs more time. Taking myciel3.col for example, PexaCol runs 25 times faster than AexaCol, but it can only get 384 best solutions, while the number of all best solutions is 12480.

Table 4

 4

	7
			2
		1
			3
		4
	5		6
	FIGURE 4.8: The input graph gr n7 0.
	TABLE 4.4: Basic information for gr n7 0.
	numNode numEdge numMaxClique chromaticNumber
	7	14	8	4

.4. From the table, we can see that this graph has eight maximal cliques of size three. The test is run to record the number of columns with different coloring sequences and then, from the statistics, the distribution of the number of columns is obtained.

Since in the original edition of TexaCol, the nodes' coloring sequence depends on the suite, i.e., the coloring sequence of the maximal cliques, the test is also done with different permutations of maximal cliques.

TABLE 4

 4 In Figure4.11, it is the statistic of the number of columns for a graph with 10 nodes and 26 edges, called gr n10 e26. Because the number of permutations of maximal cliques is extremely large, only one million of them is randomly chosen as the statistic data.From the figure, we can see that the number of columns varies in a large range, from 9 to 137. And the appearance frequency for columns is not uniformly distributed.

	.5: Comparison between clique permutations and node permutations for
		gr n7 0.
		Clique permutations Node permutations
	Number of permutations	40320	5040
	Minimal number of columns	5	5
	Maximal number of columns	11	16

FIGURE 4.11: The statistic of the number of columns for gr n10 e26 with different permutations of cliques.

  Rule 1: Some columns with different coloring sequences are actually the same and they can be transformed between each other naturally, because they represent the same coloring case. The reason is that they have the similar skeleton. On the contrary, if we change one coloring sequence into another,

			mycliel3 (node permutation)
		18000
	Number of occurrences	2000 4000 6000 8000 10000 12000 14000 16000
		0
		51	227	381	535	689	843	997	1151	1305	1459	1613	1767	1921	2075	2229	2383	2537	2691	2847	3002	3157
									Number of columns
	FIGURE 4.12: Test result for graph myciel3 with different permutations of nodes.

then if their skeletons are intrinsically identical, we can get the same number of columns, representing the same number of different coloring cases.

TABLE 4 .

 4 6: Statistics for the graph in the example.

	Number of columns Number of occurrences
	1	14
	2	4
	3	6

Table 4 .

 4 7, they are results with four different coloring sequences leading to the same number of columns, i.e., two columns. We use S1, S2, S3, S4 to represent each of these 4 results. We can see that S1 can be transformed to S2 directly by changing the coloring constraint for each node and vice versa. They have the similar skeleton, and the only difference between their skeletons is the initial coloring constraint for the node 1 and the node 4, which has almost no influence on the coloring case. Likewise for the result S3 and S4.

TABLE 4

 4

	Sequence index	Coloring sequence Skeleton Solution set 1 Solution set 2
		1
	S1

.7: Comparison between the columns with different coloring sequences

Table 5 .

 5 1. It can be learnt from this table that the number of RBs in LTE system is really limited.

Therefore, the effective RB management and assignment to efficiently reuse it becomes indispensable.

TABLE 5 .

 5

1: Bandwidth and the number of RBs in LTE system.

Table 5

 5

.2 [GJ16, AJM14].

TABLE 5 .

 5 2: Four sorts of D2D communication mode.From the table, for D2D communication, DUEs either share the same RBs with the CUEs, or use some dedicated RBs. No matter which resource sharing mode used, the interference between DUEs and CUEs should be well considered. In this thesis, it is assumed that DUEs use the dedicated RBs working in the dedicated mode, although our resource allocation method is also applicable to other resource sharing mode with little modifications.

	Silent mode	DUE keep silent without using RBs, thus no communication exists.
	Cellular mode	The traditional cellular communication via eNodeB.
	Reuse mode	As DUEs and CUEs share common RBs, resource contention and reuse coexist.
	Dedicated mode	DUEs enjoy dedicated RBs for D2D communication.

Algorithm 7 :

 7 Dynamic graph coloring algorithm Input: graph matrix G t and G t-1 , t = 1, 2, ..., m with m a natural number, old best column S t-1 Output: best column S t Initialization:

TABLE 5 .

 5 4: The process of getting the new best column.

	sv	St	suiteN ew	sv	S t	sv	S t+1
	1

TABLE 5 .

 5 6: Graph coloring result for 6 topology changes.

			Topology change 1					Topology change 2
	sv	St	suiteN ew	S t	S t+1	sv	St	suiteN ew	S t	S t+1
	1	[ ]	{3,6,7}	[

  Note that normally |V 0 | and |V add | can be chosen randomly if they are not too large, for a large |V 0 | or |V add | may directly cause the failure of the coloring. In this test, depending on different graphs, we firstly select a |V 0 | which can be calculated byPexaCol. Then |V add | is as large as possible which do not exceed the computational all these rest vertices will be added in to finish the adding process. In this way, the dynamic characteristic of the network is simulated. The result numColor is given to do the comparison with the chromatic number χ for the static graphs in DIMACS, i.e., the optimal graph coloring solution. The coloring result of dynamic graphs built from DIMACS is shown in Table5.7. |V | denotes the number of nodes and |E| denotes the number of edges. As it is shown in Table5.7, our algorithm obviously builds suboptimal solutions for these graphs by using multiple steps of coloring for each graph, therefore, it has the advantage of high resource utilization despite the dynamic change of the cluster topology.

	1]	[-13]
	18	[13 7 1]
	17	[7 1]
	graph.

ability of our dynamic algorithm. For some graphs relatively simple such as anna.col, we set |V 0 | to be all number of vertices and |V add | to be 0. The adding process stops if all vertices have been added and when the rest vertices to add are less than |V add |,

TABLE 5 .

 5 7: Coloring result of dynamic graphs built from DIMACS.

	Instance	|V |	|E|	χ	numColor	|V 0 | |V add |
	games120.col	120	638	9	9	60	30
	miles250.col	128	387	8	8	40	10
	myciel3.col	11	20	4	4	11	0
	queen5 5.col	25	160	5	5	25	0
	queen6 6.col	36	290	7	9	18	18
	queen7 7.col	49	476	7	11	20	18
	queen8 8.col	64	728	9	11	26	18
	queen8 12.col	96	1368 12	14	46	25
	queen9 9.col	81	2112 10	13	28	20
	queen10 10.col 100 2940	?	13	40	20
	queen11 11.col 121 3960 11	18	60	12
	anna.col	138	493	11	11	138	0

TABLE 5 .

 5 8: Performance gap of the dynamic algorithm compared to the static algorithm in the number of RBs and runtime.

	Time (unit)	0	1	2	3	4	5	6	7	8	9	10
	numRBs(+%)	0	11	14	16	19	19 18	24	27	27	28
	runtime(-%)	49	85	84	86	88	87 86	89	95	97	97

  Coordinate vector of all nodes coordinatesOutput: best column S best , power allocation vector powerAllocation Initialization: S best ← ∅, powerAllocation ← ∅, k = 0.

	Algorithm 8: Pseudocode of DLOA
	/* Pretreatment	*/
	treatSequence = getT reatSequence(coordinates);
	arrange the power vector allP owers in descending order;
	/* Allocate resource node by node according to the treating sequence	*/
	while sizeof (nodeT reated) |V | do
	nodetoT reat ← treatSequence[k];
	optimationIndexM ax ← 0;
	/* Try the larger power first	*/
	for i from 1 to sizeof (allP owers) do
	/* Topology construct based on the old best topology and the input power	*/
	topologyN ew = topologyConstruct(topologyOld, allP owers[i]);
	/* Graph coloring based on the new topology and the solution of the old best topology	*/
	(numColor, S best , allColumnsN ew, skeletonN ew, nextskeletonIDN ew) =
	graphColoringDLOA(topologyN ew, allColumnsOld, skeletonOld, nextskeletonIDOld);
	/* Calculate the optimal index	*/
	throughputN ew ← throughputOld + throughputCalculate(allP owers[i]);
	optimationIndexN ew ← throughputN ew b /numColor a ;
	/* Choose the power with the highest optimal index and update the relevant information */
	if optimationIndexN ew > optimationIndexM ax then
	powerBest ← allP owers[i];
	optimationIndexM ax ← optimationIndex;
	throughputBest ← throughputN ew;
	numColorBest ← numColor;
	topologyBest ← topologyN ew;
	allColumnsBest ← allColumnsN ew;
	skeletonBest ← skeletonN ew;
	nextskeletonIDBest ← nextskeletonIDN ew;
	/* Update information of the old best topology	*/
	topologyOld ← topologyBest;
	throughputOld ← throughputBest;
	allColumnsOld ← allColumnsBest;
	skeletonOld ← skeletonBest;
	nextskeletonIDOld ← nextskeletonIDBest;
	add powerBest to powerAllocation;
	add nodetoT reat to nodeT reated;
	k ← k + 1;
	/* Output the result	*/
	output S best and powerAllocation;

Input:

  nextSkeletonID[i] will be changed to -sizeN odeT reated, where m is the total number of columns and sizeN odeT reated is the number of treated nodes. If sizeN odeT reated |nextSkeletonIDOld[i]|

	Start
	Input graph matrix G,
	oldNextSkeletonID,
	allColumns, Sbest=Ø
	nextSkeletonID=initialNextSkeletonID
	(oldNextSkeletonID)
	(skeleton1,skeleton2)
	=createSkeletonDynamic(oldSkeleton1)
	Sbest =chooseBestColumnDynamic
	(allColumns, nextSkeletonID)
	solutionSize=|nextSkeletonID of Sbest|-1
	solutionSize=|V|	N
	Y	newColumns=skeletonTreatDynamic
	Output Sbest	(Sbest, allColumns, nextSkeletonID, skeleton1, skeleton2)
	end	Add newColumns to allColumns and delete Sbest
		Update nextSkeletonID

TABLE 5 .

 5 9: The relevant information after treating the first six nodes.

	Coloring sequence Old skeleton 1 Column 1 Column 2 Power allocated
	6	[ ][ ]	[ ]	[ ]	20
	10	[ ][6]	[6]	[6]	20
	5	[ ][6 10]	[6 10]	[6 10]	20
	9	[ ][6 10 5]	[6 10 5]	[6 10 5]	8
	4	[ ][6 10 5]	[6 10 5]	[6 10 5]	8
	1	[ ][6 10 9]	[6 10 9 5]	[-5]	20
	7	[ ][6 10 5 1]	[6 10 5 1]	[6 10 5]
	3	[ ][6 10 1]	[6 10]	[6 10 5]
	2	[ ][6 10 5 1]	[6 10 5]	[6 10 5]
	8	[ ][6 5]	[6 5]	[6 5]
	Next skeleton ID	-8	-11

TABLE 5 .

 5 10: Result after treating treating the first six nodes.

	Number of columns	2
	Throughput (Mbit/s) 580.097
	numColor	4
	Optimization index	145.024

TABLE 5 .

 5 11: The relevant information after treating node 7 using power 20.

	Coloring sequence	Connected nodes	Skeleton 1	Skeleton 2	Column 1	Column 2	Column 3	Column 4	Power allocated
	6	6	[ ][ ]		[ ]	[ ]	[ ]	[ ]	20
	10	10	[ ][6]		[6]	[6]	[6]	[6]	20
	5	5	[ ][6 10]		[6 10]	[6 10]	[6 10]	[6 10]	20
	9	4	[ ][6 10 5]		[6 10 5]	[6 10 5]	[6 10 5]	[6 10 5]	8
	4	1	[ ][6 10 5]		[6 10 5 9]	[6 10 5]	[6 10 5 9]	[-9]	8
	1	3	[ ][6 10 9]		[6 10 9 5 4]	[-5]	[-4]	[6 10 9 5]	20
	7	8	[ ][6 10 5 1 4]	[ ][6 10 5 4 1]	[6 10 5 1 4]	[6 10 5 4]	[6 10 5 4]	[6 10 5 1 9]	20
	3		[ ][6 10 1 7]	[ ][7]	[6 10]	[6 10 5]	[6 10 4 7]	[6 10 1 7]
	2		[ ][6 10 5 1]	[ ][ ]	[6 10 5]	[6 10 5]	[6 10 5 4]	[6 10 5]
	8		[ ][6 5 7]	[ ][7]	[6 5]	[6 5]	[6 5 7]	[6 5]
		Next skeleton ID		8	-8	11	9

TABLE 5 .

 5 12: Result after treating node 7 using power 20.

	Number of columns	4
	Throughput (Mbit/s) 690.033
	numColor	5
	Optimization index	138.007

TABLE 5 .

 5 13: The relevant information after treating node 7 using power 14.

	Coloring sequence Connected nodes	Skeleton 1	Skeleton 2 Column 1 Column 2 Power allocated
	6	6	[ ][ ]		[ ]	[ ]	20
	10	10	[ ][6]		[6]	[6]	20
	5	5	[ ][6 10]		[6 10]	[6 10]	20
	9	1	[ ][6 10 5]		[6 10 5]	[6 10 5]	8
	4		[ ][6 10 5]		[6 10 5]	[6 10 5]	8
	1		[ ][6 10 9]		[6 10 9 5]	[-5]	20
	7		[ ][6 10 5 1]	[ ][6 1]	[6 10 5 1]	[6 10 5]	14
	3		[ ][6 10 1]	[ ][ ]	[6 10]	[6 10 5]
	2		[ ][6 10 5 1]	[ ][ ]	[6 10 5]	[6 10 5]
	8		[ ][6 5]	[ ][ ]	[6 5]	[6 5]
		Next skeleton ID			8	-11

TABLE 5 .

 5 14: Result after treating node 7 using power 14.

	Number of columns	2
	Throughput (Mbit/s) 670.122
	numColor	4
	Optimization index	167.531

TABLE 5 .

 5 15: Results while treating node 7 using different powers.

	Power (dBm)	Connected nodes Number of columns	Throughput (Mbit/s)	numColor	Optimization index
	20	6 10 5 4 1 3 8	4	690.033	5	138.007
	14	6 10 5 1	2	670.122	4	167.531
	8	6 10 5 1	2	650.275	4	162.569
	2	6 10 5 1	2	630.671	4	157.668
	-4	6 10 5 1	2	611.977	4	152.994
	-10	6 10 5 1	2	596.128	4	149.032

TABLE 5 .

 5 16: The final result of optimal index.

	Number of columns	7
	Throughput (Mbit/s) 920.413
	numColor	4
	Optimization index	230.103

TABLE 5 .

 5 17: Comparison between different strategies. Only the outdoor to outdoor scenario is used and only the Line-of-Sight (LoS) propagation is considered in our simulation. Without expressly emphasizing, the parameters used in our tests are in Table5.18. As for the interference threshold, it is thought that if the receive power is below -114 dBm, no interference exists. As both of the parameters a and b equal to 1, the same importance is given to the throughput and the RB dimension in this analysis.The interference range is calculated under the LTE D2D channel model with the parameters in Table5.18. With this channel model, in Table5.19, the available power and their corresponding interference range are shown.

	Strategy	Ns	Throughput (Mbit/s)	N RB	Optimization index			Power allocation for nodes (dBm)
	Static greedy	\	744.696	4	186.174	20	20	20	8	8	2	-4	8	-4	14
	Static PexaCol	3	920.413	4	230.103	20	20	20	8	8	20	14	8	8	20
	DLOA	7	920.413	4	230.103	20	20	20	8	8	20	14	8	8	20
	DLOAA	1	920.413	4	230.103	20	20	20	8	8	20	14	8	8	20

TABLE 5 .

 5 18: Some parameters in the test.

	Range(m)	1000
	fc (MHz)	2000
	System Bandwidth (MHz)	10
	Minimal power (dBm)	-10
	Maximal power (dBm)	20
	D2D pair distance (m)	40
	Noise spectral density (dBm/MHz)	-174
	Interference threshold (dBm)	-114
	Lognormal shadow fading (dB)	7
	Value a	1
	Value b	1

TABLE 5 .

 5 19: The power and the corresponding interference range in the test.

	Power (dBm)	-10	-4	2	8	14	20
	Range (m)	127.161 179.619 253.719 358.388 506.236 715.078

Acknowledgements

I would like to thank the China Scholarship Council (CSC) for the financial support for my PhD study in France.

My sincere gratitude is expressed to my advisor Professor Alexandre Caminada, who is so open-minded, experienced and easy-going. helped me do the implementations.

Besides, special thanks to another co-supervisor Jean-No ël Martin, whose previous work is the foundation for my PhD work.

Publications International Conferences

Abstract:

Graph coloring problem is a famous NP-complete problem, which has extensive applications. In the thesis, new exact graph coloring algorithms are researched from a graph structure point of view. Based on Total solutions Exact graph Coloring algorithm (TexaCol) which is capable of getting all coloring solution subsets for each subgraph, two other exact algorithms, Partial best solutions Exact graph Coloring algorithm (PexaCol) and All best solutions Exact graph Coloring algorithm (AexaCol), are presented to get multiple best solutions. These two algorithms utilize the backtracking method, in which they only choose the best solution subset each step to continue the coloring until partial or all best solutions are obtained. The result analysis shows that PexaCol and AexaCol can deal with larger graphs than TexaCol and especially, AexaCol runs much faster than TexaCol and the solver Gurobi to get all best solutions. Device-to-Device (D2D) is a promising technique for the future mobile networks, such as 5th generation wireless systems (5G), and the resource allocation is one of the most crucial problems for its performance. In order to efficiently allocate radio resource for D2D links in Long-Term Evolution (LTE) system, a systematic resource allocation scheme is proposed based on D2D clusters, including the inter-cluster resource allocation and the intra-cluster resource allocation. With the cluster interference range, the inter-cluster resource allocation problem is formulated as a dynamic graph coloring problem, and a dynamic graph coloring algorithm is designed based on PexaCol. This algorithm is able to allocate radio resource to clusters while they are dynamically generated and deleted. The numerical analysis results show that this algorithm has good performance in resource utilization, runtime and scalability.

For the intra-cluster resource allocation problem, a topology-based resource allocation method is designed naturally combining power allocation with Resource Block (RB) allocation. To simplify this associated optimization problem, a local optimal method is proposed, in which the best topology is chosen each step achieving the maximal throughput with the minimum number of assigned RBs. With respect to this method, four algorithms are presented: static greedy, static PexaCol, dynamic PexaCol and dynamic PexaCol approximate. Result analysis shows that for small-scale clusters, static PexaCol and dynamic PexaCol are capable of getting a maximal optimization index by locally choosing the best topology for each node while static greedy and dynamic PexaCol approximate are able to get the suboptimal solution for the local optimization with much lower complexity. For large-scale clusters, giving certain treating sequences, the dynamic PexaCol approximate performs better than static greedy regarding the optimization index within an acceptable runtime.

Keywords: Graph coloring, Long-Term Evolution (LTE), Device-to-Device (D2D), Resource allocation

R ésum é :

Le probl ème de coloration de graphe est un probl ème NP-complet particuli èrement étudi é, qui permet de mod éliser de probl èmes dans des domaines vari és. Dans cette th èse, de nouveaux algorithmes exacts bas és sur une étude de la structure du graphe sont propos és. Ce travail s'appuie sur l'algorithme Total solutions Exact graph Coloring (TexaCol) qui construit toutes les solutions en exploitant l'ensemble des cliques d'un graphe. Deux algorithmes exacts, Partial best solutions Exact graph Coloring (PexaCol) et All best solutions Exact graph Coloring (AexaCol), sont pr ésent és ici pour construire certaines solutions optimales ou toutes les meilleures solutions. Ces deux algorithmes utilisent la m éthode de backtracking, dans laquelle ils ne choisissent que les sous-ensembles de meilleurs solutions pour continuer la coloration. L'analyse de r ésultat montre que PexaCol et AexaCol sont capables de traiter des graphes plus grands que TexaCol. Mais surtout, AexaCol trouve toutes les meilleures solutions significativement plus vite que TexaCol ainsi que le solveur Gurobi, qui sont utilis és comme r éf érence. La t él éphonie mobile est un domaine en plein essor qui peut s'appuyer sur une mod élisation à base de graphes. Actuellement, les techniques de type Device-to-Device (D2D) prennent une place importante dans les r éseaux mobiles. L'allocation de ressource constitue l'un des principaux probl èmes en mati ère de performance. Pour assigner efficacement une ressource radio à une paire D2D dans le syst ème Long-Term Evolution (LTE), un sch éma syst ématique d'allocation de ressources est propos é dans cette th èse. Il est bas é sur une clusturisation des liens D2D, et permet de prendre en compte à la fois l'allocation inter-cluster et intra-cluster des ressources. En d éterminant les zones d'interf érence, le probl ème d'allocation des ressources inter-cluster est formul é comme un probl ème de coloration de graphe dynamique. Un algorithme de coloration de graphe dynamique est ainsi propos é, bas é sur PexaCol. Cet algorithme peut assigner les ressources radio aux clusters qui sont g én ér és ou supprim és dynamiquement. L'analyse num érique montre que cet algorithme assure une bonne performance en termes d'utilisation des ressources, de temps d'ex écution et d'adaptabilit é. Concernant le probl ème d'allocation de ressources inter-cluster, une m éthode fond ée sur la topologie est propos ée, int égrant naturellement l'allocation de puissance et l'allocation de Resource Block (RB). Pour simplifier ce probl ème d'allocation de ressources, la meilleure topologie est choisie à chaque étape, celle qui permet d'obtenir le meilleur d ébit en utilisant le moins de RBs. A partir de ce proc éd é, quatre algorithmes d'optimisation sont propos és: l'algorithme glouton statique, PexaCol statique, PexaCol dynamique et PexaCol dynamique approximatif. L'analyse des r ésultats montre que pour les petits clusters, les versions statiques et dynamiques de PexaCol permettent d'obtenir un index d'optimisation maximal en choisissant la meilleure topologie locale pour chaque noeud. A l'oppos é, les algorithmes "glouton statique" et "PexaCol dynamique approximatif" permettent d'obtenir une solution sous-optimale pour l'optimisation locale avec une complexit é moindre. Pour les grands clusters, avec certaine s équence de la coloration, le PexaCol dynamique approximatif est mieux que l'algorithme glouton statique pour l'index d'optimisation pendant un temps d'ex écution acceptable.

Mots-cl és :

Coloration de graphes, Long-Term Evolution (LTE), Device-to-Device (D2D), Allocation des ressources