Wireless Mesh Network Gateway Location Problem

The Wireless Mesh Network(WMN) is a very hot technology.It fuses the technical features of the Ad Hoc,WLAN and WBAN,and the multi-hop communications can support the ubiquitous broadband services.Recently,the WMN is coming into the field of civil,while more and more commercial WMNs are created.It is expected that the WMN will be the very important part of the next generation of the wireless communication technology and the Internet technology.However,the WMN suffers from the scalability issue.Because of the multi-hop communications as the Ad Hoc Network,the throughput enhancement and the coverage extension become two contradictory goals in the WMN.As a result, the WMN has to be divided into clusters.In most of the practical examples,the locations of the nodes have already been decided,and the network architect can only choose some nodes as the gateways to divide the WMN into clusters. In this case,the most important thing is to decide the number and the locations of the gateways,which is so-called the Gateway Deployment Problem in the WMN.In regarding to the problem,some researches have been carried on.The constraint conditions and the optimization objectives are proposed in this paper,while the Simplified Model and the Complete Model of the Gateway Deployment are built too.With the Simplified Model,an optimal method based on the Graph Theory and Boolean Algebra is proposed,and the method gets expanded for the actual scenes then.With the Complete Model,the Gateway Deployment Problem is further divided into two types.In the type of Single-hop Mode,a Gateway Deployment Algorithm for WMN Based on Heuristic WCA is proposed.And In the type of Multi-hop Mode,an Approximate 1-median Root Spanning Tree Algorithm can be used to deploy the gateways in the WMN.A lot of simulations show that the algorithms proposed in this paper are able to solve the Gateway Deployment Problem in the WMN very well.