Cooperative Routing in Multi-Radio Multi-Hop Wireless Network

Abstract

There are many recent interests on cooperative communication (CC) in wireless networks. Despite the large capacity gain of CC in small wireless networks, CC can result in severe interference in large networks and even degraded throughput. The aim of this chapter is to concurrently exploit multi-radio and multi-channel (MRMC) and CC technique to combat co-channel interference and improve the performance of multi-hop wireless network. Our proposed solution concurrently considers cooperative routing, channel assignment, and relay selection and takes advantage of both MRMC technique and spatial diversity to improve the throughput. We propose two important metrics, contention-aware channel utilization routing metric (CACU) to capture the interference cost from both direct and cooperative transmission, and traffic aware channel condition metric (TACC) to evaluate the channel load condition. Based on these metrics, we propose three algorithms for interference-aware cooperative routing, local channel adjustment, and local path and relay adaptation, respectively, to ensure high-performance communications in dynamic wireless networks. Our algorithms are fully distributed and can effectively mitigate co-channel interference and achieve cooperative diversity gain. To our best knowledge, this is the first distributed solution that supports CC in MRMC networks. Our performance studies demonstrate that our algorithms can significantly increase the aggregate throughput.

1. Introduction

As an emerging technique for future wireless networks, cooperative communication (CC) has been proposed to take advantage of the broadcast nature of wireless communications and spatial diversity to improve the network performance [1, 2]. More specifically, relay nodes have been exploited to forward the replica of packets from the sources, and the destinations can combine multiple copies of the signal to better decode the original message. Taking advantage of spatial and multiuser diversities, CC can efficiently improve the network performance.

Despite the significant performance gain in small networks, recent research results show through both analysis and simulation that the use of cooperative relays (CRs) in large‐scale wireless networks can lead to severe interference, which in turn results in higher packet loss and consequent throughput reduction [3–5]. Although relay nodes may help to increase the throughput of a single source and destination pair, a cooperative transmission (CT) often involves three transmission links (i.e., from the source to the relay, from the source to the destination, and from the relay to the destination). The increase of transmission links in a neighborhood leads to higher interference, thus reducing the network‐wise performance [6]. When the interference is severe, the performance can be even worse than without using cooperative transmissions. It is critical to reduce the interference for CC to work efficiently in a practical wireless network, especially when the network scale is large.

Another recent technique, multi‐radio multi‐channel (MRMC), has been exploited to alleviate the co‐channel interference by supporting concurrent transmissions over orthogonal channels to improve the network capacity [7–9]. With the growth of modern wireless technologies, the cost of radio chips including those supporting 802.11 [10, 11] constantly reduces and more devices will be equipped with multiple radios.

In this chapter, we exploit MRMC to alleviate the interference in a network with cooperative communications for potentially much higher network performance. In cooperative networks, a routing path can be formed with a combination of cooperative transmissions and direct transmissions (DTs), and we call this kind of routing cooperative routing. The important and interesting question this chapter tries to answer is what is the maximum aggregate throughput of a multi‐radio multi‐channel network when the cooperative transmission is available? Current studies on cooperative communications in multi‐hop wireless network generally assume that the network nodes are equipped with only a single antenna [12–20], and it is unclear what capacity and performance gain can be achieved if nodes are equipped with multiple antennas. Despite the large potential benefit, it is highly non‐trivial to make both CC and MRMC techniques to work seamlessly together. Some of the challenges are as follows.

First, the coupled cooperative routing problem and relay selection problem should be solved together. Different from conventional routing in MRMC networks where every node just needs to find the next‐hop node to forward packets toward the destination, with cooperative routing, a neighbor of the transmitter not only needs to serve as a multi‐hop transmission relay (MR) for packet forwarding but may also act as a cooperative relay (CR) of the transmitter for cooperative transmission. The capability for a node or a radio interface to serve as two different types of relay makes multi‐radio cooperative routing and relay node assignment inter‐dependent.

Second, there is a trade‐off between alleviating co‐channel interference and exploiting cooperative diversity. In single‐radio single‐channel cooperative wireless networks, one‐hop neighbors of a transmitter are candidate MR or CR nodes. A transmitter node can determine to use direct transmission and find an MR or cooperative transmission and find a CR to maximize the cooperative transmission gain. Although MRMC can largely relieve the co‐channel interference, only the node, which tunes to the same channel as that of the transmitter, can act as an MR or a CR, which reduces the number of candidate relay nodes. This makes it important and challenging to consider radio‐channel assignment along with cooperative communications.

Third, the use of cooperative relays in cooperative communications makes the network interference condition more complicated than that in a network with only direct transmissions, and it desires careful design to reduce the interference along with the finding of the cooperative routing path and channel assignment in MRMC cooperative networks.

In summary, there is an inter‐dependence among cooperative routing, channel assignment, and relay selection. To enable cooperative communications in MRMC wireless networks and fulfill the complete potential of both techniques, the three problems need to be systematically solved together. A few recent studies [21–25] have begun to investigate interference‐aware cooperative routing algorithms to solve the challenge problems. This chapter presents a practical and distributed solution to effectively exploit both MRMC technique and cooperative diversity to ensure higher performance of a multi‐hop network with dynamic channel conditions and traffic flows. In this design, the cooperative routing at the network layer, channel assignment at the MAC layer, and cooperative communication at the physical layer will work interactively and seamlessly together. The main techniques are as follows:

• Contention‐aware channel utilization metric (CACU): this captures the interference cost from both direct transmission and cooperative transmission. Using CACU as the key routing metric, an interference‐aware cooperative routing algorithm is proposed.

