File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Distributed (Δ+1)-coloring in the physical model

TitleDistributed (Δ+1)-coloring in the physical model
Authors
Issue Date2011
PublisherSpringer 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, 8-9 September 2011. In Lecture Notes in Computer Science, 2011, v. 7111, p. 145-160 How to Cite?
AbstractIn multi-hop radio networks, such as wireless ad-hoc 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 close-by 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 Δ + 1-coloring 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.
DescriptionLNCS 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 8-9, 2011 : revised selected papers
Persistent Identifierhttp://hdl.handle.net/10722/169314
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorYu, Den_US
dc.contributor.authorWang, Yen_US
dc.contributor.authorHua, Qen_US
dc.contributor.authorLau, FCMen_US
dc.date.accessioned2012-10-18T08:49:52Z-
dc.date.available2012-10-18T08:49:52Z-
dc.date.issued2011en_US
dc.identifier.citationThe 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011), Saarbrücken, Germany, 8-9 September 2011. In Lecture Notes in Computer Science, 2011, v. 7111, p. 145-160en_US
dc.identifier.isbn978-3-642-28208-9-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/169314-
dc.descriptionLNCS 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 8-9, 2011 : revised selected papers-
dc.description.abstractIn multi-hop radio networks, such as wireless ad-hoc 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 close-by 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 Δ + 1-coloring 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.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.titleDistributed (Δ+1)-coloring in the physical modelen_US
dc.typeConference_Paperen_US
dc.identifier.emailYu, D: dxyu@hku.hken_US
dc.identifier.emailHua, Q: huaqs@hku.hken_US
dc.identifier.emailLau, FCM: fcmlau@cs.hku.hk-
dc.identifier.authorityLau, FCM=rp00221en_US
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-28209-6_12-
dc.identifier.scopuseid_2-s2.0-84863179885-
dc.identifier.hkuros211548en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84857329794&selection=ref&src=s&origin=recordpage-
dc.identifier.volume7111-
dc.identifier.spage145en_US
dc.identifier.epage160en_US
dc.publisher.placeGermany-
dc.description.otherThe 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011), Saarbrücken, Germany, 8-9 September 2011. In Lecture Notes in Computer Science, 2011, v. 7111, p. 145-160-
dc.identifier.scopusauthoridYu, D=30767911100-
dc.identifier.scopusauthoridWang, Y=55010729000-
dc.identifier.scopusauthoridHua, QS=15060090400-
dc.identifier.scopusauthoridLau, FCM=7102749723-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats