1 Introduction

Being a potential remedy for emerging local communication and high quality-of-service (QoS) requirement [1], Device-to-Device (D2D) communication underlaying cellular network [2,3,4] is drawing more and more attention and viewed as a promising add-on component in future radio communication systems [5, 6]. It takes advantage of the favorable channel condition in proximity by enabling the data link to be directly built up between the communicating user equipment (UE) instead of being relayed via base station (BS), and thus leads to high spectral efficiency, low energy consumption and short transmission latency. Besides, it offloads the burden of BS [2], extends cell coverage [3] and enriches the system functionalities [4]. And, due to spectral shortage, D2D communication is preferred to be implemented in underlay mode [2,3,4,5,6] by reusing the spectrum of cellular network under the control of BS. But, intra-cell orthogonality is impaired as a result of spectral sharing, and severe interference can be imposed between cellular links (C-Ls) and D2D links (D-Ls). So, it is a sticky issue on how to explore the potential gain of underlaid D-Ls in the above two-tier hybrid system with the existing C-Ls having a higher priority.

Power control (PC) [7] and channel assignment (CA) [8] have proven to be efficient to enhance system performance and achieve individual QoS requirement, thus are capable to tackle the above issue. In general, four system-wide performance metrics are commonly addressed: (1) energy conservation (EC), (2) system throughput (ST), (3) energy efficiency (EE), and (4) the minimum individual data rate (MI). Besides, individual QoS experience is emphasized in future user-centric radio communication systems [5, 6], but it would be handicapped by the greedy optimization of the above system-wide metrics. For instance, in a single-cell code-division-multiple-access (CDMA) based interference-limited system, ST is maximized only when the link with the most favorable channel condition transmits at its maximum power while the rest stay silent [9], and the case in multi-cell scenario can be explained by the theory of opportunistic communication [10], i.e., the link with favorable channel condition is plausible to transmit at larger transmit power, and contributes to a higher data rate. EC deteriorates with the increase in the number of co-channel links to combat the mutual interference under given data rate constraint [7]. EE is to balance the utilization of multiuser diversity and energy consumption [11], but it still omits QoS protection, and when only one link is involved, the EE is strictly decreasing in the transmit power. Different to ST and EE, MI enables all links to transmit and impedes the exploration of multiuser diversity, and specifically, in a single-channel case [12], all links will achieve a same QoS level at the risk that no one can fulfill its QoS requirement, and the links with unfavorable channel condition have to consume more power to compensate their disadvantage. On the other hand, the system may be infeasible [7], i.e., not all individual QoS requirement can be maintained at the same time, so it is better to minimize the outage ratio or maximize the number of links with satisfied QoS requirement, i.e., system capacity (SC), which calls for the design of admission control (AC) [7]. To conclude, it may be wise to make a tradeoff between the optimization of system-wide metric and SC for underlaid D-Ls with additional QoS protection for prioritized C-Ls by means of PC and CA as well as AC.

Several works have been done on the design of resource allocation in our hybrid system. Yu et al. [13] considered a simple prototype where only one C-L and one D-L were involved and maximized ST via joint design of spectral reuse mode and PC. Zulhasnine et al. [14], Jänis et al. [15], Ji et al. [16], Feng et al. [17] and Yin et al. [18] extended it to multi-channel scenario. Specifically, [14, 15] optimized ST and MI, respectively, by means of CA, but individual QoS requirement of D-Ls was omitted in [15] as [13]. Taking the above insufficiency into account, [16] initially observed the tradeoff between ST and SC. A complete design of AC, PC and CA was proposed in [17] for ST with full QoS protection, and [18] applied the above framework to optimize EE. Zhu et al. [19] enabled one D-L to reuse multiple channels and maximized ST by joint PC and CA, thus outweighed [20] where only CA was involved, but individual QoS requirement of D-Ls was still neglected [19, 20]. Cai et al. [21] overcame the about drawback via the design of CA, while omitting the coupling among channels assigned to a same D-Ls and failing to consider the feasibility check [7]. Wen et al. [22] optimized EC for multiple D2D clusters by assuming that orthogonality was achieved among them, but the QoS protection was imposed on the cluster level rather than individual level. In addition, [23] tried to maximize EE under individual QoS requirement via coalition game. The works in [13,14,15,16,17,18,19,20,21,22,23] have shown the great benefit of underlaid D-Ls, but they all restrict that each channel can only be reused by at most one D-Ls. So, [24,25,26,27,28,29,30,31,32,33] eliminated the above restriction to fully explore the proximate gain in a much denser spectral sharing condition. Oduola et al. [24] and Shalmashi [25] considered the single-channel case: [24] focused on feasibility check while [25] attempted to estimate the upper bound of SC under partial channel state information, but QoS protection was only given to prioritized C-Ls. Xu et al. [26] extended it to multi-channel scenario and optimized ST via auction-based CA. Zhang et al. [27] addressed the same problem as in [26] using graph theory, which was extensively applied in cognitive radio network [28, 29]. Moreover, EC was considered in [30, 31] and distributed PC schemes were raised to further reduce signaling overhead, but the one in [30] may lead to power diverging [7] in case of infeasibility due to the vacancy of AC mechanism, while the one in [31] omitted the design of CA. Wang et al. [32] maximized EE by adopting the framework in [26] and incorporated PC in the model, but it inherited the deficiency of [19, 20] and the complexity of the mechanism in [26, 32] increased exponentially with number of channels. Jung et al. [33] optimized EE in a CDMA-based system with QoS protection while lacking of feasibility check as [21, 30].

Inspired from the prior works [13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33], we are dedicated to building up a framework comparable to [17] when dense spectral sharing is enabled as in [24,25,26,27,28,29,30,31,32,33], and extend the optimization target to include EC, ST, EE and MI with additional consideration for individual QoS protection as expected in [5, 6] while missed in [13, 15, 19, 20, 22, 25,26,27,28,29, 32]. Besides, we include multiple resource variables into the optimization model for supreme performance which is neglected in [13,14,15,16, 20, 21, 24,25,26,27,28,29, 31, 33]. Finally, the contributions of our paper are threefold:

  • To fully address the performance tradeoff between the individual QoS requirement and the system-wide metric, we put forward a two-step mechanism. In step one: We aim to maximize the number of admitted D-Ls, i.e., SC, which explains what “capacity-oriented” means in our title. In step two: We continue to enhance the system-wide metric, i.e., EC, ST, EE, or MI, among the D-Ls admitted in previous step. Finally, the system-wide metric is optimized on condition that SC is maximized for underlaid D-Ls and QoS protection is rigidly guaranteed for prioritized C-Ls.

  • Unfortunately, the original problem to minimize the outage ratio or maximize SC in step one is non-trivial to be solved, so we model it from the perspective of graph theory and propose a joint AC and CA scheme. We further incorporate PC into step two to enhance system-wide metric, and it is worth noting that PC is also involved in step one and helps dynamically construct our graph model to eliminate infeasibility which may happen in [21, 30, 33].

  • With the help of simulations, we demonstrate that our capacity-oriented mechanism greatly outweighs greedy optimizations of system-wide metric in terms of SC, and achieves the polynomial-time complexity at only minor performance loss compared to that derived by the professional optimization toolbox. Besides, we illustrate the gain when dense spectral reusing is enabled and multiple resource variables are in elaborate cooperation compared to the literatures.

The remainder of the paper is organized as follows: In Sect. 2, we introduce the system model and formulate the original problem for performance tradeoff between system-wide metric and SC for D-Ls. In Sect. 3, we decompose the above problem into two parts and propose a two-step mechanism with each step amply articulated in a sequential order. Extensive simulations are conducted to show the efficacy of our mechanism in Sect. 4, and conclusions are finally drawn in Sect. 5.

2 System Model

We consider a single-cell cellular system where only uplink channels are available to be reused as BS is more capable to handle the interference than UEs. We assume a fully-loaded scenario where each channel has been assigned to a C-L with predefined power by cellular scheduler and each D-L is made up of one D2D transmitter (DT) and one D2D receiver (DR). We adopt the setting in [24,25,26,27,28,29,30,31,32,33] that each channel can be reused by multiple D-Ls to explore the spatial gain, while one D-L can only reuse at most one channel. We denote the set of prioritized C-Ls and underlaid D-Ls as \(C = \{ 1,2, \ldots ,N\}\) and \(D = \{ 1,2, \ldots ,M\}\), respectively, where \(N\) and \(M\) are the cardinality of the corresponding sets, and the label of each channel is identical to that of the C-L it is assigned to. Besides, we assume the path gain and received noise of each link are channel-independent, and channels are orthogonal to each other. The individual QoS experience is abstracted by the signal to interference plus noise ratio (SINR) as in [13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33]. Notations: Boldface capital and lowercase letters are to denote matrices and vectors, and the inequalities of matrices and vectors are component-wise. Vectors are assumed to be column ones and the transposition of vector \({\mathbf{a}}\) is denoted as \({\mathbf{a}}^{T}\), and the optimal value of variable \(v\) for a given problem is denoted as \(v^{*}\).

Binary variables \(x_{i,n}^{D}\) are defined to show the CA of D-Ls: If the i-th D-L is assigned to the n-th channel, \(x_{i,n}^{D} = 1\), otherwise, \(x_{i,n}^{D} = 0\), and if \(\sum\nolimits_{n \in C} {x_{j,n}^{D} } = 0\), it means the j-th D-L is not admitted into the system. Besides, the set of D-Ls reusing the n-th channel can be denoted as \(S_{n} = \{ k \in D|x_{k,n}^{D} = 1\}\), and we assume \(S_{n} \ne \emptyset ,i \in S_{n}\). For the i-th D-L on the n-th channel, we denote the path gain between its DR and its own DT, the j-th DT and the transmitter of the n-th C-L as \(G_{i}^{D} ,G_{i,j}^{DD} ,G_{i,n}^{DC}\), respectively, and signify its received noise at DR as \(\sigma_{i}^{D}\), thus the SINR of the i-th D-L and the n-th C-L can be defined in (1) as \(\gamma_{i,n}^{D}\) and \(\gamma_{n}^{C}\), respectively,

