Cross-Domain Dual-Functional OFDM Waveform
Design for Accurate Sensing/Positioning

An appropriate dual-functional waveform design is crucial[20], which is challenging due to the diverse requirements of sensing and communication functions. Specifically, sequences with good auto-correlation property are usually preferable for sensing and positioning applications, while communication symbols tend to be random and stochastic, making it challenging to ensure consistent auto-correlation properties. To address this problem, one promising representative is orthogonal frequency division multiplexing (OFDM) [20, 21, 22], which is widely adopted in current communication standards like the fourth-generation (4G) Long-Term Evolution LTE [23] and 5G new radio (NR) [24] thanks to the merits of OFDM signals, including robustness to frequency-selective fading and easy implementation. Despite of its randomness, the OFDM waveform possesses perfect auto-correlation property when using constant-amplitude constellations, e.g., phase-shift keying (PSK) [25]. Under such a waveform design, OFDM can readily support accurate sensing/positioning with marginal modifications to the existing infrastructure [26]. However, such an ideal auto-correlation property is no longer guaranteed when the quadrature amplitude modulation (QAM) format is employed for higher spectral efficiency [25, 27]. Moreover, for the application scenario which performs sensing and positioning in a broadcasting/scanning mode, whilst providing directional access to user terminals simultaneously [28, 29], the communication and sensing components should be non-overlapped in the time-frequency domain to avoid possible interference.

To tackle the aforementioned issues, a dual-functional OFDM waveform design with interleaved subcarriers, abbreviated as OFDM-IS, was explored in the existing literature, where the dual functions are allocated with orthogonal spectrum resources [30, 31, 32, 33, 34]. Specifically, in [30], the assignment and power allocation of OFDM subcarriers were optimized for the sensing and communication subsystems using a compound mutual-information (MI) based objective function, where both a radar-selfish and a balanced design strategies were developed. Another joint subcarrier and power allocation optimization strategy was proposed in [31] and [32], aiming to minimize the total power consumption under constraints on the MI metric for radar sensing and the data rate for communications. The work [33] further proposed a robust multi-carrier waveform design against imperfect channel state information, where the bit and power allocation strategies were optimized with a greedy algorithm. Rather than adopting the MI-related metrics for radar sensing, the study [34] optimized the joint subcarrier and power allocation strategy between the dual functions by minimizing the sidelobe-to-peak ratio in the radar range profile¹¹1The radar range profile is referred to as a one-dimensional correlation function of the sensing sequence., whilst ensuring an acceptable level of the communication data rate.

Unlike the aforementioned works which merely focused on the frequency- and power-domain characteristics, some studies extend the dual-functional waveform design to the time domain by involving multiple consecutive OFDM symbols [35, 36, 37, 38]. The work [35] optimized power allocation in a time-frequency range of interest to realize a favorable trade-off between sensing and communications with limited feedforward. In this study, however, the radar utilized the random and stochastic communication symbols for target detection, which limited the sensing performance. Another power allocation optimization was proposed in [36], aiming to maximize the compound signal-plus-distortion-and-noise ratio for sensing and communication subsystems. Since the time-frequency resources allocated for the two subsystems overlapped in the work [36], there may be significant interference between them. An optimum radar waveform was proposed in [37] to maximize the channel capacity by minimizing the distance between the communication symbols and the radar interference. Although this design further enhanced the capacity of the communication system, it neglected the required properties for the radar sequence. In [38], the optimum OFDM-IS design for dual-functional waveform is investigated in both time and frequency domains, and multiple resource element (RE) assignment strategies were proposed. These strategies can achieve large time-frequency radar aperture with a tiny fraction of OFDM resources, whose optimality, however, was not validated with sufficient theoretical derivations.

