The Density Based Probabilistic Counter Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Broadcasting is a fundamental data dissemination mechanism for route detection, address resolution and many other networks related services in Mobile Ad hoc Networks (MANETs). Although flooding is the simplest mechanism for broadcasting, where each node retransmits every individually received message exactly once, it is usually expensive and results in rigorous redundancy, contention and collisions in the network. These problems are widely referred to as the broadcast storm problem. Hence, an effective broadcasting scheme is essential in MANETs to transmit a data packet from the sender to the rest of the network nodes. This work introduces a new counter-based broadcasting scheme to achieve efficient broadcasting by adaptive threshold with a predetermined forwarding probability 'p' which can be fixed based on the local density information. The counter identifies nodes with duplicate data packet using threshold values and node removes the redundant message. Probabilistic schemes do not require global topological information of the network to make a rebroadcast decision. As such, every node is allowed to rebroadcast a message. The proposed work also adapts the random assessment delay (RAD) value to network congestion level and uses packet origination rate as an indicator of network congestion by keeping track of the number of packets received per second at each node. The extensive simulation results show that the new scheme outperforms the existing schemes in terms of saved-rebroadcast, reach ability and latency.

Keywords: MANETs, Flooding, Counter-based, Broadcast storm problem, Throughput, Reachability, Latency

1. Introduction

In recent years, mobile ad hoc network (MANET) has gained a lot of attention because of its self-organising and infrastructure-free characteristics. Unlike the traditional wireless networks, each node in MANET can act as a router to receive and forward packets. All nodes can randomly move around, leave the network or switch off. Hence, broadcasting has been widely used in diffusing data, routing or topology information in MANET. There are number of characteristics in MANET such as mobility services, no infrastructure and battery-powered properties make it used in a number of applications for MANET. MANET is widely used in military, emergency operations, group communication, battle-fields, and disaster recovery. MANETs can be very useful in setting up an infrastructure-less network used to make a reliable and fast communication among soldiers in the battle-fields to recover any failure in the network.

The mobile ad hoc network (MANET) has been an active research area in recent years. Routing [2,3] in a MANET is more difficult than the traditional wireless networks because of the nature of dynamic changing topology of the MANET. Thus, broadcasting is a common and important operation in MANETs for route judgment, and it could be performed frequently. The simplest solution for broadcasting is blind flooding in which every node rebroadcasts a message when the message is received at the first time. However, it has been pointed out in a number of articles [5-8] that blind flooding is improper in MANETs since it brings in lots of duplicate messages and consumes much network resources. Lots of duplicate messages imply serious redundancy in message transmissions and also lead to much contention and collision in mobile wireless networks, which is identified as the broadcast storm problem. Several solutions for reduction of the broadcast storm problem in MANETs has been proposed in the literature [7-12]. The two widely used mechanisms are sender-based and receiver-based. In sender based mechanisms, the originator of a broadcast packet determines the relay nodes from its neighbours to rebroadcast the packet. Each node in the set of relay nodes further determines its relay nodes when receiving the broadcast packet from the originator, and so forth. In receiver-based mechanisms, a mobile node that has received a broadcast packet determines by itself whether or not to rebroadcast the packet. Qayyum et al. [10] proposed a sender-based mechanism called multipoint relay (MPR) for efficient broadcasting. The MPR technique restricts the number of retransmissions by selecting a small subset of neighbours which covers (in terms of one-hop radio range) the same network region that the complete set of neighbours does.

Ad hoc On-Demand Distance Vector Routing (AODV) is an on-demand protocol used to provide the route discovery and maintenance in a wide variety of network topologies and environments and to achieve improved performance, robustness and better scalability. Route Maintenance is a mechanism used to repair routes when they are invalidated or have broken links, so this error propagated to neighbours that have used this node as their next hop. The main feature of AODV is its ability to use a target series number for each route entry created by the destination for any route information sending to requesting nodes with loop freedom and this requesting node always selects the node with the greatest sequence number. This protocol works on wired and wireless media. In AODV, the neighbouring nodes can detect each other's broadcasts by using symmetric links connecting adjacent nodes. It does not go to follow paths between nodes when one of these nodes cannot listen to the other one [9].

