Optimal Single-User Interactive Beam Alignment with Feedback Delay

We consider a single-user downlink communication scenario in a single-cell mmWave system. Motivated by previous works (e.g., [13, 14, 15]) and experimental studies (e.g., [5]), we assume that the mmWave propagation channel has only a single dominant cluster. We denote the AoD corresponding with this cluster by $\psi$ which is unknown to the BS. Motivated by several prior works (e.g., [15, 14, 12, 13]), we consider an analog BF architecture at the BS enabling it to use one beam at a time while the user is assumed to have an omnidirectional reception pattern. The goal of BA is to find the shortest possible angular interval, called uncertainty region (UR), containing $\psi$. This, in turn, results in the largest beamfomring gain. After BA, the BS will use a beam covering the entire UR for data transmission. We assume $\Psi\sim f_{\Psi}(\psi)$ for $\psi\in(0,2\pi]$ which accounts for the prior knowledge on the AoD (e.g., corresponding to the history of previously localized AoD in beam tracking applications). The BA algorithm can exploit this knowledge to reduce the width of UR and increase the beamforming gain during data transmission.

Due to practical constraints, we only consider use of contiguous beams as in [11]. Similar to [15, 14, 12, 13, 24], we assume that the beams are ideal and use the sectored antenna model introduced in [25]. In this model, each beam is characterized by an angular interval $\Phi$ representing the angular coverage region (ACR) of the beam as well as a constant beamforming gain equal to $2\pi/|\Phi|$ representing the directivity gain of the beam²²2In this paper, we neglect the impact of side-lobes and leave it for future studies.. In the case of contiguous beams, ACR $\Phi$ is a contiguous interval within $(0,2\pi]$. This model is justified as the BSs are envisioned to use large antenna arrays allowing for close to ideal beam shapes [2].

We consider an interactive BA scenario in which the BS receives feedback form the user during the transmission of BA probing packets and can change the subsequent scanning beams based on the feedback. Unlike conventional interactive BA in which the feedback to each transmitted packet is assumed to be available at the BS instantly [13, 15], we consider a fixed known delay of $d$ time-slots for each user feedback. This delay accounts for practical constraints such as processing and decoding delays at the transceivers or constraints imposed by the standard (e.g., 3GPP) where there are certain timings for various procedures. If an accurate value of this delay is not available, an upper bound can be utilized for our analysis. We assume that the feedback to each probing packet is either an acknowledgement (ACK) implying that the packet was received by the user or a negative acknowledgement (NACK) which indicates the user did not receive the packet. In our setup, NACK corresponds to the absence of ACK. Similar to [13], we consider that the feedback is received through an error free dedicated control channel [2]. Also, as in [12, 11], we assume that each BA packet is detected at the user without error if the beam used for BA packet transmission includes $\psi$.

Motivated by the above discussion, we consider a time-slotted system in which a fixed AoD is associated with user’s channel over a coherence interval of duration $T$ time-slots. We assume that the coherence interval comprises three phases as shown in Fig. 1. The first is scanning phase in which the BS transmits $b$ BA probing packets through a set of scanning beams to scan the surrounding angular space. Since the response to each packet takes $d$ time-slots, after the scanning phase there is a waiting phase in which the BS waits to receive the feedback to all of the probing packets. This phase lasts for $d$ time-slots and can be used for example, for data transmission to other users for which the BS has already performed BA. Subsequently, the BS processes all the feedback received and infers a beam for data communication. The rest of the coherence interval, i.e., the last $T-b-d$ time-slots, is called transmission phase which is used for data transmission using the beam inferred from the previous phases.

Our main goal is i) to design a dictionary of beams to be used in the scanning phase given the prior distribution of user’s AoD, ii) to provide an approach for using the designed beams in the scanning phase, and iii) to propose a method for processing the user’s feedback and construct a beam for data transmission. The main objective in all the steps is to maximize the expected beamforming gain during data transmission.

In the scanning phase, the BS uses $b$ scanning beams $\{\Phi_{i}\}_{i\in[b]}$ to transmit $b$ BA probing packets³³3We use the notation $[n]$ to represent the set $\{1,2,\ldots,n\}$.. Let $a_{i}\in\{0,1\}$ denote the feedback received for the $i^{\rm th}$ BA packet, where $a_{i}=1$ if ACK was received for $\Phi_{i}$ and $a_{i}=0$, otherwise. In general, the scanning beam $\Phi_{i}$ is determined based on the received feedback sequence until time-slot $i$ i.e., $(a_{1},a_{2},\ldots,a_{i-d})$. To model this, we adopt a hierarchical beam set ${\cal S}(b,d)=\{{\cal S}_{i}\}_{i\in[b]}$, where ${\cal S}_{i}=\{S_{i,m}\}_{m\in[M(i-d,d)]}$ denotes the set of designed scanning beams for time-slot $i$. Note that there are a total of $M(i-d,d)\leq 2^{i-d}$ possible feedback sequences until time-slot $i$. To elaborate, the set ${\cal S}_{i}$ contains a beam for each possible feedback sequence received by the $i^{\rm th}$ time-slot, the BS selects the beam $S_{i,m}\in{\cal S}_{i}$ for the transmission of the next probing packet based on the realization of the received feedback sequence. To simplify the notation, unless necessary, we refer to ${\cal S}(b,d)$ by ${\cal S}$.

Next, we describe how to process the received user feedback and infer the shortest angular region including the user’s AoD (i.e., UR). Given an AoD realization $\psi$, we denote the angular region that the BS chooses for data transmission (i.e., UR) by $\text{\sf Beam}({\cal S},\psi)$. Under the assumption of having a single dominant path channel and error free system, the minimum width UR is

where $\Theta(\Phi_{i},a_{i})=\Phi_{i}$ if $a_{i}=1$ which corresponds to $\psi\in\Phi_{i}$, and $\Theta(\Phi_{i},a_{i})=(0,2\pi]-\Phi_{i}$, otherwise. Based on (1), given ${\cal S}$, we get an UR for each possible feedback sequence $(a_{1},a_{2},\ldots,a_{b})$. We denote the set of possible URs by ${\cal U}=\{U_{m}\}_{m\in M(b,d)}$. Note that the number of URs at the end of the BA is the same as the number of possible feedback sequences received by time-slot $b+d$, that is $M(b,d)$. Note that the URs $U_{m}$s are disjoint. For reliable transmission, the BS forms a beam to cover the entire UR in the data transmission phase which means that $\text{\sf Beam}({\cal S},\psi)=U_{m}$ if $\psi\in U_{m}$. To further clarify the above discussions, let’s consider the following example.

One important observation from Ex. 1 is that even though the scanning beams are contiguous, the URs might be fragmented which is the case for $U_{2}$. However, for our optimality achieving BA procedure, which will be discussed later in the paper, we show that the resulting URs are contiguous intervals when using contiguous scanning beams. This means that the data beam will also be contiguous.

The objective is to design the set of scanning beams ${\cal S}$ so as to maximize the expected beamforming gain during data transmission. Based on the discussions in Sec. II-A, this is formulated as follows.

where the expectation is taken over the AoD prior $f_{\Psi}(\psi)$. Using the definition of URs, we can rewrite the expected beamforming gain as

where notation $|U_{m}|$ is the Lebesgue measure of $U_{m}$, which is equal to the total width of the intervals in the case where $U_{m}$ is the union of a finite number of intervals.

As it can be observed form (3), the performance of any scanning beam set ${\cal S}$ depends solely on the set of possible URs it may generate. Therefore, we can characterize the performance of the optimal scanning beam set by investigating the properties of the corresponding URs.

Considering the example shown in Fig. 2, we observe that the angular intervals in between the dotted-dashed lines can be used as basis for representation of the scanning beams. We refer to such angular intervals as component beams formally defined below.

Note that based on Def. 1, the component beams are contiguous and partition interval $(0,2\pi]$. As a result, we can use their position on the circle to define a cyclic order and form a loop of component beams. We denote this loop by ${\cal I}$. For the setup in Ex. 1 these component beams and their loop are⁴⁴4We use the notation $\odot[\ldots]$ to indicate loops.

We can use ${\cal I}$ to provide a binary loop representation of each of the scanning beams. For a given scanning beam, we construct this binary loop by putting one at the position of the component beams which represent (i.e., partition) the scanning beam and zero elsewhere. For example, the binary loop representing the beam $S_{2,1}$ in Ex. 1 is $\odot[1~{}0~{}0~{}0~{}0~{}0~{}0~{}1~{}1~{}1]$. As we can see, the positions of ones in this loop are consecutive (note that the first element is located right after the last element since it is a loop). This property holds for all of the scanning beams since they are contiguous. We refer to such binary loops as unimodal loops formally defined below.

Next, we use the loop of component beams and the unimodality property to study some properties of feedback sequences.

Let us create a loop of the feedback sequences of a scanning beam set ${\cal S}$ by first forming its loop of component beams and then replacing each element of the loop with its corresponding feedback sequence, i.e., the feedback sequence that the BS would receive if the AoD of the user falls inside that component beam. We denote this loop by ${\cal L}(b,d)$, where $b$ is the BA duration and $d$ is the delay. As an example, for the setup in Ex. 1 whose loop of component beams is shown in (4), this loop is

To simplify the notation, unless necessary, we refer to ${\cal L}(b,d)$ by ${\cal L}$. Before, we provide some general properties of ${\cal L}$, let us first consider the following example.

Generalizing the above example, we have the following theorem.

While the loop of feedback sequences, ${\cal L}$, cannot have consecutive column repetitions, non-consecutive repetitions are still possible. For example, in the loop ${\cal L}(4,3)$ shown in (9) columns two and four are identical. On the other hand, the UR corresponding to a feedback sequence is the union of component beams in ${\cal I}$ that have that feedback sequence. Therefore, column repetition in ${\cal L}$, means there are non-contiguous URs. For example, for the loop ${\cal L}(4,3)$ in (9), the UR $U_{2}=\cup\{I_{2},I_{4}\}$ is non-contiguous. This can also be observed from Fig. 2.

So far, we have shown that a scanning beam set ${\cal S}$ can be decomposed into the pair $({\cal I},{\cal L})$, where ${\cal L}$ is $(b,d)$-unimodal. Conversely, in this sub-section, we argue that given a pair $({\cal I},{\cal L})$, where ${\cal I}$ and ${\cal L}$ have the same cardinality (number of columns) and ${\cal L}$ is $(b,d)$-unimodal, we can construct a scanning beam set that corresponds to $({\cal I},{\cal L})$. Before providing the construction, let us consider the following example.

Generalizing this example we have the following result.

Using Theorems 1 and 2, we can establish the equivalence of finding the optimal scanning beam set ${\cal S}^{*}$ in (2), and finding the optimal pair of loops of component beams and loops of feedback sequences $({\cal I}^{*},{\cal L}^{*})$. We characterize the properties of $(b,d)$-unimodal loops and construct an optimality achieving loop of feedback sequences ${\cal L}^{*}$ in the next section. Then, in Section V, we provide an optimal loop of component beams ${\cal I}^{*}$ and consecutively an optimal scanning beam set ${\cal S}^{*}$, and a lower bound on the maximum expected beamforming gain.

As discussed in Sec. III, given a pair $({\cal I},{\cal L})$, where ${\cal I}$ and ${\cal L}$ have the same number of elements and ${\cal L}$ is $(b,d)$-unimodal, we can use Const. 1 in Thm. 2 to generate a scanning beam set ${\cal S}$ corresponding to $({\cal I},{\cal L})$. Moreover, each UR of ${\cal S}$ is the union of the component beams in ${\cal I}$ that have the same feedback sequences (same columns of ${\cal L}$).

Consider the optimization in (3). For the case of the uniform prior, given that the number of URs (number of unique columns in ${\cal L}$), $M(b,d)$, is fixed, it is straightforward to see that to maximize the beamforming gain we need to use a loop of component beams, ${\cal I}$, that leads to equal width URs. As a result, we get the optimal beamforming gain of $M(b,d)$. Therefore, to achieve the optimal performance for the case of the uniform prior, we need to use a $(b,d)$-unimodal loop that has the maximum number of unique columns. On the other hand, for a general prior $f_{\Psi}(\cdot)$, the more columns we have in the loop of feedback sequences, ${\cal L}$, the more degrees of freedom we will have in optimizing the URs. Motivated by these observations, we formally define a new class of $(b,d)$-unimodal loops below.

In the sequel, we will show that max cardinality loop, ${\cal MCL}$, exists by providing a construction and prove that it is sufficient to use an ${\cal MCL}$ to find an optimal scanning beam set, ${\cal S}^{*}$. For our construction, we make use of the following observation.

Let us consider the loop of feedback sequences in (9) corresponding to the scanning beam set $\{{\cal S}_{i}\}_{i\in[4]}$ shown in Fig. 2. If we remove the last row of this loop and then the resulting consecutive repetitions of its columns, we get the loop

which is the loop of feedback sequences corresponding to the scanning beam set $\{{\cal S}_{i}\}_{i\in[3]}$. In general, given a scanning beam set $\{{\cal S}_{i}\}_{i\in[b]}$ and its loop of feedback sequences ${\cal L}$, by removing the last row of ${\cal L}(b,d)$ and the resulting consecutive repetitions, we get the loop of feedback sequences ${\cal L}(b-1,d)$ corresponding to $\{{\cal S}_{i}\}_{i\in[b-1]}$. Motivated by this observation, we define a parent-child hierarchy for the $(b,d)$-unimodal loops formally defined below.

Note that the unique parent loop of $(b,d)$-unimodal loop is $(b-1,d)$-unimodal. However, a parent loop can result in different child loops. For our results, we also need to define the following notation related to the unimodal loops in Def. 2.

As an example, the loop $\odot[0~{}0~{}0~{}1~{}0~{}0~{}0]$ is a unimodal loop of length seven with $i_{f}=i_{l}=4$.

To construct an ${\cal MCL}$, we first study the properties of the parent-child hierarchy in Def. 4 and discuss child loop construction form a parent loop. To this end, let us consider the following example.

Generalizing Ex. 4, we have the following theorem.

Next, we will quantify the maximum number of columns and unique columns one can have in a child loop given a parent loop. Let us consider the following example first.

Example 5 shows that depending on the concatenated unimodal loop at Step 3 of Const. 2, the difference between the number of columns (or unique columns) of the child and parent loop can vary. In the next Proposition, we quantify the maximum changes between a child loop and its parent loop in terms of the number of columns and unique columns and provide unimodal loops that can be used at the loop concatenation step (Step 3) that achieve this maximum changes.

As discussed, we are interested in the max cardinality unimodal loop for a given BA duration $b$ and delay $d$. So far, we have provided a construction for child loops from a parent loop (Const. 2 of Thm. 3 ) and quantified the maximum number of columns and unique columns that can be added (per sub-loop) in this construction to the child loop (Prop. 1).

To find a max cardinality loop for any $b$ and $d$, let us start from ${\cal MCL}(1,d)=\odot[0,1]$ and increase duration $i$ by one at a time using Const. 2, until we reach $b$ while applying Prop. 1. We have two possibilities.

When $\mathbf{d=1}$, for any $i$, each sub-loop formed at Step 1 of the Const. 2 only consists of identical columns. This means that for $d=1$, we can only (and always) apply Case $1$ of Prop. 1 for each sub-loop and each $i$. Therefore, we can get ${\cal MCL}(b,1)$ using this method.

When $\mathbf{d\geq 2}$, for any $i$, we want to ensure that a sub-loop formed at Step 1 of the Const. 2 always corresponds to Case 2 in Prop. 1. However, this might not always be the case so we impose additional constraints motivated by the following example.

Generalizing this example, to make sure that each sub-loop includes at least two unique columns, at Step 3 of Const. 2, we need to use a unimodal loop whose first and last flip positions $i_{f}$ and $i_{l}$ correspond to the columns (if any) with different prefixes of length $i-d+1$. On the other hand, the maximum number of unique prefixes of length $i-d+1$ in a sub-loop is two since each sub-loop consists of columns with the same prefix of length $i-d$ and the $(i-d+1)^{\rm th}$ bit is either one or zero. Therefore, we have the following result.

Next, we provide the exact number of columns and unique columns for max cardinality loops.

We conclude this section by proving the optimality of max cardinality loops.

Theorem 6 indicates that an ${\cal MCL}$, can be used as an optimality achieving loop of feedback sequences ${\cal L}^{*}$.

From Thm. 5, we observe that $M^{*}(b,d)=N^{*}(b,d)$ for $d\geq 2$. As a result, for $d\geq 2$ no ${\cal MCL}$ includes any repetitions. In our BA problem, this means that the max cardinality loop resulting from Const. 3, leads to contiguous URs. This is important in practice since contiguous beams are easier to implement compared to non-contiguous beams. We will provide a method for deriving these contiguous beams in the next section along with a lower-bound on the optimal performance.

In Thm. 6, we have shown that to find an optimal scanning beams set ${\cal S}^{*}$, it is enough to consider a $(b,d)$-unimodal loop, ${\cal L}^{*}$, constructed using Const. 3. Here, we find an optimal loop of component beams ${\cal I}^{*}$ which after combination with ${\cal L}^{*}$ through Const. 1 results to an optimal scanning beam set ${\cal S}^{*}$.

To find the optimal loop of component beams, ${\cal I}^{*}=\{I_{j}^{*}\}_{j=1}^{N^{*}(b,d)},I_{j}^{*}=(x_{j}^{*},x_{j+1}^{*}]$, let us consider the set of URs $\mathcal{U}^{*}=\{U_{k}^{*}\}_{k=1}^{M^{*}(b,d)}$. The angular interval of $U_{k}^{*}$ is equal to the union of the component beams in ${\cal I}^{*}$ whose corresponding feedback is the $k^{\rm th}$ unique column of ${\cal L}^{*}$. We can find the optimal $x_{j}^{*},j\in[N^{*}(b,d)]$ by rewriting the optimization in (2) as follows.