Nghiên cứu cây R+ cho định tuyến phân cấp đảm bảo chất lượng dịch vụ với định tuyến đa đường đa truyền phát

Bài báo sẽ tập trung nghiên cứu và đánh giá: (i) Áp dụng cây R để quản lý cấu hình mạng theo mô hình phân cụm phân cấp với các bộ điều khiển mạnh tại các điểm nút quản lý nhóm; (ii) Tạo cây đa truyền phát từ nút quản lý nhóm đến các nút thành viên tăng hiệu suất truyền; (iii) Tạo các tuyến tối ưu sử dụng thuật toán ACO (tối ưu hóa đàn kiến); (iv) Sử dụng mạng neuron nhân tạo để tối ưu ư. Mạng neuron là một kỹ thuật mới thuộc ngành trí tuệ nhận tạo, được sử dụng nhiều trong khoa học để phân cụm và nhận dạng.
Nội dung trích xuất từ tài liệu:
Nghiên cứu cây R+ cho định tuyến phân cấp đảm bảo chất lượng dịch vụ với định tuyến đa đường đa truyền phát Công nghệ thông tin & Cơ sở toán học cho tin học NGHIÊN CỨU CÂY CHO ĐỊNH TUYẾN PHÂN CẤP ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ VỚI ĐỊNH TUYẾN ĐA ĐƯỜNG ĐA TRUYỀN PHÁT Nguyễn Thành Long1*, Nguyễn Đức Thuỷ2, Phạm Huy Hoàng3* Tóm tắt: Hiện tại vấn đề định tuyến hướng dịch vụ là cấp thiết, trong đó, vấn đề phân cụm trong định tuyến được đặt ra nhưng thường được giải quyết chưa tổng quát. Thường các tác giả chỉ đặt ra số cố định các mức, như là hai hoặc ba mức phân cấp. Vì vậy, giải pháp đưa ra thường là khó phát triển khi mạng trở nên phức tạp. Bài báo đề cập đến mô hình định tuyến phân cụm phân cấp tổng quát và một số cách để tối ưu việc phân cụm và tìm đường đi trong hệ thống mạng. Tương tự như định tuyến hướng nội dung, trong định tuyến hướng dịch vụ thì thông tin sẽ được tổ chức theo lớp, hoặc theo dịch vụ. Tuy nhiên, định tuyến lớp trên dựa trên định tuyến từ các lớp dưới để đưa ra quyết định. Bài báo sẽ tập trung nghiên cứu và đánh giá: (i) Áp dụng cây R để quản lý cấu hình mạng theo mô hình phân cụm phân cấp với các bộ điều khiển mạnh tại các điểm nút quản lý nhóm; (ii) Tạo cây đa truyền phát từ nút quản lý nhóm đến các nút thành viên tăng hiệu suất truyền; (iii) Tạo các tuyến tối ưu sử dụng thuật toán ACO (tối ưu hóa đàn kiến); (iv) Sử dụng mạng neuron nhân tạo để tối ưu phân cụm mạng. Mạng neuron là một kỹ thuật mới thuộc ngành trí tuệ nhận tạo, được sử dụng nhiều trong khoa học để phân cụm và nhận dạng. Từ khoá: MANET, , Dịch vụ, Định tuyến, Đa đường, Băng thông, Cụm, tree, Multicast, QOS, Overhead, Mạng nơ ron. 1. MÔ HÌNH MẠNG PHÂN CỤM PHÂN CẤP Quản lý mạng phân cụm phân cấp trong mạng di động với các nút thường xuyên thay đổi vị trí, các thủ tục để chấp nhận nút vào mạng và các nhóm phải thực hiện nhanh và hiệu quả. Các nút phải trao đổi thông tin định kỳ, hoặc khi có yêu cầu. Để phân cụm ta phải đưa ra điều kiện, trong bài viết sử dụng mạng Neuron để đánh giá nút có thuộc cụm và chọn trưởng cụm. Các cụm được hình thành ban đầu là tại mức lá của cây R, với nút trưởng cụm là nút lá. Để tạo nên mô hình phân cấp, các nút lá được gom lại thành các nhóm cũng như cách trên để hình thành các cụm cấp trên, mỗi nhóm có trưởng cụm là các nút trong của cây. Cứ hình thành dần lên trên ta có nút gốc cây sẽ quản lý mạng lớp trên cùng. Để đánh giá liên kết và tuyến trong mạng ta sử dụng thuật toán tối ưu lập cụm đàn kiến (ACO). Mỗi liên kết và tuyến sẽ có 1 xác suất tồn tại được xác định. Xác suất này được tính toán theo ACO. Khi xác suất nhỏ thì khả năng tồn tại thấp, do vậy, phải tìm nhiều tuyến giữa mỗi cặp nút (nguồn, đích). Khi cần truyền từ 1 nút đến 1 tập các nút ta hình thành cây đa truyền phát giữa nút cần truyền và tập các nút đích từ tập các tuyến tìm được bằng ACO. Khi đó có thể truyền đồng thời trên các tuyến có đảm bảo chất lượng để tăng hiệu suất. Để quản lý mạng phân cụm phân cấp hiệu quả có nhiều cách các tác giả đã đề ra. Nhưng các giải pháp này còn chưa giải quyết triệt để vấn đề cập nhật mạng và tìm đường đi tối ưu. Bài báo đề nghị dùng cấu trúc cây R để quản lý mô hình mạng này. Cây R là cây cân bằng và có số nút trên mỗi nhánh con là khá ổn định. Ngoài ra, các thuật toán để tìm kiếm và hình thành cây khá dễ dàng và đã có sẵn. Thời gian tìm kiếm trên cây này gần như không tăng khi số mức của cây tăng dựa trên kết quả thực nghiệm của các bài báo trước đây. Tuy nhiên, cây R luôn duy trì tính ổn định nội tại, khi thêm bớt nút cây sẽ được điều chỉnh lại để giữ cân bằng. Việc thêm nút vào cây luôn được thực 106 N. T. Long, N. Đ. Thủy, P. H. Hoàng, “Nghiên cứu cây R+… đa đường đa truyền phát.” Nghiên cứu khoa học công nghệ hiện tại nút lá, nút lá là nút tại mức cuối cùng trong cây để quản lý toàn bộ các phần tử cần quản lý đó là các nút mạng hay các thiết bị viễn thông di động. Các phần tử cần quản lý là bất kỳ thứ gì trong thực tế như nút mạng, dữ liệu thông thường, quá trình các nút được chấp nhận vào mỗi cụm theo các thuật toán sẽ được trình bày trong phần tiếp theo … Vậy dùng cây R để quản lý mạng ta sẽ có: nút lá quản lý các phần tử mạng, các nút lá tiếp tục lập cụm và chọn ra phần tử quản lý nhóm hình thành nhóm lớp trên. Hệ thống các nút trong quản lý phân cấp, phần tử mạng cấp trên quản lý các phần tử mạng cấp dưới. Cứ như vậy cho đến nút gốc quản lý toàn bộ cây. Tuy nhiên, nút gốc của nhiều cây R hợp tác lại để quản lý các hệ thống mạng lớn hơn. Trong bài viết không đưa ra khái niệm nút trìu tuợng mà sử dụng luôn các nút mạng làm nút quản lý điều này rất phù hợp với môi trường mạng phân cấp. Tuy vậy, chọn nút quản lý phải tuân theo các điều kiện nhất định và phải được tối ưu như sử dụng logic mờ, như đã đề cập trong bài viết [6]. Ví dụ: ban đầu chỉ có 1 nút thì nút sẽ có mọi chức năng, gốc, lá, thành phần, nút trong, quản lý nhóm. Vì là quản lý nhóm nên nút sẽ phát ra thông điệp cho phép tham gia nhóm. Khi có một nút nào đó đến gần cũng phát ra thông điệp HELLO, hai bên sẽ bắt tay và nút mới sẽ gia nhập mạng có 2 nút. Lúc này 2 nút đàm phám tìm ra trưởng nhóm mới. Do nút mới có thể đạt được tiêu chí làm trưởng nhóm hơn. Lúc đó trưởng nhóm mới sẽ phát ra thông điệp mời gia nhập, nút thành viên có kết nối với trưởng nhóm. Khi số thành viên của nhóm ban đầu đạt được ngưỡng quy định nhóm sẽ phân đôi. Số thành viên của mạng lúc này được tìm theo công thức: N= + +3 (1) và lá số phần tử của 2 nhóm con vừa hình thành. , đều thuộc khoảng [m, M] là số nút có thể trong mỗi nhóm. Các nút khi kết nạp dần vào 2 nhóm con khi đạt đến ngưỡng M sẽ lại được tách ra thành 2 nhóm. Do vậy, giá trị m phải thuộc khoảng [0, ]. Khi số phần tử trong nhóm bằng m-1, nhóm sẽ bị huỷ để thêm các nút của cụm vào cây theo thuật toán thêm nút. Cứ nh ...