METHOD FOR COMPUTING WEIGHTS FOR A BEAMFORMING ALGORITHM FROM AN INTELLIGENT REFLECTING SURFACE

Abstract

The invention discloses a method of computing weights for a 1-bit phase shifts case of beamforming from an intelligent reflecting surface (IRS) thereof. The method includes the steps of: writing a normalized array factor G of the IRS as a sum of weighted complex exponentials, where weights are binary. Identifying the partitions, the number of which is equal to the number of complex exponentials and equal to the number of unit cells in the IRS. Searching through the partitions and selecting the optimum partition, where assigning weights 104a as 1 and 1, or assigning weights 104b as any two distinct complex numbers per element. Finally step 105a or 105b involves computing the weights. The method discloses two strategies in mitigating grating lobe of an IRS. The method is extremely fast and is guaranteed to return the optimal solution with grating lobe mitigation.

Claims

1. A method of computing weights for a 1-bit phase shifts case of beamforming from an intelligent reflecting surface (IRS), the method comprising: writing a normalized array factor G of the IRS as a sum of weighted complex exponentials, where weights are binary and the phase shifts are constrained to be either 0 or 180, the normalized array factor G given by: $G\left(,\right)=\frac{1}{\mathrm{MN}}\underset{m=1}{\overset{M}{.Math.}}\underset{n=1}{\overset{N}{.Math.}}{w}_{m,n}{e}^{j{}_{m,n}\left(,\right)},\mathrm{where},$ ${}_{m,n}\left(,\right)=\frac{2d}{}\left(-m\sin \cos -n\sin \sin +m\sin {}_{\mathrm{in}}\cos {}_{\mathrm{in}}+n\sin {}_{\mathrm{in}}\sin {}_{\mathrm{in}}\right),$ where d is the inter-cell spacing, and is the wavelength of the incident wave; identifying the partitions, the number of which is equal to the number of complex exponentials, and equal to the number of unit cells in the IRS; searching through the partitions and selecting the optimum partition, wherein selecting the optimum partition comprises assigning weights as 1 and 1, or assigning weights as any two distinct complex numbers per element; and computing the weights.

2. The method as claimed in claim 1, wherein the computing comprises: providing a set of non-zero complex numbers z.sub.1, . . . z.sub.n, wherein a maximum value thereof is set to 0; setting i=1; computing for i=1 to n, .sub.i=arg z.sub.i; setting w.sub.j=1 for all j for which arg z.sub.j[.sub.i, .sub.i+], else set w.sub.j=1; computing g=|w.sub.1z.sub.1+ . . . w.sub.N z.sub.N| setting max to g if g>max, and updating the optimal weights accordingly; and returning the optimal weights.

3. The method as claimed in claim 2, wherein the computing comprises: providing a set of non-zero complex numbers z.sub.1, . . . z.sub.n, and constraint sets {a.sub.1, b.sub.1}, . . . {a.sub.n, b.sub.n} for each of the weights, where a.sub.ib.sub.i for all i; computing z.sub.1, . . . z.sub.n, z.sub.n+1 as $z_i^{}\text{?}\left(\frac{a_i-b_i}{2}\right)z_{i}i\text{?}1,.Math.n,$ $z_{n+1}^{}=\text{?}\left(\frac{a_i-b_i}{2}\right)z_i\text{?};$ $\text{?}\text{indicates text missing or illegible when filed}$ applying steps (111) to (117) to the set z.sub.1, . . . z.sub.n, z.sub.n+1 and obtaining weights as [{tilde over (y)}.sub.1 . . . {tilde over (y)}.sub.n {tilde over (y)}.sub.n+1]; setting i=1 if {tilde over (y)}.sub.n+1=1 (124); setting {tilde over (y)}.sub.i{tilde over (y)}.sub.i for i=1 to n; computing optimal weights [{tilde over (w)}.sub.1 . . . {tilde over (w)}.sub.n] as $\text{?}=\left(\frac{\text{?}}{2}\right)+\text{?}\left(\frac{\text{?}}{2}\right);$ $\text{?}\text{indicates text missing or illegible when filed}$ and returning the optimal weights.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] The invention has other advantages and features, which will be more readily apparent from the following detailed description of the invention and the appended claims, when taken in conjunction with the accompanying drawings, in which:

[0012] FIG. 1A illustrates a method of computing weights for a beamforming algorithm from an intelligent reflecting surface (IRS).

[0013] FIG. 1B illustrates the steps for computing optimum weights where the weights assigned to the complex exponentials in may be 1 and 1.

[0014] FIG. 1C illustrates the steps for computing optimum weights where the weights assigned to any two distinct complex numbers per element.

[0015] FIG. 2 shows a schematic diagram of a 55 IRS, with the incident beam wave vector (spherical coordinates (.sub.in, .sub.in)) represented in blue and the reflected beam wave vector (spherical coordinates (.sub.0, .sub.0)) represented in red.

