Gateway Deployment Optimization in Wireless Mesh Network: A Case Study in China

The rapid development of communication technology provides a enormous support for municipal mesh network. Nowadays many cities across the world have setup or prepare to setup wireless mesh networks (WMNs), includes Beijing city for its 2008 Olympic Games. However, Internet Gateway (IGW) placement, which is one of essential issues in a WMN design, has not been considered seriously in practice both by equipment provider and planning institute. Taking Beijing Wangjing zone as an example, the actual placement results didn´t consider the gateway deployment optimization. This paper, first formulates its IGW placement problem as an integer linear programming incorporating QoS into account. Then solves the problem using degree-based GDTSP algorithm proposed by and compares the results with the existent ones given by Chinacomm planning institute. After that, the paper presents a new heuristic algorithm adapt to a special type of graphs in practice, and new results analysis shows that it can help to save more than 25% of the system cost.