Network coding for wireless networks is a promising technique to improve network throughput. As a new packet forwarding architecture, COPE is the first to bring a network coding layer to the conventional TCP/IP network stack. However, COPE’s packet encoding scheme does not consider optimality. This thesis describes Local Optimal Search (LOS), a new packet encoding scheme for COPE.
We present a formal description of the packet encoding problem related to wireless network coding. We propose the concept of coding graph to model the relations among packets related to a packet encoding problem. With the assistance of coding graph, we design LOS, which always searches for a local optimal set of packets to be encoded together for each transmission. We also design a new metric, Local Coding Gain (LCG), to measure the effectiveness of a set of selected packets.
To set up an evaluation environment, we revise and implement COPE in NS2. We adjust the original NS2 network stack for 802.11 wireless networks and insert a new network coding layer between LLC sublayer and MAC sublayer. NS2 simulation results on this coding layer are close to the experiment results of a wireless mesh network testbed.
We prove that LOS always finds the largest number of packets to be encoded for a single transmission. We conduct simulations on four basic coding scenarios in NS2. Compared with COPE, the simulation results show that the number of link level transmissions is reduced up to 6.19% for delivering a certain number of packets in the transport layer.
본 논문은 COPE에 사용될 수 있는 새로운 패킷 인코딩 방법인 LOS를 제안한다. LOS는 매번 패킷을 전송할 때마다 인코딩이 가능한 모든 패킷을 인코딩한다. LOS는 여러 가지 척도를 사용해 원본 패킷 중 한 번에 전송할 수 있는 최적화된 집합을 찾아낸다. LOS 패킷 인코딩 방법의 효율성을 측정하기 위해 average effective payload (AEP)라는 척도가 고안되었다. AEP는 transport layer에서 전송된 패킷 수와 link layer에서의 전송 수의 비율로 정의된다. AEP를 측정하는 시뮬레이션을 수행한 결과에 따르면 LOS는 COPE에서 쓰이는 기본 패킷 인코딩에 비해 높은 성능을 보였다.
LOS 패킷 인코딩 방법을 사용하기 위해 각 노드에는 보내야 하는 원본 패킷의 순서를 저장하는 여러 개의 가상의 큐가 존재한다. 가상의 큐들 각각의 가장 앞에 있는 원본 패킷들의 관계를 코딩 그래프를 이용하여 나타내어 패킷 인코딩 문제를 전통적인 그래프 이론의 문제 중 하나인 최대 클릭(maximum clique) 문제로 변환한다. LOS의 성능을 측정하기 위해 network simulator-2(NS-2)에 네트워크 코딩 층위를 새로이 구현했다. 구현된 네트워크 코딩 층위는 테스트 결과 실제 무선 메쉬 네트워크 테스트베드와 비슷한 결과를 보였으므로 네트워크 코딩 층위의 구현이 바르게 되었음을 알 수 있다. 코딩 그래프와 네트워크 코딩 레이어의 개념을 이용하면 네트워크 코딩 문제에 대해 더욱 심화된 연구가 이루어질 수 있다.
