Mạng ad-hoc

1/ Khái niệm mạng Ad Hoc.
Ad hoc như những bộ định tuyến không dây. Mạng Ad hoc có thể hoạt động độc lập hoặc kết nối với mạng Mạng vô tuyến Ad hoc là mạng tập hợp các nút di động hoặc bán di động và không có cơ sở hạ tầng. Manet ( Mobile Ad-hoc Network) - Mạng không dây di động. Theo định nghĩa của Tổ chức Internet Engineering Task Force (IETF)- Mạng Manet là một vùng tự trị ( Autômmous System) của các router (đó chính là các node) được kết nối với nhau bằng liên kết không dây, các node có thể di chuyển một cách tự do nên kiến trúc của mạng thay đổi liên tục mà không thể dự đoán trước

Mỗi nút mạng có một giao diện vô tuyến và giao tiếp với nút mạng khác thông qua sóng vô tuyến hoặc tia hồng ngoại. Topo mạng thay đổi liên tục khi các nút mạng tham gia hoặc rời khỏi mạng hay khi kết nối vô tuyến trở nên không còn thích hợp.Mạng Ad hoc được hình thành bởi các nút di động có khả năng phát hiện ra sự có mặt của các nút khác và tự định dạng để tạo nên mạng. Ví dụ như một nút yêu cầu truyền tới một mạng ở xa nó thì trong mạng có thể thiết lập liên lạc qua những nút trung gian, các gói được chuyển tiếp tới nút nguồn, đích nhờ những nút trung gian. Do đó các nút mạng Internet.
Trong mạng Ad hoc không tồn tại khái niệm quản lý tập trung , nó đảm bảo mạng sẽ không bị sập vì trường hợp nút mạng di chuyển ra ngoài khoảng truyền dẫn của nút mạng khác vì nó trao đổi thông tin bằng phương pháp truyền gói tin qua nhiều bước (multi-hop), đồng thời mạng sẽ tự cấu hình lại. Ví dụ: Nếu nút mạng rời khỏi mạng sẽ gây ra sự cố mất liên kết , nút mạng bị ảnh hưởng có thể yêu cầu đường định tuyến mới và vấn đề sẽ được giải quyết. Điều này chỉ gây trễ trên mạng mà không ảnh hưởng đến người sử dụng vì mạng Ad hoc vẫn hoạt động bình thường.
Hiện nay tồn tại hai kiểu topa mạng Ad hoc:
1. Mạng có các thiết bị di động không đồng nhất (Hình dưới bên phải)
2. Mạng máy chủ di dộng (Hình dưới bên trái)

2/ Đặc điểm của mạng Ad Hoc
Một số đặc điểm chính của mạng Ad hoc:
- Mỗi máy chủ không chỉ đóng vai trò là một hệ thống cuối cùng mà còn hoạt động như một hệ thống trung gian
- Mọi nút mạng đều có khả năng di động
- Tôp mạng thay đổi theo thời gian
- Các nút di động sử dụng nguồn năng lượng pin có hạn
- Băng thông trong thông tin vô tuyến hẹp
- Chất lượng kênh luôn thay đổi
- Không có thực thể tập trung , nói cách khác là mạng phân bố
Có nhiều thiết bị khác nhau sử dụng trong mạng Ad hoc, chúng đều có đặc điểm chung là sử dụng nguồn năng lượng do pin cung cấp . Năng lượng mà pin có thể cấp cho các thiết bị này là có hạn, hơn nữa mọi hoạt động như thu phát vô tuyến , truyền lại và dẫn đường đểu tiêu thụ năng lượng. Vì vậy mà cần phải có những giao thức về năng lượng có hiệu quả cao và các kỹ thuật điều khiển công suất tốt hơn. Điều này cũng khó làm được bởi vì công nghệ pin không có được sự phát triển mạnh mẽ nhanh chóng như công nghệ sản xuất chip… do đó điểm này được coi là một nhược điểm của mạng Ad hoc.

3/ Định tuyến trong mạng Ad Hoc
Trong mạng thông tin vô tuyến nói chung và mạng Ad hoc nói riêng do mọi nút 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. Mạng Ad hoc riêng gói tin muốn đến được đích thì phải truyền qua nhiều trạm và nút mạng do đó để gói tin đến được đích thì nút 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 đường tốt nhất và chuyển gói tin đến đúng đích. Dễ thấy rằng chức năng thứ hai rất đơn giản có thể sử dụng nhiều giao thức và cấu trúc dữ liệu có sẵn ví dụ như bảng định tuyến. Do đó ta sẽ đề cập sâu hơn về việc tìm, chọn đường của các nút.

