Luận văn Đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng manet

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐOÀN CAO THANH ĐÁNH GIÁ CHI PHÍ TÌM ĐƯỜNG CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET LUẬN VĂN THẠC SĨ Hà Nội - 2011 1 Lời cám ơn Trước hết tôi xin gửi lời cám ơn tới các thầy cô giáo trong Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội đã tận tình chỉ bảo tôi trong suốt khóa học, cám ơn tập thể lớp K15T3 và đặc biệt là tới thầy giáo, PGS.TS Nguyễn Đình Việt, người đã nhiệt tình hướng dẫn, chỉ bảo tôi trong công việc nghiên cứu và học tập. Tôi cũng chân thành cám ơn tới các thành viên trong nhóm nghiên cứu với những góp ý quý báu trong quá trình thực hiện đề tài. Sau cùng tôi muốn gửi lời cám ơn tới gia đình và người thân của tôi, những người đã luôn khuyến khích và động viên tôi trong suốt khóa họ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 những thiếu sót, tôi rất mong sự góp ý của bạn bè, thầy cô và những người quan tâm đến đề tài này. 2 Lời cam đoan Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Luận văn là kết quả của quá trình học tập, nghiên cứu trong suốt hơn hai năm cao học. Trong các nội dung của luận văn, những điều được trình bày hoặc là kết quả của cá nhân hoặc là kết quả tổng hợp từ nhiều nguồn tài liệu khác. Những kết quả nghiên cứu nào của cá nhân đều được chỉ ra rõ ràng trong luận văn. Các thông tin tổng hợp hay các kết quả lấy từ nhiều nguồn tài liệu khác đều được trích dẫn đầy đủ và hợp lý. Tất cả tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình Hà Nội, Tháng 3, 2011 3 Mục lục Lời cám ơn ....................................................................................................................... 1 Lời cam đoan.................................................................................................................... 2 Danh mục các kí hiệu, các chữ viết tắt ............................................................................ 5 Danh mục các hình vẽ ...................................................................................................... 7 Danh mục các bảng .......................................................................................................... 8 Chương 1. GIỚI THIỆU CHUNG ................................................................................... 9 1.1. Đặt vấn đề [15] ..................................................................................................... 9 1.2. Mục tiêu nghiên cứu.............................................................................................. 9 1.3. Tổ chức của luận văn........................................................................................... 10 Chương 2. TỔNG QUAN VỀ MẠNG WLAN VÀ MẠNG MANET .......................... 11 2.1. Giới thiệu và phân loại mạng không dây [15]..................................................... 11 2.1.1. Phân loại theo định dạng và kiến trúc mạng................................................. 12 2.1.2. Phân loại theo phạm vi bao phủ truyền thông .............................................. 13 2.1.3. Phân loại theo công nghệ truy cập đường truyền ......................................... 14 2.1.4. Phân loại theo các ứng dụng mạng ............................................................... 14 2.2. Mạng LAN không dây (WLAN) ......................................................................... 14 2.2.1. Khái niệm về WLAN.................................................................................... 14 2.2.2. Lịch sử ra đời mạng WLAN [22] ................................................................. 16 2.2.3. Giao thức tầng con MAC trong WLAN [12] ............................................... 17 2.3. Mạng không dây đặc biệt MANET [15] ............................................................. 22 2.3.1. Sự phát triển và các ứng dụng của mạng MANET....................................... 22 2.3.2. Các đặc điểm của mạng MANET................................................................. 23 Chương 3. CÁC GIAO THỨC ĐỊNH TUYẾN MẠNG MANET ................................ 25 3.1. Giới thiệu về bài toán định tuyến [15] ................................................................ 25 3.2. Các kĩ thuật định tuyến mạng MANET [10]....................................................... 26 3.2.1. Định tuyến chủ động và định tuyến phản ứng lại......................................... 26 3.2.2. Định tuyến đơn đường và định tuyến đa đường ........................................... 26 3.2.3. Định tuyến dựa vào bảng và định tuyến khởi tạo phía nguồn ...................... 26 3.2.4. Các kĩ thuật khôi phục .................................................................................. 27 3.2.5. Chiến lược lựa chọn tuyến............................................................................ 28 3.2.6. Cập nhật định kỳ và cập nhật theo sự kiện ................................................... 28 3.2.7. Cấu trúc phẳng và cấu trúc phân cấp ............................................................ 28 3.3. Các giao thức định tuyến chủ yếu trong mạng MANET [8]............................... 29 3.3.1. Giao thức DSDV (Destination-Sequenced Distance Vector) [4] ................. 29 3.3.2. Giao thức CGSR (Clusterhead Gateway Switch Routing) [5] ..................... 30 3.3.3. Giao thức WRP (Wireless Routing Protocol) [14]....................................... 31 3.3.4. Giao thức OLSR (Optimized Link State Routing) [16] ............................... 32 3.3.5. Giao thức AODV (Ad Hoc On-Demand Distance Vector) [3] .................... 33 3.3.6. Giao thức DSR (Dynamic Source Routing) [6] ........................................... 34 4 3.3.7. Giao thức TORA (Temporally-Ordered Routing Algorithm) [11] .............. 36 3.3.8. Giao thức ABR (Associativity-Based Routing) [2]...................................... 38 3.3.9. Giao thức SSR (Signal Stability Routing) [14] ............................................ 40 3.3.10. So sánh các giao thức định tuyến chủ yếu trong mạng MANET [3]-[8] ... 40 Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG CHI PHÍ TÌM ĐƯỜNG CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN MẠNG MANET VỚI CÁC NGỮ CẢNH KHÁC NHAU ............................................................................................................................ 45 4.1. Phân tích và lựa chọn phương pháp mô phỏng để đánh giá [1].......................... 45 4.2. Bộ mô phỏng NS2 ............................................................................................... 46 4.2.1. Giới thiệu [1] ................................................................................................ 46 4.2.2. Cấu trúc phần mềm của NS2 ........................................................................ 48 4.3. Thiết lập mô phỏng mạng MANET trong NS2................................................... 48 4.3.1. Mô hình không dây cơ bản trong NS2 [9].................................................... 48 4.3.2. Quá trình mô phỏng mạng MANET với NS2 [1]......................................... 52 4.3.3. Tích hợp giao thức TORA và OLSR vào bộ mô phỏng NS2....................... 54 4.4. Đánh giá bằng mô phỏng chi phí tìm đường một số giao thức định tuyến chủ yếu trong mạng MANET............................................................................................ 56 4.4.1. Các độ đo hiệu năng được đánh giá [1] ........................................................ 56 4.4.2. Thiết lập các lựa chọn, tham số mô phỏng [17] ........................................... 57 4.4.3. Các ngữ cảnh mô phỏng ............................................................................... 57 4.4.4. Đánh giá, nhận xét chi phí tìm đường của một số giao thức định tuyến mạng MANET .................................................................................................................. 73 KẾT LUẬN.................................................................................................................... 75 TÀI LIỆU THAM KHẢO.............................................................................................. 76 PHỤ LỤC....................................................................................................................... 78 5 Danh mục các kí hiệu, các chữ viết tắt ABR Associativity-Based Routing AODV Adhoc On-Demand Distance Vector AP Access Point BQ Broadcast Query BS Base Station CBR Constant Bit Rate CDMA Code Division Multiple Access CGSR Clusterhead Gateway Switch Routing CLR Clear Packet CSMA Carrier Sense Multiple Access CSMA/CD Carrier Sense Multiple Access/Collision Detect CSMA/CA Carrier Sense Multiple Access/Collision Avoidance CTS Clear To Send DAG Directed Acyclic Graph DCF Distributed Coordination Function DIFS DCF Interframe Space DRP Dynamic Routing Protocol DSDV Destination-Sequenced Distance-Vector DSR Dynamic Source Routing FTP File Transfer Protocol GPS Global Positioning System IEEE Institude of Electrical and Electronics Engineers IETF Internet Engineering Task Force IRTF Internet Research Task Force LAN Local Area Network LCC Least Cluster Change LQ Localized Query MAC Medium Access Control MAN Metropolitan Area Network MANET Mobile Adhoc Network MRP Multipoint Relay Selector NAM Network Animator NAV Network Allocation Vector NPDU Network Protocol Data Unit NS2 Network Simulator 2 OFDM Orthogonal Frequency Division Multiplexing OLSR Optimized Link State Routing OTCL Object Tool Command Language 6 PAN Personal Area Network PCF Point Coordination Function PIFS PCF Interframe Space QoS Quality of Service RD Route Delete RN Route Notification RREP Route Reply RREQ Route Request RT Routing Table RTS Request To Send SIFS Short Interframe Space SRP Static Routing Protocol SSR Signal Stability Routing SST Signal Stability Table TC Topology Control TCL Tool Command Language TCP Transmission Control Protocol TDMA Time Division Multiple Access TORA Temporally Ordered Routing Algorithm UDP User Datagram Protocol VINT Virtual InterNetwork Testbed WAN Wide Area Network Wi-fi Wireless Fidelity WLAN Wireless Local Area Network WMAN Wireless Metropolitan Area Network WPAN Wireless Personal Area Network WWAN Wireless Wide Area Network WRP Wireless Routing Protocol ZRP Zone Routing Protocol 7 Danh mục các hình vẽ Hình 1. Ví dụ về mạng WLAN ..................................................................................... 15 Hình 2. Hiện tượng đầu cuối ẩn .................................................................................... 17 Hình 3. Hiện tượng đầu cuối lộ..................................................................................... 18 Hình 4. Giải quyết vấn đề đầu cuối ẩn với RTS/CTS................................................... 20 Hình 5. Giải quyết vấn đề đầu cuối lộ với RTS/CTS ................................................... 20 Hình 6. Các khoảng thời gian đợi SIFS, PIFS và DIFS................................................ 21 Hình 7. Chức năng điều khiển tập trung PCF............................................................... 21 Hình 8. Mạng MANET ................................................................................................. 22 Hình 9. Định tuyến hướng bảng và khởi tạo phía nguồn theo yêu cầu ........................ 27 Hình 10. Định tuyến CGSR từ nút 1 đến nút 8 ............................................................. 31 Hình 11. Phát hiện tuyến trong AODV......................................................................... 33 Hình 12. Tạo ra các bản ghi tuyến trong DSR .............................................................. 35 Hình 13. Việc tạo tuyến và đảm bảo tuyến trong TORA ............................................. 36 Hình 14. Lựa chọn tuyến trong ABR............................................................................ 38 Hình 15. Xây dựng lại tuyến trong ABR ...................................................................... 39 Hình 16. Lược đồ nút di động theo chuẩn mở rộng không dây của CMU monarch. ... 50 Hình 17. Lược đồ SRNode theo chuẩn mở rộng không dây của CMU monarch ......... 51 Hình 18. Hình ảnh 50 nút di động, giao thức DSDV, thời gian tạm dừng 0, 1 nguồn phát................................................................................................................................ 61 Hình 19. Số gói tin định tuyến trung bình cần phát với 1, 3 và 5 nguồn phát .............. 63 Hình 20. Số gói tin định tuyến trung bình cần phát với 4 giao thức định tuyến MANET ....................................................................................................................................... 64 Hình 21. Chi phí định tuyến chuẩn hóa theo tải với 1, 3 và 5 nguồn phát ................... 66 Hình 22. Chi phí định tuyến chuẩn hóa theo tải với 4 giao thức định tuyến MANET . 67 Hình 23. Thời gian phát hiện tuyến trung bình với 1, 3 và 5 nguồn phát..................... 69 Hình 24. Thời gian phát hiện tuyến trung bình với 2 giao thức định tuyến MANET .. 70 Hình 25. Số gói tin định tuyến trung bình cần phát trong mô hình Random Walk ...... 72 Hình 26. Chi phí định tuyến chuẩn hóa theo tải trong mô hình Random Walk ........... 72 Hình 27. Thời gian phát hiện tuyến trung bình trong mô hình Random Walk............. 73 8 Danh mục các bảng Bảng 1. So sánh giữa các giao thức định tuyến (Phân tích định tính 1) ....................... 29 Bảng 2. So sánh giữa các giao thức định tuyến (Phân tích định tính 2) ....................... 29 Bảng 3. So sánh đặc tính của các giao thức định tuyến hướng bảng............................ 41 Bảng 4. So sánh đặc tính của các giao thức định tuyến yêu cầu khởi tạo phía nguồn . 43 Bảng 5. Các đặc điểm ngữ cảnh giống nhau của thí nghiệm mô phỏng....................... 58 Bảng 6. Hình trạng mô phỏng với mô hình Random Waypoint ................................... 60 Bảng 7. Hình trạng mô phỏng với mô hình Random Walk .......................................... 71 9 Chương 1. GIỚI THIỆU CHUNG 1.1. Đặt vấn đề [15] Chúng ta biết rằng ngày nay khi mà tầm quan trọng của các máy tính trong cuộc sống của con người tăng lên thì điều đó cũng đòi hỏi các yêu cầu mới cho việc kết nối mạng máy tính. Ngoài các giải pháp cho mạng có dây đã được dùng từ lâu, chúng ta thấy sự gia tăng yêu cầu đối với các giải pháp cho mạng không dây để có thể kết nối tới Internet, đọc và gửi các thông điệp thư điện tử, trao đổi thông tin trong các cuộc họp… Mạng không dây đặc biệt MANET (Mobile Adhoc Networking) bao gồm các thiết bị tự tổ chức thành mạng đạt được sự giải phóng hoàn toàn khỏi cơ sở hạ tầng mạng cố định, có chi phí truyền thông thấp và triển khai dễ dàng. Về mặt thực tiễn, mạng MANET rất hữu ích cho các nhu cầu thiết lập mạng khẩn cấp tại những nơi xảy ra thảm họa như hỏa hoạn, lụt lội, động đất… Với tất cả những lý do trên, mạng MANET là một trong những lĩnh vực nghiên cứu có tính thời sự cao và đầy thách thức của mạng không dây và công nghệ này hứa hẹn sẽ trở nên phổ biến với cuộc sống của con người. Mạng MANET thừa kế những đặc tính truyền thống của mạng không dây và truyền thông di động như tối ưu hóa băng thông, điều khiển năng lượng và tăng chất lượng truyền thông. Ngoài ra, việc truyền qua nhiều chặng, không dựa trên cơ sở hạ tầng mạng cố định và đặc biệt là sự di chuyển tùy ý của mọi nút mạng đặt ra những vấn đề nghiên cứu mới về định tuyến, tiết kiệm năng lượng và an ninh. Nhiều cách tiếp cận và giao thức khác nhau đã được đề nghị để giải quyết các vấn đề phát sinh, một số phương pháp và giao thức đã được IETF và IRTF chuẩn hóa. 1.2. Mục tiêu nghiên cứu Với nhu cầu sử dụng mạng mọi lúc, mọi nơi và không phụ thuộc vào vị trí vật lý, mạng không dây đặc biệt MANET cho phép các máy tính di động thực hiện các kết nối và truyền thông với nhau không cần dựa trên cơ sở hạ tầng mạng có sẵn. Tuy nhiên, bởi cấu trúc của mạng MANET có thể thường xuyên thay đổi do các nút có thể gia nhập hay rời khỏi mạng nên để cho mạng có thể hoạt động thì tất cả các nút cần phải thực hiện chức năng tương đương với một bộ định tuyến. Vấn đề định tuyến tại tầng mạng được quan tâm đến nhiều nhất và cần tập trung giải quyết hai vấn đề cơ bản là tìm ra đường đi từ nút phát đến nút nhận và làm thế nào để duy trì đường đi. Việc định tuyến trong mạng MANET luôn đòi hỏi các chi phí về tài nguyên như dải thông đường truyền, năng lượng tiêu hao trong quá trình tìm đường, dung lượng bộ nhớ cần thiết cho việc lưu trữ bảng định tuyến và thời gian tìm đường. Đề tài luận văn này nhằm mục đích đánh giá và so sánh chi phí tìm đường của một số giao thức định tuyến điển hình trong mạng MANET với một số mức độ di động khác nhau của các nút mạng. Quá trình đánh giá này được thực hiện qua lý thuyết và thông qua mô phỏng với các nội dung bao gồm: 10 ü Nghiên cứu các đặc điểm của mạng MANET ü Xem xét bài toán định tuyến trong mạng MANET và các giải pháp có thể ü Phân loại các giao thức định tuyến mạng MANET ü Xây dựng thí nghiệm mô phỏng và tích hợp một số giao thức định tuyến mạng MANET vào bộ mô phỏng NS2 ü Đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET với các ngữ cảnh khác nhau. Ngữ cảnh của thí nghiệm thay đổi bằng cách: · Thay đổi topo mạng (Số nút mạng, đường truyền cũng như vị trí ban đầu của mỗi nút mạng) · Thay đổi mô hình chuyển động (Mô hình Random Waypoint, Random Walk… ) · Thay đổi mô hình sinh lưu lượng (TCP, CBR) · Thay đổi diện tích và hình dạng vùng mô phỏng · Thay đổi thời gian hoạt động của các nguồn sinh lưu lượng · Thay đổi thời gian mô phỏng 1.3. Tổ chức của luận văn Nội dung của luận văn được tổng hợp thành 4 chương chính. Chương đầu tiên đưa ra mục tiêu nghiên cứu và tổ chức chi tiết của luận văn. Chương 2 của luận văn trình bày tổng quan về mạng không dây WLAN và mạng không dây đặc biệt MANET. Phần nghiên cứu tìm hiểu về việc định tuyến cũng như các yêu cầu với giao thức định tuyến trong mạng MANET được trình bày ở chương 3. Ngoài ra, các kĩ thuật định tuyến mạng MANET và việc phân loại các giao thức định tuyến mạng MANET cũng được mô tả chi tiết tại chương này. Phần giới thiệu về bộ mô phỏng NS2, các thí nghiệm, đánh giá mô phỏng và những kết quả phân tích, so sánh được mô tả ở chương 4 của luận văn. Phần cuối cùng của luận văn là kết luận những công việc mà luận văn đã đạt được và những hướng nghiên cứu tiếp theo trong tương lai. 11 Chương 2. TỔNG QUAN VỀ MẠNG WLAN VÀ MẠNG MANET 2.1. Giới thiệu và phân loại mạng không dây [15] Những năm gần đây, công nghệ thông tin đã có những bước tiến vượt bậc và được áp dụng vào hầu hết các mặt của đời sống xã hội như kinh tế, giáo dục, y tế, quân sự… Xã hội càng phát triển thì nhu cầu tìm hiểu và cập nhật thông tin ngày càng tăng, con người muốn được kết nối với thế giới ở bất kỳ chỗ nào, bất kỳ nơi đâu. Điều đó giải thích tại sao mạng không dây lại được ra đời và phát triển mạnh. Ngày nay, chúng ta có thể bắt gặp mạng không dây ở nhiều nơi như những văn phòng, tòa nhà, các công ty, các tổ chức, tại các trường học, bệnh viện hay thậm chí là các quán cà phê, quán ăn nhanh. Nhờ những cải tiến nhanh chóng trong công nghệ mạng không dây và sự ra đời của các dịch vụ và ứng dụng không dây mới, phạm vi truyền thông không dây đã có những thay đổi đáng kể. Với sự nổi lên của các mạng tế bào thế hệ thứ ba làm tăng tốc độ truyền dữ liệu, cho phép cung cấp các dịch vụ dữ liệu di động đa dạng với tốc độ cao hơn. Trong khi đó thì các chuẩn mới cho sóng vô t