# Joint Channel Assignment and Power Allocation Based on Maximum Concurrent Multicommodity Flow in Cognitive Radio Networks

Authors: Ahmed Salah; Heba M. Abdel-Atty; Rawya Y. Rizk
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Emerging cognitive radio networking technology potentially provides a promising solution to the spectrum underutilization problem in wireless access. In this paper, a cross-layer routing for secondary multihop is studied in cognitive radio network operating in television white spaces. The framework considers a joint channel, power, and routing assignment under signal to interference noise ratio (SINR) constraints. The problem is formulated as a maximum concurrent multicommodity flow problem. The goal of conducting this research is to develop a new routing protocol for the secondary multihop cognitive radio network. Therefore, the objective of this paper focuses on maximizing a flow rate scaling factor. Moreover, the paper focuses on achieving multipath routing when it is possible under SINR constraints to utilize all possible unused channels efficiently. The numerical results proved the strength of the proposed algorithm in its routing ability under the physical model of SINR, in addition to the ability of using multipath routing if there are available free channels to be used in the cognitive communication paradigm.


---

## Body

## 1. Introduction

The radio spectrum is a finite natural resource that is the primary resource for wireless communication. The growing need for high data rate wireless communications has prompted an excellent development of telecommunication technologies. As a result, a nontraditional paradigm [1] is required to overcome spectrum shortage [2] in order to the swiftly develop wireless services together with the fixed spectrum assignment policy.Classical fixed spectrum allocation is the root cause of ineffective spectrum utilization [3]. For instance, a licensed frequency band can be used only by its licensed user even if it is far inactive by this authorized user. For these reasons, Federal Communications Commission (FCC) conducted spectrum surveys for various licensed primary service providers and confirmed that the spectrum is underutilized.Television white space (TVWS) is a good example of underutilized spectrum. It consists of Ultrahigh Frequency/Very High Frequency (UHF/VHF) that are either freed via the digital switch over process or unused due to local regulations [4]. Therefore, FCC considered that the traditional fixed spectrum assignment policy has to be palliated. Subsequently, wireless users are categorized into two sets relying on if they are licensed to utilize a particular spectrum band “primary users (PUs)” or are unlicensed cognitive radio users “secondary users (SUs)” [5].The main problem of routing in multihop cognitive radio networks aims at the creation and the maintenance of wireless multihop paths among SUs by deciding which relay nodes will be involved in the transmission and the spectrum to be used on each link of the path. Moreover, for interference and power control model it is necessary to assign the appropriate transmission power level for each active link and avoid weak channels. The main objective of this work is to achieve a joint channel assignment and power allocation based on maximum concurrent multicommodity flow problem to ensure fairness among all commodities. Moreover, taking into consideration the physical model of signal to interference noise ratio (SINR) model which is a model of key importance for interference characterization is targeted.This paper examines the impact of SU node transmission power division to a different finite number of levels on the channel capacity scaling factor. It formulates the model as a joint channel assignment and power allocation based on maximum concurrent multicommodity flow (MCMCF) problem to ensure fairness among all commodities. The obtained mathematical model is a nonconvex mixed integer nonlinear program (MINLP), which requires an appropriate solution technique. This problem is mathematically treated with Branch-and-Bound algorithm. The problem is solved under SINR constraints since it is of key importance for interference characterization.The remainder of this paper is organized as follows: Section2 presents the related work. Section 3 presents the system model description and assumptions. Section 4 formulates the mathematical model of the problem. Section 5 presents the results. Finally, Section 6 concludes the paper.


## 2. Related Work

In the last years, joint channel assignment routing in wireless networks has been the subject of many of research works. In [7], a centralized heuristic reconfiguration algorithm is proposed. It reassigns channels to radios and reconfigures flows’ routes with aim of achieving a tradeoff between maximizing the network throughput and minimizing the reconfiguration overhead. However, it cannot offer performance guarantee. Routing mechanisms directly affect nodes energy, in spite of the fact that there are various channel allocation mechanisms in wireless network but exceedingly few effective ones for wireless mesh networks.Channel allocation is considered with improving the routing process in [8]. A heuristic based approach that permits least amount of energy to be assigned to each channel with multiradio networks was applied in this method. It guarantees that the node runs out of power falls below a defined limit. However, it does not guarantee noise interference.In [9], a solution for joint Quality of Services (QoS) multicast routing and channel assignment in multichannel multiradio wireless mesh networks based on genetic algorithm is presented. It requires a decent sized population and a lot of generations before offering good routing results and there is no guarantee of finding global maxima.Joint opportunistic routing and channel assignment in multichannel multiradio cognitive radio networks is examined in [10] for enhancing the aggregate throughput of the SUs. A heuristic algorithm to pick out forwarding candidates and allocate channels was presented. A protocol interference model was assumed at which the interference from adjacent nodes is specified by whether or not a node resides within the transmission range of other transmitting nodes. This model does not accurately describe physical layer attributes. Hence, the accuracy of the results is still uncertain.In [11], a mathematical programming model was proposed to estimate the enhancement in throughput that could be accomplished if all the neighboring channels were utilized via partially overlapping channels (POCs). It provided a solution using column generation. In addition, a suboptimal approach is proposed to solve the problem of link selection with joint channel allocation, power control, and flow rate adaptation. However, results showed that the enhancement is found to be almost negligible for more topologies that are realistic.An approach that maximizes the aggregated flow rate of the SUs under the interference power constraint was presented in [12]. The problem is modeled as joint power control and time allocation for wireless powered underlay cognitive radio networks. However, it supposed a synchronized power control where transmission power at network nodes is adaptable. This synchronization in power control cannot provide optimal network performance.In [13], a cross-layer routing algorithm that fulfils the FCC recommendations to operate the cognitive radio in TVWS is proposed. However, the knowledge of the SINR at the interactive PUs is considered to be known via feedback path. This assumption restricts the type of primary network and devices.In [14], the problem of joint routing and channel assignment for several flows generated by source node SUs to a given destination node was addressed. An online learning based scheme was used for solving the problem. The model is based on Markov modulated Poisson process for modeling the PUs traffic at each channel. Aiming to cooperatively minimize the end-to-end delay of source SUs flows, the partial observation of SUs about PUs activity is based on decentralized partially observable Markov decision process for modeling the problem. Despite the fact that learning is capable of enhancing network decisions, applying them can turn against the network in terms of complexity [15]. Thus, caution is needed when choosing the learning technique that develops each type of knowledge and the respective variables that reveal the context where the network operates. Moreover, a challenging issue arises when considering cross-layer and cross-domain configurations, as omitted variables may provoke nonlinear behavior of the latter and instabilities when training the system.In [16], joint cognitive routing and spectrum assignment (JCRSA) algorithm was proposed. The most capacity channel is selected as communication channel on every link. JCRSA calculates the transmission delay on every link for a given packet based on classic Dijkstra algorithm to find the smallest transmission delay route. According to the routing table, the spectrum is assigned on every link. This method inherits the classic Dijkstra algorithm. It does a blind search thereby consuming a lot of time of necessary resources. Another disadvantage is that it cannot handle negative edges. This leads to acyclic graphs and most often cannot obtain the right shortest path.Per-node joint power control, scheduling, and routing in the network were proposed in [6] to optimize network performance. In this work, a formal mathematical model was developed. Moreover, it formulated a cross-layer optimization problem encompassing the three layers (physical, link, and network) and developed a unified solution procedure based on the Branch-and-Bound framework and convex hull relaxation.As presented, there are some efforts in the literature addressing the problem of routing in cognitive radio networks. The most critical issue in the routing in cognitive radio networks is capturing the physical layer characteristics precisely. Most work in literature ignores the precise representation of the interference noise level to avoid complexity associated with this kind of constraints. Adding this constraint converts the problem to nonconvex mixed integer nonlinear problem which requires a nontraditional customized solution approach. In this paper, a tailored solution is presented to solve this problem.


## 3. System Modeling

In this section, the cognitive radio network is described to formulate the mathematical model for the configuration and assumptions. All variables used are defined in Table1.Table 1
Nomenclature.
Symbol Definition i ,  j ,  k ,  h CR-aware nodes indices μ Path loss index n Session index U Set of the total available channels U i j Common available channels between nodesi and j Q Maximum number of power control levels P m a x Maximum transmit power χ i j u , χ k i u Binary variables represent the channelu state between nodes i and j and nodes k and i respectively S i j u Signal to interference ratio on channelu between nodes i and j γ SINR threshold value to avoid weak channels q i j u , q k h u Quantization variable for power control on channelu between nodes i and j and nodes k and h respectively g i j , g k j Path losses between nodesi and j and between nodes k and j, respectively C i j u Channel capacity between nodesi and j on channel u W u Bandwidth of channelu f i j n  , f k i n Flow rate on sessionn passing from nodes i to j and flow between nodes k and i r n Minimum flow rate demand during sessionn λ Session flow rate scaling factor s n , d n Source node and destination node respectively η Thermal Gaussian noise N Number of CR-aware nodes M Number of primary users H Set of available sessions for the entire networkA cross-layer routing for secondary multihop cognitive radio network operating in TVWS that complied with the FFC regulations design is presented. The proposed framework considers a joint channel, power, and routing assignment under SINR physical model. The problem is mathematically formulated as MCMCF problem. The objective of maximizing a flow rate scaling factor is considered. Furthermore, the impact of power levels digitization on that flow rate scaling factor is studied and presented. The obtained mathematical model is a nonconvex mixed integer nonlinear program, which requires an appropriate solution technique. Therefore, a tailored Branch-and-Bound algorithm is used in the proposed solution.


### 3.1. Multihop Network Model

The considered secondary cognitive radio multihop network consists of a set of cognitive radio aware nodesN. All nodes are equipped with similar hardware specifications with half-duplex radio interfaces. There are available channels for nodes i andj where i,j∈N are denoted by ui and uj, respectively. Uij symbolizes the mutual channels between two nodes; i.e., Uij=ui∩uj.


### 3.2. Interference, Power, and Channel Allocation Model

