In a packet radio network (PRN), since all users share a single channel, unconstrained transmission may lead to the packet collision, resulting in damaged useless packets at the destination. Collided packets must be retransmitted, thus increasing the system delay and the bandwidth usage, which in turn lowers the system throughput. Therefore, there needs multiple access protocol to minimize or eliminate collisions. Multiple access protocols can be divided into two classes: dynamic protocols and static protocols. Dynamic protocols only reduce the number of collisions, but do not eliminate all of them.
On the other hand, static protocols can avoid collisions perfectly through the prior broadcast scheduling, which is the most important factor of static protocols. In this thesis, we study on optimal broadcast scheduling in the following multiple access protocols: TDMA (time division multiple access), synchronous CDMA (code division multiple access), and asynchronous CDMA.
We propose a centralized algorithm to find a collision-free broadcast schedule in a TDMA frame. In order to minimize the system delay, the optimal schedule must be defined as the one that has the minimum frame length and provides the maximum slot utilization. The proposed algorithm is based on the sequential vertex coloring algorithm. Numerical examples and comparisons with previous algorithm have shown that the proposed algorithm can find near-optimal solutions in respect of the system delay.
CDMA protocol has the advantage that it can be operated in both synchronous and asynchronous manner. Synchronous CDMA is the combination of CDMA and TDMA. In synchronous CDMA, we are able to schedule transmissions in the time domain like TDMA. In synchronous CDMA PRN, we propose a collision-free broadcast scheduling algorithm, which works for general traffic distribution, independently of the particular network topology.
Asynchronous CDMA PRN is the one that CSMA (carrier sense multiple access) and CDMA protocols are co-operated. We investigate the problem of minimizing the number of codes needed to eliminate packet collisions in asynchronous CDMA PRN. This code assignment problem is trivial if the network size is small. However, it becomes very inefficient to assign a unique code to each user when the network size grows.'
패킷 무선망은 무선데이터 통신 서비스를 위하여 유선망의 패킷교환방식을 전파라 는 전송매체를 이용해 구현한 것이다. 패킷 무선망에서는 사용자들이 하나의 주파 수 자원을 공유하기 때문에 이를 조정해 주는 다중접속 방식이 필요하다. 또한, 계획 없이 수행되는 패킷의 충돌을 발생시키고 충돌된 패킷은 저장하였다가 다시 전송해야 하므로 시스템의 성능을 저하시키기 때문에, 다중접속 방식은 패킷의 충돌을 최소화하거나 완전히 회피할 수 있어야 한다. 본 논문에서는 여러 다중접속 방식 중에서, 패킷의 충돌을 완전히 회피할 수 있는 패킷전송계획 (Broadcast Scheduling) 수립이 가능한 시분할 다중접속(TDMA) 방식과 동기화된 코드분할 다중 접속(Synchronous CDMA) 방식, 그리고 비동기화된 코드분할 다중접속(Asynchronous CDMA) 방식의 세 가지 다중접속 방식을 고려하였다. 즉, 패킷 무선망에서 위의 세 가지 다중접속 방식을 사용할 때 발생하는 패킷전송계획 문제를 다루었다.
시분할 다중접속 방식을 사용하는 패킷 무선망에서는 시스템의 전송 지연을 최소화 하기 위해 전송계획의 크기를 최소화하고 채널 사용 효율을 최대화하여야 한다. 본 논문에서는 위의 문제를 풀기 위하여 vertex coloring 기법을 이용한 휴리스틱 알고리즘을 제안하였고 성능 평가를 통하여 기존의 알고리즘보다 좋은 결과를 얻을 수 있음을 보였다.
동기화된 코드분할 다중접속 방식은 시분할 다중접속방식과 코드분할 다중접속 방식의 결합된 형태로 본 논문에서는 네트워크 토폴로지(topology)와 독립적으로 운용될 수 있는 알고리즘을 제안하였다. 또한 기존의 알고리즘들이 균일한 트래픽 분포하에서만 운용될 수 있는 것과는 달리 일반적인 분포하에서도 운용될 수 있는 효율적인 알고리즘을 제안하였다.
비동기화된 코드분할 다중접속 방식하에서의 패킷전송계획은 코드의 개수를 최소화 하면서 사용자들에게 코드를 할당해주는 문제로 구현될 수 있는데, 이 문제는 vertex coloring 문제의 변형이다. 본 논문에서는 기존의 연구보다 좋은 성과를 나타내는 새로운 휴리스틱 알고리즘을 제안하였다.
