Abstract: Broadcasting or flooding is one of the principal functions in wireless ad-hoc networks. In broadcasting, a mobile node sends the same message to all nodes in the network in one-to-all model. Broadcasting based on set of dominating nodes is remunerative approach, where the broadcasting activity is constrained to only the nodes in the dominating set. A set is dominating if all nodes in the network are either in the set or neighbors of nodes in the set. In this study, the notion of constructing connected-dominating-set is extended to ad-hoc networks with unidirectional links. An enhanced distributed algorithm is presented that is based on the marking process which is has been introduced in earlier work. Our enhanced algorithm features a good locality properties since it need only 2-hop neighborhood information within each node. The algorithm checks for the mutual existence of nodes in the neighbor table of their neighbors to guarantee the symmetric connectivity between neighboring nodes. The proposed algorithm is integrated with AODV routing protocol to generate a connected dominating set that will be responsible on flooding activity. The efficiency of our approach is investigated and verified through simulation whereas the computational complexity is determined and compared with that of original marking process. All the simulations run are carried out with QualNet Simulator version 5.02.
INTRODUCTION
A mobile ad hoc network (MANET) is a wireless network consisting of mobile computing devices forming a temporary network for wireless communication, without the help of any fixed infrastructure or centralized administration. Ad hoc networks have applications in areas where it is not economically practical or physically possible to provide infrastructure-based networks. For example in emergency rescue sites, combat field communication, sensor networks, personal entertainment, etc., (Chlamtac et al., 2003). Because of absence of fixed infrastructure in ad hoc networks, each node acts as a router to provide communications throughout the network. That is if a source node cannot send a packet directly to its final destination in one hop due to limited transmission range, then it will send it to an intermediate node and this one in turn will forward the packet to its neighbor and so on, until it arrives at the final destination. An ad hoc network can be represented by a simple graph G(V, E) (Clark et al., 1990), where v represents the set of wireless mobile nodes (vertices) and E stands for the set of links (edges) between the nodes. An edge between a pair of nodes {u, v} indicates that both nodes u and v are within their wireless transmission range that is, connections between nodes depend on the geographic distance of nodes. Broadcasting to all nodes in ad hoc networks has many applications, include paging a particular host or sending an alarm signal as well as the route discovery process within on-demand routing protocols (Basagni et al., 2004). However, MANETs are characterized by scarce resources in terms of bandwidth, battery power, processing capabilities, etc. and blind flooding can become very inefficient because of the redundant broadcasts, they increase link overhead and lead to wireless medium congestion that causes a considerable collisions of packets. The resulting redundancy, contention and collisions constitute what is known the “broadcast storm problem” (Ni et al., 1999). To alleviate the problem, the concept of virtual backbone has been introduced in many literatures such as Yang and Chen (2003), Guha and Khuller (1998), Li et al. (2009), Adjih et al. (2005), Wu et al. (2003, 2006), Stojmenovic et al. (2002), Jie et al. (2001), Shaikh et al. (2003) and Ding et al. (2010, 2011). Virtual backbone has been studied extensively in undirected graphs or unit disk graphs, where all nodes have the same transmission ranges. However, in practice this is not necessarily the case, in ad hoc networks some links may be unidirectional due to variance in nodes’ transmission ranges or because of the hidden terminal problem. In this study we have investigated the marking process which considers every node as a gateway host, i.e., belongs to the dominating set if it has two unconnected neighbors and extended its implementation feasibility to ad hoc networks with unidirectional links.
RELATED WORKS
In flat broadcasting schemes or blind flooding, all nodes are allowed to participate in the broadcasting action. However, this can consume a considerable amount form the precious wireless bandwidth especially in the wireless networks and deplete the limited energy resources characterized by the nodes’ batteries. To permit scaling, hierarchical techniques have been applied to confine broadcasting within limited number of nodes selected depending on certain criteria. In the following, a brief survey for some works suggest hierarchical or dominating-set-based flooding in ad hoc networks with unidirectional links.
Wu (2002) suggested a localized algorithm for determining an extended dominating-set which adapts to the existence of unidirectional links through the introduction of absorbent-set concept. A mobile host v in set V is said to be a dominating neighbor or absorbent neighbor for host u in V also, depending on the direction of link between them, such that, the ordered pair (v, u) means v is a dominating neighbor for u whereas (u, v) denotes v as an absorbent neighbor for u while a subset of mobile hosts is dominating and absorbent if every host not in the subset is a neighbor for one dominating host and another absorbent one in the subset.
Thai et al. (2008) extended their work Thai et al. (2007) for constructing Minimum Connected Dominating Set (MCDS) in disk graph with all bidirectional links to be implemented in heterogeneous networks with unidirectional links. Their model represented the ad hoc network as a disk graph considering the presence of unidirectional links, such that, they investigated virtual backbone construction under two scenarios: The Strongly Connected Dominating Set (SCDS) and the Strongly Connected Dominating and Absorbent Set (SCDAS). Firstly, they proposed a constant approximation algorithm for constructing SCDS and discussed the ability for using this algorithm to build SCDAS by applying efficient heuristics. From the observation of NP-completeness (Garey and Johnson, 1979) to establish CDS with minimum size in Unit Disk Graph (UDG) with all bidirectional links, Thai et al. (2008) anticipated it would be the same problem in general Disk Graph (DG) and based their new algorithm on Breadth-first-search to find SCDS in general DG, this algorithm was known as (BFS-SCDS). They added an improvement to this algorithm using minimum number of Steiner Nodes; so that it is finally called (MSN-SCDS) and utilized the results to establish the SCDAS. Ramasubramanian and Mosse (2008) investigated the influence of unidirectional links on network connectivity and routing efficiency and proposed an approach called Bidirectional Routing Abstraction (BRA) with the aim to preserve multi-hop reverse paths for the asymmetric links and supplying other functionalities such as connectivity enhancement by utilizing the unidirectional links to find new and better routes, forwarding of control packets across the reverse in some routing protocols and discovering packet loss. Huang et al. (2011) proposed cross-layer approach for mesh access networks working in ad hoc model. The main ideas of their approach were to eliminate the unidirectional link at the network layer and design a handshake and channel reservation mechanisms at the Medium-Access Control (MAC) layer using topological information collected in the network layer. Markarian and Abu-Khzam (2012) worked on a hybrid heuristic approach to construct SCDAS in mobile ad hoc networks, at which they combined the elimination of low-degree nodes and selection of high degree nodes for being members in the constructed dominating set. The suggested heuristic expects high-degree nodes are more likely to dominate and absorb other nodes than nodes of lower degree. Thus, a “good” solution will most likely include many high degree nodes. However, since found dominating set must be strongly connected in addition to dominate and absorb all vertices in the graph, the proposed algorithm have been utilized the low-degree nodes as intermediary vertices to strongly connect the nodes in an optimal solution set.
CONSIDERING UNIDIRECTIONAL LINKS
Consideration of unidirectional links is motivated by the fact that not all nodes within a network are homogeneous, different nodes may have dissimilar transmission ranges due to the disparity in their energy levels. Figure 1 illustrates how unidirectional links can show up between nodes in a given ad hoc network with certain conditions, when obstacles lie in between nodes and there is disparity in their transmission ranges. In Fig. 1, nodes A, B, C and D have transmission ranges of rA, rB, rC and rD, respectively, represented by the dotted circles in the figure, with values such that rD >rC>rB>rA.
It is clear from the values and figure that nodes A and C cannot communicate with each other because C is out of A’s transmission range while A lies inside C’s coverage area. Even though A can receive messages from C but it is not mutual action between them because node C cannot hear from A. Hence, there is a unidirectional link from C to A. Thus, nodes can communicate only if they are located within each other transmission ranges and there are no objects blocking their radio transmission. In the same figure, nodes B and C cover each other but they cannot communicate due to the existence of an obstacle between them. In such conditions, a modification is suggested to the original marking process presented by Wu and Li (2001) to construct a CDS considers the unidirectional links between neighboring nodes.
| Fig. 1: | An ad hoc network with unidirectional links |
| Fig. 2: | Links types between neighboring nodes with the correspondent neighbor table contents |
Figure 2 shows the various link conditions between two given neighbors A and B. In part a there is a bidirectional link between them which indicates both nodes are located within each other wireless transmission range and therefore each one is registered in the neighbor table of the other. In parts b and c of the figure, a unidirectional link is directed from A to B and B to A, respectively, where the nodes have dissimilar transmission ranges. Thus, in part b only node A is registered at the neighbor table of node B whereas the opposite applies to part c since it is only node B is identified by A, depending on the link direction between them.
Enhanced marking process (EMP): Marking process which is a distributed algorithm developed for CDS formation has been investigated in this study. As the case with other dominating set variants, marking process cannot generate a minimum connected dominating set (MCDS), where the related decision problems are proved to be NP-complete for all dominating set approaches in general graphs. Therefore, reduction rules are utilized to obtain a CDS with reduced size. Marking process selects each node with two unconnected neighbors as a gateway, therefore it requires the availability of 2-hop neighbor information at each host to let it determines whether all its neighbors are directly connected or otherwise. Figure 3 depicts an ad-hoc network with constructed CDS according to the marking process, in which hosts B and C have been selected as gateways since they have two unconnected neighbors.
| Fig. 3: | An ad hoc network with connected dominating set |
| Fig. 4: | Checking for connections between neighbors in EMP |
To consider unidirectional links, the mutual existence of nodes in the neighbor tables of their neighbors which is indicated in the first case of Fig. 2 is examined. This is to ensure whether the neighbors for a given node are all directly connected to each other (pairwise connected) or otherwise. Figure 4 gives a pictorial description for this checking process, hosts u and w are neighbors to the same host ‘v’ and they are checked by v if they are included in the neighbor list of each other which means there is a bidirectional link between them.
From this point and by referencing to Fig. 5 which shows the flowchart for the enhanced marking process (EMP), node v tries to determine its gateway status through checking for the connections among all its neighbors. For this purpose node v inspects its neighbor table by initiating three pointers, A, B and C to check for links existence in the two directions for its entire one-hop neighbor set. Both pointers A and B are initialized to point to the first cell in the table in the first round. At each iteration in the inner loop pointer B moves to the next and when the end of neighbor table ‘list’ is reached, pointer A moves to point to the second cell while pointer B is initialized to start of the table in each iteration in the outer loop. In the mean time pointer C points to the secondary list attached to cell pointed by pointer Bat each round to check for the dual connectivity between each pair of hosts in the 1-hop neighbor set of node v. As part of the activities in the flowchart of Fig. 5, node v checks if node u exists within the neighbor list (secondary list) of node w and vice versa and it will continue investigating its existence within the secondary lists of the other neighbors in the same manner. The existence of node u in the neighbor list of each 1-hop neighbor for node v indicates link existence between host u and those neighbors. In the suggested EMP, node v will proceed with this investigation process for the complete one-hop neighbor set. The connectivity in the opposite direction for the already investigated links is examined in the subsequent iterations of the outer loop of pseudo code in algorithm 1.
If it happened and there was no mutual existence between two of its neighbors at each other’s neighbor list, host vwill consider itself a gateway since it has two unconnected neighbor as indicated in the last part of the flowchart. The pseudo code for enhanced marking process is illustrated in algorithrm 1.
| Fig. 5: | Flowchart of the enhanced marking process (EMP) and an illustration for the pointers settings, (a) pointers settings bidirectional link between A and B, (b) Unidirectional link from A-B and (c) Unidirectional link from B-A |
| Algorithm 1: | Pseudo code for the marking process |
Algorithms complexity calculation: As highlighted in the previous section, to build proper dominating set, unidirectional links must be considered and this can increase the computational complexity of the marking process. However, the huge advances in computers processing capabilities and the emergence of powerful processors and System on Chip (SoC) ICs at very low cost have mitigated the difficulties which can be faced in the implementation of algorithms with relatively high complexity. In this section, the complexities of marking process in its old version and the newer one shall be traced. In case when all links between nodes are considered bidirectional, the complexity of the marking process can be determined with the demonstration given in Fig. 6.
In Fig. 6, if the address of node u1 is found within the addresses’ list attached to node u2, it means u1 and u2 are neighbors due to the link existence between them and since it is assumed in advance that is all links between nodes are bidirectional. This will lead to conclude for link existence in the opposite direction from u2 to u1.
| Fig. 6: | Neighbor table of node v |
Therefore, when it comes to check for u2 existence in the addresses’ lists for the neighbors of node v, in order to check for pairwise connectivity condition, there is no need to check for u2 presence in the addresses’ list attached to host u1. This checking will apply to any other case in which one of two nodes exists in the 1-hop neighbor table of the other node. Therefore, the computational complexity of marking process in ad hoc network with all bidirectional links and according to Fig. 6 is as follows:
Lets n be the number of neighbors of node vand since the complexity calculation is made according to the worst case scenario that means the algorithm will run until it checks all the neighbors’ connections, the big O notation for this case will be as in Eq. 1:
| (1) |
According to marking process, the checking process will terminate and the node performing the checking will consider itself as gateway as soon as it finds out it has two unconnected neighbors. Eq. 1 reveals the number of examinations made by a node running the original marking process for connections of each of its neighbors according to Fig. 6, the first neighbor checks its connection with the all remaining n-1 neighbors of node v, whereas the second neighbor needs to check its connections with only n-2 neighbors, because it is already confirmed that there is a connection between the first and second neighbors in the first checking round and since it is assumed that all links are bidirectional, there is no need to check again about existence of link from the second neighbor to the first one. In this way, the third neighbor needs to check its connection with only n-3 neighbors and so on till the last neighbor will not need to make any check since it is already fixed that it has connections with the all previous neighbors. Eq. 1 can be rewritten as shown in Eq. 2:
| (2) |
The first term is equal to n (n-1) and the second term can be rewritten according to the finite sum formula as shown in Eq. 3:
| (3) |
By replacing each n in Eq. 3 with the (n-1) according to the second term of Eq. 2, the final expression for the algorithm complexity will be as shown in Eq. 4:
| (4) |
The last equation indicates that the calculation needed to be performed by a node to determine its gateway status in case all the links are considered bidirectional is half of what is required by the node when the unidirectional links are considered. In the second case each neighbor node ‘ui’ of node v in Fig. 6 needs to check its connections with all n-1neighbors of node v. In this way, the algorithm complexity for EMP which considers unidirectional links will be as stated in Eq. 5:
| (5) |
RESULTS AND DISCUSSION
Here, performance investigation for EMP is carried out and compared against the results obtained with original marking process. The following metrics are considered for comparison between the two algorithms:
| • | Maintenance overhead |
| • | No. of times the links broke |
| • | Data delivery |
To investigate the aforementioned metrics in dominating sets constructed with both the original and enhanced marking process, each one is implemented with AODV protocol to establish CDS in an ad hoc network. To mimic the environment where some nodes have lower transmission ranges than the others, 25% of nodes with each of the created scenarios have been assigned a lower transmission range, with a reduction of 25% from the original value. Table 1 illustrates the number of nodes with attenuated transmission range for each scenario and the attenuation amount with each investigated transmission range.
QualNet version 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 2.
Maintenance overhead: The maintenance overhead for both types of CDS are displayed in Fig. 7 with transmission ranges of 200, 300 and 400 m in parts 1, 2 and 3, respectively. It is clear from the figure, the CDS-b that is constructed with assuming all links bidirectional, generates lower maintenance overhead than its counterpart that considers unidirectional links.
| Table 1: | No. of nodes with reduced transmission ranges and the new values for their transmission ranges |
| Table 2: | Considered scenarios parameters |
| Fig. 7(a-c): | Maintenance overhead obtained with CDS-unidirectional and CDS-bidirectional (a) 200 m transmission range, (b) 300 m transmission range and (c) 400 m transmission range |
| Table 3: | Average raise in maintenance overhead resulting in CDS-unidirectional |
This is attributed to the increment in number of nodes that were recognized as gateway hosts compared with those nodes that have been considered as gateways in the case of networks with all bidirectional links. This increase comes according to the alterations made in EMP to consider mutual existence of nodes’ addresses in the neighbor tables of their respective neighbors.
Table 3 gives the percentage increase in maintenance overhead when marking process is modified to consider unidirectional links. The table illustrates the resulting increase in overhead with each inspected network size with reference to the overheads obtained when the original marking process is applied to obtain the CDS.
| Fig. 8(a-c): | Links breakages obtained with CDS-unidirectional and CDS-bidirectional (a) 200 transmission range, (b) 300 transmission range and (c) 400 transmission range |
Link breakage: By the same token, numbers of links breakages were also measured at the same transmission ranges of 200, 300 and 400 m, respectively for both types of dominating sets generated by EMP and the original marking process. Figure 8 displays graphs comparing links broke in ad hoc networks with dominating sets generated by EMP and the original algorithm. It can be seen from the figure that the number of links broke goes down with each increment step in the transmission range in both types of dominating sets. This decrease can be explained as a result of expansion in the coverage disk of each node. This stems from the fact that, when a group of neighboring nodes start to move together, or they are already moving, there is greater chance for them to keep links connectivity among them when they have higher transmission ranges, since they can move for further distances while their connections still intact. It is apparent from Fig. 8 that CDS-unidirectional which has been generated by EMP has a lower links broke than CDS-bidirectional at the three examined transmission ranges and with all inspected network sizes. This is due to the sturdy built of CDS-unidirectional compared with CDS-bidirectional since EMP in the first type checks for links availability between nodes in both directions. Therefore, more nodes are considered as gateway hosts since the condition of a node with two unconnected neighbors will happen more frequently than what can take place when all links are considered as bidirectional.
Table 4 gives the average reduction in number of times the links broke achieved with EMP. The table shows the reduction percentages in links broke in the inspected network sizes with CDS-unidirectional with reference to those obtained when the original marking process has been applied to obtain the CDS-bidirectional.
It can be seen from Table 3, the average increase in maintenance overhead when the EMP is applied and with all inspected network sizes in this study were between 4.6% as the minimum measured raise and 7.1% as the maximum one. This happens when compared with the overheads produced by CDS-bidirectional as the baseline, whereas it is obvious from the values in Table 4 that the networks employing EMP have given a significant reduction in links breakages compared with the same networks that establish dominating sets by assuming all links are bidirectional (CDS-bidirectional).
Data delivery: The impact of links breakages reduction appears evidently on the data delivery ratios in networks with CDS-unidirectional, this is illustrated in Fig. 9 in parts 1, 2 and 3 which declare the number of received data packets for the inspected networks sizes at transmission ranges of 200, 300 and 400 m, respectively. To clarify the graphs in Fig. 9, Table 5 gives the details of Constant-Bit Rate connections (CBR) that were established between the pairs of nodes in the developed scenarios.
Table 6 shows the number of data packets received in networks with CDS-unidirectional and CDS-bidirectional established by EMP and the original marking process, respectively, with the same transmission ranges indicated previously.
| Table 4: | Average reduction in link broke with CDS-unidirectional |
| Table 5: | Details of the CBR connections in the developed networks scenarios |
| Table 6: | No. of data packets received in networks utilizing the enhanced and the original marking process |
| Fig. 9(a-c): | Data delivery achieved with CDS-unidirectional and CDs-bidirectional (a) 200 m transmission range, (b) 300 m transmission range and (c) 400 m transmission range |
| Table 7: | Average raise in the delivered data packets |
Table 7 gives the average raise in data delivery ratio in networks utilized EMP to construct the dominating sets. The table gives the increment in data delivery for each inspected network size against the data delivery obtained when the original marking process is applied to construct the CDS.
EMP is compared with two algorithms developed to construct CDS in mobile ad hoc networks having a certain percentage of unidirectional links (Wu, 2002; Thai et al., 2007). Both algorithms expressed their performance in terms of size of the generated CDS. Wu (2002) employed an extended marking process to construct a connected dominating and absorbent set for an ad hoc network implemented on a square terrain area of 100x100 m.
| Table 8: | Sizes of the generated CDS with enhanced and extended marking process |
| Table 9: | Sizes of the generated CDS with enhanced marking process, TFA and TSA algorithms |
The transmission range was set to 50 m while the percentage of unidirectional links ranged from 0-15%. The network size was increased in the implemented scenarios from 20-100 nodes at increment step of 20 nodes. For comparison purposes, the connected dominating set generated by the enhanced marking process was re-tested under the same aforementioned conditions. Table 8 shows the generated CDS size by each of the enhanced and extended marking process.
In addition, EMP performance is compared against that of the algorithms presented by Thai et al. (2007). The authors developed two algorithms referred to as, the First Algorithm (TFA) and The Second Algorithm (TSA), respectively. In both algorithms, a Maximal Independent Set (MIS) is first found and then its nodes are connected with the aid of Steiner tree with a minimum number of Steiner nodes. To compare EMP performance against TFA and TSA algorithms, the same simulation conditions used by the respective authors are followed by developing a scenario within a terrain area of 800x800 m. Each node in the scenario is assigned a transmission range between 200 and 600 m. The authors tried network sizes starting from 10 till 200 nodes with a subtle increment of one per step. In order to compare the enhanced marking process with TFA and TSA algorithms, five network scenarios have been developed with sizes starting from 20-180 nodes with increment of 40 nodes per step in order to cover almost the whole scope of networks sizes examined by the authors.
It is apparent from Table 9 that the TSA algorithm outperforms our approach and the TFA algorithm. This is due to the use of Steiner tree with a minimum number of Steiner nodes to interconnect the nodes selected as members of the MIS. Besides that, the optimization of TSA over TFA algorithm and our approach is that it selects the nodes with the biggest disks i.e., the nodes with the highest transmission range as members of the MIS.
CONCLUSION
In this study, marking process which is an efficient distributed algorithm functions to generate dominating sets in wireless ad hoc networks, has been thoroughly investigated. However, this algorithm has been developed to generate dominating sets in wireless ad hoc network represented by unit disk graph. An enhanced algorithm which is based on the original marking process is presented to consider generation dominating set in mobile ad hoc network represented with a general graph, where nodes have different transmission ranges. The functionality and efficiency of the proposed algorithm ‘EMP’, have been tested through several simulation runs that have been carried out with QualNet version 5.02. The proposed algorithm has been compared against the original marking process, where it has shown a noticeable optimization in terms of overhead, link broke and data delivery. It is also compared with two other distinctive approaches in this domain and it has given favorable results in terms of the generated dominating set size.