Content area

Abstract

Translate

ABSTRACT

This paper proposes a sub‐optimal Kuhn–Munkres‐based resource assignment algorithm to maximize both the number of connected links and the mean throughput per link in ultra‐dense networks (UDNs) consisting of densely distributed co‐channel access points (APs) and user equipment (UEs). The proposed seven‐step algorithm first assigns UEs to APs that provide higher data rates while accounting for the interference of all APs. Next, only the interference from the selected APs is considered to identify UEs that meet the minimum throughput threshold level. In subsequent steps, considering both the interference of previously assigned APs and the remaining candidate APs, additional UEs are connected. Simulation results in MATLAB for a 250m×250m$$ 250\ \mathrm{m}\times 250\ \mathrm{m} $$ service area with 250$$ 250 $$ randomly distributed APs and varying numbers of UEs (25–250$$ 250 $$) demonstrate that the proposed algorithm achieves higher connectivity and total throughput with significantly reduced processing time compared to the Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Cuckoo Search (CS), and Gray Wolf Optimization (GWO). Specifically, as the number of UEs increases from 10%$$ 10\% $$ to 100%$$ 100\% $$ of the number of APs, the proposed algorithm improves the number of connected UEs by 10%−48%$$ 10\%-48\% $$, 47%−96%$$ 47\%-96\% $$, 57%−109%$$ 57\%-109\% $$, and 22%−58%$$ 22\%-58\% $$, and the total throughput by 20%−52%$$ 20\%-52\% $$, 44%−86%$$ 44\%-86\% $$, 50%−105%$$ 50\%-105\% $$, and 22%−69%$$ 22\%-69\% $$, respectively, over the four benchmark algorithms. Moreover, owing to its lower computational complexity, the proposed method achieves at least 99%$$ 99\% $$ reduction in processing time.

Full text

Translate
Turn on search term navigation

Introduction

The advancement of mobile wireless and optical networks has led to a surge in users of smart terminals—such as cell phones, smart watches, vehicle-mounted intelligent devices, and wearables—as well as new services and applications, including Artificial Intelligence (AI), the Internet of Things (IoT), and caching. This growth has driven a significant increase in mobile data traffic. In 2023, approximately 328.77$$ 328.77 $$ exabytes of data were generated per day, or 120$$ 120 $$ zettabytes per year. Data volume is expected to reach 142$$ 142 $$ zettabytes in 2024 and 181$$ 181 $$ zettabytes in 2025, with projections indicating that global mobile data traffic will reach 351$$ 351 $$ exabytes by 2025 [1, 2].

A key approach to increasing the total network data rate and Area Spectrum Efficiency (ASE) is network densification and the transition from homogeneous networks to heterogeneous networks (HetNets) [3–5]. By deploying a large number of Access Points (APs) or Base Stations (BSs), networks can support User Equipment (UEs) requiring high data rates and low-latency wireless links. The rapid growth of mobile broadband traffic will challenge traditional macrocell-based networks, which cannot meet future communication demands. To address this, network densification is essential [6]. Ultra Dense Networks (UDNs)—a key concept in 5G and 6G—deploy a very high density of small cells, base stations, or access points, far beyond conventional networks. By shortening the distance between transmitters and receivers, UDNs improve signal quality, boost data rates, lower latency, and enhance overall system performance [7]. UDNs often feature more than 1000$$ 1000 $$ access points per square kilometer [8], where the primary optimization challenge is resource allocation (assignment). Extensive research has focused on designing resource allocation schemes to serve an increasing number of UEs while maintaining acceptable data rates [9–13]. Consequently, achieving high Quality of Service (QoS) and supporting a large total throughput and number of UEs in UDNs requires low-complexity, sub-optimal resource allocation methods for effectively assigning APs to UEs.

An UDN includes NAT$$ {N}_{\mathrm{AT}} $$ access points and NUT$$ {N}_{\mathrm{UT}} $$ user equipment. The number of single-channel APs, or equivalently, the number of multi-channel APs multiplied by the number of channels per AP, is greater than the number of UEs. Both APs and UEs are densely distributed in the service area. In such a network, the resource allocation problem must be solved to address the following questions:

  • Which frequency channels, among NC$$ {N}_C $$ available channels, should be activated at each AP?
  • Which AP should be connected to which UE?
  • For active links, what transmit power should be assigned to maximize total throughput while satisfying all constraints?

By solving the corresponding optimization problem, we aim to achieve the following goals:

  • Select the best APs and frequency channels to serve UEs, ensuring both high data rates and low latency.
  • Maximize utilization of APs and frequency channels to increase the number of active links.
  • Increase the total throughput, defined as the product of the average data rate per unit bandwidth of an AP-UE link and the number of active AP-UE links.

In this study, we formulate a four-variable single-objective optimization problem, which seeks proper solutions for the following decisions:

  • To which AP should each UE be connected?
  • Which frequency channel should be assigned to each AP–UE link?
  • What transmit power should be allocated to each active AP–UE link?

Without loss of generality, and assuming uplink and downlink channels are symmetric, we focus on the downlink case, where APs act as transmitters and UEs as receivers. We propose a three-step optimization framework to solve the general problem:

  • Random clustering: Partition UEs into NC$$ {N}_C $$ independent, non-overlapping subsets, while all APs are included in each cluster.
  • Resource assignment: Determine AP–UE links within each cluster.
  • Power control: Optimize transmit power for the links assigned in the previous step.

Since all frequency channels assigned to APs are orthogonal (i.e., an Orthogonal Multiple Access (OMA) model is assumed), each cluster corresponds to one frequency channel.

The work reported in this paper focuses exclusively on the second step—the resource assignment process. We propose a suboptimal resource assignment algorithm based on the Kuhn–Munkres algorithm to determine AP–UE links in each cluster. Our main contribution is a Kuhn–Munkres-based assignment scheme for AP–UE links under a single-frequency channel per cluster.

The goal of resource assignment is to allocate NAT$$ {N}_{\mathrm{AT}} $$ resources (APs or BSs) to NUT$$ {N}_{\mathrm{UT}} $$ requesters (UEs) in order to maximize (or minimize) a given objective (or cost) function. This can be formulated as selecting NUT$$ {N}_{\mathrm{UT}} $$ elements from an NUT×NAT$$ {N}_{\mathrm{UT}}\times {N}_{\mathrm{AT}} $$ matrix such that each row has exactly one selected element, with no repetitions in columns. Specifically, the assignment algorithm selects NUT$$ {N}_{\mathrm{UT}} $$ elements from the Signal to Interference plus Noise Ratio (SINR) or throughput (data rate per Hz) matrix to maximize the total SINR or throughput of the assigned AP–UE links. The Time Complexity Order (TCO) of the optimal solution using Exhaustive Search (ES) is given in (1), which is computationally infeasible for large NUT$$ {N}_{\mathrm{UT}} $$ and NAT$$ {N}_{\mathrm{AT}} $$. TCOES=OmaxNUT,NAT!NAT−NUT!$$ {\mathrm{TCO}}_{\mathrm{ES}}=O\left(\frac{\left[\max \left({N}_{\mathrm{UT}},{N}_{\mathrm{AT}}\right)\right]!}{\left|{N}_{\mathrm{AT}}-{N}_{\mathrm{UT}}\right|!}\right) $$

When the number of requesters equals the number of resources, the time complexity order is given in Equation (2). TCOES=O(N!),forNUT=NAT=N$$ {\mathrm{TCO}}_{\mathrm{ES}}=O\left(N!\right), for\ {N}_{\mathrm{UT}}={N}_{\mathrm{AT}}=N $$

For UDNs, where NUT<NAT$$ {N}_{\mathrm{UT}}<{N}_{\mathrm{AT}} $$, the TCO of the ES is given in Equation (3). TCOES=ONAT!NAT−NUT!,forNUT<NAT$$ {\mathrm{TCO}}_{\mathrm{ES}}=O\left(\frac{N_{\mathrm{AT}}!}{\left({N}_{\mathrm{AT}}-{N}_{\mathrm{UT}}\right)!}\right), for\ {N}_{\mathrm{UT}}<{N}_{\mathrm{AT}} $$

One popular sub-optimal solution for the case NUT=NAT=N$$ {N}_{\mathrm{UT}}={N}_{\mathrm{AT}}=N $$, is the first version of the Hungarian algorithm, whose time complexity order is given in Equation (4) [14]. TCOH=ON3,forNUT=NAT=N$$ {\mathrm{TCO}}_{\mathrm{H}}=O\left({N}^3\right), for\ {N}_{\mathrm{UT}}={N}_{\mathrm{AT}}=N $$

In the works of Kuhn and Munkres [15, 16], the processing speed of the Hungarian algorithm was improved and the method extended to handle non-square matrices. The algorithm selects minNUT,NAT$$ \min \left({N}_{\mathrm{UT}},{N}_{\mathrm{AT}}\right) $$ elements from a matrix with non-identical rows and columns. It has been proven that the time complexity order of the Kuhn–Munkres (KM) algorithm for the case NUT<NAT$$ {N}_{\mathrm{UT}}<{N}_{\mathrm{AT}} $$ is given in [15, 16]. TCOKM=ONUT×NAT2,forNUT<NAT$$ {\mathrm{TCO}}_{\mathrm{KM}}=O\left({N}_{\mathrm{UT}}\times {N}_{AT}^2\right), for\ {N}_{\mathrm{UT}}<{N}_{\mathrm{AT}} $$

