1

Optimal Beam Sweeping and Communication
in Mobile Millimeter-Wave Networks

arXiv:1801.09306v1 [] 28 Jan 2018

Nicolò Michelusi, Muddassar Hussain

Abstract
Millimeter-wave (mm-wave) communications incur a high beam alignment cost in mobile scenarios
such as vehicular networks. Therefore, an efficient beam alignment mechanism is required to mitigate
the resulting overhead. In this paper, a one-dimensional mobility model is proposed where a mobile
user (MU), such as a vehicle, moves along a straight road with time-varying and random speed, and
communicates with base stations (BSs) located on the roadside over the mm-wave band. To compensate
for location uncertainty, the BS widens its transmission beam and, when a critical beamwidth is achieved,
it performs beam-sweeping to refine the MU position estimate, followed by data communication over
a narrow beam. The average rate and average transmission power are computed in closed form and the
optimal beamwidth for communication, number of sweeping beams, and transmission power allocation
are derived so as to maximize the average rate under an average power constraint. Structural properties
of the optimal design are proved, and a bisection algorithm to determine the optimal sweeping –
communication parameters is designed. It is shown numerically that an adaptation of the IEEE 802.11ad
standard to the proposed model exhibits up to 90% degradation in spectral efficiency compared to the
proposed scheme.

I. I NTRODUCTION
Millimeter-wave (mm-wave) technology has emerged as a promising solution to enable multiGbps communication, thanks to the abundant bandwidth available [1]. Mm-wave will be key
to supporting autonomous transportation systems by allowing vehicles to extend their sensing
range and make more informed decisions by exchanging rich sensory information [2]. It will also
enable a wide range of infotainment services such as digital maps, cloud computing, ultra-high
definition video streaming, etc. However, signal propagation at these frequencies poses several
N. Michelusi and M. Hussain are with the School of Electrical and Computer Engineering at Purdue University. Email:
{michelus,hussai13}@purdue.edu.
This research has been funded by the National Science Foundation under grant CNS-1642982.

January 30, 2018

DRAFT

2

challenges to the design of future communication systems supporting high throughput and high
mobility, such as high isotropic path loss and sensitivity to blockages [3]. Mm-wave systems
are expected to leverage narrow-beam communications to counteract the propagation loss [4] by
using large antenna arrays at both base stations (BSs) and mobile users (MUs).
However, sharp beams are susceptible to beam mis-alignment due to mobility or blockage,
necessitating frequent re-alignment. This task can be challenging, especially in mobile scenarios.
The beam alignment protocol may consume time, frequency, and energy resources, thus potentially offsetting the benefits of mm-wave directionality. Therefore, it is imperative to design
schemes to mitigate its overhead.
In this paper, we investigate the trade-off between beam alignment and data communication in
mobile mm-wave networks. We propose a beam-sweeping – data communication protocol that
accounts for the uncertainty on the location and speed of the MU and for the temporal overhead
of beam-sweeping. Specifically, the BS associated with the MU widens its transmission beam to
compensate for the increasing uncertainty on the MU location and, when a critical beamwidth is
achieved, it performs beam-sweeping to refine the MU’s position estimate and achieve a narrow
communication beam. We compute the performance in closed-form, and investigate the design of
the optimal beamwidth for communication, number of sweeping beams, and transmission power
so as to maximize the average rate under average power constraint. We find structural properties
and propose a bisection method to determine the optimal design. We show numerically that
an adaptation of IEEE 802.11ad to our model exhibits a performance degradation up to 90%
compared to our design.
Beam alignment in mm-wave has been a subject of intensive research due to its importance in
mm-wave communication systems. The research in this area can be categorized into beamsweeping [5]–[8]; AoA/AoD estimation [9], [10]; and data-assisted schemes [2], [11]–[13].
Beam-sweeping based schemes require scanning of regions of uncertainty of AoA/AoD. The
simplest and yet most popular form of beam-sweeping is the so-called exhaustive search [5],
which sequentially scans through all possible beam pairs from the BS and MU codebooks and
selects the one with maximum signal power. This approach has been adopted in existing mmwave standards including IEEE 802.15.3c [14] and IEEE 802.11ad [15]. The other popular
scheme is a hierarchical form of scanning called iterative search [6], where beam-sweeping is
first performed using wider beams followed by refinement with narrow beams. In our previous
work [8], we derived an energy-efficient scheme termed fractional search, which minimizes the

January 30, 2018

DRAFT

3

Fig. 1: System model.

energy consumption subject to a rate constraint: in each slot, the BS adaptively scans a fraction
of the uncertainty region of the AoD, function of the slot index, rate requirement, probabilities
of false-alarm and mis-detection, bandwidth, path loss, and noise power spectral density.
AoA/AoD estimation aims to reduce the number of measurements required by beam-sweeping
by leveraging the sparsity of mm-wave channels, e.g., via compressive sensing as in [9]. The
paper [10] derived an approximate maximum likelihood estimator for the channel by directly
exploiting the structure of the mm-wave channel. Data-aided schemes utilize information from
radar [11], lower frequencies [12], or positional information [2], [13] to reduce the cost of beamsweeping. Based on this idea, the authors of [2] proposed a beamwidth optimization algorithm
that maximizes the data rate for non-overlapping beams. In contrast to [2], we propose an
analytical framework for the joint optimization of beamwidth, communication power and beamsweeping to maximize the communication performance. To the best of our knowledge, we are
the first to propose an analytical framework for the optimization of the beam-sweeping and
communication parameters in mobile mm-wave networks.
The paper is organized as follows: in Sec. II, we present the system model and optimization
problem; in Sec. III, we present the analysis, followed by numerical results in Sec. IV; finally,
in Sec. V, we conclude with some remarks.

January 30, 2018

DRAFT

4

II. S YSTEM M ODEL
We consider a dense cell deployment, as depicted in Fig. 1. The MU is associated with its
closest BS, at distance d. We assume that the BS points its beam perpendicularly to the motion of
the MU (a good approximation in dense cell deployments). A macro-cell unit controls functions
such as handover among cells. The time-scale of this task is larger than the beam-sweeping –
data communication cycle, and thus we neglect it. We neglect the additional overhead due to
channel estimation, Doppler correction, and the impact of beamwidth on Doppler spread (see
[16]).
A. User mobility model
The MU moves along a line (e.g., a vehicle along a road). Let (pt , vt ) ∈ R2 be its position and
speed at time t. We assume that vt ∈ [vmin , vmax ], where vmin < vmax (possibly, negative), and
we let vdrift = (vmin + vmax )/2 be the drift velocity and φ , vmax − vmin be the speed uncertainty.
vt is time-varying and random, with arbitrary distribution in [vmin , vmax ]. The speed parameters
vdrift , φ are assumed to be known, and can be estimated from GPS information collected at
the macro-cell (e.g., via lower frequency dedicated short range communication channels [17]).
Herein, we assume that vdrift = 0, since a known non-zero drift can be incorporated by appropriate
beam steering. Thus, it follows that vt ∈ [−φ/2, φ/2] and, given p0 at a reference time 0,


Z t
φt
φt
.
pt = p0 +
vτ dτ ∈ p0 − , p0 +
2
2
0

(1)

In this paper, the uncertainty on the location of the MU at time t is denoted by the uncertainty interval Ut ≡[p̂t −ut /2, p̂t +ut /2], where p̂t is the median estimated position and ut is the
uncertainty width, so that pt ∈ Ut . From the mobility model (1), if no beam-sweeping is done
in the time interval [t, τ ], the uncertainty width augments at rate φ, i.e.,
uτ = ut + φ(τ − t), τ ≥ t,

(2)

and is reduced via beam-sweeping, as discussed in Sec. II-B.
The communication between BS and MU follows a beam-sweeping – data communication
cycle of duration T . We now describe the entire cycle, starting from the reference time t=0.

January 30, 2018

DRAFT

5

B. Beam Sweeping
When, at the reference time t = 0, the uncertainty width reaches a critical value u0 = uth , the
BS currently associated with the MU sweeps the entire uncertainty interval U0 using η ≥ 2, η ∈ N
beams, transmitted sequentially over η microslots, each of duration δS . During this interval, the
uncertainty width increases over time due to MU mobility. In order to compensate for it, the
BS scans wider regions over successive microslots, as detailed below. Thus, we let ωi be the
beamwidth of the ith beam, where i = 1, 2, . . . , η.
At the end of the beam-sweeping interval of duration ηδS , the MU processes the signals, and
feeds back to the BS the ID of the strongest signal (e.g., via a lower frequency control channel).
The BS uses such strongest beam to communicate with the MU in the data communication
phase, as detailed in Sec. II-C. We neglect the time to send this feedback signal.
{ωi , i = 1, 2, . . . , η} are designed with the following requirements: R1 – By the end of the
beam-sweeping phase, the entire uncertainty interval U0 must be scanned, plus the additional uncertainty resulting from the MU mobility during the beam-sweeping phase; R2 – the beamwidth
at the beginning of the data communication phase, uηδS , must be independent of the strongest
beam selected.
To guarantee R2, note that, if the ith beam, i = 1, 2, . . . , η is the strongest one detected (with
beamwidth ωi ), the uncertainty width at the end of the beam-sweeping phase becomes1
uηδS = dωi + (η + 1 − i)δS φ,

(3)

due to the MU mobility in the subsequent (η + 1 − i) microslots until the end of beam-sweeping.
Hence, R2 requires
ωi = ω1 + (i − 1)

δS φ
, ∀i = 1, 2, . . . , η,
d

(4)

so that, at the end of beam-sweeping, the uncertainty width becomes
uηδS = dω1 + ηδS φ, ∀i.

(5)

We now discuss how to design ω1 (and ωi via (4)) so as to guarantee R1. At the reference
time 0, the uncertainty interval is [0, uth ]. In the first microslot, the BS scans the interval [0, dω1 ]
1

Herein, we assume that ωi  2π, so that the length of the interval scanned in the ith microslot is 2d tan(ωi /2) ' dωi , see
Fig. 1 (the beam is approximated as being pointed perpendicularly to the motion of the MU).

January 30, 2018

DRAFT

6

