Luận văn 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

T Ổ NG QUAN M ẠNG MANET VÀ ĐỊ NH TUY ẾN ĐA ĐƯỜ NG TRONG M Ạ NG MANET

T ổ ng quan v ề m ạ ng MANET

Mạng MANET (Mobile Ad hoc Network) là một loại mạng di động không dây hoạt động độc lập mà không cần hạ tầng mạng cố định, với cấu trúc mạng được hình thành từ chính các nút mạng Chế độ "Ad hoc" theo chuẩn IEEE 802.11 cho phép thiết lập mạng đơn chặng, nhưng các mạng di động không dây không cấu trúc đã mở rộng khái niệm này thành mạng đa chặng, cho phép một nút mạng có khả năng định tuyến và chuyển tiếp gói tin từ nút này sang nút khác Điều này có nghĩa là đường truyền gói tin từ nút nguồn đến nút đích có thể bao gồm nhiều nút trung gian, mà chúng sẽ đọc thông tin trong phần header của gói tin và chuyển tiếp đến điểm tiếp theo trong đường đi đã được thiết lập.

Mạng MANET là tập hợp các nút không dây di động có khả năng trao đổi dữ liệu linh hoạt mà không cần trạm cơ sở cố định hay mạng có dây Mỗi nút di động có phạm vi truyền hạn chế, vì vậy chúng cần sự hỗ trợ từ các nút lân cận để chuyển tiếp gói dữ liệu Khi gói tin từ nút nguồn cần gửi tới nút đích nằm ngoài phạm vi truyền, các nút trung gian sẽ giúp chuyển tiếp gói tin, và để thực hiện điều này, các nút mạng cần áp dụng giao thức định tuyến phù hợp.

Hình 1.1 Minh họa của mạng MANET

Mạng MANET là một hệ thống gồm các nút kết nối với nhau trong thời gian ngắn để trao đổi thông tin, trong khi vẫn cho phép các nút di chuyển Điều này đòi hỏi mạng phải có khả năng truyền dữ liệu linh hoạt, bất chấp sự thay đổi liên tục về hình trạng Các nút trong mạng tự tổ chức để thiết lập các đường truyền mà không cần sự hỗ trợ bên ngoài Trong mô hình này, mỗi nút có thể hoạt động như một nút đầu cuối để chạy ứng dụng của người dùng hoặc như một bộ định tuyến để chuyển tiếp gói tin cho các nút khác.

Mạng MANET là một loại mạng không dây hoạt động độc lập mà không cần hạ tầng mạng cố định, sử dụng phương thức truyền thông đa chặng giữa các thiết bị di động Các thiết bị này không chỉ là đầu cuối mà còn đóng vai trò là bộ định tuyến, tạo nên những đặc điểm nổi bật cho mạng MANET.

Cấu trúc của mạng MANET thường xuyên thay đổi một cách ngẫu nhiên do tính chất di chuyển ngẫu nhiên của các nút mạng Trong quá trình này, mạng có thể thêm hoặc mất đi các kết nối hai chiều và một chiều vào những thời điểm không xác định trước.

Chất lượng liên kết không dây thường bị hạn chế do băng thông thấp hơn so với các liên kết có dây Các yếu tố như cơ chế đa truy cập, suy giảm tín hiệu và nhiễu cũng góp phần làm giảm băng thông thực tế của các liên kết không dây, khiến nó thấp hơn nhiều so với tốc độ truyền tối đa lý thuyết của môi trường truyền không dây.

Các nút mạng di động, bao gồm cảm biến, điện thoại thông minh và máy tính xách tay, thường có tài nguyên hạn chế hơn so với các máy tính trong mạng có dây và không dây truyền thống Điều này thể hiện rõ ở tốc độ xử lý, dung lượng bộ nhớ và năng lượng của pin, ảnh hưởng đến khả năng hoạt động của các nút này trong mạng.

Mạng không dây di động (MANET) có độ bảo mật thấp hơn so với mạng có dây do dễ bị tác động từ các nguồn gây nguy hại về an ninh Các kỹ thuật tấn công như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ dàng triển khai hơn trong mạng MANET, tạo ra những rủi ro lớn về an ninh vật lý.

Các đặc điểm của mạng MANET ảnh hưởng lớn đến hiệu năng hoạt động của nó Để triển khai mạng MANET trong thực tế, các thiết kế cần giải quyết những thách thức 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 Ngoài ra, cần đảm bảo chất lượng dịch vụ (QoS) cho các ứng dụng, 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 và toàn mạng, cũng như đảm bảo an ninh mạng Cuối cù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 cũng là những yếu tố quan trọng cần được chú ý.

Mạng MANET hiện nay có nhiều ứng dụng quan trọng trong đời sống, kinh tế và xã hội, đặc biệt trong các tình huống cần triển khai mạng nhanh chóng và linh động Mạng này được sử dụng rộng rãi trong thương mại, quân sự, khẩn cấp, gia đình, văn phòng, giáo dục, giao thông và cảm biến Trong thương mại, người dùng có thể chia sẻ dữ liệu giữa các thiết bị di động trong các cuộc họp mà không cần hạ tầng mạng cố định Các cá nhân có thể kết nối máy tính để tạo thành mạng tạm thời phục vụ truyền thông mà không cần bộ thu phát tập trung Ứng dụng của mạng MANET trong quân đội cho phép các lính và phương tiện quân sự như xe tăng, máy bay, tàu chiến kết nối và trao đổi thông tin tạm thời, tạo ra một mạng linh hoạt trong môi trường không có hạ tầng mạng cố định.

Trong các khu vực bị thiên tai, hạ tầng truyền thông thường bị phá hủy hoàn toàn Để khắc phục tình trạng này, các phương tiện như xe cảnh sát, cứu hỏa và cứu thương có thể được trang bị thiết bị truyền nhận không dây, biến chúng thành các thiết bị đầu cuối di động trong mạng MANET Mỗi nhân viên cứu hộ cũng có thể sử dụng thiết bị đầu cuối di động, tạo thành một mạng MANET tạm thời để trao đổi thông tin Cấu hình mạng này có thể thay đổi theo thời gian và các thiết bị đầu cuối không chỉ gửi và nhận thông tin mà còn có khả năng chuyển tiếp thông tin như các bộ định tuyến.

Các thiết bị thông minh trong gia đình, điện thoại di động và máy tính của người dùng tại văn phòng và trường học có thể hoạt động như các nút mạng trong một mạng MANET tạm thời Mạng này không cần hạ tầng cố định, phục vụ cho các ứng dụng chia sẻ thông tin, truyền dữ liệu đa phương tiện, quản lý ngôi nhà thông minh và lớp học thông minh.

Trong quản lý giao thông, mỗi phương tiện được xem như một nút mạng di động trong mạng MANET tạm thời, giúp trao đổi thông tin về tình trạng giao thông Mạng này hỗ trợ tìm đường tránh tắc nghẽn và theo dõi các thiết bị tham gia giao thông, góp phần nâng cao hiệu quả quản lý giao thông.

Cảm biến là thiết bị nhỏ, giá thành thấp và 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ạng MANET có thể bao gồm các nút cảm biến hợp tác để thực hiện nhiệm vụ như giám sát môi trường (không khí, đất, nước), theo dõi hành vi và dân số động thực vật, dò tìm động chấn, theo dõi tài nguyên và thực hiện trinh thám trong quân đội.

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 phương pháp để phân loại các chiến lược định tuyến trong mạng MANET dựa trên các tiêu chí khác nhau Những chiến lược này được trình bày 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 Loại

Định tuyến có thể được chia thành hai loại: định tuyến tìm đường trước và định tuyến theo yêu cầu Trong khi định tuyến tìm đường trước sử dụng thông tin đã được lưu trữ để xác định lộ trình, thì định tuyến theo yêu cầu lại cập nhật thông tin theo thời gian thực Về phương pháp truyền thông tin, có hai cách chính: cập nhật định kỳ và cập nhật theo sự kiện, giúp đảm bảo rằng dữ liệu định tuyến luôn chính xác và kịp thời.

Sốlượng vùng định tuyến Định tuyến phẳng và định tuyến phân cấp Thông tin định tuyến trong header của gói Định tuyến nguồn và định tuyến từng chặng

Vị trí tính toán đường Định tuyến tập trung và định tuyến phân tán

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, hay còn gọi là “định tuyến kích hoạt trước” và “định tuyến điều khiển dạng bảng”, cho phép các con đường tới mọi đích được xác định trước khi có nhu cầu truyền dữ liệu, giúp giảm thiểu độ trễ khi yêu cầu truyền dữ liệu xuất hiện Tuy nhiên, nhược điểm của phương pháp này là có thể tính toán những con đường không bao giờ được sử dụng và việc cập nhật bảng định tuyến định kỳ có thể chiếm băng thông mạng, đặc biệt khi trạng thái các liên kết thay đổi nhanh chóng Một số giao thức tiêu biểu trong nhóm này bao gồm DSDV và WRP Ngược lại, các giao thức định tuyến theo yêu cầu chỉ khởi tạo quá trình tìm đường khi có nhu cầu sử dụng, giúp tiết kiệm băng thông, nhưng có thể gây ra độ trễ đáng kể trong quá trình tìm kiếm Một số giao thức tiêu biểu trong 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

Trong các giao thức định tuyến dựa trên trạng thái liên kết, việc cập nhật thông tin về trạng thái liên kết và hình trạng mạng là rất quan trọng Thông tin định tuyến được quảng bá tới các nút mạng và có thể được phân loại thành hai nhóm: định tuyến cập nhật định kỳ và định tuyến cập nhật theo sự kiện Định tuyến theo chu kỳ giúp duy trì sự ổn định mạng và cho phép các nút học thông tin về trạng thái toàn mạng, nhưng nếu chu kỳ quá dài, thông tin có thể trở nên lỗi thời Ngược lại, chu kỳ quá ngắn sẽ tạo ra quá nhiều gói tin, gây lãng phí tài nguyên mạng Đối với định tuyến theo sự kiện, chỉ những nút chịu tác động trực tiếp mới quảng bá thông tin, giúp cập nhật nhanh chóng tình trạng mạng Tuy nhiên, khi topo mạng thay đổi nhanh chóng, việc này có thể dẫn đến nhiều gói tin quảng bá, gây lãng phí băng thông và ảnh hưởng đến 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, tất cả các nút trong mạng đều có cùng cấp độ và chức năng, giúp cho chiến lược này trở nên đơn giản và hiệu quả cho các mạng nhỏ Các giao thức như AODV, DSDV và DSR là những ví dụ tiêu biểu cho định tuyến phẳng Tuy nhiên, trong các mạng lớn, việc xử lý và truyền tải các gói tin quảng bá thông tin định tuyến có thể dẫn đến lãng phí tài nguyên mạng Do đó, chiến lược định tuyến phân cấp đã được đề xuất để khắc phục 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 thành các vùng động, có thể chia thành các vùng con theo kiểu cây phân cấp, nhằm duy trì tính ổn định của mạng Sự thay đổi trạng thái của một nút chỉ ảnh hưởng trong phạm vi vùng quản lý của nó, trong khi thông tin điều khiển cấp cao được truyền giữa các vùng để giảm tải định tuyến Mỗi nút mạng nắm vững thông tin về các nút khác trong cùng vùng thông qua kỹ thuật định tuyến tìm đường trước Khi yêu cầu truyền dữ liệu giữa hai vùng khác nhau, kỹ thuật định tuyến liên vùng theo yêu cầu sẽ được áp dụng, thường hoạt động theo cơ chế định tuyến theo yêu cầu hoặc kết hợp cả hai phương pháp Các giao thức tiêu biểu cho chiến lược này bao gồm HSR và CGSR.

Hình 1.2 và Hình 1.3 mô tả các con đường được tạo ra bởi các giao thức định tuyến, trong đó bao gồm 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

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 giữ thông tin đầy đủ về cấu trúc mạng, cho phép thực hiện các thuật toán tìm đường khi cần Các giao thức định tuyến theo chiến lược này được gọi là giao thức định tuyến kiểu trạng thái đường liên kết, trong đó OLSR là một ví dụ 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, các nút mạng chỉ lưu trữ thông tin cục bộ về cấu trúc mạng Khi cần tìm đường, nhiều nút sẽ cùng tham gia vào quá trình này Chiến lược định tuyến này được gọi là định tuyến kiểu véc tơ khoảng cách, với AODV và DSDV là hai giao thức tiêu biểu sử dụng phương pháp này.

1.2.6 Đị nh tuy ế n ngu ồn và đị nh tuy ế n t ừ ng ch ặ ng

Có một số giao thức định tuyến sử dụng thông tin về toàn bộ con đường trong header của gói tin, cho phép các nút trung gian chuyển tiếp gói tin dựa trên thông tin đó, được gọi là định tuyến nguồn Ưu điểm của chiến lược này là các nút không cần duy trì thông tin định tuyến cập nhật, vì thông tin cần thiết đã có trong gói tin Tuy nhiên, nhược điểm là kích thước gói tin tăng lên, đặc biệt trong các mạng lớn và đường dài, dẫn đến lãng phí băng thông Giao thức DSR là một ví dụ tiêu biểu cho định tuyến nguồn.

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 đến nút đích được phân chia thành các “chặng kế tiếp” của các nút trên đường đi Khi một nút nhận gói tin cần gửi đến đích, nó sẽ chuyển tiếp gói tin tới chặng kế tiếp tương ứng Do mỗi nút mạng không có thông tin đầy đủ về tất cả các liên kết trong mạng, thuật toán định tuyến của các giao thức phải đảm bảo không tạo ra định tuyến lặp Giao thức AODV là một ví dụ tiêu biểu sử dụng chiến lược này, với hình 1.5 minh họa kỹ thuật chuyển tiếp gói tin của giao thức.

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 con đường tới cùng một đích trong cùng một tiến trình tìm đường Tại mỗi nút mạng, các gói tin dữ liệu sẽ được chuyển tiếp theo con đường thích hợp có trong bảng định tuyến Khi một liên kết trên con đường đó bị lỗi, nút mạng này phải khởi tạo lại tiến trình tìm đường Để tiết kiệm tài nguyên hệ thống mạng trong các tiến trình tìm đường, các giao thức định tuyến đa đường cho phép tìm và cài đặt nhiều hơn một con đường không giao nhau tới cùng một đích vào bảng định tuyến của chúng Tại một nút, khi có yêu cầu chuyển tiếp dữ liệu tới nút đích, con đường tốt nhất sẽ được sử dụng và những con đường còn lại sẽ đóng vai trò là đường dự phòng Khi đường chính bị lỗi, các đường dự phòng sẽ được sử dụng để chuyển tiếp các gói tin dữ liệu nếu chúng vẫn trong trạng thái còn hoạt động được Thêm vào đó, nếu cơ chế cân bằng tải được sử dụng, có thể phân lưu lượng dữ liệu cần truyền thành nhiều luồng được truyền song song trên các con đường tới cùng một đích.

V ấn đề cân b ằ ng t ả i trong đị nh tuy ến đa đườ ng

Định tuyến trong mạng ad hoc di động (MANET) đã thu hút nhiều nghiên cứu trong thời gian gần đây Giao thức Định tuyến theo yêu cầu dạng véc tơ khoảng cách (AODV) là một trong những giao thức phổ biến và được áp dụng rộng rãi trong mạng MANET Nhiều nhà nghiên cứu cũng đã xem xét khả năng định tuyến nhận biết tắc nghẽn và thích ứng.

Gần đây, một giao thức mới đã được đề xuất nhằm ước tính thời gian định tuyến thay vì số chặng như trong AODV, bằng cách khám phá các đường khác nhau và chọn đường có thời gian định tuyến ngắn nhất Giao thức này xem xét độ trễ của liên kết dựa trên hiệu suất kênh truyền và độ trễ hàng đợi do tắc nghẽn tại các nút trung gian Cần lưu ý rằng thời gian định tuyến có thể tăng lên khi di chuyển trên một con đường.

Hình 1.6 Nhiều đường đi được hình thành giữa một cặp nút nguồn-đích

