A WDS Clustering Algorithm for Wireless Mesh Networks

Shigeto TAJIMA

IEICE TRANSACTIONS on Information and Systems   Vol.E93-D    No.4    pp.800-810
Publication Date: 2010/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.800
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
wireless mesh network,  WDS clustering,  gateway selection,  NP-complete,  heuristic algorithm,  variable depth search,  

Full Text: PDF>>
Buy this Article

Wireless mesh networks have been extensively studied as expandable, flexible, and inexpensive access networks to the Internet. This paper focuses on one composed of multiple access points (APs) connected through multihop wireless communications mainly by the wireless distribution system (WDS). For scalability, the proper partition of APs into multiple WDS clusters is essential, because the number of APs in one cluster is limited due to the increasing radio interference and control packets. In this paper, we formulate this WDS clustering problem and prove the NP-completeness of its decision version through reduction from a known NP-complete problem. Then, we propose its heuristic algorithm, using a greedy method and a variable depth search method, to satisfy the complex constraints while optimizing the cost function. We verify the effectiveness of our algorithm through extensive simulations, where the results confirm its superiority to the existing algorithm in terms of throughput.