Đồ á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ện tử khác như máy tính điện tử, hệ thống định vị toàn cầu GPS. 2.2 Tìm hiểu bản đồ số 2.2.1 Dữ liệu bản đồ số Dữ liệu bản đồ số chỉ là một ví dụ của dữ liệu số và nó được sử dụng trong việc tạo ra các bản đồ. Dữ liệu bản đồ số có thể được sử dụng kết hợp các loại khác của dữ liệu không gian - nó không hoàn toàn là “dữ liệu bản đồ số”. Sau đây ta tìm hiểu một chút về dữ liệu không gian. 2.2.1.1 Khái niệm dữ liệu không gian Dữ liệu không gian là dữ liệu có một vài mẫu không gian hoặc địa lý_ chúng được đặt vào trong không gian hai hay ba chiều. 2.2.1.2 Ví dụ về dữ liệu không gian • Các bản đồ: Có thể là các bản đồ giấy, hay số 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 8 Hình 2-1 Bản đồ số Hà Nội • Các danh sách, các bản dữ liệu, dữ liệu trường… 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ố 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ố STT Tương tự Số 1 Bản đồ giấy Bản đồ số 2 Cố định tỉ lệ Thay đổi được tỉ lệu 3 Cần được chuyển sang định dạng số Đã ở dạng số Không tải và không copy được Có thể tải vể hay copy 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 9 2.3 Các định dạng dữ liệu Bản đồ số thường được lưu trữ dưới một số định dạng dữ liệu, và có các chương trình phần mềm tương ứng xử lí. Định dạng phổ biến nhất của bản đồ số dựa trên kỹ thuật Vector, vì thế các định dạng Vector là phổ biến nhất. Dưới đây chúng ta sẽ tìm hiểu qua về các định dạng này: • Arc Export: là một định dạng chuyển đổi, mã ASCII hay nén vào trong mã nhị phân sử dụng các file truyền giữa các phiên bản khác nhau của ARC/INFO. Nó chỉ làm việc với các sản phẩm ESRI( Environmental Systems Research Institute - Viện nghiên cứu các hệ thống môi trường) • AutoCAD" Drawing Files (DWG): thực chất là một định dạng riêng dành cho phần mềm AutoCAD, các phần mềm dành cho thiết kế, biên tập… • Autodesk’s Data Interchange File (DXF) Format: DXF sử dụng định dạng chuyển đổi vector dữ liệu. Nó có một số lợi thế rất lớn, như nó chứa rất nhiều thông tin mà nhiều chương trình đồ họa đọc được. • MapInfo Map Files: có định dạng nhị phân riêng cho nó, được gọi là Map File. Đặc biệt nó không sử dụng được ngoài hệ thống của MapInfo. • Digital Line Graphs (DLG): một định dạng chuyển đổi bởi USGS(US Geological Survey), nó miêu tả các thông tin của vector trên các bản đồ máy in. • MapInfo" Data Transfer Files (MIF/MID): là một chuyển đổi chuẩn được sử dụng trong MapInfo, và hệ thống bản đồ màn hình. Nó chứa tất cả 3 loại của GIS1: không gian, thuộc tính và hiển thị. Các thuộc tính liên kết là ẩn trong định dạng file. • MicroStation Design Files (DGN): đây là một định dạng đóng, được sử dụng bởi một chương trình CAD do Bentley Systems Inc.’s MicroStation. • Spatial Data Transfer System (SDTS): là một kiểu định dạng mới được phát triển bởi chính phủ Mĩ, nó được tạo ra để xử lí tất cả dữ liệu không gian. SDTS có thể là mã ASCII, nhưng thường là mã nhị phân. • Topologically Integrated Geographic Encoding and Referencing Files (TIGER): là một định dạng được sử dụng bởi US Census Bureau-cục điều tra dân số Mĩ để lưu trữ bản đồ đường được vẽ trong cuộc điều tra năm 1990. Nó chứa tọa độ không gian, các đường thẳng, nhưng không chứa các đa giác. Vector Product Format (VPF): VPF đây là một định dạng nhị phân được sử dụng bởi US Defense Mapping Agency. Nó mang thông tin không gian và thuộc tính nhưng không hiển thị dữ liệu. 1 Geographic Information Systems - Hệ thống thông tin địa lý 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 10 2.4 Dữ liệu vector trong bản đồ số Chúng ta biết rằng bản đồ số được xây dựng dựa trên kỹ thuật vector và theo kỹ thuật này có thể hiểu bản đồ số được tạo từ các dữ liệu vector, đó là: các điểm, các đường và các vùng( hay còn gọi là các lớp của bản đồ số). Hình 2-2 So sánh giữa bản đồ số và bản đồ giấy Hình bên trái là hình vẽ bằng tay,còn hình bên phải là hình sử dụng trong bản đồ số. 2.4.1 Các điểm Mỗi một điểm riêng lẻ được biểu diễn bởi 2 tọa độ x, y. Ví dụ điểm A(2,5),B(3,4). Hình 2-3 Biểu diễn các điểm trong hệ tạo độ Trong lập trình: Point { Double X; Double Y; 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 11 } X,Y là tọa độ của điểm Còn nhiều điểm MultiPoint thì khai báo như sau: MultiPoint { Double[4] Box; Integer NumPoints; Point[NumPoints] Points; } Bounding Box được lưu trữ dưới Xmin, Ymin, Xmax, Ymax NumPoints số các điểm Points Số điểm trong thiết đặt 2.4.2 Các đường Tập các điểm có đặc điểm là gần thuộc đường thẳng, các đường thẳng có thể nối lại với nhau hoặc không Hình 2-4 Biểu diến đường nối các điểm Trong lập trình: PolyLine { Double[4] Box; Integer NumParts; Integer NumPoints; Integer[NumParts] Parts; 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 12 Point[NumPoints] Points; } Box được lưu trong trình tự Xmin, Ymin, Xmax, Ymax NumParts số các phần NumPoints tổng số các điểm Parts chỉ số của điểm đầu tiên trong một phần Points các điểm cho tất cả các phần. 2.4.3 Các miền Là các vùng được giới hạn bởi các đường, như các vùng rừng hay đường biên giới quốc gia. Hình 2-5 Miền giới hạn Trong lập trình các miền được lập trình như dưới đây: Polygon { Double[4] Box; Integer NumParts; Integer NumPoints; Integer[NumParts] Parts; Point[NumPoints] Points; } Box được lưu trong trình tự Xmin, Ymin, Xmax, Ymax NumParts là số vòng trong miền Polygon NumPoints tổng số các điểm Parts chỉ số của điểm đầu tiên trong một phần Points các điểm cho tất cả các phần • Các ví dụ 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 13 Các điểm, đường, vùng như: - Các điểm: Các bốt điện thoại, trạm làm việc… - Các đường: Đường bộ, đường tàu… - Các miền: Đường biên của tòa nhà, đồng ruộng… 2.4.4 Các thuộc tính của vector dữ liệu Hình 2-6 Bản đồ số về đường Hà Nội Có thể hiểu thuộc tính của vector dữ liệu là các những thông tin về một điểm, một đường, hay một vùng nào đó… Ví dụ, một căn nhà thì có số nhà, số điện thoại, ngõ, quận huyện, tỉnh thành mà căn nhà đó ở… 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 14 Các thuộc tính dễ dàng sửa đổi và thêm, xóa... ví dụ chúng ta có thể thay đổi số điện thoại, tên tuyến phố mà nó thuộc (ít xảy ra…) 2.4.5 Kiến trúc tầng dữ liệu vector Kiến trúc tầng là một thành phần quan trọng trong dữ liệu vector. Nó chỉ ra sự “thông minh” của dữ liệu vector. Nó gồm có 3 thành phần: • Liên kết: Các đặc tính trong dữ liệu có thể được liên kết lại với nhau. Trong mô hình dữ liệu vector, thông tin về các liên kết có thể được cất dữ và sử dụng trong việc phân tích của các mạng.( ví dụ: hệ thống mạng lưới đường ống dẫn nước hay dòng sông). • Sự liền kề: Một dãy nhà liền kề dùng chung một vách ngăn có thể là một ví dụ của sự liền kề. Cấu trúc của dữ liệu cho phép “vách ngăn” này được lưu trữ trong cùng dữ liệu, với các thông tin chính là các thông tin thuộc về sự xây dựng ở cả 2 bên “vách ngăn”. • Chính sách ngăn chặn: Các hòn đảo và các hồ... cần được mã hóa một cách đặc biệt để chắc chắn rằng nó được hiển thị và phân tích một cách chính xác. 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 15 2.5 Pixel và độ phân giải 2.5.1 Pixel Hình 2-7 Bản đồ được chia làm các Pixel Mỗi Pixel là đơn vị nhỏ nhất của thông tin trong lưới, hiện thị một thuộc tính duy nhất. Một ảnh được tạo nên từ nhiều Pixel. 2.5.2 Độ phân giải Đây là một đặc tính quan trọng của dữ liệu khung, nó quyết định cái nhỏ nhất mà mắt người có thể nhìn thấy trong ảnh. Hình 2-8 Độ phân giả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 16 Độ phân giải là đơn vị bản ghi nhỏ nhất hay đặc điểm tối thiểu là có thể vẽ và đo đạc được. Như ở hình trên độ phân giải của dữ liệu là 10m điều này có nghĩa là bất kì một đối tượng nào trên mặt đất diện tích dưới 10m2 sẽ không được hiển thị trên bản đồ. 2.6 Ứng dụng của bản đồ số Bản đồ số có ứng dụng rất lớn trong quân sự, du lịch, phục vụ các nhu cầu của con người rất lớn… • Bản đồ số phục vụ đời sống con người Chỉ với chiếc máy có hỗ trợ hệ thống GPS(Global Positioning System) - hệ thống định vị toàn cầu, kết hợp với cái bản đồ số trong thiết bị bạn có thể biết được vị trí nơi bạn cần đến đi theo đường nào là thuận lợi nhất( ví dụ đường đi ngắn nhất), Hay sản phẩm xác định vị trí qua vệ tinh bằng quần lót GPS sản phẩm của hãng Panchira (Nhật) sử dụng hệ thống định vị pantyMap, nhúng vào các sợi vải một cách tinh vi khiến người mặc không thể phát hiện. Những ông chồng hay ghen hoặc các ông bố khó tính có thể mua cho vợ và con gái để bảo vệ “hàng nhà”, những chiếc xe ô tô được lắp đặt hệ thống dẫn đường có gắn hệ thống GPS giúp cho việc đi lại trong thành phố dễ hơn nhiều, và không sợ bị lạc... đương nhiên là bản đồ số được áp dụng tối đa trong trường hợp này. Việt Nam có bản đồ số địa hình tỉ lệ 1:50.000, 573 mảnh bản đồ số. Ngoài ra còn có 98 mảnh bản đồ địa hình biên giới Việt - Lào, Việt Nam - Trung Quốc, và 69 mảnh bản đồ địa hình đáy biển. Các mảnh bản đồ số này bao gồm 7 tập tin cho phép người sử dụng có thể tìm hiểu thông tin về cơ sở toán học, thủy hệ, địa hình, giao thông, dân cư, ranh giới, thực vật và có thể tạo mô hình không gian 3 chiều cho bề mặt địa hình. Bản đồ, lưới toạ độ quốc gia và các trạm GPS là những tài liệu điều tra cơ bản được xây dựng theo chuẩn thống nhất, đảm bảo cung cấp thông tin nhanh, chính xác cho mọi hoạt động quản lý nhà nước, phát triển kinh tế, xã hội, bảo vệ đất nước, nghiên cứu khoa học... • Bản đồ số phục vụ quân đội Trong quân sự bản đồ là cực kì quan trọng, đặc biệt là bản đồ số. Bởi tính chính xác rất cao cũng như khả năng kết hợp với hệ thống GPS… đã là một thứ vũ khí lợi hại trong quân sự. Các trận đánh trở nên hiệu quả hơn, mục tiêu chính xác rất cao… 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 17 CHƯƠNG 3 TÌM HIỂU VỀ MẠNG THÔNG TIN DI ĐỘNG 3.1 Thông tin di động là gì? 3.2 Cấu trúc mạng thông tin di động số Cellular (Tế bào) 3.3 Sơ lược quá trình phát triển của hệ thống di động 3.4 Một số kỹ thuật đa truy nhập 3.4.1 TDMA - Time Domain Multiple Access (Dải băng hẹp) 3.4.1.1 Tổng quan TDMA 3.4.1.2 Loại hệ thống TDMA Bắc Mỹ 3.4.1.3 GSM- Group Special Mobile (Hệ thống truyền thông di động toàn cầu) 3.4.2 CDMA - Code Division Multiple Access (Dải băng rộng hay quang phổ lớn) 3.4.2.1 Giới thiệu CDMA 3.4.2.2 Thủ tục phát/thu tín hiệu 3.4.2.3 Một số đặc tính của CDMA 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 18 3.1 Thông tin di động là gì? Trước hết chúng ta cần biết rằng thuật ngữ “Thông tin di động” đã có từ lâu và được hiểu như là có thể cung cấp một cách lưu động trong quá trình thông tin. Thông tin di động có thể thực hiện được nhiều dịch vụ di động như: truyền thoại, truyền số liệu, Fax, nhắn tin... Trước đây mạng lưới thông tin di động chủ yếu được sử dụng trong lĩnh vực quân sự và ngày nay đã được thương mại hóa và được đưa vào sử dụng rộng rãi. 3.2 Cấu trúc mạng thông tin di động số Cellular (Tế bào) Toàn bộ vùng phục vụ của hệ thống điện thoại di động Cellular được chia thành nhiều vùng phục vụ nhỏ, có dạng một tổ ong hình lục giác. Trong mỗi cell2 có một trạm gốc BTS (Base Transceiver Station). BTS liên lạc vô tuyến với tất cả các máy thuê bao di động MS (Mobile Station) có mặt trong cell. MS có thể di động giữa các cell và nó phải được chuyển giao để làm việc với một BTS liền kề mà nó hiện đang trong vùng phủ song mà không làm gián đoạn cuộc gọi. Hình 3-1 đưa ra một mạng điện thoại di động tổ ong bao gồm các trạm gốc (BTS). Vùng phục vụ của một BTS được gọi là cell và nhiều cell được kết hợp lại thành vùng phục vụ của hệ thống. Hình 3-1 Hệ thống điện thoại di động 2 Vùng phục vụ của một BTS 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 19 Cấu trúc mạng thông tin số Cellular: Hình 3-2 Hệ thống điện thoại di động NSS: Network Switching Subsystem: Hệ thống chuyển mạch MSC: Mobile Service Switching Centre: Trung tâm chuyển mạch các nghiệp vụ di động. HLR: Home Location Register: Bộ ghi định vị thường trú. VLR: Visitor Location Register: Bộ ghi định vị tạm trú. ÃUC: Authentication Centre: Trung tâm nhận thực. EIR: Equipment Indentification Register: Thanh ghi nhận dạng thiết bị. BSS: Base Station System: Hệ thống trạm gốc. BSC: Base Station Controller: Đài điều khiển trạm gốc. BTS: Base Transceiver Station: Trạm thu phát gốc. OSS: Operation & Support Station: Hệ thống con khai thác và bảo dưỡng. NMC: Network Management Centre: Trung tâm quản lý mạng. PSTN: Public Swiched Telephone Network: Mạng điện thoại chuyển mạch công cộng. PLMN: Public Land Mobile Network: Mạng di động mặt đất. ISDN: Integrated Switched Digital Network: Mạng số liên kết đa dịch vụ. MS: Mobile Station: Trạm di động. Hệ thống khái thác và bảo dưỡng OSS mặc dù không thuộc thành phần của mạng thông tin di động nhưng nó liên quan chặt chẽ với mạng đó là trạm di động MS thuộc người sử dụng. Trong mỗi một BSS có một bộ điều khiển trạm gốc BSC điều khiển một nhóm BTS về các chức năng như chuyển giao và điều khiển công suấ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 20 Trong mỗi SS, một trung tâm chuyển mạch của PLMN, gọi tắt là tổng đài di động MSC phục vụ nhiều BSC hình thành cấp quản lý vùng lãnh thổ gọi là vùng phục vụ MSC bao gồm nhiều vùng định vị. Do yêu cầu quản lý về nhiều mặt đối với MS của mạng di động Cellular (tế bào) dẫn đến cơ sở dữ liệu lớn. Bộ ghi định vị thường trú HLR chứa các thông tin về thuê bao như các dịch mà thuê bao lựa chọn và các thông tin số nhận thực. Vị trí hiện thời của MS được cập nhật qua bộ ghi định vị tạm trú VLR cũng được chuyển đến HLR. Trung tâm nhận thực AUC có chức năng cung cấp cho HLR các thông số nhận thực và các khoá mật mã. Mỗi MSC có một VLR. Khi MS di động vào một vùng phục vụ MSC mới thì VLR yêu cầu HLR cung cấp các số liệu về MS này đồng thời VLR cũng thông báo cho HLR biết MS nói trên đang ở vùng phục vụ nào. VLR có đầy đủ các thông tin để thiết lập cuộc gọi theo yêu cầu của người sử dụng. Một MSC đặc biệt (gọi là MSC cổng) đươợ PLMN giao cho chức năng kết nối giữa PLMN với các mạng cố định. 3.3 Sơ lược quá trình phát triển của hệ thống di động Kể từ khi có sự ra đời của điện thoại di động, vị trí của nó trong thị trường đã phát triển một cách chóng mặt bắt đầu từ một thiết bị sơ khai, một vật chuyên biệt, rồi trở thành một vật dụng thực sự cần thiết đối với việc giải trí và kinh doanh. Khoảng từ những năm 80 trở lại đây, kết hợp với sự giảm đáng kể chi phí cho hoạt động và sự phát triển của những ứng dụng và dịch vụ mới lạ, sự tiến triển trong công nghệ di động đã khẳng định một thị trường lớn mạnh. Vào khoảng giữa năm 2000, ở châu Âu có trên 220 triệu thuê bao di động, và trên toàn cầu, con số này là 580 triệu. Ở Vương Quốc Anh, cứ 2 người thì có một người sở hữu máy điện thoại di động; trong khi đó ở Phần Lan, số lượng máy điện thoại di động tính theo đầu người đã vượt quá số hộ sử dụng điện thoại cố định. Hình 3-3 Sự phát triển của hệ thống 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 21 Sự tiến triển của công cuộc truyền thông di động có thể phân ra làm hai thế hệ phát triển. Hiện tại, chúng ta đang bước vào thế hệ thứ ba (3G) của những hệ thống di động. - Thế hệ 1G Có thể nói rằng những hệ thống của thế hệ thứ nhất (1G) là mũi tên chỉ đường cho các thế hệ sau, và nhìn chung, những hệ thống này được xếp vào loại những mạng quốc gia dựa trên nền tảng công nghệ tương tự. Vào những năm 1980, những mạng kiểu đó đã được chuyển biến thành loại hình dịch vụ. Những mạng đó được thiết kế để cung cấp cho các thuê bao di động những truyền thông chuyển tải giọng nói. 1G là công nghệ điện thoại cầm tay ra đời sớm nhất với tín hiệu truyền là analog. Một máy điện thoại sẽ sử dụng hai kênh trong suốt cuộc gọi một cho tín hiệu giọng nói và một cho tín hiệu điều khiển. - Thế hệ 2G Những hệ thống của thế hệ thứ hai (2G) được xếp vào loại công nghệ kỹ thuật số. Những hệ thống như thế này được sự giúp đỡ ủng hộ của những Công ước Quốc tế chung, tạo đà cho khả năng vận hành một chiếc máy điện thoại di động vượt qua khỏi biên giới của một quốc gia. Bên cạnh lĩnh vực viễn thông truyền giọng nói bằng kỹ thuật số, với sự góp mặt của những hệ thống 2G, một loạt các dịch vụ số mới với tốc độ truyền dữ liệu thấp đã trở nên phong phú và đa dạng, bao gồm “mobile fax” (chuyển fax di động), gửi thư giọng nói, và dịch vụ gửi tin nhanh (short message service – SMS). Cũng tại khoảng thời gian trong giai đoạn phát triển này, những thể loại hệ thống mới bắt đầu nổi dậy phục vụ cho những thị hiếu riêng biệt; không những đó là những mạng di động mà còn có những giải pháp cho vô tuyến điện (cordless), radio di động cho công cộng, vệ tinh, và mạng vô tuyến cục bộ (W-LAN). Những hệ thống của thế hệ thứ hai (2G) đồng nghĩa với sự toàn cầu hoá các hệ thống di động, và trên quan điểm đó, tầm quan trọng của chuẩn hoá là rất rõ. Ví dụ, GMS, chuẩn hoá tại châu Âu bởi Tổ chức Tiêu chuẩn Viễn thông Châu Âu (ETSI), hiện đang được coi là một tiêu chuẩn toàn cầu dưới sự thừa nhận của hầu hết các quốc gia trên thế giới. Trong việc nhận ra tầm quan trọng của Internet và đồng thời là một bước tiến tiếp tới ngưỡng cửa của công nghệ thế hệ thứ ba (3G), giai đoạn phát triển cuối của loại mạng 2G đã cho ra đời những dịch vụ đa phương tiện di động. Trong một vài năm tới, người ta hi vọng rằng những người sử dụng hệ thống di động sẽ có xu hướng truy cập vào các dịch vụ đa phương tiện băng rộng, ví như những gì đã có ở 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 22 các mạng cố định. Yêu cầu về những dịch vụ có băng thông rộng được đưa ra do sự cần thiết phải cung ứng những dịch vụ và ứng dụng tương đương với những gì đã có cho máy tính cá nhân. Sự trưởng thành đầy kinh ngạc của Internet, với hơn 500 triệu người sử dụng theo dự đoán đến trước năm 2005, mô tả hoàn hảo nhu cầu truy nhập vào các ứng dụng và dịch vụ băng rộng. Những loại dịch vụ này nằm ngoài khả năng của các hệ thống thuộc thế hệ 2G đương thời, là những dịch vụ mà chỉ cung cấp các dịch vụ thoại có tốc độ dữ liệu thấp. Sự hội tụ của những công nghệ dựa trên các giao thức Internet và di động ngày nay là động lực chính cho sự phát triển của các hệ thống thuộc 3G. - Thế hệ 3G Những hệ thống truyền thông di động 3G sẽ có khả năng phân phối các ứng dụng và dịch vụ với tốc độ dữ liệu lên tới và có thể vượt quá 2Mb/s Việc tiêu chuẩn hoá các hệ thống 3G thực hiên bởi Liên đoàn Viễn thông Quốc tế. Trên phương diện toàn cầu, người ta sẽ nhìn nhận ra đây là hệ thống Viễn thông Di động Quốc tế 2000 (IMT-200), và vấn đề này sẽ bao hàm những hệ thống trong hộ gia đình mà cung ứng các dịch vụ tế bào, vô tuyến điện, W-LAN, và vệ tinh. Ở châu Âu, hệ thống 3G này sẽ được coi là Hệ thống Viễn thông Di động Toàn cầu (UMTS). Cho dù thoại vẫn có thể là ứng dụng chiếm ưu thế trong mấy năm đầu của mạng hệ 3G, những cũng sẽ có khả năng mạng vận hành những hệ thống với những ứng dụng đa phương tiện di động, chẳng hạn như điện thoại truyền hình ảnh, truy nhập file bằng ftp, tra cứu trang Web… Khi công nghệ 3G mở ra, những ứng dụng mới với băng thông rộng sẽ thâm nhập thị trường theo một khuynh hướng mà việc chuyển phát dữ liệu sẽ cho ra thông lượng lớn nhất. -Thế hệ 4G??? Công cuộc nghiên cứu ngày này đang nhằm vào những đòi hỏi phải có sự ra đời của mạng di động thế hệ thứ tư (4G). Tốc độ dữ liệu di động trên 2Mb/s, và có khả năng lên tới 155Mb/s trong một số môi trường nhất định, sẽ tiếp tục mở rộng các dịch vụ và ứng dụng trong khả năng phân phối. Sự cải thiện về chất lượng dịch vụ (QoS), hiệu dụng băng thông, và sự tiến tới một môi trường hướng gói tin và dựa hoàn toàn vào giao thức mạng (IP) có thể được xem xét dựa trên các chuẩn nổi trội của giao thức mạng di động (Mobile IP), dưới sự triển khai của Lực lượng Công tác Kỹ thuật Internet (IETF). Nếu ta đứng về phương diện các kỹ thuật áp dụng trong hệ thống thông tin di động thì quá trình phát triển của hệ thống thông tin di động có thể được xem xét qua các kỹ thuật chủ yếu sau: 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 23 3.4 Một số kỹ thuật đa truy nhập 3.4.1 TDMA - Time Domain Multiple Access (Dải băng hẹp) 3.4.1.1 Tổng quan TDMA Trong thông tin TDMA thì nhiều người sử dụng một sóng mang và trục thời gian được chia thành nhiều khoảng thời gian nhỏ để giành cho nhiều người sử dụng sao cho không có sự chồng chéo. TDMA được chia thành TDMA băng rộng và TDMA băng hẹp. Mỹ và Nhật sử dụng TDMA băng hẹp còn Châu Âu sử dụng TDMA băng rộng nhưng cả 2 hệ thống này đều có thể được coi như là sự tổ hợp của FDMA và TDMA vì người sử dụng thực tế dùng các kênh được ấn định cả về tần số và các khe thời gian trong băng tần. Băng tần Người sử dụng 1 Người sử dụng 2 Người sử dụng 3 Khe thời gian 1 Khe thời gian 2 Khe thời gian 3 Khe thời gian 4 Khe thời gian 5 Khe thời gian 6 Hình 3-4 PhổTDMA 3.4.1.2 Loại hệ thống TDMA Bắc Mỹ Loại hệ thống TDMA Bắc Mỹ sử dụng băng tần (869 - 894) MHz và (824 - 849) MHz giống như hệ thống AMPS. Khoảng cách sóng mang là 30 KHz và mỗi kênh tần số được chia thành 6 khe thời gian. Hệ thống AMPS hiện tại có khả năng chuyển vùng với cấu trúc khung và cấu trúc khe thời gian được chỉ ra trên hình 3-7 và hình 3-8. Hệ thống này mã hoá tín hiệu thoại theo mã VSELP (dự đoán tổng vectơ tuyến tính tồn tại), điều chế /4 DQPSK và hoạt động theo kiểu cặp đôi. 6 thuê bao với một nửa tốc độ trên một kênh. 30 KHz 1 khung = 972 ký hiệu (1944 bit) = 40 ms 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 24 Người sử dụng 1 Khe thời gian 0 Người sử dụng 2 Khe thời gian 1 Người sử dụng 3 Khe thời gian 2 Người sử dụng 1 Khe thời gian 3 Người sử dụng 2 Khe thời gian 4 Người sử dụng 3 Khe thời gian 5 Người sử dụng 1 Khe thời gian 0 Người sử dụng 2 Khe thời gian 1 Người sử dụng 3 Khe thời gian 2 Người sử dụng 1 Khe thời gian 3 Người sử dụng 2 Khe thời gian 4 Người sử dụng 3 Khe thời gian 5 Hình 3-5 Cấu trúc khung a) Dạng khe thời gian từ máy di động đến trạm gốc b) Dạng khe thời gian từ trạm gốc tới máy di động Với : 324 bit = 162 ký hiệu = 40/6 ms = 6,67 ms G - thời gian guard R - thời gian ramp SACCH - kênh điều khiển liên kết chậm CDVCC - mã xác minh màu số đã mã 6 G 6 G 16 DATA 28 TRAINING 122 DATA 12 SACCH 12 CDVCC 122 DATA Hình 3-6 Dạng khe thời gian từ máy di động đến trạm gốc 28 TRAINING 12 SACCH 130 DATA 12 CDVCC 130 DATA 12 REVERVED 000.00 3 thuê bao số với tốc độ cao nhất trên một kênh 1 khung = 972 ký hiệu (1944 bit) = 40 ms 324 bit 324 bit 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 25 Hình 3-7 Dạng khe thời gian từ trạm gốc tới máy di động với 324 bit = 162 ký hiệu = 40/6 ms = 6,67 ms G - thời gian guard R - thời gian ramp SACCH – kênh điều khiển liên kết chậm CDVCC – mã xác minh mẫu số đã mã 3.4.1.3 GSM - Group Special Mobile (Hệ thống truyền thông di động toàn cầu) Theo một đề nghị của hãng Nordic Telecom (Viễn thông Bắc Âu) và của Netherlands PTT( một công ty về truyền thông của Hà Lan), nhóm nghiên cứu Group Special Mobil (GSM) đã được hình thành vào năm 1982 bởi CEPT(European Conference of Posts and Telecommunications Administrations – Hội nghị châu Âu của các cơ quan quản lý bưu điện). Mục tiêu của nhóm nghiên cứu này là tìm ra một hệ thống mobile trên đất liền công cộng xuyên châu Âu. Cho đến giữa những năm 1980, ngành mobile đã tập trung sự chú ý vào nhu cầu thiết lập thêm các dịch vụ kiểu kỹ thuật số thế hệ 2G có hiệu quả hơn về mặt quang phổ, cung cấp một số các ưu điểm quan trọng bao gồm sức kháng nhiễu lớn hơn, an ninh gia tăng, và khả năng cung cấp một loạt rộng rãi các dịch vụ. Không giống như sự trưởng thành của AMPS Bắc Mỹ, hệ thống mà sẽ được bàn đến ngắn gọn sau, việc thiết lập GSM kéo theo một quá độ cải cách tới vấn đề thiết kế và thiết lập. Vào năm 1987, 13 nhà khai thác và quản lý đã ký kết hiệp định giác thư thoả thuận sơ bộ (MoU - Memorandum of Understanding) của GSM và tên gọi ban đầu theo tiếng Pháp đã được thay thành tên mới mô tả đầy đủ chức năng hơn; đó là Hệ thống Toàn cầu Truyền thông Di động (GSM), mặc dù vẫn là những chữ cái viết tắt như thế. Cho đến năm 1999, 296 nhà vận hành khai thác và quản lý từ 110 quốc gia đã ký kết GSM MoU. Đặc biệt, vào năm 1987, theo sự đánh giá của một số những nền công nghệ dự tuyển thông qua thí nghiệm và thực nghiệm, hiệp ước đã được để ý tới về việc sử dụng một bộ mã dự đoán đặc tuyến kích xung chính tắc (gọi là RPE - LPC) đối với việc mã hoá âm thoại và TDMA đã được chọn làm phương thức đa truy nhập. Vào năm 1989, trách nhiệm đối với tiêu chuẩn kỹ thuật GSM đã được chuyển nhượng cho ETSI(European Telecommunications Standards Institute- Viện chuẩn viễn thô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 26 châu Âu), và một năm sau đó, các tiêu chuẩn kỹ thuật GSM giai đoạn 1 (Phase 1) được xuất bản. Hai năm sau đó, vào giữa năm 1991, các dịch vụ GSM chào hàng bắt đầu nẩy nở ở châu Âu. Ngoài các dịch vụ thoại ra, SMS đã được sinh ra làm một phần của chuẩn hoá GSM giai đoạn 1. Việc này tạo ra những tiện lợi cho việc gửi và nhận các bản tin chữ viết tới và từ các máy điện thoại di động. Những bản tin có thể lên tới 160 ký tự độ dài và có thể dùng để thông báo người sử dụng biết chẳng hạn như về một bản tin e-mail đang đến. Đây là một dịch vụ lưu và chuyển với tất cả các tin nhắn đi thông qua một trung tâm SMS. SMS đã chứng tỏ là một dịch vụ rất phổ cập ở châu Âu, với dung lượng truyền khoảng hơn một tỉ tin nhắn trong mỗi tháng, điển hình như tháng 4 năm 1999. Vào năm 1997, các chỉ tiêu kỹ thuật giai đoạn 2 (Phase 2) đã xuất hiện trực tuyến, cho phép việc truyền Fax và dữ liệu được thực hiện dễ dàng. Vào ngay cuối năm 1998, ETSI đã hoàn chỉnh việc chuẩn hoá của mình về các dịch vụ giai đoạn 2 cộng với các dịch vụ như dịch vụ số liệu chuyển mạch kênh tốc độ cao (HSCSD - High Speed Circuit Switched Data) và dịch vụ truyền sóng radio gói chung (GPRS - General Packet Radio Service). Hai dịch vụ mới này được nhằm rất nhiều vào việc khai thác các thị trường tiềm ẩn nằm trong lĩnh vực hoạt động dữ liệu mobile, đã nhận thấy sự ảnh hưởng của Internet vào các công nghệ mobile. HSCSD và GPRS sẽ được bàn đến một cách ngắn gọn về sau. Trách nhiệm duy trì và phát triển trong tương lai của các chuẩn GSM hiên đang dưới sự điều khiển của dự án đối tác thế hệ 3G (3GPP). GSM dụng hệ thống TDMA với cấu trúc khe thời gian sao cho tạo nên được sự linh hoạt trong truyền thoại, số liệu và thông tin điều khiển. Hệ thống GSM sử dụng băng tần (890 - 915) MHz để truyền dẫn tín hiệu từ máy di động đến BS và băng tần (935 - 960) MHz để truyền dẫn tín hiệu từ BS đến máy di động. 3.4.2 CDMA - Code Division Multiple Access (Dải băng rộng hay quang phổ lớn) 3.4.2.1 Giới thiệu CDMA Lý thuyết về CDMA đã được xây dựng từ những năm 1950 và được áp dụng trong thông tin quân sự từ những năm 1960. Cùng với sự phát triển của công nghệ bán dẫn và lý thuyết thông tin trong những năm 1980, CDMA đã được thương mại hoá từ phương pháp thu GPS và Ommi - TRACS, phương pháp này cũng đã được đề xuất trong hệ thống tổ ong của Qualcomm - Mỹ vào năm 1990. 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 27 Trong thông tin CDMA thì nhiều người sử dụng chung thời gian và tần số, mã PN (tạp âm giả ngẫu nhiên) với sự tương quan chéo thấp được ấn định cho mỗi người sử dụng. Người sử dụng truyền tín hiệu nhờ trải phổ tín hiệu truyền có sử dụng mã PN đã ấn định. Đầu thu tạo ra một dãy giả ngẫu nhiên như ở đầu phát và khôi phục lại tín hiệu dự định nhờ việc trải phổ ngược các tín hiệu đồng bộ thu được. 3.4.2.2 Thủ tục phát/thu tín hiệu (1) Tín hiệu số liệu thoại (9,6 Kb/s) phía phát được mã hoá, lặp, chèn và được nhân với sóng mang f o và mã PN ở tốc độ 1,2288 Mb/s (9,6 Kb/s x 128). (2) Tín hiệu đã được điều chế đi qua một bộ lọc băng thông có độ rộng băng 1,25 MHZ sau đó phát xạ qua anten. (3) ở đầu thu, sóng mang và mã PN của tín hiệu thu được từ anten được đưa đến bộ tương quan qua bộ lọc băng thông độ rộng băng 1,25 MHz và số liệu thoại mong muốn được tách ra để tái tạo lại số liệu thoại nhờ sử dụng bộ tách chèn và giải mã. 3.4.2.3 Một số đặc tính của CDMA (1) Máy di động có chuyển vùng mềm Như đã miêu tả trong hình 3-11, cả BS ban đầu và BS mới cùng tham gia vào việc chuyển giao cuộc gọi đối với chuyển vùng mềm. 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 28 Hình 3-8 Đường kết nối trong khi chuyển vùng mềm Việc chuyển giao cuộc gọi thông qua trình tự: BS ban đầu, cả hai BS, BS mới. Lược đồ đó làm tối thiểu hoá sự gián đoạn cuộc gọi và làm cho người sử dụng không nhận ra trạng thái chuyển vùng mềm. Do đó, trong khi hệ thống analog và hệ thống TDMA số chấp nhận hình thức chuyển mạch "cắt - trước khi - nối" thì chuyển vùng mềm của hệ thống CDMA chấp nhận hình thức chuyển mạch "nối - trước khi - cắt". Sau khi cuộc gọi được thiết lập thì máy di động tiếp tục tìm tín hiệu cuả BS bên cạnh để so sánh cường độ tín hiệu của ô bên cạnh với cường độ tín hiệu cuả ô đang sử dụng. Nếu cường độ tín hiệu đạt đến một mức nhất định nào đó có nghĩa là máy di động đã di chuyển sang một vùng phục vụ cuả một BS mới và trạng thái chuyển vùng mềm có thể bắt đầu. Máy di động chuyển một bản tin điều khiển tới MSC để thông báo về cường độ tín hiệu và số hiệu cuả BS mới. Sau đó, MSC thiết lập một đường nối mới giữa máy di động và BS mới và bắt đầu quá trình chuyển vùng mềm trong khi vẫn giữ đường kết nối ban đầu. Trong trường hợp máy di động đang trong một vùng chuyển đổi giữa hai BS thì cuộc gọi được thực hiện bởi cả hai BS sao cho chuyển vùng mềm có thể thực hiện được mà không có hiện tượng ping - pong giữa chúng. BS ban đầu cắt đường kết nối cuộc gọi khi việc đấu nối cuộc gọi với BS mới đã thực hiện thành cô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 29 (2) Tách tín hiệu thoại Trong thông tin 2 chiều song công tổng quát thì tỷ số chiếm dụng tải của tín hiệu thoại không lớn hơn khoảng 35%. Trong trường hợp không có tín hiệu thoại trong hệ thống TDMA và FDMA3 thì khó áp dụng yếu tố tích cực thoại vì trễ thời gian định vị lại kênh tiếp theo là quá dài. Nhưng do tốc độ truyền dẫn số liệu giảm nếu không có tín hiệu thoại trong hệ thống CDMA nên giao thoa ở người sử dụng khác giảm một cách đáng kể. Dung lượng hệ thống CDMA tăng khoảng 2 lần và suy giảm truyền dẫn trung bình của máy di động giảm khoảng 1/2 vì dung lượng được xác định theo mức giao thoa ở những người sử dụng khác. (3) Tái sử dụng tần số và vùng phủ sóng Tất cả các BS đều tái sử dụng kênh băng rộng trong hệ thống CDMA. Giao thoa tổng ở tín hiệu máy di động thu được từ BS và giao thoa tạo ra trong các máy di động của cùng một BS và giao thoa tạo ra trong các máy di động của BS bên cạnh. Nói cách khác, tín hiệu của mỗi một máy di động giao thoa với tín hiệu của tất cả các máy di động khác. Giao thoa tổng từ tất cả các máy di động bên cạnh bằng một nửa của giao thoa tổng từ các máy di động khác trong cùng một BS. Hiệu quả tái sử dụng tần số của các BS không định hướng là khoảng 65%, đó là giao thoa tổng từ các máy di động khác trong cùng một BS với giao thoa từ tất cả các BS. Hình 3-9 Giao thoa từ BS bên cạnh Hình 3-12 trình bày giao thoa từ các BS bên cạnh theo %. Giao thoa từ mỗi BS trong vòng biên thứ nhất tương ứng với 6% của giao thoa tổng. 3 Frequency Division Multiple Access (Đa truy cập phân theo tần số) 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 30 Do đó, giao thoa từ vòng biên thứ nhất là gấp 6 lần 6%, tức là 36%, và giao thoa tổng do vòng thứ 2 và vòng ngoài là nhỏ hơn 4%. Trong trường hợp anten của BS là định hướng (tức là búp sóng anten 120 o) thì giao thoa trung bình giảm xuống 1/3 vì mỗi anten kiểm soát nhỏ hơn 1/3 số lượng máy di động trong BS. Do đó, dung lượng cung cấp bởi toàn bộ hệ thống tăng lên xấp xỉ 3 lần. (4) Trải phổ Trong kỹ thuật CDMA, tín hiệu mang thông tin (Ví dụ như tiếng nói) được biến đổi thành tín hiệu số, sau đó được trộn với một mã giống như mã ngẫu nhiên. Tín hiệu tổng cộng, tức tiếng nói cộng với mã giải ngẫu nhiên, khi đó được phát trong một dải tần rộng nhờ một kỹ thuật gọi là trải phổ. Thông tin trải phổ là một hệ thống thông tin để truyền các tín hiệu nhờ trải phổ của các tín hiệu số liệu thông tin có sử dụng mã với độ rộng băng rộng hơn độ rộng băng của các tín hiệu số liệu thông tin. Các mã sử dụng là độc lập với tín hiệu số liệu thông tin. Trải phổ sóng mang phân loại theo tốc độ truyền lan số liệu, bao gồm: DS (trải trực tiếp), dịch tần, dịch thời gian và loại hybrid. 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 31 CHƯƠNG 4 TÌM HIỂU HỆ THỐNG GPS 4.1 Sự ra đời của hệ thống GPS 4.2 Nghiên cứu các thành phần hệ thống GPS 4.2.1 Nghiên cứu việc thiết kế hệ thống GPS 4.2.2 Các thành phần hệ thống GPS 4.2.2.1 Phần vũ trụ 4.2.2.2 Phần điều khiển 4.2.2.3 Phần sử dụng 4.3 Hoạt động của hệ thống GPS 4.3.1 Sóng của vệ tinh GPS 4.3.2 Vị trí trên mặt đất được xác định như thế nào qua hệ thống GPS? 4.4 Ứng dụng của hệ thống GPS 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 32 4.1 Sự ra đời của hệ thống GPS GPS là hệ thống bao gồm các vệ tinh bay trên quỹ đạo, thu thập thông tin toàn cầu và được xử lý bởi các trạm điều khiển trên mặt đất. Ngày nay, khó hình dung rằng có một máy bay, một con tàu hay phương tiện thám hiểm trên bộ nào lại không lắp đặt thiết bị nhận tín hiệu từ vệ tinh. Năm 1978, nhằm mục đích thu thập các thông tin về tọa độ (vĩ độ và kinh độ), độ cao và tốc độ của các cuộc hành quân, hướng dẫn cho pháo binh và các hạm đội, Bộ Quốc phòng Mỹ đã phóng lên quỹ đạo trái đất 24 vệ tinh. Những vệ tinh trị giá nhiều tỷ USD này bay phía trên trái đất ở độ cao 19.200 km, với tốc độ chừng 11.200 km/h, có nhiệm vụ truyền đi các tín hiệu radio tần số thấp tới các thiết bị thu nhận. Từ những năm đầu thập kỷ 80, các nhà sản xuất lớn chú ý nhiều hơn đến đối tượng sử dụng tư nhân. Trên các xe hơi hạng sang, những thiết bị trợ giúp cá nhân kỹ thuật số PDA (Personal Digital Assistant) như Ipaq của hãng Compaq, được coi là một trang bị tiêu chuẩn, thể hiện giá trị của chủ sở hữu. Số lượng các vệ tinh ngày càng tăng lên, do được phóng lên thêm. Tính đến thời điểm hiện tại thì số lượng vệ tinh của hệ thống GPS là 28 vệ tinh. Các đặc điểm mà GPS thu hút nhiều người quan tâm và sử dụng như: - Mức độ chính xác của vị trị đưa ra là tương đối cao, từ hàng 10m đến hàng mm… - Có khả năng xác định được vận tốc vật trên mặt đất vào thời điểm chính. - Tín hiệu phát ra đến được người dùng tại khắp mọi nơi trên thế giới: trên không, trên mặt đất, hay trên biển… - Là hệ thống định vị mà người dùng không phải trả tiền sử dụng. Ngoài ra các yêu cầu về phần cứng có giá cũng không phải quá cao – nếu không muốn nói là tương đối thấp. - Nó hoạt động trong mọi thời điểm, và trong mọi thời tiết. - Thông tin vị trí mà GPS cung cấp là được miêu tả trong không gian 3 chiều, các thông tin vị trí cung cấp như chiều dọc, chiều ngang, độ cao(hay còn gọi là kinh độ, vĩ độ, cao độ) 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 33 4.2 Nghiên cứu các thành phần hệ thống GPS 4.2.1 Nghiên cứu việc thiết kế hệ thống GPS Thực sự việc nghiên cứu phát triển hệ thống GPS của Bộ Quốc Phòng Mỹ được tiến hành trong năm 1973, mục đích chính lúc đó mà đến cả ngày nay là xây dựng một hệ thống định vị hoạt động tốt trong tất cả các điều kiện thời tiết, khí hậu, hoạt động 24 giờ trong ngày và phần quan trọng của hệ thống là cung cấp các thông tin về vị trí các điểm yêu cầu của lực lượng vũ trang Mỹ và các nước đồng minh của Mỹ. Vì thế hệ thống GPS được thiết kế để thay thế các hệ thống điều hướng đang được sử dụng và điểm mạnh của GPS so với các hệ thống có chức năng tương tự khác là ở độ tin cậy và tính bền vững. Hệ thống định vị GPS gặp phải một số khó khăn trong việc thiết kế như: - Khả năng đáp ứng được tất cả các lớp nền: như phù hợp bất kì một máy móc nào, tàu thủy, đất liền, và ở không trung. - Có thể sử dụng cho một số lượng lớn các loại máy móc, động cơ khác nhau. - Khả năng xác định rõ vị trí, vận tốc và thời điểm hiện tại, và chúng phải phù hợp với nhau, tức là vị trí và vận tốc phải ở cùng một thời điểm, không để xảy ra tình trạng vận tốc ở thời điểm này lại được cho là vận tốc ở thời điểm khác gây ra nhầm lẫn. - Độ chính xác cao nhất của hệ thống chắc chắn bị hạn chế với một lớp người nào đấy. - Có khả năng giải quyết các lỗi, sự cố xảy ra trong việc tính toán, vận hành hệ thống – có thể do chủ quan hay khách quan đem lại. - Hệ thống hoàn toàn bị động trong việc truyên dữ liệu từ người dùng đến vệ tinh, mà chỉ có chiều ngược lại. - Có thể cung cấp dịch vụ đến số lượng người dùng không giới hạn. Việc thiết kế xây dựng hệ thống GPS nói chung là dựa trên các tiêu chí sau: - Một hệ thống dải một chiều, trong đó các vệ tinh truyền tín hiệu đi mà không biết ai sẽ là người nhận tín hiệu. - Sử dụng các kỹ thuật và công nghệ hiện đại như đồng hồ nguyên tử, truyền sóng radio ngắn. - Các tín hiệu vệ tinh sẽ không bị ảnh hưởng của điều kiện thời tiết. - Hệ thống GPS gồm các vệ tinh thay nhau làm việc nhưng phải luôn đảm bảo là vào bất kì thời điểm nào cũng có đủ số vệ tinh cần thiết cùng hoạt động, để từ đó mới đảm bảo tính chính xác và liên tục của hệ thố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 34 - Sự thiếu chính xác về vị trí là trong khoảng chấp nhận được. Đề cập đến tính chính xác của GPS, cũng phải nói thêm là ngày nay hệ thống GPS ngày càng hoàn thiện hơn, đặc biệt là về độ chính xác ngày càng cao đến hàng milimet. Chính vì độ chính xác cao như vậy nên GPS ngày càng được áp dụng vào nhiều ứng dụng của con người, và thật khó có thể hình dung được là cuộc sống của chúng ta lại thiếu GPS. Các công nghệ, kỹ thuật được áp dụng trong việc xây dụng hệ thống GPS như: - Độ tin cậy của hệ thống không gian: Năm 1973, chương trình không gian của Mỹ đã cho thấy độ tin tưởng của phần cứng không gian. Trong thực tế các hệ thống truyền tín hiệu là rất quan trọng. Các vệ tinh truyền tín hiệu ban đầu được thiết kế hoạt động được 2 đến 3 năm trên quĩ đạo, nhưng có một số vệ tinh đã vượt ra cả dự đoán ban đầu, chúng có thể chạy trên 25 năm trên quĩ đạo. - Công nghệ đồng hồ nguyên tử: Với việc ra đời và phát triển của đồng hồ nguyên tử, thì một kỉ nguyên mới trong việc đảm bảo tính chính xác của thời gian đã mở ra... Tuy nhiên, trước khi các chương trình của GPS được đưa vào triển khai thì sự chính xác của các đồng hồ nguyên tử đã được kiểm tra trên vũ trụ. Các đồng hồ nguyên tử hiện tại cũng cực kỳ chính xác. Chúng chậm chưa tới một giây sau khi chạy hơn 15 triệu năm. Chúng đếm thời gian dựa trên cách thức các nguyên tử xeri (caesium) nhảy lên xuống giữa các mức năng lượng khác nhau. Những bước nhảy hay "những tiếng tích tắc" rất đều này xảy ra ở những tần số sóng cực ngắn và được sử dụng để định giây - chính xác là 9.192.631.770 tiếng tích tắc/giây. Tuy nhiên, vào năm ngoái, các nhà nghiên cứu thuộc Viện tiêu chuẩn và công nghệ quốc gia (Nist) ở Washington DC Mỹ tiến thêm một bước bằng việc chế tạo một loại đồng hồ dựa trên tần số quang học của một ion thuỷ ngân đơn nhất được làm mát (1 nguyên tử thuỷ ngân có 1 electron bị loại bỏ). Trong thiết bị này, họ cần một thiết bị laser siêu nhanh để đếm những bước nhảy nhanh hơn nhiều của ion thuỷ ngân khi nó di chuyển giữa các mức năng lượng - tạo ra khoảng 1.065.000.0004 tiếng tích tắc/giây. 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 35 Scott Diddams, một nhà nghiên cứu tại Nist, phát biểu tại Hội nghị: ''Chúng tôi biết loại đồng hồ thế hệ mới rất ổn định. Vì vậy, nghiên cứu của chúng tôi hiện tập trung vào việc kiểm tra nó hoạt động chính xác như thế nào. Các thí nghiệm cho thấy chúng có thể chỉ chậm một khoảng giây trong 100 triệu năm". - Máy tạo dao động tinh thể thạch anh: Nhằm mục tiêu giảm giá trị của các thiết bị thì máy tạo dao động tinh thể thạch anh đã được đưa ra. Máy tạo dao động này hơn là việc sử dụng đồng hồ nguyên tử trong các vệ tinh GPS. Hơn nữa giá của chúng lại thấp hơn và có sự ổn định rất cao trong thời gian ngắn. - Theo rõi tính chính xác của các vệ tinh và xác định rõ quĩ đạo của chúng: Trong quá trình hoạt động của mình, các vệ tinh không thể tránh khỏi các sai xót, bay lệch quĩ đạo của mình( dù là rất nhỏ)… chính vì thế chúng luôn phải được quản lý, theo dõi... khi thấy sai xót là phải sửa lại ngay - điều này được thực hiện bởi trạm điều hành ở dưới mặt đất. - Công nghệ mạch tích hợp cao: Một mức độ về sự tinh vi của công nghệ trong việc chế tạo các chip bán dẫn, có khả năng tương đương hơn 100. 000 - và có thể đến 1 triệu - transistor được đặt trong một chip. Nhờ vào công nghệ này mà giá sẽ thấp và kích thước của các thiết người dùng nhỏ hơn... sự thành công các chương trình GPS phụ thuộc rất lớn vào mạch tích hợp cao, và sức mạnh của hệ thống GPS cũng được xây dụng từ chúng. 4.2.2 Các thành phần hệ thống GPS Hệ thống GPS gồm có 3 thành phần chính: - Phần vũ trụ Gồm các vệ tinh và sự truyền phát tín hiệu. - Phần điều khiển Là các trạm trên mặt đất có nhiệm vụ nhận tín hiệu từ các vệ tinh, từ đố kiểm tra các vệ tinh, tính toán quĩ đạo chuyển động, và đưa ra các điều chỉnh cần thiết để các vệ tinh luôn hoạt động chính xác. - Phần người dùng Gồm người dùng và thiết bị thu GPS 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 36 Hình 4-1 Các thành phần của hệ thống GPS Sau đây chúng ta sẽ lần lượt tìm hiểu các thành phần này: 4.2.2.1 Phần vũ trụ Hình 4-2 Các vệ tinh GPS bay trên quĩ đạo Phần vũ trụ bao gồm các vệ tinh GPS bay trên quĩ đạo. Như ta đã biết ở phần trên thì vào năm 1978, Mỹ đã phóng các vệ tinh GPS lên trên quĩ đạo cách trái đất khoảng 19.200 km, với tốc độ chừng 11.200 km/h, có nhiệm vụ truyền đi các tín hiệu radio tần số thấp tới các thiết bị thu nhận. Trong số 28 vệ tinh của Bộ quốc phòng Mỹ nói trên, chỉ có 24 thực sự hoạt động, 3 vệ tinh còn lại là hệ thống hỗ trợ, và 1 vệ tinh mới phóng thêm vào ngày 26 tháng 9 năm 2005. Tín hiệu radio được truyền đi thường không đủ mạnh để thâm nhập vào các 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 37 tòa nhà kiên cố, các hầm ngầm và hay tới các địa điểm dưới nước. Ngoài ra nó còn đòi hỏi tối thiểu 4 vệ tinh để đưa ra được thông tin chính xác về vị trí (bao gồm cả độ cao) và tốc độ của một vật. Vì hoạt động trên quỹ đạo, các vệ tinh đảm bảo cung cấp vị trí tại bất kỳ điểm nào trên trái đất. Phần Vũ trụ gồm các vệ tinh trên, chúng hoạt động bằng năng lượng mặt trời, bay trên quỹ đạo. Quãng thời gian tồn tại của chúng vào khoảng 10 năm và chi phí cho mỗi lần thay thế lên đến hàng tỷ USD. Theo tin tức của báo Vietnamnet thì Mỹ vừa phóng vệ tinh định vị hiện đại nhất, thuộc một nhóm vệ tinh định vị toàn cầu mới (GPS) nhằm giúp người sử dụng thương mại và quân đội Mỹ xác định được vị trí và mục tiêu chính xác hơn. Hình 4-3 Vệ tinh GPS thế hệ mới Trị giá 75 triệu đôla, vệ tinh được phóng bằng tên lửa Boeing Delta 2 vào ngày 26/9/2005. Trong thời gian tiếp theo, nó sẽ triển khai các tấm pin mặt trời, anten và khai hoả một tên lửa nhỏ trên boong để đạt tới quỹ đạo cuối cùng, chừng 18.00km bên trên Trái đất. Vệ tinh này nhập vào một mạng lưới gồm 28 vệ tinh GPS hiện nay. Hệ thống 28 vệ tinh GPS giúp người sử dụng xác định vị trí của họ. Tuy nhiên, vệ tinh mới - vệ tinh đầu tiên trong 8 vệ tinh GPS IIR do Lookheed Martin chế tạo, có nhiệm vụ cải thiện độ chính xác của toàn hệ thống GPS hiện có. Vệ tinh mới mang theo một tấm anten, cung cấp tín hiệu mạnh hơn cho người sử dụng mặt đất, cũng như ba tín hiệu hoàn toàn mới. Hai trong số đó sẽ giúp quân đội Mỹ 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 38 khắc phục tình trạng tắc nghẽn tín hiệu GPS trên các phương tiện di chuyển mặt đất, máy bay và tàu thuỷ. Ngoài ra, chúng còn cải thiện độ chính xác của các loại vũ khí thông minh định hướng bằng GPS. Tín hiệu thứ ba sẽ là một tần số dành cho người sử dụng dân sự, giảm thiểu lỗi định vị do lớp hạt tích điện ở thượng tầng khí quyển gây ra. Quân đội Mỹ dự định phóng tiếp ba vệ tinh GPS IIR vào năm 2006. Sau đó, vệ tinh đầu tiên trong số 12 vệ tinh còn hiện đại hơn sẽ được phóng vào năm 2007. Những vệ tinh này, GPS IIF, do Boeing chế tạo và cung cấp tín hiệu dân sự thứ ba cho các máy bay. Có 5 loại vệ tinh được sử dụng trong hệ thống GPS: Block I, Block II, Block-IIA, Block IIR và Block IIF - Block I Vệ tinh Block I đầu tiên do tập đoàn Rockwell xây dựng và đưa vào hoạt động vào ngày 22 tháng 2 năm 1978. Các vệ tinh Block I đã hoạt động từ 1978 đến 1985 với tổng số 11 vệ tinh. Các vệ tinh Block I được dùng để kiểm tra và xác nhận độ khả thi của hệ thống định vị. Block I bay trên cùng quĩ đạo với “Block II” nhưng nghiêng một góc là 630, và đương nhiên là sử dụng năng lượng mặt trời. Hình 4-4 Vệ tinh Block I Sau đây là các đặc tính kỹ thuật của các vệ tinh trong “Block I”: Bảng 4-1 Thông số kỹ thuật vệ tinh Block 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 39 Block I Tần số 1572.42 MHz and 1227.6 MHz (L-Band) 2227.5 MHz (S-Band) Nhà cung cấp Tập đoàn Rockwell International Khối lượng 759 kg Tuổi thọ 5 năm Điện năng tiêu thụ 0.410 kw Pin 3 - 15 cell Ah NiCd - Block II Các vệ tinh Block II có trọng lượng khoảng 1660 kg nặng gần gấp 2 lần Block I. Vệ tinh đầu tiên được đưa vào hoạt động đầu tiên vào năm 1989, với sải cánh dài 5.1m và có thời gian phục vụ khoảng 7,5 năm. Có tổng số 9 vệ tinh Block II( từ 12 đến 21), và 18 vệ tinh Block IIA hoạt động đến tháng 9 năm 1996. Các vệ tinh Block II được thiết kế để cho phép 14 ngày hoạt động không cần sự điều khiển của phần điều khiển. Bảng 4-2 Thông số kỹ thuật vệ tinh Block II Tần số 1572.42 MHz and 1227.6 MHz (dải L) 2227.5 MHz (dải S) Nhà cung cấp Tập đoàn Rockwell International Khối lượng 1660 kg Tuổi thọ 7,5 năm Điện năng tiêu thụ 0,710 kw Pin 3 - 35 cell Ah NiCd - Block III Quá trình nghiên cứu cấu trúc của Block III gồm 3 giai đoạn, giai đoạn 1 kết thúc vào năm 2001. Boeing và Lockheed Martin để ra 16 triệu USD cho giai đoạn 1. Một nhà thầu đã trúng thầu để xây dựng và phát triển các vệ tinh Block III, theo dự kiến thì vệ tinh Block III sẽ đưa vào hoạt động vào năm 2009, và đưa toàn bộ các vệ tinh vào năm 2030. 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 40 Lực lượng không quân Mỹ( U.S. Air Force) muốn các vệ tinh Block III phải tăng cường tính bảo mật bằng cách cung cấp 2 kênh cho tín hiệu military-code (M-code) đó là L1 và L2 mà chúng phục vụ cho quân sự. Ngoài ra còn có một số các vệ tinh loại khác như Block IIA, Block IIF... xin xem thêm phần phụ lục. 4.2.2.2 Phần điều khiển Hình 4-5 Vị trí các trạm điều khiển vệ tinh GPS Phần điều khiển là các trạm điều khiển các vệ tinh đặt trên trái đất. Phần điều khiển gồm:1 trạm điều khiển chính, 5 trạm thu số liệu,3 trạm truyền số liệu. - Trạm điều khiển chính Đặt tại Colorade Springs (Mỹ) có nhiệm vụ thu thập các dữ liệu theo dõi vệ tinh từ các trạm thu số liệu để xử lý Công nghệ xử lý gồm : Tính lịch thiên văn, tính và hiệu chỉnh đồng hồ, hiệu chỉnh quỹ Đạo điều khiển, thay thế các vệ tinh ngừng họat động bằng các vệ tinh dự phòng. - 5 trạm thu số liệu Được đặt tại Hawai , Colorade Springs , Ascension (Nam Đại Tây Dương) , Diago Garia (Ấn Độ Dương) , Kwayalein (Nam Thái Bình Dương). Có nhiệm vụ theo dõi các tín hiệu vệ tinh để kiểm soát và dự đoán quỹ đạo của chúng. Mỗi trạm 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 41 được trang bị những máy thu P-code để thu các tín hiệu của vệ tinh, sau đó truyền về trạm điều khiển chính. - 3 trạm truyền số liệu Đặt tại Ascension , Diago Garia , Kwayalein có khả năng chuyển số liệu lên vệ tinh gồm lịch thiên văn mới, hiệu chỉnh đồng hồ, các thông điệp cần phát, các lệnh điều khiển từ xa. 4.2.2.3 Phần sử dụng Phần này gồm các thành phần: - Những máy thu tín hiệu GPS có anten riêng ( máy định vị ). - Các thiết bị tự ghi ( bộ ghi số liệu ). - Máy tính ( phần mềm xử lý số liệu ). - Máy định vị Máy thu GPS tính tóan đơn vị với tần suất mỗi giây một vị trí và cho độ chính xác từ dưới 1m – 5m. Khi ta di chuyển hay dừng tại chỗ , máy thu GPS nhận tín hiệu từ vệ tinh rồi tính toán định vị. Kết quả tính được là tọa độ hiển thị trên màn hình bộ ghi số liệu. - Bộ ghi số liệu Bộ ghi số liệu là máy cầm tay, có phần mềm thu thập số liệu. Bộ ghi số liệu có thể ghi vị trí hoặc gắn thông tin thuộc tính với vị trí. - Máy tính, phần mềm xử lý số liệu Máy tính, phần mềm xử lý số liệu : Hệ thống GPS có kèm theo phần mềm xử lý số liệu. Sau khi thu thập số liệu ở thực địa, phần mềm chuyển số liệu vị trí và thông tin thuộc tính sang máy tính (PC), sau đó phần mềm sẽ nâng cao độ chính xác (bằng kỹ thuật phân sai). Phần mềm xử lý số liệu GPS còn có chức năng biên tập hoặc vẽ. Phần mềm này cũng hỗ trợ thu thập các yếu tố địa lý và thông tin thuộc tính cho GPS hoặc các cơ sở dữ liệu khác. Một số máy định vị được sử dụ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 42 Bảng 4-3 Một số máy định vị GPS 4.3 Hoạt động của hệ thống GPS 4.3.1 Sóng của vệ tinh GPS Một vệ tinh có thể truyền tín hiệu radio ở nhiều mức tần số thấp khác nhau, được gọi là L1, L2... Những thiết bị nhận tín hiệu GPS thông thường bắt sóng L1, ở dải tần số UHF 575,42 Mhz. Một đài phát thanh FM thường cần có công suất chừng 100.000 watt để phát sóng, nhưng một vệ tinh định vị toàn cầu chỉ đòi hỏi 20-50 watt để đưa tín hiệu đi xa 19.200 km. Hình 4-6 Thiết bị nhận GPS cài đặt sẵn trên xe Honda Accord Tần số L1 chứa đựng 2 tín hiệu số mã hoá bằng kỹ thuật số), được gọi là P-code và C/A-code. Mã P nhằm bảo vệ thông tin khỏi những sự truy nhập trái phép. Tuy nhiên, mục đích chính của các tín hiệu mã hóa là nhằm tính toán thời gian cần thiết để thông tin 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 43 truyền từ vệ tinh tới một thiết bị thu nhận trên mặt đất. Sau đó, khoảng cách giữa 2 bên được tính bằng cách nhân thời gian cần thiết để tín hiệu đến nơi với tốc độ của ánh sáng là 300.000 km/giây (khoảng cách = vận tốc x thời gian). Tuy nhiên, tín hiệu có thể bị sai đôi chút khi đi qua bầu khí quyển. Vì vậy, kèm theo thông điệp gửi tới các thiết bị nhận, các vệ tinh thường gửi kèm luôn thông tin về quỹ đạo và thời gian. Việc sử dụng đồng hồ nguyên tử sẽ đảm bảo chính xác về sự thống nhất thời gian giữa các thiết bị thu và phát. Để biết vị trí chính xác của các vệ tinh, thiết bị nhận GPS còn nhận thêm 2 loại tín hiệu mã hóa. - Loại thứ nhất (được gọi là Almanac data) được cập nhật định kỳ và cho biết vị trí gần đúng của các vệ tinh trên quỹ đạo. Nó truyền đi liên tục và được lưu trữ trong bộ nhớ của thiết bị thu nhận khi các vệ tinh di chuyển quanh quỹ đạo. - Tuy nhiên, phần lớn các vệ tinh có thể hơi di chuyển ra khỏi quỹ đạo chính của chúng. Sự thay đổi này được ghi nhận bởi các trạm kiểm soát mặt đất. Việc sửa chữa những sai số này là rất quan trọng và được đảm nhiệm bởi trạm chủ trên mặt đất, trước khi thông báo lại cho các vệ tinh biết vị trí mới của chúng. Thông tin được sửa chữa này được gọi là Ephemeris data. Kết hợp Almanac data và Ephemeris data, các thiết bị nhận GPS biết chính xác vị trí của mỗi vệ tinh. Với GPS, các tín hiệu từ các vệ tinh sẽ đi tới các vị trí chính xác của người dùng và được đo theo phép tam giác đạc. Để thực hiện phép tam giác đạc, GPS đo khoảng cách thông qua thời gian hành trình của bản tin vô tuyến từ vệ tinh tới một máy thu mặt đất. Để đo thời gian hành trình, GPS sử dụng các đồng hồ rất chính xác trên các vệ tinh – sử dụng đồng hồ nguyên tử. Một khi khoảng cách tới vệ tinh đã được đo thì việc biết trước về vị trí vệ tinh trong không gian sẽ được sử dụng để hoàn thành tính toán. Các máy thu GPS trên mặt đất có một “cuốn niên giám” được lưu trữ trong bộ nhớ máy tính của chúng để chỉ thị mỗi vệ tinh sẽ có mặt nơi nào trên bầu trời vào bất kỳ thời điểm nào. Để bảo đảm chắc chắn vệ tinh và máy thu đồng bộ với nhau, mỗi vệ tinh có bốn đồng hồ nguyên tử chỉ thời gian chính xác tới 3 ns, tức ba phần tỷ giây. Nhằm tiết kiệm chi phí, các đồng hồ trong các máy thu dưới đất được làm ít chính xác hơn đôi chút. Bù 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 44 lại, một phép đo tầm hoạt động vệ tinh được trang bị thêm. Phép đo lượng giác chỉ ra rằng, nếu ba số đo chính xác định vị được vị trí một điểm trong không gian ba chiều thì một phép đo thứ tư có thể loại bỏ mọi độ chênh lệch thời gian nào đó. Phép đo thứ tư này chỉnh lại sự đồng bộ hoá không hoàn hảo của máy thu. GPS sử dụng một hệ tọa độ gọi là Hệ thống Trắc địa học Toàn cầu 1984 (WGS-84 - Worldwide Geodetic System 1984). Hệ thống này tương tự như các đường kẻ kinh tuyến và vĩ tuyến quen thuộc thường thấy trên các bản đồ treo tường cỡ lớn. Hệ thống WGS - 84 cung cấp một khung tham chiếu gắn sẵn tiêu chuẩn hoá, cho phép các máy thu của bất kỳ hãng sản xuất nào cũng cung cấp đúng cùng một thông tin định vị. Hiện nay, nhờ có bản đồ số, nhiều thiết bị nhận GPS sẽ hiển thị rõ ràng vị trí của bạn qua một màn hình, điều đó giúp cho việc định hướng trở nên cực kỳ thuận lợi. Nhưng nếu tắt thiết bị nhận tín hiệu trong khoảng thời gian chừng 5 giờ đồng hồ, nó sẽ mất đi các Almanac data (hay không còn nhận biết chính xác các vệ tinh trên quỹ đạo trái đất). Khi hoạt động trở lại, thiết bị sẽ cần khoảng thời gian chừng 30 giây để nạp lại thông tin về vị trí của vệ tinh, trước khi cho biết hiện thời bạn đang ở đâu. 4.3.2 Vị trí trên mặt đất được xác định như thế nào qua hệ thống GPS? Chúng ta biết, phần sử dụng trong hệ thống GPS bao gồm các thiết bị thu tín hiệu từ vệ tinh. Để sau đó chúng qua quá trình xử lí kỹ thuật sẽ đưa ra vị trí đúng của chúng. Mỗi vệ tinh quay quanh trái đất 2 vòng một ngày đêm. Quỹ đạo của các vệ tinh được tính toán sao cho ở bất kỳ nơi nào trên trái đất, vào bất kỳ thời điểm nào, cũng có thể “nhìn thấy” tối thiểu 4 vệ tinh.Công việc của một máy thu GPS là xác định vị trí của 4 vệ tinh hay hơn nữa, tính toán khoảng cách từ các vệ tinh và sử dụng các thông tin đó để xác định vị trí của chính nó. Vì phải dựa vào ít nhất là tín hiệu của 4 vệ tinh thì thông tin về vị trí mới chính xác cao. 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 45 Hình 4-7 Thu tín hiệu vệ tinh GPS Các thiết bị thu GPS xác định quãng đường (S) từ vệ tinh đến nó, bằng cách: lấy thời gian(T) nhân với vận tốc của ánh sang (V = 3.108m/s). Quá trình xác định vị trí dựa trên một nguyên lý toán học đơn giản. Giả sử bạn đang ở một nơi nào đó ở Vietnam, và bạn hoàn toàn không biết minh ở đâu, vì một lý do nào đó. Bạn gặp một người dân địa phương và hỏi một cách thân thiện: “làm ơn cho tôi biết tôi đang ở đâu ?” Anh ta trả lời: “bạn đang cách Vũng tàu 45 km”. Đây là một sự thật thú vị, nhưng chưa thật sự có ích. bạn có thể ở bất kỳ đâu trên vòng tròn có tâm là Vũng tàu, bán kính 45 km. Bạn hỏi một người khác và cô ta cho biết bạn đang cách Biên Hoà 40 km. Bây giờ bạn đã khá hơn. Nếu bạn tổng hợp hai thông tin, bạn sẽ có hai vòng tròn giao nhau. Vị trí của bạn là một trong hai giao điểm của hai đường tròn. Người thứ ba cho bạn biết vị trí của bạn cách Sài gòn 30 km. Bây giờ thì bạn đã biết mình đang ở đâu. Áp dụng nguyên lý nay vào không gian ba chiều, ta cũng có ba mặt cầu thay vì ba đường tròn, giao nhau tại một điểm. Về mặt nguyên lý thì không khác nhau nhiều lắm, nhưng khó tưởng tượng hoặc mô tả bằng hình vẽ hơn. Thay vì các đường tròn, bạn sẽ có các mặt cầu. S = V.T Khí quyể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 46 Hình 4-8 Vệ tinh GPS truyền tín hiệu về trái đất 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 Nếu bạn biết rằng mình đang ở cách vệ tinh A 20 km, bạn có thể ở bất kỳ nơi nào trên một mặt cầu khổng lồ có bán kính 20 km. Nếu bạn biết thêm rằng bạn đang ở cách vệ tinh B 30 km, giao tuyến của hai mặt cầu này là một đường tròn V. Và nếu bạn biết thêm một khoảng cách nữa đến vệ tinh C, bạn sẽ có thêm một mặt cầu, mặt cầu này giao với đường tròn V tại hai điểm. Trái đất chính là mặt cầu thứ tư, một trong hai giao điểm sẽ nằm trên mặt đất, điểm thứ hai nằm lơ lửng đâu đó trong không gian và dễ dàng bị loại. Với việc giả sử trái đất là một mặt cầu, ta đã bỏ qua cao độ của bạn rồi. Do vậy để có cả tung độ, hoành độ và cao độ, bạn cần thêm một vệ tinh thứ tư nữa. 2 vị trí có thể cần được xác định 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 47 Như vậy, với việc thu tín hiệu của ít nhất của 4 vệ tinh cùng tại một thời điểm thì ta thu được vị trí( toạ độ) có độ chính xác cao. Vì vậy mà GPS ngày càng được ứng dụng rộng dãi trong các lĩnh vực đời sống … 4.4 Ứng dụng của hệ thống GPS Thực sự với nhiệm vụ của mình là xác định chính xác toạ độ, vận tốc tại một thời điểm bất kì của một vị trí nào đó, hệ thống định vị toàn cầu đã khẳng định cần thiết của mình trong các lĩnh vực đời sống. Chúng ta liệt kê ra dưới đây một vài ứng dụng của hệ thống GPS. • Quân sự Với mục tiêu ban đầu khi ra đời - hệ thống GPS để phục vụ cho Quân đội của Mỹ. Chính vì vậy, GPS đã trở thành công cụ không thể thiếu trong nền Quân sự của Mỹ nói riêng, và các nước trên thế giới nói chung. Nhờ hệ thống GPS mà các mục tiêu quân sự được xác định có độ chính xác rất cao( sai số có khỉ chỉ tính vài mét). Các hệ thống tên lửa hành trình, các máy bay không người lái… được dẫn đường bởi hệ thống định vị toàn cầu sẽ trở nên vô cùng lợi hại. Trong các cuộc chiến tranh của Mỹ gây ra thì Mỹ đã áp dụng triệt để lợi thế có được từ hệ thống định vị GPS, từ đó khả năng đánh chính xác mục tiêu rất lớn. • Khí tượng, thời tiết GPS được các nhà khoa học áp dụng vào để cảnh báo trước các thảm họa thời tiết sẽ xảy ra cho con người như: động đất, sóng thần… Các nhà khoa học đang đề nghị NASA phóng một vệ tinh có trang bị InSAR và họ hy vọng trong vòng 20 năm tới sẽ có thêm nhiều vệ tinh tương tự như vậy trong quỹ đạo Trái đất. Mặc dù một vệ tinh đơn nhất, được trang bị InSAR, sẽ rất hữu ích song một hệ thống các vệ tinh như vậy sẽ cung cấp vô số dữ liệu cho các nhà khoa học dự báo động đất. Trong khi các nhà khoa học đợi chờ mạng vệ tinh InSAR trở thành hiện thực, hệ thống định vị toàn cầu GPS đang được sử dụng để giám sát vỏ Trái đất. Thông tin do GPS cung cấp hiện giúp các nhà khoa học tạo ra những mô hình biến dạng phức tạp của vỏ Trái đất. Các nhà khí tượng học Mỹ đưa ra một thiết bị dự báo sét. Nó có thể phân tích các tín hiệu thu được từ hệ thống định vị toàn cầu (GPS) để đoán biết nơi gặp gỡ của các đám mây lớn, thời điểm phóng sét và cường độ của sét. • Tìm đườ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 48 Đây cũng là ứng dụng mà chúng ta sẽ tìm hiểu kĩ ở phần sau. Với sự trợ giúp của GPS thì việc tìm đường đi từ điểm này đến điểm kia hoàn toàn có thể, kết hợp với một cái bản đồ số và thiết bị hiện thị( như các máy thu GPS, điện thoại di động…) một đường đi trực quan sẽ được vẽ ra… • Các ứng dụng khác… GPS ngày càng len lỏi sâu và rộng các ứng dụng đời sống con người. Khi đời sống ngày càng hiện đại thì các nhu cầu dù có thể là nhỏ bé của con người cũng được GPS “chăm sóc”. Các con vật đáng yêu của bạn có thể không sợ mất khi bị lạc, các ông chồng hay ghen sẽ yên tâm hơn với một chiếc quần lót của bà vợ có gắn thiết bị thu GPS... 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 49 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 5.1 Tích hợp bản đồ số với GPS trên điện thoại di động 5.1.1 Giới thiệu chung 5.1.2 Một số dịch vụ dựa trên vị trí 5.1.2.1 Dịch vụ thông tin dựa trên vị trí 5.1.2.2 Tính cước theo vị trí địa lý 5.1.2.3 Dịch vụ khẩn cấp 5.1.2.4 Dịch vụ dò tìm 5.1.3 Các kỹ thuật định vị thuê bao di động 5.1.3.1 Kỹ thuật Cell-ID 5.1.3.2 A-GPS (Assisted GPS - hỗ trợ GPS) 5.1.3.3 Phương pháp kết hợp 5.2 Bài toán tìm đường đi ngắn nhất trên PocketPC 5.2.1 Giới thiệu bài toán 5.2.2 Thuật toán sử dụng trong bài toán 5.2.3 Dữ liệu bản đồ 5.2.4 Lập trình 5.2.5 Một số hình ảnh của chương trình 5.2.6 Đánh giá chương trình 5.2.6.1 Các điểm đã đạt được 5.2.6.2 Các điểm chưa đạt được 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 50 5.1 Tích hợp bản đồ số với GPS trên điện thoại di động 5.1.1 Giới thiệu chung Ngày nay các ứng dụng trên chiếc điện thoại di động nhỏ bé ngày càng lớn dần, và phục vụ ngày càng nhiều nhu cầu phức tạp của con người. Chỉ với một chiếc Mobile đơn lẻ thì ta chỉ đơn giản là gọi điện, gửi tin, lướt web... nhưng khi chúng ta kết hợp nó với các ứng dụng khác đặc biệt với hệ thống định vị toàn cầu GPS, với công nghệ của bản đồ số thì ứng dụng của nó có “sức mạnh” của nó tăng lên gấp bội. Sự kết hợp của 3 thành phần: Mobile, GPS, và Digital Map đã tạo ra các dịch vụ ứng dụng định vị LBS4 (Location Base Services) đầy tiềm năng. Mô hình sự kết hợp của Mobile, GPS, Digital Map như sau: Hình 5-1 Mô hình kết hợp Mobile, GPS, DigitalMap Công nghệ GIS (Geographic Information Systems) nói chung và công nghệ bản đồ số nói riêng cùng các kỹ thuật định vị đang mở rộng các ứng dụng truyền thống sang các ứng dụng dựa trên vị trí. Thông qua việc tích hợp các công nghệ này vào thiết bị di động cho phép các nhà khai thác cung cấp rất nhiều các ứng dụng khác nhau cho khách hàng khi đã xác định được vị trí của họ. Hầu hết các dự báo về tiềm năng của LBS cho rằng dịch vụ này sẽ thu lại khoảng 7 đến 8 triệu USD trong vòng 4 năm tới. Do vậy một số 4 Dịch vụ dựa trên vị trí 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 51 Các nhà khai thác dịch vụ di động rất quan tâm đến các vấn đề kinh tế, kỹ thuật khi triển khai dịch vụ này trên mạng của họ. 5.1.2 Một số dịch vụ dựa trên vị trí Chúng ta có thể điểm qua một số dịch vụ dựa trên vị trí LBS: + Dịch vụ thông tin dựa trên vị trí (Location based information services) + Tính cước theo vị trí địa lý (Location sensitive billing) + Các dịch vụ khẩn cấp (Emergency services) + Dịch vụ dò tìm (Tracking) 5.1.2.1 Dịch vụ thông tin dựa trên vị trí Hình 5-2 Phần mềm tìm đường Wayfinder trên mobile Các ứng dụng có các thông tin được lựa chọn, chuyển tải đến người sử dụng cuối dựa vào vị trí của họ chính là các ứng dụng thuộc loại dịch vụ này. Các ứng dụng kiểu này rất thông dụng, ví dụ bạn đang đứng giữa đường và đang gặp nguy hiểm bạn có thể tìm ra đường đi đến vị trí trạm công an gần nhất để cần giúp đỡ khi đó nếu bạn có đầu cuối hỗ trợ WAP (Wireless Access Protocol) cùng sự trợ giúp của ứng dụng LBS sẽ tương tác các thành phần khác trong mạng để tìm ra vị trí của bạn và đưa ra đường đi ngắn nhất cũng như vị trí của trạm công an gầ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 52 Độ chính xác của vị trí của loại dịch vụ này là khác nhau tùy vào loại thông tin cung cần cung cấp. Như ví dụ tìm đường đi ngắn nhất thì yêu cầu độ chính xác cao, trong khi ứng dụng cung cấp thông tin về thời tiết khí hậu yêu cầu độ chính xác tương đối. 5.1.2.2 Tính cước theo vị trí địa lý Các ứng dụng này cung cấp khả năng có tính cước ưu đãi. Thông qua dịch vụ tính cước theo vị trí địa lý, tức là cước của dịch vụ phụ thuộc vào vị trí địa lý. Ví dụ, khách hàng có thể thiết lập các vùng dành riêng chẳng hạn “vùng làm việc” hoặc “vùng cư trú”. Khách hàng sẽ thoả thuận với nhà cung cấp về giá cước để họ có thể đạt được tốc độ dữ liệu không thay đổi khi thuộc vùng cư trú và các tốc độ cao hơn ở vùng làm việc. Loại hình dịch vụ này có thể đặc biệt hữu ích khi sử dụng cùng với các ứng dụng di động khác như dịch vụ thuê bao trả trước. 5.1.2.3 Dịch vụ khẩn cấp Như tên gọi của nó các dịch vụ này dành cho các trường hợp khẩn cấp như khi bạn gặp nạn, hỏa hoạn,… thì bạn có thể dùng điện thoại di động gọi điện cho cảnh sát, xe cứu thương, lính cứu hỏa,… và từ tín hiệu điện thoại di động của bạn các nhân viên cứu trợ sẽ xác định được không chỉ vị trí hiện tại của bạn nơi xảy ra tai nạn mà còn xác định được cả các thông tin về cá nhân của bạn (nếu bạn đăng kí) như nhóm máu, tình trạng sức khỏe,... của bạn. Và đó là các thông tin cực kì quí giá để các nhân viên cứu trợ giúp bạn nhanh nhất. 5.1.2.4 Dịch vụ dò tìm Hình 5-3 Xe ô tô được gắn thiết bị thu GPS Những dịch vụ dò tìm đòi hỏi độ chính xác về vị trí rất cao. Có ba loại dịch vụ dò tìm chủ yếu: 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 53 - Quản lý nhân lực/Quản lý các phương tiện: ứng dụng cho các công ty taxi, vận tải… Dịch vụ này giúp họ biết được nhân viên họ/các máy móc thiết bị đang ở đâu để có thể điều hành một cách hiệu quả nhất. - Dò tìm hiện vật: dùng cho cả các tổ chức hay cá nhân muốn đảm bảo một vật gì giá trị có thể tìm được nếu như bị đánh cắp. - Dịch vụ tìm người: Dịch vụ này cho phép bố mẹ biết được con cái họ hiện đang ở đâu, các ông chông hay ghen sẽ yên tâm khi biết vợ mình đang ở đâu! hoặc bạn bè tìm kiếm nhau v.v... 5.1.3 Các kỹ thuật định vị thuê bao di động Kỹ thuật định vị thuê bao di động ở đây ta chỉ xét trong mạng GSM/GPRS. Các nhà cung cấp dịch vụ LBS đã sử dụng một số phương pháp khác nhau nhằm định vị vị trí thuê bao. Có thể chia phương pháp định vị làm hai loại chính: - Dựa trên cơ sở mạng như Cell-ID, TOA (Time Of Arrival), AOA (Angle of Arrival), TDOA (Time Difference Of Arrival). - Dựa trên máy di động như E-OTD, A-GPS. Nhưng cũng có người phân chia phương pháp định vị thành hai loại, thứ nhất là loại phụ thuộc vào hệ thống GPS và loại còn lại là nó không phụ thuộc vào hệ thống định vị GPS. Phần tiếp theo chúng ta sẽ tập trung tìm hiểu các kỹ thuật Cell-ID và A-GPS. 5.1.3.1 Kỹ thuật Cell-ID Đây là phương pháp đơn giản nhất để xác định vị trí thuê bao di động. Với phương pháp này yêu cầu mạng xác định vị trí BTS5 trong đó MS6 nằm trong phạm vi BTS đó. Và vị trí của MS cũng chính là vị trí của BTS đó. Nhưng MS có thể ở bất kì vị trí nào trong BTS, nên vị trí MS còn phụ thuộc vào kích thước Cell. Độ chính xác sẽ phụ thuộc trực tiếp vào kích thước của BTS. Nếu trong khu thành phố, đô thị thì mật độ BTS là rất mau nên kích thước của cell là nhỏ do đó độ chính xác vị trí của MS là rất cao và ngược lại nếu ở vùng BTS thưa như vùng ngoại ô, vùng quê thì kích thước của một cell là lớn nên độ chính xác vị trí của MS là không cao, sai số trong phép định vị lên đến chục km. Để tăng độ chính xác kỹ thuật Cell-ID sử dụng sector-ID kết hợp với một hoặc các hai kỹ thuật là TA (Timing Advance) và dựa vào độ mạnh của tín hiệu. 5 Base Transceiver Station 6 Mobile Station 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 54 - TA Kỹ thuật TA sử dụng thông tin về sai lệch thời gian được gửi từ BTS tới hiệu chỉnh thời gian phát của MS sao cho tín hiệu từ MS tới BTS đúng với khe thời gian dành cho MS để tính ra khoảng cách từ MS tới BTS. Tuy nhiên, kỹ thuật TA chỉ cho biết MS trong vùng địa lý của BTS đang phục vụ nó với bán kính xác định được nhờ TA. - Độ mạnh của tín hiệu Ngoài ra, trong mạng thông tin di động MS thường đo độ mạnh của tín hiệu từ một số BTS và gửi thông tin này đến BTS đang phục vụ nó, vì vậy có thể dựa vào thông tin độ mạnh tín hiệu này để tính ra được vị trí MS với độ chính xác cao hơn TA. Tuy nhiên, có rất nhiều yếu tố làm hạn chế hiệu quả của phương pháp này như địa hình, suy hao ở môi trường trong nhà (các vật liệu xây dựng, hình dạng, kích cỡ toà nhà) Hình 5-4 Cell-ID kết hợp với Cell-sector hoặc TA Ưu điểm của phương pháp Cell-ID là ít phải thay đổi phần cứng, vì vậy mà ít tốn kém. Nhược điểm của phương pháp là độ chính xác vị trí kém, và nó phụ thuộc vào mật độ cell. Sau đây chúng ta sẽ đến với một kỹ thuật định vị có độ chính xác cao hơn nhiều so với kỹ thuật Cell-ID, đó là kỹ thuật A-GPS. 5.1.3.2 A-GPS (Assisted GPS - hỗ trợ GPS) A-GPS là một “biến thể” của GPS trong mạng điện thoại di động. A-GPS có thể sử dụng trong các mạng GSM, GPRS và WCDMA. Kỹ thuật này là phương pháp định vị có độ chính xác cao hơn trong phương pháp Cell-ID bởi trong việc định vị thì A-GPS sử dụng các vệ tinh làm các điểm tham chiếu để xác định vị trí. A-GPS sử dụng ít nhất 3 vệ tinh trong việc định vị, máy thu GPS thu tín hiệu từ vệ tinh GPS và nhờ có các đồng hồ có độ chính xác cao thì khoảng thời gian mà tín hiệu truyền từ vệ tinh GPS hoàn toàn xác định. Sau đó lây khoảng thời gian đó nhân với vận tốc ánh sáng (coi như gần bằng vận tốc của tín hiệu vệ tinh), thế là ta xác định được khoảng các từ vệ tinh GPS đến máy thu 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 55 GPS. Bạn đọc có thể tham khảo lại nguyên tắc xác định vị trí trên mặt đất của hệ thống GPS [4.3.2]. Khoảng thời gian chính xác có thể nhận được từ các tín hiệu vệ tinh tuy nhiên quá trình để nhận được thông tin này khá lâu và khó khăn khi tín hiệu từ vệ tinh quá yếu. Để giải quyết vấn đề này người ta sử dụng một server (A-GPS Location server) cung cấp các thông tin liên quan đến vệ tinh cho các máy thu. Những thông tin hỗ trợ từ server này giúp máy thu giảm được thời gian xác định vị trí và cho phép các máy thu A – GPS hoạt động trong các môi trường khác nhau. Hình 5-5 Nguyên lý hoạt động của A-GPS Máy thu A-GPS hoạt động ở hai dạng chính: - MS-Assisted (hỗ trợ từ MS) Ở dạng này, máy thu A-GPS trong MS nhận một ít thông tin từ server A-GPS LS và tính khoảng cách đến các vệ tinh, các thông tin này được MS gửi lại server để server này xác định vị trí của MS. - MS-Based (dựa trên MS) Còn ở dạng dựa trên MS thì MS xác định luôn vị trí của nó nhờ các thông tin hỗ trợ từ server. Việc thực hiện A-GPS hầu như không ảnh hưởng nhiều đến hạ tầng mạng và có thể hỗ trợ tốt cho việc roaming7, tuy nhiên với các MS yêu cầu phải có thêm phần mạch A-GPS. . Bảng 5-1 Đặc tính kỹ thuật A-GPS 7 Chuyển vùng A-GPS Location server 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 56 Chỉ tiêu Đánh giá Chú thích Độ ổn định Tốt Độ chính xác cao ở mọi vị trí địa lý Độ chính xác Tốt Từ 5 đến 50 m khi sử dụng A-GPS và có thể định vị ba chiều. Tuy nhiên cũng sẽ phụ thuộc vào phương án kết hợp TTFF (Time to First Fix) Tốt Khoảng 5 đến 10s Đầu cuối Trung bình Yêu cầu thay đổi cả phần cứng, phần mềm Roaming Tốt Yêu cầu phải có A-GPS LS ở mạng khách. Hiệu suất Tốt Sử dụng ít băng thông và dung lượng của mạng Khả năng mở rộng Tốt Rất dễ dàng mở rộng Tính tương thích Tốt Phương án này có thể sử dụng cho tất cả các mạng GSM, GPRS và WCDMA Kỹ thuật A-GPS đã tỏ rõ khả năng chính xác trong định vị của mình, nhưng khi ta kết hợp các phương pháp lại với nhau ta sẽ được một phương pháp kết hợp rất tốt, cụ thể ở đây ta sẽ tìm hiểu phương pháp kết hợp giữa A-GPS với Cell-ID. 5.1.3.3 Phương pháp kết hợp Trong mạng GSM/GPRS, WCDMA thì phương pháp kết hợp A-GPS với Cell-ID là phổ biến nhất. Phương pháp kết hợp này sẽ nắm lấy ưu điểm của cả hai kỹ thuật riêng biệt A-GPS và Cell-ID, chúng bù trừ, hỗ trợ khuyết điểm của nhau. Cụ thể là vùng phục vụ của A-GPS sẽ tăng lên, và cải thiện đáng kể độ chính xác của A-GPS trong nhiều trường hợp. Độ chính xác và vùng phủ của A-GPS rất tốt ở mọi địa điểm mà thuê bao tới, tuy vậy nó sẽ giảm mạnh đi khi thuê bao ở trong các toà nhà hoặc vùng mật độ đông đúc. Những nơi này thường mật độ cell rất cao do đó phương pháp cell-ID lại có khả năng xác định được vị trí khá chính xác cho dù không bằng A-GPS. Kết hợp hai phương pháp này làm tăng khả năng roaming cho thuê bao và có thể hỗ trợ cho rất nhiều MS đã có trong mạng. Ngoài phương án kết hợp A-GPS với cell-ID người ta cũng có kết hợp A- GPS với E-OTD8. Bảng 5-2 Đặc tính phương pháp kết hợp 8 Xem phần phụ lục 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 57 Chỉ tiêu Đánh giá Chú thích Độ ổn định Tốt Độ chính xác cao ở mọi vị trí địa lý Độ chính xác Tốt Từ 5 đến 50 m khi sử dụng A-GPS và có thể định vị ba chiều. Tuy nhiên cũng sẽ phụ thuộc vào phương án kết hợp TTFF (Time to First Fix) Tốt Khoảng 5 đến 10s Đầu cuối Trung bình Yêu cầu thay đổi cả phần cứng, phần mềm Roaming Tốt Yêu cầu phải có A-GPS LS ở mạng khách. Tuy nhiên sẽ hạn chế khi kết hợp A-GPS với E-OTD Hiệu suất Tốt Sử dụng ít băng thông và dung lượng của mạng Khả năng mở rộng Tốt Rất dễ dàng mở rộng Tính tương thích Tốt Phương án này có thể sử dụng cho tất cả các mạng GSM, GPRS và WCDMA Trong phần tiếp theo chúng ta sẽ cùng nhau tìm hiểu bài toán tìm đường đi ngắn nhất trên PocketPC9 để hiểu rõ hơn ứng dụng to lớn của LBS – các dịch vụ dựa trên định vị. 5.2 Bài toán tìm đường đi ngắn nhất trên PocketPC. 5.2.1 Giới thiệu bài toán Đây là bài toán tìm ra đường đi ngắn nhất từ nơi này đến nơi khác trên bản đồ số trên PocketPC do tác giả cùng nhóm của mình tại công ty IWICOM10 Ở đây chúng ta sử dụng từ “nơi này” “nơi khác” mà tránh sử dụng kiểu như “điểm này” “điểm khác”, như vậy sẽ tổng quát hơn và tránh được hiểu lầm. Input: Nhập nơi bắt đầu, nơi cần đến (Ví dụ nhập tên của đường, số nhà,…) Ouput: - Bản đồ đường đi ngắn nhất nếu tồn tại thoả mãn có nơi bắt đầu và nơi cần đến. - Chỉ rẫn cụ thể đường đi từ nơi bắt đầu đến nơi cần đến 9 một loại máy giả lập thay cho Mobile Phone 10 Công ty phần mềm IWICOM 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 58 - Đường đi ngắn nhất là đường đi có hướng - tức là có tính đến yếu tố đường một chiều. 5.2.2 Thuật toán sử dụng trong bài toán Chúng tôi đã sử dụng thuật toán nổi tiếng là Dijkstra để tìm đường đi ngắn nhất giữa hai điểm. Sau đây xin giới thiệu sơ qua về thuật toán này. Tóm tắt thuật toán: Thuật toán Dijkstra chỉ áp dụng được cho đồ thị không có cạnh âm. Giả sử ta phải tìm đường đi ngắn nhất từ x đến y. Thuật toán sẽ bắt đầu từ đỉnh xuất phát x và kết thúc khi đỉnh y đã được xét (tối ưu). Mảng arrnCost sẽ lưu đường đi tối ưu - ngắn nhất (hiện tại) từ đỉnh xuất phát đến các đỉnh trong đồ thị. Một đỉnh i đã được xét xong (finalized) sẽ có arrnCost[i] chính là độ dài đường ngắn nhất. Nếu muốn in ra đường đi ngắn nhất, ta sẽ phải sử dụng thêm một mảng phụ để lưu lại đỉnh trước đó (đỉnh cha). Đường đi sẽ được duyệt từ đỉnh y, đến arrnPrevious[y], … đến khi nào gặp đỉnh x thì dừng. Có thể hiểu ngắn gọn rằng tập đã xét xong (V\T)11 sẽ được mở rộng dần, bắt đầu là đỉnh x, sau đó là đỉnh x1 có chi phí đi từ x đến x1 là bé nhất, rồi đến đỉnh x2 có đường đi tích luỹ 12đi từ x hoặc x1 là bé nhất, rồi đến đỉnh x3… cứ như vậy cho đến khi đỉnh y cũng thuộc về tập đã xét xong (y ∈V\T hay y ∉ T13). Cũng giống như thuật toán tìm cây khung Prime, việc tìm lại một đường ngắn nhất từ tập đã xét xong V\T đến tập chưa xét xong T sẽ tốn rất nhiều chi phí (cần 2 vòng for), do đó ta có thể cải tiến bằng cách lưu lại độ dài nhỏ nhất đến đỉnh v ∈ T và chỉ cần 1 vòng for để tìm đỉnh có độ dài min. Dưới đây là thuật toán Dijkstra: 1. Khởi tạo: o Thuật toán được bắt đầu với giả thiết là độ dài đường đi từ đỉnh xuất phát đến tất cả các đỉnh khác là ∞ (có thể sử dụng trị đặc biệt là -1), trừ chính đỉnh xuất phát x, có độ dài đường đi là 0 (dùng mảng int arrnCost[MAX]): arrnCost[i] = ∞, ∀i ≠ x; arrnCost[k] = 0 11 tập các điểm đã xét 12 tổng đường đi 13 tập các điểm chưa xé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 59 o Ngoài ra, ban đầu, tất cả các đỉnh đều thuộc về tập chưa xét xong (not finalized yet) T (dùng mảng int T[MAX]): T[i] = true (1), ∀i o Để có thể lưu lại đường đi ngắn nhất, ta cần sử dụng thêm một mảng (int arrnPrevious[MAX]) 2. Nếu đỉnh y ∉ T, nghĩa là y đã xét xong (finalized), và arrnCost[y] chính là đường đi ngắn nhất, ta dừng thuật toán, in ra chi phí và đường đi ngắn nhất. 3. Chọn một đỉnh v ∈ T (chưa xét xong) có chi phí nhỏ nhất (dùng một vòng for). Nếu không tìm được một v như vậy, nghĩa là không thể tìm được đường đi từ x đến y (không liên thông). Dừng thuật toán và thông báo không tìm được đường đi. 4. Đánh dấu v đã được xét xong (finalized): T := T\{v} T[v] = false (0)) 5. ∀k ∈ T, nếu có cạnh nối từ v đến k và đường đi ngắn hơn arrnCost[k] == -1 (chưa xét) hoặc arrnCost[k] > arrnCost[v] + a[v, k] (tối ưu hơn) thì ta sẽ cập nhật lại đường đi ngắn nhất hoặc arrnCost[k] > arrnCost[v] + a[v, k] 6. Quay lại bước 2 Dưới đây là minh họa cho thuật toán Dijkstra với đỉnh xuất phát là 1, đỉnh kết th