Trong MANET, một lớp giao thức định tuyến tập trung vào việc tìm kiếm nhiều đường đi giữa một cặp nút nguồn - đích và phân phối tất cả các gói dữ liệu qua các đường này Phương pháp định tuyến đa đường không chỉ giúp giảm thời gian định tuyến mà còn tăng cường độ tin cậy truyền thông Độ tin cậy của một con đường được xác định bởi xác suất nhận chính xác thông điệp, với hai con đường không giao nhau có độ tin cậy tương ứng là r1 và r2 Độ tin cậy truyền thông kết hợp qua hai đường này được tính bằng công thức 1 - (1−r1)(1−r2) = r1 + r2 - r1r2, và luôn lớn hơn r1 và r2 Ví dụ, nếu r1 = 0,999 và r2 = 0,9999, độ tin cậy kết hợp sẽ đạt 0,9999999.

Giao thức cân bằng tải đa đường Fibonacci (FMLB) là một phương pháp định tuyến dữ liệu hiệu quả, phân phối tổng tải dữ liệu trên nhiều đường khác nhau dựa trên chuỗi Fibonacci Trong một tình huống cụ thể với nút nguồn S và nút đích D, có ba đường đi khả thi: P1, P2 và P3, với thời gian định tuyến lần lượt là T1, T2 và T3, trong đó T1 > T2 > T3 Theo cơ chế của FMLB, ba giá trị liên tiếp F1, F2 và F3 trong chuỗi Fibonacci được sử dụng để phân bổ 4 gói dữ liệu, trong đó 1 gói (F1) được gửi qua đường có thời gian định tuyến lớn nhất (T1), 1 gói (F2) qua đường có thời gian lớn thứ hai (T2), và 2 gói (F3) qua đường có thời gian định tuyến nhỏ nhất (T3).

Tổng thời gian tối đa đểđịnh tuyến cho cả 4 gói này là max(T 1 , T 2 , 2T 3 ).

M ộ t s ố k ỹ thu ật đị nh tuy ến đa đườ ng và cân b ằ ng t ả i

Vấn đề định tuyến đa đường trong mạng MANET đã thu hút sự quan tâm nghiên cứu đáng kể trong thời gian qua Bên cạnh những nghiên cứu đã được đề cập trước đó, còn nhiều kết quả nghiên cứu quan trọng khác đã được công bố Dưới đây là tóm tắt một số kết quả nghiên cứu nổi bật trong lĩnh vực này.

Ganjali và Keshavanian đã phát triển một mô hình đánh giá cân bằng tải trong định tuyến đa đường, trong đó K đường đi ngắn nhất được xác định trước và dữ liệu được phân phối đồng đều giữa các đường này.

Pearlman và các cộng sự đã chứng minh rằng đường đôi có tác động tích cực đến hiệu suất thời gian trễ của giao thức định tuyến APR trong các mạng ad-hoc Đặc biệt, trong nhiều môi trường đa kênh truyền, APR có khả năng giảm 20% độ trễ đầu cuối cho các luồng dữ liệu lớn.

Wang và các cộng sự đã phát triển giao thức định tuyến đa đường MSR cho mạng ad hoc, mở rộng từ giao thức DSR Họ sử dụng phép đo RTT để thiết lập sơ đồ phân phối tải dữ liệu qua nhiều đường, giúp giảm tắc nghẽn mạng và nâng cao khả năng chịu lỗi Nghiên cứu của họ chứng minh rằng MSR mang lại hiệu quả tốt hơn trong việc quản lý lưu lượng mạng.

Tác giả Parissidis và các cộng sự đã công bố kết quả nghiên cứu mô phỏng liên quan đến ba giao thức định tuyến đa đường SMR.

Nghiên cứu mô phỏng cho thấy giao thức AOMDV đạt hiệu suất tốt nhất trong mạng có mức độ di động cao, trong khi AODV_Multipath hoạt động hiệu quả hơn trong mạng có tính di động thấp và mật độ nút cao Giao thức SMR phát huy tốt nhất trong các mạng có mật độ nút thấp, nhưng hiệu suất của tất cả các giao thức đều suy giảm khi mật độ nút tăng Pham và Perreau đã phân tích chi phí và hiệu năng của các giao thức định tuyến đơn đường so với đa đường trong mạng ad hoc, cho thấy giao thức đa đường yêu cầu chi phí cao hơn nhưng cải thiện tắc nghẽn và khả năng truyền tải nếu độ dài đường đi nằm trong giới hạn nhất định Nasipuri và cộng sự đã cải tiến giao thức DSR, chứng minh rằng sử dụng định tuyến đa đường thông minh có thể giảm tần suất cơn bão truy vấn.

Nghiên cứu đã phát triển một khung mô hình phân tích nhằm xác định tần suất tương đối của các cơn bão truy vấn dựa trên các kỹ thuật khác nhau Mặc dù lý thuyết cho thấy định tuyến đa đường vượt trội hơn so với định tuyến đơn đường, nhưng hiệu suất thực tế không khác biệt nhiều khi số lượng đường ít và các con đường dài Hơn nữa, nghiên cứu chỉ ra rằng việc trang bị cho tất cả các nút trung gian trên đường chính các đường thay thế mang lại hiệu suất tốt hơn đáng kể so với chỉ trang bị cho nút nguồn.

T ổ ng k ết Chương 1

Mạng MANET có những đặc điểm nổi bật so với mạng không dây truyền thống, bao gồm cấu trúc động, chất lượng liên kết hạn chế và nguồn năng lượng pin của các nút mạng Mặc dù độ bảo mật vật lý không cao, mạng MANET đã được ứng dụng rộng rãi trong các lĩnh vực đời sống, kinh tế và xã hội.

Mạng MANET, với những đặc điểm khác biệt so với mạng truyền thống, đặt ra nhiều thách thức cho các nhà nghiên cứu và triển khai công nghệ Để giải quyết những vấn đề này, giao thức định tuyến trong mạng MANET cần tối ưu hóa tải điều khiển và tải xử lý, hỗ trợ định tuyến đa chặng, thích ứng với sự thay đổi của topo mạng và ngăn chặn tình trạng định tuyến lặp.

Các giao thức định tuyến sử dụng nhiều chiến lược khác nhau, được phân loại theo các tiêu chí như: định tuyến tìm đường trước so với theo yêu cầu, cập nhật định kỳ so với theo sự kiện, định tuyến phẳng và phân cấp, định tuyến nguồn và từng chặng, cũng như định tuyến tập trung và phân tán, và cuối cùng là định tuyến đơn đường so với đa đường.

ĐỊ NH TUY Ế N HI Ệ U QU Ả TRÊN CƠ SỞ ĐỊ NH TUY ẾN ĐA ĐƯỜ NG VÀ CÂN B Ằ NG T Ả I

Ý tưởng thiết kế của giao thức LCMR

Giao thức định tuyến LCMR, được đề xuất trong [2], là một trong những giao thức hiệu quả cho định tuyến đa đường và cân bằng tải, đặc biệt trong các mạng MANET Giao thức này hoạt động bằng cách ước lượng thời gian định tuyến của từng con đường giữa cặp nút nguồn-đích, từ đó phân phối các gói dữ liệu sao cho số lượng gói gửi qua mỗi con đường tỷ lệ nghịch với thời gian định tuyến của con đường đó Chiến lược này giúp duy trì tải dữ liệu được cân bằng giữa các con đường, rút ngắn thời gian định tuyến tổng thể Bằng cách xác định bội số chung nhỏ nhất (L) của thời gian định tuyến, số lượng gói dữ liệu được gửi qua mỗi con đường sẽ được tính toán, đảm bảo rằng tất cả các gói dữ liệu được gửi qua nhiều con đường với thời gian định tuyến gần như bằng nhau.

Giữa một nút nguồn và một nút đích, có ba con đường P1, P2 và P3 với thời gian định tuyến lần lượt là 40, 30 và 20 đơn vị thời gian Bội số chung nhỏ nhất của 40, 30 và 20 là L0 Khi chia 120 cho 40, 30 và 20, ta nhận được các giá trị tương ứng là 3, 4 và 6 Như vậy, với mỗi bộ 3 + 4 + 6 = 13 gói dữ liệu, sẽ có 3 gói được gửi qua đường P1, 4 gói qua đường P2 và 6 gói qua đường P3, đảm bảo thời gian định tuyến qua mỗi con đường.

