Luận văn Nghiên cứu phương pháp định tuyến hiệu quả trên cơ sở định tuyến đa đường có cân bằng tải cho mạng AD HOC
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Trần Thị Thu Thảo
NGHIÊN CỨU PHƯƠNG PHÁP
ĐỊNH TUYẾN HIỆU QUẢ TRÊN CƠ SỞ
ĐỊNH TUYẾN ĐA ĐƯỜNG CÓ CÂN BẰNG TẢI
CHO MẠNG AD HOC
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2020
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Trần Thị Thu Thảo
NGHIÊN CỨU PHƯƠNG PHÁP
ĐỊNH TUYẾN HIỆU QUẢ TRÊN CƠ SỞ
ĐỊNH TUYẾN ĐA ĐƯỜNG CÓ CÂN BẰNG TẢI
CHO MẠNG AD HOC
Ngành: Khoa học máy tính
Mã số: 8480101
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. NGUYỄN VĂN TAM
Thái Nguyên - 2020
LỜI CẢM ƠN
Sau thời gian học tập và nghiên cứu tại trường Đại học Công nghệ thông
tin và Truyền thông – Đại học Thái Nguyên, em đã hoàn thành luận văn tốt
nghiệp thạc sĩ ngành Khoa học máy tính. Để có được kết quả này, em xin bày
tỏ sự kính trọng và lòng biết ơn sâu sắc tới:
- PGS. TS. Nguyễn Văn Tam là cán bộ hướng dẫn khoa học đã luôn tận
tình giúp đỡ và chỉ bảo em trong suốt quá trình làm luận văn.
- Các cán bộ, giảng viên Khoa Công nghệ thông tin và Phòng Đào tạo
cùng toàn thể các thầy, cô giáo trong trường Trường Đại học CNTT &
TT - ĐHTN đã tận tình chỉ bảo, hướng dẫn và giúp đỡ em trong suốt
quá trình em thực hiện đề tài luận văn này.
Bên cạnh đó sự giúp đỡ của gia đình, bạn bè và người thân đã luôn ủng hộ
và tạo điều kiện tốt nhất để em có thể tập trung nghiên cứu hoàn thành luận văn.
Do về mặt kiến thức và thời gian còn hạn chế, luận văn còn nhiều khiếm
khuyết. Tôi mong được sự đóng góp ý kiến của các thầy, cô và mọi người để
luận văn hoàn thiện hơn.
Xin trân trọng cảm ơn!
Thái Nguyên, ngày … tháng …. năm 2020
Học viên
Trần Thị Thu Thảo
MỤC LỤC
MỞ ĐẦU........................................................................................................................1
cầu ............................................................................................................. 9
1.5. Tổng kết Chương 1 .............................................................................. 17
ĐƯỜNG VÀ CÂN BẰNG TẢI...............................................................................19
2.2.4. Thuật toán tại nút đích .................................................................. 25
3.4. Đánh giá kết quả................................................................................... 53
3.5. Tổng kết Chương 3 .............................................................................. 54
DANH MỤC HÌNH
Hình 1.1. Minh họa của mạng MANET......................................................................4
dữ liệu...................................................................................................44
dữ liệu...................................................................................................46
dữ liệu...................................................................................................47
dữ liệu...................................................................................................49
1
MỞ ĐẦU
Mạng ad hoc di động (MANET) được hình thành bởi kết nối tạm thời giữa
các nút mạng. Đây là công nghệ mạng nền tảng để phát triển các công nghệ mạng
được ứng dụng rộng rãi ngày nay như mạng cảm biến, mạng giao thông, mạng
tác chiến,… Trong mạng MANET, mỗi nút mạng vừa đóng vai trò là một thiết
bị đầu cuối, vừa đóng vai trò là một bộ định tuyến. Do tính chất di động của các
nút mạng nên bài toán định tuyến trong mạng MANET có nhiều điểm khác biệt
so với bài toán định tuyến trong các mạng truyền thống. Từ góc nhìn số lượng
đường định tuyến sử dụng, có thể phân chia các giao thức định tuyến trong mạng
MANET theo hai nhóm là định tuyến đơn đường và định tuyến đa đường.
Định tuyến trong mạng MANET là một vấn đề đã được nhiều nhà nghiên
cứu quan tâm. Giao thức định tuyến theo yêu cầu dạng véc tơ khoảng cách
trong mạng ad hoc (AODV) là một trong những giao thức phổ biến nhất và
được sử dụng rộng rãi trong MANETs. Kỹ thuật định tuyến có khả năng nhận
biết và thích ứng với vấn đề tắc nghẽn cũng đã được một số nhà nghiên cứu
xem xét. Trong thời gian qua, một số giao thức đã được đề xuất trên cơ sở ước
lượng thời gian định tuyến làm độ đo định tuyến thay vì độ đo số chặng như
trong giao thức AODV. Các giao thức này sẽ chọn đường có độ đo thời gian
định tuyến tối thiểu trong tiến trình khám phá đường. Những giao thức định
tuyến như vậy có tính đến độ trễ của liên kết dựa trên hiệu suất của kênh truyền
cũng như độ trễ hàng đợi do vấn đề tắc nghẽn tại các nút trung gian.
Đối với các giao thức định tuyến đơn đường, chỉ có tối đa một con đường
tối ưu theo độ đo định tuyến của chúng được cài đặt vào bảng định tuyến sau
mỗi tiến trình tìm đường mặc dù chúng có thể nhận được thông tin về nhiều
con đường tới cùng một đích trong cùng một tiến trình tìm đường. Tại mỗi nút
mạng, các gói tin dữ liệu sẽ được chuyển tiếp theo con đường thích hợp có
2
trong bảng định tuyến. Khi một liên kết trên con đường đó bị lỗi, nút mạng này
phải khởi tạo lại tiến trình tìm đường.
Một lớp giao thức định tuyến khác trong MANET hoạt động dựa trên cơ
chế tìm nhiều đường giữa một cặp nút nguồn đích cho trước, sau đó phân phối
tải dữ liệu của các gói từ nguồn đến đích theo tất cả các con đường tìm được.
Ngoài việc giảm thời gian định tuyến tất cả các gói tin thông qua nhiều con
đường, một ưu điểm khác của định tuyến đa đường là làm tăng độ tin cậy trong
truyền thông.
Giao thức FMLB (Fibonacci sequence based Multipath Load Balancing) là
một giao thức định tuyến đa đường hoạt động theo cơ chế phân phối tải dữ liệu
trên cơ sở chuỗi Fibonacci để cân bằng tải dữ liệu trên nhiều đường khác nhau.
Mục tiêu của đề tài này là nghiên cứu một kỹ thuật định tuyến hiệu quả
trên cơ sở định tuyến đa đường có cân bằng tải được triển khai trong một giao
thức định tuyến mới gọi là LCMR sử dụng trong mạng MANET. Các vấn đề
được nghiên cứu bao gồm: Cơ chế tìm đường cho phép tìm nhiều đường giữa
một cặp nguồn-đích; kỹ thuật ước lượng thời gian định tuyến theo mỗi con
đường; chiến lược cân bằng tải dữ liệu trên các đường để giảm thiểu thời gian
định tuyến. Việc so sánh đánh giá hiệu năng định tuyến của các kỹ thuật và
chiến lược được đề xuất trong giao thức LCMR được thực hiện thông qua việc
phân tích lý thuyết và mô phỏng, đánh giá hiệu năng giữa giao thức LCMR với
các giao thức cùng lớp đã được đề xuất trước đó là FMLB và MAODV.
Luận văn có cấu trúc như sau: Chương 1 trình bày tổng quan về mạng
MANET và vấn đề định tuyến trong mạng MANET. Một giao thức định tuyến
hiệu quả trên cơ sở định tuyến đa đường và cân bằng tải được trình bày chi tiết
trong Chương 2 từ ý tưởng thiết kế, cơ chế hoạt động đến việc phân tích hiệu
năng của giao thức theo lý thuyết toán học. Kết quả của việc cài đặt, mô phỏng,
so sánh đánh giá hiệu quả của giao thức định tuyến LCMR với 4 giao thức định
3
tuyến đa đường khác là FLMBRT, FLMBHC, MAODVRT và MAODVHC
được trình bày trong Chương 3. Nội dung tổng kết và hướng phát triển của đề
tài được đưa ra trong phần kết luận.
4
CHƯƠNG 1. TỔNG QUAN MẠNG MANET VÀ ĐỊNH TUYẾN ĐA
ĐƯỜNG TRONG MẠNG MANET
1.1. Tổng quan về mạng MANET
1.1.1. Khái niệm mạng MANET
Mạng MANET (Mobile Ad hoc Network – MANET) [4] là mạng di động
không dây hoạt động không cần dựa vào hạ tầng mạng cố định, trong đó hình
trạng mạng được tạo thành bởi chính các nút mạng. Chế độ “Ad hoc” của chuẩn
IEEE 802.11 hoạt động theo mô hình này, mặc dù nó chỉ hỗ trợ để thiết lập một
mạng đơn chặng. Các mạng di động không dây kiểu không cấu trúc đã mở rộng
khái niệm “Ad hoc” đa chặng theo nghĩa: một nút mạng có thể định tuyến và
chuyển tiếp một gói tin nó nhận được từ một nút mạng khác. Nói cách khác, con
đường chuyển tiếp gói tin từ nút nguồn tới nút đích có thể chứa các nút trung gian
khác. Các nút trung gian sẽ đọc thông tin trong phần header của các gói tin dữ liệu
và chuyển tiếp chúng tới chặng kế tiếp trên một con đường đã được hình thành.
Có thể hiểu một mạng MANET là một tập các nút không dây di động có
thể trao đổi dữ liệu một cách linh động mà không cần sự hỗ trợ của trạm cơ sở
cố định hoặc mạng có dây. Mỗi nút di động có một phạm vi truyền giới hạn, do
đó chúng cần sự trợ giúp của các nút lân cận để chuyển tiếp các gói dữ liệu.
Khi các gói tin dữ liệu từ nút nguồn cần gửi tới một nút đích mà nút đích không
nằm trong phạm vi truyền của nút nguồn, cần có sự trợ giúp của các nút trung
gian để chuyển tiếp gói tin từ nút nguồn tới nút đích. Để thực hiện được công
việc này, các nút mạng phải sử dụng giao thức định tuyến phù hợp.
Hình 1.1. Minh họa của mạng MANET
5
Hình 1 là một ví dụ của mạng MANET. Trong đó các nút trong mạng kết
nối với nhau trong một khoảng thời gian để trao đổi thông tin. Trong khi trao
đổi thông tin, các nút này vẫn có thể di chuyển, do đó, mạng này phải đáp ứng
được yêu cầu truyền dữ liệu trong khi hình trạng mạng có thể thay đổi liên tục.
Các nút mạng phải có cơ chế tự tổ chức thành một mạng để thiết lập các đường
truyền dữ liệu mà không cần sự hỗ trợ từ bên ngoài. Trong mô hình này, mỗi
nút mạng có thể đóng vai trò là một nút đầu cuối để chạy các chương trình ứng
dụng của người sử dụng hoặc là một bộ định tuyến để chuyển tiếp các gói tin
cho các nút mạng khác.
1.1.2. Đặc điểm của mạng MANET
Do mạng MANET là một mạng không dây hoạt động không cần sự hỗ
trợ của hạ tầng mạng cơ sở trên cơ sở truyền thông đa chặng giữa các thiết bị
di động vừa đóng vai trò là thiết bị đầu cuối, vừa đóng vai trò là bộ định tuyến
nên mạng MANET có một số đặc điểm nổi bật sau [12]:
Cấu trúc động: Do tính chất di chuyển ngẫu nhiên của các nút mạng nên cấu
trúc của loại mạng này cũng thường xuyên thay đổi một cách ngẫu nhiên ở
những thời điểm không xác định trước. Trong khi thay đổi, cấu trúc của mạng
MANET có thêm hoặc mất đi các kết nối hai chiều hoặc kết nối một chiều.
Chất lượng liên kết hạn chế: Các liên kết không dây thường có băng thông
nhỏ hơn so với các liên kết có dây. Ngoài ra, do ảnh hưởng của cơ chế đa truy
cập, vấn đề suy giảm tín hiệu, nhiễu và các yếu tố khác, băng thông thực của
các liên kết không dây thường thấp hơn nhiều so với tốc độ truyền tối đa theo
lý thuyết của môi trường truyền không dây.
Các nút mạng có tài nguyên hạn chế: Mỗi nút di động trong mạng có thể là
một bộ cảm biến, một điện thoại thông minh hoặc một máy tính xách tay. Thông
thường các thiết bị này có tài nguyên hạn chế so với các máy tính trong mạng
có dây và không dây truyền thống về tốc độ xử lý, dung lượng bộ nhớ và năng
lượng nguồn pin nuôi sống hoạt động của nút.
6
Độ bảo mật thấp ở mức độ vật lý: Mạng không dây di động thường chịu tác
động về mặt vật lý từ các nguồn gây nguy hại về an ninh nhiều hơn so với mạng
có dây. Về khía cạnh vật lý, các kỹ thuật gây mất an ninh và bảo mật trong
mạng như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ triển khai
trong mạng MANET hơn là trong mạng có dây truyền thống.
Có thể thấy những đặc điểm này là các yếu tố ảnh hưởng rất nhiều đến hiệu
năng của mạng MANET. Để có thể triển khai được mạng MANET trong thực tế,
các thiết kế mạng phải giải quyết được những thách thức sinh ra do những đặc
điểm đã nêu trên. Những thách thức này gồm các vấn đề kỹ thuật như khả năng
truyền dữ liệu và định tuyến hiệu quả khi kích thước mạng thay đổi; đảm bảo chất
lượng dịch vụ (QoS) cho các chương trình ứng dụng; cơ chế chuyển đổi một số
dịch vụ từ mô hình client-server; tiết kiệm năng lượng pin để kéo dài thời gian
hoạt động của các nút mạng riêng lẻ và của toàn mạng; đảm bảo an ninh mạng;
khả năng hợp tác giữa các nút mạng và khả năng tự tổ chức của mạng;
1.1.3. Ứng dụng của mạng MANET
Ngày nay, mạng MANET có nhiều những ứng dụng trong đời sống, kinh
tế, xã hội của con người. Mô hình mạng này phù hợp đối với những tình huống
cần triển khai hệ thống mạng một cách nhanh chóng, linh động và thường xuyên
có sự biến đổi trong cấu trúc mạng. Chúng còn được ứng dụng rất nhiều trong
các ứng dụng từ lĩnh vực thương mại tới các ứng dụng trong các hoạt động
quân sự, ứng dụng trong các hoạt động khẩn cấp, ứng dụng trong gia đình, văn
phòng và giáo dục, mạng giao thông và mạng cảm biến.
Đối với các ứng dụng của mạng MANET trong thương mại, những người
dùng có thể chia sẻ dữ liệu giữa các thiết bị di động trong một cuộc họp hay hội
thảo mà không cần sự hỗ trợ của một cơ sở hạ tầng mạng cố định. Các máy tính
của những cá nhân có thể kết nối với nhau để tạo thành một mạng tạm thời phục
vụ cho các ứng dụng truyền thông dữ liệu trong một nhóm những người dùng
7
mà không cần sự hiện diện của các bộ thu phát tập trung. Kết nối Internet từ
một thiết bị của một người dùng cũng có thể được chia sẻ tới các thiết bị của
những người dùng khác thông qua mạng MANET.
Ứng dụng mạng MANET trong quân đội là một trong những ý tưởng
được đưa ra ngay từ khi mạng MANET được phát triển. Trong mô hình chiến
đấu của quân đội trên chiến trường không có sự hỗ trợ về hạ tầng mạng cố định,
mỗi người lính hoặc một phương tiện quân sự như xe tăng, máy bay, tàu chiến,
tàu thủy đều có thể được kết nối và trao đổi thông tin tạm thời với nhau hoặc
với trạm chỉ huy một cách linh động thông qua mạng MANET được hình thành
bởi kết nối giữa các thiết bị di động truyền thông không dây được gắn vào các
phương tiện quân sự hay những người lính tham gia vào cuộc chiến.
Tại các vùng bị thiên tai, thảm họa, có thể tất cả các phương tiện và hạ
tầng truyền thông được xây dựng trước đó đều bị phá hủy hoàn toàn. Mỗi chiếc
xe của cảnh sát, cứu hỏa, cứu thương,… có thể được trang bị các thiết bị truyền
nhận không dây để trở thành một thiết bị đầu cuối di động và là một phần của
mạng MANET. Mỗi nhân viên cứu hộ cũng có thể mang theo một thiết bị đầu
cuối di động. Các thiết bị đầu cuối này đều liên kết với nhau, hình thành nên
một mạng MANET tạm thời nhằm trao đổi thông tin. Cấu hình mạng thay đổi
theo những thời điểm khác nhau. Ngoài ra, các thiết bị đầu cuối di động không
chỉ cung cấp chức năng gửi và nhận thông tin mà còn có thể chuyển tiếp thông
tin như vai trò các bộ định tuyến.
Mỗi thiết bị thông minh trong gia đình, các điện thoại di động thông minh
và máy tính của những người sử dụng trong văn phòng, trong môi trường
trường học, các lớp học có thể đóng vai trò như một nút mạng trong một mạng
MANET được hình thành tạm thời mà không cần sự hỗ trợ của hạ tầng mạng
cố định nhằm phục vụ cho các ứng dụng chia sẻ thông tin, truyền dữ liệu
multimedia, quản lý ngôi nhà thông minh, quản lý lớp học thông minh,…
8
Trong vấn đề quản lý và hỗ trợ giao thông, mỗi phương tiện giao thông
là một nút mạng di động trong mạng MANET được hình thành tạm thời trên
một khu vực địa lý nhằm hỗ trợ trao đổi và quản lý các thông tin về tình trạng
giao thông, hỗ trợ tìm đường tránh tắc nghẽn giao thông, theo dõi và quản lý
các thiết bị tham gia giao thông, v.v.
Cảm biến là các thiết bị nhỏ, phân tán, giá thành thấp, tiết kiệm năng
lượng, có khả năng truyền thông không dây và xử lý cục bộ. Một mạng MANET
có thể là một mạng cảm biến gồm các nút cảm biến. Các nút này hợp tác với
nhau để cùng thực hiện một nhiệm vụ cụ thể, ví dụ như: giám sát môi trường
(không khí, đất, nước), theo dõi môi trường sống, hành vi, dân số của các loài
động, thực vật, dò tìm động chấn, theo dõi tài nguyên, thực hiện trinh thám
trong quân đội,...
1.2. Một số chiến lược định tuyến trong mạng MANET
1.2.1. Phân loại các chiến lược định tuyến
Có nhiều cách để phân loại các chiến lược định tuyến cho mạng MANET
theo các tiêu chí khác nhau [11]. Các chiến lược định tuyến này được liệt kê
trong Bảng 1.1.
Bảng 1.1. Phân loại các chiến lược định tuyến của mạng MANET
Tiêu chí phân loại
Thời điểm định tuyến
Loại
Định tuyến tìm đường trước và tìm
đường theo yêu cầu
Phương pháp truyền thông tin định
tuyến
Định tuyến cập nhật định kỳ và cập
nhật theo sự kiện
Định tuyến phẳng và định tuyến
phân cấp
Số lượng vùng định tuyến
Thông tin định tuyến trong header
của gói
Định tuyến nguồn và định tuyến
từng chặng
Định tuyến tập trung và định tuyến
phân tán
Vị trí tính toán đường
9
1.2.2. Chiến lược định tuyến tìm đường trước và tìm đường theo yêu cầu
Kiểu định tuyến tìm đường trước còn được gọi là “định tuyến kích hoạt
trước” hay “định tuyến điều khiển dạng bảng”. Đối với kiểu định tuyến này,
các con đường tới mọi đích được tìm ra trước khi có nhu cầu truyền dữ liệu tại
mọi nút mạng. Trạng thái của các liên kết được lưu trữ và cập nhật định kỳ
trong bảng định tuyến để phục vụ cho thuật toán tìm đường tại mỗi nút mạng.
Ưu điểm lớn nhất của kỹ thuật định tuyến này là khi có yêu cầu truyền dữ liệu,
con đường truyền dữ liệu đã sẵn sàng tại các nút mạng và do đó không có độ
trễ từ khi có yêu cầu truyền dữ liệu tới lúc tìm ra con đường để truyền dữ liệu.
Tuy nhiên các giao thức thuộc nhóm này cũng có nhược điểm là chúng tính
toán và tìm ra những con đường tới mọi đích nên có thể có một số con đường
sẽ không bao giờ được sử dụng và kỹ thuật quảng bá bảng định tuyến định kỳ
sẽ chiếm dụng băng thông mạng nhiều khi trạng thái các liên kết và hình trạng
mạng thay đổi với tốc độ nhanh. Có thể kể đến một số giao thức định tuyến tiêu
biểu thuộc nhóm này là giao thức DSDV và giao thức WRP.
Đối với các giao thức định tuyến tìm đường theo yêu cầu, chỉ khi có nhu
cầu sử dụng đường truyền dữ liệu, các nút liên quan mới khởi tạo tiến trình tìm
đường và trao đổi thông tin định tuyến. Phương pháp này có ưu điểm là tiết kiệm
băng thông mạng dành cho tải định tuyến nhưng cũng có nhược điểm là quá trình
tìm kiếm tuyến đường có thể gây ra một độ trễ truyền tin đáng kể. Một số giao
thức tiêu biểu đã được đề xuất thuộc nhóm này là DSR, AODV và TORA.
1.2.3. Định tuyến cập nhật định kỳ và cập nhật theo sự kiện
Với các giao thức định tuyến trên cơ sở trạng thái liên kết (link state), để
đảm bảo thông tin về trạng thái của các liên kết và hình trạng mạng được cập
nhật kịp thời, thông tin định tuyến cần được quảng bá tới các nút mạng. Trên
cơ sở cách thức quảng bá thông tin định tuyến, ta có thể phân loại các chiến
lược định tuyến thành hai nhóm là định tuyến cập nhật định kỳ và định tuyến
10
cập nhật theo sự kiện. Chiến lược định tuyến theo chu kỳ sẽ duy trì độ ổn định
của mạng và quan trọng nhất là cho phép các nút mạng học được thông tin về
hình trạng và trạng thái của toàn mạng. Tuy nhiên, nếu sử dụng chu kỳ dài để
cập nhật thông tin định tuyến, các nút mạng có thể chứa các thông tin định
tuyến đã cũ và không chính xác. Ngược lại, nếu chu kỳ cập nhật thông tin định
tuyến là quá ngắn, sẽ có quá nhiều gói tin định tuyến được sinh ra và quảng bá
trong mạng gây ra sự lãng phí về tài nguyên mạng.
Đối với chiến lược định tuyến theo sự kiện, khi có một sự kiện diễn ra
trong mạng, những nút mạng chịu tác động trực tiếp của các sự kiện này mới
quảng bá các gói tin cập nhật thông tin định tuyến. Vì vậy, thông tin về những
thay đổi của trạng thái mạng sẽ nhanh chóng được cập nhật tới các nút mạng.
Tuy nhiên, khi topo mạng thay đổi với tốc độ nhanh, sẽ có rất nhiều các gói tin
quảng bá cập nhật định tuyến được sinh ra làm lãng phí băng thông mạng và
biến động đối với các con đường truyền dữ liệu.
1.2.4. Định tuyến phẳng và định tuyến phân cấp
Trong định tuyến phẳng, mọi nút trong mạng đều có cùng cấp độ và chức
năng định tuyến. Chiến lược định tuyến này tương đối đơn giản và hiệu quả đối
với các mạng nhỏ. Các giao thức AODV, DSDV, DSR là những giao thức điển
hình sử dụng chiến lược định tuyến phẳng. Đối với các mạng lớn, vấn đề gặp
phải là lãng phí tài nguyên mạng dành cho việc xử lý và truyền các gói tin
quảng bá thông tin định tuyến. Chiến lược định tuyến phân cấp được đề xuất
nhằm giải quyết vấn đề này.
Trong chiến lược định tuyến phân cấp, các nút mạng được tổ chức một
cách link động thành các vùng. Mỗi vùng lại có thể chia tiếp thành các vùng
con theo kiểu cây phân cấp. Cấu trúc phân cấp này nhằm duy trì tính ổn định
tương đối của hình trạng mạng. Sự di chuyển của thay đổi trạng thái của một
nút mạng chỉ tác động trong phạm vi của vùng quản lý nó. Chỉ có thông tin điều
11
khiển cấp cao mới được truyền giữa các vùng để giảm tải định tuyến trong
mạng. Mỗi nút mạng sẽ có thông tin đầy đủ về các nút mạng khác trong cùng
vùng với nó bằng cách sử dụng kỹ thuật định tuyến tìm đường trước. Nếu nút
đích và nút nguồn của một yêu cầu truyền dữ liệu thuộc hai vùng khác nhau,
kỹ thuật định tuyến liên vùng theo yêu cầu sẽ được sử dụng. Định tuyến liên
vùng thường hoạt động theo cơ chế định tuyến theo yêu cầu hoặc cơ chế kết
hợp giữa định tuyến tìm đường trước và định tuyến theo yêu cầu. Các giao thức
tiêu biểu sử dụng chiến lược định tuyến phân cấp là HSR và CGSR.
Hình 1.2 và Hình 1.3 minh họa cho các con đường được hình thành bởi
các giao thức định tuyến hoạt động theo chiến lược định tuyến phẳng và định
tuyến phân cấp.
Hình 1.2. Đường truyền dữ liệu theo chiến lược định tuyến phẳng
Hình 1.3. Đường truyền dữ liệu theo chiến lược định tuyến phân cấp
12
1.2.5. Định tuyến với kỹ thuật tính toán tập trung và tính toán phân tán
Trong chiến lược định tuyến với kỹ thuật tính toán tập trung, mọi nút trong
mạng sẽ duy trì thông tin đầy đủ về toàn bộ hình trạng mạng để có thể tự thực
hiện các thuật toán tìm đường khi cần thiết. Các giao thức định tuyến sử dụng
chiến lược định tuyến này còn được gọi là các giao thức định tuyến kiểu trạng
thái đường liên kết. Giao thức OLSR là một giao thức định tuyến kiểu trạng
thái đường liên kết tiêu biểu.
Trong chiến lược định tuyến với kỹ thuật tính toán phân tán, mọi nút mạng
chỉ duy trì thông tin cục bộ về hình trạng mạng. Khi có nhu cầu tìm đường,
nhiều nút mạng sẽ cùng tham gia vào tiến trình tìm đường. Chiến lược định
tuyến này còn được gọi là định tuyến kiểu véc tơ khoảng cách. AODV và
DSDV là các giao thức định tuyến tiêu biểu sử dụng chiến lược định tuyến này.
1.2.6. Định tuyến nguồn và định tuyến từng chặng
Có một vài giao thức định tuyến đưa thông tin về toàn bộ con đường vào
trong header của các gói tin dữ liệu để các nút trung gian có thể chuyển tiếp
những gói tin này theo các thông tin định tuyến mà nó đọc được trong phần
header. Chiến lược định tuyến này được gọi là định tuyến nguồn. Ưu điểm của
chiến lược định tuyến này là các nút trung gian không cần duy trì thông tin định
tuyến cập nhật để tìm đường cho các gói tin chúng chuyển tiếp vì chính trong
các gói tin dữ liệu đã chứa thông tin phục vụ cho các quyết định định tuyến.
Tuy nhiên, chiến lược này lại có nhược điểm là làm tăng kích thước của các gói
tin dữ liệu, đặc biệt với các con đường dài và các mạng có kích thước lớn dẫn
đến việc lãng phí băng thông của mạng ad hoc. Giao thức DSR là một trong
những giao thức định tuyến nguồn tiêu biểu. Hình 1.4 minh họa cơ chế chuyển
tiếp gói tin của giao thức định tuyến nguồn.
13
Hình 1.4. Truyền dữ liệu theo chiến lược định tuyến nguồn
Trong chiến lược định tuyến từng chặng, con đường tới một nút đích được
phân bố trong các “chặng kế tiếp” của các nút thuộc con đường này. Khi một
nút nhận được một gói tin cần truyền tới một đích xác định, nó sẽ chuyển tiếp
gói tin này tới chặng kế tiếp tương ứng trên con đường. Vì mỗi nút mạng không
có thông tin đầy đủ về toàn bộ các liên kết trong mạng nên thuật toán định tuyến
của các giao thức sử dụng chiến lược định tuyến này phải đảm bảo không chọn
các con đường gây ra định tuyến lặp. Giao thức AODV là một trong những giao
thức tiêu biểu sử dụng chiến lược định tuyến từng chặng. Hình 1.5 minh họa
kỹ thuật chuyển tiếp gói tin của giao thức hoạt động theo chiến lược định tuyến
từng chặng.
Hình 1.5. Truyền dữ liệu theo chiến lược định tuyến từng chặng
1.2.7. Định tuyến đơn đường và định tuyến đa đường
Đối với các giao thức định tuyến đơn đường, chỉ có tối đa một con đường
tối ưu theo độ đo định tuyến của chúng được cài đặt vào bảng định tuyến sau
mỗi tiến trình tìm đường mặc dù chúng có thể nhận được thông tin về nhiều
Tải về để xem bản đầy đủ
65 trang
10720
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Nghiên cứu phương pháp định tuyến hiệu quả trên cơ sở định tuyến đa đường có cân bằng tải cho mạng AD HOC", để 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:
- luan_van_nghien_cuu_phuong_phap_dinh_tuyen_hieu_qua_tren_co.pdf