• Traffic‐aware channel condition metric (TACC): it evaluates the channel load condition and triggers the channel‐adjustment procedure to relieve co‐channel interference. Based on TACC, a feasible channel selection algorithm is proposed to ensure active flows (involving either direct transmission or cooperative transmission) to have continuous data transmissions during the channel‐adjustment process. To further prevent the network from being instable due to channel adjustment, a chain‐puzzle detection sub‐algorithm is proposed.

• Local path and relay adjustment algorithm: it further enhances the performance of active flows after channel adjustment.

The remaining of this chapter is organized as follows. We introduce our system model in Section 2. Motivation example and solution overview are presented in Section 3. We present the detailed algorithms on cooperative routing, channel assignment, and local path and relay adjustment in Sections 4–6, respectively. The complete solution is presented in Section 7. Simulation results are given in Section 8. We conclude the work in Section 9.

2. System model

We consider a multi‐hop cooperative wireless network where a node can be equipped with multiple radios. We call this network MRMC cooperative wireless network. There are N nodes in the network. Each node i in the network is equipped with one or more radio interfaces (wireless NIC), represented by I(i). Each radio can serve as a transmitter or a receiver on a channel at a given time. We assume that there are a total of K orthogonal channels in the network, numbered Ch₁, Ch₂, …, Ch_K, and there is no inter‐channel interference. The channel assignment is trivial if the number of orthogonal channels available is at most the minimum number of radios per node I(i), since in this case every node must be assigned all the channels. This chapter assumes that K is larger than ${\max }_{i\in N}I(i)$. A radio is capable of selecting a working channel from the set of orthogonal channels, and the set of working channels of node i is denoted as w(i). Due to the interference constraints, there is no capacity benefit in equipping two different radios of a node with the same channel. There are multiple concurrent flows, denoted by a set F = { F₁, F₂,..., F_M} of M flows. The data for each flow may traverse multiple hops in the network. A flow F_i(S_i →D_i) goes through a pair of source node and destination node, denoted as S_i and D_i, respectively.

There are two transmission modes between any two nodes in the network considered, direct transmission (DT) and cooperative transmission (CT), as shown in Figure 1. Direct transmission mode is widely employed in current wireless networks, where a source node transmits its signal directly to a destination node. The achievable rate of $C_{\text{DT}}(S,D)$ between S and D is expressed as follows:

Figure 1.

Two kinds of transmission modes.

$C_{\text{DT}}(S,D)=W*{\log }_2(1+SNR(S,D)).$E1

A cooperative transmission involves three nodes and three links. Specifically, a collaborative neighbor R overhears the signal from source S and forwards the signal to the destination D, which then combines two signal streams, S→D and R→D, into a single stream that has a higher resistance to channel fading and noise and hence a higher probability of being successfully decoded. The mechanism to accomplish CT is not unique. In Ref. [3], the authors describe and compare the capacity of different cooperative transmission protocols and show that the AF‐RAKE‐based cooperative transmission protocol can achieve the maximum capacity. In AF‐RAKE, R receives signals from S and amplifies and forwards them to D without demodulation or decoding. D uses a RAKE receiver to combine both signal streams of S→D and R→D. The achievable rate of $C_{\text{CT}}(S,R,D)$ between S and D with R as relay under AF‐RAKE mode [3] is given by

$C_{\text{CT}}(S,R,D)=W*{\log }_2(1+SNR(S,D)+\frac{SNR(S,R)*SNR(R,D)}{SNR(S,R)+SNR(R,D)+1}),$E2

$SNR(m,n)=\frac{P_m}{{\sigma }_n^2}|h_{m,n}{|}^2.$E3

In the above equation, P_m denotes the transmission power at node m. h_m,n captures the effects of path loss, shadowing, and fading within the channel between m and n. The noise components are modeled as white Gaussian noise (AWGN). ${\sigma }_n^2$ denotes variance of the background noise at nodes n.

Relay nodes can be categorized into two types based on their functions: a cooperative relay (CR), which operates at the physical layer for cooperative transmission (i.e., node R₆ in flow F₃ in Figure 2), and a multi‐hop relay (MR), which operates at the network layer to relay packets from a source over multiple hops to its destination (i.e., node R₁ in flow F₂ in Figure 2). A node with multiple radios can serve as both CR and MR for multiple flows. For example, R₃ acts as CR relay in F₃, but MR relay for F₄. More complex function roles can be found on R₇, which acts as CR relay in both F₁ and F₃, and MR relay in F₂.

Figure 2.

The MRMC cooperative network.

A cooperative routing path could be a combination of cooperative transmissions and direct transmissions. For example, flow $F_3(S_3\to D_3)=S_3\stackrel{C{h}_2}{\to }{R}_2(R_3)\stackrel{C{h}_3}{\to }{R}_4(R_7)\stackrel{C{h}_1}{\to }{R}_5$

$\stackrel{C{h}_2}{\to }{D}_3(R_6)$,in Figure 2, where the first hop link $l_{S_3{R}_2(R_3)}^{C{h}_2}$, the second hop link $l_{R_2{R}_4(R_7)}^{C{h}_3}$, and the fourth hop link $l_{R_5{D}_3(R_6)}^{C{h}_2}$ adopt cooperative transmission mode with nodes R₃, R₇, and R₆ acting as CR relays, respectively, while the third hop link $l_{R_4{R}_5}^{C{h}_1}$ adopts the direct transmission mode with both R₄ and R₅ being MR relays.

3. Motivation example and solution overview

To help understand the significance of our problem, we first give a motivation example to show that only channel assignment and cooperative routing cannot achieve the good performance. Expired from the example, we give an overview on our solution.

Figure 3 is an MRMC cooperative wireless network consisting of 14 nodes. The small solid dots in each node denote the radios. There are three orthogonal channels available, denoted by Ch₁, Ch_2, and Ch₃. For simplicity, we assume that all the links are free of transmission error, and the raw capacity of each link can be calculated by Eq. (1) or (2) depending on the transmission mode. The communication range and interference range are set to 250 and 550 m, respectively. The network is connected under an initial channel assignment [26] to guarantee the connectivity of network to transmit any possible flows over multiple hops.

Figure 3.

Motivation example.

Initially, there are two flows with their routing paths $F_1(A\to K)=A\stackrel{C{h}_2}{\to }F\stackrel{C{h}_3}{\to }K$ and $F_2(D\to E)=D\stackrel{C{h}_1}{\to }B\stackrel{C{h}_3}{\to }E$, as shown in Figure 3a. According to Eq. (1), the raw capacity of links in these two flows can be calculated directly: C_DT(A,F) = 61.189 Mbps, C_DT(F,K) = 65.9819 Mbps, C_DT(D,B) = 73.1874 Mbps, C_DT(B,E) = 78.8452 Mbps. On channel Ch₃, there are two co‐channel links that interfere with each other, link $l_{FK}^{C{h}_3}$ passed by flow F₁ and link $l_{BE}^{C{h}_3}$ passed by flow F₂. A straightforward way to avoid interference is to apply TDMA to fairly allocate time slots to different flows. As a result, the available capacity of these two links becomes $C_{\text{DT}}{}^{\prime }(F,K)=C_{\text{DT}}(F,K)/2$ = 32.9909 Mbps, $C_{\text{DT}}{}^{\prime }(B,E)=C_{\text{DT}}(B,E)/2$ = 39.4226 Mbps. Assume that all flows transmit a packet at the peak link data rate through a rough calculation that neglects the overhead cost. Constrained by the bottleneck rate of the path, the end‐to‐end throughput of Flow₁ and Flow₂ are $\min \left\{C_{DT}\right(A,F),C_{DT}{}^{\text{'}}(F,K\left)\right\}$ = 32.9909 Mbps and $\min \left\{C_{\text{DT}}\right(D,B),C_{\text{DT}}{}^{\text{'}}(B,E\left)\right\}$ = 39.4226 Mbps. The aggregate network throughput of these two flows is 32.9909 + 39.4226 = 72.4135 Mbps.

In Figure 3b, a new flow F₃(G→J) arrives. To obtain higher cooperative diversity in the network, the potential route for F₃ is chosen as $F_3(G\to J)=G\stackrel{C{h}_3}{\to }I(H)\stackrel{C{h}_1}{\to }J$, where H acts as the CR relay in the flow path. Similarly, the raw capacity of each hop links $l_{GI(H)}^{C{h}_3}$, and $l_{IJ}^{C{h}_1}$ can be calculated, with $C_{\text{DT}}(I,J)$ = 91.8365 Mbps, $C_{\text{CT}}(G,H,I)$ = 51.3242 Mbps. However, there are two co‐channel links that interfere with each other on the channel Ch₁, and three co‐channel links on the channel Ch₃, respectively. The available capacity of these links is calculated as follows: $C_{\text{DT}}{}^{\prime }(A,F)=C_{\text{DT}}(A,F)$ = 61.189 Mbps, $C_{\text{DT}}{}^{\prime }(F,K)=C_{\text{DT}}(F,K)/3$ = 21.90 Mbps, $C_{\text{DT}}{}^{\prime }(D,B)=C_{\text{DT}}(D,B)/2$ = 36.5937 Mbps, $C_{\text{DT}}{}^{\prime }(B,E)=C_{\text{DT}}(B,E)/3$ = 26.2817 Mbps, $C_{\text{CT}}{}^{\prime }(G,H,I)=C_{\text{CT}}(G,H,I)/3$ = 17.1 Mbps, $C_{\text{DT}}{}^{\prime }(I,J)=C_{\text{DT}}(I,J)/2$ = 45.9182 Mbps. As a result, the end‐to‐end throughput of Flow₁, Flow_2, and Flow₃ are min{61.189, 21.90} = 21.90 Mbps, min{36.5937, 26.2871} = 26.2817 Mbps and min{17.1, 45.9182} = 17.1 Mbps. The aggregate throughput of the whole network is 21.90 + 26.2817 + 17.1 = 65.2637 Mbps. Although there are three concurrent transmission flows, the aggregate throughput decreases about 10% compared with that in Figure 3a.

With the above‐selected routes, we apply channel assignment to improve the network performance. In Figure 3c, we change the channel of node G, H, and I from the overloaded channel Ch₃ to the least‐used one Ch₂, which reduces the number of interfering links on channel Ch₃ from three to two. The raw capacity of links on the paths of the three flows becomes $C_{\text{DT}}{}^{\prime }(A,F)=C_{\text{DT}}(A,F)/2$= 30.5945 Mbps, $C_{\text{DT}}{}^{\prime }(F,K)=C_{\text{DT}}(F,K)/2$ = 32.9909 Mbps, $C_{\text{DT}}{}^{\prime }(D,B)=C_{\text{DT}}(D,B)/2$= 36.5937 Mbps, $C_{\text{DT}}{}^{\prime }(B,E)=C_{\text{DT}}(B,E)/2$ = 39.4226 Mbps, $C_{\text{CT}}{}^{\prime }(G,H,I)=C_{\text{CT}}(G,H,I)/2$ = 25.6621 Mbps, $C_{\text{DT}}{}^{\prime }(I,J)=C_{\text{DT}}(I,J)/2$ = 45.9182 Mbps. As a result, the end‐to‐end throughput of Flow₁, Flow₂, and Flow₃ are 30.594, 36.5937, and 25.6621 Mbps, respectively. The aggregate throughput of the three flows in the network is 30.5945 + 36.5937 + 25.6621 = 92.8503 Mbps. The performance is improved almost 42% compared with that in Figure 3b.

Based on the above channel assignment, transmitter nodes would further check whether there exists a better relay node which can be utilized to obtain a better cooperative capacity gain. As shown in Figure 3d, node G can select node L instead of H as the relay node to further improve the performance. The available capacity of cooperative transmission can be calculated as $C_{\text{CT}}{}^{\prime }(G,L,I)=C_{\text{CT}}(G,L,I)/2$ = 66.5462/2 = 33.2731 Mbps. As a result, the end‐to‐end throughput of Flow₁, Flow_2, and Flow₃ are 30.594, 36.5937, and 33.2731 Mbps. After relay adjustment, the aggregate throughput of the whole network is 30.5945 + 36.5937 + 33.2731 = 100.4613 Mbps, which is nearly 1.5 times that in Figure 3b.

Existing studies have demonstrated that the joint optimization problem of routing and channel assignment in multi‐radio multi‐channel wireless network is NP [27], the joint optimization problem of relay selection and cooperative routing is also NP [19]. Compared to the above problems where each considers only two issues, our problem considers three issues and can be generally proven to be NP‐hard. To solve the problem, we propose a solution framework which is formed with three important components. In the following sections, we introduce the detailed algorithms for each part.

First, to obtain cooperative gain and reduce co‐channel interference, every node periodically calculates the routing metric of CACU (contention‐aware channel utilization). Based on this metric, when new flow arrives, an interference‐aware cooperative routing algorithm is run to find the cooperative routing path and select MR and CR nodes along the path.

Second, to adapt to dynamic traffic changes, every node periodically measures the channel condition and calculates TACC metric. When a node's working channel is detected to be overloaded according to the TACC value, a dynamic channel‐adjustment algorithm is triggered to switch the highly loaded channel to a lightly loaded one to relieve the co‐channel interference.

Third, as channel adjustment changes the network topology, a local path segment and relay adjustment algorithm are followed by switching the flow traffic to a new path segment locally according to the new topology.

4. Cooperative route

To quantify the available capacity of a link, we first introduce a new routing metric. Based on the metric, we propose an interference‐aware cooperative routing algorithm to better exploit the benefit of cooperative diversity.

There are several existing routing metrics proposed for multi‐hop wireless networks. Hop count is a basic routing metric widely used. To further consider the wireless channel condition and interference, several improved metrics are also proposed, including ETX, WCETT, MIC, CCM [27], and MIPC [28]. The above routing metrics target for one‐to‐one direct transmissions between two nodes in conventional wireless networks. In cooperative wireless networks, the routing metric should consider multiple‐to‐one cooperative transmissions. As a cooperative transmission involves three links, it may cause more interference in the network, thus reducing the transmission performance. To facilitate the finding of more efficient cooperative routing path for higher throughput, the routing metric should concurrently consider the transmission mode selection and interference impact. To characterize radio transmissions in the presence of interference and identify the co‐channel interference links of a given link, two receiver‐driven interference models are proposed in the literature, the physical model [29] and the protocol model [30].

Our design does not depend on a specific model used. For the convenience of presentation and design, we simply apply a protocol model to illustrate our algorithms in this chapter. We consider link $l_{AB}^{C{h}_i}$ to be the co‐channel interference link of another link $l_{CD}^{C{h}_i}$ if A and B work on the same channel of C and D, and at least one of node pairs (A,C), (A,D), (B,C), and (B,D) is within the interference range. A cooperative transmission may involve three nodes. We consider cooperative link $l_{AB(R)}^{C{h}_i}$ to interfere with another link $l_{CD}^{C{h}_i}$ if A, B, and R work on the same channel of C and D, and at least one of node pairs (A,C), (A,D), (B,C), (B,D), (R,C), and (R,D) is within the interference range.

If a node x transmits data to a node y through the direct transmission, the available capacity $C_{D{T}_a}(x,y,C{h}_i)$ of the direct transmission link $l_{xy}^{C{h}_i}$ is equal to the link capacity $C_{DT}(x,y)$ (calculated using Eq. (1)) deducted by the traffic load of its co‐channel interference links:

$C_{{\text{DT}}_a}(x,y,C{h}_i)=C_{\text{DT}}(x,y)-\sum _{j\in I_{C{h}_i}\left(l\right)}t\left(j\right),$E4

where t(j) is the traffic load on link j, $I_{C{h}_i}(l)$ is the set of co‐channel interference links of $l_{xy}^{C{h}_i}$. Similarly, if node x transmits data to node y with the help of relay z, the available capacity $C_{{\text{CT}}_a}(x,z,y,C{h}_i)$ of a cooperative transmission link $l_{xy(z)}^{C{h}_i}$ can be calculated as

$C_{{\text{CT}}_a}(x,z,y,C{h}_i)=C_{\text{CT}}(x,z,y)-\sum _{j\in I_{C{h}_i}\left(l\right)}t\left(j\right),$E5

where $C_{\text{CT}}(x,z,y)$ is the capacity of the link $l_{xy(z)}^{C{h}_i}$ (calculated using Eq. (2)), $I_{C{h}_i}(l)$ is the set of co‐channel interference links, and t(j) denotes the traffic load on link j.

Therefore, the available capacity of a link (x, y, Ch_i) can be defined as the maximum available capacity among all possible transmission modes

$\begin{array}{l}CACU(x,y,C{h}_i)=\max \left\{C_{D{T}_a}\right(x,y,C{h}_i),\underset{z}{\max }\{C_{C{T}_a}(x,z,y,C{h}_i)\\ :z\in N_{C{h}_i}\left(x\right)and{N}_{C{h}_i}\left(y\right)\left\}\right\},\end{array}$$$E6

where $N_{C{h}_i}(x)$ and $N_{C{h}_i}(y)$ denote the set of neighbors of nodes x and y on the channel Ch_i. Obviously, $CACU(x,y,C{h}_i)=C_{{\text{DT}}_a}(x,y,C{h}_i)$ if the available capacity of direct transmission is larger than the available capacity of the cooperative transmission, otherwise, $CACU(x,y,C{h}_i)=\underset{z}{\max }\{C_{{\text{CT}}_a}(x,z,y,C{h}_i):z\in N_{C{h}_i}(x)\text{ and }{N}_{C{h}_i}(y)\}$. Multiple radios on a node are generally assigned with orthogonal channels. A pair of nodes x and y may have multiple channels to be the same. Based on Eq. (6), the routing metric of link (x,y) is defined as the maximum available capacity among all common channels as follows:

$CACU(x,y)=\underset{C{h}_i\in \omega \left(x\right)\cap \omega \left(y\right)}{\max }CACU(x,y,C{h}_i),$E7

where w(x) and w(y) denote the working channel set of nodes x and y, respectively. CACU metric in Eq. (7) captures the interference cost from both direct transmission and cooperative transmission. Therefore, CACU can be applied to facilitate finding a transmission path with lower interference thus higher capacity. Based on the metric, a node x can decide that it will take direct transmission or cooperative transmission, and determine the channel to use for transmission. In the case that a cooperative transmission is needed, the selected relay node will be informed.

In this chapter, we modified ad hoc on‐demand distance vector (AODV) routing to implement our distributed interference‐aware cooperative routing algorithm to establish the maximum capacity path while considering the flow routing and relay selection, as shown in Algorithm 1. The derived CACU metric is applied to construct the cooperative path. When a source has data to transmit but does not have a path to the destination, it broadcasts a route request (RREQ) for that destination. When an intermediate node receives RREQ, if it is the destination or has a current route to the destination, it generates a route reply (RREP). Otherwise, the node needs to rebroadcast the RREQ with a set of parameters inserted: the CACU metric for each of its outgoing link is calculated based on Eq. (7), and the maximum capacity from the source to itself is calculated based on Algorithm 1 in Figure 4.

Figure 4.

Algorithm 1: interference‐aware cooperative routing.

5. Channel adjustment

As shown in the motivation example of Section 3, the channel adjustment can reduce co‐channel interference and thus increase the aggregate throughput. The main function of channel adjustment is to switch one node's working channel from an overloaded one to a lightly loaded one to obtain better throughput. For practical implementation of the channel adjustment in a cooperative wireless network, we need to answer two basic questions: (1) Which channel to switch to? (2) How to keep the network stable and well connected during the channel adjustment?

Before presenting the detailed channel‐adjustment algorithm, we first introduce a traffic‐aware channel condition metric (TACC) to evaluate the channel load condition. The TACC of node i on channel Ch_m is defined as the channel utilization calculated as the summation of the co‐channel traffic load within this node's two hops:

$TAC{C}_i(C{h}_m)={\displaystyle \sum _{j\in N_{C{h}_m}(i)}\left(t(l_{ij}^{C{h}_m})+{\displaystyle \sum _{k\in N_{C{h}_m}(j)}t(l_{jk}^{C{h}_m})}\right)},$E8

where $N_{C{h}_m}(i)$ is node i's neighbor set on channel Ch_m, $t(l_{ij}^{C{h}_m})$ denotes the traffic load on link $l_{ij}^{C{h}_m}$, while j and k represent the one‐hop and two‐hop neighbors of node i, respectively. The average traffic conditions may be obtained by attaching the information with periodical topology maintenance messages such as Hello over two hops.

When a node finds that the TACC of a working channel exceeds a threshold ${\theta }_1$, that is, $TAC{C}_i(C{h}_m)\ge {\theta }_1$, it will trigger a channel‐adjustment process. The node needs to identify a set of feasible candidate channels and selects the best one to switch to. To improve the network throughput with channel switching, the condition of the candidate channel Ch_b should be better than the condition of the current channel Ch_a. However, the channel adjustment may lead channel Ch_b to be overloaded and result in potential network instability. To avoid this problem, the following two conditions should be satisfied:

$TAC{C}_i\left(C{h}_b\right)+Tloa{d}_i\left(C{h}_a\right)\le {\theta }_2,$E9

$TAC{C}_j\left(C{h}_b\right)+Tloa{d}_i\left(C{h}_a\right)\le {\theta }_2,$E10

where node j is within two hops of node i, Tload_i(Ch_a) is the total traffic load of all links on the original channel Ch_a, expressed as

$Tloa{d}_i\left(C{h}_a\right)=\sum _{j\in N_{C{h}_a}\left(i\right)}t\left(l_{ij}^{C{h}_a}\right).$E11

We set ${\theta }_2$ in Eq. (9) to ${\theta }_2=0.9*{\theta }_1$ so that the TACC of the new channel after the channel switching is less than 90% of TACC trigger threshold to avoid another channel switching and maintain the network stability.

Figure 5 shows an example of channel‐adjustment procedure. There are four flows in the network, F₁(A→I), F₂(A→L), F₃(A→D), and F₄(B→J). When node A finds that Ch₂ is overloaded, it tries to find another channel to switch to. If node A uses Ch₁ as the new channel, then nodes K, B, and F need to switch to Ch₁ to get connected with node A. This will change the traffic load of F₁, F_2, and F₃ on original links $l_{AK}^{C{h}_2}$, $l_{AB}^{C{h}_2}$, and $l_{AF}^{C{h}_2}$ to the links $l_{AK}^{C{h}_1}$, $l_{AB}^{C{h}_1}$, and $l_{AF}^{C{h}_1}$ on the new channel Ch₁. However, this will make Ch₁ overloaded and trigger another channel adjustment, which makes the network unstable. Therefore, Ch₁ is not the feasible candidate channel for node A because it does not satisfy condition in Eq. (9). Instead, according to Eq. (9), node A finds that Ch₃ is the candidate channel and the traffic load is switched from Ch₂ to Ch₃ as shown in Figure 5c.

Figure 5.

An example of channel adjustment.

Besides considering the condition in Eq. (9) to avoid network instability, to justify the extra channel switching overhead, the gains in terms of TACC should be larger than a given threshold ${\theta }_3$:

$\frac{Before\_TAC{C}_i(C{h}_a)}{After\_TAC{C}_i(C{h}_a)}\ge {\theta }_3,$E12

where Before_TACC_i(Ch_a) is the original TACC value of the working channel Ch_a before channel switching, while After_TACC_i(Ch_a) = TACC_i(Ch_b) + Tload_i(Ch_a) is the TACC value of the working channel Ch_b after the channel switching.

Obviously, to obtain a positive benefit of channel switching, ${\theta }_3$ in Eq. (12) should be larger than 1. Moreover, channel adjustment may involve a significant switching overhead such as switching delay and traffic interruption, and frequent channel switching will result in oscillation and severely impact the network performance. Therefore, ${\theta }_3$ should be set by well considering the tradeoff between the switching overhead and the benefit of channel switching. According to Ref. [31], in our simulation, ${\theta }_3$ is set to 1.2. That is, after the channel adjustment, the TACC of the new channel should be at least 20% less than that of the original one. Only when conditions of Eqs. (9), (10), and (12) are satisfied, the node can switch its working channel from Ch_a to Ch_b. To preserve the current flows’ connectivity and stability, connectivity checking should be applied to further identify the feasible channel, which is discussed in the next subsection.

In an MRMC cooperative network, two nodes may have more than one pair of radios connected. If nodes i and j have two pairs of radios directly connected with each other, the channel adjustment does not impact their connectivity. If nodes i and j have only one radio connected with each other over a channel, the channel adjustment may interrupt the transmission of an active flow carried over the link (i,j). To maintain the connectivity of the active flow, the channel switching may be carried by a chain of nodes, with each node on the chain having only a single common channel. We define this problem as chain puzzle.

Cooperative transmission may be more prone to the chain‐puzzle problem. Figure 6 gives two examples to illustrate the chain‐puzzle problem under direct transmission and cooperative transmission, respectively. In Figure 6a, assume that flow F₁(M→A) transmits over the link between nodes M and F using channel Ch₂, if the channel needs to be switched to Ch₃, node F's single‐channel neighbor G must switch to Ch₃. Similarly, after node G switches its channel, node G's single‐channel neighbor B has to switch to Ch₃ too, which will also lead channel switching from node A and thus result in the chain‐puzzle problem. In Figure 6b, D, E, and J work together for cooperative transmission. Assume that nodes C and D currently transmitting over channel Ch₃ want to switch to Ch₁, nodes E and J are D's single‐channel neighbors. To maintain the flow's connectivity, nodes E, J should switch channel from Ch₃ to Ch₁. As a result, K, R, Q, and P also need to switch their working channel from Ch₃ to Ch₁. Chain puzzle again happens.

Figure 6.

Chain‐puzzle problem.

Chain‐puzzle checking becomes an important issue in channel‐adjustment procedure because chain puzzle may cause a number of practical problems. First, a large number of nodes may be involved in a channel switch when chain puzzle happens, which could result in a high overhead. Second, it is difficult to synchronize the switching action among all nodes involved because the signaling used for negotiation needs to propagate through many hops. In the worst case, this may result in flow transmission interruption. Therefore, before a node switches its working channel, chain puzzle should be checked to identify feasible candidate channel to avoid switching channel sequentially, and maintain the network's stability. To facilitate chain‐puzzle checking, we propose two different connectivity rules according to different transmission modes:

Connectivity Rule 1: if any node pair of a direct transmission link passed by an active flow is originally connected, the node pair should remain connected after the channel switching.

Connectivity Rule 2: if any three nodes in an active cooperative transmission are originally connected, they should remain directly connected under a new channel.

Based on the above two connectivity rules, we propose a local two‐hop chain‐puzzle‐checking sub‐algorithm, as shown in Algorithm 2 of Figure 7. When node A checks a new channel Ch_i and finds that (through the communication with its neighbor which needs to switch channel with it) there exists a node which is not within its two‐hop distance but also needs to switch channel to preserve the connectivity of the current flows, the chain puzzle may happen and Ch_i is not a feasible channel for channel adjustment. The results of chain‐puzzle‐checking algorithm depend on the topology of the network. Based on the chain‐puzzle‐checking algorithm, the feasible channel selection algorithm can be presented as in Algorithm 3 of Figure 7.

Figure 7.

Algorithm 2: the chain‐puzzle‐checking algorithm and Algorithm 3: feasible channel selection algorithm.

6. Local routing and relay adjustment

After channel adjustment, the network topology may change. To make flow transmissions continuous under the new topology, some flows may need to adapt their path segments, channels, or relays locally.

As shown in Figure 8a, an active flow F₁(D→O) exists in the network with its original route $F_1(D\to O)=D\stackrel{C{h}_1}{\to }E(J)\stackrel{C{h}_1}{\to }L\stackrel{C{h}_1}{\to }O$. After nodes D, E, and J adjust their working channel from Ch₁ to Ch₃, nodes E and L are not directly connected. Thus, flow F₁ should switch its path locally from $E\stackrel{C{h}_1}{\to }L$ to $E\stackrel{C{h}_3}{\to }Q\stackrel{C{h}_1}{\to }L$. Moreover, after D and E switch their working channel from Ch₁ to Ch₃, besides node J, node N may have the opportunity to support cooperative transmission and provide a higher cooperative gain. As a result, node D would select node N as the relay node instead of J. To make the network stable, the path adaptation and relay adjustment should be performed locally and the corresponding traffic flows should also switch to new path segments. Based on the cooperative routing algorithm in Algorithm 1, we design a local path adaptation and relay adjustment algorithm as shown in Algorithm 4 of Figure 9.

Figure 9.

Algorithm 4: local path adaptation and relay adjustment algorithm.

Figure 8.

Local path adaptation and relay adjustment.

7. Completed solution

The complete algorithm of joint cooperative routing, channel adjustment, and relay selection is shown in Algorithm 5 of Figure 10. To handle the dynamic wireless environment, nodes in the network execute the algorithm locally as follows.

Figure 10.

Algorithm 5: complete algorithm of joint cooperative routing, channel assignment, and relay selection.

When a new flow arrives, the interference‐aware cooperative routing algorithm is applied to find the cooperative routing path with the maximum end‐to‐end available capacity and with the MR and CR relays selected along the path. Every node periodically evaluates the traffic conditions of a channel by calculating the TCAA metric according to Eq. (8) and checking whether its working channel is overloaded. If so, the node first applies Algorithm 3 to identify the feasible channel to switch to. Then, the channel adjustment will be triggered, which is followed by the local path adaptation and relay adjustment through Algorithm 4 for uninterrupted transmissions and better performance.

If each node independently makes a local channel‐adjustment decision, multiple channel‐adjustment requests may be received simultaneously by a node, which either leads to request message collisions or inconsistent requests (if all messages are successfully received). To reduce the chance of simultaneous transmissions of channel‐adjustment messages, we design a channel‐adjustment timer which introduces a random delay before the message sending according to the channel load, and the timer can be set as follows:

$T_{iC{h}_m}=\frac{1}{TAC{C}_i\left(C{h}_m\right)}.$E13

From Eq. (13), obviously, the node with a higher channel load, that is, a larger TACC value, has a lower average timer value, thus an earlier chance of adjusting its overloaded channel. When the channel load is high, the data transmissions should be switched from an overloaded channel to a light‐loaded channel. In Algorithm 5, the channel load is measured with the metric TACC and updated when the TACC timer goes off. A smaller TACC timer would allow for more frequent update of the TACC value at high measurement cost, while a larger TACC timer for smaller measurement cost would make the TACC metric less accurate. In this chapter, we set the TACC timer adaptively according to the traffic pattern in the network taking into account the tradeoff between the accuracy of TACC metric and the measurement cost. If the traffic load is high, the TACC timer reduces but remains above a minimum timeout value T_min. If the traffic load is low, the TACC timer increases but not beyond a maximum timeout value T_max. In this chapter, we set T_min = 20 ms and T_max = 300 ms according to the channel‐monitoring duration mentioned in [32].

8. Simulation

In the simulation, unless otherwise specified, the simulation setting is as follows. Thirty nodes are generated one by one in random locations in a 1000 × 1000 m area. Each new node is ensured to get connected with existing nodes in the network, and the initial channel assignment is done according to [26] to guarantee the connectivity of network to transmit possible flows over multiple hops. A node is equipped with two radio interfaces, and has the maximum transmission range set to 250 m. There are a total of 11 orthogonal channels, and the default number of flows in the network is set as M = 5.

Although ns‐3 and Omnet++ are widespread simulator, cooperative communication is a physical layer technique, and can be very hard to simulate in ns‐3 and Omnet++ if it is not completely impossible. Following the simulation setup in Refs. [17, 19], we evaluate the performance of our proposed algorithm through extensive simulations using MATLAB. Specifically, following the parameter setting in Ref. [19], we set the bandwidth of each channel to W = 22 MHz, the maximum transmission power at every node to 1 W. For simplicity, we assume that h_m,n only considers the distance between nodes m and n and is given by $\left|h_{m,n}\right|=\left|\right|m,n|{|}^{-4}$, where $\left|\right|m,n\left|\right|$ is the distance (in m) between m and n and the path loss index is 4. We assume the variance of noise is 10^-10 W at all nodes. TACC trigger threshold ${\theta }_1$ is set to 200. We set ${\theta }_2$ to ${\theta }_2=0.9*{\theta }_1=180$ to help maintain network stability, and ${\theta }_3$ to 1.2 to balance the switching overhead and benefit of channel switching.

We evaluate the effectiveness of our algorithms by comparing the results from six different implementation schemes. We implement two different cooperative transmission (CT) schemes. The first is our proposed Algorithm 5, denoted as CT_adjustment. In the second scheme, we apply the cooperative routing algorithm in Algorithm 1 to find the cooperative path, without applying channel adjustment or local path adaptation and relay adjustment, which is denoted as CT_No‐adjustment. We also implement four additional schemes based on direct transmission (DT). The first DT scheme is denoted as DT_No‐adjustment, where we use the available capacity calculated in Eq. (7) as the routing metric and apply Algorithm 1 to find the path with the maximum available capacity for each flow. In the second scheme, denoted as DT_ adjustment, channel and local path segment adjustment in Sections 5 and 6 are applied periodically to obtain better performance. The third and fourth schemes take two different routing metrics proposed in the literature to find the routing path: a HOP scheme, which uses hop count as routing metric and finds the shortest path, and an ETT scheme [27], which captures the packet transmission time in a time unit.

Two metrics are used to evaluate the performance. One is aggregate throughput which is the aggregative throughput of all flows. The other is minimum throughput, which is the minimum of all flows’ throughput. Various factors affect the performance. We perform two set of simulations to analyze the effect of node density and number of orthogonal channel. As follows, we show the simulation results, respectively. With the same topology and flows, we run the six schemes orderly to obtain the two metrics.

8.1. Impact of node density

To investigate how the node density impacts the network performance, we vary the number of nodes D from 30 to 120. When the number of nodes increases, the set of candidate relay nodes for cooperative relay (CR) and multi‐hop relay (MR) becomes larger. Therefore, the aggregate rate and minimum rate under all routing schemes increase, as shown in Figure 11.

Figure 11.

Throughput results under network with different node density.

Among all the routing schemes, the aggregate throughput and the minimum throughput increase the fastest under our CT_adjustment. With well‐designed algorithms, our CT_adjustment can more effectively exploit the resources of relay nodes and multiple channels to achieve high cooperative gain when the number of nodes is large. Our CT_adjustment has the largest aggregate throughput and minimum throughput. At the node density 120, the aggregate throughput of our CT_adjustment is 382, 270, 276, 127, 36, and 112% higher than those of HOP, ETT, DT_No‐adjustment, DT‐adjustment, CT_No‐adjustment, and CT‐adjustment, respectively. The minimum throughput of CT_adjustment is 527, 317, 235, 124, 74, and 124% higher than those of HOP, ETT, DT_No‐adjustment, DT‐adjustment, and CT_No‐adjustment, respectively.

Although the performance under CT_No‐adjustment is much better than that under DT_No‐adjustment, the performance under DT_adjustment is better than that under CT_No‐adjustment. As discussed in “Introduction”, under CT_No‐adjustment, although relay nodes can help to increase the capacity of a transmission pair, cooperative transmissions may also cause interference to more network nodes and consequently significant performance degradation. Compared with CT_No‐adjustment, CT adjustment can obtain much larger cooperative transmission gain, which demonstrates the effectiveness of our algorithms in relieving the interference raised by cooperative relays. The performance gain is also attributed to our algorithms for channel adjustment and adaptation of local path segments and relays. By exploiting the MRMC technique, the co‐channel interference is alleviated, which is the key reason for the throughput improvement.

8.2. Impact of the number of orthogonal channel

We vary the number of orthogonal channels from 1 to 15 in the network while setting other parameters to the default values. As shown in Figure 12, the aggregate network throughput and minimum flow throughput achieved by all the routing schemes increase when the number of orthogonal channels increases initially, while remaining the same when the number of channels is large enough for the tested five flows. As each node has only two radio interfaces and the traffic in the network is limited, extra channels cannot be fully utilized. Therefore, increasing the number of channels cannot unboundedly increase the performance of the routing schemes for the tested five flows. We observe that CT_adjustment can exploit available orthogonal channels to increase the throughput and achieve the best performance. When the number of channels is larger than 5, CT_adjustment achieves 251, 228, 180, 22, and 126% higher aggregate throughput compared to HOP, ETT, DT_No‐adjustment, DT‐adjustment, and CT_No‐adjustment, respectively.

Figure 12.

The impact of number of orthogonal channels.

9. Conclusion

To fulfill the complete potential of cooperative transmission in MRMC cooperative networks, a solution is proposed where cooperative routing at the network layer, channel assignment at the MAC layer, and cooperative communication at the physical layer can work coherently together to maximize the throughput. The simulation results demonstrate that cooperative communication can achieve a large capacity gain in MRMC wireless networks under well‐designed algorithms. Compared to direct transmission in multi‐radio multi‐channel, cooperative transmission in multi‐radio multi‐channel can increase the aggregate throughput more than 1.8 times when there are at least five orthogonal channels.

Acknowledgments

Acknowledgments

This work is supported by the National Natural Science Foundation of China under grant nos.6157218, 61472130, 71331001, and 71420107027, U.S. National Science Foundation under grant no. CNS 1526843, the Science and Technology Projects of Hunan Province (No. 2016JC2075), and the Research Foundation of Education Bureau of Hunan Province, China (No. 16C0047).