# Delay-aware Multiple Access Design for Intelligent Reflecting Surface Aided
Uplink Transmission

Piao Zeng, Guangji Chen, Qingqing Wu, , Deli Qiao, and Abbas Jamalipour P.
Zeng is with the School of Communication and Electronic Engineering, East
China Normal University, Shanghai, China (e-mail:
52181214005@stu.ecnu.edu.cn). G. Chen is with the State Key Laboratory of
Internet of Things for Smart City, University of Macau, Macau, China (email:
guangjichen@um.edu.mo). Q. Wu is with the Department of Electronic
Engineering, Shanghai Jiao Tong University, Shanghai, China (e-mail:
qingqingwu@sjtu.edu.cn). D. Qiao is with the School of Communication and
Electronic Engineering, East China Normal University, Shanghai, China, and
also with the National Mobile Communications Research Laboratory, Southeast
University, Nanjing, China (e-mail: dlqiao@ce.ecnu.edu.cn). Abbas Jamalipour
is with the School of Electrical and Information Engineering, The University
of Sydney, Sydney, NSW 2006, Australia (e-mail: a.jamalipour@ieee.org).

###### Abstract

In this paper, we develop a hybrid multiple access (MA) protocol for an
intelligent reflecting surface (IRS) aided uplink transmission network by
incorporating the IRS-aided time-division MA (I-TDMA) protocol and the IRS-
aided non-orthogonal MA (I-NOMA) protocol as special cases. Two typical
communication scenarios, namely the transmit power limited case and the
transmit energy limited case are considered, where the device’s rearranged
order, time and power allocation, as well as dynamic IRS beamforming patterns
over time are jointly optimized to minimize the sum transmission delay. To
shed light on the superiority of the proposed IRS-aided hybrid MA (I-HMA)
protocol over conventional protocols, the conditions under which I-HMA
outperforms I-TDMA and I-NOMA are revealed by characterizing their
corresponding optimal solution. Then, a computationally efficient algorithm is
proposed to obtain the high-quality solution to the corresponding optimization
problems. Simulation results validate our theoretical findings, demonstrate
the superiority of the proposed design, and draw some useful insights.
Specifically, it is found that the proposed protocol can significantly reduce
the sum transmission delay by combining the additional gain of dynamic IRS
beamforming with the high spectral efficiency of NOMA, which thus reveals that
integrating IRS into the proposed HMA protocol is an effective solution for
delay-aware optimization. Furthermore, it reveals that the proposed design
reduces the time consumption not only from the system-centric view, but also
from the device-centric view.

###### Index Terms:

Delay minimization, intelligent reflecting surface (IRS), multiple access
(MA), uplink (UL) transmission.

##  I Introduction

Under the trends in establishing the Internet-of-Things (IoT) ecosystem, the
next generation wireless networks are expected to support an unprecedentedly
large number of connections [1]. To accommodate the growing demands of
connectivity, the multiple access (MA) technique is one of the most
fundamental enablers for facilitating data transmission from massive IoT
devices to the access point (AP) or the base station (BS). The existing MA
techniques can be loosely classified into two categories, namely the
orthogonal multiple access (OMA) and non-orthogonal multiple access (NOMA).
Different from OMA where one resource block (in time, frequency, or code) is
occupied by at most one user, NOMA allows different users to share the same
time/frequency resources and to be multiplexed in different power levels by
invoking superposition coding and successive interference cancellation (SIC)
techniques [2, 3, 4, 5].

In general, the optimal choice of MA protocols may change in terms of
different application scenarios and objectives. For example, for the transmit
power limited system, the authors in [6] theoretically compared the optimum
sum-rate performance for NOMA and OMA systems with the consideration of user
fairness, which revealed that NOMA always achieves better performance than the
conventional OMA. Apart from the single-input single-output system as studied
in [6], the authors in [7] investigated the performance of a multiple-input
multiple-output NOMA network and analytically proved the superiority of
employing NOMA over OMA in terms of both sum channel capacity and ergodic sum
capacity. In contrast, for the transmit energy limited system, the authors in
[8] proved that the NOMA strategy is neither spectral efficient nor energy
efficient when the circuit energy consumption is non-negligible for IoT
devices, e.g. in wireless powered communication networks. Furthermore, the
error propagation of SIC in NOMA may become more severe as the number of users
increases [9]. Apart from the clustered hybrid MA scheme proposed in [9], the
authors in [10] designed a two-user paired hybrid NOMA scheme to minimize the
sum transmission delay for a mobile edge computing (MEC) system. As a
generalization of [10], the authors in [11] and [12] extended the two-user
scenario to a multi-user one via an iterative procedure and a grouping
strategy, respectively. A more general MA strategy for multiple users was
developed in [13] by including pure OMA and pure NOMA strategy as special
cases.

Although the efficiency of the transmission can be improved with well-designed
MA schemes, the throughput of the transmission will degrade severely due to
the attenuation of the wireless channels between transceivers, which thus
limits the performance of IoT networks. Fortunately, thanks to the significant
progress in electrocircuit and metamaterial [14], intelligent reflecting
surface (IRS) has recently emerged as a promising technology to improve the
spectral and energy efficiency for the next generation wireless networks[15].
Specifically, with the assistance of a large number of software-controlled
reconfigurable passive elements, the IRS can modify the phase shift and/or the
amplitude of the incident signals intelligently so as to create a favorable
signal propagation environment [16]. Benefiting from the unique physical
structure, IRS has the great potential to solve the existing issues in
wireless communications [17], which has attracted intensive research interest
[18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]. For example, the
authors in [20] presented the relationship of minimum transmit powers required
by different MA schemes in the IRS-assisted wireless network. Specifically,
the results in [20] showed that the performance comparison between NOMA and
time-division MA (TDMA) in the IRS-assisted system depends on the target rates
and locations of the users, which is not fully comply with the conclusions in
conventional systems without IRS. To achieve the delay-optimal users’
scheduling for an IRS-aided MEC system, the authors in [21] proposed a
flexible time-sharing NOMA scheme, which suggested that different from the
case without IRS, the performance gap between the NOMA and TDMA benchmarks
with IRS is much smaller. Moreover, there are also works on IRS-aided multi-
user communications with other MA strategies, such as rate-splitting MA
schemes [23], beam/angle schemes division MA [24, 25], and sparse code MA
schemes [26].

Despite of the above works, some fundamental issues still remain to be
explored in IRS-aided IoT networks. First, as the transmission delay has
become a critical bottleneck that limits the progress of the newly emerged
latency-sensitive applications in the IoT networks, such as virtual reality
and autonomous driving, delay-aware optimization is of great practical
significance. However, the related design for the new paradigm of IRS-aided
systems is still in its infancy. Thus, this calls for the efforts to establish
a more advanced MA protocol to fully reap the potential performance gain of
employing the IRS to assist the multi-device uplink (UL) transmission
networks. On one hand, under the conventional TDMA protocol, the IRS can
achieve additional beamforming (BF) gain by employing multiple IRS BF patterns
in a channel coherence interval, i.e., dynamic IRS BF [18], which is shown to
outperform NOMA in the aspect of spectral efficiency [19]. On the other hand,
under the conventional NOMA protocol, the delay of the UL transmission can be
significantly reduced compared with the TDMA protocol [10]. Considering the
above factors, it deserves dedicated work to custom design a proper MA scheme
for the IRS-aided system to minimize the sum UL transmission delay. Second,
how to enable more flexible resource allocation and IRS BF design to minimize
the sum transmission delay of the system? This question is driven by the fact
that, unlike conventional transmission networks, the use of IRS provides new
degrees of freedom (DoFs) to combat the undesired channel condition and
further reduce the transmission delay. Nevertheless, it also introduces new
optimization variables and makes the IRS BF vectors and transmit power of each
device as well as the time allocation closely coupled in the constraints, thus
rendering the joint design of the IRS BF and resource allocation more
challenging than that in conventional networks.

Motivated by the above issues, in this work, we focus on the MA design for an
IRS-aided delay-sensitive UL transmission system where an IRS is deployed to
assist the UL transmission from multiple IoT devices to a BS, as shown in Fig.
LABEL:fig:Channel. To fully reap the advantages of utilizing the IRS in
minimizing the transmission delay of the entire UL transmission period, we
propose an IRS-aided hybrid MA (HMA) UL transmission protocol by exploiting
the flexibility in resource allocation and IRS BF of the TDMA protocol, as
well as the high spectral efficiency of the NOMA protocol, where the device’s
rearranged order, time and power allocation, as well as IRS BF patterns are
optimized jointly. It is worth noting that unlike the toy example of two-user
based hybrid NOMA protocol shown in [10, 11, 21], we present a more general
multi-device HMA UL transmission protocol, where multiple devices can transmit
their desired signals to the BS simultaneously. Furthermore, different from
the design in [13, 10, 11], our proposed IRS-aided HMA (I-HMA) protocol takes
the dynamic BF gain of IRS into account, which is able to reap additional
advantages to minimize the sum transmission delay. Note that by properly
designing the BF patterns over different time slots, the channels of all
devices are no longer random and can be time-varying throughout each channel
coherence block, which is different from the conventional systems without IRS
as investigated in [13, 10, 11]. The time-division and resources reuse
mechanism in our proposed I-HMA protocol provides more flexibility in the
system design, which however imposes new challenges for the theoretical
analysis and optimization. The main contributions of this work are detailed as
follows.

  * •

To exploit the time-selective channels introduced by dynamic IRS BF, as well
as the high spectral-efficiency of NOMA protocol, an I-HMA protocol is
developed for UL transmission by allowing multiple devices to transmit their
desired signals to the BS simultaneously, which is different from the IRS-
aided TDMA (I-TDMA) protocol. On the other hand, unlike the IRS-aided NOMA
(I-NOMA) protocol, which enforces all the devices to transmit concurrently
during the entire period, the proposed protocol provides more flexibility for
each device to choose its stop-time once it finishes its required transmission
task and the possibility to vary its transmit powers as well as the IRS BF
patterns among different time slots.

  * •

Two typical communication scenarios are investigated in this work, namely the
transmit power limited case and the transmit energy limited case111For power
limited system, the devices are limited by a peak power constraint, such as
conventional wireless communication scenarios. Whereas for energy limited
systems, the devices only have a certain amount of energy, such as wireless
sensor networks, or energy harvesting scenarios, or dedicated wireless power
transmissions.. To shed light on the superiority of our proposed I-HMA
protocol over the I-TDMA and I-NOMA protocols, we characterize the minimum
achievable delay of the corresponding MA protocols and unveil the relationship
among the proposed I-HMA protocol and the other two special cases (I-TDMA and
I-NOMA), which provides a useful guideline to simplify the optimization.

  * •

For the transmit power limited delay minimization, it is found that the
maximum power transmission (MPT) strategy is the optimal solution for the last
device under the proposed protocol. Besides, it is proved that the proposed
I-HMA protocol always outperforms the I-TDMA protocol, whereas the proposed
I-HMA protocol outperforms the I-NOMA protocol when the required transmission
throughput for the latter devices is larger than a threshold. In contrast, for
the transmit energy limited system, the proposed I-HMA protocol will reduce to
the I-NOMA or I-TDMA protocol if the device’s initial energy is sufficiently
large or extremely low, respectively. We also derive the conditions under
which the proposed I-HMA outperforms I-TDMA and I-NOMA.

  * •

To solve the formulated challenging optimization problems under the proposed
framework, we first provide a generic solution for the original problems,
where an efficient device’s ordering principle is proposed, and the other
variables are optimized via an alternating optimization (AO)-based method.
Specifically, with the given device’s order, the original problem is
decomposed into two problems, namely resource allocation optimization and IRS
BF optimization. Based on the successive convex approximation (SCA)
transformations and fractional programming (FP) method, each subproblem is
optimized in an iterative way until convergence is achieved. Furthermore, we
present the solution for the special cases, namely the I-TDMA and the I-NOMA
based optimization problems.

  * •

Simulation results validate our theoretical findings and demonstrate the
significant performance gains achieved by the proposed protocol. In
particular, 1) it is shown that the performance gap between the proposed I-HMA
and I-NOMA under the asymmetric deployment is wider than its counterpart under
the symmetric deployment, which indicates that the NOMA protocol in our
proposed I-HMA protocol plays a more prominent role under the asymmetric
deployment; 2) it reveals that significant performance gain can be achieved by
employing dynamic IRS BF compared with static IRS BF even with a small size of
IRS, which indicates the effectiveness of the proposed dynamic IRS BF design;
3) it is observed that employing the proposed I-HMA protocol reduces the UL
transmission time consumption not only from the system-centric aspect, but
also from the device-centric aspect, which can reduce the energy consumption
for each device.

The rest of the paper is organized as follows. Section II introduces the
system model and the problem formulations for both the transmit power limited
system and the transmit energy limited system. Section III provides the
performance analysis of the proposed I-HMA protocol compared with the I-TDMA
protocol and I-NOMA protocol. The proposed solution and algorithm are provided
in Section IV. Section V presents numerical results to evaluate the
performance of the proposed design and provides some interesting insights.
Finally, we conclude the paper in Section VI.

_Notations:_ Throughout the paper, boldface lowercase letters and boldface
uppercase letters represent vectors and matrices, respectively. Superscripts
$(\cdot)^{{H}}$ represents the Hermitian transpose operator. $|\mathbf{X}|$
denotes the absolute value of a scalar. $\mathbb{C}^{a\times b}$ denotes the
space of $a\times b$ complex matrices. $\mathscr{W}(\cdot)$ denotes the
Lambert W function. $\Re\\{\cdot\\}$ represents the real part of a complex
value. diag$(\cdot)$ denotes the diagonalization operator.

##  II System Model And Problem Formulation

In this paper, we focus on an IRS-aided UL transmission system as shown in
Fig. LABEL:fig:Channel, which consists of a single-antenna BS, an IRS with $N$
reflecting elements and $K$ single-antenna devices. Note that it can be
readily extended to the case with multiple antennas at the BS by incorporating
the receive beamforming design at the BS, which has been extensively studied
in existing works. The equivalent baseband channels from device $k$ to the
IRS, from the IRS to the BS, and from device $k$ to the BS are denoted by
$\bm{h}_{r,k}\in\mathbb{C}^{N\times 1}$, $\bm{g}\in\mathbb{C}^{N\times 1}$,
and $h_{d,k}\in\mathbb{C}$, $\forall
k\in\mathcal{K}\triangleq\\{1,\cdots,K\\}$, respectively. To characterize the
maximum achievable performance, the channel state information (CSI) of the
direct links and cascaded links is assumed to be available at the
transceivers, which can be obtained by utilizing the techniques proposed in
[33, 34, 35, 36, 37]. The extension to the case of the imperfect CSI will be
left for future work. Besides, all the wireless channels are assumed to be
quasi-static flat-fading and remain constant within the transmission period.

###  II-A UL Transmission Protocol

To exploit the favorable time-selective channels introduced by dynamic IRS BF
as well as the high spectral efficiency of NOMA, in this work, we propose an
I-HMA UL transmission protocol as shown in Fig. LABEL:fig:HNOMA, which
combines the advantage of the I-NOMA and I-TDMA protocols.222Existing
techniques can be utilized for synchronization, whereas the investigation for
the case of imperfect synchronization will be left as our future work. This
idea comes from the observation that the “one device at a time” mechanism in
the I-TDMA protocol will result in a relatively long delay for the entire UL
transmission since the other devices need to wait until the current activated
device finishes its transmission task. Specifically, under the I-TDMA protocol
as shown in Fig. LABEL:fig:TDMA, all the devices are arranged in a sequence to
transmit their information data successively. To distinct such transmitting
order from the device’s original index, we use $\pi(\cdot)$ to denote the
inverse function that maps the rearranged order index to the device’s original
index, and use $D_{\pi(k)}$ to represent the device that in the $k$-th order
to execute its transmission under the conventional TDMA protocol with the
original index denoted by ${\pi(k)}$ as shown in Fig. LABEL:fig:TDMA.

