1

M ă

U

Trong nh ng n m g n đây, do s ti n b c a khoa h c k thu t,
vi c s n xu t các thi t b c m bi n nh và chi phí th p tr nên kh thi v
m t k thu t và m t kinh t . Vi c thi t k và th c hi n có hi u qu m ng
c m bi n không dây tr thành l nh v c thu hút đ c nhi u s quan tâm vì
ti m n ng ng d ng c a m ng c m bi n trong các l nh v c trong đ i
s ng hàng ngày nh trong y t , trong công nghi p, trong quân s …
Tuy v y, vi c thi t k và th c hi n có hi u qu m ng c m bi n không
dây ph i đ i m t v i r t nhi u thách th c, m t trong nh ng thách th c l n
nh t trong m ng c m bi n là ngu n n ng l ng b gi i h n và không th
n p l i, chính vì th hi n nay r t nhi u nghiên c u đang t p trung vào
vi c c i thi n kh n ng s d ng hi u qu n ng l ng c a toàn m ng.
Xu t phát t nh ng yêu c u th c t đó, đ tài “ nh tuy n QoS hi u
qu n ng l ng cho m ng c m bi n không dây theo d ng phân c m” đ c
th c hi n nh m gi i thi u m t cách t ng quan v m ng c m bi n không
dây, các giao th c đ nh tuy n ph bi n hi n nay nh : LEACH, LEACHC, MTE, STAT- CLUSTER …, gi i thi u v giao th c đ nh tuy n QoS
hi u qu n ng l ng cho m ng WSN theo d ng phân c m, đ ng th i s
d ng m t ph n m m MATLAB đ mô ph ng gi i pháp m i đ c đ xu t
này.
án g m có 4 ch

ng:

Ch ng 1: T ng quan v m ng c m bi n không dây (WSN): đ a ra
đ nh ngh a, c u trúc m ng WSN, các y u t nh h ng đ n c u trúc m ng
WSN, các thách th c mà m ng WSN ph i đ i m t.

M ng c m bi n không dây (WSN - Wireless Sensor Network) là
m ng có hai ch c n ng: m ng và c m nh n thông tin t môi tr ng.
M ng WSN có đ c đi m các nút liên k t v i nhau b ng k t n i sóng
vô tuy n trong đó các nút m ng th ng là các thi t b đ n gi n, nh g n,
giá thành th p ... M ng lo i này có th có s l ng l n, đ c phân b m t
cách không có h th ng trên m t di n, s d ng ngu n n ng l ng h n ch ,
có th i gian ho t đ ng lâu dài kho ng vài tháng đ n vài n m, có th ho t
đ ng trong môi tr ng kh c nghi t nh : ch t đ c, ô nhi m, nhi t đ ...
Các nút m ng th ng có ch c n ng c m nh n, quan sát môi tr ng
xung quanh nh nhi t đ , đ m, ánh sáng ... theo dõi hay đ nh v các m c
tiêu c đ nh ho c di đ ng ... Các nút giao ti p v i nhau và truy n d li u
v trung tâm (base station) m t cách gián ti p b ng k thu t đa ch ng
(multi-hop).
1.2 C u trúc m ng c m bi n không dây
1.2.1 C u trúc ph ng
1.2.2 C u trúc phân c p
1.3 Các đ c tr ng c a m ng c m bi n không dây
1.3.1 N ng l ng tiêu th
1.3.2 Chi phí
1.3.3 Lo i hình m ng
1.3.4 Tính b o m t
1.3.5
tr
1.3.6 Tính di đ ng


4

1.4 Nh ng khó kh n trong vi c phát tri n m ng không dây
1.4.1 Gi i h n n ng l ng


6

2.2.1.2 Các giao th c phân c p
2.2.1.2.1 Giao th c LEACH
2.2.1.2.2 Giao th c PEGASIS
2.2.1.2.3 Giao th c hi u qu n ng l

ng c m nh n m c ng

ng

2.2.1.3 Giao th c đ nh tuy n d a theo v trí
2.2.1.3.1 Giao th c GAF
2.2.1.3.2 Giao th c GEAR
2.2.2 Các giao th c đ nh tuy n xét theo ho t đ ng
Ph n này s trình bày phân lo i các giao th c theo ho t đ ng c a
giao th c.
2.2.2.1 Các giao th c đ nh tuy n đa đ

ng

