Internal nodes based broadcasting in wireless networks

In a multi-hop wireless network, each node has a transmission radius and is able to send a message to one or all of its neighbors that are located within the radius. In a broadcasting task, a source node sends the same message to all the nodes in the network. Some existing solutions apply re-broadcasting from each cluster-head or border node in a clustered structure. We propose to reduce the communication overhead of the broadcasting algorithm by applying the concept of internal nodes. The maintenance of internal nodes requires much less communication overhead than the maintenance of the cluster structure of the nodes. In one-to-all broadcasting, only the internal nodes forward the message, while in the one-to-one case, messages are forwarded on the edges that connect two internal nodes and on edges that connect each non-internal node with its closest internal node. Existing notions of internal nodes are improved by using node degrees instead of their IDs in internal node decisions. Highest node degrees are also proposed for reducing the number of cluster-heads and border nodes in a clustering algorithm. Further savings are obtained if GPS and the concept of planar subgraphs are used for one-to-one networks. In case of one-to-all model, no re-broadcasting is needed if all neighbors have already received the message. The important features of the proposed algorithms are their reliability, significant savings in the re-broadcasting, and their localized and parameterless behavior. The reduction in the communication overhead for the broadcasting task, with respect to existing methods, is measured experimentally.