# Transferable and Distributed User Association Policies for 5G and Beyond
Networks

Mohamed Sana1, Nicola di Pietro2, Emilio Calvanese Strinati1 1CEA-Leti,
Université Grenoble Alpes, F-38000 Grenoble, France
2Athonet, via Cà del Luogo 6/8, 36050, Bolzano Vicentino (VI), Italy
Email: {mohamed.sana<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study the problem of user association, namely finding the optimal
assignment of user equipment to base stations to achieve a targeted network
performance. In this paper, we focus on the _knowledge transferability_ of
association policies. Indeed, traditional non-trivial user association schemes
are often scenario-specific or deployment-specific and require a policy re-
design or re-learning when the number or the position of the users change. In
contrast, transferability allows to apply a single user association policy,
devised for a specific scenario, to other distinct user deployments, without
needing a substantial re-learning or re-design phase and considerably reducing
its computational and management complexity. To achieve transferability, we
first cast user association as a multi-agent reinforcement learning problem.
Then, based on a neural _attention mechanism_ that we specifically conceived
for this context, we propose a novel distributed policy network architecture,
which is transferable among users with _zero-shot generalization capability_
i.e., without requiring additional training.Numerical results show the
effectiveness of our solution in terms of overall network communication rate,
outperforming centralized benchmarks even when the number of users doubles
with respect to the initial training point.

††This work has been partially supported by the CPS4EU Project, Nr. 826276 and
the H2020 RISE-6G Project.

##  I Introduction

With the proliferation of smart connected devices, the cyber and physical
spaces are fusing, turning humans, objects and events more and more into
exponentially growing sources of digital information [1]. To cope with this,
modern wireless networks, such as 5G networks, are becoming denser and
heterogeneous with the coexistence of base stations (BSs) operating at
different frequencies. In this context, _user association_ , namely
efficiently finding optimal assignments of user equipments (UEs) to BSs to
achieve a targeted network performance, is a crucial challenge because it
directly affects the network spectral efficiency and the users’ perceived
quality of service. In general, for dense networks, this is a challenging task
as it involves non-convex and combinatorial optimization problems, whose
complexity grows exponentially with the number of UEs. This difficulty is even
exacerbated in highly dynamic networks such as in millimeter-wave (mmWave)
networks, subject to frequent changes of the radio environment due to highly
directional transmissions and variable channel conditions [2].

To address these issues, we propose a scalable and easily manageable user
association policy. Our proposed approach is conceived with a specific focus
on the key aspect of _transferability_ , which allows to apply a user
association strategy or policy acquired in a specific scenario (e.g. a network
deployment) to distinct but related ones, without needing to substantially
redesign, recompute or relearn it. This considerably reduces the computational
complexity of user association during the network operations and makes the
policy adapted to distributed and dynamic scenarios. So far, despite their
many appreciable features, solutions of the literature lack transferability.
In [3], a distributed user association scheme is proposed using Lagrangian
tools. The user association is reformulated as a non-cooperative game with
local interactions in [4] and as a matching game in [5]. However, every time
the radio environment changes due to, for instance, the arrival or departure
of UEs, this solution needs to be recomputed to seek a new convergence point
and to correct a possible drift from optimality. Recently, a deep neural
network (NN) architecture was introduced in [6] that predicts the user
association and power allocation. Similarly, authors in [7] formulated the
problem of user association as a multi-label classification problem. In [8, 9,
10], the authors proposed an approach based on distributed _multi-agent
reinforcement learning_. However, whenever the number of UEs change, these
solutions either require a new learning procedure [6, 10] or to entirely
redesign and retrain the architecture of the NNs [8]. With the complexity
associated to the re-computation or re-learning procedures, such approaches
are unsuitable to dynamic networks, characterized by a frequent change of the
radio environment due to e.g. mobility or the arrival and departure of UEs.

Here, to overcome the inadequacy of state-of-the-art solutions, we first cast
the user association problem as a multi-agent reinforcement learning problem,
aimed at optimizing predefined network utility functions common to all UEs.
Then, by conveniently adapting to this context a _neural attention mechanism_
, we successfully design a global policy network architecture (PNA) that is
transferable among UEs. Given this PNA, UEs learn a common association policy
leveraging their local (and global, if available) observations. The learned
policy has _zero-shot generalization capability_ , thus considerably reducing
the computational complexity of the user association task. Indeed, thanks to
the proposed architecture, a policy learned in a specific deployment can be
transferred to another one without requiring substantial additional training
procedure. Consequently, as desired, the proposed mechanism adapts well and by
design to variations in the number of UEs or changes in the geometry of the
network (namely the geographical positions of the UEs). Moreover, the proposed
mechanism incorporates channels’ and UEs’ traffic dynamics during the training
phase to foster better adaptability to the variations of radio channel quality
and requested quality of service (QoS). Finally, our proposed solution can be
implemented either in a centralized or in a distributed manner to trade-off
computational complexity and/or signaling overhead.

##  II System Model and Problem Formulation

MBS$\mathrm{SBS}_{1}$$\mathrm{SBS}_{2}$$\mathrm{SBS}_{3}$$\boldsymbol{\times}$$u_{2}$$\boldsymbol{\times}$$u_{3}$$\boldsymbol{\times}$$u_{4}$$\boldsymbol{\times}$$u_{5}$$\boldsymbol{\times}$$u_{6}$$\boldsymbol{\times}$$u_{7}$$\boldsymbol{\times}$$u_{8}$$\boldsymbol{\times}$$u_{1}$$\boldsymbol{\times}$$u_{9}$$\boldsymbol{\times}$$u_{10}$$\mathrm{SBS}_{4}$$\mathrm{SBS}_{5}$
Figure 1: Network topology for $N_{s}=3$ SBSs, 1 MBS, and $K=10$ UEs.

###  II-A Network Model

We consider the system model of Fig. 1 as in [10]: we focus on downlink
communications in a network of $K(t)$ UEs located at time $t$ in a region of
the bi-dimensional Euclidean space, covered by $N_{s}$ mmWave small base
stations (SBSs) and a sub-6 GHz macro base station (MBS), to enable ubiquitous
network coverage. Let $\mathcal{A}=\\{0,1,\dots,N_{s}\\}$ be the set of BSs,
where $0$ indexes the MBS, and $\mathcal{U}(t)=\\{1,2,\dots,K(t)\\}$ be the
set of UEs in the network. We call a network deployment $\mathcal{D}(t)$, a
collection of positions of all UEs in the network:

$\mathcal{D}(t)=\left\\{\left(x_{j}(t),y_{j}(t)\right),j\in\mathcal{U}(t)\right\\},$
(1)

where $x_{j}(t)$ and $y_{j}(t)$ denote respectively the two coordinates of UE
$j$ in deployment $\mathcal{D}(t)$, expressed with respect to a reference
system common to all UEs and BSs.

We denote with $\mathcal{A}_{j}(t)=\\{i,d_{i,j}(t)\leq
R_{0}\\}\cup\\{0\\}\subseteq\mathcal{A}$ the subset of BSs that can be
associated with UE $j$ at time $t$. Here, $R_{0}$ is the SBSs’ coverage range
and $d_{i,j}(t)$ is the distance from UE $j$ to SBS $i$, which we assume to be
able to support at most $N_{i}$ UEs simultaneously. Also, we assume that a UE
is associated to exactly one BS at a time and each BS $i$ communicates to its
served UEs using equal transmit power. We adopt the Friis propagation loss
model [11], according to which the power received by a UE, $P^{\mathrm{Rx}}$,
is given as a function of the distance $d$ between the UE and its serving BS:

$P^{\mathrm{Rx}}(d)=hP_{s}^{\mathrm{Tx}}G_{s}^{\mathrm{Tx}}G_{s}^{\mathrm{Rx}}C_{s}d^{-\eta_{s}},~{}~{}s\in\\{\mathrm{MBS},\mathrm{SBS}\\}.$
(2)

Here, $C_{s}$ denotes the path-loss constant, $\eta_{s}$ is the path-loss
exponent, $P_{s}^{\mathrm{Tx}}$ is the transmit power w.r.t. BS $s$ and $h$
denotes the fading coefficient. We assume $m$-Nakagami fading for UE-SBS links
whereas UE-MBS links experience Rayleigh fading, which is a special case of
$m$-Nakagami, where $m=1$. The gains of the transmitter and receiver antennas
w.r.t. BS $s$ are $G_{s}^{\mathrm{Tx}}$ and $G_{s}^{\mathrm{Rx}}$
respectively. In addition, we assume that mmWave SBSs allocate all the
available band to their served UEs, whereas the MBS equally shares its band
across its UEs. Also, we assume that UEs and BSs perform beam steering and
training in advance and ignore their impact when optimizing user association.
Finally, we assume that there exists a central controller, collocated with the
MBS, able to collect and forward information to the UEs.

###  II-B Problem formulation

At time $t$, each UE $j$ requests a data rate $D_{j}(t)$ from its serving BS
$i$ to satisfy a certain QoS. It then experiences a signal-to-interference
plus noise ratio $\mathrm{SINR}_{i,j}$, which comprises both intra-cell and
inter-cell interference. We say that UE $j$’s QoS is fully satisfied at time
$t$, if the achievable data rate
${R_{i,j}(t)=B_{i,j}\mathrm{log}_{2}\left(1+\mathrm{SINR}_{i,j}(t)\right)}$,
given by the Shannon capacity of the channel between UE $j$ and BS $i$, is
greater than $D_{j}(t)$. Therefore, the effective communication rate between
UE $j$ and its serving BS equals
$\mathrm{min}\left(R_{i,j}(t),{D_{j}(t)}\right)$. Hence, we define an
$\alpha$-fair _network utility function_ [12] as follows:

$\displaystyle R(t)$
$\displaystyle=\sum_{i\in\mathcal{A}}\sum_{j\in\mathcal{U}(t)}x_{i,j}(t)U_{\alpha}\left(\mathrm{min}\left(R_{i,j}(t),D_{j}(t)\right)\right),$
(3)
$\displaystyle=\sum_{i\in\mathcal{A}}\sum_{j\in\mathcal{U}(t)}x_{i,j}(t)U_{\alpha}\left(\kappa_{i,j}(t)D_{j}(t)\right),$

where $x_{i,j}(t)=1$ indicates that UE $j$ is associated with BS $i$ at time
$t$; otherwise $x_{i,j}(t)=0$ and
$\kappa_{i,j}(t)=\mathrm{min}\left(1,\frac{R_{i,j}(t)}{D_{j}(t)}\right)\in[0,1]$
indicates the QoS satisfaction of UE $j$ w.r.t. its associated BS $i$, which
is fully satisfied when $\kappa_{i,j}(t)=1$. $U_{\alpha}(\cdot)$ is the
$\alpha$-fair utility function given in [12, Section 2.2] as follows:

$U_{\alpha}(x)={}\left\\{\begin{array}[]{l
l}(1-\alpha)^{-1}{x^{1-\alpha}},&\text{~{}if~{}}\alpha\geq
0\text{~{}and~{}}\alpha\neq 1,\\\
\mathrm{log}(1+x),&~{}\alpha=1.\end{array}\right.$ (4)

Given a network deployment $\mathcal{D}(t)$, we formulate the user association
problem to maximize (3) at time $t$ as follows:

$\displaystyle\underset{\\{x_{i,j}(t)\\}}{\mathrm{maximize}}~{}$
$\displaystyle R(t),$ (5a) $\displaystyle\mathrm{subject~{}to~{}}$
$\displaystyle x_{i,j}(t)\in\\{0,1\\},~{}\forall i,j,$ (8a)
$\displaystyle\sum_{j\in\mathcal{U}(t)}x_{i,j}(t)\leq N_{i},~{}\forall
i\in\mathcal{A}\backslash\\{0\\},$
$\displaystyle\sum_{i\in\mathcal{A}_{j}(t)}x_{i,j}(t)=1,~{}\forall
j\in\mathcal{U}(t).$

Constraint (8a) indicates that the $x_{i,j}(t)$ are binary variables. The
number of resources available at each SBS is limited; this is highlighted in
(8a), by constraining the number of UEs simultaneously associated with a given
SBS $i$, to be lower than $N_{i}$. Finally, (8a) ensures that, in our setting,
each UE is associated with exactly one BS. Depending on $\alpha$, problem (5a)
guarantees different fairness criteria in the user association. In particular,
we will focus on $\alpha=0$ and $\alpha=1$, corresponding respectively to sum-
rate maximization and proportional fairness, widely used in the literature
[13].

Although (5a) appears as a standard user association problem, solutions of the
literature are often scenario-specific or deployment-specific. In other words,
they assume either a pre-sized or a fixed set of static UEs. Here, we are
interested in a different approach: first, we are looking for a policy that
can be applied at each time $t$ by a user, based on its instantaneous
observations of the environment. Then, taking into account the targeted
optimization objective, we are interested in an association policy, which,
once learned, is also transferable and capable of solving problem (5a) at each
time $t$ regardless of the location and the number of UEs in the network,
without the need of being relearned. This policy must be able to adapt to the
departure or arrival of UEs from and in the network, as both events have an
impact on the optimal user association. Also, a policy learned in a scenario
of $K_{1}$ UEs has to be effectively applicable to a scenario of $K_{2}\neq
K_{1}$ UEs without additional training. For this purpose, the architecture of
the association policy needs to be transferable, as well as the learned
policy.

##  III Proposed Transferable User Association policy

###  III-A On transferable policy network architecture

In order for the policy architecture to be transferable, an adequate design of
the PNA components is required. Our objective, in fact, is to construct a
policy architecture whose size does not vary with the number of UEs in the
network, which is bound to change over time. In the following, we will
describe the policy network architecture of Fig. 2, which allows the
transferability of the association policy.

####  III-A1 UE local observation encoding

In this study, we assume that at each time $t$, each UE $j$ can estimate the
received signal strength (RSS) and the corresponding angle of arrival (AoA)
w.r.t. its surrounding BSs. We denote with $\mathrm{RSS}_{i,j}$ and
$\vartheta_{i,j}$ the estimated RSS and AoA of UE $j$ w.r.t. BS $i$,
respectively. Moreover, as in [10], a UE receives an acknowledgment (ACK)
signal whenever its connection request succeeds ($\mathrm{ACK}_{j}=1$) or is
denied ($\mathrm{ACK}_{j}=0$), which may happen due to the limited resources
available at each BS (8a); we call this event a _collision_. When it happens,
each BS selects among the colliding UEs the best ones to associate with,
according to their association probability that we define later. Next, we
define UE $j$ local state, $\boldsymbol{\mathrm{o}}_{j}^{\textsc{L}}(t)$, as
follows:

$\displaystyle\begin{split}\boldsymbol{\mathrm{o}}_{j}^{\textsc{L}}(t){}={}&\bigg{\\{}a_{j}(t-1),R_{a_{j}(t-1),j},R(t-1),\\\
&{}\mathrm{ACK}_{j},\left\\{\mathrm{RSS}_{i,j}(t)\right\\}_{i\in\mathcal{A}_{j}(t)},\left\\{\vartheta_{i,j}\right\\}_{i\in\mathcal{A}_{j}(t)}\bigg{\\}}.\end{split}$
(9)

Here, $R_{a_{j}(t-1),j}$ represents the achievable rate when UE $j$ is
associated with the BS indexed by $a_{j}(t-1)$. Note that the size of
$\boldsymbol{\mathrm{o}}_{j}^{\textsc{L}}(t)$ does not depend on the number of
UEs, in sharp contrast with [8]. Then, we obtain the $n$-dimensional local
encoding vector
$\boldsymbol{\mathrm{u}}_{j}(t)=f(\boldsymbol{\mathrm{o}}_{j}^{\textsc{L}}(t))$,
where $f:\mathbb{R}^{l}\rightarrow\mathbb{R}^{n}$ is a NN, and $l$ is the size
of the vector obtained after the concatenation of the elements in
$\boldsymbol{\mathrm{o}}_{j}^{\textsc{L}}(t)$.

Figure 2: UE association policy network architecture, shared across all UEs.

####  III-A2 UE global observation encoding

After taking an action $a_{j}(t)$, the controller can encode for UE $j$ some
meaningful global state (i.e. macro) information
$\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t)$ such as the estimated position
of UEs of interfering links, i.e., of active mmWave links, the load of each
BS, etc. However, embedding more information does not necessarily imply
performance improvement. Indeed, as the agent’s state space also increases,
more exploration is required to discover the intrinsic state/action relation
at the risk of misleading the agent. In our scenario, we consider that the
information about the actual rate perceived by each UE $j$ and the position of
the potential interferers, i.e., the set of UEs $\mathcal{N}_{j}(t)$,
susceptible to impact the association decision of UE $j$ through the
interference resulting from their communications. Here, we consider
$\mathcal{N}_{j}(t)$ as the $k$-nearest neighbors of UE $j$, whose size may
vary with time, however solutions based on local interaction graphs can be
considered [4]. Hence, we define $\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t)$
as:

$\displaystyle\begin{split}\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t){}={}&\bigg{\\{}\varsigma_{l}=\left[x_{l}(t),y_{l}(t),R_{a_{l}(t-1),l}\right],~{}~{}l\in\mathcal{N}_{j}(t)\bigg{\\}},\end{split}$
(10)

from which, we construct UE $j$ global state encoding
$\boldsymbol{\mathrm{v}}_{j}(t)$.

Fixed-size encoding. A naive solution to construct
$\boldsymbol{\mathrm{v}}_{j}(t)$ is to first concatenate all elements in
$\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t)$ resulting in a vector of size
$m(t)=3\times\mathrm{card}(\mathcal{N}_{j}(t))$. Then, we obtain the local
encoding vector
$\boldsymbol{\mathrm{v}}_{j}(t)=g(\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t))$,
where $g:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ is also a NN. However, such
an approach i) has limited scalability as the size of
$\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t)$, i.e., $m(t)$ varies with the
number of UEs, especially in the neighborhood, and ii) requires ordering
elements prior to concatenation, preventing from transferability.

Order-agnostic and size-variable encoding. An efficient solution to the
problem should be agnostic of the ordering in
$\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t)$. Moreover, in order to build a
scalable and transferable architecture, the size of
$\boldsymbol{\mathrm{v}}_{j}$ should be independent of the length of
$\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t)$, thus, the size of UE $j$
neighborhood. To satisfy these properties, we adopt ideas from the _dot-
product attention mechanisms_ in [14]. Hence, let
$\boldsymbol{\mathrm{k}}_{j}=g_{k}\left(\varsigma_{j}\right)$,
$\boldsymbol{\mathrm{q}}_{j}=g_{q}\left(\varsigma_{j}\right)$, and
$\boldsymbol{\mathrm{\nu}}_{j}=g_{\nu}\left(\varsigma_{j}\right)$, where
$g_{k},~{}g_{q},~{}g_{\nu}:\mathbb{R}^{3}\rightarrow\mathbb{R}^{n}$ are also
encoding functions (e.g., neural networks), and $\boldsymbol{\mathrm{k}}_{j}$,
$\boldsymbol{\mathrm{q}}_{j},$ $\boldsymbol{\mathrm{\nu}}_{j}$ denote the
_key_ , the _query_ and the _value_ associated with UE $j$, respectively. For
a given UE $j$, we compute for each UE in its neighborhood
$\mathcal{N}_{j}(t)$ a weight (or score) $\alpha_{k,j}$

$\alpha_{k,j}=\boldsymbol{\mathrm{softmax}}\left(\left[\frac{\boldsymbol{\mathrm{q}}_{k}\boldsymbol{\mathrm{k}}_{j}^{T}}{\sqrt{n}}\right]_{k\in\mathcal{N}_{j}(t)}\right).$
(11)

Here, $\boldsymbol{\mathrm{softmax}}(\cdot)$ is the softmax function also
known as the normalized exponential function. Let
$\boldsymbol{\mathrm{\alpha}}_{j}=\left[\alpha_{k,j},{k\in\mathcal{N}_{j}}\right]$.
The vector $\boldsymbol{\mathrm{\alpha}}_{j}$ represents the interaction of UE
$j$ with its neighbors. Then, we compute the encoding
$\boldsymbol{\mathrm{v}}_{j}$ by aggregating all values’ information from the
neighborhood as follows:

$\boldsymbol{\mathrm{v}}_{j}=\sum_{k\in\mathcal{N}_{j}(t)}\alpha_{k,j}\boldsymbol{\mathrm{\nu}}_{k}.$
(12)

By construction, the size of $\boldsymbol{\mathrm{v}}_{j}$ in (12) is
invariable with the size of $\mathcal{N}_{j}(t)$. Only its value can change
depending of the aggregated information. That is to say, whenever the number
of UEs varies, there is no need to change the PNA.

####  III-A3 Local and global information combining

Now, once we obtain the UE local and global encoding vector, they are merged
together to build its context understanding vector
$\boldsymbol{\mathrm{c}}_{j}(t)=h\left(\boldsymbol{\mathrm{z}}_{j}(t)\right)$,
i.e., its perception of the radio environment, where
$\boldsymbol{\mathrm{z}}_{j}(t)=\boldsymbol{\mathrm{u}}_{j}(t)\oplus\boldsymbol{\mathrm{v}}_{j}(t)$,
with $\oplus$ denoting concatenation operation and
$h:\mathbb{R}^{2n}\rightarrow\mathbb{R}^{n}$ is also taken here, as a NN.

Now, given the context vector $\boldsymbol{\mathrm{c}}_{j}(t)$, the goal of
the learning agent $j$ at each instant $t$, is to define an association
probability vector
$\boldsymbol{\mathrm{p}}_{j}(t)=[p_{0,j},\ldots,p_{N_{s},j}]\in[0,1]^{N_{s}+1}$
with $\sum_{i\in\mathcal{A}}p_{i,j}=1$ and $p_{i,j}=0$ for all
$i\not\in\mathcal{A}_{j}(t)$. Then, the UE’s action $a_{j}(t)$, which
corresponds to a connection request towards the BS indexed by $a_{j}(t)$ in
$\mathcal{A}_{j}(t)$, is sampled from the distribution characterized by the
$p_{i,j}$. Thus, the learning problem consists in deriving an association
policy that optimizes $\boldsymbol{\mathrm{p}}_{j}(t)$, such that sampling
from it maximizes (3).

Note that in this architecture, UEs’ agents share the same model, i.e.,
$f(\cdot)$, $g(\cdot)$, and $h(\cdot)$ are common to all UEs. This setting
does not preclude UEs from taking different actions as they do not observe the
same inputs. In contrast, sharing the parameters among UEs enables a better
skill transfer since there is only a unique policy (in contrast to having one
policy per UE as in [8]), which can be efficiently and simultaneously trained
with the experiences of all UEs in a MARL framework using proximal policy
optimization (PPO) [15].

###  III-B Proximal policy optimization

