Phạm Văn Tứ
Các giao thức định tuyến chính trong mạng MANET
tải về 466.22 Kb.
|
- Điều hướng trang này:
- 3.3.2 OLSR [8]
- 3.3.3. AODV [12]
- 3.3.4. DSR [7]
- 3.3.5. TORA [11]
3.3. Các giao thức định tuyến chính trong mạng MANET
Hình 7: Phân loại các giao thức định tuyến trong mạng MANET 3.3.1. DSDVDSDV (Destination-Sequenced Distance-Vector Routing) là giao thức chủ ứng dựa trên dựa trên thuật toán Distance vector được xây dựng bởi C.Perkins và P.Bhagwat năm 1994 [13]. Giao thức này được xây dựng dựa trên tiêu chí giữ nguyên sự đơn giản của giải thuật Bellman-Ford và loại bỏ vấn đề vòng lặp. Truyền thông tin định tuyến: Thông tin định tuyến được gửi quảng bá (broadcast) tới tất cả các nút hàng xóm liền kề nó. Thông tin cập nhật được phát định kỳ hoặc ngay khi có các thay đổi xảy ra trong mạng. Để tránh lặp định tuyến DSDV gắn số thứ tự chẵn cho mỗi đường. Số thứ tự được gắn bởi nút đích, được gửi đi trong gói tin cập nhập. Số thứ tự này cho thấy độ mới của mỗi đường, đường nào có số thứ tự cao hơn được xem là tốt hơn. [10] 
Hình 8: Tô-pô mạng thay đổi Số thứ tự này sẽ tăng lên một đơn vị khi một nút phát hiện đường đi tới đích có liên kết bị hỏng khi nó không nhận được cập nhật định kỳ. Khi ấy trong gói tin cập nhật kế tiếp nó gửi đi sẽ quảng bá đường tới đích này có số chặng bằng vô hạn (metric ~ ∞) và tăng thứ tự đường. Khi một nút nhận được thông tin mới về một tuyến đường, tuyến này sẽ được chọn nếu nó có số thứ tự lớn hơn các số thứ tự khác của cùng tuyến đó trong bảng định tuyến. Nếu nó có cùng số thứ tự thì nó sẽ được chọn nếu có số metric tốt hơn. Để làm giảm kích thước gói tin cập nhập, DSDV sử dụng hai loại thông điệp cập nhật là:
Hai loại thông điệp cật nhật này được lưu vào hai bảng khác nhau, một bảng để chuyển tiếp các gói tin đầy đủ, một để phát các gói tin cập nhật. Gói tin cập nhật đầy đủ chỉ được phát thường xuyên khi các nút thường xuyên di chuyển, khi mạng ít thay đổi, chủ yếu chỉ có gói tin cập nhật bổ sung được gửi đi. 3.3.2 OLSR [8]OLSR (Optimized Link State Routing Protocol) là giao thức chủ ứng dựa trên thuật toán trạng thái kết nối (Link state). Các nút gửi định kỳ ra toàn mạng thông điệp “Hello” để trao đổi thông tin về hàng xóm. Thông tin này bao gồm IP của nút, số thứ tự và danh sách các thông tin khoảng cách của các nút hàng xóm. Sau khi cập nhật những thông tin này nút sẽ xây dựng lên bảng định tuyến của nó và có cái nhìn tổng thể về toàn mạng. Dựa vào bảng định tuyến này nó có thể tự tính được đường đi tới các nút khác dựa vào thuật toán tìm đường đi ngắn nhất. Khi một nút nhận được một gói tin trùng lặp với cùng số thứ tự nó sẽ loại bỏ gói tin này. Trong bảng định tuyến nút lưu trữ thông tin định tuyến tới tất cả các nút khác trong mạng. Những thông tin này chỉ được cập nhật khi:
Điểm khác biệt giữa OLSR và LSR (Link State Protocol) là việc giao thức OLSR hoạt động dựa trên việc một nhóm nút mạng cộng tác với nhau tạo nên một kíp phát chuyển tiếp đa điểm (Multi-Point Relays - MPR). Mỗi nút N trong mạng sẽ lựa chọn ra một tập các nút hàng xóm của nó vào kíp đa điểm MPR(N), các nút thuộc kíp đa điểm này sẽ chuyển tiếp các gói tin điều khiển được gửi từ N. Nút không thuộc kíp đa điểm của N vẫn xử lý gói tin này nhưng sẽ không chuyển tiếp đến các nút khác. 
Hình 9: Quy trình chuyển tiếp gói tin khi sử dụng kíp đa điểm – MPR Ưu điểm đầu tiên của việc sử dụng kíp đa điểm (MPR) là việc làm giảm thiểu các thông điệp quảng bá phát tràn trong mạng, giúp cho băng thông được cải thiện đáng kể. Lợi điểm thứ hai là việc giảm được kích thước của gói tin “Hello” vì nó chỉ lưu trữ các thông tin liên quan tới các nút trong kíp đa điểm của nó. 
Hình 10: OLSR ngăn chặn vòng lặp bằng việc sử dụng MPR để chuyển phát gói tin. 3.3.3. AODV [12]AODV (Ad Hoc On-Demand Distance Vector) là giao thức dựa trên thuật toán vector khoảng cách. AODV tối thiểu hoá số bản tin quảng bá cần thiết bằng cách tạo ra các tuyến trên cơ sở theo yêu cầu, ngược với việc duy trì một danh sách hoàn chỉnh các tuyến như thuật toán DSDV. 
Hình 11: quá trình khám phá tuyến trong AODV Khi một nút nguồn muốn gởi một bản tin đến một nút đích nào đó và không biết rằng đã có một tuyến đúng đến đích đó, nó phải khởi đầu một quá trình khám phá đường truyền. Nó phát quảng bá một gói yêu cầu tuyến (RREQ) đến các nút lân cận. Các nút lân cận này sau đó sẽ chuyển tiếp gói yêu cầu đến nút lân cận khác của chúng. Quá trình cứ tiếp tục như vậy cho đến khi có một nút trung gian nào đó xác định được một tuyến “đủ tươi” để đạt đến đích. AODV sử dụng số thứ tự đích để đảm bảo rằng tất cả các tuyến không lặp và chứa hầu hết thông tin tuyến hiện tại. Mỗi nút duy trì số tuần tự của nó cùng với một ID quảng bá. ID quảng bá được tăng lên mỗi khi nút khởi đầu một RREQ, và cùng với địa chỉ IP của nút, xác định duy nhất một RREQ. Cùng với số tuần tự và ID quảng bá, nút nguồn bao gồm trong RREQ hầu hết số tuần tự hiện tại của đích mà nó có. Các nút trung gian có thể trả lời RREQ chỉ khi nào chúng có một tuyến đến đích mà số tuần tự đích tương ứng lớn hơn hoặc bằng số tuần tự chứa trong RREQ. Trong suốt quá trình chuyển tiếp RREQ, các nút trung gian ghi vào Bảng định tuyến của chúng địa chỉ của các nút lân cận từ khi nhận được bản sao đầu tiên của gói quảng bá, theo đó thiết lập được một đường dẫn theo thời gian. Nếu các bản sao của cùng một RREQ được nhận sau đó, các gói này sẽ bị huỷ bỏ. Một khi RREQ đã đạt đến đích hay một nút trung gian với tuyến “đủ tươi”, nút đích (hoặc nút trung gian) đáp ứng lại bằng cách phát đơn phương một gói đáp ứng tuyến (RREP) ngược về nút lân cận mà từ đó nó thu được RREQ. Khi RREP được định tuyến ngược theo đường dẫn, các nút trên đường dẫn đó thiết lập các thực thể tuyến chuyển tiếp trong Bảng định tuyến của chỉ nút mà nó nhận được RREP. Các thực thể tuyến chuyển tiếp này chỉ thị tuyến chuyển tiếp tích cực. Cùng với mỗi thực thể tuyến là một bộ định thời tuyến có nhiệm vụ xoá các thực thể nếu nó không được sử dụng trong một thời hạn xác định. Do một RREP chuyển tiếp trên đường dẫn được thiết lập bởi một RREQ nên AODV chỉ hỗ trợ việc sử dụng đường truyền đối xứng. Trong AODV, các tuyến đươc duy trì điều kiện như sau: Nếu một nút nguồn chuyển động, nó phải khởi động lại giao thức khám phá tuyến để tìm ra một tuyến mới đến đích. Nếu một nút trên tuyến chuyển động, nút lân cận luồng lên của nó chú ý đến chuyển động đó và truyền một bản tin “Khai báo sự cố đường thông” (một RREP không xác định) đến mỗi nút lân cận tích cực luồng lên để thông báo cho các nút này xoá phần tuyến đó. Các nút này thực chất truyền một “Thông báo sự cố đường thông” đến các nút lân cận luồng lên. Quá trình cứ tiếp tục như vậy cho đến khi đạt đến nút nguồn. Nút nguồn sau đó có thể chọn khởi động lại một quá trình khám phá tuyến cho đích đó nếu một tuyến vẫn cần thiết [4]. Ngoài ra, giao thức này sử dụng bản tin HELLO được phát quảng bá định kỳ bởi một nút để thông báo cho tất cả các nút khác về những nút lân cận của nó. Các bản tin HELLO có thể được sử dụng để duy trì khả năng kết nối cục bộ của một nút. Tuy nhiên, việc sử dụng bản tin HELLO là không cần thiết. Các nút lắng nghe việc truyền lại gói dữ liệu để đảm bảo rằng vẫn đạt đến chặng kế tiếp. Nếu không nghe được việc truyền lại như thế, nút có thể sử dụng một trong số các kỹ thuật, kể cả việc tiếp nhận bản tin HELLO. Các bản tin HELLO có thể liệt kê các nút khác mà từ đó nút di động đã nghe tin báo, do đó tạo ra khả năng liên kết lớn hơn cho mạng. 3.3.4. DSR [7]Giao thức DSR (Dynamic Source Routing) là một giao thức định tuyến phản ứng từ nút nguồn. Trong đó, các nút di động cần duy trì bộ nhớ đệm về tuyến chứa các nút nguồn mà nút di động nhận biết được. Các thực thể trong bộ nhớ đệm về tuyến được cập nhật liên tục. 
Hình 12: Định tuyến nguồn động (DSR) Giao thức này bao gồm 2 giai đoạn chính: a) Khám phá tuyến và b) Duy trì tuyến. Khi một nút di động gởi một gói đến một nút đích nào đó, trước hết nó phải tham vấn bộ nhớ đệm tuyến để xác định là nó đã có một tuyến để đến đích chưa. Nếu nó có một tuyến chưa hết hiệu lực để đến đích, nó sẽ sử dụng tuyến này để gởi gói đi. Trái lại, nếu không có một tuyến như thế, nó phải khởi đầu một quá trình khám phá tuyến bằng cách phát quảng bá một gói yêu cầu tuyến. Bản tin yêu cầu này chứa địa chỉ đích, cùng với địa chỉ nút nguồn và số nhận dạng duy nhất. Mỗi nút nhận được gói này sẽ tiến hành kiểm tra là nó có biết một tuyến nào để đến đích không. Nếu không, nó thêm địa chỉ của nó vào Bảng ghi định tuyến của gói và sau đó chuyển tiếp gói trên các đường truyền ngõ ra. Để giới hạn số yêu cầu tuyến phát trên các đường truyền ngõ ra của nút, một nút chỉ chuyển tiếp yêu cầu tuyến nếu nó chưa biết yêu cầu đó và nếu địa chỉ của nút di động chưa xuất hiện trong Bảng ghi tuyến. Một đáp ứng tuyến được tạo ra khi hoặc là yêu cầu tuyến đạt đến đích hoặc là khi nó đạt đến một nút trung gian chứa trong bộ nhớ đệm tuyến của nó một tuyến đến đích chưa hết hiệu lực. Đến lúc gói có thể đạt đến đích hay đến một nút trung gian như thế, nó chứa một Bảng ghi tuyến cho biết số tuần tự chặng đã trải qua. Nếu nút tạo ra đáp ứng tuyến là đích thì nó đặt Bảng ghi tuyến chứa trong yêu cầu tuyến vào đáp ứng tuyến. Nếu nút tương ứng là một nút trung gian, nó gắn thêm tuyến trong bộ nhớ đệm của nó vào Bảng ghi tuyến và sau đó tạo ra một đáp ứng tuyến. Để trả về đáp ứng tuyến, nút tương ứng phải có một tuyến để khởi đầu. Nếu nó có một tuyến để khởi đầu trong bộ nhớ đệm tuyến của nó, nó có thể sử dụng tuyến đó. Trái lại, nếu các đường truyền đối xứng được hỗ trợ, nút có thể khởi đầu một quá trình khám phá tuyến của nó và tiếp tục gởi đi đáp ứng tuyến trên một yêu cầu tuyến mới. Việc duy trì tuyến được hoàn thành thông qua sử dụng các gói lỗi tuyến và các bản tin xác nhận. Các gói lỗi tuyến được tạo ra ở một nút khi lớp liên kết dữ liệu gặp sự cố đường truyền. Nút nguồn luôn luôn bị dừng khi một tuyến bị cắt đứt (có một liên kết trên tuyến bị lỗi). Khi nhận được một gói lỗi tuyến, chặng bị lỗi sẽ bị loại bỏ khỏi bộ nhớ đệm tuyến của nút và tất cả các tuyến chứa chặng này đều bị cắt ở điểm đó. Ngoài các bản tin lỗi tuyến, các bản tin xác nhận được sử dụng để xác minh sự hoạt động chính xác của các đường thông tuyến. Các bản tin xác nhận như thế bao gồm cả xác nhận thụ động (khi nút di động có thể nghe việc chuyển tiếp gói ở chặng kế tiếp trên tuyến).
Trong suốt giai đoạn tạo ra và duy trì tuyến, các nút sử dụng một tham số “độ cao” để thiết lập một DAG (sơ đồ hình xoắn ốc) có gốc ở nút đích. Sau đó, các đường truyền được chỉ định một hướng (luồng lên hay luồng xuống) dựa trên tham số độ cao tương đối của các nút lân cận. Quá trình thiết lập DAG tương tự như quá trình vấn tin/đáp ứng trong LMR (Light-Weight Moblie Routing - Định tuyến di động trọng số thấp). Trong thời gian một nút di chuyển, tuyến DAG bị phá vỡ và việc duy trì tuyến cần để thiết lập lại một DAG có gốc ở cùng đích đó. Khi đường thông luồng xuống cuối cùng bị sự cố thì một nút tạo ra một mức tham chiếu mới dựa vào mức tham chiếu của các nút lân cận, phối hợp hoạt động có hiệu quả để phản ứng lại sự cố đó một cách có cấu trúc. Các đường thông được đảo ngược để phản ánh những thay đổi trong việc thích nghi với mức tham chiếu mới. Việc này có hiệu quả giống như sự đảo hướng của một hay nhiều đường thông khi một nút không có các đường thông luồng xuống. Việc định thời là một yếu tố quan trọng đối với TORA do tham số “độ cao” độc lập với thời gian sự cố đường thông; TORA giả sử rằng tất cả các nút đều có đồng hồ đồng bộ (thực thi qua một nguồn thời gian bên ngoài như hệ thống định vị toàn cầu - GPS). Các tham số của TORA gồm: a) Thời gian sự cố đường thông, b) ID duy nhất của nút xác định mức tham chiếu mới, c) Bit chỉ thị phản ánh, d) Tham số thứ tự truyền, và e) ID duy nhất của nút. Tham số thứ 3 thể hiện mức tham chiếu một cách có chọn lọc. Một mức tham chiếu mới được xác định mỗi khi một nút không còn đường thông luồng xuống cuối cùng do sự cố đường thông. Giai đoạn xoá tuyến của TORA bao gồm một bản tin quảng bá “Xoá tuyến” (CLR) trong toàn mạng để xoá các tuyến không còn hiệu lực nữa. Trong TORA có một sự biến động tiềm tàng xảy ra, đặc biệt khi nhiều tập hợp các nút đang liên kết là phần hiện đang bị xoá, các tuyến đang xoá, và các tuyến đang xây dựng mới. Do TORA sử dụng toà độ liên nút nên bài toán bất cân bằng của nó tương tự như bài toán tính đến vô cùng trong các giao thức định tuyến theo vector cự ly, ngoại trừ các biến động là tạm thời và sự hội tụ tuyến cuối cùng vẫn đạt được.
Каталог: jspui -> bitstream -> 123456789 123456789 -> Nguyễn Ngọc Lý Giám đốc Trung tâm Nghiên cứu về Môi trường và Cộng đồng 123456789 -> Vò Quúnh Thu Cao häc K18 123456789 -> Khoa Báo chí Đhkhxh&NV 123456789 -> Acknowledgements 123456789 -> Danh mục chữ viết tắT 123456789 -> Chương TỔng quan vật liệu mao quản trung bình (mqtb) trật tự 1 Giới thiệu chung 123456789 -> Khoa hóa họC (141 142 báo cáo) tải về 466.22 Kb. Chia sẻ với bạn bè của bạn:
|