1 Introduction

The dominating tree problem (DTP) [11] is one of recently encountered combinatorial optimization problems in the field of wireless sensor networks (WSNs) due to its practical relevance in routing. The DTP is defined as follows: Let G = (V,E,w) be an undirected, connected, and weighted graph, where V is the set of vertices (nodes), E is the set of edges, and for each edge (u,v) ∈ E, there exists a non-negative weight. The DTP deals with finding a dominating tree (d T r e e) of minimum cost on G in such a way that each vertex of G is either in d T r e e or adjacent to a vertex in d T r e e. Vertices that are in d T r e e are called dominating nodes, whereas vertices that are not in d T r e e are called non-dominating nodes. Hereafter, vertex and node are used interchangeably in this paper.

Figure 1a presents a connected, undirected and edge-weighted graph G with 9 vertices and 13 edges, whereas Fig. 1b presents a d T r e e of G whose dominating nodes (< 2, 5, 6, 7 > ) are shown in dark grey color, non-dominating vertices (< 0, 1, 3, 4, 8 > ) are shown in light grey color. Thick grey edges in Fig. 1b are part of d T r e e. The total edge-cost of this d T r e e is 6.

Fig. 1
figure 1

A graph (G) and d T r e e of (G)

Full size image

The practical relevance of DTP lies in network routing as its solution (dominating tree) can be used as a routing backbone. Dominating nodes of a dominating tree of minimum cost (d T r e e or solution) that consist of a subset of nodes of WSN (graph) can be used for storing routing information, as each non-dominating node is adjacent to at least one of the dominating nodes of d T r e e. Under this setup, the edge weight can be considered as energy consumption in sending a message along with that edge. In the process of message forwarding from source to destination, the message needs to be first forwarded to the nearest dominating node of sender, then this message is further routed to the nearest dominating node of the receiver with the help of d T r e e, and finally it is forwarded to the receiver. Each non-dominating node requires to only memorize the information of its nearest dominating node. The major advantage of this scheme [20] is that dominating nodes of d T r e e (virtual backbone) that are usually smaller in number in comparison to the total number of nodes in WSNs can store such routing information, resulting overall a significant reduction in the size of routing table. Moreover, no recalculation of such routing table is required in case of occurrence of topological changes in the network, if such occurrence does not cause change in the set of dominating nodes of the network [20].

2 Literature survey

On the concept of connected dominating set, many approaches [6, 9, 17,18,19] for constructing a routing backbone with the objective of minimizing energy consumption in WSNs have been reported in the literature. However, all these approaches consider only node-weight rather than edge-weight for minimizing the energy consumption. All these papers discussed only the number of nodes obtained. In practice, the energy consumed at each edge directly effects the energy consumed in routing. This observation led to the introduction of DTP [11, 21]. They proved \(\mathcal {NP}\)-hardness of this problem together with the inapproximability and proposed an approximation algorithm with quasi-polynomial time complexity (|V|O(lg|V |)) for the DTP. Further, they also proposed two polynomial time problem-specific heuristics (respectively referred to as Heu_DT1 and Heu_DT2 in this paper) for the DTP. The performance of their proposed heuristics were compared with a method based on minimum spanning tree without leaf edges, as the resultant tree obtained after this method is also a dominating tree. In addition, there are some work related to the tree cover problem [1, 4, 5] in the literature. However, the tree cover problem is defined as a connected edge dominating set with the total minimum edge weights, whereas the DTP is defined as a node dominating set.

Later, many approaches have been developed for the DTP. Sundar and Singh [15] developed one problem-specific heuristic (referred to as H_DT in the paper) and two swarm intelligence techniques – artificial bee colony algorithm (referred to as O_A B C DT (O in O_A B C DT stands for existing ABC algorithm for the DTP) in this paper) and ant colony optimization algorithm (referred to as ACO_DT in the paper) – for the DTP. Chaurasia and Singh [2] presented one problem-specific heuristic (referred to as M_DT in the paper) and an evolutionary algorithm with guided mutation (referred to as EA/G in the paper) for the DTP. Zorica et al. [3] presented a variable neighborhood search algorithm (referred to as VNS in the paper) for the DTP. Meanwhile, Sundar [13] presented a steady-state genetic algorithm (referred to SSGA in the paper) as for the DTP.

This paper presents two new heuristics for the DTP: first one is a problem-specific heuristic that exploits the problem structure effectively; and second one is an artificial bee colony (ABC) algorithm. The proposed ABC algorithm is different from existing ABC algorithm (O_A B C DT) for the DTP [15] on two main components: initial solution generation, and determination of a neighboring solution. O_A B C DT [15] which was the first developed metaheuristic technique for the DTP and is not competitive in terms of solution quality and computational time in comparison to other metaheuristic techniques developed later. This motivated us to develop an ABC algorithm for the DTP through main two components: initial solution generation; and determination of a neighboring solution. Both proposed methods i.e., problem-specific heuristic and ABC algorithm for the DTP have been tested on a set of standard benchmark instances and compared respectively with existing problem-specific heuristics (Heu_DT1, Heu_DT2, H_DT and M_DT) and metaheuristic techniques (O_A B C DT, ACO_DT, EA/G, VNS, SSGA) in the literature. Computational results demonstrate the superiority of the proposed problem-specific heuristic and ABC algorithm for the DTP over all existing problem-specific heuristics and metaheuristic techniques respectively in the literature.

The structure of the remaining paper is as follows: Section 3 presents the problem-specific heuristic approach for the DTP. Section 4 presents a brief description of ABC algorithm and describes an ABC algorithm for the DTP. Section 5 reports computational results. Finally, Section 6 contains some concluding remarks.

3 Heuristic for the DTP

In literature, four different problem-specific heuristics (Heu_DT1 [11], Heu_DT2 [21], H_DT[15], M_DT [2]) have been so far presented for the DTP. A brief description of each such heuristic that highlights its properties is as follows:

  1. 1.

    Heu_DT1 [11] constructs a dominating tree based on active and inactive edge concepts. A pruning procedure is applied on the resultant tree.

  2. 2.

    Heu_DT2 [21] first creates a minimum spanning tree (MST) with the help of Kruskal Algorithm, then a sequence of search rule is applied to switch internal edges of MST to leaf edges as many as possible if there is a net gain. All the leaf edges of the resultant tree are pruned, and the remaining tree is a dominating tree.

  3. 3.

    H_DT [15] follows a greedy approach which is based on the concept of Kruskal algorithm and shortest paths between all pairs of vertices in G in order to construct a dominating tree. A pruning procedure is applied on the resultant tree.

  4. 4.

    M_DT [2] which is similar to H_DT [15] except selection of a next edge which is based on a criteria instead of selection of next edge based on least cost.

This section presents a new problem-specific heuristic for the DTP. The idea of developing a new and effective problem-specific heuristic for the DTP came from the observation of the objective of the DTP which lays the basis of two salient features, viz., minimum edge-weight set and set of vertices covering the given entire graph (G). This observation motivated us to focus on those nodes that cover the maximum number of non-dominating nodes in G and lead to a dominating tree with minimum cost. Particularly, the second salient feature is the key motivation for the development of a new problem-specific heuristic called H e u_2C_D T P. H e u_2C_D T P consists of two phases that are followed one-by-one.

  • Phase One: In the beginning, find shortest paths between all pairs of vertices of a given G; label each vertex unvisited; compute degree of each vertex, where the degree of a vertex, say v, is defined as the total number of unvisited vert(ex /ices) adjacent to v; and compute weight of each vertex, where the weight of a vertex, say v, is defined as the total sum of weight of edge(s) incident to v. Initially, both dominating tree (d T r e e) and the set, say S, containing dominating nodes of d T r e e are empty. Hereafter, select a vertex, say first vertex or v s , with maximum degree from V. Note that there are chances of more than one vertex with same maximum degree. If such chances exist, a first tie-breaking rule is applied. As per this rule, select a vertex that has minimum weight in V. In the course of applying the first tie breaking rule, if more than one vertex with same minimum weight are encountered in V, then ties are broken arbitrarily. The selected v s becomes a dominating node of the partial d T r e e and is added to S. All unvisited vertices that are adjacent to v s are labeled visited along with v s . Update the degree of each vertex in V ∖S.

  • Phase Two: At each step, select a vertex (say u) with maximum degree from V ∖S. Note that u may be visited or unvisited vertex. To establish a connection between u and a vertex, say v, in S, a shortest path, say SP, is determined. Each vertex except v in SP becomes a dominating node and is added to S. Each edge in SP becomes a part of partial d T r e e. Each unvisited vertex in SP along with its unvisited adjacent vert(ex /ices) is(are) labeled visited. Hereafter, update the degree of each vertex in V ∖S. Note that there are chances of more than one vertex with maximum degree. If such chances exist, a first tie-breaking rule is applied. As per this rule, select a vertex that has shortest distance from the partial d T r e e. In the course of applying the first tie-breaking rule, if more than one vertex with same shortest distance are encountered, then further a second tie-breaking rule is applied. According to this rule, select a vertex whose shortest distance contains maximum number of unvisited vertices. Again, while applying the second tie-breaking rule, if further ties are encountered, then ties are broken arbitrarily. This iterative process continues until all vertices of G are labeled visited.

Hence, a d T r e e is constructed with minimal number of dominating nodes. It is possible that constructed d T r e e on the set of dominating nodes is not optimal due to some edges which are incorrect, but are part of resultant d T r e e. Since, many dominating trees (spanning trees) are possible on the subgraph of G induced by the set of dominating nodes of resultant d T r e e. Through Prim’s algorithm [10], a new dominating tree with optimal cost (minimum spanning tree) can be constructed on the subgraph of G induced by the set of dominating nodes of resultant d T r e e. In doing so, no constraint of DTP is violated. This new dominating tree (minimum spanning tree) replaces the resultant d T r e e and becomes d T r e e. Further, a pruning method is applied on d T r e e. This method starts with examining each current leaf node, say v l f , of resultant d T r e e one-by-one. If all non-dominating nodes adjacent to v l f are also adjacent to other dominating nodes in d T r e e, then the edge incident to v l f is eliminated from d T r e e, resulting in further deduction in the total cost of the resultant d T r e e. v l f becomes a non-dominating node and is labeled unvisited. This pruning method is applied on only current leaf nodes of d T r e e. The idea of constructing MST and pruning method was first applied in [15].

figure c

Note that the idea of applying labeling vertex unvisited or visited is very common as it clearly distinguishes whether a vertex is in d T r e e or not. Similar ideas can be observed in [2, 15, 20]. The idea of applying degree concept for each vertex is rational, as each time selecting a vertex with maximum degree during the construction of d T r e e increases the chances of covering the maximum number of unvisited vertices. Also, in case of first-tie breaking rule in Phase One, the idea of applying minimum weight concept in conjunction with the maximum degree only once during the selection of first vertex or v s is intuitively meaningful, as whenever an edge (say e(u,v s )) incident to v s will get a chance to be a part of partial d T r e e during establishing a connection between an unselected vertex (u) and v s through a shortest path concept, its weight (weight on e(u,v s )) will be of possible minimum weight due to minimum weight concept on a vertex with maximum degree. Our preliminary experiments justify this intuitive idea. In Phase Two, applying shortest path concept for connection establishment between an unselected vertex and a vertex in the partial d T r e e is common-sense or intuitively correct, as such shortest path consisting of edges of minimum weight will help in constructing a dominating tree with minimum cost. Further this phase also uses two tie-breaking rules, i.e., first tie-breaking rule and second tie-breaking rule with the aim of minimizing the cost of d T r e e and maximizing the number of non-dominating nodes.

The psuedo-code of H e u_2C_D T P is presented in Algorithm 1. One can observe in the pseudo-code of H e u_2C_D T P that the running time of H e u_2C_D T P is mainly dominated by finding shortest paths between all pairs of vertices in G.

Figure 2 illustrates how H e u_2C_D T P works. Figure 2a represents a connected, weighted and undirected graph G = (V,E,w), where |V | = 9 and |E| = 13. Figure 2b–i depict various stages of execution of H e u_2C_D T P. Initially, d T r e e and S are two empty sets. Each vertex in V is labeled unvisited shown in white color. A vertex with maximum degree is selected. In Fig. 2a, there exists more than one vertex with same maximum degree, i.e., < 2, 7 > in V ∖S. To handle this situation, a first tie-breaking rule (see Phase One) is applied. This rule selects vertex 2 as a dominating vertex shown in dark grey color, because the weight associated with vertex 2 is less than that of vertex 7. Vertex 2 is added to S; labeled visited; and shown in dark grey color. All vertices adjacent to vertex 2 are labeled visited and are shown in grey color. This is shown in Fig. 2b. Update the degree of each vertex in V ∖S. Hereafter, at each iteration, a vertex of maximum degree is selected from V ∖S. In the first iteration, there exists more than one vertex with same maximum degree, i.e., < 1, 7, 5, 8 > in V ∖S. To handle this, a first tie-breaking rule (see Phase Two) is applied. As per this rule, vertex 8 is selected as a dominating vertex shown in dark grey color due to having shortest distance from d T r e e. Edge (2, 8) is added to d T r e e, and vertex 8 is added to S. The label of vertex 8 is already visited. All unvisited vertices adjacent to vertex 8 are labeled visited and are shown in grey color. This is shown in Fig. 2c–d. Update the degree of each vertex in V ∖S. In the second iteration, there exists more than one vertex with the same maximum degree, i.e., < 1, 3, 5, 7 > in V ∖S. As per the first-tie breaking rule (see Phase Two), vertex 5 is selected as a dominating vertex shown in dark grey color due to having shortest distance from d T r e e. Edge (2, 5) is added to d T r e e, and vertex 5 is added to S. The label of vertex 5 is already visited. All unvisited vertices adjacent to vertex 5 are labeled visited and are shown in grey color. This is shown in Fig. 2e–f. Update the degree of each vertex in V ∖S. In the final iteration, there exists more than one vertex with the same maximum degree, i.e., < 7, 1 > in V ∖S. As per the first-tie breaking rule (see Phase Two), vertex 7 is selected as a dominating vertex shown in dark grey color due to having shortest distance from d T r e e. Edges (7, 6) and (6, 5) are added to d T r e e, and vertices 7 and 6 are added to S. This is shown in Fig. 2g–h. At this stage all the vertices of d T r e e are visited, so H e u_2C_D T P stops here. Further, Prim’s algorithm [10] is applied on the subgraph of G induced by the set of dominating vertices (nodes), i.e., < 2, 5, 6, 7, 8 > in S of resultant d T r e e (Fig. 2h) in order to construct a new dominating tree with optimal cost (minimum spanning tree). Resultant minimum spanning tree is same as d T r e e (Fig. 2h) obtained by H e u_2C_D T P. Pruning method is applied on resultant d T r e e shown in Fig. 2h. Only vertex 8 is the leaf node that can be pruned without violating the constraints of DTP. Vertex 8 is pruned and deleted from S. Pruned vertex 8 is now shown in grey color. Figure 2i shows the resultant d T r e e whose dominating nodes, i.e., < 2, 5, 6, 7 > are in S. H e u_2C_D T P returns this resultant d T r e e as the final d T r e e.

Fig. 2
figure 2

The various stages in execution of H e u_2C_D T P

Full size image

4 Artificial bee colony algorithm

Artificial bee colony (ABC) algorithm is one among swarm intelligence techniques and inspired by foraging behavior of honey bees in nature [7]. ABC algorithm models the collective behavior of decentralized and self organized systems. Like real bees, ABC algorithm also categorizes artificial bees into three different groups: employed bees; scout bees; and onlooker bees in order to search high quality solutions for the optimization problem under consideration. A food source represents a feasible solution to the problem, and the nectar amount of its food source corresponds to the fitness of its solution. Since each food source is uniquely associated with an employed bee, the number of solutions is same as the number of employed bees. ABC algorithm starts with generating a fixed set of initial solution (food source). Then at each iteration, each group of artificial bee works as follows:

  • Employed bees: Each employed bee performs the job of determining a new solution in the neighborhood of its currently associated solution. If the new solution, in terms of fitness, is better than that of its currently associated solution, then the current employed bee will move to this new solution discarding the old one, otherwise it will continue with its old one.

  • Scout bees: If the solution is not improving for some time, controlled by a parameter called limit, then its associated employed bee becomes a scout bee by discarding its solution. The job of scout bee is to generate a new random solution. Once the new solution is generated, the status of scout bee changes to employed bee on this new solution.

  • Onlooker bees: Once each employed bee completes the job of determining a neighboring solution, the job of each onlooker bee starts. Each onlooker bee uses probability-based selection method to select a solution associated by an employed bee, and then it determines a new solution in the neighborhood of its selected solution that is similar to determining a new neighboring solution by an employed bee. This selection method biases towards selection of high quality solution. Once the job of each onlooker bee in terms of selecting a solution and determining a new neighboring solution is done, then all new solutions – determined in the neighborhood of a particular solution (say X) selected by one or more onlooker bees – and the solution itself X compete against each other for the position of solution X in the next iteration. The best in them will be chosen for the new position of solution X in the next iteration. Once new positions of all solutions are chosen, the next iteration of the ABC algorithm is carried out.

This whole iterative procedure is applied again and again until the termination criteria is met.

Readers can find a detail of ABC algorithm and its applications in [8].

4.1 ABC algorithm for the DTP

This subsection presents an ABC algorithm (ABC_DTP) for the DTP. Hereafter, the proposed ABC algorithm for the DTP will be referred to as ABC_DTP. The description of each component of ABC_DTP is as follows:

4.1.1 Initial solution generation

Instead of generating each initial solution of the population randomly as used in [15], ABC_DTP follows a random version of the proposed heuristic H e u_2C_D T P for generating each initial solution of the population. This random version also contains two phases which are as follows:

  • Phase One: In the beginning, label each vertex unvisited; calculate degree of each vertex similar to degree computed in H e u_2C_D T P. Initially, the dominating tree (d T r e e) and the set, say S, containing dominating nodes of d T r e e are empty. Each vertex in V whose degree is greater than zero is kept in a set, say D. Hereafter, select a vertex, say first vertex or v s randomly from D. The selected v s becomes a dominating node of the partial d T r e e and is added to S. All unvisited vertices that are adjacent to v s are labeled visited along with v s . Update the degree of each vertex in V ∖S. Now D will contain only those vertices in V ∖S whose degree is greater than zero.

  • Phase Two: At each step, select a vertex (say u) randomly from D. Note that u may be visited or unvisited vertex. To establish a connection between u and a vertex, say v, in S, a shortest path, say SP, is determined. Each vertex except v in SP becomes a dominating node and is added to S. Each edge in SP becomes a part of partial d T r e e. Each unvisited vertex in SP as well as its unvisited adjacent vert(ex/ices) are labeled visited. Hereafter, update the degree of each vertex in V ∖S. Now D will contain only those vertices in V ∖S whose degree is greater than zero. Note that if there exists more than one shortest path of same cost, then select a path that consists of maximum number of vertices. This iterative process continues until all vertices of G are labeled visited.

Once d T r e e is constructed, pruning procedure [15] is applied repeatedly until no leaf node in d T r e e can be pruned. After that, a minimum spanning tree (MST) is constructed on the sub-graph of G induced by the set (S) of dominating vertices of d T r e e with the help of Prim’s algorithm. The concept of pruning-MST applied here is similar to [15].

We have also tested with generating each initial solution of the population randomly; however, our initial experiments have suggested that this way led to inferior solution quality in comparison to generating each initial solution of the population with the help of a mixed strategy that uses randomness and problem-structure knowledge.

Each employee bee uniquely associates with each initial solution (d T r e e). The fitness of each solution is computed.

4.1.2 Probability of selecting a solution

In onlooker phase, each onlooker bee selects a solution (food source), which is one among all solutions associated by all employed bees, with the help of binary tournament selection method. In this selection method, two solutions from all solutions associated with all employed bees are picked randomly. With probability P b t , a solution with better fitness is selected, otherwise worse one is selected.

4.1.3 Determination of a neighboring solution

Determining a new neighboring solution of high quality relies heavily on how problem structure of a combinatorial optimization problem is unravelled. In this direction, we propose two methods applied in a mutually exclusive way for determining a solution (say X c) in the neighborhood of current solution (X). First method is \(\mathcal {C}\) NAS-Method that is based on copy a set of dominating nodes from another solution of the population to current solution, whereas second method is \(\mathcal {M}\) EDI-Method that is based on performing random multiple edge-deletion-insertion on current solution. Initially, a copy (say X c) of X is created. With probability P n b r , \(\mathcal {C}\) NAS-Method is applied, otherwise \(\mathcal {M}\) EDI-Method is applied.

  1. 1.

    \(\mathcal {C}\) NAS-Method: Initially, a solution, say Y, (different from X) is picked from the population with the help of binary tournament selection method. Then, \(\mathcal {C}\) NAS-Method picks at most y_d n dominating nodes of Y different from dominating nodes of X and assigns them to a set, say S y . y_d n is equal to mdn% of total number of dominating nodes of Y. mdn is a parameter to be determined empirically. Hereafter, at each step, a vertex, say u, in the order is picked from S y . An edge connecting u and a vertex in current X c is searched, as soon as an edge connecting u and a vertex in current X c is found, it is immediately added to current d T r e e of X c. Vertex u is added to X c. This procedure is repeated again and again until all nodes in S y are added to X c.

    Note that if \(\mathcal {C}\) NAS-Method fails to pick a dominating node of Y different from dominating nodes of X, then it shows that X and Y are same, which in turn also shows that employed bee solutions are suffering from a lack of diversity. This situation is coined as collision [12, 14]. In such a situtation, \(\mathcal {M}\) EDI-Method is applied on X instead of abandoning this solution [16]. Abandoning this solution means employed bee associated with this solution abandons it to become scout so that the diversity in the population can be improved. However, initial experiments have suggested that this way led to inferior solution quality overall in comparison to applying \(\mathcal {M}\) EDI-Method which is perturbation strategy.

  2. 2.

    \(\mathcal {M}\) EDI Method: This method follows a certain number of edge-deletion-insertion procedure which is applied S e times, where S e is equal to edi% of total number of edges of X. edi is a parameter to be determined empirically. Initially, this method picks a certain number of edges, where degree of atleast one end vertex (i or j) of each picked edge (say e(i, j)) must be greater than one in G. All picked edges are assigned to a set, say S e . Note that S e includes only edges of X (not of X c), as X c becomes different from X after applying first successful edge-deletion-insertion procedure. Hereafter, at each step, this method picks an edge (say e(i, j)) randomly from S e and deletes it from X c, resulting a partition of X c into two disjoint sets, say C 1 and C 2. To connect C 1 and C 2, a second connectivity rule is applied. This rule searches a particular shortest path from all candidate shortest paths connecting C 1 and C 2. This particular shortest path does not contain those edges that are already part of current d T r e e of X c and that are not added from any previous edge-deletion-insertion procedure if it has occurred already for the current d T r e e of X c as edge-deletion-insertion procedure performs multiple times for a given solution. Once this particular shortest path is found, all new edges in this particular shortest path are inserted to connect C 1 and C 2 of X c. However, if such particular shortest path is not possible, then deleted edge (e(i, j)) is restored to X c.

    Note that if \(\mathcal {M}\) EDI-Method fails to perform a single edge-deletion-insertion procedure, then in case of employed bee phase, current solution X is replaced with a new initial solution and in case of onlooker bee phase, a very large fitness value is assigned to fitness of onlooker bee associated with X.

Once the neighboring solution X c is determined, a pruning procedure [15] is applied repeatedly on X c until no leaf node in d T r e e of X c except all new nodes added through either \(\mathcal {C}\) NAS-Method or \(\mathcal {M}\) EDI-Method can be pruned. After that, a minimum spanning tree (or dominating tree) is constructed on the sub-graph of G induced by the set (S) of dominating vertices of d T r e e with the help of Prim’s algorithm [10]. This new dominating tree (minimum spanning tree) replaces the resultant d T r e e of X c and becomes d T r e e of X c. Again, the process of pruning is applied repeatedly on resultant d T r e e of X c until no leaf node (including all new nodes added through either \(\mathcal {C}\) NAS-Method or \(\mathcal {M}\) EDI-Method) in d T r e e of X c can be pruned.

Note that determining a neighboring solution which is an important component of ABC_DTP is different from that of previous ABC algorithm for the DTP, i.e., O_A B C DT [15] except pruning-MST-pruning methods. O_A B C DT [15] also applies two methods that are based on single edge-deletion-insertion procedure randomly from the current solution and adding a non-dominating vertex randomly to the current solution in a mutually exclusive way. However, ABC_DTP uses \(\mathcal {C}\) NAS-Method and \(\mathcal {M}\) EDI-Method in a mutually exclusive way. CNAS-Method is based on this concept that if a node as a dominating node is present in a good solution then the same node will be present in many good solutions. \(\mathcal {M}\) EDI-Method based on multiple edge-deletion-insertion procedure leads to better exploration in the search space in comparison to single edge-deletion-insertion procedure [15]. Experimental results justify that these two methods for determining a neighboring solution coordinated with other components of ABC_DTP make ABC_DTP more effective and robust for searching high quality solutions.

figure d

4.1.4 Other features

A solution that is not improving in terms of fitness for some iterations (controlled by a parameter called limit) is abandoned by its employed bee. The employed bee becomes a scout. This scout favors in generating a new random solution. Once a new solution is generated (similar to initial solution generation (see Section 4.1.1)), the status of scout bee changes to employed bee on this new solution.

Algorithm 2 presents the pseudo-code of ABC_DTP. In this pseudo-code, binary tournament selection method is called by \(\mathcal {B}inary\_TSM(\mathcal {E} 1, \mathcal {E} 2, ..., \mathcal {E}_{\mathcal {N}\mathcal {E}})\) function which returns a selected solution; and the method for determining a solution in the neighborhood of a solution, say \(\mathcal {X}\), is called by \(\mathcal {D}\mathcal {N}bring\_{\mathcal {S}}ol(\mathcal {X})\) function which returns a neighboring solution, say \(\mathcal {X^{\prime }}\).

5 Computational results

Both proposed approaches – H e u_2C_D T P and ABC_DTP – were implemented in C and tested on three different benchmark instance sets for evaluation. All experiments were executed on a Linux based 1.6 GHz Core 2 Duo system with 1 GB RAM which is different from that of previous existing metaheuristic techniques for the DTP, such as O_A B C DT [15], ACO_DT [15], EA/G [2], SSGA [13], and VNS [3]. O_A B C DT, ACO_DT, EA/G and SSGA used Intel Core 2 Duo processor 3.0 GHz with 2 GB RAM under Fedora 12, whereas VNS used Intel Core I7-4702MQ 2.2 GHz with 4 GB RAM under Windows XP. In such circumstances, it is difficult to exactly compare the speed of these metaheuristic techniques with ABC_DTP; however, a rough comparison can always be made. One can observe SSGA in terms of computational time and solution quality (see Table 6) that overall SSGA is superior to O_A B C DT, ACO_DT, EA/G and VNS. This observation gives an idea for rough comparison, i.e., the number of solutions generated by ABC_DTP is approximately similar to that of SSGA [13] in order to test the effectiveness of ABC_DTP. Since SSGA [13] generates X_S o l solutions to find a high quality solution for each instance, where X_S o l is equal to the sum of size of initial population and |V |× 500. Therefore, ABC_DTP is also allowed to generate approximately Y_S o l solutions to find a high quality solution for each instance, where Y_S o l is equal to the sum of size of initial population and (|V |× 500)/(\(\mathcal {N}\mathcal {E}\) + \(\mathcal {N}\mathcal {O}\)). In addition, ABC_DTP, similar to all previous existing metaheuristic techniques for the DTP, was also executed 20 independent times on each instance in order to test its robustness. H e u_2C_D T P, similar to all previous existing problem-specific heuristics – such as Heu_DT1 [11], Heu_DT2 [21], H_DT [15] and M_DT [2] –, H e u_2C_D T P was also executed once.

All instance sets used for the DTP are available on http://dcis.uohyd.ac.in/~alokcs/dtp.zip. Each instance [11, 21] is considered as a disk graph G = (V,E), where disk of a node denotes the transmission range of that node. For every pair of nodes, there will be an edge iff two nodes connecting this edge will be in the common area of their corresponding disks. For each edge e u,v ∈ E, there exists a non-negative weight w(e u,v ) which is defined as \(C_{j} \times d^{2}_{u,v}\), where \(d^{2}_{u,v}\) is the Euclidean distance between u and v; and C j is a random constant whose value is set to 1. Since instances used in [11, 21] were not available, Sundar and Singh [15], similar to [11, 21], generated a set of instances with different size varying in total number of nodes. Nodes are randomly distributed over an area of 500m × 500m, and transmission range of each node is 100m. For each size, i.e., |V| = {50, 100, 200, 300, 400, 500}, three different instances were generated, resulting a total of 18 instances. Later, Chaurasia and Singh [2] generated two different instance sets exactly similar to instance set [15], but the transmission range of each node in two different instance sets is 125m and 150m, resulting in generation of additional 36 (18 + 18) different instances.

In the next three subsections, parameter settings for ABC_DTP, comparison of the results obtained by H e u_2C_D T P with that of existing problem-specific heuristics in the literature, and comparison of the results obtained by ABC_DTP with that of existing metaheuristic approach in the literature are reported respectively.

5.1 Parameter tuning for ABC_DTP

Being stochastic in nature, proper tuning of parameters for ABC_DTP become significant. For this, various possible values of each candidate parameter (reported in Table 1) were chosen based on preliminary experimentations and available literature. To investigate parameter sensitiveness, two different instances from each instance set were taken into account. Then, the performance of ABC_DTP on different combination due to possible values of different parameters were carefully tested on these instances. One can observe in Table 2, where column Parameter denotes various parameters (\(\mathcal {N}\mathcal {E}\), \(\mathcal {N}\mathcal {O}\), P b t , P n b r , mdn, edi, limit) used for ABC_DTP; val_para denotes possible values of each parameter; Best and Avg respectively denote the best value and the average value over 20 runs obtained on such instances from corresponding value of the parameter. This investigation led to the best combination of parameter settings, i.e., \(\mathcal {NE}=\) 50, \(\mathcal {NO}=\) 100, P b t = 0.85, P n b r = 0.7, mdn = 20, edi = 10, and limit = 50 that approximately produces high quality solutions (in terms of Best and Avg in Table 2) highlighted in bold on most of these instances taken into account. Note that this testing uses every time one possible value of a parameter, while keeping values of other remaining parameters fixed (see val_para in bold of each parameter).

Table 1 Potential values of each parameter for ABC_DTP
Full size table
Table 2 Influence of parameter setting on solution quality
Full size table

5.2 Comparison of H e u_2C_D T P with Heu_DT1, Heu_DT2, H_DT and M_DT

In this subsection, we present an overview of effectiveness of the proposed problem-specific heuristic, i.e., H e u_2C_D T P in comparison to other existing problem-specific heuristics [2, 11, 15, 21], which will be referred to as Heu_DT1 [11], Heu_DT2 [21], H_DT [15] and M_DT [2] respectively. Tables 3, 4 and 5 report the results of H e u_2C_D T P along with Heu_DT1, Heu_DT2, H_DT and M_DT on instances with transmission range 100m, 125m and 150m respectively. In Tables 3–5, column Instance denotes the name of each instance, and for each heuristic, column Value denote the value obtained on each instance. In addition, similar to [2, 11, 15, 21], column NDN that denotes the number of nodes in dominating tree obtained on each instance is added, as the total number of dominating nodes has a significant role in the performance of any routing protocols based on virtual backbone structure. In Table 3, results of Heu_DT1, Heu_DT2, H_DT are taken from [15], whereas results of M_DT are taken from [2]. In Tables 4 and 5, results of Heu_DT1, Heu_DT2, H_DT and M_DT on instances with transmission range 125m and 150m respectively are taken from [2]. For each instance, the best value Value among Heu_DT1, Heu_DT2, H_DT, M_DT and H e u_2C_D T P is highlighted in bold.

Table 3 Results of Heu_DT1 [11], Heu_DT2 [21], H_DT [15], M_DT [2] and H e u_2C_D T P on the instances with transmission range 100m
Full size table
Table 4 Results of Heu_DT1 [11], Heu_DT2 [21], H_DT [15], M_DT [2] and H e u_2C_D T P on the instances with transmission range 125m
Full size table
Table 5 Results of Heu_DT1 [11], Heu_DT2 [21], H_DT [15], M_DT [2] and H e u_2C_D T P on the instances with transmission range 150m
Full size table

Tables 3, 4 and 5 clearly show that H e u_2C_D T P outperforms all previous existing problem-specific heuristics, i.e., Heu_DT1, Heu_DT2, H_DT and M_DT in terms of solution quality. In terms of Value, H e u_2C_D T P is better on all 54 instances in comparison to Heu_DT1, Heu_DT2, H_DT and M_DT. In terms of NDN, H e u_2C_D T P is better on all 54 instances except on one instance, i.e., 300_3 in 150m range whose NDN value is similar to that of M_DT.

Execution times of H e u_2C_D T P, H_DT and M_DT are dominated by precomputing all pair shortest paths in G. It is mentioned in [15] that Heu_DT1 and Heu_DT2 are faster than H_DT. Hence H e u_2C_D T P is slower than Heu_DT1 and Heu_DT2. Since H e u_2C_D T P outperforms all Heu_DT1, Heu_DT2, H_DT and M_DT in terms of solution quality and the number of dominating vertices for each test instance, such performance can compensate its execution time.

5.3 Comparison of ABC_DTP with state-of-the-art metaheuristic techniques

This subsection presents an overview of effectiveness of ABC_DTP with state-of-the-art metaheuristic techniques such as O_A B C DT [15], ACO_DT [15], EA/G [2], SSGA [13] and VNS [3] for the DTP. Table 6 reports the results of ABC_DTP along with the results of O_A B C DT, ACO_DT, EA/G, SSGA and VNS on instances with the transmission range 100m. Results of O_A B C DT, ACO_DT, EA/G, SSGA and VNS reported in Table 6 are taken from their respective papers. Tables 7–8 report the results of ABC_DTP along with the results of O_A B C DT, ACO_DT and EA/G on instances with transmission range 125m and 150m respectively. Results of O_A B C DT, ACO_DT and EA/G reported in Tables 7 and 8 are taken from [2]. For each instance in Tables 6–8, column Instance denotes the name of instance; and for each metaheuristic technique, columns Best, Avg, SD, ANDN and TET respectively denote the best value, the average solution quality, standard deviation, the average number of dominating vertices, and the average total execution time obtained over 20 runs. For each instance, the best value Best and the best average solution quality Avg among O_A B C DT, ACO_DT, EA/G, SSGA, VNS and ABC_DTP are highlighted in bold.

Table 6 Results of O_A B C DT [15], ACO_DT [15], EA/G [2], SSGA [13], VNS [3] and ABC_DTP on the instances with transmission range 100m
Full size table
Table 7 Results of O_A B C DT [15], ACO_DT [15], EA/G [2] and ABC_DTP on the instances with transmission range 125m
Full size table
Table 8 Results of O_A B C DT [15], ACO_DT [15], EA/G [2] and ABC_DTP on the instances with transmission range 150m
Full size table

Table 6 that reports the results of O_A B C DT, ACO_DT, EA/G, SSGA, VNS and ABC_DTP on 18 instances with the transmission range 100m shows the effectiveness of ABC_DTP in comparison to all other approaches. Comparing with O_A B C DT, ABC_DTP, in terms of solution quality (Best), is better on 10 and equals on 8; ABC_DTP, in terms of average solution quality (Avg), is better on 11, equals on 2 and is worse on 5; ABC_DTP, in terms of average number of dominating nodes (ANDN), is better on 6, equals on 3 and is worse on 9. Comparing with ACO_DT, ABC_DTP, in terms of Best, is better on 11, equals on 2 and is worse on 5; ABC_DTP, in terms of Avg, is better on 11, equals on 2 and is worse on 5; ABC_DTP, in terms of ANDN, is better on 10, equals on 4 and is worse on 4. Comparing with EA/G, ABC_DTP, in terms of Best, is better on 8, equals on 8 and is worse on 2; ABC_DTP, in terms of Avg, is better on 10, equals on 2 and is worse on 6; ABC_DTP, in terms of ANDN, is better on 7, equals on 5 and is worse on 6. Comparing with SSGA, ABC_DTP, in terms of Best, is better on 6, equals on 8 and is worse on 4; ABC_DTP, in terms of Avg, is better on 10 and is worse on 8; ABC_DTP, in terms of ANDN, is better on 4, equals on 2 and is worse on 12. Comparing with VNS, ABC_DTP, in terms of Best, is better on 7, equals on 8 and is worse on 3; ABC_DTP, in terms of Avg, is better on 17 and is worse on 1; ABC_DTP, in terms of ANDN, is better on 9 and is worse on 9.

Table 7 that reports the results of O_A B C DT, ACO_DT, EA/G and ABC_DTP on 18 instances with the transmission range 125m shows the effectiveness of ABC_DTP in comparison to all other approaches. Comparing with O_A B C DT, ABC_DTP, in terms of solution quality (Best), is better on 10 and equals on 8; ABC_DTP, in terms of average solution quality (Avg), is better on 10, equals on 3 and is worse on 5; ABC_DTP, in terms of average number of dominating nodes (ANDN), is better on 6, equals on 4 and is worse on 8. Comparing with ACO_DT, ABC_DTP, in terms of Best, is better on 10, equals on 7 and is worse on 1; ABC_DTP, in terms of Avg, is better on 13, equals on 1 and is worse on 4; ABC_DTP, in terms of ANDN, is better on 8, equals on 1 and is worse on 9. Comparing with EA/G, ABC_DTP, in terms of Best, is better on 3, equals on 12 and is worse on 3; ABC_DTP, in terms of Avg, is better on 8, equals on 3 and is worse on 7; ABC_DTP, in terms of ANDN, is better on 3, equals on 6 and is worse on 9.

