{'fraction_non_alphanumeric': 0.051656960911642714, 'fraction_numerical': 0.010012987557082409, 'mean_word_length': 4.323371989295272, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Channel Knowledge Map for Environment-Aware Communications: EM Algorithm for Map Construction

Channel knowledge map (CKM) is an emerging technique to enable environment-aware wireless communications, in which databases with location-specific channel knowledge are used to facilitate or even obviate real-time channel state information acquisition. One fundamental problem for CKM-enabled communication is how to efficiently construct the CKM based on finite measurement data points at limited user locations. Towards this end, this paper proposes a novel map construction method based on the \emph{expectation maximization} (EM) algorithm, by utilizing the available measurement data, jointly with the expert knowledge of well-established statistic channel models. The key idea is to partition the available data points into different groups, where each group shares the same modelling parameter values to be determined. We show that determining the modelling parameter values can be formulated as a maximum likelihood estimation problem with latent variables, which is then efficiently solved by the classic EM algorithm. Compared to the pure data-driven methods such as the nearest neighbor based interpolation, the proposed method is more efficient since only a small number of modelling parameters need to be determined and stored. Furthermore, the proposed method is extended for constructing a specific type of CKM, namely, the channel gain map (CGM), where closed-form expressions are derived for the E-step and M-step of the EM algorithm. Numerical results are provided to show the effectiveness of the proposed map construction method as compared to the benchmark curve fitting method with one single model.


I. INTRODUCTION
Channel knowledge map (CKM) is an emerging technique towards environment-aware wireless communications [1], which provides location-specific (rather than the coarse site-specific) channel knowledge associated with potential transmitter-receiver pairs by, e.g., storing them in databases. Compared to conventional environment-ignorant communication, CKM-enabled environment-aware communication is expected to facilitate or even obviate real-time channel state information (CSI) acquisition, which makes it especially appealing for future communication systems with large spatial dimensions [2] and prohibitive channel training overhead.
In fact, the attempts to use site-specific databases in wireless communications have been pursued in prior works based on, e.g., 3D city or terrain map [3], radio environment map [4], [5], and TV white space map [6]. However, these designs require storing accurate physical environment maps and implementing computation-expensive algorithms, such as ray tracing algorithms, which are costly in terms of both storage and computation. Furthermore, the TV white space map and radio environment map were mainly used for cognitive radio systems [7], for which the obtained maps critically depend on the status/activities of the primary transmitters, such as the spectrum, power, and antenna pattern being used. By contrast, CKM aims to provide location-specific knowledge that directly reflects the intrinsic channel characteristics, regardless of the transmitter or receiver activities [1]. This makes it possible to design communication systems with light or even without realtime channel training [8]. Some specific instances of CKM include channel gain map (CGM) [9], channel path map (CPM) [8], and beam index map (BIM) [8], [10]. CKM-enabled communications have been recently studied in various applications, such as training-free subband selection for device-to-device (D2D) communications [1], beam alignment for millimeter wave (mmWave) massive MIMO [8], and trajectory design for cellular-connected UAV [11].
One fundamental problem for CKM-enabled environmentaware communication is how to efficiently construct the CKM based on finite measurement data points at limited user locations. The most straightforward approach for map construction is interpolation-based methods, such as the inverse distance weighted (IDW) [12], nearest neighbours (NN), splines [13], and Kriging [14], [15]. The interpolation-based methods, however, generally require large measurement data for accurate map construction. In addition, such pure data-driven methods ignored the well-established stochastic or geometric based channel models developed over the past few decades [16], thus usually requiring huge storage capacity for map maintenance. To utilize both measurement data and expert knowledge, one straightforward method is parametric curve fitting, where the best modelling parameters of the selected channel models are determined based on the measurement data. However, such a naive curve fitting method would lead to poor map quality, since the number of tunable modelling parameters is typically very small, while the environment is usually too complex to be accurately characterized by one single model.
To overcome the above drawbacks, in this paper, we propose a novel CKM construction method based on the wellestablished expectation maximization (EM) algorithm [17]. Notice that the naive curve fitting method is not able to accurately predict the complex channel environment knowledge, as only one common channel model is used. By contrast, it is observed that different sub-areas of the site may experience different radio propagation environment, which may be modelled with different sets of modelling parameters. Based on this observation, we propose to partition the available measurement data into different modelling groups, where each group shares the same modelling parameter values that are to be determined. We show that the determination of modelling parameter values corresponds to a maximum likelihood estimation problem with latent variables. Although this is a challenging non-convex optimization problem, various existing algorithms, such as the classic EM algorithm [17], have been proposed to find its efficient solutions. In particular, we propose a generic EM-based algorithm to solve the considered CKM construction problem, which consists of two steps, namely the Expectation step (Estep) and the Maximization step (M-step). Furthermore, we also consider the special case for constructing a CGM, for which we extend the EM-based algorithm to find the optimized solution, by deriving the closed-form expressions for the Estep and M-step, respectively. Finally, extensive numerical results are provided to verify the effectiveness of the proposed EM-based algorithm for CKM construction.

II. SYSTEM MODEL
As shown in Fig. 1, we consider a wireless communication system in a specific site, with a stationary base station (BS) and mobile users, whose potential locations q are denoted by the set Q. For any given q ∈ Q, our objective is to predict the interested location-specific channel knowledge, which is denoted as r, as accurate as possible before real-time channel training is applied. Note that the channel knowledge r can be any useful information related to the wireless channel, such as the channel gain, shadowing, angle of arrival/departure (AoA/AoD), or even the channel impulse response. To this end, a BS-to-any (B2X) CKM W is constructed, which provides mapping from location q to the corresponding channel knowledge r, i.e., W : q ∈ Q → r.
One immediate method for channel knowledge prediction based on user locations is to utilize the well-established channel models, which are usually given stochastically with certain modelling parameter vector θ, denoted as p(r|q, θ). Specifically, p(r|q, θ) gives the probability density function (PDF) of the channel knowledge r for users located at q, parameterized by θ. As a concrete example, for the specific B2X CGM, r corresponds to the channel gain in dB, which is denoted by the real number r. Without loss of generality, we may assume that the BS is located at the origin. Therefore, according to the classic path loss model, we have r = β + 10α log 10 q + S, (1) where α denotes the path loss exponent, β denotes the path loss intercept, S ∼ N (0, σ 2 ) captures the log-normal shadowing with variance σ 2 , and · denotes the Euclidean norm. As such, the modelling parameter vector for channel gains is θ = [α, β, σ 2 ], and the conditional PDF of the channel knowledge r given user location q is p(r|q, θ) = N (r|β + 10α log 10 q , σ 2 ) where N (r|µ, σ 2 ) denotes the PDF of a Gaussian random variable r with mean µ and variance σ 2 . A direct channel knowledge prediction based on stochastic channel models would lead to poor accuracy, since such models characterize channels only on the average sense, by ignoring the sitespecific or even location-specific propagation environment. For instance, with the channel model in (1), no matter how good the modelling parameter θ is chosen, the predicted channel gain is symmetric around the BS, which is far from reality when the actual environment is taken into account. On the other hand, site-specific or location-specific radio propagation environment information can be learned if onsite measurement data are available. Let X ∈ R D×N denote the set of measurement data points. Each column of X, denoted as x n ∈ R D×1 , n ∈ N {1, ..., N }, corresponds to one data point, which includes the measured channel knowledge r n at the corresponding location q n . Therefore, we have x n = [q T n , r T n ] T , with the superscript T denoting the transpose. Note that the number of available measurement data points N is usually limited. As a result, to construct a complete CKM for all potential user locations, one needs to infer the channel knowledge of those unmeasured locations based on X. However, the pure data-driven methods, such as the interpolation-based methods, usually require large data and high storage capacity. On the other hand, the simple parameteric curve fitting based method, which uses one single model to fit all data points, would lead to poor accuracy due to the limited degrees of freedom associated with the few modelling parameters.
To overcome the above issues, we propose a map construction method based on multi-component or mixed channel models. Specifically, with the basic PDF p(r|q, θ), we consider a mixed channel model with a total of K components, corresponding to K sets of modelling parameters, denoted as θ k , k ∈ K {1, ..., K}. With a slight abuse of notation, let θ = {θ 1 , ...., θ K }. Then for the given measurement data X, our objective is to find the set of modelling parameters θ based on certain criterion. A commonly used criterion is the maximum likelihood estimation, which corresponds to finding parameters θ for maximizing the likelihood as follows.
(P1): max where p(X|θ) denotes the likelihood function with respect to the modelling parameters θ.

III. EM ALGORITHM FOR CKM CONSTRUCTION
The key challenge of solving (P1) lies in finding the explicit expression for the likelihood function p(X|θ). This is difficult since for each data point x n ∈ X, it is unknown which of the K modelling components it should be associated with. As a consequence, (P1) corresponds to the maximum likelihood estimation problem with latent variables, which, fortunately, has been extensively studied and can be efficiently solved by various algorithms, such as the classic EM algorithm [17]. To this end, for each data point x n , n ∈ N , we introduce a vector of latent variables z n ∈ R K×1 to indicate the association of data point x n with the K modelling components, whose k-th element z nk is a binary random variable with z nk ∈ {0, 1}, ∀k ∈ K. Here, z nk = 1 means that x n is best explained by the k-th modelling component with parameter θ k . It follows that k∈K z nk = 1, as each data point x n is only associated with the best modelling component. Furthermore, the distribution of z n is specified by the mixing coefficients π k , i.e., p(z nk = 1) = π k , k ∈ K, (3) where 0 ≤ π k ≤ 1 and k∈K π k = 1. As such, for any given modelling parameters θ, the conditional PDF of x n given its associated latent variable z n is [17] p(x n |z n , where k * defined such that z nk * = 1. Note that the last equality in (4) holds since z nk ∈ {0, 1}, ∀k ∈ K. Similarly, p(z n |θ) can be expressed as p(z n |θ) = k∈K π z nk k . As a result, the joint PDF of x n and z n can be expressed as Let Z ∈ R K×N include all the N vectors z n of latent variables, n ∈ N . Since different data points are independent, we have p(X, Z|θ) = n∈N p(x n , z n |θ). Therefore, the likelihood function p(X|θ) is obtained by marginalizing p(X, Z|θ) over Z, and (P1) can be equivalently written as Note that p(X|θ) and p(X, Z|θ) are referred to as the likelihood functions of the incomplete-data and complete-data [17], respectively. (P2) is the maximum likelihood estimation problem with the latent variable Z, which can be efficiently solved by the classic EM algorithm [17]. The EM algorithm is an iterative algorithm with two basic steps, i.e., the E-step and the M-step, which are summarized in Algorithm 1 [17,Section 9.3]. It is shown in [17,Section 9.4] that in the EM algorithm, each step will lead to an increased (or at least non-deceased) complete-data log likelihood. Therefore, the convergence of the EM algorithm is guaranteed [17].
Input: Given the joint distribution p(X, Z|θ) governed by the set of parameters θ; 1: Initialization: Choose initial parameters θ old and mixing coefficients π old k , ∀k ∈ K; 2: Repeat: 1) E-step: Evaluate the posterior distribution of the latent variables p(Z|X, θ old ) and the responsibilities

A. General Algorithm for EM-based CKM Construction
In the following, the E-step and the M-step are developed for our considered CKM construction problem (P2).
1) E-step: As given in Algorithm 1, the E-step of the EM algorithm is to evaluate the posterior distribution of the latent variable p(Z|X, θ old ), with given modelling parameter θ old . According to equation (9.75) of [17], p(Z|X, θ old ) can be factorized as p(Z|X, θ old ) = n∈N p(z n |x n , θ old ).
Furthermore, with the Bayesian theorem, we have p(z n |x n , θ old ) = p(z n |θ old )p(x n |z n , θ old ) z ′ n p(z ′ n |θ old )p(x n |z ′ n , θ old ) .
Let γ nk denote the responsibility corresponding to component k ∈ K to explain the measurement data x n , which can be obtained as the expected value of the indicator variable z nk with the posterior distribution in (7), i.e., γ nk E[z nk ] = p(z nk = 1|x n , θ old ) = π old k p(x n |θ old k )/ j∈K π old j p(x n |θ old j ) = π old k p(r n |q n , θ old k )/ j∈K π old j p(r n |q n , θ old j ), (8) where the second equality holds since z nk is binary. Furthermore, the last equality of (8) follows by noting that x n = [q T n , r T n ] T , so that p(x n |θ k ) = p(q n , r n |θ k ) = p(r n |q n , θ k ), (9) where p(r n |q n , θ k ) corresponds to the selected stochastic channel model, such as (2) for CGM. As a result, with the Estep, the posterior probabilities p(Z|X, θ old ) is obtained based on (6) and (7), and the responsibilities {γ nk } is obtained based on (8).
2) M-step: Based on the posterior probabilities in (6) and the responsibilities in (8) obtained in the E-step, the modelling parameter θ and mixing coefficients π k are updated in the Mstep, by maximizing the expectation of the log-likelihood of the complete-data, with the expectation taken with respect to p(Z|X, θ old ), which is given by [17] Q(θ, θ old ) = Z p(Z|X, θ old ) ln p(X, Z|θ).
Furthermore, we have ln p(X, Z|θ) = n∈N ln p(x n , z n |θ) where the second equality follows from (5), and the last equality follows from (9). As a result, the expectation of ln p(X, Z|θ) with respect to the posterior probabilities p(Z|X, θ old ) can be rewritten as where the identity γ nk = E[z nk ] is used. Therefore, the optimization problem for the M-step can be formulated as (P3): max It is not difficult to see that problem (P3) can be decoupled into two independent sub-problems: (P3.1): max γ nk ln p(r n |q n , θ k ).
(P3.1) is a convex optimization problem. With the standard Lagrangian method, its optimal solution can be obtained in closed form as π * k = N k /N , where N k = n∈N γ nk , ∀k ∈ K. On the other hand, the solution to (P3.2) depends on the actual conditional distribution p(r n |q n , θ k ), i.e., the selected stochastic channel model. Based on the above results in the E-step and M-step, the general algorithm for EM-based CKM construction is summarized in Algorithm 2.

B. Special Case with CGM Construction
In this subsection, we consider the the construction of a particular type of CKM, namely the CGM, for which the PDF of the channel gain given the user location is expressed as (2). Eventually, the CGM can be directly constructed by using Algorithm 2. Here, by exploiting the specific structure of CGM, we obtain the closed-form expressions in (8), and obtain the optimal solution to (P3.2) in closed form, to reduce the construction complexity, as explained in detail as follows.
Algorithm 2 General Algorithm for EM-based CKM Construction.
First, γ nk in (8) for the E-step is given by the following closedform expression: γ nk = π old k N (r n |β old k +10α old k log 10 q n , (σ old k ) 2 )) j∈K π old j N (r n |β old j +10α old j log 10 q n , (σ old j ) 2 ) . (10) Next, consider problem (P3.2), for which the log-likelihood function of the M-step can be written as where d n 10 log 10 q n is defined for convenience. By discarding constant terms, (P3.2) is equivalent to min which can be decoupled into K independent sub-problems: min Theorem 3.1: The optimal solution to problem (11) is: where d k = ( n∈N γ nk d n )/N k , r k = ( n∈N γ nk r n )/N k , (d k r k ) = ( n∈N γ nk d n r n )/N k , and d 2 k = ( n∈N γ nk d 2 n )/N k , with N k = n∈N γ nk ∀k ∈ K. Proof: Please refer to Appendix A. Based on the above derivations, the EM-based algorithm for the specific CGM construction is summarized in Algorithm 3.

C. Utilizing CKM for Channel Prediction
Based on Algorithms 2 and 3, we obtain the modelling parameters θ = {θ 1 , ..., θ K }, as well as the responsibilities {γ nk } for the measurement data X. We are now ready to utilize such information to predict the channel knowledge r for any new location q. To this end, we need to first determine which set of modelling parameters θ 1 , ..., θ K is most suitable for the new location q. This can be achieved by determining the responsibilities {γ k (q)} using the IDW method. Specifically, let M denote the subset of M user locations with training data that are nearest to q. Then, is the weighting coefficient based on the IDW criterion, with d j (q) = q j − q , j ∈ M. Then, the modelling parameter for location q is obtained as the one that maximizes γ k (q), i.e., θ(q) = θ k ⋆ , where k ⋆ = arg max k∈K γ k (q). As a result, the channel knowledge for location q can be predicted based on the PDF p(r|q, θ(q)).

IV. NUMERICAL RESULTS
In this section, we present numerical results to validate the performance of our proposed algorithm. As shown in Fig. 2, we consider a geographic area of size 2 × 2 km 2 , and focus on the channel gains with a BS located at the center. We assume that there are two building clusters shown in Fig. 2. Therefore, depending on the user locations, the direct lineof-sight (LoS) link may be blocked by one of the building cluster. Furthermore, for those indoor users located in the building cluster area, additional penetration loss is incurred. As a result, depending on the user locations, the groundtruth channel gains are generated based on 5 user groups: LoS users that have direct LoS link with the BS; NLoS1 and NLoS2 users whose LoS links are blocked by building clusters 1 and 2, respectively; and Indoor1 and Indoor2 users that are located in building clusters 1 and 2, respectively. The corresponding modelling parameters of each user group are given in Table  I. Furthermore, the initial parameters of Algorithm 3 are set as π old k = 1/K, ∀k ∈ K, and θ old are randomly generated as α k ∈ [2,5], β k ∈ [30, 140], and σ 2 k ∈ [6,15], ∀k ∈ K. Unless otherwise stated, the number of data points used for training is N = 2000.   which guarantees the convergence. Furthermore, when the assumed number of components matches with the groundtruth value, i.e., K = 5, a fastest convergence is observed. On the other hand, with K ≥ 5, Algorithm 3 is still able to converge to roughly the same components number matches as K = 5, though at slightly slower rate, while that for K = 3 leads to poor performance since the number of assumed mixing components is smaller than the groundtruth.
Next, we evaluate the quality of the constructed CGM based on Algorithm 3. For comparison, we also consider a benchmark scheme based on the single-model curve fitting method, i.e., with K = 1. In this case, no latent variable is involved since all available data points will be fitted to one single set of parameters. Fig. 4(a) shows the groundtruth data points, and Fig. 4(b) and Fig. 4(c) plot the constructed CGMs with K = 5 and K = 1, respectively, by using the IDW method with M = 3. It is observed that compared to the single-model curve fitting method, the proposed EMbased algorithm results in more accurate CGM. In fact, it is observed from Fig. 4(c) that the single-model curve fitting method leads to concentric contours of channel gain, which is far from the reality as shown in Fig. 4(a). This is due to the fact that the conventional single-model curve fitting method cannot distinguish the characteristics of different data points at different sub-areas. This issue can be addressed by our proposed EM-based algorithm with mixed channel models, as shown in Fig. 4(b).
To evaluate the impact of the number of training data points N , Fig. 5 plots the normalized root mean square error (a) Groundtruth data points.
(c) Single model curve fitting. (NRMSE) of the predicted channel gains versus N . The testing set consists of 1000 data points. It is observed from Fig. 5 that as N increases, the constructed CGM by the proposed EM algorithm with K > 1 has better fitting quality. By contrast, regardless of N , the single model curve fitting method with K = 1 has poor performance, which is due to the fact that the number of tunable modelling parameters is too small to accurately fit the complex environment. This demonstrates the effectiveness of our proposed EM algorithm for accurate CKM construction in complex environments.

V. CONCLUSION
In this paper, we proposed a novel EM-based CKM construction method towards environment-aware communications, by utilizing both the available measurement data points and the expert knowledge with well-established statistic channel models. The key idea is to partition the available data points into different groups, where each group shares the same modelling parameter values that are to be determined. We propose to use the classic EM algorithm to determine the modelling parameters by solving an equivalent maximum likelihood estimation problem with latent variables, and then extend the algorithm for constructing the specific CGM. Numerical results demonstrated the effectiveness of the proposed algorithm as compared to the benchmark curve-fitting scheme with one single model. How to extend the results to other types of channel knowledge and the efficient utilizations of the constructed CKM are interesting directions worth pursuing in future research. APPENDIX A PROOF OF THEOREM 1 Problem (11) can be solved by setting the partial derivatives with respect to the optimization variables to be zero. For convenience, let f denote the cost function of problem (11). Therefore, we have ∂f Then, (14) and (15)  By solving the linear system equations with two unknowns and two equations, we get (12). Similarly, by setting the partial derivative of f with respect to σ 2 k to zero, we get (13). This thus completes the proof.