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


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

ii
Khoa Công Nghệ Thông Tin
Bộ môn Hệ Thống Thông Tin

ĐỀ CƯƠNG CHI TIẾT
Tên đ
ề


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
iii
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:


 Đá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
v
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

Th.S Nguyễn Trầ
n Minh Thư
Ngày tháng năm 2010
SV thực hiện
La Phương Thanh – Lê Thị Thanh Thúy


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

vii
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


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

viii
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.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

ix
4.4.1 Giới thiệu 63

4.4.2 Giao diện chính của E-MIX Demo 64



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

x
5.2 Mô phỏng kiểm nghiệm kiến trúc 95



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

xi
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

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

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



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

xv
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 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

xvi
Bảng 5-14 Kết quả số lượng thông điệp với số lượng 50 MUs 116


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.
1
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 tuyến (routing)…. trong môi trường di động.
3
Một số công trình mà chúng tôi tìm hiểu như: “Caching and Query Processing
in MANETs” của tác giả Jinbao Li [7], “Cooperative caching in mobile ad hoc
networks based on data utility” của tác giả Narottam Chanda [9], “An Improved
Architecture for Complete Cache Management In Mobile Computing Environments”
của tác giả G. AnandHaraj [11]…. Sau đó chúng tôi rút ra một số ưu điểm và khuyết
điểm của từng kiến trúc, so sánh để xây dựng một kiến trúc hiệu quả trong môi
trường thông tin di động.
1.4 Nội dung đề tài
Với mục tiêu của đề tài đã đặt ra là nghiên cứu và tìm hiểu các mô hình cộng
tác dữ liệu trong hệ thống thông tin di động, sau đó đề xuất một kiến trúc và cài đặt
để kiểm tra tính hiệu quả. Nội dung luận văn được chia thành cấu trúc như sau:
 Chương 1: Mở Đầu
 Chương 2: Tổng Quan Về Các Mô Hình Cộng Tác Chia Sẻ Dữ Liệu Trong Môi
Trường Di Động. Trong chương này, chúng tôi sẽ giới thiệu một số mô hình cộng
tác chia sẻ dữ liệu trong môi trường di động, các thuật toán quản lí và thay thế
kho lưu trữ, thuật toán xử lý truy vấn phân tán. Đồng thời tìm hiểu ý tưởng chính
của các kĩ thuật lưu trữ trong môi trường di động.
 Chương 3: Kiến Trúc Hệ Thống Thông Tin Di Động Sử Dụng Mô Hình Cộng
Tác Chia Sẻ Dữ Liệu. Trong chương này, chúng tôi sẽ tìm hiểu đề xuất một kiến
trúc hệ thống thông tin di động hiệu quả vận dụng mô hình cộng tác chia sẻ dữ
liệu.
 Chương 4: Cài Đặt Thử Nghiệm. Trong chương này, chúng tôi sẽ cài đặt thử
nghiệm kiến trúc đã đề xuất ở chương 3 để kiểm tra tính hiệu quả.
 Chương 5: Kết Quả Thử Nghiệm. Trong chương này, chúng tôi trình bày các kết
quả thực nghiệm mà chúng tôi đã cài đặt và so sánh các kết quả này với các công
trình khác để kiểm tra tính hiệu quả.
 Chương 6: Tổng Kết. Trong chương này chúng tôi sẽ tóm tắt các vấn đề đã đạt
được, những vấn đề còn tồn tại và hướng phát triển trong tương lai.

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 đó,
kiến trúc có thể đem lại nhiều hiệu quả hơn trong việc khai thác, tận dụng nguồn tài
6
nguyên sẵn có của tất cả các MUs trong hệ thống mạng, nhờ đó việc phân bổ lưu
lượng thông tin khi cần một cách hợp lý để tránh tắc nghẽn trên mạng.
Khái niệm cộng tác chia sẻ dữ liệu ngày nay cải tiến theo nhiều mục đích sử dụng
khác nhau, không chỉ tối ưu kho lưu trữ giữa các thiết bị di động mà còn giảm tải băng
thông truy xuất đến server, đặc biệt trong mô hình mạng có nhiều client với tần suất
truy vấn dữ liệu cao.
2.1.2Ưu điểm của mô hình cộng tác chia sẻ dữ liệu
Nhờ việc chia sẻ kho lưu trữ giữa các thiết bị di động, mô hình cộng tác này giảm
thiểu thời gian chờ hồi đáp truy vấn dữ liệu 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 với cơ chế truy vấn, tổng
hợp dữ liệu hiệu quả hơn đã giúp giảm chi phí truyền thông giữa các client và server.
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
Với những ứng dụng trong môi trường không dây và các thiết bị di động, chúng ta
sẽ gặp phải các khó khăn về quản lý dữ liệu, ví dụ như không đảm bảo được tính nhất
quán dữ liệu, không tận dụng được không gian lưu trữ toàn cục …Trong phần này,
chúng tôi trình bày ý nghĩa của các kĩ thuật quản lý kho lưu trữ, chia sẻ, và truy vấn
dữ liệu đã được nghiên cứu sử dụng trong hệ thống thông tin di động.
2.2.1Thuật toán thay thế (Replacement Algorithm)
Thuật toán thay thế được sử dụng để quyết định dữ liệu nào sẽ bị xóa khi kho lưu
trữ đầy, để dành chỗ cho một đơn vị dữ liệu mới. Khi thêm một đơn vị dữ liệu mới,
thuật toán thay thế sẽ chọn đơn vị dữ liệu đã tồn tại có độ ưu tiên thấp nhất trong kho
lưu trữ và tiến hành thay thế với đơn vị dữ liệu mới. Mỗi thuật toán sẽ có một phương
pháp để định độ ưu tiên khác nhau và được phân thành hai nhóm tư tưởng chính:
2.2.1.1Thuật toán dựa trên vùng nhớ tạm (Temporal Locality Based
Algorithm)