Tài liệu Manet định tuyến dựa trên tiên đoán vị trí

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ v € MẠNH CƯỜNG M A N E T- Đ ỊN H T U Y Ế N DựA T R Ê N T IÊ N Đ O ÁN V Ị T R Í Ngành: Công nghệ Điện tử - Viễn thông. Chuyên ngành: Kỹ thuật vô tuyến điện tử và 'lĩiône tin liên lạc Ma so: 2.07.00 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS TS Nguyẻn Viết Kính (Trường ĐHCN - ĐHQG Hà Nội) ĐAI H Ọ C ý ƯỚC G IA HÀ NÒI TRUNG TAM THÒNG TIN THƯ VIỆN '1 HÀ NỘI 2006 / Á ỵí •ỉ MỤC LỤC M Ụ C L Ụ C ................................................................................................................................1 TÓM TẮT........................................................................................................................... 3 DANH MỤC HÌNH VẼ.............................................................................................. 4 DANH MỤC BẢNG B lỂ ư .........................................................................................6 BẢNG KÝ HIỆU CÁC CHỮVIÊT TẮT..................................................................7 MỞ ĐẦU.................................................................................................... 8 CHƯƠNG I: GIỚI THIỆU....................................................................................10 • 1.1 Mạng di động Ad hoc (MANET)....................................................................10 1.1.1 Sự phát triển của mạng...................................................................................11 1.1.2 Các ngữ cảnh sử dụng mạng......................................................................... 13 1.1.3 Các đặc điểm mạng........................................................................................14 1.2 Vấn đề định tuyến..............................................................................................15 1.2.1 Các thuật toán định tuyến truyền thống...................................................... 15 1.2.2 Bài toán định tuyến mạng MANET............................................................. 17 CHƯƠNG 2: GIAO THỨC ĐỊNH TUYẾN MANET....................................... 19 2.1 Các kỹ thuật định tuyến MANET....................................................................19 2.1.1 Định tuyến L S v à D V ....................................................................................19 2.1.2 Định tuyến chủ ứng và định tuyến phán ứng.............................................. 19 2.1.3 Cập nhật định kỳ và cập nhạt theo sự k iệ n ................................................ 20 2.1.4 Cấu trúc phẳng và cấu trúc phân cấp........................................................... 20 2.1.5 Tính toán phi tập trung và tính toán phân tán.............................................20 2.1.6 Định tuyến nguồn và định tuyến theo chặng.............................................. 21 2.1.7 Đơn đường và đa đường................................................................................. 21 2.2 Phân loại các giao thức định tuyến MANET................................................21 2.2.1 Giao thức DSDV.............................................................................................22 2.2.2 Giao thức OLSR............................................................................................. 23 2.2.3 Giao thức AODV............................................................................................24 2.2.4 Giao thức DSR................................................................................................ 25 2.2.5. Giao thức TOR A ........................................................................................... 26 2.2.6 So sánh các giao thức..................................................................................... 27 2.3 MANET- Định tuyến dựa trên tiên đoán vị trí............................................ 30 2.3.1 Giao thức cập nhật..........................................................................................31 2.3.2 Tiên đoán.........................................................................................................34 2.3.3 Định tuyến ỌoS.............................................................................................. 36 CHƯƠNG 3: MÔ PHÒNG CÁC MẠNG DI ĐỘNG AD HOC.......................39 3.1 Mô hình các MANET........................................................................................39 3.2 Bộ mô phỏng NS2............................................................................................. 39 3.3 Thiết lập MANET dùng mô phỏng trong NS2.......................................... 40 3.3.1 Mô phòng mạng không dây di độno,........................................................ 40 3.3.1.1 Nút di động mô phỏng...............................................................................40 3.3.1.2 Mô hình phương tiện chia sẻ..................................................................42 3.3.1.3 Hoạt động của nút di động..................................................................... 43 3.3.2 Tạo ngữ cảnh......... ..................................................................................... 43 3.3.2.1 Các mô hình chuyển động.........................................................................44 a.Mô hình Random Waypoint............................................................................... 44 b. Mô hình Random Walk................................................................................. 45 c. Mô hình Random Direction...............................................................................47 3.3.2.2 Các mô hình thông lượng..........................................................................48 3.4 Tổng quan quá trình mô phỏng.......................................................................49 3.5 Mô phỏng các giao thức định tuyến............................................................... 50 3.5.1 DSDV.T..... .7............... ........ ...............................................................50 3.5.2 3.5.3 3.5.4 3.5.5 AODV..............................................................................................................51 DSR..................................................................................................................51 TORA.............................................................................................................. 52 OLSR...............................................................................................................53 CHƯƠNG 4: ĐÁNH GIÁ HIỆU SUẤT CÁC GIAO THỨC ĐỊNH TUYẾN VÀ ĐỊNH TƯYẺN QOS D ựA TRÊN TIÊN ĐOÁN VỊ TRÍ................................ ... ............................................ ......... 54 4.1 Các tham số của môi trường............................................................................ 54 4.2 Các độ đo hiệu năng............................................................................55 4.3 Các thí nghiệm mô phỏng................................................................. 56 4.3.1 4.3.2 4.3.3 4.3.4 Thí nghiệm 1: sử dụng mô hình Random Waypoint................................57 Thí nghiệm 2: sử dụng mô hình Random W alk........................................63 Thí nghiệm 3: Sử dụng mỏ hình Random Direction.................................67 Thí nghiệm 4 : So sánh mô hình thông lượng TCP và CBR trong giao thức định tuyến DSR và DSDV....................... 71 4.4 Nhận xct về hiệu năng của các giao thức..................................................... 77 4.5 Thí nghiệm 5: Đánh giá định tuyén ỌoS dựa trên tiên đoán vị tri'..............80 K ẾT LUẬN....... :..................................................................................................85 TÀI LIỆU THAM K H Ả O ................................................................................. 87 2 DANH MỤC HÌNH VẼ Hình 1-1: MANET................................................................................................. 10 Hình 1-2: Hoạt động của mạng đơn chặng và đa chặng............................... 12 Hình 1-3: Mạng WPAN với các kết nối Internet............................................ 14 Hình 2-1: Phân loại các giao thức định tuyến mạng MANET.....................22 Hình 2-2: Định tuyến trạng thái liên kết và định tuyến cải tiến trong O L SR ..................................................................................................... 24 Hình 2-3: Sự hình thành đường trong giao thức T O R A ............................... 26 Hình 2-4: Tần suất cập nhật loại 1 phụ thuộc vận tốc của nút................... 32 Hình 2-5: Cập nhật loại 2 ..................................................................................... 32 Hình 2-6: Tiên đoán vị trí, sử dụng cập nhật loại 2....................................... 35 H ình 3-1: Mô phỏng /?út di động trong NS2 ..................................................... 41 Hình 3-2: Mô hình phương tiện chia sẻ trong NS2.........................................42 Hình 3-3: Di chuyển của một nút theo mô hình Random Waypoint..........45 Hình 3-4: Di chuyển của một nút theo mô hình Random Walk.................. 46 Hình 3-5: Sự di chuyển của một nút theo mô hình Random D irection...47 Hình 3-6: Các mô hình thông lượng trong NS2.............................................. 48 Hình 3-7: Tổng quan quá trình mô phỏng........................................................49 Hình 4-1: So sánh kết quả phân phát gói tin trong mỏ hình Random Waypoint................................................................................................ 59 Hình 4-2: So sánh trẻ đầu cuối trung bình trong mô hình Random Waypoint............................................................................................... 60 Hình 4-3: So sánh tải định tuyên chuẩn hoá trong mô hình Random Waypoint................................................................................................63 Hình 4-4: So sánh kết quả phân phát gói tin trong mô hình Random W alk........................................................................................................ 65 Hình 4-5: So sánh thời gian trẻ trung bình trong mó hình Random W alk......................................................................................................66 4 Hình 4-6: So sánh tải định tuyến chuấn hoá trong mô hình Random W alk....................................................................................................... 67 Hình 4-7: So sánh kết quả phân phát gói tin trong mỏ hình Random Direction...............................................................................................69 Hình 4-8: So sánh thời gian trễ trung bình trong mô hình Random Direction...............................................................................................69 Hình 4-9: So sánh tải dịnh tuyến chuẩn hoá trong mỏ hình Random Direction............................................................................................... 70 Hình 4-10: So sánh tỉ lệ phát gói tin thành công TCP và CBR trong giao thức DSDV............................................................................... 72 Hình 4-11: So sánh tải định tuyến chuẩn hóa của TCP và CBR trong giao thức DSDV............................................................................... 73 Hình 4-12: So sánh phần trăm gói tin phát thành công của TCP và CBR trong giao thức DSR........................................................................ 74 Hình 4-13: Trễ đầu cuối trung bình cüa TCP và CBR trong giao thức DSR.................................................................................................. 75 Hình 4-14: So sánh tải định tuyến chuẩn hóa TCP và CBR trong giao thức DSR..........................................................................................76 Hình 4-15: Phần trăm lỗi của tiên đoán vị trí và tiên đoán vị trí kết hợp trễ đầu cuối.......................................................................................81 Hình 4-17: Sự chính xác của vị trí dự đoán trế vói cập nhật loại 1..........82 Hình 4-17: Tổng số lỗi của khoảng lỗi tăng dần........................................... 82 Hình 4-18: số lượng gói tin trung bình cập nhật loai 1 của nút/giây.......83 5 DANH MỤC BẢNG BíỂU Bảng 2-1: So sánh độ phức tạp của các giao thức...........................................28 Bảng 2-2: So sánh giữa các giao thức................................................................ 29 Bảng 2-3: So sánh giữa các giao thức................................................................ 30 Bảng 3-1: Các tham số cua mô hình Random Waypoint..............................45 Bảng 3-2: Các tham số của mô hình Random Walk......................................46 Bảng 3-3: Các tham số của mô hình Random Direction...............................47 Bảng 3-4: Các tham số hoạt động của DSDV trong NS2............................50 Bảng 3-5: Các tham số hoạt động của AODV trong NS2...........................51 Bảng 3-6: Các tham số hoạt động của DSR trong NS2................................. 52 Bảng 3-7: Các tham số hoạt động của TORA trong NS2............................... 52 Bảng 3-8: Các tham số hoạt động của OLSR trong mô phỏng................. 53 Bảng 4-1: Cấu hình các mạng mô phỏng theo mô hình Random W aypoint................................................................................................ 58 Bảng 4-2: Tải định tuyến chuẩn hoá của TORA trong mô hình Random W aypoint................................................................................................ 62 Bảng 4-3: Cấu hình các mạng mó phỏng theo IĨ1Ô hình Random Walk...65 Bảng 4-4: Cấu hình các mạng mỏ phỏng theo mô hình Random Direction................................................................................................. 68 Bảng 4-5: c ấ u hình mô phỏng đẻ so sánh CBR, TCP trong giao thức DSR và DSDV....................................................................................... 71 Bảng 4-6: c ấ u hình mô phỏng định tuyến QoS dựa trên tiên đoán vị trí—81 6 B Ả N G K Ý H IỆ U C Á C C H Ũ V I É T T Ả T AODV Ad hoc On-demand Distance Vector CBR Constant Bit Rate CSMA/CA Carrier Sense Multiple NAM Network Animator NS2 Network Simulator 2 OLSR Optimized Link Slate Routing Protocol Access with Collision Avoidance DARPA Defense Advanced PAN Personal Area Network PDA Personal Digital Research Projects Agency DSDV PRnet Packet Radio Network QoS Quality o f Service RIP Routing Information Destination-Sequenced Distance Vector DSR Dynamic Source Routing DV Distance Vector IEEE Institute o f Electrical and Electronic Engineering IETF Assistant Internet Engineering Task Force Protocol RREP Route Reply RJR.EQ Route Request RTS Request To Send TC Topology Control TORA Temporally-Ordered LAN Local Area Network LS Link State MAC Medium Access Control WLAN Wireless LAN MAN ET Mobile Ad hoc Network WPAN Wireless PAN MPR Multipoint Relay Routing Algorithm MỞ ĐẦU Nhằm đạt tới sự giải phóng hoàn toàn của mạng di động không dây vào các cơ sở hạ tầng mạng cố định, nhiều hướng nghiên cứu, nhiều mô hình kiến trúc hoạt động mới đã được dưa ra. Một trong những hướng được đánh giá cao là mạng di động Ad hoc. Đây là mạng kết nối các thiết bị tính toán di động như các máy tính Laptop, PDA hay điện thoại cầm tay ở trong cùng một khu vực mà không cần tới các cơ sở hạ tầng mạng cố định hay đơn vị quản trị trung tâm hỗ trợ [20]. Đặc trưng của truyền thông trong MANET là đa chặng, giữa nút nguồn và nút đích có thể đi qua nhiều nút trung gian. Với cấu hình tế bào chuẩn, định tuyến mỗi gói tin chỉ thông qua một chặng từ cơ sở tới nút di động. Nhưng trong MANET các gói tin có thể được định tuyến thông qua nhiéu chặng. Mặt khác MANET có cấu hình hết sức phức tạp do sự di chuyển của các nút, băng thông liên kết không dây hạn chế, khả năng tính toán và dung lượng bộ nhớ của các nút bị giới hạn. Để phát triển MANET trong thực tế cần phải phát triển các giao thức làm việc hiệu quả trong môi trường khá đặc biệt này. Luận văn này nghiên cứu các giao thức định tuyến MANET và đánh giá hiệu năng làm việc của chúng về lý thuyết và thông qua các thí nghiệm mô phỏng mạng. Các nội dung nghiên cứu cụ thể bao gồm: ❖ Nghiên cứu môi trường làm việc và các đặc điểm của mạng ❖ Xem xét bài toán định tuyến trong mạng và các giải pháp có thể. ❖ Phân loại các giao thức định tuyến. ❖ Phân tích và so sánh các giao thức trên cơ sở lý thuyết về độ phức tạp và các đặc tính hoạt động. ❖ Xây dung môi trường mô phỏng và tích hợp một số giao thức định tuyến cho MANET trong bộ mô phỏng mạng NS2. ❖ Đánh giá các giao thức định tuyến trong các ngữ cảnh với các tham số khác nhau có ảnh hưởng nhất tới hiệu suất của các giao thức định tuyến như kích thước mạng, tải mạng, tốc độ thay đổi hình trạng mạng và mô hình di chuyển. Luận văn bao gổm 4 chương chính ngoài chương giới thiệu và kết luận: Chương I: Giới thiệu về mạng MANET và bài toán định tuyến trong mạng. Chương II: Trình bày về các giao thức định tuyến trong mạng MANET, phân loại về các giao thức, mô tả chi tiết về một số giao thức tiêu biểu và so sánh giữa các giao thức. Chương III: Trình bày về việc mô phỏng MANET bằng bộ mô phỏng NS2 Chương IV: Nghiên cứu đánh giá hiệu suất các giao Ihức định tuyến với các độ đo hiệu năng cụ thể để so sánh giữa giao thức trong các điểu kiện mạng thay đổi. So sánh MANET dùng mô hình thông lượng TCP và CBR. Đánh giá MANET sử dụng định tuyến dựa trên tiên đoán vị trí. 9 CHƯƠNG I: GIỚI THIỆU 1.1 Mạng di động Ad hoc (MANET) MANET (Mobile Ad hoc NETwork) là mạng không dây đặc biệt gồm tập hợp các thiết bị di động với giao tiếp không dây có khả năng truyền thông trực tiếp với nhau khi nằm trong vùng thu/phát sóng của nhau hoặc thông qua các nút trung gian làm nhiệm vụ chuyển tiếp hình 1-1. Trong MANET, các nút vừa đóng vai trò truyền thông vừa đóng vai trò như thiết bị định tuyến. Với nguyên tắc hoạt động như vậy, MANET không bị phụ thuộc vào các cơ sở hạ tầng cố định và các đơn vị quản trị trung tâm như các mạng tế bào và WLAN truyền thống. Hình 1-1: MANET MANET có độ linh hoạt cao với khả năng hoạt động độc lập với cơ sở hạ tầng mạng cố định [14]: • Triển khai nhanh khi có yêu cầu • Tin cây và mạnh mẽ do hoạt động phân tán và khả năng tự động cấu hình lại mạng khi có các thay đổi liên kết. • Kết nối không giới hạn. • Chi phí triển khai và hoạt động thấp. Ngoài ra, MANET có ý nghĩa đặc biệt trong quân sự, chống khủng bố, trong các trường hợp tìm kiếm và cứu hộ khẩn cấp và trong việc xây dựng các mạng cảm biến ở các khu vực con người không thể truy cập được. 10 1.1.1 Sự phát triển của mạng Hỗ trợ đầu tiên cho sự phát triển MANET là việc triển khai mạng ALOHA nãm 1968 [20]. Mục tiêu cuả mạng này là kết nối các cơ sở giáo dục ở Hawaii. Mặc dù các trạm làm việc là cố định, 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, do đó đã cung cấp cơ sở cho sự phát triển về sau của các lược đồ truy cập kênh phân tán cho phép sự hoạt động của MANET. Khởi nguồn từ các mạng ALOHA và những phát triển ban đầu của mạng cố định chuyển mạch gói, tổ chức DARPA đã bắt đầu làm việc trên các mạng vô tuyến gói tin PRnet (Packet Radio network) vào năm 1973 [16]. Đây là mạng vô tuyến gói tin đa chặng đầu tiên. Trong ngữ cảnh này, đa chặng có nghĩa là các nút hợp tác để chuyển tiếp truyền thông cho các nút ở xa nằm ngoài vùng truyền thống của một nút. PRnet đã cung cấp cơ chế cho việc quản lý hoạt động trên cơ sở tập trung cũng như phân tán. Người ta cũng bắt đầu nhận thấy nhiều lợi điểm của làm việc đa chặng so với đơn chặng. Triển khai đa chặng tạo điều kiện thuận lợi cho viộc dùng lại các tài nguyên kênh truyền về cả không gian và thời gian và làm giảm năng lượng phát cần thiết. Trong khi đó, làm việc đơn chặng chỉ chia sẻ các tài nguyên kênh về thời gian và yêu cầu năng lượng cao hơn để có thể giao tiếp được với các nút ở xa. Hình 1-2 thể hiện sự can nhiễu về không gian trong các ngữ cảnh đa chặng và đơn chặng [20]. Trong cả hai trường hợp, ngữ cảnh mạng là hoàn toàn giống nhau về sự phân bố của các nút, nguồn phát và đích. Trong trường hợp đa chặng, các gói tin được định truyền thông qua nhiều điểm chuyển phát. Tuy nhiên, trong mạng đơn chặng, gói tin được gửi trực tiếp từ nguồn tới đích. Các vòng tròn thể hiện mức năng lượng phát cần thiết của mỗi nút để có thể giao tiếp với nút đích. 11 Đa chặng © ,( " • (ỉ đJ r j V0N.VỊ © \ ®\ © o /ỵ y o © 9 Nút n g u ò n ặặ Q NÚI đích Nứt ctiưyển tiép © C ác nút k h ác © Hình 1-2: Hoạt động của mạng đơn chặng và đa chặng Mặc dù nhiều mạng vô tuyến gói tin đã được phát triển sau đó, các hệ thống không giây này vẫn chưa bao giờ được đưa vào phục vụ người sử dụng thông thường. Khi chuẩn IEEE 802.11, một chuẩn cho mạng cục bộ không đây được phát triển, viện IEEE đã thay thế khái niệm mạng vô tuyến gói tin thành MANET. Các mạng vô tuyến gói tin do đó thường gắn với các mạng đa chặng rộng lớn trong quân sự. IEEE hy vọng loại mạng mới này sẽ được triển khai rộng rãi trong thực tế. Một số công nghệ không dây hiện tại hỗ trợ sự làm việc của MANET là Bluetooth và IEEE 802.11. Trong đó, IEEE 802.11 là chuẩn cục bộ không dây có sơ sở hạ tầng được bổ sung chức năng hỗ trợ làm viêc MANET [11]. Mạng IEEE 802.1 lb làm việc ở dải băng tần 2.4GHz với tốc độ dữ liệu 11 Mbps và hiện tại đã đạt tới 20 Mbps. Chuẩn IEEE 802.1 la tiếp theo hoạt động ở giải băng tần 5GHz và tốc độ dữ liệu đạt tới 54Mbps. Trong khi đó, Bluetooth là kiến trúc làm việc của MANET không dây dải sóng ngắn cho các mạng cá nhân WPAN. Mạng này nhằm mục đích kết nối các thiết bị cá nhân di động như các máy tính laptop, PDA, các thiết bị ngoại vi, điện thoại cầm tay, các máy quay kỹ thuật số, các đầu nghe và các thiết bị điện tử khác. Vùng hoạt động của mạng do vậy rất nhỏ, thường dưới 10m xung quanh cá nhân và thường được gọi là không gian hoạt động cá nhân - POS (Personal operating Space). 12 1.1.2 Các ngữ cảnh sử dụng mạng Các ứng dụng đầu tiên của mạng vô tuyến gói tin MANET là trong quân sự, trong đó sự hoạt động phi tập trung của mạng là một nhu cầu cần thiết. Ngày nay, các thiết bị tính toán không dây, di động vẫn có mức gía rất cao. Tuy nhiên, khả năng của các máy tính di động sẽ tàng lên và nhu cầu làm việc với mạng không dây sẽ ngày càng tăng. MANET có thể được dùng trong các tình huống khi không có cơ sở hạ tầng mạng cố định hoặc mạng tế bào. MANET có thể được triển khai trong truy cập công cộng không dây ở các khu vực thành phố, trường học giúp thực hiện nhanh các cuộc truyền thông và mở rộng diện hoạt động. Các điểm truy cập có thể dùng như các trạm tiếp sóng cố định thực hiện việc định tuyến giữa chúng và giữa các nút người dùng. Một số điểm truy cập có thể dùng như gateway cho phép người dùng kết nối tới mạng xương sống cố định. Ở mức cục bộ, MANET liên kết các máy tính sách tay hoặc các máy tính để bàn để phân phát và chia sẻ thông tin giữa những người tham gia một hội nghị hay lớp học. MANET cũng thích hợp cho các ứng dụng trong mạng gia đình. Trong đó, các thiết bị có thể truyền thông trực tiếp với nhau để trao đổi thông tin dữ liệu như âm thanh, hình ảnh, báo thức và các cập nhật cấu hình. Một dạng đặc biệt của MANET là mạng cảm biến (sensor network) được triểt khai trong các ứng đụng về kiểm soát môi trường. Các mạng này có thể được dùng để dự báo những ô nhiễm về nguồn nước hoặc những cảnh báo sớm về lũ lụt hoặc sóng thần. MANET dải sóng ngắn làm đơn giản hoá truyền thông của các thiết bị di động khác nhau như điện thoại tế bào và PDA bằng việc hình thành các mạng WPAN và loại bỏ sự kết nối bằng cáp. Mạng có thể giúp chia sẻ khả năng truy cập Internet và các tài nguyên trong mạng như máy in giữa các thiết bị. Khả năng này giúp mở rộng tính di động của người dùng. Hiện nay, Bluetooth là công nghệ hứa hẹn nhất trong ngữ cảnh làm việc mạng cá nhân hình 1-3 [20]. 13 Hình 1-3: Mạng WPAN với các kết nối Internet Kết hợp với truyền thông vệ tinh, công nghệ MANET sẽ rất linh động cho việc thiết lập các truyền thông được triển khai nhanh, hoàn toàn không phụ thuộc vào các cơ sở hạ tầng truyền thông cố định. 1.1.3 Các đăc điểm mạng Trong MANET, các nút là di động và được trang bị các bộ phát và nhận tín hiộu không dây sử dụng các loại ăng-ten khác nhau. Tại một thời điểm, phụ thuộc vào vị trí của nút và dạng bao phủ của bộ nhận và phát tín hiệu, mức năng lượng phát và mức độ giao thoa cùng kênh,kết nối không dây giữa các nút có dạng ngẫu nhiên và là hình đa chặng. Cấu hình này thay đổi theo thời gian do các nút di chuyển hoặc điều chỉnh các tham số phát và nhận sóng. Từ đó, có thể nhận thấy một số đặc điểm nổi bật của M ANET có ảnh hưởng tới thiết kế và hiệu suất của các giao thức trong mạng [24]: • Cấu hình mạng động: Do sự di chuyển của các núi, mạng thông thường là đa chặng, có thể thay đổi một cách ngãu nhiên và nhanh chóng tại bất kỳ thời điểm nào có thể chứa các liên kết hai chiều cũng như một chiều. • Băng thông hạn chế, khả năng của các liên kết có th ể biến đổi: Các liên kết không dây có băng thông thấp hơn đáng kể so với các đường truyền cáp. Thêm vào đó, thông lượng của các đường truyền thông không dây do ảnh hưởng 14 của đa truy cập, sự suy giảm, nhiễu và các điều kiện giao thoa thường nhỏ hơn tốc độ truyền lớn nhất của sóng vô tuyến. • Các nút cố năng lượng thấp: Một số hoặc tất cả các nút trong mạng MANET dùng pin để cung cấp năng lượng hoạt động cho các thành phần trong thiết bị. Do vậy các nút trong MANET thường bị hạn chế về khả năng tính toán của CPU, kích thước bộ nhớ, khả năng xử lý tín hiệu và mức năng lượng phát và nhận sóng. • Bảo mật vật lý có giới hạn: Do việc truyền qua không khí, các mạng không dây tiềm ẩn nhiều về nguy cơ bảo mật hơn các mạng cáp. Nhiều khả năng tấn công bảo mật như nghe trộm, giả mạo và từ chối dịch vụ (DoS) có thể xảy ra. Các kỹ thuật bảo mật cần được triển khai trên nhiêu tầng giao thức để làm giảm các nguy cơ đe doạ việc bảo mật. 1.2 Vấn đề định tuyến Định tuyến mạng là việc tìm đường đi từ nguồn tới đích qua hệ thống mạng. Giao thức định tuyến có chức năng chính là lựa chọn đường cho các cặp nguồn - đích và phân phát gói tin tới đích chính xác. Truyền thông trong MANET dựa trên các đường đi đa chặng, do vậy định tuyến các gói tin là hoạt động quan trọng. Khác với các mạng cố định có cấu hình ít thay đổi hoặc gần như không thay đổi, do truyền tin không dây và có tính chất động của MANET khiến cho các giao thức định tuyến được thiết kế cho mạng cố định không thể áp dụng hoặc gần như thất bại trong MANET. Viộc thiết kế một giao thức định tuyến làm việc hiệu quả trong MANET là một bài toán khó. 1.2.1 Các thuật toán định luyến truyền thống Để tìm đường đi cho các gói tin qua hệ thống các bộ định tuyến (router) trong mạng, các giao thức định tuyến truyền thống thường sử dụng giải thuật vectơ khoảng cách (Distance Vector Routing-DV) hoặc trạng thái liên kết (Link State Routing-LS) thuật toán DV còn được gọi là thuật toán BellmanFord, được dùng trong mạng ARPANET lúc mới ra đời và được sử dụng trong mạng INTERNET với tên gọi là giao thức thông tin định tuyến RIP (Routing 15 Information Protocol). Thuật toán LS được sử dụng trong giao thức OLSF (Open Shortest Path First) của Intemet[3]. Trong giải thuật DV, mỗi router quảng bá một cách định kỳ tới các hàng xóm thông tin khoảng cách từ nó tới tất cả các router khác. Bằng việc so sánh các khoảng cách từ mỗi hàng xóm tới một đích nào đó, router có thể quyết định hàng xóm nào sẽ là chặng tiếp theo trong trường hợp đi tới đích để đường đi là tối ưu nhất. Bảng định tuyến các router do đó lưu trữ các thông tin về các đích trong mạng (các router khác trong mạng), chặng tiếp theo và khoảng cách tới đích. Vấn đề với DV là khả năng hội tụ chậm và sự hình thành các vòng lặp định tuyến. Trong giải thuật LS, mỗi router duy trì thông tin đầy đủ về cấu hình của toàn bộ mạng. Để làm được điều này, mỗi router quảng bá định kỳ các gói tin LSP (Link State Packet) có chứa thông tin về các hàng xóm và giá tới các hàng xóm. Các thông tin này sẽ được truyển tới tất cả các router trong mạng, từ thông tin về giá của các liên kết trong toàn bộ mạng, các router có thể tính toán đường đi ngắn nhất tới các đích có thể. Việc sử dụng các giao thức truyền thống trong MANET với việc xem mỗi nút như một router dẫn tới một loạt các vấn đề [21]: • Tiêu tốn băng thông mạng và năng lượng nguồn nuôi cho các cập nhật định kỳ. • Các nút bị phá vỡ chế độ tiết kiệm năng lượng do liên tục phải nhận và gửi thông tin. • Mạng có thể bị quá tải với các thông tin cập nhật khi số nút trong mạng tăng,do đó làm giảm tính khả mở của mạng. • Các đường đi dư thừa được tích luỹ một cách không cần thiết. • Hệ thống không thể phản hồi đủ nhanh với các thay đổi thường xuyên trong cấu hình mạng. 16 1.2.2 Bài toán định tuyến mạng MANET Các giao thức định tuyến truyền thống nếu sử dụng cho MANET sẽ đặt quá nhiều công việc tính toán và truyền thông lên các nút di động trong mạng. Yêu cầu về tính hội tụ của các giao thức sẽ không thể thực hiện trong MANET với tính chất động của môi trường. Mặc dù tốc độ hội tụ có thể cải thiộn bằng cách gửi các thông điệp cập nhật thường xuyên hơn nhưng điều này sẽ làm tiêu tốn thêm băng thông và năng lượng nguồn nuôi. Hơn nữa, khi cấu hình mạng ít thay đổi việc gửi thường xuyên các cập nhật sẽ rất lãng phí. Các giao thức định tuyến trong MANET cần giảm tổng phí cho việc định tuyến, thích ứng nhanh và tự động với các điều kiộn thay đổi của mạng. Giao thức phải đảm bảo thực hiện hiệu quả trong môi trường khi các nút đứng yên, băng thông là không giới hạn và đủ hiệu quả khi băng thông tồn tại giữa các nút thấp và mức độ di chuyển và thay đổi cấu hình cao. Do đó, khi nghiên cứu thiết kế các giao thức định tuyến trong MANET, người ta thường phải xcm xét một số yếu tố sau [24]: • Hoạt động phân tán: Cách tiếp cận tập trung sẽ thất bại đo sẽ tốn rất nhiều thời gian để tập hợp thông tin trạng thái hiện tại và phát tán lại nó. Trong thời gian đó, cấu hình mạng có thể đã thay đổi. • Không có lặp định tuyến: Hiện tượng xảy ra khi một phần nhỏ các gói tin quay vòng trong mạng trong một khoảng thời gian nào đó. Một giải pháp có thể là sử dụng giá trị thời gian quá hạn. • Tính toán đường dựa trên yêu cầu: Thay thế việc duy trì định tuyến tới tất cả các nút tại tất cả các thời điểm bằng việc thích ứng với dạng truyển thông. Mục đích là tận dụng hiệu quả năng lượng và băng thông, mặc dù độ trễ tăng lên do sự phát hiện đường. • Tính toán đường trước: Khi độ trễ có vai trò quan trọng và băng thông cũng như năng lượng cho phép, việc tính toán đường trước sẽ làm giảm độ trễ phân phát. ________ rr— _____ — OAI H Ọ C Q U Ố C GIA HÀ NÔI TRƯNG TÂf>/ TH Ồ VS TIN THƯ VIỀN • Bảo mật: Giao thức định tuyến MANET có khả năng bị tấn công dễ dàng bằng một số dạng như xâm nhập truyền thông, phát lại, thay đổi các tiêu đề gói tin, điều hướng các thông điộp định tuyến. Do vậy, cần có các phương pháp bảo mật thích hợp để ngăn chặn việc sửa đổi hoạt động của giao thức. • Hoạt động nghỉ: Giao thức định tuyến cần cung cấp yêu cầu bảo tồn năng lượng của các nút khi có thể. Hỗ trợ liên kết đơn hướng, hỗ trợ trường hợp khi các liên kết đơn hướng tồn tại trong MANET. 18 CHƯƠNG 2: GIAO THỨC ĐỊNH TUYÊN MANET 2.1 Các kỹ thuật định tuyến MANET Thiết kế của các giao thức định tuyến MANET bao gồm các lựa chọn vẻ thông tin định tuyến được trao đổi, chiến lược phát các thông tin định tuyến và cách tính toán đường đi của gói tin. Các kỹ thuật định tuyến khác nhau được áp dụng trong các giao thức định tuyến MANET có thể được thống kê như sau [18,32]. 2.1.1 Định tuyến LS và D V Một số giao thức định tuyến MANET dựa trên các kỹ thuật định tuyến trong mạng có dây LS và DV để xây dựng các giải thuật thích ứng với MANET. Vấn đề định tuyến LS là tổng phí định tuyến tăng cao khi mạng có nhiều thay đổi; đối với định tuyến DV đó là vấn đề hội tụ chậm và khuynh hướng tạo ra các vòng lặp định tuyến. Các giao thức định tuyến MANET tìm cách khắc phục các hạn chế này bằng một số sửa đổi. Một số ví dụ về các giao thức nay là DSDV,OLSR,... 2.1.2 Định tuyến chủ ứng và định tuyến phản ứng Định tuyến chủ ứng (Proactive) là phương pháp định tuyến của các giao thức truyền thống; trong đó đường tới tất cả các đích được tính toán trước, các íhông tin định luyến được cập nhật định kỳ hoặc bất cứ khi nào cấu hình mạng thay đổi. Ưu điểm của phương pháp định tuyến này là độ trễ phát gói tin thấp. Tuy nhiên, một số đường không cần dùng đến và việc truyền thông điộp định kỳ tiêu tốn băng thông khi mạng thay đổi nhanh. Định tuyến phản ứng (Reactive) là phương pháp định tuyến theo yêu cầu; trong đó đường tới đích không được tính toán trước mà chỉ được xác định khi cần đến. Quá trình phát hiện liên kết bị hỏng và xây dựng lại đường được gọi là quá trình bảo dưỡng đường. Ưu điểm của định tuyến phản ứng là hạn chế được băng thông do chỉ cần đường tới các đích cần thiết và loại bỏ các cập 19 nhật định kỳ. Tuy nhiên, vấn đề với phương pháp định tuyến này là độ trễ lớn trước khi phát do phải thực hiện phát hiện đường. 2.1.3 Cập nhật định kỳ và cập nhật theo sự kiện Cập nhật định kỳ thực hiện bằng việc phát các gói tin định tuyến một cách định kỳ. Kỹ thuật này làm đơn giản hoá các giao thức và cho phép các nút học được cấu hình và trạng thái của của toàn bộ mạng. Tuy nhiên, giá trị quãng thời gian cập nhật là một tham số quan trọng. Cập nhật theo sự kiộn diễn ra khi có sự kiện xảy ra trong mạng như liên kết hỏng hoặc liên kết mới xuất hiện. Khi đó, gói tin cập nhật sẽ được quảng bá và trạng thái cập nhật được truyẻn trong toàn bộ mạng. Nhưng khi mạng thay đổi nhanh, số lượng gói tin cập nhật sẽ lớn và có thể gây ra các dao động về đường. 2.1.4 Cấu trúc phẳng và cấu trúc phân cấp Trong cấu trúc phẳng, tất cả các nút trong mạng ở cùng mức với nhau và có chức năng định tuyến như nhau. Cấu trúc phẳng đơn giản và hiệu quả với các mạng nhỏ. Tuy nhiên, đối với các mạng lớn, lượng thông tin định tuyến cũng sẽ lớn và mất nhiều thời gian hơn để thông tin định tuyến có thể tới được các nút ở xa. Đối với các mạng lớn, định tuyến phân cấp được áp dụng để giải quyết vấn đề trên. Trong định tuyến phân cấp, các nút được tổ chức động thành các phân hoạch gọi là cụm (cluster), sau đó các cluster được kết hợp lại thành các phân hoạch lớn hơn gọi là các siêu cụm (supercluster), V .V .. Việc tổ chức mạng thành các cluster giúp duy trì cấu hình mạng tương đối bền vững. Tính chất động cao của các thành viên và cấu hình mạng được giới hạn trong cluster. Chỉ có thông tin mức cao, ổn định như mức cluster hoặc supercluster được truyén qua khoảng cách xa do đó truyền thông điều khiển hay tổng phí định tuyến được giảm đáng kể. 2.1.5 Tính toán phi tập trung và tính toán phân tán Trong các giao thức dựa trên tính toán phi tập trung, mọi nút trong mạng duy trì thông tin toàn cục hoàn chỉnh về cấu hình mạng để tính toán các