Mở đầu Với sự phát triển không ngừng của các thiết bị máy tính cá nhân xách tay và các thiết bị truyền dữ liệu không dây với giá thành ngày càng rẻ, truyền thông không dây giữa những ngƣời dùng di động đang càng ngày càng trở nên phổ biến, với mức nhu cầu truyền nhận dữ liệu càng cao, nhƣ truyền dữ liệu đa phƣơng tiện, dữ liệu hội nghị truyền hình… Do tính chất di động của các thiết bị, đôi khi việc thiết lập mạng truyền không cần sự giúp đỡ của các thiết bị hạ tầng cơ sở cố định, nhƣ các trạm phát cơ sở (base station) hoặc điểm truy cập (access point). Thay vào đó, ngƣời dùng có thể thiết lập các mạng không dây di động ngang hàng của riêng họ. Những mạng này đƣợc gọi là mạng tự hợp di động (mobile ad hoc network- MANET). Năm 2003, Chlamtac, Conti và Liu [1] đã đƣa ra khái niệm chính thức về mạng MANET, là mạng động tạm thời đƣợc thiết lập bằng một tập hợp các nút mạng không dây di động tự trị mà không cần bất kì sự hỗ trợ về cơ sở hạ tầng mạng cố định cũng nhƣ hỗ trợ về quản lí tập trung.
Các nút mạng tự do di chuyển một cách ngẫu nhiên và tự tổ chức chính nó bằng một số qui luật chung, do đó, hình trạng mạng có thể thay đổi một cách đột ngột và không thể đoán trƣớc. Hơn nữa, các thiết bị không dây di động có sự hạn chế về không gian truyền, năng lƣợng và năng lực vi xử lí, làm cho toàn bộ mạng MANET có các đặc tính rất tự nhiên nhƣ mạng động, băng thông thấp, tỉ lệ mất gói cao, giới hạn năng lƣợng… (theo Kaliaperumal và Jeyakumar [2]). Do đó, vấn đề lựa chọn thiết kế giao thức truyền thông trong mạng MANET đóng vai trò cốt lõi để đảm bảo chất lƣợng dịch vụ mạng. Mạng MANET càng ngày càng có nhiều ứng dụng thực tế, nhƣ hội nghị nhóm, các ứng dụng khẩn cấp nhƣ cứu hộ, chia sẻ dữ liệu lớn.
Đặc biệt trong các ứng dụng chia sẻ dữ liệu, một nút mạng có thể chia sẻ dữ liệu cho rất nhiều nút lân cận cùng lúc, do bản chất truyền đa hƣớng của sóng không dây. Tính chất này làm cho các ứng dụng chia sẻ dữ liệu và truyền thông kiểu phát tỏa (broadcast) và đa phát (multicast) đƣợc quan tâm nghiên cứu và phát triển nhiều hơn. Trong đó, truyền thông đa phát có cách thức thực thi khó khăn và tốn chi phí nhiều hơn so với phát tràn, do phải có cơ chế điều khiển để không truyền dữ z 6 liệu tràn lan gây lãng phí băng thông mạng, mà chỉ truyền cho một số thành viên thuộc cùng nhóm truyền thông. Vì thế, nghiên cứu về đa phát và các giao thức định tuyến đa phát trong mạng MANET là một trong những hƣớng nghiên cứu thu hút đƣợc nhiều sự quan tâm.
Có nhiều các ý tƣởng, giao thức và cách thức tiếp cận khác nhau đƣợc đƣa ra, nhƣng hiện nay vẫn chƣa có một chuẩn chính thức đƣợc công nhận rộng rãi về mặt học thuật lẫn ứng dụng công nghiệp. Luận văn này hƣớng đến nghiên cứu vấn đề một vấn đề quan trọng của định tuyến đa phát trong mạng MANET: duy trì và bảo toàn hình trạng mạng với chi phí tối thiểu, đảm bảo kết nối đƣợc liên tục và chất lƣợng, bằng hƣớng tiếp cận ứng dụng các kết quả nghiên cứu mới nhất trong lĩnh vực tính toán phân tán áp dụng cho mạng MANET, từ đó xây dựng nên một giao thức định tuyến đa phát mới, đáp ứng đƣợc yêu cầu của một giao thức định tuyến đa phát với kết quả tối ƣu về một số thông số đƣợc trình bày ở các phần sau.2 Vấn đề nghiên cứu Trong định tuyến đa phát, việc duy trì và bảo toàn hình trạng mạng nhằm đảm bảo sự truyền thông đƣợc liên tục và bảo đảm chất lƣợng dịch vụ là một vấn đề then chốt đƣợc hầu hết các nghiên cứu quan tâm đến. Có nhiều tƣ tƣởng và hƣớng tiếp cận khác nhau đƣợc đặt ra để giải quyết vấn đề này. Một trong những hƣớng tiếp cận cơ bản và có tính nền tảng là dựa theo lý thuyết đồ thị, trong đó xem xét mạng MANET là một đồ thị có trọng số vô hƣớng và mạng truyền dữ liệu là một cây nối tất cả các nút trong đồ thị.
Do từng tính chất của mạng MANET mà yêu cầu xây dựng cây có sự khác biệt, một số mạng chỉ truyền thông đa phát theo kiểu môt-nhiều, trong đó một nút gửi và nhiều nút nhận, lúc đó cây xây dựng hƣớng vào nút gửi (mô hình Source Based Tree); một số mạng khác xem toàn bộ các nút trong cây là bình đẳng (mô hình Shared Tree) và truyền thông theo kiểu nhiều-nhiều. Luận văn đặt ra vấn đề nghiên cứu truyền thông nhiều-nhiều, do các ứng dụng nhƣ hội nghị truyền hình, trong đó mọi thành viên đều có thể phát biểu và truyền dữ liệu, càng ngày càng trở nên phổ biến hơn, thay vì chỉ có một nguồn gửi dữ liệu duy nhất. Theo lí thuyết đồ thị, bài toán trở thành xây dựng và bảo trì cây khung nhỏ nhất, lúc đó, chi phí về truyền dữ liệu sẽ đƣợc tối ƣu nhất. Tuy nhiên, cây khung dùng trong định tuyến đa phát (từ đây gọi là cây khung không đầy đủ hay cây khung đa phát) không giống hoàn toàn với cây khung nhỏ nhất thuần túy, lí do là chỉ có một số nút mạng thuộc nhóm đa phát để gửi nhận dữ z 7 liệu, một số nút khác chỉ đóng vai trò định tuyến và chuyển tiếp gói tin chứ không trực tiếp nhận dữ liệu, nếu áp dụng nguyên bản tƣ tƣởng cây khung nối tất cả các nút mạng lại với nhau, thì sẽ không tối ƣu về chi phí đƣờng truyền nếu chuyển tiếp gói tin cho những nút không thuộc nhóm đa phát.
Do đó cần đƣa ra một giải pháp tiên tiến hơn để giải quyết vấn đề trên. Một số nghiên cứu cũng đặt ra vấn đề tƣơng tự, tuy nhiên hiệu suất của giao thức vẫn chƣa tối ƣu, chi phí phụ tải cho điều khiển mạng lớn. Luận văn đƣa ra một hƣớng tiếp cận hoàn toàn mới, áp dụng các thành tựu mới nhất trong lĩnh vực tính toán phân toán để đƣa ra giao thức xây dựng và bảo trì cây khung đa phát với chi phí tối thiểu hóa, cây khung đa phát đƣợc bảo trì là cây khung xấp xỉ nhỏ nhất có thể đƣợc.3 Phƣơng pháp luận Luận văn đƣợc thực hiện dựa trên các thành quả mới nhất trong lĩnh vực tính toán phân tán[11][12], trong đó giảm thiểu chi phí bảo trì hình trạng mạng từ giá trị O(E) với E là số cạnh của đồ thị sang O(V) với V là số đỉnh, trong một mạng dày đặc giá trị O(E) đạt xấp xỉ O(V)2; giá trị O(V) là giá trị tối ƣu nhất có thể có đƣợc đối với một mạng có V nút. Kết quả này đƣợc ứng dụng trong nghiên cứu xây dựng và bảo trì cây khung trong mạng động nhằm tối thiểu hóa chi phí điều khiển mạng, từ đó đƣa ra các thành quả mới trong xây dựng và bảo trì cây khung đa phát cũng với chi phí tối thiểu hóa.
Kết quả độ phức tạp đƣợc chứng minh về mặt lí thuyết bằng toán học, đồng thời so sánh đánh giá hiệu năng thực nghiệm với các giao thức tƣơng tự. Từ xây dựng một giải thuật toán học thành một giao thức thực tế, luận văn cũng giải quyết rất nhiều vấn đề liên quan đến bài toán đồng bộ xử lí tính toán và khắc phục lỗi. Để xây dựng giao thức mạng thực tế, luận văn đi vào tìm hiểu chi tiết tƣ tƣởng và phƣơng thức hoạt động của nhiều giao thức đa phát trên mạng MANET tƣơng tự, từ đó định hình nên các bƣớc giao tiếp chính của giao thức mới. Từ đó, giao thức đƣợc cài đặt trên bộ công cụ mô phỏng mạng NS-2[3], cung cấp kết quả thực thi trên NS- 2 để làm số liệu so sánh đánh giá hiệu năng thực nghiệm với các giao thức phổ biến tƣơng tự nhƣ MAODV[9] và PUMA[13], để chứng minh tính ƣu việt về tỉ lệ phát thành công gói tin, độ trễ thấp không hề thua kém các giao thức khác, thậm chí có những thông số ƣu việt hơn, trong khi chi phí điều khiển giao thức lại thấp hơn rất nhiều.
Cuối cùng các kết luận và một số phƣơng hƣớng cải tiến giao thức đƣợc đƣa ra để hoàn thiện hơn giải pháp.4 Tổ chức luận văn Luận văn đƣợc bố cục theo các chƣơng chính sau: - Chƣơng 1: Giới thiệu: Cung cấp tổng quan về luận văn, từ vấn đề cần đặt ra, đến hƣớng tiếp cận, cách thức tổ chức giải quyết vấn đề. - Chƣơng 2: Trình bày chi tiết về đa phát và đa phát trong mạng MANET. - Chƣơng 3: Trình bày sâu về bài toán xây dựng và bảo trì tối ƣu cây khung trong mạng động. - Chƣơng 4: Cải tiến giải thuật xây dựng và bảo trì tối ƣu cây khung trong mạng động - Chƣơng 5: Đề xuất giải pháp mới cho vấn đề cây khung đa phát trong mạng MANET.
- Chƣơng 6: Các kết quả đạt đƣợc: Cài đặt, so sánh và đánh giá giải pháp mới. - Chƣơng 7: Kết luận và các hƣớng nghiên cứu tiếp theo. z 9 CHƢƠNG 2 - ĐA PHÁT TRONG MẠNG MANET 2.1 Giới thiệu Trong mạng máy tính nói chung và mạng IP nói riêng, dữ liệu có thể đƣợc truyền phát bằng ba cách khác nhau: đơn phát, phát tỏa và đa phát. Đơn phát là kiểu truyền thông đơn giản và phổ biến nhất, tạo ra liên kết dữ liệu một-một giữa hai thực thể mạng đơn.
Rất nhiều các ứng dụng hiện nay nhƣ HTTP, SMTP, FTP… dựa trên định tuyến đơn phát. Phát tỏa là cơ chế phát từ một thực thể mạng cho toàn bộ các thực thể khác cùng thuộc mạng đó, tạo ra liên kết kiểu một-tất cả. Các ứng dụng trên mạng diện rộng thƣờng khó áp dụng cơ chế phát tỏa, thay vào đó, các ứng dụng ở mức cục bộ hóa, nhƣ ARP (Address Resolution Protocol) sử dụng cơ chế phát tỏa. Đa phát là khái niệm có thể xem nhƣ nằm giữa đơn phát và phát tỏa, trong đó một thực thể mạng đơn có thể gửi dữ liệu cho nhiều (nhƣng không phải tất cả) các thực thể mạng khác, tạo ra liên kết dữ liệu một-nhiều hoặc nhiều-nhiều.
Ứng dụng đa phát trở nên phổ biến hơn trong mạng máy tính xuất phát từ yêu cầu thực tế ngày càng nhiều, ví dụ việc phân phối cùng một nội dung (bản cập nhật phần mềm, hội nghị từ xa, cung cấp dịch vụ nội dung số.