Mạng adhoc và các giao thức định tuyến phổ biến của mạng adhoc

ể nhận gói tin này. Đồng thời đối chiếu xem mình có tên trong ánh xạ định danh truyền thông không. Nếu có tồn tại, nó sẽ giữ nguyên trạng thái “thức” và thực hiện quá trình nhận dữ liệu. Ngược lại, trạm sẽ trở lại trạng thái “nghỉ” và chờ gói beacon kế tiếp. Đối với mạng adhoc, do không có trạm truy cập cơ sở nên các nút mạng phải tự lưu lại dữ liệu mình muốn gửi và gửi định danh của trạm cần gửi dữ liệu đến các trạm xung quanh trong giai đoạn nó thức nhờ sử dụng ánh xạ định danh truyền thông adhoc (Adhoc Traffic Indication Map – ATIM). 2.2.3.3. Quản lý chuyển vùng (hand-off) Trong một khu vực lớn, mạng không dây cần lắp nhiều trạm truy cập cơ sở để có thể mở rộng vùng phủ sóng, giúp người sử dụng có thể truy cập tại bất kì điểm nào trong khu vực đó. Khi một thiết bị không dây di chuyển giữa các điểm trong khu vực, cần có một cơ chế quản lý việc chuyển vùng để đảm bảo tính truyền thông của thiết bị không bị gián đoạn. Việc chuyển vùng này được thực hiện theo các bước: - Một trạm nhận thấy tín hiệu liên kết giữa mình với trạm truy cập cơ sở là quá yếu (tín hiệu quá yếu), nó sẽ tìm kiếm một trạm cơ sở khác cung cấp dịch vụ với một liên kết tốt hơn. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 30 - Trong quá trình quét tín hiệu mạng được chia làm hai dạng là quét chủ động và quét bị động. Quét chủ động là máy trạm trực tiếp phát đi một gói tin tín hiệu đến mỗi kênh truyền và chờ đợi phản hồi từ các kênh truyền đó. Quét thụ động là máy trạm nghe môi trường truyền để tìm ra một BS mới. - Sau khi nhận được tín hiệu phản hồi, trạm cần chuyển vùng sẽ chọn máy trạm cơ sở cung cấp dịch vụ liên kết tốt nhất đến nó và gửi một yêu cầu cung cấp dịch vụ. - Trạm truy cập cơ sở sẽ trả lời yêu cầu của máy trạm chuyển vùng. Nếu chấp nhận thì máy trạm chuyển vùng sẽ gia nhập một BS mới. Ngược lại, nó sẽ phải quét lại để tìm một máy trạm cơ sở mới chấp nhận cho nó tham gia vào BS mới. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 31 Chương 3: Định tuyến trong mạng adhoc 3.1. Giới thiệu về thuật toán định tuyến Trong một hệ thống mạng, một trong những yếu tố ảnh hưởng lớn nhất đến hiệu suất của mạng đó là thời gian truyền các gói tin từ điểm đầu đến điểm cuối sao cho nhanh và chính xác nhất. Để đạt được điều đó thì tầng mạng có nhiệm vụ là tìm đường đi, xác định các router trung gian để chuyển gói tin từ điểm đầu đến điểm cuối. Các thuật toán giúp xác định đường đi như vậy gọi là thuật toán định tuyến. Như vậy chức năng của thuật toán định tuyến chính là xác định đường đi tốt nhất cho gói tin từ bên gửi đến bên nhận. Đối với mạng không dây có cơ sở hạ tầng, việc truyền thông giữa các nút mạng trong mạng phụ thuộc rất nhiều vào base station. Các nút mạng muốn liên lạc với nhau đều phải nằm trong vùng phủ sóng của base station (nếu một nút mạng mà nằm ngoài vùng phủ sóng của base station thì nó không thể nào liên lạc được với các nút mạng khác). Nhưng với mạng adhoc thì lại khác. Các nút mạng dù nằm ngoài vùng phủ sóng của nhau vẫn có thể liên lạc được với nhau thông qua các nút mạng trung gian. Do đó, việc tìm ra các nút mạng trung gian để truyền gói tin giữa nút mạng đầu và nút mạng cuối là rất quan trọng. Ngoài ra, một số đặc điểm khác biệt của mạng adhoc so với các mạng khác như các nút mạng có thể di động, dẫn đến topo mạng thay đổi theo; băng thông của mạng cũng thay đổi liên tục, tốc độ truyền tín hiệu của mạng phụ thuộc nhiều vào tính chất vật lý của các nút mạng và giao diện mạng, ... Chính những đặc điểm này làm cho việc thiết kế các giao thức định tuyến cho mạng adhoc là một bài toán khó. 3.2.Yêu cầu của thuật toán định tuyến cho mạng không dây adhoc Như đã trình bày ở trên, do các đặc điểm khác biệt của mạng adhoc, chúng ta không thể áp dụng các thuật toán định tuyến truyền thống như Trạng thái liên kết (Link State) hay Vector khoảng cách (Distance Vector) cho mạng adhoc được. Cả hai thuật toán này đều yêu cầu các router quảng bá thông tin định tuyến theo kiểu định kì. Những hoạt động này hạn chế khả năng thích ứng của giao thức với các thay đổi của topo mạng. Nếu khoảng thời gian định kỳ khá ngắn, giao thức sẽ hoạt động không hiệu quả bởi nó phải làm việc nhiều hơn so với sự thay đổi của topo mạng và gây lãng phí băng thông và năng lượng của các nút mạng một cách không cần thiết. Còn nếu thời gian định kì quá dài, giao thức sẽ không phản ứng kịp với sự thay đổi của topo mạng. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 32 Với thuật toán Link State, các router sẽ gửi thông tin quảng bá định kì về các hàng xóm và giá của đường đi tới các hàng xóm đến tất cả các router trong mạng. Từ đó, các router sẽ biết được toàn bộ topo của mạng để tính toán đường đi tới đích ngắn nhất có thể. Còn với thuật toán Distance Vector, mỗi router lại gửi định kì các thông tin khoảng cách từ nó đến các router khác. Bằng việc tính toán, so sánh khoảng cách từ mỗi hàng xóm đến một đích nào đó, các router sẽ quyết định tuyến đường đi ngắn nhất đến nút mạng đích. Như vậy, nếu sử dụng các thuật toán thông thường với mạng adhoc có thể dẫn đến một loạt các vấn đề sau: - Đặc điểm đầu tiên của các thuật toán định tuyến thông thường đã không phù hợp với mạng adhoc. Đó là việc các router liên tục gửi quảng bá định kì đến các nút mạng trong mạng. Việc gửi quảng bá định tuyến định kì gây ra hai vấn đề sau: o Thứ nhất, nó sẽ gây lãng phí băng thông cho các nút mạng trong mạng adhoc. Có những khi không có sự thay đổi nào trong mạng nhưng các router tiếp tục gửi các cập nhật thông tin định tuyến theo định kì làm các nút mạng phải tính toán lại các tuyến đường. Nếu trong vùng phủ sóng của một nút mạng có quá nhiều nút mạng khác thì nút mạng này phải nhận rất nhiều thông tin cập nhật định tuyến. Điều này gây lãng phí băng thông một cách không cần thiết. o Thứ hai, việc gửi các cập nhật định tuyến theo định kì cũng gây lãng phí năng lượng không cần thiết cho các nút mạng trong mạng. Chúng ta đã biết năng lượng của các nút mạng trong mạng adhoc chủ yếu là pin. Việc sử dụng năng lượng một cách tiết kiệm và hợp lý là rất cần thiết. Nếu các nút mạng phải gửi quảng bá định tuyến theo định kì sẽ tốn rất nhiều năng lượng, bởi năng lượng để gửi một gói tin không phải là nhỏ. Bên cạnh đó, việc nhận một gói tin tốn ít năng lượng nhưng việc phải cập nhật, tính toán các tuyến đường lại cản trở việc tiết kiệm năng lượng của các nút mạng. - Ở các mạng thông thường, liên kết giữa hai nút mạng trong mạng hoặc giữa nút mạng với base station là các liên kết đối xứng. Trong khi đó, liên kết giữa hai nút mạng của mạng adhoc có thể là liên kết không đối xứng, nghĩa là việc truyền thông giữa hai nút mạng không thể thực hiện tốt trên cả hai hướng. Lý do là vì khả năng truyền tín hiệu của các nút mạng là khác nhau: nút mạng nào có năng lượng truyền tín hiệu mạnh thì nút mạng đó có liên kết tốt với các nút mạng nhận tín hiệu của nó, Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 33 ngược lại, nút mạng có năng lượng truyền tín hiệu yếu thì khả năng không liên kết được với các nút mạng nhận tín hiệu là khó tránh khỏi, nếu có liên kết được thì đó cũng chỉ là những liên kết yếu, không ổn định. Do đó, giao thức định tuyến thông thường không thể hoạt động trong môi trường mạng như vậy. - Một đặc điểm nữa của mạng adhoc làm chúng ta không thể áp dụng được các thuật toán định tuyến thông thường cho nó. Đó là trong mạng adhoc tồn tại nhiều liên kết dư thừa. Với mạng có dây truyền thống, người ta thường chỉ dùng rất ít các router để nối hai mạng với nhau. Vì thế các tuyến đường dư thừa trong mạng có dây là không nhiều và các thuật toán định tuyến thông thường vẫn tính đến cả những liên kết đó. Nhưng với mạng adhoc lại khác. Mỗi nút mạng lại đóng vai trò như một router, mạng adhoc có bao nhiêu nút mạng thì có bấy nhiêu router. Điều này làm cho việc truyền dữ liệu từ nút mạng nguồn đến nút mạng đích có thể phải đi qua nhiều hơn một nút mạng trung gian, và tuyến đường mà dữ liệu di chuyển cũng không phải là duy nhất. Bên cạnh tuyến đường tốt nhất vẫn có thể tồn tại nhiều tuyến đường khác có thể hoạt động bình thường. Với mạng có quá nhiều tuyến đường dư thừa như vậy, các thuật toán định tuyến nếu tính cả đến chúng sẽ làm cho việc cập nhật và tính toán tuyến đường trở lên nhiều hơn. Điều đó là không cần thiết. - Một vấn đề cuối cùng quan trọng hơn cả, đó là các thuật toán đó không được thiết kế dành cho mạng có topo động như của mạng adhoc. Với mạng có dây truyền thống, liên kết giữa các router gần như là không đổi, giá (chất lượng) của một liên kết có thể thay đổi do tắc nghẽn chứ vị trí của các router là cố định trong cấu trúc mạng. Nhưng trong mạng adhoc, điều đó lại không hề có. Với những vấn đề nêu ra ở trên, chúng ta có thể rút ra được một số yêu cầu với các thuật toán định tuyến cho mạng adhoc: - Thuật toán phải được thiết kế sao cho phù hợp với tính động của topo mạng và các liên kết bất đối xứng. - Hoạt động phân tán: cách tiếp cận tập trung cho mạng adhoc sẽ thất bại do sẽ tốn rất nhiều thời gian để tập hợp các thông tin trạng thái hiện tại của mạng để tính toán rồi lại phát tán lại nó cho các nút mạng. Trong thời gian đó, cấu hình mạng có thể đã thay đổi rất nhiều. - Tính toán đến vấn đề năng lượng và băng thông của mạng: Do các nút mạng có nguồn năng lượng hạn chế nên cần phải tính toán đến vấn đề tiết kiệm năng lượng. Giao thức định tuyến có thể cung cấp yêu cầu bảo tồn năng lượng ở các nút mạng khi Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 34 có thể. Băng thông của mạng cũng cần được tính đến để tránh gây lãng phí băng thông không cần thiết. - Không để xảy ra hiện tượng lặp định tuyến: Hiện tượng này xảy ra khi một phần nhỏ các gói tin di chuyển vòng vòng quanh mạng trong một khoảng thời gian nào đó. Giải pháp đưa ra có thể là sử dụng bộ đếm chặng trong mỗi gói tin. Mỗi khi gói tin di chuyển đến một nút mạng mới, bộ đếm chặng sẽ tăng lên một, và đến một giá trị nào đó thì gói tin sẽ bị loại bỏ. - Thiết lập những cụm mạng nhỏ: Nếu giao thức định tuyến có thể xác định được các nút mạng gần nhau và thiết lập chúng thành một cụm mạng nhỏ thì sẽ rất thuận tiện trong định tuyến. Nếu các nút mạng đơn di chuyển nhanh hơn thì các cụm mạng lại ổn định hơn. Do đó, định tuyến trong các cụm mạng sẽ đơn giản hơn rất nhiều. Hình 14: Ví dụ về các cụm mạng nhỏ trong mạng adhoc - Bảo mật: Giao thức định tuyến của mạng adhoc có thể bị tấn công dễ dàng ở một số dạng như đưa ra các cập nhật định tuyến không chính xác hoặc ngăn cản việc chuyển tiếp gói tin, gián tiếp gây ra việc từ chối dịch vụ dẫn đến gói tin không bao giờ đến được đích. Chúng cũng có thể thay đổi thông tin định tuyến trong mạng, cho dù các thông tin đó là không nguy hiểm nhưng cũng gây tốn băng thông và năng lượng, vốn là những tài nguyên ”quý hiếm” trong mạng adhoc. Do vậy cần có những phương pháp bảo mật thích hợp để ngăn chặn việc sửa đổi hoạt động của giao thức. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 35 3.3. Phân loại các thuật toán định tuyến cho mạng adhoc Có rất nhiều giao thức định tuyến trong mạng không dây adhoc. Với mỗi cách tiếp cận khác nhau thì lại có một cách phân loại khác nhau. Song nhìn chung có thể phân thành hai loại chính là định tuyến điều khiển bằng bảng ghi (Table-Driven Routing Protocols) và định tuyến theo yêu cầu khởi phát từ nguồn (Source Initiated On-demand Routing). - Định tuyến điều khiển theo bảng ghi: phương pháp này cố gắng duy trì thông tin định tuyến cập nhật liên tục từ mỗi nút mạng đến mọi nút mạng khác trong mạng. Các giao thức loại này yêu cầu mỗi nút mạng luôn duy trì một hoặc nhiều bảng ghi để lưu trữ thông tin định tuyến, và chúng đáp ứng những thay đổi trong topo mạng bằng cách phát quảng bá rộng rãi các thông tin cập nhật tuyến qua mạng để duy trì tầm kiểm soát mạng một cách liên tục, duy trì một cái nhìn nhất quán về mạng. Các vùng nào khác nhau về số bảng ghi liên quan đến định tuyến cần thiết và các phương thức thay đổi cấu trúc mạng sẽ được phát quảng bá để cho tất cả mọi nút mạng đều có thể biết được - Định tuyến theo yêu cầu khởi phát từ nguồn: Phương pháp này chỉ tạo ra các tuyến khi nút mạng nguồn cần đến. Khi một nút mạng 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. 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. Khi mà một tuyến đã được khám phá và thiết lập, nó được duy trì bởi một số dạng thủ tục cho đến khi tuyến đó không thể truy nhập được từ nút mạng nguồn hoặc là không còn cần thiết đến nó nữa. Sau đây, tôi xin trình bày một số giao thức định tuyến phổ biến trong mạng adhoc: 3.3.1. DSDV (Destination Sequence Distance Vector) DSDV là giao thức định tuyến theo bảng, dựa trên vector khoảng cách theo chặng. Kĩ thuật này vẫn giữ được những nét cổ điển của thuật toán Bellman-Ford nhưng đã được cải tiến để loại bỏ khả năng sinh ra vòng lặp trong các bảng định tuyến để phù hợp với mạng adhoc. Trong thuật toán này, mỗi nút mạng sẽ duy trì một bảng định tuyến chứa các nút mạng đích có thể đến trong mạng và số chặng tới mỗi đích trong mạng. Để duy trì tính nhất quán trong mạng, DSDV yêu cầu các nút mạng phát quảng bá định kỳ các cập nhật định tuyến tới các nút mạng hàng xóm và phát ngay các cập nhật khi có những thay đổi quan trọng xảy ra trong mạng. Ngoài để tránh việc các thông tin định tuyến Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 36 được phát quảng bá quá nhiều khi topo mạng có những thay đổi nhanh, DSDV sử dụng một cơ chế hãm các cập nhật tức thời khi có các thay đổi quá nhanh xảy ra trong mạng. Với cơ chế này, DSDV sử dụng hai loại thông điệp cập nhật: cập nhật đầy đủ – chứa tất cả thông tin định tuyến hiện có và cập nhật thông tin bổ sung – mang những thông tin về những thay đổi từ lần cập nhật đầy đủ gần nhất. Để làm được điều này, DSDV sử dụng hai bảng ghi khác nhau, một để chuyển tiếp các gói tin, một để phát các gói tin cập nhật bổ sung. Thực tế, nếu những thay đổi trong mạng không xảy ra một cách thường xuyên thì những thông điệp cập nhật đầy đủ sẽ ít được sử dụng. Thay vào đó là những gói tin cập nhật bổ sung. Do đó, các nút mạng di động cũng phải sử dụng một bảng ghi để nhớ những thông tin của các gói cập nhật bổ sung này. Ngoài ra để tránh lặp tuyến, DSDV còn sử dụng số thứ tự gắn với mỗi đường. Số thứ tự này xác định độ mới của tuyến đường, cho phép các nút mạng di động có thể phân biệt được các tuyến đường mới và các tuyến đường cũ. Số thứ tự của tuyến đường được tăng lên 1 mỗi khi có một tuyến đường mới được phát quảng bá. Đường có số thứ tự cao hơn được xem là tốt hơn. Nếu hai đường có cùng số thứ tự, đường nào có số chặng ít hơn sẽ được sử dụng. Khi có một liên kết hỏng (nút mạng không nhận được các quảng bá định kì), trong lần quảng bá sau, nút mạng phát hiện ra liên kết hỏng sẽ phát quảng bá đường tới đích có số chặng là vô cùng và tăng thứ tự đường. Destination Next Hop Metric Seq.No Install Time Stable Data A A 0 A-864 001000 Ptr_A B B 1 B-470 001200 Ptr_B C B 3 C-920 001500 Ptr_C D B 4 D-502 001200 Ptr_D Hình 15: Ví dụ về bảng định tuyến khi dùng thuật toán DSDV Trên đây là hình vẽ miêu tả một bảng định tuyến trong DSDV. Trong đó, next hop là chặng tiếp theo, metric là số các chặng để tới đích, Seq.no là số thức tự của quảng cáo cuối cùng tới nút mạng và install time là thời gian đường được cài đặt lần đầu tiên. Ngoài ra, bảng còn chứa các trường nút mạng đích (Destination) và thời gian tồn tại của các đường (Stable Data). Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 37 3.3.2. AODV (Adhoc On-Demand Distance Vector Routing) AODVlà giao thức định tuyến dựa trên giao thức DSDV được trình bày ở trên. Nó cùng được phát triển bởi C. Perkins và S. Das tại trung tâm nghiên cứu Nokia thuộc trường đại học California và đại học Cincinnati. Giống như DSDV, AODV cũng loại bỏ được vấn đề lặp định tuyến của các giao thức Distance Vector khác bằng việc dùng số thứ tự gắn với mỗi đường. Tuy nhiên, nếu như DSDV luôn duy trì một danh sách các tuyến đường hoàn chỉnh, AODV chỉ tạo ra các tuyến đường khi được yêu cầu. Điều này giúp nó tối thiểu hóa được việc phát quảng bá trong mạng. Mỗi nút mạng trong mạng sẽ duy trì một bảng ghi định tuyến chứa thông tin về đường đi (như địa chỉ đích, số thứ tự đích, số chặng, chặng tiếp theo, thời gian tồn tại của đường, các nút mạng hàng xóm, thông tin ghi nhận các yêu cầu đã được xử lý) mà nút mạng giao tiếp. Với những nút mạng không nằm trên đường đi đến đích thì không cần phải duy trì thông tin định tuyến hoặc tham gia vào việc trao đổi các bảng định tuyến. Để phát hiện và duy trì liên kết, AODV sử dụng các thông điệp khác nhau là Route REQuest (RREQ) và HELLO. Khi nút mạng nguồn muốn gửi một gói tin đến nút mạng đích mà tuyến đường chưa được xác lập, nó sẽ gửi thông điệp yêu cầu tuyến đường RREQ đến tất cả các nút mạng hàng xóm. Quá trình này chỉ dừng lại khi gói RREQ tới được đích hoặc một nút mạng có đường đi tới đích. Tại các nút mạng đã đi qua, RREQ cũng lưu định danh các nút mạng để tạo đường quay trở về nguồn tạm thời. Đồng thời, các nút mạng cũng lưu định danh của các RREQ đã nhận để loại bỏ các RREQ được gửi lại. Hình 16: Quá trình truyền của RREQ Khi RREQ tới được đích hoặc nút mạng có đường tới được đích, gói tin trả lời Route REPly (RREP) được khởi tạo và được chuyển về nút mạng nguồn theo tuyến Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 38 đường tạm thời mà gói RREQ thiết lập. Trong quá trình đó, RREP thiết lập đường hướng đến đích tại các nút mạng chuyển tiếp. Khi RREP đến được nút mạng nguồn cũng là lúc tuyến đường từ nguồn tới đích được thiết lập. Nếu nút mạng nguồn không nhận được gói tin RREP, nút mạng sẽ gửi lại thông điệp RREQ hoặc giả thiết không có đường tới đích. Mặt khác, do RREP được chuyển tiếp dọc theo các tuyến đường được RREQ thiết lập nên AODV chỉ có thế hỗ trợ tìm đường đi qua các liên kết đối xứng. Hình 17: Đường đi của gói tin RREP trở về nguồn Để cảm nhận và duy trì các liên kết, AODV sử dụng thông điệp HELLO phát quảng bá định tuyến đến các hàng xóm. Thông điệp này cho biết sự tồn tại của nút mạng và liên kết tới nút mạng đó vẫn hoạt động. Khi thông điệp HELLO không đến được nút mạng hàng xóm nào đó, điều đó chứng tỏ liên kết bị hỏng. Nút mạng gửi HELOO sẽ đánh dấu liên kết đến hàng xóm đó là hỏng và gửi thông điệp Route ERRor (RERR) báo lỗi tới tất cả các nút mạng liên quan. Việc phát hiện lỗi này là do lớp vật lý và lớp liên kết thực hiện. 3.3.3. DSR (Dynamic Source Routing) DSR là thuật toán định tuyến phổ biến trong mạng adhoc hiện nay. So với các thuật toán định tuyến khác, nó có những điểm vượt trội hơn như: không phát quảng bá định tuyến định kì, hỗ trợ tìm đường đi qua cả các liên kết không đối xứng và phù hợp với tính động của topo mạng. DSR chia cơ chế định tuyến thành hai phần là cơ chế tìm kiếm đường đi (Route Discovery) và cơ chế duy trì tuyến đường (Route Maintenance). DSR sử dụng kĩ thuật định tuyến nguồn (source route). Theo đó, khi muốn gửi một gói tin, một tuyến nguồn sẽ được hình thành và lưu ở tiêu đề của gói tin. Tuyến Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 39 nguồn này chứa một danh sách có thứ tự và đầy đủ về các nút mạng cần đi qua để tới đích. Do đó, các nút mạng trung gian chỉ cần duy trì liên kết với các nút mạng hàng xóm để chuyển tiếp các gói tin. Nút mạng nguồn thì cần biết toàn bộ thứ tự tuyến đường để đến đích. Mỗi nút mạng đều duy trì một bộ nhớ gọi là route cache để lưu các tuyến đường khởi đầu từ nút mạng này mà nó tìm được. Khi có yêu cầu về tìm đường đi, nút mạng sẽ kiểm tra trong route cache có tuyến đường mà nó mong muốn hay không. Nếu có, tuyến đường này sẽ được sử dụng để truyền gói tin. Ngược lại, cơ chế tìm kiếm đường đi sẽ được khởi động bằng việc phát quảng bá đi một gói tin yêu cầu đường (Route Request). Khi một nút mạng nhận được gói tin yêu cầu, nó sẽ kiểm tra trong route cache của mình có địa chỉ nút mạng đích hay không. Nếu không có, nó lại chuyển gói tin đó sang nút mạng hàng xóm của mình, đồng thời, bổ sung địa chỉ của nó vào thứ tự chặng được lưu trong gói tin yêu cầu. Gói tin yêu cầu được truyền trong mạng cho tới khi tới được nút mạng đích hoặc nút mạng có chứa đường đi đến nút mạng đích. Khi đường được tìm thấy, gói tin trả lời (route reply) chứa toàn bộ tuyến đường sẽ được gửi trở lại nút mạng nguồn. Lúc này cũng cần phải có một cơ chế để loại bỏ gói tin Route Request để tránh cho nó truyền vô hạn trong mạng. Do đó, DSR thêm vào tiêu đề của gói một trường time-to-live. Mỗi khi qua một nút mạng, trường time-to-live sẽ được tăng lên một, khi time-to-live vượt quá một giá trị nào đó, nó sẽ bị loại bỏ. Ngoài ra để giảm thời gian tìm kiếm đường, các nút mạng thường xuyên bổ sung những tuyến đường mới mà nó học được trong quá trình các nút mạng khác chọn đường. Trong quá trình sử dụng route cache để ghi dữ liệu, các nút mạng vẫn có thể theo dõi sự thay đổi của các liên kết thông qua cơ chế duy trì tuyền đường. Cơ chế duy trì tuyến đường thực hiện biên nhận theo chặng hoặc biên nhận đầu cuối, kèm theo đó là cơ chế thông báo lỗi khi có liên kết bị đứt gẫy. Khi gói tin Route Error được gửi về nút mạng nguồn, nó sẽ xoá bỏ liên kết bị hỏng ra khỏi route cache và tất cả các đường có chứa chặng này được cắt tại điểm có liên kết hỏng. Ngoài ra, các nút mạng trung gian chuyển tiếp gói tin route error có thể cập nhật route cache theo cách tương tự. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 40 Hình 18: Quá trình tìm kiếm đường của DSR Hình 19: Gửi trả lại tuyến đường về cho nút nguồn 3.3.4. TORA (Temporally Ordered Routing Algorithm) TORA là giao thức định tuyến phân bố không lặp vòng và độ thích nghi cao dựa theo phương thức đảo ngược các liên kết. TORA được đề xuất cho môi trường nối mạng có tính linh động cao. Giao thức được thiết kế để phát hiện đường theo yêu cầu, cung cấp nhiều đường, thiết lập đường nhanh và tối thiểu hóa chi phí truyền thông bằng cách cục bộ hóa phản ứng của giải thuật đối với các thay đổi cấu hình khi có thể. Giao thức chỉ phản ứng khi tất cả đường tới đích bị mất. Giao thức thực hiện ba chức năng cơ bản: tạo tuyến, duy trì tuyến và xóa tuyến. Giống như các giao thức đảo ngược liên kết khác, việc tạo đường về cơ bản là thực hiện gán các hướng cho các liên kết trong một mạng hoặc phần mạng vô hướng hình thành nên đồ thị có hướng không có vòng lặp (Directed Acyclic Graph - DAG) có gốc đặt tại đích. TORA gắn cho mỗi nút mạng trong mạng một độ cao tương ứng. Các thông điệp trong mạng được truyền từ các nút mạng có độ cao lớn hơn đến các nút mạng có độ Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 41 cao thấp hơn. Để phát hiện tuyến đường, TORA sử dụng hai gói tin truy vấn (QUERY) và cập nhật (UPDATE). Khi một nút mạng cần đường đi đến đích, nó sẽ phát quảng bá gói tin truy vấn QUERY. Gói tin sẽ được truyền qua mạng cho đến khi gặp nút mạng đích hoặc gặp nút mạng có đường đi đến nút mạng đích. Khi nút mạng nào nhận được gói tin truy vấn QUERY, nó sẽ gửi phản hồi trở lại gói tin cập nhật (UPDATE) có chứa trọng số của nút mạng đó. Các nút mạng nhận được gói tin cập nhật này sẽ phải thiết lập lại trọng số của nó lớn hơn trọng số của nút mạng hàng xóm gửi gói tin cập nhật cho nó. Cơ chế duy trì tuyến đường thực ra chính là phản ứng của TORA với các thay đổi cấu hình trong mạng. Khi một nút mạng nào đó phát hiện ra đường đi tới đích không còn hợp lệ, nó sẽ điều chỉnh độ cao của mình là lớn nhất so với nút mạng hàng xóm, đồng thời phát đi một gói tin UPDATE. Các tuyến đường được đảo ngược để phản ánh những thay đổi để 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 tuyến đường khi một nút mạng không có tuyến đường xuống các nút mạng dưới. Khi mà có nút mạng nào đó không còn tuyến đường đi đến nút mạng đích, nó sẽ bị đánh dấu là vô hướng và bị xóa ra khỏi đường đi. Việc xóa các tuyến không còn hiệu lực của TORA bao gồm việc phát quảng bá đi thông điệp CLEAR tới toàn mạng. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 42 Chương 4: Đánh giá hiệu suất các giao thức định tuyến bằng bộ mô phỏng mạng NS2 4.1. Giới thiệu bộ mô phỏng NS2[4],[5] NS2 là bộ mô phỏng mạng vận hành theo sự kiện rời rạc (Discrete Event-Drivent Simulator), được phát triển như một phần của dự án VINT (Virtual Internet Testbeb). Nó được xây dựng dựa trên hai ngôn ngữ là C++ và OTcl. Phần “nhân” của nó ít thay đổi được viết bằng ngôn ngữ C++, bao gồm các module thực hiện mô phỏng và các chức năng cơ bản nhất của mạng. Phần vỏ được viết bằng ngôn ngữ Otcl, là một dạng ngôn ngữ kịch bản, thực hiện việc định cấu hình và điều khiển mô phỏng. Hình 20: Tiến trình hoạt động của một trình mô phỏng Hình trên cho ta thấy, NS2 là bộ thông dịch ngôn ngữ kịch bản hướng đối tượng Otcl bao gồm bộ lập lịch sự kiện, các thành phần mạng và các module thiết đặt mạng. Để cài đặt và chạy chương trình, người ta phải viết một chương trình mô phỏng bằng ngôn ngữ kịch bản Otcl. Chương trình này sẽ khởi tạo bộ lập lịch, thiết lập cấu hình mạng với các đối tượng mạng và các hàm thiết đặt mạng. Trong quá trình chạy chương trình, chúng ta có thể quan sát trực quan các sự kiện qua công cụ NAM. Khi kết thúc quá trình chạy, kết quả mô phỏng sẽ được ghi lại trong các file vết (trace file). Chúng ta có thể đánh giá, phân tích mạng thông qua các file này. Ngày nay, NS2 có thể coi là một công cụ quan trọng để nghiên cứu, thiết kế và mô phỏng mạng. Với những mạng quy mô lớn, việc thiết kế, đánh giá hiệu suất mạng trước khi triển khai là vô cùng quan trọng vì nó giúp hạn chế xảy ra các sự cố như ắc nghẽn mạng hay hiệu suất mạng không được như mong muốn. Vì là một phần mềm mã nguồn mở nên nó có thể cài được trên cả Windows 32 bit hay Linux. Cộng đồng sử Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 43 dụng NS2 cũng rất lớn: trên một nghìn trường đại học, viện nghiên cứu, ... với hơn mười nghìn người sử dụng trên toàn thế giới. 4.2. Khả năng mô phỏng các mạng của NS2 NS2 có thể hỗ trợ những người nghiên cứu mạng những điểm sau: - Khả năng trừu tượng hóa: giúp nghiên cứu các giao thức mạng ở nhiều mức khác nhau, từ hành vi đơn lẻ của một giao thức đến kết hợp của nhiều luồng dữ liệu và tương tác của nhiều giao thức. Điều này giúp người nghiên cứu có thể dễ dàng so sánh và phân tích các kết quả chi tiết với trừu tượng. - Khả năng tương tác với mạng thực: Cho phép chương trình mô phỏng đang chạy tương tác với các nút mạng đang hoạt đông. - Khả năng tạo ngữ cảnh: Người nghiên cứu có thể tạo các mẫu lưu lượng, các hiện trạng mạng phức tạp và các sự kiện động như lỗi liên kết một cách dễ dàng. Điều này giúp cho việc nghiên cứu, kiểm chứng các giao thức mạng trong các mô hình mạng khác nhau được đúng đắn hơn. - Khả năng trực quan hóa: Thông qua công cụ NAM, người nghiên cứu có thể nhìn trực quan các hoạt động của mạng, từ đó dễ dàng hiểu được các hành vi phức tạp của mô phỏng mạng. - Khả năng mở rộng được: NS2 cho phép mở rộng các chức năng mới một cách dễ dàng; ví dụ thêm nút mạng, thay đổi các giao thức truyền dữ liệu, ... Vì thế có thể thực hiện nghiên cứu các giao thức mới. 4.3. Mô phỏng mạng adhoc và các giao thức định tuyến trong mạng adhoc 4.3.1. Mô phỏng mạng adhoc Các mạng adhoc được mô tả dựa trên hai mô hình là mô hình di chuyển thể hiện sự chuyển động của các nút trong mạng và mô hình truyền thông thể hiện khuôn dạng truyền thông giữa các nút trong mạng. 4.3.1.1. Các mô hình di chuyển Có ba mô hình tiêu biểu mô phỏng mạng adhoc trong NS2 là: Random Waypoint, Random Walk, và Random Direction. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 44 - Mô hình Random Waypoint: Theo mô hình này, có hai khái niệm là thời gian tạm dừng (khoảng thời gian mà một nút không thay đổi vị trí của mình) và tốc độ di chuyển của nút từ vị trí này sang vị trí khác. Bốn tham số được sử dụng để xây dựng mô hình này là: Speedmin(tốc độ nhỏ nhất), Speedmax(tốc độ lớn nhất), Pmin(thời gian tạm dừng nhỏ nhất), Pmax(thời gian tạm dừng lớn nhất). Ban đầu nút ở một vị trí bất kì trong khu vực mô phỏng và thời gian tạm dừng của nó là P1 (P1 được chọn theo phân bố đồng đều trong [Pmin, Pmax]). Sau khi hết khoảng thời gian P1, nút sẽ di chuyển đến vị trí mới trong khu vực mô phỏng với tốc độ được chọn trong [Speedmin, Speedmax]. Sau đó quá trình lại tiếp tục được lặp lại. Mô hình này rất linh động, nó mô tả theo cách người ta di chuyển trong các hội nghị. Đây là mô hình phổ biến nhất trong các nghiên cứu về mạng adhoc. - Mô hình Random Walk : Mô hình mô phỏng chuyển động ngẫu nhiên của các thực thể trong tự nhiên. Nút mạng di chuyển từ vị trí hiện tại đến vị trí khác bằng việc chọn ngẫu nhiên một hướng [0o,180o], với tốc độ [Speedmin, Speedmax] trong khoảng thời gian là travel_time (khoảng thời gian di chuyển). Không có khái niệm khoảng thời gian tạm dừng trong mô hình này. Trong mô hình này, tham số thay đổi hướng của nút di động quyết định đến độ phức tạp của mạng. Tham số này càng lớn thì mạng càng phức tạp. - Mô hình Random Direction: Nút mạng sẽ chọn một hướng ngẫu nhiên, di chuyến với tốc độ được phân bố đồng đều trong khoảng [Speedmin,Speedmax]. Khi đến biên của khu vực mô phỏng, nút mạng sẽ dừng lại ở đó trong một khoảng thời gian [Pmin, Pmax] trước khi chọn một hướng khác và tiếp tục quá trình. Mô hình này được xây dựng để khắc phục số trung bình các hàng xóm cao và ít thay đổi trong mô hình Random Waypoint với sự tập trung của các nút tại trung tâm khu vực mô phỏng. Số chặng trung bình của các gói tin dữ liệu sử dụng mô hình Random Direction sẽ nhiều hơn số chặng trung bình của các mô hình mạng khác. 4.3.1.2. Mô hình mạng truyền thông Các mô hình truyền thông được mô tả trong NS2 gồm hai loại là: bộ tạo truyền thông (traffic generator) và các ứng dụng mô phỏng (simulated application). Các bộ Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 45 tạo truyền thông sử dụng giao thức UDP để truyền các gói tin và các ứng dụng mô phỏng sử dụng giao thức TCP. Bộ tạo truyền thông có nhiệm vụ là gửi các gói tin có kích thước không đổi với tốc độ cố định. Bộ tạo truyền thông có bốn loại là: lũy thừa, pareto, CBR và theo file vết. Các ứng dụng mô phỏng có hai loại là Telnet và FTP. 4.3.2. Mô phỏng các giao thức định tuyến trong mạng adhoc [1, T.Việt], [4], [5] Bốn giao thức định tuyến được NS2 hỗ trợ sẵn trong mạng adhoc đó là : DSDV, AODV, DSR và TORA. Do thời gian có hạn nên tôi xin phân tích và so sánh các giao thức định tuyến của mạng adhoc thông qua các kết quả mô phỏng sẵn có của một số người nghiên cứu đi trước. Sau đây là các tham số hoạt động của bốn giao thức trên và một số lưu ý khi cài đặt các giao thức trong mô phỏng theo tài liệu của NS2 và các file cài đặt các giao thức: 4.3.2.1. Giao thức DSDV Các tham số hoạt động của DSDV trong mô phỏng là: Tham số Giá trị Quãng cập nhật đường định kỳ 15s Số cập nhật định kỳ bị mất trước khi liên kết được xem là bị hỏng 3 Thời gian cập nhật tức thời đầu tiên được giữ lại trong hiệu ứng hãm 6s Thời gian kết hợp các quảng cáo đường 1s Số lượng các gói tin lớn nhất trong bộ đệm mỗi nút 5 Bảng 1: Các tham số hoạt động của DSDV trong mô phỏng Trong giao thức DSDV, thông điệp được trao đổi giữa các nút hàng xóm. Các cập nhật có thể là định kì hoặc tức thời. Cập nhật tức thời chỉ xảy ra khi bảng định tuyến của một nút bị thay dổi bởi thông tin định tuyến của một trong các nút hàng xóm. Các gói tin chưa có đường đến đích sẽ được lưu lại trong bộ đệm khi truy vấn về đường được gửi. Khi nhận được trả lời đường từ nút đích, các gói tin sẽ được chuyển đi. Kích thước của bộ đệm để lưu các gói tin đang chờ thông tin về đường được quy định sẵn. Nếu quá khả năng này, gói tin sẽ bị loại bỏ. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 46 Tất cả các gói tin có đích là nút di động được bộ phận tách địa chỉ đưa đến bộ phận tách cổng. Bộ phận tách cổng sử dụng một trong 255 cổng để chuyển gói tin đến đích tương ứng. Đích mặc định trong bộ phân tách địa chỉ là thành phần định tuyến. Khi đích của gói tin không được tìm thấy bởi bộ phân tách địa chỉ, gói tin sẽ được chuyển cho đích mặc định. Thành phần định tuyến gắn chặng tiếp theo của gói tin và gửi nó xuống lớp liên kết. 4.3.2.2. Giao thức AODV Các tham số hoạt động của giao thức AODV Tham số Giá trị Thời gian đường được xem là hợp lệ 300s Thời gian tồn tại của RREP được gửi bởi đích 600s Số RREQ được phát lại 3 Thời gian trước khi một RREQ được phát lại 6s Thời gian broadcastID của một gói tin RREQ được giữ 3s Thời gian đường đi ngược lại cho RREP được giữ 3s Thời gian trước khi liên kết bị hỏng được xóa khỏi bảng định tuyến 3s Phát hiện liên kết hỏng bằng lớp MAC có Bảng 2: Các tham số hoạt động của AODV trong mô phỏng Trong đặc tả của giao thức AODV, các nút mạng phát hiện các nút hàng xóm thông qua việc gửi thông điệp HELLO theo định kì. Khi mô phỏng AODV bằng NS2, việc phát hiện liên kết hỏng được thay thế bằng thông báo từ tầng MAC. Điều này giúp loại bỏ được tổng phí của việc gửi định kì các thông điệp HELLO. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 47 4.3.2.3. Giao thức DSR Các tham số đặc tả DSR trong mô phỏng: Tham số Giá trị Thời gian giữa các ROUTE REQUEST được phát lại 500ms Kích thước tiêu đề gói tin mang địa chỉ đường với n chặng 4n + 4byte Thời gian hết hạn tìm kiếm đường trong các hàng xóm 30ms Thời gian giữ các gói tin chờ đường 30s Tốc độ cao nhất việc gửi các gói tin REPLY cho một đường 1/s Bảng 3: Các tham số hoạt động của DSR trong mô phỏng Tất cả các gói tin được nhận bởi nút mạng đều được chuyển đến thành phần định tuyến theo mặc định. Tại đây có ba trường hợp xảy ra: - Thành phần định tuyến DSR nhận gói tin cho chính nó bằng việc chuyền gói tin tới bộ phận tách cổng.. - Chuyển tiếp gói tin theo thông tin về đường trong gói tin - Gửi các yêu cầu về đường và trả lời đường. Mặc dù DSR hỗ trợ đường đi đơn hướng, nhưng do IEEE802.11 yêu cầu trao đổi RTS/CTS/DATA/ACK đối với các gói tin unicast nên DSR trong NS2 chỉ phát hiện các đường đi hai chiều. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 48 4.3.2.4. Giao thức TORA Các tham số hoạt động của TORA theo mô phỏng: Tham số Giá trị Quãng thời gian phát các BEACON 1s Thời gian liên kết được xem là bị hỏng khi không có các thông tin BEACON hoặc HELLO được trao đổi 3s Thời gian phát lại object block khi không nhận được biên nhận 500ms Thời gian object block không được phát lại và liên kết tới đích được xem là bị hỏng 1500ms Bảng 4: các tham số hoạt động của TORA trong mô phỏng Trong mô phỏng, TORA được đặt trên giao thức IMEP (Internet MANET Encapsulation Protocol). Giao thức này có các đặc điểm chính sau: - Phát tin cậy và đúng thứ tự các gói tin định tuyến của TORA tới các hàng xóm và thông báo cho giao thức về liên kết tồn tại với các hàng xóm. - Trước khi tiến hành phát, IMEP kết hợp các gói tin định tuyến của TORA với IMEP thành một gói tin gọi là object block. - Để cảm nhận trạng thaí liên kết và duy trì danh sách hàng xóm, IMEP gửi gói tin beacon. Các nút nhận được gói tin beacon sẽ trả lời bằng gói tin HELLO. 4.4. Phân tích và so sánh hiệu suất của các giao thức định tuyến trong mạng adhoc 4.4.1. Các tham số của môi trường: Do đặc thù của mạng adhoc là topo mạng động, băng thông hạn chế, khả năng liên kết giữa các nút mạng có thể thay đổi, nên việc phân tích hiệu suất của các giao thức trong mạng adhoc phải xét đến các tham số sau: - Độ lớn của mạng: được thể hiện bằng số các nút mạng. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 49 - Kết nối mạng: được thể hiện thông qua số lượng trung bình các hàng xóm của một nút. - Tốc độ biến thiên của mạng: là thay đổi cấu hình vật lý của mạng theo thời gian. - Khả năng liên kết: băng thông của liên kết không dây tính bằng bps. - Dạng truyền thông: có thể là đồng dạng, không đồng dạng hoặc bùng phát. Đây chính là mức độ tải trong mạng. - Dạng di chuyển: chính là hình thái của mạng được thể hiện tương ứng theo không gian và thời gian. 4.4.2. Các thông số đánh giá hiệu suất: Đối với hệ thống nói chung, hiệu suất là độ đo công việc mà hệ thống thực hiện được bao gồm tính sẵn sàng, thông lượng, và thời gian đáp ứng. Vì thế, ở đây người ta đã sử dụng các thông số sau để đánh giá hiệu suất của các giao thức định tuyến trong mạng mô phỏng: - Phần trăm gói tin được gửi thành công: Là tỉ lệ giữa số lượng các gói tin đến được đích với số lượng các gói tin được tạo ra bởi nút phát. - Trễ đầu cuối trung bình của các gói dữ liệu: Là tổng độ trễ được tính từ khi nút nguồn phát gói tin đến khi nút đích nhận được gói tin. Nó bao gồm các độ trễ có thể như trễ do quá trình phát hiện đường, xếp hàng tại các hàng đợi, trễ do phát lại tại tầng MAC và trễ thời gian truyền. Hai độ đo này đánh giá kết quả hoạt động của giao thức định tuyến. Nó có ý nghĩa đối với hoạt động của giao thức lớp trên như giao thức giao vận và giao thức ứng dụng. Ngoài ra, đối với mạng adhoc, việc hạn chế tài nguyên mạng đòi hỏi các giao thức phải sử dụng hiệu quả các tài nguyên này. Với giao thức định tuyến, đó chính là chi phí để thực hiện các yêu cầu định tuyến. Do đó, người ta đã xét thêm một thông số nữa để thể hiện việc sử dụng các tài nguyên mạng. Đó là tải định tuyến chuẩn hóa: là tỉ lệ giữa số các gói tin định tuyến trên số gói tin dữ liệu được gửi đi. Nếu gói tin định tuyến đi qua nhiều chặng thì mỗi chặng được tính như là một truyền thông. 4.4.3. Các thí nghiệm mô phỏng [1, T.Việt] 4.4.3.1. Mục đích của các thí nghiệm: Đánh giá khả năng của các giao thức định tuyến trước sự thay đổi của topo mạng. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 50 4.4.3.2. Phương pháp thực hiện: Áp dụng các dạng di chuyển khác nhau với các mức tải khác nhau. Các mạng adhoc được mô phỏng dựa trên các mô hình di chuyển và mô hình truyền thông. Các mô hình di chuyển được sử dụng là ba mô hình Random Waypoint, Random Walk và Random Direction. Với mỗi mô hình, các tham số của mạng được thay đổi để các trạng thái của mạng như kết nối mạng, thời gian và tốc độ chuyển động của các nút mạng thay đổi theo. Các mức tải mạng của từng mạng cũng là khác nhau. Để việc đánh giá được chính xác, các điều kiện tải và môi trường áp dụng với các giao thức phải giống nhau. Mô hình truyền thông được sử dụng ở đây là mô hình CBR. 4.4.3.3. Đánh giá các thí nghiệm với từng mô hình mạng - Mô hình Random Waypoint Xét về phần trăm gói tin gửi thành công: Khi số nguồn phát nhỏ các giao thức hoạt động khá tốt, ngoại trừ giao thức TORA. Kết quả không tốt của giao thức TORA là do sự tắc nghẽn trong cơ chế làm việc của giao thức. Điều này thể hiện rất rõ ở độ trễ trong việc gửi các gói và tải định tuyến cao của TORA. Các giao thức AODV, DSR thể hiện làm việc tốt hơn so với DSDV. Khi số nguồn phát được tăng lên, khả năng gửi các gói tin của các giao thức đã có sự phân biệt khá rõ rệt. AODV có hiệu suất cao hơn so với DSDV. Và hiệu suất của giao thức DSR giảm xuống rõ rệt. Điều này chứng tỏ trong môi trường tải tăng, cơ chế làm việc của DSR chưa đạt được phản ứng tốt. Hoạt động yếu kém của giao thức TORA cũng đã khẳng định hơn nữa sự không hiệu quả của giao thức này khi một động trong môi trường tải tăng và cấu hình có nhiều thay đổi. Như vậy, khi mà số nguồn phát và sự di chuyển tăng lên thì phần trăm gửi thành công các gói tin của các giao thức định tuyến đều giảm. Xét độ trễ trung bình trong việc gửi các gói tin: Ta thấy rằng, độ trễ trung bình của các giao thức DSDV và AODV là tương đương nhau. Độ trễ trung bình của hai giao thức này là khá thấp. Ngay cả khi nguồn phát có tăng lên và mức độ di chuyển khác nhau, độ trễ trung bình của hai giao thức cũng chỉ tăng lên một cách không đáng kể. Với giao thức DSR, độ trễ đầu cuối trung bình của giao thức này thể hiện sự nhạy cảm rõ rệt với sự di chuyển của các nút mạng và tăng nguồn phát. Độ trễ đầu cuối của DSR tăng khi mà thời gian tạm dừng giảm và số nguồn phát tăng lên. Độ trễ đầu cuối trung bình của giao thức TORA rất cao và tăng mạnh khi sự di chuyển của các nút mạng gia tăng. Đó là do xảy ra tắc nghẽn trong hoạt động mạng của TORA. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 51 Một yếu tố quan trọng nữa trong việc đánh giá hiệu suất của các giao thức là việc sử dụng hiệu quả các tài nguyên mạng thông qua tải định tuyến. Trong trương hợp tải thấp và mức độ di chuyển không cao, tải định tuyến của các giao thức AODV và DSR thấp hơn so với DSDV. Đó là do các giao thức này không thực hiện định tuyến theo yêu cầu nên số gói tin định tuyến thay đổi không đáng kể. Tuy nhiên, khi mà các nút mạng di chuyển nhanh và số nguồn phát tăng lên, tải định tuyến của hai giao thức định tuyến này lại tăng lên nhanh chóng. Đó là do sự bùng phát của các gói tin phát hiện đường, trả lời đường và thông báo lỗi. Tải định tuyến cao có thể gây ra hạn chế về băng thông của toàn mạng và dẫn đến tắc nghẽn. Điều này có thể nhận thấy rõ nhất ở giao thức định tuyến TORA. Có thể kết luận rằng, hiệu suất của giao thức TORA là rất thấp trong mô phỏng. - Mô hình Random Walk Trong mô hình này, với cấu hình mạng thay đổi ở mức trung bình, điều dễ nhận thấy nhất là giao thức TORA hoạt động hiệu quả hơn so với mô hình Random Waypoint. Tuy nhiên, trong trường hợp nguồn phát tăng, tỉ lệ phần trăm gửi thành công các gói tin của TORA lại thấp hơn nhiều so với các giao thức khác. Trong cả hai trường hợp ít và nhiều nguồn phát, phần trăm gửi thành công của giao thức DSDV vẫn thấp hơn so với hai giao thức AODV và DSR. Ngoài ra, hiệu suất của các giao thức này là khá ổn định kể cả khi nguồn phát có tăng lên. Trễ đầu cuối trung bình của các giao thức AODV và DSR vẫn tốt hơn so với DSDV. So với mô hình trên, kết quả này không có gì khác biệt. Khi mà nguồn, phát tăng lên, giao thức AODV có phản hồi tốt nhất so với các giao thức còn lại. Trong khi đó, cơ chế của TORA gây tắc nghẽn làm đỗ trễ trung bình đầu cuối tăng cao. So với mô hình Random Waypoint, DSDV vẫn có mức tải định tuyến thấp và khá ổn định, DSR có mức tải định tuyến thấp. AODV có mức tải ổn định trong cả hai trường hợp số lượng nguồn phát là nhiều hay ít. Riêng với TORA, việc xảy ra tắc nghẽn khi số lượng nguồn phát tăng được thấy rõ qua việc tải định tuyến rất cao. - Mô hình Random Direction So với mô hình Random Walk, kết quả gửi các gói tin thành công trong mô hình có giá trị thấp hơn. Bên cạnh giao thức TORA bị ảnh hưởng bởi việc tăng số lượng nguồn phát, giao thức DSR cũng bị tác động mạnh khi số lượng nguồn phát tăng và cấu hình mạng thay đổi nhanh. DSDV vẫn cho kết quả thấp hơn so với các giao thức Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 52 khác. Và kết quả tốt nhất thuộc về giao thức AODV khi mà phần trăm gửi thành công của các gói tin là ổn định ngay cả khi tăng số lượng nguồn phát. Độ trễ đầu cuối trung bình trong việc gửi các gói tin của giao thức DSR khi số lượng nguồn phát tăng trong mô hình này cao hơn rất nhiều so với mô hình Random Walk. Rõ ràng, với mô hình di chuyển phi tập trung, độ dài đường đi của các gói tin dài hơn, cơ chế DSR thể hiện sự khó khăn. Giao thức AODV và DSDV vẫn cho các kết quả rất tốt. TORA thể hiện sự thay đổi mạnh khi mà số lượng nguồn phát tăng, độ trễ cũng tăng lên. Ngoài việc TORA có tải định tuyến cao do xảy ra tắc nghẽn, AODV có mức tải định tuyến cao hơn hai giao thức còn lại do cấu hình mạng phi tập trung và tải mạng cao. Nhờ có cơ chế lưu trữ nhiều đường đi và các phương pháp học hỏi đường một cách linh động, DSR có mức độ tải định tuyến thấp hơn AODV. DSDV có mức độ tải định tuyến thấp nhất trong mô hình này. 4.4.4. Nhận xét về hiệu suất của các giao thức định tuyến Tổng hợp các thí nghiệm trên, có thể rút ra các nhận xét sau: DSDV là giao thức dựa trên vector khoảng cách. Giao thức hoạt động tốt trong trường hợp cấu hình mạng có tốc độ thay đổi chậm, và giảm khi mà cấu hình mạng thay đổi tăng lên. Khi mạng có nhiều thay đổi, DSDV hội tụ chậm. Khi mà số lượng nguồn phát gói tin thấp, độ trễ trung bình cuối của DSDV là thấp và ổn định. Nhưng khi số lượng nguồn phát tăng lên, độ trễ phát gói tin của DSDV cao hơn so với AODV và DSR. Ngoài ra, tải định tuyến của DSDV là khá ổn định so với sự thay đổi của mạng. AODV là sự kết hợp của cơ chế định tuyến theo vector khoảng cách của DSDV với cơ chế định tuyến theo yêu cầu của DSR. Khả năng gửi thành công các gói tin của AODV là rất lớn, luôn cao hơn so với giao thức DSDV. So với DSR, trong trường hợp mức di chuyển của các nút mạng thấp, phần trăm gửi các gói tin là tương đương, nhưng khi mức độ di chuyển của nút mạng tăng lên, AODV có phần trăm gửi các gói tin cao hơn so với DSR. Độ trễ trung bình của các gói tin trong AODV là tương đương với DSDV. Trong trường hợp các nút mạng di chuyển nhanh trong mạng, tải định tuyến của AODV cao hơn so với DSR. DSR là giao thức dựa trên định tuyến nguồn. Mục tiêu trong thiết kế của DSR là loại bỏ các chi phí cho cập nhật định kì đường và phát hiện hàng xóm. Tuy nhiên, theo kết quả mô phỏng, DSR chỉ thực hiện tốt với mức di chuyển và tải trung bình. Khi mức di chuyển và tải tăng, hiệu suất của DSR sẽ giảm rõ rệt. Đó là do DSR áp dụng cơ Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 53 chế trả lời tất cả các yêu cầu đường. Cơ chế này giúp DSR thu thập được nhiều đường đi và phân phát các gói tin tốt hơn. Tuy nhiên, khi mà mức di chuyển trong mạng tăng, khả năng các đường đi trong cache bị hết hạn tăng lên do DSR chưa có đặc tả hết hạn đường đi trong cache. Khả năng “học” và “nghe trộm” đường của DSR cũng giúp phát tán các tuyến đường hết hạn trong cache. Cơ chế gửi route error của DSR cũng rất hạn chế. Nó chỉ truyền với các nút nằm trên đường đi qua của dữ liệu. TORA là giao thức dựa trên thuật toán đảo ngược liên kết (link reserval). Trong mô phỏng, việc cảm nhận liên lết của TORA được thực hiện bởi giao thức IMEP. Khi số lượng nguồn phát nhỏ, TORA cho các kết quả khá tốt. Tuy nhiên, khi số lượng nguồn phát tăng lên, mô hình mạng biến đổi một cách nhanh chóng, hiệu suất hoạt động của TORA là rất thấp. Mạng không thể thao tác được với các truyền thông được tạo ra bởi giao thức định tuyến, phần lớn các gói tin dữ liệu bị loại bỏ. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 54 Kết luận 1. Kết quả thu được - Hiểu thêm về mạng WLAN và cấu trúc của mạng theo mô hình 802.11 - Trang bị thêm kiến thức về mạng adhoc và một số giao thức định tuyến trong mạng adhoc - Đánh giá tổng quan về hiệu suất của các giao thức định tuyến trong mạng adhoc thông qua bộ mô phỏng NS2 2. Định hướng phát triển của luận văn Với sự phát triển nhanh chóng của mạng adhoc trong đời sống, nhu cầu nâng cao hiệu suất của mạng cần được quan tâm nhiều hơn. Các giao thức mạng cần phải được nghiên cứu và phát triển để nâng cao hiệu suất sử dụng mạng trong tương lai. Việc tìm ra giao thức định tuyến mới cho mạng adhoc cũng là hướng phát triển trong đề tài này. Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 55 Phụ Lục Biểu đồ kết quả so sánh các giao thức định tuyến trong mạng adhoc thông qua bộ mô phỏng mạng NS2 1. Mô hình Random Waypoint So sánh kết quả phân phát gói tin dữ liệu khi có 10 và 20 nguồn phát của các giao thức định tuyến trong mô hình Random Waypoint Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 56 So sánh thời gian trễ đầu cuối của các giao thức định tuyến trong hai trường hợp có 10 nguồn phát và 20 nguồn phát trong mô hình Random Waypoint Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 57 So sánh tải định tuyến chuẩn hóa trong trường hợp có 10 nguồn phát và 20 nguồn phát Bảng tải định tuyến của giao thức TORA 2. Mô hình Random Walk Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 58 Bảng so sánh kết quả phân phát gói tin dữ liệu trong mô hình Random Walk Bảng so sánh trễ đầu cuối trung bình của các giao thức định tuyến trong mô hình Random Walk Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 59 Bảng so sánh tải định tuyến chuẩn hóa trong mô hình Random Walk 3. Mô hình Random Direction So sánh kết quả phân phát gói tin dữ liệu trong mô hình Random Direction Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 60 So sánh thời gian trễ đầu cuối trung bình trong mô hình Random Direction So sánh tải định tuyến chuẩn hóa trong mô hình Random Direction (Nguồn: Luận văn cao học 2005-Nguyễn Thị Minh Nguyệt) Mạng Adhoc, Khóa luận tốt nghiệp Cử nhân CNTT, Ngô Hải Sơn, 2008 61 Tài liệu tham khảo Tiếng Việt: 1. Luận văn Cao Học(2005) - Nguyễn Thị Minh Nguyệt Tiếng Anh: 1. Andrew S. Tanenbaum (2003), Computer Networks, Prentice Hall, New Jersey, Fourth Edition. 2. ANSI/IEEE Std 802.11, 1999 Edition 3. 4. 5. 6. Jochen H. Schiller (2000), Mobile Communications, Addition-Wesley, London.