File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Distributed multiple-message broadcast in wireless ad-hoc networks under the SINR model

TitleDistributed multiple-message broadcast in wireless ad-hoc networks under the SINR model
Authors
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/
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 How to Cite?
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
Persistent Identifierhttp://hdl.handle.net/10722/169307
ISBN
ISSN
2014 SCImago Journal Rankings: 0.339

 

DC FieldValueLanguage
dc.contributor.authorYu, Den_US
dc.contributor.authorHua, Qen_US
dc.contributor.authorWang, Yen_US
dc.contributor.authorTan, Hen_US
dc.contributor.authorLau, FCMen_US
dc.date.accessioned2012-10-18T08:49:48Z-
dc.date.available2012-10-18T08:49:48Z-
dc.date.issued2012en_US
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-122en_US
dc.identifier.isbn9783642311031-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/169307-
dc.descriptionLNCS v. 7355 has title: Structural information and communication complexity: 19th International Colloquium, SIROCCO 2012 ... Proceedings-
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.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.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 modelen_US
dc.typeConference_Paperen_US
dc.identifier.emailYu, D: dxyu@hku.hken_US
dc.identifier.emailHua, Q: huaqs@hku.hken_US
dc.identifier.emailWang, Y: amywang@hku.hk-
dc.identifier.emailTan, H: hstan@HKUSUA.hku.hk-
dc.identifier.emailLau, FCM: fcmlau@cs.hku.hk-
dc.identifier.authorityLau, FCM=rp00221en_US
dc.identifier.doi10.1007/978-3-642-31104-8_10-
dc.identifier.scopuseid_2-s2.0-84864050802-
dc.identifier.hkuros211538en_US
dc.identifier.volume7355-
dc.identifier.spage111en_US
dc.identifier.epage122en_US
dc.publisher.placeGermany-
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-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats