1 Introduction

In wireless networks due to the broadcast nature, excessive redundant transmission occur, causing a serious problem, referred to as the broadcast storm problem [1, 2]. To alleviate this problem virtual backbone routing is proposed, where subset of nodes or communication links in charge of providing services to the complete network. Its size should be small enough to leverage scalability problems. The structure designed must be stable and resilient to node failures. From graph theory, a set (V,E) in graph G is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. A connected dominating set (CDS) can form an interesting virtual backbone.

As virtual structures with backbones are likely to be used by routing protocols, less control messages are exchanged between nodes, such as routing table updates, increasing the available bandwidth for real time communications. The backbone must be node-failure tolerant. This characteristic is very important as losing one node may result in a useless backbone. A backbone should be characterized by a small stretch; otherwise it would induces a substantial decrease in some quality of service (QoS) measures (round-trip time, percentage of successful delivery). In this paper, the proposed algorithms follow distributed and localized computations for virtual structure construction and maintenance.

1.1 Research issue

Nodes in wireless ad hoc networks communicate via shared medium, either through a single-hop communication or multihop relays. In order to enable data transfer in such networks, all the wireless nodes need to be frequently flooded control messages i.e. control overhead required during the node movement (backbone and other nodes), added with new node (when it stop travel). Three time calculations are required (if backbone only considered) to update or reconstruct the backbone thus causing a lot of redundancy, contentions, and collisions. Similar manner all the nodes are in movement ‘n’ time calculations are required. The only solution to reduce the control over head is each node must work on its own desire and minimum updations required if a node change its position: conserve their resources and work in self organized manner. The above issues must be satisfied by a backbone node during movement and stable conditions.

1.2 Related work

A virtual backbone of a wireless network is typically the connected dominating set (CDS) of the graph representation of the network. It is defined as a subset of nodes in a network such that each node in the network is either in the set or a neighbor of some nodes in the set, and the induced graph of the nodes in the set are connected. In general, Finding the Minimum CDS [3–5], is an NP-hard problem. The smaller the CDS size, less the communication and storage overhead the protocols making use of CDS will incur. Hence, it is desired that the size of the CDS for MANETs to be as small as possible. Feng et al. in [6], proposed a connected dominating set augmentation algorithm (CDSA) to construct a 2-connected virtual backbone that can accommodate the failure of the nodes. The main idea is to first construct a connected dominating set, and then augment it to be 2-connected by adding new nodes to the backbone. The CDSA has a constant performance ratio of 72, thus the quality of CDSA is guaranteed. To validate the proposed work in mathematically CDSA approach is used.

Similar types of CDS with unidirectional links are analyzed from [7–9]. Most of the works in the dominating set follow the Wu and Li’s marking process [10], each node is marked (i.e., in a CDS) if it has two unconnected neighbors. The marking process is effective in reducing the size of the CDS. In addition, it supports localized maintenance in a mobile environment. However, the process incurs a high communication and computation cost in a dense network, since each node needs to exchange neighbor sets among 1-hop neighbors and to check all pairs of its neighbors. Wu et al. in [11] and Sun et al. in [12], proposed a 2-level hierarchical approach in which the messages are transmitted using a long transmission range by a small set of selected cluster heads that form the upper level backbone, and a short transmission range by other cluster heads the forming lower level backbone. In 1-level flat approach, messages are transmitted by only selected cluster heads using a long transmission range. The 2-level approach is more energy efficient, as few nodes use the long transmission range. The 1-level approach has a simpler routing process and uses few backbone nodes.

A distributed algorithm is proposed by Alzoubi et al. in [13], that outperforms the existing CDS algorithms. This algorithm has an approximation factor of at most 8, time complexity O(n) and message complexity O(nlogn). Localized and distributed CDS approaches deliberated from [14, 15], describes an extended dominating set (EDS) based on the cooperative communication model. The problems of finding a minimum EDS, ECDS (connected EDS) and EWCDS (weakly connected EDS) are shown as NP-complete. Virtual Backbone Routing (VBR) is proposed in [16], which combines local proactive and global reactive routing components over a variable-sized zone hierarchy. The zone hierarchy is maintained through a novel distributed virtual backbone maintenance scheme, termed the Distributed Database Coverage Heuristic (DDCH), which is scalable in dense network. Broadcasting based algorithms based on backbone constructions are studied from [17, 18], where directional antennas are used and the transmission/reception range is divided into several sectors, and one or more sectors can be switched on for transmission. Therefore, data forwarding can be restricted to certain directions (sectors), and both energy consumption and interference can be reduced.

The self stability backbones are studied from [19–21], the objectives of the papers are based on, either locality-based hierarchy structure, or a routing protocol that uses a hybrid of proactive and reactive routing information. The proposed work follows decentralized cluster computing with demand based routing. This is the major difference between virtual cluster and [19, 20]. Clustering based ad hoc backbones are analyzed in [22–25], the idea behind this work is networks characterized by a large number of resource-constrained nodes and only the local information affects the overall protocol performance. Finally the maintenance of virtual structures are studied from [26–28], which is mainly focus on connectivity issue.

1.3 Organization

The remainder of the paper is organized as follows: Sect. 2 presents the definitions and notation. Section 3 describes the construction of fusion structure formation with mathematical proof. Section 4 gives the idea about the link based analysis with alternating possibilities in backbone domain. Section 5 shows the cluster backbone approach with theoretical analysis. Section 6 shows the simulation results and performance analysis. Finally Sect. 7, concludes the paper.

2 Definitions and notations

For textual representation the following abbreviations are used.

Normal/leaf nodes::

Except from one or two hop backbones other nodes are named as normal nodes or leaf nodes.

One and two hop connected CDS::

Neighbor connectivity/information sharing with one or two hop nodes.

VS L1, 2&3::

Virtual Structure maintained via Link 1, Link 2&3.

Backbone Tree (BT)::

A local tree, each backbone has own tree with maximum of three hop connections.

Network Tree (NT)::

Connect all the backbones with leaf nodes.

Protocol model::

Link Quality Dominating Set (LQ-CDS), Fusion Backbone (FB) approach and Cluster Backbone Approach (CBA).

2.1 Connectivity model

To analyze the performance of the proposed work a simple connectivity model is formed, named as KLN. Where K states the CDS connection in hops i.e. K=1 defines the one connected CDS. From the Fig. 1, distance between backbones (black colored nodes) is one hop. Similarly K=2 and 3 are two and three hop backbone connections. L defines the length of CDS, measured by hop count. Finally N defines the number of neighbor nodes of the backbone.

Fig. 1
figure 1

KLN connectivity model

Full size image

3 Proposed work—fusion backbone formation

Fusion is a data gathering method in wireless sensor networks, with this connection we form a new mechanism named as fusion backbone nodes. Fusion nodes are obtained from connected dominating set. A simple protocol design includes the header, payload and error detection fields in the wireless routing domain. In addition the number of hop counts are also considered for higher layer protocols like TCP for setting the discard eligibility of the packet. In fusion backbone design, the protocols must be aware of the fundamental looping problem and sustain in node and link failure situation. In other words, fusion node must find the path during the link failure and carry other node information during the routing process.

3.1 Algorithm for fusion structure formation

Coloring scheme is used to form the Fusion node in ad hoc network. The different nodes like fusion backbone, normal nodes are identified by coloring scheme. Initially all nodes in the unit disk graph are colored black and based on marking scheme each nodes are colored, red for fusion backbone, blue for virtual backbone and rest of the nodes (leaf nodes) are colored black. The fusion node formation is given in Algorithm 1. It follows two steps (1) Backbone formation and (2) Fusion node identification. Fusion nodes are formed by the extended version of Wu and Li’s [10], i.e. each node is marked (i.e., in a CDS) if it has two unconnected neighbors. It will be modified as follows: “if a node is marked as a fusion backbone if it has at has high coverage area and at least with two connected neighbors (one virtual backbone and leaf node) within its coverage area and each fusion node elected based on high coverage area”. Backbones are the second level nodes (one hop with fusion node). Wu and Li’s method follows flat routing structure for dominating set construction, where fusion backbone follows the hierarchical structure with demand based routing. Each neighbor is identified by the unique id to avoid looping problem. A network with tree based structures requires extra overhead and requires O(n) time complexity at the initial stage. Only fusion nodes are elected at the initial stages with tree structure, hence the complexity in the order of O(logn). To connect the ‘n’ number of nodes at each stage the complexity increases in the order of O(nlogn). The algorithm describes two states (1) Stable state-nodes are fixed and randomly placed in the network and (2) Mobile state-mobile backbones partial leaf nodes.

Algorithm 1
figure 2

Fusion node formation

Full size image

3.2 Theoretical analyses

Theorem 1

If a network is constructed without flooding it follows fusion protocol. (Flooding reduction.)

Proof

Assume the network topology remains connected and stable for a period of time, the collection of all nodes resulted from the fusion protocol forms a connected dominating set. After the leaf node election and tree construction phases, a set of disjoint leaf nodes and backbone trees will be created. The nodes in these dominator trees together form a dominating set. The neighboring dominator hops are determined by the node degree value. It may take one to k-hop value. Let a virtual structure formed by at least node degree 3. At most three nodes are added with fusion backbone at each stage in graph G. Fusion node are colored red and other nodes are colored black. Suppose f is the fusion node and n is the leaf node with following subset in G. Let f 1,f 2,…,f n and n 1,n 2,…,n n be the subset of G. If two n nodes follow same one hop connection and the edge of f and n is removed from the graph G, connections are maintained via f 2 (during the absence of originating fusion node). Since G be a connected graph and f connects both backbone and n nodes within the coverage area. Similarly if the network follows n-hop connection each nodes connection is maintained via neighboring fusion nodes without looping problem. Hence the theorem is proved.

In order to prove the effectiveness of the algorithm, the following theorem was proved. □

For connectivity analysis the following theorem is proved.

Theorem 2

A fusion node able to connect n nodes in k-hop. (For connectivity.)

Proof

Let f, b, and n be the hierarchical structure for fusion, backbone and normal nodes respectively. If f 1,f 2,f 3,…,f k be the number of fusion nodes in the network able to connect one hop unconnected b nodes within the coverage area. Similarly node ‘b’ able to connect multiple ‘n’ nodes without looping. The value of addition of the ‘n’ nodes with fusion set must obey the relation; i.e. f Δ ≤b Δ ≤n Δ (one hop connection), where Δ—be the node degree. Assume that k-hop connection between fusion and other nodes. The maximum number of node connectivity of the fth system is given by f i +b i ≪n i , for i=1,2,3. Connectivity of a network is defined as the probability of the number of one hop fusion connecting from one non backbone to another node in the graph. For sleep node and active nodes are computed by virtual structure (G be a connected graph); s n be the sleeping node, then s n1,s n2,…,s nn ∩G(V,E) otherwise s n1,s n2,…,s nn ∪G(V,E). The theorem is proved. □

Lemma 1

The fusion structure algorithm computes active node, ideal nodes in G. (Power saving mode.)

Proof

From Theorem 1, the tree (T) contains a fusion and dominating set of G. Let u and v be a pair of vertices T. The hop count for graph G and sub graph G′ may be unequal. Let G contain longest path between u and v. But G follows the shortest path due to unconnected neighbor property. The path in G and G′ are namely p and q respectively. If be a connected graph, a and s are active and sleep nodes of G and a′ and s′ be the nodes in G′. Set the value of p and q as follows

If G is loop less and formed by greedy method then v is a cut vertex (dominator) of G if and only if G−p>G. Similarly G′(p′) is the result from fusion structure follows the same cut vertex property. If G is able to predict the value from the above equation, G′(p′) also follows the same using hop count. Hence the theorem is proved. □

4 Link quality CDS construction

The process of maintenance required during the movement of backbone nodes or battery drained conditions. To construct backbones, coverage area is used and the maintenance is done via one hop neighbors within its own backbone tree and alternate routing done via 2 connected backbones. Backbone node periodically sends the link bandwidth information to a one hop neighbors and select the eligible backbone for next level routing within the coverage area. Different coverage area nodes are identified in the backbone tree and the next level nodes are selected based on hierarchical order. During the backbone movement next level node is elected as a tree header. In this approach three coverage areas like 100 m, 200 m and 300 m are chosen for simulation analysis. If one hop node needs an alternate routing it is performed via nearby backbones (if service providing backbone fails) and if two hop node requires a new path it is coordinated via service providing backbone. This localized computation in distributed manner support the alternate routing throughout the network tree. Algorithm 2 gives the details of link quality backbone construction and maintenance.

The proposed methodology uses two level of hierarchical structure for routing the information to the destination i.e. different coverage areas and link bandwidth. In the first level routing performed in backbone tree. In the second stage uses nearby 2-connected backbone and link bandwidth is a key for alternate routing. In both cases every time backbone updates his routing table for routing to the node in one hop.

The localized routing structure is given in Fig. 2. This is performed in distributed manner throughout the network whenever the changes occurred. In this scenario A, B and C are the backbone nodes, a to h are the normal nodes attached in one hop to the backbones. Backbone A has the neighbor’s a–c, B has the neighbor’s d–f, and C has the neighbor’s g and h respectively. Suppose the node d of C wish to communicate to node h of B, the direct link d–C–A–B–h is used. The link between d to h is broken or the link support low bandwidth based on the request from the originating backbone the new route between backbone nodes A to destination h is created based on the available bandwidth, one hop connections. The finalized route is d–C–A–a–h with the bandwidth of the link 4 Mbps. In this way number of backbone will be reduced and the new links are formed in 2 hops away from the backbone. In this scenario three level hierarchical architecture used for alternate routing and named backbone, eligible and reserved backbone nodes. The entire routing and connectivity procedure is given in Table 1.

Fig. 2
figure 3

Link updations based on bandwidth

Full size image
Algorithm 2
figure 4

Link quality backbone maintenance and alternate routing

Full size image
Table 1 Alternate routing possibilities
Full size table

5 Cluster backbone approach (CBA)

In this section, a decentralized approximation method called virtual cluster algorithm is proposed for clustering the wireless Ad Hoc networks by finding a near optimal solution to the connectivity problem. Clustering method based on the assumption that the entire area is divided into smaller zones named as clusters and elects the cluster head for information exchange. An alternate method is proposed in this work. Firstly entire area is divided into small area and a backbone set is formed based on the random selection of nodes by hello messages. Size of the cluster is determined by the backbone node not by area divided at the time of network formation. If a node enters a new area, it sends the hello packet and waits for t seconds. If no response is received during this time interval it will become a Virtual Cluster Head. If a response is received with a new id, it knows already a virtual cluster head (H vc ) is present in that area. During collision of packets the originating node sense the medium for another t seconds and do the same above mentioned process. The entire routing process is given in Fig. 3.

Fig. 3
figure 5

Cluster backbone approach based on node degree

Full size image

Cluster structure formation based on hierarchical architecture is as follows: (1) CBA node with high degree, (2) virtual node with degree three, (3) leaf nodes (attached with any one of the above). The hierarchical order provides many connections in one hop and performs alternate routing during movement. After the cluster structure construction, each node involves in routing and information processing. The sleep node information is maintained by the cluster head and it is used for topology control and increasing the network life time. To maintain the topology and connectivity, leaf nodes are resumed by the cluster head when required. Finally normal node (also named as leaf node) involves only information exchange process and it will become backbone node when the existing backbone fails. In the proposed work, node degree is counted only from the virtual node to leaf nodes, not between the virtual nodes. Most of the existing research work restricts the leaf nodes movement i.e. it must roam inside the cluster heads coverage area. But in this work, there is no restriction on leaf nodes movement, once it comes out of the cluster it acts as backbone node. Cluster structure formation is given in Algorithm 3.

Algorithm 3
figure 6

Virtual cluster formation

Full size image

5.1 Correctness

To prove correctness of the proposed algorithm, coverage area and node degree based connected localized cluster structure is considered. An argument in algorithm: (i) in line 4, C is divided into c clusters of different size, c∈C and (ii) in line 12, collision occurred with other nodes, wait random time t c and listen the medium for next header election and (iii) in line 20–23, if x comes out from v c then, dominator=k, it has been proved as follows: for (i) if a graph G is connected, network partition into small zone c, then add edges with virtual clusters to form a CDS. For (ii) during collision time t c , node wait again t seconds for next H vc . Waiting time follows: t<t c . For (iii) if one node is removed from graph (G), it divide the network into two portions (cut vertices), leaf node become localized virtual node, it means that a graph G is connected, the number of CDS is reduced due to node movement to inter and intra levels of the cluster. If x come out from c, x be the cut vertex of c, must maintain a connection with c (worst case) it proves final correctness (iii).

5.2 Complexity

The computation complexity of virtual cluster algorithm is O(n 2logn), resulting from network partition, virtual cluster head and backbones. In the CBA algorithm one virtual head may potentially need to be executed as many as O(n) times for each of the O(n) backbones come out from v c . Hence the complexity initially in the order of O(n 2) and logn is added to this complexity if the backbones from other virtual clusters. For finding the lowest complexity of the minimal v c , O(n+Δlogn) is required, where n is the number of nodes in graph G and Δ-node degree.

5.3 Approximation analysis

Let v c be the set of virtual clusters selected to interconnect v b virtual backbones and n normal nodes in CBA. Let |OPT| (optimum CDS size) represent the cardinality of an optimal solution of the MCDS problem in the plane. OPT can utilize the zone covering points across the network. Let Z vc denote the worst case approximation ratio of the algorithm v c . Z vc is the maximum of H vc /v b over all virtual set configurations in graph G. OPT size of the virtual cluster is given by, |OPT| size of c=v c (e 7)+v b (e 2)−1, where e 5,3 denote the node degrees of v b&c and forward link is neglected. Hence size of Minimum CDS=v c (6)+v b (1)+1 (dominating set includes node degree between v c to v c , v b to v b ). For each normal node at least two node degree must be exist, from [29], |1CDS|≤|8MCDS|+1, for CBA (CDS)≤8[(6v c +1v b +1)]+1≤(48+8+8)+1≤65 (forwarding node degree v c =v b =1).

6 Result analysis

In this simulation each host is modeled as an infinite-buffer, store-and forward queuing station. The IEEE 802.11 Distributed Coordination Function (DCF) with Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) is used as the medium access control protocol. All the simulations are conducted using ns-2 with 300 nodes with a 1250×1250 m2 deployment area and random way point model. Three different coverage areas 300,100 m are assigned for backbones/fusion and normal nodes, where 200 m is assigned for next eligible node in the backbone tree. Due to the larger coverage area of the backbone node, many nodes added in its backbone tree. Each backbone tree has one reserved node; it is used during the transient conditions. The idea behind this at each time a backbone tree contains at least one backbone and one reserved node. A set of 10 backbone trees are constructed in stable manner, after the initial transmission mobility applied from 10 m/s to 30 m/s, i.e. 10 m/s for three backbones randomly selected and other nodes permitted to move with other speed rate with in the backbone tree. The maintenance process is accompanied by different bandwidth associated with multihop links. The number of backbones required per network size is compared with three existing methods: LQ-CDS [30] and Javad’s cluster method [31].

6.1 Performance metrics

In the proposed approach localized virtual structure concentrate on the issues of 2-connected backbone with link updations for alternate routing. The following parameters are used to analyze the performance of our work.

  • Scalability: As the large number of nodes in wireless network increases, scalability imposes difficulties in transferring data. To overcome this issue virtual structure mechanism is proposed with 300 nodes. The following CDS performance are analyzed in the simulation.

  • Network size vs. CDS: Number nodes versus connected dominating set as a function of 300 nodes are considered. (1CDS-one hop neighbor information; 2CDS-2hop neighbor information).

  • Control load: The control load analysis is based on number of broadcasting packets required to connect the nodes with the backbone.

  • Packet Delivery Ratio (PDR): It is calculated as the ratio between the number of data packets that are sent by the source and the number of data packets that are received by the intermediate or destination node.

  • Reformation rounds: It is a measure of number of rounds required for construction and changed to other CDS connection.

  • Hop stretch (Hs): Ratio of number of hop count by CDS to the original hop count between any two nodes. Hop stretch between the nodes u and v=CDS Hs(u,v)—/original Hs of (u,v).

6.2 Simulation results

In the simulation two types of localized structures are analyzed; (1) with stable nodes and (2) partial mobile nodes. Connectivity model used in the proposed work is named as KLN model, where K—CDS connectivity, L—length of neighbors in hop, N—number of neighbors.

To compare the performance of virtual structures linear integer programming (i.e. min ∑L i , i=1 to 5, based on algorithm one to three) is used to solve for MANETs of these graphs, where the ILP was able to find the CDS for these graphs. From the results shown in Fig. 4, it is clear that proposed LQ-CDS always constructs the largest CDSs, and so is ranked lower the other algorithms. The size of the CDSs generated by FB, CBA and LQ-CDS (30) are only slightly smaller than DLA (30). The results show that the number of dominators increases as the number of nodes increases. DLA outer performs than other methods in terms of size of the dominators, but hop stretch and other parameters CBA provides greater results. The entire system follows the KLN model for connectivity model as follows; 1KLN for link quality dominating set (LQ-CDS), 2KLN for Fusion Backbone (FB) approach and 3KLN for cluster backbone approach (CBA). From the Fig. 5, basic 1KLN model require nearly 50 % of nodes must act as a backbone, and core CDS and 2KLN method requires with equal size of dominators i.e. around 27 % backbone nodes. Finally the 3KLN model maintains the 3 hop neighbor information; hence it requires only 13 % backbones to maintain the connectivity of entire network. Only stable nodes with backbone size are analyzed in this case.

Fig. 4
figure 7

Network size vs. CDS

Full size image
Fig. 5
figure 8

Control load vs. network size for different connectivity model

Full size image

During the construction of backbone, an effective marking process is applied, initially all the nodes are in black color and first level iteration the backbones are colored by red and the first level reserved nodes are represent by the green. The following parameters are observed: control message transmitted per nodes, packet delivery ratio and different connected dominating sets for network size of 300 nodes.

The performance of 2KLN model (LQ-CDS) and CBA are same in terms of control load requirements due to 3 hop neighbor information and link updations between neighbors. The control load analysis is based on number of broadcasting packets required to connect the nodes with the backbone and other nodes. For 1 and 3KLN the control packet rate is increased gradually to reach the peak value for 625 packets for 300 nodes. For 1 and 3KLN, initial backbone formation and acknowledgements are account able factors. In other hand 2KLN requires minimum number of control packets and the control rate for each is displayed in Fig. 5. Initially network grows with adding 4 nodes (3 leaf node and forwarding backbone node) to each backbone to form 3KLN connectivity model.

To analyze the performance of the localized structure group of 30 nodes are considered and the number of reformation round for different connectivity model is given in Fig. 6. First model (1KLN) requires only one round of reformation, due to 1-CDS connectivity; while the other two requires more reformation rounds. The last model wish to change to second model it needs one round of reformation. Similarly the network formed by one dominating set model again it requires one more reformation and initial round also considered a total of three reformations required for 3KLN model. The average link bandwidth is degraded in 3KLN model when the network size is getting bigger. However, the other two connectivity models are tolerant to the size of network. Therefore to support more number of nodes within the coverage area, K,L,N=2 model is preferred. Other models are scalable but not sufficient for adequate Quality of Service. Figure 7 gives the information about the protocol duration for different connectivity models. 3KLN requires initially 2 seconds for 30 nodes and reaches the maximum value of 3.1 seconds for 300 nodes. The other connectivity models form by, only less than 2 seconds for 300 node size. The protocol duration is gradually raised when the network size is increased. If local computations are minimum protocol duration is maintained. For 300 nodes Fig. 8 shows the packet delivery ratio of 2KLN (Fusion Backbone) algorithm, it is defined as the ratio between the number of data packets that are sent by the source and the number of data packets that are received by the intermediate or destination node. The FB model is scalable for dense network and the control overhead requirements are also low compared to other models. A packet size 128 byte transmitted with 2KLN model and different PDR values are analyzed in the proposed work.

Fig. 6
figure 9

Number of reformation rounds for localized structure

Full size image
Fig. 7
figure 10

Protocol duration for different network size

Full size image
Fig. 8
figure 11

Packet delivery ratio for various transmission power

Full size image

Three cases of PDR analysis are possible in infrastructure less network: (1) Effect of transmitting power at a node on PDR for varying number of nodes of certain group size, (2) Effect of multicast group size on PDR for varying number of nodes, and (3) Effect of group size over PDR for varying speed of nodes for a fixed group size. The analysis of PDR follows the first method and shows that there is an increase in PDR as power at transmitting node increases. We also observe that, as the number of nodes increases (from 50 to 3000) in the network, the delivery of packets increases since there is a possibility of decreased hop length between the nodes with increase in number of nodes, which enhances the link stability and reduces packet drops. The noise signal dominates at low transmission power levels than at higher levels that resulted in less PDR at lower power levels. The increase in PDR is fairly stable at higher power levels (more than 300 mW), where the network reaches saturation level since the traffic exceeds bandwidth one-hop at every node leading to constant packet drops. This model performs well at the time of network size grows larger in size. The entire value rounded around to 100 percentages, 300 is the low packet delivery (50 %) ratio than other network size. Finally transmission range and node degree analysis are also included in the proposed work. Each stage the node degree represent by the numbers of K, L and N. From the comparison node degree with 5 requires nearly 15 % of nodes must act as a virtual node, where as node degree 3 and 1 requires more than 50 % backbone nodes. Due to high node density node degree five is preferred for control exchange and it also need more control load for initial construction and maintenance.

Hop stretch (Hs) is the ratio of number of hop count by CDS to the original hop count between any two nodes. Hop stretch between the nodes u and v=CDS Hs(u,v)/original Hs of (u,v). Hop stretch for a graph G is calculated from greedy algorithm, here Kruskal algorithm is used to calculate the number of hops for G. the Hs for the VB and CBA is given in Fig. 9. For all the method Hs lies between 1–1.8, FB and CBA requires minimum hop count due to minimum degree backbones and other approach (LQ-CDS) requires localized link bandwidth computation with maximum hop count.

Fig. 9
figure 12

Hop count ratio for various network condition

Full size image

7 Conclusion

The main contribution of this paper is an analysis of the virtual system with node degree, transmission range and link based computations. The virtual clustering is a method by which the hosts are hierarchically organized on the basis of the proximity, and the hierarchical structure thus formed abstracts the personal communication networks so that the hosts can be simply and locally organized. In this article, first proposed a fusion protocol for solving the minimum CDS problem and secondly a link based dominating set and finally a approximation algorithm CBA for clustering the wireless Ad Hoc networks. The proposed clustering algorithm is a distributed implementation of virtual structure with inter and intra cluster domains. In this article, an upper bound on the time and message complexity of the proposed clustering algorithm for finding a near optimal size cluster-head set. And also node level computations is a very challenging issue in fast moving distributed dynamic networks to solve connectivity problems. This work defines a model for a mobile ad hoc network and proposes stable connection maintenance between nodes and also support alternate routes. The proposed approach performs well in different traffic and network conditions.