-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathOppgave.lof
193 lines (193 loc) · 12.6 KB
/
Oppgave.lof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
\boolfalse {citerequest}\boolfalse {citetracker}\boolfalse {pagetracker}\boolfalse {backtracker}\relax
\defcounter {refsection}{0}\relax
\select@language {UKenglish}
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {2.1}{\ignorespaces The hidden terminal problem illustrated\relax }}{7}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {A and C transmitting unknowingly at the same time, resulting in a collision at B}}}{7}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {2.2}{\ignorespaces Minimalist Basic Service Set in infrastructure mode\relax }}{8}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {2.3}{\ignorespaces Extended Service Set\relax }}{9}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {2.4}{\ignorespaces The timeline one frame transmission cycle in DCF mode\relax }}{11}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {2.5}{\ignorespaces Channel distribution\relax }}{14}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {2.6}{\ignorespaces Agglomerative clustering\relax }}{15}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Cluster formation}}}{15}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Dendrogram representation}}}{15}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {2.7}{\ignorespaces Illustration of the K-means clustering algorithm\relax }}{16}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Original dataset}}}{16}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Two centroids (diamond shapes) randomly placed and cluster memberships calculated}}}{16}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {The positions of centroids and the cluster memberships are updated}}}{16}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {The clusters have converged}}}{16}
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.1}{\ignorespaces Pseudocode for computing the signal strength between nodes\relax }}{27}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.2}{\ignorespaces JSON output structure\relax }}{28}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.3}{\ignorespaces Generated topology with random, uniform distribution and the interface for viewing topologies\relax }}{29}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.4}{\ignorespaces WiGLE map of Wi-Fi networks observed in Oslo from 2017-2018\relax }}{30}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.5}{\ignorespaces WiGLE accuracy\relax }}{31}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Few observation points in Ski, Norway}}}{31}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Several observations points in Manhattan, New York}}}{31}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.6}{\ignorespaces Example of a Wigle API request\relax }}{31}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.7}{\ignorespaces REST API response with AP data\relax }}{32}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.8}{\ignorespaces Implementation of haversine distance\relax }}{33}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {4.9}{\ignorespaces The Wi-Fi network topology of Tynset, Norway\relax }}{34}
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.1}{\ignorespaces Group simulation file structure\relax }}{41}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.2}{\ignorespaces Gridlock situation with agglomerative clustering\relax }}{42}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {A wants to merge with B, B with C, C with D and D with A.}}}{42}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.3}{\ignorespaces Pseudocode sample of how the K-Closest Neighbour Clustering runs in a simulated environment\relax }}{44}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.4}{\ignorespaces K-Closest Neighbour Clustering on different topologies\relax }}{45}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Uniform}}}{45}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Forks}}}{45}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {Lillehammer}}}{45}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {Tynset}}}{45}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.5}{\ignorespaces Simplified illustration of the idea behind splitting. K = 2\relax }}{47}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Two neighbouring nodes}}}{47}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {A and B merges. A third node appears}}}{47}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {All nodes joined in transient group}}}{47}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {Splitting to reduce group size}}}{47}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.6}{\ignorespaces K-means splitting on different topologies\relax }}{48}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Uniform}}}{48}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Forks}}}{48}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {Lillehammer}}}{48}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {Tynset}}}{48}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.7}{\ignorespaces Comparison with and without K-means splitting on Tynset\relax }}{49}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Without K-means splitting}}}{49}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {With K-means splitting}}}{49}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.8}{\ignorespaces Comparison with and without K-means splitting on uniform distribution\relax }}{50}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Without K-means splitting}}}{50}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {With K-means splitting}}}{50}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.9}{\ignorespaces Flowchart of the minimum cut implementation for splitting\relax }}{52}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.10}{\ignorespaces Pseudocode of the minimum cut stage of the splitting\relax }}{53}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.11}{\ignorespaces Minimum cut illustration with group maximum size set to 5\relax }}{54}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Two groups are initially too large to merge. A split is going to be attempted. }}}{54}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Both groups identify edges which should not be cut, marked by an infinite edge weight}}}{54}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {The groups excludes the partitions with the lowest capacity cuts}}}{54}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {The number of members of the groups combined is now lower than maximum size, and the merge is succesful}}}{54}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.12}{\ignorespaces Minimum cut algorithm splitting on different topologies\relax }}{55}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Uniform}}}{55}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Forks}}}{55}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {Lillehammer}}}{55}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {Tynset}}}{55}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.13}{\ignorespaces Comparison between K-means splitting and minimum cut splitting on Tynset\relax }}{56}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {With K-means splitting}}}{56}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {With minimum cut splitting}}}{56}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.14}{\ignorespaces Illustrating two algorithm iterations to find the problem source of the minimum cut\relax }}{57}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Iteration 8: The green group seeks to merge with the pink, the signal strength between them for instance being -45dBi}}}{57}
\defcounter {refsection}{0}\relax
\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Iteration 9: After the minimum cut split, some nodes have been thrown out to allow for the merge}}}{57}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {5.15}{\ignorespaces Bouldin-Index of all simulations\relax }}{59}
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {6.1}{\ignorespaces Overview of a protocol components \relax }}{66}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {6.2}{\ignorespaces The roles of a DGCP Node \relax }}{67}
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\addvspace {10\p@ }
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.2}{\ignorespaces Forks, Washington, USA\relax }}{78}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.1}{\ignorespaces Uniform distribution, 500x500, 1000 nodes\relax }}{79}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.3}{\ignorespaces Lillehammer, Norway\relax }}{79}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.4}{\ignorespaces Tynset, Norway\relax }}{80}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.6}{\ignorespaces Forks, Washington, USA\relax }}{80}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.5}{\ignorespaces Uniform distribution, 500x500, 1000 nodes\relax }}{81}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.7}{\ignorespaces Lillehammer, Norway\relax }}{81}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.8}{\ignorespaces Tynset, Norway\relax }}{82}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.10}{\ignorespaces Forks, Washington, USA\relax }}{82}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.9}{\ignorespaces Uniform distribution, 500x500, 1000 nodes\relax }}{83}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.11}{\ignorespaces Lillehammer, Norway\relax }}{83}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.12}{\ignorespaces Tynset, Norway\relax }}{84}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.14}{\ignorespaces Forks, Washington, USA\relax }}{84}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.13}{\ignorespaces Uniform distribution, 500x500, 1000 nodes\relax }}{85}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.15}{\ignorespaces Lillehammer, Norway\relax }}{85}
\defcounter {refsection}{0}\relax
\contentsline {figure}{\numberline {A.16}{\ignorespaces Tynset, Norway\relax }}{86}