Chương 1: giới thiệu tổng quan, mục tiêu, phạm vi, và ý nghĩa của đề tài. Đồng thời kế hoạch thực hiện đề tài cũng được đề cập trong chương này. Chương 2: trình bày các cơ sở lý thuyết liên quan đến đề tài, bao gồm bài toán bảo vệ tính riêng tư cho các dịch vụ dựa trên vị trí và đặc trưng cho bài toán bảo vệ tính riêng tư về đường đi. Chương 3: khảo sát các công trình nghiên cứu liên quan đến đề tài, bao gồm mức ứng dụng, mức xuất bản dữ liệu, và mức cơ sở dữ liệu.
Chương 4: đề cập đến hướng nghiên cứu tiếp cận cụ thể cho đề tài luận văn từ nhu cầu ứng dụng và bài toán bảo vệ tính riêng tư, đề nghị mô hình dự đoán thông tin vị trí các đối tượng di chuyển và phương pháp gom nhóm các đối tượng di chuyển, và đề xuất cấu trúc cây chỉ mục không thời gian bảo vệ tính riêng tư và các tác vụ của cây chỉ mục này. Chương 5: mô tả sự phân tích về mặt lý thuyết của bài toán bảo vệ tính riêng tư cho người sử dụng dịch vụ dựa trên vị trí theo các giải pháp được đề xuất, đồng thời tiến hành đánh giá thử nghiệm, phân tích và so sánh các thông số thực nghiệm đo đạc được. Chương 6: tổng kết các công việc đã hoàn thành, các thiếu sót chính của luận văn, và đề nghị các hướng phát triển cho đề tài. Danh mục công trình công bố của tác giả: thể hiện các kết quả chính của luận văn được kiểm chứng từ các hội nghị quốc tế chuyên ngành có uy tín.
Tài liệu tham khảo: hỗ trợ cho quá trình nghiên cứu và thực hiện luận văn. Phụ lục bài báo khoa học. Phan Trọng Nhân – 10071052 Trang iv Bảo vệ tính riêng tư về đường đi cho người sử dụng dịch vụ LBS 2012 ABSTRACT Location-based services have been being predicted to bring superior development over the coming years. Keeping pace with this growth are new trends of predictive applications.
The violation of user privacy from revealed positions, however, brings great concerns to end-users when they enjoy these services. This is considered as one of the significant factors affecting to the prosperous development of location-based services in general and predictive location-based applications in particular. Besides, position information exposure, in terms of space and time, leads to trajectory disclosure. In other words, knowing the trajectory of a moving object opens the private and sensitive information of a corresponding user.
Dealing with challenges originating from both application and research, the final results of the thesis are focused on two emerging issues: (1) an efficient map-aware position prediction model of moving objects; and (2) an elastic privacy-aware spatio-temporal index structure. The structure of the thesis is organized as follows: Chapter 1: introduces the overview, objective, scope, and the significance of the thesis. In addition, the research plan is mentioned in this chapter. Chapter 2: presents related background, including user privacy protection in LBS and the characteristics of trajectory-based privacy preservation.
Chapter 3: surveys related work, consisting of application level, publication level, and database level. Chapter 4: mentions our research approach originating form application requirements and user privacy protection, suggests an efficient map-aware position prediction model of moving objects and the group-based method, and proposes an elastic privacy-aware spatio-temporal index structure and its operations. Chapter 5: describes theory-based analyses and conducts performance experiments for the proposed solutions. Chapter 6: concludes what have been done, what have been lacking, and our future work.
List of publications: shows that the final results of the thesis have been evaluated from reliable international conferences. References: support the research work. Phan Trọng Nhân – 10071052 Trang v Bảo vệ tính riêng tư về đường đi cho người sử dụng dịch vụ LBS 2012 LỜI CAM ĐOAN Chúng tôi cam đoan rằng ngoài các tài liệu tham khảo được liệt kê, kết quả nghiên cứu và trình bày luận văn do chính chúng tôi thực hiện và không sao chép từ các nguồn tài liệu và công trình nghiên cứu của các tác giả khác. Nếu có bất kỳ sai phạm nào, chúng tôi xin chịu trách nhiệm trước Hội đồng bảo vệ, Khoa quản lý chuyên ngành, và cơ sở đào tạo.
Thành phố Hồ Chí Minh, ngày 05 tháng 08 năm 2012 Phan Trọng Nhân – 10071052 Trang vi Bảo vệ tính riêng tư về đường đi cho người sử dụng dịch vụ LBS 2012 MỤC LỤC CÔNG TRÌNH ĐƢỢC HOÀN THÀNH. i NHIỆM VỤ LUẬN VĂN THẠC SĨ. v LỜI CAM ĐOAN. vi MỤC LỤC.
vii DANH MỤC HÌNH. ix DANH MỤC BẢNG. xi BẢNG TRA CỨU THUẬT NGỮ. xii CHƢƠNG 1: TỔNG QUAN .1 Giới thiệu đề tài .2 Mục tiêu nghiên cứu .3 Phạm vi đề tài .4 Ý nghĩa khoa học và thực tiễn .1 Ý nghĩa khoa học .2 Ý nghĩa thực tiễn .5 Kế hoạch thực hiện .1 Hướng tiếp cận đề tài .2 Phương pháp đánh giá .3 Kế hoạch thực hiện đề tài.
4 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT .1 Dịch vụ dựa trên vị trí .2 Tác nhân và chuỗi cung ứng .3 Bức tranh tổng quan bảo vệ tính riêng tư .3 Mô hình kiến trúc bảo vệ tính riêng tư .1 Kiến trúc không cộng tác .2 Kiến trúc có sự tham gia thành phần thứ ba .3 Kiến trúc ngang hàng.4 Bảo vệ tính riêng tư về đường đi .1 Miền ứng dụng. 15 Phan Trọng Nhân – 10071052 Trang vii Bảo vệ tính riêng tư về đường đi cho người sử dụng dịch vụ LBS 2012 2.3 Các nhân tố ảnh hưởng .4 Các đối tượng cần bảo vệ .5 Các hướng tiếp cận .6 Các yêu cầu và thách thức .5 Đường cong phủ kín không gian. 20 CHƢƠNG 3: CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN .1 Mức ứng dụng .2 Mức xuất bản dữ liệu.3 Mức cơ sở dữ liệu. 30 CHƢƠNG 4: HƢỚNG NGHIÊN CỨU TIẾP CẬN .1 Giới thiệu hướng tiếp cận .2 Phương pháp dự đoán trăng khuyết.1 Hàm thời gian tuyến tính.2 Vùng dự đoán vành khuyên .3 Dự đoán nhóm các đối tượng di chuyển .4 Cập nhật vị trí .3 Cây chỉ mục không thời gian bảo vệ tính riêng tư PPST-tree .1 Giới thiệu chung.2 Cấu trúc cây chỉ mục .3 Các tác vụ của cây chỉ mục.
46 CHƢƠNG 5: PHÂN TÍCH VÀ ĐÁNH GIÁ.1 Đánh giá lý thuyết .1 Phương pháp tấn công dựa trên thông tin vị trí được dự đoán .2 Phương pháp phòng vệ .2 Đánh giá thử nghiệm .1 Thiết lập thí nghiệm .2 Tiến hành thí nghiệm.3 Kết quả đánh giá. 58 CHƢƠNG 6: TỔNG KẾT .2 Các kết quả chính đạt được .4 Hướng phát triển .1 Xu hướng chung .2 Kỹ thuật bảo vệ tính riêng tư hỗ trợ kèm theo. 64 DANH MỤC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ. 66 TÀI LIỆU THAM KHẢO.
67 PHỤ LỤC BÀI BÁO KHOA HỌC. 71 Phan Trọng Nhân – 10071052 Trang viii Bảo vệ tính riêng tư về đường đi cho người sử dụng dịch vụ LBS 2012 DANH MỤC HÌ NH Hình 2-1: Vai trò trong LBS [14]. 6 Hình 2-2: Chuỗi cung ứng LBS [14]. 6 Hình 2-3: Phân loại LBS theo lĩnh vực dịch vụ [26].
9 Hình 2-4: Tổng quan bảo vệ tính riêng tư [14]. 12 Hình 2-5: Kiến trúc không cộng tác [19]. 13 Hình 2-6: Kiến trúc có sự tham gia thành phần thứ ba [19]. 13 Hình 2-7: Kiến trúc cộng tác ngang hàng [19].
14 Hình 2-8: Ba hướng tiếp cận chính triển khai bảo vệ tính riêng tư. 18 Hình 2-9: Ví dụ đường cong phủ kín không gian; (a) Đường cong Peano (đường cong Z); (b) Đường cong Hilbert [35]. 21 Hình 3-1: Quỹ đạo của người dùng và các quỹ đạo giả [13]. 24 Hình 3-2: Mô hình vùng pha [3].
25 Hình 3-3: Kỹ thuật vùng pha động với hai quỹ đạo người dùng; (a) Trước khi xáo trộn vị trí, (b) Sau khi xáo trộn vị trí [45]. 26 Hình 3-4: Mô hình hệ thống bảo vệ tính riêng tư vị trí [5]. 27 Hình 3-5: Tổng quát hóa quỹ đạo người dùng dựa trên (k-1) quỹ đạo kế cận [29]. 28 Hình 3-6: Kiến trúc hệ thống bảo vệ tính riêng tư cho các câu truy vấn liên tục [33].
28 Hình 3-7: Phân tích mức độ thường xuyên của phân khúc đường của người dùng trong khoảng thời gian [t1, t2] [43]. 29 Hình 3-8: Ẩn danh quỹ đạo thông qua phương pháp tổng quát hóa không thời gian [10]. 30 Hình 3-9: Xấp xỉ quỹ đạo bằng MBBs [22]. 31 Hình 3-10: Cấu trúc tổng quan của PPFI [37].
31 Hình 3-11: Biểu diễn MBRs và VBRs trong TPR*-tree [38]. 32 Hình 3-12: Kiến trúc hệ thống tổng quan ứng dụng thuật giải PLU [39]. 33 Hình 3-13: Cây Bx-tree [35]. 33 Hình 3-14: Hai khung chỉ mục của giải thuật MOVIES [41].
34 Phan Trọng Nhân – 10071052 Trang ix Bảo vệ tính riêng tư về đường đi cho người sử dụng dịch vụ LBS 2012 Hình 3-15: Kiến trúc hệ thống cho bộ máy truy vấn truy vết quỹ đạo [8]. 35 Hình 3-16: Kiến trúc hệ thống của Casper* [4]. 35 Hình 3-17: Kiến trúc hệ thống sử dụng cấu trúc chỉ mục hợp nhất SPPF-tree [31]. 36 Hình 3-18: OST-tree [28].
37 Hình 3-19: Bob-tree; (a) Cấu trúc cây tổng quan, (b) Cấu trúc một nút của cây [27]. 37 Hình 4-1: Hướng tiếp cận nghiên cứu ban đầu. 38 Hình 4-2: Ánh xạ không gian bằng đường cong phủ kín không gian Hilbert; (a) Không gian gốc, (b) Áp dụng đường cong Hilbert lên không gian gốc. 39 Hình 4-3: Mô hình tổng quan chiến lược bảo vệ tính riêng tư với PPST-tree.
40 Hình 4-4: Phương pháp dự đoán được đề xuất; (a) Miền dự đoán bán nguyệt, (b) Miền dự đoán vành khuyên, (c) Miền dự đoán suy biến thành các giao điểm. 42 Hình 4-5: Cách tiếp cận cây chỉ mục PPST-tree. 45 Hình 4-6: Minh họa truy vấn thông tin các đối tượng di chuyển ở mức ứng dụng. 45 Hình 4-7: PPST-tree; (a) Cấu trúc chỉ mục; (b) Một ví dụ cây cụ thể.
46 Hình 4-8: Giải thuật tìm kiếm cho truy vấn gộp từ cây PPST-tree. 49 Hình 4-9: Giải thuật tìm kiếm tích hợp bảo vệ tính riêng tư cho truy vấn vị trí dự đoán của một đối tượng di chuyển cụ thể từ cây PPST-tree. 50 Hình 4-10: Giải thuật mở rộng giá trị khóa cho vùng không gian dự đoán dựa trên các nút láng giềng. 51 Hình 5-1: Tấn công dựa trên thông tin vị trí được dự đoán; (a) Trường hợp dự đoán trăng khuyết, (b) Trường hợp dự đoán vành khuyên, (c) Trường hợp dự đoán giao điểm.
53 Hình 5-2: So sánh chi phí lưu trữ. 59 Hình 5-3: So sánh chi phí vận hành; (a) Tác vụ chèn, (b) Tác vụ tìm kiếm. 60 Hình 5-4: Thời gian xử lý cho tác vụ chèn, tìm kiếm, và cập nhật giá trị khóa của cây PPST- tree.