Wireless networks consist of a number of nodes which communicate with each other over a wireless channel. Some wireless networks have a wired backbone with only the last hop being wireless, like cellular voice and data networks and mobile IP. In others, all links are wireless. One example of such networks is multihop radio networks or ad hoc networks. Such networks consist of a group of nodes which communicate with each other over a wireless channel without any centralized control. This ability of ad hoc networks to form “networks on the fly” is expected to play a crucial role in situations such as disaster recovery efforts after an earthquake or fire, gathering information in a battlefield or simply forming a short-lived network among people attending a business meeting. Before this century, the importance or the reason that people have great concern in these ad hoc networks was that they don’t need any infrastructure. However, these ad hoc networks are refocused in this century because of the superior capacity. The multihopping increases the network capacity significantly in comparison with that in the case of traditional siglehopping. A major reason for adopting such multihop is in capacity enhancement, which may completely pay off its increased complexity.
In this thesis, we will propose some scheduling algorithms extending the results of traditional singlehop cellular networks to multihop cellular networks which is compromised type of the traditional cellular network and ad hoc network. We are to show the capacity gain of multihop networks by proposing algorithms which produce schedules overwhelming the optimal one of singlehop networks. The purpose of this work is to investigate the efficient scheduling of NRT packets in the uplink of cellular networks. Unlike the other works in this field, we assume that the system allows the so-called multihop transmission. For example, the system would take advantages, in terms of total average throughput from having a mobile close to the base station relay the data from the other mobiles. A key question is how to detect the situation that the multihop transmission has merits over the conventional singlehop transmission, and in such a situation, how to design such an efficient multihop transmission.
Throughout the work, we assume a single CDMA cell, in which each mobile has a finite amount of NRT data to transmit to the base station. Our goal is to design an uplink scheduling algorithm that minimizes the total transmission time to send all the data of the mobile users, possibly by multihopping.
무선 네트워크는 무선채널을 통해 서로 통신하는 많은 노드들로 구성된다. 어떤 무선 네트워크는 유선 백본망을 가지고 있으면서 마지막 홉만을 무선으로 연결한다. 셀룰라 음성/데이터 네트워크와 모바일 IP등이 그 예들이다. 반면에, 모든 링크들이 다 무선인 네트워크들이 있다. 다중 홉 무선 네트워크 혹은 ad hoc 네트워크가 그 예이다. 이러한 네트워크들은 어떠한 중앙화된 제어 없이 무선 채널을 통해 서로 통신하려는 노드들의 그룹으로 이루어진다. 노드들은 서로의 데이터 패킷을 라우팅하는데 협력적일 수 있다. 중앙화된 제어가 없다는 것과 각 노드들이 움직인다는 특징은 네트워크 계층, 매체 접근, 물리 계층에서 많은 이슈들을 만들어 낸다.
유선 인프라가 필요 없는 “부유하는 네트워크”를 구성할 수 있는 ad hoc 네트워크의 특성은 지진 혹은 화재 이후의 재난 방재, 전쟁터에서의 정보수집, 사업상의 모임에 참여한 사람들 사이의 단기 네트워크의 구성과 같은 상황에서 핵심적인 역할을 수행하게 된다.
1990년대 후반까지 ad hoc 네트워크는 이와 같은 장점 때문에 이슈가 되어 왔다. 그러나, 금세기에 들어오면서부터 ad hoc 네트워크는 또 다른 측면으로 재조명되고 있다. 그것은 ad hoc 네트워크에서 나타나는 용량의 증대이다. 무선 네트워크에서 단일 홉 전송이 주는 용량보다 다중 홉 전송이 주는 용량이 의미심장하게 크다는 연구결과들이 쏟아져 나오고 있다. 이러한 용량증대가 주는 이점은 다중 홉이 야기하는 복잡성의 증가에 대한 비용을 완벽하게 넘어서고 있는 것으로 보인다.
따라서, 이 연구에서는 단일 홉 방식의 전통적인 셀룰라 네트워크에 다중 홉을 적용 함으로서 얻어지는 용량 및 시간당 처리량의 증가에 대해 다루어 보고자 한다. 그러기 위해 먼저 셀룰라 네트워크에서의 비실시간 데이터 서비스만을 고려하기로 하자.
무선 시스템은 비실시간 데이터 서비스를 지원하기 위해 진화되어 왔다. 비실시간 서비스를 제공함에 있어, 순간적으로 전송률을 0으로까지 줄일 수 있으며 이를 통해 비실시간 패킷 전송에 대한 스케쥴링을 할 수 있다. 또한, 이러한 과정에서 네트워크가 가질 수 있는 초과 용량을 활용할 수도 있다. 따라서 전송률에 대한 제어는 스케쥴링과 매우 연관이 깊다. 만일 한 사용자가 매우 높은 전송률로 데이터를 전송하고자 한다면, 그 사용자의 높은 전송전력은 다른 사용자들에게 충돌을 일으킴으로써 감소된 처리/코딩 이득에 대한 대응이 필요하게 될 수도 있다. 반면에 사용자가 낮은 전송률로 전송을 한다면, 다른 사용자들과 심각한 충돌을 일으키진 않겠지만, 전파간섭이 일어나는 시간은 길어지게 된다. 따라서 각 사용자의 패킷을 어떻게 스케쥴링을 하고, 어떻게 전송률과 전력을 할당할 것인가 하는 것은 매우 흥미로운 문제이다.
이 연구의 목적은 DS-CDMA 시스템의 상향링크에서 비실시간 패킷을 위한 효율적인 스케쥴링을 조사하는 것이다. 이 과정에서 기존의 다른 연구들과 다른 점은 셀룰라 시스템에 다중 홉 전송을 도입함으로써 전통적인 단일 홉 DS-CDMA 시스템보다 증대된 용량을 갖는 스케쥴링 알고리즘을 개발하고자 하는 점이다. 예를 들어, 기지국 근처에 있는 사용자가 다른 사용자의 데이터를 중계해 준다면 총 평균 처리률 면에서 이점을 갖게 될 것이다.
따라서, 핵심은 다중 홉 전송이 전통적인 단일 홉 전송에 비해 이점을 갖게 되는 상황을 어떻게 찾아낼 것인가, 그리고 그러한 상황에서 효율적인 다중 홉 전송을 어떻게 구현해 내는가 하는 것이다.
본 연구에서 평균 데이터 전송률과 실현 가능한 데이터 전송률의 영역에 대한 개념을 도입하여 단일 홉 혹은 다중 홉 전송에 대한 선택을 결정해주는 이론적 특성을 유도할 것이다. 이 특성을 본 연구 전체에 걸친 근본적인 원리로 하여 다일 홉 셀룰라 네트워크에 다중 홉 전송을 적용하고자 한다.무선 네트워크는 무선채널을 통해 서로 통신하는 많은 노드들로 구성된다. 어떤 무선 네트워크는 유선 백본망을 가지고 있으면서 마지막 홉만을 무선으로 연결한다. 셀룰라 음성/데이터 네트워크와 모바일 IP등이 그 예들이다. 반면에, 모든 링크들이 다 무선인 네트워크들이 있다. 다중 홉 무선 네트워크 혹은 ad hoc 네트워크가 그 예이다. 이러한 네트워크들은 어떠한 중앙화된 제어 없이 무선 채널을 통해 서로 통신하려는 노드들의 그룹으로 이루어진다. 노드들은 서로의 데이터 패킷을 라우팅하는데 협력적일 수 있다. 중앙화된 제어가 없다는 것과 각 노드들이 움직인다는 특징은 네트워크 계층, 매체 접근, 물리 계층에서 많은 이슈들을 만들어 낸다.
유선 인프라가 필요 없는 “부유하는 네트워크”를 구성할 수 있는 ad hoc 네트워크의 특성은 지진 혹은 화재 이후의 재난 방재, 전쟁터에서의 정보수집, 사업상의 모임에 참여한 사람들 사이의 단기 네트워크의 구성과 같은 상황에서 핵심적인 역할을 수행하게 된다.
1990년대 후반까지 ad hoc 네트워크는 이와 같은 장점 때문에 이슈가 되어 왔다. 그러나, 금세기에 들어오면서부터 ad hoc 네트워크는 또 다른 측면으로 재조명되고 있다. 그것은 ad hoc 네트워크에서 나타나는 용량의 증대이다. 무선 네트워크에서 단일 홉 전송이 주는 용량보다 다중 홉 전송이 주는 용량이 의미심장하게 크다는 연구결과들이 쏟아져 나오고 있다. 이러한 용량증대가 주는 이점은 다중 홉이 야기하는 복잡성의 증가에 대한 비용을 완벽하게 넘어서고 있는 것으로 보인다.
따라서, 이 연구에서는 단일 홉 방식의 전통적인 셀룰라 네트워크에 다중 홉을 적용 함으로서 얻어지는 용량 및 시간당 처리량의 증가에 대해 다루어 보고자 한다. 그러기 위해 먼저 셀룰라 네트워크에서의 비실시간 데이터 서비스만을 고려하기로 하자.
무선 시스템은 비실시간 데이터 서비스를 지원하기 위해 진화되어 왔다. 비실시간 서비스를 제공함에 있어, 순간적으로 전송률을 0으로까지 줄일 수 있으며 이를 통해 비실시간 패킷 전송에 대한 스케쥴링을 할 수 있다. 또한, 이러한 과정에서 네트워크가 가질 수 있는 초과 용량을 활용할 수도 있다. 따라서 전송률에 대한 제어는 스케쥴링과 매우 연관이 깊다. 만일 한 사용자가 매우 높은 전송률로 데이터를 전송하고자 한다면, 그 사용자의 높은 전송전력은 다른 사용자들에게 충돌을 일으킴으로써 감소된 처리/코딩 이득에 대한 대응이 필요하게 될 수도 있다. 반면에 사용자가 낮은 전송률로 전송을 한다면, 다른 사용자들과 심각한 충돌을 일으키진 않겠지만, 전파간섭이 일어나는 시간은 길어지게 된다. 따라서 각 사용자의 패킷을 어떻게 스케쥴링을 하고, 어떻게 전송률과 전력을 할당할 것인가 하는 것은 매우 흥미로운 문제이다.
이 연구의 목적은 DS-CDMA 시스템의 상향링크에서 비실시간 패킷을 위한 효율적인 스케쥴링을 조사하는 것이다. 이 과정에서 기존의 다른 연구들과 다른 점은 셀룰라 시스템에 다중 홉 전송을 도입함으로써 전통적인 단일 홉 DS-CDMA 시스템보다 증대된 용량을 갖는 스케쥴링 알고리즘을 개발하고자 하는 점이다. 예를 들어, 기지국 근처에 있는 사용자가 다른 사용자의 데이터를 중계해 준다면 총 평균 처리률 면에서 이점을 갖게 될 것이다.
따라서, 핵심은 다중 홉 전송이 전통적인 단일 홉 전송에 비해 이점을 갖게 되는 상황을 어떻게 찾아낼 것인가, 그리고 그러한 상황에서 효율적인 다중 홉 전송을 어떻게 구현해 내는가 하는 것이다.
본 연구에서 평균 데이터 전송률과 실현 가능한 데이터 전송률의 영역에 대한 개념을 도입하여 단일 홉 혹은 다중 홉 전송에 대한 선택을 결정해주는 이론적 특성을 유도할 것이다. 이 특성을 본 연구 전체에 걸친 근본적인 원리로 하여 다일 홉 셀룰라 네트워크에 다중 홉 전송을 적용하고자 한다.
