Optimal channel choice for collaborative ad-hoc dissemination

Liang Hu, J-Y. L. Boudec, M. Vojnovic

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

314 Downloads (Pure)


Collaborative ad-hoc dissemination of information has been proposed as an efficient means to disseminate information among devices in a wireless ad-hoc network. Devices help in forwarding the information channels to the entire network, by disseminating the channels they subscribe to, plus others. We consider the case where devices have a limited amount of storage that they are willing to devote to the public good, and thus have to decide which channels they are willing to help disseminate. We are interested in finding channel selection strategies which optimize the dissemination time across the channels. We first consider a simple model under the random mixing assumption; we show that channel dissemination time can be characterized in terms of the number of nodes that forward this channel. Then we show that maximizing a social welfare is equivalent to an assignment problem, whose solution can be obtained by a centralized greedy algorithm. We show empirical evidence, based on Zune data, that there is a substantial difference between the utility of the optimal assignment and heuristics that were used in the past. We also show that the optimal assignment can be approximated in a distributed way by a Metropolis-Hastings sampling algorithm. We also give a variant that accounts for battery level. This leads to a practical channel selection and re-selection algorithm that can be implemented without any central control.
Original languageEnglish
Title of host publicationproceedings INFOCOM
Publication date2010
ISBN (Print)978-1-4244-5836-3
Publication statusPublished - 2010
Event29th IEEE International Conference on Computer Communications - San Diego, CA, United States
Duration: 15 Mar 201019 Mar 2010
Conference number: 29


Conference29th IEEE International Conference on Computer Communications
Country/TerritoryUnited States
CitySan Diego, CA
Internet address

Bibliographical note

Copyright 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.


Dive into the research topics of 'Optimal channel choice for collaborative ad-hoc dissemination'. Together they form a unique fingerprint.

Cite this