Guillaume Artero Gallardo
email: guillaume.artero-gallardo@ens-lyon.fr

Gentian Jakllari
email: jakllari@enseeiht.fr

Lucile Canourgues
email: lucile.canourgues@rockwellcollins.com

André-Luc Beylot
email: beylot@enseeiht.fr

A.-L Beylot

Statistical Admission Control in Multi-Hop Cognitive Radio Networks

Keywords: Multi-hop cognitive radio networks, statistical admission control, TDMA, randomized scheduling. I

We address the problem of online admission control in multi-hop, multi-transceiver cognitive radio networks where the channel access is regulated by a bare-bones time-division multiple access protocol and the primary user activity is modeled as an ON/OFF process. We show that the problem of computing the available end-to-end bandwidth-necessary for admission control-is NP-Complete. Rather than working on an approximation algorithm and analyzing its worst-case performance, we relax the problem of online admission control by using a randomized scheduling algorithm and analyzing its average performance. Randomized scheduling is widely used because of its simplicity and efficiency. However, computing the resulting average throughput is challenging and remains an open problem. We solve this problem analytically and use the solution as vehicle for BRAND-a centralized heuristic for computing the average bandwidth available with randomized scheduling between a source destination pair in cognitive radio networks. Driven by practical considerations, we introduce a distributed version of BRAND and prove its correctness. An extensive numerical analysis demonstrates the accuracy of BRAND and its enabling value in performing admission control.

effort has been put in developing solutions for cognitive radio networks at the physical, link and the routing layers [START_REF] Gavrilovska | Medium access control protocols in cognitive radio networks: Overview and general classification[END_REF]- [START_REF] Chowdhury | CRP: A routing protocol for cognitive radio ad hoc networks[END_REF]. However, we are far from having all the answers.

One question that has not been addressed is that of online admission control in multi-hop, multi-transceiver cognitive radio networks where channel access is regulated by a TDMA MAC. Given a newly arrived traffic session, before admitting it, we would like to know whether there is enough bandwidth for servicing its traffic demand. The question can be answered by first computing the bandwidth currently available on the path from the source to the destination node. Computing the end-to-end bandwidth in wireless networks is not a new problem [START_REF] Kodialam | Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem[END_REF], [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF]. However, there are two reasons for revisiting it. First, most literature on legacy 1 TDMA wireless networks is focused on establishing worst-case bounds at the expense of practicality. For example, some of the classic works on the subject [START_REF] Kodialam | Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem[END_REF], [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF] cannot be deployed in practice. Reference [START_REF] Kodialam | Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem[END_REF] assumes a wireless node is always capable of receiving from a one-hop neighbor while a second onehop neighbor is transmitting to someone else. Reference [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF] proposes a centralized solution as benchmarking tool for quantifying the performance of distributed solutions. Solutions landing themselves to practical implementations are rare [START_REF] Li | Local sufficient rate constraints for guaranteed capacity region in multi-radio multi-channel wireless networks[END_REF]. Second, the cognitive radio architecture makes the problem non-trivially different. In its landmark ruling [START_REF]Evaluation of the Performance of Prototype TV-Band White Space Devices[END_REF], permitting the use of unlicensed devices in the UHF spectrum, FCC required that unlicensed devices -the secondary users -do not interfere with incumbents -the primary users. Thus, the endto-end bandwidth will depend not only on the interference among peers, as it is the case in legacy wireless networks, but also on a different kind of interference. Primary users, as their prerogative, will access the channel without making any effort, such as following an agreed upon protocol, to avoid interfering with secondary users.

In this work, we carefully consider the different constraints and tradeoffs and address the problem of online admission control in multi-hop cognitive radio networks in four steps. First, we construct the problem of computing the available end-to-end bandwidth in multi-hop cognitive radio networks. This is not straightforward as one has to account for the primary user interference. It may be tempting to think of primary user interference as no different than secondary interference. However, note that secondary users are required to implement mechanisms, such as sensing [START_REF] Bahl | White space networking with Wi-Fi like connectivity[END_REF], to avoid interfering with primary user traffic. These mechanisms are inevitably imperfect, leading to false positives and negatives whose impact on the bandwidth needs to be carefully modeled and calculated. Second, we analyze the problem and show that it is NP-Complete. In light of this result, the traditional approach would be to design an approximation scheduling algorithm with a bounded worst-case performance [START_REF] Kodialam | Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem[END_REF], [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF]. Instead, we relax the problem of online admission control by using a randomized scheduling algorithm and accepting an average end-to-end bandwidth. This is motivated by the observation that a distributed solution to the relaxed version of the problem is more useful to admission control than a centralized solution that in theory could calculate a better and more accurate bandwidth but that cannot be implemented. Third, we introduce the Clique Sliding approach and use it to analytically solve the problem of computing the end-to-end bandwidth with randomized scheduling. Randomized scheduling is widely used in practice because of its simplicity and efficiency [START_REF] Rhee | DRAND: Distributed randomized TDMA scheduling for wireless ad-hoc networks[END_REF]. However, computing the endto-end throughput resulting from its application on a multihop path is a challenging and, to the best of our knowledge, open problem. We use this solution as vehicle for BRAND, a centralized algorithm for estimating the available Bandwidth with RANDomized scheduling. Finally, we introduce a distributed implementation of BRAND and using the Clock Condition [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] prove its correctness. Our contributions may be summarized as follows:

• We analyze the sources of interference in cognitive radio networks, including how primary users impact the bandwidth (Section III).

• We formally define the problem of computing the available bandwidth between a source destination pair in a TDMA based multi-hop cognitive radio network and show that it is NP-Complete (Section IV-A).

• We introduce a linear time algorithm that can compute the average end-to-end throughput resulting from using randomized slot scheduling for satisfying a given traffic demand on every link of the path connecting a given source destination pair (Section IV-C).

• We introduce BRAND, a heuristic for estimating the available end-to-end bandwidth. BRAND leverages our new algorithm to compute the average endto-end throughput for all possible traffic demands.

The maximum over all the computed throughput values is returned as the available end-to-end bandwidth (Section IV-B).

• We introduce a distributed version of BRAND, prove its correctness and show that it can be implemented by most routing protocol approaches (Section V).

• We perform an extensive numerical analysis of BRAND in general and the throughput computation algorithm in particular. Our analysis demonstrates the accuracy of our algorithm and BRAND's capability to provide correct information for performing online admission control in cognitive radio networks (Section VII).

II. RELATED WORK

In the following we present related works focused on cognitive radio networks as well as works in the area of bandwidth estimation and/or allocation for traditional wireless networks.

Cognitive Radio Networks

A main goal of any cognitive radio architecture is to protect the primary users from interference [START_REF] Chowdhury | CRP: A routing protocol for cognitive radio ad hoc networks[END_REF]. At the routing layer, a node is required to adapt its path computations according to the primary user activity. To this end, it can either route around the primary user, thus potentially increasing the path length, or, switch its transmission channel on the affected links [START_REF] Khalife | Multihop cognitive radio networks: To route or not to route[END_REF]. Obviously, both strategies will increase the end-toend delay. An optimal routing metric for multi-hop cognitive radio networks is proposed in [START_REF] Caleffi | OPERA: Optimal routing metric for cognitive radio ad hoc networks[END_REF]. The authors analytically demonstrate its optimality and accuracy for the cases of mobile and static networks. While the works presented so far are shown to handle well the primary users, none of them addresses the problem of admission control for quality of service. Works closer to the problem considered in our work can be found in [START_REF] Pan | Joint routing and link scheduling for cognitive radio networks under uncertain spectrum supply[END_REF] and [START_REF] Li | Spectrum assignment and sharing for delay minimization in multi-hop multi-flow CRNs[END_REF] where algorithms for joint routing, link scheduling and spectrum assignment have been studied. Nevertheless, the problem of computing the end-to-end bandwidth of a multih-hop path is not addressed in any of these works.

