Đề 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

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úc là 2. 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 60 Nhận xét rằng, thuật toán trên chỉ đúng khi, độ dài đường đi đến các đỉnh xi luôn ≤ đường đi đến các đỉnh xj (vói j≤i). Nếu như trong đồ thị có cạnh âm, đường đi tìm đượ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 61 có thể sẽ không là tối ưu. Xét ví dụ dưới hình sau với đỉnh xuất phát là 0, đỉnh kết thúc là 2: B1: T = {0, 1, 2}, arrnCost[] = {0, ∞, ∞}, B2: v = 0 ⇒ T = {1, 2}, arrnCost[] = {0, 3, 2} B3: v = 2 ⇒ T = {1}, arrnCost[] = {0, 3, 2} B4: 2 ∉ T, dừng thuật toán. Đường đi ngắn nhất tìm được là 2. Rõ ràng là nếu ta đi theo 0 → 1 → 2 thì đường đi là 1 (3-2), đường đi 2 tìm được không phải là chi phí ngắn nhất. 5.2.3 Dữ liệu bản đồ Dữ liệu bản đồ trong bài toán được xây dựng dựa trên kỹ thuật vector. Đây là một kỹ thuật mạnh và hiệu quả. Người đọc có thể tìm hiểu thêm về kỹ thuật vector ở phần 2.4 của luận văn, chúng ta sẽ không trình bài lại ở đây. Nhưng cũng xin nhắc lại là đối với bản đồ số có 3 lớp quan trọng nhất, đó là: các điểm, các đường, các vùng. Trong bài toán này, bản đồ được chia thành các cell – hay các ô. Một một cell gồm một chỉ số Index để phân biệt cell này với cell khác. Hình 5-6 Bản đồ được chia thành các ô - cell Bản đồ trên minh họa một bản đồ được chia thành nhiều ô – cell, trong một cell có nhiều đường khác nhau chạy qua, và trong một cell cũng có nhiều các đa giá – polygon, 3 2 - 2 1 0 2 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 62 các hình nhiều nét – polylines, các đường giao nhau - cross. Trong thực tế mỗi một cross có thể là ngã ba, ngã tư, ngã năm,… Trong bài toán mỗi link là đường nối giữa hai cross với nhau. Một đường thì gồm nhiều link. Một Polygon cũng như một đường hay polyline có thể nằm trên nhiều cell khác nhau. 5.2.4 Lập trình Bài toán này chúng tôi đã sử dụng phần mềm eMbedded Visual C++ 3.0 để lập trình, các lớp của bản đồ được xây dựng thành các thư viện lớp riêng biệt. Ví dụ lớp cell, cross, polygon, polyline, line. Ví dụ lớp link được khai báo như sau: Mỗi một link có một chỉ số riêng để phân biệt link này với link kia. Ngoài ra với biến direct ta biết được link này là link một chiều hay hai chiều… Chúng ta khai báo một đường như sau: typedef class CLink { public: WORD fromCross; // điểm giao bắt đầu một link WORD toCross; //điểm giao kết thúc link BYTE direct; //chiều của link WORD numPoints; //số các điểm WORD streetIndex; //chỉ số link … }*LINKPTR; typedef class CStreet { public: WORD numLinks; //số link mà đường đi qua WORD* linkIndexs; //tập chỉ số link CString streetName; //tên đường … }* STREETPTR; 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 63 Còn bây giờ sau khi khai báo các lớp chúng ta cần có một số hàm như: void DrawLink(CDC*pDC,WORD linkIndex); //vẽ các link, CDC đặc trưng cho thiết bị phần cứng. void DrawStreet(CDC* pDC,CStreet*street); //vẽ đường void DrawMap(CDC * pDC); //vẽ bản đồ void DrawCell(CCell* cell,CDC *pDC, int left,int top,int right,int bottom,BOOL all); //vẽ các ô – cell. void DrawFullMap(CDC *pDC, int x,int y,int width,int height); //vẽ đầy bản đồ BOOL ZoomOut(int x,int y); //phóng to bản đồ BOOL ZoomIn(int x,int y); //thu nhỏ bản đồ BOOL MoveLeft(); //dịch chuyển bản đồ sang trái BOOL MoveRight(); //dịch chuyển bản đồ sang phải BOOL MoveUp(); //dịch chuyển bản đồ lên trên BOOL MoveDown(); //dịch chuyển bản đồ xuống dưới … Trên đây là một số hàm chức năng quan trọng của chương trình. Người đọc có thể xem thêm một số khai báo lớp, và định nghĩa hàm ở 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 64 5.2.5 Một số hình ảnh của chương trình Trong phần này xin giới thiệu một số hình ảnh của chương trình tìm đường đi trên PocketPC. Hình 5-7 Bản đồ số trên PocketPC 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 65 Hình 5-8 Kết quả tìm đường đi Đường đi ngắn nhất tìm đượ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 66 Hình 5-9 Hình ảnh bản đồ số phóng to 5.2.6 Đánh giá chương trình 5.2.6.1 Các điểm đã đạt được • Chương trình đã tìm ra đường đi ngắn nhất giữa 2 “điểm” • Có chỉ dẫn đường đi rõ dàng • Đường đi tìm được là có hướng 5.2.6.2 Các điểm chưa đạt được, hướng phát triển • Chương trình chưa tính điến nhiều yếu tố khác của đường đi như lưu lượng đường đi chẳng hạn • Chương trình sử dụng bản đồ số có sẵn và chưa kết hợp được với hệ thống GPS để có thể định vị và tìm đường đi trên toàn cầu!!! Đây cũng sẽ là hướng phát triển của chương trì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 67 Chương trình trong tương lai là một chương trình tìm đường trên Mobile Phone sử dụng kỹ thuật A-GPS kết hợp với một số kỹ thuật khác như Cell-ID, hay E-OTD để định vị trí và tìm đường đi. Người đọc có thể tìm hiểu thêm về điều này trong [5.1.3.2]. Để hiểu rõ tính năng của phương pháp kết hợp giữa A-GPS với E-OTD hay Cell-ID xin xem Bảng 5-2 Đặc tính phương pháp kết hợp Với những đặc tính của kỹ thuật A-GPS như trên thì ta có thể thấy để giải quyết bài toàn đặt ra: “tìm đường đi ngắn nhất” của chúng ta rất cần thiết sử dụng đến kỹ thuật này. Có thể nói mạnh dạn là kỹ thuật A-GPS là lựa chọn số một trong trường hợp nà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 68 CHƯƠNG 6 KẾT LUẬN Qua bài luận luận văn, tôi đã trình bày về bản đồ số, hệ thống GPS, và hệ thống thông tin di động. Mục tiêu chính của luận văn đó là giúp cho người đọc hiểu về các ứng dụng mạnh mẽ khi kết hợp công nghệ bản đồ số, hệ thống GPS và hệ thống di động Mobile ví dụ các ứng dụng LBS. Đồng thời tác giả cũng trình bầy cách tích hợp và giải bài toán tìm đường đi ngắn nhất. • Bản đồ số Bản đồ số sử dụng kỹ thuật vector để xây dựng. Với kỹ thuật này thì bản đồ số được phân ra các lớp khác nhau. Bao gồm: Điểm, Đường, Vùng. Các điểm trên bản đồ số có thể là: ngôi nhà, trường học… Các đường trên bản đồ số có thể là: đường đi trên mặt đất Các vùng trên bản đồ số có thể là: sông, hồ, biên giới quốc gia… • Hệ thống GPS Là hệ thống định vị toàn cầu lớn nhất hiện nay do Mỹ xây dựng và duy trì. Hệ thống GPS có thể định vị bất kì một điểm nào trên mặt đất, tại bất kì thời điểm nào với độ chính xác rất cao. GPS gồm 28 vệ tinh, chúng liên tục truyền tín hiệu vệ tinh về trái đất và các trạm điều khiển mặt đất thu tín hiệu, xử lí và truyền tín hiệu điều khiển lại cho các vệ tinh. Không chỉ các tram điểu khiển mặt đất thu được tín hiệu GPS mà bất kì một máy thu GPS nào cũng có thể thu được. Và đương nhiên là với một chiếc máy thu GPS trong tay ta có thể đi lại thoải mái mà không sợ bị lạc, khi nó đã giúp ta tìm ra đường đi hợp lý! • Hệ thống thông tin di động Trải qua các thời kì phát triển của mình 1G, 2G, 3G và giờ đang hứa hẹn thời kì 4G, thì hệ thống thông tin di động đã đóng một vai trò cực kì quan trọng trong việc thông tin liên lạc trên thế giới.Từ các kỹ thuật thông tin dựa trên tín hiệu analog - tương tự đến kỹ thuật digital - số, kỹ thuật đa truy nhập như TDMA, CDMA,… thì hệ thống thông tin di động ngày càng hoàn thiện và phát triển lên một tầm cao mới! Và nó khiến cho cuộc sống của chúng ta gắn bó ngày càng chặt chẽ hơn với chiếc điện thoại di động, bởi các dịch vụ tiện ích cài đặt trên nó. • Bài toái 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 69 Đây là bài toán tìm đường đi ngắn nhất trên PocketPC, bài toán đã áp dụng thuật toán Dijkstra để tìm đường đi ngắn nhất. Đường đi ngắn nhất tìm thấy được hiện thị trên bản đồ số - xây dựng dựa trên kĩ thuật vector. Bài toán này mở ra hướng phát triển bài toán tìm đường đi ngắn nhất trên điện thoại di động trong đó có sự kết hợp giữa bản đồ số với hệ thống định vị 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 70 PHỤ LỤC 1: Niên biểu phát triển của hệ thống GPS 2: Một số vệ tinh GPS 3: Hệ thống điện thoại di động vùng Bắc Âu (NMT) 4: Hệ thống viễn thông di động toàn cầu (UMTS) 5: Kỹ thuật E-OTD 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 71 1. Niên biểu phát triển của hệ thống GPS Niên biểu lịch sử phát triển hệ thống GPS Thời gian Sự kiện Thập niên 1920s Ra đời hệ thống dẫn đường vô tuyến Đầu Đại chiến thế giới 2 LORAN, hệ thống dẫn đường áp dụng phương pháp đo độ lệch thời gian của tín hiệu sóng vô tuyến, do Phòng thí nghiệm Bức xạ Đại học MIT (MIT Radiation Laboratory). LORAN cũng là hệ thống định vị trong mọi điều kiện thời tiết đầu tiên, nhưng là hai chiều (vĩ độ và kinh độ). 1957 Đại học MIT cho rằng tín hiệu vô tuyến điện của vệ tinh có thể tăng lên khi chúng tiếp cận trái đất và giảm đi khi rời khỏ trái đất và do vậy có thể truy theo vị trí từ mặt đất 1959 TRANSIT, hệ thống dẫn đường dựa trên vệ tinh hoạt động đầu tiên, do Phòng thí nghiệm vật lý ứng dụng Johns Hopkins phát triển dưới sự chỉ đạo của TS Richard Kirschner. Mặc dù khởi đầu Transit được chế tạo để hỗ trợ cho đội tàu ngầm của Mỹ nhưng những công nghệ này đã được phát triển có ích trở thành Hệ thống định vị toàn cầu. Vệ tinh Transit đầu tiên được phóng lên vũ trụ vào năm 1959. 1960 Hệ thống dẫn đường đo hiệu thời gian ba chiều (kinh độ, vị độ và độ cao longitude, latitude and altitude) đầu tiên do Raytheon Corporation đề xuất theo yêu cầu của Air Force để làm hệ thống dẫn đường sẽ được sử dụng với (with a proposed ICBM) có thể đạt tới độ lưu động bằng chạy trên một 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 72 đường ray. Hệ thống dẫn đường được trình bày là MOSAIC (Mobile System for Accurate ICBM Control). Ý tưởng này bị đổ vỡ khi chương trình Mobile Minuteman bị hủy bỏ vào năm 1961 1963 Tổng công ty Aerospace Corporation thực hiện nghiên cứu về hệ thống không gian làm cơ sở cho hệ thốn dẫn đường cho phương tiện chuyển động nhanh theo ba chiều không gian. Việc nghiên cứu này trực tiếp dẫn tới khái niệm về hệ thống định vị toàn cầu. Khái niệm liên quan đến việc đo thời gian tới của tín hiệu sóng vô tuyến được phát đi từ vệ tinh có vị trí chính xác đã biết. Đo thời gian sẽ cho khoảng cách tới vị trí vệ tinh đã biết và lần lượt có thể xác định được vị trí của người sử dụng. 1963 Air Force bắt đầu hỗ trợ nghiên cứu của Aerospace, chỉ định nghiên cứu này bằng Dự án Hệ thống 621B. Khoảng năm 1972, chương trình này đã biểu diễn hoạt động của một loại tín hiệu xác định khoảng cách vệ tinh mới dựa trên tiếng ồn ngẫu nhiên giả tạo (PRN, pseudo random noise). 1964 Timation, hệ thống vệ tinh hải quân, được phát triển dưới sự chỉ đạo của Roger Easton ở Phòng nghiên cứu Hải quan (Naval Research Lab, NRL) để cải thiện đồng hồ có tính ổn định cao, khả năng truyền thời gian, và dẫn đường 2 chiều. Hoạt động của Timation theo tiêu chuẩn thời gian chuẩn vũ trụ đã cung cấp cơ sở quan trọng cho hệ thống định vị toàn cầu. Vệ tinh Timation đầu tiên được phóng lên vũ trụ vào tháng 5 năm 1967. 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 73 1968 Bộ Quốc phòng Mỹ (DoD, Department of Defence, USA) thành lập một ủy ban gọi là Ủy ban Thự hiện Vệ tinh Dẫn đường (NAVSEC, Navigation Satellite Executive Committee) để phối hợp nỗ lực của các nhóm dẫn đường vệ tinh (Transit của Hải quân, Chương trình Timation, và SECOR của Quân đội, hay còn gọi là Hệ thống đồng tương quan khoảng cách chuỗi (Sequential Correlation of Range System). NAVSEC ký hợp đồng một số nghiên cứu để làm sáng tỏ khái niệm dẫn đường vệ tinh cơ bản. Những nghiên cứu này về một số vấn đề chính xung quanh khái niệm như lựa chọn tần số sóng mang (dải L đối lập với dải C), thiết kế cấu trúc tín hiệu, và lựa chọn định hình quỹ đạo vệ tinh. 1969-1972 NAVSEC quản lý các thảo luận khái niệm giữa các nhóm dẫn đường vệ tinh khác nhau. APL Hải quân ủng hộ nhóm Transit mở rộng, trong khi NRL Hải quân ủng hộ cho Timation mở rộng, còn Air Force thì ủng hộ cho “chòm sao đồng bộ mở rộng”, tức dự án ‘Hệ thống 621B’. Tháng 4 năm 1973 Thứ trưởng Bộ Quốc phòng quyết định thiết lập một chương trình hợp tác ba dịch vụ để thống nhất những khái niệm khác nhau về định vị và dẫn đường thành một hệ thống Bộ quốc phòng hỗn hợp gọi là Hệ thống vệ tinh dẫn đường quốc phòng (Defense Navigation Satellite System). Air Force được chỉ định làm người quản lý (điều hành) chương trình. Hệ thống mới được phát triển qua văn phòng chương trình kết hợp (joint program office), với sự tham gia của tất cả quan chủng quố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 74 phòng. Đại tá Brad Parkinson được chỉ định làm người chỉ đạo văn phòng chương trình kết hợp và được đặt trọng trách phát triển kết hợp khái niệm ban đầu về hệ thống dẫn đường dựa trên không gian (space-based navigation system) Tháng 8 năm 1973 Hệ thống đầu tiên được trình bày tới Hội đồng Thu nhận và Thẩm định Hệ thống Quốc phòng (Defense System Acquisition and Review Council, DSARC) bị từ chối thông qua. Hệ thống được trình lên DSARC được gói gọn trong Hệ thống 621B của Air Fore và không đại diện cho chương trình kết hợp. Mặc dù có người ủng hộ ý tưởng của hệ thống dẫn đường dựa trên vệ tinh mới nhưng Văn phòng Chương trình Kết hợp đã được thúc đẩy khẩn trương tổng quát hóa khái niệm bao gồm xem xét và yêu cầu tất cả các binh chủng quốc phòng. 17/12/1973 Một khái niệm mới được trình tới DSARC và được thông qua để thực hiện và cấp kinh phí là hệ thống NAVSTAR GPS, đánh dấu khởi đầu công nhận khái niệm (ý tưởng) (Giai đoạn I của chương trình GPS). Khái niệm mới thực sự là một hệ thống dàn xếp (thỏa hiệp – compromise system) do Đại tá Parkinson thương lượng đã kết hợp tốt nhất giữa tất cả những khái niệm và công nghệ dẫn đường vệ tinh có sẵn. Cấu hình hệ thống được thông qua bao gồm 24 vệ tinh chuyển động trong những quỹ đạo nghiêng chu kỳ 12 giờ đồng hồ. Tháng 6 năm 1974 Hãng Rockwell International được chọn làm nhà cung cấp vệ tinh cho chương trình GPS. Ngày 14 tháng 7 năm 1974 Vệ tinh NAVSTAR đầu tiên được phóng lê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 75 vũ trụ. Vệ tinh này được chỉ định là Vệ tinh Công nghệ Dẫn đường (NTS) số 1, về cơ bản đây là vệ tịnh Timation tân trang lại do NRL đóng. Vệ tinh thứ hai (là vệ tinh cuối cùng) của nhóm NTS được phóng vào năm 1977. Những vệ tinh này được sử dụng cho việc đề xuất đánh giá khái niệm (ý tưởng) và thực hiện những đồng hồ nguyên tử đầu tiên đã được phóng vào trong không gian (vũ trụ). 1977 Thực hiện kiểm tra thiết bị người sử dụng ở Yuma, Arizona. 22/2/1978 Vệ tinh Block I đầu tiên được phóng. Toàn bộ 11 vệ tinh Block I được phóng trong khoảng thời gian 1978 và 1985 trên Atlas- Centaur. Những vệ tinh Block I do Rockwell International xây dựng được coi là những vệ tinh mẫu phát triển được dùng để kiểm tra hệ thống. Bị mất một vệ tinh do phóng trượt. 26/4/1980 Phóng vệ tinh GPS đầu tiên thực hiện những bộ cảm ứng Hệ thống phát hiện tiếng nổ hạt nhân hoạt động tổng hợp (Integrated Operational Nucluear Detonation Detection System (IONDS) sensors). 1982 Bộ Quốc phòng thông qua quyết định giảm số vệ tinh của chòm vệ tinh GPS từ 24 xuống 18 tiếp theo sau tái cấu tạo lại chương trình chính do Quyết định 1979 của Văn phòng Thư ký Bộ Quốc phòng gây ra để cắt giảm kinh phí 500 triệu đô la (khoảng 30%) từ ngân sách cho giai đoạn năm tài chính FY81- FY86. 14/7/1983 Phóng vệ tinh GPS đầu tiên thực hiện hệ thống dò tìm tiếng nổ hạt nhân (NDS) mới hơn 16/9/1983 Theo (the Soviet downing of Korean Air 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 76 flight 007), tổng thống Reagan hứa cho GPS được sử dụng cho các máy bay dân dụng hoàn toàn miễn phí khi hệ thống đưa vào sử dụng. Sự kiện này đánh dấu sự bắt đầu lan tỏa công nghệ GPS từ quân sự sang dân sự. Tháng tư 1985 Hợp đồng thiết bị người sử dụng chính đầu tiên được giao cho JPO. Hợp đồng bao gồm việc nghiên cứu, phát triển cũng như lựa chọn sản xuất các máy thu GPS dùng cho máy bay, tàu thủy và máy thu xách tay (gọn nhẹ). 1987 Bộ Quốc phòng chính thức yêu cầu Bộ Giao thông (Department of Transport, DoT) có trách nhiệm thiết lập và cung cấp một văn phòng đáp ứng nhu cầu người sử dụng dân sự về thông tin GPS, dữ liệu và hỗ trợ kỹ thuật. Tháng 2 năm 1989, Coast Guard có trách nhiệm làm đại lý hướng dẫn Dịch vụ GPS Dân sự (civil GPS service). 1984 Khảo sát trở thành một thị trường GPS thương mại đầu bảng được nâng cánh! Để bù cho số vệ tinh giới hạn có sẵn trong quá trình phát triển chòm vệ tinh, các nhà khảo sát đã chuyển qua số kỹ thuật nâng cao độ chính xác bao gồm kỹ thuật GPS Vi phân (DGPS) và kỹ thuật truy theo pha sóng mang (carrier phase tracking) 3/1988 Thư ký Air Force thông báo về việc mở rộng chòm GPS tới 21 vệ tinh cộng thêm 3 vệ tinh dự phòng 14/2/1989 Vệ tinh đầu tiên của các vệ tinh Block II đã được phóng từ Cape Canaveral AFT, Florida, trên dàn phóng Delta II (Delta II booster). Phi thuyền con thoi (Space Shuttle) làm bệ phóng theo kế hoạch cho các vệ tinh 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 77 Block II được Rockwell Intenational đóng. Tiếp theo tai nạn Challenger 1986, Văn phòng Chương trình Kết hợp (JPO) xem xét lại và đã sử dụng Delta II làm bệ phóng vệ tinh GPS. SA (Selective Availabity) và AS (Anti-spoofing. 21/6/1989 Hãng Martine Marietta (sau khi mua xong General Electric Astro Space Division vào năm 1992) được thắng hợp đồng xây dựng 20 vệ tinh bổ sung (Block IIR). Chiếc vệ tinh Block IIR đầu tiên sẵng sàng để phóng vào cuối năm 1996. 1990 Hãng Trimble Navigation, nhà sản xuất bán máy thu GPS hàng đầu thế giới được thành lập năm 1978 hoàn thành loạt sản phẩm ban đầu. 25/3/1990 DoD theo Kế hoạch Dẫn đường Vô tuyến Liên bang, lần đầu tiên khởi động (kích hoạt) SA (Selective Availability) làm giảm độ chính xác dẫn đường GPS có chủ định. 8/1990 SA được tắt đi trong chiến tranh vịnh Ba tư (Persian Gulf War). Những yếu tố đóng góp vào quyết định tắt SA bao gồm việc phủ sóng ba chiều có giới hạn được chòm NAVSTAR cung cấp trong quỹ đạo vào thời gian đó và sớ máy thu mã số chính xác (Precision (P)-code) trong bản kiểm kê của DoD. DoD đã mua hàng nghìn máy thu GPS dân dụng ngay sau đó không lâu đã dùng cho lực lượng liên minh trong cuộc chiến tranh. 1990-1991 GPS được các lực lượng liên minh dùng lần đầu tiên trong điều kiện chiến tranh trong Chiến tranh Vịnh Ba Tư. Sử dụng GPS cho Bão Sa Mạc Hoạt Động (Operation Desert Storm) chúng minh là cách sử dụng chiế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 78 thuật thành công đầu tiên của công nghệ không gian trong giới hạn thiết trí hoạt động. 29/8/1991 SA được kích hoạt lại sau Chiến tranh Vịnh Ba Tư. 1/7/1991 Mỹ đã cho phép cộng đồng thế giới sử dụng dịch vụ định vị tiêu chuẩn (SPS) GPS bắt đầu từ năm 1993 trên cơ sở liên tục và miển phí trong vòng ít nhất 10 năm. Lời đề nghị này được thông báo trong Hội nghị Dẫn đường Hàng không lần thứ 10 (the 10th Air Navigation Conference) của Tổ chức Hàng không Dân dụng Quốc tế (ICAO, International Civil Aviation Organization). 5/9/1991 Mỹ mở rộng lời đề nghị 1991 vào Hội nghị thường niên ICAO bằng cách cho phép thế giới sử dụng SPS trong tương lai, việc này phụ thuộc vào việc có đủ vốn, cung cấp dịch vụ này tối thiểu 6 năm có thông báo trước về việc chấm dứt hoạt động GPS hoặc xóa bỏ SPS. 8/12/1992 Bộ Trưởng Bộ Quốc phòng chính thức thông báo Khả năng hoạt động đầu tiên của GPS, có nghĩa là 24 vệ tinh trên quỹ đạo hệ thống GPS không còn là hệ thống đang triển khai nữa mà GPS đã có khả năng duy trì độ chính xác ở mức độ sai số 100 mét và có sẵn trên toàn cầu liên tục cho người sử dụng SPS như đã hứa. 17/2/1994 Người quản trị FAA David Hinson thông báo GPS là một hệ thống dẫn đường đầu tiên đã được thông qua để sử dựng làm phương tiện hỗ trợ dẫn đường độc lập cho tất cả các phương tiện bay thông qua tiếp cận không chính xác (nonprecision approach). 6/6/1994 Người quản trị FAA David Hinson 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 79 báo ngừng phát triển Hệ thống Hạ cánh Vi sóng (MLS) cho việc hạ cánh Loại II và III. 11/1994 Hãng Orbital Sciences, một nhà sản xuất tên lửa và vệ tinh hàng đầu thế giới đồng ý mua hãng Magellen Corp., một nhà sản xuất máy thu GPS cầm tay ở California bằng trao đổi chứng khoán trị giá 60 triệu đô la Mỹ, mang lại cho Orbital tiến gần tới mục tiêu trở thành công ty viển thông hai chiều dựa vào vệ tinh. 8/6/1994 Người quản trị FAA David Hinson thông báo thực hiện Hê thống Gia tăng Vùng rộng (WAAS, Wide Area Augmentation System) nhằm mục đích cải thiện tính hợp nhất GPS và tăng tính sẵn có cho người sử dụng dân sự trên tất cả các phương tiện bay. Giá chương trình theo dự tính mất 400-500 triệu đô la Mỹ. Chương trình này được lập kế hoạch thực hiện vào khoảng năm 1997. 11/10/1994 Ủy ban hành động dẫn đường định vị Bộ Giao thông (the Department of Transportation Positioning / Navigation Executive Committee) được thành lập để cung cấp diễn đàn qua đại lý nhằm thực hiện chính sách GPS. 14/10/1994 Người quản trị FAA David Hinson nhắc lại lời đề nghị (US’s offer) làm GPS-SPS có sẵn trong tương lai, dựa trên cơ sở liên tục và toàn cầu miễn phí cho người sử dụng trực tiếp trong thư gửi cho ICAO. 16/3/1995 Tổng thống Bil Clinton tái khẳng định rằng Mỹ cung cấp tín hiệu GPS cho cộng đồng người sử dụng dân dụng thế giới trong thư gửi cho ICAO Từ sau năm 1995 hệ thống GPS vẫn tiếp tục được duy trì và bảo dưỡng cũng như thay thế những vệ tinh già tuổi. Những vệ tinh thế hệ GPS-IIR đã và đang được phóng lê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 80 thay thế những vệ tinh già tuổi. Vệ tinh mới nhất được phóng lên ngày 16/9/2005 mang tên GPS-IIR-M1, là vệ tinh đầu tiên thuộc thế hệ 8 chiếc vệ tinh hiện đại nhất GPS-IIR- M. Theo kế hoạch, vệ tinh tiếp theo sẽ được phóng lên không gian vào tháng giêng năm nay (2006). 2. Một số vệ tinh GPS - Block IIA Hình 0-1 Vệ tinh Block IIA Mặc dù các vệ tinh bay trên 6 quĩ đạo khác nhau nhưng chúng cùng nghiêng một góc như nhau so với quĩ đạo, các vệ tinh Block IIA có một chút sự khác nhau trong vũ trụ. Vào năm 1990 vệ tinh Block IIA được đưa vào hoạt động. Vệ tinh Block IIA được xây dựng từ số 22 đến 40, tức là có 18 vệ tinh Block IIA. Các vệ tinh Block II/IIA thiết kế dựa trên mô hình Block I nhưng có sự cải tiến về dung lượng lưu trữ, chống sai sót, cải thiện độ chính xác và khả năng giảm bớt lỗi. Các vệ tinh Block IIA được thiết kế với 180 ngày hoạt động mà không cần sự giám sát của khối điều khiển trong hệ thống GPS. Và đương nhiên trong thời gian này độ giảm của tính chính xác là rõ ràng. Còn về thông số kỹ thuật thì Block IIA cũng tương tự như Block II. - Block IIR 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 81 Hình 0-2 Vệ tinh Block IIA Năm 1989 General Electric AstroSpace đã xây dựng 21 vệ tinh Block IIA( số vệ tinh từ 41 đến 62). Các vệ tinh này có thể hoạt động không cần sự kiểm soát của khối điều khiển trên mặt đất từ 14 đến 180 ngày. - Block IIF Hình 0-3 Vệ tinh Block IIF Đây là loại vệ tinh thứ tư thuộc nhóm các vệ tinh sô II, Block IIF đưa vào hoạt động để phục vụ cả quân sự và người dân thường. Boeing có khả năng sẽ sản xuất 16 vệ tinh loại này, trong đó 6 cái đã được đặt hàng bởi lực lượng không quân của Mỹ và dự kiến sẽ đưa chúng lên quĩ đạo vào giữa năm nay(2006). 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 82 Chúng ta có thể tham khảo một số tính năng kỹ thuật của loại vệ tinh này: Bảng 0-1 Thông số kỹ thuật vệ tinh Block IIF Block IIF Tần số 1572.42 MHz and 1227.6 MHz (dải L) 2227.5 MHz (dải S) Nhà cung cấp Boeing Khối lượng ? kg Tuổi thọ 15 năm Điện năng tiêu thụ 2,440 kw Pin 3 – 35 cell Ah NiCd Cao x Rộng x Dài 244 x 197 x 197 cm 3. Hệ thống điện thoại di động vùng Bắc Âu (NMT) Vào ngày 1/10/1981, Hệ thống Điện thoại Di động Bắc Âu NMT450 trở thành hệ thống truyền thông di động mạng tế bào châu Âu đầu tiên được mở dịch vụ (theo [MAC- 93]). Hệ thống này thủa đầu được phát triển để cung cấp các tiện ích truyền thông di động tới các vùng nông thôn và thưa dân cư tại các nước thuộc xứ Scandinavi, như Đan Mạch, Na Uy, Phần Lan, và Thuỵ Điển. NM450 được phát triển chú trọng đến các máy điện thoại trên xe hơi và xách tay. Nhờ việc áp dụng các chuẩn chung và những tần số hoạt động, roaming giữa các quốc gia thuộc xứ Scandinavi này trở nên dễ dàng. Đặc biệt, sự ra mắt của loại công nghệ mới này đã tạo cho các nhà vận hành và phân phối mạng sự đi đầu về thị trường; một trong số đó còn được coi như vẫn còn đang phát triển mạch mẽ đến ngày nay. Do gần tương đương với những hệ thống thuộc thế hệ thứ nhất (1G), NMT450 là một hệ thống kỹ thuật analog. Hệ thống này hoạt động trên băng tần 450 MHz, cụ thể 453÷457,5 MHz từ mobile đến BS và 463÷467,5 MHz từ BS đến mobile. FDMA/FM được sử dụng làm phương thức đa truy nhập và phương thức điều chế cho tín hiệu âm thanh với khoảng dịch tần lớn nhất là ±5 kHz. Khoá mã dịch tần (FSK) được sử dụng để điều chế tín hiệu điều khiển với một khoảng dịch tần là ±3,5 kHz. NMT450 hoạt động sử dụng một khoảng phân cách kênh là 25 kHz, cho phép hỗ trợ tới 180 kênh. Kể từ khi có sự ra đời, hệ thống NMT450 đã liên tục tiến triển cùng với sự phát triển của các hệ thống NMT450i (chữ “i” có nghĩa là cải tiến) và NMT900. NMT900 được khai trương thành dịch vụ vào năm 1986, vào cùng khoảng thời gian các quốc gia Tây Âu khác đang bắt đầu cho ra mắt các giải pháp dựa vào mạng tế bào di động thành phố của chính mì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 83 NMT900 được xây dựng để đáp ứng nhu cầu sử dụng trong thành phố, phục vụ cho các thiết bị kết cuối cầm tay và xách tay. Hệ thống này hoạt động trên băng tần 900MHz với khả năng phù hợp với tốc độ dữ liệu cao và nhiều kênh. Hệ thống NMT vẫn tiếp tục nắm giữ một thị phần quan trọng trên toàn cầu và đặc biệt, hệ thống này tiếp tục tiến triển qua một loạt các chương trình nâng cấp có hoặch định. Ở châu Âu, họ NMT có một thị phần rất lớn trong các quốc gia Đông Âu, nơi mà điện thoại di động ngày nay chỉ mới đang bắt đầu trở nên thịnh hành. Giai đoạn tiếp theo trong sự phát triển của mạng NMT450 như được khởi xướng bởi NMT MoU là số hoá tiêu chuẩn. Điều này được coi như một bước tiến hoá quan trọng và cần thiết trên quan điểm cạnh tranh từ các mạng Mobile thế hệ 2G đang tồn tại và các thế hệ trong tương lai. Điều này sẽ đạt được qua sự nhập cuộc của mạng GSM, và sẽ được gọi là GSM400. Khả năng để cung cấp các mạng điện thoại GSM băng ghép để hỗ trợ việc roaming toàn cầu được xem như là khá hấp dẫn. Tiến tới những tháng cuối năm 1999, Nokia và Ericsson hội nhập để thử nghiệm cuộc gọi đầu tiên tạo ra trên một máy điện thoại di động nguyên bản GSM400/1800 song mốt. Kể từ năm 1981, các nước Bắc Âu đã liên tục dẫn đầu trên tổng số 60% dân số hiện nay ở Phần Lan và Na Uy cùng có máy điện thoại di động. Hai công ty thuộc nhóm Scandinavi, Nokia và Ericsson, là những người dẫn đầu thế giới về công nghệ điện thoại di động và cả hai đều đang đẩy mạnh sự tiến triển của loại điện thoại này. 4. Hệ thống viễn thông di động toàn cầu (UMTS) UMTS là hệ thống 3G của châu Âu và sẽ là một thành phần trong họ của các giao diện sóng radio mà sẽ hình thành nên IMT-2000, hoạt động trên các băng tần phân cấp cho FPLMTS tại WARC 92 và cho IMT-2000 tại WRC 2000. Giống như IMT-2000, UMTS sẽ bao gồm cả hai thành phần vệ tinh và mặt đất. Ngay năm 1988, cuộc nghiên cứu về UMTS đã bắt đầu là một phần của cuộc nghiên cứu của EU và chương trình Phát triển về Truyền thông Tiên tiến ở Châu Âu (RACE) (theo [DAS-95]). Thực tế cho thấy, EU đã tiếp tục đóng một vai trò nổi bật trong việc hỗ trợ cuộc nghiên cứu và phát triển xuyên suốt những năm của thập kỷ 1990, đáng ghi nhận là thông qua chương trình các công nghệ truyền thông tiên tiến và các dịch vụ (ACTS) trong những năm 1994 đến 1998 và chương trình các công nghệ xã hội thông tin (IST) trong những năm 1998 đến 2002. Thông qua những bước đầu này, một nền văn hoá của sự hợp tác quốc tế giữa các nhà sản xuất, khai thác, các nhà cung cấp dịch vụ, các chuyên gia thành lập cuộc nghiên cứu và các trường đại học đã được tạo lập một cách thành công. Chắc chắn, chương trình ACTS trong 4 năm này đã đóng một vai trò nổi trội trong việc phát triển và chuẩn hoá các công nghệ UMTS, cá biệt, trong những lĩnh vự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 84 của giao diện sóng radio và các công nghệ mạng. Kẻ đi theo sau nó, chương trình IST, hứa hẹn tiếp tục với sự thành công của các tiền lề nghiên cứu trước đó. Một sự phát triển quan trọng trong việc thiết lập UMTS diễn ra năm 1996, khi một hội gồm các nhà vận hành khai thác viễn thông, nhà sản xuất, và các nhà kiểm soát gộp vào nhau tạo nên Diễn đàn UMTS. Diễn đàn này được thành lập nhằm để xúc tiến và đẩy mạnh sự phát triển của UMTS thông qua sự xác nhận của các hoạt động chính sách cần thiết và các chuẩn. Để đạt được mục tiêu này, diễn đàn vạch ra bốn nhóm làm việc, đó là: Nhóm có xu hướng về thị trường; nhóm có xu hướng về kiểm soát; Nhóm có xu hướng về phổ tần; và nhóm có xu hướng về thiết bị đầu cuối. Kết quả hoạt động của bốn nhóm này cho thấy rằng, một vài báo cáo đã được đưa ra giải quyết với những vấn đề bao gồm những yêu cầu về quang phổ của UMTS, thị trường tiềm ẩn, và các điều kiện cấp phép (theo [UMT-97, UMT-98a, UMT-99b, UMT-99c, UMT-00a, UMT-00b, UMT-00C, và UMT-01]). Thoạt đầu, người ta có ý định thực hiện thành lập UMTS cho đến cuối thế kỷ 20. Tuy nhiên, nó đã được kiểm duyệt lại cho tới năm 2002. Giống như GSM, thời kỳ đầu, UMTS được người ta ra ý định thiết kế hoàn toàn từ vạch xuất phát. Phương hướng này làm việc với GSM do tại thời điểm thiết kế, có một nhu cầu cần có một hệ thống cải cách mới, có nghĩa rằng, việc thực hiện một dịch vụ kỹ thuật số xuyên lục địa. Tuy nhiên, đến quãng thời gian mà UMTS được đặt mục tiêu cho việc thực hiện các dịch vụ kiểu GSM, chắc sẽ đã có mặt cho một khoảng thời gian đáng kể và sẽ đạt được mức độ chiếm lĩnh thị trường đáng kể. Thực ra, người ta liệu trước rằng, GSM sẽ tiếp tục nắm giữ phần lớn lĩnh vực truyền thoại và lưu lượng tốc độ dữ liệu thấp trong ít năm đầu sau sự ra mắt của UMTS. Thực tế thì thấy, UMTS sẽ cải tiến từ các mạng GSM và ISDN. Con đường di chuyển từ GSM sang UMTS, có thể coi là G-UMTS, là tiêu điểm trong giai đoạn đầu của công cuộc thực hiện UMTS của 3GPP. 3GPP được hình thành vào năm 1998 với mục đích cung cấp toàn cầu những chỉ tiêu kỹ thuật ứng dụng cho một hệ thống mobile 3G. Những chỉ tiêu kỹ thuật này được dựa trên một CN của GSM cải tiến và UTRA (theo [HUB-00]). Nhìn chung, UMTS phải làm theo hai chức năng sau: 1. Hỗ trợ tất các dịch vụ, phương tiện và các ứng dụng đó hiện đang được cung cấp bởi các hệ thống 2G đang tồn tại và, càng đi xa hơn càng tốt, thuộc một QoS tương đương với của mạng cố định; và 2. Cung cấp một loạt các dịch vụ kiểu đa phương tiện băng rộng. Những dịch vụ này sẽ có mặt phổ biến với tốc độ bit trong khoảng từ 64 đến 2048 kb/s, cung cấp việc truyền hình ảnh, truy nhập cơ sở dữ liệu từ xa, truyền fax độ nhậy cao, video phân giải thấp, truy nhập trang Web... Cả hai loại dịch vụ chuyển mạch kênh và chuyển mạch gói sẽ được hỗ 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 85 trợ bởi UMTS. Một số dịch vụ sẽ bắt buộc phải có nhu cầu về băng thông theo yêu cầu, đó là phân cấp băng thông động tới người sử dụng phía cuối khi cần thiết. 5. Kỹ thuật E-OTD E-OTD (Enhanced Observed Time Difference) Người ta chỉ dùng E-OTD trong mạng GSM/ GPRS. Trong mạng này MS giám sát các cụm truyền từ các BTS lân cận và đo độ lệch thời gian các khung từ các BTS này làm cơ sở của phương pháp xác định vị trí. Độ chính xác của phương pháp E-OTD phụ thuộc vào độ phân giải của phép đo độ lệch thời gian, vị trí địa lý đặt các BTS lân cận và môi trường truyền sóng. MS phải đo thời gian chênh lệch từ ít nhất ba BTS để hỗ trợ xác định được vị trí của MS. Hình 0-4 Nguyên lý hoạt động của E-OTD Với phương pháp E-OTD, thời gian chính xác là tham số hết sức quan trọng để xác định vị trí của MS, vì vậy trong mạng GSM/GPRS yêu cầu có thêm các phần tử LMU (Location Measurement Unit) với tỷ lệ 1,5 BTS cần có 1 LMU. Như vậy, việc đưa thêm phần tử mới LMU vào mạng làm cấu trúc mạng thay đổi đáng kể. Để cung cấp dịch vụ này ở diện rộng cần lắp đặt rất nhiều LMU cho các BTS của mạng, điều này yêu cầu các kỹ sư phải định cỡ mạng, đánh giá ảnh hưởng tới phần vô tuyến khi lắp thêm các phần tử này. Ngoài ra, MS cũng cần nâng cấp về phần mềm để hỗ trợ cho E-OTD và khách hàng phải mang máy của mình đến các trung tâm để cập nhật phần mềm này. Hơn nữa, MS sẽ gặp phải vấn đề khi họ roaming sang mạng của nhà khai thác khác mà mạng này không cài đặt các phần tử LMU. 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 86 E-OTD là giải pháp cải thiện được các chỉ tiêu so với cell-ID, tuy nhiên lại yêu cầu rất nhiều LMU. Điều này có nghĩa là làm tăng chi phí, khó thực hiện... Ngoài ra, E- TOD yêu cầu có được thông tin từ ít nhất 3BTS do đó phương pháp này sẽ cho độ chính xác kém ở những vùng mật độ BTS thưa, hoặc trong trường hợp các BTS thẳng hàng (dọc các đường quốc lộ,..). 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 • Khai báo lớp //Khai báo lớp cell typedef class CCell { public: WORD numIndexs; BYTE numLayers; WORD * indexs; WORD * layers; CCell** subCells; CCell(CMapStream & stream,WORD numLayers,BYTE flag); virtual ~CCell(); } *CELLPTR; //khai báo lớp cross typedef class CCross { public: BYTE numLinks; WORD* linkIndexs; BYTE* atFroms; WORD x; WORD y; CCross(); CCross(CMapStream &stream); virtual ~CCross(); 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 87 } * CROSSPTR; • Định nghĩa hàm //Định nghĩa hàm vẽ đường void CMap::DrawStreet(CDC* pDC,CStreet *street) { for(int j = 0;jnumLinks;j++){ CLink* link = links[street->linkIndexs[j]]; CCross* fromCross = crosses[link->fromCross]; int fx = RealX2Screen(fromCross->x); int fy = RealY2Screen(fromCross->y); pDC->MoveTo(fx,fy); for(int k = 0;knumPoints;k++){ MAPPOINT p = link->points[k]; fx = RealX2Screen(p.x); fy = RealY2Screen(p.y); pDC->LineTo(fx,fy); } CCross* toCross = crosses[link->toCross]; fx = RealX2Screen(toCross->x); fy = RealY2Screen(toCross->y); pDC->LineTo(fx,fy); } } //định nghĩa hàm vẽ cell void CMap::DrawCell(CCell* cell,CDC *pDC,int l,int t,int r,int b,BOOL all){ if(cell != NULL){ if(cell->subCells != NULL){ BOOL draw = all; if(!all){ if(l>=left && r= top && b<=bottom){ draw = true; all = true; } else { 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 88 draw = !((l < left && r < left)|| (l > right && r > right)|| (t < top && b < top)|| (t > bottom && b > bottom)); } } if(draw){ int mx = (l+r)>>1; int my = (t+b)>>1; DrawCell(cell->subCells[0],pDC,l,t,mx,my,all); DrawCell(cell->subCells[1],pDC,mx,t,r,my,all); DrawCell(cell->subCells[2],pDC,l,my,mx,b,all); DrawCell(cell->subCells[3],pDC,mx,my,r,b,all); } } else { boolean draw = all; if(!all){ if(l>=left && r= top && b<=bottom){ draw = true; } else { draw = !((l < left && r < left)|| (l > right && r > right)|| (t < top && b < top)|| (t > bottom && b > bottom)); } } if(draw){ for(int i = cell->layers[0];ilayers[1];i++){ int index = cell->indexs[i]; if(mask[index]&POLYGON_MASK) continue; mask[index]|=POLYGON_MASK; CPoly * poly = polygons[index]; POINT* points = Poly2PointPtr(poly,-left,-top,shift); if(points!= NULL){ CBrush brush(poly->color&0xF0F0F0); 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 89 CPen pen(BS_SOLID,1,poly->color); CBrush * oldBrush = pDC- >SelectObject(&brush); CPen *oldPen = pDC->SelectObject(&pen); pDC->Polygon(points,poly->numPoints); pDC->SelectObject(oldBrush); pDC->SelectObject(oldPen); delete[] points; } } for(i = cell->layers[1];ilayers[2];i++){ int index = cell->indexs[i]; if(mask[index]&POLYLINE_MASK) continue; mask[index]|=POLYLINE_MASK; CPoly * poly = polylines[index]; POINT* points = Poly2PointPtr(poly,-left,-top,shift); if(points != NULL){ CPen pen(BS_SOLID,1,poly->color); CPen *oldPen = pDC->SelectObject(&pen); pDC->Polyline(points,poly->numPoints); pDC->SelectObject(oldPen); delete[] points; } } CPen p(BS_SOLID,nStreetWidth,STREET_COLOR); CPen *oldPen = pDC->SelectObject(&p); int n = (int)cell->layers[0]* nPaintedScale/nSqrMaxShift; for(i = 0;i<n;i++){ int streetIndex = cell->indexs[i]; if(mask[streetIndex]&STREET_MASK) continue; mask[streetIndex]|=STREET_MASK; CStreet* street = streets[streetIndex]; for(int j = 0;jnumLinks;j++){ CLink* link = links[street->linkIndexs[j]]; 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 90 CCross* fromCross = crosses[link- >fromCross]; int fx = RealX2Screen(fromCross->x); int fy = RealY2Screen(fromCross->y); pDC->MoveTo(fx,fy); draw = fx>=0&&fx=0&& fy<height; for(int k = 0;knumPoints;k++){ MAPPOINT p = link->points[k]; fx = RealX2Screen(p.x); fy = RealY2Screen(p.y); BOOL dr = fx>=0&&fx<width && fy>=0&& fy<height; if(dr || draw){ pDC->LineTo(fx,fy); } draw = dr; } CCross* toCross = crosses[link->toCross]; fx = RealX2Screen(toCross->x); fy = RealY2Screen(toCross->y); BOOL dr = fx>=0&&fx=0&& fy<=height; if(draw||dr){ pDC->LineTo(fx,fy); } } } pDC->SelectObject(oldPen); } } } } 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 91 TÀI LIỆU THAM KHẢO 1. Introduction to Digital Map Data, EDINA Digimap Training Session 2. ESRI Shapefile Technical Description, ESRI White Paper Environmental Systems Research Institute, Inc. 3. Introduction to GPS, Chris Rizos, University of New South Wales, 1999© 4. Global positioning SYSTEM - Hệ thống định vị toàn cầu, Nguyễn Thanh Việt 5. Lịch sử hệ thống định vị toàn cầu Vietsciences- Nguyễn Đức Hùng 6. Công nghệ CDMA. SupportVietnam 7. Dịch vụ dựa trên vị trí thuê bao cho mạng GSM/GPRS, KS. Trần Anh Tú, TS. Chu Ngọc Anh, KS. Lương Lý, KS.Bùi Văn Phú