In a MARL system, agents learn by interacting with a shared environment by
making decisions following a Markov Decision Process (MDP). In MDP, the action
$a_{j}(t)$ of an agent $j$ in a given state $\boldsymbol{\mathrm{s}}_{j}(t)$
leads it to the next state $\boldsymbol{\mathrm{s}}_{j}(t+1)$ and results in a
reward $r_{j}(t)$. From the underlying _experience_
$e_{j}(t)=\\{\boldsymbol{\mathrm{s}}_{j}(t),a_{j}(t),r_{j}(t),\boldsymbol{\mathrm{s}}_{j}(t+1)\\}$,
the agent learns its policy $\pi_{j,\boldsymbol{\mathrm{w}}}(\cdot|\cdot)$,
parameterized by $\boldsymbol{\mathrm{w}}$, the set of PNA parameters, where
$\pi_{j,\boldsymbol{\mathrm{w}}}(a_{j}|\boldsymbol{\mathrm{s}}_{j})=p_{a_{j}(t),j}$
is the probability that agent $j$ takes action (or requests connection)
$a_{j}$ in state $\boldsymbol{\mathrm{s}}_{j}$, to maximize an accumulated
long-term $\gamma$-discounted reward
$G_{j}(t)=\sum_{\tau=t+1}^{T_{e}}\gamma^{\tau-t-1}r_{j}(\tau)$ over an episode
\- a new network deployment - of duration $T_{e}$:
$\pi_{j,\boldsymbol{\mathrm{w}}}^{*}=\underset{\pi_{j}}{\mathrm{argmax}}~{}\mathbb{E}_{t}\left[G_{j}(t)\right]$.
In our study, we consider the particular case of _cooperative_ MARL [16],
i.e., UEs share the same reward, hence, they are assigned to the same
objective of maximizing the network utility function:
$r_{j}(t)=R(t),~{}\forall j$. Moreover, UEs also share the same policy
parameters, i.e.,
$\pi_{j,\boldsymbol{\mathrm{w}}}=\pi_{\boldsymbol{\mathrm{w}}},~{}\forall j$.

In general MARL, an agent has only access to a partial observation
$\boldsymbol{\mathrm{o}}_{j}(t)=\left\\{\boldsymbol{\mathrm{o}}_{j}^{\textsc{L}}(t),\boldsymbol{\mathrm{o}}_{j}^{\textsc{G}}(t)\right\\}$
of the actual state $\boldsymbol{\mathrm{s}}_{j}(t)$, which is unknown,
resulting in partially observable MDP [17]. Moreover, MARL is subject to non-
stationarities due to simultaneous interactions of agents with the
environment, which make the learning process more complex. In the literature,
policy gradient algorithms are used to solve this problem [18]. We use an
actor-critic mechanism to iteratively update the policy parameters
$\boldsymbol{\mathrm{w}}$ to minimize the $\epsilon$-clipped proximal loss:

$\mathcal{L}(\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}}){}={}\mathbb{E}_{\pi}\left[\mathrm{min}\left(\zeta(\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}})\hat{A},\boldsymbol{\mathrm{clip}}\left(\zeta(\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}}),1-\epsilon_{1},1+\epsilon_{2}\right)\hat{A}\right)\right],$
(13)

where
$\boldsymbol{\mathrm{clip}}(x,a,b)=\mathrm{min}\left(\mathrm{max}\left(x,a\right),b\right)$,
$\hat{A}(a_{j},\boldsymbol{\mathrm{o}}_{j})$ denotes the advantage estimator,
which measures the advantage of selecting a given action in a given state,
that we estimate using one step Temporal Difference error [18].
$\zeta(\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}})=\frac{\pi_{\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}}}(a_{j}|\boldsymbol{\mathrm{o}}_{j})}{\pi_{\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}}_{\rm
old}}(a_{j}|\boldsymbol{\mathrm{o}}_{j})}$ is the probability ratio between
current and previous update. By introducing the clipping effect, PPO
pessimistically ignores updates (possibly destructive) that will lead to high
changes between policy updates.
Hysteretic PPO. Note that in vanilla PPO, $\epsilon_{1}=\epsilon_{2}$.
However, in multi-agent environments, an agent should not be pessimistic in
the same way for both positive
($\zeta(\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}})>1$) and negative
($\zeta(\boldsymbol{\mathrm{\boldsymbol{\mathrm{w}}}})<1$) updates. In fact,
due to the interaction of multiple agents with the environment and the common
reward of the cooperative framework, an agent may receive a lower reward
because of the bad behavior of its teammates. This may cause the user to
change its policy at the risk to misleading it. To overcome this issue,
following the concept of hysteretic Q-learning in [19], we introduce
hysteretic proximal policy optimization, where we use $\epsilon_{1}$ and
$\epsilon_{2}$ for negative and positive updates, with
$\epsilon_{1}<\epsilon_{2}$. In this way, an agent gives more importance to
updates that improve its policy rather than to ones that worsen it. This
setting is particularly important when agents do not have equal contribution
to the team’s reward and for decentralized learning.

Note that the association policy can be efficiently trained in a centralized
way with the experience of all agents or in a decentralized way, by leveraging
approaches presented in [20].

To further make learning robust against the variability of the number of UEs
over time, we introduce a UE dropout mechanism with rate $p_{0}$,
corresponding to the Bernoulli probability of a UE to be masked out in a given
training episode, thus, appearing as non-existent in the cell for the others
UEs.

On complexity. In contrast to previous work where each UE learns its own
specific policy without transferability [10], here we have only one global
policy that can be transferred to any UE in the network even new ones, thus
considerably reducing the computation complexity. Also by using attention
mechanism instead of Long Short Term Memories (LSTMs), we considerably reduce
the PNA architecture. The counterpart is the aggregation of information in
(12). However, this process can be viewed as a message passing between UEs,
where they only need to exchange their queries and values with BSs and only
when there is a considerable change in the network (e.g. arrival of new UEs)
to limit signaling.

##  IV Numerical Results

TABLE I: Simulations parameters [10]

| Macro cell | Small cell
---|---|---
Parameters | Values
Carrier frequency $f_{s}$ | 2.0 GHz | 28 GHz
Path loss constant $C_{s}$ |  $\left(c/{4\pi f_{s}}\right)^{2}$, $c=3\times 10^{8}\mathrm{ms}^{-1}$
Bandwidth | 10 MHz | 200 MHz
Thermal noise, $N_{0}$ | -174 dBm/Hz
Noise figure | 5 dB | 0 dB
Shadowing variance | 9 dB | 12 dB
TX power, $P^{\mathrm{Tx}}$ | 46 dBm | 20 dBm
Antenna gain, $G_{\mathrm{max}}^{\mathrm{Tx}}$ / $G_{\mathrm{max}}^{\mathrm{Rx}}$ | 17 dBi / 0 dBi | [10, diag. 2]
Radius, $R_{0}$ |  | 50 m
Back-lobe gain |  | -20 dB
Path-loss exponent, $\eta_{s}$ | 3.76 | 2.5
Inter-cell distance |  | $1.2\times R_{0}$
AoA error $\sim\mathcal{N}(0,\sigma_{\rm AoA}^{2})$ | $2\degree$

In our simulations, we consider $K_{0}=15$ UEs randomly located in a bi-
dimensional region, under the coverage of $N_{s}=3$ SBSs working at mmWave
frequencies with a carrier frequency of 28 GHz, and one MBS communicating at 2
GHz, however, our solution can be leveraged for applications using different
technologies such as WiFi or LiFi.. Also, we consider three types of service
corresponding to an average data rate demand
$\overline{D}_{j}\in\\{5,200,1500\\}$ Mbps. We assume that the traffic request
of a UE $j$ is a random variable, which follows a Poisson distribution with
intensity $\overline{D}_{j}=\mathbb{E}\left[D_{j}(t)\right]$. Additional
simulation parameters can be founded in Table I.
Learning parameters. Since all UEs share the same policy network,
$\mathcal{A}$ coincides with the action space. However, a UE $j$ can only be
associated with BSs in $\mathcal{A}_{j}(t)\subseteq\mathcal{A}$. Accordingly,
unauthorized actions or connection requests
$a_{j}(t)\not\in\mathcal{A}_{j}(t)$ are redirected towards the MBS, i.e., they
appear as connection requests to the MBS. We fixed the size of the encoding
functions $n=128$. All encoding functions are composed of only one hidden
multi-layer perceptron (MLP) of $n$ neurons. Both actor and critic comprise
also one MLP with $2n$ neurons. All layers use a rectifier linear unit
activation. We set the learning rate $\mu$ to $10^{-4}$ and the discounting
factor $\gamma=0.6$. Unless specified, we empirically fix the clipping factors
to $\epsilon_{1}=0.01$, $\epsilon_{2}=0.5$, the time horizon to $T_{e}=250$
and the UE dropout probability to $p_{0}=0.95$. Also, we limit UE $j$’s
neighborhood $\mathcal{N}_{j}$ to its $k$-nearest neighbors, where $k\leq 15$.
Benchmarks. As a comparison, we consider the same benchmarks as in [10], i.e.,
the Max-SNR algorithm, which associates UEs on the basis of links with the
maximum SNR, and the centralized heuristic algorithm, which consists in
associating UEs, starting from the links with the maximum SNR, and in an
iterative way as long as it increases the network utility. Originally proposed
in [6], the centralized heuristic algorithm is shown to exhibit good
performance, specifically in interference-limited network. Therefore, we use
it as a baseline solution in lieu of the optimal solution, infeasible here,
due to the network size. However, we recompute the heuristic algorithm every
time the network changes, which is also cumbersome. To assess the convergence
performance of the proposed algorithm, we define
${r_{d}(t)=\overline{R}^{\mathrm{Trans.~{}RL}}(t)-\overline{R}^{\mathrm{Heur.}}(t)}$,
which corresponds to the difference of the average reward over an episode
reached by the proposed algorithm compared to the centralized heuristic
approach. Also, we represent on the histograms, the average performance over
500 random deployments of UEs.

###  IV-A Impact of the hysteretic clipping factors on convergence

Figure 3: Effect of the hysteretic clipping factors on the convergence.
$\alpha=0$ and $D_{j}(t)=\infty,~{}\forall j$. Averaged on a 100-sized rolling
window.

Here, we evaluate the impact of clipping factors $\epsilon_{1}$ and
$\epsilon_{2}$ on the convergence. Fig. 3 shows the evolution of $r_{d}(t)$ in
two settings: $\epsilon_{1}=\epsilon_{2}=0.2$, corresponding to the setting of
the vanilla PPO proposed in [15], and our empirically optimized hysteretic
setting $\epsilon_{1}=0.01,~{}\epsilon_{2}=0.5$. We show that by simply
introducing a hysteretic effect in the clipping factors, we notably improve
the stability and the learning performance, reaching the same performance as
the heuristic algorithm (as $r_{d}(t)$ converges on average to zero).

###  IV-B Policy Transferability Property: Zero shot generalization

Figure 4: Transferability for case $\alpha=0$ and with network traffic. The
PNA is initially trained for 15 UEs. Figure 5: Generalizability for case
$\alpha=1$ (no traffic). Here we fix $K=15$ and vary the number of beams
$N_{i}$.

To assess how transferable the proposed algorithm is, we train the PNA for a
reference number of users, $K_{0}=15$ and $N_{i}=3,~{}\forall i$. Then we
evaluate on Fig. 4 and 5, the performance of the trained model for different
network deployments with a variable number of UEs $K\in\\{10,20,25,30\\}$,
including changes in the UEs’ position and traffic dynamic. In Fig. 4, we
observe that when we consider the network traffic, the proposed transferable
solution clearly outperforms the two benchmarks. Even when the number of UEs
doubles from $K_{0}=15$ to $K=30$, Our solution yields $102.1\%$, $66.66\%$
network sum-rate increase w.r.t. the max-SNR and heuristic algorithms,
respectively. Moreover, an additional feature of the proposed architecture, is
that even when the number of beams available per BS later changes (w.r.t.
initial training point, fixed to $N_{i}=3$), which impacts the collision
events, the algorithm still adapts to maintain the system’s performance.
Indeed, in Fig. 5 where we evaluate the performance of the algorithms for
different $N_{i}\in\\{2,3,4,5,10,15\\}$, we can observe that as $N_{i}$
increases, implying less and less collisions since $K$ is fixed, the algorithm
keeps outperforming the two benchmarks. When $N_{i}$ becomes greater than $5$,
i.e., $\sum_{i=1}^{3}N_{i}>K=15$, there is no improvement in the sum-rate as
there are enough beams to serve all UEs.

##  V Conclusions and Perspectives

In this work, we investigated the problem of transferability of user
association policies for 5G and beyond networks. We come out with a novel
policy architecture and a learning mechanism that enable users to
cooperatively learn a robust and transferable user association policy. Our
proposed solution exploits neural attention and deep multi-agent reinforcement
learning mechanisms, where agents leverage local and, if available, global
observations to optimize network utility functions. We achieve
transferability. Indeed, with our solution, a policy learned in a given
scenario can be transferred with zero-shot generalization capability, i.e.
without any additional training. Our numerical results showed that the
proposed transferable solution provides large gains, indeed doubling the
network sum-rate compared to state-of-the-art approaches. The observed benefit
is due to the transferability feature, and by jointly considering network
traffic and radio channels dynamic during optimization.

In future work, results of this study will be exploited for applications in
Multi-access Edge Computing.

## References

  * [1] E. Calvanese Strinati et al., “6G: The Next Frontier: From Holographic Messaging to Artificial Intelligence Using Subterahertz and Visible Light Communication,” IEEE Vehicular Technology Magazine, vol. 14, pp. 42–50, Sep. 2019.
  * [2] A. De Domenico et al., “Making 5G Millimeter-Wave Communications a Reality [Industry Perspectives],” IEEE Wireless Communications, vol. 24, pp. 4–9, Aug 2017.
  * [3] G. Athanasiou, P. C. Weeraddana, C. Fischione, and L. Tassiulas, “Optimizing Client Association for Load Balancing and Fairness in Millimeter-Wave Wireless Networks,” IEEE/ACM Transactions on Networking, vol. 23, pp. 836–850, June 2015.
  * [4] Y. Liu, X. Fang, M. Xiao, and S. Mumtaz, “Decentralized Beam Pair Selection in Multi-Beam Millimeter-Wave Networks,” IEEE Transactions on Communications, vol. 66, pp. 2722–2737, June 2018.
  * [5] A. Alizadeh and M. Vu, “Early acceptance matching game for user association in 5g cellular hetnets,” in IEEE GLOBECOM, pp. 1–6, 2019.
  * [6] P. Zhou et al., “Deep Learning-Based Beam Management and Interference Coordination in Dense mmWave Networks,” IEEE Transactions on Vehicular Technology, vol. 68, pp. 592–603, Jan 2019.
  * [7] R. Liu, M. Lee, G. Yu, and G. Y. Li, “User association for millimeter-wave networks: A machine learning approach,” IEEE Transactions on Communications, vol. 68, no. 7, pp. 4162–4174, 2020.
  * [8] N. Zhao, Y. Liang, D. Niyato, Y. Pei, and Y. Jiang, “Deep Reinforcement Learning for User Association and Resource Allocation in Heterogeneous Networks,” in Proc. IEEE GLOBECOM, pp. 1–6, Dec 2018.
  * [9] M. Sana, A. De Domenico, and E. Calvanese Strinati, “Multi-Agent Deep Reinforcement Learning based User Association for Dense mmWave Networks,” in Proc. IEEE Global Communications Conference (GLOBECOM), pp. 1–6, HI, USA, Dec 2019.
  * [10] M. Sana, A. De Domenico, W. Yu, Y. Lostanlen, and E. Calvanese Strinati, “Multi-Agent Reinforcement Learning for Adaptive User Association in Dynamic mmWave Networks,” IEEE Transactions on Wireless Communications, vol. 19, no. 10, pp. 6520–6534, 2020.
  * [11] T. Bai and R. W. Heath, “Coverage and Rate Analysis for Millimeter-Wave Cellular Networks,” IEEE Transactions on Wireless Communications, vol. 14, no. 2, pp. 1100–1114, 2015.
  * [12] R. Srikant and L. Ying, Communication Networks: An Optimization, Control and Stochastic Networks Perspective.  USA: Cambridge University Press, 2014.
  * [13] D. Liu et al., “User Association in 5G Networks: A Survey and an Outlook,” IEEE Communications Surveys Tutorials, vol. 18, no. 2, pp. 1018–1044, 2016.
  * [14] A. Vaswani et al., “Attention is all you need,” in Advances in neural information processing systems, pp. 5998–6008, 2017.
  * [15] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms.,” in Proc. CoRR, 2017.
  * [16] L. Buşoniu, R. Babuška, and B. De Schutter, “Multi-agent Reinforcement Learning: An Overview,” in Innovations in multi-agent systems and applications-1, pp. 183–221, Springer, 2010.
  * [17] S. Omidshafiei, J. Pazis, C. Amato, J. P. How, and J. Vian, “Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability,” in Proc. International Conference on Machine Learning (ICML), vol. 70, pp. 2681–2690, PMLR, 06–11 Aug 2017.
  * [18] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction.  The MIT Press, second ed., 2018.
  * [19] L. Matignon, G. J. Laurent, and N. Le Fort-Piat, “Hysteretic Q-Learning: An Algorithm for Decentralized Reinforcement Learning in Cooperative Multi-agent Teams,” in Proc. International Conference on Intelligent Robots and Systems (IEEE/RSJ), pp. 64–69, 2007.
  * [20] E. Wijmans et al., “DD-PPO: Learning Near-Perfect PointGoal Navigators from 2.5 Billion Frames,” in Proc. ICLR, 2020.


# Bishop Independence on the Surface of a Square Prism

Liam H. Harris Stephanie Perkins Paul A. Roach

Department of Computing and Mathematics
University of South Wales
Pontypridd, UK.
{liam.harris, stephanie.perkins<EMAIL_ADDRESS>
(June 2020)

###### Abstract

Bishop Independence concerns determining the maximum number of bishops that
can be placed on a board such that no bishop can attack any other bishop. This
paper presents the solution to the bishop independence problem, determining
the bishop independence number, for all sizes of boards on the surface of a
square prism.

Mathematics Subject Classification: 05C69, 00A08

##  1 Introduction

In Chess, the independence problem for a given board asks for a maximal
placement of a given chess piece such that no piece in the placement can move
to the position of another in a single chess move. The independence number is
the cardinality of such a placement. The relation of this problem to graph
problems is of special interest to combinatorialists. For the graph $G$ with
set of vertices $V$, the set $S\subset V$ is independent if no two vertices in
$S$ are adjacent in $G$. The independence number $\beta_{0}(G)$ is the maximum
cardinality of an independent set of the graph $G$. This directly relates to
the problem of finding the independence number of a specified chess piece on a
given board.

Results for the independence number for the bishop piece on a variety of board
structures are known. Yaglom and Yaglom (1964) determine the independence
number of bishops for the case of $n\times n$ square boards and Berghammer
(2011) presents a proof for the independence number for bishops on the
$n\times m$ rectangular board. Demaio and Faust (2009) consider the
independence problem for bishops on the $n\times m$ torus; this paper also
addresses the related domination problem which asks, for a given board, for a
minimum placement of a given chess piece such that every square of the board
is either occupied or can be reached in a single move by a piece in the
placement. This later problem and variants have received recent interest, for
example Sowndarya and Yendamuri (2018) have addressed perfect domination for
bishops, kings and rooks on the $n\times n$ square board. Succinctly expressed
summaries of some of these results and of other similar results, for a variety
of pieces and boards, are given by Watkins (2018).

The aforementioned work only addresses board topologies created from a single
$n\times m$ board, however research has also been conducted for the surface of
an $n\times m\times l$ cuboid. This includes recent work by Omran (2017) on
the domination and independence of rooks and kings on the surface of the
$n\times n\times n$ cube. The current authors (Harris et al. (2013)) have
previously presented results for the bishop independence number on the surface
of the $n\times n\times n$ cube. This paper extends that work to provide the
bishop independence number for the $n\times n\times m$ square prism; without
loss of generality it will be assumed that $n\leq m$. We define
B${}^{3}_{n,n,m}$ to be the graph which represents permissible bishop moves on
the surface of an $n\times n\times m$ square prism.

The surface of a $n\times n\times m$ square prism can be considered as a net
consisting of two $n\times n$ faces and four $n\times m$ faces, with the 24
edges paired and identified in a specific way such that the surface of a
square prism is formed. The bishop piece moves on this board in the same
manner it does on the traditional $8\times 8$ square board moving along either
of the diagonals that intersect at its current position. A bishop is said to
cover a square if it can reach that square in a single move.

######  Definition 1.1.

A diagonal is a set of consecutive squares that are diagonally adjacent.

Using Definition 1.1 it is possible to define different types of diagonals,
and the properties of a given diagonal, which is of use in exploring the
independence problem for the bishop piece.

######  Definition 1.2.

A maximal diagonal is a set of all consecutive squares that are diagonally
adjacent. All maximal diagonals are distinct.

Since a bishop can move to any square on a diagonal on which it is currently
placed it is impossible for two bishops to be placed on the same diagonal and
be independent. Determining the number of distinct maximal diagonals of a
board can provide a useful bound to the bishop independence number of that
board. To do this it will be important to distinguish between diagonals that
do cross identities and diagonals that do not.

######  Definition 1.3.

A bounded diagonal is a set of all consecutive squares that are diagonally
adjacent without considering identities.

When imposing the grid structure of the chessboard onto the surface of a
square prism non-regularity occurs only for the 24 squares at the corners of
each face. These squares have only 7 surrounding squares as opposed to the 8
neighbours possessed by the remaining squares. Thus a bishop on a corner
square can only move in one of three directions rather than four. Hence, there
is a need to distinguish between maximal diagonals that begin at a corner and
those that do not.

######  Definition 1.4.

A maximal diagonal is closed if the squares can be ordered such that they
cycle. A maximal diagonal is open if it is not closed.

The cuboid is an interesting object of study for Bishop movement because its
closed maximal diagonals can be separated into four sets and each of its open
maximal diagonals contains only squares from a single face. Determining the
number of maximal diagonals and hence the independence number for bishops on a
$n\times n\times m$ square prism is more complicated since the open maximal
diagonals may contain squares from multiple faces and the closed maximal
diagonals cannot be separated into as small a number of sets as is the case
for the cube.

######  Lemma 1.5.

$\beta_{0}(B^{3}_{n,n,m})=\beta_{0}(B^{3}_{n,n,m+4n})$.

###### Proof.

For a $4n\times 4n$ square board with top and bottom sides identified, each
maximal diagonal contains a square from the first and last column. For each
maximal diagonal the start and end point is the same, vertically. Hence
inserting such a board into the net of an $n\times n\times m$ cuboid between
two columns of the $n\times m$ faces, would extend the board to a $n\times
n\times(m+4n)$ cuboid such that the maximal diagonals contain the same squares
as they did in the original board. Hence the independence number of the board
is not changed. ∎

######  Lemma 1.6.

All closed diagonals of an $n\times n\times m$ cuboid pass both square
$n\times n$ faces of the cuboid at least once.

###### Proof.

Each vertical identity defined by the representation in Figures 1 to 6,
labeled $1$, $2$, $3$, $4$, $5$ and $6$, of the $n\times m$ faces, identifies
with an edge of a $n\times n$ face. Since movement in this representation is
in one direction across the $n\times m$ faces, in order to close, a diagonal
must pass one of these identities and thus pass a $n\times n$ face. Any
diagonal crossing a $n\times n$ face returns to the $n\times m$ faces in the
opposite orientation, and the argument applies again at least once and to the
other $n\times n$ face in order for the diagonal to return to its original
position in the correct orientation. ∎

##  2 Bound

######  Lemma 2.1.

For B${}^{3}_{n,n,kn+r}$ with $k,r\in\mathbb{Z}$ and $0\leq r<n$:

$\beta_{0}(B^{3}_{n,n,kn+r})\leq\begin{cases}2n+4&\text{for k odd and
$r=0$,}\\\ 2n+3-r&\text{for k odd and $0<r<n$,}\\\ n+5&\text{for k even and
$r=0$,}\\\ n+3+r&\text{for k even and $0<r<n$.}\end{cases}$

###### Proof.

The only boundaries to bishop movement on the surface of a cuboid are the
corners of each face. Each face has 4 corners; there are 6 faces and for these
24 corners there are 12 distinct open diagonals. These are the 4 major
diagonals, bounded diagonals containing the most squares, of the $n\times n$
faces and the 8 diagonals that connect the corners of the $n\times kn+r$
faces. For $r=0$, $kn+r$ is a multiple of $n$ and hence these 8 open diagonals
will not pass the $n\times n$ faces. For $0<r<n$, $kn+r$ is not a multiple of
$n$ and hence each of these 8 open diagonals will pass one of the $n\times n$
faces, altering the number of maximal diagonals on the cuboid compared to that
of $r=0$.

For $0<r<n$, each $n\times n$ face is visited, exactly once, by each of four
open diagonals that commence from $n\times kn+r$ faces. Selecting the leftmost
$n\times n$ face, there are $n$ positive bounded diagonals incident to
identity $5$ the lowest of which is in the open diagonal that is contained on
this face alone. The $r^{th}$ diagonal above this is in a open diagonal which
passes this square face. The remaining $n-2$ diagonals can be split into two
sets, the $n-1-r$ diagonals above, and the $r-1$ diagonals below that open
diagonal which passes this $n\times n$ face (see Figures 1 to 6). Taking
movement across identity $7$ as granted, if necessary, the properties of all
remaining diagonals of the board will be the same as for those of these two
sets of diagonals. For $r=0$ the second set does not exist and the first set
contains $n-1$ diagonals since there is no open diagonal that commences from a
$n\times kn+r$ face which also crosses a $n\times n$ face. Hereafter it is
taken that for $r=0$ there is no second set. By Lemma 1.5 only the cases of
$k=1,~{}2,~{}3$ and $~{}4$ need to be considered, since the addition of $4n$
to $m$ does not alter the independence number.

For $k=1$, the first diagonal set, containing $n-1-r$ diagonals for $0<r<n$
and $n-1$ diagonals for $r=0$, consists of diagonals that are closed, pass
each $n\times n$ face once, and have the following path of movement:
identities 1, 4 then 5. For $0<r<n$ the second diagonal set, containing $r-1$
diagonals, consists of diagonals that are closed, pass each $n\times n$ face
twice, and have the following path of movement: identities 1, 4, 6, 3, 2 then
5. For $k=3$, the first diagonal set contains diagonals that are closed, pass
each $n\times n$ face once, and have the following path of movement:
identities 1, 6, 2 then 5. For $0<r<n$ the second diagonal set contains
diagonals that are closed, pass each $n\times n$ face twice, and have the
following path of movement: identities 1, 2, 3, 4, 6 then 5. In both of these
cases, by symmetry there exist four sets of $n-1-r$ diagonals for $0<r<n$ (and
four sets of $n-1$ diagonals for $r=0$) that traverse each square face once
and for $0<r<n$ two sets of $r-1$ diagonals traversing each $n\times n$ face
twice. This results in a total of $4(n-1-r)+2(r-1)+12=4n-2r+6$ maximal
diagonals on the $n\times n\times kn+r$ cuboid for $k$ odd and $0<r<n$ (and a
total of $4(n-1)+12=4n+8$ maximal diagonals on the $n\times n\times kn$ cuboid
for $k$ odd).

For $k=2$, the first diagonal set, containing $n-1-r$ diagonals for $0<r<n$
and $n-1$ diagonals for $r=0$, consists of diagonals that are closed, pass
each $n\times n$ face once, and have the following path of movement:
identities 1, 4, 6, 3, 2 then 5. For $0<r<n$ the second diagonal set,
containing $r-1$ diagonals, consists of diagonals that are closed, pass each
$n\times n$ face twice, and have the following path of movement: identities 1,
6, 2 then 5. For $k=4$, the first diagonal set contains diagonals that are
closed, pass each $n\times n$ face once, and have the following path of
movement: identities 1, 2, 3, 4, 6 then 5. For $0<r<n$ the second diagonal set
contains diagonals that are closed, pass each $n\times n$ face twice, and have
the following path of movement: identities 1, 4 then 5. In both of these
cases, by symmetry there exist two sets of $n-1-r$ diagonals for $0<r<n$ (and
two sets of $n-1$ diagonals for $r=0$) that traverse each $n\times n$ face
twice and for $0<r<n$ four sets of $r-1$ diagonals traversing each square face
once. This results in a total of $2(n-1-r)+4(r-1)+12=2n+2r+6$ maximal
diagonals on the $n\times n\times kn+r$ cuboid for $k$ even and $r>0$ (and a
total of $2(n-1)+12=2n+10$ maximal diagonals on the $n\times n\times kn$
cuboid for $k$ even).

Since none of these maximal diagonals cross themselves a bishop will always
cover 2 diagonals and hence the maximum number of bishops that can be placed
independently on the surface of an $n\times n\times kn+r$ cuboid is $2n-r+3$
bishops for $k$ odd and $0<r<n$, $2n+4$ bishops for $k$ odd and $r=0$, $n+r+3$
bishops for $k$ even, and $0<r<n$ and $n+5$ bishops for $k$ even and $r=0$.

∎

##  3 Constructions

There now follow constructions for placing a given number of bishops on an
$n\times n\times m$ square prism chessboard, where $m=kn+r$ and $0\leq r<n$.

######  Construction 3.1.

For $k$ odd, $n$ and $m$ even, $2n-r$ bishops are to be placed. Choosing
either $n\times n$ face, from the center of either of its middle rows, for
$r=0$ place $n$ bishops to the right and for $0<r<n$ place $r$ bishops in the
cells to the right and a further $n-r$ to the right of these, extending onto
the adjacent face if required. For the cells to the left of the center of the
row place the remaining $n-r$ bishops while leaving the first $r$ cells empty,
extending onto the adjacent face if required.

An example of Construction 3.1 is given in Figure 1.

######  Construction 3.2.

For $k$ even, $n$ and $m$ even, $n+r$ bishops are to be placed. Choosing
either $n\times n$ face, from the center of either of its middle rows, for
$r=0$ place $n$ bishops to the right and for $0<r<n$ place $r$ bishops in the
cells to the right and a further $n-r$ to the right of these, extending onto
the adjacent face if required. For $0<r<n$ place the remaining $r$ bishops in
the cells to the left of the center of the row.

An example of Construction 3.2 is given in Figure 2.

######  Construction 3.3.

For $k$ odd, $n$ even and $m$ odd, $2n+3-r$ bishops are to be placed, where
$r$ is odd. Choosing any $n\times m$ face, beginning from the center of its
$\frac{n+r+1}{2}^{th}$ column, place $\frac{2n+3-r}{2}-2$ bishops in the cells
above, extending onto the adjacent rectangular face if required. Repeat this
for the cells below the center of the column to place a further
$\frac{2n+3-r}{2}-2$ bishops. In each of the $n\times n$ faces adjacent to the
chosen rectangular face, the open diagonals intersect in four cells, arranged
in two columns and two rows. In each such face, place two bishops in those
cells in the column closest to the chosen $n\times m$ face.

An example of Construction 3.3 is given in Figure 3.

######  Construction 3.4.

For $k$ even, $n$ even and $m$ odd, $n+3+r$ bishops are to be placed, where
$r$ is odd. Choosing any $n\times m$ face, beginning from the center of its
$\frac{2n+r+1}{2}^{th}$ column, place $\frac{n+3+r}{2}-r-1$ bishops in the
cells above, extending onto the adjacent rectangular face if required. Repeat
this for the cells below the center of the column to place a further
$\frac{n+3+r}{2}-r-1$ bishops. In each of the $n\times n$ faces adjacent to
the chosen $n\times m$ face, the open diagonals intersect in four cells,
arranged in two columns and two rows. In each such face, place two bishops in
those cells in the column closest to the chosen $n\times m$ face. Then in one
of the $n\times n$ faces, a further $2r-2$ bishops are to be placed, $r-1$ of
which will be placed between the bishops already placed; the remaining $r-1$
bishops are placed in the same rows as the latter $r-1$ bishops but in the
other column in which the open diagonals intersect.

An example of Construction 3.4 is given in Figure 4.

######  Construction 3.5.

For $k$ odd, $n$ odd, $2n+3-r$ bishops are to be placed for $0<r<n$ and $2n+4$
bishops are to be placed for $r=0$. Choose an $n\times m$ face and denote its
middle row as the pivotal row; for $0<r<n$ place $r-1$ bishops in this
$n\times m$ face symmetrically around the center of the pivotal row. In one of
the $n\times n$ faces, a bishop is placed in the center cell; two further
bishops are placed in the middle row, coinciding with the pivotal row, in the
cells at which the open diagonals intersect, extending into the adjacent
rectangular faces if necessary. For this pair of placements, $n-r-1$ bishops
for $0<r<n$ and $n-1$ bishops for $r=0$ are placed in the cells left of the
left most placed bishop. Similarly $n-r-1$ bishops for $0<r<n$ and $n-1$
bishops for $r=0$ are placed to the right of the right most placed bishop. For
the second $n\times n$ face, a bishop is placed in the center cell; two
further bishops are placed in the middle column, perpendicular to the pivotal
row, in the cells at which the open diagonals intersect, extending into the
adjacent rectangular faces if necessary.

An example of Construction 3.5 is given in Figure 5.

######  Construction 3.6.

For $k$ even, $n$ odd, $n+3+r$ bishops are to be placed for $0<r<n$ and $n+5$
bishops are to be placed for $r=0$. Choose an $n\times m$ face and denote its
middle row as the pivotal row; $n-r-1$ bishops for $0<r<n$ and $n-1$ bishops
for $r=0$ are placed in this $n\times m$ face symmetrically around the center
of the pivotal row. In each of the $n\times n$ faces, a bishop is placed in
the center cell; two further bishops are placed in the middle row, coinciding
with the pivotal row, in the cells at which the open diagonals intersect,
extending into the adjacent rectangular faces if necessary. For $0<r<n$, for
one such pair of placements at the intersection of the open diagonals a bishop
is placed in each empty cell between them, accounting for the remaining $2r-2$
bishops.

An example of Construction 3.6 is given in Figure 6.

##  4 Result

######  Theorem 4.1.

For B${}^{3}_{n,n,kn+r}$ with $k,r\in\mathbb{Z}$ and $0\leq r<n$:

$\beta_{0}(B^{3}_{n,n,kn+r})=\begin{cases}2n+4&\text{for $k$ odd, $n$ odd and
$r=0$,}\\\ 2n+3-r&\text{for $k$ odd and $n$ odd and $r>0$ or for $k$ odd and
$r$ odd,}\\\ 2n-r&\text{for $k$ odd and $n$ and $r$ even,}\\\ n+5&\text{for
$k$ even, $n$ odd and $r=0$,}\\\ n+3+r&\text{for $k$ even, $n$ odd and $r>0$
or for $k$ even and $r$ odd,}\\\ n+r&\text{for $k$ even and $n$ and $r$
even.}\end{cases}$

###### Proof.

For $n$ odd, the bound given in Lemma 2.1 can be met. For $k$ even,
Construction 3.6 provides an independent placement of $n+3+r$ bishops for
$0<r<n$ and $n+5$ bishops for $r=0$. For $k$ odd, Construction 3.5 provides an
independent placement of $2n+3-r$ bishops for $0<r<n$ and $2n+4$ bishops for
$r=0$.

For $n$ even and $nk+r$ odd, then $r\neq 0$ and the bound given in Lemma 2.1
can be met. For $k$ and $r$ odd, Construction 3.3 provides an independent
placement of $2n+3-r$ bishops. For $k$ even and $r$ odd, Construction 3.4
provides an independent placement of $n+3+r$ bishops.

For $n$ and $nk+r$ even, and hence $r$ even, the bound given in Lemma 2.1
cannot be met. For $k$ odd, $2n-r$ bishops can placed independently as given
in Construction 3.1. For $k$ even $n+r$ bishops can be placed independently as
given in Construction 3.2. Each of these constructions provides a lower bound
for the independence number of their cases. Consider the set of $n-r-1$
maximal diagonals for $0<r<n$ (and $n-1$ maximal diagonals for $r=0$) which
pass the left square face via identities 1 and 5 passing each square face once
for $k$ odd and twice for $k$ even, these diagonals form a cycle set; by
symmetry there are four such cycle sets for $k$ odd and two for $k$ even. For
$0<r<n$, consider also the set of $r-1$ maximal diagonals which pass the left
square face via identities 1 and 5 passing each square face twice for $k$ odd
and once for $k$ even, these diagonals also form a cycle set; by symmetry
there are two such cycle sets for $k$ odd and four for $k$ even. By numbering
consecutively from 1 the members of each cycle set, each set can be further
split into two groups (referring to the value of each diagonal’s numbering):
the odd members $\mathfrak{P}$ of which there will be $\frac{n-r}{2}$ for each
set of the first kind and for $0<r<n$ there will be $\frac{r}{2}$ for each set
of the second kind; and the even members $\mathfrak{Q}$ of which there will be
$\frac{n-r-2}{2}$ for each set of the first kind and for $0<r<n$ there will be
$\frac{r-2}{2}$ for each set of the second kind. Since $n$ and $nk+r$ are
even, only the members of $\mathfrak{P}$ of each cycle set intersect the 12
open diagonals on a square. Further, the members of $\mathfrak{Q}$ only
intersect members of $\mathfrak{P}$ of other cycle sets on a square. Thus,
placed anywhere, a bishop covers a member of $\mathfrak{P}$, and hence an
upper bound on the maximum number of bishops that can be placed independently
on the board is $|\mathfrak{P}|$ which is $2n-r$ for $k$ odd and $n-r$ for $k$
even.

∎

## References

  * Berghammer (2011) R. Berghammer.  Relational modelling and solution of chessboard problems.  In _de Swart H. (eds) Relational and Algebraic Methods in Computer Science_ , volume 6663 of _RAMICS_ , pages 59–71. Springer, Berlin, Heidelberg, 2011.
  * Demaio and Faust (2009) J. Demaio and W. Faust.  Domination and independence on the rectangular torus by rooks and bishops.  _Technical report, Department of Mathematics and Statistics, Kennesaw State University_ , 2009.
  * Harris et al. (2013) L. H. Harris, S. Perkins, P. A. Roach, and S. K. Jones.  Bishop independence.  _British Journal of Mathematics and Computer Science_ , 3(4):835–843, 2013.
  * Omran (2017) A. A. Omran.  Domination and independence in cubic chessboard.  _Engineering and Technology Journal_ , 35(1 Part (B) Scientific):68–75, 2017.
  * Sowndarya and Yendamuri (2018) K. S. P. Sowndarya and L. N. Yendamuri.  Perfect domination for bishops, kings and rooks graphs on square chessboard.  _Annals of Pure and Applied Mathematics_ , 18(1):59–64, 2018.
  * Watkins (2018) J. J. Watkins.  _Across the Board: the Mathematics of Chessboard Problems_.  Princeton University Press, 2018.
  * Yaglom and Yaglom (1964) A. M. Yaglom and I. M. Yaglom.  _Challenging mathematical problems with elementary solutions_.  Holden-Day Inc., 1964.

Figure 1: Independent placement of bishops for $k$ odd, $n$ and $m$ even: a 6
$\times$ 6 $\times$ 8 Cuboid. Figure 2: Independent placement of bishops for
$k$, $n$ and $m$ even: a 6 $\times$ 6 $\times$ 14 Cuboid. Figure 3:
Independent placement of bishops for $k$ odd, $n$ even and $m$ odd: a 6
$\times$ 6 $\times$ 9 Cuboid. Figure 4: Independent placement of bishops for
$k$ even, $n$ even and $m$ odd: a 6 $\times$ 6 $\times$ 15 Cuboid. Figure 5:
Independent placement of bishops for $k$ and $n$ odd: a 5 $\times$ 5 $\times$
7 Cuboid. Figure 6: Independent placement of bishops for $n$ odd and $k$ even:
a 5 $\times$ 5 $\times$ 12 Cuboid.