1. Introduction
The standard solution for supporting multicast services in Long Term EvolutionAdvanced (LTEA) networks suffers from severe inefficiencies [
1], as the conventional cellular multicast performance is strictly bounded by the user with the poorest channel conditions. For this reason, researchers are active in studying solutions to enhance the multicast services performance in cellular systems [
1]. Among many alternatives, another new paradigm within LTEA systems, namely DevicetoDevice (D2D) communications [
2], has become a flourishing research field. D2D communication is about enabling direct flow of data among User Equipments (UEs) in close proximity, it holds merit of data offloading for the eNodeB (eNB), improving spectrum efficiency, and increasing system capacity [
2,
3,
4],
etc. These observations led us to the idea of bringing D2D communications into the cellular multicast services framework, and investigating the potentialities of adopting D2D communications to enhance the performance of conventional multicast services.
In LTEA networks, UEs requesting the same data from eNB can be grouped into a cluster and eNB multicasts data to all UEs within the cluster. The major issue in cellular multicast transmissions is the different channel conditions for the multicast recipients. Alternatively in D2Dassisted networks, UEs with good channel conditions are enabled to act as relays to communicate the received multicast data from the eNB to the remaining UEs via D2D links, such that the eNB can multicast at a high data rate and the transmission efficiency is improved. Based on this idea, in [
5] the authors proposed a cooperative multicast transmission scheme,
i.e., in which all successful multicast recipients participate in D2D relay transmissions by broadcasting their received data on the same resource. Because each D2D relay should serve all failed multicast recipients at a common rate selected according to the worst D2D link, it is unfavorable to improve the network throughput. In [
6] the authors assumed a single predefined multicast recipient called cluster head which is responsible for D2D relay transmissions. Unfortunately the efficiency of this scheme is not guaranteed in case the predesignated recipient fails to receive multicast data and the eNB must participate in retransmissions. In [
7] the authors proposed an adaptive D2D retransmission scheme exploiting the multichannel diversity to improve spectrum, which adaptively selects the optimal number of D2D retransmitters and conducts the optimal subcluster partition. Furthermore, in [
8] authors introduced relay based transmission into the multicast process so as to overcome transmission rate restriction caused by link heterogeneity, and a greedy heuristic algorithm was applied to select relay nodes. According to the these works, to improve the transmission quality of intracluster multicast service, a high efficient relay selection should be considered in the D2D cluster.
In this paper we consider an auctionbased approach using game theory. A combinatorial auction (CA) model for resource management was introduced in [
9]. Combinatorial auctions are multiitem or multibidder auctions in which bidders can form combinations called packages, rather than just bid individually. Furthermore, in the evolution auction mechanisms named iterative combinatorial auctions [
10], the step of bid evaluation is executed multiple times, and the auctioneer computes provisional allocations in each auction round. Iterative CAs have already found applications in allocating radio spectrum for wireless communications [
11]. The CAs motivate bidders to fully express their preferences, which is an advantage in improving system efficiency and auction revenues. Up to that point, we study an effective D2D relay selection for multicast services to further improve system efficiency based on the iterative CA. The whole system consists of the eNB, multiple successful multicast recipients, and multiple failed multicast recipients. Considering that an efficient exploitation of multichannel diversity may bring large beneficial to system throughout, we formulate the problem as a CA game. By this way, the failed multicast recipients and the successful multicast recipients are regarded as bidders and goods, respectively, while the successful multicast recipients are goods waiting to be selected as relays. Each bidder has a valuation for the relays, and multiple bidders can form a package that share the same relay. During the auction, the bidders submit bids and the auctioneer,
i.e., the eNB decides the allocation of the relays. Furthermore, we propose an auction algorithm which runs iteratively until reaching an equilibrium state. We also discuss the properties of our algorithm and the simulation results show a good performance on the sum data rate and system efficiency.
The rest of the paper is organized as follows. In
Section 2, a system model of intracluster D2D communication is introduced. Then we formulate the primary problem as a CA game in
Section 3. Next, in
Section 4, the CA algorithm for D2D relay selection is proposed, and the main properties of the proposed algorithm are discussed. In
Section 5, we present the simulation results. Finally, we conclude this paper in
Section 6.
2. System Model
We consider a singlecell multicast system where an eNB serves numerous UEs and the UEs in close proximity can group into a cluster to request the same data from eNB. The UEs within a cluster can not only communicate with eNB, but also directly communicate with each other via D2D links. Let us focus on one D2D cluster, as illustrated in
Figure 1. Due to independent properties of cellular downlink channels, when the eNB multicasts data to all UEs within a D2D cluster at a certain rate, only a portion of the UEs can correctly receive and decode the data. The UEs that can and cannot successfully receive data are referred to as “ACKUEs” and “NACKUEs”, respectively. In order to share the data from eNB in the whole cluster, ACKUEs can be employed as relays to forward the received data to NACKUEs via D2D links. In general, the underlined intracluster relay transmissions can be accomplished via D2D multicast. Meanwhile, to avoid the interference between D2D communication and cellular communication, orthogonal resources should be allocated to them.
Figure 1.
D2D clusters with ACKUEs and NACKUEs in the cellular network.
Figure 1.
D2D clusters with ACKUEs and NACKUEs in the cellular network.
In the paper, we only consider both largescale pathloss attenuation and smallscale fading characterized by Rayleigh fading, and thus the channel response follows the independent complex Gaussian distribution. In addition, the free space propagation pathloss model,
$P={P}_{0}\cdot {(d/{d}_{0})}^{\alpha}$, is used where
${P}_{0}$
and
$P$
represent signal power measured at
${d}_{0}$
and
$d$
meters away from the transmitter, respectively.
$\mathsf{\alpha}$
is a pathloss exponent. We simplify the received power at
${d}_{0}=1$
equals the transmit power. Hence, the received power of each D2D link can be expressed as.
where
${P}_{r,ij}$
and
${d}_{ij}$
are the received power and the distance of the
i–
j link.
${P}_{i}$
represents the transmit power of UE
$i$, and
${h}_{0}$
is the complex Gaussian channel coefficient that obeys the distribution
$\mathcal{C}\mathcal{N}\left(0,1\right)$. Given the power spectral density of the additive Gaussian noise
${\sigma}^{2}$
and system bandwidth
${W}_{c}$, according to Shannon formula, the channel rate of UE
j can be obtained by.
We define
${\mathcal{N}}_{\text{NACK}}$
is the set of NACKUEs and
${\mathcal{N}}_{\text{ACK}}$
is the set of ACKUEs. The numbers of NACKUEs and ACKUEs in the cluster are denoted as
${N}_{\text{NACK}}$
and
${N}_{\text{ACK}}$, respectively. Besides, inspired by [
7], we assume there are
$L$
ACKUEs acting as relays. For a given relay, the achievable D2D multicast rate depends on the worst link among all links connecting it with all NACKUEs. By optimizing selecting of a D2D relay, the system sum data rate can be defined as
where
${n}_{i}$ $\left(i=1,2,\mathrm{...},L\right)$
stands for the index of an ACKUE acting as the
ith D2D relay. The optimal D2D relay selection is performed under constraints
${n}_{i}\in {\mathcal{N}}_{\text{ACK}},{n}_{1}\ne {n}_{2}\ne \cdots {n}_{L}$, and
${\mathcal{N}}_{{n}_{1}}\cup \cdots {\mathcal{N}}_{{n}_{L}}={\mathcal{N}}_{\text{NACK}}$, to guarantee that each NACKUE in the cluster should be served by one relay. Although Equation (3) gives a generic solution, this optimization problem is very complicated in general. Therefore, it is necessary to design a relay selection mechanism that is not only computationally tractable, but also able to sustain high system efficiency.
3. Problem Formulation
In the proposed D2D cluster, system sum data rate is considered as the central optimization problem. As ACKUEs are selected as relays to serve NACKUEs, the contributions to system data rate are various due to heterogeneity of the D2D links between relays and NACKUEs. Therefore, in order to optimize the system performance, we focus on the how NACKUEs are effectively allocated to ACKUEs for the sake of relay services.
In this section, based on Equation (3), we can model the D2D relay selection process as a CA game. In this auction, NACKUEs are considered as the bidders who bid to get a certain item, i.e., ACKUE, while the eNB is the auctioneer. Since multiple NACKUEs can be served by one D2D relay, the packages of NACKUEs can form combinatorial bidders. We denote
${\mathcal{N}}_{\text{NACK}}=\{{b}_{1},{b}_{2},\mathrm{...},{b}_{N}\}$
as the set of bidders participating in the auction
$(\left{\mathcal{N}}_{\text{NACK}}\right=N)$
and denote
${b}_{k}\in {\mathcal{N}}_{\text{NACK}}$
as a specific bidder. Similarly, we denote
${\mathcal{N}}_{\text{ACK}}=\{{i}_{1},{i}_{2},\mathrm{...},{i}_{M}\}$
as the set of items to be auctioned
$(\left{\mathcal{N}}_{\text{ACK}}\right=M)$
and denote
${i}_{m}\in {\mathcal{N}}_{\text{ACK}}$
as a specific item. We also denote the set of all possible NACKUEs packages by $\mathcal{D}=({\mathcal{D}}_{1},{\mathcal{D}}_{2},\mathrm{...},{\mathcal{D}}_{M})$, in which an element package is expressed as ${\mathcal{D}}_{m},m=1,2,\mathrm{...},M$ in correspondence with the mth ACKUE. The possible packages are subsets of NACKUEs. By using
$\mathcal{D}$, we can transform the optimization problem in Equation (3) into a package assignment process. We consider a set of binary variables
$\{{x}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m})\}$
to define the allocation,
${x}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m})\in \{0,1\}$.
${x}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m})=1$
indicates that NACKUE
${b}_{k}$
bidding for ACKUE
${i}_{m}$
is assigned into package
${\mathcal{D}}_{m}$. In the auction, the goal of the eNB is to maximize the total revenue by selling ACKUEs. Meanwhile, each NACKUE targets at purchasing the item to maximize its own package utility.
In order to describe the allocation outcome intuitively, we give the definition below.
Definition 1. The result of the auction is an allocation denoted by$X=({\mathcal{D}}_{1},{\mathcal{D}}_{2},\mathrm{...},{\mathcal{D}}_{M})$, which allocates a corresponding bidder package to every item. And the allocated packages are not intersect: $\forall i,j,{\mathcal{D}}_{i}\cap {\mathcal{D}}_{j}=\varnothing $.
To motivate the bidders to reveal their true preferences, we express NACKUE
${b}_{k}$’s valuation for ACKUE
${i}_{m}$
as channel data rate
${R}_{{b}_{k},{i}_{m}}$. Then, the private valuation of package
${\mathcal{D}}_{m}$
can be expressed as:
Although the NACKUEs obtains D2D data rate by getting a D2D relay service of ACKUE, there exists some cost such as control signals transmission and information feedback during the relay selection process. We define the cost as a pay price. For ACKUE
${i}_{m}$, the pay price by the NACKUE
${b}_{k}$
in package
${\mathcal{D}}_{m}$
is written as
${p}_{{b}_{k}}({\mathcal{D}}_{m})$. Based on Equation (4), the combinatorial utility of the bidder can be expressed as ${\pi}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m},\mathcal{P})={\upsilon}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m}){\displaystyle {\sum}_{{b}_{k}\in {\mathcal{D}}_{m}}{p}_{{b}_{k}}({\mathcal{D}}_{m})}$, in which $\mathcal{P}$
is the price set, i.e., $\mathcal{P}=\{{p}_{{b}_{k}}({\mathcal{D}}_{m}),\forall m,{b}_{k}\in {\mathcal{D}}_{m}\}$. Then We define the allocation vector as
$X=[{x}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m}):\forall m,{b}_{k}\in {\mathcal{D}}_{m}]$, then the auctioneer (the eNB) revenue can be expressed as
$\Pi (X,\mathcal{P})={\displaystyle {\sum}_{{b}_{k},{\mathcal{D}}_{m}}[{x}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m}){\displaystyle {\sum}_{{b}_{k}\in {\mathcal{D}}_{m}}{p}_{{b}_{k}}({\mathcal{D}}_{m})}]}$, which is usually considered to be the auctioneer’s gain.
If given an allocation
$X$, it can easily be shown that the overall gain, which includes the total gain of the auctioneer and all bidders does not depend on the pay prices, but is equal to the sum of the allocated packages’ valuations [
10],
i.e.,
As our original intention, we employ the CA to obtain an efficient allocation for D2D relays.
Definition 2. An efficient allocation is an allocation that maximizes the overall gain. The efficient allocation is denoted by
${X}^{*}=({\mathcal{D}}_{1}^{*},{\mathcal{D}}_{2}^{*},\mathrm{...},{\mathcal{D}}_{M}^{*})=\{{x}^{\left\{{b}_{k}\right\}*}({\mathcal{D}}_{m})\}$.
Given the private valuations for all possible bidder packages in Equation (4), the efficient allocation can be obtained by solving the Combinatorial Allocation Problem (CAP) in CA games. Thus, the combinatorial NACKUEs auction can be formulated as
We note that the first constraint ensures that at most one bidders package can be allocated to each ACKUE. The second constraint guarantees that the bidderoverlapping packages can never be assigned. The CAP is also referred to as the winner determine problem, which has been proved that no polynomial time algorithm can be constructed for achieving the reasonable worst case guarantee [
12],
i.e., the problem is NP hard. In the next section, instead of directly solving the NPhard CAP in Equation (6), we introduce an approximate solution with a computationally tractable auction process to obtain the efficient NACKUEs allocation.
4. Combinatorial Auction Algorithm
In this section, we first propose an iterative combinatorial auction mechanism, in which the bid allocation choices are determined by an iterative, multiround auction process. Then, the auctionbased algorithm is described in detail and important properties of the proposed algorithm are analyzed.
Algorithm 1 Algorithm for D2D relay selection 
 1:
Initialize packages ${\mathcal{D}}_{1},{\mathcal{D}}_{2},\mathrm{...},{\mathcal{D}}_{M}$ to be empty set.  2:
Set up the history function of bidder ${b}_{k}$ for package is ${h}_{{b}_{k}}\left({\mathcal{D}}_{m}\right)=0$, ${b}_{k}={b}_{1},{b}_{2},\mathrm{...},{b}_{N}$, ${\mathcal{D}}_{m}={\mathcal{D}}_{1},{\mathcal{D}}_{2},\mathrm{...},{\mathcal{D}}_{M}$.  3:
for each ${b}_{k}:={b}_{1}\to {b}_{N}$ do  4:
for each ${i}_{m}:={i}_{1}\to {i}_{M}$ do  5:
Calculate valuation ${R}_{{b}_{k},{i}_{m}}$ according to (2);  6:
Bidder ${b}_{k}$ submits bids $\left\{{b}_{k},{i}_{m},{R}_{{b}_{k},{i}_{m}}\right\}$ for item ${i}_{m}$;  7:
end for  8:
end for  9:
for each ${b}_{k}:={b}_{1}\to {b}_{N}$ do  10:
Auctioneer finds the maximum valuation ${R}_{{b}_{k},{i}_{m}}^{*}$ and sells the ACKUE ${i}_{m}^{*}$ to bidder ${b}_{k}^{*}$;  11:
Allocate ${b}_{k}^{*}$ to package ${\mathcal{D}}_{{m}^{*}}$: ${\mathcal{D}}_{{m}^{*}}={\mathcal{D}}_{{m}^{*}}\cup \left\{{b}_{k}^{*}\right\}$;  12:
end for  13:
Calculate combinatorial valuation of each package ${\upsilon}^{\left\{{b}_{k}\right\}}\left({\mathcal{D}}_{m}\right)$ according to (4);  14:
loop until ${h}_{{b}_{k}}\left({\mathcal{D}}_{m}\right)=1,\forall {b}_{k},m$:  15:
Initialize $\delta =\infty $, $\xi =0$;  16:
for each ${b}_{k}:={b}_{1}\to {b}_{N}$ do  17:
if ${h}_{{b}_{k}}\left({\mathcal{D}}_{m}\right)=1$ then  18:
break;  19:
else  20:
Find the package ${\mathcal{D}}_{m}$ that ${b}_{k}$ is in;  21:
Try to remove ${b}_{k}$ from package ${\mathcal{D}}_{m}$, and calculate the consequent valuation ${{\upsilon}^{\prime}}^{\left\{{b}_{k}\right\}}\left({\mathcal{D}}_{m}\right)$;  22:
if ${{\upsilon}^{\prime}}^{\left\{{b}_{k}\right\}}\left({\mathcal{D}}_{m}\right){\upsilon}^{\left\{{b}_{k}\right\}}\left({\mathcal{D}}_{m}\right)>\delta $ then  23:
${b}_{{k}^{\u2020}}\leftarrow {b}_{k}$, $\delta ={{\upsilon}^{\prime}}^{\left\{{b}_{k}\right\}}\left({\mathcal{D}}_{m}\right){\upsilon}^{\left\{{b}_{k}\right\}}\left({\mathcal{D}}_{m}\right)$  24:
end if  25:
end if  26:
end for  27:
for each ${i}_{\tilde{m}}:={i}_{1}\to {i}_{M},\tilde{m}\ne m$ do  28:
Bidder ${b}_{{k}^{\u2020}}$ submits bid $\left\{{b}_{{k}^{\u2020}},{i}_{\tilde{m}},{R}_{{b}_{{k}^{\u2020}},{i}_{\tilde{m}}}\right\}$, the auctioneer calculate valuation ${{\upsilon}^{\prime}}^{\left\{{b}_{{k}^{\u2020}}\right\}}\left({\mathcal{D}}_{\tilde{m}}\right)$;  29:
if ${{\upsilon}^{\prime}}^{\left\{{b}_{{k}^{\u2020}}\right\}}\left({\mathcal{D}}_{\tilde{m}}\right){\upsilon}^{\left\{{b}_{{k}^{\u2020}}\right\}}\left({\mathcal{D}}_{\tilde{m}}\right)>\xi $ then  30:
${\mathcal{D}}_{{m}^{\u2020}}\leftarrow {\mathcal{D}}_{\tilde{m}}$, $\xi ={{\upsilon}^{\prime}}^{\left\{{b}_{{k}^{\u2020}}\right\}}\left({\mathcal{D}}_{\tilde{m}}\right){\upsilon}^{\left\{{b}_{{k}^{\u2020}}\right\}}\left({\mathcal{D}}_{\tilde{m}}\right)$;  31:
end if  32:
end for  33:
if $\delta +\xi >0$ then  34:
Update the provisional allocation: ${\mathcal{D}}_{m}={\mathcal{D}}_{m}\backslash {b}_{{k}^{\u2020}}$, ${\mathcal{D}}_{{m}^{\u2020}}={\mathcal{D}}_{{m}^{\u2020}}\cup \left\{{b}_{{k}^{\u2020}}\right\}$;  35:
${h}_{{k}^{\u2020}}\left({\mathcal{D}}_{{m}^{\u2020}}\right)={h}_{{k}^{\u2020}}\left({\mathcal{D}}_{{m}^{\u2020}}\right)+1$ ;  36:
else  37:
break;  38:
end if  39:
end loop

4.1. Algorithm for D2D Relay Selection
At the beginning of the auction, the eNB collects the location information of UEs and gets the channel state information (CSI) for all the links between UEs and the eNB. The bidders, i.e., the NACKUEs evaluate all their D2D links connecting to the ACKUEs to obtain their valuations. In the first round, all bidders submit bids for each ACKUE. Let
$\{{b}_{k},{i}_{m},{R}_{{b}_{k},{i}_{m}}\}$
denote the submitted bid by bidder
${b}_{k}$
and
$\mathcal{V}({b}_{k})$
the bid equal to its valuation for item
$k$. The auctioneer finds the highest bid
$\{{b}_{k}^{*},{i}_{m}^{*},{R}_{{b}_{k},{i}_{m}}^{*}\}$, and sells the ACKUE
${i}_{m}^{*}$
to bidder
${b}_{k}^{*}$. Then
${b}_{k}^{*}$
is added to package
${\mathcal{D}}_{{m}^{*}}$. The auction process moves on until all the bidders obtain an item. Then, the auction enters the second round.
In the auction, the ACKUEs is allowed to be sold more than once, but the bidder can only be allocated one item. That means, at the end of the first round, we can get a provisional allocation
$\{{\mathcal{D}}_{1},{\mathcal{D}}_{2},\mathrm{...},{\mathcal{D}}_{M}\}$, in which each element corresponds to a bidder package (possibly empty). To improve the outcome of the first round, the auctioneer adjusts the auction results in the second round. Given each combinatorial valuation
${\upsilon}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m})$
calculated according to Equation (2), the available adjustment strategies of the auctioneer and bidders are classified as follows
 (1)
Try to remove each bidder
${b}_{k}$ $(k=1,2,\mathrm{...},N)$
from its package
${\mathcal{D}}_{m}$
and calculate the consequent combinatorial valuation
${{\upsilon}^{\prime}}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m})$.
 (2)
Find the maximum value from the set
$\{{{\upsilon}^{\prime}}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m}){\upsilon}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m}),\forall k=1,2,\mathrm{...},N\}$
and select the corresponding
${b}_{k}$
which is marked as
${b}_{{k}^{\u2020}}$.
 (3)
Bidder
${b}_{{k}^{\u2020}}$
submits bid
$\{{b}_{{k}^{\u2020}},{i}_{\tilde{m}},{R}_{{b}_{{k}^{\u2020}},{i}_{\tilde{m}}}\}$, and then the auctioneer tries to add the bidder
${b}_{{k}^{\u2020}}$
into package
${\mathcal{D}}_{\tilde{m}}$ $(\tilde{m}\ne m,\tilde{m}=1,2,\mathrm{...},M)$
and calculates the consequent combinatorial valuation
${{\upsilon}^{\prime}}^{\{{b}_{{k}^{\u2020}}\}}({\mathcal{D}}_{\tilde{m}})$.
 (4)
Find the maximum value from the set
$\{{{\upsilon}^{\prime}}^{\{{b}_{{k}^{\u2020}}\}}({\mathcal{D}}_{\tilde{m}}){\upsilon}^{\{{b}_{{k}^{\u2020}}\}}({\mathcal{D}}_{\tilde{m}}),\forall \tilde{m}=1,2,\mathrm{...},M\}$
and select the corresponding
${\mathcal{D}}_{\tilde{m}}$
which is marked as
${\mathcal{D}}_{{m}^{\u2020}}$.
 (5)
The auctioneer checks this adjustment for validity. If
${{\upsilon}^{\prime}}^{\{{b}_{{k}^{\u2020}}\}}({\mathcal{D}}_{\tilde{m}}){\upsilon}^{\{{b}_{{k}^{\u2020}}\}}({\mathcal{D}}_{\tilde{m}})+{{\upsilon}^{\prime}}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m}){\upsilon}^{\left\{{b}_{k}\right\}}({\mathcal{D}}_{m})>0$, then updates the provisional allocation, i.e.,
${\mathcal{D}}_{m}={\mathcal{D}}_{m}\backslash {b}_{{k}^{\u2020}}$,
${\mathcal{D}}_{{m}^{\u2020}}={\mathcal{D}}_{{m}^{\u2020}}\cup \{{b}_{{k}^{\u2020}}\}$, otherwise the above adjustment strategies are invalid.
 (6)
Combinations of items 1–5.
We define history function
${h}_{{b}_{k}}({\mathcal{D}}_{m})$, which represents, for every provisional allocation
$\stackrel{\u2322}{X}$
in the second round, the number of times that bidder
${b}_{k}$
is adjusted into the package
${\mathcal{D}}_{m}$. Further, we also set a strategy constraint which does not allow each bidder is adjusted into the same package
${\mathcal{D}}_{m}$
for more than once, i.e.,
${h}_{{b}_{k}}({\mathcal{D}}_{m})\le 1,\forall {b}_{k}\in {\mathcal{N}}_{NACK}$. The proposed algorithm with a strategy constraint is summarized in Algorithm 1.
4.2. Convergence
Proposition 1: The proposed algorithm based on the iterative CA with a strategy constraint has the convergence property that the number of the iterations is finite.
Proof: According to the algorithm, in the first round, NACKUEs are allocated sequentially. Let us focus on the combinatorial auction in the second round. Suppose that the algorithm does not converge after a limited number of iterations, i.e., after T (positive integer) iterations. In this regard, denoting by
${X}^{t}$
the provisional allocation reached at the end of any iteration t, the outcome of proposed algorithm consists of an allocation sequence such as the following:
According to the pigeonhole principle, there exists an allocation
$\stackrel{\u2322}{X}=\left\{{\mathcal{D}}_{1},{\mathcal{D}}_{2},\mathrm{...},{\mathcal{D}}_{m},\mathrm{...},{\mathcal{D}}_{M}\right\}$
that occurs more than
$T/\left\mathcal{X}\right$
times, where
$\mathcal{X}$
denote the set of all possible allocations. Again, according to the pigeonhole principle, there exists a NACKUE
${b}_{k}\in {\mathcal{N}}_{\text{NACK}}$
that is allocated to package
${\mathcal{D}}_{m}$
for more than
$T/\left(\left\mathcal{X}\rightN\right)$
times, where
${\mathcal{D}}_{m}\in \stackrel{\u2322}{X}$. We suppose that
$T=\left\mathcal{X}\rightN$. Then after
T iterations, a history function
${h}_{{b}_{k}}\left({\mathcal{D}}_{m}\right)$
corresponding with the NACKUE
${b}_{k}$
satisfies
which contradicts our constraint. Thus in the second round, the proposed algorithm with a constraint must converge after
T iterations, where
T is a finite number.
4.3. Complexity
As mentioned before, a traditional CAP in fact is an NP hard problem, the number of items to be allocated is M, and the number of bidders is N. For an exhaustive optimal algorithm, an item can be allocated with N possible results. Thus, all the M items are allocated with
${N}^{M}$
possible results. The complexity of the algorithm can be denoted by
$\mathcal{O}({N}^{M})$. In the first round of the proposed algorithm, every channel is evaluated for all D2D pairs, resulting in a computation of
$\mathcal{O}(NM)$. In the second round, since each NACKUE can only be adjusted to the same package no more than once, the complexity is
$\mathcal{O}({\displaystyle {\sum}_{j}^{M}N(Mj)})=\mathcal{O}(N{M}^{2})$. Thus, the complexity of the proposed algorithm is
$\mathcal{O}(N{M}^{2})$. It is obvious that for sufficient large values of M and N, a finite number of T, a lower complexity is obtained by using the proposed iterative CA scheme. That is,
$\mathcal{O}({N}^{M})>\mathcal{O}(N{M}^{2})$.
4.4. Feedback and Signaling Overhead
In the D2D cluster, each cluster member should have the knowledge of
${\mathcal{N}}_{\text{ACK}}$
and
${\mathcal{N}}_{\text{NACK}}$. This can be achieved by employing one of the existing NACKbased feedback schemes [
13]. At the same time, as periodical D2D channel probing and estimation are indispensable for any cluster setup and maintenance procedure, we assume that each cluster member is always made aware of the channel state information (CSI) of D2D links connecting itself and the others. The additional information needed in our scheme is CSI between ACKUEs and NACKUEs, which is much less than the full D2D CSI maintenance. Then, the following iteration process is all conducted at the eNB, and no signal overhead needs to be exchanged among the network nodes until the control signal forwarding. In addition, the future work on D2D relay selection could consider some mechanism that limits the number of NACKUEs connecting to the same ACKUE by distance constraint, sociality constraint, etc, which would obviously help to reduce the overhead.