IWCMC14/HLG.tex

   1 Let us first the basic recalls of the~\cite{HLG09} article.
   2
   3
   4 The  precise the context of video sensor network as represented for instance
   5 in figure~\ref{fig:sn}.
   6
   7 \begin{figure}
   8 \begin{center}
   9 \includegraphics[scale=0.5]{reseau.png}
  10 \caption{SN with 10 sensor}\label{fig:sn}.
  11 \end{center}
  12 \end{figure}
  13
  14
  15 Let us give a formalisation of such a video network sensor.
  16 We start with the flow formalising:
  17
  18 The video sensor network is represented as a strongly
  19 connected oriented labelled graph.
  20 In this one,
  21 the nodes, in a set $N$ are sensors, links, or the sink.
  22 Furthermore, there is an edge from $i$ to $j$ if $i$ can
  23 send a message to $j$. The set of all edges is further denoted as
  24 $L$ .
  25 This boolean information is stored as a
  26 matrix $A=(a_{il})_{i \in N, l \in L}$,
  27 where
  28 $a_{il} =
  29 \left\{
  30     \begin{array}{rl}
  31       1 & \textrm{if $l$ starts with $i$ } \\
  32       -1 & \textrm{si $l$ ends width $i$ }  \\
  33       0 & \textrm{otherwise}
  34     \end{array}
  35   \right.$.
  36
  37
  38 Let $V \subset N $ be the set of the video sensors of $N$.
  39 Let thus $R_h$, $R_h \geq 0$  be the encoding rate of  video sensor $h$, $h \in V$.
  40 Let $\eta_{hi}$ be the  production rate of the $i$ node, for the $h$ session. More precisely, we have
  41   $$
  42 \eta_{hi} =
  43 \left\{
  44     \begin{array}{rl}
  45       R_h & \textrm{if $i$ is $h$} \\
  46       -R_h & \textrm{if $i$ is the sink} \\
  47       0 & \textrm{otherwise}
  48     \end{array}
  49   \right.$$
  50
  51 We are then left to focus on the flows in this network.
  52 Let $x_{hl}$, $x_{hl}\geq 0$, be the flow inside the edge $l$ that
  53 issued from the $h$ session and
  54 let $y_l = \sum_{h \in V}x_{hl} $ the sum of all the flows inside $l$.
  55 Thus, what is produced inside the $i^{th}$ sensor for session $h$
  56 is  $ \eta_{hi} = \sum_{l \in L }a_{il}x_{hl} $.
  57
  58
  59 The encoding power of the $i$ node is $P_{si}$, $P_{si} > 0$.
  60
  61 The distortion is bounded $\sigma^2 e^{-\gamma . R_h.P_{sh}^{}2/3} \leq D_h$.
  62
  63 The initial energy of the $i$ node is  $B_i$.
  64
  65 The overall consumed power of the $i$ node is
  66 $P_{si}+ P_{ti} + P_{ri}=
  67 P_{si}+ \sum_{l \in L}a_{il}^{+}.c^s_l.y_l +
  68 \sum_{l \in L} a_{il}^{-}.c^r.y_l \leq q.B_i.
  69 $
  70
  71 The objective is thus to find $R$, $x$, $P_s$  which minimize
  72  $q$ under the following set of constraints
  73 \begin{enumerate}
  74 \item $\sum_{l \in L }a_{il}x_{hl} = \eta_{hi},\forall h \in V, \forall i \in N  $
  75 \item $ \sum_{h \in V}x_{hl} = y_l,\forall l \in L$
  76 \item $\dfrac{\ln(\sigma^2/D_h)}{\gamma.P_{sh}^{2/3}} \leq R_h \forall h \in V$
  77 \item \label{itm:q} $P_{si}+ \sum_{l \in L}a_{il}^{+}.c^s_l.y_l +
  78 \sum_{l \in L} a_{il}^{-}.c^r.y_l \leq q.B_i, \forall i \in N$
  79 \item $x_{hl}\geq0, \forall h \in V, \forall l \in L$
  80 \item $R_h \geq 0, \forall h \in V$
  81 \item $P_{sh} > 0,\forall h \in V$
  82 \end{enumerate}
  83
  84
  85 To achieve a local optimisation, the problem is translated into an
  86 equivalent one: find $R$, $x$, $P_s$  which minimize
  87 $\sum_{i \in N }q_i^2$ with the same set of constraints, but
  88 item \ref{itm:q}, which is replaced by:
  89
  90 $$P_{si}+ \sum_{l \in L}a_{il}^{+}.c^s_l.\left( \sum_{h \in V}x_{hl} \right) +
  91 \sum_{l \in L} a_{il}^{-}.c^r.\left( \sum_{h \in V}x_{hl} \right) \leq q.B_i, \forall i \in N$$
  92
  93
  94 The authors then apply a dual based approach with Lagrange multiplier
  95 to solve such a problem.
  96 They first introduce dual variables
  97 $u_{hi}$, $v_{h}$, $\lambda_{i}$, and  $w_l$ for any
  98 $h \in V$,$ i \in N$, and $l \in L$.
  99 They next replace the objective of reducing $\sum_{i \in N }q_i^2$
 100 by the objective of reducing
 101 $$
 102 \sum_{i \in N }q_i^2 +
 103 \sum_{h \in V, l \in L } \delta.x_{hl}^2
 104 + \sum_{h \in V }\delta.R_{h}^2
 105 $$
 106 where $\delta$ is a \JFC{ formalisation} factor.
 107 This allows indeed to get convex functions whose minimum value is unique.
 108
 109 The proposed algorithm iteratively computes the following variables
 110
 111 \begin{enumerate}
 112 \item $ u_{hi}^{(k+1)} = u_{hi}^{(k)} - \theta^{(k)}. \left(
 113  \eta_{hi}^{(k)} - \sum_{l \in L }a_{il}x_{hl}^{(k)} \right) $
 114 \item
 115 $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\}$
 116 \item
 117   $\begin{array}{rcl}
 118    \lambda_{i}^{(k+1)} = \lambda_{i}^{(k)} - \theta^{(k)}&.&\left(
 119     q^{(k)}.B_i -
 120     \sum_{l \in L}a_{il}^{+}.c^s_l.\left( \sum_{h \in V}x_{hl}^{(k)} \right) \right.  \\
 121    && - \left. \sum_{l \in L} a_{il}^{-}.c^r.\left( \sum_{h \in V}x_{hl}^{(k)} \right) - P_{si}^{(k)}  \right)
 122 \end{array}
 123 $
 124
 125 \item
 126 $w_l^{(k+1)} = w_l^{(k+1)} +  \theta^{(k)}. \left( \sum_{i \in N} a_{il}.q_i^{(k)} \right)$
 127
 128
 129 \item
 130 $\theta^{(k)} = \omega / t^{1/2}$
 131
 132  \item
 133 $q_i^{(k)} = \arg\min_{q_i>0}
 134 \left(
 135 q^2 + q.
 136 \left(
 137 \sum_{l \in L } a_{il}w_l^{(k)}-
 138 \lambda_i^{(k)}B_i
 139 \right)
 140 \right)$
 141
 142 \item
 143 $
 144 P_{sh}^{(k)}
 145 =
 146 \arg \min_{p > 0}
 147 \left(
 148 v_h^{(k)}.\dfrac{\ln(\sigma^2/D_h)}{\gamma p ^{2/3}} + \lambda_h^{(k)}p
 149 \right)
 150 $
 151
 152 \item
 153 $
 154 R_h^{(k)}
 155 =
 156 \arg \min_{r \geq 0 }
 157 \left(
 158 \delta r^2
 159 -v_h^{(k)}.r - \sum_{i \in N} u_{hi}^{(k)} \eta_{hi}
 160 \right)
 161 $
 162 \item
 163 $
 164 x_{hl}^{(k)} =
 165 \arg \min_{x \geq 0}
 166 \left(
 167 \delta.x^2 + x.
 168 \sum_{i \in N} \left(
 169 \lambda_{i}^{(k)}.(c^s_l.a_{il}^{+} +
 170 c^r. a_{il}^{-} )+
 171  u_{hi}^{(k)} a_{il}
 172 \right)
 173 \right)
 174  $
 175 \end{enumerate}
 176 where the first four elements are dual variable and the last four ones are
 177 primal ones