update by ali

[JournalMultiPeriods.git] / article.tex

diff --git a/article.tex b/article.tex
index 29e8cb96ab615ef20fe3933fdd716dcaa132fe3f..f8f7ec441051a3e382d5f8347f52eafbce31fe67 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -538,10 +538,64 @@ Zhou~\cite{Zhang05} proved that if  the transmission range fulfills the previous
 hypothesis, a complete coverage of  a convex area implies connectivity among the
 active nodes.
 
 hypothesis, a complete coverage of  a convex area implies connectivity among the
 active nodes.
 

-Instead  of working  with a  continuous coverage  area, we  make it  discrete by
-considering for each sensor a set of points called primary points. Consequently,
-we assume  that the sensing disk  defined by a sensor  is covered if  all of its
-primary points are covered. The choice of number and locations of primary points is the subject of another study not presented here.
+%Instead  of working  with a  continuous coverage  area, we  make it  discrete by considering for each sensor a set of points called primary points. Consequently, we assume  that the sensing disk  defined by a sensor  is covered if  all of its primary points are covered. The choice of number and locations of primary points is the subject of another study not presented here.
+
+
+\indent Instead of working with the coverage area, we consider for each sensor a set of points called primary points~\cite{idrees2014coverage}. We also assume that the sensing disk defined by a sensor is covered if all the primary points of this sensor are covered. By  knowing the  position (point  center: ($p_x,p_y$))  of  a wireless sensor node  and it's sensing range $R_s$,  we calculate the primary  points directly based on the proposed model. We  use these primary points (that can be increased or decreased if necessary)  as references to ensure that the monitored  region  of interest  is  covered by the selected  set  of sensors, instead of using all the points in the area. 
+We can  calculate  the positions of the selected primary
+points in the circle disk of the sensing range of a wireless sensor
+node (see Figure~\ref{fig1}) as follows:\\
+Assuming that the point center of a wireless sensor node is located at $(p_x,p_y)$, we can define up to 25 primary points $X_1$ to $X_{25}$.\\
+%$(p_x,p_y)$ = point center of wireless sensor node\\  
+$X_1=(p_x,p_y)$ \\ 
+$X_2=( p_x + R_s * (1), p_y + R_s * (0) )$\\           
+$X_3=( p_x + R_s * (-1), p_y + R_s * (0)) $\\
+$X_4=( p_x + R_s * (0), p_y + R_s * (1) )$\\
+$X_5=( p_x + R_s * (0), p_y + R_s * (-1 )) $\\
+$X_6= ( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (0)) $\\
+$X_7=( p_x + R_s *  (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
+$X_8=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
+$X_9=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
+$X_{10}=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
+$X_{11}=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
+$X_{12}=( p_x + R_s * (0), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
+$X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
+$X_{14}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (\frac{1}{2})) $\\
+$X_{15}=( p_x + R_s * (\frac{-\sqrt{3}}{2}), p_y + R_s * (\frac{1}{2})) $\\
+$X_{16}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (\frac{- 1}{2})) $\\
+$X_{17}=( p_x + R_s * (\frac{-\sqrt{3}}{2}), p_y + R_s * (\frac{- 1}{2})) $\\
+$X_{18}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (0) $\\
+$X_{19}=( p_x + R_s * (\frac{-\sqrt{3}}{2}), p_y + R_s * (0) $\\
+$X_{20}=( p_x + R_s * (0), p_y + R_s * (\frac{1}{2})) $\\
+$X_{21}=( p_x + R_s * (0), p_y + R_s * (-\frac{1}{2})) $\\
+$X_{22}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{\sqrt{3}}{2})) $\\
+$X_{23}=( p_x + R_s * (\frac{- 1}{2}), p_y + R_s * (\frac{\sqrt{3}}{2})) $\\
+$X_{24}=( p_x + R_s * (\frac{- 1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $\\
+$X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $.
+
+
+ 
+\begin{figure} %[h!]
+\centering
+ \begin{multicols}{2}
+\centering
+\includegraphics[scale=0.28]{fig21.pdf}\\~ (a)
+\includegraphics[scale=0.28]{principles13.pdf}\\~(c) 
+\hfill \hfill
+\includegraphics[scale=0.28]{fig25.pdf}\\~(e)
+\includegraphics[scale=0.28]{fig22.pdf}\\~(b)
+\hfill \hfill
+\includegraphics[scale=0.28]{fig24.pdf}\\~(d)
+\includegraphics[scale=0.28]{fig26.pdf}\\~(f)
+\end{multicols} 
+\caption{Wireless Sensor Node represented by (a) 5, (b) 9, (c) 13, (d) 17, (e) 21 and (f) 25 primary points respectively}
+\label{fig1}
+\end{figure}
+    
+
+
+
+

 
 %By  knowing the  position (point  center: ($p_x,p_y$))  of  a wireless
 %sensor node  and its $R_s$,  we calculate the primary  points directly
 
 %By  knowing the  position (point  center: ($p_x,p_y$))  of  a wireless
 %sensor node  and its $R_s$,  we calculate the primary  points directly


@@ -1077,10 +1131,35 @@ $W_{U}$ & $|P|^2$ \\
 \end{table}
   
 \textcolor{red}{Our first protocol based GLPK optimization solver is declined into  four versions: MuDiLCO-1,  MuDiLCO-3, MuDiLCO-5,
 \end{table}
   
 \textcolor{red}{Our first protocol based GLPK optimization solver is declined into  four versions: MuDiLCO-1,  MuDiLCO-3, MuDiLCO-5,

-and  MuDiLCO-7, corresponding  respectively to  $T=1,3,5,7$ ($T$  the  number of
-rounds in one sensing period). }
-%The second protocol based GA is declined into  four versions: GA-MuDiLCO-1,  GA-MuDiLCO-3, GA-MuDiLCO-5,
-%and  GA-MuDiLCO-7 for the same reason of the first protocol. After extensive experiments, we chose the dedicated values for the parameters $P_c$, $P_m$, and $S_{pop}$ because they gave the best results}. 
+and  MuDiLCO-7, corresponding  respectively to  $T=1,3,5,7$ ($T$  the  number of rounds in one sensing period).
+The second protocol based  based GLPK optimization solver with time limit is declined into  four versions: TL-MuDiLCO-1,  TL-MuDiLCO-3, TL-MuDiLCO-5, and  TL-MuDiLCO-7. Table \ref{tl} shows time limit values for TL-MuDiLCO protocol versions. After extensive experiments, we chose the values that explained in Table \ref{tl} because they gave the best results. In Table \ref{tl}, "NO" refers to apply the GLPK solver without time limit because we did not find improvement on the results of MuDiLCO protocol with the time limit}. 
+
+\begin{table}[ht]
+\caption{Time limit values for TL-MuDiLCO protocol versions }
+\centering
+\begin{tabular}{|c|c|c|c|c|}
+ \hline
+ WSN size & TL-MuDiLCO-1 & TL-MuDiLCO-3 & TL-MuDiLCO-5 & TL-MuDiLCO-7 \\ [0.5ex]
+\hline
+ 50 & NO & NO & NO & NO \\
+ \hline
+100 & NO & NO & NO & NO \\
+\hline
+150 & NO & 0.006 & NO & 0.03 \\
+\hline
+200 & 0.0035 & 0.0094 & 0.020 & 0.06 \\
+ \hline
+ 250 & 0.0055 & 0.013 & 0.03 & 0.08 \\
+ \hline
+\end{tabular}
+
+\label{tl}
+
+\end{table}
+
+
+
+

  In  the following, we will make comparisons with
 two other methods. The first method, called DESK and proposed by \cite{ChinhVu},
 is  a   full  distributed  coverage   algorithm.   The  second   method,  called
  In  the following, we will make comparisons with
 two other methods. The first method, called DESK and proposed by \cite{ChinhVu},
 is  a   full  distributed  coverage   algorithm.   The  second   method,  called


@@ -1267,6 +1346,54 @@ indicate the energy consumed by the whole network in round $t$.
 
 \end{enumerate}
 
 
 \end{enumerate}
 

+\subsection{Performance Analysis for Different Number of Primary Points}
+\label{ch4:sec:04:06}
+
+In this section, we study the performance of MuDiLCO-1 approach for different numbers of primary points. The objective of this comparison is to select the suitable primary point model to be used by a MuDiLCO protocol. In this comparison, MuDiLCO-1 protocol is used with five models, which are called Model-5 (it uses 5 primary points), Model-9, Model-13, Model-17, and Model-21. 
+
+
+%\begin{enumerate}[i)]
+
+%\item {{\bf Coverage Ratio}}
+\subsubsection{Coverage Ratio} 
+
+Figure~\ref{Figures/ch4/R2/CR} shows the average coverage ratio for 150 deployed nodes.  
+\parskip 0pt    
+\begin{figure}[h!]
+\centering
+ \includegraphics[scale=0.5] {R2/CR.pdf} 
+\caption{Coverage ratio for 150 deployed nodes}
+\label{Figures/ch4/R2/CR}
+\end{figure} 
+As can be seen in Figure~\ref{Figures/ch4/R2/CR}, at the beginning the models which use a larger number of primary points provide slightly better coverage ratios, but latter they are the worst. 
+%Moreover, when the number of periods increases, coverage ratio produced by Model-9, Model-13, Model-17, and Model-21 decreases in comparison with Model-5 due to a larger time computation for the decision process for larger number of primary points.
+Moreover, when the number of periods increases, coverage ratio produced by all models decrease, but Model-5 is the one with the slowest decrease due to a smaller time computation of decision process for a smaller number of primary points. 
+As shown in Figure ~\ref{Figures/ch4/R2/CR}, coverage ratio decreases when the number of periods increases due to dead nodes. Model-5 is slightly more efficient than other models, because it offers a good coverage ratio for a larger number of periods in comparison with other models.
+
+
+%\item {{\bf Network Lifetime}}
+\subsubsection{Network Lifetime}
+
+Finally, we study the effect of increasing the primary points on the lifetime of the network. 
+%In Figure~\ref{Figures/ch4/R2/LT95} and in Figure~\ref{Figures/ch4/R2/LT50}, network lifetime, $Lifetime95$ and $Lifetime50$ respectively, are illustrated for different network sizes. 
+As highlighted by Figures~\ref{Figures/ch4/R2/LT}(a) and \ref{Figures/ch4/R2/LT}(b), the network lifetime obviously increases when the size of the network increases, with  Model-5 that leads to the larger lifetime improvement. 
+
+\begin{figure}[h!]
+\centering
+\centering
+\includegraphics[scale=0.5]{R2/LT95.pdf}\\~ ~ ~ ~ ~(a) \\
+
+\includegraphics[scale=0.5]{R2/LT50.pdf}\\~ ~ ~ ~ ~(b)
+
+\caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$}
+  \label{Figures/ch4/R2/LT}
+\end{figure}
+
+Comparison shows that Model-5, which uses less number of primary points, is the best one because it is less energy consuming during the network lifetime. It is also the better one from the point of view of coverage ratio. Our proposed Model-5 efficiently prolongs the network lifetime with a good coverage ratio in comparison with other models. Therefore, we have chosen Model-5 for all the experiments presented thereafter. 
+
+%\end{enumerate}
+
+

 \subsection{Results and analysis}
 
 \subsubsection{Coverage ratio} 
 \subsection{Results and analysis}
 
 \subsubsection{Coverage ratio} 


