ỦY BAN NHÂN DÂN TP.HCM
SỞ KHOA HỌC VÀ CÔNG NGHỆ

BÁO CÁO NGHIỆM THU

XÂY DỰNG MƠ HÌNH QUẢN LÝ CHIA SẺ DỮ
LIỆU TRONG MẠNG NGANG HÀNG KHÔNG
DÂY

CHỦ NHIỆM ĐỀ TÀI

PGS.TS. ĐỒNG THỊ BÍCH THỦY

THÀNH PHỐ HỒ CHÍ MINH
THÁNG 5/2015


Mục lục

PHẦN MỞ ĐẦU ................................................................................................................ 1

Thông tin đề tài: .....................................................................................................................1
Mục tiêu .................................................................................................................................1
Nội dung ................................................................................................................................2
Sản phẩm đăng ký theo hợp đồng thực hiện đề tài dự án.....................................................2
Sản phẩm nộp của đề tài dự án ..............................................................................................3
Chương 1 TỔNG QUAN VỀ TÀI LIỆU NGHIÊN CỨU ..................................................... 5

Phần 1 NGHIÊN CỨU CÁC CHIẾN LƯỢC CỘNG TÁC VÀ ĐỒNG BỘ DỮ
LIỆU5
1.1 Một số chiến lược cộng tác dữ liệu và so sánh đánh giá giữa các cơng trình ............5

1.1.1 Sơ lược các cơng trình nghiên cứu liên quan đến phương pháp cộng tác dữ
liệu trong môi trường di động ......................................................................................................5
1.1.2 So sánh đánh giá các giải pháp cộng tác dữ liệu .......................................................... 18

1.2

Một số chiến lược nhất quán dữ liệu ........................................................................ 20
1.2.1 Sơ lược các cơng trình nghiên cứu liên quan đến phương pháp nhất quán dữ
liệu trong môi trường di động ................................................................................................... 20
1.2.2 So sánh đánh giá các giải pháp ..................................................................................... 27

Phần 2 NGHIÊN CỨU VỀ HỌC TẬP CỘNG TÁC TRONG MÔI TRƯỜNG DI
ĐỘNG ................................................................................................................................. 28
1.3 Định nghĩa học tập cộng tác...................................................................................... 28
1.4 Định nghĩa học tập di động ....................................................................................... 30
1.5 Học cộng tác với sự hỗ trợ của thiết bị di động ....................................................... 31
1.6 Kết luận ..................................................................................................................... 42
Chương 2 NỘI DUNG NGHIÊN CỨU ............................................................................ 43

Phần 1 MƠ HÌNH QUẢN LÝ CHIA SẺ DỮ LIỆU TRONG MẠNG NGANG
HÀNG KHÔNG DÂY ....................................................................................................... 43
2.1 Xây dựng mơ hình quản lý chia sẻ dữ liệu ............................................................... 43
2.1.1 Mơ tả cấu trúc mơ hình chia sẻ dữ liệu ngang hàng .................................................... 43
2.1.2 Nguyên lý hoạt động tìm dữ liệu trên mơ hình ............................................................ 44
2.1.3 Kiến trúc chi tiết tại mỗi MH........................................................................................ 46

2.2

Các mơ-đun xử lý trong mơ hình .............................................................................. 48
2.2.1

2.2.2
2.2.3
2.2.4
2.2.5
2.2.6

2.3

Nguyên lý gia nhập mạng của MH............................................................................... 48
Mô tả cấu trúc kho dữ liệu lưu cục bộ của mỗi MH .................................................... 49
Mơ-đun xử tìm kiếm dữ liệu......................................................................................... 49
Mơ-đun xử lý thu nạp dữ liệu ....................................................................................... 56
Mô-đun xử lý thay thế dữ liệu ...................................................................................... 59
Mô-đun xử lý Nhất quán dữ liệu .................................................................................. 60

Kết luận ..................................................................................................................... 66

i


Phần 2 XÂY DỰNG ỨNG DỤNG MINH HỌA MƠ HÌNH QUẢN LÝ CHIA
SẺ DỮ LIỆU ...................................................................................................................... 67
2.4 Mơ hình kiến trúc và kịch bản thử nghiệm............................................................... 67
2.4.1 Mơ hình kiến trúc.......................................................................................................... 67
2.4.2 Các hệ thống con của MES .......................................................................................... 68

2.5

Phân tích các chức năng của hệ thống MES ............................................................ 72
2.5.1 Hệ thống hỗ trợ thảo luận trong lớp học (Classroom Discussion System CDS) 72

2.5.2 Hệ thống hỗ trợ học tập cộng tác theo nhóm trong lớp học(Classroom
Cooperative System - CCS) ...................................................................................................... 74
2.5.3 Hệ thống hỗ trợ đồng bộ dữ liệu (Data Consistency System - DCS) .......................... 75

2.6
2.7

Thiết kế giao diện ...................................................................................................... 76
Giới thiệu hệ thống học cộng tác ngoài trời (outdoor) ............................................. 78
2.7.1 Giới thiệu mơ hình học tập cộng tác di động. .............................................................. 78

2.8

Kịch bản thử nghiệm ................................................................................................. 79

Chương 3 KẾT QUẢ VÀ THẢO LUẬN .......................................................................... 84

Phần 1 MÔ HÌNH QUẢN LÝ CHIA SẺ DỮ LIỆU TRONG MẠNG NGANG
HÀNG KHƠNG DÂY ....................................................................................................... 84
3.1 Tiêu chí và độ đo thử nghiệm ................................................................................... 84
3.1.1 Tiêu chí đánh giá dựa trên kích thước kho lưu trữ (cache size): ................................. 84
3.1.2 Tiêu chí dựa trên số lượng MH: ................................................................................... 85

3.2

Kết quả thử nghiệm so với các cơng trình khác ....................................................... 85
3.2.1 Tham số thiết lập mô phỏng ......................................................................................... 85
3.2.2 So sánh về tiêu chí kích thước kho lưu trữ................................................................... 86
3.2.3 So sánh về tiêu chí số lượng MH ................................................................................. 89


Phần 2 XÂY DỰNG ỨNG DỤNG MINH HỌA MƠ HÌNH QUẢN LÝ CHIA
SẺ DỮ LIỆU ...................................................................................................................... 92
3.1 Kết quả thử nghiệm của hệ thống hỗ trợ dạy và học trong lớp................................ 92
3.2 Kết quả thử nghiệm của hệ thống học cộng tác ngoài lớp ....................................... 94
KẾT LUẬN VÀ ĐỀ NGHỊ ................................................................................................ 96

3.3

Các kết quả đạt được ................................................................................................. 96
3.3.1 Về mơ hình cộng tác chia sẻ dữ liệu trong mạng ngang hàng không dây................... 96
3.3.2 Về ứng dụng hỗ trợ giảng dạy và học tập trong môi trường không dây ..................... 96

3.4

Hướng phát triển ....................................................................................................... 97

Tài liệu tham khảo ......................................................................................................... 98
Các cơng trình đã cơng bố ......................................................................................... 102

ii


PHẦN MỞ ĐẦU
Thông tin đề tài:
 Tên đề tài: Xây dựng mơ hình quản lý chia sẻ dữ liệu trong mạng ngang hàng không
dây
 Chủ nhiệm đề tài/dự án:PGS. TS Đồng Thị Bích Thủy
 Cơ quan chủ trì: Trường ĐH Khoa học Tự Nhiên
 Thời gian thực hiện: 12/2010 – 12/2011
 Kinh phí được duyệt: 360 triệu

 Kinh phí đã cấp: 220 triệu theo TB số: 288/TB-SKHCN ngày 21/12/ 2010

Mục tiêu
1) Xây dựng một mơ hình quản lý chia sẻ dữ liệu trong mạng ngang hàng khơng dây.
Mơ hình xây dựng hướng đến một số vấn đề chính sau:


Xử lý truy vấn dữ liệu: Chúng tôi hướng tới việc thực hiện lưu trữ lại kết quả các
câu truy vấn trước đó tại các thiết bị di động (được gọi là kỹ thuật caching) để
phục vụ cho các lần truy vấn sau nhằm giảm khả năng yêu cầu dữ liệu tại máy
chủ, tiết kiệm năng lượng và chi phí của mạng không dây trong việc chuyển dữ
liệu. Việc lưu trữ lại dữ liệu tại mỗi thiết bị di động không chỉ phục vụ cho các
u cầu dữ liệu của chính nó mà còn phục vụ cho các yêu cầu dữ liệu của các
thiết bị lân cận.



Xử lý thay thế dữ liệu: dữ liệu sau khi được lưu trữ tại thiết bị di động được gọi là
kho dữ liệu lưu (cache), khi kho dữ liệu lưu bị đầy vấn đề chúng ta phải làm như
thế nào để loại bỏ dữ liệu không còn hợp lệ để thay thế bằng dữ liệu mới một
cách chính xác, kịp thời.



Xử lý đồng bộ dữ liệu: đảm bảo dữ liệu lưu tại kho dữ liệu luôn được nhất quán
với dữ liệu gốc ban đầu.

2) Xây dựng mơ phỏng mơ hình đề xuất thơng qua cơng cụ mô phỏng mạng.
3) Xây dựng một ứng dụng thử nghiệm trong lĩnh vực giáo dục có áp dụng mơ hình đề
xuất.


1


Nội dung
Sản phẩm đăng ký theo hợp đồng thực hiện đề tài dự án
Giai đoạn Từ tháng 12/2010 đến tháng 12/2011
TT

Tóm tắt nội dung

Sản phẩm cần đạt

1

Khảo sát hiện trạng các cơng trình nghiên cứu liên quan Tài liệu báo cáo
đến HTTT DĐ có áp dụng kiến trúc mạng P2P trong và
ngồi nước.

2

Đề xuất mơ hình quản lý ứng dụng chia sẻ dữ liệu giữa các Mơ hình
MH.

3

Phân tích, thiết kế cấu trúc kho dữ liệu lưu cục bộ tại mỗi Cấu trúc, nguyên lý hoạt
MH phục vụ truy vấn, đồng bộ, thay thế dữ liệu,…
động của kiến trúc


4

Đề xuất các giải pháp liên quan để hiện thực hóa cấu trúc Giải pháp, thuật toán
đã đề xuất

Giai đoạn Từ tháng 12/2011 đến tháng 6/2012.
TT

Sản phẩm cần đạt

Tóm tắt nội dung

1

Xây dựng mô phỏng để thử nghiệm kiến trúc đề xuất Chương trình, các mơ-đun
và hiệu chỉnh (nếu có)
liên quan

2

Xây dựng ứng dụng thực tế để thử nghiệm tính khả thi Ứng dụng thử nghiệm
của mơ hình đề xuất.

SẢN PHẨM NGHIÊN CỨU
TT
1

Tên sản phẩm tổng kết

Yêu cầu khoa học, kinh tế


Mô hình và ngun lý hoạt động 
của mơ hình trong việc chia sẻ
cộng tác dữ liệu phục vụ cho 
HTTT DĐ

Ghi chú

Chia sẻ dữ liệu giữa các thiết bị di
động.
Đồng bộ được dữ liệu trong trường
hợp dữ liệu mất hiệu lực.
Giải phóng dữ liệu hợp lý khi bộ nhớ
của thiết bị lưu trữ đầy.

Báo cáo,
Tài liệu

2

Giải pháp thực hiện và các thuật Giải pháp, thuật toán đề nghị đưa ra hiệu
toán đi kèm
quả và được so sánh đánh giá với các
cơng trình nghiên cứu trước đó.

Báo cáo,
Tài liệu

3


Chương trình thử nghiệm mô Mô phỏng được kiến trúc đã đề xuất.
phỏng

Báo cáo,
Tài liệu,
CD ROM

4

Đặc tả ứng dụng thực tế trong Bảng mô tả chi tiết ứng dụng thực tế.
lĩnh vực giáo dục có thể áp dụng
mơ hình đề xuất

Báo cáo,
Tài liệu



2


5

Bảng số liệu, Sơ đồ

Các bảng số liệu kết quả chạy thực
nghiệm và các biểu đồ so sánh dựa trên
bảng số liệu.

Báo cáo,

Tài liệu,
CD –
ROM

6

Bài báo khoa học

2 bài báo đăng ở hội nghị quốc tế hoặc
hội nghị quốc gia.

Báo cáo,
Tài liệu,
CD –
ROM

Sản phẩm nộp của đề tài dự án
Sản phẩm nộp theo đăng ký, giai đoạn từ tháng 12/2010 đến tháng 12/2011
TT

Tóm tắt nội dung

Sản phẩm nộp

1

Khảo sát hiện trạng các cơng trình nghiên cứu liên quan Tài liệu báo cáo vè
đến HTTT DĐ có áp dụng kiến trúc mạng P2P trong và Nghiên cứu hiện trạng
ngoài nước.
(Phần 1 – Chương 1)


2

Đề xuất mơ hình quản lý ứng dụng chia sẻ dữ liệu giữa các Tài liệu báo cáo về Mơ
MH.
hình đề xuất
(Phần 1 – Chương 2)

3

Phân tích, thiết kế cấu trúc kho dữ liệu lưu cục bộ tại mỗi Tài liệu báo cáo về Cấu
MH phục vụ truy vấn, đồng bộ, thay thế dữ liệu,…
trúc, nguyên lý hoạt
động của kiến trúc
(Phần 1 – Chương 2)

4

Đề xuất các giải pháp liên quan để hiện thực hóa cấu trúc Tài liệu báo cáo về Giải
đã đề xuất
pháp, thuật toán
(Phần 1 – Chương 2)

Sản phẩm nộp theo đăng ký, giai đoạn từ tháng 12/2011 đến tháng 6/2012.
TT

Sản phẩm nộp

Tóm tắt nội dung


1

Xây dựng mô phỏng để thử nghiệm kiến trúc đề xuất Chương trình, các mơ-đun
và hiệu chỉnh (nếu có)
liên quan, kết quả thử
nghiệm
( Phần 1 – Chương 3)

2

Xây dựng ứng dụng thực tế để thử nghiệm tính khả thi Ứng dụng thử nghiệm chia
của mơ hình đề xuất.
sẻ thơng tin học tập
(Phần 2 - ở các Chương 1, 2,
3)

SẢN PHẨM NGHIÊN CỨU
TT
1

Tên sản phẩm tổng kết
Mơ hình và ngun lý hoạt động 

Yêu cầu khoa học, kinh tế
Chia sẻ dữ liệu giữa các thiết bị di
3

Ghi chú
Báo cáo,



động.
Đồng bộ được dữ liệu trong trường
hợp dữ liệu mất hiệu lực.
Giải phóng dữ liệu hợp lý khi bộ nhớ
của thiết bị lưu trữ đầy.

Tài liệu

2

Giải pháp thực hiện và các thuật Giải pháp, thuật toán đề nghị đưa ra hiệu
toán đi kèm
quả và được so sánh đánh giá với các
cơng trình nghiên cứu trước đó.

Báo cáo,
Tài liệu

3

Chương trình thử nghiệm mô Mô phỏng được kiến trúc đã đề xuất.
phỏng

Báo cáo,
Tài liệu,
CD ROM

4


Đặc tả ứng dụng thực tế trong Bảng mô tả chi tiết ứng dụng thực tế.
lĩnh vực giáo dục có thể áp dụng
mơ hình đề xuất

Báo cáo,
Tài liệu

5

Bảng số liệu, Sơ đồ

Các bảng số liệu kết quả chạy thực
nghiệm và các biểu đồ so sánh dựa trên
bảng số liệu.

Báo cáo,
Tài liệu,
CD –
ROM

6

Bài báo khoa học

2 bài báo đăng ở hội nghị quốc tế hoặc
hội nghị quốc gia.

Báo cáo
(2 bài
báo), Tài

liệu, CD –
ROM

7

Đào tạo nghiên cứu

5 Luận văn tốt nghiệp đại học (ĐH), 1
cao học (CH)

Thông tin
thể hiện ở
mục Cơng
trình cơng
bố - Sản
phẩm đào
tạo

của mơ hình trong việc chia sẻ
cộng tác dữ liệu phục vụ cho 
HTTT DĐ


4


Chương 1

TỔNG QUAN VỀ TÀI LIỆU NGHIÊN CỨU
Tóm tắt chương:


Nội dung chương 1 trình bày gồm 2 phần chính: phần 1 trình bày hiện trạng nghiên cứu
về các chiến lược cộng tác dữ liệu và đồng bộ dữ liệu; phần 2 trình bày hiện trạng nghiên
cứu về học tập di động và học tập di động cộng tác.
Nội dung chi tiết của Phần 1:


Giới thiệu và phân tích một số phương pháp cộng tác dữ liệu trong môi trường di
động.



Giới thiệu và phân tích một số phương pháp nhất quán dữ liệu trong môi trường di
động.

Nội dung chi tiết của phần 2:


Giới thiệu về học tập di động và học tập di động cộng tác.



Khảo sát các hệ thống về học tập di động và học tập di động cộng tác trên thế giới.

Phần 1 NGHIÊN CỨU CÁC CHIẾN LƯỢC CỘNG TÁC VÀ ĐỒNG BỘ
DỮ LIỆU
1.1 Một số chiến lược cộng tác dữ liệu và so sánh đánh giá giữa
các cơng trình
1.1.1 Sơ lược các cơng trình nghiên cứu liên quan đến phương pháp
cộng tác dữ liệu trong môi trường di động