Non-Cognitive (Legacy) Networks

The problem of QoS in non-cognitive wireless multi-hop architectures, with a single or multiple radios, has been subject to significant research efforts and an exhaustive survey is beyond the scope of this paper. Here we simply summarize a subset of the published results closest to the work presented in this paper. The problem of admission control for QoS routing in multi-hop networks is studied by numerous works, including [START_REF] Zhu | QoS routing for mobile ad hoc networks[END_REF] and the references therein. In [START_REF] Zhu | QoS routing for mobile ad hoc networks[END_REF], it is shown that for a TDMA architecture, the problem of computing the residual end-to-end bandwidth for a multi-hop path is NP-Complete. A greedy heuristic is proposed and incorporated in the AODV routing protocol. However, this heuristic was designed for a single radio, non-cognitive radio architecture and, as we discuss in Section VII, cannot be readily applied to a cognitive radio architecture. In [START_REF] Alicherry | Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks[END_REF], Alicherry et al. study the joint routing and channel assignment problem for the case of wireless mesh networks with multiple radios. They propose a constant approximation algorithm to the NP-hard problem of maximizing the overall network throughput subjected to fairness constraints. Similarly, [START_REF] Lin | Distributed and provably efficient algorithms for joint channel-assignment, scheduling, and routing in multichannel ad hoc wireless networks[END_REF] introduces a distributed, online and provably efficient algorithm for joint routing, channel assignment and scheduling in multi-hop multi-radio ad hoc networks. In [START_REF] Kodialam | Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem[END_REF] Kodialam and Nandagopal consider the problem of joint routing and link scheduling and propose a solution which consists of forming a set of constraints and solving a linear programming problem. A set of necessary conditions for a rate vector to be achieved is available in [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF]. In [START_REF] Li | Local sufficient rate constraints for guaranteed capacity region in multi-radio multi-channel wireless networks[END_REF] the capacity region of multi-radio multi-channel wireless networks has been studied by introducing a multi-dimensional conflict graph characterizing the interference between adjacent (radio, link, channel)-tuples. An admission control scheme is introduced by deriving a set of local sufficient conditions for flow feasibility in such networks. The proposed solution can identify the feasible flows. However, among the feasible flows it can only provide a positive answer for admission for the ones that satisfy the sufficient conditions; there is no answer for the feasible flows that do not satisfy the sufficient conditions. What is more, in this work as well as in [START_REF] Kodialam | Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem[END_REF] and [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF], the focus has been on the offline version of the admission control problem. That is, given a network with no prior allocations, the problem considered is that of computing the maximum rate that can be admitted between a source and a destination. In our work, we focus on the online version of the admission control problem: Given a live network, where capacity is allocated as traffic sessions arrive, the problem we tackle is that of computing the bandwidth available between a source and a destination at the time a new traffic session arrives.

III. MODELING INTERFERENCE IN COGNITIVE RADIO NETWORKS

In the following, we describe in detail how we model a multi-hop, multi-transceiver cognitive radio network.

A. Network Model

We model a multi-hop cognitive radio network as a graph G = (V, E), where V is the set of nodes and E the links. We assume that the network comprises only symmetric links. Every cognitive radio node is equipped with a constant number of half-duplex transceivers, each capable of sensing and transmitting on B predefined orthogonal wireless channels. The transceivers can support several bit-rates on all the channels. An additional transceiver could be used for control signaling. We assume the channel assignment is performed by a spectrum allocation protocol [START_REF] Ahmed | Channel assignment algorithms in cognitive radio networks: Taxonomy, open issues, and challenges[END_REF] and focus on estimating the available end-to-end bandwidth once such assignment is completed. The only assumption we make about the frequency assignment algorithm is that only one frequency channel is assigned between a particular pair of neighboring nodes.

B. Cognitive Channel Access

As a prerequisite for using licensed spectrum, cognitive radios are not allowed to use the channel when it is in use by the respective licensed user. In literature, this is referred to as the secondary-primary2 hierarchy, with the primary (licensed) user having strict priority over the secondary user when accessing the channel. In this setting, the key novel challenge when designing a channel access protocol is maximizing the realized capacity of the cognitive radio without adversely affecting the Primary User, despite not knowing the latter's communication pattern [START_REF] Kim | Efficient discovery of spectrum opportunities with MAC-layer sensing in cognitive radio networks[END_REF], [START_REF] Jiang | Renewal-theoretical dynamic spectrum access in cognitive radio network with unknown primary behavior[END_REF]. In response to this challenge, several new MAC protocols for cognitive radio networks have been proposed [START_REF] Gavrilovska | Medium access control protocols in cognitive radio networks: Overview and general classification[END_REF]. For all the diversity of the proposed solutions, one thing underlying all the protocols is the need for a sensing module for identifying when the cognitive radio may be interfering with the primary user. In its most basic form, this module relies on physically sensing the channel [START_REF] Bahl | White space networking with Wi-Fi like connectivity[END_REF] periodically to look for primary user activity. When possible, the physical sensing can be complemented by a database of well-known primary users [START_REF] Murty | SenseLess: A database-driven white spaces network[END_REF].

Given the functionality of the sensing module, a MAC protocol for cognitive radio networks needs to provide periods of network silence dedicated to sensing for primary user activity. What is more, since the activity of the primary user may be completely unknown, the sensing periods need to be periodic. This means that, at given time intervals, all cognitive radios in the network will stop from generating any traffic, and instead, focus on sensing. This is a requirement that can be easily accommodated by a TDMA protocol. Indeed, most MAC protocols proposed for cognitive radio networks [START_REF] Debroy | Contention based multichannel MAC protocol for distributed cognitive radio networks[END_REF], [START_REF] Hamdaoui | OS-MAC: An efficient MAC protocol for spectrum-agile wireless networks[END_REF], including the IEEE 802.22 MAC, are based on TDMA. Nevertheless, some solutions based on random access have also been proposed [START_REF] Zhao | FMAC: A fair MAC protocol for coexisting cognitive radio networks[END_REF], [START_REF] Zhang | CREAM-MAC: Cognitive radio-enabled multichannel MAC protocol over dynamic spectrum access networks[END_REF], [START_REF] Ren | CAD-MAC: A channel-aggregation diversity based MAC protocol for spectrum and energy efficient cognitive ad hoc networks[END_REF], [START_REF] Deb | An agile and efficient MAC for wireless access over TV whitespaces[END_REF].

While there is no clear winner yet among the MAC protocols proposed, we believe a deterministic medium access protocol will better serve an architecture where multiple technologies share the same spectrum and synchronization is required for sensing. Therefore, we adopt a system in which a TDMA MAC with frame size S is implemented on every assigned channel. Every time-slot starts with a sensing period. When a node needs to transmit data to a neighboring node, it can get access to the medium by reserving time-slots on the frequency channel assigned to this particular link. For ease of presentation, we refer to the pair (channel, timeslot) simply as, a slot.

C. Interference in Cognitive Radio Networks

There are two kinds of interference sources in a cognitive radio network. One, the interference caused by other cognitive radios in the same interference domain, usually referred to as secondary-to-secondary interference. And two, the interference caused by the Primary User. The first is not unlike the interference legacy wireless networks have to cope with: Nodes running the same protocol contend for access to the same channel. The primary user interference, however, is different: As its prerogative, the primary user can choose to access the channel at any given time with the expectation of no interference from any potential secondary users. In the following, we discuss how these two sources of interference are modeled in this work.

1) Secondary-to-Secondary Interference:

For the secondary-to-secondary interference we use the model usually employed in TDMA systems on half-duplex wireless transceivers. Specifically, when a particular node needs to transmit data it reserves a new time-slot on the channel it has been assigned. For the time-slot to be reserved, it needs to satisfy the following requirements:

1) It is not used on this channel by the node itself for transmitting, 2) It is not used on this channel by a one-hop neighbor for transmitting, 3) It is not used on this channel by a two-hop neighbor for transmitting.

We assume every node knows the slot allocations in its two-hop neighborhood and thus can check the satisfiability of the above constraints.

2) Quantifying the Primary User Interference: Once the sensing module identifies a primary user, the cognitive radios should stop all communications. Therefore, it is required that a cognitive radio spends part of the time sensing for primary users and part of the time actually transmitting data. To accommodate this requirement, in our model an amount of time in every slot is dedicated to sensing. The optimal ratio between sensing and channel access depends on several factors, including the Primary User activity, the radio environment, etc, and its computation is orthogonal to our work. We refer the reader to [START_REF] Marino | On spectrum sensing optimal design in spatial-temporal domain for cognitive radio networks[END_REF] and references therein for an authoritative treatment of the subject. Note that, the correctness of our scheme does not depend on the exact values of sensing and access time.

If during the sensing period a primary is identified, no communication will take place in the access part of the slot. Otherwise, the cognitive radio is free to access the channel.

Note, however, that sensing is not perfect. It can very well happen that, while no primary user is identified during the sensing period, a primary user does become active for the whole or part of the access time. When this happens, the exact consequences on whatever secondary user transmissions going on will vary depending on the location and the power strength of the primary user. We follow a somehow pessimistic assumption: A primary, when active, will interfere destructively with any secondary communication taking place in its range. 3If we denote with η the part of the slot access time that will be available to the secondary user, based on the reasoning so far, we have:

η = P[sensing the channel idle]

× (Fraction of Access Time Free of PU)

Denoting with u l the probability of a primary user becoming active on link l during a particular slot, the fraction of the slot access time available to the secondary on link l can be computed as follows:

η l = (1 -u l ) 2 (1)
Proof: The PU's channel state can be modeled by an alternative ON/OFF process [START_REF] Kim | Efficient discovery of spectrum opportunities with MAC-layer sensing in cognitive radio networks[END_REF], [START_REF] Jiang | Renewal-theoretical dynamic spectrum access in cognitive radio network with unknown primary behavior[END_REF], [START_REF] Jiang | Joint spectrum sensing and access evolutionary game in cognitive radio networks[END_REF]. The lengths of the ON and OFF states related to link l, respectively T on and T of f can be assumed to be exponentially distributed as follows:

f on (t) = λ on e -λont f of f (t) = λ of f e -λ of f t
with parameters λ on and λ of f estimated with maximum likelihood methods. Jiang et al. [START_REF] Jiang | Renewal-theoretical dynamic spectrum access in cognitive radio network with unknown primary behavior[END_REF], [START_REF] Jiang | Joint spectrum sensing and access evolutionary game in cognitive radio networks[END_REF] have focused on computing the quantity of PU-SU interference accumulated during the access time for evaluating the impact of SU's communications on PU's Quality of Service and appropriately tuning the access time. Defining I 0 (T access ) as the expected length of all ON states within time T access given that T access begins from the OFF state and I 1 (T A ) the same given that T access begins from the ON state, they demonstrated that I 0 (T access ) and I 1 (T access ) satisfy two renewal equations and derived their closed-form expressions. Regarding the communication link l, as P[occurence of the OFF state] = 1 -u l , we get:

I l 0 (T access ) = u l T access -u 2 l × 1 λ of f × 1-e -Taccessλ of f /u l (2)
and

I l 1 (T access ) = u l T access + (1 -u l ) 2 × 1 λ on × 1 -e -Taccessλ of f /u l (3)
Although the sensing may declare the primary channel idle, it is still possible that PU's communications begin just before the sensing period ends. This situation can occur if the computed energy does not exceed the selected threshold. Therefore, we define the quantity of interference relative to a slot access time as:

Q l = (1 -u l ) × I l 0 (T access ) + u l × I l 1 (T access ) T access (4)
where T access corresponds to the slot access time. Substituting Equations 2 and 3 in Equation 4 leads to

Q l = u l and η l = (1 -u l ) 2 .
Taking into account the sensing time, the fraction of slot duration, f l , available for secondary-to-secondary communication is:

f l = η l × T access T sensing + T access (5)
Eq. ( 1) quantifies the effect of two things on the capacity for the secondary. First, the interference from the primary, who as the owner of the frequency is bounded by no protocol to try to avoid interference with an ongoing secondary communication. And second, the mechanism put in place, i.e. sensing, for satisfying the requirement of doing no harm to the primary.

IV. COMPUTING THE AVAILABLE END-TO-END BANDWIDTH FOR ADMISSION CONTROL

A. Problem Definition Let d, expressed in bits per second, be the amount of bandwidth demanded by an application. Before admitting to route this demand, we would first like to know whether this demand can be satisfied end-to-end. This question can be answered by simply computing the currently available end-to-end bandwidth of the path to the destination.

Definition 1: The available end-to-end bandwidth of a path is the maximum amount of data, in bits per second, that can be currently transported over the path.

Remark 1: Unlike the maximum end-to-end bandwidth, the available bandwidth is time sensitive and depends on the current conditions and allocations in the network. If there is no other ongoing traffic in the network and there is no Constructing the formal problem definition: A path is modeled as a directed chain

n 1 → n 2 • • • → n NH +1
comprising N H hops. For ease of presentation, we denote a link n i → n i+1 as l i . The bit-rate of every link is denoted by φ i and, for every link, the maximum TDMA frame size is S slots. To take into account the effect of self-interference, that is, links on the same path interfering with each other, we use the exponential notation (j) to specify that the considered quantity is evaluated just before node n j on the same path does its allocations. Using this convention, we define A (j) i as the number of slots available at node n i for communication on the link l i just before n j does its own allocations.

Let us analyze the network behavior when admitting a new flow with demand d. The first node on the path, n 1 , converts the flow demand, d, to the required number of slots, r 1 , to be allocated on the first path link, l 1 . The number of required slots will depend on the demand, the link bit-rate, φ 1 , the TDMA frame size, S, as well as the primary user interference (quantified in Section III-C.2, Eq. ( 5)):

r 1 = d φ 1 × f 1 × S
Let a i denote the number of slots allocated on every hop i ∈ {1, .., N H } for serving this particular flow. For every hop this number will depend on both the demand and how many slots are actually available for new allocations. Thus, for the first hop we have a 1 = min(r 1 , A

1 ). If a 1 < r 1 the demand on the second link will be lower than the original demand, d. To distinguish the two, we denote the demand on the second link, which depends on the allocation on the first link as, d 1 . Table I lists the notations used in the paper.

Rigorously speaking, d 1 = min d, a 1 × ( φ1×f1 S ) , where the quantity by which a 1 is multiplied is the capacity of a single slot on the first link. We can generalize these results for any hop, i > 1, as follows:

r i = d i-1 φ i × f i × S (6)
a i = min (r i , A (i) i ) (7)
d i = min d i-1 , a i × φ i × f i S (8)
Thus, for a specific demand d, the realized end-to-end throughput is min (

d 1 , d 2 , . . . , d NH ) = d NH , since d i ≥ d i+1 .
This analysis gives us a way for tackling the main problem: computing the available end-to-end bandwidth. Problem 1: Computing the available end-to-end bandwidth of a path is equivalent to solving the following optimization problem:

max d∈I d d NH (d) (9)
where