@@ -1290,7 +1417,7 @@ rounds, and thus should extend the network lifetime.
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

- \includegraphics[scale=0.5] {R/CR.pdf} 
+ \includegraphics[scale=0.5] {F/CR.pdf} 

 \caption{Average coverage ratio for 150 deployed nodes}
 \label{fig3}
 \end{figure} 
 \caption{Average coverage ratio for 150 deployed nodes}
 \label{fig3}
 \end{figure} 


@@ -1316,7 +1443,7 @@ Obviously, in that case DESK  and GAF have less active nodes, since  they have a
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

-\includegraphics[scale=0.5]{R/ASR.pdf}  
+\includegraphics[scale=0.5]{F/ASR.pdf}  

 \caption{Active sensors ratio for 150 deployed nodes}
 \label{fig4}
 \end{figure} 
 \caption{Active sensors ratio for 150 deployed nodes}
 \label{fig4}
 \end{figure} 


@@ -1340,7 +1467,7 @@ Let us emphasize that the  simulation continues as long as a network  in a subre
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

-\includegraphics[scale=0.5]{R/SR.pdf} 
+\includegraphics[scale=0.5]{F/SR.pdf} 

 \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes }
 \label{fig6}
 \end{figure} 
 \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes }
 \label{fig6}
 \end{figure} 