The power control at the transmitting node affects the SINR level at the receiving node. Moreover, SINR level affects the channel scheduling. For instance, if the node is scheduled to receive, then its SINR must exceed threshold valueγ. In the proposed system, scheduling is represented by frequency channel allocation.Channel allocation status of a communication link between nodesi and j at channel u is represented by a binary variable χiju. If the channel u is designated between these nodes,χiju=1, otherwise it is equal to 0. To exclude self-interference from the calculations, a half-duplex communication is assumed.(1)xiju1,iflinki,jisactiveonchannelu0,OtherwiseA nodei is assumed to exploit the channel u for transmission only to a single node j or for reception from only a single transmitting nodek. Suppose that giju represents the propagation path loss between the transmitting node i to the intended receiving node j and dij represents the distance between these nodes. Assume the path loss gain μ=3 [17, 18].Regarding power control representation, a power ranging variable is assumed asqiju∈0,1,2,…,Q that allows a transmitting node to transmit via various finite number of power levels; i.e., transmission power levels can be 0,Pmax/Q,2Pmax/Q,3Pmax/Q,…,Pmax. If there is no active link,q is set to 0. Subsequently, it can be expressed as(2)qiju∈1,Q,ifχiju=10,OtherwiseIn case of concurrent transmission, a nodek transmitting to node h interferes in the transmission between nodes i and j on the same channel as shown in Figure 1. Therefore, SINR can be expressed as follows: (3)Siju=gijuqijuQηW/Pmax+∑k≠iu∈uk∑h≠ku∈uLgkjuqkhuwhere qkhu represents the path loss between the interfering node k and its associated receiving node h on the frequency band u,qiju represents the power level between node i and node j on channel u, and giju represent the path loss gain between node i and node j on channel u. To ensure successful reception, the link is considered active only if SINR is greater than a predefined threshold value γ such as(4)Siju≥γ⟺χiju=1Figure 1
Interfering CR-nodes path loss gain.


### 3.3. Routing and Flow Modeling

It is supposed that the entire network has a set of active sessionsH. The nth session source and destination are denoted by snand dn, respectively, where n∈H. rn is defined as the minimum flow rate requirement for session n. The problem is formulated as an optimization problem of MCMCF problem. This can be achieved by representing the flow maximization variant λ which is a scaling factor for the flow rate rn. A flow is a nonnegative real value that must not exceed the channel capacity and is constrained by flow conservation law. Link capacity between node iand nodej can be expressed as(5)Ciju=Wulog2⁡1+SijuTherefore, it is guaranteed that the amount of traffic flowing between nodei and node j associated with session n must not exceed the link capacity.(6)∑i≠dh,j≠snUij≠∅fijn≤∑u∈Uijχiju.CijuThe flow conservation law states that the input flow to a certain node equals the output of this node. This constraint is applied for all intermediate nodes between source and destination. Therefore, the flow conservation constraints can be expressed as follows.For intermediate node,(7)∑j≠i,snUij≠∅fijn=∑k≠i,dnUki≠∅fkinFor the source node,(8)∑j≠i,i=snUij≠∅fijn=λ.rnFor the destination node,(9)∑k≠i,i=dnUki≠∅fkin=λ.rn


## 3.1. Multihop Network Model

The considered secondary cognitive radio multihop network consists of a set of cognitive radio aware nodesN. All nodes are equipped with similar hardware specifications with half-duplex radio interfaces. There are available channels for nodes i andj where i,j∈N are denoted by ui and uj, respectively. Uij symbolizes the mutual channels between two nodes; i.e., Uij=ui∩uj.


## 3.2. Interference, Power, and Channel Allocation Model

The power control at the transmitting node affects the SINR level at the receiving node. Moreover, SINR level affects the channel scheduling. For instance, if the node is scheduled to receive, then its SINR must exceed threshold valueγ. In the proposed system, scheduling is represented by frequency channel allocation.Channel allocation status of a communication link between nodesi and j at channel u is represented by a binary variable χiju. If the channel u is designated between these nodes,χiju=1, otherwise it is equal to 0. To exclude self-interference from the calculations, a half-duplex communication is assumed.(1)xiju1,iflinki,jisactiveonchannelu0,OtherwiseA nodei is assumed to exploit the channel u for transmission only to a single node j or for reception from only a single transmitting nodek. Suppose that giju represents the propagation path loss between the transmitting node i to the intended receiving node j and dij represents the distance between these nodes. Assume the path loss gain μ=3 [17, 18].Regarding power control representation, a power ranging variable is assumed asqiju∈0,1,2,…,Q that allows a transmitting node to transmit via various finite number of power levels; i.e., transmission power levels can be 0,Pmax/Q,2Pmax/Q,3Pmax/Q,…,Pmax. If there is no active link,q is set to 0. Subsequently, it can be expressed as(2)qiju∈1,Q,ifχiju=10,OtherwiseIn case of concurrent transmission, a nodek transmitting to node h interferes in the transmission between nodes i and j on the same channel as shown in Figure 1. Therefore, SINR can be expressed as follows: (3)Siju=gijuqijuQηW/Pmax+∑k≠iu∈uk∑h≠ku∈uLgkjuqkhuwhere qkhu represents the path loss between the interfering node k and its associated receiving node h on the frequency band u,qiju represents the power level between node i and node j on channel u, and giju represent the path loss gain between node i and node j on channel u. To ensure successful reception, the link is considered active only if SINR is greater than a predefined threshold value γ such as(4)Siju≥γ⟺χiju=1Figure 1
Interfering CR-nodes path loss gain.


## 3.3. Routing and Flow Modeling

It is supposed that the entire network has a set of active sessionsH. The nth session source and destination are denoted by snand dn, respectively, where n∈H. rn is defined as the minimum flow rate requirement for session n. The problem is formulated as an optimization problem of MCMCF problem. This can be achieved by representing the flow maximization variant λ which is a scaling factor for the flow rate rn. A flow is a nonnegative real value that must not exceed the channel capacity and is constrained by flow conservation law. Link capacity between node iand nodej can be expressed as(5)Ciju=Wulog2⁡1+SijuTherefore, it is guaranteed that the amount of traffic flowing between nodei and node j associated with session n must not exceed the link capacity.(6)∑i≠dh,j≠snUij≠∅fijn≤∑u∈Uijχiju.CijuThe flow conservation law states that the input flow to a certain node equals the output of this node. This constraint is applied for all intermediate nodes between source and destination. Therefore, the flow conservation constraints can be expressed as follows.For intermediate node,(7)∑j≠i,snUij≠∅fijn=∑k≠i,dnUki≠∅fkinFor the source node,(8)∑j≠i,i=snUij≠∅fijn=λ.rnFor the destination node,(9)∑k≠i,i=dnUki≠∅fkin=λ.rn


## 4. Optimization Problem Formulation

The previous section obtained the mathematical model that describes the system, but this program needs some reformulation progress to be suitable for the mathematical treatment. Constraints in (1) and (4) can be combined to produce a simplified constraint on the form qiju≤Qχiju. Equation (3) involves a double summation of two nonlinear terms Siju and qkhu.Therefore, it is better to combine these variables into one nonlinear variable. Assume thatvku=∑h≠ku∈uLqkhu.Thus, (3) can be rewritten in the form of(10)QηWPmaxSiju-gijqiju+∑k≠iu∈ukvkugkjuSiju=0This optimization problem is classified as nonconvex MINLP. From the perspective of the theory of computational complexity [18], this formulation is classified as nondeterministic polynomial time hard (NP-hard). First, MINLP is relaxed to be linear program. Then, another algorithm is applied to obtain the integer values for the integer variables. The essential variables required to be obtained in the solution are χiju,qiju,fijn,λ,vku, and Siju.


### 4.1. Optimization Program Relaxation

The nonlinearity of the problem is due to the product termvkuSiju and the channel capacity equation log2⁡1+Siju. Thus, a reformulation linearization technique [18] will be applied to obtain the program.Regarding the product termvkuSiju, a new variable Aijku is introduced where Aijku=vkuSiju. Then, linear constraints are added. Assume that vku has a minimum value vku|Min and maximum value vku|Max. Similarly, Siju has minimum value Siju|Min and maximum value (Siju)Max. Therefore, linear bounding substitution inequalities can be written in the following form:(11a)vku-vkuMinSiju-SijuMin≥0,(11b)vku-vkuMinSijuMax-Siju≥0,(11c)vkuMax-vkuSiju-SijuMin≥0,(11d)vkuMax-vkuSijuMax-Siju≥0.Then, the product termvkuSiju is replaced by Aijku obtaining that(12a)vkuMinSiju+SijuMinvku-Aijku≤vkuMinSijuMin(12b)vkuMaxSiju+SijuMinvku-Aijku≥vkuMaxSijuMin(12c)vkuMinSiju+SijuMaxvku-Aijku≥vkuMinSijuMax(12d)vkuMaxSiju+SijuMaxvku-Aijku≤vkuMaxSijuMaxOn the other hand, the second termlog2⁡1+Siju can be relaxed by creating a convex envelope for it. A new variable Ciju is introduced where Ciju=ln⁡1+Siju. Using the maximum and the minimum values of variable Siju, a convex envelope can be formed as shown in Figure 2.Figure 2
Formulating the convex envelope.The intersection between tangentsT1 and T3 corresponds to the point Siju=α where it can be calculated by the following expression:(13)α=1+SijuMin1+SijuMaxln⁡1+SijuMax-ln⁡1+SijuMinSijuMax-SijuMin-1Therefore, the convex zone can be mathematically described by(14a)1+SijuMinCiju-Siju≤1+SijuMinln⁡1+SijuMin+1(14b)1+αCiju-Siju≤1+αln⁡1+α-1+1(14c)1+SijuMaxCiju-Siju≤1+SijuMaxln⁡1+SijuMax+1(14d)SijuMax-SijuMinCiju-ln⁡1+SijuMin-ln⁡1+SijuMaxSiju≤SijuMaxln⁡1+SijuMin-SijuMinln⁡1+SijuMaxThus, the original program is relaxed to a linear program as shown in The Relaxed Linear Program. Formulation shown is compact form that is amenable to mathematical operation. These formulation constraints in summary are as follows: Equation (16a) ensures that the assigned flow on an active link does not exceed the channel capacity. Equation (16b) guarantees that the same frequency channel is not scheduled for transmission and reception simultaneously. Equations (16c) and (16d) are implemented to keep the flow conservation from the source node to the destination node. Equation (16e) is used to set the reception threshold to avoid weak channels. Equations (16h) to (16q) are used as implemented via the linear relation to remove the nonlinear terms.The Relaxed Linear Program (15) M a x  λ (16a) S u b j e c t   t o  ∑ i  ≠ d n ,   j ≠  s n U i j ≠ ∅ f i j n - ∑ u ∈  U i j W u ln ⁡ 2 c i j u ≤ 0 (16b) ∑ j ≠ i u ∈ U j χ i j u + ∑ k ≠ j u ∈ U k χ k i u ≤ 1 (16c) ∑ j ≠ i , s n U i j ≠ ∅ f i j n - ∑ k ≠ i , d n U k i ≠ ∅ f k i n = 0 (16d) ∑ j ≠ i ,   i = s n U i j ≠ ∅ f i j n - λ . r n = 0 (16e) ∑ k ≠ i ,   i = d n U k i ≠ ∅ f k i n - λ . r n = 0 (16f) S i j u χ i j u - γ ≤ 0 (16g) q i j u - Q χ i j u ≤ 0 (16h) v k u - ∑ h ≠ k u ∈ u L q k h u = 0 (16i) Q η W P m a x S i j u - g i j u q i j u + ∑ k ≠ i u ∈ u k A i j k u S i j u = 0 (16j) v k u M i n S i j u + S i j u M i n v k u - A i j k u ≤ v k u M i n S i j u M i n (16k) v k u M a x S i j u + S i j u M i n v k u - A i j k u ≥ v k u M a x S i j u M i n (16l) v k u M i n S i j u + S i j u M a x v k u - A i j k u ≥ v k u M i n S i j u M a x (16m) v k u M a x S i j u + S i j u M a x v k u - A i j k u ≤ v k u M a x S i j u M a x (16n) 1 + S i j u M i n C i j u - S i j u ≤ 1 + S i j u M i n ln ⁡ 1 + S i j u M i n + 1 (16o) 1 + α C i j u - S i j u ≤ 1 + α ln ⁡ 1 + α - 1 + 1 (16p) 1 + S i j u M a x C i j u - S i j u ≤ 1 + S i j u M a x ln ⁡ 1 + S i j u M a x + 1 (16q) S i j u M a x - S i j u M i n C i j u - ln ⁡ 1 + S i j u M i n - ln ⁡ 1 + S i j u M a x S i j u ≤ S i j u Max ln ⁡ 1 + S i j u M i n - S i j u Min ln ⁡ 1 + S i j u M a x (16r) f i j n , S i j u , λ , v k u , A i j k u , C i j u ≥ 0 (16s) χ i j u ∈ 0,1 , q i j u ∈ 0,1 , 2 , … , Q (16t) ∀   c o n s t r a i n t s   i ≠ j , k ≠ h , u ∈ U i j , i , j , k , h ∈ N , n ∈ H


### 4.2. Branch-and-Bound Main Algorithm

Branch-and-Bound [19] is an enumeration algorithm that searches all the probable solutions to the problem in an iterative manner. This algorithm starts by a relaxed version of the original problem, i.e., eliminating the integer constraints. Therefore, the obtained solution contains a value that represents the upper bound to the optimum solution for the original program [20]. Furthermore, Branch-and-Bound algorithm provides a (1-ε) suboptimality, where ε is a small nonnegative constant. Depending on a branching variable, the branches are created. Then, each branch represents a subproblem of the original problem. In every iteration phase, the algorithm selects a subproblem from the list to explore it.Figure3 shows the solution algorithm. Branch-and-Bound algorithm starts by obtaining upper bound for the objective function. Moreover, developing initial feasible solution to represent the lower bound to the objective function is required. Iteratively, the algorithm tries to narrow the distance gap between upper and lower bounds until it reaches the required accuracy.Figure 3
Branch-and-Bound main algorithm.On the other hand, if that condition is not satisfied, the original problem is portioned into two problemsɀ1 and ɀ2. Subsequently, the optimization space is split into two spaces. The upper and lower bounds for those problems are iteratively updated.By comparing the new obtained upper bounds with the original upper bound, a tighter upper bound can be achieved. The algorithm obtains optimal solution if the lower and upper bounds are close enough to achieve the conditional formula LB≥ (1-ε) UB. The strength of Branch-and-Bound algorithm lies in its ability to remove some problems from the problems list by a process called pruning. The problem can be discarded if its lower bound is greater than or equal to the original problem upper bound.


### 4.3. Finding Upper and Lower Bounds

#### 4.3.1. Finding Upper Bounds

The nonlinear logarithmic term is relaxed into a set of linear constraints. After relaxing all nonlinear terms for a problem, a relaxed problem can be solved by a linear program in polynomial time. Solving the relaxed linear program provides the upper bound.


#### 4.3.2. Finding Lower Bounds

Lower bound can be determined by local search algorithm. Thus, it starts with any initial feasible solution. That solution may be distant from the optimum one. Consequently, it is improved by iterative algorithm as shown in Figure4. To get that initial feasible solution, the optimization variables are set to xiju|Low and qiju|Low subsequently, obtaining the opposite Siju.Figure 4
Lower bound local search algorithm.Thus, the obtained SINR is compared to the threshold value. If that SINR value is greater than the threshold value, the transmission is successful. Channel capacity can be calculated by (6). It is computed and compared to the obtained flow rates to ensure that those flow rates do not exceed the channel capacity on each link. This can be verified by capacity/flow (c/f) ratio for each link between two nodes.In case of(c/f) < 1 for link(i,j), then, the aggregated flow rates exceed the link capacity and the link capacity constraint on this link is violated. In this case, the flow rates on link must be scaled down.On the other hand, havingλ as large as possible is required. Such a value is the critical value(c∕f)min among all links which is the minimum ratio of all links. Increasing(c∕f)min improves the current solution. Subsequently, in the next iteration, improving the current solution is targeted.


### 4.4. Branching Strategy

Branching variable selection approach is considered a key factor of Branch-and-Bound algorithm efficiency. As well, selecting the right variables to branch results in a spectacular reduction number of problems is required to solve an instance. Traditional branching strategy exhaustively examines variables at every problem node and selects the best variable in terms of tight gap between the best feasible solution and the recent bound [21].This strategy does not take the advantage of network flow routing problem characteristics. The nature of flow routing problem necessitates making the decision of which channels will be active firstly. Then, the power level for each active link is assigned. Based on this nature, a priority of the variables is assumed by the channel status variableχiju and power level qiju, respectively.


## 4.1. Optimization Program Relaxation

The nonlinearity of the problem is due to the product termvkuSiju and the channel capacity equation log2⁡1+Siju. Thus, a reformulation linearization technique [18] will be applied to obtain the program.Regarding the product termvkuSiju, a new variable Aijku is introduced where Aijku=vkuSiju. Then, linear constraints are added. Assume that vku has a minimum value vku|Min and maximum value vku|Max. Similarly, Siju has minimum value Siju|Min and maximum value (Siju)Max. Therefore, linear bounding substitution inequalities can be written in the following form:(11a)vku-vkuMinSiju-SijuMin≥0,(11b)vku-vkuMinSijuMax-Siju≥0,(11c)vkuMax-vkuSiju-SijuMin≥0,(11d)vkuMax-vkuSijuMax-Siju≥0.Then, the product termvkuSiju is replaced by Aijku obtaining that(12a)vkuMinSiju+SijuMinvku-Aijku≤vkuMinSijuMin(12b)vkuMaxSiju+SijuMinvku-Aijku≥vkuMaxSijuMin(12c)vkuMinSiju+SijuMaxvku-Aijku≥vkuMinSijuMax(12d)vkuMaxSiju+SijuMaxvku-Aijku≤vkuMaxSijuMaxOn the other hand, the second termlog2⁡1+Siju can be relaxed by creating a convex envelope for it. A new variable Ciju is introduced where Ciju=ln⁡1+Siju. Using the maximum and the minimum values of variable Siju, a convex envelope can be formed as shown in Figure 2.Figure 2
Formulating the convex envelope.The intersection between tangentsT1 and T3 corresponds to the point Siju=α where it can be calculated by the following expression:(13)α=1+SijuMin1+SijuMaxln⁡1+SijuMax-ln⁡1+SijuMinSijuMax-SijuMin-1Therefore, the convex zone can be mathematically described by(14a)1+SijuMinCiju-Siju≤1+SijuMinln⁡1+SijuMin+1(14b)1+αCiju-Siju≤1+αln⁡1+α-1+1(14c)1+SijuMaxCiju-Siju≤1+SijuMaxln⁡1+SijuMax+1(14d)SijuMax-SijuMinCiju-ln⁡1+SijuMin-ln⁡1+SijuMaxSiju≤SijuMaxln⁡1+SijuMin-SijuMinln⁡1+SijuMaxThus, the original program is relaxed to a linear program as shown in The Relaxed Linear Program. Formulation shown is compact form that is amenable to mathematical operation. These formulation constraints in summary are as follows: Equation (16a) ensures that the assigned flow on an active link does not exceed the channel capacity. Equation (16b) guarantees that the same frequency channel is not scheduled for transmission and reception simultaneously. Equations (16c) and (16d) are implemented to keep the flow conservation from the source node to the destination node. Equation (16e) is used to set the reception threshold to avoid weak channels. Equations (16h) to (16q) are used as implemented via the linear relation to remove the nonlinear terms.The Relaxed Linear Program (15) M a x  λ (16a) S u b j e c t   t o  ∑ i  ≠ d n ,   j ≠  s n U i j ≠ ∅ f i j n - ∑ u ∈  U i j W u ln ⁡ 2 c i j u ≤ 0 (16b) ∑ j ≠ i u ∈ U j χ i j u + ∑ k ≠ j u ∈ U k χ k i u ≤ 1 (16c) ∑ j ≠ i , s n U i j ≠ ∅ f i j n - ∑ k ≠ i , d n U k i ≠ ∅ f k i n = 0 (16d) ∑ j ≠ i ,   i = s n U i j ≠ ∅ f i j n - λ . r n = 0 (16e) ∑ k ≠ i ,   i = d n U k i ≠ ∅ f k i n - λ . r n = 0 (16f) S i j u χ i j u - γ ≤ 0 (16g) q i j u - Q χ i j u ≤ 0 (16h) v k u - ∑ h ≠ k u ∈ u L q k h u = 0 (16i) Q η W P m a x S i j u - g i j u q i j u + ∑ k ≠ i u ∈ u k A i j k u S i j u = 0 (16j) v k u M i n S i j u + S i j u M i n v k u - A i j k u ≤ v k u M i n S i j u M i n (16k) v k u M a x S i j u + S i j u M i n v k u - A i j k u ≥ v k u M a x S i j u M i n (16l) v k u M i n S i j u + S i j u M a x v k u - A i j k u ≥ v k u M i n S i j u M a x (16m) v k u M a x S i j u + S i j u M a x v k u - A i j k u ≤ v k u M a x S i j u M a x (16n) 1 + S i j u M i n C i j u - S i j u ≤ 1 + S i j u M i n ln ⁡ 1 + S i j u M i n + 1 (16o) 1 + α C i j u - S i j u ≤ 1 + α ln ⁡ 1 + α - 1 + 1 (16p) 1 + S i j u M a x C i j u - S i j u ≤ 1 + S i j u M a x ln ⁡ 1 + S i j u M a x + 1 (16q) S i j u M a x - S i j u M i n C i j u - ln ⁡ 1 + S i j u M i n - ln ⁡ 1 + S i j u M a x S i j u ≤ S i j u Max ln ⁡ 1 + S i j u M i n - S i j u Min ln ⁡ 1 + S i j u M a x (16r) f i j n , S i j u , λ , v k u , A i j k u , C i j u ≥ 0 (16s) χ i j u ∈ 0,1 , q i j u ∈ 0,1 , 2 , … , Q (16t) ∀   c o n s t r a i n t s   i ≠ j , k ≠ h , u ∈ U i j , i , j , k , h ∈ N , n ∈ H


