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 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ứ Chương 1. GIỚI THIỆU . 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 Các mốc hình thành và phát triển của mạng không dây: 1895 1893 1887 Nikola Tesla truyền thành công sóng radio. 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ừ. 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. 1931 1915 1982 , 1991 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. -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.  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. 1998, 1999 2001 1997 -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.16 được phát hành. Chuẩn này được biết đến dưới cái tên WIMAX. Chuẩn IEEE 802.11 (WiFi) đã được tạo ra, với tốc độ tối đa là 2Mb/s. 2004, 2009 2003 2010 - 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 . 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. . 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 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 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. . 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. 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: 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. 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. 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. 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 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. 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 n 10/2009 2.4/5 20 7.2, 14.4, 21.7, 28.9, 43.3, 57.8, 65, 72.2 4 40 15, 30, 45, 60, 90, 120, 135, 150 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. 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. 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. 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,… 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 đườ