Luận án 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 1 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 2 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 3 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 4 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 5 DANH MỤC CÁC TỪ VIẾT TẮT VÀ KÝ HIỆU 2D/3D 2/3 Dimensional – 2/3 chiều CAMEL Continuous Active Monitor Engine - Cơ chế giám sát tích cực liên tục DBMS Database Management System – Hệ quản trị cơ sở dữ liệu DOA_Search Thuật toán tìm kiếm điều chỉnh theo mật độ của nút trên cây DO- TPR*-tree DO-TPR*-tree Cấu trúc cây điều chỉnh theo mật độ dựa trên TPR*-tree EWMA 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 Moving Objects Database – Cơ sở dữ liệu các đối tượng chuyển động MODM Moving Objects Database Model – Mô hình cơ sở dữ liệu các đối tượng chuyển động MQM Monitoring Query Management - Quản lý giám sát truy vấn MSB Motion-Sensitive bounding Boxes - Hộp ranh giới nhạy chuyển động PLACE Pervasive Location-Aware Computing Environments - Môi trường tính toán khắp nơi nhận biết vị trí RMF Recursive Motion Function – Hàm chuyển động đệ quy 6 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 7 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 8 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 9 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 10 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 11 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ị 12 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 (spatio- temporal) 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 13 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 14 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.