To make the best use of the waiting time in TDMA-based UL transmission, we
consider to introduce the NOMA technology for the UL transmission so as to
enable simultaneous transmissions of multiple devices. In particular, given
the rearranged order ${\bm{\pi}}\triangleq\\{\pi(1),\cdots,\pi(K)\\}$, unlike
the conventional TDMA protocol as shown in Fig. LABEL:fig:TDMA, where
$D_{\pi(k)}$ needs to wait until the former $k-1$ devices, i.e.,
$D_{\pi(1)},\cdots,D_{\pi(k-1)}$, finish their transmission and can only
transmit during $\tau_{k}$, the proposed HMA protocol allows $D_{\pi(k)}$ to
utilize its waiting time, i.e., $\sum_{i=1}^{k-1}\tau_{i}$, as well as
$\tau_{k}$ for UL transmission, which means that $D_{\pi(k)}$ can occupy at
most a time duration of $\sum_{i=1}^{k}\tau_{i}$ for its transmission. And the
user will stop immediately after finishing its own transmission task.
Moreover, to reap the additional dynamic BF gain of the IRS as revealed in
[18], it is assumed that the IRS can reconfigure its reflecting elements
dynamically among different time slots.333In this paper, we assume that the
IoT devices are static or moving slowly, which is also one of the most typical
scenarios for the application of IRS. In this case, the channel coherence time
is about on the order of 25 milliseconds [38]. In addition, as reported in
[39], the minimum recovery time of PIN diode can be designed to be as small as
a few nanoseconds, enabling a maximum radiation pattern changing speed with
hundreds of MHz. Therefore, it is practical to assume that the IRS reflection
matrix can be reconfigured multiple times within the channel coherence time.

As such, compared to the I-TDMA protocol, the proposed I-HMA protocol allows
$K-(k-1)$ devices, i.e., $D_{\pi(k)},\cdots,D_{\pi(K)}$, to transmit their
desired information data to the BS simultaneously via the assistance of IRS in
the $k$-th time slot. On the other hand, compared to the I-NOMA protocol,
where all users start and end transmission simultaneously, the users may
finish their transmission at different time in the proposed protocol.
Therefore, the proposed protocol can provide more flexibility for each device
to determine its transmission completion time and the possibility to vary its
transmit powers as well as the IRS BF patterns among different time slots.
Note that the transmission power of the devices remains the same during each
time slot and only changes among different time slots. And the BS will decode
each device’s signal successively by utilizing SIC in each time slot.

###  II-B Achievable Throughput

For our proposed I-HMA UL transmission protocol, the signal received at the BS
with the aid of the IRS in the $i$-th time slot can be expressed as

$\displaystyle y_{i}$
$\displaystyle=\sum_{k=i}^{K}\sqrt{p_{\pi(k),i}}(h_{d,\pi(k)}+\bm{g}^{H}\bm{\Phi}_{i}\bm{h}_{r,\pi(k)})s_{\pi(k),i}+n_{i}=\sum_{k=i}^{K}\sqrt{p_{\pi(k),i}}\bm{b}_{\pi(k)}^{H}{\bf{v}}_{i}s_{\pi(k),i}+n_{i},$
(1)

where $\bm{b}_{\pi(k)}\in\mathbb{C}^{(N+1)\times 1}$ denotes the composite
channel of $D_{\pi(k)}$, which is given by
$\bm{b}_{\pi(k)}^{H}\triangleq[\bm{g}^{H}\text{diag}(\bm{h}_{r,\pi(k)}),h_{d,\pi(k)}]$.
$\bm{\Phi}_{i}\triangleq\text{diag}([e^{j\theta_{i,1}},\cdots,e^{j\theta_{i,N}}])$
denotes the diagonal IRS BF coefficient matrix in the $i$-th time slot. And
${\bf{v}}_{i}$ is defined as
${\bf{v}}_{i}^{H}\triangleq[e^{-j\theta_{i,1}},\cdots,e^{-j\theta_{i,N}},1]$.
Besides, $p_{\pi(k),i}$ and $s_{\pi(k),i}$ denote the transmit power and
signal of $D_{\pi(k)}$ in the $i$-th time slot, respectively. $n_{i}$ denotes
the additive white Gaussian noise with the power denoted by $\sigma^{2}$.

To decode ${\pi(k)}$-th device’s signal, $\forall k\in\\{i,\cdots,K\\}$, from
the composite signals from $D_{\pi(i)},\cdots,$ $D_{\pi(K)}$ in the $i$-th
time slot, the SIC is employed at the BS444Regarding the case of imperfect
SIC, the proposed algorithm is still applicable by making some transformation.
We will make a deeper investigation to this scenario in our future work.. And
it is assumed that the BS first decodes the signal of the device with a larger
order so as to ensure the device with prior order experiences smaller
interference, i.e., the BS decodes $D_{\pi(j)}$’s signal before decodes
$D_{\pi(i)}$’s signal, $\forall j>i$. As such, the achievable throughput of
$D_{\pi(k)}$ in bits in the $i$-th time slot $\tau_{i}$ can be calculated as

$\displaystyle\tau_{i}\hskip
1.42271ptr_{\pi(k),i}=\begin{cases}\tau_{i}B\log_{2}\left(1+\frac{p_{\pi(k),i}|\bm{b}_{\pi(k)}^{H}{\bf{v}}_{i}|^{2}}{\sum_{j=i}^{k-1}p_{\pi(j),i}|\bm{b}_{\pi(j)}^{H}{\bf{v}}_{i}|^{2}+\sigma^{2}}\right),&i<k,\\\
\tau_{i}B\log_{2}\left(1+{p_{\pi(k),i}|\bm{b}_{\pi(k)}^{H}{\bf{v}}_{i}|^{2}}/{\sigma^{2}}\right),&i=k,\end{cases}$
(2)

where $B$ denotes the transmission bandwidth. It can be seen in (2) that,
since the BS decodes all the other device’s signals before decoding the
${\pi(k)}$-th device’s signal for the signals received in the $k$-th time
slot, $D_{\pi(k)}$ will experience interference-free transmission as that in
TDMA during $\tau_{k}$. On the other hand, it is worth noting that
$D_{\pi(k)}$ can occupy at most a time duration of $\sum_{i=1}^{k}\tau_{i}$
for transmission with the proposed I-HMA protocol. Thus, its total achievable
throughput can be calculated as $\sum_{i=1}^{k}\tau_{i}r_{{\pi(k)},i}$.

###  II-C Problem Formulations

Without loss of generality, two typical communication scenarios are
investigated, namely the 1) transmit power limited case and 2) the transmit
energy limited case. For brevity, denote
$\mathcal{N}\triangleq\\{1,\cdots,N\\}$,
$\mathcal{I}(k)\triangleq\\{1,\cdots,k\\}$, and ${\bm{\Pi}}$ as the set of all
possible device’s rearranged order with $|{\bm{\Pi}}|=K!$. Besides, let
${\bm{p}}\triangleq\\{p_{\pi(k),i}\hskip 1.42271pt|\hskip 2.84544pt\forall
i\in\mathcal{I}(k),\forall k\in\mathcal{K}\\}$,
${\bm{\Psi}}\triangleq\\{{\bf{v}}_{1},\cdots,{\bf{v}}_{K}\\}$, and
${\bm{\tau}}\triangleq\\{\tau_{1},\cdots,\tau_{K}\\}$. Our goal is to minimize
the sum transmission delay during the whole UL transmission frame, by jointly
optimizing the device’s rearranged order ${\bm{\pi}}$, time allocation
${\bm{\tau}}$, transmit power ${\bm{p}}$ and IRS BF patterns set
${\bm{\Psi}}$.

1) Transmit Power Limited Delay Minimization: For the transmit power limited
case, each device is powered by a stable source, and its transmit power is
limited by the source’s maximum output power $P_{\pi(k)}^{\hskip
0.56917pt\mathsf{m}}$ for $D_{\pi(k)}$. The corresponding optimization problem
is formulated as

$\displaystyle(\text{P}1):\hskip
5.69046pt\underset{{\bm{\pi}},{\bm{\tau}},{\bm{p}},{\bm{\Psi}}}{\min}\hskip
5.69046pt$ $\displaystyle\sum\nolimits_{i=1}^{K}\tau_{i}$ (3a) s.t.
$\displaystyle\sum\nolimits_{i=1}^{k}\tau_{i}r_{{\pi(k)},i}\geq
L_{\pi(k)},\forall k\in\mathcal{K},$ (3b) $\displaystyle 0\leq
p_{{\pi(k)},i}\leq P_{\pi(k)}^{\hskip 0.56917pt\mathsf{m}},\forall
i\in\mathcal{I}(k),\forall k\in\mathcal{K},$ (3c) $\displaystyle\tau_{i}\geq
0,\forall i\in\mathcal{K},$ (3d)
$\displaystyle\left|\left[{\bf{v}}_{i}\right]_{n}\right|=1,\forall
n\in\mathcal{N},\forall i\in\mathcal{K},$ (3e)
$\displaystyle{\bm{\pi}}\in{\bm{\Pi}}.$ (3f)

In (P1), (3b) denotes the quality-of-service (QoS) constraint, where
$L_{\pi(k)}$ denotes the ${\pi(k)}$-th device’s throughput requirement for the
UL transmission. (3c) and (3d) are the transmit power constraints and the non-
negativity constraints on the optimization variables, respectively. (3e)
denotes the unit-modulus constraints of the IRS phase-shifts vectors. (3f) is
the device’s order constraint.

2) Transmit Energy Limited Delay Minimization: For the transmit energy limited
case, a certain amount of energy $E_{\pi(k)}$ Joule (J) for device
$D_{\pi(k)}$ is available at the beginning of each transmission period which
can be used for its UL transmission. The corresponding optimization problem
can be similarly formulated as

$\displaystyle(\text{P}2):\hskip
5.69046pt\underset{{\bm{\pi}},{\bm{\tau}},{\bm{p}},{\bm{\Psi}}}{\min}\hskip
5.69046pt$ $\displaystyle\sum\nolimits_{i=1}^{K}\tau_{i}$ (4a) s.t.
$\displaystyle(\ref{eq:con_Lk_P1}),(\ref{eq:con_t_noneg_P1}),(\ref{eq:con_v_P1}),(\ref{eq:con_order_P1})$
(4b) $\displaystyle\sum\nolimits_{i=1}^{k}p_{{\pi(k)},i}\tau_{i}\leq
E_{\pi(k)},\forall k\in\mathcal{K},$ (4c) $\displaystyle p_{{\pi(k)},i}\geq
0,\forall i\in\mathcal{I}(k),\forall k\in\mathcal{K},$ (4d)

where (4c) and (4d) are the transmit energy constraint and the non-negativity
constraints on the optimization variables, respectively.

It is worth noting that for the system with $K$ devices, there are $K!$
rearranged orders in total. Moreover, with the assistance of the IRS, the
equivalent channels vary with different IRS BF patterns, which makes the
design of the device’s rearranged order more difficult [40, 22]. Generally,
there are no efficient solutions to determine the optimal device’s order even
in the conventional communication system without IRS. As such, obtaining the
optimal device’s rearranged order requires an exhaustive search over every
possible user ordering, which needs to execute $K!$ times optimization and is
computationally prohibitive with the increase of $K$. Apart from the
difficulty in determining the optimal device’s rearranged order, (P1) and (P2)
are non-convex due to highly coupled optimization variables involved in the
constraint (3b). Moreover, the variables set ${\bm{\tau}}$ in the objective
function is actually an implicit function with respect to (w.r.t.) ${\bm{p}}$
and ${{\bm{\Psi}}}$. As such, problem (P1) and (P2) are difficult to solve
optimally in general. Nevertheless, in the following, we will present an
efficient algorithm to obtain their high-quality solutions. For simplicity, we
denote $\bar{L}_{\pi(k)}$ as the normalized required transmission throughput
in bits/Hz, which is given by $\bar{L}_{\pi(k)}=L_{\pi(k)}/B$, $\forall
k\in\mathcal{K}$, and denote
$\gamma_{k}({\bf{v}})\triangleq|\bm{b}_{{\pi(k)}}^{H}{\bf{v}}|^{2}/\sigma^{2}$.

##  III Performance Analysis

It is worth noting that both I-TDMA and I-NOMA can be viewed as special cases
of the proposed I-HMA protocol. Specifically, on one hand, by setting
$p_{{\pi(j)},i}=0$, $\forall i\in\mathcal{I}(k-1)$, $\forall k\in\mathcal{K}$,
the proposed I-HMA protocol reduces to the I-TDMA protocol. Whereas, by
setting $\tau_{i}=0$, $\forall i\in\\{2,\cdots,K\\}$, the proposed I-HMA
protocol degrades to the I-NOMA protocol. On the other hand, the optimal
solution to the problem with I-TDMA and I-NOMA is always feasible for the
problem with the proposed I-HMA protocol. Thus, the performance of the
proposed I-HMA protocol is no worse than the other two benchmarks. However, it
remains an open problem whether the proposed I-HMA protocol is actually
beneficial for minimizing the sum transmission delay of the whole UL
transmission compared to the other two strategies (I-TDMA and I-NOMA). To
answer this question, in this section, we analyze the performance of the
proposed I-HMA protocol compared with the I-TDMA and I-NOMA protocol under the
transmit power limited case and transmit energy limited case, respectively.

In the following, it is assumed that the analysis is under the given order
${\bm{\pi}}$. Besides, we suppose that $\mathscr{S}^{\hskip
0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}})\triangleq\\{{\bm{\tau}}^{\hskip
0.56917pt\mathsf{hy}^{*}},{\bm{p}}^{\hskip 0.56917pt\mathsf{hy}^{*}}|\hskip
1.42271pt{\bm{\Psi}}\\}$, $\mathscr{S}^{\hskip
0.56917pt\mathsf{td}^{*}}({\bm{\Psi}})\triangleq\\{{\bm{\tau}}^{\hskip
0.56917pt\mathsf{td}^{*}},{\bm{p}}^{\hskip 0.56917pt\mathsf{td}^{*}}|\hskip
1.42271pt{\bm{\Psi}}\\}$, and $\mathscr{S}^{\hskip
0.56917pt\mathsf{no}^{*}}({\bm{\Psi}})\triangleq\\{{\bm{\tau}}^{\hskip
0.56917pt\mathsf{no}^{*}},{\bm{p}}^{\hskip 0.56917pt\mathsf{no}^{*}}|\hskip
1.42271pt{\bm{\Psi}}\\}$555For I-NOMA based solution, it follows that
${\bm{\tau}}^{\hskip 0.56917pt\mathsf{no}}=\tau_{1}$ and ${\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}}={\bf{v}}_{1}$. achieve the optimal solution to the
problem with the proposed I-HMA protocol, with the I-TDMA protocol, and with
the I-NOMA protocol with the IRS BF patterns set ${\bm{\Psi}}$, respectively.
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}})$, $\mathsf{T_{sum}^{td}}({\bm{\Psi}})$,
and $\mathsf{T_{sum}^{no}}({\bm{\Psi}})$ denote the sum transmission delay
achieved at $\mathscr{S}^{\hskip 0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}})$,
$\mathscr{S}^{\hskip 0.56917pt\mathsf{td}^{*}}({\bm{\Psi}})$, and
$\mathscr{S}^{\hskip 0.56917pt\mathsf{no}^{*}}({\bm{\Psi}})$, respectively.
$\mathsf{T_{sum}^{hy^{*}}}$, $\mathsf{T_{sum}^{td^{*}}}$ and
$\mathsf{T_{sum}^{no^{*}}}$ denote the minimum sum transmission delay of
employing the proposed I-HMA protocol, I-TDMA protocol and I-NOMA protocol for
UL transmission, respectively.

###  III-A Transmit Power Limited Case

The optimal performance between the proposed I-HMA protocol and the I-TDMA
protocol can be compared as follows.

######  Proposition 1.

For the transmit power limited system, we have

$\displaystyle\mathsf{T_{sum}^{hy}}({\bm{\Psi}})<\mathsf{T_{sum}^{td}}({\bm{\Psi}}),$
(5a)
$\displaystyle\mathsf{T_{sum}^{hy^{*}}}=\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{hy}^{*}})<\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}^{*}})<\mathsf{T_{sum}^{td}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}^{*}})=\mathsf{T_{sum}^{td^{*}}}.$ (5b)

Proof: Please refer to Appendix A. $\blacksquare$

Proposition 1 shows that given the same ${\bm{\Psi}}$, the sum transmission
delay of employing the I-TDMA protocol is always larger than that with the
proposed I-HMA protocol for UL transmission under the transmit power
constraints, which indicates that the proposed I-HMA protocol always
outperforms the I-TDMA protocol in this scenario. Moreover, with the
assistance of the IRS, the performance gap between the proposed I-HMA protocol
and the I-TDMA protocol becomes larger as indicated by (5b), since introducing
the IRS provides additional DoFs and brings additional gain by properly
optimizing the IRS BF patterns.

For the performance comparison between the proposed I-HMA protocol and the
I-NOMA protocol, we have the following proposition.

######  Proposition 2.

For the transmit power limited system, if
${L}_{\pi(k)}\leq{L}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1}),\forall k>1$, then it follows that

$\mathsf{T_{sum}^{hy}}({\bm{\Psi}})=\mathsf{T_{sum}^{no}}({\bm{\Psi}})={\bar{L}_{\pi(1)}}/\hskip
0.85355pt{\log_{2}\left[1+P_{\pi(1)}^{\hskip
0.56917pt\mathsf{m}}\gamma_{1}({\bf{v}}_{1})\right]},$ (6)

where ${L}_{\pi(k)}^{{\hskip 0.56917pt\mathsf{no}}}({\bf{v}}_{1})$ is defined
as

$\displaystyle{L}_{\pi(k)}^{\hskip
0.56917pt\mathsf{no}}({\bf{v}}_{1})\triangleq{\log_{2}\left[1+\frac{P_{{\pi(k)}}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{k}({\bf{v}}_{1})}{1+\sum_{i=1}^{k-1}P_{{\pi(i)}}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{i}({\bf{v}}_{1})}\right]}{L}_{\pi(1)}\bigg{/}\hskip
0.85355pt{\log_{2}\left[1+P_{\pi(1)}^{\hskip
0.56917pt\mathsf{m}}\gamma_{1}({\bf{v}}_{1})\right]}.$ (7)

Proof: Please refer to Appendix B. $\blacksquare$

Proposition 2 indicates that compared with $L_{\pi(1)}$, if the required
transmission throughput for the latter devices, i.e., $L_{\pi(k)}$, $\forall
k>1$, are relatively small such that can be completed within the first time
slot even when all the devices transmit at their maximum power, the proposed
I-HMA protocol reduces to I-NOMA protocol, and results in the same optimal
solution. In this case, the minimum sum transmission delay is limited by the
$D_{\pi(1)}$. Besides, it can be seen from (7) that the BF patterns of IRS,
i.e., ${\bf{v}}_{1}$, does influence the threshold for the performance gap
between the proposed I-HMA protocol and I-NOMA protocol, which validates the
effect of IRS. Proposition 2 provides a region where the performance of the
proposed I-HMA protocol is the same as the I-NOMA protocol. However, if the
condition in Proposition 2 does not hold, whether the proposed I-HMA protocol
outperforms the I-NOMA protocol or not remains an open question since the
former devices may either reduce their transmit power so as to guarantee all
the devices finish their transmission simultaneously, which is the I-NOMA
protocol; or choose the proposed I-HMA protocol. To answer this question,
next, we show the superiority of the proposed I-HMA protocol when the
condition in Proposition 2 does not hold by taking the two-device system as an
example.

######  Proposition 3.

For the transmit power limited system with two devices, if
${L}_{\pi(2)}>{L}_{\pi(2)}^{{\hskip 0.56917pt\mathsf{no}}}({\bf{v}}_{1})$,
where ${L}_{\pi(2)}^{{\hskip 0.56917pt\mathsf{no}}}({\bf{v}}_{1})$ is given by
(7), then we have

$\displaystyle\mathsf{T_{sum}^{hy}}({\bm{\Psi}})<\mathsf{T_{sum}^{no}}({\bm{\Psi}}),$
(8a)
$\displaystyle\mathsf{T_{sum}^{hy^{*}}}=\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{hy}^{*}})<\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}^{*}})<\mathsf{T_{sum}^{no}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}^{*}})=\mathsf{T_{sum}^{no^{*}}}.$ (8b)

Proof: Please refer to Appendix C. $\blacksquare$

Proposition 3 shows that given the same ${\bm{\Psi}}$, the sum transmission
delay of employing the I-NOMA protocol is larger than that with the proposed
I-HMA protocol for UL transmission under the maximum power constraints if
${L}_{\pi(k)}\leq{L}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1}),\forall k>1$. Moreover, after optimizing
the IRS BF patterns properly, the performance gain brought by the proposed
I-HMA protocol will further enlarge, as indicated by (8b), which shows the
effect of introducing the IRS.

Besides, Propositions 2 and 3 reveal that under the transmit power
constraints, the optimal performance of the proposed I-HMA protocol has a
threshold-based relationship compared with the I-NOMA protocol under the same
device’s order, which can simplify the optimization if the condition in
Proposition 2 holds. Specifically, we can first solve the NOMA-based
optimization by setting $\tau_{j}=0$, and $p_{{\pi(j)},i}=0$, $\forall
i\in\\{2,\cdots,j\\}$, $\forall j\in\\{2,\cdots,K\\}$, in (P1). As such, only
$\tau_{1}$, ${\bf{v}}_{1}$, and $p_{{\pi(k)},1}$, $\forall k\in\mathcal{K}$
need to be optimized for this special case. After obtaining
$\mathscr{S}^{\hskip 0.56917pt\mathsf{no}^{*}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}^{*}})$, we can examine whether the condition in
Proposition 2 is satisfied or not. If so, we can directly obtain the optimal
solution of $\mathscr{S}^{\hskip 0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{hy}^{*}})$ with the aforementioned $\mathscr{S}^{\hskip
0.56917pt\mathsf{no}^{*}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{no}^{*}})$
instead of solving the complex multi-variable problem (P1). Thus, the
computational complexity can be significantly reduced.

###  III-B Transmit Energy Limited Case

######  Proposition 4.

For the transmit energy limited case, we have

  1. 1.

if ${E}_{\pi(k)}\geq{E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1})$, $\forall k>1$, then
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}})=\mathsf{T_{sum}^{no}}({\bm{\Psi}})=\tau_{1}^{\hskip
0.56917pt\mathsf{no}^{*}}=\mathscr{G}_{1}({\bf{v}}_{1})$;

  2. 2.

if ${E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1})>{E}_{\pi(k)}>{E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{td}}}({\bm{\Psi}})$, $\forall k>1$, then
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}})<\min\\{\mathsf{T_{sum}^{td}}({\bm{\Psi}}),\mathsf{T_{sum}^{no}}({\bm{\Psi}})\\}$;

  3. 3.

if ${E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{td}}}({\bm{\Psi}})\geq{E}_{\pi(k)}\geq 0$, $\forall k>1$,
then
$\mathsf{T_{sum}^{hy}}=\mathsf{T_{sum}^{td}}({\bm{\Psi}})=\sum_{k=1}^{K}\tau_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}=\sum_{k=1}^{K}\mathscr{G}_{k}({\bf{v}}_{k})$.

Specifically, the threshold ${E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1})$ is computed as

$\displaystyle{E}_{\pi(k)}^{{\hskip 0.56917pt\mathsf{no}}}({\bf{v}}_{1})$
$\displaystyle\triangleq\frac{\mathscr{G}_{1}({\bf{v}}_{1})}{{\gamma}_{k}({\bf{v}}_{1})}\left(2^{{\bar{L}_{\pi(k)}}/{\mathscr{G}_{1}({\bf{v}}_{1})}}-1\right)2^{\sum_{j=1}^{k-1}{\bar{L}_{\pi(j)}}/{\mathscr{G}_{1}({\bf{v}}_{1})}}.$
(9)

Whereas, the threshold ${E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{td}}}({\bm{\Psi}})$ is calculated as

$\displaystyle E_{\pi(k)}^{\hskip 0.56917pt\mathsf{td}}({\bm{\Psi}})$
$\displaystyle\triangleq\frac{\bar{L}_{\pi(k)}\left[{2^{{\bar{L}_{\pi(i)}}/{\mathscr{G}_{i}({\bf{v}}_{i})}}}\big{/}{\gamma_{k}({\bf{v}}_{i})}-{1}\big{/}{\gamma_{k}({\bf{v}}_{k})}\right]}{\log_{2}\left[{\gamma_{k}({\bf{v}}_{k})}/{\gamma_{k}({\bf{v}}_{i})}\right]+{\bar{L}_{\pi(i)}}/{\mathscr{G}_{i}({\bf{v}}_{i})}},$
(10)

with $i$ and $\mathscr{G}_{k}({\bf{v}}_{k})$, $\forall k\in\mathcal{K}$,
respectively given by

$\displaystyle i$
$\displaystyle=\underset{j\in\mathcal{I}(k-1)}{\arg\min}{\left[1+p_{{\pi(j)},j}^{\hskip
0.56917pt\mathsf{td}^{*}}({\bf{v}}_{j})\gamma_{j}({\bf{v}}_{j})\right]}\big{/}{\gamma_{k}({\bf{v}}_{j})},$
(11)
$\displaystyle\mathscr{G}_{k}({\bf{v}}_{k})=-\frac{E_{\pi(k)}{\gamma}_{k}({\bf{v}}_{k})\bar{L}_{\pi(k)}\ln
2}{E_{\pi(1)}{\gamma}_{k}({\bf{v}}_{k})\mathscr{W}\left(\xi_{k}({\bf{v}}_{k})e^{\xi_{k}({\bf{v}}_{k})}\right)+\bar{L}_{\pi(k)}\ln
2},$ (12)

where $\mathscr{W}(\cdot)$ denotes the Lambert W function [41], and

$\displaystyle\xi_{k}({\bf{v}})$ $\displaystyle=-{\bar{L}_{\pi(k)}\ln
2}\big{/}\left[{E_{\pi(k)}{\gamma}_{k}({\bf{v}})}\right].$ (13)

Proof: Please refer to Appendix D. $\blacksquare$

Proposition 4 indicates that the proposed I-HMA protocol outperforms the
I-TDMA and the I-NOMA protocol when device’s initial energy is in a region.
Whereas the proposed I-HMA protocol will reduce to the other two protocols
when device’s initial energy is sufficiently large or not sufficient, which
can simplify the optimization. Specifically, we can first obtain the optimal
solution of the problem for the two special cases, i.e., obtain
$\mathscr{S}^{\hskip 0.56917pt\mathsf{td}^{*}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}*})$ by solving the I-TDMA based optimization; and obtain
the optimal ${\bf{v}}_{1}^{\hskip 0.56917pt\mathsf{no}^{*}}$ by solving the
I-NOMA based optimization. Afterwards, we can calculate $E_{\pi(k)}^{\hskip
0.56917pt\mathsf{no}}({\bf{v}}_{1}^{\hskip 0.56917pt\mathsf{no}^{*}})$ and
$E_{\pi(k)}^{\hskip 0.56917pt\mathsf{td}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}*})$ with the obtained ${\bf{v}}_{1}^{\hskip
0.56917pt\mathsf{no}^{*}}$ and $\mathscr{S}^{\hskip
0.56917pt\mathsf{td}^{*}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}*})$. If the
condition of case 1 or case 3 in Proposition 4 holds, then we can directly
obtain the optimal solution of $\mathscr{S}^{\hskip
0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{hy}^{*}})$ with
the aforementioned $\mathscr{S}^{\hskip
0.56917pt\mathsf{no}^{*}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{no}^{*}})$ or
$\mathscr{S}^{\hskip 0.56917pt\mathsf{td}^{*}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}^{*}})$ instead of solving the original problem (P2),
which can reduce the number of variables to be optimized.

######  Remark 1.

It is worth noting that the case in [10] and [11] can be viewed as a special
case of our considered system by setting $K=2$, and leaving out the influence
of the IRS. Moreover, the results in [10] and [11] cannot be extended to our
considered system, due to the following two reasons. First, simultaneously
serving multiple users imposes additional DoFs and also introduces new
challenges for deriving the thresholds as presented in Proposition 4,
especially for the derivation of the threshold ${E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{td}}}$, where the expressions obtained by utilizing the KKT
conditions as given in Appendix D are much more complex than that of the two-
user case. Second, with the assistance of the IRS, especially under the
dynamic IRS BF configuration, the channels for each device vary among
different time slots, which further influences the aforementioned thresholds
and the existing conclusions cannot be applied directly.

##  IV Proposed Algorithms for (P1) and (P2)

As discussed in Section II-C, (P1) and (P2)666Note that (P1) is always
feasible since the transmission time can be prolonged to guarantee the QoS
constraints (3b). Whereas, (P2) is feasible if $E_{\pi(k)}^{\min\star}\leq
E_{\pi(k)}$, $\forall k\in\mathcal{K}$, where $E_{\pi(k)}^{\min\star}$ is the
minimum required energy of $D_{\pi(k)}$, which can be obtained by solving the
energy minimization problem without transmission delay constraint. are complex
non-convex optimization problems with closely coupled variables, which
generally cannot be solved optimally. Nevertheless, after deeply exploiting
the special structure of the optimal solution for (P1) and (P2), respectively
in Section III, we can simplify the optimization by examining the conditions
as indicated by Propositions 2 and 4, and then resorting to only the I-TDMA
based optimization or I-NOMA based optimization problems, which are much
simpler to solve. Therefore, in the following, we first propose a generic
algorithm for (P1) and (P2), respectively. Then, we present the algorithm for
the special cases of the I-TDMA based and I-NOMA based optimization problems,
respectively.

###  IV-A Proposed Algorithm for (P1)

To cope with the multi-variable coupled challenging problem, we first propose
a principle to rearrange the device’s order. Then, we solve the problem with
the optimized order by decomposing the original problem (P1) into two
subproblems, namely the resource allocation optimization problem and the IRS
BF optimization problem, which are solved respectively in an alternative
manner until the objective value converges.

1) Device’s Ordering Principle: To begin with, we first deal with the device’s
ordering problem. It is worth noting that, different from the special case
with the TDMA protocol where the device’s rearranged order will not affect the
sum transmission delay of the system, this order will influence the sum
transmission delay with the proposed I-HMA UL transmission protocol due to the
integration of the NOMA protocol. For the system with $K$ devices, there are
$K!$ rearranged orders, which is prohibitive for exhaustive search when $K$ is
large. Since there are no explicit expressions to evaluate the effect of
device’s rearranged order on the minimum sum transmission delay, it is hard to
determine the optimal device’s order even in the conventional communication
system without IRS. Nevertheless, in the following, we provide an effective
principle to determine the device’s order.

