Khóa luận Xây dựng ứng dụng tìm kiếm thông tin theo vị trí trên mạng ngang hàng có cấu trúc

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Đình Hậu XÂY DỰNG ỨNG DỤNG TÌM KIẾM THÔNG TIN THEO VỊ TRÍ TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Đình Hậu XÂY DỰNG ỨNG DỤNG TÌM KIẾM THÔNG TIN THEO VỊ TRÍ TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS.Nguyễn Hoài Sơn HÀ NỘI - 2009 LỜI CẢM ƠN Để hoàn thành khóa luận này, trước hết em xin bày tỏ lòng biết ơn sâu sắc tới thầy TS. Nguyễn Hoài Sơn. Thầy đã tận tình hướng dẫn, giúp đỡ em trong suốt quá trình làm khóa luận. Đồng thời em xin được cảm ơn các thầy giáo, cô giáo trong Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội đã truyền đạt cho em nhiều kiến thức bổ ích trong suốt thời gian học tập tại trường. Cuối cùng, em xin cảm ơn tất cả bạn bè, gia đình và người thân đã giúp đỡ, động viên em rất nhiều để em có thể hoàn thành tốt khoá luận. Hà Nội, ngày 25 tháng 5 năm 2009 Sinh viên Phạm Đình Hậu TÓM TẮT NỘI DUNG Hiện nay, các dịch vụ dựa vào vị trí cung cấp dịch vụ cho các thiết bị di động đang phát triển mạnh. Trong đó dịch vụ tìm kiếm thông tin theo vị trí là một dịch vụ quan trọng. Do các máy chủ cung cấp dịch vụ dựa vào vị trí hiện nay hoạt động rời rạc, không có sự liên kết với nhau dễ gây quá tải tại các máy chủ vào giờ cao điểm, thông tin cung cấp cho người dùng không đa dạng. Chính vì vậy nảy sinh nhu cầu liên kết các máy chủ của các nhà cung cấp dịch vụ lại với nhau thành một mạng dịch vụ. Để các máy chủ cung cấp dịch vụ có thể liên kết được với nhau thì phải giải quyết được các vấn đề về quản lý, lưu trữ, xử lý thông tin phân tán và tìm kiếm thông tin quy mô lớn. Mạng ngang hàng có cấu trúc sẽ là một giải pháp tốt để liên kết các máy chủ cung cấp dịch vụ lại với nhau vì bản chất của mạng ngang hàng là xử lý và lưu trữ dữ liệu phân tán đồng thời mạng ngang hàng có cấu trúc có ưu điểm là tìm kiếm dữ liệu nhanh, có thể tìm kiếm được dữ liệu trên quy mô lớn và hệ thống có khả năng mở rộng cao. Khoá luận đã xây dựng một hệ thống tìm kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc trong đó thông tin tìm kiếm được dựa trên ngữ cảnh của người sử dụng. Ngữ cảnh ở đây là các thông tin về tuổi, giới tính, sở thích của người dùng và các thông tin về môi trường như thời tiết, mùa trong năm, thời gian trong ngày và vị trí hiện tại của người dùng. Hệ thống đã được thử nghiệm và đánh giá thông qua môi trường mạng có giới hạn băng thông và độ trễ giống với môi trường mạng Internet và mạng điện thoại hiện nay. Kết quả thử nghiệm cho thấy hệ thống xây dựng đã đáp ứng được các yêu cầu của dịch vụ dựa vào vị trí là cung cấp dịch vụ thời gian thực và có thể dễ dàng mở rộng hệ thống. MỤC LỤC LỜI MỞ ĐẦU 1 CHƯƠNG 1. MÔ HÌNH DỊCH VỤ DỰA VÀO VỊ TRÍ 3 1.2. Tổng quan về dịch vụ dựa vào vị trí ...............................................................................3 1.3. Các thành phần của dịch vụ dựa vào vị trí .....................................................................4 1.3.1. Thiết bị di động .......................................................................................................5 1.3.2. Mạng kết nối............................................................................................................6 1.3.3. Thành phần định vị ..................................................................................................8 1.3.4. Nhà cung cấp ứng dụng và dịch vụ .........................................................................9 1.4. Cách thức hoạt động của dịch vụ dựa vào vị trí ...........................................................10 1.5. Tìm kiếm thông tin dựa vào vị trí.................................................................................11 1.6. Tổng kết........................................................................................................................12 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 13 2.1. Tổng quan về mạng ngang hàng...................................................................................13 2.1.1. Khái niệm mạng ngang hàng.................................................................................13 2.1.2. Ưu điểm và nhược điểm của mạng ngang hàng ....................................................14 2.1.3. Phân loại mạng ngang hàng...................................................................................15 2.2. Mạng ngang hàng có cấu trúc.......................................................................................16 2.1.1. Tổng quan về mạng ngang hàng có cấu trúc .........................................................16 2.2.2. Mạng ngang hàng có cấu trúc CHORD.................................................................18 2.3. Tìm kiếm thông tin trên mạng ngang hàng có cấu trúc ................................................22 2.3.1. Tìm kiếm chính xác ...............................................................................................22 2.3.2. Tìm kiếm theo thuộc tính – giá trị .........................................................................22 2.3.3. Tìm kiếm theo khoảng...........................................................................................23 2.4. Kết luận ........................................................................................................................24 CHƯƠNG 3. XÂY DỰNG DỊCH VỤ TÌM KIẾM THÔNG TIN THEO VỊ TRÍ DỰA TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC 26 3.1. Mục đích và yêu cầu của tìm kiếm thông tin dựa vào vị trí .........................................26 3.2. Giải pháp thực hiện.......................................................................................................27 3.2.1. Tạo câu truy vấn phù hợp với ngữ cảnh ................................................................27 3.2.2. Biểu diễn dữ liệu theo vị trí ...................................................................................27 3.2.3. Chèn dữ liệu vào mạng ngang hàng có cấu trúc....................................................29 3.2.4. Tìm kiếm dữ liệu ...................................................................................................30 3.3. Cấu trúc hệ thống..........................................................................................................32 3.4. Hoạt động của hệ thống................................................................................................33 3.5. Đặc điểm của hệ thống đề xuất.....................................................................................36 3.6. Kết luận ........................................................................................................................37 CHƯƠNG 4. THỰC THI VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH 38 4.1. Kết quả thực thi chương trình.......................................................................................38 4.2. Mô hình thử nghiệm .....................................................................................................39 CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TIẾP THEO 43 5.1. Kết luận ........................................................................................................................43 5.2. Hướng phát triển tiếp theo của khoá luận.....................................................................44 DANH MỤC HÌNH ẢNH Hình 1. Cấu trúc hệ thống dịch vụ dựa vào vị trí .......................................................................4 Hình 2. Một số thiết bị di động sử dụng dịch vụ dựa vào vị trí..................................................5 Hình 3. Mạng diện rộng không dây............................................................................................6 Hình 4. Mạng cục bộ không dây ................................................................................................7 Hình 5. Mạng cá nhân không dây...............................................................................................7 Hình 6: Xác định vị trí dùng tín hiệu vệ tinh..............................................................................8 Hình 7. Xác định vị trí dùng dựa vào các trạm sóng đài ............................................................9 Hình 8. Cách thức hoạt động của dịch vụ dựa vào vị trí ..........................................................10 Hình 9: Mô hình mạng ngang hàng..........................................................................................13 Hình 10. Hệ thống mạng ngang hàng lai ghép .........................................................................15 Hình 11. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn ...............................................17 Hình 12. Mô hình mạng Chord.................................................................................................19 Hình 13: Định nghĩa các trường trong bảng định tuyến của Chord .........................................19 Hình 14. Minh hoạ quy tắc lưu khoá trong mạng Chord..........................................................20 Hình 15. Minh hoạ chia bề mặt trái đất thành các ô.................................................................28 Hình 16. Minh hoạ một ô của bề mặt trái đất được chia ra ......................................................28 Hình 17: Minh hoạ tìm kiếm thông tin trong một vùng ...........................................................30 Hình 18: Minh hoạ thông tin vị trí của một ô trên bề mặt trái đất............................................31 Hình 20. Cấu trúc hệ thống dịch vụ tìm kiếm thông tin dựa vào vị trí.....................................33 Hình 21: Minh hoạ việc tạo truy vấn theo ngữ cảnh ................................................................34 Hình 22: Yêu cầu địa chỉ IP và cổng của các máy trong mạng ngang hàng ............................34 Hình 23: Yêu cầu tìm kiếm của thiết bị di động gửi lên mạng ngang hàng .............................35 Hình 24: Minh hoạ mạng ngang hàng trả kết quả cho thiết bị di động ....................................36 Hình 25: Minh hoạ giao diện hiển thị kết quả tìm kiếm thông tin ...........................................38 Hình 27: Giao diện hiển thị kết quả trên bản đồ.......................................................................39 Hình 28: Mô hình thí nghiệm ...................................................................................................39 Hình 29: Kết quả thí nghiệm ....................................................................................................40 Hình 30: Đồ thị kết quả thử nghiệm.........................................................................................41 1 LỜI MỞ ĐẦU Ngày này, số lượng các thiết bị di động cầm tay tăng nhanh, sức mạnh xử lý và bộ nhớ của thiết bị đã có thể đáp ứng được yêu cầu của nhiều dịch vụ. Trong đó dịch vụ dựa vào vị trí là một dịch vụ phổ biến và đang phát triển hiện nay. Dịch vụ này được ứng dụng trong nhiều lĩnh vực và cung cấp các thông tin như dịch vụ gần nhất, theo dõi phương tiện giao thông, các dịch vụ khẩn cấp. Dịch vụ tìm kiếm thông tin là một dịch vụ quan trọng của dịch vụ dựa vào vị trí và đang phát triển mạnh. Tuy hiện nay có nhiều dịch vụ tìm kiếm thông tin nhưng thông tin tìm kiếm được thường không đúng yêu cầu và không có liên hệ với ngữ cảnh của người dùng. Ngữ cảnh ở đây là các thông tin cá nhân (tuổi, giới tính, sở thích, lịch làm việc), thông tin môi trường xung quanh (thời gian trong ngày, mùa trong năm, thời tiết...) và vị trí của người dùng. Để đáp ứng được nhu cầu của người sử dụng là tìm kiếm thông tin chính xác và phù hợp với yêu cầu của người dùng thì khoá luận đã xây dựng một hệ thống tìm kiếm thông tin theo vị trí trong đó thông tin được tìm kiếm dựa trên ngữ cảnh của người dùng. Hệ thống sẽ cung cấp thông tin một cách tự động cho người dùng bằng cách tạo truy vấn tìm kiếm tự động từ ngữ cảnh của người dùng. Yêu cầu của hệ thống này là phải có khả năng tìm kiếm dữ liệu trên quy mô lớn, có tính phân tán và có khả năng mở rộng cao. Công nghệ mạng ngang hàng đã phát triển nhanh chóng trên mạng Internet trong thời gian gần đây với sự xuất hiện của hàng loạt các ứng ngang hàng như Napster, Gnutella, Freenet, BitTorrent, Edonkey…. Sở dĩ mô hình mạng mạng ngang hàng phát triển như vậy là vì mô hình này rất phù hợp với tính phân tán của dữ liệu, đồng thời nó đảm bảo quyền quản lý dữ liệu của người dùng nên khuyến khích được việc chia sẻ dữ liệu, làm tăng nguồn tài nguyên trên mạng. Mô hình mạng ngang hàng cũng được sử dụng để xử lý các bài toán phức tạp do tận dụng được khả năng tính toán phân tán và tích hợp dữ liệu từ các máy tính tham gia mạng. Trong mạng ngang hàng các máy tham gia đều đóng góp tài nguyên như băng thông, khả năng xử lý và khả năng lưu trữ. Để đáp ứng được yêu cầu của hệ thống tìm kiếm thông tin theo vị trí là có thể tìm kiếm dữ liệu trên quy mô lớn, có tính phân tán và có tính mở rộng cao thì mạng ngang hàng có cấu trúc là một giải pháp tốt. Bởi vì mạng ngang hàng có cấu trúc có ưu điểm là có thể quản lý, lưu trữ và tìm kiếm trên quy mô lớn, có tính phân tán và có thể dễ dàng mở rộng. Vì vậy khoá luận đã đi sâu vào nghiên cứu và xây dựng hệ thống tìm kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc . Để đánh giá hiệu quả của hệ thống đã xây dựng thì hệ thống đã được thử nghiệm trong môi trường được giới 2 hạn về băng thông và độ trễ giống với môi trường Internet và mạng điện thoại hiện nay và kết quả thử nghiệm là khá khả quan. Khoá luận được chia làm 5 chương: - Chương 1: Chương này sẽ giới thiệu về cấu trúc của hệ thống dịch vụ dựa vào vị trí hiện đang được sử dụng và các yêu cầu của dịch vụ dựa vào vị trí. - Chương 2: Trong chương này sẽ giới thiệu tổng quan về mạng ngang hàng, ưu nhược điểm của mạng ngang hàng và các phương pháp tìm kiếm đang được sử dụng trong mạng ngang hàng có cấu trúc. - Chương 3: Chương này sẽ trình bày về ý tưởng, yêu cầu và cách thức xây dựng dịch vụ tìm kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc. - Chương 4: Trong chương này chúng ta sẽ trình bày về mô hình thực nghiệm để đánh giá hiệu quả của dịch vụ tìm kiếm thông tin theo vị trí đã xây dựng và đưa ra các nhận xét đánh giá kết quả thử nghiệm. - Chương 5: Kết luận và hướng phát triển tiếp theo của khoá luận. 3 CHƯƠNG 1. MÔ HÌNH DỊCH VỤ DỰA VÀO VỊ TRÍ Ngày nay, với sự tiến bộ của khoa học kỹ thuật, đặc biệt là sự phát triển nhanh chóng của công nghệ phần cứng đã có thể tạo ra các thiết bị nhỏ gọn, có khả năng lưu trữ và xử lý lớn như PDA, Smart Phone, Pocket PC.... Giá thành của các sản phẩm này liên tục giảm khiến cho số lượng người dùng sử dụng các thiết bị thông minh này tăng nhanh chóng. Chính vì số lượng các thiết bị thông minh này tăng nhanh dẫn đến nhu cầu của người dùng muốn sử dụng các dịch vụ gia tăng trên các thiết bị này lớn. Dịch vụ dựa vào vị trí là một dịch vụ gia tăng đang phát triển ngày nay. Các ứng dụng của dịch vụ này rất đa dạng, các ứng dụng này cung cấp cho mọi người các thông tin như vị trí các rạp chiếu bóng, các phòng nghe nhạc, các bữa tiệc và các thông tin về bản đồ, nhà hàng, viện bảo tàng, bệnh viện... ở các địa điểm gần mình. 1.2. Tổng quan về dịch vụ dựa vào vị trí Dịch vụ dựa vào vị trí là dịch vụ cung cấp các thông tin liên quan đến vị trí của thiết bị di động cầm tay thông qua mạng điện thoại hoặc kết nối không dây. Dịch vụ dựa vào vị trí cũng có thể được định nghĩa là dịch vụ khai thác các thông tin về vị trí của thiết bị di động cầm tay. Dịch vụ này có thể cung cấp các thông tin như “Vị trí trạm ATM (Automatic Teller Machine) gần nhất” hoặc các thông tin về vị trí của các nhà hàng, quán ăn, các bến xe... ở quanh vị trí của thiết bị di động cầm tay. Các thông tin này có thể được cung cấp một cách tự động mà không cần bất cứ thao tác yêu cầu nào của người dùng hoặc người dùng cũng có thể yêu cầu trực tiếp các thông tin mình muốn tìm và có thể tuỳ chọn tìm kiếm thông tin về một vị trí được chỉ định trên bản đồ số. Dịch vụ dựa vào vị trí mới xuất hiện gần đây, dịch vụ này tập trung vào cung cấp các dịch vụ trong phạm vi nhóm người dùng không chuyên và hoạt động trong môi trường tính toán di động có năng lực tính toán thấp. Các ứng dụng phổ biến của dịch vụ dựa vào vị trí: + Định vị: Dùng để xác định vị trí của một người nào hay vật nào để trả lời cho câu hỏi đang ở đâu. + Di chuyển: Ứng dụng này có thể chỉ dẫn một cách chi tiết làm sao để đi đến một vị trí mà người dùng mong muốn. + Tìm kiếm: Ứng dụng này có thể là cung cấp các thông tin về các dịch vụ gần nhất (có thể là nhà hàng gần nhất, trạm ATM gần nhất), các thông tin về giao thông như tình trạng tắc nghẽn giao thông tại điểm nào đó. 4 + Xác định một người hay vật: Dùng để xác định một vật hay người nào đó ở vị trí hiện tại. + Kiểm tra sự kiện: Dùng để kiểm tra xem có sự kiện nào xảy ra ở vị trí này không. + Dịch vụ khẩn cấp: Khi có các tình trạng khẩn cấp như hoả hoạn, lũ lụt, trộm cướp thì có thể sử dụng dịch vụ này để thông báo cho cảnh sát hoặc cho lính cứu hoả. + Dịch vụ theo dõi: Dịch vụ này có thể là theo dõi giao thông để thông báo cho các các xe cứu thương hoặc cung cấp cho người dùng tránh các điểm tắc nghẽn. 1.3. Các thành phần của dịch vụ dựa vào vị trí Dịch vụ dựa vào vị trí gồm có bốn thành phần như hình 1 [3]: - Thiết bị di động - Mạng kết nối - Thành phần định vị -Nhà cung cấp ứng dụng và dịch vụ Hình 1. Cấu trúc hệ thống dịch vụ dựa vào vị trí 5 1.3.1. Thiết bị di động Là các thiết bị Mobile Phone, Smart Phone, Laptop, PDA... mà người dùng có thể sử dụng để truy cập và hiển thị thông tin. Người dùng có thể nhận thông tin dưới các dạng như âm thanh, văn bản, hình ảnh... Các thiết bị di động có thể là PDA, Phones, Laptops... nhưng cũng có thể là các thiết bị định vị gắn kèm với ô tô. Có nhiều loại thiết bị kết nối với dịch vụ dựa vào vị trí, tuỳ theo sức mạnh và khả năng lưu trữ của thiết bị, người dùng có thể sử dụng một hoặc nhiều dịch vụ khác nhau. Các thiết bị dùng dịch vụ dựa vào vị trí có thể được phân loại thành hai loại là thiết bị đơn nhiệm và thiết bị đa nhiệm. + Thiết bị đơn nhiệm: Thường sử dụng các dịch vụ khẩn cấp như còi báo động hoặc cảnh báo tình trạng khẩn cấp. + Thiết bị đa nhiệm: Các thiết bị này đang được nhiều người sử dụng và nó đã trở thành một phần của cuộc sống chúng ta. Một số thiết bị đa nhiệm trong hình vẽ 2: Mobile Phone, Smart Phone, Pocket PC, Laptop hoặc PDA. Hình 2. Một số thiết bị di động sử dụng dịch vụ dựa vào vị trí 6 + Đặc điểm của các thiết bị di động: - Hầu hết các thiết bị di động có tài nguyên tính toán và khả năng xử lý thấp. - Màn hình hiển thị nhỏ, pin có thời gian sử dụng ngắn, bị ảnh hưởng bởi điều kiện thời tiết. - Bị giới hạn về băng thông kết nối. 1.3.2. Mạng kết nối Thành phần này dùng để truyền dữ liệu, phục vụ các yêu cầu của người dùng và gửi kết quả cho người dùng. Mạng kết nối thường được phân chia thành các loại khác nhau tuỳ theo mục đích, giới hạn về sóng đài (radio) và các tính chất địa lý. + Mạng diện rộng không dây (WWAN: Wireless Wide Area Networks) thường từ 100 m đến 35 km và yêu cầu người dùng phải đăng ký để được sử dụng. Mạng này bao gồm GSM (Global System for Mobile, GPRS (General Packet Radio Service) và UMTS (Universal Mobile Telecommunication System). GMM và GPRS có thể truyền dữ liệu tối đa là 14 kbps và 115 kbps ngược lại UMTS có thể truyền tới 2 Mbps. Hình 3. Mạng diện rộng không dây 7 + Mạng cục bộ không dây (WLAN: Wireless Local Area Network): khoảng cách từ 10 đến 150 m. Thiết bị di động có thể kết nối thông qua các điểm truy cập. Hình 4. Mạng cục bộ không dây + Mạng cá nhân không dây (WPAN: Wireless Personal Area Networks): được dùng cho các kết nối trong một khoảng ngắn xung quanh 10 m và hệ thống thường không yêu cầu đăng ký sử dụng. Thông thường bao gồm Bluetooth và các thiết bị Infrared (IrDA), dữ liệu truyền qua công nghệ Bluetooth có thể là 1 Mbps trong khoảng cách 10 m và trong trường hợp IrDA (Inrared) nó có thể là 16 Mbps trong khoảng 1.5 m. Hình 5. Mạng cá nhân không dây 8 1.3.3. Thành phần định vị Là thành phần dùng để xác định vị trí hiện tại của người dùng. Hiện nay có hai phương pháp chính để xác định vị trí người dùng là dựa vào tín hiệu vệ tinh và dựa vào các trạm sóng đài. + Định vị dựa vào vệ tinh: Một số hệ thống định vị tiêu biểu sử dụng vệ tinh như TACAN – (TACtical Air Navigation), hệ thống định vị toàn cầu (GPS: Global Positioning System), GLONASS (Global'naya Navigatsionnaya Sputnikovaya Sistema). Hình 6: Xác định vị trí dùng tín hiệu vệ tinh Các hệ thống định vị sử dụng vệ tinh chủ yếu dùng để phục vụ cho mục đích quân sự nên khi dùng trong dân sự thì chúng bị giới hạn về độ chính xác như hệ thống định vị toàn cầu thì độ chính xác khoảng 15 m. Hiện nay có một số máy thu tín hiệu của hệ thống định vị toàn cầu đã có thể xác định vị trí chính xác hơn và sai lệch khoảng 3 m. Tín hiệu của hệ thống định vị toàn cầu bị nhiễu bởi khá nhiều yếu tố như: điều kiện khí quyển, tín hiệu đi theo nhiều đường, lỗi đồng bộ giữa máy thu và vệ tinh của hệ thống định vị toàn cầu, thiết bị thu tín hiệu bị che khuất bởi các toà nhà. 9 + Định vị dựa vào mạng: Hệ thống này xác định vị trí của người dùng dựa vào các cột sóng đài. Hình 7. Xác định vị trí dùng dựa vào các trạm sóng đài 1.3.4. Nhà cung cấp ứng dụng và dịch vụ Nhà cung cấp dịch vụ cung cấp một số các dịch vụ khác nhau cho người dùng và phản hồi các yêu cầu cung cấp dịch vụ cho người dùng. Các dịch vụ và ứng dụng được cung cấp như các dịch vụ về tìm vị trí, tìm đường đi dựa trên thông tin mà người dùng cung cấp hoặc tìm kiếm các thông tin về đối tượng mà người dùng quan tâm (như nhà hàng, viện bảo tàng, khách sạn, tiệm ăn...) Thông thường dịch vụ dựa vào vị trí được chia thành hai loại: + Dịch vụ kéo về (Pull Services): Là những dịch vụ đáp ứng yêu cầu trực tiếp của người dùng, dịch vụ này thường được chia thành hai loại: - Dịch vụ chức năng: Các dịch vụ cung cấp chức năng hỗ trợ người dùng 113, 115 (gọi dịch vụ cấp cứu khẩn cấp chỉ thông qua một nút bấm). - Dịch vụ thông tin: Cung cấp thông tin như “tìm quán ăn gần nhất”. + Dịch vụ đẩy đi (Push Services): Cung cấp thông tin dù người có có yêu cầu hay không yêu cầu trực tiếp. Dịch vụ hoạt động tự động và làm việc khi xảy ra một sự kiện được chỉ định như dịch vụ dự báo thời tiết, tin nhắn quảng cáo khi người dùng đi vào một khu vực nào đó. 10 1.4. Cách thức hoạt động của dịch vụ dựa vào vị trí Hệ thống hoạt động dựa trên các thành phần như hình vẽ 8 [3]: Các thiết bị, mạng kết nối, công nghệ xác định vị trí, máy chủ cung cấp dịch vụ và dữ liệu. Hình 8. Cách thức hoạt động của dịch vụ dựa vào vị trí Hoạt động của hệ thống sẽ như sau: Bước 1: Đầu tiên các thiết bị di động cầm tay sẽ xác định vị trí của mình dựa vào tín hiệu vệ tinh của hệ thống định vị toàn cầu, các cột sóng di động hoặc dựa vào các điểm truy cập không dây. Bước 2: Sau khi đã có được thông tin về vị trí hiện tại thì thiết bị di động sẽ gửi thông tin về vị trí của mình và thông tin cần tìm kiếm (như cửa hàng, khách sạn, trạm ATM gần nhất) đến máy chủ cung cấp dịch vụ qua mạng kết nối. Bước 3: Các máy chủ dịch vụ sẽ đọc yêu cầu của thiết bị di động, xử lý yêu cầu và gửi kết quả cho thiết bị di động. Bước 4: Thiết bị di động sẽ hiển thị kết quả cho người dùng, kết quả có thể được hiển thị dưới dạng tin nhắn hoặc hiển thị trên bản đồ để người dùng có thể thấy một cách trực quan vị trí của thông tin. 11 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. 12 1.6. Tổng kết Chương này đã giới thiệu tổng quan về dịch vụ dựa vào vị trí, cấu trúc của dịch vụ dựa vào vị trí, hoạt động của dịch vụ dựa vào vị trí cũng như các yêu cầu hệ thống của dịch vụ này. 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. 13 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 Mạ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àng 2.1.1. Khái niệm mạng ngang hàng Mạ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 14 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. 2.1.2. Ưu điểm và nhược điểm của mạng ngang hàng Mô hình mạng ngang hàng rất phù hợp với tính phi tập trung của Internet, bởi bản chất của tài nguyên là phân tán, các thông tin lưu trữ không chỉ trên các máy chủ mà ở cả các máy khách. 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: 15 + 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àng Mạ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 16 đế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. Mạng ngang hàng thuần tuý 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.2. Mạng ngang hàng có cấu trúc 2.1.1. Tổng quan về mạng ngang hàng có cấu trúc Nhượ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]). 17 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. 18 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 CHORD Theo 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. 19 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 20 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. Ánh xạ khóa vào một nút trong Chord 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 21 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. Tham gia và ổn định mạng 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. 22 2.3. Tìm kiếm thông tin trên mạng ngang hàng có cấu trúc 2.3.1. Tìm kiếm chính xác Là phương pháp tìm kiếm thông tin theo định danh, định danh này có thể là băm từ một từ khoá do người dùng nhập vào, từ tên tệp tin hoặc từ một phần nội dung của tệp tin. Phương pháp này chỉ có thể cho phép tìm kiếm chính xác thông tin người dùng yêu cầu mà không thể tìm kiếm một thông tin có kết quả gần giống với yêu cầu của người dùng. Ví dụ như khi người dùng muốn tìm một quyển sách “Mạng ngang hàng có cấu trúc” nhưng người dùng chỉ nhập vào từ khoá “Mạng ngang hàng” thì thông tin tìm thấy chỉ là những thông tin có nội dung là “Mạng ngang hàng” mà không thể tìm thấy các thông tin như “Mạng ngang hàng không có cấu trúc, Mạng ngang hàng có cấu trúc, mạng ngang hàng lai ghép...”. Phương pháp tìm kiếm này thường dùng kết hợp với bảng băm phân tán. Khi được kết hợp với bảng băm phân tán thì phương pháp tìm kiếm này có ưu điểm là giảm số thông báo yêu cầu tìm kiếm và các thông báo gửi đi có định hướng. Hiện nay, có rất nhiều mạng ngang hàng có cấu trúc đang sử dụng phương pháp tìm kiếm này, tiêu biểu là các mạng ngang hàng có cấu trúc CAN, Chord, Pastry. 2.3.2. Tìm kiếm theo thuộc tính – giá trị Phương pháp tìm kiếm này sẽ sử dụng các cặp thuộc tính – giá trị để tìm kiếm thông tin. Các từ khoá mà người dùng hay sử dụng chủ yếu là các cặp thuộc tính – giá trị ví dụ như “Trường = Đại Học Công Nghệ” là một cặp thuộc tính – giá trị, thuộc tính là “Trường” và giá trị là “Đại Học Công Nghệ”. Theo thống kê thì một từ khoá tìm kiếm mà người dùng sử dụng trung bình gồm có 2.53 từ và có tới 71.5% các truy vấn tìm kiếm bao gồm hai hoặc nhiều hơn các từ khoá . Do từ khoá tìm kiếm thường là cặp thuộc tính – giá trị nên tìm kiếm theo phương pháp này có thể tìm được hầu hết các thông tin mà người dùng mong muốn. Trong phương pháp này nội dung thông tin sẽ được biểu diễn thành một tập các cặp thuộc tính – giá trị. Việc tìm kiếm thông tin cũng sẽ dựa trên các cặp cặp thuộc tính – giá trị, trong yêu cầu tìm kiếm sẽ có chứa một tập các cặp thuộc tính – giá trị cần truy vấn. Kết quả trả về sẽ chứa danh sách các bản ghi có các cặp thuộc tính – giá trị thoả mãn truy vấn. 23 Việc phân bổ thông tin có thể dựa vào một trong số các cặp thuộc tính để phân bổ hoặc với một thông tin có n cặp thuộc tính – giá trị có thể sẽ phải phân bổ thông tin này ra n nút để khi tìm kiếm có thể tìm được thông tin đã phân bổ này. Một số giải thuật tìm kiếm theo giá trị - thuộc tính tiêu biểu như: CDS [4] (Content discovery System), INS/Twine [5] 2.3.3. Tìm kiếm theo khoảng Là phương pháp tìm kiếm mà giá trị của một thuộc tính dao động trong một khoảng nào đó. Ví dụ như tìm kiếm một thuộc tính “Quần Áo” có giá trị từ “100.000 đến 300.000 đồng” hoặc tìm kiếm trong một vùng địa lý, một khoảng thời gian. Người dùng khi tìm kiếm thông tin thường không biết chính xác thông tin hoặc chỉ biết một phần thông tin hoặc muốn tìm thông tin trong một giới hạn nào đó. Để có thể cung cấp thông tin cho người dùng dù người dùng chỉ biết một phần thông tin hoặc muốn tìm thông tin trong một giới hạn thì phương pháp tìm kiếm theo khoảng được sử dụng. Tìm kiếm theo khoảng trên các hệ thống tập trung rất đơn giản chỉ cần duyệt tất cả các bản ghi theo chỉ mục để lấy ra các bản ghi thoả mãn thuộc tính có giá trị theo khoảng yêu cầu. Tuy nhiên để tìm kiếm theo khoảng trên mạng ngang hàng có cấu trúc là khó vì mạng ngang hàng có cấu trúc chỉ hỗ trợ tìm kiếm chính xác. Tức là chỉ có những thông tin như “Giá = 100.000 đồng” thì mới có thể tìm được trên mạng ngang hàng có cấu trúc mà không thể tìm được các thông tin như “Giá < 100.000 đồng và Giá > 10.000 đồng”. Để có thể tìm kiếm theo khoảng trên mạng ngang hàng có cấu trúc thì chúng ta có một số ý tưởng để thực hiện việc đó: - Ý tưởng để có thể tìm kiếm theo khoảng trên mạng ngang hàng có cấu trúc đó là dùng một phép biến đổi từ tìm kiếm theo khoảng thành tìm kiếm chính xác. Phép chuyển đổi này có thể được thực hiện bằng cách biểu diễn thông tin sao cho dữ liệu trong một khoảng nào đó được chuyển thành dữ liệu tại một điểm hoặc với những dữ liệu gần giống nhau thì được chèn vào mạng ngang hàng tại các vị trí gần nhau về mặt tô pô của mạng (như các dữ liệu gần giống nhau có thể lưu ở hai nút là hàng xóm của nhau). - Ta có thể coi một khoảng là một giá trị nào đó khi chèn thông tin vào mạng ngang hàng có cấu trúc như “Bất kỳ giá cả của mặt hàng nào có giá từ 100.000 đồng đến 200.000 đồng” thì ta coi như là nó có giá trị 100.000 đồng. Sau đó băm chuỗi “Giá 24 = 100.000 đồng” để lấy định danh và chèn vào mạng ngang hàng có cấu trúc, trong bản ghi được chèn thì vẫn có chứa thông tin về giá cả thực của mặt hàng. Khi tìm kiếm một mặt hàng từ khoảng 120.000 đến 180.000 đồng thì ta chỉ việc băm chuỗi “Giá = 100.000 đồng” để lấy định danh và tìm xem nút nào quản lý định danh này. Khi đã biết được nút nào quản lý định danh này thì ta sẽ truy vấn đến đó và tìm kiếm, nút chứa định danh khi nhận yêu cầu tìm kiếm sẽ duyệt trong cơ sở dữ liệu (lúc này việc tìm kiếm là cục bộ nên có thể dễ dàng lọc thông tin theo khoảng) để tìm các bản ghi thoả mãn và trả về cho máy yêu cầu. Nếu dữ liệu gần tường đồng nhau mà được chèn một vùng gần nhau về mặt tô pô của mạng ngang hàng có cấu trúc thì các truy vấn tìm kiếm theo khoảng có thể truy vấn quanh vùng đó để lấy được thông tin cần tìm. 2.4. Kết luận Trong chương này chúng ta đã giới thiệu tổng quan về mạng ngang hàng, các ưu nhược điểm của mạng ngang hàng và phân loại mạng ngang hàng. Mang ngang hàng được chia thành hai loại là mạng ngang hàng lai ghép và mạng ngang hàng thuần tuý. Đại diện cho mô hình mạng ngang hàng lai ghép là mạng ngang hàng Napster, đặc điểm của mô hình mạng này là có một máy chủ trung tâm quản lý chỉ mục và đây cũng chính là nhược điểm của mô hình này. Khi máy chủ trung tâm bị lỗi thì mạng ngang hàng lai ghép sẽ không thể tìm kiếm được thông tin do không thể truy cập đến thông tin chỉ mục do máy chủ quản lý. Mạng ngang hàng thuần tuý được chia thành hai loại là mạng ngang hàng có cấu trúc và mạng ngang hàng không có cấu trúc. Mạng ngang hàng Gnutella là đại diện cho mạng ngang hàng không có cấu trúc và nhược điểm của mô hình mạng này là không đảm bảo chắc chắn tìm kiếm được dữ liệu có tồn tại trên mạng do sử dụng cơ chế tìm kiếm phát tràn thông điệp. Do mạng ngang hàng không có cấu trúc sử dụng cơ chế tìm kiếm phát tràn nên làm tốn băng thông mạng đồng thời giảm hiệu quả tìm kiếm. Mạng ngang hàng có cấu trúc đã khắc phục được những nhược điểm của mạng ngang hàng không có cấu trúc. Các nút trong mạng ngang hàng có cấu trúc được liên kết với nhau theo một quy luật, mỗi nút sẽ quản lý một phần dữ liệu chia sẻ trên mạng và các dữ liệu chia sẻ này sẽ có mối liên hệ với nút quản lý. Ở trong mô hình mạng 25 ngang hàng có cấu trúc thì ta tìm hiểu chi tiết cách thức hoạt động của mạng ngang hàng Chord. Trong chương này chúng ta cũng đã được giới thiệu về các phương pháp tìm kiếm trong mạng ngang hàng có cấu trúc là tìm kiếm chính xác, tìm kiếm theo thuộc tính – giá trị và tìm kiếm theo khoảng. Qua tìm hiểu về lịch sử phát triển của mạng ngang hàng, ưu nhược điểm của mạng ngang hàng thì ta thấy mạng ngang hàng là một công nghệ mạnh và sẽ phát triển trong tương lai. Việc triển khai các ứng dụng trên mạng ngang hàng sẽ có thể tận dụng được rất nhiều ưu điểm của mạng này như tận dưng được khả năng xử lý, lưu trữ, băng thông của mạng và hệ thống có khả năng mở rộng cao. 26 CHƯƠNG 3. XÂY DỰNG DỊCH VỤ TÌM KIẾM THÔNG TIN THEO VỊ TRÍ DỰA TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC 3.1. Mục đích và yêu cầu của tìm kiếm thông tin dựa vào vị trí Để đáp ứng được nhu cầu tìm kiếm thông tin chính xác và phù hợp với yêu cầu của người dùng thì khoá luận đã xây dựng một hệ thống tìm kiếm thông tin theo vị trí trong đó thông tin tìm kiếm được dựa trên ngữ cảnh của người dùng. Hệ thống tìm kiếm này sẽ tự động cung cấp thông tin cho người dùng bằng cách tạo ra truy vấn tìm kiếm một cách tự động từ ngữ cảnh của người dùng. Ví dụ như một người dùng đang làm việc ở cơ quan và 11 giờ là hết giờ làm việc thì hệ thống sẽ tự động cung cấp thông tin về các tiệm ăn quanh vị trí cơ quan. Thông tin về các tiệm ăn có thể được lọc theo sở thích của người dùng như người dùng thích ăn đồ ăn nhanh hay thích ăn cơm công sở. Yêu cầu của dịch vụ tìm kiếm thông tin theo vị trí được chia thành hai loại là yêu cầu của người dùng và yêu cầu của hệ thống: + Yêu cầu của người dùng: - Hệ thống có thể cung cấp thông tin mọi lúc, mọi nơi, ở bất cứ mạng nào và với bất kỳ thiết bị di động cầm tay nào. - Sử dụng dễ dàng. - Có thể cung cấp được thông tin, thông tin cung cấp chính xác, phù hợp với ngữ cảnh và yêu cầu của người dùng. - Thời gian đáp ứng của dịch vụ là nhanh - Một số yêu cầu phụ như hệ thống có giao diện đẹp, hoạt động ổn định, tốn ít khả năng xử lý và lưu trữ của thiết bị. + Yêu cầu của hệ thống: - Cung cấp thông tin đúng, chính xác. - Có thể quản lý, lưu trữ và tìm kiếm thông tin trên quy mô lớn. - Có thể cung cấp dịch vụ cho số lượng lớn người dùng tại một thời điểm. - Hệ thống có thể dễ dàng mở rộng như nâng cấp hệ thống, tăng số lượng các máy phục vụ. - Có thể kháng lỗi tốt và đảm bảo tìm kiếm được thông tin dù mạng bị lỗi. 27 3.2. Giải pháp thực hiện Triển khai dịch vụ tìm kiếm theo vị trí trên mạng mạng ngang hàng có cấu trúc vì mang hàng hàng có cấu trúc có ưu điểm là có thể quản lý, lưu trữ và tìm kiếm dữ liệu trên quy mô lớn và dễ dàng mở rộng. Để có thể tìm kiếm thông tin chính xác phù hợp với yêu cầu của người dùng thì hệ thống tự động tạo truy vấn tìm kiếm dựa trên ngữ cảnh người dùng. Dịch vụ tìm kiếm thông tin theo vị trí có đặc điểm là tìm kiếm theo khoảng chính vì vậy hệ thống phải có khả năng tìm kiếm theo khoảng. Để hệ thống có thể tìm kiếm theo khoảng thì dữ liệu theo vị trí phải được biểu diễn và chèn vào mạng ngang hàng có cấu trúc một cách phù hợp. 3.2.1. Tạo câu truy vấn phù hợp với ngữ cảnh Để tạo ra câu truy vấn phù hợp với ngữ cảnh của người dùng thì hệ thống dựa vào các thông tin cá nhân của người dùng (tuổi, giới tính, lịch làm việc, sở thích...), các thông tin môi trường xung quanh (thời tiết, khí hậu, thời gian, mùa...) và thông tin vị trí. Ví dụ như một người dùng có lịch làm việc khoảng 8 giờ thì lúc 7 giờ có thể truy vấn tìm kiếm một số quán ăn gần vị trí người dùng, câu truy vấn còn yêu cầu lọc theo sở thích của người dùng như người dùng có thể chỉ thích ăn mì hoặc phở thì kết quả trả về sẽ là các quán ăn bán mì hoặc phở. 3.2.2. Biểu diễn dữ liệu theo vị trí Cách thức chèn dữ liệu vào mạng ngang hàng có cấu trúc Chord sẽ ảnh hưởng đến cách thức tìm kiếm dữ liệu. Đặc trưng của dịch vụ tìm kiếm theo vị trí là tìm kiếm theo khoảng (trong một vùng bán kính) chính vì vậy cách thức chèn dữ liệu vào mạng Chord phải đảm bảo sao cho khi tìm kiếm có thể tìm kiếm được thông tin theo khoảng. Để có thể hỗ trợ tìm kiếm thông tin trong một vùng địa lý thì ta chia bề mặt trái đất ra thành các ô hình vuông có cạnh là một ki lô mét và tất cả các vị trí thuộc một hình vuông sẽ được quy thành một điểm chung. 28 Hình 15. Minh hoạ chia bề mặt trái đất thành các ô Giả sử như hình vẽ trên ta chia bề mặt vật lý của một khi vực thành 25 hình vuông và mỗi hình vuông sẽ có cạnh là một ki lô mét. Hình 16. Minh hoạ một ô của bề mặt trái đất được chia ra Giả sử một ô là hình vuông ABCD như hình vẽ trên và điểm E có toạ độ (2500, 1500) nằm trong hình vuông này. Khi đó điểm E sẽ được quy về coi như là điểm C có toạ độ là (2000, 1000). Như vậy tất cả các toạ độ thuộc hình vuông sẽ đều được coi như là điểm C có toạ độ (2000, 1000). Khi đó tất cả các thông tin có toạ độ trong hình 29 vuông sẽ có chung một định danh để chèn vào mạng Chord (định danh trong chương trình sẽ được tính bằng cách băm chuỗi “2000$1000” đây là chuỗi được tạo ra từ toạ độ của điểm C). Khi tìm kiếm thì ta sẽ đi ngược lại với quá trình chèn dữ liệu, giả sử như ta tìm thông tin của một vùng nào đó trong hình vuông ABCD thì ta sẽ chỉ việc truy vấn đến nút nào quản lý định danh được băm từ toạ độ của điểm C để hỏi thông tin mà ta cần tìm. 3.2.3. Chèn dữ liệu vào mạng ngang hàng có cấu trúc Sau khi đã biểu diễn được dữ liệu theo vị trí thì ta sẽ tiến hành chèn dữ liệu theo vị trí này vào mạng ngang hàng có cấu trúc có cấu trúc (cụ thể trong khoá luận này là mạng ngang hàng có cấu trúc Chord). Dữ liệu vị trí sẽ được biểu diễn dưới dạng ngôn ngữ XML (eXtensible Markup Language) để tiện cho việc lưu trữ, truy vấn, tìm kiếm cũng như khả năng mở rộng hệ thống sau này. Khi cần chèn một thông tin ở vị trí kinh độ là A và vĩ độ là B thì các bước thực hiện sẽ như sau: Bước 1: Chuyển đổi kinh độ A và vĩ độ B sang hệ mét C = A * 3600 * 30.82 (m) D = B * 3600 * 30.92 (m) Trong công thức trên thì toạ độ A và B đều ở dạng thập phân và một độ kinh độ hoặc vĩ độ bằng 3600 giây, một giây kinh độ sẽ có độ dài là 30.82 mét và một giây vĩ độ có độ dài là 30.92. Bước 2: Toạ độ C và D sẽ được quy về một toạ độ chung như đã trình bày ở mục 3.2.2 về cách biểu diễn dữ liệu theo vị trí. Giả sử toạ độ C và D được chuyển sang toạ độ chung là E và F thì E và F sẽ được tính như sau: E = C - C % 1000 F = D – D % 1000 Bước 3: Tính toán định danh và chèn dữ liệu vào mạng ngang hàng có cấu trúc: - Tính định danh ID bằng cách băm chuỗi “E + $ + F” - Chèn dữ liệu vào mạng ngang hàng có cấu trúc theo đinh danh ID. 30 - Dữ liệu chèn sẽ được lưu tại nút có nhiệm vụ quản lý định danh ID và dữ liệu chèn này sẽ được lưu thông tin đây đủ (bao gồm cả toạ độ kinh độ và vĩ độ thực tế mà không phải là kinh độ và vĩ độ đã chuyển đổi). 3.2.4. Tìm kiếm dữ liệu Giả sử như ta cần tìm thông tin ở quanh vị trí có kinh độ là A và vĩ độ là B với bán kính vùng tìm kiếm là 2 km thì các bước thực hiện sẽ như sau: Bước 1: Kinh độ A và vĩ độ B sẽ được chuyển đổi sang hệ mét C = A * 3600 * 30.82 m D = B * 3600 * 30.92 m Trong công thức trên thì toạ độ A và B đều ở dạng thập phân và một độ kinh độ hoặc vĩ độ bằng 3600 giây, một giây kinh độ sẽ có độ dài là 30.82 mét và một giây vĩ độ có độ dài là 30.92. Bước 2: Trong bước này ta sẽ tính xem truy vấn đến các nút quản lý các ô nào. Hình 17: Minh hoạ tìm kiếm thông tin trong một vùng Giả sử ta đang tìm kiếm thông tin trong một vùng hình tròn ở một khu vực được chia thành 25 ô như hình trên. Do việc tìm kiếm thông tin trong một vùng hình tròn khó hơn tìm trong một vùng hình vuông nên ta chuyển sang tìm kiếm trong một vùng 31 hình vuông bao quanh hình tròn. Giả sử hình vuông bao quanh hình tròn là ABCD và toạ độ của A, B, C, D là A (xa, ya), B (xb, yb), C (xc, yc), D (xc, yc). Nhìn trên hình ta có thể thấy rằng dữ liệu ta cần tìm sẽ được lưu tại các nút quản lý thông tin của các ô 7, 8, 9, 12, 13, 14, 17, 18, 19. Để tính được dữ liệu cần tìm sẽ lưu tại các nút quản lý thông tin của ô nào thì ta sẽ duyệt từ (xa – xa %1000) đến (xb – xb %1000) và từ (ya – ya %1000) đến (yd – yd % 10000), mỗi lần duyệt sẽ tăng toạ độ lên 1000 m. Ta sẽ tìm được các điểm giao, các điểm giao này sẽ là toạ độ chung cho cả một ô, các điểm giao này sẽ được dùng để tính định danh chèn vào mạng ngang hàng có cấu trúc của ô. Bước 3: Khi ta đã có danh sách các ô như ở đây là các ô 7, 8, 9, 12, 13, 14, 17, 19 thì ta sẽ tính định danh từ các ô này. Giả sử ô 7 là hình vuông ABCD như hình dưới thì định danh dùng để chèn dữ liệu thuộc ô 7 này vào mạng Chord sẽ được tính bằng cách băm toạ độ điểm A. Chuỗi được băm để tính định danh của ô là chuỗi (2000 + $ + 2000). Hình 18: Minh hoạ thông tin vị trí của một ô trên bề mặt trái đất Bước 4: Sau khi ta đã tính được một danh sách các định danh từ các ô ở trên thì ta sẽ gửi yêu cầu tìm kiếm theo khoảng đến các máy có nhiệm vụ quản lý các định danh này. 32 Trong yêu cầu tìm kiếm theo khoảng sẽ có giới hạn thông tin trong một vùng địa lý như (kinh độ > 1000 m và vĩ độ < 2000 m) hoặc ta có thể yêu cầu trực tiếp lọc thông tin trong vòng một bán kính xác định. Yêu cầu tìm kiếm theo khoảng thực chất là một biểu thức toán học và được biểu diễn bằng ngôn ngữ XML (eXtensible Markup Language). Khi một nút trong mạng ngang hàng nhận được yêu cầu tìm kiếm thì nút này sẽ phân tích biểu thức toán học để lọc ra các bản ghi thoả mãn yêu cầu của biểu thức toán học gửi kèm và trả về kết quả cho nút yêu cầu tìm kiếm. 3.3. Cấu trúc hệ thống Hệ thống gồm có bốn thành phần đó là thiết bị di động, mạng kết nối, mạng ngang hàng có cấu trúc và hệ thống tên miền. + Thiết bị di động: Là các máy muốn tìm kiếm thông tin, các máy này phải có khả năng xác định được vị trí của mình và có thể kết nối vào mạng Internet. + Mạng kết nối: Mạng kết nối này sẽ gửi các yêu cầu của thiết bị di động và nhận kết quả trả về. + Mạng ngang hàng có cấu trúc: Mạng ngang sẽ lưu trữ, xử lý và tìm kiếm thông tin khi có yêu cầu từ thiết bị di động. Để có thể nhận được các thông điệp từ thiết bị di động thì các máy tham gia vào mạng ngang hàng sẽ mở một cổng mặc định để lắng nghe. + Hệ thống tên miền: Hệ thống này là nơi lưu trữ các thông tin về mạng ngang hàng có cấu trúc. Các thông tin này gồm địa chỉ IP và cổng lắng nghe của các máy trong mạng ngang hàng có cấu trúc. Khi thiết bị di động muốn tìm kiếm thông tin trong mạng ngang hàng có cấu trúc thì đầu tiên thiết bị di động sẽ phải truy vấn đến hệ thống tên miền này để lấy về danh sách địa chỉ IP và cổng của các máy tham gia vào mạng ngang hàng có cấu trúc. Sau khi đã có danh sách các máy tham gia vào mạng ngang hàng có cấu trúc thì thiết bị di động sẽ kết nối đến một máy đang tham gia vào mạng này để yêu cầu máy này tìm kiếm thông tin giúp mình 33 Hình 19. Cấu trúc hệ thống dịch vụ tìm kiếm thông tin dựa vào vị trí 3.4. Hoạt động của hệ thống Bước 1: Thiết bị di động sẽ lấy thông tin về vị trí của mình thông qua hệ thống định vị toàn cầu hoặc xác định vị trí thông qua vị trí của các cột sóng đài, các điểm truy cập của mạng không dây. Sau khi đã có thông tin về vị trí của người dùng thì chương trình sẽ kết hợp thông tin này với các thông tin về ngữ cảnh của người dùng (các thông tin về lịch làm việc, sở thích, giới tính, độ tuổi, thời gian trong ngày...) để tạo ra câu truy vấn tìm kiếm thông tin. 34 Truy vấn tìm kiếm được tạo định kỳ 5 phút một lần hoặc được tạo khi vị trí người dùng cách vị trí cũ 100 m. Hình 20: Minh hoạ việc tạo truy vấn theo ngữ cảnh Bước 2: Thiết bị di động sẽ truy vấn đến hệ thống tên miền để lấy về danh sách địa chỉ IP và cổng của các máy đang tham gia vào mạng ngang hàng có cấu trúc. Hình 21: Yêu cầu địa chỉ IP và cổng của các máy trong mạng ngang hàng 35 Bước 3: Sau khi có địa chỉ IP và cổng của một máy tính đang tham gia vào mạng ngang hàng có cấu trúc thì thiết bị di động sẽ kết nối đến máy tính này để gửi truy vấn tìm kiếm cho máy này. Hình 22: Yêu cầu tìm kiếm của thiết bị di động gửi lên mạng ngang hàng Bước 4: Máy tính được thiết bị di động nhờ tìm kiếm giúp thông tin sẽ tìm kiếm thông tin trong mạng ngang hàng có cấu trúc và gửi thông tin kết quả về cho thiết bị di động. Việc tìm kiếm trên mạng ngang hàng phải đảm bảo chắc chắn tìm kiếm được dữ liệu và có thể tìm kiếm theo khoảng. Để đảm bảo chắc chắn tìm kiếm được thông tin có tồn tại trên mạng thì nút được thiết bị di động nhờ sẽ gửi lại gói tin tìm kiếm khi không thấy kết quả phản hồi. Trong một phiên làm việc, nút trong mạng ngang hàng có cấu trúc sẽ lưu lại thông tin yêu cầu của các thiết bị di động nhờ tìm kiếm. Khi thiết bị di động yêu cầu tìm kiếm thì máy tính được nhờ này chỉ trả về các kết quả mới có mà không trả về kết quả đã gửi trước đó để giảm số lượng thông tin phải gửi cho thiết bị di động. 36 Hình 23: Minh hoạ mạng ngang hàng trả kết quả cho thiết bị di động Bước 5: Khi thiết bị di động nhận được kết quả tìm kiếm thì nó sẽ hiển thị kết quả cho người dùng. Kết quả hiển thị trên thiết bị di động sẽ được hiển thị dưới dạng tin nhắn như có một nhà hàng ở gần đây hoặc có thể được hiển thị trên một bản đồ để người dùng có thể thấy thông tin một cách trực quan và biết vị trí của thông tin so với vị trí của mình. 3.5. Đặc điểm của hệ thống đề xuất Hệ thống tìm kiếm thông tin theo vị trí trên mạng ngang hàng có cấu trúc đã xây dựng có đặc điểm là: - Khắc phục được các nhược điểm của mô hình dịch vụ tìm kiếm thông tin theo vị trí cũ. Với hệ thống cũ thì thường bị quá tải tại máy chủ cung cấp dịch vụ còn với hệ thống đề xuất do sử dụng mạng ngang hàng nên khắc phục được nhược điểm này. - Hệ thống có khả năng lưu trữ, xử lý và tận dụng được băng thông của mạng (đây là ưu điểm của mạng ngang hàng). - Hệ thống có thể dễ dàng mở rộng như tăng số lượng nhà cung cấp dịch vụ tham gia vào mạng ngang hàng có cấu trúc, hệ thống có thể phục vụ cho số lượng người dùng lớn mà vẫn đảm bảo thời gian phản hồi thông tin cho người dùng là nhanh. - Hệ thống đề xuất có thể lưu trữ, xử lý và tìm kiếm thông tin trên quy mô lớn. 37 3.6. Kết luận Trong chương này chúng ta đã được trình bày về mục đích, yêu cầu và phương pháp xây dựng và cấu trúc của hệ thống tìm kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc đã đề xuất. Chương này cũng trình bày chi tiết về cách biểu diễn dữ liệu theo vị trí, cách chèn dữ liệu và tìm kiếm dữ liệu vị trí trong mạng ngang hàng có cấu trúc. Qua chương này ta thấy dịch vụ tìm kiếm theo vị trí triển khai dựa trên mạng ngang hàng có thể đáp ứng được các yêu cầu của dịch vụ tìm kiếm dựa vào vị trí đó là thời gian phản hồi của dịch vụ nhanh và hệ thống có thể dễ dàng mở rộng và hệ thống cung có khả năng tìm kiếm theo khoảng (ở đây khoảng là trong một vùng địa lý và cũng có thể là giá cả của một mặt hàng trong một khoảng nào đó) Trong chương tiếp theo chúng ta sẽ thử nghiệm và đánh giá về hiệu quả của hệ thống tìm kiếm thông tin đã trình bày trong chương này thông qua các yêu cầu đã đặt ra cho hệ thống này. Các yêu cầu của hệ thống đó là có khả năng mở rộng, phục vụ được nhiều người dùng và có thể cung cấp dịch vụ thời gian thực. 38 CHƯƠNG 4. THỰC THI VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH 4.1. Kết quả thực thi chương trình + Kết quả tìm kiếm Các thông tin tìm kiếm được sẽ được hiển thị dưới dạng tin nhắn, khi người dùng quan tâm đến thông tin nào thì người dùng có thể chọn thông tin đó để hiển thị chi tiết thông tin hoặc hiển thị thông tin trên bản đồ số. Với những người dùng khác nhau thì kết quả tìm kiếm khác nhau hệ thống lọc thông tin theo ngữ cảnh của người dùng. Ví dụ như hình dưới vơi hai người dùng là người dùng A và người dùng B thì người dùng A chỉ hiển thị các thông tin liên quan đến nhà hàng còn người dùng B thì hiển thị thông tin về các trường học gần nơi hiện tại của người dùng. Hình 24: Minh hoạ giao diện hiển thị kết quả tìm kiếm thông tin Thông tin còn được hiển thị trên bản đồ số để người dùng có thể biết thêm nhiều thông tin và thấy được vị trí của thông tin. Như hình dưới thì thông tin hiểu thị là “Nhà hàng bán rau” và hình tròn màu đỏ là vị trí hiện tại của người dùng. 39 Hình 25: Giao diện hiển thị kết quả trên bản đồ 4.2. Mô hình thử nghiệm Mô hình thử nghiệm gồm có 3 máy tham gia vào mạng ngang hàng có cấu trúc Chord và một máy chạy chương trình tìm kiếm thông tin dựa vào vị trí trên chương trình PDA ảo. Hình 26: Mô hình thí nghiệm 40 Các máy Peer A, Peer B, Peer C lần lượt ở các miền mạng 192.168.10.0/24, 192.168.10.0/24 và 192.168.30.0/24. Máy tính chạy chương trình PDA ảo sẽ ở miền mạng 192.168.100.0/24. Đường truyền giữa các máy trong mạng ngang hàng (giữa Peer A và Peer B, Peer B và Peer C, Peer C và Peer A, giữa Peer A và thiết bị di động) đều bị giới hạn về băng thông và độ trễ. Để giới hạn băng thông và độ trễ mạng thì tất cả các máy tính trong thí nghiệm đều kết nối với một bộ định tuyến (trong thí nghiệm là một máy tính chạy hệ điều hành FreeBSD). + Thử nghiệm tăng dần băng thông cho tất cả các đường truyền: Thử nghiệm này sẽ tạo ra một môi trường mạng có băng thông và độ trễ giống với môi trường Internet. Thử nghiệm này dùng để đo thời gian tìm kiếm thông tin của hệ thống dịch vụ dựa vào vị trí đã xây dựng. Băng thông sẽ được điều chỉnh trên tất cả các đường truyền, tăng lần lượt là 50 kbps , 100 kbps , 150 kbps và 200 kbps. Các băng thông này tương đối giống với băng thông của mạng Internet và mạng điện thoại hiện nay. Kết quả thử nghiệm 50 Kbit/s 100 Kbit/s 150 Kbit/s 200 Kbit/s Thời gian gửi từ thiết bị di động đến Peer A 1.3 s 1.28 s 1.2 s 1.2 s Thời gian Peer A gửi kết quả cho thiết bị di động 3.019 s 2.574 s 2.6 s 2.48 s Thời gian tìm kiếm thông tin trong mạng Chord 2.743 s 1.5542 s 1.04 s 0.86 s Tổng thời gian tìm kiếm 7.06 s 5.40 s 4.84 s 4.44 s Hình 27: Kết quả thí nghiệm 41 Bảng số liệu trên được tính từ bốn lần thí nghiệm với băng thông lần lượt là 50 kbps, 100 kbps, 150 kbps và 200 kbps . Mỗi thí nghiệm được thực hiện ba lần, mỗi lần thí nghiệm sẽ gửi khoảng 10 yêu cầu tìm kiếm. Cả 10 yêu cầu tìm kiếm này sẽ được đo về thời gian gửi từ thiết bị di động cho máy A, thời gian tìm kiếm trong mạng Chord và thời gian gửi kết quả cho thiết bị di động. Sau khi đo được thời gian của cả 10 yêu cầu tìm kiếm thì các kết quả này sẽ được tính trung bình và sau ba lần thí nghiệm sẽ lại được tính trung bình một lần nữa để được các số liệu trên. Biểu đồ minh hoạ Hình 28: Đồ thị kết quả thử nghiệm Nhận xét và đánh giá Qua bảng số liệu ta thấy thời gian gửi kết quả từ máy tính tham gia vào mạng Chord cho thiết bị di động là lớn nhất vì kết quả tìm kiếm có dung lượng lớn. Các truy vấn gửi từ thiết bị di động cho máy tính tham gia vào mạng Chord là mất ít thời gian vì kích thước của truy vấn tìm kiếm là nhỏ. Thời gian tìm kiếm trong mạng Chord thì tuỳ thuộc vào số truy vấn phải gửi đi như trong mô hình thí nghiệm có thể truy vẫn tìm kiếm không phải gửi, phải gửi một lần hoặc phải gửi hai lần yêu cầu và một yêu cầu gửi trả kết quả về. 42 - Trường hợp tìm kiếm không phải gửi bất kỳ truy vấn tìm kiếm nào trên mạng Chord là trường hợp dữ liệu cần tìm của thiết bị di động đang được quản lý bởi Peer A, trường hợp này thời gian tìm kiếm là nhỏ nhất. - Trường hợp phải gửi một truy vấn là trường hợp dữ liệu cần tìm năm ở trên Peer B. Vì khi thiết bị di động yêu cầu Peer A tìm kiếm thì lúc này Peer A là Succesor của Peer B chính vì vậy Peer A sẽ gửi yêu cầu tìm kiếm cho Peer B. - Trường hợp phải gửi hai truy vấn để tìm thấy kết quả trong mạng Chord trong mô hình thí nghiệm là khi máy Peer C chứa dữ liệu cần tìm. Khi máy Peer A nhận yêu cầu tìm kiếm của thiết bị di động thì yêu cầu này chắc chắn sẽ phải gửi đến Peer B trước rồi mới được gửi đến Peer C vì truy vấn tìm kiếm bao giờ cũng phải gửi đến nút Predecessor của nút chứa dữ liệu cần tìm. 43 CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TIẾP THEO 5.1. Kết luận Ngày nay, với sự phát triển như vũ bão của công nghệ đã tạo ra nhiều thiết bị phần cứng nhỏ gọn, có khả năng lưu trữ và xử lý lớn như PDA, Pocket PC, Smart Phone.... Các thiết bị này đã trở thành một phần không thể thiếu trong cuộc sống hiện đại, chúng ta có thể thấy chúng mọi lúc, mọi nơi. Việc nghiên cứu và triển khai các ứng dụng trên các thiết bị này đang là một vấn đề nóng và cái đích cuối cùng là tạo ra một môi trường tính toán mà ở đó người dùng không còn cảm nhận được sự có mặt của công nghệ (tức là người dùng không còn cảm nhận được sự tồn tại của máy tính ở trong môi trường mình đang sống). Dịch vụ dựa vào vị trí là một trong những dịch vụ đang được triển khai thành công trên các thiết bị thông minh này. Từ yêu cầu của người dùng là tìm kiếm thông tin chính xác, phù hợp với ngữ cảnh và yêu cầu của hệ thống tìm kiếm thông tin theo vị trí là hệ thống có khả năng quản lý, lưu trữ dữ liệu phân tán, tìm kiếm thông tin nhanh trên quy mô lớn và hệ thống dễ dàng mở rộng. Khoá luận đã xây dựng một hệ thống tìm kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc trong đó thông tin tìm kiếm dựa trên ngữ cảnh của người dùng. Từ tính chất và ưu điểm của mạng ngang hàng có cấu trúc ta thấy việc triển khai dịch vụ tìm kiếm thông tin theo vị trí trên mạng ngang hàng có cấu trúc là phù hợp vì bản chất của mạng ngang hàng là quản lý, lưu trữ thông tin phân tán và ưu điểm của mạng ngang hàng có cấu trúc là có khả năng tìm kiếm nhanh, tìm kiếm dữ liệu trên quy mô lớn và hệ thống có tính mở rộng cao. Mạng ngang hàng còn có ưu điểm là có thể tận dụng được khả năng lưu trữ, xử lý và băng thông của các máy tham gia vào mạng. Khoá luận đã xây dựng chương trình cho phép tìm kiếm thông tin theo vị trí trên mạng ngang hàng có cấu trúc Chord và thử nghiệm hệ thống trong môi trường mạng có giới hạn về băng thông và độ trễ gần giống với môi trường mạng Internet và mạng điện thoại ngày nay. Kết quả thử nghiệm cho thấy dịch vụ tìm kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc đã xây dựng có thể đáp ứng được các yêu cầu của hệ thống dịch vụ dựa vào vị trí là có khả năng lưu trữ, xử lý thông tin phân tán, tìm kiếm thông tin nhanh và hệ thống có tính mở rộng cao. Đồng thời hệ thống đã xây dựng có thể tìm kiếm thông tin dựa trên ngữ cảnh của người dùng (với các người dùng khác nhau thì kết quả tìm kiếm là khác nhau). 44 5.2. Hướng phát triển tiếp theo của khoá luận Tuy đã có nhiều cố gắng nhưng khoá luận vẫn còn gặp phải nhiều vấn đề chưa giải quyết chính vì vậy trong thời gian sắp tới khoá luận sẽ tiếp tục được hoàn thiện. Khoá luận sẽ tiếp tục thử nghiệm và đánh giá kỹ lưỡng hệ thống dịch vụ tìm kiếm thông tin theo vị trí đã xây dựng và triển khai triển khai hệ thống trên thực tế để đo khả năng định vị chính xác của thiết bị di động và đo thời gian phản hồi thông tin của dịch vụ này. 45 TÀI LIỆU THAM KHẢO [1] Challenge: Ubiquitous Location-Aware Computing and the “Place Lab” Initiative Bill N. Schilit1, Anthony LaMarca1, Gaetano Borriello1,2, William G. Griswold3, David McDonald4, Edward Lazowska2, Anand Balachandran3, Jason Hong5 and Vaughn Iverson6 [2] Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications Ion Stoica_, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnany MIT Laboratory for Computer Science chord@lcs.mit.edu [3] Foundations of Location Based Services – CartouCHe – Lecture Note on LBS, V.1.0 – Stefan Steiniger, Moritz Neun And Alistair Edwardes [4] J. Gao and P. Steenkiste, "Design and Evaluation of a Distributed Scalable Content Discovery System", IEEE Journal on Selected Areas in Communications, January, January 2004 [5] M. Balazinska, H. Balakrishnan, and D. Karger, "INS/Twine: A Scalable Peer-to- Peer Architecture for Intentional Resource Discovery", In Proceedings of International Conference on Pervasive Computing, August 2002 [6] Matthew Harren, Joseph M. Hellerstein, Ryan Huebsch, Boon Thau Loo, Scott Shenker, Ion Stoica, “Complex Queries in DHT-based Peer-to-Peer Networks” [7] Pervasive Computing: Vision and Challenges M. Satyanarayanan, Carnegie Mellon University [8] [9]