An Access Point Allocation Algorithm for Indoor Environments in Wireless Mesh Networks


IEICE TRANSACTIONS on Communications   Vol.E92-B    No.3    pp.784-793
Publication Date: 2009/03/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E92.B.784
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Ad Hoc and Mesh Networking for Next Generation Access Systems)
access point allocation,  wireless mesh network,  algorithm,  indoor environment,  NP-complete,  

Full Text: PDF>>
Buy this Article

As a flexible, cost effective solution for a large-scale access network to the Internet, we have studied the design optimization of the Wireless Internet-access Mesh NETwork (WIMNET). WIMNET consists of multiple access points (APs) that have wireless links between them mainly on the wireless distribution system (WDS). In WIMNET, the links around the Internet gateway can be bottlenecks because every packet passes through it after multihop link activations. Besides, the link quality may be degraded by obstacles in indoor environments. Thus, the proper allocation of APs is essential in WIMNET, so that the communication quality should be ensured while the installation and management cost be minimized. In this paper, we formulate this AP allocation problem for indoor environments in WIMNET with the proof of the NP-completeness of its decision version. Then, we present its two-stage heuristic algorithm composed of the initial greedy allocation and the iterative improvement. The effectiveness of our proposal is verified through extensive simulations in three indoor environments.