Optimal Channel Choice for Collaborative Ad-Hoc Dissemination
Authors:
- Milan VojnoviaeMVMilan Vojnoviae
Open Access
- 1 March 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 1-9
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Characterizing podcast services2009
- The age of gossip2009
- Power law and exponential decay of inter contact times between mobile devices2007
- Wireless Ad Hoc Podcasting2007
- First Experience with CarTorrent in a Real Vehicular Ad Hoc Network Testbed2007
- Measurement-Based Self Organization of Interfering 802.11 Wireless Access Networks2007
- Markov Chains1999
- The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for OptimalityOperations Research, 1986