# NOMA-Based Rate Optimization for Multi-UAV-Assisted D2D Communication Networks
## 4 Problem Solution
### Subchannel Assignment Based on Dynamic Hypergraph Coloring
#### 4.1.2 Dynamic Hypergraph Coloring  
Hypergraph coloring is an NP-hard problem, and traditional heuristic algorithms have high time complexity. In order to solve the hypergraph coloring problem, inspired by refs. [29; 30], this study firstly transforms hypergraphs into directed graphs to achieve efficient dynamic coloring, as shown in Definition 1. Specifically, vertex-based \"hyperdegree\" (mdeg) and unique ID (id) properties are adopted, where mdeg(w) is defined as the number of hyperedges connected to vertex \(w\) to measure the connection strength of vertices in the hypergraph, and id(w) is the unique vertex ID in the hypergraph \(H_{g}(t)\). Definition 1: For a dynamic hypergraph \(H_{g}(t)\) and two vertices \(v_{i}(t)\) and \(v_{j}(t)\), we define \(v_{i}(t)\lhd v_{j}(t)\), i.e., satisfying (1) \(mdeg(v_{i})\geq mdeg(v_{j})\); (2) \(mdeg(v_{i})=mdeg(v_{j})\), id(\
u_{i})\lhd v_{j}\). In previous studies, researchers used an algorithm based on greedy hypergraph coloring [28] for optimizing subchannel allocation to users in cellular networks. However, this method requires recoloring all vertices each time the hypergraph structure changes, resulting in high computational overhead and insufficient stability. To solve this problem, this study proposes a dynamic hypergraph coloring algorithm, which combines Definitions 2 and 3 to improve the efficiency and robustness of subchannel allocation by dynamically adjusting the coloring rules to effectively respond to dynamic changes in the hypergraph structure. Definition 2 (hypergraph-based oriented coloring graph (OGC) [30]): For a dynamic hypergraph \(H_{g}(t)=\big{(}V_{g}(t),E_{g}(t)\big{)}\), its oriented coloring graph \(H_{o}(t)=\big{(}V^{*}(t),E^{*}(t)\big{)}\) is a directed acyclic graph. In this graph, for any two vertices \(v_{i}(t)\) and \(v_{j}(t)\), a directed edge pointing from \(v_{i}(t)\) and \(v_{j}(t)\), denoted \(\big{<}v_{i}(t),v_{j}(t)\big{>}\), is drawn in if \(v_{i}(t)\lhd v_{j}(t)\) is satisfied. Definition 3 (OGC coloring [29]): For a directed acyclic graph \(H_{o}(t)=(V^{*}(t),E^{*}(t))\), the coloring function \(f_{o}\) requires that for any directed edge \(\big{<}v_{i}(t),v_{j}(t)\big{>}\), the associated two vertices \(v_{i}(t)\) and \(v_{j}(t)\) must have different colors. Examples of dynamic hypergraphs and correlation matrices as well as dynamic graph coloring for different time slots are given in Figure 2. At time slot \(t\), we have three cellular users and three D2D clusters denoted as \(\{C_{1},C_{2},C_{3}\}\) and \(\{D_{1},D_{2},D_{3}\}\). Simple edges \(\{e_{2},e_{3},e_{4}\}\) are used between the cellular users to ensure that they transmit on different subchannels, and simple edge \(e_{5}\) connects cellular user \(C_{1}\) and D2D cluster \(D_{3}\). In addition, cellular user \(C_{1}\) and D2D cluster \(D_{1}\) form a multilateral with \(D_{2}\). Due to the motion of the UAV, four new D2D clusters and two new polygons are added at the time slot \(t+1\), and their corresponding association matrices are shown in the right part of Figure 2. Finally the results of the steps of dynamic hypergraph coloring are shown according to Definitions 1-3, where first the hypergraph at the time slot is converted into a directed graph according to Definition 1, e.g., the hyperedge \(e_{5}\) is a directed edge from \(C_{1}\) to \(D_{3}\) because of \(mdeg(C_{1})\geq mdeg(D_{3})\), and so on. After the directed graph conversion is completed, the graph is colored according to Definitions 2 and 3. Based on the above analysis, the subchannel assignment algorithm based on dynamic hypergraph coloring is shown in Algorithm 1.