Abstract: The problem to locate wireless base stations and public establishments relates to how to make the best use of effectiveness, which is very important in the field of wireless communication engineering and city planning. This paper refers to the theories of graph partitioning, considering the number of covered vertex, the number of covered ranges and the gradient of density. At last, this paper presents a practical algorithm framework to solve the problem based on map partitioning. This paper takes the location problem of wireless base stations as a background. When considering the necessary conditions and optional conditions, this algorithm framework adopts the strategy of self adaptive divide-and-conquer, shows the allocations of base stations on maps, and achieves the objective to instruct construction efficiently. Our algorithm works as three steps: divide and conquer maps, check restraint conditions, and select locations. We do some experiments on Shanghai’s traffic map, and achieve good results.

Key words: Self Adaptive Divide-and-Conquer, Wireless Base Stations, Methods of Site Selection, Map Partitioning

摘要： 无线基站、公共设施等的选址问题是关系到其能否发挥到最大效用的问题，在无线通讯、城市规划等领域十分重要。本文利用地图划分理论，充分考虑选址时应注意的覆盖城市路口点数、覆盖城市范围和城市密度梯度等因素，给出一种实用的基于地图划分的选址方法和算法实现。本文以无线基站选址为背景，阐明该算法在满足基站选址的必要条件和可选条件下，采用自适应分治地图的策略，求出无线基站在地图上的分布情况，从而达到有效地指导选址的目的。算法思想主体包括三步：分治地图，考察约束条件，以及选址。本文利用上海城市电子地图进行了算法实验，取得较好的效果。

关键词: 自适应分治策略, 无线基站, 选址方法, 地图划分