zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Quản trị mạng

Đánh giá hiệu năng định tuyến đa phát dựa trên duy trì một cách tối ưu cây khung trong mạng manet

Chia sẻ: Nguyễn Thị Ánh Ngọc | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

59
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Vấn đề định tuyến đ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 nhận được nhiều sự quan tâm. Xuất phát từ thực tế đó mà tài liệu "Đánh giá hiệu năng định tuyến đa phát dựa trên duy trì một cách tối ưu cây khung trong mạng manet" tập trung trình bày về vấn đề này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đánh giá hiệu năng định tuyến đa phát dựa trên duy trì một cách tối ưu cây khung trong mạng manet

Đõ Huy Khôi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 29 - 33 ĐÁNH GIÁ HIỆU NĂNG ĐỊNH TUYẾN ĐA PHÁT DỰA TRÊN DUY TRÌ MỘT CÁCH TỐI ƢU CÂY KHUNG TRONG MẠNG MANET Đỗ Huy Khôi, Nguyễn Thị Thu Hằng*, Dƣơng Thúy Hƣờng Trường Đại học Công nghệ thông tin và truyền thông – ĐH Thái Nguyên TÓM TẮT Vấn đề định tuyến đ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 nhận đƣợc nhiều sự quan tâm. Có nhiều hƣớng tiếp cận khác nhau trong đó vấn đề định tuyến theo nguyên tắc xây dựng cây khung và tốt nhất là các cây khung có trọng số tối thiểu. Việc áp dụng giải thuật xây dựng cây khung có trọng số tối thiểu trong mạng tĩnh vào một mạng có hình trạng mạng động nhƣ MANET là khó thực hiện nên việc nghiên cứu giải thuật xây dựng và bảo trì tối ƣu cây khung đa phát trong mạng MANET – giải thuật STM (Spanning Tree for Multicasting)- là cần thiết. Bộ công cụ mô phỏng mạng NS-2 [1,9] đƣợc sử dụng để quan sát kết quả mô phỏng, đánh giá giải thuật xây dựng và bảo trì tối ƣu cây khung đa phát trong mạng MANET so với các giao thức đa phát khác nhƣ MAODV và PUMA với số lƣợng nút lớn để đánh giá chính xác hơn về hiệu năng mạng theo các tham số nhƣ thông lƣợng, độ trễ, chi phí phụ tải,… để thể hiện sự tối ƣu của giải thuật STM nhƣ chi phí định tuyến thấp hơn, hiệu năng tốt hơn so với phƣơng pháp thông thƣờng. Từ khóa: Mạng tự hợp di động, giao thức định tuyến đa phát theo yêu cầu dựa theo vector khoảng cách, giao thức cho đa phát hợp nhất dựa vào các bản tin thông báo, cây khung đa phát MỞ ĐẦU* Trong bài báo này để đánh giá đƣợc sự tối ƣu Mạng không dây đặc biệt gọi là mạng tự hợp của giải thuật tác giả sử dụng bộ công cụ mô di động (MANET – Mobile Wireless Adhoc phỏng mạng NS-2 để mô phỏng, đánh giá, so Network) là mạng động tạm thời đƣợc thiết sánh các giải thuật đa phát STM [1], lập bằng một tập hợp các nút mạng không dây MOADV [4,8], PUMA [5] với số lƣợng nút tự trị mà không cần đến bất kỳ sự hỗ trợ về cơ lớn, hình trạng mạng động. sở hạ tầng mạng cố định cũng nhƣ hỗ trợ về THUẬT TOÁN XÂY DỰNG VÀ BẢO TRÌ quản lý tập trung. TỐI ƢU CÂY KHUNG ĐA PHÁT TRONG Trong mạng máy tính, dữ liệu có thể đƣợc MẠNG MANET truyền phát bằng ba cách khác nhau: đơn Với đặc điểm của mạng MANET là sự khan phát, phát tỏa và đa phát. Trong truyền thông hiếm của băng thông, thời gian tồn tại ngắn đa phát, định tuyến là bài toán quan trọng, có của các nút do hạn chế về năng lƣợng và cấu cách thức thực thi khó khăn và tốn chi phí trúc liên kết động của các nút nên việc xây nhiều hơn so với phát tràn (broadcast), do dựng giao thức định tuyến trong mạng phải có cơ chế điều khiển để không truyền dữ MANET là một thách thức lớn. liệu tràn lan gây lãng phí băng thông mạng, Một giao thức định tuyến có hiệu quả cho mà chỉ truyền cho một số thành viên thuộc mạng MANET, đó là áp dụng giải thuật phân cùng nhóm truyền thông. tán cho cây khung có trọng số tối thiểu nghĩa là coi mạng phân tán nhƣ là một đồ thị vô Có nhiều phƣơng pháp đƣợc đƣa ra để xây hƣớng có trọng số các cạnh là khác nhau. dựng và bảo trì tối ƣu cây khung đa phát trong đó bài toán xây dựng đƣờng đi nối tất cả các nút Giải thuật bảo trì cây khung trong mạng tĩnh trong nhóm đa phát sao cho tổng chi phí nhỏ Xét hệ phân tán là một đồ thị vô hƣớng, với nhất đang thu hút đƣợc nhiều sự quan tâm. tập các nút biểu diễn là các bộ xử lý của mạng và tập cạnh biểu diễn các liên kết truyền * Tel: 01699 831287, Email: ntthang@ictu.edu.vn thông giữa các bộ xử lý. Mỗi nút trong mạng 29
Đõ Huy Khôi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 29 - 33 có một định danh phân biệt. Mỗi liên kết thuật GHS-83 [3] để xây dựng cây khung tối trong mạng có một trọng số nhất định, giả sử thiểu nhƣ: thủ tục chuyển gốc – Change root, trọng số của liên kết là khác nhau. kết hợp mảnh – Merge, thủ tục xử lý khi cấu Trong quá trình xây dựng cây khung thủ tục hình mạng thay đổi, thủ tục xử lý khi cấu hình quan trọng nhất là kết hợp mảnh, mỗi nút ban mạng thay đổi trong quá trình kết hợp mảnh. đầu đƣợc xem là một mảnh, các mảnh này sẽ Xây dựng và bảo trì tối ƣu cây khung đa dẫn kết hợp với nhau tạo thành một mảnh lớn phát trong mạng MANET (STM) hơn dựa trên việc tìm kiếm các liên kết ngoài Cây khung trong mạng đa phát đƣợc định có trọng số tối thiểu, việc kết hợp dần các nghĩa là một đồ thị vô hƣớng, cây khung con mảnh tạo thành một cây khung hoàn chỉnh có bao trùm một tập con các nút của đồ thị gọi là trọng số nhỏ nhất. cây khung không đầy đủ hoặc cây khung đa Giải thuật bảo trì cây khung trong mạng phát (Spanning Tree for Multicast - STM). động (OMST) Lúc đó mỗi nút thuộc vào cây khung đa phát Xây dựng cây khung trong mạng động gọi là nút đa phát. (OMST) [1] gặp nhiều khó khăn hơn trong Với giải thuật STM không chỉ bao gồm quá mạng tĩnh vì hình trạng mạng thay đổi liên trình kết hợp mảnh thông qua liên kết đa phát tục nên vấn đề cập nhật thông tin để bảo trì mà còn có cả quá trình mở rộng mảnh theo cây khung là cần thiết nhƣng tốn chi phí lớn đƣờng dẫn nhỏ nhất. Sau khi kết hợp, quá hơn rất nhiều. trình mở rộng tiếp tục đƣợc lặp lại. Tại mỗi Để khắc phục nhƣợc điểm này, giải thuật xây lần lặp, mảnh STM sẽ chọn ra một nút ngoài dựng và bảo trì cây khung trong mạng động tối thiểu để kết hợp. đã đƣợc đề xuất, để tận dụng những kết quả Mỗi nút trong mạng sẽ lƣu trữ danh sách các xây dựng cây khung đã đạt đƣợc, mỗi khi có nút hàng xóm cùng với các liên kết đến các sự thay đổi trong mạng, các nút chỉ cần đáp nút đó. Có 3 loại liên kết: Mesh_Link, ứng lại bằng cách thay đổi một số trạng thái Tree_Link, Data_Link [1]. của mình cho phù hợp, không thay đổi tất cả Giải thuật STM có các bƣớc thực hiện một số cây khung. thủ tục để cập nhật các liên kết ngoài tốt nhất Để lƣu trữ thông tin về cây khung, giải thuật và thủ tục kết hợp để thiết lập liên kết mới và bảo trì cây khung trong mạng động đƣa ra mở rộng mạng. một cấu trúc dữ liệu đặc biệt để lƣu trữ trên ĐÁNH GIÁ HIỆU NĂNG CỦA MỘT SỐ mỗi nút, sử dụng để khôi phục lại cây khung GIAO THỨC ĐỊNH TUYẾN MẠNG MANET trong trƣờng hợp có những thay đổi trong Tổng quan mạng, gọi là “rừng ảo” và “cây ảo” [1]. Môi trƣờng sử dụng để đánh giá hiệu năng các Mỗi nút trong hệ thống sẽ đƣợc lƣu một giao thức trên là công cụ NS-2 [2], phiên bản “rừng ảo” trong bộ nhớ cục bộ, đó là cơ sở để allinone 2.34, chạy trên hệ điều hành UNIX. các nút tìm kiếm thông tin về liên kết ngoài có trọng số tối thiểu để kết hợp các mảnh lại Sử dụng NS2 để thực hiện đánh giá hiệu năng với nhau. Nhờ lấy đƣợc thông tin trong “rừng của giao thức STM và so sánh kết quả đánh ảo” ngay tại chính nút hiện tại nên nó giảm độ giá với hiệu năng của các giao thức định phức tạp trong quá trình kết hợp mảnh. tuyến đa phát khác nhƣ PUMA và MAODV. Hai thủ tục quan trọng nhất trong giải thuật, Để thực hiện phân tích các kết quả mô phỏng liên quan đến cấu trúc dữ liệu là thủ tục đồng thời đánh giá đƣợc hiệu năng của các UPDATE và FIND. Ngoài ra trong giải thuật giao thức STM, MAODV, PUMA cần cấu OMST còn một số thủ tục khác tƣơng tự giải hình nhƣ các thông số đƣợc chỉ rõ ở hình 1. 30
Đõ Huy Khôi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 29 - 33 tổng chi phí thông điệp vẫn giữ ở mức thấp đáp ứng cho mỗi thay đổi hình trạng mạng. - Đánh giá tỉ lệ phụ tải theo số nút tham gia Hình 1: Các tham số mô phỏng Bài báo này sẽ thực hiện cài đặt mô phỏng một mạng gồm là 50 nút và tiến hành phân Hình 4. Biểu đồ tỷ lệ phụ tải theo số nút tham gia tích đánh giá hiệu năng của các giao thức mạng bằng cách so sánh kết quả dựa trên một Biểu đồ tỷ lệ phụ tải theo số nút tham gia trên số độ đo hiệu năng nhƣ: tỷ lệ phụ tải, thông hình 4 cho thấy STM có chi phí điều khiển lƣợng trung bình, độ trễ trung bình. biến động nhiều hơn vì khi có nhiều nút tham Kết quả mô phỏng: gia mà hình trạng thay đổi liên tục, nên STM chƣa kịp đáp ứng xong, hoặc vừa kịp đáp ứng thì mạng lại thay đổi hình trạng nên số lƣợng gói tin thông báo tăng lên để xử lý các tình huống. Giao thức PUMA có sự ổn định hơn do PUMA là giao thức dựa theo lƣới nên có nhiều đƣờng đi khác nhau giữa các nút trong mạng, do đó mạng duy trì trạng thái kết nối liên tục, dù có một số liên kết bị đứt gãy, vì vậy chi Hình 2: Cây khung sau khi kết thúc mô phỏng phí thông điệp trung bình cao hơn STM. giao thức STM Đánh giá thông lƣợng trung bình Kết quả đánh giá và nhận xét - Đánh giá hiệu năng theo số nút phát Đánh giá tỉ lệ phụ tải - Đánh giá tỉ lệ phụ tải theo thời gian Hình 5: Biểu đồ biểu diễn tỷ lệ thông lượng trung bình theo số nút phát Trên biểu đồ hình 5 có thể nhận thấy cả ba Hình 3. Biểu đồ tỷ lệ phụ tải theo thời gian giao thức đều có thông lƣợng trung bình tăng Biểu đồ hình 3 cho thấy STM có tỷ lệ phụ tải lên theo số nút nguồn. Trong đó, STM có thấp hơn so với PUMA và MAODV. Biểu đồ thông lƣợng trung bình cao hơn. Do STM và thể hiện sự tối ƣu khi thay đổi về thời gian thì MAODV quản lý theo cây nên gói tin sẽ đi 31
Đõ Huy Khôi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 29 - 33 theo các nhánh để đến đích, số lƣợng gói tin bị xung đột nhỏ và phải truyền lại thấp hơn, thông lƣợng cao hơn. Còn MAODV do quản lý theo lƣới, khi truyền theo broadcast gói tin sẽ truyền đi tất cả các liên kết trên mạng nên số lƣợng gói tin rất lớn tỷ lệ xung đột và phải truyền lại cao nên thông lƣợng của nó giảm hơn so với hai giao thức trên. - Đánh giá hiệu năng so với số nút tham gia Hình 8: Biểu đồ biểu diễn độ trễ theo số nút tham gia Trong hai đồ thị thể hiện trên hình 7 và hình 8 cho thấy MAODV có độ trễ cao hơn đáng kể so với STM và PUMA. Nhƣ vậy, khi số lƣợng nút tham gia vào mạng lớn thì giao thức STM và PUMA tốt hơn so với MAODV khi đánh giá theo các tiêu chí về độ trễ. KẾT LUẬN Với các kết quả đạt đƣợc, STM chứng minh Hình 6: Biểu đồ biểu diễn tỷ lệ thông lượng trung rằng một giao thức dựa theo cây cũng có thể bình theo số nút tham gia đạt đƣợc tỉ lệ truyền và độ trễ tốt tƣơng đƣơng Trong hai biểu đồ hình 6 ta thấy tỉ lệ thông với các giao thức dựa theo lƣới, nếu giao thức lƣợng trung bình của MAODV đạt cao hơn so có thể đáp ứng đƣợc sự thay đổi mạng kịp với STM và PUMA. Điều này chứng tỏ ƣu thời với tổng chi phí thông điệp là nhỏ nhất, thế của MAODN quản lý theo lƣới trong dẫn đến tổng chi phí thời gian cũng đƣợc giảm thiểu. STM sử dụng phù hợp với các trƣờng hợp có nhiều nút tham gia và hình mạng động ít thay đổi hình trạng mạng và có trạng mạng thay đổi lớn, nó sẽ đáp ứng nhanh số lƣợng thành viên khá lớn. hơn trong trƣờng hợp liên kết bị đứt và số lƣợng gói tin lớn có thế đi theo nhiều đƣờng, TÀI LIỆU THAM KHẢO điều này tốt hơn hẳn so với hai giao thức 1. Nguyễn Trung Hải (2010), Định tuyến đa phát MAODV và STM quản lý theo cây. dựa trên bảo trì tối ưu cây khung trong mạng tự hợp di động, Luận Văn Thạc sĩ, Trƣờng Đại học Đánh giá độ trễ trung bình truyền thông Công nghệ, Đại học Quốc gia Hà Nội. - Độ trễ trung bình theo thời gian, số nút 2. Nguyễn Đình Việt (2008), Bài giảng đánh giá hiệu nặng mạng máy tính, Trƣờng Đại học Công phát, số nút tham gia nghệ, Đại học Quốc gia Hà Nội. 3. Gallagher, Humblet, and Spira, (Jan. 1983). A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems 5. 4. E. Royer and C. Perkins, (August 1999) “Multicast operation of the ad hoc on-demand distance vector routing protocol,” in Proceedings of Mobicom. 5. Ravindra Vaishampayan, Efficient and Robust Multicast Routing in Mobile Ad hoc Networks, University of California, March 2006. 6. Baruch Awerbach, Israel Cidon, Shay Kutten, (2008). Optimal Maintenance of a Spanning Tree, Hình 7: Biểu đồ biểu diễn độ trễ theo số nút phát January 13. 32
Đõ Huy Khôi và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 29 - 33 7. Shuhui Yang and Jie Wu, New Technologies of 8. Yufang Zhu, (2002)Pro-Active Connection Maintenance In Aodv And Maodv. Multicasting in MANET, Florida Atlantic 9. The Network Simulator - ns-2: University, Boca Raton. http://www.isi.edu/nsnam/ns/ SUMMARY EVALUATION OF MULTICAST ROUTING PERFORMANCE BASED ON OPTIMAL MAINTENANCE OF A SPANNING TREE IN MANET Do Huy Khoi, Nguyen Thi Thu Hang*, Duong Thuy Huong College of Information and Communication Technology - TNU The multicast routing and multicast routing protocol in MANET is one of the most direction researches received much attention. There are many different approaches to routing, however the principles to building spanning tree and Minimum-Weight Spanning Trees happens to be the best choice. Applying Minimum-Weight Spanning Trees algorithm in static network into a dynamic network topologies such as MANET is difficult to perform, so a researching algorithm for building and optimally maintaining a spanning tree for multicasting in MANET – STM algorithm (Spanning Tree for Multicasting) – is necessary. The network simulation tool NS-2 is used to observe the results of simulation and evaluate algorithms for building and optimally maintaining a spanning tree for multicasting in the MANET compared with other multicasting protocols as MAODV and PUMA with a large number of nodes to more exactly evaluate network performance the parameters such as throughput, latency, load cost, ... to show the optimal algorithm STM as lower-cost routing, better performance than conventional methods. Keywords: Mobile adhoc network, Multicast Adhoc On-demand Distance Vector, Protocol for Unified Multicasting through Annoucements, multicast spanning tree Ngày nhận bài:25/01/2014; Ngày phản biện:10/02/2014; Ngày duyệt đăng: 26/02/2014 Phản biện khoa học: TS.Phùng Trung Nghĩa – Trường ĐH Công nghệ Thông tin & Truyền thông - ĐHTN * Tel: 01699 831287, Email: ntthang@ictu.edu.vn 33

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.