- 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.. - CÁC PHƯƠNG PHÁP TÌM KIẾM ĐÃ ĐỀ XUẤT TRƯỚC ĐÂY. - Các phương pháp tìm kiếm đơn lẻ. - Phương pháp tìm kiếm phát tràn thông thường. - Phương pháp tìm kiếm di chuyển ngẫu nhiên. - Các phương pháp tìm kiếm kết hợp. - Phương pháp tìm kiếm động. - Phương pháp tìm kiếm lai. - CÁC PHƯƠNG PHÁP TÌM KIẾM LAI GHÉP CỦA CHÚNG TÔI. - Phương pháp tìm kiếm lai ghép sử dụng phát tràn thông thường. - Phương pháp tìm kiếm lai ghép biến thể thứ nhất. - Phương pháp tìm kiếm lai ghép biến thể thứ hai. - Phương pháp tìm kiếm lai ghép sử dụng phát tràn cải tiến. - Phương pháp tìm kiếm lai ghép biến thể thứ ba. - Phương pháp tìm kiếm lai ghép biến thể thứ tư. - Nhưng số nút nhận thông báo truy vấn dư thừa trong phương pháp của chúng tôi là ít hơn. - Chương 3: Các phương pháp tìm kiếm đã đề xuất trước đây. - Trong chương này, chúng tôi trình bày các phương pháp tìm kiếm đã được đề xuất: Các phương pháp đơn lẻ : phương pháp phát tràn, phương pháp di chuyển ngẫu nhiên. - Các phương pháp kết hợp của 2 phương pháp đơn lẻ: phương pháp tìm kiếm động, phương pháp lai ghép.. - Chương 4: Các phương pháp tìm kiếm lai của chúng tôi. - phương pháp khác. - Và các nhận xét, đánh giá về giá trị của các phương pháp tìm kiếm đã đạt được.. - Trong mô hình mạng ngang hàng này, việc tìm kiếm file sử dụng phương pháp phát tràn (phương pháp này có sử dụng giá trị giới hạn phạm vi tìm kiếm là TTL và sử dụng GUID để trao đổi). - Vì vậy chúng tôi sẽ mô phỏng những phương pháp tìm kiếm trên những dạng đồ thị này để đánh giá xem phương pháp nào tốt, phương pháp nào tồi.. - Mô hình mạng mà khóa luận chúng tôi nghiên cứu là mô hình mạng ngang hàng thuần túy và phương pháp tìm kiếm như đã trình bày ở trên là sử dụng phương pháp phát tràn (flooding). - Ngoài phương pháp phát tràn ra, cũng có phương pháp tìm kiếm khác được sử dụng cho mô hình mạng loại này, đó là phương pháp dịch chuyển ngẫu nhiên (random walk). - Trong chương này, chúng tôi trình bày chi tiết về từng phương pháp.. - Phương pháp này thuộc nhóm phương pháp tìm kiếm mù (blind search), và trong tìm kiếm đồ thị thì phương pháp này giống với phương pháp duyệt ưu tiên theo chiều rộng (BFS).. - Ưu điểm của phương pháp. - Ngoài phương pháp phổ biến phát tràn thì việc tìm kiếm một tài nguyên ngẫu nhiên lưu trong mạng có thể sử dụng phương pháp dịch chuyển ngẫu nhiên. - dụng băng thông chung của mạng bởi các phương pháp tìm kiếm phát tràn. - Phương pháp phát tràn và phương pháp này có sự khác biệt về cơ chế tìm kiếm.. - Thông báo truy vấn sử dụng trong phương pháp này được gọi là “walker”.. - Tuy nhiên phương pháp có hạn chế đó là độ trễ thời gian tìm kiếm thấy tài nguyên cao.. - Các phương pháp này cho kết quả tốt theo hướng nghiên cứu của tác giả.. - Nếu như h ≤ n thì phương pháp tìm kiếm động thực hiện như là phát tràn để tìm kiếm hoặc là phương pháp phát tràn cải tiến.. - n thì phương pháp tìm kiếm động sử dụng di chuyển ngẫu nhiên để tìm kiếm. - Phương pháp này được đề xuất bởi Reza, Alejandro, và Pawel [14]. - Như vậy, trong chương này chúng tôi đã giới thiệu về phương pháp tìm kiếm trước đây đã được sử dụng và các phương pháp đã được đề xuất cho mô hình mạng ngang hàng thuần túy. - Và chúng tôi gọi các phương pháp lai ghép mới này là các biến thể tìm kiếm.. - Phương pháp tìm kiếm lai ghép biến thể thứ nhất 4.1.1.1. - Ý tưởng của phương pháp. - Mô tả tìm kiếm cho phương pháp di chuyển ngẫu nhiên Mô tả tìm kiếm cho phương pháp phát tràn. - Hình 5.Phương pháp tìm kiếm lai ghép biến thể thứ nhất.. - Sau các chặng, các nút truy vấn bằng phương pháp di chuyển ngẫu nhiên chưa tìm kiếm thấy file, ta thực hiện tiếp phương pháp phát tràn từ nút E.. - Mã giả của phương pháp. - Do đó mã giả cho phương pháp như sau:. - /*Thực hiện phương pháp di chuyển ngẫu nhiên trước*/. - /*Thực hiện phương pháp phát tràn với lượng thông báo truy vấn còn lại*/. - Lấy tuần tự các đỉnh ra khỏi hàng đợi, bắt đầu từ đỉnh cuối cùng, khác rỗng của phương pháp tìm kiếm di chuyển ngẫu nhiên ở trên;. - Phương pháp tìm kiếm lai ghép biến thể thứ hai 4.1.2.1. - Phương pháp tìm kiếm lai ghép biến thể thứ hai.. - Lấy tuần tự các đỉnh ra khỏi hàng đợi, bắt đầu từ đỉnh đầu tiên của phương pháp tìm kiếm di chuyển ngẫu nhiên ở trên;. - Do sử dụng phương pháp phát tràn cổ điển để tìm kiếm thì việc phát tràn sẽ gây ra lượng dư thừa thông báo truy vấn không cần thiết. - Phương pháp tìm kiếm lai ghép biến thể thứ ba 4.2.1.1. - Về mặt ý tưởng thì giống như ý tưởng của phương pháp tìm kiếm lai ghép biến thể thứ nhất nhưng chỉ khác cách thức thực hiện của phương pháp phát tràn. - Hình 7.Phương pháp tìm kiếm lai ghép biến thể thứ ba.. - Sau khi đã thực hiện phương pháp di chuyển ngẫu nhiên như trong ví dụ của phương pháp tìm kiếm biến thể thứ nhất, điểm nút E là điểm nút cuối cùng. - Phương pháp tìm kiếm lai ghép biến thể thứ tư 4.2.2.1. - Có thể mô tả hoạt động của phương pháp tìm kiếm lai ghép biến thể thứ tư như sau:. - Trước khi thực hiện phương pháp phát tràn cải tiến thì việc thực hiện di chuyển ngẫu nhiên tương tự như trong mô tả về phương pháp tìm kiếm lai ghép biến thể thứ hai.. - Hình 8.Phương pháp tìm kiếm lai ghép biến thể thứ tư.. - Mã giả trong phương pháp này chỉ thêm một chút so với phương pháp tìm kiếm lai ghép biến thể thứ hai trong phần thực hiện phát tràn.. - Trong chương này, chúng tôi tiến hành mô phỏng các phương pháp tìm kiếm đã nêu trên từng dạng đồ thị đã giới thiệu. - Mức độ bao phủ của phương pháp tìm kiếm là tổng số các điểm nút mà phương pháp có thể tìm được (bao gồm cả các nôt có chứa file cần tìm và nút không chứa).. - Rõ ràng giá trị của v 0 càng nhỏ thì phương pháp tìm kiếm càng tốt Ký hiệu cho tham số này là : C – Coverage.. - Tham số phản ánh về khía cạnh nhược điểm của phương pháp tìm kiếm.. - Các cột tiếp theo là các giá trị tương ứng với tham số độ đo của 1 phương pháp tìm kiếm. - Ký hiệu mà chúng tôi quy ước cho phương pháp phát tràn là F (Flooding search), phương pháp di chuyển ngẫu nhiên là R (Random walk search), phương pháp lai ghép được đề xuất trong [14] là H (Hybrid search). - Còn các phương pháp của chúng tôi:. - phương pháp lai ghép biến thể thứ nhất là V1 (1 st variant of Hybrid search), phương pháp lai ghép biến thể thứ hai là V2 (2 sd variant of Hybrid search), phương pháp lai ghép biến thể thứ hai là V3 (3 rd variant of Hybrid search), và phương pháp lai ghép biến thể thứ tư là V4 (4 th variant of Hybrid search).. - Bảng 1 Kết quả mô phỏng các phương pháp tìm kiếm trên đồ thị luật hàm mũ với 5 5 thông báo và γ =2.1. - Bảng 2 Kết quả mô phỏng các phương pháp tìm kiếm trên đồ thị luật hàm mũ với 5 5 thông báo và γ =2.7. - Phương pháp phát tràn có tổng số nút nhận truy vấn dư thừa là thấp nhất.. - Bảng 3 Kết quả mô phỏng các phương pháp tìm kiếm trên đồ thị luật hàm mũ với N thông báo và γ =2.1. - Bảng 4 Kết quả mô phỏng các phương pháp tìm kiếm trên đồ thị luật hàm mũ với N thông báo và γ =2.7.. - Đối với mô phỏng này, thì kết quả của phương pháp tìm kiếm lai đề xuất trong tài liệu [14] lại cho kết quả tốt nhất, sau đó là phương pháp tìm kiếm di chuyển ngẫu nhiên.. - Kết quả với phương pháp của chúng tôi và phương pháp phát tràn cho kết quả thấp hơn.. - Bảng 5 Kết quả mô phỏng các phương pháp tìm kiếm trên tô pô với phân cụm K 100. - Bảng 6 Kết quả mô phỏng các phương pháp tìm kiếm trên tô pô phân cụm G 100,1/2. - Bảng 7 Kết quả mô phỏng các phương pháp tìm kiếm trên tô pô phân cụm G 100,1/5 Độ. - Phương pháp tìm kiếm lai ghép đề xuất trong tài liệu [14] cũng là một phương pháp tìm kiếm tốt.. - Bảng 8 Kết quả mô phỏng các phương pháp tìm kiếm trên cluster với phân cụm K 100. - Bảng 9 Kết quả mô phỏng các phương pháp tìm kiếm trên cluster với phân cụm G 100,1/2. - Bảng 10 Kết quả mô phỏng các phương pháp tìm kiếm trên tô pô phân cụm G 100,1/5 Độ. - Kết quả mức độ bao phủ của các phương pháp tìm kiếm trên đồ thị luật hàm mũ với 5 5 thông báo.. - Kết quả mức độ bao phủ của các phương pháp tìm kiếm trên đồ thị luật hàm mũ với N thông báo.. - Kết quả mức độ bao phủ của các phương pháp tìm kiếm trên tô pô phân cụm với 5 5 thông báo.. - Kết quả mức độ bao phủ của các phương pháp tìm kiếm trên tô pô phân cụm với N thông báo.. - Kết quả số nút nhận được thông báo truy vấn dư thừa của các phương pháp tìm kiếm trên đồ thị luật hàm mũ với 5 5 thông báo.. - Kết quả số nút nhận được thông báo truy vấn dư thừa của các phương pháp tìm kiếm trên đồ thị luật hàm mũ với N thông báo.. - Kết quả số nút nhận được thông báo truy vấn dư thừa của các phương pháp tìm kiếm trên tô pô phân cụm với 5 5 thông báo.. - Kết quả số nút nhận được thông báo truy vấn dư thừa của các phương pháp tìm kiếm trên tô pô phân cụm với N thông báo.. - Biểu diễn sự phân bố thông báo truy vấn trên đồ thị luật hàm mũ với γ =2.1và 5 5 truy vấn, phương pháp tìm kiếm di chuyển ngẫu nhiên.. - Biểu diễn sự phân bố thông báo truy vấn trên đồ thị luật hàm mũ với γ =2.1và 5 5 truy vấn, phương pháp tìm kiếm phát tràn.. - Các biến thể của chúng tôi là sự kết hợp của phương pháp tìm kiếm: phương pháp di chuyển ngẫu nhiên (bao gồm cả phương pháp thông thường và cải tiến) trước và phương pháp phát tràn sau. - Với biến thể thứ hai: đầu tiên cũng sử dụng phương pháp tìm kiếm ngẫu nhiên, tìm kiếm k nút, sau đó thực hiện phương pháp phát tràn thông thường từ k nút này. - Phương pháp phát tràn là phương pháp tìm kiếm tốt nhất với lượng thông báo nhỏ trên đồ thị luật hàm mũ và các phương pháp tìm kiếm lai ghép biến thể của chúng tôi cũng là phương pháp tốt trong trường hợp γ =2.1. - Với lượng thông báo truy vấn N là lớn thì phương pháp tìm kiếm lai ghép biến thể thứ ba của chúng tôi cho kết quả tốt nhất, phương pháp di chuyển ngẫu nhiên và phương pháp lai ghép trong tài liệu [14] cũng cho kết quả tốt