To draw useful insights into the device’s ordering of the multiuser case, we
first investigate a special case of the system with two devices. In this case,
there are only two possible rearranged orders. We use the superscript $\land$
to represent $D_{1}$ is ranked before $D_{2}$, whereas utilizing the
superscript $\lor$ to represent $D_{2}$ is ranked before $D_{1}$, i.e.,
$\hat{\pi}(1)=\check{\pi}(2)=1$, $\hat{\pi}(2)=\check{\pi}(1)=2$. Thus,
$\hat{\gamma}_{1}(\cdot)=\check{\gamma}_{2}(\cdot)\triangleq\gamma_{1}(\cdot)$,
$\hat{\gamma}_{2}(\cdot)=\check{\gamma}_{1}(\cdot)\triangleq\gamma_{2}(\cdot)$.
For simplicity, we assume that ${\bf{v}}_{k}$, $\forall k\in\mathcal{K}$ is
given by aligning $D_{\pi(k)}$’s IRS-reflected signal with non-IRS-reflected
signal, i.e., $\big{[}{\bf{v}}_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}\big{]}_{n}=e^{j\angle{\left[\bm{b}_{\pi(k)}\right]_{n}}},\forall
n\in\mathcal{N}$. Therefore, we have
$\hat{{\bf{v}}}_{1}=\check{{\bf{v}}}_{2}\triangleq{\bf{v}}_{1}$ and
$\hat{{\bf{v}}}_{2}=\check{{\bf{v}}}_{1}\triangleq{\bf{v}}_{2}$. As shown in
Appendix C, the optimal power allocation strategy yields
$\hat{p}_{1,1}=\check{p}_{1,1}=\check{p}_{1,2}=P_{1}^{\hskip
0.56917pt\mathsf{m}}$ and
$\hat{p}_{2,1}=\hat{p}_{2,2}=\check{p}_{2,1}=P_{2}^{\hskip
0.56917pt\mathsf{m}}$. Therefore, the minimum sum transmission delay of these
two decoding orders can be compared as

$\displaystyle\mathsf{\hat{T}_{sum}^{hy^{*}}}-\mathsf{\check{T}_{sum}^{hy^{*}}}=\frac{\bar{L}_{2}\log_{2}\left[1+\frac{P_{1}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{1}({\bf{v}}_{2})}{1+P_{2}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{2}({\bf{v}}_{2})}\right]-\bar{L}_{1}\log_{2}\left[1+\frac{P_{2}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{2}({\bf{v}}_{1})}{1+P_{1}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{1}({\bf{v}}_{1})}\right]}{\log_{2}[1+P_{1}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{1}({\bf{v}}_{1})]\log_{2}[1+P_{2}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{2}({\bf{v}}_{2})]}.$ (14)

It can be seen that $D_{1}$ should be arranged before $D_{2}$ when
$\bar{L}_{1}/\log_{2}\left[1+\frac{P_{1}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{1}({\bf{v}}_{2})}{1+P_{2}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{2}({\bf{v}}_{2})}\right]>\bar{L}_{2}/$
$\log_{2}\left[1+\frac{P_{2}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{2}({\bf{v}}_{1})}{1+P_{1}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{1}({\bf{v}}_{1})}\right]$, whereas $D_{2}$
should be arranged first otherwise.

Inspired by the analysis on the optimal rearranged order of the two-device
case, we propose an efficient device ordering principle as follows.
Specifically, we first calculate the optimal ${\bm{p}}^{\hskip
0.56917pt\mathsf{td}^{*}}$, ${\bm{\tau}}^{\hskip 0.56917pt\mathsf{td}^{*}}$
and ${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}^{*}}$. Then, we can compute the
TDMA-based signal-to-noise ratio (SNR) denoted as $\varrho^{\hskip
0.56917pt\mathsf{td}}_{\pi(k)},\forall k\in\mathcal{K}$, by

$\displaystyle\varrho^{\hskip
0.56917pt\mathsf{td}}_{\pi(k)}=p_{\pi(k)}^{\hskip
0.56917pt\mathsf{td}^{*}}{\gamma}_{k}\left({\bf{v}}^{\hskip
0.56917pt\mathsf{td}^{*}}_{k}\right),\hskip 5.69046pt\forall k\in\mathcal{K}.$
(15)

Afterwards, we can rearrange the devices according to the ascending order of
the TDMA-based SNR ${\bm{\varrho}}^{\hskip
0.56917pt\mathsf{td}}\triangleq\\{\varrho^{\hskip
0.56917pt\mathsf{td}}_{1},\cdots,\varrho^{\hskip
0.56917pt\mathsf{td}}_{K}\\}$, i.e., update ${\bm{\pi}}$ to guarantee
$\varrho_{\pi(1)}^{\hskip
0.56917pt\mathsf{td}}\leq\cdots\leq\varrho_{\pi(K)}^{\hskip
0.56917pt\mathsf{td}}$.

The above device ordering principle is effective for the general case with
multiple devices in the sense that it increases both of the value and weight
for the average sum rate of each time slot. To illustrate this, we introduce
the concept of sum rate during each time slot denoted by
$R_{\text{sum}}^{(i)}$, $\forall i\in\mathcal{K}$, and the concept of average
sum rate during the entire UL transmission period denoted by
$\overline{R}_{\text{sum}}$, which are respectively expressed as

$\displaystyle R_{\text{sum}}^{(i)}=$ $\displaystyle\hskip
2.84544pt\sum_{k=i}^{K}r_{{\pi(k)},i}=B\log_{2}\bigg{(}1+\sum_{k=i}^{K}\varrho_{\pi(k),i}\bigg{)}=B\log_{2}\bigg{(}1+\sum_{k=1}^{K}\varrho_{\pi(k),i}-\sum_{k=1}^{i-1}\varrho_{\pi(k),i}\bigg{)},$
(16) $\displaystyle\overline{R}_{\text{sum}}=$ $\displaystyle\hskip
2.84544pt{\sum\nolimits_{i=1}^{K}\tau_{i}R_{\text{sum}}^{(i)}}\bigg{/}\hskip
0.56917pt{\sum\nolimits_{i=1}^{K}\tau_{i}}=\sum\nolimits_{i=1}^{K}\omega_{i}R_{\text{sum}}^{(i)},$
(17)

where $\varrho_{\pi(k),i}\triangleq p_{\pi(k),i}\gamma_{k}({\bf{v}}_{i})$ can
be viewed as the SNR of $D_{\pi(k)}$ during $\tau_{i}$,
$\omega_{i}={\tau_{i}}/{\sum_{i=1}^{K}\tau_{i}}$ can be viewed as the weight
of $R_{\text{sum}}^{(i)}$. And the average total sum rate can be interpreted
as the weighted sum rate of each time slot. Then, the whole UL transmission
process can be viewed as the composition of multiple NOMA-based transmissions
with the sum transmission throughput requirement of $\sum_{k=1}^{K}{L}_{k}$,
i.e., $\sum_{i=1}^{K}\tau_{i}R_{\text{sum}}^{(i)}=\sum_{k=1}^{K}{L}_{k}$. From
this perspective, the sum transmission delay can be obtained by

$\displaystyle\sum\nolimits_{i=1}^{K}\tau_{i}$
$\displaystyle={\sum\nolimits_{i=1}^{K}\tau_{i}R_{\text{sum}}^{(i)}}\bigg{/}\hskip
0.56917pt{\overline{R}_{\text{sum}}}={\sum\nolimits_{k=1}^{K}{L}_{k}}\bigg{/}\hskip
0.56917pt{\sum\nolimits_{i=1}^{K}\omega_{i}R_{\text{sum}}^{(i)}}.$ (18)

It can be seen in (18) that, given the required sum transmission throughput of
$\sum_{k=1}^{K}{L}_{k}$, to minimize the sum transmission delay, we need to
enlarge the denominator, i.e., the average sum rate
$\sum_{i=1}^{K}\omega_{i}R_{\text{sum}}^{(i)}$. For this consideration, on the
one hand, we should enlarge $R_{\text{sum}}^{(i)}$, which means that we need
to minimize $\sum_{k=1}^{i-1}\varrho_{\pi(k),i}$. In other words, we need to
rank the devices with smaller SNR $\varrho_{\pi(k),i}$ in the former place. On
the other hand, we should enlarge the weight of the sum rate per slot with a
larger value. As indicated by (16), we have $R_{\text{sum}}^{(1)}\geq
R_{\text{sum}}^{(2)}\geq\cdots\geq R_{\text{sum}}^{(K)}$, since more devices
will participate in the NOMA-based transmissions in the former time slots.
Therefore, we need to increase the weight of those $\tau_{i}$ with smaller $i$
in the first place. Note that $\tau_{i}$ is mostly limited by $D_{\pi(i)}$
since
$\tau_{i}\geq\frac{\bar{L}_{\pi(i)}-\sum_{j=1}^{i-1}\tau_{j}r_{\pi(k),j}}{\log_{2}\left[1+{P_{\pi(i)}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{i}({\bf{v}}_{i})}\right]}$. For example,
$\tau_{1}$ is limited by $D_{\pi(1)}$ since
$\tau_{1}>\bar{L}_{\pi(1)}/\log_{2}\left[1+{P_{\pi(1)}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{1}({\bf{v}}_{1})}\right]$. Thus, to enlarge the
weight of the $\tau_{1}$, we need to rank those devices with smaller SNR in
the former place, which results in ascending order of SNR.

2) Resource Allocation Optimization: After determining the device’s order, we
focus on the subproblem of resource allocation in this part. First, we have
the following proposition.

######  Proposition 5.

In the optimal solution to (P1), it follows that
$p^{*}_{{\pi(K)},i}=P_{\pi(K)}^{\hskip 0.56917pt\mathsf{m}}$, $\forall
i\in\mathcal{I}(K)$.

Proof: If $\exists\hskip 2.84544pti\in\mathcal{I}(K)$ such that
$p^{*}_{{\pi(K)},i}<P_{\pi(K)}^{\hskip 0.56917pt\mathsf{m}}$, then we can
increase the transmit power $p_{{\pi(K)},i}$ to shorten its transmission time
without affecting the transmission rates of other devices, since the transmit
power of $D_{\pi(K)}$, i.e., $p_{{\pi(K)},i}$, $\forall i\in\mathcal{I}(K)$
only influences its own transmission rate $r_{{\pi(K)},i}$ as indicated by
(2). $\blacksquare$

Proposition 5 indicates that MPT is the optimal solution for the last device
$D_{\pi(K)}$ during the entire transmission time slots to minimize its own
transmission time consumption under the transmit power constrains. By
utilizing Proposition 5, we can directly set
$p_{{\pi(K)},i}=P_{\pi(K)}^{\hskip 0.56917pt\mathsf{m}}$, $\forall
i\in\mathcal{I}(K)$, which can simplify the variables to be optimized.

For the optimization w.r.t the other variables in this subproblem, the main
difficulty lies in constraint (3b). To proceed, we first introduce a new set
of variables ${\bm{z}}\triangleq\\{z_{k,i}=\tau_{i}\hskip
2.84544ptp_{{\pi(k)},i}\hskip 0.56917pt|\hskip 2.84544pt\forall
i\in\mathcal{I}(k),\forall k\in\mathcal{K}\\}$ and rewrite constraint (3b) as

$\displaystyle\sum\nolimits_{i=1}^{k}\tau_{i}\log_{2}\bigg{(}1+\sum\nolimits_{j=i}^{k}$
$\displaystyle\frac{z_{j,i}\gamma_{j}({\bf{v}}_{i})}{\tau_{i}}\bigg{)}+\tau_{k}\log_{2}\bigg{(}1+\frac{z_{k,k}\gamma_{k}({\bf{v}}_{k})}{\tau_{k}}\bigg{)}$
$\displaystyle\geq\sum\nolimits_{i=1}^{k-1}\tau_{i}\log_{2}\bigg{(}1+\sum\nolimits_{j=i}^{k-1}\frac{z_{j,i}\gamma_{j}({\bf{v}}_{i})}{\tau_{i}}\bigg{)}+\bar{L}_{k},\hskip
5.69046pt\forall k\in\mathcal{K}.$ (19)

Note that (19) is still not convex due to that the term
$\tau_{i}\log_{2}\left(1+\sum_{j=i}^{k-1}\frac{z_{j,i}\gamma_{j}({\bf{v}}_{i})}{\tau_{i}}\right)$
in the right-hand-side of (19) is concave. However, by utilizing its first-
order Taylor expansion at the local points $\hat{\bm{z}}$ and
$\hat{\bm{\tau}}$, we can obtain its upper bound as

$\displaystyle\tau_{i}\log_{2}\bigg{(}1+\sum\nolimits_{j=i}^{k-1}\frac{z_{j,i}\gamma_{j}({\bf{v}}_{i})}{\tau_{i}}\bigg{)}\leq$
$\displaystyle\tau_{i}\log_{2}\bigg{(}1+\sum\nolimits_{j=i}^{k-1}\frac{\hat{z}_{j,i}\gamma_{j}({\bf{v}}_{i})}{\hat{\tau}_{i}}\bigg{)}+$
$\displaystyle\frac{\sum_{j=i}^{k-1}\bigg{(}\hat{\tau}_{i}{z}_{j,i}\gamma_{j}({\bf{v}}_{i})-{\tau}_{i}\hat{z}_{j,i}\gamma_{j}({\bf{v}}_{i})\bigg{)}}{\hat{\tau}_{i}+\sum_{j=i}^{k-1}\hat{z}_{j,i}\gamma_{j}({\bf{v}}_{i})}\triangleq\mathscr{F}_{i}(\tau_{i},{\bm{z}}).$
(20)

Then, the non-convex constraint (3b) can be replaced with

$\displaystyle\sum_{i=1}^{k}\tau_{i}\log_{2}\bigg{(}1+\sum_{j=i}^{k}$
$\displaystyle\frac{z_{j,i}\gamma_{j}({\bf{v}}_{i})}{\tau_{i}}\bigg{)}+\tau_{k}\log_{2}\bigg{(}1+\frac{z_{k,k}\gamma_{k}({\bf{v}}_{k})}{\tau_{k}}\bigg{)}\geq\mathscr{F}_{i}(\tau_{i},{\bm{z}})+\bar{L}_{k},\hskip
5.69046pt\forall k\in\mathcal{K}.$ (21)

As such, the resource allocation subproblem of (P1) is approximated as the
following convex problem

$\displaystyle(\text{P1.1}):\hskip
5.69046pt\underset{{\bm{\tau}},{\bm{z}}}{\min}\hskip 5.69046pt$
$\displaystyle\sum\nolimits_{i=1}^{K}\tau_{i}$ (22a) s.t.
$\displaystyle(\ref{eq:con_t_noneg_P1}),(\ref{eq:con_SCA}),z_{K,i}=\tau_{i}P_{\pi(K)}^{\hskip
0.56917pt\mathsf{m}},\forall i\in\mathcal{K},$ (22b) $\displaystyle 0\leq
z_{k,i}\leq\tau_{i}P_{\pi(k)}^{\hskip 0.56917pt\mathsf{m}},\forall
i\in\mathcal{I}(k),\forall k<K,$ (22c)

which can be successively solved by existing convex optimization solvers such
as CVX until convergence is achieved [42].

3) IRS Beamforming Optimization: To solve the IRS BF optimization subproblem,
we have to deal with the sum of the logarithm function and fractions in the
constraint (3b). To this end, we utilize the FP method to reformulate this
constraint [43]. Specifically, by introducing two auxiliary sets of variables
${\bm{\chi}}\triangleq\\{\chi_{k,i}\hskip 1.42271pt|\hskip 2.84544pt\forall
i\in\mathcal{I}(k),\forall k\in\mathcal{K}\\}$ and
${\bm{\iota}}\triangleq\\{\iota_{k,i}\hskip 1.42271pt|\hskip 2.84544pt\forall
i\in\mathcal{I}(k),\forall k\in\mathcal{K}\\}$, the constraint (3b) is
equivalent to

$\displaystyle\sum\nolimits_{i=1}^{k}u_{k,i}({\bf{v}}_{i},\chi_{k,i},\iota_{k,i})\geq{\bar{L}_{\pi(k)}},$
(23)

where

