Abstract: Most routing protocols in mobile ad hoc networks (MANETs) use flooding to disseminate routing information and to perform route discovery process. As flooding involves querying all network nodes, frequent flooding can rapidly deplete the energy reserved at each node. Therefore, creating competent flooding scheme is a crucial requirement and a Connected Dominating Set (CDS) can be a useful basis of backbone construction in MANETs. However, when the size of CDS becomes too small, certain features in the original network may be lost, as example, the number of broadcasts for a packet to reach its destination can be drastically increased. In this study, a multipoint relay scheme has been investigated and appended as an assistant flooding scheme beside the constructed CDS. The approach used in this concern is the Dominant Pruning (DP) which creates a dynamic dominating set at each broadcasting step. This set is a subset from the neighbor set of the broadcasting node. The incorporation of DP and CDS is made to fill the gaps that may arise within the backbone established by CDS, such that, the number of elongated paths through this backbone is efficiently reduced. Simulation results show that the developed approach outperforms DP and CDS when they are applied individually in terms of the number of flooded control packets, data delivery ratio and average end-to-end delay while keeping the same computation complexity of them.
INTRODUCTION
MANET is a wireless network consisting of mobile computing devices forming a temporary network for wireless communication, without the help of any fixed infrastructure (Chlamtac et al., 2003; Yang et al., 2003). Therefore, each node in MANET acts as a router to provide communications throughout the network. In other words, it forwards “broadcasts” packets on behalf of other nodes. Broadcasting to all nodes in ad hoc networks has many applications, such as the route discovery process within on-demand routing protocols (Johnson and Maltz, 1996; Perkins and Royer, 1999). However, such type of flooding “pure flooding” which is used with the aforementioned protocols can rapidly deplete the energy reserved at nodes, knowing that the energy supply of the ad hoc nodes is very limited since they depend on their batteries. To tackle the problems arising from the pure flooding, the concept of CDS has been introduced. CDS is inspired by contributions of physical backbone in wired networks. With CDS, searching space for routing problems can be constrained to the backbone nodes only and this applies as well in broadcasting, so that only the CDS nodes will be responsible on forwarding the control packets.
When the size of the CDS becomes very small, some characteristics of the original network may be missed, as example the shortest routing path and the minimum flooding tree, which are vital factors in most of the routing protocols and flooding approaches. The profit of such aspects, is that, the energy consumed and the average delay will be reduced, since fewer nodes are engaged in forwarding packets. In Fig. 1a, the shortest route between nodes A and C in network utilizes AODV routing protocol is {A, B, C} which includes just two hops, while through the regular CDS in Fig. 2b the routing path will become {A, D, E, F, C} with four hops which is twofold the original route.
In this study, the characteristic of a multipoint relay (MPR) scheme which is a sender-based one (Spohn and Garcia-Luna-Aceves, 2003) has been investigated and appended it as assistant flooding scheme beside the constructed CDS. The approach used in this concern is the Dominant Pruning (DP) which creates dynamic dominating set at each flooding step. This set is a subset from the neighbor set for the node in concern and must cover by its broadcasts all the neighboring nodes that are located two-hops away from that node. The incorporation of DP and the CDS is made to fill the gaps that may arise within the backbone established by the CDS alone, such that, number of the elongated paths through this backbone can be efficiently reduced. In this way the resultant flooding scheme, will be a compound one, i.e., sender-receiver-based scheme.
RELATED WORKS
CDS has always been a hot research topic since it was touched in the first place due to its great benefits for wireless networks. In the evaluation of the CDS quality, its size was the essential considered factor.
| Fig. 1(a-b): | Length difference in routing paths between (a) CDS and (b) AODV |
| Fig. 2(a-b): | Two-hop neighbor table structure, (a) Compound cell in 2-hop neighbor table and (b) Overview of the compound |
Since the communication channel in wireless networks is shared among all neighbors, a minimal virtual backbone will encounter less interference. Besides that, a smaller CDS can achieve more efficient routing and reduces the flood of control packets. For those reasons, many research studies on dominating sets gave their attention to reduce the size of the constructed virtual backbone (Ni et al., 1999; Wu and Li, 2001; Wu, 2002; Stojmenovic et al., 2002; Wu et al., 2003, 2006; Dai and Wu, 2004; Sakhaee and Jamalipour, 2008; Li et al., 2009; Anitha and Sebastian, 2011).
Mohammed et al. (2005) indicated that in wireless networks, the chance of packet transmission failure predominantly rises when a packet is sent through longer path. They also suggested the diameter of a CDS as a quality factor in CDS generation algorithms and illustrated that a smaller diameter means a better CDS. Li et al. (2007) introduced the concept of CDS diameter which they defined it as the longest shortest path between any pair of nodes in the CDS. The authors generated a Maximal Independent Set (MIS) which is a subset of all the nodes in the network, nodes in MIS are pairwise indirectly connected and no more nodes can be added to conserve this property, such that each node not in MIS is neighboring to at least one node in the MIS. By adding more nodes to the MIS, a CDS can be obtained. Kim et al. (2009) discussed the problem of constructing quality CDS in terms of size, diameter and Average Backbone Path Length (ABPL). Two centralized algorithms have been introduced in their work with a constant approximation ratio for the diameter and size of the constructed CDS. A distributed version is given for the second algorithm which can be implemented in real situation with considering the energy constraints to prolong the network lifetime. The authors noticed that the diameter captures the worst case path length of a CDS. Instead, the Average Backbone Path Length (ABPL) may be another quality factor to evaluate a CDS. ABPL of a CDS S is the sum of the hop distance between any pair of nodes x and y (x; yεS) divided by the number of all the possible pair of nodes. Therefore, the diameter is the worst case of ABPL. Ding et al. (2010) studied a special CDS that must include at least one shortest path between any pair of nodes in a wireless ad hoc network. They called their suggested CDS, the Minimum rOuting Cost CDS (MOC-CDS), therefore, routing and broadcasting by this CDS will follow the shortest paths in the network. Consequently, delivery delay and energy consumption have been considerably reduced than a regular CDS. The authors proved that constructing of a minimum MOC-CDS is NP-hard and proposed a distributed heuristic algorithm called (Flag-Contest) for constructing MOC-CDS with performance ratio (1-ln2) +2lnδ, where δ is the maximum node degree. Ding et al. (2011) further optimized their previous work and suggested a special CDS named α- MOC-CDS to improve the performance of CDS-based broadcasting and routing. As in MOC-CDS, authors proved that it is NP-hard to construct minimum α- MOC-CDS and they suggested an approximation algorithm with heuristics to construct α-MOC-CDS with reduced size. α-MOC-CDS keeps all the properties of regular CDS and made a special constraint on the path length between any pair of nodes. The condition is that, the number of nodes in such path must not exceed α times the number of nodes in the corresponding shortest path at the original network.
MATERIALS AND METHOD
In this study, a hybrid flooding approach is proposed which keeps the merits of CDS and minimizes paths length augmentation. The hybrid scheme combines sender-based and receiver-based schemes. The receiver-based part constructs CDS by following the steps of Marking Process that will be explained in the following, while the sender-based part is achieved via the Dominant Pruning that gives a boost to the flooding action by dynamically generating a local dominating set in each hop a packet traverses.
To implement any of the aforementioned techniques, 2-hop neighborhood information must be available, which is the minimum requirement for the algorithms considered in this study. A neighbor protocol will be responsible on collecting and maintaining this information, however the design of such protocol and it’s maintenance mechanism are beyond the scope of this study but an illustration for the structures which suppose to accommodate the 2-hop neighbor information is given in the next subsection to clarify how an arbitrary node decides to be a gateway or determines its forwarders based on this information.
Connected dominating set (CDS): A connected dominating set of a graph G is a set of D vertices with two properties:
| • | Any node in a subset D can reach any other node in D with a path that stays entirely within D. Where subset D induces a connected subgraph of G |
| • | Every vertex in G either belongs to D or is adjacent to a vertex in D. In this way D is the dominating set of G |
The key attribute of connected dominating set-based broadcasting or routing is that it concentrates the entire network into a small subnetwork characterized with the dominating set, where only dominating nodes keep routing information, therefore if there is no topological changes affect the subnetwork there is no need to recalculate routing tables. In this study, “Marking Process” proposed by Wu and Li (2001) has been adopted to determine the connected dominating set but with some adaptation to consider unidirectional links between nodes in some cases, since not all nodes are homogenous in the network, that, different nodes may have uneven transmission ranges. Marking Process and the other algorithms in this study utilize 2-hop neighbor information to accomplish their task. Figure 2 illustrates how this information can be arranged within a 2-hop neighbor table and in the form of linked-list data structure.
In part-a there is a sketch for a compound cell includes an address for a 1-hop neighbor node, flags indicate neighbor’s gateway and mobility status, pointer to the next cell and another pointer to a secondary list contains the 1-hop neighbors for the above-mentioned neighbor, part-b gives an overview for the arrangement of 2-hop neighbor information within a complete table.
Figure 3 demonstrates how Marking Process has been modified to consider the existence of unidirectional links or obstacles between neighbors, where it looks for the mutual existence of nodes in the neighbor tables of their neighbors to make sure if the neighbors for a given node are all directly connected to each other (pairwise connected) or not. From this point node v in Fig. 3 tries to determine its gateway status through checking for the existence of connections among all of its neighbors, therefore it checks if node u is exist within the neighbor list (secondary list) of node w and vice versa and it will continue looking for its existence within the secondary lists of the rest neighbors in the same manner. Node v will complete this investigation process for all nodes within its 1-hop neighborhood. If it happened and there was no mutual existence between two of its neighbors at each other secondary list, it will consider itself as gateway node since it has two unconnected neighbor as indicated in the last part of the flowchart.
| Fig. 3: | Flowchart of marking process and an illustration for the initial and successive pointers settings at the 2-hop neighbor table of node v |
Dominant pruning (DP): The use of dominant pruning as supporting flooding technique in conjunction with the generated CDS can give sturdy impact to flooding performance. Nodes that have been selected as forwarders with dominant pruning will forward packets for only one time. After that they will relinquish their forwarding activity and return back as ordinary nodes. They are not part of the CDS therefore they will not add extra maintenance overhead. In the same time dominant pruning will use the already existing (off-the-shelf) neighbor tables with no need for more information, where it has the same requirements of CDS, both approaches require 2-hop neighbor information. Dominant pruning generates local (on-demand) source-dependent dominating set. A node which has been selected as forwarder by a predecessor forwarder node will generate its own dominating set that must dominate its 2-hop neighborhood. An algorithm known as Greedy Set Cover (GSC) has been adopted in this study to determine forwarders for a node which is the source of the broadcast or for other subsequent nodes that are going to be selected as forwarders.
| Fig. 4: | Steps of GSC algorithm to calculate node’s forwarders |
| Fig. 5: | Flowchart of the determination process for the 2-hop-away neighboring nodes for a node v |
In this study, the behavior of GSC algorithm has been characterized into three steps as shown in Fig. 4, the steps are summarized in the following bullets:
| Step 1: | The node determines (isolate) its 2-hop away neighbors within a separate list that can be called as ‘2-hop away-neighbor table’. Figure 5 shows the flowchart for the determination process. The same diagrams of neighbor tables in Fig. 3 have been used to illustrate the discrimination operation between the 1-hop and 2-hop neighbors. Every node in the secondary lists is checked whether it’s a 1-hop neighbor table’s member or otherwise. If it’s then it will be excluded and the algorithm proceeds to check the other nodes. That’s only nodes which don’t belong to the 1-hop neighbor table can be considered as 2-hop-away neighbors |
| Step 2: | Determination of fitness value for each 1-hop neighbor node. Fitness value depends on how many neighbors that a 1-hop neighbor has inside the 2-hop-away neighbor set. In other words, fitness value for a specific 1-hop neighbor node is the intersection set between the 2-hop-away neighbor table a nd the 1-hop neighbor table for this neighbor. After fitness calculation, the corresponding fitness values for the neighboring nodes are sorted in descending order within a table known as the fitness table to facilitate forwarders selection process, so, the first cell in the table will contain the neighbor with the highest fitness value whereas the following cell will accommodate the neighbor with the second highest value and so on. When a neighbor with its fitness value are going to be inserted in the fitness table, the algorithm checks if the table is empty or not, then, the created cell for the neighbor concerned will be added in first location at the table if this neighbor has the highest fitness value otherwise it will be added in the location that corresponds with its fitness value such that the descending order of fitness table is kept. In the fitness calculation algorithm, there three pointers Pi, Pj and Pk are used to identify and access the data stored within the 2-hop neighbor table and the list that comprises the set of 2-hop away neighbors as shown in Fig. 6, whereas in Fig. 5, the pointers point to the 1-hop and 2-hop neighbor tables |
| Step 3: | When the fitness values are determined for all 1-hop neighbors i.e., fitness table becomes complete. The node which has been seleced as forwarder starts selecting it’s forwarders by adding them to the forwarders table. The node picks its forwarders from the fitness table, starting with the neighbor with the highest fitness and continues in descending manner. After each forwarder selection, the node checks if the selected forwarder(s) cover(s) all the 2-hop-away neighbors. The algorithm terminates when all the 2-hop-away neighbors are covered by the selected forwarders. Figure 7 shows the flowchart of forwarders selection for a given node v with its 2-hop neighbor table and the fitness table |
In Fig. 7, pointer Pi is set to point to the first cell in the fitness table, where the neighbor with the highest fitness is stored and continues to point to the next cells where neighbors with lower fitness values are stored in the subsequent iterations. The calculating node checks to find the selected neighbor within its 1-hop neighbor set, then, it will insert this neighbor into the forwarders table and append its respective 1-hop neighbors “only those are 2-hop away from the calculating node” in a table know as the Compare Table (CT). After each addition to the compare table, the node checks if size of the compare table becomes equal to the size of the 2-hop away neighbor table, where this condition determines if enough forwarders have been selected or otherwise.
| Fig. 6: | Flowchart of neighbors’ fitness calculation |
RESULTS
Performance of the proposed hybrid flooding scheme has been measured using computer simulation and has been compared against each of connected dominating set, dominant pruning flooding approaches and the expanding-ring search of AODV protocol which is in many aspects, near to blind flooding. QualNet v 5.02 by Scalable Network Technologies has been adopted as the simulation tool in this study. The simulation parameters for the created scenarios are outlined in Table 1. From the table, it can be seen that five networks scenarios have been created with networks’ sizes of 25, 50, 75, 100, 125 nodes respectively in terrain area of 1500*1500 m which has been kept fixed with the all created scenarios.
| Fig. 7: | Flowchart of node’s forwarders calculation |
| Table 1: | The adopted parameters of the created networks scenarios in QualNet software package |
| Fig. 8(a-c): | Average No. of RREQ packets received with nodes’ transmissions ranges of (a) 200 m, (b) 300 m and (c) 400 m |
The Medium Access Layer protocol in use is IEEE 802.11b/g/n which is the default option in QualNet just like the other parameters such nodes’ speed, the path loss model, the mobility model, the antenna type and the packet size. Nodes placement has been selected to be random whereas, the simulation time has been selected to be 200 min to mimic the real life scenarios, as example, conferences and rescue operations.
To investigate the efficiency of the developed hybrid scheme and the other examined flooding approaches, they were individually incorporated with AODV protocol, whereas a number of performance metrics have been elected to be monitored to verify the efficiency for each of the inspected approaches. The metrics are as follows:
| • | Average No. of route-request (RREQ) packets received |
| • | Average No. of RREQ packets forwarded |
| • | Data delivery ratio and |
| • | Average end-to-end delay |
The first two metrics, deal with flooding efficiency in terms of number of the flooded control packets, i.e., flooding scheme overhead. Figure 8 shows the average number of RREQ packets received within the inspected flooding schemes with transmission ranges of 200, 300 and 400 m, respectively which is the case with the other metrics also. It can be seen from the figure, the hybrid flooding scheme has transcended other approaches (CDS, DP and AODV) in reducing the average number of RREQ packets received during the simulation time for all the inspected network sizes.
Figure 9 gives the average number of the RREQ packets forwarded with the hybrid flooding scheme and the other methods in addition to AODV.
It can be seen from Fig. 9, the hybrid flooding scheme exhibits moderate performance between CDS and DP as the upper and lower edges respectively. In part-a from the figure, when the transmission range is 200 m, the hybrid scheme looks nearer to CDS, whereas in the next two parts that correspond to the higher transmission ranges, it takes the middle path.
| Fig. 9(a-c): | Average No. of RREQ packets forwarded with nodes’ transmissions ranges of (a) 200 m, (b) 300 m and (c) 400 m |
| Fig. 10(a-c): | Average No. of duplicate RREQ packets received with nodes’ transmissions ranges of (a) 200 m, (b) 300 m and (c) 400 m |
The two remaining metrics which are the data delivery ratio and the average end-to-end delay will reveal the real benefit of the hybrid flooding scheme, since the objective behind development of this scheme is to maximize the data delivery ratio and reducing routing cost ‘delay’ through minimizing the length of paths between the source and destination nodes. This will in turn reduce the probability of packets loss which often arises when they traverse longer paths. Figure 10 shows the number of data packets received with the hybrid flooding scheme and the other inspected approaches based on information given in Table 2.
Figure 11 illustrates the Average of End-to-End delays incurred by each of the developed hybrid scheme and the investigated flooding approaches, where the delays are measured in seconds.
| Fig. 11(a-c): | Average end-to-end delay obtained with transmissions ranges of (a) 200 m, (b) 300 m and (c) 400 m |
| Table 2: | Details of the CBR connections in the developed networks scenarios |
DISCUSSION
It is obvious from Fig. 8 that at higher transmission ranges more RREQ packets are received by nodes. This will incur more overhead to the receiving nodes in terms of communications and computation costs. In regard to the communication part, it is clear that a node will receive more packets from its neighbors since it will receive the additional packets from the distant neighboring nodes when the transmission range of these nodes is high and hence it will also consume more power due to the frequent receiving actions. On the other hand, in respect to the computational overhead, the extra received packets need to be checked if they are intended for the receiving node. If that is the case, then more computations are required. In respect the average number of forwarded RREQ packets, it is clear from Fig. 9 that the hybrid scheme and the inspected flooding approaches follow parabolic pattern in their paths shape. That is in the smallest network size (25 nodes), the average number of flooded RREQ packets is higher than what is resulted in the case of 50 nodes. This is because the scattered and distant positioning of few nodes in large terrain generates a network with disrupted connectivity. These conditions in addition to the nodes mobility will impact the links reliability, where they will be frequently subjected to fractures and therefore more RREQ packets are broadcast. For the remaining section of the graphs after the 50 nodes, the average number of flooded RREQ packets continues to rise uniformly with each increase in the network size, where this is inevitable with the significant rise in number of nodes at each increment step.
Figure 10 shows that the highest data delivery ratios is achieved by the hybrid scheme with the all examined transmissions ranges and networks sizes, since it combines by its flooding methodology both CDS and DP approaches to attain the shortest paths between the source and destination nodes. It is noticeable also that AODV achieves a fair delivery ratio which is better than what is obtained with CDS or DP alone. This is because AODV adopts the principle of shortest path routing beside the freshness of sequence numbers for nodes to select among the available routing paths. Finally, Fig. 11 displays the performance of the hybrid flooding schemes and the other approaches in terms of the average end-to-end delay, which is heavily related to the routing cost. This delay basically depends on the length of routing paths between source and destination nodes in addition to other factors such as the link reliability. In this study, in the context of delay minimization, DP approach is adopted to fill the gaps that can appear between the hosts of CDS in a way that efficiently reduce the length of paths followed by the packets while traveling from their sources to the intended destinations. From Fig. 11, it can be seen that the delay goes down with each increase in the transmission range. This is an axiomatic since the packets can arrive faster at their destinations, where they will travel a greater distance at each flooding step. With all inspected transmission ranges, the developed hybrid flooding scheme exhibits performance near to that obtained from the AODV routing protocol and always better than the CDS approach whereas it outperforms DP with a notable margin for the reason indicated previously (Ding et al., 2011).
The hybrid flooding scheme is compared against another approach presented by Ding et al. (2011). The authors developed an algorithm to construct a special type of CDS with minimum routing cost (α-MOC-CDS). The metrics they considered are size of the generated CDS and the average routing path length. To assess their works, they implemented three different networks scenarios correspond to different graph models. The first is general graph, the second is directed graph while the last one is Unit Disk Graph (UDG), where all nodes have the same transmission range. The results obtained from the hybrid flooding scheme are compared against that attained from the employment of the authors’ algorithm in a network modeled as a UDG. For this purpose, the same scenario’s conditions used by the authors of α-MOC-CDS approach are followed to create an ad hoc network scenario deploys the hybrid flooding scheme to organize the flooding activity in the network. In this context, 10 scenarios with different network sizes are implemented within a squared terrain of 100 m*100 area for network sizes start from 10 nodes till 100 nodes, whereas the transmission range is set for 30 m for all nodes. For each network size, 20 instances are obtained and their results are averaged to get the final results.
From Table 3 values, it can be seen when α = 1, i.e., with 1-MOC-CDS, the lowest average routing path lengths (ARPL) are attained, whereas in case of 2-MOC-CDS, the values of ARPL are higher that what achieved with 1-MOC-CDS and in respect to the hybrid flooding scheme, the ARPL values comes slightly behind their counterparts in 2-MOC-CDS. It’s also recognizable for higher network sizes, i.e., with denser networks, the α-MOC-CDS approach makes better use of the increased network density, where the nodes degrees become higher and therefore there is more chance for many of the CDS nodes to become intermediate nodes of more paths between the pairs of source and destination nodes which can it turn increase the tolerance of the CDS itself.
| Table 3: | Routes average length attained with the hybrid scheme and α-MOC-CDS when alpha value is set to 1 and 2 |
On the other hand, the hybrid flooding scheme couldn’t make full use from the increased network density since the flooding activity is not only based on the CDS nodes, that’s the additional forwarding nodes selected by the deployed MPR approach are not permanent part from the CDS.
CONCLUSION
Flooding efficiency has been improved as well as the routing cost through the supplement made by the incorporation of the DP approach as an assisting factor in the flooding process. DP is sender-based flooding scheme that can work beside the main flooding scheme i.e., the CDS without incurring additional maintenance overhead since it generates a dynamic dominating set for each node has been selected as forwarder. This set should cover the 2-hop neighborhood of the respective node. Thereafter, it will be abandoned since it has made its role and there is no need to be kept. The result of DP incorporation was a Hybrid flooding scheme which is a sender-receiver-based scheme. This scheme has been implemented with the AODV and the results have shown that it outperforms the CDS, DP and AODV routing protocol in terms of the average end-to-end delay and the data delivery rate. In respect to the flooding efficiency, the Hybrid scheme has been shown to be more superior compared with the AODV and it was always better than the CDS in terms of the average number of the received, duplicated and forwarded RREQ packets.