ROSA: distributed joint routing and dynamic spectrum allocation in cognitive radio ad hoc networks

ABSTRACT

Throughput maximization is one of the main challenges in cognitive radio ad hoc networks, where local spectrum resources may change from time to time and hop-by-hop. For this reason, a cross-layer opportunistic spectrum access and dynamic routing algorithm for cognitive radio networks is proposed, called ROSA (ROuting and Spectrum Allocation algorithm). Through local control actions, ROSA aims at maximizing the network throughput by performing joint routing, dynamic spectrum allocation, scheduling, and transmit power control. Specifically, the algorithm dynamically allocates spectrum resources to maximize the capacity of links without generating harmful interference to other users while guaranteeing bounded BER for the receiver. In addition, the algorithm aims at maximizing the weighted sum of differential backlogs to stabilize the system by giving priority to higher-capacity links with high differential backlog. The proposed algorithm is distributed, computationally efficient, and with bounded BER guarantees. ROSA is shown through discrete-event packet-level simulations to outperform baseline solutions leading to a high throughput, low delay, and fair bandwidth allocation.

REFERENCES

• 1: I. F. Akyildiz, W.-Y. Lee, and K. Chowdhury. CRAHNs: Cognitive Radio Ad Hoc Networks. Ad Hoc Networks Journal (Elsevier), 7(5):810--836, Jul. 2009.
• 2: I. F. Akyildiz, W.-Y. Lee, M. C. Vuran, and S. Mohanty. NeXt Generation/Dynamic Spectrum Access/Cognitive Radio Wireless Networks: A Survey. Computer Networks Journal(Elsevier), 50:2127--2159, Sept. 2006.
• 3: V. Brik, E. Rozner, S. Banerjee, and P. Bahl. DSAP: A Protocol for Coordinated Spectrum Access. In IEEE Intl. Symp on New Frontiers in Dynamic Spectrum Access Networks (DySPAN), Nov. 2005.
• 4: D. Cabric, S. M. Mishra, and R. W. Brodersen. Implementation Issues in Spectrum Sensing for Cognitive Radios. In Conference Record of the 38th Asilomar Conference on Signals, Systems and Computers, volume 1, pages 772--776, Nov. 2004.
• 5: L. Cao and H. Zheng. SPARTA: Stable and Efficient Spectrum Access in Next Generation Dynamic Spectrum Networks. In Proc. of IEEE Intl. Conf. on Computer Communications (INFOCOM), pages 870--878, Apr. 2008.
• 6: G. Cheng, W. Liu, Y. Li, and W. Cheng. Joint On-demand Routing and Spectrum Assignment in Cognitive Radio Networks. In IEEE Intl. Conf. on Communications(ICC), pages 6499--6503, Jun. 2007.
• 7: M. Chiang, S. Low, A. Calderbank, and J. Doyle. Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures. Proceedings of the IEEE, 95(1):255--312, Jan. 2007.
• 8: F. Cuomo, C. Martello, A. Baiocchi, and F. Capriotti. Radio Resource Sharing for Ad-hoc Networking with UWB. IEEE Journal on Selected Areas in Communications, 20(9):1722--1732, Dec. 2002.
• 9: A. Eryilmaz and R. Srikant. Joint Congestion Control, Routing, and MAC for Stability and Fairness in Wireless Networks. IEEE Journal on Seclected Areas in Communications, 24(8):1514--1524, Aug. 2006.
• 10: S. Gandhi, C. Buragohain, L. Cao, H. Zheng, and S. Suri. A General Framework for Wireless Spectrum Auctions. In IEEE Intl. Symp on New Frontiers in Dynamic Spectrum Access Networks (DySPAN), Apr. 2007.
• 11: L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource Allocation and Cross-layer Control in Wireless Networks. Found. Trends Netw., 1(1):1--144, 2006.
• 12: P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Trans. on Information Theory, 46(2):388--404, Mar. 2000.
• 13: Y. T. Hou, Y. Shi, and H. D. Sherali. Optimal spectrum sharing for multi-hop software defined radio networks. In Proc. of IEEE Intl. Conf. on Computer Communications (INFOCOM), May 2007.
• 14: D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In T. Imielinski and H. Korth, editors, Mobile Computing, pages 153--181. Kluwer Academic Publishers, 1996.
• 15: H. Khalife, S. Ahuja, N. Malouch, and M. Krunz. Joint Routing and Spectrum Selection for Multihop Cognitive Radio Networks. Technical Report, UPMC - Paris 6, 2008.
• 16: X. Lin, N. Shroff, and R. Srikant. A tutorial on cross-layer optimization in wireless networks. IEEE Journal on Selected Areas in Communications, 24(8):1452--1463, Aug. 2006.
• 17: K. Liu and Q. Zhao. A Restless Bandit Formulation of Opportunistic Access: Indexablity and Index Policy. In Proc. of the 5th IEEE Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON) Workshops, Jun. 2008.
• 18: T. Melodia and I. F. Akyildiz. Cross-layer Quality of Service Support for UWB Wireless Multimedia Sensor Networks. In Proc. of IEEE Intl. Conf. on Computer Communications (INFOCOM), Mini-Conference, Apr. 2008.
• 19: J. Mitola and G. Maguire. Cognitive Radio: Making Software Radios More Personal. IEEE Personal Communications, 6:13--18, Aug. 1999.
• 20: I. N. Psaromiligkos and S. N. Batalama. Rapid Combined Synchronization/Demodulation Structures for DS-CDMA Systems - Part II: Finite data record performance analysis. IEEE Transactions on Communications, 51:1162--1172, Jul. 2003.
• 21: I. N. Psaromiligkos, S. N. Batalama, and M. J. Medley. Rapid Combined Synchronization/Demodulation Structures for DS-CDMA Systems - Part I: Algorithmic developments. IEEE Transactions on Communications, 51:983--994, Jun. 2003.
• 22: L. Tassiulas and P. P. Bhattacharya. Allocation of Interdependent Resources for Maximal Throughput. Stochastic Models, 16(1), 2000.
• 23: L. Tassiulas and A. Ephremides. Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks. IEEE Transactions on Automatic Control, 37(12):1936--1948, Jan. 1992.
• 24: Q. Wang and H. Zheng. Route and Spectrum Selection in Dynamic Spectrum Networks. In IEEE Consumer Communications and Networking Conference (CNCC), Jan. 2006.
• 25: C. Xin, B. Xie, and C.-C. Shen. A novel layered graph model for topology formation and routing in dynamic spectrum access networks. In IEEE Intl. Symp on New Frontiers in Dynamic Spectrum Access Networks (DySPAN), pages 208--317, Nov. 2005.
• 26: Y. Yuan, P. Bahl, R. Chandra, P. A. Chou, J. I. Ferrell, T. Moscibroda, S. Narlanka, and Y. Wu. KNOWS: Kognitiv Networking Over White Spaces. In IEEE Intl. Symp on New Frontiers in Dynamic Spectrum Access Networks (DySPAN), Apr. 2007.
• 27: Y. Yuan, P. Bahl, R. Chandra, T. Moscibroda, and Y. Wu. Allocating dynamic time-spectrum blocks in cognitive radio networks. In Proc. of ACM Intl. Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc), pages 130--139, New York, NY, USA, 2007.
• 28: X. Zhou, S. Gandi, S. Suri, and H. Zheng. eBay in the Sky: Strategy-Proof Wireless Spectrum Auctions. In ACM Intl. Conf. on Mobile Computing and Networking (MobiCom), Sept. 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design

Keywords:
cognitive radio networks, cross-layer design, dynamic spectrum allocation, routing