using a beam with beamwidth ω1 . If the MU is within this interval, at the end of the beamsweeping phase it will detect the ID of the strongest beam as #1, and the uncertainty width will
thus be given by (5). Otherwise (if the MU is outside of this interval), after the first microslot
the MU may be in the interval [dω1 − δS φ/2, uth + δS φ/2], which accounts for the additional
uncertainty due to the MU mobility in the time interval [0, δS ]. Thus, in the second microslot,
the BS scans the interval [dω1 − δS φ/2, dω1 + dω2 − δS φ/2] using a beam with beamwidth ω2 .
If the MU is within this interval, at the end of the beam sweeping phase it will detect the ID
of the strongest beam as #2, and the uncertainty width will thus be given by (5). Otherwise (if
the MU is outside of this interval), after the second microslot the MU may be in the interval
[dω1 + dω2 − δS φ, uth + δS φ], which accounts for the additional uncertainty due to the MU
mobility in the time interval [δS , 2δS ]. Thus, in the third microslot, the BS scans the interval
[dω1 + dω2 − δS φ, dω1 + dω2 + dω3 − δS φ] with a beam with beamwidth equal to ω3 , and so on.
By induction, at the beginning of the ith microslot, where i = 1, 2, ..., η, i−1 beams have been
scanned. If the MU was located within one of the previous i − 1 beams (say the jth, j ≤ i − 1),
it will detect the ID of the strongest beam as #j at the end of the beam-sweeping phase, and the
uncertainty width will thus be given by (5). Otherwise (if the MU is located within one of the next
Pi−1
ωk −(i−1)δS φ/2, uth +(i−1)δS φ/2]
beams i, i+1, . . . , η), the MU may be in the interval [d k=1
at the beginning of the ith microslot, which accounts for the additional uncertainty due to the
MU mobility in the time interval [0, (i − 1)δS ]. Thus, in the ith microslot, the BS scans the
Pi
P
interval [d i−1
k=1 ωk − (i − 1)δS φ/2] using a beam with beamwidth
k=1 ωk − (i − 1)δS φ/2, d
ωi . If the MU is within this interval, it will detect the ID of the strongest beam as #i at the end
of the beam-sweeping period, and the uncertainty width will thus be given by (5). Otherwise
(if the MU is outside of this interval), at the end of the ith microslot the MU may be in the
P
interval [d ik=1 ωk − iδS φ/2, uth + iδS φ/2], which accounts for the additional uncertainty due
to the MU mobility in the time interval [(i − 1)δS , iδS ].
Using a similar argument, in the last microslot (the ηth one), if the MU was not located within
P
one of the previous η − 1 beams, then the MU will be located in the interval [d η−1
k=1 ωk − (η −
Pη−1
1)δS φ/2, uth + (η − 1)δS φ/2] of width uth + (η − 1)δS φ − d k=1 ωk . This must be scanned
exhaustively with a beam of width ωη , hence
dωη = uth + (η − 1)δS φ − d

η−1
X

ωk .

(6)

k=1

January 30, 2018

DRAFT

7

By combining (6) with (4) we obtain, ∀i = 1, 2, . . . , η,
ωi =

δS φ
uth (η − 1)(η − 2) δS φ
−
+ (i − 1)
.
dη
2η
d
d

(7)

At the end of beam-sweeping, data communication begins and the new uncertainty width is
given by (5), yielding
ucomm (uth , η),uηδS =

uth
(η−1)(η−2)
+ηδS φ−δS φ
.
η
2η

(8)

which evolves over the data communication interval according to (2).
Note that a feasible beam is such that ωk ≥ 0, ∀k = 1, 2, . . . , η. Additionally, beam-sweeping
must reduce the uncertainty width, i.e., ucomm (uth , η) ≤ uth . These two conditions together yield
 2

η /2 + 3/2η − 1 1
uth ≥ δS φ max
, (η − 1)(η − 2) .
(9)
η−1
2
Herein, we assume that the correct sector is detected with no error by the MU (this requires
proper beam design to achieve small false-alarm and misdetection probabilities, see [18]).
C. Data communication
Immediately after beam-sweeping, at time t = ηδS , the data communication phase begins, and
the uncertainty width is uηδS = ucomm (uth , η). The uncertainty width ut increases over time due
to the mobility of the MU, according to (2). The data communication period, and the beamsweeping – data communication cycle, terminate at time T such that uT = uth , at which time a
new cycle begins. From (2) we obtain
T =

(η − 1)uth δS (η − 1)(η − 2)
+
.
φη
2
η

(10)

In the time interval [ηδS , T ], the transmission beam of the BS associated with the MU is chosen
so as to support reliable communication over the entire uncertainty interval. Its beamwidth is
thus chosen as ωt ' ut /d [rad].2
Remark 1. Note that in our model the beamwidth is varied continuously within a continuous
set ω ∈ [ucomm (uth , η)/d, uth /d] for analytical tractability. This approach is a continuous ap2
Note that we assume that ut /d  2π, so that we can approximate the beamwidth as ωt = 2 arctan(ut /d/2) ' ut /d, see
Fig. 1.

January 30, 2018

DRAFT

8

proximation of a practical deployment where the system may operate at discrete times using a
discrete codebook to generate transmission beams with different beamwidths [19].
Let Pt be the transmission power per Hz at time t to communicate reliably. Assuming isotropic
reception at the MU [7], [8], the instantaneous transmission rate is given by


Pt
,
Rt = Wtot log2 1 + γ
ωt
where Wtot is the bandwidth, γ ,

λ2 ξ
8πd2 N0 Wtot

(11)

is the SNR scaling factor, λ is the wavelength, N0

is the noise power spectral density, and ξ is the antenna efficiency. Note that Pt is spread evenly
across the angular directions covered by the transmission beams, so that Pt /ωt is the power per
radian delivered to the receiver.
D. Performance metrics and optimization problem
The optimal choice of the beam-sweeping and communication parameters reflects a trade-off
between locating the MU with high accuracy so as to achieve narrow-beam communication, and
mitigating the overhead in terms of sweeping time. This is the goal of our design.
Let η ≥ 2, η ∈ N, uth satisfying (9), and P : [ηδS , T ] 7→ R+ be the transmit power function in
the data communication phase. We define the time-average communication rate and transmission
power, defined over one beam-sweeping – data communication cycle [0, T ], as


Z
Wtot T
dγPt
R̄(η, uth , P )=
log 1+
dt,
T ηδS 2
ucomm (uth , η)+φt
Z
Wtot T
P̄ (η, uth , P )=
Pt dt.
T
ηδS

(12)
(13)

The goal is to determine the optimal design of the joint data communication and beam-sweeping
parameters (η, uth , P ) so as to maximize the average rate under average power constraint Pmax >
0, i.e.,
P1 :

(η, uth , P )∗ =arg max R̄(η, uth , P ),

(14)

(η,uth ,P )

s.t. P̄ (η, uth , P ) ≤ Pmax .

(15)

The analysis is carried out in the next section.

January 30, 2018

DRAFT

9

III. A NALYSIS
Due to the concavity of the log2 function, Jensen’s inequality yields the following result.
Lemma 1. The optimal power allocation function P : [ηδS , T ] 7→ R+ is given by the water-filling
scheme

+
ut
Pt = ρ −
, ∀t ∈ [ηδS , T ],
dγ
where ρ ≥

ucomm (uth ,η)
dγ

(16)

is a parameter to optimize.

Under the water-filling power allocation, the design space is simplified to (η, uth , ρ), where
η ≥ 2, η ∈ N, uth satisfies (9), and ρ ≥

ucomm (uth ,η)
.
dγ

The average rate and average transmission

power can be computed in closed form and are given by3
"


Wtot 
uth −ucomm (uth , η) 1+ ln (dγρ)
R̄(η, uth , ρ) =
ln(2)φT
− uth ln(uth ) + ucomm (uth , η) ln(ucomm (uth , η))



#
uth
+ χ(dγρ ≤ uth ) uth ln
+ dγρ − uth
,
dγρ
P̄ (η, uth , ρ) = χ(dγρ ≤ uth )
+

(uth − dγρ)2
2dφγT

(17)
(18)


uth − ucomm (uth , η) 
2dγρ − uth − ucomm (uth , η) ,
2dφγT

where χ(·) denotes the indicator function.
It is useful to define the following change of variables:
uth
,
δS φ
dγρ
ucomm (uth , η)
ζ,
−1≥
− 1.
δS φυ
δS φυ
υ,

3

(19)
(20)

We replace the dependence on the power allocation function P with the parameter ρ.

January 30, 2018

DRAFT

10

The performance metrics (17)-(18) can thus be expressed as
υ 1
3 1
ucomm (uth , η)
= + η+ − ,
δS φ
η 2
2 η
ln(2)
1
η
R̂(η, υ, ζ) ,
R̄(η, uth , ρ) =
Wtot
η − 1 υ + η2 − 1
"



× υ − ûcomm (υ, η) 1+ ln(1 + ζ)
ûcomm (υ, η) ,


−ûcomm (υ, η) ln

υ
ûcomm (υ, η)

(21)

(22)
#



+χ(ζ<0)υ (ζ− ln(1+ζ)) ,

dγ
ηυ 2 ζ 2 χ(ζ<0)

P̄ (η, uth , ρ)=
δS φ
2(η − 1) υ + η2 − 1

η(υ − ûcomm (υ, η)) 

2υ(1
+
ζ)−υ−û
(υ,
η)
,
+
comm
2(η − 1) υ + η2 − 1
P̂ (η, υ, ζ),

where (9) and ρ ≥

ucomm (uth ,η)
dγ

(23)

yield the feasible set

o
n
ûcomm (υ, η)
−1 ,
Fη ≡ (υ, ζ) : υ ≥ υmin (η), ζ ≥
υ
and we have defined

υmin (η) , max


η 2 + 3η − 2 1
, (η − 1)(η − 2) .
2(η − 1) 2

(24)

Note that we have normalized the average rate and transmission power, so that they no longer
depend on the system parameters Wtot , φ, d, γ, δS . This is beneficial since it unifies the structure
of the optimal design in a wide range of scenarios.
The optimization problem thus becomes
P2 :

(η, υ, ζ)∗ =

arg max

R̂(η, υ, ζ)

(25)

η≥2,η∈N,(υ,ζ)∈Fη

s.t. P̂ (η, υ, ζ) ≤ P̂max ,
where P̂max =

dγ
P .
δS φ max

(26)

This optimization problem is non-convex. We have the following

structural result.
Theorem 1. ζ < 0 is suboptimal.
Proof. See Appendix A.

January 30, 2018

DRAFT

11

The intuition behind Theorem 1 is that, if ζ < 0, then the water-filling power allocation is
such that Pt = 0 during a portion of the data communication phase. This is suboptimal: it is
more energy-efficient to reduce the beam-sweeping threshold uth and increase ζ so as to reduce
the "idle" time interval in the communication phase.
Thus, in the following we focus on the case ζ ≥ 0. Note that P̂ (η, υ, ζ) needs to satisfy the
power constraint. Since it is an increasing function of ζ, we must have P̂ (η, υ, 0) ≤ P̂max to
obtain a feasible solution, yielding
η 2 +3η−2 η P̂max
υ≤
+
2(η − 1) η − 1

s
1+

1+

2η
P̂max

!
, υmax (η).

(27)

Note that υ must also satisfy the constraint υ ≥ υmin (η), hence we must have υmax (η) ≥ υmin (η).
If η ≤ 4, then

1 η 2 +3η−2
2
η−1

> 21 (η − 1)(η − 2) and any υ satisfying (27) also satisfies υ ≥ υmin (η).

On the other hand, if η ≥ 5 then

1 η 2 +3η−2
2
η−1

< 12 (η −1)(η −2) and υmax (η) ≥ υmin (η) is equivalent

to
P̂max ≥

1 [η 2 − 5η + 2]2
, for η ≥ 5.
2 η 2 − 4η + 2

(28)

Since the right hand side is an increasing function of η ≥ 5, we conclude that there exists
4 ≤ ηmax < ∞ such that the problem is feasible for all 2 ≤ η ≤ ηmax (indeed, the problem is
always feasible for η ∈ {2, 3, 4} since υmax (η) ≥ υmin (η) in this case). We thus define the new
feasibility set as
F ≡ {(υ, η) : 2 ≤ η ≤ ηmax , η ∈ N, υmin (η) ≤ υ ≤ υmax (η)} .
Let (υ, η) ∈ F. Under such pair, P̂ (η, υ, ζ) and R̂(η, υ, ζ) are increasing functions of ζ ≥ 0,
hence the optimal ζ is such that the power constraint is attained with equality. We thus obtain
ζ as a function of (υ, η) as
ζ(υ, η) ,

(η − 1)(υ + η/2 − 1)
(P̂max − P̂ (0, η, υ)).
ηυ[υ − ûcomm (υ, η)]

(29)

Since the power constraint is satisfied with equality for (υ, η) ∈ F and ζ = ζ(υ, η), the
optimization problem becomes unconstrained, yielding
P3 :

(η, υ)∗ =arg max R̂(η, υ, ζ(υ, η)),

(30)

(υ,η)∈F

January 30, 2018

DRAFT

12

and ζ ∗ = ζ(υ ∗ , η ∗ ), where
1
η
η − 1 υ + η2 − 1
"



× υ − ûcomm (υ, η) 1+ ln(1 + ζ(υ, η))

R̂(η, υ, ζ(υ, η)) =


− ûcomm (υ, η) ln

υ
ûcomm (υ, η)

(31)
(32)

#
.

We solve the optimization problem as follows: for each 2 ≤ η ≤ ηmax , we solve
υ ∗ (η) =

arg max

R̂(η, υ, ζ(υ, η)).

(33)

υmin (η)≤υ≤υmax (η)

Then, the optimal η ∗ and υ ∗ are found by optimizing η via exhaustive search over the finite
discrete set {2, 3, . . . , ηmax },
η ∗ = arg

max

η∈{2,3,...,ηmax }

R̂(ρ(υ ∗ (η), η), η, υ ∗ (η)),

(34)

and υ ∗ = υ ∗ (η ∗ ).
A. Solution of (33) given η ∈ {2, 3, . . . , ηmax }
In this section, we investigate how to compute υ ∗ (η) given η ∈ {2, 3, . . . , ηmax }. We have the
following theorem.
Theorem 2. Given η ∈ {2, 3, . . . , ηmax }, the optimal υ ∗ (η) is given by


1
∗
υ (η) = max
(η − 1)(η − 2), υ̂ ,
2
where υ̂ is the unique solution in ( 21 η

2 +3η−2

η−1

(35)

, υmax (η)) of fη (υ) = 0, where

υ − ûcomm (υ, η) (η − 1)(υ + η/2 − 1) + 2η
υ(1 + ρ(υ, η))
2η
(η − 1)(υ + η/2 − 1)
−
ρ(υ, η)
η(1 + ρ(υ, η))

fη (υ) , −

(36)

+ ln(1 + ρ(υ, η))η + ln(υ/ûcomm (υ, η))(η/2 + 1).
Proof. See Appendix B.

January 30, 2018

DRAFT

13

The function fη (υ) is proportional to the derivative of R̂(η, υ, ζ(υ, η)) with respect to υ, up
to a positive multiplicative factor. Note that υ̂ can be determined using the bisection method. In
fact, fη (υ) is a decreasing function of υ (see proof of the theorem in [20]), with

υ→ 12

lim
2

fη (υ) = ∞ and fη (υmax (η)) < 0.

(37)

η +3η−2
η−1

IV. N UMERICAL R ESULTS
In this section, we present numerical results to demonstrate the performance of the proposed
beam-sweeping – data communication protocol. We compare our proposed scheme with an
adaptation of IEEE 802.11ad to our model, in which partially overlapping beams of 7o beamwidth
are employed such that adjacent beams share half of the beam area. Moreover, to evaluate this
scheme we assume a worst-case scenario where the vehicle moves with either speed of vmax or
vmin = −vmax . Therefore, with IEEE 802.11ad, beam alignment is required after each r/vmax
o
[s] (the time required for the MU to move to the edge of the beam), where r = d tan 72 . Once
the edge of the beam is reached (thus, the MU is located in either position p ∈ {−r, r}), the BS
scans the two beams covering the intervals [−2r, 0] and [0, 2r], each with 7o beamwidth, so that
the time overhead of beam sweeping is 2δS . Immediately after, the strongest beam is detected
and data communication proceeds. Then, the fraction of time spent in data communication is
given as
fcomm =

r/vmax
,
r/vmax + 2δS

the average throughput of IEEE 802.11ad is given as


Pt
R̄11ad = Wtot log2 1 + γ
× fcomm ,
7π/180

(38)

(39)

TABLE I: Simulation parameters
Parameter
Carrier frequency
Bandwidth
Noise PSD
Microslot duration
Distance BU-MU
Antenna efficiency

January 30, 2018

Symbol
fc
Wtot
N0
δS
d
ξ

Value
60 GHz
1.76 GHz
-174 dBm/Hz
10µs
10 m
1

DRAFT

14

Fig. 2: Average spectral efficiency versus average power.

and the average power as P̄11ad = Pt × fcomm . The common parameters of the simulation are
given in Table I.
In Fig. 2, we plot the average spectral efficiency R̄/Wtot versus the average power consumption
P̄ . A monotonic trend between the spectral efficiency and the average power is observed.
Moreover, the performance of the system deteriorates as we increase the speed, due to the
increasing overhead of beam alignment. Additionally, we observe that IEEE 802.11ad performs
poorly since it uses fixed 7o beams which are not optimized to the specific mobile scenario, with
degradation up to 90% compared to our proposed scheme.
In Fig. 3, we plot the effect of speed on the spectral efficiency for two different values of the
average power P̄ . It can be seen that the spectral efficiency of the proposed scheme degrades
monotonically as the speed vmax is increased. Moreover, the performance improves with higher
value of P̄ as observed also in Fig. 2. It can be noticed that the curves corresponding to IEEE
802.11ad do not show significant degradation as the speed is increased. This is due to the

January 30, 2018

DRAFT

15

Fig. 3: Average spectral efficiency versus speed.

relatively wide beam used in IEEE 802.11ad, so that beam alignment is relatively infrequent.
However, the performance of IEEE 802.11ad is poor compared to our proposed scheme.
V. C ONCLUSION
In this paper, we propose a one-dimensional mobility model where a vehicle moves along a
straight road with time-varying and random speed and communicates with base stations located
on the roadside over the mm-wave band. We propose a beam-sweeping – data communication
protocol and study its performance in closed form. We derive structural properties of the optimal
design, based on which we design a bisection algorithm. We compare numerically our proposed
design to an adaptation of IEEE 802.11ad to our model, which exhibits performance degradation
up to 90%.
R EFERENCES
[1] J. Choi, V. Va, N. Gonzalez-Prelcic, R. Daniels, C. R. Bhat, and R. W. Heath, “Millimeter-wave vehicular communication
to support massive automotive sensing,” IEEE Communications Magazine, vol. 54, no. 12, pp. 160–167, December 2016.

January 30, 2018

DRAFT

16

[2] V. Va, T. Shimizu, G. Bansal, and R. W. Heath, “Beam design for beam switching based millimeter wave vehicle-toinfrastructure communications,” in 2016 IEEE International Conference on Communications (ICC), May 2016, pp. 1–6.
[3] T. S. Rappaport, Wireless communications: principles and practice.

Prentice Hall PTR, 2002.

[4] M. R. Akdeniz, Y. Liu, M. K. Samimi, S. Sun, S. Rangan, T. S. Rappaport, and E. Erkip, “Millimeter Wave Channel
Modeling and Cellular Capacity Evaluation,” IEEE Journal on Selected Areas in Communications, vol. 32, no. 6, pp.
1164–1179, June 2014.
[5] C. Jeong, J. Park, and H. Yu, “Random access in millimeter-wave beamforming cellular networks: issues and approaches,”
IEEE Communications Magazine, vol. 53, no. 1, pp. 180–185, January 2015.
[6] V. Desai, L. Krzymien, P. Sartori, W. Xiao, A. Soong, and A. Alkhateeb, “Initial beamforming for mmWave communications,” in 48th Asilomar Conference on Signals, Systems and Computers, Nov 2014, pp. 1926–1930.
[7] M. Hussain and N. Michelusi, “Throughput optimal beam alignment in millimeter wave networks,” in Information Theory
and Applications Workshop (ITA), Feb 2017, pp. 1–6.
[8] ——, “Energy efficient beam alignment in millimeter wave networks,” in 2017 Asilomar Conference on Signals, Systems,
and Computers, 2017, to appear.
[9] A. Alkhateeb, O. E. Ayach, G. Leus, and R. W. Heath, “Channel estimation and hybrid precoding for millimeter wave
cellular systems,” IEEE Journal of Selected Topics in Signal Processing, vol. 8, no. 5, pp. 831–846, Oct 2014.
[10] Z. Marzi, D. Ramasamy, and U. Madhow, “Compressive channel estimation and tracking for large arrays in mm-wave
picocells,” IEEE Journal of Selected Topics in Signal Processing, vol. 10, no. 3, pp. 514–527, April 2016.
[11] N. González-Prelcic, R. Méndez-Rial, and R. W. Heath, “Radar aided beam alignment in mmwave v2i communications
supporting antenna diversity,” in Information Theory and Applications Workshop (ITA), Jan 2016, pp. 1–7.
[12] T. Nitsche, A. B. Flores, E. W. Knightly, and J. Widmer, “Steering with eyes closed: Mm-wave beam steering without
in-band measurement,” in 2015 IEEE Conference on Computer Communications (INFOCOM), April 2015, pp. 2416–2424.
[13] V. Va, J. Choi, T. Shimizu, G. Bansal, and R. W. Heath, “Inverse Multipath Fingerprinting for Millimeter Wave V2I Beam
Alignment,” IEEE Transactions on Vehicular Technology, vol. PP, no. 99, pp. 1–1, 2017.
[14] “IEEE Std 802.15.3c-2009,” IEEE Standard, pp. 1–200, Oct 2009.
[15] “IEEE Std 802.11ad-2012,” IEEE Standard, pp. 1–628, Dec 2012.
[16] V. Va, J. Choi, and R. W. Heath, “The Impact of Beamwidth on Temporal Channel Variation in Vehicular Channels and
Its Implications,” IEEE Transactions on Vehicular Technology, vol. 66, no. 6, pp. 5014–5029, June 2017.
[17] J. B. Kenney, “Dedicated short-range communications (dsrc) standards in the united states,” Proceedings of the IEEE,
vol. 99, no. 7, pp. 1162–1182, July 2011.
[18] M. Hussain, D. J. Love, and N. Michelusi, “Neyman-Pearson Codebook Design for Beam Alignment in Millimeter-Wave
Networks,” in Proceedings of the 1st ACM Workshop on Millimeter-Wave Networks and Sensing Systems.

New York,

NY, USA: ACM, 2017, pp. 17–22.
[19] S. Noh, M. D. Zoltowski, and D. J. Love, “Multi-Resolution Codebook and Adaptive Beamforming Sequence Design for
Millimeter Wave Beam Alignment,” IEEE Transactions on Wireless Communications, vol. 16, no. 9, pp. 5689–5701, Sept
2017.
[20] N. Michelusi and M. Hussain, “Optimal Beam Sweeping and Communication in Mobile Millimeter-wave Networks,”
Purdue University, Tech. Rep., 2017, https://engineering.purdue.edu/~michelus/ICC2018.pdf.

January 30, 2018

DRAFT

17

A PPENDIX A
P ROOF OF T HEOREM 1
Proof. First, note that if ζ = ûcomm (υ, η)/υ − 1, then P̂ (υ(1 + ζ), η, υ) = 0 < Pmax and
R̂(υ(1 + ζ), η, υ) = 0. This configuration is clearly suboptimal since a non-zero rate can be
achieved by increasing ζ.
Now, let ûcomm (υ, η)/υ − 1 < ζ < 0 and assume this configuration is optimal. Note that this
implies υ > ûcomm (υ, η), or equivalently υ >

1 η 2 +3η−2
.
2
η−1

We have two cases: 1) υ > 12 (η − 1)(η − 2) and 2) υ = 21 (η − 1)(η − 2) (and consequently
η ≥ 5 since we must also have υ >

1 η 2 +3η−2
).
2
η−1

