SwePub
Sök i LIBRIS databas

  Extended search

onr:"swepub:oai:DiVA.org:liu-32514"
 

Search: onr:"swepub:oai:DiVA.org:liu-32514" > A Column Generation...

  • 1 of 1
  • Previous record
  • Next record
  •    To hitlist

A Column Generation Method for Spatial TDMA Scheduling in Ad Hoc Networks

Björklund, Patrik, 1970- (author)
Linköpings universitet,Tekniska högskolan,Institutionen för teknik och naturvetenskap
Värbrand, Peter, 1958- (author)
Linköpings universitet,Tekniska högskolan,Institutionen för teknik och naturvetenskap
Yuan, Di, 1970- (author)
Linköpings universitet,Tekniska högskolan,Kommunikations- och transportsystem
 (creator_code:org_t)
Elsevier BV, 2004
2004
English.
In: Ad hoc networks. - : Elsevier BV. - 1570-8705 .- 1570-8713. ; 2:Issue 4, s. 405-418
  • Journal article (peer-reviewed)
Abstract Subject headings
Close  
  • 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.

Keyword

Ad hoc networks; STDMA; Scheduling; Column generation
TECHNOLOGY
TEKNIKVETENSKAP

Publication and Content Type

ref (subject category)
art (subject category)

Find in a library

To the university's database

  • 1 of 1
  • Previous record
  • Next record
  •    To hitlist

Search outside SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Close

Copy and save the link in order to return to this view