VẤN ĐỀ NĂNG LƯỢNG TRONG MẠNG WIRELESS SENSON VÀ ĐÁNH GIÁ BẰNG MÔ PHỎNG.doc

Môc lôc

Môc lôc ...................................................................................................................... 1

ThuËt ng÷ viÕt t¾t ....................................................................................................... 4

Lêi nãi ®Çu ................................................................................................................ 6

Ch ¬ng I : Tæng quan vÒ m¹ng Wireless Sensor ....................................................... 7

1.1. Giíi thiÖu m¹ng c¶m biÕn kh«ng d©y ........................................................... 7

1.2. NÒn t¶ng ph¸t triÓn m¹ng ............................................................................... 7

1.2.1. M¹ng Ad hoc kh«ng d©y ........................................................................ 7

1.2.2. NÒn t¶ng c«ng nghÖ ............................................................................. 10

1.3. M« t¶ hÖ thèng ............................................................................................. 12

1.3.1. M« t¶ hÖ thèng tæng qu¸t ...................................................................... 12

1.3.2. HÖ thèng WISENET ............................................................................. 13

1.4. Tæng quan vÒ kiÕn tróc m¹ng ....................................................................... 17

1.4.1. Líp øng dông ........................................................................................ 18

1.4.1.1. Giao thøc qu¶n lý Sensor ..................................................................... 18

1.4.1.2. Giao thøc ph©n nhiÖm vô vµ qu¶ng c¸o sè liÖu ................................... 19

1.4.1.3 Giao thøc truy vÊn Sensor vµ phæ biÕn sè liÖu ..................................... 19

1.4.2 Líp giao vËn .......................................................................................... 20

1.4.3 Líp m¹ng ............................................................................................... 21

1.4.4. Liªn kÕt liªn m¹ng ................................................................................ 21

1.4.5 Líp liªn kÕt sè liÖu ............................................................................... 22

1.4.5.1 §iÒu khiÓn truy nhËp m«i tr êng truyÒn dÉn ......................................... 22

1.4.5.2 §iÒu khiÓn söa lçi ................................................................................. 23

1.4.6 Líp vËt lý ............................................................................................... 24

1.5. §Æc ®iÓm cña m¹ng Wireless Sensor ........................................................... 25

1.5.1. KÝch th íc vËt lý nhá vµ tiªu thô c«ng suÊt thÊp .................................... 25

1.5.2. Ho¹t ®éng ®ång thêi víi ®é tËp trung cao ............................................ 26

1.5.3. Kh¶ n¨ng liªn kÕt vËt lý vµ ph©n cÊp ®iÒu khiÓn h¹n chÕ ..................... 26

1.5.4. TÝnh ®a d¹ng trong thiÕt kÕ vµ sö dông ................................................. 26

1.5.5. Ho¹t ®éng tin cËy .................................................................................. 27

1.6. øng dông cña m¹ng Sensor .......................................................................... 27

1.6.1. øng dông trong qu©n sù ........................................................................ 27

1.6.2. øng dông vÒ m«i tr êng ......................................................................... 29

1.6.3. øng dông trong y tÕ ............................................................................... 30

1.6.4. øng dông trong gia ®×nh ....................................................................... 30

1.6.5. C¸c øng dông th ¬ng m¹i kh¸c .............................................................. 31

Ch ¬ng II : N¨ng l îng trong m¹ng Wireless Sensor ............................................... 33

2.1. TÝnh ®Æc thï cña m¹ng ................................................................................. 33

2.1.1. H¹n chÕ phÇn cøng ................................................................................ 33

2.1.2. M«i tr êng ho¹t ®éng ............................................................................. 34

2.1.3. M«i tr êng truyÒn dÉn ............................................................................ 35

2.2. Sù tiªu thô n¨ng l îng ................................................................................... 36

2.2.1. N¨ng l îng cho nhiÖm vô c¶m biÕn ....................................................... 37

2.2.2. N¨ng l îng cho truyÒn th«ng ................................................................. 37

Phan ViÕt Thêi, D2001VT 1

2.2.3. N¨ng l îng cho xö lý .............................................................................. 38

2.3. C¸c gi¶i ph¸p tiÕt kiÖm n¨ng l îng ............................................................... 38

2.3.1. Gi¶i ph¸p ®Þnh tuyÕn ............................................................................. 38

2.3.1.1. C¸c ph ¬ng ph¸p ®Þnh tuyÕn tèi u vÒ n¨ng l îng .................................... 39

2.3.1.2. Ph ¬ng ph¸p ®Þnh tuyÕn sè liÖu tËp trung ............................................. 40

2.3.1.3. C¸c giao thøc líp m¹ng kh¸c ® îc ®Ò xuÊt cho m¹ng Sensor ................ 41

2.3.2. Gi¶i ph¸p truy nhËp m«i tr êng truyÒn dÉn ............................................ 46

2.3.2.1. Yªu cÇu víi giao thøc ®iÒu khiÓn truy nhËp m«i tr êng (MAC) cho

m¹ng sensor ..................................................................................................... 46

2.3.2.2. C¸c giao thøc MAC cho m¹ng sensor .................................................. 47

2.3.2.3. C¸c chÕ ®é ho¹t ®éng tiÕt kiÖm n¨ng l îng .......................................... 49

2.3.3. Qu¶n lý nguån c«ng suÊt ...................................................................... 50

2.3.3.1 Thêi gian tån t¹i .................................................................................. 51

2.3.3.2 Ph¸t hiÖn nguån thÊp "Low Battery" ................................................... 51

2.3.3.3. C¶nh b¸o "Low Battery" ..................................................................... 52

2.3.4. TËn dông c¸c nguån n¨ng l îng trong tù nhiªn ..................................... 53

2.3.1.1. TÕ bµo quang ®iÖn ............................................................................... 54

2.3.1.2. C¸c nguån n¨ng l îng kh¸c .................................................................. 55

Ch ¬ng III : PhÇn mÒm m« pháng n¨ng l îng cho m¹ng Wireless Sensor ............... 56

3.1. M« h×nh ho¸ m« pháng ................................................................................ 56

3.1. M« h×nh nguån n¨ng l îng ............................................................................ 56

3.3. ThiÕt kÕ phÇn mÒm m« pháng m¹ng Wireless Sensor ................................. 57

3.3.1. PhÇn mÒm NS-2 .................................................................................... 57

3.3.2. C¬ së ph¸t triÓn m« pháng m¹ng Sensor trªn nÒn NS-2 ....................... 60

3.3.3. C¸c ®Þnh d¹ng míi trong NS-2 ............................................................. 61

3.3.4. Thay ®æi trong NS-2 ............................................................................. 63

3.4. ThiÕt lËp m· lËp tr×nh m« pháng .................................................................. 65

3.4.1. ThiÕt lËp kªnh hiÖn t îng vµ kªnh d÷ liÖu ............................................. 65

3.4.2. ThiÕt lËp mét giao thøc MAC cho kªnh Phenomenon ......................... 65

3.4.3. ThiÕt lËp c¸c nót Phenomenon víi giao thøc "®Þnh tuyÕn" Phenom ... 65

3.4.4. ThiÕt lËp tèc ®é vµ kiÓu xung cña Phenomenon ................................... 66

3.4.5. §Þnh h×nh nót Sensor ............................................................................ 67

3.4.6. ThiÕt lËp c¸c nót Non-Sensor (®iÓm thu thËp d÷ liÖu, Gateway) .......... 68

3.4.7. G¾n kÕt c¸c t¸c nh©n Sensor ................................................................. 69

3.4.8. G¾n kÕt mét t¸c nh©n UDP vµ øng dông Sensor cho mçi nót ............. 69

3.4.9. Khëi ®éng øng dông Sensor .................................................................. 69

Ch ¬ng IV: M« pháng m¹ng Wireless Sensor ......................................................... 70

4.1. Môc ®Ýnh m« pháng ..................................................................................... 70

4.2. Thùc hiÖn m« pháng .................................................................................... 71

4.2.1. M· ch ¬ng tr×nh ..................................................................................... 71

4.2.1. Ph©n tÝch kÕt qu¶ ................................................................................... 72

4.2. KÕt qu¶ ......................................................................................................... 73

4.2.1. Sù tæn hao n¨ng l îng ............................................................................. 74

4.2.2. Tèc ®é gi¶m n¨ng l îng khi t¨ng sè nót m¹ng ...................................... 76

4.2.3. Tèc ®é gi¶m n¨ng l îng khi mËt ®é m¹ng kh«ng ®æi ............................ 77

4.2. §¸nh gi¸ ....................................................................................................... 78

Phan ViÕt Thêi, D2001VT 2

KÕt luËn ................................................................................................................... 79

Tµi liÖu tham kh¶o .................................................................................................. 80

Phan ViÕt Thêi, D2001VT 3

§å ¸n tèt nghiÖp ®¹i häc

ThuËt ng÷ viÕt t¾t

Tõ viÕt t¾t NghÜa tiÕng Anh NghÜa tiÕng ViÖt

ADC Analogue/Digital converter Bé chuyÓn ®æi t¬ng tù / sè

AODV Ad Hoc On-Demand Distance￾Vector

§Þnh tuyÕn dùa vµo chuçi chØ híng

theo yªu cÇu t¹m thêi

API Application program interface HÖ giao tiÕp lËp tr×nh øng dông

ARC Adaptive transmitssion rate

control

§iÒu khiÓn tèc ®é truyÒn dÉn thÝch øng

ARQ automatic repeat request C¬ chÕ söa lçi b»ng yªu cÇu lÆp l¹i tù

®éng

BER Bit error rate Tû lÖ lçi bit

CSMA Carrier sense multiple access §a truy nhËp theo c¶m biÕn lu lîng

DSDV Destination-Sequenced

Distance-Vector

§Þnh tuyÕn theo chuçi chØ híng víi

®Ých tuÇn tù

DSR Dynamic Source Routing Giao thøc ®Þnh tuyÕn nguån ®éng

FDMA Frequency division multiple

access

§a truy nhËp ph©n chia theo tÇn sè

FEC Forward error correction C¬ chÕ söa lçi tríc

GPS Global Possition System HÖ thèng ®Þnh vÞ toµn cÇu

HTTP HyperText Tranffer Protocol Giao thøc truyÒn siªu v¨n b¶n

ISM band Industrial, Scientific and

Medical band

D¶i tÇn sö dông cho c¸c øng dông c«ng

nghiÖp, khoa häc vµ y häc

LEACH Low energy adaptive clustering

hierarchy

Ph©n cÊp côm thÝch øng víi n¨ng lîng

thÊp

MAC Medium access control §iÒu khiÓn truy nhËp m«i trêng truyÒn

dÉn

MANET Mobile ad hoc network M¹ng di ®éng ad hoc (t¹m thêi, kh«ng

cã c¬ së h¹ tÇng)

ME Minimum energy N¨ng lîng tiªu thô cùc tiÓu

MECN Minimum energy

communication network

M¹ng truyÒn th«ng víi n¨ng lîng cùc

tiÓu

MH Minimum hop Sè bíc nh¶y cùc tiÓu

NAM Network AniMator M« t¶ m¹ng b»ng h×nh ¶nh ®éng

NS-2 Network Simulator version 2 PhÇn mÒm m« pháng m¹ng phiªn b¶n2

Otcl Object-oriented tool command

language

Ng«n ng÷ ®iÒu khiÓn b»ng lÖnh híng

®èi tîng

PA Power available Møc n¨ng lîng hiÖn t¹i

QoS Quality of service ChÊt lîng dÞch vô

REQ Request message B¶n tin yªu cÇu

RERR Route error packet Gãi b¸o lçi tuyÕn

RREP Route reply packet Gãi ®¸p øng yªu cÇu tuyÕn

RREQ Route request packet Gãi yªu cÇu tuyÕn

RS-232 Serial Radio Link - 232 Liªn kÕt v« tuyÕn nèi tiÕp theo chuÈn

Phan ViÕt Thêi, D2001VT 4

§å ¸n tèt nghiÖp ®¹i häc

RS-232

SAR Sequential assignment routing §Þnh tuyÕn chØ ®Þnh liªn tôc

SMECN Small minimum energy

