%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
-%% CHAPTER 03 %%
+%% CHAPTER 03 %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%-------------------------------------------------------------------------------------------------------%%
\section{Introduction}
-Performance evaluation and optimization solvers are important tools. In the last few years, several intensive researches have been done about the WSNs, and for a wide range of real-world applications. Therefore, the performance evaluation of algorithms and protocols becomes challenging at various stages of design, development, and implementation. In fact, to perform an efficient deployment, it is desirable to analyze the performance of the newly designed algorithms and protocols in WSNs. Since performance evaluation tools are becoming precious means for evaluating the efficiency of algorithms and protocols in WSNs, they have received a great interest by many researchers around the world.
+\label{ch3:1}
+%Performance evaluation and optimization solvers are important tools.
+In the last few years, several intensive researches have been done about the WSNs, and for a wide range of real-world applications. Therefore, the performance evaluation of algorithms and protocols becomes challenging at various stages of design, development, and implementation. In fact, to perform an efficient deployment, it is desirable to analyze the performance of the newly designed algorithms and protocols in WSNs. Since performance evaluation tools are becoming precious means for evaluating the efficiency of algorithms and protocols in WSNs, they have received a great interest by many researchers around the world.
On the other side, the main challenges in the design of WSNs handle new hard and complex theoretical optimization problems. These optimization problems are related to several topics in WSNs such as coverage, topology control, scheduling, routing, mobility, etc.
%So, the optimization is very important in WSNs because the limited resources of the sensor nodes.
For this reason, several problems are modeled by an optimization problem for instance to optimize the network lifetime while satisfying the application requirements.
%Therefore, in order to get the optimal solutions for these mathematical optimization problems, the optimization solver is the best candidate tool to solve them. The optimization solver takes mathematical optimization problem descriptions in a certain file format and calculates their optimal solution.
Optimization solvers dedicated to specific resolution methods (meta-heuristics, linear programming, etc) are required.
%Many important real-world problems have formulated as integer programming problems.
-In this dissertation, we use linear programming because we used integer programs to optimize the coverage and the lifetime in WSNs.
+%In this dissertation, we use linear programming because we used integer programs to optimize the coverage and the lifetime in WSNs.
+In this dissertation, we optimize the coverage and the lifetime in WSNs and the problem is formulated through linear programming. These kind of models allow to obtain optimal solutions satisfying an objective (for instance, maximize coverage) under constraints (for instance, available remaining energy).
+
+The remainder of this chapter is organized as follows. The next section is devoted to the evaluation tools for evaluating and validating the performance of proposed algorithms and protocols. Section \ref{ch3:3} gives the most popular free and commercial linear optimization solvers to solve the linear programming problems. Finally, we give concluding remarks in section \ref{ch3:4}.
\section{Evaluation Tools}
+\label{ch3:2}
On the one hand, several proposed works in WSNs require evaluating the power depletion efficiently and accurately for network lifetime prediction. On the other hand, the wrong energy evaluation leads to waste of energy because the sensor nodes might be rendered useless long time before draining their energy. Furthermore, the sensor nodes might die before of the expected lifetime. However, evaluation experiments on actually deployed WSN suffer some constraints because of the large number of sensor nodes and the deployment in hostile and inaccessible environments. Moreover, the analytical (or theoretical) models might be unrealistic for real world systems.
-Two main evaluation tools are available for evaluating and validating the performance of proposed works of researchers in large-scale wireless sensor networks: testbeds and simulations~\cite{ref180}. The energy consumption results obtained by simulation and testbed evaluation tools give an alternative on time, precision, and cost.
+Two main evaluation tools are available to evaluate and validate the performance of proposed works of researchers in large-scale wireless sensor networks: testbeds and simulations~\cite{ref180}. The energy consumption results obtained by simulation and testbed evaluation tools give an alternative on time, precision, and cost.
%Therefore, the energy consumption results obtained by simulation and testbed evaluations give an alternative on time, precision and cost. Researchers can also evaluate and test their proposed works with simulation tools as well as testbed devices.
\item \textbf{NS2:}
-The Network Simulator-2 (ns-2)~\cite{ref191,ref192} is an open source, discrete event, network simulator. The major goal of ns-2 is to provide a simulation environment for wired as well as wireless networks to simulate different protocols with different network topologies. ns-2 is constructed using C++ and the simulation interface is provided via OTcl, an object-oriented dialect of Tcl. The network topology is determined by the users by writing OTcl scripts, and then the main program of ns-2 simulates this topology with fixed parameters. ns-2 provides a graphical view of the network by using network animator (Nam). Nam interface includes control features that allow researchers to forward, pause, stop, and control the simulation. ns-2 is the most common and widely used network simulator for scientific research work.
+The Network Simulator-2 (ns-2)~\cite{ref191,ref192} is an open source, discrete event, network simulator. The major goal of ns-2 is to provide a simulation environment for wired as well as wireless networks to simulate different protocols with different network topologies. ns-2 is built in C++ and the simulation interface is provided via OTcl, an object-oriented dialect of Tcl. The network topology is determined by the users by writing OTcl scripts, and then the main program of ns-2 simulates this topology with fixed parameters. ns-2 provides a graphical view of the network by using network animator (Nam). Nam interface includes control features that allow researchers to forward, pause, stop, and control the simulation. ns-2 is the most common and widely used network simulator for scientific research work.
-The next version, ns-3, is considered as a new simulator and a final replacement of ns-2, not a simple extension~\cite{ref194}. The ns-3 project~\cite{ref193} was started in mid-2006 and is still under intensive development. Like ns-2, ns-3 is an open source, discrete-event network simulator targeted essentially for research and educational use~\cite{ref195}. ns-3 supports both simulation and emulation using sockets. It also provides a tracing facility to help users in debugging.
+The next version, ns-3, is considered as a new simulator and a final replacement of ns-2, not a simple extension~\cite{ref194}. The ns-3 project~\cite{ref193} was started in mid-2006 and is still under intensive development. Like ns-2, ns-3 is an open source, discrete-event network simulator targeted essentially for research and educational use~\cite{ref195}. ns-3 supports both simulation and emulation using sockets. It also provides a tracing facility to help users in debugging.
\item \textbf{OMNeT++:}
-OMNeT++ (Objective Modular Network Testbed) is an open-source, free, discrete-event, component-based C++ simulation library, modular simulation framework for building network simulators~\cite{ref158,ref203}. Even if OMNeT++ is not a network simulator itself, it is very popular as a network simulation platform for both scientific and industrial communities. The major goal behind the development of OMNeT++ is to provide a strong simulation tool, which can be used by the academic and commercial researchers for simulating different types of networks in a distributed and parallel way~\cite{ref197}. OMNeT++ has an extensive Graphical User Interface (GUI) and intelligence support. It runs on Windows, Linux, Mac OS~X, and other Unix-like systems, and provides a component architecture for models. Components (modules) are first programmed in C++, then assembled into larger components and models using a high-level language (NED)~\cite{ref198}. Several simulation frameworks can be used with OMNeT++ such as INET, INETMANET, MiXiM, and Castalia, where each of them provides a set of simulation facilities (modelity and soon) and can be used for specific applications.
+OMNeT++ (Objective Modular Network Testbed) is an open-source, free, discrete-event, component-based C++ simulation library, modular simulation framework for building network simulators~\cite{ref158,ref203}. Even if OMNeT++ is not a network simulator itself, it is very popular as a network simulation platform for both scientific and industrial communities. The major goal behind the development of OMNeT++ is to provide a strong simulation tool, which can be used by the academic and commercial researchers for simulating different types of networks in a distributed and parallel way~\cite{ref197}. OMNeT++ has an extensive Graphical User Interface (GUI) and intelligence support. It runs on Windows, Linux, Mac OS~X, and other Unix-like systems, and provides a component architecture for models. Components (modules) are first programmed in C++, then assembled into larger components and models using a high-level language (NED)~\cite{ref198}. Several simulation frameworks can be used with OMNeT++ such as INET, INETMANET, MiXiM, and Castalia, where each of them provides a set of simulation facilities (modelity and soon) and can be used for specific applications.\\ \\
\item \textbf{OPNET:}
OPNET (Optimized Network Engineering Tool)~\cite{ref192,ref200,ref201} is the first commercial simulation tool developed in 1987 for communication networks. It is a discrete event, object-oriented, general purpose network simulator, which is widely used in industry. It uses C and Java languages. It provides a comprehensive development environment for the specification, simulation, configuration, and performance analysis of the communication network. OPNET allows researchers to develop various models by means of a graphical interface. It provides different types of tools such as Probe Editor, Filter Tool, and Animation Viewer for data collection to model graph and animate the resulting output. Unlike ns-2, OPNET provides modeling for different sensor-specific hardware, such as physical-link transceivers and antennas. It includes sensor-specific models such as ad-hoc connectivity, mobility of nodes, node failure models, modeling of power-consumption, etc. OPNET is, a commercial simulator and the license is very expensive. This represents the main disadvantage of that simulator.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\iffalse
\item \textbf{GloMoSim:}
SENSE (Sensor Network Simulator and Emulator)~\cite{ref206} is an open source, general purpose, discrete event, efficient, easy to use, and powerful network simulator. The main objective of designing this simulator is to support various requirements of the users by taking into consideration the extensibility, reusability, and scalability. The SENSE uses an object-oriented approach and J-Sim's simulator component based architecture. It supports the parallelization with a poor support for users.
SENSE provides a component-port model to release simulation models from interdependency. This allows independence among components and enables the extensibility and reusability. A level of reusability is obtained by the extensive use of C++ template, where a component is usually declared as a template class so that it handles different types of data. The designers improved the scalability by using the same packet in the memories of all sensors, assuming that the packet should not be changed. The core of the simulator still lacks a general set of models, routing protocols, and a wide variety of configuration templates for WSNs. In addition, a visualization tool, which can quickly discover the bugs during the simulation, is desirable.
+\fi
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \textbf{TOSSIM:}
TOSSIM~\cite{ref205,ref207,ref208} is a discrete event simulator for TinyOS based sensor networks, where the TinyOS application can be compiled on the TOSSIM framework, which runs on a computer rather than on the mote. This allow the users to test, debug, and analyze theirs algorithms in a controlled and repeatable environment. The users can check up their codes using debuggers and other development tools by executing them on the computer. TOSSIM is regarded as an emulator rather than a simulator because of its ability to simulate both software and hardware of the mote. TOSSIM is specially-designed for TinyOS applications run on Berkeley MICA Motes. TOSSIM needs to be improved to include four requirements: scalability, completeness, fidelity, and bridging, and to manage a large number of sensor nodes with different configurations to be scalable. For completeness, it has to capture behavior and interactions of a system at a different of levels. The simulator should capture behavior of a network with accurate timing of interactions on a mote and among motes for fidelity. The bridging requirement is satisfied due to executing the simulated code directly in a real mote. Two programming interfaces are supported by TOSSIM: Python and C++. The C++ interface transforms the code easily from one form to another. Python allows interaction with an executing simulation dynamically, like a powerful debugger. TOSSIM provides a high fidelity and scalable simulation of a complete TinyOS sensor network. It visualizes and interacts with executing simulations using GUI tool and TinyViz. The users can develop new visualizations and interfaces for TinyViz using simple plug-in model. The simulator's effectiveness for analyzing low-level protocols is decreased due to inaccuracies in the probabilistic bit error model. Moreover, TOSSIM is only supported by MICA motes platform.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\iffalse
\item \textbf{GTSNetS:}
%The stopped updating and maintaining the project since Oct, 2008 represents the main disadvantage of this simulator.
The tool is no longer maintained since October 2008.
+\fi
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
\end{enumerate}
-In this section, we investigated some simulation tools for WSNs. A large number of simulation tools are available for WSNs, with different characteristics and capabilities. Hence, it seems to be hard to decide which simulation tool to choose and which one is more appropriate for large-scale WSNs. Table~\ref{table:1} illustrates a comparison among some simulation tools~\cite{ref179}. According to table~\ref{table:1}, OMNeT++ seems to be a good candidate to be used as an evaluation tool for our proposed protocols in this dissertation. OMNeT++ is a free, extensible, and scalable simulator. It provides an easy-to-use interface using C++ language. Furthermore, several frameworks can be used with OMNeT++ such as INET, INETMANET, Veins, MiXiM, and Castalia to support various needs of users, such as mobility, Internet, vehicular, and sensor networks.
+In this section, we investigated some simulation tools for WSNs. A large number of simulation tools are available for WSNs, with different characteristics and capabilities. Hence, it seems hard to decide which simulation tool to choose and which one is more appropriate for large-scale WSNs. Table~\ref{table:1} illustrates a comparison among some simulation tools~\cite{ref179}. According to table~\ref{table:1}, OMNeT++ seems to be a good candidate to be used as an evaluation tool for our proposed protocols in this dissertation. OMNeT++ is a free, extensible, and scalable simulator. It provides an easy-to-use interface using C++ language. Furthermore, several frameworks can be used with OMNeT++ such as INET, INETMANET, Veins, MiXiM, and Castalia to support various needs of users, such as mobility, Internet, vehicular, and sensor networks.
\hline
- \textbf{GloMoSim} & Parsec (C-Based) with limited visual support & Open source with poor user support & Sensor network specific MAC and network protocols, mobility model & Good & Large-scale \\
+% \textbf{GloMoSim} & Parsec (C-Based) with limited visual support & Open source with poor user support & Sensor network specific MAC and network protocols, mobility model & Good & Large-scale \\
-\hline
+%\hline
- \textbf{SENSE} & C++ with good GUI support & Open source with poor user support & Energy models, battery models, mobility, modeling of physical environment & Excellent & Large-scale \\
+ %\textbf{SENSE} & C++ with good GUI support & Open source with poor user support & Energy models, battery models, mobility, modeling of physical environment & Excellent & Large-scale \\
-\hline
+%\hline
- \textbf{GTSNetS} & C++ with good user interface \& visual support & Open source with good user support & Energy model, battery model, accuracy model, model applications, mobility & Excellent & Very large-scale \\
+% \textbf{GTSNetS} & C++ with good user interface \& visual support & Open source with good user support & Energy model, battery model, accuracy model, model applications, mobility & Excellent & Very large-scale \\
\hline
\section{Optimization Solvers}
-
-Several optimization solvers exist, which are able to solve linear optimization problems. Linear programming~\cite{ref211} is a technique for determining the maximum or minimum of a linear function of non-negative variables subject to constraints expressed as linear equalities or inequalities. Linear programming is a special case of mathematical programming (mathematical optimization).
+\label{ch3:3}
+There are several optimization solvers to solve linear optimization problems. Linear programming~\cite{ref211} is a technique for determining the maximum or minimum of a linear function of non-negative variables subject to constraints expressed as linear equalities or inequalities. Linear programming is a special case of mathematical programming (mathematical optimization).
Linear programs are problems that can be expressed in canonical form as follows:
\begin{align} & \text{Maximize}~ (or ~\text{Minimize})~ && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{Subject to} && A \mathbf{x} \leq \mathbf{b} \\ & \text{and} && \mathbf{x} \ge \mathbf{0} \end{align}
where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients, A is a (known) matrix of coefficients, and $\left( \cdot \right) ^\mathrm{T}$ is the matrix transpose. The term to be maximized or minimized is called the objective function ($c^Tx$ in this case). The inequalities $Ax \leqslant b$ and $x \geqslant 0$ are the constraints which specify a convex polytope over which the objective function is to be optimized.
-In linear programming problem, if some or all of the unknown variables are restricted to be integers, it is called an integer programming (IP) problem.
+A linear programming problem, in which some or all of the unknown variables are restricted to be integers, it is called an integer programming (IP) problem.
%IP problems are a special cases of optimization problems, where the variables can only assume integer values. The IP problems are NP-hard. Mixed integer linear programming (MIP) problems are also special cases, where only some of the variables are restricted to integer values. The optimization problems with integer variables can also be linear or nonlinear, depending on the terms of their objective function and their constraints. However, the terms IP and MIP are almost always associated with problems that have linear features.
Linear optimization is used to solve different problems in various fields of study. It is applied for economic, business, and industry problems. For example, in the industry linear optimization is used to solve transportation, energy, telecommunications, and manufacturing problems.
%Linear optimization is succeeded in modeling different types of problems like planning, routing, scheduling, assignment, and design.
-Many approaches have been proposed to solve linear programming (IP or MIP) problems and they are classified into two main groups~\cite{ref221}:
+Many approaches have been proposed to solve linear programming (IP or Mixed Integer Programming (MIP)) problems and they are classified into two main groups~\cite{ref221}:
\begin{itemize}
-\item \textbf{Heuristic Optimization:} provides good solutions, but not necessarily optimal solutions, for problems that can not be solved efficiently and with acceptable computation time by classical optimization methods. There is no guarantee for the optimal solution. Examples of such approaches are genetic algorithms, swarm intelligence, and tabu search.
+\item \textbf{Heuristic Optimization:} provides good solutions, but not necessarily optimal solutions, for problems that can not be solved efficiently and with acceptable computation time by classical optimization methods. There is no guarantee for the optimal solution. Examples of such approaches are genetic algorithms, swarm intelligence, and tabu search \cite{ref237}.
-\item \textbf{Classical Optimization:} provides and guarantees optimal solutions for problems. Examples of such methods are zero-one enumeration algorithms and branch-and-bound algorithm, which are provided by linear optimization solvers.
+\item \textbf{Classical Optimization:} provides and guarantees optimal solutions for problems. Examples of such methods are zero-one enumeration algorithms and branch-and-bound algorithm, which are provided by linear optimization solvers \cite{ref221}.
\end{itemize}
B. Meindl and M. Templ~\cite{ref212} studied the efficiency of above optimization solvers. They used a set of instances of difficult optimization problems called the attacker problems in order to achieve a performance comparison of GLPK, lp$\_$solve, CLP, GUROBI, and CPLEX optimization solvers. They considered a total of 200 problem instances for this study, 100 of these problem instances are based on problems with two dimensions, and 100 problem instances are three-dimensional.
-Tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} compares the running times of the five linear program solvers to find solutions to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling.
+In tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} we report the result of their comparison the running times of the five linear program solvers to find solutions to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling.
\begin{table}[h]
-\caption{Total (in seconds) and scaled running times for 2-dimensional problem instances}
+\caption{Total (in seconds) and scaled running times for 2-dimensional problem instances (results of B. Meindl and M. Templ~\cite{ref212})}
\label{my-label1}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|c|c|c|c|c|c|}
\begin{table}[h]
-\caption{Total (in seconds) and scaled running times for 3-dimensional problem instances}
+\caption{Total (in seconds) and scaled running times for 3-dimensional problem instances (results of B. Meindl and M. Templ~\cite{ref212})}
\label{my-label2}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|c|c|c|c|c|c|}
\begin{table}[h]
-\caption{Total (in seconds) and scaled running times for all problems}
+\caption{Total (in seconds) and scaled running times for all problems (results of B. Meindl and M. Templ~\cite{ref212})}
\label{my-label3}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|c|c|c|c|c|c|}
\end{table}
-The results in tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} indicate that open source solvers perform worse than standard commercial solvers when applied to instances of the attacker’s problem. The GLPK outperforms the other free and open source solvers, but is still slower than CPLEX and GUROBI. We used the GLPK as an optimization solver in this dissertation to solve the proposed integer programs during the decision phase of the nodes. We motivate the use of the GLPK optimization solver for many reasons, including:
+The results in tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} indicate that open source solvers perform worse than standard commercial solvers when applied to instances of the attacker’s problem. The GLPK outperforms the other free and open source solvers, but is still slower than CPLEX and GUROBI. We have decided to use the GLPK as an optimization solver in this dissertation to solve the proposed integer programs during the decision phase of the nodes. We motivate the use of the GLPK optimization solver for many reasons, including:
\begin{enumerate} [(i)]
\item It is free and its installation is easy.
\item The GLPK does not lead to a fast solution of a large problem as in commercial optimization solvers, but it solves the smaller problems with a reasonable time. In this dissertation, we used a divide-and-conquer method to divide the large problem into smaller instances, and then the GLPK optimization solver is used to solve each of them.
-\item It is easy to use the GLPK solver and it is possible to call it's routines within a simulator.
+\item It is easy to use the GLPK solver and it is possible to call its routines within a simulator.
\item The GLPK comes with a stand-alone solver, a callable library, and the modeling language GMPL. The GMPL is compatible with AMPL and is extremely easy to learn.
\item Modeling language and solver can be used independently.
\item GUI is available for Windows, Mac OS X, and Linux. Java, Python, and Matlab interfaces are available.
\end{enumerate}
\section{Conclusion}
-\indent In this chapter, an overview of the evaluation tools for wireless sensor networks and optimization solvers has been presented. Major testbeds for wireless sensor network have been demonstrated. We have found that most researchers in the field of WSNs use the simulators to evaluate theirs works because they are free, easy to use, more flexible, and scalable for large WSNs. Several simulators for wireless sensor networks are described. The comparison among some types of network simulators show that OMNeT++ simulator is a good candidate to be used as performance evaluation tool to evaluate the efficiency of our protocols in this dissertation. This chapter also highlighted the optimization problem in WSNs and the most popular free and commercial linear optimization solvers. The commercial optimization solvers outperforms the free optimization solvers. GLPK has been chosen as a good candidate to solve the proposed optimization problems in this dissertation because it is free, easy to use, and better than some other free optimization solvers.
\ No newline at end of file
+\label{ch3:4}
+\indent In this chapter, an overview of the evaluation tools for wireless sensor networks and optimization solvers has been presented. Major testbeds for wireless sensor network have been demonstrated. We have found that most researchers in the field of WSNs use the simulators to evaluate theirs works because they are free, easy to use, more flexible, and scalable for large WSNs. Several simulators for wireless sensor networks are described. The comparison among some types of network simulators show that OMNeT++ simulator is a good candidate to be used as performance evaluation tool to evaluate the efficiency of our protocols in this dissertation. This chapter also highlightes the optimization problem in WSNs and the most popular free and commercial linear optimization solvers. The commercial optimization solvers outperform the free optimization solvers. GLPK has been chosen as a good candidate to solve the proposed optimization problems in this dissertation because it is free, easy to use, and better than some other free optimization solvers.
\ No newline at end of file
