Nghiên cứu một số giao thức định tuyến trên mạng Manet
Ngày nay, với sự bùng nổ và phát triển mạnh mẽ của công nghệ thông tin và sự đa dạng các thiết bị di động cá nhân như: laptop, smartphone, tablet thì nhu cầu kết nối giữa các thiết bị này cũng ngày càng đòi hỏi cao hơn về dịch vụ người sử dụng như chất lượng, dịch vụ QoS, tốc độ. Với sự cải tiến của công nghệ truyền thông không dây, trong vài năm trở lại đây mạng không dây ngày nay đã thu hút được sự quan tâm chú ý và phát triển ngày càng mạnh mẽ.
Mạng di động tùy biến không dây – MANET (Mobile Ad-hoc Network) – là một trong những công nghệ truyền thông không dây; bao gồm các thiết bị di động vô tuyến kết nối ngang hàng với nhau có khả năng thu phát độc lập, 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ới chi phí hoạt động thấp, triển khai nhanh, có tính di động cao, các thiết bị có thể di chuyển một cách tùy ý mà vẫn có thể truy cập mạng và có thể trao đổi dữ liệu với nhau, dễ dàng bổ sung, thay thế các thiết bị tham gia trong mạng mà không cần phải cấu hình phức tạp lại toàn bộ hình trạng (topo) của mạng. 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 thích nghi, bản ghi và lai. Tuy nhiên, hiện nay mạng MANET chưa được ứng dụng rộng rãi và vẫn còn những hạn chế như bán kính phủ sóng còn hạn chế, thiết bị phần cứng còn đắt, khả năng bảo mật chưa cao.
Để giải quyết những vấn đề này đã có nhiều nghiên cứu để cải tiến về giao thức truyền cũng như định tuyến đường truyền trên mạng để mạng đạt được hiệu quả hoạt động tốt hơn như những cải tiến của DSDV, OLSR, DDR, TORA cũng được nghiên cứu nhiều. Bên cạnh đó, còn nghiên cứu các giao thức định tuyến lai kết hợp cả giao thức định tuyến bản ghi và thích nghi như ZRP, HARP, DST, SHARP.
Chính vì những lý do trên, tôi chọn đề tài cho luận văn thạc sĩ là: “Nghiên cứu một số giao thức định tuyến trên mạng Manet” để hiểu tính tối ưu của các giao thức định tuyến trên mạng MANET.
2. Mục tiêu và nhiệm vụ đề tài
2.1. Mục tiêu
– Tìm hiểu rõ mạng di động tùy biến không dây (Mobile Ad Hoc Network – MANET)
– Mô phỏng được một số giao thức định tuyến.
2.2. Nhiệm vụ
– Tìm hiểu về các giao thức định tuyến trong mạng MANET.
– Xây dựng mô phỏng các giao thức định thức để đánh giá tính tối ưu của các giao thức định tuyến trên mạng MANET.
Trên cơ sở lý thuyết và so sánh, đánh giá tính tối ưu của một số giao thức định tuyến CBRP, ZRP, DSDV, AODV và cuối cùng đưa ra kết luận về tính tối ưu của giao thức định tuyến.
3. Đối tượng và phạm vi nghiên cứu
3.1. Đối tượng nghiên cứu
Một số giao thức định tuyến CBRP, ZRP, DSDV, AODV trên mạng MANET.
3.2. Phạm vi nghiên cứu
– Phạm vi nghiên cứu đề tài là nắm và hiểu rõ về mạng không dây mà đặc biệt là mạng MANET, một số giao thức định tuyến lai trên mạng MANET đồng thời đánh giá được các giao thức định tuyến dựa trên chương trình mô phỏng NS-2.
Để hoàn thành mục tiêu đề ra, tôi chọn phương pháp nghiên cứu lý thuyết và tiến hành mô phỏng thực nghiệm. Cụ thể như sau:
– Về lý thuyết: Thu thập, tìm hiểu, phân tích các tài liệu và thông tin có liên quan đến luận văn.
– Về thực nghiệm: Mô phỏng một số giao thức định tuyến.
– Nghiên cứu mạng không dây tùy biến MANET và các giao thức định tuyến.
– Chọn lựa 1 hoặc 2 giao thức định tuyến phù hợp để mô phỏng.
6.1. Lý thuyết
– Nghiên cứu tổng quan về mạng không dây và mạng MANET.
– Nghiên cứu các giao thức định tuyến trong mạng MANET.
– Tìm hiểu về mô phỏng bằng NS2
6.2. Thực tiễn
Hiểu sâu về mạng không dây và các giao thức định tuyến.
Luận văn tổ chức thành 3 chương chính như sau:
Chương 1: TỔNG QUAN VỀ MẠNG KHÔNG DÂY VÀ MẠNG MANET
Chương 2: MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRÊN MẠNG MANET
Chương 3: ĐÁNH GIÁ HIỆU NĂNG MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRÊN MẠNG MANET
TỔNG QUAN VỀ MẠNG KHÔNG DÂY VÀ MẠNG MANET
1.1. Khái quát về mạng không dây
Hiện nay, các mạng không dây và các thiết bị di động đang ngày càng trở nên phổ biến khi nó giúp cho người sử dụng có thể truy cập vào thông tin và truyền thông mọi lúc mọi nơi. Thông thường, việc kết nối thông tin liên lạc với các thiết bị không dây thường được hỗ trợ bởi một cơ sở hạ tầng cố định có dây. Một thiết bị di động sẽ sử dụng một cách thức định tuyến single-hop liên lạc qua môi trường vô tuyến để kết nối đến một máy trạm cơ sở của hệ thống mạng có dây. Ngược lại, các mạng ad-hoc không sử dụng bất kỳ cơ sở hạ tầng cố định. Mạng Adhoc là một tập hợp các nút mạng di động không dây nằm phân tán về mặt địa lý tạo thành một mạng tạm thời mà không sử dụng bất cứ cấu trúc hạ tầng mạng có sẵn hay sự quản lý tập trung nào. Các nút trong hệ thống mạng di động không dây tùy biến liên lạc với nhau thông qua cách thức định tuyến single-hop và multi-hop trong môi trường mạng ngang hàng (peer-to-peer). Các nút trung gian giữa một cặp của các nút giao tiếp sẽ đóng vai trò như một router. Vì vậy, các nút hoạt động cả hai như là máy chủ cũng như các bộ định tuyến. Các nút trong mạng ad hoc có thể có khả năng di động, và do đó, việc tạo ra các bảng định tuyến trong mạng cũng bị ảnh hưởng bởi việc bổ sung và xóa các nút khi nó di chuyển. Cấu trúc liên kết của mạng không dây có thể thay đổi ngẫu nhiên, nhanh chóng, và bất ngờ. [1][13]
1.2. Những đặc điểm chính của mạng không dây
Kiến trúc mạng thay đổi liên tục: Kiến trúc mạng luôn biến đổi do sự di chuyển của các nút mạng. Các nút của mạng Ad-học luôn biến đổi, thay đổi vị trí và di chuyển tự do theo nhiều hướng không thể xác định, dẫn đến liên kết giữa các nút mạng thay đổi liên tục. Vì vậy, kiến trúc mạng thay đổi liên tục làm ảnh hưởng đến hoạt động trao đổi thông tin giữa các nút mạng.
Hình 1.1. Phân loại các giao thức trong MANET
1.3.1.1. Giao thức định tuyến chủ động (Proactive Routing Protocol)
Trong phương pháp định tuyến theo bảng (chủ động), các nút trong mạng MANET liên tục đánh giá các tuyến tới các nút để duy trì tính tương thích, cập nhật của thông tin định tuyến. Vì vậy, một nút nguồn có thể đưa ra một đường dẫn định tuyến ngay lập tức khi cần. Trong các giao thức định tuyến theo bảng, tất cả các nút cần duy trì thông tin về cấu hình mạng. Khi cấu hình mạng thay đổi, các cập nhật được truyền lan trong mạng nhằm thông báo sự thay đổi. Hầu hết các giao thức định tuyến theo bảng đều kế thừa và sửa đổi đặc tính tương thích từ các thuật toán chọn đường dẫn ngắn nhất trong các mạng hữu tuyến truyền thống. Các thuật toán định tuyến theo bảng được sử dụng cho các nút cập nhật trạng thái mạng và duy trì tuyến bất kể có lưu lượng hay không. Vì vậy, tiêu đề thông tin để duy trì cấu hình mạng đối với các giao thức này thường là lớn. Một số giao thức định tuyến điển hình theo bảng trong MANET gồm: Giao thức định tuyến không dây WRP (Wireless Routing Protocol), định tuyến vector khoảng cách tuần tự đích DSDV (Destination Sequence Distance Vector), định tuyến trạng thái tối ưu liên kết OLSR (Optimized Link State Routing), định tuyến trạng thái góc rộng (Fisheye State Routing). [1]
1.4. Một số ứng dụng của mạng không dây.
Chương này giới thiệu về mạng không dây và mạng MANET, với những ưu điểm triển khai nhanh chóng, tự cấu hình và đáp ứng các đặc điểm di động mạng không dây và mạng MANET hứa hẹn mang đến sự phổ biến rộng rãi trong nhiều lĩnh vực. Tuy nhiên vẫn còn nhiều khó khăn thách thức về mặt công nghệ cần giải quyết như cấu trúc liên kết mạng thay đổi, vấn đề tiết kiệm năng lượng của các nút, lựa chọn giao thức định tuyến phù hợp. Xét thấy vấn đề định tuyến trong mạng Adhoc là vấn đề rất đáng quan tâm vì nó quyết định đến hiệu năng của mạng, vấn đề đó là làm định hướng cho việc nghiên cứu các chương tiếp theo.
CHƯƠNG 2
MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRÊN MẠNG MANET
2.1. Giao thức định tuyến CBRP (Cluster Based Routing Protocol)
Giao thức định tuyến dựa trên cụm (CBRP) là một giao thức định tuyến được thiết kế để sử dụng trong các mạng MANET. Giao thức phân chia các nút của mạng thành một số cụm chồng chéo hoặc rời nhau một cách phân phối. Nút trưởng cụm (Cluster head – CH) được bầu cho mỗi cụm để duy trì thông tin thành viên nhóm. Tuyến đường liên cụm được phát hiện tự động bằng cách sử dụng thông tin thành viên cụm lưu giữ tại mỗi CH. Bằng cách phân nhóm các nút thành các nhóm, giao thức giảm thiểu hiệu quả lưu lượng lũ lụt trong thời gian khám phá tuyến đường và tăng tốc quá trình này. Hơn nữa, giao thức đưa vào xem xét sự tồn tại của các liên kết đơn hướng và sử dụng các liên kết cho cả nội bộ cụm và tuyến đường liên cụm.[9]
Về cơ bản, trong khám phá tuyến đường, chỉ có nút CH là lũ lụt thông báo Route Request Packets (RREQ) để tìm kiếm một tuyến đường nguồn. [9]
Để thực hiện khám phá tuyến đường đến nút đích D, nút nguồn S gửi một thông báo RREQ, với trường địa chỉ nút mục tiêu được thiết lập là nút đích D. Nó điền vào mục Neighboring Cluster Head với các nút CH của nó và các mục nút CH liền kề (từ CAT), Gateway Node Address tương ứng hoặc là nút CH của chính nó hoặc là nút gateway của cụm liền kề. Đây là thông báo RREQ ban đầu được phát sóng.
Hình 2.2. Sơ đồ cơ chế định tuyến CBRP
Cluster Address cung cấp đầy đủ thông tin về trình tự của cụm mà RREP cần phải đi qua để đến nút S. Vì mỗi nút CH có kiến thức về việc làm thế nào để tiếp cận với các nút CH láng giềng, gói tin RREP sẽ được chuyển đến S cuối cùng bằng cách sử dụng định tuyến IP nguồn lỏng (loose).
Nếu một nút nguồn không nhận được bất kỳ thông báo RREP sau khi gửi đi RREQ một thời gian nhất định, nó đi vào exponential backoff trước khi gửi lại RREQ. [7]
Như thường lệ, tất cả các tuyến đường nguồn biết được bởi một nút được lưu giữ trong một Route Cache. Khi một nút muốn gửi một gói tin, nó luôn luôn kiểm tra Route Cache của nó đầu tiên trước khi thực hiện khám phá tuyến đường.
Bảng định tuyến được tạo ra do bởi địa chỉ của nút trưởng cụm. Điều này có nghĩa rằng, trong bảng định tuyến, địa chỉ của nút CH tiếp theo được lưu cho đến điểm đến bất kỳ. Trong những phương pháp trước đó nếu một nút thất bại trong việc định tuyến tuyến đường hoặc di chuyển cách xa các nút hàng xóm của nó, nó gây ra thất bại cho các tuyến đường và dẫn đến phải tái tạo lại tuyến đường.
Hình 2.3. Sửa chữa tuyến đường khu vực
2.1.3. Cơ chế cảm biến trạng thái kết nối
Trong CBRP, mỗi nút biết liên kết hai chiều của nó đến các nút láng giềng cũng như liên kết một chiều từ các nút láng giềng đến chính nó. Với mục đích này, mỗi nút duy trì một neighbor table (Neighbor table) là một khái niệm cấu trúc dữ liệu mà ta sử dụng cho việc nhận biết trạng thái liên kết và hình thành cụm. Gồm các mục: ID của nút láng giềng mà nó có kết nối; Vai trò của nút láng giềng nút CH hoặc nút thành viên cụm; Trạng thái của liên kết đó, hai chiều hoặc một chiều). Mỗi nút định kỳ phát sóng thông tin neighbor table của nó trong một tin nhắn HELLO, định kỳ mỗi giây hello_interval (tin nhắn HELLO của một nút chứa neighbor table của nó và cluster adjacency table – lưu giữ thông tin về các cụm liền kề và được duy trì bởi thủ tục khám phá cụm liền kề – Adjacent Cluster Discovery – của CBRP, gồm các mục: ID của nút CH lân cận; Nút gateway để tiếp cận với nút CH lân cận; Trạng thái của liên kết từ nút gateway của cụm lân cận đến nút CH đó. Một nút đôi khi có thể phát sóng một tin nhắn kích hoạt HELLO để đáp ứng với một số sự kiện cần hành động nhanh chóng). [6]
2.1.4. Cơ chế hình thành cụm (Cluster)
Một cụm bao gồm một nhóm các nút với một trong số các nút đó được bầu là một nút trưởng cụm (cluster head – CH). Một cụm được xác định bởi ID trưởng cụm của nó (ID nút là một chuỗi xác định duy nhất một nút cụ thể, phải được sắp xếp hoàn toàn. Ở đây, ta sử dụng địa chỉ IP của một nút như ID của nó cho các mục đích của định tuyến và khả năng tương tác với các mạng cố định). Cụm hoặc chồng chéo hoặc phân chia. Mỗi nút trong mạng biết nút trưởng cụm (s) tương ứng của nó và do đó biết nó thuộc về cụm (s) nào. [7]
2.1.5. Khám phá cụm liền kề (Adjacent Cluster Discovery)
CBRP sử dụng hai cấu trúc dữ liệu để hỗ trợ quá trình định tuyến: Cluster Adjacency Table (CAT) và cơ sở dữ liệu two-hop-topology. CAT lưu trữ thông tin về các cụm lân cận là liên kết hai chiều hoặc liên kết một chiều. Điều đó có nghĩa, một cụm được gọi là
+ Có liên kết hai chiều, nếu có một liên kết hai chiều giữa hai nút của cụm, hoặc nếu có ít nhất hai liên kết đơn hướng đối diện giữa hai nút (hình 2.18, cụm A và cụm C, cụm A và cụm B có liên kết hai chiều)
+ Có liên kết một chiều, nếu có chỉ là một liên kết đơn hướng giữa chúng (hình 2.18, cụm C và cụm D có liên kết một chiều). [9]
2.2. Giao thức định tuyến ZRP (Zone Routing Protocol)
Giao thức định tuyến ZRP kết hợp những ưu điểm của các phương pháp tiếp cận chủ động và bị động bằng cách duy trì một bản đồ liên tục cập nhật cấu trúc liên kết của một vùng định tuyến chủ động trên mỗi nút. Trong vùng định tuyến chủ động, tuyến đường có sẵn ngay lập tức. Đối với các nút bên ngoài vùng định tuyến, ZRP sử dụng một thủ tục khám phá tuyến, có thể được thừa hưởng từ thông tin định tuyến địa phương của vùng định tuyến chủ động. [5]
2.2.1. Vùng định tuyến và định tuyến nội vùng (Intrazone Routing Protocol – IARP)
Một vùng định tuyến của nút X là bao gồm các nút nằm trong một vùng có bán kính nhất định, gọi là bán kính vùng (Radius Zone). Bán kính của một vùng định tuyến không được xác định bằng số đo địa lý thông thường mà xác định bởi một số p cho trước (p là số bước nhảy của vùng). Các nút nằm trong vùng định tuyến của nút X sẽ có khoảng cách từ nó đến nút X nhỏ hơn hoặc bằng một số p bước nhảy được xác định trước. [5]
2.2.2. Định tuyến liên vùng (IERP)
Trong khi IARP duy trì các tuyến đường trong phạm vi của vùng định tuyến, thì IERP lại chịu trách nhiệm cho việc tìm kiếm các tuyến đường đến các nút nằm ngoài phạm vi vùng định tuyến (khoảng cách lớn hơn bán kính vùng).
2.2.3. Giải pháp quảng bá biên BRP (Bordercast Resolution Protocol)
BRP cung cấp cung cấp dịch vụ quảng bá tin nhắn, ở đây nó được sử dụng để chuyển tiếp các truy vấn tuyến đường của IERP đến các nút biên. Để thực hiện được, BRP sẽ sử dụng bản đồ các nút nằm trong vùng định tuyến do IARP cung cấp để xây dựng một cây quảng bá biên. [10]
2.2.4. Cơ chế kiểm soát truy vấn (Query Control)
Ta thấy ZRP có thể được thực hiện hiệu quả hơn bằng cách sử dụng quảng bá biên truy vấn đến nút biên của một vùng định tuyến thay vì lũ lụt các truy vấn trong cùng một mạng. Để đạt được hiệu quả điều này, giao thức sẽ phải thực hiện được một việc đó là phát hiện và chấm dứt một sự truy vấn khi nó xuất hiện trong một vùng định tuyến mà trước đã được truy vấn (tức là đến một nút thuộc vùng định tuyến của một nút đã được truy vấn trước đó).
2.3. Giao thức định tuyến DSDV (Destination – Sequenced Distance – Vector)
Là dựa trên thuật toán Distance vector. Giao thức này được xây dựng dựa theo tiêu chí giữ nguyên sự đơn giản của giải thuật Bellman-Ford và loại bỏ vấn đề vòng lặp. Truyền thông tin định tuyến: Thông tin định tuyến được gửi quảng bá (broadcast) tới tất cả các nút liền kề nó. Thông tin cập nhật được phát định kỳ hoặc ngay khi có các thay đổi xảy ra trong mạng. Ðể tránh lặp, định tuyến DSDV gắn số thứ tự chẵn cho mỗi đường. Số thứ tự được gắn bởi nút đích, được gửi trong gói tin cập nhập. Số thứ tự này cho thấy độ mới của mỗi đường, đường nào có số thứ tự cao hơn được xem là tốt hơn.
2.4. Giao thức định tuyến AODV
Giao thức định tuyến AODV dựa trên thuật toán vector khoảng cách nhưng thuộc loại định tuyến theo yêu cầu, nó chỉ yêu cầu đường định tuyến khi cần thiết. Giao thức này không sử dụng cơ chế định tuyến nguồn và cũng không cần biết thông tin về các nút 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ề nút nguồn và nút nguồn dùng thông tin đó để gởi dữ liệu đến đích.
Quá trình khám phá đường được phát động mỗi khi một nút nguồn cần truyền thông với một nút khác khi mà nó không có thông tin định tuyến về nút này trong bảng của nó. Nút nguồn phát động khám phá đường bằng việc quảng bá gói Route Request (RREQ) tới các hàng xóm của nó.
2.4.2. Thiết lập đường đảo chiều
Có hai số thứ tự (ngoại trừ số thứ tự của broadcast_id) trong một RREQ đó là: Số thứ tự nguồn và số thứ tự đích mới nhất. Số thứ tự nguồn được sử dụng để duy trì thông tin về “độ mới” của tuyến đường đảo chiều đến nguồn, số thứ tự đích chỉ rõ tuyến đường tới đích phải “mới” như thế nào mới được nút nguồn chấp nhận. RREQ đi từ một nguồn đến nhiều đích khác nhau, các đường đảo chiều về nút nguồn sẽ được thiết lập tự động tại tất cả các nút mà nó đi qua. Ðể thiết lập đường đảo chiều, một nút ghi lại địa chỉ của nút lân cận từ bản sao RREQ đầu tiên mà nó nhận được. Tuyến đường đảo chiều này được duy trì trong khoảng thời gian ít nhất đủ cho gói tin RREQ đi qua mạng và tạo được một phản hồi về cho bên gửi.
Mỗi nút gửi định kì các bản tin Hello tới các chặng trước của nó. Một nút quyết định gửi một bản tin Hello tới một chặng trước xác định chỉ khi nếu không có bản tin nào được gửi gần đây tới chặng trước đó. Do đó, mỗi nút mong đợi nhận định kì các bản tin (không giới hạn các bản tin Hello) từ mỗi nút trong danh sách cổng ra của nút. Nếu một nút không nhận được bản tin nào từ một vài nút cổng ra trong một khoảng thời gian dài, khi đó nút được cho là không còn có thể tới được.
2.4.6. Xử lý lỗi, hết hạn và xóa bỏ tuyến
Thông thường, việc xử lý RERR và liên kết gãy cần đến các bước sau đây:
- Làm mất hiệu lực các tuyến hiện tại.
- Liệt kê các đích bị ảnh hưởng.
- Xác định rõ nếu có bất kì nút lân cận nào có thể bị ảnh hưởng.
- Thực hiện một RERR tới các nút lân cận.
2.4.7. Quản lý kết nối nội vùng
Các nút có thể học thông tin từ nút lân cận của chúng bằng một hoặc nhiều cách khác nhau. Bất cứ khi nào một nút nhận được quảng bá từ một nút lân cận, nó cập nhật thông tin kết nối nội bộ để đảm bảo đang liên kết với nút lân cận này. Khi một nút chưa gửi gói tin nào cho các nút lân cận trong khoảng thời gian Hello, nó quảng bá tới các nút lân cận một bản tin Hello, một bản tin RREP đặc biệt chứa nhận dạng và số thứ tự của nó. Số thứ tự của nút không được thay đổi khi truyền dẫn bản tin Hello. Bản tin Hello này không được quảng bá ra ngoài vùng lân cận do giá trị thời gian sống Time-To-Live (TTL) là 1. Các nút lân cận nhận gói tin này sẽ cập nhật thông tin kết nối nội bộ chứa trong gói tin.
2.4.8. So sánh ưu điểm và nhược điểm của các giao thức ZRP, CBRP
Ưu điểm:
⮚ Điểm giống nhau của các giao thức ZRP và CBRP là chúng đều sử dụng các phương thức phân từng khu vực định tuyến (vùng định tuyến, cây phân phối, cụm) nhằm để duy trì bảng định tuyến khu vực, nếu nút đích nằm trong khu vực định tuyến nó sẽ sử dụng bảng định tuyến khu vực để gửi gói dữ liệu; ngược lại, nếu nút đích nằm ngoài vùng định tuyến thì chúng sử dụng cơ chế định tuyến liên khu vực để định tuyến gói dữ liệu. Điều này giúp giảm chi phí trong việc định tuyến và nâng cao hiệu năng hoạt động của các giao thức.
⮚ Điểm khác nhau của các giao thức ZRP và CBRP là mỗi giao thức có cách phân khu vực định tuyến với các phương pháp khác nhau và cách phân vùng định tuyến này ảnh hưởng đến hiệu năng của từng giao thức.
⬩ Đối với giao thức ZRP, giao thức này kết hợp hai phương pháp định tuyến hoàn toàn khác nhau thành một giao thức. ZRP phân vùng định tuyến dựa trên số bước nhảy, các vùng định tuyến là chồng chéo nhau. Trong vùng định tuyến, thành phần chủ động IARP duy trì bảng định tuyến up-to-date. Các tuyến đường ngoài vùng định tuyến được phát hiện bởi thành phần bị động IERP. Bằng cách kết hợp quảng bá biên, phát hiện truy vấn và chấm dứt sớm, nó có thể làm giảm lưu lượng truy vấn. Các tuyến đường đến các nút trong vùng đều có sẵn ngay lập tức. ZRP có thể xác định nhiều tuyến đường đến một địa điểm, cung cấp độ tin cậy và hiệu suất cao. ZRP là một giao thức phẳng, làm giảm ùn tắc và chi phí thường liên quan đến các giao thức phân cấp.
⬩ Đối với giao thức CBRP, các nút được chia thành cụm. Nó sử dụng cấu trúc phân cụm cho giao thức định tuyến. Bằng cách phân cụm, giao thức giảm tối thiểu lưu lượng lũ lụt trong thời gian khám phá tuyến và tăng tốc quá trình này. Rút ngắn tuyến đường của nó và các tính năng sửa chữa địa phương sử dụng các thông tin cơ sở dữ liệu two-hop-topology được duy trì bởi mỗi nút thông qua việc phát sóng các thông điệp HELLO. CBRP có kiểm soát trên định tuyến nhỏ, tắc nghẽn mạng ít hơn và thời gian tìm kiếm trong quá trình định tuyến.
Nhược điểm:
⬩ Đối với ZRP, do vùng định tuyến của nó thường chồng chéo nhau nên một nút có thể nhận được nhiều gói tin cùng định tuyến một tuyến đường.
⬩ Đối với CBRP, nếu mạng và cụm trở nên quá lớn, chi phí cho mỗi gói tin tăng lên do nguồn định tuyến. Tất cả các nút của các tuyến đường đã được lưu trữ trong các gói tin định tuyến. Vì vậy, các kích thước gói tăng tỷ lệ thuận với chiều dài đường đi của tuyến đường. Theo đó, thời gian truyền cũng tăng. Ngoài ra, nếu kích thước cụm tăng thì kích thước của thông điệp Hello và lưu trữ dữ liệu cấu trúc cũng tăng.
2.4.9. So sánh các giao thức định tuyến
| Giao thức | Thông tin lưu trữ | Thời gian cập nhật | Thông tin cập nhật | Đối tượng cập nhật |
| AODV | Chặng tiếp theo tới mỗi đích có giao tiếp | Cơ chế duy trì đường theo sự kiện | Thông điệp lỗi đường (route error) | Nút nguồn |
| DSDV | Toàn bộ cấu hình mạng | Ðịnh kỳ | Thông điệp : thông tin liên kết cục bộ và hàng xóm (MPR) Thông điệp TC : thông tin về các MPR | Tất cả cả nút trong mạng |
Trong đó:
Thông tin lưu trữ: Thông tin được lưu tại mỗi nút
Việc định tuyến trong hệ thống mạng MANET yêu cầu thời gian định tuyến hiệu quả và tiết kiệm tài nguyên. Một cách tiếp cận để giảm lưu lượng trong quá trình định tuyến là chia mạng thành các cụm (vùng) nhỏ. Trong chương này, chúng tôi đã phân tích cơ chế hoạt động của các giao thức định tuyến ZRP DSDV, , AODV, ZRP, thuộc giao thức định tuyến lai ghép trong mạng MANET, đồng thời đã làm rõ được ưu nhược điểm của chúng và làm cơ sở lý thuyết cho việc mô phỏng trong chương3
CHƯƠNG 3
ĐÁNH GIÁ HIỆU NĂNG MỘT SỐ GIAO THỨC ĐỊNH TUYẾN 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. Trong luận văn này, chúng tôi chọn phương pháp mô phỏng để đánh giá hiệu năng hoạt động của giao thức định tuyến lai ghép dựa trên phần mềm mô phỏng mạng NS2.
3.1. Giới thiệu môi trường mô phỏng NS
NS (Network Simulation) là phần mềm mô phỏng mạng điều khiển sự kiện riêng lẻ hướng đối tượng, được phát triển tại UC Berkely, viết bằng ngôn ngữ C++ và Otcl [17],[18]. NS rất hữu ích cho việc mô phỏng các hệ thống mạng hữu tuyến và vô tuyến, NS có các đặc điểm cơ bản sau:
– Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại.
– Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng.
– Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi được trong thực tế.
– Khả năng mô phỏng nhiều loại mạng khác nhau. [1]
NS2 là một công cụ giả lập hướng đối tượng được viết bằng ngôn ngữ C++ trong phần nhân và ngôn ngữ thông dịch Otcl ở phần giao tiếp.[1]
Bộ giả lập NS2 bao gồm 3 module chính:
– Module nhân được gọi là Compiler Hierarchy.
– Module giao tiếp được gọi là Interpreted Hierarchy.
– Module liên kết là module có tác dụng như một lớp keo dùng để gắn kết các lớp, các đối tượng, các biến tương ứng trong hai module nhân và module giao tiếp với nhau.
3.2. Mô phỏng mạng không dây trong môi trường mạng NS
Thực chất mô hình wireless bao gồm MobileNode trong lõi (core) cùng với các đặc tính hỗ trợ thêm vào cho phép các trình mô phỏng của mạng multihop với thủ tục Ad-Hoc, mạng LAN wireless… Đối tượng MobileNode là một đối tượng tách biệt. Lớp MobileNode trong C++ xuất phát từ lớp cha là lớp Node. Vì vậy, một MobileNode là một đối tượng Node cơ sở cộng thêm các chức năng của wireless, có khả năng di chuyển bên trong một topo và nhận hoặc truyền tín hiệu thông qua một kênh wireless. [1]
3.3. Mô phỏng giao thức định tuyến ZRP
3.3.2. Xây dựng kịch bản mô phỏng
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 NS2. Mô hình thiết kế cho các nút mạng di chuyển ngẫu nhiên trong khu vực bán kính 5000m. Các gói tin phát dựa vào dịch vụ CBR (constant bit race), với kích thước gói tin 512 byte/1 gói tin, chu kỳ gửi tin 4 gói/1 giây. 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.
Hình 3.2. Mô hình mạng mô phỏng đang hoạt động
3.4. Phân tích kết quả mô phỏng
3.4.1. Đánh giá hiệu năng của giao thức định tuyến ZRP
Các yếu tố chính ảnh hưởng đến hiệu năng của giao thức ZRP là bán kính vùng định tuyến p, số lượng nút N và tốc độ di chuyển v của nút mạng.
⬩ Sự tác động của số lượng nút mạng N, bán kính vùng định tuyến p đến hiệu năng hoạt động của giao thức ZRP.
Bảng 3.1. Tỷ lệ gói tin gửi thành công theo N
| p N | p=1 | p=3 | p=4 | p=7 | p=10 |
| 100 | 37,50% | 74,32% | 85,99% | 89,13% | 85,43% |
| 200 | 34,38% | 77,36% | 91,10% | 94,54% | 89,30% |
| 300 | 34,29% | 84,17% | 92,68% | 96,54% | 89,16% |
Điều này cho thấy, số lượng nút mạng ảnh hưởng đến hiệu năng hoạt động của giao thức ZRP, khi số lượng nút mạng càng lớn thì hiệu năng hoạt động của giao thức ZRP càng tăng. Nhưng, chúng tôi thấy với bán kính vùng định tuyến p=10 tỷ lệ gói tin gửi thành công tương ứng với số lượng nút mạng 200, 300 là 89,30%; 89,16%. Từ đó cho thấy khi số lượng nút tăng, với bán kính vùng định tuyến thích hợp thì hiệu năng hoạt động của giao thức ZRP sẽ tăng, nhưng với bán kính không thích hợp thì hiệu năng hoạt động của giao thức sẽ giảm.
Hình 3.3. Biểu đồ về sự tác động của N
Theo kết quả mô phỏng, khi bán kính p tăng lên (p=3, p=4, p=7) thì tỷ lệ gói tin gửi thành công tăng lên, cụ thể như với số lượng nút mạng là 100 nút mạng thì tỷ lệ gói tin gửi thành công của ZRP tương ứng với p = 3; 4; 7 là 74,32%; 85,99%; 89,13%. Nguyên nhân là khi p tăng thì hoạt động của giao thức đã có sự phối hợp giữa hai giao thức định tuyến nội vùng (IARP) và giao thức định tuyến liên vùng (IERP). Điều này đã làm cho hiệu năng hoạt động của giao thức ZRP tăng lên.
Bảng 3.2. Độ trễ trung bình theo N
| p N | p=1 | p=3 | p=4 | p=7 | p=10 |
| 100 | 0,000676 | 0,000417 | 0,000305 | 0,000248 | 0,000272 |
| 200 | 0,000538 | 0,000401 | 0,000326 | 0,000276 | 0,000293 |
| 300 | 0,000539 | 0,000438 | 0,000417 | 0,000371 | 0,000328 |
Hình 3.4. Biểu đồ về độ trễ trung bình theo N
⬩ So sánh hiệu năng hoạt động của giao thức ZRP và CBRP dựa trên vận tốc di chuyển của nút mạng
Theo kết quả mô phỏng, tôi thấy với vận tốc di chuyển của nút mạng nhỏ từ 5km/h đến 15km/h thì hiệu năng hoạt động của giao thức định tuyến CBRP tốt hơn giao thức định tuyến ZRP. Nhưng khi vận tốc di chuyển của nút mạng nhanh hơn từ 20km/h trở lên thì hiệu năng hoạt động của giao thức định tuyến ZRP hoạt động tốt hơn. Xảy ra điều này là do khi vân tốc di chuyển nút mạng nhỏ thì kiến trúc liên kết mạng ít thay đổi nên giao thức định tuyến CBRP ít tốn chi phí cho việc tái tạo, hình thành lại cụm, khám phá cụm liền kề, cập nhật Cluster Adjacency Table; nhưng khi vận tốc di chuyển nút mạng nhanh thì giao thức CBRP phải tốn chi phí cho các việc trên, trong khi đó giao thức ZRP chỉ tốn chi phí cho việc cập nhật bảng định tuyến nội vùng khi các vùng định tuyến thay đổi. Vì vậy, giao thức định tuyến ZRP sẽ hoạt động tốt hơn.
Chương này, tôi đã trình bày về các bước để cài đặt phần mềm mô phỏng NS-2, các bước để xây dựng tập lệnh mô phỏng giao thức hoạt động mạng MANET. Tôi đã xây dựng được mô hình mạng MANET để mô phỏng cho giao thức định tuyến ZRP, sử dụng kết quả mô phỏng để đánh giá sự tác động của vận tốc di chuyển nút mạng, số lượng nút mạng, bán kính định tuyến vùng đến hiệu năng hoạt động của giao thức ZRP; đồng thời sử dụng kết quả mô phỏng để so sánh với kết quả mô phỏng của tác giả trong tài liệu [7] và đưa ra đánh giá như sau:
– Đối với giao thức định tuyến CBRP, giao thức này hoạt động thích hợp với môi trường mạng có số lượng nút mạng ít, vận tốc di chuyển nút mạng nhỏ.
– Đối với giao thức định tuyến ZRP, giao thức này hoạt động thích hợp với vùng định tuyến chủ động lớn, vận tốc di chuyển nút mạng nhanh và số lượng nút mạng lớn.
Hiện nay, mạng MANET còn rất nhiều thách thức về mặt công nghệ cần được giải quyết, trong đó vấn đề định tuyến đường đi cho các gói tin truyền trong mạng là vấn đề quan trọng và cơ bản nhất vì nó ảnh hưởng đến hiệu năng hoạt động của mạng và là một thách thức lớn đối với các nhà nghiên cứu tìm ra các chuẩn cho phù hợp nhằm nâng cao hiệu quả hoạt động của mạng và đáp ứng kịp thời với nhu cầu phát triển của xã hội.
Qua thời gian học tập và nghiên cứu đề tài, luận văn đã đạt được một số yêu cầu đầu tiên trong lĩnh vực nghiên cứu và từ đó định hướng phát triển tiếp theo của đề tài luận văn cũng như tiến xa hơn nữa trong lĩnh vực nghiên cứu về các giao thức định tuyến trong mạng máy tính cụ thể là mạng MANET.
1. Kết quả đạt được trong luận văn
– Tìm hiểu tổng quan về mạng máy tính cụ thể là mạng không dây và mạng MANET, các kỹ thuật, công nghệ dùng cho mạng và cách phân loại, mô hình mạng không dây và mạng MANET tương ứng, những đặc điểm chính của ứng dụng, các thuật toán định tuyến trong mạng không dây và mạng MANET.
– Nghiên cứu cơ chế hoạt động của giao thức định tuyến CBRP, ZRP, DSDV và AODV.
– Thiết kế mô hình mạng MANET trên công cụ mô phỏng NS-2. Cài đặt và mô phỏng giao thức định tuyến ZRP.
– Từ kết quả mô phỏng đã đánh giá sự tác động các yếu tố đến hiệu năng hoạt động của giao thức định tuyến ZRP, đồng thời so sánh hiệu năng hoạt động của giao thức định tuyến ZRP với giao thức định tuyến CBRP trên mạng MANET.
2. Hạn chế trong luận văn:
– Chưa nghiên cứu sâu về cấu trúc các gói tin định tuyến trong giao thức.
– Chưa nghiên cứu, tìm ra các giải pháp để nâng cao hiệu năng hoạt động của các giao thức CBRP, DSDV và AODV, đồng thời hạn chế các khuyết điểm của chúng.
– Cài đặt và mô phỏng được hoạt động của giao thức định tuyến ZRP, nhưng chưa mô phỏng được hoạt động của ba giao thức định tuyến CBRP, DSDV, AODV.
2. Định hướng phát triển của đề tài
Vấn đề hướng phát triển tiếp là tiếp tục nghiên cứu giao thức định tuyến lai và đưa ra giải pháp tối ưu về chất lượng dịch vụ cũng như việc sử dụng trên mạng MANET. Cài đặt và mô phỏng hoạt động của ba giao thức định tuyến CBRP, DSDV, AODV.
E:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\HE THONG THONG TIN\DO VAN LAI\DO VAN LAI\TOM TAT
