Speech Transcript - CONVEX APPROXIMATION ALGORITHMS FOR BACK-PRESSURE POWER CONTROL OF WIRELESS MULTI-HOP NETWORKS

0:00:13	Q are like
0:00:14	so with that and everyone
0:00:16	so i would be in about uh that this a power control
0:00:19	um i know that uh i i is in and doing thing
0:00:23	and resource allocation for wireless multihop networks
0:00:26	is don't work with my
0:00:28	but a student
0:00:29	a a a a like my gone
0:00:30	my friend and probably members post you
0:00:34	oh i have a is i know that maybe be in the audience no about um i think that being
0:00:39	but for those of that then uh we can that action
0:00:43	uh if you have they can that of course in the network you know that uh
0:00:47	the you you land in our thing is that a big
0:00:51	uh where in
0:00:52	oh you have a graph and it would the to present as a graph
0:00:55	uh you could uh a it is on the go
0:00:57	every L
0:00:58	as a set and way
0:01:00	typically this way to lex
0:01:02	the back
0:01:03	or have a that's delay or or uh some other
0:01:06	uh back to a let's say your delays that this big on that particular thing
0:01:11	and we do so this that thing meeting that we compute the do this but when the source to a
0:01:16	desired destination
0:01:17	and we like it's along long what was but
0:01:20	a this of this path thing is well motivated for a number of reasons
0:01:24	uh by five to his motivation or the claim of so was but out thing is that is a service
0:01:29	by
0:01:30	and if you
0:01:30	you weights that
0:01:32	basically got to the reflect
0:01:34	uh you have is a delay let's say about link
0:01:37	uh what you get
0:01:39	delay
0:01:40	but this is a
0:01:42	at low system loads because of kind system loads the so this but may not have enough capacity to can
0:01:47	bit your traffic
0:01:49	and you may need to use
0:01:50	secondary path
0:01:52	and that a and number of other issues
0:01:54	um the going for stuff set this but i think in but the fact that you can set it
0:01:59	uh with a relatively low complexity difference
0:02:02	i including a distributed algorithms
0:02:04	or these a dynamic programming based the average
0:02:07	um
0:02:08	the
0:02:09	difficult of time and is associated with a this bad that i thing in of the fact that you must
0:02:13	know the i've and rate so we can prove a long
0:02:16	the service that
0:02:17	um i i so that is are going to that they should
0:02:21	and fighting
0:02:22	all the service that
0:02:23	uh that so
0:02:25	in fact is slow
0:02:26	uh by wireless fading on that
0:02:28	that bad to changing i as
0:02:31	um
0:02:32	in the lower than patterns of a lot but or or of that the nodes
0:02:35	and most importantly in wireless network in
0:02:38	uh i mean
0:02:39	uh change is due to fading
0:02:41	okay
0:02:42	i i ninety to my uh my colleague as that's you less of that was part of his P the
0:02:47	this
0:02:48	you you use a new but dying for a uh i think
0:02:52	no as back last a minute working common
0:02:55	uh is that on a concept
0:02:57	a that is a concert there a difference of but
0:03:00	which measures the sense only
0:03:02	a a a a a a a back to is with respect to an ending no
0:03:07	but
0:03:08	and that the decisions are but and this one difference and back
0:03:12	a and about the surrounding "'cause" one lots of plane
0:03:15	in the network i
0:03:17	for this is the most and the reason
0:03:20	is is that the K is not maximal stable throughput place so basically
0:03:24	but this work as the policy
0:03:25	so is probably
0:03:27	that if the network can sustain a set and
0:03:30	uh
0:03:31	seven and
0:03:33	"'kay"
0:03:34	a a and that big you is going to instead but
0:03:38	a a a a so we'll will start has a network and push all the packets through the network
0:03:42	do you have a site to this nation so it was a maximum flow
0:03:45	my can use they can private in that but
0:03:48	um the biggest plane
0:03:50	we should have as it must recognise the past
0:03:52	so it doesn't that a long run only
0:03:55	uh let and and the sense
0:03:57	because that of to a C is a very way
0:04:00	that
0:04:01	a is this predicted by to a teenager read quickly that's to changing
0:04:05	conditions
0:04:06	and like sort of stuff helping
0:04:08	um
0:04:09	that it is a
0:04:10	so of that a problem as well do not think that can be that
0:04:15	a because it uses but that's with to guy packets to the network it there is no
0:04:19	in the network that work is empty a back and kid can simply go through a time
0:04:24	uh would to is that is basically a you a to go
0:04:27	with respect to learn
0:04:28	okay there's an active node
0:04:30	but nice is delay and if you can be like i think you could in late
0:04:34	okay very
0:04:35	uh a uh uh a have a Q or something
0:04:37	i like but this can we get the sense that it can you can combine the said this
0:04:43	that are sets of uh
0:04:44	uh
0:04:45	that you can play
0:04:46	so can as a a uh a sort of a picture of set that of four by this of thing
0:04:50	so that
0:04:51	or that that in the network and sitting here
0:04:54	i i think about the
0:04:56	and let's my by contains the back it's in this particular example
0:04:59	uh this guy was that it contains
0:05:01	that the packets
0:05:02	a the difference in
0:05:04	is the maximum of zero and the difference of this look like this
0:05:08	so this particular uh example of so uh but we didn't know to and not five is
0:05:14	because this does is not known
0:05:17	and
0:05:18	um
0:05:19	but as we can from these because the you of that guy was is you back risk
0:05:23	best
0:05:23	that's is but
0:05:24	okay
0:05:25	a a a a a a a is the that to note is for thing to do this to set
0:05:30	of an in between this can know this two
0:05:32	but that's of adding for a
0:05:36	in that decisions
0:05:37	okay
0:05:39	a a a bad thing
0:05:40	and you that as a down here it's of any possible to is that the only possible for for the
0:05:44	so to get back
0:05:46	a packet that has been
0:05:48	if you look at a lot what he's this but the you when that in how it can be
0:05:52	the fact that the market is
0:05:53	that is the low builds that
0:05:55	okay one big are given below that this one cup
0:05:58	a "'cause" that the idea is proof of that
0:06:02	you we have not of this nation's
0:06:06	um a multiple source destination pair or even different types of that uh i think this these are a come
0:06:10	and it is in networking
0:06:12	i then
0:06:13	uh actually live that's to do this
0:06:16	what happens to you you have to be not use but no
0:06:19	well that commodity died
0:06:21	okay
0:06:22	a a and then like to do is on it to you take the maximum difference so but so the
0:06:27	my
0:06:28	of of um and that is that a this link
0:06:30	or the different so that no
0:06:32	and basically you you the entirely the capacity about lee
0:06:35	to to do the
0:06:37	to the commodity that is a uh i i i and it's about a lot
0:06:41	so i if it was ever been i me used to a maximum a can which a maximum
0:06:47	task got lost
0:06:48	okay
0:06:49	if you use that this
0:06:50	not if you
0:06:53	uh that but also i have been and some of the mitigation lead to computation you compute D for the
0:06:58	difference is basically on
0:06:59	let an occasion because i only get them as or
0:07:02	but if it so that was use but we and and a handle but not to the rest of you
0:07:06	guys for the don't at all
0:07:08	so it's a very nice but to the problem
0:07:11	the i think a station is a different because of was is you know is a broadcast medium
0:07:16	and a and a link that is dependent transmission scheduling and power of are added that the links
0:07:23	so this is what i call love a so
0:07:26	yeah i where
0:07:27	my to do this but increase
0:07:29	but the this is this is an example of the values so
0:07:32	but also how to me
0:07:33	uh a so that playing field
0:07:36	you know it's to to
0:07:38	so is the physical you um
0:07:41	interference patterns it
0:07:43	a a to control K this is what the name of the game here is all about
0:07:48	so two
0:07:49	i like the problem mathematically
0:07:50	uh if you got a set and you let's say between a a time
0:07:54	uh with of a a not the L L for link L
0:07:59	but i'm duration power my recent and parties be L
0:08:03	is that of a cost i mean you games between i have a
0:08:06	the the time to meet those have a a in this is a like but with a link a and
0:08:11	and uh the receiver of link L
0:08:13	but time use of power of link eight and then the background noise
0:08:17	okay
0:08:18	so this is a lot of in of last noise
0:08:20	uh a as you know a the C value of
0:08:22	but that
0:08:23	i if that sounds st very low
0:08:25	a i think that link will be of random is bad
0:08:29	the defence
0:08:31	i and
0:08:33	i would have that i'm to see but would be this one to you the maximum the Q
0:08:37	zero and the difference of the queue line
0:08:40	and the and
0:08:43	it
0:08:43	yes
0:08:44	that is king
0:08:45	oh was a some problem
0:08:47	you was so that is
0:08:50	that is that's good isn't because it because he he's
0:08:52	so so so is E to zero you decide of something
0:08:56	okay
0:08:57	and
0:08:58	so that is
0:08:59	and this this
0:09:01	oh maximise the reference back but sound
0:09:07	oh the it's not bad
0:09:11	well as bad for the with an upper bound on a some power of that and the have at time
0:09:17	because the right
0:09:19	and that's
0:09:20	the fans
0:09:22	okay you may
0:09:25	by a constant
0:09:26	so that
0:09:28	oh so this problem
0:09:30	there was networks
0:09:32	we do that he didn't have scheduling and power allocation
0:09:35	from the viewpoint of maximizing that works that but that the basic
0:09:41	and
0:09:44	that's
0:09:45	ah
0:09:47	at this
0:09:47	now ah
0:09:49	so that was like that was my buttons the since then and that in many ways
0:09:56	this is a a survey but
0:09:59	a a problem time my but to the sun
0:10:02	um
0:10:04	so was not for many he has to be a problem i see
0:10:10	hmmm
0:10:11	but but not count can perhaps the most
0:10:14	for example if you get you can sort
0:10:17	times with that but not have so either by
0:10:20	ah
0:10:21	yeah that was a that this is a
0:10:23	this a problem you can smell the
0:10:27	and
0:10:27	if you are so that you the core
0:10:30	and you can
0:10:32	so for hours by the powers
0:10:35	you set of it is but that for you are present
0:10:38	a about the time but in the is where Q is it is but that you had but it if
0:10:42	not you can be to use one you don't like this
0:10:45	this can you see surprisingly
0:10:48	well also so to use maximum stable
0:10:51	and and there is very nice intuition of that can exploit
0:10:53	explain of states
0:10:55	if you it
0:10:55	well as far
0:10:56	but this
0:10:57	of course it is a delay but again we could maximise
0:11:00	a a maximum throughput
0:11:03	the question that the so of this paper is and the need to compete or something a some bit about
0:11:08	this bad is leading powers that
0:11:10	you know
0:11:11	you can choose you can
0:11:12	to to between zero and an upper bound
0:11:16	but that stay on pattern
0:11:18	not not very well
0:11:19	a know if you think that this problem for the that have that this is uh it it is a
0:11:25	end of the sound of in is a some problem in not networks well as an words in S cell
0:11:30	ah
0:11:31	but
0:11:32	since sensing at this meeting that not i think that was that could be but assume that that that's and
0:11:36	once in the difference
0:11:38	we have is that as you can have just a in a as you can
0:11:42	and that's that like to answer that has that the receiver
0:11:46	and this but quite X
0:11:49	yeah
0:11:50	so you that is part of the optimization invest
0:11:55	as is that
0:11:56	that is
0:11:57	in this and i i have think that now that's a lot for change or games
0:12:03	a i think that it is bad and that was that was that that is the for time that that
0:12:09	of the channels are best
0:12:10	in a direction
0:12:11	so you and to for me to do that um
0:12:14	so uh has and so by
0:12:17	from and is that
0:12:19	a a uh hmmm so that this key difference is the best of them require
0:12:24	if you in the back
0:12:25	so that
0:12:27	uh_huh that is that
0:12:29	you can
0:12:30	basically when you prevent be is used to show that that is
0:12:34	and then P that problem
0:12:35	okay
0:12:36	and by
0:12:37	but are chosen the back
0:12:39	you that night
0:12:41	so that that them for now that a configuration of back
0:12:44	if fact can set so that it can "'cause" not consent to a special configuration if that a configuration
0:12:50	so that think that that the that does not sales
0:12:53	but has a given
0:12:55	i i see that as a
0:12:57	right
0:12:58	so
0:12:58	oh
0:12:59	is that is or so
0:13:01	and that is not to the for this that's me that on this that is not for this me that
0:13:06	i in fact is that i have a set of chords and links
0:13:10	and the for back into the the that's another
0:13:12	okay and that this so that uh
0:13:15	now if you have found this that's will discuss look not because of miss it works you also to find
0:13:21	that estimation algorithms
0:13:23	and we can basically uh
0:13:25	but
0:13:26	and i do an on a scale from a and you layers
0:13:29	a a and and and button thousand six
0:13:32	i'm going to all the level was the is but the basic idea of scale
0:13:36	is to a
0:13:37	uh no and
0:13:39	uh approximation a in a a and of the sound a uh with the an objective function that is
0:13:45	um
0:13:46	have to that is exact
0:13:48	and then to a solution
0:13:49	right instead of doing it and that approximation to has now to the specification of those
0:13:54	in this you did you that is
0:13:56	okay
0:13:57	so this is to your this realisation
0:14:00	you you of the sequence of convex problems
0:14:03	and use the second step of to move this omission of it
0:14:05	or an np-hard problem
0:14:07	okay
0:14:08	ah
0:14:08	it can do is with us that is that in that that the of the same that well at the
0:14:13	same problem that
0:14:14	that problems
0:14:15	with different objective function
0:14:17	and then
0:14:18	a if you have but as it is working but complex this you need something not fast than and that
0:14:25	a so
0:14:27	that's and look at the algorithms of that to do
0:14:29	shall this problem much faster than than it does the service
0:14:32	ah
0:14:33	where a is a is it can use here and that was that was the of something that was left
0:14:39	and then they fans the
0:14:41	this person is ugly
0:14:44	it is a it because i was network
0:14:47	but uh you have not listen what we talk states
0:14:50	the that
0:14:51	is like you are you're you use it is post by that that it is by the car so it
0:14:56	good like that
0:14:58	so there is so that that i is and the network
0:15:00	and that let you the solution that you're sitting gets that E is in fact a very different from the
0:15:05	previous one because in the previous money make for them are used you
0:15:09	oh
0:15:09	a way for
0:15:11	so in fact this is why is doesn't work
0:15:13	which also said to
0:15:14	and we could be able to show the cases
0:15:17	but
0:15:18	uh
0:15:19	well can expect you are they can be here in the network
0:15:22	if you choose a window of past solutions in single a which one of the past babble use an issue
0:15:27	is better
0:15:30	oh
0:15:30	do an excellent rents that
0:15:33	okay
0:15:33	a a i a that D V you a and that
0:15:38	uh
0:15:39	extensive uh experiments
0:15:41	uh it is interesting that that is a thing that and the simulation
0:15:46	but we bring signal processing folks we we uh
0:15:49	we the level of simulations
0:15:50	and i would have to give it just the
0:15:52	um so that that you'll and basically i'm just
0:15:56	i we just like some of them a result
0:15:58	um
0:15:59	is that is a that is it difficult scenarios uh no this is in that not if and this one
0:16:04	that has an is this is kind the file as the interference
0:16:07	scenario
0:16:08	a a this is a i think that we use that as an approximation of than and become problem
0:16:14	in terms of a uh not the last
0:16:16	so you should my and seven
0:16:18	if you do has access to that two nations that it's is the it's and that for
0:16:23	this is that this study of for all our out that is actually do do level and sound of his
0:16:28	collaborators
0:16:29	i have a so that can do a lot of that is the look up as
0:16:33	all that could that the a or using all algorithms
0:16:37	at at at next
0:16:38	well
0:16:39	at the
0:16:40	um
0:16:41	well as the estimate that sense of those of was that a as a sources
0:16:47	i would actually used
0:16:48	but
0:16:49	uh or or as as is what happens with a it is that
0:16:54	but have a thing so that was that that it might don't know
0:16:59	yeah it a suppose that like sing
0:17:01	not i concerned that
0:17:04	the problem is that car
0:17:05	and the for a approximation
0:17:07	so for and
0:17:09	i
0:17:09	so that that the minute i think course
0:17:29	at some point you are
0:17:31	and and
0:17:32	taking not as a constraint but but as the way in the capacity of ring
0:17:36	hmmm
0:17:36	at the beginning of your two
0:17:38	yeah and you are
0:17:39	acting acting as if
0:17:40	the cat the C D's where in that and then
0:17:43	and at some point
0:17:44	maybe
0:17:45	some no
0:17:46	we E a
0:17:49	contacted by to transmit
0:17:51	in this case these is will be we act
0:17:54	as a multi a model in the multiple access situation
0:17:59	and to get a C D's will not be in that then
0:18:02	well
0:18:02	okay what uh is that that uh
0:18:05	you are assume that every E
0:18:07	we we
0:18:09	um
0:18:11	a single a of mission yeah will do that to do the fist that's is something like that is you
0:18:15	see then
0:18:16	in
0:18:17	this is a nice then the formulation you that
0:18:19	that nodes i and everything because
0:18:22	you know see still
0:18:24	but a these case
0:18:25	margin for
0:18:26	and
0:18:26	you could use disk
0:18:28	which are set and that mean so that it is not
0:18:32	what that that that i when i say that is a a a a a a is a much not
0:18:36	stable through
0:18:37	i
0:18:38	assumption sounds
0:18:51	don't

CONVEX APPROXIMATION ALGORITHMS FOR BACK-PRESSURE POWER CONTROL OF WIRELESS MULTI-HOP NETWORKS

Networking and Coding

Presented by: Nikolaos Sidiropoulos, Author(s): Evaggelia Matskani, Nikolaos Sidiropoulos, Technical University of Crete, Greece; Leandros Tassiulas, University of Thessaly, Greece