Taguchi Design of Experiments for optimizing the Performance of AODV Routing Protocol in MANETS

Download Full-Text PDF Cite this Publication

Text Only Version

Taguchi Design of Experiments for optimizing the Performance of AODV Routing Protocol in MANETS

K. Sahithi

    1. ech, CS &SE Department Andhra University Visakhapatnam, A.P., India

      Dr.S.P.Setty

      Professor, CS &SE Department Andhra University Visakhapatnam, A.P., India

      AbstractIn this paper we evaluate the performance of Ad- Hoc on Demand (AODV) protocol in mobile ad hoc network. Using Taguchi design of experiment, the main effects of three factors (network size, transmission rates, and packet size) on two performance metrics (throughput and end-to-end delay) is quantified. The analysis of mean (ANOM) and analysis of variance (ANOVA) is employed to determine the best conditions required and to identify the level of importance of factors in order to obtain the best performance of AODV protocol. The findings show that network size is the leading factor to optimize the throughput and transmission rate for minimization of delay. Also, good agreement is observed between the predicted and experimented SNR for both throughput and end-to-end delay.

      Keywords AODV routing protocol, Mobile Ad-Hoc Networks, Performance metrics, Taguchi design of experiment,Analysis of Variance(ANOVA).

      1. INTRODUCTION

        A mobile ad hoc network (MANET) is a multi-hop wireless network formed by a group of mobile nodes that have wireless capabilities. As nodes are mobile determination of route between pair of nodes is challenging. So, routing is the most studied problem in MANETs. Routing protocols can be classified into two major classes: proactive protocols and reactive protocols.

        The rest of the paper is organized as follows: Reactive routing protocol AODV is described in section 2. Section 3 deals with basic concepts of Taguchi technique, section 4 shows the experimental design and simulation environment, data analysis is focused in section 5, validation is shown in section 6, section 7 concludes the findings.

      2. AD HOC ON-DEMAND DISTANCE VECTOR ROUTING (AODV)

        The On demand routing protocol, Ad Hoc On-Demand Distance Vector (AODV) Protocol finds the routes as and when required. The route discovery and route maintenance are the key elements during AODV routing.

        In Route Discovery process whenever a mobile node needs to send data to a particular node, a ROUTE REQUEST (RREQ) message was flooded.

        Once the RREP message was received by the sending node, the route has been established and data packets may be forwarded on that route.

        The failure of the links or routers was handled in the route maintenance process through a ROUTE ERROR (RERR) message.

      3. CONCEPT

        In general, performances of routing protocols are evaluated through simulation. Most of the studies are based on one- factor-at-a-time approach, in which, only one factor is changed, keeping other factors constant. Such technique doesnt consider the interaction among factors. This strategy of analysis can be enhanced by quantifying the effects of various factors and their interactions on the performance. The statistical design of experiment (DOE) can also be used that considers the simultaneous study of effects of several factors rather than one at a time.

        Design of experiments (DOE) refers to the process of planning an experiment by collecting data and analyzing using statistical methods. It is a systematic method to determine the relationship between factors affecting a process and the output of that process. This information is needed to manage process inputs in order to optimize the output.

        1. Taguchi Technique

          Taguchi technique helps in determining the optimal combination of factors. Two vital tools are utilized in Taguchi design: orthogonal arrays (OAs) and signal-to-noise ratio (SNR).

          The OA is selected based on factor quantities which allows the simultaneous study of all factors and estimate the effect of each factor independently. The degrees of freedom for the orthogonal array should be greater than or at least equal to the number of factors.

          The variation (of factor) which affects the change in particular design parameter of the performance is computed through signal-to-noise ratio (SNR). The SNR is used to measure the performance metrics as well as the significant parameters through analysis of variance (ANOVA).Three classes of the performance metric in the analysis of SNR are employed: larger-the-better, smaller-the-better and the nominal-the-best. The larger SNR corresponds to the better performance metric. As an example, for the routing protocol, throughput is a larger-the-better performance metric while end-to-end delay is a smaller-the-better performance metric.

          Analyzing SNR

          For larger-the-better case, the SNR is computed as:

          thrpt = -10 log (1/r ri=1 1/y2)

          For smaller-the-better case, the SNR is computed as:

          delay = 10 log (1/r ri=1 y2)

          Where, r is the number of simulation repetitions under same design point and y is the response value

          Label

          Factor

          Level 1

          Level 2

          Level 3

          A

          Network size

          10 nodes

          30 nodes

          50 nodes

          B

          Transmission Rate

          1 Mbps

          5.5 Mbps

          11 Mbps

          C

          Packet size

          512 bytes

          1024 bytes

          2048 bytes

          The overall mean value of over the nine experiments becomes:

          TABLE 1: EXPERIMENTAL PARAMETERS AND THEIR LEVELS

          i=1

          = 1/9 9 i

          The effect of a factor is defined as the absolute difference between the maximum S/N ratio and minimum S/N ratio of 3 levels. For example, to calculate the average effect of factor A at level 1, all results of factor A at level 1 are averaged. Hence, the average effect of factor A at level 1 A1 and the effect of factor A can be written, respectively, as:

          A1 = 1/3[1 + 2 + 3] and effect of A = |max min| A factor with the largest effect means that it has the most

          significant influence on the response metric.

        2. ANOVA

        The analysis of variance (ANOVA) is used to discuss the relative effect of all factors on the response metric and to determine which factor has the highest effect. Parameters used in ANOVA are calculated by the following equations:

        The sum of squares (SST) from SNR is:

        i=1

        SST = n (i – )2

        TABLE 2: EXPERIMENTAL LAYOUT USING L9 ORTHOGONAL ARRAY

        Where, i is the SNR for the ith experiment.

        i=1

        Design Point

        Level of Factors

        A

        B

        C

        1

        1

        1

        1

        2

        1

        2

        2

        3

        1

        3

        3

        4

        2

        1

        2

        5

        2

        2

        3

        6

        2

        3

        1

        7

        3

        1

        3

        8

        3

        2

        1

        9

        3

        3

        2

        The sum of squared deviations due to each factor (SSj) is SSj = L (ji – )2

        Routing Protocol

        AODV

        Simulation Time

        900sec

        Simulation Area

        1500m X 1500m

        Packet Size

        512,1024,2048

        bytes

        Network size

        10,30,50 nodes

        Transmission rate

        1,5.5,11 Mbps

        Traffic Type

        FTP

        SIMULATION PARAMETERS

        Where L is the number of levels and ji is the average SNR of the jth factor at ith level.

        Also, the sum of squares of error (SSe) is given by

        SSe = SST – qj=1 SSj

        Where q is the number of factors and SSj is the sum of squared deviations for each factor.

        The percentage contribution related to each factor j is

        j = (SSj/ SST )*100

        The j value gives the significance level for each factor. The F-test can also be used to determine which factor has the most significant effect on the performance metric. The large F-ratio indicates the strong effect of the factor. The F-value for jth factor can be evaluated as

        F = (SSj/Dfj)/(SSe/Dfe)

      4. EXPERIMENTAL DESIGN AND SIMULATION Taguchi technique of design of experiment has been

        extensively used in estimating the performance of routing protocols for MANETs. Performance of AODV is evaluated based on three factors: network size, transmission rates, packet size. Table 1 show the parameters examined in this study. Each factor is examined at three different factor levels- a low level

        (1) a medium level (2) and a high level (3). According to the number of parameters and their levels, a L9 (33) orthogonal array (as the degree of freedom for the orthogonal array should be greater than or at least equal to, those of factors) is the most suitable array. The experimental layout for the parameters using the L9 OA is shown in Table 2. Each combination of parameter levels is called design point. Each design point corresponds to a simulation scenario.

        Simulators like NS2, Glomosim, Opnet, Qualnet etc., were developed to evaluate the performance of routing protocols. Simulation of each design point is carried out using OPNET and results are collected. As each scenario is executed, the throughput and the end-to-end delay are computed as performance metrics. Delay and Throughput of each design point obtained is shown in figures 1 to 9.

        Figure 1 Delay and Throughput of design point 1

        Figure 2 Delay and Throughput of design point 2

        Figure 3 Delay and Throughput of design point 3

        Figure 4 Delay and Throughput of design point 4

        Figure 5 Delay and Throughput of design point 5

        Figure 6 Delay and Throughput of design point 6

        Figure 7 Delay and Throughput of design point 7

        Figure 8 Delay and Throughput of design point 8

        Figure 9 Delay and Throughput of design point 9

      5. RESULTS AND DATA ANALYSIS

        The values of performance metrics, Throughput and End-to- End Delay obtained during execution of each design point is shown in Table 3.

        The SNR is used to represent the performance metric and the largest SNR is required. The analysis of means (ANOM) was carried out to determine the effects of parameter.

        The throughput is defined as the total number of delivered data packets divided by the total duration of simulation time and the end-to-end delay is defined as the time a data packet takes to travel from source to the destination.

        A larger throughput is normally required in transmitting data packet process. Therefore, the-larger-the-better

        methodology of SNR was employed for the optimization of throughput. The SNR for each performance metric of the eight experimental runs are listed in Table 4. The effect of each parameter on the SNR at different levels can be separated out since the experimental design is orthogonal. To obtain the effect of each parameter on each performance metric for each level, the SNR with same level of parameter are average for the eight experiments.

        The response table of SNR for the throughput is summarized and listed in Table 5. Response table shows the optimal levels for each factor. The parameter level combination A3B3C3 is recommended. The results of ANOVA for the SNR of the throughput are shown in Table 6. It can be seen that the contribution of factor A to the throughput is the largest (81.96%). Therefore, the network size (factor A) has the greatest impact on the throughput.

        Main effects plot for S/N ratio for throughput is shown in Figure 10. Since the slope of the line in first box (corresponding to network size) in figure 10 is the largest than those of others which shows network size has the greatest impact on optimizing the throughput.

        Main effects plot for S/N ratio for delay is shown in Figure

        11. Since the slope of the line in second box (corresponding to data rate) in figure 11 is the largest than those of others which shows data rate has the greatest impact on minimizing the delay.

        Figure 10 Main effects plot for S/N ratio for throughput

        Figure 11 Main effects plot for S/N ratio for delay

        TABLE 3: ORTHOGONAL ARRAY WITH EXPERIMENTAL RESULTS

        Design Point

        Level of Factors

        Performance Metrics

        A

        B

        C

        Throughput

        Delay

        1

        1

        1

        1

        2125.17

        0.00168

        2

        1

        2

        2

        2583.59

        0.00058

        3

        1

        3

        3

        5723.04

        0.00048

        4

        2

        1

        2

        5812.14

        0.00131

        5

        2

        2

        3

        7042.88

        0.00045

        6

        2

        3

        1

        4762.48

        0.00044

        7

        3

        1

        3

        13478.57

        0.0014

        8

        3

        2

        1

        10230.86

        0.00037

        9

        3

        3

        2

        18787.14

        0.0004

        TABLE 4: SNR VALUES FOR THROUGHPUT AND END-TO-END DELAY

        Design Point

        Level of Factors

        SNR

        A

        B

        C

        Throughput

        Delay

        1

        1

        1

        1

        66.54787

        55.49381

        2

        1

        2

        2

        68.24447

        64.73144

        3

        1

        3

        3

        75.15254

        66.37518

        4

        2

        1

        2

        75.28672

        57.65457

        5

        2

        2

        3

        76.95501

        66.93575

        6

        2

        3

        1

        73.55666

        67.13095

        7

        3

        1

        3

        82.59288

        57.07744

        8

        3

        2

        1

        80.19824

        68.63597

        9

        3

        3

        2

        85.47721

        67.9588

        Grand averag ( )

        76.00129

        63.55488

        TABLE 5: RESPONSE TABLE FOR THROUGHPUT

        Parameter

        Mean SNR

        Delta

        Rank

        Level 1

        Level 2

        Level 3

        A

        69.97667

        75.26

        82.75

        12.77333

        1

        B

        74.80333

        75.12667

        78.05667

        3.253333

        3

        C

        73.42667

        76.33

        78.23

        4.803333

        2

        TABLE 6: ANALYSIS OF VARIANCE FOR THROUGHPUT

        Parameter

        SS

        df

        MS

        F-Ratio

        P (%)

        A

        247.1718

        2

        123.5859

        12.82435

        81.96526

        B

        19.27362

        2

        9.636811

        0.548928

        6.391375

        C

        35.11136

        2

        17.55568

        11.64337

        SSTOTAL

        301.5567

        100

        The same analysis procedure is applied to optimize the end-to-end delay. The response table of SNR for the end-to- end delay is listed in Table 7. The levels that gave the largest average response were selected from the response table. The parameter level combination A3B3C1 is recommended. The result of ANOVA in Table 8 shows that the transmission rates (factor B), 95.81% is the most important factor that effect performance end-to-end delay.

        TABLE 7: RESPONSE TABLE FOR END-TO-END DELAY

        Parameter

        Mean SNR

        Delta

        Rank

        Level 1

        Level 2

        Level 3

        A

        62.1967

        63.9267

        64.55

        2.353333

        2

        B

        56.76

        66.7633

        67.15

        10.39

        1

        C

        63.75

        63.4667

        63.4567

        0.293333

        3

        TABLE 8: ANALYSIS OF VARIANCE FOR END-TO-END DELAY

        Parameter

        SS

        df

        MS

        F-Ratio

        P(%)

        A

        8.919622

        2

        4.459811

        0.042848

        4.105613

        B

        208.1683

        2

        104.0841

        1250.844

        95.81778

        C

        0.166422

        2

        0.083211

        0.076602

        SSTOTAL

        217.2543

        100

      6. VALIDATION

        Figure 12 and figure 13 shows the linear model analysis for throughput and delay respectively. Factor with the highest coefficient shows the greatest impact on the response metric. It is observed that for throughput it is network size and for delay it is data rate. The other factors have low value of coefficient. The value of R2 from the figures12 and 13 indicate that the model perfectly fits the data. In the figure 12, the corresponding P-value of network size is 0.027 < 0.05 i.e. this factor is statistically significant for throughput and in the figure 13,the P-value for data rate is 0.011 < 0.05 showing that it has the most significant affect on delay at 5% level of significance ( = 0.05) or 95 % confidence level. From the tables in figure 12 and figure 13 the P-value for other factors which is greater than 0.05 show that these factors are insignificant.

        Figure 1210 Linear regression model for SNR values of throughput

        Figure 1311 Linear regression model for SNR values of delay

        The interpretation about the factor effects using the orthogonal array design can be considered correct and satisfied if experimented values of SNR fall within the range of confidence interval.

        The optimal predicted SNR for throughput and end-to-end delay can be computed using

        where is the grand average, jk is the means SNR for jth factor at the optimal kth level, and q is the number of factors that significantly affect.

        The predicted SNR for throughput and end-to-end delay obtained is 87.03409 and 68.3402 respectively.

        Confidence interval (C.I.) around the predicted SNR of drop rates above is computed as

        where F(,v1,v2) is the value from F distribution, is confidence level, v1 is the df of the mean performance, and v2 is the df for error, Ve is variance of error, and Ne is number of effective replications. The predicted SNR using the optimal levels is

        expected to fall in the range of . With 95% confidence level ( = 0.05), the confidence interval around the estimated SNR is 5.14. Thus, the confidence interval for the expected throughput and end-to-end delay is [92.174 81.894] and [73.48

        63.2] respectively.

        TABLE 9: RESULT OF CONFIRMATION EXPERIMENT FOR THROUGHPUT

        SNR

        Optimal factor-level combinations A3B3C3

        Predicted

        Confidence interval

        Experimented

        87.034

        [92.174 81.894]

        89.7752

        TABLE 10: RESULT OF CONFIRMATION EXPERIMENT FOR DELAY

        SNR

        Best factor-level combinations A3B3C1

        Predicted

        Confidence interval

        Experimented

        68.340

        [73.48 63.2]

        68.565

        Table 9 and Table 10 shows the comparison of the expected SNR throughput and delay at 95% confidence level with the measured SNR value of confirmation experiment. It is seen that the experimented values of throughput and delay fall in the range of confidence interval.

        Improvement in the results with performance of simulation using optimal combination of factors levels for both throughput and delay is observed as shown in the figures 13 and figure 14 respectively. Values of throughput and delay obtained using optimal combination of factors levels are 30,815.09 and 0.000373 respectively. These values of both throughput and delay are transformed into SNR.

        Figure 1412 Increase in Throughput with optimal combination of factors levels

        Figure 14 Variation of Delay with optimal combination of factors levels

      7. CONCLUSION

In this paper, the effects of three factors (network size, transmission rate, packet size) is evaluated simultaneously using Taguchi experimental design with regards to two performance metrics (throughput and end-to-end delay). The simulation data is analyzed and the results are summarized as follows:

Based on ANOM and ANOVA, the best factor combination obtained for the throughput is A3B3C3 and end-to-end delay is A3B3C1. The network size (81.96%) is the most important parameter that contributes to the performance of throughput, while the transmission rate (95.81%) is the most important parameter that contributes to the performance of end-to-end delay. Also, good agreement is observed between the predicted and actual SNR for throughput and end-to-end delay.

REFERENCES

[1]. D. P. Agrawal and Q-A Zeng. Introduction to Wireless and Mobile Systems, Brooks/Cole Publishing, ISBN No.0534-4851-6, 436 pages, 2003.

[2]. Abolhasan, M., Wysocki, T., & Dutkiewicz, E. (2004). A review of routing protocols for mobile ad hoc networks, Ad Hoc Networks.2(1): 122.

[3]. Boukerche, A. (2004). Performance Evaluation of Routing Protocols for Ad Hoc Wireless Networks, Mobile Networks and Applications, 9(5): 333342.

[4]. Ranjit K. Roy, Design of Experiment Using The Taguchi Approach: 16 step to product and process improvement, John Wiley & Sons, Inc. Toronto, Canada, 2001.

[5]. Alexander Voice, Andrew Wilkins, Rohan Parambi, Ibrahim Oraiqat Factor Analysis and ANOVA, 2007

[6]. S. R. Das, C. E. Perkins & E. M. Royer, Performance comparison of Two On-Demand Routing Protocols for Ad Hoc Networks, Proceedings of IEEE Conference on Computer Communications (INFOCOM), March 2000, Tel Aviv, Israel: IEEE.

[7]. Swati Saxena, Madhavi Sinha, Analyzing end-to-end delay and packet drop of Adaptive Fault Tolerant Replication Routing Algorithm for MANET using Taguchi Approach, International Journal of Engineering, Science and Technology, vol. 5, no. 7, July 2013, pp. 1492 1500.

[8]. Hazura Mohamed, Muhammad Hisyam Lee, Mazalan Sarahintu. Taguchi Approach for Performance Evaluation of Routing Protocols in Mobile Ad Hoc Networks, Journal of Statistical Modeling and Analytics Vol. 1 No. 2, 10-18, 2010.

[9]. Sushil Kumar, Dinesh Singh & Mridul Chawla. Performance Comparison of Routing Protocols in MANET Varying Network Size, International Journal of Smart Sensors and Ad Hoc Networks (IJSSAN) ISSN No. 2248-9738 (Print) Volume-1, Issue-2, 2011.

[10]. Mazalan Sarahintu, Muhammad Hisyam Lee & Hazura Mohamed. Determining the Effects of Scenario Metrics on the Performance of Dynamic Source Routing using Taguchi Approach, Volume 23, Number 2, 121-132.

[11]. Hazura Mohamed, Muhammad Hisyam Lee, Mazalan Sarahintu, Shaharuddin Salleh and Bahrom Sanugi. The Use of Taguchi Method to Determine Factors Affecting the Performance of Destination Sequence Distance Vector Routing Protocol in Mobile Ad Hoc Networks, Journal of Mathematics and Statistics 4 (4): 194-198, 2008

ISSN 1549-3644.

[12]. Vinod Mahor, Sandeep Raghuwanshi. Taguchis Loss Function Based Measurement of Mobile Ad-Hoc Network Parameters under AODV Routing Protocol, IEEE 31661.

Leave a Reply

Your email address will not be published. Required fields are marked *