Download miễn phí Đề 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
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è.
MỤC LỤC
Trang
LỜI NÓI ĐẦU
4
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
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
http://s1.luanvan.co/qYjQuXJz1boKCeiU9qAb3in9SJBEGxos/swf/2013/06/23/de_tai_tim_hieu_tich_hop_ban_do_so_he_thong_gps_t.HwThASOrUc.swf luanvanco /luan-van/de-tai-ung-dung-tren-liketly-30584/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
hình dạng, kích cỡ toà nhà)
Hình 5-4 Cell-ID kết hợp với Cell-sector hay 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à hay 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 tui đã 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
...