1) Lưu trữ dữ liệu (CacheData)
Trong cơng trình nghiên cứu [4], tác giả Liangzhong Yin đã đề xuất kỹ thuật lưu
trữ dữ liệu của các MH (Mobile Host) trung gian trên đường định tuyến. Cơng trình
nghiên cứu chỉ rõ các MH trung gian trên đường định tuyến nhận dữ liệu từ MH khác,
phải lưu trữ dữ liệu vào bộ nhớ cục bộ để phục vụ cho yêu cầu trong tương lai thay vì gửi
yêu cầu lên máy chủ BS (Base Station). Các MH trên đường định tuyến lưu trữ dữ liệu,
không lưu đường dẫn. Tuy nhiên, chiến lược lưu trữ này khơng hiệu quả vì nếu cùng một
hạng mục dữ liệu di mà có nhiều MH gần nhau cùng lưu trữ, khơng những gây lãng phí
bộ nhớ kho lưu trữ mà cịn tăng chi phí duy trì. Vì thế chiến lược lưu trữ dữ liệu
(CacheData) không phù hợp với kiến trúc mạng cộng tác chia sẻ dữ liệu theo nhóm nơi

5


mà các MH bị giới hạn không gian bộ nhớ lưu trữ cục bộ. Do đó cơng trình nghiên cứu
chỉ ra rằng: không lưu trữ dữ liệu nếu tất cả yêu cầu đến từ cùng một MH.

1.1.1.1 Lưu trữ định tuyến (CachePath)
Để giải quyết những hạn chế của kỹ thuật lưu trữ dữ liệu, tác giả [4] đã đưa ra kỹ
thuật lưu trữ đường định tuyến: các MH lưu trữ đường định tuyến của MH chứa dữ liệu
gần nhất, trong tương lai có thể định hướng q trình tìm kiếm nhanh hơn. Trong môi
trường mạng di động, các MH lưu trữ hay thay thế dữ liệu do sự giới hạn về kích thước
bộ nhớ cục bộ. Tuy nhiên, trong mơi trường mà các MH thường xuyên di chuyển nên
đường định tuyến từ MH nguồn đến MH đích cũng thay đổi. Vì vậy việc lưu trữ đường
định tuyến từ MH nguồn đến MH đích khơng cịn chính xác. Để giải quyết vấn đề trên,
MH nguồn chỉ lưu trữ đường định tuyến đến MH đích khi khoảng cách giữa hai MH này
ngắn hơn khoảng cách đến BS. Hay nói cách khác, lưu lại địa chỉ của MH trả dữ liệu về
(MH đích) để lần truy vấn trong tương lai có thể biết chính xác MH nào có dữ liệu u
cầu.


Hình 1-1. Mơ hình mạng ad hoc
Ví dụ trong Hình 1-1, MH1 u cầu dữ liệu di từ MH11, khi MH3 trả dữ liệu về cho
MH1, MH3 biết rằng MH1 đã có lưu dữ liệu di vào trong bộ nhớ cục bộ. Ở lần tìm kiếm
khác, như MH2 muốn có dữ liệu di, lúc này MH3 biết rằng di ở MH1 gần hơn so với MH11,
do đó MH3 sẽ đưa u cầu tìm kiếm sang MH1 thay vì MH11..

2) Kết hợp lưu trữ dữ liệu và đường định tuyến (HybridCache)
Để giải quyết hạn chế cho kỹ thuật lưu trữ dữ liệu và lưu trữ định tuyến, tác giả đã
đưa ra kỹ thuật kết hợp lưu trữ dữ liệu và đường dẫn (Hybrid Cache) [4]. HybridCache
dựa vào 3 tham số chính chính: kích thước dữ liệu (S), thời gian sống dữ liệu (TTL), số
lượng bước nhảy (Hsave). Cụ thể các trường hợp sử dụng các tham số này cho các kỹ thuật
CacheData, CachePath và HybridCache được trình bày trong Bảng 1-1.
6


Bảng 1-1. Các trường hợp sử dụng CacheData, CachePath và HybridCache
HybridCache

CacheData

CachePath

Ts

Si ≤ Ts

Si ≤ Ts

TTTL


TTLi> TTTL

Lưu trữ

TH

Hsave> TH

Hsave> TH và có đủ khơng gian bộ nhớ

Nếu kích thước Si khơng vượt quá ngưỡng tham số Ts thì sử dụng CacheData và
CachePath. Nếu giá trị TTL nhỏ hơn một giới hạn TTTL thì dữ liệu di khơng sử dụng
CachePath, ngược lại TTL lớn hơn giá trị TTTL thì sử dụng CachePath. Nếu Hsave lớn hơn
giá trị Th thì sử dụng CachePath, ngược lại CachePath sẽ không được sử dụng, sử dụng
CacheData khi có đủ khơng gian lưu trữ. Tuy nhiên CacheData, CachePath và
HybridCache có hạn chế là mỗi khi có sự thay thế trên CacheData, hay MH thường xuyên
di chuyển thì tốn thêm thời gian xử lý cho cập nhật CachePath trên MH lân cận.
Một đặc điểm của môi trường mạng không dây là các MH rất hạn chế về khả năng
xử lý và lưu trữ, hạn chế về không gian bộ nhớ, các thuật tốn trên khơng thể hiện được
tính cộng tác giữa các MH.

3) Kiến trúc COCA
Trong kiến trúc COCA (COoperative CAching) [3], [5] của nhóm tác giả Chi-Yin
Chow, mỗi MH được trang bị hai thiết bị giao tiếp không dây (Card Wireless), một thiết
bị chuyên dùng để giao tiếp với máy chủ (MSS), thiết bị còn lại dùng để truyền tin với
các MH khác trong vùng để chia sẻ dữ liệu cộng tác qua kênh truyền P2P và được mơ tả
trong Hình 1-2.

Hình 1-2. Kiến trúc COCA [3][5]


7


0.Request

1. Local cache hit

Interface Cards
Global

Interface Cards
MSS

MH

2.Local cache miss
3.Global cache hit

4.Global cache miss

MSS

Interface Cards
Global

Interface Cards
MSS

MH


Hình 1-3. Cơ chế hoạt động của kiến trúc COCA [3][5]
Cơ chế hoạt động của kiến trúc COCA được mơ tả trong Hình 1-3. Khi nhận được
u cầu dữ liệu từ người dùng, đầu tiên MH nguồn sẽ tìm kiếm dữ liệu yêu cầu trong bộ
nhớ cục bộ. Nếu dữ liệu khơng được tìm thấy trong bộ nhớ cục bộ thì yêu cầu tìm kiếm sẽ
được gửi đến các MH trong vùng (các MH liên kết với MH nguồn qua 1 bước liên kết)
đồng thời chờ dữ liệu được phát từ máy chủ (MSS) ở kênh truyền xuống (broadcast).
Trong lúc chờ dữ liệu được phát, nếu một trong số các MH đích trong vùng hồi đáp dữ
liệu yêu cầu cho MH nguồn trước khi dữ liệu được máy chủ phát, MH nguồn gởi yêu cầu
đến MH đích hồi đáp sớm nhất để yêu cầu truy xuất dữ liệu. Trong trường hợp khơng có
MH trong vùng nào hồi đáp dữ liệu yêu cầu trong một khoảng thời gian nhất định, MH
nguồn chờ dữ liệu được máy chủ phát trên kênh truyền xuống. Nếu dữ liệu yêu cầu được
phát trên kênh truyền xuống trước khi các MH vùng hồi đáp, MH nguồn lấy dữ liệu trên
kênh truyền lên mà không cần gửi thông tin truy xuất dữ liệu đến các MH trong vùng.
Tuy nhiên, nếu dữ liệu vẫn không được tìm thấy từ kênh truyền xuống và các MH trong
vùng thì yêu cầu tìm kiến sẽ được gửi đến máy chủ (MSS) qua kênh truyền Point-to-Point
(Cache miss).
Kiến trúc COCA đã cho thấy sự hiệu quả trong truy vấn dữ liệu, giảm thời gian hồi
đáp khi có yêu cầu dữ liệu từ một MH bất kì. Tuy nhiên, trong mơi trường HTTT DĐ các
8


MH thường xuyên phải di chuyển nên khả năng mất kết nối xảy ra rất cao, cơng trình
nghiên cứu khơng đề cập đến vấn đề xử lý mất kết nối khi MH ra khỏi vùng dịch vụ
mạng. Bên cạnh đó, việc cộng tác chia sẻ dữ liệu giữa các MH trong vùng và chiến lược
thay thế dữ liệu khi bộ nhớ cục bộ đầy là một phần rất quan trọng và không thể thiếu
trong môi trường mạng không dây, nơi mà các MH hạn chế về tài nguyên và kho lưu trữ.
Những vấn đề này được giải quyết trong công trình nghiên cứu [6].

4) Kiến trúc DGCOCA
Cơng trình nghiên cứu [6] đưa ra chiến lược lưu trữ dữ liệu trong vùng cộng tác,

mục tiêu của chiến lược này là tối ưu kho lưu trữ cục bộ. Chiến lược thay thế dữ liệu hợp
lý sẽ làm tăng tỉ lệ có dữ liệu trong vùng, khi đó các MH khơng tốn nhiều chi phí cho một
lần truy vấn dữ liệu. Trong mơi trường mạng không dây, khả năng mất kết nối rất sẽ xảy
ra, chính vì vậy kỹ thuật xử lý khi MH bị mất kết nối được đề cập trong công trình nghiên
cứu này nhằm giảm khả năng mất dữ liệu trong vùng.
Chiến lược lưu trữ dữ liệu trong vùng cộng tác: khi yêu cầu dữ liệu được trả về,
MH nguồn có thể lưu trữ tại các MH khác trong vùng nếu bộ nhớ cục bộ của MH nguồn
bị đầy. Nếu các MH đích nằm ngồi vùng của MH nguồn, thì MH nguồn sẽ xóa đi những
dữ liệu ít được truy cập nhất để giải phóng khơng gian bộ nhớ cục bộ. Sau khi các MH
trong vùng gửi dữ liệu trả về cho MH nguồn, MH nguồn sẽ cập nhật lại nhãn thời gian
(timestamp) trong lần truy cập gần nhất để dữ liệu có thời gian sống dài hơn trong vùng
cộng tác.
Chiến lược thay thế dữ liệu tại bộ nhớ cục bộ: khi dữ liệu yêu cầu được trả về,
MH nguồn sẽ lưu trữ hạng mục dữ liệu đó nếu bộ nhớ cục bộ cịn trống. Tuy nhiên, để
tăng khơng gian lưu trữ khi bộ nhớ cục bộ đầy, MH nguồn phải loại bỏ những hạng mục
dữ liệu cũ để thay thế những hạng mục dữ liệu mới. Những hạng mục dữ liệu được truy
cập nhiều nhất luôn được giữ lại trong bộ nhớ cục bộ, những hạng mục dữ liệu ít được
truy cập trong một khoảng thời gian dài sẽ bị loại bỏ khỏi bộ nhớ cục bộ. Trong vùng,
những dữ liệu bị trùng lắp với số lượng lớn sẽ được thay thế đầu tiên để tăng không gian
bộ nhớ cục bộ.
Xử lý khi MH bị mất kết nối: trong môi trường mạng không dây, các MH hạn chế
về năng lượng và thường xuyên di chuyển nên dễ xảy ra mất kết nối với máy chủ. Để giải
quyết vấn đề này, nhóm tác giả đưa ra giải pháp ghi nhận lại thời gian
last_signature_update_ts khi MH phát tín hiệu “broadcast” để cập nhật thông tin dữ liệu
đến các MH khác trong vùng. Ngồi ra cịn ghi lại thời gian disconnection_ts khi MH mất
9


kết nối, khi MH tham gia vào mạng (kết nối lại) thì disconnection_ts được kèm theo khi
MH


phát

tín

hiệu

“broadcast”

đến

các

MH

khác

trong

vùng.

Nếu

last_signature_update_ts < disconnection_ts: có nghĩa là các MH trong vùng trả lời cho
biết MH hợp lệ, cịn ngược lại thì khơng.
Cơng trình nghiên cứu [6] đã giải quyết được vấn đề lưu trữ, thay thế dữ liệu và vấn
đề mất kết nối của các MH. Tuy nhiên, trong môi trường HTTT DĐ, tuy nhiên chưa đưa
ra được chiến lược lưu trữ cộng tác dữ liệu giữa các MH trong vùng và chiến lược thay
thế dữ liệu cũng chưa được hiệu quả. Bên cạnh đó, cơng trình nghiên cứu cũng khơng
quan tâm đến vấn đề định tuyến (routing) – nghĩa là khi một yêu cầu truy xuất dữ liệu

khơng tìm thấy tại cục bộ hoặc trong nhóm thì định tuyến sẽ giúp cho MH truy xuất dữ
liệu tới các MH ngoài vùng (các MH liên kết với MH nguồn nhiều hơn 1 bước liên kết).
Các vấn đề này được giải quyết trong cơng trình nghiên cứu [2] của nhóm tác giả
Narottam Chand, và được chúng tơi trình bày trong phần tiếp theo.

5) Chiến lược cộng tác nhóm dựa trên vùng (clusters)
Nhóm tác Narottam đề xuất mơ hình cộng tác vùng (Cluster Cooperative - CC) cho
chiến lược lưu trữ trong môi trường mạng không dây [2]. Mơ hình CC được đặc trưng bởi
đồ thị G = (V, E), trong đó V là số lượng các MH (MH1, MH2, …MHn), E đặc trưng cho
đường nối kết giữa Vi, Vj. Kí hiệu cho hai MH có thể giao tiếp với nhau bằng đường dẫn
(u,v). Kiến trúc mạng được chia thành nhiều phần bằng nhau dựa vào vị trí vật lý được
mơ tả trong Hình 1-4.

Hình 1-4. Mơ hình phân chia thành các vùng
Kích thước lớn nhất có thể có trên một vùng là 1 bước nhảy. Mỗi MH trong vùng
đảm nhận một trong hai vai trò: CSN (cache status node) và MH lưu trữ. CSN lưu trữ
danh sách thông tin kho lưu trữ của các MH khác trong vùng cùng với khoảng thời gian
sống TTL (time to live) của từng thông di dữ liệu.
10


Với sự phân chia các MH thành các vùng thì mỗi sự chuyển động của MH được
chia thành 2 loại: intra-cluster và inter-cluster. Intra-cluster là di chuyển trong cùng một
vùng, đối với loại di chuyển này thì CSN khơng cần phải cập nhật lại thông tin kho lưu
trữ của các MH khác. Ngược lại loại di chuyển inter-cluster là di chuyển ra ngồi vùng
hiện hành nên thơng tin kho lưu trữ sẽ bị thay đổi, nhóm tác giả chia sự di chuyển intercluster thành hai loại: CSN di chuyển và MH dữ liệu di chuyển.
Trước khi MH dữ liệu di chuyển, thông tin được gửi đến CSN để CSN cập nhật lại
trạng thái thông tin các kho lưu trữ. Khi MH dữ liệu tham gia nhóm, nó sẽ phát thơng
điệp xin gia nhập đến các MH trong vùng mới gia nhập. Nếu MH lân cận nhận được
thơng điệp, nó gửi trả về địa chỉ của CSN. Dựa vào thông tin này MH dữ liệu gửi thông

tin bộ nhớ cục bộ đến CSN. Sau khi cập nhật thông tin kho lưu trữ của MH dữ liệu thành
công, CSN báo trả về lại cho MH dữ liệu. Trong trường hợp khi MH dữ liệu không nhận
được thông tin địa chỉ của CSN thì nó trở thành một CSN mới.
Khi CSN di chuyển ra ngồi vùng thì sẽ chọn lựa một MH dữ liệu trong vùng đảm
nhận vai trị CSN. Q trình thay thế CSN như sau: CSN chọn ra MH phù hợp nhất (tuy
nhiên cơng trình nghiên cứu chưa nói rõ tiêu chí nào phù hợp nhất). Tất cả các thơng tin
trạng thái bộ nhớ sẽ được di chuyển sang MH mới đó. CSN sẽ gửi thơng tin cho các thành
viên cập nhật CSN mới. CSN cũ sẽ xóa hết thơng tin về kho lưu trữ của các MH trong
vùng hiện hành và xử lý gia nhập vào vùng mới.
Khi nhận được yêu cầu tìm kiếm thì quá trình thực hiện xảy ra một trong các trường
hợp sau: Local hit (dữ liệu được tìm thấy trên kho lưu trữ), Cluster hit (dữ liệu được tìm
thấy trên vùng tại CSN), Remote hit (dữ liệu được tìm thấy thơng qua các CSN khác),
Global hit (dữ liệu được tìm trên máy chủ).

Hình 1-5. Gói tin yêu cầu dữ liệu từ MHi nguồn đến MHs đích

11


