X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/desynchronisation-controle.git/blobdiff_plain/465f4bf04069c64e49bc9420f434a0b96cbcd127..e02082ad2d87032e8cff4fa8cc48682c85efc624:/IWCMC14/HLG.tex?ds=inline diff --git a/IWCMC14/HLG.tex b/IWCMC14/HLG.tex index 183e00b..1f9fab9 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 circles 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} +\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 between +$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,50 +33,70 @@ 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 been initiated 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 emission 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 follows: $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 minimize - $q$ under the following set of constraints +\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 + -\sum_{l \in L} a_{il}^{-}.c^r.y_l \leq q.B_i, \forall i \in N$ +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 @@ -80,27 +106,62 @@ $$ \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.B_i, \forall i \in N + \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$. -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$ + + +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 -$$ -where $\delta$ is a \JFC{ formalisation} factor. -This allows indeed to get convex functions whose minimum value is unique. +\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{PM06}. +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$. -The proposed algorithm iteratively computes the following variables +\begin{equation} +\begin{array}{l} +L(R,x,P_{s},q,u,v,\lambda,w)=\\ +\sum_{i \in N} \left( q_i^2 + q_i. \left( +\sum_{l \in L } a_{il}w_l- +\lambda_iB_i +\right)\right) \\ ++ \sum_{h \in V} \left( +v_h.\dfrac{\ln(\sigma^2/D_h)}{\gamma P_{sh} ^{2/3}} + \lambda_h P_{sh} \right)\\ ++ \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} \left( +\delta R_{h}^2 +-v_h.R_{h} - \sum_{i \in N} u_{hi}\eta_{hi}\right) +\end{array} +\label{eq:dualFunction} +\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) $ @@ -108,43 +169,43 @@ The proposed algorithm iteratively computes the following variables $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)} = \lambda_{i}^{(k)} - \theta^{(k)}.\left( - q^{(k)}.B_i \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. \sum_{l \in L} a_{il}^{-}.c^r.\left( \sum_{h \in V}x_{hl}^{(k)} \right) - P_{si}^{(k)} \right) + \lambda_{i}^{(k+1)} = \max\left\{0, \lambda_{i}^{(k)} - \theta^{(k)}.\left( + q^{(k)}.B_i - P_{si}^{(k)} \right. \right.\\ + \qquad\qquad\qquad -\sum_{l \in L}a_{il}^{+}.c^s_l. \sum_{h \in V}x_{hl}^{(k)} \\ + \qquad\qquad\qquad - \left.\left. c^r.\sum_{l \in L} a_{il}^{-}. \sum_{h \in V}x_{hl}^{(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)$ +$w_l^{(k+1)} = w_l^{(k+1)} + \theta^{(k)}. \sum_{i \in N} a_{il}.q_i^{(k)} $ \item -$\theta^{(k)} = \omega / t^{1/2}$ +$\theta^{(k)} = \omega / k^{1/2}$ \item -$q_i^{(k)} = \arg\min_{q_i>0} +$q_i^{(k+1)} = \arg\min_{q_i>0} \left( -q^2 + q. +q_i^2 + q_i. \left( \sum_{l \in L } a_{il}w_l^{(k)}- \lambda_i^{(k)}B_i \right) \right)$ -\item +\item \label{item:psh} $ -P_{sh}^{(k)} +P_{sh}^{(k+1)} = \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) $ \item $ -R_h^{(k)} +R_h^{(k+1)} = \arg \min_{r \geq 0 } \left( @@ -154,7 +215,7 @@ R_h^{(k)} $ \item $ -x_{hl}^{(k)} = +x_{hl}^{(k+1)} = \begin{array}{l} \arg \min_{x \geq 0} \left( @@ -170,5 +231,4 @@ c^r. a_{il}^{-} ) \right.\\ \end{array} $ \end{enumerate} -where the first four elements are dual variable and the last four ones are -primal ones \ No newline at end of file +for any $h \in V$, $i \in N$, and $l \in L$.