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

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.