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 p, where p = 1 activates simple flooding. In the area-based scheme, a node determines whether it should rebroadcast a packet or not by calculating its additional coverage area. Although the areabased scheme works quite well, it does not know if any nodes exist in the calculated coverage area. Therefore, some nodes may not receive broadcasting packets. In the counterbased scheme, the forwarding decision is based on the a threshold counter, c, and a time interval, t. Based on this scheme, a node that hears more than c copies over a time period, t, refrains from broadcasting the original request. Finally, the distance-based scheme bases the forwarding decision on a distance threshold, dmin, and time interval t. Based on this scheme, if the smallest distance of the neighbors heard during t is less than dmin, then retransmission is aborted [4,5].

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 p of all mobile nodes are fixed at the same value in the general probabilistic approach. However, the rebroadcast probabilities p need to be adjusted by the circumstances of the node [12]. We propose a new algorithm to combine the probabilistic and area schemes in order to exploit the advantages of both approaches. The object of our scheme is to minimize the number of transmissions and at the same time to improve the reliability of the packet delivery to all nodes.

In MANET, the same probabilities p in fixed probabilistic approaches cannot reflect the situation of MANETs, in

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 S_A and S_B denote the circle areas covered by A’s and B’s transmissions, respectively. In this figure, the shaded gray area, denoted as S_B-_A, represents the extra area covered by B’s rebroadcast after A’s broadcast. The relative distance between nodes, as opposed to location information, is sufficient to determine the additional coverage area. We can derive that

Ni et al. [1] showed that the maximum additional coverage area, denoted as MAX(S_B-_A), is 0.61πr², which is achieved when d = r. Whereas the average additional coverage area, denoted as AVG(S_B-_A), is 0.41πr². Thus, after the previous broadcast, a rebroadcast can cover only an additional 41% area on average. The area-based scheme succeeds in reaching a large part of the network but does not economize the number of broadcast messages because a host may have heard a broadcast message many times [12].

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₁, n₂, n₃, and n₄ 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₅ and n₆ 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₅ and n₆, 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 p is static for every node. In this scheme, when receiving a broadcast message for the first time, a node rebroadcasts the message with a predefined probability p. This scheme has poor reachability. The problem comes from the uniformity of the algorithm; every node has the same probability of rebroadcasting the packet, regardless of its number of neighbors.

The value of rebroadcast probability p is important in our approach. Note that in sparse networks, there is much less shared coverage; thus some nodes will not receive all the broadcast packets unless the probability parameter is high. Therefore, setting the rebroadcast probability p to a very small value will result in a poor reachability. On the other hand, if p is set to a very large value, many redundant rebroadcasts will be generated. The key problem of our approach is how to decide whether a mobile node should be selfish or not. A higher probability value leads to fewer selfish nodes, and hence more forwarded packets. A lower value means a larger number of selfish nodes and fewer forwarding packets. If the rebroadcast probability is too low, a broadcasting message may die out quickly. If the rebroadcast probability is too high, then there may be little improvement over the original flooding approaches.

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 p at each mobile host according to the number of its neighbor nodes. The value of p is different in different areas. In sparser areas, the rebroadcast probability is larger while in denser areas, the probability is lower. A higher value of p means a higher number of redundant rebroadcasts while a smaller value of p means a lower reachability. Consequently, the rebroadcast probability should be set differently from one node to another according to their local topological characteristics.

We assume that a mobile node is set as selfish or nonselfish during the set up period. Let S be the area space of an ad hoc network, N be the number of mobile nodes in the network, and r be the communication range. Let α be the fraction of the area a mobile node can cover to the whole network area. α can be obtained by following formula (2), and the average number of neighbors for a mobile node, N_avg, can be obtained by using the following formula (3).

When a mobile node B hears a broadcast packet from node A for the first time, it calculates the number of neighbors, N_nbr, and the additional coverage area, S_B-_A. For a node to have the characteristic of selfishness, we assume that the number of neighbors and the additional coverage area should meet the following criteria:

If node B satisfies the condition of (4) and (5), it can have high selfishness and need not retransmit broadcast packets over the air. Otherwise, if node B satisfies the condition of N_avg ≥ N_nbr or S_B-_A ≥ 0.41πr², B can have low selfishness and must retransmit broadcast packets over the air with low probability, that is, a value equal to or lower than 0.7. If node B satisfies the condition of N_avg ≥ N_nbr and S_B-_A ≥ 0.41πr², few neighbors exist around B, and B can cover a large additional coverage area. Therefore, B has to retransmit broadcast packets over the air with a high probability, that is, a value equal to or greater than 0.7. The boundary of high or low probability is 0.7, which is demonstrated as the optimal rebroadcast probability in [3]. The procedure of our approach, rebroadcasting based on selfishness and additional coverage, is specified in Fig. 3.

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.

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 N-1 possible rebroadcasts, where N is the total number of nodes. In the fixed probabilistic approach, each node n_i decides to rebroadcast or not according to a fixed probability P_i. Since their decisions are independent, the average number of rebroadcasts is

The rebroadcast probability P_i is dynamically adjusted according to the extra coverage area and neighbor density in our approach. The probability of a node that is far away from the sender and has a great deal of extra coverage is set to high and vice versa. Fig. 4 illustrates the saved rebroadcast (SRB) as the rebroadcast ratio for a network with 20？500 mobile nodes.

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 Nr / (N ？1), where Nr is the number of hosts receiving the broadcast packet and N is the total number of hosts in the MANET. For meaningful information, Nr should be those nodes that are part of a connected com-ponent in a MANET.

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.