2.2.2.2 Giao th c đ nh tuy n th i gian s ng c c đ i
2.2.2.3 Multipath Directed Diffusion
2.2.2.4 Các giao th c d a trên truy v n
2.2.2.5 Giao th c Directed Diffusion
2.2.2.6 Giao th c đ nh tuy n Rumor
2.2.2.7 Giao th c d a trên th

ng l

d ng trong giao th c đ nh tuy n QoS hi u qu n ng l ng cho m ng c m
bi n không dây (WSN) theo d ng phân c m. Hi u qu c a thu t toán s
đ c so sánh v i gi i thu t ch s d ng tr m ngu n t nh ho c ch s d ng
tr m ngu n đ ng, hi u qu c a thu t toán s đ c th hi n vi c t ng th i
gian s ng c a m ng, c i ti n các tham s đ nh tuy n QoS nh đ tr , t l
m t gói tin, t l d li u nh n đ c.
3.2 Mô t giao th c đ nh tuy n QoS hi u qu n ng l
c m bi n không dây (WSN) theo d ng phân c m
3.2.1 Mô t v n đ

ng cho m ng

Giao th c đ nh tuy n QoS hi u qu n ng l ng cho m ng c m bi n
không dây (WSN) theo d ng phân c m h ng đ n gi i quy t ba (03) v n
đ sau:
Th nh t là, trong ki n trúc c s c a m ng WSN, tr m g c là t nh
và các nút c m bi n s d ng ph ng th c truy n thông đa đi m đ g i gói
tin đ n tr m g c. V n đ v đi m nóng (hot-spot) là v n đ th ng xuyên
x y ra trong m ng WSN v i tr m g c t nh và làm gi m đáng k th i gian


8

s ng c a toàn m ng. B n ch t t nh c a tr m g c là nguyên nhân gây ra
hi n t ng đi m nóng khi mà cùng m t th i đi m có quá nhi u nút g n
tr m g c đ ng th i g i d li u đ n tr m g c. H n ch c a các tr m g c
t nh là nó s làm t ng đ tr g i nh n gi a các nút đ u cu i trong th i
đi m các nút đ ng th i g i d li u đ n tr m g c. V i gi i pháp s d ng
tr m g c đ ng, d li u đ c g i đ n tr m g c đ ng b ng cách di chuy n
tr m g c đ ng theo các chu k trong m ng WSN, các nút s g i d li u


tr ng. Nút c m bi n t o ra nhi u lo i l u l ng khác nhau có đ tr và
b ng thông s d ng riêng. i u này c n m t c ch u tiên gói đ đ m b o
các b n tin đ c x lý m t cách phù h p d a trên các yêu c u QoS riêng.
Nh ng trong giao th c chuy n ti p gói, t t c các gói tin l i có cùng m c
đ u tiên. K t qu là vi c chuy n ti p cho phép các b n tin có đ u tiên
th p đ c truy n v i đ tr th p còn các l u l ng th i gian th c l i ph i
ch . Vì th b n tin đ u tiên th p là nguyên nhân gây ra tr các nút c m
bi n.
gi i quy t v n đ này, l u l ng đ n đ c chia thành nhi u lo i
khác nhau, d a trên đ tr khác nhau và b ng thông yêu c u c a t ng l p
l u l ng. Các l p riêng v i đ u tiên khác nhau, l u l ng th i gian
th c s có đ u tiên cao nh t và các d li u v n b n d ng “best effort” thì
có đ u tiên th p nh t. Quy t đ nh chuy n ti p gói tin đ c d a vào đ u
tiên đã đ c phân lo i cho các gói. Vi c x lý chuy n ti p gói tin phù h p
cho t ng lo i d li u có đ u tiên khác nhau s làm gia t ng th i gian ch
trong hàng đ i c a các gói tin có đ u tiên th p, các gói tin có đ u tiên
th p có th s ph i ch vô th i h n.
Th ba, các b n tin khác nhau đ c t o ra b i các nút c m bi n có
m c đ quan tr ng khác nhau. Vi c liên t c g i t t c các b n tin đ c t o
ra b i các nút c m bi n đ n tr m g c s làm nh h ng đ n hi u qu s
d ng n ng l ng c a các nút c m bi n. Quá trình này s làm c n ki t tài
nguyên n ng l ng c a h th ng WSN khi ph i tu n t truy n các b n tin
có đ u tiên th p đi, trong khi đó các b n tin quan tr ng h n l i ph i ch
đ n l t đ truy n.
gi i quy t v n đ này, d li u đ n ph i đ c phân
lo i đ u tiên theo nhi u lo i b n tin khác nhau d a trên đ quan tr ng
c a n i dung gói tin. K t qu là s có u tiên trong vi c chuy n ti p các
gói tin có đ u tiên cao d a trên quá trình so sánh các b n tin quan tr ng
và b n tin thông th ng. Do đó hi u qu s d ng n ng l ng c a các nút

l ng trong quá trình ho t đ ng. Các nút c m bi n (g m c các
“super node” và nút thông th ng) là t nh và không có kh n ng di
đ ng. Ch có tr m g c đ ng m i có th di chuy n đ c.


11

Hình 3.1: Mô hình m ng
3.2.3 Mô t giao th c đ nh tuy n QoS hi u qu n ng l
c m bi n không dây theo d ng phân c m

ng cho m ng

Giao th c đ nh tuy n QoS hi u qu n ng l ng cho m ng c m bi n
không dây theo d ng phân c m t p trung vào v n đ c t lõi là QoS và hi u
qu s d ng n ng l ng trong vi c thu th p d li u m ng WSN. Ho t
đ ng c a giao th c đ nh tuy n QoS hi u qu n ng l ng cho m ng c m
bi n không dây theo d ng phân c m đ c chia thành các pha chính và pha
ph . Có hai pha chính (Pha thi t l p và pha n đ nh) và chín pha ph (xem
hình 2 bên d i). Pha chính đ u tiên là pha thi t l p trong đó có ba pha
ph (kh i t o, l a ch n CH và phân c m, c p nh t đ nh tuy n). Pha chính
th hai là pha n đ nh; nó đ c chia thành sáu pha ph có tên nh sau:
phân lo i đ u tiên c a d li u, chuy n ti p d li u đ n CH/Super node,
chuy n ti p d li u đ n tr m g c t nh, chuy n tr ng l ng hàng đ i đ n
tr m g c đ ng, l p l ch di chuy n tr m g c đ ng, thu th p thông tin t
tr m g c đ ng.


12




13

Pha chính th hai là pha n đ nh; nó đ c chia thành sáu pha ph có
tên nh sau: Phân lo i đ u tiên c a d li u, chuy n ti p d li u đ n
CH/Super node, chuy n ti p d li u đ n tr m g c t nh, chuy n ti p tr ng
s h ng đ i đ n tr m g c đ ng, l p l ch di chuy n tr m g c đ ng, thu th p
thông tin t tr m g c đ ng.
Trong pha n đ nh, giao th c đ nh tuy n QoS hi u qu n ng l ng
cho m ng c m bi n không dây theo d ng phân c m s th c hi n nhi m v
thu th p d li u. Pha n đ nh đ c chia làm các pha ph sau:
3.2.3.2.1 Phân lo i đ ă u tiên c a d li u
Trong pha này, t i m i nút c m bi n, d li u đ n s đ c phân lo i
đ u tiên d a vào lo i gói tin và n i dung gói tin.
u tiên đ c gán
cho các gói tin s đ c s d ng trong quá trình đ nh tuy n và chuy n ti p
gói tin m t cách phù h p nh m giúp duy trì ch t l ng d ch v c a m ng.
3.2.3.2.1.1 Phân lo i u tiên d a trên lo i gói tin
3.2.3.2.1.2 Phân lo i d a trên n i dung gói tin
3.2.3.2.2 Chuy n d li u đ n nút CH/super node
Khi m t nút c m bi n nh n đ c m t d li u, d li u này c n ph i
đ c truy n đ n tr m g c (sink). Nút c m bi n s phân lo i đ u tiên d a
vào tính ch t quan tr ng theo lo i gói tin và n i dung gói tin (nh đã mô t
ph n trên).
qu n lý các gói tin v i các m c đ u tiên khác nhau, m t
hàng đ i s đ c duy trì t i m i nút c m bi n/CH/super node. Trong pha
này, m i nút c m bi n s g i d li u mà nó nh n đ c đ n các nút đ c
l a ch n là CH d a vào đ u tiên c a gói tin. Nút c m bi n s ki m tra
hàng đ i ch a đ u tiên c a nó đ ch n ra gói có đ u tiên cao nh t và

MQW thì d li u s đ c g i đ n tr m g c t nh đ gi m thi u đ tr . Sau
khi quy t đ nh truy n d li u đ c th c hi n, d li u s đ c g i đ n tr m
g c t nh thông qua đ ng truy n đa đi m c a các super node đã đ c thi t
l p trong pha c p nh t đ nh tuy n.
3.2.3.2.4 Chuy n ti p tr ng l

ng hàng đ i đ n tr m g c đ ng

Vào cu i chu k đ u tiên c ng nh t t c các chu k di chuy n c a
tr m g c đ ng đi qua t t c các nút c m bi n trong m ng c m bi n không
dây, tr m g c đ ng g i yêu c u nh n thông tin v tr ng l ng hàng đ i
c a các nút c m bi n. Super node là đ u cu i c n nh n thông tin này, m i
super node s tính toán giá tr QW c a nó và g i thông tin đ c yêu c u


15

đ n tr m g c đ ng. Sau đó, tr m g c đ ng s đi u ch nh chu k di chuy n
c a nó d a trên các thông tin v QW nh n đ c t các super node.
3.2.3.2.5 L p l ch di chuy n c a tr m g c đ ng
Thông tin v QW c a t t c các super node đ c g i đ n tr m g c
đ ng trong pha tr c s đ c s d ng t i pha này đ l p l ch di chuy n c a
tr m g c đ ng trong m ng WSN đ thu th p d li u t các super node.
Chu k di chuy n đ u tiên c a tr m g c đ ng s d a vào đ ng đ nh tuy n
đ u tiên.
đ m b o ch t l ng d ch v và đ cân b ng s d ng n ng
l ng, tr m g c đ ng di chuy n chu k th 2 và các chu k k ti p d a
vào n ng l ng còn l i và thông s QW c a các super node trong m ng.
3.2.3.2.5.1 i u ch nh l ch di chuy n
3.2.3.2.5.2 Qu ng bá thông tin v l ch di chuy n c a tr m g c đ ng


D a trên mô hình h th ng đã đ c thi t k trên, ph n mô ph ng s
đ c xây d ng đ đánh giá hi u qu c a giao th c đ nh tuy n QoS hi u
qu n ng l ng cho m ng c m bi n không dây theo d ng phân c m
(EEQR). Hi u qu c a giao th c đ nh tuy n này s đ c so sánh gi a
tr ng h p s d ng đ ng th i tr m g c đ ng và t nh v i tr ng h p s
d ng tr m g c t nh ho c tr m g c đ ng. Các tham s đ nh tuy n nh n ng
l ng truy n c a m t gói, đ tr trung bình trên m i gói tin, t l m t gói
tin trung bình, l u l ng đ ng truy n, th i gian s ng c a m ng s đ c
s d ng đ đánh giá hi u qu c a giao th c đ nh tuy n QoS hi u qu n ng
l ng cho m ng c m bi n không dây theo d ng phân c m.
Ph n ti p theo mô t chi ti t n i dung thi t l p mô ph ng, mô hình
n ng l ng và th o lu n v các k t qu mô ph ng.
1.1 Thi t l p mô ph ng
Ch ng trình mô ph ng đ c th c hi n trên m t ph m vi c m bi n
r ng 200x200m2 và s l ng nút c m bi n thay đ i t 20 đ n 240 nút c m
bi n cho các thí nghi m khác nhau. Các nút c m bi n đ c đ t ng u nhiên
v i m t v trí t a đ (x,y) không thay đ i t đ u đ n cu i mô ph ng. M t
tr m g c t nh đ c đ t c đ nh t i trung tâm c a m ng và m t tr m g c
đ ng có kh n ng di chuy n xunh quanh m ng. Mô ph ng s đ c th c
hi n v i m t chu i/dãy giao ti p b ng hai l n dãy c m bi n c a các nút
c m bi n. Các tham s mô ph ng đ c trình bày trong B ng 4.1 d i đây.
B ng 4.1: Các tham s mô ph ng
Tham s mô ph ng
Ký hi u
1. M ng
Di n tích khu v c m ng
S
V trí Tr m g c t nh
(x,y)


EI
ED

1J

+ .
.

Trong đó Eelect là giá tr n ng l ng đi n, fs là m t h ng s lan
truy n t do trong không gian và là n ng l ng trong m t b khu ch đ i
khi truy n trên m t kho ng cách ng n h n dcrossover, và mp là h ng s lan
truy n đa tuy n và là n ng l ng khu ch đ i c a m t b khu ch đ i khi


19

truy n qua m t kho ng cách l n h n dcrossover. N ng l
nh n gói tin l-bit đ c tính b i công th c:

ng tiêu hao khi

ERX = l Eelect
1.3 Các k t qu và th o lu n
Hi u qu c a ph ng pháp đ nh tuy n QoS hi u qu n ng l ng
đ c đánh giá và so sánh v i các tr ng h p ch s d ng tr m g c t nh
ho c tr m g c đ ng. Các thông s m ng đ c so sánh bao g m hi u su t là
n ng l ng trung bình trên t ng gói tin, th i gian s ng c a m ng, l u
l ng truy n, đ tr trung bình trên t ng gói tin, t l m t gói tin và th i
gian ph sóng. Các th nghi m đ c mô t nh d i đây.
1.3.1 N ng l

ng trung bình trên t ng gói tin

N ng l ng trung bình trên t ng gói tin đ c đo l ng b i n ng
l ng tiêu t n đ truy n gói tin v đ n tr m g c. Tham s này ph thu c

Có th th y r ng, giao th c đ nh tuy n QoS hi u qu n ng l ng có
th i gian s ng T100% là dài nh t, ti p theo là giao th c s d ng tr m g c
đ ng và cu i cùng là giao th c s d ng tr m g c t nh có th i gian s ng c a
m ng ng n nh t. i u đó ch ng t r ng giao th c đ nh tuy n QoS hi u qu
n ng l ng c i thi n th i gian s ng c a m ng so v i hai giao th c còn l i.
1.3.3 L u l

ng m ng (s gói tin đ

c truy n đi trong m t giây)

L u l ng m ng là s l ng gói tin đ c nh n trên m t giây t i tr m
g c. Trong ch ng trình mô ph ng, s l ng gói tin trên m t giây thay đ i
tùy thu c vào s l ng c a nút c m bi n t 20 đ n 240 nút. Trong hình 4.3
là k t qu mô ph ng so sánh gi a ba giao th c (s d ng tr m g c
đ ng/t nh và giao th c đ nh tuy n QoS hi u qu n ng l ng cho m ng
WSN theo d ng phân c m).


22

Hình 4.3: L u l

ng m ng so sánh gi a ba giao th c

K t qu cho th y r ng giao th c đ nh tuy n QoS hi u qu n ng l ng
cho m ng WSN theo d ng phân c m có k t qu t t h n hai giao th c còn
l i v l u l ng m ng. Trong giao th c ch s d ng tr m g c t nh, các nút
g n tr m g c duy trì và cùng ch u m t r i ro v l h ng n ng l ng và
v n đ đi m nóng nh nhau. V n đ này đ c gi i quy t trong giao th c

QoS hi u qu n ng l ng cho m ng WSN theo d ng phân c m luôn luôn
th p h n so v i giao th c ch s d ng tr m g c đ ng ho c tr m g c t nh.


24

K T LU N VÀ KI N NGH
Giao th c đ nh tuy n QoS hi u qu n ng l ng cho m ng c m bi n
không dây theo d ng phân c m là giao th c đ nh tuy n s d ng đ ng th i
tr m g c đ ng và tr m g c t nh. K t qu mô ph ng cho th y giao th c
đ nh tuy n này giúp ti t ki m đ c ngu n n ng l ng đáng k và t ng th i
gian s ng c a m ng. S d ng k t h p tr m g c đ ng và t nh c ng nh
cách xây d ng các c ch u tiên d a trên n i dung và phân lo i gói tin
trong giao th c đ nh tuy n QoS hi u qu n ng l ng cho m ng c m bi n
không dây giúp cho các nút c m bi n phân b n ng l ng c a chúng các
tr ng thái cân b ng h n, giúp gi m đ c đ tr và cung c p ch t l ng
d ch v m ng đ ng đ u h n cho t t c các lo i gói tin đ c truy n nh n.
K t qu mô ph ng c ng cho th y r ng, giao th c đ nh tuy n này giúp c i
thi n t t h n các tham s ch t l ng d ch v m ng nh đ tr trung bình,
t l m t gói tin, l u l ng đ ng truy n khi so sánh v i h ng ti p c n
ch s d ng tr m g c đ ng ho c t nh.
Trong t ng lai, m t h ng m r ng vi c nghiên c u này có th
đ c xem xét t i đó là vi c b sung các tham s khác vào mô ph ng nh
dung sai m c đ nh (fault tolerance) hay tác đ ng c a vi c t h p d li u.
Hi u qu n ng l ng c ng có th đ c c i thi n khi xem xét đ n khái ni m
di đ ng gi i h n c a các nút c m bi n. M t s các mô ph ng khác c ng có
th đ c xây d ng đ đánh giá hi u qu c a giao th c đ nh tuy n QoS hi u
qu n ng l ng trong m ng c m bi n không dây s d ng tr m g c đ ng
các mô hình di đ ng khác.