An Overview of Query-Broadcasting Techniques in Ad Hoc Networks

Abstract

This chapter presents query-broadcasting techniques used to minimize expenses of the route discovery in ad hoc networks. A broad variety of such techniques have been proposed that improved the effectiveness and efficiency in various aspects of route discovery considering time and energy. Time-to-live based broadcast is the most common controlled flooding scheme widely used in routing protocols. One category of such techniques leveraged the routing history, while other category used broadcast repealing strategy to cancel the query-broadcast after successful route discovery.

1. Introduction

Freely moving mobile nodes arbitrarily create temporary structures called mobile ad hoc networks (MANETs). Low cost and ease of deploying attributes exist, owing to no requirement of preestablished infrastructure or centralized supervision for its configuration [1]. Each node in the network acts as a router with limited transmission range and is unable to directly communicate with nodes out of its transmission range. To communicate route discovery, using broadcasting query packet is employed, which can lead to flooding and broadcast storm [2, 3] and hence network congestion. This congestion takes toll on the energy consumption and average latency, thereby degrading the performance of the network. Research in the area has produced diverse set of techniques pertaining to packet broadcast expense control, keeping network congestion free.

This paper surveys and reviews all such proposed and adopted techniques under two major categories: confined broadcasting and unconfined broadcasting techniques as shown in Figure 2. In unconfined broadcasting techniques, source node broadcasting has no terminating condition, and each node [4] probes the set of selected neighbors based on metrics like weighted rough set (WRS) [5]. A cost-effective approach is that only participating neighbor nodes forward the query packets, while the rest discard the same [2].

These techniques have an edge of being reliable with assured success in finding optimal path in minimal time, thereby reducing packet duplication. The shortcoming of this category of techniques lies in its inability to control unnecessary retransmission of query packets despite known route. On the other hand, confined broadcasting set of techniques permits controlled flooding of the packets in a specified ring, thereby reducing congestion in networks. However, they compromise on the speed, and such approaches are very slow in finding the requested path [6]. Authors review all relevant and contemporary broadcasting approaches attempting to reduce such flooding expenses.

2. Route discovery in ad hoc networks

Route discovery is a process of finding optimal route (e.g., shortest, less congested, etc.) between two communicating nodes in the network. It is one of the characteristics of routing protocols, which may be reactive (on-demand) or proactive depending on the nature of routing protocols. The proactive route is made available in the table through periodic messages resulting in faster transmission. A few examples are OLSR [7], DSDV [1], etc. A class of power-aware routing protocols belongs to the proactive routing category. These protocols are loop free providing route in minimum time although the regular exchange of periodic messages congests the entire network using considerable storage space and draining energy of nodes [8]. Thus reactive routing protocols came into existence to reduce congestion and storage issues. Such protocols function on an on-demand basis (also called source-initiated routing protocols) initiating when the node needs to transmit, not requiring periodic transmission. Apparently, a large amount of battery power and bandwidth is saved. In reactive routing process, the source node broadcasts the query packet to the entire network, and intermediate nodes look in its cache for a route. If no route is available, re-broadcasting is done till the route to the destination is found. AODV [1] and DSR [9] use reactive routing.

To offset the limitations of each type, hybrid routing protocols emerged. These protocols use hierarchical approach to discover the route. It employs proactive approach within the proximity of the node and reactive approach between the proximity of nodes. Some examples are ZRP, IZRP, TZRP, AntHocNet, and HOPNET [10] and cluster-based routing protocols such as DWCA, DMAC, LEACH, and DTMNS [11].

In the above approaches, deploying flooding actually increases the cost to network by packet diffusion making routing expensive. To overcome its detrimental effects, various techniques are used at all levels from Mac layer to higher levels. Consequences of packet diffusion can be analyzed in AODV [1], Least Clusterhead Change (LCC), and ZRP [12] that are overcome in [10, 13] respectively. Similar broadcasting techniques were also proposed to reduce cost of packet diffusion [3]. The next section describes these approaches in detail.

3. Flooding of query packets

The process of disseminating the query packet to discover the optimal path (flooding) is the simplest form of broadcasting. Since every path is explored, the shortest and ideal path for effective transmission is guaranteed. Flooding was employed in many routing protocols such as AODV, OLSR, DSR, and DSDV.

Since packets traverse every outgoing edge of the directed graph shown in Figure 1, most nodes receive several copies of the same packet, and the intermediate nodes continue to forward the query packets to explore path, even after the route has been found, thus consuming a large bandwidth of the channel along with battery power of the participating nodes. This lowers the efficiency of the routing protocol. Two measures are taken to overcome the issue. First, the precautionary measure is opting for selective flooding, thus preventing redundancy of the packet at intermediate nodes. Second, controlled flooding is employed to circumvent unnecessary propagation of query packets.

Figure 1.

Flooding of query packets in the network.

Assume that a graph represents a network. This network is a connected acyclic network where vertices of the graph are nodes and the edges between two nodes are connections. This network has N nodes creating an imaginary circle of diameter D. The average degree of each node is d (d > 2) representing the number of neighbor nodes.

Let PDC be the packet diffusion cost at a specified hop count, and it can be defined as

$$\mathit{PDC}=\frac{\mathit{\text{Total number of node}}\mathit{at}k\mathit{\text{hops}}}{\mathit{\text{Total number of node}}\mathit{at}k-1\mathit{\text{hops}}}$$E1

$$\mathit{PDC}=\frac{{\sum }_{i=1}^{k}d{\left(d-1\right)}^{i-1}}{{\sum }_{i=1}^{k-1}d{\left(d-1\right)}^{i-1}}$$E2

PDC of flooding excluding redundancy of packets at intermediate nodes for the entire network is given in the equation below:

$$\mathit{PDC}=\frac{d{\left(d-1\right)}^R-1}{d{\left(d-1\right)}^{R-1}-1}$$E3

where R is the radius of the network. By solving the above equation,

$$\mathit{PDC}=1+\frac{d-2}{1-1/{\left(d-1\right)}^{R-1}}$$E4

Assuming a = d − 1, we have the value of packet diffusion cost at R hop count given by the equation below:

$$\mathit{PDC}=\frac{a^R-1}{a^{R-1}-1}$$E5

Larger packet diffusion cost increases congestion in the network that leads to energy consumption problem, thus affecting network life calculated by the equation below:

$$E{C}_n=n\times E_r$$E6

where n is the number of nodes and E_r denotes the energy drained per node. In route discovery, energy is consumed in two ways: query-packet broadcast and reply-packet unicast. Let H_i be the number of nodes at ith ring and R be the radius of network. The energy consumption for flooding can then be shown as

$$E{C}_n=\sum _{i=0}^{H_R}{E}_i+E_{\mathit{\text{rrep}}}$$E7

where E_rrep is the consumed energy in unicasting reply packet. Following the aforementioned analysis, packet diffusion cost and energy drained for confined broadcasting techniques are calculated and shown in Table 1.

Broadcasting techniques	Packet diffusion cost	Energy drained
LBA	$\frac{a^{2R}-1}{a^2-1}$	${\sum }_{i=0}^{H_r}{\mathrm{E}}_{\mathrm{i}}+{\mathrm{E}}_{\text{rrep}}$
TTL-ERS	$\frac{a^2\left(a^{2l}-1\right)}{{\left(a^2-1\right)}^2}-\frac{l}{a^2-1}$	$H_r\ast E_r+{\sum }_{i=1}^{H_r}{\sum }_{j=1}^i{\mathrm{E}}_{\mathrm{j}}+{\mathrm{E}}_{\text{rrep}}$
BERS	$\frac{a^2\left(a^{2\left(k-l\right)}-1\right)}{{\left(a^2-1\right)}^2}-\frac{k-l}{a^2-1}$	$2{\sum }_{i=0}^{H_r}{\mathrm{E}}_{\mathrm{i}}+{\mathrm{E}}_{\text{rrep}}$
BERS+	$\frac{a^{2k}-1}{a^2-1}$	${\sum }_{i=0}^{H_r}{\mathrm{E}}_{\mathrm{i}}+{\mathrm{E}}_{\text{rrep}}$
CMBERS+	$\frac{a^{2k}-1}{a^2-1}-C_R$	${\sum }_{i=0}^{H_r}{\mathrm{E}}_{\mathrm{i}}+{\mathrm{E}}_{\text{rrep}}$

Table 1.

