Truthful Relay Assignment for Cooperative Communication in Wireless Networks with Selfish Source-Destination Pairs

Abstract

Cooperative communication is shown to be a promising technology to significantly increase the capacity of wireless networks. Due to the competition among multiple source-destination pairs for the same relay node set in the relay assignment problem, each pair may cheat others to achieve a more individual revenue. However, the cheating behavior may decrease the overall performance of the network greatly. Thus, there is a challenge for designing a truthful protocol that maximizes a pair's payoff only when this pair reveals its true individual information. In this paper, we propose a relay assignment protocol (RA-VCG) for cooperative communication to maximize the total social value (i.e., the total true value of all pairs) while guaranteeing truthfulness in an auction-theoretic sense by charging each pair an extra payment. Specially, RA-VCG implements a variation of the well-known VCG mechanism for the truthful relay assignment problem in the network with selfish source-destination pairs. Then, we prove the validity of this protocol and also show several surprising properties (such as no positive transfer and individual rationality) associated with this protocol. The simulation results show that the total social value achieved when each node takes untruthfully is about 23.3% less than that achieved when nodes behave truthfully.

1. Introduction

In recent years, there are growing interests in the idea of employing cooperative communication (CC) [1–4] to improve the performance of wireless networks. Spatial diversity has been shown to be very effective in copping fading in wireless channel by employing multiple transceiver antennas on a wireless node (i.e., MIMO). However, it may be infeasible for equipping multiple antennas on a wireless node in practice, as the footprint of multiple antennas may not fit on a wireless node, especially the wireless small-size device [5, 6]. In order to achieve spatial diversity without multiple antennas on the same node, the CC has been proposed in [1] by using distributed single antenna nodes. Under CC, each node is equipped with only a single antenna and can use the antennas on other (relay) nodes to achieve the spatial diversity.

There are two categories of CC modes: amplify-and-forward (AF) and decode-and-forward (DF) [1]. In AF mode, the relay node only performs a linear operation on the signal received from the source node, and then forwards it to the destination node. In DF mode, the relay node firstly decodes the signal received from the source node, and then forwards the reencoded signal to the destination node. Regardless of AF and DF, the choice of a relay node will affect the performance of CC greatly [3–5]. As shown in Section 3, an improperly relay node may make the performance of CC for a source-destination pair be worse than that of direct transmission (DT).

The previous works [2, 4–9] mainly studied the relay assignment problem for CC in the network where multiple source-destination pairs compete for the same pool of relay nodes without any cheating. However, for a source-destination pair, employing different relay nodes will achieve a different performance and the difference is very apparent. Moreover, the physical limitations of many transceivers prohibit them from transmitting data on multiple channels at the same time, so that each relay node can serve for at most one pair. These features promote the competition among all pairs, where each pair will cheat the others to get a better relay node so that it can achieve a more individual revenue. However, these selfish source-destination pairs may make the total social value (i.e., the total true value of all pairs and the true value of each pair will be defined in Section 3) very low because of cheating.

Next, we illustrate the harm caused by cheating in a network example. As shown in Figure 1, the number in each triangle denotes the true value (which will be defined in Section 3) of CC for the source-destination pair employing the corresponding relay node. For example, if pair $s_{1} - d_{1}$ denoted as $t_{1}$ employs relay node $r_{1}$ to use CC, the final true value is 10. From Figure 1, we can see that both pair $t_{1}$ and $t_{2}$ want to choose $r_{2}$ as a relay node, because both $t_{1}$ and $t_{2}$ can achieve the maximum individual true value by employing $r_{2}$ as relay node. However, due to the fact that there is only one pair can employ $r_{2}$ as relay node, then $t_{1}$ and $t_{2}$ will cheat each other. Assume that $t_{1}$ claims the values for employing relay nodes $r_{1}$ and $r_{2}$ are 5 and 30, respectively. Then $t_{2}$ may claim that the value for employing relay nodes $r_{2}$ and $r_{3}$ are 36 and 8. Since the objective is to maximize the total social value, $t_{1}$ will get $r_{1}$ and $t_{2}$ will get $r_{2}$ . As a result, the real total social value is only $18 + 10 = 28$ because of cheating. However, if all pairs claim truthfully, then the maximal total social value is 36. Obviously, the cheating behavior decreases the performance of network.

Figure 1

Illustration of attractive cheating.

Thus, there is a challenge for designing a truthful protocol that maximizes a source-destination pair's payoff (utility) only when this pair reveals its true individual value. So, we study the truthful relay assignment problem for CC in wireless networks where multiple selfish source-destination pairs compete for the same pool of relay nodes. Specially, our goal is to design a protocol that maximizes the total social value of all pairs while guaranteeing truthfulness.

The main contributions of this paper are the following.

(i)

We point out that there are cheating behaviors among some pairs, and we also give several main cheating possibilities for each pair in relay assignment problem. So, we defined a truthful relay assignment problem in this paper where each source-destination pair is selfish and it can cheat each other to get a more individual revenue.

(ii)

We design a protocol for truthful relay assignment problem called RA-VCG to maximize the total social value of all pairs while guaranteeing truthfulness. This protocol implements a variation of the well-known VCG mechanism. In order to guarantee truthfulness, RA-VCG will charge each pair a payment such that a source-destination pair's payoff will be maximized only when this pair reveals its true individual value.

(iii)

We also prove that our protocol can achieve the maximum total social value for all source-destination pairs while guaranteeing truthfulness. Moreover, there are several another nice properties (such as no positive transfer and individually rationality) associated with RA-VCG.

(iv)

The simulation results show that the total social value achieved when each node takes untruthful behaviors is about 23.3% less than that achieved when nodes behave truthfully in RA-VCG.

The rest of this paper is organized as follows. We review the literature work in Section 2. Section 3 describes the system model and problem definition. In Section 4, we present RA-VCG protocol in detail. In Section 5, we prove the correctness of this protocol in terms of maximizing total social value and truthfulness. The simulation results are presented in Section 6. Section 7 concludes this paper.

2. Related Work

It is possible for a source-destination pair to employ multiple relay nodes to use CC, but the benefit of this approach is limited. In [3], Zhao et al. showed that it is sufficient to choose the “best” relay node to achieve full diversity order than to employ multiple relay nodes for a pair. Therefore, it paved the way for research on assigning at most one relay node to a pair and we will adopt this setting in this paper. However, this work [3] is limited to a single pair and cannot be easily extended to multiple source-destination pairs’ situation.

Then, we will review the related works on the relay assignment problem with multiple source-destination pairs for CC. In [2], Ng and Yu gave a utility maximization problem for the joint optimization of relay assignment, resource allocation, and CC modes selection in a cellular network. Then, Kadloor and Adve [7] formulated a related convex optimization problem for the relay selection and power allocation problem. However, these two works assume that each relay node has infinite number of channels so as to help multiple pairs, but this setting will not always hold in practice where the number of a relay node's channels is limited.

There are also some works studied the relay assignment problem with the setting that each relay node can be assigned to at most one pair. Zhang et al. [8] investigate the relay assignment problem in the wireless network where the number of relays equals or exceeds the number of source-destination pairs. However, this assumption may not always hold in practice where the number of relay nodes is less than that of source-destination pairs. In [4], Cai et al. studied the joint relay node selection and power allocation for AF mode so as to maximize the network throughput both for the network environment with a single pair and multiple pairs. Shi et al. [5, 6] proposed an optimal algorithm for the relay node assignment problem to maximize the minimum capacity among all pairs. In [9], the authors studied the joint relay assignment and power allocation problem aiming to minimize the total power consumption for all nodes. However, all the above works did not consider the selfishness of the source-destination pairs, and the selfishness can greatly decrease the network performance.

Specially, Li et al. [10] studied the relay assignment problem in cooperative wireless networks with self-interested nodes. They modeled the cooperative relationship among the nodes as an exchange market game where nodes trade transmission power between each other to get diversity gain. However, this market mechanism faces significant challenges due to the fear of market manipulation. Moreover, the authors in [10] assumed that there is no difference between any assisted nodes (relay nodes) from the point of each node (source-destination pair). But in fact the performance of each pair by employing different relay nodes will be different in practice. This feature causes the competition among multiple pairs, and each pair will cheat the others so as to get its favorite relay node.

The works about scheme design in [11–15] are most related to our work. Shastry and Adve [13] proposed a pricing-based system to stimulate the cooperation via payment, in order to ensure both the access point and the relay nodes benefit from cooperation. Wang et al. [14] employed a buyer/seller Stackelberg game, where a buyer announced its selection of relays and the required transmission power, then the relays asked proper prices to maximize their profits. In [15], Huang et al. proposed two repeated games. In each game, each user iteratively updated its bid to maximize its own utility function with the knowledge of others previous bids. However, all the above schemes cannot guarantee the optimal total social value. In [12], Yang et al. proposed a truthful auction scheme for cooperative communications. This scheme satisfies truthfulness, individual rationality, and budget balance properties in the same time. Similarly, this scheme also cannot guarantee the optimal total social value. Moreover, in this scheme, the authors assumed that all pairs knew the capacity of other pairs in the network so as to get an initial relay assignment solution, but each pair might cheat the others about its capacity to get its favorite relay node in practice. In [11], Yang et al. proposed a robust scheme to prevent selfish behavior of source nodes and cheating behavior of relay nodes while guaranteeing the social optimal system capacity. However, this paper assumed that the information of each source node was known by all other source nodes, and thus did not consider the truthfulness of source nodes. In fact, each source node might cheat the others to get its favorite relay node.

Since VCG mechanism is effective in preventing cheating, there are many works to use VCG mechanism in wireless networks to guarantee truthfulness. Such as Anderegg and Eidenbenz [16] proposed a routing protocol which implemented a variation of VCG mechanism so as to find the most cost-efficient path. In [17], the authors investigated how to use VCG mechanism to allocate and price spectrum resource. Shu and Varaiya [18] proposed a VCG mechanism-based access control mechanism for packet traffic. Therefore, in order to prevent the cheating among some pairs, we implement a variation of VCG mechanism to guarantee truthfulness in this paper. Specially, we study the truthful relay assignment problem for CC in wireless networks where multiple selfish source-destination pairs compete for the same pool of relay nodes.

3. System Model

3.1. Cooperative Communication Model

The essence of CC can be shown by a simple example in Figure 2, where source node s potentially transmits to the destination node d with the help of relay node r. This transmission is done on a frame-by-frame basis and there are two time slots in a frame [1, 5, 6]. In the first time slot, source node s transmits a signal to destination node d, and this signal is also overheard by the relay node r. In the second time slot, the relay node r forwards the signal received in the first time slot to the destination node d. Now, node d can use a diversity combining technique on two copies of the data from two different paths to increase the capacity gain.

Figure 2

A simple example for cooperative communication.

Assume source node s sends a data to destination node d with the transmitting power $P_{s}^{tra}$ . Let $h_{s d}$ capture the effect of path loss, shadowing and fading between nodes s and d, and then the received energy at the destination node d is

\begin{matrix} P_{s, d}^{rec} = P_{s}^{tra} * {| h_{s d} |}^{2} . \end{matrix}

(1)

So, the signal noise ratio (SNR) [5, 6] at the destination d is

\begin{matrix} {SNR}_{s, d} = \frac{P_{s}^{tra} * {| h_{s d} |}^{2}}{σ_{d}^{2}} = \frac{P_{s, d}^{rec}}{σ_{d}^{2}}, \end{matrix}

(2)

where $σ_{d}^{2}$ is the variance of the background noise at node d. Note that only destination node d knows the ${SNR}_{s, d}$ , and node s have no knowledge about ${SNR}_{s, d}$ .

In AF mode, relay r simply amplifies the signal received from node s in the first time slot and then forwards it to node d in the next slot. The achievable AF capacity is given by [1]

\begin{matrix} C_{AF} (s, r, d) = \frac{W}{2} \log_{2} (1 + {SNR}_{s, d} + \frac{{SNR}_{s, r} \cdot {SNR}_{r, d}}{{SNR}_{s, r} + {SNR}_{r, d} + 1}), \end{matrix}

(3)

where W is the bandwidth.

In DF mode, relay r decodes and estimates the signal from node s in the first time slot, and then forwards the reencoded estimated signal to node d in the next slot. The DF capacity shown in [1] is

\begin{array}{l} C_{DF} (s, r, d) = \frac{W}{2} \min {\log_{2} (1 + {SNR}_{s, r}), \\ \log_{2} (1 + {SNR}_{s, d} + {SNR}_{r, d})} . \end{array}

(4)

When CC (i.e., relay node r) is not used, node s transmits directly to node d in both two time slots. Thus, the capacity of direct transmissions (DT) is

\begin{matrix} C_{DT} (s, d) = W \log_{2} (1 + {SNR}_{s, d}) . \end{matrix}

(5)

From the above results, we have three observations.

(i)

Comparing $C_{AF}$ (or $C_{DF}$ ) to $C_{DT}$ , it is hard to say that the capacity of CC is always larger than that of DT. In fact, a poor selection of relay node may cause the capacity of CC smaller than that of DT for a single source-destination pair. So, this fact indicates the significance of relay selection in CC and also causes the competition among multiple pairs for the same relay node set.

(ii)

The capacity is a monotonic increasing function of the transmission power under all the communication modes (AF, DF, and DT). Therefore, both source node and relay node should transmit at the maximum power so as to achieve the maximum capacity. So, we let $P_{s}^{tra} = P_{r}^{tra} = P_{\max} = P$ in this paper.

(iii)

The capacities for AF and DF have the same form (i.e., a function of ${SNR}_{s, d}$ , ${SNR}_{s, r}$ , and ${SNR}_{r, d}$ ). Therefore, the algorithm designed for AF mode can be easily extended to DF mode scheme, vice versa.

3.2. Truthful Relay Assignment Problem

We consider a wireless network consisting of N nodes, where there are four subsets of nodes: (1) the set of source nodes, $𝒮 = {s_{1}, s_{2}, \dots s_{N_{s}}}$ , with $| 𝒮 | = N_{s}$ , (2) the set of destination nodes, $𝒟 = {d_{1}, d_{2}, \dots d_{N_{d}}}$ , with $| 𝒟 | = N_{d}$ , (3) the set of remaining potentially relay nodes except the assignment node, $ℛ' = {r_{1}, r_{2}, \dots r_{N_{r} - 1}}$ , with $| ℛ' | = N_{r} - 1$ , and (4) the set of an assignment node, $𝒜 = {A}$ , with $| 𝒜 | = 1$ (see Figure 3). Note that the assignment node A is a special potentially trusted relay node in charge of assigning relay node to each source-destination pair, and deciding the corresponding payment. Specially, we can denote the assignment node A as $r_{N_{r}}$ . So, the set of available relay nodes can be denoted as $ℛ = {r_{1}, r_{2}, \dots r_{N_{r} - 1}, r_{N_{r}} = (A)}$ with $| ℛ | = N_{r}$ .

Figure 3

The wireless network in our model.

For clarity, we consider unicast where each source node $s_{i}$ is paired with a destination node $d_{i}$ , that is, $N_{s} = N_{d}$ , and we also assume that all nodes are assumed to be within range of each other. Specially, we denote the source-destination pair from $s_{i}$ to $d_{i}$ ( $1 \leq i \leq n$ ) as $t_{i}$ , and so the source-destination pair set is $𝒯 = {t_{1}, t_{2}, \dots t_{N_{s}}}$ , with $| 𝒯 | = N_{s}$ . Further, in order to avoid interference, we employ the orthogonal channels in the network (e.g., using OFDMA), which is also used in Laneman et al.'s [1] for CC. We also assume that the channel state is stable, that is, also assumed by the authors in [5, 6] for relay assignment problem. Moreover, each node is equipped with a single antenna and can transmit/receive within one channel at a time so that each relay node can serve for at most one pair. Specially, Zhao et al. [3] showed that it is sufficient to choose the “best” relay node to achieve full diversity order than to employ multiple relay nodes for a pair. Thus, it paved the way for research on assigning at most one relay node to a source-destination pair and we will adopt this setting in this paper.

More formally, we use $R (t_{i})$ to denote the relay node employed by the pair $t_{i}$ . In the case that $t_{i}$ does not employ a relay node where $t_{i}$ transmits with DT, we have $R (t_{i}) = ϕ$ . So, the capacity of pair $t_{i}$ can be rewritten as

