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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐOÀN CAO THANH ĐÁNH GIÁ CHI PHÍ TÌM ĐƯỜNG CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET LUẬN VĂN THẠC SĨ Hà Nội - 2011 1 Lời cám ơn Trước hết tôi xin gửi lời cám ơn tới các thầy cô giáo trong Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội đã tận tình chỉ bảo tôi trong suốt khóa học, cám ơn tập thể lớp K15T3 và đặc biệt là tới thầy giáo, PGS.TS Nguyễn Đình Việt, người đã nhiệt tình hướng dẫn, chỉ bảo tôi trong công việc nghiên cứu và học tập. Tôi cũng chân thành cám ơn tới các thành viên trong nhóm nghiên cứu với những góp ý quý báu trong quá trình thực hiện đề tài. Sau cùng tôi muốn gửi lời cám ơn tới gia đình và người thân của tôi, những người đã luôn khuyến khích và động viên tôi trong suốt khóa học. Do thời gian và điều kiện có hạn nên luận văn không tránh khỏi những thiếu sót, tôi rất mong sự góp ý của bạn bè, thầy cô và những người quan tâm đến đề tài này. 2 Lời cam đoan Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Luận văn là kết quả của quá trình học tập, nghiên cứu trong suốt hơn hai năm cao học. Trong các nội dung của luận văn, những điều được trình bày hoặc là kết quả của cá nhân hoặc là kết quả tổng hợp từ nhiều nguồn tài liệu khác. Những kết quả nghiên cứu nào của cá nhân đều được chỉ ra rõ ràng trong luận văn. Các thông tin tổng hợp hay các kết quả lấy từ nhiều nguồn tài liệu khác đều được trích dẫn đầy đủ và hợp lý. Tất cả tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình Hà Nội, Tháng 3, 2011 3 Mục lục Lời cám ơn ....................................................................................................................... 1 Lời cam đoan.................................................................................................................... 2 Danh mục các kí hiệu, các chữ viết tắt ............................................................................ 5 Danh mục các hình vẽ ...................................................................................................... 7 Danh mục các bảng .......................................................................................................... 8 Chương 1. GIỚI THIỆU CHUNG ................................................................................... 9 1.1. Đặt vấn đề [15] ..................................................................................................... 9 1.2. Mục tiêu nghiên cứu.............................................................................................. 9 1.3. Tổ chức của luận văn........................................................................................... 10 Chương 2. TỔNG QUAN VỀ MẠNG WLAN VÀ MẠNG MANET .......................... 11 2.1. Giới thiệu và phân loại mạng không dây [15]..................................................... 11 2.1.1. Phân loại theo định dạng và kiến trúc mạng................................................. 12 2.1.2. Phân loại theo phạm vi bao phủ truyền thông .............................................. 13 2.1.3. Phân loại theo công nghệ truy cập đường truyền ......................................... 14 2.1.4. Phân loại theo các ứng dụng mạng ............................................................... 14 2.2. Mạng LAN không dây (WLAN) ......................................................................... 14 2.2.1. Khái niệm về WLAN.................................................................................... 14 2.2.2. Lịch sử ra đời mạng WLAN [22] ................................................................. 16 2.2.3. Giao thức tầng con MAC trong WLAN [12] ............................................... 17 2.3. Mạng không dây đặc biệt MANET [15] ............................................................. 22 2.3.1. Sự phát triển và các ứng dụng của mạng MANET....................................... 22 2.3.2. Các đặc điểm của mạng MANET................................................................. 23 Chương 3. CÁC GIAO THỨC ĐỊNH TUYẾN MẠNG MANET ................................ 25 3.1. Giới thiệu về bài toán định tuyến [15] ................................................................ 25 3.2. Các kĩ thuật định tuyến mạng MANET [10]....................................................... 26 3.2.1. Định tuyến chủ động và định tuyến phản ứng lại......................................... 26 3.2.2. Định tuyến đơn đường và định tuyến đa đường ........................................... 26 3.2.3. Định tuyến dựa vào bảng và định tuyến khởi tạo phía nguồn ...................... 26 3.2.4. Các kĩ thuật khôi phục .................................................................................. 27 3.2.5. Chiến lược lựa chọn tuyến............................................................................ 28 3.2.6. Cập nhật định kỳ và cập nhật theo sự kiện ................................................... 28 3.2.7. Cấu trúc phẳng và cấu trúc phân cấp ............................................................ 28 3.3. Các giao thức định tuyến chủ yếu trong mạng MANET [8]............................... 29 3.3.1. Giao thức DSDV (Destination-Sequenced Distance Vector) [4] ................. 29 3.3.2. Giao thức CGSR (Clusterhead Gateway Switch Routing) [5] ..................... 30 3.3.3. Giao thức WRP (Wireless Routing Protocol) [14]....................................... 31 3.3.4. Giao thức OLSR (Optimized Link State Routing) [16] ............................... 32 3.3.5. Giao thức AODV (Ad Hoc On-Demand Distance Vector) [3] .................... 33 3.3.6. Giao thức DSR (Dynamic Source Routing) [6] ........................................... 34 4 3.3.7. Giao thức TORA (Temporally-Ordered Routing Algorithm) [11] .............. 36 3.3.8. Giao thức ABR (Associativity-Based Routing) [2]...................................... 38 3.3.9. Giao thức SSR (Signal Stability Routing) [14] ............................................ 40 3.3.10. So sánh các giao thức định tuyến chủ yếu trong mạng MANET [3]-[8] ... 40 Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG CHI PHÍ TÌM ĐƯỜNG CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN MẠNG MANET VỚI CÁC NGỮ CẢNH KHÁC NHAU ............................................................................................................................ 45 4.1. Phân tích và lựa chọn phương pháp mô phỏng để đánh giá [1].......................... 45 4.2. Bộ mô phỏng NS2 ............................................................................................... 46 4.2.1. Giới thiệu [1] ................................................................................................ 46 4.2.2. Cấu trúc phần mềm của NS2 ........................................................................ 48 4.3. Thiết lập mô phỏng mạng MANET trong NS2................................................... 48 4.3.1. Mô hình không dây cơ bản trong NS2 [9].................................................... 48 4.3.2. Quá trình mô phỏng mạng MANET với NS2 [1]......................................... 52 4.3.3. Tích hợp giao thức TORA và OLSR vào bộ mô phỏng NS2....................... 54 4.4. Đánh giá bằng mô phỏng chi phí tìm đường một số giao thức định tuyến chủ yếu trong mạng MANET............................................................................................ 56 4.4.1. Các độ đo hiệu năng được đánh giá [1] ........................................................ 56 4.4.2. Thiết lập các lựa chọn, tham số mô phỏng [17] ........................................... 57 4.4.3. Các ngữ cảnh mô phỏng ............................................................................... 57 4.4.4. Đánh giá, nhận xét chi phí tìm đường của một số giao thức định tuyến mạng MANET .................................................................................................................. 73 KẾT LUẬN.................................................................................................................... 75 TÀI LIỆU THAM KHẢO.............................................................................................. 76 PHỤ LỤC....................................................................................................................... 78 5 Danh mục các kí hiệu, các chữ viết tắt ABR Associativity-Based Routing AODV Adhoc On-Demand Distance Vector AP Access Point BQ Broadcast Query BS Base Station CBR Constant Bit Rate CDMA Code Division Multiple Access CGSR Clusterhead Gateway Switch Routing CLR Clear Packet CSMA Carrier Sense Multiple Access CSMA/CD Carrier Sense Multiple Access/Collision Detect CSMA/CA Carrier Sense Multiple Access/Collision Avoidance CTS Clear To Send DAG Directed Acyclic Graph DCF Distributed Coordination Function DIFS DCF Interframe Space DRP Dynamic Routing Protocol DSDV Destination-Sequenced Distance-Vector DSR Dynamic Source Routing FTP File Transfer Protocol GPS Global Positioning System IEEE Institude of Electrical and Electronics Engineers IETF Internet Engineering Task Force IRTF Internet Research Task Force LAN Local Area Network LCC Least Cluster Change LQ Localized Query MAC Medium Access Control MAN Metropolitan Area Network MANET Mobile Adhoc Network MRP Multipoint Relay Selector NAM Network Animator NAV Network Allocation Vector NPDU Network Protocol Data Unit NS2 Network Simulator 2 OFDM Orthogonal Frequency Division Multiplexing OLSR Optimized Link State Routing OTCL Object Tool Command Language 6 PAN Personal Area Network PCF Point Coordination Function PIFS PCF Interframe Space QoS Quality of Service RD Route Delete RN Route Notification RREP Route Reply RREQ Route Request RT Routing Table RTS Request To Send SIFS Short Interframe Space SRP Static Routing Protocol SSR Signal Stability Routing SST Signal Stability Table TC Topology Control TCL Tool Command Language TCP Transmission Control Protocol TDMA Time Division Multiple Access TORA Temporally Ordered Routing Algorithm UDP User Datagram Protocol VINT Virtual InterNetwork Testbed WAN Wide Area Network Wi-fi Wireless Fidelity WLAN Wireless Local Area Network WMAN Wireless Metropolitan Area Network WPAN Wireless Personal Area Network WWAN Wireless Wide Area Network WRP Wireless Routing Protocol ZRP Zone Routing Protocol 7 Danh mục các hình vẽ Hình 1. Ví dụ về mạng WLAN ..................................................................................... 15 Hình 2. Hiện tượng đầu cuối ẩn .................................................................................... 17 Hình 3. Hiện tượng đầu cuối lộ..................................................................................... 18 Hình 4. Giải quyết vấn đề đầu cuối ẩn với RTS/CTS................................................... 20 Hình 5. Giải quyết vấn đề đầu cuối lộ với RTS/CTS ................................................... 20 Hình 6. Các khoảng thời gian đợi SIFS, PIFS và DIFS................................................ 21 Hình 7. Chức năng điều khiển tập trung PCF............................................................... 21 Hình 8. Mạng MANET ................................................................................................. 22 Hình 9. Định tuyến hướng bảng và khởi tạo phía nguồn theo yêu cầu ........................ 27 Hình 10. Định tuyến CGSR từ nút 1 đến nút 8 ............................................................. 31 Hình 11. Phát hiện tuyến trong AODV......................................................................... 33 Hình 12. Tạo ra các bản ghi tuyến trong DSR .............................................................. 35 Hình 13. Việc tạo tuyến và đảm bảo tuyến trong TORA ............................................. 36 Hình 14. Lựa chọn tuyến trong ABR............................................................................ 38 Hình 15. Xây dựng lại tuyến trong ABR ...................................................................... 39 Hình 16. Lược đồ nút di động theo chuẩn mở rộng không dây của CMU monarch. ... 50 Hình 17. Lược đồ SRNode theo chuẩn mở rộng không dây của CMU monarch ......... 51 Hình 18. Hình ảnh 50 nút di động, giao thức DSDV, thời gian tạm dừng 0, 1 nguồn phát................................................................................................................................ 61 Hình 19. Số gói tin định tuyến trung bình cần phát với 1, 3 và 5 nguồn phát .............. 63 Hình 20. Số gói tin định tuyến trung bình cần phát với 4 giao thức định tuyến MANET ....................................................................................................................................... 64 Hình 21. Chi phí định tuyến chuẩn hóa theo tải với 1, 3 và 5 nguồn phát ................... 66 Hình 22. Chi phí định tuyến chuẩn hóa theo tải với 4 giao thức định tuyến MANET . 67 Hình 23. Thời gian phát hiện tuyến trung bình với 1, 3 và 5 nguồn phát..................... 69 Hình 24. Thời gian phát hiện tuyến trung bình với 2 giao thức định tuyến MANET .. 70 Hình 25. Số gói tin định tuyến trung bình cần phát trong mô hình Random Walk ...... 72 Hình 26. Chi phí định tuyến chuẩn hóa theo tải trong mô hình Random Walk ........... 72 Hình 27. Thời gian phát hiện tuyến trung bình trong mô hình Random Walk............. 73 8 Danh mục các bảng Bảng 1. So sánh giữa các giao thức định tuyến (Phân tích định tính 1) ....................... 29 Bảng 2. So sánh giữa các giao thức định tuyến (Phân tích định tính 2) ....................... 29 Bảng 3. So sánh đặc tính của các giao thức định tuyến hướng bảng............................ 41 Bảng 4. So sánh đặc tính của các giao thức định tuyến yêu cầu khởi tạo phía nguồn . 43 Bảng 5. Các đặc điểm ngữ cảnh giống nhau của thí nghiệm mô phỏng....................... 58 Bảng 6. Hình trạng mô phỏng với mô hình Random Waypoint ................................... 60 Bảng 7. Hình trạng mô phỏng với mô hình Random Walk .......................................... 71 9 Chương 1. GIỚI THIỆU CHUNG 1.1. Đặt vấn đề [15] Chúng ta biết rằng ngày nay khi mà tầm quan trọng của các máy tính trong cuộc sống của con người tăng lên thì điều đó cũng đòi hỏi các yêu cầu mới cho việc kết nối mạng máy tính. Ngoài các giải pháp cho mạng có dây đã được dùng từ lâu, chúng ta thấy sự gia tăng yêu cầu đối với các giải pháp cho mạng không dây để có thể kết nối tới Internet, đọc và gửi các thông điệp thư điện tử, trao đổi thông tin trong các cuộc họp… Mạng không dây đặc biệt MANET (Mobile Adhoc Networking) bao gồm các thiết bị tự tổ chức thành mạng đạt được sự giải phóng hoàn toàn khỏi cơ sở hạ tầng mạng cố định, có chi phí truyền thông thấp và triển khai dễ dàng. Về mặt thực tiễn, mạng MANET rất hữu ích cho các nhu cầu thiết lập mạng khẩn cấp tại những nơi xảy ra thảm họa như hỏa hoạn, lụt lội, động đất… Với tất cả những lý do trên, mạng MANET là một trong những lĩnh vực nghiên cứu có tính thời sự cao và đầy thách thức của mạng không dây và công nghệ này hứa hẹn sẽ trở nên phổ biến với cuộc sống của con người. Mạng MANET thừa kế những đặc tính truyền thống của mạng không dây và truyền thông di động như tối ưu hóa băng thông, điều khiển năng lượng và tăng chất lượng truyền thông. Ngoài ra, việc truyền qua nhiều chặng, không dựa trên cơ sở hạ tầng mạng cố định và đặc biệt là sự di chuyển tùy ý của mọi nút mạng đặt ra những vấn đề nghiên cứu mới về định tuyến, tiết kiệm năng lượng và an ninh. Nhiều cách tiếp cận và giao thức khác nhau đã được đề nghị để giải quyết các vấn đề phát sinh, một số phương pháp và giao thức đã được IETF và IRTF chuẩn hóa. 1.2. Mục tiêu nghiên cứu Với nhu cầu sử dụng mạng mọi lúc, mọi nơi và không phụ thuộc vào vị trí vật lý, mạng không dây đặc biệt MANET cho phép các máy tính di động thực hiện các kết nối và truyền thông với nhau không cần dựa trên cơ sở hạ tầng mạng có sẵn. Tuy nhiên, bởi cấu trúc của mạng MANET có thể thường xuyên thay đổi do các nút có thể gia nhập hay rời khỏi mạng nên để cho mạng có thể hoạt động thì tất cả các nút cần phải thực hiện chức năng tương đương với một bộ định tuyến. Vấn đề định tuyến tại tầng mạng được quan tâm đến nhiều nhất và cần tập trung giải quyết hai vấn đề cơ bản là tìm ra đường đi từ nút phát đến nút nhận và làm thế nào để duy trì đường đi. Việc định tuyến trong mạng MANET luôn đòi hỏi các chi phí về tài nguyên như dải thông đường truyền, năng lượng tiêu hao trong quá trình tìm đường, dung lượng bộ nhớ cần thiết cho việc lưu trữ bảng định tuyến và thời gian tìm đường. Đề tài luận văn này nhằm mục đích đánh giá và so sánh chi phí tìm đường của một số giao thức định tuyến điển hình trong mạng MANET với một số mức độ di động khác nhau của các nút mạng. Quá trình đánh giá này được thực hiện qua lý thuyết và thông qua mô phỏng với các nội dung bao gồm: 10 ü Nghiên cứu các đặc điểm của mạng MANET ü Xem xét bài toán định tuyến trong mạng MANET và các giải pháp có thể ü Phân loại các giao thức định tuyến mạng MANET ü Xây dựng thí nghiệm mô phỏng và tích hợp một số giao thức định tuyến mạng MANET vào bộ mô phỏng NS2 ü Đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET với các ngữ cảnh khác nhau. Ngữ cảnh của thí nghiệm thay đổi bằng cách: · Thay đổi topo mạng (Số nút mạng, đường truyền cũng như vị trí ban đầu của mỗi nút mạng) · Thay đổi mô hình chuyển động (Mô hình Random Waypoint, Random Walk… ) · Thay đổi mô hình sinh lưu lượng (TCP, CBR) · Thay đổi diện tích và hình dạng vùng mô phỏng · Thay đổi thời gian hoạt động của các nguồn sinh lưu lượng · Thay đổi thời gian mô phỏng 1.3. Tổ chức của luận văn Nội dung của luận văn được tổng hợp thành 4 chương chính. Chương đầu tiên đưa ra mục tiêu nghiên cứu và tổ chức chi tiết của luận văn. Chương 2 của luận văn trình bày tổng quan về mạng không dây WLAN và mạng không dây đặc biệt MANET. Phần nghiên cứu tìm hiểu về việc định tuyến cũng như các yêu cầu với giao thức định tuyến trong mạng MANET được trình bày ở chương 3. Ngoài ra, các kĩ thuật định tuyến mạng MANET và việc phân loại các giao thức định tuyến mạng MANET cũng được mô tả chi tiết tại chương này. Phần giới thiệu về bộ mô phỏng NS2, các thí nghiệm, đánh giá mô phỏng và những kết quả phân tích, so sánh được mô tả ở chương 4 của luận văn. Phần cuối cùng của luận văn là kết luận những công việc mà luận văn đã đạt được và những hướng nghiên cứu tiếp theo trong tương lai. 11 Chương 2. TỔNG QUAN VỀ MẠNG WLAN VÀ MẠNG MANET 2.1. Giới thiệu và phân loại mạng không dây [15] Những năm gần đây, công nghệ thông tin đã có những bước tiến vượt bậc và được áp dụng vào hầu hết các mặt của đời sống xã hội như kinh tế, giáo dục, y tế, quân sự… Xã hội càng phát triển thì nhu cầu tìm hiểu và cập nhật thông tin ngày càng tăng, con người muốn được kết nối với thế giới ở bất kỳ chỗ nào, bất kỳ nơi đâu. Điều đó giải thích tại sao mạng không dây lại được ra đời và phát triển mạnh. Ngày nay, chúng ta có thể bắt gặp mạng không dây ở nhiều nơi như những văn phòng, tòa nhà, các công ty, các tổ chức, tại các trường học, bệnh viện hay thậm chí là các quán cà phê, quán ăn nhanh. Nhờ những cải tiến nhanh chóng trong công nghệ mạng không dây và sự ra đời của các dịch vụ và ứng dụng không dây mới, phạm vi truyền thông không dây đã có những thay đổi đáng kể. Với sự nổi lên của các mạng tế bào thế hệ thứ ba làm tăng tốc độ truyền dữ liệu, cho phép cung cấp các dịch vụ dữ liệu di động đa dạng với tốc độ cao hơn. Trong khi đó thì các chuẩn mới cho sóng vô tuyến phạm vi ngắn như Bluetooth, 802.11, HiperLAN và truyền hồng ngoại đang hỗ trợ để tạo phạm vi rộng hơn cho các ứng dụng mới tại các hộ gia đình hay xí nghiệp, cho phép truyền thông không dây dữ liệu đa phương tiện được tốt hơn. Nói chung, khái niệm mạng không dây ám chỉ mạng sử dụng phương tiện truyền là sóng hồng ngoại hoặc vô tuyến điện để chia sẻ thông tin và các tài nguyên giữa các thiết bị. Nhiều kiểu thiết bị không dây đang được sử dụng phổ biến ngày nay như các thiết bị cá nhân cầm tay (PDA), các máy tính xách tay (notebook, netbook), các máy điện thoại di động, cảm biến không dây (wireless sensor), các thiết bị nhận vệ tinh… Truyền thông không dây có các đặc tính như sau: ü Nhiễu cao hơn trong khi độ tin cậy thấp hơn o Các tín hiệu hồng ngoại chịu nhiễu từ ánh sáng mặt trời và các nguồn nhiệt và có thể bị che chắn bởi nhiều loại vật cản. Các tín hiệu vô tuyến điện thường có thể xuyên qua nhiều loại vật cản tuy nhiên chúng có thể bị nhiễu bởi các thiết bị điện và điện tử. o Truyền quảng bá đồng nghĩa với việc tất cả các thiết bị có khả năng gây nhiễu cho nhau o Tự nhiễu bởi đặc tính truyền đa đường (multi-path fading) ü Băng thông và tốc độ truyền thấp hơn o Thông thường tốc độ truyền của mạng không dây chậm hơn và không ổn định so với mạng có dây, dẫn đến độ trễ và biến động trễ (jitter) cao hơn. Đây là nguyên nhân làm giảm chất lượng dịch vụ. ü Các điều kiện mạng biến đổi cao và thất thường 12 o Tỉ lệ mất mát dữ liệu cao hơn do nhiễu o Việc di chuyển của người dùng dẫn đến việc bị ngắt kết nối thường xuyên o Sự thay đổi kênh khi những người dùng di chuyển vòng quanh o Năng lượng nhận được giảm dần theo khoảng cách ü Các tài nguyên tính toán và năng lượng bị hạn chế. o Sức mạnh tính toán, bộ nhớ, kích thước ổ đĩa, dung lượng pin bị hạn chế cũng như việc giới hạn kích cỡ thiết bị, trọng lượng và chi phí. o Sự hạn chế của các tần số với các quy định khắt khe o Sự khan hiếm và đắt của phổ o Giới hạn kích cỡ thiết bị dẫn tới việc các kết quả bị giới hạn trong giao diện người dùng và màn hình ü Độ bao phủ dịch vụ bị hạn chế o Do việc giới hạn công suất phát của thiết bị mạng dẫn đến khoảng cách truyền bị hạn chế, việc thực thi dịch vụ trong mạng không dây phải đối mặt với nhiều ràng buộc và chịu nhiều thách thức hơn so với mạng có dây. ü Thực hiện bảo mật khó hơn o Do giao diện sóng vô tuyến là có thể bị truy cập bởi bất kỳ người nào trong phạm vi phủ sóng của thiết bị phát, đảm bảo an ninh mạng không dây là khó thực thi hơn. Hiện nay có nhiều kiểu mạng không dây tồn tại và có thể được phân loại theo nhiều cách đa dạng phụ thuộc vào tiêu chuẩn được lựa chọn cho việc phân loại. 2.1.1. Phân loại theo định dạng và kiến trúc mạng Các mạng không dây có thể được chia thành hai kiểu lớn dựa trên cách làm thế nào mạng được khởi tạo và kiến trúc mạng bên dưới. Người ta có thể phân loại thành: ü Mạng dựa trên cơ sở hạ tầng: Mạng dựa trên cơ sở hạ tầng được tạo bởi các nút mạng có kết nối không dây, có thể di động, chúng truyền thông với nhau một cách trực tiếp hoặc thông qua một nút thuộc mạng có dây (nút cố định), nút này đồng thời đóng vai trò nút cổng, qua đó các nút mạng không dây có thể kết nối với các máy tính trong mạng có dây và Internet. Lấy ví dụ mạng gồm một số nút di động không dây kết nối với một hoặc một vài AP (Access Point), các AP này có thể kết nối với mạng LAN có dây và Internet. WLAN thuộc kiểu này. ü Mạng không có cơ sở hạ tầng (MANET): Trong trường hợp này mạng được tạo một cách động thông qua việc kết hợp của một tập tùy ý các nút độc lập. Không có sự sắp xếp trước bất chấp vai trò xác định của mỗi nút. Thay vì đó, mỗi nút đưa ra quyết định một cách độc lập dựa trên tình huống mạng không cần sử dụng cơ sở hạ tầng mạng tồn tại trước. Lấy ví dụ, hai chiếc máy tính được trang bị với cạc mạng không dây có thể thiết lập mạng độc lập mỗi khi chúng nằm 13 trong phạm vi của thiết bị kia. Trong mạng MANET, mỗi nút thực hiện chức năng tương đương với một bộ định tuyến, cộng tác với các nút khác để thực hiện việc phát hiện và bảo đảm các tuyến tới các nút trong mạng. 2.1.2. Phân loại theo phạm vi bao phủ truyền thông Giống như các mạng có dây, các mạng không dây có thể được phân loại thành các kiểu khác nhau dựa trên khoảng cách mà dữ liệu được truyền, bao gồm: ü WWAN (Wireless Wide Area Network): Là mạng WAN không dây dựa trên cơ sở hạ tầng bao gồm MSCs và trạm BS,… làm việc để cho phép các người dùng thiết lập các kết nối không dây sử dụng sóng vô tuyến thay vì cáp đồng truyền thống. Các kết nối này có thể được tạo ra trên các phạm vi địa lý lớn, thậm chí bao trùm các thành phố hoặc các nước bằng việc sử dụng nhiều trạm BS hoặc hệ thống truyền thông vệ tinh. Các mạng máy tính dựa trên các mạng viễn thông kiểu tế bào (CDMA hoặc GSM) và các hệ thống vệ tinh là những ví dụ điển hình về các mạng WWAN. ü WMAN (Wireless Metropolitan Area Network): Là các mạng không dây cố định cỡ thành phố, có cơ sở hạ tầng, cho phép người dùng thiết lập các kết nối không dây dải tần rộng giữa nhiều vị trí trong một vùng dân cư ví dụ như giữa nhiều tòa nhà, văn phòng trong một thành phố hoặc trong khuôn viên của trường đại học mà không phải trả chi phí cao cho việc chạy cáp quang hoặc cáp đồng. Ngoài ra, mạng WMAN có thể dùng làm mạng dự phòng cho các mạng có dây khi các mạng có dây không khả dụng. Cả sóng vô tuyến và ánh sáng hồng ngoại có thể được sử dụng trong WMAN để truyền dữ liệu. Tổ chức IEEE có một tập các chuẩn về WMAN trong IEEE 802.16 và khuyến nghị sử dụng trong thực tế để hỗ trợ việc phát triển và triển khai mạng WMAN băng thông rộng. ü WLAN (Wireless Local Area Network): Là mạng LAN sử dụng đường truyền không dây để liên kết các thiết bị, các thiết bị thường truyền thông với nhau thông qua điểm truy cập – AP (Access Point), phương pháp truy cập đường truyền thường là CSMA/CA với tầng vật lý sử dụng phương pháp trải phổ hoặc OFDM. Điều này cho phép người dùng di động có thể di chuyển xung quanh AP trong phạm vi phủ sóng của nó mà vẫn duy trì được kết nối mạng. WLAN ngày càng trở nên phổ biến ở các hộ gia đình bởi việc cài đặt dễ dàng và sự phổ biến của các máy tính xách tay. ü WPAN (Wireless Personal Area Network): Là mạng không dây cá nhân được tạo bởi sự kết nối vô tuyến giữa các thiết bị không dây như PDA, điện thoại di động hay máy tính cá nhân… trong phạm vi ngắn. WPAN có tầm phủ sóng ngắn thông thường trong phạm vi 10m. Hai công nghệ WPAN chính là Bluetooth và ánh sáng hồng ngoại. Bluetooth là công nghệ sử dụng sóng vô tuyến thay thế cáp để truyền dữ liệu trong khoảng cách 9-10m. Công nghệ truyền hồng ngoại có thể kết nối các thiết bị trong phạm vi 1m. WPAN đang 14 được thúc đẩy phát triển mạnh mẽ bởi độ phức tạp thấp, tiêu thụ ít năng lượng và tương thích với các mạng 802.11 [15]. 2.1.3. Phân loại theo công nghệ truy cập đường truyền Phụ thuộc vào các chuẩn xác định (tần số, phương pháp truyền sóng và điều khiển truy cập đường truyền… ) các mạng không dây có thể được phân loại như sau: ü Các mạng GSM ü Các mạng TDMA ü Các mạng CDMA ü Các mạng vệ tinh ü Các mạng Wi-fi (802.11) ü Các mạng Hyperlan2 ü Các mạng bluetooth ü Các mạng hồng ngoại 2.1.4. Phân loại theo các ứng dụng mạng Các mạng không dây cũng có thể được phân loại dựa trên đối tượng sử dụng mạng và các ứng dụng mà mạng cung cấp, ví dụ: ü Các mạng doanh nghiệp ü Các mạng gia đình ü Các mạng quân sự ü Các mạng cảm biến ü Các mạng xe cộ tự động 2.2. Mạng LAN không dây (WLAN) 2.2.1. Khái niệm về WLAN Các mạng cục bộ không dây cho phép người dùng thiết lập các kết nối không dây giữa các thiết bị trong một vùng nhỏ, thông thường thuộc một tổ chức hay trong một tòa nhà, hoặc trong một không gian công cộng như sân bay, sân ga. WLAN có thể được sử dụng trong các không gian cần kết nối mạng tạm thời, hoặc tại những nơi trong đó việc chạy cáp là không được phép hoặc khó thực hiện. WLAN thường là phần mở rộng của mạng LAN có dây hoặc của mạng Internet để hỗ trợ cho người dùng có thể làm việc ở nhiều vị trí khác nhau. Các văn phòng, hộ gia đình, cửa hàng cà phê hay các sân bay thường là các điểm nóng cho việc cài đặt WLAN. Hình 1 là ví dụ minh họa về mạng WLAN. 15 Hình 1. Ví dụ về mạng WLAN WLAN có thể vận hành trong chế độ có cơ sở hạ tầng hoặc MANET. Trong chế độ có cơ sở hạ tầng, các trạm không dây kết nối tới các điểm truy cập không dây (AP) có chức năng như là cầu nối các trạm không dây với nhau và kết nối chúng với mạng LAN hoặc Internet. Một số AP kết nối với một mạng LAN có vai trò như là xương sống mạng WLAN. Trong chế độ MANET, nhiều trạm không dây trong một khu vực hạn chế có thể cộng tác với nhau để tạo ra một mạng tạm thời mà không cần sử dụng các AP, nếu chúng không yêu cầu truy cập vào các tài nguyên mạng. Các mạng WLAN ngày nay nói chung đều theo chuẩn 802.11. Theo chuẩn con 802.11a và 802.11b, việc truyền dữ liệu có thể đạt tới tốc độ từ 11Mbps tới 54Mbps. Mạng WLAN ra đời với rất nhiều ưu điểm đáng kể như sau: ü Sự tiện lợi: Mạng không dây cho phép người dùng truy xuất tài nguyên mạng ở bất kỳ nơi đâu trong khu vực được triển khai (tòa nhà hay văn phòng). Với sự gia tăng số người sử dụng máy tính xách tay và thiết bị di động thì đó là một điều rất thuận lợi. ü Khả năng di động: Với sự phát triển của các mạng không dây công cộng, người dùng có có thể truy cập Internet ở bất kỳ đâu. ü Hiệu quả: Người dùng có thể duy trì kết nối mạng khi họ di chuyển từ vị trí này đến vị trí khác. ü Triển khai nhanh, dễ và chi phí thấp: Việc thiết lập hệ thống mạng không dây ban đầu chỉ cần tối thiểu một điểm truy cập. Với mạng dùng cáp, phải tốn thêm chi phí và có thể gặp khó khăn trong việc triển khai hệ thống cáp ở nhiều nơi trong tòa nhà. 16 ü Khả năng mở rộng dễ dàng: Mạng không dây có thể đáp ứng tức thì khi gia tăng số lượng người dùng. Với hệ thống mạng dùng cáp cần phải gắn thêm cáp. Bên cạnh những ưu điểm mà WLAN có được, nó cũng tồn tại những nhược điểm như sau: ü Bảo mật khó khăn hơn: Do môi trường kết nối không dây là không khí nên khả năng bị tấn công là rất cao. ü Phạm vi nhỏ hơn: Một mạng chuẩn 802.11g với các thiết bị chuẩn chỉ có thể hoạt động tốt trong phạm vi vài chục mét. Nó phù hợp trong một căn nhà, nhưng với một tòa nhà lớn thì không đáp ứng được nhu cầu. Để đáp ứng cần phải mua thêm bộ lặp hay điểm truy cập, dẫn đến chi phí gia tăng. ü Độ tin cậy thấp hơn: Vì sử dụng sóng vô tuyến để truyền thông nên việc bị nhiễu, tín hiệu bị giảm do tác động của các thiết bị khác (lò vi sóng chẳng hạn) là không tránh khỏi và làm giảm đáng kể hiệu quả hoạt động của mạng. ü Tốc độ thấp hơn: Tốc độ của mạng không dây (1- 125 Mbps) chậm hơn so với mạng sử dụng cáp (100Mbps đến hàng Gbps). 2.2.2. Lịch sử ra đời mạng WLAN [22] Công nghệ WLAN xuất hiện lần đầu tiên vào cuối những năm 1990, khi những nhà sản xuất giới thiệu những sản phẩm của họ hoạt động trong băng tần 900MHz. Những giải pháp được áp dụng trong các sản phẩm này (không được thống nhất giữa những nhà sản xuất) cung cấp tốc độ truyền dữ liệu 1Mbps, thấp hơn nhiều so với tốc độ 10Mbps của hầu hết các mạng LAN sử dụng cáp hiện thời. Sau đó không lâu, vào năm 1992, các nhà sản xuất bắt đầu bán những sản phẩm WLAN sử dụng băng tần 2.4GHz. Mặc dù những sản phẩm này đã có tốc độ truyền dữ liệu cao hơn nhưng chúng vẫn sử dụng những giải pháp riêng của mỗi nhà sản xuất và không được công bố rộng rãi. Nhu cầu cần thiết cho việc hoạt động thống nhất giữa các thiết bị ở những dải tần số khác nhau dẫn đến việc một số tổ chức bắt đầu phối hợp xây dựng và phát triển ra những chuẩn mạng không dây chung. Kết quả là vào năm 1997, tổ chức IEEE đã phê chuẩn sự ra đời của chuẩn 802.11, và cũng được biết với tên gọi WIFI cho các mạng WLAN. Chuẩn 802.11 hỗ trợ ba phương pháp truyền tín hiệu, trong đó có phương pháp truyền tín hiệu vô tuyến ở tần số 2.4Ghz. Năm 1999, tổ chức IEEE đã thông qua hai sự bổ sung cho chuẩn 802.11 là các chuẩn 802.11a và 802.11b, chúng định nghĩa những phương pháp truyền tín hiệu mới nhờ đó những thiết bị WLAN dựa trên chuẩn 802.11b đã nhanh chóng trở thành công nghệ không dây vượt trội. Các thiết bị WLAN 802.11b truyền phát ở tần số 2.4Ghz, cung cấp tốc độ truyền dữ liệu có thể lên tới 11Mbps. Mục đích của việc tạo ra chuẩn IEEE 802.11b là để đáp ứng những đặc điểm về tính hiệu dụng, thông lượng và mức độ bảo mật ngang với mạng có dây. Vào năm 2003, tổ chức IEEE công bố thêm một sự cải tiến đó là chuẩn 802.11g, theo chuẩn này có thể truyền nhận thông tin ở cả hai dải tần số 2.4GHz và 17 5GHz và có thể nâng tốc độ truyền dữ liệu lên đến 54Mbps. Ngoài ra, những sản phẩm áp dụng chuẩn 802.11g cũng có thể tương thích ngược với các thiết bị theo chuẩn 802.11b. Ngày nay, chuẩn 802.11g đã đạt đến tốc độ trong khoảng 108Mbps- 300Mbps. 2.2.3. Giao thức tầng con MAC trong WLAN [12] Điểm nổi bật của mạng WLAN là giao thức tầng con MAC CSMA/CA điều khiển truy cập đường truyền chung không dây sử dụng sóng radio. Giống như mạng LAN có dây (mạng Ethernet), WLAN cũng sử dụng đa truy cập có cảm nhận sóng mang (CSMA) để điều khiển truy cập môi trường truyền. Trong mạng Ethernet, việc sử dụng thêm cơ chế phát hiện xung đột CD (Collision Detect) là hiệu quả và khả thi nhờ việc sử dụng phần cứng. Kết quả là các trạm có thể phát hiện ra xung đột trong quá trình đang truyền dữ liệu. Giao thức CSMA/CD có thể được mô tả một cách đơn giản như sau, nếu một trạm muốn truyền gói tin, nó sẽ lắng nghe xem trên đường truyền có sóng mang (carrier) hay không. Nếu đường truyền rỗi nó thực hiện truyền một gói tin. Ngược lại, nếu đường truyền bận (đang được sử dụng), nó sẽ tiếp tục lắng nghe cho đến khi đường truyền rỗi thì truyền gói tin đi với một xác suất nhất định. Ngoài ra trong quá trình truyền thì trạm vẫn lắng nghe để đảm bảo phát hiện được xung đột đối với gói tin đang truyền. Nếu phát hiện thấy có xung đột, trạm sẽ dừng ngay việc truyền trong một khoảng thời gian trước khi tiếp tục nghe đường truyền theo thuật toán như trên. Tuy nhiên với mạng WLAN, không thể sử dụng giao thức CSMA/CD do các đặc tính truyền sóng trong không khí của mạng WLAN khác rất nhiều so với truyền sóng trong cáp đồng, dẫn tới các hiện tượng không mong muốn được mô tả sau đây. ü Hiện tượng đầu cuối ẩn (Hidden Terminal) Hiện tượng đầu cuối ẩn được minh họa trên hình 2. Giả sử trạm 2 nằm trong vùng phủ sóng của trạm 1 và 3. Hai trạm 1 và 3 không nằm trong vùng phủ sóng của nhau. Nếu trạm 1 truyền gói tin dữ liệu cho trạm 2, do trạm 3 không nằm trong vùng phủ sóng của trạm 1 nên trạm 3 không cảm nhận được sóng mang của trạm 1. Do đó, nếu trạm 3 truyền dữ liệu cho trạm 2 thì dẫn đến việc xung đột tại trạm 2. Hình 2. Hiện tượng đầu cuối ẩn ü Hiện tượng đầu cuối lộ (Exposed Terminal) Hiện tượng đầu cuối lộ được minh họa trên hình 3. Giả sử trạm 2 muốn truyền dữ liệu cho trạm 1, trong lúc đó trạm 3 muốn truyền dữ liệu cho trạm 4 nhưng do trạm 18 3 cảm nhận sóng mang thấy đường truyền đang bận nên không truyền trong khi nó có thể truyền dữ liệu cho trạm 4 mà không gây ra xung đột tại trạm 1. Hình 3. Hiện tượng đầu cuối lộ Để khắc phục các đặc điểm nêu trên, trong WLAN sử dụng cơ chế đa truy cập sử dụng sóng mang tránh xung đột (CSMA/CA) với việc sử dụng gói tin biên nhận ACK. Khi một trạm muốn truyền dữ liệu, nó lắng nghe xem kênh truyền có bận hay không (đây chính là thực hiện chức năng CS). Có hai kiểu chức năng cảm nhận sóng mang trong WLAN bao gồm chức năng cảm nhận sóng mang vật lý và cảm nhận sóng mang ảo NAV (Network Allocation Vector). Nếu cả 2 chức năng cảm nhận sóng mang đều cho biết môi trường truyền là bận, tầng MAC sẽ báo cáo cho các tầng cao hơn biết việc môi trường truyền bận. NAV là một bộ định thời cho biết khoảng thời gian mà môi trường truyền sẽ được đặt trước. Phần lớn các khung theo chuẩn 802.11 chứa trường duration được sử dụng để đặt trước việc sử dụng môi trường truyền một khoảng thời gian xác định. Các trạm thiết lập giá trị NAV là thời gian chúng mong muốn sử dụng đường truyền và tiến hành đếm ngược từ giá trị NAV tới 0. Khi giá trị NAV khác không, chức năng cảm nhận sóng mang ảo cho biết môi trường là bận, ngược lại khi giá trị NAV tới 0, môi trường truyền là rỗi. Khi quá trình CS hoàn thành, nếu kênh truyền rỗi, trạm chỉ phải chờ một khoảng thời gian DIFS (DCF Interframe Space) - thời gian nhỏ nhất mà các nút mạng phải chờ trước khi sử dụng kênh truyền để truyền một gói tin dữ liệu (đây chính là thực hiện chức năng MA). Trong trường hợp ngược lại, với kênh truyền bận thì trạm phải đợi một khoảng thời gian DIFS cộng thêm khoảng trễ ngẫu nhiên gọi là “back-off time” rồi lặp lại việc lắng nghe đường truyền để tránh việc xảy ra đụng độ. Sau khoảng thời gian ngắn nhất DIFS tiếp theo, nếu môi trường rảnh rỗi thì giá trị back-off của trạm giảm đi một đơn vị. Nếu môi trường vẫn bận thì giá trị back-off này được giữ nguyên cho lần DIFS kế tiếp. Khi giá trị back-off giảm về không thì trạm có thể sử dụng đường truyền (đây chính là thực hiện chức năng CA). Tránh xung đột (CA) trong giao thức CSMA/CA sử dụng chức năng cộng phân tán DCF hoặc chức năng điều khiển tập trung PCF * Chức năng cộng phân tán DCF (Distributed Coordination Function) Chức năng cộng phân tán DCF được thực thi trong giao thức CSMA/CA với thuật toán trì hoãn (back-off) việc truyền gói tin một khoảng thời gian tăng theo hàm mũ cơ số 2 của số lần phát hiện thấy đường truyền bận. DCF yêu cầu mỗi trạm muốn truyền phải lắng nghe trạng thái kênh truyền trong khoảng thời gian DIFS. Nếu kênh 19 truyền là bận trong suốt khoảng DIFS, trạm sẽ trì hoãn việc truyền của nó. Với mạng có nhiều trạm tranh chấp môi trường truyền không dây, nếu các trạm đều cảm nhận kênh truyền bận và trì hoãn việc truy cập của chúng một khoảng thời gian giống nhau, tất cả các trạm hầu như cùng lúc phát hiện thấy kênh truyền được giải phóng và cố gắng để chiếm giữ kênh truyền. Kết quả là xung đột sẽ thể xảy ra. Để tránh vấn đề xung đột này, DCF xác định giá trị back-off ngẫu nhiên áp dụng cho trạm để trì hoãn thêm việc truy cập của nó với đường truyền. Độ dài của chu kỳ back-off được xác định bởi công thức: BackoffTime = random() x aSlotTime Sau mỗi khoảng thời gian DIFS thì giá trị back-off ngẫu nhiên sẽ giảm đi một đơn vị nếu đường truyền rỗi. Đến khi giá trị back-off giảm về không thì trạm có thể sử dụng đường truyền. Tuy nhiên, trong trường hợp có một trạm khác vẫn đang sử dụng đường truyền trước khi giá trị back-off giảm về không thì trạm vẫn giữ giá trị đó cho lần DIFS tiếp theo. Chức năng cộng phân tán có sử dụng gói tin biên nhận ACK tại bên nhận để thông báo đã nhận được gói tin thành công. Để làm được điều đó, bên nhận dữ liệu phải chiếm được đường truyền. Để gói tin biên nhận ACK không phải tranh chấp đường truyền và được truyền ngay, quá trình truyền ACK bỏ qua thuật toán back-off ngẫu nhiên và chỉ phải đợi một khoảng thời gian SIFS (Short Interframe Space) nhỏ hơn DIFS. Giao thức CSMA/CA không loại bỏ được hiện tượng xung đột. Việc sử dụng gói tin ACK giúp bên gửi biết được việc gửi gói tin có thành công hay không, nghĩa là gián tiếp xác định được xung đột. Tuy nhiên, việc sử dụng CSMA/CA + ACK không khắc phục được các hiện tượng đầu cuối ẩn và đầu cuối lộ. Để khắc phục được các hiện tượng nói trên, người ta đã đề xuất việc sử dụng thêm các gói tin điều khiển RTS và CTS. ü DCF sử dụng gói tin điều khiển RTS/CTS (Request To Send/Clear To Send) Gói tin điều khiển RTS chứa địa chỉ của trạm nhận và thời gian truyền dữ liệu cần thiết. Khi trạm nhận nhận được gói tin RTS, nó sẽ đợi khoảng thời gian SIFS và gửi lại gói tin CTS. Khi trạm gửi nhận được gói tin CTS, nó chờ khoảng thời gian SIFS sau đó bắt đầu truyền dữ liệu và đợi gói tin biên nhận ACK. Áp dụng hai kiểu gói tin này vào việc giải quyết hiện tượng đầu cuối ẩn và đầu cuối lộ như sau. Với hiện tượng đầu cuối ẩn, khi trạm 1 truyền quảng bá gói tin cho trạm 2, do trạm 3 nằm ngoài vùng phủ sóng của trạm 1 nên không cảm nhận được sóng mang và cho rằng đường truyền vẫn rỗi. Trạm 2 nhận được gói tin RTS sẽ tiến hành gửi lại gói tin CTS. Do trạm 3 nằm trong vùng phủ sóng của trạm 2 nên khi nhận được gói tin CTS biết là đường truyền đang bận nên không gửi gói tin cho trạm 2. Hình 4 minh họa việc giải quyết vấn đề đầu cuối ẩn với gói tin điều khiển RTS/CTS. 20 Hình 4. Giải quyết vấn đề đầu cuối ẩn với RTS/CTS Với hiện tượng đầu cuối lộ, khi trạm 2 quảng bá gói tin RTS tới trạm 1, trạm 3 nằm trong vùng phủ sóng trạm 2 nên cảm nhận được sóng mang và trì hoãn việc truyền dữ liệu cho trạm 4. Tuy nhiên khi trạm 1 phản hồi gói tin CTS cho trạm 2, do trạm 3 nằm ngoài vùng phủ sóng với trạm 1 nên không nhận được gói tin CTS này. Do đó, trạm 3 nghĩ rằng trạm 1 đã ra ngoài phạm vi phủ sóng và tiến hành truyền dữ liệu bình thường cho trạm 4. Hình 5 minh họa việc giải quyết vấn đề đầu cuối lộ với gói tin điều khiển RTS/CTS. Hình 5. Giải quyết vấn đề đầu cuối lộ với RTS/CTS * Chức năng điều khiển tập trung PCF (Point Coordination Function) PCF là chức năng tránh xung đột của giao thức CSMA/CA được thực hiện bên trong AP để quản lý việc phân phát các khung đến và đi từ AP mà không dẫn đến tranh chấp đường truyền. Việc thực hiện PCF cần phải có một AP, do đó nó chỉ được áp dụng cho các mạng WLAN có cơ sở hạ tầng và không được áp dụng cho mạng MANET. Trong PCF, thời gian được chia thành các siêu khung (super frame) được bắt đầu với khung dẫn đường (beacon frame) và mỗi siêu khung lại được chia thành hai giai đoạn: tranh chấp CP (Contention Period) và không tranh chấp CFP (Contention Free Period). Các AP có vai trò quyết định xem trạm nào phải chờ sau khoảng thời gian PIFS (PCF Interframe Space) để truy cập đường truyền. Giá trị của PIFS nằm giữa SIFS và DIFS, nhờ đó PCF cho phép các trạm truy cập vào môi trường truyền trước DCF nhưng vẫn đảm bảo các gói tin biên nhận ACK có thể giành được đường truyền. Hình 6 minh họa các khoảng thời gian đợi để có thể sử dụng đường truyền: 21 Hình 6. Các khoảng thời gian đợi SIFS, PIFS và DIFS Hoạt động của PCF được mô tả chi tiết trong hình 7. Ban đầu AP cho phép trạm 1 truyền dữ liệu bằng cách gửi cho trạm 1 gói tin dữ liệu D1. Trạm 1 muốn truyền dữ liệu nên gửi gói tin U1 trở lại AP sau khoảng thời gian SIFS. Sau khi AP nhận được gói tin từ trạm 1, AP chỉ định trạm 2 truyền dữ liệu sau khoảng thời gian đợi SIFS. Trạm 2 cũng muốn truyền dữ liệu nên cũng gửi lại gói tin U2. Sau khoảng thời gian SIFS, AP lại chỉ định trạm 3 truyền dữ liệu. Lúc này trạm 3 không muốn truyền dữ liệu nên AP không nhận được gói tin U3. Sau khoảng thời gian PIFS, AP lại tiếp tục chỉ định cho trạm 4 truyền dữ liệu. Trạm 4 muốn truyền dữ liệu nên gửi lại gói tin U4. AP thông báo khoảng thời gian tranh chấp sắp hết bằng cách sử dụng tín hiệu CF-END (Contention Free End). Có thể thấy rằng, trong khoảng thời gian không tranh chấp (CFP) thì tại một thời điểm chỉ có một trạm truy cập môi trường truyền, trạm đó có thể gửi hoặc không gửi dữ liệu, nhờ đó tránh được việc xảy ra xung đột. Hình 7. Chức năng điều khiển tập trung PCF 22 2.3. Mạng không dây đặc biệt MANET [15] Mạng không dây đặc biệt MANET bao gồm các thiết bị di động có hỗ trợ giao tiếp mạng không dây truyền thông với nhau không cần sử dụng cơ sở hạ tầng mạng và các vùng quản trị trung tâm. Mỗi nút trong mạng MANET hoạt động như là một bộ định tuyến độc lập và tuyến đường giữa các nút trong mạng MANET có thể bao gồm nhiều chặng. Hình 8 chỉ ra ví dụ về mạng MANET và cấu hình truyền thông của nó. Hình 8. Mạng MANET Như đã chỉ ra ở trên, mạng MANET có thể bao gồm nhiều thiết bị tính toán cá nhân bao gồm máy tính xách tay, thiết bị cầm tay cá nhân… Mỗi nút có thể truyền thông trực tiếp với các nút khác nằm trong phạm vi truyền thông của nó. Để truyền thông với các nút nằm ngoài phạm vi của nó, nút cần sử dụng các nút trung gian để truyền thông điệp theo từng chặng. 2.3.1. Sự phát triển và các ứng dụng của mạng MANET Mạng MANET ban đầu là mạng vô tuyến chuyển mạch gói được tài trợ và phát triển bởi tổ chức DARPA từ những năm đầu thập niên 1970. Sau đó vào năm 1983, mạng SURANs (Survivable Radio Networks) được đề xuất để hỗ trợ mạng có quy mô lớn hơn. Ngày nay mạng MANET được tổ chức IEEE quy chuẩn trong 802.11. Về mặt thực tiễn, mạng MANET rất hữu ích cho các nhu cầu truyền thông mang tính chất tạm thời như trong một cuộc họp hay hội thảo. Trong những trường hợp này nếu chúng ta thiết lập mạng sử dụng cơ sở hạ tầng sẽ rất tốn kém cả về thời gian lẫn chi phí thực hiện. Ngoài ra trong các tình trạng khẩn cấp tại nơi xảy ra những thảm họa như hỏa hoạn, lũ lụt, động đất…các cơ sở hạ tầng có thể bị phá hỏng dẫn đến hệ thống mạng bị ngắt không thể kết nối. Trong trường hợp này việc thiết lập nhanh mạng MANET là một giải pháp hữu ích. Nhờ đó có thể đáp ứng được việc truyền thông nhằm khắc phục, giảm thiểu thiệt hại sau thiên tai. Đối với những vùng sâu, vùng xa, những nơi có địa hình hiểm trở việc thiết lập hệ thống mạng có cơ sở hạ tầng để đáp ứng việc truyền thông là khó khăn và tốn chi phí. Vậy nên, mạng MANET là một lựa chọn tốt cho việc truyền thông tại những nơi như thế này. 23 2.3.2. Các đặc điểm của mạng MANET Khi nghiên cứu, đánh giá hiệu năng của mạng MANET cần chú ý một số đặc điểm nổi bật của mạng MANET như sau: ü Tự trị và không có cơ sở hạ tầng: Mạng MANET không phụ thuộc vào bất kỳ cơ sở hạ tầng mạng hay vùng quản trị trung tâm được thiết lập sẵn nào. Mỗi nút vận hành trong chế độ điểm nối điểm phân tán, hoạt động như là bộ định tuyến độc lập và tạo ra dữ liệu độc lập. ü Định tuyến nhiều chặng: Không sử dụng các bộ định tuyến chuyên dụng cần thiết, mỗi nút hoạt động như là bộ định tuyến và chuyển tiếp các gói tin của mỗi nút khác để cho phép chia sẻ thông tin giữa các nút di động. ü Các nút mạng có nguồn năng lượng dung lượng thấp: Các nút mạng di động nói chung đều chạy pin nên vấn đề tiết kiệm năng lượng là rất quan trọng. Điều này trở thành vấn đề lớn hơn trong các mạng MANET bởi vì mỗi nút vừa hoạt động như là hệ thống đầu cuối vừa là một bộ định tuyến cùng một lúc, do đó cần nhiều năng lượng hơn cho việc chuyển tiếp các gói tin của các nút khác trong mạng. ü Cấu trúc mạng thay đổi động: Trong các mạng MANET, vì các nút có thể di chuyển tùy ý, nên tô-pô của mạng có thể thay đổi thường xuyên và không thể dự đoán trước. Kết quả là việc xác định tuyến cần thực hiện thường xuyên hơn và khả năng mất mát gói tin cao hơn do việc xác định tuyến không kịp thời. ü Giới hạn băng thông và chất lượng: Các nút di động truyền thông với nhau bị giới hạn về băng thông, dung lượng biến đổi và dễ xảy ra lỗi và tắc nghẽn. ü Đảm bảo an ninh mạng khó hơn: Các mạng không dây di động nói chung dễ bị tổn thương bởi các mối đe dọa về an ninh thông tin cũng như an ninh vật lý hơn so với các mạng có dây cố định. Việc sử dụng các kênh không dây quảng bá mở và chia sẻ đồng nghĩa với việc các nút thiếu sự bảo vệ và dễ gặp các đe dọa an ninh. Ngoài ra, bởi vì mạng MANET là mạng không có cơ sở hạ tầng, nên về cơ bản nó phải dựa vào các giải pháp an toàn riêng rẽ của mỗi nút di động bởi việc điều khiển an ninh trung tâm là khó thực thi. Các yêu cầu an ninh chính trong mạng MANET bao gồm: o Tin cậy: Ngăn cản việc nghe trộm. o Điều khiển truy cập: Bảo vệ truy cập. o Toàn vẹn dữ liệu: Ngăn cản việc can thiệp lưu lượng (truy cập, sửa đổi, loại bỏ lưu lượng) . o Tấn công từ chối dịch vụ từ các nút độc hại. ü Khó đảm bảo chất lượng dịch vụ: Đảm bảo chất lượng dịch vụ (QoS) là quan trọng cho việc phân phối thành công lưu lượng mạng đa phương tiện. Các yêu cầu về QoS thông thường ám chỉ tới một tập các độ đo bao gồm thông lượng, tỉ lệ mất mát gói tin, độ trễ, thăng giáng độ trễ, tỉ suất lỗi…Với cấu hình mạng luôn thay đổi động, băng thông liên kết và chất lượng bị giới hạn, sự biến thiên 24 về thông lượng của liên kết, thật là khó để đạt được yêu cầu về đảm bảo chất lượng dịch vụ trong mạng MANET. 25 Chương 3. CÁC GIAO THỨC ĐỊNH TUYẾN MẠNG MANET 3.1. Giới thiệu về bài toán định tuyến [15] Chúng ta biết rằng các thay đổi thường xuyên và không thể dự đoán được trong cấu trúc mạng làm cho mạng MANET có tính động cao khiến việc định tuyến giữa các nút di động trong mạng thêm khó khăn và phức tạp. Những thách thức này cùng với tầm quan trọng đặc biệt của các giao thức định tuyến trong việc thiết lập các truyền thông giữa các nút di động khiến cho lĩnh vực định tuyến có lẽ là lĩnh vực nghiên cứu tích cực nhất trong mạng MANET. Đặc biệt hơn trong những năm gần đây, số lượng các giao thức định tuyến được đề nghị nhiều hơn và hiệu năng của chúng trong những môi trường mạng và các điều kiện lưu lượng giống nhau được nghiên cứu và so sánh. Kết quả cuối cùng của cộng đồng mạng MANET là cung cấp một tập các giao thức được chuẩn hóa có sức mạnh và khả chuyển đối với hàng chục nghìn nút mạng nhờ đó cho phép thương mại hóa các ứng dụng sử dụng mạng MANET. Mục đích đầu tiên của giao thức định tuyến mạng MANET là việc thiết lập đường đi chính xác và hiệu quả giữa các cặp nút có nhu cầu truyền thông với nhau để các thông điệp có thể được phân phát tin cậy và đúng thời điểm. Việc khởi tạo tuyến cần được thực hiện với phụ tải và tiêu thụ băng thông nhỏ nhất. Các giao thức định tuyến Distance-Vector và Link-State được thiết kế cho môi trường tĩnh vì thế không thể bắt kịp với những thay đổi cấu trúc mạng thường xuyên trong môi trường mạng MANET, kết quả gây ra việc giảm hiệu năng bao gồm việc hội tụ tuyến chậm, thông lượng truyền thông thấp. Có thể nói các giao thức định tuyến cần được thiết kế để thích hợp với các nhu cầu xác định của môi trường mạng MANET và các đặc tính của nó, cụ thể là tính di động và việc giới hạn băng thông, năng lượng. Khi nghiên cứu các giao thức định tuyến trong mạng MANET cần lưu ý các yếu tố sau: ü Thiết lập đường đi chính xác và hiệu quả: Do mạng MANET có cấu trúc mạng thay đổi động nên giao thức định tuyến phải đáp ứng được việc tìm thấy đường đi chính xác và hiệu quả cho gói tin từ nút nguồn đến nút đích. ü Không có lặp định tuyến: Nếu hiện tượng này xảy ra, một số gói tin có thể được chuyển tiếp quay vòng trong mạng một số lần không xác định, dẫn đến việc tiêu tốn các tài nguyên mạng và có thể gây tắc nghẽn mạng. Giải pháp đưa ra là dùng trường TTL (Time To Live) trong mỗi gói tin, giá trị TTL được làm giảm đi một đơn vị khi nút chuyển tiếp gói tin tới một nút mới và khi giảm đến một giá trị quy định nào đó gói tin sẽ bị loại bỏ. ü Vấn đề năng lượng và băng thông của mạng: Do các nút trong mạng MANET có năng lượng bị giới hạn nên khi nghiên cứu các giao thức định tuyến cần xem xét đến việc tiết kiệm năng lượng cho nút khi có thể. Ngoài ra, cần tránh vấn đề lãng phí băng thông 26 ü Hỗ trợ liên kết đơn hướng: Trong trường hợp có một số liên kết đơn hướng (simplex link) giữa một số cặp nút mạng liền kề, giao thức định tuyến cần có khả năng tìm được đường đi theo cả 2 chiều giữa 2 nút mạng. ü Bảo mật: Các giao thức định tuyến mạng MANET có thể bị tấn công nhằm gây ra sự vận hành sai của giao thức ví dụ như thay đổi thông tin cập nhật định tuyến, sửa đổi tiêu đề gói tin…Do đó, việc đảm bảo an toàn cho giao thức định tuyến mạng MANET là cần thiết. 3.2. Các kĩ thuật định tuyến mạng MANET [10] Việc định tuyến là vấn đề cốt lõi trong mạng MANET giúp cho việc phân phối dữ liệu từ nút này tới nút khác. Có rất nhiều tiêu chuẩn khác nhau cho việc thiết kế và phân loại các giao thức định tuyến mạng MANET như thông tin định tuyến nào được trao đổi, khi nào và làm thế nào thông tin định tuyến được trao đổi, khi nào và làm thế nào các tuyến được tính toán…Các kĩ thuật định tuyến mạng MANET có thể chia thành các loại như sau: 3.2.1. Định tuyến chủ động và định tuyến phản ứng lại Chiến lược định tuyến chủ động xác định các tuyến tới nhiều nút trong mạng, vì thế tuyến đường là sẵn sàng mỗi khi cần thiết. Phụ tải phát hiện tuyến là lớn theo chiến lược này vì một nút phải đảm bảo tuyến tới tất cả các nút khác. Chúng tiêu tốn băng thông để định kỳ cập nhật các tuyến. Điều đạt được ở đây là khi có yêu cầu, việc chuyển tiếp gói tin là nhanh hơn theo chiến lược này vì tuyến đã sẵn sàng. Ví dụ về chiến lược này là giao thức định tuyến DSDV. Chiến lược định tuyến phản ứng lại thực hiện xác định các tuyến mỗi khi cần. Vì thế chúng có phụ tải phát hiện tuyến nhỏ hơn. Một nút có yêu cầu truyền gói tin có thể phải đợi phát hiện tuyến. Các ví dụ về chiến lược này bao gồm AODV, DSR... Ngoài định tuyến chủ động và phản ứng lại còn có kĩ thuật khác gọi là làm tràn. Trong kĩ thuật làm tràn, không có tuyến nào được tính toán hay phát hiện. Gói tin được quảng bá tới tất cả các nút trong mạng. Làm tràn là phương pháp định tuyến dễ dàng nhất, tuy nhiên, nó tạo ra lưu lượng khổng lồ. 3.2.2. Định tuyến đơn đường và định tuyến đa đường Có nhiều tiêu chuẩn cho việc so sánh định tuyến đơn đường và định tuyến đa đường trong mạng MANET. Đầu tiên, phụ tải cho việc phát hiện tuyến trong định tuyến đa đường là nhiều hơn so với định tuyến đơn đường. Tuy nhiên, tần suất cho việc phát hiện tuyến là ít hơn trong mạng khi sử dụng định tuyến đa đường vì hệ thống có thể vẫn vận hành thậm chí nếu một hay một vài đường giữa nguồn và đích gặp lỗi. 3.2.3. Định tuyến dựa vào bảng và định tuyến khởi tạo phía nguồn ü Định tuyến dựa vào bảng 27 Với các giao thức định tuyến dựa vào bảng, việc cập nhật thông tin định tuyến được thực hiện bằng cách cập nhật bảng định tuyến tại mỗi nút. Các thay đổi trong cấu trúc mạng được truyền tới toàn bộ mạng bằng các gói tin cập nhật. DSDV và OLSR là hai giao thức thuộc loại định tuyến dựa vào bảng. ü Định tuyến khởi tạo từ nguồn Các giao thức định tuyến thuộc loại định tuyến theo yêu cầu khởi tạo phía nguồn tạo ra các tuyến chỉ khi được chính nút nguồn có yêu cầu gửi đi các gói tin. Khi mà một nút yêu cầu tuyến tới một nút đích xác định, nó khởi tạo quá trình phát hiện tuyến. Trong quá trình này, nút nguồn đặt thông tin mô tả địa chỉ đích trong tiêu đề của gói tin. Bất kỳ nút trung gian nào nhận được yêu cầu sẽ tìm trong bảng định tuyến của nó tuyến có địa chỉ đích như mô tả. Nếu tuyến tới đích là tồn tại, nút trung gian sẽ trả về tuyến này cho nút nguồn và tiến trình kết thúc. Ngược lại, gói tin yêu cầu sẽ được chuyển tiếp tới các hàng xóm và tiếp tục quá trình tìm kiếm tuyến. Một khi tuyến được tìm thấy, nút nguồn sẽ đặt toàn bộ đường đi trong tiêu đề của gói tin dữ liệu, các nút trung gian sẽ chuyển tiếp gói tin theo đường đi trong tiêu đề. Các giao thức định tuyến được phân loại theo cách này bao gồm AODV, DSR, TORA. Hình 9 biểu diễn các giao thức định tuyến mạng MANET thuộc 2 loại hướng bảng và khởi tạo phía nguồn. Hình 9. Định tuyến hướng bảng và khởi tạo phía nguồn theo yêu cầu 3.2.4. Các kĩ thuật khôi phục Vì thông tin định tuyến trong mỗi nút có thể trở nên cũ không sử dụng được, nhiều giao thức cần khôi phục tuyến hoặc có kĩ thuật duy trì tuyến. Rõ ràng là các giao thức định tuyến chủ động không cần kĩ thuật khôi phục tuyến vì chúng phản ứng lại với các thay đổi cấu trúc trong một chu kỳ ngắn. Tuy nhiên, các giao thức theo yêu cầu cần phải loại bỏ các tuyến mà không còn được sử dụng nữa. Các giao thức sau đây có các kĩ thuật khôi phục (tường minh hay không tường minh): ABR, AODV, CBRP, DREAM3 DSR, FORP, WAR và ZRP. 28 3.2.5. Chiến lược lựa chọn tuyến Chiến lược lựa chọn tuyến là khía cạnh quan trọng của giao thức định tuyến mạng MANET. Các chiến lược chính bao gồm: ü Độ mạnh tín hiệu: Lựa chọn tuyến dọc theo kết nối mà có độ mạnh tín hiệu tốt nhất. Chiến lược này được sử dụng chủ yếu trong giao thức định tuyến ABR và SSR. ü Ổn định liên kết: Lựa chọn tuyến dọc theo kết nối mà xuất hiện ổn định nhất trong một chu kỳ thời gian. Chiến lược này được sử dụng bởi giao thức định tuyến DST và FORP. ü Đường đi ngắn nhất/Trạng thái liên kết: Lựa chọn đường đi ngắn nhất theo một số đơn vị đo. Chiến lược này được sử dụng bởi nhiều giao thức định tuyến: CEDAR, DDR, FSR, GSR, HSR, OLSR, và TBRPF. 3.2.6. Cập nhật định kỳ và cập nhật theo sự kiện Các giao thức định tuyến cập nhật theo chu kỳ sẽ thi hành việc cập nhật thông tin định tuyến theo chu kỳ. Các cập nhật theo chu kỳ sẽ làm đơn giản hóa các giao thức định tuyến và bảo đảm sự ổn định của mạng và quan trọng nhất đó là cho phép các nút (mới) học về cấu trúc và trạng thái của mạng. Tuy nhiên, nếu chu kỳ giữa các lần cập nhật mà lớn, thì giao thức định tuyến có thể không thể theo kịp việc cập nhật thông tin. Ngược lại, nếu chu kỳ mà nhỏ thì sẽ có quá nhiều gói tin định tuyến được phân phát làm tiêu tốn băng thông một cách nghiêm trọng. Với giao thức cập nhật theo sự kiện, khi có các sự kiện xảy ra (ví dụ khi có liên kết lỗi hoặc có liên kết mới xuất hiện), gói tin cập nhật sẽ được nút phát hiện ra sự kiện phát quảng bá và trạng thái cập nhật có thể được phân phát tới toàn bộ mạng rất sớm. Vấn đề có thể xảy ra là nếu cấu trúc của mạng thay đổi quá nhanh, có rất nhiều gói tin cập nhật sẽ được phân phát tới toàn bộ mạng và sẽ sử dụng một lượng lớn băng thông có thể gây ra dao động tới các tuyến. 3.2.7. 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 là cùng mức và có cùng chức năng định tuyến. Định tuyến phẳng là đơn giản và hiệu quả cho các mạng nhỏ. Vấn đề xảy ra khi mạng trở nên lớn hơn, dung lượng của thông tin định tuyến sẽ lớn và cần nhiều thời gian để thông tin định tuyến tới được các nút ở xa. Với các mạng lớn, định tuyến phân cấp (dựa trên cụm) có thể được sử dụng để giải quyết vấn đề trên. Trong định tuyến phân cấp, các nút trong mạng được tổ chức động thành các phân hoạch gọi là các cụm và sau đó các cụm được hội tụ lại thành các phân hoạch lớn hơn gọi là siêu cụm…Việc tổ chức mạng thành các cụm giúp cho việc bảo đảm cấu trúc mạng ổn định một cách tương đối. Tính động cao của các nút và cấu trúc mạng bị giới hạn trong các cụm. Chỉ thông tin ổn định và mức cao như mức cụm hay mức siêu cụm sẽ được 29 truyền theo khoảng cách xa vì thế lưu lượng điều khiển (hay phụ tải định tuyến) có thể được giảm nhiều. Dưới đây là các so sánh từ các tiêu chuẩn khác nhau: Giao thức Triết lý định tuyến Tính toán tuyến Cấu trúc Các tuyến Định tuyến nguồn LSR Chủ động Tập trung Phẳng Đơn hoặc đa Không, có thể có DVR Chủ động Phân tán Phẳng Đơn Không DSDV Chủ động Phân tán Phẳng Đơn Không GSR Chủ động Phân tán Phẳng Đơn hoặc đa Không, có thể có FSR Chủ động Phân tán Phân cấp Đơn hoặc đa Không, có thể có CGSR Chủ động Phân tán Phẳng Đơn hoặc đa Không, có thể có WRP Phản ứng lại Phân tán Phẳng Đơn Không DSR Phản ứng lại Quảng bá Phẳng Đa Có AODV Phản ứng lại Quảng bá Phẳng Đa Không TORA Phản ứng lại Quảng bá Phẳng Đa Không ABR Phản ứng lại Quảng bá Phẳng Đơn Có HSR Lai ghép Kế thừa Phân cấp Đơn Không Bảng 1. So sánh giữa các giao thức định tuyến (Phân tích định tính 1) Giao thức Cập nhật Thông tin cập nhật Đích cập nhật LSR Lai Trạng thái liên kết của hàng xóm Tất cả các nút DVR Chu kỳ Vec tơ khoảng cách Hàng xóm DSDV Lai Vec tơ khoảng cách Hàng xóm GSR Chu kỳ Vec tơ khoảng cách Hàng xóm FSR Chu kỳ Trạng thái liên kết Hàng xóm CGSR Chu kỳ Vec tơ khoảng cách Hàng xóm và đầu cụm WRP Lai Vec tơ khoảng cách Hàng xóm DSR Hướng sự kiện Lỗi tuyến Nguồn AODV Hướng sự kiện Lỗi tuyến Nguồn TORA Hướng sự kiện Độ dài của nút Hàng xóm ABR Hướng sự kiện Lỗi tuyến Hàng xóm/Nguồn HSR Trên sự kiện Trạng thái liên kết ảo Các nút trong cụm Bảng 2. So sánh giữa các giao thức định tuyến (Phân tích định tính 2) 3.3. Các giao thức định tuyến chủ yếu trong mạng MANET [8] 3.3.1. Giao thức DSDV (Destination-Sequenced Distance Vector) [4] Giao thức định tuyến DSDV được mô tả trong [4] là giao thức dựa trên bảng khởi nguồn từ kĩ thuật định tuyến cổ điển Bellman-Ford. Các cải tiến từ kĩ thuật định 30 tuyến Bellman-Ford bao gồm việc tránh tạo ra các vòng lặp trong các bảng định tuyến và việc cập nhật định tuyến là đơn giản hơn. Mỗi nút di động trong mạng bảo đảm bảng định tuyến trong đó tất cả các đích đến có thể nằm trong mạng và số lượng các chặng tới mỗi đích đến được ghi lại. Mỗi đầu vào (entry) của bảng định tuyến được đánh dấu với số thứ tự và gán bởi đích đến. Số thứ tự này cho phép các nút di động phân biệt các tuyến cũ so với các tuyến mới và để tránh việc xuất hiện các vòng lặp định tuyến. Việc cập nhật bảng định tuyến được truyền định kỳ thông qua mạng để bảo đảm tính nhất quán của bảng. Để hỗ trợ việc giảm lưu lượng mạng lớn do quá trình cập nhật có thể tạo ra, các cập nhật tuyến có thể thi hành bằng hai kiểu gói tin. Kiểu đầu tiên được biết đến với tên gọi là kết xuất đầy đủ (full dump). Kiểu gói tin này mang tất cả thông tin định tuyến khả dụng. Trong suốt các chu kỳ di chuyển, các gói tin này hiếm khi được truyền. Các gói tin bổ sung (incremental) nhỏ hơn được sử dụng để truyền chỉ các thông tin bị thay đổi kể từ gói tin kết xuất đầy đủ cuối cùng. Mỗi một quảng bá nên thích hợp với kích cỡ chuẩn của NPDU nhờ đó làm giảm lưu lượng phát sinh. Khi nhận được các gói tin cập nhật định tuyến bổ sung, các nút cập nhật bảng định tuyến của nó. Các quảng bá tuyến mới chứa địa chỉ của nguồn, đích, số lượng các chặng tới đích đến, số thứ tự của thông tin nhận được đối với đích tương ứng, cũng như số thứ tự mới duy nhất đối với việc quảng bá. Tuyến được gán nhãn với số thứ tự gần đây nhất được sử dụng. Trong trường hợp có hai cập nhật có cùng số thứ tự, tuyến với độ đo nhỏ hơn được sử dụng cho việc tối ưu (làm ngắn) đường đi. Các nút di động cũng giữ thời điểm thiết lập của các tuyến hoặc thời điểm trung bình được đánh trọng số mà các tuyến tới đích sẽ dao động trước khi tuyến với độ đo tốt nhất được nhận. Bằng việc làm trễ việc quảng bá của cập nhật tuyến bằng độ dài của thời điểm thiết lập, các nút đi động có thể giảm lưu lượng mạng và tối ưu các tuyến bằng việc giới hạn các quảng bá mà có thể xảy ra nếu tuyến tốt hơn được phát hiện trong tương lai rất gần. 3.3.2. Giao thức CGSR (Clusterhead Gateway Switch Routing) [5] Trong giao thức CGSR, các nút di động được nhóm thành các cụm và mỗi cụm có một cụm trưởng [5]. Thuật toán phân tán trong cụm được sử dụng để lựa chọn cụm trưởng cho cụm. Nhược điểm của chiến lược cụm trưởng đó là việc thay đổi cụm trưởng thường xuyên có thể ảnh hưởng lớn tới hiệu năng giao thức định tuyến vì các nút bận rộn trong việc lựa chọn cụm trưởng hơn là việc truyền các gói tin. Vì thế, thay vì sử dụng việc lựa chọn lại cụm trưởng mỗi khi có sự thay đổi các cụm, người ta sử dụng thuật toán thay đổi cụm trưởng ít nhất LCC (Least Cluster Change). Sử dụng LCC, các cụm trưởng chỉ thay đổi khi hai cụm trưởng liên hệ hoặc khi nút di chuyển ra ngoài vùng tiếp xúc của tất cả các cụm trưởng khác. CGSR sử dụng DSDV như là chiến lược định tuyến bên dưới và vì thế cũng chịu cùng mức phụ tải như DSDV. Tuy nhiên, nó sửa đổi DSDV bằng cách sử dụng cách tiếp cận định tuyến cụm trưởng tới nút cổng phân cấp để định tuyến gói tin từ 31 nguồn tới đích. Các nút ở cổng (gateway) là các nút nằm trong phạm vi truyền thông của hai hoặc nhiều hơn các cụm trưởng. Đầu tiên, gói tin được gửi bởi một nút sẽ được định tuyến tới cụm trưởng của nó, và sau đó gói tin được định tuyến từ cụm trưởng tới nút cổng rồi tới cụm trưởng khác và cứ như thế tới cụm trưởng của nút đích mong muốn. Gói tin sau cùng được truyền tới đích. Hình 10. Định tuyến CGSR từ nút 1 đến nút 8 Hình 10 minh họa ví dụ về chiến lược định tuyến này. Sử dụng phương pháp này, mỗi nút phải giữ “bảng các thành viên cụm” trong đó lưu trữ cụm trưởng đích của mỗi nút di động trên mạng. Các bảng thành viên cụm này được quảng bá bởi mỗi nút một cách định kỳ bằng cách sử dụng giao thức DSDV. Các nút cập nhật các bảng thành viên cụm của chúng khi nhận được thông tin từ hàng xóm. Ngoài việc sử dụng bảng thành viên cụm, mỗi nút phải bảo đảm bảng định tuyến được sử dụng để xác định chặng kế tiếp để tới được đích. Khi nhận được một gói tin, nút sẽ thăm dò bảng thành viên cụm của nó và bảng định tuyến để xác định cụm trưởng gần nhất dọc theo tuyến tới đích. Kế đến, nút sẽ kiểm tra bảng định tuyến của nó để xác định chặng kế tiếp được sử dụng để tìm được cụm trưởng được lựa chọn kế tiếp. Sau đó nó sẽ truyền gói tin tới nút đó. 3.3.3. Giao thức WRP (Wireless Routing Protocol) [14] WRP được mô tả trong [14] là giao thức định tuyến dựa trên bảng. Giao thức WRP đảm bảo thông tin định tuyến giữa tất cả các nút trong mạng bằng cách thực thi 4 bảng sau tại mỗi nút di động: ü Bảng khoảng cách (Distance table) ü Bảng định tuyến (Routing table) ü Bảng chi phí liên kết (Link-cost table) ü Bảng danh sách truyền lại thông điệp MRL (Message Retransmission List table) Mỗi đầu vào (entry) của MRL chứa số thứ tự của thông điệp cập nhật, bộ đếm truyền lại, vec-tơ cờ yêu cầu biên nhận đối với mỗi hàng xóm, danh sách các cập nhật được gửi trong thông điệp cập nhật. Các bản ghi MRL có các cập nhật trong thông điệp cập nhật cần được truyền lại và các hàng xóm nên biên nhận việc truyền này. 32 Nút di động thông báo cho những nút khác các thay đổi liên kết thông qua việc sử dụng thông điệp cập nhật. Thông điệp này chỉ được gửi giữa các nút hàng xóm và chứa danh sách các cập nhật (địa chỉ đích, khoảng cách tới đích và nút đứng trước đích) cũng như danh sách các phản hồi cho biết nút di động nên biên nhận các cập nhật. Nút di động sẽ gửi thông điệp cập nhật tới các nút hàng xóm khi phát hiện thấy lỗi liên kết xảy ra. Các nút hàng xóm sau đó sẽ sửa đổi các đầu vào (entry) của bảng khoảng cách và tiến hành kiểm tra các đường dẫn mới đi qua các nút khác. Đường dẫn mới nào được truyền trở lại nút gốc để nút gốc có thể cập nhật các bảng tương ứng. Nút di động học về sự tồn tại của các nút hàng xóm từ việc nhận các biên nhận và các thông điệp khác. Nếu nút di động không có nhu cầu gửi dữ liệu, nó vẫn phải gửi thông điệp hello trong một khoảng chu kỳ thời gian xác định để bảo đảm vẫn còn kết nối. Mặt khác, việc thiếu vắng các thông điệp từ nút cho biết có lỗi liên kết đang xảy ra. Khi nút di động nhận được thông điệp hello từ một nút mới, thông tin về nút mới sẽ được thêm vào bảng định tuyến của nút di động và sau đó nó gửi cho nút mới bản sao về thông tin bảng định tuyến của nó. 3.3.4. Giao thức OLSR (Optimized Link State Routing) [16] Giao thức định tuyến OLSR kế thừa sự ổn định của giao thức trạng thái liên kết. Ưu điểm chính của OLSR là có các tuyến khả dụng ngay lập tức mỗi khi cần. Giao thức OLSR là sự tối ưu của giao thức trạng thái liên kết thuần túy cho mạng MANET. Cụ thể nó giảm kích cỡ của các gói tin điều khiển bằng cách khai báo chỉ một tập các nút chuyển phát trong số các nút hàng xóm, đó là MRP (Multipoint Relay Selectors). Chỉ có các nút chuyển phát của nút mới truyền lại các thông điệp quảng bá của nút. Kĩ thuật này làm giảm đáng kể số lần truyền lại trong thủ tục phát tràn và quảng bá. Giao thức định tuyến OLSR sử dụng hai thông điệp điểu khiển là thông điệp HELLO và thông điệp điều khiển tô-pô mạng TC (Topology Control). Thông điệp HELLO được sử dụng để xây dựng lên tập MRP và được phát định kỳ một chặng để cảm nhận trạng thái liên kết với các hàng xóm. Để quảng bá tập MRP, nút sử dụng thông điệp TC. Các nút nhận được thông điệp TC sẽ phân tích và lưu các cặp kết nối theo dạng [chặng cuối, nút] trong đó “nút” là các địa chỉ được tìm thấy trong danh sách thông điệp TC. Bảng định tuyến được xây dựng từ cơ sở dữ liệu này bằng cách truy vết các cặp kết nối theo trật tự giảm dần. Để tìm được đường từ nút ban đầu cho trước tới một nút ở xa là R, đầu tiên sẽ tìm cặp kết nối (X, R), trong đó X là một nút hàng xóm của R, sau đó là cặp (Y, X), trong đó Y là một nút hàng xóm của X và cứ như thế cho đến khi tìm được một nút Y nằm trong tập hàng xóm của nút ban đầu. Để chọn được đường dẫn tối ưu, các nút chuyển tiếp sẽ chỉ lựa chọn các cặp kết nối có đường đi nhỏ nhất. Giao thức định tuyến OLSR giữ các tuyến cho tất cả các đích có trong mạng, vì thế nó phù hợp cho các mẫu lưu lượng trong đó có một tập lớn các nút truyền thông với nhau và các cặp [nguồn, đích] thay đổi theo thời gian. Giao thức thích hợp đặc biệt 33 cho các mạng lớn và dày đặc bởi việc tối ưu sử dụng các chuyển tiếp đa điểm thực hiện tốt trong ngữ cảnh này. Mạng càng lớn và dày đặc thì việc tối ưu đạt được càng tốt. 3.3.5. Giao thức AODV (Ad Hoc On-Demand Distance Vector) [3] Giao thức định tuyến AODV được mô tả trong [3] được xây dựng từ giao thức định tuyến DSDV được mô tả ở phần trên. Khác với DSDV luôn lưu trữ một danh sách các tuyến đường hoàn chỉnh, AODV chỉ tạo ra các tuyến đường khi có yêu cầu. Khi mà nút nguồn cần gửi thông điệp tới nút đích nhưng chưa có sẵn tuyến hợp lệ tới đích, nó khởi tạo tiến trình phát hiện đường đi để định vị đường tới nút đích. Nút nguồn quảng bá gói tin yêu cầu tuyến RREQ (Route Request) tới các hàng xóm của nó và sau đó các hàng xóm sẽ chuyển tiếp yêu cầu tới các hàng xóm khác và cứ như thế cho đến khi gặp đích đến hoặc gặp nút trung gian có tuyến “đủ mới” tới đích. Hình 11a minh họa việc truyền các gói tin RREQ quảng bá vào mạng. Hình 11. Phát hiện tuyến trong AODV AODV sử dụng số thứ tự của đích đến để bảo đảm tất cả các tuyến là không có vòng lặp và chứa đựng các thông tin tuyến gần đây nhất. Mỗi nút bảo đảm số thứ tự của nó cũng như định danh của các gói tin phát quảng bá. Định danh quảng bá được tăng cho mỗi gói tin RREQ mà nút khởi tạo. Cùng với địa chỉ IP của nút, định danh gói tin RREQ là duy nhất. Ngoài số thứ tự và định danh quảng bá, nút nguồn còn bao gồm trong gói tin RREQ thông tin về số thứ tự gần đây nhất mà nó có đối với đích. 34 Các nút trung gian có thể trả lời RREQ chỉ khi chúng có tuyến tới đích tương ứng với số thứ tự địa chỉ đích lớn hơn hoặc bằng số thứ tự trong gói tin RREQ, nghĩa là chúng có thông tin mới hơn về tuyến tới đích. Trong suốt quá trình chuyển tiếp gói tin RREQ, nút trung gian khởi tạo đường quay trở về nguồn tạm thời. Ngoài ra, nút trung gian cũng lưu lại định danh của các gói tin RREQ đã nhận để loại bỏ các RREQ trùng lặp. Một khi gói tin RREQ đến được đích hoặc đến được nút trung gian với tuyến đủ mới, nút đích/nút trung gian phản hồi bằng cách truyền gói tin phản hồi tuyến RREP (Route Reply) ngược trở lại cho nút hàng xóm mà nó nhận được RREQ lần đầu tiên (Hình 11b). Vì RREP được định tuyến quay trở lại dọc theo đường mà gói tin RREQ đã đi nhưng theo chiều ngược lại, các nút dọc theo đường dẫn thiết lập các đầu vào tuyến chuyển tiếp trong bảng định tuyến của chúng trỏ tới nút có gói tin RREP đến. Các đầu vào tuyến chuyển tiếp này cho biết tuyến chuyển tiếp có còn hoạt động hay không. Mỗi đầu vào tuyến có một trường định thời, nút mạng dựa vào trường định thời để quyết định xóa đầu vào nếu nó thấy tuyến tương ứng không còn được sử dụng trong một chu kỳ thời gian xác định. Bởi vì gói tin RREP được chuyển tiếp dọc theo đường dẫn được thiết lập bởi gói tin RREQ, AODV chỉ hỗ trợ việc sử dụng các liên kết đối xứng (full duplex). Các tuyến được bảo đảm như sau. Nếu mà nút nguồn di chuyển, nó có thể khởi tạo lại giao thức phát hiện tuyến để tìm ra tuyến mới tới đích. Nếu nút dọc theo tuyến di chuyển, hàng xóm ở hướng nút nguồn sẽ thông báo về di chuyển và truyền đi thông điệp thông báo lỗi liên kết tới mỗi hàng xóm mà hướng về nút nguồn để xóa khỏi phần của tuyến, công việc này được tiếp diễn cho tới khi tới được nút nguồn. Nút nguồn sau đó có thể chọn để khởi tạo lại việc phát hiện tuyến cho mỗi đích nếu tuyến vẫn còn được yêu cầu sử dụng. Một khía cạnh khác của giao thức định tuyến AODV là việc sử dụng các thông điệp hello, được quảng bá cục bộ định kỳ bởi nút để thông báo với các nút di động hàng xóm. Các thông điệp hello có thể được sử dụng để đảm bảo kết nối cục bộ của nút. Tuy nhiên, việc sử dụng các thông điệp hello là không bắt buộc. Các nút lắng nghe việc truyền lại của các gói tin dữ liệu để đảm bảo rằng chặng tiếp theo vẫn có thể tới được. Nếu không nghe thấy việc truyền lại, nút có thể sử dụng bất kỳ kĩ thuật nào, bao gồm cả việc nhận các thông điệp hello, để xác định xem chặng tiếp theo nào nằm trong phạm vi truyền thông của nó. 3.3.6. Giao thức DSR (Dynamic Source Routing) [6] Giao thức DSR được mô tả trong [6] là giao thức định tuyến theo yêu cầu dựa trên khái niệm về định tuyến nguồn. Các nút di động được yêu cầu bảo đảm bộ đệm tuyến chứa các tuyến nguồn mà nút di động biết đến. Các đầu vào trong bộ đệm tuyến được cập nhật liên tục khi có các tuyến mới được biết. Giao thức bao gồm hai giai đoạn chính: phát hiện tuyến và bảo đảm tuyến. Khi nút di động có gói tin cần gửi tới các đích, đầu tiên nó thăm dò bộ đệm tuyến của nó 35 để xác định xem đã có sẵn tuyến tới đích chưa. Nếu nó thấy có tuyến để gửi tới đích và chưa hết hạn, nó sẽ sử dụng tuyến này để gửi gói tin. Ngược lại, nếu nút không có tuyến, nó sẽ khởi tạo việc phát hiện tuyến bằng cách quảng bá gói tin yêu cầu tuyến RREQ (Route Request). Yêu cầu tuyến này chứa địa chỉ của nút đích, cùng với địa chỉ của nút nguồn và số định danh duy nhất. Mỗi nút nhận được gói tin sẽ kiểm tra xem nó có biết tuyến tới đích hay không. Nếu nút không biết, nó sẽ thêm địa chỉ của nó vào bản ghi tuyến của gói tin và chuyển tiếp gói tin dọc theo các liên kết ra ngoài. Để giới hạn số lượng các yêu cầu tuyến được truyền ra các liên kết ngoài của nút, nút di động chỉ chuyển tiếp yêu cầu tuyến nếu yêu cầu chưa từng được nhìn thấy bởi nút di động và địa chỉ của nút di động không có trong bản ghi tuyến. Phản hồi tuyến RREP (Route Reply) được tạo ra khi yêu cầu tuyến tới được đích của nó hoặc tới nút trung gian chứa bộ đệm tuyến trong đó có tuyến đến đích theo yêu cầu và chưa hết hạn. Theo thời gian, gói tin tới được đích hoặc nút trung gian, nó chứa đựng bản ghi tuyến bao gồm một dãy các chặng đã đi qua. Hình 12. Tạo ra các bản ghi tuyến trong DSR Hình 12a minh họa định dạng của bản ghi tuyến khi yêu cầu tuyến được truyền qua mạng. Nếu nút tạo ra phản hồi tuyến là nút đích, nó đặt bản ghi tuyến mà chứa trong yêu cầu tuyến vào gói tin phản hồi tuyến. Nếu nút phản hồi là nút trung gian, nó sẽ gắn thêm bộ đệm tuyến của nó vào bản ghi tuyến và sau đó tạo ra phản hồi tuyến. Để trả về phản hồi tuyến, nút phản hồi phải có tuyến tới nút khởi tạo. Nếu nó có tuyến tới nút khởi tạo trong bộ đệm tuyến của nó, nó có thể sử dụng tuyến này. Mặt khác, 36 nếu các liên kết đối xứng được hỗ trợ, nút có thể gửi gói tin RREP đi ngược lại tuyến trong bản ghi tuyến. Nếu các liên kết đối xứng không được hỗ trợ, nút có thể khởi tạo quá trình phát hiện tuyến của nó và lắp ngược phản hồi tuyến vào yêu cầu tuyến mới. Hình 12b chỉ ra việc truyền của phản hồi tuyến với việc gắn kết bản ghi tuyến ngược trở lại nút nguồn. Việc bảo đảm tuyến được thực hiện thông qua việc sử dụng các gói tin báo lỗi tuyến và các biên nhận. Các gói tin lỗi tuyến được tạo ra tại mỗi nút khi mà tầng liên kết dữ liệu bắt gặp lỗi truyền nghiêm trọng. Khi một nút nhận được gói tin lỗi tuyến, chặng có lỗi được loại bỏ khỏi bộ đệm tuyến và tất cả các tuyến chứa chặng này được cắt cụt tại điểm này. Ngoài các thông điệp lỗi tuyến, các thông điệp biên nhận được sử dụng để biên nhận sự vận hành đúng của các liên kết tuyến. Các thông điệp biên nhận bao gồm các biên nhận thụ động trong đó nút di dộng có khả năng nghe ngóng chặng kế tiếp chuyển tiếp gói tin dọc theo tuyến. 3.3.7. Giao thức TORA (Temporally-Ordered Routing Algorithm) [11] Hình 13. Việc tạo tuyến và đảm bảo tuyến trong TORA TORA là giao thức định tuyến phân tán không có lặp tuyến thích nghi cao dựa trên khái niệm về đảo ngược liên kết. TORA được đề xuất để vận hành trong môi 37 trường mạng di động thay đổi nhanh. Nó được khởi tạo phía nguồn và cung cấp nhiều tuyến cho bất kỳ cặp nguồn/đích mong muốn nào. Khái niệm thiết kế chính của TORA là định vị các thông điệp điều khiển tới một tập các nút rất nhỏ gần nơi xảy ra việc thay đổi cấu trúc. Để làm được điều này, các nút cần bảo đảm thông tin định tuyến về các nút kề cận (một chặng). Giao thức TORA thi hành ba chức năng cơ bản: ü Tạo tuyến ü Bảo đảm tuyến ü Xóa tuyến Trong suốt giai đoạn tạo và bảo đảm tuyến, các nút sử dụng đơn vị đo “độ cao” để thiết lập đồ thị không chu trình có hướng DAG (Directed Acyclic Graph) có gốc tại đích đến. Sau đó, các liên kết được gán hướng (luồng lên hoặc xuống) dựa trên đơn vị đo độ cao tương đối của các nút hàng xóm như trong hình 13a. Trong hình vẽ, trục đứng thể hiện cho độ cao, các thông điệp trong mạng đi theo chiều từ nút có độ cao lớn hơn đến nút có độ cao nhỏ hơn giống kiểu thác nước chảy từ trên xuống. Thời gian là yếu tố quan trọng trong giao thức TORA bởi vì đơn vị đo “độ cao” phụ thuộc vào thời điểm logic của lỗi liên kết. TORA giả thuyết rằng tất cả các nút mạng đều có đồng hồ đồng bộ (có thể đạt được thông qua nguồn thời gian ngoài như GPS). Độ đo của TORA là sự tổng hợp của 5 yếu tố bao gồm thời điểm lôgic của lỗi liên kết, định danh duy nhất của nút xác định giá trị độ cao mới, bit chỉ số phản xạ, tham số của đường truyền và định danh duy nhất của nút [8]. Đường đi trong mạng được phát hiện bằng hai gói tin là QUERY và UPDATE. Khi nút có nhu cầu gửi gói tin tới đích bất kỳ, nó sẽ gửi quảng bá gói tin truy vấn QUERY. Gói tin này được các nút trung gian truyền trong mạng cho tới khi tới đích hoặc nút trung gian có đường đi tới đích. Nút trả lời sẽ gửi trả lại gói tin UPDATE chứa độ cao của nút đó. Các nút nhận được gói tin UPDATE sẽ thiết lập độ cao lớn hơn độ cao trong gói tin UPDATE và quảng bá gói tin UPDATE của nó. Kết quả nút nguồn sẽ có đường đi tới nút đích theo đường có độ cao giảm dần. Do tính di động của các nút, tuyến DAG bị phá vỡ và việc bảo đảm tuyến là cần thiết để thiết lập lại đồ thị DAG có gốc ở cùng nút đích. Như đã chỉ ra trong hình 13b, khi mà lỗi của liên kết luồng xuống cuối cùng xảy ra, nút hiệu chỉnh độ cao của nó là cao nhất so với các hàng xóm của nó và truyền quảng bá gói tin UPDATE với độ cao mới tới các nút hàng xóm nhằm phản ứng với lỗi. Các liên kết được đảo ngược phản hồi với thay đổi để thích nghi với độ cao mới. Điều này có cùng tác động do hướng đảo ngược của một hay nhiều liên kết khi nút không có các liên kết luồng xuống. Giai đoạn xóa tuyến của TORA bao gồm chủ yếu việc quảng bá gói tin xóa CLR (Clear Packet) thông qua mạng để xóa các tuyến không hợp lệ. Gói tin CLR bao gồm độ cao và định danh đích. Khi một nút nhận được gói tin CLR và độ cao của nó khớp với độ cao trong CLR, nó thiết lập tất cả độ cao cho các hàng xóm và bản thân nó đối với đích giá trị null và quảng bá tiếp gói tin CLR. Ngược lại, nếu không khớp, nó chỉ thiết lập độ cao cho các hàng xóm đối với đích giá trị null. 38 3.3.8. Giao thức ABR (Associativity-Based Routing) [2] Giao thức ABR được đề xuất và phát triển bởi C.K. Toh năm 1996. Nó là giao thức định tuyến khởi tạo phía nguồn, nghĩa là không cần các cập nhật định tuyến theo chu kỳ. ABR lựa chọn các tuyến dựa trên sự ổn định theo thời gian (Temporal Stability) của các liên kết giữa các nút. Giao thức ABR sử dụng gói tin beacon để báo hiệu sự tồn tại của mỗi nút với các nút hàng xóm. Các gói tin beacon này dùng để cập nhật bảng liên kết của mỗi nút. Sử dụng bảng ổn định theo thời gian và bảng liên kết, nút có thể chia các liên kết với hàng xóm thành hai kiểu: ổn định và không ổn định. Hoạt động của giao thức ABR bao gồm 3 giai đoạn: Phát hiện tuyến Nếu nút nguồn có tuyến tới nút đích trong bộ đệm tuyến RC (Route Cache) của nó, tuyến này sẽ được sử dụng ngay lập tức. Nếu không, quá trình phát hiện tuyến RD (Route Discovery) được khởi tạo như sau: ü Phát tràn các thông điệp RREQ (Route Request) vào mạng. Các thông điệp này chỉ được chuyển tiếp bởi các nút trung gian, giống như trong DSR. Khi nút trung gian nhận được thông điệp RREQ, nó gắn địa chỉ và đánh dấu liên kết (Associativity Tick) của nó vào gói tin. ü Khi thông điệp RREQ tới được đích, nút đích sẽ đợi một thời gian trước khi lựa chọn tuyến tốt nhất bằng cách kiểm tra liên kết dọc theo mỗi đường dẫn. Nếu nhiều tuyến có cùng mức độ ổn định, tuyến với số chặng ít nhất được lựa chọn. ü Khi nút đích lựa chọn xong tuyến, nó gửi gói tin phản hồi ngược trở lại nguồn dọc theo cùng đường dẫn. Hình 14. Lựa chọn tuyến trong ABR Trong hình 14 có 3 tuyến có thể từ 1-12: 1-5-7-9-12, 1-2-4-8-10-12, 1-2-4-8- 11-12 nhưng ABR chỉ lựa chọn tuyến 3 bởi phần trăm các liên kết ổn định theo tuyến này là cao nhất. 39 Sửa/Xây dựng lại tuyến Trường hợp 1: Liên kết bị lỗi. Liên kết lỗi được phát hiện bởi tất cả các nút hàng xóm nhờ các gói tin beacon. Nút gần liên kết bị lỗi nhất ở hướng nguồn sẽ khởi tạo quá trình sửa tuyến cục bộ. Đầu tiên nút sẽ quảng bá gói tin RouteRepair (truy vấn cục bộ LQ) tới các hàng xóm của nó. Nếu liên kết lỗi có thể được khắc phục cục bộ, nút nguồn sẽ không cần phát tràn lại truy vấn quảng bá mới. Nếu nút hiện tại không thể sửa được liên kết lỗi, nút kế tiếp hướng về nguồn (nút luồng lên) sẽ khởi tạo lại quảng bá truy vấn cục bộ. Quá trình này diễn ra cho đến khi nút ở trung tâm đường đi lỗi không thể sửa được. Sau đó, nút nguồn được thông báo bắt đầu một quá trình phát hiện tuyến mới mới Hình 15. Xây dựng lại tuyến trong ABR Trong hình 15, đường đi 8-11-12 gặp lỗi. Nút 8 khởi tạo quảng bá cục bộ và kết quả cuối cùng tìm được đường dẫn mới là 8-10-12. Trong trường hợp có 2 nút liên tiếp phát hiện thấy liên kết bị lỗi chẳng hạn là 4-8 và 8-11, đường dẫn mới có thể sử dụng là 1-5-7-9-12. Trường hợp 2: Nút đích di chuyển ra ngoài phạm vi của nút cuối cùng trước đích. Đầu tiên nút cuối cùng trước đích xóa tuyến của nó. Sau đó quá trình LQ được khởi tạo để kiểm tra xem nút vẫn có thể tới được hay không. Nếu đích đến không thể tới được, nó lựa chọn tuyến con tốt nhất và phản hồi lại. Mặt khác, quá trình LQ được chuyển tiếp tới nút luồng lên kế cận. Thông tiệp RN (Route Notification) được gửi tới nút luồng lên kế cận để xóa tuyến không hợp lệ và thông báo cho nút này là nó nên khởi tạo quá trình LQ. Nếu việc quay lui này chiếm hơn nửa đường đi tới nguồn, quá trình LQ sẽ dừng lại và nút nguồn khởi tạo tiến trình truy vấn quảng bá mới. Xóa tuyến 40 Nếu tuyến được phát hiện không cần sử dụng nữa, nút nguồn khởi tạo gói tin quảng bá xóa tuyến RD (Route Delete). Tất cả các nút dọc theo tuyến sẽ xóa đầu vào tuyến từ danh sách định tuyến của chúng. Thông điệp RD được quảng bá đầy đủ vì nút nguồn không biết bất kỳ sự thay đổi đường dẫn nào trong suốt quá trình xây dựng lại tuyến. 3.3.9. Giao thức SSR (Signal Stability Routing) [14] Một giao thức theo yêu cầu khác là SSR được mô tả trong [14]. Không giống như các giao thức đã được mô tả ở trên, SSR lựa chọn các tuyến dựa trên độ mạnh của tín hiệu giữa các nút và sự ổn định vị trí của nút. SSR có thể được chia thành 2 giao thức cộng tác: Giao thức định tuyến động DRP (Dynamic Routing Protocol) và giao thức định tuyến tĩnh SRP (Static Routing Protocol). DRP chịu trách nhiệm cho việc đảm bảo bảng ổn định tín hiệu SST (Signal Stability Table) và bảng định tuyến RT (Routing Table). SST lưu trữ độ mạnh tín hiệu của các nút hàng xóm, đạt được theo chu kỳ bởi các gói tin beacon từ tầng liên kết của mỗi nút hàng xóm. Độ mạnh tín hiệu có thể được ghi như là kênh mạnh hay yếu. Sau khi cập nhật tất cả các đầu vào bảng thích hợp, DRP chuyển gói tin nhận được cho SRP. SRP sẽ tìm kiếm đích đến trong RT. Nếu không tìm thấy đích đến, tiến trình tìm kiếm tuyến được khởi tạo. Các gói tin yêu cầu tuyến được truyền qua mạng với điều kiện qua các kênh mạnh và chưa được xử lý trước đó (để ngăn chặn việc hình thành các vòng lặp). Đích đến lựa chọn gói tin yêu cầu tuyến đến đầu tiên để gửi phản hồi bởi đó là gói tin đến được qua đường đi có mức độ tắc nghẽn ít nhất hoặc đó là đường đi ngắn nhất. Gói tin phản hồi được gửi trở lại nút khởi tạo theo tuyến được lựa chọn. DRP của các nút dọc theo đường dẫn cập nhật bảng RT tương ứng. Các gói tin tìm kiếm tuyến đến đích theo đường đi có sự ổn định tín hiệu tốt nhất bởi chúng sẽ bị loại bỏ nếu qua các kênh yếu. Nếu không nhận được thông điệp phản hồi tuyến trong một khoảng thời gian hết hạn xác định, nút nguồn thay đổi trường PREF trong tiêu đề để cho biết rằng các kênh yếu là có thể được chấp nhận. Khi có lỗi liên kết được phát hiện xảy ra trong mạng, các nút trung gian gửi thông điệp lỗi tới nút nguồn cho biết kênh đã gặp lỗi. Nút nguồn sẽ khởi tạo một tiến trình tìm kiếm tuyến khác để tìm đường đi mới tới đích. Nút nguồn cũng gửi thông điệp xóa để thông báo cho tất cả các nút biết việc liên kết bị hỏng. 3.3.10. So sánh các giao thức định tuyến chủ yếu trong mạng MANET [3]- [8] Mục dưới đây đưa ra các so sánh cho các thuật toán định tuyến được trình bày ở trên. Đầu tiên là sự so sánh của các giao thức hướng bảng và sau đó là sự so sánh của các giao thức theo yêu cầu. Trong bảng 3 và bảng 4 thì độ phức tạp thời gian được định nghĩa là số các bước cần thiết để thực thi việc vận hành giao thức và độ phức tạp 41 truyền thông là số lượng các thông báo cần thiết để thực thi việc vận hành giao thức. Giá trị của các đơn vị đo này biểu diễn trong trường hợp xấu nhất. Đầu tiên chúng ta sẽ thảo luận về các giao thức hướng bảng được mô tả trong bảng 3. Định tuyến DSDV về cơ bản là việc sửa đổi thuật toán định tuyến Bellman- Ford. Các sửa đổi bao gồm việc đảm bảo các tuyến không có các vòng lặp và việc cập nhật tuyến là đơn giản. Trong khi chỉ cung cấp một đường đi tới một đích bất kỳ, DSDV lựa chọn đường đi ngắn nhất dựa trên độ đo là số lượng chặng tới đích. DSDV cung cấp hai kiểu gói tin thông báo cập nhật, trong đó có một kiểu gói tin thông báo nhỏ hơn đáng kể so với gói tin thông báo còn lại. Việc cập nhật bằng gói tin thông báo nhỏ có thể được sử dụng cho các cập nhật bổ sung nhờ đó toàn bộ bảng định tuyến không cần truyền mỗi khi có thay đổi của cấu trúc mạng. Tuy nhiên, DSDV là không hiệu quả do có các truyền thông cập nhật theo chu kỳ, bất chấp số lượng các thay đổi trong cấu trúc mạng. Điều này giới hạn mạnh tới số lượng các nút có thể kết nối vào mạng vì phụ tải tăng theo số nút mạng có bậc là O(n2). Các tham số DSDV CGSR WRP OLSR Độ phức tạp thời gian (thêm/lỗi liên kết) O(d) O(d) O(h) O(d) Độ phức tạp truyền thông (thêm/lỗi liên kết) O(x = N) O(x = N) O(x = N) O(x = N) Có vòng lặp Không Không Không Không Tuyến đến đích sẵn có Có Có Có Có Tần số các truyền thông cập nhật Chu kỳ và khi cần Chu kỳ Chu kỳ và khi cần Chu kỳ và khi cần Các cập nhật được truyền đi Các hàng xóm Các hàng xóm và cụm trưởng Các hàng xóm MRP Tóm tắt: N = Số lượng nút trong mạng d = Đường kính mạng h = Độ cao của cây định tuyến x = Số lượng các nút bị ảnh hưởng bởi sự thay đổi cấu trúc Bảng 3. So sánh đặc tính của các giao thức định tuyến hướng bảng Trong CGSR, DSDV được sử dụng như là giao thức ở bên dưới. Định tuyến trong CGSR xảy ra trên các cụm trưởng và nút cổng. Ngoài bảng định tuyến thì bảng cụm trưởng là cần thiết. Ưu điểm của CGSR là các phương thức kinh nghiệm có thể được thi hành để cải tiến hiệu năng của giao thức. Các phương thức này bao gồm việc điều phối thẻ bài ưu tiên, điều phối mã nút cổng và đảo ngược đường đi. Giao thức WRP yêu cầu mỗi nút bảo đảm bốn bảng định tuyến. Điều này có thể dẫn tới các yêu cầu bộ nhớ đáng kể, đặc biệt khi số lượng các nút trong mạng là lớn. Trong giao thức WRP, các nút định kỳ truyền các thông điệp hello để đảm bảo vẫn còn 42 kết nối do đó hầu như không cho phép nút vào chế độ nghỉ. Tuy nhiên, mặc dù phụ thuộc vào lớp các thuật toán tìm kiếm đường đi, WRP có ưu điểm là tránh được các vấn đề tạo các vòng lặp định tuyến thông qua việc biên nhận thông tin của nút ngay trước đó. Giao thức OLSR giảm kích cỡ các gói tin điều khiển bằng cách khai báo chỉ một tập các chuyển phát đa điểm với các hàng xóm là MRP. Giao thức định tuyến OLSR giữ các tuyến cho tất cả các đích có trong mạng, vì thế nó phù hợp cho các mẫu lưu lượng trong đó có một tập lớn các nút truyền thông với nhau và các cặp [nguồn, đích] thay đổi theo thời gian. Các thảo luận về sự vận hành và các đặc tính của mỗi giao thức hướng bảng trình bày ở trên nhằm mục đích tập trung vào sự khác nhau của chúng. Trong suốt quá trình có các liên kết lỗi, WRP có độ phức tạp thời gian thấp hơn DSDV vì nó chỉ thông báo cho các nút hàng xóm về sự thay đổi trạng thái liên kết. Trong suốt quá trình thêm liên kết, các thông điệp hello được sử dụng để cho biết sự hiện diện của liên kết nhờ đó đầu vào bảng định tuyến có thể được cập nhật. Tương tự, điều này cũng xảy ra với các nút hàng xóm. Trong CGSR, bởi vì hiệu năng định tuyến là độc lập với trạng thái của nút xác định (cụm trưởng, nút cổng và các nút thường) nên độ phức tạp thời gian của lỗi liên kết kết hợp với cụm trưởng là cao hơn trong DSDV bởi phải cộng thêm thời gian để chọn lại cụm trưởng. Tương tự, điều này áp dụng cho trường hợp thêm liên kết kết hợp với cụm trưởng. Nếu nút cổng di chuyển ra ngoài phạm vi, giao thức định tuyến chịu trách nhiệm cho việc định tuyến gói tin tới nút cổng khác. Trong thuật ngữ độ phức tạp truyền thông ta thấy DSDV, CGSR, WRP và OLSR sử dụng định tuyến đường đi ngắn nhất vectơ khoảng cách như là giao thức định tuyến ở bên dưới, tất cả chúng đều có cùng mức độ phức tạp trong suốt quá trình lỗi và thêm liên kết. Bảng 4 mô tả sự so sánh của AODV, DSR, TORA, ABR và SSR. Giao thức định tuyến AODV thi hành thủ tục phát hiện tuyến tương tự như DSR, tuy nhiên, có một vài khác biệt quan trọng. Đáng chú ý nhất là phụ tải bộ nhớ trong DSR lớn hơn so với AODV bởi vì nhu cầu nhớ các tuyến đầy đủ, đối lập với việc chỉ lưu thông tin chặng kế tiếp trong AODV. Về phía luồng xuống, AODV yêu cầu các liên kết đối xứng giữa các nút và vì thế không thể sử dụng các tuyến với các liên kết không đối xứng. Về khía cạnh này thì DSR tốt hơn vì chúng không yêu cầu việc sử dụng các liên kết dạng này và có thể sử dụng các liên kết không đối xứng khi các liên kết đối xứng không khả dụng. Giao thức DSR được dự định cho các mạng trong đó các nút di động di chuyển ở tốc độ trung bình liên quan đến độ trễ truyền gói tin. Các giả thuyết liên quan tới việc vận hành là đường kính mạng tương đối nhỏ và các nút di động có thể cho phép chế độ nhận pha tạp trong đó mỗi gói tin nhận được được phân phối tới phần mềm điều khiển mạng mà không cần lọc bởi địa chỉ đích. Ưu điểm của DSR so với các giao thức định tuyến theo yêu cầu khác đó là DSR không sử dụng các quảng bá định 43 tuyến theo chu kỳ, do đó tiết kiệm được băng thông và giảm được năng lượng tiêu thụ. Vì thế, giao thức không phải gánh chịu bất kỳ phụ tải nào khi không có sự thay đổi trong cấu trúc mạng. Ngoài ra, DSR cho phép các nút giữ nhiều tuyến tới đích trong bộ đệm của chúng. Vì thế, khi có một liên kết trên tuyến bị phá vỡ, nút nguồn có thể kiểm tra bộ đệm của nó cho bất kỳ tuyến hợp lệ nào. Nếu tuyến được tìm thấy, việc khởi tạo lại tuyến không cần thiết phải được cầu khẩn lại. Trong trường hợp này, việc khôi phục tuyến là nhanh hơn so với các giao thức theo yêu cầu khác. Tuy nhiên, nếu không có tuyến tới đích nào được thêm vào bộ đệm của nút nguồn, việc phát hiện tuyến phải được khởi tạo lại, cũng như trong AODV, nếu tuyến vẫn được yêu cầu. Mặt khác, bởi vì giả thuyết đường kính nhỏ và yêu cầu định tuyến nguồn, DSR không khả chuyển với các mạng lớn. Các tham số hiệu năng AODV DSR TORA ABR SSR Độ phức tạp thời gian (khởi tạo) O(2d) O(2d) O(2d) O(d+z) O(d+z) Độ phức tạp thời gian (vượt lỗi) O(2d) O(2d) hoặc O* O(2d) O(l+z) O(l+z) Độ phức tạp truyền thông (khởi tạo) O(2N) O(2N) O(2N) O(N+y) O(N+y) Độ phức tạp truyền thông (vượt lỗi) O(2N) O(2N) O(2x) O(x+y) O(x+y) Có vòng lặp Không Không Không Không Không Phương pháp cấu hình lại tuyến Xóa tuyến, thông báo nguồn Xóa tuyến, thông báo nguồn Đảo ngược tuyến, sửa đổi tuyến Truy vấn quảng bá cục bộ Xóa tuyến, thông báo nguồn l = Đường kính của đoạn mạng bị ảnh hưởng y = Tổng số lượng các nút tạo nên đường dẫn trực tiếp trong đó gói tin REPLY truyền đi z = Đường kính của đường dẫn trực tiếp trong đó gói tin REPLY truyền đi (l <= z) * Trúng cache Bảng 4. So sánh đặc tính của các giao thức định tuyến yêu cầu khởi tạo phía nguồn TORA là giao thức định tuyến “đảo ngược liên kết” được đề xuất để vận hành trong môi trường mạng di động thay đổi nhanh. Một trong các ưu điểm của TORA là nó hỗ trợ nhiều tuyến. TORA và DSR chỉ là những giao thức được khảo sát ở đây mà giữ lại được nhiều khả năng tuyến cho một cặp nguồn/đích. Việc khởi tạo lại tuyến là không cần thiết cho đến khi tất cả các tuyến đã biết tới đích dường như không còn hợp lệ và vì thế băng thông có thể được bảo đảm việc ít xây dựng lại tuyến. 44 Việc lựa chọn tuyến trong ABR dựa trên sự ổn định liên kết giữa các nút trong mạng. Vì thế, mặc dù đường đi tới đích không cho kết quả mong muốn theo cách số lượng chặng là nhỏ nhất, đường đi vẫn có xu hướng tồn tại lâu hơn so với các tuyến khác. Tuyến mà tồn tại lâu yêu cầu ít hơn việc khởi tạo lại tuyến vì thế thông lượng đạt được cao hơn. Tuy nhiên, do ABR sử dụng gói tin beacon để báo hiệu sự tồn tại của nút với các nút hàng xóm nên có thể gây ra thêm việc tiêu thụ năng lượng. Giao thức định tuyến SSR là thừa kế logic của ABR. Nó sử dụng kĩ thuật mới trong việc lựa chọn các tuyến dựa trên độ mạnh tín hiệu và sự ổn định vị trí của nút dọc theo đường dẫn. Một trong những trở ngại của giao thức SSR đó là không giống như AODV và DSR, các nút trung gian không thể phản hồi lại yêu cầu tuyến được gửi hướng tới đích, điều này gây ra độ trễ trước khi tuyến có thể được phát hiện. Ngoài ra, khi lỗi liên kết xảy ra dọc theo đường dẫn, thuật toán phát hiện tuyến phải được cầu khẩn từ nguồn để tìm đường đi mới tới đích. 45 Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG CHI PHÍ TÌM ĐƯỜNG CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN MẠNG MANET VỚI CÁC NGỮ CẢNH KHÁC NHAU 4.1. Phân tích và lựa chọn phương pháp mô phỏng để đánh giá [1] Hiện nay có nhiều phương pháp được sử dụng để đánh giá hiệu năng mạng máy tính, về cơ bản chúng ta có thể chia chúng thành 3 nhóm chính bao gồm đánh giá dựa vào mô hình giải tích (Analytic Models), đánh giá dựa vào mô hình mô phỏng (Simulation Models) và đo hiệu năng trên mạng thực (Measurement). Với mô hình giải tích ta thấy các kĩ thuật thường được áp dụng bao gồm quá trình ngẫu nhiên, lý thuyết hàng đợi hay lý thuyết đồ thị bởi các gói số liệu được truyền qua mạng thường có chiều dài và số lượng thay đổi, thời gian của mỗi kết nối cũng thay đổi một cách thống kê do đó việc áp dụng các kĩ thuật trên để đánh giá đo lường hiệu năng của hệ thống mạng là hợp lý. Phương pháp đo hiệu năng trên mạng thực tập trung vào các độ đo mà người đo mong muốn. Kết quả của việc đo cho phép thu thập các số liệu để giám sát cũng như lập mô hình dữ liệu cho các phương pháp đánh giá hiệu năng khác. Ngoài ra, với việc đạt được các kết quả thực tế thì phương pháp đo hiệu năng trên mạng thực cũng có tác dụng kiểm chứng cho các mô hình khác. Mô phỏng theo nghĩa đơn thuần là sự bắt chước một cách giống nhất có thể các khía cạnh của sự vật, hiện tượng trong đời thực. Trong lĩnh vực đánh giá, mô phỏng mạng thì mô phỏng là việc làm các thí nghiệm mạng sử dụng kỹ thuật mà máy tính điện tử số hỗ trợ. Áp dụng ba phương pháp trên vào mạng MANET, chúng ta thấy rằng với mục tiêu có thể thay đổi các tham số hệ thống và các cấu hình mạng trong một miền rộng đạt được kết quả tốt mà chỉ mất chi phí thấp thì sử dụng mô hình giải tích là tốt nhất. Tuy nhiên, vấn đề gặp phải là việc xây dựng các mô hình giải tích với mạng MANET là khó có thể giải được nếu không dùng các giả thiết đơn giản hóa bài toán hoặc sử dụng phương pháp chia nhỏ bài toán thành các mô hình nhỏ hơn. Với các mô hình giải được thì lại khác xa so với thực tế, khó có thể áp dụng và hầu như chỉ dùng phương pháp này cho giai đoạn đầu của quá trình thiết kế mạng. Sử dụng phương pháp đo là tốn kém và hầu như không thể bởi việc đo đạc lấy kết quả cần phải tiến hành tại nhiều điểm của mạng thực trong những thời điểm khác nhau và cần lặp lại nhiều lần trong một khoảng thời gian đủ dài. Ngoài ra việc giới hạn về chi phí cho các công cụ đo cũng là vấn đề cần lưu ý. Với phương pháp mô phỏng chúng ta thấy rằng nó đòi hỏi chi phí chạy thấp cho mỗi lần chạy nhờ đó người nghiên cứu muốn chạy bao nhiều lần và với độ chính xác tùy ý đều được. Nhờ những ưu điểm đó, khi nghiên cứu về mạng MANET thì việc sử dụng mô phỏng vẫn là phương pháp phổ biến nhất hiện nay. Trong luận văn này tôi sử dụng bộ mô phỏng NS2, một bộ mô phỏng mã nguồn mở và hỗ trợ nhiều giao thức định tuyến mạng MANET. 46 4.2. Bộ mô phỏng NS2 NS2 (Network Simulator 2) là một trong các bộ mô phỏng mạng mã nguồn mở được sử dụng phổ biến nhất hiện nay trên thế giới, đặc biệt là trong các trường đại học. NS2 ban đầu là bộ mô phỏng các sự kiện rời rạc tập trung vào việc nghiên cứu mạng. Trong mục này, chúng ta sẽ xem xét mô tả ngắn gọn về hệ thống NS2. 4.2.1. Giới thiệu [1] Chúng ta biết rằng các bộ mô phỏng định hướng vào các nghiên cứu chuyên biệt được các nhà nghiên cứu mạng tạo ra thường không phản ánh được các kinh nghiệm phổ biến. Cái chúng ta cần là một bộ mô phỏng có khả năng giải quyết nhiều vấn đề chuyên sâu của mạng máy tính cũng như việc dễ dàng triển khai và tích hợp thêm các đóng góp của cộng đồng nghiên cứu. Nhận thức được điều đó, dự án VINT (Virtual InterNetwork Testbed) đã được Bộ Quốc Phòng Mỹ cấp kinh phí để xây dựng một bộ mô phỏng có khả năng mô phỏng tập rất lớn các giao thức và mô hình mạng phục vụ cho nghiên cứu, giúp thực hiện các thí nghiệm về mạng, từ đó đánh giá và so sánh nhiều giao thức, mô hình mạng và tham số hiệu năng mạng trong những điều kiện khác nhau. Bộ mô phỏng mạng NS (Network Simulator) do nhóm nghiên cứu tại phòng thí nghiệm Lawrence Berkeley phát triển đã được dự án VINT lựa chọn để phát triển tiếp. Cái tên NS-2 ra đời từ năm 1997 cùng với việc xuất hiện của các phiên bản 2.xx khác khá nhiều so với các phiên bản trước đó là 1.xx. NS2 là một bộ mô phỏng vận hành theo các sự kiện rời rạc, nó cho phép người sử dụng thay đổi cấu hình của mô phỏng một cách dễ dàng ngay cả khi bộ mô phỏng đang vận hành. Ban đầu bộ mô phỏng này được xây dựng trên nền hệ điều hành Unix/Linux. Sau này, một số phiên bản chạy cho môi trường Windows cũng được triển khai và áp dụng. Những người nghiên cứu mạng sau khi xây dựng xong các kịch bản mô phỏng của mình có thể cho nó chạy lặp đi lặp lại nhiều lần với các tham số và cấu hình hệ thống khác nhau. Kết quả thu được từ việc phân tích các tệp vết mà bộ mô phỏng sinh ra sau đó có thể được người nghiên cứu phân tích để đưa ra các kết quả phục vụ cho việc so sánh, đánh giá hiệu năng và từ đó tìm được cấu hình mạng tối ưu hoặc các tham số tối ưu của giao thức.... Khi sử dụng bộ mô phỏng NS2, có thể thấy những điểm nổi bật sau: ü Khả năng trừu tượng hoá: Với bộ mô phỏng NS2, chúng ta c