Main Article Content
Abstract
This paper presents two efficient broadcasting algorithms based on 1-hop neighbor information. In the first part of the paper, we consider sender-based broadcasting algorithms, specifically the algorithm proposed by Liu et al. In their paper, Liu et al. proposed a sender-based broadcasting algorithm that can achieve local optimality by selecting the minimum number of forwarding nodes in the lowest computational time complexity O(n log n), where n is the number of neighbors. We show that this optimality only holds for a subclass of sender-based algorithms. We propose an efficient sender-based broadcasting algorithm based on 1-hop neighbor information that reduces the time complexity of computing forwarding nodes to O(n). In Liu et al.’s algorithm, n nodes are selected to forward the message in the worst case, whereas in our proposed algorithm, the number of forwarding nodes in the worst case is 11. In the second part of the paper, we propose a simple and highly efficient receiver-based broadcasting algorithm. When nodes are uniformly distributed, we prove that the probability of two neighbor nodes broadcasting the same message exponentially decreases when the distance between them decreases or when the node density increases. Using simulation, we confirm these results and show that the number of broadcasts in our proposed receiver-based broadcasting algorithm can be even less than one of the best known approximations for the minimum number of required broadcasts.