Channel assignment aims to reduce interference by carefully assigning a channel to each radio. The dynamic channel assignment based on internal usage can improve the throughput of multi-channel, multi-radio wireless mesh networks by selecting the least used channel, thereby resulting in a low level of interference. However, simply assigning the least-used channel among mesh nodes is not sufficient to reduce the interference in a network. This is because today’s numerous urban areas around the world are covered by dense 802.11 Wi-Fi networks which may operate on the same channel used by mesh nodes, generating significant external interference. As a result, even though channel assignment schemes choose the least-used channel for a radio, if that channel is being heavily utilized by external nodes, it may not be the best channel.
Therefore, relying exclusively on the dynamic channel assignment considering only internal usage can significantly degrade network throughput due to the external interference from co-located wireless network.
In this paper, we proposed a distributed dynamic channel assignment algorithm which takes both the internal usage and external interference in a wireless mesh network into account. However, accounting for the external interference in channel assignments is a challenge since all external nodes do not allow internal mesh nodes to acquire their traffic information and do not cooperate with internal mesh nodes. Since a mesh node does not have information about which channel the external nodes are on, each mesh node has to monitor all the available channels to obtain the traffic information of the external nodes. However, monitoring all the available channels by channel switching can cause the flow disruption of current data traffic and performance degradation. To avoid these problems, the proposed algorithm does not perform channel switching to monitor external interference but the cooperation between the mesh nodes within a neighborhood.
We defined two new problems, an unknown channel problem and an unsuccessful channel switching problem, which are related to the cooperation between mesh nodes. The proposed algorithm solves the first problem by calculating the expected throughput on an unknown channel and the second problem by exploiting the PTI (Potential Throughput Increase), which is a more direct indication of an overloaded channel, as defined in this work. In addition, the SCOUT strategy used in the proposed algorithm can obtain external interference information while minimizing throughput loss by actively exploiting the fairness property of the DCF (Distributed Coordination Function). We performed extensive NS-2 simulations to evaluate the proposed algorithm and showed that the proposed algorithm can increase network throughput by 54% by considering external interference through the cooperation between mesh nodes.
무선 메쉬 네트워크는 빠르게 증가하고 있는 모바일 무선 인터넷 트래픽을 서비스하기 위한 경제적이고 효율적인 대안 기술이다. 기존 유선 네트워크를 설치하는 대신 무선 메쉬 네트워크로 무선 백본망을 설치함으로써 빠르고 경제적으로 무선 인터넷 서비스를 가능하게 하기 때문이다. 무선 백본망으로써 역할을 제대로 수행하기 위해서는 High Throughput Support가 기본적으로 필요하게 된다. 그래서 많은 연구들이 multi-radio multi-channel 환경에서 동적 채널할당을 통한 throughput 향상에 초점을 두고 있다. 기존 연구들에선 외부간섭을 고려하지 않고 메쉬 노드들 사이에서의 내부 트래픽만을 고려하여 채널을 할당하여 네트워크 throughput을 증가시키는 결과를 보여왔다.
하지만 오늘날 도심의 많은 지역들이 IEEE 802.11기반의 Wi-Fi 무선 네트워크가 설치되어 있고 이런 무선 네트워크는 무선 메쉬 네트워크에게 외부 간섭으로 작용하게 된다. 그래서 기존 연구들처럼 내부 트랙픽만을 고려한 채널 할당을 하게 되면 이러한 외부 간섭으로 인한 throughput 저하를 피할 수 없게 된다. 예를 들어보면 기존 연구들처럼 내부 트래픽을 고려하여 가장 적게 사용하는 채널을 사용하더라도 그 채널을 외부 무선 네트워크가 사용하고 있다면 그 채널은 가용 채널들 중 가장 적게 사용하는 채널이 아닐 수 있기 때문이다. 그래서 본 연구에서는 외부 간섭과 내부 트래픽 모두를 고려한 distributed version의 동적 채널할당 알고리즘을 제안한다. 그러나 외부 간섭을 고려하는 것은 매우 까다로운 문제이다. 그 이유는 외부 무선 노드들은 설치된 메쉬노드들에게 자신의 트래픽 정보를 제공하지 않고 메쉬 노드와 cooperation하지 않기 때문이다. 메쉬 노드들은 어느 채널에 외부 노드들이 존재하는지 알 수 없기 때문에 메쉬 노드들은 각자 모든 가용채널을 모두 모니터 하면서 외부 간섭양을 측정해야 한다. 그러나 모든 가용채널을 채널 스위칭을 통해서 측정하게 되면 현재 데이터 플로우의 단절문제 그리고 throughput이 저하되는 문제가 발생하게 된다. 이러한 문제를 해결하기 위해 본 연구에서 제안된 알고리즘은 외부 간섭을 측정하기 위해 채널 스위칭을 하지 않고 주변 노드들과의 cooperation을 통해서 측정한다. 주변 노드들과의 cooperation을 통해서 외부 간섭을 측정하면서 현재 데이터 플로우의 단절 문제, throughput 저하문제, 이에 따른 종단간 지연시간 증가문제를 해결할 수 있지만 unknown channel 문제, unsuccessful channel switching 이라는 새로운 문제를 야기한다. 본 연구에서는 이러한 문제를 정의하고 이러한 문제를 해결하기 위해서 다음과 같은 솔루션을 제안된 알고리즘에 구현하였다. unsuccessful channel switching 문제에 대해서 살펴보면 이 문제는 각 채널의 usage 정보가 실제 usage 정보와 불일치가 발생할 때 발생하게 된다. 이러한 usage 정보의 에러 때문에 잘못된 채널 스위칭이 일어나기도 하고 잘 못된 채널 스위칭이 일어 - 50 - 났음에도 이를 감지하지 못해서 복구하지 못하는 문제가 발생하는데 이게 바로 unsuccessful channel switching 문제이다. 이를 해결하기 위해서 제안된 알고리즘에서는 좀 더 정확한 over-load 조건으로 PTI (Potential Throughput Improvement)를 정의하고 사용하였다. PTI는 offered traffic과 traffic being serviced 값의 차이고 계산된다. Offered traffic은 3계층 라우팅 레이어에서 라우팅 프로세스가 끝낼 때에 측정되고, traffic being serviced 값은 MAC layer에서 데이터 패킷 전송 후 해당 Ack 패킷을 수신할 때 측정된다. 즉 보내고자 하는 트래픽양보다 MAC에서 서비스 받는 트래픽양이 다를 때 이를 overload 발생으로 인지하고 채널 스위칭 프로세스를 시작하는 것이다. 시뮬레이션을 통해서 heavy use case와 hidden terminal case 모두에서 PTI 조건을 사용하여 unsuccessful channel switching을 인지하고 해결하는 것을 증명하였다. 그 다음으로 unknown channel 문제를 살펴보면, 채널의 usage 혹은 interference 정보를 메쉬 노드가 얻을 수 없는 경우 unknown channel 이라고 하고 이를 어떻게 사용할 것인가를 결정하는 문제이다. 기존 외부간섭을 고려하지 않는 경우에는 unknown channel의 경우에는 해당 채널에 메쉬 노드의 사용이 없기 때문에 usage가 가장 좋은 채널로 인식하여 항상 un-known channel로 채널 스위칭이 일어나게 된다. 이 경우 해당 채널에 외부 간섭이 많은 경우 throughput 손실이 발생하는 문제가 발생하게 된다. 하지만 제안된 알고리즘에서는 자신이 측정하지 않고, 주변 메쉬 노드들도 사용하지 않는 채널 (해당 채널의 정보를 알 수 없는 채널)을 unknown channel로 정의하고 이를 효율적으로 이용하기 위하여 3가지 policy를 구현하였다. 그 중 unknown channel에서 좋은 채널과 나쁜 채널을 고를 확률을 기반으로 expected throughput을 계산하여 unknown channel의 사용 여부를 결정하는 policy가 default로 설정되어있다. 좋은 채널과 나쁜 채널을 고를 확률은 현재 메쉬 노드가 서비스 받고 있는 traffic 양(Traffic being serviced)을 기준으로 결정된다. Expected throughput을 계산함으로써 메쉬 노드들은 언제 unknown channel을 사용하면 좋은지 기준을 얻게 된다. 또 unknown channel 수가 많으면 throughput에서 variation이 커지게 된다. 이 variation을 줄이기 위해 제안된 알고리즘에서는 SCOUT strategy를 이용하여 unknown channel의 개수를 줄여 throughput variation을 줄이게 된다. SCOUT strategy는 DCF의 fairness property를 이용해서 unknown channel에 외부간섭이 존재하더라도 그에 따른 throughput loss를 최소화 하면서 외부 간섭을 측정하여 주변 메쉬 노드에 제공함으로써 주변 메쉬 노드에서 더 나은 채널 할당이 일어나도록 도와주는 역할을 수행한다. 본 연구에서 제안된 알고리즘은 NS-2 시뮬레이션을 통해서 performance evaluation을 수행하였고 가장 중요한 결과는 다음과 같다.
본 알고리즘을 사용하여 cooperation을 통해서 외부 간섭을 고려할 경우 54.6%의 throughput 증가를 가져왔고 expected throughput 을 계산하여 unknown channel을 효과적으로 사용할 때 21.25%의 throughput 증가를 얻을 수 있었다. 또한 SCOUT strategy를 이용하여 unknown channel 수를 감소시킬 경우 throughput variation을 55.1% 로 감소 시킬 수 있었다.
