WEBVTT
1
00:00:05.940 --> 00:00:09.150 A:middle L:90%
thanks very much. It's really a pleasure to be
2
00:00:09.150 --> 00:00:11.310 A:middle L:90%
here this morning. I have often said, I
3
00:00:11.310 --> 00:00:14.089 A:middle L:90%
don't think we have as much interaction as we should
4
00:00:14.089 --> 00:00:18.129 A:middle L:90%
here at Virginia tech between computer science and electrical computer
5
00:00:18.129 --> 00:00:20.730 A:middle L:90%
engineering. So it's really nice to be here.
6
00:00:20.730 --> 00:00:24.160 A:middle L:90%
And to tell you a little bit about uh my
7
00:00:24.160 --> 00:00:27.769 A:middle L:90%
work um as was mentioned actually, quite a bit
8
00:00:27.769 --> 00:00:30.429 A:middle L:90%
of my work is sponsored by the National Science Foundation
9
00:00:30.429 --> 00:00:33.289 A:middle L:90%
, but the work I'm talking about today is uh
10
00:00:33.299 --> 00:00:35.509 A:middle L:90%
is not at least not at this point. Um
11
00:00:35.520 --> 00:00:37.950 A:middle L:90%
what I'm gonna spend most of the time talking about
12
00:00:37.950 --> 00:00:40.750 A:middle L:90%
today actually was not really even funded by DARPA,
13
00:00:40.750 --> 00:00:43.659 A:middle L:90%
but uh a student was working on the DARPA project
14
00:00:43.659 --> 00:00:45.380 A:middle L:90%
and then when that project was over, just kept
15
00:00:45.380 --> 00:00:49.320 A:middle L:90%
working on this without direct sponsorship, but it extends
16
00:00:49.320 --> 00:00:53.229 A:middle L:90%
some work that was sponsored by DARPA uh through BBN
17
00:00:53.229 --> 00:00:56.119 A:middle L:90%
Technologies and of course we're grateful to them. Um
18
00:00:56.119 --> 00:00:57.899 A:middle L:90%
and then at the end I'm going to talk about
19
00:00:57.909 --> 00:01:00.329 A:middle L:90%
really what I'm hoping to be working on the problem
20
00:01:00.329 --> 00:01:03.149 A:middle L:90%
. I mainly hoping to be working on uh next
21
00:01:03.149 --> 00:01:06.969 A:middle L:90%
year when I'm planning to be on sabbatical assuming those
22
00:01:06.980 --> 00:01:10.079 A:middle L:90%
those final approvals come through. Um And so this
23
00:01:10.079 --> 00:01:12.409 A:middle L:90%
is just kind of some preliminary ideas and things that
24
00:01:12.409 --> 00:01:15.569 A:middle L:90%
I've been thinking about that I think have a lot
25
00:01:15.579 --> 00:01:19.640 A:middle L:90%
of uh connections to computer science as well. Um
26
00:01:19.650 --> 00:01:22.730 A:middle L:90%
Also like to thank some collaborators of course. Uh
27
00:01:22.739 --> 00:01:26.609 A:middle L:90%
It's uh it's graduate students who do a lot of
28
00:01:26.609 --> 00:01:29.430 A:middle L:90%
the work of research and the work I'm gonna be
29
00:01:29.430 --> 00:01:32.239 A:middle L:90%
talking most of the time about today was done by
30
00:01:32.239 --> 00:01:34.650 A:middle L:90%
Ryan Irwin who's a PhD student who is almost finished
31
00:01:34.650 --> 00:01:38.750 A:middle L:90%
his co supervised by luiz da silva, another faculty
32
00:01:38.750 --> 00:01:41.310 A:middle L:90%
member in the C. E. O. And
33
00:01:41.310 --> 00:01:44.109 A:middle L:90%
myself. Um And then uh some of the future
34
00:01:44.109 --> 00:01:49.000 A:middle L:90%
work uh has come through conversations with linda Doyle at
35
00:01:49.000 --> 00:01:52.689 A:middle L:90%
trinity college Dublin. Uh And uh and her group
36
00:01:52.700 --> 00:01:53.180 A:middle L:90%
the C. T. V. R. Um
37
00:01:53.189 --> 00:01:57.140 A:middle L:90%
But of course other students as well have have certainly
38
00:01:57.140 --> 00:02:00.000 A:middle L:90%
contributed a lot to my interest in these problems and
39
00:02:00.000 --> 00:02:02.329 A:middle L:90%
my thinking about them. Um So like I said
40
00:02:02.340 --> 00:02:05.290 A:middle L:90%
in the abstract even I'm going to talk about two
41
00:02:05.290 --> 00:02:07.150 A:middle L:90%
things to diane. I'm gonna spend most of my
42
00:02:07.150 --> 00:02:08.789 A:middle L:90%
time on the first one. But then just say
43
00:02:08.789 --> 00:02:12.110 A:middle L:90%
a little bit about the second one which is more
44
00:02:12.110 --> 00:02:15.169 A:middle L:90%
future work at the end. And so most of
45
00:02:15.169 --> 00:02:16.150 A:middle L:90%
the time today I want to talk about a channel
46
00:02:16.150 --> 00:02:21.900 A:middle L:90%
assignment problem uh in a multi hop multi radio multi
47
00:02:21.900 --> 00:02:24.520 A:middle L:90%
channel wireless network. And so I'll give you some
48
00:02:24.520 --> 00:02:28.939 A:middle L:90%
of the motivation for why we're interested in that problem
49
00:02:28.979 --> 00:02:32.069 A:middle L:90%
. Um And then I'll talk about uh about what
50
00:02:32.069 --> 00:02:36.500 A:middle L:90%
we see is critical to coming up with more practical
51
00:02:36.500 --> 00:02:38.080 A:middle L:90%
solutions to this problem. Which is how you balance
52
00:02:38.319 --> 00:02:43.080 A:middle L:90%
the resource assignment between assignments that you do in a
53
00:02:43.080 --> 00:02:46.069 A:middle L:90%
traffic independent manner. And I'll say more about what
54
00:02:46.069 --> 00:02:47.620 A:middle L:90%
I mean by that in a few minutes and resource
55
00:02:47.620 --> 00:02:52.139 A:middle L:90%
assignment or channel assignment mostly that you do in a
56
00:02:52.139 --> 00:02:54.800 A:middle L:90%
traffic driven manner. And so after I've talked and
57
00:02:54.800 --> 00:02:59.430 A:middle L:90%
presented some results on on why it's a good idea
58
00:02:59.430 --> 00:03:01.004 A:middle L:90%
to do both of these uh to to try to
59
00:03:01.004 --> 00:03:05.525 A:middle L:90%
balance the two. Um I'll say I'll say some
60
00:03:05.525 --> 00:03:09.485 A:middle L:90%
about our proposal the algorithm or technique that we proposed
61
00:03:09.495 --> 00:03:15.004 A:middle L:90%
for the traffic independent assignment. And then I'll mention
62
00:03:15.004 --> 00:03:16.854 A:middle L:90%
briefly the work that that's ongoing on coming up with
63
00:03:16.854 --> 00:03:21.844 A:middle L:90%
the right distributed algorithms for the traffic driven assignment.
64
00:03:21.854 --> 00:03:24.254 A:middle L:90%
Um And then at the end I'll talk about uh
65
00:03:24.264 --> 00:03:29.104 A:middle L:90%
about how some of these same ideas, loose ideas
66
00:03:29.104 --> 00:03:31.155 A:middle L:90%
, I think uh connect to a problem in dynamic
67
00:03:31.155 --> 00:03:36.264 A:middle L:90%
spectrum assignment. And I think it's uh I think
68
00:03:36.264 --> 00:03:38.134 A:middle L:90%
it's maybe a way of thinking about problems and to
69
00:03:38.134 --> 00:03:40.895 A:middle L:90%
some extent a critique of the way we sometimes go
70
00:03:40.895 --> 00:03:45.444 A:middle L:90%
about them uh uh in research um and just some
71
00:03:45.444 --> 00:03:46.875 A:middle L:90%
ideas that I have about about how we might be
72
00:03:46.875 --> 00:03:51.115 A:middle L:90%
able to come up with more practical, more effective
73
00:03:51.125 --> 00:03:58.764 A:middle L:90%
uh solutions. Um So here is um so here
74
00:03:58.764 --> 00:04:02.125 A:middle L:90%
is a rough idea of a multi hop wireless network
75
00:04:02.134 --> 00:04:05.594 A:middle L:90%
. Um and the slide really states something that's pretty
76
00:04:05.594 --> 00:04:09.985 A:middle L:90%
obvious here I guess. And that is the practical
77
00:04:09.985 --> 00:04:13.164 A:middle L:90%
networks need to support two things. They need to
78
00:04:13.164 --> 00:04:15.524 A:middle L:90%
support control traffic in order to organize and keep the
79
00:04:15.524 --> 00:04:20.125 A:middle L:90%
network together and sporadic traffic between nodes, be that
80
00:04:20.134 --> 00:04:26.204 A:middle L:90%
short messages or even you can imagine email or occasional
81
00:04:26.214 --> 00:04:30.074 A:middle L:90%
uh web requests or instant messages whatever. And then
82
00:04:30.074 --> 00:04:32.384 A:middle L:90%
they also need to be able to support high volume
83
00:04:32.384 --> 00:04:38.035 A:middle L:90%
application streams, so be that video or streaming audio
84
00:04:38.045 --> 00:04:40.944 A:middle L:90%
or something that is going to consume a large or
85
00:04:40.944 --> 00:04:44.074 A:middle L:90%
file transfer, something that's going to consume a significant
86
00:04:44.074 --> 00:04:47.555 A:middle L:90%
amount of network resources over a significant period of time
87
00:04:47.595 --> 00:04:50.535 A:middle L:90%
. And in general mobile ad hoc networks, which
88
00:04:50.535 --> 00:04:53.935 A:middle L:90%
is what this network I've drawn up here is basically
89
00:04:53.935 --> 00:04:57.444 A:middle L:90%
an example of have been very bad at that um
90
00:04:57.454 --> 00:05:00.384 A:middle L:90%
have been very bad at being able to support both
91
00:05:00.384 --> 00:05:01.415 A:middle L:90%
of those. Um so let me tell you a
92
00:05:01.415 --> 00:05:03.714 A:middle L:90%
little bit about the model that I'm working in.
93
00:05:03.725 --> 00:05:08.324 A:middle L:90%
Um what I'm assuming here is that notes have multiple
94
00:05:08.334 --> 00:05:12.954 A:middle L:90%
transceivers and each of those transceivers is a half duplex
95
00:05:12.954 --> 00:05:15.605 A:middle L:90%
transceiver that can be tuned to a single channel at
96
00:05:15.605 --> 00:05:17.605 A:middle L:90%
a single time. And so in most of the
97
00:05:17.605 --> 00:05:19.814 A:middle L:90%
examples here, I'm going to be talking about nodes
98
00:05:19.814 --> 00:05:24.514 A:middle L:90%
with the 23 or four transceivers. Um the DARPA
99
00:05:24.514 --> 00:05:27.425 A:middle L:90%
project we were working on had hardware knows that we're
100
00:05:27.425 --> 00:05:30.089 A:middle L:90%
supposed to have four independent transceivers but at the time
101
00:05:30.089 --> 00:05:31.990 A:middle L:90%
are part of the project finished, which was at
102
00:05:31.990 --> 00:05:34.379 A:middle L:90%
this point probably 18 months ago, you can only
103
00:05:34.379 --> 00:05:36.089 A:middle L:90%
get two of them to really work at the same
104
00:05:36.089 --> 00:05:40.439 A:middle L:90%
time. But when people but with people thinking more
105
00:05:40.439 --> 00:05:44.050 A:middle L:90%
and more about multi channel networks and dynamic spectrum access
106
00:05:44.050 --> 00:05:46.209 A:middle L:90%
networks and so on, it's clear that in a
107
00:05:46.209 --> 00:05:48.509 A:middle L:90%
lot of wireless networks you're going to have multiple transceivers
108
00:05:48.519 --> 00:05:50.819 A:middle L:90%
on a node and you're gonna need to be able
109
00:05:50.819 --> 00:05:56.699 A:middle L:90%
to make use of that. So we're gonna have
110
00:05:56.709 --> 00:06:00.040 A:middle L:90%
since we've got these multiple transceivers you can potentially to
111
00:06:00.040 --> 00:06:01.839 A:middle L:90%
tune to multiple channels at the same time. But
112
00:06:01.839 --> 00:06:04.279 A:middle L:90%
we are going to assume that the time required to
113
00:06:04.279 --> 00:06:09.300 A:middle L:90%
change channels is significantly longer than the time that's required
114
00:06:09.300 --> 00:06:12.829 A:middle L:90%
to send a packet. Um some of the work
115
00:06:12.829 --> 00:06:15.680 A:middle L:90%
that's on dynamic spectrum and channel allocation and so on
116
00:06:15.680 --> 00:06:16.790 A:middle L:90%
, and so forth, assumes that you're able to
117
00:06:16.790 --> 00:06:19.769 A:middle L:90%
completely reconfigure the network on a on a packet by
118
00:06:19.769 --> 00:06:23.790 A:middle L:90%
packet basis and we think that's kind of impractical.
119
00:06:25.089 --> 00:06:28.709 A:middle L:90%
So then the network itself has multiple available channels to
120
00:06:28.709 --> 00:06:30.759 A:middle L:90%
support traffic. Uh this could be even something like
121
00:06:30.759 --> 00:06:34.399 A:middle L:90%
eight oh 2.11 where you might have three orthogonal channels
122
00:06:34.410 --> 00:06:38.779 A:middle L:90%
, or we're really thinking more about a narrow band
123
00:06:38.779 --> 00:06:41.110 A:middle L:90%
system where you might have more channels than that.
124
00:06:42.040 --> 00:06:44.639 A:middle L:90%
But for the moment, for the work I'm talking
125
00:06:44.639 --> 00:06:46.879 A:middle L:90%
about mostly today, we're thinking about a fixed set
126
00:06:46.879 --> 00:06:48.290 A:middle L:90%
of channels. So something that a lot of people
127
00:06:48.290 --> 00:06:51.009 A:middle L:90%
have been doing research on for the last five years
128
00:06:51.009 --> 00:06:56.209 A:middle L:90%
or so is where your channel availability is changing and
129
00:06:56.209 --> 00:06:58.439 A:middle L:90%
you might sense that part of the spectrum was free
130
00:06:58.439 --> 00:07:00.350 A:middle L:90%
and try to go there. That's mostly not what
131
00:07:00.350 --> 00:07:04.160 A:middle L:90%
I'm talking about in this first part of the talk
132
00:07:04.589 --> 00:07:10.790 A:middle L:90%
. So links are formed in this network when transceivers
133
00:07:10.790 --> 00:07:13.620 A:middle L:90%
that are close enough to each other, uh select
134
00:07:13.620 --> 00:07:15.550 A:middle L:90%
a common channel. So if you've got two nodes
135
00:07:15.550 --> 00:07:17.689 A:middle L:90%
and they each have a transceiver tuned to the same
136
00:07:17.689 --> 00:07:20.449 A:middle L:90%
channel and if they're close enough to each other in
137
00:07:20.449 --> 00:07:23.389 A:middle L:90%
the simulations and so on, we've done, then
138
00:07:23.389 --> 00:07:26.410 A:middle L:90%
they can establish a link and can communicate with each
139
00:07:26.410 --> 00:07:30.050 A:middle L:90%
other. Um What we've used though is what's sometimes
140
00:07:30.050 --> 00:07:32.149 A:middle L:90%
called a double disc model. So notes that are
141
00:07:32.149 --> 00:07:34.949 A:middle L:90%
close enough, I can communicate with notes that are
142
00:07:34.949 --> 00:07:38.490 A:middle L:90%
some farther distance away are going to interfere with my
143
00:07:38.490 --> 00:07:42.189 A:middle L:90%
communication, but my receive power from them is not
144
00:07:42.189 --> 00:07:44.569 A:middle L:90%
strong enough for me to communicate with them directly.
145
00:07:44.939 --> 00:07:48.709 A:middle L:90%
Um Okay, so we're assuming here also that radio
146
00:07:48.709 --> 00:07:53.470 A:middle L:90%
costs are significant. This also gets neglected in a
147
00:07:53.470 --> 00:07:55.310 A:middle L:90%
lot of the work. A lot of the work
148
00:07:55.310 --> 00:07:57.139 A:middle L:90%
says, well I've got multiple transceivers, so I'm
149
00:07:57.139 --> 00:07:58.930 A:middle L:90%
going to turn them all on and tune into some
150
00:07:58.930 --> 00:08:01.480 A:middle L:90%
channel. Well, it turns out that even if
151
00:08:01.480 --> 00:08:03.930 A:middle L:90%
you've got to know that has four transceivers on it
152
00:08:03.069 --> 00:08:07.769 A:middle L:90%
. Turning on those transceivers is a pretty expensive operation
153
00:08:07.769 --> 00:08:09.540 A:middle L:90%
and keeping them running is a pretty expensive operation.
154
00:08:09.689 --> 00:08:11.810 A:middle L:90%
And so you'd really like to turn some off if
155
00:08:11.810 --> 00:08:15.009 A:middle L:90%
they're not needed and only turn them on on an
156
00:08:15.019 --> 00:08:18.904 A:middle L:90%
as needed basis. Um And I'm mostly gonna be
157
00:08:18.915 --> 00:08:20.644 A:middle L:90%
talking about in a network like this today, the
158
00:08:20.644 --> 00:08:24.435 A:middle L:90%
channel assignment problem. Now, some of the things
159
00:08:24.435 --> 00:08:26.975 A:middle L:90%
I'm going to talk about could also apply to power
160
00:08:26.975 --> 00:08:28.845 A:middle L:90%
control in a network like this. Um could look
161
00:08:28.845 --> 00:08:33.764 A:middle L:90%
at uh at controlling the topology, could look at
162
00:08:33.774 --> 00:08:35.955 A:middle L:90%
choosing modulation scheme or coding scheme and so on.
163
00:08:37.024 --> 00:08:39.725 A:middle L:90%
But I'm going to focus today on channel allocation.
164
00:08:41.004 --> 00:08:46.934 A:middle L:90%
Okay. So given that we're gonna look at channel
165
00:08:46.934 --> 00:08:50.184 A:middle L:90%
allocation in a network like this, the first question
166
00:08:50.184 --> 00:08:54.735 A:middle L:90%
that we have asked um kind of repeatedly over the
167
00:08:54.735 --> 00:08:56.985 A:middle L:90%
last few years and working on this is is well
168
00:08:56.985 --> 00:08:58.254 A:middle L:90%
, what else is out there? What else is
169
00:08:58.254 --> 00:09:01.565 A:middle L:90%
out there for assigning channels in a multi transceiver,
170
00:09:01.565 --> 00:09:05.205 A:middle L:90%
multi channel kind of network? And while there's lots
171
00:09:05.205 --> 00:09:07.315 A:middle L:90%
and lots of stuff on channel assignment, there's there's
172
00:09:07.315 --> 00:09:11.514 A:middle L:90%
a somewhat lesser amount on this multi transceiver problem where
173
00:09:11.524 --> 00:09:16.615 A:middle L:90%
each node is potentially on a finite number, but
174
00:09:16.625 --> 00:09:18.615 A:middle L:90%
more than one channel. But there is some work
175
00:09:18.615 --> 00:09:22.975 A:middle L:90%
out there and it almost all comes down to two
176
00:09:22.975 --> 00:09:26.245 A:middle L:90%
main categories, and one of those is what what
177
00:09:26.245 --> 00:09:30.404 A:middle L:90%
we've termed traffic independent allocation schemes. Um A lot
178
00:09:30.404 --> 00:09:33.595 A:middle L:90%
of this research has gone under the name of topology
179
00:09:33.595 --> 00:09:35.095 A:middle L:90%
control, although some of that's just power control,
180
00:09:35.105 --> 00:09:39.455 A:middle L:90%
um and not not really looking at the channel assignment
181
00:09:39.465 --> 00:09:43.475 A:middle L:90%
. Um but once those channels are assigned in these
182
00:09:43.475 --> 00:09:48.195 A:middle L:90%
traffic independent schemes, um they say basically the same
183
00:09:48.195 --> 00:09:50.705 A:middle L:90%
. And so the goal of those uh those algorithms
184
00:09:50.705 --> 00:09:54.024 A:middle L:90%
of those systems is to get the network connected.
185
00:09:54.274 --> 00:09:58.794 A:middle L:90%
It might be to get the network multiply connected in
186
00:09:58.794 --> 00:10:01.070 A:middle L:90%
some way, um but it doesn't respond in any
187
00:10:01.070 --> 00:10:03.679 A:middle L:90%
way to traffic, so if there's any dynamics is
188
00:10:03.679 --> 00:10:07.190 A:middle L:90%
um at all in these systems, it comes maybe
189
00:10:07.190 --> 00:10:09.629 A:middle L:90%
from assuming that nodes might move around and so you
190
00:10:09.629 --> 00:10:11.659 A:middle L:90%
might have to rearrange network to account for node mobility
191
00:10:11.899 --> 00:10:15.909 A:middle L:90%
, but not to account for network traffic. Typically
192
00:10:16.710 --> 00:10:20.070 A:middle L:90%
at the other end of the spectrum is research that's
193
00:10:20.070 --> 00:10:24.429 A:middle L:90%
looked at what we have termed a traffic driven allocation
194
00:10:24.429 --> 00:10:28.190 A:middle L:90%
scheme and what this work, and a lot of
195
00:10:28.190 --> 00:10:31.110 A:middle L:90%
it is in the category of what are called back
196
00:10:31.110 --> 00:10:33.820 A:middle L:90%
pressure algorithms where the allocations in the network are driven
197
00:10:33.820 --> 00:10:39.019 A:middle L:90%
by the few links in the network. Um But
198
00:10:39.019 --> 00:10:45.169 A:middle L:90%
this work is focused on allocating resources dynamically on basically
199
00:10:45.169 --> 00:10:48.360 A:middle L:90%
an instantaneous basis, uh in response to the current
200
00:10:48.360 --> 00:10:52.259 A:middle L:90%
traffic demand. And the point of most of this
201
00:10:52.259 --> 00:10:54.379 A:middle L:90%
work, although some work has gone and tried to
202
00:10:54.379 --> 00:10:56.889 A:middle L:90%
make these schemes more practical, but the point of
203
00:10:56.889 --> 00:10:58.080 A:middle L:90%
most of this work was not even to try to
204
00:10:58.080 --> 00:11:01.250 A:middle L:90%
be practical, but to say if we had perfect
205
00:11:01.250 --> 00:11:05.600 A:middle L:90%
resource allocation, what would the capacity of the network
206
00:11:05.610 --> 00:11:07.139 A:middle L:90%
be? How much traffic could we push through the
207
00:11:07.139 --> 00:11:11.429 A:middle L:90%
network? If we had if we could instantaneously reallocate
208
00:11:11.429 --> 00:11:16.120 A:middle L:90%
resources through the network. Um And so what we
209
00:11:16.120 --> 00:11:18.870 A:middle L:90%
have then is we have, on the one hand
210
00:11:18.870 --> 00:11:22.039 A:middle L:90%
, these traffic driven allocation schemes, which are perfectly
211
00:11:22.039 --> 00:11:24.799 A:middle L:90%
fine for putting together a network that's connected and you
212
00:11:24.799 --> 00:11:28.360 A:middle L:90%
can pass control traffic or short messages around but are
213
00:11:28.360 --> 00:11:31.070 A:middle L:90%
not very high capacity. If you're trying to push
214
00:11:31.080 --> 00:11:35.059 A:middle L:90%
video streams, say through the network, and then
215
00:11:35.059 --> 00:11:37.120 A:middle L:90%
you have these these proposals that I think even their
216
00:11:37.120 --> 00:11:41.049 A:middle L:90%
authors would admit or not even intended to be practical
217
00:11:41.059 --> 00:11:43.279 A:middle L:90%
, um That would help you maximize the capacity of
218
00:11:43.279 --> 00:11:48.389 A:middle L:90%
a wireless network uh to support some particular flows,
219
00:11:48.440 --> 00:11:52.529 A:middle L:90%
but that but that don't even strive to give you
220
00:11:52.539 --> 00:11:56.200 A:middle L:90%
kind of a baseline connectivity for passing control traffic around
221
00:11:56.200 --> 00:12:01.399 A:middle L:90%
and keeping the network operating. And in practice,
222
00:12:01.399 --> 00:12:03.440 A:middle L:90%
you need a network that can do both of those
223
00:12:03.440 --> 00:12:05.929 A:middle L:90%
. If you think about DARPA or D O.
224
00:12:05.929 --> 00:12:09.659 A:middle L:90%
D scenario with a bunch of uh a bunch of
225
00:12:09.659 --> 00:12:11.960 A:middle L:90%
, say, soldiers in the field with radios,
226
00:12:11.019 --> 00:12:16.320 A:middle L:90%
well, they want to maintain constant communication for short
227
00:12:16.320 --> 00:12:18.690 A:middle L:90%
traffic as well as potentially stream of video across the
228
00:12:18.690 --> 00:12:20.730 A:middle L:90%
network or something like that. But I think that's
229
00:12:20.730 --> 00:12:26.289 A:middle L:90%
true of almost all of these uh all practical deployments
230
00:12:26.289 --> 00:12:31.320 A:middle L:90%
of ad hoc networks. Um And so so we're
231
00:12:31.320 --> 00:12:33.230 A:middle L:90%
gonna be sharing the same pool of resources, most
232
00:12:33.230 --> 00:12:37.639 A:middle L:90%
likely in order to support both this control traffic and
233
00:12:37.639 --> 00:12:39.470 A:middle L:90%
this high volume traffic. And so as a result
234
00:12:39.470 --> 00:12:41.490 A:middle L:90%
, I think you almost have to consider those two
235
00:12:41.490 --> 00:12:43.799 A:middle L:90%
problems jointly. And so that's what we've tried to
236
00:12:43.799 --> 00:12:50.000 A:middle L:90%
do. So the basic of are the basics of
237
00:12:50.000 --> 00:12:52.580 A:middle L:90%
our approach here, I think is pretty intuitive,
238
00:12:52.590 --> 00:12:56.649 A:middle L:90%
and that is that we're gonna use some minimal amount
239
00:12:56.659 --> 00:13:00.090 A:middle L:90%
of resources in the network in order to keep the
240
00:13:00.090 --> 00:13:03.690 A:middle L:90%
network connected. And then we're gonna reserve other resources
241
00:13:03.690 --> 00:13:07.809 A:middle L:90%
for responding dynamically to traffic demands in the network.
242
00:13:07.850 --> 00:13:11.389 A:middle L:90%
Um And so we've divided this into two stages,
243
00:13:11.389 --> 00:13:16.110 A:middle L:90%
both conceptually as well as in um some of the
244
00:13:16.110 --> 00:13:18.940 A:middle L:90%
numerical results that I'll show you in a few minutes
245
00:13:18.240 --> 00:13:22.700 A:middle L:90%
where stage one is what we call the traffic independent
246
00:13:22.700 --> 00:13:26.470 A:middle L:90%
stage. And in this stage we seek to maximize
247
00:13:26.470 --> 00:13:31.230 A:middle L:90%
network connectivity using some portion of the radio transceivers in
248
00:13:31.230 --> 00:13:33.440 A:middle L:90%
the network. Or in some cases we seek to
249
00:13:33.450 --> 00:13:37.759 A:middle L:90%
uh achieve some particular level of connectivity using the minimum
250
00:13:37.759 --> 00:13:41.480 A:middle L:90%
amount of resources, but in either case the upshot
251
00:13:41.490 --> 00:13:46.980 A:middle L:90%
is that we've got a connected network, um multi
252
00:13:46.980 --> 00:13:50.240 A:middle L:90%
channel, multi transceiver, potentially. Um but that
253
00:13:50.250 --> 00:13:54.450 A:middle L:90%
that has kept some of those resources in reserve in
254
00:13:54.450 --> 00:13:58.769 A:middle L:90%
order to deploy in response to traffic. And so
255
00:13:58.769 --> 00:14:01.850 A:middle L:90%
that's our second stage is a traffic driven channel assignment
256
00:14:01.860 --> 00:14:05.350 A:middle L:90%
, which is, there are some flows that are
257
00:14:05.350 --> 00:14:07.740 A:middle L:90%
imposed, some traffic flows, some some quote large
258
00:14:07.740 --> 00:14:11.850 A:middle L:90%
or significant traffic flows that are imposed on the network
259
00:14:11.860 --> 00:14:16.409 A:middle L:90%
. And we're gonna make some additions to that traffic
260
00:14:16.409 --> 00:14:20.529 A:middle L:90%
independent assignment in order to better support uh, those
261
00:14:20.529 --> 00:14:24.340 A:middle L:90%
flows. And so what I'm going to talk about
262
00:14:24.350 --> 00:14:26.789 A:middle L:90%
first is we've kind of come up with an optimization
263
00:14:26.789 --> 00:14:31.460 A:middle L:90%
model, mixed any er, to stage mixed integer
264
00:14:31.460 --> 00:14:35.379 A:middle L:90%
linear programming model to try to look at the performance
265
00:14:35.379 --> 00:14:39.139 A:middle L:90%
of the strategy in general as compared to a fully
266
00:14:39.139 --> 00:14:45.240 A:middle L:90%
traffic independent or fully traffic driven strategy as well as
267
00:14:45.250 --> 00:14:46.850 A:middle L:90%
how should we strike that balance? How much of
268
00:14:46.850 --> 00:14:50.210 A:middle L:90%
our resources do we need to allocate to keeping the
269
00:14:50.210 --> 00:14:54.059 A:middle L:90%
network connected and running and so on? Um,
270
00:14:54.240 --> 00:14:58.909 A:middle L:90%
Okay. So this is um, I'm not gonna
271
00:14:58.909 --> 00:15:01.950 A:middle L:90%
put optimization problems up today. Maybe I should have
272
00:15:01.950 --> 00:15:03.190 A:middle L:90%
, this is uh, this is maybe the right
273
00:15:03.200 --> 00:15:07.899 A:middle L:90%
crowd for optimization problems and uh, pseudo code algorithms
274
00:15:07.899 --> 00:15:09.460 A:middle L:90%
and so on and so forth. But I'm trying
275
00:15:09.460 --> 00:15:13.950 A:middle L:90%
to keep this at a relatively high level. Um
276
00:15:13.950 --> 00:15:16.120 A:middle L:90%
, and if you're interested in the details, I'll
277
00:15:16.129 --> 00:15:18.149 A:middle L:90%
show some references at the end. I'm happy to
278
00:15:18.149 --> 00:15:20.379 A:middle L:90%
send you papers where we developed these ideas in more
279
00:15:20.500 --> 00:15:24.509 A:middle L:90%
detail. But the general model that we've looked at
280
00:15:24.519 --> 00:15:26.980 A:middle L:90%
is what we think of as a two stage mixed
281
00:15:26.990 --> 00:15:31.419 A:middle L:90%
integer linear program. And I'm not claiming that,
282
00:15:31.429 --> 00:15:33.679 A:middle L:90%
uh, that implementing this, uh, mixed integer
283
00:15:33.679 --> 00:15:37.299 A:middle L:90%
linear programming is the way you would actually go about
284
00:15:37.309 --> 00:15:39.850 A:middle L:90%
carrying out this strategy. That wouldn't be very practical
285
00:15:39.850 --> 00:15:41.389 A:middle L:90%
at all. I'm going to talk about some distributed
286
00:15:41.389 --> 00:15:45.179 A:middle L:90%
algorithms to do these two stages in a few minutes
287
00:15:45.419 --> 00:15:48.279 A:middle L:90%
. But what we're trying to do is assess how
288
00:15:48.279 --> 00:15:50.750 A:middle L:90%
well would a network work if we use the two
289
00:15:50.750 --> 00:15:54.379 A:middle L:90%
stage approach like this? And so two stages stage
290
00:15:54.379 --> 00:15:58.690 A:middle L:90%
one corresponds to to the first stage over here.
291
00:15:58.690 --> 00:16:02.649 A:middle L:90%
In Stage two corresponds to the second stage. So
292
00:16:02.649 --> 00:16:04.909 A:middle L:90%
traffic independent and traffic dependent. And I'm going to
293
00:16:04.909 --> 00:16:08.110 A:middle L:90%
talk a little bit about two versions of the traffic
294
00:16:08.110 --> 00:16:11.610 A:middle L:90%
independent M I L P I'm just kind of flagging
295
00:16:11.610 --> 00:16:15.250 A:middle L:90%
this for your reference because you might see me jump
296
00:16:15.250 --> 00:16:18.320 A:middle L:90%
back and forth a little bit between the two.
297
00:16:18.330 --> 00:16:21.919 A:middle L:90%
Um The main one we're really proposing for use in
298
00:16:21.919 --> 00:16:25.100 A:middle L:90%
real systems is is this bottom one here? What
299
00:16:25.100 --> 00:16:26.970 A:middle L:90%
I'll think of as the resource minimize version where the
300
00:16:26.970 --> 00:16:30.519 A:middle L:90%
goal is to minimize the number of transceivers that you
301
00:16:30.519 --> 00:16:34.789 A:middle L:90%
use uh subject to some interference constraints. We're not
302
00:16:34.789 --> 00:16:38.259 A:middle L:90%
going to allow uh we're not gonna allow many interferes
303
00:16:38.259 --> 00:16:41.320 A:middle L:90%
. In some cases. You have to allow some
304
00:16:41.399 --> 00:16:44.539 A:middle L:90%
and a connectivity constraint. Um And for the results
305
00:16:44.539 --> 00:16:45.000 A:middle L:90%
, I'm gonna show, we look at making the
306
00:16:45.000 --> 00:16:48.879 A:middle L:90%
network one connected, but you could just as easily
307
00:16:48.879 --> 00:16:51.679 A:middle L:90%
decide, oh, I want my baseline network to
308
00:16:51.679 --> 00:16:53.740 A:middle L:90%
always be too connected and I can show you can
309
00:16:53.740 --> 00:16:56.899 A:middle L:90%
show you what difference that will make in a minute
310
00:16:56.340 --> 00:16:59.080 A:middle L:90%
. But I have this other version up at the
311
00:16:59.080 --> 00:17:00.860 A:middle L:90%
top because I sat in a couple of minutes ago
312
00:17:00.940 --> 00:17:03.700 A:middle L:90%
. one of the things we also wanted to see
313
00:17:03.700 --> 00:17:07.319 A:middle L:90%
is, well how much of my resources should I
314
00:17:07.319 --> 00:17:10.410 A:middle L:90%
allocate to the traffic independent part of the network?
315
00:17:10.420 --> 00:17:14.750 A:middle L:90%
Verses? Should I keep in reserve for dynamic allocation
316
00:17:14.750 --> 00:17:15.930 A:middle L:90%
to the network? And so that's the reason for
317
00:17:15.950 --> 00:17:18.809 A:middle L:90%
this top version up here. What I've chosen at
318
00:17:18.809 --> 00:17:22.990 A:middle L:90%
this point to call the alpha balanced version. So
319
00:17:22.990 --> 00:17:26.450 A:middle L:90%
this one has a parameter called alpha and alpha ranges
320
00:17:26.450 --> 00:17:29.240 A:middle L:90%
from 0 to 1. And it's the proportion of
321
00:17:29.250 --> 00:17:33.359 A:middle L:90%
transceivers in the network that are allocated in a traffic
322
00:17:33.369 --> 00:17:37.190 A:middle L:90%
independent fashion. So if alpha is equal to zero
323
00:17:37.200 --> 00:17:41.559 A:middle L:90%
, then you save all your transceivers for dynamic allocation
324
00:17:41.569 --> 00:17:44.009 A:middle L:90%
. And if alpha is equal to one, uh
325
00:17:44.019 --> 00:17:45.829 A:middle L:90%
then you save none of them, You use them
326
00:17:45.829 --> 00:17:48.869 A:middle L:90%
all in the traffic independent phase and there's nothing left
327
00:17:48.869 --> 00:17:51.089 A:middle L:90%
when you get to stage two. Um And so
328
00:17:51.089 --> 00:17:52.829 A:middle L:90%
then what we do in stage two is we solve
329
00:17:52.839 --> 00:17:57.400 A:middle L:90%
a flow routing problem, kind of? Almost the
330
00:17:57.410 --> 00:18:03.170 A:middle L:90%
standard flow routing problem. Uh Given the allocation that
331
00:18:03.170 --> 00:18:06.569 A:middle L:90%
was done in stage one is fixed, but you
332
00:18:06.569 --> 00:18:10.150 A:middle L:90%
can make additional channel assignments in stage two, in
333
00:18:10.150 --> 00:18:12.180 A:middle L:90%
order to best support the set of flows. That's
334
00:18:12.190 --> 00:18:15.109 A:middle L:90%
that's their that's given to you. And so this
335
00:18:15.119 --> 00:18:18.720 A:middle L:90%
is to try to max so for the imposed flow
336
00:18:18.720 --> 00:18:21.569 A:middle L:90%
rates and for the results, I'm gonna show today
337
00:18:21.579 --> 00:18:22.849 A:middle L:90%
what we do is we take the network and we
338
00:18:22.859 --> 00:18:26.829 A:middle L:90%
impose a particular number of flows and we say,
339
00:18:26.829 --> 00:18:27.779 A:middle L:90%
well, all these flows have to be maintained at
340
00:18:27.779 --> 00:18:30.150 A:middle L:90%
the same rate. And what's the maximum I can
341
00:18:30.150 --> 00:18:33.470 A:middle L:90%
turn up that rate and still have the network.
342
00:18:33.480 --> 00:18:36.049 A:middle L:90%
Be able to support those flows if I assign some
343
00:18:36.049 --> 00:18:40.180 A:middle L:90%
additional channels to help me do this. Um Okay
344
00:18:40.190 --> 00:18:44.279 A:middle L:90%
, okay. Um so this is just a quick
345
00:18:44.279 --> 00:18:45.849 A:middle L:90%
example to give you a brief idea of what we're
346
00:18:45.849 --> 00:18:48.829 A:middle L:90%
talking about here. So over on the left side
347
00:18:48.829 --> 00:18:52.380 A:middle L:90%
is something that you might see out of, wow
348
00:18:52.380 --> 00:18:53.660 A:middle L:90%
, this looks different on the screen, but um
349
00:18:53.670 --> 00:18:56.819 A:middle L:90%
but something you might see as the result of a
350
00:18:56.829 --> 00:19:03.240 A:middle L:90%
conventional traffic independent channel assignment algorithm that takes all the
351
00:19:03.240 --> 00:19:06.910 A:middle L:90%
resources in the network and tries to allocate them in
352
00:19:06.910 --> 00:19:10.599 A:middle L:90%
a traffic independent manner. Um Typically we'll talk about
353
00:19:10.599 --> 00:19:11.359 A:middle L:90%
in a minute, but these are either trying to
354
00:19:11.359 --> 00:19:17.339 A:middle L:90%
maximize the connectivity or they're trying to minimize the interference
355
00:19:17.349 --> 00:19:21.299 A:middle L:90%
, um but they're gonna allocate every single transceiver in
356
00:19:21.299 --> 00:19:23.690 A:middle L:90%
the network to some channel uh and and try to
357
00:19:23.690 --> 00:19:29.559 A:middle L:90%
achieve their goals that way. And um so one
358
00:19:29.559 --> 00:19:30.380 A:middle L:90%
of the things you see on the left side here
359
00:19:30.380 --> 00:19:33.349 A:middle L:90%
is this does, tends to in some cases lead
360
00:19:33.349 --> 00:19:37.230 A:middle L:90%
to so colors here indicate different channels for different links
361
00:19:37.250 --> 00:19:41.500 A:middle L:90%
, um and this tends to lead to what are
362
00:19:41.500 --> 00:19:45.759 A:middle L:90%
called clicks or fully connected sub graphs on particular channels
363
00:19:45.769 --> 00:19:49.319 A:middle L:90%
because that tends to minimize interference because our concept of
364
00:19:49.319 --> 00:19:52.650 A:middle L:90%
interference here is a node that can that you might
365
00:19:52.650 --> 00:19:55.980 A:middle L:90%
have to time share with, that might interfere with
366
00:19:55.980 --> 00:19:57.809 A:middle L:90%
you on a particular channel, but that you can't
367
00:19:57.809 --> 00:20:03.349 A:middle L:90%
directly communicate. Um and so what you see here
368
00:20:03.349 --> 00:20:07.299 A:middle L:90%
is you see a very densely connected network, um
369
00:20:07.599 --> 00:20:11.490 A:middle L:90%
but with all the resources allocated on the right,
370
00:20:11.500 --> 00:20:15.150 A:middle L:90%
you have a solution from what I called on this
371
00:20:15.150 --> 00:20:18.500 A:middle L:90%
page. This resource minimized version of Stage one,
372
00:20:18.509 --> 00:20:22.210 A:middle L:90%
where it says I want to achieve a connected network
373
00:20:22.220 --> 00:20:25.130 A:middle L:90%
, but I want to do so using the fewest
374
00:20:25.130 --> 00:20:29.410 A:middle L:90%
possible number of transceivers. And so what you see
375
00:20:29.410 --> 00:20:33.490 A:middle L:90%
there is you get a few clicks or near clicks
376
00:20:33.490 --> 00:20:37.410 A:middle L:90%
at least on a particular channel and then some some
377
00:20:37.410 --> 00:20:38.829 A:middle L:90%
links between them. So this is if you've worked
378
00:20:38.829 --> 00:20:41.039 A:middle L:90%
in ad hoc networking, you know that a lot
379
00:20:41.039 --> 00:20:45.130 A:middle L:90%
of the algorithms, there are clustered algorithms and this
380
00:20:45.140 --> 00:20:48.180 A:middle L:90%
kind of gives you good justification for why that might
381
00:20:48.190 --> 00:20:52.349 A:middle L:90%
be because this performs pretty well. We've got these
382
00:20:52.359 --> 00:20:56.500 A:middle L:90%
clusters on the same channel and then we have what
383
00:20:56.500 --> 00:20:59.180 A:middle L:90%
you can think of as cluster heads that handle these
384
00:20:59.240 --> 00:21:04.009 A:middle L:90%
cross cluster communications. And so then what we get
385
00:21:04.019 --> 00:21:07.200 A:middle L:90%
if we run it through this two stage, um
386
00:21:07.210 --> 00:21:11.380 A:middle L:90%
, M I L p upon top we have the
387
00:21:11.380 --> 00:21:14.430 A:middle L:90%
results when alpha is equal to one. So that's
388
00:21:14.430 --> 00:21:17.009 A:middle L:90%
the case where all the resources are assigned in the
389
00:21:17.009 --> 00:21:19.720 A:middle L:90%
traffic independent manner. And so our stage one does
390
00:21:19.730 --> 00:21:22.819 A:middle L:90%
all of the channel assignment. Well, I should
391
00:21:22.819 --> 00:21:25.710 A:middle L:90%
tell you a little bit about these figures. The
392
00:21:25.710 --> 00:21:30.740 A:middle L:90%
solid lines and these figures are traffic independent assignments of
393
00:21:30.740 --> 00:21:33.809 A:middle L:90%
channels. And then the dotted lines are those that
394
00:21:33.809 --> 00:21:37.500 A:middle L:90%
are assigned in stage two in the traffic dependent uh
395
00:21:37.509 --> 00:21:40.609 A:middle L:90%
phase. And so the top the top one is
396
00:21:40.619 --> 00:21:44.210 A:middle L:90%
all traffic independent assignment. So it's all solid links
397
00:21:44.329 --> 00:21:47.210 A:middle L:90%
and the bottom one is all traffic dependent, so
398
00:21:47.210 --> 00:21:48.230 A:middle L:90%
it's all dotted links. And then the one in
399
00:21:48.230 --> 00:21:52.670 A:middle L:90%
the middle is our proposal where we've got a traffic
400
00:21:52.670 --> 00:21:56.579 A:middle L:90%
independent allocation, but then we make some traffic dependent
401
00:21:56.589 --> 00:21:59.130 A:middle L:90%
adjustments to it. Um One other thing I guess
402
00:21:59.130 --> 00:22:03.890 A:middle L:90%
to say about these figures is the darker circles or
403
00:22:03.890 --> 00:22:07.500 A:middle L:90%
triangles. I guess in the bottom two are the
404
00:22:07.500 --> 00:22:10.579 A:middle L:90%
sources and destinations of the flows. And it's pretty
405
00:22:10.579 --> 00:22:12.289 A:middle L:90%
hard to see up here, but the color inside
406
00:22:12.289 --> 00:22:15.220 A:middle L:90%
the circle tells you which flow, that's the source
407
00:22:15.220 --> 00:22:18.660 A:middle L:90%
or destination for and it's not really connected to the
408
00:22:18.660 --> 00:22:22.400 A:middle L:90%
colours for the channel assignment. Okay, so what
409
00:22:22.400 --> 00:22:25.900 A:middle L:90%
happens here? Um This is 20 nodes? Um
410
00:22:26.750 --> 00:22:27.640 A:middle L:90%
Part of my notes are covered up here, but
411
00:22:27.650 --> 00:22:30.299 A:middle L:90%
I want to say 20 nodes, I want to
412
00:22:30.299 --> 00:22:34.700 A:middle L:90%
say four transceivers on each node and about 10 available
413
00:22:34.700 --> 00:22:41.759 A:middle L:90%
channels. Um and so what happens here is alpha
414
00:22:41.759 --> 00:22:44.519 A:middle L:90%
equal to one up here, which is where we've
415
00:22:44.519 --> 00:22:48.519 A:middle L:90%
done a completely traffic independent assignment of channels. The
416
00:22:48.529 --> 00:22:52.259 A:middle L:90%
fact that we can't adapt to the flows greatly limits
417
00:22:52.259 --> 00:22:56.950 A:middle L:90%
the maximum flow rate of those flows through the network
418
00:22:56.950 --> 00:23:00.289 A:middle L:90%
. And so what's achieved here is indicated there is
419
00:23:00.289 --> 00:23:03.150 A:middle L:90%
a flow rate of 0.67 I should say the flow
420
00:23:03.150 --> 00:23:06.150 A:middle L:90%
rates here are normalized. We assume that all of
421
00:23:06.150 --> 00:23:08.940 A:middle L:90%
the wireless links have the same rate capacity. And
422
00:23:08.940 --> 00:23:11.890 A:middle L:90%
so the flow link are, sorry, the flow
423
00:23:11.900 --> 00:23:14.880 A:middle L:90%
rate is normalized to the rate of a single link
424
00:23:14.890 --> 00:23:17.400 A:middle L:90%
. So it's how much flow can you push through
425
00:23:17.400 --> 00:23:22.450 A:middle L:90%
all of these assigned uh Source destination pairs? Uh
426
00:23:22.460 --> 00:23:25.500 A:middle L:90%
with respect to how much goes on a single on
427
00:23:25.500 --> 00:23:27.440 A:middle L:90%
a single link. And so if you assign all
428
00:23:27.440 --> 00:23:30.190 A:middle L:90%
the channels in advance, you get this flow rate
429
00:23:30.200 --> 00:23:34.049 A:middle L:90%
of.67 at the other extreme, what we know
430
00:23:34.049 --> 00:23:37.359 A:middle L:90%
to be optimal in terms of flow rate is if
431
00:23:37.359 --> 00:23:41.460 A:middle L:90%
you if you saw for all I care about is
432
00:23:41.460 --> 00:23:44.809 A:middle L:90%
running these flows through the network, then you find
433
00:23:44.809 --> 00:23:48.309 A:middle L:90%
that you can support more than uh more than twice
434
00:23:48.309 --> 00:23:52.410 A:middle L:90%
that with a flow rate of 1.6. Because what
435
00:23:52.410 --> 00:23:56.069 A:middle L:90%
you wind up with this multiple paths um for each
436
00:23:56.069 --> 00:23:59.849 A:middle L:90%
source destination pair, remember that each note has multiple
437
00:23:59.849 --> 00:24:03.190 A:middle L:90%
transceivers. And so it's potentially uh putting out that
438
00:24:03.200 --> 00:24:07.869 A:middle L:90%
flow on multiple transceivers at the same time. So
439
00:24:07.960 --> 00:24:10.660 A:middle L:90%
, so what you also see though in this completely
440
00:24:10.660 --> 00:24:12.609 A:middle L:90%
traffic driven assignment at the bottom is some nodes are
441
00:24:12.609 --> 00:24:15.829 A:middle L:90%
not getting channel assignments at all because it's not optimal
442
00:24:15.829 --> 00:24:21.539 A:middle L:90%
to make use of them in forwarding this particular traffic
443
00:24:21.589 --> 00:24:23.710 A:middle L:90%
. Um And then you see our proposal in the
444
00:24:23.710 --> 00:24:27.440 A:middle L:90%
middle where you have a traffic independent assignment which just
445
00:24:27.440 --> 00:24:30.630 A:middle L:90%
strives to connect the network and then on top of
446
00:24:30.630 --> 00:24:36.529 A:middle L:90%
that you impose some additional links in response to traffic
447
00:24:36.529 --> 00:24:40.920 A:middle L:90%
demands. And what happened in this particular cases were
448
00:24:40.920 --> 00:24:44.549 A:middle L:90%
able to achieve uh the same flow rate as in
449
00:24:44.549 --> 00:24:47.910 A:middle L:90%
the optimal case, but we have this background,
450
00:24:47.920 --> 00:24:51.019 A:middle L:90%
if you will, or baseline fully connected network to
451
00:24:51.019 --> 00:24:55.619 A:middle L:90%
support control traffic or short message traffic, uh things
452
00:24:55.619 --> 00:24:57.829 A:middle L:90%
like that. Um And so even though we have
453
00:24:57.829 --> 00:25:02.950 A:middle L:90%
assigned more than half 37 out of 60 radio,
454
00:25:02.950 --> 00:25:03.670 A:middle L:90%
so I guess it must have been three transceivers per
455
00:25:03.670 --> 00:25:07.329 A:middle L:90%
note. Um uh even though we've assigned more than
456
00:25:07.329 --> 00:25:11.769 A:middle L:90%
half of the transceivers upfront for this traffic independent purposes
457
00:25:11.859 --> 00:25:17.670 A:middle L:90%
were still able to achieve the same flow rate as
458
00:25:17.680 --> 00:25:19.230 A:middle L:90%
in the optimal case. And this is a little
459
00:25:19.230 --> 00:25:22.680 A:middle L:90%
bit surprising to us. We expected there would be
460
00:25:22.680 --> 00:25:26.289 A:middle L:90%
some price to pay for holding back some of those
461
00:25:26.289 --> 00:25:30.099 A:middle L:90%
transceivers to use in a traffic independent uh fashion,
462
00:25:30.160 --> 00:25:33.210 A:middle L:90%
but as we'll see on some results in a minute
463
00:25:33.559 --> 00:25:36.730 A:middle L:90%
, in many cases there's there's very little or no
464
00:25:36.730 --> 00:25:41.029 A:middle L:90%
price to pay for it. Um this kind of
465
00:25:41.029 --> 00:25:41.650 A:middle L:90%
shows the same thing, but whereas this is a
466
00:25:41.650 --> 00:25:47.190 A:middle L:90%
particular scenario, this is averaged over thousands of realizations
467
00:25:47.190 --> 00:25:49.589 A:middle L:90%
of the network. Um so thousands of times we've
468
00:25:49.599 --> 00:25:52.779 A:middle L:90%
we've thrown nodes down in our simulation area and figured
469
00:25:52.779 --> 00:25:56.039 A:middle L:90%
out what the potential links are and solve the traffic
470
00:25:56.039 --> 00:25:57.900 A:middle L:90%
independent problem, uh and then and then solve the
471
00:25:57.900 --> 00:26:02.559 A:middle L:90%
stage to traffic driven problem. And what's shown here
472
00:26:02.559 --> 00:26:06.500 A:middle L:90%
is uh averaged over all those runs the maximum flow
473
00:26:06.500 --> 00:26:11.559 A:middle L:90%
rate um for the traffic driven and traffic independent schemes
474
00:26:11.559 --> 00:26:15.019 A:middle L:90%
at the extremes and the traffic aware in the middle
475
00:26:15.230 --> 00:26:18.269 A:middle L:90%
. And you can see the three sets along the
476
00:26:18.269 --> 00:26:21.799 A:middle L:90%
X axis here are the number of transceivers that each
477
00:26:21.799 --> 00:26:23.170 A:middle L:90%
node has, and you can see that when each
478
00:26:23.170 --> 00:26:26.049 A:middle L:90%
note only has two transceivers, there's a price to
479
00:26:26.049 --> 00:26:30.829 A:middle L:90%
be paid in terms of network capacity for for doing
480
00:26:30.829 --> 00:26:33.980 A:middle L:90%
this traffic independent assignment up front. But once we
481
00:26:33.980 --> 00:26:37.950 A:middle L:90%
get to three or four transceivers, it's possible to
482
00:26:37.960 --> 00:26:41.809 A:middle L:90%
connect the network in an interference free way and still
483
00:26:41.809 --> 00:26:45.910 A:middle L:90%
have enough transceivers left over to achieve to achieve the
484
00:26:45.910 --> 00:26:51.019 A:middle L:90%
same maximum flow rate as you can if you try
485
00:26:51.019 --> 00:26:55.410 A:middle L:90%
to use all of your transceivers dynamically. And so
486
00:26:55.410 --> 00:26:56.279 A:middle L:90%
that was a little surprising to us and we are
487
00:26:56.279 --> 00:27:00.579 A:middle L:90%
pleased by it because we think it invalidates um it
488
00:27:00.579 --> 00:27:03.220 A:middle L:90%
validates are thinking about how we might want to go
489
00:27:03.220 --> 00:27:10.509 A:middle L:90%
about solving this resource allocation problem. So this is
490
00:27:10.509 --> 00:27:12.289 A:middle L:90%
the one slide I was referring to with that alpha
491
00:27:12.289 --> 00:27:18.640 A:middle L:90%
controlled uh allocation where the proportion of transceivers that we
492
00:27:18.640 --> 00:27:22.599 A:middle L:90%
use for the traffic independent stages alpha. And we
493
00:27:22.599 --> 00:27:25.779 A:middle L:90%
try to get the maximum capacity that we can with
494
00:27:25.789 --> 00:27:29.789 A:middle L:90%
that many transceivers. And so the top graph shows
495
00:27:29.799 --> 00:27:33.450 A:middle L:90%
a metric that we call K prime connectivity. If
496
00:27:33.450 --> 00:27:37.190 A:middle L:90%
you're familiar with the graph theory, you you've heard
497
00:27:37.190 --> 00:27:40.809 A:middle L:90%
of cake, a cake connected network and a network
498
00:27:40.809 --> 00:27:44.559 A:middle L:90%
is K connected if there are K link independent paths
499
00:27:44.799 --> 00:27:48.650 A:middle L:90%
between every pair of nodes. And so we are
500
00:27:48.660 --> 00:27:52.589 A:middle L:90%
we've modified that metric a little bit to give us
501
00:27:52.589 --> 00:27:56.759 A:middle L:90%
some more granularity here where we've said, okay,
502
00:27:56.049 --> 00:28:00.549 A:middle L:90%
I've got that K connected network but then I'm also
503
00:28:00.549 --> 00:28:03.000 A:middle L:90%
going to look at what's the proportion of those source
504
00:28:03.000 --> 00:28:07.009 A:middle L:90%
destination pairs that have more than K independent paths between
505
00:28:07.009 --> 00:28:10.849 A:middle L:90%
them. And so like a K prime here of
506
00:28:10.849 --> 00:28:14.549 A:middle L:90%
2.5 would mean, well every source destination pair has
507
00:28:14.549 --> 00:28:17.009 A:middle L:90%
at least two independent paths, but half of the
508
00:28:17.009 --> 00:28:19.559 A:middle L:90%
source destination pairs have at least three. So that's
509
00:28:19.559 --> 00:28:22.329 A:middle L:90%
our that's our metric of connectivity because we wanted something
510
00:28:22.329 --> 00:28:26.789 A:middle L:90%
a little more fine grained here and you can see
511
00:28:26.789 --> 00:28:29.859 A:middle L:90%
what happens as you increase exactly as you would expect
512
00:28:29.859 --> 00:28:33.140 A:middle L:90%
as you increase the proportion of radios that are devoted
513
00:28:33.140 --> 00:28:37.930 A:middle L:90%
to this traffic independent allocation, the connectivity goes up
514
00:28:37.990 --> 00:28:42.240 A:middle L:90%
. Um And so but but what may be most
515
00:28:42.240 --> 00:28:47.829 A:middle L:90%
important here is if you look at that horizontal line
516
00:28:47.829 --> 00:28:51.680 A:middle L:90%
there that's drawn at one is once you especially for
517
00:28:51.680 --> 00:28:55.630 A:middle L:90%
three and four radios per node. Uh It's it's
518
00:28:55.630 --> 00:29:00.180 A:middle L:90%
a it's a relatively small proportion even even at two
519
00:29:00.180 --> 00:29:02.710 A:middle L:90%
radios promote, it's only about half of the radios
520
00:29:02.710 --> 00:29:07.880 A:middle L:90%
that you need to achieve this interference free um connected
521
00:29:07.890 --> 00:29:11.180 A:middle L:90%
allocation. So if you are interested in saying making
522
00:29:11.180 --> 00:29:14.039 A:middle L:90%
that this is the graph to look at, if
523
00:29:14.039 --> 00:29:17.029 A:middle L:90%
you say, well, I think 11 connected baseline
524
00:29:17.029 --> 00:29:18.730 A:middle L:90%
network is not good enough because these nodes are moving
525
00:29:18.799 --> 00:29:22.319 A:middle L:90%
and so links are going to fail and our channels
526
00:29:22.319 --> 00:29:25.059 A:middle L:90%
are not very reliable and so I want to build
527
00:29:25.059 --> 00:29:26.980 A:middle L:90%
the baseline topology that's too connected. Well, what
528
00:29:26.980 --> 00:29:30.359 A:middle L:90%
the top graph here tells you is even if you
529
00:29:30.359 --> 00:29:32.839 A:middle L:90%
want to go up to a two connected network,
530
00:29:32.930 --> 00:29:37.019 A:middle L:90%
especially for three and four transceivers, you could still
531
00:29:37.019 --> 00:29:40.730 A:middle L:90%
have a lot of your transceivers in reserve for traffic
532
00:29:40.730 --> 00:29:44.880 A:middle L:90%
driven approach. So the bottom graph here then looks
533
00:29:44.890 --> 00:29:48.349 A:middle L:90%
again at at the at the maximum flow rate that
534
00:29:48.349 --> 00:29:52.640 A:middle L:90%
you can push through the network again for two radios
535
00:29:52.640 --> 00:29:56.160 A:middle L:90%
per node. Three radios promote and four radios per
536
00:29:56.160 --> 00:30:00.059 A:middle L:90%
node. And when you're way over here at the
537
00:30:00.140 --> 00:30:03.099 A:middle L:90%
left side, you're talking about a fully uh fully
538
00:30:03.099 --> 00:30:07.190 A:middle L:90%
traffic um driven approach to channel assignment. And you
539
00:30:07.190 --> 00:30:11.430 A:middle L:90%
see that um adding additional radios per node helps you
540
00:30:11.430 --> 00:30:14.200 A:middle L:90%
a little bit, but not a great deal.
541
00:30:14.210 --> 00:30:15.359 A:middle L:90%
Uh And then as you move to the right,
542
00:30:15.539 --> 00:30:18.809 A:middle L:90%
um as you move to the right, you're using
543
00:30:18.809 --> 00:30:22.000 A:middle L:90%
more and more of those nodes traffic independently. And
544
00:30:22.000 --> 00:30:25.529 A:middle L:90%
of course your flow rate is going down, but
545
00:30:25.529 --> 00:30:27.029 A:middle L:90%
especially for the two and three radio note cases,
546
00:30:27.140 --> 00:30:32.660 A:middle L:90%
it's not going down very quickly. So. All
547
00:30:32.660 --> 00:30:33.970 A:middle L:90%
right. So, I mean, so what we've
548
00:30:33.980 --> 00:30:38.480 A:middle L:90%
really tried to establish here is using this to stage
549
00:30:38.490 --> 00:30:41.170 A:middle L:90%
M I L. P. Is that this traffic
550
00:30:41.170 --> 00:30:45.380 A:middle L:90%
aware approach is viable. It's a promising way to
551
00:30:45.380 --> 00:30:52.710 A:middle L:90%
obtain high network capacity while maintaining connectivity. So most
552
00:30:52.710 --> 00:30:56.369 A:middle L:90%
of those network capacity gains come from allocating a relatively
553
00:30:56.369 --> 00:31:02.329 A:middle L:90%
small proportion of the resources in response to dynamic traffic
554
00:31:02.410 --> 00:31:04.500 A:middle L:90%
. Um And so what we've been doing since we
555
00:31:04.500 --> 00:31:07.440 A:middle L:90%
did this work is trying to come up with practical
556
00:31:07.440 --> 00:31:11.500 A:middle L:90%
way is to implement these two phases. Um And
557
00:31:11.500 --> 00:31:14.579 A:middle L:90%
so I'm going to talk about those now. And
558
00:31:14.579 --> 00:31:17.339 A:middle L:90%
so the first one of those is associated with stage
559
00:31:17.339 --> 00:31:19.250 A:middle L:90%
one here. How should we do the traffic independent
560
00:31:19.250 --> 00:31:22.660 A:middle L:90%
assignment? So as I mentioned a little bit earlier
561
00:31:22.799 --> 00:31:26.250 A:middle L:90%
in the literature, the common approaches to this traffic
562
00:31:26.259 --> 00:31:32.119 A:middle L:90%
independent resource assignment or channel assignment in a network um
563
00:31:32.130 --> 00:31:36.440 A:middle L:90%
are are do not attempt to conserve resources. They
564
00:31:36.450 --> 00:31:40.019 A:middle L:90%
either try to maximize connectivity for some measure of connectivity
565
00:31:40.029 --> 00:31:42.049 A:middle L:90%
or they try to minimize interference in some way by
566
00:31:42.049 --> 00:31:45.740 A:middle L:90%
the way they assigned channels. But the goal is
567
00:31:45.750 --> 00:31:48.000 A:middle L:90%
you give me four transceivers and 10 channels. I'm
568
00:31:48.000 --> 00:31:52.200 A:middle L:90%
going to use every transceiver on every node assigned to
569
00:31:52.200 --> 00:31:55.380 A:middle L:90%
some channel. So our approach tries to do something
570
00:31:55.380 --> 00:31:57.630 A:middle L:90%
different. Um resource, minimize channel assignment is what
571
00:31:57.630 --> 00:32:00.869 A:middle L:90%
we call it. And the goal is to minimize
572
00:32:00.869 --> 00:32:07.410 A:middle L:90%
resource usage, subject to constraints on how much connectivity
573
00:32:07.410 --> 00:32:10.690 A:middle L:90%
we're requiring ourselves to achieving the network and how much
574
00:32:10.690 --> 00:32:14.400 A:middle L:90%
interference we're willing to allow, how many interfere,
575
00:32:14.410 --> 00:32:16.430 A:middle L:90%
how many interfering channel assignments we allow to be made
576
00:32:16.740 --> 00:32:20.640 A:middle L:90%
in the network. So this is the slide where
577
00:32:20.640 --> 00:32:22.500 A:middle L:90%
I guess I could have put up some pseudo code
578
00:32:22.500 --> 00:32:24.950 A:middle L:90%
, especially for this audience, but I decided not
579
00:32:24.950 --> 00:32:28.500 A:middle L:90%
to do that. But the algorithm is actually very
580
00:32:28.500 --> 00:32:32.589 A:middle L:90%
simple. The nodes take turns selecting channels. And
581
00:32:32.589 --> 00:32:36.670 A:middle L:90%
when a node select the channel it tries it takes
582
00:32:36.680 --> 00:32:38.730 A:middle L:90%
one of its transceivers that's not already assigned and it
583
00:32:38.730 --> 00:32:42.849 A:middle L:90%
tries to assign it to a channel that yields the
584
00:32:42.849 --> 00:32:45.910 A:middle L:90%
greatest number of new neighbors. So the greatest number
585
00:32:45.910 --> 00:32:49.539 A:middle L:90%
of nodes that I'm within communication range of, but
586
00:32:49.539 --> 00:32:52.000 A:middle L:90%
I didn't but I wasn't connected to before because we
587
00:32:52.000 --> 00:32:54.000 A:middle L:90%
didn't share a common channel, so tries to maximize
588
00:32:54.000 --> 00:32:57.289 A:middle L:90%
the number of new neighbors, but with sort of
589
00:32:57.299 --> 00:33:00.519 A:middle L:90%
two caveats, the first one being, I'm never
590
00:33:00.519 --> 00:33:02.690 A:middle L:90%
going to make a channel assignment that that I know
591
00:33:02.690 --> 00:33:06.529 A:middle L:90%
to be interfering uh with some other node in the
592
00:33:06.529 --> 00:33:07.240 A:middle L:90%
network. So that that is I'm never going to
593
00:33:07.240 --> 00:33:10.509 A:middle L:90%
choose a channel where there's gonna be someone out there
594
00:33:10.509 --> 00:33:14.130 A:middle L:90%
in my interference range on the same channel, but
595
00:33:14.130 --> 00:33:16.369 A:middle L:90%
that I'm not in communication range of And the second
596
00:33:16.369 --> 00:33:20.630 A:middle L:90%
thing is nodes stop doing this, they stop even
597
00:33:20.630 --> 00:33:24.589 A:middle L:90%
assigning new channels. Um once they are, once
598
00:33:24.589 --> 00:33:28.650 A:middle L:90%
they know that every note that they're in communication range
599
00:33:28.650 --> 00:33:31.200 A:middle L:90%
of is within either one or two hops in the
600
00:33:31.200 --> 00:33:35.440 A:middle L:90%
network as it's constructed. So it's a very simple
601
00:33:35.440 --> 00:33:38.380 A:middle L:90%
concept here. Many of the other traffic independent assignment
602
00:33:38.380 --> 00:33:42.009 A:middle L:90%
schemes are as well. Um but it's kind of
603
00:33:42.009 --> 00:33:44.650 A:middle L:90%
based on local information. If you send out some
604
00:33:44.650 --> 00:33:46.349 A:middle L:90%
neighbor discovery packets, you can find out most of
605
00:33:46.349 --> 00:33:49.579 A:middle L:90%
what you need to know in order to get,
606
00:33:49.579 --> 00:33:50.779 A:middle L:90%
you can find out all of what you need to
607
00:33:50.779 --> 00:33:53.460 A:middle L:90%
know in order to implement this. Um So what
608
00:33:53.460 --> 00:33:58.880 A:middle L:90%
happens if we compare this to approaches in the literature
609
00:33:58.980 --> 00:34:00.759 A:middle L:90%
? Um the graph on the left side here is
610
00:34:00.759 --> 00:34:04.329 A:middle L:90%
the number of transceivers used. It shouldn't be a
611
00:34:04.329 --> 00:34:07.549 A:middle L:90%
great surprise that all of these other techniques are not
612
00:34:07.549 --> 00:34:12.280 A:middle L:90%
even trying to um to conserve transceiver usage, which
613
00:34:12.280 --> 00:34:14.659 A:middle L:90%
I mentioned at the beginning is important. Even if
614
00:34:14.659 --> 00:34:16.400 A:middle L:90%
you're not going to use them dynamically, these transceivers
615
00:34:16.400 --> 00:34:20.079 A:middle L:90%
are expensive to operate, the more you turn on
616
00:34:20.079 --> 00:34:22.179 A:middle L:90%
, the faster you drain your battery and things like
617
00:34:22.179 --> 00:34:23.050 A:middle L:90%
that. But that hasn't been a goal in the
618
00:34:23.050 --> 00:34:27.639 A:middle L:90%
past. And so we're able to use um in
619
00:34:27.639 --> 00:34:31.809 A:middle L:90%
some cases many fewer transceivers than the other multi transceiver
620
00:34:31.809 --> 00:34:35.349 A:middle L:90%
schemes that are out there, you can see that
621
00:34:35.360 --> 00:34:37.050 A:middle L:90%
if you only have two transceivers per node, we
622
00:34:37.050 --> 00:34:39.630 A:middle L:90%
only do a little bit better than those other schemes
623
00:34:39.659 --> 00:34:42.840 A:middle L:90%
, but if you have three or four transceivers per
624
00:34:42.840 --> 00:34:46.349 A:middle L:90%
node, then we're still using about on average 1.5
625
00:34:46.349 --> 00:34:50.289 A:middle L:90%
transceivers per node. Whereas the other schemes for the
626
00:34:50.289 --> 00:34:52.360 A:middle L:90%
most part are just taking all those transceivers and using
627
00:34:52.360 --> 00:34:57.119 A:middle L:90%
them. The exception to that being the click based
628
00:34:57.130 --> 00:35:00.199 A:middle L:90%
um scheme here, which often runs into scenarios where
629
00:35:00.199 --> 00:35:01.889 A:middle L:90%
there's just no additional clicks that can be formed and
630
00:35:01.889 --> 00:35:06.309 A:middle L:90%
so it leaves some of the transceivers off and on
631
00:35:06.309 --> 00:35:09.469 A:middle L:90%
the right side here shows the connectivity and what you'll
632
00:35:09.469 --> 00:35:14.280 A:middle L:90%
see here is that our our scheme and this is
633
00:35:14.289 --> 00:35:16.469 A:middle L:90%
this is basic cake connectivity, it's not the k
634
00:35:16.469 --> 00:35:20.030 A:middle L:90%
prime connectivity that I was talking about before, but
635
00:35:20.030 --> 00:35:22.610 A:middle L:90%
it's averaged over many runs. So you don't necessarily
636
00:35:22.610 --> 00:35:24.530 A:middle L:90%
get integer values here, but you'll see that we
637
00:35:24.530 --> 00:35:28.679 A:middle L:90%
are much less connected than many of these other schemes
638
00:35:28.710 --> 00:35:30.650 A:middle L:90%
, which is not a surprise since a lot of
639
00:35:30.650 --> 00:35:34.469 A:middle L:90%
the other schemes are striving to maximize connectivity. But
640
00:35:34.469 --> 00:35:37.030 A:middle L:90%
what I want to point out here is um and
641
00:35:37.030 --> 00:35:37.840 A:middle L:90%
you can't see it on the graph, but we're
642
00:35:37.849 --> 00:35:44.159 A:middle L:90%
keeping the network one or two connected 1998% of these
643
00:35:44.159 --> 00:35:45.989 A:middle L:90%
runs. Um whereas some of these other schemes,
644
00:35:45.989 --> 00:35:50.360 A:middle L:90%
especially for three and four transceivers, um I guess
645
00:35:50.360 --> 00:35:52.659 A:middle L:90%
I should say this graph is two transceivers and this
646
00:35:52.659 --> 00:35:54.329 A:middle L:90%
graph is four transceivers are. Well, I guess
647
00:35:54.329 --> 00:35:58.539 A:middle L:90%
even the true transceiver case are especially in this high
648
00:35:58.539 --> 00:36:00.070 A:middle L:90%
dense that we have, we have three different deployment
649
00:36:00.079 --> 00:36:04.139 A:middle L:90%
densities of nodes here, especially in the high density
650
00:36:04.139 --> 00:36:06.869 A:middle L:90%
case are doing what I would call over connecting the
651
00:36:06.869 --> 00:36:09.300 A:middle L:90%
network. We're getting networks that are 10 and 12
652
00:36:09.300 --> 00:36:12.670 A:middle L:90%
connected. Now you can make a case to me
653
00:36:12.699 --> 00:36:14.840 A:middle L:90%
that you want your network to be two or three
654
00:36:14.840 --> 00:36:17.289 A:middle L:90%
connected to provide some robustness but I'm not sure you
655
00:36:17.289 --> 00:36:20.940 A:middle L:90%
ever really want to network to be 10 or 12
656
00:36:21.469 --> 00:36:23.889 A:middle L:90%
connected. Um at least not for the applications that
657
00:36:23.900 --> 00:36:30.030 A:middle L:90%
I'm most interested in and here's some more results from
658
00:36:30.030 --> 00:36:32.210 A:middle L:90%
this in terms of conflict and interference. Um I
659
00:36:32.219 --> 00:36:36.210 A:middle L:90%
mean two different things by conflict and interference here by
660
00:36:36.210 --> 00:36:38.650 A:middle L:90%
conflict. I mean essentially how many nodes are you
661
00:36:38.650 --> 00:36:42.829 A:middle L:90%
sharing the channel with? So even if I have
662
00:36:42.840 --> 00:36:44.639 A:middle L:90%
if I got a click and it's got a bunch
663
00:36:44.639 --> 00:36:45.590 A:middle L:90%
of nodes in it. Well, all those notes
664
00:36:45.590 --> 00:36:47.260 A:middle L:90%
can communicate with each other, but they have to
665
00:36:47.260 --> 00:36:51.460 A:middle L:90%
time share the channel somehow. Often through a carrier
666
00:36:51.460 --> 00:36:55.480 A:middle L:90%
sense multiple access kind of mechanism. And so this
667
00:36:55.480 --> 00:36:59.510 A:middle L:90%
left graph here looks at how many nodes in my
668
00:36:59.510 --> 00:37:01.489 A:middle L:90%
conflict ng with and the right graph looks at how
669
00:37:01.489 --> 00:37:06.329 A:middle L:90%
many interfere ear's are there. So interferes are sort
670
00:37:06.329 --> 00:37:08.719 A:middle L:90%
of worse than conflicts because interferes or knows that you
671
00:37:08.719 --> 00:37:12.630 A:middle L:90%
have to share the channel with, but in general
672
00:37:12.630 --> 00:37:15.429 A:middle L:90%
you can't really quite see. Um so they're out
673
00:37:15.429 --> 00:37:17.590 A:middle L:90%
there causing you interference and so you can't transmit at
674
00:37:17.590 --> 00:37:21.650 A:middle L:90%
the same time. They do. But CSM a
675
00:37:21.650 --> 00:37:24.150 A:middle L:90%
schemes for instance, don't really resolve that because you
676
00:37:24.159 --> 00:37:27.570 A:middle L:90%
, you may not be able to detect them well
677
00:37:27.570 --> 00:37:30.170 A:middle L:90%
enough to know not to transmit when they're transmitting.
678
00:37:30.199 --> 00:37:34.079 A:middle L:90%
So it's kind of a hidden node kind of phenomenon
679
00:37:36.260 --> 00:37:37.900 A:middle L:90%
. And you can see that r M C A
680
00:37:37.900 --> 00:37:42.480 A:middle L:90%
performs quite well on both of these metrics. Um
681
00:37:44.460 --> 00:37:45.010 A:middle L:90%
, It doesn't, it has a few more.
682
00:37:45.010 --> 00:37:49.000 A:middle L:90%
It has a few interferes, but not very many
683
00:37:49.010 --> 00:37:51.809 A:middle L:90%
. Sometimes we get trapped in cases where we have
684
00:37:51.809 --> 00:37:53.619 A:middle L:90%
to allow some interference in order to achieve our connectivity
685
00:37:53.619 --> 00:37:58.909 A:middle L:90%
goals. Um and it has a relatively low uh
686
00:37:58.920 --> 00:38:01.059 A:middle L:90%
relatively low number of conflict in nodes. So once
687
00:38:01.059 --> 00:38:04.440 A:middle L:90%
you get a network that's 10 or 12 connected,
688
00:38:04.449 --> 00:38:07.710 A:middle L:90%
you're also going to have a very high no degree
689
00:38:07.710 --> 00:38:08.929 A:middle L:90%
in the conflict graph. So lots of nodes sharing
690
00:38:08.929 --> 00:38:13.869 A:middle L:90%
the same channel. Okay, so that's that's sort
691
00:38:13.869 --> 00:38:15.500 A:middle L:90%
of the bulk of the completed work that I'm going
692
00:38:15.500 --> 00:38:19.590 A:middle L:90%
to talk about, although this this next slide is
693
00:38:19.590 --> 00:38:21.960 A:middle L:90%
work that we're doing right now as we speak and
694
00:38:21.960 --> 00:38:23.980 A:middle L:90%
we sort of have some preliminary results. Um and
695
00:38:23.989 --> 00:38:27.389 A:middle L:90%
so in some sense, the traffic independent piece of
696
00:38:27.389 --> 00:38:29.860 A:middle L:90%
this is the easy piece. The easy pieces.
697
00:38:29.860 --> 00:38:32.409 A:middle L:90%
How do you assign channels ignoring traffic? The hard
698
00:38:32.409 --> 00:38:36.159 A:middle L:90%
piece is how do you respond to traffic in the
699
00:38:36.159 --> 00:38:39.590 A:middle L:90%
network in a dynamic fashion? Um And this is
700
00:38:39.590 --> 00:38:44.079 A:middle L:90%
hard even for a fully traffic uh fully traffic driven
701
00:38:44.079 --> 00:38:45.289 A:middle L:90%
scheme, like a back pressure scheme. It's it's
702
00:38:45.289 --> 00:38:49.199 A:middle L:90%
hard to implement. And so our approach has been
703
00:38:49.199 --> 00:38:52.679 A:middle L:90%
this one because we are so two things that that
704
00:38:52.679 --> 00:38:54.530 A:middle L:90%
kind of drive this approach. The first one is
705
00:38:54.539 --> 00:39:00.530 A:middle L:90%
um some some research results, both recent and stretching
706
00:39:00.530 --> 00:39:04.250 A:middle L:90%
back 10 or 15 years, showing that most of
707
00:39:04.250 --> 00:39:07.429 A:middle L:90%
the traffic flows in real deployed networks are heavy tailed
708
00:39:07.440 --> 00:39:13.679 A:middle L:90%
. So something like 90% of the traffic in http
709
00:39:13.679 --> 00:39:16.789 A:middle L:90%
responses is coming from about 10% of the requests.
710
00:39:16.800 --> 00:39:22.860 A:middle L:90%
Um And this is also driven. Um This is
711
00:39:22.860 --> 00:39:27.320 A:middle L:90%
also driven by the fact that we're mostly thinking of
712
00:39:27.329 --> 00:39:29.489 A:middle L:90%
I. P. Like data gram. Kind of
713
00:39:29.489 --> 00:39:34.059 A:middle L:90%
networks where nobody tells you explicitly I'm gonna set up
714
00:39:34.059 --> 00:39:37.050 A:middle L:90%
a flow so you have to implicitly figure out when
715
00:39:37.050 --> 00:39:39.550 A:middle L:90%
flows are happening in the network so that you can
716
00:39:39.550 --> 00:39:43.630 A:middle L:90%
respond appropriately. And so this is what we've been
717
00:39:43.630 --> 00:39:47.480 A:middle L:90%
simulating even in the last couple of weeks is trying
718
00:39:47.480 --> 00:39:52.590 A:middle L:90%
to identify significant flows just by listening to the traffic
719
00:39:52.590 --> 00:39:55.079 A:middle L:90%
in your neighborhood as well as looking at the traffic
720
00:39:55.079 --> 00:40:00.519 A:middle L:90%
going through your node and tracking the source destination pairs
721
00:40:00.530 --> 00:40:04.190 A:middle L:90%
of those say I. P. Data grams in
722
00:40:04.190 --> 00:40:06.869 A:middle L:90%
order to figure out which ones of them are responsible
723
00:40:06.869 --> 00:40:08.159 A:middle L:90%
for most of the traffic. So that's one piece
724
00:40:08.159 --> 00:40:10.559 A:middle L:90%
of it. Is how do you recognize the flows
725
00:40:10.559 --> 00:40:14.389 A:middle L:90%
that are coming through or coming near your node?
726
00:40:14.820 --> 00:40:15.539 A:middle L:90%
And the second piece of it is how do you
727
00:40:15.539 --> 00:40:21.110 A:middle L:90%
respond without having a full global view of the network
728
00:40:21.230 --> 00:40:22.710 A:middle L:90%
? And so this is what we've been looking at
729
00:40:22.719 --> 00:40:24.150 A:middle L:90%
as well. And our approach here has been to
730
00:40:24.150 --> 00:40:29.179 A:middle L:90%
construct a local version of that stage to M I
731
00:40:29.179 --> 00:40:30.099 A:middle L:90%
L P, where the only thing I get to
732
00:40:30.099 --> 00:40:35.050 A:middle L:90%
change our channel assignments in my neighborhood. So I'm
733
00:40:35.050 --> 00:40:37.369 A:middle L:90%
only looking at traffic flows that come through my neighborhood
734
00:40:37.519 --> 00:40:39.699 A:middle L:90%
. And I'm only looking at channel assignments in my
735
00:40:39.699 --> 00:40:44.179 A:middle L:90%
neighborhood and saying what's the best thing I could do
736
00:40:44.179 --> 00:40:45.949 A:middle L:90%
in terms of new channel assignments that would improve the
737
00:40:45.949 --> 00:40:50.730 A:middle L:90%
performance for these flows that I've seen. And our
738
00:40:50.730 --> 00:40:53.420 A:middle L:90%
preliminary results are that while you can't quite track the
739
00:40:53.420 --> 00:40:55.820 A:middle L:90%
global M I L. P, you can see
740
00:40:55.829 --> 00:41:00.340 A:middle L:90%
dramatic improvement. And what we've mostly been measuring here
741
00:41:00.349 --> 00:41:02.750 A:middle L:90%
is average packet delay. And the reason for that
742
00:41:02.750 --> 00:41:06.650 A:middle L:90%
is even though we're optimizing for these big flows,
743
00:41:06.889 --> 00:41:09.389 A:middle L:90%
when those big flows are not handled appropriately, they
744
00:41:09.389 --> 00:41:13.599 A:middle L:90%
introduce all this queuing delay even for the short messages
745
00:41:13.829 --> 00:41:15.510 A:middle L:90%
. And so if you can handle those better than
746
00:41:15.510 --> 00:41:20.789 A:middle L:90%
you see, much improved delay performance for short messages
747
00:41:21.059 --> 00:41:25.780 A:middle L:90%
as well. So now I want to talk about
748
00:41:25.789 --> 00:41:29.230 A:middle L:90%
for just a few minutes, something completely different.
749
00:41:29.230 --> 00:41:31.579 A:middle L:90%
But that I think is is somehow related, at
750
00:41:31.579 --> 00:41:35.869 A:middle L:90%
least at the, at the macro scale. And
751
00:41:35.869 --> 00:41:37.159 A:middle L:90%
so this is the first slide which people have been
752
00:41:37.159 --> 00:41:40.559 A:middle L:90%
using a slide similar to this a lot in my
753
00:41:40.559 --> 00:41:45.179 A:middle L:90%
research community anyway for the last five plus years,
754
00:41:45.250 --> 00:41:49.750 A:middle L:90%
where they say, okay, current spectrum management regimes
755
00:41:49.750 --> 00:41:52.000 A:middle L:90%
date back to the early 19 hundreds there, based
756
00:41:52.000 --> 00:41:55.409 A:middle L:90%
on regulatory assignment by the FCC, if someone else
757
00:41:55.420 --> 00:42:01.070 A:middle L:90%
of spectrum bands and typically based on regulatory determination of
758
00:42:01.070 --> 00:42:04.510 A:middle L:90%
what the services are that can operate in those bands
759
00:42:04.510 --> 00:42:07.329 A:middle L:90%
. What technologies can be used to deliver those services
760
00:42:07.489 --> 00:42:10.429 A:middle L:90%
, and even what operators are allowed to use those
761
00:42:10.429 --> 00:42:15.619 A:middle L:90%
bands to deliver services with the assigned technology. So
762
00:42:15.619 --> 00:42:16.519 A:middle L:90%
that's kind of the picture up there in the top
763
00:42:16.519 --> 00:42:19.869 A:middle L:90%
right that you can't quite see. But we take
764
00:42:19.869 --> 00:42:22.059 A:middle L:90%
the radio spectrum and we say, okay, this
765
00:42:22.059 --> 00:42:24.889 A:middle L:90%
band is for satellite communications and this band is um
766
00:42:25.210 --> 00:42:29.199 A:middle L:90%
and this band is for cellular operations and this band
767
00:42:29.210 --> 00:42:32.530 A:middle L:90%
is for um this band is for microwave, point
768
00:42:32.530 --> 00:42:36.070 A:middle L:90%
to point links and so on and so forth.
769
00:42:36.860 --> 00:42:39.369 A:middle L:90%
And it can be easily shown largely by doing some
770
00:42:39.369 --> 00:42:45.079 A:middle L:90%
spectrum measurements that this technique that this and so these
771
00:42:45.090 --> 00:42:50.260 A:middle L:90%
these these regulatory allocations change extremely slowly over the course
772
00:42:50.260 --> 00:42:53.059 A:middle L:90%
of decades or in some cases with broadcast television even
773
00:42:53.059 --> 00:42:57.090 A:middle L:90%
50 years or more. And so you can pretty
774
00:42:57.090 --> 00:43:00.230 A:middle L:90%
easily show with the spectrum analyzer that you have not
775
00:43:00.230 --> 00:43:02.670 A:middle L:90%
done a good job of efficiently allocating these resources because
776
00:43:02.670 --> 00:43:06.079 A:middle L:90%
you can listen and you can find that even though
777
00:43:06.170 --> 00:43:08.719 A:middle L:90%
the entire spectrum is allocated, most of the spectrum
778
00:43:08.719 --> 00:43:13.480 A:middle L:90%
opportunities in any given place and time are going unused
779
00:43:13.690 --> 00:43:16.809 A:middle L:90%
. So maybe I made an allocation to the military
780
00:43:16.820 --> 00:43:21.429 A:middle L:90%
for communication with military aircraft. Well, unless you're
781
00:43:21.429 --> 00:43:23.639 A:middle L:90%
sitting on an Air Force base, you probably don't
782
00:43:23.639 --> 00:43:27.820 A:middle L:90%
see a lot of communication in that band. Uh
783
00:43:27.829 --> 00:43:29.659 A:middle L:90%
, the other thing that happens with these allocations,
784
00:43:29.659 --> 00:43:30.730 A:middle L:90%
I'm gonna talk about public safety a little bit more
785
00:43:30.730 --> 00:43:32.389 A:middle L:90%
in just a minute. But the other thing that
786
00:43:32.389 --> 00:43:37.139 A:middle L:90%
happens in public safety bands is I have to allocate
787
00:43:37.139 --> 00:43:42.179 A:middle L:90%
enough channels, uh, for incident response and for
788
00:43:42.409 --> 00:43:45.780 A:middle L:90%
big events. Um, even though those are going
789
00:43:45.780 --> 00:43:49.019 A:middle L:90%
to be used most of the time, the Virginia
790
00:43:49.019 --> 00:43:52.940 A:middle L:90%
Tech Police Department has two main channels and most days
791
00:43:52.940 --> 00:43:55.039 A:middle L:90%
they use one, they use their second channel,
792
00:43:55.050 --> 00:43:59.550 A:middle L:90%
football, game day and commencement day. They might
793
00:43:59.550 --> 00:44:00.340 A:middle L:90%
use it for big home basketball games. I don't
794
00:44:00.340 --> 00:44:02.460 A:middle L:90%
know, I don't remember, but they don't use
795
00:44:02.460 --> 00:44:06.139 A:middle L:90%
it very often. They use it for incident kind
796
00:44:06.139 --> 00:44:07.760 A:middle L:90%
of control in response, but it's sitting out there
797
00:44:07.760 --> 00:44:10.059 A:middle L:90%
unused the rest of the time. And this is
798
00:44:10.059 --> 00:44:15.099 A:middle L:90%
true across the vast majority of the, of the
799
00:44:15.099 --> 00:44:17.329 A:middle L:90%
spectrum. And you can particularly see that in some
800
00:44:17.329 --> 00:44:21.550 A:middle L:90%
of these waterfall plots here. Like the one in
801
00:44:21.550 --> 00:44:22.889 A:middle L:90%
the middle on the bottom here, the X axis
802
00:44:22.889 --> 00:44:25.929 A:middle L:90%
is a frequency band, the Y axis is time
803
00:44:25.929 --> 00:44:29.130 A:middle L:90%
. And um, and you can see that many
804
00:44:29.130 --> 00:44:30.889 A:middle L:90%
of those channels you saw little or no activity on
805
00:44:30.969 --> 00:44:32.789 A:middle L:90%
. But then at the far right there, those
806
00:44:32.789 --> 00:44:35.909 A:middle L:90%
are actually cellular bands and you can see those were
807
00:44:35.909 --> 00:44:38.119 A:middle L:90%
extremely busy except those, those little white blocks are
808
00:44:38.119 --> 00:44:40.530 A:middle L:90%
in the middle of the night. And so people
809
00:44:40.530 --> 00:44:44.039 A:middle L:90%
have been, have been making a pitch like this
810
00:44:44.039 --> 00:44:45.030 A:middle L:90%
for the last five plus years and they said,
811
00:44:45.039 --> 00:44:49.400 A:middle L:90%
so we need something totally dynamic. We need to
812
00:44:49.400 --> 00:44:52.409 A:middle L:90%
be able to listen and detect the spectrum is free
813
00:44:52.409 --> 00:44:53.710 A:middle L:90%
and then use it and we need radios that can
814
00:44:53.710 --> 00:44:58.190 A:middle L:90%
operate over the entire spectrum band. And we need
815
00:44:58.190 --> 00:45:00.019 A:middle L:90%
for regulators to allow us to do all of these
816
00:45:00.170 --> 00:45:05.519 A:middle L:90%
dynamic things. But the regulatory response while regulators are
817
00:45:05.519 --> 00:45:09.039 A:middle L:90%
excited about more flexible spectrum allocation, the regulatory response
818
00:45:09.039 --> 00:45:12.599 A:middle L:90%
from a technologist point of view has been kind of
819
00:45:12.699 --> 00:45:15.889 A:middle L:90%
um kind of slow and kind of kind of weak
820
00:45:15.900 --> 00:45:17.889 A:middle L:90%
. What's what's been allowed in the tv band now
821
00:45:17.900 --> 00:45:22.840 A:middle L:90%
is okay, you can use unused tv channels but
822
00:45:22.840 --> 00:45:27.500 A:middle L:90%
you've got to connect via some wired means to a
823
00:45:27.510 --> 00:45:30.230 A:middle L:90%
data base out on the internet to see what's being
824
00:45:30.230 --> 00:45:30.980 A:middle L:90%
used in your area. Before you get to do
825
00:45:30.980 --> 00:45:32.949 A:middle L:90%
this, you can't just rely on sensing, it's
826
00:45:32.949 --> 00:45:37.760 A:middle L:90%
not good enough. And fundamentally the reason for this
827
00:45:37.769 --> 00:45:42.980 A:middle L:90%
is because the technologies, even though people have been
828
00:45:42.980 --> 00:45:45.860 A:middle L:90%
doing research on this for five plus years, the
829
00:45:45.860 --> 00:45:47.780 A:middle L:90%
technologies to answer the hard problems of how do you
830
00:45:47.780 --> 00:45:51.750 A:middle L:90%
reallocate everyone all at the same time? How do
831
00:45:51.750 --> 00:45:54.449 A:middle L:90%
you develop radios that are sufficiently dynamic and so on
832
00:45:54.670 --> 00:45:58.599 A:middle L:90%
? The technology has not developed and there's a lot
833
00:45:58.610 --> 00:46:04.079 A:middle L:90%
of incumbent vested interest in this um in this spectrum
834
00:46:04.079 --> 00:46:06.909 A:middle L:90%
allocation being the way that it's sort of always been
835
00:46:07.030 --> 00:46:09.239 A:middle L:90%
. And so the end result is the pace of
836
00:46:09.239 --> 00:46:14.059 A:middle L:90%
the spectrum regulation. Innovation has been pretty slow and
837
00:46:14.059 --> 00:46:15.980 A:middle L:90%
it turns out that there are a lot of benefits
838
00:46:15.980 --> 00:46:19.019 A:middle L:90%
to the current regime. Um And one of those
839
00:46:19.019 --> 00:46:22.619 A:middle L:90%
is tied really to radio engineering. Because the current
840
00:46:22.619 --> 00:46:25.300 A:middle L:90%
spectrum assignment I get a stable, predictable assignment.
841
00:46:25.300 --> 00:46:29.349 A:middle L:90%
So my smartphone only has to be built to work
842
00:46:29.360 --> 00:46:31.239 A:middle L:90%
on a handful of different bands and can be well
843
00:46:31.239 --> 00:46:36.469 A:middle L:90%
engineered to access those bands and others. So this
844
00:46:36.469 --> 00:46:39.119 A:middle L:90%
leads to efficient, well engineered fit for purpose inexpensive
845
00:46:39.119 --> 00:46:43.829 A:middle L:90%
radios allocated to appropriate bands for what it is that
846
00:46:43.829 --> 00:46:45.739 A:middle L:90%
they want to do. And so a lot of
847
00:46:45.739 --> 00:46:50.139 A:middle L:90%
the proposals for dynamic spectrum access has focused on software
848
00:46:50.139 --> 00:46:52.230 A:middle L:90%
defined radio and the idea has been, everyone's gonna
849
00:46:52.230 --> 00:46:55.949 A:middle L:90%
have a radio that goes from what the E.
850
00:46:55.949 --> 00:46:58.559 A:middle L:90%
S. A. D. C. To daylight
851
00:46:58.570 --> 00:47:00.659 A:middle L:90%
. But anyway, something like 100 megahertz, 23
852
00:47:00.659 --> 00:47:04.960 A:middle L:90%
gigahertz. And it turns out that those radios are
853
00:47:04.960 --> 00:47:07.630 A:middle L:90%
difficult to build. And I'm not saying the technology
854
00:47:07.630 --> 00:47:09.219 A:middle L:90%
is not progressing here, it certainly is. But
855
00:47:09.219 --> 00:47:12.670 A:middle L:90%
in general, if you look at a software defined
856
00:47:12.670 --> 00:47:15.900 A:middle L:90%
radio and a regular in a regular radio with more
857
00:47:15.909 --> 00:47:20.199 A:middle L:90%
customized hardware, the software defined radio is going to
858
00:47:20.199 --> 00:47:23.599 A:middle L:90%
be lower performance, higher cost, lower power efficiency
859
00:47:23.949 --> 00:47:28.960 A:middle L:90%
. And and that doesn't even mention the fact that
860
00:47:28.960 --> 00:47:31.159 A:middle L:90%
the laws of physics really constrain your antenna design.
861
00:47:31.179 --> 00:47:36.469 A:middle L:90%
So it's difficult. Some would say impossible to design
862
00:47:36.469 --> 00:47:38.619 A:middle L:90%
a small handheld antenna that can go from 100 megahertz
863
00:47:38.619 --> 00:47:43.010 A:middle L:90%
, 23 gigahertz. And at the same time,
864
00:47:43.030 --> 00:47:45.849 A:middle L:90%
these different bands are really suited in many cases for
865
00:47:45.849 --> 00:47:49.699 A:middle L:90%
very different purposes. Those high bands have relatively low
866
00:47:49.699 --> 00:47:52.570 A:middle L:90%
propagation, 2.4 gigahertz turns out to be pretty good
867
00:47:52.570 --> 00:47:58.110 A:middle L:90%
band for wifi because it's relatively constrained by buildings and
868
00:47:58.110 --> 00:48:00.579 A:middle L:90%
rooms and so on. Um something down at 100
869
00:48:00.579 --> 00:48:05.219 A:middle L:90%
megahertz, on the other hand, spills out everywhere
870
00:48:05.219 --> 00:48:08.159 A:middle L:90%
because buildings are basically transparent. And so we really
871
00:48:08.159 --> 00:48:12.139 A:middle L:90%
need techniques and this is where I draw a similarity
872
00:48:12.139 --> 00:48:14.920 A:middle L:90%
with the other problem. We really need techniques that
873
00:48:14.929 --> 00:48:17.880 A:middle L:90%
do both that recognize the value of some stability in
874
00:48:17.880 --> 00:48:22.230 A:middle L:90%
the spectrum assignment, but that also allow for some
875
00:48:22.230 --> 00:48:24.280 A:middle L:90%
flexibility, particularly, I would say, on the
876
00:48:24.280 --> 00:48:30.710 A:middle L:90%
margins. And so here's an example from paper from
877
00:48:30.719 --> 00:48:36.219 A:middle L:90%
last year's uh dice ban. Um If you talk
878
00:48:36.219 --> 00:48:37.550 A:middle L:90%
to the public safety people going back to that public
879
00:48:37.550 --> 00:48:40.849 A:middle L:90%
safety example, many of them will tell you that
880
00:48:40.849 --> 00:48:44.539 A:middle L:90%
they need both of these bans. The PSST here
881
00:48:44.539 --> 00:48:46.599 A:middle L:90%
is uh it's obscured here, but it's a public
882
00:48:46.599 --> 00:48:51.590 A:middle L:90%
safety. The public safety Spectrum Trust Band. And
883
00:48:51.590 --> 00:48:52.440 A:middle L:90%
then they'll tell you they also need the D block
884
00:48:52.449 --> 00:48:55.420 A:middle L:90%
, which is another part of the 700 megahertz spectrum
885
00:48:55.800 --> 00:48:59.929 A:middle L:90%
. Well, what's shown in this paper is that
886
00:48:59.940 --> 00:49:04.239 A:middle L:90%
actually those two bands would be nearly perfect for sharing
887
00:49:04.239 --> 00:49:08.199 A:middle L:90%
between say smartphone users and public safety. And this
888
00:49:08.199 --> 00:49:12.210 A:middle L:90%
is shown by developing in some detail in this paper
889
00:49:12.210 --> 00:49:15.949 A:middle L:90%
three scenarios. The top scenario is an everyday use
890
00:49:15.949 --> 00:49:20.139 A:middle L:90%
scenario where even most of that public safety spectrum trust
891
00:49:20.150 --> 00:49:22.559 A:middle L:90%
band is not being used. So these are public
892
00:49:22.559 --> 00:49:25.070 A:middle L:90%
safety users on the right and their um smartphone,
893
00:49:25.070 --> 00:49:29.139 A:middle L:90%
say users on the left. Um So on an
894
00:49:29.139 --> 00:49:30.849 A:middle L:90%
ordinary day public safety is not even using most of
895
00:49:30.849 --> 00:49:35.820 A:middle L:90%
that public safety Spectrum Trust Band. Um On in
896
00:49:35.820 --> 00:49:38.440 A:middle L:90%
an incident response kind of scenario, you would expect
897
00:49:38.440 --> 00:49:42.579 A:middle L:90%
the usage of public safety to grow maybe even into
898
00:49:42.579 --> 00:49:45.380 A:middle L:90%
that D block. But I think most of us
899
00:49:45.380 --> 00:49:47.599 A:middle L:90%
in society would be comfortable with that. Um If
900
00:49:47.610 --> 00:49:52.550 A:middle L:90%
the police and the emergency services need more spectrum right
901
00:49:52.550 --> 00:49:54.039 A:middle L:90%
now to respond to an incident were willing to give
902
00:49:54.039 --> 00:49:58.719 A:middle L:90%
it to them. And then the bottom is a
903
00:49:58.730 --> 00:50:05.369 A:middle L:90%
is a is a wide scale wide area catastrophe scenario
904
00:50:05.409 --> 00:50:07.789 A:middle L:90%
. Um That would happen a very, very small
905
00:50:07.789 --> 00:50:10.940 A:middle L:90%
percentage of the time where most of these two bands
906
00:50:10.940 --> 00:50:15.130 A:middle L:90%
get occupied by public safety. And so this is
907
00:50:15.130 --> 00:50:19.469 A:middle L:90%
an example that illustrates flexibility and spectrum used. But
908
00:50:19.480 --> 00:50:22.530 A:middle L:90%
in a context where the radios can still be built
909
00:50:22.530 --> 00:50:28.840 A:middle L:90%
to operate over a relatively narrow uh portion of the
910
00:50:28.849 --> 00:50:32.940 A:middle L:90%
spectrum. And so and and some of the newer
911
00:50:32.940 --> 00:50:37.309 A:middle L:90%
radio technologies like L T. E, actually make
912
00:50:37.309 --> 00:50:40.440 A:middle L:90%
this very possible um for an allocation, I mean
913
00:50:40.440 --> 00:50:44.940 A:middle L:90%
you need some control over over who's using what,
914
00:50:44.949 --> 00:50:50.369 A:middle L:90%
what band win, but it seems very technologically doable
915
00:50:51.070 --> 00:50:52.889 A:middle L:90%
, but I want to contend that one of the
916
00:50:52.889 --> 00:50:55.260 A:middle L:90%
things that we need in order to enable this kind
917
00:50:55.260 --> 00:51:00.280 A:middle L:90%
of spectrum sharing on the margins is to recognize that
918
00:51:00.289 --> 00:51:05.500 A:middle L:90%
interference between radio systems is a local phenomena. And
919
00:51:05.500 --> 00:51:07.659 A:middle L:90%
so the solutions and a lot of cases need to
920
00:51:07.659 --> 00:51:09.900 A:middle L:90%
be local as well. And I mean both.
921
00:51:09.900 --> 00:51:14.199 A:middle L:90%
I mean that both geographically, I'm going to make
922
00:51:14.210 --> 00:51:16.929 A:middle L:90%
some agreement with this other operator near me as well
923
00:51:16.929 --> 00:51:20.809 A:middle L:90%
as in spectrum, I'm not going to jump probably
924
00:51:20.940 --> 00:51:24.960 A:middle L:90%
from a 100 megahertz allocation to a 1.5 gigahertz allocation
925
00:51:25.559 --> 00:51:29.159 A:middle L:90%
. And so one possible technology that I think can
926
00:51:29.159 --> 00:51:30.210 A:middle L:90%
contribute to this and that I want to spend some
927
00:51:30.210 --> 00:51:34.619 A:middle L:90%
more time looking at over the next year is automated
928
00:51:34.619 --> 00:51:37.519 A:middle L:90%
negotiation between radio systems. And one of the reasons
929
00:51:37.519 --> 00:51:39.280 A:middle L:90%
that I wanted to talk about this here is I
930
00:51:39.280 --> 00:51:44.469 A:middle L:90%
think that this is a very interdisciplinary challenge that draws
931
00:51:44.480 --> 00:51:47.679 A:middle L:90%
on um tools and techniques from a lot of different
932
00:51:47.679 --> 00:51:52.340 A:middle L:90%
fields. Obviously there's electrical and computer engineering to contribute
933
00:51:52.340 --> 00:51:57.300 A:middle L:90%
to the radio engineering, the communications theory as well
934
00:51:57.300 --> 00:52:00.030 A:middle L:90%
as the networking, but there's also a big contribution
935
00:52:00.030 --> 00:52:02.469 A:middle L:90%
here, I think from computer science, in terms
936
00:52:02.480 --> 00:52:07.980 A:middle L:90%
of distributed artificial intelligence and multi agent systems. And
937
00:52:07.980 --> 00:52:09.989 A:middle L:90%
how do we go about building these systems where we
938
00:52:09.989 --> 00:52:13.840 A:middle L:90%
have intelligent agents that cooperate with each other? There's
939
00:52:13.840 --> 00:52:15.539 A:middle L:90%
also a role to play. And this is a
940
00:52:15.539 --> 00:52:16.349 A:middle L:90%
background with some of my other research. But I
941
00:52:16.349 --> 00:52:20.119 A:middle L:90%
didn't talk about it today for economics? What are
942
00:52:20.119 --> 00:52:23.289 A:middle L:90%
the incentives for these users to cooperate with each other
943
00:52:23.289 --> 00:52:25.880 A:middle L:90%
and to share spectrum And and what are their incentives
944
00:52:25.880 --> 00:52:28.929 A:middle L:90%
when they're negotiating with each other? And that comes
945
00:52:28.929 --> 00:52:30.849 A:middle L:90%
into game theory as well as mechanism design, which
946
00:52:30.849 --> 00:52:35.360 A:middle L:90%
also has a lot of impact on computer science these
947
00:52:35.360 --> 00:52:37.070 A:middle L:90%
days. And auction theory designing auctions as well.
948
00:52:37.170 --> 00:52:39.389 A:middle L:90%
And finally, public policy is a big piece of
949
00:52:39.389 --> 00:52:43.599 A:middle L:90%
this. How do you convince regulators? How do
950
00:52:43.599 --> 00:52:45.860 A:middle L:90%
you convince current legacy spectrum holders that this is in
951
00:52:45.860 --> 00:52:50.369 A:middle L:90%
their best interests and that new spectrum management regimes that
952
00:52:50.369 --> 00:52:53.659 A:middle L:90%
do things like this are worthwhile? So I got
953
00:52:53.659 --> 00:52:55.300 A:middle L:90%
a little bit longer than I thought I might.
954
00:52:55.309 --> 00:52:59.650 A:middle L:90%
This is the first time I've given this particular talk
955
00:52:59.789 --> 00:53:01.030 A:middle L:90%
. But what I did for most of the time
956
00:53:01.030 --> 00:53:04.679 A:middle L:90%
here was showed you some promising results that we've been
957
00:53:04.679 --> 00:53:07.289 A:middle L:90%
working on the last couple of years on a traffic
958
00:53:07.289 --> 00:53:10.500 A:middle L:90%
aware approach to channel assignment in a multi transceiver wireless
959
00:53:10.500 --> 00:53:14.409 A:middle L:90%
network. And we've seen that most of the capacity
960
00:53:14.409 --> 00:53:19.750 A:middle L:90%
gains from dynamic channel assignment really come from reallocating a
961
00:53:19.750 --> 00:53:23.139 A:middle L:90%
relatively small proportion of the resources. Um And then
962
00:53:23.139 --> 00:53:27.969 A:middle L:90%
I introduced towards the end here, dynamic spectrum assignment
963
00:53:27.980 --> 00:53:31.230 A:middle L:90%
problem where we think that automated negotiation is one approach
964
00:53:31.230 --> 00:53:35.119 A:middle L:90%
to give you some sort of some flexibility at the
965
00:53:35.119 --> 00:53:39.559 A:middle L:90%
margins through a local process of spectrum management and renegotiation
966
00:53:39.670 --> 00:53:44.539 A:middle L:90%
between the notes and and that's a critical um technology
967
00:53:44.539 --> 00:53:46.449 A:middle L:90%
that I'm interested in. Um And my work on
968
00:53:46.449 --> 00:53:51.170 A:middle L:90%
that is obviously just uh just beginning and I hope
969
00:53:51.170 --> 00:53:53.059 A:middle L:90%
that you'll maybe invite me back in 18 months or
970
00:53:53.059 --> 00:53:55.610 A:middle L:90%
two years and I can tell you, uh,
971
00:53:55.619 --> 00:53:59.570 A:middle L:90%
more about it. So with that I'll wrap up
972
00:53:59.579 --> 00:54:01.489 A:middle L:90%
. These are references mostly from the material I presented
973
00:54:01.489 --> 00:54:05.329 A:middle L:90%
in the actually exclusively the material I presented in the
974
00:54:05.340 --> 00:54:07.199 A:middle L:90%
first half here. Um, a couple of these
975
00:54:07.199 --> 00:54:09.380 A:middle L:90%
are published and a couple of them are under review
976
00:54:09.380 --> 00:54:10.829 A:middle L:90%
. But if you're interested in them, I'm happy
977
00:54:10.829 --> 00:54:15.469 A:middle L:90%
to send you pre prints. Um, and with
978
00:54:15.469 --> 00:54:17.880 A:middle L:90%
that, I'm open to questions here or you're welcome
979
00:54:17.880 --> 00:54:25.980 A:middle L:90%
to, you know, uh, yeah. Thing
980
--> A:middle L:90%
.