Broadcast Protocols in Wireless Networks

A group of multiple nodes are cooperating with one another in order to achieve some objectives in distributed applications. In this paper, we would like to discuss how to broadcast messages to every node in a group which are interconnected in wireless networks. In order to reduce the number of messages in flooding protocols, only relay nodes forward messages as discussed in the MPR (Multi-Point Relay) protocol. Here, in one round, nodes covered by a root node are taken in the first- and second-neighbor nodes. By iterating rounds, a spanning tree covering every node is obtained. Here, nodes are selected in root-to-leaf manner. In this paper, we newly propose N²N³, N³N³, and MN³N³ broadcast protocols where third-neighbor nodes in addition to the first- and second-neighbor nodes are covered in one round. We consider two types of relay nodes, strong and weak ones, which broadcast messages with strongest wave intensity and unicast messages with weaker radio wave intensity, respectively. A root node is a strong one. A first-neighbor node of the root node is weak and second-neighbor node is strong. Thus, nodes forward messages alternately with strong and weaker radio wave intensity. In the proposed protocols, nodes are selected in leaf-to-root manner. In one round of the N²N³ protocol, relay nodes are first selected in second-neighbor nodes and then relay nodes in the first-neighbor nodes are selected. On the other hand, third-neighbor nodes are first selected as relay nodes and second-neighbor and first-neighbor nodes are selected as weak and strong relay nodes, respectively in one round of the N³N³ protocol. In the N²N³ protocol, every third-neighbor node may not be covered by a root node in each round while every third-neighbor node is covered in the N³N³ protocol.