-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathOppgave.bkup
2955 lines (2823 loc) · 184 KB
/
Oppgave.bkup
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
00000000: 5c64 6f63 756d 656e 7463 6c61 7373 5b61 \documentclass[a
00000010: 3470 6170 6572 2c55 4b65 6e67 6c69 7368 4paper,UKenglish
00000020: 5d7b 7265 706f 7274 7d0a 5c75 7365 7061 ]{report}.\usepa
00000030: 636b 6167 655b 7574 6638 5d7b 696e 7075 ckage[utf8]{inpu
00000040: 7465 6e63 7d0a 5c75 7365 7061 636b 6167 tenc}.\usepackag
00000050: 657b 616c 676f 7269 7468 6d7d 0a5c 7573 e{algorithm}.\us
00000060: 6570 6163 6b61 6765 7b61 6d73 6d61 7468 epackage{amsmath
00000070: 7d0a 5c75 7365 7061 636b 6167 655b 6e6f }.\usepackage[no
00000080: 656e 645d 7b61 6c67 7073 6575 646f 636f end]{algpseudoco
00000090: 6465 7d0a 5c75 7365 7061 636b 6167 657b de}.\usepackage{
000000a0: 6261 6265 6c2c 6373 7175 6f74 6573 2c64 babel,csquotes,d
000000b0: 756f 6d61 7374 6572 666f 7273 6964 657d uomasterforside}
000000c0: 0a5c 7573 6570 6163 6b61 6765 7b6c 6973 .\usepackage{lis
000000d0: 7469 6e67 737d 0a5c 7573 6570 6163 6b61 tings}.\usepacka
000000e0: 6765 7b77 7261 7066 6967 7d0a 5c75 7365 ge{wrapfig}.\use
000000f0: 7061 636b 6167 657b 6772 6170 6869 6378 package{graphicx
00000100: 7d0a 5c75 7365 7061 636b 6167 655b 6261 }.\usepackage[ba
00000110: 636b 656e 643d 6269 6265 722c 0a09 2020 ckend=biber,..
00000120: 2020 7374 796c 653d 6e75 6d65 7269 632c style=numeric,
00000130: 0a09 2020 2020 6369 7465 7374 796c 653d .. citestyle=
00000140: 6e75 6d65 7269 635d 7b62 6962 6c61 7465 numeric]{biblate
00000150: 787d 0a0a 5c61 6464 6269 6272 6573 6f75 x}..\addbibresou
00000160: 7263 657b 7265 6665 7265 6e63 6573 2e62 rce{references.b
00000170: 6962 7d0a 0a5c 7573 6570 6163 6b61 6765 ib}..\usepackage
00000180: 7b78 636f 6c6f 727d 0a0a 5c75 7365 7061 {xcolor}..\usepa
00000190: 636b 6167 657b 6361 7074 696f 6e7d 0a5c ckage{caption}.\
000001a0: 7573 6570 6163 6b61 6765 7b73 7562 6361 usepackage{subca
000001b0: 7074 696f 6e7d 0a5c 636f 6c6f 726c 6574 ption}.\colorlet
000001c0: 7b70 756e 6374 7d7b 7265 6421 3630 2162 {punct}{red!60!b
000001d0: 6c61 636b 7d0a 5c64 6566 696e 6563 6f6c lack}.\definecol
000001e0: 6f72 7b62 6163 6b67 726f 756e 647d 7b48 or{background}{H
000001f0: 544d 4c7d 7b45 4545 4545 457d 0a5c 6465 TML}{EEEEEE}.\de
00000200: 6669 6e65 636f 6c6f 727b 6465 6c69 6d7d finecolor{delim}
00000210: 7b52 4742 7d7b 3230 2c31 3035 2c31 3736 {RGB}{20,105,176
00000220: 7d0a 5c63 6f6c 6f72 6c65 747b 6e75 6d62 }.\colorlet{numb
00000230: 7d7b 6d61 6765 6e74 6121 3630 2162 6c61 }{magenta!60!bla
00000240: 636b 7d0a 0a5c 6c73 7464 6566 696e 656c ck}..\lstdefinel
00000250: 616e 6775 6167 657b 6a73 6f6e 7d7b 0a09 anguage{json}{..
00000260: 6261 7369 6373 7479 6c65 3d5c 6e6f 726d basicstyle=\norm
00000270: 616c 666f 6e74 5c74 7466 616d 696c 792c alfont\ttfamily,
00000280: 0a20 2020 206e 756d 6265 7273 3d6c 6566 . numbers=lef
00000290: 742c 0a20 2020 206e 756d 6265 7273 7479 t,. numbersty
000002a0: 6c65 3d5c 7363 7269 7074 7369 7a65 2c0a le=\scriptsize,.
000002b0: 2020 2020 7374 6570 6e75 6d62 6572 3d31 stepnumber=1
000002c0: 2c0a 2020 2020 6e75 6d62 6572 7365 703d ,. numbersep=
000002d0: 3870 742c 0a20 2020 2073 686f 7773 7472 8pt,. showstr
000002e0: 696e 6773 7061 6365 733d 6661 6c73 652c ingspaces=false,
000002f0: 0a20 2020 2062 7265 616b 6c69 6e65 733d . breaklines=
00000300: 7472 7565 2c0a 2020 2020 6261 636b 6772 true,. backgr
00000310: 6f75 6e64 636f 6c6f 723d 5c63 6f6c 6f72 oundcolor=\color
00000320: 7b62 6163 6b67 726f 756e 647d 2c0a 2020 {background},.
00000330: 2020 6c69 7465 7261 7465 3d0a 2020 2020 literate=.
00000340: 202a 7b30 7d7b 7b7b 5c63 6f6c 6f72 7b6e *{0}{{{\color{n
00000350: 756d 627d 307d 7d7d 7b31 7d0a 2020 2020 umb}0}}}{1}.
00000360: 2020 7b31 7d7b 7b7b 5c63 6f6c 6f72 7b6e {1}{{{\color{n
00000370: 756d 627d 317d 7d7d 7b31 7d0a 2020 2020 umb}1}}}{1}.
00000380: 2020 7b32 7d7b 7b7b 5c63 6f6c 6f72 7b6e {2}{{{\color{n
00000390: 756d 627d 327d 7d7d 7b31 7d0a 2020 2020 umb}2}}}{1}.
000003a0: 2020 7b33 7d7b 7b7b 5c63 6f6c 6f72 7b6e {3}{{{\color{n
000003b0: 756d 627d 337d 7d7d 7b31 7d0a 2020 2020 umb}3}}}{1}.
000003c0: 2020 7b34 7d7b 7b7b 5c63 6f6c 6f72 7b6e {4}{{{\color{n
000003d0: 756d 627d 347d 7d7d 7b31 7d0a 2020 2020 umb}4}}}{1}.
000003e0: 2020 7b35 7d7b 7b7b 5c63 6f6c 6f72 7b6e {5}{{{\color{n
000003f0: 756d 627d 357d 7d7d 7b31 7d0a 2020 2020 umb}5}}}{1}.
00000400: 2020 7b36 7d7b 7b7b 5c63 6f6c 6f72 7b6e {6}{{{\color{n
00000410: 756d 627d 367d 7d7d 7b31 7d0a 2020 2020 umb}6}}}{1}.
00000420: 2020 7b37 7d7b 7b7b 5c63 6f6c 6f72 7b6e {7}{{{\color{n
00000430: 756d 627d 377d 7d7d 7b31 7d0a 2020 2020 umb}7}}}{1}.
00000440: 2020 7b38 7d7b 7b7b 5c63 6f6c 6f72 7b6e {8}{{{\color{n
00000450: 756d 627d 387d 7d7d 7b31 7d0a 2020 2020 umb}8}}}{1}.
00000460: 2020 7b39 7d7b 7b7b 5c63 6f6c 6f72 7b6e {9}{{{\color{n
00000470: 756d 627d 397d 7d7d 7b31 7d0a 2020 2020 umb}9}}}{1}.
00000480: 2020 7b3a 7d7b 7b7b 5c63 6f6c 6f72 7b70 {:}{{{\color{p
00000490: 756e 6374 7d7b 3a7d 7d7d 7d7b 317d 0a20 unct}{:}}}}{1}.
000004a0: 2020 2020 207b 2c7d 7b7b 7b5c 636f 6c6f {,}{{{\colo
000004b0: 727b 7075 6e63 747d 7b2c 7d7d 7d7d 7b31 r{punct}{,}}}}{1
000004c0: 7d0a 2020 2020 2020 7b5c 7b7d 7b7b 7b5c }. {\{}{{{\
000004d0: 636f 6c6f 727b 6465 6c69 6d7d 7b5c 7b7d color{delim}{\{}
000004e0: 7d7d 7d7b 317d 0a20 2020 2020 207b 5c7d }}}{1}. {\}
000004f0: 7d7b 7b7b 5c63 6f6c 6f72 7b64 656c 696d }{{{\color{delim
00000500: 7d7b 5c7d 7d7d 7d7d 7b31 7d0a 2020 2020 }{\}}}}}{1}.
00000510: 2020 7b5b 7d7b 7b7b 5c63 6f6c 6f72 7b64 {[}{{{\color{d
00000520: 656c 696d 7d7b 5b7d 7d7d 7d7b 317d 0a20 elim}{[}}}}{1}.
00000530: 2020 2020 207b 5d7d 7b7b 7b5c 636f 6c6f {]}{{{\colo
00000540: 727b 6465 6c69 6d7d 7b5d 7d7d 7d7d 7b31 r{delim}{]}}}}{1
00000550: 7d2c 0a7d 0a5c 7469 746c 657b 4772 6f75 },.}.\title{Grou
00000560: 7020 6372 6561 7469 6f6e 2069 6e20 6120 p creation in a
00000570: 636f 6c6c 6162 6f72 6174 6976 6520 5032 collaborative P2
00000580: 5020 6368 616e 6e65 6c20 616c 6c6f 6361 P channel alloca
00000590: 7469 6f6e 2070 726f 746f 636f 6c7d 0a5c tion protocol}.\
000005a0: 7375 6274 6974 6c65 7b49 6465 6e74 6966 subtitle{Identif
000005b0: 7969 6e67 2063 6f6e 6e65 6374 6564 2067 ying connected g
000005c0: 726f 7570 7320 6f66 2061 6363 6573 7320 roups of access
000005d0: 706f 696e 7473 7d0a 5c61 7574 686f 727b points}.\author{
000005e0: 4861 6e73 204a c3b8 7267 656e 2046 7572 Hans J..rgen Fur
000005f0: 7265 204e 7967 c3a5 7264 7368 6175 677d re Nyg..rdshaug}
00000600: 0a0a 5c62 6567 696e 7b64 6f63 756d 656e ..\begin{documen
00000610: 747d 0a5c 6475 6f66 6f72 7369 6465 5b64 t}.\duoforside[d
00000620: 6570 743d 7b49 6e73 7469 7475 7474 2066 ept={Institutt f
00000630: 6f72 2069 6e66 6f72 6d61 7469 6b6b 7d2c or informatikk},
00000640: 0a20 2070 726f 6772 616d 3d7b 496e 666f . program={Info
00000650: 726d 6174 696b 6b3a 2070 726f 6772 616d rmatikk: program
00000660: 6d65 7269 6e67 206f 6720 6e65 7474 7665 mering og nettve
00000670: 726b 7d2c 0a20 206c 6f6e 675d 0a5c 7365 rk},. long].\se
00000680: 6374 696f 6e2a 7b41 6273 7472 6163 747d ction*{Abstract}
00000690: 0a0a 5c63 6c65 6172 7061 6765 0a5c 7365 ..\clearpage.\se
000006a0: 6374 696f 6e2a 7b4c 6973 7420 6f66 2061 ction*{List of a
000006b0: 6372 6f6e 796d 737d 0a5c 6265 6769 6e7b cronyms}.\begin{
000006c0: 7461 6275 6c61 727d 7b20 6320 6320 7d0a tabular}{ c c }.
000006d0: 095c 7465 7874 6266 7b41 507d 2026 2041 .\textbf{AP} & A
000006e0: 6363 6573 7320 506f 696e 745c 5c20 0a09 ccess Point\\ ..
000006f0: 5c74 6578 7462 667b 4353 4d41 2f43 417d \textbf{CSMA/CA}
00000700: 2026 2043 6172 7269 6572 2053 656e 7365 & Carrier Sense
00000710: 204d 756c 7469 706c 6520 4163 6365 7373 Multiple Access
00000720: 202f 2043 6f6c 6c69 7369 6f6e 2041 766f / Collision Avo
00000730: 6964 616e 6365 5c5c 0a09 5c74 6578 7462 idance\\..\textb
00000740: 667b 4d41 437d 2026 204d 6564 6975 6d20 f{MAC} & Medium
00000750: 4163 6365 7373 2043 6f6e 7472 6f6c 5c5c Access Control\\
00000760: 0a09 5c74 6578 7462 667b 4343 417d 2026 ..\textbf{CCA} &
00000770: 2043 6c65 6172 2043 6861 6e6e 656c 2041 Clear Channel A
00000780: 7373 6573 736d 656e 745c 5c0a 095c 7465 ssessment\\..\te
00000790: 7874 6266 7b4d 4143 7d20 2620 4d61 6e64 xtbf{MAC} & Mand
000007a0: 6174 6f72 7920 4163 6365 7373 2043 6f6e atory Access Con
000007b0: 7472 6f6c 5c5c 0a09 5c74 6578 7462 667b trol\\..\textbf{
000007c0: 5048 597d 2026 2050 6879 7369 6361 6c20 PHY} & Physical
000007d0: 4c61 7965 725c 5c0a 5c65 6e64 7b74 6162 Layer\\.\end{tab
000007e0: 756c 6172 7d0a 5c74 6162 6c65 6f66 636f ular}.\tableofco
000007f0: 6e74 656e 7473 0a25 5c63 6861 7074 6572 ntents.%\chapter
00000800: 7b44 6973 706f 7369 7469 6f6e 7d20 0a25 {Disposition} .%
00000810: 5c73 6563 7469 6f6e 207b 496e 7472 6f64 \section {Introd
00000820: 7563 7469 6f6e 2070 6172 747d 0a25 5c62 uction part}.%\b
00000830: 6567 696e 7b69 7465 6d69 7a65 7d20 0a09 egin{itemize} ..
00000840: 255c 6974 656d 2049 6e74 726f 6475 6374 %\item Introduct
00000850: 696f 6e20 746f 2074 6865 2077 6966 6920 ion to the wifi
00000860: 696e 7465 7266 6572 656e 6365 2070 726f interference pro
00000870: 626c 656d 0a09 255c 6974 656d 2054 616b blem..%\item Tak
00000880: 696e 6720 6120 7374 6570 2062 6163 6b20 ing a step back
00000890: 616e 6420 6c6f 6f6b 696e 6720 6174 206f and looking at o
000008a0: 7468 6572 2061 7474 656d 7074 7320 6f6e ther attempts on
000008b0: 2073 6f6c 7669 6e67 2074 6865 2070 726f solving the pro
000008c0: 626c 656d 0a09 255c 6974 656d 2042 6567 blem..%\item Beg
000008d0: 696e 2070 7265 7365 6e74 696e 6720 546f in presenting To
000008e0: 726c 6569 7620 616e 6420 4d61 676e 7573 rleiv and Magnus
000008f0: 2077 6f72 6b2c 2074 6865 2069 6465 612c work, the idea,
00000900: 2061 6e64 206d 6179 6265 2074 6865 2070 and maybe the p
00000910: 3270 2070 726f 746f 636f 6c2e 0a25 5c65 2p protocol..%\e
00000920: 6e64 7b69 7465 6d69 7a65 7d0a 0a25 5c73 nd{itemize}..%\s
00000930: 6563 7469 6f6e 207b 4d61 696e 2074 6865 ection {Main the
00000940: 7369 7320 7061 7274 7d0a 255c 7375 6273 sis part}.%\subs
00000950: 6563 7469 6f6e 7b47 726f 7570 2061 6c6c ection{Group all
00000960: 6f63 6174 696f 6e20 616c 676f 7269 7468 ocation algorith
00000970: 6d7d 200a 0a25 5c62 6567 696e 7b69 7465 m} ..%\begin{ite
00000980: 6d69 7a65 7d20 0a09 255c 6974 656d 2054 mize} ..%\item T
00000990: 6865 2070 726f 626c 656d 2e0a 0925 5c69 he problem...%\i
000009a0: 7465 6d20 506f 7373 6962 6c65 2073 6f6c tem Possible sol
000009b0: 7574 696f 6e73 3f20 5265 6665 7265 6e63 utions? Referenc
000009c0: 6573 2e0a 0925 5c69 7465 6d20 436f 6d70 es...%\item Comp
000009d0: 6c65 7869 7479 2c20 6f75 7420 6f66 2073 lexity, out of s
000009e0: 636f 7065 2066 6f72 2074 6865 7369 732e cope for thesis.
000009f0: 2041 7373 756d 6520 7072 6f62 6c65 6d20 Assume problem
00000a00: 6973 2073 6f6c 7665 642e 0a25 5c65 6e64 is solved..%\end
00000a10: 7b69 7465 6d69 7a65 7d20 0a25 5c73 7562 {itemize} .%\sub
00000a20: 7365 6374 696f 6e7b 5468 6520 616c 676f section{The algo
00000a30: 7269 7468 6d20 6974 7365 6c66 7d20 0a25 rithm itself} .%
00000a40: 5c62 6567 696e 7b69 7465 6d69 7a65 7d20 \begin{itemize}
00000a50: 0a09 255c 6974 656d 2045 6c61 626f 7261 ..%\item Elabora
00000a60: 7469 6e67 206f 6e20 7468 6520 7072 6f62 ting on the prob
00000a70: 6c65 6d2c 2069 6e74 726f 6475 6369 6e67 lem, introducing
00000a80: 2074 6865 2066 6972 7374 2061 6c67 6f72 the first algor
00000a90: 6974 686d 2073 7567 6765 7374 696f 6e2e ithm suggestion.
00000aa0: 0a09 255c 6974 656d 2045 7870 6c61 696e ..%\item Explain
00000ab0: 2073 696d 756c 6174 696f 6e20 6461 7461 simulation data
00000ac0: 2063 7265 6174 696f 6e20 7769 7468 2073 creation with s
00000ad0: 746f 6368 6173 7469 6320 756e 6966 6f72 tochastic unifor
00000ae0: 6d20 6469 7374 7269 6275 7469 6f6e 2e0a m distribution..
00000af0: 0925 5c69 7465 6d20 5368 6f77 2068 6f77 .%\item Show how
00000b00: 2074 6865 2067 726f 7570 2063 7265 6174 the group creat
00000b10: 696f 6e20 616c 676f 7269 7468 2077 6173 ion algorith was
00000b20: 2063 7265 6174 6564 2c20 6465 7369 676e created, design
00000b30: 2064 6563 6973 696f 6e73 2028 6974 6572 decisions (iter
00000b40: 6174 696f 6e73 2065 7463 292e 0a09 255c ations etc)...%\
00000b50: 6974 656d 2052 6573 756c 7473 2077 6974 item Results wit
00000b60: 6820 7669 7375 616c 697a 6174 696f 6e73 h visualizations
00000b70: 2074 6872 6f75 6768 2074 6865 2076 6973 through the vis
00000b80: 7561 6c69 7a61 7469 6f6e 2074 6f6f 6c2e ualization tool.
00000b90: 200a 0925 5c69 7465 6d20 4576 616c 7561 ..%\item Evalua
00000ba0: 7465 2072 6573 756c 7473 2061 6e64 2063 te results and c
00000bb0: 6f6e 7369 6465 7220 696d 7072 6f76 656d onsider improvem
00000bc0: 656e 7473 2e20 486f 7720 7769 6c6c 2074 ents. How will t
00000bd0: 6869 7320 776f 726b 2069 6e20 7468 6520 his work in the
00000be0: 7769 6c64 3f0a 0925 5c69 7465 6d20 496e wild?..%\item In
00000bf0: 7472 6f64 7563 6520 5353 4220 6461 7461 troduce SSB data
00000c00: 2c20 7468 6520 6461 7461 2066 6f72 6d61 , the data forma
00000c10: 7420 616e 6420 7768 7920 6974 2069 7320 t and why it is
00000c20: 7265 6c65 7661 6e74 2e20 486f 7720 6973 relevant. How is
00000c30: 2074 6865 2074 6f6f 6c20 6d61 6465 2e0a the tool made..
00000c40: 0925 5c69 7465 6d20 5361 6d65 2070 726f .%\item Same pro
00000c50: 6365 6475 7265 2077 6974 6820 7265 7375 cedure with resu
00000c60: 6c74 2076 6973 7561 6c69 7a61 7469 6f6e lt visualization
00000c70: 2061 6e64 2072 6573 756c 7420 6576 616c and result eval
00000c80: 7561 7469 6f6e 2e20 446f 2077 6520 7374 uation. Do we st
00000c90: 696c 6c20 6e65 6564 2069 6d70 726f 7665 ill need improve
00000ca0: 6d65 6e74 733f 0a09 255c 6974 656d 2049 ments?..%\item I
00000cb0: 6e74 726f 6475 6369 6e67 2057 6967 6c65 ntroducing Wigle
00000cc0: 2061 7320 6461 7461 2073 6f75 7263 652e as data source.
00000cd0: 2053 686f 7720 7265 7375 6c74 7320 6f6e Show results on
00000ce0: 206d 6170 3f0a 255c 656e 647b 6974 656d map?.%\end{item
00000cf0: 697a 657d 0a0a 255c 7365 6374 696f 6e20 ize}..%\section
00000d00: 7b43 6f6e 636c 7564 696e 6720 7061 7274 {Concluding part
00000d10: 7d0a 255c 6265 6769 6e7b 6974 656d 697a }.%\begin{itemiz
00000d20: 657d 200a 0925 5c69 7465 6d20 4861 7665 e} ..%\item Have
00000d30: 2077 6520 6372 6561 7465 6420 6120 6d65 we created a me
00000d40: 616e 696e 6766 756c 2061 6c67 6f72 6974 aningful algorit
00000d50: 686d 2074 6861 7420 6361 6e20 6265 2069 hm that can be i
00000d60: 6d70 6c65 6d65 6e74 6564 2069 6e20 6861 mplemented in ha
00000d70: 7264 7761 7265 3f0a 255c 656e 647b 6974 rdware?.%\end{it
00000d80: 656d 697a 657d 0a0a 255c 636c 6561 7270 emize}..%\clearp
00000d90: 6167 650a 5c63 6861 7074 6572 7b49 6e74 age.\chapter{Int
00000da0: 726f 6475 6374 696f 6e7d 0a2d 2045 7870 roduction}.- Exp
00000db0: 616e 7369 6f6e 206f 6620 5769 4649 0a2d ansion of WiFI.-
00000dc0: 2044 656e 7365 6c79 2070 6f70 756c 6174 Densely populat
00000dd0: 6564 2041 7265 6173 0a2d 2049 6e63 7265 ed Areas.- Incre
00000de0: 6173 6564 2075 7361 6765 0a2d 2045 7870 ased usage.- Exp
00000df0: 6563 7461 7469 6f6e 7320 6f66 2075 6e69 ectations of uni
00000e00: 7665 7273 616c 2077 6966 690a 2d20 436f versal wifi.- Co
00000e10: 6e67 6573 7465 6420 6e65 7477 6f72 6b73 ngested networks
00000e20: 2062 6563 6175 7365 206f 6620 696e 7465 because of inte
00000e30: 7265 6665 7265 6e63 650a 0a5c 7365 6374 reference..\sect
00000e40: 696f 6e7b 5072 6f62 6c65 6d20 6465 6669 ion{Problem defi
00000e50: 6e69 7469 6f6e 7d0a 5468 6520 7072 6f62 nition}.The prob
00000e60: 6c65 6d20 6973 2074 6861 7420 6465 7669 lem is that devi
00000e70: 6365 7320 6f70 6572 6174 696e 6720 6f6e ces operating on
00000e80: 2074 6865 2073 616d 6520 6368 616e 6e65 the same channe
00000e90: 6c20 696e 2074 6865 2073 616d 6520 6172 l in the same ar
00000ea0: 6561 2069 6e74 6572 6665 7265 7320 7769 ea interferes wi
00000eb0: 7468 206f 6e65 2061 6e6f 7468 6572 2e0a th one another..
00000ec0: 0a5c 7365 6374 696f 6e7b 4d6f 7469 7661 .\section{Motiva
00000ed0: 7469 6f6e 7d0a 5769 6669 2069 7320 6465 tion}.Wifi is de
00000ee0: 706c 6f79 6564 2069 6e20 616c 6d6f 7374 ployed in almost
00000ef0: 2061 6c6c 2072 6573 6964 656e 6369 6573 all residencies
00000f00: 2c20 616e 6420 7468 6520 7072 6f62 6c65 , and the proble
00000f10: 6d20 6973 2065 7370 6563 6961 6c6c 7920 m is especially
00000f20: 7072 6f6d 696e 656e 7420 696e 2064 656e prominent in den
00000f30: 7365 6c79 2070 6f70 756c 6174 6564 2061 sely populated a
00000f40: 7265 6173 2e20 0a0a 5c73 6563 7469 6f6e reas. ..\section
00000f50: 7b4d 6574 686f 647d 0a44 6566 696e 696e {Method}.Definin
00000f60: 6720 6772 6f75 7073 2066 6f72 2072 756e g groups for run
00000f70: 6e69 6e67 2061 2063 6861 6e6e 656c 2061 ning a channel a
00000f80: 6c6c 6f63 6174 696f 6e20 616c 676f 7269 llocation algori
00000f90: 7468 6d20 6f6e 0a0a 5c73 6563 7469 6f6e thm on..\section
00000fa0: 7b43 6861 6e6e 656c 2061 6c6c 6f63 6174 {Channel allocat
00000fb0: 696f 6e7d 200a 546f 2064 6561 6c20 7769 ion} .To deal wi
00000fc0: 7468 2074 6865 2070 726f 626c 656d 206f th the problem o
00000fd0: 6620 6368 616e 6e65 6c20 616c 6c6f 6361 f channel alloca
00000fe0: 7469 6f6e 2077 6520 7769 6c6c 2074 6869 tion we will thi
00000ff0: 6e6b 206f 6620 616e 2041 5020 6173 2061 nk of an AP as a
00001000: 2076 6572 7465 7820 696e 2061 2067 7261 vertex in a gra
00001010: 7068 2e20 5768 656e 2061 6e20 4150 2073 ph. When an AP s
00001020: 6361 6e73 2069 7473 2072 6164 696f 0a69 cans its radio.i
00001030: 7420 6361 6e20 6865 6172 2074 6865 2073 t can hear the s
00001040: 7472 656e 6774 6820 6f66 2061 6c6c 206e trength of all n
00001050: 6561 7262 7920 7769 7265 6c65 7373 206e earby wireless n
00001060: 6574 776f 726b 7320 6d65 6173 7572 6564 etworks measured
00001070: 2069 6e20 6442 6d20 2864 6563 6962 656c in dBm (decibel
00001080: 206d 696c 6c69 7761 7474 7329 2e20 5468 milliwatts). Th
00001090: 6973 2064 6563 6962 656c 2076 616c 7565 is decibel value
000010a0: 2077 696c 6c20 6265 0a74 6865 2076 616c will be.the val
000010b0: 7565 206f 6620 7468 6520 6564 6765 2062 ue of the edge b
000010c0: 6574 7765 656e 206f 6e65 2041 5020 746f etween one AP to
000010d0: 2061 6e6f 7468 6572 2e20 5769 7468 2061 another. With a
000010e0: 2067 7261 7068 2065 7870 7265 7373 696e graph expressin
000010f0: 6720 7468 6520 7769 7265 6c65 7373 206e g the wireless n
00001100: 6574 776f 726b 2074 6f70 6f6c 6f67 792c etwork topology,
00001110: 2074 6865 2070 726f 626c 656d 0a6f 6620 the problem.of
00001120: 6f70 7469 6d61 6c6c 7920 6469 7374 7269 optimally distri
00001130: 6275 7469 6e67 2063 6861 6e6e 656c 7320 buting channels
00001140: 6265 7477 6565 6e20 4150 7320 626f 696c between APs boil
00001150: 7320 646f 776e 2074 6f20 6120 6772 6170 s down to a grap
00001160: 6820 636f 6c6f 7269 6e67 2070 726f 626c h coloring probl
00001170: 656d 2e20 5468 6520 6e75 6d62 6572 206f em. The number o
00001180: 6620 636f 6c6f 7273 2069 6e20 7468 6520 f colors in the
00001190: 636f 6c6f 7220 7072 6f62 6c65 6d2c 0a72 color problem,.r
000011a0: 6570 7265 7365 6e74 7320 7468 6520 6e75 epresents the nu
000011b0: 6d62 6572 206f 6620 6e6f 6e2d 6f76 6572 mber of non-over
000011c0: 6c61 7070 696e 6720 6368 616e 6e65 6c73 lapping channels
000011d0: 2069 6e20 3830 322e 3131 2e20 4578 6163 in 802.11. Exac
000011e0: 746c 7920 686f 7720 616e 2061 6c67 6f72 tly how an algor
000011f0: 6974 686d 2063 616e 2062 6520 6465 7369 ithm can be desi
00001200: 676e 6564 2074 6f20 6f70 7469 6d61 6c6c gned to optimall
00001210: 7920 6469 7374 7269 6275 7465 2063 6861 y distribute cha
00001220: 6e6e 656c 7320 7769 7468 696e 2074 6865 nnels within the
00001230: 0a69 6e74 6572 6665 7269 6e67 2074 6f70 .interfering top
00001240: 6f6c 6f67 7920 6973 206f 7574 206f 6620 ology is out of
00001250: 7468 6520 7363 6f70 6520 6f66 2074 6869 the scope of thi
00001260: 7320 7468 6573 6973 2e20 486f 7765 7665 s thesis. Howeve
00001270: 7220 7765 2063 616e 2064 6566 696e 6520 r we can define
00001280: 736f 6d65 2069 6e76 6172 6961 6e74 7320 some invariants
00001290: 7468 6174 2068 6173 2074 6f20 6265 2074 that has to be t
000012a0: 7275 650a 666f 7220 7375 6368 2061 6e20 rue.for such an
000012b0: 616c 676f 7269 7468 6d20 746f 2077 6f72 algorithm to wor
000012c0: 6b3a 0a5c 6265 6769 6e7b 656e 756d 6572 k:.\begin{enumer
000012d0: 6174 657d 200a 095c 6974 656d 2041 6c6c ate} ..\item All
000012e0: 2041 5073 2068 6173 2074 6f20 7275 6e20 APs has to run
000012f0: 7468 6520 7361 6d65 2061 6c67 6f72 6974 the same algorit
00001300: 686d 0a09 5c69 7465 6d20 416c 6c20 4150 hm..\item All AP
00001310: 7320 6d75 7374 2072 756e 2074 6865 2061 s must run the a
00001320: 6c67 6f72 6974 686d 206f 6e20 7468 6520 lgorithm on the
00001330: 7361 6d65 2063 6f6e 6e65 6374 6564 2067 same connected g
00001340: 726f 7570 0a09 5c69 7465 6d20 4265 6361 roup..\item Beca
00001350: 7573 6520 6f66 2074 6865 2063 6f6d 706c use of the compl
00001360: 6578 6974 7920 6f66 2074 6865 2070 726f exity of the pro
00001370: 626c 656d 2074 6865 2061 6c67 6f72 7468 blem the algorth
00001380: 6d20 6d75 7374 2073 6f6c 7665 2c20 7468 m must solve, th
00001390: 6520 6e75 6d62 6572 206f 6620 4150 7320 e number of APs
000013a0: 696e 2074 6865 2063 6f6e 6e65 6374 6564 in the connected
000013b0: 2067 726f 7570 2063 616e 206e 6f74 2062 group can not b
000013c0: 6520 746f 6f20 6269 670a 5c65 6e64 7b65 e too big.\end{e
000013d0: 6e75 6d65 7261 7465 7d0a 0a50 6f69 6e74 numerate}..Point
000013e0: 2031 2069 7320 7472 6976 6961 6c20 746f 1 is trivial to
000013f0: 2073 6f6c 7665 206f 7220 6d69 7469 6761 solve or mitiga
00001400: 7465 2c20 6173 206f 6e6c 7920 4150 7320 te, as only APs
00001410: 7275 6e6e 696e 6720 7468 6520 616c 676f running the algo
00001420: 7269 7468 6d20 7769 6c6c 2061 6374 6976 rithm will activ
00001430: 656c 7920 7061 7274 6963 6970 6174 6520 ely participate
00001440: 696e 2074 6865 2063 6861 6e6e 656c 2073 in the channel s
00001450: 656c 6563 7469 6f6e 2e20 4120 7369 6d70 election. A simp
00001460: 6c65 2077 6179 2074 6f20 6d61 6b65 2073 le way to make s
00001470: 7572 6520 7468 6174 2074 6865 0a73 616d ure that the.sam
00001480: 6520 616c 676f 7269 7468 6d20 6973 2075 e algorithm is u
00001490: 7365 642c 2069 7320 6279 2068 6176 696e sed, is by havin
000014a0: 6720 6120 736f 6674 7761 7265 2076 6572 g a software ver
000014b0: 7369 6f6e 2074 6861 7420 6973 2063 6f6e sion that is con
000014c0: 7369 7374 656e 746c 7920 6368 6563 6b65 sistently checke
000014d0: 6420 7769 7468 2074 6865 206f 7468 6572 d with the other
000014e0: 2041 5073 2069 6e20 7468 6520 636f 6e6e APs in the conn
000014f0: 6563 7465 6420 6772 6f75 702e 0a0a 506f ected group...Po
00001500: 696e 7420 3220 616e 6420 706f 696e 7420 int 2 and point
00001510: 3320 6973 2077 696c 6c20 6265 2074 6865 3 is will be the
00001520: 206d 6169 6e20 666f 6375 7320 6f66 2074 main focus of t
00001530: 6865 2072 6573 7420 6f66 2074 6865 206d he rest of the m
00001540: 6173 7465 7220 7468 6573 6973 2c20 6173 aster thesis, as
00001550: 2074 6865 7365 2061 7265 206e 6f74 2073 these are not s
00001560: 6f20 6561 7369 6c79 2073 6f6c 7665 642e o easily solved.
00001570: 0a0a 5765 2063 616e 2064 6566 696e 6520 ..We can define
00001580: 6120 7769 7265 6c65 7373 2074 6f70 6f6c a wireless topol
00001590: 6f67 7920 6772 6170 6820 6173 2061 2073 ogy graph as a s
000015a0: 6574 206f 6620 7769 7265 6c65 7373 2041 et of wireless A
000015b0: 5073 2074 6861 7420 6172 6520 6772 6f75 Ps that are grou
000015c0: 7065 6420 746f 6765 7468 6572 2061 6e64 ped together and
000015d0: 2073 6861 7265 2069 6e66 6f72 6d61 7469 share informati
000015e0: 6f6e 2061 626f 7574 2074 6865 6972 206e on about their n
000015f0: 6569 6768 626f 7572 7320 616e 6420 696e eighbours and in
00001600: 7465 7266 6572 656e 6365 206c 6576 656c terference level
00001610: 732e 0a54 6869 7320 7365 7420 6973 2077 s..This set is w
00001620: 6861 7420 7769 6c6c 206e 6f77 206f 6e20 hat will now on
00001630: 6265 2072 6566 6572 7265 6420 746f 2061 be referred to a
00001640: 7320 6120 5c74 6578 7469 747b 636f 6e6e s a \textit{conn
00001650: 6563 7465 6420 6772 6f75 702e 7d20 416c ected group.} Al
00001660: 6c20 6d65 6d62 6572 7320 6f66 2074 6865 l members of the
00001670: 2063 6f6e 6e65 6374 6564 2067 726f 7570 connected group
00001680: 2077 696c 6c20 6265 2063 6f6e 7369 6465 will be conside
00001690: 7265 6420 7768 656e 2072 756e 6e69 6e67 red when running
000016a0: 2074 6865 2063 6861 6e6e 656c 2061 7373 the channel ass
000016b0: 6967 6e6d 656e 7420 616c 676f 7269 7468 ignment algorith
000016c0: 6d2e 0a46 6f72 2074 6865 2063 6f6e 6e65 m..For the conne
000016d0: 6374 6564 2067 726f 7570 2074 6f20 6861 cted group to ha
000016e0: 7665 2061 6e20 6163 7475 616c 2069 6d70 ve an actual imp
000016f0: 6163 7420 6f6e 2074 6865 2071 7561 6c69 act on the quali
00001700: 7479 206f 6620 6120 6e65 7477 6f72 6b20 ty of a network
00001710: 636f 6e6e 6563 7469 6f6e 2c20 6974 2068 connection, it h
00001720: 6173 2074 6f20 636f 6e73 6973 7420 6f66 as to consist of
00001730: 206e 6f64 6573 2074 6861 7420 6e6f 726d nodes that norm
00001740: 616c 6c79 2064 6973 7475 7262 7320 6561 ally disturbs ea
00001750: 6368 206f 7468 6572 2073 7562 7374 616e ch other substan
00001760: 7469 616c 6c79 2e0a 0a41 6e20 6964 6561 tially...An idea
00001770: 6c20 6578 616d 706c 6520 6f66 2061 2063 l example of a c
00001780: 6f6e 6e65 6374 6564 2067 726f 7570 2069 onnected group i
00001790: 7320 616e 2061 7061 7274 6d65 6e74 2062 s an apartment b
000017a0: 7569 6c69 6469 6e67 2e20 5468 6520 6368 uiliding. The ch
000017b0: 616e 6e65 6c20 616c 6c6f 6361 7469 6f6e annel allocation
000017c0: 2070 726f 746f 636f 6c20 6c65 7473 2041 protocol lets A
000017d0: 5073 2073 6861 7265 2069 6e66 6f72 6d61 Ps share informa
000017e0: 7469 6f6e 2061 626f 7574 2077 686f 2d64 tion about who-d
000017f0: 6973 7475 7262 732d 7768 6f20 7468 6520 isturbs-who the
00001800: 6d6f 7374 2069 6e20 7468 6520 6275 696c most in the buil
00001810: 6469 6e67 2e0a 5468 656e 2065 6163 6820 ding..Then each
00001820: 4150 2063 616e 2072 756e 2074 6865 2063 AP can run the c
00001830: 6861 6e6e 656c 2061 6c6c 6f63 6174 696f hannel allocatio
00001840: 6e20 616c 676f 7269 7468 6d2e 2042 6563 n algorithm. Bec
00001850: 6175 7365 2074 6865 7920 7275 6e20 6974 ause they run it
00001860: 206f 6e20 7468 6520 7361 6d65 2067 7261 on the same gra
00001870: 7068 2c20 6576 6572 7920 4150 2077 696c ph, every AP wil
00001880: 6c20 6669 6e64 2074 6865 2073 616d 6520 l find the same
00001890: 6f70 7469 6d61 6c20 6368 616e 6e65 6c20 optimal channel
000018a0: 6469 7374 7269 6275 7469 6f6e 2074 6872 distribution thr
000018b0: 6f75 6768 6f75 7420 7468 6520 6275 696c oughout the buil
000018c0: 6469 6e67 2c0a 616e 6420 7468 656e 2073 ding,.and then s
000018d0: 7769 7463 6820 746f 2074 6865 2063 6f72 witch to the cor
000018e0: 7265 6374 2063 6861 6e6e 656c 2e20 0a0a rect channel. ..
000018f0: 4576 656e 2074 686f 7567 6820 616e 2061 Even though an a
00001900: 7061 7274 6d65 6e74 2062 7569 6c64 696e partment buildin
00001910: 6720 6973 206d 6f73 7420 6c69 6b65 6c79 g is most likely
00001920: 2061 6e20 6f70 7469 6d61 6c20 6465 6c69 an optimal deli
00001930: 6d69 6e61 7469 6f6e 206f 6620 6120 636f mination of a co
00001940: 6e6e 6563 7465 6420 6772 6f75 702c 2069 nnected group, i
00001950: 6e20 7265 616c 6974 7920 6372 6561 7469 n reality creati
00001960: 6e67 2073 7563 6820 6120 6772 6f75 7020 ng such a group
00001970: 6973 2061 2062 6967 6765 7220 6368 616c is a bigger chal
00001980: 6c65 6e67 652e 2041 7320 7468 6520 7768 lenge. As the wh
00001990: 6f6c 6520 6368 616e 6e65 6c20 616c 6c6f ole channel allo
000019a0: 6361 7469 6f6e 0a70 726f 746f 636f 6c20 cation.protocol
000019b0: 6973 2062 6173 6564 206f 6e20 6465 6365 is based on dece
000019c0: 6e74 7261 6c69 7a65 6420 7065 6572 2d74 ntralized peer-t
000019d0: 6f2d 7065 6572 2074 6563 686e 6f6c 6f67 o-peer technolog
000019e0: 792c 2061 6e64 206e 6f20 6365 6e74 7261 y, and no centra
000019f0: 6c69 7a65 6420 7365 7276 6572 2077 6974 lized server wit
00001a00: 6820 6163 6365 7373 2074 6f20 6465 6d6f h access to demo
00001a10: 6772 6170 6869 6361 6c20 616e 6420 6765 graphical and ge
00001a20: 6f67 7261 7068 6963 616c 2064 6976 6973 ographical divis
00001a30: 696f 6e73 2065 7869 7374 732c 2074 6865 ions exists, the
00001a40: 2070 726f 746f 636f 6c20 7769 6c6c 0a68 protocol will.h
00001a50: 6176 6520 746f 2064 6973 636f 7665 7220 ave to discover
00001a60: 7375 6974 6162 6c65 2063 6f6e 6e65 6374 suitable connect
00001a70: 6564 2067 726f 7570 7320 6f6e 2069 7473 ed groups on its
00001a80: 206f 776e 2e20 4d6f 7265 6f76 6572 2c20 own. Moreover,
00001a90: 7768 656e 2074 6865 2067 726f 7570 2069 when the group i
00001aa0: 7320 6372 6561 7465 6420 7468 6520 7072 s created the pr
00001ab0: 6f74 6f63 6f6c 2077 696c 6c20 6861 7665 otocol will have
00001ac0: 2074 6f20 7265 706c 6963 6174 6520 6461 to replicate da
00001ad0: 7461 2073 6f20 7468 6174 0a61 6c6c 2070 ta so that.all p
00001ae0: 6172 7469 6369 7061 6e74 7320 6f66 2074 articipants of t
00001af0: 6865 2067 726f 7570 2068 6173 2061 6c6c he group has all
00001b00: 2074 6865 2064 6174 6120 7265 7175 6972 the data requir
00001b10: 6564 2074 6f20 7065 7266 6f72 6d20 6368 ed to perform ch
00001b20: 616e 6e65 6c20 616c 6c6f 6361 7469 6f6e annel allocation
00001b30: 2e20 4974 2077 696c 6c20 616c 736f 206e . It will also n
00001b40: 6565 6420 6120 7761 7920 746f 206d 616b eed a way to mak
00001b50: 6520 7375 7265 2074 6861 7420 7468 6520 e sure that the
00001b60: 696d 6167 6520 6f66 2074 6865 2063 7572 image of the cur
00001b70: 7265 6e74 2067 726f 7570 0a69 7320 636f rent group.is co
00001b80: 6e73 6973 7465 6e74 2077 6974 6869 6e20 nsistent within
00001b90: 616c 6c20 4150 7320 696e 2074 6865 2063 all APs in the c
00001ba0: 6f6e 6e65 6374 6564 2067 726f 7570 2e20 onnected group.
00001bb0: 0a0a 5c63 6861 7074 6572 7b42 6163 6b67 ..\chapter{Backg
00001bc0: 726f 756e 647d 0a57 6520 7769 6c6c 2062 round}.We will b
00001bd0: 7269 6566 6c79 2069 6e74 726f 6475 6365 riefly introduce
00001be0: 2074 6865 2072 656c 6576 616e 7420 6173 the relevant as
00001bf0: 7065 6374 7320 6f66 2077 6972 656c 6573 pects of wireles
00001c00: 7320 7465 6368 6e6f 6c6f 6779 2061 6e64 s technology and
00001c10: 2061 2073 656c 6563 7469 6f6e 206f 6620 a selection of
00001c20: 696d 706f 7274 616e 740a 636f 6e63 6570 important.concep
00001c30: 7473 2066 726f 6d20 7468 6520 3830 322e ts from the 802.
00001c40: 3131 2073 7461 6e64 6172 642c 2062 6f74 11 standard, bot
00001c50: 6820 6f6e 2074 6865 206c 696e 6b20 616e h on the link an
00001c60: 6420 7068 7973 6963 616c 206c 6179 6572 d physical layer
00001c70: 2e0a 0a5c 7365 6374 696f 6e7b 5769 7265 ...\section{Wire
00001c80: 6c65 7373 2074 6563 686e 6f6c 6f67 797d less technology}
00001c90: 0a54 6865 2062 6173 6963 2067 6f61 6c20 .The basic goal
00001ca0: 6f66 2077 6972 656c 6573 7320 7465 6368 of wireless tech
00001cb0: 6e6f 6c6f 6779 2069 7320 746f 2074 7261 nology is to tra
00001cc0: 6e73 6d69 7420 6120 7369 676e 616c 2066 nsmit a signal f
00001cd0: 726f 6d20 7261 6469 6f20 4120 746f 2072 rom radio A to r
00001ce0: 6164 696f 2042 2077 6974 686f 7574 2064 adio B without d
00001cf0: 6174 616c 6f73 732c 2062 7574 200a 7468 ataloss, but .th
00001d00: 6572 6520 6172 6520 736f 6d65 2063 6861 ere are some cha
00001d10: 6c6c 656e 6765 7320 7769 7468 2077 6972 llenges with wir
00001d20: 656c 6573 7320 7465 6368 6e6f 6c6f 6769 eless technologi
00001d30: 6573 2074 6861 7420 6172 6520 6861 7264 es that are hard
00001d40: 6572 2074 6f20 6f76 6572 636f 6d65 2074 er to overcome t
00001d50: 6861 6e20 696e 2045 7468 6572 6e65 7420 han in Ethernet
00001d60: 6f72 2077 6972 6564 2074 7261 6e6d 6973 or wired tranmis
00001d70: 7369 6f6e 732e 0a27 270a 5468 6520 6669 sions..''.The fi
00001d80: 7273 7420 7374 6570 2074 6f20 6163 6869 rst step to achi
00001d90: 6576 6520 7468 6973 2069 7320 6d61 6b69 eve this is maki
00001da0: 6e67 2073 7572 6520 7261 6469 6f20 4220 ng sure radio B
00001db0: 6861 7320 746f 2062 6520 7769 7468 696e has to be within
00001dc0: 2072 6164 696f 2041 2773 2074 7261 6e73 radio A's trans
00001dd0: 6d69 7420 7261 6e67 652e 2054 6865 0a74 mit range. The.t
00001de0: 7261 6e73 6d69 7420 7261 6e67 6520 6973 ransmit range is
00001df0: 2064 6563 6964 6564 2062 7920 7468 6520 decided by the
00001e00: 706f 7765 7220 7768 6963 6820 7468 6520 power which the
00001e10: 7369 676e 616c 2069 7320 7472 616e 736d signal is transm
00001e20: 6974 7465 6420 6174 2c20 7468 6520 616e itted at, the an
00001e30: 7465 6e6e 6120 6761 696e 2c20 616e 6420 tenna gain, and
00001e40: 7468 6520 7375 7272 6f75 6e64 696e 6720 the surrounding
00001e50: 0a65 6e76 6972 6f6e 6d65 6e74 2e20 4966 .environment. If
00001e60: 2074 6865 7265 2061 7265 2061 206c 6f74 there are a lot
00001e70: 206f 6620 736f 6c69 6420 6f62 7374 6163 of solid obstac
00001e80: 6c65 7320 6c69 6b65 2077 616c 6c73 2061 les like walls a
00001e90: 6e64 2063 6569 6c69 6e67 7320 7468 6520 nd ceilings the
00001ea0: 7369 676e 616c 2077 696c 6c20 6861 7665 signal will have
00001eb0: 2061 2076 6572 7920 636f 6d70 726f 6d69 a very compromi
00001ec0: 7365 6420 7261 6e67 652e 0a45 7665 6e20 sed range..Even
00001ed0: 6966 2074 6865 2073 7572 726f 756e 6469 if the surroundi
00001ee0: 6e67 2065 6e76 6972 6f6e 6d65 6e74 2069 ng environment i
00001ef0: 7320 6d6f 7374 6c79 206f 7065 6e20 7370 s mostly open sp
00001f00: 6163 652c 2074 6865 2077 6972 656c 6573 ace, the wireles
00001f10: 7320 7369 676e 616c 2062 6563 6f6d 6573 s signal becomes
00001f20: 2073 7562 6a65 6374 206f 6620 6174 7465 subject of atte
00001f30: 6e75 6174 696f 6e2c 0a77 6869 6368 2069 nuation,.which i
00001f40: 7320 6120 7068 7973 6963 616c 2070 726f s a physical pro
00001f50: 7065 7274 7920 6f66 2065 6c65 6374 726f perty of electro
00001f60: 6d61 676e 6963 2077 6176 6573 2074 6861 magnic waves tha
00001f70: 7420 7765 616b 656e 7320 7468 6520 7369 t weakens the si
00001f80: 676e 616c 2074 6865 206c 6f6e 6765 7220 gnal the longer
00001f90: 6974 2068 6173 2074 7261 7665 6c6c 6564 it has travelled
00001fa0: 2074 6872 6f75 6768 2061 0a6d 6564 6975 through a.mediu
00001fb0: 6d2e 2057 6865 6e20 7472 6176 656c 6c69 m. When travelli
00001fc0: 6e67 2074 6872 6f75 6768 2061 6972 2074 ng through air t
00001fd0: 6869 7320 6973 2061 6c73 6f20 6361 6c6c his is also call
00001fe0: 6564 2066 7265 6520 7370 6163 6520 7061 ed free space pa
00001ff0: 7468 206c 6f73 732e 2041 7474 656e 7475 th loss. Attentu
00002000: 6174 696f 6e20 6c69 6d69 7473 0a74 6865 ation limits.the
00002010: 2074 7261 6e73 6d69 7420 7261 6e67 6520 transmit range
00002020: 6f66 2061 2072 6164 696f 2c20 616e 6420 of a radio, and
00002030: 746f 2074 7261 6e73 6d69 7420 6675 7274 to transmit furt
00002040: 6865 7220 6974 2068 6173 2074 6f20 696e her it has to in
00002050: 6372 6561 7365 2069 7473 2074 7261 6e73 crease its trans
00002060: 6d69 7373 696f 6e20 706f 7765 722e 0a0a mission power...
00002070: 436f 6c6c 6973 696f 6e73 2063 616e 2061 Collisions can a
00002080: 6c73 6f20 7072 6576 656e 7420 7468 6520 lso prevent the
00002090: 7369 676e 616c 2066 726f 6d20 6265 696e signal from bein
000020a0: 6720 7265 6365 6976 6564 2063 6f72 7265 g received corre
000020b0: 6374 6c79 2e0a 4966 2074 6865 7265 2061 ctly..If there a
000020c0: 7265 206f 7468 6572 206e 6f64 6573 206e re other nodes n
000020d0: 6561 7262 7920 7468 6174 2061 7265 2077 earby that are w
000020e0: 6974 6869 6e20 7261 6469 6f20 4227 7320 ithin radio B's
000020f0: 7365 6e73 696e 6720 7261 6e67 6520 7468 sensing range th
00002100: 6174 2073 656e 6473 2061 7420 7468 6520 at sends at the
00002110: 7361 6d65 2074 696d 6520 6173 2041 2c20 same time as A,
00002120: 7261 6469 6f20 4220 6578 7065 7269 656e radio B experien
00002130: 6365 730a 7261 6469 6f20 6672 6571 7565 ces.radio freque
00002140: 6e63 7920 696e 7465 7266 6572 656e 6365 ncy interference
00002150: 2c20 616e 6420 7468 7573 206d 6179 206e , and thus may n
00002160: 6f74 2062 6520 6162 6c65 2074 6f20 636f ot be able to co
00002170: 7272 6563 746c 7920 6465 636f 6465 2074 rrectly decode t
00002180: 6865 2073 6967 6e61 6c20 6f66 2041 2e20 he signal of A.
00002190: 496e 2038 3032 2e33 2045 7468 6572 6e65 In 802.3 Etherne
000021a0: 7420 7468 6973 0a69 7320 6772 6163 696f t this.is gracio
000021b0: 7573 6c79 2068 616e 646c 6564 2062 7920 usly handled by
000021c0: 636f 6c6c 6973 696f 6e20 6465 7465 6374 collision detect
000021d0: 696f 6e20 696e 2074 6865 2043 534d 412f ion in the CSMA/
000021e0: 4344 2070 726f 746f 636f 6c2c 0a62 7574 CD protocol,.but
000021f0: 2069 6e20 7769 7265 6c65 7373 2074 6563 in wireless tec
00002200: 686e 6f6c 6f67 7920 636f 6c6c 6973 696f hnology collisio
00002210: 6e20 6465 7465 6374 696f 6e20 7468 6973 n detection this
00002220: 206e 6f74 2070 6f73 7369 626c 6520 6265 not possible be
00002230: 6361 7573 6520 6f66 2074 6865 2068 6964 cause of the hid
00002240: 6465 6e20 7465 726d 696e 616c 2070 726f den terminal pro
00002250: 626c 656d 2e0a 0a5c 7375 6273 6563 7469 blem...\subsecti
00002260: 6f6e 7b54 6865 2068 6964 6465 6e20 7465 on{The hidden te
00002270: 726d 696e 616c 2070 726f 626c 656d 7d0a rminal problem}.
00002280: 5468 6520 6869 6464 656e 2074 6572 6d69 The hidden termi
00002290: 6e61 6c20 7072 6f62 6c65 6d20 6973 206f nal problem is o
000022a0: 6e65 206f 6620 7468 6520 6d61 6a6f 7220 ne of the major
000022b0: 6368 616c 6c65 6e67 6573 2066 6f72 2077 challenges for w
000022c0: 6972 656c 6573 7320 7465 6368 6e6f 6c6f ireless technolo
000022d0: 6769 6573 2e20 496e 2063 6f6e 7472 6173 gies. In contras
000022e0: 7420 746f 2065 7468 6572 6e65 742c 2061 t to ethernet, a
000022f0: 2073 656e 6465 7220 6361 6e20 6e6f 7420 sender can not
00002300: 0a73 696d 706c 7920 6c69 7374 656e 2066 .simply listen f
00002310: 6f72 2063 6f6c 6c69 7369 6f6e 7320 6f6e or collisions on
00002320: 2074 6865 2063 6861 6e6e 656c 2077 6869 the channel whi
00002330: 6c65 2073 656e 6469 6e67 2074 6f20 6775 le sending to gu
00002340: 6172 656e 7465 6520 7468 6174 2074 6865 arentee that the
00002350: 2072 6563 6569 7665 7220 676f 7420 7468 receiver got th
00002360: 6520 6d65 7373 6167 6520 7072 6f70 6572 e message proper
00002370: 6c79 2e0a 5468 6520 7065 7270 6174 7261 ly..The perpatra
00002380: 746f 7220 6973 2074 6865 2068 6964 6465 tor is the hidde
00002390: 6e20 7465 726d 696e 616c 2e20 5768 656e n terminal. When
000023a0: 206e 6f64 6520 4120 7472 616e 736d 6974 node A transmit
000023b0: 7320 6120 6d65 7373 6167 6520 746f 206e s a message to n
000023c0: 6f64 6520 422c 2069 7420 6d61 7920 6e6f ode B, it may no
000023d0: 7420 6265 2061 626c 6520 746f 2073 656e t be able to sen
000023e0: 7365 2077 6861 7420 6973 2067 6f69 6e67 se what is going
000023f0: 206f 6e0a 6f6e 2074 6865 206f 7070 6f73 on.on the oppos
00002400: 6974 6520 7369 6465 206f 6620 6e6f 6465 ite side of node
00002410: 2042 2e20 4966 2061 206e 6f64 6520 4320 B. If a node C
00002420: 7472 616e 736d 6974 7320 6174 2074 6865 transmits at the
00002430: 2073 616d 6520 7469 6d65 2c20 7468 6973 same time, this
00002440: 2073 6967 6e61 6c20 6d61 7920 6e6f 7420 signal may not
00002450: 656e 7465 7220 6e6f 6465 2041 2773 2073 enter node A's s
00002460: 656e 7369 6e67 2072 616e 6765 2c20 616e ensing range, an
00002470: 640a 6865 6e63 6520 676f 2075 6e64 6574 d.hence go undet
00002480: 6563 7465 6420 6279 2c20 6576 656e 2074 ected by, even t
00002490: 686f 7567 6820 6120 636f 6c6c 6973 696f hough a collisio
000024a0: 6e20 6861 7320 6861 7070 656e 6564 206e n has happened n
000024b0: 6561 7220 6e6f 6465 2042 2e20 5468 6973 ear node B. This
000024c0: 2069 7320 696c 6c75 7374 7261 7465 6420 is illustrated
000024d0: 696e 2066 6967 7572 6520 5c72 6566 7b66 in figure \ref{f
000024e0: 6967 3a68 6964 6465 6e74 6572 6d69 6e61 ig:hiddentermina
000024f0: 6c7d 2077 6865 7265 0a62 6f74 6820 4120 l} where.both A
00002500: 616e 6420 4320 6861 7320 756e 6b6e 6f77 and C has unknow
00002510: 696e 676c 7920 7365 6e74 206d 6573 7361 ingly sent messa
00002520: 6765 7320 6174 2074 6865 2073 616d 6520 ges at the same
00002530: 7469 6d65 2c20 616e 6420 4220 6861 7320 time, and B has
00002540: 6e6f 7420 6265 656e 2061 626c 6520 746f not been able to
00002550: 2064 6563 6f64 6520 616e 7920 6d65 7373 decode any mess
00002560: 6167 6573 2062 6563 6175 7365 206f 6620 ages because of
00002570: 7468 6520 636f 6c6c 6964 696e 6720 6d65 the colliding me
00002580: 7373 6167 6573 2e20 0a0a 5c62 6567 696e ssages. ..\begin
00002590: 7b66 6967 7572 657d 0a09 5c63 656e 7465 {figure}..\cente
000025a0: 720a 095c 696e 636c 7564 6567 7261 7068 r..\includegraph
000025b0: 6963 735b 7363 616c 653d 302e 335d 7b49 ics[scale=0.3]{I
000025c0: 6d61 6765 732f 4869 6464 656e 7465 726d mages/Hiddenterm
000025d0: 696e 616c 6669 6775 7265 2e6a 7067 7d0a inalfigure.jpg}.
000025e0: 095c 6361 7074 696f 6e7b 4120 616e 6420 .\caption{A and
000025f0: 4320 7365 6e64 696e 6720 746f 206e 6f64 C sending to nod
00002600: 6520 4220 756e 6b6e 6f77 696e 676c 7920 e B unknowingly
00002610: 6174 2074 6865 2073 616d 6520 7469 6d65 at the same time
00002620: 2c20 7265 7375 6c74 696e 6720 696e 2061 , resulting in a
00002630: 2063 6f6c 6c69 7369 6f6e 7d0a 095c 6c61 collision}..\la
00002640: 6265 6c7b 6669 673a 6869 6464 656e 7465 bel{fig:hiddente
00002650: 726d 696e 616c 7d0a 5c65 6e64 7b66 6967 rminal}.\end{fig
00002660: 7572 657d 0a0a 5c73 6563 7469 6f6e 7b49 ure}..\section{I
00002670: 4545 4520 3830 322e 3131 7d0a 0a5c 7375 EEE 802.11}..\su
00002680: 6273 6563 7469 6f6e 7b43 534d 412f 4341 bsection{CSMA/CA
00002690: 206f 7665 7276 6965 777d 0a54 6865 2038 overview}.The 8
000026a0: 3032 2e31 3120 4d41 4320 6c61 7965 7220 02.11 MAC layer
000026b0: 696d 706c 656d 656e 7473 2074 6865 2043 implements the C
000026c0: 6172 7269 6572 2053 656e 7365 204d 756c arrier Sense Mul
000026d0: 7469 706c 6520 4163 6365 7373 202f 2043 tiple Access / C
000026e0: 6f6c 6c69 7369 6f6e 2041 766f 6964 616e ollision Avoidan
000026f0: 6365 2028 4353 4d41 2f43 4129 2070 726f ce (CSMA/CA) pro
00002700: 746f 636f 6c20 746f 2063 6f6e 7472 6f6c tocol to control
00002710: 2061 6363 6573 7320 746f 2074 6865 206d access to the m
00002720: 6564 6975 6d2e 0a54 6865 2043 534d 412f edium..The CSMA/
00002730: 4341 2070 726f 746f 636f 6c20 6973 2064 CA protocol is d
00002740: 6573 6967 6e65 6420 746f 206f 7065 7261 esigned to opera
00002750: 7465 2069 6e20 616e 2065 6e74 6972 656c te in an entirel
00002760: 7920 6469 7374 7269 6275 7465 6420 6661 y distributed fa
00002770: 7368 696f 6e2c 2077 6865 7265 2061 6c6c shion, where all
00002780: 2073 7461 7469 6f6e 7320 636f 6e6e 6563 stations connec
00002790: 7465 6420 746f 2074 6865 2073 616d 6520 ted to the same
000027a0: 4253 5320 206f 7065 7261 7465 206f 6e0a BSS operate on.
000027b0: 7468 6520 7361 6d65 2066 7265 7175 656e the same frequen
000027c0: 6379 2077 6974 686f 7574 2063 6f6f 7264 cy without coord
000027d0: 696e 6174 6564 2074 696d 6573 6c6f 7473 inated timeslots
000027e0: 2e20 4173 2073 7567 6765 7374 6564 2062 . As suggested b
000027f0: 7920 7468 6520 6e61 6d65 206f 6620 7468 y the name of th
00002800: 6520 7072 6f74 6f63 6f6c 2c20 7468 6572 e protocol, ther
00002810: 6520 6172 6520 7477 6f20 6261 7369 6320 e are two basic
00002820: 6f70 6572 6174 696f 6e73 2069 6e20 7468 operations in th
00002830: 6520 4353 4d41 2f43 4120 7072 6f74 6f63 e CSMA/CA protoc
00002840: 6f6c 3a0a 5c74 6578 7462 667b 4361 7272 ol:.\textbf{Carr
00002850: 6965 7220 5365 6e73 696e 6720 2843 5329 ier Sensing (CS)
00002860: 7d20 616e 6420 5c74 6578 7462 667b 436f } and \textbf{Co
00002870: 6c6c 6973 696f 6e20 4176 6f69 6461 6e63 llision Avoidanc
00002880: 6520 2843 4129 7d2e 200a 0a5c 7375 6273 e (CA)}. ..\subs
00002890: 7562 7365 6374 696f 6e7b 4361 7272 6965 ubsection{Carrie
000028a0: 7220 5365 6e73 657d 0a49 6e20 3830 322e r Sense}.In 802.
000028b0: 3131 2c20 6361 7272 6965 7220 7365 6e73 11, carrier sens
000028c0: 696e 6720 2843 5329 2069 7320 646f 6e65 ing (CS) is done
000028d0: 2069 6e20 7477 6f20 7761 7973 0a5c 6265 in two ways.\be
000028e0: 6769 6e7b 6974 656d 697a 657d 0a09 5c69 gin{itemize}..\i
000028f0: 7465 6d20 5c74 6578 7462 667b 5068 7973 tem \textbf{Phys
00002900: 6963 616c 2063 6172 7269 6572 2073 656e ical carrier sen
00002910: 7369 6e67 7d20 6861 6e64 6c65 6420 6279 sing} handled by
00002920: 2074 6865 2070 6879 7369 6361 6c20 6c61 the physical la
00002930: 7965 7220 2850 4859 2920 6173 2043 6c65 yer (PHY) as Cle
00002940: 6172 2043 6861 6e6e 656c 2041 7373 6573 ar Channel Asses
00002950: 736d 656e 7420 2843 4341 292c 2077 6869 sment (CCA), whi
00002960: 6368 2077 6520 7769 6c6c 2074 616c 6b20 ch we will talk
00002970: 6162 6f75 7420 696e 2074 6865 2050 4859 about in the PHY
00002980: 2073 7562 7365 6374 696f 6e2e 0a09 5c69 subsection...\i
00002990: 7465 6d20 5c74 6578 7462 667b 5669 7274 tem \textbf{Virt
000029a0: 7561 6c20 6361 7272 6965 7220 7365 6e73 ual carrier sens
000029b0: 696e 677d 2069 7320 6120 4d41 4320 6c61 ing} is a MAC la
000029c0: 7965 7220 6d65 6368 616e 6973 6d20 696e yer mechanism in
000029d0: 2070 6c61 6365 2074 6f20 6c69 6d69 7420 place to limit
000029e0: 7468 6520 6e75 6d62 6572 206f 6620 7469 the number of ti
000029f0: 6d65 730a 0909 6120 6e6f 6465 2068 6173 mes...a node has
00002a00: 2074 6f20 6368 6563 6b20 7468 6520 7068 to check the ph
00002a10: 7973 6963 616c 2072 6164 696f 2e20 5768 ysical radio. Wh
00002a20: 656e 2061 2076 616c 6964 2038 3032 2e31 en a valid 802.1
00002a30: 3120 6672 616d 6520 6973 2064 6563 6f64 1 frame is decod
00002a40: 6564 2066 6f72 2061 206c 6973 7465 6e69 ed for a listeni
00002a50: 6e67 206e 6f64 652c 2069 7420 6361 6e20 ng node, it can
00002a60: 7265 6164 2074 6865 2064 7572 6174 696f read the duratio
00002a70: 6e20 6f66 0a09 0974 6865 2074 7261 6e73 n of...the trans
00002a80: 6d69 7373 696f 6e20 6672 6f6d 2074 6865 mission from the
00002a90: 204d 4143 2068 6561 6465 722e 2054 6865 MAC header. The
00002aa0: 2066 7261 6d65 2077 6974 6820 6120 6475 frame with a du
00002ab0: 7261 7469 6f6e 2069 7320 6361 6c6c 6564 ration is called
00002ac0: 2061 204e 6574 776f 726b 2041 6c6c 6f63 a Network Alloc
00002ad0: 6174 696f 6e20 5665 6374 6f72 2028 4e41 ation Vector (NA
00002ae0: 5629 2e20 5768 656e 2061 204e 4156 2069 V). When a NAV i
00002af0: 7320 7265 6365 6976 6564 200a 0909 7468 s received ...th
00002b00: 6520 6368 616e 6e65 6c20 6973 206d 6172 e channel is mar
00002b10: 6b65 6420 6173 2062 7573 7920 616e 6420 ked as busy and
00002b20: 7468 6520 6e6f 6465 2077 696c 6c20 6261 the node will ba
00002b30: 636b 206f 6666 2066 6f72 2074 6865 2064 ck off for the d
00002b40: 7572 6174 696f 6e20 6f66 2074 6865 204e uration of the N
00002b50: 4156 2e20 0a5c 656e 647b 6974 656d 697a AV. .\end{itemiz
00002b60: 657d 200a 0a0a 5c73 7562 7375 6273 6563 e} ...\subsubsec
00002b70: 7469 6f6e 7b43 6f6c 6c69 7369 6f6e 2041 tion{Collision A
00002b80: 766f 6964 616e 6365 7d0a 4353 4d41 2f43 voidance}.CSMA/C
00002b90: 4120 6174 7465 6d70 7473 2074 6f20 6176 A attempts to av
00002ba0: 6f69 6420 636f 6c6c 6973 696f 6e73 2069 oid collisions i
00002bb0: 6e20 6120 6e65 7477 6f72 6b20 6c61 796f n a network layo
00002bc0: 7574 2074 6861 7420 696e 636c 7564 6573 ut that includes
00002bd0: 2068 6964 6465 6e20 7465 726d 696e 616c hidden terminal
00002be0: 732e 205c 7465 7874 6266 7b52 6571 7565 s. \textbf{Reque
00002bf0: 7374 2054 6f20 5365 6e64 2f43 6c65 6172 st To Send/Clear
00002c00: 2054 6f20 5365 6e64 7d20 2852 5453 2f43 To Send} (RTS/C
00002c10: 5453 290a 6973 2074 6865 2066 756e 6374 TS).is the funct
00002c20: 696f 6e20 7468 6174 2061 6c6c 6f77 7320 ion that allows
00002c30: 4353 4d41 2f43 4120 746f 2073 6f6d 6520 CSMA/CA to some
00002c40: 6465 6772 6565 2061 766f 6964 2074 6865 degree avoid the
00002c50: 2068 6964 6465 6e20 7465 726d 696e 616c hidden terminal
00002c60: 2070 726f 626c 656d 2e20 4279 206c 6574 problem. By let
00002c70: 7469 6e67 2061 206e 6f64 6520 6669 7273 ting a node firs
00002c80: 7420 6173 6b20 7468 6520 7265 6365 6976 t ask the receiv
00002c90: 6572 2069 6620 6974 2069 730a 6176 6169 er if it is.avai
00002ca0: 6c61 626c 6520 666f 7220 7472 616e 736d lable for transm
00002cb0: 6973 7369 6f6e 2028 5254 5329 2c20 6974 ission (RTS), it
00002cc0: 2070 7265 7665 6e74 7320 7468 6520 6e6f prevents the no
00002cd0: 6465 2066 726f 6d20 7365 6e64 696e 6720 de from sending
00002ce0: 7468 6520 7061 796c 6f61 6420 6672 616d the payload fram
00002cf0: 6520 756e 6c65 7373 2069 7420 7265 6365 e unless it rece
00002d00: 6976 6573 2043 6c65 6172 2054 6f20 5365 ives Clear To Se
00002d10: 6e64 2028 4354 5329 2066 7261 6d65 2066 nd (CTS) frame f
00002d20: 726f 6d20 7468 6520 7265 6365 6976 6572 rom the receiver
00002d30: 2066 6972 7374 2e20 0a09 0a5c 7375 6273 first. ...\subs
00002d40: 6563 7469 6f6e 7b44 6973 7472 6962 7574 ection{Distribut
00002d50: 6564 2043 6f6f 7264 696e 6174 696f 6e20 ed Coordination
00002d60: 4675 6e63 7469 6f6e 7d0a 5c62 6567 696e Function}.\begin
00002d70: 7b69 7465 6d69 7a65 7d0a 095c 6974 656d {itemize}..\item
00002d80: 205c 7465 7874 6266 7b49 6e74 6572 6672 \textbf{Interfr
00002d90: 616d 6520 7370 6163 696e 677d 2028 4946 ame spacing} (IF
00002da0: 5329 2069 7320 7468 6520 616d 6f75 6e74 S) is the amount
00002db0: 206f 6620 7469 6d65 2074 6865 2063 6861 of time the cha
00002dc0: 6e6e 656c 2068 6173 2074 6f20 6265 2069 nnel has to be i
00002dd0: 646c 6520 6265 666f 7265 2061 2073 656e dle before a sen
00002de0: 6465 7220 6361 6e20 636f 6d70 6574 6520 der can compete
00002df0: 666f 7220 6368 616e 6e65 6c20 6163 6365 for channel acce
00002e00: 7373 2e20 0a09 0954 6f20 6769 7665 2070 ss. ...To give p
00002e10: 7269 6f72 6974 7920 746f 2063 6572 7461 riority to certa
00002e20: 696e 2066 7261 6d65 2074 7970 6573 2c20 in frame types,
00002e30: 6469 6666 6572 656e 7420 7479 7065 7320 different types
00002e40: 6f66 2066 7261 6d65 7320 6361 6e20 6861 of frames can ha
00002e50: 7665 2064 6966 6665 7265 6e74 2074 7970 ve different typ
00002e60: 6573 206f 6620 696e 7465 7266 7261 6d65 es of interframe
00002e70: 2073 7061 6369 6e67 2e20 5468 6520 7479 spacing. The ty
00002e80: 7065 206f 6620 4946 5320 6973 2075 7375 pe of IFS is usu
00002e90: 616c 6c79 200a 0909 7072 6566 6978 6564 ally ...prefixed
00002ea0: 2077 6974 6820 7468 6520 6c65 7474 6572 with the letter
00002eb0: 206f 6620 7468 6520 6672 616d 6520 7479 of the frame ty
00002ec0: 7065 2e20 4f72 6761 6e69 7a65 6420 6279 pe. Organized by
00002ed0: 2072 656c 6174 6976 6520 696e 7465 7276 relative interv
00002ee0: 616c 206c 656e 6774 682c 2074 6865 2064 al length, the d
00002ef0: 6966 6665 7265 6e74 7320 4946 5320 6172 ifferents IFS ar
00002f00: 653a 0a09 095c 6265 6769 6e7b 6974 656d e:...\begin{item
00002f10: 697a 657d 200a 0909 095c 6974 656d 2053 ize} ....\item S
00002f20: 686f 7274 2049 4653 2028 5349 4653 292c hort IFS (SIFS),
00002f30: 2062 6566 6f72 6520 4143 4b2c 2052 5453 before ACK, RTS
00002f40: 2c20 4354 532e 2020 0a09 0909 5c69 7465 , CTS. ....\ite
00002f50: 6d20 4443 4620 4d6f 6465 2049 4653 2028 m DCF Mode IFS (
00002f60: 5049 4653 292c 2062 6566 6f72 6520 5254 PIFS), before RT
00002f70: 5320 6672 616d 6573 2028 6f72 2044 4346 S frames (or DCF
00002f80: 2064 6174 6120 6672 616d 6573 2069 6620 data frames if
00002f90: 5254 532f 4354 5320 6973 2064 6973 6162 RTS/CTS is disab
00002fa0: 6c65 6429 0a0a 0909 5c65 6e64 7b69 7465 led)....\end{ite
00002fb0: 6d69 7a65 7d0a 095c 6974 656d 205c 7465 mize}..\item \te
00002fc0: 7874 6266 7b45 7870 6f6e 656e 7469 616c xtbf{Exponential
00002fd0: 2062 6163 6b6f 6666 7d20 6973 2077 6861 backoff} is wha
00002fe0: 7420 7072 6576 656e 7473 2074 776f 2063 t prevents two c
00002ff0: 6f6d 7065 7469 6e67 206e 6f64 6573 2066 ompeting nodes f
00003000: 726f 6d20 7365 6e64 696e 6720 6174 2074 rom sending at t
00003010: 6865 2073 616d 6520 7469 6d65 2e20 5768 he same time. Wh
00003020: 656e 2074 6865 2063 6861 6e6e 656c 2069 en the channel i
00003030: 7320 636c 6561 720a 0909 666f 7220 4449 s clear...for DI
00003040: 4653 2074 696d 652c 2061 206e 6f64 6520 FS time, a node
00003050: 6861 7320 746f 2077 6169 7420 616e 6f74 has to wait anot
00003060: 6865 7220 2072 616e 646f 6d20 6e75 6d62 her random numb
00003070: 6572 206f 6620 6d69 6c6c 6973 6563 6f6e er of millisecon
00003080: 6473 2062 6566 6f72 6520 7472 616e 736d ds before transm
00003090: 6974 7469 6e67 2e20 5468 6973 2069 7320 itting. This is
000030a0: 6361 6c6c 6564 2062 6163 6b6f 6666 2e0a called backoff..
000030b0: 0909 5468 6520 616d 6f75 6e74 206f 6620 ..The amount of
000030c0: 6261 636b 6f66 6620 6973 2072 616e 646f backoff is rando
000030d0: 6d6c 7920 6368 6f73 656e 2066 726f 6d20 mly chosen from
000030e0: 6120 636f 6e74 656e 7469 6f6e 2077 696e a contention win
000030f0: 646f 7720 2843 5729 2e20 5468 6520 636f dow (CW). The co
00003100: 6e74 656e 7469 6f6e 2077 696e 646f 7720 ntention window
00003110: 6861 7320 6120 6c6f 7720 7374 6172 7420 has a low start
00003120: 7369 7a65 2c0a 0909 6361 6c6c 6564 2024 size,...called $
00003130: 4357 5f7b 5c74 6578 747b 6d69 6e7d 7d24 CW_{\text{min}}$
00003140: 2e20 4120 6e6f 6465 2064 7261 7773 2061 . A node draws a
00003150: 2062 6163 6b6f 6666 2074 696d 6520 696e backoff time in
00003160: 2074 6865 2072 616e 6765 2024 2830 2c20 the range $(0,
00003170: 325e 6e2a 4357 5f7b 5c74 6578 747b 6d69 2^n*CW_{\text{mi
00003180: 6e7d 7d29 242c 2077 6865 7265 2024 6e24 n}})$, where $n$
00003190: 2069 7320 7468 6520 6e75 6d62 6572 200a is the number .
000031a0: 0909 6f66 2074 696d 6573 2074 6865 2074 ..of times the t
000031b0: 7261 6e73 6d69 7373 696f 6e20 6861 7320 ransmission has
000031c0: 6661 696c 6564 2c20 6265 6769 6e6e 696e failed, beginnin
000031d0: 6720 6174 2024 6e3d 3024 2e0a 5c65 6e64 g at $n=0$..\end
000031e0: 7b69 7465 6d69 7a65 7d0a 0a0a 0a0a 5c73 {itemize}.....\s
000031f0: 7562 7365 6374 696f 6e7b 5048 5920 4c61 ubsection{PHY La
00003200: 7965 727d 0a0a 5c73 7562 7375 6273 6563 yer}..\subsubsec
00003210: 7469 6f6e 7b43 6c65 6172 2043 6861 6e6e tion{Clear Chann
00003220: 656c 2041 7373 6573 736d 656e 747d 0a54 el Assessment}.T
00003230: 6865 2070 7572 706f 7365 206f 6620 636c he purpose of cl
00003240: 6561 7220 6368 616e 6e65 6c20 6173 7365 ear channel asse
00003250: 7373 6d65 6e74 2069 7320 746f 2070 726f ssment is to pro
00003260: 7669 6465 2069 6e66 6f72 6d61 7469 6f6e vide information
00003270: 2074 6f20 7468 6520 4d41 4320 6c61 7965 to the MAC laye
00003280: 7220 6966 2074 6865 2063 6172 7269 6572 r if the carrier
00003290: 2069 7320 6275 7379 206f 7220 6176 6169 is busy or avai
000032a0: 6c61 626c 652e 2054 6865 7265 0a61 7265 lable. There.are
000032b0: 2074 776f 2077 6179 7320 7468 6520 0a43 two ways the .C
000032c0: 4341 2d45 4420 2843 4341 2d45 6e65 7267 CA-ED (CCA-Energ
000032d0: 7920 4465 7465 6374 2920 6465 7465 6374 y Detect) detect
000032e0: 7320 7369 676e 616c 7320 7468 6174 2063 s signals that c
000032f0: 616e 206e 6f74 2062 6520 6465 636f 6465 an not be decode
00003300: 6420 6173 2061 2038 3031 2e31 3120 6672 d as a 801.11 fr
00003310: 616d 652c 2062 7574 2061 6374 7320 6173 ame, but acts as
00003320: 2061 2064 6973 7475 7262 696e 6720 7369 a disturbing si
00003330: 676e 616c 2e20 4966 2074 6865 2043 4341 gnal. If the CCA
00003340: 2d45 4420 7661 6c75 6520 0a65 7863 6565 -ED value .excee
00003350: 6473 2061 2074 6872 6573 686f 6c64 2c20 ds a threshold,
00003360: 666f 7220 696e 7374 616e 6365 2032 3020 for instance 20
00003370: 6442 2c20 7468 656e 2074 6865 2043 4341 dB, then the CCA
00003380: 2073 6861 6c6c 2062 6520 6865 6c64 2062 shall be held b
00003390: 7573 792e 200a 5468 6520 6f70 6572 6174 usy. .The operat
000033a0: 696f 6e20 6f66 2074 6865 2070 726f 746f ion of the proto
000033b0: 636f 6c20 6265 6769 6e73 2062 7920 636c col begins by cl
000033c0: 6561 7220 6368 616e 6e65 6c20 6173 7365 ear channel asse
000033d0: 7373 6d65 6e74 2028 4343 4129 2e20 546f ssment (CCA). To
000033e0: 2070 7265 7665 6e74 2063 6f6c 6c69 7369 prevent collisi
000033f0: 6f6e 732c 2061 6c6c 206e 6f64 6573 2074 ons, all nodes t
00003400: 6861 7420 7769 7368 6573 2074 6f20 7472 hat wishes to tr
00003410: 616e 736d 6974 2068 6173 2074 6f20 6368 ansmit has to ch
00003420: 6563 6b20 7768 6574 6865 7220 6f72 0a6e eck whether or.n
00003430: 6f74 2074 6865 7265 2069 7320 616c 7265 ot there is alre
00003440: 6164 7920 6120 7472 616e 736d 6973 7369 ady a transmissi
00003450: 6f6e 206f 6e20 7468 6520 6d65 6469 756d on on the medium
00003460: 2e20 5468 6973 2069 7320 646f 6e65 2062 . This is done b
00003470: 7920 6569 7468 6572 2070 6879 7369 6361 y either physica
00003480: 6c20 6f66 2076 6972 7475 616c 2063 6172 l of virtual car
00003490: 7269 6572 2073 656e 7369 6e67 2e20 5068 rier sensing. Ph
000034a0: 7973 6963 616c 2063 6172 7269 6572 2073 ysical carrier s
000034b0: 656e 7369 6e67 206d 6561 6e73 2063 6865 ensing means che
000034c0: 636b 696e 670a 7468 6520 7261 6469 6f20 cking.the radio
000034d0: 6966 2074 6865 7265 2069 7320 616c 7265 if there is alre
000034e0: 6164 7920 616e 7920 7472 616e 736d 6973 ady any transmis
000034f0: 7369 6f6e 7320 676f 696e 6720 6f6e 2c20 sions going on,
00003500: 616e 6420 6465 636f 6469 6e67 2074 6865 and decoding the
00003510: 2068 6561 6465 722e 0a0a 2d20 504c 4350 header...- PLCP
00003520: 0a2d 2050 5044 550a 0a5c 7365 6374 696f .- PPDU..\sectio
00003530: 6e7b 5261 6469 6f20 4672 6571 7565 6e63 n{Radio Frequenc
00003540: 7920 496e 7465 7266 6572 656e 6365 7d0a y Interference}.
00003550: 0a0a 0a5c 7365 6374 696f 6e7b 4368 616e ...\section{Chan
00003560: 6e65 6c20 7365 6c65 6374 696f 6e7d 200a nel selection} .
00003570: 0a0a 5c63 6861 7074 6572 7b52 656c 6174 ..\chapter{Relat
00003580: 6564 2077 6f72 6b7d 0a0a 5c63 6861 7074 ed work}..\chapt
00003590: 6572 7b43 6f6e 6e65 6374 6564 2067 726f er{Connected gro
000035a0: 7570 737d 0a54 6f20 656e 6162 6c65 2063 ups}.To enable c
000035b0: 6f6c 6c61 626f 7261 7469 7665 2063 6861 ollaborative cha
000035c0: 6e6e 656c 2061 6c6c 6f63 6174 696f 6e2c nnel allocation,
000035d0: 2069 7420 6973 2069 6d70 6f72 7461 6e74 it is important
000035e0: 2066 6f72 2065 7665 7279 2041 5020 746f for every AP to
000035f0: 206b 6e6f 7720 7768 6963 6820 4150 7320 know which APs
00003600: 6974 2069 7320 636f 6c6c 6162 6f72 6174 it is collaborat
00003610: 696e 6720 7769 7468 2e0a 4f6e 6520 7761 ing with..One wa
00003620: 7920 746f 2073 6861 7265 2069 6e66 6f72 y to share infor
00003630: 6d61 7469 6f6e 2061 626f 7574 2077 686f mation about who
00003640: 2063 6f6c 6c61 626f 7261 7465 7320 7769 collaborates wi
00003650: 7468 2077 686f 2c20 6973 2074 6f20 6c65 th who, is to le
00003660: 7420 7468 6520 6163 6365 7373 2070 6f69 t the access poi
00003670: 6e74 7320 6772 6f75 7020 746f 6765 7468 nts group togeth
00003680: 6572 2e20 496e 666f 726d 6174 696f 6e20 er. Information
00003690: 7265 6c65 7661 6e74 2066 6f72 2063 6861 relevant for cha
000036a0: 6e6e 656c 0a61 6c6c 6f63 6174 696f 6e20 nnel.allocation
000036b0: 6361 6e20 7468 656e 2062 6520 7368 6172 can then be shar
000036c0: 6564 2066 7265 656c 7920 7769 7468 696e ed freely within
000036d0: 2074 6865 2067 726f 7570 2c20 6265 7477 the group, betw
000036e0: 6565 6e20 4150 732e 0a0a 5765 2077 696c een APs...We wil
000036f0: 6c20 7072 6f63 6565 6420 6279 206c 6f6f l proceed by loo
00003700: 6b69 6e67 2061 7420 736f 6d65 206f 6620 king at some of
00003710: 7468 6520 7265 7175 6972 656d 656e 7473 the requirements
00003720: 2066 6f72 2061 2067 726f 7570 2063 7265 for a group cre
00003730: 6174 696f 6e20 616c 676f 7269 7468 6d2e ation algorithm.
00003740: 2049 7420 7368 6f75 6c64 2077 6f72 6b20 It should work
00003750: 6465 6365 6e74 7261 6c69 7a65 6420 696e decentralized in
00003760: 2061 2064 6973 7472 6962 7574 6564 2066 a distributed f
00003770: 6173 6869 6f6e 2e0a 4865 6e63 652c 206e ashion..Hence, n
00003780: 6f74 206f 6e6c 7920 646f 6573 2074 6865 ot only does the
00003790: 2041 5073 2068 6176 6520 746f 2062 6520 APs have to be
000037a0: 696d 706f 7365 6420 6772 6f75 7020 6d65 imposed group me
000037b0: 6d62 6572 7368 6970 2c20 6275 7420 7468 mbership, but th
000037c0: 6579 2061 6c73 6f20 6861 7665 2074 6f20 ey also have to
000037d0: 6265 2061 626c 6520 746f 2063 7265 6174 be able to creat
000037e0: 6520 616e 6420 6465 6669 6e69 6e65 206d e and definine m
000037f0: 6561 6e69 6e67 6675 6c20 6772 6f75 7073 eaningful groups
00003800: 206f 6e20 7468 6569 7220 6f77 6e2e 0a4c on their own..L
00003810: 6174 6572 2077 6520 7769 6c6c 2070 726f ater we will pro
00003820: 706f 7365 2061 6e20 616c 676f 7269 7468 pose an algorith
00003830: 6d20 746f 2063 7265 6174 6520 6772 6f75 m to create grou
00003840: 7073 2c20 616e 6420 7468 656e 2065 7661 ps, and then eva
00003850: 6c75 6174 6520 636f 6d70 7574 6564 2067 luate computed g
00003860: 726f 7570 7320 6261 7365 6420 6f6e 2074 roups based on t
00003870: 6865 2061 6c67 6f72 6974 686d 2e0a 0a0a he algorithm....
00003880: 5c73 6563 7469 6f6e 7b44 6566 696e 6974 \section{Definit
00003890: 696f 6e7d 0a41 2063 6f6e 6e65 6374 6564 ion}.A connected
000038a0: 2067 726f 7570 2069 7320 6120 7365 7420 group is a set
000038b0: 6f66 2061 6363 6573 7320 706f 696e 7473 of access points
000038c0: 2074 6861 7420 6172 6520 7769 7468 696e that are within
000038d0: 2063 6c6f 7365 2067 656f 6772 6170 6869 close geographi
000038e0: 6361 6c20 7261 6e67 652e 2054 6865 2067 cal range. The g
000038f0: 726f 7570 2073 686f 756c 6420 636f 6e73 roup should cons
00003900: 6973 7420 6f66 2041 5073 2074 6861 740a ist of APs that.
00003910: 696e 7465 7266 6572 6520 7769 7468 2065 interfere with e
00003920: 6163 6820 6f74 6865 7220 7768 656e 2074 ach other when t
00003930: 6865 6972 2063 6861 6e6e 656c 7320 6172 heir channels ar
00003940: 6520 6f76 6572 6c61 7070 696e 672c 2073 e overlapping, s
00003950: 6f20 7468 6174 206f 7665 726c 6170 2063 o that overlap c
00003960: 616e 2062 6520 6176 6f69 6465 6420 7769 an be avoided wi
00003970: 7468 2061 2063 6861 6e6e 656c 2061 6c6c th a channel all
00003980: 6f63 6174 696f 6e20 616c 676f 7269 7468 ocation algorith
00003990: 6d20 7275 6e20 7769 7468 696e 2074 6865 m run within the
000039a0: 2067 726f 7570 2e0a 4e6f 7420 616c 6c20 group..Not all
000039b0: 4150 7320 696e 2074 6865 2063 6f6e 6e65 APs in the conne
000039c0: 6374 6564 2067 726f 7570 2077 696c 6c20 cted group will
000039d0: 6e65 6365 7373 6172 696c 7920 6265 2061 necessarily be a
000039e0: 626c 6520 746f 2068 6561 7220 6561 6368 ble to hear each
000039f0: 206f 7468 6572 206f 6e20 7468 6520 7261 other on the ra
00003a00: 6469 6f20 6469 7265 6374 6c79 2c0a 6275 dio directly,.bu
00003a10: 7420 616c 6c20 6e6f 6465 7320 7368 6f75 t all nodes shou
00003a20: 6c64 2062 6520 6162 6c65 2074 6f20 6865 ld be able to he
00003a30: 6172 2065 6163 6820 6f74 6865 7220 7468 ar each other th
00003a40: 726f 7567 6820 6120 7472 616e 7369 7469 rough a transiti
00003a50: 7665 2072 656c 6174 696f 6e20 286e 6569 ve relation (nei
00003a60: 6768 626f 7572 206f 6620 6120 6e65 6967 ghbour of a neig
00003a70: 6862 6f75 722c 2065 7463 2e29 2e0a 0a5c hbour, etc.)...\
00003a80: 7365 6374 696f 6e7b 5265 7175 6972 656d section{Requirem
00003a90: 656e 7473 2061 6e64 2061 7373 756d 7074 ents and assumpt
00003aa0: 696f 6e73 7d0a 5765 2061 7265 2067 6f69 ions}.We are goi
00003ab0: 6e67 2074 6f20 6265 206c 6f6f 6b69 6e67 ng to be looking
00003ac0: 2061 7420 686f 7720 4150 7320 6361 6e20 at how APs can
00003ad0: 6f72 6761 6e69 7a65 2074 6865 6d73 656c organize themsel
00003ae0: 7665 7320 7769 7468 6f75 7420 6120 6365 ves without a ce
00003af0: 6e74 7261 6c20 636f 6f72 6469 6e61 746f ntral coordinato
00003b00: 722c 0a62 7574 2069 7420 7368 6f75 6c64 r,.but it should
00003b10: 2062 6520 6e6f 7465 6420 7468 6174 2074 be noted that t
00003b20: 6865 2063 7265 6174 696f 6e20 6f66 2067 he creation of g
00003b30: 726f 7570 7320 636f 756c 6420 706f 7465 roups could pote
00003b40: 6e74 6961 6c6c 7920 6265 2065 6173 6965 ntially be easie
00003b50: 7220 6966 2061 2063 656e 7472 616c 697a r if a centraliz
00003b60: 6564 2065 6e74 6974 7920 6861 6420 7468 ed entity had th
00003b70: 6520 6675 6c6c 2070 6963 7475 7265 206f e full picture o
00003b80: 6620 4150 7320 616e 6420 7468 6569 7220 f APs and their
00003b90: 7261 6469 6f20 7265 6164 696e 6773 2e0a radio readings..
00003ba0: 4974 2063 6f75 6c64 2074 6865 6e20 636f It could then co
00003bb0: 6d62 696e 6520 6765 6f67 7261 7068 6963 mbine geographic
00003bc0: 616c 2069 6e66 6f72 6d61 7469 6f6e 2061 al information a
00003bd0: 6c6f 6e67 2077 6974 6820 4150 2072 6561 long with AP rea
00003be0: 6469 6e67 7320 746f 2063 7265 6174 6520 dings to create
00003bf0: 636f 6e73 6973 7465 6e74 2067 726f 7570 consistent group
00003c00: 732e 0a57 6520 7769 6c6c 2063 6f6e 7369 s..We will consi
00003c10: 6465 7220 7468 6520 7477 6f20 6f70 7469 der the two opti
00003c20: 6f6e 7320 6167 6169 6e73 7420 6561 6368 ons against each
00003c30: 206f 7468 6572 206c 6174 6572 206f 6e2c other later on,
00003c40: 2062 7574 2070 726f 6365 6564 696e 6720 but proceeding
00003c50: 6168 6561 6420 7769 7468 2050 3250 2067 ahead with P2P g
00003c60: 726f 7570 2063 7265 6174 696f 6e20 6173 roup creation as
00003c70: 2074 6865 206d 6169 6e20 636f 6e63 6572 the main concer
00003c80: 6e2e 200a 4573 7365 6e74 6961 6c6c 7920 n. .Essentially
00003c90: 7468 6973 206d 6561 6e73 2074 6861 7420 this means that
00003ca0: 616e 2041 5020 6861 7320 6e6f 206f 7468 an AP has no oth
00003cb0: 6572 206b 6e6f 776c 6564 6765 206f 6620 er knowledge of
00003cc0: 7468 6520 776f 726c 6420 7468 616e 2074 the world than t
00003cd0: 6865 206f 7468 6572 2041 5073 2069 7420 he other APs it
00003ce0: 6361 6e20 6865 6172 206f 6e20 6974 7320 can hear on its
00003cf0: 7261 6469 6f2e 0a46 6f72 2074 6865 2073 radio..For the s
00003d00: 616b 6520 6f66 2063 7265 6174 696e 6720 ake of creating
00003d10: 616e 6420 6576 616c 7561 7469 6f6e 6720 and evaluationg
00003d20: 6120 6772 6f75 7020 6372 6561 7469 6f6e a group creation
00003d30: 2061 6c67 6f72 6974 686d 2c20 7765 2077 algorithm, we w
00003d40: 696c 6c20 6173 7375 6d65 2061 206e 756d ill assume a num
00003d50: 6265 7220 6f66 2074 6869 6e67 7320 7468 ber of things th
00003d60: 6174 2077 696c 6c20 6861 7665 2074 6f20 at will have to
00003d70: 6265 2069 6e20 736f 6c76 6564 2061 7420 be in solved at
00003d80: 6120 6c61 7465 7220 706f 696e 743a 0a5c a later point:.\
00003d90: 6265 6769 6e7b 656e 756d 6572 6174 657d begin{enumerate}
00003da0: 0a09 5c69 7465 6d20 416c 6c20 4150 7320 ..\item All APs
00003db0: 7669 7369 626c 6520 6f6e 2061 6e79 2041 visible on any A
00003dc0: 5027 7320 7261 6469 6f20 616c 736f 2072 P's radio also r
00003dd0: 756e 7320 7468 6520 6772 6f75 7020 6372 uns the group cr
00003de0: 6561 7469 6f6e 2061 6c67 6f72 6974 686d eation algorithm
00003df0: 2e0a 095c 6974 656d 2049 6620 616e 2041 ...\item If an A
00003e00: 5020 6361 6e20 7365 6520 616e 6f74 6865 P can see anothe
00003e10: 7220 4150 206f 6e20 6974 7320 7261 6469 r AP on its radi
00003e20: 6f2c 2069 7420 616c 736f 206b 6e6f 7773 o, it also knows
00003e30: 2068 6f77 2074 6f20 6469 7265 6374 6c79 how to directly
00003e40: 2063 6f6e 7461 6374 2074 6865 2041 5020 contact the AP
00003e50: 2865 2e67 2e20 7669 6120 5443 5029 2e0a (e.g. via TCP)..
00003e60: 095c 6974 656d 2041 6c6c 2041 5073 2069 .\item All APs i
00003e70: 6e20 6120 6772 6f75 7020 6172 6520 636f n a group are co