Khóa luận Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong manet
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Phạm Văn Tứ
KHẢO SÁT ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG
CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ
GIAO THỨC ĐỊNH TUYẾN TRONG MANET
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Phạm Văn Tứ
KHẢO SÁT ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG
CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ
GIAO THỨC ĐỊNH TUYẾN TRONG MANET
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: PGS.TS. Nguyễn Đình Việt
Cán bộ đồng hướng dẫn: Ths. Đoàn Minh Phương
HÀ NỘI - 2010
TÓM TẮT
Ngày nay, cùng với sự bùng nổ, phát triển mạnh mẽ của các thiết bị di động cá
nhân như: laptop, smartphone, tablet,…, thì nhu cầu kết nối giữa các thiết bị này cũng
ngày càng đòi hỏi cao hơn về tốc độ và khả năng di chuyển trong khi kết nối. Mạng di
động đặc biệt – MANET (Mobile Ad-hoc Network) là một trong những công nghệ
vượt trội đáp ứng nhu cầu kết nối đó nhờ khả năng hoạt động không phụ thuộc vào cơ
sở hạ tầng mạng cố định, với chi phí hoạt động thấp, triển khai nhanh và có tính di
động cao. Tuy nhiên, hiện nay mạng MANET vẫn chưa được ứng dụng rộng rãi và
đang được thúc đẩy nghiên cứu nhằm cải tiến hơn nữa các giao thức định tuyến để
mạng đạt được hiệu quả hoạt động tốt hơn. Khóa luận nghiên cứu ảnh hưởng của sự
chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong mạng
MANET. Bằng những kiểm chứng thông qua mô phỏng, khóa luận đưa ra các nhận
xét, đánh giá về hiệu suất mạng đối với từng giao thức định tuyến cụ thể khi các nút
mạng chuyển động với tốc độ và hướng đi thay đổi.
MỤC LỤC
TÓM TẮT ...............................................................................................................................
DANH MỤC HÌNH VẼ...........................................................................................................
DANH MỤC BẢNG................................................................................................................
BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT ...............................................................................
LỜI CẢM ƠN..........................................................................................................................
Chương 1. GIỚI THIỆU ........................................................................................................ 1
1.1. Sự ra đời và phát triển của các mạng không dây .......................................................... 1
1.2. Mục tiêu nghiên cứu của khóa luận.............................................................................. 4
1.3. Công cụ nghiên cứu chính – NS-2 ............................................................................... 5
1.3.1. Giới thiệu về NS-2................................................................................................ 5
1.3.2. Khả năng mô phỏng của NS-2 .............................................................................. 7
1.4. Tổ chức của KLTN......................................................................................................8
Chương 2. GIAO THỨC MAC CỦA MẠNG LAN VÀ WLAN ............................................ 9
2.1. Mạng LAN và mạng WLAN ....................................................................................... 9
2.2. Chuẩn 802.3 và giao thức CSMA/CD........................................................................ 10
2.3. Chuẩn 802.11 và giao thức CSMA/CA...................................................................... 12
Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN .............................................. 15
3.1. Mạng MANET .......................................................................................................... 15
3.1.1. Lịch sử phát triển và các ứng dụng...................................................................... 15
3.1.2. Các đặc điểm chính của mạng MANET.............................................................. 16
3.2. Vấn đề định tuyến trong mạng MANET .................................................................... 17
3.2.1 Các thuật toán định tuyến truyền thống................................................................ 17
3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANET......................... 18
3.2.3. Phân loại các kỹ thuật định tuyến........................................................................ 19
3.2.3.1. Link state và Distance Vector....................................................................... 19
3.2.3.2. Định tuyến chủ ứng và phản ứng.................................................................. 20
3.2.3.3. Định tuyến nguồn và định tuyến theo chặng................................................. 21
3.3. Các giao thức định tuyến chính trong mạng MANET ................................................ 22
3.3.1. DSDV................................................................................................................. 22
3.3.2 OLSR [8]............................................................................................................. 23
3.3.3. AODV [12]......................................................................................................... 25
3.3.4. DSR [7].............................................................................................................. 27
3.3.5. TORA [11] ......................................................................................................... 28
Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG
CỦA CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN 30
4.1. Xác định các tham số hiệu suất cần đánh giá và cách thức phân tích kết quả mô phỏng
........................................................................................................................................ 30
4.1.1. Các tham số hiệu suất cần đánh giá..................................................................... 30
4.1.2. Cách thức phân tích kết quả mô phỏng của NS-2 ................................................ 30
4.1.2.1. Cấu trúc tệp vết............................................................................................ 30
4.1.2. Công cụ để phân tích và biểu diễn kết quả mô phỏng.......................................... 33
4.1.2.1. Perl.............................................................................................................. 33
4.1.2.2. GNUPLOT .................................................................................................. 33
4.2. Thiết lập mạng mô phỏng MANET ........................................................................... 35
4.2.1. Thiết lập tô-pô mạng........................................................................................... 35
4.2.2. Thiết lập mô hình chuyển động của các nút mạng và thời gian mô phỏng ........... 36
4.2.2.1. Mô hình Random Waypoint ......................................................................... 37
4.2.2.2. Mô hình Random Walk................................................................................ 38
4.2.3 Thiết lập các nguồn sinh lưu lượng đưa vào mạng ............................................... 39
4.2.4. Lựa chọn thời gian mô phỏng ............................................................................. 40
4.3. Thực hiện mô phỏng các giao thức định tuyến........................................................... 40
4.3.1. Phân tích kết quả bằng công cụ perl.................................................................... 40
4.3.2. Sử dụng gnuplot để vẽ đồ thị .............................................................................. 44
4.4. Đánh giá ảnh hưởng của sự chuyển động của nút mạng đến hiệu suất của các giao thức
định tuyến ........................................................................................................................ 47
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................................ 49
TÀI LIỆU THAM KHẢO.................................................................................................... 51
PHỤ LỤC............................................................................................................................ 53
1. Bảng các trường phụ thêm vào trong cấu trúc tệp vết phụ thuộc vào kiểu gói tin .......... 53
2. Mô phỏng mạng MANET............................................................................................. 56
3. Tỷ lệ phân phát gói tin thành công................................................................................ 58
4. Thời gian thiết lập kết nối............................................................................................. 59
DANH MỤC HÌNH VẼ
Hình 1: Sự phát triển của mạng không dây và di động............................................................ 1
Hình 2: Cấu trúc của NS-2 .....................................................................................................5
Hình 3: Luồng các sự kiện cho file Tcl chạy trong NS-2 ........................................................ 6
Hình 4: Chu trình hoạt động của giao thức CSMA/CD (bên gửi).......................................... 11
Hình 5: Chu trình hoạt động của giao thức CSMA/CA (bên gửi).......................................... 13
Hình 6: Hoạt động lắng nghe kênh truyền của giao thức CSMA/CA .................................... 14
Hình 7: Phân loại các giao thức định tuyến trong mạng MANET ......................................... 22
Hình 8: Tô-pô mạng thay đổi ............................................................................................... 23
Hình 9: Quy trình chuyển tiếp gói tin khi sử dụng kíp đa điểm – MPR................................. 24
Hình 10: OLSR ngăn chặn vòng lặp bằng việc sử dụng MPR để chuyển phát gói tin............ 25
Hình 11: quá trình khám phá tuyến trong AODV ................................................................. 25
Hình 12: Định tuyến nguồn động (DSR) .............................................................................. 27
Hình 13: Diện tích mạng mô phỏng và các nút mạng............................................................ 35
Hình 14: Di chuyển một nút theo mô hình Random Waypoint.............................................. 37
Hình 15: Di chuyển của 8 nút theo mô hình Random Walk .................................................. 38
Hình 16: Đồ thị tỷ lệ phân phát gói thành công – Random Waypoint.................................... 44
Hình 18: Đồ thị tỷ lệ phân phát gói tin thành công – Random Walk ..................................... 45
Hình 19: Đồ thị thời gian thiết lập kết nối trung bình_Random-Waypoint ............................ 46
Hình 20: Đồ thị thời gian thiết lập kết nối trung bình_Random-Walk................................... 46
DANH MỤC BẢNG
Bảng 1: Sự phát triển của chuẩn 802.3 ................................................................................. 10
Bảng 2: Sự phát triển của chuẩn 802.11 ............................................................................... 12
Bảng 3: Cấu trúc tệp vết....................................................................................................... 31
Bảng 4: Các trường thêm vào trong cấu trúc tệp vết phụ thuộc vào kiểu gói tin.................... 32
Bảng 5: Cấu hình mạng mô phỏng ....................................................................................... 36
Bảng 6: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Waypoint ................ 41
Bảng 7: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Walk....................... 42
Bảng 8: Thời gian thiết lập kết nối trung bình-Random_Waypoint ....................................... 43
Bảng 9: Thời gian thiết lập kết nối trung bình-Random_Walk.............................................. 43
Bảng 10: Tỷ lệ phân phát gói tin thành công - Random Waypoint ........................................ 44
Bảng 11: Tỷ lệ phân phát gói tin thành công – Random Walk .............................................. 45
BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT
AODV
Adhoc On-demand Distance
Vector
MANET Mobile Adhoc NETwork
CSMA/CA Carrier sense multiple access
with collision avoidance
MPR
Multi-Point Relays
CSMA/CD Carrier Sense Multiple Access NS-2
with Collision Detection
Network Simulator 2
DARPA
Defense Advanced Research
Projects Agency
OLSR
Optimized Link State
Routing Protocol
DSDV
Destination-Sequenced
Distance Vector
PRnet
Packet Radio Network
DSR
Dynamic Source Routing
RREP
RREQ
Route Reply
IEEE
Institute of Electrical and
Electronics Engineers
Route Request
LAN
Local Area Network
TORA
Temporally-Ordered
Routing Algorithm
MAC
Media Access Control
WLAN Wireless LAN
LỜI CẢM ƠN
Trước tiên, tôi xin gửi lời cảm ơn chân thành tới PGS.TS.Nguyễn Đình Việt,
người thầy đã tận tình giúp đỡ tôi trong suốt quá trình làm khóa luận. Tôi cũng xin gửi
lời cảm ơn tới Ths. Đoàn Minh Phương, người đã hướng dẫn tôi trong giai đoạn chuẩn
bị nhận đề tài.
Tôi xin gửi lời biết ơn sâu sắc tới thầy, cô trong trường Đại Học Công Nghệ, Đại
Học Quốc Gia Hà Nội. Thầy, cô đã dìu dắt, truyền lại cho chúng tôi không chỉ những
kiến thức chuyên ngành mà còn dạy bảo chúng tôi đạo làm người, rèn luyện cho chúng
tôi nghị lực, khát vọng vươn lên, phát huy khả năng tư duy sáng tạo trong mọi lĩnh
vực.
Cuối cùng, tôi xin được cảm ơn gia đình, bạn bè, những người thân yêu nhất của
tôi. Mọi người luôn ở bên cạnh tôi, động viên, khuyến khích tôi vươn lên trong cuộc
sống.
Hà nội, tháng 5 năm 2010
Phạm Văn Tứ
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Chương 1. GIỚI THIỆU
1.1. Sự ra đời và phát triển của các mạng không dây
Mạng không dây được đánh dấu mốc hình thành từ những năm 1887 khi
Heinrich Rudolf Hertz chứng minh được thuyết điện từ Maxwell thông qua thực
nghiệm. Từ đó đến nay các nhà nghiên cứu đã cho ra đời hàng loạt phát minh sáng chế
góp phần đưa công nghệ mạng không dây không ngừng cải tiến vượt trội về tốc độ
truyền nhận dữ liệu. Những năm gần đây nền công nghiệp không dây và di động tăng
trưởng mạnh mẽ cả về mặt công nghệ lẫn sự bùng nổ ngày càng nhiều các thiết bị di
động, hứa hẹn một kỷ nguyên truyền thông số nở rộ trên nền các mạng không dây và
di động. Sự phát triển này được minh họa trên Hình 1 dưới đây.
Hình 1: Sự phát triển của mạng không dây và di động
Phạm Văn Tứ
1
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Các mốc hình thành và phát triển của mạng không dây:
1887
1893
1895
Guglielmo Marconi:
Nikola Tesla truyền
thành công sóng radio.
Heinrich Rudolf Hertz
đã tạo ra được sóng điện
từ. Ông đã chứng minh
được thuyết Maxwell
thông qua thực nghiệm.
Lần đầu tiên trong lịch sử, 3
dấu chấm (tức chữ S trong
bảng ký tự Morse) đã được
truyền qua không gian với
khoảng cách 3km bằng
sóng điện từ.
1915
1931
1982 , 1991
Truyền thành công sóng
vô tuyến vượt Đại Tây
Dương từ Arlington
Virginia tới Pháp.
Sóng FM đã được phát
triển bởi Edwin H.
Armstrong và được sử
dụng rộng rãi để truyền
thông tin qua sóng vô
tuyến.
-1982: Hội nghị CEPT
đã thống nhất chọn
GSM để phát triển thành
tiêu chuẩn cho hệ thống
điện thoại di động có thể
được sử dụng trên khắp
châu Âu.
- 1991: Các mạng GSM
đầu tiên đã được đưa ra
bởi Radiolinja ở Phần
Lan với kỹ thuật bảo
dưỡng cơ sở hạ tầng
chung từ Ericsson.
Tháp Eiffel đã được sử
dụng để đặt anten thu tín
hiệu.
Phạm Văn Tứ
2
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
1997
1998, 1999
2001
Chuẩn IEEE 802.16 được
phát hành. Chuẩn này
được biết đến dưới cái tên
WIMAX.
Chuẩn IEEE 802.11
(WiFi) đã được tạo ra,
với tốc độ tối đa là
2Mb/s.
-1998: Công nghệ
Bluetooth đầu tiên
được phát triển bởi
Ericsson, sau đó được
chuẩn hoá bởi
Bluetooth Special
Interest Group (SIG).
- 1999: Chuẩn 802.11b
được phát hành cho tốc
độ tối đa lên 11Mb/s.
-20/5/1999: Chính
thức phát hành chuẩn
Bluetooth 1.0
2003
2004, 2009
2010
- Chuẩn 802.11g được
phát hành với tốc độ
tối đa lên tới 54 Mb/s.
*2004:
Liên minh Wi-Fi và
Gigabit không dây đã
đạt được thỏa thuận cho
phép Wi-Fi hoạt động ở
dải tần 60 Ghz nhằm cải
thiện tốc độ truyền dữ
liệu. Các chuẩn Wi-Fi
hiện đang hoạt động ở
dải tần từ 2.4 GHz đến 5
GHz.
- Phiên bản mới của
chuẩn 802.16 được bổ
sung, hoàn thiện chuẩn
WIMAX.
- Phát hành chuẩn
Bluetooth 2.0
- Bluetooth 1.2 được
công bố.
*2009:
- Chuẩn 802.11n được
phát hành cho phép tốc
độ truyên thông tối đa
lên tới 150 Mb/s.
Tốc độ Wi-Fi sẽ
tăng hơn 10 lần so với
tốc độ hiện tại
Phạm Văn Tứ
3
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
1.2. Mục tiêu nghiên cứu của khóa luận
Với đặc tính có thể hoạt động không phụ thuộc vào cơ sở hạ tầng mạng, triển
khai nhanh, linh hoạt ở mọi vị trí địa hình khác nhau, mạng MANET đang là tâm điểm
nghiên cứu đầy triển vọng, sẽ là công nghệ đột phá trong tương lai với nhiều ứng dụng
hữu ích vào cuộc sống, thí dụ kết nối mạng truyền thông cho các các vùng mới xảy ra
thiên tai hoặc ứng dụng cho lĩnh vực quân sự.
Khóa luận tập trung đi sâu nghiên cứu về mạng MANET, kết hợp phân tích trên
lý thuyết cùng thực nghiệm mô phỏng để tìm ra và đánh giá ảnh hưởng sự di động của
các nút mạng ở các mức độ khác nhau đến hiệu suất của một số giao thức định tuyến.
Nội dung cụ thể gồm:
Tìm hiểu sâu về mạng MANET, trong đó chủ yếu xem xét tới các giao thức
định tuyến.
Tìm hiểu sâu về các mô hình chuyển động của nút mạng trong MANET.
Xây dựng môi trường mô phỏng, đưa các giao thức định tuyến trong mạng
MANET vào mô phỏng thông qua NS-2.
Đánh giá ảnh hưởng sự chuyển động của các nút mạng đến hiệu suất của các
giao thức định tuyến DSDV, AODV và DSR bằng bộ mô phỏng mạng NS-2.
Từ đó đưa ra các nhận xét so sánh giữa ba giao thức.
Phạm Văn Tứ
4
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
1.3. Công cụ nghiên cứu chính – NS-2
1.3.1. Giới thiệu về NS-2
NS-2 là phần mềm mô phỏng mạng, hoạt động của nó được điều khiển bởi các
sự kiện rời rạc. NS-2 được thiết kế và phát triển theo kiểu hướng đối tượng, được phát
triển tại đại học California, Berkely. Bộ phần mềm này được viết bằng ngôn ngữ C++
và OTcl.
Hình 2: Cấu trúc của NS-2
Cấu trúc của NS-2 bao gồm các thành phần được chỉ ra trên Hình 2, chức năng của
chúng được mô tả như sau:
OTcl Script
Kịch bản OTcl
Simulation Program
OTcl
Chương trình Mô phòng
Bộ biên dịch Tcl mở rộng hướng đối tượng
Thư viện Mô phỏng NS
NS Simulation Library
Event Scheduler Objects
Network Component Objects
Các đối tượng Bộ lập lịch Sự kiện
Các đối tượng Thành phần Mạng
Network Setup Helping Modules Các mô đun Trợ giúp Thiết lập Mạng
Plumbling Modules
Simulation Results
Analysis
Các mô đun Plumbling
Các kết quả Mô phỏng
Phân tích
NAM Network Animator
Minh họa Mạng NAM
Phạm Văn Tứ
5
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Trong hình 2 trên, NS là Bộ biên dịch Tcl mở rộng hướng đối tượng; bao gồm
các đối tượng: Bộ lập lịch sự kiện, các đối tượng thành phần mạng và các mô đun trợ
giúp thiết lập mạng.
Để sử dụng NS-2, người dùng lập trình bằng ngôn ngữ kịch bản OTcl. Người
dùng có thể thêm các mã nguồn Otcl vào NS-2 bằng cách viết các lớp đối tượng mới
trong OTcl. Những lớp này khi đó sẽ được biên dịch cùng với mã nguồn gốc.
Kịch bản OTcl có thể thực hiện những việc sau: Khởi tạo Bộ lập lịch Sự kiện
Thiết lập Mô hình mạng dùng các đối tượng thành phần mạng Báo cho nguồn
traffic khi nào bắt đầu truyền và ngưng truyền packet trong Bộ lập lịch Sự kiện
Bộ lập lịch Sự kiện trong NS-2 thực hiện những việc sau: Tổ chức Bộ định thời mô
phỏng -- Huỷ các sự kiện trong hàng đợi sự kiện -- Triệu gọi các Thành phần mạng
trong mô phỏng.
Tùy vào mục đích của người dùng đối với kịch bản mô phỏng OTcl mà kết quả
mô phỏng có thể được lưu trữ vào tệp vết (trace file) với khuôn dạng (format) được
những người phát triển NS định nghĩa trước hoặc theo khuôn dạng do người sử dụng
NS quyết định khi viết kịch bản mô phỏng. Nội dung tệp vết sẽ được tải vào trong các
ứng dụng khác để thực hiện phân tích. NS đã định nghĩa 2 loại tệp vết:
Nam trace file (file.nam): Chứa các thông tin về tô-pô mạng như: các nút
mạng, đường truyền, vết các gói tin; dùng để minh họa trực quan mạng đã thiết
lập.
Trace file (file.tr): Tệp ghi lại vết của các sự kiện mô phỏng, tệp file dạng text,
có cấu trúc, dùng cho các công cụ lần vết và giám sát mô phỏng như: Gnuplot,
XGRAPH hay TRACEGRAPH.
Hình 3: Luồng các sự kiện cho file Tcl chạy trong NS-2
Phạm Văn Tứ
6
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
1.3.2. Khả năng mô phỏng của NS-2
NS-2 hỗ trợ mô phỏng tốt cho cả mạng có dây và mạng không dây. Bao gồm các
ưu điểm nổi bật sau:
Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại.
Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng.
Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi
được trong thực tế.
Khả năng mô phỏng nhiều loại mạng khác nhau.
Trong đó NS-2 có khả năng mô phỏng:
Các mô hình mạng: LAN, WLAN, di động, vệ tinh,...
Các giao thức mạng như: TCP, UDP...
Các dịch vụ nguồn lưu lượng như: FTP, CBR, VBR, Telnet, http...
Các kỹ thuật quản lý hàng đợi: Vào trước Ra trước (Drop Tail), Loại bỏ sớm
ngẫu nhiễn - RED (Random Early Drop) và Xếp hàng dựa trên sự phân lớp –
CBQ (Class-Based Queueing)...
Các thuật toán định tuyến như: Dijkstra, Distance Vector, Link State…
Các Chuẩn IEEE 802.11, IEEE 802.3,…
NS-2 cũng thực thi multicasting và vài giao thức lớp Điều khiển truy cập
đường truyền (MAC) đối với mô phỏng LAN.
Phạm Văn Tứ
7
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
1.4. Tổ chức của KLTN
Nội dung khóa luận bao gồm bốn chương như sau:
Chương 1: Giới thiệu về sự ra đời và phát triển của các mạng không dây, trình
bày tổng quát về bộ mô phỏng mạng NS-2 và nêu lên được mục tiêu nghiên cứu
xuyên suốt trong đề tài khóa luận tốt nghiệp này.
Chương 2: Trình bày các giao thức MAC của mạng LAN và WLAN như giao
thức CSMA/CD, CSMA/CA cùng hai chuẩn tương ứng là IEEE 802.3 và IEEE
802.11.
Chương 3: Nêu lên lịch sử hình thành, các đặc điểm chính của mạng MANET,
đồng thời mô tả chi tiết về các giao thức định tuyến như DSDV, AODV, DSR, OLSR,
TORA và phân loại các kỹ thuật định tuyến khác nhau.
Chương 4: Từ các kết quả thực nghiệm mô phỏng chúng tôi đánh giá ảnh hưởng
của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong
mạng MANET.
Phạm Văn Tứ
8
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Chương 2. GIAO THỨC MAC CỦA MẠNG LAN VÀ
WLAN
2.1. Mạng LAN và mạng WLAN
Trong nhưng năm gần đây mạng WLAN đã trở lên phổ biến rộng khắp ở mọi
nơi: lớp học, sân trường, thư viện, văn phòng, quán cà phê, khách sạn, tới hộ gia đình.
Mạng WLAN đã đạt được những bước tiến khá dài và vững chắc, dần trở thành một
đối trọng của công nghệ mạng LAN phổ biến từ trước tới nay. Các lợi thế lớn mà
WLAN đem lại cho người dùng gồm:
1. Tính di động:
Với khả năng hỗ trợ của mạng không dây, người dùng không bị ràng buộc vào
các dây nối, tức là trong khi đang kết nối người sử dụng vẫn có thể di chuyển từ vị trí
này đến vị trí khác trong khu vực phủ sóng mà không bị gò bó tại một vị trí cố định
như trong mạng LAN truyền thống. Nhờ đó người dùng có thể mang theo thiết bị của
mình đến bất cứ đâu có sóng không dây là có thể truy cập vào mạng.
2. Tính mềm dẻo:
Triển khai mạng không dây rất thuận tiện và dễ dàng vì môi trường truyền luôn
có sẵn mọi lúc, mọi nơi mà không cần phải lên kế hoach trước, không cần kéo dây cáp
mạng hay bất kỳ sự vướng víu nào. Người dùng dễ dàng thiết lập kết nối một cách
nhanh chóng phục vụ cho công việc của mình.
3. Dễ dàng triển khai lắp đặt:
Đối với nhiều khu vực việc triển khai mạng có dây khá là khó khăn, tốn nhiều
công sức do địa hình không thuận lợi hoặc không được phép lắp đặt vì làm mất mĩ
quan. Trái lại với mạng không dây ta chỉ cần thiết lập, lắp đặt các thiết bị trung tâm
như Access point, Switch, Router, sau đó không cần phải đi thêm các hệ thống dây cáp
đến từng máy cố định như trong mạng thông thường.
Phạm Văn Tứ
9
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
2.2. Chuẩn 802.3 và giao thức CSMA/CD
2.2.1. Chuẩn 802.3:
IEEE 802.3 là tập hợp các tiêu chuẩn do tổ chức IEEE định nghĩa về tầng vật lý
(Physical layer) và lớp con điều khiển truy cập môi trường truyền (MAC sublayer) của
lớp liên kết dữ liệu (Data link layer) trong mạng Ethernet. Theo chuẩn này, các kết nối
vật lý được thực hiện giữa các nút và (hoặc) các thiết bị cơ sở hạ tầng như: hub,
switch, router… bằng các loại cáp đồng hoặc cáp quang. Chuẩn 802.3 đồng thời cũng
hỗ trợ các kiến trúc mạng theo chuẩn 802.1.
Kích thước gói tin tối đa theo chuẩn là 1518 byte, mặc dù vậy để hỗ trợ mạng
LAN ảo và độ ưu tiên dữ liệu trong chuẩn 802.3ac, nó được mở rộng tới 1.522
byte. Nếu giao thức lớp trên đưa ra một khung dữ liệu (PDU) nhỏ hơn 64 byte, thì
chuẩn 802.3 sẽ đệm thêm các trường dữ liệu để đạt được tối thiểu 64 byte. Do đó kích
thước khung tối thiểu luôn luôn là 64 byte.
Với sự phát triển mạnh mẽ của công nghệ, tốc độ kết nối trong Ethernet không
ngừng được nâng lên. Dưới đây là một số mốc phát triển chính của chuẩn 802.3:
Bảng 1: Sự phát triển của chuẩn 802.3
Chuẩn
Năm
Sự kiện
Fast Ethernet ra đời với tốc độ 100 Mbit/s: 100BASE-
1995
802.3u
TX, 100BASE-T4, 100BASE-FX
1000BASE-X Gbit/s Ethernet qua cáp quang với tốc độ 1
1998
802.3z
Gbit/s
1999
2003
1000BASE-T Gbit/s Ethernet qua cáp UTP với tốc độ 1 Gbit/s
802.3ab
802.3ae
10 Gbit/s Ethernet over fiber
Phạm Văn Tứ
10
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
2.2.2. Giao thức CSMA/CD
Hình 4: Chu trình hoạt động của giao thức CSMA/CD (bên gửi)
CSMA/CD (Carrier Sense Multiple Access with Collision Detection) – là giao
thức Đa truy cập cảm nhận sóng mang có phát hiện xung đột. Mạng LAN hoạt động
dựa trên nguyên tắc này. Khi máy tính muốn truyền dữ liệu, trước tiên nó lắng nghe
xem đường truyền có bận hay không (bằng cách cảm nhận tín hiệu sóng mang). Nếu
không có, nó sẽ thực hiện truyền gói tin. Sau khi truyền gói tin, nó vẫn tiếp tục lắng
nghe để xem có máy nào định truyền tin hay không. Nếu không có xung đột, nó tiếp
tục truyền gói tin cho đến khi hoàn thành. Nếu phát hiện xung đột, nó sẽ gửi broadcast
ra toàn mạng tín hiệu nghẽn (jam signal) để các máy khác dễ dàng nhận ra xung đột.
Sau đó nó sẽ đợi một thời gian theo thuật toán Backoff rồi thử gửi lại gói tin.
Phạm Văn Tứ
11
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
2.3. Chuẩn 802.11 và giao thức CSMA/CA
2.3.1 Chuẩn 802.11
IEEE 802.11 là một tập các chuẩn do tổ chức IEEE quy định về truyền thông
máy tính trong mạng LAN không dây ở các dải tần số: 2.4 GHz, 3.6 GHz và 5 GHz.
Chuẩn 802.11 bao gồm các kỹ thuật điều biến tín hiệu “truyền qua không khí” (over-
the-air) sử dụng sóng vô tuyến để truyền nhận tín hiệu giữa các thiết bị không dây và
điểm truy cập (access point) hoặc giữa các thiết bị không dây với nhau (mạng ad-hoc).
Chuẩn mạng không dây đầu tiên được ra đời vào tháng sáu năm 1997 (802.11-
1997) nhưng phải mãi đến tháng 9 năm 1999 chuẩn 802.11b ra đời mới được chấp
nhận rộng rãi. Tiếp theo đó là sự ra đời của chuẩn 802.11g và 802.11n đánh dấu sự cải
tiến vượt trội về tốc độ truyền tải mạng không dây. Trong đó chuẩn 802.11n được ứng
dụng kỹ thuật điều biến đa luồng mới cho phép truyền dữ liệu ở tốc độ cao nhất lên
đến 150Mbps mỗi luồng. Chúng ta cùng nhìn lại sự phát triển, cải tiến của mạng
không dây chuẩn 802.11 theo bảng 2.
Bảng 2: Sự phát triển của chuẩn 802.11
Băng
thông
(MHz)
Số
Tần số
802.11
Tốc độ truyền dữ liệu trên
mỗi luồng (Mb/s)
Năm
luồng
MIMO
Protocol
(GHz)
20
20
20
20
20
1997
2.4
5/3.7
2.4
1, 2
1
1
1
1
-
9/1999
9/1999
6/2003
6, 9, 12, 18, 24, 36, 48, 54
1, 2, 5.5, 11
a
b
g
2.4
1, 2, 6, 9, 12, 18, 24, 36, 48, 54
7.2, 14.4, 21.7, 28.9, 43.3, 57.8,
65, 72.2
10/2009 2.4/5
4
n
40
15, 30, 45, 60, 90, 120, 135,
150
Phạm Văn Tứ
12
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
2.3.1 Giao thức CSMA/CA
Hình 5: Chu trình hoạt động của giao thức CSMA/CA (bên gửi)
CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) – Đa truy
cập cảm nhận sóng mang có tránh xung đột. CSMA/CD là phương thức truy cập của
lớp hai (Data link). Nguyên tắc hoạt động của phương thức này dựa trên việc cảm
nhận sóng mang, tránh xung đột và cơ chế nghe trước khi nói “Listen before talk”.
Một nút trước khi truyền phải lắng nghe kênh truyền trước để xem có nút nào khác
đang truyền sóng trong vùng sóng cần truyền hay không.
Phạm Văn Tứ
13
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Hình 6: Hoạt động lắng nghe kênh truyền của giao thức CSMA/CA
Nếu kênh truyền rỗi: Nút sẽ đợi một khoảng thời gian tối thiểu DIFS sau đó bắt
đầu quá trình truyền.
Nếu kênh truyền bận:
Nút muốn truyền phải đợi một khoảng thời gian DIFS
Và chờ thêm một khoảng thời gian Backoff ngẫu nhiên trong cửa sổ
tranh chấp. Cơ chế này giúp CSMA/CA tránh được xung đột.
Sau mỗi khoảng thời gian DIFS, nếu môi trường truyền rỗi, thời gian
Backoff giảm đi 1. Trái lại nó được giữ nguyên cho khoảng thời gian
DIFS tiếp theo. Khi thời gian Backoff giảm đến không, nút bắt đầu truy
cập môi trường truyền. Tuy nhiên, nếu trước đó một nút khác đã truy cập
môi trường truyền trước khi thời gian Backoff của nút này giảm đến
không thì nó sẽ giữ lại giá trị thời gian Backoff hiện tại để sử dụng cho
lần truy cập tiếp theo.
Phạm Văn Tứ
14
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN
3.1. Mạng MANET
3.1.1. Lịch sử phát triển và các ứng dụng
Lịch sử:
Mạng di động đặc biệt (Mobile Adhoc Netwowk) là mạng tự cấu hình của các
nút di động kết nối với nhau thông qua các liên kết không dây tạo nên mạng độc lập
không phụ thuộc vào cơ sở hạ tầng mạng. Các thiết bị trong mạng có thể di chuyển
một cách tự do theo mọi hướng, do đó liên kết của nó với các thiết bị khác cũng thay
đổi một cách thường xuyên.
Nguyên lý làm việc của mạng Adhoc bắt nguồn từ năm 1968 khi các mạng
ALOHA được thực hiện. Tuy các trạm làm việc là cố định nhưng giao thức ALOHA
đã thực hiện việc quản lý truy cập kênh truyền dưới dạng phân tán, đây là cơ sở lý
thuyết để phát triển kỹ thuật truy cập kênh phân tán vào mạng Adhoc.
Năm 1973 tổ chức DARPA đã bắt đầu làm việc trên mạng vô tuyến gói tin
PRnet. Đây là mạng vô tuyến gói tin đa chặng đầu tiên. Trong đó các nút hợp tác với
nhau để gửi dữ liệu tới một nút nằm ở xa khu vực kết nối thông qua một nút khác. Nó
cung cấp cơ chế cho việc quản lý hoạt động trên cơ sở tập trung và phân tán.
Một lợi điểm của làm việc đa chặng so với đơn chặng là triển khai đa chặng tạo
thuận lợi cho việc dùng lại tài nguyên kênh truyền về cả không gian, thời gian và giảm
năng lượng phát cần thiết.
Sau đó có nhiều mạng vô tuyên gói tin phát triển nhưng các hệ thống không dây
này vẫn chưa bao giờ tới tay người dùng cho đến khi chuẩn 802.11 ra đời. IEEE đã đổi
tên mạng vô tuyến gói tin thành mạng Adhoc.
Ứng dụng:
Quân sự: Hoạt động phi tập trung của mạng Adhoc và không phụ thuộc vào cơ
sở hạ tầng mạng là một yếu tố thiết yếu đối với lĩnh vực quân sự, nhất là trong các
trường hợp chiến đấu khốc liệt, các cơ sở hạ tầng mạng bị phá hủy. Lúc này mạng
Adhoc là lựa chọn số một để các thiết bị truyền thông liên lạc với nhau một cách
nhanh chóng.
Phạm Văn Tứ
15
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Trường học: Chúng ta cũng có thể thiết lập các mạng Adhoc trong trường học,
lớp học, thư viện, sân trường,… để kết nối các thiết bị di động (laptop, smartphone) lại
với nhau, giúp sinh viên, thầy cô giáo có thể trao đổi bài một cách nhanh chóng thông
qua mạng adhoc vừa tạo.
Gia đình: Tại nhà bạn có thể tạo nhanh mạng Adhoc để kết nối các thiết bị di
động của bạn với nhau, nhờ đó ta có thể di chuyển tự do mà vẫn đảm bảo kết nối
truyền tải dữ liệu.
Kết nối các thiết bị điện tử với nhau: Trong những năm tới khi mà các thiết bị
điện tử đều được gắn các giao tiếp không dây, giúp chúng có thể trao đổi giao tiếp với
nhau thì mạng Adhoc sẽ rất phù hợp để tạo nên một hệ thống thông mình có khả năng
liên kết với nhau.
3.1.2. Các đặc điểm chính của mạng MANET
Mỗi nút di động khác nhau trong mạng MANET đều có những đặc điểm về
nguồn năng lượng, bộ phận thu phát sóng khác nhau. Chúng có thể di chuyển về mọi
hướng theo các tốc độ khác nhau, do đó ta có thể nhận thấy rõ một số đặc điểm chính
của mạng MANET như sau:
Cấu hình mạng động: Cấu hình mạng luôn biến đổi theo các mức độ di
chuyển của nút mạng.
Khoảng cách sóng ngắn: Khoảng cách sóng của các thiết bị di động là rất hạn
chế.
Năng lượng hạn chế: Tất cả các thiết bị di động đều sử dụng pin nên khi tham
gia vào mạng MANET chúng bị hạn chế về năng lượng, khả năng xử lý của
CPU, kích thước bộ nhớ.
Băng thông hạn chế: Các liên kết không dây có băng thông thấp hơn so với
đường truyền cáp và chúng còn chịu ảnh hưởng của sự nhiễu, suy giảm tín hiệu,
các điều kiện giao thoa vì thế mà thường nhỏ hơn tốc độ truyền lớn nhất của
sóng vô tuyến.
Bảo mật yếu: Đặc điểm của mạng MANET là truyền sóng qua môi trường
không khí, điều này khiến cho cơ chế bảo mật kém hơn so vơi môi trường
truyền cáp vì nó tiềm ẩn nhiều nguy cơ bị tấn công, nghe lén đường truyền, giả
mạo, DoS,…
Phạm Văn Tứ
16
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
3.2. Vấn đề định tuyến trong mạng MANET
3.2.1 Các thuật toán định tuyến truyền thống
Các giao thức định tuyến truyền thống thường sử dụng hai giải thuật:
Distance Vector: RIP , IGRP,...
Nguyên tắc hoạt động: mỗi router sẻ gửi bảng định tuyến của mình cho tất cả
các router được nối trực tiếp với nó . Các router đó so sánh với bảng bảng định tuyến
mà mình hiện có và kiểm tra lại các tuyến đường của mình với các tuyến đường mới
nhận được, tuyến đường nào tối ưu hơn sẽ được đưa vào bảng định tuyến. Các gói tin
cập nhật sẽ được gửi theo định kỳ (30 giây với RIP ,90 giây đối với IGRP) [9].
Ưu điểm:
Dễ cấu hình, router không phải xử lý nhiều nên không tốn nhiều dung lượng bộ
nhớ và CPU có tốc độ xử lý nhanh hơn.
Nhược điểm:
- Hệ thống metric quá đơn giản (như Rip chỉ là hop-count ) dẫn đến việc các
tuyến đường được chọn vào bảng định tuyến chưa phải tuyến đường tốt nhất.
- Vì các gói tin cập nhật được gửi theo định kỳ nên một lượng băng thông đáng
kể sẽ bị chiếm.
- Do Router hội tụ chậm, dẫn đến việc sai lệch trong bảng địn tuyến gây nên hiện
tượng vòng lặp (loop).
Link state: OSPF, IS-IS
Nguyên tắc hoạt động: Các router không gửi bảng định tuyến của mình, mà chỉ
gửi tình trạng của các đường liên kết trong cơ sở dữ liệu trạng thái liên kết (linkstate-
database) của mình đi cho các router khác, các router sẽ áp dụng giải thuật SPF
(shortest path first ), để tự xây dựng bảng định tuyến riêng cho mình. Khi mạng đã hội
tụ, các giao thức Link state sẽ không gửi cập nhật định kỳ mà chỉ gửi khi nào có sự
thay đổi trong mạng (1 đường bị down , cần sử dụng đường dự phòng).
Ưu điểm:
Có thể thích nghi được với đa số hệ thống, cho phép người thiết kế có thể thiết kế
mạng linh hoạt, phản ứng nhanh với tình huống xảy ra. Do không gởi cập nhật định kỳ
như Distance Vector, nên Link State bảo đảm được băng thông cho các đường mạng.
Phạm Văn Tứ
17
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Nhược điểm:
- Do router phải xử lý nhiều, nên chiếm nhiều bộ nhớ, tốc độ CPU chậm hơn nên
tăng độ trễ
Việc sử dụng các giao thức định tuyến truyền thống trong mạng MANET sẽ dẫn
đến rất nhiều vấn đề trở ngại cần giải quyết:
Tiêu tốn năng lượng nguồn nuôi cho các cập nhập định kỳ như trong giao thức
định tuyến Distance Vector.
Tiêu tốn băng thông mạng cho các cập nhập định kỳ.
Làm quá tải bộ vi xử lý của thiết bị: khi các thông tin cập nhật, số nút mạng
tăng lên.
Tạo ra nhiều đường đi dư thừa
3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANET
Các giao thức định tuyến trong mạng MANET cần đảm bảo:
Thích ứng nhanh khi tô-pô mạng thay đổi: khi các nút mạng di chuyển nhanh,
yêu cầu kết nối tăng lên thì các giao thức hoạt động theo cơ chế tiếp cận tập
trung sẽ giảm hiệu quả rõ rệt do phải tốn nhiều thời gian để thu thập thông tin
về trạng thái hiện tại và phát tán lại nó. Trong khi đó cấu hình mạng có thể đã
thay đổi khác đi rồi.
Đảm bảo hiệu quả trong môi trường truyền khi các nút đứng yên. Lúc này tô-pô
mạng là cố định không thay đổi nên các giao thức định tuyến chỉ cần gửi các
cập nhật khi có yêu cầu hoặc mạng thay đổi như việc một nút nào đó tắt kết nối.
Không có lặp định tuyến: Cần ngăn chặn hiện tượng này, bởi vì khi đó các gói
tin bị định tuyến sai, dẫn đến việc bị truyền quay vòng liên tục trong một số kết
nối mạng, khiến cho băng thông mạng và các tài nguyên khác như năng lượng
nguồn nuôi bị tiêu tốn vô ích.
Bảo mật: Việc định tuyến trong mạng MANET có nguy cơ bị tấn công dễ dàng
bằng các phương pháp như xâm nhập đường truyền, phát lại, thay đổi các gói
tin tiêu đề, điều hướng các thông điệp định tuyến. Do đó khi thiết kế các giao
Phạm Văn Tứ
18
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
thức định tuyến cần phải có phương pháp để phát hiện được và ngăn chặn các
loại tấn công.
3.2.3. Phân loại các kỹ thuật định tuyến
3.2.3.1. Link state và Distance Vector
Thuật toán định tuyến vector khoảng cách (distance-vector routing protocols)
Thuật toán này dùng thuật toán Bellman-Ford, trong đó chỉ định một con số, gọi
là chi phí (hay trọng số), cho mỗi một liên kết giữa các nút trong mạng. Các nút sẽ gửi
thông tin về đường đi từ điểm A đến điểm B qua các đường truyền (kết nối) mang lại
tổng chi phí thấp nhất (là tổng các chi phí của các kết nối giữa các nút được dùng).
Thuật toán hoạt động với những hành động rất đơn giản. Khi một nút khởi động
lần đầu, nó chỉ biết các nút kề trực tiếp với nó, và chi phí trực tiếp để đi đến đó (thông
tin này, danh sách của các đích, tổng chi phí đến từng đích và bước kế tiếp để gửi dữ
liệu đến đó tạo nên bảng định tuyến, hay bảng khoảng cách). Mỗi nút, trong một tiến
trình, gửi đến từng “hàng xóm” tổng chi phí của nó để đi đến các đích mà nó biết. Các
nút “hàng xóm” phân tích thông tin này, và so sánh với những thông tin mà chúng
đang “biết”; bất kỳ điều gì cải thiện được những thông tin chúng đang có sẽ được đưa
vào các bảng định tuyến của những “hàng xóm” này. Đến khi kết thúc, tất cả nút trên
mạng sẽ tìm ra bước truyền kế tiếp tối ưu đến tất cả mọi đích, và tổng chi phí tốt nhất.
Khi một trong các nút gặp vấn đề, những nút khác có sử dụng nút hỏng này trong
lộ trình của mình sẽ loại bỏ những lộ trình đó, và tạo nên thông tin mới của bảng định
tuyến. Sau đó chúng chuyển thông tin này đến tất cả nút gần kề và lặp lại quá trình
trên. Cuối cùng, tất cả nút trên mạng nhận được thông tin cập nhật, và sau đó sẽ tìm
đường đi mới đến tất cả các đích mà chúng còn tới được.
Thuật toán định tuyến trạng thái kết nối (Link-state routing protocols)
Khi áp dụng các thuật toán trạng thái kết nối, mỗi nút sử dụng dữ liệu cơ sở của
nó như là một bản đồ của mạng với dạng một đồ thị. Để làm điều này, mỗi nút phát đi
tới toàn mạng những thông tin về các nút khác mà nó có thể kết nối được, và từng nút
góp thông tin một cách độc lập vào bản đồ. Sử dụng bản đồ này, mỗi nút sau đó sẽ xác
định được tuyến đường tốt nhất từ nó đến mọi nút khác.
Thuật toán đã làm theo cách này là Dijkstra, bằng cách xây dựng cấu trúc dữ liệu
khác, dạng cây, trong đó nút hiện tại là gốc, và chứa mọi nút khác trong mạng. Bắt đầu
Phạm Văn Tứ
19
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
với một cây ban đầu chỉ chứa chính nó. Sau đó lần lượt từ tập các nút chưa được thêm
vào cây, nó sẽ thêm nút có chi phí thấp nhất để đến một nút đã có trên cây. Tiếp tục
quá trình đến khi mọi nút đều được thêm vào cây.
Cây này sau đó phục vụ để xây dựng bảng định tuyến, đưa ra bước truyền kế tiếp
tốt ưu, … để từ một nút đến bất kỳ nút khác trên mạng.
So sánh các thuật toán định tuyến
Các giao thức định tuyến theo thuật toán vector khoảng cách đơn giản và hiệu
quả hơn trong các mạng nhỏ, đòi hỏi ít (nếu có) sự giám sát. Tuy nhiên nhược điểm
của nó là khả năng hội tụ chậm khi mạng lớn và thay đổi, điều này dẫn đến sự phát
triển của các thuật toán trạng thái kết nối tuy phức tạp hơn nhưng tốt hơn để dùng
trong các mạng lớn.
Ưu điểm chính của định tuyến bằng trạng thái kết nối là phản ứng nhanh nhạy
hơn, và trong một khoảng thời gian có hạn, đối với sự thay đổi kết nối. Ngoài ra,
những gói được gửi qua mạng trong định tuyến bằng trạng thái kết nối thì nhỏ hơn
những gói dùng trong định tuyến bằng vector. Định tuyến bằng vector đòi hỏi bảng
định tuyến đầy đủ phải được truyền đi, trong khi định tuyến bằng trạng thái kết nối thì
chỉ có thông tin về “hàng xóm” của nút được truyền đi. Vì vậy, các gói này dùng tài
nguyên mạng ở mức không đáng kể. Khuyết điểm chính của định tuyến bằng trạng
thái kết nối là nó đòi hỏi nhiều sự lưu trữ và tính toán để chạy hơn định tuyến bằng
vector.
3.2.3.2. Định tuyến chủ ứng và phản ứng
Các giao thức định tuyến trong mạng MANET được người ta phân chia thành các
loại: định tuyến chủ ứng (proactive), định tuyến phản ứng (reactive) và định tuyến lai
ghép giữa hai loại trên. Các giao thức định tuyến chủ ứng sử dụng phương pháp phát
tràn (Floading) để quảng bá thông tin tới các thiết bị. Phương pháp này cho phép thời
gian thiết lập đường nhanh dựa trên các tham số gửi tới thiết bị sẵn sàng cho kết nối.
Tuy nhiên, phương pháp này cũng làm lưu lượng các gói tin tìm đường tăng lên rất
lớn, đây chính là nhược điểm của phương pháp này. Giao thức định tuyến trạng thái
liên kết tối ưu OLSR (Optimized Link State Routing) và giao thức định tuyến vector
khoảng cách tuần tự đích DSDV (Dynamic Destination-Sequenced Distance-Vector
Routing) là hai ví dụ của giao thức định tuyến chủ ứng.
Phạm Văn Tứ
20
K51MMT
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Các giao thức định tuyến phản ứng thiết lập tuyến dựa theo từng yêu cầu kết nối.
Phương pháp này hạn chế được chi phí tìm đường, nhưng nhược điểm cơ bản là gây
trễ lớn cho các khung truyền dẫn đầu tiên cũng như thời gian chọn đường dẫn chậm.
Hai giao thức phản ứng điển hình là giao thức định tuyến vector khoảng cách theo yêu
cầu AODV (On-demand Distance Vector Routing) và giao thức định tuyến định tuyến
nguồn động DSR (Dynamic Source Routing).
Một khi xảy ra lỗi tại nút, các giao thức định tuyến thường khôi phục đường dẫn
bằng phương pháp thiết lập tuyến mới. Hầu hết các tiếp cận hiện nay đều sử dụng
thông tin phản hồi tới thiết bị nguồn nhằm khởi tạo tuyến mới, vì vậy lưu lượng bản
tin trao đổi là rất lớn và tăng lên rất nhanh khi kích thước mạng lớn, nhất là đối với các
giao thức định tuyến chủ ứng. Khi kích thước mạng tăng cũng đồng nghĩa với sự suy
giảm hiệu năng mạng do hiện tượng trễ của thủ tục định tuyến và truyền khung đầu
tiên tăng lên rất lớn nếu sử dụng giao thức định tuyến phản ứng.
3.2.3.3. Định tuyến nguồn và định tuyến theo chặng
Với định tuyến nguồn, toàn bộ thông tin về đường đi tới đích được đặt trong
trường tiêu đề của gói tin dữ liệu, các nút trung gian chỉ việc chuyển tiếp gói tin theo
đường trong tiêu đề. Lợi điểm của giao thức này là loại bỏ được nhu cầu quảng bá
đường định kỳ và các gói tin khám phá (discovery) hàng xóm.
Trong định tuyến theo chặng, khi một nút nhận được gói tin cần chuyển tới
đích, nút đó chuyển tiếp gói tin theo chặng tiếp theo hướng tới đích mà nó biết. Nút
tiếp theo lại chuyển tiếp gói tin đến đích theo những chặng mà nó biết dựa vào bảng
định tuyến của nó. Quá trình trên sẽ dừng lại khi gói tin được chuyển tới đích. Nhược
điểm của phương pháp này là tất cả các nút cần duy trì thông tin định tuyến nên phải
xử lý nhiều hơn và có khả năng tạo thành các vòng lặp định tuyến.
Phạm Văn Tứ
21
K51MMT
Tải về để xem bản đầy đủ
69 trang
21/05/2025
70
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong manet", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_khao_sat_anh_huong_cua_su_chuyen_dong_cac_nut_mang.pdf
