Solving Nonlinear Covering Problems Arising in WLAN Design

• 成果类型: Article
• 署名作者: Amaldi, Edoardo; Bosio, Sandro; Malucelli, Federico; Yuan, Di
• 署名单位: Polytechnic University of Milan; Swiss Federal Institutes of Technology Domain; ETH Zurich; Linkoping University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1100.0897
• 发表日期: 2011
• 页码: 173-187
• 关键词: channel assignment; optimization; placement

摘要

Wireless local area networks (WLANs) are widely used for cable replacement and wireless Internet access. Because the medium access control (MAC) scheme of WLANs has a strong influence on network performance, it should be accounted for in WLAN design. This paper presents AP location models that optimize a network performance measure specifically for the MAC scheme of WLANs that represents the efficiency in sharing the wireless medium. For these models, we propose a solution framework based on an effective integer-linear programming Dantzig-Wolfe reformulation. This framework is applicable to any nonlinear covering problem where the objective function is a sum of contributions over the groundset elements (users in WLANs). Extensive computational results show that our solution strategy quickly yields optimal or near-optimal solutions for WLAN design instances of realistic size.