Table 8 that reports the results of O_A B C DT, ACO_DT, EA/G and ABC_DTP on 18 instances with the transmission range 150m shows the effectiveness of ABC_DTP in comparison to all other approaches. Comparing with O_A B C DT, ABC_DTP, in terms of solution quality (Best), is better on 8 and equals on 10; ABC_DTP, in terms of average solution quality (Avg), is better on 12, equals on 3 and is worse on 3; ABC_DTP, in terms of average number of dominating nodes (ANDN), is better on 6, equals on 5 and is worse on 7. Comparing with ACO_DT, ABC_DTP, in terms of Best, is better on 8 and equals on 10; ABC_DTP, in terms of Avg, is better on 12, equals on 3 and is worse on 3; ABC_DTP, in terms of ANDN, is better on 10, equals on 4 and is worse on 4. Comparing with EA/G, ABC_DTP, in terms of Best, equals on 16 and is worse on 2; ABC_DTP, in terms of Avg, is better on 10, equals on 4 and is worse on 4; ABC_DTP, in terms of ANDN, is better on 6, equals on 6 and is worse on 6.

5.4 Collective picture

This subsection presents a collective picture with respect to all problem-specific heuristics (Heu_DT1, Heu_DT2, H_DT, M_DT and H e u_2C_D T P) and all metaheuristic techniques (O_A B C DT, ACO_DT, EA/G, SSGA, VNS and ABC_DTP) for the DTP. Clearly, in terms of solution quality (Value and NDN), H e u_2C_D T P shows superiority over all other existing problem-specific heuristics (Heu_DT1, Heu_DT2, H_DT, and M_DT) on all 54 instances except on one instance, i.e., 300_3 in 150m range whose NDN value is similar to that of M_DT. One can observe the performance of H e u_2C_D T P in terms of Value and NDN in Figs. 3 and 4 respectively.

Fig. 3
figure 3

Comparison of Value obtained by various heuristics for different transmission ranges (a–c) for 100m range; (d–f) for 125m range; and (g–i) for 150m range

Full size image
Fig. 4
figure 4

Comparison of NDN obtained by various heuristics for different transmission ranges (a–c) for 100m range; (d–f) for 125m range; and (g–i) for 150m range

Full size image

As far as comparison with all metaheuristic techniques (O_A B C DT, ACO_DT, EA/G, SSGA, VNS and ABC_DTP), ABC_DTP performs better overall in terms of solution quality (Best and Avg). One can observe solution quality of ABC_DTP (Best and Avg) in Table 9. ABC_DTP finds new values (Best) for 6 instances (300_1, 400_2, 400_3 and 500_2 in 100m range, and 300_3 in 125m range). One can notice in Fig. 5 that in terms of Best, ABC_DTP is overall better than all existing metaheuristic techniques for the DTP. ABC_DTP has improved average solution quality (Avg) for 23 instances (7 instances in 100m range, 7 instances in 125m range and 9 instances in 150m range) out of 54 instances. In terms of average number of dominating nodes (ANDN), ABC_DTP is comparable with all existing metaheuristic techniques for the DTP. This can be observed in Fig. 6.

Table 9 Comparison of ABC_DTP with O_A B C DT, ACO_DT, EA/G, SSGA and VNS approaches
Full size table
Fig. 5
figure 5

Comparison of Value obtained by various metaheuristics for different transmission ranges (a–c) for 100m range; (d–f) for 125m range; and (g–i) for 150m range

Full size image
Fig. 6
figure 6

Comparison of ANDN obtained by various metaheuristics for different transmission ranges (a–c) for 100m range; (d–f) for 125m range; and (g–i) for 150m range

Full size image

In terms of computational time, ABC_DTP is many times faster than O_A B C DT, ACO_DT and VNS. Overall, ABC_DTP is faster than EA/G. ABC_DTP is slower than SSGA, but ABC_DTP provides better solution quality (Best and Avg).

It is to be noted that Tables 3, 4 and 5 report best known solution value (BKS) for each instance taken from all approaches for the DTP, i.e., problem-specific heuristics including H e u_2C_D T P and metaheuristic techniques including ABC_DTP. Tables 3, 4 and 5 also report the percentage relative deviation (PRD) of each instance for H e u_2C_D T P. The PRD is defined in (1),

$$ \left[PRD = \frac{Value^{Heu\_{2C}\_{DTP}} - BKS}{BKS}\times100\%\right] $$
(1)

In equation (1), \(Value^{Heu\_{2C}\_{DTP}}\) denotes the value (Value) of each instance obtained by H e u_2C_D T P. One can observe from Tables 3, 4 and 5 that the results of H e u_2C_D T P on all instances are nearer to BKS whose maximum PRD value is 27.31 for 300_3 in 150m and minimum PRD value is 0.00 for 50_1 in 125m. It shows that H e u_2C_D T P can be a good choice for obtaining a d T r e e (solution) to the DTP in a very short time.

6 Conclusions

In this paper, we have proposed a new and effective problem-specific heuristic for the DTP (H e u_2C_D T P) that produces much better results on a set of benchmark instances than existing problem-specific heuristics in the literature. H e u_2C_D T P is so effective that it can be a good choice for obtaining a d T r e e (solution) to the DTP in a very short time. In addition, we have also proposed an artificial bee colony algorithm for the DTP (ABC_DTP) which is different from the existing ABC algorithm for the DTP in the literature on its two main components: initial solution generation; and determining a neighboring solution. These two components coordinated with other components of ABC_DTP help in making ABC_DTP more effective and robust. ABC_DTP demonstrates the superiority over not only previous ABC algorithm for the DTP, but also other existing metaheuristic techniques in the literature.

In future, similar strategies used in ABC_DTP can also be applied to develop ABC algorithms for other \(\mathcal {NP}\)-Hard graph problems.