Luận Văn Tìm kiếm ngẫu nhiên trên các mạng ngang hàng phi cấu trúc

TÓM TẮT NỘI DUNG
Trong các mô hình client-server, mô hình mạng ngang hàng tập trung hay mô hình
mạng ngang hàng lai ghép, nếu một người dùng ởtrong mạng sửdụng máy tính đểtìm
kiếm tài nguyên thì việc tìm kiếm là đơn giản bởi sựhỗtrợcủa server hoặc siêu điểm nút.
Tuy nhiên, với mô hình mạng ngang hàng thuần túy việc tìm kiếm lại không đơn giản, đó
là bởi vì điểm nút tìm kiếm không có thông tin vịtrí tài nguyên, không có thông tin định
tuyến, cũng nhưthông tin vềcác điểm nút khác trong mạng, trừcác điểm hàng xóm với
nó. Chính bởi những đặc trưng này, đã có nhiều bài báo, công trình nghiên cứu trước đây
đềxuất ra giải pháp cải tiến phương pháp tìm kiếm đơn lẻhay đềxuất phương pháp tìm
kiếm kết hợp như là: phương pháp tìm kiếm động [20], phương pháp tìm kiếm lai
[14], Ngoài ra còn có những đềxuất đểcải tiến hiệu suất tìm kiếm của các phương pháp
tìm kiếm đơn lẻnhưtrong các tài liệu [16], [17], [23].
Tuy nhiên chưa có bài báo nào đềcập đến việc kết hợp 2 phương pháp tìm đơn lẻ
theo trình tự: phương pháp di chuyển ngẫu nhiên trước và phương pháp phát tràn sau.
Khóa luận của chúng tôi đềxuất phương pháp tìm kiếm lai ghép mới từý tưởng này, sau
đó thực hiện mô phỏng các phương pháp trên một sốdạng đồthịchung của mạng ngang
hàng thuần túy. Chúng tôi cũng đưa ra các phân tích, đánh giá vềcác phương pháp tìm
kiếm.
Phương pháp của chúng tôi cho kết quảtốt trên đồthịluật hàm mũtrong một số
trường hợp, còn với tô pô phân cụm thì cho kết quả kém hơn nhưng tốt hơn so với
phương pháp phát tràn trên đồthịnày.

MỤC LỤC
Bảng ký hiệu viết tắt . 1
MỞ ĐẦU 1
CHƯƠNG 1. TỔNG QUAN VỀMẠNG NGANG HÀNG 6
1.1. Thành phần cấu tạo mạng ngang hàng 6
1.1.1. Khái niệm điểm nút 6
1.1.2. Cách phân loại peer trong mạng ngang hàng . 7
1.2. Mạng ngang hàng 8
1.2.1. Định nghĩa mạng ngang hàng 8
1.2.2. Phân loại các mô hình mạng ngang hàng . 11
1.3. Mạng xếp chồng 18
CHƯƠNG 2. LÝ THUYẾT ĐỒTHỊVÀ CÁC DẠNG ĐỒTHỊMẠNG . 19
2.1. Khái niệm đồthị 19
2.1.1. Đồthịcó hướng 19
2.1.2. Đồthịvô hướng . 19
2.1.3. Các khái niệm khác 20
2.2. Các dạng đồthịtrong mạng ngang hàng 20
2.2.1. Đồthịngẫu nhiên . 21
2.2.2. Đồthịluật hàm mũ . 21
2.2.3. Tô pô phân cụm 22
CHƯƠNG 3. CÁC PHƯƠNG PHÁP TÌM KIẾM ĐÃ ĐỀXUẤT TRƯỚC ĐÂY . 24
3.1. Các phương pháp tìm kiếm đơn lẻ 24
3.1.1. Phương pháp tìm kiếm phát tràn thông thường . 24
3.1.2. Phương pháp tìm kiếm di chuyển ngẫu nhiên 25
3.2. Các phương pháp tìm kiếm kết hợp 26
3.2.1. Phương pháp tìm kiếm động 27
3.2.2. Phương pháp tìm kiếm lai 27
CHƯƠNG 4. CÁC PHƯƠNG PHÁP TÌM KIẾM LAI GHÉP CỦA CHÚNG TÔI . 30
4.1. Phương pháp tìm kiếm lai ghép sửdụng phát tràn thông thường . 30
4.1.1. Phương pháp tìm kiếm lai ghép biến thểthứnhất . 30
4.1.2. Phương pháp tìm kiếm lai ghép biến thểthứhai . 34
4.2. Phương pháp tìm kiếm lai ghép sửdụng phát tràn cải tiến 37
4.2.1. Phương pháp tìm kiếm lai ghép biến thểthứba 38
4.2.2. Phương pháp tìm kiếm lai ghép biến thểthứtư . 41
CHƯƠNG 5. MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG 46
5.1. Các đơn vị đo hiệu năng trong mô phỏng . 46
5.1.1. Mức độbao phủ 46
5.1.2. Tỷlệthành công . 47
5.1.3. Sốlượng truy vấn thành công 47
5.1.4. Hiệu quảtruy vấn . 48
5.1.5. Sốlượng nút nhận truy vấn dưthừa . 48
5.2. Kết quảmô phỏng trên đồthịluật hàm mũ 49
5.2.1. Đồthịluật hàm mũvới 5thông báo truy vấn . 49
5.2.2. Đồthịluật hàm mũvới N thông báo truy vấn . 51
5.3. Kết quảmô phỏng trên tô pô phân cụm 53
5.3.1. Mô phỏng trên tô pô phân cụm với 55
thông báo truy vấn 53
5.3.2. Mô phỏng trên tô pô phân cụm với N thông báo truy vấn . 55
5.4. Đánh giá vềphân bốthông báo truy vấn . 61
CHƯƠNG 6. KẾT LUẬN VÀ ĐỊNH HƯỚNG 65
TÀI LIỆU THAM KHẢO 67