communication network

M¹ng truyÒn th«ng víi n¨ng lîng cùc

tiÓu lo¹i nhá

SMACS Self Organizing MAC for

Sensor network

Giao thøc MAC tù tæ chøc cho m¹ng

sensor

SMP Sensor management protocol Giao thøc qu¶n lý sensor

SPIN Sensor protocols for

information via negotiation

C¸c giao thøc th«ng tin sensor th«ng

qua tháa thuËn

SQDDP Sensor query and data

dissemination protocol

Giao thøc truy vÊn sensor vµ phæ biÕn

sè liÖu

SQL Structure Query Language Ng«n ng÷ truy vÊn theo cÊu tróc

SQTL Sensor query and tasking

language

Ng«n ng÷ truy vÊn vµ ®Æt nhiÖm vô

sensor

SSF Scalable Simulation Framework C¬ cÊu m« pháng më réng

TADAP Task assignment and data

advertisement protocol

Giao thøc ph©n nhiÖm vô vµ qu¶ng c¸o

sè liÖu

TCP/IP Transmission Control

Protocol/Internet Protocol

Giao thøc ®iÒu khiÓn truyÒn dÉn/giao

thøc Internet

TDMA Time division multiple access §a truy nhËp ph©n chia theo thêi gian

TORA Temporally Ordered Routing

Algorithm

§Þnh tuyÕn b»ng thuËt to¸n t×m ®êng

tuÇn tù theo thêi gian

WINS Wireless Integrated network

sensors

M¹ng c¸c thiÕt bÞ c¶m biÕn tÝch hîp

thiÕt bÞ thu ph¸t kh«ng d©y

WISENET WIreless SEnsor NETwork HÖ thèng m¹ng sensor kh«ng d©y

WISENET

WLAN Wireless local area network M¹ng côc bé kh«ng d©y

WSN Wireless sensor network M¹ng c¶m biÕn kh«ng d©y

Phan ViÕt Thêi, D2001VT 5

§å ¸n tèt nghiÖp ®¹i häc

Lêi nãi ®Çu

Trong nh÷ng n¨m gÇn ®©y sù ph¸t triÓn m¹nh mÏ cña c«ng nghÖ th«ng tin, c«ng

nghÖ vi m¹ch ®iÖn tö vµ viÔn th«ng ®Æc biÖt lµ trong lÜnh vùc v« tuyÕn ®· ®em l¹i nhiÒu

øng dông míi, cho phÐp chóng ta cã thÓ dÔ dµng thu thËp th«ng tin ë bÊt kú ®iÒu kiÖn

vµ vïng ®Þa lý nµo. Cã nhiÒu ph¬ng ph¸p kh¸c nhau cho phÐp chóng ta thu thËp th«ng

tin trong ®ã m¹ng Wireless Sensor hiÖn ®ang ®îc dïng phæ biÕn trªn thÕ giíi vµ ®ang

dÇn x©m nhËp vµo níc ta.

Cã nhiÒu vÊn ®Ò ®Æt ra cho m¹ng Wireless Sensor nh vÊn ®Ò n¨ng lîng, vÊn ®Ò ®ång

bé sensor, vÊn ®Ò më réng m¹ng... N¨ng lîng lu«n lµ yÕu tè quan träng cña tÊt c¶ c¸c

lo¹i m¹ng. Víi m¹ng Wireless Sensor do tÝnh ®Æc thï cña m¹ng lµ h¹n chÕ vÒ phÇn

cøng vµ øng dông ë nhiÒu vïng ®Þa lÝ phøc t¹p nªn vÊn ®Ò n¨ng lîng cµng trë lªn quan

träng.

Tríc thùc tÕ nµy, ®îc sù ®Þnh híng vµ chØ dÉn cña TiÕn sÜ §inh V¨n Dòng, phßng

Nghiªn cøu Ph¸t triÓn DÞch vô míi vµ Tù ®éng hãa, ViÖn Khoa häc Kü thuËt Bu §iÖn,

em ®· chän ®Ò tµi ®å ¸n: “VÊn ®Ò n¨ng lîng trong m¹ng Wireless Sensor vµ ®¸nh gi¸

b»ng m« pháng”.

Môc ®Ých cña ®å ¸n nµy lµ t×m hiÓu c¸c vÊn ®Ò liªn quan tíi n¨ng lîng trong m¹ng

Wireless Sensor, tõ ®ã ®a ra c¸c gi¶i ph¸p tiÕt kiÖm n¨ng lîng trong m¹ng vµ tËn dông

c¸c nguån n¨ng lîng s¹ch trong tù nhiªn.

§å ¸n gåm 4 ch¬ng:

1 - Ch¬ng I : Tæng quan vÒ m¹ng Wireless Sensor

2 - Ch¬ng II : N¨ng lîng trong m¹ng Wireless Sensor

3 - Ch¬ng III : PhÇn mÒm m« pháng cho m¹ng Wireless Sensor

4 - Ch¬ng IV: M« pháng m¹ng Wireless Sensor

Do cßn h¹n chÕ vÒ kiÕn thøc vµ n¨ng lùc nªn ®å ¸n kh«ng tr¸nh khái thiÕu sãt.

Mong ®îc sù gãp ý cña thÇy c« vµ b¹n bÌ.

Em xin ch©n thµnh c¶m ¬n thÇy gi¸o TS. §inh V¨n Dòng, phßng Nghiªn cøu Ph¸t

triÓn DÞch vô míi vµ Tù ®éng hãa, ViÖn Khoa häc Kü thuËt Bu §iÖn, ®· híng dÉn em

vÒ chuyªn m«n còng nh ph¬ng ph¸p lµm viÖc ®Ó em cã thÓ hoµn thµnh ®å ¸n. Qua ®©y,

em còng xin göi lêi c¶m ¬n ch©n thµnh tíi c¸c thÇy, c¸c c« trong Khoa ViÔn Th«ng I,

Häc viÖn C«ng nghÖ Bu chÝnh - ViÔn th«ng ®· gióp ®ì, t¹o ®iÒu kiÖn cho em hoµn

thµnh ®å ¸n nµy.

Hµ Néi ngµy 31 th¸ng 10 n¨m 2005

Sinh viªn

Phan ViÕt Thêi

Phan ViÕt Thêi, D2001VT 6

§å ¸n tèt nghiÖp ®¹i häc Ch¬ng I. Tæng quan vÒ m¹ng Wireless Sensor

Ch¬ng I : Tæng quan vÒ m¹ng Wireless Sensor

1.1. Giíi thiÖu m¹ng c¶m biÕn kh«ng d©y

C¸c thiÕt bÞ c¶m biÕn (Sensor) ®îc kÕt nèi thµnh m¹ng, phèi hîp víi nhau ®Ó thùc

hiÖn c¸c nhiÖm vô víi quy m« lín, ®îc ®Æt nhiÒu hy väng nh»m c¸ch m¹ng hãa trong

lÜnh vùc thu thËp th«ng tin ë bÊt k× ®iÒu kiÖn vµ vïng ®Þa lý nµo. M¹ng c¶m biÕn kh«ng

d©y (Wireless Sensor Network) bao gåm mét tËp hîp c¸c thiÕt bÞ c¶m biÕn sö dông c¸c

liªn kÕt kh«ng d©y (v« tuyÕn, hång ngo¹i hoÆc quang häc) ®Ó phèi hîp thùc hiÖn c¸c

nhiÖm vô c¶m biÕn ph©n t¸n vÒ ®èi tîng môc tiªu. M¹ng nµy cã thÓ liªn kÕt trùc tiÕp

víi nót qu¶n lý cña gi¸m s¸t viªn hay gi¸n tiÕp th«ng qua mét ®iÓm thu (Sink) vµ m«i

trêng m¹ng c«ng céng nh Internet hay vÖ tinh. C¸c nót Sensor kh«ng d©y cã thÓ ®îc

triÓn khai cho c¸c môc ®Ých chuyªn dông nh gi¸m s¸t vµ an ninh; kiÓm tra m«i trêng;

t¹o ra kh«ng gian th«ng minh; kh¶o s¸t, chÝnh x¸c hãa trong n«ng nghiÖp; y tÕ;... Lîi