The probabilistic broadcast includes counter-based, location-based, distance-based and hybrid-based schemes. In counter-based schemes, messages are rebroadcast only when the number of copies of the message received at a node is less than a threshold value. In the location-based scheme, messages are rebroadcast only when the additional coverage concept [11] determines the location of the mobile nodes to broadcast. In distance-based scheme messages are rebroadcast according to the decision made between the relative distance of mobile node and the previous sender. In cluster-based scheme, the network is divided into number of clusters; each cluster has a single cluster head and several gateways. Each cluster head, in turn, acts as a source for rebroadcast within its own cluster and the gateways can communicate with external clusters and are responsible for transmitting the broadcast message externally. Hybrid schemes [12,13] combine between the advantages of probabilistic and counter-based schemes to achieve the performance improvement. The second category is known as a deterministic broadcast scheme and includes multipoint relaying [14], node-forwarding [15], neighbour elimination [16], and clustering [17]. Deterministic schemes use network topological information to build a network including all the nodes in the network, so every node needs to exchange its information. Probabilistic schemes do not use any information from network but, rather, start of building a network with each broadcast domain. Ni et al. [18] proposed several receiver-based solutions for the broadcast storm problem: the counter-based, distance-based, and location-based scheme. These schemes rely on various threshold mechanisms which help a mobile node to decide whether to rebroadcast or not. Adaptive versions of the scheme are also proposed [4] in which the threshold values are dynamically chosen according to the number of neighbors of a mobile node. It has been shown that if location information is available through devices such as GPS receivers, the adaptive location-based scheme (ALB) is the best choice among threshold-based scheme in terms of saved broadcast and reachability.

2. Related Work

Over the years, several schemes have been proposed to address the broadcast storm problem in wireless networks. Tseng et al. (2002) have suggested some of the fascinating approaches, which are the following: (i) Counter-based scheme: To mitigate broadcast storms, this scheme uses a threshold C and a counter c to keep track of the number of times the broadcast message is received. Whenever c ≥C, rebroadcast is inhibited. (ii) Distance-based scheme. In this scheme, authors use the relative distance d between vehicles to decide whether to rebroadcast a message or not. It is demonstrated that when the distance d between two vehicles is short, the additional coverage (AC) of the new rebroadcast is lower, and rebroadcasting the warning message is not recommended. If d is larger, the additional coverage will also be larger. (iii) Location-based scheme is similar to the distance-based scheme, though it is required more precise locations for the broadcasting vehicles to achieve an accurate geometrical estimation (with convex polygons) of the AC of a warning message.

The probabilistic approach has been proposed in [10,18] as a mechanism to reduce redundant rebroadcast messages. Probabilistic approach works as follows: when receiving a packet, each node forwards the packet with probability p. Ni et al. [18] have proposed a probability-based scheme to reduce the redundant rebroadcast packets like flooding and counter-based schemes. Every node in flooding is rebroadcast with a fixed probability P. On the other hand, counter-based scheme is proposed with additional coverage of each rebroadcast when receiving n redundant messages of the same packet. Zhang and Agrawal in [19] proposed a Dynamic probabilistic broadcast scheme as a combination of the probabilistic and counter-based approaches. The scheme is implemented using AODV protocol. Cartigny and Simplot in [11] proposed the probabilistic scheme as a combination of the advantages of probability-based and distance-based schemes. A counter-based scheme which works as follows: when receiving a packet, the node initiates a counter and a timer. The counter is increased by one for each received redundant packet. When the timer expired, if the counter is larger than a threshold value, the node will not retransmit the message; otherwise, the node will broadcast it.

3. Issues

To lessen the broadcast storm problem, reference [18] suggests two directions: to restrain redundant rebroadcasts and to make a distinction between the timing of rebroadcasts. In counter-based scheme, when c reaches a predefined threshold C, the host is inhibited from rebroadcasting this packet because the additional coverage could be low. It provides significant saving when a small threshold is used. A larger threshold will provide less saving in a sparse network but behave almost like flooding. In location-based scheme, a predefined threshold is used to determine whether the receiving host should rebroadcast or not. Since added accurate information is used, the location-based scheme can attain better performance in terms of both reachability and the quantity of saving than the counter-based scheme. However, one problem with the schemes in is that the threshold used is a predefined fixed value. These schemes are referred to as fixed-threshold solutions. This poses a dilemma between reachability and the amount of saving on rebroadcasts as the host distribution of the MANET changes.

4. The proposed scheme

In this section, we present a new counter-based scheme which is used to reduce the contention and collision problems associated with conventional counter-based approaches. A new counter-based broadcasting scheme is proposed to achieve efficient broadcasting by adaptive threshold with a predetermined forwarding probability 'p' which can be fixed based on the local density information. The counter identifies nodes with duplicate data packet using threshold values and node removes the redundant message. This probabilistic approach does not need global topological information of the network to make a rebroadcast decision. Here every node is allowed to rebroadcast a message .The use of this scheme is to facilitate the mobile nodes to rebroadcast a message if the number of received duplicate packets is less than a threshold by taking into account the status of the node density.

To resolve the dilemma between reachability and saving, we propose a new counter-based scheme in which each individual host can dynamically adjust its threshold C based on its neighbourhood status. After waiting for a random assessment delay (RAD), which is arbitrarily chosen between 0 and Tmax seconds, if c reaches a predefined threshold C, the node does not rebroadcast the received packet. Otherwise, if c is less than the predefined threshold C, the packet is rebroadcast with a probability P (based on local density information) as against automatically rebroadcasting the message in a counter- based scheme. The algorithm for the proposed probabilistic based adaptive threshold scheme is shown in Fig. 1.

Protocol receiving ()

1. On hearing a broadcast packet m at node X:

2. Get the Broadcast ID from the message; n1 minimum numbers of neighbor, n2

maximum number of neighbor, all are threshold values;

3. Obtain the number of neighbors of node X);

4. If packet m received initially then

5. If n < =n1 then

6. Node X has a threshold value c=1

7. Else

8. Generate a random number between [0, 1]

9. Timer = 1

10. While (the message not hearing to start the transmission) Do

11. Wait for a random number of slots until the transmission is actually starts.

12. End while

13. Increment the counter-threshold

14. If (counter-threshold< threshold) Go to 11

15. Else exit algorithm

Fig. 1. Algorithm for the proposed probabilistic based adaptive threshold scheme

The use of a rebroadcast probability stems from the fact that packet counter value does not unavoidably correspond to the exact number of neighbours of a node, since some of its neighbours may have concealed their rebroadcast according to their local rebroadcast probability. Therefore, to adapt Tmax to congestion levels, each node keeps track of the number of packets received per second. Thus, each host will use a threshold C depending on its current value of n to determine whether to rebroadcast or not. There should be a neighbour discovery mechanism to estimate the current value of n. This can be achieved through periodic exchange of 'HELLO' packets among mobile nodes. Each host now executes the following steps:

S1. On hearing a broadcast packet P for the first time, the host initializes a local counter c =1.

S2. Wait for a random number (0 to 44) of slots. Then, submit P for transmission and wait until the transmission actually starts. However, during the waiting, if P is heard again, interrupt the waiting and go to S4.

S3. Packet P is on the air. The procedure exits.

S4. Increase c by one. If c < C, resume the interrupted waiting in S2. Otherwise, proceed

to S5.

S5. Adapt the RAD value to network congestion level and uses packet origination rate as an indicator of network congestion by keeping track of the number of packets received per second at each node.

S6. Cancel the transmission of P. The host is inhibited from rebroadcasting P in the future. Then, the procedure exits.

Essentially, the selection of an fitting RAD time plays a crucial role in the performance of any broadcast scheme that employes the use of counter. In the original counter-based scheme, each node is assigned a preset constant value RAD_Tmax which is used to decide RAD value at random. Thus, node does not utilize any network information such as congestion or number of neighbours in determining this value. Normally, in MANETs, congestion can be achieved by increasing the packet size or increasing the packet generation rate or both. However, in this paper we choose to fix the packet size but vary the packet generation rate because we anticipate that broadcast packets, as control type packets, to be generally small in size. Therefore, to adapt ECS's RAD Tmax to congestion levels, each node keeps track of the number of packets received per second. Table 1 provides the average packet reception rate for ECS given various packet origination rates in a network with 45 nodes.

Each data point represents an average of 30 different randomly generated mobility scenarios with 95% confidence interval. The error bars in the graphs represent the upper and lower confidence limits from the means and in most cases they have been found to be quite small. For the sake of clarity and tidiness, the error bars have not been included in some of the graphs. We evaluate the broadcast schemes using the following performance metrics:

• Reachability (RE) - The percentage of network mobile nodes that receive a given broadcast

packet over the total number of nodes that are reachable, directly or indirectly .

• Saved Rebroadcast (SRB) - This is defined as (r - t)/r, where r and t are the number of nodes

that received the broadcast message and the number of nodes that transmitted the message


• End-to-end delay - is the average time difference between the time a data packet is sent by the

source node and the time it is successfully received by the last node in the network.

5. Performance Analysis

In order to verify the effect of the RAD adaptation, numerous simulations have been performed using the proposed scheme, counter-based, and flooding, and the results are compared in these three approaches. The performance analysis is based on the assumptions widely used in literature [2, 20].

1. All nodes are identical and equipped with IEEE 802.11 transceivers with the same nominal transmission range.

