Content-Aware User Association and Multi-User MIMO Beamforming over Mobile Edge Caching
Susanna Mosleh Qiang Fan Lingjia Liu Jonathan D. Ashdown Erik Perrins Kurt Turck

 
 

  













Mobile edge caching (MEC) has been introduced to support ever-growing end-users' needs. To reduce the backhaul traffic demand and content delivery latency, cache-enabled edge servers at base stations (BSs) are employed to provision popular contents at the network edge. In this paper, multiple-input-multiple-output (MIMO) operation and user association policy are linked to the underlying cache placement strategy to ensure a good trade-off between load balancing and backhaul traffic taking into account the underlying wireless channel and the finite cache capacity at edge servers. Due to the coupled interference among mobile stations, the binary nature of the underlying cache placement and user association matrices, the resulting mixed-timescale mixed integer optimization problem is nonconvex and NP-hard. To solve this problem, we decompose the joint optimization problem into a long-term content placement sub-problem and a short-term content delivery sub-problem. A novel iterative algorithm is introduced by leveraging the alternating direction method of multipliers together with a stochastic parallel successive convex approximation-based algorithm. The introduced scheme enables all BSs to update their optimization variables in parallel by solving a sequence of convex subproblems. Simulation evaluation demonstrates the efficiency of our strategy. 



Cache placement, cache size constraint, coordinated multi-point transmission, mobile edge caching, multi-user MIMO beamforming, non-convex optimization, user association, wireless big data.



Content-Aware User Association and Multi-User MIMO Beamforming over Mobile Edge Caching
    Susanna Mosleh,
        Qiang Fan,
        Jonathan D. Ashdown, Member, IEEE,
        Erik Perrins, Senior Member, IEEE,
        Kurt Turck,
        and Lingjia Liu, Senior Member, IEEE
S. Mosleh is with the Department of Physics, University of Colorado, Boulder, and an associate of the Communications Technology Laboratory, National Institute of Standards and Technology, Boulder, CO, 80305.

E-mail: susanna.mosleh@colorado.edu
Q. Fan and L. Liu are with the Department of Electrical and Computer Engineering, Virginia Tech, Blacksburg, VA, 24061.

E-mail: {qiangf, ljliu}@vt.edu
E. Perrins is with the Department of Electrical Engineering and Computer Science, the University of Kansas, Lawrence, KS, 66045. 

E-mail: esp@ku.edu
J. Ashdown and K. Turck are with the Information Directorate, Air Force Research Laboratory (AFRL), Rome, NY, 13441.. 

E-mail:{jonathan.ashdown, kurt.turck}@us.af.mil
The corresponding author is L. Liu (ljliu@ieee.org).
    December 30, 2023
=============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





§ INTRODUCTION

The big data era is being shaped with the ongoing growth
of commercial data services, with mobile wireless network constituting a major data source contributor. Nowadays,
wireless communication is becoming tightly integrated in our
daily lives; especially with the global spread of laptops, tablets,
smartphones, video streaming and online social networking
applications. This globalization has paved the way to dramatically increase wireless network dimensions in terms of
subscribers and the amount of flowing data.  Cisco Systems forecasts that the number of mobile-connected devices per person will reach 1.5 by 2022 and
global mobile data traffic will increase seven fold between
2017 and 2022 <cit.>. The volume, velocity, and variety of data
from both mobile users and communication networks follows an exponential increase pattern. Consequently, big data will
be further entrenched in the upcoming fifth-generation (5G) wireless networks in which the ability to support high data traffic and exceedingly low latency play an important fundamental role <cit.>.

In traditional mobile network, user content requests are served by Internet content providers. Once certain contents are required, they can only be retrieved from the remote cloud or content servers. Since some popular contents may be requested for multiple times, the content provider has to repeat to transfer the identical content. The repeated requests lead to long service latency as well as increasing traffic that may congest the network. To solve this problem, mobile edge computing has been introduced to improve the network performance by provision computing capability at the network edge (i.g. at base stations (BSs)) <cit.>. As edge servers can not only provide computing resources but also storage resources, it can be utilized as cache nodes to store valuable contents required by mobile users. Hence, mobile edge caching (MEC) is referred to as caching at edge servers to reduce the traffic at the backhaul and the content delivery latency <cit.>. Note that mobile edge caching has been defined as one of the applications of mobile edge computing by ETSI ISG <cit.>. It is promising to store popular contents in cache-enabled edge servers in advance such that users can retrieve contents from the cache in their vicinity rather than the remote cloud. As a result, the cost of the traffic in the backhaul can be remarkably saved, while the content delivery time is improved.   



In the MEC with densely deployed BSs, coordinated Multi-Point (CoMP) transmission can be utilized to facilitate the wireless cache <cit.>. To do so, a cluster of BSs is assigned to each user to effectively relieve the backhaul capacity demand at MEC. Each cluster is formed by aggregating the BSs whose transmission strategies cooperatively serve the user equipments (UEs) within the cluster through joint proceding <cit.>. If the user's serving BSs cache the content that the user requests, it will be transmitted directly by the serving BSs cooperatively.  CoMP opportunities also allow a reduction in inter-cell interference <cit.>, and thus incur a substantial data rate improvement for users. 


In order to entirely utilize the benefit of MEC with CoMP transmission, developing advanced caching placement strategies in MEC is required. One way to increase the possibility for a user to access its desired content locally is to cache contents based on the data popularity distribution, such as the Zipf distribution <cit.>. Moreover, the content placement has to take user association into account. To be specific, if edge servers have the content requested by a user with undesirable channel gain, data transmission is not reliable and necessitates high transmit power. Consequently, reallocating the requested content via backhaul to BSs that have good channels to the served users will be unavoidable and increase the backhaul cost <cit.>. Owing to CoMP technology, each BS has multiple antennas and thus several BSs in a cluster can cooperatively transmit contents to a particular user with multicast beamforming technologies. Therefore, the beamforming vector design also impacts the backhaul cost. In a densely deployed wireless network, each user can be associated with one or several BSs depending on both content availability and channel condition, and thus jointly optimizing the user-association policy, caching placement strategy, and beamforming design remains a challenging issue. 



 §.§ Related Work



The importance of caching in 5G wireless networks was recognized in <cit.>. Due to the storage resources provided by mobile edge servers, MEC becomes an important use case to reduce the content delivery latency in wireless network<cit.>. Yao et al. have surveyed and investigated the cache placement and cache criteria in MEC to improve both the backhaul cost and content delivery latency in wireless networks <cit.>. In <cit.>, the authors considered the problem of jointly minimizing the total transmit power and backhaul traffic in wireless cooperative networks under the constraint of each user's SINR requirements and with respect to the beamforming vectors. Assuming there is a backhaul constraint for each BS, <cit.> considered a weighted sum rate optimization problem to design the beamforming vectors. In <cit.>, an online algorithm on user-AP association and resource allocation for content delivery with predictive scheduling is proposed to improve the throughput, queue stability and delay reduction, where the content placement is fixed. Other than these works on unicast, <cit.> discussed the effect of caching on the multicast beamforming in the Cloud-RAN. However, these works assumed that the cache placement is static, which means the caching placement matrix is fixed and known at the cloud.

In order to improve the efficiency of cache-enabled networks, <cit.> conducted an investigation into the design of caching policy. In <cit.>, an fairness-aware cache placement and delivery strategy for an OFDMA-based heterogeneous cellular networks is proposed to improve the network performance, which consists of two separated phases: caching phase and delivery phase. In <cit.>, the caching problem at the small cell BSs was considered, and a caching policy was designed such that the cache-hit-ratio is maximized. To minimize the downloading latency, <cit.> proposed a distributed caching algorithm. The line of works in <cit.> are further expanded in <cit.> for a cache-enabled Cloud-RAN to consider the trade-off between the transmission power and the backhaul cost of the Cloud-RAN system as a normalized
weighted sum and, minimized the network cost with respect to
both the beamforming matrix and the cache placement matrix
by considering the quality of service (QoS), peak transmission
power, and cache capacity constraints. However, these works are only focused on designing the beamformers and cache placement matrix while assuming the user association matrix is given and known at the cloud.

The user association problem that is mainly concerned with load balancing, was discussed in <cit.>. The key point here is accounting for both wireless channels and the number of UEs connected to each BS. Assuming caching policy is given, <cit.> designed the user association policy such that maximizes the average download rate. These studies, however, did not optimize the user association and cache placement jointly. As a result, the system was led to an inefficient operating point.

