Algorithmic problems in radio networks

We investigate algorithmic aspects of communication protocols in multi-hop packet radio networks and the multiple access channel. Radio networks model wireless data communication with arbitrary topology of direct transmissions when the bandwidth is limited to one wave frequency. A multiple-access channel is a system in which a transmission delivers the message to all nodes. Both these types of networks share the property that multiple packets arriving simultaneously at a node result in mutual interference, which prevents receiving the messages successfully by any among the recipients.; The fundamental algorithmic goal for networks is to implement useful communication tasks. We consider broadcasting and gossiping among such primitives. The static broadcast problem is about a scenario in which one source node generates input data that need to be disseminated among all the nodes. In the dynamic broadcast problem, input data are continuously injected into the nodes and next are disseminated. The gossip problem starts with all the nodes holding their individual input data (called rumors), and the goal is for all the nodes to learn all the rumors.; For multi-hop radio networks, we initiate an approach to study asynchrony. We investigate the complexity of static broadcasting in such a setting. Specific results on gossiping in multi-hop radio networks concern upper and lower bounds on the time of gossiping, in both the worst-case and average aspects.; For the multiple-access channel, we introduce a framework to study stability of deterministic broadcasting protocols in adversarial settings. Stability means that the number of packets in queues is bounded in any execution. We consider natural classes of protocols and study stability-related issues for the channels with and without collision detection depending on the rates and burstiness of injection of packets.