Revisiting relay assignment in cooperative communications

Abstract

The performance gain of cooperative communications heavily depends on the selection of relay. Most of the existing relay selection methods for cooperative communications aim at maximizing cooperative gain by selecting appropriate relay, without taking into account the adverse effect brought by cooperative communications: extra interference introduced by relay transmission (called cooperation interference). Thus the derived performance gain could be inaccurate and/or the selected relay may be not optimal. In this paper, we address the assignment of relays for multiple communication sessions using cooperative communication mode in wireless networks. We first thoroughly investigate the adverse effect brought by using relays, and derive the cooperation gain with consideration of cooperation interference. Based on the insights of our investigation, we propose a method of assigning relays to individual transmission flows while taking into account cooperation interference. In order to tradeoff the advantage and adverse effect caused by relay transmissions, we use an auction approach to address relay assignment of cooperative communications. Specifically, we propose a single round double auction scheme (SAS) for centralized wireless network and a multiple rounds sequential auction scheme (MAS) for decentralized wireless network for relay assignment. We conduct extensive simulation experiments to validate the effectiveness of SAS and MAS. The significance of cooperation interference, the improvement of overall system throughput and energy efficiency of our proposed relay assignment schemes are demonstrated by numerical results.

1 Introduction

In recent years, cooperative communication has been regarded as one of the most promising techniques to improve system throughput of wireless networks [2]. In a typical two-hop cooperative communication system, a two-hop good transmission channel via relay is used to replace a direct link for data transmission, where the source can employ one or more idle nodes as relay(s) to forward data. One of the amazing advantages of employing relay is that cooperative communication can improve capacity with the fixed transmission power [2, 3].¹

Recently, existing related research results indicate that relay plays a key role and has a significant impact on the performance gain in cooperative communications. The issue of relay selection has attracted considerable research attention and been extensively studied [4–14]. Unfortunately, most existing relay selection algorithms are merely focused on maximizing cooperation gain, while ignoring the negative impact of interferences caused by relay communications on system throughput performance. In cooperative communications, extra interference introduced by relay, called $cooperation\,interference$, may affect the transmission of neighbor nodes. In other words, the forwarded data sent from relay is useful to destination but in the meantime generates interference to other nodes which are in the interference range of the relay. Obviously, cooperation interferences do not exist in conventional communication mode with only direct transmission and have an adverse impact on system performance.

Let us use an example to illustrate the cooperation interference. Let there be two independent flows, $f_1$ (from node 1 to node 2) and $f_2$ (from node 3 to node 4), in a wireless network, and they are out of the interference range of each other, as shown in Fig. 1(a). If both flows use direct transmission without relay, there is no extra interference. On the other hand, if a relay, say node 5, is selected according to some criteria to enjoy the throughput improvement of cooperative communications [2, 3], extra interference is generated due to the transmission of node 5. In this case, although employing relay could provide higher transmission rate for $f_1$, the impact on $f_2$ should be carefully investigated. As $f_2$ is in the interference range of the relay, the transmission of node 5 could interfere with nodes 3 and 4. Thus the transmission of $f_2$ is interfered and the effective transmission rate is decreased and the performance gain of cooperative communications is compromised. In some cases, the system rate of cooperative communications could be even smaller than that of direct transmission.

Fig. 1

An example to illustrate cooperation interference. a Direct transmission without cooperation interference. b Cooperative communications with cooperation interference

The subsequences of ignoring cooperation interference in designing cooperative communication schemes are as follows. (1) The exact performance gain of cooperative communication could be fairly smaller than what the authors claim. Specifically, existing relay assignment strategies are seemed too greedy as excessive relays could be employed. In this case, the exact cooperation gain could be very small or even negative, when taking into account the cooperation interferences brought by relays. (2) A relay selected may be not the best one for maximizing the system performance gain in realistic wireless networks, and thus the performance gain could be further improved.

In this paper, we revisit existing relay assignment schemes in cooperative communications, and propose two auction based relay assignment schemes with special attention to cooperation interference. Our contribution in this paper is threefold. (1) We thoroughly investigate the impact of employing relays in cooperative communications, and analyze the negative effect of the cooperation interference; (2) Using auction model to address relay assignment, while considering the adverse effect caused by cooperation interference; (3) Compared with the results of throughput gain of cooperative communication in existing analytical model, the performance gain we derive is more accurate.

The remainder of this paper is organized as follows. Section 2 surveys the related work. Section 3 describes the system model. In Sect. 4, we present two relay assignment schemes for centralized and distributed wireless networks respectively. Simulation results as well as discussions are presented in Sect. 5. We finally conclude the paper in Sect. 6.

2 Related work

In [4], Ibrahim et al. proposed a new cooperative communication protocol by selecting optimal relay. They find that the optimal relay is the one which has the maximum instantaneous scaled harmonic mean function of its source–relay and relay–destination channel gains. In [5], Shi et al. proposed an optimal relay assignment scheme to maximize the minimum capacity with a polynomial-time complexity algorithm. In [6], Wei et al. proposed a relay selection method in time-varying channels without centralized control point. In [7], Yang et al. designed an integrated optimal relay assignment scheme which is robust to selfish and cheating behavior of users while guaranteeing the social optimal system capacity in centralized wireless networks. In [8], Liu et al. proposed an optimal distributed power allocation algorithm with auction approach, which studies the user cooperation scenario where multiple users cooperate with each other and act as both an auctioneer (seller) and a bidder (buyer). In [9], Li et al. studied an assignment game approach for relay selection, where the sources should pay the relays for their cost energy to stimulate the relays compete with each other for virtual currency from the assisted sources in cooperative transmissions. In [10], Huang et al. proposed two auction mechanisms, the SNR auction and the power auction, that determine relay selection and relay power allocation in a distributed fashion. In [11], Yang et al. designed an auction scheme for the cooperative communications, which can maintain truthfulness while fulfilling other design objectives. In [12], Razeghi et al. considered jointly three criteria to design a new relay selection scheme for multi-user cooperation communications. In [13], Omri et al. used best relay and user selection technique on demand and greedily to propose two efficient cooperative communication schemes with interference management. In [14], Xie et al. proposed three algorithms for interference-aware cooperative routing, local channel adjustment, and local path and relay adaptation respectively to ensure high performance communications in dynamic wireless networks.

So far, only very few researchers address cooperation interference in cooperative communications [15–17]. In [15], Zhang et al. investigated how the relay assignment affects interference and propose a relay assignment algorithm with interference mitigation for wireless cooperative networks. However, they assume that all source–destination pairs can work simultaneously without interference and interference is produced only by relay nodes. As a result, the proposed relay assignment is only effective for the scenario with excessive relays and very few traffic flows. In other word, the proposed relay assignment in [15] cannot work when the networks are moderately loaded. Moreover, [15] only provided a heuristic algorithm for distributed networks which is inapplicable to centralized networks. Different from [15], in this paper, our proposed MAS and SAS are general as thet have no limitation on traffic pattern and they can be used for distributed and centralized networks respectively.

Zhu et al. in [16] showed that the performance of relaying in large-scale wireless networks is penalized by the elevated level of interference induced by the relays. In order to mitigate the impact of interference, the authors in [16] present two conflict graph based channel allocation mechanisms for cooperative network, where multiple channels are required for interference mitigation. This is infeasible for single channel wireless networks. More importantly, [16] focused only on the interference mitigation on relays while ignoring the adverse effect on other traffic flows. As a result, the methodology for improving system throughput considering relay assignment problem has not been considered in [16]. In contrast, we investigate the impact of cooperation interference caused by relays and propose two auction based relay assignment algorithms for the overall system throughput in this paper.

In order to address the issue of additional competition caused by relay, our previous work [17] proposed Nash and Bayesian Nash equilibrium strategies for cooperative communications. Based on the rational and selfish nature, the proposed equilibrium strategies are optimal, which can guarantee the maximal throughput of individual traffic flows. However, [17] only provided the strategies for individual flow but system-level relay assignment has not been considered.

3 System model

In the wireless network, we assume that cooperative communication mode can be adopted to improve the system capacity, and the channel state information (CSI) can be detected with channel estimate. Specifically, we assume that Decode-Forward (DF) cooperation mode is used in the rest of this paper. Nevertheless, we would like to mention that the analytical model and our proposed relay assignment strategy can also be readily extended to other cooperation modes such as Amplify-Forward (AF) and Coded Cooperation (CC) with minor modifications. We assume that a flow uses at most one relay to forward data, and an idle node is allowed to serve one flow. Without loss of generality, we set the transmission power $P_{s_i}=P_{r_j}=P$, where $P_{s_i}$ is the transmission power of $s_i$, $P_{r_j}$ is the transmission power of $r_j$, and P is the fixed value of maximum transmission power, respectively. We consider a wireless network which consists of n traffic flows with individual sources and destinations and m idle nodes which can serve as relay. In another word, n is the number of active flows, and m is the number of idle nodes which can served as relays for cooperation, only the selected relay would forward data and affect the transmission rate. Therefore, the exact transmission rate depends on the active flows and selected relays in the interference range.

We use $S=\{s_1; s_2; \ldots ; s_n\}$, $D=\{d_1; d_2; \ldots ; d_n\}$ and $R=\{r_1; r_2; \ldots ; r_m\}$ to denote the set of sources, destinations and relays, respectively. The set of flows is denoted by $F=\{f_1; f_2;\ldots ; f_n\}$. Furthermore, we define $F_i$ is the set of flows that would be interfered by $f_i$($F_i\subset F$), where $f_j$ is interfered by $f_i$ means that the destination of $f_j$ is in the interference range of the source of $f_i$, and set $R_j$ includes the flows in the interference range of $r_j$. For example, in Fig. 2, $F=\{f_1, f_2, f_3\}$, $F_1=\{f_2, f_3\}$, $F_2=\{f_1\}$, $F_3=\{f_2\}$, $R_1=\{f_1, f_2, f_3\}$, $R_2=\{f_1, f_2\}$, $R_3=\{f_2, f_3\}$.

Fig. 2

A wireless network scenario with interference range

In direct transmission, the transmission rate of $f_i$ is given by

$$C_{f_i}=Wlog_2(1+\Gamma _{s_i,d_i}),$$

(1)

where $\Gamma _{s_i,d_i}$ is the SINR of the signal sent from $s_i$ to $d_i$,

$$\Gamma_{s_i,d_i}=\frac{{P_{s_i}G_{s_i,d_i}}}{{\sigma^2+\sum\nolimits_{f_k\in F_i,k\ne i} P_{s_k}G_{s_k,d_i}}},$$

where W is the bandwidth, $G_{s_i,d_i}$ is the channel gain between $s_i$ and $d_i$, and $G_{s_k,d_i}$ is the channel gain between $s_k$ and $d_i$, respectively. The channel gain could be calculated based on transmission distance D and fading coefficient K, $G=D^{-K} \cdot \sigma^2$ is the power of Gaussian noise. $f_k$ is a flow in $F_i$, which means that there exists cooperation interference between $f_k$ and $f_i$.

Correspondingly, the transmission rate of $f_i$ in cooperative communication with $r_j$ is given by [18].

$$C_{f_i,r_j}=min\left\{ \frac{W}{2}log_2(1+\Gamma _{s_i,r_j}), \frac{W}{2}log_2(1+\Gamma _{s_i,d_i}+\Gamma _{r_j,d_i})\right\} ,$$

(2)

where $\Gamma _{s_i,r_j}$ and $\Gamma _{r_j,d_i}$ is the SINR of the signal sent from $s_i$ to $r_j$ and SINR of the signal sent from $r_j$ to $d_i$ respectively,

$$\begin{aligned} \Gamma _{s_i,r_j}= & {} \frac{P_{s_i}G_{s_i,r_j}}{\sigma ^2+\sum _{f_l\in R_j,l\ne i}P_{s_l}G_{s_l,r_j}},\\ \Gamma _{r_j,d_i}= & {} \frac{P_{r_j}G_{r_j,d_i}}{\sigma ^2+\sum _{f_k\in F_i,k\ne i}P_{s_k}G_{s_k,d_i}}, \end{aligned}$$

where $G_{s_i,r_j}$, $G_{r_j,d_i}$, $G_{s_l,r_j}$ and $G_{s_k,d_i}$ are the channel gain between $s_i$ and $r_j$, $r_j$ and $d_i$, $s_l$ and $r_j$, $s_k$ and $d_i$, respectively. $f_l$ is the flow in $R_k$, which indicates that there exists cooperation interference between $f_l$ and $r_j$.

In direct transmission, there is no cooperation interference. The total transmission rate of flows in $R_j$ is

$$C_{R_j}=\sum _{f_l\in R_j}Wlog_2\left( 1+\frac{P_{s_l}G_{s_l,d_l}}{\sigma ^2+\sum _{f_m\in F_l,m\ne l}P_{s_m}G_{s_m,d_l}}\right) ,$$

(3)

where $C_{R_j}$ is the total transmission rate of $f_l\in R_j$ when relay $r_j$ is not employed, $f_m$ is the flow in the interference range of $f_l$, and $f_l$ is the flow in the interference of $r_j$, respectively.

Cooperation interference is caused when $r_j$ transmits data in cooperative communication. Then the total transmission rate of flows in $R_j$ in cooperation mode can be given by

$$\begin{aligned} C_{R_j}^{\prime} = \sum _{f_l\in R_j}Wlog_2\nonumber \\&\,\left( 1+ \frac{P_{s_l}G_{s_l,d_l}}{\sigma ^2+\sum _{f_m\in F_l,m\ne l}P_{s_m}G_{s_m,d_l}+P_{r_j}G_{r_j,d_i}}\right), \end{aligned}$$

(4)

where $C_{R_j}^{\prime}$ is the total transmission rate of $f_l\in R_j$ when relay $r_j$ is employed.

According to $C_{R_j}$ in (3) and $C_{R_j}^{\prime}$ in (4), we can see that $C_{R_j}'\le C_{R_j}$ due to the extra cooperation interference that has been considered in (4). Therefore, considering the adverse impact of cooperation interference, whether to adopt cooperation or not should be decided carefully, and this is the problem we would address in this paper. In order to effectively evaluate the impact of cooperation interference based on (1–4), we describe auction model in the next section.

4 Auction based mechanisms for relay assignment

In centralized networks, such as mobile cellular networks, the central node (e.g. base station) has the central control capability for its serving nodes (e.g. mobile users). In contrast, there is no any central node in distributed networks (such as ad-hoc networks). Therefore, we develop centralized and distributed relay assignment schemes, called single round double auction scheme (SAS) and multiple rounds sequential auction scheme (MAS) respectively for these two types of networks. In SAS, the central node is the auctioneer, and buyers and sellers send their bid price and sell price respectively to the auctioneer for single round allocation. In MAS, relays are assigned in multiple rounds and the seller is also the auctioneer in each round. In the following, we first elaborate SAS and MAS respectively, and then analyze the time complexity of the two schemes.

4.1 Auction model

As the relay in cooperative communications can bring both capacity gain (value) and cooperation interference (cost) which degrades capacity performance, we need to carefully explore the tradeoff between the value and cost for determining the communication mode and relay assignment. An auction model is an effective tool to address this issue. There are three basic elements in an auction model: buyer, seller and auctioneer. In cooperative communications, the relay, the flow which wants to employ relay and the node which determines communication mode (adopting cooperative communications or direct transmission) can be deemed as the seller, the buyer and the auctioneer, respectively. On the one hand, a rational buyer would bid the product when the difference between the value and cost is at least non-negative. In other words, a relay should be used only when the achieved cooperation gain can at least compensate the cost of the introduced cooperation interference. On the other hand, the greater difference between the value and cost, the greater benefit obtained. This implies that a relay which can provide a high cooperation gain while causing a low cooperation interference is preferred for a specific flow.

According to (1) and (2), we can obtain that the improved transmission rate of $f_i$ is $C_{f_i,r_j}-C_{f_i}$. Due to the cooperation interference generated by $r_j$ transmission, the total transmission rate of flows in $R_j$ would be decreased as $C_{R_j}-C_{R_j}'$. Therefore, we can compute the value of employing $r_j$ by $f_i$ (denoted by $v_{f_i,r_j}$) as

$$v_{f_i,r_j}=C_{f_i,r_j}-C_{f_i},$$

(5)

and the cost of providing cooperation at $r_j$ (denoted by $c_{r_j}$) as

$$c_{r_j}=C_{R_j}-C_{R_j}'.$$

(6)

Hence, the performance gain and negative impact of cooperation interference have been defined as the value and cost respectively in the auction model. In fact, for other design objectives of cooperation such as energy saving, the value and cost can be redefined accordingly.

4.2 Single round double auction scheme (SAS)

In SAS, relays are assigned in a single round based on double auction with truthful bid/sell price. The procedure of SAS is described as follows. First, each buyer creates a bid price vector $b_{f_i}=\{b_{f_i,r_1}, b_{f_i,r_2}, \ldots , b_{f_i,r_m}\}$ ($f_i\in F$) according to the corresponding $v_{f_i,r_j}$ ($r_j\in R$), and submits it to the auctioneer. At the same time, each seller calculates its sell price $s_{r_j}$ according to the corresponding $c_{r_j}$ and sends it to the auctioneer. Next, the auctioneer allocates relays based on the maximum weighted matching (MWM) algorithm in graph theory [19]. In order to guarantee the truthfulness of submitted cost and value, we use Vickrey–Clarke–Groves (VCG) scheme [20] in SAS. Furthermore, it has been shown that VCG based auctions are truthful, and the proof follows the standard Vickrey auction proofs [20].

By using F, R and the detected CSI, each buyer can compute the corresponding $v_{f_i,r_j}$, and each seller can compute its $c_{r_j}$. Then the auctioneer can construct the value matrix V which is defined as

$$\begin{aligned} V=\left[ \begin{array}{ccc} v_{f_1,r_1} & \ldots & v_{f_1,r_m}\\ \ldots & v_{f_i,r_j} & \ldots \\ \ldots & \ldots & v_{f_n,r_m}\\ \end{array} \right] , \end{aligned}$$

(7)

and the cost matrix C is defined as

$$\begin{aligned} C=\left[ \begin{array}{ccccc} c_{r_1} & \ldots & c_{r_j} & \ldots & c_{r_m}\\ \end{array} \right] . \end{aligned}$$

(8)

According to V and C, the auctioneer can derive the difference matrix D as

$$\begin{aligned} D=\left[ \begin{array}{ccc} d_{11} & \ldots & d_{1m}\\ \ldots & d_{ij} & \ldots \\ \ldots & \ldots & d_{nm}\\ \end{array} \right] , \end{aligned}$$

(9)

where $d_{ij}=v_{f_i,r_j}-c_{r_j}$, which is the benefit of employing $r_j$ for $f_i$ considering both value and cost.

Obviously, employing $r_j$ is beneficial for $f_i$ when $d_{ij}>0$. In other words, an idle node can be selected as relay when the caused cost is lower than the corresponding value $v_{f_i,r_j}>c_{r_j}$.

Based on the difference matrix D, the auctioneer can determine the relays which are beneficial for $f_i$ and all the flows which might employ $r_j$. The ith line in D may have more than one elements $d_{ij}>0$, as there could be more than one beneficial relays for $f_i$. In contrast, the jth row in D could also have multiple elements which are greater than zero. This observation indicates that there could be multiple flows which can employ $r_j$ for cooperation. In our proposed SAS, relay assignment algorithm should satisfy the following three conditions: (1) each flow is allowed to employ only one relay for cooperation; (2) each relay could be employed for cooperation by one flow; and (3) the overall achieved system benefit ($v_{f_i,r_j}-c_{r_j}$) should be maximal.

In SAS, we construct a bipartite graph according to F and R, and all edges in bipartite graph are based on D. An edge in bipartite graph, denoted by $E(f_i,r_j)$, means that there is a connection between $f_i$ and $r_j$, and the set of all edges is denoted by E [where $E(f_i,r_j)\in E$]. Accordingly, we can obtain the bipartite graph with initial allocation $M=\hbox {G}(F, R, E)$. Next, in order to maximize the total improvement for relay assignment, MWM is adopted to find the relay allocation with the maximal benefit. The detailed algorithm of SAS is given in Algorithm 1, where M is a mapping function from the indices of buyers to those of sellers. Finally, the output $\Theta$ of this algorithm is the relay assignment in SAS.

For truthfulness, the VCG scheme is adopted to determine the bid price of buyer and the sell price of seller at auctioneer, which can be computed as

$$b_{f_i,r_j}=v_{f_i,r_j}-(W^*-W_{-f_i}^*),$$

(10)

and

$$s_{r_j}=c_{r_j}+(W^*-W_{-r_j}^*),$$

(11)

where $b_{f_i,r_j}$, $s_{r_j}$, $W^*$, $W_{-f_i}^*$ and $W_{-r_j}^*$ are the bid price of $f_i$, the sell price of $r_j$, the weighted value of $M^*$, that when $f_i$ is removed from auction, and that when $r_j$ is removed from auction, respectively.

Therefore, we can define the utility of buyers, denoted by $U_{f_i}$, as

$$\begin{aligned} U_{f_i} = {\left\{ \begin{array}{ll} v_{f_i,r_j}-b_{f_i,r_j}, \,if\,f_i\,employs\,r_j,\\ 0, \,otherwise. \end{array}\right. } \end{aligned}$$

(12)

and the utility of sellers, denoted by $U_{r_j}$, as

$$\begin{aligned} U_{r_j}= {\left\{ \begin{array}{ll} s_{r_j}-c_{r_j},\, if\,r_j\,is\,employed,\\ 0,\, otherwise. \end{array}\right. } \end{aligned}$$

(13)

and the benefit of successful pair, denoted by $B_{f_i,r_j}$, as

$$B_{f_i,r_j}=v_{f_i,r_j}-c_{r_j}.$$

(14)

4.3 Multiple rounds sequential auction scheme (MAS)

For distributed networks, such as ad hoc wireless networks, SAS is not applicable. In this case, we develop a Multiple rounds sequential auction scheme (MAS). In MAS, all sellers wait for bidding in sequence. In each round, a seller is just the auctioneer and chooses the buyer who submits the highest bid price, and the successful bid price must be higher than the cost of the seller. Otherwise, the seller should not be allocated to any buyer, and there is no winner in this round for buyers. The successful buyer should exit the auction, and thus we can consider that the corresponding bid price is negative in the subsequent bidding rounds. Otherwise, all the unallocated buyers would bid for the next seller, and the auction procedure ends when there is no buyer or seller. The details of MAS are presented in Algorithm 2.

Due to lack of central node, the bidding price may be not truthful in Distributed Coordination Function (DCF) wireless networks, unlike that in SAS. Hence, how to submit bid price is very important for the buyers. For example, in the jth bidding round, if the bid price of the ith buyer is too low, the corresponding bidding success probability would be decreased. Otherwise, the received benefit of the ith buyer ($v_{f_i,r_j}-b_{f_i,r_j}$) would be decreased. In order to make a good tradeoff between the winning probability and the benefit, an appropriate bid price should be determined. To this end, we analyze the bidding success probability for a buyer in a bidding round first, and then detect the optimal bid price.

Without loss of generality, we assume that the kth bidding round is over, and there is always an allocated pair of buyer and seller in each completed bidding round. In the $(k+1)$th bidding round, there are $(n-k)$ buyers and $(m-k)$ sellers. We suppose that the bid price of buyers is a random variable which follows uniform distribution, and the distribution is identical and independent [21]. Therefore, we can obtain the probability density function of the bid price in this bidding round as

$$f(b)=\frac{1}{v_{max}-b_{min}},$$

(15)

where $v_{max}$ is the maximum value of employing $r_j$ as relay for a flow. For example, $v_{max}$ could be the maximum transmission rate. $b_{min}$ is the lowest price which could be accepted by the seller, which is just the cost of seller, i.e., $b_{min}=c_{r_{k+1}}$.

In the $(k+1)$th bidding round, let the bid price of the ith buyer be $b_{f_i,r_{k+1}}$, and the bid price of the jth buyer be $b_{f_j,r_{k+1}}$ ($j\ne i$). If the ith buyer is the winner in this bidding round, we can know that $b_{f_j,r_{k+1}}<b_{f_i,r_{k+1}}$. The probability of $b_{f_j,r_{k+1}}<b_{f_i,r_{k+1}}$ is given by

$$P(b_{f_j,r_{k+1}}<b_{f_i,r_{k+1}}|j\ne i)=\int _{c_{r_{k+1}}}^{b_{f_i,r_{k+1}}}f(b)db.$$

(16)

Substituting (15) into (16) yields

$$P(b_{f_j,r_{k+1}}<b_{f_i,r_{k+1}}|j\ne i)=\frac{b_{f_i,r_{k+1}}-c_{r_{k+1}}}{v_{max}-c_{r_{k+1}}}.$$

(17)

We can then derive the bidding success probability of the ith buyer, which is the probability that the bid price of the ith buyer should be higher than that of others.

$$P(\forall b_{f_j,r_{k+1}}<b_{f_i,r_{k+1}}|\forall j\ne i)=\prod ^{\forall f_j}\int _{c_{r_{k+1}}}^{b_{f_i,r_{k+1}}}f(b)db.$$

(18)

Therefore, submitting (17) into (18), we can obtain the bidding success probability of the ith buyer in the $(k+1)$th round and rewrite (18) as

$$P(\forall b_{f_j,r_{k+1}}<b_{f_i,r_{k+1}}|\forall j\ne i)=\left( \frac{b_{f_i,r_{k+1}}-c_{r_{k+1}}}{v_{max}-c_{r_{k+1}}}\right) ^{(n-k-1)}.$$

(19)

We next derive the optimal bid price to ensure the maximum benefit for buyers. The expected benefit of the ith buyer is

$$E_{f_i,r_{k+1}}=(v_{f_i,r_{k+1}}-b_{f_i,r_{k+1}})P(\forall b_{f_j,r_{k+1}}<b_{f_i,r_{k+1}}|\forall j\ne i),$$

(20)

where $v_{f_i,r_{k+1}}$ is the value of the ith buyer in the $(k+1)$th bidding round for $r_{k+1}$ if it wins.

Substituting (19) into (20) yields

$$E_{f_i,r_{k+1}}=(v_{f_i,r_{k+1}}-b_{f_i,r_{k+1}}) \left( \frac{b_{f_i,r_{k+1}}-c_{r_{k+1}}}{v_{max}-c_{r_{k+1}}}\right) ^{(n-k-1)}.$$

(21)

Setting the first derivative of $E_{f_i,r_{k+1}}$ versus $b_{f_i,r_{k+1}}$ to zero, we can obtain the optimal bid price for the ith buyer in the $(k+1)$th bidding round,

$$b_{f_i,r_{k+1}}^*=\frac{(n-k-1)v_{f_i,r_{k+1}}+c_{r_{k+1}}}{n-k}$$

(22)

Finally, $b_{f_i,r_{k+1}}^*$ is the submitted bid price in Algorithm 2.

4.4 Computational complexity

In SAS, the computational complexity is based on the calculation of bid price, sell price, value, cost, difference matrix D, initial assignment M and MWM, where $O(T(n,m))=O(((n+m)^2)log(n+m)+(n+m)nm)$ is the computational complexity for MWM [19], $O((n+m+1)*T(n,m))$ is that for computing bid and sell price, and $O(m(3n+1))$ is that for computing value $v_{f_i,r_j}$ (O(nm)), cost $c_{r_j}$ (O(m)), difference matrix D (O(nm)) and initial assignment M (O(nm)), respectively. Therefore, the computational complexity of SAS is $O((n+m+1)T(n,m)+ m(3n+1))$.

In MAS, the computational complexity is affected by the overall number of biding rounds, and we analyze the upper and lower bound of computational complexity as follows. In the case of upper bound, there is no winner in each bidding round. The complexity for computing $v_{f_i,r_j}$, $c_{r_j}$ and the bid price is O(n), O(1) and O(n), respectively. Thus, the upper bound of computational complexity of MAS is $O((3n+1)m)$, where m is the number of binding rounds. In contrast, in the case of lower bound, there is always a winner in each bidding round, and the lower bound of the computational complexity of MAS is $O(3min\{n,m\}(2n-min\{n,m\}+1)/2+min\{n,m\})$.

5 Performance evaluation and discussions

In order to demonstrate the advantages of SAS and MAS, we use the centralized relay assignment scheme in [7] and the distributed relay assignment scheme in [6] as comparison references, since they are typical relay assignment schemes in recent years. As both [6, 7] ignore cooperation interference, we call their relay assignment scheme as centralized and distributed Cooperation Interference Ignorance (CII) relay assignment, respectively.

We evaluate the performance of SAS and MAS in terms of the overall system throughput improvement ($B_s$) and energy efficiency (EE). $B_s$ is defined in (23) and EE is defined in (24), respectively. In order to examine the difference of relay assignments, we also compare the ratio of the number of identical relay assignments between SAS/MAS and CII to that of SAS/MAS, which is called similarity (S) and defined in (25). In all simulation experiments, we set $P=1$ watt, $\sigma ^2=10^{-10}$ watt and $W=22$ MHz.

$$B_{s} = \sum _{all}B_{f_i,r_j},$$

(23)

$$EE = \frac{the\, overall\, system\, throughput}{the\,overall\,energy\,consumption}.$$

(24)

$$S= \frac{Num. \,of \,identical \,relays \,between\, SAS\, (MAS) \,and\, CII}{Num. \,of \, relays \, of\,SAS \,(MAS)}.$$

(25)

5.1 Comparisons of relay assignment

In the first experiment, we examine the results of relay assignment of different schemes, aiming at verifying our analysis for the impact of cooperation interference on relay assignment. We conduct the experiments with $n=15,m=20$ and $n=20,m=10$ respectively. The relay assignment results with $k=4$ are illustrated in Tables 1 and 2 respectively. Note that the results in Tables 1 and 2 are from one experiment. The 1th, 2th and 6th column indicates the source ID, the assigned relay ID, respectively. The benefit (throughput improvement) of $f_i$ when $r_j$ is employed ($B_{f_i,r_j}$) in MAS, SAS and distributed/centralized CII is given in 3th, 7th, 5th and 9th column, respectively.

According to the assigned relay ID of distributed/centralized CII in the 4th/8th column, we can see that in experiment 1, $f_5$, $f_6$, $f_{10}$, $f_{11}$ and $f_{14}$ chooses $r_1$, $r_2$, $r_{15}$, $r_8$ and $r_{14}$ as relays for cooperation in distributed CII, respectively. In contrast, in MAS, $f_5$ and $f_6$ adopts $r_8$ and $r_6$ as relays, $f_{10}$, $f_{11}$ and $f_{14}$ uses direct transmission mode, respectively. In centralized CII, we can see that $f_1$, $f_4$, $f_6$, $f_9$, $f_{10}$ and $f_{11}$ chooses $r_{10}$, $r_9$, $r_2$, $r_{14}$, $r_{15}$ and $r_{17}$ as relays for cooperation, respectively. However, in SAS, $f_1$, $f_4$, $f_6$ and $f_9$ prefers to select $r_{11}$, $r_{18}$, $r_6$ and $r_{10}$ as relays, $f_{10}$ and $f_{11}$ uses direct transmission mode, respectively. In experiment 2, we can also find that there are 4 relay assignment results are different between MAS and distributed CII, and 5 relay assignment results are different between SAS and centralized CII. The negative value of $B_{f_i,r_j}$ represents that system throughput would be degraded when $f_i$ employs $r_j$, and this is because that the negative effect of cooperation interference caused by assigned relay is overlooked by distributed/centralized CII. Compared with MAS/SAS, we can observe that distributed/centralized CII is more greedy for cooperation as more relays are employed, and thus a relay is always adopted once the corresponding cooperation gain is positive. In contrast, the relay assignment is more conserved in MAS and SAS. This is because that in MAS and SAS, a relay is adopted only when the improvement brought by cooperation gain can fully compensate the negative effect of cooperation interference. In addition, the value of $B_{f_i,r_j}$ of MAS/SAS is always positive but that of distributed/centralized CII might be negative. This observation effectively validates our analysis on the negative effect of cooperation interference on the throughput gain of cooperative communications.

Table 1 Experiment 1: comparisons of relay assignment with $n=15$ and $m=20$

Table 2 Experiment 2: comparisons of relay assignment with $n=20$ and $m=10$

Fig. 3

Performance comparisons with varying $n=m$. a System throughput improvement in distributed networks. b System throughput improvement in centralized networks. c Energy efficiency in distributed networks. d Energy efficiency in centralized networks

Fig. 4

Relay assignments with varying $n=m$. a Number of assigned relays in distributed networks. b Number of assigned relays in centralized networks. c Similarity

5.2 Performance comparison for various network sizes

Next, in experiment 3, we evaluate the performance of SAS and MAS in terms of the overall system throughput improvement ($B_{s}$) and energy efficiency (EE) for various numbers network sizes with k=4. For simplicity, we set $n=m$ and randomly set sources, destinations and relays in a $2000\hbox {m}\times 2000\hbox {m}$ square area. For distributed and centralized networks, Fig. 3 shows $B_{s}$, EE, the number of assigned relays and similarity of relay assignments, respectively.

Figure 3a and b show $B_{s}$ as a function of n. In order to show the impact of cooperation interference, we examine $exact\,B_{s}$ and $nominal\,B_{s}$, which is defined as the overall system throughput improvement taking into account cooperation interference and that ignoring cooperation interference, respectively. We can see that exact $B_s$ of SAS and MAS outperforms that of CII. Moreover, the difference between the nominal $B_s$ and exact $B_s$ of CII is significant. This observation confirms our analysis that CII just considers the advantage of assigned relay but the adverse effect of cooperation interference is ignored. As a result, CII cannot achieve the nominal performance. Furthermore, we can also find that the improvement of SAS is higher than that of MAS. The reason is that in centralized networks system information is available to optimize the relay assignment. Moreover, it is obvious that the improvement increases with n. The reason is that a “good” relay is easily selected in a dense wireless network.

Next, we present the comparison of EE in Fig. 3c and d. Since SAS and MAS can achieve higher throughput improvement with less relays, we can see that EE of SAS / MAS is higher than that of centralized/distributed CII. Meanwhile, EE decreases with n due to increased interference when network becomes dense.

The number of assigned relays is shown in Fig. 4a and b. Obviously, the number of assigned relays of centralized/distributed CII is greater than that of SAS/MAS. The reason is that the adverse effect of cooperation interference is ignored by CII, and thus CII is more greedy to adopt cooperative communication mode compared with SAS and MAS. In comparison, SAS and MAS would rationally prefer direct transmission when cooperation gain cannot fully compensate cooperation interference.

Figure 4c shows the comparison of similarity S of SAS and MAS. We can see that S of SAS and MAS increases from around 0.65 to 0.9. This indicates that the difference of relay assignment between SAS/MAS and centralized/distributed CII is significant.

Fig. 5

Performance comparisons with varying K. a System throughput improvement in distributed networks. b System throughput improvement in centralized networks. c Energy efficiency in distributed networks. d Energy efficiency in centralized networks

Fig. 6

Relay assignment with varying K. a Number of assigned relays in distributed networks. b Number of assigned relays in centralized networks. c Similarity

5.3 Performance comparison for various channel conditions

Next, in experiment 4, we evaluate the performance of SAS and MAS with $n=m=50$ for different channel conditions (reflected by K). Figures 5 and 6 show the overall system throughput improvement $B_{s}$, energy efficiency EE, the number of assigned relays and the similarity of relay assignments S, respectively.

Figure 5a and b show $B_{s}$ and EE comparisons of SAS/MAS and centralized/distributed CII respectively. We can see that $B_{s}$ of SAS/MAS is significantly higher than that of centralized/distributed CII, and increases with K. The reason is that the data transmission rate in direct link is decreased when K becomes high, and thus the assigned relay for cooperation is more effective to improve system throughput. The advantage of SAS and MAS on EE compared with CII is validated by the results shown in Fig. 5c and d.

Figure 6 shows the number of assigned relays and S as a function of K. From Fig. 6a and b, we can observe that the number of assigned relays in CII is greater than that in SAS and MAS. The reason is that CII is more greedy to adopt cooperative communication mode. In comparison, SAS and MAS subtly employ relay by considering both the advantage and adverse effect of cooperation. In Fig. 6c, we can see that S decreases from around 0.85–0.76. According to the results in Figures 5 and 6, we can find that the relay assignment has a significant impact on system performance.

6 Conclusions

In this paper, we have proposed two schemes, single round double auction scheme (SAS) and a multiple rounds sequential auction scheme (MAS) for relay assignment, considering the improvement of cooperation gain and the adverse effect of cooperation interference. SAS is designed for centralized scenario based on single round double auction, which could optimally allocate the relay nodes with a high time complexity. In contrast, MAS is suitable for distributed scenario based on multiply rounds sequential auction, which sequentially allocates relay node according to optimal bid price with low time complexity. Numerical results have validated that our proposed schemes can significantly improve the network performance compared with the existing work which ignore the cooperation interference.

As an important metric, delay is worth noticing when the studied cooperative communications is deployed in a real-time based network scenario. In order to decline delay, some relay nodes should be employed even they would cause the significant adverse effect. Therefore, a good tradeoff should be further investigated in the future.