From 921131116b4d4b4dea91fb53e126383821fe30de Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Thu, 28 Nov 2013 20:53:44 +0100 Subject: [PATCH] avant corrections --- IWCMC14/HLG.tex | 105 +++++++++++++++++++++++++++++++++++++++-------- IWCMC14/main.tex | 14 ++++--- 2 files changed, 97 insertions(+), 22 deletions(-) diff --git a/IWCMC14/HLG.tex b/IWCMC14/HLG.tex index 9833667..456b369 100644 --- a/IWCMC14/HLG.tex +++ b/IWCMC14/HLG.tex @@ -1,7 +1,7 @@ Let us first the basic recalls of the~\cite{HLG09} article. -The precise the context of video sensor network as represeted for instance +The precise the context of video sensor network as represented for instance in figure~\ref{fig:sn}. \begin{figure} @@ -12,15 +12,15 @@ in figure~\ref{fig:sn}. \end{figure} -Let us give a formalisation of such a wideo network sensor. +Let us give a formalisation of such a video network sensor. We start with the flow formalising: The video sensor network is represented as a strongly connected oriented labelled graph. In this one, the nodes, in a set $N$ are sensors, links, or the sink. -Furtheremore, there is an edge from $i$ to $j$ if $i$ can -send a mesage to $j$. The set of all edges is further denoted as +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 $L$ . This boolean information is stored as a matrix $A=(a_{il})_{i \in N, l \in L}$, @@ -42,15 +42,15 @@ Let $\eta_{hi}$ be the production rate of the $i$ node, for the $h$ session. Mo \eta_{hi} = \left\{ \begin{array}{rl} - R_h & \textrm{si $i$ est $h$} \\ - -R_h & \textrm{si $i$ est le puits} \\ - 0 & \textrm{sinon} + R_h & \textrm{if $i$ is $h$} \\ + -R_h & \textrm{if $i$ is the sink} \\ + 0 & \textrm{otherwise} \end{array} \right.$$ We are then left to 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$ sesssion and +issued from the $h$ session 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} $. @@ -62,7 +62,7 @@ The distortion is bounded $\sigma^2 e^{-\gamma . R_h.P_{sh}^{}2/3} \leq D_h$. The initial energy of the $i$ node is $B_i$. -The overall consumed powed of the $i$ node is +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 + \sum_{l \in L} a_{il}^{-}.c^r.y_l \leq q.B_i. @@ -83,22 +83,95 @@ The objective is thus to find $R$, $x$, $P_s$ which minimize To achieve a local optimisation, the problem is translated into an -equivalent one: - -\begin{itemize} -The objective is thus to find $R$, $x$, $P_s$ which minimize +equivalent one: find $R$, $x$, $P_s$ which minimize $\sum_{i \in N }q_i^2$ with the same set of constraints, but item \ref{itm:q}, which is replaced by: $$P_{si}+ \sum_{l \in L}a_{il}^{+}.c^s_l.\left( \sum_{h \in V}x_{hl} \right) + \sum_{l \in L} a_{il}^{-}.c^r.\left( \sum_{h \in V}x_{hl} \right) \leq q.B_i, \forall i \in N$$ -\JFC{Vérifier l'inéquation précédente} -The authors then aplly a dual based approach with Lagrange multiplier +The authors then apply a dual based approach with Lagrange multiplier to solve such a problem. +They first introduce dual variables +$u_{hi}$, $v_{h}$, $\lambda_{i}$, and $w_l$ for any +$h \in V$,$ i \in N$, and $l \in L$. +They next replace the objective of reducing $\sum_{i \in N }q_i^2$ +by the objective of reducing +$$ +\sum_{i \in N }q_i^2 + +\sum_{h \in V, l \in L } \delta.x_{hl}^2 ++ \sum_{h \in V }\delta.R_{h}^2 +$$ +where $\delta$ is a \JFC{ formalisation} factor. +This allows indeed to get convex functions whose minimum value is unique. + +The proposed algorithm iteratively computes the following variables +\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) $ +\item +$v_{h}^{(k+1)}= \max\left\{0,v_{h}^{(k)} - \theta^{(k)}.\left( R_h^{(k)} - \dfrac{\ln(\sigma^2/D_h)}{\gamma.(P_{sh}^{(k)})^{2/3}} \right)\right\}$ +\item + $\begin{array}{rcl} + \lambda_{i}^{(k+1)} = \lambda_{i}^{(k)} - \theta^{(k)}&.&\left( + q^{(k)}.B_i - + \sum_{l \in L}a_{il}^{+}.c^s_l.\left( \sum_{h \in V}x_{hl}^{(k)} \right) \right. \\ + && - \left. \sum_{l \in L} a_{il}^{-}.c^r.\left( \sum_{h \in V}x_{hl}^{(k)} \right) - P_{si}^{(k)} \right) +\end{array} +$ +\item +$w_l^{(k+1)} = w_l^{(k+1)} + \theta^{(k)}. \left( \sum_{i \in N} a_{il}.q_i^{(k)} \right)$ -\inputFrameb{Formulation simplifiée}{formalisationsimplifiee} \ No newline at end of file +\item +$\theta^{(k)} = \omega / t^{1/2}$ + + \item +$q_i^{(k)} = \arg\min_{q_i>0} +\left( +q^2 + q. +\left( +\sum_{l \in L } a_{il}w_l^{(k)}- +\lambda_i^{(k)}B_i +\right) +\right)$ + +\item +$ +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 +\right) +$ + +\item +$ +R_h^{(k)} += +\arg \min_{r \geq 0 } +\left( +\delta r^2 +-v_h^{(k)}.r - \sum_{i \in N} u_{hi}^{(k)} \eta_{hi} +\right) +$ +\item +$ +x_{hl}^{(k)} = +\arg \min_{x \geq 0} +\left( +\delta.x^2 + x. +\sum_{i \in N} \left( +\lambda_{i}^{(k)}.(c^s_l.a_{il}^{+} + +c^r. a_{il}^{-} )+ + u_{hi}^{(k)} a_{il} +\right) +\right) + $ +\end{enumerate} +where the first four elements are dual variable and the last four ones are +primal ones \ No newline at end of file diff --git a/IWCMC14/main.tex b/IWCMC14/main.tex index 52404b8..f77d4eb 100644 --- a/IWCMC14/main.tex +++ b/IWCMC14/main.tex @@ -2,8 +2,8 @@ \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[english]{babel} -%\usepackage{ntheorem} \usepackage{amsmath,amssymb} + \usepackage{epsfig,psfrag} \usepackage{graphics,graphicx} \usepackage{color} @@ -29,14 +29,14 @@ FEMTO-ST Institute, UMR 6174 CNRS\\ DISC Department, University of Franche-Comt\'{e}\\ Belfort, France\\ - \{jean-francois.couchot, christophe.guyeux, jacques.bahi\}@femto-st.fr\\ + \{jean-francois.couchot, ahmed.mostefaoui\}@univ-fcomte.fr\\ } -\input{macroE} -\title{} + +\title{ } @@ -52,11 +52,13 @@ \begin{abstract} + \end{abstract} \begin{IEEEkeywords} + \end{IEEEkeywords} @@ -67,7 +69,7 @@ \section{Introduction} -\input{intro} +%\input{intro} @@ -89,7 +91,7 @@ \section{Discussion and Future Work} -\input{conclusion} +%\input{conclusion} %\bibliographystyle{compj} -- 2.39.5