Recent studies [17, 18] addressed the assignment problem for scenarios where the number of requesters exceeds the number of available resources NUT>NAT$$ {N}_{\mathrm{UT}}>{N}_{\mathrm{AT}} $$. This case is particularly relevant to wireless systems that require resource reuse [19], such as Device-to-Device (D2D) and Vehicle-to-Vehicle (V2V) communications. In these investigations, the locations of secondary UEs requesting resources and the active BSs serving primary UEs were assumed to be known. During the first stage of the KM-based algorithm, resources for the secondary UEs are assigned while accounting for interference from the primary links. If resources are still insufficient, subsequent stages of the Multi-Stage Kuhn–Munkres (MS-KM) algorithm perform resource reuse by re-allocating the resources used in the first stage, considering the interference from both the primary users' links and the secondary links selected in earlier stages.

When NUT=NMS×NAT$$ {N}_{\mathrm{UT}}={N}_{\mathrm{MS}}\times {N}_{\mathrm{AT}} $$, the time complexity order of the MS-KM-based assignment algorithm follows the order given in (6), reflecting the worst case of running the algorithm up to NMS$$ {N}_{\mathrm{MS}} $$ times. TCOMS−KM≤∑nMS=0NMS−1ONAT×NUT−nMS×NAT2<ONMS×NAT×NUT2$$ {\displaystyle \begin{array}{ll}{\mathrm{TCO}}_{\mathrm{MS}-\mathrm{KM}}& \le {\sum}_{n_{\mathrm{MS}}=0}^{N_{\mathrm{MS}}-1}O\left({N}_{\mathrm{AT}}\times {\left({N}_{\mathrm{UT}}-{n}_{\mathrm{MS}}\times {N}_{\mathrm{AT}}\ \right)}^2\right)\\ {}& <O\left({N}_{\mathrm{MS}}\times {N}_{\mathrm{AT}}\times {N}_{UT}^2\right)\end{array}} $$

Network densification improves coverage probability (or reduces outage probability), increases throughput and sum-rate (b/s/Hz), enhances Energy Efficiency (EE, measured as data rate per unit power in b/j), and improves Spectral Efficiency (SE, measured as average bits per hertz in b/Hz). However, implementing resource allocation algorithms in dense and ultra-dense networks introduces significant time, memory, computational complexity, and signaling/control overhead. To address these challenges, researchers have applied convex and combinatorial optimization, graph and game theory, stochastic and sparse optimization, binary assignment algorithms such as the Kuhn–Munkres method, grouping/clustering schemes, and thresholding/sorting algorithms [20–26]. Building on related studies [17, 18] that applied the Kuhn–Munkres approach to D2D and V2V communications, this paper proposes a novel Kuhn–Munkres-based resource allocation algorithm tailored for UDNs.

In UDNs, where APs and/or UEs are densely deployed to meet stringent low-latency and high-reliability requirements, the resource assignment problem for maximizing the objective function is a non-convex, NP-hard challenge. A key paradox arises: we must allocate resources to UEs and activate a subset of APs, yet we simultaneously seek APs that provide the best data rates and lowest delay without knowing in advance which APs are active and potentially interfering with other UEs.

In this study, we assume that all APs operate on a single shared resource, and that UEs requesting resources can activate and connect to co-channel APs. This configuration enables the UDN to accommodate a larger number of UEs and achieve higher total throughput. Consequently, when assigning an AP to a UE, it is essential to identify the optimal AP while accounting for the interference from other links, whose impact cannot be fully determined until the overall problem is solved.

In this research, we establish a seven-step KM-based assignment algorithm to find sub-optimal links between APs and UEs in UDNs. This work extends Ref. [27] with the following key contributions:

  • Formulation of the main four-variable single-objective optimization problem and a three-step suboptimal solution for clustering, co-channel resource assignment, and power control.
  • Inclusion of two additional well-known algorithms—Cuckoo Search (CS) and Gray Wolf Optimization (GWO)—alongside Genetic and Particle Swarm Optimization (PSO) to demonstrate the superiority of the proposed KM-based resource assignment algorithm for UDNs.
  • Enhancement of the KM-based algorithm with a flowchart illustrating the main concept and a pseudo-code for practical implementation.
  • Increased the number of simulation runs to produce more accurate and realistic numerical results and analysis.

The next six sections complete the objectives of this article. Section 2 presents the system model and the corresponding NP-hard, non-convex optimization problem. Section 3 provides a brief overview of the Kuhn–Munkres, Genetic, PSO, CS, and GWO algorithms. Section 4 introduces the seven-step KM-based resource allocation algorithm for UDNs with numerous co-channel APs and/or UEs, accompanied by a flowchart and pseudo-code. Section 5 presents MATLAB simulation results and numerical analyses. Finally, Sections 6 and 7 discuss the conclusions and outline directions for future work.

System Model and Optimization Problem

Optimization in UDNs can be categorized into two types of problems: multi-objective problems [28] and multi-variable single-objective problems. To address these optimization problems, three main approaches are commonly used [29]:

  • Convex or relaxed convex optimization: The problem is solved directly using convex optimization techniques or by relaxing it into a convex form.
  • Divide-and-conquer: The original problem is decomposed into multiple subproblems, each solved individually, and then their solutions are combined to obtain the overall solution.
  • Iterative variable optimization: The problem is solved iteratively by optimizing one variable at a time while keeping the others fixed, and repeating this process until convergence.

In this work, we focus on a single-objective optimization problem, which is distinct from a multi-objective optimization problem in terms of both formulation and target.

As shown in Figure 1, a UDN consists of densely distributed UEs and APs within the service area. In this study, NAT$$ {N}_{\mathrm{AT}} $$ APs have similar resources and may interfere with each other. Consequently, some APs are assigned to the NUT$$ {N}_{\mathrm{UT}} $$ UEs, while the remaining APs are turned off.

[IMAGE OMITTED. SEE PDF]

Generally, the problem can be formulated as a four-variable single-objective optimization problem, or equivalently a four-sigma optimization problem, subject to five constraints, denoted as (7). argmaxxi,jk,l∑l=1NP∑k=1NC∑j=1NAT∑i=1NUTxi,jk,l×RBk.l(i,j)Subject to:C1:xi,jk,l∈{0,1},∀i∈1,…,NUT,∀j∈1,…,NAT,∀k∈1,…,NC,∀l∈1,…,NPC2:∑i=1NUTxi,jk,l≤NC,∀j∈1,…,NAT,∀k∈1,…,NC,∀l∈1,…,NPC3:∑j=1NATxi,jk,l≤1,∀i∈1,…,NUT,∀k∈1,…,NC,∀l∈1,…,NPC4:RBk.l(i,j)≥RBth,∀i∈1,…,NUT,∀j∈1,…,NAT,∀k∈1,…,NC,∀l∈1,…,NPC5:Pt,jk,l=Ptmin+l−1NP−1×Ptmax−Ptmin,∀j∈1,…,NAT,∀k∈1,…,NC,∀l∈1,…,NP$$ \left\{\begin{array}{l}\underset{x_{i,j}^{k,l}}{\mathrm{argmax}}\left(\sum \limits_{l=1}^{N_P}\sum \limits_{k=1}^{N_C}{\sum}_{\mathrm{j}=1}^{{\mathrm{N}}_{\mathrm{AT}}}{\sum}_{i=1}^{N_{\mathrm{UT}}}{x}_{i,j}^{k,l}\times {R}_B^{k.l}\left(i,j\right)\right)\\ {}\mathrm{Subject}\ \mathrm{to}:\\ {}{\mathrm{C}}_1:\kern0.5em {x}_{i,j}^{k,l}\in \left\{0,1\right\},\kern13.9em \forall \mathrm{i}\in \left\{1,\dots, {N}_{\mathrm{UT}}\right\},\forall \mathrm{j}\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\},\\ {}\kern22em \forall \mathrm{k}\in \left\{1,\dots, {N}_C\right\},\forall \mathrm{l}\in \left\{1,\dots, {N}_P\right\}\\ {}{\mathrm{C}}_2:\kern0.5em {\sum}_{i=1}^{N_{\mathrm{UT}}}{x}_{i,j}^{k,l}\le {N}_C,\kern12.6em \forall \mathrm{j}\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\},\forall \mathrm{k}\in \left\{1,\dots, {N}_C\right\},\\ {}\kern22.10em \forall \mathrm{l}\in \left\{1,\dots, {N}_P\right\}\\ {}\\ {}{\mathrm{C}}_3:\kern0.5em {\sum}_{j=1}^{N_{\mathrm{AT}}}{x}_{i,j}^{k,l}\le 1,\kern13.6em \forall \mathrm{i}\in \left\{1,\dots, {N}_{\mathrm{UT}}\right\},\forall \mathrm{k}\in \left\{1,\dots, {N}_C\right\},\\ {}\kern22.00em \forall \mathrm{l}\in \left\{1,\dots, {N}_P\right\}\\ {}{\mathrm{C}}_4:{R}_B^{k.l}\left(i,j\right)\ge {R_B}_{\mathrm{th}},\kern12.8em \forall \mathrm{i}\in \left\{1,\dots, {N}_{\mathrm{UT}}\right\},\forall \mathrm{j}\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\},\\ {}\kern22em \forall \mathrm{k}\in \left\{1,\dots, {N}_C\right\},\forall \mathrm{l}\in \left\{1,\dots, {N}_P\right\}\\ {}\begin{array}{l}{\mathrm{C}}_5:\kern0.5em {P}_{t,j}^{k,l}={P}_{\mathrm{tmin}}+\frac{\mathrm{l}-1}{N_P-1}\times \left({P}_{\mathrm{tmax}}-{P}_{\mathrm{tmin}}\right),\kern3.5em \forall \mathrm{j}\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\},\forall \mathrm{k}\in \left\{1,\dots, {N}_C\right\},\\ {}\kern22.25em \forall \mathrm{l}\in \left\{1,\dots, {N}_P\right\}\end{array}\end{array}\right. $$ where NAT$$ {N}_{\mathrm{AT}} $$, NUT$$ {N}_{\mathrm{UT}} $$, NC$$ {N}_C $$, and NP$$ {N}_P $$ denote the numbers of APs, UEs, frequency channels of each AP, and transmit power levels of each transmitter, respectively. RBth$$ {R_B}_{\mathrm{th}} $$ is the minimum throughput threshold (data rate per hertz) required at the receiver to ensure an acceptable AP–UE wireless link. RBk.l(i,j)$$ {R}_B^{k.l}\left(i,j\right) $$ represents the Shannon–Hartley throughput of the ith UE-jth AP link in kth frequency channel with lth transmit power level. The transmit power of jth transmitter in kth frequency channel with lth power level, Pt,jk,l,$$ {P}_{t,j}^{k,l}, $$ can be changed from Ptmin$$ {P}_{\mathrm{tmin}} $$ to Ptmax$$ {P}_{\mathrm{tmax}} $$ with NP$$ {N}_P $$ level.

The first constraint, C1$$ {C}_1 $$, demonstrates whether a link is established (xi,jk,l=1$$ {x}_{i,j}^{k,l}=1 $$) or not (xi,jk,l=0$$ {x}_{i,j}^{k,l}=0 $$). The second constraint, C2$$ {C}_2 $$, indicates that each AP can be assigned to at most NC$$ {N}_C $$ user equipment. Constraint C3$$ {C}_3 $$ forces each UE to be connected to just one AP. The fourth constraint, C4$$ {C}_4 $$, guarantees the minimum required throughput for each active AP-UE link. The fifth constraint, C5$$ {C}_5 $$, limits the transmit power between minimum and maximum levels.

Solving this problem by exhaustive search has the time complexity order given in (8), which is practically infeasible. The three terms in this complexity expression make the problem NP-hard, and therefore it must be addressed using suboptimal solution methods. TCOES1=OmaxNUT,NAT!NAT−NUT!×fNC×gNP$$ {\mathrm{TCO}}_{\mathrm{ES}1}=\mathrm{O}\left(\frac{\left[\max \left({\mathrm{N}}_{\mathrm{UT}},{\mathrm{N}}_{\mathrm{AT}}\right)\right]!}{\left|{\mathrm{N}}_{\mathrm{AT}}-{\mathrm{N}}_{\mathrm{UT}}\right|!}\times f\left({N}_C\right)\times g\left({N}_P\right)\right) $$

According to Figure 2, we propose a suboptimal solution that addresses the main problem through a three-step procedure.

[IMAGE OMITTED. SEE PDF]

Therefore, the time and memory complexity of solving this four-variable single-objective optimization problem can be significantly reduced. In brief, we transform the original 4-variable (or 4-sigma) problem (7), which involves NAT$$ {N}_{\mathrm{AT}} $$ access points, NUT$$ {N}_{\mathrm{UT}} $$ user equipment, NC$$ {N}_C $$ orthogonal channels, and NP$$ {N}_P $$ transmit power levels, into a three-step procedure:

  • Select NUT$$ {N}_{\mathrm{UT}} $$ UEs to form NC$$ {N}_C $$ clusters, randomly;
  • Solve a 2-variable (2-sigma) resource assignment problem independently for each of the NC$$ {N}_C $$ clusters;
  • Evaluate NP$$ {N}_P $$ transmit power levels and select the optimal values for the assigned AP–UE links.

Given that the NC$$ {N}_C $$ frequency channels are orthogonal, we construct NC$$ {N}_C $$ clusters, each containing all NAT$$ {N}_{\mathrm{AT}} $$ access points and NU$$ {N}_U $$ UEs (9) randomly selected from the main UE set. NU=NUTNC$$ {N}_U=\frac{N_{\mathrm{UT}}}{N_C} $$

In the first step, NC$$ {N}_C $$ clusters are formed, where each cluster functions as a small UDN consisting of NAT$$ {N}_{\mathrm{AT}} $$ access points and NU$$ {N}_U $$ UEs, all of which can communicate over a single frequency channel. Since all active APs and UEs within a cluster operate on the same channel, a low-complexity assignment algorithm is required to manage frequency reuse efficiently. In the second step, NC$$ {N}_C $$ independent assignments are performed to establish AP–UE links within each cluster, assuming fixed transmit powers. Finally, in the third step, a power control algorithm is applied to the selected AP–UE links that are active across different frequency channels.

Using the proposed solution, the total time complexity orders of exhaustive search for Steps 1, 2, and 3 are given by (10–12), respectively. TCO1=ONC×NU$$ {\mathrm{TCO}}_1=\mathrm{O}\left({N}_C\times {N}_U\right) $$ TCO2=ONC×maxNU,NAT!NAT−NU!$$ {\mathrm{TCO}}_2=\mathrm{O}\left({N}_C\times \frac{\left[\max \left({N}_U,{N}_{\mathrm{AT}}\right)\right]!}{\left|{N}_{\mathrm{AT}}-{N}_U\right|!}\right) $$ TCO3=ONPNAT$$ {\mathrm{TCO}}_3=\mathrm{O}\left({N_P}^{N_{\mathrm{AT}}}\right) $$

Hence, the overall complexity order for exhaustive search is given by (13). TCOES2=ONC×NU+maxNU,NAT!NAT−NU!+NPNAT$$ {\mathrm{TCO}}_{\mathrm{ES}2}=\mathrm{O}\left({N}_C\times \left\{{N}_U+\frac{\left[\max \left({N}_U,{N}_{\mathrm{AT}}\right)\right]!}{\left|{N}_{\mathrm{AT}}-{N}_U\right|!}\right\}+{N_P}^{N_{\mathrm{AT}}}\right) $$

Although the total computational order TCOES2$$ {\mathrm{TCO}}_{\mathrm{ES}2} $$ of the proposed suboptimal solution for UDN resource allocation is significantly lower than of the original exhaustive solution, the AP–UE assignment and power control for active transmitters still require time-efficient suboptimal algorithms. The primary focus of this study, as presented below, is solving the assignment problem in the second step of the proposed solution using a new, low-complexity, seven-step Kuhn–Munkres-based assignment algorithm.

The non-convex optimization problem, consisting of an objective function subject to four constraints, is formulated in (14). argmaxxi,j∑i=1NU∑j=1NATxi,j×RB(i,j)Subject to:C1:xi,j∈{0,1},∀i∈1,…,NU,∀j∈1,…,NATC2:∑i=1NUxi,j≤1,∀j∈1,…,NATC3:∑j=1NATxi,j≤1,∀i∈1,…,NUC4:RB(i,j)≥RBth,∀i∈1,…,NU,∀j∈1,…,NAT$$ \left\{\begin{array}{l}\underset{{\mathrm{x}}_{\mathrm{i},\mathrm{j}}}{\mathrm{argmax}}\left({\sum}_{i=1}^{N_U}{\sum}_{j=1}^{N_{AT}}{x}_{i,j}\times {R}_B\left(i,j\right)\right)\\ {}\mathrm{Subject}\ \mathrm{to}:\\ {}{C}_1:\kern0.5em {x}_{i,j}\in \left\{0,1\right\},\kern8.5em \forall i\in \left\{1,\dots, {N}_U\right\},\\ {}\kern16.5em \forall j\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\}\\ {}{C}_2:\kern0.5em {\sum}_{i=1}^{N_U}{x}_{i,j}\le 1,\kern8.25em \forall j\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\}\\ {}{C}_3:\kern0.5em {\sum}_{j=1}^{N_{\mathrm{AT}}}{x}_{i,j}\le 1,\kern8.25em \forall i\in \left\{1,\dots, {N}_U\right\}\\ {}{C}_4:{R}_B\left(i,j\right)\ge {R_B}_{\mathrm{th}},\kern7.5em \forall i\in \left\{1,\dots, {N}_U\right\},\\ {}\kern16.5em \forall j\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\}\end{array}\right. $$ where NAT$$ {N}_{\mathrm{AT}} $$ denotes the number of APs and NU≤NAT$$ {N}_U\left(\le {N}_{\mathrm{AT}}\right) $$ represents the number of UEs in each cluster. RBth$$ {R_B}_{\mathrm{th}} $$ is the minimum throughput threshold (data rate per hertz) required at the receiver to ensure an acceptable AP–UE wireless link. RB(i,j)$$ {R}_B\ \left(i,j\right) $$ represents the Shannon–Hartley throughput of the ith UE-jth AP link, as given in (15), and depends on SINR(i,j)$$ \mathrm{SINR}\left(i,j\right) $$. RB(i,j)=log2(1+SINR(i,j))$$ {R}_B\left(i,j\right)={\mathit{\log}}_2\left(1+\mathrm{SINR}\ \left(i,j\right)\right) $$ where SINR(i,j)$$ \mathrm{SINR}\left(i,j\right) $$ is the SINR at the receiver of the ith UE- jth AP link, as defined in (16). Pt$$ {P}_t $$ denotes the maximum transmit power of each transmitter, γ$$ \gamma $$ is the path loss exponent, and dij$$ {d}_{ij} $$ is the distance between the ith UE and the jth AP. SINR(i,j)=Pt×di,j−γ×hi,j2σn2+∑k=1k≠jNATPt×di,k−γ×hi,k2$$ \mathrm{SINR}\left(i,j\right)=\frac{P_t\times {d}_{i,j}^{-\gamma}\times {\left|{h}_{i,j}\right|}^2}{\sigma_n^2+{\sum}_{\begin{array}{l}k=1\\ {}k\ne j\end{array}}^{N_{AT}}{P}_t\times {d}_{i,k}^{-\gamma}\times {\left|{h}_{i,k}\right|}^2} $$

The channel power gain is modeled by hi,j2$$ {\left|{h}_{i,j}\right|}^2 $$. hi,j,$$ {h}_{i,j}, $$ the channel gain between ith user equipment and jth access point, is modeled by (17) in the linear scale and (18) in the deci-Bell scale, both including the multipath fading component, hf,i,j$$ {h}_{f,i,j} $$, and the shadowing component, hs,i,j$$ {h}_{s,i,j} $$ [30–32]. hi,j=hf,i,j×hs,i,j$$ {h}_{i,j}={h}_{f,i,j}\times {h}_{s,i,j} $$ hi,jdB=hf,i,jdB+hs,i,jdB$$ {h}_{i,j\mathrm{dB}}={h}_{f,i,j\mathrm{dB}}+{h}_{s,i,j\mathrm{dB}} $$

For each link, we have the Rayleigh fading probability density function (pdf) according to (19) [32]. fhfhf=hf2π4−πσhf×e−hf244−πσhf2,hf≥0$$ {f}_{h_f}\left({h}_f\right)=\frac{h_f}{2\sqrt{\frac{\pi }{4-\pi }}{\sigma}_{h_f}}\times {e}^{-\frac{h_f^2}{\left(\frac{4}{4-\pi}\right){\sigma}_{h_f}^2}},{h}_f\ge 0 $$

Considering r=hf2$$ r={\left|{h}_f\right|}^2 $$ in the power gain, we have a negative exponential pdf for random variable r$$ r $$ as (20) [31]. fr(r)=4−π2π×e−r44−πσhf2,r≥0$$ {f}_r(r)=\frac{\sqrt{4-\pi }}{2\sqrt{\pi }}\times {e}^{-\frac{r}{\left(\frac{4}{4-\pi}\right){\sigma}_{h_f}^2}},r\ge 0 $$

For each link, we can model the shadowing effect in linear scale using a Log-normal distribution as (21) with a pdf shown in (22) or in deci-Bell scale using a Gaussian (Normal) distribution as (23) with a pdf shown in (24) [30, 31]. hs∼Lognormalμhs,dB,σhs,dB2$$ {h}_s\sim \mathrm{Lognormal}\left({\mu}_{h_{s,\mathrm{dB}}},{\sigma}_{h_{s,\mathrm{dB}}}^2\right) $$ fhshs=10Ln(10)2πσhs,dB×hs×e−hs,dB−μhs,dB22σhs,dB2$$ {f}_{h_s}\left({h}_s\right)=\frac{\frac{10}{Ln(10)}}{\sqrt{2\pi }{\sigma}_{h_{s,\mathrm{dB}}}\times {h}_s}\times {e}^{-\frac{{\left(\ {h}_{s, dB}-{\mu}_{h_{s,\mathrm{dB}}}\right)}^2}{2{\sigma}_{h_{s, dB}}^2}} $$ hsdB∼Gaussianμhs,dB,σhs,dB2$$ {h}_{s\mathrm{dB}}\sim \mathrm{Gaussian}\left({\mu}_{h_{s,\mathrm{dB}}},{\sigma}_{h_{s,\mathrm{dB}}}^2\right) $$ fhs,dBhs,dB=12πσhs,dB×e−hs,dB−μhs,dB22σhs,dB2$$ {f}_{h_{s,\mathrm{dB}}}\left({h}_{s,\mathrm{dB}}\right)=\frac{1}{\sqrt{2\pi }{\sigma}_{h_{s,\mathrm{dB}}}}\times {e}^{-\frac{{\left(\ {h}_{s,\mathrm{dB}}-{\mu}_{h_{s,\mathrm{dB}}}\right)}^2}{2{\sigma}_{h_{s, dB}}^2}} $$

In all simulations of this research, the variance of Rayleigh fading, σhf2$$ {\sigma}_{h_f}^2 $$, is 0.5$$ 0.5 $$ and the variance of shadowing, σhs2$$ {\sigma}_{h_s}^2 $$, is 6.31$$ 6.31 $$ in linear scale equivalent to 8dB$$ 8\ \mathrm{dB} $$. Moreover, an Additive White Gaussian Noise (AWGN) is considered by a power equal to σn2$$ {\sigma}_n^2 $$.

The first constraint, C1$$ {C}_1 $$, demonstrates whether a link is established (xi,j=1$$ {x}_{i,j}=1 $$) or not (xi,j=0$$ {x}_{i,j}=0 $$). The second constraint, C2$$ {C}_2 $$, shows that each AP can be assigned to just one UE. Constraint C3$$ {C}_3 $$ forces each UE to be connected to just one AP. The fourth constraint, C4$$ {C}_4 $$, guarantees the minimum required throughput for each active link.

Five Well-Known Algorithms for Sub-Optimum Resource Allocation

Recent advances in wireless systems and networks for communications, broadcasting, and sensing have created new challenges in optimizing the allocation of key resources—such as time, frequency, space, and power—in wireless radio applications and services [33, 34]. In UDNs, the resulting resource-allocation problems are typically non-convex. Some studies address this by reformulating the problem into a convex form for solution, wherwas others—like this research—apply sub-optimal heuristic or metaheuristic algorithms. In this work, we present an enhanced Kuhn–Munkres assignment algorithm for resource assignment in UDNs and compare its performance with results obtained using Genetic, PSO, CS, and GWO algorithms.

Kuhn-Munkres Algorithm

Harold Kuhn proposed the Hungarian algorithm in 1955 [14], combining the ideas of Egervary's ideas for simplification and graph theory-based methods to solve the binary (on/off) assignment problem. Kuhn expanded it in 1956 [15], and James Munkres reviewed it in 1957 [16]. The algorithm assigns each requester to exactly one resource at the lowest total cost. Given an (N×N$$ N\times N $$)-dimension square cost matrix, where rows represent requesters and columns represent resources, the main steps are:

  • Row reduction: Subtract the largest element of each row from every element in that row;
  • Column reduction: Repeat the process for each column;
  • Cover zeros: Draw the minimum number of horizontal and vertical lines needed to cover all zeros. If all requesters are covered, the process stops;
  • Adjust matrix (if not done): If the number of covering lines is less than NNN, find the largest uncovered value. Subtract it from every element in rows containing at least one uncovered cell, and add it to every element in fully covered columns;
  • Repeat covering: Recalculate the minimum set of lines to cover all zeros. Stop when every requester is covered.

Genetic Algorithm

The genetic algorithm is a stochastic search method that evolves a population of candidate solutions through successive iterations until a stopping criterion is met [35]. It relies on three key operators inspired by natural evolution: selection, crossover, and mutation.

  • Selection chooses parent individuals to produce the next generation [36];
  • Crossover exchanges genetic material between two parents to create offspring;
  • Mutation alters the value of a gene at a specific chromosome location by replacing it with an alternative allele, introducing new variation into the population.

PSO Algorithm

The PSO algorithm is a stochastic search method proposed by Kennedy and Eberhart in 1995 [37]. A key feature of PSO is velocity control, which governs how each particle updates its position within the search space to explore and converge toward the optimal solution. The velocity of the mth particle in the (n+1)th iteration is updated using Equation (25), and its position is updated using Equation (26). Here, sm(n+1)$$ {s}_m\left(n+1\right) $$ denotes the velocity of the mth particle at (n+1)th iteration and xm(n)$$ {x}_m(n) $$ is its position at the n$$ n $$th iteration. pbest,nm$$ {p}_{\mathrm{best},n}^m $$ represents the best position found so far by mth particle up to the nth iteration. gbest,n$$ {g}_{\mathrm{best},n} $$ is the global best position among all particles at the nth iteration. w$$ w $$ is the inertia weight, c1$$ {c}_1 $$ and c2$$ {c}_2 $$ are the real acceleration coefficients, and r1$$ {r}_1 $$ and r2$$ {r}_2 $$ are independent random numbers uniformly distributed in [0,1].

sm(n+1)=w×sm(n)+r1×c1pbest,nm−xm(n)+r2×c2gbest,n−xm(n)$$ {\displaystyle \begin{array}{ll}{s}_m\left(n+1\right)& =w\times {s}_m(n)+{r}_1\times {c}_1\ \left({p}_{best,n}^m-{x}_m(n)\right)\\ {}& \kern1em +{r}_2\times {c}_2\left({g}_{best,n}-{x}_m(n)\right)\end{array}} $$ xm(n+1)=xm(n)+sm(n+1)$$ {x}_m\ \left(n+1\right)={x}_m\ (n)+{s}_m\ \left(n+1\right) $$

CS Algorithm

The CS algorithm is a metaheuristic, population-based global search algorithm developed by Yang and Deb in 2009. Inspired by natural mechanisms, it mimics the breeding behavior of certain cuckoo species that lay their eggs in the nests of host birds [38, 39]. The algorithm can be summarized by three key rules:

  • Each cuckoo lays one egg at a time, depositing it in a randomly selected nest;
  • The best nests, containing high-quality eggs, are carried over to the next generation;
  • The number of available host nests is fixed, and hosts can detect and remove alien eggs.

GWO Algorithm

The GWO algorithm, developed by Mirjalili et al. in 2014, is a nature-inspired metaheuristic algorithm based on swarm intelligence. It mimics the leadership hierarchy and hunting behavior of gray wolves and models them mathematically [40, 41]. The algorithm begins with a randomly generated population of gray wolves (candidate solutions). During iterations, the α$$ \alpha $$, β$$ \beta $$, and δ$$ \delta $$ wolves estimate the prey's position, and each candidate solution updates its distance accordingly. The algorithm concludes by producing an optimized final solution.

Proposed Sub-Optimum Kuhn-Munkres-Based Resource Allocation Algorithm

The proposed Kuhn–Munkres-based resource allocation algorithm consists of seven main steps. It reduces the dimensions of the throughput matrix by activating only APs that can provide acceptable throughput to at least one unconnected UE, thereby lowering processing time while increasing the total number of connected UEs and overall throughput. In the first iteration, it establishes some AP–UE links as in the conventional KM algorithm, and then connects the remaining UEs to available APs through a recursive process.

Step 1: Initialize the Scalars, Vectors, and Matrices

Initialize the number of user equipment, NU$$ {N}_U $$, the number of access points, NA$$ {N}_A $$, the matrix of distances showing the distances (di,j$$ {d}_{i,j} $$) between UEs and APs, MD$$ {\boldsymbol{M}}_D $$ as (27), the transmit power of APs, Pt$$ {P}_t $$, the path loss exponent, γ$$ \gamma $$, the variance of noise, σn2$$ {\sigma}_n^2 $$, the throughput threshold level, RBth$$ {R_B}_{\mathrm{th}} $$, the channel gain hij$$ \left({h}_{ij}\right) $$ matrix, MH$$ {\boldsymbol{M}}_H $$ as (28), showing the effect of Rayleigh multipath fading and Log-normal shadowing. Set the number of selected user equipment equal to the total number of user equipment in each cluster, that is NUS=NU$$ {N}_{\mathrm{US}}={N}_U $$, the number of selected access points equals to the total number of access points, that is NAS=NAT$$ {N}_{\mathrm{AS}}={N}_{\mathrm{AT}} $$, the number of remaining user equipment equal to the total number of user equipment, that is NUR=NU$$ {N}_{\mathrm{UR}}={N}_U $$, the number of remaining access points equal to the total number of access points, that is NAR=NAT$$ {N}_{\mathrm{AR}}={N}_{\mathrm{AT}} $$. Moreover, set the vector of active APs, VA$$ {\boldsymbol{V}}_A $$ as (29), to zero, that is VA=01×NAT$$ {\boldsymbol{V}}_A={\mathbf{0}}_{1\times {N}_{AT}} $$, the vector of connected users, VU$$ {\boldsymbol{V}}_U $$ as (30), to zero, that is VU=01×NU$$ {\boldsymbol{V}}_U={\mathbf{0}}_{1\times {N}_U} $$, and the matrix of all AP-UE links, MUA$$ {\boldsymbol{M}}_{UA} $$ as (31), to zero, that is MUA=0NU×NAT$$ {\boldsymbol{M}}_{\mathrm{UA}}={\mathbf{0}}_{N_U\times {N}_{\mathrm{AT}}} $$. MD=d11,d12,…,d1NAT…dNU1,dNU2,…,dNUNAT$$ {\boldsymbol{M}}_D=\left[\begin{array}{l}{d}_{11},{d}_{12},\dots, {d}_{1{N}_{\mathrm{AT}}}\\ {}\dots \\ {}{d}_{N_U1},{d}_{N_U2},\dots, {d}_{N_U{N}_{\mathrm{AT}}}\end{array}\right] $$ MH=h11,h12,…,h1NAT…hNU1,hNU2,…,hNUNAT$$ {\boldsymbol{M}}_H=\left[\begin{array}{l}{h}_{11},{h}_{12},\dots, {h}_{1{N}_{\mathrm{AT}}}\\ {}\dots \\ {}{h}_{N_U1},{h}_{N_U2},\dots, {h}_{N_U{N}_{\mathrm{AT}}}\end{array}\right] $$ VA=c1,…,cNAT,cj∈{0,1},∀j∈1,…,NAT$$ {\boldsymbol{V}}_A=\left[{c}_1,\dots, {c}_{N_{\mathrm{AT}}}\right],{c}_j\in \left\{0,1\right\},\forall j\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\} $$ VU=c1,…,cNU,ci∈{0,1},∀i∈1,…,NU$$ {\boldsymbol{V}}_U=\left[{c}_1,\dots, {c}_{N_U}\right],{c}_i\in \left\{0,1\right\},\forall i\in \left\{1,\dots, {N}_U\right\} $$ MUA=c11,c12,…,c1NAT…cNU1,cNU2,…,cNUNAT,cij∈{0,1},∀i∈1,…,NU,∀j∈1,…,NAT$$ {\displaystyle \begin{array}{ll}{\boldsymbol{M}}_{UA}& =\left[\begin{array}{c}{c}_{11},{c}_{12},\dots, {c}_{1{N}_{\mathrm{AT}}}\\ {}\dots \\ {}{c}_{N_U1},{c}_{N_U2},\dots, {c}_{N_U{N}_{\mathrm{AT}}}\end{array}\right],\\ {}& \kern1em {c}_{ij}\in \left\{0,1\right\},\forall i\in \left\{1,\dots, {N}_U\right\},\forall j\in \left\{1,\dots, {N}_{\mathrm{AT}}\right\}\end{array}} $$

Step 2: Make the Throughput Matrix

Make NUS×NAS$$ \left({N}_{US}\times {N}_{AS}\right) $$-dimension throughput matrix using (15) and (16).

Step 3: Resize the Throughput Matrix

If all elements of a column are below the throughput threshold level, RBth$$ {R_B}_{\mathrm{th}} $$, then that column (associated AP) should be deleted and NAS=NAS−1$$ {N}_{\mathrm{AS}}={N}_{\mathrm{AS}}-1 $$. If all elements of a row are below the threshold level, that row (the associated user equipment) must be removed and NUS=NUS−1$$ {N}_{\mathrm{US}}={N}_{\mathrm{US}}-1 $$. If NAS=0$$ {N}_{\mathrm{AS}}=0 $$ or NUS=0$$ {N}_{\mathrm{US}}=0 $$, terminate the algorithm. Otherwise, go to the next step.

Step 4: Refresh the Throughput Matrix

Refresh NUS×NAS$$ {N}_{\mathrm{US}}\times {N}_{\mathrm{AS}} $$ throughput matrix only considering NUS$$ {N}_{\mathrm{US}} $$ number of UEs and NAS$$ {N}_{\mathrm{AS}} $$ number of APs at the output of Step 3, and combining the effect of APs assigned to active links in the previous iterations. Change elements below the threshold level to (−Inf)$$ \left(-\mathrm{Inf}\right) $$.

Step 5: Run the KM Assignment Algorithm

Run the KM resource allocation algorithm to assign the NUS$$ {N}_{\mathrm{US}} $$ number of access points to the NUS$$ {N}_{\mathrm{US}} $$ number of user equipment that supports the maximum total throughput of these new NUS$$ {N}_{\mathrm{US}} $$ links.

Step 6: Update the Scalars, Vectors, and Matrices

Update VU$$ {\boldsymbol{V}}_U $$ to show the connected and remaining UEs, VA$$ {\boldsymbol{V}}_A $$ to show the assigned and remaining APs, MUA$$ {\boldsymbol{M}}_{\mathrm{UA}} $$ to show AP-UE links, NUR=NUR−NUS$$ {N}_{\mathrm{UR}}={N}_{\mathrm{UR}}-{N}_{\mathrm{US}} $$, NAR=NAR−NAS$$ {N}_{\mathrm{AR}}={N}_{\mathrm{AR}}-{N}_{\mathrm{AS}} $$. Refresh the throughput of NU−NUR$$ \left({N}_U-{N}_{\mathrm{UR}}\right) $$ links. If NUR=0$$ {N}_{\mathrm{UR}}=0 $$, finish the algorithm. Otherwise, go to the next step.

Step 7: Check the Remaining Access Points

Check the remaining access points from 1 to NAT−NU−NUR$$ \left({N}_{\mathrm{AT}}-\left({N}_U-{N}_{\mathrm{UR}}\right)\right) $$. The effect of the first access point of this list on the throughput of the NU−NUR$$ \left({N}_U-{N}_{\mathrm{UR}}\right) $$ links that have been extracted before. If enabling this access point reduces the throughput of at least one of the dedicated links below the throughput threshold level, RBth$$ {R_B}_{\mathrm{th}} $$, it should be removed. Otherwise, update the throughput of the previously allocated links in a temporary throughput vector of NU−NUR$$ \left({N}_U-{N}_{\mathrm{UR}}\right) $$ links considering a newly added access point. Do this for the next access points up to the endpoint by checking the last temporary throughput vector of NU−NUR$$ \left({N}_U-{N}_{\mathrm{UR}}\right) $$ links. Therefore, NAS$$ {N}_{\mathrm{AS}} $$ is the number of access points that have affected the temporary throughput vector, and NUS=NUR.$$ {N}_{\mathrm{US}}={N}_{\mathrm{UR}}. $$ If NAS=0$$ {N}_{\mathrm{AS}}=0 $$, finish the algorithm. Otherwise, make NUS×NAS$$ \left({N}_{\mathrm{US}}\times {N}_{\mathrm{AS}}\right) $$-dimension throughput matrix using (15) and (16) considering the effect of APs of the active links selected in the previous iterations and go back to Step 3.

Figure 3 presents the flowchart of the proposed KM-based resource allocation algorithm, which comprises the seven steps described above. Algorithm 1 provides the corresponding pseudocode.

[IMAGE OMITTED. SEE PDF]

ALGORITHM

The Pseudo-Code of the Proposed Kuhn-Munkres-Based Resource Allocation Algorithm.

Input: The number of user equipment N_U, number of access points N_AT, path loss exponent gamma, threshold level R_B,noise variance var_N, distance matrix M_d, channel gain matrix M_h

Initialization: N_US=N_U, N_AS=N_AT, N_UR=N_U, N_AR=N_AT, vector of assigned/non-assigned access points V_A=0, vector of connected/non-connected users V_U=0, matrix of AP-UE links M_UA=0

        Declare N_US×N_AS throughput_matrix

While True do

 Remove all the columns and rows in the throughput_matrix with all values less than R_B

 N_AS=N_AS-removed columns, N_US=N_US-removed rows

 if N_AS=0 or N_US=0 do

  break

 end if

 Refresh the values of the throughput_matrix considering the removed values

 Change all elements of the throughput_matrix less than R_B to -inf

 Apply KM_algorithm on the throughput_matrix

 Refresh values of M_UA, V_A, V_U based on the result of KM_algorithm

 N_UR=N_UR-N_US, N_AR=N_AR-N_AS

 Declare three lists temp_V_A, temp_V_U and throughput_links based on the result of KM_algorithm

 for all items in M_UA equal to 1 do

  calculate value of throughput_links

 end for

 if all items in V_U = 1 do

  N_UR=0

  break

 end if

 Declare temp_throughput_links list

 N_AS = 0

 for all items in V_A do

  if item = 0 do

   Temporarly make item = 1

   Fill the temp_throughput_links list based on this value

   Refresh temp_throughput_links considering the interference of new access points

   if all items in temp_throughput_links >=R_B do

    Add the item to temp_V_A

    N_AS += 1

   end if

  end if

 end for

 if all items in temp_V_A = 0 do

  break

 end if

 for all items in V_U do

  Add the item to temp_V_U if all items in V_U = 0

 end for

 N_US = length(V_U)

 Make new N_US×N_AS throughput_matrix based on temp_V_A, temp_V_U considering the interference of all selected andactive APs

end while

Numerical Analysis and Simulation Results

According to Figure 4, a 250m×250m$$ 250\ m\times 250\ m $$ service area is simulated, containing 250$$ 250 $$ APs and up to 250$$ 250 $$ UEs, randomly distributed. In the simulations, with parameters summarized in Table 1, the number of UEs served by APs varies from 10%$$ 10\% $$ to 100%$$ 100\% $$ of the total APs, both densely and randomly distributed. Using a thresholding process, APs with no UEs within their coverage radius are turned off, and UEs without APs in range are excluded from the assignment process. The path loss exponent is set to 3$$ 3 $$, transmit power to 100mW(20dBm)$$ 100\ \mathrm{mW}\ \left(20\ \mathrm{dBm}\right) $$, and the variances of noise, Rayleigh fading, and Log-normal shadowing are −110dBm$$ -110\ \mathrm{dBm} $$, 0.5$$ 0.5 $$, and 8dB,$$ 8\ \mathrm{dB}, $$ respectively. The minimum acceptable SINR is 10dB$$ 10\ \mathrm{dB} $$, corresponding to a throughput threshold of 3.4594b/s/Hz$$ 3.4594\ \mathrm{b}/\mathrm{s}/\mathrm{Hz} $$ per link.

[IMAGE OMITTED. SEE PDF]

TABLE 1 Symbols in the system model and their values in the numerical analysis.

Symbol Description Value
NU$$ {N}_U $$ Number of user equipment 25−250$$ 25-250 $$
NAT$$ {N}_{\mathrm{AT}} $$ Number of access points 250$$ 250 $$
A$$ A $$ Area of service area 250×250m2$$ 250\times 250\ {m}^2 $$
Pt$$ {P}_t $$ Transmit power 100mW$$ 100\ \mathrm{mW} $$
γ$$ \gamma $$ Path loss exponent 3$$ 3 $$
σn2$$ {\sigma}_n^2 $$ Noise power −110dBm$$ -110\mathrm{dBm} $$
σhf2$$ {\sigma}_{h_f}^2 $$ Rayleigh fading variance 0.5$$ 0.5 $$
σhs2$$ {\sigma}_{h_s}^2 $$ Log-normal shadowing variance 6.31≡8dB$$ 6.31\equiv 8\mathrm{dB} $$
SINRth$$ {\mathrm{SINR}}_{\mathrm{th}} $$ SINR$$ \mathrm{SINR} $$ threshold level 10dB$$ 10\mathrm{dB} $$
RBth$$ {R_B}_{\mathrm{th}} $$ Throughput threshold level 3.4594$$ 3.4594 $$ b/s/Hz$$ \mathrm{b}/\mathrm{s}/\mathrm{Hz} $$
Ns$$ {N}_s $$ Number of random simulations 1000$$ 1000 $$

The population size, iteration limits, and stopping criteria for GA, PSO, CS, and GWO are not fixed; they are typically determined by the problem size, complexity, and the desired trade-off between accuracy and computational cost. In this work, we used the same settings across all algorithms to ensure fairness, with a population size of 200$$ 200 $$ and a maximum of 100$$ 100 $$ iterations. The stopping criterion was defined as reaching the maximum number of iterations or when no further improvement in fitness was observed.

The performance of the proposed KM-based algorithm is evaluated in terms of the number of connected UEs, average throughput per UE, total throughput, and processing time, based on 1000$$ 1000 $$ random simulations. Its results were compared with four metaheuristic algorithms—Genetic, PSO, CS, and GWO. The time complexity of each algorithm is also analyzed and compared with respect to the number of iterations, fitness function evaluations, APs, and UEs. All simulations in MATLAB are run on a 64−bit$$ 64-\mathrm{bit} $$ system, Intel core i7−9750H$$ i7-9750\mathrm{H} $$ with 16GB$$ 16\mathrm{GB} $$ RAM, 12MB$$ 12\mathrm{MB} $$ Cache, and 2.6GHz$$ 2.6\mathrm{GHz} $$ Max. CPU speed.

Number of Connected UEs and Total Throughput

Figure 5 depicts the number of connected users, whereas Figure 6 shows the ratio of connected users to the total number of UEs for varying UE-to-AP ratios. As the number of UEs increases, the absolute number of connected users rises; however, the percentage of connected users decreases due to the higher number of active APs and the resulting increase in interference.

[IMAGE OMITTED. SEE PDF]

[IMAGE OMITTED. SEE PDF]

The proposed KM-based algorithm achieves a higher number of connected UEs compared to the PSO, Genetic, CS, and GWO algorithms, as it effectively controls interference from active APs. By activating the most suitable APs, more UEs can be connected, making the KM-based algorithm a more efficient solution than the other four algorithms.

Figure 7 shows that the total throughput of connected UEs is higher for the proposed KM-based algorithm than for the Genetic, PSO, CS, and GWO algorithms. This improvement is primarily due to the significantly greater number of UEs connected by the KM-based algorithm.

[IMAGE OMITTED. SEE PDF]

Mean Value and the Ratio of the Standard Deviation to the Mean Value of Throughput Per User

Figure 8 depicts the average throughput per UE for the five resource allocation algorithms. The proposed KM-based algorithm achieves higher average throughput than the Genetic and GWO algorithms, but slightly lower than the CS and PSO algorithms. This is because CS and PSO connect fewer users, resulting in higher per-UE throughput, whereas the KM-based, Genetic, and GWO algorithms connect more users, distributing resources among a larger set of UEs (as shown in Figures 4 and 5).