@@ -1356,9 +1483,9 @@ network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$.
 \begin{figure}[h!]
   \centering
   \begin{tabular}{cl}
 \begin{figure}[h!]
   \centering
   \begin{tabular}{cl}

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{R/EC95.pdf}} & (a) \\
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC95.pdf}} & (a) \\

     \verb+ + \\
     \verb+ + \\

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{R/EC50.pdf}} & (b)
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC50.pdf}} & (b)

   \end{tabular}
   \caption{Energy consumption for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \end{tabular}
   \caption{Energy consumption for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}


@@ -1376,7 +1503,7 @@ versions. This is  easy to understand since the bigger the  number of rounds and
 
 
 \subsubsection{Execution time}
 
 
 \subsubsection{Execution time}

-
+\label{et}

 We observe  the impact of the  network size and of  the number of  rounds on the
 computation  time.   Figure~\ref{fig77} gives  the  average  execution times  in
 seconds (needed to solve optimization problem) for different values of $T$. The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is  employed to generate the Mixed Integer Linear Program instance  in a  standard format, which  is then read  and solved  by the optimization solver  GLPK (GNU  linear Programming Kit  available in  the public domain) \cite{glpk} through a Branch-and-Bound method. The
 We observe  the impact of the  network size and of  the number of  rounds on the
 computation  time.   Figure~\ref{fig77} gives  the  average  execution times  in
 seconds (needed to solve optimization problem) for different values of $T$. The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is  employed to generate the Mixed Integer Linear Program instance  in a  standard format, which  is then read  and solved  by the optimization solver  GLPK (GNU  linear Programming Kit  available in  the public domain) \cite{glpk} through a Branch-and-Bound method. The


@@ -1390,7 +1517,7 @@ for different network sizes.
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

-\includegraphics[scale=0.5]{R/T.pdf}  
+\includegraphics[scale=0.5]{F/T.pdf}  

 \caption{Execution Time (in seconds)}
 \label{fig77}
 \end{figure} 
 \caption{Execution Time (in seconds)}
 \label{fig77}
 \end{figure} 


@@ -1429,9 +1556,9 @@ linked.
 \begin{figure}[t!]
   \centering
   \begin{tabular}{cl}
 \begin{figure}[t!]
   \centering
   \begin{tabular}{cl}

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{R/LT95.pdf}} & (a) \\
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/LT95.pdf}} & (a) \\

     \verb+ + \\
     \verb+ + \\

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{R/LT50.pdf}} & (b)
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/LT50.pdf}} & (b)

   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}