Tài liệu Tóm tắt luận văn thạc sĩ kỹ thuật ứng dụng giải thuật di truyền mờ cho bài toán quản lý hàng đợi tích cực (aqm) trong viễn thông

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP  TÓM TẮT LUẬN VĂN THẠC SỸ KỸ THUẬT NGÀNH KỸ THUẬT ĐIỆN TỬ Mà SỐ: 605270 øNG DôNG GI¶I THUËT DI TRUYÒN Mê CHO BµI TO¸N QU¶N Lý HµNG §îI TÝCH CùC (AQM) TRONG VIÔN TH¤NG LÊ HOÀNG Thái Nguyên, 2010 Công trình được hoàn thành tại Đại học Kỹ thuật công nghiệp Thái Nguyên Người HD khoa học: PGS.TS. Lê Bá Dũng Người phản biện 1: PGS. TS. Nguyễn Hữu Công Người phản biện 2: PGS. TS. Nguyễn Quốc Trung Luận văn này sẽ được bảo vệ tại hội đồng chấm Luận văn tốt nghiệp Thạc sỹ ngành Kỹ thuật điện tử tại Đại học Kỹ thuật công nghiệp Thái Nguyên ngày …. tháng …. năm 2010. Có thể tìm hiểu luận văn tại: - Trung tâm học liệu - Đại học thái Nguyên. - Thư viện trường Đại học kỹ thuật công nghiệp LỜI NÓI ĐẦU Ngành Điện tử viễn thông luôn phải đáp ứng một nhiệm vụ quan trọng là cung cấp các dịch vụ truyền thông tin xa một cách mềm dẻo, nhanh chóng và chính xác nhất. Để đáp ứng nhiệm vụ trên, vấn đề quản lý hàng đợi tích cực luôn được đặt lên hàng đầu. Tuy nhiên việc quản lý hàng đợi tích cực luôn là vấn đề phức tạp. Xuất phát từ các vấn đề trên, tác giả chọn đề tài: “Ứng dụng giải thuật di truyền mờ cho bài toán quản lý hàng đợi tích cực (AQM) trong viễn thông”. Nội dung chính của luận văn này tập trung vào nghiên cứu việc xây dựng phương pháp để giải quyết các bài toán điều khiển lưu lượng thông minh trên mạng viễn thông hiện tại. Nhằm giải quyết được vấn đề tránh tắc nghẽn và tối ưu hoá thời gian truyền nhận các gói dữ liệu thông qua các router trên mạng. Cấu trúc luận văn bao gồm các chương sau: Chƣơng 1: Trình bày về các kiến thức tổng quan liên quan tới các lĩnh vực mà đề tài cần sử dụng bao gồm: TCP và AQM, giải thuật di truyền. Mô hình kết hợp giữa giải thuật di truyền và logic mờ nhằm giải quyết một số bài toán phức tạp. Đánh giá được ưu điểm nổi trội của giải thuật di truyền mờ nhằm tối ưu hoá luật mờ và vét cạn các lời giải. Chƣơng 2: Tìm hiểu về bài toán quản lý hàng đợi tích cực (AQM) trong mạng viễn thông hiện nay. Những phương pháp và thuật toán đã và đang được sử dụng, đánh giá được ưu nhược điểm của từng phương pháp. Minh chứng về những điểm yếu trong AQM hiện nay. Đề xuất một phương pháp sửa đổi thuật toán điều khiển tắc nghẽn nhằm đạt kết quả tốt hơn. Chƣơng 3: Tiếp tục giải quyết bài toán trong chương 2 bằng việc sử dụng mô hình mới kết hợp giữa giải thuật di truyền và logic mờ, đưa ra đánh giá thông qua các kết quả đạt được so với các phương pháp trước đó. Từ đó đưa ra kết luận có thể hay không thể áp dụng phương pháp này cho các thiết bị viễn thông và internet hiện tại. Cuối cùng là kết luận và hướng phát triển của đề tài. Trang 1 CHƢƠNG 1 CÁC KIẾN THỨC TỔNG QUAN 1.1 Giới thiệu Sự thành công của Internet như ngày nay chủ yếu là do sức mạnh của các giao thức. Tỷ lệ mất gói tăng và chất lượng mạng giảm đã gây ra những vấn đề nghiêm trọng đối với người dùng. Ngoài ra, không có khả năng hỗ trợ các dịch vụ mới đã cản trở nghiêm trọng việc triển khai rộng rãi các ứng dụng nhạy cảm về băng thông. Luận án này tập trung vào những thách thức cực kỳ quan trọng với Internet ngày nay và mô tả việc điều khiển tắc nghẽn hiện nay như thế nào và kỹ thuật AQM có thể được sửa đổi để giải quyết điều đó. 1.2 Tổng quan về AQM và TCP 1.2.1 TCP và quản lý hàng đợi tích cực (AQM) TCP sử dụng một bộ các giải thuật điều khiển tắc nghẽn: Khởi đầu chậm (slow start), tránh tắc nghẽn (congestion avoidance), truyền lại nhanh (fast retransmission) và khôi phục nhanh (fast recovery). Những giải thuật này rất quan trọng và cùng kiến tạo nên bộ khung cho cơ chế kiểm soát nghẽn của TCP. Hình 1.1 Ví dụ về hành vi cửa sổ tắc nghẽn TCP Hình 1.1 minh hoạ về phương thức TCP slow-start và hoạt động tránh tắc nghẽn. Như hình vẽ cho thấy, đầu tiên TCP bắt đầu với một cửa sổ tắc nghẽn 1. Cửa sổ đó được tăng gấp đôi sau mỗi RTT. Khi cửa sổ tắc nghẽn đạt SSTHRESH, TCP làm chậm tốc độ tăng của nó. Cuối cùng, khi tốc độ truyền của kết nối vượt quá kết nối cổ chai, các gói bị mất. Sự mất gói này được phát hiện bởi TCP sau đó phản ứng bằng cách giảm một nửa cửa sổ tắc nghẽn. Như hình vẽ cho thấy, sau khi phục hồi từ tắc nghẽn, bên gửi TCP bước vào giai đoạn tránh tắc Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 2 nghẽn vì thế cửa sổ được tăng tuyến tính với tốc độ mỗi segment trên RTT. Trong trạng thái ổn định, TCP dao động giữa cửa sổ W và W/2, ở đây W phụ thuộc vào khả năng của mạng và số lượng các kết nối hiện đang hoạt động trong kết nối cổ chai. Hình 1.3 Các hành vi mất gói/đánh dấu gói của Red Xác suất mất gói/đánh dấu của Red như là một hàm của chiều dài hàng đợi trung bình (hình 1.3). Như hình vẽ cho thấy, khi chiều dài hàng đợi trung bình vượt quá ngưỡng tối thiểu (minth), các gói bị mất hoặc đánh dấu ngẫu nhiên bằng một xác suất cho trước. Xác suất là 0 khi chiều dài hàng đợi trung bình là nhỏ hơn hoặc bằng minth và tăng tuyến tính tới maxp khi chiều dài hàng đợi trung bình gần ngưỡng tối đa (maxth). Khi chiều dài hàng đợi trung bình vượt quá maxth, tất cả các gói dữ liệu bị mất hoặc đánh dấu. 1.3 Giải thuật di truyền 1.3.1 Giới thiệu Giải thuật di truyền (Genetic Algorythm) do D.E. Goldberg đề xuất, được L. Davis và Z. Michalevicz phát triển lần đầu ở Hà Lan trên cơ sở các thuật toán tiến hoá, được xây dựng trên cơ sở học thuyết Darwin cho chọn lọc tự nhiên. Thuật toán di truyền là thuật toán tối ưu ngẫu nhiên dựa trên cơ chế chọn lọc tự nhiên và tiến hóa di truyền. Nguyên lý cơ bản của thuật toán di truyền đã được Holland giới thiệu vào năm 1962. Thuật giải di truyền cung cấp một cách tiếp cận cho việc học dựa vào mô phỏng sự tiến hóa. Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép và đột biến ngẫu nhiên sau đó là sinh sản và chọn lọc lấy các mẫu tốt nhất sau các quá trình “đấu tranh sinh tồn” và “tiến hoá” sinh học. Chương 1: Các kiến thức tổng quan Trang 3 1.3.3 Cấu trúc một giải thuật di truyền Một giải thuật đơn giản cho những kết quả tốt trong nhiều bài toàn thực tế bao gồm ba thao tác: sinh sản, lai ghép và đột biến. Ba hoạt động sinh sản, lai ghép và đột biến được chứng minh là rất đơn giản và hiệu quả trong việc giải quyết một số vấn đề tối ưu hoá quan trọng. Ngoài ra, còn có phép toán chọn lọc, nhằm lọc ra các kết quả tốt nhất trong quần thể. 1.3.4 Ứng dụng của giải thuật di truyền Thuật toán di truyền đã chứng tỏ tính hữu ích của nó khi được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của cuộc sống. 1.4 Giải thuật di truyền mờ 1.4.1 Giới thiệu Trong chương này, trình bày về mô hình kết hợp giữa giải thuật di truyền và logic mờ để tận dụng các ưu điểm của mỗi kỹ thuật đơn lẻ. 1.4.2 Giải thuật di truyền kết hợp với logic mờ Việc kết hợp giữa giải thuật di truyền và logic mờ là một lĩnh vực mới và ít được khai thác thác hơn so với việc kết hợp giữa giải thuật di truyền hoặc logic mờ với mạng nơron. Giải thuật di truyền và logic mờ có một vài đặc điểm chung và riêng. Cả hai kỹ thuật đều thích hợp với việc xử lý bộ dữ liệu dùng cho các hệ thống phi tuyến. Sử dụng hai kỹ thuật này giúp cải tiến hiệu suất của hệ thống: tối ưu kết quả và tốc độ thực hiện. 1.4.3 Tổng kết và kết luận Logic mờ có một số ưu điểm trong việc cải tiến các hệ thống thông minh cho phép biểu diễn minh bạch tri thức dưới dạng những công thức rõ ràng hoặc dưới dạng các biểu diễn toán học ngắn gọn. Giải thuật di truyền hoạt động tốt trong những môi trường tương tự với những môi trường dùng cho các hệ thống mờ, nhằm giải quyết các bài tán phi tuyến hoặc những bài toán đòi hỏi hiệu suất cao. Giải thuật di truyền cho phép kết hợp các luật cố định với những tiêu chuẩn khác: kỹ thuật kết hợp di truyền mờ là rất có giá trị trong việc đẩy mạnh cá ứng dụng thực tế của hệ thống này. Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 4 CHƢƠNG 2 BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG 2.1 Giới thiệu Quản lý hàng đợi là là một nhóm tổ hợp các phương pháp quản lý bộ đệm và lập lịch, đây là một trong những cơ chế cung cấp chất lượng dịch vụ (QoS). Quản lý bộ đệm quyết định việc phân phối bộ đệm và loại bỏ các gói đến theo một cách thức được quyết định trước. Trong khi đó lập lịch cho phép quản lý băng thông hay nói cách khác là nó quyết định xem gói nào sẽ được đưa ra từ hàng đợi nào. Do đó có rất nhiều thuật toán được đưa ra trong kĩ thuật quản lý hàng đợi. Đối với quản lý bộ đệm có các thuật toán : RED, Blue, PBS (chia sẻ bộ đệm từng phần), cắt-đuôi (Drop-Tail)….quá trình lập lịch gồm: RR, WFQ, EDF (Earliest Deadline First)… Quản lý hàng đợi dựa trên luồng gồm RED và xRED, dựa trên tốc độ gồm: Blue, PI, KT, Bat, Green, Purple... Trong chương này chủ yếu đi sâu vào các phương pháp quản lý bộ đệm hiệu quả là RED và Blue và đề xuất Fuzz-GA-AQM. Hình 2.1 Sự phát triển của các thuật toán AQM theo thời gian 2.2 Kỹ thuật chống mất gói trong mạng TCP/IP tắc nghẽn 2.2.1 Giới thiệu Như được mô tả trong Chương 1, một trong những lý do tỷ lệ mất gói cao là sự thất bại của mạng nhằm cung cấp thông báo tắc nghẽn sớm cho các nguồn. Điều này đã dẫn đến các kiến nghị về AQM như RED và các biến thể của nó [46, 67]. Trong khi RED chắc chắn Chương 2: Bài toán AQM trong viễn thông Trang 5 nhanh hơn so với cắt-đuôi truyền thống, chương này cho thấy rằng rất khó để tham số hoá hàng đợi RED để thực hiện tốt theo các kịch bản khác nhau của tắc nghẽn. Để phát hiện sớm hoạt động, thông báo tắc nghẽn phải được cung cấp với tỷ lệ đủ lớn để ngăn ngừa mất gói do tràn bộ nhớ đệm, đồng thời đủ nhỏ để ngăn ngừa sự kém khả dụng của kết nối cổ chai. Chương này chứng tỏ sự kém hiệu quả của thuật toán quản lý hàng đợi RED hiện tại và cho thấy hàng đợi RED làm thế nào có thể tự tham số hoá tuỳ thuộc vào lưu lượng tải để giảm mất gói và duy trì độ khả dụng kết nối cao. 2.2.2 Quản lý hàng đợi tích cực (AQM) Một trong những điểm yếu của RED và một số các đề xuất lập lịch AQM là thông báo tắc nghẽn không trực tiếp phụ thuộc vào số lượng kết nối được ghép kênh qua tuyến. Để phát hiện sớm hoạt động trong các mạng tắc nghẽn, thông báo tắc nghẽn phải được gửi đủ tới nguồn nhằm giảm tốc độ gửi đến mức cần thiết để tránh mất gói do tràn bộ nhớ đệm. Ngược lại, hàng đợi RED cũng phải ngăn ngừa thông báo tắc nghẽn từ chính chúng tới một số nguồn để tránh trường hợp kết nối cổ chai trở thành kém khả dụng. Ngoại trừ việc sửa đổi thuật toán RED là tích cực hơn, hàng đợi RED bị thoái hoá trong hàng đợi cắt đuôi đơn. Phần này xem xét tác động đến lưu lượng tải gồm kỹ thuật AQM như RED và đề xuất trên cơ chế thường trực để tối ưu hóa hiệu suất. 2.2.3 Điều khiển tắc nghẽn máy chủ cuối Trong khi hoàn thành thiết kế cơ chế AQM như ARED có thể giúp giảm bớt mất gói, kỹ thuật đơn lẻ như vậy không thể đảm bảo tỷ lệ mất gói thấp, đặc biệt là khi lưu lượng tải biến động lớn. Quản lý hàng đợi thông minh phải được kết hợp với điều khiển tắc nghẽn máy chủ cuối thông minh để đạt được độ khả dụng cao với số lượng mất gói tối thiểu. 2.2.4 Điều chỉnh hiệu suất tối ưu Hai phần trước đã cho thấy 2 cơ chế riêng lẻ, AQM và cơ chế máy chủ cuối có thể được dùng để giảm mất gói đáng kể trong mạng. Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 6 Khi sử dụng cùng nhau, chúng tạo thành sự kết hợp cộng tác có thể cho phép mạng đạt được hiệu quả rất cao ngay cả trong thời gian tắc nghẽn nặng. 2.2.5 Kết luận và công việc tương lai Chương này đã cho thấy cách thức AQM và thuật toán điều khiển tắc nghẽn máy chủ cuối có thể được thiết kế để đem lại hiệu quả loại trừ mất gói trong các mạng tắc nghẽn. Việc cải thiện các thuật toán kiểm soát tắc nghẽn máy chủ cuối cũng đang được khảo sát. Trong khi tăng dựa trên băng thông cung cấp cho máy chủ cuối với giá trị giới hạn trên để tích cực nhằm đạt được tốc độ truyền, nó thường muốn nguồn thay đổi tốc độ gửi chậm hơn hoặc không gửi gói nào khi gần điểm tắc nghẽn để tránh sự dao động trong thuật toán cửa sổ của TCP [23, 94, 95]. 2.3 BLUE phương pháp mới cho AQM 2.3.1 Giới thiệu Một trong những kết quả nổi bật trong phần 2.2 là ngay cả với ECN, quản lý hàng đợi RED vẫn không thể loại trừ mất gói với lượng lớn tải hoạt động. Gói mất chỉ có thể được loại trừ khi sửa đổi các thuật toán điều khiển tắc nghẽn TCP. Phần này thể hiện điểm yếu cơ bản của RED và tất cả kỹ thuật AQM khác đã biết. Trong khi RED có thể đạt được điểm hoạt động lý tưởng, nó chỉ có thể làm điều đó khi có đủ không gian đệm và được tham số đúng [33, 93]. Nổi bật hơn các thí nghiệm ở trên, phần này đề xuất một thuật toán AQM cơ bản khác, gọi là BLUE, trong đó sử dụng độ mất gói và lịch sử khả dụng của kết nối để quản lý tắc nghẽn. BLUE duy trì một xác suất duy nhất, mà nó dùng để đánh dấu (hoặc loại bỏ) các gói tin khi chúng xếp hàng. Nếu hàng đợi liên tục mất gói do tràn bộ đệm, BLUE tăng xác suất đánh dấu, do đó tăng tốc độ gửi thông báo tắc nghẽn phản hồi. Ngược lại, nếu hàng đợi rỗng, hoặc nếu kết nối rỗi, BLUE sẽ giảm xác suất đánh dấu. Cuối cùng, bằng cách sử dụng cơ chế dựa trên BLUE, phần này đề xuất và đánh giá SFB, một cơ chế mới cho hiệu quả và công bằng với số lượng lớn các luồng. 2.3.2 Sự hạn chế của RED Chương 2: Bài toán AQM trong viễn thông Trang 7 Như được mô tả trong phần 2.2, một trong những vấn đề lớn nhất với các thuật toán điều khiển tắc nghẽn của TCP đối với hàng đợi cắt-đuôi là nguồn giảm tốc độ truyền chỉ sau khi phát hiện mất gói tin do tràn hàng đợi. RED khắc phục vấn đề này bằng cách phát hiện sớm khi mới chớm tắc nghẽn và thông báo tắc nghẽn đến máy chủ cuối, cho phép chúng giảm tốc độ truyền trước khi xảy ra tràn hàng đợi. Một cách để giải quyết vấn đề này là sử dụng một lượng lớn không gian đệm cho hàng đợi RED. Trong khi RED có thể đạt được điểm hoạt động lý tưởng, chỉ khi có lượng không gian đệm đủ lớn và được tham số chính xác. 2.3.3 Blue Để khắc phục những hạn chế của RED, phần này đề xuất và đánh giá một thuật toán quản lý hàng đợi cơ bản khác gọi là BLUE. Sử dụng cả mô phỏng và thí nghiệm, BLUE cho thấy có thể khắc phục nhiều hạn chế của RED. RED đã được thiết kế với mục tiêu (1) giảm thiểu mất gói tin và trễ hàng đợi, (2) tránh đồng bộ hóa toàn cục của nguồn, (3) duy trì độ khả dụng kết nối cao, và (4) loại bỏ độ dốc chống lại nguồn truyền loạt. Phần này cho thấy BLUE cải thiện hiệu suất của RED trong tất cả các khía cạnh. Các kết quả cũng cho thấy BLUE hội tụ tới điểm hoạt động lý tưởng ngay cả khi được sử dụng với bộ đệm rất nhỏ. Thuật toán Blue Ý tưởng chính phía sau BLUE là thực hiện quản lý hàng đợi dựa trực tiếp trên gói mất và kết nối khả dụng hơn là chiều dài hàng đợi tức thời hoặc trung bình. Điều này trái ngược với tất cả các đề xuất AQM đã biết mà nó sử dụng một số hình thức chiếm dụng hàng đợi trong quản lý tắc nghẽn. BLUE duy trì một xác suất duy nhất, pm, mà nó sử dụng để đánh dấu (hoặc loại bỏ) các gói tin khi chúng đang xếp hàng. Nếu hàng đợi liên tục mất gói do tràn bộ đệm, BLUE tăng pm, do đó tăng tốc độ gửi thông báo tắc nghẽn phản hồi. Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 8 Hình 2.30 Thuật toán Blue Nếu hàng đợi trống, hoặc nếu kết nối rỗi, BLUE giảm xác suất đánh dấu. Thời gian đóng băng (freeze_time) tham số này xác định khoảng thời gian tối thiểu giữa hai cập nhật thành công pm. Các tham số khác được sử dụng là, delta, xác định lượng pm tăng lên khi hàng đợi tràn, hoặc giảm đi khi kết nối rỗi. Lưu ý rằng có vô số cách thức pm có thể được quản lý. Trong khi BLUE có vẻ cực kỳ đơn giản, nó cung cấp sự cải tiến hiệu suất đáng kể ngay cả khi so sánh với một hàng đợi RED đã được tối ưu tham số. 2.3.4 Blue cân bằng ngẫu nhiên (SFB) Phần này mô tả và đánh giá BLUE công bằng ngẫu nhiên (SFB), một kỹ thuật mới để bảo vệ các luồng TCP chống lại các luồng không đáp ứng bằng cách sử dụng thuật toán BLUE. SFB có khả năng mở rộng cao và thực hiện công bằng sử dụng số trạng thái cực kỳ nhỏ và lượng nhỏ không gian đệm. 2.4 Kết luận và công việc tương lai Phần này đã chứng tỏ sự yếu kém vốn có của thuật toán AQM hiện tại sử dụng sự chiếm dụng hàng đợi trong các thuật toán của chúng. Nhằm giải quyết vấn đề này, một thuật toán quản lý hàng đợi cơ bản khác được gọi là BLUE đã được thiết kế và đánh giá. Cuối cùng, sự phát triển của một thuật toán quản lý hàng đợi BLUE “nâng cao” tương tự như RED “nâng cao” [38, 39] đang được nghiên cứu. Bằng cách sử dụng BLUE, các bộ đệm yêu cầu cần thiết để hỗ trợ các dịch vụ phân biệt có thể được giảm đi đáng kể. Chương 2: Bài toán AQM trong viễn thông Trang 9 CHƢƠNG 3: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN MỜ CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG 3.1 Mở đầu Như đã biết điều khiển luồng dữ liệu là một cơ chế quan trọng trong điều khiển tắc nghẽn mạng TCP. Trong những năm gần đây rất nhiều nghiên cứu có thể khai thác các node trung gian nếu giảm thiểu tắc nghẽn trên mạng. Điều đó đã dẫn đến việc thiết lập thêm một số thông số mới cho giải thuật TCP/IP. Thông báo tắc nghẽn tường minh ECN như đã đề cập trong chương 1 là một khai thác tốt và có hiệu quả. Quản lý hàng đợi có thể coi như là một lớp các gói tin mất/đánh dấu trong các router. Nhiệm vụ của nó chính là: + Sớm phát hiện khả năng tắc nghẽn từ nguồn để có thể mất gói/đánh dấu các gói. + Cho phép luồng dữ liệu truyền ổn định. + Loại bỏ hiệu quả các quá trình với hàng đợi đã đầy và đã tồn tại với thời gian dài. + Cho phép có thể thực hiện nhịp nhàng giữa thông lượng lớn với trễ xảy ra khi hàng đợi nhỏ. Thuật toán RED có thể cho phép thoả mãn việc tối ưu hoá các hoạt động của router. Một số đặc tính tốt của RED có thể kể ra như sau: + Rất nhậy với các cấu hình hệ thống. + Dễ dàng đưa TCP về chế độ đồng bộ toàn cục. 3.2 AQM sử dụng giải thuật di truyền 3.2.1 Sơ đồ cấu hình mạng Hình 3.1 cho thấy nút cổ chai thể hiện qua kết nối giữa A và B. Giữa A và B có tố độ truyền dữ liệu là 15Mbps (khoảng 15000 gói/s). Mỗi một gói tin chứa khoảng 125 bytes và thời gian trễ khoảng 15ms. Trên tất các các nguồn đến A có tốc độ 10Mbps và độ trễ là 15ms và độ lớn của hàng đợi là 300 gói. Hàng đợi A được thực hiện theo AQM và Cắt-đuôi. Trang 10 10Mbps 1 15Mbps n B A 2 10Mbps 15ms 15ms d 15ms Hình 3.1 Biểu diễn nút cổ chai từ A sang B Giả số lượng tải (số phiên của TCP) là 120 và q0=75 gói. Sơ đồ điều khiển AQM sử dụng giải thuật di truyền mờ có thể thấy trên hình 3.2 e(k) Giải thuật u(k) q0 G(s) q(k) di truyền Đối tượng mờ + ĐK Hình 3.2 Sơ đồ hệ thống điều khiển GA-fuzzy-AQM Xây dựng giải thuật di truyền cho AQM có nhiều điểm khác biệt so với việc xây dựng các thuật toán PI hoặc PID. Nếu với thuật toán PI và I khó có thể dự báo dựa trên các sai số sẽ xảy ra trong tương lai thì thuật toán PID cho thấy đây là thuật toán truyền thống được dùng rất nhiều trong công nghiệp. Nhưng với thuật toán di truyền mờ dùng để điều khiển hệ AQM sẽ mang lại một hình ảnh mới với các đặc điểm nổi trội: + Có khả năng đưa các tri thức của các chuyên gian vào điều khiển hệ AQM. + Bộ điều khiển sử dụng giải thuật di truyền mờ hết sức mềm dẻo. + Có khả năng tìm biến toàn cục. + Không nhất thiết phải có một vùng nhớ đệm lớn. Với những lý do nêu trên hệ điều khiển sử dụng thuật toán điều khiển di truyền mờ sẽ được mô tả như sau: Trên hình 3.2 chúng ta giả thiết là hệ thống được mô hình hóa và mô tả trong [84]. Các thông số được tính theo [17] Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 11  RC  G (s)  3 e  Rs => 4N 2 2 R C  s  1  Rs  1  2 N   C 2  Rs e (3.1) 2N G(s)  2 N  1   s  2  s   R C  R  Trong đó: C là tốc độ đường truyền (gói/s) q0 là giá trị hàng đợi mong muốn q là giá trị hàng đợi ở đầu ra. N tải (số phiên của TCP) R là RTT; R=2(q/C +Tp) Tp là giá trị xác định. P là xác suất mất gói/đánh dấu. 3.2.2 Thiết kế thuật toán di truyền mờ Thuật toán di truyền mờ được thiết kế theo các bước sau đây: 3.2.2.1 Bộ điều khiển mờ + Các đầu vào thể hiện trên hình 3.3 + Các tín hiệu ra hình 3.4 + Hệ luật của bộ điều khiển mờ hình 3.5, bảng 3.1 + Một suy diễn của bộ điều khiển mờ hình 3.6 Bảng 3.1 Cơ sở luật – các luật ngôn ngữ p(kT) NVB NB NS Qerror Z (kT) PS PB PVB NVB H B T Z Z Z Z NB H B VS Z Z Z Z Qerror (kT - T) NS Z PS H H H B VB VB S S B Z T VS Z Z T Z Z Z Z Z Z PB H H VB S T Z Z PVB H H VB B VS T Z 3.2.2.2 Giải thuật di truyền mờ cho tìm kiếm tối ƣu các dạng hàm thuộc Như đã trình bày trong chương 1 giải thuật di truyền sử dụng cho tìm kiếm tối ưu các dạng hàm thuộc phải thực hiện được các công việc: sinh sản, chọn lọc, lai ghép , đột biến. Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 12 Bắt đầu  Khởi tạo  Hàm Thích nghi  Hội tụ? Y  N Mã hoá Chọn lọc  Kết thúc Lai tạo Đột biến Giải mã Hình 3.7 Cấu trúc giải thuật di truyền tổng quát Cụ thể, thuật toán di truyền tổng quát hình 3.7 gồm các buớc sau: Buớc 1: Khởi tạo quần thể các nhiễm sắc thể. Chọn mô hình cho giải pháp của vấn đề. Chỉ định cho mỗi giải pháp một ký hiệu. Buớc 2: Tìm hàm thích nghi và xác định giá trị thích nghi của từng nhiễm sắc thể. Buớc 3: Sao chép lại các nhiễm sắc thể dựa vào giá trị thích nghi của chúng (sinh sản) và tạo ra những nhiễm sắc thể mới bằng các phép toán di truyền (lai ghép hay đột biến). Đánh giá tính hội tụ sau mỗi thế hệ. Buớc 4: Tính hệ số thích nghi cho các thành viên mới để mất những thành viên không phù hợp trong quần thể. Buớc 5: Nếu chưa tìm được giải pháp tối ưu thì trở lại buớc 3. Nếu mục tiêu tìm kiếm đã đạt được thì dừng lại. Báo cáo kết quả. 3.2.3.1 Mã hoá Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 13 Mã hoá là quá trình chuyển đổi một mô hình mờ vào các thông số trong không gian một chiều của cá thể. Nói một cách khác cá thể chứa các thông số cho việc xây dựng mô hình mờ. Quá trình mã hoá sử dụng phép ánh xạ tuyến tính có dạng: Cij= C min  b ( C max  C min ) 2 1 (3.2) L Quá trình mã hoá một gen liên quan đến các cá thể. Giả sử mỗi một thông số có độ dài 10 bits thì một gen sẽ có tổng số 10×3×7×3 = 630 bits, như vậy hệ mờ với dạng luật if…and …then sẽ có dạng: 1 2 …29 30 211 … 239 240 Đầu vào cá thể 1.1 Trái, Tâm, Phải 421… 599 600601 … 630 Đầu ra cá thể 1 Đầu ra cá thể 7 tới cá thể 6 Trái, Tâm, Phải Hình 3.11 Một nhiễm sắc thể cho chuỗi mã hoá Từ (hình 3.11) ta thấy, điểm trái của hàm thuộc một thứ nhất là các bit (1, 2, …, 10), tâm của hàm thuộc một là các bit (11, 12, …, 20), điểm phải của hàm thuộc một thứ nhất là các bit (21, 22, …, 30), có 7 hàm thuộc cho biến vào một, như vậy 30×7 bit đầu là gen của biến vào một. Điểm trái của hàm thuộc hai thứ nhất là các bit (211, 212, …, 220), tâm của hàm thuộc hai là các bit (221, 222, …, 230), điểm phải của hàm thuộc hai là các bit (231, 232, …, 240), tương tự cũng có 7 giá trị cho biến vào hai, như vậy 30×7 bit tiếp theo là gen của biến vào hai của phần điều kiện. Đối với các gen (421….630) sẽ cho ta các giá trị của 7 biến đầu ra. Từ đó xác định được các giá trị thực, sau đó sẽ được tính như phép giải mờ theo phương pháp trọng tâm. Như vậy vị trí của các gen trong không gian vào sẽ được thay đổi trong quá trình thực hiện giải thuật. 3.2.2.4 Lai tạo Phép toán lai tạo được thực hiện thông qua thay đổi vị trí được sắp xếp cho một hàm thuộc. Quá trình thực hiện lai tạo thể hiện trên hình 3.12. Cha mẹ A 011011 | 0001 Con 011011|1100 B 110001 | 1100 110001|0001 Hình 3.12 Quá trình lai tạo Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 14 Hai cá thể cha mẹ trong quần thể được chọn lựa một cách ngẫu nhiên. Quá trình lai tạo cũng thể hiện thông qua việc chọn lựa giữa các giá trị cho các vị trí của hàm thuộc. Cấu trúc sẽ thay đổi giữa các cá thể thông qua các điểm lai tạo. Như vậy đỉnh của hàm thuộc sẽ thay đổi liên quan đến thế hệ con cháu. Các con cháu sẽ kế thừa các đặc trưng tốt của bố mẹ thông qua quá trình lai tạo. 3.2.2.5 Đột biến Các quá trình đột biến sẽ xẩy ra với các cá thể thông qua quá trình lai tạo với xác suất Pm. Quá trình đột biến ở đây là chọn lựa hàm thuộc theo nghĩa cắt bớt các tập mờ, như vậy sẽ giảm bớt các luật mờ cho phép giảm thiểu quá trình tính toán của các mô hình mờ. Như vậy sẽ cho phép tạo các cá thể mới thông qua lai tạo và đột biến. 3.2.2.6 Hàm thích nghi Hàm thích nghi dùng để đánh giá chất lượng các mô hình mờ, nó phản ánh quá trình chọn lọc tự nhiên theo một mức độ thích nghi nhất định. Ở đây các mô hình xây dựng phản ánh được các quá trình vật lý diễn ra hàng ngày xung quanh ta thể hiện trên mức độ thích nghi của hệ thống, hay nói khác đi là mức độ thích nghi của các cá thể. Hay cũng có thể nói sai lệch giữa mô hình mong mốn và mô hình mờ là một giá trị nhỏ nhất. 3.2.3 Mô hình hệ thống Hình 3.13 Mô hình hệ thống điều khiển mờ cho AQM Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 15 C  Tạo quần thể mới Dữ liệu huấn luyện Kết thúc Giá trị thích nghi tốt nhất  Luật 1 Lỗi chuẩn Kết quả Luật suy diễn  Luật 2 Các tham số Luật n Cơ sở tri thức mờ  Tối ưu hoá bằng giải thuật di truyền K Có thực hiện tiếp?  Chạy mô hình mờ  1.0 µ 0 Dữ liệu hợp lệ x Các lỗi phép đo  Chạy các luật trên dữ liệu hợp lệ Hình 3.14 Chỉnh định mô hình mờ bằng GA 3.3 Quá trình thực nghiệm 3.3.1 Xác định đối tượng Để có thể thực hiện xem xét môi trường làm việc của mạng. Chúng ta lấy một ví dụ mô phỏng như sau: Hệ thống mạng máy tính hoạt động như TCP/IP với các thông số như dưới đây: Cc = 105 gói/s=100Mbps [17]; Rc là RTT = 0.03 s; Nc = 30 tải Các thông số trên được xác định trong khoảng C (0, Cc); R (0, Rc); N(Nc,  ); Hàm truyền của hệ thống AQM dùng cho RED có thể được tính từ (3.1) C 2  Rs 5 8 0,03s (3.3) e .10 e 2N 3  2 N  1  2  100    s  2  s    s   s   R C  R  3  3   3  3  ( (b  a)  aT ) z  a( (b  a)  bT )  5.1010  98 98 Wdt (z )   z 3.98  z 3  (2a  b) z 2  (a 2  2ab) z  a 2b    G( s)   100 T (3.7) 2  T Thay số với T=1; a  e 3  3,3382.1015 ; b  e 3  0,51341712 q  k  1  0,513417119q  k   3, 42782.1015 q  k  1  5,72143.1030 q  k  2  (3.8) 2672933,733u  k   2,82558.107 u  k  1 Ứng dụng FL-GA cho bài toán AQM trong viễn thông Trang 16 3.3.2 Kết quả thực nghiệm thể hiện qua mô phỏng Hình 3.15, là dạng đáp ứng của gói dữ liệu đầu ra so với gói dữ liệu yêu cầu trước khi dùng giải thuật di truyền, hình vẽ cho thấy các gói dữ liệu ở đầu ra tiệm cận với số lượng gói dữ liệu yêu cầu là 200 gói. Response: Goi du lieu dau ra <-Xanh>, Goi du lieu yeu cau <--Do> 500 400 300 Response: Goi du lieu dau ra <-Xanh>, Goi du lieu yeu cau <--Do> 500 200 400 100 300 0 0 5 10 15 20 25 30 35 40 45 50 Hình 3.15 gói dữ liệu đầu ra tiệm cận vói gói dữ liệu yêu cầu q0=200 200 Control:Tin hieu dk<--Do>, Error:Sai so dk<-Xanh> x 10 Trên hình 3.16 1.5 là tín hiệu điều khiển mờ (đỏ) và tín hiệu sai số (xanh) giữa gói dữ liệu yêu cầu và gói dữ liệu đầu ra, trước khi dùng giải thuật di truyền: 1 -4 100 0 0 5 -4 1.5 10 15 20 25 30 35 40 45 50 Control:Tin hieu dk<--Do>, Error:Sai so dk<-Xanh> x 10 0.5 1 0 0 5 10 15 20 25 30 35 15 20 25 30 35 40 45 50 0.5 0 0 5 10 40 45 50 Hình 3.16 Tín hiệu điều khiên mờ (đỏ) và tín hiệu sai số (xanh) Hình 3.17 là các biến đầu vào, đầu ra, và bề mặt điều khiển mờ theo cơ sở tri thức của chuyên gia [26] được xây dựng từ luật (bảng 3.1) trước khi dùng giải thuật di truyền. NVB NB NS Z PS PB PVB 0.8 0.6 output1 Degree of membership 1 0.8 0.4 -0.8 -0.6 -0.4 -0.2 0 input1 0.2 0.4 0.6 NVB NB NS Z PS PB PVB 0.8 1 0 -0.5 0 0.5 1 1 -1 input2 input1 Z 1 Degree of membership Degree of membership 1 0.8 0.6 0.4 0.2 0 -1 0.4 -1 0 -1 0.6 0.2 0.2 T VS S B VB H 0.8 0.6 0.4 0.2 0 -0.8 -0.6 -0.4 -0.2 0 input2 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 output1 0.7 0.8 0.9 1 Hình 3.17 Hệ mờ, được xây dựng từ hệ luật trước khi dùng GA Ứng dụng FL-GA cho bài toán AQM trong viễn thông