An Algorithm Schema for Minimizing Broadcast Transmissions in Packet Radio Networks

摘要

In packet radio networks the broadcasting subnetwork required to reach a community of users can be substantially reduced through the algorithm schema presented. The algorithms given minimize the number of relay transmissions required to reach a given group of users in a broadcast network structure. The subnetwork produced by the algorithm schema also has the characteristic of minimizing the relay data to any user in the group. One algorithm gives a solution to the minimal cover problem (optimal except for a specific class of counterexamples) in polynomial time. Existing optimal algorithms are exponentially bounded in complexity. (Author)