From the above discussions, most of the existing literature on OFDM-based dual-functional waveform design only consider subcarrier assignment and power allocation within a single OFDM symbol. In order to improve the speed resolution in radar sensing, however, the coherent processing interval usually have to be extended by incorporating multiple consecutive OFDM symbols [6]. Considering the time-varying characteristics of the channel in high-speed scenarios, e.g., autonomous driving, it is difficult to apply the resource allocation strategy within one single OFDM symbol to the extended time interval. Consequently, to ensure the accuracy of positioning and speed estimation, optimization of the waveform design across multiple consecutive OFDM symbols is necessary. The existing attempts for multiple symbols design mostly fail to keep the communication and sensing signals orthogonal and non-interfering with each other, and consequently the diverse design requirements of the two subsystems cannot be fully satisfied. To the authors’ best knowledge, the work [38] is the only existing reference involving multiple consecutive OFDM symbols that keeps the communication and sensing signals orthogonal by RE and subcarrier assignment, but the design of [38] suffers from some drawbacks as discussed above. Against this background, we propose a cross-domain dual-functional waveform design based on the OFDM-IS structure. The waveform coefficients are optimized across time, frequency, power and even delay-Doppler domains, where both a communication-centric and sensing-centric design methodologies are developed, respectively. The main contributions of this paper can be summarized as follows.

1. 1.

   Communication-centric waveform design: To enhance the sensing performance whilst ensuring the optimal data rate, a fraction of REs within each frame of multiple consecutive OFDM symbols are optimally assigned for communications through a water-filling algorithm based on prior knowledge of the time-frequency doubly-dispersive channel. The radar sensing components are then constituted by the concatenation of the remaining REs, where the energy budget is optimized in a subcarrier-wise manner to guarantee high peak-to-sidelobe ratio (PSLR) of the radar ambiguity function. The phase-frequency characteristic of the sensing component is further adjusted based on the branch-and-bound (BB) algorithm for the peak-to-average power ratio (PAPR) reduction.

2. 2.

   Sensing-centric waveform design: To ensure superior target sensing performance, we firstly construct a ‘locally’ perfect auto-correlation property by shaping the radar ambiguity function of the integrated waveform within a pre-defined region of interest (RoI) in the delay-Doppler domain. Next we approximate Hermitian symmetry for the 2-dimensional ambiguity function. The unit cells of the ambiguity function beyond RoI, referred to as ‘irrelevant cells’ for brevity, can then be directly manipulated to determine the power allocation pattern for sensing, where the REs with relatively low sensing power are employed for data transmission with water filling. Therein the irrelevant cells and the power allocation strategy for communications are jointly optimized for throughput enhancement in an alternating iterative manner.

3. 3.

   Numerical results are provided to validate the superiority of the proposed communication-centric and sensing-centric waveform designs. The proposed communication-centric waveform is capable of achieving a high PSLR within RoI and a low PAPR while maintaining the optimal achievable data rate, compared with its classical counterparts. On the other hand, while ensuring a locally perfect auto-correlation property, the proposed sensing-centric waveform can approximate the maximum achievable data rate, demonstrating the feasibility of the proposed alternating iterative algorithm. Moreover, the effects of the key parameters on sensing and communication performance are investigated, to provide valuable guidance for the implementation of the proposed sensing-centric waveform design.

The remainder of this paper is organized as follows. Section II introduces the system model. Section III defines the RoI in the ambiguity function and presents the proposed communication-centric waveform design. In Section IV, the sensing-centric waveform design is formulated as an optimization problem and an alternating iterative algorithm is developed to solve the problem. Numerical results are provided in Section V, which is followed by conclusions in Section VI.

In this paper, DFT$(\mathbf{X},1)$ and DFT$(\mathbf{X},2)$ denote performing discrete Fourier transformation (DFT) on every row and every column of matrix $\mathbf{X}$, respectively. IDFT$(\mathbf{X},1)$ and IDFT$(\mathbf{X},2)$ denote performing inverse DFT (IDFT) on every row and every column of $\mathbf{X}$, respectively. $(\mathbf{X})^{\mathrm{T}}$ and $(\mathbf{X})^{*}$ stand for the transpose and conjugate of $\mathbf{X}$, respectively. $|\mathbf{X}|$ and $\text{angle}(\mathbf{X})$ denote the element-wise amplitude and phase values of $\mathbf{X}$, respectively. $|\mathbf{X}|^{2}$ is a matrix that contains the element-wise absolute square values of $\mathbf{X}$, and $\|\mathbf{X}\|$ denotes the Frobenius norm of $\mathbf{X}$. $\mathbf{X}\odot\mathbf{Y}$ denotes the Hadamard product of matrices $\mathbf{X}$ and $\mathbf{Y}$. For a two-dimensional matrix $\mathbf{X}$, $X(m,k)$ denotes the element in the $m$-th row and the $k$-th column of $\mathbf{X}$. $\mathbf{1}$ denotes the all-one matrix. $x\sim\mathcal{CN}(0,\sigma^{2})$ represents the random variable $x$ that follows a complex Gaussian distribution with mean $0$ and variance $\sigma^{2}$. $\lfloor\cdot\rfloor$ is the floor operation that rounds a real number to the nearest integer less than or equal to the number. $\text{card}({\cal N})$ denotes the cardinality of set ${\cal N}$.

The OFDM-IS waveform is employed for target sensing and data transmission, and the corresponding transceiver model is depicted in Fig. 2. Specifically, a frame of $M$ consecutive OFDM symbols with $N_{\rm{c}}$ subcarriers is considered for each coherent processing interval and the $k$-th subcarrier of the $m$-th symbol is called the $(m,k)$-th RE. To avoid mutual interference between the sensing and communication, these two subsystems occupy different REs in each frame [34, 32, 30]. For clarity we employ the matrix $\mathbf{U}\in\mathbb{Z}^{M\times{N_{c}}}$ to indicate whether REs are selected for sensing or communication purpose

Let $\mathbf{S}\!\in\!\mathbb{C}^{M\times{N_{c}}}$ be the transmit signal matrix with $S(m,k)$ representing the modulated symbol on the $(m,k)$-th RE. Then, the sensing and communication transmit signal matrices, denoted as $\mathbf{S}_{\rm{r}}\!\in\!\mathbb{C}^{M\times{N_{c}}}$ and $\mathbf{S}_{\rm{c}}\!\in\!\mathbb{C}^{M\times{N_{c}}}$, can be expressed as

Define $\mathbf{P}_{\rm{r}}\!\in\!\mathbb{R}^{M\times{N_{c}}}$ and $\mathbf{P}_{\rm{c}}\!\in\!\mathbb{R}^{M\times{N_{c}}}$ as the power allocation matrices for sensing and communications, which can be written as ${P}_{\rm{r}}(m,k)\!=\!|{S}_{\rm{r}}(m,k)|^{2}$ and ${P}_{\rm{c}}(m,k)\!=\!|{S}_{\rm{c}}(m,k)|^{2}$, respectively. By modulating $\mathbf{S}_{\rm{r}}$ and $\mathbf{S}_{\rm{c}}$ on different REs of the OFDM frame, the time-domain transmit signals, $x_{\rm{i}}(t)$, $\rm{i}\in\{\rm{r},\rm{c}\}$, for sensing and communications, respectively, can be expressed as

where $\Delta f$ is the subcarrier spacing and $T=1/\Delta f$ is the duration of one OFDM symbol, while $\text{rect}(\cdot)$ is the rectangle function, which is defined by

Sampling $x_{\rm{i}}(t)$ with the period $T/N_{c}$ leads to the discrete sequence $\bar{x}_{\rm{i}}(n)=x_{\rm{i}}(nT/N_{c})$ as:

with $n\!=\!0,1,\cdots,MN_{c}\!-\!1$, where $\text{rect}_{m}(n)\!=\text{rect}\big{(}\frac{n-mN_{c}}{N_{c}}\big{)}$. The cyclic prefix (CP) of length $T_{\rm{G}}$ is then inserted to mitigate the inter-frame interference. Therefore, the total duration of one OFDM symbol $T_{\rm{O}}$ is $T_{\rm{O}}=T+T_{\rm{G}}$. Afterwards, the discrete signals are fed into the digital-to-analog (D/A) converter and the transmitting (Tx) radio frequency (RF) chain. Finally, the directional beams obtained by the analog precoding are transmitted through the antennas for sensing and communications.

The standard multi-path time-varying channel model is considered, which is expressed as

where $L$ is the number of paths, and $\alpha_{l}$, $\tau_{l}$ and $v_{l}$ denote the complex gain, delay and Doppler shift of the $l$-th path, respectively [39]. For simplicity, we assume that each RE experiences time-invariant flat channel fading [40]. By sampling the channel with the period of $T_{\rm{O}}$ in time domain and $\Delta f$ in frequency domain, the discrete channel matrix $\mathbf{H}_{\rm{c}}\in\mathbb{C}^{M\times{N_{c}}}$ corresponding to different REs within the OFDM frame can be written as

which is assumed to be perfectly estimated and predicted. At the receiving (Rx) end, after the analog combining, the Rx RF chain, the analog-to-digital (A/D) conversion, CP removal and DFT operation, the received signal matrix $\mathbf{Y}_{\rm{c}}\in\mathbb{C}^{M\times N_{c}}$ is obtained, which can be written as

Here $\mathbf{W}_{\rm{c}}\!\in\!\mathbb{C}^{M\times N_{c}}$ is the additive white Gaussian noise (AWGN) matrix whose entries follow $W_{\rm{c}}(m,k)\!\sim\!\mathcal{CN}(0,\sigma_{\rm{c}}^{2})$. For demodulation, the UE first estimates the channel matrix based on the reference signals transmitted by the BS. According to the estimated channel matrix, the UE is able to deduce the RE assignment matrix $\mathbf{U}$ and acquire the indices of communication REs. Then the communication data can be extracted from $\mathbf{Y}_{\rm{c}}$ by demodulation.

In this paper, the target sensing process mainly includes the target detection, positioning and speed estimation. By denoting the distance and radial speed of the target relative to the BS as $d$ and $u$, respectively, the received echoes $\bar{y}_{\rm{r}}(n)$ of the sensing subsystem can be written as

where $f_{c}$ and $T_{\rm s}$ denote the carrier frequency and the sampling period, respectively, while ${w_{\rm{r}}}[n]$ denotes the thermal noise plus the clutters from other directions, satisfying $w_{\rm{r}}[n]\sim\mathcal{CN}(0,\sigma_{\rm{r}}^{2})$. The sensing signal matrix $\mathbf{Y}_{\rm{r}}\in\mathbb{C}^{M\times{N_{c}}}$ can be derived by the DFT and serial-to-parallel operation on $\bar{y}_{\rm{r}}(n)$, and can be expressed as

Assuming that the time delay of the target is shorter than $T_{\rm{G}}$, the cross-correlation between the transmitted sensing sequence and its echoes is equivalent to performing DFT and IDFT on the Hadamard product of $(\mathbf{S}_{\rm{r}})^{*}$ and $\mathbf{Y}_{\rm{r}}$, which is expressed as

Let $\nu=0,1,\cdots,M-1$ and $\mu=0,1,\cdots,N_{\rm{c}}-1$ denote the indices of $\mathbf{E}$ in the Doppler and delay domains, respectively. The target can be detected by the hypothesis tests:

where $\Gamma$ is a predefined test threshold. Hypothesis $\text{H}_{1}$ represents that the point $(\nu,\mu)$ corresponds to a true target, and vice versa for hypothesis $\text{H}_{0}$. $\theta(\nu,\mu)$ is the average noise power estimation at the point $(\nu,\mu)$, which can be calculated by averaging the value of $|E(\nu,\mu)|^{2}$ [41, 42].

For a given point $(\nu_{0},\mu_{0})$, if hypothesis $\text{H}_{1}$ holds true, distance $d$ and radial speed $u$ of the corresponding target can be expressed respectively as [6]

where $c$ is the speed of light. Since the time delay of the target is limited by the CP length, the maximum sensing ranges of distance and speed can be expressed as $\big{[}0,\frac{cT_{\rm{G}}}{2}\big{)}$ and $\big{(}\!\!-\!\frac{c}{4f_{\rm{c}}T_{\rm{O}}},\frac{c}{4f_{\rm{c}}T_{\rm{O}}}\big{)}$, respectively. However, in practical applications, such as autonomous driving, the ranges of interest are usually smaller than the maximum sensing ranges. This will be discussed in the next section.

The ambiguity function is defined as a two-dimensional correlation function in delay-Doppler domain, which can be categorized into the cross-ambiguity function and the auto-ambiguity function. We focus on the auto-ambiguity function of the sensing sequence, i.e., its auto-correlation property, which reflects its capability of radar sensing. Because the auto-ambiguity function is utilized to characterize the property of the sequence itself without considering external operations on the sequence, the cyclic prefix part is not included in the following derivation. Specifically, the auto-ambiguity function $\chi_{a}(\nu,\mu)$ of the discrete signal $x(n)$ with length $N$ can be expressed as [39, 41]

