Nguyên cứu cơ chế chọn đường tối ưu ytong thuật toán định tuyến enhanced ant aodv cho mạng manet

65 Trang 6 DANH MỤC TỪ VIẾT TẮT Chữ viết tắt Chữ đầy đủ Ý nghĩa AODV Ad-hoc On-demand Distance Vector Giao thức định tuyến theo yêu cầu dựa trên vector khoảng cách DSDV Destination-Seq

NGUYỄN ANH TUẤN

NGHIÊN CỨU CƠ CHẾ CHỌN ĐƯỜNG TỐI ƯU TRONG THUẬT TOÁN ĐỊNH TUYẾN ENHANCED-ANT-AODV

CHO MẠNG MANET

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2021

NGUYỄN ANH TUẤN

NGHIÊN CỨU CƠ CHẾ CHỌN ĐƯỜNG TỐI ƯU TRONG THUẬT TOÁN ĐỊNH TUYẾN ENHANCED-ANT-AODV

Thái Nguyên - 2021

LỜI CẢM ƠN

Sau thời gian học tập và nghiên cứu tại trường Đại học Công nghệ thông tin

và Truyền thông – Đại học Thái Nguyên, em đã hoàn thành luận văn tốt nghiệp thạc

sĩ ngành Khoa học máy tính Để có được kết quả này, em xin bày tỏ sự kính trọng

và lòng biết ơn sâu sắc tới:

TS Đàm Thanh Phương là cán bộ hướng dẫn khoa học đã luôn tận tình giúp

đỡ và chỉ bảo em trong suốt quá trình làm luận văn

Các cán bộ, giảng viên Khoa Công nghệ thông tin và Phòng Đào tạo cùng toàn

thể các thầy, cô giáo trong trường Trường Đại học CNTT & TT - ĐHTN đã tận tình

chỉ bảo, hướng dẫn và giúp đỡ em trong suốt quá trình em thực hiện đề tài luận văn

này

Bên cạnh đó sự giúp đỡ của gia đình, bạn bè và người thân đã luôn ủng hộ và

tạo điều kiện tốt nhất để em có thể tập trung nghiên cứu hoàn thành luận văn

Do về mặt kiến thức và thời gian còn hạn chế, luận văn còn nhiều khiếm

khuyết Em mong được sự đóng góp ý kiến của các thầy, cô và mọi người để luận

văn hoàn thiện hơn

Xin trân trọng cảm ơn!

Thái Nguyên, ngày … tháng … năm 2021

Học viên

Nguyễn Anh Tuấn

MỤC LỤC

DANH MỤC TỪ VIẾT TẮT 1

DANH MỤC BẢNG BIỂU 2

DANH MỤC HÌNH VẼ 3

MỞ ĐẦU 4

CHƯƠNG 1 TỔNG QUAN VỀ VẤN ĐỀ ĐỊNH TUYẾN TRONG MẠNG MANET 7

1.1 Tổng quan về mạng MANET 7

1.1.1 Khái niệm mạng MANET 7

1.1.2 Đặc điểm của mạng MANET 8

1.1.3 Ứng dụng của mạng MANET 9

1.2 Một số chiến lược định tuyến trong mạng MANET 11

1.2.1 Phân loại các chiến lược định tuyến 11

1.2.2 Chiến lược định tuyến tìm đường trước và tìm đường theo yêu cầu 12

1.2.3 Định tuyến cập nhật định kỳ và cập nhật theo sự kiện 13

1.2.4 Định tuyến phẳng và định tuyến phân cấp 13

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 15

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

1.2.7 Định tuyến đơn đường và định tuyến đa đường 17

1.3 Một số nghiên cứu tối ưu hiệu năng định tuyến trong mạng MANET 17

1.4 Tổng kết Chương 1 22

CHƯƠNG 2 CƠ CHẾ CHỌN ĐƯỜNG TỐI ƯU TRONG GIAO THỨC ĐỊNH TUYẾN ENHANCED-ANT AODV 23

2.1 Bài toán chọn đường tối ưu trong mạng MANET 23

2.2 Mô tả hoạt động của giao thức 28

2.3 Các độ đo định tuyến 29

2.3.1 Độ đo “Tín hiệu sinh học” của liên kết 29

2.3.2 Độ đo cường độ tín hiệu nhận (RSSM) 30

2.3.3 Độ đo tắc nghẽn (CM) 30

2.3.4 Độ đo năng lượng còn lại (REM) 31

2.3.5 Xác định độ đo số chặng (HCM) 32

2.4 Cấu trúc các gói tin điều khiển và bảng định tuyến 32

2.4.1 Gói yêu cầu tìm đường REQ_ANT 32

2.4.2 Gói trả lời đường REP_ANT 32

2.4.3 Bảng định tuyến 33

2.5 Thuật toán định tuyến 33

2.5.1 Lưu đồ thuật toán tiến trình định tuyến 33

2.5.2 Mô tả chi tiết tiến trình định tuyến 35

2.6 Minh họa thuật toán định tuyến Enhanced-ANT-AODV 40

2.7 Tổng kết Chương 2 41

CHƯƠNG 3 ĐÁNH GIÁ HIỆU QUẢ CỦA CƠ CHẾ CHỌN ĐƯỜNG TỐI ƯU CỦA GIAO THỨC ĐỊNH TUYẾN ENHANCED-ANT-AODV 43

3.1 Môi trường mô phỏng 43

3.2 Các độ đo hiệu năng 45

3.3 Kết quả mô phỏng và đánh giá 45

3.3.1 Đánh giá theo tác động của số nút mạng 45

3.3.2 Đánh giá theo tác động của tốc độ nút 52

3.3.3 Đánh giá theo tác động của lưu lượng dữ liệu 58

3.4 Tổng kết Chương 3 64

KẾT LUẬN 65

TÀI LIỆU THAM KHẢO 67

DANH MỤC TỪ VIẾT TẮT

AODV Ad-hoc On-demand Distance

Vector

Giao thức định tuyến theo yêu cầu dựa trên vector khoảng cách DSDV Destination-Sequenced

Distance- Vector routing

Giao thức định tuyến bảng, dựa trên vector khoảng cách theo chặng DSR Dynamic Source Routing

protocol

Giao thức định tuyến động dựa theo

nguồn HSR Hierarchical State Routing Định tuyến phân cấp

OSLR Optimized Link State Routing Định tuyên link state được tối ưu ZPR Zone Routing Protocol Giao thức định tuyến theo vùng WRP Wireless Routing Protocol Giao thức định tuyến không dây TORA Temporally Ordered Routing

Algorithm

Thuật toán định tuyến có thứ tự tạm

thời MRAA Multi-level Routing Algorithm

Ad hoc

Thuật toán định tuyến đa đường có chia mức cho mạng ad hoc BFBR Bird flocking behavior based

routing

Định tuyến dựa trên hành vi của đàn

chim RSSM received signal strength meter Độ đo cường độ tín hiệu nhận REM Remain Energy Meter Độ đo năng lượng còn lại

DANH MỤC BẢNG BIỂU

Bảng 1.1 Phân loại các chiến lược định tuyến của mạng MANET 12

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

Bảng 3.2 Thông lượng của các giao thức theo số lượng nút 46

Bảng 3.3 Tỷ lệ truyền thành công của các giao thức theo số lượng nút 47

Bảng 3.4 Trễ đầu cuối trung bình của các giao thức theo số lượng nút 49

Bảng 3.5 Tỷ lệ nút sống sót của các giao thức theo số lượng nút 50

Bảng 3.6 Thông lượng của các giao thức theo tốc độ nút 52

Bảng 3.7 Tỷ lệ truyền thành công của các giao thức theo tốc độ nút 53

Bảng 3.8 Trễ đầu cuối trung bình của các giao thức theo số lượng nút 55

Bảng 3.9 Tỷ lệ nút sống sót của các giao thức theo số lượng nút 57

Bảng 3.10 Thông lượng của các giao thức theo lưu lượng dữ liệu 58

Bảng 3.11 Tỷ lệ truyền thành công theo lưu lượng dữ liệu 60

Bảng 3.12 Trễ đầu cuối trung bình theo lưu lượng dữ liệu 61

Bảng 3.13 Tỷ lệ nút sống sót của các giao thức theo lưu lượng dữ liệu 62

DANH MỤC HÌNH VẼ

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

Hình 2.1 Minh họa mạng MANET chiến thuật 23

Hình 2.2 Ví dụ về tiến trình chọn đường 26

Hình 2.3 Cấu trúc header gói REQ_ANT 32

Hình 2.4 Cấu trúc header gói REP_ANT 33

Hình 2.5 Cấu trúc bảng định tuyến của giao thức Enhanced-ANT-AODV 33