2. All nodes participate fully in the protocol of the network. In particular, each participating node should be willing to forward packets to other nodes in the network.

3. The number of nodes in a given topology remains fixed throughout the simulation time.

4. Each node has sufficient power to function throughout the simulation time.

The distributed coordination function (DCF) of the IEEE 802.11 protocol [22] is utilized as MAC layer protocol while random waypoint model [23] is used as the mobility model. In a random waypoint mobility model, each node at the beginning of the simulation remains stationary for a pause time seconds, then chooses a random destination and starts moving towards it with a randomly selected speed. After the node reaches its destination, it again stops for a pause-time interval and chooses a new destination and speed. This cycle repeats until the simulation terminates. The simulation is allowed to run for 900 seconds for each simulation scenario. Other simulation parameters, which have been used in our experiment, are shown in Table 1.

Table 1 Simulation parameters.

Simulation Parameter

Parameter Value


Transmission range


Interface queue length

Packet size

Traffic type

Packet rate

Topology size

Number of nodes

Number of trials

Simulation time

Maximum speed

Counter threshold (C)

RAD Tmax

NS-2 (v.2.29)

100 meters

2 Mbps


512 byte


10 packets/sec

600 x 600 m2



900 sec

20 m/s


0.01 seconds

5.1. Effects of offered traffic load simulation

Like the previous studies, the offered traffic load simulation is done by changing the number of Constant Bit Rate (CBR) connections. This CBR connection ensures that all packets transmission is maintained from source to destination. This service type is used for multimedia application that requires a little or no packet loss and accurate timing controls during broadcast. The numbers of CBR connections that are considered in the experiments are 10, 20, 30 and 45 for the number of nodes. The maximum speed 20 m/s is chosen to study the effects of traffic load in the network with high speed. When the speed is high, the traffic load is concentrated on some nodes so the congestion is occurred.

The simulation parameters of this experiment are set as follows:

Number of nodes: 45

Maximum speed: 20 m/s.

Packet rate: 4 packets/second.

5.2. Normalized Routing Load (NRL)

Fig. 2 shows the results of the normalized routing load vs. the network sizes (number of connections) for all the three schemes. Apparently, this figure shows that increases in connections tend not to lead to noticeable increase in the NRL using our proposed scheme. When the traffic load increases, there exist many connections between any nodes used to reach to the destination, so we choose one of these connections. Most of the generated data packets and connections are dropped resulting from collisions and contention. Nevertheless, our proposed scheme will decrease the NRL over the traffic load percentage against other schemes and show better performance up to 30%. This is because the flooding sends the packets to all nodes continuously without checking if these nodes receive this packet in previous time; thus, this causes a collision and contention in the network leading to additional load on the network.

Fig. 2 normalized routing load vs. the network sizes

5.3. Average end-to-end delay

Fig. 3 represents the delays of all schemes for different traffic loads. The delay is increased as the traffic load grows. The number of packets transmitted on the network has a considerable impact on delay. When the number of CBR connections increases, the number of collisions, contentions and redundant rebroadcast packets grows. Thus, this leads to more retransmissions of packets towards the destination and, hence, resulting in growing delay. Fig. 3 shows that flooding incurs higher end-to-end delay. This is owing to the higher number of redundant rebroadcasts of RREQ packets with collisions and contention

caused by many RREQ packets that fail to reach the destination.

Fig. 3 end-to-end delay Vs number of connections

5.4. Packet delivery ratio (PDR)

Fig. 4 represents the PDR for all schemes in this study. This figure shows that our proposed scheme has a higher value of PDR compared with two counter-based and flooding. Packet delivery ratio increases when increasing the number of connections for the following reason: the more the network connections, the better and more available shortest paths towards destination. This implies that there are more connections to connect two nodes offering a better transmission in each area. Hence, there is a greater chance ensures that if the broadcast retransmission occurs successfully, resulting in an increased delivery ratio.

Fig. 4 Packet delivery ratio vs. traffic load

6. Conclusion

This work proposes a new counter-based broadcasting scheme to achieve efficient broadcasting by adaptive threshold with a probability value p can be permanent based on the local density information. The counter identifies nodes with duplicate data packet using threshold values and node removes the redundant message. The proposed work also adapts the random assessment delay (RAD) value to network congestion level and uses packet origination rate as an indicator of network congestion by keeping track of the number of packets received per second at each node. Simulation results reveal that this simple adaptation minimizes end-to-end delay and maximizes delivery ratio, and, thus, achieves superior performance in terms of saved rebroadcast, end-to-end delay and reachability over the other schemes.