A WDS clustering algorithm for wireless mesh networks

Shigeto Tajima, Nobuo Funabiki, Teruo Higashino

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)800-810
Number of pages11
JournalIEICE Transactions on Information and Systems
Issue number4
Publication statusPublished - 2010


  • Gateway selection
  • Heuristic algorithm
  • NP-complete
  • Variable depth search
  • WDS clustering
  • Wireless mesh network

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'A WDS clustering algorithm for wireless mesh networks'. Together they form a unique fingerprint.

Cite this