Hình 2.6 Lưu đồ thuật toán định tuyến của giao thức Enhanced-ANT-AODV 34

Hình 2.7 Minh họa tiến trình định tuyến giao thức Enhanced-ANT-AODV 40

Hình 3.1 Biểu đồ biến đổi thông lượng theo số nút 47

Hình 3.2 Biểu đồ biến đổi tỷ lệ truyền thành công theo số nút 48

Hình 3.3 Biểu đồ biến đổi trễ đầu cuối trung bình theo số nút 50

Hình 3.4 Biểu đồ biến đổi tỷ lệ nút sống sót theo số nút 51

Hình 3.5 Biểu đồ biến đổi thông lượng theo tốc độ nút 53

Hình 3.6 Biểu đồ biến đổi tỷ lệ truyền thành công theo tốc độ nút 55

Hình 3.7 Biểu đồ biến đổi trễ đầu cuối trung bình theo tốc độ nút 56

Hình 3.8 Biểu đồ biến đổi tỷ lệ nút sống sót theo tốc độ nút 58

Hình 3.9 Biểu đồ biến đổi thông lượng theo lưu lượng dữ liệu 59

Hình 3.10 Biểu đồ biến đổi tỷ lệ truyền thành công theo lưu lượng dữ liệu 61

Hình 3.11 Biểu đồ biến đổi trễ đầu cuối trung bình theo lưu lượng dữ liệu 61

Hình 3.12 Biểu đồ biến đổi tỷ lệ nút sống sót theo lưu lượng dữ liệu 63

MỞ ĐẦU

Trong những năm gần đây, hiệu năng của máy tính và công nghệ truyền thông không dây đã phát triển một cách mạnh mẽ dẫn tới việc sử dụng và ứng dụng điện toán di động không dây tiên tiến ngày càng phổ biến Phần lớn sự phát triển này liên quan đến việc sử dụng bộ giao thức IP

Mạng ad hoc di động (MANET) được thiết kế với mục đích hỗ trợ hoạt động mạng di động không dây một cách hiệu quả và mạnh mẽ thông qua việc kết hợp chức năng định tuyến vào các nút di động Điều này đòi hỏi mạng MANET phải có cấu trúc liên kết đa điểm, động, ngẫu nhiên và tương thích với các thay đổi nhanh chóng về cấu hình

Được hình thành bởi các kết nối tạm thời giữa các nút mạng di động không có

sự hỗ trợ của cơ sở hạ tầng mạng cố định, mạng MANET có nhiều những đặc điểm khác biệt so với mạng không dây và có dây truyền thống làm nảy sinh nhiều thách thức và các hướng nghiên cứu khác nhau như: vấn đề định tuyến hiệu quả khi topo mạng thay đổi, đảm bảo chất lượng dịch vụ theo yêu cầu từ chương trình ứng dụng, đảm bảo an ninh mạng, tiết kiệm năng lượng, khả năng tự tổ chức, chuyển đổi các dịch vụ từ mô hình client-server và đảm bảo hiệu năng khi kích thước mạng thay đổi Kết quả nghiên cứu phân loại và đánh giá về số lượng các nghiên cứu theo các hướng khác nhau đối với mạng MANET trong thời gian gần đây cho thấy, hướng nghiên cứu về định tuyến trong mạng MANET đứng đầu về số lượng các nghiên cứu đã được công bố Như vậy, có thể khẳng định, định tuyến trong mạng MANET

đã và đang là một vấn đề rất cần được quan tâm giải quyết trong những nghiên cứu cải tiến hiệu năng mạng MANET

Một giao thức định tuyến được tối ưu tốt sẽ đóng góp rất nhiều vào việc nâng cao hiệu năng mạng MANET trong điều kiện mạng MANET có các tài nguyên (băng thông, năng lượng nguồn nuôi, tốc độ xử lý, bộ nhớ,…) hạn chế hơn nhiều so với các mạng truyền thống Trong các nghiên cứu nhằm tối ưu hóa giao thức định tuyến dành cho mạng MANET, một trong những hướng nghiên cứu được quan tâm

và đã có nhiều kết quả quan trọng được công bố là áp dụng cơ chế hoạt động bầy đàn của các loại côn trùng như kiến, ong, mối, … để cải tiến mô hình lan truyền thông tin định tuyến của các giao thức định tuyến

Mục tiêu của đề tài này là nghiên cứu cơ chế chọn đường tối ưu thuật toán định tuyến Enhanced-ANT-AODV sử dụng cho mạng MANET Trong thuật toán này, kỹ thuật lan truyền tín hiệu sinh học (pheromone) của loài kiến trong quá trình hợp tác để tìm thức ăn được sử dụng để cải tiến kỹ thuật lan truyền thông tin định tuyến trong quá trình khám phá đường của giao thức định tuyến AODV thành giao thức định tuyến Enhanced-ANT-AODV Đối với loài kiến, trong quá trình tìm kiếm thức ăn, chúng sẽ xuất phát từ tổ rồi tản ra nhiều hướng Sau khi tìm thấy nguồn thức ăn, mỗi con kiến sẽ gửi tín hiệu sinh học cho các con khác trên đường trở về tổ

để các con kiến khác có được kiến thức về đường đi tới nguồn thức ăn Áp dụng kỹ thuật này của loài kiến, thay vì sử dụng gói yêu cầu đường RREQ trong giao thức AODV, giao thức Enhanced-ANT-AODV sẽ sử dụng gói Req.Ant để lan truyền yêu cầu tìm đường trong mạng từ nút nguồn Trong quá trình lan truyền gói Req.Ant, thông tin về các con đường bao gồm: độ tin cậy đầu cuối, độ tắc nghẽn, năng lượng còn lại của các nút trên đường và chiều dài của đường Sau khi nhận được gói ReqAnt, nút đích sẽ tính toán số lượng pheromone của mỗi con đường trên cơ sở thông tin được lưu trong gói ReqAnt và gửi lại gói trả lời đường Rep.Ant Đường có

số lượng pheromone cao nhất được lựa chọn để cài đặt vào bảng định tuyến và sử dụng để truyền các gói dữ liệu

Đề tài cũng sẽ thực hiện việc mô phỏng cơ chế hoạt động của kỹ thuật chọn đường tối ưu trong giao thức định tuyến Enhanced-Ant AODV và kỹ thuật chọn đường theo số chặng của giao thức định tuyến AODV trên phần mềm mô phỏng NS2 để kiểm nghiệm độ hiệu quả của kỹ thuật chọn đường tối ưu trong giao thức Enhanced-Ant AODV so với giao thức AODV

Luận văn có cấu trúc như sau: Chương 1 trình bày tổng quan về mạng MANET, vấn đề định tuyến trong mạng MANET và một số nghiên cứu tối ưu cơ

chế định tuyến dành cho mạng MANET Cơ chế chọn đường tối ưu theo yêu cầu chất lượng dịch vụ trong giao thức định tuyến Enhanced-ANT-AODV dành cho mạng MANET được trình bày chi tiết trong Chương 2 Kết quả của việc cài đặt, mô phỏng, so sánh đánh giá hiệu hiệu quả của giao thức định tuyến Enhanced-ANT-AODV với 3 giao thức định tuyến tiêu biểu cùng nhóm là DSR, AODV, và Enhanced-ANT-DSR được trình bày trong Chương 3 Nội dung tổng kết và hướng phát triển của đề tài được đưa ra trong phần kết luận

CHƯƠNG 1 TỔNG QUAN VỀ VẤN ĐỀ ĐỊNH TUYẾN TRONG MẠNG

MANET

1.1 Tổng quan về mạng MANET

1.1.1 Khái niệm mạng MANET

Mạng MANET (Mobile Ad hoc Network – MANET) [11] là mạng di động không dây hoạt động không cần dựa vào hạ tầng mạng cố định, trong đó hình trạng mạng được tạo thành bởi chính các nút mạng Chế độ “Ad hoc” của chuẩn IEEE 802.11 hoạt động theo mô hình này, mặc dù nó chỉ hỗ trợ để thiết lập một mạng đơn chặng Các mạng di động không dây kiểu không cấu trúc đã mở rộng khái niệm “Ad hoc” đa chặng theo nghĩa: một nút mạng có thể định tuyến và chuyển tiếp một gói tin nó nhận được từ một nút mạng khác Nói cách khác, con đường chuyển tiếp gói tin từ nút nguồn tới nút đích có thể chứa các nút trung gian khác Các nút trung gian

sẽ đọc thông tin trong phần header của các gói tin dữ liệu và chuyển tiếp chúng tới chặng kế tiếp trên một con đường đã được hình thành

Có thể hiểu một mạng MANET là một tập các nút không dây di động có thể trao đổi dữ liệu một cách linh động mà không cần sự hỗ trợ của trạm cơ sở cố định hoặc mạng có dây Mỗi nút di động có một phạm vi truyền giới hạn, do đó chúng cần sự trợ giúp của các nút lân cận để chuyển tiếp các gói dữ liệu Khi các gói tin dữ liệu từ nút nguồn cần gửi tới một nút đích mà nút đích không nằm trong phạm vi truyền của nút nguồn, cần có sự trợ giúp của các nút trung gian để chuyển tiếp gói tin từ nút nguồn tới nút đích Để thực hiện được công việc này, các nút mạng phải

sử dụng giao thức định tuyến phù hợp

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

Hình 1.1 là một ví dụ của mạng MANET Trong đó các nút trong mạng kết nối với nhau trong một khoảng thời gian để trao đổi thông tin Trong khi trao đổi thông tin, các nút này vẫn có thể di chuyển, do đó, mạng này phải đáp ứng được yêu cầu truyền dữ liệu trong khi hình trạng mạng có thể thay đổi liên tục Các nút mạng phải có cơ chế tự tổ chức thành một mạng để thiết lập các đường truyền dữ liệu mà không cần sự hỗ trợ từ bên ngoài Trong mô hình này, mỗi nút mạng có thể đóng vai trò là một nút đầu cuối để chạy các chương trình ứng dụng của người sử dụng hoặc là một bộ định tuyến để chuyển tiếp các gói tin cho các nút mạng khác

1.1.2 Đặc điểm của mạng MANET

Do mạng MANET là một mạng không dây hoạt động không cần sự hỗ trợ của hạ tầng mạng cơ sở trên cơ sở truyền thông đa chặng giữa các thiết bị di động vừa đóng vai trò là thiết bị đầu cuối, vừa đóng vai trò là bộ định tuyến nên mạng MANET có một số đặc điểm nổi bật sau [11]:

 Cấu trúc động: Do tính chất di chuyển ngẫu nhiên của các nút mạng nên cấu trúc của loại mạng này cũng thường xuyên thay đổi một cách ngẫu nhiên ở những thời điểm không xác định trước Trong khi thay đổi, cấu trúc của mạng MANET

có thêm hoặc mất đi các kết nối hai chiều hoặc kết nối một chiều

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

 Các nút mạng có tài nguyên hạn chế: Mỗi nút di động trong mạng có thể là một

bộ cảm biến, một điện thoại thông minh hoặc một máy tính xách tay Thông thường các thiết bị này có tài nguyên hạn chế so với các máy tính trong mạng có dây và không dây truyền thống về tốc độ xử lý, dung lượng bộ nhớ và năng lượng nguồn pin nuôi sống hoạt động của nút

 Độ bảo mật thấp ở mức độ vật lý: Mạng không dây di động thường chịu tác động về mặt vật lý từ các nguồn gây nguy hại về an ninh nhiều hơn so với mạng

có dây Về khía cạnh vật lý, các kỹ thuật gây mất an ninh và bảo mật trong mạng như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ triển khai trong mạng MANET hơn là trong mạng có dây truyền thống

Có thể thấy những đặc điểm này là các yếu tố ảnh hưởng rất nhiều đến hiệu năng của mạng MANET Để có thể triển khai được mạng MANET trong thực tế, các thiết kế mạng phải giải quyết được những thách thức sinh ra do những đặc điểm

đã nêu trên Những thách thức này gồm các vấn đề kỹ thuật như khả năng truyền dữ liệu và định tuyến hiệu quả khi kích thước mạng thay đổi; đảm bảo chất lượng dịch

vụ (QoS) cho các chương trình ứng dụng; cơ chế chuyển đổi một số dịch vụ từ mô hình client-server; tiết kiệm năng lượng pin để kéo dài thời gian hoạt động của các nút mạng riêng lẻ và của toàn mạng; đảm bảo an ninh mạng; khả năng hợp tác giữa các nút mạng và khả năng tự tổ chức của mạng

1.1.3 Ứng dụng của mạng MANET

Ngày nay, mạng MANET có nhiều những ứng dụng trong đời sống, kinh tế,

xã hội của con người Mô hình mạng này phù hợp đối với những tình huống cần triển khai hệ thống mạng một cách nhanh chóng, linh động và thường xuyên có sự

biến đổi trong cấu trúc mạng Chúng còn được ứng dụng rất nhiều trong các ứng dụng từ lĩnh vực thương mại tới các ứng dụng trong các hoạt động quân sự, ứng dụng trong các hoạt động khẩn cấp, ứng dụng trong gia đình, văn phòng và giáo dục, mạng giao thông và mạng cảm biến

Đối với các ứng dụng của mạng MANET trong thương mại, những người dùng có thể chia sẻ dữ liệu giữa các thiết bị di động trong một cuộc họp hay hội thảo mà không cần sự hỗ trợ của một cơ sở hạ tầng mạng cố định Các máy tính của những cá nhân có thể kết nối với nhau để tạo thành một mạng tạm thời phục vụ cho các ứng dụng truyền thông dữ liệu trong một nhóm những người dùng mà không cần sự hiện diện của các bộ thu phát tập trung Kết nối Internet từ một thiết bị của một người dùng cũng có thể được chia sẻ tới các thiết bị của những người dùng khác thông qua mạng MANET

Ứng dụng mạng MANET trong quân đội là một trong những ý tưởng được đưa ra ngay từ khi mạng MANET được phát triển Trong mô hình chiến đấu của quân đội trên chiến trường không có sự hỗ trợ về hạ tầng mạng cố định, mỗi người lính hoặc một phương tiện quân sự như xe tăng, máy bay, tàu chiến, tàu thủy đều có thể được kết nối và trao đổi thông tin tạm thời với nhau hoặc với trạm chỉ huy một cách linh động thông qua mạng MANET được hình thành bởi kết nối giữa các thiết

bị di động truyền thông không dây được gắn vào các phương tiện quân sự hay những người lính tham gia vào cuộc chiến

Tại các vùng bị thiên tai, thảm họa, có thể tất cả các phương tiện và hạ tầng truyền thông được xây dựng trước đó đều bị phá hủy hoàn toàn Mỗi chiếc xe của cảnh sát, cứu hỏa, cứu thương,… có thể được trang bị các thiết bị truyền nhận không dây để trở thành một thiết bị đầu cuối di động và là một phần của mạng MANET Mỗi nhân viên cứu hộ cũng có thể cũng mang theo một thiết bị đầu cuối

di động Các thiết bị đầu cuối này đều liên kết với nhau, hình thành nên một mạng MANET tạm thời nhằm trao đổi thông tin Cấu hình mạng thay đổi theo những thời điểm khác nhau Ngoài ra, các thiết bị đầu cuối di động không chỉ cung cấp chức

năng gửi và nhận thông tin mà còn có thể chuyển tiếp thông tin như vai trò như các

bộ định tuyến

Mỗi thiết bị thông minh trong gia đình, các điện thoại di động thông minh và máy tính của những người sử dụng trong văn phòng, trong môi trường trường học, các lớp học có thể đóng vai trò như một nút mạng trong một mạng MANET được hình thành tạm thời mà không cần sự hỗ trợ của hạ tầng mạng cố định nhằm phục

vụ cho các ứng dụng chia sẻ thông tin, truyền dữ liệu multimedia, quản lý ngôi nhà thông minh, quản lý lớp học thông minh,…

Trong vấn đề quản lý và hỗ trợ giao thông, mỗi phương tiện giao thông là một nút mạng di động trong mạng MANET được hình thành tạm thời trên một khu vực địa lý nhằm hỗ trợ trao đổi và quản lý các thông tin về tình trạng giao thông, hỗ trợ tìm đường tránh tắc nghẽn giao thông, theo dõi và quản lý các thiết bị tham gia giao thông, v.v

Cảm biến là các thiết bị nhỏ, phân tán, giá thành thấp, tiết kiệm năng lượng,

có khả năng truyền thông không dây và xử lý cục bộ Một mạng MANET có thể là một mạng cảm biến gồm các nút cảm biến Các nút này hợp tác với nhau để cùng thực hiện một nhiệm vụ cụ thể, ví dụ như: giám sát môi trường (không khí, đất, nước), theo dõi môi trường sống, hành vi, dân số của các loài động, thực vật, dò tìm động chấn, theo dõi tài nguyên, thực hiện trinh thám trong quân đội,

1.2 Một số chiến lược định tuyến trong mạng MANET

1.2.1 Phân loại các chiến lược định tuyến

Có nhiều cách để phân loại các chiến lược định tuyến cho mạng MANET theo các tiêu chí khác nhau [9] Các chiến lược định tuyến này được được liệt kê trong Bảng 1.1

Thời điểm định tuyến Định tuyến tìm đường trước và tìm

đường theo yêu cầu

Phương pháp truyền thông tin định tuyến Định tuyến cập nhật định kỳ và cập nhật

theo sự kiện

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

Bảng 1.1 Phân loại các chiến lược định tuyến của mạng MANET

1.2.2 Chiến lược định tuyến tìm đường trước và tìm đường theo yêu cầu

Kiểu định tuyến tìm đường trước còn được gọi là “định tuyến kích hoạt trước” hay “định tuyến điều khiển dạng bảng” Đối với kiểu định tuyến này, các con đường tới mọi đích được tìm ra trước khi có nhu cầu truyền dữ liệu tại mọi nút mạng Trạng thái của các liên kết được lưu trữ và cập nhật định kỳ trong bảng định tuyến

để phục vụ cho thuật toán tìm đường tại mỗi nút mạng Ưu điểm lớn nhất của kỹ thuật định tuyến này là khi có yêu cầu truyền dữ liệu, con đường truyền dữ liệu đã sẵn sàng tại các nút mạng và do đó không có độ trễ từ khi có yêu cầu truyền dữ liệu tới lúc tìm ra con đường để truyền dữ liệu Tuy nhiên các giao thức thuộc nhóm này cũng có nhược điểm là chúng tính toán và tìm ra những con đường tới mọi đích nên

có thể có một số con đường sẽ không bao giờ được sử dụng và kỹ thuật quảng bá bảng định tuyến định kỳ sẽ chiếm dụng băng thông mạng nhiều khi trạng thái các liên kết và hình trạng mạng thay đổi với tốc độ nhanh Có thể kể đến một số giao thức định tuyến tiêu biểu thuộc nhóm này là giao thức DSDV và giao thức WRP Đối với các giao thức định tuyến tìm đường theo yêu cầu, chỉ khi có nhu cầu

sử dụng đường truyền dữ liệu, các nút liên quan mới khởi tạo tiến trình tìm đường

và trao đổi thông tin định tuyến Phương pháp này có ưu điểm là tiết kiệm băng thông mạng dành cho tải định tuyến nhưng cũng có nhược điểm là quá trình tìm kiếm tuyến đường có thể gây ra một độ trễ truyền tin đáng kể Một số giao thức tiêu biểu đã được đề xuất thuộc nhóm này là DSR, AODV và TORA

1.2.3 Định tuyến cập nhật định kỳ và cập nhật theo sự kiện

Với các giao thức định tuyến trên cơ sở trạng thái liên kết (link state), để đảm bảo thông tin về trạng thái của các liên kết và hình trạng mạng được cập nhật kịp thời, thông tin định tuyến cần được quảng bá tới các nút mạng Trên cơ sở cách thức quảng bá thông tin định tuyến, ta có thể phân loại các chiến lược định tuyến thành hai nhóm là định tuyến cập nhật định kỳ và định tuyến cập nhật theo sự kiện Chiến lược định tuyến theo chu kỳ sẽ duy trì độ ổn định của mạng và quan trọng nhất là cho phép các nút mạng học được thông tin về hình trạng và trạng thái của toàn mạng Tuy nhiên, nếu sử dụng chu kỳ dài để cập nhật thông tin định tuyến, các nút mạng có thể chứa các thông tin định tuyến đã cũ và không chính xác Ngược lại, nếu chu kỳ cập nhật thông tin định tuyến là quá ngắn, sẽ có quá nhiều gói tin định tuyến được sinh ra và quảng bá trong mạng gây ra sự lãng phí về tài nguyên mạng Đối với chiến lược định tuyến theo sự kiện, khi có một sự kiện diễn ra trong mạng, những nút mạng chịu tác động trực tiếp của các sự kiện này mới quảng bá các gói tin cập nhật thông tin định tuyến Vì vậy, thông tin về những thay đổi của trạng thái mạng sẽ nhanh chóng được cập nhật tới các nút mạng Tuy nhiên, khi topo mạng thay đổi với tốc độ nhanh, sẽ có rất nhiều các gói tin quảng bá cập nhật định tuyến được sinh ra làm lãng phí băng thông mạng và biến động đối với các con đường truyền dữ liệu

1.2.4 Định tuyến phẳng và định tuyến phân cấp

Trong định tuyến phẳng, mọi nút trong mạng đều có cùng cấp độ và chức năng định tuyến Chiến lược định tuyến này tương đối đơn giản và hiệu quả đối với các mạng nhỏ Các giao thức AODV, DSDV, DSR là những giao thức điển hình sử dụng chiến lược định tuyến phẳng Đối với các mạng lớn, vấn đề gặp phải là lãng phí tài nguyên mạng dành cho việc xử lý và truyền các gói tin quảng bá thông tin định tuyến Chiến lược định tuyến phân cấp được đề xuất nhằm giải quyết vấn đề này

Trong chiến lược định tuyến phân cấp, các nút mạng được tổ chức một cách link động thành các vùng Mỗi vùng lại có thể chia tiếp thành các vùng con theo kiểu cây phân cấp Cấu trúc phân cấp này nhằm duy trì tính ổn định tương đối của hình trạng mạng Sự di chuyển của thay đổi trạng thái của một nút mạng chỉ tác động trong phạm vi của vùng quản lý nó Chỉ có thông tin điều khiển cấp cao mới được truyền giữa các vùng để giảm tải định tuyến trong mạng Mỗi nút mạng sẽ có thông tin đầy đủ về các nút mạng khác trong cùng vùng với nó bằng cách sử dụng

kỹ thuật định tuyến tìm đường trước Nếu nút đích và nút nguồn của một yêu cầu truyền dữ liệu thuộc hai vùng khác nhau, kỹ thuật định tuyến liên vùng theo yêu cầu

sẽ được sử dụng Định tuyến liên vùng thường hoạt động theo cơ chế định tuyến theo yêu cầu hoặc cơ chế kết hợp giữa định tuyến tìm đường trước và định tuyến theo yêu cầu Các giao thức tiêu biểu sử dụng chiến lược định tuyến phân cấp là HSR và CGSR

Hình 1.2 và Hình 1.3 minh họa cho các con đường được hình thành bởi các giao thức định tuyến hoạt động theo chiến lược định tuyến phẳng và định tuyến phân cấp

Hình 1.2 Đường truyền dữ liệu theo chiến lược định tuyến phẳng

Hình 1.3 Đường truyền dữ liệu theo chiến lược định tuyến phân cấp

1.2.5 Định tuyến với kỹ thuật tính toán tập trung và tính toán phân tán

Trong chiến lược định tuyến với kỹ thuật tính toán tập trung, mọi nút trong mạng sẽ duy trì thông tin đầy đủ về toàn bộ hình trạng mạng để có thể tự thực hiện các thuật toán tìm đường khi cần thiết Các giao thức định tuyến sử dụng chiến lược định tuyến này còn được gọi là các giao thức định tuyến kiểu trạng thái đường liên kết Giao thức OLSR là một giao thức định tuyến kiểu trạng thái đường liên kết tiêu biểu

Trong chiến lược định tuyến với kỹ thuật tính toán phân tán, mọi nút mạng chỉ duy trì thông tin cục bộ về hình trạng mạng Khi có nhu cầu tìm đường, nhiều nút mạng sẽ cùng tham gia vào tiến trình tìm đường Chiến lược định tuyến này còn được gọi là định tuyến kiểu véc tơ khoảng cách AODV và DSDV là các giao thức định tuyến tiêu biểu sử dụng chiến lược định tuyến này

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

Có một vài giao thức định tuyến đưa thông tin về toàn bộ con đường vào trong header của các gói tin dữ liệu để các nút trung gian có thể chuyển tiếp những gói tin này theo các thông tin định tuyến mà nó đọc được trong phần header Chiến lược định tuyến này được gọi là định tuyến nguồn Ưu điểm của chiến lược định tuyến này là các nút trung gian không cần duy trì thông tin định tuyến cập nhật để tìm đường cho các gói tin chúng chuyển tiếp vì chính trong các gói tin dữ liệu đã chứa

thông tin phục vụ cho các quyết định định tuyến Tuy nhiên, chiến lược này lại có nhược điểm là làm tăng kích thước của các gói tin dữ liệu, đặc biệt với các con đường dài và các mạng có kích thước lớn dẫn đến việc lãng phí băng thông của mạng ad hoc Giao thức DSR là một trong những giao thức định tuyến nguồn tiêu biểu Hình 1.4 minh họa cơ chế chuyển tiếp gói tin của giao thức định tuyến nguồn

Hình 1.4 Truyền dữ liệu theo chiến lược định tuyến nguồn

Trong chiến lược định tuyến từng chặng, con đường tới một nút đích được phân bố trong các “chặng kế tiếp” của các nút thuộc con đường này Khi một nút nhận được một gói tin cần truyền tới một đích xác định, nó sẽ chuyển tiếp gói tin này tới chặng kế tiếp tương ứng trên con đường Vì mỗi nút mạng không có thông tin đầy đủ về toàn bộ các liên kết trong mạng nên thuật toán định tuyến của các giao thức sử dụng chiến lược định tuyến này phải đảm bảo không chọn các con đường gây ra định tuyến lặp Giao thức AODV là một trong những giao thức tiêu biểu sử dụng chiến lược định tuyến từng chặng Hình 1.5 minh họa kỹ thuật chuyển tiếp gói tin của giao thức hoạt động theo chiến lược định tuyến từng chặng

Hình 1.5 Truyền dữ liệu theo chiến lược định tuyến từng chặng

1.2.7 Định tuyến đơn đường và định tuyến đa đường

Đối với các giao thức định tuyến đơn đường, chỉ có tối đa một con đường tối

ưu theo độ đo định tuyến của chúng được cài đặt vào bảng định tuyến sau mỗi tiến trình tìm đường mặc dù chúng có thể nhận được thông tin về nhiều 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

1.3 Một số nghiên cứu tối ưu hiệu năng định tuyến trong mạng MANET

Tóm tắt về các công trình nghiên cứu đã được thực hiện về các kỹ thuật tối

ưu hóa chọn đường dựa trên “trí tuệ bầy đàn” trong mạng MANET [1, 6, 10] được

trình bày trong phần này

Các tác giả Zhang và Zhou đã nghiên cứu về các khía cạnh khác nhau của giao thức định tuyến ACR trong đó việc lựa chọn chặng kế tiếp trên con đường tới đích được thực hiện trên cơ sở “tín hiệu sinh học” và “suy luận” của mạng Mỗi nút duy trì một bảng “tín hiệu sinh học” và bảng “suy luận” Trong bảng “tín hiệu sinh học”, mỗi bản ghi của bảng chứa thông tin kỳ vọng để chọn một nút làm chặng kế tiếp hướng tới đích Trong bảng “suy luận”, mỗi bản ghi chứa các tiêu chí như vị trí, năng lượng, số bước nhảy, độ trễ, được sử dụng cho nội suy Xác suất được sử

dụng để chọn chặng kế tiếp Nút có xác suất lớn nhất trong số các nút liền kề của nút hiện tại sẽ được chọn làm chặng kế tiếp Quá trình hấp thụ được sử dụng để tăng cường “tín hiệu sinh học” Về bản chất, đây là quá trình chọn một đường cụ thể để thu hút lưu lượng truy cập nhằm định tuyến tốt hơn Quá trình phân rã được sử dụng

để làm giảm bớt “tín hiệu sinh học” dẫn đến giảm xác suất chọn một con đường cụ thể nhằm tránh định tuyến qua các liên kết có chất lượng kém

Yadav và các cộng sự đã đề xuất một thuật toán định tuyến cải tiến dựa trên

kỹ thuật tối ưu hóa ACO có tên gọi là I-ACO Thuật toán định tuyến I-ACO thực hiện định tuyến với thông tin “tín hiệu sinh học” cập nhật bằng cách sử dụng hai mô hình là mô hình xác suất chuyển tiếp và mô hình xác suất định hướng Xác suất chuyển tiếp giúp tìm vị trí của nút tiếp theo trong quá trình di chuyển của gói tin Xác suất định hướng giúp tìm ra nút tiếp theo theo hướng đích Kỹ thuật này làm giảm độ trễ đầu cuối khi truyền gói tin và tăng tỷ lệ phân phối gói dữ liệu nhưng ngược lại là có chi phí định tuyến và mức tiêu thụ năng lượng cao do thiếu cơ chế quản lý năng lượng

Abdel-Moniem và các cộng sự đã đề xuất phương pháp định tuyến dựa trên thuật toán định tuyến MRAA Trong thuật toán này, giao thức AODV tìm đường theo yêu cầu và thuật toán tối ưu ACO sẽ chủ động tìm trước các đường giữa các cặp nút Phương pháp này làm giảm độ trễ đầu cuối trong quá trình phân phối gói

dữ liệu Các gói được gửi đến đích trong thời gian ngắn hơn với chi phí thấp hơn do các đường thay thế được sử dụng để phân phối dữ liệu Tuy nhiên việc lưu trữ và duy trì các đường dự phòng trên các nút di động là một công việc không đơn giản

Các tác giả Fahmy, Albayrak và Zengin đã nghiên cứu và đề xuất thuật toán định tuyến PEEBR theo cơ chế mô phỏng hoạt động của bầy ong nhằm dự đoán lượng năng lượng sẽ được tiêu thụ bởi tất cả các nút dọc theo đường đi Trong đó, thuật toán tối ưu sử dụng hai tác tử được đặt tên là “ong do thám” và “ong kiếm ăn” Kỹ thuật định tuyến này tập trung vào việc xác định đường tối ưu dựa trên giá trị mức độ tốt của đường Kỹ thuật này được xây dựng từ ý tưởng mô phỏng quá

trình tìm kiếm thức ăn của loài ong dựa trên hai thông số quan trọng là: lượng năng lượng tiêu thụ của mỗi nút dọc theo một con đường duy nhất và độ trễ đầu cuối Mức độ tốt của đường được xây dựng từ hai tham số này Thực nghiệm đã được thực hiện để đánh giá thuật toán định tuyến này cho thấy, kỹ thuật này là kỹ thuật tiêu tốn ít nhất năng lượng pin của các nút di động cho việc khám phá, đánh giá và lựa chọn đường và giảm độ trễ đầu cuối khi truyền gói tin Tuy nhiên, kỹ thuật này không thể cho kết quả tốt trong trường hợp mạng có cấu trúc thay đổi thường xuyên

Nghiên cứu của Kiran Manjappa và các cộng sự đã đề xuất một cơ chế định tuyến cho MANET dựa trên cơ chế xây dựng đồi của loài mối với tên gọi là MA-Termite Kỹ thuật này mô phỏng cơ chế phối hợp của những con mối trong quá trình xây dựng tổ để gửi gói tin đến đích Các nút di động của mạng MANET được biểu diễn như một tổ mối Nó lưu trữ các “tín hiệu sinh học” hướng tới các nút đích trong bảng “tín hiệu sinh học” Nút có số lượng “tín hiệu sinh học” đích cao nhất được xác định là chặng kế tiếp Sự hấp thụ và phân rã “tín hiệu sinh học” trên một liên kết tỷ lệ với khoảng cách giữa các nút của liên kết đó Những nút láng giềng có tính di động cao tạo ra các “tín hiệu sinh học” có độ phân rã cao Ngược lại, đối với các nút láng giềng có tính di động thấp, độ phân rã “tín hiệu sinh học” sẽ thấp Kiểm nghiệm bằng mô phỏng từ nghiên cứu này cho thấy, đường được cho có chi phí định tuyến và độ ổn định tốt hơn Tuy nhiên, giao thức này đòi hỏi cơ chế làm việc liên tầng nên nó sẽ phức tạp hơn so với các giao thức đơn tầng khác

Tác giả Srinivasan và các cộng sự đã đề xuất giao thức định tuyến BFBR mô phỏng hành vi của đàn chim cho các mạng ad hoc di động có tính di động cao Giao thức có hai phần: một phần làm nhiệm vụ tìm kiếm đụng độ được sử dụng để khám phá đường và phần còn lại là định tuyến chuyển tiếp hướng được sử dụng để bảo trì đường Khác với cơ chế quảng bá định tuyến thông thường, giao thức BFBR tiết kiệm băng thông bằng cách tránh việc di chuyển qua các liên kết không cần thiết

Cơ chế tìm kiếm đụng độ giảm số lần duyệt liên kết trong quá trình khám phá đường Cơ chế định tuyến chuyển tiếp hướng giúp duy trì môi trường cục bộ xung

mỗi nút để đảm bảo kết nối của đường Do đó, nó làm giảm chi phí định tuyến Tuy nhiên, cơ chế bảo trì đường khá phức tạp trong giao thức BFBR

Nghiên cứu của Dhurandher đã đề xuất thuật toán P2PBA hỗ trợ việc tìm kiếm tệp ngang hàng (P2P) một cách hiệu quả trong mạng MANET Thuật toán này

mô phỏng việc sử dụng trí thông minh bầy đàn dựa trên hành vi kiếm ăn của ong mật Trong đề xuất này, một tệp được chia nhỏ thành các gói Các gói này sau đó được phân phối đến một nhóm các nút có chọn lọc Tuy nhiên, trong thuật toán này, các mục tiêu tiết kiệm năng lượng, bảo mật và tính không đồng nhất của nút mạng vẫn chưa được xem xét

Các tác giả Rao và Singh đã đề xuất cải tiến giao thức định tuyến AODV với

n đường dự phòng (AODV nth BR) Giao thức cung cấp cho nút nguồn nhiều hơn một dự phòng trong trường hợp mạng bị lỗi liên kết Giao thứ này là một phiên bản cải tiến của giao thức định tuyến AODV nhằm phân phối các gói dữ liệu từ nguồn đến đích qua nhiều đường Việc lựa chọn các nút để định tuyến được thực hiện hiệu quả trên cơ sở khoảng cách và năng lượng có sẵn với các nút Trong giao thức này, mọi nút đều được kiểm tra năng lượng truyền của nó và với sự trợ giúp của vectơ khoảng cách, nút gần nhất tiếp theo sẽ được tìm ra Nút gần nhất được kiểm tra lại xem nó có đủ năng lượng để truyền hay không Quá trình này tiếp tục cho đến khi tìm thấy một nút thích hợp để truyền

Nghiên cứu của Misra và Rajesh đã đề xuất giao thức định tuyến BFIRP trên

cơ sở năng lượng và vị trí Cơ chế hoạt động của giao thức này dựa trên ý tưởng mô phỏng quá trình bay của loài chim Quá trình chuyển tiếp các gói dữ liệu đến đích được thực hiện trên cơ xem xét năng lượng của các nút và khoảng cách từ mỗi nút

từ đích Ngoài ra giao thức này còn xét tới độ gần của nút với đường tròn kết nối nút trung gian và nút đích Tuy nhiên, vấn đề băng thông của liên kết và đường đầu cuối không được xét đến trong giao thức này

Singh và các cộng sự đã đề xuất giao thức AODV-R Đây là một giao thức định tuyến dựa trên cơ chế tối ưu đường đi của đàn kiến để tìm đường đi ngắn nhất

bằng cách loại bỏ tắc nghẽn AODV-R sử dụng thuật toán ACO để cải thiện thuật toán đường đi ngắn nhất Cơ chế chọn đường tin cậy nhất của giao thức AODV-R làm giảm khả năng đứt gãy liên kết khi thay đổi cấu trúc mạng Tuy nhiên, kỹ thuật này không đáp ứng yêu cầu của định tuyến theo chất lượng dịch vụ

Nghiên cứu của các tác giả Al-Ani và Seitz đã đề xuất giao thức định tuyến QoRA nhận biết chất lượng dịch vụ dựa trên cơ chế tối ưu đường đi của đàn kiến Giao thức này tính toán tham số QoS cục bộ và tránh tắc nghẽn trong quá trình truyền dữ liệu với sự trợ giúp của hai thành phần Thành phần thứ nhất là thực thể QoRA chạy trên mỗi nút để xác định các con đường phù hợp theo các yêu cầu QoS xác định Thành phần thứ hai là thực thể SNMP bao gồm tác nhân giao thức quản trị mạng SNMP và cơ sở dữ liệu MIB Thực thể SNMP cục bộ lấy thông tin cần thiết cho mỗi nút Dựa trên những thông tin này, nút mạng sẽ tính toán các tham số QoS nhằm tránh tắc nghẽn trong quá trình chuyển tiếp gói dữ liệu Tuy nhiên cơ chế định tuyến này làm phát sinh trễ đầu cuối khi truyền gói tin

Nghiên cứu của các tác giả Chatterjee và Das đề xuất một giao thức định tuyến theo yêu cầu kết hợp giữa thuật toán ACO với giao thức định tuyến DSR có tên là Enhanced Ant DSR Trong đó, giao thức này sử dụng thuật toán ACO để chọn đường tối ưu Số lượng “tín hiệu sinh học” của một con đường được tính toán dựa trên độ đo liên kết LM, độ đo tắc nghẽn CM và số chặng Khi một nút trung gian chuyển tiếp yêu cầu tìm đường, nó sẽ cập nhật các giá trị LM, CM và số chặng Nút gửi nhận thông tin (độ dài, mức tắc nghẽn và mức kết nối) của một con đường

từ gói trả lời đường Nó tính toán giá trị “tín hiệu sinh học” của các đường và chọn đường có giá trị “tín hiệu sinh học” cao nhất để truyền dữ liệu Giao thức này có thể đáp ứng hầu hết các yêu cầu chất lượng dịch vụ cơ bản Tuy nhiên vì nó được phát triển từ giao thức DSR nên kích thước phần thông tin điều khiển của các gói tin sẽ tăng đối với các đường dài gây ra chi phí định tuyến trong mạng

1.4 Tổng kết Chương 1

Mạng MANET có những đặc điểm khác biệt rõ ràng so với mạng không dây truyền thống thể hiện ở cấu trúc động, chất lượng liên kết và năng lượng pin của các nút mạng hạn chế, độ bảo mật không cao về mặt vật lý Mạng MANET đã có nhiều ứng dụng trong đời sống, kinh tế, xã hội của con người

Do các tính chất khác biệt của mạng MANET so với mạng truyền thống, có nhiều thách thức cần được giải quyết từ các nhà nghiên cứu và triển khai công nghệ mạng này Để góp phần giải quyết những vấn đề là thách thức của mạng MANET, giao thức định tuyến sử dụng trong mạng này cần đảm bảo được yêu cầu tối thiểu hoá tải điều khiển và tải xử lý, hỗ trợ định tuyến đa chặng, đáp ứng những thay đổi

về topo mạng và ngăn chặn định tuyến lặp

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

Đã có nhiều nghiên cứu được thiết kế và đề xuất để tối ưu hiệu năng định tuyến dành cho mạng MANET các yêu cầu QoS khác nhau Tuy nhiên, không có giao thức nào trong các giao thức định tuyến này sử dụng cả 4 tham số (cường độ tín hiệu nhận, năng lượng còn lại, độ tắc nghẽn, số chặng) trong thuật toán định tuyến từ nguồn đến đích Do đó, một kỹ thuật chọn đường tối ưu cần được phát triển trong đó sử dụng cả 4 tham số này để lựa chọn đường đi từ nguồn đến đích Giao thức định tuyến Enhanced-ANT-AODV [12] là một giao thức định tuyến có

cơ chế chọn đường tối ưu theo cả 4 tham số QoS này Các chương tiếp theo của luận văn tập trung vào việc nghiên cứu cơ chế hoạt động, thuật toán định tuyến và

mô phỏng, đánh giá hiệu năng của giao thức định tuyến Enhanced-ANT-AODV

CHƯƠNG 2 CƠ CHẾ CHỌN ĐƯỜNG TỐI ƯU TRONG GIAO THỨC

ĐỊNH TUYẾN ENHANCED-ANT AODV

2.1 Bài toán chọn đường tối ưu trong mạng MANET

Do mạng MANET có tính chất động nên bài toán định tuyến trong mạng MANET là bài toán khó có lời giải tối ưu Khi xảy ra hiện tượng nút mạng bị lỗi và liên kết giữa các nút bị đứt, có thể làm mất tài nguyên mạng Một vấn đề cơ bản cần giải quyết trong mạng MANET là lựa chọn đường tối ưu giữa hai nút bất kỳ Đã có một số giao thức tiêu biểu được đề xuất để định tuyến các gói dữ liệu trong mạng MANET như AODV [8] và DSR [4] Các giao thức định tuyến này thường sử dụng

số chặng hoặc đường ngắn nhất làm độ đo chính để chọn đường

Hình 2.1 Minh họa mạng MANET chiến thuật

Việc định tuyến trở nên phức tạp và có các yêu cầu đặc biệt hơn trong các mạng MANET phục vụ cho quân đội được sử dụng trong chiến trường (mạng MANET chiến thuật) Trong mạng MANET chiến thuật, dữ liệu đa phương tiện cần được truyền đi Do đó, nó đòi hỏi phải có sự hỗ trợ Chất lượng Dịch vụ (QoS) Hình 2.1 cho thấy một tình huống trong mạng MANET chiến thuật, trong đó dữ liệu video và âm thanh sẽ được mỗi người lính truyền tới trung tâm chỉ huy và những người lính khác Để đảm bảo QoS, một số yếu tố cần được xem xét về mức độ ảnh hưởng đến chất lượng của con đường truyền dữ liệu được chọn Giá trị các thông số

cường độ tín hiệu nhận được, độ tắc nghẽn, số chặng của đường truyền và năng lượng còn lại của các nút là những yếu tố quan trọng để chọn đường tối ưu từ nguồn đến đích trong kịch bản nêu trên

Cường độ tín hiệu nhận được cần được sử dụng để chọn đường có độ tin cậy cao hơn Cấu trúc liên kết mạng thay đổi rất nhanh trong mạng đặc biệt chiến thuật Nếu một đường được chọn có các nút trung gian nhận được cường độ tín hiệu nhận nhỏ thì khi có những chuyển động giữa các nút trung gian trên đường, liên kết thuộc đường được chọn hoàn toàn có thể bị phá vỡ

Trong mạng MANET chiến thuật, ngoại trừ nút gateway và trung tâm chỉ huy, tất cả các nút còn lại đều được nuôi bằng nguồn pin Do đó, năng lượng là một vấn đề quan trọng ảnh hưởng tới sự tồn tại của mạng Nếu đường truyền dữ liệu chứa các nút có ít năng lượng dữ trữ, pin của các nút đó sẽ cạn kiệt và đường này sẽ

bị phá vỡ khi có một nút hết năng lượng pin Vì vậy, năng lượng còn lại của các nút trung gian cũng là một yếu tố quan trọng để lựa chọn đường đi từ nguồn đến đích

Vì những người lính trong mạng MANET chiến thuật sẽ cần truyền dữ liệu video và âm thanh, nên đường truyền dữ liệu được chọn cần có độ tắc nghẽn thấp Nếu đường truyền chứa các liên kết bị tắc nghẽn, độ trễ đầu cuối sẽ tăng lên, điều này không tốt cho việc truyền tải video và âm thanh theo thời gian thực Do đó, sự tắc nghẽn của các liên kết trong đường dẫn từ nguồn đến đích là một yếu tố quan trọng cho việc lựa chọn đường dẫn

Truyền thông từ nút nguồn tới đích trong mạng MANET chiến thuật là truyền thông đa chặng thông qua các nút trung gian Nếu đường truyền dữ liệu chứa nhiều chặng trung gian, hiệu suất chuyển tiếp dữ liệu của đường sẽ kém đi Do đó, số chặng của đường từ nút nguồn đến nút đích là một yếu tố quan trọng để chọn đường

Đã có nhiều giao thức định tuyến [1, 3, 7] được thiết kế và đề xuất để đáp ứng các yêu cầu QoS khác nhau Một số thuật toán định tuyến tối ưu đường tiêu biểu đã được đề xuất bao gồm: định tuyến theo đàn kiến (ACR), định tuyến đàn

kiến cải tiến tối ưu (I-ACO), thuật toán định tuyến đa đường dựa trên AODV và tối

ưu theo loài kiến (ACO), định tuyến tối ưu theo loài ong, định tuyến theo cơ chế xây dựng đồi của mối, định tuyến theo hành vi của loài chim (BFBR), định tuyến ngang hàng theo loài ong (P2PBA), định tuyến cải tiến AODV với n đường dự phòng (AODV nthBR), định tuyến theo cơ chế bay của loài chim (BFIRP), định tuyến AODV-R, Định tuyến nhận biết QoS (QoRA) và định tuyến Enhanced-ANT-DSR Tuy nhiên, không có giao thức nào trong các giao thức định tuyến này sử dụng cả 4 tham số (cường độ tín hiệu nhận, năng lượng còn lại, độ tắc nghẽn, số chặng) trong thuật toán định tuyến từ nguồn đến đích Do đó, một kỹ thuật chọn đường tối ưu cần được phát triển trong đó sử dụng cả 4 tham số này để lựa chọn đường đi từ nguồn đến đích

Hình 2.2 đưa ra một ví dụ về tiến trình chọn đường Trong ví dụ này, nút nguồn 1 muốn gửi dữ liệu đến nút đích 5 Nếu trong bảng định tuyến của nút 1 chưa

có đường đi tới nút 5, nó sẽ bắt đầu quá trình khám phá đường Quá trình khám phá đường của các thuật toán của các giao thức định tuyến khác nhau sẽ theo các cơ chế quảng bá tràn ngập khác nhau trên cơ sở các tham số chọn đường mà chúng sử dụng Sau khi đã chọn đường, các gói dữ liệu được gửi từ 1 đến 5 thông qua đường

đã chọn Vấn đề chung của tất cả các giao thức đã trình bày là không có giao thức nào xem xét tất cả bốn yếu tố quan trọng đồng thời là như khoảng cách, mức độ kết nối, năng lượng và tắc nghẽn để lựa chọn đường tối ưu cho hiệu năng định tuyến định tuyến mạnh mẽ và hiệu quả hơn

Hình 2.2 Ví dụ về tiến trình chọn đường

Quá trình khám phá tuyến đường của giao thức Enhanced-ANT-DSR [2] như được hiển thị trong Hình 2.2 bắt đầu bằng việc gửi các gói yêu cầu tìm đường Req.Ant qua tất cả các liên kết có sẵn được lưu trữ trong bộ nhớ đệm (cache) RSSM của nút gửi Mỗi nút trung gian sẽ kiểm tra bộ nhớ đệm chứa đường đi của nó Nếu

nó tìm thấy nhiều hơn một đường, nó sẽ chọn đường có số lượng “tín hiệu sinh học” cao nhất Đường này sau đó sẽ được thêm vào ngăn xếp Địa chỉ nút trung gian INA của gói trả lời đường Req Ant và các trường số chặng CM, LM cũng được cập nhật theo thông tin về đường được chọn Nút trung gian có đường đi tới đích sau đó sẽ gửi gói Req.Ant tới nút nguồn để trả lời yêu cầu tìm đường Nếu nút trung gian không tìm thấy đường tới đích, nó sẽ đọc trường INA trong gói Req.Ant Nếu địa chỉ của nó không có trong INA, nó sẽ lưu bản sao của gói tin này trong bộ nhớ đệm của mình Sau đó, nó thiết lập lại giá trị bộ đếm thời gian cho thời gian tồn tại của gói trùng lặp này và cập nhật lại giá trị các trường Hop Count, CM và LM của gói Tiếp theo, nó thêm địa chỉ của chính nó vào trường INA của Req.Ant Khi phát hiện mạng ở chế độ mật độ nút thấp, nút này sẽ chuyển tiếp gói tin Req.Ant đến tất cả

các liên kết với nó ngoại trừ liên kết mà gói Req.Ant đã đi qua (tương tự như quá trình với khám phá đường của DSR) Trong mạng chế độ mạng mật độ cao, nút trung gian sẽ chọn liên kết giá trị của tỉ số giữa cường độ tín hiệu nhận RSMM với

độ tắc nghẽn phi tuyến NNCM (SSMM/NNCM) lớn nhất và chỉ chuyển tiếp gói tin qua liên kết này Ví dụ trong Hình 2 là minh họa cho chế độ mật độ nút thấp Khi nút 1 muốn gửi gói tin đến nút 5, nút 1 không có đường đi đến nút 5 trong bộ nhớ đệm đường của nó Vì vậy, nó quảng bá gói Req.Ant thông qua các liên kết 1->2 và 1->6 Cả nút 2 và 6 sau đó sẽ tìm đường tới nút đích 5 trong bộ nhớ đệm đường của chúng Giả sử, nút 2 và 6 đều không tìm thấy đường trong bộ đệm đường của mình

Do đó, chúng sẽ cập nhật giá trị các trường số chặng, CM và LM của gói Req.Ant

và tiếp tục quảng bá gói Req.Ant qua tất cả các liên kết được lưu trữ trong bộ đệm RSSM của mình Quá trình này tiếp tục cho đến khi gói Req.Ant đến đích Khi nhận được gói Req.Ant, nút đích 5 cập nhật bộ đệm đường của nó và gửi lại gói Rep.Ant thông qua các đường 5->4->3->2->1 và 5->8->7->6->1 Khi nút nguồn 1 nhận được các gói Req.Ant qua các đường này, nó sẽ chọn đường có số lượng “tín hiệu sinh học” cao nhất Trong tình huống đường 1->2->3->4->5 là đường có số lượng “tín hiệu sinh học” cao hơn đường 1->6->7->8->5, nút 1 chọn đường 1->2->3->4->5 để chuyển tiếp các gói dữ liệu tới nút 5

Với mô tả về cơ chế chọn đường của giao thức Enhanced-ANT-DSR ở trên, vấn đề năng lượng còn lại của các nút chưa được xem xét tới Một tham số QoS quan trọng là “năng lượng” không tham gia vào cơ chế chọn đường Ngoài ra, toàn

bộ thông tin về con đường được đưa vào phần header của các gói tin làm tăng kích thước của gói Khi giao thức AODV được để thay thế cho giao thức DSR, kích thước của các gói tin sẽ được giảm xuống do thông tin về các con đường được lưu trữ trong bảng định tuyến của mỗi nút Do đó, các gói dữ liệu không nhất thiết phải chứa thông tin về toàn bộ tuyến đường Đối với giao thức DSR gốc, vấn đề định tuyến lặp sẽ làm phát sinh chi phí định tuyến để xử lý Đối với giao thức AODV, với kỹ thuật sử dụng số thứ tự đích để đánh dấu độ mới của đường nên vấn đề định tuyến lặp sẽ không còn tồn tại

2.2 Mô tả hoạt động của giao thức

Nghiên cứu trong [12] đề xuất giao thức định tuyến Enhanced-ANT-AODV nhằm mục đích đưa nhiều tham số QoS quan trọng hơn vào thuật toán định tuyến Giao thức này xây dựng đường tối ưu từ nguồn đến đích bằng cách xem xét cả 4 tham số QoS của đường bao gồm: chất lượng liên kết, độ tắc nghẽn, năng lượng còn lại và số chặng Mỗi nút lưu trữ một số thông tin trong bảng định tuyến của nó

Một nút trung gian cần duy trì một mức năng lượng còn lại để bảo đảm thực hiện được các công việc định tuyến trong mạng Khi năng lượng còn lại của bất kỳ một nút nào nhỏ hơn hoặc bằng năng lượng ngưỡng, nó sẽ không được coi là nút trung gian Tương tự, có một ngưỡng cho cường độ tín hiệu nhận được để coi một

số nút là chặng kế tiếp Hai giá trị ngưỡng được sử dụng trong giao thức này là:

• SIGNAL_THR: Giá trị ngưỡng cường độ tín hiệu nhận Khi một nút nhận tín hiệu có cường độ nhỏ hơn ngưỡng này, nó sẽ không nhận tín hiệu đó

• RE_THR: Giá trị ngưỡng năng lượng còn lại Khi một nút có năng lượng còn lại nhỏ hơn ngưỡng này, nó sẽ không được chấp nhận

Mỗi nút tính toán giá trị số lượng “tín hiệu sinh học” của mình trên cơ sở giá trị của độ đo cường độ tín hiệu đã nhận (RSSM), độ đo tắc nghẽn (CM), độ đo năng lượng còn lại (REM) và độ đo số chặng (HCM) theo Công thức (1) và lưu trữ giá trị ngày trong bảng định tuyến của mình

Khi một nút muốn gửi các gói dữ liệu đến đích, trước tiên nó sẽ kiểm tra xem

nó có đường đi đến đích hay không Nếu có, các gói dữ liệu được gửi đi theo con đường này Nếu không, nút nguồn sẽ phát gói yêu cầu định tuyến REQ-ANT theo Thuật toán 1 để thực hiện quá trình gửi yêu cầu tìm đường

Khi nhận được gói REQ_ANT, mỗi nút lân cận áp dụng Thuật toán 2 cho quá trình chuyển tiếp yêu cầu định tuyến Nó tạo ra một liên kết ngược đến nút nguồn khởi tạo gói REQ_ANT Sau đó, nó tính toán số lượng “tín hiệu sinh học” và cập nhật bảng định tuyến Nếu năng lượng dư của nút lớn hơn ngưỡng, nó sẽ phát lại

gói REQ_ANT Quá trình này được thực hiện lần lượt bởi tất cả các nút trung gian cho đến khi gói REQ_ANT đến đích

Khi nút đích nhận được REQ_ANT, nó sẽ áp dụng Thuật toán 3 để nhận yêu cầu tìm đường Nút đích sẽ cập nhật bảng định tuyến của mình về con đường đi tới nút nguồn Sau đó, nó thực hiện Thuật toán 4 để thực hiện việc gửi gói trả lời định tuyến REP_ANT Trong thuật toán này, nút đích sẽ đợi một khoảng thời gian nhất định để nhận các gói REQ_ANT khởi đầu từ nút nguồn từ qua tất cả các đường và chọn đường có số lượng “tín hiệu sinh học” cao nhất Sau đó, nó sẽ gửi gói REP_ANT tới nút lân cận trên con đường quay ngược trở về nút nguồn đã được chọn

Khi nhận được gói trả lời đường REP_ANT, nút trung gian áp dụng Thuật toán 5 để thực hiện quá trình chuyển tiếp gói REP_ANT Trong thuật toán này, nút trung gian sẽ cập nhật đường đi tới nút đích vào bảng định tuyến của mình Sau đó,

nó chuyển tiếp gói REP_ANT sang chặng kế tiếp để gửi gói này về cho nút nguồn khởi tạo gói yêu cầu tìm đường REQ_ANT Quá trình này tiếp tục cho đến khi gói REP_ANT đến được nút nguồn

Khi gói REP_ANT đến nút nguồn khởi tạo gói REQ_ANT, nút nguồn áp dụng Thuật toán 6 để thực hiện quá trình nhận thông tin trả lời đường Nó cập nhật bảng định tuyến với một con đường mới đến nút đích Cuối cùng nút nguồn sẽ gửi các gói dữ liệu qua con đường đã được thiết lập

2.3 Các độ đo định tuyến

2.3.1 Độ đo “Tín hiệu sinh học” của liên kết

Trong quá trình chọn chặng kế tiếp để chuyển tiếp yêu cầu tìm đường, nút gần nhất theo số chặng không phải lúc nào cũng là nút thích hợp nhất vì nút này có thể đang rơi vào tình trạng tắc nghẽn hoặc thiếu năng lượng còn lại để duy trì hoạt động Do đó, giao thức Enhanced-ANT-AODV căn cứ vào giá trị của “tín hiệu sinh

học” để chọn chặng kế tiếp Giả sử, tồn tại một liên kết từ nút i đến nút j Giá trị “tín hiệu sinh học” của liên kết PCij được xác định theo Công thức (1)

trong đó, Rn ij là cường độ tín hiệu nút j nhận được từ nút i, En j là năng lượng

còn lại của nút j, Cn j là độ tắc nghẽn tại nút j, Hn ij là số chặng mà yêu cầu tìm

đường đã truyền từ nút nguồn đến nút j qua nút i

2.3.2 Độ đo cường độ tín hiệu nhận (RSSM)

Cường độ tín hiệu nhận được của mỗi liên kết xác định độ tin cậy của liên kết Giá trị này có thể được sử dụng để dự đoán sự kiện liên kết bị đứt trong quá

trình truyền dữ liệu Cường độ tín hiệu nhận được RSS ix từ nút lân cận i ở khoảng cách x được xác định theo Công thức (2)

Trong đó, G r là hệ số của anten thu, R là bán kính hoạt động của anten thu

Tùy thuộc vào giá trị ngưỡng T j và giá trị RSS ix của liên kết (i, j), giá trị của độ đo cường độ tín hiệu nhận RSSM tại nút j đối với liên kết (i, j) bằng 0 nếu hoặc bằng (

) nếu

2.3.3 Độ đo tắc nghẽn (CM)

Độ tắc nghẽn giữa các nút có thể được xác định bằng mức độ sử dụng bộ đệm gói tin Độ dài của bộ đệm hàng đợi gói tin là số gói tin hiện có trong hàng đợi của

mỗi nút Giá trị này sẽ thay đổi khi số lượng gói tin đi vào và đi ra bộ đệm hàng đợi gói tin thay đổi Trong giao thức Enhanced-ANT-AODV, hàng đợi Drop Tail được

sử dụng để xác định độ tắc nghẽn tại một nút Khi số lượng gói tin đi vào hàng đợi Drop Tail vượt quá độ dài tối đa của hàng đợi, các gói tin tiếp theo đi đến sẽ bị hủy

vì hàng đợi đã đầy Tổng số gói tin N đi tới một nút với tốc độ theo trong khoảng

thời gian t xác định theo Công thức (4)

2.3.4 Độ đo năng lượng còn lại (REM)

Năng lượng của các nút trong mạng được biểu diễn bằng mô hình năng lượng Mỗi nút sẽ có một năng lượng ban đầu Năng lượng này sẽ giảm dần mỗi khi nút nhận hoặc gửi gói tin Quá trình truyền dữ liệu của nút sẽ bị cản trở nếu năng lượng còn lại của nút quá thấp Năng lượng còn lại của nút được xác định theo Công thức (5)

Trong đó, ( ) là năng lượng còn lại của nút i ở thời điểm t, là năng

lượng ban đầu của nút i, là năng lượng tiêu thụ của nút i tính đến thời điểm t Gọi

p, , tương ứng là số gói tin nút i đã truyền, đã nhận và đã nhận biết được;

( ) là năng lượng cần thiết để nút i truyền gói tin p; ( ) là năng lượng

cần thiết để nút i nhận gói tin ; ( ) là năng lượng cần thiết để nút i nhận biết được gói tin Khi đó, năng lượng tiêu thụ của nút i ở thời điểm t được xác định

theo Công thức (6)

( ) ( ) ( ) (6) Các năng lượng E tx , E rx và E o được xác định theo Công thức (7)

Trong đó, I là cường độ dòng điện tính theo đơn vị ampe, U là hiệu điện thế

tính theo đơn vị vôn, t p là khoảng thời gian để thực hiện công việc truyền / nhận / nhận biết gói tin p