Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
1
MỤC LỤC
THUẬT NGỮ VIẾT TẮT 2
DANH MỤC HÌNH 4
LỜI MỞ ĐẦU 5
CHƯƠNG I: TỔNG QUAN VỀ MẠNG MANET 6
1.1 Giới thiệu về mạng Manet 6
1.2 Đặc điểm 7
1.2.1 Một mạng MANET bao gồm các hạ tầng di động 7
1.2.2 Thay đổi đồ hình mạng liên tục 7
1.2.3 Tính tự thiết lập 8
1.2.4 Môi trường mạng không dây 8
1.3 Phân loại 9
1.4 Các giao thức định tuyến 10
1.4.1 Khái niệm định tuyến 10
1.4.2 Một số yêu cầu định tuyến 10
1.4.3 Các giao thức định tuyến theo bảng 11
1.4.4 Các giao thức định tuyến theo yêu cầu 12
1.4.5 Giao thức định tuyến lai ghép 12
1.5 Ứng dụng mạng Manet 13
CHƯƠNG II: TÌM HIỂU VỀ GIAO THỨC AODV 14
2.1 Khái quát 14
Giao thức AODV (Ad hoc On Demand Distance Vector): 14
Cơ chế tạo thông tin định tuyến (Route Discovery): 14
Cơ chế duy trì thông tin định tuyến: 17
2.2 Bảng định tuyến 17
2.2.1 Xây dựng bảng định tuyến 17
2.2.2 Quản lý bảng định tuyến 20
MAC Medium Access Control Điều khiển truy nhập môi trường
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
3
RREP Router Reply Hồi đáp truyền tin
RREQ Router Request Yêu cầu truyền tin
RM Router Maintenance Duy trì tuyến
TC Topology Control Điều khiển cấu hình mạng
WLAN Wireless Local Area Network Mạng cục bộ không dây
TORA Temporally Ordered Routing
Algorithm
Thuật toán thứ tự định tuyến tạm
thời
DSDV Destination-Sequenced Distance
Vector routing
Điểm đến sắp xếp trình tự Distance
Vector tuyến
NS Network Simulator
Mạng Similator
RRER Router Error Lỗi định tuyến
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
5LỜI MỞ ĐẦU
Ngày nay cùng với xu hướng phát triển chung mạng không dây đã và đang được ứng
dụng rộng rãi trong cuộc sống bởi lợi ích mà nó mang lại . Số lượng các thiết bị dùng
cho mạng không dây sẽ sớm vượt qua số lượng các thiết bị dùng cho mạng có dây, điều
này cũng đồng nghĩa với sự nghiên cứu, tìm hiểu về mạng không dây cũng tăng trưởng
tương tự và sau đây thì em xin được trình bày về đề tài công nghệ mạng không dây
Manet và tìm hiểu rõ hơn về một trong những giao thức định tuyến trên mạng này đó là
giao thức AODV. Để hoàn thành bài khóa luận này em xinh chân thành cảm ơn thầy
giáo Hoàng Thanh Hải, giảng viên khoa CNTT – Trường Cao Đẳng Công Nghiệp Huế
đã chỉ bảo tận tình và giúp đỡ em trong suốt quá trình làm bài khóa luận. Trong quá trình
làm khóa luận do điều kiện về thời gian và trình độ có hạn nên không tránh khỏi những
thiếu sót. Vì vậy em rất mong nhận được những ý kiến, chỉ bảo của các thầy cô, các ý
kiến đóng góp của bạn bè để em có thể kịp thời bổ sung, sữa chửa những thiếu sót của
mình.
Em xin chân thành cảm ơn.
Huế, tháng 4/ 2013
Sinh viên
Phan Cảnh Hợp
Hiện có rất nhiều ứng dụng được triển khai trong môi trường mạng ad-hoc như:
ứng dụng trong mạng sensor (sensor network) - phân bố các sensor trên 1 cánh đồng,
một thành phố,… để thu thập dữ liệu (nhiệt độ, thời tiết, độ ẩm, ) gởi về trung tâm,
home network – người dùng có thể điều khiển các thiết bị trong nhà của mình khi đang
di chuyển trên đường, …
1.2 Đặc điểm
1.2.1 Một mạng MANET bao gồm các hạ tầng di động
Ví dụ một router với nhiều host và thiết bị truyền thông vô tuyến, ở đây được gọi
là các nốt (node), đang di chuyển tự do. Các nốt có thể được đặt trên máy bay, tầu thủy,
xe kéo, ô tô hoặc được mang theo người hay các thiết bị nhỏ, và có thể bao gồm nhiều
host trên một router. Một mạng MANET là một hệ thống các nốt di động tự trị. Hệ thống
có thể hoạt động độc lập hoặc có thể có cổng để giao tiếp với mạng cố định. Trong chế
độ tiếp với mạng cố định, mạng MANET hoạt động như một mạng “đuôi” liên kết với
một mạng internet cố định. Các mạng “đuôi” truyền lưu lượng xuất phát hoặc đến các
nốt trong mạng, nhưng không cho phép truyền lưu lượng ngoài chuyển tiếp qua mạng.
Các nốt mạng MANET bao gồm các bộ phát và bộ thu sử dụng ăng ten mọi hướng để
phát quảng bá hoặc ăng ten định hướng để phát điểm-điểm, có thể điều chỉnh được, hoặc
kết hợp các loại ăng ten này. Tại một thời điểm nào đó, tùy thuộc vào vị trí của các nốt
và vùng phủ sóng bộ thu và bộ phát của chúng, mức công suất phát và mức nhiễu đồng
kênh, một kết nối vô tuyến dưới dạng ngẫu nhiên, đồ thị nhiều chặng hay mạng ad hoc
tồn tại giữa các nốt. Cấu hình adhoc này có thể thay đổi theo thời gian khi các nốt di
chuyển hoặc điều chỉnh các thông số thu phát của chúng.
1.2.2 Thay đổi đồ hình mạng liên tục
Một trong những đặc trưng quan trọng của môi trường mạng không dây di động
ad-hoc là sự thay đổi trạng thái thường xuyên và nhanh chóng của các nút mạng cũng
như các liên kết giữa các nút mạng. Một nút mạng có thể gia nhập hoặc tách khỏi mạng
tại bất kỳ thời điểm nào. Các nút mạng có thể di chuyển tự do dẫn đến các liên kết giữa
các nút mạng thay đổi liên tục. Vì vậy, đồ hình mạng (network topology) trong môi
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
9
1.3 Phân loại
Do các đặc điểm của mạng MANET (di động, vô tuyến, không dự tính trước) nên
việc xác định các thành phần của một mạng MANET là rất khó khăn, nếu không nói là
không thể trong một số trường hợp nhất định.
Thay đổi
theo thời
gian
Hình 1.1: Mạng Manet
Tại một thời điểm mạng MANET có thể bao gồm một số nốt nào đó, nhưng tại
thời điểm sau đó mạng này có thể chia thành nhiều mạng MANET. Sau đó nó lại có thể
nhập lại thành một nhóm mới các node và tạo thành mạng MANET lớn hơn.
Các router nhất định trong một mạng MANET có thể kết nối với các vùng định
tuyến khác nhau. Các router này được gọi là router biên BR (border router), và chúng
thường chạy nhiều giao thức định tuyến. Các router biên có nhiệm vụ lựa chọn thông tin
định tuyến để thông báo giữa các vùng định tuyến liên quan đến nhau. Router biên cũng
cho thấy các router có thể tiếp cận được thông qua nó. Khi các thành viên trong mạng
MANET thay đổi, thì kết nối của các router biên trong mạng MANET cũng thay đổi. Do
vậy, rất khó để router biên có thể thể hiện tập hợp cố định các nốt tiếp cận được
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
10
(reachable node). Nó có thể lựa chọn không thông báo bất kì thông tin định tuyến nào về
1.4.3 Các giao thức định tuyến theo bảng
Trong phương pháp định tuyến theo bảng, các node trong mạng MANET liên tục
đánh giá các tuyến tới các node để duy trì tính tương thích, cập nhật của thông tin định
tuyến. Vì vậy, một node nguồn có thể đưa ra một đường dẫn định tuyến ngay lập tức khi
cần. Trong các giao thức định tuyến theo bảng, tất cả các node cần duy trì thông tin về
cấu hình mạng. Khi cấu hình mạng thay đổi, các cập nhật được truyền lan trong mạng
nhằm thông báo sự thay đổi. Hầu hết các giao thức định tuyến theo bảng đều kế thừa và
sửa đổi đặc tính tương thích từ các thuật toán chọn đường dẫn ngắn nhất trong các mạng
hữu tuyến truyền thống. Các thuật toán định tuyến theo bảng được sử dụng cho các node
cập nhật trạng thái mạng và duy trì tuyến bất kể có lưu lượng hay không. Vì vậy, tiêu đề
thông tin để duy trì cấu hình mạng đối với các giao thức này thường là lớn. Một số giao
Các giao thức định tuyến trong
Manet
Theo yêu
cầu
Theo bảng Lai ghép
AODV
WPR ZPR ZHLS HARP CLSR DSDV
DSR TORA
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
12
thức định tuyến điển hình theo bảng trong MANET gồm: Giao thức định tuyến không
dây WRP (Wireless Routing Protocol), định tuyến vector khoảng cách tuần tự đích
DSDV (Destination Sequence Distance Vector), định tuyến trạng thái tối ưu liên kết
OLSR (Optimized Link State Routing), định tuyến trạng thái góc rộng (fisheye (Fisheye
State Routing), v.v.
1.4.4 Các giao thức định tuyến theo yêu cầu
Packet Radio Networking), mạng lưới di động (Mobile Mesh Networking) và kết nối
mạng vô tuyến, nhiều chặng, di động (Mobile, Multihop, Wireless etworking). Vấn đề
nổi trội của kết nối mạng di động với sự nhấn mạnh về hoạt động của giao thức IP di
động sẽ được mở rộng dần và yêu cầu công nghệ kết nối di động có khả năng tương
thích cao để có thể quản lý hiệu quả các nhóm mạng ad hoc nhiều chặng, trong đó các
nhóm mạng có thể hoạt động độc lập hoặc cũng có thể kêt nối với một số điểm Internet
cố định. Các ứng dụng của công nghệ MANET có thể bao gồm các ứng dụng công
nghiệp và thương mại liên quan đến trao đổi dữ liệu di động có tính chất cộng tác lẫn các
máy. Ngoài ra, các mạng di động cấu hình lưới có thể được vận hành một cách hiệu quả
dưới dạng mạng thay thế hoặc mạng mở rộng của mạng di động tổ ong. Việc kết nối
mạng trong quân đội cũng yêu cầu các dịch vụ dữ liệu IP trong các mạng truyền thông di
động vô tuyến, nhiều mạng trong số này bao gồm các phần với cấu hình mạng tự trị với
tính động cao. Bên cạnh đó, sự phát triển của các công nghệ tính toán và truyền thông có
thể cung cấp các ứng dụng cho các mạng MANET. Khi được kết hợp một cách hợp lý
với truyền thông vệ tinh, mạng MANET có thể cung cấp các phương thức cực kỳ linh
hoạt trong việc thiết lập truyền thông cho hoạt động cứu hỏa, cứu thương, khắc phục sự
cố tai nạn hoặc các trường hợp cần triển khai mạng thật nhanh chóng để phục vụ tức thì. Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
14
CHƯƠNG II: TÌM HIỂU VỀ GIAO THỨC AODV
2.1 Khái quát
Giao thức AODV (Ad hoc On Demand Distance Vector):
Khi nhận được một gói tin RREP gửi từ nút đích để trả lời gói tin RREQ, nó
sẽ cập nhật lại giá trị Sequence number lớn nhất của một trong 2 giá trị: Sequence
number hiện hành mà nó lưu giữ đối với Sequence number trong gói RREQ
Đối với REQ_ID: Khi có một sự thay đổi trong toàn bộ các nút lân cận của nó
dẫn đến sẽ có một số tuyến đường trong bảng định tuyến sẽ không còn hiệu lực. Số
REQ_ID sẽ được tăng lên khi node khởi động một tiến trình route discovery mới.
Hình 2.1 Các trường trong gói tin RREQ
Tiến trình Route Discovery được khởi động khi nào một node muốn trao đổi dữ
liệu với một node khác mà trong bảng định tuyến của nó không có thông tin định tuyến
đến node đích đó. Khi đó tiến trình sẽ phát broadcast một gói RREQ cho các node láng
giềng của nó. Thông tin trong RREQ ngoài địa chỉ đích, địa chỉ nguồn, số hop-count
(được khởi tạo giá trị ban đầu là 0),… còn có các trường: số sequence number của node
nguồn, số broadcast ID, giá trị sequence number được biết lần cuối cùng của node đích.
Khi các node láng giềng nhận được gói RREQ, nó sẽ kiểm tra tuần tự theo các bước:
Bước 1: Xem các gói RREQ đã được xử lý chưa? Nếu đã được xử lý thì nó sẽ
loại bỏ gói tin đó và không xử lý thêm. Ngược lại chuyển qua bước 2.
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
16
Bước 2: Nếu trong bảng định tuyến của nó chứa đường đi đến đích, thì sẽ
kiểm tra giá trị Destination sequence number trong entry chứa thông tin về đường đi với
số Destination sequence number trong gói RREQ, nếu số Destination sequence number
trong RREQ lớn hơn số Destination squence number trong entry thì nó sẽ không sử dụng
thông tin trong entry của bảng định tuyến để trả lời cho node nguồn mà nó sẽ tiếp tục
phát Broadcast gói RREQ đó đến cho các node láng giềng của nó. Ngược lại nó sẽ phát
Unicast cho gói RREP ngược trở lại cho node láng giềng của nó để báo đã nhận gói
RREQ. Gói RREP ngoài các thông tin như: địa chỉ nguồn, địa chỉ đích,… còn chứa các
thông tin: destination sequence number, hop-count, TTL. Ngược lại thì qua bước 3.
nhận được gói tin này.
Sau khi nhận thông báo này, các node sẽ xóa tất cả các đường đi có chứa node
hỏng, đồng thời có thể sẽ khởi động lại tiến trình Route discovery nếu nó có nhu cầu
định tuyến dữ liệu đến node bị hỏng đó bằng cách gởi một gói tin RREQ (với số
Sequence number bằng số Sequence number mà nó biết trước đó cộng thêm 1) đến các
node láng giềng để tìm đến địa chỉ đích.
2.2 Bảng định tuyến
2.2.1 Xây dựng bảng định tuyến
AODV (Ad hoc On-Demand Distance Vector) là sự kết hợp giữa hai giao thức
định tuyến DSDV và DSR. Cũng giống DSR , trong giao thức định tuyến khi các node
có nhu cầu trao đổi dữ liệu.
AODV vẫn sử dụng cơ chế tìm đường như trong DSR là sử dụng tiến trình route
discovery. Tuy nhiên, AODV còn sử dụng nhiều cơ chế khác để duy trì thông tin bảng
định tuyến. Nó sử dụng bảng định tuyến truyền thống để lưu trữ thông tin định tuyến
với mỗi entry cho một địa chỉ đích. Điều đó trái ngược với giao thức DSR , có thể duy
trì nhiều entry cho một điạ chỉ đích.
Không sử dụng source route và chỉ cần biết thông tin về các node láng giềng của
nó, AODV dựa trên các entry của bảng định tuyến để phát gói RREP về node nguồn và
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
18
node nguồn dùng thông tin đó để gởi dữ liệu đến đích. Để đảm bảo rằng thông tin trong
bảng định tuyến là mới nhất thì AODV sử dụng khái niệm destination sequence number
của giao thức định tuyến DSDV để loại bỏ những đường đi không còn giá trị trong bảng
định tuyến. Mỗi node sẽ có một bộ tăng số sequence number riêng cho nó. Các cơ chế
chính của AODV :
Cơ chế tạo thông tin định tuyến (route discovery)
Mỗi node luôn có hai bộ đếm (counter): bộ đếm số sequence number và bộ đếm
destination sequence number ,hop-count, TTL. Ngược lại thì qua bước 3.
Nếu trong bảng định tuyến của nó không có đường đi đến đích thì nó sẽ tăng
số hop-count lên 1, đồng thời nó sẽ tự động thiết lập một đường đi ngược (reverse path )
từ nó đến node nguồn bằng cách ghi nhận lại địa chỉ của node láng giềng mà nó nhận gói
RREQ lần đầu tiên.
Entry chứa đường đi ngược này sẽ được tồn tại trong một khoảng thời gian đủ để
gói RREQ tìm đường đi đến đích và gói RREP phản hồi cho node nguồn, sau đó entry
này sẽ được xóa đi. Các thông tin bao gồm :
+ Địa chỉ đích
+ Địa chỉ nguồn
+ Số REQ_ID
+ Thời gian timeout cho việc chờ đợi thời gian nhận gói RREP
+ Số sequence number của node nguồn
Sau đó phát broadcast đến các node láng giềng của nó.
Và quá trình trên cứ lặp lại cho đến khi gặp node đích hoặc một node trung gian
mà có các điều kiện thỏa bước 2.
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
20
Trong quá trình trả về gói RREP, một node có thể nhận cùng lúc nhiều gói
RREP, khi đó nó sẽ chỉ xử lý gói RREP có số destination sequence number lớn nhất,
hoặc nếu cùng số destination sequence number thì nó sẽ chọn gói RREP có số hop-count
nhỏ nhất. Sau đó nó sẽ cập nhật các thông tin cần thiết vào trong bảng định tuyến của nó
và chuyển gói RREP đi.
Cơ chế duy trì thông tin định tuyến (Route Maintenance )
Khi một node nhận thấy rằng next hop của nó không thể tìm thấy, thì nó sẽ phát
một gói RREP khẩn cấp với số sequence number bằng số sequence number trước đó
cộng với 1, và hop count bằng và gởi đến tất cả các node láng giềng đang ở trạng thái
đường dẫn từ một nguồn tới một điểm đến, tiếp theo là các gói dữ liệu dọc theo mục
tuyến đường hoạt động, được gọi là một đường dẫn hoạt động. Lưu ý rằng, với DSDV,
tất cả các tuyến trong bảng định tuyến được gắn thẻ với số thứ tự đích, đảm bảo rằng
không có vòng lặp định tuyến có thể hình thành, ngay cả dưới điều kiện khắc nghiệt của
cung cấp gói out-of-trật tự và tính di động nút cao.
Một nút di động duy trì một mục bảng định tuyến cho mỗi điểm đến quan tâm.
Mỗi mục bảng định tuyến có chứa các thông tin sau:
• Điểm đến
• Next Hop
• Số lượng hoa bia (metric)
• Trình tự số cho điểm đến
• hàng xóm đăng nhập cho tuyến đường này
• hết hạn thời gian cho các mục nhập bảng định tuyến
Mỗi khi một mục tuyến đường được sử dụng để truyền tải dữ liệu từ một nguồn
tới đích, thời gian chờ cho mục được thiết lập lại đến thời điểm hiện tại cộng với hoạt
động -roui e-tim eoui.
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
22
Nếu một tuyến đường mới được cung cấp cho một nút điện thoại di động, các nút
di động so sánh số thứ tự điểm đến của các tuyến đường mới để các điểm đến số thứ tự
cho các tuyến đường hiện tại. Tuyến có số thứ tự lớn hơn được chọn. Nếu số thứ tự là
như nhau, sau đó các tuyến đường mới đã được chọn chỉ khi nó có nhỏ hơn (số ít hoa
bia) số liệu đến đích.
2.2.3 Bảo trì
Phong trào của các nút không nằm dọc theo một con đường hoạt động không ảnh
hưởng đến việc định tuyến đến đích của con đường đó. Nếu nút nguồn di chuyển trong
một phiên hoạt động, nó có thể bắt đầu lại các thủ tục khám phá tuyến để thiết lập một
tuyến đường mới đến đích. Khi một trong hai điểm đến hoặc di chuyển một số nút trung
trong HelloInterval, chương trình phát sóng với các nước láng giềng tin hello (đặc biệt
không được yêu cầu RREP), có bản sắc của mình và số thứ tự. Số thứ tự của nút là
không thay đổi cho việc truyền tải tin nhắn chào. Thông điệp này xin chào bị ngăn cản
không được phát sóng lại bên ngoài vùng lân cận của các nút bởi vì nó có chứa một thời
gian sống (TTL) giá trị là 1. Hàng xóm nhận được gói tin này cập nhật thông tin kết nối
địa phương để nút. Nhận phát sóng hoặc hello từ một người hàng xóm mới, hoặc không
nhận được thông điệp liên tiếp allowed.Jh.elloJ.oss hello từ một nút trước đó trong khu
phố, là một dấu hiệu cho thấy các kết nối địa phương đã thay đổi. Không nhận được tin
nhắn chào từ các nước láng giềng không hoạt động không kích hoạt bất kỳ hành động
giao thức. Nếu thông điệp chào không nhận được từ hop tiếp theo cùng một con đường
hoạt động, những người hàng xóm đang hoạt động bằng cách sử dụng mà hop tiếp theo
được gửi thông báo lỗi liên kết.
Việc quản lý kết nối địa phương với những thông điệp chào cũng có thể được sử
dụng để đảm bảo rằng các nút duy nhất với kết nối hai chiều được coi là hàng xóm. Đối
với mục đích này, mỗi hello được gửi bởi một nút liệt kê các nút mà từ đó nó đã nghe.
Mỗi nút kiểm tra để chắc chắn rằng nó sử dụng các tuyến đường duy nhất cho những
người hàng xóm đã nghe tin nhắn chào của nút. Để tiết kiệm băng thông địa phương,
kiểm tra như vậy cần phải được thực hiện chỉ khi cấu hình một cách rõ ràng vào các nút.
Đề tài Tìm hiểu về giao thức định tuyến AODV trong mạng Manet
Sinh viên: Phan Cảnh Hợp Giáo viên hướng dẫn: Hoàng Thanh Hải
24
2.3 Ví dụ
Node 1 muốn trao đổi thông tin đến node 4 nhưng không có tuyến đường đi đến
đó, node 1 sẽ gởi một RREQ với những thông tin :
RREQ ID để nhận biết gói tin RREQ là đã này đã được xử lí chưa, nếu đã có
nó sẽ loại bỏ gói tin (số RREQ ID được tăng lên khi node gởi một gói RREQ mới).
Địa chỉ ip và số sequence number node 4 (đích).
Hình 2.3: Ví dụ một cơ chế route discovery
Copyright: Tài liệu đại học ©