Bài toán này tương tự như bài toán lập lịch cho N tác vụ độc lập với độ phức tạp NP Nghiên cứu đã chỉ ra rằng giao thức định tuyến đa đường LCMR hoạt động hiệu quả hơn so với giao thức FMLB, nhờ vào việc LCMR xem xét thời gian định tuyến thực qua các đường khác nhau, điều mà FMLB không làm Thời gian định tuyến thực có thể khác biệt đáng kể so với tỷ lệ các số Fibonacci tương ứng Bên cạnh đó, giao thức LCMR cũng vượt trội hơn giao thức MAODV, khi mà LCMR gửi nhiều gói dữ liệu hơn qua các đường có thời gian định tuyến khác nhau, thay vì phân phối đều như MAODV.

Cơ chế ho ạt độ ng c ủ a giao th ứ c LCMR

2.2.1 Mô t ả c ơ chế ho ạt độ ng

Giao thức định tuyến đa đường có cân bằng tải LCMR khám phá các đường từ nút nguồn đến nút đích dựa trên thời gian định tuyến Quá trình này tương tự như AODV nhưng thay thế số bước chặng bằng thời gian định tuyến và cho phép khám phá nhiều đường Trong tình huống động, mặc dù cấu trúc mạng và lưu lượng có thể thay đổi, quá trình khám phá được giả định hoàn thành nhanh chóng Nút nguồn phát đi thông điệp RREQ với các thông tin như ID nguồn, ID đích, và danh sách nút trung gian Khi nút đích nhận RREQ, nó sẽ gửi lại thông điệp RREP cho nút nguồn Sau khi nhận RREP, nút nguồn xác định được đường đi và thời gian di chuyển của gói tin Để giới hạn số đường có thể có, nút nguồn chỉ chờ trong khoảng thời gian tối đa T max từ khi gửi RREQ để nhận các RREP tương ứng.

Giả sử, có k con đường là P P 1 , , , 2 P k được phát hiện với thời gian truyền ước tính tương ứng là T T 1, , ,2 T k sao cho T 1   T 2 T k Đặt

Với n gói dữ liệu liên tiếp, kế hoạch truyền các gói tin n i qua các đường P i được đề xuất như sau: các gói dữ liệu được gửi theo các đường P 1, P 2, , P k theo tỷ lệ n 1: n 2: : n k Tổng thời gian truyền n gói dữ liệu qua k đường này được xác định là max(n T i).

Nếu tổng số gói dữ liệu được gửi là N = pn + r, với 0 ≤ r < n và p ≥ 0, thì các gói đầu tiên pn sẽ được gửi qua các đường P1, P2, , Pk theo tỷ lệ n1 : n2 : : nk Số gói còn lại r sẽ được gửi theo cách khác.

 gói theo đườ ng P k Còn lại

Để triển khai giao thức LCMR, gói tin sẽ chỉ được gửi theo đường Pk, và ba thuật toán được đề xuất bao gồm: Thuật toán tại nút nguồn (Thuật toán 1), Thuật toán tại nút trung gian (Thuật toán 2) và Thuật toán tại nút đích (Thuật toán 3).

Trong Thuật toán 1 ở trên, nút nguồn sẽ sử dụng một bộđếm thời gian T để kiểm soát thời gian tìm đường không vượt quá mức Tmaxcho trước, khi một

Thu ậ t toán 1 : Thu ậ t toán t ạ i nút ngu ồ n

Output: RREQ, các gói dữ liệu

1 if SA = ID nút hi ệ n t ạ i then

2 Kh ở i t ạo đồ ng h ồ th ờ i gian th ự c T = 0;

3 Qu ả ng bá gói RREQ ch ứ a thông tin nút SA và DA;

4 while ( T < T max ) do // T max is the time-out period

5 if nh ận đượ c gói RREP then

6 Thu nhận các gói RREP và tạo danh sách đường có thông tin P i và T i ;

8 if danh sách đường đã đượ c t ạ o then

11 while t ấ t c ả các gói d ữ li ệu chưa đượ c g ử i h ế t do

12 Gửi gói dữ liệu và đợi một khoảng thời gian δT; // theo tỉ lệ các giá trị n i

13 if nh ận đượ c gói ACK trong kho ả ng th ờ i gian δT then

Khi nút nguồn nhận được yêu cầu truyền dữ liệu tới một nút đích, nếu thông tin về các đường đi chưa có trong bảng định tuyến của nó, nút sẽ khởi động quá trình tìm đường để xác định lộ trình phù hợp.

Tiến trình tìm đường bắt đầu bằng việc khởi tạo bộ đếm thời gian T bằng 0 và quảng bá gói tìm đường RREQ tới các nút lân cận Nút nguồn chờ nhận gói trả lời đường RREP trong khoảng thời gian T nhỏ hơn giá trị ngưỡng Tmax Khi nhận được gói RREP, nút nguồn sẽ cập nhật bảng danh sách đường với thông tin về con đường và thời gian định tuyến ước lượng (Ti) tương ứng.

Sau khi danh sách đường đến cùng một nút đích được tạo, nút nguồn tính toán giá trị bội số chung nhỏ nhất L từ các giá trị Ti của các đường trong danh sách Tỉ lệ số gói tin được gửi qua các đường này sẽ được xác định bằng công thức n i = L T / i.

Quá trình truyền dữ liệu qua kỹ thuật cân bằng tải sẽ diễn ra theo các đường trong danh sách, với các gói tin được gửi lần lượt và thời gian chờ giữa các gói là T Giá trị T được xác định dựa trên giá trị n i của từng con đường Nếu trong thời gian T, nút nguồn nhận được gói ACK từ nút đích, nó sẽ tiếp tục gửi gói dữ liệu tiếp theo; nếu không, nó sẽ gửi lại gói dữ liệu hiện tại.

2.2.3 Thuật toán tại nút trung gian

Trong Thuật toán 2, khi một nút trung gian nhận gói tin, nó đầu tiên kiểm tra xem mình có phải là nút nguồn hoặc nút đích hay không Nếu đúng, nó sẽ áp dụng Thuật toán 1 cho nút nguồn hoặc Thuật toán 3 cho nút đích Nếu không, nút trung gian sẽ phân loại gói tin và thực hiện các hành động tương ứng dựa trên loại gói tin nhận được.

- Nếu gói nhận được là gói RREQ, nút trung gian hiện tại sẽ tiếp tục quảng bá gói RREQ kèm theo ID của mình (dòng 2-3)

- Nếu gói nhận được là gói RREP, nút trung gian hiện tại sẽ tiếp tục gửi gói RREP kèm theo ID của mình (dòng 4-5)

Nếu gói nhận được là gói dữ liệu, nút trung gian sẽ chuyển tiếp gói đó dựa trên thông tin có trong gói và thông tin đường đi trong bảng định tuyến của nó.

- Nếu gói nhận được là ACK hoặc NACK của nút đích, nút hiện tại chuyển tiếp gói tới các nút tiếp theo trên con đường tới nút nguồn (dòng 8-11)

Thu ậ t toán 2 : Thuật toán tại nút trung gian

Input: Các thông điệp định tuyến nhận được

Output: Các thông điệp đị nh tuy ế n truy ền đi

1 if (SA ID nút hi ệ n t ạ i) and (DA ID nút hi ệ n t ạ i) then

2 if nh ận đượ c gói RREQ then

3 G ử i gói RREQ kèm ID nút hi ệ n t ạ i;

4 else if nh ận đượ c gói RREP then

5 G ử i gói RREP kèm ID nút hi ệ n t ạ i;

6 else if nh ận đượ c gói d ữ li ệ u then

8 else if nh ận đượ c gói ACK then

10 else if nh ận đượ c gói NACK then

2.2.4 Thu ậ t toán t ại nút đích

Các nút đích trong giao thức định tuyến LCMR áp dụng Thuật toán 3 để xử lý gói tin Khi một nút nhận gói tin, nếu địa chỉ đích trùng với ID của nó, nút đó sẽ xác định là nút đích Sau đó, nút đích sẽ kiểm tra loại gói tin nhận được Nếu là gói RREQ, nó sẽ gửi gói RREP để phản hồi truy vấn đường từ nút nguồn Nếu là gói dữ liệu và được nhận thành công, nút đích sẽ gửi gói ACK; ngược lại, nó sẽ gửi gói NACK tới nút nguồn.

Phân tích hi ệu năng giao thứ c LCMR theo lý thuy ế t

Hiệu năng của giao thức LCMR sẽ được phân tích lý thuyết dựa trên giả định rằng tất cả các đường giữa cặp nút nguồn – đích là độc lập theo nút Tuy nhiên, trong thực tế, các đường này có thể không luôn độc lập theo nút hoặc liên kết, dẫn đến thời gian định tuyến thực tế lớn hơn giá trị lý thuyết ước lượng Những tình huống này sẽ được khảo sát qua phần mô phỏng trong các phần tiếp theo.

Thu ậ t toán 3 : Thu ậ t toán t ại nút đích

Input: RREQ, gói dữ liệu

1 if DA = ID nút hi ệ n t ạ i then

2 if nh ận đượ c gói RREQ then

3 G ử i gói RREP cho nút đã gử i gói RREQ t ớ i nút hi ệ n t ạ i;

4 if hoàn thành vi ệ c nh ậ n gói d ữ li ệ u then

Trong phân tích hiệu năng của giao thức định tuyến, chúng ta bắt đầu với trường hợp đơn giản nhất là định tuyến qua hai con đường Giả sử có N gói dữ liệu được gửi từ S đến D, với N là số chẵn Định lý 1 cho thấy rằng khi chỉ có hai đường P1 và P2 cho một cặp nguồn-đích, với thời gian định tuyến tương ứng là T1 và T2 (với T1 > T2), thì thời gian định tuyến Rp của giao thức LCMR luôn nhỏ hơn thời gian định tuyến Rf của giao thức FMLB.

Chứng minh Đặt N  pn r  , 0    r n 1 Khi sử dụng giao thức

   gói tin s ẽ được đị nh tuy ế n qua đườ ng P 1 và 2 r 2 pn n n

   gói s ẽ được đị nh tuy ế n qua đườ ng P 2

R  pT  T , khi n 1  n 2 N được giả định là chẵn và T 1 T 2

  , do đó R f  R p  0, có nghĩa là R f luôn lớn hơn R p (điều phải chứng minh)

Khi chỉ có hai đường định tuyến từ S đến D, giao thức FMLB và MAODV cho thời gian định tuyến tương đương Tuy nhiên, khi có hai đường với thời gian định tuyến khác nhau, giao thức LCMR luôn cho thời gian định tuyến ngắn hơn so với FMLB và MAODV Để đánh giá hiệu năng của LCMR trong trường hợp có hai hoặc nhiều đường từ nút nguồn S đến nút đích D, chúng ta sẽ xem xét một số ví dụ dưới đây.

Trong kịch bản được mô tả trong Hình 1.6, ba đường P1, P2 và P3 có các giá trị thời gian T1, T2 và T3 lần lượt là 40, 30 và 20 đơn vị Bội số chung lớn nhất (BCNN) của các giá trị này là 120, và khi chia 120 cho 40, ta được kết quả là 3.

Tỷ lệ các gói dữ liệu được gửi theo các đường P1, P2 và P3 là 3:4:6, tương ứng với thời gian định tuyến 120 đơn vị thời gian cho 13 gói dữ liệu Cụ thể, giao thức LCMR sẽ gửi 3 gói qua P1, 4 gói qua P2 và 6 gói qua P3.

Khi áp dụng giao thức FMLB cho cùng một kịch bản, tỷ lệ phân bổ gói dữ liệu qua các đường P1, P2 và P3 sẽ là F1:F2:F3 = 1:1:2 Với tổng cộng 13 gói dữ liệu, sẽ có 3 gói được gửi qua P1, 3 gói qua P2 và 6 gói qua P3 Gói cuối cùng được gửi qua P3 với thời gian định tuyến tối thiểu là 20 đơn vị Tổng thời gian định tuyến cho P1 là 120 đơn vị, cho P2 là 90 đơn vị và cho P3 là 140 đơn vị, dẫn đến tổng thời gian định tuyến là 140 đơn vị, cao hơn so với giao thức LCMR.

Sử dụng giao thức MAODV để phân phối dữ liệu qua ba đường theo cơ chế chia đều, thời gian định tuyến tối đa đạt 160 đơn vị, cao hơn so với giao thức LCMR.

Trong ví dụ này, nút S cần gửi 100 gói dữ liệu đến nút D qua các đường như trong Hình 1 Với n = 13, ta có 100 = 7 × 13 + 9, dẫn đến giao thức LCMR ban đầu sẽ gửi 91 gói dữ liệu Trong số đó, 21 gói được gửi qua đường P1, 28 gói qua đường P2 và 42 gói qua đường P3.

      nên trong số 9 gói còn lại, giao thức CLMR sẽ gửi 2 gói theo đường P1, 2 gói theo đường P2 và 4 gói theo đường P3 Gói cuối cùng sẽđược gửi theo đường P3

Giao thức LCMR gửi tổng cộng 23 gói qua đường P1 trong 920 đơn vị thời gian, 30 gói qua đường P2 trong 900 đơn vị thời gian, và 47 gói qua đường P3 trong 940 đơn vị thời gian.

Do đó, thời gian cần thiết để gửi tất cả 100 gói dữ liệu theo ba con đường trên là max(920,900,940) = 940 đơn vị thời gian

Khi áp dụng giao thức FMLB, gói dữ liệu được phân phối theo tỷ lệ 1:1:2, với 25 gói qua đường P1, 25 gói qua đường P2 và 50 gói qua đường P3 Tổng thời gian định tuyến đạt 1000 đơn vị, cao hơn so với tổng thời gian định tuyến của giao thức LCMR.

Sử dụng giao thức MAODV với phân phối gói đều qua ba con đường, thời gian định tuyến đạt max(1320,990,680)20 đơn vị Giá trị này lớn hơn tổng thời gian định tuyến của giao thức LCMR.

Trong Ví dụ 2, thời gian tối thiểu để định tuyến 100 gói dữ liệu từ S đến D qua ba đường P1, P2 và P3 là 930 đơn vị thời gian, bao gồm 840 đơn vị cho 91 gói đầu và 90 đơn vị cho 9 gói còn lại (2 gói qua P1, 3 gói qua P2 và 4 gói qua P3) Bài toán này tương tự như bài toán lập lịch cho N tác vụ độc lập trên k bộ xử lý song song, có độ phức tạp NP.

Xét trường hợp tổng quát với k con đường P1, P2, , Pk có thời gian định tuyến T1, T2, , Tk sao cho T1 ≥ T2 ≥ ≥ Tk Để đơn giản, giả sử tổng số N gói dữ liệu được định tuyến từ S đến D là bội số nguyên của tổng số n_i từ i = 1 đến k.

Thời gian R p để giao thức LCMR định tuyến N gói dữ liệu từS đến D qua các con đường P P 1 , , , 2 P k được xác định theo công thức (3):

Nói cách khác, thời gian định tuyến R f của giao thức FMLB được xác định theo công thức (4)

Theo Định lý 2, thời gian định tuyến N gói dữ liệu bằng giao thức LCMR luôn ngắn hơn so với thời gian định tuyến bằng giao thức FMLB [13] khi tỉ lệ

F r n  và giả sử 1 2 i i i k r r  r với  i i 1 2, , ,i k  là hoán vị của  1,2, , k  Ta có 1 2 1 1 2 2

1: : :2 k n n n khác F F 1 : : : 2 F k nên mọi giá trị 1 , , , 2 i i i k r r r có thể không bằng nhau

Từ công thức (3) và (4), ta có: 1

  Đây chính là điều cần chứng minh

Giả sử có 300 gói dữ liệu cần gửi từ nút S đến nút D qua 6 con đường P1, P2, P3, P4, P5 và P6, được sắp xếp theo thứ tự giảm dần của thời gian định tuyến Việc phân phối 300 gói này sẽ được thực hiện bằng giao thức FMLB qua các đường P1.

P2, P3, P4, P5 và P6 tuân theo tỷ lệ của các số Fibonacci tương ứng F1, F2, F3, F4,

Giao thức LCMR là một phương pháp định tuyến đa đường, áp dụng cơ chế cân bằng tải nhằm tối ưu hóa hiệu suất truyền dữ liệu, đặc biệt là về thời gian định tuyến.

Giao thức LCMR khám phá đường giống như các giao thức định tuyến khác như FMLB và MAODV, nhưng điểm khác biệt chính là kỹ thuật cân bằng tải dữ liệu qua nhiều đường giữa cặp nút nguồn-đích.

Giao thức LCMR sử dụng một phương pháp cân bằng tải dữ liệu khác biệt so với FMLB và MAODV Thay vì dựa vào tỉ lệ giá trị trong chuỗi Fibonacci hoặc phân chia đều tải, LCMR tính toán giá trị bội số chung nhỏ nhất của thời gian định tuyến giữa các cặp nút nguồn và đích Dựa vào tỉ lệ giữa thời gian định tuyến một gói tin và bội số chung nhỏ nhất, giao thức này xác định số gói tin được truyền trên mỗi con đường, từ đó tối ưu hóa quá trình cân bằng tải.

Thời gian định tuyến dữ liệu của giao thức LCMR được chứng minh là ngắn hơn so với giao thức FMLB và MAODV.

TH Ử NGHI ỆM VÀ ĐÁNH GIÁ KẾ T QU Ả

K ị ch b ả n mô ph ỏng và các độ đo đánh giá hiệu năng

Hiệu năng của giao thức LCMR được so sánh với bốn giao thức định tuyến đa đường: FMLBRT, FMLBHC, MAODVRT và MAODVHC Các giao thức này được đánh giá dựa trên giả định rằng các đường định tuyến không nhất thiết phải độc lập theo nút hoặc cạnh Giao thức FMLBRT tìm k đường ngắn nhất theo thời gian định tuyến và phân phối gói dữ liệu dựa trên giá trị chuỗi Fibonacci Trong khi đó, FMLBHC xác định k đường ngắn nhất theo số chặng và cũng sử dụng chuỗi Fibonacci để phân phối gói Giao thức MAODVRT và MAODVHC tìm k đường ngắn nhất dựa trên thời gian định tuyến và số bước nhảy, phân phối gói đồng đều theo các đường đã tìm được.

Bảng 3.1 Giá trị của các tham số mô phỏng

Kích cỡ mạng (50 x 50)m 2 cho mạng kiểu ngẫu nhiên

Phạm vi truyền thông của nút 15m cho mạng kiểu ngẫu nhiên

10m cho mạng kiểu lưới Kích cỡ gói tin 1 KB

Băng thông kênh truyền 1 MBps Độ trễ liên kết 1 ms

Sinh lưu lượng ngẫu nhiên

Gói dữ liệu được tạo ra theo phân bố Poisson, với nút nguồn và nút đích được chọn ngẫu nhiên đồng nhất trong khoảng từ 1 đến 25 Thời gian trung bình giữa hai lần tạo gói dao động từ 2 giây đến 20 giây.

Số lượng gói tin tạo ra cho một yêu cầu 2.000 đến 10.000

Mô phỏng mạng ad hoc với 25 nút đã được thực hiện trên hai topo: ngẫu nhiên và dạng lưới, sử dụng phần mềm NS3 Trong topo ngẫu nhiên, các nút được phân bố đều trong diện tích (50 × 50)m², trong khi ở topo dạng lưới, các nút được bố trí trên các ô lưới kích thước 10m, với khoảng cách giữa các ô là (40 × 40)m² Phạm vi truyền thông của mỗi nút là 15m cho topo ngẫu nhiên và 10m cho topo dạng lưới Chi tiết các tham số mô phỏng được trình bày trong Bảng 3.1.

Mô phỏng lưu lượng mạng được thực hiện ngẫu nhiên, với lưu lượng dữ liệu thứ i được gửi từ nút nguồn S i đến nút đích D i, được biểu diễn bằng bộ ba (t i , S i , D i ) Thời gian tạo lưu lượng tuân theo phân phối Poisson, trong khi S i và D i được sinh ra độc lập trong khoảng 1-25 Số lượng gói dữ liệu gửi từ nguồn đến đích dao động từ 2.000 đến 10.000 gói, mỗi gói có kích thước 1KB, tương ứng với tổng dữ liệu từ 2MB đến 10MB Thời gian giữa hai yêu cầu truyền dữ liệu cũng theo phân phối Poisson, với khoảng từ 2 đến 20 giây Băng thông mỗi kênh truyền được giả định là 1MBps, dẫn đến độ trễ truyền mỗi gói là 1 mili giây Các đường chọn cho cặp nguồn-đích có thể không độc lập, vì vậy hàng đợi tại mỗi nút có thể chứa gói tin từ nhiều cặp khác nhau cũng như từ cùng một cặp khi có các nút chung Thời gian định tuyến của một gói tin được tính bằng tổng độ trễ liên kết và độ trễ hàng đợi tại các nút trung gian.

Trong các mô phỏng, mỗi cặp nút nguồn-đích trong mạng có từ 1 đến k đường đi, với k được thiết lập là 5 Các gói dữ liệu được truyền từ nguồn đến đích qua j đường đi này, giúp đánh giá hiệu năng của các giao thức được mô phỏng.

Kết quả mô phỏng với một cặp nút nguồn-đích

3.2.1 Th ời gian đị nh tuy ế n m ộ t gói tin

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

Th ờ i gian đị nh tuy ế n m ộ t gói tin ( t i k ) (ms) LCMR FMLBRT MAODVRT FMLBHC MAODVHC

Thời gian định tuyến cho một gói tin được ước lượng bởi các giao thức sau khi thực hiện pha tìm đường Để xác định giá trị này, các mô phỏng đã được thực hiện đối với năm giao thức LCMR, FMLBRT.

Bài viết này so sánh ba giao thức MAODVRT, FMLBHC và MAODVHC dựa trên sự thay đổi số lượng đường giữa một cặp nút nguồn-đích xác định Kết quả thời gian định tuyến gói tin của các giao thức được trình bày trong Bảng 3.2, khi sử dụng các đường tách biệt theo nút giữa cặp nguồn-đích Bảng 3.3 cung cấp kết quả tương ứng khi các đường có chung liên kết giữa cặp nguồn-đích.

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

Th ời gian đị nh tuy ế n m ộ t gói tin ( t i k ) (ms) LCMR FMLBRT MAODVRT FMLBHC MAODVHC

3.2.2 S ố gói tin đượ c g ử i t ừ nút ngu ồ n Để triển khai kỹ thuật cân bằng tải cho 10.000 gói dữ liệu trên k đường giữa một cặp nguồn đích, mô phỏng đã được thực hiện với sự thay đổi giá trị của tham số k giữa các lần mô phỏng cho cả 5 giao thức Kết quả của số gói tin dữ liệu được gửi đi từ nút nguồn theo các con đường trong sốk đường giữa một cặp nút nguồn đích được tính toán theo lý thuyết về kỹ thuật cân bằng tải của mỗi giao thức Kết quả này được sử dụng để tạo lưu lượng dữ liệu và điều khiển cân bằng tải của các giao thức

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

Số gói tin gửi từ nút nguồn ( n i k )

LCMR FMLBRT MAODVRT FMLBHC MAODVHC

Để xác định số gói tin được gửi từ nút nguồn qua đường thứ i trong số k đường giữa cặp nút nguồn và đích, cần áp dụng các giao thức sử dụng trong mô phỏng.

Gọi n_i_k là số gói tin được gửi từ nút nguồn qua đường thứ i trong số k đường đến nút đích, với t_i_k là thời gian định tuyến của một gói tin qua đường đó Tổng số gói tin được gửi là N, với N = 10.000.

Với giao thức LCMR, ta có 1

Giao thức FMLBRT và FMLBHC sử dụng tỉ lệ gửi gói tin theo chuỗi Fibonacci với tỷ lệ 5:3:2:1:1 cho đường thứ i Trong khi đó, giao thức MAODVRT và MAODVHC chia đều số gói tin N cho k đường, đảm bảo tỉ lệ gửi gói tin qua các đường là bằng nhau.

Giá trị trong các mô phỏng được trình bày trong Bảng 3.4 và Bảng 3.5 tương ứng với mô hình đường tách biệt theo nút và các đường có chung liên kết.

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

3.2.3 Th ời gian đị nh tuy ế n d ữ li ệ u theo lý thuy ế t

Thời gian định tuyến T i k cho n i k gói dữ liệu qua đường thứ i trong số k đường giữa một cặp nút nguồn và đích được ước lượng theo công thức: T i k = n i k × t i k, trong đó n i k là tổng số gói tin được gửi từ nút nguồn qua đường thứ i và t i k là thời gian định tuyến cho một gói tin qua đường đó.

Gọi T là tổng thời gian định tuyến cho N gói tin dữ liệu Giá trị của k T k được xác định theo công thức T k max( ), 1T i k  i k

Thời gian định tuyến dữ liệu cho từng con đường và tổng thời gian định tuyến cho N.000 gói tin dữ liệu được trình bày trong mô hình đường tách biệt theo nút và mô hình đường có chung liên kết, cụ thể tại Bảng 3.6 và Bảng 3.7.

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 k i

LCMR FMLBRT MAODVRT FMLBHC MAODVHC k

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 k i

LCMR FMLBRT MAODVRT FMLBHC MAODVHC k

3.2.3 Th ời gian đị nh tuy ế n d ữ li ệ u c ủ a mô ph ỏ ng

Kết quả thời gian yêu cầu cho việc định tuyến 10.000 gói tin dữ liệu qua các đường tách biệt từ 5 đến 1 giữa một cặp nút nguồn-đích đã được trình bày trong Bảng 3.8, với các mô phỏng cho các giao thức LCMR, FMLBRT, MAODVRT, FMLBHC và MAODVHC Đồng thời, kết quả tương ứng của các giao thức cho mô hình các đường có chung liên kết cũng được nêu trong Bảng 3.9.

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

Thời gian định tuyến của mô phỏng (s) LCMR FMLBRT MAODVRT FMLBHC MAODVHC

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

Thời gian định tuyến của mô phỏng (s) LCMR FMLBRT MAODVRT FMLBHC MAODVHC

So sánh dữ liệu trong Bảng 3.8 với Bảng 3.6 và Bảng 3.9 với Bảng 3.7 cho thấy thời gian định tuyến dữ liệu trong mô phỏng tương đương với ước lượng lý thuyết khi sử dụng các đường tách biệt theo nút Các đường này không chia sẻ liên kết, do đó băng thông không bị chia sẻ trong quá trình truyền dữ liệu song song Điều này giải thích tại sao kết quả định tuyến dữ liệu của mô phỏng lớn hơn ước lượng lý thuyết đối với các giao thức sử dụng đường có chung liên kết.

Kết quả mô phỏng với nhiều cặp nút nguồn-đích

Trong phần này, các kịch bản thử nghiệm mô phỏng được thực hiện với nhiều cặp nút nguồn-đích ngẫu nhiên, trong đó thời gian tạo mẫu lưu lượng tại nút nguồn tuân theo phân phối Poisson Thời gian định tuyến của các giao thức LCMR, FMLBRT, FLMBHC, MAODVRT và MAODVHC được tính toán dựa trên thời gian định tuyến trung bình từ các lần mô phỏng với các tham số động ngẫu nhiên Kết quả về thời gian trung bình để truyền 10,000 gói tin được trình bày trong Bảng 4.

Trong nghiên cứu này, chúng tôi đã phân tích việc truyền tải 8000, 6000, 4000 và 2000 gói tin dữ liệu từ nút nguồn đến nút đích trong hai loại topo mạng: mạng ngẫu nhiên và mạng dạng lưới Việc truyền tải được thực hiện qua 5, 4, 3, 2 và 1 đường giữa một cặp nút nguồn-đích, nhằm đánh giá hiệu suất và độ tin cậy của các phương thức truyền tải trong các cấu trúc mạng khác nhau.

3.3.1 Tác độ ng c ủ a s ố đườ ng t ớ i th ời gian đị nh tuy ế n

* Trường hợp 10.000 gói tin dữ liệu

Kết quả mô phỏng cho thấy thời gian định tuyến cần thiết để các giao thức LCMR, FMLBRT, FMLBHC, MAODVRT và MAODVHC hoàn thành việc truyền đồng thời 10.000 gói tin dữ liệu qua các đường giữa từ 5 đến 1 giữa một cặp nút nguồn-đích trong mô hình mạng di động ngẫu nhiên và mô hình mạng di động dạng lưới được trình bày trong Bảng 3.10 và Bảng 3.11.

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

Thời gian định tuyến cần thiết (s) LCMR FMLBRT MAODVRT FMLBHC MAODVHC

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

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

Các đồ thị trong Hình 3.1 minh họa mối quan hệ giữa thời gian định tuyến cần thiết cho các giao thức được mô phỏng, dựa trên sự thay đổi số đường giữa một cặp nút nguồn và đích trong hai mô hình mạng di động: ngẫu nhiên và dạng lưới.

Kết quả mô phỏng cho thấy thời gian định tuyến cần thiết để hoàn thành việc truyền đồng thời 8.000 gói tin dữ liệu qua các đường giữa trong một cặp nút nguồn-đích đã được trình bày trong Bảng 3.12 và Bảng 3.13, tương ứng với mô hình mạng di động ngẫu nhiên và mạng di động dạng lưới.

Th ời g ia n đị nh tu yế n (s )

Số lượng đường TOPO NGẪU NHIÊN

LCMR FMLRT MAODVRT FMLBHC MAODVHC

Số lượng đường TOPO DẠNG LƯỚI

Các đồ thị trong Hình 3.2 thể hiện mối quan hệ giữa thời gian định tuyến cần thiết cho các giao thức được mô phỏng và sự thay đổi của số đường giữa cặp nút nguồn và đích trong hai mô hình mạng di động: mạng di động ngẫu nhiên và mạng di động dạng lưới.

Kết quả mô phỏng cho thấy thời gian định tuyến cần thiết để hoàn thành việc truyền đồng thời 6.000 gói tin dữ liệu qua các đường giữa trong mô hình mạng di động ngẫu nhiên và mạng di động dạng lưới được trình bày trong Bảng 3.14 và Bảng 3.15.

Các đồ thị thể hiện mối quan hệ giữa thời gian định tuyến cần thiết cho các giao thức mô phỏng và sự thay đổi về số đường giữa cặp nút nguồn và đích, được phân tích cho hai mô hình mạng di động: mạng di động ngẫu nhiên và mạng di động dạng lưới, như trình bày trong Hình 3.3.

Kết quả mô phỏng cho thấy thời gian định tuyến cần thiết để hoàn thành việc truyền đồng thời 4.000 gói tin dữ liệu qua các đường giữa trong một cặp nút nguồn-đích, tương ứng với mô hình mạng di động ngẫu nhiên và mạng di động dạng lưới, được trình bày trong Bảng 3.16 và Bảng 3.17.

Các đồ thị thể hiện mối quan hệ giữa thời gian định tuyến cần thiết cho các giao thức được mô phỏng và sự thay đổi giá trị số đường giữa cặp nút nguồn-đích tương ứng Hai mô hình mạng di động ngẫu nhiên và mạng di động dạng lưới được trình bày trong Hình 3.4.

Kết quả mô phỏng cho thấy thời gian định tuyến cần thiết để hoàn thành việc truyền đồng thời 2.000 gói tin dữ liệu qua 5, 4, 3, 2, 1 đường giữa một cặp nút nguồn-đích trong mô hình mạng di động ngẫu nhiên và mạng di động dạng lưới, được trình bày trong Bảng 3.18 và Bảng 3.19.

Các đồ thị trong Hình 3.5 thể hiện mối quan hệ giữa thời gian định tuyến cần thiết cho các giao thức được mô phỏng và sự thay đổi về số đường giữa cặp nút nguồn và đích trong hai mô hình mạng di động: ngẫu nhiên và dạng lưới.

3.3.2 Tác độ ng c ủ a s ố gói d ữ li ệ u t ớ i th ời gian đị nh tuy ế n

Với kết quả mô phỏng được trình bày trong các bảng từ Bảng 3.2 đến

Bảng 3.17 trình bày mối quan hệ giữa số lượng gói tin cần định tuyến và thời gian định tuyến, được thể hiện qua các đồ thị từ Hình 3.6 đến Hình 3.10 Mỗi hình vẽ bao gồm hai phần: bên trái là kết quả cho mô hình mạng di động ngẫu nhiên, trong khi bên phải thể hiện mô hình mạng di động dạng lưới.