[0016] FIG. 3 shows complex arg and plane with z.sub.is on the unit circle; in (a) the assignment of weights 1 to z.sub.3, z.sub.4 maximizes |G|, while in (b) the assignment of weight 1 to z.sub.4 maximizes |G|. The blue dashed lines indicate the optimal partitioning for weight assignments in each case. (c) An example where n=7 and z.sub.1, . . . z.sub.7 all lie on the unit circle. The red and blue separating lines both give rise to the same partitions, A={z.sub.1, z.sub.3, z.sub.4} and B={z.sub.2, z.sub.5, z.sub.6, z.sub.7}. Further, the set {z.sub.j|arg z.sub.2arg z.sub.j<arg z.sub.2+} is precisely B. The blue line can be thought of as having angle infinitesimally lesser than arg z.sub.2.

[0017] FIG. 4 shows scatter plots of z.sub.m,n along with assignment of weights due to (a) thresholding method (b) OPA. The dashed lines indicate the separating line in each case.

[0018] FIG. 5 shows the distribution of optimal weights on IRS and the corresponding normalized radiation pattern, for (a) (.sub.in, .sub.in)=(45, 180) and (.sub.0, .sub.0)=(30, 0) (b) (.sub.in, .sub.in)=(30, 225) and (.sub.0, .sub.0)=(15, 45).

[0019] FIG. 6 shows two different alignment scenarios of a vertically deployed 55 IRS (x-y plane) with respect to the ground (x-z plane): (a) {circumflex over (x)}, {circumflex over (x)} are parallel, and (b) {circumflex over (x)}, {circumflex over (x)} are at an angle.

[0020] FIG. 7 shows the radiation patterns for .sub.in=0, .sub.0=45, .sub.0=0, .sub.in=180 in a 3030 IRS: (a) k=0 (SLL=0 dB) (b) k=0.1 (SLL=2 dB) (c) k=0.3 (SLL=7.6 dB) (d) k=0.5 (SLL=10.9 dB).

[0021] FIG. 8 shows the radiation patterns along the xz plane corresponding to 3030 IRS operating at normal incidence, for various .sub.0.

[0022] FIG. 9 shows the proof of Theorem 2.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0023] While the invention has been disclosed with reference to certain embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted without departing from the scope of the invention. In addition, many modifications may be made to adapt to a particular situation or material to the teachings of the invention without departing from its scope.

[0024] Throughout the specification and claims, the following terms take the meanings explicitly associated herein unless the context clearly dictates otherwise. The meaning of a, an, and the include plural references. The meaning of in includes in and on. Referring to the drawings, like numbers indicate like parts throughout the views. Additionally, a reference to the singular includes a reference to the plural unless otherwise stated or inconsistent with the disclosure herein.

[0025] The invention in its various embodiments discloses a method 100 of computing weights for a 1-bit phase shifts case of beamforming from an intelligent reflecting surface (IRS) thereof. The method 100 is configured to solve the one bit beamforming problem that guaranteed to return the optimal solution in minimum time due to the linear computational complexity of the algorithms.

[0026] As illustrated in FIG. 1A, the method 100 includes the steps of: writing 101 a normalized array factor G of the IRS as a sum of weighted complex exponentials, where weights are binary and the phase shifts are constrained to be either 0 or 180, where the normalized array factor G given by:

[00005]$G\left(,\right)=\frac{1}{\mathrm{MN}}\underset{m=1}{\overset{M}{.Math.}}\underset{n=1}{\overset{N}{.Math.}}{w}_{m,n}{e}^{j{}_{m,n}\left(,\right)},\mathrm{where},$${}_{m,n}\left(,\right)=\frac{2d}{}\left(-m\sin \cos -n\sin \sin +m\sin {}_{\mathrm{in}}\cos {}_{\mathrm{in}}+n\sin {}_{\mathrm{in}}\sin {}_{\mathrm{in}}\right),$

where d is the inter-cell spacing, and is the wavelength of the incident wave.

[0027] The next step involves identifying 102 the partitions, the number of which is equal to the number of complex exponentials and equal to the number of unit cells in the IRS. The method then includes searching 103 through the partitions and selecting the optimum partition. Selecting the optimum partition comprises assigning weights 104a as 1 and 1, or assigning weights 104b as any two distinct complex numbers per element. The final step 105a, or 105b involves computing the weights.

[0028] As illustrated in FIG. 1B, the steps for computing optimum weights where the weights assigned to the complex exponentials in may be 1 and 1 according to step 105a includes of providing 111 a set of non-zero complex numbers z.sub.1, . . . z.sub.n followed by setting max to 0. The next step 112 involves initializing i to 1 and if 113 i is greater than 0 and less than or equal to n, .sub.i=arg z.sub.i is computed, else the optimal weight is returned 117. After computing the value of .sub.i 113, w.sub.j is set to 1 for all j for which arg z.sub.j[.sub.i, .sub.i+], else w.sub.j is set to 1 114. Next the value of g is computed 115 where g=|w.sub.1z.sub.1+ . . . w.sub.N z.sub.N|. Further, 116 if the value of g is greater than max, the value of max is set to g and the optimal weights are updated as [w.sub.1 . . . w.sub.n], else the optimal weight is returned 117. Finally the value of i is incremented by 1 and the steps 113-116 is repeated until i equals n. As illustrated in FIG. 1C, the steps for computing optimum weights where assigning weights as any two distinct complex numbers per element 105b includes providing 121 a set of non-zero complex numbers z.sub.1, . . . z.sub.n, and constraint sets {a.sub.1, b.sub.1}, . . . {a.sub.n,b.sub.n} for each of the weights, where a.sub.ib.sub.i for all i. Next step involves in computing 122 z.sub.1, . . . z.sub.n, z.sub.n+1 as

[00006]$\text{?}$$\text{?}\text{indicates text missing or illegible when filed}$

Further 123, the steps 111-117 as already illustrated in FIG. 1B are applied to the set z.sub.1, . . . z.sub.n, z.sub.n+1 and the optimal weights are obtained as [{tilde over (y)}.sub.1 . . . {tilde over (y)}.sub.n {tilde over (y)}.sub.n+1]. The next step proceeds to check for the condition if 124 {tilde over (y)}.sub.n+1 equal to 1. If the condition is false, the optimal weight is computed 126 a

[00007]${\tilde{w}}_i=\left(\frac{a_i+b_i}{2}\right)+{\tilde{y}}_i\left(\frac{a_i-b_i}{2}\right)$

and the same is returned 127, else the value of i is set to 1. Further if 125 the value of i is greater than 1 and less than or equal to n, the value of {tilde over (y)}.sub.i is set to {tilde over (y)}.sub.i and i is incremented by 1, else the optimal weight is computed 126 as

[00008]${\tilde{w}}_i=\left(\frac{a_i+b_i}{2}\right)+{\tilde{y}}_i\left(\frac{a_i-b_i}{2}\right)$

and the same is returned 127. The step 125 is repeated until i equals n.

[0029] In various embodiments, the invention discloses strategies to mitigate grating lobes, as their presence is detrimental to the intended operation of an IRS. The invention further includes a vertically oriented IRS (i.e. with its surface normal parallel to the ground), and an incident beam emitted by a transmitter with the wave vector parallel to the ground. There arise two scenarios as: Array x-axis parallel with respect to the ground (.sub.0=0 and .sub.in=180) and array x-axis tilted with respect to the ground (.sub.0=0 and .sub.in180).

[0030] In various embodiments, the invention discloses two strategies for mitigating the issue of grating lobes while aligning the IRS axis with the ground. In the first strategy, the layout of an IRS is constructed by arraying its elements in a triangular lattice instead of rectangular where it can be shown that .sub.0=0 and .sub.in=180 becomes viable for beamforming without encountering the issue of grating lobes. In the second strategy of prephasing, symmetry breaking technique is used to eliminate the grating lobes issue at both normal or nonnormal incidence angle.

[0031] The invention has multiple advantages as illustrated further. The method solves the one bit beamforming problem in a computationally efficient way. Thus, due to the linear computational complexity of the problem, the method is extremely fast to deploy in practice and is guaranteed to return the optimal solution. The invention provides grating lobe mitigation where these lobes can lead to security/privacy issues in the context of wireless communications.

EXAMPLES

Example 1: Optimum Beamforming and Grating Lobe Mitigation for IRS

Optimum Beamforming Algorithm & Generalizations

[0032] Problem Statement: The IRS is modeled as an MN rectangular grid of equispaced unit cells in the x-y plane. It is illumined by an incident electromagnetic plane wave in the spherical direction (.sub.in, .sub.in) in accordance with the FSA convention, as seen in FIG. 2. Each cell imparts a complex valued reflection coefficient (called the cell weight), w.sub.m,n, to the incident beam. In order to capture realistic IRS implementations we assume that the weights take on discrete values, and therefore are modeled as belonging to a discrete alphabet, S.sub.m,n (e.g. in many practical implementations, S.sub.m,n={1, 1}).

[0033] The normalized array factor G given by:

[00009]$\begin{array}{cc}G\left(,\right)=\frac{1}{\mathrm{MN}}\underset{m=1}{\overset{M}{.Math.}}\underset{n=1}{\overset{N}{.Math.}}{w}_{m,n}{e}^{j{}_{m,n}\left(,\right)},& \left(1\right)\end{array}$$\mathrm{where}$$\begin{array}{cc}{}_{m,n}\left(,\right)=\frac{2d}{}\left(-m\sin \cos -n\sin \sin +m\sin {}_{\mathrm{in}}\cos {}_{\mathrm{in}}+n\sin {}_{\mathrm{in}}\sin {}_{\mathrm{in}}\right),& \left(2\right)\end{array}$

where d is the inter-cell spacing, and is the wavelength of the incident wave. The array factor is a very useful quantity to compute since it gives the far-zone electric field of the array when multiplied by the radiation pattern of the constitutive array cell (ignoring mutual coupling). We now formally state the problem of beam forming in a certain direction (.sub.0, .sub.0) as:

[00010]$\begin{array}{cc}\underset{w_{m,n}}{\max }{.Math.G\left({}_0,{}_0\right).Math.}^{2}s.t.w_{m,n}{}_{m,n},m,n& \left(3\right)\end{array}$

