# A Markov Chain Approach for Myopic Multi-hop Relaying: Outage and Diversity
Analysis

Andreas Nicolaides, Student Member, IEEE, Constantinos Psomas, Senior Member,
IEEE, and Ioannis Krikidis, Fellow, IEEE This work has received funding from
the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (Grant agreement No. 819819) and from the
Marie Skłodowska-Curie project PAINLESS under the European Union’s Horizon
2020 research and innovation programme (Grant agreement No. 812991).A.
Nicolaides, C. Psomas and I. Krikidis are with the IRIDA Research Centre for
Communication Technologies, Department of Electrical and Computer Engineering,
University of Cyprus, Cyprus, e-mail:{anicol09, psomas<EMAIL_ADDRESS>Part of this work was presented at the IEEE Global Communications Conference,
Taipei, Taiwan, December 2020 [1].

###### Abstract

In this paper, a cooperative protocol is investigated for a multi-hop network
consisting of relays with buffers of finite size, which may operate in
different communication modes. The protocol is based on the myopic decode-and-
forward strategy, where each node of the network cooperates with a limited
number of neighboring nodes for the transmission of the signals. Each relay
stores in its buffer the messages that were successfully decoded, in order to
forward them through the appropriate channel links, based on its supported
communication modes. A complete theoretical framework is investigated that
models the evolution of the buffers and the transitions at the operations of
each relay as a state Markov chain (MC). We analyze the performance of the
proposed protocol in terms of outage probability and derive an expression for
the achieved diversity-multiplexing tradeoff, by using the state transition
matrix and the related steady state of the MC. Our results show that the
proposed protocol outperforms the conventional multi-hop relaying scheme and
the system’s outage probability as well as the achieved diversity order depend
on the degree of cooperation among neighboring nodes and the communication
model that is considered for every relay of the network.

###### Index Terms:

Cooperative networks, multi-hop relaying, myopic strategy, outage probability,
diversity-multiplexing tradeoff, Markov chain.

##  I Introduction

The initial deployment and standardization of 5G networks has recently
emerged, while research in academia and industry has already made some first
steps towards the beyond 5G (B5G)/6G-era [2]. Nowadays, there is a continuous
need for an increasing number of applications and devices to be connected,
leading to an ever-growing network of nodes that have to communicate.
Cooperative networks with multiple relays that can assist the transmission of
information from a source to a destination is an appealing technology that
enables device-to-device (D2D) communications, due to its implementation
simplicity and easy scalability [3]. Especially in B5G/6G networks, research
needs to conceive innovative ideas to satisfy the challenging demands of
ultra-reliable low-latency communications for massive connectivity networks
[4]. Cooperative relay communications is a promising low-cost solution with
high flexibility, which can help the connection of trillions of devices with
enhanced reliability and low energy consumption. As such, relay communications
can be considered for the implementation of local and private 5G networks, as
they provide an adaptive physical layer and flexible transmission protocol.
Due to their potential advantages towards future generations of wireless
communications, cooperative relay networks have attracted considerable
research interest and have been considered for several practical applications,
such as in wireless ad-hoc networks [5], millimeter-wave (mmWave)
communications [6], underwater and air-to-ground networks [7, 8], and secrecy
communications [9].

Numerous studies have investigated the performance of cooperative networks
with multiple relays over a single transmission path (multi-hop relaying).
More specifically, the end-to-end performance of a dual-hop network was
analyzed in [10], while [11] extended the classical dual-hop relaying to a
generalized model with hardware impairments. Other studies extended this
approach to multi-hop schemes. In [12], the outage probability performance of
a multi-hop system over Nakagami fading channels was studied. In addition, the
authors in [13] presented a new protocol for half-duplex multi-hop relaying
networks based on the concept of buffer-aided relaying and investigated the
corresponding achievable rates. Multi-hop relaying has been also proposed to
assist connectivity for mmWave communications [6, 14], a technology that is
considered as one of the main components of 5G networks, but is highly
susceptible to path blockage. In particular, [6] investigated a joint
scheduling and congestion control policy in multi-hop mmWave networks, in
order to maximize the throughput under fairness requirements. On the other
hand, the connectivity of mmWave networks with multi-hop relaying was analyzed
in [14] by considering a stochastic geometry approach, where the obstacles are
modeled as a Boolean model.

Cooperative diversity is another relaying technique that has received a lot of
attention in the literature, as it enables broadcast transmission and spatial
diversity of the participating nodes. In the seminal work in [15], Laneman et
al. proposed several techniques of cooperative communication, such as
selection relaying and incremental relaying, and investigated their outage
performance. Moreover, the authors in [16] studied general cooperating setups,
consisting of multiple transmission paths that include an arbitrary number of
cooperating hops, and derived asymptotic expressions for the average symbol
error probability. These setups consisted of either a single relay or multiple
relays in parallel transmission paths.

A cooperation scenario for multi-hop networks was introduced in [17], where it
has been shown that the spatial diversity gain could be achieved by combining
at each node the signals that have been concurrently sent by all the preceding
terminals along a single transmission path. Based on this idea, in [18], a
class of cooperative diversity protocols was proposed, where each relay
combines the signals received from an arbitrary number of previous nodes. The
authors proved that this class of cooperative protocols can achieve the same
diversity gain as [17]. Significant diversity gain can be also achieved,
according to [19], if we consider a multi-hop buffer-aided system, where every
relay has a buffer of sufficient size and at each time-slot a stored packet is
transmitted over the best hop, based on the received signal-to-noise ratio
($\mathrm{SNR}$). Furthermore, in [20], the maximum diversity and multiplexing
gain, as well as the achieved diversity-multiplexing tradeoff (DMT) of various
multi-hop cooperative network topologies are characterized. However, full
cooperation of the nodes in such networks exhibits a number of practical
difficulties in its implementation, especially in terms of multi-node
coordination and power management. To overcome these issues, the authors in
[21] proposed the myopic decode-and-forward (DF) strategy as an information
theory concept. In this strategy, each node of the network cooperates with a
limited number of subsequent neighboring nodes. They showed that the
achievable rate increases considerably, while the complexity of its
implementation remains low.

In several cases, the devices that need to be connected in local and private
5G networks may support different transmission policies affecting their
communication capabilities e.g., for energy conservation. Such devices could
be utilized to provide further optimized services in order to improve the
networks’ performance, based on the available resources. The authors in [22]
presented a queuing model for the performance analysis of several sleep and
wakeup strategies in a network with solar-powered wireless sensors. In [23], a
relay selection scheme was considered for a cooperative network with energy
harvesting (EH) relays that can assist the communication from source to
destination only if they have sufficient energy. It was observed that, the
overall performance of such networks depends on the EH parameters of the
relays. A similar scenario was considered in [24], where a new relay selection
method was proposed, based on the throughput gain of the EH relays with enough
stored energy, which improved the overall performance of the cooperative
network. Moreover, in [25], the on-off transmission policy for a buffer aided
EH node was studied in terms of outage probability and average throughput,
where the EH node transmits information only if the stored energy exceeds a
certain value, otherwise it remains silent.

It is, therefore, an important and challenging problem to understand how the
utilization of relaying nodes with different communication capabilities
affects the performance of a multi-hop network with limited cooperation.
Motivated by this, in this paper, we propose a general cooperative protocol
over a multi-hop network, where the relays have buffers of finite size and may
operate in different communication modes. The protocol is inspired by the
myopic DF strategy [21], and can be applied to networks with an arbitrary
number of relays with different modes of operation. For example, such scenario
could be considered for wireless networks, where some intermediate nodes are
crucial for the sustainability of the communication and so they are connected
to the power grid and are always able to transmit information. The remaining
nodes could be self-powered through EH and could transmit data only if the
harvested energy is above a required level [23, 24]. The main contributions of
the paper are summarized as follows:

  * •

A novel myopic-based cooperative protocol over a multi-hop network is
proposed. Through this paper, we extend the work presented in [21] by studying
the performance of myopic strategy in terms of outage probability and
diversity gain. To our knowledge, no previous work in the literature analyzes
myopic strategy from a communication theory perspective. A system model is
presented, where the flow of information is assisted by using finite buffers
at each relay of the network. Finally, the myopic-based protocol is extended
to the case where relays may operate in different communication modes.
Therefore, a fundamental approach of how the flow of information from source
to destination can be conveyed is presented, based on the status of the
buffers and the communication capabilities of each relay.

  * •

For the analysis of the system in terms of outage probability, we model the
evolution of the considered network as a state Markov chain (MC), by taking
into account the transitions that take place at the buffers and the
communication modes of the relays. This approach provides a flexible and
elegant modeling of the different instances that the network can be found. By
using the state transition matrix and the related steady state of the MC, we
investigate a complete theoretical framework for the performance analysis of
such cooperative networks. The presented framework is general and can be
adapted to an arbitrary number of relays, any myopic strategy and several
communication strategies supported by the participating relays.

  * •

Our results demonstrate that as the number of cooperating nodes increases, the
performance of the system is enhanced both in terms of outage probability and
diversity gain. Furthermore, it is shown that the diversity order that can be
achieved by the proposed protocol depends significantly on the communication
strategy that is supported by every relay of the network. Finally, by
extending the proposed protocol for multi-branch networks, the outage
probability of the system is improved, while the overall diversity gain
depends on the diversity gain that each branch can separately achieve.

As such, the proposed myopic protocol can provide useful insights for the
design and realization of local and private 5G networks with reduced
computational complexity and memory requirements and increased energy
efficiency.

The remainder of the paper is organized as follows. Section II introduces the
system model and Section III describes the implementation of the proposed
protocol. A state Markovian model approach used for the derivation of the
system’s outage probability is presented in Section IV. In Section V, we
provide the numerical expressions of the outage probability analysis and the
DMT for the proposed protocol. Our numerical and simulation results are
presented in Section VI and finally, some concluding remarks are stated in
Section VII.

Notation: Lower and upper case boldface letters denote vectors and matrices,
respectively; $\mathbb{P}[X]$ denotes the probability of the event $X$ and
$\mathbb{E}[X]$ represents the expected value of $X$; $\mathds{1}_{X}$ is the
indicator function, where $\mathds{1}_{X}=1$ if $X$ is true, otherwise
$\mathds{1}_{X}=0$; $\Im(x)$ returns the imaginary part of $x$ and
$\jmath=\sqrt{-1}$ denotes the imaginary unit; $\Phi(\cdot)$ is the cumulative
distribution function (cdf) of the standard normal distribution and $O(\cdot)$
denotes the big $O$ notation; $[x]^{+}=\max(0,x)$, $\lceil
x\rceil=\min\\{m\in\mathbb{Z}|m\geq x\\}$, $\binom{n}{k}=\frac{n!}{k!(n-k)!}$
and $(2n-1)!!=(2n-1)(2n-3)\ldots 3\cdot 1$.

##  II System Model

###  II-A Network topology

A wireless network topology is considered, which consists of a single source
$S$, $N$ intermediate relays $R_{1},R_{2},\ldots,R_{N}$, and a single
destination $D$111A network topology with multiple sources and destinations
can be also considered, which is left for future work.. For ease of notation,
we let node $i$ correspond to the relay $R_{i}$, $1\leq i\leq N$, and nodes
$0$ and $N+1$ correspond to the source $S$ and destination $D$, respectively.
At the relays, the DF scheme is employed for forwarding the signals. Moreover,
time is assumed to be slotted and $x(t)$ is used to denote the signal that $S$
sends to $R_{1}$ at time-slot $t$ with normalized energy, i.e.
$\mathbb{E}[|x(t)|^{2}]=1$. Each transmitter (the source $S$ or a relay
$R_{i}$) transmits with the same fixed power $P$. The destination $D$ receives
data based on a $k$-hop myopic DF strategy [21], $1\leq k\leq N+1$, where $k$
represents the maximum number of nodes that a transmitter can forward data to.
More specifically, node $i$ ($0\leq i\leq N$) can send data to
$L_{i}=\min(k,N-i+1)$ subsequent nodes. As such, at each time-slot, the $i$-th
transmitter splits its power to $L_{i}$ partitions. Therefore, a signal is
sent through the link $i\rightarrow j$ with transmit power $a_{i,j}P$, where
$a_{i,j}$ denotes the power splitting parameter, such that
$\sum_{j=i+1}^{L_{i}+i}a_{i,j}=1$. However, at a given time-slot $t$, only the
successfully decoded signals can be forwarded to the appropriate nodes. For
that reason, each relay $R_{i}$ has a data buffer (data queue) $b_{i}$ of
finite size $L_{i}$, where it can store the decoded signals for
forwarding222Note that each node sends data to the subsequent $L_{i}$ nodes
concurrently. Therefore, a storage space of the same size is required in order
to hold the data that will be forwarded., based on the proposed protocol
described in Section III. An example of this topology is presented in Fig. 1,
for $k=2$ hops and $N=3$ relays.

###  II-B Channel model

For the analysis, we consider independent and identically distributed (i.i.d.)
channel links that experience propagation path loss, which is assumed to
follow the power law $d_{i,j}^{-\eta}$, where $d_{i,j}$ is the distance
between the nodes $i$ and $j$ and $\eta$ denotes the path loss exponent.
Without loss of generality, we assume the ordering $d_{i,j}<d_{i,j+1}$,
$\forall$ $i,j$, $i<j\leq N+1$. Note that this assumption corresponds to
distance-based routing protocols in multi-hop networks that take into
consideration the Euclidean distance among the nodes e.g. the shortest-path-
routing [26]. Furthermore, all wireless links exhibit fading which is modeled
as frequency-flat Rayleigh block fading333Even though we consider Rayleigh
fading, the proposed analytical framework is general and the extension to
other fading models is straightforward as we only need to consider their
probability distributions.. This signifies that the fading coefficients
$h_{i,j}$ remain constant during one time-slot, but change independently for
different time-slots, by following a circularly symmetric complex Gaussian
distribution with zero mean and unit variance i.e.,
$h_{i,j}\sim\mathcal{CN}(0,1)$. We assume that during one time-slot, the
relays of the system can receive and transmit data simultaneously i.e., they
operate in full-duplex mode. Since we focus on the performance of the myopic
DF scheme, we consider an ideal scenario where we ignore the self-interference
and interference from other relays; interference mitigation can be achieved
through sophisticated signal processing and equalization techniques [17, 27].
In other words, the presented analysis serves as a communication theory bound.

Figure 1: Topology for $2$-hop myopic DF strategy in a wireless network with
three relays. The arrows indicate all the available links in the system and
for each link the corresponding signal that will be transmitted is shown.

###  II-C Relay communication model

The relays of the network operate based on two different communication modes,
namely the active and silent modes. If a relay is active during one time-slot,
then it is able to simultaneously transmit and receive the decoded signals. In
the silent mode, the relay can still receive data but is unable to forward its
decoded signals to the following nodes [22]. We consider a scenario where a
subset of the participating relays are always active. The remaining relays are
able to switch their operations between the two communication modes, and
therefore can be either active or silent. Such relays could correspond to
devices that are always connected to the power grid and switch off their
transmitters occasionally by design, in order to conserve energy.
Alternatively, the switching between the two communication modes could occur
probabilistically, based on the EH profile of the devices [25].

We assume that during a time-slot, a relay’s communication mode remains
constant, but can change independently between the two modes for different
time-slots. In the considered scenario, the relay’s decision for the
communication mode at each time-slot is modeled as a Bernoulli distribution
with parameter $q$, which indicates the probability that a relay operates in
silent mode. For the relays that are able to transmit and receive data at
every time-slot, or equivalently are always in the active mode, the
probability of operating in silent mode is equal to $q=0$. By using the
Bernoulli distribution, we provide a unified analysis for various decision-
based scenarios at the relays, such as EH scenarios where the decision is
related to the status of the energy buffers [28]. However, it is important to
note that the proposed analytical framework is general and any other
distribution can be applied.

##  III A $k$-hop Myopic-based Protocol

We now present our proposed protocol based on the $k$-hop myopic DF strategy
[21]. The protocol describes the procedure over which the flow of information
from $S$ to $D$ is conveyed within the considered network. Based on the
presented system model, at time-slot $t$ the received signal at the $j$-th
receiver is given by

$y_{j}(t)=\sum_{i=0}^{N}\mathds{1}_{i\rightarrow
j}\sqrt{d_{i,j}^{-\eta}\alpha_{i,j}P}h_{i,j}x(t-j+1)+w_{j}(t),$ (1)

where $w_{j}(t)\sim\mathcal{CN}(0,\sigma^{2})$ is the additive white Gaussian
noise (AWGN) with variance $\sigma^{2}$ and $\mathds{1}_{i\rightarrow j}$
equals to one if node $i$ transmits a signal to node $j$ at the current time-
slot, otherwise it is equal to zero. In this work, we focus on the fundamental
analysis of the myopic scheme, so a perfect (global) channel state information
(CSI) is assumed and each receiver is able to combine the received signals
coherently through co-phasing444In practice, a channel estimation process is
required and the associated overhead increases as $k$ increase; note that $k$
can be adapted to the available resources to achieve a balance between
estimation and system performance.. Therefore, the corresponding instantaneous
$\mathrm{SNR}$ at the $j$-th receiver during one time-slot is given by

$\mathrm{SNR}_{j}=\dfrac{P}{\sigma^{2}}\left(\sum_{i=0}^{N}\mathds{1}_{i\rightarrow
j}|h_{i,j}|\sqrt{d_{i,j}^{-\eta}a_{i,j}}\right)^{2},$ (2)

where $|h_{i,j}|$ is a random variable that follows a Rayleigh distribution
with unit scale parameter. We assume that $\nu$ relays of the network,
$0\leq\nu\leq N$, have dual-mode communication capabilities, while the
remaining $N-\nu$ relays are always active. Moreover, $S$ is able to transmit
all its available data at every time-slot. A signal at the $j$-th receiver is
successfully decoded if the instantaneous $\mathrm{SNR}_{j}$ is not less than
a predefined threshold $\gamma$ i.e., $\mathrm{SNR}_{j}\geq\gamma$, otherwise
an outage occurs. Each relay keeps in its buffer the signals that were
successfully decoded, in order to forward them through the appropriate channel
links. For this, the buffer of each relay is used as an one-dimensional array
with indexed elements, where the element $b_{i}[n]$, $1\leq n\leq L_{i}$,
corresponds to the $n$-th most recent signal that the $i$-th relay receives.

At each time-slot, the network performs three specific tasks: $(i)$
transmission of information, $(ii)$ buffer shifting, and $(iii)$ information
decoding. More specifically, at an arbitrary time-slot $t$, the network
follows the procedure described below:

  * •

Transmission of information: At first, the node $S$ sends the signals
$x(t-j+1)$ to the nodes $j=1,\dots,k$, respectively. Then, every dual-mode
relay determines whether it will operate in active or silent mode. Recall that
the relays with a single-mode operation are considered to be always active.
The $i$-th relay of the network, $i=1,\ldots,N$, forwards the signal
$x(t-j+1)$ to the corresponding node $j=i+1,\dots,\min(i+k,N+1)$, if and only
if, it is in active mode and its buffer element $b_{i}[j-i]$ is not empty
i.e., a signal is stored in this element. Thus, at the specific time-slot, the
$j$-th node of the network can receive the signal $x(t-j+1)$ simultaneously
from at most $k$ previous nodes. The example in Fig. 1 shows an instance of
the network, where at time-slot $t$ all the relays are active and every
buffer’s element has a previously decoded signal. As a result, at the
transmission phase, all the available links of the system, for the considered
2-hop myopic DF strategy, are used.

  * •

Shifting operation: After the transmission phase, each relay prepares its
buffer for the next time-slot. In particular, it shifts the elements one
position to the right. In other words, $b_{i}[2]$ will get the data of
$b_{i}[1]$, $b_{i}[3]$ the data of $b_{i}[2]$, etc. Therefore, the first
element of each buffer becomes unassigned for the decoding of $x(t-j+1)$ (see
decoding process below). The shifting operation is required for the proper
transmission of the appropriate signals to the corresponding nodes at each
time-slot.

  * •

Decoding process: Every relay combines all the received signals $x(t-j+1)$,
acquired at the transmission phase, and attempts to decode the message. The
first element of its buffer $b_{i}[1]$ is used for the outcome of the decoding
process: it stores the signal if it is successfully decoded, otherwise it
becomes an empty element. It is important to note that, an empty element
indicates that the decoding of the signal failed (i.e. similarly to a pointer
indicating a null value) and thus is not able to be forwarded. Finally, the
destination $D$ combines the received signals $x(t-N)$ and if the message is
not successfully decoded i.e., $\mathrm{SNR}_{N+1}<\gamma$, then the system is
in outage and the message is lost.

According to the above procedure, it is clear that some of the elements at the
buffers might be empty due to the shifting operation. Consequently, the proper
transmission of the successfully decoded signals to the appropriate nodes
relies on the communication mode of each relay and the content of its buffer
that evolves with time. Based on these features, in the following section, we
introduce a theoretical framework that is exploited for the system’s outage
probability analysis.

##  IV A State Markovian Model Approach

For the analysis of the considered system, we provide a theoretical framework
that models the evolution of the relays’ buffers and the communication mode of
the dual-mode relays as a MC. In this section, the state transition matrix
construction and the derivation of the stationary distribution of the MC are
presented, which will be used for the computation of the system’s outage
probability in Section V.

###  IV-A Definition of MC states

Firstly, the MC states are defined in order to represent the different
instances that characterize the status of the network. The distinction between
these instances depends on the buffers’ evolution with time and the
transitions at the dual-mode communication strategy. A state of the MC, or
equivalently a network state, needs to capture the transitions that take place
at the relays’ buffers and the dual-mode relays’ operations. Thus, it is
necessary to represent the evolution of the buffers and the relays’ status by
dividing the network states into two separate sub-states, namely the buffer
states and the relay states.

Recall from Section III that, as a result of the decoding process and the
shifting operation, each buffer’s elements can be found in two possible
conditions: either to have the $n$-th most recently received signal or to be
empty. We denote the $m$-th buffer state by

$u_{m}\triangleq(\beta_{1,m}\>\beta_{2,m}\>\ldots\>\beta_{N,m}),$ (3)

where $\beta_{i,m}$ is a one-dimensional binary array associated with the
$i$-th relay, for which each element $\beta_{i}[n]$ equals $0$ if the
corresponding buffer element $b_{i}[n]$ is empty, otherwise is equal to $1$.
Therefore, each array $\beta_{i,m}$ indicates the non-empty elements of the
corresponding buffer $b_{i}$ at the buffer state $u_{m}$, while from the
definition it is apparent that its size equals $L_{i}$. The number of the
buffer states is given by all the possible combinations that can be derived by
each $\beta_{i}$’s element. Thus, each buffer state is a vector of finite size
$L_{\beta}=\sum_{i=1}^{N}L_{i}=(2N-k+1)\frac{k}{2}$, that represents which
elements in each buffer have decoded signals, and the total number of buffer
states is equal to $M_{B}=2^{L_{\beta}}$.

However, the buffers’ evolution and equivalently the transition between
different instances of the network depends also on the communication mode of
each dual-mode relay that varies for each time-slot. In the considered
scenario, the dual-mode relays are predetermined and are given by the ordered
set $H=\\{i|R_{i}\text{ is dual-mode}\\}$. The $m$-th relay state is denoted
as

$v_{m}\triangleq(\lambda_{H(1),m}\>\lambda_{H(2),m}\>\ldots\>\lambda_{H(\nu),m}),$
(4)

where $\lambda_{H(i),m}$ indicates the communication mode of the $i$-th dual-
mode relay at the $m$-th state and is equal to $0$ if the relay operates in
silent mode, otherwise equals $1$. Note that this parameter is defined only
for the dual-mode relays of the network, since the other relays are always
active and the operations related to their communication capabilities do not
vary with time. Thus, each relay state is a $1\times\nu$ vector that captures
all the possible transitions at the dual-mode relays’ communication modes and
depicts which relays are active at each instance of the network. The total
number of relay states is then derived as $M_{R}=2^{\nu}$.

The network states are constructed by the concatenation of the buffer and
relay states that were previously defined. Therefore, the $m$-th network
state, $1\leq m\leq M$, is denoted as

$\displaystyle s_{m}$ $\displaystyle\triangleq(v_{m}\>u_{m})$
$\displaystyle=(\lambda_{H(1),m}\ldots\>\lambda_{H(\nu),m}\>\beta_{1,m}\ldots\>\beta_{N,m}),$
(5)

which represents the joint status of the relays’ buffers and the dual-mode
relays’ communication activity. The total number of network states that are
considered for the MC is given by all the possible pairs of buffer and relay
states that can be derived and is equal to $M=M_{B}M_{R}=2^{L_{\beta}+\nu}$.
Since this concatenation results in a binary representation of a decimal
number, the MC states are predefined and arranged in a numerical ascending
order, such that the states $s_{1}$ and $s_{M}$ are denoted by the
$1\times(L_{\beta}+\nu)$ binary vectors $(00\ldots 0)$ and $(11\ldots 1)$,
respectively.

###  IV-B State transition matrix and stationary distribution

The state transition matrix is a square matrix containing information on the
transition probabilities between the states of the MC. Specifically, it
defines how the system evolves with time and indicates which of the available
links will be used at each time-slot. Let $\mathbf{A}$ denote the $M\times M$
state transition matrix of the MC, where the entry
$p_{l,m}=\mathbb{P}(s_{m}\rightarrow
s_{l})=\mathbb{P}(X_{t+1}=s_{l}|X_{t}=s_{m})$ is the probability of the
transition from network state $s_{m}$ at time $t$ to state $s_{l}$ at time
$(t+1)$. The calculation of these probabilities relies on the communication
mode of each dual-mode relay and the status of each relay’s buffer, and
consequently from the corresponding parameters $\lambda_{i}$ and $\beta_{i}$.

Input:

$N\leftarrow$ Number of relays

$H\leftarrow$ Set of dual-mode relays

$k\leftarrow$ Number of hops

Output:

$\mathbf{A}\leftarrow$ Transition Matrix

1 Compute $L_{i}=\min(k,N+1-i),i=1,\ldots,N$

2 Compute $L_{\beta}=\left(2N-k+1\right)\dfrac{k}{2}$

3 Compute $M_{B}=2^{L_{\beta}}$, $M_{R}=2^{\nu}$, $M=M_{B}M_{R}$

4 for  _$m=1$ to $M$_ do

5 for  _$l=1$ to $M$_ do

6 Assume $s_{m}\rightarrow s_{l}$ exists

7 for  _$i=1$ to $N$_ do

8 Get $\beta_{i,m}$, $\beta_{i,l}$

9 for  _$n=1$ to $L_{i}-1$_ do

10 if  _$\beta_{i,m}[n]\neq\beta_{i,l}[n+1]$_ then

11 $s_{m}\rightarrow s_{l}$ does not exist

12 end if

13

14 end for

15

16 end for

17 Compute $p_{l,m}$ using (6)

18 end for

19

20 end for

Algorithm 1 Generation of the state transition matrix.

Algorithm 1 shows the proposed procedure for the construction of the state
transition matrix $\mathbf{A}$, given the number of relays $N$, the ordered
set of dual-mode relays $H$ and the number of hops $k$. First of all, we
derive the size of each array $\beta_{i}$ and the size of the buffer states.
Moreover, we compute the number of buffer and relay states and consequently
the number of states of the MC i.e., (lines $1-3$). Then, we need to detect
all the possible transitions between the states. Since the decision of the
communication mode at each dual-mode relay at time-slot $t$ is independent
from what was decided at previous time-slots, the only parameters that affect
the validity of a state transition are the arrays $\beta_{i}$, $1\leq i\leq
N$, due to their shifting operation. Thus, for each pair of states
$(s_{m},s_{l})$, we examine if the variations at the elements of each array
$\beta_{i}$ are consistent with the evolution of the buffers as in the
proposed protocol. Each array $\beta_{i,m}$ can be extracted by isolating the
buffer state $u_{m}$ from the network state $s_{m}$ and taking all the
elements of the resulting array from the index
$u_{m}[\sum_{j=1}^{i-1}L_{j}+1]$ to the index $u_{m}[\sum_{j=1}^{i}L_{j}]$. A
transition from $s_{m}$ to $s_{l}$ exists, if the contents of all the arrays
shift one position to the right. This is equivalent to the equality
$\beta_{i,m}[n]=\beta_{i,l}[n+1]$, $1\leq n\leq L_{i}-1$, for all the arrays
$\beta_{i}$, $i=1,\ldots,N$. If at least one of these equalities does not
hold, then the transition is not possible. The first element of each array at
the new buffer state $\beta_{i,l}[1]$ indicates if an outage occurred at the
corresponding relay, while the elements of the new relay state indicate which
dual-mode relays are active. As the decoding is handled separately by each
relay, these probabilities are independent and therefore the transition
probability is given as their product. The entries of the state transition
matrix are then given by

$p_{l,m}=\begin{cases}&\displaystyle\prod_{i=1}^{\nu}\displaystyle\prod_{j=1}^{N}\bigg{[}\lambda_{H(i),l}(1-q)+(1-\lambda_{H(i),l})q\bigg{]}\\\
&\times\bigg{[}\beta_{j,l}[1](1-P_{o}(j,m))+\left(1-\beta_{j,l}[1]\right)P_{o}(j,m)\bigg{]},\\\
&\hskip 128.0374pt\text{if }s_{m}\rightarrow s_{l}\text{ exists};\\\
&0,\text{otherwise},\end{cases}$ (6)

where $P_{o}(j,m)$ is the probability that the $j$-th node has an outage
event, given that the network instance is derived by the state $s_{m}$. Note
that, due to the two possible values that the elements $\lambda_{H(i),l}$ and
$\beta_{j,l}[1]$ can take, the aggregate number of all possible transitions
from every state are $2^{\nu+N}$. The analytical expressions for the outage
probability are given in Section V.

We are now able to derive the stationary distribution of the MC, which is
denoted as $\boldsymbol{\pi}$. In this case, the interpretation of the
stationary distribution gives an insight to the long-term use of the available
channel links in the system, as it indicates how the signals are being
transmitted across the relays until they reach the final destination. The
calculation of the steady states is given in the following Lemma 1.

######  Lemma 1.

The state transition matrix $\mathbf{A}$ of the defined MC has a unique
stationary distribution, which is given by

$\boldsymbol{\pi}=(\mathbf{A}-\mathbf{I}+\mathbf{B})^{-1}\mathbf{b},$ (7)

where $\boldsymbol{\pi}$ is the stationary distribution,
$\mathbf{b}=(1\>1\>\ldots\>1)^{T}$ and $\mathbf{B}_{l,m}=1$, $\forall$ $l,m$.

###### Proof.

See Appendix -A. ∎

In the next section, we provide our main results for the performance analysis
of our proposed protocol.

##  V Outage Probability & Diversity Analysis

Based on the obtained stationary distribution of the MC, we can now analyze
the performance of the proposed protocol, in terms of outage probability and
diversity gain. Firstly, we provide an expression of the outage probability at
each receiver and then the system’s outage probability is derived. To conform
with the above notation, we assume that $S$ has an array $\beta_{0}$ of finite
size $k$, in which all the elements are equal to one, since $S$ always sends a
signal to the $k$ subsequent nodes.

In general, the $i$-th transmitter sends a signal to the $j$-th receiver of
the network, if the corresponding indicator function
$\mathds{1}_{(i\rightarrow j),m}$ is equal to one and it is calculated as

$\mathds{1}_{(i\rightarrow
j),m}=\begin{cases}\beta_{i,m}[j-i]\lambda_{i,m},&i\in H;\\\
\beta_{i,m}[j-i],&\text{otherwise}.\end{cases}$ (8)

Thus, the number of nodes that transmit a signal to the $j$-th receiver at
state $s_{m}$ is equal to

$C_{j,m}=\sum_{i=[j-k]^{+}}^{j-1}\mathds{1}_{(i\rightarrow j),m},$ (9)

which can be at most $k$, based on the presented protocol. Since the signals
are transmitted coherently, the outage probability achieved at the $j$-th node
is given as follows.

######  Theorem 1.

The probability of having an outage event at the $j$-th node is

$P_{o}(j,m)=\dfrac{1}{2}-\dfrac{1}{\pi}\int_{0}^{\infty}\dfrac{1}{t}\Im\bigg{[}\exp\left(-\jmath
t\sqrt{\dfrac{\gamma\sigma^{2}}{P}}\right)\\\
\times\prod_{i=[j-k]^{+}}^{j-1}\phi_{i,j}(t)^{\mathds{1}_{(i\rightarrow
j),m}}\bigg{]}dt,$ (10)

where $\phi_{i,j}(t)$ is the characteristic function of $|h_{i,j}|$ and is
equal to

$\phi_{i,j}(t)=1+\jmath t\sqrt{\dfrac{2\pi
a_{i,j}}{d_{i,j}^{\eta}}}\exp\bigg{(}-\dfrac{a_{i,j}t^{2}}{2d_{i,j}^{\eta}}\bigg{)}\Phi\bigg{(}\jmath
t\sqrt{\dfrac{a_{i,j}}{d_{i,j}^{\eta}}}\bigg{)}.$ (11)

###### Proof.

See Appendix -B. ∎

It is clear that for the case where the $j$-th node receives a signal from
only one transmitter $i$, the outage probability can be given as the cdf of an
exponential distribution i.e.,

$P_{o}(j,m)=1-\exp\left(-\dfrac{\gamma\sigma^{2}d_{i,j}^{\eta}}{a_{i,j}P}\right).$
(12)

In the following proposition, we provide a closed form approximation of the
derived outage probability expression, based on the small argument
approximation (SAA) [29].

######  Proposition 1.

Under the SAA, the outage probability at the $j$-th receiver is approximated
by

$P_{o}(j,m)\approx
1-\exp\bigg{(}-\dfrac{\gamma\sigma^{2}}{2P\theta_{j,m}}\bigg{)}\sum_{c=0}^{C_{j,m}-1}\dfrac{1}{c!}\bigg{(}\dfrac{\gamma\sigma^{2}}{2P\theta_{j,m}}\bigg{)}^{c},$
(13)

where

$\theta_{j,m}=\frac{1}{C_{j,m}}[(2C_{j,m}-1)!!]^{1/C_{j,m}}\sum_{i=[j-k]^{+}}^{j-1}\frac{a_{i,j}}{d_{i,j}^{\eta}}\mathds{1}_{(i\rightarrow
j),m}.$ (14)

###### Proof.

From (2) it is observed that the channel gain at each receiver consists of a
weighted sum of i.i.d. Rayleigh random variables. For the distribution of the
weighted Rayleigh sum, the following inequality holds [30]

$\displaystyle P_{o}(j,m)$
$\displaystyle=\mathbb{P}\left[\sum_{i=[j-k]^{+}}^{j-1}|h_{i,j}|\sqrt{\dfrac{a_{i,j}}{d_{i,j}^{\eta}}}\mathds{1}_{(i\rightarrow
j),m}<\sqrt{\dfrac{\gamma\sigma^{2}}{P}}\right]$
$\displaystyle\geq\mathbb{P}\left[\sum_{i=[j-k]^{+}}^{j-1}|h_{i,j}|\mathds{1}_{(i\rightarrow
j),m}<\sqrt{\dfrac{C_{j,m}\gamma\sigma^{2}}{g_{j,m}P}}\right],$ (15)

where
$g_{j,m}=\sum_{i=[j-k]^{+}}^{j-1}a_{i,j}d_{i,j}^{-\eta}\mathds{1}_{(i\rightarrow
j),m}$. Note that the right-hand side of (V) follows the distribution of a
normalized Rayleigh sum. The approximated expression follows by taking the
right-hand side of the inequality and then by using the SAA to the cdf of the
normalized sum as in [29]. ∎

The outage probability of the system $P_{out}(\gamma)$ can be calculated by
using the steady state of the MC along with the probability of an outage event
at the destination. Thus, $P_{out}(\gamma)$ can be expressed as

$P_{out}(\gamma)=\sum_{m=1}^{M}\boldsymbol{\pi}_{m}P_{o}(N+1,m).$ (16)

From the derived expressions for the achieved outage probability, it can be
seen that the system’s performance depends on the number of relays ($N$), the
number of hops ($k$) and the set of relays that have dual-mode operations
($H$). In order to provide more insights on the performance of such networks,
we need to explore in greater detail how these parameters affect the overall
outage probability. In particular, in the next section the performance of our
protocol is investigated in the high $\mathrm{SNR}$ regime and the DMT is
derived.

###  V-A Diversity-multiplexing tradeoff

In this section, we use the presented outage expressions to derive a tradeoff
between the diversity and multiplexing gains for the proposed protocol. In
general, a channel achieves multiplexing gain $\rho$ and a corresponding
diversity gain $\delta^{*}(\rho)$, if the target data rate $R(P)\sim\rho\log
P$ and the outage probability $P_{out}(P)$ satisfy the conditions [31]

$\lim_{P\rightarrow\infty}\dfrac{R(P)}{\log
P}=\rho\quad\text{and}\quad\lim_{P\rightarrow\infty}-\dfrac{\log
P_{out}(P)}{\log P}=\delta^{*}(\rho).$ (17)

Below, we provide the proposition which characterizes the DMT that the
proposed protocol can achieve.

######  Theorem 2.

The DMT achieved by the proposed protocol for the considered multi-hop network
is given by

$\delta^{*}(\rho)=(1-\rho)\min_{\begin{subarray}{c}1\leq m\leq M\\\
\boldsymbol{\pi}_{m}\nrightarrow
0\end{subarray}}\mathcal{L}_{m},\>\rho\in[0,1],$ (18)

where $\mathcal{L}_{m}$ denotes the minimum number of disjoint paths from $S$
to $D$ that can be obtained for the network instance derived by the state
$s_{m}$.

###### Proof.

See Appendix -C. ∎

######  Corollary 1.

The maximum diversity order of the proposed protocol for a given network
topology is achieved when $\rho=0$ and is equal to
$\delta^{*}(0)=\displaystyle\min_{\begin{subarray}{c}1\leq m\leq M\\\
\boldsymbol{\pi}_{m}\nrightarrow 0\end{subarray}}\mathcal{L}_{m}$.

We can observe from Corollary 1 that the maximum diversity order can vary
between zero and $k$ i.e., $0\leq\delta^{*}(0)\leq k$. The exact behavior of
the network in the high $\mathrm{SNR}$ regime depends significantly on which
relays within the network are dual-mode. Below, we examine how the diversity
order of the protocol is affected in different topology scenarios.

####  V-A1 Only dual-mode relays ($\nu=N$)

In this scenario, all the relays of the network are dual-mode and so they can
transmit information only when they are active. Even though at high
$\mathrm{SNR}$ each node is able to decode all of its received signals, when
all the transmitters of a node are concurrently silent during one time-slot,
the node does not receive any signal and so the relays’ buffers may still have
empty elements. The outage performance of the network is then dominated by the
terms for which the destination does not receive information from any relay.
Therefore, the system’s performance converges to an outage floor value, unless
there is a direct link from $S$ to $D$ i.e., $k=N+1$, which results in
diversity order equal to one. For $k\leq N\leq 2k$, we state the following
proposition.

######  Proposition 2.

The outage floor value of the considered network for $k<N\leq 2k$ is given by

$e(N,k)=q^{k}e(N-2,k-1)+(1-q^{k})e(N-1,k),$ (19)

and for $N=k$ is equal to

$e(N,k)=q^{k}.$ (20)

###### Proof.

See Appendix -D. ∎

For $N>2k$ the outage floor value can be also extracted by following a similar
approach. However, the expressions of these cases are more complex and their
exact derivation is out of the scope of this paper.

####  V-A2 Only active relays ($\nu=0$)

In contrast to the previous scenario, in this case, all the relays are always
active and so they are able to transmit their decoded signals at every time-
slot. By considering $P\rightarrow\infty$, we notice that the outage
probability at each relay and for every received signal converges to zero.
This implies that the stationary distribution of the transition matrix is
given by $\boldsymbol{\pi}_{m}\rightarrow 0$, $m=1,\ldots,M-1$, and
$\boldsymbol{\pi}_{M}\rightarrow 1$, as all the buffers are full. If we follow
the same procedure as in the proof of Theorem 2 we conclude that for the
specific scenario the DMT of the investigated model is equal to

$\delta^{*}(\rho)=k(1-\rho),\>\rho\in[0,1].$ (21)

and for $\rho=0$ it can achieve a maximum diversity order equal to the number
of hops555The proof of the maximum diversity order that is achieved for the
specific scenario can be found in [1]. i.e., $\delta^{*}(0)=k$.

####  V-A3 Deployment strategy for $0<\nu<N$

In the previous two scenarios we presented the two extreme cases that a
network topology can be found, regarding the number of dual-mode relays. Any
intermediate scenario, where only part of the relays are dual-mode i.e.,
$0<\nu<N$, is expected to have a performance that lies between these limits.
As previously stated, the selection of which relays will have dual-mode
operations can significantly affect the network’s performance. The proposed
protocol can achieve diversity gain, if a signal can be received from $D$
through transmission paths which consist only of active relays, since the
outage probability in these instances will not depend on $q$ and it will
converge to zero. Specifically, a network can achieve diversity order
$\delta^{*}(0)=\epsilon$, $1\leq\epsilon\leq k-1$, if the number of dual-mode
relays satisfies the condition

$k-\epsilon\leq\nu\leq\bigg{\lceil}\dfrac{N}{k}\bigg{\rceil}(k-\epsilon),$
(22)

and each subset of $k$ consecutive relays contains a maximum number of
$k-\epsilon$ dual mode relays.

###  V-B Multi-branch multi-hop network

In general, the adaptation of the network deployment, according to the
previous cases, is not always achievable or the dual-mode operation may refer
to conditions for which our intervention is not feasible. To overcome this
issue, the aforementioned framework can be also generalized to multi-branch
networks [16]. Specifically, we consider a cooperative system of $Z$
orthogonal branches with common source and destination nodes, where each
branch consists of $N$ intermediate relays $R_{i}^{z}$, $1\leq i\leq N$,
$1\leq z\leq Z$. For each branch a $k_{z}$-myopic DF strategy is employed
independently, where $1\leq k_{z}\leq N+1$. Moreover, each branch may choose
its $\nu_{z}$ dual-mode relays differently. An example of this topology is
shown in Fig. 2.

Figure 2: Topology of a wireless network with three branches and three relays
at each branch. The branches employ the $k_{z}$-hop myopic DF strategy
independently, where $k_{1}=k_{3}=1$ and $k_{2}=2$.

We assume that the destination $D$ receives the transmitted signals by
performing the selection combining (SC) technique [32]. In this case the
combiner chooses the signal of the branch with the highest $\mathrm{SNR}$.
Since the branches in this case are orthogonal, the previous outage
probability analysis can be performed at each branch separately. Therefore,
the system’s outage probability for the multi-branch scenario is given by

$P_{out}(Z,\gamma)=\prod_{z=1}^{Z}P_{out}^{z}(\gamma)=\prod_{z=1}^{Z}\sum_{m_{z}=1}^{M_{z}}\boldsymbol{\pi}_{m_{z}}P_{o}(N+1,m_{z}),$
(23)

where $P_{o}(\cdot)$ is given by (10). Note that if the number of hops is the
same for all the participating branches, i.e. $k_{z}=k$, $1\leq z\leq Z$, and
each branch has equal number of dual-mode relays at the same position, then
the outage probability of the system can be rewritten as

$P_{out}(Z,\gamma)=\left[\sum_{m=1}^{M}\boldsymbol{\pi}_{m}P_{o}(N+1,m)\right]^{Z}.$
(24)

Regarding the high $\mathrm{SNR}$ regime, the following proposition provides
the DMT for the case of multi-branch networks.

######  Proposition 3.

The DMT of the proposed protocol for the considered multi-branch multi-hop
network is given by

$\delta^{*}(\rho)=(1-\rho)\sum_{z=1}^{Z}\min_{\begin{subarray}{c}1\leq
m_{z}\leq M_{z}\\\ \boldsymbol{\pi}_{m_{z}}\nrightarrow
0\end{subarray}}\mathcal{L}_{m_{z}},\>\rho\in[0,1].$ (25)

By considering $P\rightarrow\infty$ and since we assume that the branches are
orthogonal, the DMT is derived from (17) as

$\delta^{*}(\rho)=-\lim_{P\rightarrow\infty}\frac{\log\displaystyle\prod_{z=1}^{Z}P_{out}^{z}(\gamma)}{\log
P}=-\sum_{z=1}^{Z}\lim_{P\rightarrow\infty}\frac{\log
P_{out}^{z}(\gamma)}{\log P},$ (26)

which follows by the logarithmic identity $\log(xy)=\log(x)+\log(y)$. The
final expression in (25) is derived by calculating the DMT of each branch
separately, following the result of Theorem 2. Based on the above results, the
maximum diversity order that can be achieved by a multi-branch network is the
sum of the number of hops at each branch i.e.,

$\delta^{*}(0)=\sum_{z=1}^{Z}k_{z},$ (27)

which is achieved if each branch topology has only active relays i.e.,
$\nu_{z}=0$ $\forall$ $z=1,\ldots,Z$. Furthermore, by considering the case
with an equal number of hops at all branches, the maximum diversity order can
be calculated by $\delta^{*}(0)=Zk$. It is therefore easily observed that the
protocol can achieve a performance enhancement of order equal to the number of
branches. Even for the case where each branch’s performance reaches an outage
floor, the utilization of a multi-branch scenario can significantly decrease
the overall outage floor value for the considered network.

###  V-C Illustrative example ($N=2$ relays, $k=2$ hops)

We provide an example of the proposed framework that refers to a network
topology with $N=2$ relays and $k=2$ hops. In this case, the size of the
buffers $b_{1}$ and $b_{2}$ (and therefore of the arrays $\beta_{1}$ and
$\beta_{2}$) is $L_{1}=2$ and $L_{2}=1$, respectively. The concatenation of
the arrays $\beta_{1}$ and $\beta_{2}$ results in a binary vector of finite
size $L_{\beta}=3$, which represents a buffer state of the MC. In this
example, there are $M_{B}=2^{3}=8$ different buffer states. The set of dual-
mode relays for the considered network can be any subset of the ordered set
$H=\\{1,2\\}$. Due to space limitations, the system’s outage probability is
calculated for the case where all the relays are always active i.e.,
$H=\emptyset$. Therefore, the resulting MC states are defined only by the
buffer states of the network, and are presented in Fig. 3. By following the
procedure in Algorithm 1, the state transition matrix $\mathbf{A}$ is derived
as

$\mathbf{A}=\begin{pmatrix}p_{1,1}&p_{1,2}&p_{1,3}&p_{1,4}&0&0&0&0\\\
p_{2,1}&p_{2,2}&p_{2,3}&p_{2,4}&0&0&0&0\\\
0&0&0&0&p_{3,5}&p_{3,6}&p_{3,7}&p_{3,8}\\\
0&0&0&0&p_{4,5}&p_{4,6}&p_{4,7}&p_{4,8}\\\
p_{5,1}&p_{5,2}&p_{5,3}&p_{5,4}&0&0&0&0\\\
p_{6,1}&p_{6,2}&p_{6,3}&p_{6,4}&0&0&0&0\\\
0&0&0&0&p_{7,5}&p_{7,6}&p_{7,7}&p_{7,8}\\\
0&0&0&0&p_{8,5}&p_{8,6}&p_{8,7}&p_{8,8}\\\ \end{pmatrix},$ (28)

where the entries $p_{l,m}$ denote the probabilities of the existent
transitions and are given by

$p_{l,m}=\bigg{[}\beta_{1,l}[1](1-P_{o}(1,m))+(1-\beta_{1,l}[1])P_{o}(1,m)\bigg{]}\\\
\times\bigg{[}\beta_{2,l}[1](1-P_{o}(2,m))+\left(1-\beta_{2,l}[1]\right)P_{o}(2,m)\bigg{]}.$
(29)

Figure 3: The possible states of the MC for a network topology with $N=2$
relays, $k=2$ hops and $H=\emptyset$. For each state, the contents of the
arrays $\beta_{1}$ and $\beta_{2}$ are presented below the corresponding
relay, as well as which of the available links are used.

By using (8) and from the network instances in Fig. 3, we observe that $S$
always transmits a signal to $R_{1}$, while $R_{2}$ always receives from $S$
and at states $s_{5}$, $s_{6}$, $s_{7}$ and $s_{8}$ it also receives from
$R_{1}$. Finally, the transmitters of $D$ are $R_{1}$ and $R_{2}$ at states
$s_{4}$ and $s_{8}$, only $R_{1}$ at states $s_{3}$ and $s_{7}$ and only
$R_{2}$ at states $s_{2}$ and $s_{6}$. At states $s_{1}$ and $s_{5}$ the
destination does not receive any data, so it is on outage with probability
one. From the derived results the following relations are obtained

$\begin{split}P_{o}(1,1)&=P_{o}(1,2)=\ldots=P_{o}(1,8),\\\
P_{o}(2,1)&=P_{o}(2,2)=P_{o}(2,3)=P_{o}(2,4),\\\
P_{o}(2,5)&=P_{o}(2,6)=P_{o}(2,7)=P_{o}(2,8),\\\
P_{o}(3,m)&=P_{o}(3,m+4),\>m=1,\ldots,4.\end{split}$ (30)

The system’s outage probability is given by calculating the stationary
distribution of the MC and, based on the aforementioned relations, is equal to

$\displaystyle P_{out}(\gamma)$
$\displaystyle=\sum_{m=1}^{8}\boldsymbol{\pi}_{m}P_{o}(3,m)$
$\displaystyle=P_{o}(1,1)P_{o}(2,1)+P_{o}(1,1)\left[1-P_{o}(2,1)\right]P_{o}(3,2)$
$\displaystyle\quad+\left[1-P_{o}(1,1)\right]P_{o}(2,5)P_{o}(3,3)$
$\displaystyle\quad+\left[1-P_{o}(1,1)\right]\left[1-P_{o}(2,5)\right]P_{o}(3,4),$
(31)

where the probabilities $P_{o}(i,m)$ can be calculated by using the
aforementioned outage expressions in (10), (12) or (13).

Regarding the diversity gain of the network, we need to examine which are the
dual-mode relays within the network. Thus, if all the relays are active i.e.,
$H=\emptyset$, then the proposed protocol can achieve diversity order equal to
the number of hops, while for $H=\\{1\\}$ or $H=\\{2\\}$, from Corollary 1 the
maximum diversity order is equal to one. Finally, if all the relays are dual-
mode i.e., $H=\\{1,2\\}$, then at high $\mathrm{SNR}$ the outage probability
converges to a floor value which is calculated from (20) as $e(2,2)=q^{2}$.

TABLE I: Summary of simulation parameters

Description | Value
---|---
Number of relays |  $N=2$ or $3$
Distance between $S$ and $D$ |  $d_{0,N+1}=3$ m
Path loss exponent | $\eta=2$
Variance of AWGN | $\sigma^{2}=1$
$\mathrm{SNR}$ threshold |  $\gamma=0$ dB
Probability of silent mode |  $q=0.1$ or $0.5$

##  VI Numerical Results

In this section, we validate our theoretical analysis and main analytical
results with computer simulations to demonstrate the effect of various network
parameters on the performance of our proposed myopic protocol. For the
simulations, the following parameters are considered. The distance between $S$
and $D$ is set to a fixed value of $d_{0,N+1}=3$ m and the distance between
two consecutive nodes is the same for all nodes i.e.,
$d_{i,i+1}=d=d_{0,N+1}/(N+1)$ $\forall$ $i=0,\ldots,N$. In addition, the path
loss exponent is equal to $\eta=2$, the variance of the AWGN is normalized to
$\sigma^{2}=1$ and the energy of the channel coefficients is normalized to
$\mathbb{E}\left[\left|h_{i,j}\right|^{2}\right]=1$. Finally, the
$\mathrm{SNR}$ threshold is set to $\gamma=0$ dB. The values of the simulation
parameters are summarized in Table I. Note that, in all the presented figures,
the analytical results are illustrated with lines (solid, dashed or dotted)
and the simulation results with markers.

It can be easily observed that the system’s outage probability depends on how
the transmit power of each node is divided. Therefore, our results are
numerically optimized with respect to the power splitting parameters
$a_{i,j}$. We formulate the system’s outage probability minimization problem
as follows {ai,j}P_out(γ) ∑_j=i+1^L_i+i a_i,j=1,i=0,…,N 0 ¡ a_i,j¡ 1, i=0,…,N
q=0. Note that the second constraint ensures that a portion of the power $P$
will be allocated to all the available channel links. Moreover, the
optimization is formulated for the case where all the relays of the network
are always active i.e., $q=0$, which leads to a simpler implementation of the
protocol, since the power management at each relay will not depend on the
general knowledge of the communication modes of all the relays at each time-
slot. Due to the complexity of the derived expressions, the aforementioned
minimization problem can be solved using numerical tools, such as the
NMinimize function of Mathematica [33].

Figure 4: Outage probability versus $P$ for a network topology with $N=2$
relays, $k=1,2,3$ hops, $H=\emptyset$, $\gamma=0$ dB and $d=1$ m; the
theoretical results are depicted with lines and the simulation results with
markers.

Figs. 4 and 5 illustrate the system’s outage probability against the transmit
power $P$ in a network setting with $N=2$ and $3$ relays, respectively,
considering the case where the relays are always active. The outage
performance is investigated for all possible $k$-hop myopic scenarios i.e.,
for $k=1,\dots,N+1$. For these scenarios, the conventional multi-hop DF scheme
used in [12], where each node sends a signal only to its subsequent node
through orthogonal channels, is used as a performance benchmark. The outage
probability in this case is given by

$\displaystyle P_{out,c}$
$\displaystyle=1-\prod_{j=1}^{N+1}\mathbb{P}\left[\mathrm{SNR}_{j}\geq\gamma_{c}\right]$
$\displaystyle=1-\exp\left[-\dfrac{\left(N+1\right)\gamma_{c}d^{\eta}\sigma^{2}}{P}\right],$
(32)

where $\gamma_{c}=(\gamma+1)^{N+1}-1$. We observe that, in both figures, our
proposed protocol is superior to the conventional multi-hop scheme. In
particular, it can be seen that the $k$-hop myopic strategy outperforms the
typical multi-hop DF scheme in terms of outage performance and coding gain.
Moreover, for $k>1$ the myopic scheme also achieves a higher diversity gain.
Furthermore, in Fig. 4, the optimized outage performance of the network,
according to (VI), is also compared to the case where the power at each
transmitter is equally divided to each channel link i.e.,
$a_{i,j}=1/\min(k,N-i+1)$, $0\leq i\leq N$. It is observed that, while at high
$\mathrm{SNR}$s the performance is almost the same for both cases, in the low
$\mathrm{SNR}$ regime the outage probability is slightly improved for the
numerically optimized values of $a_{i,j}$. It is also worth noting that, when
$P$ is equally divided, the system cannot fully benefit from the increase on
the number of hops, since the outage performance for $k=3$ is worse than the
$2$-hop scenario at low transmit power values.

Figure 5: Outage probability versus $P$ for a network topology with $N=3$
relays, $k=1,2,3,4$ hops, $H=\emptyset$, $\gamma=0$ dB and $d=0.75$ m; the
theoretical results are depicted with lines and the simulation results with
markers.

Fig. 4 shows that an increase in the number of hops results in an improvement
of the outage probability performance, with the cases of $k=1$ and $k=2$
revealing the most significant difference (i.e., about $8$ dB gain for an
outage probability equal to $10^{-2}$). However, for a transmit power value up
to $15$ dB the $2$-hop scenario has similar performance with the $3$-hop case.
Therefore, for lower values of $P$ a topology with $k<N+1$ can have a
performance close to the case of full cooperation; this observation
corresponds to the results of [21]. In addition, it can be seen that as the
number of hops increases the diversity gain is also improved, which complies
with our analysis indicating a maximum diversity order equal to $k$ when the
relays of the network are always active. Similar results are derived in Fig. 5
for $N=3$ relays. It is worth noting that in this case the outage probability
for our protocol is slightly improved, compared to the results in Fig. 4, due
to the reduced path loss. On the other hand, the diversity gain remains the
same, as it depends only on the number of hops. Finally, we observe that in
both figures the theoretical values (lines) perfectly match to the simulation
results (markers), which validates the accuracy of our analysis, while for
$k>1$ the obtained SAA expression in Proposition 1 provides a tight
approximation of the actual performance of the network.

Figure 6: Outage probability versus $P$ for different sets of dual-mode
relays; $N=2$ relays, $k=2$ hops, $q=0.1$, $\gamma=0$ dB and $d=1$ m; the
theoretical results are depicted with lines and the simulation results with
markers. Figure 7: Outage probability versus $P$ for different sets of dual-
mode relays; $N=3$ relays, $k=2$ hops, $q=0.1$, $\gamma=0$ dB and $d=0.75$ m.

In Figs. 6 and 7 the achieved outage probability is presented for various sets
of dual-mode relays, under the 2-hop myopic protocol and for a network
topology with $N=2$ and $3$ relays, respectively. As expected, the case where
all the relays are active is superior to any other scenario and is the only
case that can achieve the maximum possible diversity gain $k=2$. On the other
hand, if the network consists of only dual-mode relays, the outage performance
is significantly deteriorated and as $P$ increases, the outage probability
converges to the floor value calculated in Proposition 2. The performance of
any other deployment scenario lies between the limits set by the previous two
extreme cases.

Specifically, in Fig. 6 it is observed that both intermediate cases with
$H=\\{1\\}$ and $H=\\{2\\}$ achieve the same diversity order, which is equal
to one. However, when only $R_{1}$ is able to switch between active and silent
mode, the system achieves a better outage performance than the system where
only $R_{2}$ has dual-mode operations. This is expected, since $R_{2}$ is
closer to $D$, which is also its only receiver, and so $R_{2}$ being silent
has a higher impact to the system’s outage probability. Again, in this figure
we show that our simulation results (markers) validate our analysis (lines).
In Fig. 7, it can be seen that if only $R_{1}$ is dual-mode, the achieved
diversity order is decreased to one. Moreover, in the case of $H=\\{1,3\\}$
the same diversity order can be achieved, even though more dual-mode relays
are used, since there is still a possible path from $S$ to $D$ which does not
depend on the dual-mode operations ($S\rightarrow R_{2}\rightarrow D$). On the
contrary, the performance of the topology considering $H=\\{1,2\\}$ converges
to an outage floor, due to the consecutive order of the two dual-mode relays.
Therefore, the selection of which relays will operate in dual-mode is critical
for the network’s performance, and especially the achieved diversity gain, and
this observation follows our discussion in Section V-A.

Finally, Fig. 8 depicts the outage probability versus $P$ for different number
of branches and various combinations of dual-mode relays, where each branch
deploys a network setting with $N=2$ relays and $k=2$ hops. First of all, we
can see that an increase in the number of branches results in the improvement
of the system’s outage probability. Specifically, compared to the single
branch with only active relays scenario, doubling the branches will also
double the achieved diversity gain, while if the second branch has only dual-
mode relays, the system will not achieve higher diversity gain but its outage
performance will still be enhanced. Similarly, if we consider a single branch
network with only dual-mode relays, doubling the branches will significantly
decrease the outage floor value. The aforementioned scenarios are also
presented for different values of $q$ i.e., the probability of a dual-mode
relay to be silent. As expected, as this probability increases the system’s
outage probability increases as well, since the dual-mode relays will remain
silent for a larger number of time-slots. However, the system’s performance
remains unaffected in terms of diversity gain.

Figure 8: Outage probability versus $P$ for different number of branches;
$N=2$ relays, $k=2$ hops, $\gamma=0$ dB and $d=1$ m.

##  VII Conclusions

In this paper, we presented a new protocol over a multi-hop cooperative
network, based on the myopic strategy, where the relays have buffers of finite
size and can operate in two communication modes, namely the active and silent
mode. A general methodology that captures how the contents of each relay’s
buffer and the communication operation of each relay evolve with time was
proposed by using a MC formulation. Under this framework, we derived the
outage probability of the system and a general expression for the resulting
DMT, and we investigated the maximum diversity order that can be achieved,
based on different topology scenarios. The proposed protocol was also
generalized for multi-branch networks. We demonstrated that as the number of
hops in the proposed protocol increases, the system’s performance is enhanced
in terms of outage probability, while the achieved diversity gain depends on
both the number of hops and the group of relays that have dual-mode
operations.

###  -A Proof of Lemma 1

We first need to verify that some properties of the state transition matrix
$\mathbf{A}$ hold, in order to ensure that it has a unique stationary
distribution. Specifically, $\mathbf{A}$ must be a column stochastic matrix,
which is irreducible and aperiodic. A column stochastic matrix is a square
matrix of non-negative terms in which the elements in each column sum up to
one, while a non-negative matrix is called irreducible if every pair of states
can communicate. Finally, the period of a state $s_{m}$ is the greatest common
divisor of the set $\\{t\in\mathbb{N}:p_{m,m}^{(t)}>0\\}$ and if the period is
$1$, the state is aperiodic. The transition matrix is aperiodic if all the
states are aperiodic [34].

For any MC under the proposed framework, the transitions from state $s_{m}$ to
all the possible states $s_{l}$ have probabilities that sum up to one i.e.,
$\sum_{l=1}^{M}p_{l,m}=1$. Therefore, the transition matrix is column
stochastic. Moreover, from the structure of the problem, it is observed that
there is a path from any state to any other state of the MC. Consequently, all
the states belong to a single communication class and the transition matrix is
irreducible. An irreducible MC needs only one aperiodic state to imply that
all states are aperiodic. In the defined MC the transition probability from
state $s_{1}$ to the same state is always non-zero i.e.,
$p_{1,1}=\mathbb{P}(s_{1}\rightarrow s_{1})>0$; hence the state $s_{1}$ is
aperiodic. Since there is only one communication class, all states are
aperiodic and therefore, the transition matrix is aperiodic. As the required
properties of the transition matrix hold, we conclude that it has a unique
stationary distribution which is given as in [35].

###  -B Proof of Theorem 1

In the proposed protocol, at each time-slot, the $\mathrm{SNR}$ at the $j$-th
receiver is calculated based on which nodes transmit a signal to the receiver,
given the network state $s_{m}$. According to the presented theoretical
framework, the $i$-th node transmit a signal to the $j$-th receiver, if (8) is
equal to one i.e., the node is active and its specific buffer’s element is not
empty. Thus, the $\mathrm{SNR}$ of the $j$-th node for the transition
$s_{m}\rightarrow s_{l}$ equals

$\mathrm{SNR}_{j,m}=\dfrac{P}{\sigma^{2}}\left(\sum_{i=[j-k]^{+}}^{j-1}|h_{i,j}|\sqrt{\dfrac{a_{i,j}}{d_{i,j}^{\eta}}}\mathds{1}_{(i\rightarrow
j),m}\right)^{2}.$ (33)

The probability of having an outage event at the $j$-th node can be expressed
as

$P_{o}(j,m)=\mathbb{P}\left[\sum_{i=[j-k]^{+}}^{j-1}|h_{i,j}|\sqrt{\dfrac{a_{i,j}}{d_{i,j}^{\eta}}}\mathds{1}_{(i\rightarrow
j),m}<\sqrt{\dfrac{\gamma\sigma^{2}}{P}}\right].$ (34)

To simplify the analysis, the characteristic function approach is used for the
derivation of the outage probability. Each term of the above sum follows a
Rayleigh distribution, hence its characteristic function is [36]

$\phi_{i,j}(t)=1+\jmath t\sqrt{\dfrac{2\pi
a_{i,j}}{d_{i,j}^{\eta}}}\exp\bigg{(}-\dfrac{a_{i,j}t^{2}}{2d_{i,j}^{\eta}}\bigg{)}\Phi\bigg{(}\jmath
t\sqrt{\dfrac{a_{i,j}}{d_{i,j}^{\eta}}}\bigg{)}.$ (35)

Since the sum is a linear combination of independent random variables, its
characteristic function is the product of each individual’s characteristic
function. Using the Gil-Pelaez inversion theorem [37], we can obtain
$P_{o}(j,m)$ as (10).

###  -C Proof of Theorem 2

By considering $P\rightarrow\infty$, we notice that the outage probability at
the $j$-th relay converges to zero if it receives a signal from at least one
transmitter i.e., $C_{j,m}>0$, otherwise it is equal to one. Thus, the relays
that receive a signal are almost surely able to decode the message. Moreover,
if a transmitter has a full buffer at every time-slot and is always active,
then its corresponding receivers will also have constantly a full buffer. For
example, a relay that receives information from $S$ will always have a full
buffer, and if this relay is not in dual-mode operation, then its
corresponding receivers will also have full buffers at every time-slot. This
implies that the steady states of the transition matrix that do not conform
with the above observations will converge to zero.

According to (16), the system’s outage probability is a sum of $M$ terms that
depends on the stationary distribution of the MC and the outage probability at
the destination for each steady state. At the high $\mathrm{SNR}$ regime, the
terms of the sum in (16) that correspond to steady states converging to zero
are omitted. For each of the remaining terms, we obtain the network instance
associated with the corresponding MC state $s_{m}$ and derive the flow graph
$G_{m}$ from $S$ to $D$ for the paths that will surely forward the signals to
$D$ i.e., by omitting the dual-mode relays. Let
$\mathcal{T}_{m}=\\{T_{1,m},T_{2,m},\ldots\\}$ denote the complete set of cuts
separating $S$ and $D$ at $G_{m}$, and $\mathcal{L}_{i,m}$ denote the number
of links crossing the cut $T_{i,m}$. According to the information theoretic
max-flow min-cut theorem [38], the DMT that can be achieved by $G_{m}$ is
upper bounded by

$\delta_{m}(\rho)\leq\mathcal{L}_{m}=\min(\mathcal{L}_{i,m}).$ (36)

Note that $\mathcal{L}_{m}$ is equal to the minimum number of edge-disjoint
paths that forward information from $S$ to $D$. The system’s outage
probability is dominated by the terms that have the lowest order, or
equivalently by the minimum number of links crossing a cut $T_{i,m}$ from all
the derived flow graphs $G_{m}$, $1\leq m\leq M$,
$\boldsymbol{\pi}_{m}\nrightarrow 0$. Thus, by defining the target data rate
as $R=\log{(1+\gamma)}=\rho\log{P}$ and based on the results of [20] about the
DMT of networks that can organize their relays into parallel paths, the DMT is
given by (18).

###  -D Proof of Proposition 2

Recall that, by considering $P\rightarrow\infty$, the outage probability of a
node converges to zero if it receives at least one signal during one time-
slot. Thus, a receiver is in outage only if all its corresponding transmitters
remain silent. For an arbitrary signal $x(t)$ the system is in outage if the
signal cannot reach $D$, so the outage floor value is given by the aggregate
probability of the instances that fail to transfer the signal to $D$.
According to the proposed protocol, until time-slot $(t+k-1)$ the first $k$
relays will definitely receive and decode the signal $x(t)$ from $S$, which is
always active. If $N=k$, then the next node is $D$ and an outage occurs if all
the relays remain silent, for which the probability is calculated as (20).

For $N>k$, relay $k+1$ cannot receive $x(t)$ if the previous $k$ relays remain
silent during time-slot $(t+k)$, which occurs with probability $q^{k}$. For
the remaining time-slots, we can calculate the probability of the system being
in outage by equivalently considering the outage probability of another
network topology with $N-2$ relays and $k-1$ hops, since the first relay
cannot contribute anymore to the transmission of $x(t)$ and relay $k+1$ has
not decoded the signal, and so they can be omitted. On the contrary, relay
$k+1$ receives $x(t)$ at time-slot $(t+k)$ if at least one of its transmitters
is active, and this occurs with probability $(1-q^{k})$. In this case, the
outage probability for the remaining time-slots is matched to the outage
probability of an equivalent topology with $N-1$ relays and $k$ hops, by
considering the first relay as the new source node. This recursive behavior
leads to the calculation of the outage floor by (19).

## References

  * [1] A. Nicolaides, C. Psomas, and I. Krikidis, “Outage analysis of myopic multi-hop relaying: A Markov chain approach,” in _Proc. IEEE Global Commun. Conf.,_ Taipei, Taiwan, Dec. 2020, pp. 1–6.
  * [2] W. Saad, M. Bennis, and M. Chen, “A vision of 6G wireless systems: Applications, trends, technologies, and open research problems,” _IEEE Netw.,_ vol. 34, no. 3, pp. 134–142, May 2020.
  * [3] M. N. Tehrani, M. Uysal, and H. Yanikomeroglu, “Device-to-device communication in 5G cellular networks: challenges, solutions, and future directions,” _IEEE Commun. Mag.,_ vol. 52, no. 5, pp. 86–92, May 2014.
  * [4] X. Chen, D. W. K. Ng, W. Yu, E. G. Larsson, N. Al-Dhahir, and R. Schober, “Massive access for 5G and beyond,” _IEEE J. Sel. Areas Commun.,_ vol. 39, no. 3, pp. 615–637, Mar. 2021.
  * [5] R. Atallah, M. Khabbaz, and C. Assi, “Multihop V2I communications: a feasibility study, modeling, and performance analysis,” _IEEE Trans. Veh. Technol.,_ vol. 66, no. 3, pp. 2801–2810, Mar. 2017.
  * [6] J. G. Rois, F. G. Cuba, R. M. Akdeniz, F. J. G. Castaño, J. C. Burguillo, S. Rangan, and B. Lorenzo, “On the analysis of scheduling in dynamic duplex multihop mmWave cellular systems,” _IEEE Trans. Wireless Commun.,_ vol. 14, no. 11, pp. 6028–6042, Nov. 2015.
  * [7] N. Saeed, A. Celik, M. S. Alouini, and T. Y. Al-Naffouri, “Performance analysis of connectivity and localization in multi-hop underwater optical wireless sensor networks,” _IEEE Trans. Mobile Comput.,_ vol. 18, no. 11, pp. 2604–2615, Nov. 2019.
  * [8] Y. Chen, N. Zhao, Z. Ding, and M. S. Alouini, “Multiple UAVs as relays: multi-hop single link versus multiple dual-hop links,” _IEEE Trans. Wireless Commun.,_ vol. 17, no. 9, pp. 6348–6359, Sep. 2018.
  * [9] H. Wang, Y. Zhang, X. Zhang and Z. Li, “Secrecy and covert communications against UAV surveillance via multi-hop networks,” _IEEE Trans. Commun.,_ vol. 68, no. 1, pp. 389–401, Jan. 2020.
  * [10] M. O. Hasna and M. S. Alouini, “A performance study of dual-hop transmissions with fixed gain relays,” _IEEE Trans. Wireless Commun.,_ vol. 3, no. 6, pp. 1963–1968, Nov. 2004.
  * [11] E. Bjornson, M. Matthaiou, and M. Debbah, “A new look at dual-hop relaying: Performance limits with hardware impairments,” _IEEE Trans. Commun.,_ vol. 61, no. 11, pp. 4512–4525, Nov. 2013.
  * [12] M. O. Hasna and M. S. Alouini, “Outage probability of multihop transmission over Nakagami fading channels,” _IEEE Commun. Lett.,_ vol. 7, no. 5, pp. 216–218, May 2003.
  * [13] V. Jamali, N. Zlatanov, H. Shoukry, and R. Schober, “Achievable rate of the half-duplex multi-hop buffer-aided relay channel with block fading,” _IEEE Trans. Wireless Commun.,_ vol. 14, no. 11, pp. 6240–6256, Nov. 2015.
  * [14] X. Lin and J. G. Andrews, “Connectivity of millimeter wave networks with multi-hop relaying,” _IEEE Wireless Commun. Lett._ , vol. 4, no. 2, pp. 209–212, Apr. 2015.
  * [15] J. N. Laneman, D. N. C. Tse, and G. W. Wornell, “Cooperative diversity in wireless networks: Efficient protocols and outage behavior,” _IEEE Trans. Inf. Theory,_ vol. 50, no. 12, pp. 3062–3080, Dec. 2004.
  * [16] A. Ribeiro, X. Cai, and G. B. Giannakis, “Symbol error probabilities for general cooperative links,” _IEEE Trans. Wireless Commun.,_ vol. 4, no. 3, pp. 1264–1273, May 2005.
  * [17] J. Boyer, D. D. Falconer, and H. Yanikomeroglu, “Multihop diversity in wireless relaying channels,” _IEEE Trans. Commun.,_ vol. 52, no. 10, pp. 1820–1830, Oct. 2004.
  * [18] A. K. Sadek, W. Su, and K. J. R. Liu, “Multinode cooperative communications in wireless networks,” _IEEE Trans. Signal Process.,_ vol. 55, no. 1, pp. 341–355, Jan. 2007.
  * [19] C. Dong, L. L. Yang, and L. Hanzo, “Performance analysis of multihop-diversity-aided multihop links,” _IEEE Trans. Veh. Tech.,_ vol. 61, no. 6, pp. 2504–2516, Jul. 2012.
  * [20] K. Sreeram, S. Birenjith, and P. V. Kumar, “DMT of multihop networks: End points and computational tools,” _IEEE Trans. Inf. Theory,_ vol. 58, no. 2, pp. 804–819, Feb. 2012.
  * [21] L. Ong and M. Motani, “Myopic coding in multiterminal networks,” _IEEE Trans. Inf. Theory,_ vol. 54, no. 7, pp. 3295–3314, Jul. 2008.
  * [22] D. Niyato, E. Hossain, and A. Fallahi, “Sleep and wakeup strategies in solar-powered wireless sensor/mesh networks: Performance analysis and optimization,” _IEEE Trans. Mobile Comput.,_ vol. 6, no. 2, pp. 221–236, Feb. 2007.
  * [23] B. Medepally and N. B. Mehta, “Voluntary energy harvesting relays and selection in cooperative wireless networks,” _IEEE Trans. Wireless Commun.,_ vol. 9, no. 11, pp. 3543–3553, Nov. 2010.
  * [24] Y. Luo, J. Zhang, and K. B. Letaief, “Relay selection for energy harvesting cooperative communication systems,” in _Proc. IEEE Global Commun. Conf.,_ Atlanta, USA, Dec. 2013, pp. 2514–2519.
  * [25] R. Morsi, D. S. Michalopoulos, and R. Schober, “Performance analysis of near-optimal energy buffer aided wireless powered communication,” _IEEE Trans. Wireless Commun.,_ vol. 17, no. 2, pp. 863–881, Feb. 2018.
  * [26] S. Wang, W. Guo, Z. Zhou, Y. Wu, and X. Chu, “Outage probability for multi-hop D2D communications with shortest path routing,” _IEEE Commun. Lett.,_ vol. 19, no. 11, pp. 1997–2000, Nov. 2015.
  * [27] D. Korpi, M. Heino, C. Icheln, K. Haneda, and M. Valkama, “Compact inband full-duplex relays with beyond 100 dB self-interference suppression: enabling techniques and field measurements,” _IEEE Trans. Antennas Propag.,_ vol. 65, no. 2, pp. 960–965, Feb. 2017.
  * [28] T. Li, P. Fan, and K. B. Letaief, “Outage probability of energy harvesting relay-aided cooperative networks over rayleigh fading channel,” _IEEE Trans. Veh. Technol.,_ vol. 65, no. 2, pp. 972–978, Feb. 2016.
  * [29] J. Hu and N. C. Beaulieu, “Accurate simple closed-form approximations to Rayleigh sum distributions and densities,” _IEEE Commun. Lett.,_ vol. 9, no. 2, pp. 109–111, Feb. 2005.
  * [30] P. Hitczenko, “A note on a distribution of weighted sums of i.i.d. Rayleigh random variables,” _Sankhyā: The Indian Journal of Statistics, Series A (1961-2002),_ vol. 60, no. 2, pp. 171–175, Jun. 1998.
  * [31] L. Zheng and D. N. C. Tse, “Diversity and multiplexing: a fundamental tradeoff in multiple-antenna channels,” _IEEE Trans. Inf. Theory,_ vol. 49, no. 5, pp. 1073–1096, May 2003.
  * [32] A. Goldsmith, _Wireless Communications._ Cambridge: Cambridge University Press, 2005.
  * [33] Wolfram Mathematica Documentation - NMinimize. [Online]. Available: https://reference.wolfram.com/language/ref/NMinimize.html
  * [34] R. G. Gallager, _Stochastic Processes: Theory for Applications._ Cambridge: Cambridge University Press, 2013.
  * [35] I. Krikidis, T. Charalambous, and J. S. Thompson, “Buffer-aided relay selection for cooperative diversity systems without delay constraints,” _IEEE Trans. Wireless Commun.,_ vol. 11, no. 5, pp. 1957–1967, May 2012.
  * [36] A. Papoulis and S. U. Pillai, _Probability, Random Variables, and Stochastic Processes,_ 4th ed. McGraw Hill, 2002.
  * [37] J. Gil-Pelaez, “Note on the inversion theorem,” _Biometrika,_ vol. 38, no. 3-4, pp. 481–482, Dec. 1951.
  * [38] T. M. Cover and J. Thomas, _Elements of Information Theory._ New York: Wiley, 1991.


# Prioritized Multi-Tenant Traffic Engineering for Dynamic QoS Provisioning in
Autonomous SDN-OpenFlow Edge Networks

Mohammad Sajid Shahriar, Faisal Ahmed, Genshe Chen, Khanh D. Pham, Suresh
Subramaniam,
Motoharu Matsuura, Hiroshi Hasegawa, and Shih-Chun Lin  Mohammad Sajid
Shahriar, Faisal Ahmed, and Shih-Chun Lin are with North Carolina State
University, NC, USA (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>slin23@ncsu.edu). Genshe Chen is with Intelligent Fusion Technology, Inc., MD,
USA (e-mail: gchen@intfusiontech.com). Khanh D. Pham is with the Air Force
Research Laboratory (AFRL), NM, USA (e-mail: khanh.pham.1@spaceforce.mil).
Suresh Subramaniam is with George Washington University, WA, USA (e-mail:
suresh@gwu.edu). Motoharu Matsuura is with the University of Electro-
Communications, Tokyo, Japan (e-mail: m.matsuura@uec.ac.jp). Hiroshi Hasegawa
is with Nagoya University, Nagoya, Japan (e-mail:
hasegawa@nuee.nagoya-u.ac.jp).

###### Abstract

This letter indicates the critical need for prioritized multi-tenant quality-
of-service (QoS) management by emerging mobile edge systems, particularly for
high-throughput beyond fifth-generation networks. Existing traffic engineering
tools utilize complex functions baked into closed, proprietary
infrastructures, largely limiting design flexibility, scalability, and
adaptiveness. Hence, this study introduces a software-defined networking
(SDN)-based dynamic QoS provisioning scheme that prioritizes multi-tenant
network traffic while focusing on the base station-edge cloud scenario. The
designed scheme first separates control and data planes and enables traffic
management automation using SDN programmability. It then implements dynamic
QoS management via the SDN-OpenFlow protocol, which ensures ample bandwidth
for multiple priority flows and efficiently manages the remaining bandwidth
for non-priority traffic. Empirical experiments are conducted with a Mininet
network emulator and an OpenDayLight controller. Performance evaluation
validates the proposed scheme’s effectiveness in meeting multi-tenant QoS
criteria, offering a robust solution for traffic prioritization in SDN-based
edge networks.

###### Index Terms:

Multi-tenancy, prioritized traffic engineering, dynamic QoS provisioning, SDN-
OpenFlow platforms, autonomous network management, and edge systems.

##  I Introduction

The advent of beyond-fifth-generation (B5G) mobile technology underscores the
necessity for uniform control plane operations [1] and dynamic quality-of-
service (QoS) management to meet its standards [2], which aim for higher data
rates and reduced latency. Traditional network infrastructures, however, face
challenges in adhering to these standards due to their complexity and the
limitations of existing QoS management protocols, such as DiffServ [3], which
are either too complex for practical use or lack the needed precision [4]. In
response to these challenges, software-defined networking (SDN) has emerged as
a significant innovation, providing a solution to the rigidity and complexity
of conventional cellular networks by separating the control and data planes.
This separation enhances network programmability and centralizes control,
offering a holistic view of network resources, which facilitates improved
traffic engineering and QoS management [5], [6].

SDN’s dynamic adaptability to changes in policy and configuration requirements
marks a departure from the manual and static configurations of traditional
networks. Its flexibility is particularly advantageous for traffic engineering
and prioritization, offering a promising avenue for managing various
applications, including unmanned aerial vehicles, autonomous vehicles, smart
factories, and public safety operations [6]. A notable application of SDN is
in prioritizing network traffic for emergency services, crucial for efficient
relief and response during large public gatherings [7]. This requires adaptive
network solutions capable of tailoring resource allocation to the specific
needs of each emergency scenario, from high-bandwidth needs for quality video
streaming to minimal bandwidth for basic communications. Guaranteeing
bandwidth allocation for emergency or priority traffic while optimizing the
use of remaining bandwidth for lower-priority traffic showcases SDN’s
potential to enhance network responsiveness and efficiency in critical
situations.

In consideration of the foregoing observations, this letter introduces an SDN-
based traffic engineering scheme that is designed to guarantee the allocation
of ample bandwidth for emergency network traffic. Simultaneously, it optimizes
the allocation of remaining network bandwidth to low-priority traffic flows
through the utilization of the SDN-OpenFlow [8] protocol. The main
contributions are summarized below:

  * •

To enhance low latency communication for multi-tenant environments, this study
introduces an innovative SDN-based edge-cloud platform within the network
architecture. This platform aims to minimize the distance between data sources
and the network’s base stations, facilitating reduced latency and intelligent
networking solutions.

  * •

To prioritize the QoS provisioning in multi-tenant communication systems, this
work utilizes a traffic classification method to identify priority traffic.
Moreover, dynamic QoS provisioning is proposed to establish QoS goals and
create rules to prevent any decline in priority traffic flow performance.

  * •

The effectiveness of the proposed dynamic QoS provisioning scheme is realized
by utilizing an OpenDayLight (ODL)-based controller to collect traffic data
and enforce QoS policies while simulating the data plane by using a Mininet
network emulator to strategically control the forwarding and metering of
flows.

##  II State-of-the-Arts

Recent studies have emphasized integrating QoS within the SDN framework to
enhance bandwidth guarantees and achieve general QoS objectives. While some
research [9, 10] have focused on QoS improvements, they have not specifically
concentrated on bandwidth assurance. To bridge this gap, authors in [11]
categorize network flows into QoS and best-effort flows, employing a path
selection strategy that considers requested rates for improved bandwidth
management. A significant development is considered in [12], where OpenFlow
meters and queues are used to differentiate flows, ensuring minimum bandwidth
for QoS flows and integrating an admission control process to verify network
path support for these flow rates. This bandwidth-guarantee design includes
traffic flow monitoring at ingress switches and uses multi-queue
configurations at egress ports for prioritization. Also, MPLS tunnels are
implemented from bandwidth assurance [4]; pre-configured network slices are
provided for optimizing QoS and throughput [13].

Despite these prior accomplishments, managing QoS in networks with multiple
tenants’ priority flows remains complex. Hence, this letter introduces a
dynamic QoS provisioning scheme within an SDN-based traffic engineering
platform aimed at prioritizing emergency traffic and enhancing resource
allocation in multi-tenant scenarios, representing a significant advancement
in network traffic management.

Figure 1: An exemplary scenario of SDN-enabled multi-tenant edge networks.

##  III Autonomous Software-Defined Edge Networks

This paper introduces a novel approach to managing QoS effectively by
prioritizing traffic, aiming to enhance open and smart networking in 6G
communication systems. Fig. 1 shows our considered SDN infrastructure in a BS-
EC scenario (e.g., an SDN cellular system [14]) that can accommodate multiple
heterogeneous tenants. This system comprises a single region cloud (RC), $E$
number of ECs that represented by set
$\mathsf{E}=\\{1,2,3,\dots,e,\dots,E\\}$, $N$ number of BSs, and $G$ number of
ground stations (GSs) that indexed by set
$\mathsf{N}=\\{1,2,3,\dots,n,\dots,N\\}$ and
$\mathsf{G}=\\{1,2,3,\dots,g,\dots,G\\}$, respectively. Each EC is connected
to an SDN controller, which orchestrates the data plane and the traffic flows
between the EC and the tenants. For simplicity, we will focus on a single EC,
denoted as $e$, and let $\mathsf{N}_{e}=\\{1,2,3,\dots,n_{e},\dots,N_{e}\\}$
and $\mathsf{G}_{e}=\\{1,2,3,\dots,g_{e},\dots,G_{e}\\}$ denote the set of BSs
and GSs that are covered by that EC $e$, respectively.

As illustrated in Fig. 2, the operation of the proposed system commences with
monitoring data traffic and their classification, subsequently translating
these classifications into well-defined QoS objectives. After that,
instructions for prioritizing bandwidth allocation are generated and employed
by the data plane utilizing the ODL service functions.

Figure 2: The proposed prioritized multi-tenant traffic engineering platform.

The SDN framework presented encompasses a control plane responsible for
managing flow tables and instructions and a data plane focused on enacting
match-plus-action forwarding rules. It includes an ODL controller and a
northbound application configuring QoS priorities via RestAPI, exploiting
OpenFlow programming. Additionally, the setup integrates a simulated data
plane using Mininet with OpenFlow switches for optimal flow forwarding and
metering aimed at achieving the desired QoS. Mininet acts as a network
emulator, facilitating the development and evaluation of complex network
configurations on a single server.

##  IV Multi-Tenant Quality-of-Service Provisioning with Traffic
Prioritization

To prioritize QoS provisioning for traffic originating from various tenants,
our proposed system maintains a set of pre-established QoS goals. These goals
outline the target bandwidth for each priority class, corresponding to the
traffic generated by distinct tenants. Meter tables within the OpenFlow
switches which work similar to leaky buckets, are used to put the QoS goals
into effect. By configuring meter bands with the flow tables, we gain control
over the bandwidth usage of priority and non-priority traffic flows. This
requires distinguishing between priority and non-priority traffic, which is
achieved by operating with a predefined set of network traffic classes
$C_{p}$. These are predefined as “priorities,” and each of them is associated
with a specific QoS goal $Q$. The system classifies a set of traffic classes
$C_{t}$ utilizing the traffic classification method (such as via a machine
learning approach [15]) by monitoring network traffic at a period of $T$. It
then determines whether $C_{t}$ is present in $C_{p}$. Accordingly, our design
tackles the prioritization problem in three scenarios:

  * •

A single match, (i.e., $|C_{p}\cap C_{t}|=1$);

  * •

Multiple matches (i.e., $|C_{p}\cap C_{t}|>1$);

  * •

No match of priority class (i.e., $|C_{p}\cap C_{t}|=0$).

In the first and second cases, the goal is to provide better QoS to priority
traffic. However, the second scenario poses the challenge of prioritizing
bandwidth between multiple priority flows, assuming the maximum bandwidth of
every link is $B_{\text{max}}$. However, where there is no match of a priority
class, guaranteed QoS is not required. This scheme addresses the challenges of
the scenarios by generating specific meter bands and QoS policies using
Algorithm 1. It also considers the QoS for non-priority flows when the
parameter $b_{\text{min}}$ is set to a value greater than zero. This parameter
specifies the minimum bandwidth assigned to each non-priority flow when
priority flows are present.

Algorithm 1 Generating QoS Rules Based on Traffic Priority.

1:if $|C_{p}\cap C_{t}|=1$ and $|C_{t}|>1$ then

2: if $Q(C_{p}\cap C_{t})>B_{\text{max}}-(|C_{t}|-1)*b_{\text{min}}$ then

3: if $b_{\text{min}}>0$ then

4: Set meter of $B_{\text{max}}-(|C_{t}|-1)*b_{\text{min}}$ to flow $C_{p}\cap
C_{t}$

5: Set meter band of $b_{\text{min}}$ to the flows of $C_{t}-C_{p}$

6: else

7: Drop packet for the flows of $C_{t}-C_{p}$

8: end if

9: else

10: if $b_{\text{min}}>0$ then

11: Set meter of $Q(C_{p}\cap C_{t})$ to the flows of $C_{p}\cap C_{t}$

12: end if

13: Set meter of $\frac{B_{\text{max}}-Q(C_{p}\cap C_{t})}{|C_{t}|-1}$ to
flows of $C_{t}-C_{p}$

14: end if

15:else if $|C_{p}\cap C_{t}|>1$ then

16: if $\sum_{d\in C_{p}\cap
C_{t}}Q(d)>B_{\text{max}}-|C_{t}-C_{p}|*b_{\text{min}}$ then

17: $r=\frac{B_{\text{max}}-|C_{t}-C_{p}|*b_{\text{min}}}{\sum_{d\in C_{p}\cap
C_{t}}Q(d)}$

18: Set meter band of $r*Q(d)$ to flows of $C_{p}\cap C_{t}$

19: if $b_{\text{min}}>0$ then

20: Set meter band of $b_{\text{min}}$ to flows $C_{t}-C_{p}$

21: else

22: Drop packet for the flows of $C_{t}-C_{p}$

23: end if

24: else

25: Set meter band of $Q(c)$ to flows of $C_{p}\cap C_{t}$

26: Set meter of $\frac{B_{\text{max}}-\sum_{d\in C_{p}\cap
C_{t}}Q(d)}{|C_{t}-C_{p}|}$ to flows $C_{t}-C_{p}$

27: end if

28:else

29: Reset the flow table to default

30:end if

In Algorithm 1, our proposed traffic engineering scheme adjusts meter bands
and updates flow entries when dealing with one or multiple priority classes.
The use cases are outlined below:

  * •

Case 1 (Single-Priority Flow): In cases where the network traffic includes a
single priority flow and at least one non-priority flow, Algorithm 1 makes
strategic decisions on packet dropping using designated or calculated meter
bands. The choice of imposing meter on either both priority and non-priority
flows or solely on non-priority flows depends on whether the combined
bandwidth goals for priority and non-priority flows exceed $B_{\text{max}}$
and if the value of $b_{\text{min}}$ is greater than zero.

  * •

Case 2 (Multi-Priority Flow): In more complex scenarios featuring multiple-
priority classes within the network traffic, if the total target bandwidth for
all priority flows (i.e., represented by $\sum_{d\in C_{p}\cap C_{t}}Q(d)$)
exceeds $B_{\text{max}}$, the dynamic QoS provisioning of the scheme carefully
adjusts the meter rates for each priority flow. This adjustment is made using
a factor $r$ that considers the $Q$ value of each priority flow. Conversely,
when the total target bandwidth is within $B_{\text{max}}$, the scheme
utilizes the $Q$ values to set meter rates for each priority flow, ensuring
they do not compete for bandwidth among themselves. Simultaneously, the scheme
considers non-priority flows based on $b_{\text{min}}$, similar to the
previous use case.

  * •

Case 3 (No-Priority Flow): In instances where the network traffic lacks any
priority flow, the scheme reverts the flow entries to their initial
configuration. This reset signifies a return to a baseline state, where no
specific traffic class is given preferential treatment in terms of bandwidth
allocation.

##  V Performance Evaluation

To assess the effectiveness of the proposed scheme, we analyze three flows
($f_{1}$, $f_{2}$, and $f_{3}$) using Mininet simulation, as illustrated in
Fig. 2. It is assumed that $f_{1}$, $f_{2}$, and $f_{3}$ correspond to base
stations $BS_{1}$, $BS_{2}$, and $BS_{3}$, respectively. Figs. 3 and 4 show
the generated and received traffic rates over a 25-second period, with every
$T=5$ second for flow priority identification by the SDN controller. However,
fig. 4 emphasizes on specific time period to demonstrate the advantage of the
proposed scheme. The traffic patterns for $f_{1}$, $f_{2}$, and $f_{3}$ are
configured at $7Mbps$, $5Mbps$, and $3Mbps$, respectively, to demonstrate
various scenarios—such as with one, multiple, or no priority flows—where the
overall traffic might exceed the total link capacity $B_{\text{max}}$ set at
$10Mbps$.

In Fig. 3, the proposed autonomous edge network and QoS provisioning scheme
are not utilized. It reveals that flows from different tenants compete for
bandwidth, resulting in throughput degradation when the overall generated
traffic surpasses the link bandwidth.

Fig. 4 (a) demonstrates that for case 1, among the three flows, only $f_{1}$
(marked by *) is identified as the priority flow with a $Q$ value of $6Mbps$
(i.e., the suggested throughput). The drop meters set by the proposed scheme
effectively limit the traffic rate of non-priority flows, preventing
interference in achieving the target throughput of the priority flow. Fig. 4
(b) shows the outcomes when the traffic engineering platform recognizes two
priority flows, $f_{1}$ and $f_{2}$ (marked by *), each having $Q$ values of
$6Mbps$ and $4Mbps$, respectively. This highlights the influence of drop
meters dynamically configured by the scheme at regular intervals to handle the
$b_{\text{min}}$ of $1Mbps$ for the non-priority flow. The result demonstrates
that the proposed scheme not only prevents major degradation in performance
for priority flows but also accommodates the non-priority flow, ensuring that
the minimum QoS is maintained. However, the data transmissions in Mininet do
not always reach the expected bandwidth because of overheads and shared
resources among hosts.

Figure 3: Throughput of individual flows without employing the proposed
traffic engineering platform. Figure 4: Throughput of each flow in (a) single-
priority and (b) multi-priority cases (priority flows are marked with ‘*’)
under the provisioning of proposed traffic engineering platform.

##  VI Conclusions

We introduced novel dynamic QoS provisioning within an SDN edge framework
tailored for prioritizing traffic in multi-tenant networks. The proposed
scheme revamped the SDN-OpenFlow protocol and ensured QoS adherence by
allocating specific bandwidth employing meters bands in the data plane for
precise data flow control, effectively managing bandwidth to enable target QoS
achievement. Empirical experiments validated our design’s efficacy in
bandwidth allocation, multi-tenancy sharing, and QoS policy management, thus
setting this work as a reference for future traffic engineering.

## Acknowledgment

This material is partially based upon work supported by the United States Air
Force under contract No. FA9453-23-P-A044. Any opinions, findings and
conclusions or recommendations expressed in this material are those of the
authors and don’t necessarily reflect the views of the AFRL, United States Air
Force, or the U.S. Government. We gratefully acknowledge support from the
AFRL, the NC Space Grant, the National Science Foundation (NSF) under Grant
CNS-2210344, the North Carolina Department of Transportation (NCDOT) under
Award TCE2020-03, and Meta 2022 AI4AI Research.

## References

  * [1] Marius Corici, Fabian Eichhorn, and Thomas Magedanz, “Organic 6G Continuum Architecture: A Uniform Control Plane Across Devices, Radio, and Core,” IEEE Networking Letters, 2023\.
  * [2] Z. Zhang, et al. “Quality-of-Experience Evaluation for Digital Twins in 6G Network Environments,” _IEEE Transactions on Broadcasting_ , 2024.
  * [3] M. P. Fernandez, A. C. R. Pedroza, and J. F. de Rezende, “QoS Provisioning across a DiffServ Domain using Policy-Based Management,” in _IEEE Global Communications Conference (GLOBECOM)_ , 2001.
  * [4] C. Morin, G. Texier, and C. -T. Phan, “On Demand QoS with a SDN Traffic Engineering Management (STEM) Module,” in _International Conference on Network and Service Management (CNSM)_ , 2017.
  * [5] Martin Slabber, Neco Ventura, and Joyce Mwangama, “SDN-Based Multicast Traffic Engineering for Radio Telescope Data Networks,” IEEE Networking Letters, vol. 6, no. 1, pp. 65-69, 2024\. doi: 10.1109/LNET.2023.3319965.
  * [6] A. Mendiola, J. Astorga, E. Jacob, and M. Higuero, “A Survey on the Contributions of Software-Defined Networking to Traffic Engineering,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 2, pp. 918-953, secondquarter 2017.
  * [7] J. Moeyersons, et al., “Enabling Emergency Flow Prioritization in SDN Networks,” in _International Conference on Network and Service Management (CNSM)_ , 2019.
  * [8] N. McKeown, et al. “OpenFlow: Enabling Innovation in Campus Networks,” _ACM SIGCOMM Computer Communication Review_ , vol. 38, no. 2, pp. 69-74, April 2008.
  * [9] J. Yan, et al. “HiQoS: An SDN Based Multipath QoS Solution,” _China Communications_ , vol. 12, no. 5, pp. 123-133, 2015.
  * [10] Y. Zhang, Y. Tang, D. Tang, and W. Wang, “QOF: QoS Framework Based on OpenFlow,” in _International Conference on Information Science and Control Engineering (ICISCE)_ , 2015.
  * [11] A. V. Akella and K. Xiong, “Quality of Service (QoS)-Guaranteed Network Resource Allocation via Software Defined Networking (SDN),” in _IEEE International Conference on Dependable, Autonomic and Secure Computing (DASC)_ , 2014.
  * [12] H. Krishna, N. L. M. v. Adrichem, and F. A. Kuipers, “Providing Bandwidth Guarantees with OpenFlow,” in _Symposium on Communications and Vehicular Technologies (SCVT)_ , 2016.
  * [13] Y. Lu, B. Fu, X. Xi, Z. Zhang, and H. Wu, “An SDN-Based Flow Control Mechanism for Guaranteeing QoS and Maximizing Throughput,” _Wireless Personal Communications_ , vol. 97, no. 1, pp. 417-442, 2017.
  * [14] I. F. Akyildiz, P. Wang, and S.-C. Lin, “SoftAir: A Software Defined Networking Architecture for 5G Wireless Systems,” _Computer Network (Elsevier) Journal_ , vol. 85, pp. 1-18, July 2015.
  * [15] P. Wang, S.-C. Lin, and M. Luo, “A Framework for QoS-Aware Traffic Classification using Semi-Supervised Machine Learning in SDNs,” in _IEEE International Conference on Services Computing (SCC)_ , 2016.