무선 메쉬 네트워크에서 라우터 노드 배치를 위한 타부 서치 알고리즘 = A Tabu Search Algorithm for Router Node Placement in Wireless Mesh Networks

국문 초록 (Abstract)

본 논문에서는 무선 메쉬 네트워크에서 라우터 노드와 클라이언트 노드간의 연결설정 최대화를 위해 라우터 노드를 효과적으로 배치하는 타부 서치 알고리즘을 제안한다. 네트워크에서 라우터 노드와 클라이언트 노드의 수가 증가함에 따라 두 종류의 노드 간 연결을 위한 계산량은 급격히 늘어나게 된다. 본 논문에서는 밀집도가 높은 네트워크에서 적정한 시간 내에 최적의 노드 연결을 위한 타부 서치 알고리즘을 제안하며, 효율적인 검색을 위해 타부 서치 알고리즘의 효과적인 이웃해 생성 동작을 제안한다. 제안된 알고리즘은 라우터 노드와 클라이언트 노드간의 최대 연결수와 실행시간 관점에서 성능을 평가하며, 평가 결과에서 제안된 알고리즘이 기존의 알고리즘에 비해 성능이 우수함을 보인다.

다국어 초록 (Multilingual Abstract)

This paper proposes a Tabu search algorithm to maximize the connectivity between the router nodes and the client nodes in wireless mesh networks. As the number of the router nodes and the client nodes in the networks increases, the amount of calculation for finding the solution would be too much increased. To obtain the optimal solution within a reasonable computation time for a high-density network, we propose a Tabu search algorithm to obtain the optimal solution for maximizing the connectivity. In order to make a search more efficient, we propose some efficient neighborhood generating operations of the Tabu search algorithm. We evaluate those performances through some experiments in terms of the maximum number of the connectivity and the execution time of the proposed algorithm. The comparison results show that the proposed algorithm outperforms other existing algorithms.

참고문헌 (Reference)

1 I. F. Akyildiz, "Wireless mesh networks : a survey" 47 (47): 445-487, 2005

2 Ch. Chen, "Urban Wireless Mesh Network Planning : The Case of Directional Antennas" Department of Computer Science, University of Illinois at Urbana-Champaign 2007

3 A. Barolli, "Optimization problems and resolution methods for mesh placement nodes in wireless mesh networks: A survey" 7-9, 2011

4 E. Amaldi, "Optimization models and methods for planning wireless mesh networks" 52 : 2008

5 A. Antony Franklin, "Node placement algorithm for deployment of two-tier wireless mesh networks" 4823-4827, 2007

6 T. Vanhatupa, "Genetic algorithm to optimize node placement and configuration for WLAN planning" 612-616, 2007

7 B. Aoun, "Gateway placement optimization in wireless mesh networks with QoS constraints" 24 (24): 2127-2136, 2006

8 J. Wong, "Gateway placement for latency and energy efficient data aggregation" 490-497, 2004

9 F. Glover, "Future paths for integer programming and links to artificial intelligence" 5 : 533-549, 1986

10 Y. Bejerano, "Efficient integration of multihop wireless and wired networks with QoS constraints" 12 (12): 1064-1078, 2004

11 M. R. Garey, "Computers and intractability A guide to the theory of NP-completeness" Freeman 1979

12 F. Xhafa, "An annealing approach to router nodes placement problem in wireless mesh networks" 245-252, 2010