Recently, static wireless multi-hop networks such as wireless mesh networks(WMN), wireless sensor networks have been risen due to their simplicity to deploy and cheap install cost. Multicast service in those networks has an advantage for sending data to multiple destinations by one broadcasting cost. This advantage is called wireless multicast advantage and many papers have solved the multicast routing problem with the advantage. Also, there are two key measures to evaluate performance of a multicast tree algorithm or protocol, end-to-end delay and the number of transmissions. End-to-end delay is the most important measure in QoS manner and it affects total throughput in wireless networks. Delay is same as hop count or path length from source to each destination and that is directly related to the packet success ratio. In wireless networks, each node use air medium for transmitting data, so bandwidth consumption problem is just same as the number of transmissions. If there are many transmitting nodes in network, there would have a lot of collisions and queues caused by congestions. In this paper, we optimize two metrics by guaranteed delay scheme. We will provide IP formulation for minimization of the number of transmissions with guaranteed hop count and preprocessing to solve that problem. Also, we extend this scheme not just with guaranteed minimum hop count, but 1 or more guaranteed delay bound to compromise two key metrics. We will explain the proposed heuristic algorithm for that and show the performance and result in the later part of this paper.
최근에, 무선 메쉬 네트워크(mesh network)나 센서 네트워크(sensor network)와 같이 고정된 무선 다중 홉 네트워크(wireless multi-hop network)들이 설치 및 보급의 간편성과 싼 가격으로 인해 많은 주목을 받고 있다. 멀티캐스트(multicast) 서비스는 이와 같은 무선 다중 홉 네트워크에서 한번의 전송으로 여러 노드(node)에게 동시에 데이터를 보낼 수 있다는 점에서 굉장한 이점을 가지고 있다. 이러한 무선 멀티캐스트 전송의 장점을 이용해서 많은 논문들이 멀티캐스트 라우팅(multicast routing) 문제를 풀어내고 있다. 무선 다중 홉 네트워크에서 멀티캐스트 라우팅은 크게 두가지 중요한 성능평가 항목이 있는데 그것은 종단간 지연시간(end-to-end delay)과 전송 노드의 개수이다. 라우팅에서 종단간 지연시간은 QoS(Quality of Service)만족 측면이나 무선 네트워크의 전체 성능 향상에 큰 영향을 미친다. 지연시간은 데이터 최초 발신지로부터 각 목적지까지 경로의 길이 즉, 홉의 개수(hop count)로서 표현 될 수 있고 패킷 전송 성공률과 직접적으로 관련된다. 무선 네트워크에서는 전송하는데 주위에 많은 영향을 끼치기 때문에 대역폭 사용량(bandwidth consumption)을 줄이기 위해서는 전송하는 전체의 노드의 개수를 줄이는 것이 좋다. 만약 많은 노드가 전송을 하고 있다면 많은 패킷 충돌과 그로 인한 대기열의 증가를 불러일으킨다. 본 논문에서는 위 두가지 중요한 성능평가 항목에 대해서 최소 지연시간을 보장하면서 전송 노드의 개수를 최소화함으로써 네트워크 성능을 최적화 하고자 한다. 그를 위해 정수계획 모형(IP formulation)을 세우고 선행작업(preprocessing)을 통해 문제를 최소화하여 풀어내었다. 또한 지연시간을 최소시간에서 조금씩 여유분을 늘려가면서 전송 노드의 개수를 최소화하는 알고리즘도 제안하였다.
