Luận văn Nghiên cứu phát triển hệ thống dịch vụ dựa trên vị trí địa lý và thử nghiệm

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM NGỌC HƯNG NGHIÊN CỨU PHÁT TRIỂN HỆ THỐNG DỊCH VỤ DỰA TRÊN VỊ TRÍ ĐỊA LÝ VÀ THỬ NGHIỆM LUẬN VĂN THẠC SỸ Hà Nội – 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM NGỌC HƯNG NGHIÊN CỨU PHÁT TRIỂN HỆ THỐNG DỊCH VỤ DỰA TRÊN VỊ TRÍ ĐỊA LÝ VÀ THỬ NGHIỆM Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. ĐẶNG VĂN ĐỨC Hà Nội – 2009 LỜI CẢM ƠN Trước tiên tôi xin chân thành cảm ơn PGS.TS. Đặng Văn Đức, Viện Công nghệ thông tin, Viện Khoa học và Công nghệ Việt Nam, người đã định hướng và tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Tôi xin chân thành cảm ơn các thầy cô giáo khoa Công nghệ Thông tin, trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, những người đã tận tình truyền đạt các kiến thức, quan tâm, động viên trong suốt thời gian tôi học tập và nghiên cứu tại Trường. Nhân đây cho phép tôi gửi lời cảm ơn tới nhóm các bạn học cùng lớp K14T1, lớp chuyên ngành Hệ thống thông tin, các bạn đồng nghiệp đã thường xuyên quan tâm, giúp đỡ, chia sẻ kinh nghiệm, cung cấp các tài liệu hữu ích trong thời gian tôi học tập, nghiên cứu tại Trường cũng như trong trong quá trình thực hiện luận văn tốt nghiệp vừa qua. Cuối cùng tôi xin bảy tỏ sự biết ơn sâu sắc đến cha mẹ, những người thân trong gia đình đã luôn ở bên tôi, động viên, chia sẻ và dành cho tôi những gì tốt đẹp nhất trong suốt thời gian tôi học cao học cũng như trong thời gian tôi thực hiện luận văn tốt nghiệp này. Hà Nội, tháng 12 năm 2009 Phạm Ngọc Hưng - ii - LỜI CAM ĐOAN Tôi xin cam đoan bản luận văn “Nghiên cứu phát triển hệ thống dịch vụ dựa trên vị trí địa lý và thử nghiệm” là công trình nghiên cứu của tôi dưới sự hướng dẫn khoa học của PGS.TS. Đặng Văn Đức, tham khảo các nguồn tài liệu đã được chỉ rõ trong trích dẫn và danh mục tài liệu tham khảo. Các nội dung công bố và kết quả trình bày trong luận văn này là trung thực và chưa từng được ai công bố trong bất cứ công trình nào. Hà Nội, tháng 12 năm 2009 Phạm Ngọc Hưng - iii - MỤC LỤC LỜI CẢM ƠN ........................................................................................... i LỜI CAM ĐOAN .................................................................................... ii MỤC LỤC .............................................................................................. iii DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ ........................... vi DANH SÁCH BẢNG BIỂU .................................................................. vii DANH MỤC CÁC HÌNH VẼ ............................................................... viii MỞ ĐẦU ................................................................................................. 1 Chương 1: TỔNG QUAN VỀ LBS .......................................................... 3 1.1. Giới thiệu chung về LBS ........................................................... 3 1.2. Các thành phần của LBS............................................................ 5 1.3. Các kiểu dịch vụ LBS ................................................................ 6 1.4. Xử lý các yêu cầu của LBS ........................................................ 6 1.5. Các thiết bị di động.................................................................... 8 1.5.1. Các loại thiết bị...................................................................... 8 1.5.2. Các hạn chế của thiết bị ......................................................... 9 1.6. Mạng thông tin di động không dây .......................................... 10 1.6.1. Mạng không dây diện rộng .................................................. 10 1.6.2. Mạng không dây cục bộ ....................................................... 11 1.6.3. Mạng không dây cá nhân ..................................................... 12 1.7. Hệ thống định vị ...................................................................... 14 1.7.1. Giới thiệu chung .................................................................. 14 1.7.2. Hệ thống định vị toàn cầu GPS ............................................ 16 1.8. Các mô hình dịch vụ LBS........................................................ 21 1.9. Giới thiệu một số ứng dụng dựa trên LBS................................ 22 Chương 2: ỨNG DỤNG LOGIC MỜ TRONG TÌM ĐƯỜNG............... 24 2.1. Giới thiệu Logic mờ................................................................. 24 2.1.1. Nhắc lại về tập hợp kinh điển............................................... 25 - iv - 2.1.2. Khái niệm chung về tập mờ ................................................. 25 2.1.3. Các phép toán trên tập mờ ................................................... 27 2.2. Các thuật toán tìm đường......................................................... 27 2.3. Ứng dụng logic mờ trong bài toán tìm đường .......................... 36 Chương 3: THIẾT KẾ DỊCH VỤ LBS................................................... 38 3.1. Mục tiêu thiết kế ...................................................................... 38 3.2. Các mô hình dịch vụ thiết kế.................................................... 38 3.2.1. Mô hình triển khai trên nền dịch vụ web.............................. 38 3.2.2. Mô hình triển khai dựa trên dịch vụ SMS ............................ 40 3.2.3. Mô hình kết hợp dịch vụ web và SMS ................................. 42 3.3. Dịch vụ tìm đường đi trong thành phố ..................................... 44 3.3.1. Mục tiêu............................................................................... 44 3.3.2. Kiến trúc tổng quan của hệ thống......................................... 44 3.3.3. Phần cứng hệ thống.............................................................. 46 3.3.4. Cơ sở hạ tầng mạng truyền thông......................................... 46 3.3.5. Định vị................................................................................. 47 3.3.6. Cơ sở dữ liệu GIS ................................................................ 47 3.3.7. Các kiểu dịch vụ và cách khai thác ...................................... 47 3.3.8. Vấn đề cập nhật tình trạng hệ thống giao thông ................... 53 Chương 4: CÀI ĐẶT THỬ NGHIỆM .................................................... 54 4.1. Lựa chọn mô hình cài đặt......................................................... 54 4.1.1. Mô hình dịch vụ................................................................... 54 4.1.2. Phần cứng ............................................................................ 55 4.2. Lựa chọn công nghệ................................................................. 55 4.2.1. Xử lý dữ liệu bản đồ số bằng MapInfo................................. 55 4.2.2. Công cụ lập trình ................................................................. 57 4.2.3. Cài đặt ứng dụng desktop và web với MapXtreme............... 58 4.2.4. Giao tiếp GSM Modem bằng tập lệnh AT............................ 60 4.3. Định dạng gói tin SMS sử dụng để giao tiếp trong hệ thống .... 64 4.3.1. Máy khách cài đặt phần mềm............................................... 64 - v - 4.3.2. Máy khách chỉ sử dụng tin nhắn SMS.................................. 66 4.4. Xử lý tìm đường tại máy chủ ................................................... 68 4.4.1. Thuật toán tìm đường........................................................... 69 4.4.2. Xử lý phần dữ liệu “mờ” trong đồ thị................................... 70 4.4.3. Xử lý kết quả trả lại máy khách ........................................... 70 4.5. Giao diện của hệ thống ............................................................ 71 4.5.1. Giao diện phía máy chủ ....................................................... 71 4.5.2. Giao diện phía máy khách.................................................... 72 KẾT LUẬN............................................................................................ 77 TÀI LIỆU THAM KHẢO ...................................................................... 79 - vi - DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ CSDL Cơ sở dữ liệu GIS Hệ thống thông tin địa lý (Geographic Information Systems) GPS Hệ thống định vị toàn cầu (Global Positioning System) GPRS Dịch vụ vô tuyến gói chung (General Packet Radio Service) GSM Hệ thống thông tin di động toàn cầu (Global System for Mobile Communications) LBS Dịch vụ dựa trên vị trí địa lý (Location-based Service) WLAN Mạng không dây cục bộ (Wireless Local Area Networks) WPAN Mạng không dây cá nhân (Wireless Personal Area Networks) WWAN Mạng không dây diện rộng (Wireless Wide Area Network) SMS Dịch vụ tin nhắn ngắn (Short Message Services) - vii - DANH SÁCH BẢNG BIỂU Bảng 1.1: Đặc điểm và sự khác nhau giữa các công nghệ mạng không dây ..... 13 Bảng 4.1: Tập lệnh AT xử lý tin nhắn (SMS), chế độ văn PDU ....................... 60 Bảng 4.2: Tập lệnh AT điều khiển cuộc gọi..................................................... 61 Bảng 4.3: Tập lệnh AT điều khiển Card........................................................... 61 Bảng 4.4: Tập lệnh AT điều khiển máy điện thoại ........................................... 61 Bảng 4.5: Tập lệnh AT xử lý tin nhắn (SMS), chế độ văn bản ......................... 62 - viii - DANH MỤC CÁC HÌNH VẼ Hình 1.1: LBS là phần giao của các công nghệ.................................................. 4 Hình 1.2: Các thành phần cơ bản của LBS ........................................................ 5 Hình 1.3: Luồng thông tin giữa các thành phần của LBS................................... 7 Hình 1.4: Hình ảnh minh họa các thiết bị di động dùng trong LBS.................... 9 Hình 1.5: Phân loại mạng không dây di động .................................................. 10 Hình 1.6: Mạng không dây diện rộng (WWAN).............................................. 11 Hình 1.7: Mạng không dây cục bộ (WLAN).................................................... 12 Hình 1.8: Mạng không dây cá nhân (WPAN) .................................................. 13 Hình 1.9: Định vị dựa trên mạng truyền thông................................................. 14 Hình 1.10: Định vị dựa trên thiết bị đầu cuối................................................... 15 Hình 1.11: Các phần của hệ thống GPS [6] ..................................................... 18 Hình 1.12: Quỹ đạo các vệ tinh của hệ thống GPS [6] ..................................... 19 Hình 1.13: Minh hoạ dịch vụ dẫn đường ......................................................... 22 Hình 1.14: Minh hoạ dịch vụ quản lý, theo dõi và giám sát ............................. 23 Hình 2.1: Minh hoạ phép toán hợp trên tập mờ ............................................... 27 Hình 2.2: Minh hoạ phép toán giao trên tập mờ............................................... 27 Hình 2.3: Đồ thị mờ G minh hoạ thuật toán FSA............................................. 36 Hình 2.4: Các đường đi mờ ngắn nhất của đồ thị mờ G ................................... 37 Hình 3.1: Mô hình dịch vụ LBS trên nền Web................................................. 39 Hình 3.2: Mô hình dịch vụ LBS trên dịch vụ tin nhắn SMS............................. 41 Hình 3.3: Mô hình dịch vụ LBS trên nền Web và SMS ................................... 43 Hình 3.4: Kiến trúc tổng quan hệ thống cung cấp dịch vụ tìm đường .............. 45 Hình 3.5: Minh hoạ giao diện hỗ trợ GPS, hiển thị bản đồ số .......................... 48 Hình 3.6: Minh hoạ giao diện chỉ sử dụng tin nhắn SMS................................. 50 Hình 3.7: Sơ đồ tổng quát hệ thống dịch vụ tìm đường.................................... 52 Hình 4.1: Giao tiếp của hệ thống LBS thử nghiệm .......................................... 54 Hình 4.2: Giao diện soạn thảo bản đồ MapInfo Professional 9.0 ..................... 56 Hình 4.3: Giao diện Microsoft Visual Studio 2008.......................................... 58 - ix - Hình 4.4: Giao diện MS Studio 2008 với sự tích hợp của MapXtreme 2008 ... 59 Hình 4.5: Hiển thị dữ liệu bản đồ bằng MapXtreme 2008 ............................... 59 Hình 4.6: Định dạng gói tin yêu cầu 1 ............................................................. 65 Hình 4.7: Định dạng gói tin kết quả 1.............................................................. 66 Hình 4.8: Định dạng gói tin yêu cầu 2 ............................................................. 66 Hình 4.9: Định dạng gói tin kết quả 2.............................................................. 68 Hình 4.10: Giao diện phần mềm phía máy chủ ................................................ 72 Hình 4.11: Giao diện phần mềm phía máy khách (mới khởi động) .................. 73 Hình 4.12: Giao diện phần mềm phía máy khách (menu chính)....................... 74 Hình 4.13: Giao diện phần mềm phía máy khách (tìm đường)......................... 76 MỞ ĐẦU Ngày nay, khi ra ngoài đường, đến công sở, tới các trung tâm giải trí,... hầu như ở đâu ta cũng đều có thể bắt gặp sự xuất hiện của điện thoại, các thiết bị liên lạc di động. Sự ra đời của các thế hệ điện thoại, các thiết bị di động thông minh, có khả năng kết nối internet, khai thác dịch vụ định vị toàn cầu đã làm cho các ứng dụng trên chúng ngày càng trở lên phong phú, đa dạng, đặc biệt là các ứng dụng dịch vụ dựa trên vị trí địa lý như các hệ thống dẫn đường, hỗ trợ lái tự động sử dụng trong máy bay, ô tô; bản đồ kèm theo chức năng tìm đường dành cho điện thoại di động có định vị toàn cầu... Mặc dù đã có nhiều sản phẩm phần mềm, dịch vụ dựa trên vị trí địa lý được triển khai khá hiệu quả nhưng những sản phẩm, dịch vụ mang đặc thù riêng, phù hợp với điều kiện kinh tế, xã hội hiện tại của Việt Nam thì vẫn còn rất thiếu. Việc nghiên cứu, xây dựng và triển khai các dịch vụ này cho phù hợp với điều kiện thực tế của Việt Nam là rất cần thiết. Sản phẩm mang lại sẽ góp phần cho ra đời các phần mềm, các dịch vụ thực sự hữu ích, phù hợp và đáp ứng tối đa nhu cầu trong nước. Xuất phát từ những vấn đề nêu trên, đề tài “Nghiên cứu phát triển hệ thống dịch vụ dựa trên vị trí địa lý và thử nghiệm” nhằm mục tiêu tiếp cận, nghiên cứu các đặc điểm, ứng dụng, cơ sở hạ tầng, các mô hình triển khai dịch vụ dựa trên vị trí địa lý; tìm hiểu bài toán triển khai hệ thống cung cấp dịch vụ chỉ đường cho các thiết bị di động (như điện thoại có định vi toàn cầu); trên cơ sở đó xây dựng dịch vụ tìm đường ứng dụng thử nghiệm cho điện thoại di động có tính đến các yếu tố thường xuyên thay đổi đồng thời lại có tác động lớn đến chất lượng đường đi tìm được đó là sự tắc đường, úng lụt cục bộ,... ứng dụng logic mờ vào giải bài toán tìm đường đi “tốt nhất” khai thác các yếu tố tác động nêu trên. Việc triển khai thành công dịch vụ này sẽ có ý nghĩa rất lớn trong quá trình tìm lời giải cho bài toán tắc đường, úng lụt cục bộ trong các thành phố lớn đang xuất hiện ngày một nhiều và có ảnh hưởng rất nhiều tới đời sống xã hội hiện nay đồng thời cũng là cơ sở để phát triển các dịch vụ khác dựa trên vị trí địa lý, đáp ứng các yêu cầu trong điều kiện cụ thể của Việt Nam. Luận văn được trình bày thành 3 phần bao gồm: phần mở đầu, phần nội dung và phần kết luận: Phần mở đầu: giới thiệu khái quát về đề tài, mục tiêu, ý nghĩa khoa học và xã hội mạng lại thông qua việc giải quyết các vấn đề được nêu trong đề tài. - 2 - Phần nội dung: được chia thành 4 chương: Chương 1: Tổng quan về LBS Giới thiệu tổng quan về LBS, trình bày các định nghĩa về LBS, nêu ra các thành phần chính của LBS, mô tả hoạt động, các xử lý yêu cầu dịch vụ của LBS và đi vào phân tích đặc điểm, vai trò một số thành phần chính của LBS. Chương 2: Ứng dụng logic mờ trong tìm đường Giới thiệu về tổng quan về logic mờ, một số khái niệm về logic mờ, các thuật toán tìm đường và ứng dụng logic mờ trong bài toán tìm đường. Chương 3: Thiết kế dịch vụ LBS Giới thiệu tổng quan một số mô hình dịch vụ LBS, phân tích đặc điểm, ưu và nhược điểm của mỗi mô hình. Lựa chọn và triển khai thiết kế dịch vụ LBS tìm đường đi trong thành phố. Chương 4: Cài đặt thử nghiệm Trình bày các nội dung cài đặt thử nghiệm dịch vụ LBS tìm đường đi trong nội thành thành phố Hà Nội. Lựa chọn mô hình, kiểu dịch vụ, công nghệ áp dụng và kết quả. Phần kết luận: trình bày tóm tắt kết quả đạt được của đề tài cũng như hướng phát triển để sản phẩm của đề tài thực sự trở lên hữu ích và áp dụng tốt vào thực tiễn. - 3 - Chương 1: TỔNG QUAN VỀ LBS Giới thiệu tổng quan về LBS, trình bày các định nghĩa về LBS, nêu ra các thành phần chính của LBS, mô tả hoạt động, các xử lý yêu cầu dịch vụ của LBS và đi vào phân tích đặc điểm, vai trò một số thành phần chính của LBS. 1.1. Giới thiệu chung về LBS LBS viết tắt của Location-based Service (dịch vụ dựa trên vị trí địa lý) là dịch vụ được tạo ra từ sự kết hợp của công nghệ GPS (Global Positioning System – Hệ thống định vị toàn cầu), công nghệ truyền thông không dây, công nghệ GIS (Geographic Information Systems - Hệ thống thông tin địa lý) và công nghệ Internet. Điện thoại di động và Internet đã tạo nên cuộc cách mạng trong lĩnh vực truyền thông và có tác động đến lớn đến đời sống xã hội, làm thay đổi lối sống của nhiều người. Việc gia tăng về số lượng điện thoại di động, điện thoại thông minh, các thiết bị trợ giúp cá nhân kỹ thuật số (PDA- Personal Digital Assistants),... cho phép chúng ta có thể truy cập Internet bất cứ đâu, ở bất cứ thời điểm nào mong muốn. Từ Internet, ta có thể nhận được mọi thông tin mà ta cần (tin tức sự kiện, thông tin mua sắm, dự báo thời tiết, vị trí các nhà hàng – khách sạn – bệnh viện,...). Với các hỗ trợ từ Internet, mạng di động, thiết bị định vị toàn cầu, bản đồ số ta có thể dễ dàng tìm ra được một nhà hàng, hay siêu thị gần nhất. Các nhu cầu tương tự như vậy ngày nay dễ dàng được đáp ứng nhờ vào một loại dịch vụ mới, dịch vụ dựa trên vị trí địa lý – LBS. Có nhiều cách định nghĩa về LBS như: LBS là dịch vụ thông tin có thể truy cập bằng các thiết bị di động thông qua môi trường mạng di động và mang lại các lợi ích nhờ vào sự khai thác vị trí của thiết bị di động (theo Virrantaus et al. 2001). Định nghĩa tương tự thứ hai về LBS được đưa ra bởi Open Geospatial Consortium (OGC, 2005), một tổ chức tiêu chuẩn quốc tế: LBS - Một dịch vụ IP không dây sử dụng các thông tin địa lý để phục vụ cho người dùng di động. Mọi ứng dụng dịch vụ đều khai thác vị trí của các thiết bị di động đầu cuối. - 4 - Từ các định nghĩa này cho thấy, LBS là phần giao giữa ba nhóm công nghệ là các công nghệ thông tin và truyền thông hiện đại như các hệ thống truyền thông di động, thiết bị di động cầm tay với Internet và các hệ thống thông tin địa lý (GIS)/cơ sở dữ liệu (CSDL) không gian. Hình 1.1: LBS là phần giao của các công nghệ Hình 1.1 cho thấy LBS chính là phần giao của các công nghệ, bên cạnh đó, nó cho thấy sự hình thành các hệ thống thông tin tích hợp: Hệ thống “Web GIS” được hình thành từ việc tích hợp Internet với GIS/CSDL không gian. Hệ thống “GIS di động” được hình thành từ việc tích hợp GIS/CSDL không gian với Các thiết bị di động. Hệ thống “Internet di động” được hình thành từ việc tích hợp Internet với Các thiết bị di động. Còn dịch vụ LBS được hình thành từ việc tích hợp ba loại công nghệ Internet, GIS/CSDL không gian và Các thiết bị di động. Luận văn tập trung nghiên cứu về LBS, các thành phần, các mô hình triển khai của LBS, trên cơ sở đó thiết kế dịch vụ LBS ứng dụng logic mờ trong thuật toán tìm đường để triển khai thử nghiệm dịch vụ tìm đường trên điện thoại di động. Phần tiếp theo giới thiệu về các thành của LBS. GIS/CSDL không gian Các thiết bị di động Internet - 5 - 1.2. Các thành phần của LBS Theo [9], LBS bao gồm các thành phần chính sau (thể hiện trên hình 1.2): Các thiết bị di động: Là các công cụ để người dùng yêu cầu và truy cập các thông tin mong muốn. Kết quả trả về có thể là lời nói, tranh ảnh hay văn bản... Các thiết bị có thể là điện thoại di động, thiết bị hỗ trợ cá nhân kỹ thuật số (PDA), máy tính xách tay, thậm chí là thiết bị dẫn đường trên ô tô... Mạng truyền thông: thành phần thứ hai là mạng truyền thông với vai trò truyền các dữ liệu người dùng, các yêu cầu dịch vụ từ các thiết bị di động đầu cuối đến các nhà cung cấp dịch vụ và sau đó tải các thông tin về phía người dùng. Hệ thống định vị: Để dịch vụ có thể hoạt động được, cần thiết phải xác định được vị trí của người dùng. Vị trí của người có thể được xác định bằng thiết bị định vi toàn cầu (GPS) hay thông qua mạng truyền thông. Thậm chí còn có thể xác định nhờ vào các dấu hiệu hoạt động, các tín hiệu sóng radio. Nếu vị trí không thể xác định một cách tự động thông qua mạng hay các thiết bị định vị thì người sử dụng có thể cập nhật bằng tay và tự cung cấp cho hệ thống. Hình 1.2: Các thành phần cơ bản của LBS Thiết bị di động (người dùng) Hệ thống định vị Mạng truyền thông Các nhà cung cấp dịch vụ và nội dung Các thành phần của LBS Thiết bị di động Mạng truyền thông Nhà cung cấp dịch vụ và nội dung Hệ thống định vị - 6 - Các nhà cung cấp dịch vụ và ứng dụng: Các nhà cung cấp dịch có thể cung cấp các dịch vụ khác nhau cho người dùng và có trách nhiệm xử lý các yêu cầu dịch vụ của người dùng. Các dịch vụ cung cấp có thể là tính toán vị trí, tìm đường đi, tìm các trang vàng (yellow pages) theo các khía cạnh về vị trí hoặc tìm kiếm các thông tin xác định của các đối tượng mà người dùng quan tâm... Nhà cung cấp dữ liệu và nội dung: Nhà cung cấp dịch vụ thường không lưu trữ và bảo quản các thông tin mà người dùng quan tâm. Các dữ liệu và nội dung liên quan như bản đồ, dữ liệu về giao thông ... đều được lưu trữ tại các công ty, các cơ quan có thẩm quyền. 1.3. Các kiểu dịch vụ LBS Có hai kiểu dịch vụ là Push (đẩy) và Pull (kéo) được phân biệt dựa vào đặc điểm là thông tin được cung cấp có tương tác với người dùng hay không [9][6]: Dịch vụ kiểu Pull: cung cấp thông tin theo các yêu cầu trực tiếp của người dùng. Kiểu dịch vụ này tương tự như khi người dùng duyệt một trang web trên Internet bằng cách gõ địa chỉ trang web vào thanh địa chỉ của trình duyệt và yêu cầu mở. Hơn nữa, các dịch vụ kiểu Pull có thể chia thành các dịch vụ chức năng (functional services) kiểu như gọi xe taxi hay xe cứu thương chỉ bằng một động tác nhấn nút trên thiết bị và các dịch vụ thông tin (information services) giống như việc tìm kiếm một nhà hàng, hay quan bia gần nhất vậy. Dịch vụ kiểu Push: cung cấp thông tin theo yêu cầu trực tiếp hoặc không trực tiếp của người dùng. Dịch vụ hoạt động theo các sự kiện. Các sự kiện có thể xuất hiện khi đi vào một vùng xác định hay theo thời gian. Ví dụ như các thông tin quảng cáo tự động được gửi đến cho người dùng khi họ đi vào khu phố buôn bán, có nhiều nhà hàng, siêu thị hay thông tin cảnh báo về thời tiết khi có sự thay đổi. 1.4. Xử lý các yêu cầu của LBS Mục 1.2 đã giới thiệu các thành phần của LBS bao gồm: các thiết bị di động, mạng truyền thông, internet, hệ thống định vị, các nhà cung cấp dịch vụ và nội dung. Vậy các thành phần này có mối quan hệ và tương tác với nhau thế nào trong dịch vụ LBS? Giả sử người dùng khai thác dịch vụ LBS để tìm kiếm một nhà hàng gần nhất. Thông tin mà người dùng cần là đường đi đến nhà hàng. Khi đó người - 7 - dùng có thể sử dụng thiết bị di động mà họ có (ví dụ như một Smart Phone hay một PDA), khởi động chức năng cần thiết để gửi yêu cầu. Luồng thông tin yêu cầu của người dùng cũng như các trả lời được thể hiện trên hình 1.3: Hình 1.3: Luồng thông tin giữa các thành phần của LBS Sau khi chức năng được kích hoạt, vị trí của thiết bị di động (cũng chính là vị trí của người dùng) được xác định và cung cấp bởi dịch vụ định vị. Vị trí này có thể được xác định nhờ vào dịch vụ GPS hoặc một dịch vụ định vị bởi mạng truyền thông. Tiếp theo đó, thiết bị di động của người dùng sẽ gửi các thông tin yêu cầu bao gồm đối tượng cần tìm kiếm và vị trí hiện tại thông qua một mạng truyền thông được gọi gateway. Gateway có nhiệm vụ truyền tải các thông điệp giữa mạng truyền thông di động và internet. Các thông điệp có thể được truyền tải thông qua một vài máy chủ ứng dụng để đến một máy chủ xác định đồng thời lưu giữ lại các thông tin về yêu cầu và vị trí của người dùng. Máy chủ ứng dụng sẽ đọc yêu cầu và kích hoạt dịch vụ phù hợp để đáp ứng yêu cầu (trong ví dụ này, một dịch vụ tìm kiếm không gian sẽ được kích hoạt). Tiếp theo, dịch vụ tìm kiếm sẽ phân tích thông điệp thêm lần nữa và quyết định thông tin gì cần được bổ sung vào điều kiện tìm kiếm và vị trí của người gửi yêu cầu. Trong tình huống này, dịch vụ sẽ tìm kiếm các thông tin cần thiết về nhà hàng từ các trang vàng của một khu vực cụ thể và yêu cầu nhà cung cấp dữ liệu về các thông tin cần thiết. Tiếp theo dịch vụ sẽ tìm các tuyến đường dẫn đến nhà hàng cần tìm thỏa mãn yêu cầu tìm kiếm và đánh dấu lại. Các dịch vụ: - Tìm nhà hàng - Dẫn đường xe - Tìm bạn - Bàn đồ - Trợ giúp khách du lịch ... Công ty X Nhà cung cấp dữ liệu/nội dung Thiết bị/ người dùng Mạng truyền thông Internet Hệ thống định vị - 8 - Sau khi đã có được các thông tin cần thiết, dịch vụ sẽ hoạt động trên bộ đệm không gian để tìm đường đi đến các nhà hàng. Sau khi tính toán và liệt kê ra được danh sách các nhà hàng gần nhất, dịch vụ sẽ gửi lại cho người dùng kết quả thông qua mạng internet, gateway, qua mạng thông tin di động đến với thiết bị di động của người dùng. Kết quả tìm kiếm có thể được gửi về cho người dùng dưới dạng văn bản (một danh sách các nhà hàng được sắp xếp theo thứ tự khoảng cách) hoặc vẽ trên bản đồ. Tiếp theo đó, người dùng có thể yêu cầu thêm các thông tin chi tiết về nhà hàng họ quan tâm (sẽ làm kích hoạt các dịch vụ khác). Cuối cùng họ chọn một nhà hàng cụ thể và tiếp tục yêu cầu chỉ đường đi đến nhà hàng. 1.5. Các thiết bị di động 1.5.1. Các loại thiết bị Thiết bị di động là phương tiện để người sử dụng LBS đưa ra yêu cầu, thu thập thông tin và khai thác các dịch vụ LBS, đáp ứng nhu cầu của người dùng. LBS mang lại nhiều tiện ích lớn bởi sự phong phú của các dịch vụ được cung cấp và bởi chính sự trợ giúp đắc lực của rất nhiều loại thiết bị tạo nên. Các thiết bị có ảnh hưởng lớn tới chất lượng các dịch vụ LBS mang lại. Dựa vào các đặc điểm, mục tiêu thiết kế và khả năng ứng dụng, các thiết bị di động sử dụng cho LBS có thể được chia thành hai loại thiết bị là các thiết bị đơn mục đích và các thiết bị đa mục đích. Các thiết bị đơn mục đích: là các thiết bị được thiết kế nhằm đáp ứng một nhu cầu hay ứng dụng cụ thể nào đó, ví dụ như hộp chỉ đường trên ô tô, hộp chỉ dẫn hay trợ giúp từ xa trong trường hợp khẩn cấp dành cho người già hoặc người khuyết tật. Trong số đó có những thiết bị chỉ thực hiện nhiệm vụ gọi dịch vụ hay đội cứu hộ. Có những thiết bị cao cấp hơn, đóng vai trò như một người canh gác, người soát vé trên các cây cầu hay tòa nhà. Các thiết bị đa mục đích: là các thiết bị được thiết kế để có thể sử dụng cho nhiều mục đích khác nhau tùy thuộc nhu cầu của người sử dụng. Các thiết bị này có thể là các điện thoại di động thông thường (Mobile phones), các loại điện thoại thông minh (Smart Phones), các thiết bị trợ giúp cá nhân kỹ thuật số (PDA), máy tính xách tay (Laptops) hay máy tính bảng (Tablet PC). - 9 - Hình 1.4: Hình ảnh minh họa các thiết bị di động dùng trong LBS 1.5.2. Các hạn chế của thiết bị Quan sát trở lại các loại thiết bị đã được giới thiệu, rõ ràng là các thiết bị đơn mục đích do được thiết kế cho mục đích sử dụng xác định nên không có hoặc hầu như không thể chuyển đổi chức năng, tính linh hoạt kém. Các thiết bị đa mục đích có tính linh hoạt cao và có khả năng sử dụng cho nhiều loại dịch vụ khác nhau trên cùng thiết bị. Tuy nhiên các thiết bị loại này cũng có nhiều mặt hạn chế ảnh hưởng đến việc thiết kế và triển khai các dịch vụ như: Hầu hết các thiết bị này đều có khả năng tính toán và tài nguyên hạn chế, do vậy rất khó khăn để thực hiện các tính toán, tìm kiếm không gian, tìm đường và thể hiện các bản đồ ứng dụng trong các loại dịch vụ liên quan đến bản đồ di động, chỉ dẫn, tìm đường, tìm địa chỉ xác định. Chính vì các hạn chế đó nên thông thường các tính toán tìm kiếm và xử lý phức tạp được thực hiện trên các máy chủ và gửi kết quả trở lại cho người dùng. Các thiết bị chủ yếu thực hiện vai trò cung cấp yêu cầu, các số liệu về vị trí và hiển thị kết quả do máy chủ gửi lại. Ngoài ra, các thiết bị này còn có các giới hạn khác như dung lượng nguồn pin thấp, kích thước màn hình nhỏ và chịu ảnh hưởng nhiều của môi trường (có những màn hình sẽ rất khó quan sát khi bị ảnh hưởng của ánh sáng mặt trời,...). Trong vấn đề gửi/nhận dữ liệu thì vẫn thiếu băng tần rộng để truy cập vào các mạng truyền thông, tốc độ thấp. - 10 - 1.6. Mạng thông tin di động không dây Như đã được giới thiệu ở phần trước, mạng truyền thông nói chung và mạng di động không dây (Wireless Mobile Networks) nói riêng thực hiện nhiệm vụ truyền tải các dữ liệu người dùng, các yêu cầu dịch vụ, các thông điệp từ các thiết bị đầu cuối tới các nhà cung cấp dịch vụ và truyền tải các thông tin ngược trở lại cho người dùng. Mạng di động không dây còn có thể có nhiệm vụ thứ hai là xác định vị trí của người dùng. Các mạng di động hiện nay có thể được phân loại theo hai cách. Thứ nhất, mạng được phân loại dựa trên phạm vi của mạng bao gồm mục đích sử dụng và giới hạn về phạm vi phủ sóng. Thứ hai, mạng được phân loại dựa trên công nghệ mạng, theo đó, có mạng bao gồm một lượng lớn các cơ sở hạ tầng là các nút mạng không di động và các khách hàng di động chỉ truy cập vào các nút và các khách hàng thuộc mạng “Ad-Hoc”, bản thân họ cũng chính là các nút mạng. Cách phân loại dựa vào yếu tố về phạm vi bao phủ chia mạng thành các loại mạng: Mạng không dây diện rộng (Wireless Wide Area Networks- WWAN), ví dụ như mạng GSM và UMTS, mạng không dây cục bộ (Wireless Local Area Networks –WLAN), ví dụ như mạng IEEE 802.11 và mạng không dây cá nhân (Wireless Personal Area Networks - WPAN), ví dụ như mạng Bluetooth. Hình 1.5 thể sự phân loại mạng không dây di động theo các tiêu chí về phạm vi và công nghệ sử dụng [9]. Hình 1.5: Phân loại mạng không dây di động 1.6.1. Mạng không dây diện rộng Mạng không dây diện rộng (WWAN) [9], minh họa như ở hình 1.6, có các tế bào mạng (cells) bao phủ trong phạm vi vài trăm mét đến 35Km. Mạng sử dụng giải tần số bị kiểm soát và phải được cấp phép. Thế hệ thứ nhất của mạng (analogue G1) phục vụ cho giao tiếp âm thanh nên dữ liệu chỉ được truyền với - 11 - tốc độ rất thấp (4.8 kbps). Hệ thống mạng di động toàn cầu (Global System for Mobile - GSM) và General Packet Radio Service (GPRS) thuộc thế hệ thứ hai (digital G2). Thế hệ mạng này có thể truyền tải dữ liệu với tốc độ cao hơn (GSM: 9.6 –14kbps; GPRS: 20-115kbps). Tuy nhiên, các tốc độ này vẫn chưa đáp ứng được yêu cầu về tốc độ để truyền tải các dữ liệu đa phương tiện. Để đáp ứng nhu cầu của các ứng dụng đa phương tiện, thế hệ mạng thứ 3 đã được xây dựng . Ở Châu Âu, hệ thống băng thông rộng này được gọi là UMTS (Universal Mobile Telecommunication System) với tốc độ có thể lên đến 2Mbps. Hình 1.6: Mạng không dây diện rộng (WWAN) 1.6.2. Mạng không dây cục bộ Mạng không dây cục bộ (WLAN) có tầm bao phủ trong phạm vi từ 10m đến 150m [9]. Mạng này sử dụng giải tần số không bị kiểm soát (không phải xin cấp phép), cho tốc độ truyền dữ liệu (100Mbps), cao hơn nhiều so với mạng WWAN. Mạng WLAN được thể hiện như là sự mở rộng của mạng máy tính cục bộ (LAN). Các trạm di động kết nối với mạng WLAN có thể sử dụng cơ sở hạ tầng mạng đơn giản với các điểm truy cập mạng (Access Points-APs) thay cho các trạm cơ sở vốn rất phức tạp và tốn kém trong mạng WWAN hoặc có thể kết nối trực tiếp với nhau theo mô hình mạng Ad-hoc. Hình 1.7 là một minh họa cho mạng không dây cục bộ. - 12 - Hình 1.7: Mạng không dây cục bộ (WLAN) 1.6.3. Mạng không dây cá nhân Mạng không dây cá nhân (WPAN) cung cấp các kết nối trong phạm vi ngắn, dùng cho các camera số hay các thiết bị cầm tay [9]. Mạng có phạm vi bao phủ trong bán kính khoảng 10m và có thể tăng lên đến 100m trong tương lai. Mạng sử dụng giải tần số tự do, không bị kiểm soát và cho tốc độ truyền thông khoảng 0.5Mbps (nằm giữa mạng WWAN và WLAN). Các thiết bị tham gia mạng có thể kết nối hoặc bỏ kết nối khi cần thiết (không duy trì kết nối liên tục) cho nên còn được gọi là mạng Ad-hoc. Hầu hết các mạng WPAN đều được triển khai trên cơ sở chuẩn truyền thông Bluetooth. Mạng này có ưu điểm hơn so với mạng WLAN là hỗ trợ truyền thông âm thanh và tính năng bảo mật. Hình 1.8 minh hoạ mạng không dây cá nhân WLAN. - 13 - Hình 1.8: Mạng không dây cá nhân (WPAN) Bảng 1.1: Đặc điểm và sự khác nhau giữa các công nghệ mạng không dây Công nghệ mạng Khoảng cách trung bình Tốc độ dữ liệu (Mbps) Phạm vi tần số GSM (G2) 0.009-0.014 GPRS 0.160 WWAN UTMS (G3) Khoảng cách các trạm cơ sở từ 100m-35Km 2.0 ~ 900 MHz (phải được cấp phép) Ultra- Wideband 10m 100 IEEE 802.11a 50m 54 WLAN IEEE 802.11b 100m 11 ~ 2.4 và 5 GHz (không cần cấp phép) Bluetooth 10m 1 HomeRF 50m 10 ~ 2.4 GHz (không cần cấp phép) WPAN IrDA (Infrared) 1-1.5 (đường truyền không bị chắn) 1-16 Không cần cấp phép - 14 - 1.7. Hệ thống định vị 1.7.1. Giới thiệu chung Hệ thống định vị có vai trò rất lớn trong việc triển khai các dịch vụ LBS. Hệ thống này cung cấp dịch vụ xác định vị trí của thiết bị di động và cung cấp cho các thiết bị này thông tin về vị trí của chúng để các thiết bị gửi kèm theo các yêu cầu dịch vụ LBS đến các nhà cung cấp dịch vụ LBS. Ngoại trừ trường hợp người dùng nhập trực tiếp tọa độ (vị trí), phương pháp xác định vị trí có thể được chia thành hai nhóm [9]: Nhóm thứ nhất được gọi là định vị dựa trên mạng (network-based positioning). Trong nhóm này, việc xác định vị trí của các thiết bị di động hay người dùng được thực hiện nhờ vào các trạm cơ sở của mạng. Trong khi hoạt động, các thiết bị di động thường gửi tín hiệu liên lạc với các trạm cơ sở của mạng, mỗi trạm cơ sở chỉ kiểm soát trọng một phạm vi gới hạn nên chỉ có một số trạm là có thể thu được tín hiệu gửi từ thiết bị di động, do vậy dựa vào tín thiệu thu nhận được từ các trạm cơ sở này mà xác định được thiết bị di động đang ở khu vực nào (thể hiện như ở hình 1.9) [13]. Hình 1.9: Định vị dựa trên mạng truyền thông - 15 - Nhóm thứ hai được gọi là định vị dựa trên thiết bị đầu cuối (terminal- based positioning). Trong nhóm này, vị trí của của thiết bị được tính toán bởi chính các thiết bị dựa trên các tín hiệu thu được từ các trạm cơ sở (hình 1.10) [13]. Một đại diện trong nhóm này là hệ thống định vị toàn cầu GPS. Trong hệ thống này, các trạm cơ sở chính là các vệ tinh GPS. Nhóm thứ ba là nhóm được tạo nên từ sự tích hợp của kỹ thuật định vị dựa trên mạng và kỹ thuật định vị dựa trên thiết bị đầu cuối. Hình 1.10: Định vị dựa trên thiết bị đầu cuối Các nguyên tắc cơ bản để tính toán vị trí của người dùng, áp dụng cho cả ba nhóm trên là: Các trạm cơ sở có vị trí xác định được biết từ trước Thông tin từ các tín hiệu thu được được chuyển thành khoảng cách Tính toán vị trí dựa vào khoảng cách thu được tới các trạm cơ sở Sau đây là các kỹ thuật thường được dùng để xác định vị trí: Kỹ thuật Cell of origin (COO), location signature, location beacons: cell id thường là nhận dạng của các trạm gần nhất, ví dụ như các trạm anten điện thoại di động. Với kỹ thuật này, vị trí được biết trong một đường tròn đã được định nghĩa sẵn hoặc một vùng xung quanh một trạm cơ sở đã biết trước vị trí. Các đèn hiệu (beacons), ví dụ như sóng hồng ngoại, sóng siêu âm hay RFID, thường có một số hiệu nhận dạng và truyền chính xác vị trí của chúng tới các thiết bị di động mà chúng có thể với tới được. - 16 - Kỹ thuật Time of Arrival (TOA): Các tín hiệu điện từ di chuyển với tốc độ của ánh sáng. Nhờ đó, khoảng cách giữa trạm truyền và trạm thu có thể tính được khi biết tốc độ và thời gian tín hiệu di chuyển tính từ lúc truyền đi đến khi nhận được. Tốc độ ánh sáng đã được biết là sấp xỉ 300000Km/s vì thế mà thời gian truyền là rất ngắn, đòi hỏi phải có một đồng hồ chính xác để ghi nhận thời gian. Nguyên tắc này cũng có thể được dùng cho các tín hiệu có tốc độ thấp hơn như sóng siêu âm. Kỹ thuật Time Difference of Arrival (TDOA), Enhanced Observed Time Difference (E-OTD): các kỹ thuật này tính toán khoảng cách bằng cách đo thời gian truyền, sự khác nhau về thời gian truyền của các tín hiệu khác nhau của các trạm cơ sở (thường là 3 trạm). Vì thế, việc thu được các tín hiệu từ các trạm cơ sở ở các vị trí khác nhau (thường xếp theo hình tam giác) có thể được các nhà cung cấp dịch vụ tính toán vị trí theo TDOA và được các thiết bị di động sử dụng để tính toán vị trí trong E-ODT. Kỹ thuật Angle of Arrival (AOA), Direction of Arrival (DOA): được thực hiện bằng cách sử dụng các anten có đực tính về chiều và góc có khả năng phát hiện được sự di chuyển của các thiết bị di động. Vì sự di chuyển của các thiết bị di động là không chính xác. Một khả năng khác là góm một số các trạm cơ sở lại tạo nên một cung (thường là 2 hoặc 4 trạm), chúng có thể được chia thành từng cụm trên một đường tròn với các cung 90, 120 hoặc 180 độ. Các công nghệ định vị thường được dùng hiện nay là GPS và tính toán vị trí dựa vào Cell-ID từ các trạm thu phát cơ sở gần nhất (theo phương pháp định vị mạng). GPS cung cấp vị trí với độ chính xác rất cao (chính xác tới 5m), trong khi đó, Cell-ID chỉ cho phép xác định vị trí với độ chính xác rất thấp (độ chính xác thường trong phạm vi từ 100m đến Km). 1.7.2. Hệ thống định vị toàn cầu GPS Hệ thống định vị toàn cầu (tiếng Anh gọi là Global Positioning System - GPS) là hệ thống xác định vị trí dựa trên vị trí của các vệ tinh nhân tạo. Trong cùng một thời điểm, ở một vị trí trên mặt đất nếu xác định được khoảng cách đến ba vệ tinh (tối thiểu) thì sẽ tính được tọa độ của vị trí đó. GPS được thiết kế và quản lý bởi Bộ Quốc phòng Mỹ, nhưng chính phủ Mỹ cho phép mọi người trên thế giới sử dụng nó miễn phí, bất kể quốc tịch nào. Các nước trong Liên minh châu Âu đang xây dựng Hệ thống định vị Galileo, có tính năng giống như GPS của Mỹ, dự tính sẽ bắt đầu hoạt động năm 2013. - 17 - Hệ thống định vị toàn cầu của Mỹ là hệ dẫn đường dựa trên một mạng lưới 24 vệ tinh được Bộ Quốc phòng Mỹ dưa lên quỹ đạo không gian. Các hệ thống dẫn đường truyền thống hoạt động dựa trên các trạm phát tín hiệu vô tuyến điện. Được biết đến nhiều nhất là các hệ thống sau: LORAN – (LOng RAnge Navigation) – hoạt động ở giải tần 90-100 kHz chủ yếu dùng cho hàng hải TACAN – (TACtical Air Navigation) – dùng cho quân đội Mỹ VOR/DME – VHF (Omnidirectional Range/Distance Measuring Equipment) – là một biến thể của TACAN với độ chính xác thấp dùng cho hàng không dân dụng. Gần như đồng thời với thời điểm Mỹ phát triển GPS, Liên Xô cũ cũng phát triển một hệ thống tương tự với tên gọi GLONASS. Hiện nay Liên minh Châu Âu đang phát triển hệ dẫn đường vệ tinh của mình mang tên Galileo. Ban đầu, GPS và GLONASS đều được phát triển cho mục đích quân sự, nên mặc dù chúng dùng được cho dân sự nhưng không hệ nào đưa ra sự đảm bảo tồn tại liên tục và độ chính xác. Vì thế chúng không thỏa mãn được những yêu cầu an toàn cho dẫn đường dân sự hàng không và hàng hải, đặc biệt là tại những vùng và tại những thời điểm có hoạt động quân sự của những quốc gia sở hữu các hệ thống đó. Chỉ có hệ thống dẫn đường vệ tinh châu Âu Galileo (đang được xây dựng) ngay từ đầu đã đặt mục tiêu đáp ứng các yêu cầu nghiêm ngặt của dẫn đường và định vị dân sự. GPS ban đầu chỉ dành cho các mục đích quân sự, nhưng từ năm 1980 chính phủ Mỹ cho phép sử dụng trong dân sự. GPS hoạt động trong mọi điều kiện thời tiết, mọi nơi trên Trái Đất, 24 giờ một ngày. Không mất phí thuê bao hoặc mất tiền trả cho việc thiết lập sử dụng GPS [5]. Hệ thống vệ tinh GPS Hệ thống vệ tinh GPS chia làm 3 phần [6]: - 18 - Hình 1.11: Các phần của hệ thống GPS [6] Phần không gian: Gồm 24 vệ tinh nhân tạo, cập nhật đến năm 1994, (21 vệ tinh hoạt động và 3 vệ tinh dự phòng) nằm trên các quỹ đạo xoay quanh trái đất. Chúng cách mặt đất 12000 dặm. Chúng chuyển động ổn định, hai vòng quỹ đạo trong khoảng thời gian gần 24 giờ. Các vệ tinh này chuyển động với vận tốc 7000 dặm một giờ. Các vệ tinh trên quỹ đạo được bố trí sao cho các máy thu GPS trên mặt đất có thể nhìn thấy tối thiểu 4 vệ tinh vào bất kỳ thời điểm nào. Các vệ tinh hoạt động nhờ vào nguồn năng lượng Mặt Trời. Chúng có các nguồn pin dự phòng để duy trì hoạt động khi chạy khuất vào vùng không có ánh sáng Mặt Trời. Các tên lửa nhỏ gắn ở mỗi quả vệ tinh giữ chúng bay đúng quỹ đạo đã định [5] . Mỗi vệ tinh nặng từ 1,5 đến 2 tấn, dài khoảng 5m với công suất phát khoảng 50W. Máy tính điều khiển trung tâm mỗi vệ tinh được trang bị CPU với tốc độ 16MHz. Các vệ tinh được lập trình bằng ngôn ngữ Ada (một ngôn ngữ lập trình xuất xứ từ Bộ quốc phòng Mỹ vào khoảng nửa đầu thập niên 80 của thế kỷ 20, ngôn ngữ này được đặt tên theo Ada Augusta nữ bá tước xứ Lovelace (1815 – 1852), nhà toán học với ý tưởng tiên phong coi phần cứng và phần mềm là hai mặt khác nhau đã đi vào lịch sử như lập trình viên đầu tiên và hacker đầu tiên của loài người). Hệ điều hành của vệ tinh được lập trình với sấp xỉ 25000 dòng lệnh [6]. - 19 - Hình 1.12: Quỹ đạo các vệ tinh của hệ thống GPS [6] Phần kiểm soát: Mục đích của phần này là kiểm soát vệ tinh đi đúng hướng theo quỹ đạo và thông tin thời gian chính xác. Có tất cả 5 trạm kiểm soát được đặt rải rác trên trái đất. Bốn trạm kiểm soát hoạt động một cách tự động, và một trạm kiểm soát là trung tâm. Bốn trạm này nhận tín hiệu liên tục từ những vệ tinh và gửi các thông tin này đến trạm kiểm soát trung tâm. Tại trạm kiểm soát trung tâm, nó sẽ sửa lại dữ liệu cho đúng và kết hợp với hai anten khác để gửi lại thông tin cho các vệ tinh . Phần sử dụng: là các thiết bị nhận tín hiệu vệ tinh GPS và người sử dụng thiết bị này. Hoạt động của hệ thống GPS Các vệ tinh GPS bay vòng quanh Trái Đất hai lần trong một ngày theo một quỹ đạo rất chính xác và phát tín hiệu có thông tin xuống Trái Đất. Các máy thu GPS nhận thông tin này và bằng phép tính lượng giác tính được chính xác vị trí của người dùng. Về bản chất máy thu GPS so sánh thời gian tín hiệu được phát đi từ vệ tinh với thời gian nhận được chúng. Sai lệch về thời gian cho biết máy thu GPS ở cách vệ tinh bao xa. Rồi với nhiều khoảng cách đo được tới nhiều vệ tinh máy thu có thể tính được vị trí của người dùng (vị trí máy thu). Máy thu phải nhận được tín hiệu của ít nhất ba vệ tinh để tính ra vị trí hai chiều (kinh độ và vĩ độ) và để theo dõi được chuyển động. Khi nhận được tín hiệu của ít nhất 4 vệ tinh thì máy thu có thể tính được vị trí ba chiều (kinh độ, vĩ độ và độ cao). Khi vị trí người dùng đã tính được thì máy thu GPS có thể tính - 20 - các thông tin khác, như tốc độ, hướng chuyển động, bám sát di chuyển, khoảng hành trình, quãng cách tới điểm đến, thời gian Mặt Trời mọc, lặn và nhiều thông tin khác nữa . Các vệ tinh GPS phát hai tín hiệu vô tuyến công suất thấp giải L1 và L2 (giải L là phần sóng cực ngắn của phổ điện từ trải rộng từ 0,39 tới 1,55 GHz). GPS dân sự dùng tần số L1 1575.42 MHz trong giải tần số UHF. Tín hiệu truyền trực thị, có nghĩa là chúng sẽ xuyên qua mây, thuỷ tinh và nhựa nhưng không qua phần lớn các đối tượng cứng như núi và nhà. L1 chứa hai mã "giả ngẫu nhiên" (pseudo random), đó là mã Protected (P) và mã Coarse/Acquisition (C/A). Mỗi một vệ tinh có một mã truyền dẫn nhất định, cho phép máy thu GPS nhận dạng được tín hiệu. Mục đích của các mã tín hiệu này là để tính toán khoảng cách từ vệ tinh đến máy thu GPS. Tín hiệu GPS chứa ba mẩu thông tin khác nhau – mã giả ngẫu nhiên, dữ liệu thiên văn và dữ liệu lịch. Mã giả ngẫu nhiên đơn giản chỉ là mã định danh để xác định được vệ tinh nào là phát thông tin nào. Dữ liệu thiên văn cho máy thu GPS biết vệ tinh ở đâu trên quỹ đạo ở mỗi thời điểm trong ngày. Mỗi vệ tinh phát dữ liệu thiên văn riêng chỉ ra thông tin quỹ đạo của vệ tinh đó. Dữ liệu lịch được phát đều đặn bởi mỗi vệ tinh, chứa thông tin quan trọng về trạng thái của vệ tinh, ngày giờ hiện tại. Phần này của tín hiệu là cốt lõi để phát hiện ra vị trí . Độ chính xác của GPS và nguồn gây lỗi Các máy thu GPS ngày nay có độ chính xác rất cao, nhờ vào thiết kế nhiều kênh hoạt động song song. Các máy thu 12 kênh song song (của Garmin) nhanh chóng “khóa” vào các quả vệ tinh khi mới bật lên và chúng duy trì kết nối bền vững, thậm chí vào thành phố với các toà nhà cao tầng. Trạng thái của khí quyển và các nguồn gây sai số khác có thể ảnh hưởng tới độ chính xác của máy thu GPS. Các máy thu GPS có độ chính xác trung bình trong vòng 15 mét. Các máy thu hiện đại hơn với khả năng WAAS (Wide Area Augmentation System) có thể tăng độ chính xác trung bình tới dưới 3 mét. Người dùng có thể nhận được số liệu định vị có độ chính xác tốt hơn với GPS Vi sai (Differential GPS, DGPS) sửa lỗi các tín hiệu GPS để có độ chính xác trong khoảng 3 đến 5 mét. Cục Phòng vệ Bờ biển Mỹ vận hành dịch vụ sửa lỗi này. Hệ thống bao gồm một mạng các đài thu tín hiệu GPS và phát tín hiệu đã sửa lỗi bằng các máy phát tín hiệu. Để thu được tín hiệu đã sửa lỗi, người dùng phải có máy thu tín hiệu vi sai bao gồm cả anten để dùng với máy thu GPS của họ . Thông tin thu được từ hệ thống GPS có thể thiếu chính xác do tác động của nhiễu. Sự thiếu chính xác này xảy ra do nhiều nguyên nhân khác nhau: - 21 - Từ nhiễu do tính chất giữ chậm của tầng đối lưu và tầng ion: tín hiệu vệ tinh bị chậm đi khi xuyên qua tầng khí quyển. Tín hiệu đi theo nhiều đường do bị phản xạ trước khi đến thiết bị thu. Do đồng hồ trên máy thu thiếu chính xác (đồng hồ trên các vệ tinh là đồng hồ nguyên tử, có độ chính xác rất cao). Số lượng vệ tinh “nhìn thấy” ít. Số lượng vệ tinh “quan sát được” càng nhiều thì độ chính xác càng cao. Sự giảm chính xác có chủ định: là sự làm giảm tín hiệu cố ý do sự áp đặt của Bộ Quốc phòng Mỹ, nhằm chống lại việc đối thủ quân sự dùng tín hiệu GPS chính xác cao. Chính phủ Mỹ đã ngừng việc này từ tháng 5 năm 2000, làm tăng đáng kể độ chính xác của máy thu GPS dân sự. Tuy nhiên biện pháp này hoàn toàn có thể được sử dụng lại trong những điều kiện cụ thể để đảm bảo “gậy ông không đập lưng ông”. Chính điều này là nguyên nhân tiềm ẩn hạn chế an toàn cho hệ thống dẫn đường và định vị dân sự sử dụng GPS. 1.8. Các mô hình dịch vụ LBS Tùy thuộc vào khả năng của các thành phần tham gia trong hệ thống dịch vụ LBS như tốc độ và băng thông của đường truyền, tài nguyên và khả năng xử lý của các thiết bị di động, khả năng của máy chủ cung cấp dịch vụ... các dịch vụ LBS có thể được triển khai theo các mô hình khác nhau như: Mô hình nặng máy chủ, nhẹ máy trạm: là mô hình mà các xử lý, tính toán phức tạp được tập trung thực hiện trên máy chủ, máy trạm (các thiết bị di động) chủ yếu là gửi các yêu cầu dịch vụ kèm theo vị trí đến máy chủ, chờ nhận kết quả gửi từ máy chủ về để thể hiện. Mô hình này thích hợp cho hệ thống mà cơ sở hạ tậng mạng truyền thông không tốt, tốc độ thấp, băng thông hẹp (các mạng truyền thông thế hệ 1G, 2G) và các thiết bị di động có khả năng tính toán không cao, bộ nhớ nhỏ (điện thoại di động, smart phone cấu hình thấp,...) Mô hình nhẹ máy chủ, nặng máy trạm: là mô hình mà các xử lý chính được thực hiện ngay trên máy trạm. Mô hình này phù hợp cho điều kiện cơ sở hạ tầng truyền thông không tốt (tốc độ thấp, băng thông hẹp) nhưng máy trạm có cấu hình mạnh. Mô hình cân bằng: là mô hình và các xử lý nhằm cung cấp dịch được phân đều cho máy chủ và máy trạm cùng xử lý. Mô hình này tận dụng khả năng tính toán của cả máy chủ và máy trạm nhưng đòi hỏi mạng truyền thông phải có tốc độ cao, bang thông lớn vì nhu cầu truyền tải thông tin qua lại giữa máy chủ và máy trạm là khá lớn. - 22 - 1.9. Giới thiệu một số ứng dụng dựa trên LBS Các dịch vụ khẩn cấp Một trong số nhiều ứng dụng của LBS đó là ứng dụng xác định vị trí của người nào đó mà bản thân họ không biết được mình đang ở đâu hoặc không thể xác định được vì đang ở trong tình trạng khẩn cấp, cần trợ giúp (ví dụ như bị tai nạn, bị tội phạm tấn công, hay khách du lịch không xác định được vị trí của mình khi xep bị hỏng trong quá trình di chuyển,...). Với vị trí chính xác được tự động chuyển về nhà cung cấp dịch vụ khẩn cấp, họ có thể dễ dàng thực hiện các trợ giúp một cách nhanh chóng và hiệu quả. Nhóm dịch vụ đang được để cập này bao gồm cả dịch vụ khẩn cấp công cộng và dịch vụ khẩn cấp cá nhân, phục vụ cho cả người đi bộ lẫn các lái xe. Các dịch vụ dẫn đường Ứng dụng tiếp theo phải kể đến đó là ứng dụng chỉ dẫn giao thông. Ứng dụng này được triển khai trên các đối tượng người dùng di chuyển. Trên một số phương tiện giao thông hay một số thiết bị do động có tích hợp sẵn tính năng định vị (GPS) qua đó triển khai dịch vụ xác định vị trí hiện thời và chỉ dẫn hướng phải đi để đến được đích mong muốn. Hình 1.13: Minh hoạ dịch vụ dẫn đường - 23 - Các dịch vụ thông tin Dịch vụ tìm kiếm nơi cung cấp các dịch vụ gần nhấn (nhà hàng, khách sạn, trạm xăng,...), truy cập các bản tin giao thông, nhận trợ giúp chỉ đường khi tham gia giao thông ở nơi xa lạ,... là một số ví dụ điển hình nhóm dịch vụ thông tin dựa trên LBS. Ví dụ cụ thể như khi đang tham gia giao thông bằng ô tô, phát hiện xe sắp hết xăng, lái xe có nhu cầu tìm trạm xăng gần nhất để nhanh chóng bơm xăng nếu không muốn để lại xe bên đường để đi bộ vì hết xăng. Lái xe có thể yêu cầu đến trung tâm cung cấp dịch vụ thông tin cho biết vị trí trạm xăng gần nhất. Trung tâm dịch vụ dựa trên vị trí hiện tại của lái xe để đưa ra chỉ dẫn phù hợp. Các dịch vụ quản lý, theo dõi và giám sát Dịch vụ giám sát, theo vết có khả năng ứng dụng đồng thời cho cả hai đối tượng người dùng cá nhân hay một công ty, một tổ chức. Một số ví dụ điển hình như: một công ty taxi muốn giám sát hệ thống các xe của mình, biết chính xác vị trí của các xe để có thể thông báo chính xác và điều xe đến nơi yêu cầu của khách hàng một cách hiệu quả nhất, giảm chi phí (chọn xe rỗi ở gần khách hàng). Ví dụ khác như tình huống cha mẹ muốn giám sát vị trí của con cái để tiện quản lý, theo dõi. Trong trường hợp này cha mẹ có thể yêu cầu hoặc bí mật gắn thiết bị hỗ trợ định vị và khai thác dịch vụ này để thông qua đó xác định vị trí cũng như lộ trình con mình đã đi trong khoảng thời gian nào đó. Hình 1.14: Minh hoạ dịch vụ quản lý, theo dõi và giám sát - 24 - Chương 2: ỨNG DỤNG LOGIC MỜ TRONG TÌM ĐƯỜNG Giới thiệu về tổng quan về logic mờ, một số khái niệm về logic mờ, các thuật toán tìm đường và ứng dụng logic mờ trong bài toán tìm đường. 2.1. Giới thiệu Logic mờ Trong cuộc sống, con người truyền thông tin cho nhau chủ yếu là bằng ngôn ngữ tự nghiên. Ngôn ngữ tự nhiên thường đa nghĩa hoặc thâm chí có lúc còn thiếu tính chính xác, nhưng nó vẫn là phương tiện chính mà con người dùng để truyền thông tin cho nhau. Với khả năng đặc biệt của mình, con người thường vượt qua những hạn chế của ngôn ngữ tự nhiên (đa nghĩa, chiếu chính xác, không rõ ràng) và thường là hiểu đúng các thông tin nhận được. Đây là điều mà máy móc chưa thể thực hiện được. Tham vọng của các nhà khoa học là mong muốn máy móc có khả năng hiểu được ngôn ngữ tự nghiên, có khả năng suy diễn, có khả năng xử lý thông tin tương tự như bộ óc con người, để con người có thể ra lệnh cho máy móc bằng ngôn ngữ tự nhiên, yêu cầu đến sự trợ giúp của máy móc mà qua đó đòi hỏi máy móc phải xử lý các dữ liệu mang nhiều ý nghĩa khác nhau, có khi thiếu tính chính xác, chưa được xác định một cách rõ ràng giống như ngôn ngữ tự nhiên. Ví dụ như chúng ta có thể yêu cầu máy móc chỉ ra một đường đi “tốt nhất” để đi từ vị trí A đến một ví trí B nào đó. Việc có tồn tài một đường đi từ A đến B hay không thường là có thể xác định một cách rõ ràng, thậm chí có thể chỉ ra nhiều đường đi khác nhau để có thể đi từ A đến B. Vấn đề là xác định con đường nào là “tốt nhất” để đi từ A đến B. Ở đây, ngay mệnh đề “tốt nhất” bản thân đã không được xác định một cách rõ ràng, thế nào là tốt nhất. Một con đường tốt có thể là con đường ngắn nhất những cũng có thể không phải vậy. Nếu đường ngắn nhưng dễ xảy ra tắc đường thì chưa hẳn đã là “tốt”, thậm chí còn “tệ” hơn con đường dài nhưng luôn thông suốt. Độ tốt của con đường phụ thuộc vào nhiều yếu tố, có những yếu tố cố định và xác định được ngay từ đầu, nhưng cũng có những yếu tố là chưa xác định và thường xuyên thay đổi ví dụ như yếu tố tắc đường, sự cố bất thường khiến đường đi bị nghẽn,... Để máy móc có thể hiểu và xử lý được những tri thức được diễn đạt bằng ngôn ngữ tự nhiên người ta cần phải xây dựng một lý thuyết logic toán cho phép mô tả chính xác ý nghĩa của các mệnh đề không rõ ràng, đa nghĩa. chẳng hạn như: đường tốt, đượng rộng, đường hẹp, giàu, nghèo, đắt, rẻ,... Năm 1965, Lotti - 25 - Zahden, một nhà toán học và cũng là nhà logic học người Hà Lan, đã xây dựng thành công lý thuyết tập mờ và hệ thống logic mờ. Phát minh này của Lotti Zahden cho phép người ta có thể lượng hóa giá trị các mệnh đề mờ, qua đó có thể truyền đạt một số thông tin cho máy móc bằng ngôn ngữ tự nhiên, có thể yêu cầu máy móc xử lý các dữ liệu mang nhiều thông tin, thiếu tính chính xác, không rõ ràng. 1.1.1. Nhắc lại về tập hợp kinh điển Khái niệm về tâp hợp được hình thành trên nền tảng logic và được G.Cantor định nghĩa như là một sự xếp đặt chung các vật, các đối tượng có cùng một tính chất, được gọi là phần tử của tập hợp đó. Ý nghĩa logic của khái niệm tập hợp được xác định ở chỗ một vật hoặc một đối tượng bất kỳ chỉ có thể có hai khả năng hoặc là phaàn tử của tập đang xét hoặc không [3]. Có nhiều cách để biểu diễn tập hợp. Cách biểu diễn vừa đơn giản lại dễ được chấp nhận nhất là liệt kê các phẩn tử của tập hợp, ví dụ S1 = {0, 2, 4, 6, 8} hay S2 = {nhà, xe, cây} Trong trường hợp không thể liệt kê hết được các phần tử của tập A, người ta có thể chỉ ra những tính chất chính xác mà những phần tử trong tập A phải thoả mãn, chẳng hạn A = {x | x là số tự nhiên}. Tập hợp mà các phần tử của nó có thể được xác định một cách rõ ràng như vậy còn được gọi là “tập rõ”. Với tập hợp A, ánh xạ µA(x): A->R được định nghĩa như sau       Ax nÕu 0 A x nÕu 1 A )(x (1) được gọi là hàm thuộc của tập A. Một tính chất quan trọng nhất của tập rõ mà chúng ta cần chú ý, đó là một tập rõ hoàn toàn được xác định bởi hàm thuộc của nó. Hàm thuộc của tập rõ A được ký hiệu là µA(x), là một hàm chỉ nhận một trong hai giá trị (0/1). Hàm nhận giá trị 1 khi x thuộc tập A và nhận giá trị 0 khi x không thuộc tập A. Các phần tử của tập rõ luôn có một ranh giới rõ ràng giữa các phần tử thuộc và các phần tử không thuộc nó. Một tập X luôn có µA(x)=1, với mọi x được gọi là không gian nền (tập nền). 1.1.2. Khái niệm chung về tập mờ Trong thực tế, có những vấn đề không biểu diễn bằng tập rõ được. Ví dụ như khi nói về vận tốc của một chiếc xe ô tô chạy trên đường, ta cần chỉ ra là xe chạy với “vận tốc cao”, “vận tốc thấp”. Giả sử quy ước vận tốc dưới 40Km/h là vận tốc thấp, trên 60Km/h là vận tốc cao. Như vậy dải vận tốc từ 40Km/h đến - 26 - 60Km/h sẽ thuộc vào vận tốc thấp hay vận tốc cao? Ngay cả quy ước giới hạn vận tốc thấp hay cao tùy từng con đường, thời điểm cũng có thể khác nhau. Như vậy mệnh đề “vận tốc cao”, “vận tốc thấp” không phải là một mệnh đề rõ cho phép xác định một tập rõ. Tương tự như vậy, mệnh đề “người giàu”, “người nghèo”, “người trẻ”, “người già”,... đều không phải là “mệnh đề chính xác”. Trong các trường hợp tương tự như các ví dụ trên người ta sử dụng tập mờ để biểu diễn. Nếu tập rõ được xác định bởi các tính chất chính xác cho phép chúng ta biết một đối tượng là thuộc hay không thuộc tập đã cho và hàm thuộc của tập rõ chỉ nhận hai giá trị 0 hoặc 1, hàm thuộc của tập rõ nhận giá trị là 1 khi đối tượng thuộc tập đã cho; ngược lại, nó sẽ nhận giá trị 0 khi đối tượng không thuộc tập đó. Từ những ví dụ trên cho thấy, các tập mờ có đặc trưng là tính không rõ ràng, không chính xác. Các tập mờ được xác định bởi hàm thuộc mà giá trị của nó là các số thực từ 0 đến 1. Trong tập mờ S, mỗi phần tử được xác định [8]: µS : Ω -> M (2) trong đó µS là hàm xác định phần tử của tập (hàm thành viên - membership function), Ω là tập nền, M là miền giá trị cho phép. Thông thường M lựa chọn trong phạm vi [0,1]. vì vậy công thức (2) có thể viết lại: µS : Ω -> [0,1] (3) Support của tập mờ S, ký hiệu là supp(S), bao gồm các phần tử có bậc tư cách thành viên dương: supp(S) = { x ∈ Ω | μs(x) > 0 } (4) α-cut của tập mờ S được ký hiệu Sα: Sα = { x ∈ Ω | μs(x) ≥ α } (5) Tương tự, α-level cut của tập mờ S, ký hiệu là Sα, là tập con chứa tất cả các phần tử có bậc tư cách thành viên đúng bằng α: - 27 - Sα = { x ∈ Ω | μs(x) = α } (6) 1.1.3. Các phép toán trên tập mờ Các phép toán cơ bản trên tập mờ là phép hợp, phép giao và phép bù [3] [1]. Tương tự như định nghĩa về tập mờ, các phép toán trên tập mờ cũng sẽ được định nghĩa thông qua hàm thuộc (hàm thành viên). Tập mờ S được gọi là rỗng nếu µS(x)=0 với mọi x  X Tập mờ A=B khi µA(x)= µB(x) với mọi x  X Tập mờ AB khi µA(x)< µB(x) với mọi x  X C=AB trong đó µC(x)=min{µA(x), µB(x)} C=AB trong đó µC(x)=max{µA(x), µB(x)} A’ là phần bù của A và µA’(x)=1-µA(x) Minh họa một số phép toán trên tập mờ: Hình 2.1: Minh hoạ phép toán hợp trên tập mờ Hình 2.2: Minh hoạ phép toán giao trên tập mờ 2.2. Các thuật toán tìm đường - 28 - Trong các ứng dụng thực tế, như trong các mạng lưới giao thông đường bộ, đường thuỷ hay đường không. Người ta không chỉ quan tâm đến việc tìm đường đi giữa hai địa điểm mà còn phải lựa chọn một hành trình “tốt nhất” (theo tiêu chuẩn nào đó như không gian, thời gian hay chi phí). Khi đó phát sinh yêu cầu tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị. Trong đó, các đỉnh của đồ thị tương ứng với các điểm nút giao thông, các cạnh của đồ thị tương ứng với các tuyến đường nối các điểm nút giao thông với nhau, độ dài tuyến đường hay kết hợp với các thông số khác như độ rộng, tốc độ cho phép,… đóng vai trò là trọng số của cạnh tương ứng trên đồ thị. Bài toán này phát biểu dưới dạng tổng quát như sau: Cho đồ thị có trọng số G = (V, E), hãy tìm một đường đi ngắn nhất từ đỉnh xuất phát S ∈ V đến đỉnh đích F ∈ V. Độ dài của đường đi này được ký hiệu là d[S, F] và gọi là khoảng cách từ S đến F. Nếu như không tồn tại đường đi từ S tới F thì ta sẽ đặt khoảng cách đó = +∞. Nếu như đồ thị có chu trình âm (chu trình với độ dài âm) thì khoảng cách giữa một số cặp đỉnh nào đó có thể không xác định, bởi vì bằng cách đi vòng theo chu trình này một số lần đủ lớn, ta có thể chỉ ra đường đi giữa hai đỉnh nào đó trong chu trình này nhỏ hơn bất kỳ một số cho trước nào. Trong trường hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản (đường đi không có đỉnh lặp lại) ngắn nhất. Tuy nhiên đây là một vấn đề phức tạp, không nằm trong phạm vi nghiên cứu của đề tài nên không được trình bày cụ thể trong luận văn này. Nếu như đồ thị không có chu trình âm thì ta có thể chứng minh được rằng một trong những đường đi ngắn nhất là đường đi cơ bản. Và nếu như biết được khoảng cách từ S tới tất cả những đỉnh khác thì đường đi ngắn nhất từ S tới F có thể tìm được một cách dễ dàng qua thuật toán sau: - 29 - Gọi c[u, v] là trọng số của cạnh [u, v]. Qui ước c[v, v] = 0 với mọi v ∈ V và c[u, v] = +∞ nếu như (u, v) ∉ E. Đặt d[S, v] là khoảng cách từ S tới v. Để tìm đường đi từ S tới F, ta có thể nhận thấy rằng luôn tồn tại đỉnh F1 ≠ F sao cho: d[S, F] = d[S, F1] + c[F1, F] (Độ dài đường đi ngắn nhất S->F = Độ dài đường đi ngắn nhất S->F1 + Chi phí đi từ F1 tới F) Đỉnh F1 đó là đỉnh liền trước F trong đường đi ngắn nhất từ S tới F. Nếu F1≡S thì đường đi ngắn nhất là đường đi trực tiếp theo cung (S, F). Nếu không thì vấn đề trở thành tìm đường đi ngắn nhất từ S tới F1. Và ta lại tìm được một đỉnh F2 khác F và F1 để: d[S, F1] = d[S, F2] + c[F2, F1] Cứ tiếp tục như vậy, sau một số hữu hạn bước, ta suy ra rằng dãy F, F1, F2, … không chứa đỉnh lặp lại và kết thúc ở S. Lật ngược thứ tự dãy cho ta đường đi ngắn nhất từ S tới F. Tuy nhiên, người ta thường không sử dụng phương pháp này mà sẽ kết hợp lưu vết đường đi ngay trong quá trình tìm kiếm. Sau đây là một số thuật toán tìm đường đi ngắn nhất từ đỉnh S tới đỉnh F trên đơn đồ thị có hướng G = (V, E) có n đỉnh và m cung. Thuật toán Ford-Bellman Thuật toán Ford-Bellman áp dụng trên đồ thị không có chu trình âm và được phát biểu như sau: Với đỉnh xuất phát S. Gọi d[v] là khoảng cách từ S tới v với các giá trị khởi tạo là: d[S] = 0 d[v] = +∞ nếu v ≠ S Sau đó ta tối ưu hoá dần các d[v] như sau: Xét mọi cặp đỉnh u, v của đồ thị, nếu có một cặp đỉnh u, v mà d[v] > d[u]+ c[u, v] thì ta đặt lại d[v] := d[u] + c[u, v]. - 30 - Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ S tới u cộng với chi phí đi từ u tới v thì ta sẽ huỷ bỏ đường đi từ S tới v đang có và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v. Chú ý rằng ta đặt c[u, v] = +∞ nếu (u, v) không là cung. Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa. Tính đúng đắn của thuật toán: Tại bước khởi tạo thì mỗi d[v] chính là độ dài ngắn nhất của đường đi từ S tới v qua không quá 0 cạnh. Giả sử khi bắt đầu bước lặp thứ i (i ≥ 1), d[v] đã bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i - 1 cạnh. Do tính chất: đường đi từ S tới v qua không quá i cạnh sẽ phải thành lập bằng cách: lấy một đường đi từ S tới một đỉnh u nào đó qua không quá i - 1 cạnh, rồi đi tiếp tới v bằng cung (u, v), nên độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh sẽ được tính bằng giá trị nhỏ nhất trong các giá trị (Nguyên lý tối ưu Bellman): Độ dài đường đi ngắn nhất từ S tới v qua không quá i - 1 cạnh Độ dài đường đi ngắn nhất từ S tới u qua không quá i - 1 cạnh cộng với trọng số cạnh (u, v) (∀u) Vì vậy, sau bước lặp tối ưu các d[v] bằng công thức d[v]bước i = min(d[v]bước i-1, d[u]bước i-1+ c[u, v]) (∀u) thì các d[v] sẽ bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh. Sau bước lặp tối ưu thứ n - 1, ta có d[v] = độ dài đường đi ngắn nhất từ S tới v qua không quá n - 1 cạnh. Vì đồ thị không có chu trình âm nên sẽ có một đường đi ngắn nhất từ S tới v là đường đi cơ bản (qua không quá n - 1 cạnh). Tức là d[v] sẽ là độ dài đường đi ngắn nhất từ S tới v. Do vậy số bước lặp tối ưu hoá sẽ không quá n - 1 bước. Trong cài đặt chương trình, nếu mỗi bước lặp được mô tả dưới dạng: for u := 1 to n do - 31 - for v := 1 to n do d[v] := min(d[v], d[u] + c[u, v]); Do sự tối ưu bắc cầu (dùng d[u] tối ưu d[v] rồi lại có thể dùng d[v] tối ưu d[w] nữa…) chỉ làm tốc độ tối ưu nhãn d[v] tăng nhanh hơn nên số bước lặp tối ưu nhãn vẫn sẽ không quá n - 1 bước. Thuật toán Dijkstra Trong trường hợp trọng số trên các cung không âm, thuật toán do Dijkstra đề xuất dưới đây hoạt động hiệu quả hơn nhiều so với thuật toán Ford-Bellman. Ta hãy xem trong trường hợp này, thuật toán Ford-Bellman thiếu hiệu quả ở chỗ nào: Với đỉnh v ∈ V, Gọi d[v] là độ dài đường đi ngắn nhất từ S tới v. Thuật toán Ford-Bellman khởi gán d[S] = 0 và d[v] = +∞ với ∀v ≠ S, sau đó tối ưu hoá dần các nhãn d[v] bằng cách sửa nhãn theo công thức: d[v] := min(d[v], d[u] + c[u, v]) với ∀u, v ∈ V. Như vậy nếu như ta dùng đỉnh u sửa nhãn đỉnh v, sau đó nếu ta lại tối ưu được d[u] thêm nữa thì ta cũng phải sửa lại nhãn d[v] dẫn tới việc d[v] có thể phải chỉnh đi chỉnh lại rất nhiều lần. Vậy nên chăng, tại mỗi bước không phải ta xét mọi cặp đỉnh (u, v) để dùng đỉnh u sửa nhãn đỉnh v mà sẽ chọn đỉnh u là đỉnh mà không thể tối ưu nhãn d[u] thêm được nữa. Thuật toán Dijkstra có thể mô tả như sau: Bước 1: Khởi tạo - 32 - Với đỉnh v ∈ V, gọi nhãn d[v] là độ dài đường đi ngắn nhất từ S tới v. Ta sẽ tính các d[v]. Ban đầu d[v] được khởi gán như trong thuật toán Ford-Bellman (d[S] = 0 và d[v] = ∞ với ∀v ≠ S). Nhãn của mỗi đỉnh có hai trạng thái tự do hay cố định, nhãn tự do có nghĩa là có thể còn tối ưu hơn được nữa và nhãn cố định tức là d[v] đã bằng độ dài đường đi ngắn nhất từ S tới v nên không thể tối ưu thêm. Để làm điều này ta có thể sử dụng kỹ thuật đánh dấu: Free[v] = TRUE hay FALSE tuỳ theo d[v] tự do hay cố định. Ban đầu các nhãn đều tự do. Bước 2: Lặp Bước lặp gồm có hai thao tác: 1. Cố định nhãn: Chọn trong các đỉnh có nhãn tự do, lấy ra đỉnh u là đỉnh có d[u] nhỏ nhất, và cố định nhãn đỉnh u. 2. Sửa nhãn: Dùng đỉnh u, xét tất cả những đỉnh v và sửa lại các d[v] theo công thức: d[v] := min(d[v], d[u] + c[u, v]) Bước lặp sẽ kết thúc khi mà đỉnh đích F được cố định nhãn (tìm được đường đi ngắn nhất từ S tới F); hoặc tại thao tác cố định nhãn, tất cả các đỉnh tự do đều có nhãn là +∞ (không tồn tại đường đi). Có thể đặt câu hỏi, ở thao tác 1, tại sao đỉnh u như vậy được cố định nhãn, giả sử d[u] còn có thể tối ưu thêm được nữa thì tất phải có một đỉnh t mang nhãn tự do sao cho d[u] > d[t] + c[t, u]. Do trọng số c[t, u] không âm nên d[u] > d[t], trái với cách chọn d[u] là nhỏ nhất. Tất nhiên trong lần lặp đầu tiên thì S là đỉnh được cố định nhãn do d[S] = 0. Bước 3: Kết hợp với việc lưu vết đường đi trên từng bước sửa nhãn, thông báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (d[F] = +∞). Thuật toán Dijkstra sử dụng cấu trúc Heap - 33 - Nếu đồ thị có nhiều đỉnh, ít cạnh, ta có thể sử dụng danh sách kề kèm trọng số để biểu diễn đồ thị, tuy nhiên tốc độ của thuật toán Dijkstra vẫn khá chậm vì trong trường hợp xấu nhất, nó cần n lần cố định nhãn và mỗi lần tìm đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O(n). Để tăng tốc độ, người ta thường sử dụng cấu trúc dữ liệu Heap để lưu các đỉnh chưa cố định nhãn. Heap ở đây là một cây nhị phân hoàn chỉnh thoả mãn: Nếu u là đỉnh lưu ở nút cha và v là đỉnh lưu ở nút con thì d[u] ≤ d[v]. (Đỉnh r lưu ở gốc Heap là đỉnh có d[r] nhỏ nhất). Tại mỗi bước lặp của thuật toán Dijkstra có hai thao tác: Tìm đỉnh cố định nhãn và Sửa nhãn. Với mỗi đỉnh v, gọi Pos[v] là vị trí đỉnh v trong Heap, quy ước Pos[v] = 0 nếu v chưa bị đẩy vào Heap. Mỗi lần có thao tác sửa đổi vị trí các đỉnh trên cấu trúc Heap, ta lưu ý cập nhập lại mảng Pos này. Thao tác tìm đỉnh cố định nhãn sẽ lấy đỉnh lưu ở gốc Heap, cố định nhãn, đưa phần tử cuối Heap vào thế chỗ và thực hiện việc vun đống (Adjust). Thao tác sửa nhãn, sẽ duyệt danh sách kề của đỉnh vừa cố định nhãn và sửa nhãn những đỉnh tự do kề với đỉnh này, mỗi lần sửa nhãn một đỉnh nào đó, ta xác định đỉnh này nằm ở đâu trong Heap (dựa vào mảng Pos) và thực hiện việc chuyển đỉnh đó lên (UpHeap) phía gốc Heap nếu cần để bảo toàn cấu trúc Heap. Thuật toán A* Xét bài toán tìm đường - bài toán mà A* thường được dùng để giải. A* xây dựng tăng dần tất cả các tuyến đường từ điểm xuất phát cho tới khi nó tìm thấy một đường đi chạm tới đích. Tuy nhiên, cũng như tất cả các thuật toán tìm kiếm có thông tin, nó chỉ xây dựng các tuyến đường "có vẻ" dẫn về phía đích. Để biết những tuyến đường nào có khả năng sẽ dẫn tới đích, A* sử dụng một "đánh giá heuristic" về khoảng cách từ điểm bất kỳ cho trước tới đích. Trong trường hợp tìm đường đi, đánh giá này có thể là khoảng cách đường chim bay - một đánh giá xấp xỉ thường dùng cho khoảng cách của đường giao thông. Điểm khác biệt của A* đối với tìm kiếm theo lựa chọn tốt nhất là nó còn tính đến khoảng cách đã đi qua. Điều đó làm cho A* "đầy đủ" và "tối ưu", nghĩa là, A* sẽ luôn luôn tìm thấy đường đi ngắn nhất nếu tồn tại một đường đi như thế. A* không đảm bảo sẽ chạy nhanh hơn các thuật toán tìm kiếm đơn giản hơn. Trong một môi trường dạng mê cung, cách duy nhất để đến đích có thể là trước hết phải đi về phía xa đích và cuối cùng mới quay lại. Trong trường hợp - 34 - đó, việc thử các nút theo thứ tự "gần đích hơn thì được thử trước" có thể gây tốn thời gian. Thuật toán có thể mô tả như sau: A* lưu giữ một tập các lời giải chưa hoàn chỉnh, nghĩa là các đường đi qua đồ thị, bắt đầu từ nút xuất phát. Tập lời giải này được lưu trong một hàng đợi ưu tiên (priority queue). Thứ tự ưu tiên gán cho một đường đi x được quyết định bởi hàm f(x) = g(x) + h(x). Trong đó, g(x) là chi phí của đường đi cho đến thời điểm hiện tại, nghĩa là tổng trọng số của các cạnh đã đi qua. h(x) là hàm đánh giá heuristic về chi phí nhỏ nhất để đến đích từ x. Ví dụ, nếu "chi phí" được tính là khoảng cách đã đi qua, khoảng cách đường chim bay giữa hai điểm trên một bản đồ là một đánh giá heuristic cho khoảng cách còn phải đi tiếp. Hàm f(x) có giá trị càng thấp thì độ ưu tiên của x càng cao (do đó có thể sử dụng một cấu trúc heap tối thiểu để cài đặt hàng đợi ưu tiên này). function A*(điểm_xuất_phát,đích) var đóng := tập rỗng var q := tạo_hàng_đợi(tạo_đường_đi(điểm_xuất_phát)) while q không phải tập rỗng var p := lấy_phần_tử_đầu_tiên(q) var x := nút cuối cùng của p if x in đóng continue if x = đích return p bổ sung x vào tập đóng for each y in các_đường_đi_tiếp_theo(p) đưa_vào_hàng_đợi(q, y) return failure Trong đó, các_đường_đi_tiếp_theo(p) trả về tập hợp các đường đi tạo bởi việc kéo dài p thêm một nút kề cạnh. Giả thiết rằng hàng đợi được sắp xếp tự động bởi giá trị của hàm f. "Tập hợp đóng" (đóng) lưu giữ tất cả các nút cuối cùng của p (các nút mà các đường đi mới đã được mở rộng tại đó) để tránh việc lặp lại các chu trình (việc này cho ra thuật toán tìm kiếm theo đồ thị). Đôi khi hàng đợi được gọi một - 35 - cách tương ứng là "tập mở". Tập đóng có thể được bỏ qua (ta thu được thuật toán tìm kiếm theo cây) nếu ta đảm bảo được rằng tồn tại một lời giải hoặc nếu hàm các_đường_đi_tiếp_theo được chỉnh để loại bỏ các chu trình. Giống như tìm kiếm theo chiều rộng (breadth-first search), A* là thuật toán đầy đủ theo nghĩa nó sẽ luôn luôn tìm thấy một lời giải nếu bài toán có lời giải. Nếu hàm heuristic h có tính chất thu nạp được, nghĩa là nó không bao giờ đánh giá cao hơn chi phí nhỏ nhất thực sự của việc đi tới đích, thì bản thân A* có tính chất thu nạp được (hay tối ưu) nếu sử dụng một tập đóng. Nếu không sử dụng tập đóng thì hàm h phải có tính chất đơn điệu (hay nhất quán) thì A* mới có tính chất tối ưu. Nghĩa là nó không bao giờ đánh giá chi phí đi từ một nút tới một nút kề nó cao hơn chi phí thực. Phát biểu một cách hình thức, với mọi nút x, y trong đó y là nút tiếp theo của x: h(x) ≤ g(y) – g(x) + h(y) A* còn có tính chất hiệu quả một cách tối ưu với mọi hàm heuristic h, có nghĩa là không có thuật toán nào cũng sử dụng hàm heuristic đó mà chỉ phải mở rộng ít nút hơn A*, trừ khi có một số lời giải chưa đầy đủ mà tại đó h dự đoán chính xác chi phí của đường đi tối ưu. Độ phức tạp thuật toán: Độ phức tạp thời gian của A* phụ thuộc vào đánh giá heuristic. Trong trường hợp xấu nhất, số nút được mở rộng theo hàm mũ của độ dài lời giải, nhưng nó sẽ là hàm đa thức khi hàm heuristic h thỏa mãn điều kiện sau: | h(x) – h*(x)| ≤ O(log h*(x)) trong đó h * là heuristic tối ưu, nghĩa là hàm cho kết quả là chi phí chính xác để đi từ x tới đích. Nói cách khác, sai số của h không nên tăng nhanh hơn lôgarit của "heuristic hoàn hảo" h * - hàm trả về khoảng cách thực từ x tới đích. Vấn đề sử dụng bộ nhớ của A* còn rắc rối hơn độ phức tạp thời gian. Trong trường hợp xấu nhất, A* phải ghi nhớ số lượng nút tăng theo hàm mũ. Một số biến thể của A* đã được phát triển để đối phó với hiện tượng này, một trong số đó là A* lặp sâu dần (iterative deepening A*), A* bộ nhớ giới hạn (memory-bounded A* - MA*) và A* bộ nhớ giới hạn đơn giản (simplified memory bounded A*). Thuật toán Dijkstra là một trường hợp đặc biệt của A* trong đó đánh giá heuristic là một hàm hằng h(x) = 0 với mọi x. - 36 - Một thuật toán tìm kiếm có thông tin khác cũng có tính chất tối ưu và đầy đủ nếu đánh giá heuristic của nó là thu nạp được. Đó là tìm kiếm đệ quy theo lựa chọn tốt nhất (recursive best-first search - RBFS). 2.3. Ứng dụng logic mờ trong bài toán tìm đường Xem xét một đồ thị mờ G với tập đỉnh mờ V [8]. Gọi  là tập tất cả các đường đi từ đỉnh va tới đỉnh vb (hình 2.3) và độ dài “mờ” của tuyến đường được tính theo công thức: (7) với P  , ek là các cạnh của G. Tập mờ các đường đi ngắn nhất là tập mờ S trên  với hàm thành viên S cho bởi công thức: (8) với P  , Q  . Support bao gồm tất cả các đường đi có thể với độ dài tối thiểu (9) Hình 2.3: Đồ thị mờ G minh hoạ thuật toán FSA Thuật toán đường đi ngắn nhất “mờ” (Fuzzy Shortest Path Algorithm - FSA) được mô tả như sau: Bước 1: tạo các đồ thịG và G đồng nhất với G và trọng số trên các cạnh của G và G có thể được tính như sau: Với G : )}supp(sup{ a a (10) Với G : )}supp(inf{ a a (11) - 37 - Bước 2: Tìm đường đi ngắn nhất p từ va đến vb trong G , vấn đề tìm đường đi ngắn nhất có thể được giải quyết bởi một trong số các thuật toán tìm đường đi ngắn nhất. Gọi k là độ dài của đường đi p. Bước 3: Gọi S là tập tất cả các đường đi từ va đến vb trong G , có độ dài nhỏ hơn k. Gọi S là tập tất cả các đường đi trong G. Hình ảnh các đường đi này trong cả S và S là tương đồng. Vì thế, S là tập tất cả các đường đi mờ ngắn nhất. Cuối cùng tính hàm thành viên cho mỗi đường đi mờ trong S có tính đến k. Hình 2.3 biểu diễn trọng số của đồ thị mờ. Đỉnh a là đỉnh xuất phát và f là đỉnh kết thúc của đường đi. Trọng số có thể chỉ là một số hoặc bộ ba số “mờ”. Độ dài mờ cho 4 đường đi từ a đến f được của đồ thị biểu diễn treen hình 2.3 – với k=8 – là các đường abdf có hàm thành viên S(abdf)=1, đường đi abef có hàm thành viên S(abef)=2/5, và các đường khác có hàm thành viên S(acdf)=S(acef)=0 trong tập các đường đi mờ ngắn nhất. Hình 2.4 minh hoạ các đường đi mờ ngắn nhất này. Hình 2.4: Các đường đi mờ ngắn nhất của đồ thị mờ G - 38 - Chương 3: THIẾT KẾ DỊCH VỤ LBS Giới thiệu tổng quan một số mô hình dịch vụ LBS, phân tích đặc điểm, ưu và nhược điểm của mỗi mô hình. Lựa chọn và triển khai thiết kế dịch vụ LBS tìm đường đi trong thành phố. 3.1. Mục tiêu thiết kế Việc thiết kế dịch vụ LBS thử nghiệm nhằm mục tiêu thứ nhất là thể hiện các kết quả nghiên cứu về LBS, cách thức triển khai một dịch vụ LBS trong thực tế. Mục tiêu thứ hai nhằm xây dựng lên một mô hình triển khai dịch vụ LBS có khả năng đáp ứng tối đa nhu cầu của người dùng trong điều kiện hạn chế về cơ sở hạ tầng, tài chính của việc ứng dụng dịch vụ LBS tại Việt Nam (như mạng truyền thông chậm, băng thông hẹp, giá dịch vụ còn cao, thiết bị lạc hậu...) ở thời điểm hiện tại và trong tương lai gần sắp tới. Sản phẩm minh hoạ là dịch vụ tìm đường đi trong thành phố. 3.2. Các mô hình dịch vụ thiết kế 3.2.1. Mô hình triển khai trên nền dịch vụ web Mô hình này đòi hỏi cả phía cung cấp dịch vụ (máy chủ) và phía khai thác dịch vụ (máy khách) phải có cấu hình phần cứng đủ mạnh, khả năng xử lý tốt. Các thành phần chính trong mô hình này bao gồm: Máy chủ cung cấp dịch vụ, Máy khách, Môi trường truyền thông. Máy chủ cung cấp dịch vụ: là máy tính cung cấp dịch vụ thông tin, máy chủ vừa đóng vai trò máy chủ cung cấp dịch vụ web đồng thời là nơi quản lý thông tin sẽ cung cấp cho máy khách. Máy khách: là các thiết bị di động có khả năng khai thác dịch vụ web như PDA, thiết bị chuyên dụng, Smart phone cũng như các loại điện thoại di động tích hợp khả năng khai thác dịch vụ web. Trong thực tế chỉ cần máy khách có khả năng kết nối Internet kèm theo trình duyệt web là cơ bản đáp ứng được yêu cầu. Tuy nhiên do dữ liệu hiển thị kèm theo hình ảnh thường chiếm dụng nhiều bộ nhớ nên để đáp ứng tốt cho yêu cầu khai thác thì bộ nhớ còn trống phía máy khách cũng phải đủ lớn. - 39 - Hình 3.1: Mô hình dịch vụ LBS trên nền Web Môi trường truyền thông: do dịch vụ được triển khai trên nền web nên môi trường được sử dụng là Internet. Các thiết bị khai thác dịch vụ thông qua mạng Internet. Tuỳ thuộc thiết kế của thiết bị phía khách mà đường truyền vật lý cũng như cách thức truy cập có thể khác nhau như: sử dụng mạng không dây wifi (PDA, một số dòng máy Smart phone,..), sử dụng GPRS trên các loại điện thoại di động có hỗ trợ công nghệ này. Dịch vụ định vị: các máy khách khai thác dịch vụ định vị để xác định vị trí của mình và gửi kèm theo yêu cầu đến máy chủ. Trên cơ sở đó máy chủ sẽ đáp ứng yêu cầu dựa trên vị trí địa lý của máy khách. Máy khách có thể khai thác dịch vụ định vị toàn cầu GPS hay dịch vụ định vị dựa trên cở sở mạng di động. Thậm chí, nếu máy khách không có khả năng khai thác các dịch vụ này thì vị trí có thể được nhập thủ công bởi người sử dụng thông qua giao diện phần mềm phía máy khách (nhập toạ độ dưới dạng số, xác định vị trí trên bản đồ được hiển thị ở máy khách,...). Thiết bị di động - PDA... - Smart phone, mobi phone... Mạng Interrnet Máy chủ cung cấp dịch vụ - Webserver - GIS Wifi, GPRS,... Dịch vụ định vị Thông tin vị trí - 40 - Một số đặc điểm chính của mô hình này: - Giao diện người dùng, dữ liệu, thông tin được thể hiện trên nền web - Môi trường truyền tải thông tin chính là Internet - Máy chủ phải có cấu hình đủ mạnh để cung cấp dịch vụ và lưu trữ dữ liệu - Máy khách cần có cấu hình đủ mạnh để có thể duyệt web và thể hiện thông tin dưới dạng hình ảnh (bản đồ). Ưu điểm: Do được triển khai trên nền web nên có khả năng cung cấp dịch vụ phong phú, tính tương thích cao (ít phụ thuộc vào nền tảng phần cứng hay phần mềm). Dữ liệu có thể được biểu diễn trực quan bằng hình ảnh, kết hợp văn bản, thậm chí cả âm thanh. Nhược điểm: Đòi hỏi máy chủ phải có cấu hình đủ mạnh. Mách khách cũng phải có cấu hình mạnh với khả năng kết nối Internet, hỗ trợ trình duyệt web. Theo yêu cầu này, một số loại máy điện thoại cấu hình thấp nhưng đang được sử dụng khá phổ biến hiện nay khó có thể khai thác được dịch vụ. Đòi hỏi tốc độ truyền dữ liệu cao, băng thông lớn. 3.2.2. Mô hình triển khai dựa trên dịch vụ SMS Khác với mô hình đã giới thiệu ở trên, dịch vụ triển khai trong mô hình này không dựa trên nền web, mạng Internet mà chủ yếu dựa vào mạng truyền thông GSM (dịch vụ SMS). Máy chủ cung cấp dịch vụ cũng như máy khách khai thác dịch vụ đều phải có khả năng gửi nhận thông tin qua mạng GSM. - Máy chủ: là máy tính tiếp nhập và đáp ứng các yêu cầu dịch vụ từ phía máy khách. Máy chủ là nơi lưu dữ các dữ liệu bản đồ, các thông tin dịch vụ. Phần mềm cung cấp dịch vụ tại máy chủ đảm nhiệm chức năng xử lý chính, kết quả cuối cùng mới gửi cho máy khách. Máy chủ được kết nối với máy khách thông qua mạng di động GSM với các gói dữ liệu SMS. Như vậy yêu cầu máy chủ phải có GSM Modem hay - 41 - thiết bị có vai trò tương tự để kết nối được vào mạng GSM, sử dụng dịch vụ SMS của nhà cung cấp dịch vụ truyền thông di động nào đó. Hình 3.2: Mô hình dịch vụ LBS trên dịch vụ tin nhắn SMS - Máy khách: thông thường là các loại điện thoại di động, smart phone hay các PDA có khả năng đàm thoại, gửi nhận tin nhắn SMS. Nếu là máy tính hay thiết bị chuyên dụng khác thì yêu cầu phải có khả năng gửi nhận tin nhắn SMS. Yêu cầu khác về phần cứng phía máy khách tuỳ thuộc lựa chọn giao diện phần mềm sử dụng. Nếu giao diện phần mềm phía máy khách chỉ thuần tuý trình diễn các số liệu dưới dạng văn bản thì không đòi hỏi cấu hình cao (máy điện thoại thông thường có khả năng cài đặt bổ sung phần mềm là được). Trong trường hợp giao diện yêu cầu phải thể hiện dữ liệu trực quan dưới dạng hình ảnh (bản đồ), biểu diễn vị trí, các kết quả xử lý bằng đồ hoạ thì đòi hỏi máy khách có cấu hình mạnh và bộ nhớ đủ lớn để lưu trữ dữ liệu hình ảnh, Thiết bị di động - PDA... - Smart phone, mobi phone... Mạng GSM Máy chủ cung cấp dịch vụ - Webserver - GIS SMS Dịch vụ định vị Thông tin vị trí SMS - 42 - âm thanh (dữ liệu này được chuẩn bị sẵn và lưu trữ cố định trên máy khách ngay khi cài đặt phần mềm cho máy khách). - Môi trường truyền thông: mô hình này sử dụng dịch vụ SMS của mạng GSM để truyền dữ liệu. Khả năng khai thác dịch vụ SMS là mặc định cho hầu hết các thiết bị đàm trong mạng truyền thông di động. - Dịch vụ định vị: theo mô hình này, máy khách cần thiết phải cung cấp vị trí địa lý của mình kèm theo yêu cầu đến máy chủ tương tự như mô hình triển khai trên nền web đã giới thiệu ở trên. Một số đặc điểm chính của mô hình này: - Môi trường truyền tải thông tin chính là mạng SMS, băng thông hẹp - Máy chủ ngoài khả năng lưu trữ dữ liệu, xử lý, đáp ứng các yêu cầu dịch vụ đến từ máy khách còn phải có khả năng kết nối và khai thác dịch vụ của mạng GSM - Cấu hình yêu cầu phía máy khách khá linh hoạt, tuỳ thuộc lựa chọn giao diện, chất lượng dịch vụ. Ưu điểm: Yêu cầu về phần cứng nói chung và môi trường truyền thông là đơn giản. Mô hình này dễ triển khai rộng do yêu cầu phần cứng cho máy khách linh hoạt, các máy cấu hình thấp cũng có thể đáp ứng được. Nhược điểm: Tốc độ thấp và băng thông sử dụng hẹp nên khó triển khai được các dịch vụ chất lượng cao. Trong trường hợp muốn triển khai dịch vụ chất lượng cao cần phải trang bị máy khách có cấu hình mạnh (khả năng xử lý tốt, bộ nhớ lớn). Yêu cầu cài đặt giao diện phía máy khách trên từng máy, phụ thuộc nhiều vào cấu hình phần cứng và hệ điều hành của máy khách. 3.2.3. Mô hình kết hợp dịch vụ web và SMS Hai mô hình dịch vụ triển khai trên nền web và mô hình dựa trên SMS được giới thiệu ở trên đều có các ưu nhược điểm riêng. Việc kết hợp hai mô hình này sẽ mang lại một mô hình dịch vụ mới linh hoạt, phát huy được các ưu điểm của mỗi mô hình riêng lẻ đồng thời giúp hạn chế bớt các nhược điểm. Đặc - 43 - biệt là khả năng đáp ứng nhu cầu khai thác dịch vụ cho máy khách sẽ được nâng cao vì không đòi hỏi khắt khe về yêu cầu phần cứng phía máy khách. Mô hình kết hợp này sẽ cung cấp dịch vụ qua mạng Internet dựa trên công nghệ web đồng thời cho phép người dùng có thể khai thác dịch vụ thông qua tin nhắn SMS. Hình 3.3: Mô hình dịch vụ LBS trên nền Web và SMS Mạng GSM SMS Thiết bị di động - PDA... - Smart phone, mobi phone... Máy chủ cung cấp dịch vụ - Webserver - GIS Thông tin vị trí Dịch vụ định vị SMS Mạng Internet - 44 - 3.3. Dịch vụ tìm đường đi trong thành phố 3.3.1. Mục tiêu Nội thành thành phố Hà Nội, nơi có mật độ dân cứ đông đúc, nhiều trung tâm thương mại, dịch vụ với lượng người tham gia giao thông rất lớn. Thêm vào đó, hệ thống cơ sở hạ tầng giao thông còn nhiều hạn chế, chưa đáp ứng tốt nhu cầu người dân cho nên hiện tượng tắc đường xảy ra thường xuyên mỗi ngày, ở nhiều nơi, đặc biệt là vào các giờ cao điểm. Dịch vụ tìm đường đi trong thành phố nhằm mục tiêu cung cấp dịch vụ hỗ trợ người tham gia giao thông trong nội thành thành phố Hà Nội. Thông qua dịch vụ, họ có thể sử dụng điện thoại di động hay các thiết bị truyền thông di động khác có cấu hình phù hợp để tìm đường đi “tốt nhất” từ một vị trí xuất phát nào đó (có thể là vị trí hiện tại của người tham gia giao thông) đến vị trí đích. Vấn đề đặt ra là con đường “tốt nhất” tìm được thường chịu tác động của nhiều yếu tố khác nhau do đó có ảnh hưởng nhiều đến kết quả tìm kiếm. Dịch vụ không chỉ đơn thuần là tìm ra một đường đi mà còn phải tính đến các yếu tố như đường đi hiện tại có bị tắc hay không, nguy cơ tắc đường, mật độ người và phương tiện lưu thông,... Người khai thác dịch vụ có thể sử dụng điện thoại, thiết bị hỗ trợ cá nhân kỹ thuật số (PDA), thậm chí máy tính xách tay để gửi yêu cầu tìm đường đi và nhận kết quả trả về. Trong điều kiện lý tưởng là điện thoại thông minh có tính năng khai thác dữ liệu định vị toàn cầu (tích hợp thiết bị thu GPS), hỗ trợ duyệt web, hiển thị bản đồ số với bộ nhớ và khả năng tính toán đủ mạnh, đáp ứng được yêu cầu phần mềm. Hệ thống dịch vụ thường xuyên cập nhật các số liệu trạng thái hiện hành các điểm nút, các tuyến giao thông để cung cấp dịch vụ cho người dùng. 3.3.2. Kiến trúc tổng quan của hệ thống Hệ thống xây dựng dựa theo mô hình phối hợp sử dụng công nghệ web, mạng Internet với hệ thống thông tin di động GSM thông qua dịch vụ SMS. Theo đó, hệ thống bao gồm các thành phần chính sau: - Hệ thống máy chủ, nơi tiếp nhận yêu cầu và cung cấp các dịch vụ thông tin. - Hệ thống máy khách: là các loại điện thoại di động, PDA hay các thiết bị di động cầm tay khác có khả năng khai thác dịch vụ web, SMS. - 45 - - Mạng truyền thông: sử dụng mạng Internet, mạng thông tin di động GSM với dịch vụ SMS. - Dịch vụ định vị: khai thác dịch vụ định vị toàn cầu GPS. Kiến trúc hệ thống được biểu diễn trên hình 3.4: Hình 3.4: Kiến trúc tổng quan hệ thống cung cấp dịch vụ tìm đường MẠNG TRUYỀN THÔNG Internet GSM Yêu cầu Thông tin lộ trình Thông tin lộ trình Yêu cầu Vị trí Dịch vụ định vị toàn cầu HỆ THỐNG MÁY KHÁCH HỆ THỐNG MÁY CHỦ - 46 - 3.3.3. Phần cứng hệ thống Máy chủ Máy chủ là máy tính có cấu hình đủ mạnh trên đó có cài đặt phần mềm cung cấp dịch vụ web (webserver), phần mềm tiếp nhận và xử lý các yêu cầu dịch vụ thông qua hệ thống tin nhắn SMS, kết nối Internet. Máy chủ tích hợp sẵn hoặc có mô đun bổ sung khả năng giao tiếp trong mạng GSM để nhận và gửi tin nhắn SMS. Máy chủ được lắp đặt tại trung tâm quản lý và cung cấp dịch vụ. Máy trạm Máy trạm (máy khách) là các thiết bị di động có khả năng khai thác dịch vụ web hay dịch vụ SMS. Máy khách có thể là các loại điện thoại thường (chỉ nghe gọi, gửi nhận tin nhắn SMS), các loại điện thoại thông minh (có hệ điều hành với khả năng cài đặt phần mềm, truy cập Web, tích hợp bộ thu GPS), các thiết bị hỗ trợ cá nhân kỹ thật số PDA, thậm chí có thể là laptop hay thiết bị chuyên dụng có thiết kế phù hợp yêu cầu khai thác dịch vụ. Máy trạm được người tham gia giao thông tự trang bị và mang theo trong quá trình tham gia giao thông và khai thác dịch vụ. 3.3.4. Cơ sở hạ tầng mạng truyền thông Mạng Internet cung cấp kết nối và dịch vụ web. Máy chủ kết nối vào mạng Internet bằng các loại đường truyền thường dùng trong mạng máy tính. Riêng với thiết bị di động, kết nối tới Internet có thể được thực hiện thông qua dịch vụ GPRS hay có thể là GSM Data. Kết nối Internet qua GPRS hay GSM Data nhìn chung cho tốc độ thấp (GSM: 9,6-14 kbps, GPRS: 20-110 kbps), không đủ đáp ứng nhu cầu tương tác bản đồ [2]. Do vậy, việc hiển thị bản đồ để có chất lượng hình ảnh tốt và tốc độ cao thì cần do máy khách đảm nhiệm. Nếu dữ liệu hình ảnh được truyền tải thường xuyên trong quá trình khai thác dịch vụ có thể phải chấp nhận tốc độ chậm, chất lượng hình ảnh không cao. Mạng GSM với dịch vụ SMS cho phép máy khách gửi yêu cầu và tiếp nhận thông tin khá nhanh nhưng chỉ thuần tuý văn bản. Yêu cầu gửi đi và kết quả trả về được thực hiện thông qua các bản tin SMS. Trong trường hợp khai thác dịch vụ SMS để liên lạc giữa máy khách và máy chủ thì phía máy khách phải đảm nhiệm chức năng hiển thị bản đồ số, như vậy mới cho chất lượng dịch vụ cao trong điều kiện hạn chế về tốc độ và băng thông của mạng truyền dữ liệu. - 47 - 3.3.5. Định vị Máy khách có trách nhiệm cung cấp vị trí của mình cùng với yêu cầu cho máy chủ. Vị trí của máy khách có thể nhận được thông qua hệ thống định vị toàn cầu GPS nếu máy có tích hợp sẵn bộ thu GPS. Trong trường hợp máy khách không có khả năng xác định vị trí thông qua dịch vụ GPS thì người sử dụng phải nhập vị trí vào máy để gửi đến cho máy chủ. Vị trí có thể được nhập vào theo nhiều cách khác nhau: toạ độ chính xác, tên địa danh, giao lộ, tuyến phố hay có thể chỉ định ngay trên bản đồ nếu máy khách có khả năng hiển thị dữ liệu bản đồ số và cho phép người dùng tương tác trên bản đồ này. 3.3.6. Cơ sở dữ liệu GIS Tại máy chủ sẽ lưu trữ toàn bộ dữ liệu mà hệ thống khai thác để cung cấp các dịch vụ cho máy khách. Các dữ liệu này bao gồm bản đồ số nội thành thành phố Hà Nội, các dữ liệu về trạng thái hiện hành các tuyến đường, nút giao thông. Hệ thống giao thông trong thành phố được biểu diễn thông qua một đồ thị có trọng số. Trong đó, các tuyến đường là các cạnh của đồ thị, các nút giao thông, các điểm giao cắt là các đỉnh của đồ thị. Trọng số trên các cạnh được tạo bằng cách phối hợp các yếu tố về độ rộng của đường (khả năng đáp ứng cho các loại phương tiện khác nhau như xe máy hay ô tô), mật độ người tham gia giao thông trên tuyến đường, tình trạng tắc đường. Chiều được phép lưu thông trên đường xác định chiều của cạnh. Ngoài trọng số trên các cạnh, ở đồ thị biểu diễn hệ thống giao thông này còn lưu ý đến tính chất của từng đỉnh. Do các đỉnh biểu diễn các giao lộ, các nút giao thông nên vào những thời điểm bị tắc đường hay mật độ giao thông trên nút quá lớn sẽ ảnh hưởng tới quyết định có chọn đường đi qua nút đó hay không. 3.3.7. Các kiểu dịch vụ và cách khai thác 1) Kiểu thứ nhất: áp dụng cho các thiết bị di động có khả năng kết nối Internet, duyệt web, tích hợp bộ thu GPS. Mách khách truy cập vào trang web của hệ thống theo địa chỉ đã công bố. Trang web hiển thị giao diện chính là bản đồ số thành phố Hà Nội, các công cụ hỗ trợ. Thiết bị thu GPS sẽ giúp xác định vị trí hiện hành và được biểu diễn ngay trên bản đồ. - 48 - Người dùng khởi động chức năng tìm đường, sử dụng thiết bị trỏ hoặc nhập tên địa điểm cần đến, yêu cầu tìm. Quá trình tìm kiếm được thực hiện trên máy chủ và kết quả trả về sẽ là hình ảnh bản đồ chỉ ra đường đi tốt nhất theo yêu cầu tìm kiếm hoặc thông báo không tìm được nếu không tồn tại đường đi thoả mãn yêu cầu. Ngoài biểu thị kết quả trên bản đồ, phần mềm sẽ liệt kê danh sách các cung đường phải qua, độ dài tương ứng. Hình 3.5: Minh hoạ giao diện hỗ trợ GPS, hiển thị bản đồ số Ưu nhược điểm chính: về ưu điểm, không đòi hỏi máy khách phải có cấu hình lớn (bộ nhớ, tốc độ xử lý), có tính cập nhật cao (luôn thể hiện được bản đồ mới nhất). Nhược điểm chính là tốc độ đáp ứng chậm do thường xuyên phải truyền tải dữ liệu bản đồ số qua mạng truyền thông. Để nâng cao chất lượng dịch vụ đòi hỏi phải nâng cao tốc độ cũng như mở rộng băng thông của hệ thống truyền thông. 2) Kiểu thứ hai: áp dụng cho các thiết bị di động có cấu hình mạnh, bộ nhớ lớn, có khả năng kết nối Internet hay khai thác dịch vụ SMS, tích hợp bộ thu GPS. Về giao diện chính cũng là bản đồ thành phố nhưng toàn bộ dữ liệu bản đồ được lưu trên thiết bị di động. - 49 - Dữ liệu được truyền tải qua lại chỉ là yêu cầu dịch vụ và kết quả là danh sách các nút phải đi qua (thông qua tin nhắn SMS). Dựa vào dữ liệu trả về, giao diện phía máy khách sẽ thể hiện trực quan lộ trình tìm được trên bản đồ số. Các thao tác vận hành về cơ bản giống như kiểu thứ nhất. Một số ưu nhược điểm chính: tốc độ đáp ứng cao do không phải truyền tài dữ liệu lớn qua mạng truyền thông, bản đồ có thể trình bày được chi tiết và đẹp hơn. Nhược điểm chính là đòi hỏi máy trạm phải có bộ nhớ đủ lớn, tốc độ xử lý cao để xử lý dữ liệu bản đồ số tại máy, khả năng cập nhật bản đồ thấp và phải thực hiện độc lập. 3) Kiểu thứ ba: áp dụng cho các thiết bị di động có khả năng kết nối Internet, duyệt web, không tích hợp bộ thu GPS. Về giao diện chính cũng như cách khai thác cơ bản giống như kiểu thứ nhất. Không tự động xác định vị trí hiện hành do không tích hợp bộ thu GPS, nếu dùng phương pháp định vụ qua mạng di động thì sai số khá lớn, hiệu quả mang lại không cao. Khi người dùng có yêu cầu tìm đường thì phải xác định rõ cả điểm xuất phát và điểm tới (bằng thiết bị trỏ hoặc nhập bằng văn bản). 4) Kiểu thứ tư: áp dụng cho các thiết bị di động có cấu hình thấp, không duyệt được web, không tích hợp GPS mà chỉ khai thác dịch vụ SMS (điện thoại thường), có khả năng cài đặt phần mềm. Giao diện chính không thể hiện bản đồ mà chỉ có các công cụ nhập số liệu, gửi yêu cầu. Người dùng phải nhập điểm xuất phát, điểm đến. Kết quả được trả về dưới dạng danh sách các cung đường phải đi qua cùng độ dài tương ứng. 5) Kiểu thứ năm: áp dụng cho các thiết bị di động có cấu hình rất thấp, chỉ khai thác dịch vụ SMS, không có khả năng cài đặt phần mềm (điện thoại chỉ nghe gọi và gửi tin nhắn). Người dùng được cung cấp thông tin về số điện thoại dịch vụ. Khi có nhu cầu tìm đường, người dùng sử dụng điện thoại, gửi tin nhắn đến số trung tâm dịch vụ với nội dung yêu cầu chỉ rõ điểm xuất phát, điểm đến và một số thông tin phụ khác. - 50 - Hệ thống sẽ “so sánh” thông tin này với dữ liệu có tại máy chủ, nếu trùng khớp sẽ tiến hành tìm kiếm ngay. Trường hợp thông tin không chính xác, hệ thống sẽ gửi về danh sách các địa danh gợi ý yêu cầu xác nhận từ phía người dùng. Sau khi có thông tin xác nhận sẽ tiến hành tìm kiếm. Kết quả trả về là danh sách các cung đường phải qua và độ dài tương ứng qua tin nhắn. Đánh giá: kiểu dịch vụ này phù hợp cho mọi đối tượng người dùng có cấu hình thiết bị di động từ thấp nhất đến cao. Tuy nhiên chất lượng dịch vụ không cao do không có khả năng biểu diễn trực quan bản đồ, mất nhiều thời gian cung cấp vị trí xuất phát và vị trí đến. Hình 3.6: Minh hoạ giao diện chỉ sử dụng tin nhắn SMS Tóm lại, hệ thống cung cấp dịch vụ tìm đường trong thành phố được thiết kế với khả năng đáp ứng yêu cầu dịch vụ khá đa dạng, phù hợp cho nhiều đối tượng sử dụng khác nhau. Hệ thống hỗ trợ đồng thời tất cả các kiểu dịch vụ nêu trên. Mỗi kiểu dịch vụ có thể được coi như là một gói dịch vụ độc lập nhưng thống nhất về hệ thống thông tin, mục đích khai thác. - 51 - Để thận tiện cho tham chiếu và sử dụng trong các nội dung trình bày sau, mỗi kiểu khác thác dịch vụ trên được coi là một gói dịch vụ trong hệ thống dịch vụ tìm đường và ký hiệu như sau: Gói TD1: triển khai dịch vụ theo kiểu thứ nhất Gói TD2: triển khai dịch vụ theo kiểu thứ hai Gói TD3: triển khai dịch vụ theo kiểu thứ ba Gói TD4: triển khai dịch vụ theo kiểu thứ tư Gói TD5: triển khai dịch vụ theo kiểu thứ năm Sơ đồ tổng quát của hệ thống dịch vụ và khách hàng khai thác dịch vụ được thể hiện như sau (hình 3.7): - 52 - Hình 3.7: Sơ đồ tổng quát hệ thống dịch vụ tìm đường KHÁCH HÀNG DỊCH VỤ TÌM ĐƯỜNG Máy chủ, cơ sở dữ liệu chung Gói TD1 Gói TD2 Gói TD3 Gói TD4 Gói TD4 Duyệt web, GPS, hiển thị bản đồ GPS, SMS, hiển thị bản đồ Duyệt web, hiển thị bản đồ SMS, phần mềm nhập vị trí Chỉ dùng tin nhắn SMS Mạng Internet, dịch vụ Web Mạng GSM, dịch vụ SMS GPS - 53 - 3.3.8. Vấn đề cập nhật tình trạng hệ thống giao thông Cập nhật trạng thái của hệ thống giao thông là một nhiệm vụ quan trọng. Ý nghĩa lớn nhất của dịch vụ tìm đường này là chỉ ra đường đi thực sự hữu ích có tính đến các yếu tố biến động thường xuyên, tác động lên đường đi tìm được như yếu tố tắc đường chẳng hạn. Thực hiện việc cập nhật trạng thái tuyến đường có thể tiến hành theo nhiều cách khác nhau hoặc phối hợp đồng thời nhiều cách: Thứ nhất: lắp đặt hệ thống camera quan sát tại các điểm trọng yếu (nút giao thông, các cung đường hay xảy ra tắc nghẽn). Theo phương án này, hệ thống cần phải có chức năng phân tích hình ảnh, xác định trạng thái tuyến được. Công việc phân tích hình ảnh này có thể được thực hiện một cách tự động bởi phần mềm máy tính hoặc do người làm thủ công. Giải pháp này có ưu điểm là đảm bảo tính cập nhật (ngay tức thời), thông tin chính xác. Tuy nhiên đây là giải pháp tốn kém do phải chi phí nhiều cho trang bị và duy trì hoạt động của hệ thống camera, cùng với đó là phải giải quyết vấn đề truyền thông giữa các camera với trung tâm. Thứ hai: kết hợp với trung tâm dịch vụ điện thoại để tiếp nhận các thông tin về trạng thái các nút giao thông qua điện thoại. Mỗi người dân tham gia giao thông sẽ được khuyến nghị tham gia vào hệ thống. Họ sẽ gọi điện hay nhắn tin đến hệ thống để thông báo về tình trạng giao thông (một cách tự nguyện). Phía hệ thống phải có bộ phận tiếp nhận và cập nhật các thông tin này, cần có sự tham gia trực tiếp của con người với sự hỗ trợ của thiết bị, phần mềm. Giải pháp này có ưu điểm là chi phí đầu tư thấp. Thực chất, các chi phí này được san sẻ cho những người tham gia giao thông. Tuy nhiên, giải pháp này có một số nhược điểm lớn đó là tính cập nhật thấp, bị động (tuỳ thuộc vào người tham gia giao thông), độ tin cậy của thông tin nhận được không cao, khó kiểm chứng. Thứ ba: về phương tiện và cách thức thu thập thông tin thì tương tự như cách thứ hai nhưng đối tượng cung cấp thông tin có bổ sung thêm nhóm người khai thác dịch vụ. Đối với người khai thác dịch vụ, họ được yêu cầu phải cung cấp thông tin về trạng thái của hệ thống giao thông tại vị trí hiện tại của họ (với giả thiết họ đang tham gia giao thông) mỗi khi có yêu cầu dịch vụ. Theo cách này, thông tin về tình trạng hệ thống giao thông sẽ thu thập được nhiều hơn. Các mặt ưu và nhược điểm về cơ bản tương tự như đã trình bày ở cách thứ hai. - 54 - Chương 4: CÀI ĐẶT THỬ NGHIỆM Trình bày các nội dung cài đặt thử nghiệm dịch vụ LBS tìm đường đi trong nội thành thành phố Hà Nội. Lựa chọn mô hình, kiểu dịch vụ, công nghệ áp dụng và kết quả. 4.1. Lựa chọn mô hình cài đặt 4.1.1. Mô hình dịch vụ Do hạn chế về thời gian và phương tiện (phần cứng) thể hiện nên tác giả lựa chọn cài đặt một nhánh nhỏ theo mô hình kết hợp sử dụng công nghệ web thông qua mạng Internet với dịch vụ tin nhắn SMS đã giới thiệu ở chương 3 (nhánh đánh dấu bằng đường nét đứt ở hình 3.7); truyền dữ liệu qua mạng GSM dưới dạng tin nhắn SMS; triển khai kiểu dịch vụ thứ ba (đã giới thiệu ở mục 3.2.7) nhưng không tích hợp bộ thu GPS, thực hiện mô phỏng thiết bị thu GPS. Phía máy chủ: tập trung biểu diễn hiện trạng khai thác dịch vụ một cách trực quan trên bản đồ số; giao tiếp với máy trạm qua dịch vụ tin nhắn SMS. Máy chủ lưu trữ dữ liệu bản đồ số thành phố Hà Nội (dữ liệu chủ yếu được xây dựng để thử nghiệm). Cài đặt thuật toán tìm kiếm đường đi ngay tại máy chủ. Phía máy khách: sử dụng điện thoại thường, mô phỏng bộ thu GPS tạo số liệu toạ độ hiện thời, gửi yêu cầu và nhận kết quả trả về dưới dạng tin nhắn. Hình 4.1: Giao tiếp của hệ thống LBS thử nghiệm MẠNG TRUYỀN THÔNG DI ĐỘNG MÁY CHỦ GSM MODEM MÁY KHÁCH SMS SMS SMS - 55 - 4.1.2. Phần cứng Máy chủ: máy tính để bàn hoặc máy xách tay có cấu hình yêu cầu ở mức trung bình, giao tiếp được với GSM Modem. GSM Modem: là thiết bị ghép nối máy tính giúp giao tiếp với mạng di động GSM. Có thể sử dụng GSM Modem chuyên dụng hoặc điện thoại di động đóng vai trò GSM Modem để thực hiện việc gửi, nhận tin nhắn SMS từ máy tính. Máy khách: sử dụng các loại điện thoại thông thường, không cần tích hợp thiết bị thu GPS. 4.2. Lựa chọn công nghệ 4.2.1. Xử lý dữ liệu bản đồ số bằng MapInfo MapInfo là phần mềm bản đồ đang được sử dụng khá rộng rãi trên thị trường Việt Nam. MapInfo thiên về quản lý, tổng hợp thông