thanks very much. It's really a pleasure to be
here this morning. I have often said, I
don't think we have as much interaction as we should
here at Virginia tech between computer science and electrical computer
engineering. So it's really nice to be here.
And to tell you a little bit about uh my
work um as was mentioned actually, quite a bit
of my work is sponsored by the National Science Foundation
, but the work I'm talking about today is uh
is not at least not at this point. Um
what I'm gonna spend most of the time talking about
today actually was not really even funded by DARPA,
but uh a student was working on the DARPA project
and then when that project was over, just kept
working on this without direct sponsorship, but it extends
some work that was sponsored by DARPA uh through BBN
Technologies and of course we're grateful to them. Um
and then at the end I'm going to talk about
really what I'm hoping to be working on the problem
. I mainly hoping to be working on uh next
year when I'm planning to be on sabbatical assuming those
those final approvals come through. Um And so this
is just kind of some preliminary ideas and things that
I've been thinking about that I think have a lot
of uh connections to computer science as well. Um
Also like to thank some collaborators of course. Uh
It's uh it's graduate students who do a lot of
the work of research and the work I'm gonna be
talking most of the time about today was done by
Ryan Irwin who's a PhD student who is almost finished
his co supervised by luiz da silva, another faculty
member in the C. E. O. And
myself. Um And then uh some of the future
work uh has come through conversations with linda Doyle at
trinity college Dublin. Uh And uh and her group
the C. T. V. R. Um
But of course other students as well have have certainly
contributed a lot to my interest in these problems and
my thinking about them. Um So like I said
in the abstract even I'm going to talk about two
things to diane. I'm gonna spend most of my
time on the first one. But then just say
a little bit about the second one which is more
future work at the end. And so most of
the time today I want to talk about a channel
assignment problem uh in a multi hop multi radio multi
channel wireless network. And so I'll give you some
of the motivation for why we're interested in that problem
. Um And then I'll talk about uh about what
we see is critical to coming up with more practical
solutions to this problem. Which is how you balance
the resource assignment between assignments that you do in a
traffic independent manner. And I'll say more about what
I mean by that in a few minutes and resource
assignment or channel assignment mostly that you do in a
traffic driven manner. And so after I've talked and
presented some results on on why it's a good idea
to do both of these uh to to try to
balance the two. Um I'll say I'll say some
about our proposal the algorithm or technique that we proposed
for the traffic independent assignment. And then I'll mention
briefly the work that that's ongoing on coming up with
the right distributed algorithms for the traffic driven assignment.
Um And then at the end I'll talk about uh
about how some of these same ideas, loose ideas
, I think uh connect to a problem in dynamic
spectrum assignment. And I think it's uh I think
it's maybe a way of thinking about problems and to
some extent a critique of the way we sometimes go
about them uh uh in research um and just some
ideas that I have about about how we might be
able to come up with more practical, more effective
uh solutions. Um So here is um so here
is a rough idea of a multi hop wireless network
. Um and the slide really states something that's pretty
obvious here I guess. And that is the practical
networks need to support two things. They need to
support control traffic in order to organize and keep the
network together and sporadic traffic between nodes, be that
short messages or even you can imagine email or occasional
uh web requests or instant messages whatever. And then
they also need to be able to support high volume
application streams, so be that video or streaming audio
or something that is going to consume a large or
file transfer, something that's going to consume a significant
amount of network resources over a significant period of time
. And in general mobile ad hoc networks, which
is what this network I've drawn up here is basically
an example of have been very bad at that um
have been very bad at being able to support both
of those. Um so let me tell you a
little bit about the model that I'm working in.
Um what I'm assuming here is that notes have multiple
transceivers and each of those transceivers is a half duplex
transceiver that can be tuned to a single channel at
a single time. And so in most of the
examples here, I'm going to be talking about nodes
with the 23 or four transceivers. Um the DARPA
project we were working on had hardware knows that we're
supposed to have four independent transceivers but at the time
are part of the project finished, which was at
this point probably 18 months ago, you can only
get two of them to really work at the same
time. But when people but with people thinking more
and more about multi channel networks and dynamic spectrum access
networks and so on, it's clear that in a
lot of wireless networks you're going to have multiple transceivers
on a node and you're gonna need to be able
to make use of that. So we're gonna have
since we've got these multiple transceivers you can potentially to
tune to multiple channels at the same time. But
we are going to assume that the time required to
change channels is significantly longer than the time that's required
to send a packet. Um some of the work
that's on dynamic spectrum and channel allocation and so on
, and so forth, assumes that you're able to
completely reconfigure the network on a on a packet by
packet basis and we think that's kind of impractical.
So then the network itself has multiple available channels to
support traffic. Uh this could be even something like
eight oh 2.11 where you might have three orthogonal channels
, or we're really thinking more about a narrow band
system where you might have more channels than that.
But for the moment, for the work I'm talking
about mostly today, we're thinking about a fixed set
of channels. So something that a lot of people
have been doing research on for the last five years
or so is where your channel availability is changing and
you might sense that part of the spectrum was free
and try to go there. That's mostly not what
I'm talking about in this first part of the talk
. So links are formed in this network when transceivers
that are close enough to each other, uh select
a common channel. So if you've got two nodes
and they each have a transceiver tuned to the same
channel and if they're close enough to each other in
the simulations and so on, we've done, then
they can establish a link and can communicate with each
other. Um What we've used though is what's sometimes
called a double disc model. So notes that are
close enough, I can communicate with notes that are
some farther distance away are going to interfere with my
communication, but my receive power from them is not
strong enough for me to communicate with them directly.
Um Okay, so we're assuming here also that radio
costs are significant. This also gets neglected in a
lot of the work. A lot of the work
says, well I've got multiple transceivers, so I'm
going to turn them all on and tune into some
channel. Well, it turns out that even if
you've got to know that has four transceivers on it
. Turning on those transceivers is a pretty expensive operation
and keeping them running is a pretty expensive operation.
And so you'd really like to turn some off if
they're not needed and only turn them on on an
as needed basis. Um And I'm mostly gonna be
talking about in a network like this today, the
channel assignment problem. Now, some of the things
I'm going to talk about could also apply to power
control in a network like this. Um could look
at uh at controlling the topology, could look at
choosing modulation scheme or coding scheme and so on.
But I'm going to focus today on channel allocation.
Okay. So given that we're gonna look at channel
allocation in a network like this, the first question
that we have asked um kind of repeatedly over the
last few years and working on this is is well
, what else is out there? What else is
out there for assigning channels in a multi transceiver,
multi channel kind of network? And while there's lots
and lots of stuff on channel assignment, there's there's
a somewhat lesser amount on this multi transceiver problem where
each node is potentially on a finite number, but
more than one channel. But there is some work
out there and it almost all comes down to two
main categories, and one of those is what what
we've termed traffic independent allocation schemes. Um A lot
of this research has gone under the name of topology
control, although some of that's just power control,
um and not not really looking at the channel assignment
. Um but once those channels are assigned in these
traffic independent schemes, um they say basically the same
. And so the goal of those uh those algorithms
of those systems is to get the network connected.
It might be to get the network multiply connected in
some way, um but it doesn't respond in any
way to traffic, so if there's any dynamics is
um at all in these systems, it comes maybe
from assuming that nodes might move around and so you
might have to rearrange network to account for node mobility
, but not to account for network traffic. Typically
at the other end of the spectrum is research that's
looked at what we have termed a traffic driven allocation
scheme and what this work, and a lot of
it is in the category of what are called back
pressure algorithms where the allocations in the network are driven
by the few links in the network. Um But
this work is focused on allocating resources dynamically on basically
an instantaneous basis, uh in response to the current
traffic demand. And the point of most of this
work, although some work has gone and tried to
make these schemes more practical, but the point of
most of this work was not even to try to
be practical, but to say if we had perfect
resource allocation, what would the capacity of the network
be? How much traffic could we push through the
network? If we had if we could instantaneously reallocate
resources through the network. Um And so what we
have then is we have, on the one hand
, these traffic driven allocation schemes, which are perfectly
fine for putting together a network that's connected and you
can pass control traffic or short messages around but are
not very high capacity. If you're trying to push
video streams, say through the network, and then
you have these these proposals that I think even their
authors would admit or not even intended to be practical
, um That would help you maximize the capacity of
a wireless network uh to support some particular flows,
but that but that don't even strive to give you
kind of a baseline connectivity for passing control traffic around
and keeping the network operating. And in practice,
you need a network that can do both of those
. If you think about DARPA or D O.
D scenario with a bunch of uh a bunch of
, say, soldiers in the field with radios,
well, they want to maintain constant communication for short
traffic as well as potentially stream of video across the
network or something like that. But I think that's
true of almost all of these uh all practical deployments
of ad hoc networks. Um And so so we're
gonna be sharing the same pool of resources, most
likely in order to support both this control traffic and
this high volume traffic. And so as a result
, I think you almost have to consider those two
problems jointly. And so that's what we've tried to
do. So the basic of are the basics of
our approach here, I think is pretty intuitive,
and that is that we're gonna use some minimal amount
of resources in the network in order to keep the
network connected. And then we're gonna reserve other resources
for responding dynamically to traffic demands in the network.
Um And so we've divided this into two stages,
both conceptually as well as in um some of the
numerical results that I'll show you in a few minutes
where stage one is what we call the traffic independent
stage. And in this stage we seek to maximize
network connectivity using some portion of the radio transceivers in
the network. Or in some cases we seek to
uh achieve some particular level of connectivity using the minimum
amount of resources, but in either case the upshot
is that we've got a connected network, um multi
channel, multi transceiver, potentially. Um but that
that has kept some of those resources in reserve in
order to deploy in response to traffic. And so
that's our second stage is a traffic driven channel assignment
, which is, there are some flows that are
imposed, some traffic flows, some some quote large
or significant traffic flows that are imposed on the network
. And we're gonna make some additions to that traffic
independent assignment in order to better support uh, those
flows. And so what I'm going to talk about
first is we've kind of come up with an optimization
model, mixed any er, to stage mixed integer
linear programming model to try to look at the performance
of the strategy in general as compared to a fully
traffic independent or fully traffic driven strategy as well as
how should we strike that balance? How much of
our resources do we need to allocate to keeping the
network connected and running and so on? Um,
Okay. So this is um, I'm not gonna
put optimization problems up today. Maybe I should have
, this is uh, this is maybe the right
crowd for optimization problems and uh, pseudo code algorithms
and so on and so forth. But I'm trying
to keep this at a relatively high level. Um
, and if you're interested in the details, I'll
show some references at the end. I'm happy to
send you papers where we developed these ideas in more
detail. But the general model that we've looked at
is what we think of as a two stage mixed
integer linear program. And I'm not claiming that,
uh, that implementing this, uh, mixed integer
linear programming is the way you would actually go about
carrying out this strategy. That wouldn't be very practical
at all. I'm going to talk about some distributed
algorithms to do these two stages in a few minutes
. But what we're trying to do is assess how
well would a network work if we use the two
stage approach like this? And so two stages stage
one corresponds to to the first stage over here.
In Stage two corresponds to the second stage. So
traffic independent and traffic dependent. And I'm going to
talk a little bit about two versions of the traffic
independent M I L P I'm just kind of flagging
this for your reference because you might see me jump
back and forth a little bit between the two.
Um The main one we're really proposing for use in
real systems is is this bottom one here? What
I'll think of as the resource minimize version where the
goal is to minimize the number of transceivers that you
use uh subject to some interference constraints. We're not
going to allow uh we're not gonna allow many interferes
. In some cases. You have to allow some
and a connectivity constraint. Um And for the results
, I'm gonna show, we look at making the
network one connected, but you could just as easily
decide, oh, I want my baseline network to
always be too connected and I can show you can
show you what difference that will make in a minute
. But I have this other version up at the
top because I sat in a couple of minutes ago
. one of the things we also wanted to see
is, well how much of my resources should I
allocate to the traffic independent part of the network?
Verses? Should I keep in reserve for dynamic allocation
to the network? And so that's the reason for
this top version up here. What I've chosen at
this point to call the alpha balanced version. So
this one has a parameter called alpha and alpha ranges
from 0 to 1. And it's the proportion of
transceivers in the network that are allocated in a traffic
independent fashion. So if alpha is equal to zero
, then you save all your transceivers for dynamic allocation
. And if alpha is equal to one, uh
then you save none of them, You use them
all in the traffic independent phase and there's nothing left
when you get to stage two. Um And so
then what we do in stage two is we solve
a flow routing problem, kind of? Almost the
standard flow routing problem. Uh Given the allocation that
was done in stage one is fixed, but you
can make additional channel assignments in stage two, in
order to best support the set of flows. That's
that's their that's given to you. And so this
is to try to max so for the imposed flow
rates and for the results, I'm gonna show today
what we do is we take the network and we
impose a particular number of flows and we say,
well, all these flows have to be maintained at
the same rate. And what's the maximum I can
turn up that rate and still have the network.
Be able to support those flows if I assign some
additional channels to help me do this. Um Okay
, okay. Um so this is just a quick
example to give you a brief idea of what we're
talking about here. So over on the left side
is something that you might see out of, wow
, this looks different on the screen, but um
but something you might see as the result of a
conventional traffic independent channel assignment algorithm that takes all the
resources in the network and tries to allocate them in
a traffic independent manner. Um Typically we'll talk about
in a minute, but these are either trying to
maximize the connectivity or they're trying to minimize the interference
, um but they're gonna allocate every single transceiver in
the network to some channel uh and and try to
achieve their goals that way. And um so one
of the things you see on the left side here
is this does, tends to in some cases lead
to so colors here indicate different channels for different links
, um and this tends to lead to what are
called clicks or fully connected sub graphs on particular channels
because that tends to minimize interference because our concept of
interference here is a node that can that you might
have to time share with, that might interfere with
you on a particular channel, but that you can't
directly communicate. Um and so what you see here
is you see a very densely connected network, um
but with all the resources allocated on the right,
you have a solution from what I called on this
page. This resource minimized version of Stage one,
where it says I want to achieve a connected network
, but I want to do so using the fewest
possible number of transceivers. And so what you see
there is you get a few clicks or near clicks
at least on a particular channel and then some some
links between them. So this is if you've worked
in ad hoc networking, you know that a lot
of the algorithms, there are clustered algorithms and this
kind of gives you good justification for why that might
be because this performs pretty well. We've got these
clusters on the same channel and then we have what
you can think of as cluster heads that handle these
cross cluster communications. And so then what we get
if we run it through this two stage, um
, M I L p upon top we have the
results when alpha is equal to one. So that's
the case where all the resources are assigned in the
traffic independent manner. And so our stage one does
all of the channel assignment. Well, I should
tell you a little bit about these figures. The
solid lines and these figures are traffic independent assignments of
channels. And then the dotted lines are those that
are assigned in stage two in the traffic dependent uh
phase. And so the top the top one is
all traffic independent assignment. So it's all solid links
and the bottom one is all traffic dependent, so
it's all dotted links. And then the one in
the middle is our proposal where we've got a traffic
independent allocation, but then we make some traffic dependent
adjustments to it. Um One other thing I guess
to say about these figures is the darker circles or
triangles. I guess in the bottom two are the
sources and destinations of the flows. And it's pretty
hard to see up here, but the color inside
the circle tells you which flow, that's the source
or destination for and it's not really connected to the
colours for the channel assignment. Okay, so what
happens here? Um This is 20 nodes? Um
Part of my notes are covered up here, but
I want to say 20 nodes, I want to
say four transceivers on each node and about 10 available
channels. Um and so what happens here is alpha
equal to one up here, which is where we've
done a completely traffic independent assignment of channels. The
fact that we can't adapt to the flows greatly limits
the maximum flow rate of those flows through the network
. And so what's achieved here is indicated there is
a flow rate of 0.67 I should say the flow
rates here are normalized. We assume that all of
the wireless links have the same rate capacity. And
so the flow link are, sorry, the flow
rate is normalized to the rate of a single link
. So it's how much flow can you push through
all of these assigned uh Source destination pairs? Uh
with respect to how much goes on a single on
a single link. And so if you assign all
the channels in advance, you get this flow rate
of.67 at the other extreme, what we know
to be optimal in terms of flow rate is if
you if you saw for all I care about is
running these flows through the network, then you find
that you can support more than uh more than twice
that with a flow rate of 1.6. Because what
you wind up with this multiple paths um for each
source destination pair, remember that each note has multiple
transceivers. And so it's potentially uh putting out that
flow on multiple transceivers at the same time. So
, so what you also see though in this completely
traffic driven assignment at the bottom is some nodes are
not getting channel assignments at all because it's not optimal
to make use of them in forwarding this particular traffic
. Um And then you see our proposal in the
middle where you have a traffic independent assignment which just
strives to connect the network and then on top of
that you impose some additional links in response to traffic
demands. And what happened in this particular cases were
able to achieve uh the same flow rate as in
the optimal case, but we have this background,
if you will, or baseline fully connected network to
support control traffic or short message traffic, uh things
like that. Um And so even though we have
assigned more than half 37 out of 60 radio,
so I guess it must have been three transceivers per
note. Um uh even though we've assigned more than
half of the transceivers upfront for this traffic independent purposes
were still able to achieve the same flow rate as
in the optimal case. And this is a little
bit surprising to us. We expected there would be
some price to pay for holding back some of those
transceivers to use in a traffic independent uh fashion,
but as we'll see on some results in a minute
, in many cases there's there's very little or no
price to pay for it. Um this kind of
shows the same thing, but whereas this is a
particular scenario, this is averaged over thousands of realizations
of the network. Um so thousands of times we've
we've thrown nodes down in our simulation area and figured
out what the potential links are and solve the traffic
independent problem, uh and then and then solve the
stage to traffic driven problem. And what's shown here
is uh averaged over all those runs the maximum flow
rate um for the traffic driven and traffic independent schemes
at the extremes and the traffic aware in the middle
. And you can see the three sets along the
X axis here are the number of transceivers that each
node has, and you can see that when each
note only has two transceivers, there's a price to
be paid in terms of network capacity for for doing
this traffic independent assignment up front. But once we
get to three or four transceivers, it's possible to
connect the network in an interference free way and still
have enough transceivers left over to achieve to achieve the
same maximum flow rate as you can if you try
to use all of your transceivers dynamically. And so
that was a little surprising to us and we are
pleased by it because we think it invalidates um it
validates are thinking about how we might want to go
about solving this resource allocation problem. So this is
the one slide I was referring to with that alpha
controlled uh allocation where the proportion of transceivers that we
use for the traffic independent stages alpha. And we
try to get the maximum capacity that we can with
that many transceivers. And so the top graph shows
a metric that we call K prime connectivity. If
you're familiar with the graph theory, you you've heard
of cake, a cake connected network and a network
is K connected if there are K link independent paths
between every pair of nodes. And so we are
we've modified that metric a little bit to give us
some more granularity here where we've said, okay,
I've got that K connected network but then I'm also
going to look at what's the proportion of those source
destination pairs that have more than K independent paths between
them. And so like a K prime here of
2.5 would mean, well every source destination pair has
at least two independent paths, but half of the
source destination pairs have at least three. So that's
our that's our metric of connectivity because we wanted something
a little more fine grained here and you can see
what happens as you increase exactly as you would expect
as you increase the proportion of radios that are devoted
to this traffic independent allocation, the connectivity goes up
. Um And so but but what may be most
important here is if you look at that horizontal line
there that's drawn at one is once you especially for
three and four radios per node. Uh It's it's
a it's a relatively small proportion even even at two
radios promote, it's only about half of the radios
that you need to achieve this interference free um connected
allocation. So if you are interested in saying making
that this is the graph to look at, if
you say, well, I think 11 connected baseline
network is not good enough because these nodes are moving
and so links are going to fail and our channels
are not very reliable and so I want to build
the baseline topology that's too connected. Well, what
the top graph here tells you is even if you
want to go up to a two connected network,
especially for three and four transceivers, you could still
have a lot of your transceivers in reserve for traffic
driven approach. So the bottom graph here then looks
again at at the at the maximum flow rate that
you can push through the network again for two radios
per node. Three radios promote and four radios per
node. And when you're way over here at the
left side, you're talking about a fully uh fully
traffic um driven approach to channel assignment. And you
see that um adding additional radios per node helps you
a little bit, but not a great deal.
Uh And then as you move to the right,
um as you move to the right, you're using
more and more of those nodes traffic independently. And
of course your flow rate is going down, but
especially for the two and three radio note cases,
it's not going down very quickly. So. All
right. So, I mean, so what we've
really tried to establish here is using this to stage
M I L. P. Is that this traffic
aware approach is viable. It's a promising way to
obtain high network capacity while maintaining connectivity. So most
of those network capacity gains come from allocating a relatively
small proportion of the resources in response to dynamic traffic
. Um And so what we've been doing since we
did this work is trying to come up with practical
way is to implement these two phases. Um And
so I'm going to talk about those now. And
so the first one of those is associated with stage
one here. How should we do the traffic independent
assignment? So as I mentioned a little bit earlier
in the literature, the common approaches to this traffic
independent resource assignment or channel assignment in a network um
are are do not attempt to conserve resources. They
either try to maximize connectivity for some measure of connectivity
or they try to minimize interference in some way by
the way they assigned channels. But the goal is
you give me four transceivers and 10 channels. I'm
going to use every transceiver on every node assigned to
some channel. So our approach tries to do something
different. Um resource, minimize channel assignment is what
we call it. And the goal is to minimize
resource usage, subject to constraints on how much connectivity
we're requiring ourselves to achieving the network and how much
interference we're willing to allow, how many interfere,
how many interfering channel assignments we allow to be made
in the network. So this is the slide where
I guess I could have put up some pseudo code
, especially for this audience, but I decided not
to do that. But the algorithm is actually very
simple. The nodes take turns selecting channels. And
when a node select the channel it tries it takes
one of its transceivers that's not already assigned and it
tries to assign it to a channel that yields the
greatest number of new neighbors. So the greatest number
of nodes that I'm within communication range of, but
I didn't but I wasn't connected to before because we
didn't share a common channel, so tries to maximize
the number of new neighbors, but with sort of
two caveats, the first one being, I'm never
going to make a channel assignment that that I know
to be interfering uh with some other node in the
network. So that that is I'm never going to
choose a channel where there's gonna be someone out there
in my interference range on the same channel, but
that I'm not in communication range of And the second
thing is nodes stop doing this, they stop even
assigning new channels. Um once they are, once
they know that every note that they're in communication range
of is within either one or two hops in the
network as it's constructed. So it's a very simple
concept here. Many of the other traffic independent assignment
schemes are as well. Um but it's kind of
based on local information. If you send out some
neighbor discovery packets, you can find out most of
what you need to know in order to get,
you can find out all of what you need to
know in order to implement this. Um So what
happens if we compare this to approaches in the literature
? Um the graph on the left side here is
the number of transceivers used. It shouldn't be a
great surprise that all of these other techniques are not
even trying to um to conserve transceiver usage, which
I mentioned at the beginning is important. Even if
you're not going to use them dynamically, these transceivers
are expensive to operate, the more you turn on
, the faster you drain your battery and things like
that. But that hasn't been a goal in the
past. And so we're able to use um in
some cases many fewer transceivers than the other multi transceiver
schemes that are out there, you can see that
if you only have two transceivers per node, we
only do a little bit better than those other schemes
, but if you have three or four transceivers per
node, then we're still using about on average 1.5
transceivers per node. Whereas the other schemes for the
most part are just taking all those transceivers and using
them. The exception to that being the click based
um scheme here, which often runs into scenarios where
there's just no additional clicks that can be formed and
so it leaves some of the transceivers off and on
the right side here shows the connectivity and what you'll
see here is that our our scheme and this is
this is basic cake connectivity, it's not the k
prime connectivity that I was talking about before, but
it's averaged over many runs. So you don't necessarily
get integer values here, but you'll see that we
are much less connected than many of these other schemes
, which is not a surprise since a lot of
the other schemes are striving to maximize connectivity. But
what I want to point out here is um and
you can't see it on the graph, but we're
keeping the network one or two connected 1998% of these
runs. Um whereas some of these other schemes,
especially for three and four transceivers, um I guess
I should say this graph is two transceivers and this
graph is four transceivers are. Well, I guess
even the true transceiver case are especially in this high
dense that we have, we have three different deployment
densities of nodes here, especially in the high density
case are doing what I would call over connecting the
network. We're getting networks that are 10 and 12
connected. Now you can make a case to me
that you want your network to be two or three
connected to provide some robustness but I'm not sure you
ever really want to network to be 10 or 12
connected. Um at least not for the applications that
I'm most interested in and here's some more results from
this in terms of conflict and interference. Um I
mean two different things by conflict and interference here by
conflict. I mean essentially how many nodes are you
sharing the channel with? So even if I have
if I got a click and it's got a bunch
of nodes in it. Well, all those notes
can communicate with each other, but they have to
time share the channel somehow. Often through a carrier
sense multiple access kind of mechanism. And so this
left graph here looks at how many nodes in my
conflict ng with and the right graph looks at how
many interfere ear's are there. So interferes are sort
of worse than conflicts because interferes or knows that you
have to share the channel with, but in general
you can't really quite see. Um so they're out
there causing you interference and so you can't transmit at
the same time. They do. But CSM a
schemes for instance, don't really resolve that because you
, you may not be able to detect them well
enough to know not to transmit when they're transmitting.
So it's kind of a hidden node kind of phenomenon
. And you can see that r M C A
performs quite well on both of these metrics. Um
, It doesn't, it has a few more.
It has a few interferes, but not very many
. Sometimes we get trapped in cases where we have
to allow some interference in order to achieve our connectivity
goals. Um and it has a relatively low uh
relatively low number of conflict in nodes. So once
you get a network that's 10 or 12 connected,
you're also going to have a very high no degree
in the conflict graph. So lots of nodes sharing
the same channel. Okay, so that's that's sort
of the bulk of the completed work that I'm going
to talk about, although this this next slide is
work that we're doing right now as we speak and
we sort of have some preliminary results. Um and
so in some sense, the traffic independent piece of
this is the easy piece. The easy pieces.
How do you assign channels ignoring traffic? The hard
piece is how do you respond to traffic in the
network in a dynamic fashion? Um And this is
hard even for a fully traffic uh fully traffic driven
scheme, like a back pressure scheme. It's it's
hard to implement. And so our approach has been
this one because we are so two things that that
kind of drive this approach. The first one is
um some some research results, both recent and stretching
back 10 or 15 years, showing that most of
the traffic flows in real deployed networks are heavy tailed
. So something like 90% of the traffic in http
responses is coming from about 10% of the requests.
Um And this is also driven. Um This is
also driven by the fact that we're mostly thinking of
I. P. Like data gram. Kind of
networks where nobody tells you explicitly I'm gonna set up
a flow so you have to implicitly figure out when
flows are happening in the network so that you can
respond appropriately. And so this is what we've been
simulating even in the last couple of weeks is trying
to identify significant flows just by listening to the traffic
in your neighborhood as well as looking at the traffic
going through your node and tracking the source destination pairs
of those say I. P. Data grams in
order to figure out which ones of them are responsible
for most of the traffic. So that's one piece
of it. Is how do you recognize the flows
that are coming through or coming near your node?
And the second piece of it is how do you
respond without having a full global view of the network
? And so this is what we've been looking at
as well. And our approach here has been to
construct a local version of that stage to M I
L P, where the only thing I get to
change our channel assignments in my neighborhood. So I'm
only looking at traffic flows that come through my neighborhood
. And I'm only looking at channel assignments in my
neighborhood and saying what's the best thing I could do
in terms of new channel assignments that would improve the
performance for these flows that I've seen. And our
preliminary results are that while you can't quite track the
global M I L. P, you can see
dramatic improvement. And what we've mostly been measuring here
is average packet delay. And the reason for that
is even though we're optimizing for these big flows,
when those big flows are not handled appropriately, they
introduce all this queuing delay even for the short messages
. And so if you can handle those better than
you see, much improved delay performance for short messages
as well. So now I want to talk about
for just a few minutes, something completely different.
But that I think is is somehow related, at
least at the, at the macro scale. And
so this is the first slide which people have been
using a slide similar to this a lot in my
research community anyway for the last five plus years,
where they say, okay, current spectrum management regimes
date back to the early 19 hundreds there, based
on regulatory assignment by the FCC, if someone else
of spectrum bands and typically based on regulatory determination of
what the services are that can operate in those bands
. What technologies can be used to deliver those services
, and even what operators are allowed to use those
bands to deliver services with the assigned technology. So
that's kind of the picture up there in the top
right that you can't quite see. But we take
the radio spectrum and we say, okay, this
band is for satellite communications and this band is um
and this band is for cellular operations and this band
is for um this band is for microwave, point
to point links and so on and so forth.
And it can be easily shown largely by doing some
spectrum measurements that this technique that this and so these
these these regulatory allocations change extremely slowly over the course
of decades or in some cases with broadcast television even
50 years or more. And so you can pretty
easily show with the spectrum analyzer that you have not
done a good job of efficiently allocating these resources because
you can listen and you can find that even though
the entire spectrum is allocated, most of the spectrum
opportunities in any given place and time are going unused
. So maybe I made an allocation to the military
for communication with military aircraft. Well, unless you're
sitting on an Air Force base, you probably don't
see a lot of communication in that band. Uh
, the other thing that happens with these allocations,
I'm gonna talk about public safety a little bit more
in just a minute. But the other thing that
happens in public safety bands is I have to allocate
enough channels, uh, for incident response and for
big events. Um, even though those are going
to be used most of the time, the Virginia
Tech Police Department has two main channels and most days
they use one, they use their second channel,
football, game day and commencement day. They might
use it for big home basketball games. I don't
know, I don't remember, but they don't use
it very often. They use it for incident kind
of control in response, but it's sitting out there
unused the rest of the time. And this is
true across the vast majority of the, of the
spectrum. And you can particularly see that in some
of these waterfall plots here. Like the one in
the middle on the bottom here, the X axis
is a frequency band, the Y axis is time
. And um, and you can see that many
of those channels you saw little or no activity on
. But then at the far right there, those
are actually cellular bands and you can see those were
extremely busy except those, those little white blocks are
in the middle of the night. And so people
have been, have been making a pitch like this
for the last five plus years and they said,
so we need something totally dynamic. We need to
be able to listen and detect the spectrum is free
and then use it and we need radios that can
operate over the entire spectrum band. And we need
for regulators to allow us to do all of these
dynamic things. But the regulatory response while regulators are
excited about more flexible spectrum allocation, the regulatory response
from a technologist point of view has been kind of
um kind of slow and kind of kind of weak
. What's what's been allowed in the tv band now
is okay, you can use unused tv channels but
you've got to connect via some wired means to a
data base out on the internet to see what's being
used in your area. Before you get to do
this, you can't just rely on sensing, it's
not good enough. And fundamentally the reason for this
is because the technologies, even though people have been
doing research on this for five plus years, the
technologies to answer the hard problems of how do you
reallocate everyone all at the same time? How do
you develop radios that are sufficiently dynamic and so on
? The technology has not developed and there's a lot
of incumbent vested interest in this um in this spectrum
allocation being the way that it's sort of always been
. And so the end result is the pace of
the spectrum regulation. Innovation has been pretty slow and
it turns out that there are a lot of benefits
to the current regime. Um And one of those
is tied really to radio engineering. Because the current
spectrum assignment I get a stable, predictable assignment.
So my smartphone only has to be built to work
on a handful of different bands and can be well
engineered to access those bands and others. So this
leads to efficient, well engineered fit for purpose inexpensive
radios allocated to appropriate bands for what it is that
they want to do. And so a lot of
the proposals for dynamic spectrum access has focused on software
defined radio and the idea has been, everyone's gonna
have a radio that goes from what the E.
S. A. D. C. To daylight
. But anyway, something like 100 megahertz, 23
gigahertz. And it turns out that those radios are
difficult to build. And I'm not saying the technology
is not progressing here, it certainly is. But
in general, if you look at a software defined
radio and a regular in a regular radio with more
customized hardware, the software defined radio is going to
be lower performance, higher cost, lower power efficiency
. And and that doesn't even mention the fact that
the laws of physics really constrain your antenna design.
So it's difficult. Some would say impossible to design
a small handheld antenna that can go from 100 megahertz
, 23 gigahertz. And at the same time,
these different bands are really suited in many cases for
very different purposes. Those high bands have relatively low
propagation, 2.4 gigahertz turns out to be pretty good
band for wifi because it's relatively constrained by buildings and
rooms and so on. Um something down at 100
megahertz, on the other hand, spills out everywhere
because buildings are basically transparent. And so we really
need techniques and this is where I draw a similarity
with the other problem. We really need techniques that
do both that recognize the value of some stability in
the spectrum assignment, but that also allow for some
flexibility, particularly, I would say, on the
margins. And so here's an example from paper from
last year's uh dice ban. Um If you talk
to the public safety people going back to that public
safety example, many of them will tell you that
they need both of these bans. The PSST here
is uh it's obscured here, but it's a public
safety. The public safety Spectrum Trust Band. And
then they'll tell you they also need the D block
, which is another part of the 700 megahertz spectrum
. Well, what's shown in this paper is that
actually those two bands would be nearly perfect for sharing
between say smartphone users and public safety. And this
is shown by developing in some detail in this paper
three scenarios. The top scenario is an everyday use
scenario where even most of that public safety spectrum trust
band is not being used. So these are public
safety users on the right and their um smartphone,
say users on the left. Um So on an
ordinary day public safety is not even using most of
that public safety Spectrum Trust Band. Um On in
an incident response kind of scenario, you would expect
the usage of public safety to grow maybe even into
that D block. But I think most of us
in society would be comfortable with that. Um If
the police and the emergency services need more spectrum right
now to respond to an incident were willing to give
it to them. And then the bottom is a
is a is a wide scale wide area catastrophe scenario
. Um That would happen a very, very small
percentage of the time where most of these two bands
get occupied by public safety. And so this is
an example that illustrates flexibility and spectrum used. But
in a context where the radios can still be built
to operate over a relatively narrow uh portion of the
spectrum. And so and and some of the newer
radio technologies like L T. E, actually make
this very possible um for an allocation, I mean
you need some control over over who's using what,
what band win, but it seems very technologically doable
, but I want to contend that one of the
things that we need in order to enable this kind
of spectrum sharing on the margins is to recognize that
interference between radio systems is a local phenomena. And
so the solutions and a lot of cases need to
be local as well. And I mean both.
I mean that both geographically, I'm going to make
some agreement with this other operator near me as well
as in spectrum, I'm not going to jump probably
from a 100 megahertz allocation to a 1.5 gigahertz allocation
. And so one possible technology that I think can
contribute to this and that I want to spend some
more time looking at over the next year is automated
negotiation between radio systems. And one of the reasons
that I wanted to talk about this here is I
think that this is a very interdisciplinary challenge that draws
on um tools and techniques from a lot of different
fields. Obviously there's electrical and computer engineering to contribute
to the radio engineering, the communications theory as well
as the networking, but there's also a big contribution
here, I think from computer science, in terms
of distributed artificial intelligence and multi agent systems. And
how do we go about building these systems where we
have intelligent agents that cooperate with each other? There's
also a role to play. And this is a
background with some of my other research. But I
didn't talk about it today for economics? What are
the incentives for these users to cooperate with each other
and to share spectrum And and what are their incentives
when they're negotiating with each other? And that comes
into game theory as well as mechanism design, which
also has a lot of impact on computer science these
days. And auction theory designing auctions as well.
And finally, public policy is a big piece of
this. How do you convince regulators? How do
you convince current legacy spectrum holders that this is in
their best interests and that new spectrum management regimes that
do things like this are worthwhile? So I got
a little bit longer than I thought I might.
This is the first time I've given this particular talk
. But what I did for most of the time
here was showed you some promising results that we've been
working on the last couple of years on a traffic
aware approach to channel assignment in a multi transceiver wireless
network. And we've seen that most of the capacity
gains from dynamic channel assignment really come from reallocating a
relatively small proportion of the resources. Um And then
I introduced towards the end here, dynamic spectrum assignment
problem where we think that automated negotiation is one approach
to give you some sort of some flexibility at the
margins through a local process of spectrum management and renegotiation
between the notes and and that's a critical um technology
that I'm interested in. Um And my work on
that is obviously just uh just beginning and I hope
that you'll maybe invite me back in 18 months or
two years and I can tell you, uh,
more about it. So with that I'll wrap up
. These are references mostly from the material I presented
in the actually exclusively the material I presented in the
first half here. Um, a couple of these
are published and a couple of them are under review
. But if you're interested in them, I'm happy
to send you pre prints. Um, and with
that, I'm open to questions here or you're welcome
to, you know, uh, yeah. Thing 980 --> A:middle L:90% .