M.S. Thesis Presentation by Görkem Özdemir

M.S. Thesis Presentation by
Görkem Özdemir
Department of Industrial Engineering
Bilkent UniversityWireless Mesh Networks (WMNs) are wireless communication networks that consist of a finite number of radio nodes, in which a predetermined subset of nodes, called gateways, have wired connections to the Internet and the remaining ones transmit their traffic to a gateway node through the wireless media in a multi-hop fashion through the other nodes.

 

Wireless communication signals that propagate simultaneously within the same frequency band may interfere with one another at a receiving node and may therefore prevent successful transmission of data. In order to circumvent this problem, nodes on the network can be configured to receive and send signals in different time slots and through different frequency bands. Therefore, a transmission slot can be defined as a pair of a certain frequency band and a specific time slot. In addition, by adjusting the power level of a radio node, its transmission range can be modified.

Given a wireless mesh network with fixed node locations, demand rate at each node, and maximum power level for each node, we study the problem of carrying the traffic of each node to the Internet through the network. Our goal is to allocate capacities in proportion to the demand of each node in such a way that the minimum ratio is maximized. We propose a mixed integer linear programming (MILP) formulation to select a given number of gateway locations from among the nodes in the network, to determine the routing of the traffic of each node through the gateway nodes, to assign transmission slots to each node in order to ensure no interference among wireless signals, and to determine the transmission power levels. In our study, we adopt the more realistic physical interference model.

MILP formulation becomes computationally infeasible for larger instances, we propose several heuristic methods that can quickly find reasonably good solutions. The proposed heuristics simply approaches the problem in two steps. In both steps, easier MILP problems are solved. In the first step, a relaxed version of the proposed MILP is used to make routing decisions. Second step performs the transmission slot assignment with given results of the first step. We evaluate the performance of our methods on a number of data sets.

Keywords: Wireless Mesh Networks, Integer Programming, Gateway Selection, Routing, Transmission Slot Assignment.

 

This thesis is supervised by
Asst. Prof. Kağan Gökbayrak