On Cost Minimization for Cache-Enabled D2D Networks with Recommendation

Yu Hua,Yaru Fu,Qi Zhu,*

1 The Key Wireless Laboratory of Jiangsu Province,Nanjing University of Posts and Telecommunications,Nanjing 210003,China

2 School of Science and Technology,Hong Kong Metropolitan University,Hong Kong 999077,China

Abstract: To accommodate the tremendous increase of mobile data traffic,cache-enabled device-to-device(D2D) communication has been taken as a promising technique to release the heavy burden of cellular networks since popular contents can be pre-fetched at user devices and shared among subscribers.As a result,cellular traffic can be offloaded and an enhanced system performance can be attainable.However,due to the limited cache capacity of mobile devices and the heterogeneous preferences among different users,the requested contents are most likely not be proactively cached,inducing lower cache hit ratio.Recommendation system,on the other hand,is able to reshape users’request schema,mitigating the heterogeneity to some extent,and hence it can boost the gain of edge caching.In this paper,the cost minimization problem for the social-aware cache-enabled D2D networks with recommendation consideration is investigated,taking into account the constraints on the cache capacity budget and the total number of recommended files per user,in which the contents are sharing between the users that trust each other.The minimization problem is an integer non-convex and non-linear programming,which is in general NP-hard.Therewith,we propose a timeefficient joint recommendation and caching decision scheme.Extensive simulation results show that the proposed scheme converges quickly and significantly reduces the average cost when compared with various benchmark strategies.

Keywords: edge caching; cost minimization; D2D communication;recommendation systems

I.INTRODUCTION

The spiraling growth of intelligent devices and smart applications triggers the tremendously increased mobile data traffic,bringing unprecedented pressure to current wireless cellular networks due to the limited radio resource and backhaul link capacity.Recently,it has been reported that the contents downloaded by users is concentrated in some popular contents [1].To release networks’ pressure and reduce users’ content retrieving costs,cache-enabled device-to-device(D2D) communication has been acknowledged as a promising enabler.In detail,by pre-fetching popular contents at users’ devices and sharing them with the other subscribers via D2D communication links,an enhanced system performance is attainable [2–5].To be more specific,the authors in[2]investigate caching scheme to maximize the total offloading probability of the D2D system.Whilst,interference alignment(IA) is leveraged in [3]to manage the interference among small cells and exploit caching and computing to simplify the network topology.The authors in[4]investigate the joint content pushing and transmit power allocation to maximize D2D network’s energy efficiency.In [5],authors focus on maximizing contents’successful transmission probability via optimizing the cache placement at both base station(BS)side and users’ side.In [6],authors analyze the competitions in D2D UE-to-network(UE-NW)relay networks to further enhance the caching design.In [7],unmanned aerial vehicles(UAVs)with caching are used as SBSs to transmit video to mobile users.In order to disrupt the potential eavesdropping,authors utilize the idle SBSs to generate jamming signal.

However,the gain of cache-enabled D2D is highly dependent on the homogeneity among users’ preferences due to the limited cache capacity.Even for popular contents,the limited cache capacity is unable to cache them all.In addition,users may not request the most popular contents because they are not interested in the contents of that theme.As a result,it is impossible for users to cache all popular contents that all users are interested in.To further boost the performance of edge caching,some proactive mechanisms are of necessity to be considered,in which recommendation has received widespread attention due to its capability of reshaping users’request mode.Nowadays,recommendation systems have played an important role in content providing sites.The recommendation systems can help the sites to present the contents that best suit the users’preferences to the users.As a result,users’requests will be affected by recommendations when facing massive information.For example,30%of the overall views on YouTube come from relevant recommendations[8],and 80%of viewing hours on Netflix are brought by the recommendation system[9].