Hình 3.6 Tác động của số gói tin tới thời gian định tuyến qua 5 đường

Số gói tin TOPO NGẪU NHIÊN

Số gói tin TOPO DẠNG LƯỚI

Đánh giá kế t qu ả

Qua các kết quả mô phỏng đã được trình bày chi tiết trong phần 3.5 và 3.6, có thể rút ra một số nhận xét đánh giá như sau:

Giao thức LCMR cho thấy hiệu năng định tuyến dữ liệu tốt nhất trong số 5 giao thức được kiểm nghiệm, bao gồm LCMR, FMLBRT, FMLBHC, MAODVRT và MAODVHC Sự khác biệt về hiệu suất định tuyến giữa các giao thức càng trở nên rõ rệt khi số lượng đường được sử dụng đồng thời trong cơ chế cân bằng tải tăng lên.

Số lượng đường truyền được sử dụng trong cơ chế cân bằng tải là yếu tố quan trọng ảnh hưởng đến hiệu năng định tuyến của các giao thức Khi truyền cùng một lượng dữ liệu, thời gian hoàn thành truyền dữ liệu sẽ tỉ lệ nghịch với số lượng đường giữa cặp nút nguồn và đích.

- Các giao thức sử dụng độ đo định tuyến là thời gian định tuyến là LCMR, FMLBRT và MAODVRT cho kết quả hiệu năng về thời gian định

FMLBHC MAODVHC tuyến tốt hơn các giao thức sử dụng độ đo định tuyến là số chặng (giao thức FMLBHC và giao thức MAODVHC)

Các giao thức định tuyến được thử nghiệm trên mô hình mạng di động ngẫu nhiên cho thấy hiệu năng vượt trội so với khi thử nghiệm trên mô hình mạng di động dạng lưới.

Thời gian định tuyến của các giao thức trong mô phỏng cho thấy kết quả tương đương với ước lượng lý thuyết khi chỉ có một luồng dữ liệu giữa một cặp nút nguồn-đích Tuy nhiên, trong trường hợp có nhiều luồng dữ liệu giữa nhiều cặp nút nguồn-đích, thời gian định tuyến theo mô phỏng sẽ cao hơn so với ước lượng lý thuyết Điều này là hợp lý vì thực tế thường xảy ra tình trạng tắc nghẽn và trễ hàng đợi tại các liên kết và nút trong mạng khi nhiều luồng dữ liệu được truyền đồng thời.

Chương 3 đã trình bày các kết quả quan trọng trong việc mô phỏng, so sánh và đánh giá hiệu năng của giao thức định tuyến LCMR so với các giao thức đa đường FMLBRT, FMLBHC, MAODVRT và MAODVHC

Các kịch bản mô phỏng đã được phát triển cho mạng MANET với topo di động ngẫu nhiên và topo di động dạng lưới Hiệu suất thời gian định tuyến dữ liệu của các giao thức được kiểm nghiệm, so sánh và đánh giá dựa trên tác động của số luồng dữ liệu, số đường đi giữa cặp nút nguồn – đích, và số gói tin dữ liệu.

Kết quả phân tích mô phỏng cho thấy giao thức FMLB vượt trội về hiệu suất thời gian định tuyến dữ liệu so với các giao thức khác.

Mạng MANET, được hình thành từ các kết nối tạm thời giữa các nút mạng di động mà không cần cơ sở hạ tầng mạng cố định, mang nhiều đặc điểm khác biệt so với mạng không dây và có dây truyền thống Điều này tạo ra nhiều thách thức và mở ra nhiều hướng nghiên cứu mới, trong đó vấn đề định tuyến là một trong những vấn đề được các nhà nghiên cứu chú trọng giải quyết nhất.

Bài luận văn này đã tiến hành nghiên cứu tổng quan về mạng MANET và cơ chế hoạt động của một số giao thức định tuyến đa đường Đồng thời, nó cũng đi sâu vào phân tích giao thức định tuyến đa đường LCMR với tính năng cân bằng tải.

Luận văn tập trung vào việc nghiên cứu cơ chế hoạt động và đánh giá hiệu năng của giao thức định tuyến đa đường LCMR trong mạng MANET Khác với giao thức FLMB sử dụng chuỗi Fibonacci để cân bằng tải dữ liệu, hoặc giao thức MAODV phân chia đều tải, LCMR tính toán bội số chung nhỏ nhất của thời gian định tuyến giữa các cặp nút nguồn-đích Từ đó, giao thức này sử dụng tỷ lệ giữa thời gian định tuyến và bội số chung nhỏ nhất để xác định số gói tin được truyền trên mỗi đường trong quá trình cân bằng tải.

Thời gian định tuyến dữ liệu của giao thức LCMR được chứng minh lý thuyết là ngắn hơn so với giao thức FMLB và MAODV.

Luận văn đã thực hiện mô phỏng để so sánh hiệu năng thời gian định tuyến của giao thức LCMR với các giao thức đa đường FMLBRT, FMLBHC, MAODVRT và MAODVHC Các kịch bản mô phỏng được thiết lập cho mạng MANET với topo di động ngẫu nhiên và dạng lưới Độ đo hiệu năng thời gian định tuyến dữ liệu của các giao thức được kiểm nghiệm và đánh giá dựa trên số luồng dữ liệu, số đường đi giữa cặp nút nguồn – đích, và số gói tin dữ liệu Kết quả phân tích cho thấy giao thức LCMR đạt hiệu năng tối ưu hơn trong việc định tuyến dữ liệu so với các giao thức khác.

Việc đánh giá hiệu năng của giao thức LCMR hiện chỉ dựa trên thời gian định tuyến dữ liệu, do đó cần thực hiện các nghiên cứu tiếp theo để đánh giá toàn diện hơn qua các chỉ số như tỉ lệ truyền thành công, thông lượng và chi phí định tuyến Ngoài ra, kỹ thuật cân bằng tải dựa trên bội số chung nhỏ nhất của thời gian khám phá đường đi có thể được áp dụng cho các giao thức định tuyến đa đường khác, nhằm nâng cao hiệu năng mạng MANET.

[1] A Nasipuri, R Castaủeda, S.R Das (2001), “Performance of multipath routing for on- demand protocols in mobile ad hoc networks”, Mobile Network Appl

[2] B Ansuman, S Koushik (2017), “An efficient protocol for load-balanced multipath routing in mobile ad hoc networks”, Ad Hoc Networks 63, pp 104-114

[3] C.E Perkins , E.M Royer (1999), “Ad-hoc on-demand distance vector routing, Proceedings of the Second IEEE Workshop on Mobile Computing Systems and Applications”, pp 90-100

[4] C Perkins (2001), “Ad Hoc Networking”, Addison-Wesley, USA

[5] D.A Tran , H Raghavendra (2005), “Routing with congestion awareness and adaptivity in mobile ad hoc networks”, in: IEEE Wireless Communications and Networking Conference, vol 4, pp 1988–1994

[6] G Parissidis, V Lenders, M May, B Plattner (2006), “Multi-path Routing Protocols in Wireless Mobile Ad Hoc Networks: A Quantitative Comparison”, International Conference on Next Generation Wired/Wireless Networking, pp 313-326 doi: 10.1007/11759355

[7] L Wang, Y Shu, M Dong, L Zhang, O.W.W Yang (2001), “Adaptive multipath source routing in ad hoc networks”, Communications, 2001 ICC

2001 IEEE International Conference, pp 867-871 vol.3, doi: 10.1109/ICC.2001.937362

[8] M Naseem, C Kumar (2015), “Congestion-aware Fibonacci sequence based multipath load balancing routing protocol for MANETs”, Wireless Pers Commun 84 (4), pp 2955-2974

[9] M.R Pearlman, Z.J Haas, P Sholander, S.S Tabrizi (2000), “On the impact of alternate path routing for load balancing in mobile ad hoc networks”, Mobile

Tiê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
Tác giả	Trần Thị Thu Thảo
Người hướng dẫn	PGS.TS. Nguyễn Văn Tam
Trường học	Đại học Thái Nguyên
Chuyên ngành	Khoa học máy tính
Thể loại	luận văn thạc sĩ
Năm xuất bản	2020
Thành phố	Thái Nguyên

Định dạng
Số trang	65
Dung lượng	1,37 MB