A wireless mesh network (WMN) is expected to be a key enabler for next generation networking due to its infrastructure-less strengths such as scalability, cost-efficient rapid deployment, and long distance communications. In a WMN, in its nature, a mesh node cooperates to forward a packet to a destination with each other. In this process, traffic concentrates on a specific region, and forms a congested hot spot which increases channel access contention and queueing delays. Thus, path load balancing is essential for improving the performance of a WMN. Compared with a wired network, the scalability of a WMN is more challengeable due to the unstable nature of wireless links including interference and fading. Conventional shortest-path routing, which requires the route maintenance process, is vulnerable to congested hot spots and node failures. Because control messages consume the available bandwidth for data traffic, network throughput decreases. In this sense, a protocol design of a WMN is required to cover scalable distributed networking with minimum control overheads. A WMN is a hub-and-spoke type network, where mesh gateways as hubs play a role to provide Internet access. The majority of traffic in a WMN is from mesh clients to mesh gateways or vice versa. As a result, the throughput capacity of an entire WMN totally depends on the utilization efficiency of mesh gateways. To maximize the throughput efficiency in a WMN, load balancing among mesh gateways is a primary issue.
As a load balancing routing scheme, back-pressure routing is well-known. Back-pressure routing utilizes queue length information for routing decisions, but no consideration of path length causes unnecessary long paths which involve frequent channel access contention and queueing delays. On the other hand, geographic routing fully exploits scalable distributed networking. Because there is no route maintenance, geographic routing with few control overheads minimizes the consumption of wireless resources. However, geographic routing tends to form a congested hot spot, and it has no mitigation resolution for that.
We approach the path load balancing and gateway load balancing problems on the framework of anycast (one-to-one-of-many). Because mesh clients only have to connect to one mesh gateway for Internet service, routing of one source-one unspecified destination pair is a matter of concern.
By inspirations of an electrostatic potential theory, we propose a hybrid form of back-pressure routing and geographic routing. Our scheme, ALFA (autonomous load-balancing field-based anycast routing) as field-based routing, simultaneously keeps traffic load dynamics and efficient shortest-path exploration taking the advantages and overcoming the limitations of back-pressure routing and geographic routing. Based on Poisson’s equation, which governs the steady states of physical systems, ALFA constructs a routing metric to achieve autonomous load balancing and preserve efficient path lengths. To develop a completely scalable solution, we derive two-dimensional and three-dimensional distributed models with the help of a finite element method and a local equilibrium method; hence, ALFA utilizes only one-hop information for routing decisions.
We analyze the properties of our protocol such as loop-freeness, load balancing behavior, efficient path length provision, stateless property, and scalability. Furthermore, simulation results exhibit such properties and the superior performance of ALFA compared with conventional protocols. As a proof-of-concept demonstration, we implement ALFA on the top of an IEEE 802.11-based WMN testbed. Experiment results validate the performance of ALFA.
유비쿼터스 시대의 개막과 더불어 무선 메쉬 네트워크는 차세대 네트워크의 인프라로서 학계 및 산업계에서 각광을 받고 있다. 기존 유선 네트워크에 비해 네트워크 포설 비용 및 운용 비용을 절감하면서 보다 많은 사용자들을 수용할 수 있기 때문이다. 무선 메쉬 네트워크에서는 메쉬 노드들이 타 메쉬 노드들과의 협력을 통해 패킷을 목적지로 전달한다. 이 경우, 트래픽이 특정 지역으로 집중되어 혼잡 지역을 야기할 가능성이 있다. 혼잡 지역에서는 심화된 채널 접근 경쟁으로 인한 수율 감소 및 증가된 큐로 인한 지연 시간 증대라는 문제들이 발생한다. 이러한 문제를 해결하기 위해 경로 부하 분산 기법이 필요하다. 유선 네트워크 환경에 비해, 무선 메쉬 네트워크의 확장성은 무선 채널의 간섭 영향으로 인해 상당한 제약을 받는다. 기존 최단 경로 라우팅 기법들은 경로를 지속적으로 관리하기 위해 플로딩 기법을 사용한다. 특히 네트워크 혼잡 상태 및 특정 노드의 고장인 경우, 빈번한 플로딩 메세지를 발생시켜 한정된 무선 자원의 상당량을 소모한다. 확장성 있는 네트워킹을 위해 무선 메쉬 네트워크에서의 프로토콜은 분산적인 네트워킹을 수용해야 할 필요가 있다. 그리고 무선 메쉬 네트워크는 대부분의 트래픽 방향이 메쉬 노드에서 메쉬 게이트웨이, 또는 메쉬 게이트웨이에서 메쉬 노드로 향하는 특징을 가진다. 이러한 환경 하에서, 메쉬 네트워크 전체의 성능은 메쉬 게이트웨이의 트래픽 처리 효율에 좌우됨을 알 수 있다. 즉, 메쉬 네트워크의 수율을 최대화시키기 위해서는 트래픽 처리 효율을 증가시키는 메쉬 게이트웨이 부하 분산 기법이 필요하다. 본 연구는 경로 부하 분산 기법 및 메쉬 게이트웨이 부하 분산 기법을 애니캐스트라는 독특한 통신 구조 하에서 다루고자 한다. 무선 메쉬 네트워크에서는 소스와 특정 목적지로 구성되는 기존 유니캐스트의 통신 구조와 차별화되게 소스가 불특정 다수의 메쉬 게이트웨이 중 하나와의 통신만 이루어지면 인터넷 연결이 가능하기 때문이다. 부하 분산 기법으로서, 백프레셔 라우팅이 잘 알려져 있다. 백프레셔 라우팅은 큐 정보를 경로 결정에 이용함으로써 네트워크 전체의 부하를 적절히 분산시킨다. 하지만, 경로 길이에 대한 고려가 없기 때문에 불필요하게 장거리 경로를 선택하여 채널 접근 경쟁 및 큐잉 지연 시간을 증가시킨다. 한편, 지리적 정보 기반 라우팅은 단거리 경로를 보존하면서 확장성 있는 분산 네트워킹의 장점을 가진다. 경로를 유지하지 않고, 패킷 전송 순간 이웃 노드의 위치 정보만을 사용하기 때문에 무선 자원의 소비를 최소화시킨다. 반면, 프로토콜의 특성 상 혼잡 지역을 생성하는 경향이 있고 이에 대한 대처 방안이 없는 것이 단점이다.
본 연구에서는 전자기장 포텐셜 이론에서 착안하여 백프레셔 라우팅과 지리적 정보 기반 라우팅을 결합한 형태의 라우팅 기법을 제시한다. 필드 기반 라우팅의 일종인 제안 프로토콜 ALFA (자율 부하 분산 필드 기반 애니캐스트 라우팅)는 트래픽 부하에 역동적이며 효율적으로 최단 경로를 탐색한다. 즉, 백프레셔 라우팅과 지리적 정보 기반 라우팅의 장점을 아우르고 단점을 극복하는 기법이다. 제안 프로토콜은 물리계 시스템의 안정화 상태를 서술하는 포아송 방정식에 기반하여 라우팅 메트릭을 생성한다. 확장성을 위한 방안으로 수치해석기법인 유한차분법과 지역평형법으로 분산 형태의 모델을 도출한다. 2차원 및 3차원 각각에 대해 모델을 제시하였으며, 제안 프로토콜은 라우팅 결정을 위해 단순히 1홉 이웃 노드들의 정보만을 이용한다.
한편, 제안 프로토콜의 특성을 라우팅 루프, 부하 분산, 효율적 경로 선택, 확장성 측면에서 분석하고 시뮬레이션을 통해 검증한다. 보다 실증적인 검증을 위해, 제안 프로토콜을 IEEE 802.11기반 메쉬 테스트베드에 구현하여 실험을 수행한다. 실험 결과는 제안 프로토콜의 특성 및 우수성을 보여준다.
본 연구에서 제시하는 프로토콜은 기존 무선 메쉬 네트워크의 확장성 문제를 최소한의 비용으로 해결하고, 한정된 무선 네트워크 대역 자원을 최대한 활용 가능하게 한다. 이로써 제안 프로토콜은 향후 3GPP/LET-Advanced, WiFi-n 기반 광대역 무선 메쉬 네트워크의 사업자급 솔루션에 대한 교두보를 마련한다. 아울러, 물리계 관점에서의 네트워크 재해석은 세계적으로 활발히 진행되고 있는 융합 연구에 대한 새로운 패러다임을 시사하고 있다. 근래의 연구 동향인 자연계 영감(nature-inspired) 기반의 공학적 응용 분야 발굴의 흐름과 부합되어 학문적으로 큰 임팩트를 생성할 것으로 기대된다. 또한, 수치해석기법에 기반한 독창적인 네트워크 프로토콜 설계 방법 및 프로토콜 검증을 위해 KAIST 캠퍼스 내에 구축된 메쉬 테스트베드는 무선 사업자의 저가 공중 네트워크 포설에 대한 실용적 해법을 제시하고 있다.