Comparative study of different controlled flooding techniques.

An optimization of blind flooding is broadcasting to intended nodes only. Broadcasting is essential to discover the choicest path along with other varied objectives. Some of them are listed below:

3.1 Reducing the flooding expenses

As already discussed, a main drawback of blind flooding is the broadcast storm [2] that congests the entire network. This congestion develops due to the redundant propagation of query packets. This undesirable circulation is reduced by the use of a suitable broadcast repealing technique.

3.2 Limiting the packet dropping

In ad hoc networks, multiple classes of congestion exist, leading to dropping of the packets. A traffic control technique is employed during the packet broadcast to estimate the traffic in the network. This enhances the reliability of the packet transmission [6, 14].

3.3 Optimizing the path length

End-to-end delay is the average time taken by the source node to transfer the packet successfully [15]. The length and traffic of the path determines the delay. Therefore, careful adoption of broadcasting technique optimizes the desired path.

3.4 Increasing reliability of the path

Reliability is determined by the stability of the path. Independent movement of the mobile nodes changes network topology which in turn causes link breakage. Frequent link breakage decreases the reliability of the path [1, 9]. Therefore, broadcasting of the query packet is done in such a way that the packet can cover the least area which is sufficient to obtain the set of nodes with maximum battery life. Length of the path is another attribute determining the stable route with the shortest length.

3.5 Utilizing unicast and multicast modes

Although several routing protocols exist that work for unicast and multicast communication in MANETs, no routing protocol fits all scenarios due to varied nature of routing properties [1]. These properties are in turn dependent on broadcasting techniques. Consider a case, for example, there are five clients with each transmitting at 50 kbps in unicast mode. The group bandwidth turns out to be 250 kbps. While in multicast mode, the same load is experienced by 1 client to 250 clients. Thus the use of multicasting in confined broadcasting can reduce the cost of packet diffusion by customizing packet diffusion for group communication where the source node needs to find multiple routes at once for a set of nodes. In the unicast mode, unconfined broadcasting is useful along with the adoption of selective flooding.

Figure 2.

Classification of broadcasting techniques.

4. Unconfined broadcasting techniques

Efficient and effective packet broadcasting during route discovery phase is pivotal to MANETs. As dynamic changes in topology occur, packet flooding gets costlier and poses the broadcast storm problem as well [2]. This situation worsens, when the source and destination nodes do not have record of previous communication. To prevent this situation, unconfined broadcasting techniques have been proposed. These approaches are based on the selective flooding, and thus blind flooding does not occur.

This is just like a modeled graph representing a network where initially all nodes are colored white. The source node determines a set of neighbor nodes based on attributes like position, knowledge, previous record, etc. The query packet is processed by nodes of the set, and such nodes are then colored either black or red as shown in Figure 3. This algorithm is iterative and the resultant set of participating nodes is obtained. As an example, WRS uses weight metric to choose forwarding set of nodes.

Figure 3.

A sample of the network representing the covered nodes in route discovery.

Similarly, position-based broadcasting techniques like LAR and DREAM, being scalable, reduce participating nodes by a considerable margin by exchanging location information in comparison to non-position-based techniques. But location-based techniques are not suitable where GPS signal reception is poor or inaccurate.

Another approach for reducing the congestion is knowledge-based technique. They have an advantage of not requiring any special device. These rely on previous communication, and with the increase in iterations, accuracy improves, and these techniques like HoWL and QLT [8] find a desirable route with much less effort than location-based techniques [2]. Comparative study of performance metrics is depicted in Table 2. These techniques prevent redundancy at intermediate nodes, thereby reducing congestion. But unconfined broadcasting does not have the capability to prevent unnecessary circulation of packets.

Broadcasting techniques	Path strategy	Type	Complexity	Hello message
FRESH	ABF	Proactive	O(n)	Yes
HoWL	RBF	Reactive	O(n)	No
WRS	NKBF	Reactive	O(n^2)	Yes
LAR	LBF	Reactive	O(n)	No
DREAM	LBF	Proactive	O(n)	Yes
QLT	RBF	Reactive	O(p + k)	No
PARBE	PBF	Reactive	O(n)	Yes

Table 2.

Comparative study of the unconfined broadcasting schemes.