where $\mu$ and $\nu$ denote the delay and Doppler indices, respectively. In the practical radar system, without consideration of noise, the cross-correlation matrix between the transmitted sensing sequence and its echoes is approximately equivalent to the ambiguity function shifted based on the time delay and Doppler frequency offset. By substituting the OFDM-based sensing sequence (6) into (16), the auto-ambiguity function can be derived as ²²2Note that due to the existence of CP, the correlation of intra-symbol ($m_{1}=m_{2}$) points is calculated as circular correlation.

where $\psi(n,m,k)=e^{\textsf{j}2\pi k(n-mN_{c})/N_{c}}\text{rect}_{m}(n)$. Due to the CP protection, the inter-frame ($m_{1}\neq m_{2}$) interference is negligible. Therefore, (III-A) can be further expressed as

where $\bar{n}=n-m{N_{c}}$. For simplicity, we focus on the auto-correlation component of each subcarrier ($k_{1}=k_{2}$), while neglecting the cross-correlation component between different subcarriers ($k_{1}\neq k_{2}$), since the cross-correlation is marginal due to the subcarrier orthogonality [41]. Therefore, the auto-ambiguity function can be approximated as

with

Note that only $\gamma(\nu,\mu)$ is related to the waveform design. Since $\gamma(\nu,\mu)$ reaches its maximum when $\nu$ and $\mu$ are multiples of $M$ and $N_{\rm{c}}$, respectively, we consider the region $(\nu,\mu)\in\Omega=\big{[}-\lfloor\frac{M}{2}\rfloor,\cdots,-1,0,1,\cdots,M-1-\lfloor\frac{M}{2}\rfloor\big{]}\times\big{[}-\lfloor\frac{N_{\rm{c}}}{2}\rfloor,\cdots,-1,0,1,\cdots,N_{\rm{c}}-1-\lfloor\frac{N_{\rm{c}}}{2}\rfloor\big{]}$ to avoid the ambiguity problem in target detection [43]. As the sensing distance and the speed of interest in practical applications are commonly smaller than the maximum sensing ranges corresponding to region $\Omega$ in the ambiguity function, we define the RoI $\Omega_{\bm{s}}$ in the ambiguity function as

Given the required sensing scopes of distance $[0,d_{0}]$ and speed $[-u_{0},u_{0}]$, $a$ and $b$ are chosen as the largest factors of $M$ and $N_{\rm{c}}$, respectively, such that $\big{(}-\frac{c}{4af_{\rm{c}}T_{\rm{O}}},\frac{c}{4af_{\rm{c}}T_{\rm{O}}}\big{)}$ and $\big{[}0,\frac{c}{2b\Delta f}\big{)}$ contain $[-u_{0},u_{0}]$ and $[0,d_{0}]$, respectively. That is, for $\Omega_{\bm{s}}$ of (III-A), the sensing ranges of distance and speed are $\big{[}0,\frac{c}{2a\Delta f}\big{)}$ and $\big{(}-\frac{c}{4bf_{\rm{c}}T_{\rm{O}}},\frac{c}{4bf_{\rm{c}}T_{\rm{O}}}\big{)}$, respectively. Let $F(\Omega_{\bm{s}})$ be the highest sidelobe in RoI, namely,

The PSLR within $\Omega_{\bm{s}}$ is $\frac{|\chi_{a}(0,0)|}{F(\Omega_{\bm{s}})}$, which is adopted to characterize the sensing performance.

The communication-centric waveform design consists of the following three steps.

Step 1. Communication RE and power allocation: Given the total communication power $\bar{P}_{\rm{c}}$ and the estimated communication channel $\mathbf{\hat{H}}_{\rm{c}}\in\mathbb{C}^{M\times{N_{c}}}$, the communication power allocation strategy is to maximize the achievable data rate, which is formulated as

with $m=0,1,\cdots,M-1$ and $k=0,1,\cdots,N_{\rm{c}}-1$. For brevity, the ranges of values for $m$ and $k$ are omitted in sequel. Problem $\mathcal{P}1$ can be solved by using the Karush-Kuhn-Tucker (KKT) conditions, and the optimal solution is given by [44]