$\displaystyle u_{k,i}({\bf{v}}_{i},\chi_{k,i},\iota_{k,i})\triangleq\hskip
2.84544pt$
$\displaystyle\tau_{i}\log_{2}\big{(}1+\chi_{k,i}\big{)}-\tau_{i}\chi_{k,i}+2\Re\big{\\{}\iota_{k,i}^{H}\sqrt{\tau_{i}(1+\chi_{k,i})p_{{\pi(k)},i}}\bm{b}_{\pi(k)}^{H}{\bf{v}}_{i}\big{\\}}$
$\displaystyle-|\iota_{k,i}|^{2}\big{(}\sigma^{2}+\sum\nolimits_{j=i}^{k}p_{{\pi(j)},i}|\bm{b}_{\pi(j)}^{H}{\bf{v}}_{i}|^{2}\big{)}.$
(24)

Besides, $\iota_{k,i}$ and $\chi_{k,i}$, $\forall i\in\mathcal{I}(k),\forall
k\in\mathcal{K}$, are respectively updated by

$\displaystyle\iota_{k,i}$
$\displaystyle=\frac{\sqrt{\tau_{i}(1+\chi_{k,i})p_{{\pi(k)},i}}\bm{b}_{\pi(k)}^{H}{\bf{v}}_{i}}{\sigma^{2}+\sum_{j=i}^{k}p_{{\pi(j)},i}|\bm{b}_{\pi(j)}^{H}{\bf{v}}_{i}|^{2}},\hskip
28.45274pt\chi_{k,i}=\begin{cases}\frac{p_{{\pi(k)},i}|\bm{b}_{{\pi(k)}}^{H}{\bf{v}}_{i}|^{2}}{\sum_{j=i}^{k-1}p_{{\pi(j)},i}|\bm{b}_{\pi(j)}^{H}{\bf{v}}_{i}|^{2}+\sigma^{2}},&1\leq
i<k,\\\
{p_{{\pi(k)},i}|\bm{b}_{\pi(k)}^{H}{\bf{v}}_{i}|^{2}}/{\sigma^{2}},&i=k.\end{cases}$
(25)

Since ${\bm{\Psi}}$ is not explicitly expressed in the objective, we convert
this subproblem into the following feasibility check problem, whose optimality
is shown in [15].

$\displaystyle\underset{{\bm{\delta}},{{\bm{\Psi}}}}{\max}\hskip
5.69046pt\sum\nolimits_{k=1}^{K}\delta_{k}\hskip 28.45274pt\text{ s.t. }\hskip
5.69046pt(\ref{eq:con_v_P1}),\sum\nolimits_{i=1}^{k}u_{k,i}({\bf{v}}_{i},\chi_{k,i},\iota_{k,i})\geq{\bar{L}_{\pi(k)}}+\delta_{k},\forall
k\in\mathcal{K},$ (26)

where the slack variables
${\bm{\delta}}\triangleq\\{\delta_{1},\cdots,\delta_{K}\\}$ can be interpreted
as the “channel gain residual” in the optimization, which is beneficial in
terms of the convergence manner [15].

###  IV-B Proposed Algorithm for (P2)

1) Device’s Ordering Principle: Under the transmit energy constraints, for a
special case of a two-device system without IRS, the descending order based on
the SNR in the TDMA scheme will undermine the performance of the proposed
I-HMA protocol for the special case with the same UL transmission throughput
requirement and energy constraint for each device, since it always leads to
$E_{\pi(k)}\leq E_{\pi(k)}^{\hskip 0.56917pt\mathsf{td}}$, $\forall k>1$ [11].
However, with the assistance of the IRS, the equivalent channels vary with
different IRS BF patterns, which may change the optimal device’s rearranged
order and thus it is difficult to evaluate the specific performance under
different rearranged orders. Nevertheless, given
${\bm{\Psi}}={\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}}$, by examining the KKT
conditions as given in Appendix D, if we rearrange the devices according to
the ascending order of TDMA-based SNR, we always have
$E_{\pi(k)}>E_{\pi(k)}^{\hskip 0.56917pt\mathsf{td}}({\bm{\Psi}})$, $\forall
k>1$, which can guarantee the superiority of the proposed I-HMA protocol over
the I-TDMA protocol. Therefore, in this case, we still adopt the ascending
order of TDMA-based SNR as the ordering principle. The superiority of the
proposed device’s ordering is also validated by the simulation results as will
be presented in Section V.

2) Resource Allocation Optimization: Similar to the manipulations for (P1),
the solution of the resource allocation subproblem for (P2) can be obtained by
solving the following convex problems

$\displaystyle(\text{P2.1}):\hskip 5.69046pt$
$\displaystyle\underset{{\bm{\tau}},{\bm{z}}}{\min}\hskip
5.69046pt\sum\nolimits_{i=1}^{K}\tau_{i}\hskip 28.45274pt\text{ s.t. }\hskip
5.69046pt(\ref{eq:con_t_noneg_P1}),(\ref{eq:con_SCA}),0\leq z_{k,i}\leq
E_{\pi(k)},\forall i\in\mathcal{I}(k),\forall k\in\mathcal{K}.$ (27)

3) IRS Beamforming Optimization: For the subproblem of IRS BF optimization
regarding to (P2), the aforementioned transformation for (P1) is also
applicable, which can be tackled by solving the feasibility check problem as
given by (26).

###  IV-C Solution for I-TDMA Based Optimization

1) Transmit Power Limited Case:  It is easy to verify that the optimal
${\bm{p}}^{\hskip 0.56917pt\mathsf{td}^{*}}$, ${\bm{\tau}}^{\hskip
0.56917pt\mathsf{td}^{*}}$ and ${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}^{*}}$
can be obtained as

$\displaystyle p_{{\pi(k)}}^{\hskip
0.56917pt\mathsf{td}^{*}}=P_{\pi(k)}^{\hskip 0.56917pt\mathsf{m}},\forall
k\in\mathcal{K},$ (28a) $\displaystyle\tau_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}=\bar{L}_{\pi(k)}/\log_{2}\big{[}1+p_{{\pi(k)}}^{\hskip
0.56917pt\mathsf{td}^{*}}\gamma_{k}({\bf{v}}_{k}^{\hskip
0.56917pt\mathsf{td}^{*}})\big{]},\forall k\in\mathcal{K},$ (28b)
$\displaystyle\big{[}{\bf{v}}_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}\big{]}_{n}=e^{j\angle{\left[\bm{b}_{\pi(k)}\right]_{n}}},\forall
n\in\mathcal{N},\forall k\in\mathcal{K}.$ (28c)

2) Transmit Energy Limited Case: Based on the discussion in Appendix D, the
optimal ${\bm{\tau}}^{\hskip 0.56917pt\mathsf{td}^{*}}$ and ${\bm{p}}^{\hskip
0.56917pt\mathsf{td}^{*}}$ are calculated by

$\displaystyle\tau_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}=\mathscr{G}_{k}({\bf{v}}_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}),\hskip 11.38092pt\forall k\in\mathcal{K},$ (29a)
$\displaystyle p_{{\pi(k)}}^{\hskip
0.56917pt\mathsf{td}^{*}}=E_{\pi(k)}/\tau_{k}^{\hskip
0.56917pt\mathsf{td}^{*}},\hskip 5.69046pt\forall k\in\mathcal{K},$ (29b)

where $\mathscr{G}_{k}({\bf{v}}_{k})$ is given by (12) and the optimal IRS BF
patterns set ${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}^{*}}$ is given by
(28c).

###  IV-D Solution for I-NOMA Based Optimization

1) Transmit Power Limited Case: The optimal ${\bm{p}}^{\hskip
0.56917pt\mathsf{no}^{*}}$, ${\bm{\tau}}^{\hskip 0.56917pt\mathsf{no}^{*}}$
and ${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{no}^{*}}$ in this scenario can be
obtained by solving the following problem

$\displaystyle(\text{P1-N}):\hskip
5.69046pt\underset{{\tau_{1}},\\{p_{k,1}\\},{\bf{v}}_{1}}{\min}\hskip
5.69046pt$ $\displaystyle\tau_{1}$ (30a) s.t.
$\displaystyle\tau_{1}r_{{\pi(k)},1}\geq L_{\pi(k)},\forall k\in\mathcal{K},$
(30b) $\displaystyle 0\leq p_{{\pi(k)},1}\leq P_{\pi(k)}^{\hskip
0.56917pt\mathsf{m}},\forall k\in\mathcal{K},$ (30c)
$\displaystyle\tau_{1}\geq
0,\left|\left[{\bf{v}}_{1}\right]_{n}\right|=1,\forall n\in\mathcal{N},$ (30d)

which can be solved via the manipulations similar to (P1).

Algorithm 1 Proposed Algorithm for (P1) and (P2).

1: Initialize the device’s ordering as $\pi(k)=k,\forall k\in\mathcal{K}$.

2: Obtain ${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}^{*}}$ by (28c), obtain
${\bm{\tau}}^{\hskip 0.56917pt\mathsf{td}^{*}}$ and ${\bm{p}}^{\hskip
0.56917pt\mathsf{td}^{*}}$ by (28) for (P1), or by (29) for (P2).

3: Calculate the TDMA-based SNR ${\bm{\varrho}}^{\hskip 0.56917pt\mathsf{td}}$
with (15).

4: Update the order ${\bm{\pi}}$ such that $\varrho_{\pi(1)}^{\hskip
0.56917pt\mathsf{td}}\leq\cdots\leq\varrho_{\pi(K)}^{\hskip
0.56917pt\mathsf{td}}$.

5: Obtain the NOMA-based solution $\mathscr{S}^{\hskip
0.56917pt\mathsf{no}^{*}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{no}^{*}})$ by
solving (P1-N) or (P2-N).

6: Compute ${L}_{\pi(k)}^{{\hskip 0.56917pt\mathsf{no}}}({\bf{v}}_{1}^{\hskip
0.56917pt\mathsf{no}^{*}}),\forall k>1$, for (P1); or compute
${E}_{\pi(k)}^{{\hskip 0.56917pt\mathsf{no}}}({\bf{v}}_{1}^{\hskip
0.56917pt\mathsf{no}^{*}})$ and ${E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{td}}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}^{*}})$,
$\forall k>1$, for (P2).

7: if ${L}_{\pi(k)}\leq{L}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1}^{\hskip 0.56917pt\mathsf{no}^{*}}),\forall
k>1$ for (P1); or ${E}_{\pi(k)}\geq{E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1}^{\hskip 0.56917pt\mathsf{no}^{*}}),\forall
k>1$, for (P2), then

8: Set ${\bm{\tau}}^{\hskip 0.56917pt\mathsf{hy}^{*}}={\bm{\tau}}^{\hskip
0.56917pt\mathsf{no}^{*}}$, ${\bm{p}}^{\hskip
0.56917pt\mathsf{hy}^{*}}={\bm{p}}^{\hskip 0.56917pt\mathsf{no}^{*}}$, and
${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{hy}^{*}}={\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}^{*}}$.

9: else if ${E}_{\pi(k)}\leq{E}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{td}}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{td}^{*}}),\forall
k>1$, for (P2), then

10: Set ${\bm{\tau}}^{\hskip 0.56917pt\mathsf{hy}^{*}}={\bm{\tau}}^{\hskip
0.56917pt\mathsf{td}^{*}}$, ${\bm{p}}^{\hskip
0.56917pt\mathsf{hy}^{*}}={\bm{p}}^{\hskip 0.56917pt\mathsf{td}^{*}}$, and
${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{hy}^{*}}={\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}^{*}}$.

11: else

12: Initialize the iteration index $n$ to be 0.

13: Initialize $\tau^{(n)}_{\pi(k)}=\tau_{\pi(k)}^{\hskip
0.56917pt\mathsf{td}^{*}}$, $p^{(n)}_{{\pi(k)},k}=p_{\pi(k)}^{\hskip
0.56917pt\mathsf{td}^{*}}$, $p^{(n)}_{{\pi(k)},i}=0$, $\forall
i\in\mathcal{I}(k-1)$, and $\forall k\in\mathcal{K}$.

14: repeat

15: repeat

16: Update ${\bm{\iota}}$ and ${\bm{\chi}}$ with the given
${\bm{\tau}}^{(n)}$, ${\bm{p}}^{(n)}$ and ${\bm{\Psi}}^{(n)}$ by (25).

17: Update ${\bm{\Psi}}^{(n)}$ by solving problem (26) with the given
${\bm{\tau}}^{(n)}$, ${\bm{p}}^{(n)}$, ${\bm{\iota}}$ and ${\bm{\chi}}$.

18: until problem (26) converges.

19: Set ${\bm{\Psi}}^{(n+1)}={\bm{\Psi}}^{(n)}$

20: Calculate ${\bm{z}}^{(n)}$ according to ${\bm{p}}^{(n)}$ and
${\bm{\tau}}^{(n)}$.

21: Obtain ${\bm{\tau}}^{(n+1)}$ and ${\bm{p}}^{(n+1)}$ by solving problem
(P1.1) for (P1), or (P2.1) for (P2), at the local point ${\bm{z}}^{(n)}$ and
${\bm{\tau}}^{(n)}$ with the given ${\bm{\Psi}}^{(n+1)}$.

22: Set $n=n+1$.

23: until the fractional decrease of the sum transmission delay is below a
predefined threshold.

24: Set ${\bm{\tau}}^{\hskip 0.56917pt\mathsf{hy}^{*}}={\bm{\tau}}^{(n)}$,
${\bm{p}}^{\hskip 0.56917pt\mathsf{hy}^{*}}={\bm{p}}^{(n)}$, and
${\bm{\Psi}}^{\hskip 0.56917pt\mathsf{hy}^{*}}={\bm{\Psi}}^{(n)}$.

25: end if

26: Output: ${\bm{\pi}}$, ${\bm{\tau}}^{\hskip 0.56917pt\mathsf{hy}^{*}}$,
${\bm{p}}^{\hskip 0.56917pt\mathsf{hy}^{*}}$ and ${\bm{\Psi}}^{\hskip
0.56917pt\mathsf{hy}^{*}}$.

2) Transmit Energy Limited Case: Likewise, by applying similar manipulations
for (P2), the optimal ${\bm{p}}^{\hskip 0.56917pt\mathsf{no}^{*}}$,
${\bm{\tau}}^{\hskip 0.56917pt\mathsf{no}^{*}}$ and ${\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}^{*}}$ can be obtained by solving the following problem

$\displaystyle(\text{P2-N}):\hskip 5.69046pt$
$\displaystyle\underset{{\tau_{1}},\\{p_{k,1}\\},{\bf{v}}_{1}}{\min}\tau_{1}\hskip
28.45274pt\text{ s.t. }(\ref{eq:con_Lk_P3}),(\ref{eq:con_v_P3}),0\leq
p_{{\pi(k)},1}\tau_{1}\leq E_{\pi(k)},\forall k\in\mathcal{K}.$ (31)

###  IV-E Computational Complexity Analysis

To sum up, the solution of (P1) and (P2) can be obtained as summarized in
Algorithm 1. The computational complexity of (P1) and (P2) is given by
$\mathcal{O}\big{(}I_{\text{AO}}\big{[}(K+{K^{2}}/{4})^{3.5}+I_{\text{FP}}(KN)^{3.5}\big{]}\big{)}$,
whereas the computational complexity of (P1-N) and (P2-N) is given by
$\mathcal{O}\left(I_{\text{AO}}\left[K^{3.5}+I_{\text{FP}}N^{3.5}\right]\right)$
based on the analytical results in [44]. Since the optimal solution of TDMA-
based optimization is given by the (28c), (28) and (29), its computational
complexity computational complexity is caused by the calculation of
$\bm{b}_{{\pi(k)}}^{H}{\bf{v}}$ in $\gamma_{k}({\bf{v}})$, which is given by
$\mathcal{O}(KN)$. As such, the computational complexity can be reduced
greatly by resorting to the special cases of TDMA-based optimization problem
or NOMA-based optimization problem with the proposed algorithm if the
condition as indicated by Propositions 2 and 4 holds.

##  V Simulation Results

In this section, simulation results are presented to numerically validate our
analytical propositions and the effectiveness of the proposed I-HMA protocol
in the IRS-aided UL transmission system. As shown in Fig. LABEL:fig:simu, the
BS and IRS are located at $(0,0,0)$ meter (m) and $(30,0,5)$ m, respectively,
and the devices are distributed along the $x$-axis, if not specified
otherwise. For the involved channels777Note that no particular assumption on
the channel models and device’s location has been made in our system model and
the problem formulation shown in Section II. Therefore, all the analytical
results regarding performance comparison of the proposed I-HMA protocol with
the I-TDMA and I-NOMA schemes in IRS-aided energy-constrained UL communication
systems and algorithmic design are applicable for any channel model and
device’s location., we adopt the path loss model in [15], where the path loss
exponent is set to be 2.2 for $\bm{g}$ and $\bm{h}_{r,k}$, whereas 3.6 for
$h_{d,k}$, $\forall k\in\mathcal{K}$. Rayleigh fading is adopted to
characterize the small-scale fading for all the channels [18]. Unless
otherwise stated, the parameters are set as follows: $B=500$ kHz,
$\sigma^{2}=-80$ dBm and $N=50$ [18]. Other simulation parameters given in the
following are set according to [10, 11, 12, 13].

The annotations for the curves in the simulation results are given as follows.
1) HMA: the approach in Sec. IV-A or Sec. IV-B; 2) TDMA: the approach in Sec.
IV-C; 3) NOMA: the approach in Sec. IV-D; 4) opt-o: find the optimal device’s
order by exhausting all possible orders; 5) pro-o: employing the proposed
principle in Sec. IV; 6) des-o: rearrange devices according to the descending
order of TDMA-based SNR; 7) d-IRS: utilizing dynamic IRS BF and optimizing the
IRS BF patterns with the proposed method in Sec. IV-A3; 8) s-IRS: utilizing
static IRS BF and optimizing the IRS BF vector with the proposed method in
Sec. IV-A3 by replacing ${\bf{v}}_{k}$ with ${\bf{v}}_{1}$; 9) w/o IRS:
without the assistance of IRS.

###  V-A Comparison Among Different MA Protocols

(a) Asymmetric distributed devices (${L}_{2}^{{\hskip
0.56917pt\mathsf{no}}}=68.39$ Kbits).

(b) Symmetric distributed devices (${L}_{2}^{{\hskip
0.56917pt\mathsf{no}}}=3.15$ Kbits).

Figure 5: Sum transmission delay under the transmit power constraints ($K=2$,
$P_{1}^{\hskip 0.56917pt\mathsf{m}}=P_{2}^{\hskip 0.56917pt\mathsf{m}}=5$ dBm,
$L_{1}=200$ Kbits).

(a) Asymmetric distributed devices ($E_{2}^{\hskip 0.56917pt\mathsf{td}}=0.01$
J, $E_{2}^{\hskip 0.56917pt\mathsf{no}}=0.084$ J).

(b) Symmetric distributed devices ($E_{2}^{\hskip 0.56917pt\mathsf{td}}=0.147$
J, $E_{2}^{\hskip 0.56917pt\mathsf{no}}=2.156$ J).

Figure 6: Sum transmission delay under the transmit energy constraints ($K=2$,
$E_{1}=0.1$ J, $L_{1}=2000$ Kbits, $L_{2}=200$ Kbits).

In Figs. 5 and 6, we investigate the performance of different MA protocols
under the transmit power constraints and the transmit energy constraints,
respectively. Two kinds of deployment, namely the asymmetric distribution and
symmetric distribution are considered as shown in Fig. LABEL:fig:loca with
$K=2$. Specifically, for asymmetric deployment as shown in Fig.
LABEL:fig:asy_dep, two devices have different distances to the BS, which are
located at $(20,0,0)$ m and $(40,0,0)$ m, respectively. In contrast, for
symmetric deployment as shown in Fig. LABEL:fig:sy_dep, two devices have equal
distance to the BS, which are located at $(30,2,0)$ m and $(30,-2,0)$ m,
respectively.

It can be seen in Fig. 5 that, for a transmit power limited system, the
proposed I-HMA protocol always outperforms the I-TDMA protocol for both
deployments, as proved by Proposition 1. Note that the performance gap between
the proposed I-HMA protocol with the I-TDMA protocol is more significant when
the devices are distributed asymmetrically compared with its symmetrical
counterpart. This is because NOMA can better reduce transmission delay under
asymmetric device’s channels, which enables the proposed I-HMA protocol to
reap more benefits from the NOMA protocol. For the comparison between the
proposed I-HMA protocol with the I-NOMA protocol, we calculate
${L}_{2}^{{\hskip 0.56917pt\mathsf{no}}}$ by utilizing (7). It is observed
that when ${L}_{2}\leq{L}_{2}^{{\hskip 0.56917pt\mathsf{no}}}$, the
performance of the proposed I-HMA protocol is the same as that of the I-NOMA
protocol, whereas the proposed I-HMA protocol outperforms the I-NOMA protocol
when ${L}_{2}>{L}_{2}^{{\hskip 0.56917pt\mathsf{no}}}$, which validates the
accuracy of Propositions 2 and 3. Moreover, we also compare the performance of
the proposed I-HMA protocol under the proposed ordering principle (“HMA,
pro-o”) and the optimal order by exhausting all possible orders (“HMA,
opt-o”). In particular, the performance of the “HMA, pro-o” protocol is in
accordance with that of the “HMA, opt-o” protocol, which indicates the
effectiveness of the proposed ordering principle.

(a) The sum transmission delay versus the path loss exponent of the cascaded
links ($K=3$, $P_{1}^{\hskip 0.56917pt\mathsf{m}}=P_{2}^{\hskip
0.56917pt\mathsf{m}}=P_{3}^{\hskip 0.56917pt\mathsf{m}}=5$ dBm,
$L_{1}=L_{2}=L_{3}=10$ Kbits).

(b) The sum transmission delay versus the number of reflecting elements
($K=2$, $P_{1}^{\hskip 0.56917pt\mathsf{m}}=P_{2}^{\hskip
0.56917pt\mathsf{m}}=5$ dBm, $L_{1}=20$ Kbits, $L_{2}=40$ Kbits).

Figure 7: The effect of IRS on the sum transmission delay under the transmit
power constraints.

On the other hand, for a transmit energy limited system as shown in Fig. 6,
the performance of the proposed I-HMA protocol outperforms the other two
benchmarks (I-TDMA and I-NOMA) when ${E}_{2}^{{\hskip
0.56917pt\mathsf{no}}}>{E}_{2}>{E}_{2}^{{\hskip 0.56917pt\mathsf{td}}}$, as
indicated by Proposition 4. By utilizing (9) and (10), we calculate the value
of $E_{2}^{\hskip 0.56917pt\mathsf{no}}$ and $E_{2}^{\hskip
0.56917pt\mathsf{td}}$, which are exactly consistent with the simulation
results. One can observe that when ${E}_{2}\leq{E}_{2}^{{\hskip
0.56917pt\mathsf{td}}}$, the proposed I-HMA protocol degrades to the I-TDMA
protocol, whereas the proposed I-HMA protocol reduces to the I-NOMA protocol
when ${E}_{2}\geq{E}_{2}^{{\hskip 0.56917pt\mathsf{no}}}$, which verifies the
correctness of Proposition 4. Besides, it is noted that when the devices are
distributed asymmetrically, the value of ${E}_{2}^{{\hskip
0.56917pt\mathsf{no}}}$ is smaller than its symmetrical counterpart, which
indicates that the NOMA protocol plays a more significant role under the
asymmetric deployment because the the proposed I-HMA scheme is equivalent to
the I-NOMA scheme for a wider range in the former scenario.

###  V-B The Effect of IRS

In Fig. 7, we evaluate the advantages of introducing the IRS into the system.
Specifically, in Fig. 7(a), we plot the sum transmission delay versus the path
loss exponent (denoted by $\alpha$) of the IRS-involved links, i.e., $\bm{g}$
and $\bm{h}_{r,k}$, $\forall k\in\mathcal{K}$ in a power limited system, with
the parameters set as $K=3$, $D_{1}=(40,0,0)$ m, $D_{2}=(30,0,0)$ m,
$D_{3}=(20,0,0)$ m, $P_{1}^{\hskip 0.56917pt\mathsf{m}}=P_{2}^{\hskip
0.56917pt\mathsf{m}}=P_{3}^{\hskip 0.56917pt\mathsf{m}}=5$ dBm, and
$L_{1}=L_{2}=L_{3}=10$ Kbits. Note that the path loss exponent of the IRS-
involved links can characterize the weight of the role the IRS plays in the
system. In particular, the smaller the path loss exponent of the IRS-involved
links is, the more prominent the effect of those links will be. It is found
that a significant performance gain is achieved after introducing the IRS into
the system as compared to the case without IRS for all MA schemes. And this
performance gap is more significant as $\alpha$ decreases, which indicates
that the IRS does play an important role in improving the system performance.
Besides, we also examine the benefit of dynamic IRS BF. Specifically, a
significant performance gain can be achieved by utilizing the dynamic IRS BF
compared with the performance of static IRS BF. And when the proposed I-HMA
protocol can only use static IRS BF, the performance gain compared with the
I-NOMA protocol will be very small. This is expected since the static IRS BF
setting results in a less flexible channel reconfiguration. By comparing the
performance of “HMA, d-IRS” with “TDMA, d-IRS” and “HMA, s-IRS”, it can be
verified that the proposed dynamic I-HMA protocol not only can reap the
benefit of the time-saving advantage of the NOMA protocol compared with the
TDMA protocol, but can also get the dynamic BF gain of the TDMA protocol
compared with the NOMA protocol, which indicates the effectiveness of the
proposed design. In addition, it is also observed that the proposed ordering
principle performs well compared with the optimal order, which provides a
useful guideline to rearrange the devices in practice.

To show the effect of the number of reflecting elements at the IRS on the
system performance, we plot the sum transmission delay versus $N$ in Fig.
7(b), with the parameters set as $K=2$, $D_{1}=(40,0,0)$ m, $D_{2}=(20,0,0)$
m, $P_{1}^{\hskip 0.56917pt\mathsf{m}}=P_{2}^{\hskip 0.56917pt\mathsf{m}}=5$
dBm, $L_{1}=20$ Kbits, and $L_{2}=40$ Kbits. It can be seen that the sum
transmission delay declines significantly with the assistance of the IRS under
both MA protocols. More importantly, the proposed design significantly reduces
the sum transmission delay even with a very small number of reflecting
elements at IRS, which indicates the great potential of utilizing IRS.
Besides, we can also observe an additional performance gain by shifting the
IRS BF patterns over time compared with the static IRS BF scheme, with the
performance gap increasing as $N$ increases, which demonstrates the
effectiveness of the dynamic IRS BF design.

(a) The sum transmission delay under the transmit power constraints
($P_{k}^{\hskip 0.56917pt\mathsf{m}}=10$ dBm, $L_{k}=10(K-k+1)$ Kbits).

(b) The sum transmission delay under the transmit energy constraints
($E_{k}=k$ J, $L_{k}=200(K-k+1)$ Kbits).

Figure 8: The effect of different device’s rearranged orders ordering
($K=10$).

###  V-C The Effect of Device’s Ordering

In Fig. 8, we evaluate the effect of different device’s rearranged order under
the transmit power constraints and transmit energy constraints, respectively.
In particular, the parameters are set as $K=10$, $D_{k}=(5(K-k+1),0,0)$ m,
$\forall k\in\mathcal{K}$. Note that under this setting, there are
$10!=3628800$ possible rearranged orders, which is prohibitive for utilizing
the exhaustive search. Therefore, we adopt two random rearranged orders
(“rand-o 1” and “rand-o 2”) and the descending order of TDMA-based SNR
(“des-o”) as the benchmarks compared with our proposed ordering principle
(“pro-o”). It can be seen from Fig. 8 that device’s order has a nonnegligible
impact on the sum transmission delay when employing the proposed I-HMA
transmission protocol. Specifically, no matter under the transmit power
constraints or under the transmit energy constraints, rearranging the devices
according to the proposed ordering principle achieves a lower sum transmission
delay than its counterparts, which validates the superiority of the proposed
ordering principle.

Besides, it is observed from Fig. 8(a) that under the transmit power
constraints, employing the proposed I-HMA transmission protocol outperforms
that with I-TDMA protocol under any kind of device’s orders, which validates
the accuracy of Proposition 1. Whereas, for the transmit energy limited case
as shown in Fig. 8(b), this performance gain vanishes with the descending
device’s order, which validates the discussions in Section IV-B1\. Moreover,
it is noticed that employing the proposed I-HMA protocol reduces transmission
completion time duration not only from the system-centric view, but also from
the device-centric view, which thus can reduce the energy consumption for each
device, revealing another advantage with the proposed I-HMA protocol.

##  VI Conclusion

In this paper, we investigated an IRS-aided UL transmission system, where an
I-HMA protocol was designed to shorten the transmission delay. Two typical
communication scenarios, namely the transmit power limited case and the
transmit energy limited case were considered, where the device’s rearranged
order, time and power allocation, as well as dynamic IRS BF patterns were
jointly optimized to minimize the sum transmission delay. After formulating
the corresponding problems mathematically, we compared the performance of the
proposed hybrid protocol with the other two conventional MA strategies through
a rigorous analysis and then provided an efficient ordering principle as well
as a well-designed algorithm by deeply exploiting the properties of the
formulated problems. Through simulation results, the accuracy of the proposed
theoretical analysis and the superiority of the proposed protocol were
validated, which can shed some light in practice. Besides, it was found that
the proposed protocol can significantly reduce the sum transmission delay by
combining the additional gain of dynamic IRS BF with the time-saving
advantages of the NOMA protocol, even with a small size of IRS. Furthermore,
it revealed that the time reduction with the proposed design not only came
from the system-centric aspect, but also from the device-centric aspect, which
thus can reduce the energy consumption for each device. The application in the
downlink system will be an interesting extension and is left for future study.

## Appendix A: Proof of Proposition 1

Proof: To proceed, we first introduce the following lemma.

######  Lemma 1.

We can always construct an optimal solution for (P1) and/or (P2) by setting
constraints (3b) to be
$\sum_{i=1}^{k}\tau_{i}r_{{\pi(k)},i}=L_{\pi(k)},\forall k\in\mathcal{K}$.

Lemma 1 can be proved as follows. If there exists a solution
$\mathscr{S}^{*}_{K}({\bm{\Psi}})\triangleq\\{{\bm{\tau}}^{*},{\bm{p}}^{*}|\hskip
1.42271pt{\bm{\Psi}}\\}$ that achieves the minimum sum transmission delay
where the constraints (3b) are not met with equality for some devices, i.e.,
$\exists\hskip 2.84544pt{\pi(k)}\in\mathcal{K}$ such that
$\sum_{i=1}^{k}\tau_{i}^{*}r_{{\pi(k)},i}({\bm{p}}^{*},{\bm{\Psi}})>{L}_{\pi(k)}$,
we can always construct another solution
$\hat{\mathscr{S}}_{K}({\bm{\Psi}})\triangleq\\{\hat{\bm{\tau}},\hat{\bm{p}}|\hskip
1.42271pt{\bm{\Psi}}\\}$ by lowering its transmit power $p_{{\pi(k)},i}$,
$\forall i\in\mathcal{I}(k)$ until this constraint meets with equality, i.e.,
by setting $\hat{p}_{{\pi(k)},i}=\alpha p^{*}_{{\pi(k)},i}$, $\forall
i\in\mathcal{I}(k)$, $\hat{p}_{{\pi(j)},i}=p^{*}_{{\pi(j)},i}$, $\forall j\neq
k,\forall i\in\mathcal{I}(j)$, $\hat{\bm{\tau}}={\bm{\tau}}^{*}$, where
$\alpha<1$ such that
$\sum_{i=1}^{k}\hat{\tau_{i}}r_{{\pi(k)},i}(\hat{\bm{p}},{\bm{\Psi}})={L}_{\pi(k)}$.
It is easy to verify that the newly constructed solution
$\hat{\mathscr{S}}_{K}({\bm{\Psi}})$ satisfies all the constraints in (P1) and
(P2) while keeping the sum transmission delay unchanged. Besides, after
reducing the transmit power of $D_{\pi(k)}$, the interference to the latter
devices i.e., $D_{\pi(n)}$, $(n>k)$, can get smaller, which can shorten
$D_{\pi(n)}$’s UL transmission time consumption with the original transmit
power or reduce the transmit power to finish its UL transmission task within
the original time duration.

