Wireless mesh networks (WMNs) have emerged as a key technology for the next-generation wireless networking and attracted many research attention. WMNs are multi-hop wireless networks, composed of static mesh routers and mobile users. In wireless mesh networks, nodes communicate directly with other nodes within their wireless transmission range (single-hop communication). Using intermediate nodes as relays (multi-hop communication), they communicate to all other participating nodes. Because of the infrequent change of topology in WMN backbone, it is more important to form an optimal topology. Moreover, how to route the traffic to the gateways, which connect the WMN backbone to the wired Internet, is another concern in nowadays research....[ Read more ]

Wireless mesh networks (WMNs) have emerged as a key technology for the next-generation wireless networking and attracted many research attention. WMNs are multi-hop wireless networks, composed of static mesh routers and mobile users. In wireless mesh networks, nodes communicate directly with other nodes within their wireless transmission range (single-hop communication). Using intermediate nodes as relays (multi-hop communication), they communicate to all other participating nodes. Because of the infrequent change of topology in WMN backbone, it is more important to form an optimal topology. Moreover, how to route the traffic to the gateways, which connect the WMN backbone to the wired Internet, is another concern in nowadays research.

Our first contribution is the formulation of the constrained optimization problems. Secondly, we apply the decomposition method to solve our problem for large scale networks. In this thesis, we formulate the topology formation and the traffic routing jointly in terms of two objectives. One is to balance the traffic load in the network, and the other is to guarantee the fairness and at the same time to maximize the throughput.

In particular, we formulate the problem as a linear binary programming (LBP) problem. Since LBP is difficult to solve, we decompose the primal problem into two solvable sub-problems. One is a linear programming (LP) problem and the other is a binary programming (BP) problem. Furthermore, we propose a heuristic method, called the iterative Hungarian (IH), which aims to solve the BP efficiently. Our algorithms have been shown to be effective through numerical results.