a) υ > 12 (η − 1)(η − 2): We show that, by increasing ζ and decreasing υ so as to preserve
the power consumption, the rate strictly increases, and thus we achieve a contradiction. From
(22) and (23) with ζ < 0 we obtain
R̂(η, υ, ζ) =

η ûcomm (υ, η)
η − 1 υ + η2 − 1

"

(40)


υ
υ
(1 + ζ) − 1 − ln
ûcomm (υ, η)
ûcomm (υ, η)

2
η υ(1 + ζ) − ûcomm (υ, η)

.
P̂ (η, υ, ζ) =
2(η − 1) υ + η2 − 1
×

#
(1 + ζ) ,

(41)

We increase ζ by h > 0 (arbitrarily small) and decrease υ by a function g(h) > 0, so as to
maintain the power consumption unaltered, i.e.,
P̂ (η, υ, ζ) = P̂ (η, υ − g(h), ζ + h).

(42)

In the limit h → 0 we must have
dP̂ (η, υ, ζ)
dP̂ (η, υ, ζ)
− g 0 (0)
= 0,
dζ
dυ

January 30, 2018

(43)

DRAFT

18

where g 0 (0) is the derivative of g(h) in zero, which must be positive since g(h) > 0 for arbitrarily
small h. To show this, note that




ηυ υ(1 + ζ) − ûcomm (υ, η)
dP̂ (ζ, η, υ)

=
> 0,
dζ
(η − 1) υ + η2 − 1


η υ(1 + ζ) − ûcomm (υ, η)
dP̂ (ζ, η, υ)
=
2
dυ
2(η − 1) υ + η2 − 1

1 1
υ 1
> 0,
× (1 + ζ)(υ + η − 2) − + η + +
η 2
2 η

(44)

(45)

where the last inequality follows from the fact that ζ > ûcomm (υ, η)/υ − 1. Hence, it follows
that indeed g 0 (0) > 0.
We now show that, for arbitrarily small h,
R̂(η, υ, ζ) < R̂(η, υ − g(h), ζ + h).

(46)

Equivalently, in the limit h → 0, we must have
dR̂(η, υ, ζ)
dR̂(η, υ, ζ)
− g 0 (0)
> 0.
dζ
dυ

(47)

Note that
1
dP̂ (ζ, η, υ)
dR̂(η, υ, ζ)
=
,
dζ
υ(1 + ζ)
dζ
dR̂(ζ, η, υ)
η(η/2 − 1)
=
[υ(1 + ζ) − ûcomm (υ, η)]
dυ
(η − 1)υ(υ + η2 − 1)2


