For designing broadcast protocols in mobile ad hoc networks (MANETs), one of the important goals is to reduce the rebroadcast packets redundancy while reaching all the nodes in network. In this paper, we propose a probabilistic broadcasting mechanism based on selfishness and additional coverage in MANETs. Our approach dynamically adjusts the rebroadcast probability according to the extra covered area and number of neighbor nodes. By these two factors, mobile hosts can be classified into three groups: normal, low selfishness, and high selfishness groups. The nodes in the normal group forward packets for other nodes with high probability, whereas the nodes in the low selfishness group rebroadcast packets with low probability and the nodes in the high selfishness group do not rebroadcast packets. We compared our approach with simple flooding and the fixed probabilistic approach. The simulation results show that the proposed schemes can significantly reduce the number of retransmissions by up to 40% compared simple flooding and fixed probabilistic scheme without significant reduction in the network reachability and end-to-end packet delay.
A mobile ad hoc network (MANET) is a network formed without central administration that consists of mobile nodes that use a wireless interface to send packet data. MANET is a special type of wireless mobile network in which mobile hosts can move and communicate with no aid of any established infrastructure. With no fixed infrastructure, the efficient use of a MANET’s resources is highly crucial for the successful communication between mobile nodes [1].
Broadcasting is used to transmit a message from a source to all the other nodes in the network. It is widely used to resolve many network layer problems. DNS lookups, exchange of control packets for management purposes, and routing discovery requests are some examples of broadcasting across the network. In a MANET in particular, due to host mobility, broadcasting can be applied to many areas, such as paging a particular host, sending an alarm signal, and finding a route to a particular host, etc. Several ad hoc network protocols assume that the broadcasting service is available [1,2].
Many schemes have been proposed for broadcasting in MANETs. The most straightforward broadcast mechanism used in MANETs is simple flooding (SF) [3]. In this approach, as in a wired network, each mobile host rebroadcasts received broadcast packets if they have not been received before. Packets that have already been received are discarded. Although SF is a very simplistic protocol, it has the virtue of being reliable, while requiring minimal state retention. Unfortunately, the large number of rebroadcast packets in SF often results in redundant messages, consuming valuable bandwidth and power as well as causing contention, collision, and packet loss. More sophisticated solutions such as probability-based, counter-based, distancebased, location-based, and neighbor knowledge-based approaches have been proposed to overcome the drawbacks of SF [4,5].
A probability-based approach depends upon a predefined fixed probability to determine whether the packets should be rebroadcast or not. One problem of the probabilistic approach is how to set the rebroadcast probability. It is demonstrated that the optimal rebroadcast probability is around 0.7. Intuitively, this value does not seem globally optimal regardless of the neighbors’ distance or density. For example, the mobile hosts close to the sender will have more neighbors whose coverage areas significantly overlap. Therefore, the rebroadcast probability of a node in a MANET should be set dynamically according to its circumstances [3].
Based on this observation, we propose a dynamic probabilistic broadcast approach, which is an improvement upon the blind fixed probabilistic broadcasting approach and can efficiently reduce broadcast redundancy in MANETs. The main idea of our approach is to reduce the number of unnecessary packets for broadcast in MANETs. The proposed algorithm in this paper dynamically calculates the rebroadcast probability according to the number of neighbor nodes and the extra coverage area of a mobile node. We use a scheme based on selfishness. Our approach dynamically adjusts the rebroadcast probability according to the extra covered area and number of neighbor nodes. Using these two factors, we categorize mobile hosts into three groups: normal nodes, low selfishness nodes, and high selfishness nodes. Normal nodes forward packets for other nodes with high probability, whereas low selfishness nodes rebroadcast packets with low probability, and high selfishness nodes do not rebroadcast packets. This is a hierarchical approach such that high selfishness nodes do not rebroadcast packets whereas most of the relaying node set is the set of normal nodes. We compared our approach with simple flooding and the fixed probabilistic approach. The simulation results show that these concepts significantly reduce the number of retransmissions without expansion of insignificant reduction in the network reachability and end-to-end packet delay.
The rest of this paper is organized as follows: in Section II, we introduce related works on broadcasting to provide a background on MANET. In Section III, we describe the probabilistic broadcasting mechanism based on selfishness and additional coverage in MANETs, highlighting the procedure of this approach. We evaluate and present the simulation results in Section IV. In Section V, conclusions are drawn and recommendations for future work are suggested.
One of the well-known solutions to routing in ad hoc networks is flooding, where every node in the network retransmits a message to its neighbors after receiving it. Although flooding is extremely simple and easy to implement, it can be very costly and can lead to serious problems, known as the broadcast storm problem. It is characterized by redundant packet retransmissions, network bandwidth contention, and collision. A simple solution to the broadcast storm problem is to send fewer redundant messages [1,2]. Ni et al. [1] studied the flooding protocol analytically and experimentally and showed that a rebroadcast can provide only 61% additional coverage and only 41% additional coverage on average over that already covered by the previous transmission. Therefore, rebroadcasts are very costly and should be used with caution [1,2,4].
Four deterministic schemes are described in [4]: probability-based, area-based, counter-based, and distancebased schemes. These schemes differ with regard to the criteria used in the decision for forwarding a message to its neighbors after receiving it. A probability-based scheme is a very simple way of reducing rebroadcasts. Every node rebroadcasts with a predefined probability
Kim et al. [6] introduced a dynamic probabilistic broadcasting approach with a coverage area and neighbors confirmation for MANETs. Their scheme combines a probabilistic approach with the area-based approach. A mobile host can dynamically adjust its forwarding probability according to its additional coverage in its neighborhood. The additional coverage is estimated by the distance from the sender. The simulation results showed that this approach generates fewer rebroadcasts than the flooding approach. It also incurs lower broadcast collision without sacrificing high reachability [7].
Zhang and Agrawal [8] have also described a dynamic probabilistic scheme, which uses a combination of probabilistic and counter-based schemes. The value of a packet counter does not necessarily correspond to the exact number of neighbors from the current host, since some of its neighbors may have suppressed their rebroadcasts according to their local rebroadcast probability [9].
Bani-Yassein et al. [10] proposed a dynamic probabilistic algorithm to improve network reachability and saved rebroadcast. The forwarding probability is determined by considering the network density and node movement. This is done based on locally available information and without requiring any assistance in the distance measurements or exact location of determination devices. The algorithm controls the frequency of rebroadcasts and thus might save network resources without affecting delivery ratios [9].
Khan et al. [7] proposed a coverage-based dynamically adjusted probabilistic forwarding scheme and compared its performance with simple flooding and fixed probabilistic schemes. The proposed scheme maintains the reachability of pure flooding while maintaining the simplicity of the probability-based schemes [11].
Although the goal of all of the above works is to minimize the number of retransmissions, none of them guarantee the best suited bounds of retransmissions. In general, neighbor knowledge methods perform better than areabased methods, while area-based methods perform better than probability-based methods. This is due to the complexity and increased overhead of the complex schemes. Our approach combines the advantages of probability-based, counter-based, and area-based approaches. It has higher throughput, better reachability, and lower latency compared to general probabilistic or area-based approaches. Moreover, it is simple enough for easy implementation. We describe the details of our approach in Section III.
The rebroadcast probabilities
In MANET, the same probabilities
which topologies frequently change. These changes include how sparse or dense a MANET is, or how far or near the nodes that receive the packets are from the sender. If these circumstances are not taken into consideration, the value of P might be set too small or large, and in the end, the reach-ability will be poor and a large quantity of rebroadcast packets will be generated. This kind of problem arises from the fact that every node has the same probability of rebroad-casting a message, regardless of the extra area covered.
In a MANET, the areas that neighboring nodes of a mobile node cover typically overlap. Manipulating the overlapping area between a node’s own coverage and its neighbors’ coverage is very important in reducing the number of duplicate route requests. After a node receives a message from its neighborhood, the additional area covered by its rebroadcast is a small fraction of its whole coverage area, as depicted by Fig. 1. Let
Ni et al. [1] showed that the maximum additional coverage area, denoted as MAX(
In a MANET, the mobile nodes have no motivation to share their resources with other nodes. As mobile nodes want to minimize unnecessary resource consumption and to maximize throughput of their own messages, they refuse to forward packets for other nodes and non-cooperative behavior arises. This kind of behavior is called selfishness. In order to reduce the number of rebroadcasts in a MANET, we introduce the concept of selfishness.
Fig. 2 shows the selfishness that is part of our approach. In Fig. 2, intuitively, it is better those nodes far away from the sender among the neighbors retransmit broadcast packets instead of nodes close to the sender. The nodes n_{1}, n_{2}, n_{3}, and n_{4} are geographically far away from sender node s, so it would be better that they act as relay nodes with a high retransmission probability. On the other hand, node n_{5} and n_{6} are geographically close to sender node s, and they may be shadowed from relay nodes with low retransmission probability. These nodes in the shadowed area, n_{5} and n_{6}, can be selfish, so that they can be alleviated from the burden of rebroadcasting a packet.
All of the mobile nodes in a MANET can be classified as normal or selfish nodes. Normal nodes rebroadcast packets for other nodes, while selfish nodes do not rebroadcast. However, selfish nodes may generate data packets and request the normal nodes to forward data for them. We propose probability broadcasting based on selfishness in a MANET. In order to determine whether a node is selfish or not, a node needs to observe the routing behavior of other nodes. A node can attempt to learn the threshold value and the period and optimize its behavior so that it refuses to cooperate the amount that the threshold value allows exactly.
We allow each node to choose different probabilities according to its distance from the sender. The distance from the sender to a node can be calculated from the sender’s transmission power level or global positioning system (GPS). In short, with our approach, each node examines how far it is from sender and determines its retransmission probability. It is better for the node that is further from the sender to have a high retransmission probability than to have a low probability. This means that a node that is geographically further from the sender may potentially act as a relay node for a node that is closer to the sender. Note that a node close to the sender might be selfish and alleviated from the rebroadcast burden in the extreme case. The advantage of the concept of selfishness is that the total rebroadcast traffic may be reduced. The drawback of this concept is that the network reachability may be adversely affected if all of the nodes in any cut set of the MANET graph are assigned to be selfish.
In the fixed probabilistic approach, the rebroadcast probability
The value of rebroadcast probability
We choose a predefined number of mobile nodes as selfish during the network set-up period. Our goal is to assign selfishness so that the set size of normal nodes is minimized while the connectivity constraint of the resultant network is probabilistically satisfied. The proposed algorithm dynamically calculates the value of rebroadcast probability
We assume that a mobile node is set as selfish or nonselfish during the set up period. Let
When a mobile node
If node
The main idea of this paper is to reduce the rebroadcasting number in the route discovery phase. Reduced rebroadcasting leads to a decrease in the network traffic and cuts down the probability of channel contention and packet collision. Since our algorithm is based on a probabilistic approach, it does not fit in every case of MANET. In this section, we evaluate the performance of our algorithm by comparing it with simple flooding and the fixed probabilistic broadcast algorithm.
There is a small chance that the broadcast packets cannot reach the destination in our probabilistic approach. The performance of broadcast protocols can be measured by a variety of metrics [6,10]. In this work, we used three measures: rebroadcast savings, average broadcast delay, and reachability and evaluated the performance by comparing it with simple flooding, fixed probability, and our approach. For simplicity, we assigned 0.7 as the probability of the fixed probability approach.
[Table 1.] Simulation parameters
Simulation parameters
To evaluate our scheme, we modified the ad hoc network simulator GloMoSim [13]. All the simulations were performed in a simulation area of 1,000 × 1,000 m, and the number of nodes was varied from 20 to 500. Our simulation parameters are shown in Table 1.
In this subsection, we evaluate the performance of our algorithm with regard to rebroadcast saving. We vary the traffic load by using different numbers of source-destination connections. In flooding, a mobile node rebroadcasts all routing request packets that are received for the first time. Therefore, there are
The rebroadcast probability
Fig. 4 shows rebroadcast saving of three approaches for route request when mobile nodes are not permitted to move in MANET. From Fig. 4, we can see that our approach can significantly reduce the number of rebroadcasts when the number of mobile nodes is large. The savings ranges from 30% to 40% compared with simple flooding.
As shown in Fig. 4, our improved algorithm can significantly reduce the number of rebroadcasts. As shown in the figure, the saving is higher when the traffic is heavier. This indicates that our algorithm is the most efficient among those tested.
The average end-to-end delay times taken for broadcast packets to reach destination node including transmission time and routing delay in the path are measured to compare the three algorithms for the delay of broadcast packet. The start time of broadcast packets and the time when they reach the last node are recorded. The difference between these two values is used as the delay of broadcast packets.
Fig. 5 shows the delay for different levels of traffic loads under the supposition of no node mobility. As expected, our proposed improved probabilistic algorithm displays lower delay than simple flooding or the fixed probabilistic approach. Since rebroadcasts can cause collision and possible contention for shared channels, our improved probabilistic approach incurs the lowest number of rebroadcasts, consequently generating the lowest delay.
The simple flooding approach guarantees that all mobile nodes can receive the broadcast packets at the expense of redundant rebroadcasting. However, in the probabilistic approach, some packets will be dropped according to their retransmission probability, which may cause some nodes to miss a broadcast packet.
The metric of reachability measures the proportion of nodes that can receive a broadcast packet.
Reachability is defined as
Fig. 6 shows the simulation results for reachability for a network of 20？500 nodes with the assumption of no host mobility. The flooding algorithm has the best performance with regard to reachability, reaching nearly 100% in the case of 500 node density. The performance of our improved probabilistic algorithm shows that the reachability is above 90% in the density of more than 100 nodes, so the reachability of our scheme performs better than the fixed probabilistic scheme. The figure shows that our improved probabilistic algorithm has higher reachability than the fixed probabilistic scheme and has nearly the same reachability as flooding in all network densities.
Broadcasting is an active research topic in MANETs. A significant problem is how to reduce the number of rebroadcast packets. Even though the large number of rebroadcasts guarantees high reachability, it causes high network bandwidth consumption and so many packet collisions occur. On the other hand, the lesser number of rebroadcasts results in low reachability, because it causes rebroadcast paths to be broken so that some mobile nodes may not receive the packets.
In this paper we introduced a probabilistic broadcasting approach based on selfishness and additional coverage for mobile hosts in MANETs. Our approach classifies mobile nodes into normal nodes and selfish nodes. Normal nodes relay packets with rebroadcast probability for others, while selfish nodes are divided into high or low selfishness. Low selfishness nodes relay packets with low rebroadcast probability and high selfishness nodes do not. The condition of these classifications is based on the number of neighbor nodes and additional coverage in MANETs.
The advantage of using selfish nodes is that the total rebroadcast traffic can be reduced. Using this method, we can reduce routing costs by minimizing the number of rebroadcasts in the route discovery phase, while achieving a higher delivery rate and lower end-to end delay. The disadvantage is that we may miss the optimal route and suffer from a low delivery rate. Simulation results show that our approach outperforms the AODV protocol in rebroadcast traffic. Compared with the simple flooding and fixed probabilistic approach, the simulation results showed that our probabilistic algorithm can improve the saved rebroadcast by up to 40% without sacrificing reachability.
We plan to build an analytic model for the dynamic probabilistic approach in order to facilitate the search for the optimal adaptation strategy. On the base of the analytic model, we should be able to obtain the proper value for using our scheme and predict the network performance with our approach in a MANET.