Luận văn Tìm hiểu tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất

Tìm hiều tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất 1 4 MỤC LỤC LỜI NÓI ĐẦU CHƯƠNG 1 GIỚI THIỆU ĐỀ TÀI LUẬN VĂN ............................................................... 5 CHƯƠNG 2 TÌM HIỂU BẢN ĐỒ SỐ ................................................................................ 6 2.1 Bản đồ số là gì? ......................................................................................................... 7 2.2 Tìm hiểu bản đồ số .................................................................................................... 7 2.2.1 Dữ liệu bản đồ số ................................................................................................ 7 2.2.1.1 Khái niệm dữ liệu không gian ..................................................................... 7 2.2.1.2 Ví dụ về dữ liệu không gian ........................................................................ 7 2.2.2 Phân biệt trường dữ liệu không gian tương tự và dữ liệu không gian số ........... 8 2.3 Các định dạng dữ liệu ................................................................................................ 9 2.4 Dữ liệu vector trong bản đồ số ................................................................................ 10 2.4.1 Các điểm ........................................................................................................... 10 2.4.2 Các đường ......................................................................................................... 11 2.4.3 Các miền ........................................................................................................... 12 2.4.4 Các thuộc tính của vector dữ liệu ..................................................................... 13 2.4.5 Kiến trúc tầng dữ liệu vector ............................................................................ 14 2.5 Pixel và độ phân giải ............................................................................................... 15 2.5.1 Pixel .................................................................................................................. 15 2.5.2 Độ phân giải...................................................................................................... 15 2.6 Ứng dụng của bản đồ số .......................................................................................... 16 CHƯƠNG 3 TÌM HIỂU VỀ MẠNG THÔNG TIN DI ĐỘNG ........................................ 17 3.1 Thông tin di động là gì? ........................................................................................... 18 3.2 Cấu trúc mạng thông tin di động số Cellular (Tế bào) ............................................ 18 3.3 Sơ lược quá trình phát triển của hệ thống di động .................................................. 20 3.4 Một số kỹ thuật đa truy nhập ................................................................................... 23 3.4.1 TDMA - Time Domain Multiple Access (Dải băng hẹp) ................................ 23 3.4.1.1 Tổng quan TDMA ..................................................................................... 23 3.4.1.2 Loại hệ thống TDMA Bắc Mỹ .................................................................. 23 3.4.1.3 GSM - Group Special Mobile (Hệ thống truyền thông di động toàn cầu) 25 3.4.2 CDMA - Code Division Multiple Access (Dải băng rộng hay quang phổ lớn) ................................................................................................................................... 26 3.4.2.1 Giới thiệu CDMA ...................................................................................... 26 3.4.2.2 Thủ tục phát/thu tín hiệu ............................................................................ 27 3.4.2.3 Một số đặc tính của CDMA ....................................................................... 27 CHƯƠNG 4 TÌM HIỂU HỆ THỐNG GPS ...................................................................... 31 4.1 Sự ra đời của hệ thống GPS ..................................................................................... 32 4.2 Nghiên cứu các thành phần hệ thống GPS .............................................................. 33 4.2.1 Nghiên cứu việc thiết kế hệ thống GPS ............................................................ 33 4.2.2 Các thành phần hệ thống GPS .......................................................................... 35 4.2.2.1 Phần vũ trụ ................................................................................................. 36 4.2.2.2 Phần điều khiển ......................................................................................... 40 4.2.2.3 Phần sử dụng ............................................................................................. 41 4.3 Hoạt động của hệ thống GPS ................................................................................... 42 Trang Tìm hiều tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất 2 4.3.1 Sóng của vệ tinh GPS ....................................................................................... 42 4.3.2 Vị trí trên mặt đất được xác định như thế nào qua hệ thống GPS? .................. 44 4.4 Ứng dụng của hệ thống GPS ................................................................................... 47 CHƯƠNG 5 TÍCH HỢP BẢN ĐỒ SỐ, HỆ THỐNG GPS TRÊN ĐIỆN THOẠI DI ĐỘNG VÀ BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT ............................................... 49 5.1 Tích hợp bản đồ số với GPS trên điện thoại di động .............................................. 50 5.1.1 Giới thiệu chung ............................................................................................... 50 5.1.2 Một số dịch vụ dựa trên vị trí ........................................................................... 51 5.1.2.1 Dịch vụ thông tin dựa trên vị trí ................................................................ 51 5.1.2.2 Tính cước theo vị trí địa lý ........................................................................ 52 5.1.2.3 Dịch vụ khẩn cấp ....................................................................................... 52 5.1.2.4 Dịch vụ dò tìm ........................................................................................... 52 5.1.3 Các kỹ thuật định vị thuê bao di động .............................................................. 53 5.1.3.1 Kỹ thuật Cell-ID ........................................................................................ 53 5.1.3.2 A-GPS (Assisted GPS - hỗ trợ GPS) ......................................................... 54 5.1.3.3 Phương pháp kết hợp ................................................................................. 56 5.2 Bài toán tìm đường đi ngắn nhất trên PocketPC. .................................................... 57 5.2.1 Giới thiệu bài toán ............................................................................................ 57 5.2.2 Thuật toán sử dụng trong bài toán .................................................................... 58 5.2.3 Dữ liệu bản đồ .................................................................................................. 61 5.2.4 Lập trình ........................................................................................................... 62 5.2.5 Một số hình ảnh của chương trình .................................................................... 64 5.2.6 Đánh giá chương trình ...................................................................................... 66 5.2.6.1 Các điểm đã đạt được ................................................................................ 66 5.2.6.2 Các điểm chưa đạt được, hướng phát triển ................................................ 66 CHƯƠNG 6 KẾT LUẬN .................................................................................................. 68 PHỤ LỤC .......................................................................................................................... 70 1. Niên biểu phát triển của hệ thống GPS ..................................................................... 71 2. Một số vệ tinh GPS .................................................................................................... 80 3. Hệ thống điện thoại di động vùng Bắc Âu (NMT) .................................................... 82 4. Hệ thống viễn thông di động toàn cầu (UMTS) ........................................................ 83 5. Kỹ thuật E-OTD ........................................................................................................ 85 6. Một số khai báo lớp và định nghĩa hàm chương trình bài toán tìm đường đi ngắn nhất ................................................................................................................................ 86 TÀI LIỆU THAM KHẢO ................................................................................................. 91 THỐNG KÊ HÌNH ẢNH, CÁC BẢNG Hình 2-1 Bản đồ số Hà Nội ................................................................................................. 8 Hình 2-2 So sánh giữa bản đồ số và bản đồ giấy .............................................................. 10 Hình 2-3 Biểu diễn các điểm trong hệ tạo độ .................................................................... 10 Hình 2-4 Biểu diến đường nối các điểm ............................................................................ 11 Hình 2-5 Miền giới hạn ..................................................................................................... 12 Tìm hiều tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất 3 Hình 2-6 Bản đồ số về đường Hà Nội ............................................................................... 13 Hình 2-7 Bản đồ được chia làm các Pixel ......................................................................... 15 Hình 2-8 Độ phân giải ....................................................................................................... 15 Hình 3-1 Hệ thống điện thoại di động ............................................................................... 18 Hình 3-2 Hệ thống điện thoại di động ............................................................................... 19 Hình 3-3 Sự phát triển của hệ thống di động ..................................................................... 20 Hình 3-4 PhổTDMA .......................................................................................................... 23 Hình 3-5 Cấu trúc khung ................................................................................................... 24 Hình 3-6 Dạng khe thời gian từ máy di động đến trạm gốc .............................................. 24 Hình 3-7 Dạng khe thời gian từ trạm gốc tới máy di động ............................................... 25 Hình 3-8 Đường kết nối trong khi chuyển vùng mềm ...................................................... 28 Hình 3-9 Giao thoa từ BS bên cạnh ................................................................................... 29 Hình 4-1 Các thành phần của hệ thống GPS ..................................................................... 36 Hình 4-2 Các vệ tinh GPS bay trên quĩ đạo ...................................................................... 36 Hình 4-3 Vệ tinh GPS thế hệ mới ...................................................................................... 37 Hình 4-4 Vệ tinh Block I ................................................................................................... 38 Hình 4-5 Vị trí các trạm điều khiển vệ tinh GPS .............................................................. 40 Hình 4-6 Thiết bị nhận GPS cài đặt sẵn trên xe Honda Accord ........................................ 42 Hình 4-7 Thu tín hiệu vệ tinh GPS .................................................................................... 45 Hình 4-8 Vệ tinh GPS truyền tín hiệu về trái đất .............................................................. 46 Hình 4-9 3 hình cầu giao nhau tai 2 điểm vị trí sẽ xác định được chính xác .................... 46 Hình 5-1 Mô hình kết hợp Mobile, GPS, DigitalMap ....................................................... 50 Hình 5-2 Phần mềm tìm đường Wayfinder trên mobile .................................................... 51 Hình 5-3 Xe ô tô được gắn thiết bị thu GPS ..................................................................... 52 Hình 5-4 Cell-ID kết hợp với Cell-sector hoặc TA ........................................................... 54 Hình 5-5 Nguyên lý hoạt động của A-GPS ...................................................................... 55 Hình 5-6 Bản đồ được chia thành các ô - cell ................................................................... 61 Hình 5-7 Bản đồ số trên PocketPC .................................................................................... 64 Hình 5-8 Kết quả tìm đường đi.......................................................................................... 65 Hình 5-9 Hình ảnh bản đồ số phóng to .............................................................................. 66 Hình 0-1 Vệ tinh Block IIA ............................................................................................... 80 Hình 0-2 Vệ tinh Block IIA ............................................................................................... 81 Hình 0-3 Vệ tinh Block IIF ............................................................................................... 81 Hình 0-4 Nguyên lý hoạt động của E-OTD ....................................................................... 85 Bảng 2-1So sánh trường dữ liệu không gian tương tự và dữ liệu không gian số ................ 8 Bảng 4-1 Thông số kỹ thuật vệ tinh Block I ..................................................................... 38 Bảng 4-2 Thông số kỹ thuật vệ tinh Block II .................................................................... 39 Bảng 4-3 Một số máy định vị GPS .................................................................................... 42 Bảng 5-1 Đặc tính kỹ thuật A-GPS ................................................................................... 55 Bảng 5-2 Đặc tính phương pháp kết hợp ........................................................................... 56 Bảng 0-1 Thông số kỹ thuật vệ tinh Block IIF .................................................................. 82 Tìm hiều tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất 4 Lời Nói Đầu Những năm qua, sự phát triển mạnh mẽ của hai nghành công nghệ thông tin và công nghệ viễn thông đã cung cấp ngày càng nhiều loại hình dịch vụ mới đa dạng, chất lượng cao đáp ứng ngày càng tốt các yêu cầu của khách hàng. Thế kỷ 21 đã và đang chứng kiến sự bùng nổ của công nghệ thông tin trong đó thông tin đóng vai trò rất quan trọng. Thông tin vị trí đã được phát triển từ những năm 70 của thế kỷ trước. Từ khi bắt đầu phát triển cho đến nay, thông tin vị trí phát triển rất mạnh, khẳng định vai trò quan trọng trong các lĩnh vực đời sống con người. Ngày nay, với việc đưa vào hoạt động hệ thống định vị toàn cầu GPS thì thông tin vị trí đã được xác định đơn giản và có độ chính xác cao. Song song với việc phát triển của thông tin vị trí, mạng thông tin di động cũng phát triển rất mạnh mẽ tạo điều kiện cho các dịch vụ tích hợp thông tin vị trí với mạng thông tin di động ra đời. Để hiểu rõ hơn về các dịch vụ tích hợp thông tin vị trí với mạng thông tin di động em đã quyết định lựa chọn đề tài “Tìm hiểu tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất”. Bài toán tìm đường đi ngắn nhất của em trình bày mới chỉ dừng lại ở mức minh họa cho sự tích hợp bản đồ số trên điện thoại di động. Nội dung chính của luận văn gồm: Chương 1: Giới thiệu đề tài. Chương 2: Tìm hiểu bản đồ số. Chương 3: Tìm hiểu mạng thông tin di động. Chương 4: Tìm hiểu GPS hệ thống GPS. Chương 5: Tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất. Trong quá trình làm luận văn tốt nghiệp, mặc dù em đã cố gắng nhiều nhưng do trình độ có hạn nên không thể tránh khỏi những sai sót, em rất mong nhận được sự phê bình, hướng dẫn, và sự giúp đỡ của Thầy cô, bạn bè. Em xin chân thành cảm ơn sự giúp đỡ, chỉ bảo tận tình của Thầy Phạm Hồng Nguyên cùng các thầy cô trong khoa Công nghệ Thông tin đã giúp em hoàn thành luận văn tốt nghiệp. Tìm hiều tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất 5 CHƯƠNG 1 GIỚI THIỆU ĐỀ TÀI LUẬN VĂN Ngày nay cùng với sự phát triển không ngừng của khoa học, kỹ thuật… nhu cầu con người ngày vì thế ngày càng được nâng cao cả về chất lượng và số lượng. Thiết bị di động ngày càng khẳng định vị trí quan trọng của mình trong đời sống con người… Khi mới ra đời thiết bị di động thật là một kì tích của khoa học, các nhà cung cấp mạng di động đã giúp con người “xích lại gần nhau hơn”. Chúng ta có thể nghe thấy giọng nói của một người cách mình nửa vòng trái đất mà chỉ cần một chiếc điện thoại di động... rồi là nhiều tiện ích khác nữa mà thiết bị di động đem đến cho con người: nhắn tin, chơi games, các dịch vụ WAP(Wireless Application Protocol – giao thức ứng dụng không dây) như lướt Web trực tuyến, kiểm tra thư Yahoo, nghe nhạc, xem truyền hình trực tuyến... và một ứng dụng đặc biệt trên thiết bị di động mà ta sẽ trình bày trong bài luận văn này đó là: “tích hợp bản đồ số và GPS trên thiết bị di động” – tức là ta sẽ nghiên cứu sự tích hợp bản đồ số vào thiết bị di động sau đó dựa vào tín hiệu thu được từ hệ thống GPS - Global Positioning System (hệ thống định vị toàn cầu) để xử lí, đáp ứng yêu cầu của người dùng (ví dụ như việc tìm đường đi trên thiết bị di động). Tìm hiều tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất 6 CHƯƠNG 2 TÌM HIỂU BẢN ĐỒ SỐ 2.1 Bản đồ số là gì? 2.2 Tìm hiểu bản đồ số 2.2.1 Dữ liệu bản đồ số 2.2.1.1 Khái niệm dữ liệu không gian 2.2.1.2 Ví dụ về dữ liệu không gian 2.2.2 Phân biệt trường dữ liệu không gian tương tự và dữ liệu không gian số 2.3 Các định dạng dữ liệu 2.4 Dữ liệu vector trong bản đồ số 2.4.1 Các điểm 2.4.2 Các đường 2.4.3 Các miền 2.4.4 Các thuộc tính của vector dữ liệu 2.4.5 Kiến trúc tầng dữ liệu vector 2.5 Pixel và độ phân giải 2.5.1 Pixel 2.5.2 Độ phân giải 2.6 Ứng dụng của bản đồ số Nội dung Tìm hiều tích hợp bản đồ số, hệ thống GPS trên điện thoại di động và bài toán tìm đường đi ngắn nhất 7 2.1 Bản đồ số là gì? Bản đồ số là loại bản đồ được thành lập dưới dạng cơ sở dữ liệu máy tính trên cơ sở xử lý số liệu nhận được từ các thiết bị quét chuyên dụng, ảnh hàng không, ảnh vệ tinh, viễn thám hoặc số hóa các bản đồ được chế tác theo phương pháp cổ điển, trong đó toàn bộ thông tin về các đối tượng được mã hóa thành dữ liệu số và lưu giữ trên các băng, đĩa từ, đĩa quang… Thông tin trong bản đồ số thường được tổ chức quản lý theo các lớp, tập hợp các dữ liệu có cùng thuộc tính (vùng, đường, điểm, chữ) về các đối tượng cùng loại, thể hiện một nội dung của bản đồ tổng thể. Số lượng các lớp tùy thuộc vào yêu cầu cụ thể, nguồn cung cấp dữ liệu (các cơ sở dữ liệu ảnh quét có thể cho hàng trăm lớp) và khả năng quản lý của phần mềm chuyên dùng. Tùy theo yêu cầu sử dụng, các lớp thông tin có thể được hiển thị trên màn hình hoặc in trên giấy với tỉ lệ tùy chọn, riêng biệt hoặc chồng xếp với nhau tạo thành các bản đồ theo tỉ lệ thích hợp. Bản đồ số là sự thể hiện những thông tin về không gian xung quanh chúng ta ở dạng số trong sự liên kết với các thiết bị đi