I d = [0, min(φ 1 , φ 2 , . . . , φ NH )].
The optimization problem thus defined leads to two observations:

1) The realized end-to-end throughput, d NH (d), given a demand, d, obviously depends on d. 2) d NH (d) depends on how the slots are allocated on every hop. Theorem 1: Computing the available end-to-end bandwidth of a path in a TDMA-based multi-hop cognitive radio networks with multiple transceivers is NP-complete.

Proof: The proof is straightforward so we provide a sketch. We show that our problem is NP-Complete by reducing the problem of computing the maximum path bandwidth in a single-channel TDMA-based multi-hop network, therein referred to as P 2 , to our problem, therein referred to as P 1 . To this end, we consider the instance of P 1 where a same channel with a constant data rate is assigned on every link along the path and the probability of primary activity on all links is zero. Solving P 2 actually consists of solving one instance of P 1 . Since P 2 has been shown to be NP-complete [START_REF] Zhu | QoS routing for mobile ad hoc networks[END_REF], that concludes the proof.

B. BRAND: An Approach for Estimating the Available End-to-End Bandwidth of a Path

With the problem of computing the available end-to-end bandwidth being NP-Complete, the overwhelming approach in literature has been to design a scheduling heuristic. We follow a different approach: We select a specific slotscheduling algorithm and focus on computing the available end-to-end bandwidth resulting from applying this particular algorithm. As scheduling algorithm we select the randomized scheduling [START_REF] Rhee | DRAND: Distributed randomized TDMA scheduling for wireless ad-hoc networks[END_REF]: when a node needs to assign a certain number of slots, it will select at random among those available. Randomized scheduling is widely used because of its simplicity and efficiency even though the worst case performance can be poor.

Algorithm 1 provides a high-level description of BRAND, our solution for estimating the available end-to-end Bandwidth with RANDom scheduling. It works as follows: For every possible demand d, the necessary slots are allocated at random among those available on every link and the resulting end-to-end throughput is computed (Section IV-C). By Eq. ( 9), the available end-to-end bandwidth is simply the maximum end-to-end throughput realized over all possible demands d.

), E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3
. When an allocation takes place on l 1 , the proportion of the slots allocated, p 1 , (area painted in gray) is transferred from the sets E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 to E 1,2,3 to account for the interference. The same is repeated for the allocations on l 2 and l 3 . The challenge is estimating the size of the "gray" (or, equivalently, "white") areas in every set after each allocation. for every possible demand d do //Use randomized scheduling.

:

avT hput ← Compute-averageThput (d);

:

if avThput > AvailBW then 5 :

AvailBW ← avT hput;

:

Return AvailBW ;

The value of the demand, d, is upper-bounded by the lowest radio bit-rate in the network and lower-bounded by 0. Since this is a slotted system, the values of d have to be multiples of the smallest slot capacity in the network. Thus, the possible values of d that need to be considered are bounded by a constant. The non-trivial step of BRAND, line 3 in Algorithm 1, is computing the average end-to-end throughput when the required slots for satisfying a particular demand, d, are assigned at random. Note that, because the slots are allocated at random, we can only compute the average and not the exact value of the resulting end-to-end throughput. In Section IV-C, we give a centralized approach that, given a demand d, computes the average end-to-end throughput realized. In Section V we propose a distributed approach.

C. Computing the Average End-to-End Throughput With Random Scheduling

We propose an analytical framework for computing the average end-to-end throughput that could be realized if a new demand d is admitted and randomized scheduling is used on every link. This calculation constitutes line 3 in Algorithm 1.

(1) The Case of a 3-hop Path At first we solve the problem of computing the average throughput on a 3-hop path. This helps introduce our approach along with the notations we use (see Table I) before we show how it is extended to the general case of a n-hop path.

Let PSAT (path's slots availability table) be a 2-dimensional array of B × S columns and N H lines showing the available slots across the N H hops constituting the particular path and the B available frequencies at any given time -the total path capacity.

• 3-hop available slots partition -not all slots are created equal: Let A 1 be the set of slots (represented by their respective indices {1, . . . , S.B} in the PSAT table) available for reservation on link l 1 at the beginning of the computation process. These slots are not all equal -some are available on l 1 , l 2 and l 3 , some only on l 1 , some on l 1 and l 2 but not l 3 , and some are available on l 1 and l 3 but not l 2 . Allocating slots available on all three links will reduce the slots available on l 2 and l 3 and by extension the end-to-end throughput; allocating slots available only on l 1 will have no bearing on l 2 and l 3 . Clearly, for the same number of slots allocated on l 1 , depending on which specific slots are actually allocated, the resulting end-to-end throughput can be different. Therefore, to compute the end-to-end throughput, we divide the available slots into sets of slots whose allocation impacts the bandwidth the same way -the 3-hop available slots partition. Fig. 1(a) illustrates the concept.

• Computing the average throughput of a 3-hop path given a demand d: Fig. 1 gives a high level picture of how the computation process works. Fig. 1(a) -we carry a 3-hop available slots partition that produces 8 different sets:

E (1) 1,2,3
(set of slots available for allocation on all 3 links), E

(1) 1,2,3 (set of slots available to none of the links),

E (1) 1,2,3 , E (1) 1,2,3 , E (1) 1,2,3 , E (1) 1,2,3 , E (1) 1,2,3 , E (1)
1,2,3 . The exponent, 1, indicates that the particular membership of each set is valid until node n 1 performs its allocations. Fig. 1(b) -node n 1 tries to allocate enough slots to satisfy the demand d. As the slots are allocated uniformly at random, it is possible that a portion of slots is allocated ("painted gray") from each of the 4 possible sets:

E (1) 1,2,3 , E (1) 1,2,3 , E (1) 1,2,3 , E (1)
1,2,3 . Fig. 1(c) -node n 2 tries to allocate enough slots to satisfy the demand generated by n 1 . It is conditioned by the initial state of the system as well as the allocations of n 1 . Its own allocations can affect each of the sets

E (2) 1,2,3 , E (2) 1,2,3 , E (2) 1,2,3 , E (2)
1,2,3 . Fig. 1(d) -finally, node n 3 tries to allocate enough slots to satisfy the demand generated by n 2 . It is conditioned by the initial state, the slots allocated by n 1 and those allocate by n 2 . The slots that n 3 is able to allocate define the end-to-end throughput given the demand d at n 1 . Computing it requires calculating the impact of each allocation on the 8 available slot sets -or, using the illustration, computing the size of the "gray" areas. • Domino Effect: Algorithm 2 leverages the random nature of the scheduling algorithm to compute the average number of slots impacted in every available slots partition set. For example, a proportion a 1 /A (1) 1 , line 7 in Algorithm 2, of the available slots on l 1 is likely to be reserved by n 1 . Therefore, in lines 8 and 9, we can calculate the impact of this allocation on the available slots partition sets and, by extension, the slots left available for allocation on links l 2 and l 3 . This reveals why this problem is fundamentally hard: an allocation on l 1 can impact the allocations on all the following links, creating what we refer to as a domino effect.

While quantifying the domino effect on all allocations is manageable for 3 hops, it becomes intractable for the general case of a n-hop path. For k ∈ {0, 1, . . . , n}, the number of sets containing the slots available to k hops but not the other n -k equals n k . Thus, the number of sets resulting from the n-hop available slots partition would be:

n k=0 n k = 2 n .
In the following, we present the Interference-Clique sliding approach, capable of breaking the domino effect, thus, making the problem of computing the average end-to-end throughput tractable.

(

2) The General Case of a n-Hop Path

The interference-clique sliding approach breaks the domino effect by processing the end-to-end bandwidth estimation clique by clique while using only a constant number of variables. We define an interference-clique, or simply clique, 4as any set of three consecutive links on the path. For instance, a 4-hop path comprises two cliques: c 1 = {l 1 , l 2 , l 3 } and c 2 = {l 2 , l 3 , l 4 }.

When processing a clique i, the goal is to calculate a i , the number of slots that will be allocated on link l i given a demand d at the source. As shown by Eq.( 7) in Section IV-A, a i depends on the demand arriving from link l 1 and the slots available when the allocation takes place, A (i) i . Given the 3-hop available slots partition of clique i, we have:

A (i) i = C (i) i,i+1,i+2 + C (i) i,i+1,i+2 + C (i) i,i+1,i+2 + C (i) i,i+1,i+2 (10)
The challenge in solving Eq.( 10) is computing the cardinalities of the available slots set based on the initial state of the system, i.e. before any allocations for serving the demand d taking place. Generally speaking, when processing the i th clique, the impact of the allocations on the two previous links can be correctly estimated by updating the cardinalities of the sets resulting from its 3-hop available slots partition as follows:

C (i) i = C (1) i -p i × I i + u i + v i (11)
where

C (j) i = C (j) i,i+1,i+2 C (j) i,i+1,i+2 • • • C (j) i,i+1,i+2 p i = p i-2 p i-1 [p i-2 + p i-1 .(1 -p i-2 )]
and

I i =     C (i-2) i-2,i-1,i,i+1,i+2 • • • C (i-2) i-2,i-1,i,i+1,i+2 C (i-2) i-2,i-1,i,i+1,i+2 • • • C (i-2) i-2,i-1,i,i+1,i+2 C (i-2) i-2,i-1,i,i+1,i+2 • • • C (i-2) i-2,i-1,i,i+1,i+2    
The vector u i serves to compensate a set that is not affected by allocations on all the links. The vector v i is then used to update the sets receiving slots that, due to the allocation process, become unavailable on other links. The values of vectors u i and v i depend on some variables used in p i and I i and are given in the Appendix of the companion technical report [START_REF] Gallardo | Statistical admission control in multi-hop cognitive radio networks[END_REF].

In the following we solve Eq.( 11) for all the possible cases.

• Interference-Clique 1: Clique 1 is the easiest to process as it does not depend on any previous allocations. Exactly a 1 = min(r 1 , A

(1) 1 ) slots are reserved for communication on link l 1 . The remaining available slots on l 1 are not considered anymore and the calculation is passed on to clique 2.

• Interference-Clique 2: To measure correctly the impact on clique 2 by the reservations on l 1 , the 3-hop available slots partition related to clique 2 is extended to the 4-hop available slots partition so as to include l 1 . Thus, we have:

C (1) 2,3,4 = C (1) 1,2,3,4
impacted by allocations on l1 + C

(1) 1,2,3,4 not impacted [START_REF] Li | Local sufficient rate constraints for guaranteed capacity region in multi-radio multi-channel wireless networks[END_REF] Therefore, an average proportion

p 1 = a 1 /A (1) 1 of slots in E (1)
1,2,3,4 is likely to become unavailable for reservation on link l 2 after node n 1 performs its allocations.

Assuming there is no interference between l 1 and l 4 , the clique 2 sets can be updated as follows:

C (2) 2,3,4 = C (1) 2,3,4 -p 1 .C (1) 1,2,3,4 C (2) 2,3,4 = C (1) 2,3,4 -p 1 .C (1) 1,2,3,4 C (2) 2,3,4 = C (1) 2,3,4 -p 1 .C (1) 1,2,3,4 C (2) 2,3,4 = C (1) 2,3,4 -p 1 .C (1) 1,2,3,4 C (2) 2,3,4 = C (1) 2,3,4 -p 1 .C (1) 1,2,3,4 C (2) 2,3,4 = C (1) 2,3,4 -p 1 .C (1) 1,2,3,4 C (2) 2,3,4 = C (1) 2,3,4 + p 1 . C (1) 1,2,3,4 + C (1) 1,2,3,4 + C (1) 1,2,3,4 C (2) 2,3,4 = C (1) 2,3,4 + p 1 . C (1) 1,2,3,4 + C (1) 1,2,3,4 + C (1) 1,2,3,4 (13)
• Interference-Clique 3: This clique is impacted by the allocations on the two previous links, l 1 and l 2 . Furthermore, we need to keep in mind that l 3 is impacted by the allocation on l 1 and l 2 while l 4 only by the allocation on l 2 . Therefore, we have:

C (1) 3,4,5 = C (1) 1,2,3,4,5
impacted by allocations on l1 and then l2 + C

(1) 1,2,3,4,5

impacted by allocations on l1 but not l2 + C

(1) 1,2,3,4,5

impacted by allocations on l2 but not l1 + C

(1) 1,2,3,4,5 not impacted [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] which leads to:

C (3) 3,4,5 = C (1) 3,4,5 -[p 1 + p 2 (1 -p 1 )].C (1) 1,2,3,4,5 -p 1 .C (1) 1,2,3,4,5 -p 2 .C (1) 1,2,3,4,5 (15)
Measuring the impact of allocations on l 1 and l 2 is equivalent to transferring slots from one set to another. Indeed, from the previous equations, we can conclude that, on average,

p 1 . C (1) 1,2,3,4,5 + C (1)
1,2,3,4,5 slots and p 2 (1 -p 1 ).C • Interference-Clique 4 and beyond: When processing the third clique, the entries of matrix I i referred strictly to sets that had not changed from the beginning of the estimation process. However, that is not the case when processing the fourth clique. The corresponding sets are likely to have been impacted by allocations on the previous links. For example, E

(2) 2,3,4,5,6 is probably impacted by the allocations on l 1 and thus needs to be updated. A straightforward solution would identify the sets resulting from the 6-hop available slots partition and estimate how each set is impacted. This method is correct but the number of resulting sets grows exponentially with the number of links and thus is intractable.

Fortunately, the random nature of the scheduling algorithm can simplify the analysis and bound by a constant the number of variables to deal with at every clique. Say we want to characterize a set used in the clique i, e.g.

E (i-2) i-2,i-1,i,i+1,i+2
, as a function of its initial state. We start by doing the 2-hop available slots partition related to l i-2 and l i-1 . This partition leads to four disjoint sets:

E (j) i-2,i-1 ,E (j) i-2,i-1 ,E (j) i-2,i-1 and E (j) i-2,i-1 . Let us first work on E (j)
i-2,i-1 . This set can also be partitioned into eight subsets resulting from the 3-hop available sets partition of clique i. In this partition the slot space equals E (j) i-2,i-1 rather than {1, 2, . . . , S.B}, leading to subsets of the following form

E (j) i-2,i-1,i,i+1,i+2 . A property of the set E (j)
i-2,i-1 is that along the estimation process, it can only transfer slots to the set E (j) i-2,i-1 and cannot receive slots from another. Therefore, the number of slots that initially belonged to the set E (j) i-2,i-1 but became unavailable just before the allocation on link l i-2 equals C

(1)

i-2,i-1 -C (i-2) i-2,i-1 .
These slots became unavailable due to allocations on l i-4 and l i-3 . Because of the random nature of the slot reservation process, these slots were taken uniformly at random among the subsets partitioning E (j) i-2,i-1 . We can thus represent the number of slots that became unavailable in

E (j) i-2,i-1,i,i+1,i+2
with the discrete random variable X i-2,i-1,i,i+1,i+2 taking its values in the set {0, . . . , C

i-2,i-1 -C (i-2) i-2,i-1 } and following a hypergeometric distribution with parameters (C (1) i-2,i-1 , C (1) i-2,i-1,i,i+1,i+2 , C (1) i-2,i-1 -C (i-2) (1)
i-2,i-1 ). From this identification we can deduce that, for C

i-2,i-1 strictly positive, the average value of this random variable equals

[(C (1) i-2,i-1 -C (i-2) i-2,i-1 )/C (1) i-2,i-1 ] × C (1) i-2,i-1,i,i+1,i+2 .
More generally, just before node n i-2 does its allocations,

C (i-2) i-2,i-1 /C (1)
i-2,i-1 of the initially available slots remain available in every subset partitioning

E (j) i-2,i-1 . The quantity C (i-2)
i-2,i-1,i,i+1,i+2 can be computed as follows: [START_REF] Caleffi | OPERA: Optimal routing metric for cognitive radio ad hoc networks[END_REF] where the reduction factor of the set

C (i-2) i-2,i-1,i,i+1,i+2 = C (1) i-2,i-1,i,i+1,i+2 × α i-2,i-1
E (j) i-2,i-1 equals α i-2,i-1 =              0, if C (1) i-2,i-1 = 0 C (i-2) i-2,i-1 C (1) i-2,i-1 = C (i-2) i-2,i-1,i + C (i-2) i-2,i-1,i C (1) i-2,i-1,i + C (1) i-2,i-1,i , otherwise (17)
and is related to clique (i -2) as it can be computed at the beginning of the process of this clique. The same analysis can be applied to the other two sets of interest, E

i-2,i-1 . However, it needs modification for the case of

E (j) i-2,i-1 when C (1)
i-2,i-1 = 0 as this set can receive slots from E (j) i-2,i-1 due to the allocations on the previous links. To correctly update the resulting subsets, we compute the proportion of slots transferred from

E (j) i-2,i-1 to E (j) i-2,i-1 . The quantity C (i-2)
i-2,i-1,i,i+1,i+2 can be computed as follows:

C (i-2) i-2,i-1,i,i+1,i+2 = C (1) i-2,i-1,i,i+1,i+2 × τ i-2 (18)
with

τ i-2 = C (i-2) i-2,i-1 C (1) i-2,i-1 = C (i-2) i-2,i-1,i + C (i-2) i-2,i-1,i C (1) i-2,i-1,i + C (1) i-2,i-1,i (19) if C (1)
i-2,i-1 is strictly positive, and zero otherwise. Note that for all the apparent complexity, the cliquesliding approach does a single pass on the path, with a constant number of computations on every clique. Therefore, the running time is linear on the length of the path.

V. DISTRIBUTED IMPLEMENTATION OF BRAND

The centralized version of BRAND can be easily used with source routing protocols, like DSR [START_REF] Maltz | The effects of on-demand behavior in routing protocols for multihop wireless ad hoc networks[END_REF], where the path computation is centralized at the source. However, this is not the case for non-source routing protocols, like the popular OLSR [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF], where the route computation is performed at every node in distributed fashion. To address this limitation we present a simple mechanism that enables the distributed execution of BRAND. Fig. 2. The BRAND computation is executed clique by clique -first clique being l 1 , l 2 , l 3 , second l 2 , l 3 , l 4 , and so forth. Node n 3 knows the source, n 1 , the previous hop, n 2 , and next hop, n 4 , allowing it to bootstrap the BRAND computation.

previous clique. Second, the sliding is strictly linear, needing a single pass from the source to the destination.

A straightforward solution would work as follows. The first node on the path would execute the computation for the first clique, comprising links l 1 , l 2 , l 3 . Once the computation was done, the node would insert the results of the computation as well as the reduction factors in a control packet, call it the bandwidth packet (BP) and would transmit it to the next hop on the path asking it to perform the same for the second clique, comprising links l 2 , l 3 , l 4 . The process would be repeated till the destination, which would complete the sliding and send the results back to the source node. Assuming the BP packet is received by the destination, the result would be identical to centralized BRAND.

The problem with this solution is that, with non-source routing, a particular node does not know which direction a given packet is going beyond the next hop. That means the source node only knows the next hop for a given path, when doing the computation for the first clique of that path requires knowledge of the next three hops. To overcome this challenge, we propose a simple trick: Simply shift the interferenceclique calculation by two hops down the path. As illustrated in Figure 2, the BRAND computation is bootstrapped by node n 3 , which regardless of the routing protocol will know n 1 , the source, n 2 , the previous hop and n 4 , the next hop. Equipped with the information necessary,5 n 3 , performs the BRAND computation for the first clique. Once the computation is done, it sends the BP control packet to n 4 and the rest proceeds as in the straightforward solution. Algorithm 3 gives the specification of the distributed algorithm in pseudo-code for the case of non-trivial (longer than two hops) paths.

Finally, in the following we show the correctness of distributed BRAND.

Theorem 2: Assuming the bandwidth packet (BP) is eventually received by all nodes along the path and the communications follow the protocol model [START_REF] Gupta | The capacity of wireless networks[END_REF], distributed BRAND results in the same computation as centralized BRAND.

Proof: For distributed BRAND to give the same result as centralized BRAND it suffices to show that clique computations take place in order. That is, computation in clique i -1 always happens-before computation in clique i. That is equiva-

VI. R-BRAND: ADMISSION CONTROL FOR TIME-SENSITIVE APPLICATIONS

In this section, we show how to modify BRAND so as to provide admission control to time-sensitive traffic flows. At the high level, R-BRAND, the real-time tailored version of BRAND, works by repeating the following fours steps as long as there are flows waiting admission:

1) Compute the available end-to-end bandwidth with BRAND, 2) Determine the amount of RTP flows that can be admitted end-to-end, given the bandwidth required by every single flow, 3) Compute the average6 end-to-end delay for that set of newly admitted flows, 4) Decide whether admission can be granted given the endto-end QoS constraints. To estimate 7 the average end-to-end delay, we adopt a queuing system approach and model a path as a set of N h queues with finite buffer sizes disposed in tandem, as illustrated in Fig. 3. A service corresponds to a transmission occurring over a link i at rate µ i packets per second. Given that a i slots would be allocated on the i-th link (this quantity is evaluated during the execution of step 1), the probability of server i being active at an arbitrary time is f i = r i /S. The i-th queue blocking probability, B i , depends on the values of µ i as well the traffic intensity entering the queue, λ i . Given its value, the traffic intensity entering the following queue equals λ i+1 = (1 -B i )λ i . Denoting with Q i and R i the average number of packets stored in queue i and the average delay of packets traversing that queue, respectively, the Little's law gives:

R i = Q i /((1 -B i )λ i ),
We compute R, the average end-to-end delay, as the sum of the values R i for all the queues composing the path. Due to space constraints, however, the rest of the analysis can be found in the Appendix C of the companion technical report [START_REF] Gallardo | Statistical admission control in multi-hop cognitive radio networks[END_REF]. user interference. As computing the optimal slot scheduling is NP-Complete, we formulate the problem as an integer linear program, see the Appendix of the companion technical report [START_REF] Gallardo | Statistical admission control in multi-hop cognitive radio networks[END_REF], and use lpsolve [START_REF] Berkelaar | telecommunications and networks from INP Toulouse, France, in 2011 and 2015[END_REF] to generate optimal scheduling assignments for a given PSAT table of a given path. Figure 4 shows that BRAND is very competitive when compared to KODIALAM, an algorithm proposed as benchmarking tool by its inventors mainly because it cannot be computed in distributed fashion, as well as the optimal scheduler.

C. End-to-End Throughput With Randomized Scheduling

The most novel and challenging part of BRAND is its algorithm for computing the average throughput of randomized scheduling, introduced in Section IV-C. Given the involved analysis of the algorithm, here we perform a simple experiment for verifying its correctness. For a specific value of hop-count and probability of no secondary interference, p a , we generate a PSAT table using MATLAB. The algorithm is applied using the PSAT table and the average end-to-end throughput is computed for all demands described in Section VII-A. With the same PSAT and traffic demands, we run simulations in MATLAB in which the slots are selected at random on every hop. The simulation is run multiple times and the seed for the random generator is changed every time. The throughput values measured at the end of each simulation are averaged over all runs. In Figure 5, for every demand, the computed and the measured throughput values for p a = 33% and p a = 50% are plotted on the x and y-axis, respectively. The probability of PU interference is set to 10%. The data shown are for a 10-hop path, a very large value. Even for this challenging scenario, after 5 runs the measurements are already converging to the computed values.

