Distributed Approximation Algorithms for Spectrum Allocation in Wireless ad Hoc Networks

详细信息    查看全文

• 作者：Yalin Shi ; Jian Chen ; Limin Wang ; Ming Chen…
• 关键词：Distributed approximation scheme ; Spectrum allocation ; Roman dominating set ; Unit ball graph ; Growth ; bounded graph
• 刊名：Mobile Networks and Applications
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：21
• 期：6
• 页码：962-973
• 全文大小：1,851 KB
• 刊物类别：Computer Science
• 刊物主题：Computer Communication Networks
  Electronic and Computer Engineering
  Business Information Systems
  
• 出版者：Springer Netherlands
• ISSN：1572-8153
• 卷排序：21

文摘

Spectrum allocation is a difficult and hot issue in wireless ad hoc networks. An efficient method of spectrum allocation is a key factor to improve quality of service and performance of wireless networks. In this paper, we consider the spectrum allocation problem which asks how to allocate the least number of spectrum blocks in a field to ensure the service on any random k locations simultaneously. Our solution to the spectrum allocation problem is the minimum k-Roman dominating set. We propose two distributed algorithms for the issue of spectrum allocation in wireless ad hoc networks. One is a distributed 6k-approximation algorithm for the spectrum allocation of satisfying any random k (k ≥ 2) locations in the class of unit ball graphs. The other one is a better distributed algorithm for finding a (1 + ε)-approximation for the spectrum allocation problem of serving any random two locations, in the class of growth-bounded graphs. We also describe the simulation results and analyze them.