Wireless Access Point Configuration Problem
A benchmark problem for topology synthesis by genetic programming
Jianjun Hu (hujianju@msu.edu)
Wireless Access Point Configuration problem is proposed as a benchmark problem for testing our Genetic Programming algorithm in simultaneous open-ended structure and parameter evolution (search)
A small city is planning to provide wireless Internet service to its citizens, who are located around the city map below (labeled as circled C). A bunch of wireless access points then need to be placed at several places to cover all the clients as each access point has limited service radius. To reduce the cost, a design solution with minimal number of access points and minimum length of the wires connecting those access points is regarded as optimal. So the question is, how to decide the number of necessary access points and which place should we put. To make it harder, we can ask to maximize the average signal strength at all clients, or add some constraints on the location of the access points. As this problem (not the simplified version) requires simultaneous topology and parameter search, many issues exist.
Where is the structure to be evolved?
Every wireless access point must be either directly linked to the source radio station or linked to another access point which has been linked to the radio station (directly or indirectly) by wires whose cost is proportionate to its length. All the connected graph is the structure to be evolved
What are the parameters to be evolved?
The locations of access points are the parameters to be evolved. Their range can be constrained in a range, e.g. (x,y)|x,y
[0, 1000]
II. Detailed Problem Statement (PDF)
III Some running results
