Tài liệu Nghiên cứu phương pháp định tuyến hiệu quả trên cơ sở định tuyến đa đường có cân bằng tải cho mạng ad hoc

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