A WDS Clustering Algorithm for Wireless Mesh Networks

The wireless mesh network has been studied as an expandable wireless access network to the Internet. This paper focuses on the network composed of only access points (APs) that has multihop wireless connections with each other through wireless distribution system (WDS). Because the number of APs in a single WDS cluster is limited due to transmission loads of broadcasting control packets, the proper partition of APs for multiple WDS clusters is essential for its scale-up. In this paper, we formulate this WDS clustering problem, and prove the NP-completeness of its decision version through reduction from the bin packing problem. Then, we present its two-stage heuristic algorithm where we verify the effectiveness of our approach through extensive simulations.