$$\begin{array}{c} \gamma_{i,n}^{D}=\dfrac{G_{i}^{D} p_{i,n}^{D}}{\sum\nolimits_{\begin{subarray}{l} j \in S_{n} \\ j \ne i \end{subarray} } {G_{i,j}^{DD} p_{j,n}^{D} } + G_{i,n}^{DC} p_{n}^{C} + \sigma_{i}^{D}},\\ \gamma_{n}^{C}=\dfrac{G_{n}^{C} p_{n}^{C}}{\sum\nolimits_{{k \in S_{n} }} {G_{n,k}^{CD} p_{k,n}^{D} } + \sigma_{n}^{C}}, \end{array}$$
(1)

where \(p_{i,n}^{D}\) is the transmit power of the i-th DT on the n-th channel which is upper-bounded by \(p_{i,\hbox{max} }^{D}\), and \(G_{n,k}^{CD}\) is the path gain from the k-th DT to the receiver of the n-th C-L, i.e., the BS, while \(G_{n}^{C} ,p_{n}^{C} ,\sigma_{n}^{C}\) are the desired path gain, fixed transmit power, and received noise of the n-th C-L, respectively. To facilitate the denotations, we set \(I_{i,n}^{D} = G_{i,n}^{DC} p_{n}^{C} + \sigma_{i}^{D}\). If we define \(Z_{i,j}^{D} ,j \in S_{n} ,j \ne i\) and \(\eta_{i,n}^{D}\) as the normalized form of \(G_{i,j}^{D} ,j \in S_{n} ,j \ne i\) and \(I_{i,n}^{D}\) with respect to \(G_{i}^{D}\), respectively, i.e., \(Z_{i,j}^{D} = G_{i,j}^{D} /G_{i}^{D} ,j \ne i,\eta_{i,n}^{D} = I_{i,n}^{D} /G_{i}^{D}\), the relationship between transmit power of D-Ls and the achieved SINRs can be expressed in matrix form as (2),

$$({\mathbf{E}}_{{S_{n} }} - {\mathbf{D}}({\varvec{\upgamma}}_{{S_{n} }} ){\mathbf{Z}}_{{S_{n} }} ){\mathbf{p}}_{{S_{n} }} = {\mathbf{D}}({\varvec{\upgamma}}_{{S_{n} }} ){\varvec{\upeta}}_{{S_{n} }}$$
(2)

where \({\mathbf{Z}}_{{S_{n} }}\) is the matrix form of \(Z_{k,l}^{D} ,k,l \in S_{n} ,k \ne l\) with all diagonal elements being 0; \({\mathbf{D}}({\varvec{\upgamma}}_{{S_{n} }} )\) is the diagonal matrix with vector \({\varvec{\upgamma}}_{{S_{n} }}\) being diagonal elements, and \({\varvec{\upgamma}}_{{S_{n} }}\) is the vector form of \(\gamma_{k,n}^{D} ,\forall k \in S_{n}\), i.e., \({\varvec{\upgamma}}_{{S_{n} }} = \{ \gamma_{k,n}^{D} \}_{{k \in S_{n} }}\). \({\mathbf{E}}_{{S_{n} }}\) is the identity matrix of the same size with \({\mathbf{Z}}_{{S_{n} }}\); \({\mathbf{p}}_{{S_{n} }} ,{\varvec{\upeta}}_{{S_{n} }}\) are the vector form of \(p_{k,n}^{D} ,\forall k \in S_{n}\) and \(\eta_{k,n}^{D} ,\forall k \in S_{n}\), respectively, i.e., \({\mathbf{p}}_{{S_{n} }} = \{ p_{k,n}^{D} \}_{{k \in S_{n} }} ,{\varvec{\upeta}}_{{S_{n} }} = \{ \eta_{k,n}^{D} \}_{{k \in S_{n} }}\). Besides, each link requires an SINR threshold, and we denote that of the n-th C-L and the i-th D-L as \(\varphi_{n}^{C}\) and \(\varphi_{i}^{D}\), respectively. We assume the cellular system to be interference-limited, so that the QoS requirement of a C-L can be obtained when no D-Ls is reusing its channel and we denote \(Q_{n}^{C} = G_{n}^{C} p_{n}^{C} /\varphi_{n}^{C} - \sigma_{n}^{C} > 0\). Finally, the four system-wide metrics, i.e., EC, ST, EE and MI, can be defined in (3) as \(\alpha ,\beta ,\delta ,\theta\), respectively,

$$\begin{array}{c} \alpha = \sum\nolimits_{n \in C} {\sum\nolimits_{{i \in S_{n} }} {p_{i,n}^{D} } } ;\\ \beta = \sum\nolimits_{n \in C} {\sum\nolimits_{{i \in S_{n} }} {\log_{2} (1 + \gamma_{i,n}^{D} )} } ;\\ \delta = \beta /\alpha ;\\ \theta = \min_{i \in D} \sum\nolimits_{m \in C} {x_{i,m}^{D} \log_{2} (1 + \gamma_{i,m}^{D} )}. \end{array}$$
(3)

Based on the above denotations, the original problem to balance the performance tradeoff between system-wide metric and outage ratio or, equivalently, SC can be defined in (4),

$$\begin{array}{clr} \max_{x_{i,n}^{D},p_{i,n}^{D}} & {\psi}, & (a)\\ \min_{x_{i,n}^{D},p_{i,n}^{D}} & \left(M-\sum\nolimits_{n\in C} {|S_{n}|}\right)/M=\max_{x_{i,n}^{D},p_{i,n}^{D}} {\sum\nolimits_{n\in C} {|S_{n}|}}, & (b)\\ \mathrm{s.t.} & x_{{i,n}}^{D} = \{ 0,1\} ,\sum\nolimits_{{m \in C}} {x_{{i,m}}^{D} } \le 1,\forall i \in D, & (c)\\ & 0 \le p_{{i,n}}^{D} \le p_{{i,\max }}^{D} ,\forall i \in D,n \in C, & (d)\\ & \gamma_{n}^{C} \ge \varphi_{n}^{C},\forall n \in C, & (e)\\ & \gamma_{{i,n}}^{D} \ge \varphi_{i}^{D},\forall i \in S_{n},n \in C, & (f) \end{array}$$
(4)

where \(\psi\) in (4a) is the specified system-wide metric, i.e., any of \(\alpha ,\beta ,\delta ,\theta\). (4b) is to minimize outage ratio or maximize SC. (4c) is the definition of CA variables, and indicates each D-L can reuse at most one channel. (4d) is the local power budget constraint at each D-L, and (4e) and (4f) are to satisfy the QoS requirement of all prioritized C-Ls and admitted D-Ls, respectively.

3 Our Two-Step Resource Allocation Mechanism

The original problem in (4) is a multi-objective and mixed-integer non-linear programming, which is in general NP-hard and non-trivial to be analyzed. Accordingly, we decompose the above performance tradeoff into two parts and devise a two-step mechanism accordingly: In step one, we attempt to answer the following two questions: (1) which set of requesting D-Ls should be admitted, and (2) which channel should be assigned to each of the above admitted D-Ls, so that the outage ratio is minimized or the SC is maximized as demonstrated by Problem 1 (P1) in (5); In step two, we proceed to answer (3) how much power should be allocated to the above admitted D-Ls, so that their specified system-wide metric is optimized with strict QoS protection as illustrated by Problem 2 (P2) in (6), where \(S_{n}^{*} = S_{n} (x_{i,j}^{D*} )\) is a function of the optimal variable \(x_{i,j}^{D*}\) to P1, i.e., \(S_{n}^{*} = S_{n} (x_{i,j}^{D*} ) = \{ k \in D|x_{k,n}^{D*} = 1\} ,\forall n \in C\). Besides, the QoS requirement of prioritized C-Ls is always guaranteed during our two-step mechanism.

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 1:}} & \max_{{x_{i,n}^{D}{\kern 1pt},p_{i,n}^{D} }} & \sum\nolimits_{n \in C} {|S_{n}|} & (a)\\ & \mathrm{s.t.} & x_{i,n}^{D} = \{ 0,1\} ,\sum\nolimits_{m \in C} {x_{i,m}^{D} } \le 1,\forall i \in D, & (b)\\ & & 0 \le p_{i,n}^{D} \le p_{i,\hbox{max} }^{D} ,\forall i \in D,n \in C, & (c)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C} ,\forall n \in C, & (d)\\ & & \gamma_{i,n}^{D} \ge \varphi_{i}^{D} ,\forall i \in S_{n} ,n \in C. & (e) \end{array}$$
(5)
$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 2:}} & \max_{{p_{i,n}^{D} }} & \psi, & (a)\\ & \mathrm{s.t.} & 0 \le p_{i,n}^{D} \le p_{i,\hbox{max} }^{D} ,\forall i \in S_{n}^{*} ,n \in C, & (b)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C} ,\forall n \in C, & (c)\\ & & \gamma_{i,n}^{D} \ge \varphi_{i}^{D} ,\forall i \in S_{n}^{*} ,n \in C. & (d) \end{array}$$
(6)

In what follows, we show the high complexity of P1 and view it from the perspective of graph theory as elaborated in Sect. 3.1, while the details of PC optimization to P2 will be presented at length in Sect. 3.2 for each of the four metrics listed in (3).

3.1 Capacity-Oriented AC and CA Mechanism from Graph Perspective

In this section, we start from the single-channel scenario where P1 in (5) is reduced to the design of AC only, which is shown to be a mixed-integer linear programming and in general NP-hard, thus we propose a heuristic scheme from graph perspective and further extend it to multi-channel scenario.

3.1.1 Single-Channel Scenario

Without loss of generality, we only consider the n-th channel in this subsection and the design of AC can be mathematically formulated as Problem 3 (P3) in (7),

$$\begin{array}{lclc} \underline{{Problem\ 3:}} & \max_{x_{i,n}^{D},p_{i,n}^{D}} & |S_{n}|=\sum\nolimits_{i \in D} {x_{i,n}^{D}}, & (a)\\ & {\rm s.t.} & x_{i,n}^{D} = \{ 0,1\} ,\forall i \in D, & (b)\\ & & 0 \le p_{i,n}^{D} \le p_{i,{\rm max} }^{D} ,\forall i \in D, & (c)\\ & & \gamma_{n}^{C}=G_{n}^{C} p_{n}^{C}\big/\left(\sum\nolimits_{{k \in S_{n} }} {G_{n,k}^{CD} p_{k,n}^{D} } + \sigma_{n}^{C}\right)\ge \varphi_{n}^{C}, & (d)\\ & & \gamma_{i,n}^{D}=p_{i,n}^{D}\big/\left(\sum\nolimits_{j \in D \atop j \ne i} {Z_{i,j}^{DD} p_{j,n}^{D}} + \eta_{i,n}^{D}\right)\ge \varphi_{i}^{D},\forall i\in S_{n}. & (e) \end{array}$$
(7)

It’s noteworthy that constraint (7e) is pertinent to the value of variable \(x_{i,n}^{D}\), so we reformulate it in (8) to remove the above coupling, where \(B_{i,n}^{D} = \varphi_{i}^{D} (\sum\nolimits_{\begin{subarray}{l} j \in D \\ j \ne i \end{subarray} } {Z_{i,j}^{DD} p_{j,\hbox{max} }^{D} } + \eta_{i,n}^{D} )\) and is introduced to make (8) applicable to both admitted and non-admitted D-Ls, i.e., if \(x_{i,n}^{D} = 1\), it simply reduces to (7e); otherwise, \(B_{i,n}^{D} /(\sum\nolimits_{\begin{subarray}{l} j \in D \\ j \ne i \end{subarray} } {Z_{i,j}^{DD} p_{j,n}^{D} } + \eta_{i,n}^{D} ) \ge \varphi_{i}^{D}\) is always satisfied, so \(p_{i,n}^{D}\) will be driven to 0 and facilitates the QoS achievement of the remaining D-Ls. With some manipulations, P3 can be rewritten in (9) and turns out to be a mixed-integer linear programming, which motivates our graph formulation.

$$\dfrac{p_{i,n}^{D} + (1 - x_{i,j}^{D} )B_{i,n}^{D}}{\sum\nolimits_{\begin{subarray}{l} j \in D \\ j \ne i \end{subarray} } {Z_{i,j}^{DD} p_{j,n}^{D} } + \eta_{i,n}^{D}} \ge \varphi_{i}^{D} ,\forall i \in D.$$
(8)
$$\begin{array}{clr} \max_{x_{i,n}^{D},p_{i,n}^{D}} & |S_{n}|=\sum\nolimits_{i \in D} {x_{i,n}^{D}} & (a)\\ \mathrm{s.t.} & x_{i,n}^{D} = \{ 0,1\} ,\forall i \in D, & (b)\\ & 0 \le p_{i,n}^{D} \le p_{i,\hbox{max} }^{D} ,\forall i \in D, & (c)\\ & \sum\nolimits_{k \in D} {G_{n,k}^{CD} p_{k,n}^{D} } \le Q_{n}^{C}, & (d)\\ & \varphi_{i}^{D} \sum\nolimits_{j \in D \atop j \ne i} {Z_{i,j}^{DD} p_{j,n}^{D} } - p_{i,n}^{D} + B_{i,n}^{D} x_{i,n}^{D} \le \varphi_{i}^{D} \sum\nolimits_{j \in D \atop j \ne i} {Z_{i,j}^{DD} p_{j,\hbox{max} }^{D} } ,\forall i \in D. & (e) \end{array}$$
(9)
3.1.1.1 Static Graph Formulation

To facilitate the elaboration of the following part, we first give the definition of feasible set below.

Definition 1

A set of D-Ls, e.g., \(S_{n}\), is a feasible set on the n-th channel if the set of power vectors \(A_{{S_{n} }}\) defined in (10) is non-empty, i.e., (1) the SINR thresholds of underlaid D-Ls in \(S_{n}\) can be achieved within their local power budgets, and (2) the SINR threshold of the prioritized C-L is also obtained. We denote the set of all feasible sets on the n-th channel as \(F_{n} = \{ S_{n} \subseteq D|A_{{S_{n} }} \ne \emptyset \}\).

$$A_{{S_{n} }} = \{ {\mathbf{p}}_{{s_{n} }} = \{ p_{i,n}^{D} \}_{{i \in S_{n} }} |0 \le p_{i,n}^{D} \le p_{i,\hbox{max} }^{D} ;\gamma_{i,n}^{D} \ge \varphi_{i}^{D} ,\forall i \in S_{n} ;\sum\nolimits_{{k \in S_{n} }} {G_{n,k}^{CD} p_{k,n}^{D} } \le Q_{n}^{C} \}$$
(10)

By Definition 1, our original problem for SC maximization on the n-th channel is to find the feasible set with the largest cardinality, i.e., \(S_{n}^{*} = argmax_{{S_{n} \in F_{n} }} |S_{n} |\). To make it tractable, we formulate an undirected graph model \(G_{n} = (V_{n} ,E_{n} )\), where \(V_{n}\) is the set of vertices or underlaid D-Ls, and \(i \in V_{n}\) if the i-th D-L is at least accessible when it is the unique D-L reusing the n-th channel, i.e., \(V_{n} = \{ j \in D|\{ j\} \in F_{n} \}\); while \(E_{n}\) is the set of edges, and two vertices will form an edge if the two D-Ls can’t reuse the n-th channel in the meantime regardless of the remaining ones, i.e., \(E_{n} = \{ (k,l)|\{ k\} ,\{ l\} \in F_{n} ,k \ne l,\{ k,l\} \notin F_{n} \}\). And we articulate the vertex and edge formulation rule below which is addressed by Propositions 1 and 2 respectively.

The vertex formulation rule 1 (VF-R1) \(i \in V_{n}\) or equivalently \(\{ i\} \in F_{n}\) if the optimal objective function in Problem 4 (P4) satisfies \(\gamma_{i,n}^{D*} \ge \varphi_{i}^{D}\).

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 4:}} & \max_{{p_{{i,n}}^{D}}} & \gamma_{{i,n}}^{D} = p_{{i,n}}^{D} /\eta_{{i,n}}^{D}, & (a)\\ & \mathrm{s.t.} & 0 \le p_{{i,n}}^{D} \le p_{{i,\max }}^{D}, & (b)\\ & & \gamma _{n}^{C} = p_{n}^{C} G_{n}^{C} /(p_{{i,n}}^{D} G_{{n,i}}^{{CD}} + \sigma _{n}^{C} ) \ge \varphi _{n}^{C}. & (c) \end{array}$$
(11)

Proposition 1

The optimal objective function in P4 satisfies \(\gamma_{i,n}^{D*} \ge \varphi_{i}^{D}\) if \(\varphi_{i}^{D} \eta_{i,n}^{D} \le \hbox{min} \{ Q_{n}^{C} /G_{n,i}^{CD} ,p_{i,\hbox{max} }^{D} \}\).

Proof

In P4, \(\gamma_{i,n}^{D}\) is strictly increasing in \(p_{i,n}^{D}\), thus \(\gamma_{i,n}^{D*}\) is achieved when \(p_{i,n}^{D}\) takes its maximum, i.e., \(p_{i,n}^{D*} = \hbox{min} \{ Q_{n}^{C} /G_{n,i}^{CD} ,p_{i,\hbox{max} }^{D} \}\), and to maintain \(\gamma_{i,n}^{D*} \ge \varphi_{i}^{D}\), \(p_{i,n}^{D*} \ge \varphi_{i}^{D} \eta_{i,n}^{D}\), so \(\varphi_{i}^{D} \eta_{i,n}^{D} \le \hbox{min} \{ Q_{n}^{C} /G_{n,i}^{CD} ,p_{i,\hbox{max} }^{D} \}\).

The edge construction rule 1 (EF-R1) \((i,j) \in E_{n} ,\forall i,j \in V_{n}\) or equivalently \(\{ i,j\} \notin F_{n} ,\forall \{ i\} ,\{ j\} \in F_{n}\) if Problem 5 (P5) in (12) has no feasible solution.

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 5:}} & \min_{{p_{k,n}^{D} }} & \sum\nolimits_{{k \in \{ i,j\} }} {p_{k,n}^{D} } & (a)\\ & \mathrm{s.t.} & 0 \le p_{k,n}^{D} \le p_{k,\hbox{max} }^{D} ,\forall k \in \{ i,j\}, & (b)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C}, & (c)\\ & & \gamma_{k,n}^{D} \ge \varphi_{k}^{D} ,\forall k \in \{ i,j\}. & (d) \end{array}$$
(12)

Proposition 2

P5 has no feasible solution if either of the two conditions is satisfied: (i) \(A_{1} \le 0\), (ii) \(A_{2} /A_{1} > \hbox{min} \{ A_{3} ,A_{4} ,p_{i,\hbox{max} }^{D} \}\) , where \(A_{1} = 1 - \varphi_{j}^{D} \varphi_{i}^{D} Z_{i,j}^{DD} Z_{j,i}^{DD}\), \(A_{2} = \varphi_{i}^{D} \varphi_{j}^{D} Z_{i,j}^{DD} \eta_{j,n}^{D} + \varphi_{i}^{D} \eta_{i,n}^{D}\), \(A_{3} = (p_{j,\hbox{max} }^{D} /\varphi_{j}^{D} - \eta_{j,n}^{D} )/Z_{j,i}^{DD}\) and \(A_{4} = (Q_{n}^{C} - \varphi_{j}^{D} G_{n,j}^{CD} \eta_{j,n}^{D} )/(G_{n,i}^{CD} + \varphi_{j}^{D} G_{n,j}^{CD} Z_{j,i}^{DD} )\).

Proof

From either constraint in (12d), e.g., \(\gamma_{j,n}^{D} \ge \varphi_{j}^{D}\), we derive that \(p_{j,n}^{D} \ge \varphi_{j}^{D} (p_{i,n}^{D} Z_{j,i}^{DD} + \eta_{j,n}^{D} )\), and as the objective function in (12a) is positively proportional to \(p_{j,n}^{D}\), the optimal is achieved when \(p_{j,n}^{D} = \varphi_{j}^{D} (p_{i,n}^{D} Z_{j,i}^{DD} + \eta_{j,n}^{D} )\), i.e., the optimal \(p_{j,n}^{D}\) has a direct link with the optimal \(p_{i,n}^{D}\), therefore P5 can be transformed into the one only pertinent to \(p_{i,n}^{D}\) by substituting \(p_{j,n}^{D}\) by \(\varphi_{j}^{D} (p_{i,n}^{D} Z_{j,i}^{DD} + \eta_{j,n}^{D} )\) and further ensuring \(p_{j,n}^{D} \le p_{j,\hbox{max} }^{D}\), so \(p_{i,n}^{D} \le A_{3}\). And from \(\gamma_{i,n}^{D} \ge \varphi_{i}^{D}\), we obtain \(A_{1} p_{i,n}^{D} \ge A_{2} > 0\), so (i) if \(A_{1} \le 0\), the SINR thresholds of both D-Ls can’t be achieved in the meantime as required in (12d), thus P5 is infeasible; (ii) otherwise, \(p_{i,n}^{D} \ge A_{2} /A_{1}\), thus \(A_{2} /A_{1} \le p_{i,n}^{D} \le \hbox{min} \{ A_{3} ,A_{4} ,p_{i,\hbox{max} }^{D} \}\) needs to be achieved combining (12b) and (12c), so P5 is still infeasible when \(A_{2} /A_{1} > \hbox{min} \{ A_{3} ,A_{4} ,p_{i,\hbox{max} }^{D} \}\), i.e., SINR thresholds of the two D-Ls are maintained at the violation of (12b) or (12c).□

