Let us first the basic recalls of the~\cite{HLG09} article.


The  precise the context of video sensor network as represeted for instance 
in figure~\ref{fig:sn}.

\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{reseau.png}
\caption{SN with 10 sensor}\label{fig:sn}.
\end{center}
\end{figure} 


Let us give a formalisation of such a wideo 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
$L$ .  
This boolean information is stored as a  
matrix $A=(a_{il})_{i \in N, l \in L}$,
where 
$a_{il} = 
\left\{
    \begin{array}{rl}
      1 & \textrm{if $l$ starts with $i$ } \\
      -1 & \textrm{si $l$ ends width $i$ }  \\
      0 & \textrm{otherwise}
    \end{array}
  \right.$.


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 $i$ node, for the $h$ session. More precisely, we have 
  $$
\eta_{hi} = 
\left\{
    \begin{array}{rl}
      R_h & \textrm{si $i$ est $h$} \\
      -R_h & \textrm{si $i$ est le puits} \\
      0 & \textrm{sinon}
    \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 
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 initial energy of the $i$ node is  $B_i$.

The overall consumed powed 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. 
$

The objective is thus to find $R$, $x$, $P_s$  which minimize
 $q$ under the following set of constraints
\begin{enumerate}
\item $\sum_{l \in L }a_{il}x_{hl} = \eta_{hi},\forall h \in V, \forall i \in N  $
\item $ \sum_{h \in V}x_{hl} = y_l,\forall l \in L$
\item $\dfrac{\ln(\sigma^2/D_h)}{\gamma.P_{sh}^{2/3}} \leq R_h \forall h \in V$
\item \label{itm:q} $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, \forall i \in N$
\item $x_{hl}\geq0, \forall h \in V, \forall l \in L$
\item $R_h \geq 0, \forall h \in V$
\item $P_{sh} > 0,\forall h \in V$
\end{enumerate}


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 
$\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 
to solve such a problem.




\inputFrameb{Formulation simplifiée}{formalisationsimplifiee}