# Cross-Layer Throughput Optimization in Cognitive Radio Networks with SINR Constraints

Authors: Miao Ma; Danny H. K. Tsang
Journal: International Journal of Digital Multimedia Broadcasting
 (2010)

---

## Abstract

Recently, there have been some research works in the design of cross-layer protocols for cognitive radio (CR) networks, where the Protocol Model is used to model the radio interference. In this paper we consider a multihop multi-channel CR network. We use a more realisticSignal-to-Interference-plus-Noise Ratio (SINR) model for radio interference and study the following cross-layer throughput optimization problem: (1) Given a set of secondary users with random but fixed location, and a set of traffic flows, what is the max-min achievable throughput? (2) To achieve the optimum, how to choose the set of active links, how to assign the channels to each active link, and how to route the flows? To the end, we present a formal mathematical formulation with the objective of maximizing the minimum end-to-end flow throughput. Since the formulation is in the forms of mixed integer nonlinear programming (MINLP), which is generally a hard problem, we develop a heuristic method by solving a relaxation of the original problem, followed by rounding and simple local optimization. Simulation results show that the heuristic approach performs very well, that is, the solutions obtained by the heuristic are very close to the global optimum obtained via LINGO.


---

## Body

## 1. Introduction

Cognitive radio technology [1–3] provides a novel way to solve the spectrum underutilization problem. In cognitive radio (CR) networks, there are two types of users: primary users and secondary users. A primary user is the rightful owner of a channel, while a secondary user periodically scans the channels, identifies the currently unused channels, and accesses the channels opportunistically. The secondary users organize among themselves an ad hoc network and communicate with each other using these identified available channels. As a result, a multihop multichannel CR network is formed. How to efficiently share the spectrum holes among the secondary users, therefore, is of interest.In this paper, we are interested in studying the opportunistic spectrum sharing problem among the secondary users, but our concern is on a cross-layer design of spectrum sharing and routing with SINR constraints. The main issues we are going to address include the following.(1) Given a set of secondary users with random but fixed location, and a set of traffic flows, what is the max-min achievable throughput?(2) To achieve the optimum, how to choose the set of active links, how to assign the channels to each active link, and how to route the flows?There have been some research works on cross-layer protocols in CR networks. Hou et al. [4] characterized the behaviors and constraints for a cognitive radio network from multiple layers, including modeling the spectrum sharing and subband division, scheduling and interference constraints, and flow routing. Shi and Hou [5] developed a formal mathematical model for scheduling feasibility under the influence of power control; the formulation is a cross-layer design optimization problem encompassing power control, scheduling, and flow routing. Subsequently, on the basis of the work in [5], Shi and Hou [6] implemented their cross-layer optimization framework in a distributed manner and compared the performance of the distributed optimization algorithm with the upper bound and validated the efficacy. The work in [4–6] assume that the links are unidirectional, and to avoid collision only the designated receiver is need to be out of the interference caused by another transmitter. Ma and Tsang [7] proposed a cross-layer design on spectrum sharing and power control, where bidirectional links were considered and all nodes were operated at an optimal common power level at which the total spectrum utilization is maximized. Ma and Tsang [8] also proposed a cross-layer design on spectrum sharing and routing, where the channel heterogeneity (which is a unique feature for cognitive radio) was considered and modeled.In the previous work, however, a common limitation exists since all such cross-layer protocols [4–8] are designed on the basis of the Protocol Model for radio interference, where the interference range is assumed to be limited and no interference is caused beyond the interference range. As a result, in the Protocol Model the conflict relationships among the wireless links are binary. However, in reality the aggregate interference of a large number of far transmitters could be significant and may cause interference on a receiver, and a near transmitter may not necessarily cause interference on a receiver if the transmitter properly controls its transmission power. Therefore, a definite criticism of the Protocol Model is that interference is not a binary relationship [9–11].In order to solve the above realistic problems, theSignal-to-Interference-plus-Noise Ratio (SINR) model is adopted. The rationale of SINR model is to compare the SINR with the additive interference calculation at the receiver with a threshold. Some researchers have adopted the SINR model when they consider the link scheduling, power control, or throughput improvement and and so forth. in wireless networks. For example, Brar et al. [11] investigated throughput improvements in wireless mesh networks by replacing CSMA/CA with an STDMA scheme where transmissions were scheduled according to the SINR model. Chafekar et al. [12] studied a cross-layer latency minimization problem in wireless networks with SINR model for interference. Behzad and Rubin [13] developed a new mathematical programming formulation for minimizing the schedule length in multihop wireless networks while meeting the requirements on the SINR at intended receivers.In this paper, we consider a multihop multi-channel CR network. We adopt the (more realistic)Signal-to-Interference-plus-Noise Ratio (SINR) model to study the wireless channel interference. Different from the work in [4–6], we consider the links being bidirectional because we believe the link level acknowledgments in an ad hoc network are a must. We propose a cross-layer optimization framework which jointly considers the spectrum sharing and routing with SINR constraints. The optimization problem is in the forms of a mixed integer nonlinear programming (MINLP) and the objective is to maximize the minimum end-to-end flow throughput. Since the MINLP formulation is NP-hard in general, we present a heuristic methodology by solving a relaxation of the original problem, followed by rounding and simple local optimization. Simulation results show that the heuristic approach works very well; that is, the solutions obtained by the heuristic are very close to the global optimum obtained via LINGO [14].The rest of this paper is organized as follows. In Section2, we describe the assumptions and system model. Section 3 introduces two interference models: one is protocol model and the other is SINR model. Section 4 presents the cross-layer design of spectrum sharing and routing with SINR constraints, and the formulation is in the forms of a mixed integer nonlinear programming (MINLP) problem. The heuristic approach is proposed in Section 5 to solve the MINLP problem. Section 6 presents the simulation results. Finally, Section 7 concludes the paper.


## 2. Assumptions and System Model

We consider a cognitive radio (CR) network withn secondary users, denoted by the set V and the cardinality |V|=n. There are M orthogonal channels in the network, denoted by the set C and the cardinality |C|=M. Each secondary user individually detects the available channels, and the set of available channels that can be used for communication is different from node to node. Let Ci denote the set of available channels observed by node i, and we have Ci⊆C.Each secondary useri (where 1≤i≤n) has a programmable number of radio interfaces, denoted by γi. We assume that the radio interface is able to tune in a wide range of channels, but at a specific time each radio interface can only operate on one channel [15].


### 2.1. Static Node Location with a Centralized Server

We assume that the node locations are static. We also assume the set of available channel at each secondary user is static. This corresponds to the applications with a slow varying spectrum environment (e.g., TV broadcast bands). We assume that there exists a centralized server in the CR network. Each secondary user reports its location and the set of available channels to the spectrum server. The spectrum management and flow routing, therefore, is simple and coordinated. Note that the formulations in the work [4, 5, 8] are also centralized and for static scenario (i.e., both node location and set of available channels at each node are static). Table 1 lists the notations used in this paper.Table 1
Notations.
SymbolMeaningVSet of secondary usersnNumber of secondary users|V|ESet of potential linksGNetwork graphCSet of available channelsMNumber of available channels|C|EiSet of links incident on nodeiCiSet of available channels at nodeiCeSet of available channels at linkeγiNumber of radio interfaces at nodeiriTransmission range for nodeiRiInterference range for nodeiΔGuard zoneE′Set of links that have simultaneous transmissions with linke by using a same channelEm′Set of links that have simultaneous transmissions with linke by using channel mPCommon transmission powerNiNoise power at nodeiIiInterference power at nodeiNNoise power at each nodeβThe minimum threshold to decode a transmission at a receiverdijDistance between nodesi and jGijPropagation gain from nodei to node jηPath loss exponentxemBinary variable indicating if linke is active on channel mBemCapacity of linke by using channel mTMinimum end-to-end flow throughputWBandwidth of a channelQNumber of communication sessionss(q)Source node for sessionqd(q)Destination node for sessionqfi,jqTraffic flow fromi to j for session qfj,iqTraffic flow fromj to i for session q


### 2.2. Bidirectional Links

We consider bidirectional links, rather than unidirectional links, due to two reasons [16].(1)
Wireless medium is lossy. We cannot assume that a packet can be successfully received by a neighbor unless the neighbor acknowledges it. In an ad hoc network, the link level acknowledgments are necessary.(2)
Medium access controls such as IEEE 802.11 implicitly rely on bi-directionality assumptions. For example, a RTS-CTS exchange is usually used to perform virtual carrier sensing.Thus, if nodei can transmit data to node j and vice versa, then we represent this by a (bidirectional) link, denoted by e=(i,j), between node i and node j. Moreover, we let Ce denote the set of available channels for the link e, and we have Ce=Ci∩Cj.


### 2.3. Common Transmission Power

According to the study by Narayanaswamy et al. [16], to ensure that links are bidirectional, the simplest approach is to assume that nodes are homogeneous; that is, nodes transmit at the same power. In this paper we assume that each secondary user is equipped with an omnidirectional antenna. Similar to [16], we also assume that each secondary user transmits at the same power. Note that this assumption is used in [4] as well.Abidirectional link, denoted by e=(i,j), can be established between nodes i and j if there exists a transmission power P under which the Signal-to-Noise Ratio (SNR) in the absence of cochannel interference at nodes i and j is not less than a threshold β, that is,(1)P·GijNj≥β,P·GjiNi≥β,
where β is signal-to-noise Ratio (SNR) threshold, Gij (and Gji) denotes the channel propagation gain from i to j (and from j to i), and Nj (and Ni) denotes the noise power at node j (and node i). Since it has been commonly assumed that Gij is equal to Gji [4–8, 17–21], and Ni is equal to Nj, we make the same assumptions here and thus we have(2)P·GijN≥β.We letEi denote the set of links incident on node i, which can be obtained by(3)Ei={e:P·GijN≥β}.
Let E denote the union of Ei; we have(4)E=⋃i∈VEi.As a result, we obtain anundirected connectivity graph G=(V,E) to represent the CR network, where V is the set of secondary users denoted by the vertices of the graph, and E is the set of edges between two vertices (i.e., secondary users).


## 2.1. Static Node Location with a Centralized Server

We assume that the node locations are static. We also assume the set of available channel at each secondary user is static. This corresponds to the applications with a slow varying spectrum environment (e.g., TV broadcast bands). We assume that there exists a centralized server in the CR network. Each secondary user reports its location and the set of available channels to the spectrum server. The spectrum management and flow routing, therefore, is simple and coordinated. Note that the formulations in the work [4, 5, 8] are also centralized and for static scenario (i.e., both node location and set of available channels at each node are static). Table 1 lists the notations used in this paper.Table 1
Notations.
SymbolMeaningVSet of secondary usersnNumber of secondary users|V|ESet of potential linksGNetwork graphCSet of available channelsMNumber of available channels|C|EiSet of links incident on nodeiCiSet of available channels at nodeiCeSet of available channels at linkeγiNumber of radio interfaces at nodeiriTransmission range for nodeiRiInterference range for nodeiΔGuard zoneE′Set of links that have simultaneous transmissions with linke by using a same channelEm′Set of links that have simultaneous transmissions with linke by using channel mPCommon transmission powerNiNoise power at nodeiIiInterference power at nodeiNNoise power at each nodeβThe minimum threshold to decode a transmission at a receiverdijDistance between nodesi and jGijPropagation gain from nodei to node jηPath loss exponentxemBinary variable indicating if linke is active on channel mBemCapacity of linke by using channel mTMinimum end-to-end flow throughputWBandwidth of a channelQNumber of communication sessionss(q)Source node for sessionqd(q)Destination node for sessionqfi,jqTraffic flow fromi to j for session qfj,iqTraffic flow fromj to i for session q


## 2.2. Bidirectional Links

We consider bidirectional links, rather than unidirectional links, due to two reasons [16].(1)
Wireless medium is lossy. We cannot assume that a packet can be successfully received by a neighbor unless the neighbor acknowledges it. In an ad hoc network, the link level acknowledgments are necessary.(2)
Medium access controls such as IEEE 802.11 implicitly rely on bi-directionality assumptions. For example, a RTS-CTS exchange is usually used to perform virtual carrier sensing.Thus, if nodei can transmit data to node j and vice versa, then we represent this by a (bidirectional) link, denoted by e=(i,j), between node i and node j. Moreover, we let Ce denote the set of available channels for the link e, and we have Ce=Ci∩Cj.


## 2.3. Common Transmission Power

According to the study by Narayanaswamy et al. [16], to ensure that links are bidirectional, the simplest approach is to assume that nodes are homogeneous; that is, nodes transmit at the same power. In this paper we assume that each secondary user is equipped with an omnidirectional antenna. Similar to [16], we also assume that each secondary user transmits at the same power. Note that this assumption is used in [4] as well.Abidirectional link, denoted by e=(i,j), can be established between nodes i and j if there exists a transmission power P under which the Signal-to-Noise Ratio (SNR) in the absence of cochannel interference at nodes i and j is not less than a threshold β, that is,(1)P·GijNj≥β,P·GjiNi≥β,
where β is signal-to-noise Ratio (SNR) threshold, Gij (and Gji) denotes the channel propagation gain from i to j (and from j to i), and Nj (and Ni) denotes the noise power at node j (and node i). Since it has been commonly assumed that Gij is equal to Gji [4–8, 17–21], and Ni is equal to Nj, we make the same assumptions here and thus we have(2)P·GijN≥β.We letEi denote the set of links incident on node i, which can be obtained by(3)Ei={e:P·GijN≥β}.
Let E denote the union of Ei; we have(4)E=⋃i∈VEi.As a result, we obtain anundirected connectivity graph G=(V,E) to represent the CR network, where V is the set of secondary users denoted by the vertices of the graph, and E is the set of edges between two vertices (i.e., secondary users).


## 3. The Interference Model

In wireless networks, there are three types of interference:duplexing interference, primary interference, and secondary interference. In this paper, we assume that links using different channels do not interfere with each other. Interference only occurs among the links sharing the same channel.Theduplexing interference constraint [22] only prohibits any node from simultaneously transmitting and receiving on any frequency band (i.e., the case in Figure 1 is not allowed).Figure 1
Duplexing interference constraint.Theprimary interference constraint prohibits any node from simultaneously transmitting or receiving on any band (i.e., neither case in Figures 2(a), 2(b) nor 2(c) is allowed). In other words, links that shared a common node cannot transmit or receive simultaneously on any channel. Obviously, the duplexing constraint is less stringent than the primary interference constraint. And also, the duplexing and primary interference constraints are applicable to the links which share a common node (see Figures 1 and 2), and particularly, these constraints hold irrespective of the interference model.Primary interference constraint.
(a)(b)(c)Thesecondary interference constraint, on the other hand, further prohibits any node from transmitting when a neighbor node within its interference range is receiving from another node. Different from the duplexing and primary interference constraints, the secondary interference constraints are applicable to those links which do not share a common node (see Figure 8 shown in the appendix for better understanding).For the purpose of modeling the secondary interference, there are two models [23, 24]: the Protocol Model and the Physical Model. Since rationale of the Physical Model is based on the SINR at the receiver, we call the Physical Model as the SINR model hereinafter in this paper. The relationship of these three types of interferences is shown in Figure 3.Figure 3
Relationship of three types of interferences.


### 3.1. The Protocol Model

Gupta and Kumar proposed the Protocol Model [23] which implicitly assumed that links are unidirectional. With this assumption, collisions only occur when the designated receiver is interfered by another transmitter. Basically, the Protocol Model assumes that the interference range is limited and no interference will be caused beyond the interference range. We let ri and Ri denote the transmission range and interference range for any node i, respectively; then we have Ri=(1+Δ)ri, where Δ is the guard zone to prevent a neighboring node from transmitting on the same channel at the same time [23]. The Protocol Model claims that a transmission from node i to node j is successful if and only if any node k which may cause interference on node j (i.e., if dkj≤Rk where dkj denotes the distance between k and j) is not simultaneously transmitting.A more realistic version, however, assumes that IEEE 802.11 MAC is employed and thus the links are bidirectional (due to RTS-CTS and ACK exchange). We usually call this version as 802.11-style Protocol Model [7, 8]. Suppose that link e=(i,j) and link e′=(k,h) are established and both are bidirectional. They are also active on a same channel. The 802.11-style Protocol Model states that a transmission on link e between nodes i and j is successful if and only if for any link e′=(k,h), such that dkj≤Rk or dki≤Rk or dhj≤Rh or dhi≤Rh, is not simultaneously transmitting.Note that the Protocol Model leads tobinary conflict relationships among the wireless links. In other words, any two links either interfere with each other or can be active simultaneously, regardless of the other ongoing signal transmissions.


### 3.2. The SINR Model

As we mentioned before, in reality the aggregate interference of a large number of far transmitters could be significant and may cause interference at the receiver, and a near transmitter may not necessarily cause interference at the receiver if the transmitter properly controls its transmission power. Thus, the main limitation of the Protocol Model is that interference is not a binary relationship. These problems can be overcome by means of the SINR model, whose rationale is as follows.


#### 3.2.1. Unidirectional Links

Before we consider bidirectional link, let us first consider unidirectional link. For clarification, we lete=i→j and e′=k→h denote two unidirectional links and suppose that they are active on a same channel. The transmission from node i is successfully received by node j if and only if the SINR at the receiving node j is not less than a threshold β. That is,(5)P·GijIj+N≥β,
where Ij denotes the interference power at node j. To calculate Ij, we need to sum all the links {e′=k→h} that have simultaneous transmissions with link e on a same channel. Therefore we have(6)P·GijP·∑k→h∈E′Gkj+N≥β,
where E′ contains all links that have transmissions concurrent with link e by using a same channel. The SINR model accurately captures the fact that interference is caused by aggregate effect of the simultaneous active links.


#### 3.2.2. Bidirectional Links

Next, we extend the SINR model from unidirectional link to bidirectional link. To distinguish from the unidirectional links, we lete=(i,j) and e′=(k,h) denote two bidirectional links and suppose that they are active on a same channel. Because the interference raised by node k and node h might be different, we need to choose the maximum one. To ensure the transmission on link e between nodes i and j to be successful, the SINR at both nodes i and j is not less than a threshold β. We also need to sum all the links {e′=(k,h)} that have simultaneous transmissions with link e on a same channel. To the end, we obtain(7)P·GijP·∑(k,h)∈E′max(Gkj,Ghj,Gki,Ghi)+N≥β.Note that the SINR model is more accurate than the Protocol Model since it better captures the physical propagation. Moreover, in the SINR model a correct packet reception is allowed even in the presence of (moderate) interference, and the cumulative character of interference is taken into account. The main drawback of this model lies in its high complexity, as the interference is described as the complex mathematical relationships.


## 3.1. The Protocol Model

Gupta and Kumar proposed the Protocol Model [23] which implicitly assumed that links are unidirectional. With this assumption, collisions only occur when the designated receiver is interfered by another transmitter. Basically, the Protocol Model assumes that the interference range is limited and no interference will be caused beyond the interference range. We let ri and Ri denote the transmission range and interference range for any node i, respectively; then we have Ri=(1+Δ)ri, where Δ is the guard zone to prevent a neighboring node from transmitting on the same channel at the same time [23]. The Protocol Model claims that a transmission from node i to node j is successful if and only if any node k which may cause interference on node j (i.e., if dkj≤Rk where dkj denotes the distance between k and j) is not simultaneously transmitting.A more realistic version, however, assumes that IEEE 802.11 MAC is employed and thus the links are bidirectional (due to RTS-CTS and ACK exchange). We usually call this version as 802.11-style Protocol Model [7, 8]. Suppose that link e=(i,j) and link e′=(k,h) are established and both are bidirectional. They are also active on a same channel. The 802.11-style Protocol Model states that a transmission on link e between nodes i and j is successful if and only if for any link e′=(k,h), such that dkj≤Rk or dki≤Rk or dhj≤Rh or dhi≤Rh, is not simultaneously transmitting.Note that the Protocol Model leads tobinary conflict relationships among the wireless links. In other words, any two links either interfere with each other or can be active simultaneously, regardless of the other ongoing signal transmissions.


## 3.2. The SINR Model

As we mentioned before, in reality the aggregate interference of a large number of far transmitters could be significant and may cause interference at the receiver, and a near transmitter may not necessarily cause interference at the receiver if the transmitter properly controls its transmission power. Thus, the main limitation of the Protocol Model is that interference is not a binary relationship. These problems can be overcome by means of the SINR model, whose rationale is as follows.


### 3.2.1. Unidirectional Links

Before we consider bidirectional link, let us first consider unidirectional link. For clarification, we lete=i→j and e′=k→h denote two unidirectional links and suppose that they are active on a same channel. The transmission from node i is successfully received by node j if and only if the SINR at the receiving node j is not less than a threshold β. That is,(5)P·GijIj+N≥β,
where Ij denotes the interference power at node j. To calculate Ij, we need to sum all the links {e′=k→h} that have simultaneous transmissions with link e on a same channel. Therefore we have(6)P·GijP·∑k→h∈E′Gkj+N≥β,
where E′ contains all links that have transmissions concurrent with link e by using a same channel. The SINR model accurately captures the fact that interference is caused by aggregate effect of the simultaneous active links.


### 3.2.2. Bidirectional Links

Next, we extend the SINR model from unidirectional link to bidirectional link. To distinguish from the unidirectional links, we lete=(i,j) and e′=(k,h) denote two bidirectional links and suppose that they are active on a same channel. Because the interference raised by node k and node h might be different, we need to choose the maximum one. To ensure the transmission on link e between nodes i and j to be successful, the SINR at both nodes i and j is not less than a threshold β. We also need to sum all the links {e′=(k,h)} that have simultaneous transmissions with link e on a same channel. To the end, we obtain(7)P·GijP·∑(k,h)∈E′max(Gkj,Ghj,Gki,Ghi)+N≥β.Note that the SINR model is more accurate than the Protocol Model since it better captures the physical propagation. Moreover, in the SINR model a correct packet reception is allowed even in the presence of (moderate) interference, and the cumulative character of interference is taken into account. The main drawback of this model lies in its high complexity, as the interference is described as the complex mathematical relationships.


## 3.2.1. Unidirectional Links

Before we consider bidirectional link, let us first consider unidirectional link. For clarification, we lete=i→j and e′=k→h denote two unidirectional links and suppose that they are active on a same channel. The transmission from node i is successfully received by node j if and only if the SINR at the receiving node j is not less than a threshold β. That is,(5)P·GijIj+N≥β,
where Ij denotes the interference power at node j. To calculate Ij, we need to sum all the links {e′=k→h} that have simultaneous transmissions with link e on a same channel. Therefore we have(6)P·GijP·∑k→h∈E′Gkj+N≥β,
where E′ contains all links that have transmissions concurrent with link e by using a same channel. The SINR model accurately captures the fact that interference is caused by aggregate effect of the simultaneous active links.


## 3.2.2. Bidirectional Links

Next, we extend the SINR model from unidirectional link to bidirectional link. To distinguish from the unidirectional links, we lete=(i,j) and e′=(k,h) denote two bidirectional links and suppose that they are active on a same channel. Because the interference raised by node k and node h might be different, we need to choose the maximum one. To ensure the transmission on link e between nodes i and j to be successful, the SINR at both nodes i and j is not less than a threshold β. We also need to sum all the links {e′=(k,h)} that have simultaneous transmissions with link e on a same channel. To the end, we obtain(7)P·GijP·∑(k,h)∈E′max(Gkj,Ghj,Gki,Ghi)+N≥β.Note that the SINR model is more accurate than the Protocol Model since it better captures the physical propagation. Moreover, in the SINR model a correct packet reception is allowed even in the presence of (moderate) interference, and the cumulative character of interference is taken into account. The main drawback of this model lies in its high complexity, as the interference is described as the complex mathematical relationships.


## 4. Cross-Layer Design of Spectrum Sharing and Routing

In this section, we present a cross-layer optimization framework which jointly designs the spectrum sharing and routing. Spectrum sharing can be done either in time domain or in frequency domain. In this paper, we consider frequency domain channel assignment. Spectrum sharing is to determine which link is going to be active and which channel will be assigned to each active link, and our target is to form aconflict-free topology. Routing is to determine which path each traffic flow is going to travel from the source node to the destination node. We allow multipath for each traffic flow. Different from the previous work, in this paper, we adopt the SINR model for radio interference and consider links being bidirectional.


### 4.1. Link Assignment

We say that linke is active only if there is a transmission on channel m over link e. We define a 0-1 binary variable xem as follows:(8)xem={1iflinkeisactiveonchannelm,0otherwise.


### 4.2. Interference Constraints

In this paper, we consider both primary and secondary interference constraints. We term the secondary interference constraints as theSINR constraints hereinafter in this paper, since we use the SINR model to model them.In the remaining part of this subsection, we lete=(i,j) denote a link and let e′=(k,h) denote another link. Both links are active and use a same channel m for transmission.


#### 4.2.1. Primary Interference Constraints

By using a same channel, each node can either transmit or receive but not both, at a given time. In other words, links that share a common node cannot transmit or receive simultaneously on any channel.For ease of presentation and also for notational convenience,each link is also understood as a set of two nodes; then we define(9)e∩e′{=∅ifi≠kandj≠kandi≠handj≠h,≠∅ifi=korj=kori=horj=h.Clearly, we use the notatione∩e′=∅ to denote that the two links e and e′ do not share a common node, and the notation e∩e′≠∅ to denote that the two links e and e′ share a common node.Thus, the primary interference constraint can be expressed as follows:(10)xem+xe′m≤1(m∈Ce∩Ce′,e′∩e≠∅,e′≠e,e′∈E,e∈E).


#### 4.2.2. SINR (i.e., Secondary Interference) Constraints

For the links that donot share a common node but share a common channel, they are applicable to the SINR constraints if the links are active simultaneously. That is, a transmission on a bidirectional link e=(i,j) is successful if and only if the SINR at either node i or node j is not less than the minimum required threshold β. This leads to the following constraint: (11)PGijxem-βP∑e′∈Em′max(Gkj,Ghj,Gki,Ghi)xe′m-βN≥Υ(xem-1)(m∈Ce∩Ce′,e∩e′=∅,e′∈E,e∈E),
where Em′ contains all links that have transmissions concurrent with link e by using channel m. Similar to [13], we introduce a sufficiently large positive number Υ in the constraint (11), where the constraint becomes “redundant” when link e is not active (i.e., xem=0). Notice that we only sum the interference caused by those active links because link e′ will not cause any interference on link e whenever link e′ is not active (i.e., xe'm=0). And also note that when we calculate the interference caused by the active link e′=(k,h), we choose the maximum interference caused from either node k or node h to either node i or node j (due to bidirectional link).


### 4.3. Node-Radio Constraint

A node can establish multiple links with its neighboring nodes if it can tune each of its radio interface to a different channel. However, the number of established links at each node is constrained by the number of its radio interfaces. This leads to the following constraint:(12)∑e∈Ei∑m∈Cexem≤γi(i∈V).


### 4.4. Multipath Routing Constraints

We consider multiple traffic flows in the network. We term the traffic flow for each source-destination pair as a communication session and useq (q=1,2,…,Q) to index each session. Let s(q) and d(q) represent the source node and destination node for session q. Because the links are bidirectional, the traffic flow on each link can be in either direction. Thus, for any link e=(i,j), we let fi,jq (and fj,iq) denote the traffic flow traveling from i to j (and from j to i) for the session q, where (i,j)∈E,i≠j. For each traffic flow, we allow multi-path routing.Our definition of the maximum throughput ismax-min flow rate [25]. That is, our target is to maximize the minimum end-to-end flow throughput that can be achieved in the network. Therefore, the multi-path routing constraints are listed as follows: (13)fi,jq≥0,fj,iq≥0((i,j)∈E,q∈Q),(14)∑k:k≠d(q),(k,i)∈Eifk,iq=∑j:j≠s(q),(i,j)∈Eifi,jq(i≠d(q),i≠s(q),i∈V,q∈Q),(15)∑j:(i,j)∈Eifi,jq≥T(i=s(q),q∈Q),(16)∑j:(j,i)∈Eifj,iq≥T(i=d(q),q∈Q),(17)∑q∈Qfi,jq+∑q∈Qfj,iq≤∑m∈CeBem(e=(i,j),e∈E),
where T is the minimum end-to-end throughput for every session.The constraint (13) restricts the amount of flow on each link to be nonnegative. The constraint (14) states that at each node, except the source node and destination node, the amount of incoming flow is equal to the amount of outgoing flow. The constraint (15) represents that the minimum outgoing flow from each source node is at least T. The constraint (16) states that the minimum incoming flow to the destination node is at least T. The constraint (17) indicates that the sum of the flows over all sessions traversing a link cannot exceed the link capacity.To calculate the link capacity, we letW denote the bandwidth of each channel, and let Bem denote the capacity of link e by using channel m. Assuming Gaussian noise and interference, we have (18)Bem=Wlog2(1+PGjixemP·∑e′∈Em′max(Gkj,Ghj,Gki,Ghi)xe′m+N)(m∈Ce∩Ce′,e∩e′=∅,e′∈E,e∈E).


### 4.5. Problem Formulation

We aim to maximize the minimum end-to-end throughput, and this optimization problem can be formulated as(19)maxT(20)Subjectto:xem=0,1(m∈Ce,e∈E),(21)xem+xe′m≤1(m∈Ce∩Ce′,e′∩e≠∅,e′≠e,e′∈E,e∈E),(22)PGijxem-βP∑e′∈Em′max(Gkj,Ghj,Gki,Ghi)xe'm-βN≥Υ(xem-1)(m∈Ce∩Ce′,e∩e′=∅,e′∈E,e∈E),(23)∑e∈Ei∑m∈Cexem≤γi(i∈V),(24)fi,jq≥0,fj,iq≥0((i,j)∈E,q∈Q),(25)∑k:k≠d(q),(k,i)∈Eifk,iq=∑j:j≠s(q),(i,j)∈Eifi,jq(i≠d(q),i≠s(q),i∈V,q∈Q),(26)∑j:(i,j)∈Eifi,jq≥T(i=s(q),q∈Q),(27)∑j:(j,i)∈Eifj,iq≥T(i=d(q),q∈Q),(28)∑q∈Qfi,jq+∑q∈Qfj,iq≤∑m∈CeBem(e=(i,j),e∈E),
where γi is constant and Bem can be obtained by (18). xem (binary integer) and fi,jq and fj,iq (rational number) are decision variables. The objective function is a linear function; however, (28) is a nonlinear constraint. The optimization problem is in the form of mixed integer nonlinear programming (MINLP) problem and can be solved by LINGO.


## 4.1. Link Assignment

We say that linke is active only if there is a transmission on channel m over link e. We define a 0-1 binary variable xem as follows:(8)xem={1iflinkeisactiveonchannelm,0otherwise.


## 4.2. Interference Constraints

In this paper, we consider both primary and secondary interference constraints. We term the secondary interference constraints as theSINR constraints hereinafter in this paper, since we use the SINR model to model them.In the remaining part of this subsection, we lete=(i,j) denote a link and let e′=(k,h) denote another link. Both links are active and use a same channel m for transmission.


### 4.2.1. Primary Interference Constraints

By using a same channel, each node can either transmit or receive but not both, at a given time. In other words, links that share a common node cannot transmit or receive simultaneously on any channel.For ease of presentation and also for notational convenience,each link is also understood as a set of two nodes; then we define(9)e∩e′{=∅ifi≠kandj≠kandi≠handj≠h,≠∅ifi=korj=kori=horj=h.Clearly, we use the notatione∩e′=∅ to denote that the two links e and e′ do not share a common node, and the notation e∩e′≠∅ to denote that the two links e and e′ share a common node.Thus, the primary interference constraint can be expressed as follows:(10)xem+xe′m≤1(m∈Ce∩Ce′,e′∩e≠∅,e′≠e,e′∈E,e∈E).


### 4.2.2. SINR (i.e., Secondary Interference) Constraints

For the links that donot share a common node but share a common channel, they are applicable to the SINR constraints if the links are active simultaneously. That is, a transmission on a bidirectional link e=(i,j) is successful if and only if the SINR at either node i or node j is not less than the minimum required threshold β. This leads to the following constraint: (11)PGijxem-βP∑e′∈Em′max(Gkj,Ghj,Gki,Ghi)xe′m-βN≥Υ(xem-1)(m∈Ce∩Ce′,e∩e′=∅,e′∈E,e∈E),
where Em′ contains all links that have transmissions concurrent with link e by using channel m. Similar to [13], we introduce a sufficiently large positive number Υ in the constraint (11), where the constraint becomes “redundant” when link e is not active (i.e., xem=0). Notice that we only sum the interference caused by those active links because link e′ will not cause any interference on link e whenever link e′ is not active (i.e., xe'm=0). And also note that when we calculate the interference caused by the active link e′=(k,h), we choose the maximum interference caused from either node k or node h to either node i or node j (due to bidirectional link).


## 4.2.1. Primary Interference Constraints

By using a same channel, each node can either transmit or receive but not both, at a given time. In other words, links that share a common node cannot transmit or receive simultaneously on any channel.For ease of presentation and also for notational convenience,each link is also understood as a set of two nodes; then we define(9)e∩e′{=∅ifi≠kandj≠kandi≠handj≠h,≠∅ifi=korj=kori=horj=h.Clearly, we use the notatione∩e′=∅ to denote that the two links e and e′ do not share a common node, and the notation e∩e′≠∅ to denote that the two links e and e′ share a common node.Thus, the primary interference constraint can be expressed as follows:(10)xem+xe′m≤1(m∈Ce∩Ce′,e′∩e≠∅,e′≠e,e′∈E,e∈E).


## 4.2.2. SINR (i.e., Secondary Interference) Constraints

For the links that donot share a common node but share a common channel, they are applicable to the SINR constraints if the links are active simultaneously. That is, a transmission on a bidirectional link e=(i,j) is successful if and only if the SINR at either node i or node j is not less than the minimum required threshold β. This leads to the following constraint: (11)PGijxem-βP∑e′∈Em′max(Gkj,Ghj,Gki,Ghi)xe′m-βN≥Υ(xem-1)(m∈Ce∩Ce′,e∩e′=∅,e′∈E,e∈E),
where Em′ contains all links that have transmissions concurrent with link e by using channel m. Similar to [13], we introduce a sufficiently large positive number Υ in the constraint (11), where the constraint becomes “redundant” when link e is not active (i.e., xem=0). Notice that we only sum the interference caused by those active links because link e′ will not cause any interference on link e whenever link e′ is not active (i.e., xe'm=0). And also note that when we calculate the interference caused by the active link e′=(k,h), we choose the maximum interference caused from either node k or node h to either node i or node j (due to bidirectional link).


## 4.3. Node-Radio Constraint

A node can establish multiple links with its neighboring nodes if it can tune each of its radio interface to a different channel. However, the number of established links at each node is constrained by the number of its radio interfaces. This leads to the following constraint:(12)∑e∈Ei∑m∈Cexem≤γi(i∈V).


## 4.4. Multipath Routing Constraints

We consider multiple traffic flows in the network. We term the traffic flow for each source-destination pair as a communication session and useq (q=1,2,…,Q) to index each session. Let s(q) and d(q) represent the source node and destination node for session q. Because the links are bidirectional, the traffic flow on each link can be in either direction. Thus, for any link e=(i,j), we let fi,jq (and fj,iq) denote the traffic flow traveling from i to j (and from j to i) for the session q, where (i,j)∈E,i≠j. For each traffic flow, we allow multi-path routing.Our definition of the maximum throughput ismax-min flow rate [25]. That is, our target is to maximize the minimum end-to-end flow throughput that can be achieved in the network. Therefore, the multi-path routing constraints are listed as follows: (13)fi,jq≥0,fj,iq≥0((i,j)∈E,q∈Q),(14)∑k:k≠d(q),(k,i)∈Eifk,iq=∑j:j≠s(q),(i,j)∈Eifi,jq(i≠d(q),i≠s(q),i∈V,q∈Q),(15)∑j:(i,j)∈Eifi,jq≥T(i=s(q),q∈Q),(16)∑j:(j,i)∈Eifj,iq≥T(i=d(q),q∈Q),(17)∑q∈Qfi,jq+∑q∈Qfj,iq≤∑m∈CeBem(e=(i,j),e∈E),
where T is the minimum end-to-end throughput for every session.The constraint (13) restricts the amount of flow on each link to be nonnegative. The constraint (14) states that at each node, except the source node and destination node, the amount of incoming flow is equal to the amount of outgoing flow. The constraint (15) represents that the minimum outgoing flow from each source node is at least T. The constraint (16) states that the minimum incoming flow to the destination node is at least T. The constraint (17) indicates that the sum of the flows over all sessions traversing a link cannot exceed the link capacity.To calculate the link capacity, we letW denote the bandwidth of each channel, and let Bem denote the capacity of link e by using channel m. Assuming Gaussian noise and interference, we have (18)Bem=Wlog2(1+PGjixemP·∑e′∈Em′max(Gkj,Ghj,Gki,Ghi)xe′m+N)(m∈Ce∩Ce′,e∩e′=∅,e′∈E,e∈E).


## 4.5. Problem Formulation

We aim to maximize the minimum end-to-end throughput, and this optimization problem can be formulated as(19)maxT(20)Subjectto:xem=0,1(m∈Ce,e∈E),(21)xem+xe′m≤1(m∈Ce∩Ce′,e′∩e≠∅,e′≠e,e′∈E,e∈E),(22)PGijxem-βP∑e′∈Em′max(Gkj,Ghj,Gki,Ghi)xe'm-βN≥Υ(xem-1)(m∈Ce∩Ce′,e∩e′=∅,e′∈E,e∈E),(23)∑e∈Ei∑m∈Cexem≤γi(i∈V),(24)fi,jq≥0,fj,iq≥0((i,j)∈E,q∈Q),(25)∑k:k≠d(q),(k,i)∈Eifk,iq=∑j:j≠s(q),(i,j)∈Eifi,jq(i≠d(q),i≠s(q),i∈V,q∈Q),(26)∑j:(i,j)∈Eifi,jq≥T(i=s(q),q∈Q),(27)∑j:(j,i)∈Eifj,iq≥T(i=d(q),q∈Q),(28)∑q∈Qfi,jq+∑q∈Qfj,iq≤∑m∈CeBem(e=(i,j),e∈E),
where γi is constant and Bem can be obtained by (18). xem (binary integer) and fi,jq and fj,iq (rational number) are decision variables. The objective function is a linear function; however, (28) is a nonlinear constraint. The optimization problem is in the form of mixed integer nonlinear programming (MINLP) problem and can be solved by LINGO.


## 5. Finding the Optimal Solution by Heuristic

We are interested in finding the optimal solution under which the minimum end-to-end flow throughput is maximized. However, the original problem is in the form of MINLP since the constraint (28) is nonlinear due to the logarithm function. But if we investigate the formulation more carefully, we find that the complexity of the MINLP problem formulation does not lie in the nonlinear logarithm function in constraint (28). Instead, the complexity comes from the existence of the binary variable xem. The reason is that as long as the values of xem are determined (i.e., the set of active links and the channel assignment on each active link are determined), then this MINLP reduces to an LP, which can be solved in polynomial time. To this end, we develop a heuristic method by solving a relaxation of the original problem, followed by rounding and simple local optimization [26].


### 5.1. Relaxation

We start by relaxing the MINLP problem to the following format.(29)maxT(30)Subjectto:0≤xem≤1(m∈Ce,e∈E)constraints(21)–(28).That is, we allow the variablesxem to take values between 0 and 1. The relaxed problem can be solved in polynomial time. By solving the relaxed problem, we obtain an upper bound of the optimal value of the original problem, and we let X* denote the relaxed solution that produces the upper bound.


### 5.2. Getting Independent Sets

In order to determine the set of active links and form a conflict-free topology, we need to obtain the independent sets (i.e., the set of links that can be simultaneously active on a channel). The reason is that we can significantly speed up the search process by combining the independent sets together with the rounding and local optimization (introduced below).To obtain the independent sets, Karnik et al. [25] proposed a smart enumerative technique. In this paper, we extend this technique into a more general case from the following two aspects. (1) In [25], all nodes are assumed to transmit at a single channel. But in our formulation we consider a more realistic scenario where each node (i.e., secondary user) is able to access a set of available channels, and especially, the set of available channels is different from node to node. (2) In [25] the links are unidirectional, but in our formulation the bidirectional links are considered.For this technique, similar to [25] we make the following additional assumptions. (Interested readers are advised to refer [25] for details on why the above three assumptions are reasonable.)(A1)
The propagation gains are modeled by isotropic path loss. That is, the propagation gain from nodei to node j is
(31)Gij=(d0dij)η,
where d0 is the far-field crossover distance and η denotes the path loss exponent.(A2)
The minimum distance for any pair of nodes isdmin.(A3)
The nodes are located in a square sizeL×L area.Theorem 1.
Under the assumptions (A1)–(A3), the number of simultaneous transmissions on a same channel (i.e., the size of maximum independent sets on a channel) is upper bounded by 2L2/π(dminβ1/η)2.Proof.
Please see the appendix.Section6 will show the extent of complexity reduction by using this technique together with rounding and local optimization.


### 5.3. Rounding

The next step is to round the relaxed problem solutionX* to a valid binary integer solution X̂. To create X̂, we can simply round the one (say xem) with the largest value to 1. According to the independent set, with xem=1 we can immediately decide some variables which share the same channel m with the link e to be 1 or 0. After fixing some decision variables to 1 or 0 in the first iteration, we update a new relaxed LP for the second iteration. We can solve this new LP, then again round the one with the largest value to 1, and set some additional variables to 0 accordingly. The iteration continues and eventually we can determine all {xem} to either 0 or 1.Upon fixing all thexem values, the original MINLP reduces to an LP problem, which can be solved in polynomial time. It is worth emphasizing that, unlike the solutions obtained by relaxation, the final solution obtained here is a feasible solution since all xem values are binary instead of rational numbers.


### 5.4. Local Optimization

Further improvement can be obtained by a local optimization method, starting fromX̂. Suppose that for channel m there are nm independent sets, and we use 1,2,…,nm to index each independent set. Since, in the initial solution X̂, one of nm independent sets is active on channel m, then we use v (1≤v≤nm) to index the active independent set. Then for channel m, we observe its independent sets and cycle through k=1,2,…,(nm-1) while k≠v, and at the kth step replacing the kth independent set as 1. If this change leads to an improvement for the objective function, we accept the change and continue. Otherwise we go on to the next independent set of channel m. We continue until we have tried all the independent sets for channel m. The same process repeats for all the channels. Numerical experiments show that this local optimization method can lead to significant improvement on the objective function.


## 5.1. Relaxation

We start by relaxing the MINLP problem to the following format.(29)maxT(30)Subjectto:0≤xem≤1(m∈Ce,e∈E)constraints(21)–(28).That is, we allow the variablesxem to take values between 0 and 1. The relaxed problem can be solved in polynomial time. By solving the relaxed problem, we obtain an upper bound of the optimal value of the original problem, and we let X* denote the relaxed solution that produces the upper bound.


## 5.2. Getting Independent Sets

In order to determine the set of active links and form a conflict-free topology, we need to obtain the independent sets (i.e., the set of links that can be simultaneously active on a channel). The reason is that we can significantly speed up the search process by combining the independent sets together with the rounding and local optimization (introduced below).To obtain the independent sets, Karnik et al. [25] proposed a smart enumerative technique. In this paper, we extend this technique into a more general case from the following two aspects. (1) In [25], all nodes are assumed to transmit at a single channel. But in our formulation we consider a more realistic scenario where each node (i.e., secondary user) is able to access a set of available channels, and especially, the set of available channels is different from node to node. (2) In [25] the links are unidirectional, but in our formulation the bidirectional links are considered.For this technique, similar to [25] we make the following additional assumptions. (Interested readers are advised to refer [25] for details on why the above three assumptions are reasonable.)(A1)
The propagation gains are modeled by isotropic path loss. That is, the propagation gain from nodei to node j is
(31)Gij=(d0dij)η,
where d0 is the far-field crossover distance and η denotes the path loss exponent.(A2)
The minimum distance for any pair of nodes isdmin.(A3)
The nodes are located in a square sizeL×L area.Theorem 1.
Under the assumptions (A1)–(A3), the number of simultaneous transmissions on a same channel (i.e., the size of maximum independent sets on a channel) is upper bounded by 2L2/π(dminβ1/η)2.Proof.
Please see the appendix.Section6 will show the extent of complexity reduction by using this technique together with rounding and local optimization.


## 5.3. Rounding

The next step is to round the relaxed problem solutionX* to a valid binary integer solution X̂. To create X̂, we can simply round the one (say xem) with the largest value to 1. According to the independent set, with xem=1 we can immediately decide some variables which share the same channel m with the link e to be 1 or 0. After fixing some decision variables to 1 or 0 in the first iteration, we update a new relaxed LP for the second iteration. We can solve this new LP, then again round the one with the largest value to 1, and set some additional variables to 0 accordingly. The iteration continues and eventually we can determine all {xem} to either 0 or 1.Upon fixing all thexem values, the original MINLP reduces to an LP problem, which can be solved in polynomial time. It is worth emphasizing that, unlike the solutions obtained by relaxation, the final solution obtained here is a feasible solution since all xem values are binary instead of rational numbers.


## 5.4. Local Optimization

Further improvement can be obtained by a local optimization method, starting fromX̂. Suppose that for channel m there are nm independent sets, and we use 1,2,…,nm to index each independent set. Since, in the initial solution X̂, one of nm independent sets is active on channel m, then we use v (1≤v≤nm) to index the active independent set. Then for channel m, we observe its independent sets and cycle through k=1,2,…,(nm-1) while k≠v, and at the kth step replacing the kth independent set as 1. If this change leads to an improvement for the objective function, we accept the change and continue. Otherwise we go on to the next independent set of channel m. We continue until we have tried all the independent sets for channel m. The same process repeats for all the channels. Numerical experiments show that this local optimization method can lead to significant improvement on the objective function.


## 6. Simulation Results

In this section, we present simulation results for our heuristic method and compare it with the upper bound and the global optimum. The upper bound is obtained by solving a relaxation of the original problem, while the global optimum is obtained by LINGO which is a mathematical software package. The default settings for the simulations are as follows. The noise power at every receiver is equal to-100 dBm. η and d0 are taken to be 4 and 0.1 m, respectively. The minimum threshold (β) is set to 2.3 dB.We consider two scenarios: one is regular topology and the other is random topology. We make no claims that these topologies are representative of typical cognitive radio networks. The reason that we have chosen these two simple topologies is to facilitate detailed discussion of the results and for the illustration purpose. For the propagation model, we adopt the isotropic path loss shown in (31). However, we stress that the validity of the conclusions drawn in the following holds for any scenario and also when more complicated propagation models are used to determine Gij parameters.


### 6.1. Performance in Regular Topology

We first look at the performance of the proposed approach in the regular topology, as illustrated in Figure4(a). A total number of n=9 nodes are placed in a 3×3 grid, and the deployment area is a square size of 80×80. The unit grid separation (i.e., distance between adjacent nodes along the grid-side) is 20 m. All nodes use a common transmit power of 3 mW, which results in a transmission range of 23.4 m. The transmission range is greater than the unit grid separation but is less than the unit grid diagonal (i.e., distance between adjacent nodes along the diagonal). This results in a simple topology where all nodes can only communicate with their physical one-hop neighbors on the grid. Figure 4(b) shows the connection graph. There are M=6 channels that can be used for the entire network. Every node has 3 radio interfaces (γi). The set of available channels at each node is randomly generated; see Table 2. Note that the set of available channels is different from node to node.Table 2
Set of available channels at each node (i.e.,Ci) for regular topology.
Node indexLocationAvailable channels1(20, 20)2, 3, 42(20, 40)1, 2, 4, 63(20, 60)1, 2, 5,4(40, 20)3, 4, 5, 65(40, 40)1, 3, 4, 66(40, 60)1, 3, 57(60, 20)1, 2, 5, 68(60, 40)2, 4, 59(60, 60)1, 2, 3, 6Regular topology.
(a)
Node location(b)
Connectivity Graph


#### 6.1.1. Complexity Reduction

For this scenario, there are 12 potential links and 24 binary variables (i.e.,{xem}). By using the enumerative technique, we obtain 22 independent sets and the size of the maximum independent set is 2. The exhaustive search space to determine the binary variable is 224; however, combining the independent sets together with the rounding and local optimization, the search space is significantly reduced from 224 to 1800.


#### 6.1.2. Throughput

Regarding the traffic flow, we consider|Q|= 1, 2, or 3 active sessions and run 3 experiments, respectively. In each experiment, the source node and destination node for each session are randomly generated. Figure 5(a) shows the results of the throughput obtained by our heuristic, upper bound and global optimum. Since the regular topology is simple, the heuristic method includes rounding technique only. It is observed that such heuristic results (obtained by rounding technique only) are equal to the global optimum, therefore no need to carry out local optimization. It is also found that there are gaps between the heuristic results and the relaxation bound.Comparison between heuristic, upper bound and global optimum for regular topology.
(a)
Throughput(b)
Optimality ratioFor comparison purpose Figure5(b) shows the results of the optimality ratio (which is defined as the normalized throughput over the global optimum) obtained by our rounding technique. It is found that the optimality ratio obtained by rounding is 1, while the optimality ratio of the relaxation bound is within (1,1.6). Simulation results show that the rounding technique performs very well in this scenario.


### 6.2. Performance in Random Topology

We next relax the regularity of node placement and look at the performance of the proposed approach in the random topology. As Figure6(a) shows, we assume that n=10 nodes are uniformly distributed in a square size of 40×40 area. All nodes use a common transmit power of 4 mW, which results in a transmission range of 25.1 m. Figure 6(b) shows the connection graph. There are M=8 channels that can be used for the entire network. Every node has 4 radio interfaces (γi). The set of available channels at each node is shown in Table 3. Again, the set of available channels is different from node to node.Table 3
Set of available channels at each node (i.e.,Ci) for random topology.
Node indexLocationAvailable channels1(29.0, 28.8)1, 2, 6, 72(23.2, 9.9)3, 4, 5, 73(12.4, 13.7)5, 7, 84(4.4, 38.8)3, 4, 65(15.3, 2.9)1, 2, 3, 4, 7, 86(12.8, 30.5)2, 57(38.0, 10.8)1, 4, 68(1.6, 6.1)3, 4, 59(24.3, 37.7)2, 4, 5, 810(39.1, 34.1)1, 3, 6, 8Random topology.
(a)
Node location(b)
Connectivity graph


#### 6.2.1. Complexity Reduction

For this scenario, there are 21 potential links and 32 binary variables (i.e.,{xem}). By using the enumerative technique, we get 29 independent sets and the size of the maximum independent set is 2. The exhaustive search space to determine the binary variable is 232; however, combining the independent sets together with the rounding and local optimization, the search space is significantly reduced from 232 to 13500.


#### 6.2.2. Throughput

Regarding the traffic flow, we consider|Q|= 1, 2, 3, 4, or 5 active sessions and run 15 experiments, respectively. In each experiment, the source node and destination node for each session are randomly generated. Different from the results obtained in the regular topology, in this random topology we show not only the heuristic results obtained by rounding technique but also the heuristic solutions obtained by rounding and local optimization. Table 4 shows the results. It is observed that there are some minor gaps between global optimum and the heuristic results obtained by rounding technique. However, by further using local optimization method, we find that the heuristic results are very close to the the global optimum. This observation demonstrates that the local optimization can lead to significant improvement on the objective function. Also note that there are some moderate gaps between the global optimum and the bounds obtained by relaxation.Table 4
Throughput comparison for random topology.
Experiment indexGlobal optimalRelaxation boundRoundingRounding& local optimization1404.67725.38260.50404.672508.28860.37504.81504.813534.48860.37260.50534.484183.67183.67154.17183.675254.14416.66144.17254.146247.78422.54123.89247.787154.17183.67117.63154.178152.76183.67101.84152.769222.72286.79123.89222.7210177.44286.79123.89177.4411140.07183.67126.48140.0712130.25183.67123.89130.2513123.89215.09117.63117.6314148.48183.6794.86148.4815111.34167.47104.54111.34For comparison purpose Table5 shows the optimality ratio obtained by our heuristic and relaxation. It is observed that the heuristic results obtained by rounding and local optimization are very close to 1, while the heuristic results obtained by only rounding are within (0.48,1.0) and the ratio of the relaxation is within (1,1.8). The simulation results show that the combination of rounding and local optimization performs very well in this scenario.Table 5
Optimality ratio comparison for random topology.
Experiment indexRelaxation boundRoundingRounding& local optimization11.790.641.0021.690.990.9931.610.491.0041.000.841.0051.640.571.0061.710.501.0071.190.761.0081.200.671.0091.290.561.00101.620.701.00111.310.901.00121.410.951.00131.740.950.95141.240.641.00151.500.941.00


#### 6.2.3. Spectrum Sharing and Routing

For illustration purpose, we show the results of spectrum sharing and routing when there are 5 communication sessions. The source node and destination node for each communication session are randomly generated; see Table6.Table 6
Rate requirements of 5 sessions for random topology.
Source nodeDestination node81074593126By solving the MINLP problem by heuristic, we obtain that the optimal achievable throughput for each traffic flow is 111.3 (which is the 15th experiment shown in Figure7). Figure 7(a) illustrates the optimal spectrum sharing. It is noticed that there are 10 active links in total, and channels 4 and 8 are reused. The nodes form themselves as an ad hoc network and all links can be active simultaneously (i.e., the topology is conflict-free). Figures 7(b)–7(f) illustrate the routing path(s) for each traffic flow. Figure 7(b) shows that the traffic flow generated by node 8 first travels to node 5, and then the traffic is split into 2 paths: one is 5→3→6→9→10 and the other path is 5→2→1→10. Figure 7(c) indicates that the traffic from node 7 to node 4 is via a single path, that is, 7→1→10→9→4. Similarly, as shown in Figures 7(d) and 7(e), the routing path for traffic flow from node 5 to node 9 is 5→3→6→9, while the traffic flow from node 3 to node 1 is via the path 3→5→2→1. Finally, the traffic flow generated from node 2 travels through 2 paths, one is through 2→5→3→6, and the other is via 2→1→10→9→6.Spectrum sharing and routing for random topology.
(a)
Spectrum sharing(b)
Routing flow 1(c)
Routing flow 2(d)
Routing flow 3(e)
Routing flow 4(f)
Routing flow 5Figure 8
SINR model of interference.


## 6.1. Performance in Regular Topology

We first look at the performance of the proposed approach in the regular topology, as illustrated in Figure4(a). A total number of n=9 nodes are placed in a 3×3 grid, and the deployment area is a square size of 80×80. The unit grid separation (i.e., distance between adjacent nodes along the grid-side) is 20 m. All nodes use a common transmit power of 3 mW, which results in a transmission range of 23.4 m. The transmission range is greater than the unit grid separation but is less than the unit grid diagonal (i.e., distance between adjacent nodes along the diagonal). This results in a simple topology where all nodes can only communicate with their physical one-hop neighbors on the grid. Figure 4(b) shows the connection graph. There are M=6 channels that can be used for the entire network. Every node has 3 radio interfaces (γi). The set of available channels at each node is randomly generated; see Table 2. Note that the set of available channels is different from node to node.Table 2
Set of available channels at each node (i.e.,Ci) for regular topology.
Node indexLocationAvailable channels1(20, 20)2, 3, 42(20, 40)1, 2, 4, 63(20, 60)1, 2, 5,4(40, 20)3, 4, 5, 65(40, 40)1, 3, 4, 66(40, 60)1, 3, 57(60, 20)1, 2, 5, 68(60, 40)2, 4, 59(60, 60)1, 2, 3, 6Regular topology.
(a)
Node location(b)
Connectivity Graph


### 6.1.1. Complexity Reduction

For this scenario, there are 12 potential links and 24 binary variables (i.e.,{xem}). By using the enumerative technique, we obtain 22 independent sets and the size of the maximum independent set is 2. The exhaustive search space to determine the binary variable is 224; however, combining the independent sets together with the rounding and local optimization, the search space is significantly reduced from 224 to 1800.


### 6.1.2. Throughput

Regarding the traffic flow, we consider|Q|= 1, 2, or 3 active sessions and run 3 experiments, respectively. In each experiment, the source node and destination node for each session are randomly generated. Figure 5(a) shows the results of the throughput obtained by our heuristic, upper bound and global optimum. Since the regular topology is simple, the heuristic method includes rounding technique only. It is observed that such heuristic results (obtained by rounding technique only) are equal to the global optimum, therefore no need to carry out local optimization. It is also found that there are gaps between the heuristic results and the relaxation bound.Comparison between heuristic, upper bound and global optimum for regular topology.
(a)
Throughput(b)
Optimality ratioFor comparison purpose Figure5(b) shows the results of the optimality ratio (which is defined as the normalized throughput over the global optimum) obtained by our rounding technique. It is found that the optimality ratio obtained by rounding is 1, while the optimality ratio of the relaxation bound is within (1,1.6). Simulation results show that the rounding technique performs very well in this scenario.


## 6.1.1. Complexity Reduction

For this scenario, there are 12 potential links and 24 binary variables (i.e.,{xem}). By using the enumerative technique, we obtain 22 independent sets and the size of the maximum independent set is 2. The exhaustive search space to determine the binary variable is 224; however, combining the independent sets together with the rounding and local optimization, the search space is significantly reduced from 224 to 1800.


## 6.1.2. Throughput

Regarding the traffic flow, we consider|Q|= 1, 2, or 3 active sessions and run 3 experiments, respectively. In each experiment, the source node and destination node for each session are randomly generated. Figure 5(a) shows the results of the throughput obtained by our heuristic, upper bound and global optimum. Since the regular topology is simple, the heuristic method includes rounding technique only. It is observed that such heuristic results (obtained by rounding technique only) are equal to the global optimum, therefore no need to carry out local optimization. It is also found that there are gaps between the heuristic results and the relaxation bound.Comparison between heuristic, upper bound and global optimum for regular topology.
(a)
Throughput(b)
Optimality ratioFor comparison purpose Figure5(b) shows the results of the optimality ratio (which is defined as the normalized throughput over the global optimum) obtained by our rounding technique. It is found that the optimality ratio obtained by rounding is 1, while the optimality ratio of the relaxation bound is within (1,1.6). Simulation results show that the rounding technique performs very well in this scenario.


## 6.2. Performance in Random Topology

We next relax the regularity of node placement and look at the performance of the proposed approach in the random topology. As Figure6(a) shows, we assume that n=10 nodes are uniformly distributed in a square size of 40×40 area. All nodes use a common transmit power of 4 mW, which results in a transmission range of 25.1 m. Figure 6(b) shows the connection graph. There are M=8 channels that can be used for the entire network. Every node has 4 radio interfaces (γi). The set of available channels at each node is shown in Table 3. Again, the set of available channels is different from node to node.Table 3
Set of available channels at each node (i.e.,Ci) for random topology.
Node indexLocationAvailable channels1(29.0, 28.8)1, 2, 6, 72(23.2, 9.9)3, 4, 5, 73(12.4, 13.7)5, 7, 84(4.4, 38.8)3, 4, 65(15.3, 2.9)1, 2, 3, 4, 7, 86(12.8, 30.5)2, 57(38.0, 10.8)1, 4, 68(1.6, 6.1)3, 4, 59(24.3, 37.7)2, 4, 5, 810(39.1, 34.1)1, 3, 6, 8Random topology.
(a)
Node location(b)
Connectivity graph


### 6.2.1. Complexity Reduction

For this scenario, there are 21 potential links and 32 binary variables (i.e.,{xem}). By using the enumerative technique, we get 29 independent sets and the size of the maximum independent set is 2. The exhaustive search space to determine the binary variable is 232; however, combining the independent sets together with the rounding and local optimization, the search space is significantly reduced from 232 to 13500.


### 6.2.2. Throughput

Regarding the traffic flow, we consider|Q|= 1, 2, 3, 4, or 5 active sessions and run 15 experiments, respectively. In each experiment, the source node and destination node for each session are randomly generated. Different from the results obtained in the regular topology, in this random topology we show not only the heuristic results obtained by rounding technique but also the heuristic solutions obtained by rounding and local optimization. Table 4 shows the results. It is observed that there are some minor gaps between global optimum and the heuristic results obtained by rounding technique. However, by further using local optimization method, we find that the heuristic results are very close to the the global optimum. This observation demonstrates that the local optimization can lead to significant improvement on the objective function. Also note that there are some moderate gaps between the global optimum and the bounds obtained by relaxation.Table 4
Throughput comparison for random topology.
Experiment indexGlobal optimalRelaxation boundRoundingRounding& local optimization1404.67725.38260.50404.672508.28860.37504.81504.813534.48860.37260.50534.484183.67183.67154.17183.675254.14416.66144.17254.146247.78422.54123.89247.787154.17183.67117.63154.178152.76183.67101.84152.769222.72286.79123.89222.7210177.44286.79123.89177.4411140.07183.67126.48140.0712130.25183.67123.89130.2513123.89215.09117.63117.6314148.48183.6794.86148.4815111.34167.47104.54111.34For comparison purpose Table5 shows the optimality ratio obtained by our heuristic and relaxation. It is observed that the heuristic results obtained by rounding and local optimization are very close to 1, while the heuristic results obtained by only rounding are within (0.48,1.0) and the ratio of the relaxation is within (1,1.8). The simulation results show that the combination of rounding and local optimization performs very well in this scenario.Table 5
Optimality ratio comparison for random topology.
Experiment indexRelaxation boundRoundingRounding& local optimization11.790.641.0021.690.990.9931.610.491.0041.000.841.0051.640.571.0061.710.501.0071.190.761.0081.200.671.0091.290.561.00101.620.701.00111.310.901.00121.410.951.00131.740.950.95141.240.641.00151.500.941.00


### 6.2.3. Spectrum Sharing and Routing

For illustration purpose, we show the results of spectrum sharing and routing when there are 5 communication sessions. The source node and destination node for each communication session are randomly generated; see Table6.Table 6
Rate requirements of 5 sessions for random topology.
Source nodeDestination node81074593126By solving the MINLP problem by heuristic, we obtain that the optimal achievable throughput for each traffic flow is 111.3 (which is the 15th experiment shown in Figure7). Figure 7(a) illustrates the optimal spectrum sharing. It is noticed that there are 10 active links in total, and channels 4 and 8 are reused. The nodes form themselves as an ad hoc network and all links can be active simultaneously (i.e., the topology is conflict-free). Figures 7(b)–7(f) illustrate the routing path(s) for each traffic flow. Figure 7(b) shows that the traffic flow generated by node 8 first travels to node 5, and then the traffic is split into 2 paths: one is 5→3→6→9→10 and the other path is 5→2→1→10. Figure 7(c) indicates that the traffic from node 7 to node 4 is via a single path, that is, 7→1→10→9→4. Similarly, as shown in Figures 7(d) and 7(e), the routing path for traffic flow from node 5 to node 9 is 5→3→6→9, while the traffic flow from node 3 to node 1 is via the path 3→5→2→1. Finally, the traffic flow generated from node 2 travels through 2 paths, one is through 2→5→3→6, and the other is via 2→1→10→9→6.Spectrum sharing and routing for random topology.
(a)
Spectrum sharing(b)
Routing flow 1(c)
Routing flow 2(d)
Routing flow 3(e)
Routing flow 4(f)
Routing flow 5Figure 8
SINR model of interference.


## 6.2.1. Complexity Reduction

For this scenario, there are 21 potential links and 32 binary variables (i.e.,{xem}). By using the enumerative technique, we get 29 independent sets and the size of the maximum independent set is 2. The exhaustive search space to determine the binary variable is 232; however, combining the independent sets together with the rounding and local optimization, the search space is significantly reduced from 232 to 13500.


## 6.2.2. Throughput

Regarding the traffic flow, we consider|Q|= 1, 2, 3, 4, or 5 active sessions and run 15 experiments, respectively. In each experiment, the source node and destination node for each session are randomly generated. Different from the results obtained in the regular topology, in this random topology we show not only the heuristic results obtained by rounding technique but also the heuristic solutions obtained by rounding and local optimization. Table 4 shows the results. It is observed that there are some minor gaps between global optimum and the heuristic results obtained by rounding technique. However, by further using local optimization method, we find that the heuristic results are very close to the the global optimum. This observation demonstrates that the local optimization can lead to significant improvement on the objective function. Also note that there are some moderate gaps between the global optimum and the bounds obtained by relaxation.Table 4
Throughput comparison for random topology.
Experiment indexGlobal optimalRelaxation boundRoundingRounding& local optimization1404.67725.38260.50404.672508.28860.37504.81504.813534.48860.37260.50534.484183.67183.67154.17183.675254.14416.66144.17254.146247.78422.54123.89247.787154.17183.67117.63154.178152.76183.67101.84152.769222.72286.79123.89222.7210177.44286.79123.89177.4411140.07183.67126.48140.0712130.25183.67123.89130.2513123.89215.09117.63117.6314148.48183.6794.86148.4815111.34167.47104.54111.34For comparison purpose Table5 shows the optimality ratio obtained by our heuristic and relaxation. It is observed that the heuristic results obtained by rounding and local optimization are very close to 1, while the heuristic results obtained by only rounding are within (0.48,1.0) and the ratio of the relaxation is within (1,1.8). The simulation results show that the combination of rounding and local optimization performs very well in this scenario.Table 5
Optimality ratio comparison for random topology.
Experiment indexRelaxation boundRoundingRounding& local optimization11.790.641.0021.690.990.9931.610.491.0041.000.841.0051.640.571.0061.710.501.0071.190.761.0081.200.671.0091.290.561.00101.620.701.00111.310.901.00121.410.951.00131.740.950.95141.240.641.00151.500.941.00


## 6.2.3. Spectrum Sharing and Routing

For illustration purpose, we show the results of spectrum sharing and routing when there are 5 communication sessions. The source node and destination node for each communication session are randomly generated; see Table6.Table 6
Rate requirements of 5 sessions for random topology.
Source nodeDestination node81074593126By solving the MINLP problem by heuristic, we obtain that the optimal achievable throughput for each traffic flow is 111.3 (which is the 15th experiment shown in Figure7). Figure 7(a) illustrates the optimal spectrum sharing. It is noticed that there are 10 active links in total, and channels 4 and 8 are reused. The nodes form themselves as an ad hoc network and all links can be active simultaneously (i.e., the topology is conflict-free). Figures 7(b)–7(f) illustrate the routing path(s) for each traffic flow. Figure 7(b) shows that the traffic flow generated by node 8 first travels to node 5, and then the traffic is split into 2 paths: one is 5→3→6→9→10 and the other path is 5→2→1→10. Figure 7(c) indicates that the traffic from node 7 to node 4 is via a single path, that is, 7→1→10→9→4. Similarly, as shown in Figures 7(d) and 7(e), the routing path for traffic flow from node 5 to node 9 is 5→3→6→9, while the traffic flow from node 3 to node 1 is via the path 3→5→2→1. Finally, the traffic flow generated from node 2 travels through 2 paths, one is through 2→5→3→6, and the other is via 2→1→10→9→6.Spectrum sharing and routing for random topology.
(a)
Spectrum sharing(b)
Routing flow 1(c)
Routing flow 2(d)
Routing flow 3(e)
Routing flow 4(f)
Routing flow 5Figure 8
SINR model of interference.


## 7. Conclusion

In this paper, we consider a multihop multi-channel CR network. We present a cross-layer optimization framework by jointly designing the spectrum sharing and routing with the SINR constraints. Distinguished from the previous studies, we adopt a more realistic SINR model to capture the conflict relationships among the links, rather than using the Protocol Model. Our objective is to maximize the minimum end-to-end flow throughput, and our study addresses the following two cross-layer throughput optimization problem. (1) Given a set of secondary users with random but fixed location, and a set of traffic flows, what is the max-min achievable throughput? (2) To achieve the optimum, how to choose the set of active links, how to assign the channels to each active link, and how to route the flows? We answer these questions via a formal mathematical formulation in the forms of mixed integer nonlinear programming (MINLP). Since the MINLP formulation is generally an NP-hard problem, we develop a heuristic method by solving a relaxation of the original problem, followed by rounding and simple local optimization. Simulation results show that the heuristic approach performs very well; that is, the solutions obtained by the heuristic are very close to the global optimum.For the future work, we need to consider how to design a distributed algorithm for a multihop CR network. Since in reality, there may not exist a centralized server, and also, the available channels are highly dynamic, in such situation, how to choose the set of active links and how to allocate channels and route the flows to obtain the max-min achievable throughput is a highly desirable and challenging work.



---

*Source: 985458-2010-07-05.xml*