Đánh giá một số giao thức định tuyến đa đường giảm thời gian trễ trong mạng Manet - Đỗ Đình Cường

Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 51 ĐÁNH GIÁ MỘT SỐ GIAO THỨC ĐỊNH TUYẾN ĐA ĐƯỜNG GIẢM THỜI GIAN TRỄ TRONG MẠNG MANET Đỗ Đình Cường*, Nguyễn Anh Chuyên Trường Đại học Công nghệ Thông tin & Truyền thông – ĐH Thái Nguyên TÓM TẮT Trong những năm gần đây có một hướng tiếp cận mới cho bài toán định tuyến trong mạng MANET là định tuyến đa đường. Bài báo này trình bày một cách tổng quan về các đặc điểm chính trong cơ chế hoạt động của một số giao thức định tuyến đa đường mới cho mạng MANET tiếp cận theo mục tiêu giảm thời gian trễ, sau đó thực hiện việc phân tích, so sánh và đánh giá chúng theo các tiêu chí về hiệu năng hoạt động, đồng thời chỉ ra hướng cần cải tiến của các giao thức này. Từ khoá: Mạng MANET, Định tuyến đa đường, Thời gian trễ, Tìm đường, Lựa chọn đường. GIỚI THIỆU* Mạng không dây di động không cấu trúc (MANET) là một mạng bao gồm tập các nút di động không có cơ chế quản trị tập trung. Mạng MANET có khả năng tự cấu hình, tự tổ chức và tự bảo trì hoạt động của mình, có thể tương thích với các mạng có hình trạng động. Tuy nhiên, mỗi nút di động lại có những hạn chế về tài nguyên như năng lượng nguồn, khả năng xử lý và bộ nhớ. Cơ chế truyền thông giữa các nút di động trong mạng MANET là cơ chế đa chặng. Do đó, thời gian tồn tại của mỗi nút đi động trong mạng là rất quan trọng. Việc thiết kế giao thức định tuyến hiệu quả cho mạng MANET là một bài toán được quan tâm nhiều trong các nghiên cứu về hệ thống mạng di động trong thời gian qua. Có nhiều giao thức định tuyến đơn đường cho mạng MANET đã được đề xuất và có thể chia chúng thành hai nhóm chính là các giao thức “tìm đường trước” và các giao thức “tìm đường theo yêu cầu”. Các giao thức này đều chỉ sử dụng duy nhất một con đường tối ưu để truyền dữ liệu giữa một cặp nút nguồn-đích. Thông thường đây là con đường ngắn nhất. Các nghiên cứu trong [1], [2], [10] và [13] đã chỉ ra rằng, thuật toán tìm đường ngắn nhất không phải là lựa chọn tốt nhất cho mạng MANET. Khi thuật toán này được sử dụng, các nút phân bố xung quanh tâm sẽ phải truyền lưu lượng dữ liệu định tuyến nhiều hơn các nút phân bố gần biên của mạng. Điều này * Tel: 0982 990908, Email: ddcuong@ictu.edu.vn có thể gây ra tình trạng tắc nghẽn khi có nhiều kết nối được thiết lập trong mạng làm ảnh hưởng tới hiệu năng mạng ở khía cạnh thời gian trễ và thông lượng. Để giải quyết các hạn chế này, thay vì việc tìm ra và sử dụng duy nhất một con đường để truyền dữ liệu, sẽ có nhiều hơn một con đường được sử dụng đồng thời để truyền dữ liệu trong các giao thức định tuyến đa đường. Các giao thức định tuyến đa đường được phân loại theo mục tiêu tiếp cận của chúng. Trong số năm nhóm giao thức định tuyến đa đường đã được phân loại trong [12], bài báo này chỉ tập trung đánh giá nhóm thứ nhất là nhóm các giao thức định tuyến đa đường giảm thời gian trễ. Nhóm này bao gồm các giao thức: Định tuyến đường dự phòng [8], định tuyến đa đường trên cơ sở định tuyến vùng Fresnel (FZR) [7], định tuyến AODV đa đường với cơ chế chọn đường theo xác suất (AODVM- PSP) [6], định tuyến đa đường có độ ưu tiên (PRIMAR) [5], định tuyến theo góc địa lý (BGR) [11] và định tuyến đa đường Split-n- save [4]. Phần còn lại của bài báo được tổ chức như sau: Mục 2 trình bày về hoạt động chi tiết, ưu điểm, nhược điểm và các hạn chế của các giao thức định tuyến đa đường nhằm giảm thời gian trễ đã nói đến ở trên. Mục 3 thực hiện việc so sánh phân tích các giao thức đã đưa ra trên các tham số về hiệu năng. Mục 4 phân tích các nhược điểm cần cải tiến của các giao thức này và Mục 5 là kết luận của bài báo. Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 52 ĐỊNH TUYẾN ĐA ĐƯỜNG NHẰM GIẢM THỜI GIAN TRỄ Phần lớn các giao thức định tuyến đa đường đều được phát triển từ các giao thức định tuyến đơn đường truyền thống dành cho mạng MANET là giao thức DSR[3] và AODV[9]. Tuy nhiên các giao thức DSR và AODV không có khả năng tương thích cao với các mạng có kích thước thay đổi thường xuyên. Vấn đề thay đổi hình trạng mạng dẫn đến tình trạng làm tăng các gói tin điều khiển, tăng thời gian trễ, mất độ tin cậy khi truyền dữ liệu và tốn năng lượng nguồn nuôi các nút di động. Thời gian trễ lớn khi truyền gói tin giữa hai điểm đầu-cuối là một vấn đề ảnh hưởng nhiều tới hiệu năng của các giao thức định tuyến theo yêu cầu. Nguyên nhân của vấn đề này là việc lựa chọn đường không hiệu quả, cân bằng tải không thích hợp và số lượng gói tin điều khiển lớn. Mục tiêu chính của những giao thức định tuyến thuộc nhóm định tuyến đa đường nhằm giảm thời gian trễ là đảm bảo cân bằng tải dữ liệu giữa các nút di động sao cho không có đoạn mạng nào bị tắc nghẽn. Các tác giả Pham và Perau trong [10] đã chỉ ra rằng nếu sử dụng định tuyến chọn đường ngắn nhất, các liên kết gần tâm của mạng phải hoạt động nhiều hơn so với các liên kết ở gần biên. Do đó không đảm bảo cân bằng tải dữ liệu giữa các nút mạng và điều này làm cho thời gian trễ của các gói tin phải truyền qua tâm của mạng tăng lên. Để giải quyết vấn đề này các giao thức định tuyến đa đường giảm thời gian trễ dành cho mạng MANET đã được đề xuất. Giao thức định tuyến đa đường dự phòng Một cơ chế định tuyến có tên gọi là định tuyến đa đường dự phòng đã được tác giả Lim giới thiệu trong [8] nhằm cải thiện hiệu năng của các mạng sử dụng giao thức TCP ở tầng Chuyển vận. Tác giả này đã phát biểu rằng mặc dù giao thức định tuyến đa đường làm việc tốt với các lưu lượng UDP nhưng khi sử dụng các lưu lượng TCP, hiệu năng của nó sẽ bị giảm. Vấn đề giảm hiệu năng này do một trong các nguyên nhân sau gây nên: thứ nhất là không ước lượng được một cách chính xác thời gian truyền một vòng trung bình (RTT) trong định tuyến đa đường bởi vì mỗi một con đường có một giá trị RTT khác nhau và thứ hai là các gói tin đi theo các con đường khác nhau tới đích với thứ tự thay đổi có thể làm cho nút đích gửi đúp gói báo nhận dẫn tới việc giảm một cách không cần thiết kích thước cửa sổ trượt. Để giải quyết vấn đề này, chỉ có một con đường được sử dụng tại một thời điểm nhưng vẫn cần duy trì các con đường dự phòng. Vấn đề quan trọng ở đây chính là cơ chế lựa chọn đường chính cũng như lựa chọn một tập các đường dự phòng. Khác với giao thức DSR, một nút đích chỉ trả lời hai gói yêu cầu tìm đường. Một gói trả lời đường chứa đường chính và một gói khác chứa đường dự phòng. Nút đích sử dụng ba điều kiện chính để lựa chọn đường: (1) đường ngắn nhất, (2) đường có thời gian trễ nhỏ nhất và (3) đường khác biệt nhiều nhất. Đường ngắn nhất tương tự như đường do giao thức DSR lựa chọn. Sự kết hợp của ba điều kiện này sẽ tạo thành nhiều kiểu cơ chế lựa chọn đường chính và đường dự phòng khác nhau. Cơ chế lựa chọn thứ nhất thực hiện việc chọn đường ngắn nhất là đường chính và đường có độ trễ nhỏ nhất là đường dự phòng. Cơ chế thứ hai chọn đường có độ trễ ngắn nhất làm đường chính và đường khác biệt nhiều nhất là đường dự phòng. Kết quả mô phỏng của nghiên cứu này đã cho thấy rằng hiệu năng của mạng đã được tăng lên đối với thông số độ trễ định tuyến và lượng thông điệp điều khiển khi các nút di chuyển với tốc độ từ 10m/s tới 20m/s khi áp dụng định tuyến đa đường dự phòng so với định tuyến DSR khi áp dụng cơ chế thứ nhất. Giao thức định tuyến đa đường trên cơ sở định tuyến vùng Fresnel Định tuyến đa đường trên cơ sở định tuyến vùng Fresnel (FZR) được các tác giả Liang và Midkiff đề xuất trong [7]. Khái niệm vùng Fresnel là khái niệm xuất phát từ lý thuyết truyền sóng áp dụng vào kỹ thuật định tuyến trong mạng ad-hoc. FZR phân loại các nút trung gian theo khả năng và hiệu suất chuyển tiếp gói tin của chúng. Giao thức FZR là giao thức định tuyến kết hợp giữa kỹ thuật định tuyến “tìm đường trước” và kỹ thuật định tuyến “theo yêu cầu”. FZR có thể làm giảm Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 53 bớt tắc nghẽn tại các nút trung gian và đạt được thông lượng tốt hơn tại tầng Chuyển vận. Nó sử dụng độ đo số chặng trong quá trình xây dựng vùng. Xét một nút nguồn S và một nút đích D trong mạng. Khoảng cách ngắn nhất tính theo số chặng giữa S và D là L. Nếu có một con đường ngắn nhất từ S tới D qua một nút trung gian có L+n-1 chặng thì nút này thuộc vào vùng thứ n và con đường này được gọi là con đường thứ n. Trong FZR, mỗi một nút phải duy trì một bảng khoảng cách. Để xây dựng và duy trì bảng này, nút di động sử dụng các gói tin Hello. Khi một nút nhận được một gói tin Hello, nó sẽ cập nhật bảng khoảng cách của mình. Khi bảng khoảng cách được truyền qua mạng, mỗi nút sẽ cập nhật bảng khoảng cách của mình và xác định con đường thứ nhất. FZR xác định con đường thứ hai theo kiểu “tìm đường theo yêu cầu”. Khi có một nút nằm trong vùng thứ nhất khởi tạo tiến trình tìm đường bằng gói tin yêu cầu đường, gói tin này sẽ được quảng bá tới các nút láng giềng thuộc vùng thứ hai. Ta gọi nút thuộc vùng thứ hai nhận gói tin yêu cầu đường đầu tiên là nút láng giềng một chặng. Nút một chặng sẽ tiếp tục quảng bá gói tin này tới các nút láng giềng của nó. Khi một nút tiếp theo nằm trong vùng thứ hai nhận được gói tin yêu cầu đường từ nút một chặng, nó sẽ là nút hai chặng. Nút hai chặng này sẽ gửi gói tin trả lời đường cho nút nguồn qua nút láng giềng một chặng. Nút láng giềng một chặng sẽ ghi lại con đường chuyển tiếp qua nút 2 chặng vào bảng định tuyến của mình và chuyển tiếp gói tin trả lời đường tới nút nguồn. Khi đó nút nguồn sẽ ghi con đường này vào bảng định tuyến của mình. Với cơ chế này, một nút nguồn có thể tìm ra một hoặc nhiều đường thứ hai. Có thể hình thành nhiều vùng bằng cách sử dụng phương pháp này nhưng để hạn chế nhiễu, định tuyến FZR chỉ giới hạn sử dụng con đường thứ nhất và đường thứ hai. FZR chấp nhận cách tiếp cận đơn giản khi phân phối dữ liệu qua nhiều đường. Nếu tồn tại nhiều con đường khác nhau, FZR sẽ phân phối dữ liệu từng phần qua tất cả các con đường. Quá trình phân phối dữ liệu qua nhiều đường có thể điều chỉnh động tuỳ theo điều kiện về băng thông và tắc nghẽn của mạng. Giao thức định tuyến AODV đa đường với cơ chế chọn đường theo xác suất Giao thức định tuyến đa đường theo yêu cầu dạng véc tơ khoảng cách với cơ chế chọn đường theo xác suất (AODVM-PSP) do tác giả Jing đề xuất trong [6]. Giao thức này là giao thức mở rộng của giao thức AODVM [15]. Tiến trình tìm đường của AODVM-DSP tương tự như AODV [9]. Quá trình thiết lập nhiều đường tương tự như giao thức AODVM. Sự khác biệt chính giữa AODVM- DSP và AODVM là AODVM-DSP xem xét đến yếu tố độ trễ dọc theo con đường khi đưa ra một quyết định chọn đường. Khi một nút gửi một gói tin tới đích, gói tin này sẽ chứa các thông tin về thời gian bắt đầu được truyền đi. Một nút trung gian hoặc một nút nguồn có thể ước lượng độ trễ trên cơ sở thông tin này. Nút nguồn xác định con đường tốt nhất theo xác suất của con đường đó trên cơ sở độ trễ khi truyền theo đường này. Xác suất của một con đường thứ i giữa nút nguồn S và nút đích D ký hiệu là Pi(S, D) được tính bằng công thức: trong đó Ti(S, D) là thời gian trễ khi truyền từ nút S tới nút D theo con đường thứ i và k là số lượng các con đường đi từ nút S tới nút D. Khác với giao thức AODVM, giao thức AODVM-PSP không tìm kiếm các con đường khác biệt. Nó cũng không sử dụng các gói tin nhận biết sự tồn tại của các nút như AODVM. Vì vậy, tiến trình tìm đường của giao thức AODVM-PSP không diễn ra thường xuyên như trong giao thức AODVM và điều này làm giảm bớt lượng thông tin điều khiển truyền trong mạng. Giao thức định tuyến đa đường Split-n-Save Các tác giả Cha và Lee đã hiệu chỉnh giao thức AODVM thành giao thức split-n-save [4] nhằm đạt được hai mục tiêu chính: (1) để đảm bảo giao thức định tuyến đa đường hoạt động tốt qua thời gian hoạt động của các nút và (2) để cân bằng giữa định tuyến và chuyển tiếp dữ liệu trong mạng. Các tác giả này đã đặt tên cho hai mục tiêu trên là khả năng sống Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 54 của mạng và khả năng đáp ứng của nút. Khả năng sống của mạng được định nghĩa là số lượng nút đang hoạt động qua một khoảng thời gian cho trước. Khả năng đáp ứng của mạng được định nghĩa là tỷ lệ giữa số lượng gói tin do nút sinh ra trên số lượng gói tin do nút chuyển tiếp tới các nút khác. Các tác giả đã đề xuất một cơ chế phân kênh đơn giản dành cho việc chuyển đổi lưu lượng giữa các con đường. Theo cơ chế này, một nút nguồn sẽ chuyển đường truyền dữ liệu sau khi truyền k gói tin trên một con đường. Khi k=1, giao thức sẽ chuyển đường truyền dữ liệu sau mỗi gói tin được gửi. Khi k=0, nó sẽ sử dụng duy nhất một con đường cho đến khi đường này bị lỗi. Các kết quả mô phỏng trên cơ sở các giá trị k khác nhau đã chỉ ra rằng thời gian trễ cho từng gói tin cao hơn khi k=0 hoặc k=1 so với các trường hợp k lớn hơn 1. Đối với trường hợp k=0 hoặc k=1, giá trị thời gian trễ biến động tương đối rộng còn đối với các trường hợp k nhận giá trị khác, giá trị thời gian trễ biến động không nhiều. Từ các kết quả này, các tác giả đã kết luận rằng với trường hợp k=0 hoặc k=1, một số ít nút trong mạng phải đóng vai trò là nút trung tâm giữa các kết nối khác nhau do đó rất dễ xảy ra hiện tượng tắc nghẽn dữ liệu tại các nút này. Khi lựa chọn các giá trị k lớn hơn, xác xuất xảy ra hiện tượng tắc nghẽn này sẽ giảm đi. Giao thức định tuyến đa đường có độ ưu tiên Giao thức định tuyến đa đường có độ ưu tiên (PRIMAR) được đề xuất bởi Huang và Fang năm 2005 [5]. Trong giao thức này, nhiều con đường được lựa chọn giữa nút nguồn và nút đích phụ thuộc vào loại lưu lượng. Giao thức này giả định rằng nút nguồn nhận biết được độ quan trọng của một gói tin khi gửi nó tới nút đích. Nút nguồn sử dụng một giá trị để phân loại các gói tin dựa vào độ quan trọng của nó. Quá trình quyết định đường đi được tạo ra trên cơ sở sử dụng độ ưu tiên của giá trị này. Các gói tin có độ ưu tiên thấp hơn sẽ được truyền trên các con đường dài hơn so với các gói tin có độ ưu tiên cao. Độ ưu tiên được gán các giá trị từ 1 tới M với M là độ ưu tiên cao nhất. Gói tin có độ ưu tiên cao nhất sẽ được truyền trên con đường tối ưu trong số M con đường. Đường tối ưu được định nghĩa là đường có độ trễ nhỏ nhất. Mặc dù có M giá trị độ ưu tiên đã được thiết lập nhưng có thể có trường hợp số lượng các con đường đầu ra nhỏ hơn M. Trong trường hợp này độ ưu tiên cao nhất được thiết lập là m = min(M, K) với K là tổng số con đường giữa nút nguồn và nút đích đã tìm được. Sau khi nhận được một gói tin, một nút sẽ kiểm tra độ ưu tiên của gói tin và chuyển tiếp gói này tới chặng kế tiếp thích hợp. Độ trễ đầu-cuối luôn biến đổi trong mạng không dây vì vậy độ trễ trung bình được sử dụng để cập nhật bảng định tuyến. Các nút sẽ cập nhật độ trễ trung bình bằng cách sử dụng cơ chế báo nhận thuộc tầng MAC. Tiến trình duy trì đường của giao thức PRIMAR tương tự như giao thức DSR nhưng thủ tục duy trì đường của PRIMAR chỉ được kích hoạt khi có một con đường bị lỗi hoặc có một con đường không đáp ứng điều kiện về độ trễ của gói tin. Sự thay đổi này trong tiến trình duy trì đường cho phép giao thức PRIMAR đáp ứng được yêu cầu truyền dữ liệu có độ ưu tiên cao. Giao thức định tuyến theo góc địa lý Giao thức định tuyến theo góc địa lý (BGR) [11] được Popa và các cộng sự giới thiệu nhằm cải thiện thông số thời gian trễ của hiệu năng mạng bằng cách sử dụng thông tin về sự tắc nghẽn trong mạng. Ý tưởng chính của giao thức BGR là chèn vào mỗi gói tin một giá trị góc nghiêng bias. Giá trị này xác định quỹ đạo của con đường tiến về phía đích. Hai thuật toán điều khiển tắc nghẽnđược sử dụng trong giao thức BGR là thuật toán thuật toán tách gói trong mạng IPS và thuật toán tách gói đầu cuối EPS. Thuật toán IPS phân tách dòng lưu lượng truyền dữ liệu để tránh khỏi hiện tượng tắc nghẽn tức thời. Hiện tượng này xảy ra khi có quá nhiều kết nối cùng được thiết lập trên một đoạn mạng nào đó. Để tránh khỏi hiện tượng này, thuật toán IPS phân tách dòng lưu lượng dữ liệu ngay trước các điểm tắc nghẽn. Thuật toán này yêu cầu thông tin về tắc nghẽn phải được định kỳ trao đổi giữa các nút láng giềng. Nếu thuật toán IPS không đạt được hiệu quả về giảm tắc nghẽn, thuật Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 55 toán EPS sẽ được kích hoạt. Trong trường hợp của thuật toán EPS, nút nguồn sẽ chia lưu lượng dữ liệu theo nhiều con đường khác nhau và do đó giảm được tắc nghẽn. Các kết quả mô phỏng cho thấy rằng việc kết hợp giữa thuật toán IPS và thuật toán EPS cải thiện khá tốt thời gian phân phối gói tin giữa các nút và do đó làm cho thông lượng của mạng tăng lên. ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO THỨC ĐỊNH TUYẾN ĐA ĐƯỜNG GIẢM THỜI GIAN TRỄ Trên cơ sở mô phỏng các giao thức định tuyến đa đường và so sánh cơ chế hoạt động của các giao thức [12], bảng sau đây trong đưa ra các so sánh về hiệu năng của các giao thức định tuyến đa đường giảm thời gian trễ: Nhìn vào bảng trên có thể kết luận rằng không có giao thức nào là tối ưu đối với mọi tham số về hiệu năng ngoài tham số về thời gian trễ. Tuy nhiên với từng trường hợp cụ thể ta có thể lựa chọn được giao thức phù hợp nhất. Đối với các mạng có tần suất di chuyển của các nút mạng và tần suất thay đổi hình trạng mạng là lớn, nếu chấp nhận được mức độ tiêu tốn nhiều năng lượng nguồn của các nút mạng và lượng thông tin điều khiển nhiều thì giao thức PRIMAR là giao thức tốt nhất. Đối với các mạng cần dành nhiều băng thông cho dữ liệu và tần suất di chuyển của các nút không nhiều đồng thời không yêu cầu quá cao về độ tin cậy tại tầng mạng thì giao thức định tuyến đa đường dự phòng là giao thức tối ưu. Đối với các mạng sử dụng các ứng dụng cần thời gian hoạt động dài của các nút mạng trong khi các nút mạng di chuyển nhiều và chấp nhận được tỷ lệ cao giữa số lượng gói tin điều khiển/ số lượng gói tin dữ liệu thì giao thức định tuyến Split-N-Save lại là sự lựa chọn hàng đầu. MỘT SỐ VẤN ĐỀ CẦN CẢI TIẾN TRONG CÁC GIAO THỨC ĐỊNH TUYẾN ĐA ĐƯỜNG Mặc dù các giao thức định tuyến đa đường cải thiện được kỹ thuật phân luồng dữ liệu, độ tin cậy, độ trễ và khả năng sử dụng hiệu quả năng lượng nhưng chúng vẫn gặp phải các vấn đề kỹ thuật sau: Chọn đường dài hơn: Trong một giao thức định tuyến đa đường, thông thường các gói tin di chuyển qua số chặng nhiều hơn so với giao thức định tuyến chọn đường ngắn nhất. Do đó, thời gian trễ khi truyền các gói tin sẽ lớn hơn. Vẫn cần có các thử nghiệm về các kỹ thuật lựa chọn các con đường truyền dữ liệu trong các giao thức định tuyến đa đường đã đề cập để hạn chế việc các giao thức sử dụng các con đường quá dài. Gói tin điều khiển đặc biệt: Ngoài các gói tin điều khiển sử dụng trong cơ chế tìm đường và duy trì đường, một giao thức định tuyến đa đường còn sử dụng thêm các gói tin điều khiển khác. Các gói tin điều khiển này được nút di động sử dụng để tập hợp các thông tin về các nút láng giềng để tìm ra các con đường khác. Chúng có thể chiếm một phần băng thông quan trọng trong mạng đặc biệt là đối với các mạng lớn và do đó làm ảnh hưởng tới hiệu năng của mạng. Vì vậy cần có những kỹ thuật làm hạn chế số lượng và kích thước gói tin điều khiển. Bảng 1: So sánh các thông số về hiệu năng của các giao thức định tuyến đa đường giảm thời gian trễ Giao thức Thông tin điều khiển Độ tin cậy Độ hiệu quả sử dụng năng lượng Hỗ trợ tính di động Định tuyến đường dự phòng [8] Ít Trung bình Trung bình Thấp Định tuyến đa đường Fresnel [7] Nhiều Thấp Thấp Cao Định tuyến AODVM-PSP [6] Nhiều Thấp Thấp Thấp Định tuyến PRIMAR [5] Nhiều Cao Thấp Cao Định tuyến BGR [11] Nhiều Thấp Trung bình Thấp Định tuyến Spit-n-Save [4] Nhiều Trung bình Cao Thấp Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 56 Cơn bão gói tin tìm đường: Giao thức định tuyến đa đường có thể sinh ra một số lượng lớn các gói tin tìm đường trong mạng MANET trong tiến trình tìm đường. Cần có những kỹ thuật và thuật toán hạn chế chuyển tiếp các gói tin tìm đường không cần thiết nhằm làm giảm hiệu ứng của cơn bão gói tin tìm đường. Tìm đường không hiệu quả: Tiến trình tìm đường của một giao thức định tuyến đa đường có thể không hiệu quả bằng các giao thức DSR và AODV. Trong tiến trình tìm đường của DSR và AODV, một nút trung gian được cho phép gửi gói tin trả lời từ bộ nhớ đường của chúng nếu chúng tìm thấy một con đường phù hợp trong bộ nhớ đường của mình. Điều này làm giảm thời gian tìm đường từ nút nguồn bởi vì nút nguồn có thể không phải đợi cho đến khi gói tin tìm đường đến được nút đích. Tuy nhiên, trong các giao thức định tuyến đa đường sử dụng các con đường khác biệt theo nút hoặc khác biệt theo liên kết, không cho phép các nút trung gian gửi gói tin trả lời từ bộ nhớ đường của mình. Do đó, nút nguồn phải đợi cho đến khi gói tin tìm đường tới được nút đích. Vì vậy, thông thường thời gian tìm đường của các giao thức định tuyến đa đường thường dài hơn so với giao thức DSR hoặc AODV. Do đó, cần có những cải tiến tiếp theo làm giảm thời gian tìm đường trong giao thức định tuyến đường dự phòng [8] khi sử dụng đường khác biệt. Xử lý các gói tin đúp: Để đảm bảo khả năng truyền dữ liệu một cách tin cậy, các giao thức định tuyến đa đường của Tsirigos [13] và Wang [14] đề xuất sử dụng các đường đi khác nhau để gửi các bản sao của cùng một gói tin. Các gói tin nhân bản chính là các gói tin dư thừa và đương nhiên là chúng sẽ chiếm giữ băng thông của hệ thống mạng. Thêm vào đó, các giao thức này cũng yêu cầu kỹ thuật nhân bản gói tin tại nút nguồn và lọc gói tin nhân bản tại nút đích. Các kỹ thuật xử lý gói tin đúp này vẫn cần được cải tiến để đạt được hiệu quả cao hơn. KẾT LUẬN Trong những năm gần đây đã có rất nhiều nghiên cứu tập trung vào mạng không dây kiểu không cấu trúc. Một trong những hướng nghiên cứu quan trọng là thiết kế các giao thức định tuyến đảm bảo thời gian truyền dữ liệu nhanh, độ tin cậy cao và có cơ chế đảm bảo chất lượng dịch vụ. Nhằm cải tiến các nhược điểm của các giao thức định tuyến đơn đường truyền thống trong mạng không dây kiểu không cấu trúc, đã có một số giao thức định tuyến đa đường tiếp cận theo mục tiêu giảm thời gian trễ khi truyền dữ liệu được đề xuất. Với những cải tiến đã đưa ra của các giao thức này, hiệu năng của chúng đã được cải thiện so với các giao thức đơn đường truyền thống nhưng rất khó để có thể lựa chọn một giao thức định tuyến đa đường giảm thời gian trễ là giao thức tối ưu đối với mọi tham số về hiệu năng. Việc lựa chọn một giao thức định tuyến đa đường giảm thời gian trễ còn phải phụ thuộc vào các tham số cụ thể của mô hình mạng cụ thể. Ngoài ra, các giao thức định tuyến này vẫn cần phải cải tiến về cơ chế tìm đường, cơ chế lựa chọn đường và cơ chế cân bằng tải để có thể đạt được hiệu năng tốt hơn. TÀI LIỆU THAM KHẢO [1]. Anurag K, Manjunath D, Kuri J. Communication networking: an analytical approach, Los Altos, CA: Morgan Kaufmann Publishers; 2004. P.715-720 [2]. Bertsekas D, Gallager R. Data networks, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall; 1992 p.162-170 [3]. Broch J, Johnson DB, Maltz DA. The dynamic source routing for mobile ad hoc networks. IETF Internet-draft, draft-ietf-manet- dsr-00.txt; 1998. [4]. Cha M, Lee DK. Split-n-save multiplexing in wireless ad hoc routing. In: Proceedings of the 24th annual joint conference of the IEEE computer and communications societies (INFOCOM), Miami, March 2005. [5]. Huang X, Fang Y. End-to-end delay differentiation by prioritized multipath routing in wireless sensor networks. In: Military communications conference, MILCOM 2005, vol. 2, p. 1277-1283. [6]. Jing F, Bhuvaneswaran RS, Katayama Y, Takahashi N. A multipath on-demand routing with path selection probabilities for mobile ad hoc networks. In: Proceedings of the international Đỗ Đình Cường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 51 - 57 57 conference on wireless communications, networking and mobile computing, 2005, vol. 2, p. 1145-1151. [7]. Liang Y, Midkiff SF. Multipath Fresnel zone routing for wireless ad hoc networks. In: Proceedings of the IEEE wireless communications and networking conference, vol. 4, March 2005, p. 1958–1963. [8]. Lim H, Xu K, Gerla M. TCP performance over multipath routing in mobile ad hoc networks. In: IEEE international conference on communication (ICC), vol. 2, 2003, p. 1064–1070. [9]. Perkins CE. Ad hoc on-demand distance vector (AODV) routing. IETF Internet-draft, draft- ietf-manet-aodv-00.txt; 1997. [10]. Pham PP, Perrau S. Performance analysis of reactive shortest path and multipath routing mechanism with load balance. In: Proceedings of the IEEE INFOCOM, San Francisco, California, USA, April 2003, p. 251-259. [11]. Popa L, Raiciu C, Stoica I, Rosenblum DS. Reducing congestion effects in wireless networks by multipath routing. In: Proceeding of the 14th IEEE international conference on network protocols, Santa Barbara, California, USA, November 2006, p. 96-104. [12]. Tarique M, Kelnal E. Tepe, Sasan Adibi, Shervin Erfani. Survey of multipath routing protocols for mobile ad hoc networks. In: Journal of Network and Computer Applications 32, 2009, p. 1125-1143. [13]. Tsirigos A, Haas ZJ, Tabrizi SS. Multipath routing in mobile ad hoc networks or how to route in the presence of frequent topology changes In: Proceedings of themilitary communications conference, vol. 2, Vienna, Virginia, October 2001, p. 878–883. [14]. Wang L, Jang S, Lee T-Y. Redundant source routing for real-time services in ad hoc networks. In: Proceedings of IEEE international conference on mobile ad hoc and sensor systems conference, Washington, DC, November, 2005. [15]. Ye Z, Krishnamurthy SV, Tripathi SK. A framework for reliable routing in mobile ad hoc networks. In: Proceedings of the 22nd annual joint conference of the IEEE computer and communications societies (INFOCOM), vol. 1, 2003, p. 270-280. SUMMARY EVALUATING DELAY-AWARE MULTIPATH ROUTING PROTOCOLS IN MANET Do Dinh Cuong*, Nguyen Anh Chuyen College of Information Technology and Communication - TNU Recently, multipath routing has become a new approach for routing in MANET. In this paper, we introduces a fundamental overview about operation mechanism of several new delay-aware multipath routing protocols. Later, we do more action in analyzing, comparing, and evaluating these protocols based on target and performance. Furthermore, this paper also points out future works that these protocols need to do. Keywords: Mobile Adhoc Network, Multipath Routing, Delay, Route Finding, Route Selecting Ngày nhận bài:30/1/2013, ngày phản biện: 19/2/2013, ngày duyệt đăng:26/3/2013 * Tel: 0982 990908, Email: ddcuong@ictu.edu.vn