This paper studies the problem of stable user association and channel assignment in downlink multi-cell non-orthogonal multiple-access (NOMA) networks. To be specific, the goal is to assign network users to the channels at each base station, while accounting for inter-user interference and maintaining quality of service (QoS) per user. To that end, a low-complexity iterative solution procedure is devised to obtain the optimal power allocation for proportional fairness signal-to-interference-plus-noise ratio (SINR)-based maximization, which is then utilized to determine the preferences of network users over the channels available at each base station and the preferences of base stations over the network users. In turn, a many-to-one matching-theoretic model based on the student-project allocation problem is applied. Particularly, two polynomial-time complexity stable matching algorithms are proposed to associate users with base stations and perform channel assignment, such that no user or base station would deviate and change its association or channel assignment unilaterally. To validate the efficacy of the proposed solution procedure and stable matching algorithms, extensive simulation results are presented to compare them to a centralized joint user association, channel assignment, and power allocation (C-J-UA-CA-PA) scheme. It is demonstrated that the proposed algorithms efficiently associate users with base stations and assign them to channels as well as efficiently yielding comparable SINR per user to the C-J-UA-CA-PA scheme, while maximizing proportional fairness and satisfying QoS constraints.
Notes
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Abbreviations
BS
Base station
BS-SM
Base station-oriented stable matching
C-J-UA-CA-PA
Centralized joint user association, channel assignment, and power allocation
CPA
Conventional power allocation
CoMP
Coordinated multipoint
CSI
Channel state information
CSIT
Channel state information at transmitter
D2D
Device-to-device
EPA
Equal power allocation
LF
Linear-fractional
mmWave
Millimeter-wave
NOMA
Non-orthogonal multiple access
OFDMA
Orthogonal frequency-division multiple access
OMA
Orthogonal multiple access
PR-SINR-MAX
Proportional fairness SINR-based maximization
SIC
Successive interference cancelation
SINR
Signal-to-interference-plus-noise ratio
SP-PF-SINR-MAX
Solution procedure for proportional fairness SINR maximization
SPA
Student-project allocation
SPM
Sum-power minimization
SRM
Sum-rate maximization
U-SM
User-oriented stable matching
1 Introduction
Non-orthogonal multiple access (NOMA) has recently attracted so much attention to meet the ever-increasing demand for high spectral efficiency, improved fairness, massive connectivity, low transmission latency, and high throughput in future 5G cellular networks [1]. Specifically, the principle of NOMA is based on multiplexing users in the power domain over resource blocks by enforcing power imbalance between the transmitted user signals, which allows successive interference cancelation (SIC) to effectively eliminate inter-user interference, and yielding considerable performance gains over conventional orthogonal multiple access (OMA) schemes [2]. To date, the majority of the published literature on resource allocation for NOMA systems has considered on single-cell networks. For example, the problem of sum-throughput maximizing power allocation based on α−fairness in single-cell downlink NOMA networks is studied in [3]. Particularly, the cases of statistical and perfect channel state information at the transmitter (CSIT) are considered. For the former case, fixed target data rates are pre-defined for all users, while for the latter case, users’ rates are adapted according to the instantaneous CSI. In [4], the authors propose user-pairing schemes for capacity maximization in single-cell downlink NOMA networks. To be specific, two user-pairing schemes have been proposed so as to provide capacity gains to almost all users by grouping them in pairs. Additionally, the exact sum capacity of a two-user pair has been analytically derived, while taking into account perfect and imperfect SIC. A dynamic power allocation scheme—subject to quality-of-service requirements—for downlink and uplink single-cell NOMA networks with two users has been considered in [5]. Moreover, the exact expressions for the outage probability and average rate resulting from the proposed scheme are obtained. The problem of optimal power allocation with given channel assignment under different performance criteria for single-cell downlink NOMA networks is studied in [6]. Furthermore, the authors proposed a low-complexity scheme for joint channel assignment and power allocation via a dynamic/iterative matching algorithm. Although single-cell NOMA networks have received significant attention in the past few years, much less attention has been given to multi-cell NOMA networks. Therefore, it is of paramount importance to study NOMA in the more realistic multi-cell scenario, which is much more challenging due to the complex interplay between multiple cells [7].
Recently, a few research works have focused on resource allocation in multi-cell NOMA networks. For example, in [8], distributed power control for downlink multi-cell NOMA networks is studied. Particularly, the authors study the problem of total transmit power minimization of all base stations, subject to minimum data rate requirements of network users. Moreover, a distributed algorithm is devised, which has been shown to converge to the optimal solution, if one exists. The problems of sum-power minimization (SPM) and sum-rate maximization (SRM) for multi-cell NOMA networks are studied in [9]. To be specific, the SPM is transformed into a linear programming problem, and closed-form solutions to the power allocation of each user are determined. Contrarily, the SRM problem is solved by decomposing it into a power allocation problem for users in a single cell, and a power control problem over multiple cells. After obtaining the optimal sum rate in a single cell, a distributed algorithm is devised to solve the original sum-rate maximization. In [10], the authors consider the problem of jointly optimizing power allocation, user-pair selection, and time-frequency resource allocation in multi-cell NOMA networks. In particular, an efficient algorithm for obtaining the equilibrium for resource allocation—while taking into account inter-cell interference—is proposed, which has also been proven to be the global optimum resource allocation solution. In [11], the authors outline a general framework for coordinated multipoint (CoMP) transmission in downlink multi-cell NOMA systems with distributed power allocation at each cell. Specifically, the applicability and necessary conditions for different CoMP schemes and network scenarios are investigated, and simulation results are presented to quantify the spectral efficiency gains of CoMP-NOMA over CoMP-OMA. Efficient power allocation for sum network capacity maximization in downlink multi-cell multi-user NOMA networks is considered in [12]. Particularly, a local optimal solution iterative scheme is proposed, which has been shown to outperform non-optimal NOMA and OMA schemes. In [13], the performance of NOMA in multi-cell downlink millimeter-wave (mmWave) networks is investigated. To be specific, closed-form outage probability expressions are derived, where it has been demonstrated that NOMA can outperform OMA in multi-cell mmWave networks.
Advertisement
This paper studies the problem of stable user association and channel assignment in downlink multi-cell NOMA networks. To be specific, the goal is to assign network users to the channels available at each base station, while accounting for inter-user interference, and maintaining quality of service (QoS) per user. To that end, a low-complexity iterative solution procedure—that can be executed locally at each base station—is devised to obtain the optimal power allocation for proportional fairness signal-to-interference-plus noise ratio (SINR)-based maximization, which is utilized to determine the preferences of network users over the channels available at each base station, and the preferences of base stations over the network users. In turn, a many-to-one matching-theoretic model based on the student-project allocation (SPA) problem is applied [14, 15]. Particularly, two polynomial-time complexity algorithms are proposed, namely the user-oriented stable matching (U-SM) and the base station-oriented stable matching (BS-SM). The proposed SPA-based stable matching algorithms incorporate constraints on the number of users per channel and the number of users to be associated with each base station. Furthermore, in the U-SM algorithm, a user-optimal stable matching solution is achieved, while in the BS-SM algorithm, a base station-optimal stable matching solution is obtained. More importantly, the U-SM and BS-SM algorithms yield user association and channel assignment stable matchings that are simultaneously best response for all users and all base stations, respectively, such that no user or base station would deviate and change its association or channel assignment unilaterally. Additionally, a centralized joint user association, channel assignment, and power allocation (C-J-UA-CA-PA) optimization problem is formulated and shown to be computationally expensive. To validate the efficacy of the proposed solution procedure and stable matching algorithms, extensive simulation results are presented to compare them to the C-J-UA-CA-PA scheme. It is demonstrated that the proposed algorithms efficiently associate users with base stations and assign them to channels as well as yielding comparable SINR per user to the C-J-UA-CA-PA scheme, while maximizing proportional fairness and satisfying QoS constraints.
Few recent research works have applied matching theory to NOMA networks. For example, in [16], user pairing in a single-cell cognitive radio-inspired NOMA network is studied, where the base station allocates power to paired users within a cluster. In particular, a user with poor channel conditions is paired with a user with good channel conditions, while satisfying their rate requirements. To that end, a two-sided one-to-one distributed matching algorithm is developed, which is shown to yield performance that approaches that of centralized user pairing and power allocation. The authors in [17] investigate channel assignment, power allocation, and scheduling for single-cell downlink NOMA networks. To be specific, the problem of joint channel assignment and sum-rate maximizing power allocation with user fairness is considered. Moreover, a many-to-many user-channel matching algorithm is proposed, and an iterative solution for joint channel assignment and power allocation based on swap matching is devised. In [18], the authors consider the problem of sum-rate maximization for device-to-device (D2D) communication in uplink single-cell NOMA networks by optimizing channel and power allocation. In particular, a two-sided many-to-one matching algorithm is proposed to allow D2D groups to reuse the same channel occupied by a cellular user. Power allocation is also studied, where swap matching is applied to jointly allocate channel and power to the D2D groups. In [19], the problem of joint spectrum allocation and power control in single macro-cell NOMA-enhanced heterogenous networks is considered. In particular, several many-to-one matching-theoretic algorithms with a swap operation are proposed while incorporating users’ fairness in sum-rate maximizing power allocation. Clearly, all the aforementioned works focus on single-cell NOMA networks.
To the best of our knowledge, no prior work has applied the SPA matching problem for user association and channel assignment with proportional fairness SINR-based power allocation in downlink multi-cell NOMA networks. In turn, the main contributions of this work are summarized as follows:
Proposed a low-complexity iterative solution procedure for determining the proportional fairness SINR-based maximizing power allocation for different user sets over the channels available at each base station.
Modeled the user association and channel assignment problem in downlink multi-cell NOMA networks as a SPA matching problem.
Devised two polynomial-time complexity stable matching algorithms based on the SPA matching problem, which associate network users with base stations and channels, such that user optimal and base station-optimal stable matching solutions are obtained.
Compared the proposed algorithms to the C-J-UA-CA-PA scheme and demonstrated that the proposed algorithms yield comparable SINR per user as well as efficiently assigning channels to cell-edge users, while maximizing proportional fairness and satisfying QoS constraints.
The proposed algorithmic designs in this work aim at filling the gap for effective resource allocation solutions in multi-cell NOMA-based 5G cellular networks. In particular, the proposed solution procedure can be executed locally at each base station to efficiently determine the proportional fairness SINR-based maximizing power allocation of cellular users over each channel and within each base station, and with minimal computational complexity, while taking into account inter-user interference, QoS requirements, and SIC decoding constraints. In fact, the proposed solution procedure can incorporate other power allocation strategies and performance criteria (e.g., sum rate, energy efficiency, etc.) to establish the preferences of users over channels and base stations over users. Furthermore, the proposed stable matching algorithms can efficiently be executed among the base stations and without the need for a centralized controller. In summary, by optimizing the SINR of the network users via proportional fairness-based power allocation, and efficiently associating users with base stations and assigning channels to them over multiple cells, this work fulfills some of the requirements of NOMA-based 5G cellular networks.
Advertisement
The rest of this paper is organized as follows. Section 2 presents the network model, while Section 3 presents the centralized joint user association, channel assignment, and power allocation problem formulation. Section 4 discusses the proposed solution procedure for proportional fairness SINR-based maximizing power allocation. In Section 5, the SPA-based stable matching algorithms are devised, whereas in Section 6, the simulation results are presented. Finally, Section 7 draws the conclusions.
2 Network model
Consider a downlink multi-cell NOMA network with a set of Q base stations (BSs), denoted \(\mathcal {B} = \left \{\mathrm {BS_{1}, {BS}_{2}, \ldots, {BS}}_{Q}\right \}\), a set of N users \(\mathcal {U} = \left \{U_{1}, U_{2}, \ldots, U_{N} \right \}\), and a set of K channels \(\mathcal {C} = \left \{C_{1}, C_{2}, \ldots, C_{K} \right \}\). Particularly, the network bandwidth is divided into K non-overlapping equal bandwidth channels, such that each base station \({\text {BS}}_{q} \in \mathcal {B}\) is allocated a non-empty set of channels \(\mathcal {C}_{q} \subset \mathcal {C}\), where \(\mathcal {C}_{1}, \mathcal {C}_{2}, \ldots, \mathcal {C}_{q}\) partition \(\mathcal {C}\). In other words, \(\mathcal {C}_{q} \cap \mathcal {C}_{w} = \phi \) for w≠q, and \(\bigcup ^{Q}_{q=1} \mathcal {C}_{q} = \mathcal {C}\). Furthermore, let \(\mathcal {U}_{q} \subset \mathcal {U}\) be the subset of network users within the coverage area of each base station \({\text {BS}}_{q} \in \mathcal {B}\) (see Fig. 1). Also, let ζq, k be the maximum number of users that can be assigned to channel \(C_{q,k} \in \mathcal {C}_{q}\). That is, each channel \(C_{q,k} \in \mathcal {C}_{q}\) can be occupied by at most ζq, k users, \(\forall {BS}_{q} \in \mathcal {B}\)1. Moreover, note that some network users may fall within the overlapping region of two or more cells. Therefore, the maximum number of users that can be associated with each base station BSq is set to ξq (i.e., a quota per base station). Additionally, each user may be associated with at most one base station and assigned to one channel. Our network model mimics that of a multi-cell orthogonal frequency-division multiple access (OFDMA)-NOMA network, where each channel is allocated to only one user, as per conventional OFDMA networks; while multiple users within a cell can share a channel via NOMA2.
Fig. 1
A downlink multi-cell NOMA network with Q=2 base stations and N=8 users
×
In downlink NOMA networks, each base station BSq sends data (over each assigned channel \(C_{q,k} \in \mathcal {C}_{q}\)) to its users simultaneously via power-domain superposition coding. The instantaneous channel between each BS and the network users within its coverage area follows narrowband Rayleigh fading with zero-mean N0-variance additive white Gaussian noise3. Particularly, \(h^{k}_{q,n} \sim \mathcal {C}\mathcal {N}\left (0, \sigma ^{2}_{q,n} \right)\) is the channel coefficient between BSq and user \(U_{n} \in \mathcal {U}_{q}\) over channel \(C_{q,k} \in \mathcal {C}_{q}\), and \(\sigma ^{2}_{q,n} = d^{-\nu }_{q,n}\) is the channel variance, with ν and dq, n being the path loss exponent and distance, respectively. Moreover, the instantaneous channel gain is defined as \(g^{k}_{q,n} \triangleq \left |h^{k}_{q,n}\right |^{2}\). Thus, without loss of generality, let the channel gains between base station BSq and the users within its vicinity over each channel Cq, k be ordered as \(g^{k}_{q,1} \leq g^{k}_{q,2} \leq \cdots \leq g^{k}_{q,|\mathcal {U}_{q}|}\). In turn, the power allocation coefficients are ordered as \(a^{k}_{q,1} \geq a^{k}_{q,2} \geq \cdots \geq a^{k}_{q,|\mathcal {U}_{q}|}\). Additionally, the total transmit power at each base station BSq is set as \(P_{\text {BS}}, \forall {\text {BS}}_{q} \in \mathcal {B}\). More importantly, let \(P_{q,k} = P_{BS}/|\mathcal {C}_{q}| \triangleq P\) be the transmit power per allocated channel, \(\forall C_{q,k} \in \mathcal {C}_{q}\) and \(\forall {\text {BS}}_{q} \in \mathcal {B}\), where |·| denotes the cardinality of the parameter set.
In this work, perfect SIC is assumed4, and thus, the signal-to-interference-plus-noise ratio (SINR) of user \(U_{n} \in \mathcal {U}_{q}\) over channel \(C_{q,k} \in \mathcal {C}_{q}\) is written as
with \(\rho \triangleq P/N_{0}, \bar {a}^{k}_{q,n} \triangleq \sum ^{|\mathcal {U}_{q}|}_{m = n+1} a^{k}_{q,m}\), and \(\bar {a}^{k}_{q,|\mathcal {U}_{q}|} = 0\).
Remark 1
The SINR function \(\gamma ^{k}_{q,n}, \forall n \neq |\mathcal {U}_{q}|\), is linear-fractional (LF) function, with \(\rho g^{k}_{q,n} a^{k}_{q,n}\) and \(\rho g^{k}_{q,n}\bar {a}^{k}_{q,n} + 1 > 0\) being linear functions in \(a^{k}_{q,n}\) and \(\bar {a}^{k}_{q,n}\), respectively [21]. However, the SNR function \(\gamma ^{k}_{q,|\mathcal {U}_{q}|}\) is a linear function in \(a^{k}_{q,|\mathcal {U}_{q}|}\).
3 Centralized joint user association, channel assignment, and power allocation
In this work, the aim is to jointly associate users with base stations and perform channel assignment, along with proportional fairness SINR-based maximizing power allocation. Additionally, each user must satisfy a target minimum SINR \(\gamma _{T_{n}}, \forall U_{n} \in \mathcal {U}_{q}\), and \(\forall {BS}_{q} \in \mathcal {B}\) (i.e., QoS constraints). To this aim, define the binary decision variable \(\mathcal {I}^{k}_{q,n}\) as
Constraint (3a) ensures that if a user Un is paired to a channel Cq, k, then it must satisfy the target minimum SINR \(\gamma _{T_{n}}\), while constraint (3b) ensures that the total number of users paired to channels in any base station BSq must not exceed ξq. Moreover, constraint (3c) ensures that the number of users paired to each channel \(C_{q,k} \in \mathcal {C}_{q}\) is at most ζq, k. Constraint (3d) ensures that a user is associated with at most one base station, while constraint (3e) ensures that the sum of power allocation coefficients of the assigned users over any channel does not exceed one. Constraint (3f) ensures that the decoding order of the SIC is preserved. Constraint (3g) defines the range of values each power allocation coefficients can take. Particularly, if \(\mathcal {I}^{k}_{q,n} = 1\), then \(0 \leq a^{k}_{q,n} \leq 1\); otherwise, \(a^{k}_{q,n} = 0\). Finally, the last constraint defines the range of values the binary decision variables can take.
Remark 2
The C-J-UA-CA-PA problem comprises an upper-bound total of \(N \cdot \sum _{BS_{q} \in \mathcal {B}} |\mathcal {C}_{q}|\) continuous decision variables (i.e., \(a^{k}_{q,n}\)) and a similar number of binary decision variables (i.e., \(\mathcal {I}^{k}_{q,n}\)). In addition, it can be verified that there is an upper-bound total of \(N + Q + 2\left (\sum _{BS_{q} \in \mathcal {B}}|\mathcal {C}_{q}| + \sum _{BS_{q} \in \mathcal {B}} |\mathcal {C}_{q}| \cdot |\mathcal {U}_{q}| \right) + \sum _{BS_{q} \in \mathcal {B}} |\mathcal {C}_{q}| \cdot \left (|\mathcal {U}_{q}| - 1\right)\) constraints.
Remark 3
Problem C-J-UA-CA-PA is a classified as a mixed-integer nonlinear programming problem (MINLP), which is NP-hard (i.e., extremely computationally expensive [22,23]). Thus, it can only be solved via a global optimization package.
Based on Remark 3, problem C-J-UA-CA-PA can be decomposed in two sub-problems: (1) proportional fairness SINR-based maximizing power allocation and (2) stable matching-theoretic user association and channel assignment. Particularly, the aim is to optimally solve the SINR-maximizing power allocation per base station and over each channel, while accounting for inter-user interference and QoS constraints. This will be achieved via a low-complexity iterative solution procedure, which also determines the preferences of users over channels, and the preferences of base stations over users. After that, base-station association and channel assignment is performed via the stable matching algorithms.
4 Proportional fairness SINR-based maximizing power allocation
This section focuses on proportional fairness SINR-based maximizing (PR-SINR-MAX) power allocation, subject to target minimum SINR \(\gamma _{T_{n}}\) per user \(U_{n} \in \mathcal {U}_{q}\). Specifically, the objective function of base station BSq over channel \(C_{q,k} \in \mathcal {C}_{q}\) be given by
where \(\mathbf {a}^{k}_{q} = \left [a^{k}_{q,1}, a^{k}_{q,2}, \ldots, a^{k}_{q,|\mathcal {U}_{q}|} \right ]\) is the power allocation vector, while \({\mathcal {I}}^{k}_{q} = \left [\mathcal {I}^{k}_{q,1}, \mathcal {I}^{k}_{q,1}, \ldots, \mathcal {I}^{k}_{q,|\mathcal {U}_{q}|}\right ]\) is the channel assignment vector. Since each channel \(C_{q,k} \in \mathcal {C}_{q}\) has a quota ζq, k, then \(\sum _{U_{n} \in \mathcal {U}_{q}} \mathcal {I}^{k}_{q,n} \leq \zeta _{q,k}\). The objective function in (5) stipulates that if user Un is assigned channel Cq, k (i.e., \(\mathcal {I}^{k}_{q,n} = 1\)), then its SINR function is maximized; otherwise, it is set to one. Therefore, the PR-SINR-MAX optimization problem can be formulated as
Constraint (6a) ensures that if a user is selected, then it must satisfy the target minimum SINR, while constraint (6b) ensures that the sum of power allocation coefficients of the selected users does not exceed one. Constraint (6c) ensures that the maximum number of users per channel \(C_{q,k} \in \mathcal {C}_{q}\) does not exceed ζq, k, while constraint (6d) maintains the SIC decoding order. Constraint (6e) ensures that if channel Cq, k is assigned to user Un (i.e., \(\mathcal {I}^{k}_{q,n} = 1\)), then the power allocation coefficient \(a^{k}_{q,n}\) must not exceed one; otherwise, \(a^{k}_{q,n} = 0\) (since \(\mathcal {I}^{k}_{q,n} = 0\)). The last constraint defines the range of values the binary decision variables take.
Remark 4
Problem PR-SINR-MAX is classified as a mixed-integer linear-fractional programming (MILFP) problem. More importantly, it is non-convex (and NP-hard [24]); and thus, it is still computationally expensive.
In turn, a simple solution procedure is devised to efficiently solve problem PR-SINR-MAX. To that end, let \({\Omega }_{q,k} = \left \{{\Omega }_{q,k,1}, \ldots, {\Omega }_{q,k,\zeta _{q,k}} \right \}\) be the set of all combinations of assigning uq users in \(\mathcal {U}_{q}\) (for 1≤uq≤ζq, k) over each channel \(C_{q,k} \in \mathcal {C}_{q}\), where \({\Omega }_{q,k,u_{q}} = \left \{{\omega }_{q,k,1}, {\omega }_{q,k,2}, \ldots, {\omega }_{q,k,\varpi _{u_{q}}} \right \}\), and
with \(\varpi _{u_{q}} = |{\Omega }_{q,k,u_{q}}|\). Each combination is defined as \({{\omega }_{q,k,\varsigma } = \left [\!\mathcal {J}^{k}_{q,\varsigma,1}, \mathcal {J}^{k}_{q,\varsigma,2}, \ldots, \mathcal {J}^{k}_{q,\varsigma,|\mathcal {U}_{q}|} \!\right ]}\), for \(\varsigma = 1,2,\ldots, \varpi _{u_{q}}\). Specifically, \(\mathcal {J}^{k}_{q,\varsigma,n}\) is defined as
For example, if \(|\mathcal {U}_{q}| = 3\) and ζq, k=2, then Ωq, k={Ωq, k,1,Ωq, k,2}, where Ωq, k,1 includes the combinations [1,0,0],[0,1,0], and [0,0,1], while Ωq, k,2 contains the combinations [1,1,0],[1,0,1], and [0,1,1]. In other words, in the first set of combinations Ωq, k,1, only one user is assumed to be assigned to channel Cq, k, while in Ωq, k,2, different combinations of two users are assigned to that channel.
Remark 5
The total number of all possible user combinations over each channel \(C_{q,k} \in \mathcal {C}_{q}, \forall {\text {BS}}_{q} \in \mathcal {B}\) is obtained as
For notational convenience, let \(\mathcal {U}_{q,k,\varsigma } \subseteq \mathcal {U}_{q}\) be the subset of users in \(\mathcal {U}_{q}\) with \(\mathcal {J}^{k}_{q,\varsigma,n} = 1\) in \({\omega }_{q,k,\varsigma } \in {\Omega }_{q,k,u_{q}}\phantom {\dot {i}\!}\). Thus, the SINR of each user \(U_{n} \in \mathcal {U}_{q,k,\varsigma }\) is expressed as
It can be seen that for each possible combination \(\phantom {\dot {i}\!}{\omega }_{q,k,\varsigma } \in {\Omega }_{q,k,u_{q}}\), each user \(U_{n} \in \mathcal {U}_{q,k,\varsigma }\) will have a different SINR value, which depends on the other users sharing the same channel in that combination.
Remark 6
The SINR function of each user is one with peer effects (also known as negative network externality), which is due to the fact that each user’s SINR \(\gamma ^{k}_{q,n,\varsigma }\) is influenced by the allocated power to all the other users utilizing the same channel.
Remark 7
For uq=1, only one user is assigned to each channel \(C_{q,k} \in \mathcal {C}_{q}\), in any combination ωq, k,ς in \({\Omega }_{q,k,1}, \forall \varsigma = 1,2,\ldots,|\mathcal {U}_{q}|\). Consequently, the power allocation coefficient for each user Un with \(\mathcal {J}^{k}_{q,\varsigma,n} = 1\) in ωq, k,ς is \(a^{k}_{q,n,\varsigma } = 1\), whereas \(\bar {a}^{k}_{q,n,\varsigma } = 0\), and hence, \(\gamma ^{k}_{q,n,\varsigma } = \rho g^{k}_{q,n,\varsigma }\).
Now, for each possible combination \(\phantom {\dot {i}\!}{\omega }_{q,k,\varsigma } \in {\Omega }_{q,k,u_{q}}\), for 2≤uq≤ζq, k, problem PR-SINR-MAX can be re-written as
which can be verified to be non-convex, although all the constraints are linear [25]. By utilizing the fact that the ln(·) function is concave and strictly monotonically increasing, then the objective function of problem PR-SINR-MAX (ωq, k,ς) can be re-expressed as
It is noteworthy that \(f\left (\mathbf {a}^{k}_{q,\varsigma } \right)\) and \(g\left (\mathbf {a}^{k}_{q,\varsigma } \right)\) are concave functions, which are also twice continuously differentiable in \(a^{k}_{q,n,\varsigma }\) and \(\bar {a}^{k}_{q,n,\varsigma }\), respectively. Hence, \(\ln \gamma ^{k}_{q,\varsigma }\left (\mathbf {a}^{k}_{q,\varsigma }, {\omega }_{q,k,\varsigma }\right)\) is a difference convex function [26,27]. As a result, problem PR-SINR-MAX (ωq, k,ς) can be reformulated as [28,29]
with μ being an auxiliary variable. It can be easily verified that the objective function and the first constraint are concave functions in \(a^{k}_{q,n,\varsigma }, \forall U_{n} \in \mathcal {U}_{q,k,\varsigma }\), whereas the remaining constraints are linear.
Remark 8
R-PR-SINR-MAX (ωq, k,ς) is a concave minimization problem [30] and thus is solved efficiently with minimal complexity via any standard convex optimization package [31].
Remark 9
The optimal solution of problem R-PR-SINR-MAX (ωq, k,ς) is also the optimal solution of the original problem PR-SINR-MAX (ωq, k,ς) [30].
The following solution procedure determines the resulting SINR per user Un for each channel Cq, k of each base station BSq. The goal is to iterate over all possible user combinations in Ωq, k. Specifically, the solution procedure starts by considering single-user combinations (i.e., when uq=1 and for each ωq, k,ς∈Ωq, k,1) over each channel \(C_{q,k} \in \mathcal {C}_{q}\) and determines whether the target minimum SINR \(\gamma _{T_{n}}\) is satisfied by calculating \(\gamma ^{k}_{q,n,\varsigma }, \forall U_{n} \in \mathcal {U}_{q,k,\varsigma }\). If \(\gamma ^{k}_{q,n,\varsigma } < \gamma _{T_{n}}\) for any \(\forall U_{n} \in \mathcal {U}_{q,k,\varsigma }\), then set \(\gamma ^{k}_{q,n,\varsigma } = 0\); otherwise, keep the value of \(\gamma ^{k}_{q,n,\varsigma }\) for later use to determine the preference lists. After that, the solution procedure considers user combinations of sizes 2≤uq≤ζq, k, and solves problem R-PR-SINR-MAX (ωq, k,ς) for each combination, such that the optimal SINR of each user in each combination over each channel is evaluated to determine whether the target minimum SINR is satisfied, as stated earlier. Upon completion of the solution procedure, each user \(U_{n} \in \mathcal {U}_{q}\) calculates
for each channel \(C_{q,k} \in \mathcal {C}_{q}\), which is considered as a weight of how valuable that channel is to that user. Contrarily, each base station \({\text {BS}}_{q} \in \mathcal {B}\) calculates
for each user \(U_{n} \in \mathcal {U}_{q}\), which is used as a weight for how valuable that user is to that base station.
The proposed solution procedure for proportional fairness SINR-based maximization (SP-PF-SINR-MAX) is outlined in Algorithm 1, which can be performed locally at each base station.
Remark 10
For the case when uq=1 (i.e., only combinations ωq, k,ς∈Ωq, k,1, for ς=1,2,…,ϖ1) in which only a single user is considered over each channel \(C_{q,k} \in \mathcal {C}_{q} \left (\text {i.e.}\ \mathcal {J}^{k}_{q,1,n} = 1\right)\), if a user \(U_{n} \in \mathcal {U}_{q,k,\varsigma }\) cannot satisfy the target minimum SINR \(\gamma _{T_{n}}\), then it cannot satisfy it when a greater number of users are considered (i.e., when 2≤uq≤ζq, k) over that channel (due to negative network externality). Hence, \(\chi ^{k}_{q,n} = 0\) for user \(U_{n} \in \mathcal {U}_{q}\) over channel \(C_{q,k} \in \mathcal {C}_{q}\).
Remark 11
The greater the value of \(\chi ^{k}_{q,n}\) is, the more preferred channel \(C_{q,k} \in \mathcal {C}_{q}\) is to user \(U_{n} \in \mathcal {U}_{q}\). In a similar manner, the greater the value of ψq, n is, the more preferred user \(U_{n} \in \mathcal {U}_{q}\) is to base station \({BS}_{q} \in \mathcal {B}\).
Remark 12
If for any user \(U_{n} \in \mathcal {U}_{q}\), the value of \(\chi ^{k}_{q,n} = 0\), then that channel is considered unacceptable to that user. In a similar manner, if, for a base station \({BS}_{q} \in \mathcal {B}, \psi _{q,n} = 0\), then user Un is deemed unacceptable.
Remark 13
At the outset, the proposed solution procedure may seem to be excessively complex. However, for each base station \({BS}_{q} \in \mathcal {B}\), there is a total of \(|\mathcal {C}_{q}| \cdot \Sigma \left (\mathcal {U}_{q}, \zeta _{q,k} \right)\) iterations, and a convex optimization problem is efficiently solved in only \(|\mathcal {C}_{q}| \cdot \Sigma \left (\mathcal {U}_{q}, \zeta _{q,k} \right) - |\mathcal {U}_{q}|\) iterations and thus is guaranteed to converge5.
It should be noted that in multi-cell NOMA networks, a small number of users are to be multiplexed into a channel, which is mainly to minimize inter-user interference, reduce SIC hardware complexity and error propagation, and leverage capacity gains [7], while satisfying the target minimum SINR constraint per user (i.e., ζq, k must be kept reasonably small, \(\forall C_{q,k} \in \mathcal {C}_{q}\)). Lastly, the proposed solution procedure eliminates the need for swap operations, which have been utilized in [17‐19]. Specifically, in the aforementioned references, a swap operation is utilized in an iterative manner to ensure stability after power allocation. However, in the solution procedure, the optimal power allocation per user over each channel is already determined, which is then used to determine the preference lists in the proposed matching algorithms (discussed in the following section). Consequently, the stable matching solutions resulting from the proposed stable matching algorithms will already have obtained the optimal power allocation for the users sharing each channel within each base station.
5 Stable matching algorithms
In this section, the stable matching algorithms based on the SPA problem are devised.
5.1 Description
The classical SPA problem involves a set of students (users), projects (channels), and lecturers (base stations). Each project is offered by a specific lecturer, and each lecturer has quotas (i.e., a maximum number of students per project and per lecturer, respectively). Moreover, students have preferences over the projects that are acceptable (i.e., in which they would like to be involved), while each lecturer has preferences over the acceptable students6. Typically, a project is assigned to at most one student, while in some other cases, a project may be undertaken by more than one student to work on. More importantly, there should be a number of projects that coincides with the number of potential students, and each lecturer is responsible for offering a range of projects, which are not necessarily all taken up. By utilizing the students’ and lecturers’ preferences, the goal is to find a stable matching that pairs students to projects offered by each lecturer, while satisfying the quotas [14,15]. In an analogous manner, the goal is to assign users to channels available at each base station, such that a stable matching solution is obtained, while satisfying the quotas of the channels and base stations.
To that end, a few definitions must first be given.
5.2 Definitions
Definition 1
(Acceptability) A channel \(C_{q,k} \in \mathcal {C}_{q}, \forall {BS}_{q} \in \mathcal {B}\), is said to be acceptable to user \(U_{n} \in \mathcal {U}_{q}\) if \(\chi ^{k}_{q,n} > 0\). Thus, let \(\mathcal {A}_{U_{n}}\) be the list of acceptable channels by user Un. In a similar fashion, \(\mathcal {A}_{BS_{q}}\) is the list of acceptable users \(U_{n} \in \mathcal {U}_{q}\) to base station BSq (i.e., for which ψq, n>0).
Definition 2
(Assignment) An assignment \(\mathcal {M}\) is defined as a subset of \(\mathcal {U} \times \mathcal {C}\), such that:
(a)
\((U_{n}, C_{q,k}) \in \mathcal {M}\) (i.e., user Un finds channel Cq, k acceptable).
(b)
A user Un is assigned at most one channel (i.e., \(| \left \{(U_{n}, C_{q,k}) \in \mathcal {M} \text { for}\, C_{q,k} \in \mathcal {A}_{U_{n}} \right \} | \leq 1\)).
In turn, if \((U_{n}, C_{q,k}) \in \mathcal {M}\), then user Un is considered to be assigned to channel Cq, k, and vice versa (i.e., Cq, k is assigned to Un). Also, let \(\mathcal {M}\left (U_{n} \right) = C_{q,k}\) indicate that channel Cq, k is assigned to user Un in \(\mathcal {M}\), whereas \(\mathcal {M}\left (C_{q,k} \right) = U_{n}\) indicates that user Un is assigned to channel Cq, k.
Definition 3
(Preference) If user Un prefers channel Cq, k to Cw, l (i.e., \(\chi ^{k}_{q,n} > \chi ^{l}_{w,n}\) for k≠l)7, then \(C_{q,k} \succ _{U_{n}} C_{w,l}\phantom {\dot {i}\!}\). In a similar fashion, if base station BSq prefers user Un to Um (i.e., ψq, n>ψq, m for n≠m), then \(\phantom {\dot {i}\!}U_{n} \succ _{BS_{q}} U_{m}\).
Definition 4
(Preference list) Let \(\mathbb {P}_{U_{n}} = \left \{C^{(1)}_{q,k}, \ldots,\right.\hspace *{-3pt} \hspace *{-1pt}\left.C^{(|\mathcal {A}_{U_{n}}|)}_{w,l} \right \}\) denote the preference list of user Un, where \(C^{(1)}_{q,k} \left (C^{(|\mathcal {A}_{U_{n}}|)}_{w,l} \right)\) refers to the most (least) preferred channel to Un. Similarly, \(\mathbb {P}_{BS_{q}} = \left \{U^{(1)}_{n}, \ldots, U^{(|\mathcal {A}_{BS_{q}}|)}_{m} \right \}\) denotes the preference list of base station BSq, where \(U^{(1)}_{n} \left (U^{(|\mathcal {A}_{BS_{q}}|)}_{m} \right)\) refers to the most (least) preferred user to BSq.
Definition 5
(Projected preference list) Let \(\overline {\mathbb {P}}^{k}_{BS_{q}},\! \forall \! {BS}_{q}\! \in \! \mathcal {B}\), be the projected preference list of base station BSq, which is obtained from \(\mathbb {P}_{BS_{q}}\) by eliminating the users who find channel \(C_{q,k} \in \mathcal {C}_{q}\) unacceptable.
Definition 6
(Subscription) A channel \(C_{q,k} \in \mathcal {C}_{q}\) is said to be under-subscribed, full, or over-subscribed if \(|\mathcal {M}\left (C_{q,k} \right)|\) is less than, equal to, or greater than ζq, k, respectively. In a similar manner, for any base station \({BS}_{q} \in \mathcal {B}\) under assignment \(\mathcal {M}\) (i.e., \(\mathcal {M}\left ({BS}_{q} \right)\)), BSq is considered to be under-subscribed, full, or over-subscribed if \(|\mathcal {M}\left ({BS}_{q} \right)|\) is less, equal to, or greater than ξq, respectively.
Definition 7
(Matching) A matching\(\mathcal {M}\) is an assignment, such that [14]:
(a)
For each channel \(C_{q,k} \in \mathcal {C}_{q}, |\mathcal {M}\left (C_{q,k} \right)| \leq \zeta _{q,k}\).
(b)
For each base station \({BS}_{q} \in \mathcal {B}, |\mathcal {M}\left ({BS}_{q} \right)| \leq \xi _{q}\).
In other words, under matching \(\mathcal {M}\), no channel \(C_{q,k} \in \mathcal {C}_{q}\) is assigned to more than ζq, k users and that each base station BSq is assigned at most ξq users.
Definition 8
(Blocking) The pair \(\left (U_{n}, C_{q,k} \right) \in \left (\mathcal {U} \times \mathcal {C} \right) \setminus \mathcal {M}\) is said to block a matching \(\mathcal {M}\) if [15]:
(a)
\(C_{q,k} \in \mathcal {A}_{U_{n}}\) (i.e., user Un finds Cq, k acceptable).
(b)
Either Un is unassigned in \(\mathcal {M}\) or Un prefers Cw, l to \(\mathcal {M}\left (U_{n} \right)\).
(c)
Either
(c1)
Cq, k is under-subscribed, and BSq is under-subscribed, or
(c2)
Cq, k is under-subscribed, BSq is full, and either \(U_{n} \in \mathcal {M}\left ({BS}_{q} \right)\) or BSq prefers Un to the worst user in \(\mathcal {M}\left ({{BS}}_{q} \right)\), or
(c3)
Cq, k is full and BSq prefers Un to the worst user in \(\mathcal {M}\left (C_{q,k} \right)\).
Accordingly, a (student, project) pair satisfying the above conditions should not be included in the matching solution, as such matching would not be stable.
Definition 9
(Stable matching) A matching \(\mathcal {M}\) is considered stable if \(\mathcal {M}\) contains no blocking pairs.
5.3 Algorithmic design
In this subsection, the user-oriented stable matching (U-SM) and base station-oriented stable matching (BS-SM) algorithms are described [15].
5.3.1 User-oriented stable matching
Initially, all users are assumed to be free, and all channels and base stations are completely unsubscribed. The U-SM algorithm is based on a sequence of proposals by each user to the acceptable channels in its preference list. Such proposals lead to provisional assignments between users, channels, and base stations, which may be modified during the execution of the algorithm. That is, entries from the preference lists of users and the preference lists of base stations may be eliminated. To be more specific, deleting a pair (Un,Cq, k) corresponds to eliminating channel Cq, k from user Un’s preference list \(\mathbb {P}_{U_{n}}\) and also removing Un from the projected list \(\overline {\mathbb {P}}^{k}_{\text {BS}_{q}}\) of base station BSq, which offers channel Cq, k. The algorithm iterates as long as there is some user with a non-empty preference list and who is still unpaired to any channel under any base station. If some channel Cq, k is over-subscribed, then its base station rejects the worst user Um assigned to that channel (i.e., the pair (Um,Cq, k) is deleted). Also, if some base station BSq is over-subscribed, then it rejects its worst assigned user Um and deletes the pair (Um,Cq, l), where Cq, l is the channel previously assigned to user Um. On the other hand, if a channel Cq, k is full, then for the worst user Um paired to the channel (as per \(\overline {\mathbb {P}}^{k}_{\text {BS}_{q}}\)), delete the pair of each successive user Up with that channel (i.e., (Up,Cq, k)). Lastly, if some base station BSq is full, then for the worst user Um associated with BSq, delete the pair (Up,Cq, l) of each successive user Up (in \(\mathbb {P}_{\text {BS}_{q}}\)) with each channel Cq, l that Up finds acceptable by base station BSq. The U-SM algorithm is outlined in Algorithm 2.
5.3.2 Base station-oriented stable matching
In a similar manner to the U-SM algorithm, all users are initially assumed to be free, and all channels and base stations are totally unsubscribed. Now, the BS-SM algorithm iterates over each base station BSq that is under-subscribed and offers a channel Cq, k to a user Un, which is the first on BSq’s preference list \(\mathbb {P}_{\text {BS}_{q}}\), and Cq, k must be the first under-subscribed channel on Un’s preference list \(\mathbb {P}_{U_{n}}\), such that \(U_{n} \in \overline {\mathbb {P}}^{k}_{\text {BS}_{q}}\). After breaking any existing assignment of user Un, then it is provisionally assigned to channel Cq, k under base station BSq. In turn, any pair (Un,Cw, l) to which user Un prefers Cq, k to Cw, l is deleted, and hence, Cw, l is removed from Un’s preference list, and Un is eliminated from the projected list \(\overline {\mathbb {P}}^{l}_{\text {BS}_{w}}\) of base station BSw offering channel Cw, l. This process is repeated until convergence, as given in Algorithm 3.
Remark 14
Backhaul links can be utilized to efficiently execute the U-SM and BS-SM algorithms among the base stations with minimal overhead [32,33] and without the need for a centralized controller.
5.4 Properties
In the following subsections, the properties of the U-SM and BS-SM algorithms are discussed. To be concised, the properties of the U-SM algorithm are discussed, which are also applicable to the BS-SM algorithm.
5.4.1 Convergence to a stable matching solution
Lemma 1
The U-SM algorithm converges in a finite number of iterations to a stable matching solution.
Proof
In the U-SM algorithm, a free user applies to the first channel on its preference list in each iteration. In particular, no user can apply to the same channel more than once (i.e., each user-channel pair can occur at most once). This can be verified from the fact that once a pair (Um,Cq, k) is deleted, then user Um is freed and cannot apply to that channel again. This also implies that no pair deleted during the execution of the U-SM algorithm can block the matching under construction [15]. If this had not been the case (i.e., the pair (Um,Cq, k) is not deleted), then user Um must be assigned to some channel \(\mathcal {M}_{U}\left (U_{m} \right) \neq C_{q,k}\); otherwise, user Um remains free with a non-empty preference list containing channel Cq, k (i.e., a contradiction). Therefore, the pair (Um,Cq, k) must be deleted, since if Um prefers Cq, k to \(\mathcal {M}_{U}\left (U_{m}\right)\), then (Um,Cq, k) must block \(\mathcal {M}_{U}\). More importantly, the U-SM algorithm never deletes a stable pair during its execution [15]. Lastly, since the lengths of the user preferences lists are bounded, then the total number of iterations is also bounded. Hence, the U-SM algorithm converges in a finite number of iterations to a stable matching solution. □
5.4.2 Complexity
Lemma 2
The U-SM algorithm converges with polynomial-time complexity of \(\mathcal {O}\left (|\mathcal {U}|\cdot |\mathcal {C}| \right)\), where \(|\mathcal {U}|\) and \(|\mathcal {C}|\) are the total number of users and channels, respectively [15].
Proof
It is straightforward to verify that in the worst-case scenario of the U-SM algorithm, each free user \(U_{n} \in \mathcal {U}\)–with a non-empty preference list—applies to at least one channel out of the possible \(|\mathcal {C}|\) channels. Moreover, throughout the execution of the algorithm, some user-channel pairs may be deleted, and their corresponding entries are deleted from the preference lists of users and from the projected preference lists of base stations. Hence, the overall worst-case complexity of the U-SM algorithm is \(\mathcal {O}\left (|\mathcal {U}|\cdot |\mathcal {C}| \right)\). □
5.4.3 Optimality
Lemma 3
The stable matching resulting from the U-SM algorithm is optimal with respect to each assigned user (i.e., user-optimal stable matching).
Proof
Since each user is assigned to its first preferred channel on its reduced preference list, and no stable pair is deleted during the execution of the U-SM algorithm [15], then each user is simultaneously assigned to the best channel it can get in any stable matching. In addition, and due to the proposed solution procedure SP-PF-SINR-MAX, each user is not only assigned to its best channel, but also is allocated power optimally over its assigned channel. □
By similar arguments, the BS-SM algorithm can straightforwardly be verified to converge to a stable matching solution within a finite number of iterations, and with polynomial-time complexity of \(\mathcal {O}\left (|\mathcal {U}|\cdot |\mathcal {C}| \right)\) [15]. It should be noted that the complexity of both the U-SM and BS-SM algorithms may be much lower than \(\mathcal {O}\left (|\mathcal {U}|\cdot |\mathcal {C}| \right)\), which is due to the fact that each user \(U_{n} \in \mathcal {U}_{q}\) only has preferences over the channels within its cell (i.e., \(\mathcal {C}_{q}\)). In other words, it is only the users within the overlapping region of all cells that may have preferences over all channels. Last-but-not-least, the stable matching resulting from the BS-SM algorithm is simultaneously optimal with respect to each base station. That is, each base station is associated with the best set of users it can get.
Despite the optimality of the proportional fairness SINR-based maximizing power allocation (and hence the solution procedure SP-PF-SINR-MAX), and also the optimality of the proposed stable matching algorithms (i.e., U-SM and BS-SM), the resulting base-station association, channel assignment, and power allocation solutions are not necessarily global optimal. This is due to the following two reasons. Firstly, decomposing problem C-J-UA-CA-PA into two sub-problems does not necessarily guarantee the global optimal solution. Secondly, enforcing stability in terms of the user association and channel assignment via the proposed stable matching algorithms may lead to a sub-optimal solution. Nevertheless, our algorithmic solutions pose a trade-off between complexity, optimality, and stability.
Remark 15
Problem C-J-UA-CA-PA globally optimally maximizes proportional fairness, but does not necessarily ensure that the resulting user association and channel assignment are stable.
The intuition behind Remark 15 is that for some network instance, a certain user may be paired to a certain channel in the solution of problem C-J-UA-CA-PA. However, that (user, channel) pair forms a blocking pair and thus cannot be included in the stable matching solution of any of the stable matching algorithms. In other words, that (user, channel) pair may be formed under problem C-J-UA-CA-PA so as to obtain the global optimal solution, however would be excluded from the matching solution to ensure stability. Specifically, stability is particularly important from a network’s perspective, as it ensures that no user or base station would unilaterally want to change its channel assignment or association. This in turn minimizes communications overheads and signaling.
6 Simulation results
This section evaluates the performance of the proposed solution procedure and stable matching algorithms. The simulations assume a network consisting of Q=3 base stations/cells, with N=12 users, K=9 channels in a 200×200 m2 area and cell radius of 50 m per base station (see Fig. 2). Also, each base station \({\text {BS}}_{q} \in \mathcal {B}\) for q∈{1,2,3} is allocated the channel sets \(\mathcal {C}_{1} = \{C_{1}, C_{2}, C_{3}\}, \mathcal {C}_{2} = \{C_{4}, C_{5}, C_{6}\}\), and \(\mathcal {C}_{3} = \{C_{7}, C_{8}, C_{9}\}\), respectively. Moreover, the transmit power per allocated channel is set to P=1 W, the noise variance is N0=10−7 W, and the path loss exponent is ν=3. The target minimum SINR per user is set to \(\gamma _{T_{n}} = \gamma _{T} = 15\) dB, \(\forall U_{n} \in \mathcal {U}\). Furthermore, the simulations are averaged over 103 independent instances of randomly generated channel coefficients, where the channel coefficients are assumed to be quasi-static during each network instance, but vary from one network instance to another8.
Fig. 2
Simulated network topology
×
In the simulations, the following scenarios are compared: Scenario 1:ξq = 4 and \(\zeta _{q,k} = 2, \forall C_{q,k} \in \mathcal {C}_{q}\) and \(\forall {\text {BS}}_{q} \in \mathcal {B}\). Scenario 2:ξq = 4 and \(\zeta _{q,k} = 3, \forall C_{q,k} \in \mathcal {C}_{q}\) and \(\forall {\text {BS}}_{q} \in \mathcal {B}\).
These scenarios aim at investigating the effect of assigning different numbers of users to each channel. In addition, in the aforementioned scenarios, the following two deterministic power allocation schemes are compared: Equal power allocation (EPA)In this scheme, the power is equally allocated across all users over each channel. Specifically, for Scenario 1 (i.e., ζq, k=2), \(a^{k}_{q,n} = 1/2\), while in Scenario 2 (i.e., ζq, k=3), \(a^{k}_{q,n} = 1/3, \forall U_{n} \in \mathcal {U}_{q}, \forall C_{q,k} \in \mathcal {C}_{q}\), and \(\forall {BS}_{q} \in \mathcal {B}\). Conventional power allocation (CPA)For this scheme, the power allocation coefficients of the ordered network users (for 1≤n≤ζq, k) are set as \(a^{k}_{q,n} = \frac {3-n}{3}\) in Scenario 1, while in Scenario 2, \(a^{k}_{q,n} = \frac {4-n}{6}, \forall U_{n} \in \mathcal {U}_{q}, \forall C_{q,k} \in \mathcal {C}_{q}\), and \(\forall {BS}_{q} \in \mathcal {B}\) [34]. That is, for the ordered users under Scenario 1, \(a^{k}_{q,1} = \frac {2}{3}\) and \(a^{k}_{q,2} = \frac {1}{3} \left (\text {i.e.,}\ a^{k}_{q,1} > a^{k}_{q,2}\right)\), while under Scenario 2, \(a^{k}_{q,1} = \frac {3}{6}, a^{k}_{q,2} = \frac {2}{6}\), and \(a^{k}_{q,3} = \frac {1}{6}\ \left (\text {i.e.,}\ a^{k}_{q,1} > a^{k}_{q,2} > a^{k}_{q,3}\right)\).
For notational convenience, let the proposed U-SM and BS-SM matching algorithm when combined with the SP-PF-SINR-MAX be denoted SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) for short. Similarly, let the power allocation schemes when combined with the proposed stable matching algorithms be denoted EPA (U-SM), EPA (BS-SM), CPA (U-SM), and CPA (BS-SM). Lastly, the proposed algorithms are compared to the C-J-UA-CA-PA scheme9.
In Fig. 3a, the average SINR per user for Scenario 1 is illustrated. In particular, it can be seen that for the SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) algorithms, all network users satisfy the target minimum SINR per user of γT=15 dB. On the other hand, for the proposed stable matching algorithms with the EPA and CPA schemes, not all users satisfy γT. This is due to the fact that power is deterministically allocated to the paired users and without ensuring that the target minimum SINR constraint per user over each channel is satisfied. This proves that the SP-PF-SINR-MAX is effective in guaranteeing that γT is met for all network users. It is also evident that the highest average SINR among all users is achieved by users U2,U7, and U10, which is due to their locations being closest to their respective base stations, as can be seen from Fig. 2. Moreover, the C-J-UA-CA-PA scheme marginally outperforms the proposed SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) algorithms, while guaranteeing that γT is achieved. This is because the C-J-UA-CA-PA scheme maximizes proportional fairness of the SINR of all network users via user association and channel assignment without any bearing on the network stability (as per Remark 15). Figure 3b shows the average power allocation coefficient per user. Evidently, the SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) algorithms allocate power very similarly to all network users. However, the power allocated per user resulting from the C-J-UA-CA-PA scheme is lower than the aforementioned algorithms. As before, this is attributed to the fact that the C-J-UA-CA-PA scheme aims at maximizing proportional fairness without necessarily enforcing stability. Generally speaking, the C-J-UA-CA-PA scheme achieves only marginally higher average SINR per network user with relatively lower transmit power per user. Lastly, it is observed that the users U2,U7, and U10 are allocated relatively lower power than the other network users, since they are relatively closer to their respective base stations than the other users (i.e., in agreement with the concept of NOMA).
Fig. 3
a Average SINR (dB) and b average power allocation coefficients—Scenario 1
×
Similar observations to Fig. 3 can be made for Scenario 2 (see Fig. 4a and b). However, the average SINR per user in Scenario 2 is relatively lower than in Scenario 1. This is attributed to the fact that in Scenario 2, \(\zeta _{q,k} = 3, \forall C_{q,k} \in \mathcal {C}_{q}, \forall {BS}_{q} \in \mathcal {B}\), which implies more users can be assigned to each channel. This in turn means that the available transmit power over each channel is distributed over a potentially larger number of users, and hence, each user’s share of the allocated power is less than that of Scenario 1. As before, it can be seen from Fig. 4a that γT is satisfied for all network users under both proposed SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) algorithms as well as the C-J-UA-CA-PA scheme, but this is not the case for the EPA and CPA schemes when combined with the U-SM and BS-SM matching algorithms.
Fig. 4
a Average SINR (dB) and b average power allocation coefficients—Scenario 2
×
Figure 5 illustrates Jain’s fairness index based on the average SINR of each network user under both scenarios [36]. Evidently, under both scenarios, the C-J-UA-CA-PA scheme achieves the greatest fairness, which is followed by the proposed SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) algorithms, respectively. Contrarily, the EPA and CPA schemes when combined with the U-SM and BS-SM matching algorithms achieve the lowest fairness among all schemes. In addition, the different schemes achieve relatively greater fairness in Scenario 2 than in Scenario 1. This is because Scenario 2 considers a potentially greater number of user combinations over each channel, which in turn maximizes proportional fairness across a greater number of users per channel. Hence, this confirms that the SP-PF-SINR-MAX maximizes proportional fairness among all network users.
Fig. 5
Jain’s fairness index: a Scenario 1 and b Scenario 2
×
In Fig. 6, the average number of associated users per base station of the SP-PF-SINR-MAX (U-SM) algorithm is illustrated. One can see that for Scenario 1 (2), base station BS3 is associated with 4 users about 90.79% (93.47%) of the time, which is greater than base stations BS1 and BS2. More importantly, BS3 is always associated with at least 3 users under both scenarios. In Fig. 7, the average number of associated users per base station of the SP-PF-SINR-MAX (BS-SM) is illustrated. As before, for BS3, the average numbers of associated users for Scenarios 1 and 2 are 82.88% and 84.07%, respectively, which are greater than those of BS1 and BS2. By comparing Figs. 6 and 7, base stations BS1 and BS2 under the SP-PF-SINR-MAX (BS-SM) algorithm are associated with four users more often than the SP-PF-SINR-MAX (U-SM) algorithm, under both scenarios. An opposite observation can be made for base station BS3.
Fig. 6
Average number of associated users—SP-PF-SINR-MAX (U-SM) algorithm. a BS1 (Scenario 1). b BS2 (Scenario 1). c BS3 (Scenario 1). d BS1 (Scenario 2). e BS2 (Scenario 2). f BS3 (Scenario 2)
Fig. 7
Average number of associated users—SP-PF-SINR-MAX (BS-SM) algorithm. a BS1 (Scenario 1). b BS2 (Scenario 1). c BS3 (Scenario 1). d BS1 (Scenario 2). e BS2 (Scenario 2). f BS3 (Scenario 2)
×
×
Figure 8 illustrates the percentage of user unassignment under the U-SM and BS-SM algorithms when combined with the SP-PF-SINR-MAX for both scenarios. Evidently, U1 and U8 are the two users with the highest percentage of unassignment, and this is because they are farthest from their respective base stations as well as not being in the overlapping region of other base stations. It is also noteworthy that although user U6 is located at the cell edge of all three base stations, the percentage of it being unassigned is at most 2%, under both scenarios. This is due to the fact that it can be allocated a channel by any of the three base stations, since it falls within the overlapping region of all three base stations. Additionally, all users except U1 and U8 are assigned to a channel and associated with a base station at least 90% of the time, under both scenarios.
Fig. 8
Percentage of user unassignment: a Scenario 1 and b Scenario 2
×
Figure 9 demonstrates the percentage of channel assignment of users U3,U4,U5,U6, and U9 under both matching algorithms (with SP-PF-SINR-MAX) under Scenario 1. Specifically, one can see that user U3 is paired only with the channels of base stations BS1 and BS3 (i.e., in \(\mathcal {C}_{1}\) and \(\mathcal {C}_{3}\)). As for user U6, it is paired with all channels, since it falls within the overlapping region of all three base stations. Similar observations can be made to the other users. To summarize, it has been verified that all users can only be paired with the channels corresponding to cells where they are located. Similar observations are made for Scenario 2 in Fig. 10.
Fig. 9
Percentage of channel assignment—Scenario 1. a U3 (U-SM). b U3 (BS-SM). c U4 (U-SM). d U4 (BS-SM). e U5 (U-SM). f U5 (BS-SM). g U6 (U-SM). h U6 (BS-SM). i U9 (U-SM). j U9 (BS-SM)
Fig. 10
Percentage of channel assignment—Scenario 2. a U3 (U-SM). b U3 (BS-SM). c U4 (U-SM). d U4 (BS-SM). e U5 (U-SM). f U5 (BS-SM). g U6 (U-SM). h U6 (BS-SM). i U9 (U-SM). j U9 (BS-SM)
×
×
Figure 11a and b illustrate the average number of iterations of each stable matching algorithms (with SP-PF-SINR-MAX) under Scenarios 1 and 2. It is evident that both algorithms require almost the same number of iterations under the two scenarios. More importantly, the BS-SM algorithm requires more iterations than its U-SM counterpart algorithm. In addition, for our simulated network scenario in Fig. 2, \(|\mathcal {C}_{1}| = |\mathcal {C}_{2}| = |\mathcal {C}_{3}| = 3\), and \(|\mathcal {U}_{1}| = |\mathcal {U}_{2}| = |\mathcal {U}_{3}| = 6\). Based on Remarks 5, 8, and 13, and for Scenario 1, the execution of the solution procedure locally at each base station requires a total of 63 iterations, of which 45 iterations involve the solution of a convex optimization problem, which can be solved within polynomial-time complexity. As for scenario 2, each base station involves at total of 123 iterations of the solution procedure, of which 105 iterations involve the solution a convex optimization problem. In turn, both SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) algorithms can be executed efficiently and with lower computational complexity than the C-J-UA-CA-PA scheme. On the other hand, in Fig. 11c, the percentage of identical stable matchings of the proposed stable matching algorithms is illustrated. Particularly, it can be seen that for Scenario 2, the percentage of identical matchings is slightly less than that of Scenario 1. This is due to the fact in Scenario 2, there are more user combinations than in the case of Scenario 1, which results in identical matchings occurring slightly less often. In all, increasing the maximum number of users that can be assigned a channel reduces the possibility of having identical matchings for both stable matching algorithms. This also explains the discrepancies in the resulting average SINR, average number of associated users with each base station, and percentages of user unassignment and channel assignment of the proposed stable matching algorithms.
Fig. 11
Average number of iterations for aU-SM, and bBS-SM, and c Percentage of identical matchings
×
In summary, the proposed algorithmic solutions have been shown to yield comparable performance to the C-J-UA-CA-PA scheme in terms of average SINR per user and network SINR-based fairness. Additionally, the proposed algorithms have been shown to efficiently associate users with base stations and assign them to channels. More importantly, the proposed solution procedure can be executed locally at each base station to determine the proportional fairness maximizing power allocation and preference lists, while the stable matching algorithms can be efficiently executed among the base stations to perform user association and channel assignment with minimal communication overheads and signaling, and with the added merit of network stability. In other words, the proposed SP-PF-SINR-MAX (U-SM) and SP-PF-SINR-MAX (BS-SM) algorithms offer a reasonable trade-off between average SINR, fairness, complexity, and stability.
7 Conclusions
In this paper, the problem of joint user association and channel assignment with proportional fairness SINR-based power allocation in downlink multi-cell NOMA networks has been studied. Particularly, a low-complexity iterative solution procedure has been devised to determine the optimal power allocation for proportional fairness SINR-based maximization over each channel within each cell. Moreover, two many-to-one polynomial-time complexity matching algorithms have been proposed to associate users with base stations and perform channel assignment. To validate the efficacy of the proposed solution procedure and stable matching algorithms, extensive simulation results have been presented, which illustrate that the proposed algorithms efficiently yield comparable SINR per user to the C-J-UA-CA-PA scheme as well as maximizing proportional fairness and satisfying QoS constraints. Finally, the proposed algorithms have been shown to efficiently assign channels to cell-edge users and especially those within the overlapping region of multiple cells.
Acknowledgements
Not applicable.
Competing interests
The authors declare that they have no competing interests.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Our algorithmic designs are applicable to arbitrary network topologies and sets of parameters, provided that the selected parameters yield feasible solutions.
The C-J-UA-CA-PA problem is solved via MIDACO [35], with tolerance set to 0.001. Moreover, problem C-J-UA-CA-PA involves a total of 648 decision variables and 144 inequality constraints.
