ĐẠ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 TỐN TỐI ƯU TRONG MẠNG KHƠNG DÂY LUẬN ÁN TIẾN SỸ TỐ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 TỐN TỐI ƯU TRONG MẠNG KHƠNG DÂY Chun ngành: Cơ sở tố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: PGS.TS Lê Trọng Vĩnh PGS.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 số tốn tối ưu mạng khơng dây" cơng trình nghiên cứu riêng tơi Các số liệu, kết trình bày luận án hoàn toàn trung thực chưa cơng bố cơng trình 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, muốn cảm ơn PGS.TS Lê Trọng Vĩnh, PGS.TSKH Nguyễn Xuân Huy - người trực tiếp giảng dạy hướng dẫn suốt thời gian học tập thực luận án Một vinh dự lớn cho học tập, nghiên cứu hướng dẫn tận tình, khoa học hai Thầy Tôi xin gửi lời cám ơn đến Thầy, Cô Bộ môn Tin học, Khoa TốnCơ-Tin học giúp đỡ đề xuất, trao đổi nghiên cứu hữu ích cho luận án Xin cảm ơn Thầy, Cô anh chị em góp ý, cổ vũ động viên sát cánh bên tơi suốt q trình thực 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 suốt q trình thực luận án Tôi bày tỏ 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 thời gian hỗ trợ kinh phí cho tơi hồn thành luận án Cuối cùng, tơi xin bày tỏ lịng biết ơn gia đình người thân ln động viên, hỗ trợ suốt thời gian học tập thực 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 Tổng quan tối ưu mạng 1.1 Mạng không dây 1.1.1 Khái niệm 1.1.2 Phân loại 1.1.2.1 Mạng cá nhân không dây 1.1.2.2 Mạng cục không dây 1.1.2.3 Mạng Ad-hoc 1.1.2.4 Mạng đô thị không dây 1.1.2.5 Mạng lưới không dây 1.1.3 Sự phát triển mạng thông tin di động 1.2 Các vấn đề tối ưu mạng 1.2.1 Các vấn đề mở mạng không dây 1.2.2 Bài toán tối ưu 1.3 Các thuật tốn tiến hóa 1.3.1 Thuật toán di truyền 1.3.2 Thuật toán tối ưu hóa đàn kiến 1.3.3 Thuật tốn tối ưu hóa nhóm bầy 1.3.3.1 Giới thiệu chung 1.3.3.2 Các thành phần thuật toán 1.3.3.3 Thuật toán PSO dạng Constriction 1.3.3.4 Thuật toán PSO–TVIW PSO–RANDIW 1.3.3.5 Thuật toán PSO-TVAC 1.3.3.6 Thuật toán MPSO–TVAC 1.3.3.7 Thuật toán SOHPSO–TVAC 1.3.3.8 Sự kết hợp phương pháp PSO phương pháp khác 1.3.3.9 Thuật toán SWT-PSO 5 6 10 13 20 22 25 26 27 31 34 34 36 37 38 39 40 40 41 42 iii TIEU LUAN MOI download : skknchat@gmail.com 1.4 1.3.3.10 Thuật toán PSO tổng quát 44 Kết chương 46 Tối ưu thông lượng mạng 2.1 Tối ưu thông lượng mạng lưới không dây 2.1.1 Mơ hình hóa phát biểu toán 2.1.1.1 Kiến trúc hệ thống 2.1.1.2 Mơ hình truyền thông 2.1.1.3 Thông lượng 2.1.1.4 Trọng số MTW 2.1.1.5 Chia sẻ hiệu suất sử dụng Gateway 2.1.1.6 Lập trình tính tốn thơng lượng 2.1.1.7 Phân tích, đánh giá phương pháp 2.1.2 Đặt gateway hiệu sử dụng thuật toán PSO 2.1.2.1 Biểu diễn phần tử 2.1.2.2 Khởi tạo quần thể ban đầu 2.1.2.3 Hàm đo độ thích nghi 2.1.2.4 Q trình tiến hóa 2.1.2.5 Quá trình dừng 2.1.2.6 Mô tả thuật toán 2.1.3 Kết mô đánh giá 2.1.3.1 Tham số mô 2.1.3.2 Kết mô 2.2 Truyền thông Broadcast truyền thông tối ưu 2.2.1 Bài tốn khung truyền thơng tối ưu 2.2.2 Các nghiên cứu liên quan 2.2.2.1 Mã hóa tập cạnh 2.2.2.2 Mã hóa Prufer 2.2.2.3 Mã hóa liên kết cạnh nút (LNB) 2.2.2.4 Mã hóa NetKeys 2.2.2.5 Mã hóa CB-TCR 2.2.3 Tối ưu khung truyền thông sử dụng thuật tốn PSO 2.2.3.1 Mã hóa giải mã 2.2.3.2 Mô tả thuật toán 2.2.4 Kết mô đánh giá 2.2.4.1 Tham số thực nghiệm 2.2.4.2 Kết mô 2.3 Kết chương Tối ưu truy cập mạng 3.1 Đặt trạm sở mạng thông tin di động 3.1.1 Mô hình hóa phát biểu tốn 3.1.2 Các nghiên cứu liên quan 3.1.3 Tối ưu đặt trạm điều khiển sử dụng thuật toán PSO 47 47 48 48 49 50 50 52 54 59 59 60 60 60 61 61 61 61 61 62 65 66 68 69 70 70 70 70 71 71 73 74 74 75 76 78 79 79 81 85 iv TIEU LUAN MOI download : skknchat@gmail.com 3.1.3.1 3.1.3.2 Kết 3.1.4.1 3.2 3.3 Mã hóa cá thể Mơ tả thuật tốn 3.1.4 mô đánh giá Mơ hình thực nghiệm thiết lập tham số cho thuật toán 3.1.4.2 Phân tích, đánh giá thuật tốn 3.1.4.3 Áp dụng thử nghiệm thành phố Đà Nẵng Tối ưu truy cập tập trung mạng không dây 3.2.1 Mơ hình hóa phát biểu toán 3.2.2 Các nghiên cứu liên quan 3.2.3 Tối ưu truy cập tập trung sử dụng thuật toán PSO 3.2.3.1 Mã hóa cá thể 3.2.3.2 Mơ tả thuật tốn 3.2.4 Kết mô đánh giá 3.2.4.1 Mô hình thực nghiệm thiết lập tham số cho thuật toán 3.2.4.2 Phân tích, đánh giá thuật toán Kết chương 85 87 87 87 87 90 94 95 98 99 99 99 100 100 100 101 Kết luận 102 Danh mục công trình khoa học 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 sở BSS Base Station Subsystem Phân hệ trạm gốc BTS Base Transmitter Station Trạm thu phát sóng 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 tố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 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 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 hệ PSO Particle Swarm Optimization Tối ưu nhóm bầy SA Simulate Annealing Algorithm Thuật tốn luyện thép SS Switching Sub System Hệ thống chuyển mạch 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 2.2 2.3 2.6 2.7 2.8 Tính tốn hiệu suất chia sẻ gateway Các tham số thiết lập chạy thuật toán So sánh thông lượng đạt đặt gateway theo thuật toán GA, PSO, ACO MTW So sánh thông lượng thấp client đặt gateway theo thuật toán GA, PSO, ACO MTW So sánh thông lượng trung bình gateway theo thuật tốn GA, PSO, ACO MTW Bộ liệu mạng 12 nút 40 cạnh Các tham số thiết lập chạy thuật toán So sánh kết thực thi thuật toán liệu chuẩn 63 73 75 76 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 Qui ước ký hiệu dùng toán TA Qui ước ký hiệu dùng tốn đặt trạm điều khiển Ví dụ toán TA Thông tin liệu thực nghiệm đặt trạm điều khiển Các tham số thiết lập chạy thuật toán So sánh hàm mục tiêu thuật toán Đề xuất qui hoạch trạm BTS Đà Nẵng Định nghĩa ký hiệu dùng tốn truy cập tập trung Thơng tin liệu thực nghiệm tối ưu truy cập Các tham số thiết lập chạy thuật toán 79 80 82 88 88 88 94 95 100 100 2.4 2.5 53 62 62 63 viii TIEU LUAN MOI download : skknchat@gmail.com Trong pj số lượng tối đa trạm BTS mà MSC Sj phục vụ với p0 = N (giả sử trạm trung tâm LE phục vụ tất N trạm BTS) Bài toán thiết kế kiến trúc mạng xác định ma trận X sau:  X = (xij )N ×M +1   =  x10 x20 x11 x21 xN xN x1M x2M xNM      (3.14) đó, thành phần xij (i = N , j = M ) xác định sau: xij = Nếu BTS Ti kết nối đến MSC Sj Ngược lại (3.15) Chú ý rằng, trạm BTS kết nối đến M MSC kết nối trực tiếp đến LE Do đó, dịng ma trận X có giá trị Hơn nữa, số lượng số cột j thể số BTS kết nối đến MSC Sj Vì vậy, ma trận tồn cột mà toàn phần tử chứng tỏ MSC vị trí khơng sử dụng Từ đó, ta biểu diễn trạm MSC sử dụng từ ma trận X vectơ sau: Y = (y0 , y1 , , yM ) (3.16) đó, thành phần yj (j = M ) xác định sau: yj =     Nếu Sj sử dụng tức N xij > i=1 (3.17) N    Nếu Sj không sử dụng tức xij = i=1 Hàm mục tốn tối thiết chi phí kết nối mơ tả sau: N M M (cij ×xij )+ Z = i=1 j =0 M (fj ×yj )+ j =0 (bj ×yj ) j =0 (3.18) ⇔ Z = sumdiag(C ×X T )+F ×Y T +B ×Y T Thành phần thể chi phí kết nối từ N BTS đến M MSC sử dụng đến LE, thành phần thứ thể chi phí kết nối từ MSC đến LE, cuối chi phí trì MSC sử dụng Trong đó, X T ma trận, Y T vectơ chuyển vị sumdiag(A) hàm tính tổng thành phần ma trận A 97 TIEU LUAN MOI download : skknchat@gmail.com Bài toán tối ưu truy cập tập trung mạng phát biểu sau: Tìm ma trận X vectơ Y cho tối thiểu chi phí kết nối Z [41] Z = sumdiag(C ×X T )+F ×Y T +B ×Y T → (3.19) Thỏa mãn ràng buộc: X ×E = E (3.20) E T ×X ≤ P (3.21) Trong đó: - Ràng buộc (3.20) thể tổng thành phần dòng i ma trận X phải (i = 1, 2, , N ) với E vectơ cột với thành phần - Ràng buộc (3.21) thể tổng thành phần cột j ma trận X phải nhỏ pj tức số lượng BTS tối đa đáp ứng MSC Sj 3.2.2 Các nghiên cứu liên quan Các tác giả [41] đưa mô hình kiến trúc truy cập tập trung mạng di động thể tương tác BTS đến MSC MSC đến LE Đây kiến trúc đặc trưng tiêu biểu mạng di động tế báo Trong trường hợp đơn giản, kiến trúc mạng biểu diễn theo mơ hình truy cập tập trung hình Tức trạm LE sử dụng để điều khiển tập MSC, MSC điều khiển truy cập tập BTS Cuối cùng, BTS cung cấp kết nối đến nhóm trạm di động MS thơng qua kết nối không dây Đây kiến trúc quan trọng, thu hút nhiều nghiên cứu với công bố [32, 36, 46] Tuy nhiên, tốn khó phức tạp nên nghiên cứu tập trung theo hướng sử dụng thuật toán heuristic để giải Các thuật toán tiêu biểu kể đến là: - Thuật tốn Exhaustive search sinh tất ma trận kết nối kiểm tra tìm ma trận kết nối với chi phí tối thiểu đề xuất [21] - Thuật toán Heuristic sử dụng tư tưởng greedy để tìm kết nối tối ưu sau vịng lặp với việc sử dụng MSC gần đủ dung lượng để đáp ứng yêu cầu BTS đề xuất [5, 23, 38, 42] - Thuật toán ngẫu nhiên để lựa chọn trạm BTS vùng phủ sóng Raisane [56] 98 TIEU LUAN MOI download : skknchat@gmail.com 3.2.3 3.2.3.1 Tối ưu truy cập tập trung sử dụng thuật tốn PSO Mã hóa cá thể Mỗi cá thể thuật toán PSO mã hóa ma trận x = (xij )N ×(M +1) , (i = N , j = M ) với qui ước xij = có nghĩa BTS Ti tương ứng kết nối với MSC Sj , ngược lại Để khởi tạo nhóm bầy, chúng tơi sinh ngẫu nhiên vị trí phần tử Sau tiến hành hiệu chỉnh lại cá thể cho cá thể X thỏa mãn ràng buộc (3.20-3.21) Để đảm bảo cá thể có xác N bit ứng với N trạm điều khiển cần thiết lập đề xuất hàm PSO Repair để hiệu chỉnh cá thể Thuật toán 3.7 PSO-Repair Input: Cá thể x = (xij )N ×(M +1) có p bit Output: Cá thể x = (xij )N ×(M +1) có xác N bit Begin If p < N then Thêm (N −p) bit cách sinh ngẫu nhiên vị trí; else Chọn ngẫu nhiên (p−N ) bit loại bỏ khỏi xâu nhị phân; End Sau chuẩn hóa, cá thể có tổng phần tử dịng i ma trận (i = 1, 2, , N ) tổng phần tử cột j ma trận k phải nhỏ để Pj Hàm mục tiêu tính theo (3.19) 3.2.3.2 Mơ tả thuật toán Thuật toán PSO cho toán tối ưu truy cập tập trung mô tả sau: Thuật toán 3.8 PSO tối ưu truy cập tập trung mạng khơng dây Begin For each nhóm bầy Khởi tạo nhóm bầy; Endfor Do For each nhóm bầy PSO-Repair(nhóm bầy); Tính giá trị thích nghi (fitness value) theo (3.19); If (fitness value > pBest) Then pBest = fitness value; If (pBest > gBest) Then gBest = pBest; Endfor For each nhóm bầy Tính vận tốc v [] = v []+c1 ∗ rand ()∗ (pbest[]−present[])+ c2 ∗ rand ()∗ (lbest[]−present[]); Cập nhật vị trí present[] = present[]+v []; Endfor While (Điều kiện dừng chưa thỏa mãn); End 99 TIEU LUAN MOI download : skknchat@gmail.com 3.2.4 3.2.4.1 Kết mô đánh giá Mơ hình thực nghiệm thiết lập tham số cho thuật toán Thực nghiệm tiến hành tốn với mức độ khó khác thể thông qua số lượng trạm N M Thông tin liệu, ma trận chi phí BS-kết nối hiển thị Bảng 3.9 Bảng 3.9: Thông tin liệu thực nghiệm tối ưu truy cập Bài toán # Số trạm MSCs Số trạm BTSs #1 #2 #3 #4 #5 #6 #7 #8 10 20 40 50 60 10 20 40 80 100 150 200 250 Tham số thực nghiệm chi tiết thuật toán PSO cho Bảng 3.10 Bảng 3.10: Các tham số thiết lập chạy thuật tốn Tham số Giá trị Kích thước nhóm bầy P = 1000 Số lượng vịng lặp tối đa Ngen = 500 Hệ số học tri thức bầy đàn c1 = c2 = Số lân cận xem xét K =3 3.2.4.2 Phân tích, đánh giá thuật toán Thực nghiệm tiến hành nhằm so sánh hiệu thực thi thuật toán đề xuất với thuật toán Exhaustive Search [21] Heuristic [23] Hình 3.10 thể kết so sánh hàm mục tiêu thuật toán Kết cho thấy giá trị hàm mục tiêu thuật toán đạt tốt nhiều so với thuật toán Heuristic giải pháp tốt gần Đầy đủ Tìm kiếm thuật tốn Tuy nhiên, hiệu suất thuật tốn đề xuất chúng tơi tốt so với thuật toán khác Việc so sánh thời gian xử lý cho thấy Hình 3.11 100 TIEU LUAN MOI download : skknchat@gmail.com Hình 3.10: So sánh hàm mục tiêu thuật tốn Hình 3.11: So sánh thời gian thực thi thuật toán 3.3 Kết chương Trong chương này, luận án đề xuất thuật toán PSO để giải hai toán đặt trạm sở mạng không dây tối ưu truy cập mạng không dây Đây toán quan trọng thiết kế tối ưu mạng Các thử nghiệm số với vấn đề mạng lưới thơng tin liên lạc có quy mơ khác cho thấy tính hiệu hiệu thuật toán đề xuất, điều cho thấy thuật toán tốt nhiều so với nghiên cứu gần Các kết công bố cơng trình 1, 2, 4, tác giả 101 TIEU LUAN MOI download : skknchat@gmail.com Kết luận Trong luận án này, đóng góp luận án trình bày hệ thống thuật tốn sinh học cộng đồng nghiên cứu nước sử dụng nhiều để giải tốn tối ưu hóa tổ hợp GA, PSO, ACO Từ việc phân tích lý thuyết chúng tơi hướng luận án đến việc sử dụng thuật toán PSO để giải tốn qui hoạch mạng khơng dây Việc phân tích tốn quan trọng qui hoạch mạng khơng dây trình bày chi tiết Các đóng góp luận án áp dụng thành công PSO để giải tốn qui hoạch mạng khơng dây, cụ thể: 1) Đối với tốn đặt gateway để tối ưu thơng lượng mạng lưới khơng dây Luận án trình bày chi tiết cách tính thơng lượng truyền thơng lõi, truyền thông cục bộ, thông lượng khả thi cho mạng lưới khơng dây Sau đó, chúng tơi thiết kế việc đặt gateway đồng thời dựa thuật toán PSO để khắc phục nhược điểm phương pháp khác đặt gateway gateway đặt sau phụ thuộc vào gateway đặt trước Với cách làm vậy, phương pháp đặt gateway đề xuất đạt hiệu cao hơp so với phương pháp tiếp cận trước 2) Đối với tốn truyền thơng tối ưu, luận án ứng dụng việc định tuyến broadcast mạng khơng dây Việc mã hóa số thực cá thể thuật toán PSO kết hợp với NBE cho phép thuật tốn tìm lời giải gần với tối ưu tồn cục khơng gian tìm kiếm rộng Các kết thực nghiệm PSO hiệu số thuật toán trước nhiều tập liệu mẫu khác 3) Đối với vấn đề tối ưu hóa truy cập, toán đặt trạm sở tối ưu hóa truy cập, luận án trình bày phương pháp mã hóa để chuyển việc giải mã cá thể thành việc tìm các cặp ghép lớn đồ thị hai phía dựa vào thuật tốn tìm luồng cực đại thời gian đa thức Do việc biểu diễn giải mã vậy, nên thuật toán đề xuất PSO cho hai tồn có hiệu tốt cách tiếp cận trước 4) Một việc làm khác luận án xem đóng góp để so sánh hiệu PSO , luận án mô đánh giá so sánh PSO với thuật toán sinh học khác GA ACO 102 TIEU LUAN MOI download : skknchat@gmail.com Các kết luận án cơng bố cơng trình khoa học đăng tải tạp chí, hội nghị chuyên ngành ngồi nước Trong có báo đăng kỷ yếu hội nghị quốc tế, báo đăng tạp chí quốc tế, đăng tạp chí nước kỷ yếu hội quốc gia chuyên ngành Mặt dù vậy, luận án chưa phân tích sử ảnh hưởng tham số thuật toán sinh học đến hiệu thuật toán Mặt khác, toán tối ưu xem xét giảm bớt yếu tố thực tế địa hình, độ nhiễu, Để toán dễ giải hay việc phân tích so sánh kết với thuật tốn xấp xỉ theo lý thuyết chưa thực Đây thiếu sót luận án hướng phát triển luận án thời gian tới 103 TIEU LUAN MOI download : skknchat@gmail.com Danh mục công trình khoa học tác giả liên quan đến luận án Nguyễn Gia Như, Lê Đắc Nhường, Lê Trọng Vĩnh, Nguyễn Xuân Huy (2014), Ant Colony Optimization and Particle Swarm Optimization Algorithms Applied to Optimizing Access Centralized in Wireless Network, Kỷ yếu Hội thảo Quốc gia Một số vấn đề chọn lọc Công nghệ thông tin Truyền thông, Dak Lak, trang 13-18 Nguyễn Gia Như, Lê Đắc Nhường (2013), Optimal location of Controllers in Wireless network using Genetic Algorithm, Tạp chí Khoa học Cơng nghệĐại học Đà Nẵng, Số 6(67), Trang 122-127 Gia Nhu Nguyen, Dac Nhuong Le, Vinh Trong Le (2013), A Novel PSO based Algorithm Approach for the cMTS to Improve QoS in Next Generation Networks, Journal of Future Computer and Communication (IJFCC), Vol.2(5), pp 413-417 Nguyễn Gia Như, Lê Đắc Nhường, Lê Trọng Vĩnh (2013), Tối ưu qui hoạch vị trí trạm BTS dựa thuật tốn tối ưu hóa nhóm bầy, Kỷ yếu Hội thảo Quốc gia Một số vấn đề chọn lọc Công nghệ thông tin Truyền thông, Đà Nẵng, trang 23-28 Nguyễn Gia Như, Lê Đắc Nhường, Lê Đăng Nguyên (2013), A Novel Ant Colony Optimization-based Algorithm for the Optimal Communication Spanning Tree problem, International Journal of Computer Theory and Engineering, Vol.5(3), pp.509-513 Lê Đắc Nhường, Nguyễn Gia Như, Lê Đăng Nguyên, Lê Trọng Vĩnh (2013), “So sánh đánh giá cách tiếp cận sinh học giải toán đặt trạm sở mạng không dây”, Kỷ yếu Hội thảo Quốc gia nghiên cứu ứng dụng Công nghệ thông tin lần thứ 6, Nhà xuất KHKT, Trang 494-501 Nguyễn Gia Như, Lê Đắc Nhường (2012), Particle Swarm Optimization and Ant Colony Optimization Algorithms Applied to the Optimal Communication Spanning Tree problem, Kỷ yếu Hội thảo Quốc gia Một số vấn đề chọn lọc Công nghệ thông tin Truyền thông, Hà Nội, Trang 334-340 Vinh Trong Le, Dinh Huu Nghia, Gia Nhu Nguyen (2011), A Novel PSOBased Algorithm for Gateway Placement in Wireless Mesh Networks, in proceedings of 2011 IEEE 3rd International Conference on Communication Software and Networks (ICCSN 2011), May 27-29, 2011, China, pp 37-42 Vinh Trong Le, Dinh Huu Nghia, Gia Nhu Nguyen (2011), The mininum number of gateways for maximizing throughput in Wireless Mesh Networks, In Proceeding of The 2nd International Symposium on Information and Communication Technology (SoICT 2011), Ha Noi, Viet Nam, pp 37-42 104 TIEU LUAN MOI download : skknchat@gmail.com Tài liệu tham khảo [1] A Apavatjrut Energy efficient optimization and route recovery for gradient broadcast routing protocol for wireless sensor networks In New Technologies, Mobility and Security (NTMS), 2012 5th International Conference on, pages 1–4, May 2012 doi: 10.1109/NTMS.2012.6208738 [2] R.C Basole, S Narasimhan, and S Snoi Optimal capacity expansion of next genernation wireless base station subsystems In Georgia Atlanta, editor, Proceedings of Conference on Information Systems and Technology (CIST), pages 1–7, 2003 [3] Y Bejerano Efficient integration of multihop wireless and wired networks with qos constraints Networking, IEEE/ACM Transactions on, 12(6):1064– 1078, Dec 2004 ISSN 1063-6692 doi: 10.1109/TNET.2004.838599 [4] Djohara Benyamina, Abdelhakim Hafid, and Michel Gendreau Wireless mesh networks design - A survey IEEE Communications Surveys and Tutorials, 14(2):299–310, 2012 doi: 10.1109/SURV.2011.042711.00007 URL http:// dx.doi.org/10.1109/SURV.2011.042711.00007 [5] L Budzisz, F Ganji, G Rizzo, M.A Marsan, M Meo, Yi Zhang, G Koutitas, L Tassiulas, S Lambert, B Lannoo, M Pickavet, A Conte, I Haratcherev, and A Wolisz Dynamic resource provisioning for energy efficiency in wireless access networks: A survey and an outlook Communications Surveys Tutorials, IEEE, 16(4):2259–2285, Fourthquarter 2014 ISSN 1553-877X doi: 10.1109/COMST.2014.2329505 [6] Lê Đắc Nhường, Nguyễn Gia Như, Lê Đăng Nguyên, and Lê Trọng Vĩnh Optimal location of controllers in wireless networks using genetic algorithm In Kỷ yếu Hội thảo quốc gia Một số vấn đề chọn lọc CNTTT&TT lần thứ 15, Hà Nội, pages 328–333, 2012 [7] P Calegari, F Guidee, P Kuonen, and D Wagner Genetic approach to radio network optimization for mobile systems IEEE VTC, pages 755–759, 1997 [8] T Chan and A Grant On capacity regions of non-multicast networks In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pages 2378–2382, June 2010 doi: 10.1109/ISIT.2010.5513732 [9] Keyu Chen, Maode Ma, En Cheng, Fei Yuan, and Wei Su A survey on mac protocols for underwater wireless sensor networks Communications Surveys Tutorials, IEEE, 16(3):1433–1447, Third 2014 ISSN 1553-877X doi: 10 1109/SURV.2014.013014.00032 [10] M.X Cheng, Jinhua Sun, Manki Min, and Ding-Zhu Du Energy-efficient broadcast and multicast routing in ad hoc wireless networks In Performance, Computing, and Communications Conference, 2003 Conference Proceedings of the 2003 IEEE International, pages 87–94, April 2003 doi: 10.1109/PCCC 2003.1203687 105 TIEU LUAN MOI download : skknchat@gmail.com [11] Hsinghua Chou, G Premkumar, and Chao-Hsien Chu Genetic algorithms for communications network design - an empirical study of the factors that influence performance Evolutionary Computation, IEEE Transactions on, (3):236–249, Jun 2001 ISSN 1089-778X doi: 10.1109/4235.930313 [12] M.Z Chowdhury, Won Ryu, Eunjun Rhee, and Yeong Min Jang Handover between macrocell and femtocell for umts based networks In Advanced Communication Technology, 2009 ICACT 2009 11th International Conference on, volume 01, pages 237–241, Feb 2009 [13] T.A Chowdhury, R Bhattacharjee, and M.Z Chowdhury Handover priority based on adaptive channel reservation in wireless networks In Electrical Information and Communication Technology (EICT), 2013 International Conference on, pages 1–5, Feb 2014 doi: 10.1109/EICT.2014.6777831 [14] H.P Christos, S Kenneth, and N.Y Mineola Combinatorial optimization : algorithms and complexity Dover Publications, Inc, 1998 [15] M Clerc and J Kennedy The particle swarm - explosion, stability, and convergence in a multidimensional complex space Evolutionary Computation, IEEE Transactions on, 6(1):58–73, Feb 2002 ISSN 1089-778X doi: 10.1109/ 4235.985692 [16] M Dorigo and T Stă utzle Ant colony optimization MIT Press, 2004 [17] R Edirisinghe and A Zaslavsky Cross-layer contextual interactions in wireless networks Communications Surveys Tutorials, IEEE, 16(2):1114–1134, Second 2014 ISSN 1553-877X doi: 10.1109/SURV.2013.101813.00023 [18] F.N Abuali et al Terminal assignment in a communications network using genetic algorithms In ACM Conference on Computer Science, pages 74–81, 1994 [19] S.S Sanz et al A hybrid greedy-simulated annealing algorithm for the optimal location of controllers in wireless networks In Proceedings of the 5th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases, pages 159–164, 2006 [20] S.S Sanz et al Optimal switch location in mobile communication networks using hybrid genetic algorithms Appl Soft Comput., 8(4):1486–1497, September 2008 [21] M Galota, C Glaßer, S Reith, and H Vollmer A polynomial-time approximation scheme for base station positioning in umts networks In DIAL-M, pages 52–59, 2001 [22] Thomas Gaube and Franz Rothlauf The link and node biased encoding revisited: Bias and adjustment of parameters 2037:1–10, 2001 doi: 10.1007/ 3-540-45365-2_1 URL http://dx.doi.org/10.1007/3-540-45365-2_1 [23] C Glaßer, S Reith, and H Vollmer The complexity of base station positioning in cellular networks In ICALP Satellite Workshops, pages 167–178, 2000 [24] C Glaßer, S Reith, and H Vollmer The complexity of base station positioning in cellular networks Discrete Applied Mathematics, 148(1):1–12, 2005 [25] F Glover and M Laguna Tabu Search Kluwer Academic Publishers, Norwell, MA, USA, 1997 ISBN 079239965X 106 TIEU LUAN MOI download : skknchat@gmail.com [26] Goldberg and E David Genetic Algorithms in Search, Optimization and Machine Learning Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989 ISBN 0201157675 [27] Guifen Gu and Guili Peng The survey of gsm wireless communication system In Computer and Information Application (ICCIA), 2010 International Conference on, pages 121–124, Dec 2010 doi: 10.1109/ICCIA.2010.6141552 [28] Nguyen Duy Hiep and Huynh Thi Thanh Binh Improved genetic algorithm for solving optimal communication spanning tree problem In Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2013, HuangShan, China, July 12-14, 2013, pages 405–413, 2013 doi: 10.1007/978-3-642-37502-6_49 URL http://dx.doi org/10.1007/978-3-642-37502-6_49 [29] Tracey Ho and Desmond S Lun Network Coding - an Introduction Cambridge University Press, 2008 ISBN 978-0-521-87310-9 [30] Sidharth Jaggi, Michael Langberg, Sachin Katti, Tracey Ho, Dina Katabi, and Muriel Médard Resilient Network Coding in the Presence of Byzantine Adversaries In INFOCOM’07, pages 616–624 IEEE, 2007 [31] W.S Jang, H Kang, and B Lee Hybrid simplex-harmony search method for optimization problems In Evolutionary Computation, 2008 CEC 2008 (IEEE World Congress on Computational Intelligence), pages 4157–4164, June 2008 [32] L Kazovsky, Shing-Wa Wong, T Ayhan, K.M Albeyoglu, M.R.N Ribeiro, and A Shastri Hybrid optical x2013;wireless access networks Proceedings of the IEEE, 100(5):1197–1225, May 2012 ISSN 0018-9219 doi: 10.1109/ JPROC.2012.2185769 [33] J Kennedy and R.C Eberhart Swarm Intelligence Morgan Kaufmann Publishers, 2001 [34] Shahbaz Khan, Sadiq Ullah, Aziz Ahmed, and Sahibzada A Mahmud A survey of rate-adaptation schemes for IEEE 802.11 compliant wlans TIIS, (3):425–445, 2013 doi: 10.3837/tiis.2013.03.001 URL http://dx.doi.org/ 10.3837/tiis.2013.03.001 [35] S Khuri and T Chiu Heuristic algorithms for the terminal assignment problem In in Proc 1997 ACM Symp Applied Computing, pages 247–251, 1997 [36] Youngjun Kim, Taekook Kim, Myeongyu Kim, Yeunwoong Kyung, and Jinwoo Park Scalable wireless-optical broadband access network using reconfigurable optical backhaul and gateway selection method In Optical Internet 2014 (COIN), 2014 12th International Conference on, pages 1–2, Aug 2014 doi: 10.1109/COIN.2014.6950623 [37] S Kirkpatrick, C.D Gelatt, and M.P Vecchi Optimization by simulated annealing Science, 220:671–680, 1983 [38] Y Kishi, N Kurishima, Y Fujimoto, Y Ikenoue, H Iwama, H Uchiyama, M Matsuda, M Shimizu, K Fukushima, and Y Hirata Rapid recovery of base station backhaul by the neighbor regional wireless access network and its extension with the multi-hop wireless lan relay In Wireless Personal Multimedia Communications (WPMC), 2012 15th International Symposium on, pages 221–224, Sept 2012 107 TIEU LUAN MOI download : skknchat@gmail.com [39] J Knowles and D Corne A new evolutionary approach to the degreeconstrained minimum spanning tree problem Evolutionary Computation, IEEE Transactions on, 4(2):125–134, Jul 2000 ISSN 1089-778X doi: 10.1109/4235.850653 [40] J.D Knowles and D.W Corne A comparison of encodings and algorithms for multiobjective minimum spanning tree problems In Evolutionary Computation, 2001 Proceedings of the 2001 Congress on, volume 1, pages 544–551 vol 1, 2001 doi: 10.1109/CEC.2001.934439 [41] K Kraimeche, B Kraimeche, and K Chiang Optimization of a wireless access network ACM Symposium on Applied Computing, 2005 [42] B Krishnamachari and S Wicker Base station location optimization in cellular wireless networks using heuristic search algorithms L Wang (Edt), Springer, 2003 [43] H Kusetogullari Dynamic multiple description wavelet based image coding using enhanced particle swarm optimization Selected Topics in Signal Processing, IEEE Journal of, 9(1):125–138, Feb 2015 ISSN 1932-4553 doi: 10.1109/JSTSP.2014.2331911 [44] Youngseok Lee and B Mukherjee Traffic engineering in next-generation optical networks Communications Surveys Tutorials, IEEE, 6(3):16–33, Third 2004 ISSN 1553-877X doi: 10.1109/COMST.2004.5342291 [45] Fan Li, Yu Wang, and Xiang-Yang Li Gateway placement for throughput optimization in wireless mesh networks In Communications, 2007 ICC ’07 IEEE International Conference on, pages 4955–4960, June 2007 doi: 10.1109/ ICC.2007.818 [46] Lusheng Li, B Feldman, and J Arge Self-organizing security scheme for multi-hop wireless access networks In Aerospace Conference, 2004 Proceedings 2004 IEEE, volume 2, pages 1231–1240 Vol.2, March 2004 doi: 10.1109/AERO.2004.1367721 [47] B Liu, Z Liu, and D Towsley On the capacity of hybrid wireless networks In INFOCOM 2003 Twenty-Second Annual Joint Conference of the IEEE Computer and Communications IEEE Societies, volume 2, pages 1543–1552 vol.2, March 2003 doi: 10.1109/INFCOM.2003.1208989 [48] Hongbo Liu and A Abraham Fuzzy adaptive turbulent particle swarm optimization In Hybrid Intelligent Systems, 2005 HIS ’05 Fifth International Conference on, pages pp.–, Nov 2005 doi: 10.1109/ICHIS.2005.49 [49] R Mathar and T Niessen Optimum positioning of base stations for cellular radio networks Wirel Netw., 6(6):421–428, December 2000 [50] Rudolf Mathar and Thomas Niessen Optimum positioning of base stations for cellular radio networks Wireless Networks, 6(6):421–428, 2000 doi: 10.1023/ A:1019263308849 URL http://dx.doi.org/10.1023/A:1019263308849 [51] E Muneender and D.M Vinodkumar Particle swarm optimization with time varying acceleration coefficients for congestion management In Sustainable Utilization and Development in Engineering and Technology (STUDENT), 2012 IEEE Conference on, pages 92–96, Oct 2012 doi: 10.1109/STUDENT 2012.6408372 108 TIEU LUAN MOI download : skknchat@gmail.com [52] Vijayvaradharaj T Muralidharan and B Sundar Rajan Linear network coding, linear index coding and representable discrete polymatroids CoRR, abs/1306.1157, 2013 URL http://dblp.uni-trier.de/db/journals/ corr/corr1306.html#MuralidharanR13 [53] M.L Pilat and T White Using genetic algorithms to optimize acs-tsp In Ant Algorithms, pages 282–287, 2002 [54] F.M Rahman and M.A Gregory Quadrant based intelligent energy controlled multicast algorithm for mobile ad hoc networks In Advanced Communication Technology (ICACT), 2011 13th International Conference on, pages 12981303, Feb 2011 [55] Gă unther R Raidl and Bryant A Julstrom A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem In SAC (1), pages 440–445, 2000 [56] L Raisane, R Whitaker, and S Hurley A comparison of randomized and evolutionary approaches for optimizing base station site selection In ACM Symposium on Applied Computing, pages 1159–1165, 2004 [57] A Ratnaweera, S Halgamuge, and H.C Watson Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients Evolutionary Computation, IEEE Transactions on, 8(3):240–255, June 2004 ISSN 1089-778X doi: 10.1109/TEVC.2004.826071 [58] A Reaz, V Ramamurthi, D Ghosal, J Benko, Wei Li, S Dixit, and B Mukherjee Enhancing multi-hop wireless mesh networks with a ring overlay In Sensor, Mesh and Ad Hoc Communications and Networks Workshops, 2008 SECON Workshops ’08 5th IEEE Annual Communications Society Conference on, pages 1–6, June 2008 doi: 10.1109/SAHCNW.2008.18 [59] J Robinson and E.W Knightly A performance study of deployment factors in wireless mesh networks In INFOCOM 2007 26th IEEE International Conference on Computer Communications IEEE, pages 2054–2062, May 2007 doi: 10.1109/INFCOM.2007.238 [60] Franz Rothlauf On optimal solutions for the optimal communication spanning tree problem Operations Research, 57(2):413–425, 2009 doi: 10.1287/ opre.1080.0592 URL http://dx.doi.org/10.1287/opre.1080.0592 [61] Franz Rothlauf, David E Goldberg, and Armin Heinzl Network random keysa tree representation scheme for genetic and evolutionary algorithms Evolutionary Computation, 10(1):75–97, 2002 doi: 10.1162/106365602317301781 URL http://dx.doi.org/10.1162/106365602317301781 [62] Yuhui Shi and R Eberhart A modified particle swarm optimizer In Evolutionary Computation Proceedings, 1998 IEEE World Congress on Computational Intelligence., The 1998 IEEE International Conference on, pages 69–73, May 1998 doi: 10.1109/ICEC.1998.699146 [63] M Sipser Introduction to the theory of computation PWS Publishing Company, 2006 [64] Aaron So and Ben Liang Minimum cost configuration of relay and channel infrastructure in heterogeneous wireless mesh networks In NETWORKING 2007 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet, 6th International IFIP-TC6 Networking Conference, 109 TIEU LUAN MOI download : skknchat@gmail.com Atlanta, GA, USA, May 14-18, 2007, Proceedings, pages 275–286, 2007 doi: 10.1007/978-3-540-72606-7_24 URL http://dx.doi.org/10.1007/ 978-3-540-72606-7_24 [65] Sang-Moon Soak A new evolutionary approach for the optimal communication spanning tree problem IEICE Transactions, 89-A(10):2882–2893, 2006 doi: 10.1093/ietfec/e89-a.10.2882 URL http://dx.doi.org/10.1093/ ietfec/e89-a.10.2882 [66] Sang-Moon Soak and Moon-Gu Jeon The property analysis of evolutionary algorithms applied to spanning tree problems Appl Intell., 32(1):96–121, 2010 doi: 10.1007/s10489-008-0137-8 URL http://dx.doi.org/10.1007/ s10489-008-0137-8 [67] A Tizghadam and A Leon-Garcia A graph theoretical approach to traffic engineering and network control problem In Teletraffic Congress, 2009 ITC 21 2009 21st International, pages 1–8, Sept 2009 [68] Shiao-Li Tsao and Chung-Huei Huang A survey of energy efficient MAC protocols for IEEE 802.11 WLAN Computer Communications, 34(1):54– 67, 2011 doi: 10.1016/j.comcom.2010.09.008 URL http://dx.doi.org/10 1016/j.comcom.2010.09.008 [69] Ugo Vaccaro Introduction: Approximation and randomized algorithms in communication networks In ICALP Satellite Workshops, pages 97–98, 2000 [70] Phùng Văn Vận, Trần Hồng Quân, and Nguyễn Quý Minh Hiền Mạng viễn thông xu hướng phát triển NXB Bưu điện, Hà Nội, 2002 [71] Peng-Jun Wan, Yu Cheng, Zhu Wang, and F Yao Multiflows in multichannel multi-radio multihop wireless networks In INFOCOM, 2011 Proceedings IEEE, pages 846–854, April 2011 doi: 10.1109/INFCOM.2011.5935308 [72] Junfang Wang, Bin Xie, Kan Cai, and D.P Agrawal Efficient mesh router placement in wireless mesh networks In Mobile Adhoc and Sensor Systems, 2007 MASS 2007 IEEE International Conference on, pages 1–9, Oct 2007 doi: 10.1109/MOBHOC.2007.4428616 [73] Bang Ye Wu Approximation algorithms for the optimal p-source communication spanning tree Discrete Applied Mathematics, 143(1-3):31–42, 2004 doi: 10.1016/j.dam.2003.10.002 URL http://dx.doi.org/10.1016/j.dam 2003.10.002 [74] A Zemlianov and G de Veciana Capacity of ad hoc wireless networks with infrastructure support Selected Areas in Communications, IEEE Journal on, 23(3):657–667, March 2005 ISSN 0733-8716 doi: 10.1109/JSAC.2004.842536 [75] Yan Zhang, Nirwan Ansari, Mingquan Wu, and Heather Yu On wide area network optimization Communications Surveys Tutorials, IEEE, 14(4):1090– 1113, Fourth 2012 ISSN 1553-877X doi: 10.1109/SURV.2011.092311.00071 [76] Dan Zhao, Hongjun Liu, Xiaofeng Hu, and Chunqing Wu Towards network convergence and traffic engineering optimization In Performance Computing and Communications Conference (IPCCC), 2012 IEEE 31st International, pages 448–455, Dec 2012 doi: 10.1109/PCCC.2012.6407656 110 TIEU LUAN MOI download : skknchat@gmail.com [77] Jin-Yi Zhou, Shu-Tao Xia, Yong Jiang, Hai-Tao Zheng, and Laizhong Cui Maximum multiflow in wireless network coding IEICE Transactions, 96-B(7): 1780–1790, 2013 URL http://dblp.uni-trier.de/db/journals/ieicet/ ieicet96b.html#ZhouXJZC13 [78] Ping Zhou, Xudong Wang, and R Rao Asymptotic capacity of infrastructure wireless mesh networks Mobile Computing, IEEE Transactions on, 7(8): 1011–1024, Aug 2008 ISSN 1536-1233 doi: 10.1109/TMC.2007.70778 [79] Ping Zhou, Xudong Wang, B S Manoj, and Ramesh R Rao On optimizing gateway placement for throughput in wireless mesh networks EURASIP J Wireless Comm and Networking, 2010, 2010 doi: 10.1155/2010/368423 URL http://dx.doi.org/10.1155/2010/368423 111 TIEU LUAN MOI download : skknchat@gmail.com ... 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 TỐN TỐI ƯU TRONG MẠNG KHƠNG DÂY Chun ngành: Cơ sở tốn học cho Tin học Mã số: 624 6011 0 LUẬN ÁN TIẾN SỸ TOÁN HỌC NGƯỜI HƯỚNG DẪN... tối ưu mạng Trong chương này, phần đầu luận án giới thiệu tổng quan mạng không dây, vấn đề tối ưu mạng Tiếp theo, luận án trình bày thuật tốn tiến hóa như: giải thuật di truyền (GA), tối ưu hóa. .. tiết số lớp toán quy hoạch khác kỹ thuật giải chúng trình bày [14] Trong luận án tác giả tập trung sử dụng thuật tốn tiến hóa để giải toán tối ưu mạng máy tính 1.3 Các thuật tốn tiến hóa Trong