# Hypergraph Game Theoretic Solutions for Load Aware Dynamic Access of Ultra-dense Small Cell Networks.

1. IntroductionThe ultra-dense small cell (SCN) has been regareded as a promising technology in the next generation communication [1], [2], to meet with the huge increase of traffic demand. They significantly mitigate the interference of different communication channels, and improve the global throughput. In the related works of hyperdense SCN, the common interfernce model is the bianry graph model [3]-[6]. However, due to a large number of users, equioments, and cells in the hyperdense SCNs, the interferencec relationship between users are much more complicated, such as the cumulative and directional interference. While, the traditional bianry model cannot capture these complicated relationship and some new model needs to be investigated.

Recently, the hypergraph interference model, which shows a good modeling ability for the interfernece of dense deployment scenes, has attracted more and more researchers' attention. It has been used in many fields, such as, device-to-device (D2D) underlay communications [7], the cross-cell D2D communications [8], and interference coordination [9]. In these works, they all employed a centralized manner. Although a distributed manner is proposed in [10], the implement method of communication among hyperedges is still unsolved. Therefore in this paper, a cloud-based centralized-distributed algortihm framework is used to realize the communication in a cloud-based center and make the strategy of each small cell in a distributed way.

Moreover, the heterogeneous demand issue of users is also an improtant factor in resource allocation, and some studies paid not so much attention. They usually employed the one channel transmisstion model and this assumption seems to be impractical in the ultra-dense networks with heterogeneous demand. This motivates us to investigate the multi-channel access problem to meet users' heterogeneous traffic loads.

To the best of authors' knowledge, most of the works, regardless of the graph based or the hypergraph based, generate the graph or the hypergraph interference model based on the MAC layer interference [3]-[10], [25]. To simplify the arithmetic and to reduce communications, they reduce the MAC layer interference by reducing the number of the conflicting edges or hyperedges to improve the physical layer throughput. In our work, the traditional optimization method to reduce the MAC layer interference is implemented as the first solution. Moreover, another optimization method that jointly considers the MAC layer and the physical layer interference is proposed to minimize the physical interference with the weight.

The proposed two optimization problems are formulated in the centralized-distributed manner utilizing the local altruistic games [11], which is proved to be exact potential games,where exists at least one pure Nash equilibrium (NE). To approach the NE points, a cloud-based learning algorithm is utilized for the two game models.

To summarize, our main contributions are as follows:

1. In order to overcome that the neighbors in a hyperedge cannot exchange information directly in a distributed manner, and to reduce the huge strategic space in the centralized manner to reduce the computation and the complexity, we utilize a cloud-based centralized-distributed manner.

2. According to different scenarios, we respectively formulate the multi-channel access problem as the unweighted hypergraph-based game, which needs less information exchange and can converge faster, to optimize the MAC layer interference, and as the vertex-weighted hypergraph-based game, which can achieve a better performance, to optimize the physical layer interference.

3. The proposed games are both proved to be exact potential games, where exists at least one pure Nash Equilibrium (NE). Compared with other algorithms, the enhanced best response algorithm, initially reported in [12], which is noted as spatial best response dynamic (SBRD) algorithm, is proved to be the most suitable algorithm for the centralized-distributed hypergraph model with the high convergence speed and the ideal final value.

Note that this paper is an extention of our previous conference paper [24]. The main differences are as follows: 1) Besides the unweighted hypergraph-based game in the conference paper [24], a vertex-weighted hypergraph-based game is proposed in this paper. The vertex-weighted game can obtain a better performance than the unweighted one, with slightly lower convergence speed. 2) A hypergraph construction algorithm is presented to model the hyper interference relationship of users. 3) More simulation results are discussed. The two proposed game models are compared from the convergence performance and network throughput aspects.

The rest of this paper is organized as follows. In Section II, the system model is presented and the problem is formulated. In Section III, the cumulative interference model using hypergraph is introduced. In Section IV, the unweighted and weighted hypergraph-based game models are formulated, and the SBRD algorithm is proposed to achieve the NE points. Simulation results and analysis are presented in Section V. Finally, Section VI concludes the paper.

2. System Model and Problem Formulation

In this paper, we consider a SCN with N small cell access points (SAPs). We denote SAP set as N = {1,2,...N} and the channel set as M = {[c.sub.1],[c.sub.2],...,[c.sub.M]}. Each channel has the same bandwidth. We assume that the heterogeneous traddic load of cells are related with their serving user numebrs. To meet these demands, SAP n simultaneously accesses to 1 [less than or equal to] [k.sub.n] [less than or equal to] 3 channels. The SAP n's channel selection is denoted as [K.sub.n], i.e., [mathematical expression not reproducible]. For the optimal selction number, it has been studied in [13]-[15]. Hence, we concentrate our attention on the channel selection problem.

Based on the Shannon capaticy, we have C = B*[log.sub.2](1+ [gamma]), where C and B represent the capacity and the bandwidth of the channel respectively. The signal to interference-plus-noise power ratio (SINR) is [gamma]. Based on the channel threshold [theta], we represent the network throughput T as:

[mathematical expression not reproducible] (1)

where T(n,[c.sub.j]) is the throughput of channel [c.sub.j] selected by small cell n.

Following the same interpretation in [16], we define T(n,[c.sub.j]) as:

[mathematical expression not reproducible] (2)

where [mathematical expression not reproducible] is the SINR of the channel [c.sub.j] selected by n, B represents the bandwidth of each channel, [theta] and [theta]' are the specified threshold, and [T.sub.max] denotes the maximum throughput of each channel.

However, optimizing the throughput directly is computationally complex. In our former work [17], we can find that, approximately, the smaller interference level leads to the larger network throughput.

3. Cumulative Interference Modeling by Hypergraph

3.1 Cloud Based Centralized-Distributed Model

In traditional binary graph based interference models, edges represent the pairwise strong interference relations. Therefore, small cell access points (SAPs) can easily discover and directly communicate with their neighbors. However, in a hypergraph, a hyperedge with more than two vertexes describes cumulative interference effect caused by multiple weak interfering sources. Therefore, direct communication among neighbors in a hyperedge is unprocurable. Most of the existing works researching hyperedges [7]-[9], are formulated in a centralized manner. Users are always densely distributed in ultra-dense small cell networks. Centralized algorithms are always with a huge strategic space and a large amount of computing. However, the scanty work which using a distributed manner [10], did not detailedly clarify the implement method of communication among hyperedges.

A centralized-distributed optimization architecture [18] for small cell networks is shown in Fig. 1. The decesion making process of the small cell networks is decided in the virtual cloud by the agent nodes. Under this mechanism, the inforamton such as location, traffic are reported to the cloud, and then the correonding algorthm are processing to ontain the decision. Finally, the cloud sends the decision results of channel selection to the small cells.

3.2 Hypergraph Construction

We utilize the hypergraph to accurately model the interference relationship between the SAPs. In a hypergraph, when the vertexes transmit at the same channel, any subset of the given set of vertexes constitutes a hyperedge, while one of the vertexes is interfered by the rest in it [15]. Therefore, a hyperedge includes at least two vertexes. Hence, we give the definition of the hypergraph.

Definition 1 [19]: A hypergraph [GAMMA] is denoted as [GAMMA] = (V,E = [([e.sub.i]).sub.i[member of][LAMBDA]]), where [LAMBDA] is a finite set of indexes, V = {[v.sub.1],[v.sub.2],...,[v.sub.N]} is a finite set of vertexes representing different small cells in the network. The hypergraph [GAMMA] on V is a family E = {[e.sub.1],[e.sub.2],...,[e.sub.|E|]} of subsets of V.

Each hypergraph is constructed based on a specified network topology. Each small cell in the network is seen as a vertex. The vertex m constitutes a binary edge with vertex n if [mathematical expression not reproducible] In the former equation, [P.sub.n] and [P.sub.m] are te transmission powers of the vertexes n and m, respectively, [N.sub.0] represents the power of noise, [h.sub.nn] characterizes the channel gain from the vertex n to its MUs, and [h.sub.mn] represents the channel gain from vertex m to vertex n [12], [theta] is the same threshold in eq.(2). [h.sub.mn] =[d.sub.mn.sup.-[alpha]] where [d.sub.mn] is the distance between m and n in meter and [alpha] is the path loss in Np/meter.

Considering the cumulative interference relationship, the hyperedges containing more than two vertexes may be considered. Here, we denote the largest number of vertexes as Q. It has been investigated that for the Q[greater than or equal to]3 situations, the benefits improved is very limitted but complexity is much more serious [7]. The total interference over a given threshold, between vertex n and vertexes [m.sub.1],...,[m.sub.Q,-1], for a positive integer Q' satisfying 2[less than or equal to]Q'[less than or equal to]Q, eq. (3) reads:

[mathematical expression not reproducible] (3)

The corresponding hyperedge constructing procedure is shown in Algorithm 1, where [C.sub.N.sup.a] represents the number of combinations of a vertexes from N.

Algorithm 1: hypergraph construction algorithm Step 1: Initialization: set the appropriate value of Q and the threshold [theta]. Step 2: For Q' = 2:Q (1) Traverse all the [C.sub.N.sup.Q] combinations of Q' vertexes, find the combinations satisfying eq. (3) and construct hyperedges on them. (2) Considering the hyperedges constructed in this step, if any subset of vertexes in a hyperedge could construct another hyperedge with fewer vertexes, the former hyperedge should be abandoned. End

Remark 1: The process of withdrawing hyperedges in Algorithm 1 is reasonable. For vertexes satisfying eq. (1), any other vertex [m.sub.Q'] added to them can also satisfy eq. (1). The hypergraph will be too complicated if we keep all the hyperedges when Q' gets larger or the network gets denser. The withdrawn hyperedges are redundant when we make the channel allocation. For a withdrawn hyperedge [e.sub.n], regardless of the number of its sub-hyperedges, once the channels are reasonably allocated in sub-hyperedges, we ensure that not all of the vertexes in [e.sub.n] transmit in the same channel, so there will be no interference over the pre-defined threshold in [e.sub.n].

Fig. 2 depicts the construction procedure of the hypergraph on a random topology. First, the edges with two vertexes are constructed, which are marked with red dot dash line. Then, the hyperedges with three vertexes are constructed which are shown with green circles. However, in the hypergraph, no hyperedges contains edges or hyperedges with fewer vertexes.

3.3 Hypergraph-based Spectrum Access Problem

Fig. 3 illustrates the hypergraph-based interference model composed of eleven vertexes and eight hyperedges. In this model, we consider the binary edges as interfering pairs (1,2), (1,3), (2,3) and (1,8), as well as the three-vertex hyperedges as (3,4,5), (2,6,7), (6,9,10) and (3,10,11), while in the traditional graph-based interference model, only binary edges are considered. The incidence matrix is shown beside the interference model, where each line represents a vertex and each column characterizes a hyperedge [20]. If vertex [v.sub.i] is incident to the hyperedge [e.sub.j], then the (i,j)-entry in the matrix is one, otherwise it is zero. In Fig. 3, each vertex selects one, two or three channels according its traffic load. Different colors in each vertex represent the selected channel set of each small cell. For instance, vertex 1 and 8 select one and three channels, respectively. If one of the color is selected simultaneously by all the vertexes in one hyperedge, it means that the corresponding channel is conflicting in that hyperedge.

4. Hypergraph Based Game Solution

With the application of the centralized-distributed model, SAPs exchange information in the centralized manner. However, if we make the spectrum access in the centralized manner, the strategy space is proportional to ([C.sub.M.sup.k])N. The strategy space is too large to make the optimization especially when M and N are large. With the exchanged information, we resort to the game theory to solve the spectrum access problem in the distributed manner.

Definition 2 (Nash equilibrium [21]): An channel selection profile in the small cell networks [mathematical expression not reproducible] is defined as a pure NE, if and only if no player can improve its utility by deviating unilaterally, i.e.,

[mathematical expression not reproducible]. (4)

Definition 3 (Exact potential game [21]): For a given player n, the two different actions selected by n are noted as [K.sub.n] and [vbar.[K.sub.n]]. A game is an exact potential game (EPG) if an exact potential function exists, i.e., [PHI]:[K.sub.1]x[K.sub.2]x...x[K.sub.N] [right arrow]R and then the following equation holds:

[mathematical expression not reproducible] (5)

In other wods, when one play changes its action, the corresponding change in the utility function is same with the potential function. The EPG guarantees that there exists at least one pure NE points [22].

4.1 Unweighted Hypergraph-based Game

Inspired by the mainstream of optimization by reducing MAC layer interference, in this section, we propose the unweighted hypergraph-based game aiming at reducing the number of interfered hyperedges to optimize the network throughput. Motivated by [10], we consider the concept of potentially maximum protocol interference (PMPI) to model the interference level as follows:

Definition 4 (Potentially maximum protocol interference (PMPI) [10]): We define PMPI In(I[C.sub.n]) of small cell n as the total protocol interference of all user n' channels:

[mathematical expression not reproducible], (6)

where E(n) = {[e.sup.1.sub.n],[e.sub.n.sup.2],...,[e.sub.n.sup.Jn]} denotes the set of hyperedges that contain vertex n; S([e.sub.n.sup.i],cj) is the indicator function as:

[mathematical expression not reproducible] (7)

We define the network PMPI as:

[mathematical expression not reproducible]. (8)

All SAPs' channel selection profile is [mathematical expression not reproducible]. Commonly, a lower interfernce would lead to a higher throughput. Therefore, the optimization problem can be formulated as:

[mathematical expression not reproducible]. (9)

Then we construct the potential function as follows:

[mathematical expression not reproducible] (10)

Formally, the channel resource allocaction game bansed on hypergraph is modeled as

G1 = [N,[{[K.sub.n]}.sub.n[member of]N],[{[[U.sub.n]}.sub.n[member of]N]], (11)

where N denotes the set of SAPs, [K.sub.n] is the small cell n's available action set, and [U.sub.n] is the set of corresponding utility function.

Local altruistic game proposed in [11] is a significant innovation in which one can make the global optimization through local optimization. In the local altruistic game, each small cell is a player in the game, the channel selections of each small cell are the actions of each player. The opposite number of the summery of both the neighbors' and its own received interference is the small cell's utility function. Each small cell optimizes its utility, and can get the maximum of the predefined global potential function. Based on the hypergraph model, hyperedges represent the interference relations among vertexes. Therefore, vertexes in hyperedges containing n can be noted as the neighbors of n.

Motivated by [11], we define the player n's utility function in a locally altruistic form as:

[mathematical expression not reproducible] (12)

where [N.sub.n] = [N.sub.n.sup.d] [union] [N.sub.n.sup.p] represents n's neighboring set, and it contains the direct interfering neighboring set [N.sub.n.sup.d] and the potential interfering neighboring set which consists of neighbors in hyperedges that contain small cell n denoted as [N.sub.n.sup.p].

The objectives of the game can be noted as:

[mathematical expression not reproducible]. (13)

The following theorem indicates the properties of the proposed spectrum access game.

Theorem 1: The proposed game G1 has at least one pure NE, and the optimization solution of OP 1 constitutes a pure strategy NE of G1.

Proof: The following proof is inspired by the proof lines of [10].

We order an arbitrary player n unilaterally changes its action from [K.sub.n] ={[c.sup.n.sub.1],[c.sup.n.sub.2],...[c.sup.n.sub.kn]} to [K.sub.n] = {[c.sub.1.sup.n*], [c.sub.2.sup.n*],...[c.sup.n.sub.kn.sup.*]}, the corresponding change of utility function is [U.sub.n]([K.sub.n.sup.*], [K.sub.-n])-[U.sub.n]([K.sub.n],[K.sub.-n]).

Whereafter, we can classify the channels in the two actions into following three sets : 1. [C.sub.0]= [K.sub.n] [intersection] [K.sub.n]*, which means the set of channels that remain unchanged when the action changes.

2. [C.sub.1] = [K.sub.n] \ ([K.sub.n] [intersection] [[K.sub.n].sup.*]), which represents the channels chosen by the former action [K.sub.n], but not contained within the latter action [K.sub.n]*.

3. [C.sub.2] = [K.sub.n.sup.*] \ ([K.sub.n] [intersection] [K.sub.n]*), which represents the channels chosen by the latter action [K.sub.n.sup.*], but not contained within the former action [K.sub.n].

Obviously, we can note that [K.sub.n] = [C.sub.0] [union] [C.sub.1], [K.sub.n]* = [C.sub.0] [intersection] [C.sub.2]. The number of channels in two actions are both [k.sub.n], so [C.sub.1] = [C.sub.2] = [k.sub.n] - |[C.sub.0]|. For presentation, we can make the one-to-one mapping, i.e., match each channel [c.sub.m] in [C.sub.1] uniquely with one channel [c.sub.n]* in [C.sub.2] one to one.

Afterwards, the E(n) can be divided into three subsets:

1. [E.sub.0](n,[c.sub.m]), which means when the channel changes from [c.sub.m] to [c.sub.m.sup.*], hyperedges in the subset satisfy: [delta]([e.sub.n.sup.i] [c.sub.m]) = [delta]([e.sup.i.sub.n], [c.sub.m.sup.*]).

2. [E.sub.1] (n, [c.sub.m]), which represents the subset in which the hyperedges satisfy: S([e.sub.i],[c.sub.m]) = 1 and [delta]([e.sup.i.sub.n], [c*.sub.m]) = 0.

3. [E.sub.2](n,[c.sub.m]), which represents the subset in which the hyperedges satisfy: [delta]([e.sub.n.sup.i], [c.sub.m]) = 0 and [delta]([e.sub.n.sup.i], [c*.sub.m]) = 1.

We have

[mathematical expression not reproducible], (14)

where E(n, a) represents the set of hyperedges that both contain n and a. Then we can calculate the change of utility function:

[mathematical expression not reproducible] (15)

We have

[mathematical expression not reproducible], (16)

since the actions of all the a [member of] [N.sub.n] didn't change, we have:

where [E.sub.i](n,a,[c.sub.m]) denotes the set of hyperedges that contain both n and a in [E.sub.i](a,[c.sub.m]), i = 0,1,2. Therefore, we get:

[mathematical expression not reproducible]. (18)

Meanwhile, the corresponding change of the potential function can be transformed as following:

[mathematical expression not reproducible], (19)

in which |[e.sup.k.sub.n]| represents the number of players that in the hyperedge [e.sup.k.sub.n]. We can find that:

[mathematical expression not reproducible], (20)

so we get :

[mathematical expression not reproducible] (21)

We can get:

[PHI]([K.sub.n.sup.*], [K.sub.-n])-[PHI]([K.sub.n], [K.sub.-n]) = [U.sub.n]([K.sub.n.sup.*], [K.sub.-n])-[U.sub.n]([K.sub.n], [K.sub.-n]). (22)

Therefore, the proposed dynamic channel access game G1 is an EPG which admits at least one pure strategy NE. The channel selection profile minimizing the I([K.sub.1],[K.sub.2],...,[K.sub.N]) is the globally optimal solution and it is also a pure strategy NE in G1. That completes the proof.

4.2 Vertex-weighted Hypergraph-based Game

The MAC layer interference elimination can improve the network throughput to some extent. However, the network throughput is directly affected by the physical layer interference. Therefore, the physical layer interference elimination is a more efficient method to improve the network throughput. In this subsection we propose a vertex-weighted hypergraph-based game to eliminate the physical layer interference.

In order to realize the communication among SAPs in a hyperedge, we utilize the cloud model. The location information was firstly uploaded to the cloud to determine the hypergraph model. Therefore, each SAP can recognize its neighbors in the hyperedges and can furtherly calculate the distance to each neighbor. Therefore, the interference generated by each neighbor can be estimated by the distance information and the channel model. As mentioned above, we can estimate the interference from m to n as:

[P.sub.mn] =[P.sub.m][h.sub.mn] =[P.sub.m][d.sub.mn.sup.-[alpha]]. (23)

With the estimation of interference, the significance of each neighbor is distinguished. The weight of a vertex is different when it is considered by its different neighbors. The weight of m to its neighbor n is [[lambda].sub.mn], we can set [[lambda].sub.mn] =[P.sub.mn]. In the topology in Fig. 4, we illustrate the distances of 2's neighbors to the vertex 2. Afterwards, the neighbors' weights to the vertex 2 can be solved out.

With the definition of each neighbor's weight, we can modify the local altruistic game in 3.2 by describing interference with a more accurate indicator. To this end, we present the concept of potentially neighborly physical interference (PNPI) to model the interference caused by neighbors in hyperedges as follows:

Definition 5: We define the potentially neighborly physical interference (PNPI) [J.sub.n]([K.sub.n]) of small cell n as the total neighborly physical interference of all channels selected by n :

[mathematical expression not reproducible] (24)

where [epsilon](m,[c.sub.j]) is the indicator function as:

[mathematical expression not reproducible] (25)

We define the network PNPI as:

[mathematical expression not reproducible]. (26)

Note that the PNPI has the similar form with the PMPI. However, the PNPI depicts a specific physical interference value. The small cell with a large PNPI means that it suffers serious interference from its neighbors, so the small cell is significant since it contributes a large amount of interference to the global interference. Therefore, the weight of each vertex can be measured by its corresponding PNPI. We can also optimize the network throughput by minimizing the PNPI. Therefore, the optimization problem is:

[mathematical expression not reproducible]. (27)

Similar to section 3.1, the potential functionis formulated as follows:

[mathematical expression not reproducible]. (28)

Similarly, the game is modeled as:

G2 = [N,[{[K.sub.n]}.sub.n[member of]N],[{[U.sub.n]}.sub.n[member of]N]], (29)

Based on the hypergraph model, we can find the neighbor set of each small cell. The weight of each neighbor is determined by the neighbor's estimated physical interference to the small cell. In the same locally altruistic form, the player n's utility function is as:

[mathematical expression not reproducible] (30)

Theorem 2: The proposed dynamic channel access game G2 is an EPG, which has at least one pure strategy NE, and the optimization solution of OP2 constitutes a pure strategy NE of G2.

Proof: The proof is similar to that in section 3.1, so we omit it for brevity. Note that the classification of hyperedges according to [delta](*) in section 3.1 should be changed to the classification of neighbors according to [epsilon](*).

4.3 Comparation and Discussion

In order to distinguish the two game solutions, we list the different advantages of them. The unweighted hypergraph-based game needs less information interaction and can converge with fewer iterations. The faster convergence will be validated by the simulation in the next section. Therefore, the unweighted hypergraph-based game is more suitable for networks which has a strict requirement of the convergence speed. On the other hand, the vertex-weighted hypergraph game solution can further improve the network throughput compared with the unweighted hypergraph game solution. Therefore, the vertex-weighted hypergraph-based game solution is more suitable for the network with a high network throughput requirement.

4.4 Spatial Best Response Dynamic Learning Algorithm

In this section, we modified a learning algorithm to approach the Ne points [11].

Following the SBRD learning algorithm [12], the learning algorithm permits multiple nodes to update their actions at each iteration. Note that any two of the selected nodes don't exist in the same hyperedge. In other words, the chosen nodes are non-adjacent vertexes in the hypergraph.

Algorithm 2: SBRD learning algorithm Step 1: Initialization: each vertex n [member of]N randomly choose an action [K.sub.n] (0) [member of] [K.sub.n]. Step 2: Loop for i = 1,2,...,[k.sub.max], all the vertexes exchange information with their neighbors in the cloud, and select vertexes of no relations to update the action. Step 3: Each selected vertex n calculates the utility corresponding to each available action, and chooses the one of the largest utility, [mathematical expression not reproducible]. If there exist more than one actions of largest utility, randomly choose one of them. Step 4: Go to step 2. End

Theorem 3: The SBRD learning algorithm converges to the local or the global maxima of the proposed potential function.

Proof: According to [12], the SBRD algorithm is enhanced from the best response algorithm. As it is proved in [21], in the best response algorithm, the selected node in each iteration only chooses the strategy which yields the largest utility function. Therefore, in each iteration, the utility function of the selected node increases to or remains in the largest value. It means that the potential function either increases or remains in each iteration. Besides, the potential function has an upper bound, so that the algorithm, after finite iterations, converges to one of the NEs. Different from [21], in the SBRD algorithm, non-adjacent nodes are chosen to update the strategies simultaneously. The strategies that are taken by chosen nodes have no influence on each other. Therefore, the enhanced best response algorithm just speeds up the convergence and has the same convergence performance as the best response algorithm. This ends the proof

5. Simulation Results

In this section, we compare the simulation results with the previous works to demonstrate the superiority of the proposed method. The simulation scenario follows the setting given in [23]. The bandwidth of each channel is B = 6MHz, and each small cell randomly chooses one, two or three channels based on its load. The noise power is [N.sub.0] = -100dBm, the transmission power of each small cell is P = 23dBm, and the path loss factor is [alpha] = 4. The distance between small cell n and its associated boundary user is [d.sub.nn] = 20m. To construct the hyperedges, we assume Q = 3 and set the two thresholds as [theta] = 3dB and [theta]' = 6dB.

5.1 Convergence Performance

In this section the small cells are randomly located in a 500m x 500m square area. It is assumed that there are 15 channels available for SAPs. The simulation results are revealed to illustrate the converge speed and the converge performance. We compare the average iteration times before convergences and average convergence values respectively of the BR (Best Response) [21], the SBRD and the E-SAP [10] algorithms versus the number of small cells.

Average iteration times before convergences versus the number of small cells are illustrated in Fig. 5. As the number of SAPs grows, the number of iterations required by the three algorithms increases accordingly. Both in case of the PMPI and the PNPI, the SBRD algorithm can converge with the least number of iterations, followed by the BR algorithm. The E-SAP algorithm needs the largest number of iterations, which is much higher than the other two algorithms. Meanwhile, in the same network topology and using the same learning algorithm, the vertex-weighted hypergraph-based game (PNPI) needs more iteration times than the unweighted hypergraph-based game (PMPI). Moreover, when the network gets denser, the difference in iteration number gets more obvious. In other words, the unweighted hypergraph-based game outperforms the vertex-weighted hypergraph-based game in the convergence speed especially when the network gets denser.

Average convergence values versus the number of small cells are illustrated in Fig. 6. As the number of SAPs grows, the defined global PMPI and PNPI increase because of the more serious interference. The E-SAP algorithm can always get the strategy with the interference less than or equal to the other two algorithms. While the average convergence values of the BR and the SBRD algorithms are almost equal. However, the difference in interference is not obvious. Moreover, when the interferences are brought into throughput, the difference of throughputs are much less obvious. Considering the convergence speed illustrated in Fig. 5, the SBRD algorithm can converge much faster than other algorithms. Therefore, the shortage of the SBRD algorithm in interference is negligible for a much higher converging speed. Though the E-SAP algorithm can converge to a strategy with the least interference, however, the small advantage in performance is obtained by the price of the converging speed.

5.2 Network Throughput Comparison

In this section we compare the network throughput respectively of the graph based MAC layer interference elimination game [11], the unweighted hypergraph-based game and the vertex-weighted hypergraph-based game.

By simulation, we get the network throughput versus the number of available channels of the three game solutions in different topologies with N = 30 in a 250m x 250m square area. Then we average them in Fig. 7.

We can conclude from the figure that the both hypergraph-based game solutions have the higher network throughput than the graph-based game solution. The reason is that the hypergraph-based solutions eliminate the cumulative interference which is ignored in the graph-based solution. When the available channels are insufficient, i.e., M [less than or equal to] 10, the SAPs are seriously interfered, so whatever optimization cannot further enhance the network throughput. Therefore, the two hypergraph-based game solutions have the similar throughputs. When 10 <M < 26, the vertex-weighted hypergraph- based game solution minimizes the physical layer interference, which, can better reflect the interference of the network than the MAC layer interference. Therefore, the vertex-weighted hypergraph-based game solution has the higher network throughput than the unweighted hypergraph-based game solution. When the available channels are abundant, i.e., M[greater than or equal to]26, the both hypergraph-based solutions can get the interference-free channel allocation strategies. Therefore, they have the similar throughputs.

It is assumed that there are 15 channels available for small cells. In Fig. 8, we compare the network throughput of the three game solutions versus the number of small cells in a 250m X 250m square area.

We can conclude from the figure that the two hypergraph-based game solutions have the higher network throughput than the graph-based game solution for they eliminate the cumulative interference which is ignored in the graph-based solution. When N [less than or equal to]15, the network is relatively sparse, both the direct and the cumulative interference are weak, the available channels are abundant for an interference-free arrangement. Therefore, the two hypergraph-based game solutions have the same network throughput. When N >15, the cumulative interference becomes stronger, the vertex-weighted hypergraph-based game solution minimizes the physical layer interference, which, can better reflect the interference of the network than the MAC layer interference. Therefore, the vertex-weighted hypergraph-based game solution has the higher network throughput than the unweighted hypergraph-based game solution. Moreover, as the network gets denser, the interference gets stronger, the advantage of the vertex-weighted hypergraph- based game solution gets more obvious. In the simulation scenario, each small cell selects a fixed number of channels according to its own load requirements. While the total number of available channels in the scene is fixed. Therefore, if more small cells are added into the network when the number of small cells in the area is saturated, no matter how the channel selection strategy is optimized, the network will be seriously interfered and receive more interference than the throughput gain. Therefore, the network throughput may decrease when the number of small cells is over 35.

Note that even though the vertex-weighted hypergraph-based game solution has the higher network throughput than the unweighted hypergraph-based game solution, its convergence speed is much lower.

6. Conclusion

We investigated the multi-channel access problem for hyper-dense small cell networks. With the application of the centralized-distributed model, we formulated the dynamic channel access problem as local altruistic games respectively based on the traditional unweighted hypergraph and the vertex-weighted hypergraph models. The two games were respectively aimed at minimizing the MAC layer interference and the physical layer interference. Then we proved that the games are both exact potential games, which admit at least one pure strategy NE. The SBRD learning algorithm is used to approach the NE points. Simulation results proved the advantage of the SBRD algorithm in the ultra-dense small cell networks. Also, the proposed hypergraph models improve the network throughput, better than the binary graph-based game model. Moreover, the different advantages of the two game solutions are validated.

It is noted that our work is focused on the static network and needs the information interaction. In the future work, we will study the spectrum access with no information interaction in the dynamic network.

References

[1] A. J. Fehske, I. Viering, J. Voigt, C. Sartori, S. Redana and G. P. Fettweis, "Small-Cell Self-Organizing Wireless Networks," Proceedings of the IEEE, vol. 102, no. 3, pp. 334-350, 2014. Article(CrossRefLink)

[2] J. G. Andrews, H. Claussen, M. Dohler, S. Rangan and M. C. Reed, "Femtocells: Past, Present, and Future," IEEE Journal on Selected Areas in Communications, vol. 30, no. 3, pp. 497-508, 2012. Article(CrossRefLink)

[3] H. Tamura, M. Sengoku, K. Nakano and S. Shinoda, "Graph theoretic or computational geometric research of cellular mobile communications," Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on, Orlando, FL, pp. 153-156 vol.6, 1999. Article(CrossRefLink)

[4] Y. Xu, J. Wang, Q. Wu, J. Zheng, L. Shen and A. Anpalagan, "Dynamic Spectrum Access in Time-Varying Environment: Distributed Learning Beyond Expectation Optimization," IEEE Transactions on Communications, vol. 65, no. 12, pp. 5305-5318, 2017. Article(CrossRefLink)

[5] Rongqing Zhang, Xiang Cheng, Liuqing Yang and Bingli Jiao, "Interference-aware graph based resource sharing for device-to-device communications underlaying cellular networks," in Proc. of 2013 IEEE Wireless Communications and Networking Conference (WCNC), Shanghai, 2013. Article(CrossRefLink)

[6] H. Zhang, T. Wang, L. Song and Z. Han, "Graph-based resource allocation for D2D communications underlaying cellular networks," in Proc. of 2013 IEEE/CIC International Conference on Communications in China - Workshops (CIC/ICCC), Xi'an, 2013, pp. 187-192, 2013. Article(CrossRefLink)

[7] H. Zhang, L. Song and Z. Han, "Radio Resource Allocation for Device-to-Device Underlay Communication Using Hypergraph Theory," IEEE Transactions on Wireless Communications, vol. 15, no. 7, pp. 4852-4861, 2016. Article(CrossRefLink)

[8] H. Zhang, Y. Ji, L. Song and H. Zhu, "Hypergraph based resource allocation for cross-cell device-to-device communications," in Proc. of 2016 IEEE International Conference on Communications (ICC), Kuala Lumpur, pp. 1-6, 2016. Article(CrossRefLink)

[9] J. Liu, S. Sun, J. Liu and Y. He, "Hypergraph-Based Intercell Interference Coordination for QoS Guarantees in Dense Femtocell Networks," in Proc. of 2015 IEEE 81st Vehicular Technology Conference (VTC Spring), Glasgow, pp. 1-6, 2015. Article(CrossRefLink)

[10] Y. Sun, Q. Wu, Y. Xu, Y. Zhang, F. Sun and J. Wang, "Distributed Channel Access for Device-to-Device Communications: A Hypergraph-Based Learning Solution," IEEE Communications Letters, vol. 21, no. 1, pp. 180-183, 2017. Article(CrossRefLink)

[11] Y. Xu, J. Wang, Q. Wu, A. Anpalagan and Y. D. Yao, "Opportunistic Spectrum Access in Cognitive Radio Networks: Global Optimization Using Local Interaction Games," IEEE Journal of Selected Topics in Signal Processing, vol. 6, no. 2, pp. 180-194, 2012. Article(CrossRefLink)

[12] Y. Xu, Q. Wu, et al., "Distributed Channel Selection in CRAHNs with Heterogeneous Spectrum Opportunities: A Local Congestion Game Approach," IEICE TRANS COMMUN, vol. E95-B, no. 3, 2012. Article(CrossRefLink)

[13] Q. Li, G. Kim and R. Negi, "Maximal Scheduling in a Hypergraph Model for Wireless Networks," in Proc. of 2008 IEEE International Conference on Communications, Beijing, pp. 3853-3857, 2008. Article(CrossRefLink)

[14] T. R. Jensen and B. Toft, Graph Coloring Problems. Wiley-Interscience, New York City, NY, 1995.

[15] D. Tsolkas, E. Liotou, N. Passas and L. Merakos, "A graph-coloring secondary resource allocation for D2D communications in LTE networks," in Proc. of 2012 IEEE 17th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), Barcelona, pp. 56-60, 2012. Article(CrossRefLink)

[16] J. Feng and M. Tao, "Hypergraph-based Frequency Reuse in Dense Femtocell Networks," in Proc. of 2013 IEEE/CIC International Conference on Communications in China (ICCC), pp. 537-542, 2013. Article(CrossRefLink)

[17] K. Yao, Q. Wu, Y. Xu and J. Jing, "Distributed ABS-Slot Access in Dense Heterogeneous Networks: A Potential Game Approach With Generalized Interference Model," IEEE Access, vol. 5, pp. 94-104, 2017. Article(CrossRefLink)

[18] Y. Xu, J. Wang, Y. Xu, L. Shen, et al., Centralizeddistributed Spectrum Access for Small Cell Networks: A Cloud-based Game Solution. [Online] Available: https://www.researchgate.net/publication/272845765_Centralized-distributed_Spectrum_Access_for_Small_Cell_Networks_A_Cloud-based_Game_Solution.

[19] A. Bretto, Hypergraph Theory: An Introduction, Springer International Publishing, 2013. Article(CrossRefLink)

[20] C. Berge, Graphs. North-Holland publishing company, Amsterdam, Netherlands, 1985.

[21] D. Monderer. and L. S. Shapley, "Potential Games," Games and Economic Behavior, vol. 14, pp. 124-143, 1996. Article(CrossRefLink)

[22] Y. Xu et al., "Load-Aware Dynamic Spectrum Access for Small-Cell Networks: A Graphical Game Approach," IEEE Transactions on Vehicular Technology, vol. 65, no. 10, pp. 8794-8800, 2016. Article(CrossRefLink)

[23] X. Chen and J. Huang, "Database-Assisted Distributed Spectrum Sharing," IEEE Journal on Selected Areas in Communications, vol. 31, no. 11, pp. 2349-2361, 2013. Article(CrossRefLink)

[24] X. Zhu, Yu. Xu, Y. Zhang, Y. Sun, Z. Du, "Load-aware Dynamic Access for Ultra-dense Small Cell Networks: A Hypergraph Game Theoretic Solution", in Proc. of 6th Interference Conference on Communication Signal Process and Systems, (CSPS) 2017, pp. 20-28. Harbn, Jul, 2018. Article(CrossRefLink)

[25] X. Zhu, X. Liu, Y. Xu, et al., "Dynamic Spectrum Access for D2D Networks: A Hypergraph Game Approach", in Proc. of 2017 IEEE 17th International Conference on Communication Technology (ICCT), pp. 861 - 866, Chengdu, Oct, 2017. Article(CrossRefLink)

Xucheng Zhu received his B.S. degree in School of Automation, Nanjing University of Science and Technology, Nanjing, China, in 2015. He received his M.S. degree in Communications and Information System in Army Engineering University of PLA College of Communication Engineering, Nanjing, China. His research interests focus on hyper-graph, game theory and optimization techniques for wireless communication networks.

Yuhua Xu received his B.S. degree in Communications Engineering, and Ph.D. degree in Communications and Information Systems from College of Communications Engineering, PLA University of Science and Technology, in 2006 and 2014 respectively. He is currently with the College of Communications Engineering, Army Engineering University of PLA, as an Associate Professor. He has published several papers in international conferences and reputed journals in his research area. His research interests focus on UAV communication networks, opportunistic spectrum access, learning theory and distributed optimization techniques for wireless communications.

He received Certificate of Appreciation as Exemplary Reviewer for the IEEE Communications Letters in 2011 and 2012, respectively. He was selected to receive the IEEE Signal Processing Society's 2015 Young Author Best Paper Award and the Funds for Distinguished Young Scholars of Jiangsu Province in 2016. He served as an Associate Editor for Transactions on Emerging Telecommunications Technologies (Wiley) and KSII Transactions on Internet and Information Systems, and the Guest Editor of Special Issue on The Evolution and the Revolution of 5G Wireless Communication Systems for IET Communications.

Xin Liu received his B.S. degree in Communications Engineering, M.S. degree in Communications and Information Systems, and Ph.D. degree in Communications and Information Systems from College of Communications Engineering, PLA University of Science and Technology, in 2004, 2008 and 2011 respectively. He has been with College of Information Science and Engineering, Guilin University of Technology since 2017, and currently as an Associate Professor. His research interests focus on anti-jamming communication, deep reinforcement learning, game theory, and soft defined radio. He has published several papers in international conferences and reputed journals in his research area.

Yuli Zhang received his B.S. degree in electronic and information engineering from Peking University, Beijing, China, in 2012 and M.S. degree from College of Communications Engineering, PLA University of Science and Technology, Nanjing, China, in 2015, respectively. He is currently a Ph.D. candidate in College of Communications Engineering, PLA University of Science and Technology. His research interests include resource allocation in small cell networks, game theory and energy harvesting.

Youming Sun (S'16) received the B.S. degree in electronic and information engineering from Yanshan University, Qinhuangdao, China, in 2010, and the M.S. degree from the National Digital Switching System Engineering and Technological Research Center (NDSC), Zhengzhou, China, in 2013, respectively. He is currently pursuing the Ph.D. degree in communications and information system with NDSC.

His research interests include resource allocation in small cell networks, cognitive radio networks, game theory, statistical learning and visible light communication. He currently serves as a Regular Reviewer for many technical journals, including the IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, the IEEE SYSTEMS JOURNAL, the IEEE ACCESS, the Transactions on Emerging Telecommunications Technologies, the Wireless Networks, the IET Communications, and the KSII Transactions on Internet and Information Systems. He has acted as a Technical Program Committee Member of the IEEE International Conference on Wireless Communications and Signal Processing 2015 and the 3rd International Conference on Wireless Communications and Sensor Networks 2016.

Zhiyong Du (S'12, M'17) received his B.S. degree in electronic information engineering from Wuhan University of Technology, Wuhan, China, in 2009 and his Ph.D. degree in communications and information systems in College of Communications Engineering, PLAUST, Nanjing, China, in 2015. Since 2016, he has been an assistant professor in National University of Defense Technology, Changsha, China. His research interests include 5G, quality of experience (QoE), learning theory and game theory.

Dianxiong Liu received the B.S. degree in School of Physics & Telecommunication Engineering, South China Normal University, Guangzhou, China, in 2014. He is currently pursuing the M.S. degree in communications and information system at College of Communications Engineering, PLA University of Science and Technology, Nanjing, China. His research interests are game theory and distributed optimization techniques for wireless communications.

Xucheng Zhu (1, 2,3), Yuhua Xu (1,3), Xin Liu (4), Yuli Zhang (1*), Youming Sun (5), Zhiyong Du (6) and Dianxiong Liu (1)

(1) Army Engineering University of PLA College of Communication Engineering, Nanjing, 210007, CHINA

[e-mails: zhuxucheng16@163.com; yuhuaenator@gmail.com; yulipkueecs08@126.com; dianxiongliu@163.com]

(2) Luoyang Electronic Equipment Test Center of China, Luoyang 471000, CHINA.

(3) Science and Technology on Communication Networks Laboratory, Shijiazhuang 050002, CHINA

(4) Guilin University of Technology, Guilin, 541000, CHINA

[e-mail: leo_nanjing@126.com]

(5) National Digital Switching System Engineering &Technological Research Center, Zhengzhou, 450000,

[e-mail: sunyouming10@163.com]

(6) National University of Defense Technology, Changsha, 410000, CHINA [e-mail: duzhiyong2010@gmail.com]

(*) Corresponding author: Yuli Zhang

Received July 9, 2017; revised January 25, 2018; accepted March 30, 2018; published February 28, 2019

This work was supported by the National Natural Science Foundation of China under Grant No. 61771488, No. 61671473 and No. 61631020, in part by the Natural Science Foundation for Distinguished Young Scholars of Jiangsu Province under Grant No. BK20160034, and in part by the Open Research Foundation of Science and Technology on Communication Networks Laboratory.

This paper is an extension of our conference paper ("Load-aware Dynamic Access for Ultra-dense Small Cell Networks: A Hypergraph Game Theoretic Solution", IEEE International Conference on Communications, Signal Processing, and Systems (CSPS) 2017, pp. 1-8, Harbin, Jul, 2017.).

http://doi.org/10.3837/tiis.2019.02.002

Printer friendly Cite/link Email Feedback | |

Author: | Zhu, Xucheng; Xu, Yuhua; Liu, Xin; Zhang, Yuli; Sun, Youming; Du, Zhiyong; Liu, Dianxiong |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Case study |

Date: | Feb 1, 2019 |

Words: | 7481 |

Previous Article: | Uplinks Analysis and Optimization of Hybrid Vehicular Networks. |

Next Article: | Content-Aware D2D Caching for Reducing Visiting Latency in Virtualized Cellular Networks. |

Topics: |