Thuật toán quảng bá lại thông tin Định tuyến nhằm tối thiểu hoá chi phí Định tuyến trong mạng ad hoc di Động

Một con đường “đủ mới” là một con đường tới đích hợp lệtrong bảng định tuyến có một số thứ tự ít nhất là bằng với số thứ tự chứa trong thông điệp RREQ.. Để khẳng định rằng thông tin về m

ĐẠT HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Lê Hồng Sơn

THUAT TOAN QUANG BA LAI THONG TIN DINH TUYEN NHAM TOI THIEU HOA CHI PHi DINH TUYEN

TRONG MANG AD HOC DIDONG

LUẬN VĂN THẠC SĨ KHOA HOC MAY TINH

‘Thai Nguyên - 2020

ĐẠT HỌC THÁI NGUYÊN TRUONG DAIHOC CONG NGHE THONG TIN VA TRUYEN THONG

LUẬN VĂN THẠC Si KHOA HOC MAY TINH

NGUOIHUONG DAN KHOA HOC

TS ĐỖ ĐÌNH CUC

ad hoc di động” tôi đã nhận được sự giúp đỡ, chỉ bão nhiệt tỉnh của các thầy,

cô giáo thuộc Trường Đại học Công nghệ thông tin và Truyền thông — Đại hoc

"Thái Nguyên để hoàn thành luận văn này

'Với tình cảm chân thành, tôi xin bày tỏ lòng biết ơn đối với Ban giám

hiệu, phòng Đào tạo, Khoa Công nghệ thông tin, các thả

Trường Đại học Công nghệ thông tin và Truyền thông — Dai học Thái Nguyên

giáo, cô giáo thuộc

đã tham gia quản lý, giảng đạy và giúp đỡ tôi trong suốt quá trình học tập,

nghiên cứu

Tôi xin bày tô sự biết ơn đặc biệt đến Thây TS Đỗ Đình Cường - người

đã trực tiếp hướng đẫn, giúp đỡ về kiến thức, tài liệu và phương pháp để tôi

hoàn thành đề tài luận văn thạc sĩ này

"Tôi cũng xin chân thành cảm ơn gia đỉnh, bạn bè, đồng nghiệp đã động

viên, cỗ vũ, khích lệ và giúp đỡ tôi trong suốt thời gian qua

Mặc đù đã có nhiều cổ gắng trong suốt quá trình thực hiện đề tài, song có thể còn có những mặt hạn chế, thiểu sot Tôi rất mong nhận được ý kiến đóng gốp và sự chỉ dẫn của các thây cô giáo và các bạn đồng nghiệp đề luận văn

được hoàn thiện

(guyên, ngày tháng năm 2020

Học viên

Lê Hồng Sơn

MUCLUC

MỠ ĐẦU

CHƯƠNG 1 TONG QUAN VE MANG AD HOC VA UNG DUNG

1.1 Téng quan vé mang ad hoc

1.1.1 Định nghĩa và đặc trưng của mạng ad hoc

1.1.2 Đặc điểm của mạng ađ học

1.1.3 Ứng dụng của mang ad hoc

1.2 Giao thức định tuyến AODV trong mạng ad hoc

1.2.1 Đặc điểm chung của giao thức định tuyến AODV

1.2.2 Cơ chế hoạt động của giao thức AODV

1.3 Một số phương pháp cải tiến cơ chế quảng bá thông tin định tuyến 1.3.1 Vấn đề bão quảng bá của giao thức AODV

1.3.2 Phương pháp sử dụng các bộ đếm thời gian

1.3.3 Phương pháp khám phá đường theo xác suất

1.3.4 Phương pháp định tuyến đa đường

4 Tinh xc suất quảng bá

5 Trién khai phân cụm ão LVC

7 Chu kỳ hiệu lực của liên kết LEP

(6 Thuật toán quảng bá lại dựa trên thông tin nút lân cận

3.1 Các tham số mô phông và độ đo đánh giá hiệu năng

3.1.1 Các tham số mô phỏng

3.1.1 Các độ đo đánh giá hiệu năng

3.2 Đánh giá về tỉ lệ quảng bá

3.2.1 Tỉ lệ quảng bá theo lưu lượng mạng

3.2.2 Tỉ lệ quãng bá theo số nút mang

3.2.3 Tỉ lệ quãng bá theo vận tốc di ch

3.2.4 Tỉ lệ quảng bá theo băng thông yêu cầu

3.3 Đánh giá về chỉ phí định tuy:

3.3.1 Chỉ phí định tuyến theo số nút mạng

3.3.2 Chỉ phí định tuyến theo vận tốc đi chuyển

3.4 Đánh giá về tỉ lệ tái liên kết

TAI LIEU THAM KHẢO

ic

“Cường độ tia hiệu từ N1 đến các nit Ling giéng,

Giá trị các tham số mô phông

"Dữ liệu về tỉ lệ quảng bá theo lưu lượng mạng

Dữ liệu về tỉ lệ quảng bá theo số lượng nút mạng

Dữ liệu về tỉ lệ quảng bá theo vận tốc đi chuyển

Dữ liệu về tỉ lệ quảng bá theo băng thông yêu cầu

Dữ liệu về chỉ phí định tuyến theo số nút mạng

Dữ liệu về chỉ phí định tuyến theo vận tốc đi chuyển

Dữ liệu về tỉ lệ tái liên kết theo phạm vi truyền

4

4

Wwubibb

"Hình 1.2 Vi du minh hoa mang ad hoc trén xe bus

"Hình 1.3 Mét vi du cia mang Rooftop

Hình 1.4 Cấu trúc gói RREQ

Hình 1.5 Cấu trúc gói RREP

Hình 1.6 Cấu trúc gói RRER

Hình 2.1 Sơ đồ ý tưởng của phương pháp

Hình 2.2 Tiền trình yêu cầu đường

Hình 2.3 Truyền đữ liệu trên cơ sở hệ số kết nồi

Tình 2.4 Quá trình truyền sử đụng LVC

"Hình 2.5 Thủ tục truy vấn đường

"Hình 2.6 Thủ tục trả lời đường

"Hình 2.7 Hình trạng mạng cho thủ tục truy v

"Hình 2.8 Lập lịch cho chu kj truyén dữ liệu

Hình 3.1 Biểu đồ tỉ lệ quảng bá theo lưu lượng mạng

và trả lời đường,

Hình 3.2 Biểu đồ tỉ lệ quảng bá theo số nút mạng

Hình 3.3 Biêu đồ tỉ lệ quảng bá theo tốc độ di chuyên

Hình 3.4 Biêu đồ tỉ lệ quảng bá theo băng thông yêu cầu

Hình 3.5 Biêu đô chỉ phí định tuyến theo số lượng nút mạng

Hình 3.6 Biêu đô chỉ phí định tuyến theo vận tốc đi chuyên đi chuyển Hình 3.7 Biêu đô tỉ lệ tái liên kết theo phạm vi truyền thông.

MỠĐẦU Một mạng ad hoc di động là một tập hợp các nút không đây di động làm

việc cùng nhau Loại mạng này có thể hoạt động mà không cần cơ sở hạ tầng mạng để thực hiện kết nói và chúng có thể hoạt động theo kiểu tự quản Do các nút là thiết bị đi động nên việc các liên kết có thể bị phá vỡ tại bất kỳ thời điểm

ào theo định hướng di chuyễn trong không gian của các nút Hai nút đi động

nằm ngoài phạm vi truyền thông vẫn có thể giao tiếp với nhau qua sự trợ giúp

của các thiết bị khác trong phạm vĩ truyền thông của chúng Mạng ad hoc di động cung cấp khả năng truyền thông cho các khu vực thiếu hoặc không có cơ

sở hạ tầng truyền thông Loại mạng này không sử đụng cơ sở hạ tằng mạng cố định Nó sử đụng cơ chế định tuyến đa chặng để cung cấp kết nối mạng Việc truyền thông trong mạng có thê được thực hiện khi sử đụng các giao thức định tuyến để để khám phá đường động Khi đường truyền thông đã được thiết lập,

đữ liệu sẽ được chuyển tiếp Thủ tục bảo trì đường được sử dụng để thiết lập

lại mạng cho môi trường động Hiệu suất của mạng đối với người đùng là vấn

đề quan trọng để duy trì chất lượng địch vụ

"Trong kịch bản truyền thông đa chặng, các gói dữ liệu xuất phát từ nút

nguên được các nút trung gian chuyên tiếp tới nút đích Do tính đi động của các nút trong mạng ad hoc đi động, các tuyến đường có thể sẽ bị lỗi làm kích hoat tién trình khám phá đường Điều này làm tăng tré đầu cuối, giảm tỷ lệ phân

phối thành công đữ liệu và quan trọng hơn là tăng chỉ phí hoạt động của các

giao thức định tuyến Do đó, việc giãm chỉ phí định tuyến trong quá trình khám

kỹ thuật trong ad hoc di

phá đường là một yếu tổ thiết yéu trong mang ad hoc di déng Mét

định tuyến đa đường được sử đụng để giảm chỉ phí định tuy

động thông qua khả năng cân bằng tải, tăng thông lượng và các khả năng chịu

lỗi Vấn đ loại bỏ các điểm tắc cô chai là van đề chính cần thực hiện nhằm tối

định tuyến là để cãi thiện hiệu quả của việc truyền thông điệp thành công Bằng cách cải thiện tí ệ truyền thành công, các gối dữ liệu sẽ được truyền từ nút đầu tới nút cuối Tuy nhiên, đối với các phương pháp định tuyến đa đường, chưa có

nhiều phương pháp hiệu quả nhằm giảm thiểu chỉ phí định tuy

ến ôn định được thực

các thiết bị đầu cuối khả năng và tạo ra cơ chế định

"hiện bằng cách tăng thời gian hoạt động của các nút mạng Đ tài sẽ nghiên cứu

về các thuật toán mới được đề xuất dé đự đoán liên kết đựa trên thông tin quảng

bá lại của các nút lân cận Phương pháp phân cum do cũng được nghiên cứu

trong đề tài ngày để giảm thiêu chỉ phí định tuyến Nó được sử đụng nhằm cải thiện cơ chế điều khiễn cấu trúc mạng để tối thiêu hoá chỉ phí định tuyết tăng thông lượng mạng bằng cách giảm tằn sĩ

Cấu trúc luận văn được trình bày như sau: Chương 1 trình bày tổng quan

về mạng ađ hoc, giao thức định tuyến AODV và một số phương pháp cải tiến

cơ chế quảng bá thông tin định tuyến của giao thức AODV Phương pháp và

thuật toán cải tiền thuật toán quảng bá định tuyến đựa trên thông tin từ các nút

lân cận sẽ được trình bay chi tit trong Chương 2 Kết quả của việc mô phông,

so sánh đánh giá hiệu năng của giao thức NKR ~ giao thức triển khai phương

pháp cải tiến thuật toán quảng bá định tuyến đựa trên thông tin từ các nút lân

cận so với một số giao thức có liên quan được trình bày trong Chương 3 Cuối

cùng là phân kết luận đưa ra những tông kết và hướng phát triển của luận văn.

(CHUONG 1 TONG QUAN VE MANG AD HOC VA UNG DUNG 1.1 Tổng quan về mạng ad hoc

LLL Dinh nghĩa và đặc trưng cũa mạng ad hoc

Theo dinh nghĩa của Tổ chức IETF (Intemet Engineering Task Force), Mang ad hoc không đây di động là một vùng tự trị (Autonomous System) của

các bộ định tuyến được kết nối với nhau bằng liên kết không đây Mỗi nút mạng vừa đóng vai trò là thiết bị đầu cuối vừa đồng vai trò là bộ định tuyến Các nút

liên tục,

Hinh 1.1 Minh hoa mang ad hoc di dong

"Như vậy có thể thấy mạng ađ hoc đi động bao gồm tập các nút không đây

đi độ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ó day Mỗi nút đi động có một phạm vỉ truyền

giới hạn, đo đó chúng cần sự trợ giúp của các nút láng giềng đẻ chuyên tiếp các

gi đữ liệu

Hình 1.1 là một ví đụ minh họa cho một mạng ad hoc đi động Trong ví

đụ này, các gói tin từ nút nguồn là một máy tính cần chuyển tới một nút đích là

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

phù hợp cho mạng ad hoc đi động, Trong mạng ad hoc, liên kết giữa các nút mạng được đặc trưng bởi khoảng cách giữa các nút và tính sẵn sàng hợp tác để tạo thành mạng mặc đủ

14 tạm thời Để triển khai thành công được mạng ađ hoc, thiết kế và công nợi

mạng phải đáp ứng được các yêu cầu sau:

—_ Đảm bảo kết nối khi nút mạng đi chuyên: Khoảng cách giữa các nút hoặc trạng thái ở gần nhau của chúng định nghĩa ranh giới mạng Chỉ cần hai hoặc nhiều nút chuyên động trong một bán kính nhất định là tạo thành một mạng ad-hoc Chính sự chuyên động làm cho khoảng cách giữa các nút thay đổi gây ra bản chất đặc biệt (a-hoc) của mạng

— Tinh sin sàng hợp tác: Các nút ở trong khoảng cách đủ gần phải sẵn sàng hợp tác để tạo thành mạng Nói cách khác, tự bản thân nút quyết định

“online” hay “offline”

~ Mang ngang hàng tạm thời: Tại bất cứ một thời điểm nào, mạng ad-hoc được xác định bởi các nút đang “online” va ở trong một khoảng cách nhất

1.1.2 Đặc điêm của mang ad hoc

Do ad hoc la mét mạng không day 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ị đi động vừa

dong vai trò là thiết bị đầu cuối, vữa đồng vai trò là bộ định tuyến nên mạng ad

hoc còn cô một số đặc điểm nỗi bật sau [1 1]:

—_ 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 ađ học 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

hỗ hơn so với các liên kết có đâ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 đâ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 đây

—_ Các nút mạng có tài nguyên hạn chế: Mỗi nút đi động trong mạng ađ hoc 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

lượng bộ nhớ và năng lượng nguồn pin nuôi

— D6 bio mat thấp ở mức độ vật tý: Mạng không day đi đông thường chịu tác

động về mặt vật

mạng có đâ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

ý từ các nguồn gây nguy hại về an ninh nhiều hơn so với

‘ing dung trong những điều kiện khô có thể triển khai được một cơ si ha ting mạng cố định hoặc việc triển khai là không khả thi do những lý do về mặt thực

"hành (địa hình ) hoặc do những lý đo

gian lớn, chỉ phí thiết lập nhiều điễm truy

'kinh tế (chỉ phí cáp trong một không

4p)

> Ung dung trong quân đội

"Những thành tựu mới của công nghệ thông tin thường được áp đụng trong quân sự đầu tiên, và mạng không day kiéu không cấu trúc cũng không phải là

một ngoại lệ Nhiều năm nay, quân đội đã sử đụng các mang “packet radios” —

một nguyên mẫu đầu tiên của mạng chuyển mạch gói không đây ngày nay

"Mang ađ hoc thuần túy thường tuân theo một mô hình điễm ngẫu nhiên, các nút tự đo đi chuyển theo bất cứ hướng nào, với bắt cứ tốc độ nào Trong

mô hình mạng ad hoc cho quân đội, các mút phân nhóm theo bản chất tự nhiên của chúng khi chúng cùng thực hiện một nhiệm vụ cụ thé Xu hướng di đội đây là theo nhóm

gỡ

Do đó, nếu đưa ra được một mô hình chuyển động theo nhóm, các vấn

đề của mạng ađ hoc sẽ trở nên cu thé hon (vi du: định tuyến, sử dụng các ứng dung thời gian thực như tiếng néi, video ), cho phép phát triển một giãi pháp

tối ưu

+ Các ứng dụng trong cuộc sống

‘Mang ad hoc rit lý tưởng trong các trường hợp không có sẵn một cơ sở 'hạ tầng thông tin, tuy nhiên lại cần phải thành lập một mạng tạm thời nhằm trao đổi thông tin và hợp tác cùng làm việc.

Tại các vũng bị thiên tai, thám họa, khó có thể có được một cơ sỡ hạ tầng

về thông tin vững chắc Hệ thống có trước đó rất có thể bị hỏng hoặc bị phá

"hủy hoàn toàn

Tại vùng có thảm họa, tất cã các phương tiện và hệ thống truyền thông đề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, đều được trang bị như một thiết bị đầu cuối đi động — là một phần của mạng

ad-hoc Méi nhân viên cũng 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 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 đi độ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 — đóng vai trò như router

trên Internet,

"Đối với ứng dụng chia sẽ tài nguyên trong hội họp, khác với cách làm

truyền thống khi những người tham gia hội thão muốn chia sẽ tài liệu cho nhau

là gửi ñle đính kèm qua email hoặc sao chép qua các thiết bị lưu trữ thứ cấp có

khả năng đi động, tất cả những người tham đự hội thảo đều có thê sử đụng thiết 'bị đi động để tạo thành một mạng aó-hoc trong suốt thời gian đó Các thiết bị

có thể truyền thông với nhau, truyền/nhận các tài liệu được sử đụng trong hội thảo Khi hội thão kết thúc, các thiết bị được tắt nguồn, mạng tự bị hủy bỏ Đối với ứng đụng trong cuộc sống hàng ngày, môi trường mạng là mạng

ad hoc thuần tủy, tức là không có cơ sở hạ ting về cáp, các thiết bị đầu cuối tự cấu hình để thành lập mạng, mà không cô sự quản lý tập trung Mạng này có thể tự chia nhỏ thành các mạng con Ví du như một mạng riêng giữa em học sinh và bạn của em, một mạng “chung” được khởi tạo bởi người muốn chia sé các chương trình trò chơi điện tử trên máy của anh ta Hai mạng này được trộn

lẫn vào nhau một cách linh động.

Hinh 1.2 Vidu minh họa mạng ad hoc trên xe bus

+ Mạng cam biến

Cam 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 đây và xử lý cục bộ Mạng căm biển là

mạng gồm các nút cảm biến (sensor) — 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ê, vi đụ như: giám sát môi trường (không khi, đất,

nước), theo đõi môi trường sống, hành vỉ, đân số của các loài động, thực vật

đồ tìm động chấn, theo đối tài nguyên, thực hiện trình thâm trong quân đội,

Trước đây mạng cảm biến thường bao gồm một lượng nhỏ các nút cảm biển được kết nối bằng cáp tới một trạm xử lý tập trung Ngày nay, các nút

tạng cảm biến thường là không dây, phân tán để vượt qua các trở ngại vật lý của môi trường, tiết kiệm năng lượng và đo trong nhiều trường hợp không thể

cô được một hạ tầng có sẵn về năng lượng và truyền thông

Công nghệ mạng không day kiéu không cấu trúc thường được áp dung

để triển khai mạng cảm biến đo:

—_ Các nút cảm biến được phân tán trong vùng không có sẵn cơ sở hạ tầng về truyền thông và năng lượng Các nút phải tự hình thành kết nồi

—_ Các nút phải tự tự cầu hình, tự hoạt động trong bất cứ trường hợp nào

—_ Cấu hình mạng luôn có thể thay đổi (các nút cảm biến bị hỏng, các nút mới

được thêm vào, ), mạng cảm biến phải tự thích nghỉ với những thay đổi

này

4 Mang Rooftop

Là một công nghệ đang bùng nỗ để cung cấp truy cập mạng băng thông rộng tới các gia đình, một cách để thay thế ADSL (Asymmetric Digital

Subscriber Line) va các công nghệ tương tự khác Mang rooftop sử dụng công

nghệ mạng ad-hoc để mở rộng phạm vi của một số điểm truy cập - các điểm

này được nối với nhà cung cấp địch vụ Internet (SP) Mỗi người truy cập được

trang bi mét router ad-hoc cho phép chuyên tiếp lưu lượng thay mặt những

người truy cập khác,

Từ khía cạnh ad-hoc, những mạng MANET như vậy là tương đối tỉnh —

cấu hình của mạng hiểm khi thay đồi

Hình 1.3 Một ví dụ của mang Rooftop

+ Mỡ rộng phạm vi của điềm truy cập

"Trong các mạng không dây được sử đụng rộng rãi ngày nay, các nút mạng

đi động được kết nổi với các điểm truy cập theo cấu hình hình sao Đề được kết nối vào mạng, người sử đụng phải ở trong phạm vi truy cập của mạng Do phạm

vi truy cập này là giới hạn và cơ si ha ting mét chặng (one-hop) của cấu hình

này, các điểm truy cập phải được trải rộng trong toàn bộ vũng, bao phủ khắp

những nơi muốn kết nối với nhau

Sir dung mang khôi

\g đây kiểu không cấu trúc, nhu cầu cần các điểm truy

cập sẽ giảm ~ người sử dụng bên ngoài phạm vi truy cập sẽ vẫn có thể được

"tiếp sống” thông qua một hoặc nhiều nút trung gian để truy cập được vào mạng

1.2 Giao thức định tuyến AODV trong mang ad hoc

1.2.1 Đặc diém chung cita giao thite dink tuyén AODV

AODV [2] là một giao thức định tuyến đông, đa chặng và tự khởi động giữa các nút mạng di đông tham gia vào mạng không đây kiêu không cầu trúc AODV cho phép các nút mạng di động tìm được các con đường tới một nút đích nào đô một cách nhanh chông và không yêu cầu các nút đuy trì các con đường tới đích khi không truyền thông AODV cho phép các nút đi động làm việc được với sự thay đổi hình trạng của mạng hoặc liên kết bị đứt

Hoạt động của AODV là hoạt động tránh lặp vòng và cung cắp khả năng nội tụ nhanh khi hình trạng mạng thay đổi Khi một liên kết bị đứt, AODV sẽ gây ra một hiệu ứng để báo cho tập các nút mạng di động biết rằng chúng có thể bỏ tính hiệu lực của các con đường sử đụng liên kết đã bị đứt

"Một đặc điễm khác biệt quan trong của AODDV so với các thuật toán định

'tuyến truyền thống trong mạng có đây là nó sử dụng một số thứ tự đích cho mỗi

một đồng trong bang định tuyến Số thứ tự đích được nút đích tạo ra được đưa vào cùng với các thông tin định tuyến khác và được gửi đi đến nút có yêu cầu

Nút yêu cầu sẽ lựa chọn một con đường có số thứ tự lớn nhất

Các thông điệp yêu cầu đường đi RREQ, đáp ứng đường đi RREP và lỗi

đường đi RERR là các thông điệp được định nghĩa trong AODV Các kiểu

"1

thông điệp này được nhận về qua UDP va công việc xử lý IP header thông thường sẽ được áp dụng Khi một nút muốn xác định một đường đi đến đích,

nó sẽ quảng bá thông điệp RREQ Một con đường có thể được xác định khi

thông điệp RREQ đến được đích của nó hoặc một khi thông điệp RREQ đến

được một nút trung gian có một con đường "đủ mới” đến đích Một con đường

“đủ mới” là một con đường tới đích hợp lệtrong bảng định tuyến có một số thứ

tự ít nhất là bằng với số thứ tự chứa trong thông điệp RREQ Nút chứa con

đường này sẽ gửi thông điệp RREP đạng unicast tới nút yêu cầu đường đi Mỗi

một nút nhận thông điệp RREQ sẽ đưa vào bộ nhớ đệm để hình thành con đường quay trở lại cho thông điệp RREP Thông điệp RREP quay trở lại qua

các nút đã chuyển thông điệp RREQ cho đến khi tới được nút ban đầu yêu cầu

đường đi

Các nút theo dõi trạng thái liên kết của các chặng tiếp theo trong các con

đường hiện hành Khi một liên kết bị đứt trong một con đường hiện hành được phát hiện, một thông điệp báo lỗi RERR sẽ được sử đụng đễ báo cho các nút

khác biết rằng một liên kết đã bị đứt Thông điệp RERR chỉ ra rằng các đích này không thể đi đến được nếu sử dụng liên kêt đã bị đứt Để cho phép thực

hiện được cơ chế báo cáo này, mỗi một nút phải giữ một “đan sách con trỏ

trước”, danh sich này sẽ chứa địa chỉ TP cũa mỗi một nút hàng xôm được sử dung đễ đi đến một đích xác định nào đó

AODV là một giao thức định tuyến và nô thực hiện công việc của mình

'bằng việc quản lý bảng định tuyến Thông tin bảng định tuyến là các con đường

có thời gian tôn tại ngắn, chẳng hạn một con đường tạm được tạo ra đề lưu trữ

đường trở lại các nút phát ra thông điệp RREQ AODV sử đụng các trường sau

cho mỗi một đòng trong bảng định tuyến:

— Địa chỉ IP đích

— Ching tip theo

—_ Danh sách các con trồ trước

— Thời gian sống

để tránh định tuyến

Việc quản lý số thứ tự là một công việc thiết y

vòng, thậm chí khi các liên kết đã bị đứt và một nút không còn cung cấp các thông tin của nô về số thứ tự nữa Một nút đích sẽ trở thành không tới được khỉ

một liên kết bị đứt hoặc không hiện hành Khi những điều kiện này xây ra, một

con đường sẽ bị mắt hiệu lực bis

đồ trong bảng định tuyển là con đường không hợp lệ

1g thao tac gan số thứ tự và đánh đầu con đường

út đích đối với mỗi một đồng trong băng định tuyến khi các nút đuy trì bảng

định tuyến của mình Số thứ tự này được gọi là “số thứ tự đích” Nó được cập

nhật khi một nút nhận được thông tin mới về số thứ tự từ các thông digp RREQ 'RREP hoặc RERR liên quan đến đích AODV phụ thuộc vào mỗi nút trong

13

mạng khi nút này đuy trì các số thứ tự đích của nó nhằm đâm bảo tránh khỏi

việc định tuy

lặp vòng cho mọi con đường đi ra từ nút đó Một nút đích sẽ

tăng số thứ tự của nó trong hai tình huồng:

Trước khi một nút bắt đầu việc khám phá một con đường mới, nỗ phải

tăng số thứ tự của mình Điều này nhằm ngăn căn sự xung đột với các con

đường trước đồ đã được hình thành khi quay trở lại chính nó bằng thông điệp

RREQ

Trước khi một nút đích khởi tạo một thông điệp RREP đễ trả lời thông điệp RREQ mà nó nhận được, nô phải cập nhật số thứ tự của nó bằng một số thứ tự hiện tại lớn nhất và số thứ tự đích cô trong gói tin RREQ

Khi một nút đích tăng số thứ tự của nó, số thứ tự mới phải là số thứ tự chưa được sử dụng lần nào số thứ tự hiện đang sử dụng đã là số lớn nhất

\g 4204967295 với 32 bit số nguyên không dấu), số thứ tự tiếp theo sẽ quay về bằng 0 Nói cách khác, nều một số thứ tự hiện tại có giá trị là

2147483647 là số đương lớn nhất có thê, nếu phép toán lấy phần bù của 2 được

so sánh kết quả của 2 số thứ tự AODV

Để khẳng định rằng thông tin về một đích thông tin mới, một nút phải so

sánh giá trị số thứ tự hiện tại của nó với số thứ tự trong các thông điệp AODV'

mà nó nhận được Việc so sảnh này phải được hoàn tit bing phép toán số học

có đấu Điều này là cần thiết vì quá trình gán số thứ tự là quá trình quay vòng

"Nếu hiệu của số thứ tự nhận được trữ đi số thứ tự hiện tại được lưu trữ là một

số âm thì thông tin liên quan đến đích trong thông điệp AODV sẽ bị bỏ qua

"Một tỉnh huống khác mà một nút có thé thay đổi số thứ tự đích của một

trong các đòng trong bảng định tuyến của nó là tỉnh huống đáp ứng lại việc một liên kết tới một nút tiếp theo đã bị mất hoặc đã quá tên tại quá thời gian

cho phép mà không được cập nhật Nút nay sẽ theo dõi các con đường nào sit

đụng chặng đó làm chặng tiếp theo đề đi đến đích trong bảng định tuyến của

nó Trong trường hợp này, với mỗi một con đường đến đích sử đụng chặng tiếp theo này, nút hiện tại sẽ tăng giá trị số thứ tự và đánh đấu con đường này là

không hợp lệ Bắt cứ khi nào một nút nào đồ nhận được thông tin định tuyến

một đích nào đó được đánh dấu trong bang định tuyến là không hop 1ê, nút này sẽ cập nhật bảng định tuyển của nó theo thông tin mà nó nhận được

Một nút có thê thay đổi số thứ tự trong một đòng của bảng định tuyến

của một đích chỉ khi nếu:

— Ban thân nó là nút đích, và yêu cầu một con đường mới tới chính nó

— Né nhận được một thông điệp AODV với các thông tin mới về số thứ tự của nút đích

— Con đường tiếp theo tới nút đích bị đứt hoặc đã quá hạn thời gian không được cập nhật

+ Băng định tuyến và các danh sách con trỗ trước

“Khi một nút nhận được một gối tin điều khiển AODV từ một nút hing

ôm hoặc cập nhật một con đường tới một đích hoặc một mạng con nào đó, nỗ

sẽ kiếm tra xem trong bing định tuyến đã có đồng nào liên quan đến đích này

hay chưa Trong trường hợp chưa có đòng nào trong bảng định tuyến liên quan đến đích này, một đòng mới sẽ được tạo ra Số thứ tự được xác định hoặc là từ 'thông tin chứa trong gói tin điều khiển, hoặc là từ trường số thứ tự hợp lệ được thiết lập là sai Một con đường chỉ được cập nhật nều một số thứ tự mới là:

@ cao hon sé thir tu dich trong bang dinh tuy

(i _ bing với số thứ tự đích trong bảng định tuyến nhưng số chặng (của thông tin mới) công thêm 1 là nhỏ hơn số chặng hiện tại trong bảng

(ii) số thứ tự chưa được biết đến

Trường Lifetime cia mỗi dòng trong bảng định tuyển được xác định hoặc

là từ gói tin điều khiển hoặc là được khởi tạo ban đả

ACTIVE_ROUTE_TIMEOUT Con dung này giờ đây có thể được sử dụng

t kỹ một gói dữ liệu nào và đáp ứng lại các yêu cẩu tìm đường còn

theo trong con đường đi đến đích sẽ được cập nhật bằng giá trị không nhỏ hơn

ới ACTIVE_ROUTE_TIMEOUT Khi con

đường giữa mỗi một cặp nút nguồn và nút đích được coi là đối xứng, trường -Active Route Lifetime của các chặng trước đó quay ngược trở lại đến nút IP

giá trị thời gian hiện tại cội

nguồn cũng được cập nhật bằng một giá trị không nhỏ hơn giá trị thời gian hiện

tại cộng với ACTIVE_ROUTE_TIMEOUT Giá tri lifetime cho mét Active

'Route được cập nhật mỗi lần con đường này được sử dụng mà không cần quan tâm tới việc đích là một nút đơn hay là một mạng con

‘Voi mdi mét con đường hợp lệ được một nút đuy trì như là một đồng

trong bảng định tuyến, nút đó cũng đuy trì một danh sách các con trỏ trước

"Danh sách này sẽ nhận các thông báo từ một nút trong sự kiện phát hiện ra một

liên kết tới chặng tiếp theo bị đứt Danh sách các con trỏ trước của mỗi đòng trong bảng định tuyến chứa các nút hàng xóm tới một con đường phân hôi được sinh ra hoặc được chuyên tiếp.

+ Tạo gói yêu cầu tìm đường RREQ

Giao thức AODV sử đụng gói tin RREQ để gửi yêu cầu tìm đường Cấu trúc gói RREQ được biểu diễn trong Hình 1.4

ấu trúc gói RREQ

"Một nút sẽ phát ra một thông điệp RREQ khi nó khác khi nó cần một con

đường tới một đích và chưa có một con đường nào Điều này có thể xây ra nếu

út đô chưa biết một con đường nào đến đích đó hoặc nếu nó đã có một con

đường hợp lệ tới đích nhưng đã quá khoảng thời gian cập nhật cho phép con đường này không được cập nhật hoặc nó bị đánh đầu lä không hợp lệ Trường Destination Sequence Number trong thông điệp RREQ là số thứ tự đích được

'biết lần gần nhất cho đích này và được sao chép từ trường Destination Sequence

‘Number trong bảng định tuyến của nút Nếu trường số thứ tự chưa biết, cờ “Ư

phải được thiết lập là True Trường Originator Sequence Number trong thông điệp RREO là số thứ tự của chính nút đó Số thứ tự này sẽ được tăng trước khi đưa vào trong thông điệp RREQ Trường RREQ ID được tăng thêm một đơn

vị từ RREQ ID cuối cùng được nút hiện tại sử đụng Mỗi một nút chỉ đuy trì

một RREQ ID Trường Hop Couat được thiết lập bằng 0

"Trước khi quảng bá thông điệp RREQ, nút nguồn sẽ lưu lạ giá trị trường RREQ ID và trường Originator IP address của RREQ trong một khoảng thời

1

gian bing giá trị PATH_DISCOVERY,_TIME Theo cách này, khi một nút nhận lại gối tin đồ từ các nút hàng xôm của nó, nó sẽ không xử lý và không

chuyển tiếp gói tin này

Một nút nguồn thường muốn truyền thông hai chiều với một nút đích Trong trường hợp này, nút nguồn phải có một con đường tới nút đích và nút

đích cũng phải có một con đường quay trở lại nút nguồn Dé giãi quyết vẫn đề

này theo một phương pháp hiệu quả nhất có thé, khi một nút trung gian bất kỳ sinh ra một thông điệp RREP đề truyền đến nút nguồn, nút trung gian này nên 'thực hiện thêm một vài hành động để báo cho nút đích biết về con đường quay trở lại nút nguôn Nút nguôn chọn chế độ này cho hoạt động của các nút trung gian bằng cách thiết lập cờ “G' trong thông điệp RREQ

Số thông điệp RREQ trong mỗi gi

giá trị RREQ_RATELTMIT Sau khi quảng bá một thông

đợi một thông điệp RREP (hoặc một thông điệp điều khiễn khác với thông tin

"hiện tại về một con đường tới đích tương ứng) Nếu một con đường không nhận được trong khoảng thời gian NET_TRAVERSAL_TIME mili giây nút này có

thể thữ khám phá một con đường bằng cách quảng ba một thông dip RREQ

khác Số lần gửi lại lớn nhất là RREQ_RETRIES lần tại trị TTL lớn nhất Mỗi

lẫn thử gửi lại một thông điệp RREQ, nút gửi phải tăng và cập nhật trường RREQID và trường IP header cũng phải được thiết lập lại theo một cơ chế đặc

'biệt đề cho phép điều khiên thời gia RREQ có thé phat lại ở lần thử lại tiếp theo

là bao lâu

Các gói dữ liệu đang đợi một con đường (ví đụ, đợi một thông điệp RREP sau khi một thông điệp RREQ đã được gửi đi) nên lưu trữ vào bộ đệm Bộ đệm nên tổ chức theo kiéu FIFO Nếu một con đường không thể phát hiện được sau

số lần thử phát RREQ là RREQ_RETRIES lần và khoảng thời gian TTL lớn

nhất, mọi đữ liệu đang lưu trữ trong bộ đệm sẽ bị xóa và thông điệp Destination

‘Unreachable nén được đưa ra trong các ứng dung,

Để làm giảm sự tắc nghẽn trong một mạng, thời gian thử truyền lại thông

điệp RREQ khi một nút nguồn muốn tìm đường tới một đích nào đó phải thực hiện theo quy luật hàm mũ nhị phân Lin đầu tiên một nút nguồn quảng bá một thông điệp RREQ, nó sẽ đợi một khoảng thời gian là

‘NET_TRAVERSAL_TIME mili giây cho việc nhận một thông điệp trả lời 'RREP Nếu thông điệp RREP không nhận được sau trong khoảng thời gian trên, nút nguồn sẽ gửi một thông điệp RREQ mới Khi tính toán thời gian chờ tiếp theo đễ nhận thông điệp RREP sau khi gửi thông điệp RREP thứ hai, nút nguồn phải sử đụng một hàm mũ nhị phân Do đó, khoảng thời gian chờ tương

‘ing ở lần gửi thông điệp RREQ thứ hai là (2 x NET_TRAVERSAL_TIME) mmili giây Nếu không nhận được một thông điệp RREP nào sau khoảng thời

gian này, một thông điệp RREQ tiếp theo sẽ được gửi tiếp đi cho đến khi nào

số lần gửi vượt quá giá trị RREQ_RETRIES sau lần gửi đầu tiên Với mỗi lần

thử gửi lại, thời gian chờ sẽ là gắp đôi thời gian chờ của lần gửi trước bởi vì thời gian này tuân theo dạng của hàm mũ nhị phân

+ Điều khiên truyền gói RREQ

Để ngăn cân việc truyền các thông điệp RREQ không cần thiết, nút nguồn

niên sử đụng một kỹ thuật tìm kiếm đạng vòng mỡ rộng Trong kỹ thuật tìm

kiếm đạng vòng mở rộng, đầu tiên nút nguồn bắt sử đụng một

TTL=TTL,_START trong IP header chứa gói tin RREQ và thiết lập thời gian timeout cho khoảng thời gian đợi thông điệp RREP là RING_TRAVERAL_TIME mili giay Gia tri TTL,_VALUE được sử dụng tính gia tri RING_TRAVERAL TIME dugc thiết lập bằng với giá trị của

trường TTL trong IP heađer Nếu sau thời gian timeout mà không nhận được

thông điệp RREP trả lời, nút nguồn sẽ quảng bá lại hông điệp RREQ với thời

19

gian TTL tăng lên TTL_INCREMENT đơn vị Việc này sẽ tiếp tục cho đến khi

TTL được thiết lập trong RREQ đạt đến ngưỡng TTL_THRESHOLD, ngoại trừ trường hợp TTLENET_DIAMETER được sử dụng cho mỗi lần thử truyền lại RREQ Sau mỗi lẫn, khoảng thời gian timeout chờ đễ nhận một thông điệp

RREP la RING_TRAVERAL TIME Khi muén trong moi lần thử lại, thông điệp RREQ sẽ đi qua toàn bộ mạng không dây kiểu không cấu trúc, chỉ cần thiết lập cả giá trị TTL_ START và TTL INCREMENT đều

số chặng cộng với TTL_INCREMENT Sau mỗi lần timeout, TTL duoc ting

một giá trị bằng TTL_TNCREMENT cho đến khi TTL=TTL,_THRESHOLD ngoại trừ trường hợp TIL=NET DIAMETER được sử dụng Mỗi khi TIL=NET_DIAMETER, thời gian timeout cho thông điệp RREP được thiết lập bằng NET_TRAVERSEL _TIME

+ Xử

và chuyên tiếp các thông điệp RREQ

Khi mét nút nhận được một thông điệp RREQ, đầu tiên nó sẽ tạo hoặc

cập nhật một con đường tới các chặng trước đó mã không có một số thứ tự hợp

lệ, sau đó nó sẽ kiểm tra để xác định xem nô đã nhận được thông điệp RREQ

có cùng giá trị của trường địa chỉ IP nút nguồn và RREQ ID trong khoảng thời

gian tối thiêu lần cuối của PATH_DISCOVERY_TIME hay chưa Nếu nó đã

nhận được một thông điệp RREQ như vậy, nút này sẽ bố qua thông điệp RREQ mới nhận được Tuy nhiên, phẫn sau đây sẽ mô tả về các thao tác cần thiết khi một nút nhận được một thông điệp RREQ không bị bô qua

Trước hết, nó sé tăng giá trị số chặng trong RREQ thêm một đơn vị Sau

đó, nó sẽ tìm một con đường quay lại tới Originator IP Address Nếu cần, nó sẽ tạo ra một con đường mới hoặc nó sẽ cập nhật một con đường đã có trong bảng định tuyến bằng cách sử dụng trường Originator Sequence Number trong théng điệp RREQ nô nhận được Khi một con đường quay lại được tạo ra hoặc cập nhật, các thao tác sau sẽ được thực hiện:

1 Giá trị Originator Sequence Number trong RREQ được sao chép lại nếu giá trị này lớn hơn giá trị của số thứ tự đích hiện tại

2 Trường số thứ tự hợp lệ sẽ được thiết lập là True

“Khi một nút nhận được một thông điệp, trường Lifetime của đồng tương

ứng với con đường quay ngược lại nút ban đầu được thiết lập là giá trị lớn nhất

cia Existing] ifetime và MinimalLifetime, trong đó:

Minimal ifetime = (CurrentTime + 2x NET _TRAVERSAL_TIME-

2x HopCount x NODE _TRAVERSAL _ TIME)

‘Nat hiện tại có thê sử đụng con đường nghịch đễ chuyên tiếp các gói tin

21

Count trong théng điệp RREQ được tăng lên 1 giá trị, dé tính toán số chặng

mới qua nút trung gian Cuối cùng, giá trị số thứ tự đích cần đến trong bảng

định tuyến sẽ được cập nhật bằng giá trị lớn nhất tương ứng trong thông điệp RREQ và giá trị số thứ tự đích hiện tại này sẽ được nút này duy tr cho đích cần

tìm Tuy nhiên, nút chuyên tiếp thông điệp RREQ không được sửa đổi giá trị

số thứ tự đích, thậm chí nếu giá trị nhận được trong thông điệp

đang lưu giữ v

‘RREQ đến lớn hơn giá trị hiện tại đang được nút chuyển tiếp lưu giữ

‘Noi cach khác, nếu một nút không sinh ra một thông điệp RREP thi nit

đồ sẽ không xử lý thông điệp RREQ Chú ý rằng, nếu các nút trung gian trả lời lại mọi thông điệp RREQ cho một đích nào đó thì nó có thé làm cho dich này

không nhận được bắt cứ thông tin nào về các thông điệp tìm đường đến đích

đó Trong tình huống này, đích này không học được con đường quay lại nút

'ban đầu từ thông điệp RREQ Điều này có thê gây ra việc nút đích lại phải bắt

đầu một quá trình tìm đường (chẳng hạn, nút nguồn đang có gắng thiết lập một

phiên TCP) Đề đâm bảo nút đích luôn học được các con đường đến nút nguồn, nút nguồn nên thiết lập cờ “G' trong thông điệp RREQ nó sinh ra Nếu điều này

Xây ra, một nút trung gian khi sinh ra một thông điệp RREP gửi trả về nút

nguồn

+ Tạo gói trả lời đường RREP

Giao thức AODV đồng göi tin RREP (Hình 1.5) đễ trả lời truy vấn đường

fa) s [elo alli ln a a ara ni

type lala Reversed’ | PrafxSz | Hop Count

REQ ID DDestnation IP Adress Destination Sequirce Number

Originator IP Across

Hinh 1.5 Câu trúc gói RREP

Một nút tạo ra một thông điệp RREP nu:

(6) Bản thân nó là nút đích

GĐNö có một con đường đang hoạt động đến đích, số thứ tự đích thuộc đồng trong bang định tuyến tương ứng với đích này là hợp lệ và lớn hơn hoặc bằng giá trị của trường Destination Sequence Number cia thông điệp RREQ nó nhận được và cờ 'D' không được thiết lập trong thông điệp RREQ

“Khi tạo ra một thông điệp RREP, một nút sẽ sao chép giá trị trường Destination IP Address va giả trị trường Originator Sequence Number tir thong điệp RREQ vào các trường tương ứng trong thông điệp RREP được tạo ra Quá trình xử lý hơi khác biệt trên một nút néu nút bản thân nút đó là nút đích hoặc néu nút đó là một nút trung gian c6 mét cơn đường “đủ mới” tới nút đích

Mỗi lần được tạo ra, thôi

23

‘Hop Count sé biéu dién khoang cach tinh bing sé chang tir nút nguồn đến nút

dich

“Tạo thông điệp trả lời RREP từ nút đích

"Nếu nút sinh ra thông điệp RREP chính là nút đích, nó phải tăng số thứ

tự của nó lên một đơn vị nếu số thứ tự trong thông điệp RREQ bằng với giá trị

đã tăng Ngược lại, nút đích không thay đổi số thứ tự của nó trước khi sinh ra thông điệp RREQ Nút đích sẽ đưa số thứ tự của nó vào trường Destination Sequence Number vi đưa giá trị 0 vào trường Hop Count trong thông điệp RREP

Nút đích sẽ sao chép gia ti MY_ROUTE_TIMEOUT vào trường

Lifetime cia RREP Mỗi một nút cô thể tự cấu hình giá trị

‘MY_ROUTE_TIMEOUT cia riêng mình miễn là giá trị này nằm trong một giới hạn xác định

“Tạo thông điệp trả lời RREP tử nút trung gian

‘Néu nút sinh ra thông điệp RREP không phải là nút đích mà là một nút

trung gian trong con đường đi đến đích, nó sẽ sao chép giá trị số thứ tự nó biết

về nút đích vào trường Distination Sequence Number của RREP

Nút trung gian cập nhật đòng tương ứng với con đường chuyên tiếp đến đích trong bảng định tuyến bằng cách đưa nút cuối cùng truyền RREQ đến nó

(Gia chi IP nguén trong IP header) vo dank sách con trỏ trước cho đồng tương

ứng với con đường chuyên tiếp Nút trung gian cũng cập nhật đòng tương ứng với con đường chuyển tiếp quay lại nguồn trong bảng định tuyến bằng cách đưa nút tiếp theo trong con đường đi đến đích vào trong danh sách con trõ trước

‘Nat trung gian sẽ đưa khoảng cách từ nó đến đích tính bằng số chặng vào

trong trường Hop Count của thông điệp RREP Trường Lifetme của thông điệp

'RREP được tính toán bằng cách lấy thời gian timeout trong bảng định tuyến trừ

đi thời gian hiện tại

Tao thông điệp RREP đến nút đích

“Khi một nút nhận được một thông điệp RREQ và trả lời bằng thông điệp RREP, nó sẽ không xử lý thông điệp RREQ nữa Nếu cỡ 'G° trong RREQ đã

được thiết lập, nút trung gian sẽ trả một thông điệp RREP về nút nguồn đồng

thời nô phải gửi kiêu unicast một thông điệp RREP đến nút đích Thông điệp

RREP gửi đến nút dich là thông điệp gửi đến một đích xác định Thông điệp

RREP niy sẽ chứa các giá trị sau trong các trường của nó;

— Hop Count: Gia trị Hop Count trong đòng tương ứng con đường đến nút nguần

— Destination IP Address: Địa chỉ IP của nút sinh ra thông điệp RREQ

— Destination Sequence Number: Gia tri tong Originator Sequence Number trong RREQ

— Originator IP Address: Dia chi IP cia nit dich trong RREQ

— Lifetime: Khoảng thời gian sống còn lại của quay trở lại nút nguồn của -RREQ mà nút trung gian biết được

"Thông điệp RREP chỉ được gửi đến nút đích bằng cách gửi tới nút tiếp theo theo con đường tới nút đích mà nó biết khi mà nó nhận được một thông điệp RREQ yêu cầu con đường tới nút đích

+ Nhận và chuyển tiếp gói RREP

“Khi một nút nhận một thông điệp RREP, nó sẽ tìm kiếm một con đường tới chặng trước nó Nếu cần thiết, một con đường sẽ được tạo ra cho chặng

trước nó nhưng không cần một số thứ tự hợp lệ Tiếp theo, nút này sẽ tăng giá

trị số chăng trong trường Hop Count của thông điệp RREP lên một đơn vị Sau

đồ con đường chuyển tiếp cho đích này được tạo ra nếu nó chưa tồn tại Ngược.

2

lại nút này sẽ so sánh giá trị của trường Destination Sequence Number trong thông điệp với giá trị của số thứ tự đích mà nó lưu trữ cho con đường tới đích Destination IP Ađdress trong thông điệp RREP Trên cơ sở sự so sánh này, một

sẽ được cập nhật khi một trong các tỉnh huồng

Các số thứ tự bằng nhau nhưng con đường đồ lại đang bị đánh đấu là không hoạt động,

CCác số thứ ty bằng nhau và số chặng mới tính được từ RREP nhỏ hơn số chặng trong đồng tương ứng của băng định toyền

'Nếu đòng tương ứng với đích trong bảng định tuyến đã được tạo ra hoặc

đã được cập nhật thì các công việc sau sẽ được thực hiện:

—_ Con đường này được đánh đấu là hoạt động

—_ Số thứ tự đích được đánh đầu là hợp lệ

— Nit tiép theo trong đòng tương ứng của bảng định tuyến sẽ được gán là nút truyền RREP đến nó Đây chính là nút được chỉ định bằng trường địa chi IP

nguén trong IP header

— Gia tri trong Hop Count được thiết lập giá trị mới

—_ Thời gian quá han được thiết lập bằng thời gian hiện tại cộng với giá trị của trường Lifetime trong thông điệp RREP

—_ Số thứ tự đích lã giá trị của trường Destination Sequence Number trong thông điệp RREP

Nút hiện tại sau đó có thể sử đụng con đường này để chuyển tiếp các gói

tin dữ liệu đến đích.

'Nếu nút hiện tại không phải là nút xác định bằng trường Originator IP

Address trong thông điệp RREP và một con đường chuyễn tiếp đã được tạo

hoặc cập nhật như đã mô tả ở trên, nút này sẽ tìm kiếm trong bảng định tuyến

của nỗ xem có đồng nào tương ứng với con đường tới nút nguồn hay không để

xác định chặng tiếp theo cho gói tin RREP và sau đó chuyên tiếp RREP ngược trở lại nguồn ban đầu bằng cách sử dụng các thông tin đã tìm được trong bảng định tuyến Nếu một nút chuyên tiếp một thông điệp RREP qua một liên kết có khả năng bị lỗi hoặc là liên kết một chiều, nút này nên thiết lập cờ “A' au

cầu nút nhận được thông điệp RREP nó chuyển tiếp đi phải gửi lại thông điệp

trả lời RREP-ACK để báo đã nhận được RREP

Khi bat ky nat nào truyền một thông điệp RREP, đanh sách con trõ trước cho nút đích tương ứng được cập nhật bằng cách thêm vào nó nút tiếp theo ma 'RREP sẽ được truyền chuyển tiếp đến Cuối cùng, đanh sách con trõ trước cho chặng tiếp theo hướng về nút đích cũng sẽ được cập nhật để chứa chặng tiếp

theo hướng về nút nguồn

+ Gói Helo

Giao thức AODV sử đụng gói Hello như là một phần của gói REP duy tri trang thai kết nối Gói Hello chỉ sử dụng 4 trường của gói RREP Khi một nút gửi gói Hello, trường Destination IP chứa địa chi IP của nút gửi

Destination Sequence Number chứa số thứ tự hiện tại của nút, Hop Count thiết lập bằng 0 và Lifetime thiết lập bằng giá trị ALLOWED_HELLO _LOSS *

THELLO_TNTERVAL Mỗi nút thuộc một đường đang hoạt động sẽ quảng bá

gối Hello trong gói IP cô giá trị trường TIL bằng 1 theo chu ky

THELLO_TNTERVAL Nếu một nút đã nhận được một gói HELLO trước đó và

nô không nhận được gói Hello tiếp theo sau khoảng thời gian bằng

ALLOWED_HELLO_LOSS * HELLO_INTERVAL, nit niy coi như liên kết

2

giữa nô với nút gửi gói Hello da bị đứt và khỡi tạo tiền trình báo

gói RRER

® Gói báo lỗi đường RERR

Khi một nút nhận được thông tin về một đường bị lỗi hoặc một liên kết

bị phá vỡ, nỗ sẽ: (1) làm mắt tính hiệu lực của các con đường đang tồn tại; (2) xác định danh sách các nút đích bị ảnh hưỡng; (3) xác định các nút án;

‘bj ảnh hưởng; (4) truyền gói RERR tới các nút lãng giềng bị ảnh hưởng

ng

Gói RRER được tạo ra khi một nút gặp phải một trong các tỉnh huồng:

(0 khi liên kết tới chặng kế tiếp của đường tới dich bi ditt; (ii) khi nhận được

g6i dữ liệu có đích mà không có entry hợp lệ: (ii) khi nhận được gói RRER

‘Additonal Ureachable Destination IP Adresses (needed)

‘Aditenal Ureachable Destination Sequence Numbers ( needed)

Hinh 1.6 Cau triic g6i RRER

"rước khi truyền thông điệp RERR, việc cập nhật được thực hiện đối vớ các entry chứa đích không đến được trong bảng định tuyến bao

số thứ tự đích của entry với trường hop (i) và () hoặc thiết lập số thứ tự đích

bằng giá trị trường Unreachable Destination Sequence Number của gói RRER trong trường hợp (fi): (2) làm mắt tính hiệu lực của entry bằng trạng thái Tnvalid; (3) thiết lập giá trị trường Lifetime của entry bằng thời gian hiện tại công với giá trị DELETE_PERIOD Sau khoảng thời gian Lifetime, néu trang thải của entry không thay đổi, entry này sẽ bị xoá khỏi bảng định tuyển