As a wireless mesh network becomes one of the major architecture for a wireless network, it intrigues a research question for a higher throughput of the wireless mesh network. The network coding is one of the candidates which can satisfy the requirement for a higher throughput. However, the computational complexity at a coding node is too high to deploy a network coding function to all intermediate nodes in a multi-hop network. It is proved that coding at several nodes can achieve the maximum throughput. However, finding the number of minimal coding node is a NP-hard problem. In this thesis, heuristic algorithm is proposed which selects the placement of small number of network coding nodes achieving given throughput. The concept of a dormant node is introduced and the worst case throughput at each stage of the algorithm is estimated by using the average number of arrival packet at each node. Then the selection algorithm is proposed which selects a node as network coding node or dormant node which can maximize the worst case throughput.
The proposed algorithm unblocks a throughput bottleneck of a network by changing a bottleneck node to a network coding node or dormant node, where the dormant node of a flow is a node which discards all packets for the flow. In our case studies, it shows that unblocking bottleneck can increases throughput. By introducing a dormant node, the given throughput is achieved with the small number of network coding nodes, even with the small number of store-and-forward nodes.
최근 무선 기기에 대한 수요가 급증하면서, 무선 메시 네트워크의 더 빠른 전송률에 대한 요구도 증가하고 있다. 네트워크 코딩 기술은 이러한 요구를 만족시킬 수 있는 대안이지만 코딩 노드에서의 계산 복잡도가 높기 때문에 모든 중간 노드에 적용시키기는 어렵다는 한계가 있다. 하지만, 모든 중간 노드에 네트워크 코딩을 적용시키지 않고, 더 적은 수의 코딩 노드로 최대 쓰루풋을 달성할 수 있는 것이 이미 증명되었다. 따라서 본 논문에서는 주어진 쓰루풋을 달성하는 작은 수의 네트워크 코딩 노드를 선택하는 휴리스틱 알고리즘을 제안한다. 또한 제거 노드의 개념을 도입하였다. 본 논문에서는 먼저, 제안된 알고리즘의 각 단계에서의 최저 쓰루풋을 각 노드에 도착하는 패킷의 평균을 이용하여 추정한다. 그리고 최저 쓰루풋을 최대화시키는 노드를 네트워크 코딩 노드 혹은 휴면 노드로 선정하는 선택 알고리즘을 제안한다.
제안 알고리즘은 네트워크 코딩 노드 혹은 휴면 노드로 선정함으로써 네트워크의 병목 노드를 해소시킨다. 병목현상을 해소시키면 네트워크의 전체 쓰루풋이 향상될 수 있다. 휴면 노드란 해당 플로우에 대한 모든 패킷을 버퍼에 저장하지 않고 버리는 노드이며, 휴면 노드를 도입함으로써, 주어진 쓰루풋을 더 적은 수의 코딩노드로, 심지어 더 적은 수의 전달노드로 달성할 수 있다.
