Received August 13, 2019, accepted August 30, 2019, date of publication September 30, 2019, date of current version October 11, 2019. Digital Object Identifier 10.1109/ACCESS.2019.2944579 Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO GABRIEL E. GARCIA 1 , NIL GARCIA1 , (Member, IEEE), GONZALO SECO-GRANADOS 2 , (Senior Member, IEEE), ELEFTHERIOS KARIPIDIS3 , (Member, IEEE), AND HENK WYMEERSCH 1 , (Member, IEEE) 1 Department of Electrical Engineering, Chalmers University of Technology, 41296 Gothenburg, Sweden 2 Department of Telecommunications and Systems Engineering, Universitat Autònoma de Barcelona, 08193 Barcelona, Spain 3 Ericsson Research, 16440 Stockholm, Sweden Corresponding author: Gabriel E. Garcia (ggarcia@chalmers.se) This work was supported in part by the European Research Council under Grant 258418 (COOPNET), in part by the EU project High precision positioning for cooperative ITS applications (HIGHTS) under Grant MG-3.5a-2014-636537, and in part by the Research and Development Project of Spanish Ministry of Science, Innovation and Universities under Grant TEC2017-89925-R. ABSTRACT Millimeter-wave (mm-wave) and massive multiple-input-multiple-output technologies appear as key enablers in future emerging wireless communication systems. Propagation in mm-wave communi- cations is well described by geometric channel models, where a clear relation between communication and positioning arises. On one hand, initial access, a procedure that precedes high data rate transmission and consists of beam selection and alignment between two devices, can benefit from position information. On the other hand, accurate positioning relies on high-quality communication links with proper beam alignment. This work analyzes the interplay between communication and positioning, proposes a new in-band position- aided beam selection protocol considering scenarios with line-of-sight and reflected paths, and possible beam alignment errors. Simulation results show significant reductions in latency with respect to standard beam selection protocols. INDEX TERMS Cramer-Rao bounds, initial access, millimeter wave communication, MIMO, orientation, positioning, position measurement, protocols. I. INTRODUCTION wearables [6] to automotive [7]. However, operating in those Emerging wireless communication systems are intended to bands comes at cost in terms of the high isotropic propagation address stringent requirements in terms of (i) throughput loss. Hence, solutions involving highly directional antennas (1 Gb/s or higher), (ii) low latency (less than one 1 ms), to improve link budgets as well as the implementation of (iii) ultra reliability, and (iv) higher connectivity [1]–[5]. beamforming (BF) both at the transmitter and the receiver Millimeter-wave (mm-wave) communications have recently have been proposed [8]–[10]. These solutions rely on the gained attention in cellular systems operating at frequencies knowledge and characterization of the mm-wave MIMO between 30 to 300 GHz, and where the available bandwidths propagation channel. are wider than in current cellular networks. Moreover, they The mm-wave channel can be characterized with few have been presented as a key enabler to achieve the future parameters by means of stochastic geometrical channel mod- communication system’s requirements along with its inte- els (SGCM), which have become an attractive approach, gration with multiple-input-multiple-output (MIMO), using given the propagation behavior of mm-wave where the line- a large number of antennas. This integration facilitates the of-sight (LOS) and a few dominant multipath components exploitation of spatial multiplexing and provides high data contribute to the received power [11]–[15]. SCGMs relate the rates to users within a wide range of applications, from propagation to the geometry of the operating scenario, thus creating an interplay between the communication channel The associate editor coordinating the review of this manuscript and and the positions of the transmitter and receiver, as well approving it for publication was Wei Xu . as the environment [11]–[15]. On one hand, the positions This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see http://creativecommons.org/licenses/by/4.0/ VOLUME 7, 2019 142325 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO of devices can be estimated through the exchange of mm- wave signals, which in turn requires the establishment of a communication link [16], [17]. On the other hand, the establishment of a communication link can be performed by a dedicated protocol that searches within the angle space: angle of departure (AOD) [18], and angle-of-arrival (AOA) [19], which in turn are geometrically related to the positions of the devices. Hence, the positioning and communication aspects are inherently intertwined [20]. This synergy suggest devot- ing efforts towards finding a joint solution where both the FIGURE 1. Two-dimensional MIMO system model with a D1 with known communication and the positioning aspects can benefit from position and orientation, and a D2 with unknown position (p) and orientation (α), with reflective surface. each other and result in an overall better system performance. This synergy is especially pronounced in the initial access to [37] is the inclusion of both precoding and combining with problem [4], where position information can reduce the time hybrid arrays at both end of the link ( [37] only considered to set up a communication link and where the exchange of precoding and digital receiver arrays), as well as an analysis radio signals provides position information. of the positioning/SNR trade-off. In an a priori unknown Initial access has the aim of establishing a sufficient link environment with unknown device location, we propose to budget, discovering suitable propagation paths for transmis- progressively refine knowledge regarding the device posi- sion, and discarding paths with low gain [4], [21], [22]. Beam tion and orientation during the initial access process, which selection protocols are designed to tackle the initial access allows us to quickly point fine beams towards the device. The problem. These protocols may or may not exploit context or method is evaluated using metrics relevant to communication structure information such as position or channel sparsity. (SNR and set-up time) as well as positioning (position error Conventional protocols such as exhaustive beam selection bound and orientation error bound). Our contributions are: schemes, or received signal power protocols do not consider • A novel in-band positioning-aided beam selection pro- the positioning information in an explicit manner [8]. A great deal of research has been devoted to reduce the time for tocol with the aim of reducing the set-up time of the initial access, including methods for different array types initial access procedure for communication under beam (analog [8], [23], hybrid [14], arrays of subarrays [24], [25]), alignment errors in the presence of a line-of-sight path as well as methods that adapt rate and power [26], [27], and reflectors. The protocol is compatible with standard operate in tracking mode [28]–[30], rely on low-complexity initial access procedures from the literature, but leads to non-coherent processing [31], or consider learning-based faster link establishment. • A numerical trade-off analysis between the final link approaches [32]. Alternatively, context-based methods can exploit position SNR and the position error bounds, providing indi- information. Position information can be harnessed from out- cations for future generation wireless communication of-band technologies, (e.g., Global Positioning System, dis- systems, where adaptive initial access solutions can be placement sensors) in contrast to possible in-band solutions, implemented based on a specific performance metric. where location information is obtained from the mm-wave The remainder of the paper is structured as follows. Section II communication signal itself. Contributions such as [33]–[36] presents the communication model. In section III, the con- exploit position information obtained from out-of-band tech- ventional signal received power-based protocol description nologies. For instance, in [34], a position-aided beam align- and its specifics are described. Then, in section V the ment solution is proposed with the use of position information joint positioning and beam selection protocol, its operation obtained from the on-board train system. A database-based and specifications are introduced. Finally, numerical results solution is proposed in [35], where channel propagation infor- are given in section VII, followed by the conclusions in mation is linked to the user’s geographical position. In [36], section VIII. high-sensitivity displacement sensors provide information about the fixed-position networks nodes to perform beam II. SYSTEM MODEL alignment in mm-wave backhaul systems. In [33], location We consider a MIMO mm-wave system, consisting of a (ref- information is harnessed for fast channel estimation in a erence) device D1 and a second device D2, equipped with vehicular context. As out of band position information may analog arrays (single radio frequency chain per array) of Nt not always be available, in-band position information is a and Nr antennas, respectively. Both devices are assumed to promising alternative or complement. lie on a plane with unobstructed line-of-sight. We denote In this paper, we extend our work from [37] and propose the locations of D1 and D2 by q = [qx , qy ]T ∈ R2 and a fast in-band position-aided beam selection protocol with p = [px , py ]T ∈ R2 , respectively,1 and let α ∈ [0, 2π ) be the the goal of (i) reducing the set-up time of the initial access 1 The analysis can be extended to a 3-dimensional scenario with 2- problem; (ii) determine the location and orientation of a dimensional antenna arrays. A 2-dimensional model and linear antenna device. The main difference of the current work with respect arrays are assumed for simplicity. 142326 VOLUME 7, 2019 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO r −1 1 2π ld TABLE 1. List of notations. [arx (θrx )]N sin θrx ,  l=0 = √ exp j (3) Nr λ where d is the antenna spacing. B. TRANSMITTER We assume the use of beamforming, implemented using phase shifters, and combined with antenna selection. Each transmission consists of N sequentially transmitted sym- bols x[n] = [x1 (n), . . . , xN (n)]T for each subcarrier n = 0, . . . , Ns − 1, with constant energy Ex = E[|xk |2 ]. Hence, the transmitted signal model over subcarrier n can be expressed as fm xT [n] ∈ CNt ×N where fm ∈ CNt ×1 corresponds to a unit energy precoding vector for the m ∈ angle of rotation of the D2 antenna array with respect to the {1, . . . , Mt }-th beam. The precoding vector is expressed as coordinate system of D1 as shown in Figure 1. We assume that q is known and the rotation of D1 with respect to the 1 h jφ 0 iT fm = p 0 ejφm,0 . . . e m,Nt −1 0Nt −Nt0 , (4) absolute coordinate frame is set to zero, while p and α are Nt unknown. The system model setup is general, however, it is where 0Nt −Nt0 is defined as a null vector of size Nt − Nt0 and compatible with downlink transmission since the location of and Nt0 ≤ Nt indicates the number of active antennas, which the transmitter D1 (a base station) is generally known. A list is used to control the beam width at the expense of the beam of notations is found in Table 1. gain [39]. The values of φm,i are dependent on the specific codebook Ctx design for the transmitter, and can include [8] A. GEOMETRIC CHANNEL MODEL WITH LOS AND • 2-bit phase shifters: The phases are constraint to φm,i ∈ REFLECTORS {0, π/2, π, −π/2} . For the LOS path, we can introduce the angle of departure • Unconstrained directional: The phases are linearly (AOD) θtx,0 and angle of arrival (AOA) θrx,0 , which are increasing, φm,i = iφm,0 , where φm,0 is a spa- defined with respect to the absolute coordinate frame and tial frequency, corresponding to a direction θ = to D2’s local coordinate frame, respectively. We denote the arcsin(φ/(2π d/λ)). LOS propagation delay as τ0 = kq − pk /c, where c is the speed of light. The environment can include non-line-of-sight In the current paper, only 2-bit phase shifters are used for (NLOS) paths. For each NLOS path, we assume the existence all protocols. These beams allow for a varying degree of of an incidence point with location sk , k ≥ 1, and the controlled directionality. Fewer active antennas means larger corresponding parameters are: the delay τk = kq − sk k /c + array aperture and consequently broader beams. ksk − pk /c, the AOD θtx,k , and the AOA θrx,k . The relation between the AOD and AOA of each path, and the locations C. RECEIVER sk , p, and rotation α can be graphically observed in Figure 1. We denote the combining vector at the receiver for the l ∈ This relation is also valid when the NLOS path corresponds to {1, . . . , Mr }-th beam as wl ∈ CNr , and it can be expressed a cluster of unresolved rays, and thus captures both specular similarly to the precoding vector as in (4) where the number of and mixed specular/diffuse NLOS. active antennas at the receiver is Nr0 ≤ Nr . Then, the received The transmitting device, D1, transmits OFDM signals at a signal vector for subcarrier n = 0, . . . , Ns − 1 for all N carrier frequency fc (or equivalently wavelength λ = c/fc ) transmitted symbols under a given pair of precoding and and with bandwidth B = 1/Ts over Ns subcarriers. The Nr × combining vectors (fm , wl ), is expressed as a row vector of Nt channel matrix for subcarrier n = 0, . . . , Ns − 1 is given length N by [38] yTl,m [n] = wH T T l H[n]fm x [n] + vl [n], (5) K −1 p X where vl [n]T ∈ CN (0, IN N0 ) denotes additive noise which H[n] = Nt Nr hk arx (θrx,k )aH tx (θtx,k )e −j2πτk n/Ns Ts (1) is independent across subcarriers. Finally, we assume a feed- k=0 back channel exists from D2 to D1 [40]. where hk is a complex channel gain, and atx (θtx,k ) ∈ CNt , arx (θrx,k ) ∈ CNr are the normalized antenna steering and III. CONVENTIONAL BEAM SELECTION response vectors, all associated with the k-th path. We assume The goal of a beam selection protocol is to minimize the uniform linear arrays (ULAs) in both D1 and D2, so that the beamforming set-up time within the initial access proce- steering and response vectors are computed as dure. The IEEE 802.15.3c standard [41], which aims to real- ize Gb/s communication in wireless personal area network t −1 1 2π ld systems, includes an optional functionality based on the hier- [atx (θtx )]N sin θtx  l=0 = √ exp j (2) Nt λ archical codebooks described in [8]. This iterative protocol VOLUME 7, 2019 142327 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO relies on a multilevel beam tree search starting from lower B. SELECTION OF THE NUMBER OF OFDM SYMBOLS resolution beams that cover large angular range per beam, Given a target total error probability Perr  1 and I number moving towards higher resolution beams covering a smaller of iterations, we easily find the alignment error probability ε angular range based on the reference signal received power. at each iteration i from the relation We will describe a general beam selection protocol for D1 and D2 based on reference signal received power during the ini- Perr = 1 − (1 − ε)I . (7) tial access procedure. It is important to note that the beam Note that this relation is not unique and many combinations selection protocol does not exploit any position information. of εi at iteration i could lead to the same Perr . We have chosen to use a fixed ε for each iteration. Given ε = 1 − exp(log(1 − A. GENERIC PROCEDURE Perr )/I ), we find that (see Appendix A) Under the conventional beam selection, the D1–D2 pair  ε 2(2 + νl ∗ −1,m∗ + νl ∗ ,m∗ ) applies an iterative procedure, where at iteration i, a number  (Q−1 ( ))2  Nt0 > Nr0 0 (i) 0 (i) of active antennas (Nt , Nr ) is selected, as well as a set   2 (ν l ,m ∗ ∗ − ν ∗ l −1,m ∗ )2 ε 2(2 + νl ∗ ,m∗ −1 + νl ∗ ,m∗ )   (i) (i) (i) (i) of Mt transmitting beams F (i) = {f1 , . . . , f (i) } and Mr NNs ≈ (Q−1 ( ))2 Nt0 < Nr0 Mt  2 (ν l ∗ ,m∗ − νl ∗ ,m∗ −1 )2 receiving beams W (i) = {w1 , . . . , w (i) (i) ε 2(2 + νl ∗ −1,m∗ + νl ∗ ,m∗ )  (i) } from codebooks   (Q−1 ( ))2 Nt0 = Nr0   Mr (i) 0(i) (i) 0(i) 4 (νl ∗ ,m∗ − νl ∗ −1,m∗ )2 Ctx (Nt ) and Crx (Nt ), which are a function of the con- (i) (i) 0(i) (8) tiguous active antennas [8]. Hence, we have fm ∈ Ctx (Nt ) (i) (i) 0(i) (i) and wl ∈ Crx (Nr ), for m = 1, . . . , Mt , and l = where Q(·) is the Q function. From (8), we can immediately (i) 1, . . . , Mr , respectively. Beam overlapping occurs among find N (i) for a specific iteration i. Note that for different beams that point towards the same direction and belong to iteration numbers, the values of Nt0 , Nr0 as well as νl,m will distinct iteration codebooks with different number of active vary, so that N (i) will generally decrease with the iteration antennas and set of transmitting/receiving beams. For each of index. Note also that under fixed number of subcarriers Ns , (i) (i) the Mt × Mr pairs (fm , wl ), a training OFDM signal is sent and directivity as a function of Nt0 and Nr0 , the number of T(i) over Ns subcarriers, leading to an observation yl,m [n], and the symbols N (Nt0 , Nr0 , ε) serves as a tuneable design parameter corresponding received power is computed. which can be calculated for a specific required ε, or total error In particular, the receiver D2 first computes the received probability Perr . Observe that this calculation involves a given power for each beam pair and then determines the beams nominal channel H[n], from which νl,m are immediately giving rise to the maximum energy derived. s −1 NX 2 T(i) C. PROTOCOL SPECIFICS [l̂, m̂] = arg max yl,m [n] , (l,m) n=0 The above beam selection procedure can be instantiated in a number of ways, for example: and sends back the value of m̂ to D1 over the feedback • Exhaustive: D1 and D2 can both use all available anten- channel. Second, both D1 and D2 determine the number of active antennas as well as a set of beams, for the next nas and all possible associated beams (for orthogonal iteration i + 1, where Nt 0(i+1) 0(i) ≥ Nt and Nr 0(i+1) 0(i) ≥ Nr , codebooks this number would be the same as the number translating into more (or at least not less) directive beams at of antennas) for only a single iteration. In that case, for each iteration step. Note that D2 does not need to know which Mt = Nt and Mr = Nr , the total number of beam pairs (i) scales as O(Mt Mr ) = O(Nt Nr ) [4]. beams D1 transmits, provided the number of beams Mt and (i) • Hierarchical: D1 and D2 can double the number of Mr are agreed upon beforehand. active antennas at each iteration, progressively increas- To ensure that the protocol achieves a certain probability of ing the beam directivity, while maintaining fixed values correct alignment, one can increase the aggregated received for Mt and Mr across all iterations. The total number of energy by adapting the power per iteration [14], or by increas- beam pairs scales as O(Mt Mr max log2 Nt , log2 Nr ). ing the number of symbols N . We have chosen to adapt N at Note that considering the codebook designs described each iteration i and for any combination of transmit Nt0 and in section II-B, a beam pointing towards a predefined receive antennas Nr0 , in such a way that the probability of (i) direction from codebook Ctx (Nt0 ) can be covered by 3 misalignment at a given target distance and at each stage (i+1) beams from codebook Ctx (2Nt0 ) using double number Pr ([l̂, m̂] 6 = arg max νl,m ), of antennas pointing towards the same direction [37]. (l,m) Hence, Mt = Mr = 3 is a reasonable value for all is sufficiently small, where iterations. Ns −1 We note that while the first approach requires a large number Ex X νl,m = l H[n]fm | , |wH 2 (6) of D1/D2 beam pair transmissions, Ns P s −1it hasT(i) the advantage of n=0 evaluating the received energy N n=0 ||y 2 l,m [n]|| for the best which is maximized under optimal alignment. possible beam pair. In contrast, the second approach performs 142328 VOLUME 7, 2019 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO a fast depth-first search, but any mistake in early iterations Given the injective relation between η and η0 described in (i) (i) leads to an inevitable loss in SNR. section IV-A, we can also determine the FIM of Jη0 as Jη0 = (i) TT Jη T, where T is the Jacobian matrix associated with the IV. MM-WAVE POSITIONING DURING BEAM SELECTION transformation from η to η0 , that is, Tij = ∂ηi /∂ηj0 . Finally, In this section, we analyze the tight relation between posi- the inverse of the FIM can be related to the mean squared tioning information and beam alignment. First, we introduce error (MSE) of unbiased estimators of η0 [42]: our observation model based on the received waveforms. Then, we characterize the achievable positioning perfor- h T i h (i) i−1 Ey|η0 η̂0 − η η̂0 − η .   Jη0 (10) mance based on our observation model along with position estimation approaches. At sufficient high SNR, and under some mild conditions [43], the covariance of the maximum likelihood estimator is tight A. OBSERVATION MODEL to this lower-bound. Since we operate in an indoor environ- The signals as observed in (5), depend on the AODs and ment with relatively small distances, we assume the receiver AOAs for the LOS and NLOS paths according to (1). More- operates in a high SNR regime. From this relationship, we can over, as presented in section II, by geometrical analysis, derive the position error bound (PEB) as there exists a relation between the known location of D1, s  the unknown position of D2 with the AOD, θtx,0 , the AOA (i) h i−1  (i) θrx,0 and the delay τ0 for the LOS path. Similarly, for the k- PEB = tr Jη0 (11) 1:2,1:2 th NLOS path, there exists a relation between the incidence q point location sk and the locations of D1, D2 by means of ≤ E{kp − p̂k2 } (12) the delay τk , AOD θtx,k , and AOA θrx,k , k ≥ 1. Given the observation model, we stack the 5K unknown channel and the rotation error bound (REB) parameters in the vector rh i (i) −1 h iT REB(i) = Jη0 (13) η = τ0 , θ T0 , hT0 , . . . , τK −1 , θ TK −1 , hTK −1 , q 3,3 T T ≤ E{kα − α̂k2 }, (14) where θ k = θtx,k , θrx,k , hk = hR,k , hI ,k   = [<{hk }, ={hk }]T . Moreover, here exists an injective relation where [·]−1 1:2,1:2 denotes the 2 × 2 upper left submatrix of the from inverse of the argument, and [·]−1 3,3 denotes the third diagonal h iT element of the inverse of the argument. We observe that the η0 = β T , hT0 , sT1 , hT1 , . . . , sTK −1 , hTK −1 , PEB and REB must be decreasing functions of i, as progres- sively more information is collected. to η, where β = [p, α]T , which will be useful in the fundamental performance characterization. Hence, since the C. POSITION AND ORIENTATION ALGORITHMS received signals can be expressed as a function of η0 , they T(i0 ) Based on yl,m [n], i0 = 1, . . . , i, n = 0, . . . , Ns − 1, provide information regarding [p, α]T as well as sk , k ≥ 1. an estimation problem can be set up to infer β, the position and orientation of D2 at iteration i. Different approaches can B. FUNDAMENTAL PERFORMANCE CHARACTERIZATION be categorized into: In this subsection, we analyze the ability of D2 to estimate its position and orientation β = [p, α]T at each iteration. The 1) One-step: the location of the receiver is estimated Fisher information matrix (FIM) serves as a tool to assess the directly from the transmitted signal, without estimating quality of the estimation [42], without the need to consider intermediate parameters, i.e., AOAs, AODs of LOS or a specific estimator. The FIM associated with observation NLOS paths [44]–[47]. T(i) yl,m [n], due to a beam pair (fm , wl ) subcarrier n at iteration 2) Two-step: first the intermediate parameters such as AOD and AOA and delay are estimated, possibly i, and unknown vector parameter η, Jm,l,iη [n], is a 5K × 5K exploiting channel sparsity [48]–[52], based upon matrix, whose expression is provided in (36) in Appendix B. which a position and orientation estimate is deter- Due to the additive nature of Fisher information and the fact mined [12], [17], [53]. that observations are independent across subcarriers n and beam pairs, the FIM for multiple beams decouples into the As in [37], we abstract our work from the specific method sum of the corresponding FIMs over the total number of beam and instead assume that the estimator of D2’s position and pairs and subcarriers. The total FIM after i iterations can then orientation at each iteration i is efficient, i.e., (i) it is unbiased, be expressed as (ii) the MSE is close to the PEB and the REB at medium to high SNRs. Hence, we assume an idealized receiver which (i0 ) (i0 ) i M t Mr Ns −1 serves to understand the potential behind the use of position X X X X 0 J(i) η = Jm,l,i η [n]. (9) information in the initial access procedure and thus provides i0 =1 m=1 l=1 n=0 a bound for any real receiver. We denote the estimate of β at VOLUME 7, 2019 142329 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO Algorithm 1 Joint Positioning and Beam Selection 0(1) tx , N 0(1) rx Input: Nt , Mt , fmap r , Mr , fmap , Nt , and Nr 0(i) 0(i) while Nt ≤ Nt or Nr ≤ Nr do (i) for m = 1 to Mt do (i) for l = 1 to Mr do D1 transmits a training sequence for each m-th (i) beam pattern, fm ; (i) D2 measures received power Pl,m = PNs −1 T(i) 2 n=0 yl,m [n] for the m-th transmit pattern (i) FIGURE 2. High level depiction of the joint positioning and beam with its l-th receive pattern wl ; selection protocol. Position and orientation information are fed back from D2 to D1. This information is used by D1 to select a higher directivity end for codebook to refine beam search alignment. end for D2 performs in-band positioning and determines a posi- (i) (i) iteration i by β̂ , with associated covariance matrix (i) tion estimate and uncertainty [β̂ , 6 β ]; (i) (i) D2 feeds back [P(i) , β̂ , 6 β ] to D2; h i−1 (i) (i) 6 β = Jη0 . (15) 1:3,1:3 i = i + 1; Remark 1: The approach’s main goal is the estimate of A new selection of beams is obtained for tx (F (i−1) , P(i−1) , β̂ (i−1) , 6 (i−1) ); D1: F (i) = fmap the position and orientation of D2. However, as a side prod- β rx (W (i−1) , P(i−1) , β̂ (i−1) (i−1) uct, estimates of the incidence point can be obtained. Both D2: W (i) = fmap , 6 β ); Bayesian [53] and non Bayesian [17] methods exist, which end while include the ability to estimate the number of paths. These Output: Final transmit and receive beam pattern selections estimates can be used to optimize beam alignment, since fsel , and wsel . beams can be pointed towards the point scatterers themselves. This kind of optimization is relevant when D1, and D2 have more than one radio frequency chain, and when the LOS is tx , and f rx can be designed to adaptive mapping functions fmap map obstructed between devices, so that the best NLOS path is compute the new number of active antennas as well as the new discovered. tx (F (i−1) , P(i−1) , β̂ (i−1) , 6 (i−1) ) and set of beams F (i) = fmap β rx (W (i−1) , P(i−1) , β̂ (i−1) (i−1) V. JOINT POSITIONING AND BEAM SELECTION W (i) = fmap , 6 β ) for beamforming PROTOCOL at D1 and D2, respectively. Examples of mapping functions In this section, we propose an iterative positioning-based will be presented later in the paper. The protocol is described beam selection protocol compatible with the conventional in Algorithm 1. protocol from section III, but including the ability to reduce the initial access time by exchanging in-band position infor- B. CHOICE OF MAPPING mation, obtained as described in section IV. Hence, after The mapping functions at transmitter and receiver account initial access, we aim to have a high SNR for communication both for the receiver energies at D2 as well as the esti- and a low error in the estimate of the position and orientation mation position and orientation. While a variety of map- of D2. ping functions are possible, we here focus on reducing the set-up time by allowing larger increases in the num- A. PROTOCOL DESCRIPTION ber of active antennas and avoiding making incorrect beam The joint positioning and beam selection protocol is an itera- decisions. tive procedure that harnesses not only the received powers • D1 operation: When the position information is suf- at D2, but also its estimated position and orientation β̂ = ficiently accurate, this allows D1 to select a code- [p̂, α̂]T . First, at every iteration i the transmitter sends a book (from the conventional protocol) with higher 0(i) training OFDM signal x[n] over Ns subcarriers for all the directivity, thus selecting a value of Nt that can (i) (i) Mt × Mr pairs (fm , wl ). The receiver D2 computes the significantly exceed 2Nt 0(i−1) , as described in [37]. corresponding received energy for each beam pair and gathers (i−1) (i−1) (i) (i) Given β̂ , 6 β , D1 determines the AOD estimate them in the matrix P(i) ∈ RMt ×Mr . Moreover, D2 deter- (i−1) θ̂tx and uncertainty (standard deviation) σtx (i−1) . Then mines an estimate of its position as described in section IV-C. D1 solves the following problem Considering the position and orientation estimation are well (i) 0(i) approximated by the Gaussian distribution with mean β̂ and maximize Nt (16) (i) a covariance matrix 6 β . This information can be used not (i−1) subject to f = arg max 0(i) tx (θ̂tx aH )f̃ (17) only by D2 but is also fed back to D1. As a consequence, f̃∈Ctx (Nt ) 142330 VOLUME 7, 2019 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO (i−1) κσtx ≤ 3θHPBW (f) (18) dependent on the number of active transmitting, receiv- Nt 0(i) ≥ ζ Nt 0(i−1) (19) ing antennas and the alignment error probability ε and the same for all protocols. Thus, the delay at the final where ζ > 1 is a design parameter to ensure sufficient iteration I can be defined as the total number of OFDM progress, while κ > 1 is set to attain a certain level of symbols transmitted as: robustness against the positioning error, and θHPBW (f) I returns the half-power beamwidth angle of the beam f D = Ns X (i) N (i) Mt Mr(i) . (23) 0(i) using Nt active antennas. When the problem (16) is not i=1 0(i) 0(i−1) feasible, D1 sets Nt = Nt in order to collect more information. Solving the optimization problem entails VII. SIMULATION RESULTS 0 (i) limited complexity: for a fixed value of Nt , finding f is A. SIMULATION SETUP straightforward as it can be implemented in a table look- D1 is fixed at position q = [0, 0]T and D2 located at p = up. Verifying the remaining constraints is trivial. [7, 4]T . We assume K = 2 paths are possible by considering • D2 operation: Independent of D1, D2 solves a the existence of a reflector, represented as a line between similar optimization problem based on w = points [5, 5]T and [5, 7]T . If D2 is inside the reflective area (i−1) arg maxw̃∈C (N 0(i) ) w̃ arx (θ̂rx ) in order to find the H then an incidence point is located at s = [sx , sy ]T , where rx r 0(i) {sx | 5 ≤ sx ≤ 7] and sy = 5. The ULAs are along the largest possible value of Nr . vertical axis. We set for the LOS path Setting a larger ζ avoids making small increments in the √ q number of active antennas, while larger κ means that we want h0 = (1 − ξ )2 exp(jφ0 )/ ρ0 , (24) to cover the angle uncertainty sufficiently well with 3 beams. where ρ0 = (2π kq − pk/λ)2 is the path-loss between D1 and VI. PERFORMANCE METRICS D2, φ0 ∼ U(0, 2π ) and ξ ∈ [0, 1]. For the NLOS path, we set In this section, we present the performance metrics for the √ q protocols presented in sections III and V. The goal of the hk = ξ 2 exp(jφk )/ ρk (25) protocols is to reliably determine the precoding matrix fsel and the combining matrix wsel in a fast manner. Hence, where ρk = (02π (kq − sk k + ksk − pk)/λ)2 , 0 is the the relevant performance metrics include: SNR, positioning reflection coefficient and φ1 ∼ U(0, 2π ). When the NLOS quality computed after beam alignment and delay. path corresponds to a cluster of unresolved rays, the value of 1) SNR: The selection of fsel and wsel has as main objec- hk should be replaced by the superposition of the complex tive to maximize the SNR, which is defined as gains of each ray. The parameter ξ allows us to control the energy division between the LOS and NLOS paths, i.e., when Ex X Ns −1 ξ = 0, only the LOS path is present, while when ξ = 1 only sel H[n]fsel | , |wH 2 SNR , (20) the NLOS path is present. Moreover, we set fc = 60 GHz, N0 Ns n=0 B = 100 MHz, and a nominal SNR of 10 dB at a distance where Ex is the energy per symbol. of 10 meters between D1 and D2 for a fixed ξ = 0.25. 2) Positioning quality: The MSE of the positioning and Furthermore, we consider Ns = 65 subcarriers, the number orientation errors are of antennas at both D1 and D2 is Nt = Nr = 64, and the inter-element spacing is d = λ/2. The number of OFDM E{kp − p̂k2 } (21) 0(i) 0(i) symbols N (i) (Nt , Nr , ε) are tabulated and equally defined for all protocols. and We will evaluate three protocols in terms of SNR, posi- E{kα − α̂k2 }, (22) tioning and orientation quality (PEB and REB) and delay for scenarios with the reflector (R) and with no reflector (NR): where p̂ and α̂ denote the estimated position and angle • Conventional beam selection protocol (CBS) which of rotation for the D2, respectively, obtained from the can only use Mt , Mr ∈ {2, 4, 8, 16, 32, 64} discrete sequence of received signals of the form (5). beams, Nt0 = Mt and Nr0 = Mr active contiguous 3) Delay: Assuming a fixed number2 of symbols and antennas sequentially selected, generated using phase subcarriers throughout each iteration i, the delay is shifters φi = {π, 0, π/2, −π/2}, based on [8]. The CBS dependent on the number of Mt × Mr pairs (fm , wl ), is instantiated according to the hierarchical approach the number of subcarriers Ns employed and number described in section III-C. of symbols sent N (i) . The number of OFDM sym- • Joint positioning and beam selection protocol (JPBS), bols N (i) (Nt0 , Nr0 , ε) at each iteration is predefined and which uses the same discrete codebook as the CBS. The 2 More advanced protocols can include adaptive number of symbols and JPBS generates estimates of the position of D2 as p̂ ∼ (i) subcarriers within each iteration to mitigate beam alignment errors and N (p, [Jη0 ]−1 −1 1:2,1:2 ) where [·]1:2,1:2 denotes the 2×2 upper reduce even further the delay. left submatrix of the inverse of the argument. The JPBS VOLUME 7, 2019 142331 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO FIGURE 3. SNR as a function of the total number of OFDM symbols. FIGURE 4. PEB as a function of the total number of OFDM symbols. is instantiated as described in section V. The design 2) POSITIONING ERROR VS. DELAY parameters are set to ζ = 2 and κ = 2. Figure 4 shows the PEB as a function of the total number • For the sake of completeness we include results for an OFDM symbols for a fixed ξ = 0.25. Note that in practice, exhaustive beam selection (EBS) protocol instantiated position information can only be exploited by the JPBS. Once as explained in section III-C. again, for each protocol line in Figure 4 the markers to the We note that since both the devices have a single RF left-most correspond to the probability of making a mistake chain, comparison with more sophisticated protocols (e.g., in the beam pair selection half of the time, i.e., ε = 0.5, while with hybrid precoding) is not possible. the markers at the right-most of the plot for each of the proto- col lines correspond to a low probability of making a mistake, B. RESULTS AND DISCUSSION i.e., ε = 0.01. The exhaustive approach exhibits a fixed 1) SNR VS. DELAY number of OFDM transmitted symbols. Since for a fixed ε Figure 3 shows the final SNR, as expressed in equation (20), there exists a fixed number of OFDM symbols transmitted per as a function of the total number of total OFDM symbols beam pair combination the PEB remains fixed due to the fact needed for the protocols for ξ = 0.25 for different values that the FIM always harnesses the same information. We can of ε (ranging from 0.5 on the left side to 0.01 on the right observe for the conventional approach that the PEB decreases side). A lower ε requires a higher number of transmitted sym- with decreasing ε: lower alignment error probability results in bols N (i) to attain the desired alignment error requirement. less beams pair misalignment within iterations, which in turn The exhaustive protocol corresponds to a single delay, since affects the positioning error. Similar behavior for the REB 0(i) 0(i) N (i) (Nt = 64, Nr = 64, ε) = 1, and thus shows as a occurs, thus, only figures for the PEB are included. Under the single point in the figure. As expected, we observe that for same initial conditions, the JPBS shows lower PEB even in the CBS protocol the SNR increases with smaller ε. However, scenarios with large alignment error probability. For instance, the SNR increase comes at a cost in terms of delay since for ε = 0.35 the PEB for the JPBS is approximately 55% a lower ε leads to more OFDM symbols per iteration. The and 65% lower in comparison with the CBS-NR and CBR- JPBS shows a constant maximum achievable SNR. The SNR R, respectively; while the delay is approximately 15% lower, of the positioning-based protocol is not affected by ε, instead, respectively. As discussed before, ε has no direct impact on a lower ε allows the JPBS to collect more information at the JPBS protocol in terms of final SNR. However, a change early iterations since a higher number of OFDM symbols in ε involves a change in the number of iterations and thus, are transmitted, and thus perform aggressive increases at transmitted OFDM symbols, which affect the position esti- each iteration on the number of active contiguous antennas mation. Figs. 6 and 7 exemplify the convergence of the JPBS 0(i) 0(i) at the transmitter and receiver, Nt and Nr , respectively. in terms of the probability of change of the selected number These aggressive increases translate into a smaller delay for of active antennas for the transmitting and receiver devices a given value of ε compared to the CBS.The JBPS pro- for  = 0.5. As an example, in Fig. 6, there is probability of tocol attains to the achievable SNR even for a high ε at 0.41 and 0.55 to go from 2 transmitting antennas at iteration a small delay compared to the CBS and at more than a i to 8 or 16 antennas at iteration i + 1, respectively. Similarly, hundred times faster. Note that, it is only when ε ≈ 0.01 there exists approximately a probability of 0.85 when going (right-most markers) that the SNR for both the conven- from 8 or 16 active transmitting antennas to at iteration i to 64 tional and the positioning protocol are the same achievable antennas at iteration i+1. We can observe that despite the high SNR. beam alignment the JPBS protocol shows a fast convergence 142332 VOLUME 7, 2019 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO FIGURE 7. Probability of the change of selected number of receiving FIGURE 5. PEB as a function of the final SNR. Different data points active antennas antennas from iteration i to iteration i + 1 for  = 0.5. correspond to different values of ε, where smaller ε leads to higher SNR and lower PEB at a cost of more delay. The proposed JPBS method achieves the highest SNR. FIGURE 8. PEB as a function of the final SNR for different LOS and NLOS conditions for ε = 0.1. Different data points correspond to different ξ , where increasing ξ means a weaker LOS and a stronger NLOS path. The FIGURE 6. Probability of the change of selected number of transmitting conventional methods are more robust than the proposed method, active antennas from iteration i to iteration i + 1 for  = 0.5. leading to high SNR when all the energy is in a single path (LOS or NLOS). 4) LOS VS. NLOS in terms of the number of selected active antennas between In contrast to [54], which considered a trade off between consecutive iterations. PEB and effective rate, rather than SNR, Figure 8 shows the relationship between the SNR and PEB for different LOS 3) SNR VS. POSITIONING ERROR and NLOS conditions for a fixed ε = 0.1. Each marker Figure 5 shows the connection between SNR and PEB for within the protocol’s curve corresponds to a increasing ξ , the different protocols and a fixed ξ = 0.25. Each marker where ξ = 0 corresponds to the existence only of the LOS within each protocol’s curve corresponds to a different ε. path component, and ξ = 1 corresponds to the existence The EBS protocol shows a fixed SNR and PEB independent only of the reflected path. The JPBS shows a negative linear of the alignment error probability. We observe that for the trend with increasing ξ, showing that both the PEB and SNR CBS protocol a low PEB means a higher SNR, since at of the JPBS degrade when ξ approaches 1, since JPBS is small alignment error probabilities, beam pairs within each designed specifically for channels with a strong LOS com- iteration are correctly chosen to be aligned between devices, ponent (see also Figure 9). The CBS and EBS show a similar contributing to a lower PEB. Finally, the JPBS shows a PEB behavior: when ξ ≈ 1 a lower SNR is achieved compared decrease for decreasing ε. For each protocol, attaining better to the case where only a LOS path exists, i.e., ξ = 0, due SNR and lower PEB are a consequence of devoting more time to the higher pathloss. Moreover, both methods show their during initial access. Hence, there is no trade-off between higher PEB and lowest SNR when ξ ≈ 0.55, when the communication and localization performance. reflected path is just slightly stronger than the LOS path. VOLUME 7, 2019 142333 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO the presence of multipath propagation channels, provided the LOS path is sufficiently strong compared to other paths. The protocol can be extended to explicitly account for multipath (through estimating incidence points) as well, in order to operate when LOS is weak or not present. APPENDIX A ALIGNMENT ERROR AND NUMBER OF SYMBOLS In order to set the number of OFDM symbols N at each . iteration i we observe that the received signal Yl,m = PNs −1 T n=0 yl,m [n] 2 exhibits a non-central chi-squared random distribution with non-centrality parameter νl,m from (6) and k = NNs degrees of freedom, i.e., Yl,m ∼ χNN 2 (ν ). s l,m Following the central limit theorem, the received signal can be approximated as a Gaussian random variable [55] FIGURE 9. Number of OFDM symbols as a function of LOS and NLOS 2(1 + νl,m )   Yl,m energy parameter ξ , for a fixed  ≈ 0.1. ∼ N 1 + νl,m , (26) NNs NNs For ξ > 0.55, the EBS and CBS are able to partially recover We can express the alignment error probability ε (at itera- their SNR performance by beaming towards the incidence tion i) as point. Finally, Figure 9 depicts the delay as a function of the LOS ε = Pr(∪[l,m] Yl,m > Yl ∗ ,m∗ ) (27) and NLOS conditions. Note that for 0 ≤ ξ ≤ 0.75 the JPBS X ≤ Pr(Yl,m > Yl ∗ ,m∗ ) (28) protocol shows a reduction in the delay of approximately l,m 14% and 22% compared to the CBS and EBS, respectively. ≈ Pr(Yl ∗ −1,m∗ > Yl ∗ ,m∗ ) + Pr(Yl ∗ ,m∗ −1 > Yl ∗ ,m∗ ) (29) However, for a ξ ≈ 1, the JPBS needs a larger number of transmitted symbols due to the poor position estimates which + Pr(Yl ∗ +1,m∗ > Yl ∗ ,m∗ ) + Pr(Yl ∗ ,m∗ +1 > Yl ∗ ,m∗ ), translate into a higher delay compared to both the CBS and The inequality in equation (28) follows from the union union EBS. bound and the approximation in (29) reflects the error being We can conclude that under a small and fixed ε and a strong dominated by neighboring beams. Given the symmetry within LOS path, all protocols have a similar SNR performance but the codebook design we can express  as the JPBS outperforms the other protocols in terms of delay, which results in faster set up times; on the other hand when ε ≈ 2Pr(Yl ∗ −1,m∗ − Yl ∗ ,m∗ > 0) the NLOS path is strong (ii) the CBS and EBS show an overall better performance in terms of delay and SNR compared to + 2Pr(Yl ∗ ,m∗ −1 − Yl ∗ ,m∗ > 0) (30) the JPBS, which due to the poor position estimates require a We note that when Nt0 > Nr0 , then the first term in (30) will high number of iterations and is not able to establish a reliable dominate (as the receiver is using broader beams and is thus link. more likely to make errors), while for Nt0 < Nr0 , the second term in (30) will dominate. From (26), we find that VIII. CONCLUSION We have proposed and analyzed a novel simultaneous posi- Yl,m /(NNs ) − Yl ∗ ,m∗ /(NNs ) ∼ (31) tioning and beam selection protocol, harnessing the syn-   ergy between communication and positioning that exists in 2(2 + νl,m + νl ∗ ,m∗ )  N νl,m − νl ∗ ,m∗ , ,  mm-wave channels. We have shown that an in-band position- | {z } NNs aided protocol achieves similar, or even better, SNR as the <0 conventional protocol but with a reduction of the setup time. This improved performance comes at a cost of increased com- from which it follows that putational complexity, as at each iteration the position and orientation of a device needs to be estimated. The provided Pr(Yl ∗ −1,m∗ /(NNs ) − Yl ∗ ,m∗ /(NNs ) > 0) (32) √ ! position information is more accurate than in the conventional NNs (νl ∗ ,m∗ − νl ∗ −1,m∗ ) =Q p protocol. Moreover, for short durations of the reference sig- 2(2 + νl ∗ −1,m∗ + νl ∗ ,m∗ ) nal, the conventional protocol is prone to beam alignment Pr(Yl ∗ ,m∗ −1 /(NNs ) − Yl ∗ ,m∗ /(NNs ) > 0) (33) errors, and the positioning-aided protocol outperforms the √ ! conventional protocols in terms of final SNR at a similar per- NNs (νl ∗ ,m∗ − νl ∗ ,m∗ −1 ) =Q p (34) formance in delay. The position-aided protocol can operate in 2(2 + νl ∗ ,m∗ −1 + νl ∗ ,m∗ ) 142334 VOLUME 7, 2019 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO ∂m[n] where Q(·) denotes the Q-function. Hence,  √ ! ∂hI ,i NNs (νl ∗ ,m∗ − νl ∗ −1,m∗ )   −j2π nτi >  2Q p Nt0 Nr0 = κj exp wH arx (θrx,i )aH  tx (θtx,i )fx [n] (43)  2(2 + νl ∗ −1,m∗ + νl ∗ ,m∗ )     NTs √   ! NNs (νl ∗ ,m∗ − νl ∗ ,m∗ −1 ) We easily find that the diagonal elements of the subma-   ε ≈ 2Q p Nt0 < Nr0 trices J(i,j) [n]. We first define 1/σ 2 = 2Nr Nt /N0 , γtx,i = 2(2 + νl ∗ ,m∗ −1 + νl ∗ ,m∗ ) fH atx (θtx,i ), γrx,i = aH  rx (θrx,i )w as well as ȧtx (θtx ) =  √   ! NNs (νl ∗ ,m∗ − νl ∗ −1,m∗ ) ∂atx (θtx )/∂θtx , γ̇tx,i = ȧH tx (θtx,i )f, and γ̇rx,i = w ȧrx (θtx,i ).   H Nt0 = Nr0   4Q p2(2 + ν ∗  We also introduce Al [n] = (2π n/ (NTs )) , and 1ij [n] =  l ∗ + ν ∗ ∗)  l −1,m l ,m exp −j2π n τi − τj / (NTs ) . from which solving for NNs immediately leads to (8). DIAGONAL ELEMENTS OF J(i ,j ) APPENDIX B We then find that DERIVATION OF THE FIM We consider the case of multiple paths under OFDM trans- 8(τi , τj , n) mission and a transmitting fm ∈ Ctx and and a receiving beam 1 n o = 2 < h∗i hj A2 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 (44) wl ∈ Crx . Without loss of generality, we do not include the σ subscripts of the beam pair for simplicity in the derivation. 8(θtx,i , θtx,j , n) The general form of the FIM for k paths and subcarrier n is 1 n o = 2 < h∗i hj A0 [n]1ij [n]γ̇tx,i ∗ γ̇tx,j γrx,i γrx,j ∗ kx[n]k2 (45) given by σ   8(θrx,i , θrx,j , n) J(1,1) [n] · · · J(1,k) [n] 1 n o .. .. .. = 2 < h∗i hj A0 [n]1ij [n]γtx,i γtx,j ∗ γ̇rx,i ∗ γ̇rx,j kx[n]k2 (46) Jη [n] =  . . . , (36)   σ J(k,1) [n] ··· J(k,k) [n] 8(hR,i , hR,j , n) = 8(hI ,i , hI ,j , n) 1 n o where each of the sub-matrices has the form (35), as shown = 2 < A0 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 . (47) σ at the top of the next page. Denoting the noise-free signal by K −1 OFF-DIAGONAL ELEMENTS OF J(i ,j ) The off-diagonal elements are computed in similar fashion. X H T m[n] = w Hk [n]fx [n], (37) k=0 The final expressions for the upper diagonal elements are computed as: it can be shown that 8(τi , θtx,j , n) ∂mH [n] ∂m[n] Z  2 8(x1 , x2 ) = < dt . (38) 1 n o N0 ∂x1 ∂x2 = 2 < jh∗i hj A1 [n]1ij [n]γtx,i γ̇tx,j γrx,i γrx,j ∗ kx[n]k2 (48) σ √ 8(τi , θrx,j , n) = We define κ = Nt Nr and it is readily verified that for an arbitrary path i, 1 n o = 2 < jh∗i hj A1 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γ̇rx,j kx[n]k2 (49) σ ∂m[n] 8(τi , hR,j , n) ∂τi 1 n o  −j2π nτi  −j2π n H = 2 < jh∗i A1 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 (50) = κhi exp w arx (θrx,i )aH σ tx (θtx,i )fx [n] NTs NTs 8(τi , hI ,j , n) (39) 1 n o ∂m[n] = − 2 < h∗i A1 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 (51) σ ∂θtx,i 8(θtx,i , θrx,j , n) 1 n   −j2π nτi o = κhi exp wH arx (θrx,i )P aH tx (θtx,i )fx [n] (40) = 2 < h∗i hj A0 [n]1ij [n]γ̇tx,i ∗ γtx,j ∗ γrx,i γ̇rx,j kx[n]k2 (52) NTs σ ∂m[n] 8(θtx,i , hR,j , n) ∂θrx,i 1 n o = 2 < h∗i A0 [n]1ij [n]γ̇tx,i ∗ γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 (53)  −j2π nτi  σ = κhi exp wH ȧrx (θrx,i )aHtx (θtx,i )fx [n] (41) 8(θtx,i , hI ,j , n) NTs 1 n o ∂m[n] = 2 < jh∗i A0 [n]1ij [n]γ̇tx,i ∗ γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 (54) σ ∂hR,i 8(θrx,i , hR,j , n)   −j2πnτi 1 n = κ exp wH arx (θrx,i )aH o tx (θtx,i )fx [n] (42) = 2 < h∗i A0 [n]1ij [n]γtx,i γtx,j ∗ γ̇rx,i ∗ γrx,j ∗ kx[n]k2 (55) NTs σ VOLUME 7, 2019 142335 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO 8(τi , τj ) 8(τi , θtx,j ) 8(τi , θrx,j ) 8(τi , hR,j ) 8(τi , hI ,j )    8(θtx,i , τj ) 8(θtx,i , θtx,j ) 8(θtx,i , θrx,j ) 8(θtx,i , hR,j ) 8(θtx,i , hI ,j )   8(θrx,i , τj ) 8(θrx,i , θtx,j ) 8(θrx,i , θrx,j ) 8(θrx,i , hR,j ) 8(θrx,i , hI ,j )    J(i,j) = (35)  8(hR,i , τj ) 8(hR,i , θtx,j ) 8(hR,i , θrx,j ) 8(hR,i , hR,j ) 8(hR,i , hI ,j )   8(hI ,i , τj ) 8(hI ,i , θtx,j ) 8(hI ,i , θrx,j ) 8(hI ,i , hR,j ) 8(hI ,i , hI ,j ) 8(θrx,i , hI ,j , n) [4] M. Giordani, M. Mezzavilla, and M. Zorzi, ‘‘Initial access in 5G mmWave cellular networks,’’ IEEE Commun. Mag., vol. 54, no. 11, pp. 40–47, 1 n o = 2 < jh∗i A0 1ij [n]γtx,i γtx,j ∗ γ̇rx,i ∗ γrx,j ∗ kx[n]k2 (56) Nov. 2016. σ [5] M. Shafi, A. F. Molisch, P. J. Smith, T. Haustein, P. Zhu, P. De Silva, 8(hR,i , hI ,i , n) F. Tufvesson, A. Benjebbour, and G. Wunder, ‘‘5G: A tutorial overview 1 n o of standards, trials, challenges, deployment, and practice,’’ IEEE J. Sel. = 2 < jA0 1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 , (57) Areas Commun., vol. 35, no. 6, pp. 1201–1221, Jun. 2017. σ [6] K. Venugopal and R. W. Heath, Jr., ‘‘Millimeter wave networked wearables in dense indoor environments,’’ IEEE Access, vol. 4, pp. 1205–1221, and for the lower diagonal as: 2016. [7] J. Choi, V. Va, and N. Gonzalez-Prelcic, R. Daniels, C. R. Bhat, and 8(θtx,i , τj , n) R. W. Heach, Jr., ‘‘Millimeter-wave vehicular communication to support massive automotive sensing,’’ IEEE Commun. Mag., vol. 54, no. 12, 1 n o = − 2 < jh∗i hj A1 [n]1ij [n]γ̇tx,i ∗ γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 (58) pp. 160–167, Dec. 2016. σ [8] J. Wang, Z. Lan, C.-W. Pyo, T. Baykas, C.-S. Sum, M. A. Rahman, 8(θrx,i , τj , n) R. Funada, F. Kojima, I. Lakkis, H. Harada, and S. Kato, ‘‘Beam code- book based beamforming protocol for multi-Gbps millimeter-wave WPAN 1 n o = − 2 < jh∗i hj A1 [n]1ij [n]γtx,i γtx,j ∗ γ̇rx,i ∗ γrx,j ∗ kx[n]k2 (59) systems,’’ IEEE J. Sel. Areas Commun., vol. 27, no. 8, pp. 1390–1399, σ Oct. 2009. 8(hR,i , τj , n) [9] S. Hur, T. Kim, D. J. Love, J. V. Krogmeier, T. A. Thomas, and A. Ghosh, ‘‘Millimeter wave beamforming for wireless backhaul and access in small 1 n o = − 2 < jhj A1 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j∗ kx[n]k2 (60) cell networks,’’ IEEE Trans. Commun., vol. 61, no. 10, pp. 4391–4403, σ Oct. 2013. 8(hI ,i , τj , n) [10] Y. Tsang, A. S. Y. Poon, and S. Addepalli, ‘‘Coding the beams: Improving 1 n o Beamforming training in mm Wave communication system,’’ in Proc. = − 2 < hj A1 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 (61) IEEE Global Commun. Conf., Dec. 2011, pp. 1–6. σ [11] R. J. Lopes and J. M. Brazio, ‘‘A geometry-based statistical model for 8(θrx,i , θtx,j , n) fast fading in millimeterwave communications,’’ in Proc. IEEE 45th 1 n o Veh. Technol. Conf. Countdown Wireless 21st Century, vol. 1, Jul. 1995, = 2 < h∗i hj A0 [n]1ij [n]γtx,i γ̇tx,j γ̇rx,i ∗ γrx,j ∗ kx[n]k2 (62) pp. 459–463. σ [12] H. Deng and A. Sayeed, ‘‘Mm-wave MIMO channel modeling and 8(hR,i , θtx,j , n) user localization using sparse beamspace signatures,’’ in Proc. 15th Int. 1 n o Workshop Signal Process. Adv. Wireless Commun. (SPAWC), Jun. 2014, = 2 < hj A0 [n]1ij [n]γtx,i γ̇tx,j γrx,i γrx,j ∗ kx[n]k2 (63) pp. 130–134. σ [13] Q. Li, G. Wu, and T. S. Rappaport, ‘‘Channel model for millimeter-wave 8(hI ,i , θtx,j , n) communications based on geometry statistics,’’ in Proc. IEEE Global 1 n o Commun. Conf. Workshops, Dec. 2014, pp. 427–432. = − 2 < jhj A0 [n]1ij [n]γtx,i γ̇tx,j γrx,i γrx,j ∗ kx[n]k2 (64) [14] A. Alkhateeb, O. El Ayach, G. Leus, and R. W. Heath, Jr., ‘‘Chan- σ nel estimation and hybrid precoding for millimeter wave cellular sys- 8(hR,i , θrx,j , n) tems,’’ IEEE J. Sel. Topics Signal Process., vol. 8, no. 5, pp. 831–846, 1 n o Oct. 2014. = 2 < hj A0 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γ̇rx,j kx[n]k2 (65) [15] M. Steinbauer, A. F. Molisch, and E. Bonek, ‘‘The double-directional σ radio channel,’’ IEEE Antennas Propag. Mag., vol. 43, no. 4, pp. 51–63, 8(hI ,i , θrx,j , n) Aug. 2001. 1 n o [16] Z. Abu-Shaban, X. Zhou, T. Abhayapala, G. Seco-Granados, and = − 2 < jhj A0 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γ̇rx,j kx[n]k2 (66) H. Wymeersch, ‘‘Error bounds for uplink and Downlink 3D localization σ in 5G millimeter wave systems,’’ IEEE Trans. Wireless Commun., vol. 17, 8(hI ,i , hR,j , n) no. 8, pp. 4939–4954, Aug. 2018. 1 n o [17] A. Shahmansoori, G. E. Garcia, G. Destino, G. Seco-Granados, and = − 2 < jA0 [n]1ij [n]γtx,i γtx,j ∗ γrx,i γrx,j ∗ kx[n]k2 . (67) H. Wymeersch, ‘‘Position and orientation estimation through millimeter- σ wave MIMO in 5G systems,’’ IEEE Trans. Wireless Commun., vol. 17, no. 3, pp. 1822–1835, Mar. 2017. REFERENCES [18] J. Bae, S. H. Lim, J. H. Yoo, and J. W. Choi, ‘‘New beam tracking technique [1] Z. Pi and F. Khan, ‘‘An introduction to millimeter-wave mobile broadband for millimeter wave-band communications,’’ 2017, arXiv:1702.00276. systems,’’ IEEE Commun. Mag., vol. 49, no. 6, pp. 101–107, Jun. 2011. [Online]. Available: https://arxiv.org/abs/1702.00276 [2] T. S. Rappaport, S. Sun, R. Mayzus, H. Zhao, Y. Azar, K. Wang, George [19] K. Gao, M. Cai, D. Nie, B. Hochwald, J. N. Laneman, H. Huang, and N. Wong, J. K. Schulz, M. Samimi, and F. Gutierrez, ‘‘Millimeter wave K. Liu, ‘‘Beampattern-based tracking for millimeter wave communication mobile communications for 5G cellular: It will work,’’ IEEE Access, vol. 1, systems,’’ in Proc. IEEE Global Commun. Conf., Dec. 2016, pp. 1–6. pp. 335–349, 2013. [20] R. Di Taranto, S. Muppirisetty, R. Raulefs, D. Slock, T. Svensson, and [3] A. L. Swindlehurst, E. Ayanoglu, P. Heydari, and F. Capolino, ‘‘Millimeter- H. Wymeersch, ‘‘Location-aware communications for 5G networks: How wave massive MIMO: The next wireless revolution,’’ IEEE Commun. location information can improve scalability, latency, and robustness of Mag., vol. 52, no. 9, pp. 56–62, Sep. 2014. 5G,’’ IEEE Signal Process. Mag., vol. 31, no. 6, pp. 102–112, Nov. 2014. 142336 VOLUME 7, 2019 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO [21] C. N. Barati, S. A. Hosseini, M. Mezzavilla, T. Korakis, S. S. Panwar, [45] M. Wax and T. Kailath, ‘‘Optimum localization of multiple sources by S. Rangan, and M. Zorzi, ‘‘Initial access in millimeter wave cellular passive arrays,’’ IEEE Trans. Acoust., Speech, Signal Process., vol. ASSP- systems,’’ IEEE Trans. Wireless Commun., vol. 15, no. 12, pp. 7926–7940, 31, no. 5, pp. 1210–1217, Oct. 1983. Dec. 2016. [46] M. Wax and T. Kailath, ‘‘Decentralized processing in sensor arrays,’’ [22] V. Desai, L. Krzymien, P. Sartori, W. Xiao, A. Soong, and A. Alkhateeb, IEEE Trans. Acoust., Speech, Signal Process., vol. ASSP-33, no. 5, ‘‘Initial beamforming for mm wave communications,’’ in Proc. 48th Asilo- pp. 1123–1129, Oct. 1985. mar Conf. Signals, Syst. Comput., Nov. 2014, pp. 1926–1930. [47] A. J. Weiss, ‘‘Direct position determination of narrowband radio frequency [23] H.-H. Lee and Y.-C. Ko, ‘‘Low Complexity Codebook-based beamform- transmitters,’’ IEEE Signal Process. Lett., vol. 11, no. 5, pp. 513–516, ing for MIMO-OFDM systems in millimeter-wave WPAN,’’ IEEE Trans. May 2004. Wireless Commun., vol. 10, no. 11, pp. 3607–3612, Nov. 2011. [48] X. Song, S. Haghighatshoar, and G. Caire, ‘‘A scalable and statisti- [24] Z. Xiao, T. He, P. Xia, and X.-G. Xia, ‘‘Hierarchical codebook design for cally robust beam alignment technique for mm-wave systems,’’ 2017, beamforming training in millimeter-wave communication,’’ IEEE Trans. arXiv:1708.09433. [Online]. Available: https://arxiv.org/abs/1708.09433 Wireless Commun., vol. 15, no. 5, pp. 3380–3392, May 2016. [49] D. E. Berraki, S. M. Armour, and A. Nix, ‘‘Application of compressive [25] J. Singh and S. Ramakrishna, ‘‘On the feasibility of codebook-based sensing in sparse spatial channel recovery for beamforming in mm Wave beamforming in millimeter wave systems with multiple antenna arrays,’’ outdoor systems,’’ in Proc. IEEE Wireless Commun. Netw. Conf. (WCNC), IEEE Trans. Wireless Commun., vol. 14, no. 5, pp. 2670–2683, May 2015. Apr. 2014, pp. 887–892. [26] M. Kokshoorn, H. Chen, P. Wang, Y. Li, and B. Vucetic, ‘‘Millimeter [50] A. Alkhateeb, G. Leus, and R. W. Heath, Jr., ‘‘Compressed sensing wave MIMO channel estimation using overlapped beam patterns and rate based multi-user millimeter wave systems: How many measurements adaptation,’’ IEEE Trans. Signal Process., vol. 65, no. 3, pp. 601–616, are needed,’’ in Proc. IEEE Int. Conf. Acoust., Speech Signal Process. Feb. 2017. (ICASSP), Apr. 2015, pp. 2909–2913. [27] J. Kim and A. F. Molisch, ‘‘Fast millimeter-wave beam training with [51] J. Choi, ‘‘Beam selection in mm-wave multiuser MIMO systems receive beamforming,’’ J. Commun. Netw., vol. 16, no. 5, pp. 512–522, using compressive sensing,’’ IEEE Trans. Commun., vol. 63, no. 8, Oct. 2014. pp. 2936–2947, Aug. 2015. [28] S. Sur, X. Zhang, P. Ramanathan, and R. Chandra, ‘‘BeamSpy: Enabling [52] K. Venugopal, A. Alkhateeb, N. G. Prelcic, and R. W. Heath, ‘‘Chan- robust 60 GHz links under blockage,’’ in Proc. 13th USENIX Symp. Netw. nel estimation for hybrid architecture based wideband millimeter wave Syst. Design Implement. (NSDI), 2016, pp. 193–206. systems,’’ IEEE J. Sel. Areas Commun., vol. 35, no. 9, pp. 1996–2009, [29] A. Zhou, X. Zhang, and H. Ma, ‘‘Beam-forecast: Facilitating mobile 60 Sep. 2017. GHz networks via model-driven beam steering,’’ in Proc. IEEE INFOCOM [53] J. Talvitie, M. Valkama, G. Destino, and H. Wymeersch, ‘‘Novel algorithms IEEE Conf. Comput. Commun., May 2017, pp. 1–9. for high-accuracy joint position and orientation estimation in 5G mm wave [30] D. Zhang, H. Chen, M. Shirvanimoghaddam, Y. Li, and B. Vucetic, ‘‘Train- systems,’’ in Proc. IEEE Globecom Workshops (GC Wkshps), Dec. 2017, ing beam sequence optimization for millimeter wave MIMO tracking pp. 1–7. systems,’’ in Proc. IEEE Int. Conf. Commun. (ICC), May 2018, pp. 1–6. [54] G. Destino and H. Wymeersch, ‘‘On the trade-off between positioning and [31] M. E. Rasekh, Z. Marzi, Y. Zhu, U. Madhow, and H. Zheng, ‘‘Noncoherent data rate for mm-wave communication,’’ in Proc. IEEE Int. Commun. Conf. mm wave path tracking,’’ in Proc. 18th Int. Workshop Mobile Comput. Syst. Workshops (ICC Workshops), May 2017, pp. 797–802. Appl., Feb. 2017, pp. 13–18. [55] R. J. Muirhead, Aspects Multivariate Statistical Theory. Hoboken, [32] H. S. Ghadikolaei, H. Ghauch, and C. Fischione, ‘‘Learning-based tracking NJ, USA: Wiley, 2005. of aoas and aods in mm wave networks,’’ in Proc. 2nd ACM Workshop Millim. Wave Netw. Sens. Syst., Oct. 2018, pp. 45–50. [33] N. Garcia, H. Wymeersch, E. G. Ström, and D. Slock, ‘‘Location-aided mm-wave channel estimation for vehicular communication,’’ in Proc. IEEE Int. Workshop Signal Process. Adv. Wireless Commun., Jul. 2016, pp. 1–5. GABRIEL E. GARCIA received the B.Sc. degree in [34] V. Va, X. Zhang, and R. W. Heath, Jr., ‘‘Beam switching for millimeter electronics and communication engineering from wave communication to support high speed trains,’’ in Proc. IEEE 82nd the Instituto Tecnológico y de Estudios Superiores Veh. Technol. Conf. (VTC Fall), Sep. 2015, pp. 1–5. de Monterrey, Querétaro, Mexico, in 2007, and [35] J. C. Aviles and A. Kouki, ‘‘Position-aided mm-wave beam training under NLOS conditions,’’ IEEE Access, vol. 4, pp. 8703–8714, 2016. the M.Sc. degree in communication, the Licentiate [36] G. C. Alexandropoulos, ‘‘Position aided beam alignment for mil- degree, and the Ph.D. degree in electrical engi- limeter wave backhaul systems with large phased arrays,’’ 2017, neering from Chalmers University of Technology, arXiv:1701.03291. [Online]. Available: https://arxiv.org/abs/1701.03291 Gothenburg, Sweden, in 2010, 2013, and 2019, [37] G. E. Garcia, G. Seco-Granados, E. Karipidis, and H. Wymeersch, ‘‘Trans- respectively. His research interests include cooper- mitter beam selection in millimeter-wave MIMO with in-band position- ative networks, robust radio frequency localization aiding,’’ 2017, arXiv:1705.05668. [Online]. Available: https://arxiv. and navigation, UWB, mm-wave, wireless sensor networks, GNSS, statisti- org/abs/1705.05668 cal inference, and sensor fusion. [38] A. Alkhateeb and R. W. Heath, Jr., ‘‘Frequency selective hybrid precoding for limited feedback millimeter wave systems,’’ IEEE Trans. Commun., vol. 64, no. 5, pp. 1801–1818, May 2016. [39] N. Celik, W. Kim, M. F. Demirkol, M. F. Iskander, and R. Emrick, ‘‘Implementation and experimental verification of hybrid smart-antenna beamforming algorithm,’’ IEEE Antennas Wireless Propag. Lett., vol. 5, NIL GARCIA (S’14–M’16) received the Telecom- no. 1, pp. 280–283, Dec. 2006. munications Engineer degree from the Polytechnic [40] R. W. Heath, Jr., N. González-Prelcic, S. Rangan, W. Roh, and University of Catalonia, Barcelona, Spain, in 2008, A. M. Sayeed, ‘‘An overview of signal processing techniques for millimeter and the Ph.D. degrees in electrical engineering wave MIMO systems,’’ IEEE J. Sel. Topics Signal Process., vol. 10, no. 3, from the New Jersey Institute of Technology, pp. 436–453, Apr. 2016. [41] IEEE Standard for High Data Rate Wireless Multi-Media Networks, Stan- Newark, NJ, USA, and the National Polytechnic dard IEEE Std 802.15.3-2016, 2016. Institute of Toulouse, Toulouse, France, in 2015. [42] S. M. Kay, Fundamentals Statistical Signal Processing: Estimation The- In 2009, he was an Engineer with the Centre ory. New York, NY, USA: Prentice-Hall, 2010. National d’Etudes Spatiales. He had internships [43] H. Van Trees, Detection, Estimation, Modulation Theory. Hoboken, in CNES and NASA, in 2008 and 2009. He is NJ, USA: Wiley, 2001. currently a Postdoctoral Researcher of communication systems with the [44] M. Wax, T.-J. Shan, and T. Kailath, ‘‘Location and the spectral den- Department of Electrical Engineering, Chalmers University of Technology, sity estimation of multiple sources,’’ DTIC, Fort Belvoir, VA, USA, Gothenburg, Sweden. His research interests include the areas of localization, Tech. Rep. AFOSR-TR-83-0323, 1982. intelligent transportation systems, and 5G. VOLUME 7, 2019 142337 G. E. Garcia et al.: Fast in-Band Position-Aided Beam Selection in Millimeter-Wave MIMO GONZALO SECO-GRANADOS (S’97–M’02– HENK WYMEERSCH (S’01–M’05) received the SM’08) received the Ph.D. degree in telecom- Ph.D. degree in electrical engineering/applied sci- munications engineering from the Universitat ences from Ghent University, Belgium, in 2005. Politècnica de Catalunya, Spain, in 2000, and the He was a Postdoctoral Researcher with the Lab- M.B.A. degree from the IESE Business School, oratory for Information and Decision Systems, Spain, in 2002. From 2002 to 2005, he was a Massachusetts Institute of Technology, from member of the European Space Agency, where he 2005 to 2009. He is currently a Professor of was involved in the design of the Galileo system. communication systems with the Department of In 2015, he was a Fulbright Visiting Professor with Electrical Engineering, Chalmers University of the University of California at Irvine, Irvine, CA, Technology, Sweden. His current research inter- USA. Since 2006, he has been with the Department of Telecommunications, ests include cooperative systems and intelligent transportation. He has served Universitat Autònoma de Barcelona, where he has been the Vice Dean of the as an Associate Editor for the IEEE COMMUNICATIONS LETTERS, from 2009 to Engineering School, since 2011, and is currently a Professor. His research 2013, and the IEEE TRANSACTIONS ON COMMUNICATIONS, from 2016 to 2018. interests include satellite and terrestrial localization systems. Since 2018, He has been serving as an Associate Editor for the IEEE TRANSACTIONS ON he has been serving as a member for the Sensor Array and Multichannel WIRELESS COMMUNICATIONS, since 2013. Technical Committee of the IEEE Signal Processing Society. He was a recipient of the 2013 ICREA Academia Award. ELEFTHERIOS KARIPIDIS (S’05–M’09) rec- eived the Diploma degree in electrical and com- puter engineering from the Aristotle University of Thessaloniki, Greece, in 2001, the M.Sc. degree in communications engineering from the Techni- cal University of Munich, Germany, in 2003, and the Ph.D. degree in electronic and computer engi- neering from the Technical University of Crete, Chania, Greece, in 2008. From 2008 to 2013, he was with the Communication Systems Division, Department of Electrical Engineering, Linköping University, Sweden. Since 2013, he has been with Ericsson Research, Stockholm, Sweden, where he is currently a Senior Researcher. He is involved in the standardization of 5G New Radio in 3GPP, since Release 15, with a focus on multiple-input multiple-output and reference signals. From 2016 to 2018, he was a member of the Signal Processing for Communications and Networking Technical Committee of the IEEE Signal Processing Society. 142338 VOLUME 7, 2019