where $\frac{1}{\beta\ln 2}=\frac{\bar{P}_{\rm{c}}+\sum_{(m,k)\in{\cal N}_{\rm e}}\frac{\sigma_{\rm{c}}^{2}}{|\hat{H}_{\rm{c}}(m,k)|^{2}}}{\text{card}({\cal N}_{\rm{e}})}$ and ${\cal N}_{\rm e}$ contains the indices of all the REs with non-zero power, i.e., $P_{\rm{c}}(m,k)>0$.

Step 2. Sensing RE and power allocation: According to (25), if the $(m,k)$-th RE is under poor channel condition, i.e., $|\hat{H}_{\rm{c}}(m,k)|^{2}$ is less than the threshold $\varsigma=\sigma_{\rm{c}}^{2}\beta\ln 2$, it will not be allocated for communication. By employing these inactivated REs for sensing purpose, the time-frequency resources for both subsystems will be completely orthogonal without inducing mutual interference in principle, while ensuring the optimal communication performance. Accordingly, the matrix $\mathbf{U}$ defined in (1) can be expressed as

Note that when the communication channel is relatively flat-fading, the number of sensing REs may prove insufficient to support high-resolution sensing. In order to mitigate this issue, a minimum threshold is set for the number of sensing REs, which is denoted as $\hat{N}_{r}$. If the number of sensing REs (i.e., the number of non-zero elements in $\mathbf{U}$), denoted as ${N}_{r}$, is less than the threshold $\hat{N}_{r}$, $\hat{N}_{r}-{N}_{r}$ communication REs with the lowest channel gains are re-assigned for sensing. Since the REs with good channel conditions are chosen for communication first, the sensing REs may be discontinuous in both time and frequency domains, causing possible high sidelobe in the ambiguity function. To reduce the sidelobe level for enhancing sensing performance, the power allocation strategy for sensing REs is to maximize the PSLR within $\Omega_{\bm{s}}$, which is formulated as

where $\bar{P}_{\rm{r}}$ is the total sensing power budget. Since the main peak $|\chi_{a}(0,0)|$ is always equal to the total sensing power $N_{\rm{c}}\bar{P}_{\rm{r}}$, the problem $\mathcal{P}2$ is equivalent to minimize the highest sidelobe level given by:

Due to the minimax form of the objective function, it is difficult to solve problem $\mathcal{P}3$ directly. To address this issue, a slack variable $z_{0}$ is introduced as the optimization objective. Accordingly, we add an extra constraint that all the sidelobes within $\Omega_{\bm{s}}$ are less than $z_{0}$. Then the optimization problem can be expressed as

Problem $\mathcal{P}4$ now can be formulated into a quadratic problem, which is solvable using the CVX toolbox [45].

Step 3. PAPR reduction: In addition to the PSLR in the ambiguity function, the PAPR is also a significant metric for sensing sequences. A high PAPR results in nonlinear distortion of high power amplifier, which is detrimental especially for the millimeter wave and Terahertz bands [46]. To tackle this problem, we need to minimize the PAPR of the sensing sequence, whilst retaining the high PSLR property. Recall that the PSLR is mainly related to the power allocation $\mathbf{P}_{\rm{r}}$ according to (19), which inspires us to minimize the PAPR by optimizing the phase of each element of $\mathbf{S}_{\rm{r}}$. Let $\theta(m,k)$ denote the phase of the symbol on the $(m,k)$-th RE. The PAPR of the sensing sequence among $M$ OFDM symbols can be expressed as

where $0\leq m\leq M-1$ and $0\leq n\leq N_{c}-1$. Since the average power of all the symbols has been determined by the proposed RE assignment and power allocation strategy, minimizing the PAPR is equivalent to minimizing the peak. Considering that the peak among $M$ symbols is the maximum value among the peak values of all symbols, we can reduce it by lowering the peak value of each symbol individually. Additionally, the peak values corresponding to different OFDM symbols are independent of each other, the phase-frequency characteristics of different OFDM symbols can be optimized separately. Consider the case that the phases of all the modulated symbols on different sensing REs are selected from the set $\{0,2\pi/R,\cdots,2\pi(R-1)/R\}$ with the size $R$. Then the PAPR reduction problem for the $m$-th OFDM symbol can be formulated as

where $\boldsymbol{\theta}_{m}=\big{[}\theta(m,0),\theta(m,1),\cdots,\theta(m,N_{\rm{c}}-1)\big{]}^{\mathrm{T}}$.

To solve this discrete optimization problem, we propose a heuristic searching method based on the BB algorithm to obtain a near optimal solution. The BB algorithm divides the whole feasible region into several sub-regions, which correspond to several sub-problems. For each sub-problem, well-designed functions are employed to estimate its upper and lower performance bounds. As the number of iterations increases, the minimum upper and lower bounds among all the sub-problems are obtained and updated. When the difference between the minimum upper and lower bounds is lower than a threshold, the iteration terminates and the solution that achieves the minimum upper bound is adopted as the final solution [47].

Let $\mathbf{A}_{m}$ denote $e^{\textsf{j}\boldsymbol{\theta}_{m}}$, i.e., the $k$-th element of $\mathbf{A}_{m}$ is ${A}_{m}(k)=e^{\textsf{j}\theta(m,k)}$. Since the feasible region of ${A}_{m}(k)$ is $\Phi=\big{\{}1,e^{\textsf{j}\frac{2\pi}{R}},\cdots,e^{\textsf{j}\frac{2\pi(R-1)}{R}}\big{\}}$, the whole feasible region of $\mathbf{A}_{m}$ is $\Psi^{(0)}=\Phi^{N_{\rm{c}}}$, which is the Cartesian product of $N_{\rm{c}}$ $\Phi$s. The problem $\mathcal{P}5$ can be compactly written as

with

For each sub-region $\Psi\in\Psi^{(0)}$, denote its corresponding sub-problem as $\mathcal{P}(\Psi)$. A lower bound of $\mathcal{P}(\Psi)$ can be derived by a bounding function, which can be expressed as

where $\mathbf{A}_{m}^{L}$ is a relaxed solution of $\mathcal{P}(\Psi)$ that achieves the lower bound. More specifically, suppose that the first $k_{0}$ elements in $\Psi$ remain in their original values, and its $(k_{0}+1)$-th element is fixed to a feasible value. By extending the feasible region of the other elements to a continuous search region, a relaxed problem $\mathcal{P}_{\rm{L}}(\Psi)$ can be expressed as

with $k=k_{0}+1,k_{0}+2,\cdots,N_{\rm{c}}-1$. $\mathbf{A}_{m}^{L}$ can be derived by solving $\mathcal{P}_{\rm{L}}(\Psi)$ via the CVX toolbox, yielding the lower bound $f_{\rm{L}}(\Psi)$ of each sub-problem. On the other hand, by projecting $\mathbf{A}_{m}^{L}$ onto its closest feasible point, i.e.,

an upper bound of each sub-problem is obtained, which can be written as

The proposed PAPR reduction procedure is summarized in Algorithm 1. We initialize the problem set $\mathcal{S}$ as $\{\mathcal{P}\big{(}\Psi^{(0)}\big{)}\}$. The minimum upper bound $B_{\rm{U}}$ and lower bound $B_{\rm{L}}$ are initialized as the upper and lower bounds of $\mathcal{P}\big{(}\Psi^{(0)}\big{)}$, respectively. At each iteration, the sub-problem ${\cal P}(\Psi)$ with the smallest lower bound in $\mathcal{S}$ is selected. Note that the first $k_{0}$ elements of $\mathbf{A}_{m}$ in $\Psi$ have been set to fixed values in the previous iterations. If $k_{0}=N_{\rm c}$, i.e., all the elements of $\mathbf{A}_{m}$ have already been set to fixed values, $\Psi$ is non-divisible and ${\cal P}(\Psi)$ is deleted from $\mathcal{S}$, and the algorithm considers the next smallest lower-bound subproblem in $\mathcal{S}$. Otherwise, by denoting the fixed value of ${A}_{m}({k})$ as ${a}_{{k}}\in{\Phi}$, the region $\Psi$ can be expressed as $\Psi=\{{a}_{0}\}\otimes\{{a}_{1}\}\otimes\cdots\otimes\{{a}_{k_{0}-1}\}\otimes\Phi^{N_{\rm{c}}\!-k_{0}}\triangleq\Psi^{[k_{0}]}\otimes\Phi^{N_{\rm{c}}\!-k_{0}}$, where $\otimes$ denotes the Cartesian product. $\Psi$ is divided into $R$ smaller regions by fixing the $(k_{0}+1)$-th element of $\mathbf{A}_{m}$ to each of the $R$ values in $\phi$, while the feasible region of the remaining elements of $\mathbf{A}_{m}$ is the full search region $\Phi$, which can be expressed as

Their corresponding problems, $\mathcal{P}\big{(}\Psi_{1}\big{)}$, $\mathcal{P}\big{(}\Psi_{2}\big{)},\cdots,\mathcal{P}\big{(}\Psi_{R}\big{)}$, are added to $\mathcal{S}$ and the problem $\mathcal{P}\big{(}\Psi\big{)}$ is deleted from $\mathcal{S}$. The lower and upper bounds of each of these created sub-problems are calculated by bounding functions to update $B_{\rm{L}}$ and $B_{\rm{U}}$. If the lower bound of a certain sub-problem is larger than $B_{\rm{U}}$, it is deleted from $\mathcal{S}$. To reduce the worst-case computational complexity, we also keep $\text{card}(\mathcal{S})$ to no more than a threshold $N_{\rm{s}}$ by deleting sub-problems with relatively larger lower bound from $\mathcal{S}$. When the difference between $B_{\rm{L}}$ and $B_{\rm{U}}$ is less than a threshold $\epsilon$ or $\mathcal{S}$ is an empty set, the iteration procedure terminates. The solution corresponding to $B_{\rm{U}}$ is the final solution $\mathbf{A}_{m}^{\rm opt}$, and the symbol phase $\boldsymbol{\theta}_{m}$ is set as $\text{angle}(\mathbf{A}_{m}^{\rm opt})$. As it can be seen, the worst-case computational complexity of the proposed PAPR reduction is $\mathcal{O}(\text{card}(\mathcal{S}){N_{\rm{c}}})$, which is much lower than the computation complexity of exhaustive searching ($\mathcal{O}(R^{N_{\rm{c}}})$). Besides, the computational complexity can be further reduced by adjusting the parameter $\epsilon$.

To provide accurate sensing, the sidelobe level in the ambiguity function can be adopted to characterize sensing performance, as mentioned in Section III. A sensing sequence has a locally perfect auto-correlation property, when the value of the highest sidelobe within RoI in its ambiguity function is zero, which can be expressed as

Since $\eta(\nu)\neq 0$ (when $m>1$), $|\chi_{a}(\tau,\nu)|=0$ is equivalent to $\gamma(\nu,\mu)=0$. Given the total sensing power $\sum_{m=0}^{M-1}\sum_{k=0}^{N_{\rm{c}}-1}P_{\rm{r}}(m,k)=\bar{P}_{\rm{r}}$, $\gamma(0,0)$ is always equal to $\bar{P}_{\rm{r}}$. Therefore, the locally perfect auto-correlation property can be obtained by setting the function $\gamma(\nu,\mu)$ within RoI as

According to (20), $\gamma(\nu,\mu)$ is derived by performing DFT and IDFT on ${P}_{\rm{r}}(m,k)$ along its column and row, respectively. Therefore, ${P}_{\rm{r}}(m,k)$ can be derived by performing inverse operations on $\gamma(\nu,\mu)$, which can be expressed as

Since there is a one-to-one mapping between $\gamma(\nu,\mu)$ and ${P}_{\rm{r}}(m,k)$, we can use $\gamma(\nu,\mu)$ as the optimization variable instead of ${P}_{\rm{r}}(m,k)$ to reduce the dimension of the optimization variable. This is because for a sensing with a locally perfect auto-correlation property, the unit cells of $\gamma(\nu,\mu)$ within $\Omega_{\rm{s}}$ are fixed and we only need to optimize the unit cells in the complementary set of $\Omega_{\rm{s}}$, which are called irrelevant cells. ${P}_{\rm{r}}(m,k)$ is always a non-negative real number, the irrelevant cells should be designed under this constraint, which is formulated as