Social-Aware Joint Mode Selection and Link Allocation for Device-to-Device Communication Underlaying Cellular Networks

Lianxin Yang, Dan Wu, Hongkui Shi＊, Yanshan Long, Yueming Cai Institute of Communications Engineering, Army Engineering University of PLA, Nanjing 20007, China

2 College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210007, China

* The corresponding author, email: shihk@njupt.edu.cn

Abstract: Joint mode selection and link allocation are crucial to achieve the advantage of Device-to-Device (D2D) communications in improving spectral efficiency. In practice,cellular users tend to not be totally altruistic or absolutely selfish. How to stimulate them to devote their links and how to allocate their links to D2D pair candidates efficiently are two main challenges. In this paper, we encourage cellular users through the variable payment with regard to the social tie strength between cellular users and D2D pair candidates. In particular, the social tie strength is inferred through a graph inference model and its impact on the payment is quantified as a negative exponential function. Then, we propose a resource scheduling optimization model based on the non-transferable utility coalition formation game, and a distributed coalition formation algorithm based on the Pareto preference and merge-and-split rule. From them, thefinal coalition structure is obtained, which reflects the strategy of mode selection and link allocation. Numerical results are presented to verify the effectiveness of our proposed scheme.

Keywords: D2D communication; mode selection; link allocation; social ties; coalition formation game

I. INTRODUCTION

Due to the explosion of mobile data volume,Device-to-Device (D2D) communications have been playing a more and more important role in recent years [1-3]. By allowing two users in close proximity to communicate directly without being relayed by the BS, D2D communications can achieve great advantages in improving network throughput, spectral efficiency, and decreasing energy consumption. To make the best of these advantages,we should strive to address the following two issues: i) Mode selection. A D2D pair candidate needs to choose a proper communication mode from the cellular mode and the reusing D2D mode. In particular, the reusing D2D mode can achieve higher spectral efficiency,but leads to serious interference, and accordingly it has been a research hot spot, such as[4, 5]. ii) Link allocation. When the D2D pair candidate determines the reusing D2D mode,it needs to choose proper link sharers to suppress the interference, such as [6, 7]. Since the two issues will influence each other, and the joint optimization can bring much more improvement in network performance, it is necessary to develop a unified framework to in-volve both of them, such as [8]-[10]. However,due to the fact that this joint problem turns out to be NP-hard, it is usually decomposed into some sub-problems [8, 9], or is solved by using a centralized method based on nonlinear fractional programming [10].

As a result, we should construct a novel distributed optimization framework to deal with this joint problem. In the D2D communication scenario, once the D2D pair candidate reuses the links of cellular users, there is a relationship between them, and it can be seen that they form a group, and especially, both of them can achieve cooperative gains (e.g., the bandwidth broadening), but are subject to the costs of the link sharing (e.g., the mutual interference).Hence, we introduce a novel framework from coalitional game theory, known as coalition formation, to model the joint problem of mode selection and link allocation. Indeed, the coalition formation game can achieve a tradeoff between the benefits and the costs of the players involved in coalitions [11], and has been widely used in communication fields, such as [12, 13]. Unfortunately, few works focus on studying how to apply coalition formation game to solve the joint problem in D2D communications, except [14].

Furthermore, most of the existing works,e.g., [14, 15], assume that cellular users are completely altruistic, so that they are always willing to devote their links without any incentive. In fact, cellular users are not absolutely altruistic and then, they will ask the BS for some payments as the reward for their devotions. Since the BS can improve its traffic offloading by cellular users devoting their links to D2D pair candidates, it is always willing to provide cellular users with some payments.Such payment from the BS can be seen as an incentive to cellular users. In fact, the mobile devices are carried by human beings, who form stable social relationship in real world.The social information makes cellular users not totally selfish or not absolutely selfless.Obviously, the more intimate the relationship between D2D pair candidates and cellular users is, the more generous cellular users will be and the less the payment will be. It means that the social relationship enables to impact the amount of the payment. As such, the change of the payment leads to the change of the cooperative gains, and finally the change of the resource sharing strategy. Consequently,we should tap into the potential of the social relationship between D2D pair candidates and cellular users in variable payments when studying the joint mode selection and link allocation problem in D2D communications.

There exists some literature considering social relationship when studying D2D communications such as [16]-[21], where the concept of social ties is exploited. The social tie is one of the most important social networking characteristics [22], and plays an important role in the incentives for cooperation. The stronger the social tie between a D2D pair candidate and a cellular user is, the closer the social relationship between them will be. However, the social tie strength is assumed to obey a certain distribution, such as uniform distribution between 0 and 1 [17], or just set to be 1 [18]. In[19], the similarity of one interest of two users is used to infer the social tie strength, which lacks of comprehensiveness. Fortunately, a graph inference model introduced in [20] and[21] is a much more reasonable model to infer the social tie strength compared with other methods mentioned above. Hence, we need to further investigate the description of the social tie from what perspective to characterize the payments, and ponder how to avoid the additional storage and communication costs for obtaining the knowledge of the social tie.

In this paper, the social-aware joint mode selection and link allocation problem is studied from the perspective of coalition formation game. The main contributions are summarized as follows.

➢ We motivate cellular users to devote their links through the variable payment in terms of the social tie strength between cellular users and D2D pair candidates. In particular, the social tie strength is inferred by means of users’ encounter history and a graph inference model. The impact of the social ties on the payment is modeled as a negative exponential function to show the devoting willingness of cellular users.

➢ We model the social-aware joint mode selection and link allocation problem as a non-transferable utility coalition formation game. The proposed model can achieve a tradeoff among the broadening bandwidth, the payments and the mutual interference. Then,the mode selection and link allocation strategy can be transformed into the coalition structure by the dynamic coalition formation process

➢ We develop a social-aware distributed algorithm based on the Pareto preference and the merge-and-split rule to operate the dynamic coalition formation process. Importantly, the convergence of the algorithm is analyzed as well as the stability of the resulting coalition structure.

The remainder of the paper is organized as follows. The system model and the analysis of users’ achievable rates are presented in Section II. In Section III, we define the social-aware joint mode selection and link allocation problem as a non-transferable utility coalition formation game. Section IV presents the numerical results and discussions. Finally, Section V concludes the keyfindings for the paper.

Fig. 1. System model.

II. SYSTEM MODEL AND ANALYSIS OF USERS’ ACHIEVABLE RATES

2.1 System model

We consider a single cell network where the BS, is located in the center, and M D2D pair candidates and N cellular users are uniformly distributed as shown in figure 1. All users in the network form the set T. M and N denote the sets which are composed of M D2D pair candidates and N cellular users, respectively. That is,and. A D2D pair candidate is denoted by mi, and a cellular user is denoted by. Moreover,the transmitter and the receiver of D2D pair candidate miare denoted by mitand mir, respectively.

A D2D pair candidate refers to two users,who have satisfied some requirements of D2D communication, such as the distance and the interface. Cellular users have been allocated orthogonal links. Since the BS owns strong ability to process the interference and the traffic is heavier in downlink than in uplink, we restrict our attention to the underlying D2D communications with uplink resource sharing.Then, there mainly exist two modes, that is,the cellular mode and the reusing D2D mode.Moreover, we assume that one D2D pair candidate can reuse the uplinks of multiple cellular users, but the uplink of one cellular user can just be reused by at most one D2D pair candidate. Once there exist cellular users devoting their uplinks to D2D pair candidates,these D2D pair candidates may well adopt the reusing D2D mode to communicate. Otherwise, they employ the cellular mode.

In particular, when D2D pair candidates and cellular users share uplinks together, they form a group. One group consists of at most one D2D pair candidate, and there is no overlap between groups. In figure 1, D2D pair candidate m1reuses the uplinks of cellular users n3and n4, and they form a group. Similarly,D2D pair candidate m2shares the uplinks with cellular users n1and n2, and they constitute a group. Since D2D pair candidate m3does not share uplinks with any celluar user, a group if formed by itself.

Furthermore, D2D pair candidates and cellular users are connected with social ties,as shown in the upper layer of figure 1. The social tie strength influences the devoting willingness of cellular users, and directly leads to the amount of the payment from the BS. Strong social ties mean strong devoting willingness of cellular users, and they will ask little payment as the reward in this case.To offload its traffic, the BS always hopes that cellular users can devote their uplinks to D2D pair candidates, which motivates the BS to reward cellular users. Moreover, when allocating the uplinks of cellular users to D2D pair candidates, we learn the social tie strength between the receivers of D2D pair candidates and cellular users since the beneficiaries of D2D communications are the receivers of these D2D pair candidates. For simplicity, we don’t distinguish the receivers of D2D pair candidates and D2D pair candidates in the rest of the paper.

2.2 A graph inference model for social tie strength

In this subsection, we introduce a graph inference model [20, 21] to infer the social tie strength between D2D pair candidates and cellular users. Nowadays, the social network is developing rapidly, and people’s activities in social networks are mainly dependent on phone communications. Once two users communicate, we think they encounter. Here, we use the encounter history between D2D pair candidates and cellular users to infer the social tie strength. Due to the homogeneity property of social networks [21], it is observed that the stronger the social tie is, the longer time every encounter will stay for and the more frequently encounters will happen.

1) Encounter History Model: Inspired by [23, 24], we define the encounter history model for D2D pair candidate miand cellular user njas shown in figure 2. Tkdenotes the contact duration time for one encounter. The number of encounters for an observation time Tlenis denoted as Fmi,nj. Also, Ikis regarded as the time interval between two adjacent encounters. All the parameters are observed by the BS.

Given the observation, we define the similarity cmi,njbetween D2D pair candidate miand cellular user njas

Meanwhile, the average encounter intervalbetween two adjacent encounters is defi ned as

In order to ensure the precise social ties, an efficient method is to allow a large number of observations and calculate the average values.

2) Learning Model for Social Tie Strength:The social tie strength between D2D pair candidate miand cellular user njis denoted by εmi,nj, and a graph inference model [20, 21] is shown as figure 3.

Fig. 2. Encounter history model through physical interactions between D2D pair candidate mi and cellular user nj.

vmiand vnjare the attribute vectors which include some information of miand nj, such as political views, genders and communication trend. Here, the attribute refers to the encounter history. ymi,njis binary to indicate whether miand njencounter or not. When they encounter, ymi,nj=1. Otherwise, ymi,nj=0. In order to describe the encounter history information comprehensively, the descriptive vector emi,njis defined aswhere [⋅]Tmeans transposition. The social tie strength εmi,njis estimated to maximize the overall observed data likelihood.

Before getting the expression of the likelihood function, we will analyze some distributions, similar to [20, 21].

a) Given vmiand vnj, the joint distribution of εmi,njand yminjis presented as

b) Given vmiand vnj, the distribution of εmi,njis shown as

where w denotes the parameter which needs to be optimized in (5), and γ is the variance of this distribution.

c) Given εmi,njand emi,nj, the conditional probability of ymi,njis modeled as

Fig. 3. A graph inference model for the social tie strength εmi, nj.

Based on the above distributions, we rewrite (4) as

By substituting (5) and (6) into (7), we get the likelihood function as

Using (8), we get

The attribute vectors vmiand vnjare independent of the parameters gmi,njand w, and gmi,njand w are independent of each other.(9) is rewritten as

To avoid overfitting the observed data, the regularization variable μgand μwfor the parameters gmi,njand w are employed. Hence,the logarithmic form of the model is

in which C is a constant, and (11) is a concave function [20]. Then, we can use Newton Rapson algorithm [21] to adjust the parameters εmi,nj, w and gmi,njwith the goal of maximizing the likelihood function (11). Thefinal εmi,njis used to measure the social tie strength between D2D pair candidate miand cellular user nj.

Remark: Since the social ties are stable, the inferred social tie strength is not frequently updated during the whole resource sharing process.

2.3 Users’ achievable rates with social-aware incentive

In this subsection, we analyze users’ achievable rates when considering the impact of the social ties. The channel power gains from mitto its receiver mirof D2D pair candidate miand from mitto the BS are denoted by, respectively. The channel power gain from cellular user njto the BS and mirare expressed asrespectively. The transmit powers of D2D pair candidate miand cellular user njare pmiand pnj, respectively. Consider a Rayleigh fading channel model, the channel power gainis exponentially distributed with mean,where dit,iris the distance between mitand mir, and α denotes the path loss exponent.The same definitions are for other channel power gains. Moreover, σ2is the power spectral density of the additive Gaussian noise.

As a result, the received signal to interference plus noise ratio (SINR) at the receiver mirof D2D pair candidate mion the link of cellular user njis given by

Given the SINR, the achievable rate of D2D pair candidate mican be given by

The received SINR at the BS for cellular user njis denoted by

Given the SINR, the achievable rate of cellular user njcan be expressed as

Due to the existence of the interference, we should design a mechanism to stimulate cellular users to devote their uplinks. Inspired by[25, 26], we turn to the payment that the BS rewards. Since cellular users are two-faced,that is, they are generous to their “friends”, but are selfish to “strangers”, the payment varies with the social tie strength.

Motivated by this, the achievable rates of cellular user njwith social-aware incentive is rewritten as

where Kmi,njis the payment that the BS rewards cellular user njwhen it devotes its link to D2D pair candidate mi.

Moreover, we define Kmi,njas where Cnjis a constant for cellular user nj.It denotes the maximum payment that the BS needs to reward when cellular user njis absolutely selfish. εmi,njis the social tie strength between D2D pair candidate miand cellular user nj. η＞ 0 is an impact factor of the social ties to illustrate how important cellular user njconsiders the social ties. Large η means little payment, which may make the motivation to cellular users not enough. In contrast, the smaller the value of η is, the larger the payment will be. In this case, the traffic offloading cannot be improved efficiently, and the BS may be reluctant to provide the payment. Hence, the cellular users are required to balance the cons and pros to decide what η is.

The reasons why we define Kmi,njwith regard to εmi,njas (17) are listed as follows.

a) Intuitively, the larger εmi,njis, the more possible cellular user njwill be to contribute its uplink, and then the less the payment Kmi,njwill be. Thus, a monotone decreasing function with regard to εmi,njis required.

b) In practice, cellular user njis between totally selfish and altruistic. As a result, Kmi,njis bound to belong to a closed interval. For simplicity, we adopt a function with value(0,1) and an adjustable parameter to achieve such a goal. The product of the function and the parameter is used to denote the variable payment Kmi,nj.

c) The second derivative of the function with regard to the social tie strength εmi,njis smaller than 0. When εmi,njis increasing to a certain degree, cellular user njtends to be not very sensitive, and the decreasing of Kmi,njis not obvious. Under this circumstance, the payment Kmi,njthat cellular user njasks the BS for as the reward will have a little change.

Based on the above considerations, we turn to the negative exponential function for help.Moreover, our formula in (17) is able to measure the devoting willingness of cellular users well. Then, the stronger the social ties, the fewer the payments, and then the stronger the devoting willingness of cellular users

When cellular users share their uplinks with D2D pair candidates, their quality of service(QoS) requirements must be satisfied. In other words, the achievable rates should satisfy some threshold constraints. Thus, we have

Note that, (18) can also be seen as a protection measure for both D2D pair candidates and cellular users from the interference. Under such constraints, the QoS requirements for both D2D pair candidates and cellular users can be satisfied, whether the link sharing is successful or not.

When D2D pair candidate miemploys the cellular mode, the achievable rate is given by

When cellular user njdoes not share its link with any D2D pair candidate, the achievable rate is given by

III. SOCIAL-AWARE UPLINK SHARING AS A COALITION FORMATION GAME

When one D2D pair candidate tries to reuse the uplink of one cellular user, there is no doubt that serious interference will occur between them. This is the cost of uplink sharing.However, such uplink sharing will lead to bandwidth broadening. Also, the cellular users can enjoy the payments that the BS rewards.Due to the existence of social ties between D2D pair candidates and cellular users, the payment will decrease with increased social tie strength. As such, the achievable rates of cellular users will decrease as shown in (16).In turn, this will result in some benefits, such as the traffic offloading, to the BS. Thus, when studying the social-aware joint mode selection and link allocation problem in D2D communications, we should make a tradeoff between users’ achievable rates, the payments and the mutual interference.

As mentioned above, coalition formation game can study the complex interactions among users, and achieve a tradeoff between the gains and the costs involved in coalitions.Accordingly, we mathematically model the social-aware joint mode selection and link allocation problem as a non-transferable utility coalition formation game [27].

3.1 Coalition formation game

Specifically, the game is modeled as(T, S,u), where T denotes the players,including both D2D pair candidates and cellular users. They seek to form groups,named coalitions, to maximize their individual benefits.denotes the coalition structure. Here,andu is utility function,which is used to measure the coalition for a player. All players have their corresponding utilities when they are in different coalitions.

In essence, the resulting coalition structure indicates the strategies of the mode selection and link allocation for D2D pair candidates.Then, the four different cases are developed to show the corresponding relationship and the formulation of utility function.

Case 1: D2D pair candidate miand multiple cellular users are contained in coalition sk.In this case, D2D pair candidate miemploys reusing D2D mode and reuses the uplinks of these cellular users to communicate. The utilities of D2D pair candidate miand cellular user njare defined as

Case 2: Only D2D pair candidate miis contained in coalition sk. In this case, D2D pair candidate miemploys cellular mode and uses orthogonal link to communicate. The utility of D2D pair candidate miis defined as

Case 3: Only cellular user njis contained in coalition sk. In this case, cellular user doesn’t share its uplink with any D2D pair candidate. The utility of cellular user njis deif ned as

Case 4: Multiple D2D pair candidates and cellular users are contained in a coalition. Due to the serious interference among these D2D pair candidates, the utilities of the players in such coalition tend to be −∞.

From (21), we know that the stronger the social tie is, the smaller the utilities of cellular users will be. This is because when designing the utilities, we balance the traffic offloading from the BS, the social tie strength and the devoting willingness of cellular users.

Definition 1: The coalition formation is said to have a non-transferable utility, if every player in coalition skowns his corresponding utility.

Theorem 1[15]. Given the definition of the utilities for cellular users and D2D pair candidates, the defined coalition formation game has a non-transferable utility.

Theorem 2. Disjoint independent coalitions form instead of grand coalitions in the defined coalition formation game.

Proof: In practice, it is likely that more than one D2D pair candidate can join the same coalition as illustrated in Case 4. In this way, the utility of every player tends to be−∞. Thus, such coalitions cannot be formed.Another case is that one D2D pair candidate and so many cellular users join the same coalition. However, the increases in the number of these cellular users will cause the broadening bandwidth Wmito narrow. As a result, the benefit of the uplink sharing gradually weakens. Moreover, the cellular user can always get the payments from the BS once it joins a coalition, whether the coalition is grand or disjoint. Then, cellular users will not choose to join grand coalitions. Thus, thefinal coalition structure generally contains disjoint coalitions.

3.2 Distributed coalition formation algorithm

1) Algorithm Description:

Definition 2: For two different coalition structures A and B, if ∀l∈M, thenin which skand sk′are the coalitions in A and B that player l belongs to, respectively. Moreover, at least one player gets stronger utility in A than in B. In this case, coalition structure A is better than B,which is denoted by A▷pB. This relationship is Pareto preference.

Definition 3: Merge rule: Given two coalition structures

Splitrule: Given two coalition structures

Then, we propose a social-aware distributed coalition formation algorithm based on the Pareto preference and merge-and-split rule,which is described in Algorithm 1.

Our proposed algorithm consists of three stages. The first stage is initialization, which inputs some parameters that the algorithm needs. Then, the merge process happens. If there don’t exist any two coalitions that can merge into one coalition, this process ends.Finally, the players in one coalition check if their leave can improve their utilities without harming the performance of the players still in the coalition. If so, the coalition will split into smaller coalitions. Otherwise, the algorithm terminates.

2) Property Analysis:

Theorem 3. Whatever the number of D2D pair candidates and the number of cellular users are, thefinal coalition structure can always be formed throughfinite comparisons in Algorithm 1.

Proof: Consider that there exist M D2D pair candidates and N cellular users in the single cell. During merge process, in the worst case, thefirst D2D pair candidate requires N attempts for merge, the second one requires N and so on. Thus, the total number of comparisons leads to M⋅ N and only the last comparison may result in a coalition. In general, the final coalition structure may be formed through less than M⋅ N comparisons. The split process has the similar analysis. Moreover, the utilities of players need to satisfy their QoS requirements if they join coalitions. Thus, not all the players can step into merge process. As a result, only if the number of the users in the cell isfinite, thefinal stable coalition structure can always be obtained via our proposed algorithm.

Moreover, we exploit the concept of defection function in [27, 28] to illustrate the stability of thefinal coalition structure.

Definition 4: A coalition structure S is Dhp−stable, if no player has interest in leaving the current coalition to join another through merge-and-split rule. Specifically, the following two conditions are met: i) For coalition sk,there doesn’t exist a positive number q which makes thatcontains the same players as skand, and ii) For each(is the opposite rule of ▷p).

Theorem 4. The resulting coalition structure through the proposed algorithm in Algorithm 1 is Dhp−stable.

Proof: Based on Theorem 3, we know that the players cannot leave the final coalition structure S from algorithm 1. For anyandfor sk, we assume thatThen, S is still modified based on the split rule, which contradicts with the fact that S is thefinal coalition structure based on the merge-and-split rule from algorithm 1. Thus, thefirst condition of Definition 4 is proven. A similar proof process is made for the second condition. Therefore,the theorem is proven.

Then, we analyze the complexity of the proposed algorithm. To be specific, the complexity actually consists of three parts. Thefirst part is the complexity of Newton Rapson algorithm for the inference of the social ties.The second part comes from the merge process. Its complexity in the worst case is M⋅ N as shown in the proof of Theorem 3. Another extreme case is that thefirst D2D pair candidate and all the cellular users form the final coalition structure. In this case, the complexity is N. The last part is the complexity of split process. The split operations are only applied to the coalitions that include both D2D pair candidate and more than one cellular user.As analyzed in [15], for such a coalition, the number of all possible dissociated coalitions isOnce a dissociated coalition satisfies the Pareto preference, the coalition will split. Due to the additional costs of split process, the BS may not allow such coalitions to split into small coalitions, which further reduces the complexity of the proposed algorithm.

Finally, we analyze the overhead of the proposed algorithm. D2D pair candidates and cellular users need to exchange some information, such as the knowledge of channel state and the social characteristics, which leads to some but not too much additional overhead.Specifically, the signaling mechanism in [29]is exploited for users to periodically report to the BS to show whether they newly join in or disaffiliate from the cell. In fact, this justneeds to send an acknowledgment which is similar to a handshake. Importantly, when deciding which D2D pair candidate and cellular users can join in the same coalitions, we need the knowledge of channel state and the social characteristics to calculate the utilities.Due to the channel reciprocity, the knowledge on channels between the users and between the users and the BS can be obtained by each other during the above processes. Similarly,the information of social characteristics can be informed by each other, which is attached to these processes. Moreover, such information is updated periodically, and the corresponding frequency is a predetermined value in general. For example, the time scale can be set by LTE’s scheduling and transmission time interval of 1 ms. Once the time is up, the most outdated information are replaced by the newest. It implies that the users and the BS always keep a history of recent values with a low storage overhead.

IV. NUMERICAL RESULTS

In this section, we conduct some numerical simulations to validate our proposed social-aware distributed algorithm. We consider one realization of a single cell where 4 cellular users and 3 D2D pair candidates are uniformly distributed as shown in figure 4. The maxi-mum distance of the two users for one D2D pair candidate is restricted to be less than 30 m. Note that the scenario can be extended to a network where there exist more users. Other parameter settings are presented in table 1.

Table I. Simulation parameters.

Fig. 4. Users’ locations in the network. 4 cellular users and 3 D2D pair candidates are contained, which is assumed to be an example to verify the effectiveness of our proposed scheme.

Based on these settings, the social tie strength through the Newton Rapson algorithm is inferred to be about 0.4. For simplicity, we adopt the absolute value of a Gaussian distribution to model the social tie strength between cellular users and D2D pair candidates. The mean of the distribution is 0.4 and its variance is 1.

As for the constant Cnjin (17), it is hard for us to determine the exact Cnjis. When D2D pair candidate miemploys reusing D2D mode and reuses the uplink of cellular user njto communicate, the achievable rate of D2D pair candidateis, whereAt this moment, D2D pair candidate miwill provide some of its utility to be the payment of cellular user nj.Thus, we setasin our simulation.

Moreover, to determine the value of η in(17), we firstly define the traffic offloaded from the BS as

in which ξminjis binary to indicate whether D2D pair candidate miand cellular user njshare uplinks or not.

Then, we try to determine what η is. We set η from 2 to 30 and its interval 0.5 to get the corresponding offloaded traffic when the numbers of cellular users and D2D pair candidates are different. For every η, we run 100 times and get the average offloaded traffic.The change of the offloaded traffic versus η is shown as figure 5.

From figure 5, we can see that the offloaded traffic decreases with η increasing.This is because that large η results in less payment for cellular users when the social ties are determined. In this regard, fewer and fewer cellular users will like to join coalitions.Moreover, with the number of cellular users and D2D pair candidates increasing, more cellular users have the opportunity to join the coalitions. Thus, the offloaded traffic becomes larger. Moreover, on one hand, the smaller η is, the more the payment the BS rewards cellular users. Though the offloaded traffic is larger, the process of the BS rewarding the payment in practical scenarios will limit this benefit. On the other hand, the larger η is, the more reluctant cellular users will be to devote their links. Moreover, the offloaded traffic is becoming less and less. As a result, we make a tradeoff when setting the value of η. In our experiment, η is set as 3.

After that, we simulate the scenario as shown in figure 4. The matrix for the social tie strength between D2D pair candidates and cellular users is obtained as

The final coalition structure isHence, D2D pair candidate m2, cellular users n1and n3share uplinks together. D2D pair candidate m2employs reusing D2D mode to communicate and becomes a true D2D pair.However, D2D pair candidates m1and m3still communicate using cellular mode. We can see from figure 4 that D2D pair candidate m2is far away from the BS, but m1and m3are located near the BS. Thus, D2D pair candidate m1and m3can achieve higher utilities with cellular mode than those with reusing D2D mode. This is why they don’t form coalitions with any cellular users. As for cellular users n2and n4, their utilities make them not form coalitions with any other D2D pair candidates.Specifically, D2D pair candidate stay close to cellular user n2and will cause serious to n2.The social tie strength between D2D pair candidate m2and n4is large so that the payment for n4is small. This results in the small utility of n4. In next uplink sharing process, cellular users and the BS will adjust the parameters to avoid such phenomenon to happen. Note that, different social tie strength may result in different resource sharing strategies. Here, we present one case to prove the effectiveness of our proposed scheme.

Fig. 5. The traffic offloaded from the BS versus the impact factor of the social ties from 2 to 30 under different numbers of users in the network.

Fig. 6. Comparison of the utilities for cellular users under different communication modes when we consider users’ social ties.

Figure 6 depicts the comparison of the utilities for cellular users when their links are reused by D2D pair candidates and not. The utilities of cellular users n1and n3are all improved. This is because that the benefit of the bandwidth broadening from resource sharing and the payment from the BS is larger than the cost from the mutual interference. Moreover,the utility of cellular user n1is improved by 24.10%, while cellular user n362.39%. This is due to the fact that the social tie strength between D2D pair candidate m2and cellular user n3and is weaker than that between D2D pair candidate m2and cellular user n1. As a result, the payment that the BS rewards cellular user n3is larger than that the BS rewards cellular user n1.

Fig. 7. Comparison of the utilities for D2D pair candidates under different communication modes when we consider users’ social ties.

Fig. 8. Comparison of the utilities for cellular users under different communication modes when we don’t consider users’ social ties.

Figure 7 shows the improvement of the utility for D2D pair candidate m2by 347.14%.Obviously, it is improved more than those of cellular users. On the one hand, uplink sharing leads to the bandwidth broadening. On the other hand, D2D pair candidate m2is able to make full use of the advantage of close proximity when it employs reusing D2D mode.Thus, its utility is improved a lot.

To illustrate that our proposed scheme can motivate cellular users to join coalitions, we compare our scheme with the scheme in [15], which does not consider the social-aware incentive. Under the scenario in figure 4, the final coalition structure isWe can see that if we don’t stimulate cellular users to devote their links, cellular user n3cannot join the coalition with D2D pair candidate m2and cellular user n1. However, if the BS rewards cellular users with large amount of payment indiscriminately, on one hand,the traffic offload of the BS cannot be improved a lot, and on the other hand, this is not consistent with practical situation due to the existence of the social ties between D2D pair candidates and cellular users.

Besides, the comparison of the utilities for cellular users is shown in figure 8. Obviously,the utility of cellular user n3can even not guarantee its QoS requirement.

Moreover, to prove the effectiveness of our proposed scheme, we compare our scheme with cellular scheme, and the scheme in [20]when there exist different number of cellular users and D2D pair candidates in the network.In cellular scheme, all D2D pair candidates communicate through cellular modes. In[20], the authors add the normalized social tie strength to the achievable rates of cellular users in the resource allocation problem. Such method is employed to stimulate cellular users and considered as another comparison benchmark. Other parameters are set the same as our scheme for comparison.

When the number of cellular users varies from 5 to 25, but the number of D2D pair candidates is fixed as 10, figure 9 compares the average sum utilities for cellular users.We can see that the average sum utilities are larger in our proposed scheme than those in the other two schemes, which demonstrates that our proposed scheme can achieve a better performance for cellular users. Moreover, the advantage between our proposed scheme and the other two schemes becomes more obvious with the number of cellular users increasing.This is because more cellular users can join coalitions with the number of cellular users increasing. Thus, they can get much more payment from the BS.

Figure 10 corresponds to the scenario where the number of cellular users is fixed as 10,but the number of D2D pair candidates varies from 5 to 25. We can see that our proposed scheme and the scheme in [20] outperform the cellular scheme. This is due to the fact that D2D pair candidates in the cellular scheme all employ cellular mode and the advantage of close proximity cannot be achieved. Moreover,the gap is becoming smaller with the number of D2D pair candidates increasing. This is because the number of cellular users is fixed as 10 and the number of D2D pair candidates who can join coalitions is limited. It is worthy to note that our proposed scheme can achieve a better performance than the scheme in [20],which illustrates that our incentive scheme is much more efficient.

V. CONCLUSION

Fig. 9. Comparison of the average sum utilities for cellular users between the proposed scheme and two other schemes when the number of cellular users varies from 5 to 25 and the number of D2D pair candidates isfixed as 10.

Fig. 10. Comparison of the average sum utilities for D2D pair candidates between the proposed scheme and two other schemes when the number of D2D pair candidates varies from 5 to 25 and the number of cellular users isfixed as 10.

In this paper, we develop a novel coalition formation framework to study the social-aware joint mode selection and link allocation problem for D2D communications under-laying cellular networks. To be specific, a graph inference model is used to infer the social tie strength, and then, we stimulate cellular users to devote their links through variable payment with the social tie strength. Moreover, we model the joint mode selection and link allocation problem as a non-transferable utility coalition formation game and propose a distributed coalition formation algorithm based on the Pareto preference and merge-andsplit rule. The convergence of this algorithm is analyzed, and the stability of the coalition structure via this algorithm is proven. Simulation results demonstrate the effectiveness of the proposed model and algorithm. In ongoing work, we will extend the single cell scenario to a multi-cell scenario, and pursue some joint optimal solutions, e.g. to jointly study mode selection, link allocation and power control,especially when the impact of the social ties is considered.

ACKNOWLEDGEMENT

This work was supported by Natural Science Foundations of China (No. 61671474), and Jiangsu Provincial Natural Science Foundation for Excellent Young Scholars (No.BK20170089).