Tài liệu Nghiên cứu kỹ thuật cộng tác kho dữ liệu lưu giữa các clients trong hệ thống thông tin di động dựa trên kiến trúc p2p

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN LA PHƯƠNG THANH – LÊ THỊ THANH THÚY NGHIÊN CỨU KỸ THUẬT CỘNG TÁC KHO DỮ LIỆU LƯU GIỮA CÁC CLIENTS TRONG HỆ THỐNG THÔNG TIN DI ĐỘNG DỰA TRÊN KIẾN TRÚC P2P KHÓA LUẬN TỐT NGHIỆP CỬ NHÂN CNTT TP. HCM, 2010 TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN LA PHƯƠNG THANH - 0612390 LÊ THỊ THANH THÚY - 0612440 NGHIÊN CỨU KỸ THUẬT CỘNG TÁC KHO DỮ LIỆU LƯU GIỮA CÁC CLIENTS TRONG HỆ THỐNG THÔNG TIN DI ĐỘNG DỰA TRÊN KIẾN TRÚC P2P KHÓA LUẬN TỐT NGHIỆP CỬ NHÂN CNTT GIÁO VIÊN HƯỚNG DẪN Th. S NGUYỄN TRẦN MINH THƯ KHÓA 2006 - 2010 LỜI CẢM ƠN Sau sáu tháng tìm hiểu và thực hiện, khóa luận “Nghiên cứu kỹ thuật cộng tác kho dữ liệu lưu giữa các clients trong Hệ thống thông tin di động dựa trên kiến trúc P2P” trên cơ bản đã hoàn thành. Để đạt được kết quả như hôm nay chúng em đã cố gắng rất nhiều và cũng được sự giúp đỡ, sự ủng hộ của gia đình, các thầy cô và bạn bè. Trước hết, chúng em xin chân thành cảm ơn Khoa Công Nghệ Thông Tin, trường Đại Học Khoa Học Tự Nhiên TpHCM đã tạo điều kiện thuận lợi cho chúng em thực hiện khóa luận tốt nghiệp này. Chúng em xin bày tỏ lòng biết ơn sâu sắc đến cô Nguyễn Trần Minh Thư đã tận tình hướng dẫn, chỉ bảo chúng em trong suốt thời gian thực hiện khóa luận. Chúng con xin chân thành cảm ơn Ông Bà, Cha Mẹ đã chăm sóc, nuôi dạy chúng con thành người. Xin chân thành cám ơn các thầy cô, các anh chị và các bạn đã ủng hộ, giúp đỡ và động viên chúng em trong thời gian học tập và nghiên cứu. Khóa luận đã hoàn thành với một số kết quả nhất định, tuy nhiên vẫn không tránh khỏi sai sót. Kính mong sự đóng góp ý kiến của các thầy cô và các bạn. Sinh viên thực hiện La Phương Thanh – Lê Thị Thanh Thúy 07-2010 i Khoa Công Nghệ Thông Tin Bộ môn Hệ Thống Thông Tin ĐỀ CƯƠNG CHI TIẾT Tên đề tài: Nghiên cứu kỹ thuật cộng tác kho dữ liệu lưu giữa các clients trong Hệ thống thông tin di động dựa trên kiến trúc P2P. Giáo viên hướng dẫn: Ths. Nguyễn Trần Minh Thư Sinh viên thực hiện:  La Phương Thanh MSSV: 0612390 Email: [email protected] Điện thoại: 0902054500  Lê Thị Thanh Thúy MSSV: 0612440 Email: [email protected] Điện thoại: 0908195336 Loại đề tài: Nghiên cứu và thử nghiệm Mục tiêu đề tài: Ngày nay công nghệ thông tin (CNTT) nói chung và hệ thống thông tin di động nói riêng đã phát triển một cách mạnh mẽ cùng với sự phát triển của kỹ thuật mạng không dây kết hợp với các loại thiết bị di động ngày càng hiện đại đã mang lại nhiều tiện ích cho người dùng trong việc trao đổi thông tin và dữ liệu. Hệ thống thông tin di động được phát triển đầu tiên với kiến trúc mạng client/server. Mô hình mạng client/server có rất nhiều điểm ưu việt, nổi bật là mọi xử lý sẽ nằm trên server, do đó tránh cho các client những tính toán nặng nề. Tuy nhiên với sự phát triển không ngừng của hệ thống thông tin di động thì kiến trúc mạng client/server không còn phù hợp và gây ra nhược điểm khi số lượng máy khách tăng lên. Lý do ii chính là khi số lượng máy khách tăng lên thì nhu cầu truy xuất dữ liệu và băng thông tăng, dẫn đến server giảm khả năng cung cấp dịch vụ cho các clients. Đặc biệt trong môi trường mạng không dây kết nối yếu hoặc thường xuyên mất kết nối thì kiến trúc client/server này hoàn toàn không còn phù hợp nữa. Để khắc phục các nhược điểm của kiến trúc client/server, các nhà khoa học đã nghiên cứu đưa ra một mô hình kiến trúc mới phù hợp trong môi trường hệ thống thông tin di động, đó là mô hình cộng tác chia sẽ dữ liệu và thông tin giữa các clients với nhau để hạn chế việc truy xuất đến server. Đối với mô hình này thì client là các thiết bị di động có khả năng xử lý, lưu trữ. Tuy nhiên các thiết bị di động hạn chế về năng lượng, khả năng tính toán và không gian lưu trữ thấp, vì vậy người ta muốn các thiết bị di động chia sẻ cộng tác kho lưu trữ (cache). Việc này giúp giảm thời gian chờ và tăng khả năng lấy được dữ liệu trong một môi trường ít kết nối. Nhiều công trình nghiên cứu đã đưa ra các chiến lược và kỹ thuật lưu trữ lại dữ liệu (caching). Các kỹ thuật xử lý, lưu trữ hiệu quả giúp tăng hiệu suất của mô hình cộng tác chia sẻ dữ liệu. Từ đó giảm chi phí truyền thông giữa các client và server cũng như rút ngắn thời gian hồi đáp truy vấn dữ liệu. Do đó, mục tiêu của chúng tôi đặt ra trong đề tài này là nghiên cứu tìm hiểu các mô hình cộng tác chia sẻ dữ liệu trong hệ thống thông tin di động. Sau đó, xây dựng và hiện thực hóa một kiến trúc hệ thống, cài đặt thử nghiệm để kiểm tra tính hiệu quả của kiến trúc. Nội dung đề tài:  Tìm hiểu các mô hình cộng tác chia sẻ dữ liệu trong các hệ thống thông tin di động. Đối với mỗi mô hình tìm hiểu cần nắm được thông tin về ý tưởng, giải pháp thực hiện và đánh giá được các ưu khuyết điểm của từng mô hình.  Từ hiện trạng khảo sát sinh viên xây dựng mô hình cộng tác chia sẻ dữ liệu trong hệ thống thông tin di động. Trong mô hình đề xuất cần quan tâm đến vấn đề điều phối truy vấn cho các thiết bị lân cận đồng thời xử lý hỗ trợ truy vấn cho nhiều hạng mục dữ liệu.  Đề xuất giải pháp lưu trữ, chia sẻ, truy vấn dữ liệu cho mô hình đề nghị, trong iii giải pháp thực hiện sinh viên có thể kế thừa hoặc kế thừa có cải tiến hoặc đề xuất giải pháp mới để thực hiện cho mô hình đã đề xuất.  Xây dựng ứng dụng thử nghiệm cho mô hình đề xuất.  So sánh, đánh giá với các giải pháp của các mô hình đã đề xuất theo từng tiêu chí đặt ra trong kiến trúc hệ thống thông tin di động (nếu có thể).  Đánh giá nhận xét cho mô hình sau khi đã chạy thực nghiệm với các bộ dữ liệu để đánh giá được hiệu quả của việc chia sẻ dữ liệu trong mô hình đã đề nghị. Yêu cầu đạt được:  Về mặt lý thuyết: o Nghiên cứu mô hình cộng tác chia sẻ dữ liệu trong hệ thống thông tin di động o Đề xuất mô hình truy vấn đa dữ liệu cho hệ thống thông tin di động có áp dụng kiến trúc P2P và xây dựng giải pháp, thuật toán để hiện thực hóa mô hình  Về mặt ứng dụng: o Cài đặt và đánh giá hiệu quả giải pháp đã đề nghị. o Ứng dụng minh họa Kế hoạch thực hiện:  Giai đoạn 1:(Từ 20/12/2009  15/03/2010) Thu thập, nghiên cứu, tổng hợp tài liệu tham khảo  Khảo sát mô hình cộng tác chia sẻ dữ liệu áp dụng trên môi trường di động.  Đánh giá các mô hình  Đề xuất mô hình và lựa chọn giải pháp lưu trữ, chia sẻ, truy vấn dữ liệu trong mô hình cộng tác dữ liệu trên hệ thống di động  Giai đoạn 2:(Từ 16/03/2010  15/05/2010) Cài đặt thử nghiệm  Triển khai cài đặt thử nghiệm mô hình và giải pháp lưu trữ, chia sẻ, truy vấn dữ liệu  Xây dựng ứng dụng minh họa  Giai đoạn 3:(Từ 16/05/2010  30/06/2010) Đánh giá, kiểm nghiệm và viết báo iv cáo  Kiểm tra tính đúng đắn của chương trình.  Hoàn thiện các chức năng còn lỗi.  Mở rộng chức năng nếu có. Hoàn thiện báo cáo luận văn. Xác nhận của GVHD Ngày tháng năm 2010 SV thực hiện Th.S Nguyễn Trần Minh Thư La Phương Thanh – Lê Thị Thanh Thúy v MỤC LỤC LỜI CẢM ƠN ...................................................................................................... i ĐỀ CƯƠNG CHI TIẾT ...................................................................................... ii MỤC LỤC ...........................................................................................................vi DANH MỤC HÌNH VẼ .................................................................................... xii DANH MỤC CÁC BẢNG ................................................................................xiv TÓM TẮT ........................................................................................................xvii Chương 1 - MỞ ĐẦU ...........................................................................................1 1.1 Giới thiệu đề tài ............................................................................................1 1.2 Mục tiêu đề tài ..............................................................................................2 1.3 Hướng tiếp cận và giải quyết bài toán ...........................................................2 1.4 Nội dung đề tài .............................................................................................3 Chương 2 - TỔNG QUAN VỀ MÔ HÌNH CỘNG TÁC CHIA SẺ DỮ LIỆU TRONG MÔI TRƯỜNG DI ĐỘNG ........................................................................5 2.1 Giới thiệu mô hình cộng tác chia sẻ dữ liệu ..................................................5 2.1.1 Định nghĩa mô hình cộng tác chia sẻ dữ liệu ..........................................5 2.1.2 Ưu điểm của mô hình cộng tác chia sẻ dữ liệu .......................................6 2.2 Các chiến lược quản lý và thay thế kho lưu trữ trong mô hình cộng tác ........6 2.2.1 Thuật toán thay thế (Replacement Algorithm) ........................................6 2.2.1.1 Thuật toán dựa trên vùng nhớ tạm (Temporal Locality Based Algorithm) ........................................................................................................6 2.2.1.2 Thuật toán dựa trên lợi ích (hoặc dựa trên chi phí):..........................7 2.2.2 Chiến lược nhất quán kho lưu trữ ...........................................................7 2.2.3 Chiến lược điều phối truy vấn và tổng hợp dữ liệu .................................7 2.3 Sơ lược các công trình nghiên cứu về cộng tác chia sẻ dữ liệu ......................7 2.3.1 Dẫn nhập................................................................................................7 2.3.2 Kiến trúc MIX........................................................................................8 2.3.2.1 Phương thức hoạt động .................................................................. 10 2.3.2.2 Kiến trúc và nguyên lý hoạt động .................................................. 10 vi 2.3.3 Kỹ thuật lưu trữ theo nhóm và truy vấn tổng hợp dữ liệu phân tán ....... 14 2.3.3.1 Kế hoạch truy vấn dữ liệu tại một MU dựa trên chiến lược lưu trữ nhóm .............................................................................................................. 14 2.3.3.2 Xây dựng kế hoạch truy vấn dữ liệu tại nhiều MU dựa trên chiến lược lưu trữ nhóm ........................................................................................... 16 2.3.4 Chiến lược thay thế cache với giá trị LUV ........................................... 20 2.3.5 CCCM - Kiến trúc cộng tác chia sẻ kho lưu trữ .................................... 22 2.3.5.1 Lưu trữ .......................................................................................... 23 2.3.5.2 Khám phá ...................................................................................... 23 2.3.5.3 Nhất quán ...................................................................................... 24 2.3.5.4 Thay thế ........................................................................................ 25 2.4 So sánh đánh giá các giải pháp ................................................................... 27 2.4.1 Bảng so sánh đánh giá các giải pháp .................................................... 27 2.4.2 Đánh giá ưu điểm, khuyết điểm của các giải pháp ................................ 27 2.5 Kết luận ...................................................................................................... 29 Chương 3 - ĐỀ XUẤT KIẾN TRÚC MẠNG P2P TRONG MÔI TRƯỜNG DI ĐỘNG ...................................................................................................................... 30 3.1 Dẫn nhập .................................................................................................... 30 3.2 Kiến trúc hệ thống thông tin di động áp dụng mạng P2P............................. 32 3.2.1 Giới thiệu ............................................................................................. 32 3.2.2 Phương thức hoạt động của hệ thống.................................................... 32 3.3 Kiến trúc và nguyên lý hoạt động ............................................................... 34 3.3.1 Lớp Cooperative Caching Process ........................................................ 35 3.3.1.1 Lớp Local Cache Process............................................................... 35 3.3.1.2 Lớp Zone Process .......................................................................... 36 3.3.1.3 Lớp Routing Process...................................................................... 36 3.3.2 Lớp Query Process ............................................................................... 37 3.3.2.1 Module “Local Query” .................................................................. 37 3.3.2.2 Module “Zone Query” ................................................................... 37 3.3.2.3 Module “Route Query” .................................................................. 37 3.4 Thuật toán xử lý tại MU ............................................................................. 38 vii 3.4.1 Luồng xử lý tại lớp Cooperative Caching Process ................................ 39 3.4.1.1 Luồng xử lý tại lớp Local Cache Process ....................................... 39 3.4.1.1.1 Thuật toán phân loại dữ liệu .................................................... 39 3.4.1.1.2 Thay thế dữ liệu ...................................................................... 40 3.4.1.1.3 Thay đổi phù hợp với truy vấn đa hạng mục ............................ 40 3.4.1.2 Luồng xử lý tại lớp Zone Process .................................................. 42 3.4.1.2.1 Thuật toán “Lưu trữ thông tin trong bảng RRT” ...................... 42 3.4.1.2.2 Thuật toán “Định tuyến trong vùng” ....................................... 44 3.4.1.3 Luồng xử lý tại lớp Routing Process .............................................. 44 3.4.2 Luồng xử lý tại lớp Query Process ....................................................... 45 3.4.2.1 Thuật toán xử lý module Local Query ........................................... 45 3.4.2.2 Thuật toán xử lý module Zone Query ............................................ 47 3.4.2.2.1 Thuật toán xử lý tại MU dữ liệu khi nhận được JoinResquest từ MU nguồn ................................................................................................... 47 3.4.2.2.2 Thuật toán xử lý tại MU nguồn khi nhận được RJoinRequest từ MU dữ liệu ................................................................................................. 49 3.4.2.2.3 Thuật toán xử lý tại MU dữ liệu khi nhận được DataRequest từ MU nguồn ................................................................................................... 51 3.4.2.2.4 Thuật toán xử lý tổng hợp dữ liệu tại MU dữ liệu ................... 52 3.4.2.3 Thuật toán xử lý module Route Query ........................................... 53 3.5 Xây dựng cở sở dữ liệu............................................................................... 55 3.5.1 Cấu trúc lưu trữ .................................................................................... 55 3.5.2 Cấu trúc xử lý ...................................................................................... 58 3.6 Kết luận ...................................................................................................... 59 Chương 4 - XÂY DỰNG CHƯƠNG TRÌNH MÔ PHỎNG ............................. 61 4.1 Giới thiệu ................................................................................................... 61 4.2 Network Simulation 2 – NS2 ...................................................................... 61 4.2.1 Giới thiệu ............................................................................................. 61 4.2.2 Kiến trúc của NS2 ................................................................................ 61 4.3 Cấu trúc chương trình mô phỏng ................................................................ 62 4.4 Chương trình tạo kịch bản mô phỏng – E-MIX Demo ................................ 63 viii 4.4.1 Giới thiệu ............................................................................................. 63 4.4.2 Giao diện chính của E-MIX Demo ....................................................... 64 4.4.2.1 Màn hình “Main”........................................................................... 65 4.4.2.2 Màn hình “Configuration node”..................................................... 66 4.4.2.3 Màn hình “Model”......................................................................... 67 4.4.2.4 Màn hình “Animation” .................................................................. 68 4.4.2.5 Màn hình “Result” ......................................................................... 69 4.5 Thực thi kịch bản mô phỏng ....................................................................... 70 4.6 Kiến trúc E-MIX ........................................................................................ 70 4.6.1 Giao thức “EMIXAgent” ..................................................................... 70 4.6.2 Kỹ thuật lưu trữ trong kiến trúc E-MIX ................................................ 71 4.6.2.1 Lớp RRT ....................................................................................... 71 4.6.2.2 Lớp MyCache ................................................................................ 73 4.6.2.3 Lớp numNeighNeigh ..................................................................... 75 4.6.2.4 Lớp MyList ................................................................................... 75 4.6.2.5 Lớp EMixAgent ............................................................................ 77 4.6.3 Kỹ thuật xử lý trong kiến trúc E-MIX .................................................. 83 4.6.3.1 Lớp RRT ....................................................................................... 83 4.6.3.2 Lớp MyCache ................................................................................ 84 4.6.3.3 Lớp MyList ................................................................................... 86 4.6.3.4 Lớp numNeighNeigh ..................................................................... 87 4.6.4 Kỹ thuật truyền và nhận gói tin trong giao thức .................................... 87 4.6.5 Danh sách các gói tin sử dụng trong giao thức E-MIX ......................... 89 4.6.6 Kỹ thuật tạo gói tin .............................................................................. 89 4.6.7 Gửi gói tin............................................................................................ 91 4.6.8 Kỹ thuật xếp lịch thời gian ................................................................... 91 4.6.9 Sơ đồ luồng xử lý thông tin các module của giao thức EMixAgent ...... 93 4.6.10 Biên dịch NS-2................................................................................... 94 4.7 Kết luận ...................................................................................................... 94 Chương 5 - KẾT QUẢ MÔ PHỎNG ................................................................ 95 5.1 Giới thiệu ................................................................................................... 95 ix 5.2 Mô phỏng kiểm nghiệm kiến trúc ............................................................... 95 5.2.1 Các tiêu chí mô phỏng thử nghiệm ....................................................... 95 5.2.1.1 Tiêu chí 1: Tỷ lệ đưa yêu cầu lên kênh uplink ................................ 95 5.2.1.2 Tiêu chí 2: Thời gian đáp ứng của một yêu cầu dữ liệu .................. 95 5.2.1.3 Tiêu chí 3: Số lượng thông điệp của một yêu cầu dữ liệu ............... 96 5.2.1.4 Tiêu chí 4: Số lượng thông điệp của một yêu cầu dữ liệu ............... 96 5.2.1.5 Tiêu chí 5: Số lượng thông điệp trung bình của một yêu cầu dữ liệu ....................................................................................................................... 96 5.2.2 Thử nghiệm kiểm tra tính hiệu quả của kiến trúc E-MIX...................... 96 5.2.3 Các trường hợp thử nghiệm kiến trúc E-MIX ....................................... 97 5.3 Cấu hình mô phỏng chung .......................................................................... 98 5.3.1 Cấu hình tham số thử nghiệm ............................................................... 98 5.3.2 Bộ dữ liệu thử nghiệm.......................................................................... 99 5.3.3 Kịch bản và kết quả thử nghiệm E-MIX-3............................................ 99 5.3.3.1 Mô phỏng 10 MUs......................................................................... 99 5.3.3.1.1 Tiêu chí số lượng thông điệp của một yêu cầu dữ liệu ............. 99 5.3.3.1.2 Tiêu chí thời gian đáp ứng của một yêu cầu dữ liệu............... 101 5.3.3.2 Mô phỏng 20 MUs....................................................................... 103 5.3.3.2.1 Tiêu chí số lượng thông điệp của một yêu cầu dữ liệu ........... 103 5.3.3.2.2 Tiêu chí thời gian đáp ứng của một yêu cầu dữ liệu............... 105 5.3.3.3 Mô phỏng 30 MUs....................................................................... 107 5.3.3.3.1 Chi tiết quá trình chọn lựa DN để gửi dữ liệu tại QN trong trường hợp thử nghiệm 3 ........................................................................... 107 5.3.3.3.2 Tiêu chí số lượng thông điệp của một yêu cầu dữ liệu ........... 108 5.3.3.3.3 Tiêu chí thời gian đáp ứng của một yêu cầu dữ liệu............... 109 5.3.3.4 Mô phỏng 40 MUs....................................................................... 111 5.3.3.4.1 Tiêu chí số lượng thông điệp của một yêu cầu dữ liệu ........... 111 5.3.3.4.2 Tiêu chí thời gian đáp ứng của một yêu cầu dữ liệu............... 112 5.3.3.4.3 Tiêu chí tỉ lệ đưa yêu cầu lên kênh uplink ............................. 114 5.3.3.5 Mô phỏng 50 MUs....................................................................... 115 5.3.3.5.1 Tiêu chí số lượng thông điệp của một yêu cầu dữ liệu ........... 115 x 5.3.3.5.2 Tiêu chí thời gian đáp ứng của một yêu cầu dữ liệu............... 117 5.3.3.6 Mô phỏng 60 MUs....................................................................... 118 5.3.3.6.1 Tiêu chí số lượng thông điệp của một yêu cầu dữ liệu ........... 118 5.3.3.6.2 Tiêu chí thời gian đáp ứng của một yêu cầu dữ liệu............... 120 5.3.4 Đánh giá kết quả thử nghiệm E-MIX ................................................. 121 5.4 Kết luận .................................................................................................... 123 Chương 6 - KẾT LUẬN ................................................................................... 125 6.1 Kết luận .................................................................................................... 125 6.2 Hướng phát triển luận văn ........................................................................ 125 TÀI LIỆU THAM KHẢO ............................................................................... 127 xi DANH MỤC HÌNH VẼ Hình 2-1 Mô hình kiến trúc hệ thống ...........................................................................9 Hình 2-2 Nguyên lý hoạt động của kiến trúc ............................................................. 10 Hình 2-3 Kiến trúc tại MU ........................................................................................ 11 Hình 2-4 Mô hình kiến trúc MIX ............................................................................... 11 Hình 2-5 Xử lý Routing Process ................................................................................ 13 Hình 2-6 Xử lý Route Discovery Phase ..................................................................... 13 Hình 2-7 Ví dụ truy vấn tại nhiều MU trong Group-Caching based Query Processing ........................................................................................................................... 19 Hình 2-8 Mô hình kiến trúc hệ thống ......................................................................... 22 Hình 3-1 Mô hình kiến trúc hệ thống mạng ............................................................... 31 Hình 3-2 Nguyên lý hoạt động kiến trúc đề xuất........................................................ 33 Hình 3-3 Kiến trúc tại mỗi MU ................................................................................. 34 Hình 3-4 Mô hình kiến trúc đề xuất ........................................................................... 35 Hình 3-5 Luồng xử lý tại lớp Middleware ................................................................. 38 Hình 3-6 Module "Cache Management" .................................................................... 39 Hình 3-7 Ví dụ bảng RRT ......................................................................................... 43 Hình 3-8 Xử lý tại MU nguồn khi gửi thông điệp đến MUs lân cận ........................... 46 Hình 3-9 Minh họa quá trình xử lý tại MU nguồn khi nhận được RJoinRequest từ MU dữ liệu ................................................................................................................ 50 Hình 3-10 Lưu đồ thuật toán xử lý tại MU dữ liệu khi nhận được DataRequest từ MU nguồn ................................................................................................................. 51 Hình 3-11 Lưu đồ thuật toán xử lý tổng hợp dữ liệu tại MU dữ liệu ......................... 52 Hình 3-12 Thuật toán tìm kiếm RD trong các MUs mạng .......................................... 54 Hình 4-1 NS-2 theo quan điểm người dùng ............................................................... 62 Hình 4-2 Cấu trúc chương trình mô phỏng ................................................................ 63 Hình 4-3 Sơ đồ liên kết các màn hình ........................................................................ 64 Hình 4-4 Màn hình Main ........................................................................................... 65 Hình 4-5 Màn hình "Configuration node" .................................................................. 66 xii Hình 4-6 Màn hình Model ......................................................................................... 67 Hình 4-7 Màn hình Animation .................................................................................. 68 Hình 4-8 Màn hình "Result" ...................................................................................... 69 Hình 4-9 Ví dụ NS-2 thực thi một kịch bản ............................................................... 70 Hình 4-10 Sơ đồ liên kết các lớp trong giao thức EMixAgent.................................... 71 Hình 4-11 Sơ đồ luồng xử lý các module của giao thức EMixAgent.......................... 93 Hình 4-12 Quá trình biên dịch NS-2 .......................................................................... 94 Hình 5-1 Kết quả số lượng thông điệp với số lượng 10 MUs ................................... 101 Hình 5-2 Kết quả thời gian đáp ứng so với số lượng 10 MUs .................................. 103 Hình 5-3 Kết quả số lượng thông điệp với số lượng 20 MUs ................................... 105 Hình 5-4 Kết quả thời gian đáp ứng của một RD với số lượng 20 MUs ................... 106 Hình 5-5 Kết quả số lượng thông điệp với số lượng 30 MUs ................................... 109 Hình 5-6 Kết quả thời gian đáp ứng của một RD với số lượng 30 MUs ................... 110 Hình 5-7 Kết quả số lượng thông điệp với số lượng 40 MUs ................................... 112 Hình 5-8 Kết quả thời gian đáp ứng của một RD với số lượng 40 MUs ................... 114 Hình 5-9 Kết quả tiêu chí đưa yêu cầu lên kênh uplink ............................................ 114 Hình 5-10 Kết quả số lượng thông điệp với số lượng 50 MUs ................................. 116 Hình 5-11 Kết quả thời gian đáp ứng của một RD với số lượng 50 MUs ................. 118 Hình 5-12 Kết quả số lượng thông điệp với số lượng 60 MUs ................................. 120 Hình 5-13 Kết quả thời gian đáp ứng của một RD với số lượng 60 MUs ................. 121 Hình 5-14 Thời gian đáp ứng trung bình của một yêu cầu dữ liệu............................ 122 Hình 5-15 Số lượng thông điệp trung bình của một yêu cầu dữ liệu......................... 123 xiii DANH MỤC CÁC BẢNG Bảng 2-1 Thuật toán truy vấn tại một MU trong Group-Caching based Query Processing .......................................................................................................... 15 Bảng 2-2 Thuật toán truy vấn tại nhiều MU trong Group-Caching based Query Processing .......................................................................................................... 19 Bảng 3-1 Mả giã thuật toán xử lý thay thế dữ liệu ..................................................... 42 Bảng 3-2 Mã giả "Xử lý lưu trữ thông tin trong RRT" ............................................... 44 Bảng 3-3 Mã giả thuật toán "Định tuyến trong vùng" ................................................ 44 Bảng 3-4 Thuật toán tại module "Local Query" ......................................................... 46 Bảng 3-5 Thuật toán xử lý tại MU dữ liệu khi nhận được JoinResquest từ MU nguồn ........................................................................................................................... 49 Bảng 3-6 Thuật toán xử lý tại MU nguồn khi nhận được RJoinRequest từ MU dữ liệu ........................................................................................................................... 51 Bảng 3-7 Thuật toán xử lý tổng hợp dữ liệu tại MU dữ liệu...................................... 53 Bảng 3-8 Mã giả xử lý thuật toán tìm kiếm RD trong các MUs mạng ........................ 55 Bảng 4-1 Chi tiết các giao diện chính của E-MIX Demo ........................................... 64 Bảng 4-2 Chức năng màn hình "Main" ...................................................................... 66 Bảng 4-3 Chi tiết màn hình "Configuration node" ..................................................... 67 Bảng 4-4 Chi tiết màn hình "Model" ......................................................................... 68 Bảng 4-5 Chi tiết màn hình "Animation" ................................................................... 69 Bảng 4-6 Chi tiết màn hình "Result".......................................................................... 69 Bảng 4-7 Chức năng các lớp trong giao thức EMixAgent .......................................... 71 Bảng 4-8 Cấu trúc dữ liệu của lớp RRT..................................................................... 72 Bảng 4-9 Các hàm chức năng của lớp RRT ............................................................... 73 Bảng 4-10 Cấu trúc dữ liệu của lớp MyCache ........................................................... 74 Bảng 4-11 Các hàm chức năng của lớp MyCache ...................................................... 75 Bảng 4-12 Cấu trúc dữ liệu của lớp numNeighNeigh ................................................ 75 Bảng 4-13 Cấu trúc dữ liệu của lớp MyList ............................................................... 76 Bảng 4-14 Các hàm chức năng của lớp MyList ......................................................... 77 xiv Bảng 4-15 Cấu trúc dữ liệu lớp EMixAgent .............................................................. 80 Bảng 4-16 Các hàm chức năng của lớp EMixAgent .................................................. 83 Bảng 4-17 Kỹ thuật xử lý tại lớp RRT ....................................................................... 84 Bảng 4-18 Kỹ thuật tính giá trị utility trong lớp MyCache ......................................... 84 Bảng 4-19 Kỹ thuật xử lý phân loại và thêm dữ liệu trong lớp MyCache ................... 86 Bảng 4-20 Kỹ thuật xử lý tại lớp MyList ................................................................... 87 Bảng 4-21 Kỹ thuật xử lý tại lớp numNeighNeigh..................................................... 87 Bảng 4-22 Hàm comand ............................................................................................ 88 Bảng 4-23 Hàm recv ................................................................................................. 89 Bảng 4-24 Danh sách gói tin ..................................................................................... 89 Bảng 4-25 Cấu trúc thông tin điều hướng .................................................................. 90 Bảng 4-26 Cấu trúc thông tin "hdr_cmn *ch=HDR_CMN(Packet *)" ....................... 90 Bảng 4-27 Cấu trúc gói tin "reply_numberNeigh_pkt" .............................................. 90 Bảng 4-28 Các thuộc tính trong gói tin "reply_numberNeigh_pkt" ............................ 91 Bảng 4-29 Quá trình gửi gói tin đến các MU xác định ............................................... 91 Bảng 4-30 Lớp PktMU_Neighs_Timeout .................................................................. 92 Bảng 4-31 Khởi động timeout ................................................................................... 92 Bảng 4-32 Phương thức expire .................................................................................. 93 Bảng 5-1 Các trường hợp tổng quát phân bổ dữ liệu .................................................. 97 Bảng 5-2 Chi tiết các trường hợp DN ........................................................................ 97 Bảng 5-3 Các trường hợp mô phỏng thử nghiệm kiến trúc E-MIX-3 ......................... 98 Bảng 5-4 Cấu hình tham số thử nghiệm ..................................................................... 99 Bảng 5-5 Kết quả số lượng thông điệp với số lượng 10 MUs .................................. 100 Bảng 5-6 Kết quả thời gian đáp ứng của một RD với số lượng 10 MUs .................. 102 Bảng 5-7Kết quả số lượng thông điệp với số lượng 20 MUs ................................... 104 Bảng 5-8 Kết quả thời gian đáp ứng của một RD với số lượng 20 MUs .................. 106 Bảng 5-9 Kết quả số lượng thông điệp với số lượng 30 MUs .................................. 109 Bảng 5-10 Kết quả thời gian đáp ứng của một RD với số lượng 30 MUs ................ 110 Bảng 5-11 Kết quả số lượng thông điệp với số lượng 40 MUs................................. 112 Bảng 5-12 Kết quả thời gian đáp ứng của một RD với số lượng 40 MUs ................ 113 Bảng 5-13 Kết quả tiêu chí đưa yêu cầu lên kênh uplink ......................................... 115 xv Bảng 5-14 Kết quả số lượng thông điệp với số lượng 50 MUs................................. 116 Bảng 5-15 Kết quả thời gian đáp ứng của một RD với số lượng 50 MUs ................ 118 Bảng 5-16 Kết quả số lượng thông điệp với số lượng 60 MUs................................. 119 Bảng 5-17 Kết quả thời gian đáp ứng của một RD với số lượng 60 MUs ................ 121 Bảng 5-18 Kết quả số lượng thông điệp trung bình và thời gian đáp ứng trung bình với từng số lượng MUs .......................................................................................... 122 Bảng 5-19 So sánh với kiến trúc MIX ..................................................................... 124 xvi TÓM TẮT Trong bối cảnh môi trường di động hiện nay, các thiết bị di động hạn chế về năng lượng, khả năng tính toán và không gian lưu trữ. Vì vậy, khi các thiết bị động truy vấn dữ liệu cần phải tính toán đến hiệu quả năng lượng, hiệu quả xử lý và hiệu quả lưu trữ. Trong kiến trúc client/server, các client thường xuyên truy vấn dữ liệu đến server làm tăng chi phí truyền thông, băng thông tăng, thời gian hồi đáp dài. Vì vậy, người ta muốn các thiết bị di động chia sẻ cộng tác kho lưu trữ (cache) để giảm thời gian chờ và tăng khả năng lấy được dữ liệu trong một môi trường ít kết nối. Về mặt năng lượng, các kiến trúc cũng cần có một cơ chế truy vấn, tổng hợp dữ liệu hiệu quả hơn. Nhiều công trình nghiên cứu đã đưa ra các chiến lược và kỹ thuật lưu trữ lại dữ liệu (caching). Các kỹ thuật xử lý, lưu trữ hiệu quả giúp tăng hiệu suất của mô hình cộng tác chia sẻ dữ liệu. Từ đó giảm chi phí truyền thông giữa các client và server cũng như rút ngắn thời gian hồi đáp truy vấn dữ liệu. Do đó, trong đề tài này chúng tôi sẽ tìm hiểu về các vấn đề sau: Về mặt lý thuyết: Nghiên cứu tìm hiểu các mô hình cộng tác chia sẻ dữ liệu trên môi trường di động. Về mặt ứng dụng: Chúng tôi hiện thực hóa một mô hình cộng tác chia sẻ dữ liệu trong môi trường cơ sở dữ liệu di động, cài đặt thử nghiệm thuật toán và đưa ra kết quả thực nghiệm cho bài toán. xvii Chương 1 - MỞ ĐẦU 1.1 Giới thiệu đề tài Theo xu thế hiện nay, công nghệ thông tin (CNTT) đã trở thành một phần tất yếu trong cuộc sống. CNTT hỗ trợ trong nhiều lĩnh vực như kinh tế, thương mại, dịch vụ, xã hội...Với sự phát triển mạnh mẽ của kỹ thuật mạng không dây cùng với các loại thiết bị di động ngày càng hiện đại đã mang lại nhiều tiện ích cho người dùng trong việc trao đổi thông tin và dữ liệu. Hệ thống thông tin di động được phát triển đầu tiên với kiến trúc mạng client/server. Theo kiến trúc này, các máy khách (clients) sẽ kết nối đến một máy chủ (server) thông qua một giao thức nhất định (www, fpt, telnet, ..). Mô hình mạng client/server có rất nhiều điểm ưu việt, nổi bật là mọi xử lý sẽ nằm trên server, do đó tránh cho các client những tính toán nặng nề. Tuy nhiên, kiến trúc mạng client/server không còn phù hợp và gây ra nhược điểm khi số lượng máy khách tăng lên. Lý do chính là khi số lượng máy khách tăng lên thì nhu cầu truy xuất dữ liệu và băng thông tăng, dẫn đến server giảm khả năng cung cấp dịch vụ cho các clients. Đặc biệt trong môi trường mạng không dây kết nối yếu hoặc thường xuyên mất kết nối thì kiến trúc client/server này hoàn toàn không còn phù hợp nữa. Để khắc phục các nhược điểm của kiến trúc client/server, các nhà khoa học đã nghiên cứu đưa ra một mô hình kiến trúc mới phù hợp trong môi trường hệ thống thông tin di động, đó là mô hình cộng tác chia sẽ dữ liệu và thông tin giữa các clients với nhau để hạn chế việc truy xuất đến server. Đối với mô hình này các mobile user (MUs) có vai trò như nhau, mỗi MU đóng vai trò vừa là máy chủ vừa là máy khách. Client là các thiết bị di động có khả năng xử lý, lưu trữ. Tuy nhiên các thiết bị di động hạn chế về năng lượng, khả năng tính toán và không gian lưu trữ thấp, vì vậy người ta muốn các thiết bị di động chia sẻ cộng tác kho lưu trữ (cache). Việc này nhằm giảm thời gian chờ và tăng khả năng lấy được dữ liệu trong một môi trường ít kết nối. Với cơ chế này, kiến trúc đưa ra sẽ giải quyết được vấn đề quá tải do một số lượng lớn các clients truy xuất đến server, cũng như vấn đề clients vẫn hoàn toàn truy xuất được dữ liệu trong trường hợp máy chủ ngưng cung cấp dịch vụ do môi trường mất kết nối hoặc kết nối yếu. Bên cạnh đó, 1