# NOMA Clustering for Improved Multicast IoT Schemes
## 3 System Model and Problem Formulation
### Formation of Coalitions  
In the remainder, and without loss of generality, CHs are denoted using indices from \(1\) to \(M\), in the order of their respective channel gains to the BS. \(\text{C}_{i}\) is the coalition of UEs around \(\text{CH}_{i}\), and \(\text{C}\) denotes the set of all coalition heads. At the end of phase \(1\), the BS shares the list of the selected coalition heads with all the remaining \(N-M\) multicast users. Each UE evaluates the channel quality of all D2D links to all announced CHs, and joins the coalition by the CH with which it has the best link. When there is no reachable coalition head, a UE tries to connect to the best neighbor among its reachable D2D neighbors that are already members of a coalition, and joins the same coalition as that neighbor. We consider that a D2D link exists between \(\text{UE}_{i}\) and \(\text{UE}_{j}\) if \(G_{ij}\geq G_{\text{TH}}\), where \(G_{\text{TH}}\) is a predefined threshold that will be discussed later. The number of tentative connections is set by the BS based on the cell parameters, and the maximum acceptable end-to-end transmission delay. At the end of phase \(2\), the BS summarizes the state of all UEs, updates the established list of coalitions, and identifies the list of lone users. The latter will be served directly by the BS during the transmission phase. We define \(\mathcal{L}\) as the set of lone users with \(l\) as its cardinal. Algorithm 1 summarizes the steps of the coalitions formation. ```
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
99:
10:
99:
11:
12:
13:
14:
15:
16:
17:
18:
19:
19:
19:
12:
14:
15:
16:
17:
18:
19:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
29:
2



### Construction of D2D Transmission Trees

To exclude all the considerations that are out of the scope of this paper, we consider that within the coalitions, all users are involved in a trust-based cooperative mode. To alleviate the notations, we drop the index referring to the coalition and its coalition head in this subsection, i.e., \(\mathcal{C}\) denotes the coalition around a given CH. The objective at this stage is to establish a path reaching every UE in \(\mathcal{C}\), and connecting it to the BS via CH. Specifically, we construct a _transmission tree_ over the D2D connections by choosing, for each UE, the best route that will maximize its transmission rate. We describe the transmission construction steps as follows and in Algorithm 2:

* We sort UEs in \(\mathcal{C}\) in a descending order, with regards to their channel gains with the CH. We index them as: \(\text{UE}_{1},\text{UE}_{2},\dots\). For notational reasons, we refer to the CH as \(\text{UE}_{0}\). * We define \(y_{i}\) as the number of connected D2D users to \(\text{UE}_{i}\) (\(0\leqslant i\)). \(x_{i}\) is the maximum number of users that the \(\text{UE}_{i}\) can serve simultaneously. * Each user of the coalition connects to its most preferred D2D user having a lower index:
* First, \(\text{UE}_{1}\) connects to the CH. * For \(j>1\), \(\text{UE}_{i}\) connects to \(\text{UE}_{s}\) from \(\{\text{UE}_{0},\text{UE}_{1},\dots\text{UE}_{j-1}\}\), such as \(\text{UE}_{s}\) is having the best D2D link with \(\text{UE}_{j}\) and is not saturated (i.e., \(y_{s}<x_{s}\)). ```
1. Users within coalition \(\mathcal{C}\). 2. Number of D2D users that every user can serve simultaneously. Initialization:
1. Sort users in a descending order, with regards to their channel gains with the CH. Construction of the transmission tree:
1. \(\text{UE}_{1}\) connects to CH. 2.