liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Column Generation Method for Spatial TDMA Scheduling in Ad Hoc Networks
Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology.
Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology.
Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology, Communications and Transport Systems.
2004 (English)In: Ad hoc networks, ISSN 1570-8705, E-ISSN 1570-8713, Vol. 2, no Issue 4, 405-418 p.Article in journal (Refereed) Published
Abstract [en]

An ad hoc network can be set up by a number of units without the need of any permanent infrastructure. Two units establish a communication link if the channel quality is sufficiently high. As not all pairs of units can establish direct links, traffic between two units may have to be relayed through other units. This is known as the multi-hop functionality. In military command and control systems, ad hoc networks are also referred to as multi-hop radio networks. Spatial TDMA (STDMA) is a scheme for access control in ad hoc networks. STDMA improves TDMA by allowing simultaneous transmission of multiple units. In this paper, we study the optimization problem of STDMA scheduling, where the objective is to find minimum-length schedules. Previous work for this problem has focused on heuristics, whose performance is difficult to analyze when optimal solutions are not known. We develop novel mathematical programming formulations for this problem, and present a column generation solution method. Our numerical experiments show that the method generates a very tight bound to the optimal schedule length, and thereby enables optimal or near-optimal solutions. The column generation method can be used to provide benchmarks when evaluating STDMA scheduling algorithms. In particular, we use the bound obtained in the column generation method to evaluate a simple greedy algorithm that is suitable for distributed implementations.

Place, publisher, year, edition, pages
2004. Vol. 2, no Issue 4, 405-418 p.
Keyword [en]
Ad hoc networks; STDMA; Scheduling; Column generation
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-32514DOI: 10.1016/j.adhoc.2003.09.002Local ID: 18422OAI: oai:DiVA.org:liu-32514DiVA: diva2:253336
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2017-12-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Björklund, PatrikVärbrand, PeterYuan, Di

Search in DiVA

By author/editor
Björklund, PatrikVärbrand, PeterYuan, Di
By organisation
The Institute of TechnologyDepartment of Science and TechnologyCommunications and Transport Systems
In the same journal
Ad hoc networks
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 83 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf