Open access peer-reviewed chapter

Efficient Frontier and Benchmarking Models for Energy Multicast in Wireless Network Coding

Written By

Adeyemi Abel Ajibesin

Submitted: December 16th, 2017 Reviewed: June 8th, 2018 Published: August 22nd, 2018

DOI: 10.5772/intechopen.79377

Chapter metrics overview

951 Chapter Downloads

View Full Metrics


This chapter introduces efficiency frontier and benchmarking concepts to evaluate the efficiency performance of wireless networks for multicast energy. These concepts are efficiency models based on the data envelopment analysis (DEA) technique. The DEA framework allows network administrators to evaluate the technical efficiency and determine how the inefficient wireless networks will attain a targeted efficiency frontier. In order to achieve efficiency frontier and benchmark by a wireless network, this chapter presents several models including the envelopment and the slack. The envelopment model evaluates the technical efficiency scores of each wireless network, while the slack model shows how the inefficient wireless network achieves efficiency frontier. The benchmark model evaluates the efficiency reference set and the lambda values of each network. The efficiency frontier algorithm has shown that many of the wireless networks sampled are inefficient. However, the algorithm has capability to help the inefficient wireless networks to achieve efficiency frontier and benchmark with their peers that are fully efficient.


  • efficiency frontier
  • network coding
  • modeling
  • wireless networks
  • multicast energy

1. Introduction

Technical efficiency evaluation and expectation are new kinds of thinking for many evaluators especially in the field of network coding [1, 2]. The current approach to coded packet evaluations is largely dependent on average measurement [3]. This type of approach is only good to demonstrate the impact of a program but inadequate to evaluate the technical efficiency and benchmark [4]. One of the major factors in the evaluation of efficiency is the limited resources and decisions on how to allocate such resources. This requires a special consideration in evaluation processes [5, 6].

In literature, the essence of minimum energy multicast is to optimize high-energy transmission over the network. This was achieved using the minimum energy multicast algorithm. However, the minimum energy multicast problem is NP-hard [7]. The alternative solutions using polynomial time-based heuristics approach were considered [810]. One of these solutions is the multicast incremental power algorithm. As an improvement to this technique, the minimum energy multicast problem in ad hoc wireless networks is solvable as a linear program, assuming network coding technique [11]. Compared with conventional routing solutions, network coding technique does not only promise a potentially lower multicast energy but also enables finding the optimal solution in polynomial time. Other energy efficiency algorithms presented in the literature for energy efficiency were all designed to achieve similar goals using the effective performance evaluation approach [1214].

In this chapter, a network coding algorithm is studied and its performance is investigated for the data evaluation analysis (DEA) technique. The DEA methodology is necessary because the coded packet is not a fully efficient technique for energy efficiency [15]. The DEA, which was used to study the relative efficiency and productivity of systems in economic and operational research (OR) disciplines, is a nonparametric method that relies on linear programming techniques for optimizing discrete units of observation called the decision-making units (DMUs) [16]. The DEA method is different from other because it adopts the frontier analysis approach to evaluate efficiency rather than averages and standard deviation [16]. Therefore, our system model is based on frontier analysis that consists of several models including envelopment and benchmarking. These models are considered for evaluating the technical efficiency of multicast energy and performing the benchmark in wireless network nodes without affecting the overall network performance.

The remainder of this chapter is presented in sections: Section 2 provides necessary background information on the minimum energy multicast and Section 3 presents the network coding performance that is based on average multicar energy. Section 4 and 5 discuss the efficiency frontier method and benchmarking model, respectively. In Section 6, efficiency frontier implementation and results analyzed are discussed while Section 7 concludes the chapter.


2. Background

This section begins with the discussion of energy-efficient multicast following the various multicasting techniques used to minimize the wireless multicast energy.

2.1. Energy-efficient multicast

Researchers have worked on energy-efficient networking for several years especially with the growth of the wireless networks such as wireless sensor networks, mesh networks, and ad hoc wireless networks. Many studies have explored the topic of energy efficiency of these networks [1719]. Some of the studies that were investigated in literature include routing, coding, cross-layer designs, MAC protocols, spectrum allocation, resource allocation, and scheduling. The scope of this chapter is to present the actual efficiency of multicast energy in wireless networks. So it discusses energy efficiency in the routing. An approach to energy efficiency is the exploration of the broadcast nature of the wireless links. Wireless links are either omnidirectional or directed over a large area to ensure that transmissions are received by more than one node. This feature has effects on multicast networks, and it is known as wireless multicast advantage (WMA) [20, 21]. In routing, the problem of performing energy-efficient multicast considering WMA is NP-complete [22]. Thus the problem of minimum energy broadcast and multicast is solved in wire-line cases by various minimum weight-spanning tree algorithms but the solutions are generally suboptimal [23]. However, alternative approach using the network coding method was employed [2427].

2.2. Minimum-energy multicast

The main optimization problem for energy efficiency broadcast and multicast routing in ad hoc wireless networks is to minimize the total transmission power assigned to all nodes [15]. This is widely recognized as one of the performance challenges in wireless networking. The minimum energy multicast problem in ad hoc wireless networks is solvable using several approaches. A popular approach is the minimum shortest path tree (MSPT) algorithm that has been applied to solve minimum energy network problems [22]. This algorithm builds minimum energy networks and measures the cost (energy) of an edge based on certain levels [23]. However, this problem is known to be NP-hard [7]. An alternative approach such as minimum spanning tree that is based on the greedy heuristic algorithm was proposed [9]. The method used can compute minimum energy in polynomial time, thereby reducing the cost (energy) on multicast tree twice than that of SMPT. However, the solutions provided by this approach are suboptimal. In order to improve the solutions, a large number of approximation algorithms were proposed for energy-efficient multicast in wireless networks including a unique method to improve the energy efficiency of multicast trees using pruned or greedy heuristics [21]. In the literature, the performances of three greedy heuristics algorithms, multicast incremental power (MIP) algorithm, multicast least-unicast-cost (MLU) algorithm, and multicast link-based MST (MLiMST) algorithm, were analyzed [22]. It has been shown that MIP algorithm has best performance for all network nodes that are considered. However, the MIP approach is also suboptimal. Thus, the network coding technique has been considered for improved performance [25].


3. Network coding performance

In this section, the performance of a network coded algorithm is investigated and the results serve as imputes for the frontier analysis. We consider a flow-based approach that addresses networks with costs such as energy using a linear programming technique [26]. The cost is a function of coding subgraph z. We represent the cost function with ξ . This approach assumes that all nodes in the network are capable of coding with a focus on the problem of minimizing network resource such as multicast energy. We represent this function with z which is the coding subgraph. We then consider a formulated multicast problem connection, which is a triplet S T R t t T , where S is the source of the connection, T is the set of network receivers, and R t is the set of rates at which the flow is being injected to the sinks. Furthermore, the multicast connections using the random linear network coding (RLNC) algorithm that has been proved in the literature to address such problems are considered. The optimization formulation for this problem is given as:

min ξ z

subject to

z Z
j K x iJj t z iJK b iJK , i J H , K J , t T , x t F t
min ξ z

subject to

z Z
j J x iJj t z iJ , i J H , t T , x t F t

where x iJj t represents the average rate of the packets that are injected on the hyper arc link and received by exactly the set of nodes J, which occurs with the average rate z iJ and that allocated to a particular connection. F t is the bounded polyhedron of points

x t satisfying the conservation of flow constraints. We consider a lossless network with multicast applications and made some assumptions [27]. For example, it is assumed that when nodes transmit, they reach all other nodes in certain regions, with cost increasing as the region expands. These assumptions have helped the problem to reduce in the case of linear separable cost and separable constraints. Therefore, a fixed cost such as energy can easily be evaluated while the constraints set for Z are dropped. Readers are referred to [28] for more details about this formation. A well-known RLNC algorithm, which is appropriate to deploy network coding in a real multicast network, is considered for the simulation of this optimization problem. The details and the pseudocode for the RLNC algorithm are presented in [29].

The authors have considered various network parameters which include the network sizes, the radius of connectivity, the dimension for the nodes, the source nodes, and the receiving nodes. Randomly generated nodes were simulated and the average energy of the multicast networks was evaluated using the RLNC algorithm. The effective performance of the network coding algorithm presented has shown the limitation of the algorithm and the evaluation approach in terms of efficiency performance [30]. It is important to understand that “effectiveness” is mainly concerned with achieving a set goal. For instance, network effectiveness is the ability of such a network to attain its predetermined goals. For instance, one of the goals of the RLNC algorithm is to minimize energy such that the results or outcome is better than the previous algorithms [31, 32]. This evaluation approach is concerned on the right way of minimizing multicast energy rather than how well the multicast energy is being minimized. Thus, efficiency is concerned with how well the multicast energy is minimized. This is achieved by quantitatively evaluating the ratio of output to input. With efficiency evaluation, the performance is based on the combination of both inputs and outputs rather than focusing on the outcome results (outputs) only. For example, in [33], the results presented based on average performance show that the performance of the RLNC algorithm in minimizing energy was degraded as the number of sinks increased but improved as the network size increased. This result has been shown to perform better than the existing algorithm when compared. However, it is an effective performance and cannot determine the efficiency of the algorithms.


4. Efficient frontier method