Designing jointly the caching strategy and the user association policy in cache-enabled wireless networks is considered in <cit.>. To minimize the number of requests performed by the macro BSs in a small-cell network, <cit.> designed a joint data caching and user association policy.  To this end, <cit.> jointly designed user association and video caching policy by minimizing the user experienced delay while considering different quality requirements for each user. To obtain an optimal trade-off between the content availability and the load balancing, an online algorithm was proposed in <cit.>. To maximize the system throughput in a coordinated small-cell cellular system, the problem of joint designing of caching, user association, and routing is discussed in <cit.>. Considering distinct users have different wireless channels, <cit.> jointly designed the caching and user association policy by minimizing the average delay of small cell UEs in a
heterogeneous network. Jing et. al. <cit.>, proposed a joint cache delivery and placement strategy by optimizing the user association in different time scales. The line of these works was further
expanded in <cit.> for a cache-enabled Cloud-RAN network
to lessen the backhaul traffic by maximizing a proportional
fairness network utility. However, <cit.> considered a single input single output (SISO) case in which both UEs and BSs
are equipped with a single antenna, and each user is only
connected with one BS.

In practice, the cache placement and the content delivery
(precoding and user association) usually happen in different
timescales. Cache placement usually takes much longer
(e.g., days or hours) than that of content delivery (e.g.,
seconds). Therefore, like <cit.>, we study a mixed-timescale
joint optimization, but in this case for content placement
and content delivery in the cache-enabled cloud radio access
networks to maximize a weighted backhaul-aware network
utility function subject to the peak transmission power and
cache capacity constraints at all BSs. The cache placement
reduces the backhaul consumption and provides more CoMP
opportunities. It is adaptive to the long-term popularity of
data, therefore, the caching strategy should be adaptive to the channel statistics instead of the instantaneous channel
realization in each channel coherent time. In contrast, the
role of the content delivery is to guarantee delivery of a
better average throughput to each user and be adaptive to
instantaneous channel state information.






 §.§ Main Contributions
 
This paper differs from previously studies particularly in its aim to bring a consideration of caching along with user association and resource allocation. We optimize the tradeoff between backhaul reduction and network throughput by maximizing a weighted backhaul-aware network utility function. Furthermore, we consider multiple real-world factors for effective content caching such as popularity distribution, caching placement from the user perspective, and temporal and spatial locality of the content demand, in order to accommodate challenging use cases with strict quality of service requirements. That is why the original problem and, therefore, the three sub-problems in our paper are completely different from the previous works. The main contributions of this paper can be summarized as follows.



  
  * For the first time, we define and maximize the network throughput as a function of caching placement strategy, user association policy, precoding vectors, probability that a file is requested by a specific user, and the distance from all connected BSs to this specific user. We consider multiple real-world factors for effective content caching such as popularity distribution, caching placement from the user perspective, and temporal and spatial locality of the content demand, in order to accommodate challenging use cases with strict quality of service requirements.
  
  * We introduce the tradeoff between network throughput and backhaul savings by combining user association, MIMO transmit precoding, and cache placement to boost user experience, and identify the interaction between user association, resource allocation and cache placement for a multi-cluster multi-user MEC network.

 
 
   
  * To the best of our knowledge, there is no existing study on jointly optimizing the cache placement and the content delivery. We consider a multi-cluster multi-user MEC network consisting of different users with distinct file preferences, and jointly optimize the mixed-timescale optimization problem of cache placement, user association, and beamforming matrices.
  
  
  * We propose an iterative novel algorithm by leveraging the stochastic parallel successive convex approximation (SCA)-based method and the alternating direction method of multipliers (ADMM) to jointly optimize the aforementioned optimization problem. 
  By reducing the complexity, the proposed algorithm is feasible for future wireless big data processing systems.
  

  








 §.§ Paper Organization and Notations

The remainder of this paper is organized as follows. In Section II, the system model is described and the main assumptions required for our analysis are introduced. Section III, presents the problem formulation and analysis. Simulation results
are presented in section IV. An overview of the results and concluding remarks are presented in Section V.

Notation: Throughout this paper, normal letters are used for scalars. Boldface capital
and lower case letters denote matrices and vectors, respectively. The transposition, the Hermitian
transposition, and the determinant of a complex matrix 𝐀 are denoted by 𝐀^T,
𝐀^H and |𝐀|, respectively. An N × K matrix, with ones
on its main diagonal and zeros on its off-diagonal entries, is denoted by 𝐈_N × K,
while the identity matrix of size N is simply denoted by 𝐈_N. An N × K all-zeros matrix is denoted by 0_N × K. The sets of
complex and real numbers are denoted by ℂ and ℝ, respectively. A circularly
symmetric complex Gaussian random variable (r.v.) is represented by Z=X+jY ∼𝒞𝒩(0,σ^2),
where X and Y are independent and identically distributed (i.i.d.) normal r.v.'s from
𝒩(0,σ^2/2). 𝔼[·] represents the expectation operator. The Hadamard product between two matrices 𝐀 and 𝐁 is symbolized by 𝐀⊙𝐁. 




§ SYSTEM MODEL AND ASSUMPTIONS

We consider a mobile edge caching network consisting of one central computing unit (cloud), B base stations, and K user equipments  as depicted in Fig. 1. Table <ref> summarizes the major notations and symbols used in this paper. The location of the BSs  is modeled by a Poisson Point Process (PPP) with density λ_B while UEs are distributed around each BS independently and uniformly. We partition the area to M clusters. |ℐ_i| and |𝒬_i| indicate the number of UEs and BSs in the i-th cluster, respectively, where 𝒬_i⊆{1,2,…, B}, ℐ_i⊆{1,2,…, K}, 𝒬_i∩𝒬_j = ∅, ℐ_i∩ℐ_j = ∅, ∀ i ≠ j, i,j ∈ℳ≜{1,2,…,M}. Let i_j, i ∈ℳ and j ∈𝒬_i, denote the j-th BS in the i-th cluster and i_k, i ∈ℳ and k ∈ℐ_i, indicate the k-th user in the i-th cluster. BS i_j is equipped with N_t^i_j transmit antennas and a cache that stores s_i_j bits of data while user i_k has N_r^i_k receive antennas. The channel (propagation) coefficient between the i_j BS and the i_k user form channel matrix 𝐆_i_k,i_j = √(β_i_k,i_j)𝐇_i_k,i_j∈ℂ^N_r^i_k× N_t^i_j where β_i_k,i_j is a large-scale fading coefficient that depends upon the shadowing and distance between the corresponding user and BS. The large-scale fading coefficient denoted by β_i_k,i_j = ψ_i_k,i_jd_i_k,i_j^-α, where d_i_k,i_j is the distance between the i_k user and the i_j BS; α is the path-loss exponent; and ψ_i_k,i_j is a log-normal random variable, i.e., the quantity 10log_10(ψ_i_k,i_j) is distributed zero-mean Gaussian with a standard deviation of σ_shadowing. The small-scale fading coefficients, i.e., elements of 𝐇_i_k,i_j, are modeled as i.i.d. complex Gaussian variables with zero-mean and unit-variance. We further assume a block fading model, where small-scale channels are constant over a few time slots with respect to channel estimation and CSI feedback procedures. Similarly, we assume that large-scale fading coefficients β_i_k,i_j stay constant during large-scale coherence blocks. The small-scale and large-scale fading coefficients in different coherence blocks are assumed to be independent.




Each BS i_j is connected to the cloud through a finite-capacity backhaul link B_i_j, i ∈ℳ, j ∈𝒬_i. The cloud has access to the whole data library containing F files, where different contents are independent. Making use of the capacity-limited links restricts the amount of information transfer between the cloud to the BSs. We define Π_i = {π_i_1,…,π_i_|ℐ_i|} as the user request profile at the i-th cluster, where π_i_k denotes the index of the requested file by the i_k user. Users can make random requests from a directory of files ℱ = {f_1, f_2, … , f_F} where each file f_n has size ℓ_f_n bits. For the sake of simplicity, we assume that the cache size at any BS is at least large enough to cache any of the files, i.e., ℓ_f_n≤ s_i_j for all f_n∈ℱ,  i ∈ℳ,  j ∈𝒬_i. Moreover, we assume that the i_k user makes q_i_k requests over a given time interval T. Therefore, 𝐪_i = [q_i_1, …, q_i_|ℐ_i|] indicates the rates of requests that are made by users in the i-th cluster.
We also assume different users in the i-th cluster may have different file preferences. Assuming p̅_i_k,f_n is the probability that i_k user, i ∈ℳ, k ∈ℐ_i, request file f_n∈ℱ, the discrete popularity distribution of files for the users in the i-th cluster can be indicated as


    𝐏_i =
    [     𝐩_i_1;         ⋮;     𝐩_i_k;         ⋮; 𝐩_i_|ℐ_i| ]
    =
    [     p̅_i_1,f_1              …     p̅_i_1,f_F;              ⋮              ⋱              ⋮;     p̅_i_k,f_1              …     p̅_i_k,f_F;              ⋮              ⋱              ⋮; p̅_i_|ℐ_i|,f_1              … p̅_i_|ℐ_i|,f_F ]∈ [0,1]^|ℐ_i| × F