## 4.2. Branch-and-Bound Main Algorithm

Branch-and-Bound [19] is an enumeration algorithm that searches all the probable solutions to the problem in an iterative manner. This algorithm starts by a relaxed version of the original problem, i.e., eliminating the integer constraints. Therefore, the obtained solution contains a value that represents the upper bound to the optimum solution for the original program [20]. Furthermore, Branch-and-Bound algorithm provides a (1-ε) suboptimality, where ε is a small nonnegative constant. Depending on a branching variable, the branches are created. Then, each branch represents a subproblem of the original problem. In every iteration phase, the algorithm selects a subproblem from the list to explore it.Figure3 shows the solution algorithm. Branch-and-Bound algorithm starts by obtaining upper bound for the objective function. Moreover, developing initial feasible solution to represent the lower bound to the objective function is required. Iteratively, the algorithm tries to narrow the distance gap between upper and lower bounds until it reaches the required accuracy.Figure 3
Branch-and-Bound main algorithm.On the other hand, if that condition is not satisfied, the original problem is portioned into two problemsɀ1 and ɀ2. Subsequently, the optimization space is split into two spaces. The upper and lower bounds for those problems are iteratively updated.By comparing the new obtained upper bounds with the original upper bound, a tighter upper bound can be achieved. The algorithm obtains optimal solution if the lower and upper bounds are close enough to achieve the conditional formula LB≥ (1-ε) UB. The strength of Branch-and-Bound algorithm lies in its ability to remove some problems from the problems list by a process called pruning. The problem can be discarded if its lower bound is greater than or equal to the original problem upper bound.


## 4.3. Finding Upper and Lower Bounds

### 4.3.1. Finding Upper Bounds

The nonlinear logarithmic term is relaxed into a set of linear constraints. After relaxing all nonlinear terms for a problem, a relaxed problem can be solved by a linear program in polynomial time. Solving the relaxed linear program provides the upper bound.


### 4.3.2. Finding Lower Bounds

Lower bound can be determined by local search algorithm. Thus, it starts with any initial feasible solution. That solution may be distant from the optimum one. Consequently, it is improved by iterative algorithm as shown in Figure4. To get that initial feasible solution, the optimization variables are set to xiju|Low and qiju|Low subsequently, obtaining the opposite Siju.Figure 4
Lower bound local search algorithm.Thus, the obtained SINR is compared to the threshold value. If that SINR value is greater than the threshold value, the transmission is successful. Channel capacity can be calculated by (6). It is computed and compared to the obtained flow rates to ensure that those flow rates do not exceed the channel capacity on each link. This can be verified by capacity/flow (c/f) ratio for each link between two nodes.In case of(c/f) < 1 for link(i,j), then, the aggregated flow rates exceed the link capacity and the link capacity constraint on this link is violated. In this case, the flow rates on link must be scaled down.On the other hand, havingλ as large as possible is required. Such a value is the critical value(c∕f)min among all links which is the minimum ratio of all links. Increasing(c∕f)min improves the current solution. Subsequently, in the next iteration, improving the current solution is targeted.


## 4.3.1. Finding Upper Bounds

The nonlinear logarithmic term is relaxed into a set of linear constraints. After relaxing all nonlinear terms for a problem, a relaxed problem can be solved by a linear program in polynomial time. Solving the relaxed linear program provides the upper bound.


## 4.3.2. Finding Lower Bounds

Lower bound can be determined by local search algorithm. Thus, it starts with any initial feasible solution. That solution may be distant from the optimum one. Consequently, it is improved by iterative algorithm as shown in Figure4. To get that initial feasible solution, the optimization variables are set to xiju|Low and qiju|Low subsequently, obtaining the opposite Siju.Figure 4
Lower bound local search algorithm.Thus, the obtained SINR is compared to the threshold value. If that SINR value is greater than the threshold value, the transmission is successful. Channel capacity can be calculated by (6). It is computed and compared to the obtained flow rates to ensure that those flow rates do not exceed the channel capacity on each link. This can be verified by capacity/flow (c/f) ratio for each link between two nodes.In case of(c/f) < 1 for link(i,j), then, the aggregated flow rates exceed the link capacity and the link capacity constraint on this link is violated. In this case, the flow rates on link must be scaled down.On the other hand, havingλ as large as possible is required. Such a value is the critical value(c∕f)min among all links which is the minimum ratio of all links. Increasing(c∕f)min improves the current solution. Subsequently, in the next iteration, improving the current solution is targeted.


## 4.4. Branching Strategy

Branching variable selection approach is considered a key factor of Branch-and-Bound algorithm efficiency. As well, selecting the right variables to branch results in a spectacular reduction number of problems is required to solve an instance. Traditional branching strategy exhaustively examines variables at every problem node and selects the best variable in terms of tight gap between the best feasible solution and the recent bound [21].This strategy does not take the advantage of network flow routing problem characteristics. The nature of flow routing problem necessitates making the decision of which channels will be active firstly. Then, the power level for each active link is assigned. Based on this nature, a priority of the variables is assumed by the channel status variableχiju and power level qiju, respectively.


## 5. Numerical Results and Discussion

In this section, configuration parameters and results are presented. The results are portioned into two parts. First, finding the impact of the number of power levels (Q) on the channel capacity maximization factor (λ) is required. This is achieved by assuming two network configurations. For each network configuration, the number of nodes, sessions, and the available frequency channels are fixed, while the number of power levels is changing from 1 to 15. This assumption formulates 15 separate cases for each network.Second, studying the performance of the proposed routing scheme in terms of the available frequency channels and connectivity graph is required. In this study, three network configurations are assumed. For each network configuration, there are two cases: the number of available frequency bands (U) is equal to 10 and 20 except the third network configuration where an extra scenario is added when U=30.


### 5.1. System Parameters

In this section, the configuration setup is presented. For all cases, nodes are arbitrarily positioned in a square area of 70m×70m. Each channel has a bandwidth ofWu = 50 MHz. SINR threshold lower bound and the path loss index are assumed to be γ = 3 and μ = 3, respectively. Also, it is assumed that a node at distance of 20 can receive data properly where Pmax=0.48×106ηWu. For the optimization algorithm, the solution accuracy parameter ε is set to 0.05, which guarantees that the obtained solution is within 5% from the optimum solution.


### 5.2. Number of Power Levels

Based on the performance benchmarking for the two network configurations, the best number of transmission power levelsQ is calculated. For the first configuration, the network is assumed to consist of 20 cognitive radio aware nodes. All variables are assumed as in Tables 2 and 3 that represent the position of nodes with the available frequency bands and the source-destination minimum flow rate, respectively. The number of power levels is set to one power level that represents the maximum transmit power level and the first problem is solved. Then, the number of power levels is set to two power levels and this problem is solved, repeatedly, until the relationship between the number of power levels and the scaling factor is obtained. Furthermore, the second network configuration is set to 30 cognitive radio aware nodes. By the same procedure, the relationship between the scaling factor and number of power levels in the two network configurations is obtained as shown in Figure 5.Table 2
20-node position and 10-channel availability.
Node Position Available frequency bands x y N1 2.84 11.77 3,7,10 N2 31.94 33.57 1,2,3,4 N3 1.10 1.07 1,4,5,6 N4 27.74 6.87 5,8 N5 18.54 11.57 5,7,8,10 N6 19.04 21.37 3,5,6,8,9 N7 7.34 5.27 1,4,8 N8 25.34 42.77 1,2,3,5,7,9,10 N9 38.04 12.17 2,9,5 N10 34.64 21.47 3,4,5,6,7,8,9 N11 30.84 27.47 4,5,6,7,8,9 N12 34.94 39.87 1,8,9,10 N13 49.94 4.47 3,5,10 N14 47.44 16.87 2,3,6,7,8 N15 47.44 25.87 5,6,7 N16 50.64 45.67 1,3 N17 49.14 18.67 1,7,9 N18 14.24 14.07 2,5,6,10 N19 30.94 16.67 6,7,8,9 N20 5.24 16.37 1,7Table 3
Source-destination minimum flow rate.
Session Source Destination Minimum flow rate (Mbps) 1 N16 N10 8 2 N18 N3 5 3 N5 N9 1 4 N13 N17 7 5 N15 N6 6Figure 5
Relation between flow rate scaling factor and number of power levels in 20- and 30-node cognitive radio aware network.Based on the results obtained in Figure5, it is shown that the best number of power levels is Q =10. The small number of power levels leads to high power usage even if it is not required which leads to higher interference levels. On the other hand, the large number of power levels allows the nodes to choose the required power level precisely, but that comes at the expense of huge search space.


### 5.3. First Network Configuration

In this network configuration, the cognitive radio nodes are supposed to be 20 nodes. It is assumed that there are 5-user communication sessions in the entire network. This configuration is studied in two cases:U=10 and U=20.


#### 5.3.1. Case I

Frequency channel availability for each node is arbitrarily chosen as listed in Table2. There are 10 frequency channels for the entire network.It is assumed that there are 5-user communication sessions. For each session, source and destination, as well as the associated minimum flow rates, are arbitrarily chosen as listed in Table3. Results for that case are shown in Table 4. It depicts link scheduling assignment. Table 5 shows session and link flow rate assignment. Table 6 depicts power level assignment. Figure 6 shows the connectivity graph in this case.Table 4
Link scheduling assignment.
Band Scheduling Band Scheduling 1 x 7,3, x16,12 6 x 15,19 2 x 8,2 7 x 14,17, x20,1 3 x 13,14 8 x 12,11, x 5,4 4 x 1,7, x2,10 9 x 12,8, x19,6 5 x 11,10, x 4,9 10 x 18,20Table 5
Session and link flow rate assignment.
Session Session flow rate (Mbps) Assigned link flow rate (Mbps) 1 133.4 f 16,12= 133.40, f12,11= f11,10=17.34, f12,8= f8,2= f2,10= 116.06 2 67.5 f 18,20= f20,1= f1,,7= f7,3= 13.5 3 13.5 f 5,4= f4,9= 13.5 4 94.5 f 13,14= f14,17= 94.5 5 81 f 15,19= f19,6= 13.5Table 6
20-node power level assignment.
Band Assigned power level Band Assigned power level 1 q 7,3= 1, q16,12= 10 6 q 15,19= 9 2 q 8,2= 2 7 q 20,1= 1, q14,17= 1 3 q 13,14= 2 8 q 5,4= 3 4 q 2,10= 2, q1,7= 6 9 q 19,6= 4, q12,8= 1 5 q 4,9= 4 10 q 18,20= 1Figure 6
Connectivity graph for N=20 nodes, Case I.To verify flow balance, for example, Session 1 which is the1st row in Table 5, the flow rate from the source node N16 is f16,12= 133.40. It is equal to the flow rate going to the destination node N10 which is equal to the following summation: f11,10+ f2,10 =17.34+116.06 =133.40. Also, at relay nodes such as node N12 f16,12= f12,11 + f12,8. So, the flow conservation constraints in (16c) to (16e) hold from source node to the destination node for each session across the intermediate nodes.Flow splitting and multipath routing appeared for Session 1, which has the largest rate requirement. The same frequency band may be used by concurrent transmissions. For example, sincex7,3, x16,12 are scheduled to Band 1 in Table 4, both nodes N7 and N16 are transmitting on Band 1. Such concurrent transmissions are allowed as long as the SINR at receiving nodes is no less than γ = 3. For example, SINR at receiving node N12 on Band 1 based on (3) and based on the results of the values of power levels q16,121 and q7,31 in Table 6 is(17)S16,121=g16,121q16,121QηW/Pmax+g7,121q7,31=1.27×10-5×102.083×10-5+8.1×10-7×1=5.87.Subsequently,S16,121=5.87 which is larger than γ = 3 and constraint equation (16f) is verified. Thus, the transmission N16 → N12 on Band 1 is successful. Also, constraint equation (16a), which guarantees that the flow rate on an active channel does not exceed the channel capacity can be verified where the channel capacity can be calculated as follows:(18)C16,121=50×log2⁡1+S16,121=50×log2⁡1+5.87≅139.By comparing the channel capacityC16,121 to the deduced flow rate in 1st row in Table 5, f16,12= 133.40 which does not exceed the channel capacity C16,121≅139. Constraint equation (16b) can be easily verified visually where there is no node that uses the same frequency for transmission and reception. Also, by comparing Table 3 session minimum flow rates to the achieved flow rates in Table 5, it is found that all minimum requirements are achieved.


#### 5.3.2. Case II

For further investigation of the solution algorithm performance, the number of available frequency bands is expanded from 10 to 20 bands for the same network configuration. Figure7 shows the connectivity graph in this case.Figure 7
Connectivity graph for N=20 nodes, Case II.Connectivity graph in Figure7 shows that the solution algorithm exploited the extra available bands via multipath routing compared to the connectivity graph in Figure 6. It is clear from Figure 7 that node N18 in this case has the chance to use two available bands to destination node N3 in the same time (Path 1: through nodes N18, N20, N1, N7, and N3 as it appears in Figure 6; Path 2: through the direct path N18-N3). These extra paths are created thanks to the local search algorithm shown in Figure 4. With a closer look to the local search algorithm, it is found that it is trying to increase the power level on unused frequency if it is possible.


### 5.4. Second Network Configuration

In this network configuration, the cognitive radio network is supposed to consist of 30 nodes. It is assumed that there are 5-user communication sessions in the entire network. Two cases are assumed:U =10 and U=20.


#### 5.4.1. Case I

Frequency channel availability for each node is arbitrarily chosen as listed in Table7. There are 10 frequency channels for the entire network. 5-user communication sessions are assumed. For each session, source and destination, and the associated minimum flow rates, are arbitrarily chosen as listed in Table 8. Figure 8 shows the connectivity graph in this case. It is clear from the figure that the multipath routing is verified from N19 to N29. First, N19 uses one path to N23 then it uses direct path N23-N29 and the other path N23-N26-N29.Table 7
30-node position and 10-frequency channels.
Node Position Available frequency bands x y N1 2.84 11.77 1,2,4,7,16,17,19,20 N2 31.94 33.57 3,5,9,12,14,15 N3 5.74 32.97 1,2,6,7,8,11,16,17,19,20 N4 27.74 6.87 1,2,6,7,16,20 N5 18.54 11.57 9.5,17 N6 19.04 21.37 1,2,6,7,8,16,20 N7 7.34 5.27 3,4,5,9,12,14 N8 25.34 42.77 3,4,12 N9 38.04 12.17 10,18 N10 34.64 21.47 3,4,5,9,14 N11 30.84 27.47 1,6,7,8,11,16,17,19,20 N12 34.94 39.87 10,13,18 N13 49.94 4.47 1,2,6,8,11,19 N14 47.44 16.87 3,5,9,14 N15 47.44 25.87 4,9,12,14 N16 50.64 45.67 7,8,11,16,17,19,20 N17 49.14 18.67 7,11,16,17,19,20 N18 14.24 14.07 3,4,5 N19 30.94 16.67 3,12,15 N20 5.24 16.37 5,9 N21 2.84 11.77 1,2,6,7,8,11,16,17,19,20 N22 31.94 33.57 9,12,14,15 N23 5.74 32.97 3,4,5,9,10,12,13,14,15,17 N24 27.74 6.87 1,2,11,16,17,20 N25 18.54 11.57 3,4,5,9,12,14 N26 19.04 21.37 3,5,9,15 N27 7.34 5.27 1,16,20 N28 25.34 42.77 1,2,6,7,8,11,16,17,20 N29 38.04 12.17 3,4,5,9,10,12,14,15,18 N30 41.6 19.14 1,2,6,7,8,11,16,17,19,20Table 8
30-node source-destination minimum flow rate.
Session Source Destination Minimum flow rate 1 N16 N28 4 2 N24 N11 5 3 N13 N1 1 4 N19 N29 7 5 N26 N15 6Figure 8
Connectivity graph for N=30 nodes, Case I and Case II.


#### 5.4.2. Case II

For this network configuration which contains 30 nodes,Q=10, and 20 frequency bands’ availability, multipath routing appears in Session 2 and Session 4. When the spectrum availability is set to 10 bands, only like the previous problem the routing solution reduces these paths to deal with the small number of frequency bands. It is observed that the connectivity graphs for both Cases I and II are the same as shown that in Figure 8.


### 5.5. Third Network Configuration

In this case, the solution algorithm is examined on large number of sessions. So, the number of network nodes is set to N=50, and the number of sessions is 10. Nodes are arbitrarily positioned as shown in Table9. Frequency channel availability for each node is arbitrarily chosen as the listed in Table 9. Source-destination minimum flow rate is shown in Table 10. Two cases are considered: U =20 and U =30.Table 9
50-node positions and frequency availability, Case III.
Node Position Available Bands x y N1 11.1 21.7 2, 3, 4, 8, 25 N2 0.1 4 6, 7, 10, 13, 14, 20, 23, 24, 26, 28 N3 7.2 16.6 6, 10, 14, 20, 23, 24, 26 N4 11 32.2 6, 7, 10, 13, 14, 20, 23, 24, 26, 28 N5 16.3 3.6 10, 13, 14, 20, 23 N6 14.5 24.7 8, 11, 25 N7 14.9 13.7 5, 9, 12, 16, 17, 18, 22, 27, 29, 30 N8 19.5 14.9 7, 24, 28 N9 26.6 13.4 1, 19, 21, 25 N10 22.5 29.3 1, 3, 4, 8, 11, 15, 19 N11 24.6 40.5 3, 8, 25 N12 38.4 13.1 2, 8, 11, 15 N13 4 3.9 9, 12, 16, 22, 27, 29, 30 N14 6.1 18.6 9, 12, 16, 17, 18, 22, 27, 30 N15 38.5 22.6 2, 4, 11, 15, 19, 21, 25 N16 1.2 24.3 5, 9, 12, 17, 22, 29, 30 N17 4.9 42.3 5, 27 N18 18.5 1.4 5, 9, 12, 17, 18, 27, 30 N19 16.9 29.1 3, 4, 10, 11, 12, 15 N20 33.5 10.4 7, 13, 14, 20, 23, 24, 26, 28 N21 25.6 12.8 6, 7, 20, 23, 24, 28 N22 45.2 45.5 2, 8, 15, 19 N23 43.6 22.7 1, 2, 3, 4, 11, 15, 19, 21 N24 10.6 40.5 4, 15, 19, 21, 25 N25 18.2 32.7 9, 12, 18, 22, 27 N26 25.2 27.2 10, 14, 20, 24, 26 N27 22.5 42.2 5, 9, 12, 16, 18, 27, 29, 30 N28 30 31.5 6, 13, 24, 26, 28 N29 35 22.1 6, 10 N30 25.7 6.2 5, 9, 12, 17, 18, 22, 27, 29, 30 N31 34.1 12.4 9, 12, 16, 17, 30 N32 26.4 30 5, 9, 12, 16, 17, 18, 22, 27, 29, 30 N33 14.1 40.7 1, 2, 25 N34 34.4 46.5 9, 17, 18, 30 N35 19 22.5 1, 6, 7, 10, 13, 14, 20, 23, 24, 28 N36 39.9 25.1 6, 13, 14, 20, 23, 24, 26, 28 N37 20.3 18.2 1, 2, 3, 4, 8, 11, 15, 19, 21, 27 N38 10 20.5 6, 7, 10, 13, 14, 20, 23, 24, 26, 28 N39 20.5 21.4 1, 2, 3, 4, 8, 11, 15, 19, 21, 25 N40 37.1 28.6 7, 10, 13, 14, 20, 23, 24, 26 N41 44.1 16.1 1, 15, 21 N42 41.1 6 9, 29 N43 43 18.8 5, 9, 12, 16, 18, 22 N44 45.4 24.2 9, 12, 16, 17, 18, 30 N45 36.2 41.2 5, 9, 17, 27, 29, 30 N46 27.5 32.3 12, 16, 17, 18, 29, 30 N47 47.8 13.8 22, 27, 29, 30 N48 8.9 14.8 5, 30 N49 6.8 6.2 5, 9, 12, 16, 17, 27, 30 N50 11.7 35.8 1, 2, 3, 4, 8, 11, 15, 19, 21, 25Table 10
50-node source-destination minimum flow rate, 10 sessions.
Session Source Destination Minimum flow rate 1 N21 N4 4 2 N5 N26 7 3 N19 N20 6 4 N33 N6 10 5 N37 N10 9 6 N23 N11 2 7 N25 N46 3 8 N42 N43 9 9 N44 N27 8 10 N47 N30 1


#### 5.5.1. Case I

In this case, there are 20 frequency channels for the entire network. Then, there are more available links. The solution algorithm could not establish all communication links properly.


#### 5.5.2. Case II

When there are 30 frequency channels for the entire network, the solution algorithm has more rooms to choose between available links and then it could establish all communication links properly. In addition, it is observed that all communication sessions contain only single path routing. Figure9 shows the connectivity graph in this case. Therefore, in case of large scale network either ensuring that the number of active sessions simultaneously is low or ensuring that there are sufficient available frequency bands is recommended.Figure 9
Connectivity graph for N=50 nodes, Case III.The numerical results proved that the original constraints are achieved. In the first part of the study, the numerical results depicted that the optimum number of power levelsQ is 10. In this case, the network achieves the best flow rate scaling factor and avoids increasing the search space without advantages. In the second part of the study, the routing algorithm was evaluated through different scenarios which proved the strength of the algorithm of routing ability under the physical model of SINR, in addition to the ability of using multipath routing if there are available free channels for use.


### 5.6. Comparative Study

For comparison, the work in [6] shares the power control model in the same way as modeled in the proposed work by using discrete power levels, but this work differs in two main points:(1)
The objective function: It considers the network resource usage minimization including bandwidth usage minimization. Bandwidth usage cannot characterize the interference of radio transmission [22]. For instance, a transmitting node on the same channel bandwidth but with another power levels will produce different interference areas.(2)
Linear relaxation: The utilized relaxation implements the convex hull theory but on a different variable than that proposed in our work. In our work, the relaxation is based on the channel capacity linear relaxation which characterizes the actual levels of interference.By comparing the objective function related to the change of the available power levels in both methods as shown in Figure5 versus Figure 10, the behavior of the two curves is the same manner for three sections, but they are inverted. In other words, the objective function in our technique increases by increasing the number of power levels. Therefore, the other technique loses the granular control for power and interference.Figure 10
Objective value as a function of number of power levels [6].


## 5.1. System Parameters

In this section, the configuration setup is presented. For all cases, nodes are arbitrarily positioned in a square area of 70m×70m. Each channel has a bandwidth ofWu = 50 MHz. SINR threshold lower bound and the path loss index are assumed to be γ = 3 and μ = 3, respectively. Also, it is assumed that a node at distance of 20 can receive data properly where Pmax=0.48×106ηWu. For the optimization algorithm, the solution accuracy parameter ε is set to 0.05, which guarantees that the obtained solution is within 5% from the optimum solution.


## 5.2. Number of Power Levels

Based on the performance benchmarking for the two network configurations, the best number of transmission power levelsQ is calculated. For the first configuration, the network is assumed to consist of 20 cognitive radio aware nodes. All variables are assumed as in Tables 2 and 3 that represent the position of nodes with the available frequency bands and the source-destination minimum flow rate, respectively. The number of power levels is set to one power level that represents the maximum transmit power level and the first problem is solved. Then, the number of power levels is set to two power levels and this problem is solved, repeatedly, until the relationship between the number of power levels and the scaling factor is obtained. Furthermore, the second network configuration is set to 30 cognitive radio aware nodes. By the same procedure, the relationship between the scaling factor and number of power levels in the two network configurations is obtained as shown in Figure 5.Table 2
20-node position and 10-channel availability.
Node Position Available frequency bands x y N1 2.84 11.77 3,7,10 N2 31.94 33.57 1,2,3,4 N3 1.10 1.07 1,4,5,6 N4 27.74 6.87 5,8 N5 18.54 11.57 5,7,8,10 N6 19.04 21.37 3,5,6,8,9 N7 7.34 5.27 1,4,8 N8 25.34 42.77 1,2,3,5,7,9,10 N9 38.04 12.17 2,9,5 N10 34.64 21.47 3,4,5,6,7,8,9 N11 30.84 27.47 4,5,6,7,8,9 N12 34.94 39.87 1,8,9,10 N13 49.94 4.47 3,5,10 N14 47.44 16.87 2,3,6,7,8 N15 47.44 25.87 5,6,7 N16 50.64 45.67 1,3 N17 49.14 18.67 1,7,9 N18 14.24 14.07 2,5,6,10 N19 30.94 16.67 6,7,8,9 N20 5.24 16.37 1,7Table 3
Source-destination minimum flow rate.
Session Source Destination Minimum flow rate (Mbps) 1 N16 N10 8 2 N18 N3 5 3 N5 N9 1 4 N13 N17 7 5 N15 N6 6Figure 5
Relation between flow rate scaling factor and number of power levels in 20- and 30-node cognitive radio aware network.Based on the results obtained in Figure5, it is shown that the best number of power levels is Q =10. The small number of power levels leads to high power usage even if it is not required which leads to higher interference levels. On the other hand, the large number of power levels allows the nodes to choose the required power level precisely, but that comes at the expense of huge search space.


## 5.3. First Network Configuration

In this network configuration, the cognitive radio nodes are supposed to be 20 nodes. It is assumed that there are 5-user communication sessions in the entire network. This configuration is studied in two cases:U=10 and U=20.


### 5.3.1. Case I

Frequency channel availability for each node is arbitrarily chosen as listed in Table2. There are 10 frequency channels for the entire network.It is assumed that there are 5-user communication sessions. For each session, source and destination, as well as the associated minimum flow rates, are arbitrarily chosen as listed in Table3. Results for that case are shown in Table 4. It depicts link scheduling assignment. Table 5 shows session and link flow rate assignment. Table 6 depicts power level assignment. Figure 6 shows the connectivity graph in this case.Table 4
Link scheduling assignment.
Band Scheduling Band Scheduling 1 x 7,3, x16,12 6 x 15,19 2 x 8,2 7 x 14,17, x20,1 3 x 13,14 8 x 12,11, x 5,4 4 x 1,7, x2,10 9 x 12,8, x19,6 5 x 11,10, x 4,9 10 x 18,20Table 5
Session and link flow rate assignment.
Session Session flow rate (Mbps) Assigned link flow rate (Mbps) 1 133.4 f 16,12= 133.40, f12,11= f11,10=17.34, f12,8= f8,2= f2,10= 116.06 2 67.5 f 18,20= f20,1= f1,,7= f7,3= 13.5 3 13.5 f 5,4= f4,9= 13.5 4 94.5 f 13,14= f14,17= 94.5 5 81 f 15,19= f19,6= 13.5Table 6
20-node power level assignment.
Band Assigned power level Band Assigned power level 1 q 7,3= 1, q16,12= 10 6 q 15,19= 9 2 q 8,2= 2 7 q 20,1= 1, q14,17= 1 3 q 13,14= 2 8 q 5,4= 3 4 q 2,10= 2, q1,7= 6 9 q 19,6= 4, q12,8= 1 5 q 4,9= 4 10 q 18,20= 1Figure 6
Connectivity graph for N=20 nodes, Case I.To verify flow balance, for example, Session 1 which is the1st row in Table 5, the flow rate from the source node N16 is f16,12= 133.40. It is equal to the flow rate going to the destination node N10 which is equal to the following summation: f11,10+ f2,10 =17.34+116.06 =133.40. Also, at relay nodes such as node N12 f16,12= f12,11 + f12,8. So, the flow conservation constraints in (16c) to (16e) hold from source node to the destination node for each session across the intermediate nodes.Flow splitting and multipath routing appeared for Session 1, which has the largest rate requirement. The same frequency band may be used by concurrent transmissions. For example, sincex7,3, x16,12 are scheduled to Band 1 in Table 4, both nodes N7 and N16 are transmitting on Band 1. Such concurrent transmissions are allowed as long as the SINR at receiving nodes is no less than γ = 3. For example, SINR at receiving node N12 on Band 1 based on (3) and based on the results of the values of power levels q16,121 and q7,31 in Table 6 is(17)S16,121=g16,121q16,121QηW/Pmax+g7,121q7,31=1.27×10-5×102.083×10-5+8.1×10-7×1=5.87.Subsequently,S16,121=5.87 which is larger than γ = 3 and constraint equation (16f) is verified. Thus, the transmission N16 → N12 on Band 1 is successful. Also, constraint equation (16a), which guarantees that the flow rate on an active channel does not exceed the channel capacity can be verified where the channel capacity can be calculated as follows:(18)C16,121=50×log2⁡1+S16,121=50×log2⁡1+5.87≅139.By comparing the channel capacityC16,121 to the deduced flow rate in 1st row in Table 5, f16,12= 133.40 which does not exceed the channel capacity C16,121≅139. Constraint equation (16b) can be easily verified visually where there is no node that uses the same frequency for transmission and reception. Also, by comparing Table 3 session minimum flow rates to the achieved flow rates in Table 5, it is found that all minimum requirements are achieved.


### 5.3.2. Case II

For further investigation of the solution algorithm performance, the number of available frequency bands is expanded from 10 to 20 bands for the same network configuration. Figure7 shows the connectivity graph in this case.Figure 7
Connectivity graph for N=20 nodes, Case II.Connectivity graph in Figure7 shows that the solution algorithm exploited the extra available bands via multipath routing compared to the connectivity graph in Figure 6. It is clear from Figure 7 that node N18 in this case has the chance to use two available bands to destination node N3 in the same time (Path 1: through nodes N18, N20, N1, N7, and N3 as it appears in Figure 6; Path 2: through the direct path N18-N3). These extra paths are created thanks to the local search algorithm shown in Figure 4. With a closer look to the local search algorithm, it is found that it is trying to increase the power level on unused frequency if it is possible.


## 5.3.1. Case I

Frequency channel availability for each node is arbitrarily chosen as listed in Table2. There are 10 frequency channels for the entire network.It is assumed that there are 5-user communication sessions. For each session, source and destination, as well as the associated minimum flow rates, are arbitrarily chosen as listed in Table3. Results for that case are shown in Table 4. It depicts link scheduling assignment. Table 5 shows session and link flow rate assignment. Table 6 depicts power level assignment. Figure 6 shows the connectivity graph in this case.Table 4
Link scheduling assignment.
Band Scheduling Band Scheduling 1 x 7,3, x16,12 6 x 15,19 2 x 8,2 7 x 14,17, x20,1 3 x 13,14 8 x 12,11, x 5,4 4 x 1,7, x2,10 9 x 12,8, x19,6 5 x 11,10, x 4,9 10 x 18,20Table 5
Session and link flow rate assignment.
Session Session flow rate (Mbps) Assigned link flow rate (Mbps) 1 133.4 f 16,12= 133.40, f12,11= f11,10=17.34, f12,8= f8,2= f2,10= 116.06 2 67.5 f 18,20= f20,1= f1,,7= f7,3= 13.5 3 13.5 f 5,4= f4,9= 13.5 4 94.5 f 13,14= f14,17= 94.5 5 81 f 15,19= f19,6= 13.5Table 6
20-node power level assignment.
Band Assigned power level Band Assigned power level 1 q 7,3= 1, q16,12= 10 6 q 15,19= 9 2 q 8,2= 2 7 q 20,1= 1, q14,17= 1 3 q 13,14= 2 8 q 5,4= 3 4 q 2,10= 2, q1,7= 6 9 q 19,6= 4, q12,8= 1 5 q 4,9= 4 10 q 18,20= 1Figure 6
Connectivity graph for N=20 nodes, Case I.To verify flow balance, for example, Session 1 which is the1st row in Table 5, the flow rate from the source node N16 is f16,12= 133.40. It is equal to the flow rate going to the destination node N10 which is equal to the following summation: f11,10+ f2,10 =17.34+116.06 =133.40. Also, at relay nodes such as node N12 f16,12= f12,11 + f12,8. So, the flow conservation constraints in (16c) to (16e) hold from source node to the destination node for each session across the intermediate nodes.Flow splitting and multipath routing appeared for Session 1, which has the largest rate requirement. The same frequency band may be used by concurrent transmissions. For example, sincex7,3, x16,12 are scheduled to Band 1 in Table 4, both nodes N7 and N16 are transmitting on Band 1. Such concurrent transmissions are allowed as long as the SINR at receiving nodes is no less than γ = 3. For example, SINR at receiving node N12 on Band 1 based on (3) and based on the results of the values of power levels q16,121 and q7,31 in Table 6 is(17)S16,121=g16,121q16,121QηW/Pmax+g7,121q7,31=1.27×10-5×102.083×10-5+8.1×10-7×1=5.87.Subsequently,S16,121=5.87 which is larger than γ = 3 and constraint equation (16f) is verified. Thus, the transmission N16 → N12 on Band 1 is successful. Also, constraint equation (16a), which guarantees that the flow rate on an active channel does not exceed the channel capacity can be verified where the channel capacity can be calculated as follows:(18)C16,121=50×log2⁡1+S16,121=50×log2⁡1+5.87≅139.By comparing the channel capacityC16,121 to the deduced flow rate in 1st row in Table 5, f16,12= 133.40 which does not exceed the channel capacity C16,121≅139. Constraint equation (16b) can be easily verified visually where there is no node that uses the same frequency for transmission and reception. Also, by comparing Table 3 session minimum flow rates to the achieved flow rates in Table 5, it is found that all minimum requirements are achieved.


## 5.3.2. Case II

For further investigation of the solution algorithm performance, the number of available frequency bands is expanded from 10 to 20 bands for the same network configuration. Figure7 shows the connectivity graph in this case.Figure 7
Connectivity graph for N=20 nodes, Case II.Connectivity graph in Figure7 shows that the solution algorithm exploited the extra available bands via multipath routing compared to the connectivity graph in Figure 6. It is clear from Figure 7 that node N18 in this case has the chance to use two available bands to destination node N3 in the same time (Path 1: through nodes N18, N20, N1, N7, and N3 as it appears in Figure 6; Path 2: through the direct path N18-N3). These extra paths are created thanks to the local search algorithm shown in Figure 4. With a closer look to the local search algorithm, it is found that it is trying to increase the power level on unused frequency if it is possible.


## 5.4. Second Network Configuration

In this network configuration, the cognitive radio network is supposed to consist of 30 nodes. It is assumed that there are 5-user communication sessions in the entire network. Two cases are assumed:U =10 and U=20.


### 5.4.1. Case I

Frequency channel availability for each node is arbitrarily chosen as listed in Table7. There are 10 frequency channels for the entire network. 5-user communication sessions are assumed. For each session, source and destination, and the associated minimum flow rates, are arbitrarily chosen as listed in Table 8. Figure 8 shows the connectivity graph in this case. It is clear from the figure that the multipath routing is verified from N19 to N29. First, N19 uses one path to N23 then it uses direct path N23-N29 and the other path N23-N26-N29.Table 7
30-node position and 10-frequency channels.
Node Position Available frequency bands x y N1 2.84 11.77 1,2,4,7,16,17,19,20 N2 31.94 33.57 3,5,9,12,14,15 N3 5.74 32.97 1,2,6,7,8,11,16,17,19,20 N4 27.74 6.87 1,2,6,7,16,20 N5 18.54 11.57 9.5,17 N6 19.04 21.37 1,2,6,7,8,16,20 N7 7.34 5.27 3,4,5,9,12,14 N8 25.34 42.77 3,4,12 N9 38.04 12.17 10,18 N10 34.64 21.47 3,4,5,9,14 N11 30.84 27.47 1,6,7,8,11,16,17,19,20 N12 34.94 39.87 10,13,18 N13 49.94 4.47 1,2,6,8,11,19 N14 47.44 16.87 3,5,9,14 N15 47.44 25.87 4,9,12,14 N16 50.64 45.67 7,8,11,16,17,19,20 N17 49.14 18.67 7,11,16,17,19,20 N18 14.24 14.07 3,4,5 N19 30.94 16.67 3,12,15 N20 5.24 16.37 5,9 N21 2.84 11.77 1,2,6,7,8,11,16,17,19,20 N22 31.94 33.57 9,12,14,15 N23 5.74 32.97 3,4,5,9,10,12,13,14,15,17 N24 27.74 6.87 1,2,11,16,17,20 N25 18.54 11.57 3,4,5,9,12,14 N26 19.04 21.37 3,5,9,15 N27 7.34 5.27 1,16,20 N28 25.34 42.77 1,2,6,7,8,11,16,17,20 N29 38.04 12.17 3,4,5,9,10,12,14,15,18 N30 41.6 19.14 1,2,6,7,8,11,16,17,19,20Table 8
30-node source-destination minimum flow rate.
Session Source Destination Minimum flow rate 1 N16 N28 4 2 N24 N11 5 3 N13 N1 1 4 N19 N29 7 5 N26 N15 6Figure 8
Connectivity graph for N=30 nodes, Case I and Case II.


### 5.4.2. Case II

For this network configuration which contains 30 nodes,Q=10, and 20 frequency bands’ availability, multipath routing appears in Session 2 and Session 4. When the spectrum availability is set to 10 bands, only like the previous problem the routing solution reduces these paths to deal with the small number of frequency bands. It is observed that the connectivity graphs for both Cases I and II are the same as shown that in Figure 8.


## 5.4.1. Case I

Frequency channel availability for each node is arbitrarily chosen as listed in Table7. There are 10 frequency channels for the entire network. 5-user communication sessions are assumed. For each session, source and destination, and the associated minimum flow rates, are arbitrarily chosen as listed in Table 8. Figure 8 shows the connectivity graph in this case. It is clear from the figure that the multipath routing is verified from N19 to N29. First, N19 uses one path to N23 then it uses direct path N23-N29 and the other path N23-N26-N29.Table 7
30-node position and 10-frequency channels.
Node Position Available frequency bands x y N1 2.84 11.77 1,2,4,7,16,17,19,20 N2 31.94 33.57 3,5,9,12,14,15 N3 5.74 32.97 1,2,6,7,8,11,16,17,19,20 N4 27.74 6.87 1,2,6,7,16,20 N5 18.54 11.57 9.5,17 N6 19.04 21.37 1,2,6,7,8,16,20 N7 7.34 5.27 3,4,5,9,12,14 N8 25.34 42.77 3,4,12 N9 38.04 12.17 10,18 N10 34.64 21.47 3,4,5,9,14 N11 30.84 27.47 1,6,7,8,11,16,17,19,20 N12 34.94 39.87 10,13,18 N13 49.94 4.47 1,2,6,8,11,19 N14 47.44 16.87 3,5,9,14 N15 47.44 25.87 4,9,12,14 N16 50.64 45.67 7,8,11,16,17,19,20 N17 49.14 18.67 7,11,16,17,19,20 N18 14.24 14.07 3,4,5 N19 30.94 16.67 3,12,15 N20 5.24 16.37 5,9 N21 2.84 11.77 1,2,6,7,8,11,16,17,19,20 N22 31.94 33.57 9,12,14,15 N23 5.74 32.97 3,4,5,9,10,12,13,14,15,17 N24 27.74 6.87 1,2,11,16,17,20 N25 18.54 11.57 3,4,5,9,12,14 N26 19.04 21.37 3,5,9,15 N27 7.34 5.27 1,16,20 N28 25.34 42.77 1,2,6,7,8,11,16,17,20 N29 38.04 12.17 3,4,5,9,10,12,14,15,18 N30 41.6 19.14 1,2,6,7,8,11,16,17,19,20Table 8
30-node source-destination minimum flow rate.
Session Source Destination Minimum flow rate 1 N16 N28 4 2 N24 N11 5 3 N13 N1 1 4 N19 N29 7 5 N26 N15 6Figure 8
Connectivity graph for N=30 nodes, Case I and Case II.


## 5.4.2. Case II

For this network configuration which contains 30 nodes,Q=10, and 20 frequency bands’ availability, multipath routing appears in Session 2 and Session 4. When the spectrum availability is set to 10 bands, only like the previous problem the routing solution reduces these paths to deal with the small number of frequency bands. It is observed that the connectivity graphs for both Cases I and II are the same as shown that in Figure 8.


## 5.5. Third Network Configuration

In this case, the solution algorithm is examined on large number of sessions. So, the number of network nodes is set to N=50, and the number of sessions is 10. Nodes are arbitrarily positioned as shown in Table9. Frequency channel availability for each node is arbitrarily chosen as the listed in Table 9. Source-destination minimum flow rate is shown in Table 10. Two cases are considered: U =20 and U =30.Table 9
50-node positions and frequency availability, Case III.
Node Position Available Bands x y N1 11.1 21.7 2, 3, 4, 8, 25 N2 0.1 4 6, 7, 10, 13, 14, 20, 23, 24, 26, 28 N3 7.2 16.6 6, 10, 14, 20, 23, 24, 26 N4 11 32.2 6, 7, 10, 13, 14, 20, 23, 24, 26, 28 N5 16.3 3.6 10, 13, 14, 20, 23 N6 14.5 24.7 8, 11, 25 N7 14.9 13.7 5, 9, 12, 16, 17, 18, 22, 27, 29, 30 N8 19.5 14.9 7, 24, 28 N9 26.6 13.4 1, 19, 21, 25 N10 22.5 29.3 1, 3, 4, 8, 11, 15, 19 N11 24.6 40.5 3, 8, 25 N12 38.4 13.1 2, 8, 11, 15 N13 4 3.9 9, 12, 16, 22, 27, 29, 30 N14 6.1 18.6 9, 12, 16, 17, 18, 22, 27, 30 N15 38.5 22.6 2, 4, 11, 15, 19, 21, 25 N16 1.2 24.3 5, 9, 12, 17, 22, 29, 30 N17 4.9 42.3 5, 27 N18 18.5 1.4 5, 9, 12, 17, 18, 27, 30 N19 16.9 29.1 3, 4, 10, 11, 12, 15 N20 33.5 10.4 7, 13, 14, 20, 23, 24, 26, 28 N21 25.6 12.8 6, 7, 20, 23, 24, 28 N22 45.2 45.5 2, 8, 15, 19 N23 43.6 22.7 1, 2, 3, 4, 11, 15, 19, 21 N24 10.6 40.5 4, 15, 19, 21, 25 N25 18.2 32.7 9, 12, 18, 22, 27 N26 25.2 27.2 10, 14, 20, 24, 26 N27 22.5 42.2 5, 9, 12, 16, 18, 27, 29, 30 N28 30 31.5 6, 13, 24, 26, 28 N29 35 22.1 6, 10 N30 25.7 6.2 5, 9, 12, 17, 18, 22, 27, 29, 30 N31 34.1 12.4 9, 12, 16, 17, 30 N32 26.4 30 5, 9, 12, 16, 17, 18, 22, 27, 29, 30 N33 14.1 40.7 1, 2, 25 N34 34.4 46.5 9, 17, 18, 30 N35 19 22.5 1, 6, 7, 10, 13, 14, 20, 23, 24, 28 N36 39.9 25.1 6, 13, 14, 20, 23, 24, 26, 28 N37 20.3 18.2 1, 2, 3, 4, 8, 11, 15, 19, 21, 27 N38 10 20.5 6, 7, 10, 13, 14, 20, 23, 24, 26, 28 N39 20.5 21.4 1, 2, 3, 4, 8, 11, 15, 19, 21, 25 N40 37.1 28.6 7, 10, 13, 14, 20, 23, 24, 26 N41 44.1 16.1 1, 15, 21 N42 41.1 6 9, 29 N43 43 18.8 5, 9, 12, 16, 18, 22 N44 45.4 24.2 9, 12, 16, 17, 18, 30 N45 36.2 41.2 5, 9, 17, 27, 29, 30 N46 27.5 32.3 12, 16, 17, 18, 29, 30 N47 47.8 13.8 22, 27, 29, 30 N48 8.9 14.8 5, 30 N49 6.8 6.2 5, 9, 12, 16, 17, 27, 30 N50 11.7 35.8 1, 2, 3, 4, 8, 11, 15, 19, 21, 25Table 10
50-node source-destination minimum flow rate, 10 sessions.
Session Source Destination Minimum flow rate 1 N21 N4 4 2 N5 N26 7 3 N19 N20 6 4 N33 N6 10 5 N37 N10 9 6 N23 N11 2 7 N25 N46 3 8 N42 N43 9 9 N44 N27 8 10 N47 N30 1


### 5.5.1. Case I

In this case, there are 20 frequency channels for the entire network. Then, there are more available links. The solution algorithm could not establish all communication links properly.


### 5.5.2. Case II

When there are 30 frequency channels for the entire network, the solution algorithm has more rooms to choose between available links and then it could establish all communication links properly. In addition, it is observed that all communication sessions contain only single path routing. Figure9 shows the connectivity graph in this case. Therefore, in case of large scale network either ensuring that the number of active sessions simultaneously is low or ensuring that there are sufficient available frequency bands is recommended.Figure 9
Connectivity graph for N=50 nodes, Case III.The numerical results proved that the original constraints are achieved. In the first part of the study, the numerical results depicted that the optimum number of power levelsQ is 10. In this case, the network achieves the best flow rate scaling factor and avoids increasing the search space without advantages. In the second part of the study, the routing algorithm was evaluated through different scenarios which proved the strength of the algorithm of routing ability under the physical model of SINR, in addition to the ability of using multipath routing if there are available free channels for use.


## 5.5.1. Case I

In this case, there are 20 frequency channels for the entire network. Then, there are more available links. The solution algorithm could not establish all communication links properly.


## 5.5.2. Case II

When there are 30 frequency channels for the entire network, the solution algorithm has more rooms to choose between available links and then it could establish all communication links properly. In addition, it is observed that all communication sessions contain only single path routing. Figure9 shows the connectivity graph in this case. Therefore, in case of large scale network either ensuring that the number of active sessions simultaneously is low or ensuring that there are sufficient available frequency bands is recommended.Figure 9
Connectivity graph for N=50 nodes, Case III.The numerical results proved that the original constraints are achieved. In the first part of the study, the numerical results depicted that the optimum number of power levelsQ is 10. In this case, the network achieves the best flow rate scaling factor and avoids increasing the search space without advantages. In the second part of the study, the routing algorithm was evaluated through different scenarios which proved the strength of the algorithm of routing ability under the physical model of SINR, in addition to the ability of using multipath routing if there are available free channels for use.


## 5.6. Comparative Study

For comparison, the work in [6] shares the power control model in the same way as modeled in the proposed work by using discrete power levels, but this work differs in two main points:(1)
The objective function: It considers the network resource usage minimization including bandwidth usage minimization. Bandwidth usage cannot characterize the interference of radio transmission [22]. For instance, a transmitting node on the same channel bandwidth but with another power levels will produce different interference areas.(2)
Linear relaxation: The utilized relaxation implements the convex hull theory but on a different variable than that proposed in our work. In our work, the relaxation is based on the channel capacity linear relaxation which characterizes the actual levels of interference.By comparing the objective function related to the change of the available power levels in both methods as shown in Figure5 versus Figure 10, the behavior of the two curves is the same manner for three sections, but they are inverted. In other words, the objective function in our technique increases by increasing the number of power levels. Therefore, the other technique loses the granular control for power and interference.Figure 10
Objective value as a function of number of power levels [6].


## 6. Conclusions

In this paper, a cross-layer routing framework for distributed multihop cognitive radio networks was studied. The problem formulated under the SINR physical model captures the physical layer characteristics precisely. The proposed solution provided a tailored Branch-and-Bound solution algorithm via linear relaxation, local search algorithm, and problem specific branching variables selection. Numerical results depicted that the optimum scaling factor is affected by the number of power levels available to SUs. Thus, the conducted scenarios depicted that optimum achieved scaling factor can be optimum when the number of power levels is equal to 10. This value achieves better performance power without sacrificing better flow rate scaling factor and avoids increasing the search space without significant improvement in the flow rate scaling factor. In addition, the algorithm could achieve the multipath routing when it is possible where local search algorithm tries to assign power to unused frequency channels taking into consideration the interference levels. However, using this framework in applications with small to medium networks to avoid the complexity raised by increasing the number of variables to the Branch-and-Bound algorithm is recommended.



---

*Source: 3545946-2018-07-10.xml*