quelques modifs

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

\begin{figure*}
\begin{center}

\includegraphics[scale=0.2]{SensorNetwork.png}
\begin{scriptsize}

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 Sensor Network of size 10}\label{fig:sn}.
\end{center}
\end{figure*} 

Let us first recall  the basics of the~\cite{HLG09} article.
The video sensor network is memorized as a connected non oriented 
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$, \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.
  
This link information is stored as a  
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  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.
  
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 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 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} $ where 
$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 + 
\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 maximizes
the network lifetime $T_{\textit{net}}$, or equivalently which minimizes
$q=1/{T_{\textit{net}}}$. 
Let $B_i$ is the initial energy in node $i$.
One have the equivalent objective to find $R$, $x$, $P_s$ which minimizes
$q^2$
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 + 
c^r.\sum_{l \in L} a_{il}^{-}.y_l \leq q.B_i, \forall i \in N$
\item $\sum_{i \in N} a_{il}q_i = 0, \forall l \in L$ 
\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 this optimizing goal 
a local optimisation, the problem is translated into an 
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:
$$
\begin{array}{l}
P_{si}+ \sum_{l \in L}a_{il}^{+}.c^s_l.\left( \sum_{h \in V}x_{hl} \right) \\
\qquad + 
 \sum_{l \in L} a_{il}^{-}.c^r.\left( \sum_{h \in V}x_{hl} \right) \leq q_i.B_i, \forall i \in N
\end{array}
$$
and where the following constraint is added
$$ $q_i > 0, \forall i \in N  $$



They thus replace the objective of reducing
$\sum_{i \in N }q_i^2$
by the objective of reducing 
\begin{equation}
\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 
\label{eq:obj2}
\end{equation}
where $\delta$ is a regularisation factor.
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 
to solve such a problem~\cite{}.
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$.

\begin{equation}
\begin{array}{l}
L(R,x,P_{s},q,u,v,\lambda,w)=\\ 
\sum_{i \in N} q_i^2 + q_i.  \left(
\sum_{l \in L } a_{il}w_l^{(k)}-
\lambda_iB_i
\right)\\
+ \sum_{h \in V}
v_h.\dfrac{\ln(\sigma^2/D_h)}{\gamma P_{sh} ^{2/3}} + \lambda_h P_{sh}\\
+ \sum_{h \in V} \sum_{l\in L}
\left(
\delta.x_{hl}^2  \right.\\
\qquad \qquad + x_{hl}.
\sum_{i \in N} \left( 
\lambda_{i}.(c^s_l.a_{il}^{+} +
c^r. a_{il}^{-} ) \right.\\
\qquad \qquad\qquad \qquad +
\left.\left. u_{hi} a_{il}
\right)
\right)\\
 + \sum_{h \in V}
\delta R_{h}^2 
-v_h.R_{h} - \sum_{i \in N} u_{hi}\eta_{hi}
\end{array}
\end{equation}

The proposed algorithm iteratively computes the following variables 
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) $
\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}{l}
   \lambda_{i}^{(k+1)} = \max\left\{0, \lambda_{i}^{(k)} - \theta^{(k)}.\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}
$

\item 
$w_l^{(k+1)} = w_l^{(k+1)} +  \theta^{(k)}. \left( \sum_{i \in N} a_{il}.q_i^{(k)} \right)$


\item 
$\theta^{(k)} = \omega / t^{1/2}$

 \item 
$q_i^{(k)} = \arg\min_{q_i>0}
\left(
q_i^2 + q_i. 
\left(
\sum_{l \in L } a_{il}w_l^{(k)}-
\lambda_i^{(k)}B_i
\right)
\right)$

\item \label{item:psh} 
$
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)} =
\begin{array}{l}
\arg \min_{x \geq 0}
\left(
\delta.x^2  \right.\\
\qquad \qquad + x.
\sum_{i \in N} \left( 
\lambda_{i}^{(k)}.(c^s_l.a_{il}^{+} +
c^r. a_{il}^{-} ) \right.\\
\qquad \qquad\qquad \qquad +
\left.\left. u_{hi}^{(k)} a_{il}
\right)
\right)
\end{array}
$
\end{enumerate}
where the first four elements are dual variable and the last four ones are 
primal ones.