Bounded information dissemination in multichannel

Authors: Yu Yan Dongxiao Yu Yuexuan Wang Jiguo Yu Francis C M Lau

Publish Date: 2014/10/17

Volume: 31, Issue: 3, Pages: 996-1012

PDF Link

Abstract

More and more wireless networks and devices now operate on multiple channels which poses the question How to use multiple channels to speed up communication In this paper we answer this question for the case of wireless adhoc networks where information dissemination is a primitive operation Specifically we propose a randomized distributed algorithm for information dissemination that is very near the optimal The general information dissemination problem is to deliver k information packets stored initially in k different nodes the packet holders to all the nodes in the network and the objective is to minimize the time needed With an eye toward the reality we assume a model where the packet holders are determined by an adversary and neither the number k nor the identities of packet holders are known to the nodes in advance Not knowing the value of k sets this problem apart from broadcasting and alltoall communication gossiping We study the information dissemination problem in singlehop networks with boundedsize messages We present a randomized algorithm which can disseminate all packets in Okfrac1mathcal F+frac1mathcal P+log 2n rounds with high probability where mathcal F is the number of available channels and mathcal P is the bound on the number of packets a message can carry Compared with the lower bound varOmega kfrac1mathcal F+frac1mathcal P the given algorithm is very close to the asymptotical optimal except for an additive factor Our result provides the first solid evidence that multiple channels can indeed substantially speed up information dissemination which also breaks the varOmega k lower bound that holds for singlechannel networks even if mathcal P is infinity

Keywords: