Printer Friendly

A Bankruptcy Game for Optimize Caching Resource Allocation in Small Cell Networks.

1. Introduction

Driven by the sustainable growth of mobile devices [1] and diversified access needs of wireless users [2], mobile data traffic has increased dramatically. According to Ericsson Mobility Report [3], mobile data traffic grew by around 52% between Q2 2017 and Q2 2018. To cope with the data traffic challenge, small cell networks (SCNs), comprising the densification of small cells (SCs) [4], have been proposed. The SCNs have been regarded as an important cellular network architecture for improving data throughput and balancing traffic load [5].

In the SCNs, pre-caching popular content is widely beneficial to both users and operators [6]. For users, they can directly get data resources from the nearby SCs' local cache [5], reducing latency wait time [7]. For mobile operators, pre-caching technology reduces the load on the traffic network by reducing backbone and avoiding repeated data long-distance transmission with the central cloud server [8]. To some extent, it can ease the network congestion caused by repeat downloads and enhance the spectrum utilization [9]. Pre-caching technology has become one of the key technologies in the fifth generation (5G) mobile communication system.

However, in the context of content caching [35], the actual wireless pre-caching system is more complicated. First, mobile Internet operator that owns SC and provides caching services, plays the role of Internet Service Provider (ISP). Meanwhile, Internet Content Providers (ICPs) are pre-cached files providers that want to cache their files to SC [16]. From a business perspective, they are two different interest groups that need us to look at separately. Moreover, Each ICP is both rational and selfish, which means they have its own interests and goals. All these ICPs want to put more their own contents in the caching space, so that they can provide better data services and gain greater market share. The following question then arises: For operators, how to balance the interests of ICPs while improve mobile users' satisfactions?

Our answer to this question follows from three key observations: (1) Each ICP only supplies one type of file, Basically. For example, YouTube only provides videos and Instagram mostly supplies images. (2) User's access result presents diversity on file types. As pointed out by [11], the user's access probability follows the file popularity distribution. If we sort the files by popularity, we will see a result that different types of files interspersed with each other. At the same time, ICP have different influences and users also have their own preferred file types [35]. Therefore, when users access high-popularity files, they will access multiple types of files. (3) Satisfaction: The satisfactions of content providers mainly come from whether the operators allocate the cache space they need [19]. On the other hand, users' satisfaction mainly depends on whether the contents they want to access are in the SCs or not. The higher the cache hit rate, the higher the users' satisfaction [13].

Under the above observations, we further proposed as follows: from a user perspective, both diverse type and popular contents should be cached. The former meets user access habits while the latter guarantees cache hit ratio. At the same time, operators need to consider the interests of various ICPs to ensure balance and improve the fairness of distribution. Considering that the general size of different types content is also different (for example, the storage size of video is generally larger than the storage size of picture and text), each ICP's demand for space and satisfaction are not the same. We can put the competition problem between ICPs into the framework of game theory, so that the problem can be solved effectively and fairly.

In this paper, we study the pre-caching for ICPs in a small cell of Small Cell Network (SCN). A general approach based on bankruptcy game model is proposed for finding the optimal caching policy. In this approach, ICPs allocate SC's pre-caching space according to bankruptcy game model. After the allocation, operator store different type files with high cache value in each allocated area. Considering that the cache value is measured by multiple factors, we propose a caching value assessment algorithm based on analytic hierarchy process to optimize the caching strategy and increase users' cache hit ratio. Our simulation results show that our approach can improve the cache hit ratio while ensuring ICPs' satisfaction. That means our approach satisfies the interests of both ICPs and users. In summary, the main contribution of this paper are as follows:

(1) Focus on the caching space allocation of ICPs, we propose an allocation model based on bankruptcy games. ICPs are players under this framework, they collaborate and compete, which can balance the interests of ICPs and improve the efficiency of caching space utilization.

(2) We also optimize the caching strategy which takes both the user's access result and cache hit ratio into account. The cache value is proposed which consider multiple features of the content (type, popularity, and size) and determine the weights of features based on Analytic Hierarchy Process (AHP).

(3) Our simulation results show that in the case of a network operator and multiple content providers, our approach can improve the cache hit rate while balancing the interests of ICPs.

The rest of this paper is organized as follows. In Section 2, we review the previous work in pre-caching technology. In Section 3, we describe the system model and formulate the distributed collaborative problem as a bankruptcy game. We describe our cache optimization strategy in Section 4. Our simulations and numerical results are detailed in Section 5, and we present the conclusions of this paper in Section 6.

2. Related Work

Small cell network is considered as a core architecture in the evolution of 5G cellular networks. In recent research works, ultra-dense small cell network has been proposed and discussed [1].

The basic idea of ultra-dense small cell network is to densify cellular networks with a high network densification [1,4]. In [1] and [4], the network architecture was proposed. In [1], the authors proposed a potential network architecture for ultra-dense heterogeneous network and provided an access scheme to improve the network efficiency. The authors of [4] not only proposed distribution network architecture, but also investigated the backhaul network capacity and energy efficiency. Besides, the performance constraints were analyzed in [36, 37]. In [36], the authors illustrated the transition behaviors that dominated by different factors and offer the guidance on management of SCNs. The work in [37] discussed network performance from users' perspective, that is, evaluate the impact of user mobility in SCNs.

As can be seen from above works, the exist study in SCNs mainly around the network architecture and limits. Considering the data traffic challenge in SCNs, optimize pre-caching resource allocation is a promising technique.

Pre-caching technology is widely used to pre-cache resource that has not yet requested by users. The two main factors affecting the cache performance are: the accuracy of cache value estimation [10] and the efficiency of cache space utilization [12]. The existing literature has studied a number of problems related to pre-caching in heterogeneous networks such as [10]-[17]. In [10]-[11], the authors have studied the popularity of cached files and believed the high popularity means cache value. The work in [12] investigated the cache space allocation problem in cellular networks to maximize the user success probability. With the higher data rates provided by mobile operators, users start accessing more types contents especially video and music though their mobile devices. The work in [5] studied the video layer layout in SCN, the caching scheme take both popularity and quality preference into account. Collaborative caching strategies have also been gradually proposed to improve cache efficiency by utilizing coverage overlap of small cells [13]-[14] and coded transmission methods [15]. In [35], a cooperative optimal solution to content caching, a joint design of allocation and caching, was proposed. [16] proposed the fully cooperative caching case during which a centralizer helps all small cells to make caching decisions. A framework for the joint optimization of cache content placement has been introduced in [17], which optimize rate allocation for users with different quality requirements.

The caching strategy discussed above does solve some of the problems encountered with pre-caching techniques. However, the actual wireless pre-caching system is more complicated. From a business perspective, ISP (i.e. operator) and ICP are two different interest groups that need us to look at separately. In the case where each ICP wants to put files into the cache space, operator need to balance demands and interests between ICPs. With the goal to identify strategic interaction among multiple interest groups, game theory has been applied in various fields. Bankruptcy game is the game theory which is used to model distribution problems [20].

In this paper, focus on the caching space allocation of ICPs, we propose an allocation model based on bankruptcy games. After the allocation, the operator store files with high cache value in each allocated area. As far as we know, there is no prior work on ICP's cache resource allocation in SC networks which based on bankruptcy game model.

3. System model

3.1 Problem Formulation

We consider the interaction between one mobile Internet provider (i.e. ISP) and multiple ICPs. We assume that there is one SC with a cache size of V and there are N ICPs wants to store some of its own files in the cache. Each ICP has only one type of file, which means that different file type corresponds to different ICP. User access diverse types of files, they tend to access high-popularity files, but they also have their own preferred file types. Every wireless user can access one file or multiple file types. The specific visit situation is shown in Fig. 1.

Let N = {1,..., N} be the sets of ICPs, with |N| = N being the number of ICPs. There are M files coexisting in the repository. Each ICP has [a.sub.1],[a.sub.2],...,[a.sub.N] files, which satisfies M = [[SIGMA].sup.N.sub.i=1][a.sub.i]. We assume that each ICP wants a cache size of [b.sub.i] (i = 1, 2, ..., N). Y is the total required cache size by all ICPs, which satisfies Y=[N.summation over i=1] [b.sub.i]. Since each ICP wants to maximize its own revenue, that is, it wants to occupy as much SC's cache space as possible, then the following assumption that is reasonable:

Y=[N.summation over i=1] [b.sub.i] >V (1)

That means the cache space required by all ICPs is much larger than the space owned by SC. This fully reflects the greediness of individual ICP. Because SC's cache space is quite limited and cannot meet the demands of all ICPs, operator need allocate cache space reasonably and fairly. Meanwhile, operator needs to consider the user's access behavior and increase the cache hit rate. How to allocating space and pre-caching contents is the problem to be solved in this paper.

The notations and the descriptions for the bankruptcy model and cache space allocation approach are shown in Table 1.

3.2 Bankruptcy Game Model

Bankruptcy game is used to solve distribution problems which is modeled as a cooperative game [20]. In the case that the amount of money left by the bankrupt company is not enough to satisfy all creditors' demands, all creditors can use the bankruptcy game to complete the distribution. Because this is a cooperative game, in order to get a better and more fair rewarding, the players cooperate with each other to form an alliance. After the formation of the coalition, the income obtained is represented by a characteristic function [21].

In this paper, the space allocation method among the ICPs proposed is a multiplayer cooperative game featuring bankruptcy games. As shown by (1), the size of the cache space is much smaller than that of the ICPs claim (i.e., sum of the demands). ICPs work together to form a coalition S, which is defined as a subset of N(S [subset] N). Assuming that ICPs share information about respective demands (the size of cache space), the claims can be modeled as a cooperative game. Based on the bankruptcy game model, SC's cache space and different ICPs are modeled separately to the bankrupt company and creditors in the game. The selection of the game characteristic function, representing the interests attributed to each player in a coalitional game, is a precondition for the formation of coalitions [22]. A figure to demonstrate the space allocation based on bankruptcy game model is shown in Fig. 2.

We assume that the ICP group apart in the coalition S to decide how to share the cache space among them. They will be able to share the cache space left by other content providers after they get what they demand. That is, V - [[SIGMA].sub.i[member of]N\S] [b.sub.i]. In fact, the best coalition should be a large alliance of all ICPs. In this way, it could avoid separation and the game's characteristic function satisfies super additivity [24].

Definition 1: A bankruptcy game [25] is given by (N, v), where MA represents the collection of players and players may form [2.sup.N] coalitions in a game. For any two coalitions S, K [member of] [2.sup.N], the game's characteristic function satisfies the following conditions [23]:

v(S [union] K) [greater than or equal to] v(S) + v(K) (2)

That means the game's characteristic function v satisfies super additivity. Only when characteristic function v satisfies the super additivity condition, the necessity of forming a new alliance can be achieved.

In our model, V [greater than or equal to] 0 is the resource that has to be divided among the members of N . b is the ICP claim vector which satisfies: [N.summation over (i=1)] [b.sub.i] > V. In addition, the game's characteristic function v satisfies super additivity which means that coalition creates new value and cooperation makes it sense.

v(S) = max{0,V- [[SIGMA].sub.i[member of]N\S][b.sub.i]} (3)

where v([empty set]) = 0 and v(N) = V.

It should be noted that solutions to cooperative game are qualified with respect to the satisfaction of rationality constraints. In other words, the space size that ICP i obtains after participating in the alliance shouldn't be less than the space size that ICP i does not participate in the alliance. Because once this happens, the ICP i will not agree to join the coalition because of its own interests. Therefore, the solution vector H = {[h.sub.1],[h.sub.2], ..., [h.sub.N]}, which means the allocation that each ICP can obtain by forming a coalition, must satisfy the following constraint conditions.

H = {[h.sub.1], ..., [h.sub.N]}|[summation over (i[member of]N)][h.sub.1] = v(N),[h.sub.i] [greater than or equal to] v(i),[for all]i [member of] N} (4)

Moreover, if the solution vector T is not stable, there is at least one ICP that is unsatisfied with the coalition. To get the stable solution vector T = {[t.sub.1], ..., [t.sub.N]}, existence conditions as follows should be added to (4).

[summation over (i[member of]S)][h.sub.i] [greater than or equal to] v(S),[for all]S [subset] N (5)

Therefore, we establish a bankruptcy game model (N,v),N = {1,***,n}. For participating providers, solution vector H = {[h.sub.1], [h.sub.2],..., [h.sub.N] } satisfies (4) and (5).

3.3 Nucleolus Theory

The bankruptcy game is a cooperative game method used to simulate allocation problems. Solutions to bankruptcy games are essentially qualified with respect to the constraints (4) and (5).

The Nucleolus [26], appealing solution concept, is the imputation that minimizes the worst situation between demand and assigned. It is computed by minimizing the largest excess.

Definition 2: In order to evaluate satisfaction of the alliance S for the solution vector H = {[h.sub.1], [h.sub.2],..., [h.sub.N] }, An out-of-value indicator is defined as follows [25]:

e(S, h) = v(S)-[summation over (i[member of]S)][h.sub.i] (6)

The size of e(S,t) reflects the satisfaction of alliance S with regard to allocation T. The bigger e(S,t) is, the more dissatisfied the alliance S is with regard to the allocation T, because the sum of the allocation of all providers in S is far from reaching the cooperation surplus v(S) it creates; the smaller e(S, t) is, the more satisfied the alliance S is with respect to the allocation T .

For the case mentioned before, we establish the nucleolus theory distribution model as follows: find the minimum value of maxe(S,t) among the [2.sup.n] -1 possible combinations of n ICPs.

minmaxe(S,t) s.t. (4) and (5)

However, the nucleolus of the game is likely to be an empty set. If it is not an empty set, the nuclear allocation is likely not to be unique. In this case, we want to find the only solution.

3.4 Shapley Value

The Shapley value [27] is a very intuitive solution concept in Game Theory. It contains N real numbers, which represent the resources that players get in a game (N,v). All players are assigned according to the Shapley Value which can be expressed as n-dimensional vector [phi](v) = [[[phi].sub.1](v),[[phi].sub.1](v), ..., [[phi].sub.N](v)]. In our model, the Shapley Value [[phi].sub.i](v) means the space size which the ICP i (i.e. player i) obtained. Most importantly, the solution to the Shapley Value is unique, that is why we choose Shapley Value to get the stable solution vector T = {[t.sub.1],*** [t.sub.N]}. This value must satisfy the following three axioms:

Axioms 1: The total gain is distributed as follows:

[summation over (i[member of]N)][[phi].sub.i] (v) = v( N) (7)

This theorem is called the efficiency theorem [28]. It reflects the overall rationality that the sum of the distributions obtained by all players is the distribution obtained by the coalition.

Axioms 2: If i and j are two players who are equivalent in the sense that [29]:

v(S [union]{i}= v( S [union]{ j}) (8)

For every subset S of N which contains neither i nor j, then [[phi].sub.i] (v) = [[phi].sub.j] (v) (9)

This theorem is called the symmetrical theorem. It reflects the player's name does not affect the outcome of the game.

Axioms 3: If two coalition games described by gain functions v and w are combined, then the distributed gains should correspond to the gains derived from v and the gains derived from w:

[[phi].sub.i] (v + w) = [[phi].sub.i] (v) + [[phi].sub.i] (w) (10)

This theorem is called the linearity theorem [30]. It indicates that, when any two independent games are joined together, the new game consists of the direct addition of the original two games.

According to the above axioms, we can get a function that satisfies the following definition: Definition 3: The Shapley value is a way to distribute the resources to the players, satisfying the above axioms. The amount that player i gets given in a coalitional game is [31]:

[[phi].sub.i] (v) = [summation over (S[[subset].bar] N)] [|S|!(n - |S| - 1)!/n!] (v(S [union] {i}) - v(S)) (11)

Where |S| is the number of elements in the set S . n is the total number of players and the sum extending over all subsets S of N not containing player i. The formula can be interpreted as follows: assume the coalition being formed one group at a time, with each group member ask for their contribution (v(S [union] {i}) - v(S)) as a fair compensation, and then for each group member to get the average of this contribution. It can form an alliance.

The sum of Shapley values [26] is the size of the SC's cache space need to be allocated, that is:

[summation over (i[member of]N)][[phi].sub.i] (v)=V (12)

Therefore, the size of the cache space obtained by v providers of different files should meet the following conditions:

[t.sub.i]=[[phi].sub.i] (v) (13)

In order to assess the satisfaction of each provider's earnings (the amount of cache space obtained), the expected index (EI) is defined as the following formula:

[mu] = [[[phi].sub.i] (v)/[b.sub.i]] (14)

Where [b.sub.i] is the demand space that each ICP claims. The fairness evaluation of the proposed method Jain's fairness index [32] is defined as:

[mathematical expression not reproducible] (15)

With the Shapley value, the cache resources of the SC are reasonably and equitably distributed to ICPs of different content types, which improves the efficiency of cache space utilization.

4. Optimized Caching Strategy

The SC has very limited cache space, so able-cached contents are also extremely limited. Considering the user's access behavior and the cache hit rate, we intend enrich the measure of cache value.

We assume the cache value Ecv which consider multiple features of the content (type, popularity and size) and determine the weights of features. Each ICP only supplies one type of file, that is, ICP i only provides the files in type [t.sub.i] (i = 1, 2, ..., N). For each ICP, measuring the cache value of files in its own content store and storing the cached high-value files in the allocated limited space is the key to improving overall cache value. The higher the overall cache value, the higher the user's satisfaction.

We list several parameters used in optimized caching strategy in Table 2.

Based on the cache value Ecv, we propose an algorithm based on the Analytic Hierarchy Process (AHP) to solve the proposed optimization cache problem.

4.1 Popularity

In recent years, pre-caching technology deploys the most popular files in base stations to meet user needs and increase the burden on the backhaul links [13]. In the previous study, a small number of files are accessible to most users has been proved. Hence, the difference in popularity can easily affect the cache value.

Many people use probabilistic methods in which users' requirements are random and follow a certain probability distribution, where the emphasis is on the average result and not on the worst case [33]. There has been particular focus on Zipf distributions, which has a continuous nature. Based on the Zipf distribution, we can give the following definition of the popularity of the file:

Definition 4: The probability that the file is accessed obeys Zipf distribution [34], which is:

[mathematical expression not reproducible] (16)

Where [mathematical expression not reproducible] indicates the access probability of the file x (x = 1, 2, ...,[a.sub.i]) in type i (i = 1, 2, ..., N). ICP i has [a.sub.i] files in its content library. It should be pointed out that r is a parameter of the Zipf distribution, and the value is between 0 to 1. When users' access is concentrated on several files, the users' access behavior can be reasonably modeled by a Zipf distribution with s close to 1.

In our strategy, the value of r is related to the file type. When user access some types of files, they tend to access files with high popularity. Among other file types, the popularity factor is less important.

4.2 Cache Value

To measure the cache value Ecv comprehensively, we need to consider multiple factors that influence it, not just popularity p. The file size u is a factor that cannot be ignored. In the actual scene, the SC's cache space is much smaller than the ground cache space. Therefore, if we only consider the popularity, it is very likely that there will be an extreme situation. That is, when the file with the greatest popularity is extremely large, the other files cannot be cached.

From the above description, we believe that popularity p and file size u are two factors that influence the cache value. At the same time, the file type t should also be a factor of cache value because the popularity p is related to file type t. Considering the cache space has already been allocated to each ICP reasonably, we believe that file type is determined in each allocated space.

The calculation of the cache value is done by the following steps. The first four steps are used for normalization of file-factor matrix. After that, weight can be calculated by using Analytic Hierarchy Process (AHP) method, and assigned to different factors. Finally, we can get the cache value [mathematical expression not reproducible] and Ecv. The different steps are:

1) Considering that ICP i only supplies files in type [t.sub.i], we can construct file (in type [t.sub.i] )-factor matrix [mathematical expression not reproducible]. The matrix [mathematical expression not reproducible] is constructed by taking [a.sub.i] files (total files the ICP i owes) and m factors corresponding to each file.

2) According to different attributes of factors, we scale the file (in type [t.sub.i] )-factor matrix [mathematical expression not reproducible] to matrix [mathematical expression not reproducible].

If [l.sub.xy] is the benefit parameters, then [mathematical expression not reproducible] If [mathematical expression not reproducible] is the cost parameters, then [mathematical expression not reproducible]

3 ) Column by column normalization: we normalize the matrix [mathematical expression not reproducible] by column to get the new matrix [mathematical expression not reproducible] The column by column normalization is done by the following formula:

[mathematical expression not reproducible] (17)

4) Complete normalization: a normalized file (in type [t.sub.i] )-factor matrix [mathematical expression not reproducible], [mathematical expression not reproducible] (where i = 1, 2, ..., N ; x = 1, 2, ..., [a.sub.i]; y = 1, 2, ..., m) is finally given by:

[mathematical expression not reproducible] (18)

It should be point out that each element of matrix [mathematical expression not reproducible] represents the file's assessment value under each factor.

5) Considering the above factors, the cache value of the file x in type [t.sub.i] can be defined as:

[mathematical expression not reproducible] (19)

Where [mathematical expression not reproducible] indicates the cache value of file x in type [t.sub.i] and [w.sub.y] is the weight assigned to each factor by using Analytic Hierarchy Process (AHP).

6) Under the premise that the SC's cache space has been allocated to each ICP reasonably, the cache value in each allocated area is:

[mathematical expression not reproducible] (20)

Each ICP only needs to store as many files with high cache value in each type area, and the purpose of optimizing the cache can be achieved. The specific algorithm is described as follows:
Algorithm 1 Cache Value Assessment algorithm

Input: the size of each file [mathematical expression not reproducible]
the popularity of each file [mathematical expression not reproducible]
Output: [mathematical expression not reproducible] (the cache value of
file f in type [t.sub.i])
Procedure:
    for i [member of] {1, 2, ..., N} do
        for x [member of] {1, 2, ..., [a.sub.i]}, y [member of] {1, 2,
        ..., m} do
              Construct file (in type [t.sub.i] )-factor matrix
              [mathematical expression not reproducible]; end for
    //Scale matrix according to attribute:
        if [mathematical expression not reproducible] is the benefit
        parameters,
        do [mathematical expression not reproducible]
        else [mathematical expression not reproducible] is the cost
        parameters,
        do [mathematical expression not reproducible] ;
        end if
// Column by column normalization:
       for x [member of] {1, 2, ..., [a.sub.i]}, y [member of] {1, 2,
       ..., m} do
              Construct matrix [mathematical expression not
              reproducible] based on (17);
       end for
// Complete normalization:
       for x [member of] {1, 2, ..., [a.sub.i]}, y [member of] {1, 2,
       ..., m} do
             Construct matrix [mathematical expression not
             reproducible] based on (18);
       end for
         Calculate cache value based on (20);
         return [mathematical expression not reproducible]
       end for
         return [mathematical expression not reproducible]


In this algorithm, we can know the cache value of each file and each allocated space. At the same time, our caching strategy is to put files with high cache value into the cache space. Under the premise that the cache space has been allocated to each ICP reasonably, our optimized caching strategy is to maximize the cache value in each allocated space. That is, store as many files with high cache value in each type area. In this way, the operator can optimize cache effects while balancing ICP benefits.

5. Simulations

5.1 Simulation Configuration

In our simulation, there is one SC and multiple ICPs. To measure ICP's satisfaction on distribution in various situations, we change the SC's cache size V and the number of ICPs N in the simulation. The SC's cache size V varies from 300MB to 1000MB and the number of ICPs (i.e., the number of file types) N varies from 2 to 8.

There are 200 files in each ICP's file library. To evaluate the determining the cache value, we assume the size and popularity of all files are different.

1) Considering file general size u is related to the file type t (for example, video is generally larger than audio and text), we assume that there are N file size intervals. For the same type files, their sizes are in the same interval; for the different type files, their sizes are in different intervals.

2) The popularity of files follows a Zipf distribution of parameter r = 0.7. We setup simulation environment using the MATLAB version 2017a on a computer with process 2.8GHz Intel Core i7, RAM of 8GB, and operating system Win 10.

5.2 Simulation results

To evaluate the method of cache space allocation based on bankruptcy game and optimized caching strategy, this paper carries out extensive simulation. It should be noted that the simulation results have a certain relationship with the simulation configuration.

1) Cache Allocation Method

Considering the benefits of ICPs, the SC's space should be allocated to ICPs reasonably. We evaluate the performance of the allocation methods by evaluating ICPs' satisfaction of multiple distribution methods. We compare our proposed allocation approach with the following methods:

* Baseline [11]: a baseline method that ignores ICPs' satisfaction. This model doesn't allocate cache space, just save high popularity files to SC's space.

* Fixed Ratio: an allocation method that allocate cache space according to a certain fixed ratio.

* Claimed Ratio: an allocation method that allocate according to the ratio of space claimed by ICPs to the total claimed space.

* Bankruptcy: the proposed model that allocate cache space to ICPs based on bankruptcy game.

We evaluate the performance of the allocation methods by varying SC's space size and the number of ICPs.

Based on the simulation results in Fig. 3, we can make the following observations:

(1) The baseline method has limited performance as it ignores ICPs' satisfaction. Compared to the baseline method, the Fix Ratio method and Claimed Ratio method improve ICP's satisfactions, as both methods consider the interests of ICPs and allocate the cache space.

(2) The Fix Ratio method and Claimed Ratio method do not allocate cache space fairly. We found that the proposed model that based on bankruptcy game is superior over other methods, achieving a significant improvement. This happens because the proposed model balances the interests of ICPs and allocate cache space reasonably.

(3) When the SC's space becomes larger, the satisfaction of ICPs increase in all methods.

Fig. 4 shows the effect on ICP's satisfaction, with changes the number of ICPs. When the number of ICP increases, the overall satisfaction of ICPs will decrease. If the resources are the same, the number of ICP to be allocated increases, the space that each ICP can allocate will naturally decrease corresponding. At the same time, we can still find that allocation method based on the bankruptcy game is relatively good, overall maintained a good level of satisfaction.

2) Optimized Caching Strategy

We further evaluate the optimized caching strategy of the allocation methods by testing the cache hit rate.

Based on the simulation results in Fig. 5, we can make the following observations:

(1) Compared to Fix Ratio method and Claimed Ratio method, the proposed model is not only superior over other methods, but also when the space size is more than 500M, the file cache hit rate is close to 90%.

(2) With the rise of SC's size, all allocation methods have increased the hit rate of the file cache.

(3) We also noticed a very interesting phenomenon. When the space is very small, cache hit ratio of Claimed Ratio method is lower than the cache hit rate of Fixed Ratio method. With the increase of SC's size, cache hit rate of Claimed Ratio method can gradually exceed the cache hit rate by Fix Ratio method. This happens because each ICP's acquired space is smaller than their claimed space. It may appear that the space is allocated but cannot be stored in the file. With the increase of SC space, the phenomenon of being unable to store into the file has been alleviated, and the cache hit ratio of proportional allocation has also rapidly increased.

To verify the superiority of AHP in measuring the files' cache value, we compared it with the method of only using popularity to measure files.

In Fig. 6, the distribution method to allocate the cache space is both the resource allocation method of the bankruptcy game, except that the way the operator measures the cache value is different. Based on the simulation results in Fig. 6, we can obtain the conclusions as follows:

(1). When we using AHP to comprehensively consider the popularity and size of the file and other factors, it can keep the cache hit at a relatively high level.

(2). If operator only considers the popularity of files, the hit rate is not high. Especially when the SC's space is relatively small, cache hit rate will be particularly low. This phenomenon may cause by extreme case. That is, highly popular documents are particularly large, providers can only store very few files in the space they allocated.

(3). With the increasing of SC space size, the cache hit rate of the method that only consider the popularity risen sharply. This means that extreme situation is mitigated with the increasing of SC space size.

6. Conclusion

In this article, focusing on the wireless resource allocation of different ICPs in small cells, we propose a optimize caching resource allocation based on bankruptcy games. The advantage of the bankruptcy game-based resource allocation method in terms of cache hit rate indicates that cooperative sharing improves resource utilization. Based on the distribution results, we consider rich cache value measurement. That is, not only consider the popularity of the file, but also consider size and type. By using AHP to determine the weights of features, we optimize the caching strategy. The simulation results show that the satisfaction of each provider is maintained at a good level, which ensures the fairness of distribution. The hit rate of wireless users' access has also improved.

In summary, the main contribution of this paper is as follows: the efficiency of cache space utilization can be improved through cooperative sharing. Moreover, the cache value estimation is considered more comprehensive so that improve the cache hit rate. All these ensure the fair distribution for providers and improve the wireless users' experience.

References

[1] J. An, K. Yang, J. Wu, N. Ye, S. Guo, and Z. Liao, "Achieve sustainable ultra-dense heterogeneous networks for 5G," IEEE Communications Magazine, vol. 55, no. 12, pp.84-90, 2017. Article (CrossRef Link).

[2] Z. Li, J. Lin, M.-I. Akodjenou, G. Xie, M. A. Kaafar, Y. Jin, and G. Peng, "Watching videos from everywhere: A study of the pptv mobile vod system," in Proc. of ACM IMC, pp. 185-198, 2012. Article (CrossRef Link).

[3] Ericsson, "Ericsson Mobility Report," June 2018.

[4] X. Ge, S. Tu, G. Mao, C. Wang, and T. Han, "5G Ultra-Dense Cellular Networks," IEEE Wireless Communications, vol. 23, no.1, pp. 72-79, 2016. Article (CrossRef Link).

[5] X. Zhang, T. Lv, and S. Yang, "Near-Optimal Layer Placement for Scalable Videos in Cache-Enabled Small-Cell Networks." IEEE Transactions on Vehicular Technology, vol. 67, no. 9, pp. 9047-9051, 2018. Article (CrossRef Link).

[6] M. Hu, J. Luo, Y Wang, and B.Veeravalli, "Practical Resource Provisioning and Caching with Dynamic Resilience for Cloud-Based Content Distribution Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 8, pp. 2169-2179, 2014. Article (CrossRef Link).

[7] M. Leconte, G. Paschos, L. Gkatzikis, M. Draief, S. Vassilaras, and S. Chouvardas, "Placing dynamic content in caches with small population," in Proc. of IEEE Infocom, pp. 1-9, 2016. Article (CrossRef Link).

[8] A. Finamore, M. Mellia, Z. Gilani, K. Papagiannaki, V. Erramilli, and G. Yan, "Is there a case for mobile phone content pre-staging?" in Proc. of conference on emerging network experiment and technology, pp. 321-326, 2013. Article (CrossRef Link).

