ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐỖ VĂN MẠNH






MÃ HÓA MẠNG KHÔNG DÂY SỬ DỤNG
GIAO THỨC ALOHA










LUẬN VĂN THẠC SĨ CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG















Hà Nội - 2013


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ




ĐỖ VĂN MẠNH






MÃ HÓA MẠNG KHÔNG DÂY SỬ DỤNG
GIAO THỨC ALOHA


Ngành: Công nghệ Điện tử - Viễn thông
Chuyên ngành: Kỹ thuật điện tử
Mã số: 60 52 70




LUẬN VĂN THẠC SĨ CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG







NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN QUỐC TUẤN








Hà Nội - 2013

iii


Trang ph  Trang
 i
 iii
 vi
 ix

D x
 1
 4
1.1.  4
1.1.1.  4
1.1.2.  5
1.1.3.  6
1.1.4.  6
1.1.4.1.  6
1.1.4.2.  7
1.1.4.3.  7
1.2.  7
1.2.1.  7
1.2.2.  8
1.2.2.1.  8
1.2.2.2.  9
1.3.  9
1.3.1.  10
1.3.2.  11
1.3.3.  11
1.3.3.1.  11
1.3.3.2.  12
1.3.3.3.  12
1.3.4.  12
 14
2.1.  14
2.1.1.  15
2.1.2.  16
iv


2.2.  16
2.2.1. Pure-ALOHA 16
2.2.2. Slot-ALOHA 18
2.3.  20
2.3.1.  20
2.3.1.1.  20
2.3.1.2.  20
2.3.1.3.  21
2.3.1.4.  21
2.3.2.  21
2.4.  22
2.4.1. -ALOHA 22
2.4.1.1.  22
2.4.1.2.  24
2.4.2.  -ALOHA 25
2.4.2.1.  25
2.4.2.2.  25
 27
3.1.  27
3.1.1. Nghe 28
3.1.2.  29
3.1.3.  31
3.2.   32
3.2.1.  32
3.2.2.  32
3.2.2.1.  32
3.2.2.2.  33
3.2.2.3.   33
3.2.2.4.  34
3.2.2.5.  35

3.2.3.  35
3.2.3.1.  36
3.2.3.2.  36
3.2.3.3.  36
3.2.3.4.  37
v

3.2.4.  38
3.2.5.  38
3.3.  39
3.3.1.  39
3.3.1.1.  39
3.3.1.2.  40
3.3.1.3.  40
3.3.2.  40
3.4.  [31] 41
3.4.1.  41
3.4.2.  43
3.5.  45
3.6.  46
3.7.  48
3.7.1. Slot-ALOHA 49
3.7.2.  49
3.7.3.  50
3.8.  51
 55
 56
 59

vi


Danh m vit tt



ACK
Acknowledgment

API
Application Programming
Interface
 
ARQ
Automatic Repeat Query

CMAPS
Conflict Maps

COPE




CSMA
Carrier Sense Multiple
Access

CSMA/CA
Carrier Sense Multiple
Access with Collision

Avoidance


C/N
Carrier to Noise
T s gi
sut nhiu
DSSS
Direct Sequence Spread
Spectrum

ETX
Expected Transmission
Count

ExOR


     
     

FDMA
Frequency Division
Multiple Access
chia theo 

FEC
Forward Error Correction

FIFO

First In First Out

vii

GSM
Global System for Mobile
communications

IEEE
Institute of Electrical and
Electronics Engineers
 
IETF
Internet Engineering Task
Force
    

.
IP
Internet Protocol

ISMA
Inhibit Sense Multiple
Access

ITU-T
International
Telecommunication
Union-Telecommunication
Standardization Sector

- 
      

LAN
Local Area Network

MAC
Media Access Control
 
MIMO
Multiple-Input and
Multiple-Output
 
MORE



NP
Nondeterministic
Polynomial

OFDM
Orthogonal Frequency
Division Multiplexing
 
OMS
Opportunistic Multipath
Scheduling

PRMA

Packet Reservation
Multiple Access

QoS
Quality of Service

RFID
Radio Frequency
Identification
 
RSVP
Resource Reservation

viii

Protocol
RTT
Round-Trip Time

SINR
Signal to Interference plus
Noise Ratio
 
TDM
Time Division
Multiplexing
heo t
TDMA
Time Division Multiple
Access

       

TCP
Transmission Control
Protocol

UDP
User Datagram Protocol

UWB
Ultra-Wide Band

