go ahead and get started. So, uh,
welcome to the first wireless at Virginia tech seminar for
the year. Like I said, I'm in the
somewhat awkward position of uh, announcing myself as the
first speaker for the seminar series. I have this
talk that I gave a few times in the last
year and I needed, uh, some video of
me giving a talk and I hadn't given it here
at Virginia Tech. So, uh, that's kind
of how this came to be the first seminar of
the year. We are setting up some others,
uh, dr Michael Marcus, who some of you
have heard uh, come to campus before a few
years ago is going to be here, I think
on october the fourth and I think um, Professor
Nicola Marchetti from trinity College Dublin is going to be
here either the following week or the week after that
. Um, we're still working on the details of
that. Um, but like I said, this
is a talk I gave a few times. I
was on sabbatical last year, as some of,
you know, I was at trinity college Dublin at
C T. V. R, which is Telecommunications
Research center of Ireland. And so I don't know
, maybe this is the last time I'll give this
talk acknowledging the support of the Science Foundation of Ireland
and of C T V. R. Um but
so this is stuff that I've been thinking about for
a few months. But maybe what's surprising to me
is uh is even now these are the topics that
I see as or so these topics at least lead
to things that I think are going to be of
research interest for the next several years. Um So
I'm working on some proposals now and they're directly related
to the topics that I'm going to be talking about
today. So without further ado then, um we
all know, I think that resource management is critical
for wireless communications. And so if you look at
the history of resource management and particularly spectrum management,
a lot of people even trace the story back to
the titanic disaster and the story whether you how much
of it you believe, I guess it's up to
you. But is that because of difficulties with radio
communication, more people perished in the titanic disaster than
might have otherwise? Um And that this was one
of the motivating factors for um for initial spectrum regulation
and for assigning spectrum to particular users into particular technologies
uh to try to protect users from interference and to
try to use spectrum uh in a in the most
valuable way possible as efficiently as possible. Um But
I'm gonna be trying today to talk about resource management
a little more broadly than just um spectrum management because
there are other resources that we care about here as
well um Within a wireless network, we often also
need to manage resources such as power. Um We're
interested in how much power those cellular base stations consume
as well as managing power on the handsets to give
us long battery life. And we also need to
manage computational resources. So we especially see this in
software defined radio systems, but the computation that we're
able to do on the device may limit what we're
able to do and we may be wilds. Engineers
don't think about it as much as we should,
but we also have resources that we need to manage
in terms of infrastructure access points and where those might
be placed and how those get used as well as
the back hall, the fiber optic infrastructure that might
connect those access points to the wired network. And
so, resource management is really critical to managing all
of these things and to trying to orchestrate them together
into a network that does the sorts of things uh
that we wanted to do. And so if you
look at this, um if you look at the
story of resource management and wireless networks over time,
you see a number of trends, you see things
going from being more centralized to more distributed. There
are lots of reasons for this, but as the
problem space grows, it becomes harder and harder to
even make these centralized resource management decisions. Uh It
also becomes less clear where they should go as our
systems, as our systems themselves have more pieces and
are more distributed. We also see trends in resource
management, from static resource management to dynamic resource management
. So in the original cellular systems, most channel
allocations to base stations were completely static. Over time
those have become more dynamic. Um And now we
see even more dynamics with LT systems where you want
to have to reuse factor one, so you want
to reuse the same frequencies in every cell and you
have to manage that interference closely in order to enable
you to do that. And we also see a
move from exclusive allocation to reuse and sharing. Um
Now I don't completely mean open spectrum or anything like
that here because we even see more reuse and sharing
within a cellular system owned by a single operator operating
under a single license. So we want to get
more and more spatial reuse. Um and we want
to be able to use the we want to be
able to use that spectrum resource more and more efficiently
. So these are all big trends that you can
see over decades here. Um Yeah. And they're
making things, you can say that they're making things
more and more complicated I guess in terms of the
resource management um and at the same time we have
another complexity that I think is is becoming really critical
to understanding resource allocation in these systems. And that's
a move from homogeneous systems to heterogeneous systems. So
even five years ago, but certainly if you go
any farther than that six or seven years ago,
um we had almost a one device per radio access
technology approach. You have a cell phone if you
wanted to use the cellular network and you have a
laptop if you wanted to use the data network.
Um So your laptop would let you use wifi,
Your cellphone would let you use the cellular system.
But of course those have converged into smartphones and in
addition to those to access technologies were adding more access
technologies to those smartphones going into the future. And
you even see the same thing on the base station
side on the access point side. Whereas before we
had complete separation of cellular base stations and wifi access
points. Now we have more and more convergence with
these, these sort of symptoms sell devices that may
also offer wifi services um, as well as functioning
as cellular base station. So we have a convergence
on that side as well. Um, and the
reason I think this trend is important for resource management
is I think we really don't know how to manage
wireless resources across these multiple radio access technologies. So
if you have a smartphone, you probably know that
right now the smart phones, the usual algorithm for
smartphones is if there's a wifi network use it and
if not use the cellular, well, if you've
tried to use your smartphone while you walk around campus
here, you might have realized that's not a very
good strategy because while you're walking around campus, walking
from access point to access point, you don't get
very good data coverage at all. Um and that's
a resource management issue because because how you choose what
radio access technology you use affects the load on the
network also affects the performance that you see. And
as we add more radio access technologies to the mix
, I think this becomes a more complicated and more
important problem. But this is all taking place in
a setting where we see more and more dynamic spectrum
access. So this goes back to the Titanic story
that I mentioned a minute ago. Um, but
our current spectrum management regimes date to the early 1900s
and are primarily based on regulatory assignment of spectrum and
regulatory selection of services, technologies and sometimes even operators
. And so I think it's pretty broadly accepted,
certainly in the community of wireless resource researchers that this
is inefficient and it leads and it's not adequate to
meet future demand for wireless services and we need something
better, something more dynamic. Um This is the
picture that people have been showing for the last uh
six or seven years at least. But it shows
uh in particular, this band here shows spectrum occupancy
. I believe that one actually is measured in Dublin
. Um and you can see that some of the
spectrum bands where their cellular service are very efficiently used
. But most of the rest of the band that's
shown here looks pretty empty. And so we would
like to be able to use that spectrum much more
efficiently uh in order to provide wireless services. So
what I'm saying is clearly, um, something more
flexible than this static regulatory regime is required. Um
, but that having been said, I think,
uh, a lot of researchers in dynamic spectrum access
and a lot of research and dynamic spectrum access has
ignored, um, has ignored the benefits of the
current regulatory scheme. And those benefits are, the
current spectrum assignment is stable and predictable. And because
it's stable and predictable, you know, what frequencies
your device is going to be operating in. You
can build an efficient a well engineered, inexpensive radio
with an appropriate antenna that's perfectly fit for the spectrum
band or bands that you're going to be using.
Um, and so proposals for dynamic spectrum access have
focused on software defined radio and they focused on this
capability to use wide swaths of spectrum. Many of
you are probably enrolled in the software defined radio course
uh this semester. And while those software defined radios
give us amazing capabilities and benefits that we didn't have
before, they also typically are lower performance and less
power efficient and much more expensive than a fit for
purpose radio that was designed for a single band.
That's that's just natural. Besides all that, these
different bands tend to be suited for somewhat different purposes
anyway. Uh if you think about your high frequency
bands, they're great for use uh inside buildings where
you want to have a lot of spatial re use
, you want to be able to use the same
frequencies in this classroom as in the classroom next door
. Um whereas your lower frequencies have better building penetration
may be better for wider area coverage. And so
what I'm saying here, what I'm proposing here is
that we need some balance between this fully dynamic approach
and a static approach. So this is inefficient and
we would like to see something something better, something
more dynamic, that lets us use more of the
spectrum resources. But we need to be careful that
we don't uh that we don't forget what some of
the benefits are of having some predictability to our resource
assignments. And I think mhm mobile ad hoc networks
give us a something of a cautionary tale here because
they followed some of the same paths that we've seen
with dynamic spectrum access resource, with dynamic spectrum access
research. Um So mobile ad hoc networks were of
course the primary focus of wireless networking research for more
than a decade. And yet even today, we
don't see that many deployed outside of testbed environments and
maybe some military applications. And there are lots of
potential reasons for this. But I want to claim
to you that one of them was this idea that
we were going to be able to completely decentralize every
resource allocation problem in a mobile ad hoc networks.
And what this did is it gave us lots of
really great challenging research problems that people wrote lots of
theses and dissertations on and published lots of papers on
. But many of these problems turned out to be
intractable in practice, the solutions that we have didn't
scale to real world scenarios. And so that along
with some other reasons, I think it would be
hard to to call the Net the Monette research program
a real success, although it's certainly contributed some,
some technologies that we're now seeing applied uh, in
other places. Um, so the rest of this
talk is basically going to have two components. Uh
the first one I'm going to talk about what I
call bootstrapping. Uh and I'm gonna give you a
very specific example from some research that we did a
couple of years ago with Ryan Irwin, some of
you might know him uh that I think is an
example of bootstrapping that show. And it's for a
particular problem on channel assignment in multi hot, multi
radio, wireless networks. Um and then I'm going
to talk about another approach that I think is also
valuable to think about for resource management and these future
systems. And that's an approach that thinks about automated
negotiation in these systems and what kind what automated negotiation
might entail. Um So I'm going to tell you
a little bit about why, and then I'm gonna
give you a couple of examples of simple automated negotiation
techniques. Uh Now I think automated negotiation can be
much more than what I'm going to describe here,
but I hope it gives kind of a a sense
of the sort of simple things that we can do
that. Maybe then we can build up more complex
things in the future. Okay, so what do
I mean by bootstrapping? Well in computing, in
particular, boot strapping refers to a self sustaining process
that proceeds without external help. And in particular it
usually refers to the development or the startup of successively
more complex environments. So you turn on your pc
, it starts in a very simple state, and
that simple state is used to boot up the more
complex operating system that you actually interact with. You
see this with lots of devices, but you also
see it with development environments. So you start out
with a very simple development environment and you can use
it to help you develop tools that then lets you
do more complex things. Um And so bootstrapping,
I think as a general principle is a very pragmatic
engineering solution to try to add complexity to a system
. Um So if we think about the complex systems
that are modern wireless networks, I think we mostly
see a lack of bootstrapping. Uh and by that
, I mean we've been unwilling to use the simple
things that are already there to help us build complexity
into our systems. And so some examples of that
are again, if you look at mobile ad hoc
networks, you see people were unwilling to allow any
kind of centralization in the system, even if that
might have given them a simple point from which they
could add more complexity. Um A lot of the
early cognitive radio visions, you see this as well
? They said, oh, we won't even need
to define modulation schemes or protocols because the nodes will
negotiate and come up with their own modulation schemes and
protocols. Well, that's probably just a bit silly
. I mean, we're gonna start with some known
modulation scheme and then from that we might add complexity
, we might modify it, we might try using
a different approach. So there's one thing from the
dynamic spectrum access literature that I think does exemplify this
bootstrapping approach and that's lots and lots of solutions that
people have proposed have used control channels and dynamic spectrum
access. Um Now there's lots of problems with the
way control channels have been applied in the dynamic spectrum
access uh research literature because people have just assumed that
the control channel was always going to be, there
was always going to be available, was always going
to have adequate bandwidth to support the control for their
systems and so on. Um But that having been
said that control channel is I think an example of
bootstrapping, it's it's something simple that we can rely
on to then allow us to add complexity on top
. And so this is what I want to propose
is how many future wireless systems that are going to
have dynamic spectrum access and all of these things can
be built. And that is by relying on the
existing standards and by relying on the infrastructure that's already
been deployed for initial connection and configuration. But then
from there, being able to add complexity, being
able to use other, other standards, being able
to use other spectrum bands and so on on a
negotiated basis. So, yeah, now I want
to talk about this specific problem and our solution and
why I think of it as a kind of bootstrapping
. Um and so this is a channel assignment problem
. And the idea is that practical networks, practical
multi hop wireless networks really have to support two kinds
of traffic and you ignore this. I think at
your peril when you start to design these systems um
and the first kind of traffic that they have to
support is they have to support control traffic and sporadic
traffic. So I send a message to another user
in the network. I transfer a small file to
another user in the network. I send routing messages
to other users in the network to let them know
who my neighbors are and how I can reach them
. Um So we need this control and sporadic traffic
and we needed to be able to reach every node
in the network typically. But the other thing that
we often have in these wireless networks is high volume
applications streams. And so you might have a video
stream, you might have a large file transfer from
one user to another user, um video conferencing.
There are lots of things you can imagine that would
require pushing much more data over the network. And
so if you start to look through the channel assignment
literature for these types of systems, what you'll find
is there's sort of two approaches, uh and each
of those approaches is really suited to handling one of
these kinds of traffic, but not both of them
. So almost all the research either focuses on what
we would call traffic independent allocation schemes. And these
schemes allocate channels. And typically their primary objective is
network connectivity. Um And there's no sort of dynamic
allocation really in the network at all. Maybe they
have some ability to handle mobility and to rebuild the
network after links break or nodes disappear, but once
the topology is fixed, if the notes don't move
, the topology is fixed. And this line of
research people have developed lots of protocols, uh and
even practical implementations for topology control for building up a
network topology that will give you a connected network hopefully
with low power. Um but that's been the objective
. And then if you look around the literature,
you find another set, a whole other set of
literature, the two scarcely even reference each other that
are what we would call traffic driven allocation schemes.
And most of these are in the family of back
pressure algorithms. If you're familiar with those. And
the idea here is we only want to allocate network
resources to serve traffic. And so really the objective
of this, of the second line of research is
not to build practical protocols, but is to say
, what is the absolute carrying capacity of this network
? What's the maximum amount of traffic we can push
through the network? And how should we allocate resources
in order to support that maximum amount of traffic?
And so these back pressure based approaches say, okay
, you give me an imposed traffic load and I'll
tell you how to allocate resources in order to get
that traffic delivered. But they typically make no provision
at all for basic network connectivity. For sporadic traffic
for control traffic in the network. It's just a
problem to see what's the maximum capacity we can push
through this network. And so the ones in blue
up here, these traffic independent allocation schemes tend to
be practical, tend to be actually developing protocols that
people can use in a network. And the ones
in green tend to be almost purely theoretical. What's
the maximum capacity of this network with these particular characteristics
. But in practice, so in practice this blue
is good for that sporadic traffic and the green is
good for those high data rate flows. But in
real networks these mix, um we need to be
able to have connectivity. We need to be able
to support control traffic, but we also need to
be able to push higher volume traffic through the network
when it's demanded. And so what we've tried to
do in this work is consider these problems jointly because
they rely on a common pool of wireless resources that
has to support both this connectivity as well as the
dynamic user needs. And so this is our approach
. It's a two stage approach and at the first
stage we do some traffic independent channel assignment. So
we find out where the nodes are, what the
possible neighbors are and what their links are. And
we do channel assignment in order to give us a
topology that we call the traffic independent topology. And
then once we have that traffic independent topology on that
is imposed some flows. So these are those high
volume flows that we want to be able to push
through the network and on the basis of what the
demands are. We then try to allocate additional channels
in order to optimally support those flows at the highest
rates possible. And so, uh and then if
the flows change, we may want to change those
allocations, but we probably want to keep this traffic
independent assignment the same. So the idea is we
do a lot of our resource allocation upfront to support
baseline connectivity. These sporadic flows control traffic and so
on. But we hold some of our network resources
and reserve in order to apply them for these high
rate flows when they come along. And so to
look at this problem, we wanted to look at
it initially fairly abstract lee. And so we looked
at it as an optimization problem, particularly as a
two stage mixed any integer linear program. Uh And
I've tried to revise this talk so that I only
have to give you one version of the stage one
problem and one version of the stage two problem,
but I haven't been able to do it. Uh
So in order to show you the results that I
want to show you in a couple of slides,
I have to describe two versions of the stage one
problem. Uh and then I'll describe one version of
the Stage two problems. So the first version of
the Stage one problem that I want to describe is
what we call the alpha balanced version. And the
idea here is that you're given this parameter Alpha and
alpha ranges from 0 to 1. And it's the
proportion of your transceivers in the network That you are
allowed to use in stage one. So if alpha
is.5, that means you're allowed to use half
the transceivers in the network in order to establish this
uh this traffic independent topology. And so the goal
of this and we have this all written out informal
um optimization problem terms, but I'm not gonna lay
that on you today. But the goal of this
alpha balanced version is to maximize the connectivity of the
network. And we have a measure for connectivity that's
related to K connectivity if you're familiar with graph theory
. Um but so to maximize the connectivity subject to
an interference constraint, we don't allow channel assignments that
would create hidden nodes or undesired interference. Um and
subject to this transceiver constraint that I was talking about
this determined by alpha. So if alpha is 0.5
, then you get then you only allowed to use
a maximum of half of your transceivers in this stage
of the problem. So the other version of this
problem, which is what we're driving towards for more
practical solutions, is what we call the resource,
minimized version. And in the resource minimize version,
what we're actually trying to do is minimize the number
of transceivers we use subject to an interference constraint and
much like the one above, but this time subject
to a connectivity constraint. So now we say we
want the network to at least be connected, but
we want to do it using the minimum number of
transceivers subject to our interference constraint. Or we say
we could even say we haven't done this a lot
in practice, but we could even say we want
the network to be too connected. That is we
want there to be two independent paths between any source
and destination. Um but we want to use the
minimum number of transceivers to do it. So the
difference between these two is the alpha balanced version.
You're specifically told what portion of the resources you get
to use for Stage one. And in this resource
minimized version, you're not told that you're told minimize
the resources you use, but make the network connected
and satisfy the other constraints. So then we take
the output of this first optimization problem and that becomes
an input to stage two. And the objective of
this optimization problem at Stage two is to maximize some
flow rates for some given source destination pairs by using
the remaining transceivers, the ones that were left over
from Stage one subject to some channel sharing constraints,
which are similar to our interference constraints, uh and
some flow constraints. Um So the idea this is
where those flows are imposed on the network and we
want to see how fast we can push them through
the network. And so to give you an idea
of what comes out of this. Um Let me
show you just an example assignment for a network.
Uh So on the left is yeah, George.
Well, the thing about mps, space stations and
music, these are nodes in a mobile ad hoc
network, essentially so their mobile nodes, but they
have multiple transceivers. This problem grew out. That's
a good question, I usually mentioned that and I
forgot, but this problem grew out of the DARPA
W nan project, where there was, where there
were handheld transceivers developed, that handheld nodes developed,
I should say that each had four transceivers. Uh
And we were looking at the problem of how to
do topology control in those networks. Um So we're
mostly thinking about mobile notes. Um and so what
we have on the left here is a topology that
comes out of a of a typical uh well it's
a topology that comes out of our of our stage
one problem, but where we set alpha equal to
one and this is actually very similar to the results
that will come out of most of the topology control
algorithms that are proposed in the literature. So you
see, we kind of have this, I might
even call it hyper connected topology where we have lots
and lots and lots of links, lots and lots
of interference uh and a very, very highly connected
network because the goal typically for these algorithms was to
maximize connectivity, whereas what we have on the right
is what comes out of our stage one traffic independent
stage of our algorithm when its resource minimized. And
in this case you see a very different structure.
You see a few clusters and colors here indicate channels
by the way. Um So you see a few
clusters on a common channel and then you see some
nodes that are acting as gateways between those clusters and
you also see some extra links on different channels that
also act as connections between these different clusters. Mhm
. And so this is kind of the difference when
we look at those traffic independent assignments, So mhm
. Then we when we then look at the two
stage output. What we're gonna see is uh this
is three different things. Um The one on top
is a completely traffic independent assignment. So that's kind
of of the sort of a lot of the topology
control protocols in the literature. The one on the
bottom is a completely traffic driven assignment. So that's
kind of like the back pressure based algorithms and so
on in the literature. And then the one in
the middle is what we came up with. So
let me tell you a little bit about how to
read these these graphs. Um So all of the
dots here are nodes, but the ones with the
bigger dots, circles on top and triangles on the
bottom, our sources and destinations. And you can
tell it's a little hard to see. I know
, but you can tell by the color that's in
the middle of those uh which source goes with which
destinations. So there are I think there are four
or maybe five source destination pairs shown here. Um
And then the links, the solid links are the
traffic independent links. So those are assigned in stage
one and the dotted ones are the traffic driven links
and so on. Top, we have a completely
traffic independent assignment. Like I said, you get
from most Monette protocols that are out there now and
it just makes the network as connected as possible and
then does its best with those links to push traffic
from the source to the destination. And you can
think of these as relative flow rates normalized to the
amount of flow that a single link can carry And
the maximum flow rate they can achieve between those sources
and their destinations is.67. Um down on the
bottom we have that completely traffic driven assignment where we
look at the source destination pairs and we construct the
links we need in order to maximize the flow from
those sources to those destinations. And we don't construct
any other links. You can see lots of the
nodes there, don't have any links attached to them
at all Because they're not needed for those optimal paths
from the sources to the destinations. And so in
this case you assign some channels uh to create those
links that you need, uh and you get a
flow rate of 1.6. Like I said again,
this is normalized to the flow rate of a single
link. And then what's in the middle is what
we have proposed, where first you construct this resource
, minimized Uh this resource minimized traffic independent topology and
that's the solid lines again. Uh and in this
case that uses about 37 of the available 60 radios
in the network. I think there are 20 nodes
here and I think that each of them has three
transceivers. Um and then you get to turn on
some of the additional transceivers to help you support traffic
from the sources to the destinations. And what we
find out here is, and this is you're going
to see in the results in a minute. This
actually turns out to be fairly typical. We can
get a flow rate just as high with our proposed
scheme, as you do with the traffic driven scheme
, but you get this fully connected topology which you
can use for control traffic and sporadic traffic essentially for
free. Mhm. So by only assigning some of
the resources dynamically, we get all of the benefits
of dynamic assignment, but without the costs of not
having a connected topology for control traffic. Is that
to engender or is it for this particular? Well
, it is absolutely true for this particular instance.
Now let me show you some average results that give
you, I mean, they're still simulation results but
but their simulation results based on this optimization model,
um to give you an idea of what happens with
more generality. Um So this is the flow rate
and the black bars here are is the only the
traffic independent topology. And the white bars here is
only the traffic driven approach where you only assign links
to support particular source destination pairs. And then the
gray is what we get from our approach, which
we call traffic aware. And then on the X
axis here we have three different scenarios with 23 and
four transceivers per node. Um so we were really
surprised when we first got these results, um because
what we found was that when we had three or
four radios per node, uh we had a flow
rate just as high as the traffic driven scheme.
Uh in the vast majority of cases with our traffic
aware scheme, um when we only had two transceivers
per node, we do much better than the traffic
independent approach, but not quite as well as the
completely traffic driven. So um this was averaged over
1000 network realizations uh and running an M I L
P solver to solve those um those optimization problems that
I told you about earlier. So we wanted to
start to understand why this was uh and to start
to understand what we might be able to do with
it. And so we started to look at this
issue of resource balance. Uh And in particular we
looked at the proportion of radios that were allocated,
or sorry, we set the proportion of radios that
were allocated in stage one and we looked at the
impact both on the connectivity and on the flow rate
. Um and so what you can see here and
the and the curves here are for 22 transceivers,
three transceivers and four transceivers per node. Um And
what you can see here is that as that proportion
of radios allocated traffic independently increases the connectivity actually increases
quite quickly. Uh Exactly where that increase occurs depends
on whether you have 23 or four radios per node
, because it's essentially a function of how many radios
do you need in order to achieve a particular level
of connectivity? But it happens fairly sharply with four
radios per node. It happens somewhere around 30 of
those radios allocated with only two radios per node,
you need a little over 50 of them allocated to
traffic independently before you achieve even one connectivity. Um
But then flow rate we see a very different story
and that is the flow rate. So when we're
at zero here, that means we get to allocate
whatever transceivers we want dynamically. And when we're at
one we get to allocate none of them dynamically.
But what we see here is that at least for
the three and 4 radio promote case The flow rate
holds up surprisingly well all the way up to 80
or 90 even of the radios being statically allocated.
So what is this telling us? It's telling us
the vast majority of the benefits from dynamic resource allocation
in these networks is coming from dynamic allocation of a
small percentage of the resources. So by dynamically allocating
only 20 or 30 of the resources in the network
, we get all of the benefits that we could
achieve if we tried to allocate them all dynamically,
but with none of but with little of the hassle
. And so that's what I refer to here as
bootstrapping, because we built a network where we can
take advantage of this traffic independent topology for our control
traffic and for our sporadic traffic, um but then
we've held us we can hold a small amount of
those resources in reserve to dynamically allocate. Uh and
when we do that, we get the vast majority
of the benefits of dynamic allocation. Um is this
generalised able to other resource allocation scenarios? It's hard
to say. Um But that's something that I'm very
interested in continuing to look at uh in the future
. Now, I'm running a little behind where I'd
like to be. So in the interest of time
, I'm going to kind of skip over the next
few slides, where I say a little bit more
about the efforts we've made to try to take this
approach and to develop it into a practical protocol and
some practical algorithms that might be able to be run
in a real network. So just to say that's
something we have been working on and we've made some
considerable progress on uh is moving away from this just
optimization problem formulation and to some real protocols that do
this kind of thing, there's some cost to that
, but not as bad as you might think.
And so then I want to take the last 10
minutes that I have here to talk about this other
topic, which is automated negotiation. And tell you
a little bit about what I mean by that.
And then, like I said at the beginning,
give you a couple of very simple examples of um
of applying what I think of as types of automated
negotiation uh in these systems, um so with shrinking
cell sizes and very dense wifi deployments, the number
of network elements we have in our wireless networks is
really exploding uh and it's becoming very difficult to manage
these networks. So if you talk to people in
CNS about the network on campus, uh they will
tell you that this is one of the biggest problems
is that they have uh something on the order of
tens of thousands of deployed devices on the campus.
And how do they manage all those devices? Make
sure they're all configure it configured correctly, detect and
route around faults when they occur. Um because a
lot of times you could have a device that's mis
configured and you don't find out its mis configured until
you're in a failure failure situation where you suddenly are
expecting the device to do something that other than what
it usually does and it doesn't do so. And
so we need self organization in these networks in order
to support this kind of scale. Um And the
interactions between these elements are also becoming more complicated.
As we think about dynamic spectrum, as we think
about uh multiple uh multiple network elements that are sharing
the same spectrum being an L. T or or
in wifi systems uh and so on. Um and
in that context we also know that interference is a
local phenomenon. Now that doesn't necessarily mean that you
can find a global optimum locally, but it does
suggest that in a lot of cases that's where you
should look. If you have an interference problem,
you should probably be looking for an interfere. Er
that's relatively close to you certainly in these low power
kinds of networks and so you may be able to
negotiate with another node in the network in order to
achieve a solution that reduces your interference, let's say
. And so this is the subject of some new
research that I undertook while I was at C T
V R. And that we're just starting to develop
into some papers, but the idea being that these
nodes in a dynamic spectrum access system may need to
negotiate with each other about interference limits and so on
and that that may allow us to obtain more efficient
resource allocations then we could otherwise. And so now
I'm going to talk very briefly about two recent pieces
of work from my students that I think illustrate a
simple version of automated negotiation. Um So the first
of those pieces of work is on coalition formation in
mobile ad hoc networks. Um and this is some
work that Amber Hilal is doing. Um many of
you probably know armor. Um but the nets require
note cooperation. There are a lot of schemes in
the literature that seek to get this node cooperation that
seek to incentivize nodes to cooperate in a man yet
. Um and most of those can be put into
two categories either credit based or reputation based. Uh
But we actually pursue another approach which is based on
coalitions and that is nodes voluntarily join coalitions that agree
to forward packets for each other and they only do
this if it's in their best interest to do so
. And so the rule that these coalitions use in
our particular case is a node will forward any packet
that's sourced by or destined to a member of its
coalition. Uh and then we study the performance of
this scheme under mobility and that's really uh so this
idea of using coalitions to manage um to manage cooperation
in a man yet is not our idea, but
what is new in our work is looking at what
happens to these coalitions when the nodes move, What
happens under my mobility. And so this is what
happens in these uh in this, in this work
is coalition form initially and then nodes move mobility occurs
and when these nodes move this breaks some of the
coalition's it breaks the coalitions in two ways. The
first way is that we require our coalitions to be
connected. So if mobility moves the members of a
coalition around such that they're no longer directly connected,
then we say that's not a coalition anymore, it's
broken into pieces. Um And the other thing that
happens is after this topology changes, there may be
notes that don't want to be a member of their
coalition anymore, They may have voluntarily joined this coalition
, but now the coalition structure has changed, the
note says uh it's not beneficial to me to be
part of this coalition anymore, so I'm gonna quit
, I'm gonna leave. Um and so we have
mobility, it breaks the coalitions and then we allow
very limited opportunities for the nodes to try to re
form some coalitions and then they move again. So
mobility happens, we offer limited opportunities for coalitions to
reform and then there's mobility again. And the main
thing we look at in these networks is reach ability
. So can these coalitions maintain reach ability in these
networks? And what we find is that these coalitions
can maintain reach ability of about 90%, depending mostly
on no density. Some of the other parameters matter
a little bit, but not as much. Um
but the most interesting thing uh that we actually see
here is that mobility actually improves reach ability over what
we would get in a static scenario with the same
coalition formation approach. And the reason for that is
coalitions are maintained in the network that would never be
formed in a static scenario. So I've joined a
coalition then mobility happens and now I'm in a coalition
that I wouldn't have joined in this case, but
things are not so bad that I want to quit
, it's kind of the way to look at it
. Um And so why do I think of this
as a kind of proto or initial automated negotiation?
Because these nodes are making decisions about which coalitions to
join and they're negotiating with other coalitions about merging their
coalitions. Um So the way this coalition formation process
works is a node makes an are you can think
of it as a coalition makes an offer to another
coalition? Uh Should we, I'd like to propose
that we merge our coalitions and then the other member
, a representative of the other coalition replies, yes
, we agree to merge or no we don't.
So this is an automated interactive process between these nodes
to decide what coalitions to form and to maintain.
So the second example of automated negotiation that I want
to give here is an auction. So at auction
again is a very constrained type of negotiation, but
it is a negotiation of sorts. And so this
is a former student of mine, Mohammed bidis who
did this work to study a multi source, multi
relay cooperative network where you have the source nodes and
they're all trying to communicate with a common destination.
And there are some relays out there, but we
don't know exactly how we want the relays to allocate
their power between source nodes. Um And the way
transmission works here is in the broadcast phase, each
source node. Broadcasted symbol and the cooperation phase,
the relays for Millennia Network code based on the power
allocation they've decided on and transmit it to the destination
. And so what we designed here was what's called
an ascending clock auction, where the relays announce their
prices and the sources reply with how much relay power
they want to request from each relay. And then
there's a simple scheme but too complicated to describe in
the two minutes that I have left that credits some
of that power to the sources and increases the price
if demand exceeds the available power. And it turns
out that this very simple auction procedure can converge to
an equilibrium that maximizes the some rate in the system
, which is one of the objectives that you might
design a centralized power allocation algorithm to do. So
. Again, another simple example of a type.
A constrained type, but a type of automated negotiation
between nodes that achieves uh some of the resource allocation
goals that we might have if we were in a
centralized system. And these are the simulation results.
The main thing they show is that you get the
same thing from the auction that you would from a
centralized algorithm. Uh And they also show that in
the scenario which has shown up in the upper left
sort of happens, what what you might expect to
happen, which is that? Top Source node mostly
uses the relay node over on the right in the
middle there. Uh And the bottom left node mostly
uses the relay more to the uh more to the
to the left and then the source node in the
middle actually does the best because it's sort of able
to play the two relays off of each other and
make use of both of them in a way that
other nodes can't. So those are two brief examples
in which a simple automated negotiations scheme leads to kind
of interesting outcomes. But what if we're interested in
trying to apply this in more complicated problems? Well
, I want to contend to you that there are
two tools that are worth thinking about and they're related
to each other and one of them is one that
I've used for a long time, which is game
theory. So game theory is a bag of analytical
tools to help us understand what happens when decision makers
interact with each other. Well, as nodes and
wireless networks become more and more autonomous, it becomes
more and more important that we analyze their interactions as
autonomous decision makers. And so game theory gives us
some of the tools to be able to do.
That gives us a mathematical basis for doing that.
So, something I'm very interested in applying in future
work but have made limited progress with so far is
actually a sub field of game theory called mechanism design
. And mechanism design sounds like a perfect fit for
engineering problems because it studies how you can achieve desirable
social outcomes given the constraints of self, industry interested
individuals and incomplete information. Um The problems in the
past have been that a lot of the results in
mechanism design or negative results. The proposed mechanisms are
sometimes computational intractable. Uh and application is usually has
sometimes proven difficult. But in the last few years
, algorithmic computer science has made enormous progress on mechanism
design and on overcoming some of these problems. And
so I think we finally have some techniques that might
realistically make their way into real systems uh for designing
interaction mechanisms for actually designing protocols that have a theoretical
basis uh in accomplishing the system designers goals even though
the individual nodes are self interested. Um So I
want to contend to you that this is an interdisciplinary
challenge I want to encourage you to reach outside of
e. Ce two tools and economics and computer science
and even to consider some of the public policy implications
of of some of these kinds of approaches and what
they might mean. Um And with that I can
try to take a few questions and I will stop
. Thank you. Yeah. Mhm. I will
also put up a slide that gives source material for
most of what I've talked about today. Are there
any questions? Mhm. Yeah. Yeah, I
think somebody asked me a hard question. Mhm.
Mhm. Yeah. What is it was you want
to get? Mm? Mm Yeah, you did
event and Uh huh Yeah, yeah, probably hard
. Mm um it's a good question. So if
you knew up front what the traffic was going to
be imposed on the system, then could you do
better by jointly deciding by jointly making all the decisions
? Um I don't really know the answer to that
question. I think probably you could you could certainly
right down the you could certainly right down the uh
the optimization problem. And I don't I don't think
that's something we even did because we have the optimization
problem for maximizing the flow rates, but we never
said and you must also be connected which you could
add that and you can see what the outcomes would
be. Uh My intuition is it wouldn't lead to
very practical protocols though because we have the information,
we need to construct that traffic independent topology, usually
earlier than we know exactly what the traffic flows are
that are going to be imposed on the network.
And even if the topology stays the same, the
traffic flows are probably going to change at a shorter
time scale. So. Okay. I mean,
then you get into even more interesting should we be
changing our traffic independent topology on the basis of the
flow of the demands that have been imposed on the
network? And that's the problem we haven't approached yet
, but maybe it's something good to think about.
All right. Thank you very much for coming.
Have a good day. Yeah.