Then we give the definition of independent set (IS), followed by Proposition 3 to shed some light on SC maximization under Assumption 1, which is indeed impractical but helps the design and understanding of our AC algorithm.

Definition 2

Given an undirected graph model \(G_{n} = (V_{n} ,E_{n} )\), a subset of nodes \(I \subseteq V_{n}\) is an IS if for \(\forall i \in I,(i,j) \notin E_{n} ,\forall j \in I - \{ i\}\), i.e., there is no edge between any two nodes in \(I \subseteq V_{n}\), and the IS with the largest cardinality is called the maximum independent set (MIS).

Assumption 1

\(S_{n} \in F_{n}\) if \((i,j) \in F_{n} ,\forall i,j \in S_{n} ,i \ne j\), i.e., the feasibility check is only accounted among every pair of D-Ls in \(S_{n}\) while omitting the accumulative effect when multiple D-Ls are involved.

Proposition 3

To achieve the optimal \(S_{n}^{*} = argmax_{{S_{n} \in F_{n} }} |S_{n} |\) or the optimality to P3 is equivalent to derive the MIS of our graph model \(G_{n} = (V_{n} ,E_{n} )\) under Assumption 1.

Proof

Under Assumption 1, \(S_{n}\) is a feasible set if \(\{ i\} ,\{ j\} \in F_{n} ,\{ i,j\} \in F_{n} ,\forall i,j \in S_{n} ,i \ne j\), i.e., \((i,j) \ne E_{n} ,\forall i,j \in V_{n} ,i \ne j\), thus the set of D-Ls in feasible set \(S_{n}\) is an IS under our graph formulation by Definition 2, and to maximize its cardinality, we are to find the MIS in \(G_{n} = (V_{n} ,E_{n} )\).□

Remark

The MIS problem has proven to be NP-hard, and an efficient greedy scheme is provided in [34, Chapter 2.1.2] to approximate to the optimality in an iterative manner. We apply it in our graph formulation as articulated in Table 1 (Algorithm 1), and the vertex selection rule in each iteration (Assignment section) provides us a metric to assess which D-L is more favorable to be admitted into the system and has its physical meaning. Specifically, the degree of a vertex, i.e., \(D(i)\), indicates the number of originally admissible D-Ls which can no longer get admitted due to the access of the D-L the vertex stands for, thus the vertex with a smaller degree is more favorable to get admitted to benefit SC maximization. And if there are ties, the vertex selection rule is switched to the optimal objective function in P4 and facilitates the subsequent optimization of system-wide metrics. Once a D-L is added into \(S_{n}\), its neighbor nodes will have no chance to get admitted and removed from graph (Updating section). Besides, the worst-case complexity of Algorithm 1 is in the order of \(O(M + \left( {\begin{array}{c} M \\ 2 \\ \end{array} } \right) + \sum\nolimits_{{k = 1}}^{M} {(M - k + 1)} ) = O(M^{2} )\) when \(V_{n} = D,E_{n} = \emptyset\), where the first two parts are for vertex and edge formulation in initiation, while the last is for the iterative process when all D-Ls are finally admitted, and \(M - k + 1\) is the complexity to find the most favorable D-L by vertex selection rule in the k-th iteration.

Table 1 Our AC scheme based on static graph formulation (Algorithm 1)
Full size table

Unfortunately, the output set from Algorithm 1, i.e., \(S_{n}\), is in general infeasible even if it is the optimal MIS. For instance, we consider a possible graph formulation: \(V_{n} = \{ 1,2,3,4\} ,E_{n} = \emptyset\), i.e., \(\{ 1,2\} ,\{ 1,3\} ,\{ 1,4\} ,\{ 2,3\} ,\{ 2,4\} ,\{ 3,4\} \in F_{n}\), but every triple can’t coexist, i.e., \(\{ 1,2,3\} ,\{ 1,2,4\} ,\{ 1,3,4\} ,\{ 2,3,4\} \notin F_{n}\). By Algorithm 1, all D-Ls can get admitted as shown in Fig. 1a, thus results in infeasibility and calls for additional design of user removal [35]. Taking the above downside into account, we are supposed to consider the impact of the D-Ls admitted in previous iterations in evaluating the feasibility check in the current iteration, i.e., the graph should be “dynamically” adjusted with the gradual admission of D-Ls rather than “statically” staying unchanged. So, after the first iteration, i.e., D-L 1 is admitted, an edge should be formulated between each pair of the remaining vertices as illustrated in Fig. 1b, i.e.,\(\{ 2,3\} ,\{ 2,4\} ,\{ 3,4\}\), thus further admission of any D-L in \(\{ 2,3,4\}\), i.e., \(\{ 2\}\), will cancel out the admission opportunity of the rest two, i.e., \(\{ 3\} ,\{ 4\}\) as \(\{ 1,2,3\} ,\{ 1,2,4\} \notin F_{n}\).

Fig. 1
figure 1

AC process based on static (Algorithm 1, Fig. 1a) and dynamic graph formulation (Fig. 1b)

Full size image
3.1.1.2 Dynamic Graph Formulation

In order to include the impact of previously admitted D-Ls when evaluating the feasibility check in current iteration, both vertices and edges need to be updated upon each admission as inspired from Fig. 1. Without loss of generality, we denote the current iteration as \(t\), and the set of D-Ls admitted during previous iterations as \(S_{n} (t)\), then the vertex and edge formulation rule can be specified below and addressed by Propositions 4 and 5, respectively.

The vertex formulation rule 2 (VF-R2) \(i \in V_{n} (t)\) if the optimal objective function in Problem 6 (P6) satisfies \(\gamma_{i,n}^{D*} \ge \varphi_{i}^{D}\), and compared to VF-R1, the impact of D-Ls in \(S_{n} (t)\) is considered in P6.

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 6:}} & \max_{{p_{i,n}^{D} ,p_{j,n}^{D} ,\forall j \in S_{n} (t)}} & \gamma_{i,n}^{D} = {\kern 1pt} p_{i,n}^{D} \big/\left(\sum\nolimits_{{k \in S_{n} (t)}} {p_{k,n}^{D} Z_{i,k}^{DD} } + \eta_{i,n}^{D}\right), & (a)\\ & \mathrm{s.t.} & 0 \le p_{k,n}^{D} \le p_{k,\hbox{max} }^{D} ,\forall k \in S_{n}\left(t\right) \cup \{ i\}, & (b)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C}, & (c)\\ & & {\kern 1pt} \gamma_{j,n}^{D} \ge \varphi_{j}^{D} ,\forall j \in S_{n}\left(t\right). & (d) \end{array}$$
(13)

Proposition 4

P6 is concave in logarithmic change of variables \(p_{l,n}^{D} ,\forall l \in S_{n} (t) \cup \{ i\}\) , and when optimal, \(\gamma_{j,n}^{D*} = \varphi_{j}^{D} ,\forall j \in S_{n} (t)\) and \(p_{i,n}^{D*}\) takes its maximum allowable value, i.e., at least one of the following conditions are satisfied: (i) \(\exists l \in S_{n} (t) \cup \{ i\} ,p_{l,n}^{D*} = p_{l,\hbox{max} }^{D}\); (ii) \(\sum\nolimits_{{l \in S_{n} (t) \cup \{ i\} }} {p_{l,n}^{D*} G_{n,l}^{CD} } = Q_{n}^{C}\).

Proof

P6 can be equivalently switched into the one in (14), i.e., to minimize a posynomial [36, Chapter 2.1.1] under upper bound constraints on posynomials, thus is a geometric programming (GP) [36]. By the properties of GP, the problem in (14) is convex in the logarithmic change of variables, so P6 is (log, x)-concave in \(p_{l,n}^{D} ,\forall l \in S_{n} (t) \cup \{ i\}\). Besides, we can further characterize the optimality of P6 by its feature. From (13a), \(\gamma_{i,n}^{D}\) is strictly decreasing in \(p_{j,n}^{D} ,\forall j \in S_{n} (t)\), and when combined with (13d), \(p_{j,n}^{D} ,\forall j \in S_{n} (t)\) have a lower bound to maintain \(\varphi_{j}^{D}\), thus \(\gamma_{i,n}^{D*}\) is achieved when \(\gamma_{j,n}^{D*} = \varphi_{j}^{D} ,\forall j \in S_{n} (t)\). So we have \({\mathbf{p}}_{{S_{n} (t)}} = ({\mathbf{E}}_{{S_{n} (t)}} - {\mathbf{D}}({\varvec{\varphi }}_{{S_{n} (t)}} ){\mathbf{Z}}_{{S_{n} (t)}} )^{ - 1} {\mathbf{D}}({\varvec{\varphi }}_{{S_{n} (t)}} ){\varvec{\uppsi}}_{{S_{n} (t)}}\) from (2), where all matrices are defined similarly to those in (2) only by replacing \(S_{n}\) with \(S_{n} (t)\), and \({\varvec{\uppsi}}_{{S_{n} (t)}} = {\varvec{\upeta}}_{{S_{n} (t)}} + p_{i,n}^{D} {\mathbf{B}}_{{\mathbf{1}}}\) and \({\mathbf{B}}_{{\mathbf{1}}}\) is the vector of \(Z_{j,i}^{DD} ,\forall j \in S_{n} (t)\), thus \(p_{j,n}^{D*} ,\forall j \in S_{n} (t)\) are functions in \(p_{i,n}^{D*}\), and the objective function can be switched into the one only pertinent to \(p_{i,n}^{D}\). Then, we derive the first-order derivative of (13a) in (15), and the numerator can be reduced to \({\mathbf{B}}_{{\mathbf{2}}}^{T} ({\mathbf{E}}_{{S_{n} (t)}} - {\mathbf{D}}({\varvec{\varphi }}_{{S_{n} (t)}} ){\mathbf{Z}}_{{S_{n} (t)}} )^{ - 1} {\mathbf{D}}({\varvec{\varphi }}_{{S_{n} (t)}} ){\varvec{\upeta}}_{{S_{n} (t)}} + \eta_{i,n}^{D} > 0\), where \({\mathbf{B}}_{{\mathbf{2}}}\) is the vector of \(Z_{i,j}^{DD} ,\forall j \in S_{n} (t)\), thus \(\gamma_{i,n}^{D}\) is monotonically increasing in \(p_{i,n}^{D}\), and \(\gamma_{i,n}^{D*}\) is achieved on the upper bound of \(p_{i,n}^{D}\), i.e., at least one of the conditions in (i) and (ii) are satisfied combined with the constraints in (13b) and (13c).□

$$\begin{array}{clr} \min_{{p_{i,n}^{D},p_{j,n}^{D},\forall j \in S_{n}\left(t\right)}} & 1/\gamma_{i,n}^{D} = \left(\sum\nolimits_{{k \in S_{n} (t)}} {p_{k,n}^{D} Z_{i,k}^{DD} } + \eta_{i,n}^{D} \right)/p_{i,n}^{D}, & (a)\\ \mathrm{s.t.} & 0 \le p_{k,n}^{D} \le p_{k,\hbox{max} }^{D} ,\forall k \in S_{n}\left(t\right), & (b)\\ & \sum\nolimits_{{l \in S_{n} (t) \cup \{ i\} }} {p_{l,n}^{D} G_{n,l}^{CD} } \le Q_{n}^{C}, & (c)\\ & \varphi_{j}^{D} \left(\sum\nolimits_{k \in S_{n} (t) \cup \{ i\} \atop k \ne j} {p_{k,n}^{D} Z_{j,k}^{DD} } + \eta_{j,n}^{D}\right)/p_{j,n}^{D} \le 1,\forall j \in S_{n}\left(t\right). & (d) \end{array}$$
(14)
$$\frac{{\partial \gamma_{i,n}^{D} }}{{\partial p_{i,n}^{D} }} = \frac{{\sum\nolimits_{{k \in S_{n} (t)}} {p_{k,n}^{D} Z_{i,k}^{DD} } + \eta_{i,n}^{D} - p_{i,n}^{D} \sum\nolimits_{{k \in S_{n} (t)}} {Z_{i,k}^{DD} \partial p_{k,n}^{D} /\partial p_{i,n}^{D} } }}{{\left(\sum\nolimits_{{k \in S_{n} (t)}} {p_{k,n}^{D} Z_{i,k}^{DD} } + \eta_{i,n}^{D} \right)^{2} }}$$
(15)

Remark

Due to above monotonicity, we could resort to the bisection method to solve P6 instead of barrier method [37, Chapter 11.3], and \(\gamma_{i,n}^{D*}\) is within \([0,\gamma_{i,n}^{D*} (S_{n} (t) = \emptyset )]\), where \(\gamma_{i,n}^{D*} (S_{n} (t) = \emptyset )\) is the optimal SINR level by setting \(S_{n} (t) = \emptyset\) in P6, i.e., the optimal objective function in P4.

The edge formulation rule 2 (EF-R2) \((i,j) \in E_{n} (t)\) if the optimization problem in Problem 7 (P7) has no feasible solution, and compared to EF-R1, the impact of D-Ls in \(S_{n} (t)\) is considered in P7.

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 7:}} & \min_{{p_{l,n}^{D} ,\forall l \in S_{n}\left(t\right) \cup \{ i,j\} }} & \sum\nolimits_{{l \in S_{n} \left(t\right) \cup \{ i,j\} }} {p_{l,n}^{D} } & (a)\\ & \mathrm{s.t.} & 0 \le p_{l,n}^{D} \le p_{l,\hbox{max} }^{D} ,\forall l \in S_{n}\left(t\right) \cup \{ i,j\}, & (b)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C}, & (c)\\ & & \gamma_{l,n}^{D} \ge \varphi_{l,n}^{D} ,\forall l \in S_{n}\left(t\right) \cup \{ i,j\}. & (d) \end{array}$$
(16)

Proposition 5

P7 in (16) has no feasible solution if either of the two following conditions is satisfied: (i) \(\rho ({\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\mathbf{Z}}_{{S_{n}^{'} (t)}} ) \ge 1\) , where \(S_{n}^{'} (t) = S_{n} (t) \cup \{ i,j\}\) , and \(\rho ( \cdot )\) is to derive the maximum eigenvalue of the matrix; (ii) \(\rho ({\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\mathbf{Z}}_{{S_{n}^{'} (t)}} ) < 1\) , and \(\exists k \in S_{n}^{'} (t),p_{k,n}^{D*} > p_{k,\hbox{max} }^{D}\) or \(\sum\nolimits_{{k \in S_{n}^{'} (t)}} {p_{k,n}^{D*} G_{n,k}^{CD} } > Q_{n}^{C}\) , where \({\mathbf{p}}_{{S_{n}^{'} (t)}}^{*} = ({\mathbf{E}}_{{S_{n}^{'} (t)}} - {\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\mathbf{Z}}_{{S_{n}^{'} (t)}} )^{ - 1} {\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\varvec{\upeta}}_{{S_{n}^{'} (t)}}\) , and above matrices are defined similarly to those in (2) only by replacing \(S_{n}\) with \(S_{n}^{'} (t)\).

Proof

We divide the feasibility check into two steps by Definition 1: (i) We first check if the SINR thresholds of all D-Ls in \(S_{n}^{'} (t)\) can be maintained within their local power budget, i.e., (16b) and (16d). By Perron-Frobenius theorem [7], there exists a positive power vector \({\mathbf{p}}_{{S_{n}^{'} (t)}}^{*}\), so that \(\gamma_{k,n}^{D} \ge \varphi_{k}^{D} ,\forall k \in S_{n}^{'} (t)\) only when \(\rho ({\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\mathbf{Z}}_{{S_{n}^{'} (t)}} ) < 1\), thus P7 is infeasible if \(\rho ({\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\mathbf{Z}}_{{S_{n}^{'} (t)}} ) \ge 1\), otherwise, above unique \({\mathbf{p}}_{{S_{n}^{'} (t)}}^{*} = \{ p_{k,n}^{D*} \}_{{k \in S_{n}^{'} (t)}}\) can be derived from (2) by replacing \(S_{n}\) with \(S_{n}^{'} (t)\), i.e., \({\mathbf{p}}_{{S_{n}^{'} (t)}}^{*} = ({\mathbf{E}}_{{S_{n}^{'} (t)}} - {\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\mathbf{Z}}_{{S_{n}^{'} (t)}} )^{ - 1} {\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\varvec{\upeta}}_{{S_{n}^{'} (t)}}\), and if \(\exists k \in S_{n}^{'} (t),p_{k,n}^{D*} > p_{k,\hbox{max} }^{D}\), P7 is also infeasible. (ii) We proceed to check if (16c) is satisfied on \({\mathbf{p}}_{{S_{n}^{'} (t)}}^{*}\), and if \(\sum\nolimits_{{k \in S_{n}^{'} (t)}} {p_{k,n}^{D*} G_{n,k}^{CD} } > Q_{n}^{C}\), P7 is still infeasible.□

Moreover, when all D-Ls pursue the same SINR threshold, i.e., \(\varphi_{l}^{D} = \varphi^{D} ,\forall l \in D\), the edge formulation rule can be simplified to EF-R3 below and addressed by Proposition 6.

The edge construction rule 3 (EF-R3) \((i,j) \in E_{n} (t)\) if the optimal objective function in Problem 8 (P8) satisfies \(minimize_{{k \in S_{n} (t) \cup \{ i,j\} }} \gamma_{k,n}^{D*} < \varphi^{D}\).

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 8:}} & \max_{{p_{l,n}^{D} ,\forall l \in S_{n}\left(t\right) \cup \{ i,j\} }} & \min_{{k \in S_{n} (t) \cup \{ i,j\} }} \gamma_{k,n}^{D} & (a)\\ & \mathrm{s.t.} & 0 \le p_{l,n}^{D} \le p_{l,\hbox{max} }^{D} ,\forall l \in S_{n}\left(t\right) \cup \{ i,j\}, & (b)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C}. & (c) \end{array}$$
(17)

Proposition 6

The optimization model in (17) is (log, x)-concave in \(p_{l,n}^{D} ,\forall l \in S_{n}^{'} (t) = S_{n} (t) \cup \{ i,j\}\) , and on optimality, \(\gamma_{l,n}^{D*} = \min_{{k \in S_{n} (t) \cup \{ i,j\} }} \gamma_{k,n}^{D*} ,\forall l \in S_{n}^{'} (t)\) and at least one of the following two conditions are satisfied: (i) \(\exists l \in S_{n}^{'} (t),p_{l,n}^{D*} = p_{l,\hbox{max} }^{D}\), (ii) \(\sum\nolimits_{{l \in S_{n}^{'} (t)}} {p_{l,n}^{D*} G_{n,l}^{CD} } = Q_{n}^{C}\).

Proof

P8 can be transferred into (18), where \(\min_{k} \gamma_{k,n}^{D}\) is substituted by a new variable \(\theta_{n}\), and falls into the framework of GP, and (log, x)-convex in \(p_{l,n}^{D} ,\forall l \in S_{n}^{'} (t)\), thus P8 is (log-x)-concave in \(p_{l,n}^{D} ,\forall l \in S_{n}^{'} (t)\). We can readily show that all SINR are equal and at least one of the conditions in (i) and (ii) is satisfied when optimal via contradiction, while the details are omitted for brevity.□

$$\begin{array}{clr} \min_{{p_{l,n}^{D} ,\forall l \in S_{n}^{'}\left(t\right)}} & 1/\theta_{n}, & (a)\\ \mathrm{s.t.} & 0 \le p_{l,n}^{D} \le p_{l,\hbox{max} }^{D} ,\forall l \in S_{n}^{'}\left(t\right), & (b)\\ & \sum\nolimits_{{l \in S_{n}^{'}\left(t\right)}} {p_{l,n}^{D} G_{n,l}^{CD} } \le Q_{n}^{C}, & (c)\\ & \theta_{n} \left(\sum\nolimits_{k \in S_{n}^{'} (t) \atop k \ne l} {p_{k,n}^{D} Z_{l,k}^{DD} } + \eta_{l,n}^{D} \right)\big/p_{l,n}^{D} \le 1,\forall l \in S_{n}^{'}\left(t\right). & (d) \end{array}$$
(18)

Remark

We can apply bisection method to derive the optimal SINR in (18) instead of using barrier method, and the optimality lies within \([0,\min_{{l \in \{ i,j\} }} \gamma_{l,n}^{D*} (S_{n} (t) = \emptyset )]\).

In what follows, we derive the AC algorithm based on dynamic graph formulation as shown in Table 2 (Algorithm 2). Compared to Algorithm 1, the graph is dynamically updated upon each admission (Step [iii] of Updating section). If EF-R2 is applied, its worst-case complexity is in the order of \(O(M + \left( {\begin{array}{*{20}c} M \\ 2 \\ \end{array} } \right) + \sum\nolimits_{{k = 1}}^{M} {[(M - k + 1) + (M - k)I_{{bis}}^{{P6}} + \left( {\begin{array}{*{20}c} {M - k} \\ 2 \\ \end{array} } \right)(k + 2)^{3} ]} = O(M^{2} I_{{bis}}^{{P6}} + M^{6} )\) when all D-Ls are admitted, where the first two items are the complexity in initiation, and the last is that of iteration. In the k-th iteration, \((M - k + 1)\) is the complexity of assignment section, and \((M - k)I_{bis}^{P6}\) is that of vertex updating of \(G_{n}\) with \(I_{bis}^{P6}\) being the maximum iterations required to solve P6 by bisection, while \(\left( {\begin{array}{*{20}c} {M - k} \\ 2 \\ \end{array} } \right)(k + 2)^{3}\) is that of edge updating of \(G_{n}\) with \((k + 2)^{3}\) being the complexity of matrix reversion of \({\mathbf{E}}_{{S_{n}^{'} (t)}} - {\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{'} (t)}} ){\mathbf{Z}}_{{S_{n}^{'} (t)}}\) in pursuit of \({\mathbf{p}}_{{S_{n}^{'} (t)}}^{*}\). If EF-R3 is applied, its worse-case complexity is in the order of \(O(M + \left( {\begin{array}{*{20}c} M \\ 2 \\ \end{array} } \right) + \sum\nolimits_{{k = 1}}^{M} {[(M - k + 1) + (M - k)I_{{bis}}^{{P6}} + \left( {\begin{array}{*{20}c} {M - k} \\ 2 \\ \end{array} } \right)I_{{bis}}^{{P8}} ]} ) = O(M^{2} I_{{bis}}^{{P6}} + M^{3} I_{{bis}}^{{P8}} )\) when all D-Ls are admitted, where \(I_{bis}^{P8}\) is the maximum iterations required to solve P8 by bisection.

Table 2 Our AC scheme based on dynamic graph formulation (Algorithm 2)
Full size table

3.1.2 Multi-channel Scenario

When multiple channels are available to be reused, the originally non-admitted D-Ls may get accessed into other channels. We adopt the same idea from single-channel case, and dynamically determine the admitted D-L and its assigned channel based on the degree information in the iteratively updated graph model. Unlike the case when only one channel is considered, the degree information is two-dimensional data when multiple channels are involved, which varies not only among different D-Ls, but also among different channels. Finally, we conclude our joint AC and CA mechanism in Table 3 (Algorithm 3), and its worst-case complexity is in the order of \(O(NM^{2} ) + \sum\nolimits_{n \in C} {\Delta (S_{n} )} \le O(NM^{2} ) + \Delta\) when all D-Ls are accessible and admitted into the same channel, where \(\Delta\) is the worst-case complexity of Algorithm 2, i.e., \(\Delta = O(M^{2} I_{bis}^{P6} + M^{6} )\) or \(\Delta = O(M^{2} I_{bis}^{P6} + M^{3} I_{bis}^{P8} )\), while \(\Delta (S_{n} )\) represents the complexity by replacing \(M\) with \(S_{n}\) in \(\Delta\).

Table 3 Our joint AC and CA scheme in multi-channel scenario (Algorithm 3)
Full size table

3.2 PC Optimization for the Enhancement of System-Wide Metrics

It is noteworthy that underlaid PC optimization is actually involved in the above joint design of AC and CA mechanism, i.e., the vertex and edge formulation rules. When all \(S_{n} ,\forall n \in C\) are determined and no more D-Ls can be admitted, we switch the optimization model of PC to enhance system-wide performance metric, i.e., EC, ST, EE and MI. Due to the orthogonality among different channels and the reuse limitation, i.e., \(\sum\nolimits_{m \in C} {x_{i,m}^{D} } \le 1,\forall i \in D\), the optimizations of global EC, ST and MI are reduced to the sub-problems on each channel except EE. Without loss of generality, we only consider the n-th channel, and the set of admitted D-Ls is \(S_{n}^{*}\) as the output of Algorithm 3.

3.2.1 When Optimizing EC

The optimization model is same with P7 only by switching \(S_{n} (t) \cup \{ i,j\}\) by \(S_{n}^{*}\), as the feasibility has been achieved during Algorithm 3, the optimal power is \({\mathbf{p}}_{{S_{n}^{*} }}^{EC*} = ({\mathbf{E}}_{{S_{n}^{*} }} - {\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{*} }} ){\mathbf{Z}}_{{S_{n}^{*} }} )^{ - 1} {\mathbf{D}}({\varvec{\varphi }}_{{S_{n}^{*} }} ){\varvec{\upeta}}_{{S_{n}^{*} }}\), and the complexity of this part mainly depends on the matrix reversion operation and is in the order of \(O(|S_{n}^{*} |^{3} )\), thus the sum complexity is \(O(\sum\nolimits_{n \in C} {|S_{n}^{*} |^{3} } ) \le O(M^{3} )\).

3.2.2 When Optimizing ST

The optimization model can be expressed as Problem 9 (P9) in (19), but P9 is in general non-convex and hard to be solved [7] except for some special cases when no more than two D-Ls are involved [13]. So, we weight the tradeoff between performance and complexity by assuming \(\varphi_{i}^{D} > > 1,\forall i \in S_{n}^{*}\), thus \(\log_{2} (1 + \gamma_{i,n}^{D} ) \approx \log_{2} (\gamma_{i,n}^{D} ),\forall i \in S_{n}^{*}\), which complies with the high QoS requirement in local communication [2,3,4], e.g., local file sharing, video streaming offloading. And the revised form of P9 becomes tractable and its optimality can be concluded in Proposition 7.

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 9:}} & \max_{{p_{i,n}^{D} ,\forall i \in S_{n}^{*} }} & \sum\nolimits_{{i \in S_{n}^{*} }} {\log_{2} \left(1 + \gamma_{i,n}^{D}\right)}, & (a)\\ & \mathrm{s.t.} & 0 \le p_{i,n}^{D} \le p_{i,\hbox{max} }^{D} ,\forall i \in S_{n}^{*}, & (b)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C}, & (c)\\ & & \gamma_{i,n}^{D} \ge \varphi_{i}^{D} ,\forall i \in S_{n}^{*}. & (d) \end{array}$$
(19)

Proposition 7

The revised form of P9 by replacing the objective function with \(\sum\nolimits_{{i \in S_{n} }} {\log_{2} (\gamma_{i,n}^{D} )}\) is (log, x)-concave in \(p_{i,n}^{D}\).

Proof

The objective function can be directly transformed into maximizing \(\log_{2} \prod\nolimits_{{i \in S_{n}^{*} }} {\gamma_{i,n}^{D} }\), and due to the monotonicity of logarithmic function, it is equivalent to minimize \(\prod\nolimits_{{i \in S_{n}^{*} }} {1/\gamma_{i,n}^{D} }\) as expressed in (20), which is also to minimize a posynomial under upper bound constraints on posynomials as (14), thus is (log, x)-convex in \(p_{i,n}^{D}\) [36], so the revised form of P9 is (log, x)-concave in \(p_{i,n}^{D}\).□

$$\begin{array}{clr} \min_{{p_{i,n}^{D} ,\forall i \in S_{n}^{*} }} & \prod\nolimits_{{i \in S_{n}^{*} }} {1/\gamma_{i,n}^{D} } = \prod\nolimits_{{i \in S_{n}^{*} }} {\left(\sum\nolimits_{k \in S_{n}^{*} \atop k \ne i} {p_{k,n}^{D} Z_{i,k}^{DD} } + \eta_{i,n}^{D} \right)\big/p_{i,n}^{D} } & (a)\\ \mathrm{s.t.} & 0 \le p_{i,n}^{D} \le p_{i,\hbox{max} }^{D} ,\forall i \in S_{n}^{*}, & (b)\\ & \sum\nolimits_{{i \in S_{n}^{*} }} {p_{i,n}^{D} G_{i,n}^{D} } \le Q_{n}^{C}, & (c)\\ & \varphi_{i}^{D} \left(\sum\nolimits_{k \in S_{n}^{*} \atop k \ne i} {p_{k,n}^{D} Z_{i,k}^{DD} } + \eta_{i,n}^{D} \right)/p_{i,n}^{D} \le 1,\forall i \in S_{n}^{*}. & (d) \end{array}$$
(20)

3.2.3 When Optimizing MI

The optimization model can be extended from P8 by replacing \(S_{n} (t) \cup \{ i,j\}\) by \(S_{n}^{*}\), and further impose the SINR protection for all admitted D-Ls, i.e., \(\varphi_{i}^{D} /\gamma_{i,n}^{D} \le 1,\forall i \in S_{n}^{*}\). Thus the proper of P8 remains, and the optimization of MI is still (log, x)-concave in \(p_{i,n}^{D}\), and could also be efficiently solved by bisection method, and the sum complexity can be denoted as \(O(N \cdot I_{bis}^{P8} )\).

3.2.4 When Optimizing EE

The optimization model can be expressed as Problem 10 (P10) in (21), and similar to P9, it is non-convex, but fortunately, we can show that it becomes tractable under the same assumption made in P9, i.e., \(\varphi_{i}^{D} > > 1,\log_{2} (1 + \gamma_{i,n}^{D} ) \approx \log_{2} (\gamma_{i,n}^{D} ),\forall i \in S_{n}^{*}\), as concluded in Proposition 8.

$$\begin{array}{lclr} \underline{{Problem{\kern 1pt} {\kern 1pt} {\kern 1pt} 10:}} & \max_{{p_{i,n}^{D} ,\forall i \in \cup_{n \in C} {\kern 1pt}{\kern 1pt}{\kern 1pt}S_{n}^{*} }} & \sum\nolimits_{n \in C} {\sum\nolimits_{{i \in S_{n}^{*} }} {\log_{2} \left(1 + \gamma_{i,n}^{D} \right)} } \big/\sum\nolimits_{n \in C} {\sum\nolimits_{{i \in S_{n}^{*} }} {p_{i,n}^{D} } } & (a)\\ & \mathrm{s.t.} & 0 \le p_{i,n}^{D} \le p_{i,\hbox{max} }^{D} ,\forall i \in S_{n}^{*} ,n \in C, & (b)\\ & & \gamma_{n}^{C} \ge \varphi_{n}^{C} ,\forall n \in C, & (c)\\ & & \gamma_{i,n}^{D} \ge \varphi_{i}^{D} ,\forall i \in S_{n}^{*} ,\forall n \in C. & (d) \end{array}$$
(21)

Proposition 8

The revised form of P10 by replacing \(\log_{2} (1 + \gamma_{i,n}^{D} )\) in (21a) with \(\log_{2} (\gamma_{i,n}^{D} )\) is (log, log)-concave in \(p_{i,n}^{D}\) , i.e., when taking logarithmic operation to the revised objective function in P10, it becomes (log, x)-concave in \(p_{i,n}^{D} ,i \in S_{n}^{*}\).

Proof

The above conclusion has been proved in [33] for CDMA-based systems, where all D-Ls are viewed on a same channel, so it can be directly extended to our scenario if we show P10 can be transformed into the single-channel case. To achieve this, we bring in the definition of new channel coefficients: (i) \({\mathbf{Z}}_{GL}\) is the global uniformed path gain matrix among D-Ls as shown in (22a), where \({\mathbf{\rm Z}}_{{S_{n}^{*} }}\) is the uniformed path gain matrix on the n-th channel as defined in (2) while the remaining unmarked elements are all 0. (ii) \({\varvec{\upeta}}_{GL}\) is global uniformed noise at D-Ls and defined as the concatenation of \({\varvec{\upeta}}_{{S_{n}^{*} }}\), i.e., \({\varvec{\upeta}}_{GL} = [{\varvec{\upeta}}_{{S_{1}^{*} }}^{T} ,{\varvec{\upeta}}_{{S_{2}^{*} }}^{T} , \ldots ,{\varvec{\upeta}}_{{S_{N}^{*} }}^{T} ]^{T}\). (iii) \({\varvec{\varphi }}_{GL}\) is global SINR threshold of D-Ls and defined as the concatenation of \({\varvec{\varphi }}_{{S_{n}^{*} }}\), i.e.,\({\varvec{\varphi }}_{GL} = [{\varvec{\varphi }}_{{S_{1}^{*} }}^{T} ,{\varvec{\varphi }}_{{S_{2}^{*} }}^{T} , \ldots ,{\varvec{\varphi }}_{{S_{N}^{*} }}^{T} ]^{T}\). (iv) \({\mathbf{Y}}_{GL}\) is the global cross-tier path gain matrix from D-Ls to C-Ls as shown in (22b), where \({\mathbf{Y}}_{{S_{n}^{*} }} = \{ G_{n,i}^{CD} \}_{{i \in S_{n}^{*} }}\) while the rest elements are all 0. In this way, the revised form of P10 can be equivalently transformed into (23), where \({\mathbf{p}}_{GL}^{D}\) is the concatenation of \(p_{k}^{D} ,\forall k \in \cup_{n \in C} S_{n}^{*}\). Compared to [33, Sect. III-A], we only consider the PC of D-Ls, and further impose \(N\) additional linear constraints, i.e., (23c), to maintain the QoS requirement of C-Ls, which will not affect the convexity of the original problem.□

$${\mathbf{Z}}_{GL} = \left( \begin{aligned} {\mathbf{Z}}_{{S_{1}^{*} }} \hfill \\ \hfill \\ \hfill \\ \hfill \\ \end{aligned} \right.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \begin{array}{*{20}c} {} \\ {{\mathbf{Z}}_{{S_{2}^{*} }} } \\ {} \\ {} \\ \end{array} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \begin{array}{*{20}c} {} \\ {} \\ \ddots \\ {} \\ \end{array} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left. \begin{aligned} \hfill \\ \hfill \\ \hfill \\ {\mathbf{Z}}_{{S_{N}^{*} }} \hfill \\ \end{aligned} \right)_{{\sum\nolimits_{n \in C}{\kern 1pt}{\kern 1pt} {|S_{n}^{*} |} \times \sum\nolimits_{n \in C} {\kern 1pt}{\kern 1pt}{|S_{n}^{*} |} }} (a);{\mathbf{Y}}_{GL} = \left( \begin{aligned} {\mathbf{Y}}_{{S_{1}^{*} }}^{T} \hfill \\ \hfill \\ \hfill \\ \hfill \\ \end{aligned} \right.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \begin{array}{*{20}c} {} \\ {{\mathbf{Y}}_{{S_{2}^{*} }}^{T} } \\ {} \\ {} \\ \end{array} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \begin{array}{*{20}c} {} \\ {} \\ \ddots \\ {} \\ \end{array} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left. \begin{aligned} \hfill \\ \hfill \\ \hfill \\ {\mathbf{Y}}_{{S_{N}^{*} }}^{T} \hfill \\ \end{aligned} \right)_{{N \times \sum\nolimits_{n \in C} {\kern 1pt}{\kern 1pt}{|S_{n}^{*} |} }} (b)$$
(22)
$$\begin{array}{clr} \max_{{p_{k}^{D} ,\forall i \in \cup_{n \in C} {\kern 1pt}{\kern 1pt}{\kern 1pt}S_{n}^{*} }} & \sum\nolimits_{{k \in \cup_{n \in C} {\kern 1pt}{\kern 1pt}{\kern 1pt}S_{n}^{*} }} {\log_{2}\left(\gamma_{k}^{D}\right)} \big/\sum\nolimits_{{k \in \cup_{n \in C} {\kern 1pt}{\kern 1pt}{\kern 1pt}S_{n}^{*} }} {p_{k}^{D} }, & (a)\\ \mathrm{s.t.} & 0 \le p_{k}^{D} \le p_{k,\hbox{max} }^{D} ,\forall k \in \cup_{n \in C} S_{n}^{*}, & (b)\\ & {{\mathbf{Y}}_{GL} {\mathbf{p}}_{GL}^{D} \le [Q_{1}^{C} ,Q_{2}^{C} , \ldots ,Q_{N}^{C} ]^{T}}, & (c)\\ & {\{ \gamma_{k}^{D} \}_{{k \in \cup_{n \in C} {\kern 1pt}{\kern 1pt}{\kern 1pt}S_{n}^{*} }} = {\mathbf{p}}_{GL}^{D} ./({\mathbf{Z}}_{GL} {\mathbf{p}}_{GL}^{D} + {\varvec{\upeta}}_{GL} ) \ge {\varvec{\varphi }}_{GL}}. & (d) \end{array}$$
(23)

Remark

The optimization models in Sects. 3.2.2 and 3.2.4 both turn out to be constrained convex optimizations, thus could be well approximated by barrier method in polynomial time, and the detailed analysis of above complexity has been given in [37, Chapter 11.3], so we don’t included here due to space limitation, and simply denote it as \(O(BM)\).

4 Numerical Results

We consider an isolated circular cell with the radius being 200 m, where BS is at cell center and all transmitters are uniformly distributed in the cell area, and each DR is uniformly distributed in the disk area of its corresponding DT with the radius being 20 m. We assume each UE and the BS is equipped with a single and omni-directional antenna with the processing gain being 14/0 dB for BS/UEs, and the path loss model is same with [17]. The power spectral density of received noise is −174 dBm/Hz, and the bandwidth of each channel is 180 kHz, while the noise figure is 5/9 dB for BS/UEs. We divide this section into two parts: (1) in part one, we focus on single-channel scenario to show the necessity to weight the performance tradeoff between SC or outage ratio and system-wide metric; (2) in part two, we compare our two-step mechanism with the literatures in multi-channel scenario, and observe the gain when dense spectral sharing is enabled and multiple radio resource variables are in elaborate cooperation.

In the single-channel scenario, we compare our scheme with greedy optimizations of system-wide performance metrics (without individual QoS protection), and a detailed explanation of all reference algorithms is given below: (1) Alg1: to greedily optimize ST; (2) Alg2: to greedily optimize EE; (3) Alg3: to greedily optimize MI; (4) Opt: to solve (9) by Gurobi, which is a commercial optimization solver for extremely complex problems including the mixed-integer linear programming. We first get the detailed individual performance on a specified topology with \({\mathbf{Z}}_{{S_{n} }} ,{\varvec{\upeta}}_{{S_{n} }} ,\{ G_{n,i}^{CD} \}_{{i \in S_{n} }}\) defined in (24), and \(M = 8,\varphi_{i}^{D} = \varphi^{D} = 20dB,\forall i \in D,\varphi_{n}^{C} = 10dB\). We then continue to observe variation in SC with change in \(M\) and \(\varphi_{n}^{C}\), respectively. In Fig. 2a, we fix \(\varphi_{n}^{C} = 10dB\) and change \(M\) from 5 to 15 with a step size of 1. In Fig. 2b, we fix \(M = 10\) and change \(\varphi_{n}^{C}\) from 10 to 20 dB with a step size of 1 dB. The final results in Fig. 2 are averaged over 1000 random topologies.

$$\begin{aligned}{\mathbf{Z}} & = \left( {\begin{array}{cccccccc} 0 & {0.00000} & {0.0000} & {0.0037} & {0.0000} & {0.0236} & {0.0000} & {0.0003} \\ {0.0000} & 0 & {0.0000} & {0.0000} & {0.0001} & {0.0000} & {0.0001} & {0.0001} \\ {0.0000} & {0.0000} & 0 & {0.0000} & {0.0000} & {0.0000} & {0.0000} & {0.0001} \\ {0.0001} & {0.0000} & {0.0000} & 0 & {0.0000} & {0.0001} & {0.0000} & {0.0000} \\ {0.0000} & {0.0001} & {0.0000} & {0.0000} & 0 & {0.0000} & {0.0002} & {0.0000} \\ {0.0928} & {0.0000} & {0.0001} & {0.0154} & {0.0000} & 0 & {0.0000} & {0.0004} \\ {0.0000} & {0.0000} & {0.0000} & {0.0000} & {0.0001} & {0.0000} & 0 & {0.0000} \\ {0.0004} & {0.0000} & {0.0008} & {0.0013} & {0.0000} & {0.0002} & {0.0001} & 0 \\ \end{array} } \right)(a)\\ {\varvec{\eta }} & = [0.0010,0.2552,0.0001,0.0000,0.0018,0.0017,0.0004,0.0015]^{T} (b) \\ \{ G_{{n,i}}^{{CD}} \} _{{i \in S_{n} }} & = [0.3215,3.3914,0.2410,0.2223,0.3233,0.1865,0.9957,1.8516]^{T} (c) \\ \end{aligned}$$
(24)
Fig. 2
figure 2

Performance comparison in single-channel scenario in terms of SC

Full size image

Alg1 is to take advantage of multiuser diversity, and the D-L with favorable channel condition, i.e., small \(Z_{i,j}^{D} ,\forall j \ne i,\eta_{i,n}^{D} ,G_{n,i}^{CD}\) for the i-th D-L, tends to reap a high SINR as shown in Table 4, i.e., D-L 3, 4, 5 and 7 achieve a SINR higher than \(\varphi^{D}\), and depicted in Fig. 2a, with the increase of \(M\), its performance in SC is raised as more multiuser diversity can be utilized. Compare to Alg1, Alg2 lays more emphasize on energy consumption, and though D-L 3, 4 and 7 still harvest a higher SINR than the rest, their performance is greatly reduced and only D-L 4 obtains a satisfied QoS experience. Different to Alg1 and Alg2, in Alg3, the D-L with unfavorable channel condition has to consume more powers to combat its disadvantage, i.e., D-L 2 in Table 4, thus shares a large quota from \(Q_{n}^{C}\) and imposes a strong interference to the rest D-Ls. Although its MI is the highest, no D-L achieves a satisfied SINR as \(7.5055dB < \varphi^{D} = 20dB\). In this sense, Alg3 suffers from multiuser diversity, and explains why its SC declines with the increase of \(M\) as shown in Fig. 2a. Compare to the above greedy optimization schemes, we further bring in individual QoS requirement into optimization model and strive to maximize SC. For the specified topology, our mechanism may suffer an inferior system-wide metric compared to Alg1–Alg3, i.e., when ST is set as the target, we achieve 63.2667 bps/Hz compared to 67.4613 bps/Hz of Alg1; when EE is set, we achieve 83.4721 bps/Hz/mW compared to 555.5234 bps/Hz/mW of Alg2; when MI is set, we achieve an unified SINR of 28.7328 dB with 2 D-Ls, i.e., D-L 2 and D-L 6, being silent compared to 7.5055 dB of Alg3 with all D-Ls being active, but we maximize SC as stressed in future user-centric radio communication system [5, 6]. Besides, compared to Opt, our mechanism only suffers a loss of 9.0668e−04 in SC on average with the change in \(M\). Moreover, with the increase of \(\varphi_{n}^{C}\), more restriction is imposed on power emission of D-Ls, thus impairs the SC of all algorithms as illustrated in Fig. 2b, but our mechanism still outweighs Alg1–Alg3 and only suffer a loss of 9.1386e−04 in SC on average with the change in \(\varphi_{n}^{C}\) when compared to Opt.

Table 4 Individual performance under different comparing algorithms
Full size table

In what follows, we proceed to observe the performance of our mechanism in terms of SC and system-wide metrics as shown from Figs. 3 to 4 in multi-channel scenario where \(M = 20,N = 3\), and compare it with the literatures when \(\varphi_{n}^{C}\) changes from 10 to 20 dB with a step size of 1 dB. A detailed description of the algorithms compared in this part is given below: (1) LIT1: the joint AC, PC and CA scheme for ST proposed in [17], and it is modeled as a bipartite matching, which is optimally solved by Kuhn-Munkres algorithm with the complexity being \(O(\hbox{max} (M,N)^{3} )\). It outweighs [13,14,15,16] in ST and can be further extended to optimize SC [16], EC and EE [18], but at most \(N\) D-Ls can get admitted. (2) LIT2: the joint PC and CA scheme for ST proposed in [19], and it could be relaxed to be convex and solvable in polynomial time. It is superior to [20, 21] in ST, but it omits QoS protection for D-Ls and at most \(N\) D-Ls can get admitted as LIT1. (3) LIT3: the interference graph-based CA scheme proposed in [28], and it is solved by sequential coloring algorithm with the complexity being \(O(M^{2} )\). (4) LIT4: another graph-based CA scheme raised in [29], which is modeled into the classic Max K-cut problem and well approximated by a greedy scheme with the complexity being \(O(M^{2} + N)\). (5) LIT5: the interference graph-based CA in [27], which is solved by an iterative process with the complexity being \(O(N^{3} + N^{2} M + NM^{2} )\). (6) O-EC: our two-step mechanism for EC, and it can be viewed as an extension of [24, 25] to multi-channel scenario and as an enhanced version of [30] with feasibility check and optimization of SC; (7) O-ST: our two-step mechanism for ST, and it suffers an inferior ST compared to the greedy scheme as shown in previous section, but it maintains polynomial-time complexity compared to [26] which is computational prohibited in practice; (8) O-EE: our two-step mechanism for EE, and it can be viewed as an extension of [31, 33] to include CA and feasibility check, besides, it avoids the high complexity in [32]; (9) O-MI: our two-step mechanism for MI, which has not been addressed in literatures. In LIT3-LIT5, we set \(p_{i,n}^{D} = 10mW,\forall i \in D\) to facilitate the formulation of interference-based graph, and when CA is determined, we further set \(p_{i,n}^{D} = Q_{n}^{C} /|S_{n} |/G_{n,i}^{CD} ,\forall i \in S_{n}\) to maintain the QoS requirement of C-Ls, making them comparable to ours. Besides, we set \(\varphi_{i}^{D} = \varphi^{D} = 20dB,\forall i \in D\) and the final results are averaged over 1000 random topologies.

Fig. 3
figure 3

Performance comparison in multi-channel scenario in SC and ST

Full size image
Fig. 4
figure 4

Performance comparison in multi-channel scenario in EC, EE and MI

Full size image

Illustrated in Fig. 3, compared to LIT1 and LIT2, the remaining ones enable one channel to be reused by multiple D-Ls and greatly enhance ST even under a different optimization target, i.e., O-EC, O-EE, and O-MI. And compared to the conventional interference graph-based schemes in LIT3–LIT5, we further incorporate AC and PC into the design of CA, i.e., the dynamic graph formulation with feasibility check, thus harvest the highest SC as depicted in Fig. 3a. Besides, it is noteworthy that LIT4–LIT5 enable all D-Ls to transmit and may achieve a higher ST than O-ST as shown in Fig. 3b, but it comes at the cost of a higher service outage ratio, a worse EC and a lower EE with Fig. 4, which results from the vacancy of AC and PC. As LIT1 and LIT2 keep all admitted D-Ls free from mutual interference, they reap the highest MI with the largest power consumption when combining Fig. 4a, c. In addition, with the increase of \(\varphi_{n}^{C}\), more restriction is imposed on the power emission of D-Ls, thus impairs the SC, ST and MI of all algorithms, but EC and EE of all algorithms increase as mutual interference is reduced with the decrease in the number of co-channel D-Ls. So, we can speculate that the scheme in [22] and the ones in [18, 23] will outweigh our O-EC and O-EE in terms of EC and EE, respectively, but their gain comes at substantial loss in terms of SC. In Fig. 3a, when \(\varphi_{n}^{C} = 20dB\), we achieve a SC of 14.6800, which is 4.8933 times of the largest SC of [18, 22, 23], i.e., \(N = 3\). The above comparison is similar to that between LIT1/LIT2 and O-ST in terms of MI and SC, so we leave out the details of above three schemes in Fig. 3 and Fig. 4 due to space limitation. Moreover, we observe the performance tradeoff among different system-wide performance metrics. O-EC achieves the minimum energy consumption at the cost of the lowest ST within our four algorithms, while O-ST just does the opposite. O-EE weights their tradeoff: It improves EC compared to O-ST and enhances ST compared to O-EC, and the performance of O-EC in EE is approximate to O-EE from Fig. 4b. Besides, O-MI achieves the highest MI at certain loss in the utilization of multiuser diversity, thus suffers a lower ST than O-ST and larger energy consumption than O-EC and O-EE.

5 Conclusion

In this paper, we attempt to weight the performance tradeoff between system-wide metric and SC for underlaid D2D communication with additional QoS protection for prioritized C-Ls via joint consideration of AC, PC and CA. Unfortunately, the original problem is non-trivial to be solved, so we decompose it into two parts and propose a two-step mechanism accordingly: (1) a graph-based joint AC and CA scheme is devised to maximize SC or minimize outage ratio; (2) PC is further performed among admitted D-Ls for supreme system-wide metric. With the help of simulations, we demonstrate the necessity to weight our performance tradeoff, and specifically, our graph-based AC and CA mechanism greatly outweighs greedy optimizations of system-wide metrics in terms of SC, and achieves polynomial-time complexity at minor performance loss compared to the optimality derived by professional optimization toolbox. Besides, we observe the potential gain when one channel is enabled to be reused by multiple D-Ls compared to [13,14,15,16,17,18,19,20,21,22,23], and show the advantage when multiple resource allocation variables are in elaborate cooperation compared to [13,14,15,16, 20, 21, 24,25,26,27,28,29, 31, 33]. In the future, we would like to study another tradeoff between performance and signaling overhead as inspired by the distributed schemes in [30, 31].