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

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