Spectrum auction framework for access allocation in cognitive radio networks

ABSTRACT

Cognitive radio networks are emerging as a promising technology for the efficient use of radio spectrum. In these networks, there are two categories of networks on different channels: primary networks and secondary networks. A primary network on a channel has prioritized access to the channel and secondary networks can use the channel when the primary network is not using it. The access allocation problem is to select the primary and secondary networks on each channel. We develop an auction-based framework that allows networks to bid for primary and secondary access based on their utilities and traffic demands, and uses the bids to solve the access allocation problem. We develop algorithms for the access allocation problem and show how they can be used either to maximize the auctioneer's revenue given the bids, or to maximize the social welfare of the bidding networks, while enforcing incentive compatibility. We first consider the case when the bids of a network depend on which other networks it will share channels with. When there can be only one secondary network on a channel, we design an optimal polynomial-time algorithm for the access allocation problem based on reduction to a maximum matching problem in weighted graphs. When there can be two or more secondary networks on a channel, we show that the optimal access allocation problem is NP-Complete. Next, we consider the case when the bids of a network are independent of which other networks it will share channels with. We design a polynomial-time dynamic programming algorithm to optimally solve the access allocation problem when the number of possible cardinalities of the set of secondary networks on a channel is upper-bounded. Finally, we design a polynomial-time algorithm which approximates the access allocation problem within a factor of 2 when the above upper bound does not exist.

REFERENCES

• 1: Q. Zhao and B. Sadler "A Survey of Dynamic Spectrum Access", IEEE Signal Processing Magazine, Vol. 24, Issue 3, pp. 79--89, 2007.
• 2: FCC Spectrum Policy Task Force "Report of the Spectrum Efficiency Working Group", Nov. 2002. Available at: http://www.fcc.gov/sptf/reports.html
• 3: FCC Auctions http://wireless.fcc.gov/auctions/
• 4: Ian F. Akyildiz , Won-Yeol Lee , Mehmet C. Vuran , Shantidev Mohanty, NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.13, p.2127-2159, 15 September 2006 [doi>10.1016/j.comnet.2006.05.001]
• 5: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 6: Z. Ji, K.J. Ray Liu, "Belief-Assisted Pricing for Dynamic Spectrum Allocation in Wireless Networks with Selfish Users" In Proc. of IEEE SECON, 2006.
• 7: J. Huang, R. Berry, M. Honig "Auction Mechanisms for Distributed Spectrum Sharing" In Proc. of 42nd Allerton Conference, 2004.
• 8: S. Sengupta, M. Chatterjee "Sequential and Concurrent Auction Mechanisms for Dynamic Spectrum Access" In Proc. of CROWNCOM, 2007.
• 9: Sorabh Gandhi , Chiranjeeb Buragohain , Lili Cao , Haitao Zheng , Subhash Suri, Towards real-time dynamic spectrum auctions, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.4, p.879-897, March, 2008 [doi>10.1016/j.comnet.2007.11.003]
• 10: J. Peha, "Emerging Technology and Spectrum Policy Reform", In Proc. of ITU Workshop on Market Mechanisms for Spectrum Management, Jan. 2007.
• 11: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 12: Moshe Tennenholtz, Some Tractable Combinatorial Auctions, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.98-103, July 30-August 03, 2000
• 13: J. Edmonds "Maximum Matching and a Polyhedron with 0,1-Vertices", In Journal of Research of the National Bureau of Standards, 69B, 125--130, 1965.
• 14: L. White "A Parametric Study of Matchings and Coverings in Weighted Graphs" Ph.D. Dissertation, University of Michigan, Ann Arbor, 1967.
• 15: L. White, "An Efficient Algorithm for Maximum k-Matching in Weighted Graphs". In Proc. of 12th Allerton Conference on Circuits and Systems Theory, 1974.
• 16: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 17: A. Mas-Colell, M. Whinston and J. Green "Microeconomic Theory", Oxford University Press, 1995.
• 18: Jon Kleinberg , Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 19: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 20: Amir Ronen, Mechanism design with incomplete languages, Proceedings of the 3rd ACM conference on Electronic Commerce, p.105-114, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501170]

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, Economics, Theory

Keywords:
algorithms, cognitive radio networks, spectrum auctions