WAN
Wide Area Network

Wi-Fi
Wireless Fidelity


ix

Danh mng
Bu king 23
Bt ng s d 28
Bng 3.2 Hiu sut cho mt s n 45
x

Danh m th
 n s dng nhng. 4
Ging thc hi Gauss vi m > n 

nhn. 6
ng ci thi  truy hp tuyn
a P
a

b
cho ti khi c n ng ca
mng. 8
ng chng li v mn gi C qua router B.
ng truyt mε
AB
ε
BC
ng. 9
n nhiu
hop ti gateway kt ni ti Internet. Client kt ni vn gn nht. 10
 15
 pure-ALOHA 17
 t gia nhrong h thng pure-ALOHA 17
slot-ALOHA 18
 thng slot-ALOHA 18
t gia nh 20
 Cn 22
ng ca pure-ALOHA 24
 tr a pure-ALOHA 24
ng ca slot-ALOHA 25
 tr a slot-ALOHA 26
 minh hng 27
 ci 30
 COPE 39

 cho thc hin COPE 41
 hiu v u sua COPE
43
a k lung hai ching. M
t chuyn tip. 46
t truyn dn
p
,
khi
1
,
0
0N 

4k 
52
xi

t truyn dn
p
,
khi
1
,
0
0.1N 

4k 
53
ng t


, vi
**
,
c
pp

4k 
53
1

M U
Tt c mng vi c gi nh r
u mn thoc truy 
ng cao tc trong ng dng d lic lp
chia s  nh tuyn, ngun d liu
khin lu d 
ng l gi  chuyn ti
d ling kt hp m liu   liu ti
u ra.
Ma lu xem li kh ng dng 
mc bit, lu t ki
chun 802.11i d liu v
 bng ti
 tr l u sut ca slot-ALOHA cho
mt topo mng Vi n slot-ALOHA l slot-ALOHA nh
ng [12] -[30] nh cho giao thc slot-ALOHA
ng, nc hin mng v
 ng lu lng truy cp c
M       xut trong [4, 31], thc hi  

slot-ng, btn dng li th  truyn qung
truyc mc qu
t m ng bt l
n tin kiu qu
mt trong nhng hn ch n ca m
Mng dng da t chia s ng truy
tuyn, qung truyn ca my. M 
tr n thit trong mt khong thi gian ng
cc bn
  thc hi
c hin XOR nhit qu, nu m
 giu  rng kii hai lung
truyc hin vi nhit c
Thit k kin tic thit k mt
thuu qu p phi mt s c nhu
 i hn
c nhng truyn. Th 
 di bm truyn tin c
ng ti tt c n phn hi ca ln
2

 i thit k mt k thu
truyn li hiu qu 
K thung d  t ca
 cng cc
b c b   gi
truyng unicast b lm rnh truyn
nh s  chuyng. Vi
ng  t
lun sau:

 t nhiu lc t   
ng mn.
 ng truyn trong mn b tc nghng gm nhiu
lung UDP, COPE s ng mng 3 - 4 ln.
 Nu khin lu
ci thiu so vng b
i trong router nh i loi b n
do tc nghn.
 Vi mi kt ni vi Internet qua access point, s ci thin v t
ng s d bii ph thu l gia tng
xum truy cp (access point-AP),
i t 5% ti 70%.
 t b u cui n to ra s  u thm
i s ta k thut truyn li theo chu
d lit b 
ng TCP s 
B cc ca lu
Ni dung ca lun c b c
Nhng v n. ii thiu tng quan v 
mt k mng lc 1.1 gii thiu v ng. Mc 1.2 li
ng. Mc 1.3 tho lun king mng l
n ti.
K thup. Gii thiu giao thp: Giao th
truy cp tranh chpc hong
ca giao thng ca hiu ng l kt qu 
phng thu--ALOHA.
3

  dng giao thc ALOHA
t k, thc hi hi COPE

s dng giao thc ALOHA, mt kii cho truyn tin s d
mng  m ci thing mn. Ki
m gia lp MAC, t  truyn nhit
ln truyn.
Tip theo  giao thLutt topo
mng i d liu v
ng
tmng  ki
tc nghn trong mt mt nhing truy c
a luc hin t
lp qua lp v lp MAC.


4

. NHNG V N
1.1. ng


1  gin s dng ng nhm ng.
Ngun S
1
cn truy
1
ti c D
1

2
n S
2

cn truy
2
i
D
1
, D
2
. Cho rng tt c ng truy n mu router
R
1

2
ch chuyn ting truyn  gia s b tc nghn.
Ti mi thm, hai router hoi P
1
ti D
2
hoc P
2
ti D
1
c li, nu router
g ng truyP
1
⊕P
2
(hoc bt k t hp tuya P
1

2

) xem
  nh
1
s c P
2
sau khi thc hi

1
(nhc trc tip t S
1
) vi P
1
⊕P
2
 D
2
s c P
1
. Do
 t tng multicast c
nh tuyn ch c t
Mu trm D
1
nhn P
1
trc tip vt li bng 
1
c
P
1

⊕P
2
vt li 
2
ng hp d liu s 
1
vi thng 
1
(1 - 
2
) +

2
(1 - 
1
) .
Mng tuy v  thay th
 linh hoc
 kt hp v chuyn ti to ra
t hp tuya n ti mi g
 ngn gng mc sau.
1.1.1. 
Gi s mL bitt hp v
bit  bit 0. Ta xem s bit t 
5

t ca tp hu hn
2
s
F

, m ca L/s . Vuy
 hp tuyu,  c thc hin
ng hu hn
2
s
F
.
Gi P
1
, P
2
, …, P
n
n u t mt hoc nhiu ngu
i X  c s
(1), (2) ( )g g g g n

ng
2
s
F
g   X c t 
ngun:
1
()
n
i
i
X g i P




(1.1)
Tnh ti mi v ,
1
( ) ( ) ( )
n
i
i
X k g i P k



vi P
i
(k) X(k)
 th k
’
ca P
i
X  1ng F
2
={0,1}, m  mt bit
i tuyi bi R
1
sau khi nhc P
1

2


1
⊕ P
2
 mc
 c X c s dng t gi
d liu, s gi mc sau.
 c thc hi   mt tp

1
1
( , ), ,( , )
m
m
g X g X
vi
j
g
 X
j
 
th li ti
''
( , )gX
ba chn mt t  s
(1), , ( )h h h m
 hp tuy
'
1
()
m

j
j
X h j X



 
'
g

b 
h
 s u P
1
, P
2
,…, P
n
;
i mi s h thy
'
g
c cho bi
'
1
()
m
i
j
g h j g




ng
th lp li t trong mng.
1.1.2. Gi
X
1
, X
2
, …, X
n
v 
ng
1
, ,
m
gg
  hp tuy
u. V n, cn phi gii h :
1
()
n
j j i
i
X g i P



(1.2)

 u P
i
 i m
n n. Khi m  n t n t hc lp tuy 
 c ging phm bo
truyt n c lp tuy d c hi
 mc sau.
6

1.1.3. a chn t hp tuy
V ca thit k a chn t hp tuy mng thc
hi b t n t hc lp tuy  gii
u. Mt thu m la chn theo bin ng
 s ng
2
s
F
, theo kic lp trung [25]. Vng
ng  sut chc chn ca la chn t hc lp tuy [25]
sun quan tc cng 2
s
. Kt qu ng cho thy thi
 (, s = t nh.
 s dng thu thit k ng. Thu
thc thi gian cho multicastt m mnh t hp tuy
m thc hi s dng h s tuyn
 ng thu hn ch cu
ng.
1.1.4.  thc t
1.1.4.1. Gi

Vic giu gii mt h  thc hin s
d Gauss. Mt   
ng, theo tn gig
n mt 
ma trn gi c thc hin ti dng ma tr
Mt c gi nng ca ma trn. Nu mt 
tin i b bit   loi
b. Khi mt phn  a ma trn gm mt ng e
i
(   vi duy
nht mt t  i
’
X u P
i
y ra khi
nhc n  c lp tuyn thc hin ti tt c
 ca m t  ch  Gauss bin
i m n u.

2 Ging thc hi Gauss vi m > n 
nhn.
7

1.1.4.2. Khi 
Thc tc ca ma tri gii h
 i mc t hp vc ca
khi ng ti hic cng.
ng nh s t ca truy
gim hiu sun l thng thc t 
 mt byte trong mt 

c khi.
1.1.4.3. ng hu hn

2
s
F
, thc hii s 
co bit ca XOR. a chui b
0
, … , b
s
ca s c b
0
+
b
1
x + … + b
s-1
x
s-1
c thc hin bng ca hai
 phi cc ti gi
i thuEuclidian. C  thc hin hiu qu i
ch.
1.2. Lng
 ng dng trong nhng ng c m
tng ad-u qu ci thi
n hong ca mng.
1.2.1. ng
c lng multicast. Ahlswede et al. [1]

ch ra “với tốc độ nguồn cố định, nếu không có mã hóa thì mạng có thể hỗ trợ các nút
nhận tách biệt. Với lựa chọn thích hợp các hệ số mã tuyến tính, mạng có thể hỗ trợ tất cả
các nút nhận đồng thời”.
N  ng, mi m
th nhn vi t t dng tt c ng. Do v 
m  ng t
ng chng nhi v ng m
 1.
gi ngun S
1
truyh D
2

2
ti D
1
. Ta s d
truy c t unicast t mi ngun t mt 
ng, ngun ch  truyn tin vi t 0,
ng.
Mt ng t
truyn multicast s dng thuc thi gian.
8

1.2.2. S 
m ln nht c  
ng ging nhng, bi
nh s  ti
c nhng thc hin bii tuy
t ngun  m m

  mng.

3 Mmng ci thi  truy hp tuyn
a P
a

b
cho ti khi c ng ca
mng.
  S qui A
  tr (hong nht
thr S. Nu tr S quP
a

(hoc P
b
 s  nhu tr
S quP
a
⊕ P
b
, hoc t hp tuyi ln
truyn s mang nhi ti tt c ng.
1.2.2.1. i ni dung
   ng trong thit lp mng
Bittorrent, m trong mng cn ti xung mt c chia nh
O(n)   gin gi s n  i file. Vi thit k tp trung, giao
thc t  file ti tt c  trong θ(n) i
p trung, s cn θ(nlog(n)) a s log(n) 
n tin nh s d

truy hp tuyt c i  u nhn
c bt c n   
b file trong θ(n)  c n hot
ng ca mc hiu sut tp trung s dng mt thut
n.
9

1.2.2.2. Chng li m
ng li v m 4, ngun
A cn gng truyng AB
ε
AB
ε
BC
. S dng giao
thn [20]) hogu t tng ti
- ε
AB
)(1- ε
BC
) (gi s mng truyc mt 
 m ng truyi


4 ng chng li v mn gi C qua router B.
ng truyt mε
AB
ε
BC
ng.

ng ci thing hng
truyn. Nu ta cho router B s dng, g hp tuy
cc t  - ε
AB
),(1- ε
BC
)}, cao
i truyn l
mt t ngun, router B phi bo m truy s t hp tuyn thi
th gi thu c s dng trong topo m
dng ( multicast, unicast, broadcast, .
1.3. Mng i (mesh)
Mng  i t ni vi nhau qua
nhing thng nht s dng thu  t
ni di. Mt n qua nhing truy
tuyc khi ti  gateway kt ni ti m t
 ng d m truy cp (access point) 
sut truyn thu hon khai tht ni s dn
ti tt c access point s t5
minh ha kia mt mng  mesh 
10


5 Kin nhiu
hop ti gateway kt ni ti Internet. Client kt ni vn gn nht.
ng mt ni,
t vi phn cn m 
 n tip d
u thp, d i nhing th lu
mng mi (c c trin khai vi mt ni

Ing mi s xut hiu
a hng dt ni
Internet rng khp vng lng ad-hoc t cao.
1.3.1. Lp v
Lp vt a phn lng mng s dng chun phn
cng 802.11. Ph h tr  truyn dng t
hp u ch  u [23] ch
 thut tri ph chui trc tip (DSSS) hong ti mt megabit trong khong tn
2,  bit s dng
hn s tr dng tn s ti 5,8 GHz
ch s dng t bit OFDM.
  linh hot v t l li s dng
thu m thua ch
 ng tu g
u v  thut phn cng s d MIMO, loi b nhiu
ng (UWB)  h tr t s k thut lp vt
c trit v 
th ng k thung m, mng mi s 
ng phc tp ging truyn trong nhiu  ca m
h thng phc tu so v thng MIMO trong mn hoc
mng t ng.
11

1.3.2. Lt d liu
Lp MAC ca mn  mesh t k i m
tuyng s dng  dng APc MAC hin ti ca
mng  d c thit k cho access
point. Giao thc dm nhn s Carrier Sense) 
  ki i bu truy
 ng b Ack t n, nc ACKho r

mt hot), ch  truyn 
truyn li. Nhic hin vi giao thc CSMA/CA cho mng 
meshu ch MAC c ca
s, ca s t c gi c
i th thut b
u cui n hoi cho truyng thi.
Nhu gt s giao thc MAC mi. Conflict Maps
(CMAPS) [29mt giao thng mt b i ca vic
truyng thi d thut lp v
i b nhiu  gii quyt v ng k thu
p ng th ng mt giao thc MAC thc t
dng k thut v lu t c [22
 thng vi truyng s to
ra nhiu  n. Nhng k thui mt vi nh
 phc tp ca h thc t c
cu [26hu khi
 cn thic bing m     s dng li
 trong mng m c n tr i t 
bt truyn tht ca vin   
u.
1.3.3. Lp mng
nh tuyn trong mng mc tp bi s ng ging
truyn vi nhau. Rt nhiu giao thnh tuy s 

1.3.3.1. Giao thnh tuyn v
nh tuyn trng truyn (link- 
 m hop, k vng 
Transmission ETX) [24i gian truyn (Round-Trip Time  RTT)nh
nghch o ct truyn truyn. ETX cho mt ng
truyng c ETX c n hnh

12

tuyng dn ngn nht gia tt c  cp  
ng. Metric ETX hong tt nhng m.
1.3.3.2. nh tuyng
Ma s dnh tuyn dng tp
nhn li ln. Khi mt ng truyn b t, mt p hng sn
 c s dng. Do v thit lnh tuyn m tr,
c phc l c ci thi ci thin ph thuc
n gia ngunh tuy
phc tp.
nh tuynh nhiu tuyn, s dng m
n qua li n li. Lp li nhing (OMS) 
 tr thp ho
 [28 xut ga m
ng ri nhau trong mt mng ad-ng chng s ma
mt s nh do fading hoc di chuy
Giao thnh tuyn [19, 21 
 thc hinh tuyng. Trong hai h thng, s la
chn ca hop tic thc hin sau khi truyn  tin. ExOR [19] chn hop tip
ng c kin t [21] s dng mp cn
 dng m loi b  kt h
 thc t v ng
. Tr ci thi tin cy u
cui  u cui (end-to-end)n tip tt c 
l tin ct nhiu truyn d.
1.3.3.3. nh tuy
So vi k thunh tuyn da theo toponh tuyn tip
 bi s d a   i topo 
ng tnh tuynh tuyt

nh tuyt loi ca k thunh tuyng, trong
nh chuyn ti a  hin ta
 t c nh tuyu gp phi mt vn 
c bm ngay c khi mt con ng tn ti gia ngu
 truyn tin cy, thunh tuy th hai chiu 
ra gng thung mt nhi v
thunh tuyng.
1.3.4. Lp giao vn
i ta s dp giao vn t k
in gp phi mt s v nhu
13

 u chc lp giao vn. Giao thc c mt
c ngh l li bit cao, mc nghng
gng m i
xn bi xng vu) ng ti truyn ACK, kt qu nh
ng ti hiu sut cu [16t nhi thu ci thin
hia TCP trong mn.
n ca m u khin
truy cp vi giao thc slot-ALOHA cho truyn dn theo khe th-ALOHA
cho truyn dng mng t.

14

K THUP
M s dng chung mng truyp 
giao thc truy c. Giao th  tho thun
p hp nhng quy tc gia nhng ng truy dng
mng chung.  m bo hing truy cng
thc truy cc s dng:

a) Truy cp d ch lp lp
b) Truy cp d mng
p.
Khi t s xut hin nu hn mt ng gng truy c
m. Mt cch v mng hii (Thoi, d
li      u v cht lng dch v - QOS (Best effort,
ng thc truyc truy cng xu
 .
Truy c: t giao tip t n mm.
Nhng tr ng truy truyn d lin
trm gc t chc nhng truy cp truyn thit cho vic
s dng hiu qu ngu
Truy cng xung: ng xung t mt trm
 n nht kt nm  m. Tr 
qu  t          nh    a ch
DL-MAP trong bn tin DL- li nhng bn tin hoc d lia ch cho
t gi
2.1.  giao thp
B vi giao thu giao th
n. Nhic g ng giao th
 i nhng giao thnhng giao
thc tranh chp, nhng giao thc p ng giao thc lp CDMA.
Nhng giao thc tranh chp (hay truy cp ng
chc chn rng s truyn tin s  t b
n tin (truy cn) tng giao
thn phi gii quyt s t nt hin.
Nhng giao thp lng hai hoc nhiu
m bp lch s
truyn tin ca nhc lp lc thc hin theo ki 
mc ct phn cng truyn, hoc theo kiu ng