Tài liệu Xây dựng hệ thống quản lý thông tin về khí hậu dùng vào mạng cảm biến

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG THỊ HUẾ XÂY DỰNG HỆ THỐNG QUẢN LÝ THÔNG TIN VỀ KHÍ HẬU SỬ DỤNG VÀO MẠNG CẢM BIẾN Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. VŨ THỊ HỒNG NHẠN Hà Nội, năm 2014 1 CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu, tìm hiểu của riêng cá nhân tôi. Trong toàn bộ nội dung của luận văn, những điểm được trình bày là của cá nhân tôi, hoặc là được tổng hợp từ nhiều nguồn tài liệu, các luận điểm đưa ra rõ ràng, chính xác, các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 26 tháng 6 năm 2014 Tác giả luận văn HOÀNG THỊ HUẾ 2 LỜI CẢM ƠN Để hoàn thành luận văn tốt nghiệp là cả một quá trình đầy khó khăn và thử thách trong học tập và nghiên cứu của bản thân. Để có được những thành quả như ngày hôm nay, ngoài những nỗ lực của bản thân, không thể không nhắc tới là sự động viên, giúp đỡ của các thầy, cô giáo, bạn bè, đồng nghiệp và người thân trong gia đình. Tôi xin trân trọng cảm ơn TS. Vũ Thị Hồng Nhạn là giảng viên của trường Đại học Công Nghệ đã hướng dẫn tận tình, chu đáo và giúp đỡ tôi hiểu về chuyên môn, nghiên cứu cũng như định hướng phát triển trong suốt quá trình làm luận văn. Tôi cũng xin gửi lời cảm ơn tới các thầy cô giáo trong trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội đã giảng dạy, truyền đạt những kiến thức bổ ích về lĩnh vực công nghệ phần mềm mà tôi đã theo đuổi và đồng thời đã tạo điều kiện thuận lợi cho tôi trong quá trình học tập cũng như nghiên cứu đề tài này. Tôi xin cảm ơn tất cả các bạn bè cùng khóa đã cho tôi cơ hội được trao đổi, chia sẻ kiến thức cũng như kinh nghiệm thực tế qua các môn học, giúp tôi có thể tiếp thu được thêm nhiều vấn đề mới không chỉ trong lĩnh vực chuyên ngành phần mềm của mình. Cuối cùng, tôi xin gửi lời bày tỏ cảm ơn chân thành và sâu sắc tới gia đình của tôi. Gia đình là chỗ dựa tinh thần đã luôn ở bên tôi, ủng hộ tôi trong suốt quá trình học tập và nghiên cứu để tôi có thể hoàn thành bản luận văn này. Dù đã rất cố gắng song luận văn chắc chắn không tránh khỏi các thiếu sót, tôi rất mong nhận được các ý kiến đóng góp quý báu của thầy cô và các bạn. Xin chân thành cảm ơn! Hà Nội, ngày 26 tháng 6 năm 2014 Tác giả luận văn HOÀNG THỊ HUẾ 3 MỤC LỤC CAM ĐOAN ........................................................................................................1 LỜI CẢM ƠN .....................................................................................................2 MỤC LỤC ...........................................................................................................3 DANH MỤC HÌNH VẼ ...................................................................................... 5 Chương 1 .............................................................................................................8 GIỚI THIỆU .......................................................................................................8 1.1 Bối cảnh chung ........................................................................................ 8 1.2 Động cơ và định nghĩa bài toán ............................................................. 10 1.3 Giới hạn và phạm vi nghiên cứu ............................................................ 12 1.4 Bố cục của luận văn ...............................................................................13 Chương 2 ...........................................................................................................14 TỔNG QUAN VỀ MẠNG CẢM BIẾN VÀ ỨNG DỤNG ............................ 14 2.1 Cơ sở dữ liệu mạng cảm biến ................................................................ 14 2.2 Mô hình lưu trữ dữ liệu cảm biến .......................................................... 16 2.2.1 Lữu trữ tập trung và tìm kiếm .................................................... 17 2.2.2 Lưu trữ cục bộ và tìm kiếm địa lý ..............................................17 2.2.3 Lưu trữ cục bộ với chỉ mục phân tán .........................................18 2.2.4 Phương pháp lưu trữ cục bộ với đa độ phân giải ....................... 18 2.3 Các cách tiếp cận xử lý truy vấn cho ứng dụng với mạng cảm biến .....19 2.4 Quản lý hệ thống mạng cảm biến .......................................................... 23 2.4.1 Hệ thống xử lý tổng hợp dữ liệu bên trong mạng ...................... 23 2.4.2 Hệ thống dữ liệu lịch sử dài hạn ................................................26 Chương 3 ...........................................................................................................29 KHÁI NIỆM VÀ ĐỊNH NGHĨA .....................................................................29 3.1 Bối cảnh và giả thiết ..............................................................................29 3.2 Dữ liệu cảm biến và cách lưu trữ ........................................................... 31 3.3 Phân tích các loại truy vấn trong mạng cảm biến ..................................33 Chương 4 ...........................................................................................................36 PHƯƠNG PHÁP GIẢM DỮ LIỆU BA PHA CHO MẠNG CẢM BIẾN ...36 4.1 Giới thiệu ............................................................................................... 36 4.2 Loại bỏ các bản ghi trùng lặp ................................................................ 38 4.3 Khoảng cách giá trị dựa trên dữ liệu giảm.............................................40 Chương 5 ...........................................................................................................46 4 XỬ LÝ TRUY VẤN DỰA TRÊN PROXY .................................................... 46 5.1 Chức năng của Proxy .............................................................................46 5.2 Phân tích lịch sử của các truy vấn tại Proxy ..........................................48 5.3 Cơ sở dữ liệu siêu dữ liệu trong Proxy ..................................................50 Chương 6 ...........................................................................................................55 CÁC THÍ NGHIỆM VÀ PHÂN TÍNH HIỆU SUẤT ....................................55 6.1 Môi trường thí nghiệm ...........................................................................55 6.2 Hiệu quả lưu trữ thông qua cơ chế giảm dữ liệu ...................................56 6.3 Độ chính xác của truy vấn .....................................................................64 6.4 Hiệu quả của xử lý truy vấn bằng cách sử dụng Proxy và hệ thống thử nghiệm theo dõi khí hậu ............................................................................................ 68 Chương 7 ...........................................................................................................72 KẾT LUẬN .......................................................................................................72 TÀI LIỆU THAM KHẢO ................................................................................74 5 DANH MỤC HÌNH VẼ Hình 1.1 Tổng quan về mạng cảm biến................................................................ 9 Hình 2.1 Hai cách tiếp cận trong cơ sở dữ liệu mạng cảm biến......................... 15 Hình 2.2 Tổng hợp đa độ phân giải ....................................................................19 Hình 2.3 Ví dụ về tập hợp đơn giản trong mạng ................................................20 Hình 2.4 Mạng cảm biến với một mạng (trái) và tổng hợp nhóm áp dụng cho nó (phải) trong TAG ...........................................................................................................21 Hình 2.5 Giám sát mạng cảm biến không dây ...................................................22 Hình 2.6 Khái niệm về xử lý dữ liệu cho hệ thống cơ sở dữ liệu cảm biến của TinyDB hoặc Cougar .....................................................................................................24 Hình 2.7 Kiến trúc tổng thể của Fjord ................................................................ 25 Hình 2.8 Kiến trúc mạng cảm biến hai lớp StonesDB .......................................27 Hình 2.9 Mô hình cơ bản trong MauveDB......................................................... 28 Bảng 3.1 Dữ liệu yêu cầu ước tính cho các ứng dụng khoa học ........................ 30 Hình 4.1 Tổng quan lược đồ giảm dữ liệu ba pha ..............................................37 Hình 4.2 Ví dụ giảm dữ liệu của pha Naïve ....................................................... 39 Thuật toán 4.1: Thủ tục so sánh các bản ghi nhân đôi ......................................40 Hình 4.3 Ví dụ về sơ đồ giảm dữ liệu dựa trên giá trị khoảng cách...................42 Thuật toán 4.2 Ước khoảng giá trị trên một khoảng dữ liệu dựa vào các thông số về khoảng cách ..........................................................................................................44 Hình 4.4 Tác dụng của việc giảm dữ liệu........................................................... 45 Hình 5.1 Tổng quan về hệ thống ba tầng mạng cảm biến ..................................47 Hình 5.2 Các truy vấn có điều kiện tìm kiếm chồng chéo .................................49 Bảng 5.1 Mô tả bảng siêu dữ liệu không gian .................................................... 51 6 Bảng 5.2 Mô tả bảng lịch sử truy vấn ............................................................... 52 Hình 5.3 Thủ tục đăng ký truy vấn .....................................................................53 Bảng 5.3 Lưu trữ dữ liệu trong bảng lịch sử truy vấn ........................................53 Bảng 5.4 Lưu trữ dữ liệu trong bảng lịch sử truy vấn theo thời gian .................53 Bảng 6.2 Tóm tắt các thông số ...........................................................................55 Hình 6.3 Dữ liệu giảm theo cơ chế ba pha với tập 5 cảm biến và ngưỡng giá trị khoảng cách của Level1 và Level2 là 1.........................................................................56 Hình 6.4 Thời gian thực hiện thuật toán giảm giữ liệu theo cơ chế ba pha với tập 5 cảm biến và ngưỡng giá trị khoảng cách của Level1 và Level2 là 1 ...................57 Hình 6.5 Dữ liệu giảm theo cơ chế ba pha với tập 7 cảm biến và ngưỡng giá trị khoảng cách của Level1 và Level2 là 1.........................................................................58 Hình 6.6 Thời gian thực hiện thuật toán giảm giữ liệu theo cơ chế ba pha với tập 7 cảm biến và ngưỡng giá trị khoảng cách của Level1 và Level2 là 1 ...................59 Hình 6.7 Dữ liệu giảm theo cơ chế ba pha với tập 9 cảm biến và ngưỡng giá trị khoảng cách của Level1 và Level2 là 0,5......................................................................61 Hình 6.8 Thời gian thực hiện thuật toán giảm giữ liệu theo cơ chế ba pha với tập 9 cảm biến và ngưỡng giá trị khoảng cách của Level1 và Level2 là 0.5 ................62 Hình 6.9 So sánh nhiệt độ trung bình của 2 cơ chế giảm dữ liệu giảm dữ liệu .65 so với nhiệt độ trung bình của dữ liệu thô theo khoảng thời gian ...................... 65 Hình 6.10 So sánh nhiệt độ trung bình của 2 cơ chế giảm dữ liệu giảm dữ liệu so với nhiệt độ trung bình của dữ liệu thô theo từng Cảm biến ....................................66 Hình 6.11 Tỉ lệ lỗi trung bình của nhiệt độ theo khoảng thời gian .................... 67 Hình 6.12 Tỉ lệ lỗi trung bình của nhiệt độ theo từng cảm biến ........................ 67 Hình 6.13: Tổng quan về hệ thống sử dụng mạng cảm biến để giám sát môi trường ............................................................................................................................ 69 7 Hình 6.14 Hệ thống thử nghiệm theo dõi thông tin về khí hậu .......................... 70 Hình 6.15 Đăng ký truy vấn từ người dùng ....................................................... 70 8 Chương 1 GIỚI THIỆU Mạng cảm biến không dây đang được sử dụng trong nhiều lĩnh vực ứng dụng dân sự, bao gồm cả môi trường, giám sát môi trường sống, các ứng dụng chăm sóc sức khỏe, nhà tự động hóa và điều khiển giao thông,... Cho đến nay, có rất nhiều nghiên cứu đã và đang thực hiện thiết kế những cấu trúc mạng cảm biến phù hợp có thể triển khai trong các lĩnh vực ứng dụng đó. Bên cạnh đó, việc quản lý và xử lý thông tin thu được từ mạng cảm biến cũng là một trong những yêu cầu cấp thiết vì dữ liệu dưới dạng dòng (data stream) và được thu liên tục theo thời gian thực. Dữ liệu thu được thường có nhiều nhiễu hoặc lặp lại trong một khoảng thời gian nào đó. Vì thế để tiết kiệm tài nguyên dung lượng nhớ khan hiếm và tăng tốc thời gian xử lý, chúng ta cần có những biện pháp tiền xử lý trước khi đưa vào quản lý và sử dụng lâu dài trong các ứng dụng hỗ trợ quyết định. Nghiên cứu này sẽ tập trung tìm hiểu, giới thiệu một hệ thống theo dõi thông tin về thời tiết và khảo sát các kiến trúc hệ thống ứng dụng công nghệ mạng cảm biến. Một số kỹ thuật xử lý và lưu trữ các dòng dữ liệu cảm biến theo thời gian thực sẽ được thiết kế để hỗ trợ các truy vấn liên quan tới dữ liệu biến đổi liên tục theo không gian và thời gian. Đặc biệt nghiên cứu sẽ tìm hiểu và triển khai phương pháp xử lý dữ liệu cảm biến thu được với mục tiêu giảm dung lượng lưu trữ đồng thời vẫn đảm bảo độ chính xác về thông tin. Hiệu năng của phương pháp sẽ được đánh giá trong các truy vấn dữ liệu theo sự thay đổi về các điều kiện truy vấn liên quan tới không gian và thời gian. 1.1 Bối cảnh chung Sự tiến bộ của các mạng cảm biến và các công nghệ phần cứng hiện đại đã đưa tới sự ra đời của các khái niệm điện toán đến khắp mọi nơi cho các ứng dụng thế giới thực như giám sát địa vật lý, theo dõi vi khí hậu, giám sát ô nhiễm không khí, theo dõi chuyển động, theo dõi cấu trúc sức khỏe, theo dõi bệnh nhân y tế,... Mạng cảm biến được tạo nên bởi một số lượng lớn các cảm biến, chúng có khả năng thu thập và giao tiếp dữ liệu liên tục với nhau (như hình 1.1). Những cảm biến 9 này được thiết kế để thu dữ liệu trong phạm vi một khu vực ứng dụng cụ thể (ví dụ: nhiệt độ, ánh sáng, âm thanh và áp suất), dữ liệu sau đó được truyền về một máy chủ bằng cách phối hợp với các trạm trung gian khác được đặt gần chúng. Các máy chủ giám sát toàn hệ thống, quản lý các dữ liệu thu được và cung cấp một giao diện để xử lý các truy vấn của người dùng và hiển thị kết quả truy vấn cho người dùng. Các cảm biến có thể sẽ tiết kiệm năng lượng bằng các phương pháp truyền thông tối ưu [Madd 2005]. Hình 1.1 Tổng quan về mạng cảm biến Trong môi trường này, dữ liệu cảm biến được định nghĩa như là siêu dữ liệu (ví dụ: dữ liệu được lưu trữ), trong đó bao gồm các thông tin không gian (địa điểm), các chi tiết kỹ thuật và các dữ liệu đo (ví dụ: dữ liệu cảm biến) cùng với thời gian [Bonn 2001, Yao 2002]. Những dữ liệu này được sử dụng để trả lời không chỉ truy vấn không gian và thời gian, mà còn cả truy vấn không gian thời gian. Để có được các kết quả của các truy vấn thì hệ thống ứng dụng thực hiện các hoạt động liên quan đến điều kiện không gian, thời gian, hoặc cả không gian thời gian. Theo đó, một giải pháp tốt cho vấn đề xử lý hiệu quả các truy vấn phức tạp liên quan đến không gian, thời gian hoặc cả không gian thời gian là cần thiết. Các loại truy vấn lịch sử chủ yếu là phân tích định kỳ hoặc thống kê các số liệu của luồng dữ liệu. Vì vậy, hiểu được các tính năng của dữ liệu trong mạng cảm biến là rất quan trọng đối với xử lý hiệu quả các truy vấn và cung cấp dịch vụ tối ưu theo các yêu cầu trong mỗi ứng dụng. Cho đến nay, nhiều công trình nghiên cứu về xử lý truy vấn dữ liệu trong mạng 10 cảm biến và quản lý hệ thống mạng cảm biến đã được giới thiệu. Hầu hết trong số đó chủ yếu quan tâm đến các phương pháp xử lý truy vấn liên tục và quản lý dữ liệu trong mạng cảm biến theo hướng tiêu thụ năng lượng hiệu quả. Mạng cảm biến được coi như là một cơ sở dữ liệu phân tán và cung cấp ngôn ngữ truy vấn khai báo. Để giảm tiêu thụ năng lượng trong các nút cảm biến đã có nhiều đề xuất để thực hiên như: kế hoạch truy vấn hiệu quả, giảm thiểu sử dụng tài nguyên trong hệ thống, tối ưu hóa truy vấn trung tâm, sử dụng cách tiếp cận xử lý truy vấn ước khoảng thu khi dữ liệu từ đó dữ liệu được yêu cầu tùy thuộc vào các truy vấn cụ thể. Mặt khác, một số nghiên cứu tập trung xây dựng những hệ thống tích hợp mạng cảm biến với hệ thống quản lý dữ liệu dòng (DSMS: Data Stream Management System), trong đó có xem xét hiệu quả của việc sử dụng năng lượng. Các mô hình hệ thống sử dụng kiến trúc proxy bao gồm cả thiết bị chạy bằng pin không chỉ các chức năng xử lý truy vấn trong mạng mà còn có các chức năng xử lý truy vấn lịch sử trong hệ thống quản lý dữ liệu dòng. 1.2 Động cơ và định nghĩa bài toán Trong vài năm qua, những thách thức chính trong mạng cảm biến chủ yếu là làm thế nào để dữ liệu đến từ mạng cảm biến phân tán với nguồn năng lượng hạn chế trên các nút. Trong những ứng dụng mạng cảm biến, hầu hết các truy vấn có thể được phân loại thành truy vấn trực tiếp thu dữ liệu và các truy vấn dữ liệu lịch sử đang được lưu trữ [Diao 2007]. Các truy vấn trực tiếp thu dữ liệu hữu ích cho hầu hết các ứng dụng giám sát phát hiện các sự kiện bất thường như cháy, giám sát theo dõi lở đất và giám sát môi trường sống. TinyDB và Cougar [Yao 2002] cung cấp ngôn ngữ truy vấn giống như ngôn ngữ truy vấn SQL, tập trung vào xử lý truy vấn liên tục cho các ứng dụng sử dụng trong mạng tập hợp và lọc các phương pháp với mức tiêu thụ năng lượng hiệu quả. Tuy nhiên, các phương pháp tiếp cận này có một số hạn chế liên quan đến mặt ứng dụng như phát hiện mô hình đặc biệt và phân tích xu hướng lịch sử. Ví dụ như các ứng dụng quản lý hệ sinh thái, quản lý môi trường khí hậu, ô nhiễm không khí và quản lý nhu cầu tích lũy dữ liệu thu thập từ mạng cảm biến vào một cơ sở dữ liệu để phân tích dữ liệu sau đó,… Trong khi đó, truy vấn dữ liệu lịch sử chủ yếu là khai thác trong một mạng cảm biến với sự hỗ trợ của các thiết bị cảm biến dựa trên flash được gọi là mạng cảm biến lưu trữ tập trung, nơi các nút cảm biến được trang bị dung lượng cao và tiết kiệm năng lượng lưu trữ flash cục bộ [Diao 2007]. Các nút cảm biến flash đều có thể duy trì một số lượng lớn dữ liệu lịch sử trong bộ nhớ của chúng. Ví dụ như xây dựng đa độ phân giải tổng hợp sử dụng sóng lăn tăn, dữ liệu sau đó được gửi proxy được chạy pin (ví 11 dụ trạm cơ sở). Người dùng truy vấn dữ liệu đã được nén với khối lượng không gian thời gian ban đầu rất lớn mà vẫn có thể có được kết quả gần đúng từ dữ liệu tổng hợp đó. Theo [Aly 2008] trong mạng sự kiện có sử dụng lưu trữ dữ liệu tập trung có liên quan đến việc nhận diện lưu trữ tại các điểm được xác định trong mạng. Mặc dù cơ chế lưu trữ cho thao tác truy vấn lịch sử hiệu quả cao về năng lượng, nhưng liên quan đến chi phí truyền dữ liệu tổng hợp tới proxy và duy trì việc xây dựng các cấu trúc thực hiện truy vấn và phân phối các hoạt động truy vấn giữa proxy cũng như hệ thống ứng dụng vẫn đang là mối quan tâm lớn. Khả năng duy trì dữ liệu thô trong bộ nhớ cục bộ của mỗi nút cảm biến sao cho chúng được sử dụng càng lâu càng tốt. Mục tiêu của nghiên cứu này là giải quyết các hạn chế của các nút cảm biến sao cho vừa tiết kiệm bộ nhớ cục bộ mà vẫn đảm bảo mức mất mát tối thiểu nhất của dữ liệu thô và hứa hẹn cung cấp đầy đủ thông tin để xử lý các truy vấn liên quan dữ liệu lịch sử. Cụ thể, nghiên cứu này được bắt đầu bởi bốn động cơ nghiên cứu như sau:  Làm thế nào để quản lý dữ liệu trong bộ nhớ cục bộ của mỗi nút cảm biến có giới hạn về năng lượng một cách hiệu quả.  Làm thế nào để duy trì dữ liệu lịch sử càng lâu càng tốt trong khi có thể tiết kiệm dung lượng lưu trữ của mỗi nút cảm biến.  Làm thế nào để xử lý các truy vấn liên quan tới dữ liệu lịch sử trong hệ thống mạng cảm biến.  Làm thế nào để phân tán các truy vấn cần phải xử lý ở trong mạng cảm biến hoặc trong hệ thống ứng dụng một cách tối ưu. Ví dụ để xử lý các truy vấn “Khu vực nào có nhiệt độ trung bình hơn 29 độ hơn 2 tuần qua?”, hoặc “Nhiệt độ trung bình mỗi ngày trong vùng A từ 01 tháng 03 năm 2014 đến 30 tháng 04 năm 2014 là gì?” Nút cảm biến nên có khả năng lưu trữ dữ liệu lịch sử được tích lũy qua thời gian để lưu trữ cục bộ. Tuy nhiên, không giống như trên ổ đĩa lưu trữ dữ liệu trong cơ sở dữ liệu truyền thống, mạng cảm biến hầu như không quản lý một khối lượng lớn các dữ liệu tích lũy trong lưu trữ cục bộ bằng cách áp dụng lưu trữ sao lưu hoặc cơ chế lưu trữ như cơ sở dữ liệu truyền thống. Làm thế nào để khai thác dung lượng lưu trữ hạn chế của các nút cảm biến có hiệu quả trở thành một vấn đề rất quan trọng. Ngoài ra tồn tại trường hợp truy vấn trùng lặp hoàn toàn, các nút cảm biến phải thực hiện một số lần lặp đi lặp lại. Để giải quyết vấn đề này, với một tập các truy vấn được gửi tới hệ thống, chúng ta cần phân tích điều kiện truy vấn xem điều kiện đó có trùng lặp với các truy vấn trước đó không. Dựa trên phân tích điều kiện truy vấn này, những thao tác truy vấn nào bị lặp sẽ không phải xử lý lại nữa. 12 1.3 Giới hạn và phạm vi nghiên cứu Trong luận văn này sẽ tìm hiểu và triển khai kỹ thuật xử lý truy vấn lịch sử dựa trên kiến trúc proxy cho truy vấn phổ biến và phương pháp lưu trữ dữ liệu gần đúng tập trung đảm bảo việc tiêu thu năng lượng hiệu quả. Trong cách tiếp cận của luận văn, dữ liệu thô thu được sẽ phải trải qua một bước tiền xử lý trước khi được lưu trữ vào bộ nhớ của nút cảm biến. Cơ chế ba pha được áp dụng bằng cách tổng hợp một số bản ghi mà thông tin liên tiếp có giá trị khác biệt tương đối nhỏ trong một khoảng thời gian nào đó và thay thế chúng bằng một bản ghi có giá trị tương đối gần đúng nhất. Hoạt động này không chỉ giúp loại bỏ các bản ghi trùng lặp, mà còn giữ lại bản ghi có giá trị gần đúng trong các nút cảm biến, cung cấp đủ thông tin để có độ chính xác cao của các câu trả lời truy vấn. Ngoài ra, luận văn có đưa ra cách sử dụng proxy để xử lý dữ liệu và các truy vấn giữa mạng cảm biến và hệ thống ứng dụng. Proxy có nhiệm vụ phân tích những truy vấn có điều kiện truy vấn trùng lặp. Nhiệm vụ này được thực hiện với sự hỗ trợ của bảng lịch sử truy vấn trong đó có lưu siêu dữ liệu (metadata). Truy vấn nào chưa xuất hiện trước đó thì truyền vào mạng cảm biến, nếu đã xuất hiện trước đó thì hệ thống lấy kết quả từ hệ thống ứng dụng. Cơ chế hoạt động này không chỉ giải quyết việc trùng lặp trong truy vấn, mà còn cung cấp hoạt động thực hiện truy vấn trong mạng cảm biến và hệ thống ứng dụng một cách dễ dàng. Do đó, năng lượng tiêu thụ trong mạng cảm biến sẽ được giảm. Sơ lược luận văn có thể được tóm tắt như sau:  Định nghĩa các khái niệm liên quan đến mạng cảm biến, lưu trữ cục bộ của một nút cảm biến và siêu dữ liệu được sử dụng trong việc xử lý các truy vấn lịch sử.  Phương pháp giảm thiểu dữ liệu cảm biến được đề xuất để hỗ trợ việc quản lý các dữ liệu lịch sử trong lưu trữ cục bộ với chi phí năng lượng thấp. Nghiên cứu đề xuất thực hiện nén dữ liệu qua nhiều giai đoạn, dữ liệu gần đúng cuối cùng được lưu giữ trong các nút cảm biến dựa trên khoảng cách của các giá trị liên tục trong một số bản ghi đọc được từ cảm biến.  Kỹ thuật xử lý truy vấn trùng lặp mang lại tính tối ưu trong việc truyền dữ liệu giữa các mạng cảm biến và hệ thống ứng dụng, tránh xử lý nhiều lần một thao tác truy vấn trùng lặp. Hiệu quả của phương pháp đề xuất được đánh giá dựa trên một số yếu tố khác nhau như: độ chính xác của các dữ liệu thô được duy trì là bao nhiêu, khả năng lưu trữ là bao nhiêu bằng cách sử dụng chiến lược giảm thiểu dữ liệu và ảnh hưởng của proxy 13 trong hệ thống mạng cảm biến như thế nào trong các xử lý truy vấn và tiêu thụ năng lượng. 1.4 Bố cục của luận văn Với mục tiêu như đã nêu ở trên, luận văn bao gồm bảy chương với nội dung nghiên cứu như sau: Chương 1: Giới thiệu tổng quan về đề tài. Chương 2: Trình bày một số tài liệu nghiên cứu, các khái niệm trong cơ sở dữ liệu mạng cảm biến, kỹ thuật xử lý truy vấn, đề án lưu trữ dữ liệu cảm biến và quản lý hệ thống mạng cảm biến. Phân tích hạn chế của các phương pháp tiếp cận hiện có đối với việc quản lý dữ liệu và thao tác truy vấn liên quan tới việc tiêu thụ năng lượng trong mạng cảm biến. Chương 3: Mô tả kiến trúc mạng cảm biến, các định nghĩa của mô hình dữ liệu, lược đồ lưu trữ, các mô hình truy vấn không gian, thời gian và cả không gian thời gian. Trình bày kịch bản sử dụng và một số hạn chế của môi trường mạng cảm. Chương 4: Liên quan tới tính năng của tín hiệu nhận được, luận văn sẽ giới thiệu một cơ chế giảm thiểu dữ liệu ba pha, trong đó giá trị của các bản ghi đọc được từ cảm biến liên tục được việc kiểm tra, nếu sự khác biệt của chúng quá nhỏ, giá trị mới có thể được loại bỏ. Cơ chế này dẫn đến sự mất mát một số thông tin tuy nhiên lại không ảnh hưởng tới ứng dụng, ngược lại lưu trữ tại các nút cảm biến có thể được tăng lên đáng kể. Chương 5: Trình bày chi tiết kỹ thuật xử lý truy vấn cảm biến. Đặc biệt, giới thiệu cơ chế giải quyết vấn đề trùng lặp ở các truy vấn mạng cảm biến. Tại proxy, truy vấn lịch sử do người dùng phát hành sẽ được phân tích và khoảng thời gian của điều kiện truy vấn được chia dọc theo vòng đời của truy vấn, nhờ đó các truy vấn trùng lặp là duy nhất theo khoảng thời gian truy vấn. Các truy vấn này sau đó được gửi vào mạng cảm biến hoặc hệ thống ứng dụng để xử lý. Chương 6: Thực hiện kỹ thuật đề xuất, đánh giá và so sánh với các phương pháp lấy mẫu dựa trên sự kiện được sử dụng trong TinyDB liên quan đến một số yếu tố như: mức độ chính xác của dữ liệu sau khi đi qua các hoạt động xử lý dữ liệu gần đúng, hiệu quả lưu trữ tại mỗi nút trong bộ cảm biến, số lượng bản ghi dữ liệu được thực hiện trong truy vấn và hiệu quả của việc sử dụng proxy về quản lý dữ liệu cũng như xử lý truy vấn. Chương 7: Tóm tắt nghiên cứu thực hiện được và trình bày một số vấn đề cần thảo luận. 14 Chương 2 TỔNG QUAN VỀ MẠNG CẢM BIẾN VÀ ỨNG DỤNG Trong mạng cảm biến, hầu hết các nghiên cứu quan trọng đều quan tâm đến nguồn tài nguyên hạn chế như tuổi thọ pin, dung lượng bộ nhớ và không gian lưu trữ của các nút cảm biến trong mạng. Vì vậy, xử lý các nút trong mạng như thế nào để việc sử dụng năng lượng được hiệu quả. Trong chương này sẽ tổng quan và phân tích các nghiên cứu trước đây trong mạng cảm biến với việc xem xét giảm chi phí năng lượng. 2.1 Cơ sở dữ liệu mạng cảm biến Từ một điểm lưu trữ dữ liệu, mạng cảm biến có thể được định nghĩa như là một cơ sở dữ liệu phân tán, có nhiệm vụ thu thập các phép đo vật lý về môi trường, các chỉ số và phục vụ truy vấn từ người dùng và các ứng dụng khác từ bên ngoài mạng hoặc bên trong mạng [Bonn 2001, Madd 2005]. Cơ sở dữ liệu mạng cảm biến cho phép bất kỳ người dùng nào cũng có thể phát đi một truy vấn đến mạng cảm biến như một hệ thống cơ sở dữ liệu thông thường và nhận phản hồi từ truy vấn đó. Như vậy có thể coi mạng cảm biến như một hệ thống định tuyến dữ liệu trung tâm [Ratn 2003]. Có ít nhất hai cách tiếp cận dễ nhận thấy của một cơ sở dữ liệu mạng cảm biến như trong Hình 2.1:  Hình 2.1(a) là cơ sở dữ liệu tập trung: Dữ liệu được chiết xuất từ mạng cảm biến theo cách xác định trước và được lưu trữ trong cơ sở dữ liệu nằm trên một máy chủ front-end duy nhất. Xử lý truy vấn trên cơ sở dữ liệu tập trung rất phù hợp cho các truy vấn được xác định trước trên dữ liệu lịch sử [Gane 2005]. Tuy nhiên, các nút gần điểm truy cập trở thành điểm nóng, là điểm trung tâm gây ra lỗi có nguy cơ cạn kiệt nguồn năng lượng rất nhanh. Để giảm tải dữ liệu truyền thông thì phương pháp này không tận dụng được lợi thế của dữ liệu tổng hợp, nhất là khi chỉ cần dữ liệu tổng hợp cho các thao tác xử lý. Bất kỳ truy vấn nào thì việc thiết lập tỷ lệ lấy mẫu ở mức cao tuy nhiên điều này lại là cản trở cho việc truyền thông trong mạng. 15  Hình 2.1 (b) là cơ sở dữ liệu phân tán: Tiết kiệm năng lượng vì tỷ lệ truy vấn ít hơn so với tốc độ dữ liệu được tạo ra. Lưu trữ dữ liệu trong từng nút mạng và cho phép các truy vấn được lấy ra bất cứ nút nào trong mạng. Tuy nhiên, cơ sở dữ liệu phân tán truyền thống không thích hợp cho mạng cảm biến quy mô lớn vì trong cơ sở dữ liệu phân tán truyền thống đã được giả thiết topo mạng được duy trì toàn cục [Madd 2003]. (a) Cơ sở dữ liệu tập trung (b) Cơ sở dữ liệu phân tán Hình 2.1 Hai cách tiếp cận trong cơ sở dữ liệu mạng cảm biến Cần thiết phải có kiến trúc để triển khai cơ sở dữ liệu mạng cảm biến. Kiến trúc này dựa trên hai tính năng:  Tính năng thứ nhất: Thực hiện khai thác cơ sở dữ liệu trong mạng cảm biến khi người dùng hoặc một ứng dụng phát đi một truy vấn và truy vấn này được lưu hành trên mạng hoặc để tất cả các nút sử dụng tràn lan, hoặc là một tập các nút được hạn chế sử dụng trong một vùng địa lý. Để phản hồi lại truy vấn thì mỗi nút sẽ tạo ra bộ dữ liệu phù hợp, bộ dữ liệu này được định tuyến qua mạng và truyền tới đích đã phát truy vấn. Các công việc trong mạng xử lý dữ liệu tại mạng cảm biến là nền tảng để đạt được mục tiêu tiết kiệm năng lượng truyền thông trong mạng cảm biến.  Tính năng thứ hai: Không giống như cơ sở dữ liệu truyền thống, cơ sở dữ liệu mạng cảm biến sẽ cung cấp kết quả gần đúng. Trong mạng cảm biến, tính khả dụng của dữ liệu có thể bị giảm do kết quả của sự mất mát thông tin khi có một thay đổi bất thường trong quá trình truyền thông hoặc bị lỗi nút. Liên quan đến câu trả lời của kết quả gần đúng thì đây một tính năng rất quan 16 trọng trong mạng cảm biến được gọi là kết quả dòng, đặc biệt là sử dụng cho ứng dụng giám sát môi trường liên tục. Tính năng này sẽ cho phép hiển thị kết quả truy vấn một phần trong thời gian thực và cho phép người dùng tự động tinh chỉnh truy vấn trong mạng cảm biến. Tính năng này được gọi là tổng hợp trực tuyến và đã được đề xuất trong các tài liệu cơ sở dữ liệu lớn trên hệ thống hỗ trợ quyết định. 2.2 Mô hình lưu trữ dữ liệu cảm biến Một trong những thách thức chính trong mạng cảm biến không dây là việc lưu trữ và truy vấn dữ liệu cảm biến hữu ích, được gọi là quản lý dữ liệu [Gane 2005]. Dữ liệu cảm biến hữu ích phụ thuộc vào từng ứng dụng và có ý nghĩa khác nhau trong các tình huống ứng dụng khác nhau. Ví dụ trong một ứng dụng theo dõi mục tiêu, người dùng quan tâm đến việc phát hiện và theo dõi các phương tiện di chuyển. Dữ liệu cảm biến hữu ích bao gồm phát hiện mục tiêu (nhãn thời gian và địa điểm) và theo dõi. Ví dụ trong một ứng dụng giám sát kết cấu, các nhà khoa học quan tâm đến phân tích dữ liệu thu được từ cảm biến liên quan tới không gian thời gian như độ rung đo được tại các điểm khác nhau của một tòa nhà. Để thực hiện nhiệm vụ này, dữ liệu về độ rung tương ứng với khoảng thời gian yêu cầu được thu thập và xử lý đối với phạm vi tòa nhà. Có ba câu hỏi được đặt ra liên quan tới việc quản lý dữ liệu:  Dữ liệu được lưu trữ ở đâu trong mạng? Nó được lưu trữ tại nút cảm biến cục bộ (lưu trữ cục bộ) hay phân tán trong hệ thống (lưu trữ phân tán) hoặc ở ngoài của mạng tại các trạm cơ sở (lưu trữ tập trung)?  Làm thế nào để các truy vấn chuyển đến được lưu trữ? Có thể sử dụng các thuộc tính tìm kiếm để tăng hiệu quả như thế nào?  Làm thế nào để giải quyết vấn đề về giới hạn lưu trữ tại các nút cảm biến? 17 Để trả lời những câu hỏi này đã có bốn cách tiếp cận: 2.2.1 Lữu trữ tập trung và tìm kiếm Phương pháp thông thường để lưu trữ dữ liệu theo chuỗi dữ liệu thời gian là phải có các nút cảm biến nguồn cung cấp tất cả dữ liệu đến một kho lưu trữ trung tâm bên ngoài tới môi trường cảm biến [Lee 2008]. Với một mạng có n nút, chi phí dựa trên thứ tự đường kính của mạng cho mỗi phần dữ liệu được gửi bằng O(√𝑛). Do dữ liệu đã được lưu trữ bên ngoài mạng nên truy vấn trên dữ liệu này không bị mất thêm bất kỳ chi phí nào khác. Lưu trữ tập trung có thể phù hợp cho lưu trữ với tốc độ thấp, truy xuất dữ liệu thấp và mạng cảm biến quy mô nhỏ. Ví dụ như xem xét một hệ thống theo dõi mục tiêu phát hiện mục tiêu không thường xuyên và tạo ra bộ dữ liệu sự kiện với các loại sự kiện đánh nhãn thời gian và địa điểm dò. Dữ liệu là rất nhỏ và tỷ lệ sự kiện là thấp, do đó lưu trữ tập trung có thể hợp lý cho một mạng hàng trăm nút truyền dữ liệu qua 2 - 3 chặng và một trạm phát. Lưu trữ tập trung không phải lúc nào cũng khả thi trong mạng cảm biến do chi phí tổng hợp và chi phí thắt nút cổ chai, truyền tất cả dữ liệu hướng tới một cổng mạng. 2.2.2 Lưu trữ cục bộ và tìm kiếm địa lý Trong hình 2.1 ở phía dưới bên phải của quang phổ là một chương trình lưu trữ đầy đủ của tất cả dữ liệu cảm biến hữu ích tại cục bộ mỗi nút, truy vấn được chuyển đến nơi mà dữ liệu được lưu trữ. Khi dữ liệu được lưu trữ cục bộ tại mỗi nút cảm biến thì sẽ không có bất kỳ chi phí nào liên quan đến truyền thông. Tuy nhiên, do dữ liệu được lưu trữ bất cứ nút nào trong mạng, nên nếu trong mạng có xử lý tìm kiếm và truy vấn thì sẽ phải chịu chi phí cao về năng lượng, một truy vấn mà không hạn chế rõ ràng không gian tìm kiếm vật lý thì chi phí tìm kiếm lên tới O(n), với n là số nút trong mạng. Phản hồi truy vấn sẽ có chi phí là O( √n) vì đường kính mạng là O( √n). Nếu chỉ phát sinh một vài truy vấn được phát ra trong suốt vòng đời của một mạng, thì việc phản hồi cho các truy vấn này có thể bao gồm một ít chi phí truyền thông [Gola 2006]. Một số lượng lớn các truy vấn liên quan đến tất cả các nút trong mạng thì chi phí truyền thông là không ít, có thể tiêu hao cả năng lượng dự trữ của mạng. Cơ chế này có ba nhược điểm:  Thứ nhất: Các truy vấn không giới hạn về phạm vi địa lý, chi phí tìm kiếm là O(√𝑛) do vậy có thể bị hạn chế cho các mạng lớn với các truy vấn thường xuyên. 18  Thứ hai: Việc xử lý vấn truy dữ liệu không gian thời gian điều quan trọng nhất là cần phải thực hiện phân tán dữ liệu, mỗi lần xử lý một truy vấn được phát ra có thể rất tốn kém.  Thứ ba: Cần phải tăng cường những kỹ thuật giải quyết về giới hạn lưu trữ tại mỗi nút cảm biến. 2.2.3 Lưu trữ cục bộ với chỉ mục phân tán Có rất nhiều các kỹ thuật khác nhau trong cơ chế sử dụng tổng hợp dữ liệu dựa trên ý tưởng của hàm băm địa lý và cấu trúc bản sao. Một chương trình lập chỉ mục như lưu trữ dữ liệu trung tâm cung cấp một hàm băm để lập bản đồ từ tên sự kiện dựa vào vị trí. Lưu trữ dữ liệu trung tâm xây dựng một cấu trúc lưu trữ phân tán các nhóm sự kiện lại với nhau về mặt không gian theo tên [Suen 2008]. Tên được coi là khóa tùy ý trong hàm băm và là đơn vị cơ bản của phân loại. Một nút có thể phát hiện sự kiện lưu trữ dựa vào phản chiếu gần nhất với vị trí của nút đó. Tìm kiếm sử dụng cấu trúc bản sao sẽ bắt đầu với nút gốc, xuống đến bốn nút con, xuống bốn mỗi nút con trong bốn nút con,… lưu trữ dữ liệu này sử dụng cấu trúc bản sao để đăng ký sự tồn tại của các sự kiện tại các nút tụ điểm bản sao. Chi phí thông tin liên lạc để lưu trữ một dữ kiện là O(√𝑛) và chi phí để gửi một truy vấn và lấy dữ liệu là O(√𝑛). Trong cơ sở dữ liệu truyền thống, một bảng được lập chỉ mục để tăng tốc độ truy vấn phổ biến. Tương tự như vậy, lưu trữ dữ liệu trung tâm chỉ mục là dữ liệu được tối ưu hóa cho truyền thông. Các tính năng của chỉ mục phân tán và các phạm vi truy vấn đa chiều trong mạng cảm biến đã mở rộng cách tiếp cận lưu trữ dữ liệu trung tâm nhằm cung cấp một hệ thống phân cấp phân tán về không gian của các chỉ mục dữ liệu. 2.2.4 Phương pháp lưu trữ cục bộ với đa độ phân giải DIMENSIONS [Gane 2003b] là một hệ thống xây dựng tổng hợp đa độ phân giải, sử dụng kỹ thuật nén wavelet để xây dựng tổng hợp đa độ phân giải từ không gian khác nhau có thể được truy vấn sử dụng hiệu quả kỹ thuật drill-down. DIMENSIONS hướng đến mạng cảm biến với quy mô lớn và lưu trữ dữ liệu hạn chế để cung cấp một cái nhìn thống nhất về xử lý dữ liệu trong mạng cảm biến, kết hợp lưu trữ lâu dài, truy cập dữ liệu đa độ phân giải và khai thác mô hình không gian thời gian. Hình 2.2 cho thấy khái niệm về đa độ phân giải về lưu trữ dữ liệu trong DIMENSIONS. 19 Hình 2.2 Tổng hợp đa độ phân giải Mục tiêu cơ bản của thiết kế DIMENSIONS là khả năng trích xuất dữ liệu cảm biến một cách đa độ phân giải từ mạng cảm biến. Cơ chế làm việc này cung cấp nhiều lợi ích, cho phép người dùng nhìn vào dữ liệu có độ phân giải thấp từ một khu vực lớn hơn với chi phí thấp. Dữ liệu cảm biến có độ phân giải thấp được nén từ số lượng lớn từ các nút, có thể đủ để truy vấn và được ước tính thống kê trên một tổng thể dữ liệu lớn. 2.3 Các cách tiếp cận xử lý truy vấn cho ứng dụng với mạng cảm biến Kỹ thuật xử lý truy vấn trong mạng cảm biến, thường tập trung vào thu thập câu trả lời của các truy vấn bằng cách xử lý các truy vấn trong mạng một cách phân tán [Gane 2005]. Phương pháp này khác với phương pháp tiếp cận xử lý tập trung, thu thập dữ liệu riêng lẻ ở một máy chủ mạnh và xử lý truy vấn bất kỳ ở trung tâm. Cách tiếp cận này khá tốn kém trong một số ứng dụng khi mà dữ liệu thô riêng lẻ không quan trọng. Các truy vấn ở đây được giả thiết là đơn giản giống như truy vấn trong cơ sở dữ liệu truyền thống. Do đó, chúng khác nhau từ việc thực hiện tổng hợp các truy vấn trong kỹ thuật xử lý dữ liệu trung tâm. Truy vấn tổng hợp trong mạng tập hợp sử dụng hai giai đoạn: giai đoạn phân tán và giai đoạn thu thập. Chỉ tập hợp phân tích được các hàm như giá trị nhỏ nhất, giá trị lớn nhất, tổng, trung bình và đếm, được đánh giá bằng cách sử dụng như một phương pháp tiếp cận phân tán [Madd 2002b]. Trong giai đoạn phân tán, các truy vấn được phân tán đến tất cả các nút trong mạng. Một cây bắt nguồn tại trạm cơ sở được sử dụng để định tuyến dữ liệu, còn gọi là cây định tuyến. Dữ liệu không liên quan sẽ bị loại bỏ và chỉ có dữ liệu liên quan được