Tài liệu Các đề xuất cải tiến giao thức aodv nhằm hỗ trợ đảm bảo qos

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN GIA DŨNG CÁC ĐỀ XUẤT CẢI TIẾN GIAO THỨC AODV NHẰM ĐẢM BẢO HỖ TRỢ QOS LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội, năm 2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN GIA DŨNG CÁC ĐỀ XUẤT CẢI TIẾN GIAO THỨC AODV NHẰM ĐẢM BẢO HỖ TRỢ QOS Ngành: Công nghệ thông tin Chuyên ngành: Truyền dữ liệu và Mạng máy tính Mã số:8480102.01 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS NGUYỄN ĐÌNH VIỆT Hà Nội, năm 2019 ii LỜI CAM ĐOAN Tôi xin cam đoan luận văn thạc sĩ “Các đề xuất cải tiến giao thức AODV nhằm đảm bảo hỗ trợ QoS” là công trình nghiên cứu của riêng tôi và được sự hướng dẫn của PGS. TS. Nguyễn Đình Việt. Các nội dung nghiên cứu và kết quả trong đề tài là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Những phân tích, đánh giá được tác giả thu thập từ các nguồn khác nhau có ghi rõ trong tài liệu tham khảo. Tác giả Nguyễn Gia Dũng i LỜI CẢM ƠN Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới PGS. TS. Nguyễn Đình Việt, người thầy đã chỉ bảo và hướng dẫn tận tình cho tôi trong suốt quá trình học thạc sĩ và trong suốt quá trình nghiên cứu và thực hiện luận văn này. Tôi xin chân thành cảm ơn sự dạy bảo, giúp đỡ, tạo điều kiện của các thầy, cô trường Đại học Công nghệ, Đại học Quốc gia Hà Nội trong suốt quá trình tôi học tập tại trường. Cuối cùng, tôi xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, đồng nghiệp - những người luôn ở bên tôi trong lúc khó khăn, động viên, khuyến khích tôi trong cuộc sống và công việc. Do thời gian và điều kiện có hạn nên luận văn không tránh khỏi có những thiếu sót, tôi rất mong nhận được sự góp ý từ bạn bè, thầy cô và những người quan tâm đến đề tài này. Tôi xin chân thành cảm ơn! Tác giả Nguyễn Gia Dũng ii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Cụm từ đầy đủ STT Từ viết tắt 1 ACO 2 AODV Adhoc On-Demand Distance Vector 3 DSDV Destination-Sequenced Distance-Vector Routing 4 DSR 5 HARP 6 LSD 7 MANET 8 NDMLNR 9 OLSR 10 QoS 11 RERR Route Error 12 RREP Route Reply 13 RREQ Route Request 14 TORA Temporally Ordered Routing Algorithm 15 ZRP Ant Colony Optimization Dynamic Source Routing Hybrid Ad hoc Routing Protocol Link Stability Degree Mobile Adhoc Network Node Disjoint Multipath routing considering Link and Node Stability Optimized Link State Routing Quality of Sevice Zone Routing Protocol iii DANH MỤC HÌNH VẼ Hình 1.1. Mạng MANET phân cấp (Hierarchical).......................................................... 3 Hình 1.2 Mạng MANET kết hợp (Aggregate)..................................................................4 Hình 1.3: Cấu trúc của NS-2 ........................................................................................... 9 Hình 1.4: Luồng các sự kiện cho file Tcl chạy trong NS-2 ........................................... 10 Hình 1.5: Kiến trúc của NS-2 ........................................................................................ 10 Hình 1.6: C++ và OTcl: Sự đối ngẫu ........................................................................... 11 Hình 1.7: TclCL hoạt động như liên kết giữa A và B .................................................... 11 Hình 2.1. Đường truyền dữ liệu theo chiến lược định tuyến phẳng .............................. 17 Hình 2.2. Đường truyền dữ liệu theo chiến lược định tuyến phân cấp ......................... 17 Hình 2.3. Truyền dữ liệu theo định tuyến nguồn ........................................................... 18 Hình 2.4. Truyền dữ liệu theo phương pháp định tuyến từng chặng ............................ 18 Hình 2.5: Quá trình lan truyền của gói tín RREQ ........................................................ 23 Hình 2.6: Đường đi ngược được tạo ra khi RREQ lan truyền trong môi trường ......... 25 Hình 2.7: Đường đi từ nút nguồn và nút đích được hình thành. ................................... 26 Hình 2.8: Lan truyền gói tin RERR ............................................................................... 28 Hình 3.1: Mạng bầy kiến ............................................................................................... 31 Hình 3.2: Hành vi bầy kiến tìm thức ăn ........................................................................ 32 Hình 4.1:Gói RREQ. ...................................................................................................... 44 Hình 4.2: Ví dụ .............................................................................................................. 46 iv MỤC LỤC LỜI CAM ĐOAN ........................................................................................................................... i LỜI CẢM ƠN.................................................................................................................................. ii MỤC LỤC ....................................................................................................................................... v CHƯƠNG 1: GIỚI THIỆU CHUNG VỀ MẠNG MANET ........................................................ 1 1.1. Tổng quan về mạng MANET.............................................................................................. 1 1.1.1 Khái niệm về mạng MANET (Mobile Adhoc Network) ............................................ 1 1.1.2. Đặc điểm của mạng MANET ...................................................................................... 1 1.1.3. Phân loại mạng MANET.............................................................................................. 2 1.2. Các vấn đề cần giải quyết .................................................................................................... 4 1.2.1 Định tuyến trong mạng MANET .................................................................................. 4 1.2.2 Vấn đề tiết kiệm năng lượng ......................................................................................... 5 1.2.3 Vấn đề đảm bảo chất lượng dịch vụ ............................................................................. 6 1.3. Các độ đo hiệu năng được dùng trong luận văn ................................................................ 8 1.4 Giới thiệu bộ mô phỏng NS2 được sử dụng để đánh giá hiệu năng mạng ........................ 9 1.4.1 Giới thiệu về NS2 .......................................................................................................... 9 1.4.2 C++ và OTcL : ............................................................................................................. 10 1.4.3 Các đặc tính của NS-2 ................................................................................................. 12 1.5 Mục tiêu nghiên cứu luận văn ............................................................................................ 12 CHƯƠNG 2. MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET ................. 14 2.1 Phân loại các kỹ thuật định tuyến ...................................................................................... 14 2.1.1 Link state và Distance Vector .................................................................................... 14 2.1.2 Định tuyến chủ ứng (Proactive) và phản ứng (Reactive)......................................... 15 2.1.3 Định tuyến phẳng và định tuyến phân cấp ................................................................. 16 2.1.4 Định tuyến nguồn và định tuyến từng chặng ............................................................. 17 2.1.5 Định tuyến đơn đường và định tuyến đa đường ........................................................ 19 2.2 Giao thức DSDV (Destination – Sequenced Distance – Vector) [1]............................... 19 2.2.1Quản lý bảng định tuyến .............................................................................................. 20 2.2.2 Cập nhật bảng định tuyến trong DSDV ..................................................................... 20 2.2.3 Quản lý sự thay đổi của Topology ............................................................................. 21 2.3. Giao thức AODV [1] ......................................................................................................... 21 2.3.1. Tổng quan về giao thức AODV ................................................................................. 21 2.3.2 Cơ chế hoạt động ......................................................................................................... 22 2.3.3 Quản lý cục bộ ............................................................................................................. 26 v 2.3.4 Duy trì đường đi .......................................................................................................... 27 2.3.5 Thời gian hết hạn và việc hủy bỏ một đường đi ........................................................ 28 CHƯƠNG 3. SỬ DỤNG THUẬT TOÁN BẦY KIẾN TRONG TỐI ƯU ĐỊNH TUYẾN MẠNG MANET ........................................................................................................................... 29 3.1. Giới thiệu ............................................................................................................................ 29 3.2. Thuật toán tối ưu bầy kiến nhân tạo ................................................................................. 30 3.2.1 Định tuyến sử dụng ACO (Ant colony Optimization) .............................................. 33 3.2.2 Một số đặc tính của ACO trong việc định tuyến ...................................................... 33 3.3. Thuật toán OLSR ............................................................................................................... 33 3.3.1. Cảm nhận nút liền kề................................................................................................. 34 3.3.2. Các trạm chuyển tiếp đa điểm (MPR) ...................................................................... 34 3.3.3. Thông tin kiểm soát cấu trúc ..................................................................................... 34 3.3.4. Tìm đường định tuyến ................................................................................................ 35 3.3.5. Định tuyến từ nguồn ................................................................................................. 35 3.4. Triển khai thuật toán ACO ................................................................................................ 36 3.4.1. Giai đoạn tìm đường định tuyến ............................................................................... 36 3.4.2. Giai đoạn duy trì đường định tuyến ........................................................................ 37 3.5.Kết luận ............................................................................................................................... 37 CHƯƠNG 4. Định tuyến đảm bảo QoS trong Manets dựa trên thông số vị trí và năng lượng 37 4.1. Tổng quan ........................................................................................................................... 37 4.2. Giới thiệu ............................................................................................................................ 38 4.3. Giao thức nguồn động (DSR - Dynamic Source Routing).............................................. 39 4.4. Vấn đề phát sinh................................................................................................................. 40 4.5. Phương pháp sử dụng ........................................................................................................ 41 4.6. Đề xuất: Định tuyến đa đường node rời rạc có xét đến liên kết và ổn định node NDMLNR (Node Disjoint Multipath routing considering Link and Node Stability) [5] .... 42 4.6.1. Phát hiện định tuyến ................................................................................................... 43 4.6.2. Lựa chọn định tuyến ................................................................................................... 46 4.6.3. Bảo trì định tuyến ....................................................................................................... 46 4.7. Ví dụ ................................................................................................................................... 46 4.8. Kết luận .............................................................................................................................. 48 CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU.......................................................... 49 5.1 Kết quả đạt được của luận văn ............................................................................................... 49 5.2 Hướng nghiên cứu................................................................................................................... 50 TÀI LIỆU THAM KHẢO ............................................................................................................ 51 vi vii CHƯƠNG 1: GIỚI THIỆU CHUNG VỀ MẠNG MANET 1.1. Tổng quan về mạng MANET 1.1.1 Khái niệm về mạng MANET (Mobile Adhoc Network) Với rất nhiều ưu điểm của công nghệ truyền thông không dây, các mạng di động không dây đã phát triển rất mạnh thời gian gần đây. Có thể chia mạng di động không dây thành hai kiểu mạng: mạng có hạ tầng và mạng không có hạ tầng. Trong mạng có hạ tầng, truyền thông giữa các phần tử mạng phụ thuộc vào sự hỗ trợ của hạ tầng mạng, các thiết bị đầu cuối di động và qua các điểm truy nhập (các trạm cơ sở). Mạng MANET (Mobile Adhoc Network) là một tập hợp các nút di động có thể được triển khai mà không cần bất kỳ cơ sở hạ tầng tập trung nào. Mạng ad hoc rất linh hoạt và có thể tự cấu hình. Do có cơ sở hạ tầng phân tán nên không có bộ định tuyến được cài đặt sẵn nào có thể chuyển tiếp các gói từ máy chủ này sang máy chủ khác. Nhiệm vụ này phải được đảm nhiệm bởi các nút di động phân tán của mạng. Mỗi nút có vai trò như nhau, có nghĩa là tất cả chúng có thể hoạt động như một máy chủ và như một bộ định tuyến. Do đó, hoạt động cơ bản của mạng này phụ thuộc vào sự hợp tác của các nút để cung cấp các tuyến truyền thông. Trong MANET, mỗi nút hoạt động như một bộ định tuyến và như một máy chủ lưu trữ, thậm chí cấu trúc liên kết của mạng cũng có thể thay đổi nhanh chóng do các thiết bị di chuyển tự do theo mọi hướng. Mỗi nút di động có một phạm vi truyền giới hạn, các gói tin từ nút nguồn cần chuyển tới một nút đích có thể không nằm trong phạm vi truyền của nút nguồn. Vì vậy, cần có sự trợ giúp của các nút trung gian để chuyển tiếp gói tin. Để thực hiện được công việc này, các nút mạng phải sử dụng giao thức định tuyến phù hợp. 1.1.2. Đặc điểm của mạng MANET Do MANET là một mạng không dây hoạt động không cần sự hỗ trợ của hạ tầng mạng cơ sở trên cơ sở truyền thông đa chặng giữa các thiết bị di động vừa đóng vai trò là thiết bị đầu cuối, vừa đóng vai trò là bộ định tuyến nên mạng MANET còn có một số đặc điểm nổi bật sau: Thiết bị tự trị đầu cuối (Autonomous terminal): mỗi thiết bị di động đầu cuối trong MANET là một node tự trị, mang chức năng của host và router. 1 Các node di động này có khả năng xử lý cơ bản của một host, vừa có thể chuyển đổi chức năng như một router. Hoạt động phân tán (Distributed operation): Vì không có hệ thống cơ sở hạ tầng mạng nên việc kiểm soát và quản lý hoạt động của mạng được đảm nhận bởi các thiết bị đầu cuối. Các node trong MANET đòi hỏi phải có sự phối hợp với nhau và hoạt động như một bộ chuyển tiếp (relay) để thực hiện chức năng của mình. Tô pô mạng động (dynamic network topology): vì các node là di động tự do theo mọi hướng, nên cấu trúc mạng và các kết nối giữa các thiết bị đầu cuối có thể thay đổi theo thời gian. MANET sẽ tự thích ứng định tuyến theo sự di động của các node mạng. Các node trong mạng thiết lập định tuyến động với nhau trong khi di chuyển và tự hình thành các mạng riêng với nhau. Ngoài ra, một user trong MANET có thể không chỉ hoạt động trong mạng MANET nội bộ mà còn có thể yêu cầu truy cập vào một mạng cố định khác, ví dụ như mạng Internet. Chất lượng liên kết hạn chế: Các liên kết không dây thường có băng thông nhỏ hơn so với các liên kết có dây. Các kết nối có thể được chia sẻ qua một vài chặng, vấn đề suy giảm tín hiệu, nhiễu và các yếu tố khác, thông lượng hiệu dụng của các liên kết không dây thường thấp hơn nhiều so với tốc độ truyền tối đa theo lý thuyết của môi trường truyền không dây. Các thiết bị đầu cuối có tài nguyên hạn chế: Mỗi nút di động trong mạng MANET có thể là một nút cảm biến, một điện thoại thông minh hoặc một máy tính xách tay. Thông thường các thiết bị này có tài nguyên hạn chế so với các máy tính trong mạng có dây và không dây truyền thống về tốc độ xử lý, dung lượng bộ nhớ và năng lượng nguồn pin nuôi sống hoạt động của nút. Vì vậy cần phải tối ưu hóa các thuật toán và cơ chế. Độ bảo mật thấp ở mức độ vật lý: Mạng không dây di động thường gặp các vấn đề về an ninh nhiều hơn so với mạng có dây như nghe lén, giả mạo và tấn công từ chối dịch vụ... vì dễ triển khai trong mạng MANET hơn là trong mạng có dây truyền thống. 1.1.3. Phân loại mạng MANET Mạng MANET đẳng cấp (phẳng, Flat): 2 Trong mạng MANET đẳng cấp tất cả các node có vai trò ngang hàng với nhau (peer to peer) và các node đóng vai trò như các router định tuyến dữ liệu gói trên mạng. Kiến trúc mạng này thích hơp trong những topo có các node di chuyển nhiều. Mạng MANET phân cấp (Hierarchical): Đây là mô hình được sử dụng phổ biến nhất. Trong mô hình này thì mạng chia thành các domain, trong mỗi domain bao gồm một hoặc nhiều cluster (cụm) mỗi cluster gồm nhiều node. Có hai loại node là master node và nomal node. Master node là node quản trị, có chức năng của một router với nhiệm vụ chuyển dữ liệu của các node trong cluster đến các node trong cluster khác và ngược lại (giống như một gateway). Normal node là các node nằm trong cùng một cluster. Nó có thể kết nối với các node trong cluster hoặc kết nối với các cluster khác thông qua master node. Hình 1.1. Mạng MANET phân cấp (Hierarchical) Mạng MANET kết hợp (Aggregate): Mỗi node bao gồm hai mức topo : Topo mức thấp (node level), và topo mức cao (zone level). Mỗi node đặc trưng bởi: node ID và zone ID. Trong một Zone có thể áp dụng kiến trúc đẳng cấp hoặc kiến trúc phân cấp. 3 Hình 1.2 Mạng MANET kết hợp (Aggregate) 1.2. Các vấn đề cần giải quyết 1.2.1 Định tuyến trong mạng MANET Việc thiết kế các giao thức định tuyến trong mạng Adhoc thường xem xét một số các yếu tố sau đây [1] Hoạt động phân tán: cách tiếp cận tập trung 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 các tuyến và phân phát cho tất cả các nút trong mạng. Trong thời gian đó, cấu hình mạng có thể đã có các thay đổi, các thông tin định tuyến mà các nút nhận được không còn giá trị sử dụng. Không có lặp định tuyến: hiện tượng xảy ra khi một phần nhỏ các gói tin quay vòng trong mạng trong một khoảng thời gian nào đó. Một giải pháp có thể áp dụng là sử dụng giá trị thời gian quá hạn cho các gói tin. Tính toán đường dựa trên yêu cầu: thay thế việc tính toán và duy trì định tuyến tới tất cả các nút tại tất cả các thời điểm, kể cả khi chưa có yêu cầu truyền, bằng việc thích ứng với dạng truyền thông, chỉ thực hiện tìm đường khi một nút có yêu cầu truyền đến một nút khác trong mạng. Mục đích là để tiết kiệm năng lượng và băng thông, mặc dù độ trễ định tuyến tăng lên do sự phát hiện đường cần thời gian. Tính toán đường trước: Khi cần có độ trễđịnh tuyến nhỏvà băng thông cũng như các tài nguyên năng lượng cho phép, việc tính toán đường trước khi có yêu cầu truyền sẽ giảm độ trễ phân phát gói tin. 4 Bảo mật: Giao thức định tuyến mạng Adhoc có khả năng bị tấn công dễ dàng bằng một số dạng như xâm nhập truyền thông, phát lại, thay đổi các tiêu đề gói tin, điều hướng các thông điệp định tuyến. Do vậy, cần có các 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. Hoạt động nghỉ: giao thức định tuyến cần có cơ chế bảo tồn năng lượng của các nút khi có thể, ví dụ khi một nút không có yêu cầu truyền hoặc không có nhiệm vụ chuyển tiếp gói tin cho các nút khác. Hỗ trợ liên kết đơn hướng: Khi thực hiện định tuyến đa chặng trong mạng Adhoc, giao thức cần hỗ trợ trường hợp có một số chặng là khi các liên kết đơn hướng, nghĩa là tuyến đường từ nút nguồn đến nút đích và tuyến đường từ nút đích đến nút nguồn có thể không hoàn toàn trùng nhau 1.2.2 Vấn đề tiết kiệm năng lượng Để thiết lập các tuyến đường giữa các nút, một giao thức định tuyến hiệu quả là cần thiết kế để việc khám phá đường trong mạng MANET. Năng lượng của nút là một trong những tiêu chí thiết kế quan trọng cho mạng MANET do cấu trúc liên kết động của mạng MANET. Các nút di động thường sử dụng pin nên thời gian hoạt động sẽ phụ thuộc vào dung lượng pin của chung. Khi một nút di động bị ngưng hoạt động do hết năng lượng sẽ ảnh hướng tới tất cả các kết nối đa chặng đi qua nó và phải xây dựng lại các đường định tuyến mới, sẽ làm giảm hiệu suất của mạng. Việc xây dựng các tuyến đường mới hay khôi phục các tuyến đường bị lỗi sẽ cần đến việc gửi, nhận và xử lý nhiều gói tin sẽ tiếp tục tiêu hao năng lượng của mỗi node lớn hơn, từ đó làm ảnh hưởng đến thời gian hoạt động của mạng giảm bớt. Ngoải ra, một nút di động ngoài việc chủ động gửi hoặc nhận gói tin, khi nó ở trạng thái nhàn rỗi vẫn phải liên lạc với các nút khác trong mạng xem có yêu cầu truyền thông từ các nút khác hay không. Để có một giao thức định tuyến sử dụng năng lượng hiệu quả là giao thức làm giảm thiểu năng lượng dành cho việc truyền và nhận gói dữ liệu, sửa lỗi hoặc trong thời gian không hoạt động. Nó xác định đường đi tối ưu để giảm thiểu năng lượng cần để chuyển gói dữ liệu đến đích và khi không hoạt động có thể chuyển sang trạng thái ngủ để tranh tiêu hao năng lượng. 5 Điều này có thể dẫn đến việc tiết kiệm năng lượng một cách đáng kể, đặc biệt khi các ứng dụng truyền thông trên mạng có yêu cầu truyền thông thấp. Tuy nhiên nó đòi hỏi một giao thức định tuyến được thiết kế tốt để đảm bảo khả năng truyền dữ liệu ngay cả khi hầu hết các nút ngủ và không chuyển tiếp các gói tin cho nút khác. Một cách tiếp cận khác để tối ưu hóa năng lượng hoạt động là phương pháp phân phối tải. Đối với việc xác định tuyến tối ưu và tắt tạm thời các nút khi không sử dụng là để giảm thiểu tiêu hao năng lượng của từng nút riêng biệt, thì mục tiêu chính của phương pháp phân bổ tải trọng là để cân bằng việc sử dụng năng lượng giữa các nút và để tối đa hóa tuổi thọ mạng bằng cách tránh việc sử dụng thường xuyên một số nút mạng nhất định khi lựa chọn một con đường định tuyến, dù tuyến đi qua các nút đó là tuyến tối ưu. [1] 1.2.3 Vấn đề đảm bảo chất lượng dịch vụ 1.2.3.1 Giới thiệu QoS (Quality of Service) là khả năng giúp cho việc truyền dữ liệu với thời gian trễ, tỉ lệ mất/ lỗi gói tin nằm trong phạm vi cho phép và cung cấp băng thông đủ lớn cho những ứng dụng truyền thông đa phương tiện thời gian thực. Vấn đề chất lượng dịch vụ được nghiên cứu và triển khai áp dụng trên môi trường mạng Internet và các mạng khác từ khá lâu, các vấn đề chính được đề cập đến hiện nay như định tuyến có QoS, đảm bảo QoS bằng cách kiểm soát truy cập và đặt trước tài nguyên. Mạng MANET và mạng có dây truyền thống có sự khác biệt cơ bản về tính di động, hạ tầng mạng, nguồn năng lượng của các nút mạng và khả năng tự tổ chức giữa các kiến trúc mạng. Sự khác biệt này làm nảy sinh rất nhiều khác biệt và yêu cầu cải tiến trong những mảng bài toán mô hình hóa, điều khiển môi trường truyền, định tuyến, bảo mật, tổ chức thông tin, đảm bảo chất lượng dịch vụ, tiết kiệm năng lượng cho nguồn… 1.2.3.2. Những vấn đề của việc đảm bảo chất lượng dịch vụ [3] Kiểm soát phi tập trung (Decentralized control) Các nút có thể tham gia hoặc rời khỏi mạng liên tục và mạng được thiết lập tự phát -> dẫn đến sự phức tạp về thuật toán. Kênh không thể dự đoán trước: Lỗi bit là sự cố phát sinh do các kênh không dây không đáng tin cậy. Các kênh này gây ra tỷ lệ lỗi bit là cao do nhiễu, 6 nhiễu nhiệt, hiệu ứng fading đa đường, v.v. Điều nàydẫn đến tỷ lệ phân phối gói thấp. Ngoài ra còn dẫn đến mất thông tin và môi trường xung quanh. Sự mất mát dữ liệu (Data Loss): Mất dữ liệu hoặc mất gói trong quátrình gửi dữ liệu Bảo trì tuyến đường (Route Maintenance): Bản chất động của topo mạng và thay đổi môi trường truyền thônglàm cho việc duy trì thông tin trạng thái mạng rất khó khăn. - Các đường định tuyến đã được thiết lập có thể bị hỏng trong suốtquá trình truyền dữ liệu, dẫn đếnsự cần thiết phải duy trì và tái thiết các đường định tuyến với chi phí tối thiểu và giải quyết nguyên nhân mất kết nội. - Định tuyến có QoS sẽ yêu cầu đặt các tài nguyên tại các nút trung gian. Sự di động của nút mạng (Node mobility):các nút ở đây là các nút di động, chúng di chuyển một cách độc lập và ngẫu nhiên ở mọi hướng và mọi tốc độ thông tin tô pô mạngcần phải được cập nhật thường xuyên và phù hợp để cung cấp định tuyến và giảm tỷ lệ mất gói. Nguồn năng lượng dung lượng thấp: Các nút di động có nguồn điện hạn chế so với các nút trong mạng có dây.Việc cung cấp QoS tiêu tốn nhiều điện hơn có thể làm giảm sự hoạt động của các nút. Tính an ninh thích hợp: do các nút không dây di động nên bảo mật kém, dễ bị truy cập trái phép nên khó đảm bảo được QoS. Vì vậy cần thiết kế giao thức đảm bảo an toàn bảo mật cho mạng. 1.2.3.3. Các tham số Các ứng dụng khác nhau có yêu cầu về QoS khác nhau. Ví dụ, đối với các ứng dụng Multimedia thì dải thông (bandwidth), độ trễ (delay) và biến động trễ (delay-jitter) là các tham số chính. Các ứng dụng quân sự thì đòi hỏi yêu cầu bảo mật nghiêm ngặt. [3] Khả năng đáp ứng(Responsiveness): quan trọng trong việc trải nghiệm mạng của người dùng. Dung lượng và thông lượng (Capacity and throughput): 1 thước đo quan trọng của người dùng với các ứng dụng mạng, được định nghĩa là tốc độ gửi hoặc nhận dữ liệu 7 Độ trễ (Delay):thời gian cần thiết cho một gói tin truyền tới đích. Trễ lan truyền (Propagation Delay): thời gian từ lúc truyền đến khi kết thúc nhận gói tin của 1 liên kết Thời gian khứ hồi – RTT (Round-Trip Time): bằng thời gian gửi + thời gian xác nhận đã được nhận. Biến động trễ - Delay Variation (Jitter) độ lệch không mong muốn khi có sự thay đổi trong tỉ lệ xuất hiện của các gói tin định kỳ. 1.3. Các độ đo hiệu năng được dùng trong luận văn Theo nghĩa chung, hiệu năng là một độ đo công việc mà một hệ thống thực hiện được. Hiệu năng chủ yếu được xác định bởi tính sẵn sàng để dùng, thông lượng và thời gian đáp ứng. Trong mạng Adhoc, các giới hạn về tài nguyên mạng yêu cầu các giao thức bên cạnh các yếu tố hiệu suất nêu trên cần đảm bảo việc dùng hiệu quả các tài nguyên hạn chế này. Với các giao thức định tuyến, đó chính là chi phí để thực hiện các yêu cầu định tuyến được thể hiện bởi mức tải định tuyến Do vậy, luận văn sử dụng các độ đo sau để đánh giá hiệu quả các giao thức định tuyến trong các mạng mô phỏng: [1] Tỉ lệ gói tin được phân phát thành công (Packet delivery fraction): 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. Trễ đầu cuối trung bình của các gói dữ liệu (Average end to end data packet delay): Là độ trễ toàn phần được tính từ khi gói tin phát đi từ ứng dụng phát cho tới khi được nhận bởi ứng dụng nhậ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ễ phát lại tại tầng MAC, và thời gian trễ truyền. Thông lượng dữ liệu đầu cuối (End-to-end data throughput): Tổng số dữ liệu của các gói tin tạo bởi mọi nguồn đo được trong một khoảng thời gian mô phỏng, tính bằng kbit/s. Tải định tuyến chuẩn hóa (Normalized Routing Load): Là tỷ lệ giữa số các gói tin định tuyến trên số gói tin dữ liệu được phân phát thành công. Nếu gói tin định tuyến đi qua nhiều chặng thì mỗi chặng được tính như một lần truyền thông. 8 1.4 Giới thiệu bộ mô phỏng NS2 được sử dụng để đánh giá hiệu năng mạng 1.4.1 Giới thiệu về NS2 NS-2 là phần mềm mô phỏng mạng, hoạt động của nó được điều khiển bởi các sự kiện rời rạc. NS-2 được thiết kế và phát triển theo kiểu hướng đối tượng, được phát triển tại đại học California, Berkely. Bộ phần mềm này được viết bằng ngôn ngữ C++ và OTcl. [7] Hình 1.3: Cấu trúc của NS-2 Để sử dụng NS-2, người dùng lập trình bằng ngôn ngữ kịch bản OTcl. người dùng có thể thêm các mã nguồn Otcl vào NS-2 bằng cách viết các lớp đối tượng mới trong OTcl. Những lớp này khi đó sẽ được biên dịch cùng với mã nguồn gốc. Kịch bản OTcl có thể thực hiện những việc sau: - Khởi tạo Bộ lập lịch Sự kiện - Thiết lập Mô hình mạng dùng các đối tượng Thành phần Mạng - Báo cho nguồn traffic khi nào bắt đầu truyền và ngưng truyền packet trong Bộ lập lịch Sự kiện Phụ thuộc vào mục đích của user đối với kịch bản mô phỏng OTcl mà kết quả mô phỏng có thể được lưu trữ như file trace. Định dạng file trace sẽ được tải vào trong các ứng dụng khác để thực hiện phân tích: - File nam trace (file.nam) được dùng cho công cụ minh họa mạng NAM - File Trace (file.tr) được dùng cho công cụ Lần vết và Giám sát Mô phỏng XGRAPH hay TRACEGRAPH 9 Hình 1.4: Luồng các sự kiện cho file Tcl chạy trong NS-2 1.4.2 C++ và OTcL : Hình 1.5 biểu diễn kiến trúc chung của NS-2. Người dùng có thể tưởng tượng mình đang đứng ở góc trái dưới, thiết kế và chạy các mô phỏng trong Tcl. Tcl dùng các đối tượng mô phỏng trong OTcl. Các đối tượng Bộ lập lịch Sự kiện và hầu hết các đối tượng Thành phần Mạng thực thi bằng C++ và sẵn có cho OTcl qua một liên kết OTcl. Liên kết OTcl này được thực thi dùng TclCL. [7] Hình 1.5: Kiến trúc của NS-2 - NS-2 sử dụng hai ngôn ngữ lập trình: Ngôn ngữ kịch bản (Tcl – Tool Command Language,) và Ngôn ngữ lập trình hệ thống (C/C++) - NS là tầng biên dịch Tcl để chạy các kịch bản Tcl - Bằng cách sử dụng C++/OTcl, bộ mô phỏng mạng phải hoàn toàn là hướng đối tượng 10 Hình 1.6 chỉ ra các đối tượng C++ có liên kết OTcl. Khi đó, nếu chúng tạo nên một phân cấp thì các đối tượng OTcl cũng có một phân cấp tương ứng như vậy. Hình 1.6: C++ và OTcl: Sự đối ngẫu TclCL là ngôn ngữ được sử dụng để cung cấp liên kết giữa C++ và OTcl. Các kịch bản Tcl/OTcl được viết để thiết lập và cấu hình topology của mạng. TclCL cung cấp liên kết giữa phân cấp lớp, khởi tạo đối tượng, nối kết biến và gửi lệnh. Hình 1.7: TclCL hoạt động như liên kết giữa A và B NS-2 sử dụng đến hai ngôn ngữ vì Bộ mô phỏng cần thực hiện hai việc khác nhau: Một mặt là vì các mô phỏng cho các giao thức yêu cầu một ngôn ngữ lập trình hệ thống có thể tính toán một cách hiệu quả các byte, các tiêu đề packet và các thuật toán thực thi đang chạy trên một tập dữ liệu lớn. Với tác vụ này, run-time speed (tốc độ thời gian chạy thực) là quan trọng trong khi turn-around time (thời gian thay đổi) thì ít quan trọng hơn. Turn-around time bao gồm thời gian chạy mô phỏng, thời gian tìm lỗi, thời gian sửa lỗi, thời gian biên dịch lại và thời gian chạy lại. Hầu hết định tuyến được viết bằng OTcl (dù thuật toán Dijkstra lõi viết bằng C++). Mô phỏng HTTP có từng luồng bắt đầu tại OTcl nhưng việc xử lý 11