ĐẠi học quốc gia hà NỘi trưỜng đẠi học công nghệ Phạm Đình Hậu
Tìm kiếm thông tin dựa vào vị trí
tải về 2.07 Mb.
|
- Điều hướng trang này:
- 1.6. Tổng kết
- CHƯƠNG 2. PHƯƠNG PHÁP TÌM KIẾM THÔNG TIN TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC
- 2.1. Tổng quan về mạng ngang hàng
- 2.1.2. Ưu điểm và nhược điểm của mạng ngang hàng
- 2.1.3. Phân loại mạng ngang hàng
- 2.2. Mạng ngang hàng có cấu trúc
- 2.2.2. Mạng ngang hàng có cấu trúc CHORD
1.5. Tìm kiếm thông tin dựa vào vị trí+ Yêu cầu của hệ thống tìm kiếm thông tin theo vị trí là: - Cung cấp kết quả chính xác với yêu cầu của người dùng và giá thành của dịch vụ hợp lý. - Có thể định vị được các thiết bị di động trong phạm vị rộng, - Với các dịch vụ khác nhau thì có độ ưu tiên khác nhau như với dịch vụ khẩn cấp thì phải đáp ứng nhanh còn với dịch vụ tìm tiệm ăn, nhà hàng, khách sạn thì có thể ưu tiên ít hơn. - Dịch vụ không làm tăng kích thước, khối lượng của thiết bị nhiều cũng như không làm tiêu tốn nhiều năng lượng của thiết bị. - Có thể phục vụ được một số lượng lớn các thiết bị di động tại cùng một thời điểm. - Các thông tin về khách hàng phải được giữ bí mật. - Hệ thống phải dễ dàng mở rộng: Có thể tăng số người sử dụng cũng như tăng khả năng xử lý và lưu trữ của hệ thống. - Hệ thống có thể cung cấp dịch vụ thời gian thực. - Người dùng có thể sử dụng dịch vụ mọi lúc, mọi nơi. + Vấn đề tìm kiếm thông tin theo vị trí: Hệ thống dịch vụ tìm kiếm thông tin theo vị trí hiện nay chủ yếu được xây dựng theo mô hình khách - chủ. Nhược điểm của mô hình này đó là dễ bị quá tải tại máy chủ trung tâm khi có nhiều người dùng truy cập cùng một thời điểm và khó khăn khi mở rộng hệ thống. Yêu cầu của hệ thống dịch vụ tìm kiếm thông tin theo vị trí là hệ thống có thể lưu trữ, xử lý, tìm kiếm dữ liệu trên quy mô lớn và có khả năng mở rộng cao vì vậy việc triển khai dịch vụ này trên mô hình khách - chủ là không phù hợp. Mạng ngang hàng có cấu trúc là một giải pháp tốt để triển khai dịch vụ tìm kiếm thông tin theo vị trí vì bản chất của mạng ngang hàng là quản lý, lưu trữ, xử lý thông tin phân tán và mạng ngang hàng có cấu trúc có ưu điểm là có thể thể tìm kiếm thông tin nhanh, tìm kiếm trên quy mô lớn và hệ thống có tính mở rộng cao.
Qua các yêu cầu của dịch vụ này ta có thể thấy việc triển khai dịch vụ dựa vào vị trí trên mạng ngang hàng là hoàn toàn khả thi vì khi triển khai dịch vụ này trên mạng ngang hàng thì hệ thống sẽ có thể tận dụng được khả năng lưu trữ, xử lý thông tin của các máy tham gia vào mạng chính vì vậy làm tăng khả năng xử lý tổng thể của hệ thống. Khả năng xử lý tổng thể của hệ thống tăng sẽ làm cho thời gian đáp ứng của dịch vụ nhanh, đáp ứng được dịch vụ thời gian thực và ưu điểm của mạng ngang hàng là khả năng mở rộng dễ cao chính vì vậy hệ thống triển khai trên mạng ngang hàng sẽ có được ưu điểm là khả năng mở rộng hệ thống dễ dàng. CHƯƠNG 2. PHƯƠNG PHÁP TÌM KIẾM THÔNG TIN TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚCMạng ngang hàng ngày càng trở nên phổ biến trong các ứng dụng chia sẻ trên mạng. Các mạng ngang hàng đã xuất hiện từ những năm 1980 và phát triển mạnh mẽ như APANET, Usenet, FidoNet. Hiện nay, với sự tham gia của các công ty thương mại và phi thương mại như Napster, Gnutella mạng ngang hàng ngày càng lớn mạnh và được được nhiều người sử dụng. Nhất là hiện nay khi lượng thông tin truyền tải trên mạng vô cùng lớn, nhu cầu tìm kiếm và chia sẻ thông tin cũng tăng lên. Mạng ngang hàng được xây dựng giữa các máy tính độc lập có khả năng chia sẻ dữ liệu và tận dụng tài nguyên để chia sẻ cho các máy tính khác. 2.1. Tổng quan về mạng ngang hàng2.1.1. Khái niệm mạng ngang hàngMạng ngang hàng là một cấu trúc được tạo nên bởi các máy tính liên kết với nhau, vai trò của mỗi máy tính là như nhau, mỗi máy tính là một phần và duy trì sự tồn tại của mạng. Các máy tính trong mạng thường xuyên liên lạc với các máy tính khác để ổn định mạng và chia sẻ dữ liệu với nhau. Mạng ngang hàng có nhiều ứng dụng và ứng dụng phổ biến nhất là chia sẻ tệp tin, tất cả các dạng tệp tin chia sẻ như âm thanh, hình ảnh, dữ liệu... 
Hình 9: Mô hình mạng ngang hàng Một mạng ngang hàng đúng nghĩa không có khái niệm máy chủ và máy khách hay nói cách khác tất cả các máy tham gia đều bình đẳng và được gọi là Peer. Peer là một nút mạng vừa đóng vai trò là máy chủ với các máy khác trong mạng vừa đóng vai trò là máy khách khi được các máy khác phục vụ mình. Dữ liệu được chứa trên các máy tính và chia sẻ trực tiếp với nhau cũng thông qua các máy tính tham gia vào mạng ngang hàng.
Xét về khía cạnh sức mạnh xử lý, mạng mạng ngang hàng có khả năng xử lý cao hơn cả những máy chủ lớn nhất hiện nay do đó sử dụng mạng mạng ngang hàng có thể cải thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu và giải các bài toán phức tạp (đây đều là những vấn đề vượt ra ngoài tầm xử lý của những máy chủ tập trung khi số lượng truy vấn, tính toán tăng lên đến hàng trăm triệu mỗi ngày). Sở dĩ như vậy là vì mạng ngang hàng đã tận dụng khả năng xử lý, khả năng lưu trữ còn thừa của các máy tính tham gia mạng với những thuật toán phân tán hợp lý. Công nghệ này đã chia việc xử lý lớn ra thành những việc xử lý nhỏ có thể phân tán giữa các máy tính trong một mạng. Mỗi máy tính sẽ xử lý một phần dữ liệu và trả về kết quả xử lý cho máy tính trung tâm, máy tính trung tâm sẽ ghép nối các kết quả này lại với nhau. Bằng cách đó, ta có thể giải quyết được những bài toán phức tạp mà không cần phải nâng cấp khả năng xử lý của hệ thống hiện tại. Bên cạnh đó, việc phân tán trách nhiệm cung cấp dịch vụ đến tất cả các nút trên mạng sẽ giúp loại bỏ vấn đề ngừng trệ dịch vụ do nơi cung cấp duy nhất gặp sự cố. Mạng ngang hàng cũng tận dụng được băng thông trên toàn bộ mạng vì việc tăng số giao tiếp giữa các thiết bị mạng qua các đường truyền khác nhau sẽ làm giảm khả năng tắc nghẽn mạng. Ngoài ra, khi càng nhiều máy tính tham gia vào mạng ngang hàng thì tổng sức mạnh xử lý, khả năng lưu trữ và băng thông lại tăng theo điều đó cho thấy khả năng mở rộng của mạng mạng ngang hàng. Tuy nhiên, mạng ngang hàng cũng có nhiều nhược điểm. Với mô hình mạng ngang hàng thuần túy, tức là mô hình mà ở đó mọi máy đều có vai trò như nhau và không tuân theo bất cứ một quy luật định tuyến hay kết nối nào thì mạng mạng ngang hàng cũng bộc lộ khá nhiều nhược điểm: + Chính vì yêu cầu dịch vụ được đáp ứng một cách tùy biến nên máy yêu cầu dịch vụ có thể nhận được nhiều kết quả khác nhau khi nó kết nối đến các máy khác nhau cung cấp cùng một dịch vụ. + Các yêu cầu gửi đi có thể không nhận được kết quả trả về vì không có gì đảm bảo sẽ tồn tại một máy nào đó có khả năng đáp ứng yêu cầu đó. + Các tài nguyên có thể biến mất do nút cung cấp tài nguyên có thể ngắt kết nối bất cứ lúc nào. 2.1.3. Phân loại mạng ngang hàngMạng ngang hàng lai ghép Trong mô hình này, mỗi máy đều được nối với tất cả các máy khác trong mạng, cách nối này mang đặc điểm của mô hình mạng ngang hàng thuần túy. Tuy nhiên, vẫn có một máy đóng vai trò máy chủ trung tâm, máy chủ này có nhiệm vụ quản lý các thông tin chỉ mục. 
Hình 10. Hệ thống mạng ngang hàng lai ghép Những nhược điểm của việc quản lý điều khiển tập trung vẫn tồn tại trong mô hình mạng này. Nếu máy chủ trung tâm gặp lỗi thì các máy Peer không thể truy cập đến thông tin chỉ mục ở trên máy chủ trung tâm nên không thể tìm kiếm thông tin được. Đại diện cho mô hình mạng ngang hàng lai ghép là mạng ngang hàng Napster.
Trong mạng ngang hàng thuần tuý thì vai trò của các máy trong mạng là ngang nhau và trong mô hình mạng này thì đã loại bỏ sự tồn tại của các máy chủ tập trung. Mạng ngang hàng thuần tuý được chia thành hai loại là mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc. Mạng ngang hàng không cấu trúc: Trong mạng ngang hàng không cấu trúc thì các liên kết giữa các nút trong mạng được thiết lập ngẫu nhiên không theo quy luật. Những mạng như thế này dễ dàng được xây dựng vì một máy mới khi muốn tham gia mạng có thể lấy các liên kết có sẵn của một máy khác đang ở trong mạng và sau đó dần dần tự bản thân nó sẽ thêm vào các liên kết mới cho riêng mình. Khi một máy muốn tìm một dữ liệu trong mạng ngang hàng không cấu trúc, yêu cầu tìm kiếm sẽ được truyền trên cả mạng để tìm ra càng nhiều máy chia sẻ càng tốt. Đại diện cho mô hình mạng này là mạng ngang hàng Gnutella.
2.1.1. Tổng quan về mạng ngang hàng có cấu trúcNhược điểm của mạng ngang hàng không có cấu trúc là không thể đảm bảo chắc chắn sẽ tìm thấy một thông tin có tồn tại trên mạng ngang hàng do mạng này sử dụng cơ chế tìm kiếm phát tràn tức là gửi thông điệp ra toàn mạng. Thông điệp tìm kiếm theo kiểu phát tràn chỉ được chuyển tiếp một số lần rồi sẽ bị loại bỏ nên không thể đảm bảo sẽ tìm thấy thông tin có tồn tại trên mạng. Cách tìm kiếm phát tràn khi tìm kiếm các dữ liệu phổ biến được chia sẻ trên nhiều máy thì tỷ lệ thành công là khá cao nhưng ngược lại nếu dữ liệu chỉ được chia sẻ trên một vài máy thì xác suất tìm thấy là nhỏ. Tính chất này là hiển nhiên vì trong mạng ngang hàng không có cấu trúc, không có bất kỳ mối liên hệ giữa một máy và dữ liệu nó quản lý trong mạng, do đó yêu cầu tìm kiếm được chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số lượng máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhược điểm khác của hệ thống này là yêu cầu gửi đi không có định hướng nên một yêu cầu tìm kiếm thường được chuyển cho một số lượng lớn các máy trong mạng, làm tiêu tốn một lượng lớn băng thông của mạng và dẫn đến hiệu quả tìm kiếm chung của mạng thấp. Mạng ngang hàng có cấu trúc đã khắc phục nhược điểm của mạng không cấu trúc bằng cách sử dụng hệ thống bảng băm phân tán (DHT: Distributed Hash Table [6]). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Trong mạng ngang hàng có cấu trúc, tài nguyên được phân bố một cách hợp lý để không có một máy tính nào lưu giữ quá nhiều dữ liệu dẫn đến quá tải thông tin định tuyến. Do mạng là có cấu trúc nên các thông điệp chuyển đi giữa các máy tính để duy trì mạng ngang hàng được giảm xuống tối thiểu. Băng thông của mạng được dành nhiều hơn cho việc chia sẻ tài nguyên. 
Hình 11. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn Việc tìm kiếm thông tin trong mạng ngang hàng có cấu trúc cũng nhanh hơn trong mạng ngang hàng không có cấu trúc. Nếu như trong mạng ngang hàng không có cấu trúc các máy tính gửi thông điệp lan tràn để tìm kiếm thông tin thì trong mạng ngang hàng có cấu trúc một máy tính chỉ cần gửi thông điệp tìm kiếm qua một số máy tính là có thể tìm thấy được thông tin có tồn tại trên mạng. Một số mạng ngang hàng có cấu trúc nổi tiếng bao gồm Chord, CAN, Kademlia, Pastry và Tapestry. DHT nhấn mạnh vào các thuộc tính sau: + Khả năng mở rộng: hệ thống vẫn có thể hoạt động hiệu quả với hàng nghìn hoặc hàng triệu nút. + Khả năng chịu lỗi: hệ thống vẫn có thể làm việc ổn định ngay cả khi có các sự kiện nút tham gia, rời bỏ mạng hay lỗi xảy ra. + Kỹ thuật khóa được sử dụng để đạt được mục đích là mỗi nút chỉ cần liên kết với một số ít các nút khác trong hệ thống, thường là O(logn) với n là số nút tham gia. Vì vậy sự thay đổi của một nút chỉ ảnh hưởng đến một phần nhỏ của hệ thống mạng. + Một số thiết kế bảng băm phân tán có tính bảo mật nhằm chống lại những người tham gia có ác tâm và cho phép người tham gia giấu danh tính, mặc dù điều này không phổ biến trong các hệ thống mạng ngang hàng chia sẻ tệp tin. + Cuối cùng, bảng băm phân tán phải giải quyết những vấn đề cơ bản của các hệ thống phân tán đó là cân bằng tải, tính toàn vẹn dữ liệu và hiệu năng (cụ thể là đảm bảo các hoạt động như định tuyến, lưu trữ, truy vấn phải được thực thi nhanh chóng). 2.2.2. Mạng ngang hàng có cấu trúc CHORDTheo một đánh giá tổng hợp về các thuật toán định tuyến dựa trên bảng băm phân tán trong các kiến trúc mạng khác nhau như hình tròn (với giao thức Chord), hình cây, hình hộp (với giao thức CAN)…xét về tính linh hoạt trong việc định tuyến, khả năng phục hồi trạng thái cũng như khả năng chịu lỗi, kiến trúc hình tròn đều được đánh giá cao. Vì vậy, kiến trúc Chord thường được sử dụng như là mạng phủ để thực hiện các cài đặt cải tiến việc tìm kiếm trên mạng ngang hàng có cấu trúc. Mô hình mạng Chord: Chord được mô tả dưới dạng một vòng tròn và không gian định danh phân bố đều trên vòng tròn tăng dần theo chiều kim đồng hồ. Nếu gọi N là số bit định danh của không gian khóa thì mạng Chord có thế chứa tối đa 2N nút. Mỗi nút trên Chord có một định danh id và có khả năng duy trì liên kết hai chiều với các nút đứng liền trước và liền sau nó theo chiều kim đồng hồ, tạo thành một mạch liên kết vòng. Nút liền trước được gọi là Successor(id), và nút liền sau được gọi là Predecessor(id). Thêm vào đó, mỗi nút sẽ lưu một bảng định tuyến gọi là Finger Table, cho phép nút đó định tuyến tới các nút ở xa. Mỗi dòng trong bảng Finger Table sẽ lưu thông tin về một nút ở xa, gọi là một entry. Không gian định danh của mạng sử dụng bao nhiêu bit thì Finger Table có bấy nhiêu entry. 
Hình 12. Mô hình mạng Chord Hình trên minh hoạ cho một mạng Chord có 3 nút là 0, 1, 3 và các bảng Finger Table ứng với mỗi nút, N = 3 bit nên Finger Table có 3 entry. Các trường trong mỗi entry trong bảng Finger Table của nút n được định nghĩa trong bảng dưới: 
Hình 13: Định nghĩa các trường trong bảng định tuyến của Chord Trong đó các giá trị tại dòng i của bảng được coi như là finger thứ i của nút n. Thông tin lưu trong bảng cũng bao gồm cả IP và Port của các nút tương ứng. Nút đầu tiên trong bảng Finger Table của n chính là Successor của n, hay còn được gọi là Immediate Successor. Từ bảng Finger Table ở trên ta có thể thấy rằng: + Mỗi nút chỉ cần lưu trữ thông tin của một số nút nhất định trong bảng định tuyến của mình. + Nút biết thông tin về các nút gần nó nhiều hơn là các nút ở xa. + Bằng cách định tuyến thông qua bảng Finger Table, một nút n có thể xác định được vị trí của bất kỳ khóa nào trên mạng.
Chord ánh xạ các khóa vào các nút, thường theo cặp (khoá, giá trị). Một giá trị có thể là một địa chỉ, một văn bản, hoặc một mục dữ liệu. Chord có thể thực hiện chức năng này bằng cách lưu các cặp (khoá, giá trị) ở các nút mà khoá được ánh xạ. Một nút sẽ chịu trách nhiệm lưu giữ một khóa k nếu nút đó là nút có định danh id nhỏ nhất thỏa mãn điều kiện id >= k. Một nút khi lưu giữ khóa k cũng sẽ được gọi là Successor của k, ký hiệu là Successor(k). Hình dưới minh hoạ việc lưu khoá trong mạng Chord: nút 0 lưu khoá 6, nút 1 lưu khoá 1 và nút 3 lưu khoá 2. 
Hình 14. Minh hoạ quy tắc lưu khoá trong mạng Chord Tìm kiếm trong mạng Chord Khi một nút n cần tìm kiếm một khóa có định danh id, nút n sẽ tìm nút chịu trách nhiệm lưu giữ id đó. Nếu nút n ở xa so với vị trí của nút lưu giữ id, n có thể nhờ vào thông tin trong bảng Finger Table để định tuyến đến các nút xa hơn, từ đó dần dần tìm ra nút chịu trách nhiệm lưu giữ id. Một ví dụ được chỉ ra trong hình 12, giả sử nút 3 muốn tìm successor của ID = 1 (hoặc còn có thể coi là khóa) . ID =1 thuộc khoảng [7, 3). Nút 3 kiểm tra entry thứ 3 trong bảng định tuyến của nó, là 0. Bởi vì 0 nằm ngay trước 1 trên vòng tròn, nút 3 sẽ hỏi nút 0 để tìm successor của 1. Tiếp theo, nút 0 sẽ tìm trong bảng định tuyến của nó và suy ra successor của 1 chính là nút 1, và trả lời nút 3 rằng nút 1 chính là successor của khóa ID = 1.
Trong một mạng động thì các nút thường xuyên tham gia hay rời mạng nên để có thể xác định được vị trí của các khóa lưu trong mạng Chord thì mạng này cần thỏa mãn các điểm sau. + Mỗi successor của một nút phải được duy trì. + Với mỗi khóa k, nút successor(k) có trách nhiệm quản lý k. Khi tham gia vào một mạng Chord, một nút n cần chọn cho nó một định danh id và báo cho các nút bên cạnh biết sự tham gia của nó. Các nút Successor và Predecessor sẽ cần phải cập nhật thông tin về nút mới tham gia vào mạng và nút n cũng sẽ khởi tạo bảng định tuyến cho riêng mình. Để mạng vẫn định tuyến đúng sau khi có sự tham gia của nút n thì các nút cần thường xuyên chạy thuật toán ổn định mạng để cập nhật thông tin về các nút bên cạnh (hay nút láng giềng). Một số nút có lưu thông tin về n trong bảng Finger Table thì cần cập nhật các entry liên quan trọng Finger Table. Cuối cùng, nút Successor của n sẽ chuyển một phần khóa k mà bây giờ n là Successor(k) cho n lưu giữ. Khi một nút chuẩn bị rời khỏi mạng, nó cần thông báo cho các nút bên cạnh biết để ổn định lại mạng. Nút đó cũng sẽ chuyển các khóa nó lưu giữ cho nút Successor của mình. Каталог: jspui -> bitstream -> 123456789 123456789 -> Nguyễn Ngọc Lý Giám đốc Trung tâm Nghiên cứu về Môi trường và Cộng đồng 123456789 -> Vò Quúnh Thu Cao häc K18 123456789 -> Khoa Báo chí Đhkhxh&NV 123456789 -> Acknowledgements 123456789 -> Danh mục chữ viết tắT 123456789 -> Chương TỔng quan vật liệu mao quản trung bình (mqtb) trật tự 1 Giới thiệu chung 123456789 -> Khoa hóa họC (141 142 báo cáo) tải về 2.07 Mb. Chia sẻ với bạn bè của bạn:
|