Trong Hình 1-5, khi MHi cần dữ liệu dx, đầu tiên nó sẽ kiểm tra trong bộ nhớ cục bộ
của chính nó. Nếu dữ liệu dx được tìm thấy thì kết quả sẽ được trả về. Nếu dữ liệu không
được tìm thấy, MHi sẽ gửi gói tin “lookup” u cầu tìm kiếm lên CSN. CSN dựa vào
thơng tin tìm kiếm đó để tìm trong danh sách các cluters có dữ liệu dx. Nếu dữ liệu được
tìm thấy thì CSN gửi 1 gói tin “ack” đến MHi, trong gói tin “ack” chứa thơng tin địa chỉ
của MH đích có chứa dx. Lúc này MHi gửi gói tin “confirm” tới MH đích có địa chỉ vừa
nhận được từ gói tin “ack” và dữ liệu được trả về cho MHi. Nếu gói tin “ack” từ CSN là
rỗng, nghĩa là trong vùng khơng có dữ liệu cần thiết. MHi sẽ gửi gói tin yêu cầu đến các
MHa bên cạnh. Tiếp tục lại thao tác tìm kiếm tại MHa tương tự như tại MHi cho đến khi
tìm thấy dữ liệu và MH đích sẽ gửi dữ liệu ngược lại về cho MHi theo đường định tuyến
đã hình thành trong quá trình tìm kiếm (tuy nhiên cơng trình nghiên cứu [2] khơng nêu rõ

đến khi nào sẽ yêu cầu lên máy chủ). Dữ liệu hồi đáp bao gồm các thông tin: chỉ mục dữ
liệu, dữ liệu thật sự và thời gian sống của dữ liệu đó.
Chiến lược lưu trữ dữ liệu: khi nhận được dữ liệu, việc đầu tiên MHi sẽ lưu trữ
trên bộ nhớ cục bộ của chính nó, nếu khơng gian bộ nhớ khơng đủ chỗ, MHi sẽ loại bỏ
một hạng mục dữ liệu có giá trị utility thấp nhất. Nếu vẫn khơng đủ chỗ, thì MHi sẽ gửi
thơng tin lên CSN để được nhận về địa chỉ của MH có khơng gian bộ nhớ đủ chỗ để lưu
trữ. Nếu nhận được địa chỉ của MH có đủ khơng gian lưu trữ thì MHi sẽ di chuyển dữ liệu
đến MH đó, nếu khơng có MH nào thỏa thì dữ liệu bị loại bỏ.
Chiến lược thay thế dữ liệu bằng LUV-Mi (Lest Utility Value with Migration).
Thuật tốn MHV-Mi bao gồm 2 khung xử lý chính: thay thế và di chuyển để chọn ra dữ
liệu cần thay thế dựa vào 4 yếu tố chính:
Popularity: dựa vào tần suất truy cập của dữ liệu. Tần suất truy cập dữ liệu của một di
được cho bởi công thức sau:

Với ai là tỷ lệ truy cập vào một dữ liệu di, N là tổng số dữ liệu trên cơ sở dữ liệu, ai được
tính theo cơng thưc sau:

Với K là số lần truy cập vào dữ liệu di, tc là lần truy cập hiện tại, tik là nhãn thời gian truy
cập cũ nhất.
12


Distance: б là khoảng cách tính theo số lượng bước nhảy từ MH chứa dữ liệu và MH yêu
cầu.
Coherency: TTLi thể hiện thời gian sống của một hạng mục dữ liệu.
Size: kích thước dữ liệu (S)
Vậy cơng thức tổng qt để tính khi thay thế dữ liệu:

Cơng trình nghiên cứu [2] đã tối ưu được không gian bộ nhớ cục bộ (không trùng
lắp dữ liệu). Dùng cộng tác theo vùng để tăng khả năng cộng tác chia sẽ dữ liệu. Chiến

lược thay thế dữ liệu LUV-Mi hiệu quả. Mục tiêu chính của cơng trình nghiên cứu là
giảm khả năng trùng lắp dữ liệu và cung cấp môi trường cộng tác tốt hơn. Tuy nhiên,
trong thực tế việc chia các vùng mạng thành các ô vuông nhỏ là vấn đề rất phức tạp và
khó thực hiện được. Bên cạnh đó, trong môi trường mạng không dây, khả năng mất kết
nối cao, việc sử dụng CSN lưu giữ thông tin bộ nhớ cục bộ của các MH là không hợp lý,
khi CSN mất kết nối, dẫn đến tất cả các MH trong vùng quản lý của CSN cũng mất kết
nối theo. Hơn nữa, các MH ln ln hạn chế khả năng tính tốn và khơng gian lưu trữ,
cơng trình nghiên cứu khơng đề cập đến vấn đề tổ chức cấu trúc dữ liệu lưu trữ như thế
nào.

6) Chiến lược lưu trữ cộng tác dữ liệu theo nhóm (GroupCaching)
Các điểm hạn chế của cơng trình nghiên cứu [2] được giải quyết trong cơng trình
nghiên cứu [1] của nhóm tác giả Yi-Wei Ting. Trong mơi trường mạng khơng dây, một
MH có thể giao tiếp các MH bất kì ở mọi nơi và bất cứ lúc nào. Kỹ thuật lưu trữ cộng tác
dữ liệu có thể tăng khả năng truy cập dữ liệu. Tuy nhiên, các MH thường xuyên di
chuyển, bên cạnh đó sự giới hạn về băng thông và năng lượng tiêu thụ dẫn đến tỉ lệ có dữ
liệu trong vùng thấp và thời gian truy vấn dữ liệu tăng cao. Cơng trình nghiên cứu [1] đề
ra kỹ thuật quản lý chia sẻ cộng tác dữ liệu theo nhóm, cho phép các MH trao đổi thông
tin liên lạc với nhau qua một bước nhảy. Với việc sử dụng kĩ thuật GroupCaching, thông
tin trạng thái bộ nhớ cục bộ được trao đổi và duy trì trong nhóm sau mỗi chu kỳ, các MH
biết được trạng thái bộ nhớ của nhau vì vậy giảm được sự dư thừa dữ liệu, tăng hiệu quả
không gian bộ nhớ cục bộ. Với kỹ thuật này chi phí về thời gian truy xuất dữ liệu và lưu
trữ dữ liệu hiệu quả hơn.

13


Mỗi MH có một mã nhóm (mã nhóm có thể là địa chỉ IP hoặc mã host). Để duy trì
tính kết nối trong nhóm, thơng điệp “Hello” sẽ được trao đổi theo định kỳ giữa các MH.
Bằng cách này, mỗi MH biết được các MH nào nằm trong phạm vi giao tiếp hay nói cách

khác biết được những MH nào thuộc nhóm của nó.
Để ghi nhận thơng tin trạng thái bộ nhớ cục bộ của các MH trong nhóm, tại mỗi
MH lưu trữ hai bảng {self_table và group_table} lưu trữ thơng tin của chính nó và thơng
tin của các MH trong nhóm. Nội dung mỗi bảng được trình bày trong Bảng 1-2:
Bảng 1-2. Cấu trúc lưu trữ tại mỗi MH
self_table = {cache data Id, cache data item, datasource Id, times stamp}
group_table={cache data id, data source id, group member id, times tamp}
Bảng self_table lưu trữ thông tin bộ nhớ cục bộ tại chính MH đó, thơng tin
seft_table được cập nhật khi có sự lưu trữ dữ liệu tại MH. Trong khi đó bảng group_table
lưu trữ thơng tin bộ nhớ cục bộ của các MH khác trong nhóm tại MH đang xét, thông tin
group_table được cập nhật khi MH nhận thông tin cập nhật trạng thái bộ nhớ từ các MH
thành viên trong nhóm. Nếu một MHA khơng nhận được thơng điệp “Hello” từ MHI bất
kỳ trong nhóm trong một khoảng chu kỳ thời gian, nghĩa là MHI đã rời khỏi nhóm hoặc
tắt nguồn. Lúc này, thông tin group_table của MHA cần được cập nhật lại bằng cách xóa
đi những thơng tin liên quan đến MHI. Từ group_table, một MH biết được hạng mục dữ
liệu được lưu trữ tại MH nào trong nhóm, khi có yêu cầu dữ liệu, MH nguồn có thể tìm
kiếm thơng tin dữ liệu trong seft_table và group_table để truy hồi dữ liệu tồn tại, chính vì
vậy tỉ lệ có dữ liệu sẽ tăng lên và thời gian truy vấn sẽ giảm xuống.

Hình 1-6. Nhóm của MHD
Trong Hình 1-6 mơ tả nhóm của MH D và các MH thành viên trong nhóm {C, E, G
và H}. Trong chu kỳ thời gian, MH D gửi thông tin trạng thái bộ nhớ cục bộ của chính nó
đến các MH {C, E, G và H} và ngược lại các MH {C, E, G và H} cũng gửi thông tin bộ
nhớ đến MH D. Vì vậy, khi một yêu cầu dữ liệu được trả về cho MH D, MH D có thể lưu
trữ dữ liệu hoặc kiểm tra không gian bộ nhớ cục bộ của các MH {C, E, G và H} để lưu
trữ dữ liệu khi bộ nhớ cục bộ của nó đầy.
14


