Uplink Resource Allocation for Multi-Cluster Internet-of-Things Deployment Underlaying Cellular Networks

Abstract

Internet-of-Things (IoT) deployment underlaying cellular communication have been drawing increasing attention in recent years. In this work, we consider Device-to-Device (D2D) communication technology for enabling uplink transmission in multiple IoT groups/clusters at which the resource block (RB) of each cellular user is reused by multiple IoT devices (IoTDs). Joint resources and power allocation optimization problem is formulated for maximizing both the IoTDs connectivity and cell throughput under an interference constraint. A heuristic algorithm, namely greedy iterative matching (GIM), is proposed as a sub-optimal solution for the resource allocation problem while a fixed-power margin technique is used for the cellular users’ power allocation. Simulations results show that the proposed GIM algorithm provides enhanced cell throughput gain and accessibility to IoTDs. The proposed reuse model is applicable in a network at which the number of IoTDs deployed within multiple groups is larger than the available cellular reuse partners.

1 Introduction

Internet of Things (IoT) has emerged as a promising technology for a fully connected world through which billions of objects such as sensors, machines, vehicles, and other devices to be connected to the Internet [27]. The ultimate goal for such massive connectivity is to improve utilization, enhance process efficiency, and introduce new business models in every aspect of life such as smart grids, health and environmental monitoring, security, and intelligent transportation systems [34]. Over 60 percent of IoT applications, including machine-type communication (MTC), have many unique features such as low power, short-range, long battery life, massive connectivity, and wide coverage. However, existing wireless technologies, such as Bluetooth, Wi-Fi, and ZigBee do not well support such features [10]. Recently, different technologies are introduced to support the IoT deployment especially underlaying the existence of cellular networks such as Narrow-Band Internet-of-Things (NB-IoT). NB-IoT is a promising emerging low-power, wide-area (LPWA) technologies that are released by the Third Generation Partnership (3GPP), and is adapted by Ericsson, Nokia, and Huawei as part of the fifth generation (5G) wireless systems [16]. The main noticeable feature of NB-IoT is the compatibility with existing Long-Term Evolution (LTE) functionalities, which facilitate the coexistence of such IoT deployment using existing infrastructure [16, 24]. However, a large number of devices in IoT systems yields tremendous traffic pressure and congestion in the network, which imposes critical challenges to the coexistence of NB-IoT and cellular systems.

In order to address such challenges, a combination of 5G heterogeneous network architecture [25, 35], low power transmission, and device-to-device (D2D) communication [14] features are expected to provide feasible solutions to such challenges. By offloading traffic through nearby small cells (or gateways), IoT devices can effectively reduce the power consumption and guarantee the throughput requirement and quality of service (QoS) of IoT systems. With the appropriate signaling protocols, the small-cell gateways could aggregate traffic from a large number of low-power IoT devices (IoTDs) into the existing cellular networks.

In D2D technology, communication between nodes in close proximity to each other is performed without passing the messages through the macro base station, or the evolved Node Base station (eNB). The direct D2D communication introduces benefits for the network such as lower energy consumption due to short range transmission, load balancing, traffic offloading, and better coverage for edge users [3, 14]. In order to support the operation of D2D communication, two modes are defined in LTE networks, namely the dedicated mode, known as overlay, and the reuse mode [13], known as underlay. In dedicated mode, D2D nodes share the available cellular spectrum with orthogonal sharing (i.e. a part of the available radio resources is dedicated for D2D nodes).

On the other hand, D2D nodes in the underlay cellular communication mode reuse the same resources of users’ equipment (UEs) under control of the base station [22, 37] in a non-orthogonal way, which provides efficient utilization of the available spectrum to support more users in the system. Hence, the spectrum efficiency, as well as the network throughput, can be increased under a controlled interference from D2D communication. Moreover, this type of non-orthogonal resources sharing offers different types of gains [22] such as proximity gain, hop gain, reuse gain, and pairing gain. However, interference management is needed to guarantee successful detection of the simultaneously transmitted signals at the destinations in this mode [2]. There are different resource allocation methods in D2D communication underlaying cellular networks that are described in [22, 33]. In this work, we exploit D2D reuse mode for enabling IoT devices to upload messages to a gateway by sharing the resources of a group of cellular users while guaranteeing the target rate for both UE and IoT devices.

The success of such heterogeneous architecture assuming an interplay between IoT systems and D2D communication necessitates careful resource management, power allocation, and transmission scheduling which is generally non-deterministic polynomial-time hard (NP-hard) problems [3, 10, 11]. It is worth noting that the process of resource sharing in D2D and machine to machine (M2M) networks are investigated from different perspectives in order to optimize various performance metrics and enable different applications [3, 5, 6, 10,11,12, 17,18,19,20, 23, 28, 29, 31, 32]. In the context of this work, we summarize a survey report in Table 1, which compares a group of optimization problems in terms of deployment scenario, objective, optimization variables, and the used algorithm.

Table 1 Different optimization problems

The authors in [19] considered a successive convex approximation to solve a joint rate and power control problem that maximizes the network utility subject to the capacity and the primary user (PU) outage constraints in multi-hop cognitive radio networks (CRNs). By targeting a high-performance video streaming, the authors in [32] exploited D2D helper-requester pairs for achieving a high quality of experience (QoE) at high energy efficiency (EE) taking into consideration the co-channel interference over D2D communications in 5G networks. Similarly, the authors in [31] proposed a joint caching and downlink resource sharing optimization framework to efficiently deliver multimedia contents to the mobile users in a wireless multimedia sensor networks (WMSNs). Additionally, the EE maximization has recently gained a lot of attention for different networks architectures. In those schemes, the EE is targeted alone or as a joint objective with other performance metrics such as latency, sum rate maximization, etc. [17, 18, 28, 29]. The authors in [17] investigated different resource allocation schemes for EE maximization for various wireless networks. The authors in [5] investigated a sum-rate maximization problem for simultaneous spectrum access of M2M and human-to-human (H2H) communications in uplink multi-cluster underlaying cellular communication. In [6], the authors considered the dynamic allocation for M2M using a proportional integral derivative (PID) controller to mitigate M2M interference on H2H communication under data rate and fairness constraints.

In [11], the authors proposed a two time-slots downlink transmission protocol for ultra-reliable and low latency communication (URLLC) between the base station (BS) and a group of clustered IoT devices (IoTDs) within a factory system. The proximity service of D2D communication is used as a means for delivering a short-range reliable transmission mechanism from a cluster-head to IoTDs in the second time-slot. The authors in [10] adopted D2D communication technique as a mean of route extension of NB-IoT systems. In [20], the authors proposed a social-aware group formation framework to allocate resource blocks (RBs) effectively in NB-IoT solution. The authors in [3, 23] proposed resource allocation protocols to provide the required connectivity between a group of IoTDs and its associated cluster-head using D2D communication underlaying LTE networks for uplink transmission. In [12], the authors proposed a multi-antenna transceiver design and multi-hop D2D communication to guarantee reliable transmission and extend the unmanned aerial vehicles (UAV) coverage for IoT in disasters.

In this work, we consider the D2D communication technique for enabling a multi-cluster IoT deployment at which multiple groups of IoTDs are uniformly deployed in the vicinity of K cluster heads devices that works as a gateway/small-cell for the entire cluster. Each IoTD is allowed to reuse the RB of one UE for uplink transmission while the RB of each cellular user can be shared by one IoTD from each IoT group (IoTG) provided that all reuse partners can achieve their pre-defined quality-of-service (QoS) requirements. The proposed optimization problem is formulated for maximizing both the IoTDs connectivity and cell throughput under a fixed power-margin interference management scheme that is used for the cellular users’ power allocation.

By carefully allowing IoT devices to share the cellular resources, the spectrum efficiency, in terms of the total network throughput, is maximized while guaranteeing QoS. In spite of the fact that we do not investigate EE in this work, the proposed algorithm can intuitively improve the EE by limiting the transmit power of the admitted IoTDs in order to satisfy the interference constraints. This means that the admitted IoTDs are the group that can achieve QoS requirements with a low-power transmission. The major contributions in this work are listed as follows:

• Investigate the throughput and access rate for a single-cell scenario with a multiple-clusters of IoT devices under a fixed power-margin interference management scheme.

• Propose joint resources and power allocation optimization problem for maximizing both the IoTDs connectivity and cell throughput.

• A sub-optimal heuristic algorithm, namely greedy iterative matching (GIM), is proposed as a low-complexity sub-optimal solution for the resource allocation problem.

• Simulations results show that the proposed GIM algorithm provides enhanced cell throughput gain and accessibility for IoTDs compared to single IoT cluster in [3].

The rest of the paper is organized as follows. In Section 2, we describe the system model while illustrating the QoS requirements. Then, we introduce the joint optimization problem formulation and the proposed sub-optimal algorithm in Section 3. In Section 4, the performance analysis of the proposed algorithm is analyzed. Finally, the paper is concluded in Section 5.

2 System model

In this work, we focus on a single-cell uplink scenario, as shown in Fig. 1. We consider a group of cellular users equipment (UEs), $\mathcal {M} = \{UE_{m} |m = 1,..., M\}$, that communicate with one BS in a traditional cellular mode. Each UE is assigned with one subcarrier with no interference among UEs.¹ There is a set of IoT gateway (IoT-GW) nodes, $\mathcal {K} = \{IoTG_{k} |k = 1,..., K\}$, deployed within the cell, which are surrounded by a group of uniformly distributed IoTDs within a disc of radius r_max around each GW. The number of IoTDs communicating with each GW is N, where all nodes are equipped with a single antenna.

Fig. 1

System model: Multi-cluster of IoT devices are reusing the cellular resources of M cellular users (UE) to communicate with multiple IoT-GWs for uplink transmission

We assume that ${h_{m}^{b}}$, $h_{m,k}^{g}$, $h_{n,k}^{b}$, and $h_{n,l,k}^{g}$ represent the channels between the m^th UE to BS, m^th UE to the k^th GW, n^th IoTD to BS, and n^th IoTD in the l^th IoTG to the k^th GW, respectively. We assume a distanced based path-loss model defined as $P_{\mu } =P_{\eta } L d_{\eta ,\mu }^{-\alpha }$, where P_η and P_μ are the transmit and received powers, respectively. d_η,μ is the distance between node η and node μ, α is the path-loss exponent and L is the path-loss constant. We also assume that the BS knows the locations of the users within the cell, and so perfect channel state information (CSI) is available at the BS whose responsibility is to pair the UEs and IoTDs and optimize the power allocations. Assume that at maximum one IoTD from each IoTG is allowed to share the resources of any UE ² provided that QoS requirements of all paired nodes are satisfied. In other words, each UE is willing to support more than one IoTD as reuse partners as long as they all can satisfy their QoS constraints assuming only one IoTD from each group at maximum is permitted per UE.

Let ${x_{m}^{u}}$ and $x_{n,k}^{d}$ be the information symbols of the m^th cellular user UE_m and n^th IoT device IoTD_n in the k^th IoT group IoTG_k with the expectation $E\{|{x_{m}^{u}}|^{2}\} = 1$ and $E\{|x_{n,k}^{d}|^{2}\} = 1$. The received signals at the eNB and at the k^th IoT-GW on the m^th subcarrier, respectively are given by:

$$ {y_{m}^{b}} = \sqrt{P_{m}} {h_{m}^{b}} {x_{m}^{u}} + \displaystyle {\sum\limits_{k}^{K}}{\sum\limits_{n}^{N}} a_{m,n,k}\sqrt{P_{n,k}} h_{n,k}^{b} x_{n,k}^{d} + n_{b}, $$

(1)

$$ \begin{array}{@{}rcl@{}} y_{n,k}^{g} &=& \sqrt{P_{n,k}} h_{n,k,k}^{g} x_{n,k}^{d} + {\displaystyle\sum\limits_{n}^{N}} \sum\limits_{l\neq k}^{K} a_{m,n,l}\sqrt{P_{n,l}} h_{n,l,k}^{g} x_{n,l}^{d} \\&&+ \displaystyle \sqrt{P_{m}} h_{m,k}^{g} {x_{m}^{u}} + {n_{k}^{g}}, \end{array} $$

(2)

where P_m and P_n,k are the transmit powers of the m^th UE and the n^th IoTD in the k^th IoTG, respectively. n_b and ${n_{k}^{g}}$ are the additive white Gaussian noise (AWGN) at the eNB and the k^th IoT-GW, respectively with the same distribution $\mathcal {CN}(0,N_{o})$, where N_o is the noise power. a_m,n,k is a binary pairing coefficient which is given as follows:

$$ a_{m,n,k} = \left\{\begin{array}{ll} 1 &, \text{if RB of the } m^{th} \text{ UE is reused by the } n^{th} \text{ IoTD in the } k^{th} \text{ IoTG}, \\ 0 &, \text{otherwise}. \end{array}\right. $$

(3)

We assume that the destinations (i.e., eNB and the K IoT-GW) have certain QoS constraints, Γ_u and Γ_g, that need to be satisfied in order to correctly decode the received signals from the UE and the IoTDs. In order to consider sharing the same subcarrier between one UE and a K IoTDs (one IoTD from each IoTG at maximum), a fixed-power margin (FPM) interference management scheme is adapted [3, 8, 9]. In FPM scheme, the average received powers from all UEs at eNB are controlled to the same power level denoted by $P^{u}_{eNB}$. Therefore, based on the path-loss model, the transmit power of the m^th UE, P_m, is given by:

$$ \displaystyle P_{m} = \frac{P^{u}_{eNB}}{ L ({d_{m}^{b}})^{-\alpha}}. $$

(4)

A power margin in the signal-to-interference-plus-noise ratio (SINR) of the UE is assumed to protect the UE from excessive interference from the IoT reuse partners. This power margin (i.e., κ) is used by the eNB to determine: (1) The maximum allowable interference introduced by all paired IoTDs to avoid harmful interference to the UE. (2) The maximum power to be allocated to the IoTDs which can be derived by taking κ into account when calculating the signal-to-noise ratio (SNR) at eNB. If the IoTDs control their introduced interference perfectly, the UE achieves the required QoS (i.e., Γ_u) by scaling its own transmit power, P_m, by a factor of κ. In other words, in the absence of interference from the IoTDs, the UE link achieves κΓ_u signal-to-interference ratio (SIR), or SINR with zero interference, as follows:

$$ \displaystyle \frac{P^{u}_{eNB}}{N_{o}} \geq \kappa {\Gamma}_{u}, $$

(5)

where ($P^{u}_{eNB}= \kappa {\Gamma }_{u} N_{o}$) represents a lower bound on the received power at the BS from each UE. We consider the m^th UE to be a candidate partner for the K IoTDs only if the following QoS interference constraints are satisfied (${r_{m}^{u}} \geq {\Gamma }_{u}$ and $r_{n,k}^{d} \geq {\Gamma }_{g} \forall$ IoTDs paired with the UE) where ${r_{m}^{u}}$ and $r_{n,k}^{d}$ are the achievable SINR of the m^th UEs and the n^th IoTDs in the k^th IoTG which are given as follows, respectively:

$$ \displaystyle {r_{m}^{u}} = \frac{P_{eNB}^{u}}{{I_{m}^{u}} + N_{o}}, $$

(6)

$$ \displaystyle r_{n,k}^{d} = \frac{L (d_{n,k,k}^{g})^{-\alpha} P_{n,k}}{I_{n,k}^{d}+N_{o}}, $$

(7)

where ${I_{m}^{u}}$ and $I_{n,k}^{d}$ are the interference from all IoTDs that reuse the m^th UE subcarrier from all IoTGs, and the interference to the n^th IoTD on the k^th IoTG from the m^th UE and all other IoTDs from other groups, which are given as follows:

$$ {I_{m}^{u}} = {\displaystyle\sum\limits_{k}^{K}} {\sum\limits_{n}^{N}} a_{m,n,k} L (d_{n,k}^{b })^{-\alpha} P_{n,k}, $$

(8)

$$ I_{n,k}^{d} = {\displaystyle\sum\limits_{n}^{N}} \sum\limits_{l\neq k}^{K} a_{m,n,l} L (d_{n,l,k}^{g})^{-\alpha} P_{n,l} + L \left( \frac{d_{m,k}^{g}}{{d_{m}^{b}}}\right)^{-\alpha} \!P_{eNB}^{u}. $$

(9)

Now, we would like to find the upper-bound of the interference to the cellular user by considering the SINR QoS constraint (${r_{m}^{u}} = \frac {P_{eNB}^{u}}{{I_{m}^{u}}+N_{o}} \geq {\Gamma }_{u}$) where the upper bound is given as as follows:

$$ \displaystyle {I_{m}^{u}} \leq N_{o}(\kappa-1). $$

(10)

Hence, without losing generality, if we assume an equal transmit power level of all IoTDs assigned to the m^th UE, the IoTDs transmit power can be derived using (8) and (10) as follows:

$$ \displaystyle P_{n,k}^{m} =P_{d} \leq \frac{N_{o}(\kappa-1)}{{{\sum}_{k}^{K}} {{\sum}_{n}^{N}} a_{m,n,k} L (d_{n,k}^{b })^{-\alpha}}. $$

(11)

3 Resources allocation for IoTDs

The resource allocation in such underlay multi-cluster IoT network is a crucial process in optimizing the performance of the network. Therefore, suitable uplink resources allocation need to be controlled by eNB to manage the interference between UEs and IoTDs and between IoTDs themselves to achieve the QoS constraints for the admitted nodes. The author in [3], formulated an optimization problem that maximizes the achievable throughput gain in a single IoT group network where one IoTD is reusing the subcarrier of each UE. In the following sub-section, we formulate an optimization problem for supporting multiple IoT groups and we propose a low complexity suboptimal solution using a greedy iterative matching (GIM) algorithm.

3.1 Problem formulation

The objective of the proposed joint resource and power allocation problem is to find the sub-optimal transmit powers $\boldsymbol {P_{nk}} = \{P_{n,k}^{*}| \forall n \in \mathcal {N} \text {and} k\in \mathcal {K}\}$ and pairing coefficients $\{a_{m,n,k}^{*}\}$ of all admitted paired IoTDs that maximize the total cell throughput and achieve the QoS constraints for all nodes. The problem can be mathematically formulated as follows:

$$ \begin{array}{l} \displaystyle \underset{\boldsymbol{a_{m,n,k}}, \boldsymbol{P_{n,k}^{m}}}{\text{maximize}} T(\boldsymbol{a_{m,n,k}}, \boldsymbol{P_{n,k}^{m}}), \\ \displaystyle \text{subject to} C_{1} : {r_{m}^{u}} \geq {\Gamma}_{u}, \forall\ m \in \mathcal{M}, \\ \displaystyle \qquad \qquad C_{2} : r_{n,k}^{d} \geq {\Gamma}_{g}, \forall\ n \in \mathcal{N} \text{and} k\in \mathcal{K}, \\ \displaystyle \qquad \qquad C_{3} : a_{m,n,k} \in \{0,1\} \forall\ m,n,k, \\ \displaystyle \qquad \qquad C_{4} : {\sum\limits_{n}^{N}} a_{m,n,k} \le 1,\forall m\in \mathcal{M} \text{and} k\in \mathcal{K}, \\ \displaystyle \qquad \qquad C_{5} : {\sum\limits_{m}^{M}} a_{m,n,k} \le 1,\forall n\in \mathcal{N} \text{and} k\in \mathcal{K}, \\ \displaystyle \qquad \qquad C_{6}: P_{n,k}^{m} \le P_{d}^{max},\forall\ m,n,k, \end{array} $$

(12)

where

$$ T(\boldsymbol{a_{m,n,k}}, \boldsymbol{P_{n,k}^{m}}) = {\displaystyle\sum\limits_{m}^{M}} \log_{2}\left( 1+{r_{m}^{u}}\right) +{\displaystyle\sum\limits_{m}^{M}} {\sum\limits_{k}^{K}} {\sum\limits_{n}^{N}} a_{m,n,k} \log_{2}\left( 1+r_{n,k}^{d} \right). $$

(13)

Constraints C₁ and C₂ ensure the QoS of all UEs and admitted IoTDs. The pairing coefficients in C₃ is set to 1 if the RB of the m^th UE is assigned to the n^th IoTD in the k^th IoTG and 0 otherwise. Constraints C₄ are used to make sure that the maximum number of IoTDs in each IoTG reusing the subcarrier of any UE is one to avoid severe harmful interference between IoTDs within the same IoTG. Constraints C₅ are used to make sure that each IoTD is reusing only one UE. The group of constraints in C₆ is to limit the assigned powers to all IoTDs to the maximum allowed power level $P_{d}^{max}$. This resource allocation problem is a non-convex, mixed integer non-linear program. The complexity of an exhaustive search algorithm to solve this problem is $\mathcal {O}((ML)^{KN})$ and hence it is NP-hard for the large values of M, L, N, and L, where L is a finite set of available power levels.

3.2 Matching algorithm

In this sub-section, we try to shed light on the nature of the mixed integer non-linear program (MINLP) proposed in (12) in order to propose our solution. The proposed matching algorithm is a many-to-one matching at which multiple IoTDs (from different IoTGs) are allowed to be paired with one cellular user. Since there is only one IoTD from each IoTG is allowed to reuse the spectrum of each UE, there is at most N^K possible combinations for each UE to consider. This leads us to define an M × N^K cost matrix $E^{K} = [e_{m,c(v)}^{K}]$ whose element $e_{m,c(v)}^{K}$ represents the throughput achieved when the subcarrier of the m^th UE is shared with K IoTDs in the combination c(v). c(v) represents one possible combination out of the N^K possible combinations that consists of only one device from each IoTG and v is the index of this combination where v ∈{1,2,...,N^K}. The throughput element, $e_{m,c(v)}^{K}$, is given as follows:

$$ e_{m,c(v)}^{K} = \left\{\begin{array}{ll} TE_{m,c(v)}^{K} &, \text{if } {r_{m}^{u}} \geq {\Gamma}_{u} \text{ and } r_{n,k}^{d} \geq {\Gamma}_{g} \forall n, k \text{ in combination } c(v), \\ 0 &, \text{otherwise}, \end{array}\right. $$

(14)

where

$$ \begin{array}{@{}rcl@{}} &&TE_{m,c(v)}^{K} \!= \log_{2}\left( 1 + \frac{P_{eNB}^{u}}{N_{o}+L{{\sum}_{k}^{K}} {{\sum}_{n}^{N}} f_{n,k} (d_{n,k}^{b })^{-\alpha} P_{n,k}} \right)\\ &&+ {\displaystyle\sum\limits_{k}^{K}} {\sum\limits_{n}^{N}} f_{n,k}\log_{2}\left( 1 + \frac{L (d_{n,k,k}^{g})^{-\alpha} P_{n,k}^{m}}{N_{o}+I_{1} + L \left( \frac{d_{m,k}^{g}}{{d_{m}^{b}}}\right)^{-\alpha} P_{eNB}^{u}}\right), \end{array} $$

(15)

$$ I_{1}={\sum\limits_{n}^{N}} \sum\limits_{l\neq k}^{K} f_{n,l} L (d_{n,l,k}^{g})^{-\alpha} P_{n,l}, $$

and

$$ f_{n,k} = \left\{\begin{array}{ll} 1 &, \text{if } n, k \text{ exists in combination c(v)}, \\ 0 &, \text{otherwise}. \end{array}\right. $$

(16)

where f_n,k is a selector function that equals 1 when the n^th IoTD in the k^th IoT-GW is paired (i.e., exists in the combination c(v) for which the sum throughput is being calculated). For example, if we have K = 2 IoTGs with N = 2 IoTDs per group, the possible combinations of any UE will be c = {(1,1),(1,2),(2,1),(2,2)}, where $e_{m,c(1)}^{K} = e_{m,(1,1)}^{K}$, $e_{m,c(2)}^{K} = e_{m,(1,2)}^{K}$, and so on. Notice that all IoTDs are using the same transmit power level, $P_{n,k} = P_{n,l} = P_{n,k}^{m}$, given in (11). By inspecting the the elements of E^K, it is obvious that they are not unique in terms of the individual IoTDs since each IoTD appears in N combinations in each row. Consequently, the well-known weighted bipartite matching technique is not applicable as IoTDs will be paired with multiple UEs which violates C₅. Therefore, we propose a Greedy Iterative Matching algorithm (GIM) as shown in algorithm 1 which is introduced in the following sub-section.

3.3 Greedy iterative matching algorithm (GIM)

The GIM algorithm is proposed to provide a low complexity suboptimal solution of problem (12) iteratively by pairing the maximum allowable number of IoTDs with each UE (i.e., K IoTDs) in step 2 and 3 using the initial cost matrix E^k with k = K. In steps 4 to 7, we propose a greedy matching to get a sub-optimal solution that satisfies the constraint C₅ and guarantee the uniqueness of the set of IoTDs. We iteratively check the IoTDs used in best combination in E^k and match the UE in this best combination to the corresponding IoTDs. Then, we set all other elements in E^k to zero that use the same UE and IoTDs in Step 8. We also remove those nodes from the lists of unpaired nodes. If any UEs are still unpaired, this means that those UEs cannot afford the interference introduced by K IoTDs, i.e., the QoS constraints are violated. If any IoTDs are still unpaired, we iteratively repeat the process and try to pair a less number of IoTDs to the unpaired UEs until all UEs are paired or all IoTDs are paired.

A numerical example of the GIM algorithm is in Fig. 11 in Appendix where M = 4, K = 2 and N = 4. Hence, we start the GIM algorithm using the cost matrix E^K = E² where the number of rows equals to |U| = 4 and the number of columns equals to |I| = 4². In this example, maximum number of iterations is M = 4. For the first iteration, itr = 1, we search for the entry with the maximum value of throughput in the cost matrix which is $e^{k}_{m,c(v)} = e^{2}_{4,c(7)} = 39.42$, i.e., pairing UE₄ with IoTD₂ from IoTG₁ and IoTD₃ from IoTG₂. Then, in order to satisfy the design constraints in (12), we replace all entries that correspond to any of paired IoTDs and UE with zero (i.e., columns (2,1),(2,2),(2,3),(2,4),(3,3),(1,3) and (4,3)) in addition to the complete row number 4. In itr = 2, again search for the entry with the maximum value of throughput in E² which is $e^{2}_{2,(4,4)}=34.29$, i.e., pairing UE₂ with IoTD₄ from IoTG₁ and IoTD₄ from IoTG₂. Then, replace entries with zero, i.e., (1,4), (3,4), (4,4), (4,1), (4,2) in addition to row number 2. Repeat the same procedures in itr = 3 and itr = 4 and get $e^{2}_{3,(1,2)} = 28.59$ and $e^{2}_{1,(3,1)}=25.66$, respectively. Consequently, the final row in Fig. 11 shows the final greedy assignment matrix where each UE is paired with a pair of IoTDs where each combination consisted of 2 IoTDs with one device from each IoTG.

4 Performance analysis and numerical results

In all simulations, UEs and IoTDs are assumed to be uniformly distributed around eNB and IoTG, respectively. The Simulation parameters follow the IEEE WiMAX 2.1 (WIMAX 802.16e) standard which is compatible and inter-operable with time division (TD) LTE which are also adopted in [3, 4, 8] for cluster D2D models. Simulation parameters are listed in Table 2.

Table 2 System parameters

The performance of the proposed resources allocation algorithm is measured in terms of the total cell throughput gain and the accessibility of the IoTDs. The dimensions of the matching matrix E^K leads to a high complexity if an exhaustive search is used to find the best combination. Figure 2 shows the matching matrix dimension in log scale for a different number of IoTDs per each IoTG. The dimension is given by:

$$ D = M ({C_{j}^{N}} )^{K}, $$

(17)

where j is the allowed number of paired IoTDs per one IoTG for each UE and ${C_{j}^{N}}$ is the number of j combinations from N elements. The dimensions of the matching matrix increase exponentially with increasing number of IoTGs and also increasing number of paired IoTDs per each IoTG for each UE and hence, increases the computation complexity. Figure 2 shows the variation of D as a function of the number of IoTGs for different values of the permitted number of IoTDs to be paired with each UE from each IoTG (i.e., j). On the other hand, pairing only one IoTD from each IoTG for each UE (i.e., j = 1) has a significant increase in the throughput compared with the single cluster scenario in [3] with much less complexity than higher values of j. Therefore, we assume a pairing scheme where at most one IoTD from each IoTG is paired with each UE if the QoS constraints are satisfied. Notice that the dimension D increases also with the increasing number of IoTGs per cell.

Fig. 2

Exhaustive matrix dimensions in log scale vs. number of IoTGs for different values of the number of paired IoTDs/IoTG for each UE

Notice that the worst case computational complexity of the proposed algorithm can be written as:

$$ M N^{K}+\sum\limits_{i=1}^{M-2}\left( M N^{K}-i N^{K} - \left[\left( M - i\right)\left( 2\left( N - i\right)+1\right)\right]\right) $$

(18)

which can be reduced to $\mathcal {O}(M N^{k})$, where M is the number of cellular users, N is the number of IoT devices in each cluster, and K is the number of clusters.

In order to reduce the computation complexity, we could assume that IoTDs that are closer than a certain threshold distance to the BS are not allowed to be reuse partners. This assumption gives a two-fold advantage, first, it helps in avoiding severe interference at the BS and reduce the number of combinations. This threshold distance can be lower-bounded using the high-SNR approximation of (6) as follows:

$$ {r_{m}^{u}} \le \frac{P_{eNB}^{u}}{K L P_{d} (d_{th})^{-\alpha}}, $$

(19)

where the maximum number of allowed IoT interferes to each UE from all groups are assumed (i.e.,${\sum }_{k=1}^{K} {\sum }_{n=1}^{N} a_{m,n,k} = K$) and equal transmit power for all IoTDs. therefore, any IoTD with a distance larger than this threshold is allowed to be reuse candidate which can be recast as follows:

$$ d_{n,k}^{b}\geq d_{th} =\left( \frac{K {r_{m}^{u}} L P_{d}}{P_{eNB}^{u} }\right)^{1/\alpha}. $$

(20)

If we assume a threshold distance equal to d_th, 1.1d_th and 1.2d_th, the matching algorithm execution time is reduced by 48%, 55% and 61%, while the throughput gain and the access rate for a threshold distance d_th are almost the same without taking a threshold (this will be explained later in Figs. 4 to 9).

On the other hand, since we assume an equal power allocation of all IoTDs reusing the same UE, we need to determine a sub-optimal value ($P_{n,k}^{m}=P_{d}$) that achieves the maximum throughput. In Fig. 3, we adopted numerical simulation to find the power level that maximizes the throughput gain within the allowed range of values (i.e., P_d from 0 : 23 dB_m) for different distances between eNB and IoTD-GWs. The simulation results show that increasing P_d improves the throughput gain until a certain value where the gain saturates due to the introduced interference.

Fig. 3

Throughput gain vs.transmit power levels, $P_{n,k}^{m}=P_{d}$, for different values of the distance between IoT-GW and eNB, where number of IoTDs/Cluster is 50

Figures 4 and 5 illustrate the effect of changing the distance between any IoT-GW and eNB (400, 600, and 800 m) on the cell throughput gain and accessibility of IoTDs when the IoTGs radii are 100 m. Both figures compare the single IoT group ORA algorithm, the proposed GIM algorithm for single IoT group scenario (K = 1 GIM), and the proposed GIM algorithm for double IoT groups (K = 2 GIM). The simulation results show that the cell throughput gain and IoTDs accessibility increase with increasing the distance between eNB and IoT-GWs due to the reduced interference from IoTDs. Figure 4 reveals that throughput gain improves with the increases in the number of IoTDs due to the availability of much more combination of IoTDs that to select from. On the other hand, the results in Fig. 5 show that the access rate drops with the increase of the number of deployed IoTDs due to the assumption of a constant number of available UEs where each UE is limited to be paired with at most K IoTDs. Additionally, the proposed GIM algorithm with K = 2 has a better performance in terms of both of the cell throughput gain and accessibility of IoTDs compared to the single IoTG scenario. The simulation results show the effect of setting a distance threshold for the multiple IoT group scenario where the throughput gain and the access rates drop slightly when we increase the threshold distance. The effect appears when there is a large number of IoTDs in the system.

Fig. 4

Throughput gain vs. the number of IoTDs per IoTG for different values of the distance between IoT-GW and eNB

Fig. 5

Access rate vs. the number of IoTDs per IoTG for different values of the distance between IoT-GW and eNB

Figures 6 and 7 show the effect of the IoTGs radii (100, 200, and 300 m) on the throughput gain and the access rate for a fixed distance between the IoT-GW and the eNB (600 m). The simulation results show that the cell throughput gain and IoTDs accessibility increase with decreasing the radii of the IoTGs. Decreasing the radius reduces the interference from IoTDs to eNB which increases the number of paired IoTDs and the total cell throughput.

Fig. 6

Throughput gain vs. the number of IoTDs per IoTG for different values of the IoTG radius (100, 200, and 300 m)

Fig. 7

Access rate vs. the number of IoTDs per IoTG for different values of IoTG radius (100, 200, and 300 m)

Figures 8 and 9 show the effect of the QoS constraints of the IoTDs on the throughput gain and the access rate for a fixed distance between IoT-GW and eNB (600 m) and IoTGs radii of 100 m. the simulation results show that a lower SIR increases cell throughput gain and accessibility of IoTDs, since decreasing SIR constrains for IoTDs increases the probability of pairing larger number of IoTDs while reducing interference of IoTDs on eNB and increasing the cell throughput gain.

Fig. 8

Throughput gain vs. the number of IoTDs per IoTG for different values of maximum SIR of IoTDs

Fig. 9

Access rate vs. the number of IoTDs per IoTG for different values of maximum SIR of IoTDs

Based on the previously presented results, the performance of the proposed GIM algorithm outperforms the optimal resource allocation (ORA) in [3] as a baseline in terms of both of the cell throughput gain and accessibility of IoTDs in the cases of a single cluster and two clusters as well.

In Fig. 10, the performance of the GIM algorithm is further compared to two multi-cluster based algorithms, namely the fixed-radio resource sharing algorithm (F-RRSA) [5] and the adaptive radio resource sharing algorithm (A-RRSA) [6]. F-RRSA aims to maximize the sum rate with a computational complexity of $\mathcal {O}(M^{3}+KM^{3})$ while A-RRSA is built upon F-RRSA to consider the trade-off between fairness and data rate with a higher computational complexity due to the adoption of proportional integral control (PID). The simulation parameters in Fig. 10 are adopted from [5, 6] for fair comparison which are given as follows: the radius of eNB coverage is 500 m, the cluster radius is 70 m, the distance between eNB and IoT-GW is 100 m, the maximum transmission power of UEs is 24 dB_m, and the D2D transmission power is 5:15 dB_m. Moreover, the number of devices per cluster is 50 % of the number of UEs. The simulation results show that the proposed GIM algorithm outer performs the two other algorithms, while the F-RRSA achieves better performance compared to the A-RRSA algorithm.

Fig. 10

Performance comparison of the GIM algorithm with F-RRSA [5], A-RRSA [6], and ORA [3] algorithms

5 Conclusion

In this work, we investigated a sub-optimal resources allocation scheme for multiple IoT group deployment underlaying cellular communication. The proposed greedy iterative matching (GIM) algorithm improves the cell throughput gain and IoTDs access rate compared to the single IoT group deployment scenarios. The proposed analysis and simulation results show that setting a lower-bound on how close the allowed IoT reuse partners reduces the computation complexity while preserving sufficient performance gain. As future research directions, we would like to investigate the joint EE and number of admitted IoT devices maximization in addition to the investigation of other matching algorithms to improve performance.

Appendix: Numerical Example of the GIM Algorithm

Fig. 11

GIM numerical example: M = 4, K = 2, N = 4, distance between IoT-GW and eNB= 800 m, max distance between IoT-GW and IoTDs= 100 m