SINR-based Scheduling and Game Theoretic Off-loading in Wireless Networks

Abstract

지난 십여 년간 무선채널의 특별한 특성 때문에 무선네트워크에 관한 연구가 활발히 이루어졌다. 무선채널은 형태가 없고 어디에나 존재하는 모든 사용자에게 공유된 자원이다. 따라서 적절한 조절을 하지 못하면 그 성능에 큰 영향을 미칠 수 있다. 무선이라는 물리적인 특성 때문에 하위 계층일수록 기존의 유선 네트워크와 큰 차이를 보이는데, 무선 네트워크 연구 분야에서는 MAC 계층 프로토콜이나, 네트워크 계층의 라우팅 알고리즘, 또한 전송계층의 TCP/UDP 문제에 대해서도 많은 연구가 이루어졌다. 이중, 링크 스케쥴링 알고리즘은 무선 멀티홈 네트워크의 성능을 결정짓는데 가장 큰 걸림돌로써 오랫동안 연구되었다. 링크 스케쥴링 알고리즘은 중앙 집중 형태의 알고리즘에서부터 IEEE 802.11 CSMA를 활용한 분산적 알고리즘에 이르기까지 많은 알고리즘이 제안되었지만, 실제 무선의 특성인 간섭현상을 반영한 알고리즘에 대해서는 연구가 미미한 상태였다.

최근 많은 네트워크 통계 자료들은 무선네트워크 데이터 폭발 문제를 지적하고 있으며 근래에 폭발적으로 그 수요가 증가하는 스마트 기기들은 이러한 현상을 가속하고 있다. 특히, 이동하는 사용자에게도 일정 수준의 데이터 통신을 할 수 있도록 고안된 셀룰러 네트워크는 광범위한 통신 범위 덕분에 자원 사용량이 많고 공유자원이라는 무선의 특성 및 공간적 특성을 살리지 못하는 점 때문에 낮은 대역폭을 제공할 수밖에 없다. 따라서 점차 가속화될 셀룰러 네트워크에서의 데이터 폭발 문제는 한정된 무선 자원을 보다 효과적으로 사용하여 최대한 완화해야 한다. 본 학위 논문에서는 무선 네트워크 성능 향상을 위해 링크 스케쥴링 알고리즘과 셀룰러 네트워크의 통신량을 완화하는 기법을 제안한다.

첫째로, 무선 멀티홉 환경에서 SINR 기반의 분산적 스케쥴링 알고리즘을 제안하였다. 최근 무선 멀티홉 환경에서 고성능의 분산적 스케쥴링 알고리즘을 개발하는 문제는 많은 관심을 받고 있다. 특히나 수신 측에서 성공적으로 패킷을 수신하는데 SINR 한계치를 요구하는 물리적인 채널 모델에서의 스케쥴링 문제는 더욱 어려운 문제로 인식되고 있다. 이러한 SINR 모델에서의 전송 실패는 멀리 떨어져 있는 다른 노드의 동시 전송 때문에 생기는 방해 전파가 영향을 줄 수가 있는데, 이러한 현상은 분산적 기반의 알고리즘을 개발하는 데 있어 더욱 어려움을 준다. 이를 위해 제안한 DSS 기법은, CSMA 기법을 활용한 분산적 기반의 스케쥴링 알고리즘이며 최적의 처리량을 만족한다. 또한, 지연 시간 성능 향상을 위하여 실제 전송 스케쥴과 시스템 상태를 나누어 동작하게 하는 이중 상태 기법을 적용한 DSS-D를 제안하였다. 추가로 제어 시간의 오버헤드를 줄이기 위하여 p-persistence CSMA를 활용한 DSS-P도 제안하였으며 이 역시 최적의 처리량을 만족한다.

