International Journal of Computer Networks & Communications (IJCNC)

AIRCC PUBLISHING CORPORATION

IJCNC 4

Response Surface Methodology For Performance Analysis And Modeling Of MANET Routing Protocols

Mohamed Skander Daas1 and Salim Chikhi2

1MISC Lab, Department of Fundamental Computer Science and its Applications, Abdelhamid Mehri Constantine 2 University, Constantine, Algeria

2MISC Lab, University of Abdelhamid Mehri – Constantine 2, Constantine, Algeria

Abstract


Numerous studies have analyzed the performances of routing protocols in mobile Ad-hoc networks (MANETs); most of these studies vary at most one or two parameters in experiments and do not study the interactions among these parameters. Furthermore, efficient mathematical modeling of the performances has not been investigated; such models can be useful for performance analysis, optimization, and prediction. This study aims to show the effectiveness of the response surface methodology (RSM) on the performance analysis of routing protocols in MANETs and establish a relationship between the influential parameters and these performances through mathematical modeling. Given that routing performances usually do not follow a linear pattern according to the parameters; mathematical models of factorial designs are not suitable for establishing a valid and reliable relationship between performances and parameters. Therefore, a Box–Behnken design, which is an RSM technique and provides quadratic mathematical models, is used in this study to establish a relationship. The obtained models are statistically analyzed; the models show that the studied performances accurately follow a quadratic evolution. These models provide invaluable information and can be useful in analyzing, optimizing, and predicting performances for mobile Ad-hoc routing protocols.

Keywords


Response surface methodology, performance analysis, and modeling, routing protocols, mobile ad-hoc networks, design of experiments

1.Introduction


Many protocols have been developed for mobile ad-hoc networks, OLRS, AODV, and DSDV are among the most studied [1], and have often been used as a reference in most studies and performance analyses.

However, analyzing protocols performances in MANETs is a complex task. For each scenario, several critical parameters (e.g., number of nodes, number of connections, data rate, node velocity, and pause time) must be accurately controlled to satisfy the required characteristics of the performance analysis. The development of computing machines has led to the development of increasingly complex simulators. This complexity results in simulations that require much computing time. For example, simulating an experience may consume more time than real-world execution. Therefore, realizing or simulating real experiences in both cases may be relatively costly in terms of time, effort, energy, resources, and so on. In order to cope with this problem, design of experiments (DOE) provides a set of well-selected experiences to obtain the maximum desired information at a low cost. Conventional methods of analyzing protocol performances are usually Univariate; only one parameter is changed at a time while the remaining parameters are kept constant, and the interactions among different parameters are disregarded. These methods require a large number of experiments and consume much time, [2-8] are examples which use this kind of analysis.

Response surface methodology (RSM) can effectively deal with the limitations of the abovementioned methods. RSM is a systematic technique to define the relationship between the parameters affecting a process and the response of that process via quadratic models. Analysis of variance (ANOVA) and regression are the most important tools in RSM data analysis. RSM has been successfully applied in various scientific and industrial fields, such as chemistry, biology, physics, mechanics, and chemical engineering. RSM has also been used to conduct experiments to rapidly develop and improve novel products and processes. It allows researchers and engineers to explicitly model the relationships among various parameters in a given system and arrive at optimal solutions in minimal time. In RSM, several process parameters can be simultaneously varied and studied. A small number of experiments are necessary to estimate the contribution degree of the individual and the interaction effect parameters on the investigated responses.

In the presented study, several important parameters (number of nodes, number of connections, data rate, velocity of nodes, and pause time) of OLSR, AODV, and DSDV routing protocols are examined, and a quadratic mathematical modeling using the Box–Behnken design is performed to analyze the effects of main parameter and their interactions on numerous crucial performance metrics (packet delivery fraction, average throughput, average end-to-end delay, mean of hops number, mean jitter, and normalized routing overhead). The obtained models can be used to analyze, predict and optimize the performance of each metric of each protocol under the provided parameters. This provides invaluable perspectives to the performance analysis of the selected routing protocols

2.Related Works


In literature, only a few studies employed DOE to study several parameter effects or/and their interactions on several performance metrics of MANET routing protocols. The authors in [9] used the Taguchi approach to determine the effects of several factors (terrain, network size, pause time, node velocity, transmission range, packet rates, and traffic load) and their interactions on the routing overhead performance metric of the DSR protocol. The study showed that the most significant parameter that affects the routing overhead is the size of the network, followed by pause time, node speed, and traffic load. Similarly, the authors in [10] employed the Taguchi approach to investigate the drop rate performance of DSR and AODV routing protocols. In the same work various parameters of network performance (routing protocol, node density, node speed, traffic load, and pause time)  are considered to analyze the factors and interactions for the network performance of DSR and AODV routing protocols by  determining various metrics (packet delivery ratio, average delay, discovery time, and recovery time) using a factorial design. Many other works used factorial design to quantify the main and interactive effects [11, 10, 12, 13]. The authors in [14], have used a factorial design technique to analyze routing mobile ad-hoc networks and have developed two first-order linear models that define the relationship between the influential parameters and two performance metrics. An interesting study [15] used DOE for factor screening (23 factorial design) to identify the most influential timers in the AODV routing protocol and the number of retries before declaring link failure in the MAC protocol affecting average throughput and average packet delay. Response surface methodology (RSM) was applied to optimize the values of the significant factors and improve the average packet delay and average throughput. Similarly, authors in [16] applied successfully RSM to model and optimize the node’s power consumption to study the effect of several parameters on the power consumption of Digi’s XBee PRO of shelf WSN modules.

3.Mobile Ad-Hoc Routing Protocols 


Several protocols exist, addressing the problem of routing in MANETs. Such protocols can be divided into three classes based on when and how discovering routes. The first type of protocols is the proactive protocols, where routing information is collected without an actual need for a given route establishment. This information is stored in routing tables and should be periodically maintained. The second type of protocols is the reactive (or on-demand) protocols, this kind of protocols establish a route from source to a destination node when a source need it. The third type is the hybrid routing protocols which are a combination of proactive and reactive routing protocols [17]. In this paper, we examine three main ad-hoc routing protocols – OLSR [18], AODV [19] and DSDV [20].

4.Performance Metrics


Performance metrics are interesting because they can project what actually occurs during the simulations and provide valuable information on the simulated routing protocols.

Before presenting the studied performance metrics, below are several utilized terms.

  • tFirstRxPacket and tLastRxPacket represent the beginning and end times of the flow from the viewpoint of the receiver.
  • delaySum and jitterSum are the sum of delay and jitter values.
  • txPackets is the number of transmitted packets.
  • rxBytes and rxPackets are the number of received bytes and packets.
  • timesForwarded is the number of times a packet has been reportedly forwarded summed for all packets in the flow.
  • txRoutingPackets is the number of transmitted routing packets.

4.1. Packet Delivery Fraction 

Packet delivery fraction (PDF) is the ratio of the total number of successfully delivered data packets at the destination divided by the total number of generated data packets.

4.2. Average Throughput

The average throughput (ATH) is the total number of received data packets by the sink agent at a specific time. ATH is obtained by dividing the total data packet size received by the sum of the differences between the time the last packet was received and the time the first packet was received in each flow multiplied by 8. It is expressed in bits/s.

4.3. Average End-To-End Delay

The average end-to-end delay (E2ED) determines the average time that packets require from the source to the application layer at the destination node. It is expressed in seconds.

4.4. Mean Hop Count

Mean hop count is the mean of the number of hops traveled by packets

4.5. Mean Jitter

Jitter is the variation in time between arrivals of packets. For improved performance, the delay between packets should be small.

4.6. Normalized Routing Overhead

The normalized routing overhead (ROH) is the total number of transmitted routing packets, including forwarded routing packets, divided by the total number of received data packets at the destination.

5.Performance Analysis And Modeling Of MANET Routing Protocols Using RSM


 The most important parameters (number of nodes, number of connections, data rate, node velocity, and pause time) of OLSR, AODV, and DSDV routing protocols were studied, and an RSM approach was employed to analyze the effects of these main parameters and their interactions on numerous crucial performance metrics (PDF, ATH, E2ED, MHOP, JIT, and ROH).The relationship between parameters and the performances is generally nonlinear (presence of curvature effect), that is why the full factorial design models will not be suitable for performance modeling. Quadratic mathematical models using the Box–Behnken design were developed to model the performance of each metric of each protocol under the given parameters. Invaluable perspectives for the performance analysis of the selected routing protocols are thus provided. The software Minitab was used for results analysis, mathematical model building, and graph plotting. The interested reader can find more details about RSM in [21].

5.1. Mathematical Modeling Of Routing Protocols Performances Using Box-Behnken Design

The Box–Behnken design is an RSM (Response Surface Methodology) design used to develop a mathematical model that allows efficient estimation of first- and second-order coefficients. Each factor takes one of three equally spaced values coded as -1, 0, and +1. Figure 1 shows the experimental points of a Box–Behnken design with three factors.


Figure 1.An example of the Box-Behnken design with three factors

5.2. Experiment Details 

The experiments were simulated with the network simulator NS-3 version 3.25 under the Linux (Ubuntu 15.0) operating system. The simulation time was set to 900 s, and the first 50 s were used as start-up time. Nodes were randomly distributed and positioned according to the random waypoint (RWP) mobility model in a rectangular field of 300m x 1500m; their velocity was uniformly selected from 0 to a given speed (m/s). The nodes used CBR/UDP sources generating packets of 64 bytes. The 802.11b MAC was installed on each node. The bandwidth was 11 Mb/s. Application data were initialized at a random time between 50 and 51 s and continued until the end of the simulation. We employed 10 runs in each experiment, and each obtained performance result is the average of 10 runs.

5.3. Selection Of Process Parameters

By following RSM, the five parameters were considered, The five factors and their corresponding levels are provided in Table 1; the response varies in the studied domain.

Table 1. Parameter levels.


To estimate the coefficients of the quadratic model, the experiment matrix of the Box–Behnken design for five factors is provided in Table 2. The parameters corresponding to the central point (0, 0, 0, 0, 0) are repeated three times. The proposed design requires 43 runs to model a response surface.

Table 2 Box-Behnken design matrix with five parameters.

5.4. Experimental Results For Box-Behnken Design

The PDF, ATH, E2ED, MHOP, JIT, and ROH values determined as output parameters (responses) for OLSR, AODV, and DSDV for the 43 experiments are provided in Table 3 and Table 4.

Table 3 Results of the Box-Behnken Design Experiments of PDF, ATH and E2ED performances.


Table 4 Results of the Box-Behnken Design Experiments of MHOP, JIT, and ROH performances.


5.5. Quadratic Regression Models

The mathematical models generated by RSM in the current study aims to establish a relationship between different performance metrics and input parameters A, B, C, D, and E that can be used to predict the response values for a given set of control parameters. The second-order polynomial equation may be written as:


where is the predicted response, β0 is the constant coefficient, βi is the ith linear coefficient of input parameter xi, βii is the ith quadratic coefficient of input parameter xi, βij is the interaction coefficients between input parameters xi and xj, and є is the error of the model. The estimated coefficients  are obtained using mathematical regression according to formula 8:


Where is the transpose of the matrix .  is the matrix of the model which depends on the experimental points chosen to execute the design. y is the vector of the responses, Eighteen mathematical models were obtained through RSM. Each model corresponds to a given performance (PDF, ATH, E2ED, MHOP, JIT, or ROH) of a given protocol (OLSR, AODV, or DSDV). These models can be employed to analyze, optimize, and predict the six performance metrics of the three protocols under a given configuration of the five factors (A, B, C, D, and E). Table 5 and Table 6 show the coefficients of different models according to Equation 9.


Table 5.Model Coefficients of PDF, ATH and E2ED performances.


Table 6.Model Coefficients of MHOP, JIT, and ROH performances.


Based on models 9 and 15, two examples of surface plots are generated in Figures 2 and Figure 3 to see a graphic representation of the effect of different parameters on E2ED performance respectively in AODV and DSDV protocols. Surface plots show how two parameters at one time affect E2ED metric together. Since there are more than two parameters, the parameters not exposed in the graphs are kept constant at level 0.


Figure 2. Surface Plots of Average End-to-End Delay (E2ED) in AODV


Figure 3. Surface Plots of Average End-to-End Delay (E2ED) in DSDV

5.6. Analysis Of Quadratic Models

The responses of the Box–Behnken design experiments in Tables 3 and 4 were fed into Minitab software and analyzed using analysis of variance (ANOVA) with 95% of confidence level.

Firstly, using DOE can provide much analytical information and statistical plots. For the sake of brevity, these plots are not presented in this paper for all responses; however, it can be obtained using a DOE software. Figure 4 is a screenshot from Minitab software showing an example of the regression model and ANOVA results of ATH performance of OLSR protocol.

The p-value (P) determines which of the effects in the model are statistically significant, P is compared to a-level of (0.05), and if the p-value is less than to 0.05 we can conclude that the effect is significant; else we conclude that the effect is not significant. In this example, it can be seen that the only significant terms are A, C, D, AC and DE, the other terms are not significant.

Many others plots can be extracted like residual plots; Figure 5 presents an example of four residual plots of ROH performance of AODV protocol which are:

  • Histogram of the residuals: shows global characteristics of the residuals. A long tail on one side indicates a skewed distribution. If at least two bars are distant from the others, those points can be considered as outliers.
  • Normal probability plot of residuals: if the residuals are normally distributed, the points should generally take a straight line, else, the normality assumption may be invalid.
  • Residuals versus fitted values: on both sides of 0, this plot should form a random pattern. If a point is far from the majority of the other points, it may be considered as an outlier.

Residuals versus order of data: represents a plot of all residuals in the order of data collection, it can be useful to find non-random error and to check if the residuals are uncorrelated with each other.


Figure 4. An example of the regression model and the ANOVA results of ATH performance of OLSR protocol


Figure 5. An example of four residual plots of ROH performance of AODV protocol

Secondly, to check the quality of the obtained models many statistical measurements are shown in Table 7: R2, adjusted R2, predicted R2, lack-of-fit, P-value of regression and adequate precision. These statistical measurements can be obtained by performing an analysis of variance of the regression model which is a means of testing significance, quality, predictability, and adequacy of a model.

Table 7.Statistical measurements for models’ quality and validation.


The adequacy of the model fits can be explained by the significance determined by the p-value (Prob>F), when the model has a p-value <= 0,05, that means the model is significant and has 5% probability that a calculated response using the model is due to noise. All the studied responses have a very small p-value <= 0.001 which make all regression models significant.

The Lack-of-Fit report provides details for a test that evaluates whether the model fits the data well; it compares the residual error to the pure error from replicated design points. When the p-value of the lack-of-fit > 0.05 , means its non-significance. So when lack-of-fit is significant means that the model fits the data well. As shown in Table 7 p-values of lack-of-fit of ATH and PDF models for all protocols are >= 0.05 that the models accurately fits the data in contrary of ROH and JIT which have a p-value of lack-of-fit < 0.05.

R2 and adjusted R2 (adjusted for the number of terms in the model) are other measures to determine the amount of variation around the mean as explained by the given model; their values are always between 0 and 100%. The higher the value of R2 the better the model fits the data. However, the predicted R2 is calculated for each model in Table 7 to determine how well the model predicts novel observations. The predicted R2 determines how much variability in the new data the model is expected to explain [22]. The predicted R2 is always lower than the R2 and the adjusted R2 and may even be negative. Table 7 shows that the R2 values are considerably high. Generally, an R2 value between 70 and 100 indicates good correlation, that between 40 and 70 indicates average correlation, and that between 0 and 40 indicates low correlation.

To determine whether the obtained models can be adequately used to predict the response, adequate precision, which is a signal-to-noise ratio, was calculated; the result should be greater than 4 for it to be desirable [23]. All of the 18 developed models have adequate precision greater than 4, which indicates that these models are adequate for predicting responses. In general, it can be seen that ATH and PDF performances behaviors follow accurately quadratic pattern better than E2ED and MHOP metrics. JIT and especially ROH metrics are less predictable and show less quality of fitting models than all the other metrics.

5.6. Case Study 

This example shows how can the obtained models be used to predict ATH in OLSR, AODV, and DSDV protocols under a given parameters. Assuming that we wish to study the effects of number of nodes (A) on the average throughput metric under the given configuration of parameters (number of connections B=4, data rate C=512, node velocity D=16, and pause time E=100). Before replacing the values in different concerned models, the natural value of each parameter should be converted to a coded one (between -1 and +1) using formula 10.


Where,,,  and  correspond to the coded, natural, high, and low values of the parameter, respectively. The low and high values of each parameter are provided in Table 1. Therefore, the coded values of B, C, D, and E will be -0,5, -0,54, 0,55, and -0,77, respectively. The coded values can be replaced in the corresponding equation (Equation 11 to predict ATH in OLSR, Equation 12 to predict ATH in AODV, and Equation 13 to predict ATH in DSDV) plotted in Figure 6.



Figure 6.Example: Average throughput analysis of the case study

6.Conclusions


This study shows the manner in which the response surface methodology approach can be used to analyze and model the routing protocol performances of MANETs. The method provides more information, clear vision, an overview and detailed analysis, and an easy way of evaluating and comparing routing protocols and their behaviors. Eighteen empirical quadratic mathematical models are developed using the Box–Behnken design. The quality and the adequacy of the models are also studied and validated through statistical measures mainly based on regression and ANOVA tests. The models can be effectively employed to analyze, optimize, and accurately predict the six performance metrics under a given configuration of five parameters. The presented response surface plots provide an extensive exploratory analysis and comparison of these metrics, and give insight into the effects of various parameters. Developing models rather than conducting traditional experimental analysis is important; various models can be exploited by a third party to extract, analyze, or compare performances without performing additional specific experiments.

References 


[1]     A. Upadhyay and R. Phatak, “Performance evaluation of aodv dsdv and olsr routing protocols with varying ftp connections in manet,” IJRCCT, vol. 2, no. 8, 2013.

[2]     M. Salehi, A. Boukerche, and A. Darehshoorzadeh, “Modeling and performance evaluation of security attacks on opportunistic routing protocols for multihop wireless networks,”Ad Hoc Networks, vol. 50, pp. 88 – 101, 2016.

[3]     K. Yamaguchi, K. Mukaiyama, T. Akiyama, T. Kobayashi, and H. Matsue, “Performance analysis of routing methods based on olsr and aodv with traffic load balancing and qos for wi-fi mesh network,” in 2016 International Conference on Information Networking (ICOIN). IEEE, Jan 2016, pp. 114-119.

[4]     S. R. Das, R. Casta~neda, and J. Yan, “Simulation based performance evaluation of routing protocols for mobile ad hoc networks,” Mobile Networks and Applications, vol. 5, no. 3, pp. 179-189, 2000.

[5]     J. Zheng and Q. Wu, “Performance modeling and analysis of the ieee 802.11p edca mechanism for vanet,” IEEE Transactions on Vehicular Technology, vol. 65, no. 4, pp. 2673-2687, April 2016.

[6]     K. A. A. Omer, “The Impact of Node Misbehavior on the Performance of Routing Protocols in Manet,” International Journal of Computer Networks & Communications, vol. 8, no. 2, pp. 103-112, Nov 2016.

[7]     D. Torrieri, S. Talarico, and M. C. Valenti, “Performance comparisons of geographic routing protocols in mobile ad hoc networks,” IEEE Transactions on Communications, vol. 63, no. 11, pp. 4276-4286, Nov 2015.

[8]     G. A. QasMarrogy, A. Y. Ali, E. S. QasMarrogy, A. H. M. Aldlawie, “Performance Analysis of Routing Protocols and TCP Variants under HTTP and FTP Traffic in MANETs,” International Journal of Computer Networks & Communications, vol. 6, no. 6, pp. 79-96, Nov 2014.

[9]     M. H. Lee, H. Mohamed, and M. Sarahintu, “Determining the effects of scenario metrics on the performance of dynamic source routing using taguchi approach,” Matematika, vol. 23, pp. 121-132, 2007.

[10]   Y. Wang, D. Kaleshi, M. H. Barton, J. He, L. Li, A. Munro, and Z. Fan, “Key factor and interaction for network performance in mobile ad hoc networks,” in Wireless Pervasive Computing, 2007. ISWPC’07. 2nd International Symposium on. IEEE, 2007, pp. 302-306.

[11]   R. V. Boppana and A. Mathur, “Analysis of the dynamic source routing protocol for ad hoc networks,” in Workshop on Next Generation Wireless Networks, 2005, pp. 1-8.

[12]   S. Saxena and M. Sinha, “Statistical study of performance metrics of adaptive fault tolerant replication routing protocol for manet,” International Journal on Computer Science and Engineering, vol. 4, no. 11, p. 1804, 2012.

[13]   S. Hakak, S. A. Latif, F. Anwar, and M. K. Alam, “Impact of key factors on average jitter in manet,” in Proceedings of the 2014 First International Conference on Systems Informatics, Modelling and Simulation, ser. SIMS ’14. Washington, DC, USA: IEEE, 2014, pp. 219-223.

[14]   M. W. Totaro and D. D. Perkins, “Using statistical design of experiments for analyzing mobile ad hoc networks,” in Proceedings of the 8th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, ser. MSWiM ’05. New York, NY, USA: ACM, 2005, pp. 159-168.

[15]   K. K. Vadde, V. R. Syrotiuk, and D. C. Montgomery, “Optimizing protocol interaction using response surface methodology,” IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 627-639, June 2006.

[16]   G. Horvat, D. Sostaric, and D. Zagar, “Response surface methodology based power consumption and rf propagation analysis and optimization on xbee wsn module,” Telecommun. Syst., vol. 59, no. 4, pp. 437-452, Aug. 2015.

[17]   L. Buhrer, “Simulation of a data centric routing protocol for mobile ad hoc networks,” Master’s thesis, Swiss Federal Institute of Technology (ETH) Zurich, ftp://ftp.tik.ee.ethz.ch, 3 2003.

[18]   T. Clausen and P. Jacquet, “Optimized link state routing protocol (olsr),” United States, Tech. Rep., 2003.

[19]   C. E. Perkins and E. M. Royer, “Ad-hoc on-demand distance vector routing,” in Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA ’99. Second IEEE Workshop on. IEEE, Feb 1999, pp. 90-100.

[20]   C. E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers,” SIGCOMM Comput. Commun. Rev., vol. 24, no. 4, pp. 234-244, Oct. 1994.

[21]   R. Myers, D. Montgomery, and C. Anderson-Cook, Response Surface Methodology: Process and Product Optimization Using Designed Experiments, ser. Wiley Series in Probability and Statistics. Wiley, 2016. [Online]. Available: https://books.google.co.in/books?id=YFSzCgAAQBAJ

[22]   D. C. Montgomery, Design and analysis of experiments, 5th ed. New York / Chichester: John Wiley & Sons, 2001.

[23]   Stat-Ease, Handbook for Experimenters, Stat-Ease, Inc, T2021 East Hennepin Ave, Suite 480 Minneapolis, MN 55413, 2016.

Authors


Mohamed Skander Daas got his engineer degree in Parallel and Distributed Systems from the University of Mentouri Constantine, in 2007 and a Magister degree in Artificial Intelligence and Computer Imaging from University of Oum El-Bouaghi in 2014. He is currently a PhD candidate at the Department of Fundamental Computer Science and its Applications and a member at SCAL team (Soft Computing and Artificial Life) of MISC Laboratory, University of Constantine 2. He is also and Assistant Professor of computer science at University of Brothers Mentouri – Constantine 1. His current research projects focus on computational intelligence and mobile Ad-Hoc networks.

Salim Chikhi received his M.Sc. degree in computer systems from University Mentouri Of Constantine, Algeria, in collaboration with Glasgow University, UK, in 1993. He received his Ph.D. degree in computer science from University Mentouri of Constantine, Algeria in 2005. Currently, he is a full professor at the University Constantine2, Algeria. He is the head of MISC laboratory (Modeling and Implementation of Complex Systems) and the leader of the SCAL team (Soft Computing and Artificial Life). His research areas include soft computing and artificial life techniques and their applications to real life problems, namely routing in logistics, biometry, and natural language processing.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Information

This entry was posted on February 6, 2018 by .
%d bloggers like this: