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%
.