where p̅_m,n represents the probability that the m-th UE in the i-th cluster requests the n-th file. Note that the m-th row of matrix 𝐏_i is a stochastic vector that indicates the discrete probability distribution of the m-th UE.

Since the file popularity distributions seen at each BS depend on the local file popularities of all connected UEs to the BS <cit.>, this matrix will be different from 𝐏_i. The popularity distributions at the BSs in the i-th cluster, namely 𝐏_i∈ [0,1]^|𝒬_i| × F, can be derived as (<ref>) 

where p_i_j,f_n = ∑_k =1^|ℐ_i|d_i_j,i_kq_i_kp̅_i_k,f_n / ∑_k=1^|ℐ_i|d_i_j,i_kq_i_k
denotes the n-th file popularity distribution observed at the j-th BS in the i-th cluster and the denominator is a normalization factor. In practice, by adding up the number of times that the f_n file is requested by users, the value of p_i_j,f_n can be computed at the cloud. Moreover, since user behavior is correlated with the previously requested data, p_i_j,f_n can provide the information regarding the file popularity of the future requests, and thus it helps to efficiently store the files in caches before a request is made. 𝐃_i∈{0, 1}^|𝒬_i| × |ℐ_i| denotes the user association matrix in the i-th cluster, which depicts the connection between the BSs and UEs in the i-th cluster. The user association matrix is structured as


    𝐃_i =
    [     𝐝_i_1;         ⋮; 𝐝_i_|𝒬_i| ]
    =
    [         d_i_1,i_1                 …         d_i_1,i_k                 …     d_i_1,i_|ℐ_i|;                 ⋮                 ⋱                 ⋮                 ⋱                 ⋮;     d_i_|𝒬_i|,i_1                 …     d_i_|𝒬_i|,i_k                 … d_i_|𝒬_i|,i_|ℐ_i| ]

where d_m,n =  1(r̃_m,n≥ r). r̃_m,n is the mn-th entry of the wireless downlink rate matrix 𝐑̃_i∈ℝ^|𝒬_i| × |ℐ_i| in the i-th cluster and represents the achievable data rate from BS m to user n while r guarantees a certain quality of service so that the n-th user would not connect to the m-th BS if the wireless link rate between them was below the threshold r.



Since the caching capacity is limited, the aim of designing a cache placement strategy is to store the most popular contents such that the BSs can directly serve the majority of UEs' demands. We define the content placement matrix at the i-th cluster as 𝐂_i∈{0,1}^F × |𝒬_i|, where 𝐂_i(f_n,i_j) = 1 means the f_n-th content is stored in the i_j BS and 𝐂_i(f_n,i_j) = 0 represents the opposite. The caching matrix will be different for different user in one cluster. To be specific, the caching matrix corresponding to the BSs that are associated with UE i_k, i ∈ℳ and k ∈ℐ_i, can be expressed as

    𝐂_i_k = 𝐂_iΛ(𝐃_i(:,i_k));

where Λ(𝐱) is a diagonal matrix formed from vector 𝐱 and 𝐀(:,n) indicates the n-th column of the matrix 𝐀. Therefore, the sum of all elements in the n-th row of 𝐂_i_k represents the number of BSs who serve the i_k user and cache the f_n-th file. Considering the cache at i_j BS can only store s_i_j bits of data[We assume that a file is either completely cached or not cached at all in a BS. Of course, partial/coded caching techniques can be envisaged, and these are left for future research.], the following constraint should be fulfilled at BS i_j

    ∑_n = 1^F𝐂_i(f_n,i_j)ℓ_f_n≤ s_i_j,    ∀ i ∈ℳ,   j ∈𝒬_i.

Moreover, the i_k user is able to download the f_n-th file from the cache if the following condition is satisfied:

    ∑_j=1^|𝒬_i|d_i_j,i_k𝐂_i(f_n,i_j)> 0;  ∀ i∈ℳ, k ∈ℐ_i,f_n∈ℱ,

otherwise, corresponding links may have backhaul cost to transfer the f_n-th file. As a result, by associating each user with the BSs that cache its requested content, the total backhaul reduction of the aforementioned MEC network can be represented as


    𝔼{∑_i = 1^M∑_k =1^|ℐ_i|∑_j=1^|𝒬_i|d_i_j,i_k𝐂_i(f_n,i_j)} = 
       ∑_i = 1^M∑_k =1^|ℐ_i|∑_n = 1^F∑_j=1^|𝒬_i|d_i_j,i_kp̅_i_k,f_n𝐂_i(f_n,i_j) = ∑_i = 1^MTr(𝐏_i𝐂_i𝐃_i),
where expectation is with respect to the random user requests.

Furthermore, we assume that in the underlying MEC network, a cluster of cooperative BSs serves each UE. To be specific, a cooperating set ℬ_i_k is assigned to i_k user where ℬ_i_k = {i_j|d_i_j,i_k = 1}⊆𝒬_i is formed by aggregating all the BSs that have knowledge of channels 𝐇_i_k,i_j,  i_j∈ℬ_i_k, and have access to i_k user's message. They may also jointly encode the message intended for this user in their transmission <cit.>. Note that, due to the shadowing effect, the |ℬ_i_k| strongest BSs under coordination are not necessarily the |ℬ_i_k| nearest BSs, where |ℬ_i_k|=𝐃_i(:,i_k)_0 denote the set's cardinality. Since each BS may get involved in transmission to more than one UE, the cooperating set of different users may overlap. We designate the set of users served by the i_j BS by 𝒦_i_j≜{i_k| i_j∈ℬ_i_k}⊆ℐ_i. It is worth nothing that since the number of users that a BS can support in a specific frequency and time resource block is limited by the number of BS antennas, it is assumed that 𝒦_i_j≤ N_t^i_j. Moreover, similar to <cit.>, we assume each co-scheduled user operating in the MU-MIMO mode only receives one spatial stream (rank 1 transmission) as specified by the Rel-10 LTE-Advanced standard <cit.>. BS i_j plans to communicate a symbol vector 𝐬_i_j = [s_i_1,i_j, …, s_i_|𝒦_i_j|,i_j]^T∈ℂ^|𝒦_i_j| to its associated receivers, where s_i_k,i_j is the transmit symbol from the i_j BS to the i_k∈𝒦_i_j receiver with unit power of 𝔼{|s_i_k,i_j |^2} = 1 and |𝒦_i_j| denote the set's cardinality.


The main idea behind defining M and ℬ_i_k is that the demand for content shows variations both across time and space and, in this paper, we considered both temporal and spatial locality of the content demand. To be specific, it is crucial to consider the user location since the demand may differentiate from one geographical area to another. This space variation of the content request, referred to as spatial locality, is why we define M clusters, where M can be any arbitrary number. On the other hand, the demand may vary from time to time. This temporal variation of the content request, referred to as time locality, is the reason that we defined the ℬ_i_k cluster associated with user i_k.




Prior to transmitting, the i_j BS linearly precodes its symbol vector 𝐱_i_j = ∑_i_k∈𝒦_i_j√(p̃_i_k,i_j)𝐯_i_k,i_js_i_k,i_j where p̃_i_k,i_j stands for the transmit power allocated to user i_k from the i_j BS and 𝐯_i_k,i_j denotes the unit-norm beamformer that BS i_j uses to transmit the signal s_i_k,i_j to receiver i_k. Each BS i_j is under a transmit power constraint of P_i_j^max and so, the transmit power at the i_j BS is computed as P̃_i_j = 𝔼{𝐱_i_j^2}= ∑_i_k∈𝒦_i_jp̃_i_k,i_j𝐯_i_k,i_j^H𝐯_i_k,i_j = ∑_i_k∈𝒦_i_jp̃_i_k,i_j≤ P_i_j^max <cit.>. Under our assumptions, when user i_k requests file f_n which is available at the cache of the BSs in ℬ_i_k, the received signals from these BSs are combined coherently using coordinated joint transmission. Since there are |ℬ_i_k| BSs participating in the cooperating data transmission to user i_k, at the same frequency and time, we denote s_i_k∈ℂ as the complex data symbol for the i_k UE, where i ∈ℳ and k ∈ℐ_i. Consequently, throughout each symbol duration time, the cooperating BSs transmit the same symbol s_i_k and the expected received signal vector 𝐲_i_k,f_n∈ℂ^N_r^i_k× 1 at the k-th user in the i-th cluster, when user i_k requested file f_n, can be written as 



    𝐲_i_k,f_n   =  ∑_j = 1^|𝒬_i|𝐂_i_k(f_n,i_j)√(p̃_i_k,i_j)√(β_i_k,i_j)𝐇_i_k,i_j𝐯_i_k,i_js_i_k+ 𝐧_i_k


    +
    ∑_n=1^F∑_m=1 
     m≠ k^|ℐ_i|∑_j = 1^|𝒬_i|𝐂_i_m(f_n,i_j)√(p̃_i_m,i_j)√(β_i_k,i_j)×𝐇_i_k,i_j𝐯_i_m,i_js_i_m
       +
    ∑_n=1^F∑_q=1 
     q≠ i^M∑_ℓ = 1^|ℐ_q|∑_j =1^|𝒬_q|𝐂_q_ℓ(f_n,q_j)√(p̃_q_ℓ,q_j)√(β_i_k,q_j)𝐇_i_k,q_j𝐯_q_ℓ,q_js_q_ℓ,













where the first term on the right-hand side represents the received useful signal, the third and fourth terms represent the intra- and inter-cluster interference respectively, and 𝐧_i_k∼𝒞𝒩(0, σ_i_k^2𝐈) is the additive white Gaussian noise (AWGN) at the i_k UE. We assumed that the signals for different users are independent from each other. In  this paper, we  treat interference as  noise and consider a linear receive beamforming strategy so that the estimated signal is given by ŝ_i_k = 𝐮_i_k^H𝐲_i_k,f_n. Indeed, each receiver i_k∈𝒦_i_j, linearly processes the received signal to obtain 𝐮_i_k^H𝐲_i_k,f_n where 𝐮_i_k∈ℂ^N_r^i_k denotes the unit-norm post processing filter at receiver i_k, i.e., 𝐮_i_k^2 = 1. 

As mentioned above, the received interference at the i_k-th UE is the summation of the intra-cluster and inter-cluster interferences. While the former is the interference experienced by the i_k UE from all BSs inside the i-th cluster, i.e.,


    I_i_k,f_n^intra = ∑_n=1^F∑_m=1 
     m≠ k^|ℐ_i|∑_j=1^|𝒬_i|   𝐂_i_m(f_n,i_j)p̃_i_m,i_jβ_i_k,i_j|𝐯_i_m,i_j^H𝐇_i_k,i_j^H𝐮_i_k|^2,

the latter is the received interference from all the BSs outside the i-th cluster and can be represented as


    I_i_k,f_n^inter = ∑_n=1^F∑_q=1 
     q≠ i^M∑_ℓ=1^|ℐ_q|∑_j =1^|𝒬_q|   𝐂_q_ℓ(f_n,q_j)p̃_q_ℓ,q_jβ_i_k,q_j|𝐯_q_ℓ,q_j^H𝐇_i_k,q_j^H𝐮_i_k|^2.



Therefore, the expected SINR at the k-th user in the i-th cluster, when user i_k requests file f_n, is a function of transmit power, cache placement matrix, user association matrix, probability of file being requested, and distance from all connected BSs to i_k user and can be written as Eqn. (<ref>), where 𝐂_q_ℓ(f_n,q_j) = 𝐂_q(f_n,q_j)𝐃_q(q_j,q_ℓ). Therefore the average transmission rate over channel realizations for user i_k can be written as R_i_k,f_n = 𝔼[log(1+ SINR_i_k,f_n)] and the total average throughput of this user can be formulated as



    R_i_k = 𝔼{R_i_k,f_n} = ∑_n=1^Fp̅_i_k,f_nR_i_k,f_n,    ∀ i∈ℳ, k ∈ℐ_i

where expectation is with respect to the random user requests. Note that, the network throughput does not depend on the cache placement matrix (𝐂_i) but depends on the caching matrix corresponding to the BSs that are associated with a specific user (𝐂_i_k). To be specific, no matter the content is cached or not cached in the BS, the user needs to communicate with its associated BSs. The distribution of the UEs' content demands follows a Zipf-like distribution P_ℱ(i) given as P_ℱ(i) = 1/i^γ∑_i=1^Fi^-γ, i ∈ℱ, where γ models the skewness of the popularity profile <cit.>. Depending on both the BSs deployment strategies and the UEs' behavior, γ takes different values. The popularity is uniformly distributed over content files for lower values of γ, meaning UEs have more distinct interests. As γ grows, the popularity becomes more skewed towards the most popular files, which means UEs have very similar file interests and a small subset of files are more desired than the rest.






§ PROBLEM FORMULATION AND ANALYSIS

In this section, the problem of interest is a joint optimization of the content placement and content delivery (precoding and user association). We formulate a mixed-timescale optimization problem which maximizes the trade-off between the backhaul savings and the network throughput. The motivation behind maximizing the trade-off between the backhaul savings and the network throughput is providing a new technique in MEC that can support both low latency (in a low-cost manner) and high throughput requirements for the upcoming 5G wireless network. For maximizing the backhaul reduction, each UE should be associated with a BS (cluster of BSs) that caches the largest amount of its desired contents. However, such a BS might be a long way away. On the other hand, in order to maximize the network throughput, each UE should take the BSs' load into account and accordingly associate with a BS that provides it a reasonably high SINR. Nonetheless, such a BS may not store the user's desired contents. Considering such a tradeoff into account, in this paper the problem of maximizing the user throughput and backhaul savings with respect to the precoding matrix, cache placement matrix, and user association matrix, is formulated subject to peak transmission power, cache capacity, and backhaul capacity constraints.

Let 𝒱 = {𝐯_i_k,i_j(Π_i,{𝐇_i_k,i_j}_j=1^|𝒬_i|): ∀ i,k,j} and 𝒟 = {𝐃_i(Π_i,{𝐇_i_k,i_j}_j=1^|𝒬_i|):∀ i,k,j} denote all the beamforming vectors and user-association matrices for all user request profiles {Π_i}_i=1^M and instantaneous CSI matrices {𝐇_i_k,i_j}_j=1^|𝒬_i|, respectively. Then for a given set of optimization variables (𝒱,𝒟,𝐂_i) and user request profiles {Π_i}_i=1^M, the average utility function of our optimization problem can be expressed as ∑_i = 1^M∑_k=1^|ℐ_i|𝔼[λ R_i_k,f_n + (1-λ)∑_j=1^|𝒬_i|d_i_j,i_k𝐂_i(f_n,i_j)|Π_i] where the expectation is taken with respect to both the CSI and the distribution of user requests, and the parameter controlling the tradeoff between network throughput and backhaul savings is denoted by λ∈ (0,1) so that by adjusting λ we can emphasize one term over the other. The optimization variables are partitioned into short-term (user association and beamforming) and long-term (content placement) variables. While the latter is adaptive to the popularity of data and the channel statistics, the former is adaptive to the instantaneous CSI. The following feasible sets are defined for the cache placement 𝐂_i, the user association 𝐃_i, and the beamforming vectors 𝐯_i_k,i_j for all i ∈ℳ, j ∈𝒬_i, k ∈ℐ_i as follows[It is worth mentioning that although the capacity capability of cloud is much higher than that of caching, but it is by no means that the cloud capability is unlimited in the cloud. Investigating the effect of this constraint in a multi-cluster multi-user cache-enabled CRAN would be an important topic for future work.] 


    𝒮_𝐂   = {𝐂_i: 𝐂_i(f_n,i_j)∈{0,1} , ∑_n = 1^F𝐂_i(f_n,i_j)ℓ_f_n≤ s_i_j},
    
    𝒮_𝐃   = {𝐃_i: 𝐃_i(i_j,i_k)∈{0,1}},
    
    𝒮_𝐯   = {𝐯_i_k,i_j: ∑_k=1^|ℐ_i|Tr(𝐯_i_k,i_j^Hp̃_i_k,i_j𝐯_i_k,i_j)≤ P_i_j^max}.





