The basic idea of shaping demand in this paper is that the recommender system does not recommend the contents that best match the interest of each user,but to recommend the contents that match the user preference and can be accepted by other users.After reshaping users’request mode by recommendation,the gain of edge caching will be higher.The practicability of recommendation in cache-enabled systems is well verified by[10–13].Specifically,in[10]the authors propose a joint caching policy and recommendation scheme at BSs to maximize the caching gain for multi-cell networks.Optimal caching and recommendation decisions are designed in[11]to maximize“direct”cache hit and“soft”cache hit.In[12]the authors propose a heuristic caching-aware recommendation scheme to maximize the cache hit ratio for small cell networks.Moreover,the authors in [13]investigate the joint recommendation and caching decision for multi-cell wireless content caching systems from a perspective of revenue maximization.All the existing works[10–13]focus on the cache placement at BS sides.How the recommendation affects the performance of cache-enabled D2D network is of the same significance but receives less attention,which stimulates our work.Furthermore,it is of the same importance for cache-enabled D2D network to minimize the system cost[14]such that each user can reduce its cost of retrieving contents,meanwhile the network service providers can reduce the cellualr traffic,but none of the aforementioned work on the cache-enabled D2D network with recommendation focus on it.

For brevity,the main contributions of this article are summarized as follows:

• We formulate the cost minimization problem for cache-enabled D2D networks with recommendation,taking into consideration the recommendation size and cache capacity budget of each user.The minimization problem is a non-convex and non-linear integer programming problem,which is in general NP-hard.

• For the sake of analytical tractability,the original problem is decoupled into two subproblems.Thereinafter,we first solve the two subproblems separately,and then we propose an alternative algorithm to jointly optimize the two types of decision variables,along with the convergence analysis.

• Simulation results show that our devised algorithm converges quickly and reduces the average cost when compared with the benchmark strategies.

The remainder of this paper is organized as follows.In Section II,we present our system model for socialaware cache-enabled D2D network.In Section III,we formulate the cost minimization problem.In Section IV,joint recommendation and caching decision algorithm is proposed.Section V shows the simulation results.Section VI concludes this paper.

II.SYSTEM MODEL

We consider a cache-enabled device-to-device (D2D)network with one base station (BS) serving a set ofKusers,referred to asK={1,2,...,K}as shown in Figure 1.Each user is equipped with a capacitylimited storage with the size ofCkto pre-fetch and store some popular contents.We stipulate that each user requests the file from a catalogue ofIcontent items.DefineIas the index set of all the contents.Fork ∈Kandi ∈I,letyk,i ∈{0,1}be the cache indicator of userkto itemi.With the cache capacity requirement at userk,we have

in whichLirepresents the bit size of contenti,wherei ∈I.

For a typical userk,its content retrieving can be summarized as follows: the requested content is selfprovided given that the content is locally cached.As such,there is no need to establish a outward communication link.Otherwise,userkwill seek possible help from the neighbor users located within its D2D communication region,whose index set is denoted byUp(k)for userk.Given that neither the local storage nor the D2D helpers have cached the desired item,the demanded content will be supplied by BS.It is noteworthy that the BS has sufficient large storage capacity to supply all the requested contents from users.Moreover,we assume that two proximal users can communicate with each other directly if the distance between them is less than the pre-determined maximum D2D communication distance,referred to asRD2D.Furthermore,it is assumed that frequency division multiplexing is adopted for D2D communications,and the bandwidth is large enough for each D2D pair.Thereby,there is no intereference between different D2D links[15].

2.1 Social Network

Taking into consideration the selfishness of individual users,one may not be willing to provide contents to its neighbors due to privacy concerns and power consumptions.To remedy this issue,a social network aware D2D communication model is adopted in this paper.To be more specific,we useG(K,E) to characterize the social connectivity among users,in whichKdepicts the vertex set andErepresents the edge set,namely,E={(k,j) :ekj=1,∀k,j ∈K,k≠j},in whichekj ∈{0,1}.Thereof,ekj=1 if and only if userskandjtrust each other.In other words,the content sharing between userkand userjis applicable.According to[16],the trustworthiness between userkand userj,denoted byψk,j,is calculated as follows:

whereRk,jis the physical distance between userskandj.In addition,Ok,jis the number of historical communications between usersiandj.Besides,depicts the number of times that userskandjcommunicate with their common neighbors.Moreover,θandϕare the weighting factors.

With the definitions,we say that userkforms a social connection with userj,i.e.,ekj=1,ifψk,jis higher than the pre-determined thresholdψth.Denote byUs(k)={j:ekj=1,∀j ∈K,j≠k}the index set of users that trust userk,which means that users inUs(k)are willing to share their cached contents to userk.With foregoing analysis,the index set of users who can provide the possible content sharing with userkvia D2D communication,denoted byU(k),is obtained as follows:

2.2 Personalized Content Preferences Distribution

It is assumed that each of the contents inIis relevant toMthemes.Fori ∈ I,letfi=(fi(1),fi(2),...,fi(M))be the feature vector of contenti,whosem-th elementfi(m) denotes the degree of relevance between itemiand themem,wherefi(m)∈[0,1]and Σ(m)=1.Similarly,fork ∈K,we definefk=(fk(1),fk(2),...,fk(M))with Σ(m)=1 be the feature vector of userk,whosem-th component,i.e.,fk(m)∈[0,1],indicates how much userkis interested in the item related to the themem.Considering the heterogeneity among users,we assume that each user has a different preference distribution towards the contents inI.Fork ∈K,defineas the content preference distribution of userk,where=1.Based on [12],ppkrefcan be characterized by the feature vectors of userkand contenti,i.e.,fkandfi,respectively.For ease of elaboration,we introduce an auxiliary variableak,i,and it is quoted below:

Fork ∈K,we normalize the auxiliary variableak,iover all contents and hence the preference distribution of userkis given as follows:

So far,the information as regards each user’s inherent preference distribution is known.

2.3 Personalized Content Demand Distribution

In this subsection,we investigate the impact of recommendation on user’s contents demand.In principle,recommendation is capable of increasing the demand probabilities for the recommended contents while degrading the requests for the un-recommended items.LetRbe the total amount of the recommended contents to each user and(i)=1/Rbe the improvable factor that the recommendation brings to theseRcontents.Moreover,define(i) as the probability of userkin terms of requesting the recommended contenti.Meanwhile,denote by(i)the demand ratio of userkin regard to the unrecommended contenti.Following the content request model in[12],we have

wherewrk ∈(0,1) represents the recommendation weight of userk,and(i)is defined in(5).We define a binary decision variablexk,ito represent the recommendation indicator of userkto contenti.Specifically,xk,i=1 if itemiis recommended to userkandxk,i=0 otherwise.With the definitions,the probability of userkwith respect to request itemiis quantified below:

wherek ∈Kandi ∈I.In addition,are defined in(6)and(7),respectively.

Before ending this subsection,we declare that although the telecom operators can implement recommendations at user side to enhance the networks’performance,users may not pay attention to or download the recommended contents due to their personalized preference distribution.To solve this problem,we defineas the minimum preference threshold setting for userkto guarantee the recommendation quality.To be more specific,the preference of userkto the recommended items must no less thanMore precisely,we have

III.PROBLEM FORMULATION

In this work,we investigate how recommendation and caching can be jointly applied to minimize the costs of D2D-enabled communication networks,taking into consideration the cache capacity budget and the recommendation quality of each user.For simplicity,defineUik={j:yj,i=1,j ∈U(k)}as the set of users who cached contentiand can provide content sharing with userk,wherek ∈Kandi ∈I.In addition,in our system model,different links have different communication costs [14],letdkjibe the cost of userkin terms of retrieving contentifrom userj,which is related to the distance betweenkandj.Besides,definedkbias the cost of delivering contentifrom the BS to userk,which is related to the distance betweenkand BS.Moreover,denote byx=(xk,i)k∈K,i∈Iandy=(yk,i)k∈K,i∈Ithe recommendation and the caching strategy of the system,respectively.

With above mentioned definitions,we mathematically formulated the cost minimization problem as follows:

where(i) in the objective function is given in(8).In addition,(11)reflects the cache storage capacity constraint.(12) ensures thatRitems are recommended to every user and (13) guarantees that if the preference of userkto content(i) is less than,the system will not recommend contentito userk,i.e.,xk,imust be 0.Furthermore,(14)and(15)show that the indicators are binary.

IV.JOINT RECOMMENDATION AND CACHING DECISION ALGORITHM

The problem (10) is an integer non-linear programming problem which is in general NP-hard,and hence it is difficult to be optimally solved.For ease of tractability,we decouple the original problem into two subproblems,namely,recommendation optimization problem and caching placement problem.Thereinafter,we first solve the two subproblems separately,and then we devise an iterative algorithm to jointly optimize the two types of decision variables.It is worth mentioning that BS is responsible for solving the minimization problem,as BS can collect the users’preferences,location information and social relationships in real systems.

4.1 Recommendation Algorithm

In this subsection,we aim to obtain the optimal recommendation policy for a given cache policy.We denote the pure recommendation optimization problem as P1,which is mathematically formulated as follows:

As can be inferred from foregoing discussions,the recommendation decision among users is mutually independent.Thereby,P1 can be further decoupled intoKsubproblems,each of them determines the recommendation policy for an individual user.We take a typical userkas an example to show our developed recommendation optimization scheme,which is derived from simulated annealing algorithm.In detail,we defineXkas the recommendation lists of userkand ¯Xkas the index set of the remaining contents that can be recommended to userk,i.e.,the remaining contents that satisfy inequality (13).By randomly swapping the associated sets regarding contentsiandi′,wherei ∈ Xkandi′ ∈,a new recommendation set,referred to asX′k,is obtained.Denote bythe costs of userkunder recommendation stateXk.Given thatC(X′k)< C(Xk),X′kis accepted as the new recommendation set of userk.Otherwise,Xkchanges toX′kwith a cost-based probability,denoted byPk(Xk,X′k),which is calculated below:

whereBcis the Boltzmann constant.In addition,is the minimum cost of userkobtained so far.For simplicity,the pseudo-code of the developed recommendation algorithm for userkcan be summarized in Algorithm 1.

The time complexity of simulated annealing algorithm mainly depends on the total iteration number[17].Since we have definedtmaxas the maximum iteration number,the time complexity is mainly determined by the maximum iteration numbertmax.Simulated annealing algorithm can obtain the approximate optimal solution quickly but this solution may not be globally optimal because it is a random algorithm.However,if the iteration number is large enough,we can get the global optimal solution with a high probability.

Algorithm 1.Recommendation algorithm.Require: Initial the index set of contents that are recommended to user k,i.e.,Xk.Thereby,¯Xk can be obtained.Let Cmink= C(Xk).Besides,denote by tmax the maximum iteration number.1: Set t=1 2: while trandom(0,1)then 7: Xk=X′k and ¯Xk=¯X′k.8: else 9: Keep Xk and ¯Xk unchanged.10: end if 11: Update Cmink ≜min{C(Xk),C(X′k),Cmink }.12: Let t=t+1.13: end while 14: return Xk

4.2 Caching Algorithm

In this subsection,we aim to optimize the cache policy with a given recommendation strategy.We define P2 as the pure caching optimization problem,which is quoted below:

It is noteworthy that the objective function of P2 has no explicit and closed-form expression although(i)is attainable under fixedxbased on(8).Hereinafter,an iterative algorithm is developed to solve P2.

Algorithm 2.Caching algorithm.Require: Initial the index set of the cached contents at user k,i.e.,Yk(0),where k ∈K.1: Set t=0 2: repeat 3: Let t=t+1.4: for k=1 to K do 5: Update Yk(t)by solving the Knapsack problem with the dynamic programming 6: if F(Yk(t))>F(Yk−1(t))then 7: Yk(t)=Yk(t−1).8: end if 9: end for 10: until F(t)=F(YK(t))11: return Yk

Fork ∈K,we defineYk(t) as the index set of the cached contents at userkin thet-th iteration.Within each iteration,a typical userkupdates its cached contents with the other users’ caching policies known as prior.More precisely,given the other users’ caching states,the cache placement optimization for userkrecasts as a classical Knapsack problem,which can be optimally solved by the dynamic programming algorithm [18].LetF(Yk(t)) be the total cost of the network after userkupdating its cache state in iterationt.We stipulate thatYk(t)=Yk(t−1) given thatF(Yk(t))> F(Yk−1(t)).In other words,each user’s state change induces an enhanced system performance.Denote byF(t) the system cost in iterationt.As can be inferred from the foregoing analysis,we haveF(t)=F(YK(t−1)) and we defineF(Y0(t))=F(t).For ease of brevity,we summarize the pseudo-code of the proposed cache pushing approach in Algorithm 2.

4.3 Joint Recommendation and Caching Decision Algorithm

In this subsection,we devise an iterative algorithm to jointly optimize the two types of decision variables,namely,xandy,respectively.We definex(l) as the optimal recommendation policy andy(l)as the cache policy obtained in thel-th iteration.First,we initialize a temporary cache policyy(0) that satisfy constraint(11)and(15)and then in the iterationl,we can get the optimalx(l)from recommendation algorithm with the giveny(l−1).Further,we can obtainy(l) through caching algorithm by usingx(l) andy(l−1) as the inputs.Repeating the foregoing processes,an optimized strategy profile{x∗,y∗}is attainable for the original cost minimization problem (10).For clarity,the pseudo-code of joint recommendation and caching decision algorithm is summarized in Algorithm 3.

Algorithm 3.Joint recommendation and caching decision algorithm.Require: Initial a temporary cache policy,i.e.,y(0),and set x(0)=0.1: Set l=0 2: repeat 3: Let l=l+1.4: get the optimal x(l) from recommendation algorithm by y(l−1).5: get the optimal y(l)through caching algorithm by x(l)and y(l−1)6: until{x(l),y(l)}={x(l−1),y(l−1)}7: return {x(l),y(l)}

Lemma 1.The proposed iterative algorithm is convergent.

Proof.If the iteration number of recommendation algorithm is large enough,we can get the global optimal solution of recommendation [17].Besides,the caching algorithm ensures that the objective function value does not increase in each iteration.In addition,the objective function has a lower bound which must be greater than 0.Since our proposed algorithm decreases monotonically with a lower bound,the proof is completed[19].

V.SIMULATION RESULTS

In this section,we conduct Monte-Carlo simulation to evaluate the performance of our developed joint decision making method.We stipulate that the users are randomly and uniformly distributed within a disk of radius 200 m.We use feature vectorsfiandfkto model user preferences and content items,respectively.The elements of the two vectors are randomly and uniformly valued.Besides,we definedkji=Dkj/RBas the cost of userkin terms of retrieving contentifrom userj,whereDkjrepresents the distance between userskandjandRBrepresents the service radius of BS.In addition,the simulation parameters are set as follows:M=8,K=10,I=50,wrk ∈(0.5,1)andLi=1 fori ∈I.

For performance comparison,three baseline schemes with different recommendation algorithms and cache decision policies are taken into account and they are given below:

• Baseline 1: In this algorithm,the cache deployment is determined by our devised Algorithm 2.In addition,each user is recommended by its top-Rmost preferred contents.

• Baseline 2: In this algorithm,each user caches its most interested contents to fill in the storage entity.Besides,the recommendation decision is the same as that in Baseline 1.

• Baseline 3: In this algorithm,the cache dscision is done by our Algorithm 2 and we recommend nothing to users.

Hereinafter,we evaluate the performance of the foregoing schemes from two aspects,namely,the convergence performance and the system costs.

Figure 2 and Figure 3 shows the convergence performance of the proposed scheme,in which we considerRD2D=80 andRD2D=150 for Figure 2 and Figure 3,respectively.From Figure 2 and Figure 3,we can see that the proposed scheme converges quickly,demonstrating the efficacy of our explored joint optimization algorithm.By comparing Figure 2 and Figure 3,we see that the curves converge faster and the costs are lower in Figure 3 than Figure 2.This is becauseRD2Din Figure 3 is larger,which means more users can share contents via D2D communication.

To show the performance gap between our proposed algorithm and the optimal solution,we used the exhaustive search enabled algorithm to find the global optimal solution,and then we did the performance comparison between the global optimal scheme and our method and baselines,as shown in Figure 4,in which we setR=3,K=3 andI=6 and users are randomly and uniformly distributed within a disk of radius 50 m within the service range of BS.It can be seen that the average cost obtained by our proposed algorithm is very close to the global optimal solution and there is a significant gap between Baseline 1,2 and the optimal algorithm.Nevertheless,the exhaustive algorithm exposes a worst-case exponentially increased time complexity,which is not affordable for the wireless systems,whilst our algorithm can converge very quickly.

Figure 5 and Figure 6 depicts the cost performance of the proposed scheme and its three benchmark algorithms,whereinR=5 and the D2D communication distance is set to be 80 and 150 for Figure 5 and Figure 6,respectively.From Figure 5 and Figure 6,we can see that the average costs of our proposed scheme and two baselines with recommendation algorithm are distinctly less than the baseline without recommendation,showing the effectiveness of recommendation in enhancing system performance.In addition,the costs of each scheme decrease with the increasing ofC.Moreover,we see that when cache sizeCis smaller than the number of recommendationsR,our proposed scheme is better than the two baselines with recommendation.In addition,the smaller the cache capacity,the greater the benefits brought by our scheme.This is because Baseline 1 and Baseline 2 recommend each user’s most preferred contents,whilst different users are more likely to request the contents that they are interested in.Due to the heterogeneity between users’ preferences,the gain of edge caching will be degraded due to the limited cache capacity.Our proposed scheme can mitigate the heterogeneity of users’preferences to some extent to make better use of limited capacity.The average cost of the three schemes with recommendation drops quickly asCgrows,while the rate of decline slowed down asCcontinues to increase,and the average cost of our proposed scheme is similar to the two baselines with recommendation.This is because,when cache size is large enough,the system can always recommend the files that users have cached and they are interested in.Furthermore,we observe that all the schemes in Figure 6 achieves smaller costs when compared to that in Figure 5,implying that D2D communication is a promising technology in the cache-enabled network with recommendation.

Figure 7 and Figure 8 depicts the impact of the number of recommendations on the cost performance of the proposed scheme and its two benchmark algorithms in which we assume thatC=3 and the D2D communication distance of Figure 7 and Figure 8 is 80 and 150,respectively.It is observed that,when the number of recommendationsRis smaller than the cache sizeC,the same conclusion can be drawn: The cost performance of the three algorithms is similar.With the increase of recommendations,the benefits of our proposed algorithm are gradually showing up.For example,whenRD2D=80 andR=6,our proposed scheme saves cost by 18.65%and 22.04%when comparing to Baseline 1 and Baseline 2,respectively.Meanwhile,whenRD2D=150 andR=6,our proposed scheme saves cost by 23.96%and 28.33%when comparing to Baseline 1 and Baseline 2,respectively.In additon,from Figure 7 and Figure 8 we can see that the average cost is increasing as the number of recommendations grows.This is because when fewer contents are recommended,the probability of these files being requested will be larger in the system model.After reshaping users’request mode by recommendation,the users’ request will be concentrated on a few recommended contents,then we can get a low average cost by caching these contents.But in reality,we can’t recommend two or three contents to users,we usually recommend some contents for users to choose when facing massive information.In this case,the superiority of our algorithm can be better reflected.

In addition,Figure 9 and Figure 10 shows the cache hit ratio of the proposed scheme and its three benchmark algorithms,in which we setR=5 and the D2D communication distance is set to be 80 and 150 for Figure 9 and Figure 10,respectively.We can see that the cache hit ratio of our proposed scheme and Baseline 1,2 is distinctly higher than the Baseline 3,which without recommendation.It shows that recommendation can effectively improve the cache hit rate of the networks.Moreover,when the cache size of users is limited,our proposed scheme can get a higher cache hit ratio than Baseline 1 and Baseline 2 as well.In addition,by comparing Figure 9 and Figure 10,we observe that the cache hit ratio in Figure 9 is smaller than that in Figure 10,which means that D2D communication is a promising technology in improving cache hit ratio.

VI.CONCLUSION

In this paper,we investigated the cost minimization problem for cache-enabled D2D networks with recommendation.We proposed a time-efficient joint recommendation and caching decision scheme for this NPhard problem.Simulation results have demonstrated that the proposed scheme converges quickly and distinctly reduces the average cost when compared with the benchmark strategies without recommendation.In addition,when the cache size of users is limited,our proposed scheme can get a lower cost compared with the two algorithms with recommendation.The future work includes study the cache placement at both BS side and users’ side with recommendation to further reduce the average cost of the system.

ACKNOWLEDGEMENT

This work was supported in part by the grant from the Research Grants Council of the Hong Kong Special Administrative Region,China(Project Reference No.UGC/FDS16/E09/21),in part by the Hong Kong President’s Advisory Committee on Research and Development (PACRD) under Project No.2020/1.6,in part by the National Natural Science Foundation of China (NSFC) under Grants No.61971239 and No.92067201,in part by Jiangsu Provincial Key Research and Development Program under grant No.BE2020084-4,and in part by Postgraduate Research&Practice Innovation Program of Jiangsu Province under Grant KYCX200714.