Abstract: The IEEE 802.16j standard can provide coverage and capacity improvements through the introduction of new nodes called relay stations (RS). IEEE 802.16j network has the potential to deliver higher capacity networks at lower cost than more conventional single hop wireless access network. The joint optimization of relay stations and base stations is one of the network planning content for mobile network operators. Because the relay stations can be developed at significantly lower cost than base stations, given a set of candidate sites and network coverage demand, the number of base stations which need deploying can decrease through the joint optimization of relay stations and base stations, and the total cost of the network construction can be reduced. To solve the problem of location planning of base station and relay station in IEEE 802.16j relay network, a solution of location planning based on immune algorithm is proposed. The mathematical model of location planning is expounded, the framework of immune optimization algorithm is given, and simulation experiments are conducted to validate the algorithm. Experimental result shows that the proposed solution of location planning can obtain good network capacity with low cost of network construction, and has the advantages of good application value.