{'fraction_non_alphanumeric': 0.03500766336909572, 'fraction_numerical': 0.00884770795597046, 'mean_word_length': 4.440401743414819, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Millimeter-Wave Downlink Positioning with a Single-Antenna Receiver

The paper addresses the problem of determining the unknown position of a mobile station for a mmWave MISO system. This setup is motivated by the fact that massive arrays will be initially implemented only on 5G base stations, likely leaving mobile stations with one antenna. The maximum likelihood solution to this problem is devised based on the time of flight and angle of departure of received downlink signals. While positioning in the uplink would rely on angle of arrival, it presents scalability limitations that are avoided in the downlink. To circumvent the multidimensional optimization of the optimal joint estimator, we propose two novel approaches amenable to practical implementation thanks to their reduced complexity. A thorough analysis, which includes the derivation of relevant Cram\'er-Rao lower bounds, shows that it is possible to achieve quasi-optimal performance even in presence of few transmissions, low SNRs, and multipath propagation effects.


I. INTRODUCTION
Millimeter-wave (mmWave) and massive multiple-input multiple-output (MIMO) technologies are currently regarded as strong candidates for next-generation wireless systems, including vehicular and 5G cellular networks. Indeed, such technologies not only are key enabler of high data rates and spectral efficiency [1]- [5], but also they are promising tools for precise localization thanks to their high temporal resolution and high directivity [6]- [10].
The theoretical localization performance achievable using mmWave MIMO have been recently investigated in [11]- [13]. In [13], the Cramér-Rao Lower bound (CRLB) on the position and rotation angle estimates obtained using mmWave from a single transmitter has been derived.
Furthermore, a novel position and rotation estimation algorithm based on compressed sensing that attains the CRLB for average to high signal-to-noise ratio (SNR) is proposed. In [11], fundamental limits of position and orientation estimation for uplink and downlink in 3D-space were presented. Authors in [12] have shown that non-line-of-sight (NLOS) components can also be exploited to gain additional information for position and orientation estimation.
A few papers have proposed more sophisticated localization schemes, trying to take advantage of the peculiarities of mmWave and (massive) MIMO technologies. In [14], a 3D indoor positioning scheme based on hybrid received signal strength (RSS) and Angle-Of-Arrival (AOA), which employs only a single base station (BS) has been presented. A hypothesis testing localization approach is proposed in [15] exploiting the concept of channel sparsity. A low-complexity AOAbased approach with signal subspace reconstruction is devised in [16] to localize incoherently distributed sources. An extended Kalman filter (EKF) tracking algorithm that jointly exploits AOA and time of flight (TOF) from uplink reference signals has been proposed in [17]. In [18], a direct position estimation algorithm is derived. It is based on a compressed sensing framework that exploits some channel properties to identify NLOS signal paths, leading to superior performance compared to other approaches. Authors in [19] addressed the problem of positioning based on joint TOF, Angle-of-Departure (AOD), and AOA estimation and investigated the impact of errors in delays and phase shifters. A hybrid time-difference-of-arrival (TDOA), AOA, and AOD localization scheme is presented in [20] based on linearization of a set of local constraints, while in [21] positioning is addressed using a Gaussian process regressor based on a fingerprinting technique operating on a vector of RSS measurements.
It is worth noticing that almost all the aforementioned approaches heavily rely on the adoption of (possibly large) multi-antenna systems at both transmitter and receiver sides. Although this setup allows for efficient channel estimation by employing high directional beamforming to compensate severe path loss [22], it requires that commercial massive MIMO implementations for mobile stations (MSs) (e.g., smartphones) will be available in the very near term [23].
However, as recent research showed, it is reasonable to expect that MSs will likely have one (or very few) antennas, while massive arrays will be initially implemented only at the BSs side [24], [25].
In this work, we address the problem of estimating the unknown MS position under a multipleinput single-output (MISO) system setup. The processing is done exclusively on-board at the MS by exploiting the known signals transmitted by a single BS, without any increase in the bandwidth consumption, and requiring an antenna array only on the BS (as opposed to typical MIMO scenarios). While conventional localization schemes mainly focus on AOA estimation, the proposed approach aims at exploiting the AOD of received downlink signals, which can be estimated using a single ominidirectional antenna, thus avoiding the high computational cost required by large arrays. We show that mmWave and MISO are enabling technologies for designing accurate positioning systems that can be readily implemented in the near future.
More specifically, the paper provides two kinds of contributions. First, we thoroughly analyze the problem from a theoretical perspective, deriving the exact solution to the Maximum Likelihood (ML) estimation problem and complementing the CRLB-analysis available in the literature [11] with a precise assessment of the achievable performance under the considered MISO setup.
As a second contribution, we design two novel and practical estimators with reduced complexity.
In particular: • a first estimator based on an unstructured transformation of the likelihood function is proposed, which provides an approximate solution to the exact ML problem while avoiding the burden of multidimensional optimization methods; • a second estimation approach based on the method of moments is devised for the case of sufficient amount of received data, which results in a closed-form estimator of the TOF and hence further reduces the complexity to a single one-dimensional search.
The numerical analysis in a realistic MISO scenario demonstrates that the proposed estimators can achieve almost the same performance of the exact ML estimator and are able to cope with the different operating conditions at play in typical mmWave channels.
The remaining of the paper is organized as follows. In Sec. II we introduce the system model and describe the reference scenario. In Sec. III we formulate the ML estimation problem and illustrate in details the design and derivation of the proposed low-complexity estimators. Then, in Sec. IV, we derive the fundamental lower bounds on the estimation uncertainty under the considered MISO setup. In Sec. V we analyze the performance, also in comparison with the uplink channel, by means of Monte Carlo simulations in different realistic scenarios. We conclude the paper in Sec. VI.

II. SYSTEM MODEL
We consider, as a reference scenario, a MISO system with a BS equipped with N BS antennas and a MS equipped with a single antenna operating at a carrier frequency f c (corresponding to wavelength λ c ) and bandwidth B. Without loss of generality, the location of the BS is taken in the origin, while we denote by p = [p x p y ] T the unknown position of the MS.

A. Transmitter Model
We consider the transmission of orthogonal frequency division multiplexing (OFDM) signals, where the BS, implementing a hybrid analog/digital precoder at the transmitting side, communicates with the MS. Particularly, we assume that G signals are transmitted sequentially, where the g-th transmission comprises M simultaneously transmitted symbols for each subcarrier n = 0, . . . , N − 1, i.e.,  The transmitted signal over subcarrier n at time g can be expressed as F g [n]x g [n], with F g [n] ∈ C N BS ×M denoting the beamforming matrix applied at the transmitting side. To lower the hardware complexity, in this work we adopt a hybrid beamforming architecture. In particular, assuming that M RF BS RF chains are available at the BS, the beamforming matrix F g [n] can be expressed as where F RF ∈ C N BS ×M RF BS is implemented using analog phase shifters with entries of the form e jφm,n , where {φ m,n } are given phases, and F g BB [n] ∈ C M RF BS ×M is the digital beamformer.
Furthermore, we impose a total power constraint F RF F g BB [n] F = 1 [26]. Considering the angular sparsity of the mmWave channels, one usually needs less beams than antenna elements, i.e., M ≤ N BS [27], [28]. It should be noticed that our work does not assume any specific choice of the beamformers F g [n], hence the derived expressions will be completely general.

B. Channel Model
We assume that a direct Line-Of-Sight (LOS) link exists between the BS and the MS, and that additional NLOS paths due to local scatterers or reflectors may also be present. The different position-related parameters of the channel are depicted in Fig. 1. These parameters include θ k and τ k , denoting the AOD and TOF related to the k-th path, respectively. In the following, k = 0 corresponds to the LOS link and k > 0 denotes the NLOS paths. Considering P + 1 paths and a constant channel during the transmission of the G signals, the 1 × N BS complex channel vector associated with subcarrier n can be expressed as where we have exploited the fact that λ n = c/ n N T S + f c ≈ λ c ∀n (with c denoting the speed of light), i.e., the typical narrowband condition. Under this model, the array response matrix is given by and where α p = h p / √ ρ p , with ρ p the path loss and h p denoting the complex channel gain of the p-th path, respectively. The structure of the antenna steering vectors a BS (θ p ) ∈ C N BS ×1 depends on the specific geometry of the considered array. Without loss of generality, in the following we consider a Uniform Linear Array (ULA) without mutual antenna coupling and with isotropic antennas, whose steering vector can be expressed as where d = λc 2 denotes the ULA interelement spacing.

C. Received Signal Model
The received signal related to the n-th subcarrier and transmission g, after CP removal and Fast Fourier Transform (FFT), is given by where ν g [n] is the additive circularly complex Gaussian noise with zero mean and variance σ 2 .
The ultimate goal of this work is to estimate the unknown MS position p from the set of all received signals To this aim, we focus on the estimation of the LOS position-related parameters θ 0 and τ 0 . Based on such estimates, the unknown MS position p can be determined by recalling that the TOF defines a circle centered in the BS and with radius d 0 = cτ 0 from the MS, according to while the AOD is related to the unknown MS position as where the function atan2(y, x) is the four-quadrant inverse tangent. Solving (9)-(10) and replacing the actual values with the estimated ones readily provides an estimate of the MS position according top Fundamental lower bounds on the estimation uncertainty will be derived to evaluate the performance.

III. ANGLE OF DEPARTURE (AOD) AND TIME OF FLIGHT (TOF) ESTIMATION
In this section, we derive novel algorithms for the estimation of the LOS channel parameters θ 0 and τ 0 in presence of the nuisance parameters α 0 and σ 2 .

A. Joint Maximum Likelihood Estimation
To formulate the estimation problem, we exploit the fact that, under typical mmWave assumptions, all the paths are resolvable in either the time or space domains, and the multipath components are likely uncorrelated with the LOS [11]. Since we are interested in estimating the sole LOS position-related parameters, NLOS paths can be omitted from (3) and the multipath parameter estimation can be then reduced to a problem of single-path estimation, that is, the channel vector given in (3) can be re-defined as where only LOS path is considered from now on. To ease the notation, we introduce α be statistically characterized as whereh and all the parameters are treated as deterministic unknowns, except the transmitted symbols x g [n] and the beamforming matrix F g [n], which are assumed known to the receiver. More precisely, the whole set of unknowns in Y can be arranged as where θ and τ represent the sole parameters of interest, while ψ = [σ 2 α] T denotes the vector of nuisance parameters. The ML estimator of θ and τ is given by where L(θ, τ, ψ) def = log f (Y |θ, τ, ψ) and f (·) denotes the probability density function of the observations Y given ψ and both θ and τ . From (15) it follows that where we have denoted by . . .
the g-th column of the observation matrix Y , and We start by observing that the resolution of the ML estimation problem is invariant to the knowledge of σ 2 ; in fact, if such a parameter were unknown, it could be estimated asσ 2 = 1 N G G g=1 y g − √ N BS αw g 2 , leading to the same value of the compressed likelihood as for whereL(θ, τ, α) is the compressed negative log-likelihood function, and the ML estimator of θ and τ reduces to It is a simple matter to observe that the minimization of (19) with respect to α ∈ C is solved bŷ Substituting this maximizing value back in (19) leads tõ where we highlight the dependency of w on both τ and θ. As it can be noticed, the function in (22) cannot be expressed in terms of any projection matrix; furthermore, it is highly non-linear in both the unknown θ and τ and does not admit a closed-form solution. A possible approach to solve the estimation problem could be based on the adoption of a numerical search algorithm 1 ; more precisely, a two-dimensional grid search can be used for a direct minimization ofL(θ, τ ).
To overcome the burden of a multidimensional minimization, in the following we derive two novel suboptimal methods to estimate the TOF τ . In so doing, we can put such an estimated value back in (22) and then solve for the unknown θ in the ML problem by resorting to a simple one-dimensional search.
It is worth remarking that NLOS paths are not considered (nor exploited) at the design stage.
Although their number is limited thanks to the sparsity of the mmWave channel, in the simulation analysis conducted in Sec. V, we will investigate the sensibility of the proposed algorithms to multipath effects according to the LOS-to-Multipath Ratio (LMR), the latter defined as the ratio between the power of the LOS component and the sum of powers of NLOS multipath components.

B. Unstructured ML-based TOF Estimation
In this subsection, we propose a novel method for the estimation of the TOF τ . For the sake of exposition, we initially consider the case of single transmission, that is, G = 1. Stacking the observations y[n] from (7), we obtain where 1 Iterative search algorithms like the steepest descent algorithm or the Gauss-Newton method cannot be easily applied since the objective function given in (22) exhibits several local minima.
To formulate the estimation problem, we make use of an unstructured model for the array steering vector instead of the one parameterized by the AOD, i.e., we introduce the generic vector b = √ N BS αa * BS (θ). Under this model, (23) can be equivalently rewritten as As it can be noticed, the above expression is no longer an explicit function of θ, but depends only on the TOF τ . Starting from this new model and generalizing to arbitrary values of G ≥ 1, a ML-based estimator of τ , referred to as Unstructured ML (UML), can be derived aŝ whereX g , g = 1, . . . , G, are known matrices which depend on the transmitted sequences and b ∈ C N BS ×1 is treated as an unknown nuisance vector. It is not difficult to show that the inner minimization of (27) whereX G def = G g=1 (X g ) HX g and the existence ofX −1 G only requires N ≥ N BS . Substituting this maximizing value back in (27) finally yieldŝ which can be solved by resorting to a simple one-dimensional search over the space of τ .
Putting the above estimateτ UML back in (22) and solving for the unknown θ readily provides an approximate solution to the original ML problem, but at the reduced cost of two one-dimensional searches.

C. Moment-based TOF Estimation
In this section, we further investigate the problem of estimating the unknown τ when a sufficient number of transmissions G is available. We start by observing that the elements in (7) can be equivalently re-arranged as We can now express the collected observations as If we assume that G ≥ N BS , the known matrices X[i] have full row-rank, so that the following transformation can be applied where X + i = X H i (X i X H i ) −1 denotes the Moore-Penrose right pseudo-inverse matrix. It can be observed that these new transformed observations are ruled bỹ where It is worth noting that, differently from (33), the elements of each vectorỹ T i are now correlated. Starting from these new observables, we can further define where each z i is obtained by multiplying two consecutiveỹ T i , with overlap. This transformation reduces the number of available observations only by one (to N − 1).
For the new set of data z = [z 0 · · · z N −1 ] T , by exploiting the independence of the (transformed) noise vectors, it follows (hereafter we omit the dependency on θ for simplicity) Remarkably, this new expression does not depend on the unknown AOD θ, but it is solely parameterized as function of the TOF τ . Therefore, one can build a method-of-moment (MM) estimator from this expressionτ which results in a closed-form estimator of τ . By analyzing the transformed observables z i in (36), we can derive a useful analogy with the classical frequency estimation theory. Similarly to the Kay's method presented in [29], the approach proposed in (38) exploits a one-lag sample autocorrelation function to provide a suboptimal estimator of τ . Nonetheless, even though this method could provide good estimation performance, an additional improvement can be obtained by considering higher lags in the sample autocorrelation function, as shown in [30]. Based on this result, we derive a more general multi-lag extension of the estimator in (38) aŝ with L < N denoting the number of different lags adopted and q(L) = L

D. Complexity Analysis
Asymptotically speaking, we observe that the complexity in performing the two-dimensional minimization in (22)  The average runtimes of the estimators normalized by the average runtime of the MM are given in Fig. 2. As it could be expected, the ML 2D requires by far the longest runtime due to the multidimensional search required for solving (22). On the other hand, the MM has the smallest

A. FIM Derivation for Channel Parameters
Let the noise-free observation at subcarrier n, transmission g be where s g [n] = F g [n]x g [n], α = h/ √ ρ def = r exp(jφ) with r and φ modulus and phase of the complex amplitude α, respectively. Let γ ∈ R 4×1 denotes the vector of the unknown channel where we assume without loss of generality that the noise variance σ 2 is known 2 . Definingγ as an unbiased estimator of γ, it is well-known that the mean squared error (MSE) is lower bounded as [31] where E Y |γ [·] denotes the expectation parameterized as function of the unknown vector γ and is the gradient of m with respect to γ given by construct a diagonal matrix with its entries. We can show that for the matrix J γ to be nonsingular when G = 1, we need at least two subcarriers and send different pilot sequences on each subcarrier. Similarly, when N = 1, we need at least two transmissions with different pilot sequences. Further details are found in the Appendix.

B. FIM Derivation for Position
In this section, we derive the FIM in the position domain by applying a transformation of variables from the vector of channel parameters γ to the vector of location parameters The FIM of η is obtained by means of the 4 × 4 transformation matrix T as The entries of the matrix T can be obtained from the relations between the parameters in γ and η, as expressed in (9)-(10). More precisely, we have , ∂θ/∂p y = 1/p x 1 + (p y /p x ) 2 , and the rest of the entries in T are zero.

C. Bounds on Position Estimation Error
The position error bound (PEB) can be readily derived by inverting the FIM J η given in (44), then adding the diagonal entries of the lower right 2 × 2 sub-matrix, and taking the square root where the operator [·] j,j denotes the selection of the j-th diagonal entry of J −1 η .

V. SIMULATION MODEL AND RESULTS
In this section, we present simulation results to evaluate the performance of the proposed estimators in comparison with the two-dimensional ML, as well as the theoretical bounds derived based on the FIM analysis conducted in Sec. IV.

A. Reference scenario
We consider a scenario representative of outdoor localization in a small open area with maximum distance between BS and MS of 100 meters. The BS is located at the origin of the considered Cartesian reference system and is equipped with N BS = 10 antennas. As concerns the transmitted signal, we assume a carrier frequency f c = 60 GHz, a bandwidth B = 40 MHz, a transmitted power P t = 1 W, and a number of subcarriers N = 20 [33]. The number of simultaneously transmitted beams is M = 1 and we vary the number of sequentially transmitted signals G between 1 and 20, respectively.
The channel path loss ρ is computed according to [34], [35]. For the specific case of the LOS link, we obtain where µ 2 (d 0 ) denotes the atmospheric attenuation at a distance d 0 and the last term is the free space path loss at a distance d 0 . Following [1], the atmospheric attenuation µ 2 (d 0 ) is set to 16 dB/Km. As to the complex channel gain, it can be expressed in terms of h = ae jϕ with a = √ P t the amplitude and ϕ the related phase, respectively.
To complete the analysis, we show the performance achievable in the uplink channel and compare them with the ones obtained in the downlink. Notice that, in the uplink case, the model of the received signal is different from the one provided in (7) since an antenna array should be considered at the receiver side. As a result, the localization will be based on the estimation of the AOA, as typical in many existing approaches, while we recall that the present contribution focuses on leveraging AOD information. Therefore, in the following we will consider the proper modified expressions for the theoretical bounds, as derived in the literature [11].
As anticipated in Sec. III-A, we also investigate the performance of the proposed estimators in presence of multipath propagation. Notice that, in this case, the estimation performance are evaluated in a simulation environment that is not matched to the design assumption of the proposed algorithms. More precisely, it is assumed that, in addition to the direct LOS link, two different NLOS paths are present at the receiver side. Assuming that only one dominant reflector is present in each NLOS path [35], we can compute the path loss ρ k for the k-th NLOS link with path length d k according to where P 0 (d k ) = (γ r d k ) 2 e −γrd k denotes the Poisson distribution of the environment geometry with density γ r , and k = 1, 2. According to [35], we consider a density γ r = 1/7 and set the average reflection loss for the first-order reflection σ 2 0 to 10 dB with the root-mean-square (RMS) deviation equal to 4 dB. To analyze the sensibility of the proposed estimators to multipath effects, we consider the following definition of LMR: where P LOS is the power associated to the LOS path, while P k NLOS is the power of the k-th multipath component.
The elements of the analog beamformers F RF are generated as uniform random values on the unit circle. As concerns the sequencesx g [n] = F g BB [n]x g [n], they are computed as complex exponential terms e jφn,g having random phases uniformly distributed in [0, 2π) along different subcarriers n and different transmissions g, respectively. Finally, we define the SNR in dB as SNR def = 10 log 10 P t ρN 0 B where log 10 (·) denotes the base-10 logarithm and N 0 B is the receiver noise figure, i.e., N 0 B = k B T 0 B, k B being the Boltzmann constant and T 0 the standard thermal noise temperature.
We consider the Root Mean Squared Error (RMSE) as metric to assess the algorithms performance, estimated based on 1000 Monte Carlo trials.

B. AOD, TOF and Position Estimation in LOS
In this section, we assess the performance of the proposed algorithms assuming only the LOS component is present.
In Fig. 4   Starting from a sufficient number of transmissions G = 10 -which we recall is the limit condition for defining the right pseudoinverse X + i required in (34) -we can observe that the performance of the MM estimator are worse than that of the UML, but still acceptable in terms of achieved accuracy. As the solid (magenta) curves show, the RMSE ofd exhibits a small gap with respect to the theoretical lower bound, which however starts to decrease as more transmissions G are available, thanks to an increasingly accurate estimation of the first-order moment in (37).
On the other hand, the RMSE ofθ approaches the theoretical bounds for G ≥ 15. As the bottom plot in Fig. 4 shows, this results in an overall position error which is always below 60 cm and tends to decrease as G increases, achieving performance very close to the one provided by the UML, but at the lower cost of a single one-dimensional search.
For the implementation of the MM algorithm, we compared the one-lag based estimator in (38) with the multi-lag extension in (39), assuming a number of lags L = 2. We observed that both estimators exhibit almost the same performance in the considered scenario. Interestingly, the proposed UML estimator performs well even for very low values of the received SNR, which is a typical operating condition in mmWave systems before beamforming stage. On the other hand, it should be noticed that the UML attains the theoretical bounds also in the downlink channel, starting from values of SNR of about 10 dB.

C. AOD, TOF and Position Estimation in LOS + NLOS
In this section, we evaluate the algorithms performance assuming that, in addition to the direct LOS path, two NLOS paths due to multipath propagation are also present.
In Fig. 6 we report the RMSEs of d, θ and p as function of different levels of LMR for G = 10 and SNR = 15 dB. As it could be expected, the obtained performance are slightly worse than that in LOS-only (depicted as dashed curves for reference), especially for non-negligible levels  The localization capability of the MM algorithm is also interesting, at least for non-severe multipath conditions, as confirmed by the solid (magenta) curves. These results show that the proposed algorithms are effective also in presence of multipath propagation effects.

VI. CONCLUSION
We have addressed the problem of determining the unknown MS position under a mmWave MISO system setup. Our solution is based on the ML approach and exploits the AOD of received downlink signals, which can be conveniently estimated using a single receive antenna, thus providing an efficient way for locating a receiver while avoiding the high computational cost required by large arrays. We have performed a thorough theoretical analysis, providing the exact solution to the ML estimation problem and deriving the fundamental lower bounds on the estimation uncertainty for both channel and position parameters. To circumvent the need for multidimensional optimization to compute the joint ML estimator, we proposed two novel approaches amenable to practical implementation thanks to their reduced complexity.
The performance assessment demonstrated that different accuracy/complexity trade-offs exist; however, remarkably, it is possible to achieve almost the same performance of the exact ML estimator, at a fraction of its computational complexity, even in presence of few transmissions, low SNRs, and multipath propagation effects.
where S has as columns the N pilots s[n]. The FIM is then given by (up to irrelevant constants) From the Cauchy-Schwarz inequality for complex numbers, it then follows that the FIM is singular if and only if ζ and ξ are parallel, i.e., there exists a u ∈ C so that ξ = uζ. It then follows immediately that: • when N = 1, ζ and ξ become scalars, which are necessarily parallel and thus J γ is singular; • when N > 1, a necessary and sufficient condition for a non-singular J γ is that the columns of S are not parallel.
Thus, a necessary and sufficient condition for a non-singular FIM with a single transmission (G = 1) is that we use at least N = 2 subcarriers and that the pilots across those subcarriers are different (non parallel). It can similarly be shown that when N = 1, we must use at least two transmissions with different pilots.