File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783642282096_12
 Scopus: eid_2s2.084863179885
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Distributed (Δ+1)coloring in the physical model
Title  Distributed (Δ+1)coloring in the physical model 

Authors  
Issue Date  2011 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011), Saarbrücken, Germany, 89 September 2011. In Lecture Notes in Computer Science, 2011, v. 7111, p. 145160 How to Cite? 
Abstract  In multihop radio networks, such as wireless adhoc and sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of closeby transmissions. These protocols can be implemented using standard node coloring. The (Δ + 1)coloring problem is to color all nodes in as few timeslots as possible using at most Δ + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Δ is the maximum degree of the modeled unit disk graph using the scaling factor R. Being one of the most fundamental problems in distributed computing, this problem is well studied and there are a long chain of algorithms for it. However, all previous work are based on models that are highly abstract, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice. In this paper, for the first time, we consider the distributed Δ + 1coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized (Δ + 1)coloring algorithm with time complexity O(Δlog n+log2 n). For the case where nodes can not adjust their transmission power, we give an O(Δlog2 n) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead. 
Description  LNCS v. 7111 has title: Algorithms for sensor systems: 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, Saarbrücken, Germany, September 89, 2011 : revised selected papers 
Persistent Identifier  http://hdl.handle.net/10722/169314 
ISBN  
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Yu, D  en_US 
dc.contributor.author  Wang, Y  en_US 
dc.contributor.author  Hua, Q  en_US 
dc.contributor.author  Lau, FCM  en_US 
dc.date.accessioned  20121018T08:49:52Z   
dc.date.available  20121018T08:49:52Z   
dc.date.issued  2011  en_US 
dc.identifier.citation  The 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011), Saarbrücken, Germany, 89 September 2011. In Lecture Notes in Computer Science, 2011, v. 7111, p. 145160  en_US 
dc.identifier.isbn  9783642282089   
dc.identifier.issn  03029743   
dc.identifier.uri  http://hdl.handle.net/10722/169314   
dc.description  LNCS v. 7111 has title: Algorithms for sensor systems: 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, Saarbrücken, Germany, September 89, 2011 : revised selected papers   
dc.description.abstract  In multihop radio networks, such as wireless adhoc and sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of closeby transmissions. These protocols can be implemented using standard node coloring. The (Δ + 1)coloring problem is to color all nodes in as few timeslots as possible using at most Δ + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Δ is the maximum degree of the modeled unit disk graph using the scaling factor R. Being one of the most fundamental problems in distributed computing, this problem is well studied and there are a long chain of algorithms for it. However, all previous work are based on models that are highly abstract, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice. In this paper, for the first time, we consider the distributed Δ + 1coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized (Δ + 1)coloring algorithm with time complexity O(Δlog n+log2 n). For the case where nodes can not adjust their transmission power, we give an O(Δlog2 n) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead.   
dc.language  eng  en_US 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/   
dc.relation.ispartof  Lecture Notes in Computer Science  en_US 
dc.rights  The original publication is available at www.springerlink.com   
dc.title  Distributed (Δ+1)coloring in the physical model  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Yu, D: dxyu@hku.hk  en_US 
dc.identifier.email  Hua, Q: huaqs@hku.hk  en_US 
dc.identifier.email  Lau, FCM: fcmlau@cs.hku.hk   
dc.identifier.authority  Lau, FCM=rp00221  en_US 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/9783642282096_12   
dc.identifier.scopus  eid_2s2.084863179885   
dc.identifier.hkuros  211548  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.084857329794&selection=ref&src=s&origin=recordpage   
dc.identifier.volume  7111   
dc.identifier.spage  145  en_US 
dc.identifier.epage  160  en_US 
dc.publisher.place  Germany   
dc.description.other  The 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011), Saarbrücken, Germany, 89 September 2011. In Lecture Notes in Computer Science, 2011, v. 7111, p. 145160   
dc.identifier.scopusauthorid  Yu, D=30767911100   
dc.identifier.scopusauthorid  Wang, Y=55010729000   
dc.identifier.scopusauthorid  Hua, QS=15060090400   
dc.identifier.scopusauthorid  Lau, FCM=7102749723   