# A New Cooperative Dual-Level Game Approach for Operator-Controlled Multihop D2D Communications

Authors: Sungwook Kim
Journal: Mobile Information Systems
 (2019)

---

## Abstract

With the development of wireless communications and the intellectualization of mobile devices, device-to-device (D2D) communications are considered as a standard part of future 5G networks. This new paradigm can provide better user experiences while improving the system performance such as network throughput, latency, fairness, and energy efficiency. In this study, we investigate a new dual-level D2D communication scheme consisting of multiple D2D operators and a group of mobile devices. To model the interaction among D2D operators and devices, we adopt two cooperative game approaches based on the incentive mechanism design and r-egalitarian Shapley value. At the upper level, routing paths and incentive payments for multihop relay services are decided using the incentive mechanism. At the lower level, mobile devices share the given incentive based on the r-egalitarian Shapley value. Both level control procedures are mutually dependent on each other by the proper coordination and collaboration. According to the main features of two cooperative game models, the proposed scheme takes various benefits in a fair-efficient way. Through the derived simulation results, we can verify the superiority of our proposed scheme comparing to the existing protocols. Finally, we propose further challenges and future opportunities in the research area of operator-controlled multihop D2D communications.


---

## Body

## 1. Introduction

The recent widespread use of intelligent mobile devices with smart applications has led to an explosive growth in mobile data traffic. As a result of dramatic traffic growth of mobile devices, a massive burden on wireless network is created. To provide a higher peak date rate and a better network capacity, the development of the fifth generation (5G) mobile communications technology far beyond the current 4G systems is necessary. By 2023, more than 20 percent of mobile data traffic worldwide is expected to be carried by 5G networks. This is 1.5 times more than the total 4G/3G/2G traffic today. This remarkable growing momentum of network traffic will stimulate and promote researches on novel cooperative communication techniques, mainly due to the emerging need for connecting mobile devices in a ubiquitous manner [1].Recently, device-to-device (D2D) communication has become a potential candidate technology to handle the 5G network capacity and coverage problems. Most D2D communications have focused on the case of natural disasters when the infrastructure-based network services are either partially or totally unavailable. Usually, the D2D technology extends the traditional wireless communication system. It enables two mobile devices directly establish a wireless link between each other without any backbone network structure; these two mobile devices are geographically close to each other in the proximity area. However, single-hop D2D communications are usually limited to a specific geographic area. Therefore, the advantages of D2D communication can be fully realized in the multihop communication scenario. Nowadays, ad hoc manner-based multihop D2D service is a new communication model for the 5G network technology [2, 3].Commonly, multihop D2D communications refer to direct data exchanges among multiple devices without the involvement of wireless operators (WOs). Therefore, the conventional multihop D2D approach cannot provide efficiently quality-of-service (QoS) ensuring data traffic services. Nowadays, there is a new trend towards an operator-controlled D2D communication paradigm to maximize the profit of system manager as well as better QoS experience for devices. In this new paradigm, WOs should pursue the D2D communication function in their networks. Specifically, each WO is responsible to monitor devices in its covering area and establishes routing paths in concert with other WOs. To induce selfish devices to participate in data relay transmissions in multihop D2D communications, WOs should provide adaptive incentives to the corresponding devices [4, 5].In the operator-controlled D2D communication system, each individual WO needs to cooperate with each other to improve the total system performance. In addition, mobile devices covering by a specific WO also need to reach a collaborative agreement for the incentive distribution. To get the mutual advantages for themselves, this interrelated operator-device cooperation can be modeled as a hierarchical cooperation problem. To solve this problem, the major questions to be answered are (i) what is the adaptable incentive payment to perform the multihop D2D communications and (ii) how to effectively distribute the given incentive payment to relaying devices. For these two issues, two different strategies are necessary [4, 6].Over the past decade, various non-cooperative and cooperative game models have been extensively applied to analyze interactive decision makings of network agents. However, traditional non-cooperative games suffer from many shortcomings, which render them inadequate to apply for the operator-controlled D2D communications. In particular, major arguments against using non-cooperative game models can be listed, but are not limited to (i) the immense overhead caused by information acquisition, (ii) the slow convergence to equilibrium, (iii) the inefficiency of equilibrium in terms of social welfare, and (iv) the theoretical complexity of characterizing the equilibrium set [7, 8]. In contrast to non-cooperative games, cooperative game models can fit the characteristics of multihop D2D systems more appropriately. In essence, such models are beneficially used for D2D communication functions. To this end, the cooperative game approach is chosen to design a novel operator-controlled D2D communication scheme.In this paper, we adopt two different cooperative game concepts to solve the hierarchical cooperation problem for the operator-controlled D2D communications. By considering the mutual-interactive relationship between WOs and mobile devices, a new dual-level game model is formulated based on two cooperative game solutions, i.e., incentive mechanism design (IMD) and r-egalitarian Shapley value. At the upper-level process, the IMD is used to decide the incentive payment for WOs, which are covering the routing path of multihop D2D communications. At the lower-level process, each WO distributes the obtained payment to incentivize its corresponding mobile devices based on the r-egalitarian Shapley value. With desired properties of cooperative game concepts, we attempt to reach an outcome that meets our design goals while taking advantages under asymmetric information situations.


### 1.1. Related Work

Due to the promising driving force for the improvement of 5G network capacity, multihop D2D communications are attracting growing attention from industry and academia. Recently, various protocols have been published from the new perspectives of key techniques and challenges about multihop D2D communications. TheCoalitional Perspective D2D (CPD2D) scheme is a cooperative game approach to perform a multipath routing mechanism. This scheme enables the WOs and mobile devices to improve their payoffs by collaborative working [4]. To model the interactions among game players, i.e., WOs and devices, this scheme designs a cooperative game-theoretic algorithm and proposes a layered coalitional game model to address the decision-making problems among players. By using the extended recursive core coalition approach, the cooperative devices establish links among each other to form a stable network structure for the multipath routing. Finally, simulation results have shown that the CPD2D scheme yields notable performance gains relative to the non-cooperative approach and achieves good convergence speed [4].TheRelay-Assisted D2D (RAD2D) scheme is designed to improve the QoS of D2D communications while enlarging the communication range [9]. By taking the user selfishness and mobility into considerations, this scheme formulates the throughput maximization problem for the multihop D2D communications and develops the theoretical foundation of the spectrum reuse set partitioning. In particular, the RAD2D scheme is a relay-assisted D2D communication protocol that addresses the challenges in enabling multihop D2D communications with relay incentives; a cheat avoidance incentive mechanism is developed with lightweight overheads to incentivize users to relay data. Under dynamic scenarios, extensive simulation results show that the RAD2D scheme can improve the system throughput and the user access rate as compared with baseline schemes [9].TheCentralized Adaptive D2D (CAD2D) scheme focuses on an analysis of state-of-the-art routing algorithms that will enable intelligent D2D communications [10]. Based on the centralized adaptive routing, this scheme develops a new route discovery mechanism that will reduce the routing overhead to a great extent. Depending upon network conditions, such as varying device density and traffic load, the CAD2D scheme updates periodically the D2D communication path while adapting between reactive and proactive routing strategies. By gathering information from all mobile devices, the proposed protocol in [10] has a number of features, including energy and load awareness, special route request, and avoiding any kind of flooding. The main contribution of the CAD2D scheme is to reduce the routing overhead to a dramatic level in multihop D2D communications [10].The earlier studies [4, 9, 10] have attracted considerable attentions while introducing unique challenges in handling multihop D2D communication problems. In this paper, we compare our proposed scheme with the existing the CPD2D [4], RAD2D [9], and CAD2D [10] schemes and demonstrate that our dual-level cooperative game-based D2D control approach can significantly outperform these existing schemes.


### 1.2. Contribution

In this paper, we model the interactions between WOs and mobile devices and design a new dual-level hierarchical cooperative game. At the upper-level game, WOs are game players, and the incentive payments are calculated based on the IMD for relay WOs. At the lower-level game, data relaying mobile devices are game players, and they share the incentive payment of their corresponding WO based on the r-egalitarian Shapley value. To leverage the full synergy of our dual-level approach, we take into account comprehensively some control issues and consider all the relevant practical factors in the operator-controlled multihop D2D communications. In summary, the contributions of this study are as follows:(i)
Dual-level game model: motivated by a hierarchically depending situation, we introduce a new dual-level game model while capturing the interactive relationship between WOs and mobile devices. Our dual-level game approach is generic and applicable to operator-controlled multihop D2D communications.(ii)
IMD for the upper-level game: incentive payments for WOs are assigned to compensate for the cost of D2D communication relay services. According to the IMD, we properly make amends for the devices’ relaying cost through their representative WO.(iii)
r-egalitarian Shapley value for the lower-level game: mobile devices share the incentive payment of their corresponding WO. According to the r-egalitarian Shapley value, it can be shared in a fair-efficient way. Therefore, our method can effectively induce mobile devices to participate in multihop D2D data relay services.(iv)
The synergy of combined two game models: we explore the interaction of two different game approaches and jointly design an integrated scheme to leverage the synergistic and complementary features. The main idea of our dual-level game lies in its responsiveness to the reciprocal combination of two different cooperative game solutions for operator-controlled D2D communications.(v)
Solution concept: under dynamic D2D communication environments, traditional non-cooperative game solutions suffer from the uncertainty and impractical assumptions. The main goal of this study is to investigate the potential benefit gained from practically implemented cooperation game methods and to get the finest solution based on the step-by-step interactive feedback process.(vi)
Conclusions: numerical study shows that our dual-level game approach can improve the system throughput and the fairness of WOs and mobile devices by 10% to 40% under different D2D service request rates, comparing to the existingCPD2D [4], RAD2D [9], and CAD2D [10] schemes.


### 1.3. Organization

The rest of this paper proceeds as follows. Section2 presents an infrastructure of operator-controlled multihop D2D communication system, and some basic mathematical concepts about IMD and r-egalitarian Shapley value are given. Based on the novel dual-level game method, the details of our proposed scheme are covered in this section. Experimental results from the simulation analysis are provided in Section 3. Finally, Section 4 summarizes the whole work and concludes this study with suggestions for future work.


## 1.1. Related Work

Due to the promising driving force for the improvement of 5G network capacity, multihop D2D communications are attracting growing attention from industry and academia. Recently, various protocols have been published from the new perspectives of key techniques and challenges about multihop D2D communications. TheCoalitional Perspective D2D (CPD2D) scheme is a cooperative game approach to perform a multipath routing mechanism. This scheme enables the WOs and mobile devices to improve their payoffs by collaborative working [4]. To model the interactions among game players, i.e., WOs and devices, this scheme designs a cooperative game-theoretic algorithm and proposes a layered coalitional game model to address the decision-making problems among players. By using the extended recursive core coalition approach, the cooperative devices establish links among each other to form a stable network structure for the multipath routing. Finally, simulation results have shown that the CPD2D scheme yields notable performance gains relative to the non-cooperative approach and achieves good convergence speed [4].TheRelay-Assisted D2D (RAD2D) scheme is designed to improve the QoS of D2D communications while enlarging the communication range [9]. By taking the user selfishness and mobility into considerations, this scheme formulates the throughput maximization problem for the multihop D2D communications and develops the theoretical foundation of the spectrum reuse set partitioning. In particular, the RAD2D scheme is a relay-assisted D2D communication protocol that addresses the challenges in enabling multihop D2D communications with relay incentives; a cheat avoidance incentive mechanism is developed with lightweight overheads to incentivize users to relay data. Under dynamic scenarios, extensive simulation results show that the RAD2D scheme can improve the system throughput and the user access rate as compared with baseline schemes [9].TheCentralized Adaptive D2D (CAD2D) scheme focuses on an analysis of state-of-the-art routing algorithms that will enable intelligent D2D communications [10]. Based on the centralized adaptive routing, this scheme develops a new route discovery mechanism that will reduce the routing overhead to a great extent. Depending upon network conditions, such as varying device density and traffic load, the CAD2D scheme updates periodically the D2D communication path while adapting between reactive and proactive routing strategies. By gathering information from all mobile devices, the proposed protocol in [10] has a number of features, including energy and load awareness, special route request, and avoiding any kind of flooding. The main contribution of the CAD2D scheme is to reduce the routing overhead to a dramatic level in multihop D2D communications [10].The earlier studies [4, 9, 10] have attracted considerable attentions while introducing unique challenges in handling multihop D2D communication problems. In this paper, we compare our proposed scheme with the existing the CPD2D [4], RAD2D [9], and CAD2D [10] schemes and demonstrate that our dual-level cooperative game-based D2D control approach can significantly outperform these existing schemes.


## 1.2. Contribution

In this paper, we model the interactions between WOs and mobile devices and design a new dual-level hierarchical cooperative game. At the upper-level game, WOs are game players, and the incentive payments are calculated based on the IMD for relay WOs. At the lower-level game, data relaying mobile devices are game players, and they share the incentive payment of their corresponding WO based on the r-egalitarian Shapley value. To leverage the full synergy of our dual-level approach, we take into account comprehensively some control issues and consider all the relevant practical factors in the operator-controlled multihop D2D communications. In summary, the contributions of this study are as follows:(i)
Dual-level game model: motivated by a hierarchically depending situation, we introduce a new dual-level game model while capturing the interactive relationship between WOs and mobile devices. Our dual-level game approach is generic and applicable to operator-controlled multihop D2D communications.(ii)
IMD for the upper-level game: incentive payments for WOs are assigned to compensate for the cost of D2D communication relay services. According to the IMD, we properly make amends for the devices’ relaying cost through their representative WO.(iii)
r-egalitarian Shapley value for the lower-level game: mobile devices share the incentive payment of their corresponding WO. According to the r-egalitarian Shapley value, it can be shared in a fair-efficient way. Therefore, our method can effectively induce mobile devices to participate in multihop D2D data relay services.(iv)
The synergy of combined two game models: we explore the interaction of two different game approaches and jointly design an integrated scheme to leverage the synergistic and complementary features. The main idea of our dual-level game lies in its responsiveness to the reciprocal combination of two different cooperative game solutions for operator-controlled D2D communications.(v)
Solution concept: under dynamic D2D communication environments, traditional non-cooperative game solutions suffer from the uncertainty and impractical assumptions. The main goal of this study is to investigate the potential benefit gained from practically implemented cooperation game methods and to get the finest solution based on the step-by-step interactive feedback process.(vi)
Conclusions: numerical study shows that our dual-level game approach can improve the system throughput and the fairness of WOs and mobile devices by 10% to 40% under different D2D service request rates, comparing to the existingCPD2D [4], RAD2D [9], and CAD2D [10] schemes.


## 1.3. Organization

The rest of this paper proceeds as follows. Section2 presents an infrastructure of operator-controlled multihop D2D communication system, and some basic mathematical concepts about IMD and r-egalitarian Shapley value are given. Based on the novel dual-level game method, the details of our proposed scheme are covered in this section. Experimental results from the simulation analysis are provided in Section 3. Finally, Section 4 summarizes the whole work and concludes this study with suggestions for future work.


## 2. Proposed Operator-Controlled D2D Control Scheme

In this section, we present several concepts in line with the IMD and r-egalitarian Shapley value; they are needed in the rest of the paper. And then, we briefly introduce the formulation of our dual-level game approach and explain in detail the proposed operator-controlled D2D communication scheme. Finally, they are described in the nine-step procedures.


### 2.1. Operator-Controlled D2D Communication Infrastructure

In this study, we consider an operator-controlled D2D communication system consisting of a number of devices belonging to multiple operators. Mobile devices are randomly deployed within a large coverage area. In the operator-controlled D2D infrastructure, a geographic coverage area is subdivided and served by operators. Operators are connected each other through high-speed wired links to transfer the system control information, and mobile devices are connected their corresponding operators through wireless links. Due to the limited transmission power of each device, multihop relaying is adopted to route flow data communications from source mobile devices to destination mobile devices [4, 11]. Denote the set of operators as O=O1,…,On and MO1≤i≤n=M1Oi,…,MmOi is the set of devices under the operator Oi∈O. Oi is responsible to the devices in the set MOi, and MjOi∈MOi reports its status information to its own operator Oi, and each M is connected to neighboring devices for multihop D2D communications. For the multiple access at every hop, we consider a OFDMA-based transmission, and communication capacity at each hop link is fixed [4, 11, 12]. The general infrastructure of operator-controlled D2D system is shown in Figure 1, and Table 1 lists the notations used in this paper.Figure 1
Operator-controlled D2D communication infrastructure.Table 1
Parameters used in the proposed algorithm.
Notations
Explanation
O
=
O
1
,
…
,
O
n
The set of wireless operators
M
O
i
=
M
1
O
i
,
…
,
M
m
O
i
The set of devices under the operatorOi∈O
M
k
O
,
M
l
O
The wireless link betweenMkO and MlO
g
M
k
O
The set ofMkO’s neighboring devices
ℰ
M
k
O
,
M
l
O
The communication cost degree of linkMkO,MlO
β
M
k
O
The interference parameter ofMkO
g
M
k
O
The cardinality ofgMkO
χ
The path loss exponent factor
ξ
The path interference factor
d
M
k
O
,
M
l
O
The distance betweenMkO and MlO
T
The multihop communication flow
s
T, dT
The source and destination device of flowT
M
The payment mechanism for the upper-level game
A
A set of possible outcomes from relay operators
R
T
The set of relay operators for theT relay service
A
A set of relay operators to establish a routing path
v
O
i
A
,
T
O
i’s value to a specific outcome A∈A
R
T
O
i
The set of relay devices under theOi for the T service
N
M
k
O
i
The next relay device ofMkOi
ℰ
M
k
O
i
,
N
M
k
O
i
α
M
k
O
i’s energy consumption to connect the NMkOi
v
^
A
,
T
The misreport of true valuation functionvA,T
I
O
i
·
The incentive payment ofOi
U
O
i
·
O
i’s utility function
C
O
i
·
The real cost function ofOi
v
^
−
O
i
·
A vector ofv except the OiDuring the D2D system operations, system agents, i.e., operators and mobile devices, make decisions individually. In this situation, a main issue for each agent is how to perform well by considering the mutual-interaction relationship. To formulate this relationship, we design a new dual-level game model. At the upper level, operatorsO1,…,On are game players and they establish routing paths while getting the relay service payment based on the IMD. At the lower level, mobile devices MO1,…,MOn are game players, and they share the service payment given by their corresponding operator according to the r-egalitarian Shapley value. For the implementation practicality, our lower-level games are carried out in an entirely distributed and parallel fashion. During the dual-level interaction, operators and mobile devices work together toward an appropriate system performance.LetMkO,MlO denote the wireless link between two neighboring devices MkO and MlO, and gMkO is denoted as the set of MkO’s neighboring devices where MlO∈gMkO. ℰMkO,MlO is the communication cost degree of link MkO,MlO for D2D communications [4].(1)ℰMkO,MlO=βMkO×dMkO,MlOχ,s.t.βMkO=gMkOξ,where βMkO is the interference parameter of MkO, and gMkO is the cardinality of gMkO. χ and ξ are the path loss exponent and interference factors, respectively. dMkO,MlO is the distance between MkO and MlO. Let T is the multihop communication flow, and the source and destination device of flow T is represented as sT and dT, respectively. T consists of multiple links, and mobile devices for these links can be covered by different operators [4]. Mobile devices estimate the ℰ· values of all available connection links and report this information to their corresponding operators. Therefore, each operator can recognize the device topology of its covering area; operators interact with each other to configure the large area, which is partially covered by other operators.If an operator includes asT (or dT) device, it is called as a source (or destination) operator. From the source operator to the destination operator, there can be some relay operators. Each relay operator reveals the total sum of ℰ· values about the relay links in its corresponding area; it can be interpreted as a relay cost of that operator. In this study, the source operator is responsible to collect all this information and configures a routing path through relay operators to reach the destination operator. Usually, all multihop D2D communication algorithms are designed by relying on the assumption that devices under relay operators willing to act as relay nodes in the multihop routing path. However, devices acting as relay nodes have to sacrifice their resources to forward data packets. Therefore, it is necessary to stimulate collaborative actions of relay devices toward a socially optimal outcome. During the upper-level game operation, we develop an incentive payment mechanism to guide selfish relay devices. Based on the IMD, the source device pays appropriate incentives for the relay operators. And then, each relay operator redistributes the given incentive to its corresponding relay devices. During the lower-level game operation, this incentive sharing problem is solved according to the r-egalitarian Shapley value.


### 2.2. Incentive Mechanism Design Based Upper-Level Game Model

In the upper-level game procedure, the main issue is to calculate the incentive payment. To develop an incentive payment algorithm for D2D communications, the key concern is how much a relay operator should be paid for the participation in relay services. In this paper, the basic concept of IMD is adopted to calculate the incentive payment for each relay operator. Usually, the IMD, also called reverse game theory, is a field in economics and game theory that takes an engineering approach toward desired objectives, where players act rationally. The main feature of IMD is that a game designer, who is interested in the game’s outcome, chooses the game structure to reach a social optimum. For a class of private-information games, IMD studies solution concepts of broad applications from economics and politics to network system management. However, the IMD has enjoyed much success only in static settings; it does not easily translate into an optimal mechanism for dynamic settings. In addition, the classic IMD literature largely ignores computational considerations [13, 14].From the viewpoint of strategic players, one natural objective in dynamic environments is maximizing the long-term social welfare of all players (optimality). With regards to optimal mechanisms in a dynamic setting, there are elegant extensions [13]. As a special case of traditional IMD, Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially optimal solution while being applicable to quite general dynamic settings. Especially, the VCG mechanism is strategy-proof, in the sense that the truthful reporting of player’s preference is always a dominant strategy. This property can provide a normative guide for the outcome and has better computational properties than the classical IMD approach [14].In the upper-level game model, the VCG mechanism is used to define a strategic situation to make the D2D system exhibit better performance when independent operators pursue self-interested strategies. LetM be our payment mechanism for the upper-level game, and A is denoted as a set of possible outcomes based on inputs from relay operators. RT represents the set of relay operators for the T traffic relay service. Each relay operator Oi∈RT has its valuation function vOiA,T, which quantifies Oi’s value to a specific outcome A∈A. Usually, vOiA,T maps A to a positive real number. In this study, this number represents Oi’s real contribution for the T relay service, and A is a set of relay operators to establish a routing path. Motivated by the basic idea of Dijkstra routing algorithm, A is given to establish the routing path while minimizing the total sum of vOiA,T values where Oi∈A. For the T relay service, Oi’s vOi⋅ function is defined as follows:(2)vOiA,T=∑MkOi∈RTOiℰMkOi,NMkOiα×IOi,s.t.IOi=1,ifOi∈A,IOi=0,otherwise,where RTOi is the set of relay mobile devices under the Oi for the T service, and NMkOi is the next relay device of MkOi. ℰMkOi,NMkOiα represents the MkOi’s energy consumption to connect the NMkOi. With the control parameter α, the ℰ· value polynomially increases related to the communication cost degree between MkOi and NMkOi.FromM, each relay operator is asked to report its valuation function vA,T and M decides an outcome A∈A by selecting relay operators to set a multihop D2D path route. At this moment, each relay operator can submit its function, which may or may not equal vA,T. Let v^A,T represent that an operator misreports its true valuation function vA,T, i.e., v^A,T≠vA,T. If M is the VCG mechanism, the outcome Av^,T∗ selected by M is(3)Av^,T∗≔argminA∑Ok∈Av^OkA,TA⟹sT|dT,s.t.v^=v^Ok∈AA,T,where A⟹sT∣dT means that A consists of relay operators to relay the T service from sT to dT. The incentive payment of Oi, i.e., IOiAv^∗,T, is defined as the profit that its presence causes others with respect to the reported v^Ok∈RT,Ok≠OiT [8]; formally,(4)IOiAv^∗,T=minA∑Oj≠Oiv^OjA−∑Oj≠Oiv^OjAv^∗,T.In equation (4), the first term is the total reported value the other operators would obtain when Oi is absent and the second term is the total reported value the others obtain when Oi is present. If Oi’s dominant strategy is to report its valuation truthfully, i.e., vOiA,T, we say that M is truthful [8]. Formally, it can be expressed as follows:(5)UOivOiA,T,v^−OiA,T≥UOiv^OiA,T,v^−OiA,T,s.t.UOivOiA,T,v^−OiA,T=IOivOiA,T,v^−OiA,T−COiA,T,UOiv^OiA,T,v^−OiA,T=IOiv^OiA,T,v^−OiA,T−COiA,T,v^−OiA,T=v^Ok∈RT,Ok≠OiA,T,where UOi· is Oi’s utility function and IOivOiA,T,v^−OiA,T is decided based on input vOiA,T and v^−OiA,T. v^−Oi· is a vector of v except Oi, and COiA,T is the real cost function of Oi. In this study, COiA,T is defined as the same manner as the communication cost degree. If the incentive payment for each relay operator is given according to (4), M is a truthful mechanism [8].Theorem 1.
M is a truthful mechanism for all relay operators.Proof.
We can fix the reportsv^−Oi of all relay operators except Oi. Suppose that Oi’s true valuation function is vOi⋅, and it can report its valuation function truthfully, i.e., vOi⋅, or untruthfully, i.e., v^Oj·.Case (I).
IfOi report its false valuation function v^Oj·, then the outcome of M is given by (3) and Oi’s incentive payment is given by (4). Based on this reason, Oi’s utility function can be defined as follows:(6)UOiv^OiAv^∗,T,v^−OiAv^∗,T=IOiv^OiAv^∗,T,v^−OiAv^∗,T−COiAv^∗,T=IOiAv^∗,T−COiAv^∗,T=argminA∑Oj≠Oiv^OjAA⟹sTdT−∑Oj≠Oiv^OjAv^∗,T−COiAv^∗,T.Case (II).
IfOi report truthfully its valuation function, i.e., vi⋅, then the outcome of M is given by(7)AvOi,v^−Oi,T′=argminAvOiA,T+∑Oj∈A,Oj≠Oiv^OjAA⟹sT|dT.
O
i’s incentive payment is(8)IOiAvOi,v^−Oi′,T=argminA∑Oj≠Oiv^OjAvOi,v^−Oi′,T−∑Oj≠Oiv^OjAvOi,v^−Oi′,T.
O
i’s utility function can be defined as follows:(9)UOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T=IOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T=IOiAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T=minA∑Oj≠Oiv^OjAvOi,v^−Oi′,T−∑Oj≠Oiv^OjAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T.
Finally,(10)UOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T−UOiv^OiAv^∗,T,v^−OiAv^∗,T=IOiAvOi,v^−Oi′,T−vOiAvOi,v^−Oi′,T−IOiAv^∗,T−vOiAv^∗,T=minA∑Oj≠Oiv^OjAvOi,v^−Oi′,T−∑Oj≠OivOiAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T−minA∑Oj≠Oiv^OjA+∑Oj≠Oiv^OjAv^∗,T+COiAv^∗,T.
O
i’s report has no influence on minA∑Oj≠Oiv^OjAvOi,v^−Oi′,T and minA∑Oj≠Oiv^OjA. Therefore, they are the same constant from the viewpoint of the player Oi. Therefore, the final equation (10) can be simplified as follows:(11)COiAv^∗,T+∑Oj≠Oiv^OjAv^∗,T−COiAvOi,v^−Oi′,T−∑Oj≠OivOiAvOi,v^−Oi′,T≥0≅UOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T≥UOiv^OiAv^∗,T,v^−OiAv^∗,T.
In conclusion, the value ofUOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T is always higher than the value of UOiv^OiAv^∗,T,v^−OiAv^∗,T for every v^, vOi, and Oi.


### 2.3. Lower-Level Game Model Based on the r-egalitarian Shapley Value

From the upper-level game, the incentives are paid by the source device to relay operators. In the lower-level game, each individual relay operator redistributes its given incentive to the corresponding relay devices to compensate the loss of relay devices. Commonsensically, mobile devices under a relay operator enter into a binding agreement to form a coalition if all relay devices are able to improve their individual payoffs. When some relay devices may contribute more to the coalition than others, the given incentive should be shared fairly and optimally among the relay devices. Therefore, the main concern in the lower-level game is to maintain the overall cooperation of delay devices while fair-efficiently share the given incentive. In the proposed scheme, we adopt another novel cooperative game solution to answer to this question.In 1953, L. Shapley characterized a solution concept that associates with canonical coalition games. This solution is known as the Shapley value. Throughsuper-additivity, it assigns a unique distribution among the players of a total surplus generated by the coalition of all players. Shapley also proved that the Shapley value can satisfy four axioms; (i) efficiency, (ii) symmetry, (iii) dummy, and (iv) additivity. The (i), (ii), and (iii) axioms are self-explanatory. To motivate the (iv) axiom, imagine the same players engage in two consecutive games. This axiom states that the outcome in one game should not affect the other, and thus, in the combined game, the allocation to a player is the sum of his allocations in the component games [7, 8].In 2018, Yokote et al. modified the concept of Shapley value and introduced the r-egalitarian Shapley valueEShr. It is characterized by some axioms that have the advantage of the original Shapley value. The solution EShr satisfies efficiency, weak covariance, and balanced contributions property for equal contributors axioms. To explain the axioms, we introduce some notations. Let (N,v) be a game with transferable utility, where N=a1,a2,…,an is the set of players and v is the characteristic function, which assigns a real number vC to every coalition C∈N where N is the set of nonempty subsets of N. A transferable utility game is a pair C,v consisting of a set of players C, and a coalition function v∈VC≔f:2C⟶R:f∅=0. With the C,v and S⊆C, S≠∅ , let S,v denote the game in which the domain of v is restricted from 2C to 2S, and the EShr of ai is EShair [15].(i)
Efficiency. For all (C,v), ∑ai∈CEShairC,v=vC; it divides the total payoff vC.(ii)
Weak Covariance. For all (C,v) and λ∈R, we define v+λ×uai∈VC by v+λ×uaiS=vS+λ×uaiS. Then, EShrC,v+λ×uaiS=EShrC,v+λ×EShrC,uai; this axiom leaves limited room for the treatment of ai’s contributions. Regarding uai, we require the outcome EShrC,λ×uai to be determined linearly from EShrC,uai.(iii)
Balanced Contributions Property for Equal Contributors. For all (C,v), ai,aj∈C and ai≠aj. If vC\ai=vC\aj, then EShairC,v−EShairC\aj,v=EShajrC,v−EShajrC\ai,v.Given the grand coalition form,EShr investigates the problem of how to distribute the total payoff among players fairly. The solution of EShr assigns a payoff vector EShai∈CrC,v∈R to each game C,v. To define EShr, the idea of rescaling the worth of coalitions is necessary [15]. Let L denote the set of finite sequences of real numbers:(12)L=Lkk=1N∣Lk∈Rfor allk∈1,…,N,where N represents the cardinality of N. According to (12) and r∈L, vrS is defined as(13)vrS=rs×vS,s.t.r∈L, for allS⊆C,S≠∅,vr∈VC.In the gamevr, the worth of each coalition is rescaled by multiplying the sth entry of the sequence vector r, where s is the size of coalition S. This type of rescaling is often discussed in the context of the per-capita measure or discounting; vr can be interpreted as generalizing these ideas by allowing for any sequence of real numbers [15]. Finally, the EShr is defined as follows:(14)EShai∈CrC,v=vC−vrCC+∑S⊂C,ai∈SXS,Cr×YS,air,s.t.XS,Cr=S−1!×C−S!C!,YS,air=vrS−vrS−ai,where XS,Cr can be interpreted as the probability of a coalition containing ai with the size of S and YS,air is the payoff difference between the coalitions with and without the ai, which measures the contribution of the ai to the coalition. According to XS,Cr and YS,air, the original Shapley value is obtained based on the vr game [7, 16]. Therefore, we can interpret EShair as (i) the worth of coalitions are rescaled based on the sequence vector r, (ii) an imaginary vr game is constructed, (iii) the Shapley value idea is applied to the vr game, and (iv) the gap between the vC and vrC is equally divided among players [15].In the lower-level game process, the given incentive of each relay operator is shared by corresponding relay devices. Therefore, relay devices are game players and form each coalition. In this study, the characteristic functionv for the coalition CvC is defined based on the bankruptcy problem in [17]. It is analogous to a distribution or entitlement problem by involving the allocation of a given amount of a perfectly divisible good. Therefore, we can effectively estimate vC values for all possible coalitions. Based on the bankruptcy problem and EShr, relay devices can share their incentive payment using equation (14); it is the most fair-efficient solution while satisfying EShr axioms.


### 2.4. Main Steps of Proposed Dual-Level D2D Communication Scheme

To effectively operate operator-controlled multihop D2D communications, the interactive relationship between operators and mobile devices is an important research topic and should be considered to design the control scheme. In this study, we provide the main D2D communication control method, which is modeled based on two cooperative game solutions, i.e., the IMD andEShr. Owing to our dual-level game model, the upper-level and lower-level game processes are hierarchically applied, and we can get the most fair-efficient system performance by combining both solution approaches. Periodically, our dual-level game-based D2D control method is operated for each multihop communication service T. The principle novelties of this study are a judicious mixture of two cooperation game solutions and its feasible self-adaptability of each D2D network agent, i.e., operators and mobile devices, in the real-world multihop D2D system operations.Usually, conventional optimization methods such as Lagrangian or dynamic programming require global objective functions with exponential time complexity; it is impractical to be implemented for realistic system operations. However, our dual-level game approach model can significantly reduce computational complexity based on the distributed lower-level game operations; it is an important feature of the proposed scheme. The main steps of the proposed scheme are described as follows.Step 1.
System factors and control parameters are determined by the simulation scenario (see simulation assumptions in Section3).Step 2.
All operators announce theirvO⋅ function values to connect their neighboring operators. Owing to the feature of VCG mechanism, relay operators truthfully announce their vO⋅ values.Step 3.
Multihop D2D communication service (T) is generated from the sT. At this time, the source operator including the sT finds out the destination operator including the dT while figuring out all possible relay operators.Step 4.
The source operator establishes the multihop D2D communication routeA, which can be consisting of multiple relay operators. According to the Dijkstra routing algorithm, this route is decided to minimize the total sum of all relay operators’ vO⋅ values.Step 5.
During the upper-level game process,sT pays the incentive payments IOT to relay operators using equation (4).Step 6.
During the lower-level game process, mobile relay devices under each individual relay operator inA share the given incentive payment IOAv^∗,T using equation (14). Owing to the feature of EShr, the IOAv^∗,T is shared fair-efficiently among relay mobile devices.Step 7.
In a distributed fashion, all relay operators execute their lower-level games in parallel. Therefore, we can significantly reduce the computation complexity to calculate theEShr. This approach is suitable for the practical implementation.Step 8.
Based on the dual-level game model, relay operators and mobile devices are hierarchically interconnected and interacting with one another to operate multihop D2D communications.Step 9.
Repeatedly,T is generated from another sT and proceeds to Step 3 for the next dual-level game procedure for the new D2D communication.


## 2.1. Operator-Controlled D2D Communication Infrastructure

In this study, we consider an operator-controlled D2D communication system consisting of a number of devices belonging to multiple operators. Mobile devices are randomly deployed within a large coverage area. In the operator-controlled D2D infrastructure, a geographic coverage area is subdivided and served by operators. Operators are connected each other through high-speed wired links to transfer the system control information, and mobile devices are connected their corresponding operators through wireless links. Due to the limited transmission power of each device, multihop relaying is adopted to route flow data communications from source mobile devices to destination mobile devices [4, 11]. Denote the set of operators as O=O1,…,On and MO1≤i≤n=M1Oi,…,MmOi is the set of devices under the operator Oi∈O. Oi is responsible to the devices in the set MOi, and MjOi∈MOi reports its status information to its own operator Oi, and each M is connected to neighboring devices for multihop D2D communications. For the multiple access at every hop, we consider a OFDMA-based transmission, and communication capacity at each hop link is fixed [4, 11, 12]. The general infrastructure of operator-controlled D2D system is shown in Figure 1, and Table 1 lists the notations used in this paper.Figure 1
Operator-controlled D2D communication infrastructure.Table 1
Parameters used in the proposed algorithm.
Notations
Explanation
O
=
O
1
,
…
,
O
n
The set of wireless operators
M
O
i
=
M
1
O
i
,
…
,
M
m
O
i
The set of devices under the operatorOi∈O
M
k
O
,
M
l
O
The wireless link betweenMkO and MlO
g
M
k
O
The set ofMkO’s neighboring devices
ℰ
M
k
O
,
M
l
O
The communication cost degree of linkMkO,MlO
β
M
k
O
The interference parameter ofMkO
g
M
k
O
The cardinality ofgMkO
χ
The path loss exponent factor
ξ
The path interference factor
d
M
k
O
,
M
l
O
The distance betweenMkO and MlO
T
The multihop communication flow
s
T, dT
The source and destination device of flowT
M
The payment mechanism for the upper-level game
A
A set of possible outcomes from relay operators
R
T
The set of relay operators for theT relay service
A
A set of relay operators to establish a routing path
v
O
i
A
,
T
O
i’s value to a specific outcome A∈A
R
T
O
i
The set of relay devices under theOi for the T service
N
M
k
O
i
The next relay device ofMkOi
ℰ
M
k
O
i
,
N
M
k
O
i
α
M
k
O
i’s energy consumption to connect the NMkOi
v
^
A
,
T
The misreport of true valuation functionvA,T
I
O
i
·
The incentive payment ofOi
U
O
i
·
O
i’s utility function
C
O
i
·
The real cost function ofOi
v
^
−
O
i
·
A vector ofv except the OiDuring the D2D system operations, system agents, i.e., operators and mobile devices, make decisions individually. In this situation, a main issue for each agent is how to perform well by considering the mutual-interaction relationship. To formulate this relationship, we design a new dual-level game model. At the upper level, operatorsO1,…,On are game players and they establish routing paths while getting the relay service payment based on the IMD. At the lower level, mobile devices MO1,…,MOn are game players, and they share the service payment given by their corresponding operator according to the r-egalitarian Shapley value. For the implementation practicality, our lower-level games are carried out in an entirely distributed and parallel fashion. During the dual-level interaction, operators and mobile devices work together toward an appropriate system performance.LetMkO,MlO denote the wireless link between two neighboring devices MkO and MlO, and gMkO is denoted as the set of MkO’s neighboring devices where MlO∈gMkO. ℰMkO,MlO is the communication cost degree of link MkO,MlO for D2D communications [4].(1)ℰMkO,MlO=βMkO×dMkO,MlOχ,s.t.βMkO=gMkOξ,where βMkO is the interference parameter of MkO, and gMkO is the cardinality of gMkO. χ and ξ are the path loss exponent and interference factors, respectively. dMkO,MlO is the distance between MkO and MlO. Let T is the multihop communication flow, and the source and destination device of flow T is represented as sT and dT, respectively. T consists of multiple links, and mobile devices for these links can be covered by different operators [4]. Mobile devices estimate the ℰ· values of all available connection links and report this information to their corresponding operators. Therefore, each operator can recognize the device topology of its covering area; operators interact with each other to configure the large area, which is partially covered by other operators.If an operator includes asT (or dT) device, it is called as a source (or destination) operator. From the source operator to the destination operator, there can be some relay operators. Each relay operator reveals the total sum of ℰ· values about the relay links in its corresponding area; it can be interpreted as a relay cost of that operator. In this study, the source operator is responsible to collect all this information and configures a routing path through relay operators to reach the destination operator. Usually, all multihop D2D communication algorithms are designed by relying on the assumption that devices under relay operators willing to act as relay nodes in the multihop routing path. However, devices acting as relay nodes have to sacrifice their resources to forward data packets. Therefore, it is necessary to stimulate collaborative actions of relay devices toward a socially optimal outcome. During the upper-level game operation, we develop an incentive payment mechanism to guide selfish relay devices. Based on the IMD, the source device pays appropriate incentives for the relay operators. And then, each relay operator redistributes the given incentive to its corresponding relay devices. During the lower-level game operation, this incentive sharing problem is solved according to the r-egalitarian Shapley value.


## 2.2. Incentive Mechanism Design Based Upper-Level Game Model

In the upper-level game procedure, the main issue is to calculate the incentive payment. To develop an incentive payment algorithm for D2D communications, the key concern is how much a relay operator should be paid for the participation in relay services. In this paper, the basic concept of IMD is adopted to calculate the incentive payment for each relay operator. Usually, the IMD, also called reverse game theory, is a field in economics and game theory that takes an engineering approach toward desired objectives, where players act rationally. The main feature of IMD is that a game designer, who is interested in the game’s outcome, chooses the game structure to reach a social optimum. For a class of private-information games, IMD studies solution concepts of broad applications from economics and politics to network system management. However, the IMD has enjoyed much success only in static settings; it does not easily translate into an optimal mechanism for dynamic settings. In addition, the classic IMD literature largely ignores computational considerations [13, 14].From the viewpoint of strategic players, one natural objective in dynamic environments is maximizing the long-term social welfare of all players (optimality). With regards to optimal mechanisms in a dynamic setting, there are elegant extensions [13]. As a special case of traditional IMD, Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially optimal solution while being applicable to quite general dynamic settings. Especially, the VCG mechanism is strategy-proof, in the sense that the truthful reporting of player’s preference is always a dominant strategy. This property can provide a normative guide for the outcome and has better computational properties than the classical IMD approach [14].In the upper-level game model, the VCG mechanism is used to define a strategic situation to make the D2D system exhibit better performance when independent operators pursue self-interested strategies. LetM be our payment mechanism for the upper-level game, and A is denoted as a set of possible outcomes based on inputs from relay operators. RT represents the set of relay operators for the T traffic relay service. Each relay operator Oi∈RT has its valuation function vOiA,T, which quantifies Oi’s value to a specific outcome A∈A. Usually, vOiA,T maps A to a positive real number. In this study, this number represents Oi’s real contribution for the T relay service, and A is a set of relay operators to establish a routing path. Motivated by the basic idea of Dijkstra routing algorithm, A is given to establish the routing path while minimizing the total sum of vOiA,T values where Oi∈A. For the T relay service, Oi’s vOi⋅ function is defined as follows:(2)vOiA,T=∑MkOi∈RTOiℰMkOi,NMkOiα×IOi,s.t.IOi=1,ifOi∈A,IOi=0,otherwise,where RTOi is the set of relay mobile devices under the Oi for the T service, and NMkOi is the next relay device of MkOi. ℰMkOi,NMkOiα represents the MkOi’s energy consumption to connect the NMkOi. With the control parameter α, the ℰ· value polynomially increases related to the communication cost degree between MkOi and NMkOi.FromM, each relay operator is asked to report its valuation function vA,T and M decides an outcome A∈A by selecting relay operators to set a multihop D2D path route. At this moment, each relay operator can submit its function, which may or may not equal vA,T. Let v^A,T represent that an operator misreports its true valuation function vA,T, i.e., v^A,T≠vA,T. If M is the VCG mechanism, the outcome Av^,T∗ selected by M is(3)Av^,T∗≔argminA∑Ok∈Av^OkA,TA⟹sT|dT,s.t.v^=v^Ok∈AA,T,where A⟹sT∣dT means that A consists of relay operators to relay the T service from sT to dT. The incentive payment of Oi, i.e., IOiAv^∗,T, is defined as the profit that its presence causes others with respect to the reported v^Ok∈RT,Ok≠OiT [8]; formally,(4)IOiAv^∗,T=minA∑Oj≠Oiv^OjA−∑Oj≠Oiv^OjAv^∗,T.In equation (4), the first term is the total reported value the other operators would obtain when Oi is absent and the second term is the total reported value the others obtain when Oi is present. If Oi’s dominant strategy is to report its valuation truthfully, i.e., vOiA,T, we say that M is truthful [8]. Formally, it can be expressed as follows:(5)UOivOiA,T,v^−OiA,T≥UOiv^OiA,T,v^−OiA,T,s.t.UOivOiA,T,v^−OiA,T=IOivOiA,T,v^−OiA,T−COiA,T,UOiv^OiA,T,v^−OiA,T=IOiv^OiA,T,v^−OiA,T−COiA,T,v^−OiA,T=v^Ok∈RT,Ok≠OiA,T,where UOi· is Oi’s utility function and IOivOiA,T,v^−OiA,T is decided based on input vOiA,T and v^−OiA,T. v^−Oi· is a vector of v except Oi, and COiA,T is the real cost function of Oi. In this study, COiA,T is defined as the same manner as the communication cost degree. If the incentive payment for each relay operator is given according to (4), M is a truthful mechanism [8].Theorem 1.
M is a truthful mechanism for all relay operators.Proof.
We can fix the reportsv^−Oi of all relay operators except Oi. Suppose that Oi’s true valuation function is vOi⋅, and it can report its valuation function truthfully, i.e., vOi⋅, or untruthfully, i.e., v^Oj·.Case (I).
IfOi report its false valuation function v^Oj·, then the outcome of M is given by (3) and Oi’s incentive payment is given by (4). Based on this reason, Oi’s utility function can be defined as follows:(6)UOiv^OiAv^∗,T,v^−OiAv^∗,T=IOiv^OiAv^∗,T,v^−OiAv^∗,T−COiAv^∗,T=IOiAv^∗,T−COiAv^∗,T=argminA∑Oj≠Oiv^OjAA⟹sTdT−∑Oj≠Oiv^OjAv^∗,T−COiAv^∗,T.Case (II).
IfOi report truthfully its valuation function, i.e., vi⋅, then the outcome of M is given by(7)AvOi,v^−Oi,T′=argminAvOiA,T+∑Oj∈A,Oj≠Oiv^OjAA⟹sT|dT.
O
i’s incentive payment is(8)IOiAvOi,v^−Oi′,T=argminA∑Oj≠Oiv^OjAvOi,v^−Oi′,T−∑Oj≠Oiv^OjAvOi,v^−Oi′,T.
O
i’s utility function can be defined as follows:(9)UOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T=IOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T=IOiAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T=minA∑Oj≠Oiv^OjAvOi,v^−Oi′,T−∑Oj≠Oiv^OjAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T.
Finally,(10)UOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T−UOiv^OiAv^∗,T,v^−OiAv^∗,T=IOiAvOi,v^−Oi′,T−vOiAvOi,v^−Oi′,T−IOiAv^∗,T−vOiAv^∗,T=minA∑Oj≠Oiv^OjAvOi,v^−Oi′,T−∑Oj≠OivOiAvOi,v^−Oi′,T−COiAvOi,v^−Oi′,T−minA∑Oj≠Oiv^OjA+∑Oj≠Oiv^OjAv^∗,T+COiAv^∗,T.
O
i’s report has no influence on minA∑Oj≠Oiv^OjAvOi,v^−Oi′,T and minA∑Oj≠Oiv^OjA. Therefore, they are the same constant from the viewpoint of the player Oi. Therefore, the final equation (10) can be simplified as follows:(11)COiAv^∗,T+∑Oj≠Oiv^OjAv^∗,T−COiAvOi,v^−Oi′,T−∑Oj≠OivOiAvOi,v^−Oi′,T≥0≅UOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T≥UOiv^OiAv^∗,T,v^−OiAv^∗,T.
In conclusion, the value ofUOivOiAvOi,v^−Oi′,T,v^−OiAvOi,v^−Oi′,T is always higher than the value of UOiv^OiAv^∗,T,v^−OiAv^∗,T for every v^, vOi, and Oi.


## 2.3. Lower-Level Game Model Based on the r-egalitarian Shapley Value

From the upper-level game, the incentives are paid by the source device to relay operators. In the lower-level game, each individual relay operator redistributes its given incentive to the corresponding relay devices to compensate the loss of relay devices. Commonsensically, mobile devices under a relay operator enter into a binding agreement to form a coalition if all relay devices are able to improve their individual payoffs. When some relay devices may contribute more to the coalition than others, the given incentive should be shared fairly and optimally among the relay devices. Therefore, the main concern in the lower-level game is to maintain the overall cooperation of delay devices while fair-efficiently share the given incentive. In the proposed scheme, we adopt another novel cooperative game solution to answer to this question.In 1953, L. Shapley characterized a solution concept that associates with canonical coalition games. This solution is known as the Shapley value. Throughsuper-additivity, it assigns a unique distribution among the players of a total surplus generated by the coalition of all players. Shapley also proved that the Shapley value can satisfy four axioms; (i) efficiency, (ii) symmetry, (iii) dummy, and (iv) additivity. The (i), (ii), and (iii) axioms are self-explanatory. To motivate the (iv) axiom, imagine the same players engage in two consecutive games. This axiom states that the outcome in one game should not affect the other, and thus, in the combined game, the allocation to a player is the sum of his allocations in the component games [7, 8].In 2018, Yokote et al. modified the concept of Shapley value and introduced the r-egalitarian Shapley valueEShr. It is characterized by some axioms that have the advantage of the original Shapley value. The solution EShr satisfies efficiency, weak covariance, and balanced contributions property for equal contributors axioms. To explain the axioms, we introduce some notations. Let (N,v) be a game with transferable utility, where N=a1,a2,…,an is the set of players and v is the characteristic function, which assigns a real number vC to every coalition C∈N where N is the set of nonempty subsets of N. A transferable utility game is a pair C,v consisting of a set of players C, and a coalition function v∈VC≔f:2C⟶R:f∅=0. With the C,v and S⊆C, S≠∅ , let S,v denote the game in which the domain of v is restricted from 2C to 2S, and the EShr of ai is EShair [15].(i)
Efficiency. For all (C,v), ∑ai∈CEShairC,v=vC; it divides the total payoff vC.(ii)
Weak Covariance. For all (C,v) and λ∈R, we define v+λ×uai∈VC by v+λ×uaiS=vS+λ×uaiS. Then, EShrC,v+λ×uaiS=EShrC,v+λ×EShrC,uai; this axiom leaves limited room for the treatment of ai’s contributions. Regarding uai, we require the outcome EShrC,λ×uai to be determined linearly from EShrC,uai.(iii)
Balanced Contributions Property for Equal Contributors. For all (C,v), ai,aj∈C and ai≠aj. If vC\ai=vC\aj, then EShairC,v−EShairC\aj,v=EShajrC,v−EShajrC\ai,v.Given the grand coalition form,EShr investigates the problem of how to distribute the total payoff among players fairly. The solution of EShr assigns a payoff vector EShai∈CrC,v∈R to each game C,v. To define EShr, the idea of rescaling the worth of coalitions is necessary [15]. Let L denote the set of finite sequences of real numbers:(12)L=Lkk=1N∣Lk∈Rfor allk∈1,…,N,where N represents the cardinality of N. According to (12) and r∈L, vrS is defined as(13)vrS=rs×vS,s.t.r∈L, for allS⊆C,S≠∅,vr∈VC.In the gamevr, the worth of each coalition is rescaled by multiplying the sth entry of the sequence vector r, where s is the size of coalition S. This type of rescaling is often discussed in the context of the per-capita measure or discounting; vr can be interpreted as generalizing these ideas by allowing for any sequence of real numbers [15]. Finally, the EShr is defined as follows:(14)EShai∈CrC,v=vC−vrCC+∑S⊂C,ai∈SXS,Cr×YS,air,s.t.XS,Cr=S−1!×C−S!C!,YS,air=vrS−vrS−ai,where XS,Cr can be interpreted as the probability of a coalition containing ai with the size of S and YS,air is the payoff difference between the coalitions with and without the ai, which measures the contribution of the ai to the coalition. According to XS,Cr and YS,air, the original Shapley value is obtained based on the vr game [7, 16]. Therefore, we can interpret EShair as (i) the worth of coalitions are rescaled based on the sequence vector r, (ii) an imaginary vr game is constructed, (iii) the Shapley value idea is applied to the vr game, and (iv) the gap between the vC and vrC is equally divided among players [15].In the lower-level game process, the given incentive of each relay operator is shared by corresponding relay devices. Therefore, relay devices are game players and form each coalition. In this study, the characteristic functionv for the coalition CvC is defined based on the bankruptcy problem in [17]. It is analogous to a distribution or entitlement problem by involving the allocation of a given amount of a perfectly divisible good. Therefore, we can effectively estimate vC values for all possible coalitions. Based on the bankruptcy problem and EShr, relay devices can share their incentive payment using equation (14); it is the most fair-efficient solution while satisfying EShr axioms.


## 2.4. Main Steps of Proposed Dual-Level D2D Communication Scheme

To effectively operate operator-controlled multihop D2D communications, the interactive relationship between operators and mobile devices is an important research topic and should be considered to design the control scheme. In this study, we provide the main D2D communication control method, which is modeled based on two cooperative game solutions, i.e., the IMD andEShr. Owing to our dual-level game model, the upper-level and lower-level game processes are hierarchically applied, and we can get the most fair-efficient system performance by combining both solution approaches. Periodically, our dual-level game-based D2D control method is operated for each multihop communication service T. The principle novelties of this study are a judicious mixture of two cooperation game solutions and its feasible self-adaptability of each D2D network agent, i.e., operators and mobile devices, in the real-world multihop D2D system operations.Usually, conventional optimization methods such as Lagrangian or dynamic programming require global objective functions with exponential time complexity; it is impractical to be implemented for realistic system operations. However, our dual-level game approach model can significantly reduce computational complexity based on the distributed lower-level game operations; it is an important feature of the proposed scheme. The main steps of the proposed scheme are described as follows.Step 1.
System factors and control parameters are determined by the simulation scenario (see simulation assumptions in Section3).Step 2.
All operators announce theirvO⋅ function values to connect their neighboring operators. Owing to the feature of VCG mechanism, relay operators truthfully announce their vO⋅ values.Step 3.
Multihop D2D communication service (T) is generated from the sT. At this time, the source operator including the sT finds out the destination operator including the dT while figuring out all possible relay operators.Step 4.
The source operator establishes the multihop D2D communication routeA, which can be consisting of multiple relay operators. According to the Dijkstra routing algorithm, this route is decided to minimize the total sum of all relay operators’ vO⋅ values.Step 5.
During the upper-level game process,sT pays the incentive payments IOT to relay operators using equation (4).Step 6.
During the lower-level game process, mobile relay devices under each individual relay operator inA share the given incentive payment IOAv^∗,T using equation (14). Owing to the feature of EShr, the IOAv^∗,T is shared fair-efficiently among relay mobile devices.Step 7.
In a distributed fashion, all relay operators execute their lower-level games in parallel. Therefore, we can significantly reduce the computation complexity to calculate theEShr. This approach is suitable for the practical implementation.Step 8.
Based on the dual-level game model, relay operators and mobile devices are hierarchically interconnected and interacting with one another to operate multihop D2D communications.Step 9.
Repeatedly,T is generated from another sT and proceeds to Step 3 for the next dual-level game procedure for the new D2D communication.


## 3. Simulation Results and Discussion

In this section, we perform simulations to examine the performance of our proposed protocol, and compare it with that of theCPD2D [4], RAD2D [9], and CAD2D [10] schemes. To ensure a fair comparison, we have considered the following assumptions and scenarios.(i)
Simulated operator-controlled D2D communication system covers a cellular area of 500 × 500 meter square(ii)
There are 10 operators; they can cover to within a 150-meter radius; they are laid out in regular pattern(iii)
There are 100 mobile devices; they are randomly located in the cellular area(iv)
Multihop communication service request rate is Poisson process (ρ). The offered rate range is varied from 0 to 3.0(v)
We assume that there are no physical obstacles in the experiments and each mobile device has enough bandwidth capacity for relay services(vi)
Network performance measures obtained on the basis of 100 simulation runs are plotted as functions of the offered multihop service request rate (ρ).(vii)
We setχ=1.2, ξ=0.7, and α=1.1 in this simulation study; they represent the path loss exponent, interference factor for a wireless link, and a control parameter to polynomially increase the cost degree, respectively.(viii)
Performance criteria obtained through simulation are system throughput, the fairness among operators, and mobile devices; these simulation metrics are evaluated mainly to demonstrate the validity of our proposed method.The result of throughput comparisons for multihop D2D systems is displayed in Figure2. In this study, system throughput is the ratio of successful data delivery over multihop D2D communications. We measure this performance metric to show and determine whether our dual-level game approach can well orchestrate the operator-controlled D2D communication infrastructure to maximize the system performance. As expected, the system throughput of each scheme tends to increases as D2D communication service request rates increases; it is intuitively correct. The resulting curves allow us to see that our proposed scheme has gained a better system throughput than other existing schemes. It is therefore worth to say that, under different service request rate conditions, our dual-level game based self-controlled management policies can perform excellently to maintain the stable performance superiority.Figure 2
Multihop D2D system throughput.Figure3 plots the fairness comparison among operators in the D2D system. To characterize the fairness notion, we follow the main concept of Raj Jain’s fairness index, which is varied from 0 to 1; 1 is the best case for fairness. It is given by [18](15)Jindex=∑Oi∈OγOi∈OA,T2O×∑Oi∈OγOi∈OA,T2,s.t.γOi∈OA,T=IOiA,TCOiA,T.Figure 3
The fairness among Operators.Following the main features of IMD, our upper-level game procedure can balance well the ratio of D2D relay contribution to incentive payment in each operator. Therefore, under diversified service request conditions, the proposed scheme can maintain significantly higherJindex values than the CPD2D, RAD2D, and CAD2D schemes. It is a highly desirable property for multihop D2D communication operations. To our knowledge, this result has not been made without explicitly adopting a truthful incentive mechanism for relay operators.Figure4 depicts the fairness comparison among mobile devices in each relay operator. It is also estimated based on the Jindex in equation (15). As can be seen, the fairness among mobile devices is very similar to the performance trend in Figure 3. In the proposed scheme, mobile devices in each relay operator share the given incentive payment according to the EShr. If the fairness concept is not considered obviously at the design stage of lower-level game process, the γ values of each mobile device are dissimilar significantly. It causes lower Jindex values. Simulation results have shown clearly that our proposed scheme can effectively assign the incentive payments to relay mobile devices while ensuring the fairness among mobile devices. In particular, the EShr method can compensate the actual contributions of relay devices with the axiom of balanced contributions property for equal contributors. Therefore, we attain a higher fairness for mobile devices compared to other existing schemes.Figure 4
The fairness among mobile devices.


## 4. Summary and Conclusions

To meet the growing demands of traffic services, a constant need to increase the network capacity has led to the evolution of D2D communications in 5G networks. In a conventional D2D communication system, devices are not allowed to communicate with each other through multihop connections. This paper proposes a novel operator-assisted multihop D2D communication scheme. The role of operators is to coordinate mobile devices in a distributed manner while getting the incentive payment from the source device. To induce selfish mobile devices to participate in multihop D2D communications, we adopt two cooperative game solutions; IMD andEShr. These two solution methods mutually interact with each other in our dual-level game model, and we can formulate a win-win situation for multihop D2D communication services. Therefore, in the proposed scheme, operators and mobile devices reciprocally work together toward an appropriate system performance. Based on the simulation result analysis, we demonstrate that our dual-level game approach is effective and efficient comparing to the existing CPD2D, RAD2D, and CAD2D schemes. As directions for future research, we aim at investigating the privacy and energy issues for multihop D2D communications. In addition, we plan to develop a new mechanism design with theoretical analysis. It will be a potential direction and another possible extension to this work.



---

*Source: 6276872-2019-07-04.xml*