Open access peer-reviewed chapter

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

By Adeyemi Abel Ajibesin

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

DOI: 10.5772/intechopen.79377

Downloaded: 643


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 zwhich is the coding subgraph. We then consider a formulated multicast problem connection, which is a triplet STRttT, where Sis the source of the connection, Tis the set of network receivers, and Rtis 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:


subject to


subject to


where xiJjtrepresents 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 ziJand that allocated to a particular connection. Ftis the bounded polyhedron of points

xtsatisfying 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.


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:


subject to


where λjare unknown weights with j=1,2,,nand they correspond to the DMUnumbers. DMU0 is one of the n DMUs under evaluation, and θxi0and yr0are 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 DMUobased 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]:


subject to


where sjandsr+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 si=sr+=0. The targeted multicast energy can be calculated using the following expressions:


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:


subject to


where αCCR/CRSrepresents the optimal value to model, and Εrepresents the set of benchmarks identified by the DEA. The new observation is represented by DMUnew with inputs xinewi=12mand outputs yrnewr=12s. The superscript of CCR/CRS indicates that the benchmark composed by benchmark DMUs in set Eis 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 ithinput and the rthoutput for the benchmark can be expressed as:


The expression (5) indicates that although the DMUs associated with set Eare 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.

DMUAve. energy (RLNC)Efficiency score (%)Inefficiency score (%)Targeted energy

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.

DMUsEfficiency reference set (ERS)Lambdas values (%)
DMU1DMU18, DMU270.02019.98
DMU2DMU9, DMU18, DMU277.3102.52020.17
DMU3DMU9, DMU18, DMU2719.282.30018.41
DMU4DMU9, DMU18, DMU2732.032.00015.98
DMU5DMU9, DMU18, DMU2745.891.57012.54
DMU6DMU9, DMU18, DMU2751.992.00016.00
DMU7DMU9, DMU18, DMU2774.540.6104.850
DMU10DMU18, DMU275.00015.00
DMU11DMU18, DMU2710.9119.09
DMU12DMU18, DMU2722.6917.31
DMU13DMU18, DMU2735.3014.70
DMU14DMU18, DMU2745.8614.14
DMU15DMU18, DMU2754.4715.53
DMU16DMU18, DMU2771.288.720
DMU20DMU27, DMU4510.4419.56
DMU21DMU27, DMU4515.1424.86
DMU22DMU27, DMU4536.4113.59
DMU23DMU27, DMU4546.6313.37
DMU24DMU27, DMU4559.8210.18
DMU25DMU27, DMU4574.705.300
DMU26DMU27, DMU4531.6958.31
DMU29DMU27, DMU456.97023.03
DMU30DMU27, DMU4519.5020.50
DMU31DMU27, DMU4531.7718.23
DMU32DMU27, DMU4544.2015.80
DMU33DMU18, DMU270.36069.64
DMU34DMU27, DMU4576.403.600
DMU35DMU18, DMU278.97081.03
DMU36DMU18, DMU279.61090.39
DMU52DMU27, DMU455.29074.71
DMU53DMU27, DMU455.63084.37
DMU54DMU27, DMU459.66090.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.

© 2018 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Adeyemi Abel Ajibesin (August 22nd 2018). Efficient Frontier and Benchmarking Models for Energy Multicast in Wireless Network Coding, Network Coding, Mohammad A. Matin, IntechOpen, DOI: 10.5772/intechopen.79377. Available from:

chapter statistics

643total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Introductory Chapter: Network Coding

By Mohammad Abdul Matin

Related Book

First chapter

A Novel PFC Circuit for Three-Phase Utilizing Single Switching Device

By Keiju Matsui and Masaru Hasegawa

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us