Phạm Văn Tứ
Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN
tải về 466.22 Kb.
|
- Điều hướng trang này:
- 3.1.2. Các đặc điểm chính của mạng MANET
- 3.2. Vấn đề định tuyến trong mạng MANET
- 3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANET
- 3.2.3. Phân loại các kỹ thuật định tuyến
- 3.2.3.2. Định tuyến chủ ứng và phản ứng
- 3.2.3.3. Định tuyến nguồn và định tuyến theo chặng
Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN3.1. Mạng MANET3.1.1. Lịch sử phát triển và các ứng dụngLịch sử: Mạng di động đặc biệt (Mobile Adhoc Netwowk) là mạng tự cấu hình của các nút di động kết nối với nhau thông qua các liên kết không dây tạo nên mạng độc lập không phụ thuộc vào cơ sở hạ tầng mạng. Các thiết bị trong mạng có thể di chuyển một cách tự do theo mọi hướng, do đó liên kết của nó với các thiết bị khác cũng thay đổi một cách thường xuyên. Nguyên lý làm việc của mạng Adhoc bắt nguồn từ năm 1968 khi các mạng ALOHA được thực hiện. Tuy các trạm làm việc là cố định nhưng giao thức ALOHA đã thực hiện việc quản lý truy cập kênh truyền dưới dạng phân tán, đây là cơ sở lý thuyết để phát triển kỹ thuật truy cập kênh phân tán vào mạng Adhoc. Năm 1973 tổ chức DARPA đã bắt đầu làm việc trên mạng vô tuyến gói tin PRnet. Đây là mạng vô tuyến gói tin đa chặng đầu tiên. Trong đó các nút hợp tác với nhau để gửi dữ liệu tới một nút nằm ở xa khu vực kết nối thông qua một nút khác. Nó cung cấp cơ chế cho việc quản lý hoạt động trên cơ sở tập trung và phân tán. Một lợi điểm của làm việc đa chặng so với đơn chặng là triển khai đa chặng tạo thuận lợi cho việc dùng lại tài nguyên kênh truyền về cả không gian, thời gian và giảm năng lượng phát cần thiết. Sau đó có nhiều mạng vô tuyên gói tin phát triển nhưng các hệ thống không dây này vẫn chưa bao giờ tới tay người dùng cho đến khi chuẩn 802.11 ra đời. IEEE đã đổi tên mạng vô tuyến gói tin thành mạng Adhoc. Ứng dụng: Quân sự: Hoạt động phi tập trung của mạng Adhoc và không phụ thuộc vào cơ sở hạ tầng mạng là một yếu tố thiết yếu đối với lĩnh vực quân sự, nhất là trong các trường hợp chiến đấu khốc liệt, các cơ sở hạ tầng mạng bị phá hủy. Lúc này mạng Adhoc là lựa chọn số một để các thiết bị truyền thông liên lạc với nhau một cách nhanh chóng. Trường học: Chúng ta cũng có thể thiết lập các mạng Adhoc trong trường học, lớp học, thư viện, sân trường,… để kết nối các thiết bị di động (laptop, smartphone) lại với nhau, giúp sinh viên, thầy cô giáo có thể trao đổi bài một cách nhanh chóng thông qua mạng adhoc vừa tạo. Gia đình: Tại nhà bạn có thể tạo nhanh mạng Adhoc để kết nối các thiết bị di động của bạn với nhau, nhờ đó ta có thể di chuyển tự do mà vẫn đảm bảo kết nối truyền tải dữ liệu. Kết nối các thiết bị điện tử với nhau: Trong những năm tới khi mà các thiết bị điện tử đều được gắn các giao tiếp không dây, giúp chúng có thể trao đổi giao tiếp với nhau thì mạng Adhoc sẽ rất phù hợp để tạo nên một hệ thống thông mình có khả năng liên kết với nhau. 3.1.2. Các đặc điểm chính của mạng MANETMỗi nút di động khác nhau trong mạng MANET đều có những đặc điểm về nguồn năng lượng, bộ phận thu phát sóng khác nhau. Chúng có thể di chuyển về mọi hướng theo các tốc độ khác nhau, do đó ta có thể nhận thấy rõ một số đặc điểm chính của mạng MANET như sau:
3.2. Vấn đề định tuyến trong mạng MANET3.2.1 Các thuật toán định tuyến truyền thốngCác giao thức định tuyến truyền thống thường sử dụng hai giải thuật:
Nguyên tắc hoạt động: mỗi router sẻ gửi bảng định tuyến của mình cho tất cả các router được nối trực tiếp với nó . Các router đó so sánh với bảng bảng định tuyến mà mình hiện có và kiểm tra lại các tuyến đường của mình với các tuyến đường mới nhận được, tuyến đường nào tối ưu hơn sẽ được đưa vào bảng định tuyến. Các gói tin cập nhật sẽ được gửi theo định kỳ (30 giây với RIP ,90 giây đối với IGRP) [9]. Ưu điểm: Dễ cấu hình, router không phải xử lý nhiều nên không tốn nhiều dung lượng bộ nhớ và CPU có tốc độ xử lý nhanh hơn. Nhược điểm: - Hệ thống metric quá đơn giản (như Rip chỉ là hop-count ) dẫn đến việc các tuyến đường được chọn vào bảng định tuyến chưa phải tuyến đường tốt nhất. - Vì các gói tin cập nhật được gửi theo định kỳ nên một lượng băng thông đáng kể sẽ bị chiếm. - Do Router hội tụ chậm, dẫn đến việc sai lệch trong bảng địn tuyến gây nên hiện tượng vòng lặp (loop).
Nguyên tắc hoạt động: Các router không gửi bảng định tuyến của mình, mà chỉ gửi tình trạng của các đường liên kết trong cơ sở dữ liệu trạng thái liên kết (linkstate-database) của mình đi cho các router khác, các router sẽ áp dụng giải thuật SPF (shortest path first ), để tự xây dựng bảng định tuyến riêng cho mình. Khi mạng đã hội tụ, các giao thức Link state sẽ không gửi cập nhật định kỳ mà chỉ gửi khi nào có sự thay đổi trong mạng (1 đường bị down , cần sử dụng đường dự phòng). Ưu điểm: Có thể thích nghi được với đa số hệ thống, cho phép người thiết kế có thể thiết kế mạng linh hoạt, phản ứng nhanh với tình huống xảy ra. Do không gởi cập nhật định kỳ như Distance Vector, nên Link State bảo đảm được băng thông cho các đường mạng. Nhược điểm: - Do router phải xử lý nhiều, nên chiếm nhiều bộ nhớ, tốc độ CPU chậm hơn nên tăng độ trễ Việc sử dụng các giao thức định tuyến truyền thống trong mạng MANET sẽ dẫn đến rất nhiều vấn đề trở ngại cần giải quyết:
3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANETCác giao thức định tuyến trong mạng MANET cần đảm bảo:
3.2.3. Phân loại các kỹ thuật định tuyến3.2.3.1. Link state và Distance VectorThuật toán định tuyến vector khoảng cách (distance-vector routing protocols) Thuật toán này dùng thuật toán Bellman-Ford, trong đó chỉ định một con số, gọi là chi phí (hay trọng số), cho mỗi một liên kết giữa các nút trong mạng. Các nút sẽ gửi thông tin về đường đi từ điểm A đến điểm B qua các đường truyền (kết nối) mang lại tổng chi phí thấp nhất (là tổng các chi phí của các kết nối giữa các nút được dùng). Thuật toán hoạt động với những hành động rất đơn giản. Khi một nút khởi động lần đầu, nó chỉ biết các nút kề trực tiếp với nó, và chi phí trực tiếp để đi đến đó (thông tin này, danh sách của các đích, tổng chi phí đến từng đích và bước kế tiếp để gửi dữ liệu đến đó tạo nên bảng định tuyến, hay bảng khoảng cách). Mỗi nút, trong một tiến trình, gửi đến từng “hàng xóm” tổng chi phí của nó để đi đến các đích mà nó biết. Các nút “hàng xóm” phân tích thông tin này, và so sánh với những thông tin mà chúng đang “biết”; bất kỳ điều gì cải thiện được những thông tin chúng đang có sẽ được đưa vào các bảng định tuyến của những “hàng xóm” này. Đến khi kết thúc, tất cả nút trên mạng sẽ tìm ra bước truyền kế tiếp tối ưu đến tất cả mọi đích, và tổng chi phí tốt nhất. Khi một trong các nút gặp vấn đề, những nút khác có sử dụng nút hỏng này trong lộ trình của mình sẽ loại bỏ những lộ trình đó, và tạo nên thông tin mới của bảng định tuyến. Sau đó chúng chuyển thông tin này đến tất cả nút gần kề và lặp lại quá trình trên. Cuối cùng, tất cả nút trên mạng nhận được thông tin cập nhật, và sau đó sẽ tìm đường đi mới đến tất cả các đích mà chúng còn tới được. Thuật toán định tuyến trạng thái kết nối (Link-state routing protocols) Khi áp dụng các thuật toán trạng thái kết nối, mỗi nút sử dụng dữ liệu cơ sở của nó như là một bản đồ của mạng với dạng một đồ thị. Để làm điều này, mỗi nút phát đi tới toàn mạng những thông tin về các nút khác mà nó có thể kết nối được, và từng nút góp thông tin một cách độc lập vào bản đồ. Sử dụng bản đồ này, mỗi nút sau đó sẽ xác định được tuyến đường tốt nhất từ nó đến mọi nút khác. Thuật toán đã làm theo cách này là Dijkstra, bằng cách xây dựng cấu trúc dữ liệu khác, dạng cây, trong đó nút hiện tại là gốc, và chứa mọi nút khác trong mạng. Bắt đầu với một cây ban đầu chỉ chứa chính nó. Sau đó lần lượt từ tập các nút chưa được thêm vào cây, nó sẽ thêm nút có chi phí thấp nhất để đến một nút đã có trên cây. Tiếp tục quá trình đến khi mọi nút đều được thêm vào cây. Cây này sau đó phục vụ để xây dựng bảng định tuyến, đưa ra bước truyền kế tiếp tốt ưu, … để từ một nút đến bất kỳ nút khác trên mạng. So sánh các thuật toán định tuyến Các giao thức định tuyến theo thuật toán vector khoảng cách đơn giản và hiệu quả hơn trong các mạng nhỏ, đòi hỏi ít (nếu có) sự giám sát. Tuy nhiên nhược điểm của nó là khả năng hội tụ chậm khi mạng lớn và thay đổi, điều này dẫn đến sự phát triển của các thuật toán trạng thái kết nối tuy phức tạp hơn nhưng tốt hơn để dùng trong các mạng lớn. Ưu điểm chính của định tuyến bằng trạng thái kết nối là phản ứng nhanh nhạy hơn, và trong một khoảng thời gian có hạn, đối với sự thay đổi kết nối. Ngoài ra, những gói được gửi qua mạng trong định tuyến bằng trạng thái kết nối thì nhỏ hơn những gói dùng trong định tuyến bằng vector. Định tuyến bằng vector đòi hỏi bảng định tuyến đầy đủ phải được truyền đi, trong khi định tuyến bằng trạng thái kết nối thì chỉ có thông tin về “hàng xóm” của nút được truyền đi. Vì vậy, các gói này dùng tài nguyên mạng ở mức không đáng kể. Khuyết điểm chính của định tuyến bằng trạng thái kết nối là nó đòi hỏi nhiều sự lưu trữ và tính toán để chạy hơn định tuyến bằng vector.
Các giao thức định tuyến phản ứng thiết lập tuyến dựa theo từng yêu cầu kết nối. Phương pháp này hạn chế được chi phí tìm đường, nhưng nhược điểm cơ bản là gây trễ lớn cho các khung truyền dẫn đầu tiên cũng như thời gian chọn đường dẫn chậm. Hai giao thức phản ứng điển hình là giao thức định tuyến vector khoảng cách theo yêu cầu AODV (On-demand Distance Vector Routing) và giao thức định tuyến định tuyến nguồn động DSR (Dynamic Source Routing). Một khi xảy ra lỗi tại nút, các giao thức định tuyến thường khôi phục đường dẫn bằng phương pháp thiết lập tuyến mới. Hầu hết các tiếp cận hiện nay đều sử dụng thông tin phản hồi tới thiết bị nguồn nhằm khởi tạo tuyến mới, vì vậy lưu lượng bản tin trao đổi là rất lớn và tăng lên rất nhanh khi kích thước mạng lớn, nhất là đối với các giao thức định tuyến chủ ứng. Khi kích thước mạng tăng cũng đồng nghĩa với sự suy giảm hiệu năng mạng do hiện tượng trễ của thủ tục định tuyến và truyền khung đầu tiên tăng lên rất lớn nếu sử dụng giao thức định tuyến phản ứng.
Trong định tuyến theo chặng, khi một nút nhận được gói tin cần chuyển tới đích, nút đó chuyển tiếp gói tin theo chặng tiếp theo hướng tới đích mà nó biết. Nút tiếp theo lại chuyển tiếp gói tin đến đích theo những chặng mà nó biết dựa vào bảng định tuyến của nó. Quá trình trên sẽ dừng lại khi gói tin được chuyển tới đích. Nhược điểm của phương pháp này là tất cả các nút cần duy trì thông tin định tuyến nên phải xử lý nhiều hơn và có khả năng tạo thành các vòng lặp định tuyến. Каталог: 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:
|