To serve the peak trac demand, Wi-Fi networks that consist of a high-density access points (APs) have been deployed. Dense Wi-Fi networks incur two critical problems, energy waste and interference. In this paper, we solve these problems throughout optimized management of operation mode (on/of) of APs and user association according to traffic demand. We propose the rounding algorithm based on linear programming (LP) to minimize the average power consumption of APs while ensuring coverage of the active users and avoiding interference. We provide the theoretical performance guarantee of our algorithm in terms of approximation ratio and polynomial complexity. Moreover, in our simulations, the suggested algorithm shows near-optimal performance with very short run time. In other words, we suggest a promising solution even in practice as theory promises. To our best knowledge, we are the first to theoretically solve the energy eciency and interference problem in Wi-Fi networks at the same time.
최근 통계자료에 의하면 Wi-Fi AP의 개수가 약 1억 6천 7백만개에 달할 정도로 과거에 비해 기하급수적으로 증가하고 있다. 여기서 중요한 현상은 절대적인 양만 증가하는 것이 아니라 AP들이 peak time때의 트래픽을 수용하기 위하여 밀집되어 분포되고 있다는 것이다. 이런 밀집된 Wi-Fi 네트워크는 불필요한 에너지 낭비와 AP간의 간섭이라는 2가지 문제를 야기하였다. 먼저 대부분의 AP가 항상 켜져 있기 때문에 peak time때가 아닐 때의 AP들은 불필요하게 많은 에너지를 낭비하게 된다. 또한 간섭문제를 발생시키지 않는 Non-overlapping 채널의 개수가 2.4GHz 대역에서는 4개에 불과할 정도로 매우 부족하기 때문에 밀집된 WI-FI 환경은 심각한 간섭문제를 야기하게 된다.
이러한 문제를 해결하기 위해, 본 학위 논문에서는 각 AP들이 중앙 컨트롤러에 연결되어 동작하는 모델 하에서 Wi-Fi AP의 on/off control과 유저 association control 기법을 제안한다. 먼저 간섭 문제를 피하면서도 throughput을 최대화 할 수 있는 AP들을 greedy하게 선택하는 알고리즘을 통해 어떤 AP를 켜고 끌지를 결정하게 된다. 그 다음으로는 선택된 AP들의 집합 위에서 유저들을 최대한 효율적으로 assign할 수 있는 알고리즘을 통해 자원을 가장 효율적으로 사용 할 수 있는 유저 association을 결정하게 된다. 제안된 알고리즘은 문제의 제약조건을 모두 만족하면서도 polynomial time안에 끝날 수 있는 형태로 제안되었다. 또한 수학적인 증명을 통해 worst case에서도 최적의 솔루션 대비 어떤 approximation ratio를 가지는 지를 증명하였다.
본 학위 논문에서는 다양한 성능 비교를 통해, 제안하는 방법의 성능을 검증 하였다. 첫째, 작은 규모의 테스트 환경에서 모든 가능한 조합을 검색하여 최적의 솔루션을 찾는 알고리즘과 비교 했을 때, 빠르게 동작하면서도 최적의 솔루션에 근접하는 성능을 보임을 검증하였다. 둘째, 큰 규모의 테스트 환경에서 쉽게 생각할 수 있는 비교 알고리즘 대비 약 20% 높은 성능을 내는 것을 검증하였다. 이러한 결과는 제안한 방법이 단순히 이론적인 성능 보장만을 하는 것이 아니라 실제로도 잘 동작할 것을 보여주는 결과라고 볼 수 있다.
