Finding the Size of a Radio Network with Short Labels
Barun Gorain, Andrzej Pelc · 2018
The number of nodes of a network, called its size, is one of the most important network parameters. Knowing the size (or a good upper bound on it) is a prerequisite of many distributed network algorithms, ranging from broadcasting and gossiping, through leader election, to rendezvous and exploration. A radio network is a collection of stations, called nodes, with wireless transmission and receiving capabilities. It is modeled as a simple connected undirected graph whose nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node v hears a message from a neighbor w in a given round, if v listens in this round, and if w is its only neighbor that transmits in this round. If v listens in a round, and two or more neighbors of v transmit in this round, a collision occurs at v. If v transmits in a round, it does not hear anything in this round. Two scenarios are considered in the literature: if listening nodes can distinguish collision from silence (the latter occurs when no neighbor transmits), we say that the network has the collision detection capability, otherwise there is no collision detection.