In layered multicast [1], signal (e.g. video or audio) is encoded into multiple layers with different rates and sent from one transmitter to an arbitrary number of receivers. Depending on the network condition, receivers can receive different numbers (all or only a portion) of the layers and obtain reconstructed signal with different qualities. Compared with single-rate multicast, layered multicast is more advantageous in heterogeneous networks because it can satisfy receivers with different requirements simultaneously so that the network can be utilized more efficiently.
A multicast session can be described by a tree in which the root and leaf nodes are the transmitter and receivers, respectively, while the internal nodes play roles of relaying [2]. Each link in the tree has a weight, representing the capacity of the corresponding link in real network. The goal of rate control in layered multicast is to determine the rates of all the internal and leaf nodes that achieves optimality according to certain criterion. When there is only one multicast session in the network, the rate control is simple: every internal node transmits to its child node the maximum number of layers it receives from its parent that doesn’t exceed the link capacity. However, problem becomes complicated when two or more multicast sessions in one network compete on shared links. In this case, we can define a utility function for received rates in all sessions and solve an optimization problem whose objective is to maximize the overall utility.
In [2], Kar and Tassiulas proposed a dual-based iterative algorithm using Lagrange relaxation to solve the rate control problem for layered multicast in wireline network (each link has a fixed capacity). Each iteration include two steps: link price update and session rates update. They further showed that the session rates update step can be solved by dynamic programming which greatly reduces the computation cost and allows the algorithm to be performed in a distributed manner. Indeed, because of the tree structure of multicast the session rates update step is a finite state space (because the number of layers is finite) deterministic dynamic programming problem with perfect state information
When considering layered multicast in cognitive radio network, problem becomes more complicated because of the fact that the cognitive radio network is full of randomness:
- There exists interference between neighboring nodes, which implies not all the nodes are allowed to communicate simultaneously. In [3], interference is taken into account by adding constraints to the optimization problem that only a subset of nodes can transmit in the same time slot. However, there are other ways of avoiding interference, such as using random access.
- Because of multipath propagation or shadowing, the wireless fading channel is time-varying, which means the channel capacity for each link is not a fixed value, but a random variable depending on the channel condition of that link and power allocated to it.
- In cognitive radio networks, the available frequency bands at each node are different, depending on its location and environment. Again, the available bands at each node can be modeled as random varibles [4]. In addition to rate control, we have to do frequency control which again is a power control problem, i.e. allocating limited power among available frequency bands.
When taking all these randomness of cognitive radio networks into account, the rate control problem is no longer a deterministic optimization problem. Instead, the session rates update step as described in (1) becomes a stochastic dynamic programming problem
![\displaystyle J_i(x_k) = \sum_{i' \in B_i} \underset{x_{k'} \leq x_k}{\text{max}}\{ J_{i'}(x_{k'}) - E_{\vec w_k}[c(x_{k'},\vec w_k)] \}, \ \ \ \ \ (2)](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+++J_i%28x_k%29+%3D+%5Csum_%7Bi%27+%5Cin+B_i%7D+%5Cunderset%7Bx_%7Bk%27%7D+%5Cleq+x_k%7D%7B%5Ctext%7Bmax%7D%7D%5C%7B+J_%7Bi%27%7D%28x_%7Bk%27%7D%29+-+E_%7B%5Cvec+w_k%7D%5Bc%28x_%7Bk%27%7D%2C%5Cvec+w_k%29%5D+%5C%7D%2C+%5C+%5C+%5C+%5C+%5C+%282%29&bg=ffffff&fg=000000&s=0 "\displaystyle J_i(x_k) = \sum_{i' \in B_i} \underset{x_{k'} \leq x_k}{\text{max}}\{ J_{i'}(x_{k'}) - E_{\vec w_k}[c(x_{k'},\vec w_k)] \}, \ \ \ \ \ (2)")
The goal of this project has three aspects. First, we assume that power is fixed and full channel and frequency information is known and solve (2). This is not a difficult task, but from which we wish to get some intuition about how the optimal control policy changes as network characteristics change. Second, develop power control algorithm which is expected to be distributed while still assuming we have perfect prior knowledge about channel and network conditions. Finally, develop stochastic learning algorithms [5] that solve optimal rate and power control problem without using any prior information about channel and network. This is extremely important because in practice full channel and network information is either inaccurate or unavailable.
{99}
[1] S. McCanne, V. Jacobson ,and M. Vetterli, “Receiver-driven layered multicast”, in Proc. ACM SIGCOMM, Stanford, CA, Aug. 1996, pp. 117-130.
[2] K. Kar and L. Tassiulas, “Layered multicast rate control based on Lagrangian relaxation and dynamic programming”, in IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1464-1474, Aug. 2006.
[3] L. Bui, R. Skirant, and A. Stolyar,“Optimal resource allocation for multicast sessions in multi-hop wireless networks”, in Phil. Trans. R. Soc. A, no. 366, pp. 2059-2074, Mar. 2008.
[4] Y. Shi and T. Hou, “A distributed optimization algorithm for multi-hop cognitive radio networks”, in Proc. IEEE INFOCOM, pp. 1292-1300, Apr. 2008.
[5] A. Ribeiro, “Stochastic learning algorithms for optimal design of wireless fading networks”, submitted to IEEE INFOCOM, Jul. 2009.
October 22, 2009 at 7:35 am |
don’t know why \cite doesn’t work….
October 22, 2009 at 12:57 pm |
\cite cannot work because the latex parse is just local, cannot make reference accross your documents. Simple way to fix it is to replace your \cite by just numbers, e.g. [1]
November 16, 2009 at 7:35 pm |
sounds good. Not much comment at this point, although I’m not sure that I completely understand your equations (1) and (2).
Get in touch with me this week.
The “distributed part” does not seem to be an issue because of the fact that you are just doing DP on a tree, but I might have misunderstood.
What is the power control problem? doesn’t this problem require a larger state-space? In case you need an approximation architecture at some point for this problem, we can talk about fluid models.
The last part on learning looks like a typical case where stochastic approximation would be useful, probably just the simplest case of stochastic gradient descent. Try to spend some time on this part, at least getting some simulations.