Thuật toán lập kế hoạch mạng Wimax trên địa hình 3D – GIS

Nội dung tài liệu: Thuật toán lập kế hoạch mạng Wimax trên địa hình 3D – GIS

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------ PHẠM HUY THÔNG THUẬT TOÁN LẬP KẾ HOẠCH MẠNG WiMAX TRÊN ĐỊA HÌNH 3D – GIS LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – 2013
2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------ PHẠM HUY THÔNG THUẬT TOÁN LẬP KẾ HOẠCH MẠNG WiMAX TRÊN ĐỊA HÌNH 3D – GIS Chuyên ngành: Cơ sở toán học cho tin học Mã số: 60.46.01.10 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN THỊ HỒNG MINH Hà Nội – 2013
3. Lời cảm ơn Tôi xin chân thành gửi lời cảm ơn đến quý thầy cô, các anh chị em đồng nghiệp của Trung tâm Tính toán Hiệu Năng Cao và khoa Toán – Cơ – Tin học, trường Ðại học Khoa học Tự nhiên đã quan tâm giúp đỡ, tạo điều kiện về nhiều mặt, chỉ bảo tận tình trong quá trình tôi thực hiện luận văn. Nhờ đó tôi đã tiếp thu được nhiều ý kiến đóng góp và nhận xét quí báu thông qua các buổi thảo luận seminar. Tôi xin được gửi lời cảm ơn sâu sắc nhất tới giáo viên hướng dẫn là TS. Nguyễn Thị Hồng Minh đã trực tiếp hướng dẫn, định hướng chuyên môn, giúp đỡ để tôi có thể hoàn thành luận văn này. Cuối cùng xin cảm ơn gia đình, bạn bè đã cổ vũ và động viên tôi trong công việc và học tập cũng như trong quá trình thực hiện luận văn này. Xin chúc mọi người luôn mạnh khoẻ, đạt được nhiều thành tích cao trong công tác, học tập và nghiên cứu khoa học! Hà Nội, ngày 25 tháng 11 năm 2013 Tác giả Phạm Huy Thông
4. Mục lục Danh mục viết tắt ..................................................................................................... i Danh mục các hình ................................................................................................. iii Danh mục các bảng ................................................................................................ iv Lời nói đầu .............................................................................................................. v Chương 1 – Một số kiến thức cơ sở về bài toán lập kế hoạch mạng WiMAX trên 3D–GIS ................................................................................................................... 1 1.1. Hệ thống thông tin địa lý 3D–GIS ........................................................... 1 1.1.1. Định nghĩa ............................................................................................ 1 1.1.2. Các chuẩn của địa hình độ cao số 3D–GIS ........................................... 2 1.2. Cơ bản về WiMAX ................................................................................. 3 1.2.1. Khái niệm về WiMAX ......................................................................... 3 1.2.2. Các chuẩn WiMAX .............................................................................. 4 1.2.3. Cấu hình mạng ..................................................................................... 6 1.2.4. Ưu điểm của mạng WiMAX ................................................................. 8 1.3. Bài toán lập kế hoạch mạng WiMAX ...................................................... 9 1.3.1. Mô hình hóa bài toán ............................................................................ 9 1.3.2. Tính toán chất lượng sóng trên địa hình 3D–GIS ................................ 13 1.3.3. Một số nghiên cứu liên quan ............................................................... 17 1.4. Kết luận chương .................................................................................... 19 Chương 2 – Nhận dạng địa hình độ cao số ............................................................. 21 2.1. Giới thiệu về bài toán nhận dạng địa hình độ cao số .............................. 21 2.2. Trích chọn đặc trưng ............................................................................. 22 2.3. Thuật toán phân loại rừng ngẫu nhiên ................................................... 24 2.4. Kết luận chương .................................................................................... 27 Chương 3 – Thuật toán lai lập kế hoạch mạng WiMAX trên địa hình 3D–GIS ...... 28 3.1. Ý tưởng chính ....................................................................................... 28 3.2. Thuật toán BTP ..................................................................................... 28 3.3. Thuật toán PSO cải tiến ......................................................................... 29
5. 3.3.1. Khởi tạo ............................................................................................. 29 3.3.2. Đánh giá, cập nhật vận tốc và vị trí ..................................................... 30 3.3.3. Tối ưu số sector .................................................................................. 33 3.3.4. Đột biến.............................................................................................. 34 3.3.5. Điều kiện dừng ................................................................................... 34 3.4. Thuật toán WNPA–3DT ........................................................................ 35 3.5. Kết luận chương .................................................................................... 36 Chương 4 – Một số kết quả thực nghiệm ............................................................... 37 4.1. Mục tiêu và môi trường thực nghiệm .................................................... 37 4.2. Kết quả thực nghiệm so sánh với các thuật toán khác về độ hiệu quả .... 41 4.3. Kết quả thực nghiệm so sánh với các thuật toán khác về thời gian chạy.49 4.4. Kết quả thực nghiệm so sánh trên các bộ tham số khác nhau ................. 55 4.5. Kết luận chương .................................................................................... 61 KẾT LUẬN ........................................................................................................... 62 Danh mục các công trình công bố có liên quan đến luận văn ................................. 63 TÀI LIỆU THAM KHẢO ..................................................................................... 64
6. Danh mục viết tắt Viết tắt Viết đầy đủ Ý nghĩa BS Base Station Trạm thu phát cơ sở BPSK Binary Phase Shift Keying Điều chế pha nhị phân BWA Broadband Wireless Access Mạng không dây băng thông rộng CID Connection ID ID kết nối DEM Digital Elevation Model Mô hình độ cao số GA Genetic Algorithm Thuật toán di truyền GIS Geographic Information System Hệ thống thông tin địa lý Institute of Electrical and IEEE Học viện Kỹ nghệ Điện và Điện tử Electronics Engineers LOS Line Of Sight Đường truyền thẳng MIMO Multiple Input Multiple Output Đa đầu vào và đa đầu ra NLOS Non Line Of Sight Đường truyền không thẳng Orthogonal Frequency Division OFDM Multiplexing Kỹ thuật điều chế đa sóng mang Orthogonal Frequency Division OFDMA Đa truy nhập phân tần trực giao Multiple Access Personal Computer Memory Card Hiệp hội quốc tế thẻ nhớ máy tính PCMCIA International Association cá nhân PDU Protocol Data Unit Đơn vị dữ liệu giao thức PMP Point to Multipoint Mạng đa điểm PSO Particle Swarm Optimization Thuật toán tối ưu bầy đàn QPSK Quadature Phase Shift Keying Điều chế pha trực giao Thuật toán phân loại rừng ngẫu RF Random Forest nhiên SS Subscriber Station Trạm thuê bao Đa truy cập phân chia theo thời TDMA Time Division Multiple Access gian TIN Triangulated Irregular Network Mạng tam giác không đều Hàm xóa các đầu đọc không cần TRE Tentative Reader Elimination thiết USGS The U.S Geological Survey Cục đo đạc địa chất Hoa Kỳ i
7. Một phép chiếu biểu diễn bề mặt UTM Universal Transverse Mercator địa cầu VoIP Voice over IP Điện thoại qua giao thức IP Worldwide Interoperability for Mạng tương tác toàn cầu với truy WiMAX Microwave Access nhập vi ba WNPA- WiMAX Network Planning Thuật toán lập kế hoạch mạng 3DT Algorithm – 3D Terrain WiMAX trên địa hình 3D ii
8. Danh mục các hình Hình 1.1: Hệ thống GIS ........................................................................................... 1 Hình 1.2: Mô hình hoạt động WiMAX mạng điểm – đa điểm PMP ......................... 7 Hình 1.3: Mô hình hoạt động WiMAX mạng mắt lưới............................................. 8 Hình 1.4: Mô hình tính toán độ suy hao trong trường hợp một vật cản .................. 15 Hình 2.1: Ví dụ về các đặc trưng của việc nhận dạng địa hình độ cao số................ 24 Hình 3.1: Sơ đồ hoạt động của thuật toán WNPA-3DT .......................................... 35 Hình 4.1: Phân bố đều của 4000 người dùng trên địa hình nhỏ .............................. 38 Hình 4.2: Phân bố đều của 10000 người dùng trên địa hình lớn ............................. 39 Hình 4.3: Phân bố không đều của 4000 người dùng trên địa hình nhỏ.................... 40 Hình 4.4: Phân bố không đều của 10000 người dùng trên địa hình lớn .................. 41 Hình 4.5: So sánh giá trị hàm lượng giá fitness ở kịch bản 1 và kịch bản 2 ............ 44 Hình 4.6: So sánh giữa kịch bản 1 và kịch bản 3 .................................................... 47 Hình 4.7: So sánh giá trị fitness với bốn kịch bản .................................................. 49 Hình 4.8: Biểu đồ tăng tốc và hiệu quả của các trường hợp trong kịch bản 1 ......... 51 Hình 4.9: So sánh thời gian chạy trung bình giữa kịch bản 1 và kịch bản 2 ............ 52 Hình 4.10: So sánh thời gian chạy trung bình giữa kịch bản 1 và kịch bản 3 .......... 53 Hình 4.11: So sánh thời gian chạy trung bình giữa kịch bản 1 và kịch bản 4 .......... 55 Hình 4.12: So sánh giá trị Fitness giữa các bộ tham số qua các trường hợp trong cả bốn kịch bản .......................................................................................................... 60 iii
9. Danh mục các bảng Bảng 1: So sánh kết quả chạy của các thuật toán với địa hình nhỏ và người dùng phân bố đều ........................................................................................................... 42 Bảng 2: So sánh kết quả chạy của các thuật toán với địa hình lớn và người dùng phân bố đều ........................................................................................................... 45 Bảng 3: So sánh kết quả chạy của các thuật toán với địa hình nhỏ và người dùng phân bố không đều ................................................................................................ 46 Bảng 4: So sánh kết quả chạy của các thuật toán với địa hình lớn và người dùng phân bố không đều ................................................................................................ 48 Bảng 5: Thời gian tính toán song song của WNPA-3DT với kịch bản 1 ................ 50 Bảng 6: Thời gian tính toán song song của WNPA-3DT với kịch bản 2 ................ 52 Bảng 7: Thời gian tính toán song song của WNPA-3DT với kịch bản 3 ................ 53 Bảng 8: Thời gian tính toán song song của WNPA-3DT với kịch bản 4 ................ 54 Bảng 9: Kết quả chạy WNPA-3DT với các tham số khác nhau ở kịch bản 1 .......... 56 Bảng 10: Kết quả chạy WNPA-3DT với các tham số khác nhau ở kịch bản 2 ........ 57 Bảng 11: Kết quả chạy WNPA-3DT với các tham số khác nhau ở kịch bản 3 ........ 58 Bảng 12: Kết quả chạy WNPA-3DT với các tham số khác nhau ở kịch bản 4 ........ 59 iv
10. Lời nói đầu Sự phát triển không ngừng của công nghệ thông tin đã đưa tin học thâm nhập sâu vào nhiều lĩnh vực khoa học và đời sống, mở ra một giai đoạn mới trong quá trình phát triển khoa học. Hệ thống thông tin địa lý ba chiều (3D–GIS) là một trong những ứng dụng rất có giá trị của công nghệ tin học trong ngành địa lý, điều tra cơ bản, quy hoạch đô thị và cảnh báo môi trường. Với sự phát triển không ngừng của thế giới cũng như của đất nước ta hiện nay, việc tổ chức quản lý thông tin địa lý một cách tổng thể có đóng góp không nhỏ vào việc sử dụng hiệu quả hơn các nguồn lực và tài nguyên. Trong số các ứng dụng của 3D–GIS, chúng tôi quan tâm hơn cả đến việc lập kế hoạch mạng không dây, đặc biệt là WiMAX trên địa hình 3D–GIS. Vấn đề này được nhóm nghiên cứu của chúng tôi quan tâm và thực hiện tại Trung tâm tính toán Hiệu Năng Cao, trường Đại học Khoa học Tự nhiên từ năm 2011. Như chúng ta đã biết, mạng Internet đóng một vai trò vô cùng quan trọng trong đời sống hiện đại. Nhờ có Internet, chúng ta có thể cập nhật tin tức, trao đổi thông tin một cách nhanh chóng, dễ dàng và mọi lúc. Hơn nữa, với sự ra đời của mạng không dây, bằng việc sử dụng các trạm thu phát sóng phủ sóng trong một vùng rộng lớn đến vài chục km2, Internet đã “vươn” đến những vùng miền xa xôi nhất. Tuy nhiên, mạng không dây cũng có những nhược điểm của nó. Các sóng mạng không dây chủ yếu là các sóng radio, dễ dàng bị cản trở bởi các vật cản như núi, đồi, nhà cửa, vv. Do đó, bài toán đặt ra là phải đặt các trạm thu phát sóng một cách hợp lý sao cho chất lượng sóng tại mọi điểm đủ “tốt” và chi phí cho số lượng trạm thu phát là nhỏ nhất có thể. Bài toán này đã được nghiên cứu khá nhiều trong thời gian gần đây. Tuy nhiên các phương pháp giải còn nhiều hạn chế, như chỉ áp dụng trên bản đồ hai chiều, lập kế hoạch mạng thủ công hoặc chỉ chú trọng đến một mục tiêu như chất lượng sóng hoặc chi phí, một vài phương pháp có thời gian tính toán lớn và đặc biệt là không xác định được các vị trí có thể đặt trạm thu phát. Nếu có một phương pháp giải đủ tốt, bài toán này sẽ đặc biệt hữu ích đối với các nhà v