avant corrections

[desynchronisation-controle.git] / IWCMC14 / HLG.tex

diff --git a/IWCMC14/HLG.tex b/IWCMC14/HLG.tex
index 9833667136aa620b6ad7da2aaf897c4ce0b4a079..456b3693db23dd590767c1a42d423efb813debaa 100644 (file)
--- a/IWCMC14/HLG.tex
+++ b/IWCMC14/HLG.tex
@@ -1,7 +1,7 @@
 Let us first the basic recalls of the~\cite{HLG09} article.
 
 
 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}
 in figure~\ref{fig:sn}.
 
 \begin{figure}


@@ -12,15 +12,15 @@ in figure~\ref{fig:sn}.
 \end{figure} 
 
 
 \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.
 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}$,
 $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}
 \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 
     \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} $.
 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 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. 
 $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 
 
 
 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$$
 
 $\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.
 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