Problems of optimizing the performance of wired and wireless networks have been widely studied in recent past. In wireless network, activating a link affects the performance of network significantly as the capacity of a link is highly dependent to other links’activation. Unfortunately, neither optimal algorithm nor Greedy Maximal Scheduling, a well-known sub-optimal algorithm, is feasible to use in general because of the complexity and the centralized implementation. In this paper, we design a novel scheduling algorithm which approximates Greedy Maximal Scheduling in a distributed manner using multi-class contention resolution. We also analysis the efficiency of our scheduling algorithm compared to the reference policy. The performance obtained from simulation results are close to that of Greedy Maximal Scheduler thus validating our analytic model.
무선 네트워크는 다음의 두 가지 방향으로 진화하고 있다. 첫 번째로 사용자의 대용량의 멀티미디어 통신에 대한 요구의 충족을 위해, 통신 링크의 대역폭이 점점 증가하고 있다. 두 번째로 서비스 제공자들의 무선 접속 영역의 확대에 대한 요구의 충족을 위하여 다중의 무선 홉을 사용하는 무선 다중 홉 네트워크가 대두되고 있다.
유선 또는 무선 네트워크의 성능을 최적화 하기 위한 노력으로, 이와 관련된 많은 연구들이 진행되어져 왔다. 이러한 연구들의 결과로 유선 네트워크를 위한 다양한 흐름제어 (Flow Control) 기법들이 많이 제안되었다. 하지만, 무선 네트워크의 통신 링크의 용량은 독립적으로 정의되지 않고, 간섭 효과에 의해 다른 통신 링크의 영향을 받는 특성이 있다. 따라서, 무선 네트워크의 성능을 최적화하기 위해서는 흐름제어 뿐만 아니라, 무선 링크들의 활성화 또는 비활성화를 제어하는 문제인 스케줄링 문제 또한 포함하게 된다. 이론적인 연구의 결과로 최적 (Optimal), 또는 부 최적 (Sub-optimal) 스케줄링 기법이 제안되었지만, 이러한 기법들은 높은 복잡도를 가질 뿐만 아니라 중앙 집중화된 방법이기 때문에, 일반적인 무선 다중 홉 네트워크에서의 구현이 불가능하다.
본 논문에서는 일반적인 무선 다중 홉 네트워크를 위한 분산화된 스케줄링 기법을 제안한다. 이 기법은 노드 간 제어 메시지를 교환하지 않고, 고정된 비율의 구간동안의 경쟁을 통하여 스케줄링을 결정한다. 또한 경쟁 구간 (Contention Period)을 다수개의 클래스로 나누어, 주변 노드에 비하여 상대적으로 대기열의 길이가 긴 노드가 전송을 시도함에 있어 우선순위를 가질 수 있게 하였다. 이러한 방식을 사용함으로써 부 최적 기법인 Greedy Maximal 스케줄링을 효과적으로 근사할 수 있게 할 뿐만 아니라 노드간의 충돌 (Collision) 또한 효과적으로 감소시킬 수 있게 하였다.
또한 제안된 방식을 사용하였을 때의 성능이 부 최적 스케줄링 기법을 효과적으로 근사함을 수학적인 분석을 통하여 보였다. 이 분석결과는 최적의 파라메터를 결정할 수 있는 지침으로서 사용될 수 있다. 또한, 컴퓨터를 이용한 모의실험 (Simulation)을 통하여 제안하는 알고리즘의 성능을 검증하였다. 마지막으로, 제안된 기법을 널리 사용되는 네트워크 시뮬레이터인 ns-2에 구현하여, 현재 널리 사용되고 있는 802.11 DCF 스케줄링 기법과 그 성능을 전송속도 (Throughput)와 공평성 (Fairness)의 관점에서 비교하였으며, 제안된 기법을 사용함으로서 더 높은 전송속도와 공평성을 얻을 수 있음을 보였다.
