From 17a131a2d00611e1582103549a9c7d2bac2be03e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Wed, 4 Dec 2013 20:49:06 +0100 Subject: [PATCH 1/1] correction HLG --- IWCMC14/HLG.tex | 66 +++++++++++++++++++++++++++-------------- IWCMC14/argmin.tex | 2 +- IWCMC14/convergence.tex | 16 +++++----- IWCMC14/convexity.tex | 31 ++++++++++++++----- IWCMC14/main.tex | 6 ++-- 5 files changed, 78 insertions(+), 43 deletions(-) diff --git a/IWCMC14/HLG.tex b/IWCMC14/HLG.tex index ff12b04..7daf581 100644 --- a/IWCMC14/HLG.tex +++ b/IWCMC14/HLG.tex @@ -1,24 +1,30 @@ -\begin{figure} +\begin{figure*} \begin{center} -\includegraphics[scale=0.3]{reseau.png} +\includegraphics[scale=0.2]{SensorNetwork.png} \begin{scriptsize} -An example of a sensor network ofsize 10. All nodes are video sensor -except the 5 and the 9 one which is the sink. -\JFC{reprendre la figure, trouver un autre titre} -\end{scriptsize} -\caption{SN with 10 sensor}\label{fig:sn}. +An example of a sensor network of size 10. +All nodes are video sensors (depicted as small discs) +except the 9 one which is the sink (depicted as a rectangle). +Large lircles represent the maximum +transmission range which is set to 20 in a square region which is +$50 m \times 50 m$. +\end{scriptsize} +\caption{Illustration of a SN of size 10}\label{fig:sn}. \end{center} -\end{figure} +\end{figure*} Let us first recall the basics of the~\cite{HLG09} article. The video sensor network is memorized as a connected non oriented -oriented labelled graph. +graph. In this one, the nodes, in a set $N$, are sensors, links, or the sink. Furthermore, there is an edge from $i$ to $j$ if $i$ can -send a message to $j$. The set of all edges is further denoted as +send a message to $j$, \textit{i. e.}, the distance betwween +$i$ and $j$ is less than a given maximum +transmission range. +All the possible edges are stored into a sequence $L$. Figure~\ref{fig:sn} gives an example of such a network. @@ -27,30 +33,44 @@ matrix $A=(a_{il})_{i \in N, l \in L}$, where $a_{il}$ is 1 if $l$ starts with $i$, is -1 if $l$ ends width $i$ and 0 otherwise. - +Moreover, the outgoing links(resp. the incoming links) are represented +with the $A^+$ matrix (res. with the $A^-$ matrix), whose elements are defined: +$a_{il}^+$ (resp. $a_{il}^-$) is 1 if the link $l$ is an outgoing link from $i$ +(resp an incoming link into $i$) and 0 otherwise. Let $V \subset N $ be the set of the video sensors of $N$. Let thus $R_h$, $R_h \geq 0$, be the encoding rate of video sensor $h$, $h \in V$. -Let $\eta_{hi}$ be the production rate of the node $i$, -for the session initiated by $h$. More precisely, we have +Let $\eta_{hi}$ be the rate inside the node $i$ +of the production that has beeninitiated by $h$. More precisely, we have $ \eta_{hi}$ is equal to $ R_h$ if $i$ is $h$, is equal to $-R_h$ if $i$ is the sink, and $0$ otherwise. -We are then left to focus on the flows in this network. +Let us focus on the flows in this network. Let $x_{hl}$, $x_{hl}\geq 0$, be the flow inside the edge $l$ that -issued from the $h$ session and +issued from the node $h$ and let $y_l = \sum_{h \in V}x_{hl} $ the sum of all the flows inside $l$. Thus, what is produced inside the $i^{th}$ sensor for session $h$ is $ \eta_{hi} = \sum_{l \in L }a_{il}x_{hl} $. The encoding power of the $i$ node is $P_{si}$, $P_{si} > 0$. - -The distortion is bounded $\sigma^2 e^{-\gamma . R_h.P_{sh}^{}2/3} \leq D_h$. - +The emmission distortion of the $i$ node is +$\sigma^2 e^{-\gamma . R_i.P_{si}^{}2/3}$ +where $\sigma^2$ is the average input variance and +$\gamma$ is the encoding efficiency coefficient. +This distortion +is bounded by a constant value $D_h$. The initial energy of the $i$ node is $B_i$. - +The transmission consumed power of node $i$ is +$P_{ti} = c_l^s.y_l$ where $c_l^s$ is the transmission energy +consumption cost of link $l$, $l\in L$. This cost is defined +as foolows: $c_l^s = \alpha +\beta.d_l^{n_p} $ wehre +$d_l$ represents the distance of the link $l$, +$\alpha$, $\beta$, and $n_p$ are constant. +The reception consumed power of node $i$ is +$P_{ri} = c^r \sum_{l \in L } a_{il}^-.y_l$ +where $c^r$ is a reception energy consumption cost. The overall consumed power of the $i$ node is $P_{si}+ P_{ti} + P_{ri}= P_{si}+ \sum_{l \in L}a_{il}^{+}.c^s_l.y_l + @@ -94,7 +114,7 @@ by the objective of reducing \label{eq:obj2} \end{equation} where $\delta$ is a regularisation factor. -This indeed introduces quadratic fonctions on variables $x_{hl}$ and +This indeed introduces quadratic functions on variables $x_{hl}$ and $R_{h}$ and makes some of the functions strictly convex. The authors then apply a classical dual based approach with Lagrange multiplier @@ -130,7 +150,7 @@ c^r. a_{il}^{-} ) \right.\\ \end{equation} The proposed algorithm iteratively computes the following variables -untill the variation of the dual function is less than a given threshold. +until the variation of the dual function is less than a given threshold. \begin{enumerate} \item $ u_{hi}^{(k+1)} = u_{hi}^{(k)} - \theta^{(k)}. \left( \eta_{hi}^{(k)} - \sum_{l \in L }a_{il}x_{hl}^{(k)} \right) $ @@ -139,7 +159,7 @@ $v_{h}^{(k+1)}= \max\left\{0,v_{h}^{(k)} - \theta^{(k)}.\left( R_h^{(k)} - \dfr \item $\begin{array}{l} \lambda_{i}^{(k+1)} = \max\left\{0, \lambda_{i}^{(k)} - \theta^{(k)}.\left( - q^{(k)}.B_i \right. \left.\\ + q^{(k)}.B_i \right. \right.\\ \qquad\qquad\qquad -\sum_{l \in L}a_{il}^{+}.c^s_l.\left( \sum_{h \in V}x_{hl}^{(k)} \right) \\ \qquad\qquad\qquad - \left.\left. \sum_{l \in L} a_{il}^{-}.c^r.\left( \sum_{h \in V}x_{hl}^{(k)} \right) - P_{si}^{(k)} \right) \right\} \end{array} @@ -168,7 +188,7 @@ P_{sh}^{(k)} = \arg \min_{p > 0} \left( -v_h^{(k)}.\dfrac{\ln(\sigma^2/D_h)}{\gamma p ^{2/3}} + \lambda_h^{(k)}p +v_h^{(k)}.\dfrac{\ln(\sigma^2/D_h)}{\gamma p^{2/3}} + \lambda_h^{(k)}p \right) $ diff --git a/IWCMC14/argmin.tex b/IWCMC14/argmin.tex index 0f64780..47eae44 100644 --- a/IWCMC14/argmin.tex +++ b/IWCMC14/argmin.tex @@ -1,5 +1,5 @@ The approach detailed previously requires to compute -the variable that minimizes four convex fonctions +the variable that minimizes four convex functions on constraint domains, one for each primal variable $q_i$, $P_{sh}$, $R_h$, and $x_{hl}$, Among state of the art for this optimization step, there is diff --git a/IWCMC14/convergence.tex b/IWCMC14/convergence.tex index ea4d4c2..13b3b2d 100644 --- a/IWCMC14/convergence.tex +++ b/IWCMC14/convergence.tex @@ -1,8 +1,8 @@ -Let us first have a discussion on the stop criterion of the citted algorithm. +Let us first have a discussion on the stop criterion of the cited algorithm. We claim that even if the variation of the dual function is less than a given -threeshold, this does not ensure that the lifetime has been maximized. +threshold, this does not ensure that the lifetime has been maximized. Minimizing a function on a multiple domain (as the dual function) -may indeed easilly fall into a local trap because some of introduced +may indeed easily fall into a local trap because some of introduced variables may lead to uniformity of the output. \begin{figure} @@ -11,7 +11,7 @@ variables may lead to uniformity of the output. \label{fig:convergence:scatterplot} \end{figure} -Experimentations have indeed shown that even if the dual +Experiments have indeed shown that even if the dual function seems to be constant (variations between two evaluations of this one is less than $10^{-5}$) not all the $q_i$ have the same value. @@ -20,15 +20,15 @@ a scatter plot. The maximum amplitude rate of the sequence of $q_i$ --which is $\frac{\max_{i \in N} q_i} {\min_{i \in N}q_i}-1$-- -is represented in $y$-coordonates +is represented in $y$-coordinate with respect to the -value of the threeshold for dual function that is represented in -$x$-coordonates. +value of the threshold for dual function that is represented in +$x$-coordinate. This figure shows that a very small threshold is a necessary condition, but not a sufficient criteria to observe convergence of $q_i$. In the following, we consider the system are $\epsilon$-stable if both -maximum amplitude rate and the dual function are less than a threeshold +maximum amplitude rate and the dual function are less than a threshold $\epsilon$. diff --git a/IWCMC14/convexity.tex b/IWCMC14/convexity.tex index 9ca786a..a663986 100644 --- a/IWCMC14/convexity.tex +++ b/IWCMC14/convexity.tex @@ -8,25 +8,40 @@ P_{sh}^{(k)} v_h^{(k)}.\dfrac{\ln(\sigma^2/D_h)}{\gamma p ^{2/3}} + \lambda_h^{(k)}p \right) $. -The function inside the $\arg \min$ is stricly convex if and only if -$\lamda_h$ is not null. This asymptotic configuration may arrise due to +The function inside the $\arg \min$ is strictly convex if and only if +$\lambda_h$ is not null. This asymptotic configuration may arise due to the definition of $\lambda_i$. Worth, in this case, the function is -stricly decreasing and the minimal value is obtained when $p$ is the infinity. +strictly decreasing and the minimal value is obtained when $p$ is the infinity. To prevent this configuration, we replace the objective function given in equation~(\ref{eq:obj2}) by \begin{equation} \sum_{i \in N }q_i^2 + -\delta_x \sum_{h \in V, l \in L } .x_{hl}^2 -+ \delta_r\sum_{h \in V }\delta.R_{h}^2 -+ \delta_p\sum_{h \in V }\delta.P_{sh}^{\frac{8}{3}}. +\delta_x \sum_{h \in V, l \in L } x_{hl}^2 ++ \delta_r\sum_{h \in V }R_{h}^2 ++ \delta_p\sum_{h \in V }P_{sh}^{\frac{8}{3}}. \label{eq:obj2} \end{equation} In this equation we have first introduced new regularisation factors (namely $\delta_x$, $\delta_r$, and $\delta_p$) instead of the sole $\delta$. This allows to further study the influence of each modification separately. -Next, the introduction of the rationnal exponent is motivated by the goal of -providing a stricly convex function. +Next, the introduction of the rational exponent is motivated by the goal of +providing a strictly convex function. + +Let us now verify that the induced function is convex. +Let $f: \R^{+*} \rightarrow \R$ such that $ +f(p)= v_h.\dfrac{\ln(\sigma^2/D_h)}{\gamma p^{2/3}} + \lambda_h p ++ \delta_p p^{8/3}$. This function is differentiable and +for any $x \in \R^{+*}$ and we have +$$ +\begin{array}{rcl} +f'(p) &=& -2/3.v_h.\dfrac{\ln(\sigma^2/D_h)}{\gamma p^{5/3}} + \lambda_h + +8/3.\delta_p p^{5/3} \\ +&& \dfrac {8/3.\delta_p p^{10/3} + \lambda_h p^{5/3} -2/3.v_h\ln(\sigma^2/D_h) }{p^{5/3}} +\end{array} +$$ +which is positive if and only if the numerator is. +Provided $p^{5/3}$ is replaced by $P$, we have a quadratic function which is strictly convex, for any value of $\lambda_h$. \ No newline at end of file diff --git a/IWCMC14/main.tex b/IWCMC14/main.tex index b887bc2..67018d3 100644 --- a/IWCMC14/main.tex +++ b/IWCMC14/main.tex @@ -90,15 +90,15 @@ \input{convexity} \JFC{On doit parler du probleme pour Ps} -\subsection{Directly retreiving the argmin} +\subsection{Directly retrieving the argmin} \input{argmin} -\subsection{Fault-Tolerence Considerations} +\subsection{Fault-Tolerance Considerations} + -\ \section{Discussion and Future Work} -- 2.39.5