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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Văn Tứ 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 KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Văn Tứ 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 KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS.TS. Nguyễn Đình Việt Cán bộ đồng hướng dẫn: Ths. Đoàn Minh Phương HÀ NỘI - 2010 TÓM TẮT Ngày nay, cùng với sự bùng nổ, phát triển mạnh mẽ của các thiết bị di động cá nhân như: laptop, smartphone, tablet,…, thì nhu cầu kết nối giữa các thiết bị này cũng ngày càng đòi hỏi cao hơn về tốc độ và khả năng di chuyển trong khi kết nối. Mạng di động đặc biệt – MANET (Mobile Ad-hoc Network) là một trong những công nghệ vượt trội đáp ứng nhu cầu kết nối đó nhờ khả năng hoạt động không phụ thuộc vào cơ sở hạ tầng mạng cố định, với chi phí hoạt động thấp, triển khai nhanh và có tính di động cao. Tuy nhiên, hiện nay mạng MANET vẫn chưa được ứng dụng rộng rãi và đang được thúc đẩy nghiên cứu nhằm cải tiến hơn nữa các giao thức định tuyến để mạng đạt được hiệu quả hoạt động tốt hơn. Khóa luận nghiên cứu ả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 mạng MANET. Bằng những kiểm chứng thông qua mô phỏng, khóa luận đưa ra các nhận xét, đánh giá về hiệu suất mạng đối với từng giao thức định tuyến cụ thể khi các nút mạng chuyển động với tốc độ và hướng đi thay đổi. MỤC LỤC TÓM TẮT ............................................................................................................................... DANH MỤC HÌNH VẼ ........................................................................................................... DANH MỤC BẢNG................................................................................................................ BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT ............................................................................... LỜI CẢM ƠN.......................................................................................................................... Chương 1. GIỚI THIỆU ........................................................................................................ 1 1.1. Sự ra đời và phát triển của các mạng không dây .......................................................... 1 1.2. Mục tiêu nghiên cứu của khóa luận.............................................................................. 4 1.3. Công cụ nghiên cứu chính – NS-2 ............................................................................... 5 1.3.1. Giới thiệu về NS-2................................................................................................ 5 1.3.2. Khả năng mô phỏng của NS-2 .............................................................................. 7 1.4. Tổ chức của KLTN...................................................................................................... 8 Chương 2. GIAO THỨC MAC CỦA MẠNG LAN VÀ WLAN ............................................ 9 2.1. Mạng LAN và mạng WLAN ....................................................................................... 9 2.2. Chuẩn 802.3 và giao thức CSMA/CD........................................................................ 10 2.3. Chuẩn 802.11 và giao thức CSMA/CA ...................................................................... 12 Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN .............................................. 15 3.1. Mạng MANET .......................................................................................................... 15 3.1.1. Lịch sử phát triển và các ứng dụng...................................................................... 15 3.1.2. Các đặc điểm chính của mạng MANET .............................................................. 16 3.2. Vấn đề định tuyến trong mạng MANET .................................................................... 17 3.2.1 Các thuật toán định tuyến truyền thống ................................................................ 17 3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANET ......................... 18 3.2.3. Phân loại các kỹ thuật định tuyến........................................................................ 19 3.2.3.1. Link state và Distance Vector....................................................................... 19 3.2.3.2. Định tuyến chủ ứng và phản ứng.................................................................. 20 3.2.3.3. Định tuyến nguồn và định tuyến theo chặng ................................................. 21 3.3. Các giao thức định tuyến chính trong mạng MANET ................................................ 22 3.3.1. DSDV................................................................................................................. 22 3.3.2 OLSR [8]............................................................................................................. 23 3.3.3. AODV [12]......................................................................................................... 25 3.3.4. DSR [7] .............................................................................................................. 27 3.3.5. TORA [11] ......................................................................................................... 28 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 30 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 ........................................................................................................................................ 30 4.1.1. Các tham số hiệu suất cần đánh giá ..................................................................... 30 4.1.2. Cách thức phân tích kết quả mô phỏng của NS-2 ................................................ 30 4.1.2.1. Cấu trúc tệp vết ............................................................................................ 30 4.1.2. Công cụ để phân tích và biểu diễn kết quả mô phỏng .......................................... 33 4.1.2.1. Perl .............................................................................................................. 33 4.1.2.2. GNUPLOT .................................................................................................. 33 4.2. Thiết lập mạng mô phỏng MANET ........................................................................... 35 4.2.1. Thiết lập tô-pô mạng........................................................................................... 35 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 ........... 36 4.2.2.1. Mô hình Random Waypoint ......................................................................... 37 4.2.2.2. Mô hình Random Walk................................................................................ 38 4.2.3 Thiết lập các nguồn sinh lưu lượng đưa vào mạng ............................................... 39 4.2.4. Lựa chọn thời gian mô phỏng ............................................................................. 40 4.3. Thực hiện mô phỏng các giao thức định tuyến ........................................................... 40 4.3.1. Phân tích kết quả bằng công cụ perl .................................................................... 40 4.3.2. Sử dụng gnuplot để vẽ đồ thị .............................................................................. 44 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 ........................................................................................................................ 47 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................................ 49 TÀI LIỆU THAM KHẢO .................................................................................................... 51 PHỤ LỤC ............................................................................................................................ 53 1. 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 .......... 53 2. Mô phỏng mạng MANET............................................................................................. 56 3. Tỷ lệ phân phát gói tin thành công................................................................................ 58 4. Thời gian thiết lập kết nối............................................................................................. 59 DANH MỤC HÌNH VẼ Hình 1: Sự phát triển của mạng không dây và di động............................................................ 1 Hình 2: Cấu trúc của NS-2 ..................................................................................................... 5 Hình 3: Luồng các sự kiện cho file Tcl chạy trong NS-2 ........................................................ 6 Hình 4: Chu trình hoạt động của giao thức CSMA/CD (bên gửi) .......................................... 11 Hình 5: Chu trình hoạt động của giao thức CSMA/CA (bên gửi) .......................................... 13 Hình 6: Hoạt động lắng nghe kênh truyền của giao thức CSMA/CA .................................... 14 Hình 7: Phân loại các giao thức định tuyến trong mạng MANET ......................................... 22 Hình 8: Tô-pô mạng thay đổi ............................................................................................... 23 Hình 9: Quy trình chuyển tiếp gói tin khi sử dụng kíp đa điểm – MPR................................. 24 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. ........... 25 Hình 11: quá trình khám phá tuyến trong AODV ................................................................. 25 Hình 12: Định tuyến nguồn động (DSR) .............................................................................. 27 Hình 13: Diện tích mạng mô phỏng và các nút mạng............................................................ 35 Hình 14: Di chuyển một nút theo mô hình Random Waypoint.............................................. 37 Hình 15: Di chuyển của 8 nút theo mô hình Random Walk .................................................. 38 Hình 16: Đồ thị tỷ lệ phân phát gói thành công – Random Waypoint.................................... 44 Hình 18: Đồ thị tỷ lệ phân phát gói tin thành công – Random Walk ..................................... 45 Hình 19: Đồ thị thời gian thiết lập kết nối trung bình_Random-Waypoint ............................ 46 Hình 20: Đồ thị thời gian thiết lập kết nối trung bình_Random-Walk ................................... 46 DANH MỤC BẢNG Bảng 1: Sự phát triển của chuẩn 802.3 ................................................................................. 10 Bảng 2: Sự phát triển của chuẩn 802.11 ............................................................................... 12 Bảng 3: Cấu trúc tệp vết ....................................................................................................... 31 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 .................... 32 Bảng 5: Cấu hình mạng mô phỏng ....................................................................................... 36 Bảng 6: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Waypoint ................ 41 Bảng 7: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Walk ....................... 42 Bảng 8: Thời gian thiết lập kết nối trung bình-Random_Waypoint ....................................... 43 Bảng 9: Thời gian thiết lập kết nối trung bình-Random_Walk.............................................. 43 Bảng 10: Tỷ lệ phân phát gói tin thành công - Random Waypoint ........................................ 44 Bảng 11: Tỷ lệ phân phát gói tin thành công – Random Walk .............................................. 45 BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT AODV Adhoc On-demand Distance Vector MANET Mobile Adhoc NETwork CSMA/CA Carrier sense multiple access with collision avoidance MPR Multi-Point Relays CSMA/CD Carrier Sense Multiple Access with Collision Detection NS-2 Network Simulator 2 DARPA Defense Advanced Research Projects Agency OLSR Optimized Link State Routing Protocol DSDV Destination-Sequenced Distance Vector PRnet Packet Radio Network DSR Dynamic Source Routing RREP Route Reply IEEE Institute of Electrical and Electronics Engineers RREQ Route Request LAN Local Area Network TORA Temporally-Ordered Routing Algorithm MAC Media Access Control WLAN Wireless LAN LỜI CẢM ƠN Trước tiên, tôi xin gửi lời cảm ơn chân thành tới PGS.TS.Nguyễn Đình Việt, người thầy đã tận tình giúp đỡ tôi trong suốt quá trình làm khóa luận. Tôi cũng xin gửi lời cảm ơn tới Ths. Đoàn Minh Phương, người đã hướng dẫn tôi trong giai đoạn chuẩn bị nhận đề tài. Tôi xin gửi lời biết ơn sâu sắc tới thầy, cô trong trường Đại Học Công Nghệ, Đại Học Quốc Gia Hà Nội. Thầy, cô đã dìu dắt, truyền lại cho chúng tôi không chỉ những kiến thức chuyên ngành mà còn dạy bảo chúng tôi đạo làm người, rèn luyện cho chúng tôi nghị lực, khát vọng vươn lên, phát huy khả năng tư duy sáng tạo trong mọi lĩnh vực. Cuối cùng, tôi xin được cảm ơn gia đình, bạn bè, những người thân yêu nhất của tôi. Mọi người luôn ở bên cạnh tôi, động viên, khuyến khích tôi vươn lên trong cuộc sống. Hà nội, tháng 5 năm 2010 Phạm Văn Tứ 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 Phạm Văn Tứ 1 K51MMT Chương 1. GIỚI THIỆU 1.1 . Sự ra đời và phát triển của các mạng không dây Mạng không dây được đánh dấu mốc hình thành từ những năm 1887 khi Heinrich Rudolf Hertz chứng minh được thuyết điện từ Maxwell thông qua thực nghiệm. Từ đó đến nay các nhà nghiên cứu đã cho ra đời hàng loạt phát minh sáng chế góp phần đưa công nghệ mạng không dây không ngừng cải tiến vượt trội về tốc độ truyền nhận dữ liệu. Những năm gần đây nền công nghiệp không dây và di động tăng trưởng mạnh mẽ cả về mặt công nghệ lẫn sự bùng nổ ngày càng nhiều các thiết bị di động, hứa hẹn một kỷ nguyên truyền thông số nở rộ trên nền các mạng không dây và di động. Sự phát triển này được minh họa trên Hình 1 dưới đây. Hình 1: Sự phát triển của mạng không dây và di động 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 Phạm Văn Tứ 2 K51MMT Các mốc hình thành và phát triển của mạng không dây: Nikola Tesla truyền thành công sóng radio. Heinrich Rudolf Hertz đã tạo ra được sóng điện từ. Ông đã chứng minh được thuyết Maxwell thông qua thực nghiệm. 1887 1893 1895 1915 1931 1982 , 1991 Guglielmo Marconi: Lần đầu tiên trong lịch sử, 3 dấu chấm (tức chữ S trong bảng ký tự Morse) đã được truyền qua không gian với khoảng cách 3km bằng sóng điện từ. Truyền thành công sóng vô tuyến vượt Đại Tây Dương từ Arlington Virginia tới Pháp. Tháp Eiffel đã được sử dụng để đặt anten thu tín hiệu. Sóng FM đã được phát triển bởi Edwin H. Armstrong và được sử dụng rộng rãi để truyền thông tin qua sóng vô tuyến. -1982: Hội nghị CEPT đã thống nhất chọn GSM để phát triển thành tiêu chuẩn cho hệ thống điện thoại di động có thể được sử dụng trên khắp châu Âu. - 1991: Các mạng GSM đầu tiên đã được đưa ra bởi Radiolinja ở Phần Lan với kỹ thuật bảo dưỡng cơ sở hạ tầng chung từ Ericsson. 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 Phạm Văn Tứ 3 K51MMT -1998: Công nghệ Bluetooth đầu tiên được phát triển bởi Ericsson, sau đó được chuẩn hoá bởi Bluetooth Special Interest Group (SIG). - 1999: Chuẩn 802.11b được phát hành cho tốc độ tối đa lên 11Mb/s. -20/5/1999: Chính thức phát hành chuẩn Bluetooth 1.0 Chuẩn IEEE 802.11 (WiFi) đã được tạo ra, với tốc độ tối đa là 2Mb/s. 1997 1998, 1999 2001 2003 2004, 2009 2010 Chuẩn IEEE 802.16 được phát hành. Chuẩn này được biết đến dưới cái tên WIMAX. - Chuẩn 802.11g được phát hành với tốc độ tối đa lên tới 54 Mb/s. - Bluetooth 1.2 được công bố. *2004: - Phiên bản mới của chuẩn 802.16 được bổ sung, hoàn thiện chuẩn WIMAX. - Phát hành chuẩn Bluetooth 2.0 *2009: - Chuẩn 802.11n được phát hành cho phép tốc độ truyên thông tối đa lên tới 150 Mb/s. Liên minh Wi-Fi và Gigabit không dây đã đạt được thỏa thuận cho phép Wi-Fi hoạt động ở dải tần 60 Ghz nhằm cải thiện tốc độ truyền dữ liệu. Các chuẩn Wi-Fi hiện đang hoạt động ở dải tần từ 2.4 GHz đến 5 GHz.  Tốc độ Wi-Fi sẽ tăng hơn 10 lần so với tốc độ hiện tại 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 Phạm Văn Tứ 4 K51MMT 1.2 . Mục tiêu nghiên cứu của khóa luận Với đặc tính có thể hoạt động không phụ thuộc vào cơ sở hạ tầng mạng, triển khai nhanh, linh hoạt ở mọi vị trí địa hình khác nhau, mạng MANET đang là tâm điểm nghiên cứu đầy triển vọng, sẽ là công nghệ đột phá trong tương lai với nhiều ứng dụng hữu ích vào cuộc sống, thí dụ kết nối mạng truyền thông cho các các vùng mới xảy ra thiên tai hoặc ứng dụng cho lĩnh vực quân sự. Khóa luận tập trung đi sâu nghiên cứu về mạng MANET, kết hợp phân tích trên lý thuyết cùng thực nghiệm mô phỏng để tìm ra và đánh giá ảnh hưởng sự di động của các nút mạng ở các mức độ khác nhau đến hiệu suất của một số giao thức định tuyến. Nội dung cụ thể gồm:  Tìm hiểu sâu về mạng MANET, trong đó chủ yếu xem xét tới các giao thức định tuyến.  Tìm hiểu sâu về các mô hình chuyển động của nút mạng trong MANET.  Xây dựng môi trường mô phỏng, đưa các giao thức định tuyến trong mạng MANET vào mô phỏng thông qua NS-2.  Đánh giá ảnh hưởng sự chuyển động của các nút mạng đến hiệu suất của các giao thức định tuyến DSDV, AODV và DSR bằng bộ mô phỏng mạng NS-2. Từ đó đưa ra các nhận xét so sánh giữa ba giao thức. 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 Phạm Văn Tứ 5 K51MMT 1.3 . Công cụ nghiên cứu chính – NS-2 1.3.1. Giới thiệu về NS-2 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. Hình 2: Cấu trúc của NS-2 Cấu trúc của NS-2 bao gồm các thành phần được chỉ ra trên Hình 2, chức năng của chúng được mô tả như sau:  OTcl Script Kịch bản OTcl  Simulation Program Chương trình Mô phòng  OTcl Bộ biên dịch Tcl mở rộng hướng đối tượng  NS Simulation Library Thư viện Mô phỏng NS  Event Scheduler Objects Các đối tượng Bộ lập lịch Sự kiện  Network Component Objects Các đối tượng Thành phần Mạng  Network Setup Helping Modules Các mô đun Trợ giúp Thiết lập Mạng  Plumbling Modules Các mô đun Plumbling  Simulation Results Các kết quả Mô phỏng  Analysis Phân tích  NAM Network Animator Minh họa Mạng NAM 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 Phạm Văn Tứ 6 K51MMT Trong hình 2 trên, NS là Bộ biên dịch Tcl mở rộng hướng đối tượng; bao gồm các đối tượng: Bộ lập lịch sự kiện, các đối tượng thành phần mạng và các mô đun trợ giúp thiết lập mạng. Để 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 Bộ lập lịch Sự kiện trong NS-2 thực hiện những việc sau: Tổ chức Bộ định thời mô phỏng -- Huỷ các sự kiện trong hàng đợi sự kiện -- Triệu gọi các Thành phần mạng trong mô phỏng. Tùy vào mục đích của người dùng đối với kịch bản mô phỏng OTcl mà kết quả mô phỏng có thể được lưu trữ vào tệp vết (trace file) với khuôn dạng (format) được những người phát triển NS định nghĩa trước hoặc theo khuôn dạng do người sử dụng NS quyết định khi viết kịch bản mô phỏng. Nội dung tệp vết sẽ được tải vào trong các ứng dụng khác để thực hiện phân tích. NS đã định nghĩa 2 loại tệp vết:  Nam trace file (file.nam): Chứa các thông tin về tô-pô mạng như: các nút mạng, đường truyền, vết các gói tin; dùng để minh họa trực quan mạng đã thiết lập.  Trace file (file.tr): Tệp ghi lại vết của các sự kiện mô phỏng, tệp file dạng text, có cấu trúc, dùng cho các công cụ lần vết và giám sát mô phỏng như: Gnuplot, XGRAPH hay TRACEGRAPH. Hình 3: Luồng các sự kiện cho file Tcl chạy trong NS-2 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 Phạm Văn Tứ 7 K51MMT 1.3.2. Khả năng mô phỏng của NS-2 NS-2 hỗ trợ mô phỏng tốt cho cả mạng có dây và mạng không dây. Bao gồm các ưu điểm nổi bật sau:  Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại.  Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng.  Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi được trong thực tế.  Khả năng mô phỏng nhiều loại mạng khác nhau. Trong đó NS-2 có khả năng mô phỏng:  Các mô hình mạng: LAN, WLAN, di động, vệ tinh,...  Các giao thức mạng như: TCP, UDP...  Các dịch vụ nguồn lưu lượng như: FTP, CBR, VBR, Telnet, http...  Các kỹ thuật quản lý hàng đợi: Vào trước Ra trước (Drop Tail), Loại bỏ sớm ngẫu nhiễn - RED (Random Early Drop) và Xếp hàng dựa trên sự phân lớp – CBQ (Class-Based Queueing)...  Các thuật toán định tuyến như: Dijkstra, Distance Vector, Link State…  Các Chuẩn IEEE 802.11, IEEE 802.3,…  NS-2 cũng thực thi multicasting và vài giao thức lớp Điều khiển truy cập đường truyền (MAC) đối với mô phỏng LAN. 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 Phạm Văn Tứ 8 K51MMT 1.4 . Tổ chức của KLTN Nội dung khóa luận bao gồm bốn chương như sau: Chương 1: Giới thiệu về sự ra đời và phát triển của các mạng không dây, trình bày tổng quát về bộ mô phỏng mạng NS-2 và nêu lên được mục tiêu nghiên cứu xuyên suốt trong đề tài khóa luận tốt nghiệp này. Chương 2: Trình bày các giao thức MAC của mạng LAN và WLAN như giao thức CSMA/CD, CSMA/CA cùng hai chuẩn tương ứng là IEEE 802.3 và IEEE 802.11. Chương 3: Nêu lên lịch sử hình thành, các đặc điểm chính của mạng MANET, đồng thời mô tả chi tiết về các giao thức định tuyến như DSDV, AODV, DSR, OLSR, TORA và phân loại các kỹ thuật định tuyến khác nhau. Chương 4: Từ các kết quả thực nghiệm mô phỏng chúng tôi đánh giá ả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 mạng MANET. 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 Phạm Văn Tứ 9 K51MMT Chương 2. GIAO THỨC MAC CỦA MẠNG LAN VÀ WLAN 2.1. Mạng LAN và mạng WLAN Trong nhưng năm gần đây mạng WLAN đã trở lên phổ biến rộng khắp ở mọi nơi: lớp học, sân trường, thư viện, văn phòng, quán cà phê, khách sạn, tới hộ gia đình. Mạng WLAN đã đạt được những bước tiến khá dài và vững chắc, dần trở thành một đối trọng của công nghệ mạng LAN phổ biến từ trước tới nay. Các lợi thế lớn mà WLAN đem lại cho người dùng gồm: 1. Tính di động: Với khả năng hỗ trợ của mạng không dây, người dùng không bị ràng buộc vào các dây nối, tức là trong khi đang kết nối người sử dụng vẫn có thể di chuyển từ vị trí này đến vị trí khác trong khu vực phủ sóng mà không bị gò bó tại một vị trí cố định như trong mạng LAN truyền thống. Nhờ đó người dùng có thể mang theo thiết bị của mình đến bất cứ đâu có sóng không dây là có thể truy cập vào mạng. 2. Tính mềm dẻo: Triển khai mạng không dây rất thuận tiện và dễ dàng vì môi trường truyền luôn có sẵn mọi lúc, mọi nơi mà không cần phải lên kế hoach trước, không cần kéo dây cáp mạng hay bất kỳ sự vướng víu nào. Người dùng dễ dàng thiết lập kết nối một cách nhanh chóng phục vụ cho công việc của mình. 3. Dễ dàng triển khai lắp đặt: Đối với nhiều khu vực việc triển khai mạng có dây khá là khó khăn, tốn nhiều công sức do địa hình không thuận lợi hoặc không được phép lắp đặt vì làm mất mĩ quan. Trái lại với mạng không dây ta chỉ cần thiết lập, lắp đặt các thiết bị trung tâm như Access point, Switch, Router, sau đó không cần phải đi thêm các hệ thống dây cáp đến từng máy cố định như trong mạng thông thường. 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 Phạm Văn Tứ 10 K51MMT 2.2. Chuẩn 802.3 và giao thức CSMA/CD 2.2.1. Chuẩn 802.3: IEEE 802.3 là tập hợp các tiêu chuẩn do tổ chức IEEE định nghĩa về tầng vật lý (Physical layer) và lớp con điều khiển truy cập môi trường truyền (MAC sublayer) của lớp liên kết dữ liệu (Data link layer) trong mạng Ethernet. Theo chuẩn này, các kết nối vật lý được thực hiện giữa các nút và (hoặc) các thiết bị cơ sở hạ tầng như: hub, switch, router… bằng các loại cáp đồng hoặc cáp quang. Chuẩn 802.3 đồng thời cũng hỗ trợ các kiến trúc mạng theo chuẩn 802.1. Kích thước gói tin tối đa theo chuẩn là 1518 byte, mặc dù vậy để hỗ trợ mạng LAN ảo và độ ưu tiên dữ liệu trong chuẩn 802.3ac, nó được mở rộng tới 1.522 byte. Nếu giao thức lớp trên đưa ra một khung dữ liệu (PDU) nhỏ hơn 64 byte, thì chuẩn 802.3 sẽ đệm thêm các trường dữ liệu để đạt được tối thiểu 64 byte. Do đó kích thước khung tối thiểu luôn luôn là 64 byte. Với sự phát triển mạnh mẽ của công nghệ, tốc độ kết nối trong Ethernet không ngừng được nâng lên. Dưới đây là một số mốc phát triển chính của chuẩn 802.3: Bảng 1: Sự phát triển của chuẩn 802.3 Chuẩn Năm Sự kiện 802.3u 1995 Fast Ethernet ra đời với tốc độ 100 Mbit/s: 100BASE- TX, 100BASE-T4, 100BASE-FX 802.3z 1998 1000BASE-X Gbit/s Ethernet qua cáp quang với tốc độ 1 Gbit/s 802.3ab 1999 1000BASE-T Gbit/s Ethernet qua cáp UTP với tốc độ 1 Gbit/s 802.3ae 2003 10 Gbit/s Ethernet over fiber 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 Phạm Văn Tứ 11 K51MMT 2.2.2. Giao thức CSMA/CD Hình 4: Chu trình hoạt động của giao thức CSMA/CD (bên gửi) CSMA/CD (Carrier Sense Multiple Access with Collision Detection) – là giao thức Đa truy cập cảm nhận sóng mang có phát hiện xung đột. Mạng LAN hoạt động dựa trên nguyên tắc này. Khi máy tính muốn truyền dữ liệu, trước tiên nó lắng nghe xem đường truyền có bận hay không (bằng cách cảm nhận tín hiệu sóng mang). Nếu không có, nó sẽ thực hiện truyền gói tin. Sau khi truyền gói tin, nó vẫn tiếp tục lắng nghe để xem có máy nào định truyền tin hay không. Nếu không có xung đột, nó tiếp tục truyền gói tin cho đến khi hoàn thành. Nếu phát hiện xung đột, nó sẽ gửi broadcast ra toàn mạng tín hiệu nghẽn (jam signal) để các máy khác dễ dàng nhận ra xung đột. Sau đó nó sẽ đợi một thời gian theo thuật toán Backoff rồi thử gửi lại gói tin. 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 Phạm Văn Tứ 12 K51MMT 2.3. Chuẩn 802.11 và giao thức CSMA/CA 2.3.1 Chuẩn 802.11 IEEE 802.11 là một tập các chuẩn do tổ chức IEEE quy định về truyền thông máy tính trong mạng LAN không dây ở các dải tần số: 2.4 GHz, 3.6 GHz và 5 GHz. Chuẩn 802.11 bao gồm các kỹ thuật điều biến tín hiệu “truyền qua không khí” (over- the-air) sử dụng sóng vô tuyến để truyền nhận tín hiệu giữa các thiết bị không dây và điểm truy cập (access point) hoặc giữa các thiết bị không dây với nhau (mạng ad-hoc). Chuẩn mạng không dây đầu tiên được ra đời vào tháng sáu năm 1997 (802.11- 1997) nhưng phải mãi đến tháng 9 năm 1999 chuẩn 802.11b ra đời mới được chấp nhận rộng rãi. Tiếp theo đó là sự ra đời của chuẩn 802.11g và 802.11n đánh dấu sự cải tiến vượt trội về tốc độ truyền tải mạng không dây. Trong đó chuẩn 802.11n được ứng dụng kỹ thuật điều biến đa luồng mới cho phép truyền dữ liệu ở tốc độ cao nhất lên đến 150Mbps mỗi luồng. Chúng ta cùng nhìn lại sự phát triển, cải tiến của mạng không dây chuẩn 802.11 theo bảng 2. Bảng 2: Sự phát triển của chuẩn 802.11 802.11 Protocol Năm Tần số (GHz) Băng thông (MHz) Tốc độ truyền dữ liệu trên mỗi luồng (Mb/s) Số luồng MIMO - 1997 2.4 20 1, 2 1 a 9/1999 5/3.7 20 6, 9, 12, 18, 24, 36, 48, 54 1 b 9/1999 2.4 20 1, 2, 5.5, 11 1 g 6/2003 2.4 20 1, 2, 6, 9, 12, 18, 24, 36, 48, 54 1 20 7.2, 14.4, 21.7, 28.9, 43.3, 57.8, 65, 72.2 n 10/2009 2.4/5 40 15, 30, 45, 60, 90, 120, 135, 150 4 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 Phạm Văn Tứ 13 K51MMT 2.3.1 Giao thức CSMA/CA Hình 5: Chu trình hoạt động của giao thức CSMA/CA (bên gửi) CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) – Đa truy cập cảm nhận sóng mang có tránh xung đột. CSMA/CD là phương thức truy cập của lớp hai (Data link). Nguyên tắc hoạt động của phương thức này dựa trên việc cảm nhận sóng mang, tránh xung đột và cơ chế nghe trước khi nói “Listen before talk”. Một nút trước khi truyền phải lắng nghe kênh truyền trước để xem có nút nào khác đang truyền sóng trong vùng sóng cần truyền hay không. 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 Phạm Văn Tứ 14 K51MMT Hình 6: Hoạt động lắng nghe kênh truyền của giao thức CSMA/CA  Nếu kênh truyền rỗi: Nút sẽ đợi một khoảng thời gian tối thiểu DIFS sau đó bắt đầu quá trình truyền.  Nếu kênh truyền bận:  Nút muốn truyền phải đợi một khoảng thời gian DIFS  Và chờ thêm một khoảng thời gian Backoff ngẫu nhiên trong cửa sổ tranh chấp. Cơ chế này giúp CSMA/CA tránh được xung đột.  Sau mỗi khoảng thời gian DIFS, nếu môi trường truyền rỗi, thời gian Backoff giảm đi 1. Trái lại nó được giữ nguyên cho khoảng thời gian DIFS tiếp theo. Khi thời gian Backoff giảm đến không, nút bắt đầu truy cập môi trường truyền. Tuy nhiên, nếu trước đó một nút khác đã truy cập môi trường truyền trước khi thời gian Backoff của nút này giảm đến không thì nó sẽ giữ lại giá trị thời gian Backoff hiện tại để sử dụng cho lần truy cập tiếp theo. 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 Phạm Văn Tứ 15 K51MMT Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN 3.1. Mạng MANET 3.1.1. Lịch sử phát triển và các ứng dụng Lịch sử: Mạng di động đặc biệt (Mobile Adhoc Netwowk) là mạng tự cấu hình của các nút di động kết nối với nhau thông qua các liên kết không dây tạo nên mạng độc lập không phụ thuộc vào cơ sở hạ tầng mạng. Các thiết bị trong mạng có thể di chuyển một cách tự do theo mọi hướng, do đó liên kết của nó với các thiết bị khác cũng thay đổi một cách thường xuyên. Nguyên lý làm việc của mạng Adhoc bắt nguồn từ năm 1968 khi các mạng ALOHA được thực hiện. Tuy các trạm làm việc là cố định nhưng giao thức ALOHA đã thực hiện việc quản lý truy cập kênh truyền dưới dạng phân tán, đây là cơ sở lý thuyết để phát triển kỹ thuật truy cập kênh phân tán vào mạng Adhoc. Năm 1973 tổ chức DARPA đã bắt đầu làm việc trên mạng vô tuyến gói tin PRnet. Đây là mạng vô tuyến gói tin đa chặng đầu tiên. Trong đó các nút hợp tác với nhau để gửi dữ liệu tới một nút nằm ở xa khu vực kết nối thông qua một nút khác. Nó cung cấp cơ chế cho việc quản lý hoạt động trên cơ sở tập trung và phân tán. Một lợi điểm của làm việc đa chặng so với đơn chặng là triển khai đa chặng tạo thuận lợi cho việc dùng lại tài nguyên kênh truyền về cả không gian, thời gian và giảm năng lượng phát cần thiết. Sau đó có nhiều mạng vô tuyên gói tin phát triển nhưng các hệ thống không dây này vẫn chưa bao giờ tới tay người dùng cho đến khi chuẩn 802.11 ra đời. IEEE đã đổi tên mạng vô tuyến gói tin thành mạng Adhoc. Ứng dụng: Quân sự: Hoạt động phi tập trung của mạng Adhoc và không phụ thuộc vào cơ sở hạ tầng mạng là một yếu tố thiết yếu đối với lĩnh vực quân sự, nhất là trong các trường hợp chiến đấu khốc liệt, các cơ sở hạ tầng mạng bị phá hủy. Lúc này mạng Adhoc là lựa chọn số một để các thiết bị truyền thông liên lạc với nhau một cách nhanh chóng. 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 Phạm Văn Tứ 16 K51MMT Trường học: Chúng ta cũng có thể thiết lập các mạng Adhoc trong trường học, lớp học, thư viện, sân trường,… để kết nối các thiết bị di động (laptop, smartphone) lại với nhau, giúp sinh viên, thầy cô giáo có thể trao đổi bài một cách nhanh chóng thông qua mạng adhoc vừa tạo. Gia đình: Tại nhà bạn có thể tạo nhanh mạng Adhoc để kết nối các thiết bị di động của bạn với nhau, nhờ đó ta có thể di chuyển tự do mà vẫn đảm bảo kết nối truyền tải dữ liệu. Kết nối các thiết bị điện tử với nhau: Trong những năm tới khi mà các thiết bị điện tử đều được gắn các giao tiếp không dây, giúp chúng có thể trao đổi giao tiếp với nhau thì mạng Adhoc sẽ rất phù hợp để tạo nên một hệ thống thông mình có khả năng liên kết với nhau. 3.1.2. Các đặc điểm chính của mạng MANET Mỗi nút di động khác nhau trong mạng MANET đều có những đặc điểm về nguồn năng lượng, bộ phận thu phát sóng khác nhau. Chúng có thể di chuyển về mọi hướng theo các tốc độ khác nhau, do đó ta có thể nhận thấy rõ một số đặc điểm chính của mạng MANET như sau:  Cấu hình mạng động: Cấu hình mạng luôn biến đổi theo các mức độ di chuyển của nút mạng.  Khoảng cách sóng ngắn: Khoảng cách sóng của các thiết bị di động là rất hạn chế.  Năng lượng hạn chế: Tất cả các thiết bị di động đều sử dụng pin nên khi tham gia vào mạng MANET chúng bị hạn chế về năng lượng, khả năng xử lý của CPU, kích thước bộ nhớ.  Băng thông hạn chế: Các liên kết không dây có băng thông thấp hơn so với đường truyền cáp và chúng còn chịu ảnh hưởng của sự nhiễu, suy giảm tín hiệu, các điều kiện giao thoa vì thế mà thường nhỏ hơn tốc độ truyền lớn nhất của sóng vô tuyến.  Bảo mật yếu: Đặc điểm của mạng MANET là truyền sóng qua môi trường không khí, điều này khiến cho cơ chế bảo mật kém hơn so vơi môi trường truyền cáp vì nó tiềm ẩn nhiều nguy cơ bị tấn công, nghe lén đường truyền, giả mạo, DoS,… 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 Phạm Văn Tứ 17 K51MMT 3.2. Vấn đề định tuyến trong mạng MANET 3.2.1 Các thuật toán định tuyến truyền thống Các giao thức định tuyến truyền thống thường sử dụng hai giải thuật:  Distance Vector: RIP , IGRP,... Nguyên tắc hoạt động: mỗi router sẻ gửi bảng định tuyến của mình cho tất cả các router được nối trực tiếp với nó . Các router đó so sánh với bảng bảng định tuyến mà mình hiện có và kiểm tra lại các tuyến đường của mình với các tuyến đường mới nhận được, tuyến đường nào tối ưu hơn sẽ được đưa vào bảng định tuyến. Các gói tin cập nhật sẽ được gửi theo định kỳ (30 giây với RIP ,90 giây đối với IGRP) [9]. Ưu điểm: Dễ cấu hình, router không phải xử lý nhiều nên không tốn nhiều dung lượng bộ nhớ và CPU có tốc độ xử lý nhanh hơn. Nhược điểm: - Hệ thống metric quá đơn giản (như Rip chỉ là hop-count ) dẫn đến việc các tuyến đường được chọn vào bảng định tuyến chưa phải tuyến đường tốt nhất. - Vì các gói tin cập nhật được gửi theo định kỳ nên một lượng băng thông đáng kể sẽ bị chiếm. - Do Router hội tụ chậm, dẫn đến việc sai lệch trong bảng địn tuyến gây nên hiện tượng vòng lặp (loop).  Link state: OSPF, IS-IS Nguyên tắc hoạt động: Các router không gửi bảng định tuyến của mình, mà chỉ gửi tình trạng của các đường liên kết trong cơ sở dữ liệu trạng thái liên kết (linkstate- database) của mình đi cho các router khác, các router sẽ áp dụng giải thuật SPF (shortest path first ), để tự xây dựng bảng định tuyến riêng cho mình. Khi mạng đã hội tụ, các giao thức Link state sẽ không gửi cập nhật định kỳ mà chỉ gửi khi nào có sự thay đổi trong mạng (1 đường bị down , cần sử dụng đường dự phòng). Ưu điểm: Có thể thích nghi được với đa số hệ thống, cho phép người thiết kế có thể thiết kế mạng linh hoạt, phản ứng nhanh với tình huống xảy ra. Do không gởi cập nhật định kỳ như Distance Vector, nên Link State bảo đảm được băng thông cho các đường mạng. 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 Phạm Văn Tứ 18 K51MMT Nhược điểm: - Do router phải xử lý nhiều, nên chiếm nhiều bộ nhớ, tốc độ CPU chậm hơn nên tăng độ trễ Việc sử dụng các giao thức định tuyến truyền thống trong mạng MANET sẽ dẫn đến rất nhiều vấn đề trở ngại cần giải quyết:  Tiêu tốn năng lượng nguồn nuôi cho các cập nhập định kỳ như trong giao thức định tuyến Distance Vector.  Tiêu tốn băng thông mạng cho các cập nhập định kỳ.  Làm quá tải bộ vi xử lý của thiết bị: khi các thông tin cập nhật, số nút mạng tăng lên.  Tạo ra nhiều đường đi dư thừa 3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANET Các giao thức định tuyến trong mạng MANET cần đảm bảo:  Thích ứng nhanh khi tô-pô mạng thay đổi: khi các nút mạng di chuyển nhanh, yêu cầu kết nối tăng lên thì các giao thức hoạt động theo cơ chế tiếp cận tập trung sẽ giảm hiệu quả rõ rệt do phải tốn nhiều thời gian để thu thập thông tin về trạng thái hiện tại và phát tán lại nó. Trong khi đó cấu hình mạng có thể đã thay đổi khác đi rồi.  Đảm bảo hiệu quả trong môi trường truyền khi các nút đứng yên. Lúc này tô-pô mạng là cố định không thay đổi nên các giao thức định tuyến chỉ cần gửi các cập nhật khi có yêu cầu hoặc mạng thay đổi như việc một nút nào đó tắt kết nối.  Không có lặp định tuyến: Cần ngăn chặn hiện tượng này, bởi vì khi đó các gói tin bị định tuyến sai, dẫn đến việc bị truyền quay vòng liên tục trong một số kết nối mạng, khiến cho băng thông mạng và các tài nguyên khác như năng lượng nguồn nuôi bị tiêu tốn vô ích.  Bảo mật: Việc định tuyến trong mạng MANET có nguy cơ bị tấn công dễ dàng bằng các phương pháp như xâm nhập đường truyền, phát lại, thay đổi các gói tin tiêu đề, điều hướng các thông điệp định tuyến. Do đó khi thiết kế các giao 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 Phạm Văn Tứ 19 K51MMT thức định tuyến cần phải có phương pháp để phát hiện được và ngăn chặn các loại tấn công. 3.2.3. Phân loại các kỹ thuật định tuyến 3.2.3.1. Link state và Distance Vector Thuật toán định tuyến vector khoảng cách (distance-vector routing protocols) Thuật toán này dùng thuật toán Bellman-Ford, trong đó chỉ định một con số, gọi là chi phí (hay trọng số), cho mỗi một liên kết giữa các nút trong mạng. Các nút sẽ gửi thông tin về đường đi từ điểm A đến điểm B qua các đường truyền (kết nối) mang lại tổng chi phí thấp nhất (là tổng các chi phí của các kết nối giữa các nút được dùng). Thuật toán hoạt động với những hành động rất đơn giản. Khi một nút khởi động lần đầu, nó chỉ biết các nút kề trực tiếp với nó, và chi phí trực tiếp để đi đến đó (thông tin này, danh sách của các đích, tổng chi phí đến từng đích và bước kế tiếp để gửi dữ liệu đến đó tạo nên bảng định tuyến, hay bảng khoảng cách). Mỗi nút, trong một tiến trình, gửi đến từng “hàng xóm” tổng chi phí của nó để đi đến các đích mà nó biết. Các nút “hàng xóm” phân tích thông tin này, và so sánh với những thông tin mà chúng đang “biết”; bất kỳ điều gì cải thiện được những thông tin chúng đang có sẽ được đưa vào các bảng định tuyến của những “hàng xóm” này. Đến khi kết thúc, tất cả nút trên mạng sẽ tìm ra bước truyền kế tiếp tối ưu đến tất cả mọi đích, và tổng chi phí tốt nhất. Khi một trong các nút gặp vấn đề, những nút khác có sử dụng nút hỏng này trong lộ trình của mình sẽ loại bỏ những lộ trình đó, và tạo nên thông tin mới của bảng định tuyến. Sau đó chúng chuyển thông tin này đến tất cả nút gần kề và lặp lại quá trình trên. Cuối cùng, tất cả nút trên mạng nhận được thông tin cập nhật, và sau đó sẽ tìm đường đi mới đến tất cả các đích mà chúng còn tới được. Thuật toán định tuyến trạng thái kết nối (Link-state routing protocols) Khi áp dụng các thuật toán trạng thái kết nối, mỗi nút sử dụng dữ liệu cơ sở của nó như là một bản đồ của mạng với dạng một đồ thị. Để làm điều này, mỗi nút phát đi tới toàn mạng những thông tin về các nút khác mà nó có thể kết nối được, và từng nút góp thông tin một cách độc lập vào bản đồ. Sử dụng bản đồ này, mỗi nút sau đó sẽ xác định được tuyến đường tốt nhất từ nó đến mọi nút khác. Thuật toán đã làm theo cách này là Dijkstra, bằng cách xây dựng cấu trúc dữ liệu khác, dạng cây, trong đó nút hiện tại là gốc, và chứa mọi nút khác trong mạng. Bắt đầu 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 Phạm Văn Tứ 20 K51MMT với một cây ban đầu chỉ chứa chính nó. Sau đó lần lượt từ tập các nút chưa được thêm vào cây, nó sẽ thêm nút có chi phí thấp nhất để đến một nút đã có trên cây. Tiếp tục quá trình đến khi mọi nút đều được thêm vào cây. Cây này sau đó phục vụ để xây dựng bảng định tuyến, đưa ra bước truyền kế tiếp tốt ưu, … để từ một nút đến bất kỳ nút khác trên mạng. So sánh các thuật toán định tuyến Các giao thức định tuyến theo thuật toán vector khoảng cách đơn giản và hiệu quả hơn trong các mạng nhỏ, đòi hỏi ít (nếu có) sự giám sát. Tuy nhiên nhược điểm của nó là khả năng hội tụ chậm khi mạng lớn và thay đổi, điều này dẫn đến sự phát triển của các thuật toán trạng thái kết nối tuy phức tạp hơn nhưng tốt hơn để dùng trong các mạng lớn. Ưu điểm chính của định tuyến bằng trạng thái kết nối là phản ứng nhanh nhạy hơn, và trong một khoảng thời gian có hạn, đối với sự thay đổi kết nối. Ngoài ra, những gói được gửi qua mạng trong định tuyến bằng trạng thái kết nối thì nhỏ hơn những gói dùng trong định tuyến bằng vector. Định tuyến bằng vector đòi hỏi bảng định tuyến đầy đủ phải được truyền đi, trong khi định tuyến bằng trạng thái kết nối thì chỉ có thông tin về “hàng xóm” của nút được truyền đi. Vì vậy, các gói này dùng tài nguyên mạng ở mức không đáng kể. Khuyết điểm chính của định tuyến bằng trạng thái kết nối là nó đòi hỏi nhiều sự lưu trữ và tính toán để chạy hơn định tuyến bằng vector. 3.2.3.2. Định tuyến chủ ứng và phản ứng Các giao thức định tuyến trong mạng MANET được người ta phân chia thành các loại: định tuyến chủ ứng (proactive), định tuyến phản ứng (reactive) và định tuyến lai ghép giữa hai loại trên. Các giao thức định tuyến chủ ứng sử dụng phương pháp phát tràn (Floading) để quảng bá thông tin tới các thiết bị. Phương pháp này cho phép thời gian thiết lập đường nhanh dựa trên các tham số gửi tới thiết bị sẵn sàng cho kết nối. Tuy nhiên, phương pháp này cũng làm lưu lượng các gói tin tìm đường tăng lên rất lớn, đây chính là nhược điểm của phương pháp này. Giao thức định tuyến trạng thái liên kết tối ưu OLSR (Optimized Link State Routing) và giao thức định tuyến vector khoảng cách tuần tự đích DSDV (Dynamic Destination-Sequenced Distance-Vector Routing) là hai ví dụ của giao thức định tuyến chủ ứng. 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 Phạm Văn Tứ 21 K51MMT Các giao thức định tuyến phản ứng thiết lập tuyến dựa theo từng yêu cầu kết nối. Phương pháp này hạn chế được chi phí tìm đường, nhưng nhược điểm cơ bản là gây trễ lớn cho các khung truyền dẫn đầu tiên cũng như thời gian chọn đường dẫn chậm. Hai giao thức phản ứng điển hình là giao thức định tuyến vector khoảng cách theo yêu cầu AODV (On-demand Distance Vector Routing) và giao thức định tuyến định tuyến nguồn động DSR (Dynamic Source Routing). Một khi xảy ra lỗi tại nút, các giao thức định tuyến thường khôi phục đường dẫn bằng phương pháp thiết lập tuyến mới. Hầu hết các tiếp cận hiện nay đều sử dụng thông tin phản hồi tới thiết bị nguồn nhằm khởi tạo tuyến mới, vì vậy lưu lượng bản tin trao đổi là rất lớn và tăng lên rất nhanh khi kích thước mạng lớn, nhất là đối với các giao thức định tuyến chủ ứng. Khi kích thước mạng tăng cũng đồng nghĩa với sự suy giảm hiệu năng mạng do hiện tượng trễ của thủ tục định tuyến và truyền khung đầu tiên tăng lên rất lớn nếu sử dụng giao thức định tuyến phản ứng. 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. 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 Phạm Văn Tứ 22 K51MMT 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] 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 Phạm Văn Tứ 23 K51MMT 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 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 Phạm Văn Tứ 24 K51MMT 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 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 Phạm Văn Tứ 25 K51MMT 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. 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 Phạm Văn Tứ 26 K51MMT 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 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 Phạm Văn Tứ 27 K51MMT 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á 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 Phạm Văn Tứ 28 K51MMT 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 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 Phạm Văn Tứ 29 K51MMT 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. 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 Phạm Văn Tứ 30 K51MMT 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 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 Phạm Văn Tứ 31 K51MMT 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 %.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 Wireless Event s: Send r: Receive d: Drop f: Forward 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: 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 Phạm Văn Tứ 32 K51MMT 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 ------- [%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 IP Trace int Next Hop Address, If Any Địa chỉ của nút kế tiếp gói tin sẽ chuyể tiếp tới. [%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 TCP Trace int Optimal Number Of Forwards Số chuyển tiếp tối ưu [%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 CBR Trace 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. 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 Phạm Văn Tứ 33 K51MMT 4.1.2. Công cụ để phân tích và biểu diễn kết quả mô phỏng 4.1.2.1 . 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 4.1.2.2. 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 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 Phạm Văn Tứ 34 K51MMT 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 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 Phạm Văn Tứ 35 K51MMT 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 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 Phạm Văn Tứ 36 K51MMT 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 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 Phạm Văn Tứ 37 K51MMT 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. 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 Phạm Văn Tứ 38 K51MMT 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. 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 Phạm Văn Tứ 39 K51MMT 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. 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 Phạm Văn Tứ 40 K51MMT 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. 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 Phạm Văn Tứ 41 K51MMT 4.3.1.1 . 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. a. 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 Gói tin truyền thành công 2768 50802 49802 Tổng số gói tin gửi đi 2813 50925 49943 0m/s Tỷ lệ % 98,40 99,75 99,72 Gói tin truyền thành công 63930 62871 57789 Tổng số gói tin gửi đi 64601 64063 58170 5m/s Tỷ lệ % 98,96 98,13 99,34 Gói tin truyền thành công 97453 60909 105725 Tổng số gói tin gửi đi 97979 61554 106059 10m/s Tỷ lệ % 99,46 98,95 99,69 Gói tin truyền thành công 24978 46136 41019 Tổng số gói tin gửi đi 25222 46937 41356 15m/s Tỷ lệ % 99,03 98,29 99,19 Gói tin truyền thành công 37344 46212 45568 Tổng số gói tin gửi đi 37839 47180 45897 20m/s Tỷ lệ % 98,69 97,95 99,28 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 Phạm Văn Tứ 42 K51MMT b. 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 Gói tin truyền thành công 69919 72729 69972 Tổng số gói tin gửi đi 70033 72859 70101 0m/s Tỷ lệ % 99,84 99,82 99,82 Gói tin truyền thành công 51120 48731 44450 Tổng số gói tin gửi đi 51547 50096 44685 5m/s Tỷ lệ % 99,17 97,28 99,47 Gói tin truyền thành công 55272 61102 56998 Tổng số gói tin gửi đi 55652 62065 57391 10m/s Tỷ lệ % 99,32 98,45 99,32 Gói tin truyền thành công 34680 44709 42969 Tổng số gói tin gửi đi 35149 45723 43396 15m/s Tỷ lệ % 98,67 97,78 99,02 Gói tin truyền thành công 31045 49969 50373 Tổng số gói tin gửi đi 31498 51238 50845 20m/s Tỷ lệ % 98,56 97,52 99,07 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 Phạm Văn Tứ 43 K51MMT 4.3.1.2. Thời gian thiết lập kết nối a. 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 b. 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 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 Phạm Văn Tứ 44 K51MMT 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 a. 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 97 97,5 98 98,5 99 99,5 100 0m/ s 5m/ s 10m/ s 15m/ s 20m/ s DSDV (%) AODV (%) DSR (%) Hình 16: Đồ thị tỷ lệ phân phát gói thành công – Random Waypoint Kết quả phân phát gói tin dữ liệu Ph ần t ră m g ói t in t ru yề n th àn h cô ng (% ) Vận Tốc 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 Phạm Văn Tứ 45 K51MMT b. 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 96 96,5 97 97,5 98 98,5 99 99,5 100 100,5 0m/ s 5m/ s 10m/ s 15m/ s 20m/ s DSDV (%) AODV (%) DSR (%) Hình 17: Đồ thị tỷ lệ phân phát gói tin thành công – Random Walk Kết quả phân phát gói tin dữ liệu Ph ần t ră m g ói t in t ru yề n th àn h cô ng (% ) Vận Tốc 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 Phạm Văn Tứ 46 K51MMT 4.3.2.2. Thời gian thiết lập kết nối a. Random Waypoint Hình 18: Đồ thị thời gian thiết lập kết nối trung bình_Random-Waypoint b. Mô hình Random Walk Hình 19: Đồ thị thời gian thiết lập kết nối trung bình_Random-Walk 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 Phạm Văn Tứ 47 K51MMT 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 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 Phạm Văn Tứ 48 K51MMT 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. 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 Phạm Văn Tứ 49 K51MMT KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. 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. 2. 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ư: 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 Phạm Văn Tứ 50 K51MMT  Vấn đề năng lượng  Chất lượng dịch vụ  Vấn đề bảo mật,… 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 Phạm Văn Tứ 51 K51MMT 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. 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 Phạm Văn Tứ 52 K51MMT [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. lab/Ad-Hoc+Protocols.html [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. 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 Phạm Văn Tứ 53 K51MMT PHỤ LỤC 1. 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 ------- [%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 ARP Trace int Destination Address Địa chỉ đích %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 DSR Trace int Number Of Errors Số lượng lỗi 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 Phạm Văn Tứ 54 K51MMT 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 [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 AODV Trace string Operation (REPLY, ERROR, HELLO) Hoạt động: Trả lời, Lỗi hay gói tin Hello [0x%x %d] (QUERY) hexadecimal Type Kiểu int Destination Đích TORA Trace 0x%x %d (%f %d %d %d %d) (UPDATE) 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 Phạm Văn Tứ 55 K51MMT 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 [%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 IMEP Trace hexadecimal Length Chiều dài ------- [%c %d %d %d] char Operation (A, R, D) int RCA Source int RCA Link Destination RCA Trace (from MIT Leach code) int RCA MAC Destination 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 Phạm Văn Tứ 56 K51MMT 2. 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 \ 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 Phạm Văn Tứ 57 K51MMT -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 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 Phạm Văn Tứ 58 K51MMT 3. 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"; 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 Phạm Văn Tứ 59 K51MMT print STDOUT "Tỷ lệ phân phát gói tin thành công = $productivity % \n"; close DATA; exit(0); 4. 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