Optimization techniques have been applied to networking problems since the seminal work of Kelly. They have been used not only in wired networks but also wireless scheduling problems. However, those algorithms are based on many assumptions such as centralized scheduling, global information and so on. Due to those reasons, they cannot be applied to real networks without modifications. In this thesis, we would like to understand performance implications of those assumptions. Specially, we considered the factors such as delay in the queue information and the difference between centralized and distributed scheduler. We performed simulation study to investigate their impacts using four different versions of the optimization based scheme.
Our conclusions from the simulation study are as follows: First, the scheduling algorithm plays a very important role in determining the performance. Especially, the performance gap between the centralized scheduler and distributed one is wide. Second, queue information and control overhead have a little influence on the performance.
본 연구는 무선 ad-hoc 네트워크상에서 최적화 이론 기반의 스케줄링 성능분석에 관한 연구이다. 기존의 제시되었던 최적화 이론들은 주어진 capacity내에서 최적의 성능을 보여주고 있다. 하지만, 무선 adhoc 네트워크에서 이러한 최적화 기반의 알고리즘들을 단순화하여 적용하였을 때 최적화 이론에서 제시되었던 성능을 보여주지 못하고 있다. 이는 centralized된 방식을 사용하는 최적화 이론을 distributed된 방식으로 구현할 때 발생하는 구현의 차이에서 발생하는데, 대부분의 이론들이 distributed한 구현을 고려하지 않고 centralized된 스케줄러를 사용하며, 모든 노드들의 큐 정보를 정확하게 보유하고 있다는 가정을 하고 있기 때문이다. 본 연구에서는 이러한 성능 차이의 원인에 대해 LQF 스케줄링 이론을 이용하여 NS-2 시뮬레이션을 통하여 분석하였다. 이를 위하여 802.11, Imperfect LQF 스케줄링, Perfect LQF 스케줄링, 그리고 Ideal LQF 스케줄링의 4가지 알고리즘을 제시하여 비교분석하였다. 또한, 큐를 기반으로 하는 우선순위 스케줄링 구현을 위하여 Rank-based contention window 할당방법과 direct backoff scheme을 제안하였다. 시뮬레이션을 통하여 성능차이에 가장 큰 영향을 주는 것은 정확한 스케줄링이라는 것을 보였다. 특히, distributed 스케줄링과 centralized 스케줄링의 성능차이가 크게 나왔다. 또한, 큐 정보의 유무나 control overhead는 성능에 적은 영향을 주었다.
