Study On Gateway Placement Algorihtm In Wireless Mesh Network

Wireless Mesh Networks(WMN) is a new type of distributed broadband wireless access network with high capacity, high rate. It is an important technology for next-generation wireless networking. Wireless Mesh backbone is the core of WMN. The client exchanges information with Internet through gateway through multiple hops, so the majority of network traffic aggregates on the gateway. When designing a WMN, gateway placement is significant because it determines the total network performance. In this thesis, gateway placement problem is studied, and gateway placement algorithms are proposed from the following two aspects:(1) The gateway placement algorithm bases on transmission success rate is proposed. It aims to the maximize average transmission success rate and increase the network throughput.Firstly, the influence of link quality on network throughput is analysed. To maximinze the network throughput, Greedy_TSR algorithm is proposed. In this algorithm, the node around which link qulities are the best is choosed as a gateway. The gateway is marked as a cluster head node. Then the nodes satisfying QoS requirements are added to this cluster. These steps are repeated until all nodes are added to clusters. Lastly, the border nodes of clusters are adjusted to increase the network thoughput. Simulation experiments show that the number gateways chosen by Greedy_TSR algorithm is almost the same as these chosen by others, whereas the average transmission success rate is better than others.(2) Focused on the two factors of loading balance and average transmission success rate, the algorithm based on load balancing is proposed to get the optimal trade-offs among the number of gateway, gateway load balancing and average transmission success rate.Firstly, We analyzed the impact of gateway load balancing on network performance. To maximize average transmission success rate, we designed the greedy algorithm Greedy_Part by modifying the algorithm Greedy_TSR. Greedy_Part maximizes the average transmission success rate through adjusting the cluster structure. It can cluster the network based on the assigned gateways, as well as randomly construct the gateway palacement scheme. Based on combination of Greedy_part and genetic algorithm(GA), the algorithm GA_LBGP is proposed. GA_LBGP aims to optimize the gateway number, the average transmission success rate and gateway load balancing. With GA's mutiple-objective optimization characteristics, the GA_LBGP can get the optimal trade-offs among the number of gateway, gateway load balancing and average transmission success rate in a few iterations. Simulation experiments show that the number of gateways chosen by GALBGP is almost the same as these chosen by other algorithms. Whereas gateway load balancing and average transmission success rate are better than Greedy_Part.