chương 1, luận văn đã trình bày các kiến thức tổng quan về hệ thống mạng MANET, từ đặc điểm, các kiểu kết nối, cách thức hoạt động, phân loại và các ứng dụng của MANET trong thực tế. Trong chương 2, luận văn sẽ đi sâu vào nghiên cứu các giao thức định tuyến trên mạng MANET, phân tích ưu nhược điểm của chúng và đề xuất cách thức cải tiến để nâng cao hiệu năng của giao thức định tuyến AODV cho mạng MANET. NGHIÊN CỨU NÂNG CAO HIỆU NĂNG GIAO THỨC AODV CHO MẠNG MANET 2. Một số thuật toán định tuyến cơ bản trong mạng MANET Trong mạng thông tin vô tuyến nói chung và mạng MANET nói riêng do mỗi node mạng đều có khả năng di chuyển nên topo mạng cũng thay đổi theo thời gian.
Ðặc điểm này gây ra khó khăn trong việc truyền tải gói tin. Riêng mạng MANET gói tin muốn đến được đích thì phải truyền qua nhiều trạm và node mạng, do đó để gói tin đến được đích thì node mạng phải sử dụng phương pháp định tuyến. Giao thức định tuyến có hai chức năng: Tìm, chọn tuyến tốt nhất và chuyển gói tin đến đúng đích. Một phương pháp khá đơn giản và hiệu quả để thực hiện việc định tuyến trong hầu hết các hệ thống mạng truyền thông là việc sử dụng các bộ định tuyến để phát hiện và lựa chọn tuyến hợp lý cho gói dữ liệu đến đích thông qua các thuật toán định tuyến như: thuật toán vectơ khoảng cách (Distance Vector) và thuật toán trạng thái liên kết (Link State) [4].
Thuật toán Vectơ khoảng cách (Distance Vector) Phương pháp này được thực hiện bằng cách truyền định kì các bản sao của bảng định tuyến từ router này sang router khác. Mỗi router nhận được bảng định tuyến của những router lân cận kết nối trực tiếp với nó. Dựa vào thông tin cung cấp bởi các router lân cận, thuật toán vectơ khoảng cách sẽ lựa chọn tuyến tốt nhất. Việc tính toán đường đi trong thuật toán định tuyến theo vectơ khoảng cách dựa vào thuật toán Bellman-Ford.
Thuật toán Bellman-Ford thường được áp dụng trong giao thức định tuyến tĩnh RIP để xây dựng bảng định tuyến. Thuật toán này cũng tương tự như thuật toán Dijkstra nhưng nó không áp dụng phương pháp tham lam trong việc chọn ra đỉnh v có trọng số nhỏ nhất lân cận với đỉnh u đang xét. Thuật toán Bellman-Ford tính toán đường đi ngắn nhất từ nguồn tới đích được mô tả như sau: Input: Đồ thị (G, w, s); Bellman-Ford-More(G, w, s) - Bước 1: Khởi tạo node nguồn s - Bước 2: for i = 1 to V[G] –1 do for mỗi cạnh (u, v) E[G] do if d(v) > d(u) + w then {d(u), d(v) là chi phí được tính từ node gốc đến các đỉnh u, v} d(v) : = d(u) + w; z 14 - Bước 3: for mỗi cạnh (u,v) E[G] do if d[u] + w(u, v) < d[v] then return False; else return True; Output: Cây đường đi ngắn nhất từ node s đến các node khác, kết quả hàm là true nếu không có đỉnh nào mà đường đi đến nó có giá trị lớn hơn tổng đường đi đến node kề đứng trước nó với trọng số trên cạnh nối hai đỉnh u và v, ngược lại hàm trả về giá trị là false. Sử dụng các giao thức định tuyến theo vectơ khoảng cách thường tốn ít tài nguyên của hệ thống.
Tuy nhiên, tốc độ đồng bộ giữa các router lại chậm và thông số được sử dụng để chọn đường đi có thể không phù hợp với những hệ thống mạng lớn. Thuật toán trạng thái liên kết (Link State) Trạng thái liên kết là một mô tả đặc điểm các mối liên kết từ bộ định tuyến này tới các bộ định tuyến lân cận. Các đặc điểm này bao gồm: địa chỉ IP, mặt nạ, kiểu mạng kết nối, và các bộ định tuyến kết nối mạng đó. Giao thức định tuyến trạng thái liên kết được thực hiện dựa trên các gói tin thông báo trạng thái liên kết (LSA), mỗi bộ định tuyến xây dựng cho mình một cơ sở dữ liệu trạng thái riêng dựa vào nội dung của các bản tin này.
Do đó các bộ định tuyến biết rõ và chính xác thông tin về topo mạng và thực hiện truyền dẫn các gói tin từ node nguồn đến node đích trong mạng dễ dàng. Gói thông báo trạng thái liên kết (LSA: Link State Advertisment) là các gói tin nhỏ chứa thông tin định tuyến được truyền qua lại giữa các bộ định tuyến, được làm tràn trên mạng theo định kì hay khi có thay đổi thông tin của một bộ định tuyến nào đó trong mạng. Cơ sở dữ liệu trạng thái liên kết (LSDB: Link State Database) được tạo và cập nhật từ thông tin của các bản tin thông báo LSA. Thuật toán trạng thái liên kết được dùng để xây dựng và tính toán đường đi ngắn nhất từ node nguồn đến tất cả các node đích trong mạng.
Thuật toán Dijkstra được áp dụng trong giao thức định tuyến trạng thái liên kết được thực hiện qua các bước sau: Input: Đồ thị (G, w, s); Dijkstra(G, w, s) - Bước 1: Khởi tạo node nguồn s; - Bước 2: S : = {}; {Cuối cùng S sẽ chứa các đỉnh có trọng số đường đi ngắn nhất từ s} z 15 - Bước 3: Khởi tạo hàng đợi ưu tiên Q : = V[G] {Q chứa các đỉnh trong đồ thị G} - Bước 4: While Q <> {} do u : = EXTRACT_MIN(Q) {Chọn ra đỉnh v trong Q lân cận đỉnh u có trọng số cạnh (u,v) nhỏ nhất gán cho u} - Bước 5: S : = S {u} ; Q : = Q \ {u} - Bước 6: for mỗi đỉnh v Adj[u] do {v các đỉnh liền kề với u} if d( v) > d(u) + w then {d(u), d(v) là chi phí được tính từ node gốc đến các đỉnh u, v} d(v) : = d(u) + w; {quay lại Bước 4} Output: Cây đường đi ngắn nhất từ đỉnh s đến các node trong mạng. Sử dụng giao thức định tuyến trạng thái liên kết sẽ dẫn đến một số nhược điểm: - Router sử dụng định tuyến theo trạng thái liên kết sẽ phải cần nhiều bộ nhớ hơn và hoạt động xử lí nhiều hơn là sử dụng định tuyến theo vectơ khoảng cách. - Router phải có đủ bộ nhớ để lưu cơ sở dữ liệu về cấu trúc mạng, bảng định tuyến. Khi khởi động việc định tuyến, tất cả các router phải gửi gói LSA cho tất cả các router khác, khi đó băng thông đường truyền sẽ bị chiếm dụng làm cho băng thông dành cho đường truyền dữ liệu của người dùng bị giảm xuống.
Tuy nhiên, sau khi các router đã thu thập đủ thông tin để xây dựng cơ sở dữ liệu về cấu trúc mạng thì băng thông đường truyền không bị chiếm dụng nữa. Phân loại các giao thức định tuyến trong mạng MANET Để khắc phục vấn đề liên quan đến giải thuật trạng thái liên kết và vector khoảng cách, một số giao thức cho mạng MANET được đề xuất. Dựa vào việc tập hợp thông tin định tuyến, vai trò một node có thể đảm nhận trong quá trình định tuyến, các giao thức này có thể được phân thành 3 nhóm (Hình 2.1): - Định tuyến theo bảng ghi - Proactive (Table-Driven Routing Protocol) - Định tuyến theo yêu cầu - Reactive (On-Demand Routing Protocol) - Định tuyến lai ghép - Hybrid Routing Protocol z 16 MANET Routing Protocols Proactive/Table-driven Hybrid Reactive/On-Demand DSDV FSR HSLS ZHL AODV TORA OLSR WRP HARP ZRP DSR ACOR Hình 2. Phân loại các giao thức định tuyến trong mạng MANET 2.
Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol) Giao thức định tuyến theo bảng ghi còn được gọi là giao thức chủ ứng (Proactive). Theo giao thức này, bất kì một node trong mạng đều luôn duy trì trong bảng định tuyến của nó thông tin định tuyến đến tất cả các node khác trong mạng. Thông tin định tuyến được phát broadcast trên mạng theo một khoảng thời gian quy định để giúp cho bảng định tuyến luôn cập nhật những thông tin mới nhất. Chính vì vậy, một node nguồn có thể lấy thông tin định tuyến ngay lập tức khi cần thiết.
Tuy nhiên, với những mạng mà các node di chuyển nhiều hoặc các liên kết giữa các node bị đứt thì cần phải có cơ chế tìm kiếm hoặc sửa đổi thông tin của node bị đứt trong bảng định tuyến, nhưng nếu các liên kết đó không sử dụng thì sẽ trở nên lãng phí tài nguyên, ảnh hưởng đến các băng thông của mạng. Chính vì thế giao thức định tuyến theo bảng ghi chỉ áp dụng trong các mô hình mạng MANET mà các node ít di chuyển. Các giao thức hoạt động theo kiểu giao thức định tuyến theo bảng ghi như: giao thức DSDV (Destination Sequenced Distance Vector), giao thức WRP (Wireless Routing Protocol), giao thức GSR (Global State Routing), giao thức OLSR (Optimized Link State Routing). Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol) Một phương pháp khác với phương pháp định tuyến điều khiển theo bảng ghi đó là định tuyến điều khiển theo yêu cầu còn được gọi là giao thức phản ứng (Reactive).
Theo phương pháp này, các tuyến đường sẽ được tạo ra nếu như có nhu cầu. Khi một node yêu cầu một tuyến đến đích, nó phải khởi đầu một quá trình khám phá tuyến (Route Discovery) để tìm tuyến đến đích. Quá trình này chỉ hoàn tất khi đã tìm ra một tuyến sẵn sàng hoặc tất cả các tuyến khả thi đều đã được kiểm tra. z 17 Khi một tuyến đã được khám phá và thiết lập, nó được duy trì thông tin định tuyến (route maintenance) bởi một số dạng thủ tục cho đến khi hoặc là tuyến đó không thể truy nhập được từ node nguồn hoặc là không cần thiết đến nó nữa.
Với các cơ chế đó, các giao thức định tuyến điều khiển theo yêu cầu không phát broadcast đến các node lân cận về các thay đổi của bảng định tuyến theo thời gian, nên tiết kiệm được tài nguyên mạng. Vì vậy, loại giao thức này có thể sử dụng trong các mạng MANET phức tạp, các node di chuyển nhiều. Một số giao thức định tuyến điều khiển theo yêu cầu tiêu biểu như: giao thức AODV (Ad-hoc On Demand Distance Vector), giao thức DSR (Dynamic Source Routing), giao thức TORA (Temporally Ordered Routing Algorihm), … 2. Giao thức định tuyến kết hợp (Hybrid Routing Protocol) Trong giao thức định tuyến này có kết hợp cả hai cơ chế của giao thức định tuyến chủ ứng (Proactive) và giao thức định tuyến phản ứng (Reactive).
Giao thức này phù hợp với những mạng quy mô, kích thước lớn, mật độ các node mạng dày đặc. Trong giao thức định tuyến này, mạng được chia thành các vùng (zone). Mỗi node duy trì cả thông tin về kiến trúc mạng trong vùng của nó và thông tin về các vùng lân cận.