Luận văn 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
ĐẠI 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
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
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
Lê Hồng Sơn
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
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
TS. ĐỖ ĐÌNH CƯỜNG
Thái Nguyên - 2020
LỜI CẢM ƠN
Trong quá trình học tập, nghiên cứu đề tài luận văn: “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” 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 học
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ầy giáo, cô giáo thuộc
Trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên
đã tham gia quản lý, giảng dạ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 dẫ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 dù đã 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 sót. 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.
Thái Nguyên, ngày … tháng …. năm 2020
Học viên
Lê Hồng Sơn
MỤC LỤC
MỞ ĐẦU........................................................................................................... 1
1.1. Tổng quan về mạng ad hoc .................................................................... 3
1.4. Tổng kết Chương 1 .............................................................................. 31
2.2. Giao thức NKR..................................................................................... 34
2.3. Tính trễ quảng bá ................................................................................. 35
3.2. Đánh giá về tỉ lệ quảng bá.................................................................... 49
3.4. Đánh giá về tỉ lệ tái liên kết ................................................................. 56
3.5. Tổng kết Chương 3 .............................................................................. 57
DANH MỤC BẢNG
DANH MỤC HÌNH
Hình 1.4. Cấu trúc gói RREQ ......................................................................... 16
Hình 1.5. Cấu trúc gói RREP.......................................................................... 22
Hình 1.6. Cấu trúc gói RRER.......................................................................... 27
Hình 2.2. Tiến trình yêu cầu đường ................................................................ 36
Hình 2.5. Thủ tục truy vấn đường................................................................... 43
1
MỞ ĐẦU
Một mạng ad hoc di động là một tập hợp các nút không dâ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ị di độ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
nào theo định hướng di chuyển trong không gian của các nút. Hai nút di độ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 vi 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ử dụng cơ sở hạ tầng mạng cố
định. Nó sử dụ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ử dụ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,
dữ 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 dùng là vấn
đề quan trọng để duy trì chất lượng dị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 di động của
các nút trong mạng ad hoc di động, các tuyến đường có thể sẽ bị lỗi làm kích
hoạt 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 dữ liệu và quan trọng hơn là tăng chi phí hoạt động của các
giao thức định tuyến. Do đó, việc giảm chi phí định tuyến trong quá trình khám
phá đường là một yếu tố thiết yếu trong mạng ad hoc di động. Một số kỹ thuật
định tuyến đa đường được sử dụng để giảm chi phí định tuyến trong ad hoc di
độ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à vấn đề chính cần thực hiện nhằm tối
2
thiểu hoá tắc nghẽn. Phương pháp định tuyến đa đường chủ yếu được sử dụng
để cải thiện chất lượng dịch vụ trong mạng. Mục đích của việc giảm chi phí
đị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ỉ lệ 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 chi phí định tuyến.
Mục tiêu chính của đề tài này là nghiên cứu phương pháp giảm tải định
tuyến trong mạng ad hoc di động trên cơ sở phân tích yêu cầu của các trung
gian trong việc quá trình hình thành mạng. Điều này nhằm mục đích giảm lượng
truy cập tài nguyên liên quan đến chất lượng dịch vụ. Việc thay đổi linh hoạt
các thiết bị đầu cuối khả năng và tạo ra cơ chế định tuyến ổn định được thực
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 dự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 cụm ảo cũng được nghiên cứu
trong đề tài ngày để giảm thiểu chi phí định tuyến. Nó được sử dụng nhằm cải
thiện cơ chế điều khiển cấu trúc mạng để tối thiểu hoá chi phí định tuyến và
tăng thông lượng mạng bằng cách giảm tần suất lỗi của các liên kết.
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 ad 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 dựa trên thông tin từ các nút
lân cận sẽ được trình bày chi tiết 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 dự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.
3
CHƯƠNG 1. TỔNG QUAN VỀ MẠNG AD HOC VÀ ỨNG DỤNG
1.1. Tổng quan về mạng ad hoc
1.1.1. Định nghĩa và đặc trưng của mạng ad hoc
Theo định nghĩa của Tổ chức IETF (Internet Engineering Task Force),
Mạng ad hoc không dâ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 dâ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
có thể di chuyển một cách tự do làm cho kiến trúc của mạng thay đổi liên tục.
Hình 1.1. Minh họa mạng ad hoc di động
Như vậy có thể thấy mạng ad hoc di động bao gồm 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áng giềng để chuyển tiếp các
gói dữ liệu.
Hình 1.1 là một ví dụ minh họa cho một mạng ad hoc di động. Trong ví
dụ 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à
4
một điện thoại thông minh không nằm trong phạm vi truyền của nút nguồn. Vì
vậy, 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 cho mạng ad hoc di độ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 dù
là tạm thời. Để triển khai thành công được mạng ad hoc, thiết kế và công nghệ
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 di 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 (ad-hoc) của mạng.
Tính sẵn 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”.
Mạng 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” và ở trong một khoảng cách nhất
định. Một nút luôn có xu hướng tham gia hay biến mất khỏi mạng. Do đó,
mạng được coi là tạm thời. Hơn nữa, do không có một cơ sở hạ tầng mạng
cho trước, các nút trong mạng phải truyền thông theo kiểu ngang hàng (peer-
to-peer).
5
1.1.2. Đặc điểm của mạng ad hoc
Do ad hoc 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 ad
hoc còn có một số đặc điểm nổi bật sau [11]:
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 ad hoc 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 ad 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
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.
Độ 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 ad hoc hơn là trong mạng có dây truyền thống.
6
1.1.3. Ứng dụng của mạng ad hoc
Mạng ad hoc có rất nhiều ưu thế so với các mạng truyền thống về mặt
ứng dụng trong những điều kiện khó có thể triển khai được một cơ sở hạ tầng
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ý do về kinh tế (chi phí cáp trong một không
gian lớn, chi phí thiết lập nhiều điểm truy cập)..
Ứng dụng trong quân đội
Những thành tựu mới của công nghệ thông tin thường được áp dụng trong
quân sự đầu tiên, và mạng không dây 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ử dụng các mạng “packet radios” –
một nguyên mẫu đầu tiên của mạng chuyển mạch gói không dây ngày nay.
Mạng ad 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ự do di 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 nú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 động ở
đây là theo nhóm.
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 ad hoc sẽ trở nên cụ thể hơn (ví dụ: định tuyến, sử dụng các ứng
dụng 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
Mạng ad hoc rất 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.
7
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 di độ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 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 – đó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 file đí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 di động, tất cả những người tham dự hội thảo đều có thể sử dụng thiết
bị di động để tạo thành một mạng ad-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ử dụ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 dụ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ạ tầng 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í dụ 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.
8
Hình 1.2. Ví dụ minh họa mạng ad hoc trên xe bus
Mạng cảm biến
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ạ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ể, 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,...
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
mạ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à do 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 dây kiểu không cấu trúc thường được áp dụng
để triển khai mạng cảm biến do:
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 nghi với những thay đổi
này.
9
Mạng 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) và các công nghệ tương tự khác. Mạng 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 dịch vụ Internet (ISP). Mỗi người truy cập được
trang bị 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 mạng 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ử dụng rộng rãi ngày nay, các nút mạng
di độ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ử dụ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ơ sở hạ tầng một chặng (one-hop) của cấu hình
10
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.
Sử dụng mạng không dâ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 mạng ad hoc
1.2.1. Đặc điểm chung của giao thức định 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 dâ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 duy trì các con
đường tới đích khi không truyền thông. AODV cho phép các nút di độ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
hộ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ử dụng liên kết đã bị đứt.
Một đặc điểm khác biệt quan trọng của AODV so với các thuật toán định
tuyến truyền thống trong mạng có dây là nó sử dụng một số thứ tự đích cho mỗi
một dòng trong bảng đị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
11
thông điệp này được nhận về qua UDP và 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 dạ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ử dụ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 “danh sách con trỏ
trước”, danh sách này sẽ chứa địa chỉ IP của mỗi một nút hàng xóm được sử
dụng để đ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ử dụng các trường sau
cho mỗi một dòng trong bảng định tuyến:
Địa chỉ IP đích
12
Số thứ thự đích
Cờ số thứ tự đích hợp lệ
Các cờ trạng thái và cờ định tuyến khác (chẳng hạn như hợp lệ, không hợp
lệ, đã được sửa, đang được sửa).
Network Interface
Số chặng
Chặng tiếp theo
Danh sách các con trỏ trước.
Thời gian sống
Việc quản lý số thứ tự là một công việc thiết yếu để tránh định tuyến
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 khi
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 bằng thao tác gán số thứ tự và đánh dấu con đường
đó trong bảng định tuyến là con đường không hợp lệ.
1.2.2. Cơ chế hoạt động của giao thức AODV
Duy trì các số thứ tự
Mọi bảng định tuyến trong mọi nút di động trong mạng không dây kiểu
không cấu trúc phải chứa các thông tin mới nhất về số thứ tự cho địa chỉ IP của
nút đích đối với mỗi một dòng trong bảng định tuyến khi các nút duy 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 điệp 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 duy trì các số thứ tự đích của nó nhằm đảm bảo tránh khỏi
việc định tuyến 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. Nếu số thứ tự hiện đang sử dụng đã là số lớn nhất
(chẳng hạn bằng 4294967295 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ố dương lớn nhất có thể, nếu phép toán lấy phần bù của 2 được
áp dụng với số nguyên 32 bit, giá trị tiếp theo sẽ là 2147483648 là giá trị âm
lớn nhất có thể trong cùng một hệ thống số. Việc biểu diễn các số âm không
liên quan đến việc tăng các số thứ tự AODV. Đây là sự tương phản trong dạng
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 tất bằng phép toán số học
có dấ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.
Tải về để xem bản đầy đủ
68 trang
17180
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn 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", để 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_thuat_toan_quang_ba_lai_thong_tin_dinh_tuyen_nham_t.pdf