Data envelopment analysis (DEA) is a nonparametric method that relies on the linear programming technique for optimization using frontier analysis. It is used to measure the relative efficiency of peer decision-making units (DMUs) that have multiple inputs and outputs [34]. Unlike network coding evaluation method that is based on average performance evaluation, the frontier method is used to evaluate the technical efficiency of DMUs. Besides, the efficiency frontier technique is capable of improving the input resources as well augment the output results while the performance remained the same. In case of input resources, the multicast energy of a wireless network is considered to be minimized, while the number of sinks remained the same. Also, in the case of output augmentation, the number of sinks can be increased, while the multicast energy is kept constant. Furthermore, the efficiency frontier method evaluates the performance of a wireless network by comparing its efficiency with the best observed performance in the data set. Thus, efficiency frontier represents the best observed performance among the networks [35].

4.1. Illustrating efficient frontier

This concept of efficiency frontier is best explained with a simple case of one input and one output. Let us consider the data in Table 1 where the technical efficiency of each set of eight wireless networks (DMUs) is evaluated. A data value for each DMU is provided. We plot the data in Table 1 with input on the x axis (the horizontal axis) and the output on the y axis (the vertical axis) to obtain Figure 1. This figure shows the technical efficiency of each DMU. The figure also shows the picture of efficient frontier. The wireless network with efficiency frontier is the one that floats on top of data observations.

Output 4 6 6 8 10 10 12 16
Input 2 3 4 6 10 4 6 10

Table 1.

Data of simple efficiency ratio to evaluate efficient frontier.

Figure 1.

DMU on efficient frontier versus inefficient DMUs.

Figure 1 shows the wireless network E on the efficiency frontier with an efficiency of 1. The line that spans from the origin through the wireless network (DMU E) is known as efficiency frontier [36]. The inefficient wireless networks are located beneath the efficient frontier. These inefficient wireless networks can be moved unto the efficient frontier using an orientation approach [36]. There are two fundamental directions to achieve this move: The input-oriented and the output-oriented approaches. The input-oriented approach will be applied to reduce the multicast energy while the number of receives is fixed at their current levels. The output-oriented approach is outside the scope of this chapter. Using input orientation and considering the wireless network F, which is an example of inefficient network, a projection to point E can be performed. This is the targeted position for wireless network F to become efficient. In the real world, most problems are multidimensional in nature with many input and output variables. As a result, the efficiency frontier using DEA solver that is based on the linear programing technique is considered for the evaluation of efficiency frontier in this chapter.

4.2. Efficient frontier system model and procedure

A wireless network (DMU) that lies on the efficiency frontier is said to attain its targeted energy level. The main problem that this chapter addresses is that many networks multicast their messages using average energy rather than targeted energy. A wireless network administrator, especially at this stage of technological development, cannot base network evaluation on average performance. Therefore, one of the problems is that given the different set of wireless networks with a node (source) multicast to some selected group of nodes (receivers) using average energy, how can we qualitatively evaluate performance so that they attain targeted energy? This problem is impossible to answer without the efficiency frontier method. The existing approach was to calculate the average energy multicast and then rank them according to the lowest. The lowest average energy multicast is considered the most effective network. However, the lowest average energy multicast does not mean it is the most efficient [37]. We state that any wireless network that multicasts messages to a selected group of nodes using targeted or projected energy is said to attain efficiency frontier. Performance according to the efficiency frontier is possible if a network makes use of the combination of its multiple inputs and multiple output resources correctly.

Figure 2 presents the flowchart that is used to solve this problem. The flowchart consists of different steps. The first step, which is envelopment model, evaluates the technical efficiency scores of a wireless network. Subsequently, the second step, which is the slack model calculates and classifies the efficient wireless into full or weak networks. The last step is the projection model that determines how the weakly efficient wireless network will be fully efficient so that they also attain efficiency frontier. These procedures are computed using the DEA solver and the efficiency frontier results are compared with the average energy computed using the network coding algorithm. The differences in multicast energy are recorded. If there is no difference, it means that the average energy used by RLNC is fully efficient. Otherwise, it is inefficient or weakly efficient. However, as discussed, the efficiency frontier method provides mechanisms for making the inefficient wireless network to achieve efficiency. The models considered are based on Charnes, Cooper, and Rhodes (CCR) with assumption of constant returns to scale (CRS) [38].

Figure 2.

Algorithm of the targeted multicast energy based on efficiency frontier approach.

4.3. The envelopment model

This chapter considers the minimization of multicast energy using efficiency frontier method that relies on the linear programing (LP) technique of the DEA. The LP is an approach to evaluate a set of weights that yields the maximum efficiency. An appropriate envelopment DEA model that evaluates energy efficiency was presented in [39] and is given below:

θ = min θ

subject to

j = 1 n λ j x ij θ x i 0 , i = 1 , 2 , , m ; j = 1 n λ j y rj y r 0 , r = 1 , 2 , , s ; λ j 0 , j = 1 , 2 , , n , E1

where λ j are unknown weights with j = 1 , 2 , , n and they correspond to the DMU numbers. DMU0 is one of the n DMUs under evaluation, and θ x i 0 and y r 0 are the ith input and rth output for DMU0, respectively.

The following conditions are required for the calculation of efficiency scores: If θ = 1 , then the DMU under evaluation is a frontier point (fully or weakly efficient). Otherwise if θ < 1 , then the DMU under evaluation is inefficient. To address inefficiency, the DMU can either increase its output levels or decrease its input levels to achieve efficiency [40]. The θ represents the efficiency score of DMU o based on input-orientation. This means that the model is able to minimize energy while maintaining the current output levels.

4.4. The slack model

The slack model is needed to push the weak efficient or inefficient wireless networks to their real efficiency frontier so that targeted energy is achieved. The linear programming formulated for slack model is given as [40, 41]:

max i = 1 m s j + r = 1 s s r +

subject to

j = 1 n λ j x ij + s j = θ x io , i = 1 , 2 , , m ; j = 1 n λ j y rj s r + = y r 0 , r = 1 , 2 , , s ; j 0 j = 1 , 2 , , n E2

where s j and s r + represent input and output slacks, respectively. The superscripts (−) and (+) represent input reduction and output augmentation, respectively. The condition for fully (100%) efficient is if and only if both (a) θ = 1 and (b) all slacks s i = s r + = 0 . The targeted multicast energy can be calculated using the following expressions:

X i 0 = θ x io S i , i = 1 , 2 , , m Y r 0 = y ro + S r + , r = 1 , 2 , , s E3

This is calculated by multiplying the average multicast energy with an optimal efficiency score ( θ ), and slack amounts are subtracted.


5. Benchmarking model

In this section, a variable-benchmark model is considered for minimum energy multicast. The variable benchmark allows a new wireless network to be evaluated against a set of given benchmarks or standards. Also, it is formulated upon input-oriented CCR/CRS model. The model extends the envelopment and slack models discussed in the previous section. The benchmark model determined the efficiency reference set (ERS) and the amount required by each wireless network to catch up with their peers. The remainder of this section presents the mathematical function and the requirements for benchmark evaluation.

In the process of developing a benchmark, once the efficiency frontier is established, we can compare a set of new wireless networks with the reference efficiency frontier. The idea is that whenever a new wireless network outperforms the identified efficiency frontier, a new efficiency frontier is generated by the DEA solver. This means that the benchmark for a wireless network is different from other new wireless networks depending on network condition and variables used. The benchmark model contributes to how a wireless network learns the best way to utilize the available resources [42]. The benchmark model first evaluates the efficiency reference set (ERS) and the amount required by each wireless network to catch up with their peers. This magnitude is called the lambdas.

In order to formulate variable benchmark, the envelopment model is modified for the benchmark optimization problem as follows:

Minimise α CCR / CRS

subject to

j E λ j x ij α CCR / CRS x i new j E λ j y rj y r new λ j 0 , j E , E4

where α CCR / CRS represents the optimal value to model, and Ε represents the set of benchmarks identified by the DEA. The new observation is represented by DMUnew with inputs x i new i = 1 2 m and outputs y r new r = 1 2 s . The superscript of CCR/CRS indicates that the benchmark composed by benchmark DMUs in set E is based on CCR/CRS model. Model represents the performance of DMUnew with respect to benchmark DMUs in set E , when outputs are fixed at their current levels. Furthermore, model is capable of yielding a benchmark for DMUnew. Thus the ith input and the rth output for the benchmark can be expressed as:

j E λ j x ij ith input j E λ j y rj rth ouput E5

The expression (5) indicates that although the DMUs associated with set E are given, the resulting benchmark may be different for each new DMU under evaluation. Thus, there is a variable-benchmark scenario.


6. Implementation, results, and discussions

This section begins with brief overview of the software used for the implementation of the algorithm presented in Section 4 and 5. It then discusses and analyses the results obtained from the models.

6.1. DEA solver for efficient frontier analysis

The frontier analysis is evaluated using the DEA software, which is the tool that was specially packaged to solve the envelopment model and other types of DEA models. The efficiency frontier analysis relies on the DEA library, which includes the Solver and LPsolver (linear programming solver) program to perform optimizations. This work makes use of DEAOS for the implementation of the efficiency frontier models. The DEAOS is a web-based software. The readers are referred to [43] for details about the DEAOS package and user’s documentation. The DEA implementation procedures were discussed in [40].

6.2. Technical efficiency performance

