Luận án: Phát triển thuật toán tiến hóa giải bài toán tối ưu mạng không dây - Nguyễn Gia Như

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Nguyễn Gia Như PHÁT TRIỂN THUẬT TOÁN TIẾN HÓA GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU TRONG MẠNG KHÔNG DÂY LUẬN ÁN TIẾN SỸ TOÁN HỌC Hà Nội - 2015 TIEU LUAN MOI download : skknchat@gmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Nguyễn Gia Như PHÁT TRIỂN THUẬT TOÁN TIẾN HÓA GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU TRONG MẠNG KHÔNG DÂY Chuyên ngành: Cơ sở toán học cho Tin học Mã số: 62460110 LUẬN ÁN TIẾN SỸ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1.TS Lê Trọng Vĩnh 2.TSKH Nguyễn Xuân Huy Hà Nội - 2015 TIEU LUAN MOI download : skknchat@gmail.com ———————————— Lời cam đoan Tôi xin cam đoan luận án "Phát triển thuật toán tiến hóa giải một số bài toán tối ưu trong mạng không dây" là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả được trình bày trong luận án là hoàn toàn trung thực và chưa từng được công bố trong bất kỳ một công trình nào khác. Tác giả: Hà Nội: i TIEU LUAN MOI download : skknchat@gmail.com Lời cảm ơn Trước hết, tôi muốn cảm ơn PGS.TS Lê Trọng Vĩnh, PGS.TSKH Nguyễn Xuân Huy - những người đã trực tiếp giảng dạy và hướng dẫn tôi trong suốt thời gian học tập và thực hiện luận án này. Một vinh dự lớn cho tôi được học tập, nghiên cứu dưới sự hướng dẫn tận tình, khoa học của hai Thầy.

Tôi xin gửi lời cám ơn đến các Thầy, Cô trong Bộ môn Tin học, Khoa Toán- Cơ-Tin học vì sự giúp đỡ và những đề xuất, trao đổi trong nghiên cứu rất hữu ích cho luận án. Xin cảm ơn các Thầy, Cô và các anh chị em đã góp ý, cổ vũ động viên và sát cánh bên tôi trong suốt quá trình thực hiện luận án. Tôi trân trọng cảm ơn Ban Giám hiệu, Phòng Sau Đại học trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi cho tôi trong suốt quá trình thực hiện luận án. Tôi cũng bày tỏ sự cảm ơn đến Hội đồng quản trị, Ban giám hiệu trường Đại học Duy Tân đã tạo điều kiện về thời gian và hỗ trợ kinh phí cho tôi hoàn thành luận án này.

Cuối cùng, tôi xin bày tỏ lòng biết ơn đối với gia đình và người thân đã luôn động viên, hỗ trợ tôi trong suốt thời gian học tập và thực hiện luận án. ii TIEU LUAN MOI download : skknchat@gmail.com Mục lục Lời cam đoan i Lời cảm ơn ii Danh mục từ viết tắt vi Danh mục bảng viii Danh mục hình vẽ ix Mở đầu 1 1 Tổng quan về tối ưu mạng 5 1.1 Mạng không dây .1 Mạng cá nhân không dây .2 Mạng cục bộ không dây .3 Mạng Ad-hoc .4 Mạng đô thị không dây .5 Mạng lưới không dây .3 Sự phát triển của mạng thông tin di động .2 Các vấn đề của tối ưu mạng .1 Các vấn đề mở đối với mạng không dây .2 Bài toán tối ưu .3 Các thuật toán tiến hóa .1 Thuật toán di truyền .2 Thuật toán tối ưu hóa đàn kiến .3 Thuật toán tối ưu hóa nhóm bầy .1 Giới thiệu chung .2 Các thành phần cơ bản của thuật toán .3 Thuật toán PSO dạng Constriction .4 Thuật toán PSO–TVIW và PSO–RANDIW .5 Thuật toán PSO-TVAC .6 Thuật toán MPSO–TVAC .7 Thuật toán SOHPSO–TVAC .8 Sự kết hợp giữa phương pháp PSO và các phương pháp khác .9 Thuật toán SWT-PSO. 42 iii TIEU LUAN MOI download : skknchat@gmail.10 Thuật toán PSO tổng quát .4 Kết chương. 46 2 Tối ưu thông lượng trong mạng 47 2.1 Tối ưu thông lượng trong mạng lưới không dây .1 Mô hình hóa và phát biểu bài toán .1 Kiến trúc hệ thống .2 Mô hình truyền thông .4 Trọng số MTW .5 Chia sẻ hiệu suất sử dụng các Gateway .6 Lập trình tính toán thông lượng .7 Phân tích, đánh giá các phương pháp .2 Đặt gateway hiệu quả sử dụng thuật toán PSO .1 Biểu diễn của một phần tử .2 Khởi tạo quần thể ban đầu .3 Hàm đo độ thích nghi .4 Quá trình tiến hóa .5 Quá trình dừng .6 Mô tả thuật toán .3 Kết quả mô phỏng và đánh giá .1 Tham số mô phỏng .2 Kết quả mô phỏng .2 Truyền thông Broadcast và cây truyền thông tối ưu .1 Bài toán cây khung truyền thông tối ưu .2 Các nghiên cứu liên quan .3 Mã hóa liên kết cạnh và nút (LNB) .3 Tối ưu cây khung truyền thông sử dụng thuật toán PSO .2 Mô tả thuật toán .4 Kết quả mô phỏng và đánh giá .1 Tham số thực nghiệm .2 Kết quả mô phỏng .3 Kết chương.

76 3 Tối ưu truy cập mạng 78 3.1 Đặt trạm cơ sở trong mạng thông tin di động .1 Mô hình hóa và phát biểu bài toán .2 Các nghiên cứu liên quan .3 Tối ưu đặt trạm điều khiển sử dụng thuật toán PSO. 85 iv TIEU LUAN MOI download : skknchat@gmail.2 Mô tả thuật toán .4 Kết quả mô phỏng và đánh giá .1 Mô hình thực nghiệm và thiết lập tham số cho các thuật toán .2 Phân tích, đánh giá các thuật toán .3 Áp dụng thử nghiệm tại thành phố Đà Nẵng .2 Tối ưu truy cập tập trung trong mạng không dây .1 Mô hình hóa và phát biểu bài toán .2 Các nghiên cứu liên quan .3 Tối ưu truy cập tập trung sử dụng thuật toán PSO .2 Mô tả thuật toán .4 Kết quả mô phỏng và đánh giá .1 Mô hình thực nghiệm và thiết lập tham số cho các thuật toán .2 Phân tích, đánh giá các thuật toán .3 Kết chương. 101 Kết luận 102 Danh mục công trình khoa học của tác giả liên quan đến luận án 104 Tài liệu tham khảo 105 v TIEU LUAN MOI download : skknchat@gmail.com Danh mục từ viết tắt Viết tắt Dạng đầy đủ Diễn giải ACO Ant Colony Optimization Tối ưu đàn kiến BSC Base Station Controller Trạm điều khiển cơ sở BSS Base Station Subsystem Phân hệ trạm gốc BTS Base Transmitter Station Trạm thu phát sóng cơ sở CN Core Network Mạng lõi CS Classifier Systems Hệ thống phân lớp CST Communication Spanning Tree Cây truyền thông EC Evolutionary Computing Thuật toán tiến hóa EP Evolutionary Programming Lập trình tiến hóa ES Evolutionary Strategies Các chiến lược tiến hóa FDMA Frequency Division Multiple Access Đa truy cập phân chia tần số GA Genetic Algorithm Thuật toán di truyền GoS Grade of Service Cấp độ dịch vụ GP Genetic Programming Lập trình di truyền GSMC Gateway Mobile Service Center Trung tâm dịch vụ di động HLR Home Location Register Thanh ghi định vị thường trú LAN Local Area Network Mạng cục bộ LE Local Exchanges Tổng đài truy cập tập trung MANET Mobile Adhoc Network Mạng di động Ad-hoc MS Mobile Station Trạm di động cơ sở MSC Mobile Switch Controller Tổng đài chuyển mạch MTW Multihop Traffic-flow weight Trọng số lưu lượng đa chặng NGN Next Generation Network Mạng thế hệ mới PSO Particle Swarm Optimization Tối ưu nhóm bầy SA Simulate Annealing Algorithm Thuật toán luyện thép SS Switching Sub System Hệ thống chuyển mạch con TA Terminal Assignment Đặt trạm đầu cuối VLR Visitor Location Register Bộ ghi định vị thường trú vi TIEU LUAN MOI download : skknchat@gmail.com WLAN Wireless Local Area Network Mạng LAN không dây WMAN Wireless Metropolitan Area Network Mạng di động đô thị WMN Wireless Mesh Network Mạng lưới không dây WPAN Wireless Personal Area Network Mạng cá nhân không dây WMN Wireless Mesh Network Mạng lưới không dây vii TIEU LUAN MOI download : skknchat@gmail.com Danh mục bảng 2.1 Tính toán hiệu suất chia sẻ giữa các gateway .2 Các tham số thiết lập khi chạy thuật toán .3 So sánh thông lượng đạt được khi đặt gateway theo thuật toán GA, PSO, ACO và MTW .4 So sánh thông lượng thấp nhất của mỗi client khi đặt gateway theo thuật toán GA, PSO, ACO và MTW .5 So sánh thông lượng trung bình của các gateway theo thuật toán GA, PSO, ACO và MTW .6 Bộ dữ liệu mạng của 12 nút và 40 cạnh .7 Các tham số thiết lập khi chạy thuật toán .8 So sánh kết quả thực thi của các thuật toán trên bộ dữ liệu chuẩn .1 Qui ước các ký hiệu dùng trong bài toán TA .2 Qui ước các ký hiệu dùng trong bài toán đặt trạm điều khiển .3 Ví dụ về bài toán TA .4 Thông tin về bộ dữ liệu thực nghiệm đặt trạm điều khiển .5 Các tham số thiết lập khi chạy thuật toán .6 So sánh hàm mục tiêu của các thuật toán .7 Đề xuất qui hoạch trạm BTS tại Đà Nẵng .8 Định nghĩa các ký hiệu dùng trong bài toán truy cập tập trung .9 Thông tin về bộ dữ liệu thực nghiệm tối ưu truy cập .10 Các tham số thiết lập khi chạy thuật toán. 100 viii TIEU LUAN MOI download : skknchat@gmail.com Danh mục hình vẽ 1.1 Kiến trúc mạng lưới không dây .2 Kết nối điểm-điểm .3 Kết nối điểm–đa điểm .4 Kết nối đa điểm – đa điểm .5 Mô hình hệ thống thông tin di động GSM .6 Lộ trình phát triển của thông tin di động .7 Kiến trúc mạng di động không dây .8 Quá trình quy hoạch mạng .9 Sơ đồ tổng quát của thuật toán di truyền .10 Thí nghiệm đàn kiến 1 .11 Thí nghiệm đàn kiến 2 .12 Sơ đồ tổng quát của thuật toán tối ưu đàn kiến .13 Quy luật chuyển động của bầy đàn .14 Quy luật tìm tổ của bầy đàn .15 Vị trí cá thể trong quần thể .16 Sơ đồ tổng quát của thuật toán PSO .1 Kiến trúc mạng WMN có các gateway .2 Ví dụ về tính Multi-hop Traffic-Flow Weight .3 Ví dụ về tính hiệu suất chia sẻ giữa các gateway .4 Một kế hoạch lập lịch TDMA trong truyền thông lõi với SRD=3 .5 Ví dụ về lập lịch lưu lượng trong truyền thông lõi .6 Một kế hoạch lập lịch phân chia khe thời gian trong truyền thông cục bộ với CRF=4 .7 So sánh thông lượng trung bình của Client trong kịch bản 4 .8 So sánh thông lượng trong trường hợp xấu nhất của kịch bản 4 .9 So sánh thông lượng trung bình của Client trong kịch bản 5 .10 So sánh thông lượng trong trường hợp xấu nhất của kịch bản 5 .12 Trường hợp của Palmer 6 nút .13 Hai cây khung truyền thông của Palmer 6 nút .14 Ma trận khoảng cách của đồ thị G .15 Ma trận khoảng cách của đồ thị G sau khi biến đổi .16 Cây khung tối ưu mới được xây dựng .17 Mạng truyền thông tối ưu với 12 nút và 40 cạnh .18 So sánh tổng thời gian trễ trung bình của các thuật toán với các cách mã hóa khác nhau .19 So sánh thời gian xử lý của các thuật toán với lớp bài toán Palmer .20 So sánh thời gian xử lý của các thuật toán với lớp bài toán Raidl .21 Kết quả so sánh hàm mục tiêu giữa các thuật toán.

77 ix TIEU LUAN MOI download : skknchat@gmail.1 Bài toán đặt trạm điều khiển trong mạng không dây .