File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1145/1400863.1400874
 Scopus: eid_2s2.065249127422
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Exact and approximate link scheduling algorithms under the physical interference model
Title  Exact and approximate link scheduling algorithms under the physical interference model 

Authors  
Keywords  Ad Hoc Networks Coloring Constraint Satisfaction Problem Counting InclusionExclusion Principle Link Scheduling Physical Interference Model Sensor Networks Sinr Wireless 
Issue Date  2008 
Citation  DialmPomc'08: Proceedings Of The Acm 5Th International Workshop On Foundations Of Mobile Computing, 2008, p. 4554 How to Cite? 
Abstract  Given n arbitrarily distributed singlehop wireless links, using the physical interference model, the objective is to minimize the scheduling length. This is an open problem (Problem 1) proposed by Locher et al. [21]. In this paper, we solve this open problem at the cost of moderately exponential time. Specifically, this paper gives two classes of exact and approximate link scheduling algorithms, one based on the somewhat straightforward link independent set covering, and the other on counting the number of set covers. Letp(n) denote the time of checking whether the spectral radius of an irreducible nonnegative matrix is smaller than 1 or not, then the time complexity for the set covering based exact algorithm isO(2 n/ 2)), whereas the proposed counting based exact scheduling algorithm called ESAMLSAT needs only time O(3n • n ■ log 2 n ■ p(n)) with polynomial space. If exponential space is allowed, the time complexity can be further reduced to O(2n ■ n ■ log 2 n ■ p(n)). The time complexity for the set covering based approximate algorithm is O(( n n/2)logn ■ p(n)) with approximation ratio O(logn) . The time complexity of the first counting based approximation algorithm is O(n 2polylog(n)) with approximation ratio O(nlog n), the time complexity of the second counting based approximation algorithm is O(n 1+og3' og n polylog(n)) with approximation ratio O(njlog n), and the time complexity of the third counting based approximate algorithm is O((( n n/2) + 3 e n•n• logn)lognp(n)) with approximation ratio (1 + s). All these approximation algorithms use polynomial space. © 2008 ACM. 
Persistent Identifier  http://hdl.handle.net/10722/151946 
References 
DC Field  Value  Language 

dc.contributor.author  Hua, QS  en_US 
dc.contributor.author  Lau, FCM  en_US 
dc.date.accessioned  20120626T06:31:19Z   
dc.date.available  20120626T06:31:19Z   
dc.date.issued  2008  en_US 
dc.identifier.citation  DialmPomc'08: Proceedings Of The Acm 5Th International Workshop On Foundations Of Mobile Computing, 2008, p. 4554  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/151946   
dc.description.abstract  Given n arbitrarily distributed singlehop wireless links, using the physical interference model, the objective is to minimize the scheduling length. This is an open problem (Problem 1) proposed by Locher et al. [21]. In this paper, we solve this open problem at the cost of moderately exponential time. Specifically, this paper gives two classes of exact and approximate link scheduling algorithms, one based on the somewhat straightforward link independent set covering, and the other on counting the number of set covers. Letp(n) denote the time of checking whether the spectral radius of an irreducible nonnegative matrix is smaller than 1 or not, then the time complexity for the set covering based exact algorithm isO(2 n/ 2)), whereas the proposed counting based exact scheduling algorithm called ESAMLSAT needs only time O(3n • n ■ log 2 n ■ p(n)) with polynomial space. If exponential space is allowed, the time complexity can be further reduced to O(2n ■ n ■ log 2 n ■ p(n)). The time complexity for the set covering based approximate algorithm is O(( n n/2)logn ■ p(n)) with approximation ratio O(logn) . The time complexity of the first counting based approximation algorithm is O(n 2polylog(n)) with approximation ratio O(nlog n), the time complexity of the second counting based approximation algorithm is O(n 1+og3' og n polylog(n)) with approximation ratio O(njlog n), and the time complexity of the third counting based approximate algorithm is O((( n n/2) + 3 e n•n• logn)lognp(n)) with approximation ratio (1 + s). All these approximation algorithms use polynomial space. © 2008 ACM.  en_US 
dc.language  eng  en_US 
dc.relation.ispartof  DIALMPOMC'08: Proceedings of the ACM 5th International Workshop on Foundations of Mobile Computing  en_US 
dc.subject  Ad Hoc Networks  en_US 
dc.subject  Coloring  en_US 
dc.subject  Constraint Satisfaction Problem  en_US 
dc.subject  Counting  en_US 
dc.subject  InclusionExclusion Principle  en_US 
dc.subject  Link Scheduling  en_US 
dc.subject  Physical Interference Model  en_US 
dc.subject  Sensor Networks  en_US 
dc.subject  Sinr  en_US 
dc.subject  Wireless  en_US 
dc.title  Exact and approximate link scheduling algorithms under the physical interference model  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Lau, FCM:fcmlau@cs.hku.hk  en_US 
dc.identifier.authority  Lau, FCM=rp00221  en_US 
dc.description.nature  link_to_subscribed_fulltext  en_US 
dc.identifier.doi  10.1145/1400863.1400874  en_US 
dc.identifier.scopus  eid_2s2.065249127422  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.065249127422&selection=ref&src=s&origin=recordpage  en_US 
dc.identifier.spage  45  en_US 
dc.identifier.epage  54  en_US 
dc.identifier.scopusauthorid  Hua, QS=15060090400  en_US 
dc.identifier.scopusauthorid  Lau, FCM=7102749723  en_US 