Then the joint content placement and content delivery problem 𝒫 is formulated as follows[Note that we are considering a particular realization of the PPP, i.e., B is a sample of a Poisson random variable.]:


    𝐂,𝐃,𝐯maximize      ∑_i = 1^M∑_k=1^|ℐ_i|𝔼[λ R_i_k,f_n + (1-λ)∑_j=1^|𝒬_i|d_i_j,i_k𝐂_i(f_n,i_j)|Π_i] 
       subject to      𝐂_i∈𝒮_𝐂 , 𝐯_i_k, i_j∈𝒮_𝐯 , 𝐃_i∈𝒮_𝐃
             ∑_i_k∈𝒦_i_jd_i_j,i_kR_i_k≤ B_i_j,  ∀ i ∈ℳ,   j ∈𝒬_i

where ∑_i_k∈𝒦_i_jd_i_j,i_kR_i_k denotes the i_j BS's backhaul consumption. The objective function can be expressed in a more compact form as ∑_i = 1^M𝔼[Tr(λ𝐄_i(𝐏_i⊙𝐑_i)+ (1-λ)𝐏_i𝐂_i𝐃_i)] in which 𝐄_i is a F × |ℐ_i| matrix full of 1's, 𝐑_i is a |ℐ_i| × F rate matrix so that its (i_k-f_n)-th element is equal to R_i_k,f_n, and the expectation is taken with respect to the distribution of user requests.

Due to the coupled interference among users and the limited-backhaul capacity constraint, the optimization problem (<ref>) is non-convex. Moreover, the entries of user association and cache placement matrices take binary values 0 and 1, thus the optimization problem falls into a mixed integer nonlinear programming (MINLP) which is NP-hard in general <cit.> and non-tractable in practice. Since it is highly unlikely to compute a globally optimal solution in polynomial time, our goal is to obtain a tractable near-optimal solution by developing effective suboptimal algorithms. By utilizing the timescale separations of the optimization variables and making use of the fact that all constraints are separable, we divide the original optimization problem into three subproblems and propose an iterative algorithm that at each time maximizes the objective function with respect to one variable while assuming the other two variables are given. Therefore, each of these subproblems can be relaxed to a convex problem so that it can be solved efficiently. The mixed-timescale joint optimization of content delivery and content placement can be decomposed to the following sub-problems:




 §.§ Short-term Content Delivery

As mentioned before, the content placement usually takes much longer than the content delivery. Therefore, in this subsection, it is assumed that the user request and the content placement matrix 𝐂_i is fixed and given. Therefore, we pay attention to the joint optimization of beamforming design and user-association (with respect to the user request). We further decouple the joint optimization problem in two stages. At the first stage, we associated each user with a cluster of BSs and at the second stage, assuming the user-association is fixed and given, we design the beamformers. The proposed algorithm is described as follows:

♢  User-association Stage:
 Assuming caching policy and beamforming vectors are given, the user association problem can be simplified as


    𝒫_1:    𝐃_imaximize      ∑_i = 1^M∑_k =1^|ℐ_i|∑_j=1^|𝒬_i|d_i_j,i_kμ_i_j,i_k
       subject to       d_i_j,i_k(1 - d_i_j,i_k) = 0, ∀ i ∈ℳ, j ∈𝒬_i, k ∈ℐ_i
             ∑_i_k∈𝒦_i_jd_i_j,i_kR_i_k≤ B_i_j,  ∀ i ∈ℳ,   j ∈𝒬_i

where μ_i_j,i_k = ∑_n = 1^Fp̅_i_k,f_n𝐂_i(f_n,i_j) represents the amount of backhaul savings by associating the i_k-th UE with the i_j-th BS. Due to the fact that the entries of 𝐃_i take binary values 0 and 1, the optimization problem is a mixed integer optimization over the user association. In order to solve this optimization problem and inspired by the idea used in <cit.>, this paper adopts a new approach called dual analysis. The main idea behind this method is to answer how the optimal value can be deduced from the constraints. This method is used in <cit.> and <cit.> to find a solution to the user association problem in heterogeneous cellular networks under the proportional fairness criterion. Using this method, the optimization problem can be easily decoupled among the clusters and the solution can be expressed as:

    d^∗_i_j,i_k =
    
        1   ,         if μ_i_j,i_k> 0
    
        0   ,         Otherwise

which shows that taking caching placement and thus backhaul reduction into account can be viewed as an additional incentive for UEs to associate with a BS.

  ♢ Beamforming Stage: With fixed user association and request, the problem of designing beamforming vectors 𝐯_i_k and 𝐮_i_k, i ∈ℳ,   j ∈𝒬_i, can be written as  
  
    𝒫_2:    𝐯_i_k,i_j
    𝐮_i_k,i_jmaximize      ∑_i = 1^M∑_k=1^|ℐ_i|log(1 + SINR_i_k,f_n)
    
       subject to      ∑_k=1^|ℐ_i|p̃_i_k,i_j∥𝐯_i_k,i_j∥^2≤ P_i_j,
    
             ∑_i_k∈𝒦_i_jd_i_j,i_klog(1+ SINR_i_k,f_n)≤ B_i_j,

where the optimal short-term bemformers will be calculated with respect to the given user request and thus they do not depend on the file request probability. In order to suit our system model we applied the weighted minimum mean-square error (WMMSE) framework <cit.> into the above optimization problem and modified Proposition 3.2. in <cit.>. In this way, each user can connect to a cluster of BSs instead of being served by only one BS. Thereby, (<ref>) can be effectively rewritten as


    𝐯_i_k,i_j
    𝐮_i_k,i_j
     w_i_kmaximize      ∑_i = 1^M∑_k=1^|ℐ_i|(log(w_i_k)- w_i_kε_i_k+1)
    
       subject to      ∑_k=1^|ℐ_i|p̃_i_k,i_j∥𝐯_i_k,i_j∥^2≤ P_i_j,
    
             ∑_i_k∈𝒦_i_jϱ_i_k,i_jd_i_j,i_kR̂_i_k||𝐯_i_k,i_j||^2≤ B_i_j,

where {w_i_k} are the weights variable introduced by WMMSE framework and {ε_i_k} are the mean square estimation errors which are defined by









    ε_i_k   ≜ |1 - ∑_j = 1^|𝒬_i|𝐂_i_k(f_n,i_j)p̃_i_k,i_jβ_i_k,i_j𝐮_i_k^H𝐇_i_k,i_j𝐯_i_k,i_j|^2 +σ_i_k𝐮_i_k^2
       
    + ∑_(ℓ, q)≠ (k,i)∑_j =1^|𝒬_q|𝐂_q_ℓ(f_n,q_j)p̃_q_ℓ,q_jβ_i_k,q_j|𝐮_i_k^H𝐇_i_k,q_j𝐯_q_ℓ,q_j|^2,

and ϱ_i_k,i_j and R̂_i_k are the iteratively updated weights with a small positive regularization factor and the achievable data rate calculated from the previous iteration as in <cit.>, respectively.

The objective function of (<ref>) is convex with respect to each of the optimization variables 𝐯_i_k,i_j, 𝐮_i_k,i_j, and w_i_k, which enables us to employ the block coordinate descent method to solve it <cit.>. To be specific, we maximize the cost function of (<ref>) by updating one of three variables 𝐯_i_k,i_j, 𝐮_i_k,i_j, and w_i_k, while assuming the rest are given. In particular, we iteratively run the following steps.

∙ Initializing all the transmit beamformers 𝐯_i_k,i_j's, ∀ i, k, j, and minimizing the weighted sum-MSE leads us to the MMSE receiver 𝐮_i_k as follows

 
    𝐮_i_k^mmse = 𝐉_i_k^-1𝐇_i_k,i_j𝐯_i_k,i_j

  where
  
    𝐉_i_k = ∑_q=1^M∑_ℓ = 1^|ℐ_q|∑_j =1^|𝒬_q|𝐂_q_ℓ(f_n,q_j)p̃_q_ℓ,q_jβ_i_k,q_j
    ||𝐇_i_k,q_j𝐯_q_ℓ,q_j||^2+ σ_i_k^2𝐈

is the covariance matrix of the total received signal at UE i_k.


∙  By fixing all 𝐮_i_k's and 𝐯_i_k,i_j's, ∀ i, j, k, the weights, for all i and k, can be updated as follows

      
    w_i_k = (1-∑_j = 1^|𝒬_i|𝐂_i_k(f_n,i_j)p̃_i_k,i_jβ_i_k,i_j𝐮_i_k^H𝐇_i_k,i_j𝐯_i_k,i_j)^-1
∙  By fixing all w_i_k's and 𝐮_i_k's, the transmit beamformers can be calculated using the following optimization problem

  
    𝐯_i_k,i_jminimize      ∑_i = 1^M∑_k=1^|ℐ_i|  w_i_kε_i_k
    
       subject to      ∑_k=1^|ℐ_i|p̃_i_k,i_j∥𝐯_i_k,i_j∥^2≤ P_i_j ,
             ∑_i_k∈𝒦_i_jd_i_j,i_kR̂_i_k||𝐯_i_k,i_j||^2≤ B_i_j

Problem (<ref>) is convex and (<ref>) and (<ref>) can be locally implemented at the users. Therefore, we solve the problem (<ref>) in a distributed manner based on the alternating direction method of multipliers (ADMM) <cit.>. 
In what follows, it is shown that by exchanging a fair amount of information between UEs and BSs the ADMM can be applied in a distributed fashion to solve optimization problem (<ref>).
In order to achieve a distributed implementation of the ADMM in the aforementioned MEC network, the following assumptions are made (similar to <cit.> and <cit.>). We assume that each BS j ∈ Q_i knows 𝐇_i_k,i_j for all i_k user in cluster ℬ_i_k and each user i_k can estimate the interference plus noise covariance matrix. Under these assumptions, the ADMM can be applied distributively. Note that, in order to identify the beamforming vectors in a distributed fashion, our aim here is to have a same form as the one in <cit.>. To do so, we introduce auxiliary variables {𝐱_i_k,i_j} and {X_i_k^i_k,i_j} and rewrite problem (<ref>) as (13).











 Then, we form the augmented Lagrangian ℒ_ρ(𝐯,𝐱,𝐗;λ_i_k,𝐳_i_k) as follows


    ℒ_ρ(𝐯,𝐱,𝐗;λ_i_k,𝐳_i_k) = 
       ∑_i = 1^M∑_k =1^|ℐ_i|∑_n=1^Fp̅_i_k,f_n(|√( w_i_k) - ∑_j = 1^|𝒬_i|p̅_i_k,f_n^2𝐂_i_k(f_n,i_j)p̃_i_k,i_jβ_i_k,i_j X_i_k^i_k,i_j|^2
       + ∑_n=1^F∑_(ℓ, q)≠ (k,i)∑_j =1^|𝒬_q|p̅_q_ℓ,f_n^2𝐂_q_ℓ(f_n,q_j)p̃_q_ℓ,q_jβ_i_k,q_j|X_i_k^q_ℓ,q_j|^2)
       + Re(∑_i = 1^M∑_k =1^|ℐ_i|∑_m=1 
     m≠ k^|ℐ_i|∑_j = 1^|𝒬_i|⟨√(w_i_k)𝐮_i_k^H𝐇_i_k,i_j𝐯_i_m,i_j - X_i_k^i_m,i_j,λ_i_k^i_m,i_j⟩)
       +ρ/2∑_i = 1^M∑_k =1^|ℐ_i|∑_m=1 
     m≠ k^|ℐ_i|∑_j =1^|𝒬_i|| √(w_i_k)𝐮_i_k^H𝐇_i_k,i_j𝐯_i_m,i_j - X_i_k^i_m,i_j|^2
       +Re(∑_i = 1^M∑_k =1^|ℐ_i|∑_q=1 
     q≠ i^M∑_ℓ=1^|ℐ_q|∑_m =1^|𝒬_q|⟨√(w_i_k)𝐮_i_k^H𝐇_i_k,q_m𝐯_q_ℓ,q_m - X_i_k^q_ℓ,q_m, λ_i_k^q_ℓ,q_m⟩) 
       + ρ/2∑_i = 1^M∑_k =1^|ℐ_i|∑_q=1 
     q≠ i^M∑_ℓ=1^|ℐ_q|∑_m =1^|𝒬_q|| √(w_i_k)𝐮_i_k^H𝐇_i_k,q_m𝐯_q_ℓ,q_m - X_i_k^q_ℓ,q_m|^2
       + Re(∑_i =1^M∑_k=1^|ℐ_i|∑_j=1^ |𝒬_i|⟨𝐯_i_k,i_j - 𝐱_i_k,i_j,𝐳_i_k,i_j⟩)
       + ρ/2∑_i =1^M∑_k=1^|ℐ_i|∑_j=1^|𝒬_i|𝐯_i_k,i_j - 𝐱_i_k,i_j^2

where ρ is the penalty parameter, and λ_i_k≜{λ_i_k^i_m,i_j|m,k ∈ℐ_i,  j ∈𝒬_i} and 𝐳_i_k≜{𝐳_i_k,i_j∈ℂ^N_t^i_j|k ∈ℐ_i,  j ∈𝒬_i} are the scaled dual variables for the last three sets of equality constraints.


The ADMM approach consists of three steps. First, minimizing the augmented Lagrangian ℒ_ρ over the decision variables 𝐯, while assuming all the other variables are given at their current values. Second,  minimizing the augmented Lagrangian ℒ_ρ over the decision variables {𝐱,𝐗}, assuming the rest of variables are given and fixed. While the latter is a constrained optimization problem the former is an unconstrained one. The last step consists of a simple dual update. 

Therefore, assuming 𝐱 and 𝐗 are given, the optimization problem with respect to 𝐯 can be expressed as


    𝐯minimize      ℒ_ρ(𝐯,𝐱,𝐗;λ_i_k,𝐳_i_k),

which can be decomposed into i = 1, …, M, k = 1, …, |ℐ_i|,  j = 1, …, |𝒬_i|

    𝐯_i_k,i_jminimize      f(𝐯_i_k,i_j)

where f(𝐯_i_k,i_j) is defined as


    f(𝐯_i_k,i_j) ≜Re(∑_m=1 
     m≠ k^|ℐ_i|λ_i_m^i_k,i_j√(w_i_m)𝐮_i_m^H𝐇_i_m,i_j𝐯_i_k,i_j)+ρ/2∑_m=1 
     m≠ k^|ℐ_i| |√(w_i_k)
       𝐮_i_m^H𝐇_i_m,i_j𝐯_i_k,i_j - X_i_m^i_k,i_j|^2+ Re(𝐳_i_k,i_j^H(𝐯_i_k,i_j - 𝐱_i_k,i_j))
       
    + ρ/2𝐯_i_k,i_j - 𝐱_i_k,i_j^2.



Assuming 𝐯 is given, the constrained optimization problem with respect to {𝐱,𝐗} can be expressed as


    𝐱,𝐗minimize      ℒ_ρ(𝐯,𝐱,𝐗;λ_i_k,𝐳_i_k),
       subject to      ∑_k=1^|ℐ_i|p̃_i_k,i_j∥𝐱_i_k,i_j∥^2≤ P_i_j,  ∀ i ∈ℳ, j ∈𝒬_i
             ∑_i_k∈𝒦_i_jd_i_j,i_kR̂_i_k||𝐯_i_k,i_j||^2≤ P_i_j,  ,∀ i ∈ℳ, j ∈𝒬_i

which can be decomposed into 


    X_i_k^i_k,i_jminimize      g(X_i_k^i_k,i_j)

where g(X_i_k^i_k,i_j) is defined as


    g(X_i_k^i_k,i_j) ≜ -∑_m=1 
     m≠ k^|ℐ_i|∑_j=1^|𝒬_i| X_i_m^i_k,i_jλ_i_m^i_k,i_j
       +∑_n=1^Fp̅_i_k,f_n(|√( w_i_k) - ∑_j = 1^|𝒬_i|p̅_i_k,f_n^2𝐂_i_k(f_n,i_j)p̃_i_k,i_jβ_i_k,i_j X_i_k^i_k,i_j|^2)
       +ρ/2∑_m=1 
     m≠ k^|ℐ_i|∑_j=1^|𝒬_i||√(w_i_m)𝐮_i_m^H𝐇_i_m,i_j𝐯_i_k,i_j - X_i_m^i_k,i_j|^2,

and 


    𝐱_i_k,i_jminimize      h(𝐱_i_k,i_j)
    
    subject to     ∑_k=1^|ℐ_i|p̃_i_k,i_j∥𝐱_i_k,i_j∥^2≤ P_i_j,
    
       ∑_i_k∈𝒦_i_jd_i_j,i_kR̂_i_k||𝐯_i_k,i_j||^2≤ P_i_j,  ,∀ i ∈ℳ, j ∈𝒬_i

where h(𝐱_i_k,i_j) is defined as follows


    h(𝐱_i_k,i_j)   ≜Re(∑_k=1^|ℐ_i|∑_j=1^| 𝒬_i|⟨𝐯_i_k,i_j - 𝐱_i_k,i_j,𝐳_i_k,i_j⟩)
       +  ρ/2∑_k=1^|ℐ_i|∑_j=1^|𝒬_i|𝐯_i_k,i_j - 𝐱_i_k,i_j^2

Note that all the three subproblems (<ref>) and (<ref>)–(<ref>) are convex problems and can be solved efficiently. After calculating each variable at the m+1 iteration, we will update the λ_i_k as discussed earlier.




 §.§ Long-term Caching Placement:

As discussed earlier, the caching problem can be decoupled among all the clusters in the aforementioned MEC network. Specifically, the caching problem for the i-th cluster can be expressed as the stochastic optimization problem (<ref>) (since the average rate is in the form of expectation over all possible channel realizations and user requests), where μ_i_j,f_n= ∑_k = 1^|ℐ_i|p̅_i_k,f_nd_i_j,i_k represents the amount of backhaul savings due to storing f_n-th file in the i_j-th BS's cache. Maximization of ∑_n = 1^Fμ_i_j,f_n𝐂_i(f_n,i_j) for a simple SISO case in which both BSs and UEs are equipped with a single antenna, and each UE is only connected with one BS is considered in <cit.>. This maximization poses the following question: which files should be cached in the i_j-th BS to achieve the backhaul reduction μ_i_j,f_n? Under the condition that all files have the same size, the optimal solution to maximize ∑_n = 1^Fμ_i_j,f_n𝐂_i(f_n,i_j) is caching the s_i_j files that make the largest backhaul reduction; i.e.,





    𝐂_i^∗(f_n,i_j) =
    
        1   ,         if μ_i_j,f_n∈{μ_i_j,f_1, …, μ_i_j,f_s_i_j}
    
        0   ,         Otherwise

where μ_i_j,s is the s-th item which is more requested in the list of μ_i_j,f_n <cit.>. If each content has different sizes, the aforementioned caching strategy at each BS becomes a knapsack problem <cit.> that can be solved using dynamic programming. Here, we consider a more general case than the one discussed in <cit.>, by considering the multi-cluster multi-user MIMO network in which each UE can be associated with a cluster of BSs.  Consequently, the optimization problem becomes more complicated and the objective function can be written as (<ref>)

where 𝐂_-i≜ (𝐂_q)_q ≠ i and 𝐌_i(𝐂_i) = ∑_jp̅_i_k,f_n^2𝐂_i(f_n,i_j)d_i_j,i_kp̃_i_k,i_jβ_i_k,i_j𝐇_i_k,i_j𝐯_i_k,i_j𝐯_i_k,i_j^H𝐇_i_k,i_j^H, and 𝐍_i(𝐂_-i) = ∑_(ℓ, q)≠ (k,i)∑_jp̅_q_ℓ,f_n^2𝐂_q(f_n,q_j)d_q_j,q_ℓp̃_q_ℓ,q_j β_i_k,q_j𝐇_i_k,q_j𝐯_q_ℓ,q_j𝐯_q_ℓ,q_j^H𝐇_i_k,q_j^H+σ^2𝐈.
















Since the entries of 𝐂_i take binary values 0 and 1, the optimization problem falls into a MINLP category, which is usually NP-hard in general <cit.> and non-tractable in practice. Therefore, we are interested in obtaining a near-optimal solution. Inspired by the method proposed in <cit.>, we allow the binary variables to take real values in [0,1], and hence the original MINLP can be relaxed to a non-linear programming problem. Our aim is to introduce a distributed solution method that efficiently computes the stationary solutions of this problem. To do so, we develop a stochastic parallel successive convex approximation (SCA)-based method <cit.> and substitute a series of strongly convex problems for the optimization problem (<ref>). The main idea here is approximating the non-convex objective function O(𝐂_i,𝐂_-i) by a suitable convex approximation. To be specific, the aim of BSs in each cluster is to choose a feasible cache placement matrix 𝐂_i that maximizes the objective function O(𝐂_i,𝐂_-i) assuming the strategy profile 𝐂_-i is given. Inspired by the scheme introduced in <cit.>, our method is based on solving a sequence of parallel convex problems, i.e., one for each cluster. Each of these convex problems is obtained by maintaining the convex structure of the utility function while linearizing the rest around 𝐂̅_̅i̅. To isolate the inter-cluster and intra-cluster interferences that make O(𝐂_i,𝐂_-i) nonconvex, we define the utility function of the clusters other than the i-th cluster as


    f_i(𝐂_i,𝐂_-i)    = ∑_s ≠ i(λ∑_k = 1^|ℐ_s|∑_n = 1^Fp̅_s_k,f_n𝔼[log_2( 𝐈 + 𝐌_s(𝐂_s)
       𝐍_s^-1(𝐂_-s))]+(1-λ)∑_n = 1^F∑_j=1^|𝒬_s|μ_s_j,f_n𝐂_s(f_n,s_j)).



Making the objective function convex can be done by keeping the convex part O_i(𝐂_i,𝐂_-i) while linearizing the nonconvex part f_i(𝐂_i,𝐂_-i). Therefore, we use the first order Taylor series expansion of the function f_i(𝐂_i,𝐂_-i). 
that is given by:

    f_i(𝐂_i,𝐂_-i)≈ f_i(𝐂̅_i,𝐂_-i) + f_i^'(𝐂_i,𝐂_-i)|_𝐂_i = 𝐂̅_i(𝐂_i - 𝐂̅_i),

where 𝐂_i -𝐂̅_i is small, thus the higher order terms can be neglected so that the Taylor’s expansion truncated to the first order. Recalling that d/dx(log_a(f(x))) = f(x)^'/(f(x)ln a), the first-order differential is given by

    f_i^'(𝐂_i,𝐂_-i) = ∑_s ≠ i(λ∑_k = 1^|ℐ_s|∑_n = 1^Fξp̅_s_k,f_n/h(𝐂_i)×
       -∑_j =1^|𝒬_s|p̅_s_k,f_n^2𝐂_s(f_n,s_j)d_s_j,s_kp̃_s_k,s_jβ_s_k,s_j𝔼{|𝐇_s_k,s_j𝐯_s_k,s_j|^2}/(∑_j =1^|𝒬_q|p̅_q_ℓ,f_n^2𝐂_q(f_n,q_j)d_q_j,q_ℓp̃_q_ℓ,q_jβ_s_k,q_j𝔼{|𝐇_s_k,q_j𝐯_q_ℓ,q_j|^2}+ σ^2𝐈)^2)


where ξ = ∑_j =1^|𝒬_i|p̅_i_ℓ,f_n^2   d_i_j,i_ℓp̃_i_ℓ,i_jβ_s_k,i_j𝔼{|𝐇_s_k,i_j𝐯_iq_ℓ,i_j|^2} and h(𝐂_i) is given by (<ref>).
 
By keeping only the linear term in the Taylor’s expansion of f_i(𝐂_i,𝐂_-i) around 𝐂̅_i and adding a proximal like regularization term, the objective function in (<ref>) can be approximated as


    Õ(𝐂_i,𝐂_-i)    = O_i(𝐂_i,𝐂_-i)+ 𝐂_i(f_n,i_j)f_i^'(𝐂_i,𝐂_-i)|_𝐂_i = 𝐂̅_i
       -τ_i/2|𝐂_i(f_n,i_j) - 𝐂̅_i(f_n,i_j)|^2
where τ_i is a given nonnegative constant. We can approximate (<ref>) by a set of |𝒬_i| per cluster problems given by

    𝐂_i∈𝒦maximize      Õ(𝐂_i,𝐂_-i)

where 𝒦≜{𝐂_i(f_n, i_j)|∑_n = 1^F𝐂_i(f_n,i_j)ℓ_f_n≤ s_i_j}. Using the proposed algorithm in <cit.>, for each BS we have the following best response mapping which consists of solving iteratively the sequence of a (strongly) convex optimization problem
  
    𝐂_i^∗(f_n,i_j) =     𝐂_i∈𝒦max      Õ(𝐂_i,𝐂_-i)

Unlike (<ref>), (<ref>) is strongly convex and can be efficiently solved by numerical iterative
algorithms.

(A Summary of Overall Operation)
Utilizing the timescale separation of the optimization variables, we divide the original solution into short-term content delivery and long-term content placement. While the short-term process consists of user-association and beamforming optimization, the long-term process is composed of cache content placement. MEC incorporates cloud computing capabilities into wireless networks. The network, therefore, benefits from the cloud capability to perform substantial and large-scale resource allocation and interference management. The content placement and the content delivery optimizations are performed in the cloud in order to overcome with any memory requirements. The content placement and the content delivery optimizations are performed in the cloud. The caching placement strategy is adaptive to the channel statistics. As soon as the user request profile changes, the cloud computes the updated cache placement and passes it to the BSs. Then the BSs update their cache. In each channel coherence time, the CSI is acquired from the users through feedback, and the user-association and beamforming vectors are determined based on the instantaneous channel realization.



 (Computational Complexity)
Since we employ the WMMSE algorithm <cit.> for designing the beamformers, the computational complexity of the beamforming optimization problem is much like the WMMSE, with the difference being that the introduced ADMM-based algorithm decomposes the original large-scale problem into parallel small-scale subproblems. As a result, it needs more complex calculations than the coordinated descent method which is more desirable when the network size is small. However, the computation complexity of the proposed algorithm increases at a slower linear rate with respect to the number of users. The computational complexity of the user-association algorithm is similar to <cit.> and is polynomial in relation to the network size. However, we further lower the complexity of associating a user with a BS by taking content placement into account and excluding the candidate users that increase the backhaul consumption from consideration. The computational complexity of the long-term caching placement is exceedingly low due to the fact that for each realization of the user request profile, the only thing the introduced algorithm needs to do is a simple Jacobi/Gauss-Seidel update. 

To be specific, denote B, K, N_t, and N_r as the total number of BSs, the total number of users in the system, the number of transmit antenna at each BS, and the number of receive antenna at each user, respectively. We calculate per iteration complexity, where an iteration of algorithm means one round of updating all users’ beamforming and user-association matrices. Under these conditions, each iteration of the proposed algorithm involves the computation of the MMSE receiver vector. To determine this vector in the proposed algorithm, we need to first calculate the covariance matrix of the total received signal at each receiver and then compute their sum. Consequently, the per-iteration complexity of the receive beamformer is 𝒪(K^2 B^2 N_t N_r^2 + K^2B^2 N_r N_t^2 + K^2 BN_t^3+ KBN_r^3 ) . In order to obtain the global computational complexity of the ADMM, again, we calculate the per-iteration complexity which means obtained point should satisfies ϵ-optimality condition ℒ_ρ(𝐯̂,𝐱̂,𝐗̂;λ_i_k,𝐳_i_k) - ℒ_ρ(𝐯,𝐱,𝐗;λ_i_k,𝐳_i_k) ≤ϵ. Hence, the per-iteration complexity of the (<ref>) and (<ref>) is 𝒪(28N_t^4 ) where lower order terms are ignored.
 




§ SIMULATION EVALUATIONS


In this section, we evaluate the performance of the proposed schemes in MEC networks. The setup of our experiments is shown as follows: we simulated a multi-cluster multi-user MEC network in which the locations of the BSs are modeled based on a PPP process with density λ_B = 1/(π R_B^2) = 5 BS/km^2 which corresponds to an average inter-site distance of 500 m. Multiple UEs are randomly and uniformly distributed around each BS, excluding an inner circle of 35 metersas illustrated in Fig. <ref>. The transmission is subject to interference from all neighboring BSs that do not serve the specific user. The transmit antenna power gain and the transmit power at each BS is set to 10 dBi and 46 dBm, respectively. The noise variance at the UE is fixed to -174 dBm. System bandwidth is taken as 5 MHz. We consider a possible antenna configuration in a typical deployment scenario for LTE/LTE-Advanced systems: 4 transmit and 2 receive antennas. The simulation is run for 1000 channel realizations where each channel is uncorrelated Rayleigh fading and each channel element is drawn i.i.d from a complex Gaussian distribution with zero mean and variance 1. The path-loss is generated using 3GPP (TR 36.814) methodology, PL(dB) = 148.1 + 37.6log_10(d), where d is the distance in kilometers. The log-normal shadowing parameter is assumed to be 8 dB. The total number of files available in the cloud is considered as F = 20. For the sake of simplicity, it is assumed that all files have the same size of one while the caches of the BSs can be filled with the s = {1, 2, 4, 8, 10} bits of the most popular files. A Zipf-like distribution with parameter 0.56 is considered for the file popularity.

The influence of the weighted coefficient on the objective introduced function in (<ref>) is demonstrated in Fig. <ref>. The results can be interpreted as follows: when λ increases the backhaul savings plays a less critical role than the network throughput. Conversely, when λ approaches zero the backhaul reduction dominates the objective function. Fig. <ref> also investigates the influence of the cache size. It shows that the defined weighted objective function of the network with bigger cache size always performs better than the system in which the BSs have a smaller cache. The reason is the smaller the cache sizes, the smaller the portions of the contents can be cached. Therefore, the files must be fetched from the cloud, which increases the backhaul usage. Moreover, when the size of caches grows from 2 to 8, an increase of approximately 76.42% in the backhaul savings is observed. Furthermore, 84% additional increase is acquired when the cache sizes enlarge from 1 to 2. This shows that even a small size of cache at each BS causes a substantial decrease in the backhaul usage.

In order to compare the performance of the proposed algorithm with some benchmarks, we consider the benchmark algorithm proposed in <cit.> (which is considered as a benchmark by many authors). Note that, despite our interest in joint optimizing of the beamforming, user association, and cache placement, no one to the best of our knowledge has studied maximizing the trade-off between network throughput and backhaul savings in a MIMO multi-user multi-cluster MEC networks. The proposed algorithm in <cit.> considered the joint optimizing beamforming and user association while considering the caching strategy is fixed. Fig. <ref> demonstrates the performance comparison between our scheme and the ones proposed in <cit.>. A different metric, normalized network cost, is used for the comparison, which is defined as a weighted sum of the backhaul cost and the transmit power cost. As shown in Fig. <ref>, compared to the full group sparse beamforming algorithm and the partial group sparse beamforming algorithm our introduced algorithm can reduce the network cost, which can interpreted as: taking caching placement into account can be viewed as an additional incentive for backhaul reduction.















The average network throughput versus the SNR and the number of UEs in the MEC network are plotted in Fig. <ref> and <ref>, respectively. In Fig. <ref>, we assume that each BS has the same cache size of 4 and the network contains 10 UEs. The algorithm is initialized by choosing a randomly generated feasible point. Moreover, the termination criterion is satisfied when the absolute value of the network throughput error in two consecutive rounds becomes smaller than 10^-2. In Fig. <ref> we assumed that UEs have the same SNR, due to the fact that co-scheduled UEs usually have similar SNRs in multi-user MIMO operation. The average network throughput is plotted for two SNR values. It is observed that the average sum rate gradually increases when the number of UEs becomes larger.
















In addition, the average number of iterations required by
the proposed algorithms to converge versus the number of UEs is plotted in Fig. <ref>. The average is taken over 1000 independent channel realizations. It is observed that the algorithm converges in several steps. Moreover, the average CPU time versus the total number of UEs is plotted in Fig. <ref>. Our experiments were run using MATLAB R2016b on a 3.6 GHz Intel(R) Xeon(R) E51620 Processor Cores machine, equipped with 8 GB of memory. As can be expected, the average CPU time increases with the number of UEs.


















§ CONCLUSION

In this paper we introduced a novel iterative algorithm to increase the network throughput and backhaul savings of a multi-cluster multi-user MEC network, by jointly optimizing the user association, caching placement, and beamforming design. The proposed algorithm utilizes the ADMM along with the stochastic SCA-based method and enables all BSs to update their optimization variables in parallel. Simulation results demonstrate that efficiently designing of the content placement along with the content delivery greatly influence the backhaul savings and network throughput.













IEEEtran