[9] E. Zeydan, E. Bastug, M. Bennis, M. A. Kader, A. Karatepe, A. S. Er, and M. Debbah, "Big data caching for networking: moving from cloud to edge," IEEE Communications Magazine, vol. 54, no. 9, pp. 36-42, 2016. Article (CrossRef Link).

[10] L. Marini, Loris, L. Jun, and Y. Li, "Distributed caching based on decentralized learning automata," in Proc. of international conference on communications, pp. 3807-3812, 2015. Article (CrossRef Link).

[11] J. Zhang, X. Lin, and X. Wang, "Coded caching under arbitrary popularity distributions," in Proc. of information theory and applications, pp. 98-107, 2017. Article (CrossRef Link).

[12] M. K. Kiskani, S. Vakilinia, and C. Mohamed, "Popularity based file categorization and coded caching in 5G networks," in Proc. of personal, indoor and mobile radio communications, pp. 1-5, 2017. Article (CrossRef Link).

[13] X. Peng, J. Zhang, S.H. Song, and K.B. Letaief, "Cache size allocation in backhaul limited wireless networks," in Proc. of international conference on communications, pp. 1-6, 2016. Article (CrossRef Link).

[14] N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and G. Caire, "Femtocaching: Wireless video content delivery through distributed caching helpers," in Proc. of IEEE INFOCOM, pp.1107-1115, 2012. Article (CrossRef Link).

[15] K. Poularakis, G. Iosifidis, and L. Tassiulas, "Approximation algorithms for mobile data caching in small cell networks," IEEE Transactions on Communications, vol. 62, no. 10, pp. 3665-3677, 2014. Article (CrossRef Link).

[16] M. A. Maddah-Ali and U. Niesen, "Fundamental limits of caching," IEEE Trans. on Information Theory, vol. 60, no.5, pp. 2856-2867, May 2014. Article (CrossRef Link).

[17] H. Dahrouj, A. Douik, O. Dhifallah, T. Y. Al-Naffouri, and M.-S. Alouini, "Resource allocation in heterogeneous cloud radio access networks: advances and challenges," IEEE Wireless Communications, vol. 22, no. 3, pp. 66-73, June 2015. Article (CrossRef Link).

[18] C. Zhan, and K. Gao, "Video Delivery in Heterogeneous Wireless Networks with Network Coding," IEEE Wireless Communications Letters, vol 5, no. 5, pp. 472-475, 2016. Article (CrossRef Link).

[19] Dennis A. Kopf, Ivonne M. Torres, and Andrew P. Ciganek, "Advertising and Internet Content Providers: Creating a Market for Information," Journal of Internet Commerce, vol 11, no.2, pp. 81-99, 2012. Article (CrossRef Link).

[20] R. Trestian, O. Ormond, G. M. Muntean. "Game Theory-Based Network Selection: Solutions and Challenges," IEEE Communications Surveys & Tutorials, vol. 14, no. 4, pp. 1212-1231, 2012. Article (CrossRef Link).

[21] S. Hoteit, S. Secci, R. Langar, G. Pujolle, and R. Boutaba, "A bankruptcy game approach for resource allocation in cooperative femtocell networks," in Proc. of global communications conference, pp. 1800-1805, 2012. Article (CrossRef Link).

[22] Meenakshi, and N. P. Singh, "A comparative study of cooperative and non-cooperative game theory in network selection," in Proc. of international conference on computational techniques in information and communication technologies, pp. 612-617, 2016. Article (CrossRef Link).

[23] F Drew, T Jean, "Game Theory," Decision Analysis Location Models & Scheduling Problems, pp. 111-150, 2004. Article (CrossRef Link).

[24] R. Branzei, D. Dimitrov, and S. Tijs, "Models in Cooperative Game Theory," Lecture Notes in Economics & Mathematical Systems, vol 19, no. 2, pp. 139-152, 2005. Article (CrossRef Link).

[25] R. J. Auman, M. Maschler, "Game theoretic analysis of a bankruptcy from the Talmud. J Econ Theory," Journal of Economic Theory, vol 36, no. 2, pp. 195-213, 1985. Article (CrossRef Link).

[26] M. Leng, and M. Parlar, "Allocation of Cost Savings in a Three-Level Supply Chain with Demand Information Sharing: A Cooperative-Game Approach," Operations Research, vol 57, no. 1, pp. ii-260, 2009. Article (CrossRef Link).

[27] R. B. Myerson, "Graphs and Cooperation in Games," Mathematics of Operations Research, vol. 2, no. 3, pp. 209-296, 1977. Article (CrossRef Link).

[28] E. Winter, "Chapter 53 The shapley value," Handbook of Game Theory with Economic Applications, vol. 3, pp. 2025- 2054, 2002. Article (CrossRef Link).

[29] S. C. Littlechild, and G. Owen, "A simple expression for the shapley value in a special case," Management Science, vol. 20, no. 3, pp. 261-422, 1973. Article (CrossRef Link).

[30] M. A.Pulido, J. Sanchez-Soriano, and N. Llorca, "Game Theory Techniques for University Management: An Extended Bankruptcy Model," Annals of Operations Research, vol. 109, no. 1-4, pp. 129-142, 2002. Article (CrossRef Link).

[31] M. Rabin, "Incorporating Fairness into Game Theory and Economics," The American Economic Review, vol. 83, no. 5, pp. 1281-1302, 1993.

[32] J. Jiang, S. Vyas, and H Zhang, "Improving Fairness, Efficiency, and Stability in HTTP-Based Adaptive Video Streaming with Festive," IEEE ACM Transactions on Networking, vol. 22, no.1, pp. 326-340, 2014.Article (CrossRef Link).

[33] K. Ibrahimi, Y. Serbouti, "Prediction of the content popularity in the 5G network: Auto-regressive, moving-average and exponential smoothing approaches," in Proc. of international conference on wireless networks, pp. 1-7, 2017. Article (CrossRef Link).

[34] J. Zhang, X. Lin, and X. Wang, "Coded caching under arbitrary popularity distributions," in Proc. of information theory and applications, pp. 98-107, 2015. Article (CrossRef Link).

[35] Q Li, W Shi, X Ge, and Z Niu, "Cooperative Edge Caching in Software-Defined Hyper-Cellular Networks," IEEE Journal on Selected Areas in Communications, vol. 35, no. 11, pp. 2596-2605, 2017. Article (CrossRef Link).

[36] B. Yang, G. Mao, M. Ding, X. Ge, and X. Tao, "Dense small cell networks: from noise-limited to dense interference-limited," IEEE Transactions on Vehicular Technology, vol. 67, no. 5, pp. 4262-4277, 2018. Article (CrossRef Link).

[37] X. Ge, J. Ye, Y. Yang, and Q. Li, "User mobility evaluation for 5g small cell networks based on individual mobility model," IEEE Journal on Selected Areas in Communications, vol. 34, no. 3, pp. 528-541, 2016. Article (CrossRef Link).

Liying Zhang received her B.E. degree in Electrical and Information Engineering from Beihang University, Beijing, Beijing, P. R. China. She is currently pursuing a master degree at Beihang University, Beijing, Beijing, P. R. China. Her current research interests include information network economics, with a particular focus on game theory, resource allocation optimization and recommender system.

Gang Wang is currently an associate professor at Beihang University, Beijing, Beijing, P. R. China. He received his B.E. degree from Qufu Normal University, Qufu, Shandong, P. R. China, and a PhD degree from Beihang University, Beijing, Beijing, P.R. China. His current research interests include wireless networks, with a particular focus on network coding, information dissemination, and resource allocation.

Fuxiang Wang is currently a lecturer at Beihang University, Beijing, P. R. China. He received his PhD degree from Beihang University. His current research interests include Blind signal processing and application of air traffic flow management.

Liying Zhang (1), Gang Wang (1) and Fuxiang Wang (1*)

(1) School of Electrical and Information Engineering, Beihang University Beijing, BJ 100191--P. R. China

[e-mail: 13021109@buaa.edu.cn]

(*) Corresponding author: Fuxiang Wang

Received September 12, 2018; revised November 5, 2018; accepted November 22, 2018; published May 31, 2019

http://doi.org/10.3837/tiis.2019.05.005
Table 1. Notations and descriptions of the bankruptcy game and the
proposed cache space allocation

Notation       Bankruptcy Game                   Cache space allocation

N              Set of players                    Set of ICPs
V              Total money the company owes      SC's cache space size
Y              Total money the player demands    Total required cache
                                                 size by all ICPs
N              Total number of players           Total number of ICPs
i,j            Serial number, represent a        Serial number,
               specific player                   indicating a specific
                                                 player
[b.sub.i]      Claimed money of player i         Demand cache space of
M              /                                 ICP i Total number of
                                                 files in the repository
[a.sub.i]      /                                 Number of files the
                                                 ICP i owes
S,K            Coalition formed by players       Coalition formed by
                                                 ICPs
v,w            Characteristic
               function(gain function)  /
v(S)           Characteristic function
               of coalition S  /
[[phi].sub.i]  Solution of money distributed to  Cache size allocated to
(v)            player i                          ICP i
H              The solution vector               The cache space
                                                 allocation solution
                                                 vector

Table 2. notations and definitions of optimized caching strategy

Notation                                    Definition

r                                           A parameter of the Zipf
                                            distribution
[a.sub.i]                                   Number of files the ICP i
                                            owes
[t.sub.i]                                   Type of files provided by
                                            ICP i
[mathematical expression not reproducible]  Popularity of the file x in
                                            type [t.sub.i]
[mathematical expression not reproducible]  Size of the file x in type
                                            [t.sub.i]
m                                           Number of factors
[w.sub.y]                                   Weight assigned to factor y
[mathematical expression not reproducible]  file (in type
                                            [t.sub.i])-factor matrix
[mathematical expression not reproducible]  a normalized file (in type
                                            [t.sub.i] )-factor matrix
[mathematical expression not reproducible]  Cache value of the file
                                            x in type [t.sub.i]
Ecv                                         Cache value
COPYRIGHT 2019 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2019 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Zhang, Liying; Wang, Gang; Wang, Fuxiang
Publication:KSII Transactions on Internet and Information Systems
Geographic Code:9CHIN
Date:May 1, 2019
Words:7550
Previous Article:Distributed Target Localization with Inaccurate Collaborative Sensors in Multipath Environments.
Next Article:ST Reliability and Connectivity of VANETs for Different Mobility Environments.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |