Exact and heuristic approaches based on noninterfering transmissions for joint gateway selection, time slot allocation, routing and power control for wireless mesh networks

Kagan Gokbayrak*, E. Alper Yıldırım

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Wireless mesh networks (WMNs) provide cost-effective alternatives for extending wireless communication over larger geographical areas. In this paper, given a WMN with its nodes and possible wireless links, we consider the problem of gateway node selection for connecting the network to the Internet along with operational problems such as routing, wireless transmission capacity allocation, and transmission power control for efficient use of wired and wireless resources. Under the assumption that each node of the WMN has a fixed traffic rate, our goal is to allocate capacities to the nodes in proportion to their traffic rates so as to maximize the minimum capacity-to-demand ratio, referred to as the service level. We adopt a time division multiple access (TDMA) scheme, in which a time frame on the same frequency channel is divided into several time slots and each node can transmit in one or more time slots. We propose two mixed integer linear programming formulations. The first formulation, which is based on individual transmissions in each time slot, is a straightforward extension of a previous formulation developed by the authors for a related problem under a different set of assumptions. The alternative formulation, on the other hand, is based on sets of noninterfering wireless transmissions. In contrast with the first formulation, the size of the alternative formulation is independent of the number of time slots in a frame. We identify simple necessary and sufficient conditions for simultaneous transmissions on different links of the network in the same time slot without any significant interference. Our characterization, as a byproduct, prescribes a power level for each of the transmitting nodes. Motivated by this characterization, we propose a simple scheme to enumerate all sets of noninterfering transmissions, which is used as an input for the alternative formulation. We also introduce a set of valid inequalities for both formulations. For large instances, we propose a three-stage heuristic approach. In the first stage, we solve a partial relaxation of our alternative optimization model and determine the gateway locations. This stage also provides an upper bound on the optimal service level. In the second stage, a routing tree is constructed for each gateway node computed in the first stage. Finally, in the third stage, the alternative optimization model is solved by fixing the resulting gateway locations and the routing trees from the previous two stages. For even larger networks, we propose a heuristic approach for solving the partial relaxation in the first stage using a neighborhood search on gateway locations. Our computational results demonstrate the promising performance of our exact and heuristic approaches and the valid inequalities

Original languageEnglish
Pages (from-to)102-118
Number of pages17
JournalComputers and Operations Research
Early online date3 Oct 2016
Publication statusPublished - 1 May 2017

Keywords / Materials (for Non-textual outputs)

  • Heuristic method
  • k-opt hill climbing
  • Mixed integer linear programming
  • Wireless mesh network


Dive into the research topics of 'Exact and heuristic approaches based on noninterfering transmissions for joint gateway selection, time slot allocation, routing and power control for wireless mesh networks'. Together they form a unique fingerprint.

Cite this