File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Distributed multiple-message broadcast in wireless ad-hoc networks under the SINR model
  • Basic View
  • Metadata View
  • XML View
TitleDistributed multiple-message broadcast in wireless ad-hoc networks under the SINR model
 
AuthorsYu, D1
Hua, Q
Wang, Y2
Tan, H2
Lau, FCM1
 
KeywordsArbitrary number
Broadcast algorithm
Broadcast protocols
Collision detection
High probability
 
Issue Date2012
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationThe 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Reykjavik, Iceland, 30 June-2 July 2012.In Lecture Notes in Computer Science, 2012, v. 7355, p. 111-122 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-31104-8_10
 
AbstractIn a multiple-message broadcast, an arbitrary number of messages originate at arbitrary nodes in the network at arbitrary times. The problem is to disseminate all these messages to the whole network. This paper gives the first randomized distributed multiple-message broadcast algorithm with worst-case performance guarantee in wireless ad-hoc networks employing the SINR interference model which takes interferences from all the nodes in the network into account. The network model used in this paper also considers the harsh characteristics of wireless ad-hoc networks: there is no prior structure, and nodes cannot perform collision detection and have little knowledge of the network topology. Under all these restrictions, our proposed randomized distributed multiple-message broadcast protocol can deliver any message m to all nodes in the network in O(D + k + log 2 n) timeslots with high probability, where D is the network diameter, k is the number of messages whose broadcasts overlap with m, and n is the number of nodes in the network. We also study the lower bound for randomized distributed multiple-message broadcast protocols. In particular, we prove that any uniform randomized algorithm needs Ω(D + k + log 2n/log log log n) timeslots to deliver k messages initially stored at k nodes to all nodes in the network. © 2012 Springer-Verlag.
 
DescriptionLNCS v. 7355 has title: Structural information and communication complexity: 19th International Colloquium, SIROCCO 2012 ... Proceedings
 
ISBN9783642311031
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-642-31104-8_10
 
DC FieldValue
dc.contributor.authorYu, D
 
dc.contributor.authorHua, Q
 
dc.contributor.authorWang, Y
 
dc.contributor.authorTan, H
 
dc.contributor.authorLau, FCM
 
dc.date.accessioned2012-10-18T08:49:48Z
 
dc.date.available2012-10-18T08:49:48Z
 
dc.date.issued2012
 
dc.description.abstractIn a multiple-message broadcast, an arbitrary number of messages originate at arbitrary nodes in the network at arbitrary times. The problem is to disseminate all these messages to the whole network. This paper gives the first randomized distributed multiple-message broadcast algorithm with worst-case performance guarantee in wireless ad-hoc networks employing the SINR interference model which takes interferences from all the nodes in the network into account. The network model used in this paper also considers the harsh characteristics of wireless ad-hoc networks: there is no prior structure, and nodes cannot perform collision detection and have little knowledge of the network topology. Under all these restrictions, our proposed randomized distributed multiple-message broadcast protocol can deliver any message m to all nodes in the network in O(D + k + log 2 n) timeslots with high probability, where D is the network diameter, k is the number of messages whose broadcasts overlap with m, and n is the number of nodes in the network. We also study the lower bound for randomized distributed multiple-message broadcast protocols. In particular, we prove that any uniform randomized algorithm needs Ω(D + k + log 2n/log log log n) timeslots to deliver k messages initially stored at k nodes to all nodes in the network. © 2012 Springer-Verlag.
 
dc.descriptionLNCS v. 7355 has title: Structural information and communication complexity: 19th International Colloquium, SIROCCO 2012 ... Proceedings
 
dc.description.otherThe 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Reykjavik, Iceland, 30 June-2 July 2012.In Lecture Notes in Computer Science, 2012, v. 7355, p. 111-122
 
dc.identifier.citationThe 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Reykjavik, Iceland, 30 June-2 July 2012.In Lecture Notes in Computer Science, 2012, v. 7355, p. 111-122 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-31104-8_10
 
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-31104-8_10
 
dc.identifier.epage122
 
dc.identifier.hkuros211538
 
dc.identifier.isbn9783642311031
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.scopuseid_2-s2.0-84864050802
 
dc.identifier.spage111
 
dc.identifier.urihttp://hdl.handle.net/10722/169307
 
dc.identifier.volume7355
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.subjectArbitrary number
 
dc.subjectBroadcast algorithm
 
dc.subjectBroadcast protocols
 
dc.subjectCollision detection
 
dc.subjectHigh probability
 
dc.titleDistributed multiple-message broadcast in wireless ad-hoc networks under the SINR model
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Yu, D</contributor.author>
<contributor.author>Hua, Q</contributor.author>
<contributor.author>Wang, Y</contributor.author>
<contributor.author>Tan, H</contributor.author>
<contributor.author>Lau, FCM</contributor.author>
<date.accessioned>2012-10-18T08:49:48Z</date.accessioned>
<date.available>2012-10-18T08:49:48Z</date.available>
<date.issued>2012</date.issued>
<identifier.citation>The 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Reykjavik, Iceland, 30 June-2 July 2012.In Lecture Notes in Computer Science, 2012, v. 7355, p. 111-122</identifier.citation>
<identifier.isbn>9783642311031</identifier.isbn>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/169307</identifier.uri>
<description>LNCS v. 7355 has title: Structural information and communication complexity: 19th International Colloquium, SIROCCO 2012 ... Proceedings</description>
<description.abstract>In a multiple-message broadcast, an arbitrary number of messages originate at arbitrary nodes in the network at arbitrary times. The problem is to disseminate all these messages to the whole network. This paper gives the first randomized distributed multiple-message broadcast algorithm with worst-case performance guarantee in wireless ad-hoc networks employing the SINR interference model which takes interferences from all the nodes in the network into account. The network model used in this paper also considers the harsh characteristics of wireless ad-hoc networks: there is no prior structure, and nodes cannot perform collision detection and have little knowledge of the network topology. Under all these restrictions, our proposed randomized distributed multiple-message broadcast protocol can deliver any message m to all nodes in the network in O(D + k + log 2 n) timeslots with high probability, where D is the network diameter, k is the number of messages whose broadcasts overlap with m, and n is the number of nodes in the network. We also study the lower bound for randomized distributed multiple-message broadcast protocols. In particular, we prove that any uniform randomized algorithm needs &#937;(D + k + log 2n/log log log n) timeslots to deliver k messages initially stored at k nodes to all nodes in the network. &#169; 2012 Springer-Verlag.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<subject>Arbitrary number</subject>
<subject>Broadcast algorithm</subject>
<subject>Broadcast protocols</subject>
<subject>Collision detection</subject>
<subject>High probability</subject>
<title>Distributed multiple-message broadcast in wireless ad-hoc networks under the SINR model</title>
<type>Conference_Paper</type>
<identifier.doi>10.1007/978-3-642-31104-8_10</identifier.doi>
<identifier.scopus>eid_2-s2.0-84864050802</identifier.scopus>
<identifier.hkuros>211538</identifier.hkuros>
<identifier.volume>7355</identifier.volume>
<identifier.spage>111</identifier.spage>
<identifier.epage>122</identifier.epage>
<publisher.place>Germany</publisher.place>
<description.other>The 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Reykjavik, Iceland, 30 June-2 July 2012.In Lecture Notes in Computer Science, 2012, v. 7355, p. 111-122</description.other>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Tsinghua University