Based on the optimal solution of the problems with the I-TDMA protocol and the
proposed I-HMA protocol, i.e., $\mathscr{S}^{\hskip
0.56917pt\mathsf{td}^{*}}({\bm{\Psi}})$ and $\mathscr{S}^{\hskip
0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}})$, we can construct another feasible
solution
$\tilde{\mathscr{S}}({\bm{\Psi}})\triangleq\\{\tilde{\bm{\tau}},\tilde{\bm{p}}\hskip
1.42271pt|\hskip 1.42271pt{\bm{\Psi}}\\}$ for the problem with the proposed
I-HMA protocol, where $\tilde{\bm{\tau}}={\bm{\tau}}^{\hskip
0.56917pt\mathsf{td}^{*}}$, $\tilde{p}_{\pi(k),k}={p}_{\pi(k)}^{\hskip
0.56917pt\mathsf{td}^{*}}$, $\tilde{p}_{\pi(k),i}=0$, $\forall
i\in\mathcal{I}(k-1)$, $\forall k\in\mathcal{I}(K-1)$, and
$\tilde{p}_{\pi(K),i}={p}_{\pi(K)}^{\hskip 0.56917pt\mathsf{td}^{*}}$,
$\forall i\in\mathcal{I}(K)$. Then, we have

$\displaystyle\tau_{K}^{\hskip
0.56917pt\mathsf{td}^{*}}=\frac{{L}_{\pi(K)}}{r_{{\pi(K)},K}({\bm{p}}^{\hskip
0.56917pt\mathsf{td}^{*}},{\bm{\Psi}})}$
$\displaystyle\overset{\text{(a)}}{>}\frac{{L}_{\pi(K)}-\sum_{i=1}^{k-1}\tilde{\tau}_{i}r_{{\pi(K)},i}(\tilde{\bm{p}},{\bm{\Psi}})}{r_{{\pi(K)},K}(\tilde{\bm{p}},{\bm{\Psi}})}$
(32)
$\displaystyle\overset{\text{(b)}}{\geq}\frac{{L}_{\pi(K)}-\sum_{i=1}^{K-1}\tau_{i}^{\hskip
0.56917pt\mathsf{hy}^{*}}r_{{\pi(K)},i}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}^{*}},{\bm{\Psi}})}{r_{{\pi(K)},K}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}^{*}},{\bm{\Psi}})}\overset{\text{(c)}}{=}\tau_{K}^{\hskip
0.56917pt\mathsf{hy}^{*}},$

where the strict inequality (a) holds due to the fact that
$\sum_{i=1}^{K-1}\tilde{\tau}_{i}r_{{\pi(K)},i}($$\tilde{\bm{p}},{\bm{\Psi}}$$)>0$
and $r_{{\pi(K)},K}($${\bm{p}}^{\hskip
0.56917pt\mathsf{td}^{*}},{\bm{\Psi}}$$)$
$=r_{{\pi(K)},K}(\tilde{\bm{p}},{\bm{\Psi}})$. The inequality (b) holds since
given the IRS BF patterns set ${\bm{\Psi}}$, the constructed solution
$\tilde{\mathscr{S}}({\bm{\Psi}})$ is only a feasible solution of (P1),
whereas the solution $\mathscr{S}^{\hskip
0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}})$ is the optimal solution of (P1). The
equality (c) holds due to the fact that we can always construct a solution by
tightening the constraints (3b) in (P1) that achieve the minimum sum
transmission delay, as indicated by Lemma 1. Therefore, we have
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}})<\mathsf{T_{sum}^{td}}({\bm{\Psi}})$. On
the other hand, the minimum sum transmission delay with the proposed I-HMA
protocol and with the I-TDMA protocol, i.e., $\mathsf{T_{sum}^{hy^{*}}}$ and
$\mathsf{T_{sum}^{td^{*}}}$, are respectively achieved at $\mathscr{S}^{\hskip
0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{hy}^{*}})$ and
$\mathscr{S}^{\hskip 0.56917pt\mathsf{td}^{*}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}^{*}})$, which leads to
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{hy}^{*}})<\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{td}^{*}})$. $\blacksquare$

## Appendix B: Proof of Proposition 2

Proof: When ${L}_{\pi(k)}\leq{L}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1}),\forall k>1$, with ${L}_{\pi(k)}^{{\hskip
0.56917pt\mathsf{no}}}({\bf{v}}_{1})$ given by (7), it follows that

$\displaystyle\tau_{1}^{\hskip
0.56917pt\mathsf{no}^{*}}\log_{2}[1+P_{\pi(1)}^{\hskip
0.56917pt\mathsf{m}}\gamma_{1}({\bf{v}}_{1})]=\bar{L}_{\pi(1)},$ (33a)
$\displaystyle\tau_{1}^{\hskip
0.56917pt\mathsf{no}^{*}}\log_{2}\left[1+\frac{P_{{\pi(k)}}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{k}({\bf{v}}_{1})}{1+\sum_{i=1}^{k-1}P_{{\pi(i)}}^{\hskip
0.56917pt\mathsf{m}}{\gamma}_{i}({\bf{v}}_{1})}\right]\geq\bar{L}_{\pi(k)},k>1.$
(33b)

It can be easily verified that
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}})=\mathsf{T_{sum}^{no}}({\bm{\Psi}})=\tau_{1}^{\hskip
0.56917pt\mathsf{no}^{*}}$, which thus completes the proof. $\blacksquare$

## Appendix C: Proof of Proposition 3

Proof: If ${L}_{\pi(2)}>{L}_{\pi(2)}^{\hskip
0.56917pt\mathsf{no}}({\bf{v}}_{1})$, then for the I-NOMA protocol, it follows
that

$\displaystyle p_{\pi(1),1}^{\hskip
0.56917pt\mathsf{no}^{*}}<P_{\pi(1)}^{\hskip
0.56917pt\mathsf{m}},p_{{\pi(2)},1}^{\hskip
0.56917pt\mathsf{no}^{*}}=P_{\pi(2)}^{\hskip 0.56917pt\mathsf{m}},$ (34a)
$\displaystyle\frac{\log_{2}\left[1+\frac{p_{{\pi(2)},1}^{\hskip
0.56917pt\mathsf{no}^{*}}{\gamma}_{2}({\bf{v}}_{1})}{1+p_{{\pi(1)},1}^{\hskip
0.56917pt\mathsf{no}^{*}}{\gamma}_{1}({\bf{v}}_{1})}\right]}{\log_{2}[1+p_{\pi(1),1}^{\hskip
0.56917pt\mathsf{no}^{*}}\gamma_{1}({\bf{v}}_{1})]}={{L}_{\pi(2)}}\big{/}{{L}_{\pi(1)}},$
(34b)

In contrast, for the proposed I-HMA protocol, we have $p_{{\pi(2)},1}^{\hskip
0.56917pt\mathsf{hy}^{*}}=p_{{\pi(2)},2}^{\hskip
0.56917pt\mathsf{hy}^{*}}=P_{\pi(2)}^{\hskip 0.56917pt\mathsf{m}}$, and

$\displaystyle\mathsf{T_{sum}^{hy}}\left(p_{\pi(1),1},{\bm{\Psi}}\right)$
$\displaystyle=\tau_{1}+\tau_{2}=\mathscr{T}\left(p_{\pi(1),1},{\bm{\Psi}}\right)+\frac{\bar{L}_{\pi(1)}+\bar{L}_{\pi(2)}}{\log_{2}[1+p_{\pi(2),2}\gamma_{2}({\bf{v}}_{2})]},$
(35)

where $\mathscr{T}(p_{\pi(1),1},{\bm{\Psi}})$ and its partial derivative
w.r.t. $p_{\pi(1),1}$ are respectively given by

$\displaystyle\hskip
11.38092pt\mathscr{T}(p_{\pi(1),1},{\bm{\Psi}})\triangleq\frac{\bar{L}_{\pi(1)}}{\log_{2}[1+p_{\pi(1),1}\gamma_{1}({\bf{v}}_{1})]}\bigg{\\{}1+\frac{\log_{2}[1+p_{\pi(1),1}+p_{{\pi(2)},1}{\gamma}_{2}({\bf{v}}_{1})}{\log_{2}[1+p_{\pi(2),2}\gamma_{2}({\bf{v}}_{2})]}\bigg{\\}}.$
(36) $\displaystyle\frac{\partial\hskip
0.85355pt\mathscr{T}(p_{\pi(1),1},{\bm{\Psi}})}{\partial\hskip
0.85355ptp_{\pi(1),1}}=\hskip 0.85355pt$
$\displaystyle\frac{\gamma_{1}({\bf{v}}_{1})\bar{L}_{\pi(1)}}{\log_{2}[1+p_{\pi(1),1}\gamma_{1}({\bf{v}}_{1})]}\bigg{\\{}\frac{1}{\log_{2}[1+p_{\pi(2),2}\gamma_{2}({\bf{v}}_{2})]}\frac{1}{1+p_{\pi(1),1}+p_{{\pi(2)},1}{\gamma}_{2}({\bf{v}}_{1})}$
$\displaystyle-\frac{1}{\log_{2}[1+p_{\pi(2),2}\gamma_{2}({\bf{v}}_{2})]}\frac{1}{1+p_{\pi(1),1}}\frac{\log_{2}[1+p_{\pi(1),1}+p_{{\pi(2)},1}{\gamma}_{2}({\bf{v}}_{1})}{\log_{2}[1+p_{\pi(1),1}\gamma_{1}({\bf{v}}_{1})]}$
$\displaystyle-\frac{1}{\log_{2}[1+p_{\pi(1),1}\gamma_{1}({\bf{v}}_{1})]}\frac{1}{1+p_{\pi(1),1}}\bigg{\\}}<0.$
(37)

It can be seen from (37) that
$\mathsf{T_{sum}^{hy}}\left(p_{\pi(1),1},{\bm{\Psi}}\right)$ is monotonically
decreasing as $p_{\pi(1),1}$ increases, whose minimum value is achieved at
$p_{\pi(1),1}^{\hskip 0.56917pt\mathsf{hy}^{*}}=P_{\pi(1)}^{\hskip
0.56917pt\mathsf{m}}$. On the other hand, as indicated by (34), there is
$p_{\pi(1),1}^{\hskip 0.56917pt\mathsf{no}^{*}}<P_{\pi(1)}^{\hskip
0.56917pt\mathsf{m}}=p_{\pi(1),1}^{\hskip 0.56917pt\mathsf{hy}^{*}}$. Thus, we
have $\mathsf{T_{sum}^{hy}}\left(p_{\pi(1)}^{\hskip
0.56917pt\mathsf{hy}^{*}},{\bm{\Psi}}\right)<\mathsf{T_{sum}^{hy}}\left(p_{\pi(1),1}^{\hskip
0.56917pt\mathsf{no}^{*}},{\bm{\Psi}}\right)$. Besides, by examining the
solution for the optimization problem, it is easy to verify that
$\mathsf{T_{sum}^{hy}}\left(p_{\pi(1),1}^{\hskip
0.56917pt\mathsf{no}^{*}},{\bm{\Psi}}\right)=\mathsf{T_{sum}^{no}}\left(p_{\pi(1),1}^{\hskip
0.56917pt\mathsf{no}^{*}},{\bm{\Psi}}\right)$. In addition, the minimum sum
transmission delay with the proposed I-HMA protocol and with the I-NOMA
protocol, i.e., $\mathsf{T_{sum}^{hy^{*}}}$ and $\mathsf{T_{sum}^{no^{*}}}$,
are respectively achieved at $\mathscr{S}^{\hskip
0.56917pt\mathsf{hy}^{*}}({\bm{\Psi}}^{\hskip 0.56917pt\mathsf{hy}^{*}})$ and
$\mathscr{S}^{\hskip 0.56917pt\mathsf{no}^{*}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}^{*}})$, which leads to
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{hy}^{*}})<\mathsf{T_{sum}^{hy}}({\bm{\Psi}}^{\hskip
0.56917pt\mathsf{no}^{*}})$. $\blacksquare$

## Appendix D: Proof of Proposition 4

Proof: Since given the IRS BF patterns set ${\bm{\Psi}}$, the optimal solution
of the problem with the I-NOMA protocol, i.e., $\mathscr{S}^{\hskip
0.56917pt\mathsf{no}^{*}}({\bm{\Psi}})$ is always a feasible solution for the
problem with the proposed I-HMA protocol, then we have
$\mathsf{T_{sum}^{hy}}({\bm{\Psi}})\leq\mathsf{T_{sum}^{no}}({\bm{\Psi}})$,
where the equality holds when $\mathscr{S}^{\hskip
0.56917pt\mathsf{no}^{*}}({\bm{\Psi}})$ is also the optimal solution of the
problem with the proposed I-HMA protocol. To guarantee this condition, the
initial energy $E_{\pi(k)}$ at the device $D_{\pi(k)}$, $\forall k>1$, needs
to satisfy

$\displaystyle\tau_{1}\left[1+\frac{p_{{\pi(k)},1}{\gamma}_{k}({\bf{v}}_{1})}{1+\sum_{i=1}^{k-1}p_{{\pi(k)},1}{\gamma}_{i}({\bf{v}}_{1})}\right]=\bar{L}_{\pi(k)},$
(38a) $\displaystyle E_{\pi(k)}\geq\tau_{1}p_{{\pi(k)},1}\triangleq E^{{\hskip
0.56917pt\mathsf{no}}}_{\pi(k)},$ (38b)

where $\tau_{1}$ can be obtained by solving

$\displaystyle\tau_{1}\log_{2}\left[1+{p_{{\pi(1)},1}{\gamma}_{1}({\bf{v}}_{1})}\right]=\bar{L}_{\pi(1)},$
(39a) $\displaystyle\tau_{1}p_{{\pi(k)},1}=E_{\pi(1)},$ (39b)

which leads to (9). Next, we investigate the condition when the optimal
solution of the problem with the I-TDMA protocol, i.e., $\mathscr{S}^{\hskip
0.56917pt\mathsf{td}^{*}}({\bm{\Psi}})$ is the optimal solution of the problem
with the proposed I-HMA protocol. By utilizing Lemma 1, we have

$\displaystyle\tau_{1}^{\hskip
0.56917pt\mathsf{hy}}={{L}_{\pi(1)}}/{r_{{\pi(1)},1}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}},{\bm{\Psi}})},$ (40a) $\displaystyle\tau_{k}^{\hskip
0.56917pt\mathsf{hy}}=\frac{{L}_{\pi(k)}-\sum_{i=1}^{k-1}{\tau}_{i}^{\hskip
0.56917pt\mathsf{hy}}r_{{\pi(k)},i}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}},{\bm{\Psi}})}{r_{{\pi(k)},k}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}},{\bm{\Psi}})},\hskip 5.69046pt\forall k>1.$ (40b)

