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ừ đó. 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. Đ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. 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.
Ứ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 (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. Đồ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 12 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. 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 14 độ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 15 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 16 đánh giá rất cao và tiếp tục được cải 17 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.