This is a discrete optimization problem since the weights (w.sub.m,n) belong to a finite set. We note that the problem of beamforming can take on many more sophisticated forms as compared to Eq. (3) above; in this work we focus on the simpler, noise-free analysis.

[0034] Thresholding Method: Thresholding (also known as quantization) is the most common discrete beamforming algorithm used in the literature. Consider the case where the allowed values for each cell are: S.sub.m,n={1,1}, i.e. a 1-bit IRS, which corresponds to each unit cell having phase shift of 0 or 180 (here, only the phase difference between the states is relevant). In the thresholding method, the main idea is to first obtain the optimal solution to the continuous version of the problem (i.e. we solve Eq. (3) with the constraint as w.sub.m,nC, |w.sub.m,n|=1). Since Eq. (1) is a summation of weighted complex exponentials, this optimal solution is obtained by simply taking w.sub.m,n=exp (j.sub.m,n(.sub.0, .sub.0)), which yields |G(.sub.0, .sub.0)|=MN. The solution is unique up to multiplication by a unit-magnitude complex number. Once the continuous solution is obtained, we discretize the weights by mapping them to whichever among {1,1} they are closest to. The complete methodology is presented in Algorithm 1.

TABLE-US-00001 Algorithm 1 Thresholding Algorithm Require: .sub.in, .sub.in: .sub.0, .sub.0 1: for 1 m M, 1 n N do 2:Compute w.sub.m,n = exp (j.sub.m,n(.sub.0, .sub.0) [00011]$3:\mathrm{if}\text{?}\text{?}\left(-\frac{\text{?}}{2},\frac{\text{?}}{2}\right)\mathrm{then}$ 4:{tilde over (w)}.sub.m,n 1 5:else 6:{tilde over (w)}.sub.m,n 1 7:end if 8: end for 9: return discrete weights {tilde over (w)}.sub.m,n [00012]$\text{?}\text{indicates text missing or illegible when filed}$
The thresholding method is popular on account of being intuitive and easy to implement. However, due to its heuristic nature it does not have any guarantees of optimality. Further, it is not clear how to generalize the algorithm if the elements of S.sub.m,n have unequal amplitude. These observations pave the way for our proposed method, which we present next.

[0035] Optimal Partitioning Algorithm: The proposed method is termed the Optimal Partitioning Algorithm (OPA), which is based on the following intuition. The sum of complex exponentials in Eq. (1) can be re-written as G=.sub.iw.sub.iz.sub.i, where w.sub.i, z.sub.i represent the weights and angle dependent phase terms, respectively. For simplicity, we assume the z.sub.is to be unit-magnitude complex numbers, and consider the following two cases. (i) Consider the z.sub.is as shown in FIG. 3(a). To maximize |G| as per Eq. (3), the weight w.sub.i associated with each z.sub.i must be chosen appropriately. Since the w.sub.is are restricted to {1, 1}, it follows that |G| is maximized when all the z.sub.is in the left-half of the plane are assigned w.sub.i=1 and those in the right half plane are assigned w.sub.i=1 (or vice-versa). In effect, we have found a partitioning line (in this case the y-axis) that separates the assignment of the weights. The resulting weight assignment is equivalent to the thresholding algorithm. (ii) Consider the z.sub.is as shown in as shown in FIG. 3(b). As can be seen, the y-axis no longer partitions the weights correctly and instead, a different weight assignment gives the optimal sum. Thus, the thresholding algorithm would have given a suboptimal weight assignment. We note that this optimal assignment can also be conceived of as the result of an optimal partitioning line as indicated by the dashed blue lines in FIG. 3.

[0036] The above intuition of an optimal partitioning is formalized via the following two theorems.

[0037] Theorem 1: Let z.sub.1, . . . z.sub.n be arbitrary non-zero complex numbers, and let {tilde over (w)}.sub.1, . . . {tilde over (w)}.sub.n be an optimal solution to the optimization problem.

[00013]$\begin{array}{cc}\underset{w_i}{\max }.Math.w_1{z}_1+.Math.+w_n{z}_n.Math.s.t.w_i\left\{1,-1\right\},i=1,.Math.n& \left(4\right)\end{array}$

[0038] Then, there exists a line l passing through the origin with the following properties: [0039] 1) does not contain any z.sub.i. [0040] 2) {tilde over (w)}.sub.i=1 for all z.sub.i lying on one side of the line, and [0041] {tilde over (w)}.sub.i=1 for all z.sub.i on the other side.

[0042] The above theorem asserts that if an optimal set of weights exists, then there exists a separating line passing through the origin, which partitions the set {z.sub.1, . . . z.sub.n} into two sets A and B, where {tilde over (w)}.sub.i=1 for each z.sub.iA, and {tilde over (w)}.sub.i=1 for each z.sub.iB. However, we know that an optimal solution exists because the feasible set is finite. Therefore, an optimal separating line definitely exists, and our goal should be to find one such line. Once the partition {A, B} is obtained, the assignment of 1 and 1 to each set is arbitrary, as replacing {tilde over (w)}.sub.i with {tilde over (w)}.sub.i for each i=1, . . . n will yield the same value of |.sub.iw.sub.iz.sub.i|.