η(η/2 + 1)
υ
+
ln
(1 + ζ) ,
(η − 1)(υ + η2 − 1)2
ûcomm (υ, η)

(48)

(49)

and thus replacing (48) in (47), and using (43) and the fact that g 0 (0) > 0, we obtain the
equivalent condition
dP̂ (η, υ, ζ)
dR̂(η, υ, ζ)
− υ(1 + ζ)
> 0,
dυ
dυ

January 30, 2018

(50)

DRAFT

19

iff
υ 1
1 1
ûcomm (υ, η) 
(1 + ζ)υ − + η + +
g(ζ) , 1 −
υ(1 + ζ)
η 2
2 η


υ
− (η + 2) ln
(1 + ζ) > 0,
ûcomm (υ, η)


(51)

which we are now going to prove. The derivative with respect to ζ is given by
dg(ζ)
∝ η(υ(1 + ζ) − ûcomm (υ, η))2
dζ
+ (2υ + η − 2)(υ(1 + ζ) − ûcomm (υ, η)) > 0,

(52)

where the inequality follows from the fact that ζ > ûcomm (υ, η)/υ − 1. It follows that g(ζ) is an
increasing function of ζ, minimized at ζ = ûcomm (υ, η)/υ − 1, thus proving the inequality.
b) υ = 21 (η − 1)(η − 2) and η ≥ 5: In this case, we cannot decrease υ any further. Using
a similar approach as in the previous case, we show that a strictly larger rate can be obtained
by decreasing both η and ζ, while preserving the power consumption. From (40) and (41) with
υ = 21 (η − 1)(η − 2), we obtain
R̂(η, υ, ζ) = 1 + ζ

(53)


−

2η
1 + ln
(η − 1)(η − 2)



(η − 1)(η − 2)(1 + ζ)
2η


,

[υ(1 + ζ) − ûcomm (υ, η)]2
,
P̂ (η, υ, ζ) =
(η − 1)(η − 2)
where

−η 2 +5η−2
(η−1)(η−2)

(54)

< ζ < 0.

Now, we decrease η by one unit, while keeping υ as before, and we choose the new ζ, denoted
as ζ̂, in such a way as to preserve the power consumption. Note that υ ≥ υmin (η − 1) hence the
constraint on υ is still satisfied, since υmin (η − 1) is a decreasing function of η.
From (41) with υ = 21 (η − 1)(η − 2) we obtain

2
(η − 1) υ(1 + ζ̂) − ûcomm (υ, η − 1)
P̂ (η − 1, υ, ζ̂) =

(η − 2)(η 2 − 2η − 1)

.

(55)

where
ûcomm (υ, η − 1) = η −

January 30, 2018

1
< ûcomm (υ, η) = η.
η−1

(56)

DRAFT

20

ζ̂ is chosen so that P̂ (η − 1, υ, ζ̂) = P̂ (η, υ, ζ), yielding
υ(1 + ζ̂) = ûcomm (υ, η − 1)
p
υ(1 + ζ) − ûcomm (υ, η)
+ η 2 − 2η − 1
.
η−1

(57)

Thus, it follows that υ(1 + ζ̂) > ûcomm (υ, η − 1) Additionally, using (56) and the fact that
υ(1 + ζ) − ûcomm (υ, η) > 0 it follows that υ(1 + ζ̂) < υ(1 + ζ). Therefore
ûcomm (υ, η − 1) < υ(1 + ζ̂) < υ(1 + ζ) < υ,

(58)

since ζ < 0, hence ûcomm (υ, η − 1)/υ − 1 < ζ̂ < 0. We now show that this new configuration
strictly increases the throughput. From (40) and using the expression of ζ̂ and of ûcomm (υ, η − 1)
we obtain
R̂(η − 1, υ, ζ̂) =
−

2
p
(υ(1 + ζ) − η)
(η − 2) η 2 − 2η − 1

(59)

2(η 2 − η − 1)
ln(υ(ζ̂ + 1)/ûcomm (υ, η − 1)),
(η − 2)(η 2 − 2η − 1)

and therefore
h(ζ) , R̂(η − 1, υ, ζ̂) − R̂(η, υ, ζ)

(60)

4(υ(1 + ζ) − η)
p
p
(η − 1)(η − 2) η 2 − 2η − 1(η − 1 + η 2 − 2η − 1)
2η
ln(υ(1 + ζ)/η)
+
(η − 1)(η − 2)
2(η 2 − η − 1)
−
ln(υ(ζ̂ + 1)/ûcomm (υ, η − 1)).
(η − 2)(η 2 − 2η − 1)
=

The derivative of h(ζ) with respect to ζ is given by
dh(ζ)
∝ υ(1 + ζ) − ûcomm (υ, η)
dζ
2(υ(1 + ζ) − η)2
p
+
> 0.
η − 1 + η 2 − 2η − 1

(61)

Therefore, h(ζ) is an increasing function of ζ, minimized at ζ = ûcomm (υ, η)/υ − 1, yielding
R̂(ζ̂, η − 1, υ) − R̂(ζ, η, υ) > 0.

January 30, 2018

(62)

DRAFT

21

The Theorem is thus proved.
A PPENDIX B
P ROOF OF T HEOREM 2
Proof. To study the optimization problem P3, we study the derivative R̂(η, υ, ζ(υ, η)) with
respect to υ. We have that
dR̂(η, υ, ζ(υ, η))
dR̂(η, υ, ζ) dR̂(η, υ, ζ) dζ(υ, η)
=
+
dυ
dυ
dζ
dυ
∝ fη (υ),

(63)

where ∝ denotes proportionality up to a positive multiplicative factor, with fη (υ) given by (36).
Therefore, R̂(ζ, η, υ) is an increasing function of υ iff fη (υ) > 0. We now show that fη (υ) is a
strictly decreasing function of υ, with limits given by (37).
Note that υ̂ can be determined using the bisection method. In fact, fη (υ) is a decreasing
function of υ (see proof of the theorem), with

υ→ 21

lim
2

fη (υ) = ∞

(64)

η +3η−2
η−1

and
fη (υmax (η)) < 0

(65)

(see second part of the proof). Therefore, there exists a unique υ̂ ∈ ( 21 η
that fη (υ̂) = 0, and

dR̂(η,υ,ζ(υ,η))
dυ

> 0 for υ < υ̂ and

dR̂(η,υ,ζ(υ,η))
dυ

2 +3η−2

η−1

, υmax (η)) such

< 0 for υ > υ̂.

Therefore, the maximum of R̂(η, υ, ζ(υ, η)) with respect to υ ∈ ( 12 η

2 +3η−2

η−1

, υmax (η)) is attained

at υ = υ̂. By combining this result with the constraint υ ≥ υmin (η), we obtain (35).

January 30, 2018

DRAFT

22

Thus, we now show that fη (υ) is a decreasing function of υ. We have
dfη (υ)
dυ
(η − 1)(υ + η/2 − 1) + 2η
= −(η − 1)
(1 + ζ(υ, η))
2υη 2
(η − 1)(η/2 − 1) + 2η
(1 + ζ(υ, η))
+ [υ − ûcomm (υ, η)]
2υ 2 η
(η − 1)(υ + η/2 − 1) + 2η 0
+ [υ − ûcomm (υ, η)]
ζ (υ, η)
2υη
(η − 1)
(η − 1)(υ + η/2 − 1) 0
−
ζ(υ, η)(1 + ζ(υ, η)) −
ζ (υ, η)
η
η

(1 + ζ(υ, η))2

+ ηζ 0 (υ, η)(1 + ζ(υ, η))
+ [1/υ − 1/ûcomm (υ, η)/η](η/2 + 1)(1 + ζ(υ, η))2 ,
where ζ 0 (υ, η) =

dζ(υ,η)
.
dυ

(66)

By simplifying and reorganizing the expression, we obtain

1
df (υ)
= − [υ − ûcomm (υ, η)]2
(1 + ζ(υ, η))2
dυ
υ


η+2
υ − ûcomm (υ, η)
×
+
2ηυûcomm (υ, η) 4υ(υ + η/2 − 1)
[υ − ûcomm (υ, η)]
− ζ(υ, η)
υ2
 2

η3
(η + 2)υ
η /2 + 3/2η − 1
+
+
×
υ − ûcomm (υ, η)
(υ + η/2 − 1)(η − 1) ηûcomm (υ, η)


[υ − ûcomm (υ, η)]2
η 2 + 3η − 2
− ζ(υ, η)
1+
υ2
2(υ + η/2 − 1)(η − 1)
"
1
− ζ(υ, η)2 [υ/ûcomm (υ, η) − 1](1/2 + 1/η)
υ
#
2
2
η
η /2 + 3/2η − 1
+
(υ + η/2 − 1)(η − 1) υ − ûcomm (υ, η)


2 1 υ − ûcomm (υ, η) + 2η 2
− ζ(υ, η)
η + 1 + υ − ûcomm (υ, η) < 0,
υ (υ + η/2 − 1)(η − 1)

(67)

(68)

where inequality holds since ζ(υ, η) ≥ 0 and υ > ûcomm (υ, η). This proves that fη (υ) is strictly
decreasing in υ.
Now, note that, in the limit υ →

1 η 2 +3η−2
,
2
η−1

we obtain υ → ûcomm (υ, η) and ζ(υ, η) →

∞, yielding (64). On the other hand, when υ = υmax (η), by letting x , P̂max (η − 1)[1 +

January 30, 2018

DRAFT

23

q
1 + 2η/P̂max ] > 0 we obtain
x[η + 2 + x]
fη (υmax (η)) = −(η − 1) 2
η + 3η − 2 + 2ηx


(η − 1)x
(η/2 + 1) , g(x).
+ ln 1 + 2
η /2 + 3/2η − 1 + x

(69)
(70)

The derivative of the above expression with respect to x satisfies
dg(x)
∝ −[η 2 /2 + 3/2η − 1][2η + 2x + xη] − x2 η < 0,
dx

(71)

which satisfies the inequality since η ≥ 2, hence g(x) is maximized at x = 0, yielding
fη (υmax (η)) = g(x) < g(0) = 0.

(72)

The Theorem is thus proved.

January 30, 2018

DRAFT