When the proposed I-HMA protocol reduces to the I-TDMA protocol, the optimal
protocol for each device $D_{\pi(k)}$, $\forall k>1$, is to keep inactivated
during the former time duration of $\sum_{i=1}^{k-1}\tau_{i}^{\hskip
0.56917pt\mathsf{hy}}$ so as to preserve its stored energy to support its UL
transmission only within $\tau_{k}^{\hskip 0.56917pt\mathsf{hy}}$. Thus,
$\tau_{k}^{\hskip 0.56917pt\mathsf{hy}}$ is determined by $D_{\pi(k)}$ whereas
$\tau_{i}^{\hskip 0.56917pt\mathsf{hy}}$, $\forall i\in\mathcal{I}(k-1)$, can
be considered as a constant when designing the optimal resource allocation
strategy for $D_{\pi(k)}$. As such, the sum transmission delay minimization
problem can be solved by investigating a series of subproblems for each device
in a successive manner, i.e., minimizing $\tau_{k}^{\hskip
0.56917pt\mathsf{hy}}$, $\forall k\in\mathcal{K}$. To this end, we utilize the
Dinkelbach method and introduce a set of auxiliary variables
${\bm{\lambda}}\triangleq\\{\lambda_{1},\cdots,\lambda_{K}\\}$, which
satisfies

$\displaystyle\lambda_{k}$ $\displaystyle=\frac{1}{\tau_{k}^{\hskip
0.56917pt\mathsf{hy}}}=\frac{r_{{\pi(k)},k}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}},{\bm{\Psi}})}{{L}_{\pi(k)}-\sum_{i=1}^{k-1}{\tau}_{i}^{\hskip
0.56917pt\mathsf{hy}}r_{{\pi(k)},i}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}},{\bm{\Psi}})}.$ (41)

Then, the optimal resource allocation solution for $D_{\pi(k)}$ can be
obtained by solving

$\displaystyle\underset{{{\lambda_{k}}},{\bm{p}}^{\hskip
0.56917pt\mathsf{hy}}}{\max}\hskip 11.38092pt$ $\displaystyle
r_{{\pi(k)},k}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}},{\bm{\Psi}})-\lambda_{k}{L}_{\pi(k)}+\lambda_{k}\sum\nolimits_{i=1}^{k-1}{\tau}_{i}^{\hskip
0.56917pt\mathsf{hy}}r_{{\pi(k)},i}({\bm{p}}^{\hskip
0.56917pt\mathsf{hy}},{\bm{\Psi}})$ (42a) s.t.
$\displaystyle(\ref{eq:P2_con3}),\quad\sum\nolimits_{i=1}^{k}{p_{{\pi(k)},i}^{\hskip
0.56917pt\mathsf{hy}}}/{\lambda_{k}}\leq E_{\pi(k)},$ (42b)

which is a convex problem with the given $\\{\tau_{j}^{\hskip
0.56917pt\mathsf{hy}}\hskip 1.42271pt|\hskip 2.84544pt\forall
j\in\mathcal{I}(k-1)\\}$, $\\{p_{\pi(j),i}^{\hskip 0.56917pt\mathsf{hy}}\hskip
1.42271pt|\hskip 2.84544pt\forall i\in\mathcal{I}(j),\forall
j\in\mathcal{I}(k-1)\\}$, ${{\lambda_{k}}}$ and ${\bm{\Psi}}$. Therefore, the
optimal power allocation solution can be expressed as a function w.r.t.
$\lambda_{k}$ by using the Karush-Kuhn-Tucker (KKT) condition [10]. By
investigating the dual function of problem (42), if the optimal solution of
$D_{\pi(k)}$ satisfies $p_{\pi(k),i}^{\hskip 0.56917pt\mathsf{hy}}=0$,
$\forall i\in\mathcal{I}(k-1)$, the following inequalities must satisfy

$\displaystyle{\gamma_{k}({\bf{v}}_{k})}\big{/}\left({1+p_{\pi(k),k}^{\hskip
0.56917pt\mathsf{hy}}}\right)\geq{\gamma_{k}({\bf{v}}_{i})}\big{/}\left({1+p_{\pi(i),i}^{\hskip
0.56917pt\mathsf{td}}}\right),\hskip 5.69046pt\forall i\in\mathcal{I}(k-1),$
(43)

which further leads to (10) and (11). Besides, $\tau_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}$ and $p_{{\pi(k)}}^{\hskip
0.56917pt\mathsf{td}^{*}}$, $\forall k\in\mathcal{K}$, can be obtained by
solving

$\displaystyle\tau_{k}\log_{2}\left[1+{p_{{\pi(k)}}{\gamma}_{k}({\bf{v}}_{k})}\right]=\bar{L}_{\pi(k)},$
(44a) $\displaystyle\tau_{k}p_{{\pi(k)}}=E_{\pi(k)},$ (44b)

which leads to $\tau_{k}^{\hskip
0.56917pt\mathsf{td}^{*}}=\mathscr{G}_{k}({\bf{v}}_{k})$, with
$\mathscr{G}_{k}({\bf{v}}_{k})$ given by (12). $\blacksquare$

## References

  * [1] L. Chettri and R. Bera, “A comprehensive survey on internet of things (IoT) toward 5G wireless systems,” _IEEE Internet Things J._ , vol. 7, no. 1, pp. 16–32, Jan. 2020.
  * [2] L. Dai, B. Wang, Y. Yuan, S. Han, I. Chih-Lin, and Z. Wang, “Non-orthogonal multiple access for 5G: solutions, challenges, opportunities, and future research trends,” _IEEE Commun. Mag._ , vol. 53, no. 9, pp. 74–81, Sep. 2015\.
  * [3] Y. Liu, Z. Qin, M. Elkashlan, Z. Ding, A. Nallanathan, and L. Hanzo, “Nonorthogonal multiple access for 5G and beyond,” _Proc. IEEE_ , vol. 105, no. 12, pp. 2347–2381, Dec. 2017.
  * [4] Z. Ding _et al._ , “A survey on non-orthogonal multiple access for 5G networks: Research challenges and future trends,” _IEEE J. Sel. Areas Commun._ , vol. 35, no. 10, pp. 2181–2195, Oct. 2017.
  * [5] Z. Ding, P. Fan, and H. V. Poor, “Impact of non-orthogonal multiple access on the offloading of mobile edge computing,” _IEEE Trans. Commun._ , vol. 67, no. 1, pp. 375–390, Jan. 2018.
  * [6] Z. Chen, Z. Ding, X. Dai, and R. Zhang, “An optimization perspective of the superiority of NOMA compared to conventional OMA,” _IEEE Trans. Signal Process._ , vol. 65, no. 19, pp. 5191–5202, Oct. 2017.
  * [7] M. Zeng, A. Yadav, O. A. Dobre, G. I. Tsiropoulos, and H. V. Poor, “Capacity comparison between MIMO-NOMA and MIMO-OMA with multiple users in a cluster,” _IEEE J. Sel. Areas Commun._ , vol. 35, no. 10, pp. 2413–2424, Oct. 2017.
  * [8] Q. Wu, W. Chen, D. W. K. Ng, and R. Schober, “Spectral and energy-efficient wireless powered IoT networks: NOMA or TDMA?” _IEEE Trans. Veh. Technol._ , vol. 67, no. 7, pp. 6663–6667, Jul. 2018.
  * [9] M. Zeng, A. Yadav, O. A. Dobre, and H. V. Poor, “Energy-efficient joint user-RB association and power allocation for uplink hybrid NOMA-OMA,” _IEEE Internet Things J._ , vol. 6, no. 3, pp. 5119–5131, Jun. 2019.
  * [10] Z. Ding, D. W. K. Ng, R. Schober, and H. V. Poor, “Delay minimization for NOMA-MEC offloading,” _IEEE Signal Process. Lett._ , vol. 25, no. 12, pp. 1875–1879, Dec. 2018.
  * [11] M. Zeng, N.-P. Nguyen, O. A. Dobre, and H. V. Poor, “Delay minimization for NOMA-assisted MEC under power and energy constraints,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 6, pp. 1657–1661, Dec. 2019.
  * [12] J. Zhu, J. Wang, Y. Huang, F. Fang, K. Navaie, and Z. Ding, “Resource allocation for hybrid NOMA MEC offloading,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 7, pp. 4964–4977, Jul. 2020.
  * [13] Z. Ding, D. Xu, R. Schober, and H. V. Poor, “Hybrid NOMA offloading in multi-user MEC networks,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 7, pp. 5377–5391, Jul. 2022.
  * [14] N. Kaina, M. Dupré, G. Lerosey, and M. Fink, “Shaping complex microwave fields in reverberating media with binary tunable metasurfaces,” _Sci. Rep._ , vol. 4, no. 1, pp. 1–8, Oct. 2014.
  * [15] Q. Wu and R. Zhang, “Intelligent reflecting surface enhanced wireless network via joint active and passive beamforming,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 11, pp. 5394–5409, Nov. 2019.
  * [16] Q. Wu and R. Zhang, “Beamforming optimization for wireless network aided by intelligent reflecting surface with discrete phase shifts,” _IEEE Trans. Commun._ , vol. 68, no. 3, pp. 1838–1851, Mar. 2020.
  * [17] Q. Wu and R. Zhang, “Towards smart and reconfigurable environment: Intelligent reflecting surface aided wireless network,” _IEEE Commun. Mag._ , vol. 58, no. 1, pp. 106–112, Jan. 2019.
  * [18] Q. Wu, X. Zhou, W. Chen, J. Li, and X. Zhang, “IRS-aided WPCNs: A new optimization framework for dynamic IRS beamforming,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 7, pp. 4725–4739, Jul. 2022.
  * [19] G. Chen, Q. Wu, W. Chen, D. W. K. Ng, and L. Hanzo, “IRS-aided wireless powered MEC systems: TDMA or NOMA for computation offloading?” _IEEE Trans. Wireless Commun._ , vol. 22, no. 2, pp. 1201–1218, Feb. 2023.
  * [20] B. Zheng, Q. Wu, and R. Zhang, “Intelligent reflecting surface-assisted multiple access with user pairing: NOMA or OMA?” _IEEE Commun. Lett._ , vol. 24, no. 4, pp. 753–757, 2020.
  * [21] F. Zhou, C. You, and R. Zhang, “Delay-optimal scheduling for IRS-aided mobile edge computing,” _IEEE Wireless Commun. Lett._ , vol. 10, no. 4, pp. 740–744, Apr. 2020.
  * [22] X. Mu, Y. Liu, L. Guo, J. Lin, and R. Schober, “Joint deployment and multiple access design for intelligent reflecting surface assisted networks,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 10, pp. 6648–6664, Oct. 2021\.
  * [23] A. Bansal, K. Singh, B. Clerckx, C.-P. Li, and M.-S. Alouini, “Rate-splitting multiple access for intelligent reflecting surface aided multi-user communications,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 9, pp. 9217–9229, 2021.
  * [24] W. Mei and R. Zhang, “Multi-beam multi-hop routing for intelligent reflecting surfaces aided massive MIMO,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 3, pp. 1897–1912, 2022.
  * [25] W. Mei, B. Zheng, C. You, and R. Zhang, “Intelligent reflecting surface-aided wireless networks: From single-reflection to multireflection design and optimization,” _Proc. IEEE_ , vol. 110, no. 9, pp. 1380–1400, 2022.
  * [26] I. Al-Nahhal, O. A. Dobre, and E. Basar, “Reconfigurable intelligent surface-assisted uplink sparse code multiple access,” _IEEE Commun. Lett._ , vol. 25, no. 6, pp. 2058–2062, 2021.
  * [27] M. Hua, Q. Wu, D. W. K. Qiao, Deli Ng, J. Zhao, and L. Yang, “Intelligent reflecting surface-aided joint processing coordinated multipoint transmission,” _IEEE Trans. Commun._ , vol. 69, no. 3, pp. 1650–1665, Mar. 2021.
  * [28] P. Zeng, G. Chen, Q. Wu, and D. Qiao, “Delay-aware multiple access design for intelligent reflecting surface aided uplink transmission,” in _Proc. IEEE Globecom Workshops_ , Dec. 2022.
  * [29] X. Shao, C. You, W. Ma, X. Chen, and R. Zhang, “Target sensing with intelligent reflecting surface: Architecture and performance,” _IEEE J. Sel. Areas Commun._ , vol. 40, no. 7, pp. 2070–2084, Jul. 2022.
  * [30] Z. Ding, R. Schober, and H. V. Poor, “On the impact of phase shifting designs on IRS-NOMA,” _IEEE Wireless Commun. Lett._ , vol. 9, no. 10, pp. 1596–1600, Apr. 2020.
  * [31] X. Yue and Y. Liu, “Performance analysis of intelligent reflecting surface assisted NOMA networks,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 4, pp. 2623–2636, Apr. 2022.
  * [32] G. Chen, Q. Wu, C. He, W. Chen, J. Tang, and S. Jin, “Active IRS aided multiple access for energy-constrained IoT systems,” _IEEE Trans. Wireless Commun._ , vol. 22, no. 3, pp. 1677–1694, Mar. 2023.
  * [33] A. Taha, M. Alrabeiah, and A. Alkhateeb, “Enabling large intelligent surfaces with compressive sensing and deep learning,” _IEEE Access_ , vol. 9, pp. 44 304–44 321, Mar. 2021.
  * [34] J. Chen, Y.-C. Liang, H. V. Cheng, and W. Yu, “Channel estimation for reconfigurable intelligent surface aided multi-user MIMO systems,” _arXiv preprint arXiv:1912.03619_ , 2019.
  * [35] Z. Wang, L. Liu, and S. Cui, “Channel estimation for intelligent reflecting surface assisted multiuser communications: Framework, algorithms, and analysis,” _IEEE Tran. Wireless Commun._ , vol. 19, no. 10, pp. 6607–6620, Oct. 2020.
  * [36] C. You, B. Zheng, and R. Zhang, “Channel estimation and passive beamforming for intelligent reflecting surface: Discrete phase shift and progressive refinement,” _IEEE J. Sel. Areas Commun._ , vol. 38, no. 11, pp. 2604–2620, Nov. 2020.
  * [37] A. L. Swindlehurst, G. Zhou, R. Liu, C. Pan, and M. Li, “Channel estimation with reconfigurable intelligent surfaces–a general framework,” _Proc. IEEE_ , vol. 110, no. 9, pp. 1312–1338, Sep. 2022.
  * [38] D. Tse and P. Viswanath, _Fundamentals of wireless communication_. Cambridge, U.K.: Cambridge Univ. Press, 2005\.
  * [39] L. Li _et al._ , “Intelligent metasurfaces: control, communication and computing,” _eLight_ , vol. 2, no. 1, pp. 1–24, May 2022.
  * [40] X. Mu, Y. Liu, L. Guo, J. Lin, and N. Al-Dhahir, “Exploiting intelligent reflecting surfaces in NOMA networks: Joint beamforming optimization,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 10, pp. 6884–6898, Oct. 2020\.
  * [41] R. M. Corless _et al._ , “On the Lambert W function,” _Adv. Comput. Math._ , vol. 5, no. 1, pp. 329–359, 1996.
  * [42] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” 2014. [Online]. Available: http:cvxr.com/cvx.
  * [43] K. Shen and W. Yu, “Fractional programming for communication systems—part II: Uplink scheduling via matching,” _IEEE Trans. Signal Process._ , vol. 66, no. 10, pp. 2631–2644, May 2018.
  * [44] K.-Y. Wang _et al._ , “Outage constrained robust transmit optimization for multiuser MISO downlinks: Tractable approximations by conic optimization,” _IEEE Trans. Signal Process._ , vol. 62, no. 21, pp. 5690–5705, Nov. 2014\.