25-04-2010, 11:49 AM
EFFICIENT BROADCASTING IN MOBILE ADHOC NETWORKS
Efficient Broadcasting in Mobile Ad Hoc Networks
Abstract:
This paper presents two efficient broadcasting algorithms based on 1-hop neighbor information. In the first part of the paper, we consider 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). Using flooding, each node receives the message from all its neighbors in a collision-free network. 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. We show that using our proposed receiver-based algorithm, two close neighbors are not likely to broadcast the same message. 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.
Existing system:
Broadcasting is a fundamental communication operation in which one node sends a message to all other nodes in the network. Broadcasting is widely used as a basic mechanism in many ad hoc network protocols. The simplest broadcasting algorithm is flooding, in which every node broadcasts the message when it receives it for the first time. Using flooding, each node receives the message from all its neighbors in a collision-free network. Therefore, the broadcast redundancy significantly increases as the average number of neighbors increases. High broadcast redundancy can result in high power and bandwidth consumption in the network. Moreover, it increases packet collisions, which can lead to additional transmissions. This can cause severe network congestion or significant performance degradation.
Proposed system:
In this paper, we propose two broadcasting algorithms based on 1-hop neighbor information. The first proposed algorithm is a sender-based algorithm. In sender based algorithms, the nodes select a subset of their neighbors to forward the message. We compare our proposed broadcasting algorithm to one of the best sender-based broadcasting algorithms that use 1-hop information. In receiver-based algorithms, the receiver decides whether or not to broadcast the message. The proposed receiver based algorithm is a novel broadcasting algorithm that can significantly reduce the number of broadcasts in the network. We show that using our proposed receiver based algorithm, two close neighbors are not likely to broadcast the same message. Based on our experimental results, the number of broadcasts using our receiver-based algorithm is less than one of the best known approximations for the minimum number of required broadcasts.
Efficient Broadcasting in Mobile Ad Hoc Networks
Abstract:
This paper presents two efficient broadcasting algorithms based on 1-hop neighbor information. In the first part of the paper, we consider 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). Using flooding, each node receives the message from all its neighbors in a collision-free network. 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. We show that using our proposed receiver-based algorithm, two close neighbors are not likely to broadcast the same message. 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.
Existing system:
Broadcasting is a fundamental communication operation in which one node sends a message to all other nodes in the network. Broadcasting is widely used as a basic mechanism in many ad hoc network protocols. The simplest broadcasting algorithm is flooding, in which every node broadcasts the message when it receives it for the first time. Using flooding, each node receives the message from all its neighbors in a collision-free network. Therefore, the broadcast redundancy significantly increases as the average number of neighbors increases. High broadcast redundancy can result in high power and bandwidth consumption in the network. Moreover, it increases packet collisions, which can lead to additional transmissions. This can cause severe network congestion or significant performance degradation.
Proposed system:
In this paper, we propose two broadcasting algorithms based on 1-hop neighbor information. The first proposed algorithm is a sender-based algorithm. In sender based algorithms, the nodes select a subset of their neighbors to forward the message. We compare our proposed broadcasting algorithm to one of the best sender-based broadcasting algorithms that use 1-hop information. In receiver-based algorithms, the receiver decides whether or not to broadcast the message. The proposed receiver based algorithm is a novel broadcasting algorithm that can significantly reduce the number of broadcasts in the network. We show that using our proposed receiver based algorithm, two close neighbors are not likely to broadcast the same message. Based on our experimental results, the number of broadcasts using our receiver-based algorithm is less than one of the best known approximations for the minimum number of required broadcasts.
