Tài liệu Luận án tiến sĩ toán học một số kỹ thuật dự báo vị trí và truy vấn các đối tượng chuyển động trong cơ sở dữ liệu không gian thời gian

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ NGUYỄN TIẾN PHƯƠNG MỘT SỐ KỸ THUẬT DỰ BÁO VỊ TRÍ VÀ TRUY VẤN CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG TRONG CƠ SỞ DỮ LIỆU KHÔNG GIAN-THỜI GIAN Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ NGUYỄN TIẾN PHƯƠNG MỘT SỐ KỸ THUẬT DỰ BÁO VỊ TRÍ VÀ TRUY VẤN CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG TRONG CƠ SỞ DỮ LIỆU KHÔNG GIAN-THỜI GIAN Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS. TS. Đặng Văn Đức HÀ NỘI -2015 LỜI CAM ĐOAN Tôi xin cam đoan những kết quả trình bày trong luận án là mới, trung thực và chưa từng được công bố trong bất kỳ công trình của ai khác. Những kết quả viết chung với cán bộ hướng dẫn đã được sự đồng ý khi đưa vào luận án. Nghiên cứu sinh Nguyễn Tiến Phương 1 LỜI CẢM ƠN Lời đầu tiên, tôi xin gửi lời cảm ơn sâu sắc tới PGS. TS. Đặng Văn Đức đã tận tình hướng dẫn, giúp đỡ tôi trong quá trình nghiên cứu và hoàn thành luận án này. Tôi cũng xin chân thành cảm ơn Lãnh đạo Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện thuận lợi cho quá trình nghiên cứu của mình, cảm ơn các các bộ của phòng Hệ thông tin Địa lý đã nhiệt tình trong công tác, giúp tôi dành thời gian hoàn thành luận án. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn là nguồn động viên, ủng hộ, giúp tôi thêm động lực để hoàn thành tốt luận án này. NCS. Nguyễn Tiến Phương 2 MỤC LỤC LỜI CAM ĐOAN .......................................................................................................1 LỜI CẢM ƠN .............................................................................................................2 MỤC LỤC ....................................................................................................................3 DANH MỤC CÁC TỪ VIẾT TẮT VÀ KÝ HIỆU ....................................................5 DANH SÁCH HÌNH VẼ ............................................................................................7 DANH SÁCH BẢNG .................................................................................................9 MỞ ĐẦU ...................................................................................................................10 Các ứng dụng của dịch vụ dựa trên vị trí ...............................................................10 Tình hình nghiên cứu trên thế giới và trong nước .................................................12 a. Mô hình hóa dữ liệu vị trí ..........................................................................13 b. Các cách tiếp cận xử lý truy vấn phụ thuộc vị trí ......................................15 c. Tính riêng tư ..............................................................................................18 Chương 1 CƠ SỞ DỮ LIỆU CÁC ĐỐI TƯỢNG CHUYỂN ĐỘNG ......................22 1.1. Một số khái niệm cơ bản ...........................................................................22 1.1.1. Cơ sở dữ liệu không gian-thời gian.......................................................22 1.1.2. Cơ sở dữ liệu các đối tượng chuyển động.............................................24 1.1.3. Dữ liệu trong cơ sở dữ liệu các đối tượng chuyển động .......................26 1.1.4. Truy vấn trong cơ sở dữ liệu các đối tượng chuyển động ....................27 1.2. Các vấn đề cần giải quyết ..........................................................................29 1.2.1. Vấn đề về mô hình hóa vị trí .................................................................29 1.2.2. Vấn đề về ngôn ngữ truy vấn ................................................................30 1.2.3. Vấn đề về lập chỉ mục ...........................................................................30 1.2.4. Vấn đề về tính không chắc chắn/không chính xác ................................31 Chương 2 DỰ ĐOÁN VỊ TRÍ CỦA ĐỐI TƯỢNG CHUYỂN ĐỘNG ..................33 2.1. Dự đoán vị trí của đối tượng dựa theo hàm chuyển động ..............................35 2.1.1. Dự đoán dựa theo hàm tuyến tính ............................................................36 2.1.2. Dự đoán dựa theo hàm phi tuyến .............................................................36 2.2. Dự đoán dựa trên hành vi của đối tượng ........................................................50 3 2.2.1. Luật kết hợp ..............................................................................................52 2.2.2. Thuật toán phân cụm dựa trên mật độ DBSCAN.....................................53 2.2.3. Mẫu hình di chuyển ..................................................................................54 2.2.4. Khai phá mẫu hình di chuyển ...................................................................57 2.2.5. Khai phá luật kết hợp của mẫu hình quỹ đạo để dự đoán vị trí của đối tượng chuyển động .......................................................................................................61 Chương 3 LẬP CHỈ MỤC DỮ LIỆU KHÔNG GIAN-THỜI GIAN......................71 3.1. R-tree ..............................................................................................................73 Cấu trúc cây R-tree .............................................................................................73 3.2. TPR-tree ..........................................................................................................76 Cấu trúc cây TPR-tree ........................................................................................76 3.3. TPR*-tree ........................................................................................................80 3.4. DO-TPR*-tree .................................................................................................81 3.4.1. Cấu trúc cây DO-TPR*-tree .....................................................................83 3.4.2. Thuật toán tìm kiếm DOA_Search ...........................................................84 3.4.3. Kết quả thực nghiệm ................................................................................89 KẾT LUẬN ...............................................................................................................95 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ.................................................97 TÀI LIỆU THAM KHẢO .........................................................................................98 4 DANH MỤC CÁC TỪ VIẾT TẮT VÀ KÝ HIỆU 2D/3D CAMEL DBMS DOA_Search DO-TPR*-tree EWMA 2/3 Dimensional – 2/3 chiều Continuous Active Monitor Engine - Cơ chế giám sát tích cực liên tục Database Management System – Hệ quản trị cơ sở dữ liệu Thuật toán tìm kiếm điều chỉnh theo mật độ của nút trên cây DOTPR*-tree Cấu trúc cây điều chỉnh theo mật độ dựa trên TPR*-tree Exponentially Weighted Moving Average – Trung bình động trọng số mũ GIS Geographical Information System – Hệ thống thông tin địa lý GPRS General Packet Radio Service - Dịch vụ vô tuyến gói tổng hợp GPS Global Positioning System – Hệ thống định vị toàn cầu GSM Global System for Mobile Communications - Hệ thống thông tin di động toàn cầu LBS Location Based Service – Dịch vụ dựa trên vị trí MAI Motion Adaptive Indexing - Chỉ mục thích ứng chuyển động MBR Minimum Bounding Rectangle – Hình chữ nhật bao nhỏ nhất MODB MODM MQM MSB PLACE RMF Moving Objects Database – Cơ sở dữ liệu các đối tượng chuyển động Moving Objects Database Model – Mô hình cơ sở dữ liệu các đối tượng chuyển động Monitoring Query Management - Quản lý giám sát truy vấn Motion-Sensitive bounding Boxes - Hộp ranh giới nhạy chuyển động Pervasive Location-Aware Computing Environments - Môi trường tính toán khắp nơi nhận biết vị trí Recursive Motion Function – Hàm chuyển động đệ quy 5 SINA Scalable INcremental hash-based Algorithm – Thuật toán đánh giá các truy vấn phụ thuộc vị trí đồng thời SMA Simple Moving Average – Trung bình động đơn giản SMS Short Message Services – Dịch vụ tin nhắn ngắn TM Transition Matrix – Ma trận chuyển đổi VBR Velocity Bounding Rectangle – Hình chữ nhật bao vận tốc VCI Velocity-Constraint Indexing – Chỉ mục ràng buộc vận tốc W-EWMA Window Exponentially Weighted Moving Average – Trung bình động trọng số mũ sử dụng cửa sổ giới hạn 6 DANH SÁCH HÌNH VẼ Hình 0.1. Môi trường nhận biết vị trí ........................................................................10 Hình 0.2. Các thiết bị định vị vị trí ...........................................................................11 Hình 0.3. Ứng dụng của hệ thống quản lý và điều hành giao thông đô thị ..............11 Hình 1.1. Cơ sở dữ liệu không gian-thời gian và MODB .........................................23 Hình 1.2. Mô hình hệ thống ứng dụng MODB .........................................................25 Hình 1.3. Điểm chuyển động rời rạc và liên tục .......................................................27 Hình 1.4. Các kiểu truy vấn phổ biến trong MODB .................................................28 Hình 1.5. Ngữ nghĩa của CÓ THỂ và CHẮC CHẮN trong MODB ........................31 Hình 2.1. Dự đoán sai của mô hình tuyến tính .........................................................37 Hình 2.2. So sánh thời gian tính toán của các kỹ thuật dự đoán ...............................46 Hình 2.3. So sánh kết quả dự đoán của của W-EWMA và EWMA .........................47 Hình 2.4. Ảnh hưởng của w với kết quả dự đoán .....................................................48 Hình 2.5. Ảnh hưởng của giá trị α với kết quả dự đoán ...........................................49 Hình 2.6. Quỹ đạo chuyển động của đối tượng và các thông tin địa lý ....................55 Hình 2.7. Phân tách quỹ đạo của đối tượng ..............................................................58 Hình 2.8. Quỹ đạo con ..............................................................................................59 Hình 2.9. Quy trình khai phá mẫu hình di chuyển ....................................................60 Hình 2.10. Sai lệch khi dự đoán di chuyển của đối tượng trong thực tế...................62 Hình 2.11. So sánh độ chính xác của hai phương pháp dự đoán ..............................69 Hình 3.1. Các cấu trúc cây phát triển từ TPR-tree (2005-2012) ...............................72 Hình 3.2. Biểu diễn hai chiều của R-tree ..................................................................75 Hình 3.3. Biểu diễn cấu trúc cây R-tree ....................................................................75 7 Hình 3.4. Các điểm chuyển động ở các nút lá của TPR-tree ....................................76 Hình 3.5. Các điểm chuyển động trong các nút trung gian của TPR-tree ................77 Hình 3.6. Cập nhật khoảng giới hạn theo tham số thời gian .....................................78 Hình 3.7. Biểu diễn nút trung gian trong cây TPR-tree ............................................79 Hình 3.8. Vùng quét từ thời điểm 0 đến thời điểm 1 ................................................81 Hình 3.9. MBR của R tại thời điểm khởi tạo 0 và mở rộng R1 tại thời điểm 1 .........82 Hình 3.10. Ảnh hưởng của độ lớn phạm vi truy vấn ................................................92 Hình 3.11. So sánh hiệu năng của DO-TPR*-tree với TPR*-tree ............................93 8 DANH SÁCH BẢNG Bảng 2.1. Tọa độ các điểm trên quỹ đạo mẫu ...........................................................67 Bảng 2.2. Dữ liệu mẫu về di chuyển hàng ngày của đối tượng ................................67 Bảng 2.3. Quỹ đạo của đối tượng..............................................................................68 Bảng 2.4. Di chuyển thường xuyên và độ hỗ trợ ......................................................68 Bảng 2.5. Mẫu hình di chuyển với độ hỗ trợ nhỏ nhất là 0.5 ...................................69 Bảng 3.1. Dữ liệu thực nghiệm các đối tượng chuyển động .....................................90 9 MỞ ĐẦU Sự kết hợp các chức năng của công nghệ định vị cá nhân, công nghệ định vị vệ tinh, công nghệ truyền thông không dây và công nghệ GIS đã tạo ra một môi trường mới trong đó tất cả các đối tượng chuyển động có thể xác định vị trí của chúng. Các công nghệ này là cơ sở cho việc phát triển mạnh mẽ môi trường nhận biết vị trí và các dịch vụ dựa trên vị trí. Dịch vụ dựa trên vị trí là dịch vụ được đặc chế dựa trên những thông tin về vị trí của đối tượng. Những dịch vụ này là tiềm năng để nâng cao chất lượng cuộc sống nhờ việc thêm các thông tin vị trí vào hầu hết các thiết bị, đối tượng chuyển động như ô tô, máy bay, tàu thủy, máy tính xách tay, điện thoại di động, vật nuôi và cả con người… Hình dưới đây thể hiện một môi trường nhận biết vị trí đơn giản mà trong đó các đối tượng chuyển động sử dụng các thiết bị định vị vị trí như GPS hay điện thoại thông minh. Các đối tượng này có thể gửi thông tin về vị trí và vận tốc của mình lên máy chủ cơ sở dữ liệu và lấy thông tin cũng như thực hiện các truy vấn từ đó. Hình 0.1. Môi trường nhận biết vị trí Các ứng dụng của dịch vụ dựa trên vị trí Các thiết bị có hỗ trợ định vị vị trí như GPS, RFID, các thiết bị cầm tay, điện thoại di động… ngày càng được sử dụng rộng rãi (hình 0.2). Điều này là tiền đề cho việc 10 phát triển các ứng dụng dựa trên vị trí mà trong đó các đối tượng chuyển động cùng với các thiết bị này thay đổi vị trí liên tục trong không gian, theo thời gian. Hình 0.2. Các thiết bị định vị vị trí Các ứng dụng có thể thấy rõ nhất là quản lý và điều hành giao thông đô thị (hình 0.3); theo dõi, dự báo thời tiết; cảnh báo sóng thần, động đất; theo dõi và xử lý cứu hộ, cứu nạn… Trong các ứng dụng này, người sử dụng có thể thực hiện các truy vấn kiểu như: “Tìm tất cả các xe taxi chưa có khách cách sân bay 1km trong vòng 15 phút nữa?”, “Ước tính lưu lượng xe cộ tại ngã tư A lúc 11h trưa nay”, “Cơn bão B đang hình thành có ảnh hưởng đến vùng V hay không, nếu có thì bao giờ và phạm vi, mức độ phá hủy như thế nào?”… Hình 0.3. Ứng dụng của hệ thống quản lý và điều hành giao thông đô thị 11 Với tốc độ đô thị hóa ngày càng nhanh, các thành phố lớn trên chục triệu dân ngày càng nhiều, vấn đề quản lý và điều hành giao thông đô thị càng trở nên bức thiết. Hơn nữa với mức sống ngày càng cao, nhu cầu quản lý tài sản cá nhân như xe cộ, vật nuôi trong nhà hay thậm chí là cả giám sát chăm sóc trẻ em, người cao tuổi ngày càng lớn. Để đáp ứng được các nhu cầu đó, bài toán quản lý thông tin các đối tượng chuyển động dựa trên nền tảng của môi trường và ứng dụng định vị vị trí càng cần có lời giải chính xác, tối ưu. Nhiều mô hình cơ sở dữ liệu các đối tượng chuyển động (MODM - Moving Objects Database Model) đã và đang được nghiên cứu, thử nghiệm. Trong các mô hình này, dữ liệu của các đối tượng chuyển động, bao gồm cả thông tin về vị trí trong quá khứ, hiện tại và tương lai được lưu trữ và cập nhật thường xuyên. Khó khăn lớn khi giải quyết bài toán này là làm thế nào để khai thác hệ thống một cách hiệu quả khi số lượng đối tượng chuyển động trong không gian-thời gian (spatiotemporal) là rất lớn và thường xuyên thay đổi vị trí. Việc truy vấn vị trí của đối tượng trong tương lai cùng với tính không chắc chắn của nó cũng là một vấn đề cần giải quyết và nâng cao tính chính xác. Một số phương pháp đã được đề xuất nhằm nâng cao khả năng dự đoán vị trí cũng như tăng tốc độ truy vấn của các đối tượng chuyển động. Tuy nhiên các nghiên cứu này mới đạt được những kết quả nhất định và còn một số khó khăn, hạn chế cần cải tiến, khắc phục. Luận án này tập trung chính vào việc góp phần giải quyết lớp bài toán quản lý thông tin đối tượng chuyển động hay quản lý và điều hành giao thông một cách nhanh chóng, hiệu quả hơn. Tình hình nghiên cứu trên thế giới và trong nước Vấn đề quản lý thông tin đối tượng chuyển động trong môi trường và ứng dụng dựa trên vị trí đã được đặt ra và tìm cách giải quyết từ những năm 90 của thế kỷ trước. Nó đã đạt được những kết quả nhất định và đang được ứng dụng trong thực tế ở nhiều nước phát triển trên thế giới như Mỹ, Nhật Bản, Hàn Quốc… Ở Việt Nam, TP. Hà Nội đang áp dụng hệ thống giám sát giao thông qua bản đồ số và camera từ tháng 3/2015 (hình 0.3). Đồng thời, Hà Nội cũng là địa phương đầu tiên thực hiện thí điểm đề án giao thông thông minh dự kiến trong tháng 7/2015 và sẽ triển khai diện rộng 12 trên toàn quốc trong những năm tới. Với đề án này, thông qua phần mềm cài đặt trên điện thoại của người tham gia giao thông, các nhà mạng thu thập thông tin về tốc độ, hướng di chuyển, mật độ xe trên đường. Dữ liệu này sau đó được gửi về trung tâm giám sát để điều chỉnh tức thời hoặc đưa ra các nghiên cứu, quy hoạch giao thông đô thị. Cũng thông qua đó, người tham gia giao thông có thể xác định đường đi tối ưu, tránh các điểm ùn tắc… Như vậy, cùng với sự phát triển mạnh mẽ của các ứng dụng dựa trên vị trí, khái niệm về hệ cơ sở dữ liệu nhận biết vị trí (Location-aware database systems) ngày càng trở nên quan trọng và đặt ra những thách thức lớn cho sự phát triển của các hệ quản trị cơ sở dữ liệu hiện có. Các hệ quản trị cơ sở dữ liệu hiện tại không phù hợp với việc quản lý các dữ liệu thay đổi liên tục theo thời gian như vị trí của các đối tượng chuyển động. Hệ cơ sở dữ liệu nhận biết vị trí phải có các khả năng sau: a) Mô hình hóa một lượng lớn dữ liệu vị trí theo cách thức nào đó để có thể cập nhật vào và lấy ra một cách hiệu quả b) Xử lý hiệu quả các truy vấn dữ liệu phụ thuộc vị trí c) Đảm bảo sự riêng tư về thông tin vị trí của người dùng. a. Mô hình hóa dữ liệu vị trí Ứng dụng cung cấp dịch vụ dựa trên vị trí yêu cầu phải truy cập vào một lượng lớn dữ liệu vị trí lại liên tục thay đổi. Vì có quá nhiều dữ liệu, việc tổ chức chúng theo cách mà những thông tin liên quan có thể được lấy ra một cách hiệu quả là rất quan trọng. Hơn thế, do dữ liệu thay đổi thường xuyên, việc giảm chi phí cập nhật cũng rất cần thiết. Hai kỹ thuật chính để biểu diễn dữ liệu vị trí thường được sử dụng là: cơ sở dữ liệu các đối tượng chuyển động (MODB) và dòng dữ liệu liên tục (data streams). Cơ sở dữ liệu các đối tượng chuyển động Cơ sở dữ liệu các đối tượng chuyển động là phần mở rộng của một hệ thống quản lý cơ sở dữ liệu truyền thống, hỗ trợ lưu trữ dữ liệu vị trí cho đối tượng chuyển động liên tục. Những nỗ lực đầu tiên trong việc mô hình hóa đối tượng chuyển động là biểu 13 diễn các chuyển động của chúng như là mẫu của các dữ liệu vị trí có sẵn [28]. Nhược điểm của kỹ thuật này là đòi hỏi chi phí cập nhật cao. Sistla cùng đồng nghiệp đã thiết kế mô hình dữ liệu MOST [38] mà trong đó duy trì một véc tơ vị trí cho mỗi đối tượng chuyển động. Véc tơ vị trí sẽ thay đổi theo thời gian bởi một hàm cập nhật, ngay cả nếu không xảy ra một sự cập nhật rõ ràng. Hàm cập nhật có thể là tuyến tính hoặc phi tuyến dưới dạng chuyển động đệ quy. Guting và đồng nghiệp [8] thiết kế một hệ thống sử dụng các kiểu dữ liệu trừu tượng để biểu diễn các đối tượng chuyển động bằng các khái niệm như: “điểm chuyển động” và “vùng chuyển động”. Su và Ibarra [40] đề xuất một cơ sở dữ liệu ràng buộc thông tin vị trí bằng cách sử dụng công thức toán học để biểu diễn dữ liệu. MD-HBase [31] đã tạo ra hệ quản trị dữ liệu cho dịch vụ dựa trên vị trí mà tận dụng cấu trúc chỉ mục đa chiều nằm trên bộ lưu trữ theo cặp khóa-giá trị. Bộ lưu trữ cặp khóa-giá trị này cho phép DBMS để xử lý việc chèn một lượng lớn dữ liệu với tốc độ cao trong khi vẫn duy trì khả năng chịu lỗi. Cấu trúc chỉ mục này làm cho việc truy vấn dữ liệu hiệu quả hơn. Trong CSDL các đối tượng chuyển động, việc dự đoán vị trí đóng vai trò quan trọng trong mô hình hóa vị trí nhằm giảm tần suất cập nhật thông tin này. Có một số phương pháp như dự đoán theo hàm chuyển động [33], [34], lô-gíc mờ [47], xác xuất thống kê [5], [19] hay kết hợp nhiều phương pháp khác nhau [15], [23]. Lập chỉ mục là đặc biệt quan trọng trong cơ sở dữ liệu các đối tượng chuyển động vì có một lượng rất lớn dữ liệu và chẳng hệ thống nào muốn tìm kiếm bằng cách kiểm tra tất cả các dữ liệu có trong đó. Cấu trúc cây R-tree [10] có thể được sử dụng để lập chỉ mục dữ liệu không gian, tuy nhiên vì dữ liệu vị trí thường xuyên thay đổi, các chỉ mục này sẽ cần phải được cập nhật thường xuyên. Việc mở rộng cấu trúc cây R-tree cũng như các chiến lược lập chỉ mục khác đã được nghiên cứu để giảm bớt gánh nặng cập nhật, điển hình là TPR-tree, TPR*-tree. TPR-tree [36] lưu trữ cả vị trí hiện tại cùng với vận tốc của từng đối tượng tại những thời điểm cụ thể và do đó rất hiệu quả cho việc tìm kiếm, đồng thời cho phép dự đoán vị trí của đối tượng chuyển động. Cây TPR*-tree [42] được cải tiến từ TPR-tree và mang lại hiệu suất cao hơn, gấp 5 lần so với cây TPR-tree. Đây là cấu trúc chỉ mục được đánh giá rất cao và tiếp tục được cải 14 tiến theo nhiều hướng khác nhau phù hợp với từng hoàn cảnh và ứng dụng cụ thể trong thực tế. Dòng dữ liệu liên tục cho thông tin vị trí (data streams) Một dòng dữ liệu liên tục là một cấu trúc được sử dụng cho thông tin đầu vào, trong đó lượng dữ liệu là rất lớn (giả định là vô hạn) và thay đổi liên tục. Trong trường hợp đặc biệt, lượng dữ liệu lớn đến mức không thể lưu trữ toàn bộ chúng. Huang và Jensen [12] đã sử dụng dòng dữ liệu để mô hình hóa dữ liệu vị trí cho các đối tượng chuyển động và trả lại kết quả truy vấn. Truy vấn liên tục được xử lý bởi hệ thống như là một chuỗi các truy vấn chụp lại trước (snapshot) được thực hiện trong những khoảng thời gian xác định. Tương tự như vậy, Patroumpas và Sellis [34] đã chọn mô hình hóa đối tượng chuyển động như một dòng quỹ đạo. Môi trường tính toán khắp nơi nhận biết vị trí (Pervasive Location-Aware Computing Environments - PLACE) [26] được tạo thành bởi việc mở rộng hệ thống quản lý dòng dữ liệu có khả năng hỗ trợ dữ liệu nhận biết vị trí. PLACE sử dụng cách ước lượng gia tăng để cập nhật liên tục các câu trả lời truy vấn. Cơ chế giám sát tích cực liên tục (Continuous Active Monitor Engine - CAMEL) [50] được Chen đề xuất nhằm hỗ trợ các dịch vụ nhận biết vị trí. Đây là cơ chế dựa trên dòng dữ liệu, sử dụng chỉ số lưới để xử lý một lượng lớn các đối tượng chuyển động. b. Các cách tiếp cận xử lý truy vấn phụ thuộc vị trí Truy vấn phụ thuộc vị trí là truy vấn mà kết quả dựa trên vị trí của các đối tượng cụ thể. Truy vấn phụ thuộc vị trí thường là truy vấn liên tục, có nghĩa là kết quả của các truy vấn được cập nhật theo các đối tượng chuyển động khi thay đổi vị trí. Hai kỹ thuật chính thường được sử dụng cho việc xử lý truy vấn phụ thuộc vị trí đã được nghiên cứu trong những năm gần đây là: • Sử dụng sự cộng tác từ các đối tượng chuyển động • Sử dụng dự đoán quỹ đạo cho các đối tượng chuyển động. 15 Sử dụng sự cộng tác từ các đối tượng chuyển động Một số hệ thống cơ sở dữ liệu nhận biết vị trí sử dụng sự cộng tác từ chính các đối tượng chuyển động để tạo thuận lợi cho việc xử lý truy vấn phụ thuộc vị trí. Ý tưởng cơ bản là đối tượng chuyển động định kỳ sẽ gửi thông tin vị trí của chúng đến một máy chủ dựa trên một số chính sách cập nhật được xác định trước. Chính sách này mô tả những thông tin cần gửi và mức độ thường xuyên khi thực hiện điều đó. Cai và đồng nghiệp [3] [4] phát triển hệ thống Quản lý Giám sát Truy vấn (Monitoring Query Management - MQM) cho việc xử lý các truy vấn phạm vi, trong đó đối tượng chuyển động chịu trách nhiệm giám sát các truy vấn gần kề của chúng và báo cáo vị trí lên máy chủ bất cứ khi nào chuyển động của chúng ảnh hưởng đến kết quả truy vấn. Để thực hiện điều này, mỗi đối tượng chuyển động có một miền thường trú cùng với một tập hợp các truy vấn liên quan đến miền thường trú này. Giá trị vị trí được gửi đi khi đối tượng chuyển động di chuyển ra bên ngoài miền thường trú hoặc đi qua ranh giới truy vấn. Chiến lược cập nhật này có thể làm giảm chi phí xử lý bằng cách hạn chế việc thực hiện chỉ dành cho những cập nhật thực sự cần thiết. Tuy nhiên, nó đòi hỏi đối tượng chuyển động có năng lực xử lý (CPU) nhất định và chỉ hỗ trợ cho các truy vấn trong đó điểm truy vấn là tĩnh. Tương tự như vậy, MobiEyes [6] định nghĩa một khu vực giám sát cho mỗi truy vấn và các đối tượng chuyển động sẽ phải thông báo cho máy chủ khi chúng vượt qua ranh giới của miền truy vấn. Ngoài ra, MobiEyes sử dụng tối ưu hóa để giảm bớt số lượng công việc mà các đối tượng chuyển động sẽ phải thực hiện. Gedik [7] đề xuất một hệ thống tương tự khác, đó là hệ chỉ mục thích ứng chuyển động (Motion Adaptive Indexing - MAI), để xử lý các truy vấn chuyển động liên tục. Hệ thống này sử dụng các hộp ranh giới nhạy chuyển động (MotionSensitive bounding Boxes - MSB) cho các đối tượng và truy vấn. Trong MAI, Gedik không lập chỉ mục vị trí mà thay vào đó là lập chỉ mục các MSB và sử dụng dự đoán để tính toán trước các kết quả truy vấn. Prabhakar và đồng nghiệp [35] cũng đề xuất một hệ thống mà lập chỉ mục các truy vấn thay vì vị trí. Khu vực an toàn được sử dụng để xác định vùng xung quanh đối tượng chuyển động mà không giao với ranh giới truy vấn. Các đối tượng chuyển động chỉ cập nhật vị trí của nó khi di chuyển ra 16 bên ngoài khu vực an toàn. Lập chỉ mục hạn chế tốc độ (Velocity-Constraint Indexing - VCI) cũng được sử dụng để điều tiết các truy vấn mới mà không thực tế trong việc lập chỉ mục truy vấn. VCI dùng để trì hoãn việc cập nhật chỉ mục để đáp lại sự chuyển động của các đối tượng. DISQO [49] đã được giới thiệu bởi Zheng và đồng nghiệp để xử lý cả truy vấn chụp lại và truy vấn không gian liên tục bằng cách chuyển đổi thông tin vị trí và thông tin truy vấn giữa máy chủ và các đối tượng chuyển động. Sử dụng dự báo quỹ đạo Kỹ thuật này giả định rằng đối tượng sẽ đi theo một quỹ đạo biết trước để dự đoán được vị trí của nó. Với kỹ thuật này, hệ thống không cần thực hiện nhiều việc cập nhật vị trí của đối tượng. Tuy nhiên, điều này làm tăng sự không chắc chắn vì đối tượng chuyển động có thể đi chệch khỏi các quỹ đạo giả định. Trong hệ thống DOMINO [32], khi một đối tượng cung cấp vị trí hiện tại, thì cũng cung cấp luôn vị trí tương lai dự kiến của nó. DOMINO sử dụng thông tin này để chiếu đến vị trí tương lai của đối tượng. Nó sử dụng mô hình dữ liệu MOST mà định kỳ thay đổi thuộc tính vị trí động ngay cả khi vị trí không được cập nhật một cách rõ ràng bởi các đối tượng. CAT (Correct Answers of Continuous Queries Using Triggers) [44] sử dụng một bảng dữ liệu lưu trữ quỹ đạo của một đối tượng và các truy vấn kết hợp với đối tượng đó. Trong CAT, các truy vấn liên tục chỉ được cập nhật nếu có sự thay đổi với các dữ liệu mà có thể đã ảnh hưởng đến kết quả truy vấn. CAT sử dụng bộ kích hoạt (trigger) để báo hiệu mỗi khi có sự thay đổi xảy ra. Một số kỹ thuật xử lý truy vấn khác Ngoài hai kỹ thuật trên còn có một số kỹ thuật xử lý truy vấn khác cũng đã được nghiên cứu sử dụng. SINA [24] được thiết kế để đánh giá các truy vấn phụ thuộc vị trí đồng thời. Khi có sự thay đổi dữ liệu, SINA chỉ tính toán cập nhật từ một câu trả lời đã xác định trước. Mokbel và Aref giới thiệu SOLE [25] để xử lý dữ liệu vị trí qua dòng dữ liệu bằng cách theo dõi các đối tượng có ý nghĩa và sử dụng cách tiếp cận phát tán tải (load shedding) để loại bỏ một số đối tượng nhất định đã lưu trữ khi hệ thống bị quá tải. SOLE là cách tiếp cận trong bộ nhớ và sử dụng đánh giá gia tăng để 17 xây dựng các kết quả truy vấn. SCUBA [29] được thiết kế để xử lý các truy vấn liên tục thông qua dòng dữ liệu nhận biết vị trí. SCUBA nhóm các đối tượng chuyển động và truy vấn thành các cụm đối tượng chuyển động, trong đó các đối tượng là gần nhau và di chuyển theo cùng một hướng. Đánh giá truy vấn cho tập các truy vấn được trừu tượng hóa như sự kết nối giữa các cụm chuyển động đó. ClusterSheddy [30] là phần mở rộng của SCUBA mà tập trung vào phát tán tải của các cụm dựa vào thuộc tính di chuyển như vị trí, thời gian, hướng và tốc độ. Nó cũng sử dụng cách truy vấn đánh giá gia tăng. Lazaridis và đồng nghiệp [16] trình bày một giải pháp mà tập trung vào các truy vấn động, tức là những truy vấn mà thay đổi theo thời gian. Điều này xảy ra khi các đối tượng quan tâm đến các truy vấn cũng chuyển động. Việc xử lý định kỳ các truy vấn được thực hiện bằng cách sử dụng chỉ mục của các hình bao biểu diễn cho chuyển động của đối tượng. Chỉ có các hình bao được cập nhật kể từ lần đánh giá cuối cùng là được kiểm tra. LOQOMOTION [13] cung cấp một giải pháp cho truy vấn trong đó cả người dùng và các đối tượng được hỏi có thể chuyển động. Giải pháp này sử dụng các tác nhân di động được phân bố trên một mạng lưới cố định để thực hiện nhiệm vụ xử lý như theo dõi vị trí của đối tượng chuyển động và làm mới các câu trả lời truy vấn… c. Tính riêng tư Với sự phát triển mạnh mẽ của công nghệ định vị toàn cầu, giờ đây độ chính xác về định vị vị trí cá nhân có thể tính đến đơn vị mét. Công nghệ này mang lại cho người sử dụng nhiều dịch vụ LBS với sự tiện nghi và thoải mái, nhưng cũng dẫn đến đe dọa tính riêng tư và an ninh của họ. Một khi thông tin vị trí bị lộ, đối tượng xấu có thể sử dụng thông tin vị trí này để suy luận ra thông tin về cuộc sống riêng tư của họ như mối quan hệ chính trị, thói quen sống, các vấn đề về bệnh tật hoặc ngay cả các bí mật kinh doanh của tổ chức liên quan… Người dùng luôn mong muốn có được tối đa các tiện ích của dịch vụ LBS mà không hoặc khó bị lộ thông tin vị trí của mình. Tính riêng tư thường được bảo vệ bằng một trong hai cách sau: - Ẩn danh: loại bỏ các liên hệ giữa danh tính người dùng với các dữ liệu vị trí 18