Throughput-Optimal Scheduling for Cooperative Communications in Wireless Ad Hoc Networks

Abstract

Cooperative communications that take advantage of the broadcasting nature of wireless environments can help to increase system throughput in wireless ad hoc networks. However, the promised throughput might be lost in presence of the error transmission and the interference caused by relay transmission in cooperative communication. In this paper, we introduced the relay selection schemes that can control the interference at the relay to prevent the relay that may harm other pairs. Then, we proposed the throughput-optimal scheduling that takes into account error probability in decision and maximizes throughput, that is, the amount of packets transmitted without error in network. In addition, we derive a simple and lightweight framework to implement the proposed policy in distributed manner. The simulation results show that the proposed scheduling policy outperforms the noncooperative policy and multihop relay policy.

1. Introduction

Cooperative communications that can take advantage of the broadcasting nature of wireless environments have shown excellent performance in both theoretical aspects and implementations; for example, per-node throughput of the cooperative network is a constant factor, while per-node throughput of the conventional wireless network decreases when node density increases [1]. The basic concept of the cooperative communication comes from the design of multiple-input multiple-output (MIMO) system. In MIMO system, by using the multiple antennas at the transmitter and receiver, the system throughput and reliability were improved significantly [2]. However, in wireless networks, for example, sensor networks and ad hoc networks, due to the space limitation and the implementation cost, it is not reasonable to equip each wireless device with multiple antennas. To overcome this restriction, cooperative communication is proposed as a solution to implement the MIMO technique in the form of single antenna node in wireless networks. Many cooperative communication schemes have been proposed in the general framework of wireless ad hoc network [3, 4] in order to improve the performance of the system.

Scheduling policies are employed to determine a set of active users at a given time regarding the interference constraints between links. Throughput-optimal scheduling policy that provides the highest data rate transmission is desirable in wireless networks. It has been shown that cooperative communication at the network layer can help to increase the throughput of the network [5]. However, in wireless ad hoc networks, the throughput gained by cooperative communication might be lost in the presence of the interference caused by relay transmission. Furthermore, since the wireless links are unreliable and the transmission states are only known by the acknowledgments from receivers, the scheduling decision must consider random packet loss and packet retransmission. Hence, this necessitates a new design for throughput-optimal scheduling for the cooperative communication in ad hoc networks.

In this paper, we focus on designing a throughput-optimal scheduling for the cooperative communication at the network layer. We consider the cooperation between the number of source-destination pairs and relay nodes in wireless ad hoc networks. Each pair can communicate either through direct transmission or cooperative transmission which uses other relay to forward its data to destination. These relays are selected under the constraint of the interference of relay below a certain threshold to prevent the relays that may harm other pairs. Otherwise, in our scenarios, each source node has a single queue, where packets are backlogged before transmitting to destination. Due to the network stability constraint, the scheduling policy also needs to minimize the sum square of the queue lengths so as to equalize and keep the queue bounded.

The primary contributions of this study are as follows.

• (i)

  We first introduce the relay selection scheme which considers interference from relay node by keeping the interference level below a certain threshold. The effect of the interference is controlled by an interference threshold ɛ. The simulation results show that the effectively selected relay can help to mitigate interference at the relay and improve the network throughput.

• (ii)

  We propose a scheduling policy to determine which pair is allowed to transmit and which transmission mode is used to transmit data at each time. This scheduling is derived from the suboptimal control principles. At each time slot, the scheduling policy takes an action that maximizes a weighted cost function. This cost function is defined regarding parallel objective of the control strategies: maximization of the throughput, and stabilization of network queues.

• (iii)

  We analyze the sufficient condition for throughput-optimal policy and stability in cooperative communication. A theoretical analysis using the Lyapunov function shows that this scheduling policy obtains the throughput to be near optimal while the simulation results show that it outperforms the noncooperative policy and multihop relay policy.

2. Related Work

There are several works concerning the optimal use of the cooperative communication in wireless ad hoc networks. These works mostly focus on information theory study [6, 7] or design and analysis for cooperation at physical layers with amplify-and-forward, decode-and-forward, selection relaying, and incremental relaying [8]. In [9, 10], the authors focus on the design of optimal algorithms and solve the optimal power allocation between the source and relay nodes to maximize capacity [9] and minimize outage probability [10]. In particular, the research in [11] studied the dynamic resource allocation for delay limited cooperative communication networks and developed dynamic cooperation strategies to achieve a target outage probability. They first consider the optimization problem with objective minimizing the number of packet errors. Then by using the Lyapunov technique, they present a framework to achieve the optimal solution of this problem at each time slot. This approach is similar to that of our study except that our work is performed at network layer. However, the objects of this work are different from the goal of our research, for example, throughput-optimal.

Research on throughput-optimal scheduling for single-hop and multihop wireless networks is addressed in [12, 13]. These results have shown that a scheduling policy based on the current queue length and link rate can achieve the maximum throughput region and stability region. In [12], the backpressure scheduling policy, which is based on the difference of queue length between source and destination nodes of links, can achieve the maximum throughput region and guarantee the stability of the network. The works in [13] extend the scheduling policy to a general framework for scheduling and flow control in multihop wireless networks. Recently, these results have been extended to cooperative networks. In [14], the authors provide an analysis of the throughput region and delay of cooperation in a line-like topology. They focus on characterizing the stability region and the delay of network-level cooperation. However, they assume a line-like topology and TDMA scheduling, whereas our research finds a throughput-optimal scheduling oncooperative ad hoc networks.

3. Problem Formulation

3.1. System Model

We consider a wireless ad hoc network with N source destination pairs and K other nodes which have no own data to transmit. These nodes are installed to increase throughput and reliability of the network. They receive and forward packet to the destination. We assumed a slotted time frame structure that is widely used in implementation of practical system, for example, WiMax, and theoretic analyses [9, 11]. The time is divided into equal units $t=\{\mathrm{0,1},\mathrm{2},\dots \}$ called time slot.

The exogenous traffic stream arrives to each source node at each time slot t according to independent stochastic process. Then, it is stored in separate queues to await transmission. Let $a(t)=\{a_k(t){\}}_{k\in N}$ represent the exogenous traffic arriving at the time slot t with the mean ${\lambda }_c=E\{a_k(t)\}$ and $a_k(t)\le A_{\max }$ . The arrival processes are i.i.d over slots, and the second moment $E\{a_k^{\mathrm{2}}(t)\}$ of the arrival process is finite. Let $Q_k(t)$ be the number of packets waiting at queue of source node k at time t.

The wireless channel is considered to be flat fading and all noise components are modeled as additive white Gaussian noise (AWGN) with zero means and variance $N_{\mathrm{0}}$ . We focus on the slow fading channel, where the channel states of all links remain constant during one time slot and might be changed in the next time slot. Moreover, the channel gain between node i and node j is denoted by $h_{i,j}$ . Assume that the transmission power at each node is fixed with P. Let ${\gamma }_{i,j}$ be the instantaneous signal-to-noise ratio (SNR) when node i transmits packet to node j. Thus, the instantaneous SNR ${\gamma }_{i,j}$ is ${\gamma }_{i,j}=(P/N_{\mathrm{0}}){|h_{i,j}|}^{\mathrm{2}}$ , which is modeled as an exponential distribution with means ${\delta }_{i,r}^{\mathrm{2}}=(P/N_{\mathrm{0}})E[{|h_{i,j}|}^{\mathrm{2}}]$ [15].

In our model, each pair in the network has freedom in selecting the transmission mode at each time slot. They can communicate either through direct transmission or cooperative transmission. In the first case, we say that the pair is in the direct mode, and in the latter case we say that the pair is in the cooperative mode. If the pair is in direct mode, the packet is transmitted directly to the destination by the source node. If the pair is in cooperative mode, the packet is forwarded to the destination by employing another relay node.

3.2. Relay Selection Scheme with Interference Control

In cooperative mode, the transmission of the selected relay may create unacceptable interference for other pairs. To prevent this problem, we proposed that each selected relay must maintain interference constraint, where the interference at each relay must be below a predetermined value ${\gamma }_{th}$ . However, since the channel gain at each relay node is changed per time slot in time-varying channel, it is not reasonable to guarantee this constraint in every time slot. Thus, we require the probability of satisfying the interference constraint for selected relay of each pair i above a certain value $p_{th}$ :

$$\begin{array}{cc}& \text{Pr}\left(\frac{{\gamma }_{i,r}}{{\gamma }_{\mathrm{int},r}+\mathrm{1}}<{\gamma }_{th}\right)>p_{th},\end{array}$$

(1)

where ${\gamma }_{i,r}$ is the received SNR of the link between source node i and its relay r and ${\gamma }_{\mathrm{int},r}$ is the interference at the relay node which is caused by multiple transmission of other pairs. Note that, if other pairs keep silent, ${\gamma }_{\mathrm{int},r}=\mathrm{0}$ . In this case, the interference constraint is given by

$$\begin{array}{cc}& \text{Pr}\left({\gamma }_{i,r}<{\gamma }_{th}\right)=\mathrm{1}-\exp \left(-\frac{{\gamma }_{th}}{{\delta }_{i,r}^{\mathrm{2}}}\right)>p_{th}.\end{array}$$

(2)

Thus, if $\mathrm{1}-\exp (-{\gamma }_{th}/{\delta }_{i,r}^{\mathrm{2}})<p_{th}$ , the constraint is not satisfied and the relay is prohibited. Otherwise, the relay will be opportunistically selected. In this case, it is hard to calculate the value of ${\gamma }_{\mathrm{int},r}$ directly. To overcome this problem, instead of studying the constraint in (1), we study the approximation to the constraint given by

$$\begin{array}{cc}& \left(\mathrm{1}-\varepsilon \right)\text{Pr}\left({\gamma }_{i,r}<{\gamma }_{th}\right)>p_{th}.\end{array}$$

(3)

Here, parameter ɛ indicates the interference control level: if $\varepsilon \to \mathrm{1}$ , the threshold is tight that only few relays are selected to forward the data; otherwise, if $\varepsilon \to \mathrm{0}$ , the threshold is rather loose; most of the relays are selected to forward without restriction. Finally, we obtained the straightforward expression of a set of relays satisfying the interference constraint for each pair i:

$$\begin{array}{cc}& {\mathbf{R}\mathbf{e}}_i=\left\{r\mid \left(\mathrm{1}-\varepsilon \right)\text{Pr}\left({\gamma }_{i,r}<{\gamma }_{th}\right)>p_{th}\right\},\end{array}$$

(4)

or

$$\begin{array}{cc}& {\mathbf{R}\mathbf{e}}_i=\left\{r\mid {\delta }_{i,r}^{\mathrm{2}}\ge \frac{\mathrm{1}}{{\gamma }_{th}}\ln \left(\frac{\mathrm{1}-\varepsilon }{\mathrm{1}-\varepsilon -p_{th}}\right)\right\}.\end{array}$$

(5)

The average channel gain between relay and source node is determined by $E[{|h_{i,r}|}^{\mathrm{2}}]={(d_{i,r}/d_{\mathrm{0}})}^{-\mathrm{3}}$ [16], in which $d_{i,r}$ is the distance between source node i and relay r and $d_{\mathrm{0}}$ is the unit distance. Therefore, the relay set for each pair i is circular with radius $\text{R}{\text{e}}_i$ as follows: ${\mathbf{R}\mathbf{e}}_i=\{r\mid d_{i,r}\le \text{R}{\text{e}}_i\}$ , where $\text{R}{\text{e}}_i=d_{\mathrm{0}}{(N_{\mathrm{0}}{\gamma }_{th}/P\ln ((\mathrm{1}-\varepsilon )/(\mathrm{1}-\varepsilon -p_{th})))}^{\mathrm{1}/\mathrm{3}}$ .

After the set of relays is determined, the source node can opportunistically select from this set one relay to forward the message without considering the effect on other pairs.

3.3. Network Objective and Control Variables

Whenever a pair is communicated, it will receive a certain throughput, which is defined by the number of the successful transmitted packets in one time slot. Let $p_k^d(t),p_k^c(t)$ be the success transmission probabilities over direct link and cooperative link at time t. We use the superscripts $d,c$ to indicate the direct transmission and cooperative transmission in this paper. The success probabilities depend on the channel conditions, modulation, coding type, and power level, as shown in [17]. Using the pilot signal, these probabilities can be estimated at the beginning of each time slot. We assume that these probabilities evolve over slots according to a finite-state Markov chain, and thus the steady state is measurable and is denoted by $p^d,p^c$ . Let $w_k^d(t),w_k^c(t)$ be the number of transmitted packets of pair k in direct mode and cooperative mode at time t. These values can be calculated based on the transmission rate and packet length. Notice that, since different transmission modes have different success probability and number of transmitted packets, the throughput attained by using a different mode will be different. Let $R_k(t)=[R_k^d(t),R_k^c(t)]$ represent the throughput of pair k:

$$\begin{array}{cc}& R_k^d\left(t\right)=w_k^d\left(t\right)p_k^d\left(t\right),\hspace{1em}\hspace{1em}{R}_k^c\left(t\right)=w_k^c\left(t\right)p_k^c\left(t\right).\end{array}$$

(6)

At any time slot t, the source node k can use one of the following transmission modes: direct transmission, cooperative transmission, and no transmission. Define $I_k(t)=[I_k^d(t),I_k^c(t)]$ as the control variable indicating the transmission mode of source node k at time slot t. That is, $I_k(t)=[\mathrm{1,0}]$ if node k activated the direct mode, $I_k(t)=[\mathrm{0,1}]$ if node k activated the cooperative mode to transmit data, and $I_k(t)=[\mathrm{0,0}]$ in other cases. Notice that $I_k(t)$ represents a virtual transmission packet because it describes the possibility of choosing transmission mode independent of the current queue length. In the case when $I_k(t)=[\mathrm{1,0}]$ or $[\mathrm{0,1}]$ but there is no packet available at the pair k's queue, then no packet is actually transmitted. The vector $\overrightarrow{I}(t)=[I_{\mathrm{1}}(t),I_{\mathrm{2}}(t),\dots ,I_N(t)]$ denotes the control vector at time slot t. Let $\mathrm{\Gamma }=\{{\overrightarrow{I}}^{\mathrm{1}}(t),{\overrightarrow{I}}^{\mathrm{2}}(t),\dots ,{\overrightarrow{I}}^m(t)\}$ denote the set of all valid control vectors of the network. Clearly, $m\le {\mathrm{2}}^{\mathrm{2}N}$ . In each slot $t>\mathrm{1}$ , the scheduling policy $\mathrm{\Delta }$ decides the control vector ${\overrightarrow{I}}^{\mathrm{\Delta }}(t)$ such that ${\overrightarrow{I}}^{\mathrm{\Delta }}(t)\in \mathrm{\Gamma }$ . Now, we present some definitions.

Definition 1 (network stability).

Queue Q is stable if the time average of the queue length ${\lim }_{T->\infty }(\mathrm{1}/T){\sum }_{t=\mathrm{0}}^{T-\mathrm{1}}E\{Q(t)\}<\infty$ . The network is stable if all queues are stable.

Definition 2 (stability region).

The stability region of a scheduling policy is the set of arrival rates $\{{\lambda }_m{\}}_{m\in \{\mathrm{1},\dots ,N\}}$ that stabilize the system under the policy. The stability region of the system Ω is the union of stability region of all scheduling policies.

Definition 3 (throughput).

For the arrival rate λ, the throughput under the scheduling policy $\mathrm{\Delta }$ at time slot t, $G^{\mathrm{\Delta }}(\lambda )$ , is the total successful transmitted packet that is received by all users in the network. Mathematically,

$$\begin{array}{cc}& G^{\mathrm{\Delta }}\left(\lambda \right)=\underset{t\to \infty }{\lim }\frac{\mathrm{1}}{T}{\displaystyle \sum }_{t=\mathrm{1}}^T‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^N‍R_k\left(t\right)I_k^{\mathrm{\Delta }}\left(t\right).\end{array}$$

(7)

Definition 4 (throughput-optimal).

The scheduling policy is called throughput-optimal for the arrival rate vector $\overrightarrow{\lambda }\in \Omega$ if it can obtain the maximum throughput among all scheduling policies that stabilizes the network. We represent the throughput obtained by such policies for arrival rate vector $\overrightarrow{\lambda }$ by $G_{\max }(\overrightarrow{\lambda })$ .

Definition 5 ( $ϵ$ -throughput-optimal).

The scheduling policy is called ϵ-throughput optimal for $ϵ>\mathrm{0}$ if under this policy the network is stable and $G^{\mathrm{\Delta }}(\overrightarrow{\lambda })>G_{\max }(\overrightarrow{\lambda })-ϵ$ . The ϵ-throughput-optimal policy attains a throughput which is at most ϵ less than the throughput of any scheduling.

In this paper, we aim to design the optimal policy that selects the control vector ${\overrightarrow{I}}^i(t)\in \mathrm{\Gamma }$ in each time slot to maximize the average throughput, while the stability of the network is guaranteed

$$\begin{array}{cc}& \underset{{\overrightarrow{I}}^i\left(t\right)\in \mathrm{\Gamma }}{\max }\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^N‍R_k\left(t\right)I_k^i\left(t\right)\end{array}$$

(8)

subject to

$$\begin{array}{cc}& \underset{t\to \infty }{\lim }\frac{\mathrm{1}}{t}{\displaystyle \sum }_{k=\mathrm{1}}^t‍\hspace{0.17em}{\displaystyle \sum }_{i=\mathrm{1}}^N‍Q_i\left(k\right)<\infty ,\end{array}$$

(9)

where $E(·)$ denote an expectation and $I_k^i$ denote the kth component of control vector ${\overrightarrow{I}}_i$ . The constraint in (9) ensures the stability of the network.

4. Throughput-Optimal for Cooperative Communication (TOCC)

4.1. TOCC Policy

We consider a discrete-time linear time-invariant system with dynamics queues, where $\mathrm{\Phi }(t)=\{Q_k(t){\}}_{c\in N}\ge \mathrm{0}$ are the states and ${\overrightarrow{I}}^k(t)\in \mathrm{\Gamma }$ is the control input. Note that only ${\overrightarrow{I}}^k(t)$ is variable here since the scheduling decision is considered in this design. We define a cost function that is comprised of objectives in policy design: maximizing the throughput and stabilizing the queuing. The cost function is defined as follows:

$$\begin{array}{cc}& J=\underset{T\to \infty }{\lim }\frac{\mathrm{1}}{T}{\displaystyle \sum }_{t=\mathrm{0}}^T‍E\left\{{\displaystyle \sum }_{k=\mathrm{1}}^N‍Q_k^{\mathrm{2}}\left(t\right)-V{\displaystyle \sum }_{k=\mathrm{1}}^N‍R_k\left(t\right)I_k^i\left(t\right)\right\}.\end{array}$$

(10)

The first term in function J is the average expectation sum quadratic of the queue length. This quadratic form gives higher cost values to the larger queue length; thus, it tends to equalize the queue length of every pair and reduces queue length of larger queues. The second term of J is the average expectation of total throughput. The minimization of J assures that the queue at each pair is minimized and total throughput is maximized. V is a control parameter that provides tradeoff between the stability of queue and attained throughput.

In general, linear stochastic optimal control problem can be solved effectively with optimal policy in only few special cases [18, 19]. However, there exist different methods to find suboptimal control policy [18]. Regarding computational complexity and its compliance to our objective function, we consider control-Lyapunov feedback method. Suboptimal control policy following the control-Lyapunov feedback method is given as

the TOCC policy:

$$\begin{array}{cc}& \overrightarrow{I}\left(t\right)=\arg \underset{\overrightarrow{I}\in \mathrm{\Gamma }}{\max }\left({\displaystyle \sum }_{k=\mathrm{1}}^N‍\left(Q_k\left(t\right)I_k\left(t\right)+V{R}_k\left(t\right)I_k\left(t\right)\right)\right).\end{array}$$

(11)

The TOCC has a similar form to that of the SNO algorithms [13]; however, the throughput is calculated differently. In TOCC, the throughput takes into account the success probability on each transmission mode and the number of transmitted packets in each mode. The solution of the TOCC uses the value of the current channel states, the queue length $Q(t)$ , the success probability, and the achievable rate (or number of transmitted packets) of each mode and does not need a memory of historical states or a required knowledge of the arrival rate.

4.2. Operation of TOCC Policy

In this section, we describe the operation of the TOCC policy: how this policy can stabilize the network while maximizing the throughput, by comparing it with the well-known backpressure policy [12]. We first denote

$$\begin{array}{cc}& W_{\text{TOCC}}\left({\overrightarrow{I}}^i\right)={\displaystyle \sum }_{k=\mathrm{1}}^N‍Q_k\left(t\right)I_k^i\left(t\right)+V{R}_k\left(t\right)I_k^i\left(t\right),\end{array}$$

(12)

$$\begin{array}{cc}& W_{\text{BP}}\left({\overrightarrow{I}}^i\right)={\displaystyle \sum }_{k=\mathrm{1}}^N‍Q_k\left(t\right)·I_k^i\left(t\right),\end{array}$$

(13)

where $I_k^i(t)$ denote the kth element of vector ${\overrightarrow{I}}^i(t)$ . In each time slot t, the TOCC and backpressure policies select the control vector that maximizes $W_{\text{TOCC}}({\overrightarrow{I}}^i)$ and $W_{\text{BP}}({\overrightarrow{I}}^i)$ . It has been shown in [12] that the backpressure policy stabilizes the network for every arrival rate vector within the stability region. This is because, under this policy, the queue length process ${\sum }_{k=\mathrm{1}}^N{Q}_k^{\mathrm{2}}$ has a negative drift when the total queue length ${\sum }_{k=\mathrm{1}}^N{Q}_k$ is significantly large.

We consider the two cases: large queue length and small queue length. In the first case, when the queue lengths are significantly large, we have ${\sum }_{k=\mathrm{1}}^N{Q}_k(t)\gg V{\sum }_{k=\mathrm{1}}^N|R_k(t)I_k|$ ; then, from (12) and (13) for every $\overrightarrow{I}(t)$ , we have $W_{\text{TOCC}}({\overrightarrow{I}}^i)\approx W_{\text{BP}}({\overrightarrow{I}}^i)$ . Thus, TOCC policy and Backpressure policy select similar control vector. It is clear that the queue length process under TOCC policy also has a negative drift when the total queue length is sufficiently large. Therefore, TOCC policy stabilizes network for every arrival rate vector strictly inside the stability region.

In case the queue lengths are small, $W_{\text{TOCC}}({\overrightarrow{I}}^i)$ and $W_{\text{BP}}({\overrightarrow{I}}^i)$ differ, and the control vectors which are selected under TOCC policy and backpressure policy are not similar. In this case, we have $Q_k(t)\ll |R_k(t)I_k|$ . The TOCC policy prefers to select pair k and control vectors which have high throughput to maximize $W_{\text{TOCC}}({\overrightarrow{I}}^i)$ . Therefore, TOCC policy can guarantee the maximum throughput for every transmission pair.

The following theorem summarizes our discussion above. It is shown that the TOCC is ϵ-throughput-optimal. The TOCC attains a throughput with a gap ϵ to the optimal solution. By controlling parameter V, we can achieve total throughput arbitrary close to the optimal point.

Theorem 6.

Given any arrival rate vector, λ, strictly inside the stability region, the TOCC policy stochastically stabilized all the queue. And then, for every $ϵ>\mathrm{0}$ , there exits $V^{*}$ such that, for every $V>V^{*}$ , TOCC policy is ϵ-throughput-optimal policy.

Proof.

The proof of Theorem 6 is given in Appendix A.

4.3. Distributed Implementation Issues

Implementation of the TOCC policy requires two steps: gathering network states information which includes the queue length, success probability, and transmission rate, and computing the optimal control vector. In the first step, it requires centralized implementation and thus leads to increasing delay and bandwidth. In the second step, the control policy TOCC needs to find optimal vector $\overrightarrow{I}\in \mathrm{\Gamma }$ by solving (11). In the worst case, since the cardinality of $\mathrm{\Gamma }$ can be ${\mathrm{2}}^{\mathrm{2}N}$ , the complexity to compute the optimal control vector ${\overrightarrow{I}}^{*}$ is also $O({\mathrm{2}}^{\mathrm{2}N})$ . Thus, finding the optimal control policy is challenging since it requires the centralized implementation and the complexity of the problem is high.

To address the above challenges, we apply the Randomize Pick and Compare (RPC) framework [20] in order to implement TOCC policy in distributed manner with polynomial computation. The key feature of the RPC framework is that it does not seek to find an optimal control vector in every slot, and hence, it can significantly reduce the computation time. In every time slot, it determines the set $I(t)$ in two steps.

Step 1 (pick).

At each time slot, it generates a new control vector $\overrightarrow{\bar{I}}(t)$ such that

• $\hspace{0.17em}\text{Pr}(W_{\text{TOCC}}({\overrightarrow{I}}^{*}(t))=W_{\text{TOCC}}(\overrightarrow{\bar{I}}(t)))>\sigma$ ,

for constant $\sigma >\mathrm{0}$ and ${\overrightarrow{I}}^{*}(t)$ is the optimal control vector selected by TOCC policy.

Step 2 (compare).

Determine the control vector at time slot t by comparing the previous control vector $I(t-\mathrm{1})$ and the new one $\bar{I}(t)$ :

$$\begin{array}{cc}& \overrightarrow{I}\left(t\right)=\arg \underset{I\left(t\right)}{\max }\left(W_{\text{TOCC}}\left(\overrightarrow{\bar{I}}\left(t\right)\right),W_{\text{TOCC}}\left(\overrightarrow{I}\left(t-\mathrm{1}\right)\right)\right).\end{array}$$

(14)

Based on [20, 21], the compare operation can be performed in a distributed fashion with $O(N^{\mathrm{3}})$ computations. The following theorem shows that RPC framework has the same performance with the TOCC policy.

Theorem 7.

Given any arrival rate vector, λ, strictly inside the stability region, the RPC framework stabilized all the queue. And then, for every $ϵ>\mathrm{0}$ and $\overrightarrow{\lambda }\in \Omega$ , there exits $V^{\prime }$ such that, for every $V>V^{\prime }$ ,

$$\begin{array}{cc}& G^{{\Pi }_{*}}\left(\overrightarrow{\lambda }\right)>G_{\max }\left(\overrightarrow{\lambda }\right)-ϵ,\end{array}$$

(15)

where $G^{{\Pi }_{*}}$ is the throughput of the system under RPC framework.

Proof.

The proof of Theorem 7 is given in Appendix B.

5. Performance Evaluation

In this section, we present our simulation to illustrate the theoretical results and to compare the performance of TOCC policy and its implementation with the aforementioned well-known policy.

In our simulation, we generate a random topology with 100 nodes which are uniformly distributed in a rectangular area. We select 20 nodes as the source nodes, and each source node picks one of its neighbor nodes as a destination. A relay node is also picked from the relay set of each pair. In order to determine the relay set of each pair, we let ${\gamma }_{th}=\mathrm{1}$ and $p_{th}=\mathrm{0.8}$ . We set up a dynamic wireless environment where the link qualities and the arrival rate are stationary processes. A 2-hop interference model is used to determine the set of all valid control vectors, $\mathrm{\Gamma }$ . The extended packets arrival to each pair k is assumed to follow the exponential distribution with mean ${\lambda }_k$ . These pairs can transmit either directly or cooperatively with a relay node inside their relay set $\text{R}{\text{e}}_i$ . At each time slot, our simulation runs the following steps. At the first step, the success probabilities are generated using a random process with given mean quality. At the second step, we find control vector $\overrightarrow{I}$ according to the TOCC policy. At the last step, queuing evolution is updated.

5.1. Throughput Comparison

In the first experiment, we compare our performance with two other policies called noncooperative policy (NCP) and multihop relay policy (MHR) which always uses relay node to forward its data. We evaluate the performance of these policies in the term of the throughput. The control parameter V is set to 10. The relay set for each pair is calculated with the interference control level $\varepsilon =\mathrm{0.8}$ . The number of source nodes is 20 nodes. Figure 1(a) shows the throughput under the scenario where the direct links between source and destination have very poor quality, $p^d=\mathrm{0.4}$ . We can see that the throughput of these policies is decreased in order: TOCC, RPC, MHR, and NCP. Although the multihop relay policy provides better performance than the noncooperative policy in this case, since it does not use the direct link, its performance is far below that of the TOCC and RPC. Similar results are shown in Figure 1(b) on the contrary case where the direct links between source and destination have good quality, $p^d=\mathrm{0.8}$ . These results have two interesting features. First, when the quality of the direct link is good, the noncooperative policy performs better than multihop relay. When the quality of the direct link is low, the two-hop relay performs better. This reflects the nature of the wireless network: the performance of the direct transmission and multihop relay transmission depends on the link qualities. Second, in all cases, TOCC and RPC provide throughput better than what the noncooperative and multihop relays do. The reason behind this result is that the TOCC and RPC have wider degrees of freedom in choosing transmission mode of each pair at every time slot than others. Notice that, contrary to throughput of NCP and MHR policies, the throughput of the TOCC and RPC policies is almost the same in the two cases and its performance does not depend on the link quality of network.

Figure 1

Throughput and arrival rate under different direct link quality.

Next, we consider the effect of the parameter V to the performance of throughput. Given an input rate ${\lambda }_n=0.6$ and the number of users $k=20$ , simulations were conducted by using control parameters V in the range from 0 to 50, and the results are given in Figure 2. From Figure 2, it is seen that the throughput converges to the optimal throughput level, as the control parameter V is increased. This result has been predicted in Theorems 6 and 7: when $V>V^{*}$ , the throughputs obtained by TOCC and RPC are near optimal.

Figure 2

Impact of control parameter V on throughput.

5.2. Convergence and Network Stability

We verify the stability of the network under TOCC and RPC policies by investigating the queue length over 500 time slots. Figure 3 shows the evolution of the average queue lengths at source nodes. This result shows the queue length property of TOCC and RPC policies, which is specified in Theorems 6 and 7. The queue length fluctuates and coverages at the predefined queue length. Hence, the network is stable under TOCC and RPC policies. Notice that the RPC selects the control vector in an opportunistic way; thus, the convergence of the queue length under TOCC is faster than that of RPC.

Figure 3

Evolution of the queues under the TOCC and RPC policies.

5.3. Impact of the Interference Control

We consider the impact of the interference to the selection of the relay. The number of the relays under variation of the parameter ɛ and the average SNR on the link between source and relay nodes ${\delta }_{i,r}^{\mathrm{2}}$ are shown in Figure 4(a). The number of the relays is increased with the increase of ${\delta }_{i,r}^{\mathrm{2}}$ . Similarly, the parameter ɛ also impacts on the permitted number of the relays. This is because small ɛ means that the interference control is rather loose. Consequently, more relays are permitted to forward message.

Figure 4

The impact of interference control parameter.

The throughput of the TOCC under variance of parameter ɛ is illustrated in Figure 4(b). The throughput decreases drastically when ɛ goes to 0. From the interference control effect, it is clear that the throughput is lowered by nearly one and a half times with $\varepsilon =\mathrm{0}$ (control-free case) in contrast to $\varepsilon =\mathrm{0.7}$ case. Furthermore, the parameter ɛ more than 0.4 is recommended since TOCC can maintain its competitive performance in throughput in comparison with no-relay case.

6. Conclusion

Wireless ad hoc networks with cooperative transmission and direct transmission have been considered in this paper. Aiming at maximizing network throughput, we have investigated the scheduling policy which can guarantee the stability of network and obtain the throughput to be near optimal. In addition, the relay selection has been introduced to deal with interference caused by relay and other pairs. The relay selection scheme considers interference caused by relay transmission, since it required that each relay must maintain an interference constraint. Through simulation, we demonstrate the effectiveness of the proposed TOCC algorithm. The throughput that was obtained by our TOCC policy is very close to the optimum. It is also observed that effectively selecting relay can help to mitigate interference at the relay and improve the network throughput.