STDMA tabanlı tek-kanallı kablosuz örgü ağlarda birleşik link/paket planlaması, hız ataması ve yönlendirme eniyilemesi

Wireless Mesh Networks (WMN) are a promising solution for next generation wireless access networks since they cherish benefits of having a reliable backbone in an ad hoc nature. This thesis investigates the joint scheduling and routing problem in minimizing the maximum delay required for delivering a given packet traffic to the intended destinations in spatial reuse Time Division Multiple Access (STDMA) based single channel multi-rate WMNs. Firstly, an Integer Linear Programming (ILP) model is developed by considering the constraints inherent to the problem, such as the Signal-to-Noise and Inteference Ratio (SINR) and capacity. The model is then improved by using additional constraints, such that these constraints do not affect the final solution but narrow down the search space. Because of the computational complexity, this ILP based optimization model is limited to small sized networks. We then consider different approaches to obtain sub-optimum solutions and find good lower and upper bounds on the optimum solution. LP and Lagrangian relaxations are used for obtaining lower bounds. Improving LP relaxation with cutting planes and Lagrangian relaxation, we obtain lower bounds that are up to 100% tighter than the simple LP relaxation. Next, a greedy heuristic approach is employed as an upper bounding technique. Tabu Search technique is implemented to improve the upper bound provided by the greedy approach, and around 10 - 20% tighter bounds are obtained. The sub-optimum solutions obtained by using the heuristic Tabu Search algorithm are shown to provide maximum delays that are within 10 -50% of the bounds obtained by using the cutting planes and Lagrangian relaxation for the networks considered in this thesis.