둘째로, 셀룰러 네트워크의 성능 향상을 위해 무선 데이터의 오프로딩을 위한 무선 임시 네트워크 통신 기법을 제안하였다. 무선 임시 네트워크 통신을 통한 오프로딩 기법은 셀룰러 네트워크에서 모바일 데이터 트래픽 폭발과 무선 자원의 부족 때문에 실용적인 솔루션으로 점점 주목받고 있다. 우리는 이러한 오프로딩 문제를 무선 네트워크를 사용하는 사용자들은 자신이 가진 데이터와 네트워크 자원을 제공하고 기지국에서는 최소 비용을 제시한 사용자를 선택하게끔 하는 베이지안 게임으로 모형화하였다. 차가 봉인 경매 이론을 활용하여 제안한 기법은 간단한 보상제도를 도입하여 네트워크 자원을 제공하는 사용자 및 기지국에 이득이 생기도록 하였으며, 제안한 기법이 내시균형을 만족하는 것을 보였다. 또한, 지하철 탑승객들의 통계 정보와 콘텐츠 시장에서의 데이터 다운로드 패턴을 활용한 성능평가를 시행하여 제안한 오프로딩 기법이 셀룰러 네트워크의 성능 향상에 도움을 주는 것을 확인하였다.

In recent decades, many researches in wireless networks have addressed extensively the issue of challenging characteristics of wireless channels. Wireless channel is incorporeal and exists everywhere; thus, it is a shared medium for every user. There could be serious performance degradation if the wireless resource is not controlled properly. It is clear that the lower layer has the more significant differences than the wired network because of the physical characteristics of wireless, and many studies have been performed in the field of MAC layer protocol, routing algorithm, and transport layer protocols such as TCP and UDP. Among them, it is well known that the scheduling in link layer is a major performance bottleneck in wireless multi-hop networks. In spite of many link scheduling algorithms proposed, from centralized approaches to distributed method based on IEEE 802.11 CSMA mechanism, research on scheduling algorithm reflecting physical interference model is insufficient.

Many of recent network statistics reports show that mobile data explosion problem will become more serious in the future, and that the recent explosion in demand for smart devices will accelerate this phenomenon even further. To support user mobility, a cellular technology was designed to provide broad communication coverage. However, the high transmission power it requires makes its energy consumption inefficiency. Current cellular technology could not provide enough bandwidth for each user because of low spatial reusability and shared medium property. Therefore, the mobile data explosion problem will be gradually accelerated, and we should mitigate this by utilizing the limited wireless resource more efficiently. In this dissertation, we have conducted researches to improve the performance of the wireless networks: link scheduling, and traffic off-loading.

First, we propose a distributed SINR based scheduling algorithms for multi-hop wireless networks. The problem of developing high-performance distributed scheduling algorithms for multi-hop wireless networks has seen enormous interest in recent years. The problem is especially challenging when studied under a physical interference model, which requires the SINR at the receiver to be above a certain threshold for decoding success. Under such an SINR model, transmission failure may be caused by interference due to simultaneous transmissions from far away nodes, which exacerbates the difficulty in developing a distributed algorithm. We propose a scheduling algorithm that exploits carrier sensing and show that the algorithm is not only amenable to distributed implementation, but also results in throughput optimality. Our algorithm has a feature called the dual-state approach, which separates the transmission schedules from the system state and can be shown to improve delay performance. To mitigate control mini-slot overhead, we further utilize p-persistence CSMA mechanism in our algorithm.

To enhance performance of the cellular networks, we propose ad hoc Wi-Fi communication for mobile data off-loading. As mobile data traffic explodes and signifies the scarcity of wireless resources in cellular networks, ad hoc wireless communications have increasingly attracted attention as a practical solution for traffic off-loading. We model the off-loading problem as a Bayesian game, where mobile users with the contents and Wi-Fi capability can participate in the game, and the base station will select the user who can contribute with the least cost. We develop a solution using the second-price sealed-bid auction, and design simple incentive mechanisms that offer gain to the contributing user and the base station as well. We show that our solution achieves Nash equilibrium and evaluate its performance under various trace-driven scenarios of downloading contents in subways.