The DEA solver compares each DMU with all other DMUs and identifies those DMUs that are operating inefficiently. It also evaluates the magnitude of inefficiency of the DMUs that are suboptimal. The efficient DMUs are those that attain efficient frontier and are identified by a DEA efficiency rating of θ = 1. The inefficient DMUs are identified by the efficiency score of less than 1 (θ < 1). Column 1 of Table 2 is the results of the average multicast energy computed by the RLNC reports. This result was presented in [43]. Column 2 of Tables 2 and 3 report the results of DEA technical efficiency and inefficiency scores of 54 wireless networks, respectively. From Table 2, only DMU9, DMU18, DMU27, and DMU45 have the efficiency score of θ = 1 (i.e., 100%) and thus they are identified as efficient. Other DMUs have efficiency scores of less than 1 (θ < 1) but greater than 0 and are identified as inefficient. It is possible for inefficient DMUs to improve their technical efficiency scores by reducing certain inputs using input orientation. For example, DMU1 can improve its technical efficiency score by reducing certain inputs up to 73.4% (100–26.6). Similarly, DMU2 can do so with approximately 63.1% of input reduction. However, DMU36 is closer to an efficiency frontier and needs only a 2.4% reduction of its input resources. This is achieved using the slack model.

DMU Ave. energy (RLNC) Efficiency score (%) Inefficiency score (%) Targeted energy
DMU1 4.5 30 70 1.3
DMU2 5.5 40.1 59.9 2.2
DMU3 6.2 49.2 50.8 3.1
DMU4 6.8 58 42 4
DMU5 7.3 66.3 33.7 4.9
DMU6 7.2 78 22 5.6
DMU7 8.1 82.4 17.6 6.7
DMU8 8.8 90 10 7.6
DMU9 8.5 100 0 8.5
DMU10 5.2 27.5 72.5 1.4
DMU11 5.6 39.5 60.5 2.2
DMU12 6.3 48.7 51.3 3.1
DMU13 6.9 57.3 42.7 3.9
DMU14 7.1 67.1 32.9 4.8
DMU15 7.2 77.8 22.2 5.6
DMU16 7.7 84.4 15.6 6.5
DMU17 8.6 90 10 7.5
DMU18 8.3 100 0 8.3
DMU19 4.2 30.3 69.7 1.3
DMU20 5.3 36.5 63.5 1.9
DMU21 5.4 48.3 51.7 2.6
DMU22 6.1 54.5 45.5 3.3
DMU23 6.2 64.5 35.5 4
DMU24 6.4 73.4 26.6 4.7
DMU25 6.6 81.8 18.2 5.4
DMU26 7.3 90 10 6.1
DMU27 6.7 100 0 6.7
DMU28 3.6 34.9 65.1 1.3
DMU29 5.1 37.7 62.3 1.9
DMU30 5.6 46.8 53.2 2.6
DMU31 5.9 56.1 43.9 3.3
DMU32 6.1 65.3 34.7 4
DMU33 6.8 69.9 30.1 4.7
DMU34 6.6 81.2 18.8 5.4
DMU35 7.1 87 13 6.2
DMU36 7.1 96.8 3.2 6.9
DMU37 3.1 40.1 59.9 1.3
DMU38 4.6 41 59 1.9
DMU39 4.8 53 47 2.5
DMU40 4.8 66.2 33.8 3.2
DMU41 5.6 68 32 3.8
DMU42 5.6 79 21 4.4
DMU43 6.3 80.6 19.4 5
DMU44 6.3 90.1 9.9 5.7
DMU45 6.3 100 0 6.3
DMU46 3.6 34.8 65.2 1.3
DMU47 4.3 43.8 56.2 1.9
DMU48 5.1 49.7 50.3 2.5
DMU49 5.1 61.5 38.5 3.2
DMU50 5.5 69.3 30.7 3.8
DMU51 5.7 76.8 23.2 4.4
DMU52 6.4 78.7 21.3 5.1
DMU53 6.4 88.6 11.4 5.7
DMU54 6.5 97.6 2.4 6.3

Table 2.

Results of the average multicast energy computed by network coding (RLNC) algorithm, the envelopment model, (efficiency and inefficiency), and the projected multicast energy computed by DEA Solver.

DMUs Efficiency reference set (ERS) Lambdas values (%)
DMU1 DMU18, DMU27 0.020 19.98
DMU2 DMU9, DMU18, DMU27 7.310 2.520 20.17
DMU3 DMU9, DMU18, DMU27 19.28 2.300 18.41
DMU4 DMU9, DMU18, DMU27 32.03 2.000 15.98
DMU5 DMU9, DMU18, DMU27 45.89 1.570 12.54
DMU6 DMU9, DMU18, DMU27 51.99 2.000 16.00
DMU7 DMU9, DMU18, DMU27 74.54 0.610 4.850
DMU8 DMU9 90.00
DMU9 DMU9 100.0
DMU10 DMU18, DMU27 5.000 15.00
DMU11 DMU18, DMU27 10.91 19.09
DMU12 DMU18, DMU27 22.69 17.31
DMU13 DMU18, DMU27 35.30 14.70
DMU14 DMU18, DMU27 45.86 14.14
DMU15 DMU18, DMU27 54.47 15.53
DMU16 DMU18, DMU27 71.28 8.720
DMU17 DMU9 90.00
DMU18 DMU18 100.0
DMU19 DMU45 20.00
DMU20 DMU27, DMU45 10.44 19.56
DMU21 DMU27, DMU45 15.14 24.86
DMU22 DMU27, DMU45 36.41 13.59
DMU23 DMU27, DMU45 46.63 13.37
DMU24 DMU27, DMU45 59.82 10.18
DMU25 DMU27, DMU45 74.70 5.300
DMU26 DMU27, DMU45 31.69 58.31
DMU27 DMU27 100.0
DMU28 DMU45 20.00
DMU29 DMU27, DMU45 6.970 23.03
DMU30 DMU27, DMU45 19.50 20.50
DMU31 DMU27, DMU45 31.77 18.23
DMU32 DMU27, DMU45 44.20 15.80
DMU33 DMU18, DMU27 0.360 69.64
DMU34 DMU27, DMU45 76.40 3.600
DMU35 DMU18, DMU27 8.970 81.03
DMU36 DMU18, DMU27 9.610 90.39
DMU37 DMU45 20.00
DMU38 DMU45 30.00
DMU39 DMU45 40.00
DMU40 DMU45 50.00
DMU41 DMU45 60.00
DMU42 DMU45 70.00
DMU43 DMU45 80.00
DMU44 DMU45 90.00
DMU45 DMU45 100.00
DMU46 DMU45 20.00
DMU47 DMU45 30.00
DMU48 DMU45 40.00
DMU49 DMU45 50.00
DMU50 DMU45 60.00
DMU51 DMU45 70.00
DMU52 DMU27, DMU45 5.290 74.71
DMU53 DMU27, DMU45 5.630 84.37
DMU54 DMU27, DMU45 9.660 90.34

Table 3.

ERS and lambdas of input-oriented variable benchmark.

6.3. Evaluation of slacks and targeted multicast energy

Column 4 of Table 2 presents the targeted results using slack and projection. In the slack model, none of the efficient DMUs have a slack, meaning that slacks exist only for those DMUs identified as inefficient. The slacks are obtained after proportional reductions in inputs. The slack is essential whenever a wireless network cannot reach the targeted multicast energy. Then, slacks are required to project such wireless networks to the targeted multicast energy which is their efficient frontier. The general rule is that a DMU with at least a slack input value is needed to be projected into the frontier, but a DMU that has zero slack for all the inputs does not need any projection because it already reached targeted efficient frontier. The targeted multicast energy is calculated by multiplying the average multicast energy with the technical efficiency score, and the slack values are subtracted. This calculation is used to achieve the target set for multicast energy.

6.4. Benchmarking for ERS and lambdas evaluation

The benchmark model addresses the benchmark problem. It is a model for establishing the standard of excellence. The model is able to determine the efficiency reference set (ERS) and lambdas of the inefficient wireless networks. Lambdas define the amount of inputs to be reduced for an inefficient wireless network to catch up with their peers that are already operating efficiently. We consider the same data set used for envelopment and slack model. The implementation procedures for benchmarking are also similar. The same DEA solver is used for the benchmark model. The benchmark model is able to identify the ERS and calculate the lambda values.

Table 3 is extracted from the DEA simulation output sheet. The network administrators whose network is inefficient can observe the benchmark networks that they need to catch up with. From Table 3, the full efficient network may consider itself to be its own “benchmarks.” This is because efficient network has already achieved 100% efficiency. So, benchmark for DMU9 is DMU9 and for DMU18 is DMU18. The same applies to DMU27 and DMU45. However, for inefficient ad hoc networks, their benchmarks are one or many of the efficient ad hoc networks. For example, a benchmark for DMU2 and DMU3 are DMU9, DMU18 and DMU27. This means, DMU2 and DMU3 must use a combination from DMU9, DMU18 and DMU27 to become efficient.

Another benchmark analysis is the lambda value. This benchmark analysis calculates the amounts of benchmark needed from a DMU to achieve efficiency. These values are reported as magnitude (lambda) next to each benchmark DMU on Table 3. For instance, as seen from Table 3 and as shown in Figure 3, DMU16 will attempt to become like DMU18 (blue bar) more than DMU27 (red bar) as observed from their respective lambda weights of DMU18 and DMU27 (λ18 = 71.3 and λ27 = 8.7).

Figure 3.

Benchmarks and lambdas of the input-oriented variable benchmark.


7. Conclusion

This chapter studied the existing network coding algorithm and investigated the efficiency performance of the multicast energy in wireless networks. The previous reports have shown that network coding based on effective evaluation is sub-optimal because they were largely calculated using central tendency performance such as average and standard deviation. While effective performance is a good evaluation tool, it is not enough to measure the actual efficiency of networks. In order to appropriately evaluate the network efficiency, a new algorithm based on efficiency frontier was considered for the evaluation. With this approach, the targeted multicast energy for wireless networks is achieved using envelopment, slack, and benchmarking models. These models were formulated upon input-oriented CCR/CRS assumptions. The aim of this chapter was to achieve economic efficiency by ensuring that wireless networks are multicast at the targeted energy rather than average energy. Furthermore, this was achieved without sacrificing the network performance.


  1. 1. Hassan Mohammed A, Dai B, Huang B, Azhar M, Xu G, Qin P, Yu S. A survey and tutorial of wireless relay network protocols based on network coding. Journal of Network and Computer Applications. Mar. 2013;36(2):593-610
  2. 2. Minn J, Zeng H, Vijay K. Green cellular networks: A survey, some research issues and challenges. IEEE Communication Surveys and Tutorials. 2012;13(4):524-540
  3. 3. Lilien LT, Othmane LB, Pelin A, DeCarlo A, Salih RM, Bhargava B. A simulation study of ad hoc networking of UAVs with opportunistic resource utilization networks. Journal of Network and Computer Applications. Feb. 2014;38:3-15
  4. 4. Begum IA, Buysse J, Alam MJ, Van Huylenbroeck G. Technical, allocative and economic efficiency of commercial poultry farms in Bangladesh. World’s Poultry Science Journal. Aug. 2010;66(03):465-476
  5. 5. Raayatpanah MA, Salehi Fathabadi H, Khalaj BH, Khodayifar S, Pardalos PM. Bounds on end-to-end statistical delay and jitter in multiple multicast coded packet networks. Journal of Network and Computer Applications. May 2014;41:217-227
  6. 6. Katrina P. Understanding Cost-Effectiveness of Energy Efficiency Programs: Best Practices, Technical Methods, and Emerging Issues for Policy-Makers. A Resource of the National Action Plan for Energy Efficiency; 2008
  7. 7. Cagalj M, Hubaux JP, Enz C. Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues. In: ACM MobiCom; 2002. pp. 172-182
  8. 8. Guo S, Yang O. Minimum-energy multicast in wireless ad hoc networks with adaptive antennas: MILP formulations and heuristic algorithms. IEEE Transactions on Mobile Computing. 2006;5(5):333-346
  9. 9. Yuan D, Bauer J, Haugland D. Minimum-energy broadcast and multicast in wireless networks: An integer programming approach and improved heuristic algorithms. Ad Hoc Networks. Jul. 2008;6(5):696-717
  10. 10. Wieselthier EJ, Nguyen GD, Anthony E. Algorithms for energy-efficient multicasting in static ad hoc wireless networks. Mobile Networks and Applications. 2001;6(3):251-263
  11. 11. Ho T, Lun DS. Network Coding: An Introduction. Cambridge, UK: Cambridge University Press; 2008
  12. 12. Ajibesin AA, Ventura N, Murgu A, Chan HA. Energy minimization in WSNs: Empirical study of multicast incremental power algorithm. In: South Africa Telecommunication Networks and Applications Conference (SATNAC); Port Elizabeth, South Africa; 31 August–3 September, 2014
  13. 13. Mueen U, Azizah AR. Virtualization implementation model for cost effective and efficient data centers. International Journal of Advanced Computer Science and Applications. 2011;2(1):59-68
  14. 14. Wen Y-F, Liao W. Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach. Wireless Networks. Jun. 2011;17(6):1401-1421
  15. 15. Ajibesin AA, Ventura N, Murgu A, Chan H. Data envelopment analysis: Efficient technique for measuring performance of wireless network coding protocols. In: 15th International Conference on Advanced Communication Technology; 2013. pp. 1122-1127
  16. 16. Cooper WW, Lawrence MS, Kaoru T. Data Envelopment Analysis: A Comprehensive Text with Models, Applications, References and DEA-Solver Software. New York, USA: Springer Science + Business Media; 2007
  17. 17. Blume O, Zeller D, Barth U. Approaches to energy efficient wireless access networks. In: 4th International Symposium on Communications, Control, and Signal Processing; 2010
  18. 18. Lin R, Wang Z, Sun Y. Energy efficient medium access control protocols for wireless sensor networks and its state-of-art. In: 2004 IEEE International Symposium on Industrial Electronics. Vol. 1; 2004
  19. 19. Louhi J. Energy efficiency of modern cellular base stations. In: 29th International Telecommunications Energy Conference (INTELEC); 2007. pp. 475-476
  20. 20. Etoh M, Ohya T, Nakayama Y. Energy consumption issues on mobile network systems. In: International Symposium on Applications and the Internet (SAINT 2008); 2008
  21. 21. Zhang H, Gladisch A, Pickavet M, Tao Z, Mohr W. Energy efficiency in communications. IEEE Communications Magazine. 2010;48(11):48-49
  22. 22. Akbari Torkestani J, Meybodi MR. A link stability-based multicast routing protocol for wireless mobile ad hoc networks. Journal of Network and Computer Applications. Jul. 2011;34(4):1429-1440
  23. 23. Lun DS, Ratnakar N, Medard M, Koetter R, Karger DR, Ho T, Ahmed E. Minimum-cost multicast over coded packet networks. IEEE Transactions on Information Theory. Jun. 2006;52(6):2608-2623
  24. 24. Wieselthier JE, Nguyen GD, Ephremides A. Energy-efficient broadcast and multicast trees in wireless networks. Mobile Networks and Applications. 2002;7(6):481-492
  25. 25. Biradar R, Manvi C, Sunilkumar S. Review of multicast routing mechanisms in mobile ad hoc networks. Journal of Network and Computer Applications. Jan. 2012;35(1):221-239
  26. 26. Wu M, Kim C. A cost matrix agent for shortest path routing in ad hoc networks. Journal of Network and Computer Applications. Nov. 2010;33(6):646-652
  27. 27. Liang W. Approximate minimum-energy multicasting in wireless ad hoc networks. IEEE Transactions on Mobile Computing. 2006;5(4):377-387
  28. 28. Eslami A, Khalaj BH. Capacity of network coding for wireless multicasting. In: IEEE Annual Wireless and Microwave Technology Conference; 2006. pp. 1-5
  29. 29. Ho T, Medard M, Koetter R, Karger DR, Effros M, Shi J, Leong B. A random linear network coding approach to multicast. IEEE Transactions on Information Theory. Oct. 2006;52(10):4413-4430
  30. 30. Ajibesin AA, Wajiga GM, Odekunle MR, Egunsola OK. Energy-efficient for multicast networks: A new approach to efficiency measure. In: 8th IEEE EUROSIM Congress on Modelling and Simulation (EUROSIM2013); Cardiff, Wales, United Kingdom; September 9–12, 2013. pp. 616-621
  31. 31. Fragouli C, Soljanin E. Network coding applications. Foundation and Trends in Networking. 2007;2(2):135-269
  32. 32. Li Z, Li B. Network coding in undirected networks. Computer (Long Beach, California). 2004:1-6
  33. 33. Ajibesin AA, Ventura N, Chan HA, Murgu A, Egunsola OK. Performance of multicast algorithms over coded packet wireless networks. In: 2012 UKSim–14th International Conference on Modelling and Simulation; Cambridge: Cambridgeshire United Kingdom; March 28–30, 2012
  34. 34. Cooper WW, Lawrence MS, Joe Z. Handbook on Data Envelopment Analysis. 2nd ed. New York, USA: Springer Science + Business Media; 2011
  35. 35. Kastaniotis G, Maragos E, Douligeris C, Despotis DK. Using data envelopment analysis to evaluate the efficiency of web caching object replacement strategies. Journal of Network and Computer Applications. Mar. 2012;35(2):803-817
  36. 36. Coelli TJ, Rao DS, O’Donnell CJ, Battese GE. An Introduction to Efficiency and Productivity Analysis. 2nd ed. New York, USA: Springer Science + Business Media; 2005
  37. 37. Katrina P. The Measurement of Productive Efficiency and Productivity Growth (Google eBook). Oxford University Press; 2008
  38. 38. Banker WW, Charnes RD, Cooper A, et al. Management Science. 1984;30(9):1078-1092
  39. 39. Cullinane K, Song D-W, Wang T. The application of mathematical programming approaches to estimating container port production efficiency. Journal of Productivity Analysis. Sept. 2005;24(1):73-92
  40. 40. Ajibesin AA, Ventura N, Chan A, Murgu A. DEA envelopment with slacks model for energy efficient multicast over coded packet wireless networks. IET Journal of Science, Measurement and Technology. 2014;8(6):408-419
  41. 41. Tone K. A slacks-based measure of efficiency in data envelopment analysis. European Journal of Operational Research. 2001;130(3):498-509
  42. 42. Joe Z. Qualitative Models for Performance Evaluation and Benchmarking: Data Envelopment Analysis with Spread Sheets. New York, USA: Springer Science + Business Media LLC; 2009
  43. 43. Data Envelopment Analysis. 2015. [Online]. Available from: [Accessed: May 30, 2018]

Written By

Adeyemi Abel Ajibesin

Submitted: December 16th, 2017 Reviewed: June 8th, 2018 Published: August 22nd, 2018