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
http://www.ebook.edu.vn
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


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

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

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
http://www.ebook.edu.vn
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ư

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
http://www.ebook.edu.vn
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ố


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
http://www.ebook.edu.vn
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 GIS
1
: 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.


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
http://www.ebook.edu.vn
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;
}
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

• 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
http://www.ebook.edu.vn
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

ơ 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
http://www.ebook.edu.vn
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ỹ

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
http://www.ebook.edu.vn
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

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
http://www.ebook.edu.vn
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

đ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
http://www.ebook.edu.vn
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

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.

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ử

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

ã đượ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