[IMAGE OMITTED. SEE PDF]

For a fair comparison, Figure 9 shows the ratio of the standard deviation to the average throughput per UE for the five resource allocation algorithms. This ratio is higher in the proposed KM-based algorithm, indicating greater variability in throughput among connected UEs. The increased standard deviation arises from the initial AP selection in the KM-based algorithm, whereas Genetic, PSO, CS, and GWO algorithms address this through multiple iterations at the cost of higher processing time. Nevertheless, as shown in Figures 5–7, the KM-based algorithm achieves higher numbers of connected UEs and greater total throughput. In future improvements, introducing a hysteresis mechanism in the throughput threshold during the second step of the algorithm could reduce this ratio by increasing the number of active APs.

[IMAGE OMITTED. SEE PDF]

Time Complexity Order and the Required Elapsed Processing Time to Solve the Optimization Problem

The time complexity order of the proposed KM-based algorithm is given in Equation (32). TCOProp.=OkProp.×nProp.×NAT2$$ {\mathrm{TCO}}_{\mathrm{Prop}.}=O\left({k}_{\mathrm{Prop}.}\times {n}_{\mathrm{Prop}.}\times {N}_{\mathrm{AT}}^2\right) $$ where NATis the number ofAPs,nProp.$$ {N}_{\mathrm{AT}}\ \mathrm{is}\ \mathrm{the}\ \mathrm{number}\ \mathrm{of}\ \mathrm{APs},{n}_{\mathrm{Prop}.} $$ is at most the number of user equipment (UEs), and kProp.$$ {k}_{\mathrm{Prop}.} $$ represents the number of iterations required to find additional AP–UE links. Simulations indicate that kProp.$$ {k}_{\mathrm{Prop}.} $$ is at most 3 or 4 in the worst cases, which does not affect the overall complexity order. In other words, the computational complexity of the proposed seven-step KM-based algorithm remains in the same order as that of the original single-step KM-based algorithm.

For the Genetic algorithm, the TCO can be expressed as Equation (33). TCOG=OkG×MG×nG×NAT2$$ {\mathrm{TCO}}_G=O\left({k}_G\times {M}_G\times {n}_G\times {N}_{\mathrm{AT}}^2\right) $$ where kG$$ {k}_G $$ denotes the number of iterations, nG$$ {n}_G $$ represents the number of UEs selected by the algorithm, and MG$$ {M}_G $$ is the number of fitness function evaluations in each iteration.

The time complexity order of the PSO algorithm is given in Equation (34). TCOPSO=OkP×MP×nP×NAT2$$ {\mathrm{TCO}}_{\mathrm{PSO}}=O\left({k}_P\times {M}_P\times {n}_P\times {N}_{\mathrm{AT}}^2\right) $$ where kP$$ {k}_P $$ denotes the number of iterations, nP$$ {n}_P $$ represents the number of UEs selected by the algorithm, and MP$$ {M}_P $$ is the number of fitness function evaluations in each iteration.

For the CS algorithm, the time complexity order can be expressed as Equation (35). TCOCS=OkC×MC×nC×NAT2$$ {\mathrm{TCO}}_{\mathrm{CS}}=O\left({k}_C\times {M}_C\times {n}_C\times {N}_{\mathrm{AT}}^2\right) $$ where kC$$ {k}_C $$ denotes the number of iterations, nC$$ {n}_C $$ represents the number of UEs selected, and MC$$ {M}_C $$ denotes the required number of fitness function evaluations in each iteration.

The time complexity order of the GWO algorithm is given in Equation (36). TCOGWO=OkW×MW×nW×NAT2$$ {\mathrm{TCO}}_{\mathrm{GWO}}=O\left({k}_W\times {M}_W\times {n}_W\times {N}_{\mathrm{AT}}^2\right) $$ where kW$$ {k}_W $$ denotes the number of iterations, nW$$ {n}_W $$ represents the number of UEs selected by the algorithm, and MW$$ {M}_W $$ denotes the number of fitness function evaluations required in each iteration.

The differences in the time complexity order of the proposed KM-based, Genetic, PSO, CS, and GWO algorithms arise from two factors: (i) the number of APs selected for resource allocation, and (ii) the number of algorithm repetitions. Moreover, unlike the Genetic, PSO, CS, and GWO algorithms, the proposed KM-based algorithm does not require fitness function evaluations.

Figure 10 shows the elapsed simulation time for these five resource allocation algorithms in a UDN service area with 250$$ 250 $$ APs and varying numbers of UEs from 25$$ 25 $$ to 250$$ 250 $$. Consistent with their time complexity orders, the proposed KM-based algorithm requires significantly less processing time than the Genetic, PSO, CS, and GWO algorithms. This reduction is due to the absence of fitness function evaluations, the smaller number of APs selected for checking, and the fewer iterations required compared to the other algorithms.

[IMAGE OMITTED. SEE PDF]

Conclusion

A seven-step sub-optimal algorithm was proposed to address the non-convex NP-hard resource allocation problem in ultra-dense networks (UDNs) with densely distributed APs and UEs. Based on the Kuhn–Munkres (KM) assignment algorithm, the method was evaluated in a 250m×250m$$ 250\ m\times 250\ m $$ area with randomly distributed 250$$ 250 $$ APs and 10−250$$ 10-250 $$ UEs. The simulation accounted for path loss, additive white Gaussian noise, multipath Rayleigh fading, Log-normal shadowing, and co-channel interference among AP–UE links sharing the same resources. Numerical results show that the proposed KM-based algorithm outperforms Genetic, PSO, CS, and GWO algorithms by achieving more connected UEs, higher total throughput, lower time complexity, and reduced processing time, demonstrating its efficiency for resource allocation in UDNs.

Future Work

The following directions can be considered for the continuation of this research:

  • Neighborhood radius evaluation: Determining the coverage radius of each AP and identifying the APs around each UE in order to exclude UEs outside the coverage area of an AP as well as APs that are too far from a given UE.
  • Interference reduction: In the first step of the proposed KM-based algorithm, we avoid the consideration of interference from all APs by applying a suitable hysteresis in SINR calculation and using an appropriate threshold for the throughput of each link.
  • Sensitivity analysis: Examining the robustness of the five proposed algorithms by introducing random deviations in the relative locations of UEs and APs. Additional standby APs (not limited to on/off operation) can be employed to ensure coverage for UEs that move outside the range of their associated APs.
  • Resource assignment extension: Extending the KM-based algorithm to handle resource assignment when each AP is equipped with multiple orthogonal resources.
  • Two-dimensional clustering: Applying two-dimensional clustering to both APs and UEs within the service area to decompose the UDN resource allocation problem into several smaller problems. Each sub-area cluster of UEs can then be assigned to the corresponding cluster of APs.
  • Incorporating power control mechanisms to enhance energy efficiency, similar to the approach in Ref. [28].

Acknowledgments

This work was supported by Shahid Rajaee Teacher Training University (SRTTU) under grant number 1404.388028(17.03.1404). AP and UE icons are extracted from .

Conflicts of Interest

The authors declare no conflicts of interest.

Data Availability Statement

The data that support the findings of this study are available on request from the corresponding author. The data are not publicly available due to privacy or ethical restrictions.

References

B. U. Kazi and G. A. Wainer, “Next Generation Wireless Cellular Networks: Ultra‐Dense Multi‐Tier and Multi‐Cell Cooperation Perspective,” Wireless Networks 25, no. 4 (2019): 2041–2064, https://doi.org/10.1007/s11276‐018‐1796‐y.

S. Shirvani Moghaddam, “The Past, Present, and Future of the Internet: A Statistical, Technical, and Functional Comparison of Wired/Wireless Fixed/Mobile Internet,” Electronics 13, no. 10 (2024): 1986, https://doi.org/10.3390/electronics13101986.

A. Habibzadeh, S. Shirvani Moghaddam, S. M. Razavizadeh, and M. Shirvanimoghaddam, “Modeling and Analysis of Traffic‐Aware Spectrum Handover Schemes in Cognitive HetNets,” Transactions on Emerging Telecommunications Technologies 28, no. 12 (2017): e3199, https://doi.org/10.1002/ett.3199.

A. Habibzadeh, S. Shirvani Moghaddam, S. M. Razavizadeh, and M. Shirvanimoghaddam, “Analysis and Performance Evaluation of an Efficient Handover Algorithm for Cognitive HetNets,” International Journal of Communication Systems 30, no. 16 (2017): e3315, https://doi.org/10.1002/dac.3315.

S. Shirvani Moghaddam, M. Shirvanimoghaddam, and A. Habibzadeh, “Clustering‐Based Handover and Resource Allocation Schemes for Cognitive Radio Heterogeneous Networks, Presented at the 28th International Telecommunication Networks and Applications Conference (ITNAC), Sydney, Australia, 21‐23,” (2018).

V. Stoynov, V. Poulkov, Z. Valkova‐Jarvis, G. Iliev, and P. Koleva, “Ultra‐Dense Networks: Taxonomy and Key Performance Indicators,” Symmetry 15, no. 1 (2023): 2.