ABF, anchor-based flooding; NKBF, neighbor knowledge-based flooding; RBF, record-based flooding; LBF, location-based flooding; PBF, probability-based flooding; p, set of nodes lie in previous recorded route; k, threshold value.

Anchor-based flooding employs primitive search in order to find the route. Anchor nodes are those nodes that have found the desirable route most recently. Every node maintains an encountering history consisting of the time of its last encounter with every other node. Source node searches the nearest anchor in its proximity using ERS [15]. Upon receiving route discovery packets, the anchor node informs the source node about itself and starts to search the next nearest anchor node. This practice is continued until the route node receives the query packet. These anchor nodes form the path from the source node to the destination node. An example of this approach is FRESH [17].

PARBE [18] is a probabilistic approach, aimed at reducing issues related to the route discovery process in AODV [1]. It helps in the reduction of unwanted searches during the route establishment process by considering the previous behavior of the network. Source node sends the query packet to only those intermediate nodes that have the probability to find the route to the destination. This probability is calculated using the previous record of requested path from the routing table. Unlike flooding, it does not require any freshet of the packet for route discovery.

5. Confined broadcasting techniques

The goal of confined techniques is preventing unnecessary circulation of query packets by limiting its hop count. Techniques like LBA [19], LHBA [20], revisiting-TTL ERS [21], blocking ERS [22], blocking ERS+ [15], BCIR [4], and tBERS [23] belong to this category. Chase-based strategy is used in almost all broadcasting techniques, revisiting-TTL ERS being an exception. LBA, for example, works in the following fashion: when a node starts route discovery, it broadcasts the query packet. On receiving, the destination node sends back a reply packet. After route discovery, the source node broadcasts the chase packets to terminate further propagation of the query packets. Limitations of high overhead were overcome in LHBA in a manner that single packet, based on reference bit, behaves as query, reply, or chase packet [19].

On the other hand, revisiting-TTL ERS shown in Figure 4(a) is an expanding ring search-based technique to control the flooding. It broadcasts the query packet periodically with increased time-to-live (TTL) value as attempts fail instead of using the chase packet to limit disseminated area of query packets. BERS, BERS*, and BERS+[24] are improvised versions of revisiting-TTL ERS depicted in Figures 4(b) and (c).

Figure 4.

Processing of ERS-based algorithm. (a) TTL sequenced-based ERS, (b) blocking ERS, and (c) blocking ERS+.

The major advantage of chase-based approach is the guaranteed controlled flooding by canceling the packet broadcast at a specified hop in only one attempt though it causes channel overhead. Revisiting-TTL ERS, on the other hand, uses periodic packet broadcast to carry out the route discovery and increases the average latency and energy consumption and induces retransmission overhead. Other versions of this algorithm like BERS, BERS*, tBERS, tBERS*, BCIR, and BCIR* incur the same cost as conventional TTL-ERS in the worst-case scenario which is when predefined TTL value is small. This methodology is not adaptive in the case distance between the source and destination increases. BERS+ is adaptive to the mobility of the destination node and is best suitable where no previous communication exists. The drawback of BERS+ is that its broadcast termination is source initiated causing additional latency in the processing of control packets. However, BCIR, BCIR*, tBERS, and tBERS* apply destination-initiated broadcast termination approach offering higher retransmission efficiency over BERS, BERS*, and BERS+ [3, 6, 11, 14].

Apparently, there are a few more ways to tackle controlling the flooding. The method used to reduce the packet retransmission is cluster-based broadcast. The cluster heads and gateway nodes participate in packet retransmission, and other ordinary nodes remain silent. CBERS+ [16] is one such example. BERS+ is implemented in a destination-initiated manner, over a distributed clustered network that achieves scalability and broadcast termination. In highly dynamic networks, maintaining clusters is a difficult task as routing processing charges increase. Therefore, CMBERS+ is suitable for medium-sized networks with slow to moderate mobility with nodes that move in groups and where nodes are more likely to stay in groups. Overall comparisons of all techniques along with their features and applications are presented in Table 3.

Broadcasting technique class	Unconfined broadcasting technique	Confined broadcasting technique
Method	Selective flooding	Controlled flooding
Packet disseminated area	Large enough area of the network to find the route; usually depends on the routing history and location as well, e.g., QLT, LAR, and DREAM	Small enough area of the network which depends on the predefined time-to-live (TTL) count
Control packets	No, prone to unnecessary propagation of query packets, e.g., WRS, HoWL	Yes, except using to control the further propagation of query packets, e.g., BERS, BERS+, tBERS
Applicable in	Proactive routing protocols where source node has link information of the whole network, which helps to prune the conveying intermediate nodes	Reactive routing protocols where the source node makes the first route discovery for any node
Storage requirement	Yes, increases as the number of nodes increases	No, however, some type of cache is used to track the predefined TTL value
Preferred for	Unicast mode	Multicast mode
Average latency	Very low, due to proactive nature	Higher due to added delay in the processing of query packet at each intermediate nodes
Periodic updates	Yes, require to gain previous routing information	Not required
Suitable	For small networks with high mobility	For large networks with slower to moderate mobility where no previous communication is available

Table 3.

Overall comparisons of broadcasting techniques.

6. Conclusion

In this chapter, almost all broadcasting techniques are reviewed under two categories: confined and unconfined. The unconfined broadcasting techniques, mainly derived from selective flooding, eliminate query packet redundancy at intermediate nodes in the route discovery, while confined broadcasting techniques reduce retransmission of query packets by controlling flooding. Most of the flat routing protocols employ only one broadcasting property of the two categories. Hybrid routing protocols, on the other hand, employ both properties by maintaining selective flooding within the proximity of node and controlled flooding between the proximity of nodes. Each technique has its merits and demerits. Unconfined approach of WRS and QLT and probabilistic approach offer simplicity in implementation where previous communications exist, while unnecessary flooding may be controlled with the use of a special device like NOVSTAR GPS to reduce conveying nodes as done in location-based algorithms DREAM and LAR. Though signal is weak, low accuracy due to atmosphere remains an issue. Confined broadcasting techniques save energy by employing strategies like TTL value to confine the region. Broadcasting techniques like TTL sequence-based ERS and its variants such as BERS and tBERS converge slowly for short predefined TTL value. BERS+ improves speed by introducing added delay after a maximum limit of TTL value. An enhanced version of CMBERS+ further increases the speed by issuing control packets at the route node. Moreover, scalability issue also has been resolved by dividing the network into distributed clusters. The advantage of these techniques over unconfined broadcasting techniques is that route discovery can be accomplished with controlled flooding when record of previous communication does not exist.

The central challenge in MANETs is exploring optimal path with minimal cost. A lot of research efforts have been devoted to the discovery of route using efficient and effective broadcasting technique. This chapter surveys shortcomings of the existing broadcasting techniques as well as discusses possible measures. Here are a few challenges that can be taken up in future research in the domain:

1. Blocking ERS+ introduced added delay after threshold to capture the query packets that slow down the route discovery after kth failed attempt. It can also be improved by reducing the added delay.

2. A comparative analysis of broadcasting techniques can be done in the clustered network which is still lacking in the majority of works.

3. Destination unreachability problem in LHBA can be removed to prevent the dropping of the gratuitous reply packet.

Moreover, Internet of Things (IoT) is a buzzword in the information and communications technology which covers a variety of routing protocols and their applications. In such scenarios, broadcasting techniques can play an important role in monitoring power theft, animals in the forest, automobiles with built-in sensors, etc. In this growing field, a controlled flooding will be required for multicast or group communication.

Notes/Thanks/Other declarations

Not Applicable.

Acronyms and abbreviations

ERS	expanding ring search
AODV	ad hoc on-demand distance vector
BERS	blocking expanding ring search
BERS+	enhanced BERS
BERS*	blocking expanding ring search*
tBERS	time-efficient BERS
tBERS*	time-efficient BERS*
BCIR	broadcast cancelation initiated on resource
MBERS+	modified BERS+
CMBERS+	cluster-based MBERS+
PARBE	probabilistic approach to reduce the broadcast expenses
LBA	limited broadcasting algorithm
LHBA	limited hop broadcasting algorithm
HoWL	hop-wise limited broadcasting
TSERS	two-sided ERS
QPM	query packet minimize technique
FRESH	fresher encounter search
QLT	query localization technique
DREAM	distance routing effect algorithm for mobility
WRS	weighted rough set
LAR	location aided routing