Theoretical research on graph coloring: Application to resource allocation in device-to-device 4G radio system (LTE) Jianding Guo To cite this version: Jianding Guo. Theoretical research on graph coloring: Application to resource allocation in device- to-device 4G radio system (LTE). Networking and Internet Architecture [cs.NI]. Université Bourgogne Franche-Comté, 2018. English. ￿NNT: 2018UBFCA007￿. ￿tel-01867956￿ HAL Id: tel-01867956 https://theses.hal.science/tel-01867956 Submitted on 4 Sep 2018 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. (cid:2)(cid:7)(cid:12)(cid:10)(cid:6)(cid:0)(cid:5)(cid:6)(cid:0)(cid:1)(cid:8)(cid:4)(cid:11)(cid:8)(cid:9)(cid:3)(cid:11) école doctorale sciences pour l’ingénieur et microtechniques UNIVERSITÉ DE TECHNOLOGIE BELFORT-MONTBÉLIARD Theoretical research on graph coloring - Application to resource allocation in device-to-device 4G radio system (LTE) (cid:0) JIANDING GUO (cid:2)(cid:7)(cid:12)(cid:10)(cid:6)(cid:0)(cid:5)(cid:6)(cid:0)(cid:1)(cid:8)(cid:4)(cid:11)(cid:8)(cid:9)(cid:3)(cid:11) école doctorale sciences pour l’ingénieur et microtechniques UNIVERSITÉ DE TECHNOLOGIE BELFORT-MONTBÉLIARD THE`SE pre´sente´e par JIANDING GUO pour obtenir le Grade de Docteur de l’Universite´ de Technologie de Belfort-Montbe´liard Spe´cialite´ : Informatique Theoretical research on graph coloring - Application to resource allocation in device-to-device 4G radio system (LTE) Unite´ deRecherche: Franche-Comte´ ElectroniqueMe´caniqueThermiqueetOptique-SciencesetTechnologies FEMTO-STInstitute(CNRSUMR6174),DISC/OMNI Soutenue publiquement le 6 juin 2018 devant le Jury compose´ de : JIN-KAO HAO Rapporteur Professeur a` l’Universite´ d’Angers ABDEL LISSER Rapporteur Professeur a` l’Universite´ Paris Sud- Orsay DAVID COUDERT Examinateur Directeur de recherche INRIA ALEXANDRE CAMINADA Directeur de the`se Professeur a` l’UBFC, FEMTO-ST LAURENT MOALIC Codirecteur de the`se Maˆıtre de confe´rences a` l’UHA JEAN-NOE¨L MARTIN Codirecteur de the`se Docteur, Enseignant e´me´rite a` l’UTBM Acknowledgements I would like to thank the China Scholarship Council (CSC) for the financial support for my PhD study in France. MysinceregratitudeisexpressedtomyadvisorProfessorAlexandreCaminada,whois so open-minded, experienced and easy-going. During my PhD study, he has provided me a very good research platform and has given me great freedom to do my research. Meanwhile, I am deeply grateful to my co-supervisor, Laurent Moalic, who gave me plenty of constructive suggestions and also helped me do the implementations. Besides, special thanks to another co-supervisor Jean-Noe¨l Martin, whose previous work is the foundation for my PhD work. Itisanhonorformetoshowmygratitudetothereviewersofthemanuscript,Professor Abdel Lisser, Professor Jin-Kao Hao and Research Director David Coudert. Their comments are so valuable and so essential for the quality of my thesis. ThankstoallmycolleaguesinthelabFEMTO-STandtoallmyfriends,whohavebeen constantly giving me the courage and support. Last but not the least, I would like to thank my family for supporting me spiritually throughout all these years. Although we are far away from each other, it is their deep love that motivates me to go ahead. iii Contents Acknowledgements iii Contents v List of Figures ix List of Tables xi 1 Introduction 1 1.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Objectives and contributions. . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Graph Coloring Problem 7 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Definitions of graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Definitions for graph coloring problem . . . . . . . . . . . . . . . . . . . . 9 2.4 Classification of graph coloring . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 Graph coloring algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5.1 Exact algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5.2 Heuristic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Graph coloring applications . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 Texacol 15 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 v Contents vi 3.6 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4 Improvement of TexaCol 31 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 PexaCol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.1 General idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.2 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.3 Example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3 AexaCol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.3.1 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3.2 Example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4.1 Comparison with Gurobi . . . . . . . . . . . . . . . . . . . . . . . . 40 4.4.2 Comparison between TexaCol, AexaCol and PexaCol . . . . . . . 40 4.4.3 Statistical analysis of node coloring sequence impact . . . . . . . 41 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5 Resource Allocation Problem in LTE System 49 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2 LTE system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.2.1 LTE network architecture . . . . . . . . . . . . . . . . . . . . . . . 52 5.2.2 LTE resource . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.3 D2D in LTE network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3.1 System architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3.2 Clustering mechanism . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.4 D2D resource allocation problem . . . . . . . . . . . . . . . . . . . . . . . 57 5.4.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.4.2 Cluster-based D2D resource allocation scheme . . . . . . . . . . . 60 5.5 Cluster-based D2D resource allocation algorithm . . . . . . . . . . . . . . 60 5.5.1 D2D dynamic cluster resource allocation algorithm . . . . . . . . . 60 5.5.1.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . 60 5.5.1.2 Algorithm description . . . . . . . . . . . . . . . . . . . . 63 5.5.1.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.5.1.4 Result analysis . . . . . . . . . . . . . . . . . . . . . . . . 67 5.5.2 D2D intra-cluster resource allocation algorithm . . . . . . . . . . . 72 5.5.2.1 Intra-cluster resource allocation problem . . . . . . . . . 72 5.5.2.2 Topology-based resource allocation mechanism . . . . . 75 5.5.2.3 Intra-cluster resource allocation strategies . . . . . . . . 78 5.5.2.4 Dynamic local optimization algorithm (DLOA) . . . . . . . 81 5.5.2.5 Running example of DLOA . . . . . . . . . . . . . . . . . 91 5.5.2.6 Result analysis . . . . . . . . . . . . . . . . . . . . . . . . 96 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101 6 Conclusions and Future Work 103 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104 Contents vii 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .106 A Experimental Results 109 B Acronyms 113 C Publications 115 Bibliography 117