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

Đây là Khóa luận tốt nghiệp ngành CNTT


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.


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.


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 55 thô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


Khóa luận gồm 76 trang