Để nhận biết được sự tồn tại của các MH trong nhóm, sau mỗi khoảng chu kỳ thời

gian nhất định, giữa các MH trong nhóm có sự trao đổi thơng tin trạng thái bộ nhớ cục bộ
với nhau. Đồng thời các MH trong xử lý cập nhật thông tin bộ nhớ từ các MH trong
nhóm. Thơng tin trạng thái bộ nhớ cục bộ bao gồm: {Group member Id, cache data Id,
time stamp, remaing availible cache space}.
Cơ chế hoạt động: khi yêu cầu dữ liệu được phát ra, đầu tiên MH nguồn kiểm tra
thơng tin self_table có tồn tại dữ liệu khơng. Nếu có (cache hit), dữ liệu sẽ được trả về
cho người dùng, ngược lại nếu dữ liệu khơng tìm thấy trong self_table thì MH nguồn tiếp
tục kiểm tra thơng tin trong bảng group_table xem có dữ liệu yêu cầu hay khơng. Nếu có,
MH nguồn gửi u cầu đến MH đích trong nhóm để truy hồi và đợi dữ liệu được trả về
(remote cache hit). Nếu dữ liệu yêu cầu khơng tìm thấy trong self_table lẫn group_table
thì MH nguồn sẽ tiếp tục qua trình tìm kiếm sang các MH ngồi nhóm. Để có thể yêu cầu
dữ liệu từ các MH ngồi nhóm, MH nguồn phải xây dựng đường đinh tuyến từ MH
nguồn đến MH đích bằng cách gửi yêu cầu dữ liệu đến MH kế tiếp trên đường đi từ MH
nguồn đến MH đích.
Bảng 1-3. Xử lý tại MH trung gian trên đường định tuyến
Khi một yêu cầu dữ liệu di đến MH nằm trên đường định tuyến
1. Nếu dữ liệu tồn tại trong seft_table
Gửi dữ liệu di đến MH nguồn
2. Ngược lại nếu thông tin dữ liệu tồn tại trong group_table
Gửi yêu cầu dữ liệu đến MH trong nhóm có chứa dữ liệu di
3. Ngược lại
Tiếp tục chuyển đến MH kế tiếp trên đường định tuyến
Trong Bảng 1-3, khi MH trung gian trên đường định tuyến nhận yêu cầu dữ liệu, nó
cũng xử lý tương tự như tại MH nguồn, nếu dữ liệu vẫn khơng tìm thấy thì u cầu dữ
liệu sẽ được chuyển đến MH kế tiếp trên đường định tuyến đến MH đích.Nếu MH đích
nhận được yêu cầu, dữ liệu hồi đáp sẽ được trả về theo đường định tuyến đã được xây
dựng trong quá trình tìm kiếm. Khi MH trung gian trên đường định tuyến nhận được dữ
liệu trả về từ MH đích, dữ liệu đó sẽ được lưu trữ vào bộ nhớ cục bộ, nếu bộ nhớ cục bộ
đầy, MH trung gian sẽ xóa những hạng mục dữ liệu không hợp lệ để thay bằng dữ liệu
mới. Thuật toán xử lý lưu trữ và thay thế được trình bày trong phần tiếp theo.

Thuật tốn xử lý lưu trữ và thay thế dữ liệu trong bộ nhớ cục bộ: trong phần
này, chúng tơi sẽ trình bày thuật toán xử lý lưu trữ khi MH nguồn truy xuất dữ liệu từ MH
đích được mơ tả trong Bảng 1-4.
15


Bảng 1-4. Xử lý lưu trữ tại MH nguồn
(A) Khi dữ liệu di được trả về MH nguồn hoặc MH trung gian trên đường định
tuyến
1. Nếu dữ liệu đã tồn tại trong seft_table hoặc group_table
Khơng lưu di
2. Ngược lại
Thuật tốn lưu trữ di
(B) Thuật tốn lưu trữ di
1. Nếu khơng gian lưu trữ cịn lại của bộ nhớ > kích thước dữ liệu di
Lưu trữ di vào bộ nhớ cục bộ
Thốt
2. Ngược lại nếu khơng gian lưu trữ cịn lại của nhóm > kích thước di
Lưu di tại một MH bất kì trong nhóm
Thốt
3. Ngược lại tìm kiếm di trong group_table
3.1. Nếu có
Khơng lưu di
3.2. Ngược lại
Chọn một MH thích hợp trong nhóm
Chuyển dữ liệu đến MH được chọn để lưu trữ
Dựa trên thông tin cập nhật trạng thái bộ nhớ cục bộ, mỗi MH biết được thông tin
không gian bộ nhớ các của các MH khác trong nhóm như chỉ mục dữ liệu hay nhãn thời
gian (thời gian dữ liệu được cập nhật sau cùng). Đầu tiên, khi MH nguồn nhận về một
hạng mục dữ liệu, dữ liệu sẽ được lưu trữ vào bộ nhớ khi không gian bộ nhớ cục bộ còn

trống. Ngược lại, MH nguồn sẽ kiểm tra thông tin bộ nhớ cục bộ của các MH trong nhóm,
nếu khơng gian bộ nhớ trong nhóm chưa đầy, MH nguồn sẽ chuyển dữ liệu đến một MH
bất kì trong nhóm. Nếu khơng gian bộ nhớ trong nhóm khơng đủ để lưu hạng mục dữ liệu
đó thì MH nguồn sẽ kiểm tra trong group_table để xem dữ liệu đó đã tồn tại trong nhóm
chưa, nếu có thì dữ liệu sẽ không được lưu, ngược lại MH nguồn chọn một MH thích hợp
nhất chứa dữ liệu có nhãn thời gian lâu nhất để lưu dữ liệu. Khi đó, tại MH được chọn sẽ
tiến hành thuật toán thay thế dữ liệu LRU nhằm tăng không gian bộ nhớ cho đến khi dữ
liệu mới được thêm vào.
Cơng trình nghiên cứu [1] đưa ra được cấu trúc lưu trữ dữ liệu, giải quyết vấn đề
cộng tác kho lưu trữ dữ liệu theo nhóm, giảm độ dư thừa dữ liệu trong bộ nhớ vốn rất hạn
16


chế về kích thước và tăng độ phổ biến dữ liệu trong nhóm từ đó tăng khả năng truy cập
dữ liệu nhờ khả năng cộng tác của các MH thành viên trong nhóm. Tuy nhiên, cơng trình
nghiên cứu sử dụng thuật tốn tìm kiếm dữ liệu bằng cách “phát thơng điệp ngập lụt”
(flooding broadcast) trong hệ thống nên chi phí cho tìm kiếm rất cao, có thể làm tăng thời
gian hồi đáp và hao tốn nhiều năng lượng nếu dữ liệu khơng nằm trong vùng dịch vụ, do
đó cơng trình nghiên cứu chưa có một kỹ thuật định tuyến tìm kiếm dữ liệu ngồi nhóm
rõ ràng khi trong nhóm khơng có dữ liệu. Hơn nữa, tại mỗi khoảng chu kỳ thời gian, các
MH phải xử lý cho việc gửi thông tin duy trì nhóm và xử lý cập nhật thơng tin trong
nhóm, như vậy rất hao tốn năng lượng khi mà năng lượng tiêu thụ của các MH luôn luôn
hạn chế trong môi trường mạng không dây.

7) Một hướng tiếp cận khác cho giải pháp cộng tác kho lưu trữ (Proactive
Caching)
Cơng trình nghiên cứu [1] cũng chưa giải quyết được vấn đề di chuyển khi các MH
ra khỏi nhóm cộng tác hoặc tham gia vào một nhóm mới. Cơng trình nghiên cứu [7] của
nhóm tác giả Prashant Kumar đã giải quyết được vấn đề di chuyển của các MH và đưa ra
một chiến lược thay thế dữ liệu hiệu quả. Trong cơng trình nghiên cứu này, mỗi MH