thÕ chñ yÕu cña chóng lµ kh¶ n¨ng triÓn khai hÇu nh trong bÊt k× lo¹i h×nh ®Þa lý nµo kÓ

c¶ c¸c m«i trêng nguy hiÓm kh«ng thÓ sö dông m¹ng Sensor cã d©y truyÒn thèng ®îc.

ViÖc kÕt hîp c¸c bé c¶m biÕn thµnh m¹ng líi ngµy nay ®· t¹o ra nhiÒu kh¶ n¨ng míi

cho con ngêi. C¸c bé vi c¶m biÕn víi bé xö lý g¾n trong vµ c¸c thiÕt bÞ v« tuyÕn hoµn

toµn cã thÓ g¾n trong mét kÝch thíc rÊt nhá. Chóng cã thÓ ho¹t ®éng trong mét m«i tr￾êng dµy ®Æc víi kh¶ n¨ng xö lý tèc ®é cao. Do ®ã, víi m¹ng c¶m biÕn kh«ng d©y ngµy

nay, ngêi ta ®· cã thÓ kh¸m ph¸ nhiÒu hiÖn tîng rÊt khã thÊy tríc ®©y.

Ngµy nay, c¸c m¹ng c¶m biÕn kh«ng d©y ®îc øng dông trong nhiÒu lÜnh vùc nh c¸c

cÊu tróc chèng l¹i ®Þa chÊn, nghiªn cøu vi sinh vËt biÓn, gi¸m s¸t viÖc chuyªn chë c¸c

chÊt g©y « nhiÔm, kiÓm tra hÖ sinh th¸i vµ m«i trêng sinh vËt phøc t¹p...

1.2. NÒn t¶ng ph¸t triÓn m¹ng

ViÖc ph¸t triÓn m¹ng Wireless Sensor dùa trªn c«ng nghÖ m¹ng Ad hoc kh«ng d©y vµ

®îc thóc ®Èy bëi hai yÕu tè lµ nhu cÇu øng dông vµ c¸c tiÕn bé c«ng nghÖ.

1.2.1. M¹ng Ad hoc kh«ng d©y

M¹ng Ad hoc kh«ng d©y lµ kiÓu m¹ng kh«ng cã c¬ së h¹ tÇng nÒn t¶ng, ®îc triÓn

khai cho c¸c môc ®Ých sö dông t¹m thêi cÇn thiÕt lËp nhanh chãng, thuËn tiÖn nh ®Ó t×m

kiÕm vµ cøu hé, phôc vô liªn l¹c cho c¸c thµnh viªn trong mét cuéc häp,.v.v. M¹ng Ad

hoc kh«ng cÇn c¸c thµnh phÇn c¬ së h¹ tÇng nh tæng ®µi, tr¹m thu ph¸t gèc hay bÊt k×

mét trung t©m ®iÒu khiÓn nµo. TÊt c¶ c¸c nót di ®éng trong m¹ng Ad hoc ®îc liªn kÕt

®éng víi nhau mét c¸ch tuú ý, kh«ng cã bÊt k× sù ®iÒu khiÓn nµo tõ bªn ngoµi. TÊt c¶

Phan ViÕt Thêi, D2001VT 7

§å ¸n tèt nghiÖp ®¹i häc Ch¬ng I. Tæng quan vÒ m¹ng Wireless Sensor

c¸c nót nµy ®Òu cã thÓ ho¹t ®éng nh mét bé ®Þnh tuyÕn nhê kh¶ n¨ng t×m vµ duy tr×

tuyÕn tíi c¸c nót kh¸c trong m¹ng. C¸c giao thøc ®Þnh tuyÕn trong m¹ng Ad hoc cã thÓ

chia thµnh hai lo¹i:

- C¸c giao thøc ®Þnh tuyÕn theo b¶ng: mçi nót m¹ng sÏ duy tr× vµ cËp nhËt th«ng tin

®Þnh tuyÕn tíi mäi nót m¹ng kh¸c.

- C¸c giao thøc ®Þnh tuyÕn theo yªu cÇu: ViÖc ®Þnh tuyÕn chØ ®îc thùc hiÖn khi cã yªu

cÇu chuyÓn gãi, nhê c¬ chÕ t×m ®êng.

HiÖn nay cã bèn giao thøc ®Þnh tuyÕn ®îc sö dông trong m¹ng Ad hoc:

a) §Þnh tuyÕn theo chuçi chØ híng víi ®Ých tuÇn tù

Trong §Þnh tuyÕn theo chuçi chØ híng víi ®Ých tuÇn tù (Destination-Sequenced

Distance-Vector - DSDV), mäi tr¹m di ®éng ®Òu cã mét b¶ng ®Þnh tuyÕn trong ®ã ghi

c¸c ®Ých hiÖn t¹i, sè c¸c bíc nh¶y ®Ó ®Õn ®îc ®Ých vµ sè thø tù ®îc g¸n cho nót ®Ých. Sè

thø tù nµy ®îc sö dông ®Ó ph©n biÖt c¸c tuyÕn vµ nh vËy tr¸nh ®îc sù h×nh thµnh c¸c

vßng lÆp. C¸c tr¹m ®Þnh kú göi b¶ng ®Þnh tuyÕn cña nã cho c¸c nót l©n cËn cña nã. Mét

tr¹m còng göi b¶ng ®Þnh tuyÕn nÕu mét thay ®æi ®¸ng kÓ trong b¶ng so víi lÇn göi cËp

nhËt cuèi cïng ®îc ph¸t hiÖn. Nh vËy, viÖc cËp nhËt ®îc thùc hiÖn c¶ theo thêi gian vµ

theo sù kiÖn.

C¸c b¶ng ®Þnh tuyÕn cã thÓ ®îc göi cËp nhËt theo hai c¸ch: chuyÓn toµn bé (“full

dump”) hay cËp nhËt phÇn gia t¨ng. Theo c¸ch chuyÓn toµn bé, b¶ng ®Þnh tuyÕn sÏ ®îc

göi trän vÑn ®Õn c¸c nót l©n cËn vµ nã cã thÓ bao gåm nhiÒu gãi tin. Ngîc l¹i, theo

c¸ch cËp nhËt phÇn gia t¨ng, chØ nh÷ng môc ghi míi cña b¶ng ®Þnh tuyÕn so víi lÇn cËp

nhËt cuèi cïng míi ®îc göi ®i vµ ph¶i võa trong mét gãi tin. Khi m¹ng t¬ng ®èi æn

®Þnh, c¸c gãi cËp nhËt phÇn gia t¨ng ®îc sö dông ®Ó tr¸nh viÖc lu lîng t¨ng cao vµ viÖc

chuyÓn toµn bé (full dump) Ýt ®îc sö dông h¬n. Trong c¸c m¹ng thay ®æi nhanh, sè l￾îng c¸c gãi cËp nhËt phÇn gia t¨ng cã thÓ trë lªn rÊt lín nªn viÖc chuyÓn toµn bé b¶ng

®îc thùc hiÖn thêng xuyªn h¬n.

b) §Þnh tuyÕn b»ng thuËt to¸n t×m ®êng tuÇn tù theo thêi gian

§Þnh tuyÕn b»ng thuËt to¸n t×m ®êng tuÇn tù theo thêi gian (Temporally Ordered

Routing Algorithm - TORA) lµ mét giao thøc ®Þnh tuyÕn trªn c¬ së mét thuËt to¸n

“®¶o liªn kÕt” (“Link Reversal”). Nã ®îc thiÕt kÕ ®Ó t×m c¸c tuyÕn ®êng theo yªu cÇu,

cung cÊp nhiÒu tuyÕn tíi mét ®Ých, thiÕt lËp tuyÕn nhanh vµ gi¶m tíi møc tèi thiÓu

phÇn phô t¶i (overhead) b»ng thuËt to¸n khoanh vïng chèng l¹i c¸c thay ®æi vÒ h×nh

tr¹ng m¹ng cã thÓ s¶y ra. ViÖc tèi u ®Þnh tuyÕn (t×m ®êng ng¾n nhÊt) ®îc coi lµ thø yÕu

Phan ViÕt Thêi, D2001VT 8