A WDS Clustering Algorithm for Wireless Mesh Networks

作者：Tajima Shigeto^*; Funabiki Nobuo; Higashino Teruo

来源：IEICE Transactions on Information and Systems, 2010, E93D(4): 800-810.

DOI：10.1587/transinf.E93.D.800

• wireless mesh network
• WDS clustering
• gateway selection
• NP-complete
• heuristic algorithm
• variable depth search

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 hinted 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 as superiority to the existing algorithm in terms of throughput.

• 出版日期2010-4