trong mơ hình mạng có khả năng chia sẻ nội dung bộ nhớ cục bộ của chính nó với các
MH lân cận. Khi một MH cập nhật bộ nhớ cục bộ, sẽ phát tín hiệu cập nhật này đến tất cả
các MH trong vùng. Mỗi MH sẽ lưu một bảng thông tin lưu trữ (CIT). Bảng CIT chứa n
hạng mục dữ liệu , mỗi hạng mục dữ liệu d có 4 trường:
d.available: có giá trị TRUE/FALSE cho biết dữ liệu d hiện tại có trong kho lưu trữ hay
khơng.
d.nnode: cho biết MH lân cận có chứa dữ liệu u cầu hay khơng.
d.accesscount : sô lần truy cập dữ liệu d.
d.TTL : thời gian sống của dữ liệu d.
Tìm kiếm dữ liệu d: ban đầu MH nguồn sẽ tìm trong bộ nhớ cục bộ, kiểm tra
d.available là đúng hay sai, nếu sai thì MH nguồn sẽ kiểm tra d.nnode để biết dữ liệu có
lưu trong các MH lân cận hay khơng. Nếu có thì yêu cầu sẽ được gửi đến các MH lân cận,
ngược lại thì chuyển hướng tìm kiếm về phía máy chủ. Trên đường định tuyến, các MH
trung gian cũng lặp lại quá trình tìm kiếm giống như tại MH nguồn. Nếu dữ liệu được tìm
thấy tại MH trung gian trên đường định tuyến thì yêu cầu tìm kiếm kết thúc, ngược lại thì
yêu cầu được gửi lên BS.
17


Tính di chuyển: khi MH gia nhập vùng mới, nó sẽ gửi thơng tin kho lưu trữ của
chính MH đó đến tất cả các MH trong vùng. Khi MH rời khỏi vùng thì nó sẽ phát một
thơng điệp “LEAVE” đến tất cả các MH trong vùng. Các MH trong vùng sẽ dựa vào các
tiêu chuẩn sau để quyết định lưu dữ liệu của MH rời hay không. Đầu tiên các MH sẽ kiểm
tra kho lưu trữ của nó, nếu có các MH sẽ kiểm tra CIT để xem dữ liệu đã có ở các MH
trong vùng lân cận của nó hay khơng, nếu có thì sẽ khơng lưu. Trong trường hợp ngược
lại thì dữ liệu này sẽ được lưu trữ bởi một MH bất kì trong vùng. Nếu MH khơng đủ
khơng gian trống thì nó sẽ sử dụng thuật tốn thay thế kho lưu trữ để có khơng gian lưu
dữ liệu mới
Chiến lược thay thế dữ liệu: khi bộ nhớ khơng đủ khơng gian lưu trữ thì ta sẽ
chọn một bộ dữ liệu d có d.accesscount lớn nhất để thay thế nhằm tránh tình trạng dư

thừa dữ liệu trong vùng. Nếu một hạng mục dữ liệu không được truy cập trong vùng thì
khi đó ta sẽ kiểm tra giá trị thời gian sống của đơn vị dữ liệu (TTL: time-to-live) của nó
có hết hạn hay chưa, khi đó dữ liệu sẽ bị xóa khỏi kho lưu trữ.
Cơng trình nghiên cứu [7] giải quyết được trường hợp khi MH rời khỏi vùng hay
gia nhập một vùng mới, sử dụng thuật toán thay thế kho lưu trữ hiệu quả. Tuy nhiên giải
pháp chỉ dừng lại ở mức ý tưởng, tác giả chưa thực nghiệm để kiểm tra độ hiệu quả của
kiến trúc.

1.1.2 So sánh đánh giá các giải pháp cộng tác dữ liệu
Với các cơng trình nghiên cứu được tìm hiểu ở trên, chúng tôi lập bảng so sánh độ
hiệu quả của các giải pháp dựa trên khả năng chúng khắc phục được những yếu tố hạn
chế trong môi trường HTTT DĐ.
Bảng so sánh đánh giá các giải pháp
Tiêu chí
đánh giá
các giải
pháp
Thay thế
dữ liệu
Lưu trữ
dữ liệu
Thời gian
đáp ứng
Định
tuyến

2004
[4]
CacheData,
CachePath,

CacheHybrid

X
(CacheData,
CacheHybrid)

2004
[3], [5]

2005
[6]

2006
[2]

2007
[1]

2010
[7]

COCA

DGCOCA

Cluster

GroupCaching

Proactive


X

X

X

X

X

X

X

X

X

X

X

X

X

X

X


X

X

X
18


Cấu trúc
dữ liệu
lưu trữ

X

X

Dựa vào bảng so sánh độ hiệu quả các cơng trình nghiên cứu trên, chúng tơi đưa ra
các đánh giá tổng quát về các giải pháp này.
Bảng nhận xét tổng quát
Ưu điểm

[4]

Khuyết điểm

CacheData
Chiến lược lưu trữ dữ liệu tại
MH trung gian trên đường
định tuyến.

Chi phí xử lý thấp.
CachePath
Chiến lược lưu trữ đường
định tuyến từ MH nguồn đến
MH đích
Chi phí xử lý thấp
HybridCache
Khắc phục nhược điểm của
của CacheData, CachePath.
Chi phí xử lý thấp.

Gây lãng phí kho lưu trữ
Khơng có cấu trúc dữ liệu lưu
trữ

COCA
Truy vấn dữ liệu hiệu quả
hơn.
Giảm thời gian hồi đáp.
[3],
[5]

[6]

[2]

DGCOCA
Xử lý khi MH mất kết nối.
Xử lý lưu trữ dữ liệu.
Thay thế dữ liệu khi bộ nhớ

đầy.
CLUSTER
Chia các MH theo vùng, tìm
kiếm theo vùng.
Lưu trữ dữ liệu hiệu quả làm
tối ưu không gian bộ nhớ.
Giảm số lượng thông điệp.
Tăng khả năng cộng tác chia
sẻ dữ liệu.
Đưa ra công thức thay thế dữ
19

Quản lý kho
lưu trữ
Thay thế
Đồng bộ

Khơng phù hợp với mơ hình
mạng thường xun thay đổi.
Khơng có cấu trúc dữ liệu
lưu trữ

Thay thế
Đồng bộ

Khơng có tính cộng tác chia
sẻ dữ liệu theo nhóm.
Khơng có cấu trúc dữ liệu lưu
trữ


Thay thế
Đồng bộ

Chi phí xử lý cao.
Khơng đề cập đến vấn mất kết
nối.
Khơng có hướng giải quyết
trong trường hợp bộ nhớ đầy.
Không đề cập vấn đề định
tuyến.
Không có cấu trúc dữ liệu lưu
trữ

Khám phá
Lưu trữ

Chi phí xử lý cao.
Khơng đề cập vấn đề định
tuyến.
Khơng có cấu trúc dữ liệu lưu
trữ.

Khám phá
Lưu trữ
Thay thế
Đồng bộ

Chi phí xử lý cao.
Phụ thuộc vào CSN, CSN mất
kết nối dẫn đến các MH trong

vùng quản lý của CSN cũng
mất thơng tin.
Khơng có cấu trúc dữ liệu lưu
trữ

Khám phá
Lưu trữ
Thay thế
Đồng bộ


[1]

[7]

liệu hiệu quả
Xây dựng đường định tuyến.
GROUPCACHING
Khắc phục được nhược điểm
của Cluster (khơng dùng
CSN).
Có tổ chức cấu trúc dữ liệu rõ
ràng.
Chia các MH theo nhóm.
Tối ưu khơng gian bộ nhớ.
Tăng khả năng có dữ liệu
trong vùng cộng tác
Giảm thời gian truy vấn
Thay thế dữ liệu dựa trên
LRU, TTL.

Xây dựng đường định tuyến.
Proactive approach
Giải quyết vấn đề di chuyển
giữa các MH
Có tổ chức cấu trúc dữ liệu
Sử dụng thuật toán thay thế
dữ liệu hiệu quả (tốt hơn
LRU, …)
Xây dựng đường định tuyến.

Chi phí duy trì nhóm cao, tốn
năng lượng tiêu thụ.
Sử dụng thuật tốn loang mù
sang các MH ngồi vùng khi
trong vùng khơng có dữ liệu
Chưa giải quyết được vấn đề
di chuyển của các MH (ra
khỏi nhóm, tham gia nhóm
mới)

Khám phá
Lưu trữ
Thay thế
Đồng bộ

Chi phí xử lý cao.
Sử dụng thuật tốn loang mù
sang các MH ngồi vùng khi
trong vùng khơng có dữ liệu
Chưa có cài đặt thực nghiệm


Khám phá
Thay thế
Đồng bộ

1.2 Một số chiến lược nhất quán dữ liệu
1.2.1 Sơ lược các cơng trình nghiên cứu liên quan đến phương pháp
nhất quán dữ liệu trong môi trường di động
1) Kỹ thuật gom nhóm dữ liệu
Ý tưởng của kỹ thuật gom nhóm dữ liệu động (Dynamic Group Caching - DGC) [14]
của nhóm tác giả Jinbao Li là mỗi nhóm chỉ có một MH chủ và nhiều MH thành viên.
Mỗi MH chủ đi đến các MH thành viên trong nhóm thơng qua một bước nhảy và mỗi MH
chỉ thuộc về một nhóm. Các thành viên trong nhóm có thể giao tiếp với nhau thơng qua
MH chủ. Các nhóm xung quanh giao tiếp với nhau thông qua MH trung gian. Trong kỹ
thuật này, chỉ số bộ nhớ được chia thành 2 mức: chỉ số bộ nhớ nút (index node) duy trì ở
client và chỉ số bộ nhớ nhóm (index group) duy trì ở nút quản lý nhóm. Khi một MH cần
tìm kiếm dữ liệu, MH sẽ truy xuất dữ liệu từ các MH khác trong nhóm hoặc gửi yêu cầu
đến các MH từ xa dựa vào MH chủ của nó. Như vậy, theo tác giả, chi phí về thời gian truy
xuất và quản lí dữ liệu sẽ hiệu quả hơn. Đồng thời, chi phí về truyền thông giữa các MH
cũng được cải thiện. Tuy nhiên, nếu một dữ liệu khơng được tìm thấy trong nhóm hoặc
trong nhóm khác thì bài báo chưa đưa ra giải pháp cụ thể để giải quyết vấn đề này. Ngoài
20


ra, chúng tôi nhận thấy trong kỹ thuật này, MH chủ đóng vai trị quan trọng trong việc
quản lí thơng tin dữ liệu, hỗ trợ, chia sẻ dữ liệu giữa các thành viên trong nhóm; tuy nhiên,
trong HTTT DĐ, các MH thường xuyên di chuyển dẫn đến thường xuyên xảy ra mất kết
nối giữa MH chủ và các MH thành viên; vì vậy, việc để các MH khác phụ thuộc nhiều vào
MH chủ sẽ mang lại hiệu quả không cao.
Cũng với kỹ thuật gom nhóm dữ liệu, ở cơng trình nghiên cứu [1], tác giả Yi-Wei

Ting đưa ra kỹ thuật Group Caching – GC. Trong đó, các client lân cận (trong phạm vi
một bước nhảy) tạo thành một nhóm các client thông qua cơ chế sử dụng thông điệp xin
chào (Hello). Thông điệp này sẽ được gửi một cách định kì giữa các client với nhau như tín
hiệu cho biết client vẫn còn tồn tại (Keep-Alive-Signal). Mỗi client sẽ biết được tình trạng
bộ nhớ (Caching Status) của các client lân cận trong nhóm mình. Và định kì, client cũng sẽ
gửi thơng tin tình trạng bộ nhớ của mình đến thành viên trong nhóm. Tại mỗi client lưu trữ
2 bảng: self_table, group_table có cấu trúc như sau:
Self_table={cache data Id, cache data item, data source Id, times stamp}
Group_table ={cache data Id, cache data item, group member Id, times stamp}
Bảng self_table giữ thông tin bộ nhớ nội bộ của chính MH đó. Bảng group_table giữ
thông tin bộ nhớ của các MH khác trong phạm vi một bước nhảy từ MH đang xét. Do đó,
trong cấu trúc này khơng tồn tại MH chủ. Khi một MH A cần đồng bộ dữ liệu, nó sẽ kiểm tra
tình trạng bộ nhớ của mỗi thành viên trong nhóm để tìm dữ liệu đồng bộ. Nếu một u cầu
dữ liệu khơng được tìm thấy trong bộ nhớ của các thành viên trong nhóm, MH A sẽ dựng
đường định tuyến từ nó đến nguồn dữ liệu (Data Source), và yêu cầu dữ liệu sẽ được chuyển
đến MH kế tiếp trên đường định tuyến đó. Sau đó, MH kế tiếp này lại tìm dữ liệu trong tình
trạng bộ nhớ của mình và trong tình trạng bộ nhớ của các thành viên khác trong nhóm; nếu
u cầu dữ liệu vẫn khơng được tìm thấy, MH này lại phát sinh đường định tuyến mới, yêu
cầu dữ liệu sẽ tiếp tục được chuyển đi.
Do đó, theo tác giả thì so với kỹ thuật CacheData, kỹ thuật này có số bước nhảy và
độ trễ trung bình giảm, cải thiện tỉ lệ sử dụng bộ nhớ do tận dụng được khơng gian lưu trữ
trong nhóm và giảm tỉ lệ gửi câu truy vấn lên kênh uplink. Nếu dữ liệu được tìm thấy trong
nhóm thì thao tác tìm kiếm và đồng bộ dữ liệu rất nhanh. Tuy nhiên, nếu dữ liệu cần tìm
kiếm, đồng bộ khơng được tìm thấy trong nhóm thì thuật tốn lại lan truyền ra bên ngoài
dựa vào đường định tuyến mà tác giả lại không đề cập rõ giải pháp định tuyến.

2) Một hướng tiếp cận dựa trên hai lược đồ ABI+HCQU và SWRCC+MHVI
Một hướng tiếp cận khác cho việc đồng bộ dữ liệu là kỹ thuật đồng bộ dựa trên hai
lược đồ ABI+HCQU và SWRCC+MHVI, của nhóm tác giả Po-Jen Chuang và Yu-Shian


21


Chiu [13]. Trong đó, lược đồ ABI+HCQU giải quyết cho vấn đề đồng bộ dữ liệu giữa
client và server, còn lược đồ SWRCC+MHVI phục vụ cho việc đồng bộ sau khi xảy ra mất
kết nối củaclient với server. Với kỹ thuật này, các tiêu chí về thời gian truy cập dữ liệu, tỉ
lệ không sử dụng bộ nhớ và sự tiêu thụ băng thông được xem xét đến. Ở lược đồ
SWRCC+MHVI, nhóm tác giả đã giải quyết khá nhiều trường hợp mất kết nối sát với thực
tế và đạt được một số tiêu chí mà tác giả đưa ra. Các thông điệp được tác giả sử dụng trong
lược đồ này là: mất kết nối (Sleep), kết nối lại (Wakeup), phục hồi (Recovery), kiểm tra
(Check) và xác nhận (Confirm).
Trong bối cảnh đưa ra, tác giả giải quyết hai tình huống mất kết nối sau: mất kết nối
chủ động và mất kết nối bị động. Ở trường hợp mất kết nối chủ động, trước khi ngắt kết
nối, client gửi thông điệp Sleep tới server. Sau khi kết nối trở lại, client gửi thông điệp
Wakeup và nhận lại từ server thông điệp Recovery (bao gồm những dữ liệu bị cập nhật
trong khoảng thời gian client khơng cịn kết nối). Client dùng thơng tin này để cập nhật lại
bộ nhớ của mình. Trong trường hợp này, gần như ngay khi kết nối trở lại thì client đã có
thể cập nhật lại dữ liệu, và trạng thái của mỗi đơn vị dữ liệu là hợp lệ. Còn với trường hợp
mất kết nối bị động, client mất kết nối đột ngột và không kịp thông báo với server.
Giả định client A mất kết nối đột ngột và không kịp thông báo cho server trước khi
mất kết nối; khi kết nối trở lại, A sẽ đánh dấu tồn bộ dữ liệu ở trạng thái khơng chắc chắn
(Uncertain) và sẽ xin cập nhật dữ liệu từ các client lân cận. A gửi thông điệp Check chứa
danh sách định danh (id) và nhãn thời gian của các dữ liệu tới tất cả client lân cận theo chu
kì kiểm tra (Check period) bằng 1/4 hoặc 1/5 chu kì đồng bộ của server. Client lân cận nào
đó nhận được thơng điệp Check từ A sẽ phản hồi thông điệp Confirm (gồm những dữ liệu
trong Check mà nó có lưu trữ và hợp lệ) tới A và những client lân cận khác. Những client
lân cận cịn lại khi nhận được thơng điệp Check và Confirm sẽ tìm trong dữ liệu của mình
những dữ liệu hợp lệ có trong thơng điệp Check mà khơng có trong thơng điệp Confirm.
Client này cũng tạo thơng điệp Confirm bao gồm các dữ liệu tìm được rồi gửi tới A và
những client lân cận khác. Sau khi nhận được những dữ liệu phản hồi từ các client lân cận,

A sẽ thay đổi trạng thái dữ liệu từ không chắc chắn sang trạng thái thay đổi(Modified) và
đợi đến chu kì phát thơng báo dữ liệu mất hợp lệ (IR1) kế tiếp của server để xác nhận lại
tính hợp lệ. Dữ liệu sẽ được chuyển sang trạng thái hợp lệ (Valid) nếu còn hợp lệ và ngược
lại sẽ chuyển sang trạng thái mất hợp lệ (Invalid). Khi đó, dữ liệu tại client A đã được đồng
bộ với các client khác. Bởi vì việc trao đổi dữ liệu trong trường hợp này chủ yếu diễn ra

1

Invalidation Reports
22