Mục lục Lời cảm ơn .......................................................................................................................... 3 TU UT Danh mục các từ viết tắt ................................................................................................... 4 TU UT Danh mục hình vẽ .............................................................................................................. 5 TU UT Mở đầu ................................................................................................................................ 7 TU UT Đặt vấn đề ........................................................................................................................ 7 TU UT Phương pháp nghiên cứu ................................................................................................. 7 TU UT Tóm tắt nội dung các chương .......................................................................................... 8 TU UT Chương 1. Giới thiệu mạng ad-hoc .................................................................................. 9 TU UT 1.1. Khái niệm .................................................................................................................. 9 TU UT 1.2. Các ứng dụng của mạng ad-hoc .............................................................................. 10 TU UT 1.3. Đặc điểm của mạng ad-hoc..................................................................................... 11 TU UT 1.4. Một số khái niệm sử dụng trong luận văn .............................................................. 13 TU UT Chương 2. Các thuật toán định tuyến trong mạng ad-hoc .......................................... 15 TU UT 2.1. Thuật toán định tuyến trước .................................................................................... 15 TU UT 2.1.1. Tổng quát ......................................................................................................... 15 TU UT 2.1.2. Nguyên tắc hoạt động ...................................................................................... 16 TU UT 2.1.3. Đánh giá ........................................................................................................... 24 TU UT 2.2. Thuật toán định tuyến theo yêu cầu ........................................................................ 25 TU UT 2.2.1. Tổng quát ......................................................................................................... 25 TU UT 2.2.2. Nguyên tắc hoạt động ...................................................................................... 26 TU UT 2.2.3. Đánh giá ........................................................................................................... 35 TU UT 2.3. Thuật toán lai .......................................................................................................... 36 TU UT Chương 3. Thuật toán định tuyến theo vùng ZRP ....................................................... 37 TU UT 3.1. Giới thiệu chung ..................................................................................................... 37 TU UT 3.1.1. Tổng quát ......................................................................................................... 37 TU UT 3.1.2. Vùng định tuyến ............................................................................................... 38 TU UT 3.1.3. Trạm làm việc ngoại biên - trạm làm việc nội vùng ........................................ 39 TU UT 3.2. Nguyên tắc hoạc động của thuật toán ZRP ............................................................. 40 TU UT 3.2.1. Định tuyến nội vùng ......................................................................................... 40 TU UT 3.2.2. Định tuyến liên vùng ........................................................................................ 41 TU UT 3.2.3. Giải pháp truy vấn ngoại biên .......................................................................... 44 TU UT 3.2.4. Các kỹ thuật điều khiển truy vấn ..................................................................... 47 TU UT 3.2.5. Tham số kích thước vùng ................................................................................. 51 TU UT 3.2.6. Thí dụ minh họa hoạt động của thuật toán ZRP .............................................. 52 TU UT 3.2.7. Đánh giá ........................................................................................................... 55 TU UT 3.3. Mô phỏng hoạt động của thuật toán ZRP bằng phần mềm máy tính ..................... 56 TU UT 3.3.1. Mô phỏng hoạt động của thuật toán ZRP bằng hệ mô phỏng NS-2 ................ 56 TU UT 3.3.2. Mô phỏng hoạt động của thuật toán ZRP bằng hệ mô phỏng Qualnet ............ 57 TU UT 3.3.3. Đánh giá chung ................................................................................................ 62 TU UT 3.4. Các đề xuất cải tiến ................................................................................................. 63 TU UT 3.4.1. Sử dụng thuật toán cập nhật nhanh trạng thái kết nối cho thành phần IARP .. 63 TU UT 3.4.2. Tự động thiết lập riêng tham số kích thước vùng định tuyến. ......................... 63 TU UT 3.4.3. Cho phép lựa chọn sử dụng kỹ thuật điều khiển truy vấn................................ 64 TU UT Kết luận ............................................................................................................................ 65 TU UT 2 Tóm tắt kết quả nghiên cứu trong luận văn ................................................................... 65 TU UT Hướng nghiên cứu tiếp theo........................................................................................... 65 TU UT Tài liệu tham khảo ........................................................................................................... 66 TU UT Phụ lục1: Kết quả chi tiết mô phỏng minh họa hoạt động của thuật toán ZRP TU bằng NS-2 ......................................................................................................................... 68 UT Phụ lục 2: Thực hiện thí nghiệm bằng phần mềm mô phỏng Qualnet ...................... 71 TU UT 3 Lời cảm ơn Lời cám ơn sâu sắc đầu tiên, tác giả xin được gửi tới thày giáo hướng dẫn PGS.TS. Vũ Duy Lợi – Văn phòng Trung ương Đảng. Mặc dù công việc rất bận, nhưng thày đã dành khá nhiều thời gian để hướng dẫn tận tình, giúp cho luận văn được hoàn thành đúng thời hạn. Xin trân trọng cảm ơn thày giáo, TS. Nguyễn Đình Việt, người đã cung cấp và hướng dẫn cài đặt bộ mô phỏng NS-2, một công cụ mô phỏng đã được sử dụng trong quá trình làm luận văn. Thày cũng đã có những góp ý bổ ích và tạo điều kiện để tác giả luận văn được cùng làm việc với nhóm do thày hướng dẫn. Xin cảm ơn sự tạo điều kiện, giúp đỡ, động viên của lãnh đạo và anh chị em trong Viện Công nghệ Thông tin - Đại học Quốc gia Hà nội, cơ quan nơi tôi đang công tác. Cảm ơn sự động viên giúp đỡ của các bạn cùng lớp cao học K9T3. Các bạn đã cung cấp một số tài liệu liên quan tới vấn đề mà luận văn nghiên cứu. Cảm ơn các thày cô giáo và các cán bộ trong trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã cung cấp các kiến thức khoa học và tạo điều kiện thuận lợi cho tác giả trong quá trình học tập và thực hiện luận văn cao học này. Những nguồn giúp đỡ động viên quý báu kể trên tạo điều kiện và là động lực rất lớn để tác giả hoàn thành luận văn. 4 Danh mục các từ viết tắt AODV Ad-hoc On Demand Distance Vector routing protocol – một giao thức định tuyến cho mạng ad-hoc. BRP Bordercast Resolution Protocol - giải pháp truy vấn ngoại biên. CBR Constant Bit Rate – kỹ thuật phát gói tin theo tốc độ cố định. DSDV Highly Dynamic Destination-Sequenced DistanceVector routing protocol – một giao thức định tuyến trước dựa vào vectơ khoảng cách. IARP Intrazone Routing Protocol – thành phần định tuyến nội vùng. IERP Interzone Routing Protocol – thành phần định tuyến liên vùng. NPDU Network Protocol Data Unit – gói dữ liệu mạng. QD Query Detection - Kỹ thuật phát hiện truy vấn đã xử lý. RERR Route Error – gói tin báo lỗi đường truyền. RREP Route Reply – gói tin trả lời định tuyến. RREQ Route Request – gói tin yêu cầu định tuyến. ZRP Zone Routing Protocol – giao thức định tuyến theo vùng, một giao thức định tuyến cho mạng ad-hoc. 5 Danh mục hình vẽ Hình 1. Mạng máy tính kết nối không dây với 2 access point TU UT 9 Hình 2. Mạng ad-hoc TU UT 10 Hình 3. Ứng dụng rộng rãi của mạng ad-hoc trong cuộc sống TU UT 11 Hình 4. Giá trị thước đo định tuyến tính theo số bước nhảy TU UT 13 Hình 5. Thuật toán phân phối Bellman-Ford (Distance Vector) TU UT 17 Hình 6. Bảng định tuyến của trạm làm việc trong mạng sử dụng thuật toán DSDV TU UT 18 Hình 7. Trạm làm việc được cung cấp hai thông tin định tuyến khác nhau TU UT 21 Hình 8. Hiện tượng mất liên kết. TU UT 22 Hình 9. Mạng ad-hoc với sự di chuyển của trạm làm việc TU UT 23 Hình 10. Thiết lập đường quay lại TU UT 28 Hình 11. Thiết lập đường truyền số liệu TU UT 30 Hình 12. Đường kết nối tích cực TU UT 31 Hình 13. Hiện tượng mất kết nối TU UT 34 Hình 14. Đảm bảo kết nối đối xứng dựa vào gói tin hello TU UT 35 Hình 15. Các thành phần của thuật toán định tuyến vùng ZRP TU UT 37 Hình 16. Vùng định tuyến tương ứng với trạm làm việc S có bán kính r = 2 TU UT 38 Hình 17. Sự chồng chéo của các vùng định tuyến TU UT 39 Hình 18. Trạm làm việc ngoại biên TU UT 39 Hình 19. Cách thức làm việc của thành phần định tuyến liên vùng IERP TU UT 43 Hình 20. Gửi quảng bá gói tin yêu cầu định tuyến TU UT 45 Hình 21. Gửi gói tin yêu cầu định tuyến với giải pháp truy vấn ngoại biên BRP TU UT 46 Hình 22. Kết thúc truy vấn lặp TU UT 47 Hình 23. Kết thúc truy vấn sớm TU UT 48 Hình 24. Kỹ thuật phát hiện truy vấn đã xử lý TU UT 49 Hình 25. Truy vấn ngoại biên chọn lọc TU UT 50 Hình 26. Trạm làm việc nguồn S yêu cầu thông tin định tuyến TU UT 52 Hình 27. Cây truy vấn ngoại biên do S xây dựng TU UT 53 Hình 28. Trạm làm việc J tiếp tục quá trình truy vấn định tuyến TU UT 53 Hình 29. Cây truy vấn ngoại biên do J xây dựng TU UT 54 Hình 30. Trạm làm việc đích D được tìm thấy TU UT 54 Hình 31. Mô hình thử nghiệm xác minh hoạt động của thuật toán định tuyến TU UT 56 Hình 32. Thí nghiệm mô phỏng hoạt động của thuật toán ZRP trên hệ mô phỏng TU QualnetUT 58 Hình 33. Số lượng gói tin truyền trên từng trạm TU UT 59 Hình 34. Lưu lượng gói tin truyền trên mạng có tính di động cao TU UT 60 Hình 35. Thời gian trễ trung bình của các gói tin TU UT 60 Hình 36. Số lượng gói tin gửi thành công TU UT 61 Hình 37. Số lượng ít gói tin yêu cầu định tuyến được gửi đi TU UT 61 6 Hình 38. Thiết lập diện tích và thời gian cho thí nghiệm mô phỏng TU UT 71 Hình 39. Lựa chọn thuật toán định tuyến TU UT 72 Hình 40. Thiết đặt kích thước vùng định tuyến TU UT 72 Hình 41. Tự động đặt các trạm làm việc TU UT 72 Hình 42. Lựa chọn để đặt các trạm bằng tay TU UT 72 Hình 43. Chỉ định file cung cấp thông tin di chuyển của các trạm làm việc TU UT 73 Hình 44. Chỉ định file thiết lập kết nối và kết quả sau khi chỉ định TU UT 74 Hình 45. Nhấn nút run để thực hiện thí nghiệm TU UT 75 Hình 46. Sử dụng chức năng Run Batch Experiment TU UT 75 Hình 47. Hiển thị và trích xuất dữ liệu bằng Analyzer TU UT 76 7 Mở đầu Đặt vấn đề Cùng với sự phát triển không ngừng của khoa học công nghệ, hệ thống thông tin liên lạc và truyền thông cũng liên tục đổi mới. Ngày nay, các thiết bị di động ngày càng được sử dụng rộng rãi và phát huy sức mạnh. Trên thế giới, các kết quả nghiên cứu và ứng dụng của mạng không dây đã mang lại rất nhiều lợi ích cho xã hội. Tại Việt Nam, mạng điện thoại di động trong vài năm gần đây cũng phát triển hết sức mạnh mẽ. Trong lĩnh vực mạng máy tính, đã có nhiều cơ quan, đơn vị lựa chọn sử dụng mạng không dây thay thế mạng hữu tuyến truyền thống. Những mô hình mạng nói trên đòi hỏi các đơn vị, công ty phải xây dựng một cơ sở hạ tầng mạng với hệ thống các trạm tiếp sóng (base station) được thiết đặt trước tại những vị trí cố định. Thời gian gần đây, các nhà khoa học đang hướng tới nghiên cứu, triển khai mạng di động, trong đó, các thiết bị di động có thể kết nối, giao tiếp, trao đổi thông tin với nhau bằng sóng vô tuyến, theo phương thức bắc cầu, mà không đòi hỏi có một cơ sở hạ tầng thông tin liên lạc nào được xây dựng từ trước. Các thiết bị di động ở xa ngoài vùng phủ sóng vô tuyến của nhau có khả năng giao tiếp với nhau thông qua các thiết bị khác, và do vậy vẫn có thể phối hợp hoạt động một cách nhịp nhàng. Việc kết nối cũng được thực hiện “trong suốt”, khi mà người sử dụng không cần phải bận tâm thiết lập môi trường làm việc để kết nối các thiết bị di động với nhau. Một mạng như mô tả ở trên được gọi là mạng di động không cấu trúc, hay mạng ad-hoc. Để mạng ad-hoc có thể làm việc được, các thiết bị di động trong mạng cần sử dụng một giao thức truyền thông hiệu quả, mà phần rất quan trọng trong đó là thuật toán định tuyến trong mạng ad-hoc. Luận văn đi sâu tìm hiểu một thuật toán định tuyến cho các thiết bị di động trong môi trường mạng di động không cấu trúc - thuật toán định tuyến theo vùng Zone Routing Protocol (ZRP) Phương pháp nghiên cứu Nhằm đạt được mục đích nghiên cứu của luận văn, tác giả phải tập hợp và nghiên cứu các tài liệu đề cập đến các vấn liên quan, đã được công bố trên thế giới; các bản nháp khuyến nghị của tổ chức IETF; các tài liệu trình bày về mạng không dây và các giao thức cho mạng không dây. Do không thể thực hiện thí nghiệm trên hệ thống mạng thực, tác giả sử dụng các hệ mô phỏng NS-2 và Qualnet (phiên bản thương mại của Glomosim) – là các hệ mô phỏng mạng đã và đang được các nhà nghiên cứu và nhiều trường đại học trên thế giới tin cậy sử dụng trong các nghiên cứu khoa học và giảng dạy - để làm thí nghiệm. 8 Luận văn cũng kế thừa các thành quả nghiên cứu đã được công nhận của các trung tâm nghiên cứu, các trường đại học và các tác giả đã từng nghiên cứu các lĩnh vực liên quan, sát với đề tài của luận văn. Tóm tắt nội dung các chương Luận văn được chia làm 3 chương. Chương 1 nêu lên khái niệm về mạng ad-hoc, ứng dụng của mạng ad-hoc và các vấn đề cần giải quyết. Để đạt được tính nhất quán về các thuật ngữ sử dụng trong luận văn, một số thuật ngữ cũng được đưa ra. Chương 2 giới thiệu các thuật toán định tuyến trước và định tuyến theo yêu cầu trong mạng ad-hoc, làm cơ sở cho việc trình bày thuật toán lai ZRP trong chương 3. Ở đây, luận văn bày sâu về thuật toán DSDV, một đại diện cho loại thuật toán định tuyến trước. Tương tự, thuật toán AODV được chọn làm đại diện cho loại thuật toán định tuyến theo yêu cầu và cũng được trình bày kỹ lưỡng. Ưu, nhược điểm của mỗi loại thuật toán được nêu ra ở phần đánh giá, cuối mỗi phần trình bày về nguyên tắc hoạt động của các thuật toán. Chương 3 trình bày về thuật toán định tuyến theo vùng Zone Routing Protocol – ZRP, trong đó, giới thiệu chi tiết các thành phần của thuật toán và mối quan hệ giữa chúng. Đồng thời, nội dung của chương này cũng trình bày các giải pháp và kỹ thuật điều khiển truy vấn sao cho thuật toán đạt được hiệu quả cao nhất. Phần đánh giá chỉ rõ ưu, nhược điểm của thuật toán ZRP. Luận văn cũng đưa ra kết quả cài đặt và mô phỏng thuật toán trên hệ mô phỏng Qualnet và NS-2 làm minh họa và có đánh giá chung, sau đó, đưa ra các đề xuất cải tiến. Phần kết luận nêu các kết quả đạt được trong luận văn và hướng nghiên cứu tiếp theo. Cuối luận văn là danh sách các tài liệu tham khảo đã được sử dụng. Sau cùng, hai phụ lục mô tả các bước tiến hành thí nghiệm và phân tích chi tiết kết quả thí nghiệm mô phỏng, minh hoạ thuật toán định tuyến ZRP được đính kèm. 9 Chương 1. Giới thiệu mạng ad-hoc 1.1. Khái niệm Mạng không dây Sau thời gian dài phát triển trên thế giới, những năm gần đây mạng điện thoại di động đã và đang nở rộ trên thị trường Việt Nam, làm nên những thay đổi lớn trong xã hội. Mạng điện thoại di động chính là một thí dụ tiêu biểu của mạng không dây. Ở đó, các điện thoại được kết nối với nhau thông qua các hệ thống thiết bị kết nối trung gian là các trạm tiếp sóng. Khi điện thoại di động không nằm trong vùng phủ sóng của bất kỳ một trạm tiếp sóng nào, nó không thể thực hiện được cuộc gọi đi hay nhận cuộc gọi đến. Tương tự, trong lĩnh vực mạng máy tính, các máy tính có thể được kết nối với nhau thông qua một thiết bị trung gian gọi là Access Point (chính là các trạm tiếp sóng - Base Station). Các thiết bị này thường kết nối với nhau và với phần còn lại của mạng bằng đường truyền hữu tuyến nhưng giao tiếp với các máy tính (có cắm vỉ mạng không dây) bằng sóng vô tuyến. Cũng có khi các Access Point kết nối vô tuyến với nhau như trong hình 1. Đó là mạng máy tính không dây thông thường. Hình 1. Mạng máy tính kết nối không dây với 2 access point Với cách kết nối không dây như trên, các trạm làm việc (máy tính, điện thoại di động,…) sẽ trao đổi số liệu với nhau thông qua các trạm tiếp sóng. Tức là các gói dữ liệu gửi giữa các trạm làm việc đều được truyền tới trạm tiếp sóng và trạm tiếp sóng sẽ chịu trách nhiệm chuyển các gói tin này tới trạm đích được chỉ định. Như vậy, trạm tiếp sóng đồng thời đóng vai trò của bộ định tuyến. 10 Mạng ad-hoc Trong nhiều trường hợp, điều kiện không cho phép xây dựng hệ thống trạm tiếp sóng, chẳng hạn khi thiết lập hệ thống liên lạc phục vụ cứu nạn sau thiên tai, hoặc trong các trận chiến sử dụng công nghệ cao mà các vũ khí, khí tài và ngay cả các chiến binh cần thường xuyên liên lạc với nhau. Để giải quyết vấn đề, người ta đưa ra giải pháp xây dựng mạng, trong đó, mỗi trạm làm việc không dây đồng thời đảm trách cả chức năng của bộ định tuyến. Các trạm làm việc gửi số liệu cho nhau thông qua các trạm khác, không cần có các trạm kết nối trung gian (Base Station). Một mạng như vậy được gọi là Mobile Ad-hoc Network (MANET) hay mạng di động không cấu trúc, trong luận văn, gọi tắt là mạng ad-hoc. Hình 2. Mạng ad-hoc 1.2. Các ứng dụng của mạng ad-hoc Như đã nói ở trên, mạng ad-hoc được áp dụng cho các cuộc tìm kiếm, cứu nạn sau thiên tai, như động đất, lũ lụt,… khi mà hệ thống thông tin liên lạc đã bị phá hủy. Việc tiến hành cứu nạn là khẩn cấp, và người ta không thể chờ đợi để xây dựng lại hệ thống liên lạc. Hay việc tìm kiếm cứu nạn ở những nơi mà hệ thống thông tin liên lạc không có sẵn như các vùng núi cao, bắc cực, xa mạc… nơi không có con người sinh sống. Trong trường hợp này, ngoài tính khẩn cấp, việc xây dựng một hệ thống thông tin liên lạc nhằm mục đích chỉ phục vụ cho một công việc nhất thời là không khả thi. Mạng ad-hoc còn được áp dụng rất hiệu quả trong quân đội một số cường quốc, nơi mà các vũ khí, khí tài công nghệ cao, có độ chính xác rất lớn được sử dụng. Khi triển khai các trận đánh, các vũ khí, khí tài, thậm chí từng quân nhân có thể liên lạc với nhau để có thể đánh hiệp đồng một cách nhịp nhàng, chính xác. 11 Ngoài ra, mạng ad-hoc còn có thể được triển khai một cách rộng rãi cho các ứng dụng khác như: • Trong các cuộc họp (thay thế mạng không dây thông thường đang sử dụng hiện nay). Công việc chuẩn bị cho cuộc họp sẽ dễ dàng hơn do không phải chuẩn bị hệ thống liên lạc cho các máy móc thiết bị sử dụng trong cuộc họp. Do vậy các cuộc họp có thể diễn ra tại bất cứ địa điểm nào. • Mạng kết nối dành cho cá nhân (Bluetooth). Mọi người không cần phải bận tâm trong việc thiết lập kết nối cho các thiết bị cá nhân. • Mạng kết nối các thiết bị trong gia đình. Các thiết bị sẽ hoạt động hiệu quả hơn nhờ sự phối hợp nhịp nhàng. Chẳng hạn đài sẽ tự tắt khi ta bật ti vi. • Trong các ứng dụng khác (điều khiển công nghệp, mạng taxi, mạng kết nối các tàu thuyền,…) Hình 3. Ứng dụng rộng rãi của mạng ad-hoc trong cuộc sống 1.3. Đặc điểm của mạng ad-hoc Mạng ad-hoc có các đặc điểm sau: • Có cấu trúc động: Do tính di động của tất cả các trạm làm việc trong mạng, sự thay đổi về cấu trúc mạng xảy ra thường xuyên. Các kết nối giữa các trạm làm việc có thể hình thành và mất đi nhanh chóng, phụ thuộc vào tốc độ và hướng di chuyển của các trạm làm việc. Điều này khiến cho việc truyền số liệu giữa các trạm làm việc gặp nhiều khó khăn. Chúng phải thường xuyên định tuyến lại trong suốt quá trình truyền số liệu và không sử dụng được hướng truyền mặc định (default route) như đối với mạng hữu tuyến và mạng di động thông 12 thường. Do vậy, vấn đề định tuyến, vốn đã rất phức tạp trong mạng hữu tuyến và mạng không dây thông thường, nay còn phức tạp hơn rất nhiều trong mạng ad-hoc. • Dung lượng đường truyền thấp: Các thiết bị di động kết nối với nhau qua sóng vô tuyến, do vậy dung lượng đường truyền bị hạn chế, thấp hơn rất nhiều so với dung lượng truyền trên các đường truyền hữu tuyến. Khi các trạm làm việc càng cách xa nhau, tín hiệu vô tuyến càng yếu và do đó dung lượng truyền cũng giảm dần. • Mức năng lượng cung cấp cho các trạm làm việc hạn chế: Do tính chất di động của các trạm làm việc, pin là nguồn cung cấp năng lượng chủ yếu. Do vậy các thiết bị di động phải được thiết kế (cả phần cứng lẫn phần mềm) sao cho mức tiêu thụ năng lượng đạt tối thiểu và phải áp dụng các giải pháp tiết kiệm năng lượng tối đa. Trong một vài năm gần đây, một số công ty lớn đã phát triển những loại pin có thời gian sử dụng lâu hơn, thậm chí thời gian sạc lại rất ngắn và sẽ tung ra thị trường trong tương lai không xa. Tuy nhiên, vấn đề hạn chế về nguồn năng lượng cung cấp cho các thiết bị di động vẫn là một mối quan tâm lớn. • Có thể xảy ra hiện tượng kết nối một chiều (unidirectional link): Ở mạng hữu tuyến, khi trạm làm việc A truyền được dữ liệu tới trạm làm việc B thì B cũng có thể truyền dữ liệu trở lại A (bidirectional link). Tuy nhiên trong mạng không dây, đôi khi A gửi được dữ liệu tới B nhưng do mức năng lượng phát tín hiệu của B yếu, hoặc do nhiễu điện từ mà tín hiệu phát đi từ B lại không tới được A. Trường hợp này được gọi là kết nối một chiều hay kết nối không đối xứng. Cần có biện pháp giải quyết để đảm bảo cho việc truyền số liệu khi gặp hiện tượng trên. • Ngoài ra, vấn đề bảo mật thông tin cũng là điều đáng quan tâm, do sự lan tỏa của sóng vô tuyến. Đối với mạng hữu tuyến, muốn nhận được thông tin truyền trên đường truyền, bắt buộc phải tiếp cận được với đường cáp truyền. Trong mạng không dây nói chung, sự lan tỏa của sóng vô tuyến khiến cho bất kỳ trạm làm việc nào nằm trong vùng bao phủ của sóng cũng có thể tiếp cận với tín hiệu được phát ra. Có nghĩa là vấn đề mã hóa thông tin cần phải được chú trọng trong mạng ad-hoc nói riêng và mạng không dây nói chung. Như vậy có rất nhiều vấn đề cần được giải quyết để đảm bảo mạng ad-hoc hoạt động tin cậy, an toàn và hiệu quả. Luận văn chỉ xin đề cập chủ yếu đến vấn đề định tuyến trong mạng ad-hoc. 13 1.4. Một số khái niệm sử dụng trong luận văn Trạm làm việc Trong mạng máy tính, các máy tính được kết nối với nhau để trao đổi thông tin. Các máy tính là thành phần quan trọng nhất trong mạng máy tính. Nhưng để kết nối các máy tính này, cần có các thiết bị kết nối mạng như bộ định tuyến, bộ chuyển mạch,… Để có thể đảm trách được nhiệm vụ đó, chúng cũng phải truyền, nhận, xử lý thông tin ở một mức độ nào đấy. Trong mạng truyền thông nói chung, mỗi thiết bị như vậy (máy tính, bộ định tuyến, bộ chuyển mạch,…) được gọi với tên chung là trạm làm việc (node). Tuy nhiên, trong mạng ad-hoc, có thể coi các trạm làm việc chính là các máy tính vì chúng đảm trách chức năng của tất cả các thiết bị còn lại. Trong các ứng dụng thực tế của mạng ad-hoc, trạm làm việc là bất kỳ thiết bị nào có khả năng giao tiếp với các thiết bị mạng khác và chuyển tiếp gói tin trong mạng. Giá trị thước đo định tuyến - bước nhảy Trong mạng máy tính thường có nhiều đường kết nối giữa hai trạm làm việc. Vì vậy các bộ định tuyến (router) cần phải chọn đường kết nối nào để việc truyền dữ liệu đạt hiệu quả cao nhất. Người ta đưa ra khái niệm thước đo định tuyến (metric) để đánh giá ưu thế của các đường kết nối. Giá trị này có thể là tổng hợp của nhiều yếu tố như tốc độ tối đa của đường truyền, độ trễ truyền tin, tỷ lệ các gói tin bị mất,… nhưng cũng có thể chỉ dựa vào số bước nhảy (hop count) trong đường kết nối giữa hai trạm làm việc. Hình 4a: Khoảng cách 1 hop Hình 4b: Khoảng cách 2 hop Hình 4. Giá trị thước đo định tuyến tính theo số bước nhảy Nếu để đến được trạm làm việc đích, gói tin phải được chuyển qua N+1 bộ định tuyến khác nhau thì nói hai trạm làm việc cách nhau N bước nhảy, hay đường kết nối giữa hai trạm làm việc có khoảng cách N bước nhảy. Nói cách khác, đường kết nối trực tiếp hai bộ định tuyến với nhau tương ứng với một bước nhảy. Ở đây, ta không chú ý đến độ dài địa lý của đường kết nối. Trong ví dụ ở hình 4, mặc dù chiều dài đường kết nối gữa hai bộ định tuyến trong hình 4a có thể dài hơn rất nhiều (về mặt địa lý) so với tổng chiều dài đường kết nối trong hình 4b (từ bộ định tuyến A đến bộ định tuyến B). Nhưng khi tính theo số bước nhảy, khoảng cách từ A đến B trong hình 4a (1 hop) được coi là gần hơn khoảng cách từ A đến B trong hình 4b (2 hop). 14 Trong luận văn, số bước nhảy được lấy làm đơn vị thước đo đánh giá khoảng cách giữa hai trạm làm việc. Mỗi trạm làm việc cũng đồng thời là một bộ định tuyến và kết nối giữa các trạm làm việc là kết nối vô tuyến. Trạm nguồn - Trạm đích - Trạm lân cận - Trạm kế tiếp Để không bị nhầm lẫn các khái niệm được dùng trong luận văn, tác giả xin nêu các từ đã sử dụng để chỉ rõ vai trò của các trạm làm việc trong mạng ad-hoc. Khi trạm A có yêu cầu truyền số liệu tới trạm B thì A được gọi là trạm làm việc nguồn, B được gọi là trạm làm việc đích. Trạm làm việc nguồn phải sử dụng thuật toán định tuyến để tìm được đường đi tới trạm làm việc đích, sau đó mới có thể chuyển đi các gói số liệu. Một trạm làm việc N được coi là lân cận (neighbor node) của trạm làm việc S nếu nó có thể trao đổi dữ liệu trực tiếp với S mà không cần thông qua các trạm làm việc khác. Nói cách khác, N cách S một bước nhảy. Trong mạng ad-hoc, N phải nằm trong vùng phủ sóng tín hiệu của S. N được coi là trạm làm việc kế tiếp (next hop) của M nếu nó là trạm lân cận của M và nằm trên đường kết nối giữa trạm làm việc nguồn và trạm làm việc đích. Nói cách khác, N sẽ là trạm làm việc đầu tiên mà M gửi gói số liệu đến trong quá trình chuyển tiếp các gói số liệu tới trạm làm việc đích. Gói tin yêu cầu định tuyến – gói tin trả lời định tuyến – gói tin định tuyến - xử lý truy vấn Trước khi truyền số liệu, trạm làm việc nguồn cần phải tìm được đường đi tới trạm làm việc đích. Để thực hiện việc này, chúng phát đi các gói tin yêu cầu định tuyến. Khi một trạm làm việc biết đường đi tới trạm làm việc đích, nó sẽ trả lời trạm làm việc nguồn bằng gói tin trả lời định tuyến cho biết đường đi tới trạm làm việc đích. Gói tin định tuyến được sử dụng để chỉ tất cả các gói tin truyền trên mạng nhằm mục đích tìm đường từ trạm làm việc nguồn đến tram làm việc đích, bao gồm cả các gói tin yêu cầu định tuyến, gói tin trả lời định tuyến và các gói tin cập nhật thông tin định tuyến. Các gói tin định tuyến không chứa số liệu cần truyền. Những hành động mà một trạm làm việc thực hiện khi nhận được một gói tin yêu cầu định tuyến (kiểm tra gói tin yêu cầu định tuyến, tìm thông tin định tuyến, chuyển tiếp gói tin yêu cầu định tuyến…) được gọi chung là xử lý truy vấn. 15 Chương 2. Các thuật toán định tuyến trong mạng ad-hoc Đã có rất nhiều thuật toán định tuyến dành cho mạng ad-hoc được đề xuất. Mỗi thuật toán đều có ưu, nhược điểm riêng và được cải tiến dần để hạn chế các nhược điểm, đồng thời phát huy ưu điểm vốn có. Người ta có thể phân loại các thuật toán định tuyến dành cho mạng ad-hoc theo các đặc điểm về thời điểm định tuyến (proactive, reactive), về tính phân cấp (hierachical), tính sử dụng dữ liệu địa lý (geographical), tính tiết kiệm năng lượng (power aware), v.v...[14]. Xét theo thời điểm định tuyến, ta có hai loại thuật toán định tuyến: định tuyến trước (proactive routing protocol) và định tuyến theo yêu cầu (reactive routing protocol). Ngoài ra, nhiều thuật toán kết hợp hai loại trên cũng được đề xuất. Luận văn sẽ trình bày về hai loại thuật toán trên với các đại diện tiêu biểu và tập trung vào một thuật toán kết hợp - thuật toán định tuyến theo vùng Zone Routing Protocol. 2.1. Thuật toán định tuyến trước Khi sử dụng thuật toán định tuyến trước, mỗi trạm làm việc sẽ lưu giữ và thường xuyên cập nhật một bảng định tuyến, trong đó, chỉ rõ đường đi tới các trạm làm việc khác trong mạng. Do vậy, bất cứ khi nào một trạm làm việc muốn truyền số liệu, nó có thể lấy ngay thông tin trong bảng định tuyến do chính nó đang lưu giữ để lập tức chuyển gói tin tới đích đã định. Nói cách khác, thông tin định tuyến đã sẵn sàng từ trước khi có nhu cầu truyền số liệu. Tiêu biểu cho loại thuật toán định tuyến trước phải kể đến DSDV (Highly Dynamic Destination-Sequenced DistanceVector routing protocol), WRP (Wireless Routing Protocol), OLSR (Optimized Link State Routing Protocol). 2.1.1. Tổng quát Các thuật toán định tuyến trước thường sử dụng thuật toán phân phối Bellman-Ford (Distributed Bellman-Ford Algorithm). Đây là thuật toán sử dụng vector khoảng cách (Distance Vector), trong đó các trạm làm việc định kỳ trao đổi thông tin của toàn bộ bảng định tuyến. Do vậy, các thuật toán sử dụng vector khoảng cách còn được gọi là các thuật toán dựa vào việc trao đổi bảng định tuyến (Table Driven). Chúng ta sẽ tìm hiểu thuật toán Bellman-Ford làm cơ sở để sau đó xem xét một đại diện cho loại thuật toán đinh tuyến trước: thuật toán định tuyến DSDV. Sở dĩ thuật toán DSDV được chọn trình bày trong luận văn, cùng với thuật toán AODV (được trình bày trong phần 2.2), vì cả hai thuật toán cùng do C. Perkins đề xuất. DSDV là thuật toán nền tảng để sau đó Perkins phát triển thuật toán định tuyến theo yêu cầu AODV. Chúng ta sẽ dễ dàng phân tích đánh giá sự khác biệt giữa hai loại thuật toán sau khi tìm hiểu kỹ hai thuật toán này. 16 2.1.2. Nguyên tắc hoạt động 2.1.2.1. Thuật toán phân phối Bellman-Ford Thuật toán phân phối Bellman-Ford (còn được gọi là thuật toán vector khoảng cách - Distance Vector) đã được sử dụng hiệu quả trong một số thuật toán định tuyến cho mạng hữu tuyến, chẳng hạn RIP (Routing Information Protocol), IGRP (Internet Gateway Routing Protocol – do Cisco phát triển), RTMP (Routing Table Maintenance Protocol – do Apple phát triển) và một số thuật toán định tuyến dành cho mạng không dây, trong đó có DSDV [1], [15]. Trong thuật toán phân phối Bellman-Ford, mỗi trạm làm việc S lưu giữ một bảng định tuyến, trong đó chỉ rõ để tới được mỗi trạm làm việc đích D trong mạng thì phải chuyển gói tin số liệu qua trạm làm việc lân cận N nào của S và khoảng cách tương ứng theo đường đi đó, với khoảng cách là quãng đường ngắn nhất từ S tới D, thường tính bằng số bước nhảy. N khi đó sẽ là trạm làm việc kế tiếp của S trong đường đi ngắn nhất từ S tới D nêu trên. Để cập nhật các thông tin về đường đi ngắn nhất, mỗi trạm làm việc định kỳ trao đổi thông tin trong bảng định tuyến của nó với các trạm làm việc lân cận. Căn cứ vào thông tin định tuyến do các trạm làm việc lân cận gửi đến, S sẽ biết được đường đi ngắn nhất tới mỗi trạm làm việc khác trong mạng, thông qua các trạm làm việc lân cận. Chẳng hạn, với mỗi trạm làm việc D trong mạng, S sẽ chọn một trạm làm việc N lân cận với S làm trạm kế tiếp trong đường đi tới D, sao cho khoảng cách từ N tới D là ngắn nhất so với khoảng cách từ các trạm làm việc lân cận còn lại của S tới D. Thông tin này được lưu lại trong bảng định tuyến của S (là một dòng của bảng định tuyến), và sau đó sẽ được S trao đổi với các trạm làm việc lân cận của nó tại thời điểm trao đổi thông tin định tuyến định kỳ lần tiếp theo. Hình 5 dưới đây là một thí dụ minh họa. Trong minh hoạ này, trạm làm việc 1 kết nối trực tiếp với D (là lân cận của D). Dĩ nhiên, nó biết được đường đi ngắn nhất từ nó đến D và gửi thông tin định tuyến tới các trạm làm việc lân cận 2 và 3 cho biết trạm làm việc kế tiếp trong đường đi ngắn nhất từ nó tới D - ở đây chính là D - với khoảng cách là 1, tính theo số bước nhảy. Dựa vào thông tin đó, trạm làm việc 2 và trạm làm việc 3 biết được đường đi ngắn nhất tới D là đi qua trạm làm việc 1 với khoảng cách cùng là 2 bước nhảy. Trạm làm việc 2 tiếp tục gửi thông tin định tuyến của nó tới hai trạm lân cận là 4 và S. Trong khi đó, trạm làm việc 3 cũng gửi thông tin định tuyến của mình tới trạm làm việc 4. Và do đó, S cũng sẽ nhận được thông tin định tuyến từ trạm làm việc 4 cho biết đường đi ngắn nhất từ trạm làm việc 4 tới D là qua trạm làm việc 3 với khoảng cách là 3 bước nhảy. Như vậy, S nhận được thông tin định tuyến từ hai trạm làm việc 2 và 4. 17 Hình 5. Thuật toán phân phối Bellman-Ford (Distance Vector) Sau khi tính toán, S thấy rằng để đến D, nếu đi qua trạm làm việc 4 thì khoảng cách là 4 bước nhảy; còn nếu đi qua trạm làm việc 2 thì khoảng cách là 3 bước nhảy. Vậy đường đi qua trạm làm việc 2 sẽ ngắn hơn. S sẽ lưu thông tin tính toán được này vào bảng định tuyến của nó và sau đó trao đổi thông tin này, cùng các thông tin khác đã được lưu trong bảng định tuyến, với các trạm làm việc lân cận của nó. Việc tính toán đường đi tới các trạm làm việc khác cũng tương tự. Bảng định tuyến tại S sẽ có nội dung như sau: Destination Next Hop Hops S S 0 1 2 2 2 2 1 3 4 2 4 4 1 D 2 3 … … … Lưu ý rằng, trong thuật toán này, bảng định tuyến chỉ lưu một đường đi ngắn nhất đến mỗi trạm làm việc trong mạng. Thuật toán phân phối Bellman-Ford có ưu điểm là việc tính toán đơn giản và hiệu quả, do tính chất phân phối của nó (tất cả các trạm làm việc đều lưu thông tin định tuyến và việc tính toán tại mỗi trạm làm việc dựa vào thông tin do các trạm làm việc lân cận cung cấp). 18 Tuy nhiên, thuật toán cũng có nhược điểm là sự hội tụ chậm. Tức là khi có sự thay đổi về thông tin định tuyến, do tính chất định kỳ trong việc trao đổi thông tin nên phải mất một thời gian, toàn bộ các trạm làm việc trong mạng mới có được thông tin định tuyến chính xác (đạt trạng thái hội tụ - convergence). Tại một thời điểm nào đó, khi thông tin định tuyến trên toàn mạng chưa hội tụ có thể nảy sinh hiện tượng gói tin bị chuyển vòng quanh trên mạng (routing loop). Hiện tượng này thường xảy ra trong các mạng có nhiều kết nối không ổn định. 2.1.2.2. Thuật toán định tuyến DSDV DSDV (Destination Sequence Distance Vector routing protocol) được C. Perkins đề xuất năm 1994, sử dụng thuật toán vector khoảng cách (hay thuật toán Bellman-Ford) trình bày ở trên với một số sửa đổi bổ sung nhằm tránh hiện tượng các gói tin bị gửi vòng quanh (loop) [3], [17]. DSDV đã được tích hợp trong phần mềm mô phỏng NS2. Trong mạng ad-hoc sử dụng thuật toán định tuyến DSDV, mỗi trạm làm việc sẽ lưu giữ một bảng định tuyến chứa các thông tin về đường đi tới các tất cả các trạm làm việc khác mà nó có thể kết nối được. Một bảng định tuyến được thể hiện như trong hình 6: Destination Next Hop Hops Seq. No A A 0 A-846 B B 1 B-470 C B 2 C-920 D B 2 D-502 Hình 6. Bảng định tuyến của trạm làm việc trong mạng sử dụng thuật toán DSDV Trong đó: • Trường Destination liệt kê tất cả các trạm làm việc trong mạng mà nó có thể kết nối được. • Next Hop là trạm làm việc kế tiếp mà gói tin cần được gửi qua trong quãng đường đi tới trạm làm việc đích. • Hops là giá trị thước đo định tuyến (metric) dùng để đánh giá đường đi, được tính bằng số bước nhảy, của đường đi ngắn nhất mà nó tính toán được theo thuật toán Bellman-Ford. • Để đánh dấu các gói tin yêu cầu định tuyến mới, DSDV sử dụng cách đánh số thứ tự thông tin định tuyến tăng dần (sequence number) - trường Seq.No. Việc đánh số thứ tự được thực hiện bởi mỗi trạm làm việc đích khi gửi lên mạng 19 thông tin về chính nó. Chẳng hạn, trong bảng định tuyến trên, đường đi đến trạm làm việc D có số thứ tự do chính D đưa ra (D-502). Số thứ tự này luôn là số chẵn. Ở đây, D là ký hiệu trạm làm việc đã đưa ra số thứ tự này. Trong thực tế xây dựng thuật toán, số thứ tự có thể chỉ là một số tự nhiên thông thường mà không cần kèm thêm các giá trị đánh dấu cho biết trạm làm việc đã đưa ra nó. Cập nhật thông tin định tuyến Mỗi trạm làm việc định kỳ truyền đi các thông tin định tuyến tới các trạm làm việc lân cận theo cách quảng bá. Do tính chất thường xuyên thay đổi về cấu trúc của mạng ad-hoc, thời gian giữa các lần quảng bá thông tin định tuyến của mỗi trạm làm việc cần đủ ngắn để các trạm có được thông tin định tuyến chính xác tới mỗi trạm khác trong mạng. Để giảm lượng thông tin quảng bá trên mạng, thuật toán sử dụng hai cách cập nhật thông tin định tuyến: cập nhật toàn phần (full dump) và cập nhật tức thời (hay cập nhật tăng tiến - incremental). Cập nhật toàn phần được sử dụng khi một trạm làm việc muốn quảng bá toàn bộ bảng định tuyến. Cập nhật tức thời được thực hiện giữa các lần cập nhật toàn phần, khi có các thay đổi đáng kể và lượng thông tin cần cập nhật là đủ nhỏ. Các thông tin cập nhật này sẽ ngay lập tức được truyền đi. Chẳng hạn, khi có sự thay đổi về giá trị thước đo định tuyến của một đường đi thì thay đổi đó được coi là đáng kể và ngay sau khi thông tin đạt được tính ổn định (được giải thích cụ thể hơn trong phần trì hoãn quảng bá và thời gian chờ ổn định ở phần sau), nó phải được quảng bá ngay để cập nhật cho các trạm làm việc khác trong mạng. Khi thông tin mới nhận có giá trị thước đo định tuyến giữ nguyên, chỉ có thay đổi về số thứ tự định tuyến thì sự thay đổi đó không được coi là đáng kể và do vậy thông tin này không cần thiết phải được quảng bá ngay. Như đã nói, lượng thông tin cập nhật tức thời phải đủ nhỏ để có thể chỉ cần sử dụng một gói dữ liệu của mạng (network protocol data unit - NPDU) trong việc truyền dữ liệu. Nếu lượng thông tin cập nhật vượt quá một gói dữ liệu, phương thức cập nhật toàn phần sẽ được sử dụng. Khi đó toàn bộ thông tin trong bảng định tuyến sẽ được gửi đi. Một mạng cho dù có kích thước khá nhỏ thì để truyền thông tin của toàn bộ bảng định tuyến của một trạm làm việc cũng cần tới vài gói dữ liệu. Khi một mạng ổn định, nghĩa là sự di chuyển của các trạm làm việc trong mạng là rất ít, có thể hạn chế việc cập nhật toàn phần. Tần suất cập nhật toàn phần cũng cần phải giảm bớt khi lượng dữ liệu quảng bá tăng cao chiếm nhiều dung lượng đường truyền. Trong các gói tin cập nhật tức thời, thông tin định tuyến có những thay đổi về giá trị thước đo định tuyến sẽ được ưu tiên trước. Phần không gian dư thừa còn lại sẽ dành cho thông tin định tuyến chỉ có thay đổi về số thứ tự định tuyến. Nếu có quá nhiều thông tin định tuyến chỉ có thay đổi về số thứ tự định tuyến mà một gói dữ liệu của mạng không thể chứa hết thì một phần thông tin (đủ chứa trong một gói dữ liệu) sẽ được đưa vào gói dữ liệu để cập nhật tức thời. Các dòng thông tin định tuyến còn lại sẽ 20 được quảng bá trong các lần cập nhật tức thời sau đó với một cơ chế lựa chọn sao cho chúng lần lượt được quảng bá hết. Đánh giá đường đi DSDV đánh giá đường đi căn cứ vào số thứ tự định tuyến (sequence number) và giá trị thước đo định tuyến. Thông tin định tuyến nào có số thứ tự lớn hơn được đánh giá là mới hơn và được sử dụng. Mỗi khi nhận được thông tin cập nhật, trạm làm việc sẽ so sánh thông tin đó với thông tin trong bảng định tuyến mà nó lưu giữ. Nếu số thứ tự định tuyến của thông tin mới nhận được là lớn hơn thì đường đi mới sẽ được sử dụng, tương ứng với việc loại bỏ thông tin cũ trong bảng định tuyến. Khi các thông tin định tuyến nhận được có số thứ tự định tuyến là như nhau, giá trị thước đo định tuyến sẽ được áp dụng để chọn đường đi tốt hơn. Cụ thể là đường đi có giá trị thước đo định tuyến nhỏ nhất sẽ được chọn. Chẳng hạn, nếu số bước nhảy được lấy làm thước đo định tuyến thì thông tin về đường đi nào (tới cùng trạm làm việc đích, có cùng số thứ tự định tuyến) có số bước nhảy ít nhất sẽ được chọn. Giá trị thước đo định tuyến tăng lên nếu quãng đường tới trạm đích phải qua nhiều trạm làm việc. Nếu tính theo số bước nhảy thì qua mỗi trạm làm việc giá trị thước đo định tuyến sẽ tăng thêm 1 bước nhảy. Trì hoãn quảng bá và thời gian chờ ổn định Đôi khi, một trạm làm việc trong mạng nhận được thông tin có cùng số hiệu định tuyến, nhưng giá trị thước đo định tuyến lại khác nhau. Trường hợp này thường xảy ra khi mạng có kích thước lớn và mức độ thường xuyên của việc cập nhật thông tin định tuyến thấp, hoặc, khi thời gian giữa các lần cập nhật của các trạm làm việc có sự chênh lệch lớn. Hình 7 là một thí dụ minh họa một mạng ad-hoc, trong đó, F kết nối trực tiếp với hai nhóm riêng rẽ các trạm làm việc. Số lượng trạm làm việc trong nhóm 2 nhiều hơn hẳn so với nhóm 1. A cũng kết nối với hai nhóm trên thông quan B và C. Giả sử mỗi trạm làm việc cập nhật thông tin định tuyến với tần suất thấp (chẳng hạn, khoảng l lần/15 giây); B biết một đường tới F qua 12 bước nhảy, trong khi C biết đường đi tới F chỉ qua 11 bước nhảy. Thông tin truyền từ B tới A nhanh hơn so với từ C tới A. Khi đó, A sẽ nhận được thông tin định tuyến đến F do B quảng bá trước khi nhận được thông tin do C quảng bá. Việc này có thể xảy ra thường xuyên, mỗi khi F đưa ra số thứ tự định tuyến mới. Một trong những nguyên nhân là số lượng các trạm trong mỗi nhóm làm việc cũng ảnh hưởng đến thời gian nhận được thông tin cập nhật tại A, do sự lựa chọn lần lượt thông tin đưa vào gói tin cập nhật tức thời, như đã nói trong phần Cập nhật thông tin định tuyến ở trên. Vậy, thông tin định tuyến tới F mà A nhận được từ B sẽ không tốt (vì có số bước nhảy lớn hơn) so với thông tin A nhận được sau đó, từ C.