3.1/ Định tuyến Bellman-Ford
Nhiều lược đồ định tuyến trước đây được xây dựng cho mạng không dây Ad hoc dựa trên thuật toán Bellman-Ford. Các lược đồ này cũng được nghiên cứu giải quyết các vấn đề của lược đồ Distance Vector (DV). Trong thuật toán Bellman-Ford, mọi nút i duy trì một bảng định tuyến hay ma trận chứa thông tin khoảng cách và thông tin về nút kế tiếp với i trên đường đi ngắn nhất tới đích j bất kỳ, trong đó khoảng cách chính là chiều dài ngắn nhất từ i tới j. Để cập nhật thông tin về đường đi ngắn nhất mỗi nút sẽ thường xuyên trao đổi bảng định tuyến với các nút bên cạnh nó. Dựa trên bảng định tuyến từ các nút lân cận đó , nút i biết được khoảng cách ngắn nhất từ các lân cận của nó tới nút bất đích bất kỳ. Do đó , với mỗi nút đích j, i sẽ chọn một nút k cho chặng kế tiếp sao cho khoảng cách từ i qua k tới j là nhỏ nhất . Các thông tin tính toán mới này sẽ được lưu trữ vào bảng định tuyến của i và được trao đổi ở vòng cập nhật định tuyến tiếp theo. Định tuyến này có ưu điểm là đơn giản và tính toán hiệu quả do đặc điểm phân bố. Tuy nhiên nhược điểm của nó là hội tụ chậm khi topo mạng thay đổi và có xu hướng tạo các vòng lặp định tuyến đặc biệt là khi các điều kiện liên kết không ổn định.

3.2/ Định tuyến Link State
Định tuyến Link State còn gọi là định tuyến trạng thái liên kết. Định tuyến này cũng là một trong những thuật toán được sử dụng rộng rãi trong nhiều giao thức, chẳng hạn như OSPF. Mặc dù định tuyến Link State hiếm khi được sử dụng cho mạng không dây, song nó lại chứa nhiều tiềm năng cung cấp các giải pháp định tuyến theo yêu cầu cho các tiêu chuẩn định tuyến khác nhau.
Trong định tuyến Link State, khi có một nút phát hiện ra có thay đổi trong vùng kết nối với nó, nút làm tràn trạng thái kết nối mới bởi gói chứa thông tin kết nối cục bộ được cập nhập. Các nút khác thông báo về sự thay đổi này khi gói trạng thái liên kết tới, do đó thông tin về topo mạng thay đổi theo. Định tuyến Link State đáp lại sự thay đổi mạng nhanh hơn DBF và tương tự với định tuyến on-demand. Nó tính toán đường đi theo kiểu tập trung để dễ dàng chống lại các vòng lặp định tuyến. Tuy nhiên do định tuyến Link State cũng dựa vào cơ chế flooding để quảng bá thông tin về sự thay đổi kết nối của nút, phụ trội điều khiển làm cho định tuyến Link State có chất lượng kém hơn DBF và on-demand trong môi trường không dây bất chấp độ chính xác mà nó cung cấp. Vấn đề khác trong định tuyến Link State là một nút có thể không tìm ra những biến đổi về topo mạng chính xác nếu toàn bộ mạng được chia thành hai phần và sau đó được khôi phục lại.

3.3/ Định tuyến tìm đường
Các giao thức mới như DSDV (Destination Sequenced Distance Vector) và WRP (Wireless Routing Protocol) dựa trên DBF để cung cấp định tuyến lặp tự do. Cho dù là vấn đề đã được giải quyết thì vẫn còn tồn tại vấn đề về độ thiếu chính xác trong định tuyến DBF, vấn đề này có thể gây ra suy giảm hiệu suất mạng. Nguyên nhân dẫn đến sự thiếu chính xác là do nút mạng không có được cac thông tin trạng thái toàn mạng dẫn đến các quyết định đưa ra chỉ tối ưu trong phạm vi cục bộ, nó không đảm bảo một giải pháp tối ưu trong môi trường di động. Thêm vào đó khi DBF chỉ duy trì một đường đi duy nhất tới đích, nó thiếu khả năng thích nghi với các lỗi liên kết và yêu cầu nghiên cứu mở rộng cho các hỗ trợ multicasting.

3.4/ Định tuyến On-demand
Định tuyến On-demand được biết đến như DC (Diffusion Computation) cũng được sử dụng trong mạng không dây. Trong lược đồ định tuyến On-demand, một nút xây dựng đường đi bằng cách chất vấn tất cả các nút trong mạng. Gói chất vất tìm được ID của các nút trung gian và lưu giữ ở trường Path. Khi dò tìm các chất vấn, nút đích hay các nút đã biết đường đi tới đích trả lời chất vấn bằng cách phúc đáp “source routed” cho nơi gửi. Do nhiều phúc đáp nên có nhiều đường đi được tính toán và duy trì. Sau khí tính toán đường đi nút liên kết bất kỳ bắt đầu các chất vấn , phúc đáp khác nên luôn cập nhật định tuyến. Mặc dù các tiếp cận dựa trên cơ sở DC có độ chính xác cao hơn và phản ứng nhanh hơn với sự thay đổi mạng nhưng phụ trộ điều khiển quá mức do thường xuyên yêu cầu flooding đặc biệt khi tính di động cao hơn và lưu lượng dày đặc phân bố đều nhau. Kết quả là các giao thức định tuyến On-demand chỉ phù hợp với mạng không dây băng thông rộng trễ truyền gói nhỏ và lưu lượng rất mỏng.

3.5/ Định tuyến vùng
Định tuyến vùng là một giao thức định tuyến khác thiết kế trong môi trường Ad hoc. Đây là giao thức lai giữa định tuyến On-demand với một giao thức bất kỳ đã tồn tại. Trong định tuyến vùng mỗi nút xác định vùng riêng khi nút ở khoảng cách nhất định. Hai lược đồ định tuyến khác nhau được yêu cầu cho định tuyến vùng. Để định tuyến trong vùng có thể sử dụng bất kỳ lược đồ giao thức nào DBF hoặc LS. Mục đích trong vùng là để duy trì thông tin đầy đủ về khả năng nút đạt tới đích của nút ở trong vùng đang xét. Định tuyến vùng trung gian sử dụng định tuyến On-demand để tìm đường đi.Định tuyến vùng kết hợp hai lược đồ định tuyến nêu trên và hoạt động như sau: khi có lưu lượng cần được định tuyến, nó kiểm tra xem đích có ở trong vùng đó hay không. Nếu nút đích ở trong vùng trung gian duy trì thông tin cần thiết. Khi nút gửi một lưu lượng tới đích ở phạm vi ngoài vùng của nút, định tuyến vùng sẽ gửi các gói yêu cầu theo kỹ thuật multicasting tới các nút đường biên để tìm đường đi, giao thức định tuyến trong vùng cung cấp đường đi ngắn nhất. Nếu một số nút đường biên có thông tin về đích thì các gói phúc đáp sẽ được gửi trở lại cho nguồn. Ngược lại, các nút đường biên sẽ vẫn cứ yêu cầu các nút đường biên khác cho đường đi tới đích.
Ưu điểm của định tuyến vùng là khả năng mở rộng cấp độ khi nhu cần lưu trữ cho bảng định tuyến giảm xuống. Tuy nhiên do gần giống với định tuyến On-demand nên định tuyến vùng cũng gặp phải vấn đề về trễ kết nối và điểm kết thúc của các gói yêu cầu. 

4/ Giao thức định tuyến trong mạng Ad Hoc
Phân loại các giao thức định tuyến:
- Dựa trên bảng định tuyến: DSDV, WRP,
- Theo yêu cầu: AODV, DSR, LMR > TORA, ABR > SSR

4.1 DSDV
4.1.1 Mô tả
DSDV là giao thức định tuyến vecto khoảng cách theo kiểu từng bước: trong mỗi nút mạng duy trì bảng định tuyến lưu trữ đích có thể đến ở bước tiếp theo của định tuyến và số bước để đến đích. DSDV yêu cầu nút mạng phải gửi đều đặn thông tin định tuyến quảng bá trên mạng
Ưu điểm của DSDV là đảm bảo không có đường định tuyến kín bằng cách sử dụng số thứ tự đệ đánh dấu mỗi đường. Số thứ tự cho biết mức độ “mới” của đường định tuyến, số càng lớn thì mức độ đảm bảo càng cao (đường R được coi là tốt hơn R’ nếu số thứ tự của R lớn hơn, trong trường hợp có cùng số thứ tự thì R phải có số bước nhỏ hơn). Số thứ tự sẽ tăng khi nút A phát hiện ra đường đến đích D đị phá vỡ, sau đó nút A quảng bá đường định tuyến của nó tới nút D với số bước không giới hạn và số thứ tự sẽ tăng lên.
Về cơ bản DSDV dùng thuật toán vecto khoảng cách có điều chỉnh cho phù hợp với mạng Ad hoc: có xét đến thay đổi cấu trúc mạng giữa các lần quảng bá thông tin. Để giảm lượng thông tin trong các gói tin cập nhật thông tin DSDV sử dụng hai loại bản tin: bản tin đầy đủ và bản tin có thông tin mới (so với thông tin cập nhật trước đó).

4.1.2 Đặc điểm
DSDV phụ thuộc vào thông tin quảng bá định kỳ nên nó sẽ tiêu tốn thời gian để tổng hợp thông tin trước khi đường định tuyến được đưa vào sử dụng. Thời gian này là không đáng kể đối với mạng có cấu trúc cố định nói chung (bao gồm cả mạng có dây), nhưng với mạng Ad hoc thời gian này là đáng kể, có thể gây ra mất gói tin trước khi tìm ra được định tuyến hợp lý. Ngoài ra, bản tin quảng cáo định kỳ cũng là nguyên nhân gây ra lãng phí tài nguyên mạng

4.2 AODV
4.2.1 Mô tả
4.2.2 Mô tả chung
Giao thức định tuyến AODV cho phép định tuyến nhiều bước giữa các nút mạng để thiết lập và duy trì mạng Ad hoc. AODV dựa trên thuật toán vecto khoảng cách nhưng thuộc loại định tuyến yêu cầu, AODV chỉ yêu cầu định tuyến khi cần thiết và không yêu cầu nút mạng phải duy trì đường định tuyến đến các nít mạng không tham gia trao đổi thôngtin
AODV cho phép: định tuyến mở khi liên kết bị phá vỡ thông báo được gói đi ngay lập tức đến nhóm nút mạng liên quan và chỉ những nút mạng này thôi. Hơn nữa AODV cũng hỗ trợ định tuyến multicast và giải quyết được vấn đề đếm vô hạn trong thuật toán Bellman-Ford. Việc sử dụng số thứ tự ở nút mạng đích giúp cho đường định tuyến luôn được cập nhật và không hình thành đường định tuyến khép kín.
Thuật toán sử dụng nhiều dạng bản tin khác nhau để phát hiện và duy trì liên kết trong mạng. Khi nút mạng muốn sử dụng hoặc tìm đường định tuyến đến nút mạng khác, nó quảng bá bản tin yêu cầu đường định tuyến RREQ đến tất cả nút mạng gần nó. Bản tin RREQ này truyền trên mạng đến khi nó đến được nút mạng đích hoặc một nút mạng có đường định tuyến đến đích. Sau đó bản tin RREP sẽ được gửi lại, thông báo với nút nguồn.
Ngoài ra AODV còn sử dụng bản tin HELLO (là dạng bản tin RREP thu gọn) để quảng bá tới nút mạng bên cạnh. Bản tin này cho biết sự hiện diện của nút mạng nguồn trong mạng và nút mạng gần đó sử dụng đường định tuyến thông qua nút mạng nguồn phát tín hiệu quảng bá, đường định tuyến đó là hợp lệ. Nếu nút mạng không nhận được bản tin HELLO từ nút mạng A và liên kết đến nút A coi như bị phá vỡ và nó cũng thông báo cho nút mạng liên quan thông quan bản tin thông báo liên kết bị hỏng (RREP)

4.2.2.1 Quản lý bảng định tuyến
AODV lưu giữ thông tin cho mỗi đường định tuyến trong bảng định tuyến
- Địa chỉ IP của nút mạng đích
- Số thứ tự của nút mạng đích
- Số các nút mạng để tới đích
- Nút mạng trong bước tiếp theo
- Thời gian tồn tại của đường định tuyến
- Danh sách các nút mạng gần kề còn hoạt động
- Bộ đệm yêu cầu: để bảo đảm môi yêu cầu được xử lý một lần không bị bỏ sót

4.2.2.2 Tìm kiếm đường định tuyến
Trong trường hợp nút mạng quảng bá bản tin RREQ khi nó cần một đường đến nút mạng đích và không có đường nào có sẵn (thông thường đường đến nút mạng đích không biết hoặc đường đó bị quá thời gian) Sau khi quảng bá PREQ, nút mạng chờ bản tin RREP, trong một thời gian nhất định mà nó không nhận được trả lời thì bản tin RREQ lại được gửi đi hoặc mặc định là không có đường định tuyến đến nút mạng đó
Khi nhận được RREQ mà không có đường định tuyến đến đích theo yêu cầu thì nó sẽ chuyển bản tin RREQ đi, quảng bá lại RREQ. Nút mạng cũng tạo ra một đường định tuyến ngược đến địa chỉ IP nguồn trong bảng định tuyến của nó với nút mạng trung gian có địa chỉ IP trùng với địa chỉ chứa trong trường IP của nút mạng bên cạnh đã gửi quảng bá bản tin RREQ, điều này thực hiện được nhở việc ghi lại đường ngược đến nút mạng đưa ra yêu cầu và có thể được sử dụng cho bản tin cuối cùng RREP để tìm đường đến nút mạng đó.
Khi bản tin RREQ đến được nút mạng đích hoặc nút mạng có định tuyến đến đích, thì bản tin RREP được tạo ra và gửi unicast đến nút mạng đưa ra yêu cầu. Trong khi RREP được chuyển tiếp thì một đường định tuyến được tạo ra đến đích và khi RREP đến được, nút mạng đưa ra yêu cầu thì đường định tuyến từ nút mạng nguồn đến nút mạng đích đã tồn tại.

4.2.2.3 Cập nhật đường định tuyến
Khi một nút mạng phát hiện đường định tuyến đến nút mạng bên cạnh không hoạt động, nó sẽ xóa trong bảng định tuyến và gửi một bản tin liên kết hỏng. AODV sử dụng danh sách nút mạng bên cạnh còn hoạt động để ghi nhớ nút mạng đang sử dụng đường định tuyến trong bảng định tuyến. Nút mạng nhận được bản tin này cũng sẽ lặp lại quá trình gửi bản tin. Cuối cùng bản tin cũng gửi đến tất cả nút mạng có liên quan, từ đó chúng có thể dừng việc gửi thông tin hoặc yêu cầu đường định tuyến mới thông qua bản tin RREQ.

4.2.2 Đặc điểm
AODV giảm được lượng lớn thông tin định tuyến trên mạng nhờ sử dụng phương thức định tuyến theo yêu cầu. AODV coi trọng định tuyến hơn so với giao thức DRS điều này cho phép mạng Ad hoc có thể kết nối đến mạng có dây dễ dàng hơn (như mạng internet)
AODV sử dụng số thứ tự SeqNum nên có thể làm mơi đường định tuyến và SeqNum sẽ tăng khi có vấn đề ở khu vực xung quanh, đồng thời chống được định tuyến kín. Tuy nhiên, SeqNum dùng cho thuật toán định tuyễn cũng nảy sinh những vấn đề mới: điều gì sẽ xảy ra khi SeqNum không đồng bộ trên toàn mạng (nếu như mạng bị chia nhỏ theo các khu vực khác nhau hoặc số thứ tự bị trùng lặp).
AODV hỗ trợ một đường định tuyến cho một nút mạng đích, nhưng cũng dễ dàng thay đổi để xác định nhiều đường định tuyến cho mỗi đích. Thay vì yêu cầu một đường định tuyến mới khi định tuyến cũ không hợp lệ thì AODV có thể chọn đường định tuyến được lưu trữ đến cùng nút mạng đích đó với xác suất hợp lệ cao hơn.
AODV sử dụng bản tin HELLO ở mức IP, hỗ trợ lớp liên kết, nên chất lượng hoạt động của giao thức là điều cần quan tâm và cần cải tiến. Bản tin HELLO sẽ thêm phần tiêu đề vào gói tin định tuyến. AODV không hỗ trợ liên kết một chiều. Khi nút mạng nhận yêu cầu RREQ, nó sẽ khởi tạo đường định tuyến ngược đến nút nguồn bằng cách sử dụng những nút mạng đã chuyển tiếp bản tin RREQ. Đường định tuyến trả lời này thường là unicast và giống với đường đã sử dụng. Do vậy khi hỗ trợ liên kết một chiều AODV có thể khởi tạo tất cả liên kết chứ không chỉ là liên kết hai chiều như hiện nay. Tuy nhiên khi mô tả lớp MAC trong IEEE 802.11 không hoạt động với liên kết này.

4.3. DSR
4.3.1 Mô tả
4.3.1.2 Mô tả chung
Giao thức định tuyến DSR nằm trong lớp giao thức theo yêu cầu và cho phép nút mạng có thể tìm kiếm đường định tuyến thông qua nhiều nút mạng đến bất kỳ nút mạng đích nào. Định tuyến theo yêu cầu (hoạc từ nút nguồn) nghĩa là trong tiêu đề của mỗi gói tin chứa danh sách theo thứ tự nút mạng mà gói tin qua để đến nút mạng đích. DSR không sử dụng bản tin định kỳ (không có bản tin quảng bá đường định tuyến) nên giảm được băng thông mạng, bảo tôn được năng lượng pin và giảm được thông tin định tuyến. Để thực hiện những việc trên DSR dựa trên sự hỗ trợ của lớp MAC (lớp MAC sẽ thông tin cho giao thức định tuyến về trạng thái các liên kết). DSR cũng sử dụng hai cơ chế cơ bản là tìm kiếm đường và cập nhật đường định tuyến.

4.3.1.3 Thủ tục tìm kiếm đường
Nút mạng X muốn thông tin với nút mạng Y thì nó cần có một đường định tuyến nguồn tới Y, nút X sẽ gửi quảng bá gói tin RREQ. Tất cả các nút mạng nhận đượng yêu cầu này sẽ tìm kiếm trong bộ đệm đường định tuyến đến Y. DSR lưu toàn bộ các đường định tuyến thông dụng trong bộ đệm của nó. Nếu như không có đường định tuyến nào được tìm thấy thì nút mạng sẽ chuyển tiếp RREQ đi và thêm cả địa chỉ của nó. Yêu cầu này sẽ truyền trên mạng đến khi đến được nút mạng Y hoặc đến được nút mạng có định tuyến đến nút mạng Y. Khi đó bản tin trả lời RREP được gửi theo kiểu unicast ngược lại nút mạng nguồn. RREP chứa nút mạng trong mạng để có thể đến nút mạng Y. Trong thủ tục tìm đường, đầu tiên nút mạng gửi bản tin RREQ với giới hạn tối đa đường truyền được đặt ra là 0 để cho các nút mạng bên cạnh nó quảng bá lại bản tin này. Theo giá của gói tin quảng bá, kỹ thuật này cho phép nút mạng truy vấn đến bộ đệm định tuyến của nút mạng bên cạnh nó.
Các nút mạng cũng có thể hoạt động ở giao diện mạng theo chế độ lẫn lộn, không lọc địa chỉ giao diện và làm cho giao thức mạng nhận được tất cả gói tin mà giao diện nhận được. Các gói tin này được quét bởi đường định tuyến nguồn hoặc do các bản tin báo lỗi định tuyến và sau đó sẽ được loại bỏ.
Đường định tuyến ngược lại nút mạng X có thể nhận được theo nhiều cách khác nhau: cách đơn giản nhất là nghịch đảo lại bản ghi trong gói tin, tuy nhiên nó đòi hỏi liên kết phải cân xứng. Theo đó, DSR cũng kiểm tra bộ đệm định tuyến của nút mạng trả lời, nếu đường định tuyến được tìm thấy nó sẽ được sử dụng thay thế. Cách thứ hai là sử dụng ngay bản tin trả lời nút X. Tức là DSR có thể tính toán sửa được các đường liên kết một chiều (không cân xứng), khi đường định tuyên được tìm thấy nó sẽ được lưu trong bộ đệm với nhãn thời gian và giai đoạn duy trì đường định tuyến bắt đầu.

4.3.1.4 Cập nhật đường định tuyến
Thủ tục này được thực hiện bằng cách gói tin S được gửi đi để kiểm tra cấu trúc mạng, nếu thay đổi nó không sử dụng đường định tuyến đến nút mạng đích D (có thể do nút mạng nằm trong danh sách di chuyển ra ngoài mạng hoặc ngắt đường định tuyến). Khi thủ tục này phát hiện vấn đề với thời gian định tuyến đang sử dụng, gói tin báo lỗi định tuyến được gửi trở lại nút mạng nguồn, nút mạng này sẽ xoá bỏ nút mạng báo lỗi trong bộ đệm. Do đó đường định tuyến có chứa nút mạng đó sẽ bị ngắt tại điểm nút mạng đó.

4.3.2 Đặc điểm
DSR tận dụng ưu điểm tối đa của định tuyến từ nút nguồn. Nút mạng trung gian không cần duy trì, cập nhậ thông tin định tuyến để định tuyến gói tin mà chúng chuyển tiếp, cũng không cần bản tin quảng bá thông tin định tuyến định kỳ. Giao thức DSR có thể cập nhật đường định tuyến bằng cách quét thông tin trong gói tin nhận được. Đường định tuyến từ nút A đến nút C thông qua nút B: nút A có thể lấy thông tin từ nút C và cũng có thể lấy thông tin từ nút B. Định tuyến nguồn cũng có nghĩa là B lấy thông tin từ nút A và C, C cũng lấy thông tin từ A vàB. Tuy nhiên gói tin mang thông tin của phần định tuyến và phần thông tin này sẽ lớn dần khi gói tin đi qua nhiều nút mạng trước khi tới nút mạng đích. Khi hoạt động ở chế độ lẫn lộn, bảo mật là một vấn đề quan trọng, thủ tục lọc địa chỉ ở giao diện bị tắt và gói tin được quét lấy thông tin. Do đó có thể những người không hợp pháp lấy được thông tin này. Ứng dụng vì thế cần có cơ chế bảo mật của mình trước khi gửi gói tin đi. Giao thức định tuyến là đối tượng dễ tấn công bảo mật do đó nó cần có cơ chế bảo mật, có thể dùng giao thức IPSec. DSR hỗ trợ liên kết một chiều do sử dụng chế độ piggyback, và yêu cầu giao thức MAC hỗ trơ liên kết này.

4.4 ZRP
4.4.1 Mô tả
4.4.1.1 Mô tả chung
Giao thức ZRP la giao thứ sử dụng hỗn hợp hai kiểu tương tác và dự đoán trước. Nó chia thành nhiều vùng định tuyến và chỉ rõ hai giao thức riêng biệt hoạt động trong và giữa các vùng định tuyến.
Giao thức IARP hoạt động trong các vùng định tuyến và lấy được khoảng cách ngắn nhất và đường định tuyến đến tất cả nút mạng trong vùng. Nó không chỉ rõ giao thức định tuyến theo kiểu dự đoán trước nào, như vecto hay trạng thái liên kết. Các vùng định tuyến khác nhau có thể hoạt động với giao thức intrazone khác nhau ngay cả khi nó bị giới hạn với những vùng này. Khi có sự thay đổi cấu trúc mạng thì thông tin cập nhật chỉ được truyền trong các vùng định tuyến liên quan chứ không phải toàn mạng.
Giao thức thứ hai, IERP là giao thức tương tác được sử dụng để tìm đường định tuyến giữa các vùng định tuyến, khi nút mạng đích không nằm trong vùng định tuyến. Giao thức sẽ quảng bá RREQ đến tất cả nút mạng nằm ở đường biên trong vùng định tuyến. Thủ tục này được lặp lại cho đến khi nút mạng yêu cầu được tìm thấy và bản tin được trả lời được gửi đến nút nguồn. IERP sử dụng giao thứuc BRP và ZRP.

4.4.1.2 Vùng định tuyến
Được định nghĩa là tập hợp nút mạng, nằm trong khoảng cách tối thiểu nào đó trong số bước bước từ nút yêu cầu. Khoảng cách được hiểu là bán kính của vùng. Để yêu cầu không quay lại vùng định tuyến trước, ZRP sử dụng danh sách yêu cầu được xử lý PRL, khi nút mạng nhận được yêu cầu nó so sánh PRL, nếu yêu cầu đã đựoc xử lý thì lập tức bị loại bỏ.

Mạng sử dụng giao thức ZRP

4.4.2 Đặc điểm
Đây là giao thức đựoc quan tầm nhiều với mạng Ad hoc, nó có thể điều chỉnh trong điều kiện vận hành của mạng (chẳng hạn sự thay đổi đường kính vùng định tuyến). Tuy nhiên nó không thực hiện hoàn toàn do đường kính vùng định tuyến được khuyến nghị do người quản trị mạng khởi tạo hoặc với giá trị mặc định của nhà sản xuất. Hoạt động của giao thức phụ thuộc nhiều vào quyết định này. Do áp dụng cả hai loại định tuyến: định tuyến theo bảng và theo yêu cầu nên giao thức định tuyến tận dụng được ưu điểm của cả hai. Đường định tuyến được tìm rất nhanh trong vùng định tuyến, còn đường định tuyến ngoài có thể được truy vấn từ nút mạng được chọn lựa. Tuy nhiên, giao thức intrazone không xác định nút mạng sẽ phải hộ trợ nhiều giao thức định tuyến khác nhau, nó không thực sự khả thi với thiết bị nhỏ như PDA. Do đó sử dụng cùng giao thức định tuyến intrazone sẽ đem lại hiệu quả hơn.
ZRP giới hạn thông tin về thay đổi cẩu trúc mạng, nó chỉ gửi đến nút mạng bên cạnh có thay đổi (trái ngược với kiểu dự đoán trước, thông tin sẽ gửi trên toàn mạng), tất nhiên sự thay đổi cấu trúc sẽ gây nhiều ảnh hưởng đến vùng định tuyến

4.5 TORA
4.5.1 Mô tả
TORA là giao thức định tuyến phân tán, thuật toán cơ bản là thuật toán hoán vị liên kết, nó được thiết kế nhằm tối thiểu hoá phản ứng với sự thay đổi về cấu trúc mạng. Khái niệm quan trọng trong giao thức này là các bản tin điều khiển được khoanh vùng trong tập hợp nhỏ các nút mạng. TORA đảm bảo tất cả các đường định là là vòng mở và cung cấp nhiều đường định tuyến cho mỗi cặp nút mạng nguồn và đích. Nó chỉ thực hiện thuần tuý chức năng định tuyến, chức năng khác phụ thuộc vào giao thức IMEP.
Ba chức năng cơ bản là : Tạo định tuyến, cập nhật đường định tuyến, xoá bỏ đường định tuyến. Chức năng tạo đưòng định tuyến đơn giản là gán hướng cho liên kết mạng vô hường hoặc một phần mạng vô hướng, xây dựng lên đồ thị xoắn có hướng bắt từ nút mạng đích.

Đồ thị xoắn có gốc ở nút đích D
TORA gắn cho mỗi nút trong mạng một giá trị “chiều cao”, tất cả bản tin trong mạng được di chuyển theo chiều xuôi xuống: từ nút mạng có chiều cáo hơn đến nút mạng có chiều cao thấp hơn. Đường định tuyến được tìm thông qua bản tin truy vấn QRY và bản tin cập nhật UPD. Khi nút mạng không có liên kết xuống cần có định tuyến đến nút mạng đích, nó sẽ quảng bá gói tin QRY, gói tin này truyền trên mạng đến khi nó gặp được nút mạng đích hoặc có đường định tuyến đến nút mạng đích. Sau đó nó quảng bá UPD với chiều cao của nó. Tất cả nút mạng nhận được gói tin cập nhật này sẽ gửi chiều cao của nó đến nút có chiều cao lớn hơn giá trị trong gói UPD. Nút mạng cũng quảng bá gói tin UPD của riêng nó, kết quả thu được một số liên kết định hướng từ nút gửi bản tin truy vấn đến nút mạng đích. Duy trì đường định tuyến khi cấu trúc mạng thay đổi theo kiểu đường định tuyến đến đích được thành lập lại trong khoảng thời gian có hạn. Thủ tục xoá đường định tuyến được thực hiện thông quan bản tin CLR.

4.5.2 Đặc điểm
Thuật toán hoán vị sẽ thay đổi cùng với sự thay đổi liên kết thông qua thuật toán phân tán trong vùng nhỏ đơn lẻ, điều này không cho phép bản tin CLR được truyền quá xa trong mạng. Theo dự án CMU Monarch cho thấy phần tiêu đề trong TORA khá lớn do sử dụng giao thức
IMEP. Đồ thị bắt nguồn ở đích (nút mạng có chiều cao thấp nhất) nhưng nút phải gửi bản tin truy vấn không cần có chiều cao lớn nhất. Tuy nhiên, nảy sinh tình huồng: có nhiều đường định tuyến giữa cặp nút mạng nguồn-đích nhưng chỉ có một đường được tìm thấy. Có thể giải thích là chiều cao ban đầu dựa trên khoảng cách giữa các nút mạng trung gian trước khi đến nút mạng đích.

4.6 IMEP
4.6.1 Mô tả
IMEP là giao thức thiết kế hỗ trợ hoạt động của nhiều giao thức định tuyến trong mạng Ad hoc. Ý tưởng giao thức tổng quát cho tất cả giao thức định tuyến sử dụng, nó kết hợp các kỹ thuật mà các giao thức lớp trên cần:
- Phán đoán trạng thái liên kết
- Kết hợp các bản tin điều khiển
- Quảng bá một cách tin cậy
- Giải địa chỉ lớp mạng
- Các thủ tục chứng thực bảo mật liên quan router.
IMEP cũng đưa ra cấu trúc nhận dạng router MANET, nhận dạng giao diện và đánh địa chỉ, với mục đích nâng cao chất lượng hoạt động của giao thức và giảm thiểu số lượng bản tin điều khiển, ghép các chức năng chung. Chính vì thế mà TORA và OLSR sử dụng IMEP cho các chứng năng khác định tuyến


Giao thức định tuyến IMEP

4.6.2 Đặc điểm
Ý tưởng thiết kế giao thức này rất hay nhưng đứng từ quan điểm chất lượng hoạt động của giao thức thì giao thức lại chưa đạt. Nó thêm thành phần chia lớp vào bộ giao thức và khi thực hiện trong dự án CMU Monarch IMEP đã sinh ra quá nhiều thông tin tiêu đề .

4.7 CBRP
4.7.1 Mô tả
4.7.1.1 Mô tả chung
CBRP chia nút mạng trong mạng Ad hoc thành các cluster chồng nhau hoặc rời rạc. Mỗi một cluster có một nút mạng đại diện có chứa các thông tin quan hệ nút mạng cho cluster đó. Đường định tuyến trong một cluster được tìm kiếm tự động thông qua thông tin quan hệ giữa các nút mạng.
CBRP dựa tên thuật toán định tuyến nguồn tương tự như DSR, có nghĩa là định tuyến giữa các cluster được thực hiện thông qua bản tin RREQ gửi trên toàn mạng, chỉ khác là sô lượng nút nhỏ hơn. Trong khi giao thức định tuyến theo mặt phẳng sẽ chịu khối lượng tiêu đề quá tải khi mở rộng, CBRP cũng giống như các giao thứuc phân tán khác, điều này có lợi khi mà cấu trúc mạng thay đổi liên tục, hơn nữa sẽ chú ý đến sự tồn tại của liên kết một chiều.

4.7.1.2 Phán đoán liên kết.
Mỗi nút mạng trong CBRP biết tên liên kết hai chiều đến nút mạng bên cạnh cũng như liên kết một chiều từ nút mạng bên cạnh đến nó thông qua bảng danh sách nút mạng nằm trong phạm vi truyền dẫn. Mỗi nút mạng sẽ gửi quảng bá định kỳ các bản tin HELLO đến nút bên cạnh, có chứa thông tin: ID của nút mạng, có vai trò của nút mạng và bảng nút mạng nằm trong phạm vi truyền dẫn. Thông tin trong bản tin HELLO được sử dụng để cập nhật thông tin trong bảng của mỗi nút mạng. Nếu một nút không nhận được bản tin HELLO thì thông tin trong bảng sẽ bị loại bỏ.

4.7.1.3 Cluster
Thuật toán thông tin cluster rất đơn giản, nút mạng với ID nhỏ nhất được chọn là cluster đứng đầu, nó quan tâm đến nút mạng mà nó liên kết hai chiều đến nút mạng thành viên của nó. Một nút mạng coi như là nít mạng thành viên của một cluster nếu nó liên kết hai chiều đến cluster đứng đầu, như vậy một nút mạng có thể thuộc nhiều cluster.Các cluster được nhận dạng bởi nhiều tiêu đề đại diện của chúng, khi hai cluster đứng đầu di chuyển gần nhau thì một trong hai sẽ mất vai trò đứng đầu cluster.


Liên kết hai chiều đến các Cluster

4.7.1.4 Định tuyến
Định tuyến trong CBRP dựa trên định tuyến nguồn và tìm kiếm đường thông qua việc gửi RREQ trên toàn mạng tất nhiên với một số lượng nhỏ các nút mạng trong cluster. Khi nút mạng X muốn có đường đến nút mạng Y thì nó gửi bản tin RREQ với bản ghi định tuyến chỉ có nó. Bất kỳ nút mạng nào khi nhận được gói tin sẽ thêm ID của nó vào trong RREQ. Mỗi nút mạng chỉ chuyển tiếp gói tin một lần nhờ kiểm tra trong bản ghi định tuyến.
Trong CBRP, bản tin RREQ theo đường định tuyến dạng:
Nút mạng nguồn > Cluster đứng đầu > Gateway > Cluster đứng đầu > Gateway…> Nút mạng đích.
Nút mạng Gateway cho một cluster là nút mạng có đường liên kết hai chiều hoặc một chiều đến một nút mạng nằm trong cluster khác. RREQ sẽ được chuyển đi như trên cho đến khi đến được môt nút có khả năng cung cấp đường định tuyến. Khi RREQ đến được đích, nút mạng đích có thể chon đường đin ngược lại đến nguồn trong gói tin trả lời RR.

4.7.2 Đặc điểm
Giao thức định tuyến này có nhiều đặc điểm chung với các giao thức định tuyến đã trình bày ở trên: nó có cơ chế tìm đường và loại bỏ đường tương tự với DSR và AODV. Giải pháp clustering là một giải pháp hay với mạng Ad hoc quy mô lớn, nó có khả năng mở rộng hơn với các giao thức khác, giới hạn được các bản tin điều khiển được gửi đi trong mạng. CBRP có các lợi thế khi tận dụng các liên kết một chiều. Tuy nhiên, câu hỏi tối ưu với CBRP là kích thước của cluster là bao nhiêu.

Nguồn từ forum saobacdau nhưng hiện forum đang bị die

Posted in: Mạng không dây