\begin{matrix} C_{R} (t_{i}, R (t_{i})) = {\begin{cases} C_{XF} (s_{i}, R (t_{i}), d_{i}), & if R (t_{i}) \neq ϕ, \\ C_{DT} (s_{i}, d_{i}), & if R (t_{i}) = ϕ, \end{cases} \end{matrix}

(6)

with $C_{XF} (\cdot) = C_{AF} (\cdot)$ for AF and $C_{XF} (\cdot) = C_{DF} (\cdot)$ for DF.

We propose to model the true value of a source-destination pair through a parameter: the value-of-capacity parameter $v_{i}$ of dollars per mbps (similar to the cost parameter: the cost-of-energy parameter $c_{i}$ dollars per watt proposed in [16]) is individual for each pair in the network, and this parameter reflects the value of each pair for the unit capacity. Therefore, the true value of pair $t_{i}$ by employing relay node $R (t_{i})$ is

\begin{matrix} V (t_{i}, R (t_{i})) = {\begin{cases} v_{i} * C_{XF} (s_{i}, R (t_{i}), d_{i}), & if R (t_{i}) \neq ϕ, \\ v_{i} * C_{DT} (s_{i}, d_{i}), & if R (t_{i}) = ϕ . \end{cases} \end{matrix}

(7)

We assume that there is no collusion in the wireless network and that each pair wants to employ its favorite relay so as to maximize its individual revenue. However, the favorite relay node of some pairs may be the same one (e.g., in Figure 3, $r_{3}$ may be the favorite relay node of pairs $t_{1}$ and $t_{2}$ ; $r_{6}$ may be the favorite relay node of $t_{3}$ , $t_{4}$ , and $t_{5}$ ), and this feature will cause the competition among some pairs. Thus, each pair will try to cheat the others so as to get its favorite relay node, and this will significantly decrease the total social value. For clarity, we regard all relay nodes are truthful and this assumption is reasonable in the energy-abundance networks. Because there is no loss for each relay node to serve for a pair using CC except some energy consumption.

Specially, our objective is to design a relay assignment protocol to find a relay assignment result that maximizes the total social value:

\begin{matrix} \max \sum_{i = 1}^{N_{s}} ‍ V (t_{i}, R (t_{i})), \end{matrix}

(8)

and causes all source-destination pairs to act truthfully, that is, to reveal their true values, where $R (t_{i})$ is denoted as the corresponding relay node assigned to source-destination pair $t_{i}$ by this protocol.

In order to guarantee truthfulness, the assignment node will charge each pair a payment (virtual money) in the protocol such that a source-destination pair's payoff will be maximized only when it reveals its true individual value. The payment determination for each pair will be presented in Section 4.3.

As with other truthful protocols in wireless networks, we assume a payment mechansm [19] that takes charge of accounting and transferring payments between nodes. There is also a tamper-proof hardware [20] which can protect virtual money from modification or other attacks. Note that, conceptually we could also think that the payments can be funded by the entities which own the wireless devices. However, we focus on effective truthful relay assignment problem in this paper. Other issues about the virtual money, securely crediting and transferring money are beyond the scope of this paper.

Note that this network model might correspond to a snapshot of a wireless network. For example, in the context of a Cognitive Radio Network (CRN) which consists of some second users and a primer user, each user also have a source node (device) and a paired destination node (device). When the primer user does not use its own spectrum in a period of time, it will divide its spectrum to some second users so as to maximize total social value. Thus, the assignment node corresponding to the destination node (or source node) of the primer node; the source-destination pairs correspond to the occupied second users that have data to transmit; the available relay nodes corresponding to the unoccupied second users’ source node or destination node which do not have data to transmit. Moreover, every unoccupied second user is willing to participate in cooperative communication, so that the others can help this user when it has data to transmit. Specially, the primer node can also enforce each unoccupied user to participate in CC; otherwise, the primer user does not allow this pair to use its spectrum forever. Note that, in this paper, every node in the network only serve as one role in a period of time and we focus on the relay assignment in this period of time. Moreover, the role of each node may change in the next period of time, and it needs to reexecute the protocol designed in this paper. From above, when a primer user tries to divide its spectrum to some second users so as to maximize total social value in CRN, there are two important issues that need to be solved. One is spectrum allocation, where the primer user decides how to divide and allocate its spectrum. The other is relay assignment, where the primer user decides how to assign relay nodes (unoccupied second user) to source-destination pairs (occupied second users). Specially, in this paper, we focus on relay assignment problem and omit spectrum allocation problem. However, we will jointly consider spectrum allocation and relay assignment problem for cooperative communication in CRN in the future.

4. Truthful Relay Assignment Protocol

In order to achieve truthfulness, we design a truthful relay assignment protocol (RA-VCG) which implements a variation of the well-known VCG mechanism for CC in wireless networks. RA-VCG will charge each pair a payment (virtual money) such that a source-destination pair's payoff will be maximized only when it reveals its true individual value.

4.1. Basic Idea

Figure 4 shows the flow chart of RA-VCG. This protocol consists of the following three phases:

(1)

relay discovery,

(2)

relay assignment,

(3)

data transmission.

Figure 4

The flow chart of RA-VCG protocol.

In relay discovery phase, the assignment node will first broadcast a message to inform all the source nodes to select relay nodes. Then, each source node will send a message to find the corresponding relay node. Next, each relay node will forward the message from the source node to its corresponding destination node. After that, each destination node can compute the true value $V (t_{i}, R (t_{i}))$ by (7) and send this information to the assignment node (Algorithm 1).

Algorithm 1: Relay discovery phase.

1.Initialization step:

Each destination node $d_{i}$ creates a message BID $(s_{i}, d_{i}, v_{i})$ and a message queue $Q_{i}$ ;

Assignment node A broadcasts a message START(A).

2. Process Step:

2.1. Source node $s_{i}$

On receiving the message START(A)

Broadcast a message RTEST( $s_{i}, d_{i}$ ).

2.2 Relay node $r_{j}$ (including assignment node A)

On receiving the message RTEST( $s_{i}, d_{i}$ )

Determine the received power $P_{s_{i}, r_{j}}^{rec}$ . and compute the $SN R_{S_{i}, r_{j}}$ ;

Send a message RREP( $s_{i}, d_{i}, r_{j}, SN R_{S_{i}, r_{j}}$ ) to the destination node $d_{i}$ .

2.3. Destination node $d_{i}$

On receiving the message RREP( $s_{i}, d_{i}, r_{j}, SN R_{S_{i}, r_{j}}$ )

Determine the received power $P_{r_{j}, d_{i}}^{rec}$ , and compute $S N R_{r_{j}, d_{i}}$ ;

if $d_{i}$ has not received the message RTEST( $s_{i}, d_{i}$ ) from

its paired source node $s_{i}$ then

Append $SN R_{r_{j}, d_{i}}$ to this RREP message;

Push the appended message to queue $Q_{i}$ ;

else

Compute $C_{XT} (s_{i}, r_{j}, d_{i})$ ;

Append the BID packet by $r_{j}$ and $C_{XT} (s_{i}, r_{j}, d_{i})$ .

end if

On receiving the message RTEST( $s_{i}, d_{i}$ )

Determine the received power $P_{s_{i}, d_{i}}^{rec}$ . and compute $SN R_{s_{i}, d_{i}}$ ;

Compute $C_{DT} (s_{i}, d_{i})$ ;

Append the BID packet by $C_{DT} (s_{i}, d_{i})$ ;

for each message RREP( $s_{i}, d_{i}, r_{j}, SN R_{S_{i}, r_{j}}, SN R_{r_{j}, d_{i}}$ ) in $Q_{i}$ do

Compute $C_{XT}$ ( $s_{i}, r_{j}, d_{i}$ );

Append the BID message by $r_{j}$ and $CXT (s_{i}, r_{j}, d_{i})$ .

end for

On receive all the RREP messages and the corresponding RTEST message

Send the BID message to the assignment node A.

In the relay assignment phase, the assignment node will determine the final relay assignment result according to all the information sent by the destination nodes. After that, the assignment node also decides the payments for each pair to guarantee truthfulness.

In data transmission phase, each pair pays the payment and starts transmitting data. Next, we will present our RA-VCG protocol in detail.

4.2. Relay Discovery

We introduced a trusted node called assignment node to the network, which takes charge of assigning relay nodes and deciding the corresponding payments for each pair. For example, in the CRN, the assignment node corresponds to the primer user who shares his spectrum to some second users so as to maximize the total social value. Specially, if there is not a primer node in the network, we can designate a relay node as the assignment node.

In the beginning, the assignment node will broadcast a message $START (A)$ with the maximum transmission power P, where A is the ID of the assignment node. If a node (source node, destination node, or potentially relay node) receives the message $START (A)$ , it will know that A is the assignment node. Specially, if this node is a source node $s_{i}$ , it will broadcast a relay test message $RTEST (s_{i}, d_{i})$ with its maximum transmission power, where $s_{i}$ is the ID of this source node and $d_{i}$ is the ID of the destination node paired with $s_{i}$ .

Each potentially relay node $r_{j}$ (including the assignment node A) that receives a message $RTEST (s_{i}, d_{i})$ from a source node $s_{i}$ executes the following operations:

(1)

determine the received power $P_{s_{i}, r_{j}}^{rec}$ and compute the ${SNR}_{s_{i}, r_{j}}$ by (2);

(2)

send a relay reply message RREP( $s_{i}$ , $d_{i}$ , $r_{j}$ , ${SNR}_{s_{i}, r_{j}}$ ) with its maximum transmission power to the corresponding destination node $d_{i}$ in the RTEST message.

For each destination node $d_{i}$ , it first creates a message queue $Q_{i}$ and a message $BID (s_{i}, d_{i}, v_{i})$ , where $s_{i}$ is the ID of its paired source node and $v_{i}$ is the individual value-of-capacity parameter of this pair $t_{i}$ . On receiving a message $RREP (s_{i}, d_{i}, r_{j}, {SNR}_{s_{i}, r_{j}})$ form potentially relay node $r_{j}$ , the destination node $d_{i}$ will execute the following operations:

(1)

determine the received power $P_{r_{j}, d_{i}}^{rec}$ and compute the ${SNR}_{r_{j}, d_{i}}$ ;

(2)

if $d_{i}$ has not received the message $RTEST (s_{i}, d_{i})$ from its paired source node $s_{i}$ , then append ${SNR}_{r_{j}, d_{i}}$ to this message as $RREP (s_{i}, d_{i}, r_{j}, {SNR}_{s_{i}, r_{j}}, {SNR}_{r_{j}, d_{i}})$ . Then push the appended message to the message queue $Q_{i}$ ;

(3)

if $d_{i}$ has received the message $RTEST (s_{i}, d_{i})$ from source node $s_{i}$ , it uses ${SNR}_{s_{i}, r_{j}}$ , ${SNR}_{r_{j}, d_{i}}$ , and ${SNR}_{s_{i}, d_{i}}$ to computes the $C_{XT} (s_{i}, r_{j}, d_{i})$ by (3) or (4). Append the BID packet by adding the relay node $r_{j}$ and the corresponding capacity $C_{XT} (s_{i}, r_{j}, d_{i})$ .

Once the destination node $d_{i}$ receives the message $RTEST (s_{i}, d_{i})$ from its paired source node $s_{i}$ , it will execute the following operations:

(1)

determine the received power $P_{s_{i}, d_{i}}^{rec}$ and compute the ${SNR}_{s_{i}, d_{i}}$ by (2), and then compute the $C_{DT} (s_{i}, d_{i})$ by (5). Append the BID packet by adding $C_{DT} (s_{i}, d_{i})$ ;

(2)

for each message $RREP (s_{i}, d_{i}, r_{j}, {SNR}_{s_{i}, r_{j}}, {SNR}_{r_{j}, d_{i}})$ in $Q_{i}$ , use ${SNR}_{s_{i}, r_{j}}$ , ${SNR}_{r_{j}, d_{i}}$ , and ${SNR}_{s_{i}, d_{i}}$ to compute $C_{XT} (s_{i}, r_{j}, d_{i})$ by (3) or (4). Then append the BID message by $r_{j}$ and $C_{XT} (s_{i}, r_{j}, d_{i})$ .

After the destination node $d_{i}$ has already received all the RREP message from each potentially relay node $r_{j}$ and the RTEST message from its paired source node $s_{i}$ , it will derive a message whose format is $BID (s_{i}, d_{i}, v_{i}, C_{DT} (s_{i}, d_{i}), r_{j_{1}}, C_{XT} (s_{i}, r_{j_{1}}, d_{i}), \dots, r_{j_{N_{r}}}, C_{XT} (s_{i}, r_{j_{N_{r}}}, d_{i}))$ , and then send this BID message to the assignment node A. Note that, we assume that there is no packet loss in RA-VCG. This assumption is also reasonable because there is too many works providing the reliable packet transmitting.

4.3. Relay Assignment

After the relay discovery phase, all the destination nodes (source-destination pairs) have sent BID messages to the assignment node A that collects all the arriving BID messages. Then the assignment node A will perform an algorithm called truthful relay assignment (TRA) algorithm. In TRA, the assignment node A will first perform an optimal polynomial-time algorithm, called relay assignment (RA) to maximize the total social value by assigning relay nodes to each pair; after that, the VCG-payment of each pair is also determined by the assignment node A to guarantee truthfulness.

The essence of RA algorithm is the maximum matching of weighted bipartite graph. RA algorithm consists of three steps: bipartite graph construction, saturated matching, and relay node assignment, shown in Algorithm 2.

Algorithm 2: RA( $𝒮, ℛ, 𝒟$ , flag).

Step 1. Bipartite Graph Construction

Create the vertex sets X and Y;

for each message BID( $s_{i}$ ; $d_{i}$ , $v_{i}$ , $C_{DT}$ ( $s_{i}$ , $d_{i}$ ), $r_{j 1}$ ,

$C_{XT}$ ( $s_{i}, r_{j_{1}}, d_{i}$ ), …, $r_{{j_{N}}_{r}}, C_{XT}$ ( $s_{i}, r_{{j_{N}}_{r}}, d_{i}$ )) and $s_{i}$ ϵ𝒮

w( $x_{i}, y_{i}^{'}$ ) = $v_{i}$ * $C_{DT} (s_{i}, d_{i})$ ;

for k = 1 to $N_{r}$ do

w( $x_{i}$ , $y_{j_{k}}$ ) = $v_{i}$ * $C_{XT} (s_{i}, r_{j_{k}}, d_{i})$ ;

end for

Step 2. Saturated Matching

Adopt KM algorithm to find a saturated matching in Graph

G; Assume that vertex $x_{i}$ is matched to vertex $M (x_{i})$ ;

Step 3. Relay Node Assignment

for each $s_{i}$ ϵ𝒮 do

if flag = true then

if M( $x_{i}$ ) = $y_{j}$ then

$R (t_{i})$ = $r_{j}$ ;

else

$R (t_{i})$ = ϕ;

end if

result+ = w $(x_{i}, M (x_{i}))$ ;

end for

Return result;

At first, RA algorithm builds up the following weighted bipartite graph $G = (V, E, w)$ based on the all BID messages and the input parameters: source node set 𝒮, available relay node set ℛ, and destination node set 𝒟. The graph G contains two independent vertex sets X and Y, where $| X | = | 𝒮 |$ and $| Y | = | ℛ | + | 𝒟 |$ . Without loss of generality, assume that $X = {x_{i} ∣ s_{i} \in 𝒮, 1 \leq i \leq N_{s}}$ where each vertex $x_{i}$ represents the corresponding source node $s_{i}$ , as well as $Y = {y_{j} ∣ r_{j} \in ℛ, 1 \leq j \leq N_{r}} \cup {y_{i}^{'} ∣ d_{i} \in 𝒟, 1 \leq i \leq N_{s}}$ where each vertex $y_{j}$ represents the corresponding potentially relay nodes $r_{j}$ and each vertex $y_{i}^{'}$ represents the corresponding destination node $d_{i}$ . Based on the above, we will define the weights of the edges in the graph G. For each message $BID (s_{i}, d_{i}, v_{i}, C_{DT} (s_{i}, d_{i}), r_{j_{1}}, C_{XT} (s_{i}, r_{j_{1}}, d_{i}), \dots, r_{j_{N_{r}}}, C_{XT} (s_{i}, r_{j_{N_{r}}}, d_{i}))$ , we will define the corresponding weights as follows:

\begin{matrix} w (x_{i}, y_{i}^{'}) = v_{i} * C_{DT} (s_{i}, d_{i}), \\ w (x_{i}, y_{j_{k}}) = v_{i} * C_{XT} (s_{i}, r_{j_{k}}, d_{i}), 1 \leq k \leq N_{r} . \end{matrix}

(9)

Now, a bipartite graph G has been constructed. Thus, the second step is to adopt the well-known KM algorithm [9, 21] to find out an optimal saturated matching for G, that is, the total weight of all the matched edges is maximized. After the second step, each vertex $x_{i}$ will be matched to a vertex $M (x_{i})$ in Y. Here, RA decides whether to assign relay nodes to each pair through the parameter flag. If flag is true, then assign relay nodes to each pair; otherwise, only return the total social value without relay assignment. Specially, when flag is true, if $M (x_{i}) = y_{j}$ , then the source-destination pair $t_{i}$ will employ relay node $r_{j}$ to use CC; If $M (x_{i}) = y_{i}^{'}$ , then the pair $t_{i}$ will use DT. Thus, we have

\begin{matrix} R (t_{i}) = {\begin{cases} r_{j}, & if M (x_{i}) = y_{j}, \\ ϕ, & if M (x_{i}) = y_{i}^{'} . \end{cases} \end{matrix}

(10)

RA algorithm is only a subroutine of TRA algorithm which has been shown in Algorithm 3. After performing the RA algorithm, the assignment node has assigned relay nodes for each pair. Then, it will also determine the VCG-payment for each pair to guarantee truthfulness. The VCG-payment for each pair is the harm that it causes to the rest of other pairs and we can formulate it as

\begin{array}{l} pay (t_{i}) = RA (𝒮 ∖ {s_{i}}, ℛ, 𝒟 ∖ {d_{i}}, false) \\ - RA (𝒮 ∖ {s_{i}}, ℛ ∖ {R (t_{i})}, 𝒟 ∖ {d_{i}}, false), \end{array}

(11)

where $𝒮 ∖ {s_{i}}$ denotes that $s_{i}$ is removed from 𝒮. For simplicity, we will use the notations $M_{𝒮, ℛ}^{𝒟}$ to denote $RA (𝒮, ℛ, 𝒟, false)$ . Thus, the payment of $t_{i}$ can be rewritten as follows:

\begin{matrix} pay (t_{i}) = M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} - M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R (t_{i})}} . \end{matrix}

(12)

Algorithm 3: TRA.

RA( $𝒮, ℛ, 𝒟, true$ );

for i = 1 to $N_{s}$ do

first = RA( $𝒮 ∖ {s_{i}}, ℛ, 𝒟 ∖ {d_{i}}, false$ );

second = RA( $𝒮 ∖ {s_{i}}, ℛ ∖ {ℛ (t_{i})}, 𝒟 ∖ {d_{i}}, false$ );

pay $(t_{i})$ = first-second

end for

In (11) or (12), the first term is the total social value should the corresponding source node $s_{i}$ and destination node $d_{i}$ of pair $t_{i}$ be removed from 𝒮 and 𝒟, respectively; the second term is the total social value should $s_{i}$ , $R (t_{i})$ and $d_{i}$ be removed from 𝒮, ℛ and 𝒟, respectively. Hence, the first term is the total social value received by all the other pairs when pair $t_{i}$ did not participate in relay assignment, and the second term is the total social value received by all the other pairs when $t_{i}$ participate in relay assignment. So $pay (t_{i})$ is the total harm caused by $t_{i}$ .

As a result, the assignment node has completed relay assignment and also decides the VCG-payment for each pair after performing TRA algorithm. So, it will broadcast the result by a message $RA - RESULT (t_{1}, R (t_{1}), pay (t_{1}), t_{2}, R (t_{2}), pay (t_{2}), \dots, t_{N_{s}}, R (t_{N_{s}}), pay (t_{N_{s}}))$ to all nodes in the network.

4.4. Data Transmission

When the pair $t_{i}$ receives the message RA-RESULT, if $R (t_{i}) \neq ϕ$ , it will pay the payment $pay (t_{i})$ to the relay node $R (t_{i})$ (or the assignment node A where A can get this payment alone or divide it to all the relay nodes to encourage them to participate in RA-VCG), and then start to employ the relay node $R (t_{i})$ to use CC. Otherwise, it will exploit DT.

4.5. Complexity Analysis

Now, we mainly analyze the computational complexity of TRA algorithm and the message complexity of RA-VCG.

First, let us focus on the time complexity of TRA algorithm. In the first step of RA algorithm, there are at most $N_{s} * N_{r} + N_{s}$ edges in the bipartite graph G. So, the time complexity for graph construction is $O (N_{s} * N_{r})$ . Moreover, the time complexity to find out a saturated matching for this bipartite graph G is $O (N_{s}^{2} * N_{r})$ shown in [9, 21]. Finally, it costs $O (N_{s})$ to transform the matching result into the relay assignment in the third step. So, the total time complexity of RA is $O (N_{s} * N_{r}) + O (N_{s}^{2} * N_{r}) + O (N_{s}) = O (N_{s}^{2} * N_{r})$ . In TRA algorithm, it will call RA algorithm $2 * N_{s} + 1$ times and so the time complexity of TRA is $O (N_{s}^{3} * N_{r})$ .

Next, we will focus on the message complexity of RA-VCG. In the relay discovery phase, the assignment node A sends a START message. Then each source node send a corresponding RTEST message after receiving the START message from assignment node A and so there are $N_{s}$ RTEST messages in total. After that, each relay node will forward an RREP message for each source node to its paired destination node. Thus, the number of the total RREP messages is $N_{s} * N_{r}$ . At last, each destination node sends a BID message to assignment node A and thus there are $N_{d}$ BID messages in total. After the TRA algorithm, there is also one RA-RESULT sent by assignment node A to broadcast the relay assignment result. Thus, there are $1 + N_{s} + N_{s} * N_{r} + N_{d} + 1 = 2 + 2 N_{s} + N_{s} * N_{r}$ messages in total. So, the message complexity of RA-VCG is $O (N_{s} * N_{r})$ .

5. Analysis

In this section, we show that RA-VCG meets the design requirements of maximizing the total social value and truthfulness in the presence of selfish source-destination pairs. We also show that our RA-VCG protocol has other nice properties.

Lemma 1.

If all source-destination pairs act truthfully, that is, reveal its true information in BID message, and then RA or TRA algorithm can find out an optimal relay assignment result which maximizes the total social value.

Proof.

The assignment node in RA-VCG collects all BID messages, and then converts the relay assignment problem to an optimal saturated matching problem in weighted bipartite graph based on these messages. If each pair acts truthfully, then the optimal saturated matching found by KM algorithm can also be converted to an optimal relay assignment result that maximizes the total social value. So, the lemma holds.

From Lemma 1, we can see that maximizing the total social value of RA-VCG follows immediately from the description of RA-VCG, if we can guarantee truthfulness of each pair. Thus, now we will show that the RA-VCG can guarantee truthfulness. Specially, showing that RA-VCG is truthful is more involved. Truthfulness is given if and only if it is a dominant strategy for each pair $t_{i}$ to always

(i)

declare its true value-of-capacity parameter $v_{i}$ in its BID message;

(ii)

correctly compute and declare its capacity of DT;

(iii)

correctly compute and declare its capacity of CC for all relay nodes (including both its desired relay node and undesired relay nodes) in BID message.

We call all these items “cheating possibilities”.

In accordance with the definition of dominant strategies, we assume an adversarial pair to be omniscient: an omniscient pair knows all edge weight of the bipartite graph. Our protocol is truthful only if even such a powerful pair cannot use its knowledge to its own advantage. The reason for using such a strong adversarial model is to prevent some pairs from taking bets based on their partial knowledge of the network.

Lemma 2.

In RA-VCG, each source-destination pair $t_{i}$ declares its true information in BID message.

Proof.

We use ${BID}_{t_{i}}$ to denote the BID messages declared by pair $t_{i}$ and use ${BID}_{𝒯 ∖ t_{i}}$ to denote the BID messages declared by all the other pairs except $t_{i}$ . Then, for pair $t_{i}$ , if all other pairs declare ${BID}_{𝒯 ∖ t_{i}}$ , we show that $t_{i}$ can maximize its utility only when it reveals its true individual value according to ${BID}_{t_{i}}$ . So, the cheating behaviors will not increase the utility (payoff) of each pair. The utility (payoff) of the pair $t_{i}$ is the true value received by exploiting the assigned relay node $R (t_{i})$ minus the payment $pay (t_{i})$ charged by RA-VCG:

\begin{matrix} U (t_{i}) = V (t_{i}, R (t_{i})) - pay (t_{i}) . \end{matrix}

(13)

There are only two cases to discuss in the following. Assume that $t_{i}$ declares its true information in ${BID}_{t_{i}}$ , and it gets its relay node $R (t_{i})$ . Thus, the true value, payment, and utility of $t_{i}$ are $V (t_{i}, R (t_{i}))$ , $pay (t_{i})$ , and $U (t_{i}) = V (t_{i}, R (t_{i})) - pay (t_{i})$ , respectively. Similarly, assume that $t_{i}$ does not declare truthfully in BID message (assume that it declares ${BID}_{t_{i}}^{'}$ and ${BID}_{t_{i}}^{'} \neq {BID}_{t_{i}}$ ), that is, does not satisfy all the “cheating possibilities,” and $t_{i}$ gets its relay node $R' (t_{i})$ . As a result, the true value, payment, and utility of $t_{i}$ are $V (t_{i}, R' (t_{i}))$ , ${pay}^{'} (t_{i})$ , and $U' (t_{i}) = V (t_{i}, R' (t_{i})) - {pay}^{'} (t_{i})$ in untruthful BID message, respectively.

In the first case, the source-destination pair $t_{i}$ receives the same relay node by declaring ${BID}_{t_{i}}$ and ${BID}_{t_{i}}^{'}$ . In this case, the payment of $t_{i}$ is also ${pay}^{'} (t_{i}) = pay (t_{i})$ (see (11)). So the utility of $t_{i}$ is $U' (t_{i}) = V (t_{i}, R' (t_{i})) - {pay}^{'} (t_{i}) = V (t_{i}, R (t_{i})) - pay (t_{i}) = U (t_{i})$ . Thus, the untruthful information in BID message has no effect on the utility of $t_{i}$ in this case.

In the second case, the source-destination pair $t_{i}$ receives a different relay node by declaring ${BID}_{t_{i}}^{'}$ , that is, $R (t_{i}) \neq R' (t_{i})$ . Hence, we must prove that $U (t_{i}) - U' (t_{i}) \geq 0$ , which shows that the utility received from truthful information in BID message is always at least that received from untruthful information BID message in this case. Joining (12) and (13), we can get that

\begin{array}{l} U (t_{i}) - U' (t_{i}) \\ = (V (t_{i}, R (t_{i})) - (M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} - M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R (t_{i})}})) \\ - (V (t_{i}, R^{'} (t_{i})) - (M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} - M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R' (t_{i})}})) \\ = (V (t_{i}, R (t_{i})) + M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R (t_{i})}}) \\ - (V (t_{i}, R^{'} (t_{i})) + M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R' (t_{i})}}), \end{array}

(14)

where the definition of parameters in (14) can be seen from (12) in Section 4.3. Note that in (14), the first term is the maximum total social value when $t_{i}$ is assigned relay node $R (t_{i})$ by declaring its true information in BID message. The second term represents (equals) the maximum total social value in the situation that $t_{i}$ declares truthful information, but for some reason $t_{i}$ is assigned relay node $R' (t_{i})$ . However, when other pairs declare ${BID}_{𝒯 ∖ t_{i}}$ and $t_{i}$ declares truthful information in its BID message, we have already assumed that the relay assignment solution with the maximal social value assigns $R (t_{i})$ to $t_{i}$ (see Algorithm 3). Thus, in (14), the first term must be not smaller than the second one, and we get $U (t_{i}) - U' (t_{i}) \geq 0$ . So, the lemma holds.

Theorem 3.

RA-VCG is truthful and can maximize the total social value.

Proof.

From Lemma 2, we can see that each pair is truthful about not only the desired relay nodes but also other undesired relay nodes and DT. In other words, each pair is truthful about all the relay nodes and thus declares its true information in its BID message. Thus, RA-VCG is truthful. Since all source-destination pairs act truthfully (see Lemma 2) in RA-VCG, then we can get that RA-VCG (RA or TRA algorithm) can maximize the total social value from Lemma 1. Thus, the theorem holds.

Our RA-VCG also has some other nice properties as follows.

Theorem 4.

If source-destination pair $t_{i}$ uses DT in RA-VCG, that is, $R (t_{i}) = ϕ$ , the payment of $t_{i}$ is $0$ .

Proof.

Note that if source-destination pair $t_{i}$ is assigned the relay node $R (t_{i}) = ϕ$ , then the payment of $t_{i}$ is

\begin{array}{l} pay (t_{i}) & = & M_{𝒮 \ {s_{i}}, 𝒟 \ {d_{i}}}^{ℛ} - M_{𝒮 \ {s_{i}}, 𝒟 \ {d_{i}}}^{ℛ \ {ℛ (t_{i}) = φ}} \\ = & M_{𝒮 \ {s_{i}}, 𝒟 \ {d_{i}}}^{ℛ} - M_{𝒮 \ {s_{i}}, 𝒟 \ {d_{i}}}^{ℛ} = 0. \end{array}

(15)

Thus, the theorem holds.

Theorem 5.

For each source-destination pair $t_{i}$ in RA-VCG, the payment is nonnegative.

Proof.

In the first case $R (t_{i}) = ϕ$ , from Theorem 4, we can get $pay (t_{i}) \geq 0$ .

In the second case $R (t_{i}) \neq ϕ$ , it is easy to see that $M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} \geq M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R (t_{i})}}$ , because the corresponding bipartite graph in the first term contains all the edges of the corresponding bipartite graph in the second term. So

\begin{matrix} pay (t_{i}) = M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} - M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R (t_{i})}} \geq 0 . \end{matrix}

(16)

Thus, the theorem holds.

Theorem 6.

For each source-destination pair $t_{i}$ in $R A - V C G$ , the utility is no smaller than $V (t_{i}, ϕ)$ .

Proof.

The utility of $t_{i}$ in RA-VCG is

\begin{array}{l} U (t_{i}) = V (t_{i}, R (t_{i})) - pay (t_{i}) \\ = V (t_{i}, R (t_{i})) - M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} + M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ ∖ {R (t_{i})}} \\ = M_{𝒮, 𝒟}^{ℛ} - M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} \\ \geq M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} + V (t_{i}, ϕ) - M_{𝒮 ∖ {s_{i}}, 𝒟 ∖ {d_{i}}}^{ℛ} \\ = V (t_{i}, ϕ) . \end{array}

(17)

Thus, the theorem holds.

From Theorems 4 and 5, we can see that RA-VCG has no positive transfer. It means that the assignment node does not need to pay anything to the source-destination pairs. Moreover, RA-VCG is individually rational. It means that the pairs are willing to participate in RA-VCG, that is, no pair is really being forced to participate, because the utility achieved by each pair in participating is not smaller than that achieved by using DT (see Theorem 6).

6. Simulation Results

In this section, we give some simulation results to evaluate the performance of RA-VCG in wireless networks with selfish source-destination pairs. Firstly, we present the simulation settings. Secondly, we will show that RA-VCG is indeed truthful (i.e., it can indeed prevent source-destination pairs from cheating each other). Thirdly, we will observe the total social value achieved by RA-VCG. Moreover, we consider both the AF and DF modes for CC.

6.1. Simulation Settings

We consider a wireless network generated by randomly placing all the nodes in the square area $800 * 800$ m². Under this network, we consider both the cases that the value-of-capacity parameter is the same or different for all pairs. In case 1, all the pairs have the same value-of-capacity parameter and we set this parameter as $v = 1$ for all pairs. While in case 2, each pair has different value-of-capacity parameter which is random in [1, 4].

We assume the bandwidth $W = 22$ MHZ for each channel and the maximum transmission power $P = 1$ W at each node. Similar to [5, 6], we also assume that $h_{u v}^{2} = d_{u v}^{- 4}$ , where $d_{u v}$ is the Euclidean distance between nodes u and v, and $4$ is the pass loss index. We assume the channel is AWSN channel and the variance of noise is $1 0^{- 10}$ W for all nodes. To verify the performance of RA-VCG, we assume each source-destination pair can declare its BID message truthfully and untruthfully. For untruthful (cheating) behavior, we assume the declared capacity of each pair according to each relay node (or DT) is random in $(0,2 C)$ , where C is the capacity achieved by this pair. The data points represented in the following graphs are averaged over $100$ simulation runs.

6.2. Truthfulness of RA-VCG

We first observe the effect of the number of source-destination pairs on the average utility of each pair for RA-VCG. As shown in Figures 5 and 6, we have 15 available relay nodes in the network, and the number of source-destination pairs changed from 9 to 19. Then, We observe the effect of the number of available relay nodes on the average utility of each pair for RA-VCG. As shown in Figures 7 and 8, we have 15 source-destination pairs in the network, and the number of available relay nodes changes from 5 to 33.

Figure 5

Average utility versus source-destination pair number in case 1.

Figure 6

Average utility versus source-destination pair number in case 2.

Figure 7

Average utility versus available relay node number in case 1.

Figure 8

Average utility versus available relay node number in case 2.

Nevertheless AF and DF, the average utility of each pair by declaring untruthful BID message is less than the average utility obtained when each source-destination pair declares truthful BID message (i.e., see Figures 5–8). These simulation results show that RA-VCG maximizes a source-destination pair's payoff only when this pair reveals its true individual information. Hence, RA-VCG is truthful.

6.3. Impact of Untruthfulness on Total Social Value

Next, we focus on the impact of untruthful behaviors of source-destination pairs on the total social value. As shown in Figures 9 and 10, when the number of source-destination pairs increases, total social value increases for both cases 1 and 2. Moreover, the truthful behavior in AF mode and DF mode can increase 26.5% and 19.6% total social value than untruthful behaviors both in case 1 and case 2. Figures 11 and 12 show that the total social value increases when the number of available relay nodes increases for both AF and DF in case 1 (see Figure 11) and 2 (see Figure 12). This is because with more relay nodes, there are more chances for each pair to employ relay nodes to use CC. However, since the number of source-destination pairs do not change, the total social value of DT is always the same when the number of relay nodes changes both in case 1 (which is 427.7 in Figure 11) and case 2 (which is 1043.7 in Figure 12). Moreover, we can see that AF mode and DF mode with truthful behavior can increase about 27.0% and 19.7% total social value comparing with untruthful behavior both in case 1 and case 2. Thus, from all these simulation results (Figures 9–12), we can see that the total social value achieved when each node takes untruthful behaviors is average of about 23.3% less than that achieved when nodes behave truthfully.

Figure 9

Total social value versus source-destination pair number in case 1.

Figure 10

Total social value versus source-destination pair number in case 2.

Figure 11

Total social value versus available relay node number in case 2.

Figure 12

Payment ratio versus available relay node number in case 2.

7. Conclusion

CC is a novel technology to achieve spatial diversity. Thus, this paper studies the truthful relay assignment problem in wireless network where each source-destination pair may cheat the others to achieve more individual revenue. Therefore, in order to prevent cheating, we propose RA-VCG, a relay assignment protocol for CC to maximize the total social value while guaranteeing truthfulness by charging each pair an extra payment in wireless networks with selfish source-destination pairs. Moreover, we prove the validity of this protocol and also show several surprising properties associated with this protocol. The simulation results show that the total social value achieved when each node takes untruthful behaviors is about 23.3% less than that achieved when nodes behave truthfully.

Footnotes

Acknowledgments

The work of this paper is supported by the National Grand Fundamental Research 973 Program of China under Grant no. 2011CB302-905, the National Science Foundation of China under Grant nos. 61170058, 61272133, and 51274202, National Science and Technology Major Project under Grant no. 2011ZX03005-004-04, the Natural Science Foundation of Jiangsu Province in China (Grant nos. BK2009150 and BK2012632), and Research Fund for the Doctoral Program of Higher Education of China no. 20103402110041.

References

Laneman

J. N.

Tse

D. N. C.

Wornell

G. W.

Cooperative diversity in wireless networks: efficient protocols and outage behavior

IEEE Transactions on Information Theory 2004 50 12 3062 3080

10.1109/TIT.2004.838089

2103484

T. C.-Y.

Joint optimization of relay strategies and resource allocations in cooperative cellular networks

IEEE Journal on Selected Areas in Communications 2007 25 2 328 339

2-s2.0-33847717542

10.1109/JSAC.2007.070209

Zhao

Adve

Lim

T. J.

Improving amplify-and-forward relay networks: optimal power allocation versus selection

Proceedings of the IEEE International Symposium on Information Theory (ISIT '06)

July 2006

Seattle, Wash, USA

1234 1238

2-s2.0-39049096748

10.1109/ISIT.2006.262002

Cai

Shen

Mark

J. W.

Alfa

A. S.

Semi-distributed user relaying algorithm for amplify-and-forward wireless relay networks

IEEE Transactions on Wireless Communications 2008 7 4 1348 1357

2-s2.0-54949129479

10.1109/TWC.2008.060909

Shi

Sharma

Hou

Y. T.

Kompella

Optimal relay assignment for cooperative communications

Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008 (MobiHoc '08)

May 2008

3 12

2-s2.0-57349143707

10.1109/TWC.2008.4543042

Sharma

Shi

Hou

Y. T.

Kompella

An optimal algorithm for relay node assignment in cooperative Ad Hoc networks

IEEE/ACM Transactions on Networking 2011 19 3 879 892

2-s2.0-79958856206

10.1109/TNET.2010.2091148

Kadloor

Adve

Relay selection and power allocation in cooperative cellular networks

IEEE Transactions on Wireless Communications 2010 9 5 1676 1685

2-s2.0-77952286291

10.1109/TWC.2010.05.090307

Zhang

Ghrayeb

Hasna

Relay assignment schemes for multiple source-destination cooperative networks

Proceedings of the 17th International Conference on Telecommunications (ICT '10)

April 2010

147 152

2-s2.0-77954545979

10.1109/ICTEL.2010.5478645

Huang

Wang

Liu

Joint relay assignment and power allocation for cooperative communications

Wireless Networks 2010 16 8 2209 2219

2-s2.0-78049530930

10.1007/s11276-010-0254-2

10.

Liu

Wang

Relay assignment and cooperation maintenance in wireless networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '10)

April 2010

2-s2.0-77955015595

10.1109/WCNC.2010.5506253

11.

Yang

Fang

Xue

HERA: an optimal relay assignment scheme for cooperative networks

IEEE Journal on Selected Areas in Communications 2012 30 2 245 253

10.1109/JSAC.2012.120202

12.

Yang

Fang

Xue

Truthful auction for cooperative communications

Proceedings of the 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing (ACM MOBIHOC '11)

2011

89 98

10.1145/2107502.2107514

13.

Shastry

Adve

R. S.

Stimulating cooperative diversity in wireless ad hoc networks through pricing

2006 IEEE International Conference on Communications (ICC '06)

July 2006

3747 3752

2-s2.0-34548353537

10.1109/ICC.2006.255655

14.

Wang

Han

Ray Liu

K. J.

Distributed relay selection and power control for multiuser cooperative communication networks using buyer/ seller game

Proceedings of the 26th IEEE International Conference on Computer Communications (IEEE INFOCOM '07)

May 2007

544 552

2-s2.0-34548364231

10.1109/INFCOM.2007.70

15.

Huang

Han

Chiang

Poor

H. V.

Auction-based resource allocation for cooperative communications

IEEE Journal on Selected Areas in Communications 2008 26 7 1226 1237

2-s2.0-50649122537

10.1109/JSAC.2008.080919

16.

Anderegg

Eidenbenz

Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile Ad hoc Networks with selfish agents

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03)

September 2003

245 259

2-s2.0-1542299118

17.

Jia

Zhang

Liu

Revenue generation for truthful spectrum auction in dynamic spectrum access

Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '09)

May 2009

3 12

2-s2.0-70450159053

10.1145/1530748.1530751

18.

Shu

Varaiya

Smart pay access control via incentive alignment

IEEE Journal on Selected Areas in Communications 2006 24 5 1051 1060

2-s2.0-33646406556

10.1109/JSAC.2006.872887

19.

Zhong

Chen

Yang

Y. R.

Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (Infocom '03)

April 2003

1987 1997

2-s2.0-0042933944

20.

Buttyan

Hubaux

Enforce service availability in mobile as-hoc wans

Proceedings of the 1st ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc '00)

2000

87 96

21.

Munkres

Algorithm for the assignment and transportation problem

Journal of the Society for Industrial and Applied Mathematics 1957 5 32 38

10.1137/0105003

Truthful Relay Assignment for Cooperative Communication in Wireless Networks with Selfish Source-Destination Pairs

Abstract

1. Introduction

2. Related Work

3. System Model

3.1. Cooperative Communication Model

3.2. Truthful Relay Assignment Problem

4. Truthful Relay Assignment Protocol

4.1. Basic Idea

Algorithm 1: Relay discovery phase.

4.2. Relay Discovery

4.3. Relay Assignment

Algorithm 2: RA( 𝒮 , ℛ , 𝒟 , flag).

Algorithm 3: TRA.

4.4. Data Transmission

4.5. Complexity Analysis

5. Analysis

Lemma 1.

Proof.

Lemma 2.

Proof.

Theorem 3.

Proof.

Theorem 4.

Proof.

Theorem 5.

Proof.

Theorem 6.

Proof.

6. Simulation Results

6.1. Simulation Settings

6.2. Truthfulness of RA-VCG

6.3. Impact of Untruthfulness on Total Social Value

7. Conclusion

Footnotes

Acknowledgments

References

Algorithm 2: RA( $𝒮, ℛ, 𝒟$ , flag).