D. Admission Control Performance

BRAND is designed for enabling admission control. As such, we expect any flow with demand less than or equal to the available bandwidth computed by BRAND to be admitted end-to-end. To verify that this is the case, we perform the following two-step experiment. In the first step, we apply BRAND on a 4-hop path and compute the available end-to-end Fig. 5.

Numerical verification of the correctness of the algorithm for computing the average throughput introduced in Section IV-C. The y-axis represents the values obtained numerically, and for these graphs are averages over 5 runs. The probability of PU interference, u, is set to 10%.

6. The x-axis represents the available end-to-end bandwidth computed by BRAND for various probabilities of no secondary interference. The y-axis represents the end-to-end throughput measured in simulations -utilizing the same PSAT as the computation -when the traffic demand is equal to the respective end-to-end bandwidth computed by BRAND. The data shown here is for paths of four (N H = 4) and ten hops (N H = 10). Nearly 100% admission is achieved.

bandwidth for various values of p a . Specifically, we perform the computation on PSAT tables generated by taking the probabilities of no secondary interference, p a , in (0, 1) while the primary user interference is set to 10%. One PSAT table is generated per value of p a and one bandwidth value per PSAT is computed by BRAND.

The available bandwidth values computed by BRAND in the first step are used as input in the second step of the experiment. Specifically, for every value of p a and respective PSAT used in the first step, we run a simulation during which a single session with traffic demand equal to the available bandwidth computed by BRAND for this value of p a is initiated endto-end. We measure the end-to-end throughput realized during the simulation and plot it as function of the computed demand. To provide more data about the behavior of BRAND we repeat the same experiment for a 10-hop path, as long a path as one can expect to encounter in deployed multi-hop cognitive radio networks. As shown in Figure 6, the measured throughput is practically identical to the computed values of the available bandwidth. This demonstrates that BRAND delivers the bandwidth it promises and provides nearly 100% admission.

E. Cognitive Effect: Primary Users and Multi-Rate Links

We now evaluate the performance of BRAND for a cognitive network architecture in which nodes access the spectrum as secondary users. In addition to BRAND, we also use the Zhu heuristic in this part of the evaluation. The latter was designed for a single-rate, single-transceiver legacy architecture so clearly it would be unfair to expect it to perform as well as BRAND. Instead, the reason for which we include it in this evaluation is for quantifying the consequences of ignoring the primary user and multi-rate links when computing the available bandwidth.

To evaluate the "cognitive" effect, we repeat the experiment of the previous section using multi-transceivers, multiple-rates and varying probabilities of the Primary User occurrence. As shown in Figure 7 BRAND almost always estimates the correct value for the available capacity. On the other hand, ignoring the operating specifics of the cognitive radio networks leads to significant errors, as high as 900%, when calculating the available end-to-end bandwidth. A careful analysis of the data, especially that of Figure 7(c), does show that, at times, Zhu realizes a higher available bandwidth in simulations. As predicted by Equation 1 in Section III-C.2, protecting the Primary User comes at a cost in terms of bandwidth, explaining the smaller bandwidth values computed by BRAND at times.

F. Distributed BRAND: Mobility, Channel Fading, Sensing Errors and Multiple Flows

In this experiment, we consider a more realistic scenario that includes mobility, channel fading and PU sensing errors for evaluating the performance of distributed BRAND. We set up a multi-hop cognitive radio network of 30 nodes placed at random on a 1000mx1000m area. We select at random four source-destination pairs and start generating unicast sessions. Whenever a new traffic session arrives we use the distributed implementation of BRAND for performing admission control. We carry out two sets of experiments, one with no mobility for isolating the effect of sensing errors and a second where we evaluate the effect of fading and node mobility.

Figure 8 shows the performance of distributed BRAND for various PU sensing error levels. As the data shows, BRAND is resilient to sensing errors and that, even when the PU activity is underestimating by 30%, the estimation errors are modest in most cases.

Finally, we evaluate the effect of fading and mobility on distributed BRAND. For this set of experiments we use the random waypoint mobility model and consider two levels of maximum speed: 5m/s and 15 m/s, corresponding to pedestrian and vehicle movement, respectively. The routing tables are updated once a minute, as is the case for popular routing protocols like OLSR. In addition we add Rayleigh fading. As the data in Figure 9 shows, for static topologies, where the only source of error is channel fading, BRAND is accurate. When the mobility is introduced the accuracy starts to drop although the drop is limited at pedestrian speeds. As is to be expected, at vehicular speed the errors start becoming significant and we do not recommend using BRAND in this context.

G. R-BRAND: Admission Control for Time-Sensitive Applications

Finally, in the following experiment we evaluate the performance of R-BRAND.

Method: The analysis is performed on 64kbps voice call flows with RTP packets sent once every 20ms. We carried out the experiments on 4-hop paths with TDMA frame size S=32 slots and buffers of size K=16. The duration of every time-slot was set to 0,625ms. All the links operated on data rates almost equaling 2Mbps. We compare the estimation for the the end-to-end delay given by R-BRAND with the average of what is observed over 5 simulation runs of 20-second duration.

Results: Figure 10 depicts the average end-to-end delay achieved by the RTP packets as a function of the number of flows admitted end-to-end by R-BRAND (packet delivery ratio > 95%). The data shows that R-BRAND is capable of performing delay-based admission control -its computation of end-to-end delay closely resembles what was observed during the simulations.

VIII. CONCLUSION

In this paper, we revisited the problem of admission control for the cognitive radio context. With the problem NP-Complete, we relaxed the requirement for exact end-to-end bandwidth and replaced it with a quest for an average endto-end bandwidth using randomized scheduling. We solved analytically the problem of estimating the average throughput with randomized scheduling by introducing the concepts of l-link available slots partition and clique sliding, reducing the calculation complexity from exponential to linear. The solution was used as vehicle for BRAND, an algorithm for computing the average available bandwidth of a given source, destination pair. A thorough numerical analysis demonstrated the correctness of BRAND as well as its capability to accurately take into account the cognitive radio context, in particular the Primary User and multi-rate links. The distributed version of BRAND was shown to deliver almost 100% admission rate in a variety of conditions, thus, validating our choice to work with the relaxed version of the admission control problem. Finally, we introduced a version of BRAND tailored for timesensitive applications and showed that it can perform delaybased admission control.

Fig. 1 .

 1 Fig.1. On a 3-hop path, a given slot can belong to one of the 8 possible slot sets: E 1,2,3 (set of slots available for allocation on all 3 links), E 1,2,3 (set of slots available to none of the links),E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 .When an allocation takes place on l 1 , the proportion of the slots allocated, p 1 , (area painted in gray) is transferred from the sets E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 to E 1,2,3 to account for the interference. The same is repeated for the allocations on l 2 and l 3 . The challenge is estimating the size of the "gray" (or, equivalently, "white") areas in every set after each allocation. (a) Initial state of the available slots partition. (b) After allocation on the first link. (c) After allocation on the second link. (d) After allocation on the third link.

  Fig.1. On a 3-hop path, a given slot can belong to one of the 8 possible slot sets: E 1,2,3 (set of slots available for allocation on all 3 links), E 1,2,3 (set of slots available to none of the links),E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 .When an allocation takes place on l 1 , the proportion of the slots allocated, p 1 , (area painted in gray) is transferred from the sets E 1,2,3 , E 1,2,3 , E 1,2,3 , E 1,2,3 to E 1,2,3 to account for the interference. The same is repeated for the allocations on l 2 and l 3 . The challenge is estimating the size of the "gray" (or, equivalently, "white") areas in every set after each allocation. (a) Initial state of the available slots partition. (b) After allocation on the first link. (c) After allocation on the second link. (d) After allocation on the third link.

