Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

Better Analysis of Lower Bounds of Frequency Assignment Problems in Wireless Networks with Cellular Topology

셀룰러 위상구조 무선망에서의 주파수 할당 문제의 향상된 하한 값 분석

  • 이상규 (숙명여자대학교 컴퓨터과학과) ;
  • 이주영 (덕성여자대학교 인터넷 정보공학)
  • Published : 2006.10.15
Download PDF
⟨ Previous Next ⟩

Abstract

Because of its exponential growth of data and voice transmissions through wireless communications, efficient resource management became more important factor when we design wireless networks. One of those limited resources in the wireless communications is frequency bandwidth. As a solution of increasing reusability of resources, the efficient frequency assignment problems on wireless networks have been widely studied. One suitable approach to solve these frequency assignment problems is transforming the problem into traditional graph coloring problems in graph theory. However, most of frequency assignments on arbitrary network topology are NP-Complete problems. In this paper, we consider the Chromatic Bandwidth Problem on the cellular topology wireless networks. It is known that the lower bound of the necessary number of frequencies for this problem is $O(k^2)$. We prove that the lower bound of the necessary number of frequencies for the Chromatic Bandwidth Problem is $O(k^3)$ which is tighter lower bound than the previous known result.

데이타 및 음성 등의 통신에서 무선 통신의 비중은 날로 증가하고 있다. 그러나 무선 통신에서는 유선통신에 비해 여러 가지 자원의 제약을 받는다. 컴퓨터, PDA, 이동통신기기 등 급격히 증가하는 무선 단말기의 증가에 따른 통신량 수요를 충족하기위해 제한된 자원을 보다 효율적으로 사용해야 한다. 무선 통신에 있어 효율성이 필요한 자원중의 하나가 주파수 이다. 효율적 주파수 사용을 위한 주파수 할당 문제에 관한 연구는 현재 활발히 진행되고 있다. 그러나 대부분의 주파수 할당 문제가 NP-Complete의 어려운 문제로 실험적 연구를 통한 접근과 함께 이에 대한 이론적 이해 또한 필요하다. 주파수 할당 문제의 이론적 연구 중 셀룰러 위상구조에서의 크로마틱 대역폭 문제의 하한 값이 $O(k^2)$로 알려져 있다. 본 논문에서는 셀룰러 위상구조에서의 크로마틱 대역폭 주파수 할당 문제의 하한 값으로 기존에 알려진 $O(k^2)$보다 향상된 하한 값 $O(k^3)$을 제시하여, 주파수 할당 문제의 보다 정확한 이론적 이해를 제시하였다.

Keywords

References

  1. A. Sen, T. Roxborough and S. Medidi, 'Upper and Lower bounds of a Class of Channel Assignment Problems in Cellular Networks,' Proc. of IEEE INFOCOM '98, San Francisco, April 1998 https://doi.org/10.1109/INFCOM.1998.662943
  2. M.Duque-Anton, D.Kunz and B.Ruber, 'Channel Assignment for Celluler Radio Using Simulated Annealing,' IEEE Transactions on Vehicular Technology, Vol. 42, No. 1, pp.14-21, Feb 1993 https://doi.org/10.1109/25.192382
  3. S. Jordan and E.J, Schwabe. 'Worst-case Performance of Cellular Channel Assignment Policies,' Wireless Networks, Vol. 2, No 4, pp.265-275, 1996 https://doi.org/10.1007/BF01262046
  4. D.Kunz, 'A Graph Theoretic Approach for Channel Assignment In Cellular Networks,' Wireless Networks, Vol. 7, No. 6, pp. 567-574, Nov. 2001 https://doi.org/10.1023/A:1012359132263
  5. K.K. Leung and B.J. Kim, 'Frequency Assignment for IEEE 802.11 Networks,' Proc. of IEEE Veh. Tech. Conf. Oct. 2003 https://doi.org/10.1109/VETECF.2003.1285259
  6. D. Tcha, Y. Chung and T. Choi, 'A New Lower Bound for the Frequency Assignment Problem,' IEEE/ACM Transactions on Networking, Vol. 5, No. 1, pp. 34-39, Feb 1997 https://doi.org/10.1109/90.554720
  7. D.B. West, 'Introduction to graph theory,' Prentice-Hall, 1996
  8. T.R. Gensen and B. Toft, 'Graph coloring problems,' Wiley-interscience, New York, 1995
  9. B. Raman, 'Channl Allocation in 802.11-based Mesh Networks,' Proc. of IEEE INFOCOM '06, April 2006 https://doi.org/10.1109/INFOCOM.2006.317
  10. H. Ju and I. Rubin, 'Mesh Topology Construction for Interconnected Wireless LANs,' Proc. of IEEE INFOCOM '06, April 2006