  In intelligent reflecting surface (IRS) assisted communication, beam search
is usually time-consuming as the multiple-input multiple-output (MIMO) of IRS
is usually very large. Hierarchical codebooks is a widely accepted method for
reducing the complexity of searching time. The performance of this method
strongly depends on the design scheme of beamforming of different beamwidths.
In this paper, a non-constant phase difference (NCPD) beamforming algorithm is
proposed. To implement the NCPD algorithm, we first model the phase shift of
IRS as a continuous function, and then determine the parameters of the
continuous function through the analysis of its array factor. Then, we propose
a hierarchical codebook and two beam training schemes, namely the joint
searching (JS) scheme and direction-wise searching (DWS) scheme by using the
NCPD algorithm which can flexibly change the width, direction and shape of the
beam formed by the IRS array. Simulation results show that the NCPD algorithm
is more accurate with smaller side lobes, and also more stable on IRS of
different sizes compared to other wide beam algorithms. The misalignment rate
of the beam formed by the NCPD method is significantly reduced. The time
complexity of the NCPD algorithm is constant, thus making it more suitable for
solving the beamforming design problem with practically large IRS.
