- BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM VĂN TRUNG NGHIÊN CỨU CÁC GIAO THỨC ĐỊNH TUYẾN ĐIỀU KHIỂN THEO YÊU CẦU TRÊN MẠNG MANET LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN Huế 2009 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM VĂN TRUNG NGHIÊN CỨU CÁC GIAO THỨC ĐỊNH TUYẾN ĐIỀU KHIỂN THEO YÊU CẦU TRÊN MẠNG MANET CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SÔ NGƯỜI HƯỚNG DẪN KHOA HỌC TS. - Xin chân thành cảm ơn! Học viên Phạm Văn Trung 3 MỤC LỤC LỜI CAM ĐOAN LỜI CẢM ƠN DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT DANH MỤC CÁC HÌNH VẼ, ĐỒ THI DANH MỤC CÁC HÌNH VẼ, ĐỒ THI MỤC LỤC CHƯƠNG Giới thiệu về mạng không dây Phân loại mạng không dây Theo quy mô triển khai mạng Theo quan hệ di động của các bộ định tuyến và nút mạng Hình 1.1. - Các thiết bị truy cập mạng không dây Yêu cầu thiết bị sử dụng trong mạng MANET Những đặc điểm chính và ứng dụng của mạng không dây Những đặc điểm chính của mạng không dây Những ứng dụng cơ bản của mạng không dây Công nghệ WiMax Công nghệ Wireless USB (WUSB Công nghệ Ultra WideBand (UWB Kết luận chương CHƯƠNG Giới thiệu về định tuyến trong hệ thống mạng máy tính Một số thuật toán định tuyến cơ bản trong mạng Thuật toán Vectơ khoảng cách (Distance Vector Thuật toán trạng thái kết nối (Link State Các giao thức định tuyến trong mạng MANET Hình 2.3. - Phân loại các giao thức định tuyến trong mạng Ad Hoc.......38 Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol Giao thức định tuyến kết hợp (Hybrid Routing Protocol Giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET:. - 40 Giao thức DSR (Dynamic Source Routing Cơ chế tạo thông tin định tuyến (Route Discovery Lưu đồ 2.1. - Nút D phát gói tin RREP về nút S theo đường đã khám phá Cơ chế duy trì thông tin định tuyến (Route Maintanance Hình 2.6. - Minh họa cơ chế duy trì thông tin định tuyến Giao thức AODV (Ad hoc On Demand Distance Vector Cơ chế tạo thông tin định tuyến (Route Discovery Hình 2.6. - Các trường trong gói tin RREP Cơ chế duy trì thông tin định tuyến So sánh và đánh giá hiệu quả làm việc của các giao thức Kết luận chương CHƯƠNG Giới thiệu môi trường mô phỏng NS Hình 3.1. - Mã cấu hình sự di chuyển cho Node Các thành phần cấu thành mạng trong một MobileNode Viết mã tcl để thực thi mô phỏng mạng wireless Thiết kế mô hình mạng để mô phỏng cho các giao thức định tuyến theo yêu cầu trên mạng MANET Hình 3.5. - Cơ chế xử lý khám phá đường tại node của AODV Error: Reference source not found 9 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ TRANG LỜI CAM ĐOAN LỜI CẢM ƠN DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT DANH MỤC CÁC HÌNH VẼ, ĐỒ THI DANH MỤC CÁC HÌNH VẼ, ĐỒ THI MỤC LỤC CHƯƠNG Giới thiệu về mạng không dây Phân loại mạng không dây Theo quy mô triển khai mạng Theo quan hệ di động của các bộ định tuyến và nút mạng Hình 1.1. - Mạng MANET là một mạng bao gồm các thiết bị di động vô tuyến kết nối ngang hàng với nhau hình thành nên một mạng tạm thời mà không cần sự trợ giúp của các thiết bị trung tâm cũng như các cơ sở hạ tầng mạng cố định, nên nó vừa đóng vai trò truyền thông, vừa đóng vai trò như thiết bị định tuyến. - Vì thế, một số giao thức định tuyến truyền thống không còn phù hợp với mạng MANET mà được thay thế bằng các giao thức định tuyến theo yêu cầu, bảng ghi, kết hợp...[8],[9]. - Nội dung chính của luận văn sẽ đi sâu nghiên cứu các giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET. - Đồng thời đánh giá hiêu năng của một số giao thức định tuyến theo yêu cầu tiêu biểu trong mạng MANET dựa trên phương pháp mô phỏng bằng NS-2. - Chương 2: Nghiên cứu các giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET nhằm phân tích một số thuật toán định tuyến truyền thống trên hệ thống mạng, từ đó rút ra khuyết điểm mà các giao thức truyền thống không thể áp dụng cho mạng MANET. - Thông qua việc phân loại các giao thức định tuyến trên mạng MANET để so sánh và đánh giá một số giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET. - Chương 3: Mô phỏng một số giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET. - Theo quan hệ di động của các bộ định tuyến và nút mạng: Với hướng này có thể phân thành 3 loại: Mạng không dây cố định (Fixed wireless network), Mạng không dây với các điểm truy cậy cố định (Wireless network with fixed access points) và Mạng di động tùy biến (Mobile ad hoc network. - Các điểm truy cập cố định đóng vai trò như các thiết bị định tuyến cho các nút mạng. - Thiết bị truy cập không dây: Hình 1.11. - Những đặc điểm chính của mạng không dây. - 32 33 CHƯƠNG 2 NGHIÊN CỨU CÁC GIAO THỨC ĐỊNH TUYẾN ĐIỀU KHIỂN THEO YÊU CẦU TRÊN MẠNG MANET Trong mạng máy tính để định đường đi trong quá trình truyền dữ liệu người ta thường dùng các bộ định tuyến. - Hay định tuyến là cách thức mà các bộ định tuyến, các máy tính hoặc các thiết bị mạng sử dụng để tìm đường trong việc phát các gói tin tới địa chỉ đích trên mạng, đảm bảo tìm đường đi tốt nhất từ lớp mạng này sang lớp mạng khác để đưa dữ liệu đến được đích mong muốn. - Định tuyến trong hệ thống mạng: Thông thường, tiến trình định tuyến thường chỉ hướng đi dựa vào bảng định tuyến được tổ chức trong bộ nhớ của router, đó là bảng chứa những lộ trình tốt nhất đến các đích khác nhau trên mạng. - Vì vậy, việc xây dựng bảng định tuyến trở nên vô cùng quan trọng trong việc định tuyến trên các hệ thống mạng. - Nếu router chạy định tuyến động thì router sẽ tự động nhớ những thông tin này từ các router khác. - Còn nếu router chạy định tuyến tĩnh thì người quản trị mạng phải cấu hình các thông tin đến các mạng khác cho các router. - Một số thuật toán định tuyến cơ bản trong mạng: Một phương pháp khá đơn giản và hiệu quả để thực hiện việc định tuyến trong hầu hết các hệ thống mạng truyền thông là việc sử dụng các bộ định tuyến để phát hiện và lựa chọn đường đi hợp lý cho gói dữ liệu đến đích thông qua các thuật toán định tuyến như: thuật toán vectơ khoảng cách (Distance Vector) và thuật toán trạng thái kết nối (Link State . - Thuật toán Vectơ khoảng cách (Distance Vector): 34 Phương pháp này được thực hiện bằng cách truyền định kỳ các bản sao của bảng định tuyến từ router này sang router khác. - Mỗi router nhận được bảng định tuyến của những router láng giềng kết nối trực tiếp với nó. - Việc tính toán đường đi trong thuật toán định tuyến theo vectơ khoảng cách dựa vào thuật toán Bellman-Ford. - Thuật toán Bellmen-Ford thường được áp dụng trong giao thức định tuyến tĩnh RIP để xây dựng bảng định tuyến. - Sử dụng các giao thức định tuyến theo vectơ khoảng cách thường tốn ít tài nguyên của hệ thống. - Thuật toán trạng thái kết nối (Link State): Trạng thái liên kết là một mô tả đặc điểm các mối liên kết từ bộ định này tới các bộ định tuyến lân cận. - Các đặc điểm này bao gồm: địa chỉ IP, mặt nạ, kiểu mạng kết nối, và các bộ định tuyến kết nối mạng đó. - Giao thức định tuyến trạng thái liên kết được thực hiện dựa trên các bản tin thông báo trạng thái liên kết (LSA), mỗi bộ định tuyến xây dựng cho mình một cơ sở dữ liệu trạng thái riêng dựa vào nội dung của các bản tin này. - Do đó các bộ định tuyến biết rõ và chinh xác thông tin topo về mạng và thực hiện truyền dẫn các gói tin từ nút nguồn đến nút đích trong mạng dễ dàng. - Gói thông báo trạng thái liên kết (LSA: Link State Advertisment) là các gói tin nhỏ chứa thông tin định tuyến được truyền qua lại giữa các bộ định tuyến, được làm tràn trên mạng theo định kỳ hay khi có thay đổi thông tin của một bộ định tuyến nào đó trong mạng. - Thuật toán Dijkstra được áp dụng trong giao thức định tuyến trạng thái liên kết được thực hiện qua các bước sau: Input: Đồ thị (G, w, s). - Router sử dụng định tuyến theo trạng thái kết nối sẽ phải cần nhiều bộ nhớ hơn và hoạt động xử lý nhiều hơn là sử dụng định tuyến theo vectơ khoảng cách. - Router phải có đủ bộ nhớ để lưu cơ sở dữ liệu về cấu trúc mạng, bảng định tuyến. - Phân loại các giao thức định tuyến trong mạng MANET 37 Mạng MANET (Mobile Ad hoc Network) là mạng không dây đặc biệt gồm tập hợp các thiết bị di động, giao tiếp không dây, có khả năng truyền thông trực tiếp với nhau hoặc thông qua các nút trung gian làm nhiệm vụ chuyển tiếp. - Các nút mạng vừa đóng vai trò như thiết bị truyền thông vừa đóng vai trò như thiết bị định tuyến. - Như vậy, khi sử dụng các giao thức định tuyến thông thường dựa trên các giải thuật Distance-Vector hoặc Link-State trong mạng Ad Hoc sẽ dẫn đến một số vấn đề phát sinh: [6. - Ở các mạng thông thường, việc kết nối các bộ định tuyến nhìn chung là không thay đổi về vị trí, chính vì thế ít xảy ra việc thay đổi cấu hình tôpô mạng nên việc hội tụ mạng là ít xảy ra.Tuy nhiên, trong mạng Ad Hoc, các nút luôn thay đổi vị trí dẫn đến cấu hình tôpô mạng thay đổi, nên đòi hỏi cần phải có sự hội tụ của mạng cho các tuyến mới một cách nhanh chóng. - Để thực hiện được việc này, các giao thức định tuyến phải liên tục gửi cập nhật định tuyến, dẫn đến việc tiêu tốn khá nhiều băng thông và năng lượng. - Các đường đi dư thừa được tích lũy một cách không cần thiết: Trong môi trường mạng Ad Hoc, có rất nhiều đường đi từ nút nguồn đến nút đích và những đường đi này sẽ được cập nhật tự động vào bảng định tuyến trong các thiết bị định tuyến (thiết bị di động), dẫn đến việc dư thừa đường đi trong bảng định tuyến. - 38 Các giao thức định tuyến trong mạng Ad Hoc được chia thành 3 loại: Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol), Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol) và Giao thức định tuyến kết hợp (Hybrid Routing Protocol). - Phân loại các giao thức định tuyến trong mạng Ad Hoc 2.3.1. - Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol): Giao thức định tuyến theo bảng ghi còn được gọi là giao thức chủ ứng (Proactive). - Theo giao thức này, bất kỳ một nút trong mạng đều luôn duy trì trong bảng định tuyến của nó thông tin định tuyến đến tất cả các nút khác trong mạng. - Thông tin định tuyến được phát broadcast trên mạng theo một khoảng thời gian quy định để giúp cho bảng định tuyến luôn cập nhật những thông tin mới nhất. - Chính vì vậy, một nút nguồn có thể lấy thông tin định tuyến ngay lập tức khi cần thiết. - Chính vì thế giao thức định tuyến theo bảng ghi chỉ áp dụng trong các mô hình mạng MANET mà các nút ít di chuyển. - Các giao thức hoạt động theo kiểu giao thức định tuyến theo bảng ghi như: Giao thức DSDV (Destination Sequenced Distance Vector), Giao thức WRP (Wireless Routing Protocol), Giao thức GSR (Global State Routing)… 2.3.2. - Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol): Một phương pháp khác với phương pháp định tuyến điều khiển theo bảng ghi đó là định tuyến điều khiển theo yêu cầu còn được gọi là giao thức phản ứng (Reactive). - Khi một tuyến đã được khám phá và thiết lập, nó được duy trì thông số định tuyến (route maintenance) bởi một số dạng thủ tục cho đến khi hoặc là tuyến đó không thể truy nhập được từ nút nguồn hoặc là không cần thiết đến nó nữa. - Với các cơ chế đó, các giao thức định tuyến điều khiển theo yêu cầu không phát broadcast đến các nút lân cân về các thay đổi của bảng định tuyến theo thời gian, nên tiết kiệm được tài nguyên mạng. - 40 Một số giao thức định tuyến điều khiển theo yêu cầu tiêu biểu như: Giao thứ CBRP (Cluster Based Routing Protocol), Giao thức AODV (Ad hoc On Demand Distance Vector), Giao thức DSR (Dynamic Source Routing), Giao thức TORA (Temporally Ordered Routing Algorihm)… 2.3.3. - Giao thức định tuyến kết hợp (Hybrid Routing Protocol): Trong giao thức định tuyến này có kết hợp cả hai cơ chế giao thức định tuyến chủ ứng (Proactive) và giao thức định tuyến phản ứng (Reactive). - Trong giao thức định tuyến này, mạng được chia thành các vùng (zone). - Đều đó có nghĩa là giao thức Hybrid sử dụng giao thức định tuyến phản ứng (Reactive) giữa các zone và giao thức định tuyến chủ ứng (Proactive) cho các node mạng trong cùng zone. - Do đó, đường đi đến nỗi node trong cùng một zone được lập mà không cần phải định tuyến ra ngoài zone, trong khi đó các tiến trình khám phá đường và duy trì đường thì được sử dụng để tìm kiếm và duy trì đường đi giữa các zone với nhau. - Các giao thức định tuyến tiêu biểu sử dụng kiểu Hybrid: Giao thức ZPR (Zone Routing Protocol), Giao thức ZHLS (Zone-based Hierarchical Link State Routing Protocol)… 2.4. - Giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET: Như chúng ta đã biết, việc định tuyến trên các hệ thống mạng là khá quan trọng, quá trình định tuyến có thể xảy ra trước khi hệ thống có nhu cầu truyền dữ liệu hoặc trong khi hệ thống truyền dữ liệu. - Giao thức DSR (Dynamic Source Routing): DSR (Dynamic Source Routing) là giao thức định tuyến đơn giản và hiệu quả được thiết kế riêng cho mạng MANET. - Giao thức DSR là giao thức định tuyến phản ứng (Reactive) sử dụng cơ chế định tuyến nguồn (source routing), nghĩa là bên gửi sẽ biết toàn bộ thông tin về đường đi đến đích. - 42 Như vậy, hoạt động của giao thức DSR bao gồm hai cơ chế chính: cơ chế tạo thông tin định tuyến (Route Discovery) và cơ chế duy trì thông tin định tuyến (Route Maintanance . - Cơ chế tạo thông tin định tuyến (Route Discovery): Route Discovery cho phép các node trong mạng Ad Hoc tìm kiếm đường đi đến đích một cách tự động thông qua các node trung gian. - Tiến trình tạo thông tin định tuyến sẽ phát gói tin Route Request (RREQ) đến các node lân cận của nó trong mạng. - Các nút láng giềng sau khi nhận gói tin RREQ sẽ thực hiện việc kiểm tra thông tin (quay về bước 1) Như vậy, quá trình này cứ tiếp tục cho đến khi node nguồn nhận được thông tin về đường đi đến đích hoặc thông tin rằng không thể định tuyến đến đích. - Thông tin lưu trữ trong Route Cache tại thời điểm 1 - Nút A, E, F sẽ phát gói tin RREQ đến các nút lân cận của nó (Hình 2.5.2) Hình 2.2.2. - Cơ chế duy trì thông tin định tuyến (Route Maintanance): Route Maintanance cho phép các nút trong hệ thống mạng tự động bảo trì thông tin định tuyến trong Route Cache. - Trong giao thức định tuyến DSR, các node khi chuyển gói tin trên mạng đều phải có nhiệm vụ xác nhận rằng các gói tin đó đã chuyển đến node kế tiếp hay chưa (thông qua sự phản hồi thông tin của node nhận. - Minh họa cơ chế duy trì thông tin định tuyến 2.4.2. - Giao thức AODV (Ad hoc On Demand Distance Vector): Giao thức định tuyến AODV là một trong những giao thức định tuyến theo cơ chế phản ứng trong hệ thống mạng MANET. - Tuy nhiên điểm khác biệt cơ bản đối với giao thức DSR là AODV sử dụng nhiều cơ chế khác để duy trì thông tin bảng định tuyến, chẳng hạn như nó sử dụng bảng định tuyến truyền thống để lưu trữ thông tin định tuyến với mỗi entry cho một địa chỉ đích. - [3] Không sử dụng cơ chế Source Routing và cũng không cần biết thông tin về các node láng giềng của nó, AODV dựa trên các entry của bảng định tuyến để phát gói tin RREP về node nguồn và node nguồn dùng thông tin đó để gởi dữ liệu đến đích. - Để đảm bảo rằng thông tin trong bảng định tuyến là mới nhất thì AODV sử dụng kỹ thuật Sequence Number (kỹ thuật này dùng để nhận ra các con đường đi không còn giá trị trong quá trình cập nhật bảng định tuyến) để loại bỏ những đường đi không còn giá trị trong bảng định tuyến. - [5] 50 Tương tự như cơ chế hoạt động của DSR, quá trình định tuyến của AODV cũng bao gồm 2 cơ chế chính: cơ chế tạo thông tin định tuyến và cơ chế duy trì thông tin định tuyến. - Cơ chế tạo thông tin định tuyến (Route Discovery): Cơ chế tạo thông tin định tuyến sẽ được thiết lập khi một nút nguồn có nhu cầu trao đổi thông tin với một nút khác trong hệ thống mạng. - o Khi nhận được một gói tin RREP gửi từ nút đích để trả lời gói tin RREQ, nó sẽ cập nhật lại giá trị Sequence number lớn nhất của một trong 2 giá trị: Sequence number hiện hành mà nó lưu giữ đối với Sequence number trong gói RREQ - Đối với REQ_ID: Khi có một sự thay đổi trong toàn bộ các nút lân cận của nó dẫn đến sẽ có một số tuyến đường trong bảng định tuyến sẽ không còn hiệu lực. - Các trường trong gói tin RREQ Tiến trình Route Discovery được khởi động khi nào một node muốn trao đổi dữ liệu với một node khác mà trong bảng định tuyến của nó không có thông tin định tuyến đến node đích đó. - Bước 2: Nếu trong bảng định tuyến của nó chứa đường đi đến đích, thì sẽ kiểm tra giá trị Destination sequence number trong entry chứa thông tin về đường đi với số Destination sequence number trong gói RREQ, nếu số Destination sequence number trong RREQ lớn hơn số Destination squence number trong entry thì nó sẽ không sử dụng thông tin trong entry của bảng định tuyến để trả lời cho node nguồn mà nó sẽ tiếp tục phát Broadcast gói RREQ đó đến cho các node láng giềng của nó. - Bước 3: Nếu trong bảng định tuyến của nó không có đường đi đến đích thì nó sẽ tăng số Hop-count lên 1, đồng thời nó sẽ tự động thiết lập một đường đi ngược (Reverse path ) từ nó đến node nguồn bằng cách ghi nhận lại địa chỉ của node láng giềng mà nó nhận gói RREQ lần đầu tiên. - Sau đó nó sẽ cập nhật các thông tin cần thiết vào trong bảng định tuyến của nó và chuyển gói RREP đi. - Cơ chế duy trì thông tin định tuyến: Như đã nhận xét ở trên, cơ chế hoạt động của AODV là không cần phải biết thông tin về các nút láng giềng, chỉ cần dựa vào các entry trong bảng định tuyến. - Thông tin định tuyến được lưu trữ tại tất cả các nút trung gian. - DSR sử dụng cơ chế định tuyến nguồn, theo đó nó luôn trả lời cho tất cả các yêu cầu tìm đường. - Kết luận chương 2: Định tuyến là một cơ chế không thể thiếu trong việc truyền tin trên các hệ thống mạng. - Trong chương này, chúng tôi đã nghiên cứu một số thuật toán định tuyến truyền thống, nêu ra những đặc điểm cơ bản mà các giao thức này không hiệu quả trên hệ thống mạng MANET. - Qua đó, chúng tôi đã phân loại 55 các giao thức định tuyến và phân tích sâu một số giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET và khả năng áp dụng của các giao thức trong từng môi trường mạng khác nhau. - 56 CHƯƠNG 3 MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU SUẤT MỘT SỐ GIAO THỨC ĐỊNH TUYẾN ĐIỀU KHIỂN THEO YÊU CẦU TRÊN MẠNG MANET Để đánh giá hiệu suất hoạt động của các giao thức thông thường người ta có thể dùng các phương pháp như: phương pháp giải tích, phương pháp thử nghiệm hoặc phương pháp mô phỏng. - các thuật toán định tuyến như Dijkstra… NS cũng thực thi multicasting và giao thức lớp Điều khiển truy cập đường truyền (MAC) đối với mô phỏng LAN. - Link Layer LL: Thông thường đối với tất cả các packet đi ra từ kênh, các packet được đưa xuống LL nhờ vào agent định tuyến Routing Agent. - Interface Queue: Lớp PriQueue được thực thi như một hàng đợi ưu tiên đưa ra các quyền ưu tiên để định tuyến các packet, thêm chúng vào đầu hàng đợi. - Thiết kế mô hình mạng để mô phỏng cho các giao thức định tuyến theo yêu cầu trên mạng MANET: Việc thiết kế và thử nghiệm cho các giao thức dựa trên phần mềm mô phỏng NS-2. - Hàng đợi kiểu FIFO, các gói tin định tuyến sẽ có độ ưu tiên cao hơn các gói tin dữ liệu. - yêu cầu các thiết bị để triển khai hệ thống mạng không dây. - phân tích một số công nghệ ứng dụng mạng không dây