[0043] The natural question that arises is: how many partitions should we check? We must check all partitions that arise due to separating lines passing through the origin. However, multiple separating lines can lead to the same partition, as shown in FIG. 2c. In particular, one has the freedom to rotate a separating line anticlockwise about the origin without changing the partition, until it hits some z.sub.i. Therefore, the partition obtained by any separating line is the same as the partition obtained by a separating line whose angle with the x axis is infinitesimally lesser than the argument of some z.sub.i. This intuition is formalized in the following theorem.

[0044] Theorem 2: A partition {A, B} of {z.sub.1, . . . z.sub.n} arises due to a separating line passing through the origin not containing any z.sub.i, if and only if either A or B is of the form

[00014]$\left\{z_j|\arg z_i\arg z_j<\arg z_i+\right\}$

for some i{1, . . . n}.

[0045] Since there are n complex numbers z.sub.i, only n such separating lines (and therefore only n such partitions) need to be investigated. So, an algorithm that seeks the optimal partitioning will have linear time complexity. Finally, we remark that the summations in Eq. (1) and Eq. (4) are identical with z.sub.i being equivalent to e.sup.jm,n(,). Theorems 1 and 2 can now be used to formulate the Optimal Partitioning Algorithm (OPA), which computes the optimal weights for the optimization problem in Eq. (3) with S.sub.m,n={1, 1}. The complete method is displayed in Algorithm 2; since we only need to check n=MN partitions, OPA will find the optimal weights in time O(MN). The optimality of the obtained solution is preserved up to a change of sign, i.e. if {{tilde over (w)}.sub.i} are optimal, then so are {{tilde over (w)}.sub.i}, since both sets give the same value of |G|.

TABLE-US-00002 Algorithm 2 Optimal Partitioning Algorithm (OPA) Require: Non-zero complex numbers z.sub.l,...z.sub.n 1: max 0 2: for i = 1 to n do 3: Compute .sub.i = arg .sub.i. 4: Set w.sub.j = 1 for all j such that arg x.sub.j ( ) and w.sub.j = 1 for others. 5: Compute g = | + ... | 6: if g > max then 7: max g 8: optimal weights [w.sub.j ... w.sub.n] 9: end if 10: end for 11: return optimal weights indicates data missing or illegible when filed

[0046] Generalized Optimal Partitioning Algorithm: In the OPA previously stated, we had assumed the discrete alphabet as S.sub.m,n={1, 1}. Next, we generalize OPA for the case where the discrete alphabet consists of two arbitrary complex numbers. In many practical situations, such as in metasurface based implementations of IRS structures, the reflection coefficients have less than unity magnitude. Thus, it is important to allow |w.sub.i|<1 in the beamforming algorithms to cater to such scenarios. The optimization problem is formulated as:

[00015]$\begin{array}{cc}\underset{w_i}{\max }.Math.\underset{i=1}{\overset{n}{.Math.}}{w}_i{z}_i.Math.s.t.w_i\left\{a_i,b_i\right\},i=1,.Math.n.& \left(5\right)\end{array}$

[0047] To solve this problem, we introduce a new scaled variable, y.sub.i, such that

[00016]$w_i=\left(\frac{a_i+b_i}{2}\right)+y_i\left(\frac{a_i-b_i}{2}\right),$

and rewrite the summation in Eq. (5) as:

[00017]$\begin{array}{cc}\text{?}& \left(6\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

where

[00018]$z_i^{}=\left(\frac{a_i+b_i}{2}\right)z_i$

for all i=1, . . . n, and

[00019]$z_{n+1}^{}={.Math.}_{i=1}^n\left(\frac{a_i+b_i}{2}\right).$

Due to the mapping y.sub.i=1.fwdarw.w.sub.i=a.sub.i and y.sub.i=1.fwdarw.w.sub.i=b.sub.i, the optimization problem of Eq. (5) is equivalent to the following problem:

[00020]$\begin{array}{cc}\underset{\text{?}}{\max }.Math.\text{?}{y}_i{z}_i^{}.Math.& \left(7\right)\end{array}$$s.t.y_i\left\{1,-1\right\},i=1\text{?}n$$y_{n+1}=1\text{?}$$\text{?}\text{indicates text missing or illegible when filed}$

[0048] The above problem looks almost the same as the problem in Eq. (4), except for the constraint y.sub.n+1=1. Since the solution given by the OPA to Eq. (4) is preserved up to a sign, we can always find an optimal solution to the above problem (i.e. Eq. (7)) by applying the OPA and then using the freedom in the assignment of an overall sign to ensure that y.sub.n+1=1. Thus, we have obtained the Generalized OPA (gOPA), which is summarized in Algorithm 3.

TABLE-US-00003 Algorithm 3 Generalized OPA (gOPA) Require: Non-zero complex numbers z.sub.1, ... z.sub.n, and the con- straint sets {a.sub.1, b.sub.1}, ... {a.sub.n, b.sub.n} for each of the weights (where a.sub.i b.sub.i for all i). 1: Compute z.sub.1 ... z.sub.n, z.sub.n+1 as: [00021]$\text{?}=\left(\frac{a_i-b_i}{2}\right)z_{i}i=1,\text{?}$ [00022]$\text{?}=\text{?}\left(\frac{a_i+b_i}{2}\right)\text{?}$ 2: Apply OPA to the set z.sub.1, ... z.sub.n+1, and get optimal weights [{tilde over (y)}.sub.1 ... {tilde over (y)}.sub.n {tilde over (y)}.sub.n+1] 3: if {tilde over (y)}.sub.n+1 = 1 then 4:for i = 1 to n do 5:{tilde over (y)}.sub.i {tilde over (y)}.sub.i 6:end for 7: end if 8: Compute the optimal weights {tilde over (w)}.sub.1, ... {tilde over (w)}.sub.n as [00023]$\text{?}=\left(\frac{a_i+b_i}{2}\right)+\text{?}\left(\frac{a_i-b_i}{2}\right)$ 9: return optimal weights [{tilde over (w)}.sub.1 ... {tilde over (w)}.sub.n] [00024]$\text{?}\text{indicates text missing or illegible when filed}$

[0049] Results for optimal beamforming: In this Section, we provide various simulation results as well as theoretical explanations in support of the efficacy of our proposed method. In all simulations, we take the interelement spacing d=/2.

[0050] OPA versus Thresholding: We first compare the proposed OPA with the existing thresholding method. The hypothesis is that the thresholding method does not always return the optimal weights, and we provide an example that shows exactly that. Consider a 33 array, with incident direction (.sub.in, .sub.in)=(45, 215) and the desired direction (.sub.0, .sub.0)=(30, 35). All weights are constrained to the set {1,1}. From the weights returned by the thresholding method, we obtain |G(.sub.0, .sub.0)|.sup.2=3.86. dB, whereas from the weights obtained by OPA, we obtain |G(.sub.0, .sub.0)|.sup.2=2.95 dB (normalized by the number of elements, MN). FIG. 4 shows the scatter plots the weight assignment for each method. Clearly the OPA results are superior and this example confirms our hypothesis.

[0051] Visualization of weights: Next, we visualize the output of the OPA by plotting the weights distribution across the IRS, and the resulting beam patterns for a couple of sample cases. We fix the array size to be 3030, and choose .sub.in=30, .sub.0=15 and .sub.0=45, .sub.in=225. As seen in FIG. 5(a), the distribution consists of diagonal strips of 1 and 1, whose angle with the y axis (vertical axis) is precisely .sub.in. Intuitively, this makes sense because the strips are precisely the locus of points on the IRS that get the same initial phase due to the incident beam. Next, we consider the case of .sub.in=45, .sub.0=30 and .sub.0=0, .sub.in=180. As seen in FIG. 5(a), the distribution consists of vertical strips of 1 and 1 as expected. However, in addition to the expected reflected beam at .sub.0=30, we also observe a second peak of equal strength around .sub.0=5. Understanding the existence of this second peak is of great importance, and we do so in the following sub-section.

[0052] Grating lobe considerations: Having visualized several weight assignments and radiation patterns, we investigate a critical issue in be (8) ming concerning the presence of grating lobes in the radiation pattern. A grating lobe is an undesired lobe with the same intensity as the main lobe (i.e. has sidelobe level (SLL) equal to 0 dB). Such a lobe is seen in FIG. 5(b); these lobes can lead to security/privacy issues in the context of wireless communications and are undesirable. We now derive theoretical conditions under which a grating lobe is guaranteed to exist. By examining the array factor expression in Eq. (1), we can see that given a main lobe at (.sub.0, .sub.0), a grating lobe will appear at (*, *) if the following condition holds for all m, n:

[00025]${}_{m,n}\left({}^{*},{}^{*}\right)=-{}_{m,n}\left({}_0,{}_0\right)+\mathrm{am}+\mathrm{bn},$

where a and b are even integers, i.e. |G(*, *)|=|G(.sub.0, .sub.0)|. Further, using the phase expression from Eq. (2) and comparing the coefficients of m, n on both sides, Eq. (8) gives:

[00026]$\begin{array}{cc}-2\sin {}_{\mathrm{in}}\cos {}_{\mathrm{in}}-\sin {}_0\cos {}_0+\frac{a}{2d}=\sin {}^{*}\cos {}^{*}\left(=A\right)\text{?}& \left(9a\right)\end{array}$$\begin{array}{cc}-2\sin {}_{\mathrm{in}}\sin {}_{\mathrm{in}}-\sin {}_0\cos {}_0+\frac{b}{2d}=\sin {}^{*}\sin {}^{*}\left(=B\right).& \left(9b\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0053] To check if there is a (*, *) that satisfies this, we must find an a, b such that A.sup.2+B.sup.2=sin.sup.2 *1, with A, B from Eq. (9), holds true. If it does, then we can compute *=arcsin {square root over (A.sup.2+B.sup.2)} and *=arccos {square root over (A.sup.2+B.sup.2)}. If the resultant (*, *) are different from (.sub.0, .sub.0), then we have a grating lobe.

[0054] In order to graphically visualize the algebraic conditions for the existence of a grating lobe (i.e. Eq. (9)), we consider several cases. For ease of visualization, we fix the incidence beam angle and sweep the reflected beam angle, while maintaining the incident and reflected wavevectors to be in the same plane. The heatmaps (not shown here) were generated, showing the region of (.sub.0, .sub.0) for which a grating lobe exists, i.e. for given incident and reflected beam directions, a different (*, *) exists for which the condition in Eq. (9) holds, i.e the regions free of grating lobes. Note that (, ) is equivalent to (, +); thus the left half of the plots, where .sub.0<0, denote the reflected beam going in the forward scattering direction.

[0055] We verified the theoretical plots by performing simulations for various arrays, where the optimal weights are obtained using OPA. The simulated heatmaps increasingly agree with the theoretical plot generated using the equation 9, as the array sizes grow. We observed bands around .sub.0=45 the simulation, in addition to certain other small regions of non-zero SLL. This happens because the mainlobe does not form exactly at (.sub.0, .sub.0), but rather at a direction close to it, and we refer to angle between the desired direction and the actual direction in which the mainlobe occurs as the beamforming error. We observed that even when .sub.0 is close to but not exactly 45 (represented by the blue band), the sidelobe level is not 0 dB, which seems to contradict the theoretical calculation. However, what actually happens is that the mainlobe occurs at 45 rather than the actual .sub.0, and indeed 45 corresponds to non-zero SLL according to the calculation. As the array size increases, the beamforming error also decreases, which can be seen by the band becoming narrower.

[0056] Grating lobe mitigation: Having identified the existence of grating lobes and confirmed them via simulations, we now seek to propose strategies to mitigate these lobes, as their presence is detrimental to the intended operation of an IRS. As we will demonstrate, the proposed OPA and gOPA algorithms are well suited to implement these mitigation strategies. For sake of definiteness, we only consider 1-bit IRS implementations in this discussion.

[0057] We consider a vertically oriented IRS (i.e. with its surface normal parallel to the ground), and an incident beam emitted by a transmitter with the wavevector parallel to the ground. It is desired to beamform to a mobile user in the same horizontal plane, i.e. .sub.in=.sub.0, as depicted in FIG. 6. There arise two scenarios:

[0058] Array x-axis parallel with respect to the ground: This amounts to .sub.0=0 and .sub.in=180. As shown by theoretical calculations for .sub.0=0, a grating lobe always exists, regardless of the value of .sub.in. It is easy to see this theoretically, as shown below. Eq. (9) simplifies to:

[00027]$\begin{array}{cc}2\sin {}_{in}-\sin {}_0+a=\sin {}^{*}\cos {}^{*}& \left(10a\right)\end{array}$$\begin{array}{cc}b=\sin {}^{*}\sin {}^{*}.& \left(10b\right)\end{array}$

[0059] Clearly if b=0 and a is chosen to be 2, 0 or 2, depending on whether (2 sin .sub.insin .sub.0) lies in [3,1], [1, 1] or [1, 3] respectively, then a grating lobe exists for *=0 and *=arcsin (2 sin .sub.insin .sub.0+a). The lobe doesn't exist only when *=.sub.0, which happens for two particular angles (one of them being .sub.0=.sub.in). Not only does there exist a grating lobe for almost all values of .sub.0, the grating lobe also lies along the xz plane, as *=0.

[0060] Array x-axis tilted with respect to the ground: When .sub.in180, the issue of grating lobes can be circumvented for some user locations. In particular, we see that if .sub.in=30, a user can move in the entire half-range .sub.0=[0, 90] for a tilted IRS with .sub.0=30 and .sub.in=210. Of course, this range is curtailed depending on the size of the array. It is often not convenient to tilt an IRS from an implementation perspective, because most deployments are likely to be on walls or sides of buildings, where a horizontal formfactor is more suitable. Therefore, we outline two strategies that mitigating the issue of grating lobes while aligning the IRS axis with the ground.

[0061] Triangular lattice for IRS layout: In all the examples considered so far, the layout of the constitutive elements was assumed to be rectangular (e.g. see FIG. 2). Instead, if we construct an IRS by arraying its elements in a triangular lattice, it can be shown that .sub.0=0 and .sub.in=180 becomes viable for beamforming without encountering the issue of grating lobes. The array factor is now modified as:

[00028]$\begin{array}{cc}G\left(,\right)=\frac{1}{\mathrm{MN}}\underset{m,n}{.Math.}{w}_{m,n}\text{?},& \left(11\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

where (,)=[sin cos sin sin cos ].sup.T and r.sub.m,n=md.sub.1+nd.sub.2, with 0nN and

[00029]$-.Math.\frac{n}{2}.Math.mM-.Math.\frac{n}{2}.Math..$

Here, d.sub.1=d[1 0 0].sup.T and

[00030]$d_2={d\left[\begin{array}{ccc}\frac{1}{2}& \frac{\sqrt{3}}{2}& 0\end{array}\right]}^T$

are the basis vectors for the lattice.

[0062] Analogous to the analysis in the case of the rectangular lattice, we can work out the conditions under which a grating lobe appears. The relations for a grating lobe at (*, *) are:

[00031]$\begin{array}{cc}-2\sin \text{?}-\sin \text{?}+\frac{a}{2d}=\sin \text{?}\cos \text{?}& \left(12a\right)\end{array}$$\begin{array}{cc}-2\sin \text{?}-\sin \text{?}\sin \text{?}+\frac{}{2d}(\frac{-a+2b}{\sqrt{3}}\text{?}=\sin \text{?}\sin \text{?}& \left(12b\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

where a, b are even integers, as in Eq. (9).

[0063] Substituting .sub.in=.sub.0+ in these relations gives us the theoretical heatmaps and sidelobe levels after the application of OPA for a finite size IRS. A major difference between the SLL heatmaps of the two different lattices is that .sub.0=0 gives a wide range of grating-lobe free operation for triangular lattices, which is not the case in rectangular arrays. Thus, the triangular lattice enables the alignment of the IRS axis with the ground while mitigating the grating lobe issue.

[0064] Prephasing technique for elimination of grating lobes: In the grating lobe considerations considered so far, a nonzero incidence angle was assumed. However, there may be deployment scenarios where keeping .sub.in=0 is desired, since this opens up the possibility of steering the reflected beam in either quadrant (i.e. .sub.0>0 or .sub.0<0). However, this presents a fundamental problem, because when: (a) .sub.in=0, and (b) the weights are constrained to {1,1}, we can show that |G(, )|=|G(, )| for all (, ) and for both types of lattices:

[00032]$\begin{array}{cc}G\left(-\text{?},\text{?}\right)=\frac{1}{\mathrm{MN}}\text{?}=\frac{1}{\mathrm{MN}}\text{?}.Math.\text{?}=\text{?}.& \left(13\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0065] The key argument we used is that w.sub.m,n=w.sub.m,n, since each w.sub.m,nRm, n. This symmetry means that there will always be a grating lobe for normal incidence. As earlier work has identified, if the primary assumption of w.sub.m,nR is attacked (for e.g. by constraining some of the weights to {j,j}), we arrive at a technique of symmetry breaking. This technique is called prephasing.

[0066] There are several techniques to implement prephasing. For instance, adding random phase perturbations to each element of the IRS also helps break the symmetry [15]. Another approach [17] involves shifting subsets of the IRS elements in the normal direction by a small amount. Yet another possibility is to choose a fraction k of tuples from {1, . . . , M}{1, . . . N} (denoting this set as P), and to then solve the following optimization problem (indeed, [14] does so with k=0.5):

[00033]$\begin{array}{cc}\underset{w_{m,n}}{\max }.Math.G\left({}_0,{}_0\right).Math.& \left(14\right)\end{array}$$s.t.w_{m,n}\left\{j,-j\right\},\left(m,n\right)$$w_{m,n}\left\{1,-1\right\},\left(m,n\right).$

[0067] In general, there can be more than two prephases [18]. Formally, if the prephase set is {.sub.1, . . . .sub.P}, and if {P.sub.i}.sup.p.sub.i=1 is a partition of the IRS such that each unit cell in P.sub.i gets the prephase .sub.i, then the optimization problem becomes

[00034]$\begin{array}{cc}\underset{w_{m,n}}{\max }.Math.G\left({}_0,{}_0\right).Math.& \left(15\right)\end{array}$$s.t.w_{m,n}\left\{e^{j{}_i},e^{j\left({}_i+\right)}\right\},\left(m,n\right){}_i,i=1,.Math.,p.$

[0068] Remarkably, this problem is custom made for solving by the proposed gOPA, as is evident by a comparison of the above equation with the gOPA formulation in Eq. (5). Even with the earlier techniques of random phase perturbations [15], the problem of determining the optimum weights for beamforming can be solved by the gOPA.

[0069] We implement the prephasing method as captured in Eq. (14), and implement the gOPA for various values of the prephasing fraction k. FIG. 7 shows the radiation pattern in the xz plane for several values of k, with the highest SLL suppression of 10.9 dB achieved for k=0.5 in a 3030 IRS. We also note that while SLL reduces with increasing k, the magnitude of the mainlobe remains the same. Thus, prephasing is a viable means of grating lobe mitigation while not sacrificing the mainlobe magnitude.

[0070] Next, we confirm the feasibility of scanning a single beam across space for (fixed) normal incidence. FIG. 8 shows the radiation patterns along the xz-plane, of a 3030 IRS in the scanning range [30, 30] spaced by intervals of 10. The set P is chosen randomly, with k=0.5. The worst-case SLL is observed to be 8.6 dB. We note that the SLL can be further improved by optimizing the set P itself by using evolutionary algorithms, however at a significant computational cost compared to our proposed method.

[0071] Finally, we comment on another remarkable outcome of the prephasing approach. While originally designed to eliminate the grating lobes issue at normal incidence, it turns out that it offers the opportunity to deploy the IRS at both normal or nonnormal incidence angle without any issue of grating lobes. We demonstrate this by applying the gOPA on a 3030 IRS with .sub.in=.sub.0=0 and investigate the behaviour w.r.t. incidence angle after implementing prephasing with k=0.5. We confirm grating lobe free operation at normal and non-normal incidence angles (with the exception for small regions at the corners), without having to tilt the IRS axis w.r.t. the ground.