Network coding-aware flow control in wireless ad-hoc networks with multi-path routing

Abstract

In this paper, we study a flow control problem considering network coding in wireless ad-hoc networks with multi-path routing. As a network coding scheme, we use XOR network coding, in which each node bitwise-XORs some packets received from different sessions, and then broadcasts this coded packet to multiple nodes in a single transmission. This process can reduce the number of required transmissions, and thus can improve network utilization, especially if it is used with appropriate network coding-aware protocols. Considering this XOR network coding, we formulate an optimization problem for flow control that aims at maximizing network utility. By solving the optimization problem in a distributed manner, we implement a distributed flow control algorithm that provides the optimal transmitting rate on each of multiple paths of each session. The simulation results show that our flow control algorithm performs well exploiting the advantages of network coding and provides significant performance improvement.

Appendix

In this appendix, we derive iterative procedures in (16)–(19) from the Lagrangian function in (13). By substituting the expression on the right hand side of the inequality in (11) for h ⁿ _m (x) and by using (4), we can rewrite the Lagrangian function in (13) as:

$$ \begin{aligned} L({\bf x}, {\varvec{\lambda}}) =& \sum_{s \in S} U_s\left(\sum_{p \in P(s)} x_{(s,p)} \right) + \sum_{n \in N} \sum_{m \in N(n)} \lambda_{m}^n \left\{ c_{m}^n + \frac{1}{2} \sum_{k\in N(n)\backslash \{m\}} c_{(k,m)}^n \right. \\ & \left. - x^n_{m} - \sum_{k\in N(n)\backslash \{m\}} x_{(k, m)}^n + \frac{1}{2} \sum_{k\in N(n)\backslash \{m\}} \min \left[x_{(k,m)}^n,\,x_{(m,k)}^n,\,c_{(k,m)}^n \right] \right\}. \end{aligned} $$

(20)

Then, by rearranging the above Lagrangian function, we obtain the following:

$$ \begin{aligned} L({\bf x}, {\varvec{\lambda}}) =& \sum_{s \in S} U_s\left(\sum_{p \in P(s)} x_{(s,p)} \right) \\ &- \sum_{n \in N} \sum_{m \in N(n)} \lambda_{m}^n x^n_{m} - \sum_{n \in N} \sum_{m \in N(n)} \sum_{k\in N(n) \backslash \{m\}} \lambda_{m}^n x_{(k, m)}^n \\ & + \frac{1}{2} \sum_{n \in N} \sum_{m \in N(n)} \sum_{k\in N(n) \backslash \{m\}} \lambda_{m}^n \left( \delta_{(k,m)}^n x_{(k,m)}^n + \delta_{(m,k)}^n x_{(m,k)}^n + \zeta_{(k,m)}^n c_{(k,m)}^n \right) \\ & + \sum_{n \in N} \sum_{m \in N(n)} \lambda_{m}^n c_{m}^n + \frac{1}{2} \sum_{n \in N} \sum_{m \in N(n)} \sum_{k\in N(n) \backslash \{m\}} \lambda_{m}^n c_{(k,m)}^n, \end{aligned} $$

(21)

where

$$ \delta_{(k,m)}^n = \left\{ \begin{array}{ll} 1, & \hbox{if}\, \min \left[x_{(k,m)}^n, \, x_{(m,k)}^n, \, c_{(k,m)}^n \right] = x_{(k,m)}^n \\ 0, & \hbox{otherwise}\\ \end{array} \right., \quad \forall k,m \in N(n), \,\, k \neq m, \,\, \forall n \in N, $$

and

$$ \zeta_{(k,m)}^n = \left\{ \begin{array}{ll} 1, & \hbox{if}\, \min \left[x_{(k,m)}^n,\,x_{(m,k)}^n,\,c_{(m,k)}^n \right] = c_{(k,m)}^n \\ 0, & \hbox{otherwise} \end{array} \right., \quad \forall k,m \in N(n) \,\, k \neq m, \,\, \forall n \in N. $$

We can further rewrite (21) by substituting (8) for x ⁿ _m , and (3) for x ⁿ_(k,m) and x ⁿ_(m,k) as:

$$ \begin{aligned} L({\bf x}, {\varvec{\lambda}}) =& \sum_{s \in S} \left\{ U_s\left(\sum_{p \in P(s)} x_{(s,p)}\right) \right. \\ &\left. + \sum_{p \in P(s)} x_{(s,p)} \sum_{n \in p} \left[-\lambda_{t_{(s,p)}(n)}^n + \frac{1}{2} \delta_{(r_{(s,p)}(n), t_{(s,p)}(n))}^n \left( \lambda_{t_{(s,p)}(n)}^n + \lambda_{r_{(s,p)}(n)}^n \right) \right] \right\} \\ & + \sum_{n \in N} \sum_{m \in N(n)} \lambda_{m}^n c_{m}^n + \frac{1}{2} \sum_{n \in N} \sum_{m \in N(n)} \sum_{k \in N(n) \backslash \{m\}} \left( 1 + \zeta_{(k,m)}^n \right) \lambda_{m}^n c_{(k,m)}^n. \end{aligned} $$

(22)

Hence, from (20) and (22), we can obtain the partial derivatives of the Lagrangian function with respect to λ ⁿ _n and x _(s,p) as:

$$ \begin{aligned} \frac{\partial L({\bf x},{\varvec{\lambda}})}{\partial \lambda_{m}^n} =h_{m}^n({\bf x})=& c_{m}^n + \frac{1}{2} \sum_{k\in N(n)\backslash \{m\}}c_{(k,m)}^n - x^n_{m} - \sum_{k\in N(n)\backslash \{m\}} x_{(k,m)}^n \\ &+ \frac{1}{2} \sum_{k\in N(n)\backslash \{m\}} \min\left[x_{(k,m)}^n,\,x_{(m,k)}^n,\,c_{(k,m)}^n \right]\end{aligned} $$

and

$$ \begin{aligned} \frac{\partial L({\bf x}, {\varvec{\lambda}})}{\partial x_{(s,p)}} \,=\,& \frac{\partial U_s \left( \sum_{p \in P(s)} x_{(s,p)} \right)}{\partial x_{(s,p)}} + g^n_{(s,p)}({\varvec{\delta, \lambda}})\\ \,=\,& \frac{\partial U_s \left( \sum_{p \in P(s)} x_{(s,p)} \right)}{\partial x_{(s,p)}} -\lambda_{t_{(s,p)}(n)}^{n} + \frac{1}{2} \delta_{(r_{(s,p)}(n), t_{(s,p)}(n))}^n \left( \lambda_{t_{(s,p)}(n)}^n + \lambda_{r_{(s,p)}(n)}^n \right), \end{aligned} $$

where ${\varvec{\delta}} = \left( \delta_{(k,m)}^n \right)_{k \neq m, \, k,m \in N(n),\, n \in N}$.

Hence, the Lagrangian algorithm can be implemented as

$$ \begin{aligned} {x_{(s,p)}}^{(i+1)} =& \left[ {x_{(s,p)}}^{(i)} + \alpha^{(i)} \frac{\partial L({{\bf x}}^{(i)}, {\varvec{\lambda}}^{(i)})}{\partial x_{(s,p)}} \right]^{+} \\ =& \left[ {x_{(s,p)}}^{(i)} + \alpha^{(i)} \left\{ \left.\frac{\partial U_s \left( \sum_{p \in P(s)} x_{(s,p)} \right)}{\partial x_{(s,p)}} \right|_{{\bf x}={{\bf x}}^{(i)}} + \sum_{n \in p} g^n_{(s,p)}({\varvec{\delta}}^{(i)}, {\varvec{\lambda}}^{(i)}) \right\} \right]^+, \quad \forall p \in P(s), \,\, \forall s \in S \end{aligned} $$

and

$$ \begin{aligned} {\lambda_{m}^n}^{(i+1)} =& \left[ {\lambda_{m}^n}^{(i)} - \beta^{(i)} { \frac{\partial L({{\bf x}}^{(i)}, {\varvec{\lambda}}^{(i)})}{\partial \lambda_{m}^n}} \right]^+\\ =& \left[ {\lambda_{m}^n}^{(i)} - \beta^{(i)} h_{m}^n({\bf x}^{(i)}) \right]^+ , \quad \forall m \in N(n), \,\, \forall n \in N, \end{aligned} $$

where α⁽ⁱ⁾ and β⁽ⁱ⁾ are step sizes at iteration i, [a]⁺ = max {a, 0},

$$ \begin{aligned} {\delta_{(k,m)}^n}^{(i+1)} = & \left\{ \begin{array}{ll} 1, & \hbox{if}\, \min \left[{x_{(k,m)}^n}^{(i)},\,{x_{(m,k)}^n}^{(i)},\,c_{(k,m)}^n \right] = {x_{(k,m)}^n}^{(i)} \\ 0, & \hbox{otherwise} \\ \end{array}\right.,\quad \forall k,m \in N(n), \,\, k \neq m, \,\, \forall n \in N, \end{aligned} $$

and

$$ \begin{aligned} g^n_{(s,p)}({\varvec{\delta}}^{(i)}, {\varvec{\lambda}}^{(i)}) =& -{\lambda_{t_{(s,p)}(n)}^{n}}^{(i)} + \frac{1}{2} {\delta_{(r_{(s,p)}(n), t_{(s,p)}(n))}^n}^{(i)} \left( {\lambda_{t_{(s,p)}(n)}^n}^{(i)} + {\lambda_{r_{(s,p)}(n)}^n}^{(i)} \right), \quad \forall n \in N, \,\, \forall p \in P(s), \,\, \forall s \in S. \end{aligned} $$