16 :

 16 d3 ← min d2, a3 × φ 3 ×f 3

5 5 and p 2

 552 are allocated by links l 1 and l 2 , respectively. Due to the nature of the interference, when updating the sets resulting from the 3-hop available slots partition related to clique 3, on average p 1 . C (1 -p 1 ).C

  ,3,4,5 + p 2 .C (1) 1,2,3,4,5 to the set E (1) 3,4,5 .

Fig. 3 .

 3 Fig. 3. The model for estimating the end-to-end delay.

Fig. 4 .

 4 Fig. 4. Available end-to-end bandwidth values computed by BRAND and KODIALAM as function of the optimal values, obtained by using lpsolve to solve the integer linear program.

Fig. 7 .

 7 Fig. 7. The presence of multi-rate links and primary users does not affect BRAND's accuracy. Ignoring them, however, leads to significant errors, as high as 900%, when calculating the available end-to-end bandwidth. (a) Multiple-Transceivers, Multiple-Rates, u=10%. (b) Multiple-Transceivers, Multiple-Rates, u=20%. (c) Multiple-Transceivers, Multiple-Rates, u=50%.

Fig. 8 .

 8 Fig. 8. Sensing error of x% means the sensing module underestimates the PU activity by x%. Every point is an average across all sessions in the network.For the most part, distributed BRAND deals well with sensing errors, even when those errors reach 30%.

Fig. 9 .

 9 Fig. 9. Performance of distributed BRAND with mobility, channel fading and multiple concurrent flows.

Fig. 10 .

 10 Fig. 10. End-to-end delay as a function of the number of admitted flows. A larger number of admitted flows means there was more available capacity initially, resulting in smaller end-to-end delays.

TABLE I THE

 I MAIN NOTATIONS USED IN THE PAPERprimary user activity, the available bandwidth is equivalent to the maximum path bandwidth.

We refer to non-cognitive architectures as legacy.

We will use the terms primary user/secondary user, primary/secondary and PU/SU interchangeably.

We assume that if a secondary can sense a primary user then the particular secondary is in the interference range of the primary user.

We use the terms clique and interference-clique interchangeably.

A simple heart-beat protocol can give every node the quantities φ, f, p, A for all links in the two-hop neighborhood.

Tail delay would be a better metric for admission control of real-time traffic. However, considering the difficulty of computing it, we relax the problem and work with average delay.

We use the notations from TableI.

Algorithm 2 shows the solution. To make the problem tractable, we relax it by recasting Equations 6-8 (Section IV-A) to use average values while maintaining the same notations. In addition, although mathematically speaking E[a 3 ] = min E[r 3 ], E[A [START_REF]Evaluation of the Performance of Prototype TV-Band White Space Devices[END_REF] 3 ] , we do such an approximation to reduce the calculation complexity. As shown in Section VII, this approximation does not degrade the performance of the overall estimation process. output : a1, a2, a3, d1, d2, d3 1 : begin //The cardinalities of the 8 sets resulting from the available slots partition.

:

C

1,2,3 , C

1,2,3 , C

1,2,3 , C

1,2,3 , C

1,2,3 , C

1,2,3 , C

1,2,3 , C

1,2,3 ; //Allocation on l1

;

A

1,2,3 ); //Allocation on l2

2 ); p2 ← a2/A

(2) 2 ;

13 :

1,2,3 + (1 -p1).C a3 ← min (r3, A Transmit (avail_BW, BP.sourceID); Transmit (BP, next_hop); BRAND's interference-clique sliding approach (Section IV- C) is what makes it amenable to a distributed computation, for two reasons. The computation at every step requires only knowledge of the interference clique at hand and the three reduction factors, α, resulting from the computation on the

VII. PERFORMANCE EVALUATION OF BRAND

In this section, we evaluate BRAND numerically using MATLAB and compare it with the work of Zhu and Corson [START_REF] Zhu | QoS routing for mobile ad hoc networks[END_REF] and Kodialam and Nandagopal [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF].

A. Simulation Parameters

Nodes implement a TDMA MAC with a 50 ms frame comprising 40 time slots. The frame is divided into a control part, for slot scheduling, and data transmission part. During the control period, a node broadcasts beacons containing information regarding its own allocations and that of its one-hop neighbors, allowing all nodes to eventually acquire two-hop information. 20% of every data transmission slot is dedicated to sensing and the rest to data transmissions. As the specific spectrum assignment process is beyond the scope of this paper, we simply use the following probabilistic model to select the assigned channel for each communication link: P[channel1] = 0.80, P[channel2] = 0.10, P[channel3] = 0.05 and P[channel4] = 0.05.

In practice, link rates depend on the local environment and may fluctuate with time. To approximate this behavior, we sample every link rate φ i according to a normal distribution with mean µ φ and standard deviation σ φ where µ φ is the mean link transmission rate on the corresponding assigned channel and σ φ is taken proportional to µ φ . In all the simulation results presented here σ φ = µ φ × 0.10. For the channels considered, we choose: µ φ (channel1) = 2Mbps, µ φ (channel2) = 1.5Mbps, µ φ (channel3) = 800kbps and µ φ (channel4) = 250kbps. According to the corresponding cumulative distribution function, the generated transmission rates for µ φ = 2000kbps and σ φ = 400kbps oscillate between 1000kbps and 3000kbps.

BRAND Parameters: BRAND calculates the available endto-end bandwidth by computing the average end-to-end throughput realized over all possible demands and returning the highest value. In this evaluation, the demand values are taken in the range I d = [0, min (φ 1 , φ 2 , . . . , φ NH )] (kbps) with step ∆ φ = 10kbps.

Basis for Comparison: To the best of our knowledge, there is no other work that tackles the problem of computing the available end-to-end bandwidth for a cognitive radio network. The closest to our work is that by Zhu and Corson [START_REF] Zhu | QoS routing for mobile ad hoc networks[END_REF], which computes the available bandwidth for legacy TDMA multihop network. Furthermore, we use the algorithm proposed by Kodialam and Nandagopal [START_REF] Kodialam | Characterizing the capacity region in multi-radio multi-channel wireless mesh networks[END_REF] and the optimal solution obtained by solving the integer linear program with lpsolve [START_REF] Berkelaar | telecommunications and networks from INP Toulouse, France, in 2011 and 2015[END_REF] as benchmarking tools.

B. End-to-End Bandwidth With BRAND

We perform the following experiment for comparing BRAND to KODIALAM and the optimal. We choose the values of no secondary interference, p a , for every link uniformly at random in (0, 1) and generate PSAT tables for various path sizes. We run BRAND and KODIALAM in MATLAB using these PSAT tables and compute the available end-to-end bandwidth for different values of primary Systems Engineer with Rockwell Collins, France, from 2011 to 2014, where he conducted research in software defined radio networks. He was a member of the IRIT and LIP research laboratories, France, from 2015 to 2016. He is currently a Research Engineer with Sysoco Group, France. His current research interests concern networking technologies with an emphasis on the performance evaluation and design of multimedia wireless communications systems, including cognitive radio and mission-critical LTE.

Gentian