Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu kỹ thuật ước lượng chất lượng liên kết và cải tiến thuật toán chọn đường cho giao thức AODV

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:78

Thêm vào BST

Báo xấu

26
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của đề tài là nghiên cứu một phương pháp định tuyến xuyên tầng, ước lượng chất lượng của các liên kết từ tầng MAC và truyền thông tin ngược lên tầng định tuyến để sử dụng làm thông tin đầu vào cho thuật toán chọn đường của giao thức định tuyến. Phương pháp này sẽ được áp dụng thử nghiệm để cải tiến giao thức AODV nhằm tăng hiệu năng định tuyến trong mạng MANET. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu kỹ thuật ước lượng chất lượng liên kết và cải tiến thuật toán chọn đường cho giao thức AODV

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Phạm Thị Hồng An NGHIÊN CỨU KỸ THUẬT ƢỚC LƢỢNG CHẤT LƢỢNG LIÊN KẾT VÀ CẢI TIẾN THUẬT TOÁN CHỌN ĐƢỜNG CHO GIAO THỨC AODV LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2019
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Phạm Thị Hồng An NGHIÊN CỨU KỸ THUẬT ƢỚC LƢỢNG CHẤT LƢỢNG LIÊN KẾT VÀ CẢI TIẾN THUẬT TOÁN CHỌN ĐƢỜNG CHO GIAO THỨC AODV 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 - 2019
LỜI CẢM ƠN Sau thời gian học tập và rèn luyện 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, bằng sự biết ơn và kính trọng, tôi xin gửi lời cảm ơn chân thành đến Ban Giám hiệu, Phòng Đào tạo và Khoa Công nghệ thông tin 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 cùng các thầy, cô giáo đã nhiệt tình hƣớng dẫn, giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu và hoàn thiện luận văn này. Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Nguyễn Văn Tam, ngƣời thầy đã trực tiếp hƣớng dẫn, giúp đỡ em trong quá trình thực hiện đề tài. Xin chân thành cảm ơn gia đình, bạn bè cùng đồng nghiệp đã tạo điều kiện sát, nghiên cứu để hoàn thành đề tài này. Tuy nhiên điều kiện về năng lực bản thân còn hạn chế, luận văn chắc chắn không tránh khỏi những thiếu sót. Kính mong nhận đƣợc sự đóng góp ý kiến của các thầy cô giáo, bạn bè và đồng nghiệp để luận văn của tôi đƣợc hoàn thiện hơn. Xin trân trọng cảm ơn! Thái Nguyên, ngày … tháng …. năm 2019 Học viên Phạm Thị Hồng An
MỤC LỤC MỞ ĐẦU ................................................................................................................ 1 CHƢƠNG 1. ĐỊNH TUYẾN TRONG MẠNG MANET ..................................... 3 1.1. Giới thiệu về mạng MANET....................................................................... 3 1.1.1. Khái niệm mạng MANET .................................................................... 3 1.1.2. Đặc điểm của mạng MANET............................................................... 4 1.1.3. Ứng dụng của mạng MANET .............................................................. 6 1.2. Định tuyến trong mạng MANET ................................................................ 8 1.2.1. Những yêu cầu đối với giao thức định tuyến trong mạng MANET .... 8 1.2.2. Một số chiến lƣợc định tuyến trong mạng MANET ............................ 9 1.3. Giao thức định tuyến AODV .................................................................... 16 1.3.1. Giới thiệu về giao thức AODV .......................................................... 16 1.3.2. Cơ chế hoạt động của giao thức AODV ............................................ 17 1.4. Một số nghiên cứu cải tiến giao thức AODV ........................................... 26 1.4.1. Đảm bảo tính sẵn sàng chuyển tiếp dữ liệu ....................................... 26 1.4.2. Tiết kiệm năng lƣợng và tăng độ bền vững của đƣờng. .................... 29 1.4.3. Hỗ trợ chất lƣợng dịch vụ .................................................................. 32 1.4.4. Đảm bảo an ninh định tuyến .............................................................. 33 1.4.5. Đánh giá các cải tiến giao thức AODV ............................................. 35 1.5. Tổng kết Chƣơng 1 ................................................................................... 36 CHƢƠNG 2. CẢI TIẾN GIAO THỨC AODV TRÊN CƠ SỞ ĐÁNH GIÁ CHẤT LƢỢNG LIÊN KẾT ................................................................................. 38 2.1. Ƣớc lƣợng trễ liên kết trên cơ sở thời gian phục vụ ................................. 38 2.1.1. Phân tích độ trễ của liên kết theo mô hình DCF ................................ 38 2.1.2. Ƣớc lƣợng độ trễ của liên kết theo thời gian phục vụ ....................... 39 2.2. Cải tiến giao thức AODV .......................................................................... 44 2.2.1. Mô hình hoạt động định tuyến xuyên tầng ........................................ 44 2.2.2. Module đo mức độ sử dụng kênh truyền ........................................... 45
2.2.3. Module ƣớc lƣợng tỷ lệ lỗi frame của liên kết................................... 48 2.2.4. Module định tuyến ............................................................................. 52 2.3. Tổng kết Chƣơng 2 ................................................................................... 56 CHƢƠNG 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ................................ 58 3.1. Kịch bản mô phỏng ................................................................................... 58 3.2. Các kết quả và đánh giá ............................................................................ 60 3.2.1. Thông lƣợng trung bình ..................................................................... 60 3.2.2. Tỷ lệ truyền gói thành công ............................................................... 62 3.2.3. Trễ truyền gói trung bình ................................................................... 64 3.2.4. Tải định tuyến .................................................................................... 66 3.3. Tổng kết Chƣơng 3 ................................................................................... 68 KẾT LUẬN .......................................................................................................... 70 TÀI LIỆU THAM KHẢO .................................................................................... 72
1 MỞ ĐẦU Đƣợc hình thành bởi các kết nối tạm thời giữa các nút mạng di động không có sự hỗ trợ của cơ sở hạ tầng mạng cố định, mạng MANET có nhiều những đặc điểm khác biệt so với mạng không dây và có dây truyền thống làm nảy sinh nhiều thách thức và các hƣớng nghiên cứu khác nhau: vấn đề định tuyến hiệu quả khi topo mạng thay đổi, đảm bảo chất lƣợng dịch vụ theo yêu cầu từ chƣơng trình ứng dụng, đảm bảo an ninh mạng, tiết kiệm năng lƣợng, khả năng tự tổ chức, chuyển đổi các dịch vụ từ mô hình client-server và đảm bảo hiệu năng kích thƣớc mạng thay đổi. Kết quả của nghiên cứu phân loại và đánh giá về số lƣợng các nghiên cứu theo các hƣớng khác nhau đối với mạng MANET trong thời gian gần đây cho thấy, hƣớng nghiên cứu về định tuyến trong mạng MANET đứng đầu về số lƣợng các nghiên cứu đã đƣợc công bố. Nhƣ vậy, có thể khẳng định, định tuyến trong mạng MANET đã và đang là một vấn đề rất cần đƣợc quan tâm giải quyết trong những nghiên cứu cải tiến hiệu năng mạng MANET. AODV (Ad hoc On demand Distance Vector Routing Protocol) là một trong các giao thức định tuyến tiêu biểu trong nhóm các giao thức định tuyến đơn đƣờng có cơ chế định tuyến kết hợp giữa chiến lƣợc định tuyến tìm đƣờng theo yêu cầu với các chiến lƣợc định tuyến cập nhật theo sự kiện, định tuyến phẳng, định tuyến từng chặng và định tuyến phân tán. Từ khi đƣợc giới thiệu lần đầu vào năm 2001 cho tới nay, đã có nhiều đề xuất cải tiến giao thức AODV theo các mục tiêu: Đảm bảo tính sẵn sàng chuyển tiếp dữ liệu, tiết kiệm năng lƣợng, hỗ trợ QoS và đảm bảo an ninh định tuyến. Trong số các đề xuất cải tiến này, có nhiều đề xuất đã sử dụng phƣơng pháp khai thác thông tin định tuyến theo cách tiếp cận liên tầng để xây dựng cơ chế định tuyến với độ đo định tuyến
2 mới thay cho độ đo số chặng của giao thức AODV nhƣng không hƣớng tới mục tiêu giảm tắc nghẽn gây ra bởi thuật toán tìm đƣờng ngắn nhất theo số chặng đã đề cập ở trên. Mục đích của đề tài là nghiên cứu một phƣơng pháp định tuyến xuyên tầng, ƣớc lƣợng chất lƣợng của các liên kết từ tầng MAC và truyền thông tin ngƣợc lên tầng định tuyến để sử dụng làm thông tin đầu vào cho thuật toán chọn đƣờng của giao thức định tuyến. Phƣơng pháp này sẽ đƣợc áp dụng thử nghiệm để cải tiến giao thức AODV nhằm tăng hiệu năng định tuyến trong mạng MANET. Luận văn có bố cục nhƣ sau: Sau phần mở đầu, nội dung giới thiệu Chƣơng 1 trình bày về vấn đề định tuyến trong mạng MANET. Lý thuyết về phƣơng pháp và kỹ thuật cải tiến giao thức định tuyến AODV trên cơ sở đánh giá chất lƣợng liên kết đƣợc trình bày trong Chƣơng 2. Các kết quả của việc thử nghiệm đánh giá kết quả về hiệu năng của giao thức cải tiến AODV-DM so với giao thức gốc AODV đƣợ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. ĐỊNH TUYẾN TRONG MẠNG MANET 1.1. Giới thiệu về mạng MANET 1.1.1. Khái niệm mạng MANET Mạng MANET (Mobile Ad hoc Network) [18] 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áng giềng để chuyển tiếp các gói dữ liệu. Hình 1.1 minh họa một mạng MANET. 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à 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 MANET. Hình 1.1. Một ví dụ của mạng MANET Thuật ngữ “Ad hoc” áp dụng cho mạng không dây mô tả một mạng không có cơ sở hạ tầng cố định, trong đó hình trạng mạng đƣợc tạo thành bởi chính các
4 nút mạng. Chế độ “Ad hoc” của chuẩn IEEE 802.11 [33] 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 (MANET) đã mở rộng khái niệm “Ad hoc” đa chặng [66] 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ác nút trong mạng MANET thông thƣờng sẽ 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 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òn có một số đặc điểm nổi bật sau [8]:  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 ở
5 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 MANET 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 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 MANET 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 của mạng MANET. 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
6 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. Ngày nay, mạng MANET đƣợc ứng dụng trong rất nhiều lĩnh vực từ các ứng dụng trong 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 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 trông 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
7 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ể 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 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ò nhƣ 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,… 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.
8 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. Định tuyến trong mạng MANET 1.2.1. Những yêu cầu đối với giao thức định tuyến trong mạng MANET Nhƣ đã đƣợc đề cập ở phần trƣớc, mạng MANET có những khác biệt lớn với mạng truyền thống về tài nguyên hạn chế tại các nút mạng, băng thông hạn chế, tỷ lệ lỗi cao, topo mạng thay đổi liên tục. Do đó, các giao thức định tuyến trong mạng MANET cần đảm bảo đƣợc những yêu cầu sau [3]:  Tối thiểu hóa tải điều khiển: Việc truyền và nhận các gói tin điều khiển đều tiêu tốn băng thông mạng, tài nguyên xử lý và năng lƣợng pin. Giao thức định tuyến nào giảm đƣợc số lƣợng các gói tin điều khiển thì sẽ tiết kiệm đƣợc những tài nguyên này.  Tối thiểu hóa tải xử lý: Những thuật toán phức tạp yêu cầu tài nguyên CPU cao dẫn đến trễ xử lý lớn và tốn pin tại các nút mạng. Giao thức định tuyến có thuật toán đơn giản sẽ kéo dài đƣợc thời gian hoạt động của toàn mạng.  Hỗ trợ định tuyến đa chặng: Mỗi nút mạng không dây chỉ có khả năng truyền tín hiệu trong một phạm vi giới hạn nên để thực hiện việc truyền dữ liệu trong
9 mạng, giao thức định tuyến phải có khả năng tìm đƣợc các đƣờng đa chặng giữa các cặp nút nguồn – đích.  Đáp ứng đƣợc với sự thay đổi về topo mạng: Giao thức định tuyến phải có khả năng duy trì đƣợc các đƣờng đã tìm đƣợc khi nút nguồn, nút đích hoặc các nút trung gian trên các đƣờng đó di chuyển. Các kết nối trong mạng MANET cũng thƣờng xuyên bị phá vỡ nên giao thức định tuyến phải có khả năng phản ứng nhanh với tải điều khiển nhỏ nhất.  Ngăn chặn định tuyến lặp: Vấn đề định tuyến lặp bởi việc một nút chọn chặng kế tiếp của đƣờng là một nút trƣớc đó đã xuất hiện. Khi tồn tại đƣờng lặp vòng, các gói dữ liệu sẽ bị chuyển tiếp liên tục trong vòng mà không đến đƣợc đích cho đến khi trƣờng TTL của nó bằng không. Hiện tƣợng này gây tốn băng thông và giảm hiệu năng mạng. Vì vậy, giao thức định tuyến phải có khả năng tìm đƣợc các đƣờng không lặp. 1.2.2. Một số chiến lược định tuyến trong mạng MANET  Đị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 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, nhƣợc điểm của chúng là tính toán và tìm ra những con đƣờng tới mọi đích nên có thể có một
10 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 nhiều băng thông mạng khi trạng thái các liên kết và topo mạng thay đổi với tốc độ nhanh. Đố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ể.  Đị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 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
11 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.  Đị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 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
12 đƣờ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  Đị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.
13 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.  Đị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.
14 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 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 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
15  Đị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 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ó 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. Để tiết kiệm tài nguyên hệ thống mạng trong các tiến trình tìm đƣờng, các giao thức định tuyến đa đƣờng cho phép tìm và cài đặt nhiều hơn một con đƣờng không giao nhau tới cùng một đích vào bảng định tuyến của chúng. Tại một nút, khi có yêu cầu chuyển tiếp dữ liệu tới nút đích, con đƣờng tốt nhất sẽ đƣợc sử dụng và những con đƣờng còn lại sẽ đóng vai trò là đƣờng dự phòng. Khi đƣờng chính bị lỗi, các đƣờng dự phòng sẽ đƣợc sử dụng để chuyển tiếp các gói tin nếu chúng vẫn trong trạng thái còn hoạt động đƣợc. Thêm vào đó, nếu cơ chế cân bằng tải đƣợc sử dụng, có thể phân lƣu lƣợng dữ liệu cần truyền thành nhiều luồng đƣợc truyền song song trên các con đƣờng tới cùng một đích. Trong số các phƣơng pháp phân loại các chiến lƣợc định tuyến đã đƣợc trình bày ở trên, phƣơng pháp phân loại theo tiêu chí thời điểm định tuyến bao gồm hai chiến lƣợc là định tuyến tìm đƣờng trƣớc và định tuyến tìm đƣờng theo yêu cầu đƣợc sử dụng rất rộng rãi. Với các giao thức sử dụng chiến lƣợc định tuyến tìm đƣờng trƣớc kết hợp với cơ chế điều khiển dạng bảng, đƣờng truyền dữ liệu giữa mọi cặp nút nguồn, đích trong mạng sẽ đƣợc khám phá trƣớc khi có yêu cầu truyền dữ liệu. Tuy nhiên, do sự thay đổi ngẫu nhiên với tần suất lớn của