Advances in cognitive radio networks: A survey <s> I. Routing in a CR Network <s> This paper studies a fundamental problem in dynamic spectrum access (DSA) networks: given a set of detected spectrum bands that can be temporarily used by each node in a DSA network, how to form a topology by selecting spectrum bands for each radio interface of each node, called topology formation in this paper. We propose a novel layered graph to model the temporarily available spectrum bands, called spectrum opportunities (SOPs) in this paper, and use this layered graph model to develop effective and efficient routing and interface assignment algorithms to form near-optimal topologies for DSA networks. We have evaluated the performance of our layered graph approach and compared it to a sequential interface assignment algorithm. The numerical results show that the layered graph approach significantly outperforms the sequential interface assignment <s> BIB001 </s> Advances in cognitive radio networks: A survey <s> I. Routing in a CR Network <s> In a cognitive radio (CR) network, MAC-layer configuration involves determining a common set of channels to facilitate communication among participating nodes. Further, the availability of multiple channels and frequent channel switches add to the complexity of route selection. Knowledge of the global network topology can be used to solve the above-described problems. In this paper, we propose a distributed algorithm for gathering global network topology information for a CR network. We outline approaches that utilize the gathered topology information for MAC-layer configuration and efficient routing of packets. In addition, situation awareness is achieved by sharing the physical location information among the nodes in the network. The proposed algorithm determines the global network topology in O(N2 ) timeslots, where N is the maximum number of nodes deployed. With 80 available channels for communication, the algorithm terminates within 0.8 second <s> BIB002 </s> Advances in cognitive radio networks: A survey <s> I. Routing in a CR Network <s> Efficient spectrum allocation in dynamic spectrum systems is a challenging problem, particularly for multi-hops transmissions. The inter-dependence between route selection and spectrum management makes it important to examine interaction between the two and the corresponding performance and com- plexity tradeoffs. In this paper, we explore two design method- ologies: a decoupled design where these tasks are carried out independently by different protocol layers, and a collaborative design that integrates them into a single task. Experimental results show that the collaborative design, if well-provisioned, offers significant performance improvement compared to the decoupled design. I. INTRODUCTION <s> BIB003 </s> Advances in cognitive radio networks: A survey <s> I. Routing in a CR Network <s> This paper addresses the problem of spectrum-aware data-adaptive routing in multi-channel, single-radio (MC-SR) multi-hop dynamic spectrum access (DSA) networks. We develop a scalable and simple to implement data-adaptive routing scheme that routes varied amounts of data from a given source to a destination through fast routes. For a given amount of data, our routing scheme takes into account the capacity (per unit of time) of the links, the available spectrum, the link disruption probabilities as well as the link propagation time between nodes. We model our routing problem as a combinatorial optimization task with two objectives. Our solution methodology generates Pareto optimal paths in polynomial time as there do not exist paths in general which optimize both objectives simultaneously. We generalize our routing method for broadcasting and multicasting scenarios. To the best of our knowledge this work is the first analytical treatment of the problem of spectrum-aware routing in DSA networks. <s> BIB004 </s> Advances in cognitive radio networks: A survey <s> I. Routing in a CR Network <s> Routing in multi-hop cognitive radio net- works(CRN) should consider how to dynamically switch frequency band for either per flow throughput guarantee or global spectrum utilization. Previous research have offered both centralized and distributed solutions on combining the two, but since different nodes may sense different spectrum availability, efficiently sharing this information in the dynamic spectrum environment still remains challenging. In this paper, we propose an approach to reactively initiate route computing and frequency band selection. We further present a novel multi-flow multi-frequency scheduling scheme for single node to relief the multi-flow interference and frequent switching delay. We use cumulative delay along the path for evaluation, simulation results show that, comparing to other typical approaches, our protocol provides better adaptability to the dynamic spectrum and multi-flow environment, and incurs much lower cumulative delay. <s> BIB005 </s> Advances in cognitive radio networks: A survey <s> I. Routing in a CR Network <s> This paper argues for the need to address the issue of multi-channel network performance under constraints on channel switching. We present examples from emergent directions in wireless networking to motivate the need for such a study, and introduce some models to capture channel switching constraints. For some of these models, we study connectivity and capacity of a wireless network comprising n randomly deployed nodes, equipped with a single interface each, when there are c=O(logn) channels of equal bandwidth W/c available. We consider an adjacent (c,f) channel assignment where a node may switch between f adjacent channels, but the adjacent channel block is randomly assigned. We show that the per-flow capacity for this channel assignment model is Theta(Wradic(f/cnlogn)). We then show the adjacent (c,2) assignment maps to the case of untuned radios. We also consider a random (c,f) assignment where each node may switch between a pre-assigned random subset of f channels. For this model, we prove that per-flow capacity is O(Wradic(prnd/nlogn)) (where prnd=1-(1-f/c)(1-f/(c-1))...(1-f/(c-f+1)) and Omega(Wradic(f/cnlogn))). <s> BIB006 </s> Advances in cognitive radio networks: A survey <s> I. Routing in a CR Network <s> We present a novel routing approach for multichannel cognitive radio networks (CRNs). Our approach is based on probabilistically estimating the available capacity of every channel over every CR-to-CR link, while taking into account primary radio (PR). Our routing design consists of two main phases. In the first phase, the source node attempts to compute the most probable path (MPP) to the destination (including the channel assignment along that path) whose bandwidth has the highest probability of satisfying a required demand D. In the second phase, we verify whether the capacity of the MPP is indeed sufficient to meet the demand at confidence level delta. If that is not the case, we judiciously add channels to the links of the MPP such that the augmented MPP satisfies the demand D at the confidence level delta. We show through simulations that our protocol always finds the best path to the destination, achieving in some cases up to 200% improvement in connection acceptance rate compared to the traditional Dijkstra. <s> BIB007
In traditional wireless networks, all network nodes will be provided with a certain fixed spectrum band for use. For instance, WLAN uses 2.4 and 5 GHz bands, and GSM uses 900 and 1800 MHz bands. In DSA networks, however, there may be no such pre-allocated spectrum that can be used by every node at any time, and the frequency spectrum that can be used for communication may vary from node to node. This new feature of DSA network imposes even greater challenges on wireless networking, especially on routing. If two neighboring nodes do not have a common channel, or they have common channels but do not tune to the same frequency, then multi-hop communication will be infeasible. Thus, new routing algorithms are needed to accommodate the spectrum dynamics and ensure satisfying network performance such as high network capacity and throughput, short latency and low packet loss. Due to the heterogeneity of spectrum availability among nodes, routing problem can not be well solved without considering the spectrum allocation. In BIB003 , the inter-dependence between route selection and spectrum management is studied, where the network layer selects the packet route as well as decides a time schedule of a conflict-free channel usage. In BIB001 , the topology formation and routing in DSA networks is studied. DSA network nodes first identify spectrum opportunities by detection, and then the detected spectrum opportunities are associated to the radio interfaces of each node. A layered graph model is proposed to help assign the spectrum opportunities to the radio interfaces. A MAC-layer configuration algorithm is proposed BIB002 , which enables nodes to dynamically discover the global network topology and node location, and identify common channels for communication. New routing metrics are introduced BIB002 , BIB004 , such as the number of channel switches along a path, frequency of channel switches on a link, and switching delay BIB002 . Spectrum-aware on-demand routing protocol is proposed in BIB005 , which select routes according to the switching delay between channels and the backoff delay within a channel. A probabilistic path selection approach is proposed for a multi-channel CR network BIB007 . The source node first computes the route that has the highest probability to satisfying a required demand, and then verifies whether the capacity of the potential path indeed meets the demand. If not, extra channels are judiciously added to the links of the route until the augmented route satisfies the demand at a confidence level. Considering the channel switching constraints due to primary users' activity, BIB006 proposes analytical models for channel assignment in a general multi-hop CR network, studies the impact of the constraints on network performance, and investigates the connectivity and transport capacity of the network.