C. Pan, M. Elkashlan, J. Wang, J. Yuan, and L. Hanzo, “User‐Centric C‐RAN Architecture for Ultra‐Dense 5G Networks: Challenges and Methodologies,” IEEE Communications Magazine 56, no. 6 (2018): 14–20, https://doi.org/10.1109/MCOM.2018.

X. Wang, L. Kong, F. Kong, et al., “Millimeter Wave Communication: A Comprehensive Survey,” IEEE Communications Surveys & Tutorials 20, no. 3 (2018): 1616–1653, https://doi.org/10.1109/COMST.2018.2844322.

Y. Teng, M. Liu, F. R. Yu, V. C. M. Leung, M. Song, and Y. Zhang, “Resource Allocation for Ultra‐Dense Networks: A Survey, Some Research Issues and Challenges,” IEEE Communications Surveys & Tutorials 21, no. 3 (2019): 2134–2168, https://doi.org/10.1109/COMST.2018.2867268.

N. Sharma and K. Kumar, “Resource Allocation Trends for Ultra Dense Networks in 5G and Beyond Networks: A Classification and Comprehensive Survey,” Physical Communication 48 (2021): 101415, https://doi.org/10.1016/j.phycom.2021.101415.

T. T. Bui, L. D. Nguyen, H. H. Kha, N.‐S. Vo, and T. Q. Duong, “Joint Clustering and Resource Allocation Optimization in Ultra‐Dense Networks With Multiple Drones as Small Cells Using Game Theory,” Sensors 23 (2023): 3899, https://doi.org/10.3390/s23083899.

Y. Zhou, Z. M. Fadlullah, B. Mao, and N. Kato, “A Deep‐Learning‐Based Radio Resource Assignment Technique for 5G Ultra Dense Networks,” IEEE Network 32, no. 6 (2018): 28–34, https://doi.org/10.1109/MNET.2018.1800085.

Z. Ye, “Intelligent Resource Allocation for Ultradense Networks Based on Improved Reinforcement Learning,” Scientific Programming 2022 (2022): 9312847, https://doi.org/10.1155/2022/9312847.

H. W. Kuhn, “The Hungarian Method for the Assignment Problem,” Naval Research Logistics Quarterly 2, no. 1–2 (1955): 83–97, https://doi.org/10.1002/nav.3800020109.

H. W. Kuhn, “Variants of the Hungarian Method for Assignment Problems,” Naval Research Logistics Quarterly 3, no. 4 (1956): 253–258.

J. Munkres, “Algorithms for the Assignment and Transportation Problems,” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (1957): 32–38, https://doi.org/10.1137/0105003.

M. Hosseini and S. Shirvani Moghaddam, “Sub‐Optimum Radio Resource Allocation in Vehicle‐To‐Vehicle Communications Based on a Multi‐Step Hungarian Algorithm, Presented at the IEEE Workshop on Microwave Theory and Techniques in Wireless Communications (MTTW), Riga, Latvia, 7‐8 Oct,” (2021).

S. Shirvani Moghaddam and N. Afzalkhani, “A Munkres‐Based D2D Resource Allocation Algorithm Aware of Cluster Information, Presented at the IEEE Workshop on Microwave Theory and Techniques in Wireless Communications (MTTW), Riga, Latvia, 5‐7 Oct,” (2022).

S. Shirvani Moghaddam, “Chapter 1: Introductory: Primary and Secondary Users in Cognitive Radio‐Based Wireless Communication Systems,” in Cognitive Radio in 4G/5G Wireless Communication Systems (IntechOpen Publisher, 2018), 1–12.

S. Shirvani Moghaddam, Cognitive Radio in 4G/5G Wireless Communication Systems (IntechOpen Publisher, 2018).

K. Shirvani Moghaddam and S. Shirvani Moghaddam, “Sorting Algorithm for Medium and Large Data Sets Based on Multi‐Level Independent Subarrays, Presented at the 10th IEEE International Conference on Communications, Network, and Satellite (COMNETSAT), Purwokerto, Indonesia, 17‐18 July,” (2021).

S. Shirvani Moghaddam and K. Shirvani Moghaddam, “A Threshold‐Based Sorting Algorithm for Dense Wireless Communication Networks,” IET Wireless Sensor Systems 13, no. 2 (2023): 37–47, https://doi.org/10.1049/wss2.12048.

S. Shirvani Moghaddam and K. Shirvani Moghaddam, “A General Framework for Sorting Large Data Sets Using Independent Subarrays of Approximately Equal Length,” IEEE Access 10 (2022): 11584–11607, https://doi.org/10.1109/ACCESS.2022.3145981.

S. Shirvani Moghaddam and K. Shirvani Moghaddam, “On the Performance of Mean‐Based Sort for Large Data Sets,” IEEE Access 9 (2021): 37418–37430, https://doi.org/10.1109/ACCESS.2021.3063205.

K. Shirvani Moghaddam and S. Shirvani Moghaddam, “A Fast Sub‐Optimum Access Point Selection in Ultra‐Dense Networks, Presented at the 10th IEEE International Conference on Communications, Network, and Satellite (COMNETSAT), Purwokerto, Indonesia, 17‐18 July,” (2021).

S. Shirvani Moghaddam and K. Shirvani Moghaddam, “Efficient Base‐Centric/User‐Centric Clustering Algorithm Based on Thresholding and Sorting, Presented at the 14th IEEE International Conference on Innovations in Information Technology (IIT), AlAin, UAE, 17–18 Nov,” (2020).

S. Shirvani Moghaddam and E. Ashoor, “Kuhn‐Munkres‐Based Sub‐Optimum Resource Allocation Algorithm for Ultra‐Dense Networks,” In Presented at the 11th International Symposium on Telecommunication (IST) (IEEE, 2024), 9–10.

J. Galeano‐Brajones, F. Luna‐Valero, J. Carmona‐Murillo, P. H. Zapata Cano, and J. F. Valenzuela‐Valdes, “Designing Problem‐Specific Operators for Solving the Cell Switch‐Off Problem in Ultra‐Dense 5G Networks With Hybrid MOEAs,” Swarm and Evolutionary Computation 78 (2023): 101290, https://doi.org/10.1016/j.swevo.2023.101290.

Y.‐F. Liu, T.‐H. Chang, M. Hong, et al., “A Survey of Recent Advances in Optimization Methods for Wireless Communications,” IEEE Journal on Selected Areas in Communications 42, no. 11 (2024): 2992–3031, https://doi.org/10.1109/JSAC.2024.3443759.

A. Goldsmith, Wireless Communications, 1st ed. (Cambridge University Press, 2005).

J. G. Proakis and M. Salehi, Digital Communications, 5th ed. (McGraw‐Hill, 2007).

A. Papoulis and S. U. Pillai, Probability, Random Variables, and Stochastic Processes, 4th ed. (McGraw‐Hill, 2002).

C. Serodio, J. Cunha, G. Candela, S. Rodriguez, X. R. Sousa, and F. Branco, “The 6G Ecosystem as Support for IoE and Private Networks: Vision, Requirements, and Challenges,” Future Internet 15, no. 11 (2023): 348, https://doi.org/10.3390/fi15110348.

S. Shirvani Moghaddam and M. Ghasemi, “A Low‐Complex/High‐Throughput Resource Allocation for Multicast D2D Communications, Presented at the 7th International Conference on Computer and Communication Engineering (ICCCE), Kuala Lumpur, Malaysia, 19‐20 Sept,” (2018).

A. K. Das, S. Sengupta, and S. Bhattacharyya, “A Group Incremental Feature Selection for Classification Using Rough Set Theory Based Genetic Algorithm,” Applied Soft Computing 65 (2018): 400–411, https://doi.org/10.1016/j.asoc.2018.01.040.

W. Qian, J. Chai, Z. Xu, and Z. Zhang, “Differential Evolution Algorithm With Multiple Mutation Strategies Based on Roulette Wheel Selection,” Applied Intelligence 48, no. 10 (2018): 3612–3629, https://doi.org/10.1007/s10489‐018‐1153‐y.

J. Li, Q. Pan, and K. Mao, “Hybrid PSO Optimization for Hybrid Flowshop Scheduling Problem With Maintenance Activities,” Scientific World Journal 2014 (2014): 596850, https://doi.org/10.1155/2014/596850.

X.‐S. Yang and S. Deb, “Cuckoo Search via Lévy Flights,” In Presented at the World Congress on Nature & Biologically Inspired Computing (NaBIC) (IEEE, 2009), 9–11.

A. H. Gandomi, X. S. Yang, and A. H. Alavi, “Cuckoo Search Algorithm: A Metaheuristic Approach to Solve Structural Optimization Problems,” Engineering With Computers 29 (2013): 17–35, https://doi.org/10.1007/s00366‐011‐0241‐y.

S. Mirjalili, “How Effective Is the Grey Wolf Optimizer in Training Multi‐Layer Perceptrons,” Applied Intelligence 43 (2015): 150–161, https://doi.org/10.1007/s10489‐014‐0645‐7.

S. Saremi, S. Z. Mirjalili, and S. M. Mirjalili, “Evolutionary Population Dynamics and Grey Wolf Optimizer,” Neural Computing and Applications 26 (2015): 1257–1263, https://doi.org/10.1007/s00521‐014‐1806‐7.

Word count: 7860

Show less

© 2025. This work is published under http://creativecommons.org/licenses/by/4.0/ (the "License"). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.