Khóa luận Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong manet

sử dụng giao thức định tuyến phản ứng. 3.2.3.3. Định tuyến nguồn và định tuyến theo chặng Với định tuyến nguồn, toàn bộ thông tin về đường đi tới đích được đặt trong trường tiêu đề của gói tin dữ liệu, các nút trung gian chỉ việc chuyển tiếp gói tin theo đường trong tiêu đề. Lợi điểm của giao thức này là loại bỏ được nhu cầu quảng bá đường định kỳ và các gói tin khám phá (discovery) hàng xóm. 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. 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. DSDV DSDV (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à: Full dump: Cập nhật đầy đủ. Thông điệp này bao gồm toàn bộ thông tin định tuyến mà nút đó biết đến thời điểm đó. Incremental dump: cập nhật bổ sung. Gói thông điệp này chỉ bao gồm các thông tin về những thay đổi từ lần cập nhật đầy đủ gần nhất. 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: Khi nút nhận thấy sự thay đổi trong quan hệ hàng xóm (vd: mất liên kết đến nút hàng xóm,…) Tuyến đường tới các nút đích khác hết hạn (quá lâu không được cập nhập) Phát hiện ra đường đi mới ngắn hơn để tới đích. Đ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). 3.3.5. TORA [11] TORA (Temporally Ordered Routing Algorithm) là một thuật toán định tuyến phân bố không có vòng lặp và độ thích nghi cao, dựa trên khái niệm đảo ngược đường thông. TORA được đề xuất cho môi trường nối mạng có tính linh động cao. Nó là một giao thức khởi phát từ nguồn và cung cấp đa tuyến cho mọi cặp nút nguồn/đích cần thiết. Nguyên lý chủ đạo trong TORA là định vị các bản tin điều khiển đối với mọi tập hợp các nút gần với nơi xảy ra sự thay đổi topo mạng. Để thực hiện được điều này, các nút cần duy trì thông tin định tuyến về các nút kế cận (chỉ một chặng). Giao thức này thực hiện 3 chức năng cơ bản: Tạo tuyến, Duy trì tuyến, và Xoá 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. Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG CỦA CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN 4.1. Xác định các tham số hiệu suất cần đánh giá và cách thức phân tích kết quả mô phỏng 4.1.1. Các tham số hiệu suất cần đánh giá Hiệu suất là khái niệm chỉ độ đo công việc mà hệ thống thực hiện được. Đối với lĩnh vực nghiên cứu mạng máy tính, hiệu suất bao gồm các độ đo thông dụng như: tính sẵn sàng, thông lượng, độ trễ và thời gian đáp ứng... Do còn nhiều giới hạn về tài nguyên nên các giao thức định tuyến trong mạng MANET cần phải đảm bảo việc sử dụng hiệu quả các tài nguyên hạn chế này. Chúng tôi sử dụng các độ đo sau để đánh giá hiệu suất hoạt động của các giao thức định tuyến khi các nút mạng thay đổi về hướng và tốc độ di chuyển: Tỷ lệ phân phát gói tin thành công: Là tỷ lệ giữa số gói tin được phân phát thành công tới đích so với số gói tin được gửi đi nguồn phát. Thời gian phản ứng của các giao thức định tuyến: Là thời gian tính từ thời điểm nút nguồn có nhu cầu truyền tới khi bắt đầu truyền dữ liệu. Thông lượng: Là tổng dung lượng dữ liệu truyền đến đích thành công trong 1 đơn vị thời gian (Kbps,…). 4.1.2. Cách thức phân tích kết quả mô phỏng của NS-2 4.1.2.1. Cấu trúc tệp vết Tệp vết là file dạng văn bản (text), mỗi dòng như một bản ghi (record), có cấu trúc như nhau, bao gồm một số trường phân cách nhau bởi ký tự trống (mã ASCII bằng 32). Cấu trúc một dòng của tệp vết thường có dạng: r 160.093884945 _6_ RTR --- 5 tcp 1492 [a2 4 6 800] ------- [36:0 16777984:0 31 16777984] [1 0] 2 0 Tên các trường của một dòng tệp vết trên là: Event, Time, Node ID, Trace Name, Reason, Event Identifier, Packet Type, Packet Size, [Time To Send Data, Destination MAC Address, Source MAC Address, Type (ARP, IP)]. Ý nghĩa của các trường được giải thích tại bảng 4. Bảng 3: Cấu trúc tệp vết Event Type Value Ý Nghĩa Wireless Event s: Sendr: Received: Dropf: Forward %.9f %d (%6.2f %6.2f) %3s %4s %d %s %d [%x %x %x %x] %.9f _%d_ %3s %4s %d %s %d [%x %x %x %x] double Time Thời gian int Node ID Chỉ số của nút double X Coordinate Tọa độ trục x – Chỉ lưu lại nếu được log lại vị trí double Y Coordinate Tọa độ trục y – Chỉ lưu lại nếu được log lại vị trí string Trace Name Tên vết như: RTR, AGT,.. string Reason Lý do tạo ra sự kiện int Event Identifier Số thứ tự gói tin string Packet Type Kiểu gói tin: TCP, UDP, ACK int Packet Size Kích thước gói tin hexadecimal Time To Send Data Thời gian trông đợi gói tin được gửi xuống kênh truyền hexadecimal Destination MAC Address Địa chỉ MAC của nút đích hexadecimal Source MAC Address Địa chỉ MAC của nút nguồn hexadecimal Type (ARP, IP) Kiểu của trường MAC VD: 800à ETHERTYPE_IP Phụ thuộc vào kiểu của gói tin mà cấu trúc tệp vết còn có thêm một số trường sau: ------- [Source IP Address: Source Port Number, Destination IP Address: Destination Port Number, TTL Value, Next Hop Address, If Any], [Sequence Number, Acknowledgment Number], Number Of Times Packet Was Forwarded, Optimal Number Of Forwards. Ý nghĩa của các trường này được giải thích tại bảng 5 bên dưới. Bảng 4: Các trường thêm vào trong cấu trúc tệp vết phụ thuộc vào kiểu gói tin Event Type Value Ý Nghĩa IP Trace ------- [%d:%d %d:%d %d %d] int Source IP Address Địa chỉ IP nguồn int Source Port Number Chỉ số cổng nguồn int Destination IP Address Địa chỉ IP đích int Destination Port Number Chỉ số cổng đích int TTL Value Time To Live: Thời gian tồn tại của gói tin int Next Hop Address, If Any Địa chỉ của nút kế tiếp gói tin sẽ chuyể tiếp tới. TCP Trace [%d %d] %d %d int Sequence Number Số thứ tự int Acknowledgment Number Số thứ tự của gói biên nhận int Number Of Times Packet Was Forwarded Số lần gói tin được chuyển tiếp int Optimal Number Of Forwards Số chuyển tiếp tối ưu CBR Trace [%d] %d %d int Sequence Number Số thứ tự int Number Of Times Packet Was Forwarded Số lần gói tin được chuyển tiếp int Optimal Number Of Forwards Số chuyển tiếp tối ưu Chi tiết các trường phụ thêm vào của các kiểu gói tin khác được nêu trong phần PHỤ LỤC. 4.1.2. Công cụ để phân tích và biểu diễn kết quả mô phỏng . Perl Ban đầu, Perl (Practical Extraction and Report Language) là một ngôn ngữ lập trình được phát triển cho thao tác văn bản, sau này được phát triển để sử dụng cho một loạt các ứng dụng khác như: quản trị hệ thống, phát triển web, lập trình mạng, giao diện phát triển,…Ưu điểm vượt trội của Perl là nhỏ gọn, dễ sử dụng, hỗ trợ cả lập trình hướng đối tượng (OOP), được xây dựng hỗ trợ xử lý văn bản. Sử dụng Perl  Để chạy Perl trên Linux, ta dùng lệnh sau:  perl progName.pl Viết Script bằng perl, đặt dòng sau lên trên đầu trong Script #!/usr/bin/perl Sau đó chạy lệnh: /duongdan/script.pl  ví dụ :  chmod 755 script.pl /duongdan/script.pl  Cú pháp cơ bản của Perl: Một đoạn code Perl script hay một chương trình đều bao gồm nhiều các statements. Các statements này chỉ đơn giản được viết bằng các kiểu cách đơn giản trong script. Không nhất thiết phải có main() hoặc tương tự.  perl statements kết bằng dấu “ ; “ Ví dụ: print”Hello, I’m Tu”; Sử dụng “#” để Comments trong Perl, ví dụ :  # Comment ở đây GNUPLOT Gnuplot là một công cụ vẽ đồ thị gọn nhẹ và rất hữu dụng trên Linux. Gnuplot tỏ ra khó dùng lúc ban đầu, tuy nhiên, nếu nắm được các cú pháp cơ bản của nó, chúng ta sẽ thấy đây là một công cụ mạnh mẽ và đầy hiệu quả. Với chức năng tạo script để vẽ, việc tạo hoặc sửa đổi một đồ thị trở nên rất dễ dàng. Gnuplot có thể nhận vào tệp văn bản (input file) có nhiều cột, lúc ấy cần chỉ ra hai cột cụ thể để lấy dữ liệu vẽ đồ thị. Gnuplot còn có thể nhận vào từ nhiều file và vẽ trên cùng một đồ thị, điều này rất thuận lợi cho việc so sánh và nghiên cứu. Ví dụ: File đầu vào là: Time_of_connection_setup.data STT DSDV AODV DSR 0 0,0045 0,6204 0,0333 5 1,1788 1,6365 1,4792 10 5,4950 1,4021 3,8303 15 5,0125 2,3528 3,4793 20 6,9357 1,4003 0,5594 Thiết lập định dạng cho bản vẽ và thực hiện vẽ đồ thị: #plot.script set title "Thoi gian thiet lap ket noi" set xlabel "Van Toc (m/s)" set ylabel "Thoi gian (s)" set key right top set pointsize 1 set xr [0:20] set yr [0:8] set size 0.8,0.8 set terminal postscript eps enhanced mono dashed lw 1 set output " Time_of_connection_setup.eps" plot "connection_time_RandomWaypoint" using 1:2 title 'DSDV' with linespoints lt 1 pt 6 lw 1, \ "connection_time_RandomWaypoint" using 1:3 title 'AODV' with linespoints lt 2 pt 12 lw 1, \ "connection_time_RandomWaypoint" using 1:4 title 'DSR' with linespoints lt -1 pt 3 lw 1 4.2. Thiết lập mạng mô phỏng MANET Tôi đã xây dựng chương trình mô phỏng, có sử dụng đoạn mã ví dụ về mô phỏng mạng ad-hoc với giao thức DSDV trong cuốn "NS Simulator for beginners" [1] của tác giả Eitan Altman và Tania Jimenez. Chương trình mô phỏng của tôi có tên là: MANET_Simulation.tcl, được in trong mục 2.Mô phỏng mạng MANET của phần Phụ Lục. Chương trình này sau khi chạy sẽ sinh ra các tệp vết là :MANET.nam và MANET.tr. Chúng sẽ được dùng làm input cho chương trình NAM để trực quan hóa toàn bộ quá trình mô phỏng bằng đồ họa; làm input cho đoạn mã perl do tôi xây dựng để tính: Tỷ lệ phân phát gói tin thành công, thời gian phản ứng của các giao thức định tuyến, thông lượng; và kết xuất ra các tệp dùng cho gnuplot vẽ đồ thị. 4.2.1. Thiết lập tô-pô mạng Sau nhiều khảo sát đánh giá, chúng tôi lựa chọn khu vực mô phỏng mạng MANET theo hình vuông với diện tích là 1500m x 1500m (1,5Km x 1,5Km). Việc mở rộng diện tích khu vực mô phỏng này sẽ đảm bảo cho các nút mạng di động có đủ không gian chuyển động với quãng đường đi lớn nhất lên tới 1,5x√2 = 2,12Km . Theo chuẩn 802.11 thì vùng thu phát sóng của nút di động tối đa là 250m nên ta có độ dài đường đi lớn nhất trong mạng mô phỏng lớn hơn 8 chặng dài nhất có thể có. Điều này rất hữu ích trong trường hợp nghiên cứu quá trình định tuyến giữa các nút ở xa nhau. Mạng mô phỏng bao gồm 50 nút di động phân bố ngẫu nhiên trong diện tích mô phỏng với tọa độ các nút là (x, y, z) trong đó z = 0 (Mặt phẳng). Hình 13: Diện tích mạng mô phỏng và các nút mạng Vị trí ban đầu của các nút được khởi tạo ngẫu nhiên như vậy nhằm làm tăng tính khách quan trong quá trình mô phỏng. Tổng quan về mạng mô phỏng với các tham số cấu hình chung, cấu hình di chuyển và cấu hình truyền dữ liệu được thể hiện trong bảng 5. Bảng 5: Cấu hình mạng mô phỏng Thông số Giá trị Cấu hình chung Khu vực địa lý 1,5Km x 1,5Km Tổng số nút 50 nút Vùng thu phát sóng 250m Cấu hình di chuyển Tốc độ di chuyển nhanh nhất 20 m/s ó 72 km/h Tốc độ di chuyển chậm nhất 0 m/s ó Đứng yên Cấu hình truyền dữ liệu Dạng truyền thông TCP Số nguồn phát 10 nguồn, nằm trên 8 nút mạng: 4, 5, 7, 12, 15, 16, 18, 19 Thực thể nhận 8 nút mạng: 5, 6, 8, 13, 16, 17, 19, 20 Kích thước gói tin 512 bytes Kiểu – Kích thước hàng đợi DropTail - 50 4.2.2. Thiết lập mô hình chuyển động của các nút mạng và thời gian mô phỏng Trong mô phỏng mạng Ad-hoc các mô hình di chuyển đóng một vai trò rất quan trọng. Nó thể hiện chính xác các ngữ cảnh có thể của mạng và góp phần quyết định tính đúng đắn của việc đánh giá hiệu suất của các giao thức định tuyến trước khi mang ra triển khai thực tế. Trên thực tế có hai loại mô hình di chuyển được sử dụng cho mạng không dây là mô hình vết (trace-based model) và mô hình tổng hợp (synthetic model). Mô hình vết cung cấp cho ta thông tin chính xác, đặc biệt là khi nó có liên quan tới nhiều bên tham gia va có thời gian đủ dài. Tuy nhiên, mô hình tổng hợp là phù hợp hơn đối với mạng di động ngày nay. Mô hình tổng hợp cố gắng thể hiện hành vi của các nút di động bằng cách thống kê. Mỗi nút sẽ được gán một giải thuật nhằm ngẫu nhiên hóa quá trình di chuyển. Hai mô hình tiêu biểu mô phỏng các mạng Ad-hoc là: Random Waypoint và Random Walk. 4.2.2.1. Mô hình Random Waypoint Tại mô hình này, ban đầu mỗi nút có một vị trí ngẫu nhiên trong khu vực mô phỏng và ở tại đó một khoảng thời gian tạm dừng. Khi hết quãng thời gian tạm dừng, nút chọn cho mình một đích ngẫu nhiên trong khu vực mô phỏng và chuyển động với tốc độ phân bố đồng đều giữa [speedmin, speedmax]. Khi tới vị trí mới nút dừng một khoảng thời gian trong khoảng [Pmin, Pmax] và sau đó tiếp tục lại quá trình. Hình 14: Di chuyển một nút theo mô hình Random Waypoint. Đây là mô hình có tính linh động cao nên được sử dụng phổ biến và rộng rãi nhất. Mô hình Random Waypoint có biến thể khác với một vài thay đổi khác biệt là mô hình Random Walk. 4.2.2.2. Mô hình Random Walk Mô hình này mô phỏng chuyển động ngẫu nhiên của các thực thể trong cuộc sống tự nhiên. Nút di động di chuyển từ vị trí hiện tại tới vị trí mới bằng việc chọn ngẫu nhiên một hướng nằm trong khoảng [0, 180°] và tốc độ nằm trong khoảng [speedmin, speedmax]. Mỗi chuyển động diễn ra trong khoảng thời gian travel_time (thời gian di chuyển của nút trước khi thay đổi hướng và tốc độ) hoặc trong một khoảng cách hằng số và đặc biệt là không có thời gian tạm dừng trước khi nút mạng thay đổi hướng và tốc độ. Hình 15 thể hiện trực quan hóa quá trình di chuyển của tám nút mạng theo mô hinh Random Walk. Hình 15: Di chuyển của 8 nút theo mô hình Random Walk Với mô hình chuyển động này thì tham số về sự thay đổi hướng di chuyển của nút có tính chất quyết định đến mức độ thay đổi của mạng. Nếu tham số này nhỏ, các nút di chuyển ngẫu nhiên trong phạm vi nhỏ, lúc này mạng được coi là mạng nửa tĩnh. Ngược lại nếu tham số này lớn, mạng thay đổi trên phạm vi rộng hơn. 4.2.3 Thiết lập các nguồn sinh lưu lượng đưa vào mạng Chúng tôi lựa chọn 10 cặp truyền thông (sender, receiver) truyền phát dữ liệu. Chúng được sắp xếp phân bố hợp lý trên khu vực mô phỏng sao cho đảm bảo có đủ các chặng truyền phát với độ dài khác nhau, từ các cặp truyền thông nằm gần nhau nhất tới các cặp truyền thông nằm xa nhau nhất có thể trong khu vực mô phỏng , các nút mạng còn lại tham gia vào quá trình định tuyến với vai trò là nút trung gian chuyển tiếp gói tin. Giao thức TCP được chúng tôi lựa chọn để đưa vào mô phỏng bởi trong các ứng dụng trên thực tế hầu hết đều hoạt động dựa trên giao thức này. Các nguồn phát sinh lưu lượng sử dụng giao thức FTP để truyền. NS-2 hỗ trợ một số công cụ để tạo ra các file ngữ cảnh một cách tự động và ngẫu nhiên. Các công cụ này nằm trong thư mục: …/ns-2/indep-utils/cmu-scen-gen/, với các tính năng sau: • setdest: Là công cụ viết trên nền C++, giúp cho người nghiên cứu tạo ra các kịch bản bao gồm vị trí ban đầu của nút di động và sự di chuyển của chúng. Trong công cụ này, chúng ta coi tọa độ z của các nút đều bằng 0 và các nút di chuyển trên cùng một mặt phẳng. Thực hiện setdest bằng cách gõ lệnh như sau: ./setdest -n -p -s -t -x -y > / • cbrgen.tcl: Là công cụ viết bằng ngôn ngữ tcl, sử dụng thông qua bộ thông dịch ns-2, giúp người nghiên cứu có thể tạo ra các kịch bản truyền thông trên nền giao thức giao vận TCP. Câu lệnh: ns cbrgen.tcl [-type cbr|tcp] [-nn nodes] [-seed seed] [-mc connections] [-rate rate] > / Sử dụng các công cụ này giúp người nghiên cứu tạo ra các kịch bản truyền thông cũng như di chuyển của mạng với số lượng các nút di động là tương đối lớn. Tuy nhiên việc tạo ra các kịch bản này là ngẫu nhiên, có thể không theo ý muốn của người nghiên cứu, nên trong nhiều trường hợp người nghiên cứu phải tự viết ra các kịch bản truyền thông có ý nghĩa mô phỏng điển hình. 4.2.4. Lựa chọn thời gian mô phỏng Quá trình mô phỏng diễn ra trong thời gian t = 600s = 10 phút. Đây là khoảng thời gian vừa đủ để chúng ta nghiên cứu các sự kiện xảy ra trong mạng. Thật vậy do các nút mạng di chuyển với vận tốc từ [0m/s – 20m/s] nên ta giả sử nút di chuyển với tốc độ gần như là thấp nhất ứng với người đi bộ là 1m/s thì quãng đường đi được sau 600s cũng lên tới 600m. S = v.t = 1 x 600 = 600m Với thời gian như vậy đủ để nút chậm nhất di chuyển ra ngoài vùng thu phát sóng của nút khác (radio range = 250m) và làm cho tô-pô mạng thay đổi. Quá trình đó cũng thể hiện rõ các tính chất đặc trưng của các mô hình chuyển động khác nhau: Random Waypoint: Mô hình này tuy các nút có thêm các khoảng thời gian tạm dừng trước khi thay đổi hướng và tốc độ chuyển động nhưng thời gian tạm dừng này là rất nhỏ so với thời tổng toàn bộ thời gian mô phỏng. Do đó với 600s các nút mạng vẫn đủ thời gian để đạt đưỡng quãng đường di chuyển cần thiết tạo ra các thay đổi khác nhau đối với tô-pô mạng. Random Walk: Mô hình này các nút di chuyển liên tục, không có thời gian tạm dừng nên đương nhiên với thời gian mô phỏng 600s là đủ để đánh giá các giao thức định tuyến khi tô-pô mạng thay đổi liên tục. 4.3. Thực hiện mô phỏng các giao thức định tuyến 4.3.1. Phân tích kết quả bằng công cụ perl Tôi đã xây dựng các chương trình perl để đánh giá các tham số hiệu năng sẽ được trình bày tại mục 4.3.1 này. Tên các chương trình đó là: Pkt_success_rate. pl: Dùng để tính ra tỷ lệ phân phát gói tin thành công, chính là tỷ lệ giữa số các gói tin được phân phát thành công tới đích so với số các gói tin tạo ra bởi nguồn phát. Time_of_connection_setup.pl: Dùng để tính thời gian phản ứng của các giao thức định tuyến từ thời điểm nút nguồn có nhu cầu truyền đến khi bắt đầu truyền dữ liệu. . Tỷ lệ phân phát gói tin thành công Mô phỏng mạng gồm 50 nút di động với 10 nguồn sinh lưu lượng kết nối. Mô hình Random Waypoint Bảng 6: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Waypoint DSDV AODV DSR 0m/s Gói tin truyền thành công 2768 50802 49802 Tổng số gói tin gửi đi 2813 50925 49943 Tỷ lệ % 98,40 99,75 99,72 5m/s Gói tin truyền thành công 63930 62871 57789 Tổng số gói tin gửi đi 64601 64063 58170 Tỷ lệ % 98,96 98,13 99,34 10m/s Gói tin truyền thành công 97453 60909 105725 Tổng số gói tin gửi đi 97979 61554 106059 Tỷ lệ % 99,46 98,95 99,69 15m/s Gói tin truyền thành công 24978 46136 41019 Tổng số gói tin gửi đi 25222 46937 41356 Tỷ lệ % 99,03 98,29 99,19 20m/s Gói tin truyền thành công 37344 46212 45568 Tổng số gói tin gửi đi 37839 47180 45897 Tỷ lệ % 98,69 97,95 99,28 Mô hình Random Walk Bảng 7: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Walk DSDV AODV DSR 0m/s Gói tin truyền thành công 69919 72729 69972 Tổng số gói tin gửi đi 70033 72859 70101 Tỷ lệ % 99,84 99,82 99,82 5m/s Gói tin truyền thành công 51120 48731 44450 Tổng số gói tin gửi đi 51547 50096 44685 Tỷ lệ % 99,17 97,28 99,47 10m/s Gói tin truyền thành công 55272 61102 56998 Tổng số gói tin gửi đi 55652 62065 57391 Tỷ lệ % 99,32 98,45 99,32 15m/s Gói tin truyền thành công 34680 44709 42969 Tổng số gói tin gửi đi 35149 45723 43396 Tỷ lệ % 98,67 97,78 99,02 20m/s Gói tin truyền thành công 31045 49969 50373 Tổng số gói tin gửi đi 31498 51238 50845 Tỷ lệ % 98,56 97,52 99,07 4.3.1.2. Thời gian thiết lập kết nối Mô hình Random Waypoint Bảng 8: Thời gian thiết lập kết nối trung bình-Random_Waypoint Tốc độ Giao thức 0m/s 5m/s 10m/s 15m/s 20m/s DSDV (s) 0,0045 1,1788 5,4950 5,0125 6,9357 AODV (s) 0,6204 1,6365 1,4021 2,3528 1,4003 DSR (s) 0,0333 1,4792 3,8303 3,4793 0,5594 Mô hình Random Walk Bảng 9: Thời gian thiết lập kết nối trung bình-Random_Walk Tốc độ Giao thức 0m/s 5m/s 10m/s 15m/s 20m/s DSDV (s) 0,0039 0,7459 0,2433 0,0721 0,0514 AODV (s) 0,0077 3,2728 1,8551 6,0929 0,9361 DSR (s) 0,0179 5,1817 3,0653 2,5129 1,7436 4.3.2. Sử dụng gnuplot để vẽ đồ thị Tôi đã sử dụng gnuplot với input là các file sau: Time_of_connection_setup_randomWaypoint Time_of_connecion_setup_randomWalk Thực hiện các theo tác trong chế độ tương tác của gnuplot để vẽ các đồ thị trong mục 4.3.2.2: Thời gia thiết lập kết nối. 4.3.2.1. Tỷ lệ phân phát gói tin thành công Mô hình Random Waypoint Bảng 10: Tỷ lệ phân phát gói tin thành công - Random Waypoint Tốc độ Giao thức 0m/s 5m/s 10m/s 15m/s 20m/s DSDV (%) 98,40 98,96 99,46 99,03 98,69 AODV (%) 99,75 98,13 98,95 98,29 97,95 DSR (%) 99,72 99,34 99,69 99,19 99,28 Kết quả phân phát gói tin dữ liệu Phần trăm gói tin truyền thành công (%) Vận Tốc Hình 16: Đồ thị tỷ lệ phân phát gói thành công – Random Waypoint Mô hình Random Walk Bảng 11: Tỷ lệ phân phát gói tin thành công – Random Walk Tốc độ Giao thức 0m/s 5m/s 10m/s 15m/s 20m/s DSDV (%) 99,84 99,17 99,32 98,67 98,56 AODV (%) 99,82 97,28 98,45 97,78 97,52 DSR (%) 99,82 99,47 99,32 99,02 99,07 Kết quả phân phát gói tin dữ liệu Vận Tốc Phần trăm gói tin truyền thành công (%) Hình 18: Đồ thị tỷ lệ phân phát gói tin thành công – Random Walk 4.3.2.2. Thời gian thiết lập kết nối Random Waypoint Hình 19: Đồ thị thời gian thiết lập kết nối trung bình_Random-Waypoint Mô hình Random Walk Hình 20: Đồ thị thời gian thiết lập kết nối trung bình_Random-Walk 4.4. Đánh giá ảnh hưởng của sự chuyển động của nút mạng đến hiệu suất của các giao thức định tuyến Thông qua tập các cấu hình mạng mô phỏng được xây dựng ở trên, chúng tôi tiến hành mô phỏng, phân tích, khảo sát ảnh hưởng của sự chuyển động các nút đến hiệu suất của ba giao thức định tuyến điển hình trong mạng MANET là: DSDV, AODV và DSR. Các kết quả so sánh được bao gồm: kết quả về tỷ lệ phân phát gói tin thành công và thời gian phản ứng của các giao thức định tuyến (Thời gian thiết lập kết nối). Hình 16 thể hiện tỷ lệ phân phát gói tin thành công trong mô hình Random Waypoint với 10 nguồn phát. Các giao thức cho kết quả làm việc khá tốt với tỷ lệ đạt trên 97%, tỷ lệ mất gói tin là rất ít chỉ chiếm khoảng từ 1-3%. Đi vào xem xét sâu hơn nữa chúng ta thấy ngay hoạt động tốt nhất là giao thức DSR gần như các gói tin truyền đi đều tới đích, tỷ lệ rớt gói luôn dưới 1%. Giao thức AODV thể hiện ưu điểm của mình khi tô-pô mạng cố định không có thay đổi nào, nó cho phép truyền dữ liệu khá tin cậy với tỷ lệ gói tin truyền thành công là 99,75% nhưng khi các nút mạng thay đổi tốc độ di chuyển thì hiệu quả của nó lại bị giảm đi nhiều hơn so với các giao thức còn lại. Nhìn chung cả ba giao thức hoạt động khá tốt, tỷ lệ rớt gói là rất nhỏ và chỉ bị giảm đôi chút khi các nút thay đổi tốc độ chuyển động làm cho tô-pô mạng thay đổi. Với mô hinh Radom Walk, tỷ lệ phân phát gói tin thành công được thể hiện trong hình 18. Các giao thức cũng có tỷ lệ phân phát gói tin thành công là rất cao như trong mô hình Radom Waypoint. Hoạt động hiệu quả nhất vẫn là DSR với việc thích nghi tốt với sự thay đổi của mạng khi các nút di chuyển liên tục theo các vẫn tốc khác nhau. Hình 19 thể hiện thời gian thiết lập kết nối trong mạng hoạt động theo mô hình Random Waypoint. Đây là khoảng thời gian được tính từ khi nút nguồn có yêu cầu truyền dữ liễu đến khi bắt đầu truyền. Thời điểm này chính là lúc nút thực hiện quá trình bắt tay ba bước thiết lập kết nối. Tùy vào từng loại giao thức và trạng thái của tô-pô mạng hiện tại mà quá trình thiết lập kết nói này có thể diễn ra thành công hoặc thất bại, lúc đó các nút nguồn sẽ phải truyền lại gói tin. Từ hình vẽ chúng ta có thể thấy ban đầu khi mạng ít thay đổi, các nút chuyển động rất chậm với tốc độ dưới 5m/s thì khoảng thời gian cần thiết để thiết lập kết nối của cả ba giao thức là như nhau. Nhưng khi các nút mạng chuyển động nhanh hơn với vận tốc từ 5m/s tới 10m/s thì lúc này có sự phân hóa rõ rệt giữa các giao thức định tuyến. Giao thức chủ ứng DSDV cần tới nhiều thời gian nhất để thiết lập kết nối, thời gian hội tụ rất chậm, có thời điểm phải mất tới 5,49s mới thiết lập xong được kết nối truyền thông. Bên cạnh đó thì giao thức DSR cần tới hơn 3s cho việc kết nối và giao thức có thời gian kết nối nhanh nhất là AODV với thời gian tối đa cho việc thiết lập kết nối là 1,4s. Một điều khá đặc biệt mà đồ thị 19 cho chúng ta thấy đó là khi các nút mạng tăng vận tốc di chuyển lên trong khoảng từ 10m/s đến 15m/s thì thời gian thiết lập kết nối của hai giao thức DSDV và DSR là giữ nguyên không không có sự tăng đột biến trừ giao thức AODV có mất thời gian kết nối lâu hơn một chút. Hình 20 thể hiện đồ thị về thời gian thiết lập kết nối với mô hình Random Walk. Với mô hình di chuyển này các nút mạng chuyển động liên tục không có quãng thời gian nghỉ với việc chọn ngẫu nhiên hướng đi và tốc độ chuyển động. Trái với mô hình chuyển động Radom Waypoint, trong mô hình này giao thức DSDV lại thể hiện được ưu điểm vượt trội của mình, cho phép kết nối nhanh chóng với thời gian luôn dưới 1s cho dù tô-pô mạng có thay đổi nhanh hơn đi chăng nữa, giao thức vẫn cho khả năng kết nối nhanh chóng. Khi các nút mạng chuyển động nhanh hơn dẫn tới tô-pô mạng cũng thay đổi một cách liên tục thì hai giao thức còn lại: DSR và AODV phải cần tới một khoảng thời gian từ 3 đến 5s cho việc thiết lập kết nối. Các nút mạng chuyển động càng nhanh thì càng cần nhiều thời gian để thiết lập kết nối hơn do tô-pô mạng thay đổi liên tục, các nút phải mất thêm một khoảng thời gian cần thiết để học hỏi về mạng mới. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Các kết quả của khóa luận Khóa luận đã trình bày các kết quả khảo sát đánh giá về ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong MANET. Khóa luận đã nghiên cứu một cách chi tiết về môi trường mạng, các giao thức định tuyến, các mô hình chuyển động đặc trưng và quan trọng hơn nữa chúng tôi đã thực nghiệm được một số thí nghiệm bằng mộ phỏng nhằm tìm ra cơ sở khách quan, thực tế, kết hợp với cơ sở lý thuyết để tìm ra các đặc điểm khác nhau của từng giao thức chịu ảnh hưởng thế nào khi các nút mạng di chuyển với tốc độ và hướng đi khác nhau. Cụ thể chúng tôi đã xem xét chi tiết hoạt động của ba giao thức định tuyến điển hình là: DSDV, AODV và DSR. Các giao thức này có các giải thuật định tuyến khác nhau: DSDV là giao thức chủ ứng dựa trên thuật toán vector khoảng cách; AODV là giao thức phản ứng dựa trên bảng vector khoảng cách; DSR là giao thức phản ứng dựa trên giải thuật chuyển tiếp đa điểm (Multi-Point Relay MPR). Kết quả mô phỏng cho thấy các kết luận như sau: - DSDV cho kết quả làm việc tốt khi mạng có tốc độ thay đổi cấu hình thấp. Tuy nhiên giao thức DSDV hội tụ chậm và hiệu suất giảm khi mạng có nhiều thay đổi. - AODV cho kết quả hoạt động tốt trong trường hợp mạng có các thay đổi cấu hình và tải mạng khác nhau. - DSR có khả năng phân phát gói tin tốt song thời gian thiết lập kết nối vẫn còn chậm nhất là khi các nút di chuyển nhanh, tô-pô mạng thay đổi liên tục. Hướng phát triển của đề tài Do hạn chế về mặt thời gian nên khóa luận chỉ tập trung nghiên cứu kỹ ba giao thức định tuyến điển hình: DSDV, AODV và DSR. Trong thời gian tới chúng tôi sẽ tiếp tục nghiên cứu sâu hơn về cả hai giao thức còn lại là OLSR và TORA. Thêm vào đó vẫn còn một số vấn đề khác của các giao thức cần được xem xét như: Vấn đề năng lượng Chất lượng dịch vụ Vấn đề bảo mật,… TÀI LIỆU THAM KHẢO Tiếng Việt [1] Nguyễn Hoàng Cẩm, Trịnh Quang. Các giải pháp định tuyến tối ưu trong mạng di động không dây tuỳ biến. Tạp chí Bưu Chính Viễn Thông. Tháng 3 năm 2006 [2] Hoàng Trọng Minh. Định tuyến trong mạng kết nối hình lưới WLAN. Tạp chí Bưu Chính Viễn Thông. Tháng 10 năm 2008. [3] Nguyễn Thị Minh Nguyệt. Đánh giá hiệu suất bằng mô phỏng các thuật toán định tuyến trong mạng đặc biệt di động MANET. Luận văn cao học. Hà Nội, 2005. [4] Hà Minh Toản. Nguyên cứu một số giao thức truy cập môi trường truyền trong mạng LAN 802.11. Khóa luận tốt nghiệp. Hà Nội, 2005. [5] Nguyễn Đình Việt. Đánh giá hiệu năng mạng máy tính. Hà Nội, 2008. Tiếng Anh [1] Eitan Altman, Tania Jimenez. NS Simulator for beginners. Univ. de Los Andes, Mérida, Venezuela and ESSI, Sophia-Antipolis, France. December 4, 2003. [2] Humayun Bakht. The future of mobile ad-hoc networks. Computing Unplugged Magazine. October 2010. [3] Jae Chung and Mark Claypool. NS by Example. WPI worcester polytechnic institute Computer Science. [4] Kevin Fall, Kannan Varadhan. The NS manual. VINT Project. April 14, 2002. [5] Marc Greis.Tutorial for the network simulator “NS”. VINT Group [6] Bernd Gloss, Michael Scharf, Daniel Neubauer. A more realistic random direction mobility model. University of Stuttgart. October 2005. [7] David B. Johnson, David A. Maltz, Yih-Chun Hu. (2003), “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)”, Published by IETF as RFC, work in progress, April 2003. [8] T. Clausen, Ed., P. Jacquet, Ed. (2003), “Optimized Link State Routing Protocol (OLSR)”, RFC 3626, IETF Network Working Group [9] Todd Lammle. CCNA study guide 4th edition. SYBEX 2004. [10] The SECAN-Lab of the University of Luxembourg. [11] V. Park and M. Corson (2001), “Temporally-Ordered Routing Algorithm (TORA)”, IETF Internet Draft, work in progress, 20 July 2001 [12] C. Perkins, E. Belding-Royer, S. Das. (2003), Ad hoc On-Demand Distance Vector (AODV) Routing, IETF Mobile Ad Hoc Network Working Group, Internet Draft, work in progress, 19 October 2003. [13] Charles E. Perkins, Pravin Bhagwat. (1994), “Highly dynamic Destination-Sequenced Distance Vector routing (DSDV) for mobile computers”, ACM SIGCOMM Computer Comm. Rev., 4(24), pp. 234-244, 1994. [14] Jochen H. Schiller. Mobile Communications, Addison-Wesley, 2nd edition, 2003 [15] Karthik Sadasivam. Tutorial for Simulation-based Performance Analysis of MANET Routing Protocols in ns-2. Page 4 – 9 [16] History of wireless. [17] Thomas Williams & Colin Keylley. Gnuplot 4.4 - An Interactive Plotting Program. March 2010. [18] Wikipedia. PHỤ LỤC Bảng các trường phụ thêm vào trong cấu trúc tệp vết phụ thuộc vào kiểu gói tin Event Type Value Ý Nghĩa ARP Trace ------- [%s %d/%d %d/%d] string Request or Reply Gói tin yêu cầu hoặc Trả lời int Source MAC Address Địa chỉ MAC nguồn int Source Address Địa chỉ nguồn int Destination MAC Address Địa chỉ MAC đích int Destination Address Địa chỉ đích DSR Trace %d [%d %d] [%d %d %d %d->%d] [%d %d %d %d->%d] int Number Of Nodes Traversed Số nút đã đi qua. int Routing Request Flag Cờ yêu cầu định tuyến int Route Request Sequence Number Số thứ tự yêu cầu tuyến đường int Routing Reply Flag Cờ trả lời định tuyến int Route Request Sequence Number Số thứ tự yêu cầu tuyến đường int Reply Length Chiều dài gói tin trả lời int Source Of Source Routing Định tuyến nguồn của nút nguồn int Destination Of Source Routing Định tuyến nguồn của nút đích int Error Report Flag (?) Cờ báo lỗi int Number Of Errors Số lượng lỗi int Report To Whom Báo cáo tới nút nào int Link Error From Liên kết lỗi từ đâu tới int Link Error To Liên kết lỗi đi tới đâu AODV Trace [0x%x %d %d [%d %d] [%d %d]] (REQUEST) hexadecimal Type Kiểu int Hop Count Số Hop tính được int Broadcast ID ID quảng bá int Destination Đích int Destination Sequence Number Số thứ tự nút đích int Source Nguồn int Source Sequence Number Số thứ tự nút nguồn [0x%x %d [%d %d] %f] (%s) hexadecimal Type Kiểu int Hop Count Số Hop tính được int Destination Đích int Destination Sequence Number Số thứ tự nút đích double Lifetime Thời gian sống string Operation (REPLY, ERROR, HELLO) Hoạt động: Trả lời, Lỗi hay gói tin Hello TORA Trace [0x%x %d] (QUERY) hexadecimal Type Kiểu int Destination Đích 0x%x %d (%f %d %d %d %d) (UPDATE) hexadecimal Type Kiểu int Destination Đích double Tau int Oid int R int Delta int ID Chỉ số [0x%x %d %f %d] (CLEAR) hexadecimal Type Kiểu int Destination Đích double Tau int Oid IMEP Trace [%c %c %c 0x%04x] char Acknowledgment Flag Cờ biên nhận char Hello Flag Cờ Hello char Object Flag Cờ đối tượng hexadecimal Length Chiều dài RCA Trace (from MIT Leach code) ------- [%c %d %d %d] char Operation (A, R, D) int RCA Source int RCA Link Destination int RCA MAC Destination Mô phỏng mạng MANET # MANET_Simulation. # # Define options_ set val(chan) Channel/WirelessChannel set val(prop) Propagation/TwoRayGround set val(netif) Phy/WirelessPhy set val(mac) Mac/802_11 set val(ifq) Queue/DropTail/PriQueue set val(ll) LL set val(ant) Antenna/OmniAntenna set val(ifqlen) 50 set val(seed) 0.0 set val(nn) 50 set val(rp) DSDV set val(x) 1500 set val(y) 1500 set val(cp) "…/tcp-50-2-10" set val(sc) "…/scenario-50-30-10-600-1500-1500" set val(stop) 600 ;# time of simulation end set ns_ [new Simulator] set namtrace [open MANET.nam w] set tracefd [open MANET.tr w] $ns_ trace-all $tracefd $ns_ namtrace-all-wireless $namtrace $val(x) $val(y) #Set up topography object set topo [new Topography] $topo load_flatgrid $val(x) $val(y) # # Create God # set god_ [create-god $val(nn)] #------------------------------------------------------- #Create nn mobilenodes and attach them to channel #Configure the nodes $ns_ node-config -adhocRouting $val(rp) \ -llType $val(ll) \ -macType $val(mac) \ -ifqType $val(ifq) \ -ifqLen $val(ifqlen) \ -antType $val(ant) \ -propType $val(prop) \ -phyType $val(netif) \ -channelType $val(chan) \ -topoInstance $topo \ -agentTrace ON \ -routerTrace ON \ -macTrace OFF \ -movementTrace ON for {set i 0} {$i < $val(nn) } { incr i } { set node_($i) [$ns_ node] $node_($i) random-motion 0 } # # Define node movement model # puts "Loading connection pattern..." source $val(cp) # # Define traffic model # puts "Loading scenario file..." source $val(sc) # Define node initial position in nam for {set i 0} {$i < $val(nn)} {incr i} { #30 defines the node size for nam $ns_ initial_node_pos $node_($i) 30 } # Telling nodes when the simulation ends for {set i 0} {$i < $val(nn)} {incr i} { $ns_ at $val(stop) "$node_($i) reset"; } $ns_ at $val(stop).0002 "puts \"ns_ EXITING...\" ; $ns_ halt" puts $tracefd "M 0.0 nn $val(nn) x $val(x) y $val(y) rp $val(rp)" puts $tracefd "M 0.0 sc $val(sc) cp $val(cp) seed $val(seed)" puts $tracefd "M 0.0 prop $val(prop) ant $val(ant)" #ending nam and the simulation $ns_ at $val(stop) "$ns_ nam-end-wireless $val(stop)" $ns_ at $val(stop) "stop" proc stop {} { global ns_ tracefd namtrace $ns_ flush-trace close $tracefd close $namtrace } puts "Starting Simulation..." $ns_ run Tỷ lệ phân phát gói tin thành công #!/usr/bin/perl # # Phạm Văn Tứ - K51MMT-UET-VNU. # GVHD: PGS.TS. Nguyễn Đình Việt. # GVĐHD: Ths. Đoàn Minh Phương. # # Tỷ lệ phân phát gói tin thành công (Hiệu suất đường truyền) #----------------------------------------------------> # Là tỷ lệ giữa số các gói tin được phân phát thành công tới đích # so với số các gói tin tạo ra bởi nguồn phát. # # Tư tưởng giải thuật: # - Ta dựa vào dấu hiệu trường: Trace level = AGT. Chỉ những gói tin gửi nhận của nút nguồn hoặc nút đích # thì trường Trace level mới được gán nhãn AGT (gói tin tầng giao vận).Các nút trung gian khác thực hiện # việc định tuyến, chuyển tiếp gói tin, hoạt động tại tầng Network nên Trace Level = RTR. # # - Do đó ta chỉ cần tính: # + Tổng số gói tin các nút nguồn đã gửi (src_sent) # + Tổng số gói tin các nút đích nhận được (dst_receive) # ==> Tỷ lệ phân phát gói tin thành công = dst_receive*100/src_sent. # # type: perl Pkt_success_rate.pl #==================================================== $infile=$ARGV[0]; $src_sent = 0; #Tổng số gói tin các nút nguồn gửi đi $dst_receive = 0; #Tổng số gói tin các nút đích nhận được $productivity = 0; #Hiệu suất đường truyền. open (DATA, "<$infile") || die "Loi mo file: $infile $!"; while (){ @x = split(' '); # Nút nguồn gửi gói tin if (($x[0] eq 's') && ($x[3] eq 'AGT') && ($x[6] eq 'tcp')) { $src_sent++; } # Nút đích nhận được gói tin if (($x[0] eq 'r') && ($x[3] eq 'AGT') && ($x[6] eq 'tcp')){ $dst_receive++; } } $productivity = $dst_receive*100/$src_sent; print STDOUT "Tổng số gói tin các nút nguồn gửi đi = $src_sent \n"; print STDOUT "Tổng số gói tin các nút đích nhận được = $dst_receive \n\n"; print STDOUT "Tỷ lệ phân phát gói tin thành công = $productivity % \n"; close DATA; exit(0); Thời gian thiết lập kết nối #!/usr/bin/perl # # Pham Van Tu - K51MMT - UET - VNU # GVHD: PGS.TS. Nguyen Dinh Viet # # Tinh thoi gian thiet lap ket noi: # Tinh tu khi nut nguon co yeu cau ket noi den khi no nhan duoc goi tin bien nhan (ACK) # # Type: perl Connection_time.pl # $infile=$ARGV[0]; $src=$ARGV[1]; $dst=$ARGV[2]; $start_time = 0; #Thoi diem nut nguon bat dau co yeu cau truyen $end_time = 0; #Thoi diem nut nguon nhan duoc Ack $connection_time = 0; #Thoi gian ket noi $src_ = 0; #Chi so nut nguon. $source = 0; #Dia chi nguon $destination = 0; #Dia chi dich open (DATA, "<$infile") || die "Loi mo file: $infile $!"; while (){ @x = split(' '); # Lay thong tin tu file tep vet $src_ = $x[2]; $source = $x[13]; $destination = $x[14]; # Xu ly xau(String) de lay ra truong so nham phuc vu cho viec so sanh. # Loai bo 2 dau gach duoi "_" trong truong chi so nut nguon (_node-ID_) $src_ = substr($src_, 1); $src_ = substr($src_, 0, -1); # Loai bo Port va dau [ truong dia chi nguon va dia chi dich. $source = substr($source, 1); $source = substr($source, 0, -2); $destination = substr($destination, 0, -2); # Nut nguon co nhu cau ket noi if ((($x[0] eq "s") || ($x[0] eq "+")) && ($src_ == $src) && ($x[3] eq 'AGT') && ($x[6] eq 'tcp') && ($source == $src) && ($destination == $dst) && ($x[17] eq '[0')){ $start_time = $x[1]; } # Nut nguon nhan duoc goi tin bien nhan (ACK) if (($x[0] eq 'r') && ($src_ == $src) && ($x[3] eq 'AGT')&& ($x[6] eq 'ack') && ($source == $dst) && ($destination == $src) && ($x[17] eq '[0')){ $end_time = $x[1]; $connection_time = $end_time - $start_time; last; } } print STDOUT "\nThoi gian thiet lap ket noi tu nut $src toi nut $dst = $connection_time\n\n"; close DATA; exit(0);