Brief announcement: uniform information exchange in multi-channel wireless ad hoc networks

Abstract

We consider a complete graph of n nodes, any pair of which can communicate with each other directly through one of F available wireless channels. n is not known to the nodes. Time is divided into synchronous rounds. In each round, a node can select at most one channel to listen to or transmit on. Transmission is successful if there is exactly one node transmitting on a channel (and one or more nodes listening). If two or more nodes transmit on the same channel, a collision occurs and their transmissions fail. Nodes can detect collisions, i.e., can distinguish collision from silence. We study distributed solutions to the information exchange problem: given initially k nodes each holding a packet, the task is to disseminate these k packets to all n nodes as quickly as possible. We assume that multiple packets can be packed in a single message. Recently, due to the advent of mobile devices that can operate on multiple channels, some attention has been given to studying the effect of multiple channels on improving communication [1–4]. However, all existing works require prior knowledge of n. In ad hoc networks, to make n known to all the nodes in fact can be a tough task. Moreover, in ad hoc networks, the value of n could change sporadically or even frequently due to nodes leaving and joining. Hence, there is practical need for designing uniform protocols that do not require any prior information about the network including n and k. Not knowing the parameters n or k greatly increases the difficulty of designing fast algorithms, especially in the case where different nodes can operate on different channels, as it is hard to manage the transmission probabilities over the distributed set of nodes.