Báo cáo Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc

Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 1 ĐH Công nghệ - ĐH Quốc Gia HN TRƯỜNG …………………. KHOA………………………. -----[\ [\----- Báo cáo tốt nghiệp Đề tài: SỬ DỤNG TÁC TỬ DI ĐỘNG PHÁT HIỆN DỊCH VỤ TRONG CÁC MẠNG NGANG HÀNG KHÔNG CÓ CẤU TRÚC Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 2 ĐH Công nghệ - ĐH Quốc Gia HN LỜI CẢM ƠN Tôi xin gửi lời cảm ơn tới các thầy cô trong khoa Công nghệ Thông tin trường Đại học Công nghệ, Đại học Quốc Gia Hà Nội, đặc biệt là các thầy cô trong bộ môn Mạng và truyền thông máy tính. Các thầy cô đã dạy bảo và giúp đỡ tôi rất nhiều trong quá trình học tập, giúp tôi trưởng thành hơn trong suy nghĩ và nhận thức. Đặc biệt xin chân thành cảm ơn thầy Nguyễn Đại Thọ, người đã trực tiếp hướng dẫn tôi hoàn thành khóa luận này. Sự nhiệt tình hướng dẫn của thầy là nguồn động lực lớn lao cho tôi. Tôi cũng xin chân thành cảm ơn những người bạn thân thiết đã chia sẻ những kinh nghiệm và kiến thức bổ ích cho tôi, xin cảm ơn những người thân trong gia đình đã động viên và tạo điều kiện cho tôi trong quá trình hoàn thành khóa luận. Hà Nội, tháng 5 năm 2009 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 3 ĐH Công nghệ - ĐH Quốc Gia HN TÓM TẮT NỘI DUNG Khóa luận này là kết quả nghiên cứu của tác giả về vấn đề tìm kiếm trong mạng ngang hàng.Trong khuôn khổ của khóa luận, tác giả đã trình bày tổng quan nhất về mạng ngang hàng và vấn đề tìm kiếm trong mạng ngang hàng không có cấu trúc. Phương pháp tìm kiếm đề xuất trong khóa luận được tác giả nghiên cứu dựa trên nhiều nguồn tư liệu trong đó tư liệu chính là bài báo [4] Khóa luận cũng giới thiệu về một công nghệ đang còn rất nhiều tiềm năng đó là công nghệ tác tử di động. Công nghệ hữu ích này đã giải quyết bài toán tìm kiếm hóc búa như thế nào và dựa trên những cơ sở lý thuyết nào, đó là vấn đề mà khóa luận tập trung phân tích. Để làm rõ hơn những phân tích và nghiên cứu, trong khóa luận tác giả đã trình bày phần thí nghiệm mô phỏng với dự án MATES của Evan Sultanik. Dựa trên kết quả thực nghiệm thu được, so sánh với các công thức lý thuyết tác giả đã đánh giá và đưa ra kết luận cho những nghiên cứu của mình. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 4 ĐH Công nghệ - ĐH Quốc Gia HN MỤC LỤC LỜI CẢM ƠN .................................................................................................................................... 2 TÓM TẮT NỘI DUNG ..................................................................................................................... 3 BẢNG CÁC THUẬT NGỮ VIẾT TẮT ............................................................................................ 6 DANH MỤC CÁC HÌNH VẼ BẢNG BIỂU ..................................................................................... 7 MỞ ĐẦU............................................................................................................................................ 8 Chương 1. TỔNG QUAN ................................................................................................................ 10 1.1. Tổng quan mạng ngang hàng ................................................................................................ 10 1.1.1. Định nghĩa...................................................................................................................... 10 1.1.2. Phân loại......................................................................................................................... 11 1.1.3. Ưu điểm và nhược điểm của mạng ngang hàng ............................................................. 11 1.1.4. Các ứng dụng của mạng ngang hàng.............................................................................. 12 1.2. Vấn đề tìm kiếm trong mạng ngang hàng không cấu trúc..................................................... 13 1.2.1. Một số kĩ thuật tìm kiếm phổ biến ................................................................................. 13 1.2.2. Xu hướng phát triển ....................................................................................................... 15 Chương 2. CÔNG NGHỆ TÁC TỬ DI ĐỘNG ............................................................................... 16 2.1. Tổng quan về tác tử di động.................................................................................................. 16 2.1.1. Lịch sử hình thành.......................................................................................................... 16 2.1.2. Định nghĩa...................................................................................................................... 16 2.1.3. Các đặc tính chính .......................................................................................................... 17 2.2. Nguyên lý hoạt động ............................................................................................................. 17 2.3. Ứng dụng............................................................................................................................... 18 2.3.1. Những lợi điểm của tác tử di động................................................................................. 18 2.3.2. Các ứng dụng chính........................................................................................................ 19 Chương 3. MÔ HÌNH SỬ DỤNG TÁC TỬ DI ĐỘNG PHÁT HIỆN DỊCH VỤ TRONG CÁC MẠNG NGANG HÀNG KHÔNG CẤU TRÚC ............................................................................. 21 3.1. Cơ sở lý thuyết ...................................................................................................................... 21 3.1.1. Chuỗi Markov và đường đi ngẫu nhiên.......................................................................... 22 3.1.2. Thuật toán PageRank ..................................................................................................... 24 3.2. Các tham số đánh giá hiệu năng............................................................................................ 26 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 5 ĐH Công nghệ - ĐH Quốc Gia HN 3.2.1. Xác suất tác tử tới thăm một host cho trước................................................................... 26 3.2.2. Xác suất tác tử phát hiện dịch vụ ................................................................................... 26 3.2.3. Hàm dự đoán tác tử nhìn thấy dịch vụ và thăm host ...................................................... 27 3.2.4. Thời gian kì vọng tác tử di chuyển ngẫu nhiên trở về nguồn......................................... 28 3.3. Mô hình triển khai ................................................................................................................. 29 3.4. Đánh giá mô hình .................................................................................................................. 30 Chương 4. CÁC THÍ NGHIỆM MÔ PHỎNG VÀ ĐÁNH GIÁ...................................................... 31 4.1. Chương trình mô phỏng MATES.......................................................................................... 31 4.1.1. Kiến trúc chương trình ................................................................................................... 31 4.1.2. Triển khai chương trình.................................................................................................. 34 4.1.3. Ưu điểm, nhược điểm của chương trình......................................................................... 36 4.2. Thí nghiệm đo tần suất tác tử tới thăm host .......................................................................... 37 4.3. Thí nghiệm 2 ......................................................................................................................... 39 4.4. Thí nghiệm 3 ......................................................................................................................... 43 Chương 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN..................................................................... 45 LỜI KẾT .......................................................................................................................................... 47 TÀI LIỆU THAM KHẢO................................................................................................................ 48 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 6 ĐH Công nghệ - ĐH Quốc Gia HN BẢNG CÁC THUẬT NGỮ VIẾT TẮT P2P Peer-to-Peer WWW World Wide Web URL Uniform Resource Locator CAN Content Addressable Networks DHT Distributed Hash Table TTL Time-to-Live MATES Macro Agent Transport Event-based Simulator MANET Mobile Ad-hoc Network AI Artificial Intelligence Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 7 ĐH Công nghệ - ĐH Quốc Gia HN DANH MỤC CÁC HÌNH VẼ BẢNG BIỂU Hình 1-Mô hình mạng ngang hàng .......................................................................... 10 Hình 2-Một agent di chuyển ngẫu nhiên trong mạng ngang hàng .......................... 22 Hình 3-Một vòng mô phỏng...................................................................................... 31 Hình 4-Mối tương quan giữa xấp xỉ v và tần suất tác tử tới thăm host trong 100000 lần lặp ....................................................................................................................... 39 Hình 5-Hàm dự đoán F(N) và xác suất tới thăm host của tác tử có thông tin về dịch vụ .............................................................................................................................. 42 Hình 6-Thời gian kì vọng tác tử về nguồn................................................................ 44 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 8 ĐH Công nghệ - ĐH Quốc Gia HN MỞ ĐẦU Ngày này cư dân mạng đã không còn lạ lẫm với thuật ngữ mạng ngang hàng (P2P). Mạng ngang hàng là bước phát triển từ mô hình mạng client/server truyền thống tới một mô hình mạng trong đó mỗi phần tử của mạng hoạt động với vai trò của cả client và server. Mạng ngang hàng đã tỏ rõ ưu thế và ích lợi của mình trong vấn đề lưu trữ và băng thông. Công nghệ mạng ngang hàng đã trở nên gần gũi và phổ dụng với người dùng. Nó giảm những chi phí đắt đỏ bởi những người dùng có thể sử dụng chung và chia sẻ cho nhau những phần cứng, những tài nguyên mạng. Một số hệ thống mạng ngang hàng đã trở nên quen thuộc với người dùng Internet như Napster, SETI@Home, ICQ. P2P hiện đang được ứng dụng trong rất nhiều lĩnh vực, bao gồm cả thương mại điện tử. Thu hút hàng nghìn kết nối từ người dùng mà không phải lo lắng tới vấn đề điều khiển tập trung và mở rộng, P2P vẫn phải đối mặt với vấn đề định vị tài nguyên do sự phân tán của mạng đặc biệt khi cấu trúc mạng không cố định mà thường xuyên thay đổi. Các giao thức phát hiện tài nguyên phổ biến nhất trong mạng ngang hàng vẫn là truy vấn phát tràn và bảng băm phân tán. Tuy nhiên phương thức phát tràn đặt ra bài toán tắc nghẽn trong mạng trong khi bảng băm phân tán lại yêu cầu tăng chi phí cho những cập nhật phân tán. Giao thức tìm kiếm truyền thống trong mạng ngang hàng có thể được cải tiến nếu một nút bắt đầu truy vấn có một chút thông tin về nơi tìm kiếm tài nguyên mà không phải duy trì việc băm phân tán. Một số thông tin như topo mạng, băng thông do các nút khác hỗ trợ có thể được sử dụng để cung cấp hướng tìm kiếm cho những truy vấn sau này. Sự phát triển của khoa học máy tính, trí tuệ nhân tạo và công nghệ phần mềm cho ra đời một đối tượng khá hữu dụng giải quyết vấn đề trên đó là tác tử. Một tác tử là một đoạn mã có thể tiếp tục thi hành những hành động đã được lập trình mà không cần phải chịu sự giám sát của bộ quản lý trung tâm. Các tác tử thông minh cũng có khả năng học hỏi thông tin từ môi trường để cải tiến hành động của chúng và di chuyển từ một nút này tới nút khác để thực thi những tác vụ phân tán. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 9 ĐH Công nghệ - ĐH Quốc Gia HN Tác tử phần mềm (software agent) là một hướng lập trình mới phù hợp để thực thi cơ chế tìm kiếm thông tin trong mạng ngang hàng không có cấu trúc. Trong bối cảnh đó đề tài “Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc” đi sâu vào nghiên cứu giải pháp ứng dụng tác tử di động phát hiện dịch vụ trong mạng ngang hàng không có cấu trúc dựa trên thuật toán đường đi ngẫu nhiên và những cơ sở lý thuyết toán học. Ý tưởng sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc không phải là mới. Vấn đề này đã được các nhà khoa học nghiên cứu và có những đánh giá nhất định. Trong khuôn khổ của khóa luận này, tác giả chỉ nghiên cứu và xem xét các khía cạnh liên quan tới nguyên lý, cơ chế, những lý thuyết về thuật toán của giải pháp và đánh giá những lý thuyết đã đưa ra bằng những thí nghiệm mô phỏng cụ thể. Nội dung của khóa luận sẽ bao gồm những phần sau: • Chương 1: Tìm hiểu chung về mạng ngang hàng, những phương pháp tìm kiếm truyền thống trong mạng ngang hàng. • Chương 2: Giới thiệu công nghệ tác tử di động, từ khái niệm, phân loại, các tính chất, nguyên lý hoạt động, các lợi điểm cho tới những ứng dụng của công nghệ này trong thực tiễn. • Chương 3: Nghiên cứu giải pháp sử dụng tác tử di động tìm kiếm thông tin trong các mạng ngang hàng không có cấu trúc, cơ sở lý thuyết, các tham số liên quan và những đánh giá sơ bộ về giải pháp. • Chương 4: Giới thiệu chương trình mô phỏng và cài đặt những thí nghiệm cụ thể để đánh giá giải pháp • Chương 5: Kết luận và hướng phát triển Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 10 ĐH Công nghệ - ĐH Quốc Gia HN Chương 1. TỔNG QUAN 1.1. Tổng quan mạng ngang hàng 1.1.1. Định nghĩa Mạng ngang hàng (peer to peer) là một mạng máy tính trong đó hoạt động của mạng chủ yếu dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập chung vào một số nhỏ các máy chủ tập chung như các mạng thông thường. Hay nói một cách đơn giản hơn đó là mạng ngang hàng là một mạng mà được tạo ra bởi hai hay nhiều máy tính được kết nối với nhau và chia sẻ tài nguyên mà không phải thông qua một máy chủ rành riêng. Dưới đây là một ví dụ về mạng ngang hàng. Hình 1-Mô hình mạng ngang hàng Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 11 ĐH Công nghệ - ĐH Quốc Gia HN 1.1.2. Phân loại Có thể phân loại các mạng đồng đẳng hiện nay theo tiêu chí về mức độ tập trung của chúng như sau: - Mạng ngang hàng “thuần túy”: • Các máy trạm có vai trò vừa là máy chủ vừa là máy khách • Không có máy chủ trung tâm quản lý mạng • Không có bộ định tuyến trung tâm, các máy trạm có khả năng tự định tuyến - Mạng ngang hàng “lai”: • Có một máy chủ trung tâm dùng để lưu trữ thông tin của các máy trạm và trả lời các truy vấn thông tin này. • Các máy trạm có vai trò lưu trữ thông tin, tài nguyên được chia sẻ, cung cấp các thông tin về chia sẻ tài nguyên của nó cho máy chủ. • Sử dụng các trạm định tuyến để xác định địa chỉ IP của các máy trạm. Các mạng ngang hàng "thuần túy" có thể kể là Gnutella và Freenet. Các mạng ngang hàng lai có nhiều loại: mạng P2P tập trung như Napste, mạng P2P phân tán như KazaA, mạng P2P có cấu trúc như CAN, mạng P2P không cấu trúc như Gnutella. 1.1.3. Ưu điểm và nhược điểm của mạng ngang hàng 1.1.3.1. Ưu điểm Mạng ngang hàng thể hiện rõ ưu thế so với mạng theo mô hình Client/Server.Nó tận dụng được tiềm năng từ "cạnh" của Internet còn ít được khai thác. Ví dụ chỉ cần từ 10 triệu máy tính 100 MHz nối vào mạng cùng một lúc, mỗi máy có dung lượng lưu trữ 100 MB, băng thông 1000 bps, 10% khả năng xử lý chưa được sử dụng đến. Nó không dựa trên server tập trung và thường hoạt động ngoài hệ thống tên miền mà sử dụng kiến trúc phẳng, tính kết nối cao để các máy tự tìm ra nhau, xác định nơi cung cấp dịch vụ và chủ động yêu cầu dịch vụ theo ý muốn. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 12 ĐH Công nghệ - ĐH Quốc Gia HN Kiến trúc mạng ngang hàng cho phép phân tán trách nhiệm cung cấp dịch vụ đến tất cả các điểm nút trên mạng. Chính vì thế đã loại bỏ vấn đề ngừng trệ dịch vụ do nơi duy nhất cung cấp bị sự cố. Đó chính là giải pháp khả biến hơn trong việc cung cấp dịch vụ. Mạng ngang hàng tận dụng băng thông trên toàn bộ mạng bởi vì các máy tính giao tiếp qua nhiều đường truyền khác nhau nên đã giảm đáng kể hiện tượng nghẽn tắc mạng. Mạng ngang hàng phục vụ tài nguyên với độ sẵn sàng cao, chi phí thấp đồng thời nâng cao hiệu suất khai thác trong khi đó thì mạng theo mô hình Client-Server thì phải cần thêm băng thông, thiết bị, phương tiện. 1.1.3.2. Nhược điểm Do tính các máy tính trong mạng có vai trò ngang nhau nên yêu cầu dịch vụ cũng được đáp ứng một cách tùy biến. Ví dụ, các client yêu cầu cùng một dịch vụ có thể nối tới các máy khác nhau, qua các đường truyền khác nhau, với kết quả nhận được khác nhau. Một nhược điểm nữa của mạng ngang hàng là các yêu cầu từ các máy có thể không nhận được kết quả ngay và có thể không được đáp ứng do các tài nguyên có thể biến mất do máy cung cấp ngắt kết nối trong khi đó với Client/Server thì hầu như tài nguyên liên tục hiện diện. 1.1.4. Các ứng dụng của mạng ngang hàng Ứng dụng lớn nhất có thể kể đến của mạng ngang hàng là ứng dụng chia sẻ file. Có hai công nghệ mạng ngang hàng trong lĩnh vực chia sẻ file điển hình là Napster và Gnutenlla. Trong khi Napster cho phép người dùng trao đổi các file MP3 với nhau và có thêm chức năng gửi tin nhắn tức thời thì Gnutenlla có thể cho phép chia sẻ mọi kiểu file. Napster sử dụng kiến trúc mạng ngang hàng lai ghép trong đó server lưu danh sách các file MP3 mỗi người dùng chia sẻ, cho phép người dùng tìm kiếm một file cụ thể và các file được trao đổi trực tiếp giữa các điểm nút. Gnutella thì không sử dụng server. Ngoài ứng dụng chia sẻ file, mạng ngang hàng còn có ứng dụng tính toán phân tán. SETI@Home và Distributed.net là hai ứng dụng điển hình của tính toán phân tán. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 13 ĐH Công nghệ - ĐH Quốc Gia HN 1.2. Vấn đề tìm kiếm trong mạng ngang hàng không cấu trúc 1.2.1. Một số kĩ thuật tìm kiếm phổ biến 1.2.1.1. Phát tràn Phát tràn là chiến lược tìm kiếm đơn giản nhất và thông dụng nhất trong mạng ngang hàng. Bởi thế mà mạng Gnutella đã sử dụng phương pháp tìm kiếm này. Việc tìm kiếm được tiến hành như sau: đầu tiền nút cần tìm gửi đi một thông điệp do thám tới tất cả các hàng xóm của nó. Các hàng xóm này sẽ chuyển những bản sao của thông điệp kia tới những nút hàng xóm kế tiếp trừ nút hàng xóm mà đã chuyển thông điệp tới nó. Cứ như thế, công cuộc tìm kiếm được tiếp diễn. Trong quá trình thực thi phương pháp này cho thấy một số hạn chế và nhược điểm. Hạn chế lớn nhất đó là vấn đề truyền tải. Những thành phần tham dự vào mạng như những máy tính cá nhân tại gia hay ở cơ quan là những thành phần chịu ảnh hưởng nhiều nhất. Nếu một máy tính phải xử lý rất nhiều gián đoạn mạng khi tham gia vào mạng ngang hàng, người dùng chắc sẽ chẳng do dự mà chọn giải pháp quay trở về với công việc thực tại hơn là cố gắng kết nối vào mạng chỉ để giải trí. Đó là một lý do làm giảm khả năng và sự hữu dụng của mạng ngang hàng. Thật không may là thuật toán tìm kiếm phát tràn lại làm gia tăng vấn đề này. Gnutella đã sử dụng TTL(Time-To-Live) để điều khiển số chặng mà truy vấn có thể lan truyền. Tuy nhiên việc chọn số TTL làm sao cho thích hợp lại là cả vấn đề. Nếu TTL quá cao, các nút không cần thiết sẽ trở thành gánh nặng cho mạng còn nếu TTL quá thấp, nút có thể không tìm được đối tượng nó cần. Một vấn đề nữa với phương thức phát tràn này là có rất nhiều bản sao các thông điệp được phát tán ra. Điều này đồng nghĩa với việc tăng chi phí trên mạng. Những bản sao này gia tăng các quá trình xử lý ngắt tại mỗi nút nhận nhưng không hề làm tăng cơ hội tìm thấy đối tượng cần. 1.2.1.2. Mở rộng vòng Khi phát tràn lộ rõ những hạn chế của mình thì những nhà phát triển mạng đã cố gắng tìm ra những phương pháp thích hợp hơn, tối ưu hơn. Đầu tiên họ nhắm vào vấn đề chọn TTL. Với phương pháp vòng mở rộng thì một nút bắt đầu phát tràn Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 14 ĐH Công nghệ - ĐH Quốc Gia HN với số TTL nhỏ và đợi xem việc tìm kiếm có thành công hay không. Nếu câu trả lời là có thì nút sẽ dừng việc tìm kiếm. Ngược lại, nút sẽ tăng số TTL và bắt đầu lượt phát tràn khác. Tiến trình này lặp lại cho tới khi đối tượng được tìm thấy. Kết quả thực nghiệm chỉ ra rằng, mặc dù liên tục lặp lại quá trình phát tràn đó nhưng so với phương pháp phát tràn truyền thống mà số TTL là cố định thì phương pháp mở rộng vòng vẫn giảm đáng kể tải mạng. Tuy nhiên có thể thấy phương pháp này sẽ làm tăng độ trễ trong việc tìm ra đối tượng do nó phụ thuộc khá nhiều vào thời gian chờ. Mặc dù phương pháp mở rộng vòng đã giải quyết được vấn đề chọn số TTL, nhưng nó chưa giải quyết được vấn đề bản sao thông điệp. Để giảm số lượng bản sao thông điệp ta thử một hướng tiếp cận khác, đó là đường đi ngẫu nhiên. 1.2.1.3. Di chuyển ngẫu nhiên Di chuyển ngẫu nhiên được đánh giá là một kĩ thuật tốt. Nó gửi một thông điệp truy vấn tới một hàng xóm được chọn ngẫu nhiên tại mỗi bước cho tới khi đối tượng được tìm ra. Ta gọi những thông điệp này là “những người đi đường”. Khi sử dụng phương pháp di chuyển ngẫu nhiên chuẩn (chỉ với một người đi đường), tải mạng sẽ được giảm xuống một cách đáng kể so với phương pháp mở rộng vòng. Tất nhiên nó sẽ kéo theo độ trễ trong việc tìm ra đối tượng lớn hơn. Để giảm độ trễ này ta sử dụng nhiều “người đi đường” hơn. Thay vì gửi đi một thông điệp truy vấn, nút yêu cầu sẽ gửi đi k thông điệp truy vấn và mỗi thông điệp này lại tự nó di chuyển một các ngẫu nhiên. Dự tính là với k “người đi đường” sau T bước sẽ đi qua một số nút tương tự như số nút mà một người đi đường đi được sau kT bước. Và thực nghiệm quả đã chứng minh điều này. Như vậy dùng k “người đi đường” hiệu quả công việc sẽ tăng lên gấp k lần và độ trễ tìm kiếm cũng giảm đi rất nhiều. Để giới hạn đường đi trong trường hợp có nhiều “người đi đường” các nhà nghiên cứu đã thử nghiệm hai phương pháp: dùng TTL và kiểm tra. Phương pháp dùng số TTL tương tự như phát tràn, mỗi đường đi ngẫu nhiên sẽ dừng sau một số chặng xác định. Phương pháp kiểm tra thì khác, một “người đi đường” sẽ kiểm tra một cách định kì yêu cầu đầu tiên trước khi tiếp tục di chuyển một cách ngẫu nhiên tới nút khác. Thực ra phương pháp kiểm tra vẫn sử dụng TTL, nhưng số TTL rất lớn và thường dùng để tránh lặp. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 15 ĐH Công nghệ - ĐH Quốc Gia HN Ở phần sau của khóa luận ta cũng sẽ nghiên cứu phương pháp di chuyển ngẫu nhiên nhưng có sử dụng cơ chế khác. 1.2.2. Xu hướng phát triển Theo những phân tích ở trên ta có thể thấy phương pháp di chuyển ngẫu nhiên với k người đi đường có nhiều khả năng mở rộng hơn phương pháp phát tràn. Chìa khóa cho tìm kiếm mở rộng trong mạng không có cấu trúc là bao quát được các nút đúng một cách nhanh nhất có thể và với chi phí thấp nhất có thể. Trong mạng không có cấu trúc, cách duy nhất để tìm các đối tượng là tới thăm tất cả các nút, như thế có thể nói chắc chắn là một nút sẽ có đối tượng cần tìm. Tuy nhiên, để đến được nút yêu cầu thì một nút cần chú ý tới những vấn đề sau: Tối giản những thông điệp lặp. Mỗi truy vấn nên tới thăm một nút đúng một lần. Càng nhiều lần tới thăm càng tốn nhiều chi phí và tăng tải mạng. Số nút tới thăm trong quá trình tìm kiếm nên nhỏ. Trong mỗi bước di chuyển tiếp sau của quá trình tìm kiếm nên hạn chế số nút đã tới thăm. Điều này có lẽ là khác nhau cơ bản giữa phương pháp phát tràn và phương pháp đường đi ngẫu nhiên có nhiều người đi đường. Trong phát tràn thì số nút tới thăm tăng theo hàm mũ còn trong đường đi ngẫu nhiên ở mỗi bước lặp sau thì số nút tới thăm tăng theo một hằng số. Khi mỗi lần tìm kiếm chỉ yêu cầu chính xác một số nút để tới thăm thì các nút phụ được tới thăm trong phương pháp phát tràn chỉ làm tăng tải trên mỗi nút. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 16 ĐH Công nghệ - ĐH Quốc Gia HN Chương 2. CÔNG NGHỆ TÁC TỬ DI ĐỘNG 2.1. Tổng quan về tác tử di động 2.1.1. Lịch sử hình thành Với sự phát triển đa dạng và phong phú của công nghệ thông tin, từng ngày từng giờ đang ra đời hàng loạt những sản phẩm mới, tiện ích hơn, thông minh hơn, hữu dụng hơn và nhỏ gọn hơn, đặc biệt là những sản phẩm có khả năng hoạt động một mình và kết hợp với những chương trình khác. Là một sự gặp nhau giữa trí tuệ nhân tạo và công nghệ phần mềm, các software agent là một chương trình như thế. Tác tử di động là một loại software agent. Khái niệm “software agent” được Mark Sidell và Chuck Knuff đưa ra năm 1994. Năm 1995 phiên bản đầu tiên của software agent xuất hiện.Tới những năm 1975 thì kĩ thuật lập trình phổ biến là lập trình hướng cấu trúc, những năm 1982 kĩ thuật lập trình phổ biến là lập tình hướng đối tượng và đến khi agent ra đời thì nó đã mở ra một phương pháp lập trình mới. 2.1.2. Định nghĩa Để hiểu khái niệm về tác tử di động, ta đi từ khái niệm tác tử (agent). Khái niệm agent theo Nawana đề xuất năm 1996 là một thành phần phần mềm hoặc phần cứng có khả năng hoạt động chính xác để thay mặt chủ nhân hoàn thành nhiệm vụ. Nó là sự kết hợp của nhiều kĩ thuật tin học hiện đại như: kĩ thuật cơ sở dữ liệu và cơ sở tri thức, máy học, AI và khoa học nhận dạng, phục hồi thông tin, các hệ thống phân tán, mobile code. Mobile agent (tác tử di động) là từ ghép của mobile (tính di động) và agent (tác tử). Xét trong bối cảnh mạng internet một mobile agent là một chương trình có khả năng di chuyển một cách tự trị từ nút mạng này sang nút mạng khác và thực hiện các xử lý thay thế con người hoàn thành nhiệm vụ. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 17 ĐH Công nghệ - ĐH Quốc Gia HN 2.1.3. Các đặc tính chính - Tính tự trị: là khả năng tự kiểm soát bản thân của agent sau khi được giao việc mà không cần sự can thiệp nào của người dùng hoặc agent khác. Khả năng này của agent chủ yếu được quyết định bởi tri thức trang bị cho agent. Để đánh giá tính tự trị của agent người ta thường dựa vào hai đặc tính là hướng đích (goal-oriented) và tính chủ động (pro-activeness). - Tính di động: là khả năng chuyển từ môi trường thi hành này sang môi trường thi hành khác. Có thể phân tính di động thành hai loại: di động mạnh và di động yếu. Di động mạnh là khả năng mà hệ thống có thể di chuyển cả mã chương trình và trạng thái thi hành của agent tới một môi trường khác còn di động yếu là khả năng mà hệ thống chỉ có thể di chuyển mã chương trình giữa các môi trường thi hành với nhau, mã nguồn có thể mang kèm một số dữ liệu khởi tạo nhưng trạng thái thi hành thì không thể di chuyển. - Khả năng cộng tác: là khả năng liên lạc, phối hợp hoạt động của các agent với các agent khác cùng môi trường hay với các loại đối tượng khác trong những môi trường khác. - Tính thích nghi: là khả năng agent có thể hoạt động trên những môi trường lạ và cảm nhận được những thay đổi 2.2. Nguyên lý hoạt động Về thực chất agent chỉ là một đoạn mã, nó cũng có vòng đời và tùy vào loại và mục đích sử dụng mà agent có chi tiết vòng đời khác nhau. Tuy nhiên vòng đời của agent vẫn bao gồm những điểm chính sau: Khi agent được tạo ra trên một host cũng là lúc vòng đời của agent bắt đầu. Trong khoảng thời gian này thì các trạng thái ban đầu của agent cũng có thể được khởi tạo theo. Khi đã sẵn sàng hoặc được lệnh di trú tới một host khác nằm trong đường đi của agent, agent sẽ lưu lại trạng thái hiện hành của mình và tiến hành quá trình di trú. Nếu quá trình di trú thất bại, agent sẽ tự ngừng hoạt động. Sau một khoảng thời gian định trước hay được kích hoạt nó sẽ tiến hành lại quá trình di trú tới host khác. Khi đã di trú tới host mới thành công, agent sẽ phục hồi trạng thái, khi đó nó bắt đầu thực thi nhiệm vụ của mình. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 18 ĐH Công nghệ - ĐH Quốc Gia HN Sau khi agent hoàn thành nhiệm vụ, nó có thể bị hủy hoặc chuyển sang trạng thái ngủ đông cho đến khi có yêu cầu từ bộ đếm trong chính bản thân agent. Khi đó agent sẽ lưu lại trạng thái của nó và di trú tới một host khác. Vòng đời agent lặp lại theo quy trình như trên cho đến khi nó hoàn thành nhiệm vụ hoặc hết thời gian hoạt động thì agent sẽ bị hủy. 2.3. Ứng dụng 2.3.1. Những lợi điểm của tác tử di động Tác tử di động có rất nhiều lợi điểm. Dưới đây là một số lợi điểm chính. - Giảm tải mạng Với phương châm là “mang xử lý tới nơi chứa dữ liệu hơn là mang dữ liệu đến chỗ xử lý” kỹ thuật Mobile Agent cho phép người dùng đóng gói cuộc trao đổi, gửi nó đến máy đích và thực hiện xử lý dữ liệu, trao đổi cục bộ tại đó. Có thể thấy những dòng dữ liệu thô trên mạng sẽ được giảm xuống đáng kể, điều này đồng nghĩa với tải mạng cũng được giảm xuống. - Đóng gói các giao thức Khi dữ liệu được trao đổi trong hệ thống phân tán, việc truyền và nhận dữ liệu phải được mã hóa bởi các giao thức cần thiết. Các giao thức này được sở hữu bởi mỗi máy trong hệ thống. Tuy nhiên, một khi các giao thức phải tiến hóa để phù hợp với những yêu cầu mới về bảo mật hoặc tính hiệu quả, chúng bắt đầu trở nên cồng kềnh, nặng nề và trở thành vấn đề nan giải. Với giải pháp Mobile Agent, các agent có thể mang trên mình các giao thức thích hợp và di chuyên tới các máy ở xa để thiết lập các kênh truyền nhận thông tin tương ứng. - Thi hành không đồng bộ và tự trị Hãy tưởng tượng khi agent được nhúng các tác vụ cần thực hiện và được gửi lên mạng. Lúc này agent trở nên độc lập thi hành không đồng bộ và có khả năng tự trị. Các thiết bị di động sau đó có thể kết nối trở lại để đón agent về. - Khắc phục sự trễ mạng Việc điều khiển các hệ thống có quy mô lớn thông qua mạng sẽ phải chấp nhận một giới hạn trễ nào đó. Tuy nhiên điều này là không được phép nếu đó là những hệ thống thời gian thực như điều khiển robot, quy trình sản xuất…Với các Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 19 ĐH Công nghệ - ĐH Quốc Gia HN agent có thể được gửi đi từ một trung tâm điều khiển và hành động cục bộ, tự trị, trực tiếp thi hành các chỉ dẫn của người điều khiển thì vấn đề này xem ra đã có thể được giải quyết. 2.3.2. Các ứng dụng chính - Thu thập dữ liệu phân tán Trong trường hợp có nhu cầu truy vấn phức tạp, chuyên biệt và liên quan đến nhiều nguồn dữ liệu phân tán, không đồng nhất, việc cử các mobile agent di chuyển đến các nguồn tin để khai thác tại chỗ và quay về với những thông tin cần thiết sẽ cho phép giảm tải mạng và giải quyết tốt hơn bài toán tương thích. Đã có những dự án thuộc loại này như Distributed Query Processing via Mobile Agents (University of Maryland), DB Access (University of Cyprus). - Thương mại điện tử Các ứng dụng thương mại điện tử là môi trường hấp dẫn để phát triển công nghệ mobile agents. Một giao dịch thương mại điện tử có thể bao gồm sự thương lượng với các thực thể ở xa và có thể đòi hỏi truy cập nguồn thông tin liên tục thay đổi. Thực tế đó nảy sinh nhu cầu thay đổi hành vi của các thực thể để đạt được một nghi thức chung trong việc thương lượng. Hơn nữa việc di chuyển các thành phần của ứng dụng tiến gần đến nguồn thông tin thích hợp cho giao dịch cũng được quan tâm. - Quản trị hệ thống mạng Đối với những hệ thống mạng lớn, việc chuẩn đoán lỗi, duy trì sự ổn định của hệ thống là các công việc rất khó khăn. Việc ứng dụng mobile agent vào việc quản trị mạng sẽ giúp cho các công việc chuẩn đoán lỗi và duy trì từ xa sự ổn định của hệ thống được dễ dàng hơn. - Giám sát và phân tán thông tin Các mobile agents là một minh họa cho mô hình Internet push. Các agent có thể phổ biến tin tức và cập nhật phần mềm tự động cho các nhà sản xuất. Các agent mang các thành phần phần mềm cũng như các thủ tục cần thiết đến các máy cá nhân của khách hàng và tự cập nhật phần mềm trên máy đó. Mô hình này giúp cho nhà sản xuất chủ động hơn trong việc phục vụ khách hàng để đảm bảo chất lượng dịch vụ của mình. Mặt khác, các ứng dụng loại này cũng tỏ ra hiệu quả đối với các mạng Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 20 ĐH Công nghệ - ĐH Quốc Gia HN cục bộ hay các chương trình quản lý quy trình hoạt động, sản xuất…để giúp người quản trị giám sát các hệ thống con. Có một số dự án ứng dụng loại này như Banking Dartflow [CAI-96], Autopilot [FOS-99]. - Xử lý song song Vì các mobile agent có thể tạo ra nhiều bản sao của nó trên mạng, tận dụng đặc tính này mà mobile agent được ứng dụng để quản trị các tác vụ song song. Một ứng dụng đòi hỏi quá nhiều tài nguyên bộ xử lý có thể được phấn bố cho các mobile agent mang đi thực hiện trên nhiều máy tính khác nhau để tận dụng các tài nguyên rảnh rỗi và cân bằng tải. Một ví dụ của loại ứng dụng này là Hệ mobile agents không đồng nhất [HER-99] Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 21 ĐH Công nghệ - ĐH Quốc Gia HN Chương 3. MÔ HÌNH SỬ DỤNG TÁC TỬ DI ĐỘNG PHÁT HIỆN DỊCH VỤ TRONG CÁC MẠNG NGANG HÀNG KHÔNG CẤU TRÚC Sự truyền thông từ một nút tới các hàng xóm của nó trong mạng ad-hoc và mạng ngang hàng vốn đã bị hạn chế, thế nên sự truyền thông trên nhiều chặng trong mạng càng trở nên khó khăn, điển hình là vấn đề định tuyến. Những nghiên cứu gần đây tập trung vào vấn đề sử dụng tác tử di động để định tuyến trong mạng ad-hoc. Hầu hết các phương pháp dựa vào việc sử dụng tần suất của tác tử tới thăm mỗi nút để dự đoán topo mạng. Những nghiên cứu sâu hơn thì tập trung vào vấn đề tìm kiếm dịch vụ phân tán trong mạng. Dịch vụ phân tán có thể bao gồm cả những tác tử tĩnh và tác tử di động. Chủ yếu do sự phát triển của công nghệ chia sẻ file ngang hàng, những nghiên cứu quan trọng đã được tiến hành trong lĩnh vực mạng động. Kiến trúc tìm kiếm dịch vụ đã từng tồn tại trong những mạng như vậy, tuy nhiên khi muốn sử dụng lại cần phải đăng kí. Trong mạng CAN (Content-Addressable Network) kĩ thuật tìm kiếm cũng đã được áp dụng trong vấn đề định vị. Hướng tiếp tìm kiếm cơ bản thường giả định rằng các tác tử có thể tự di trú từ một máy này tới một máy khác trong mạng. Các phương pháp dựa trên tác tử để tìm kiếm dịch vụ đã được triển khai. Thêm vào đó CANs và DHTs giả sử rằng chỉ mục và các phần tử dữ liệu là cố định, không có cái nào trong những hướng tiếp cận này đề cập trực tiếp tới vấn đề về xác định vị trí các dịch vụ di động. Trong chương 2 ta cũng đã biết được rất nhiều ưu điểm của tác tử di động. Giải pháp dựa trên tác tử di động sẽ là một lựa chọn hợp lý cho bài toán tìm kiếm đang còn gặp nhiều khó khăn. 3.1. Cơ sở lý thuyết Phát hiện dịch vụ có thể được hiểu chính xác nhờ mô hình triển khai một tập các tác tử A, ngẫu nhiên trên đường đi của mình chọn một tập các hosts H trong mạng ngang hàng. Một các đầy hình ảnh có thể tưởng tượng rằng các agent hoạt Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 22 ĐH Công nghệ - ĐH Quốc Gia HN động như những chú ong, công việc của chúng là “thụ phấn” cho mạng với những thông tin về vị trí của dịch vụ. Hình 2-Một agent di chuyển ngẫu nhiên trong mạng ngang hàng Hướng tiếp cận này có ba lợi điểm quan trọng đó là không tốn băng thông mạng, các dịch vụ không cần phải được đăng kí và tính chất của đường đi ngẫu nhiên có liên quan nhiều tới những mô hình toán học, đó là những cơ sở khoa học chắc chắn. Dưới đây ta sẽ áp dụng những mô hình toán học để mô tả những trạng thái của các tác tử này. Ta sử dụng các tính chất của chuỗi Markov để mô hình hóa xác suất một tác tử sẽ tới thăm một host xác định, phân bố nhị phân để mô hình hóa xác suất một tác tử nhìn thấy một dịch vụ và một phân bố nhị phân khác để tính giá trị kì vọng số tác tử sẽ tới thăm một host trong một khoảng thời gian. 3.1.1. Chuỗi Markov và di chuyển ngẫu nhiên 3.1.1.1. Chuỗi Markov Nhắc lại một chút về lý thuyết giải tích, Chuỗi Markov là một quá trình thống kê ngẫu nhiên thời gian rời rạc. Đó là một tập các trạng thái S là các phần tử của ma trận xác suất chuyển P. S có thể là hữu hạn hoặc vô hạn đếm được. Ma trận xác suất chuyển P có một hàng và một cột cho mỗi trạng thái trong tập S. Mỗi phần tử của ma trận này Pij là xác suất chuyển sang trạng thái j từ trạng thái hiện tại là trạng thái i. Như vậy 10:, ≤≤∈∀ PSji JK và ∑ = j ijP 1 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 23 ĐH Công nghệ - ĐH Quốc Gia HN Một tính chất quan trọng của chuỗi Markov là trạng thái tương lai chỉ phụ thuộc vào trạng thái hiện thời và nó không xảy ra tại thời điểm hiện tại. Theo luận điểm đó có thể thấy xác suất chuyển Pij chỉ phụ thuộc vào trạng thái i. Chuỗi Markov có nhiều ứng dụng trong nhiều lĩnh vực khác nhau. Với các ứng dụng Internet thì PageRank là thuật toán điển hình sử dụng mô hình chuỗi Markov mà ta sẽ tìm hiểu trong phần sau. 3.1.1.2. Di chuyển ngẫu nhiên và dự đoán tác tử tới thăm một host Di chuyển ngẫu nhiên theo đồ thị về bản chất là chuỗi Markov hữu hạn. Nó có rất nhiều tính chất tương tự như chuỗi Markov. Thực nghiệm của Gkantsidis đã chỉ ra rằng với việc tìm kiếm một thông tin xuất hiện thường xuyên trong mạng thì với lượng thông điệp là ngang nhau, phương pháp đường đi ngẫu nhiên chắc chắn thực hiện tốt hơn phương pháp truyền thống phát tràn. Môi trường để tác tử thực thi nhiệm vụ là mạng ngang hàng động, đầy tính ngẫu nhiên, luôn thay đổi. Ở đó tồn tại độ trễ của sự nhận biết những thay đổi về topo mạng. Vì vậy mục đích cơ bản của các tác tử cũng là di chuyển một cách ngẫu nhiên trong mạng để thu thập thông tin. Hành động của các tác tử chỉ bao gồm việc di chuyển ngẫu nhiên từ nút mạng hiện thời tới một hàng xóm của nó. Tại mỗi nút, tác tử truy vấn dịch vụ, lưu trữ dữ liệu trong bộ nhớ. Tần suất tác tử tới thăm một host có thể được dự đoán nhờ hàm F(N). Hàm F(N) cho biết xác suất một tác tử a ∈ A với thông tin về dich vụ s ∈ S sẽ tới thăm một host h ∈ H trong thời gian t. N là một mô tả trạng thái cục bộ bao gồm các thành phần: t – độ dài khoảng thời gian v – xác suất một tác tử sẽ ở tại host h η – số thể hiện của dịch vụ s |H| - tập các host có trong mạng |A| - tập các tác tử l – thời gian trung bình cần để một tác tử di chuyển từ một nút hàng xóm tới một nút khác Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 24 ĐH Công nghệ - ĐH Quốc Gia HN τ – thời gian lớn nhất mà tác tử nhìn thấy dịch vụ s F(N) được định nghĩa như một ánh xạ từ N tới xác suất thực: F: (t, v, η, |H|, |A|, l, τ ) α [0,1] (1) Theo đánh giá trực quan thì |A| càng lớn, |H| và l càng nhỏ sẽ có càng nhiều tác tử tới thăm host. Kalman Filtering là phương pháp đánh giá trạng thái của một hệ thống động tuyến tính từ một chuỗi các phép đo. Tuy nhiên tần suất tác tử mang thông tin tới thăm một host sẽ không theo phân bố Gaussian tuyến tính, đặc biệt là với mạng có độ thay đổi lớn, vì thế hàm F(N) không thể được dự đoán bằng phương pháp tương tự như Kalman Filtering. 3.1.2. Thuật toán PageRank Để dự đoán tần suất tới thăm một host xác định của các tác tử di chuyển ngẫu nhiên, ta cần tính xác suất một tác tử sẽ tới thăm một host xác định tại một thời điểm nào đó. PageRank là thuật toán giúp ta làm việc đó. PageRank là thuật toán phân tích liên kết để đánh giá trọng số của mỗi phần tử trong tập các tài liệu siêu liên kết ví dụ như WWW. Thuật toán này được sử dụng trong công cụ tìm kiếm nổi tiếng Google. Nó sẽ xác định xác suất mà một người lướt web ngẫu nhiên sẽ thăm một trang tại một thời điểm nào đó. Nếu N là số trang web đã biết và một trang i có ki liên kết thì xác suất chuyển từ trang i tới các trang khác mà i liên kết tới là và cho các trang mà i không có liên kết tới. Trong đó tham số α thường được lấy giá trị bằng 0.85. PageRank dùng chuỗi Markov để mô hình hóa đường đi ngẫu nhiên theo đồ thị của mạng Internet. Thuật toán này cũng được áp dụng để tính xác suất một tác tử sẽ tới thăm một host xác định tại một thời điểm nào đó. Nó lợi dụng tính dừng của đồ thị, tính toán vecto đặc trưng πρcủa ma trận kề J. Vecto đặc trưng πρ tương ứng với giá trị riêng 1λ bởi phương trình πρJ = 1λ πρ và πρ chứa xác suất một agent di chuyển ngẫu nhiên sẽ ở trên một nút bất kì. Trong trường hợp liên quan tới đường đi ngẫu nhiên thì J là ma trận xác suất chuyển từ host này tới host khác trong mạng. Ma trận J có dạng: Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 25 ĐH Công nghệ - ĐH Quốc Gia HN J = ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ nnnn inijii n n hhh hhhh hhhh hhhh .......... ...................... ....... ..................... ... ... 21 21 2232221 1131211 trong đó hij là xác suất chuyển từ host i sang host j 1π là xác suất mà tác tử ở tại host 1. Theo dự đoán xác suất tác tử ở tại host 2 là 2π = 1π J . Xác suất tác tử ở tại host 3 là : 3π = 2π J = 1π J2 Cứ như thế, xác suất tác tử ở tại host n là : nπ = 1π 1−nJ Thuật toán PageRank với đầu vào là ma trận kề J đại diện cho mạng, d là số thực nằm trong khoảng [0,1] (thường lấy giá trị 0.85), iterations là số lần lặp và tất cả các phần tử của πρ sẽ được khởi tạo là || 1 H . Phát biểu thuật toán PageRank như sau: Thuật toán được lặp iterations bước, tại mỗi bước, duyệt các phần tử của tập |H| . Với mỗi phần tử này xét các liên kết của nó tới các nút khác, nếu có bao nhiêu liên kết thì tăng biến đếm lên từng đó. Giá trị của πρ tại các nút hàng xóm sẽ chia đều cho số liên kết này và cộng dồn vào biến đếm sum. Và giá trị πρ tại các nút hiện thời sẽ bằng tổng của (1-d) và d*sum. Dưới đây là đoạn giả mã cho thuật toán for i = 1 to iterations do for j = 1 to |H| do sum ← 0 for k = 1 to |H| do if Jk,j > 0 then links ← |{x| (1 ≤ x ≤ |H|) ∧ (Jk,x > 0)}| if links > 0 then sum ← sum + πρk ÷ links πρj ← (1-d) + d*sum Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 26 ĐH Công nghệ - ĐH Quốc Gia HN Theo thuật toán PageRank ở trên, πρh chính là xác suất mà một tác tử a∈A nằm trên một host xác định h ∈ H tại một thời gian cho trước. Trong toán học πρ có thể được tính bằng vecto đặc trưng của (dJT) trong đó J đã được chuẩn hóa. 3.2. Các tham số đánh giá hiệu năng 3.2.1. Xác suất tác tử tới thăm một host cho trước Trong trường hợp |A| = 1 thì ta có thể sử dụng πρ để ước lượng v: vˆ = πρh (3) Nếu |A| > 1 thì cần phải sử dụng một phân bố nhị phân để tính toán vˆ . Có thể thấy vˆ bằng 1 trừ đi xác suất mà không có |A| tác tử sẽ tới thăm trong thời gian t. vˆ = 1 – (1 – (1 – (1 - πρh)|A| ) )t = 1 – (1 - πρh)|A| t (4) Tuy nhiên sẽ không đủ nếu chỉ dựa trên vˆ để định nghĩa F(N) vì không phải tất cả các tác tử tới thăm host đều có đầy đủ dữ liệu về dịch vụ được định vị. 3.2.2. Xác suất tác tử phát hiện dịch vụ v đưa ra một cơ chế dự đoán trước số tác tử di chuyển ngẫu nhiên sẽ thăm một host. Tuy nhiên, v không được tính cho trường hợp các tác tử này có thể chưa nhìn thấy dịch vụ s. H ∈ H là một tập các host mà một tác nhân ghé thăm trong thời gian τ và là tập các dịch vụ mà tác nhân tìm thấy trong thời gian τ . Giá trị kỳ vọng của số lượng các host mà tác nhân sẽ ghé thăm là : = ⎥⎦ ⎥⎢⎣ ⎢ λ τ (5) Với η là số thể hiện của dịch vụ s thì xác suất một thể hiện của dịch vụ tồn tại ở một host ngẫu nhiên là H η . Xác suất mà một tác tử di chuyển ngẫu nhiên trong mạng sẽ phát hiện ra một thể hiện của dịch vụ s trong thời gian τ có thể được mô hình hóa bằng phân bố nhị phân của |H| phép thử. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 27 ĐH Công nghệ - ĐH Quốc Gia HN P(n| |H|) = nHn HHn − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ Η ηη 1 (6) Trong đó n là số thể hiện của dịch vụ s được tìm thấy: n = |{x|x∈S∧ x=s}| (7) Tổng tất cả n khi n ≥ 1 ta có: P(n ≥ 1) = ∑ = − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛H i iHi HHi H 1 1 ηη = 1 - ⎥⎦ ⎥⎢⎣ ⎢ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − λ τ η H 1 (8) P(n ≥ 1) = P( ), sxSxx =∧∈∃ là xác suất một tác tử vừa nhìn thấy ít nhất một thể hiện của dịch vụ s trong khi di chuyển ngẫu nhiên trong thời gian τ 3.2.3. Hàm dự đoán tác tử nhìn thấy dịch vụ và thăm host Cho xác suất một tác tử a sẽ ghé thăm một host là v, và xác suất một tác tử di chuyển ngẫu nhiên sẽ thấy một thể hiện của dịch vụ là P(n ≥ 1), ta có thể xác định được ánh xạ hàm F(N) Giả sử việc một tác tử thấy một thể hiện của dịch vụ s là độc lập với việc nó ghé thăm host h. Gọi A là tập các agent ghé thăm h trong thời gian t. Sử dụng A, ta có thể kết hợp công thức (4) và (8) và có : Sau đó sử dụng phân bố nhị phân ta có thể định nghĩa ánh xạ F(N) cho tất cả giá trị của t: Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 28 ĐH Công nghệ - ĐH Quốc Gia HN Hàm F(N) hữu dụng trong việc đoán trước số lượng agent di chuyển ngẫu nhiên nhìn thấy dịch vụ s trong thời gian τ và tới thăm host h trong thời gian t. Lấy ví dụ trong lĩnh vực hàng không, giả sử rằng một tác tử cần phải định vị được một dịch vụ trong một khoảng thời gian cố định. Nếu dịch vụ không còn tồn tại thì tác tử sẽ đợi trong khoảng thời gian đó để cố tìm kiếm dịch vụ. Sử dụng hàm F(N) tác tử có thể dự đoán nếu nó nghe thấy thông tin từ bất cứ một tác tử tìm kiếm dịch vụ nào khác trong thời gian t. Nếu F(N) trả về xác suất thấp, tác tử sẽ ngay lập tức lập lại kế hoạch mà không cần chờ thêm. 3.2.4. Thời gian kì vọng tác tử di chuyển ngẫu nhiên trở về nguồn Mạng ad-hoc có thể được mô hình hóa bởi đồ thị liên thông, không hướng nếu coi các host là các đỉnh và các liên kết giữa các host trong mạng là các cạnh. Ta có đồ thị G=(V, E) trong đó V là tập các đỉnh, E là tập các cạnh. Đồ thị G có n đỉnh và m cạnh. Với mỗi đỉnh v ∈V, )(vΓ là tập các hàng xóm của v, đường đi ngẫu nhiên trên G là một quá trình liên tục tiếp diễn của một chuỗi các bước bắt đầu từ đỉnh v0 chọn ngẫu nhiên 1 đỉnh hàng xóm của v0, điều này cũng có nghĩa là ta chọn 1 cạnh ngẫu nhiên xuất phát từ đỉnh v0 để đến đỉnh v1 ∈ )( 0vΓ . Tại đỉnh v1 ta lại tiếp tục quá trình như thế. Sự chọn lựa ngẫu nhiên ở mỗi bước là hoàn toàn độc lập với bước trước đó. Theo lý thuyết đường đi ngẫu nhiên trong đồ thị ta có công thức sau: Với mọi v ∈V, hvv = 1/ vπ = 2m/d(v) (11) trong đó vπ là phân bố dừng tại đỉnh v, d(v) là số bậc của đỉnh v Từ công thức này ta có định nghĩa “hitting time” huv là số bước kì vọng trong đường đi ngẫu nhiên xuất phát từ u và kết thúc ở v. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 29 ĐH Công nghệ - ĐH Quốc Gia HN Và Cuv là thời gian chuyển mạch: Cuv = huv + hvu = Cvu là thời gian kì vọng mà một đường đi ngẫu nhiên bắt đầu từ u và trở về u sau khi đã thăm v ít nhất 1 lần. Cu(G) là độ lớn kì vọng của đường đi bắt đầu ở u và kết thúc trên mỗi đỉnh của G ít nhất 1 lần. Thời gian phủ của đồ thị G: C(G) = maxuCu(G) là thời gian lớn nhất của đường đi ngẫu nhiên xuất phát từ u và tới thăm mỗi đỉnh của G ít nhất 1 lần. Việc tính những giá trị thời gian kì vọng nêu trên rất có ý nghĩa khi tác tử cần tìm kiếm đường đi và xây dựng bảng định tuyến cho host hoặc đánh giá tần suất cập nhật thông tin trong mạng. 3.3. Mô hình triển khai Để mô hình hóa mạng ta sử dụng phương pháp liên thông chính xác tạo ra đồ thị mạng di động ad-hoc. Các kết nối được xác định bằng khoảng cách Euclidean giữa các host. Sự di chuyển của các host sẽ nằm trong vùng diện tích 1200x1200 m và mỗi host có vùng phủ sóng là 300 m. Tại thời điểm ban đầu của thí nghiệm, các host được di chuyển một cách ngẫu nhiên trong vùng diện tích đã định. Tất cả các tác tử và thể hiện của dịch vụ đều được phân bố một cách ngẫu nhiên trên các host. Trong mỗi lần lặp của mô phỏng sẽ thực hiện các công việc sau: 1. Hướng di chuyển của mỗi host sẽ được chọn ngẫu nhiên. Khả năng host di chuyển nhưng vẫn giữ nguyên hướng cũ là 60%, host quay 450 theo chiều kim đồng hồ và ngược chiều kim đồng hồ mỗi trường hợp là 20%. 2. Các host di chuyển về phía trước 1m theo hướng đã chọn 3. Các tác tử di trú từ host hiện tại tới một hàng xóm của host đó một cách ngẫu nhiên. 4. Mỗi thể hiện của dịch vụ s cũng được coi là một tác tử di động và cũng có thể di trú tới một nút hàng xóm ngẫu nhiên như mô tả ở trên 5. Trong mỗi lần lặp t, mỗi host sử dụng hàm F(N) để tính xác suất một tác tử với thông tin dịch vụ tới thăm nó trong những lần lặp tiếp theo t. Tần suất thực sự các tác tử tới thăm là t A cũng được ghi lại. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 30 ĐH Công nghệ - ĐH Quốc Gia HN 3.4. Đánh giá mô hình Tác tử di động tỏ ra hữu dụng trong việc thu thập thông tin. Nhờ những thông tin cập nhật cuả tác tử di động, các hệ thống đa tác tử hoạt động trên mạng ngang hàng có thể tạo ra những khả năng mới đầy tiện ích như: Đặt ra một ngưỡng nào đấy, khi mà tác tử với nhiệm vụ do thám không tìm thấy một dịch vụ hay host cần thiết nào trong thời gian cho phép thì ta có thể coi là dịch vụ hoặc host đấy không còn khả dụng nữa. Khi đó ta không tiếp tục đợi tác tử này nữa mà ngay lập tức lập lịch lại cho quá trình tìm kiếm. Điều này làm giảm độ trễ về thời gian chờ đợi và tìm kiếm trong mạng. Phát hiện những vùng đang xuống cấp của mạng. Dùng các tác tử do thám ta có thể dự đoán những vùng nào mạng bị lỗi, bị phân đoạn để kịp thời đưa ra hướng giải quyết. Nơi đó là những nơi tác tử không xuất hiện hoặc là không có những liên lạc với những nút mạng còn sống. Các host sử dụng thông tin do các tác tử cung cấp để báo cho hàm giới hạn thời gian về khoảng thời gian chúng có thể chờ đợi để thực thi nếu các host này bị phụ thuộc vào các dịch vụ từ xa. Tối ưu số tác tử để đạt được yêu cầu tần suất cập nhật thông tin của các tác tử phát hiện dịch vụ. Vẫn còn một số giới hạn cần phải kể đến như các phần tử của mô tả trạng thái N, tất cả đều có thể thay đổi và không được xác định trong một số miền. Vì vậy các tác tử có thể phải dựa vào một số tham số như λvà η . Thêm vào đó có nhiều cách hiệu quả mà tác tử có thể đi trong mạng. Việc nghiên cứu những công nghệ thay đổi này là cần thiết tuy nhiên các mô hình toán học của chúng phức tạp hơn là đường đi ngẫu nhiên. Còn một giới hạn nữa đó là mặc dù v có thể được định nghĩa từ hπ nhưng duy trì topo mạng toàn cục, J, là một vấn đề khó khăn trong mạng ngang hàng động. Các thuật toán định tuyến tích cực trong mạng ad-hoc thường định nghĩa một giao thức để lan truyền thông tin nhưng nó rất đắt. Tổng lượng bộ nhớ hoặc băng thông yêu cầu cho mỗi thông điệp trong trường hợp xấu nhất là O(n2) (đó là trường hợp di chuyển qua toàn bộ ma trận kề). Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 31 ĐH Công nghệ - ĐH Quốc Gia HN Chương 4. CÁC THÍ NGHIỆM MÔ PHỎNG VÀ ĐÁNH GIÁ 4.1. Chương trình mô phỏng MATES MATES là một mô phỏng trên tầng ứng dụng được tạo ra để nghiên cứu trạng thái của hệ thống tác tử cơ bản phân tán chạy trên đỉnh của mạng ngang hàng động và mạng di động adhoc (MANET). MATES không dùng để mô phỏng cho bất cứ nền tảng tác tử cụ thể nào mà nó cung cấp một môi trường chung, có thể mở rộng một cách dễ dàng cho quá trình kiểm tra các hệ thống dựa trên tác tử di động. 4.1.1. Kiến trúc chương trình MATES dựa trên 4 mô hình chính: - Host Mobility - Link Connectivity - Transport - Agent Behavior Mỗi mô hình có thể được liên tưởng như mỗi khối hoặc tương tự như mỗi khối của mô hình OSI. Trong mỗi lần mô phỏng thì mỗi mô hình kể trên được gắn vào một miền. Hình dưới là một vòng mô phỏng Hình 3-Một vòng mô phỏng Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 32 ĐH Công nghệ - ĐH Quốc Gia HN a. Hosts và Agents Đó là 2 thực thể chính của mô hình MATES. Mỗi agent có thể truy vấn trên các host hiện thời để điều khiển những agent khác ở host đó, định vị địa chỉ của host hiện thời hay xác định địa chỉ mạng của các hàng xóm. Một chú ý quan trọng nữa là các agents không tồn tại trên bất cứ host nào trong khi di chuyển giữa các host. Thêm vào đó sự di trú các agent có thể bị lỗi vì một lý do nào đó như host nguồn và host đích nằm ngoài vùng phủ sóng của nhau. Hai file Host.java và Agen.java cài đặt hai đối tượng trên. Đối tượng Host có các thuộc tính là String name; //Tên host Simulator simulator; //Mô phỏng mà chứa host Hashtable agents; //Tập các tác tử đang nằm trên host Hashtable agents_by_name; //Tập các tác tử lấy theo tên MobilityModel mobility_model; //Mô hình di chuyển host CPUSchedulingModel scheduling_model; //Mô hình lập lịch CPU UniqueID uid; //Định danh host Position position; //Vị trí của host Color color; //Màu sắc thể hiện trên giao diện PriorityQueue agent_queue, processed_agents; //Các hàng đợi tiến trình và hàng đợi dành cho tác tử cần xử lý double radio_range; //Vùng phủ sóng Host có một số phương thức chính như sau: Phương thức iterate() lập lịch thời gian cho các tác tử hiện đang nằm trên host dựa trên độ ưu tiên của mỗi tác tử. Phương thức addAgent(Agent agent) có nhiệm vụ thêm các tác tử cho host mỗi khi có tác tử tới. Tương tự phương thức removeAgent(Agent agent) sẽ xóa tác tử khỏi danh sách các tác tử trên host khi tác tử này dời khỏi host. Phương thức getNeighborsICanHear() trả về tập các hàng xóm mà host có thể kết nối tới Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 33 ĐH Công nghệ - ĐH Quốc Gia HN Agent có các thuộc tính sau: private String name; //Tên tác tử protected Host host; //Host mà tác tử đang ở trên đó private UniqueID uid; //Định danh duy nhất private int priority; //Độ ưu tiên private double transmission_size;//Lượng dữ liệu cần chuyển private boolean alive; //Đánh dấu tác tử còn sống hay không private int migration_timeout; //Thời gian timeout của quá trình di trú private Thread thread = null; private AgentThread agent_thread; private long sleep_until_iteration; //Thời điểm tác tử thức dậy sau khi tạm dừng hoạt động private boolean consume_processor; //Nếu là true bộ xử lý cua host sẽ thực thi trong khi tác tử này đang tạm dừng hoạt động private boolean started; //Đặt là true sau khi hàm iterate() được gọi lần đầu private boolean die_on_migration_failure; //Kiểm tra tác tử có die trong khi di trú không Agent cũng có một số phương thức chính như sau: Phương thức iterate() sẽ được gọi mỗi lần tác tử được lập lịch để chạy. Phương thức sleep() biểu diễn trạng thái tạm dừng hoạt động của tác tử. Hoạt động chủ yếu của tác tử là di trú và hàm migrate() dùng để mô tả các hành vi đó của tác tử. Phương thức getHost() trả về host hiện thời mà tác tử đang ở thăm. b. Host Mobility Model Host Mobility Model ra lệnh phương thức di chuyển của host. Sau mỗi khoảng thời gian thì mô hình này sẽ di chuyển host tới một vị trí liền kề nằm trong phạm vi của mô phỏng. c. Link Connectivity Model Đây là mô hình chịu trách nhiệm xác định kết nối giữa 2 host. Nó áp dụng được cả với các mô hình mạng tĩnh và mô hình mạng adhoc. Với mô hình mạng tĩnh thì Link Connectivity Model cơ bản là bảng tra cứu kết nối còn với mạng adhoc Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 34 ĐH Công nghệ - ĐH Quốc Gia HN thì nó là chức năng định vị host. Nó cũng xác định chất lượng của kết nối giữa các host. d. Data Transport Model Mô hình này dùng để xác định số lần một thực thể được gửi đi trên một liên kết cụ thể. Nó thường là một hàm về chất lượng kết nối và kích thước của thực thể. e. Định tuyến Tác tử được thừa nhận là tự định tuyến. Tuy nhiên nó có thể thực thi giao thức định tuyến trong mô phỏng. Việc này có thể được hoàn thành bởi một tác tử tĩnh trên mỗi host chịu trách nhiệm định tuyến. Khi một tác tử muốn biết chặng tiếp theo trong tuyến đường nó sẽ truy vấn host để điều khiển tác tử định tuyến và truy vấn chính tác tử này cho bảng định tuyến. f. Thời gian trong mô phỏng Trong MATES thời gian được mô phỏng bằng các lần lặp. Mỗi lần lặp tương ứng với một lượng tử thời gian. Mỗi tác tử được cung cấp một luồng riêng để chạy nhưng điều đó không có nghĩa là các tác tử sẽ thực thi nhiệm vụ đồng thời, các luồng được sử dụng để các tác tử có thể tạm dừng thực thi bằng việc ngủ và di trú giữa các host để chờ các khối thực thi khác xong. Tác tử sau đó lại có thể tiếp tục công việc của mình. 4.1.2. Triển khai chương trình Java là ngôn ngữ được MATES sử dụng. MATES đã tận dụng những lợi điểm của ngôn ngữ này như tính đa hình, tính ánh xạ và tính thừa kế. Các mô hình mô tả ở trên giúp cho chương trình mô phỏng mạng ad-hoc một cách khá trực quan và sinh động. Chương trình chạy trên nền Linux. Để biên dịch chương trình, chuyển đường dẫn vào thư mục chính của chương trình, tại chế độ dòng lệnh gõ make. Các file nguồn sẽ được biên dịch và đóng gói để tiện cho việc thực thi. Class chính của chương trình là Mates nằm trong file Mates.java. Lớp này có nhiệm vụ phân tích dòng lệnh input tạo giao diện nguời dùng thích hợp, và gọi thực thi những thí nghiệm cụ thể. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 35 ĐH Công nghệ - ĐH Quốc Gia HN Tất cả nhân của chương trình nằm trong file Simulator.java. Đây là file cài đặt mô phỏng, thực thi các bước lặp và quản lý các tác tử di trú. Dưới đây sẽ liệt kê một số file quan trọng nhất của chương trình. File Experiment.java là file cài đặt các thí nghiệm. Các thí nghiệm sẽ chạy các mô phỏng để đưa kết quả ra giao diện chính. File Topology.java chứa các mô hình liên quan của mạng, cách thức tạo, cập nhật topo mạng, một số thuộc tính về mạng như bán kính mạng, độ phân bố dừng…Các thuật toán liên quan tới mạng sẽ được cài đặt trong file này. GraphicalUserInterface.java là file cung cấp giao diện chính cho chương trình, xử lý các sự kiện người dùng và các sự kiện của các đối tượng, đưa ra kết quả. StatisticsPlugin.java lấy kết quả thực thi chương trình để xây dựng một số hàm tính toán các thông số mạng như mật độ trung bình, đường kính trung bình của topo, bậc trung bình của các host trong topo… Topo mạng ban đầu hình thành thế nào? Trong hàm handleInitialize của mỗi thí nghiệm sẽ cố định số lượng host trong mạng sau đó các host sẽ được khởi tạo. Thông tin về host gồm có : tên, vị trí, mô hình di chuyển, gán với simulator nào. Duyệt danh sách host để add từng host vào mô phỏng. Trong mô phỏng tại mỗi lần lặp, các host sẽ được move theo mô hình di chuyển đã khai báo. Vậy các host di chuyển thế nào? - Nếu tập các hướng chưa được cài đặt thì chọn 1 hướng ngẫu nhiên nhỏ hơn 360 độ. - Khi đã chọn 1 hướng ngẫu nhiên host sẽ chọn chiều di chuyển: hoặc là xuôi chiều kim đồng hồ, hoặc ngược chiều kim đồng hồ hoặc giữ nguyên hướng đã chọn. Các host xác định hàng xóm thế nào? Hàm getCommunicableHosts() trong file Topology.java trả về tập các host mà host đang xét có thể truyền tin tới. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 36 ĐH Công nghệ - ĐH Quốc Gia HN Có 2 loại hàng xóm: - Neighbors host can hear: những hàng xóm có thể gửi tin nhắn tới host đang xét. - Neighbors host can talk: những hàng xóm có thể nhận tin nhắn từ host đang xét. Trước khi di chuyển, host sẽ lấy danh sách hàng xóm mà nó có thể gửi tin nhắn tới sau đó nó có thể di chuyển ngẫu nhiên về phía trước theo hướng định sẵn và đảm bảo là vẫn ở trong vùng cho phép. Tiếp theo nó tính số host mà nó có thể gửi thông điệp tới. Nếu kết quả nhỏ hơn trước host sẽ quay trở về vị trí ban đầu. Mỗi lần lặp của mô phỏng làm những công việc gì? - Di chuyển tất cả các host - Cập nhật topo mạng - Các host gọi CPUSchedulingModel để thực hiện thao tác với tác tử. - Di chuyển các tác tử đang trong trạng thái di trú: + Lượng dữ liệu cần truyền sẽ giảm đi trong mỗi lần agent di trú thành công. Lượng dữ liệu giảm đi này bằng lư ợng dữ liệu cần truyền giữa 2 host trong 1 lần iteration. Đồng thời số lần tác tử di trú tăng lên 1 + Nếu dữ liệu mà các agent mang đi trong quá trình di trú < 0.0 : agent đã tới thăm host mới và agent sẽ đuợc gán cho Host này đồng thời xóa tên agent này trong danh sách các agent đang di trú => sinh sự kiện AgentArrivalEvent(agent, mi.destination, mi.source) + Nếu agent đang time out, xét trường hợp agent trong quá trình di trú lỗi thì nó sẽ bị kill, còn nếu không nó sẽ quay trở lại nơi nó đuợc gửi đi. - Cuối cùng tăng iterate lên 1. 4.1.3. Ưu điểm, nhược điểm của chương trình Chương trình được viết bằng ngôn ngữ Java mềm dẻo. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 37 ĐH Công nghệ - ĐH Quốc Gia HN Giao diện chương trình thân thiện, dễ sử dụng.Việc biên dịch và chạy chương trình cũng nhanh chóng nhờ một script trợ giúp. Kết quả của mô phỏng được đưa ra ngay trên giao diện chính tạo điều kiện dễ dàng cho việc nhận xét đánh giá. Mọi thao tác của từng tác tử cũng được thống kê lại. Thông tin về host rõ ràng, cụ thể, cập nhật sau mỗi lần lặp. Topo mạng được mô hình hóa rất trực quan. Phần dưới đây ta sẽ phát triển ví dụ template của chương trình nguồn để làm những thí nghiệm mô phỏng và đánh giá lý thuyết. Ví dụ này ban đầu chỉ có hai file AgentTemplate.java và ExperimentTemplate.java . File AgentTemplate.java cài đặt lớp AgentTemplate kế thừa từ lớp cha là Agent. Lớp ExperimentTemplate trong file ExperimentTemplate.java cũng được kế thừa từ lớp Experiment. Ví dụ mô phỏng quá trình di trú đơn giản của 2 agent trong một topo mạng có 2 host. Phần dưới đây ta sẽ cải tiến chương trình cho phù hợp với từng thí nghiệm mô phỏng. 4.2. Thí nghiệm đo tần suất tác tử tới thăm host 4.2.1. Mô tả thí nghiệm Thí nghiệm này kiểm nghiệm sự chính xác của thuật toán PageRank trong việc dự đoán tần suất tác tử tới thăm một host xác định. Ta đo độ phân bố dừng tại một host trong tổng số 30 host của thí nghiệm và số lần lặp là 100000. Ở đây ta chọn host 0 làm thí nghiệm. Hàm tính phân bố dừng calculateStationaryDistribution() trong file Topology.java là phần cài đặt thuật toán PageRank đã mô tả ở trên. Hàm trả về tập các giá trị phân bố xác suất trên tất cả các host trong mạng. Cũng tại một host bất kì trong 30 host ta đếm số tác tử đã tới thăm host này. Ta sẽ so sánh 2 kết quả đo được để đưa ra nhận xét. 4.2.2. Thiết lập các tham số liên quan Đặt biến num_hosts trong hàm handleInitialize() của file ExperimentTemplate.java là 30. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 38 ĐH Công nghệ - ĐH Quốc Gia HN Số tác tử di chuyển ngẫu nhiên num_agents = 15. Với đối tượng AgentTemplate trong hàm khởi tạo, ta đặt thêm thời gian timeout cho quá trình di trú là 500 bằng cách gọi phương thức setMigrationTimeout() của lớp cha là lớp Agent. Với đối tượng Host trong file Host.java ta cài đặt thêm thuộc tính số tác tử tới thăm int agent_count, và phương thức setAgentCounter() để cài đặt số tác tử tới thăm, phương thức getAgentCounter() để lấy số tác tử tới thăm. Trong hàm iterate() của file Simulator.java ta đặt một biến đếm count gán số lượng các tác tử tới thăm host. Với mỗi sự kiện tác tử tới thăm một host, ta kiểm tra xem đó là host nào, và tăng biến đếm tương ứng của host đó lên 1. Số lần lặp của thí nghiệm là 100000 lần, sau 500 lần lặp ta cho in kết quả ra màn hình và kiết xuất ra file text. 4.2.3. Kết quả thu được và đánh giá Kết quả của hàm calculateStationaryDistribution() ta dùng để tính ra xấp xỉ v theo công thức vˆ = 1 – (1 – (1 – (1 - πρh)|A| ) )t = 1 – (1 - πρh)|A| t (4) Số lượng agent thu được sau mỗi 500 lần lặp đem chia cho 500 ta thu được tần suất tác tử tới thăm host trong thời gian t=500. Tuy nhiên khi tính toán với các số liệu, xấp xỉ v luôn cho ra giá trị gần như bằng 1. Nguyên nhân của hiện tượng này là do tham số mũ t. Với t là số lần lặp và tăng dần từ 500 tới 100000, giá trị πρh đo được lại rất nhỏ (thường khoảng 0.05) thì kết quả xấp xỉ v luôn tiến rất gần tới 1. Theo như lý luận về ý nghĩa của công thức (4) thì đó là xác suất để có ít nhất 1 tác tử tới thăm host h trong thời gian t. Với số tác tử là khá nhiều (15 tác tử) và số lượng host chỉ có 30 thì xác suất để không có tác tử nào tới thăm host trong thời gian t là rất nhỏ. Như vậy để tính xác suất tác tử tới thăm một host cụ thể trong thời gian t ta nên thay công thức (4) thành công thức sau: vˆ = 1 – (1 - πρh)|A| Với công thức mới này ta tính toán với các số liệu thu được kết quả cho ra như hình ở dưới. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 39 ĐH Công nghệ - ĐH Quốc Gia HN Hình 4-Mối tương quan giữa xấp xỉ v và tần suất tác tử tới thăm host trong 100000 lần lặp Nhìn vào đồ thị có thể thấy sự tương đồng giữa hai đường xấp xỉ v và xác suất tác tử tới thăm host. Điều đó cũng chứng minh cho những dự đoán lý thuyết là khá chính xác. Như vậy thuật toán PageRank áp dụng để tính xác suất tác tử tới thăm một host trong mạng là rất phù hợp. Việc dự đoán của chúng ta cũng có căn cứ toán học chắc chắn. 4.3. Thí nghiệm 2 4.3.1. Mô tả thí nghiệm Thí nghiệm đánh giá độ chính xác của hàm F(N). Hàm F(N) sẽ được tính theo công thức (10). Thực nghiệm ta đo số tác tử có thông tin về dịch vụ và tới thăm một host xác định. So sánh 2 kết quả ta sẽ rút ra kết luận. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 40 ĐH Công nghệ - ĐH Quốc Gia HN Do dịch vụ cũng có tính di động được, nghĩa là nó có thể xuất hiện ở một nút ngẫu nhiên trong mạng rồi di chuyển tới host mới nên nhiệm vụ của các tác tử bây giờ là đi tìm kiếm dịch vụ, cố gắng phát hiện dịch vụ trên 1host nào đấy trong mạng. Tại mỗi bước lặp ta đếm số lần 1 tác tử nhìn thấy dịch vụ . Tại mỗi host, ta đếm số lần các tác tử này tới thăm nó. Đồng thời ta cũng đếm số host mà 1 tác tử đã đi qua trong quá trình di trú. Ta cũng cho thí nghiệm lặp 100000 lần, sau mỗi 500 lần cho kết quả chương trình kiết xuất ra file text để xử lý. 4.3.2. Thiết lập các tham số liên quan Trong file Experiment.java đặt: int num_hosts = 30; int num_agents = 15; int num_service = 3; và add ngẫu nhiên dịch vụ vào các host. Xây dựng file ServiceTemplate.java mô tả đối tượng ServiceTemplate. Lớp này thừa kế từ lớp Agent. ServiceTemplate cũng di chuyển ngẫu nhiên trong mạng, nó cũng có thể coi là 1 agent. Bổ sung một số thuộc tính và thêm một số phương thức cho đối tượng AgenTemplate như sau: Host destination; // Host chứa dịch vụ int count_service = 0; //Số dịch vụ mà tác tử tìm thấy LinkedList track_back; //Danh sách các host mà tác tử đi qua Trong hàm khởi tạo AgentTemplate đặt thời gian timeout cho quá trình di trú là 1000. Thêm phương thức _searchingService() mô tả quá trình tìm kiếm dịch vụ. Phương thức getNumService() trả về số dịch vụ mà tác tử tìm thấy. Phương thức getNumHost() trả về số lượng host mà tác tử đi qua. Phương thức getDestination() lấy thông tin về host chứa dịch vụ Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 41 ĐH Công nghệ - ĐH Quốc Gia HN Trong hàm run() mỗi lần tác tử chọn hàng xóm mới để di trú tới, ta add host mới này vào danh sách track_back để lưu đường đi của tác tử. Trong file Simulator.java, bố sung 2 thuộc tính int service_counter = 0;//Đếm số dịch vụ mà tác tử tìm thấy int num_host = 0; //Đếm số host mà tác tử đi qua Tại mỗi lần lặp, đếm số dịch vụ tìm thấy, số host tác tử đi qua và gán vào các biến trên. 4.3.3. Kết quả thu được và đánh giá Các số liệu ta thu được gồm có: - Phân bố dừng ứng với host 0 - Số lượng host mà tác tử đi qua - Số tác tử tìm thấy dịch vụ và tới thăm host 0 - Xác suất 1 dịch vụ tới thăm host : 3/30 Dùng phân bố dừng và xác suất 1 dịch vụ tới thăm host, số lượng host mà tác tử đi qua lắp vào công thức (10) ta tính F(N) Ta lại bắt gặp trường hợp như thí nghiệm 1 đó là vấn đề với tham số t. Khi t là số lần lặp và tăng dần từ 500 tới 100000 lần thì F(N) tính theo công thức trên tiến rất gần tới 1, có thể coi bằng 1. Theo như lý giải phần thí nghiệm 1 ta cũng có công thức mới tính xác suất tác tử có thông tin về dịch vụ và tới thăm một host cụ thể như sau: F(N) = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −− λ τ ηυ H 11 Các số liệu tính toán theo công thức mới và tính theo thực nghiệm cho kết quả như hình dưới. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 42 ĐH Công nghệ - ĐH Quốc Gia HN Hình 5-Hàm dự đoán F(N) và xác suất tới thăm host của tác tử có thông tin về dịch vụ Đồ thị cho thấy 2 đường xác suất tác tử có thông tin về dịch vụ tới thăm host và đường dự đoán F(N) theo công thức mới có hình dạng khá tương đồng, giá trị của chúng cũng rất gần nhau. Có thể thấy hàm F(N) đã dự đoán khá chính xác so với kết quả thực đo được. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 43 ĐH Công nghệ - ĐH Quốc Gia HN 4.4. Thí nghiệm 3 4.4.1. Mô tả thí nghiệm Thí nghiệm đo thời gian tác tử bắt đầu xuất phát từ một host, di chuyển ngẫu nhiên trong mạng và trở về host ban đầu. Trong thí nghiệm này ta chỉ đo với 1 tác tử. Tác tử này được gắn ban đầu vào host 0. Ta sẽ đo phân bố dừng của host này, tính thời gian “hitting time” và so với kết quả đo thời gian tác tử di chuyển. 4.4.2. Thiết lập các tham số liên quan Trong file ExperimentTemplate.java thiết lập các thông số như sau: int num_hosts = 30; int num_agents = 1; Agent sinh ra được gán cho host 0: hosts[0].addAgent(new AgentTemplate(hosts[0])); Trong file AgentTemplate.java cài đặt thêm một số thuộc tính và phương thức sau: LinkedList track_back; // Danh sách các host mà tác tử đi qua int times_finish = 0; // Số lần tác tử di chuyển về nguồn int sum_step = 0; //Số bước tổng cộng tác tử đi qua Hai phương thức getTimesFinish() để lấy số lần tác tử đi về nguồn và phương thức getSumStep() lấy tổng số bước tác tử đi qua Trong hàm run() ở mỗi bước tác tử chọn 1 hàng xóm mới để di trú tới ta thêm hàng xóm này vào danh sách track_back để lưu vết của đường đi đồng thời kiểm tra điều kiện xem nút hàng xóm mới có trùng với nút nguồn của tác tử. Nếu trùng tức là tác tử đã về nguồn, khi đó tăng biến times_finish lên 1. Số bước tác tử đi qua sum_step = track_back.size(); Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 44 ĐH Công nghệ - ĐH Quốc Gia HN Trong hàm khởi tạo AgentTemplate() ta cũng đặt thời gian timeout cho quá trình di trú là 500. Hết thời gian di trú tác tử sẽ phải trở về nguồn và khởi động lại quá trình di trú. 4.4.3. Kết quả thu được và đánh giá Hình 6-Thời gian kì vọng tác tử về nguồn Đồ thị trên cho thấy giữa 2 đường có sự tương đồng lớn trong những lần lặp đầu. Ở nửa sau, đường tính theo thực nghiệm có sự khác biệt khá lớn với đường tính theo lý thuyết. Như vậy thời gian kì vọng mà tác tử trở về nguồn tính theo thực nghiệm và lý thuyết tương đối giống nhau. Sự sai khác ở những lần lặp sau có thể giải thích như sau: Trong những lần lặp đầu, khi các host di chuyển về phía trước và chưa xa nhau nhiều, topo mạng vẫn là môt đồ thị liên thông và đầy đủ. Thời gian kì vọng tác tử di chuyển về nguồn tính theo công thức lý thuyết (11) là hợp lý. Tuy nhiên trong những lần lặp sau này, khi mà các host di chuyển khá xa nhau, một số host đã không còn liên kết với những host khác thì topo mạng trở thành không đầy đủ. Công thức (11) không còn phù hợp nữa, do vậy có sự khác biệt lớn như trong hình vẽ thể hiện. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 45 ĐH Công nghệ - ĐH Quốc Gia HN Chương 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Với đề tài “Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc” tác giả đã trình bày được 4 phần rõ ràng: • Phần đầu là cái nhìn tổng quan về mạng ngang hàng và những kĩ thuật tìm kiếm trong mạng ngang hàng không có cấu trúc. • Phần tiếp theo giới thiệu về công nghệ tác tử di động, những lợi điểm và ứng dụng của công nghệ này trong thực tiễn. Công nghệ này có nhiều tiềm năng phát triển trong tương lai. • Phần thứ ba là phần ứng dụng công nghệ tác tử di động trong một lĩnh vực vô cùng quan trọng của mạng, đó là lĩnh vực tìm kiếm. Tuy trong khuôn khổ của nghiên cứu khóa luận chỉ đề cập tới một phần nhỏ của vấn đề tìm kiếm trong mạng ngang hàng đó là phát hiện dịch vụ song đây cũng là một khía cạnh chủ yếu trong lĩnh vực rộng lớn này. • Phần cuối cùng là phần mô phỏng và làm những thí nghiệm đánh giá một số tham số liên quan tới giải pháp phát hiện dịch vụ đã trình bày ở phần trước. Trong khóa luận này, những thí nghiệm làm được chưa phải là nhiều, tuy nhiên đó là những thí nghiệm quan trọng. Những thí nghiệm đã góp phần đánh giá lại lý thuyết, mô tả lại thực tế một cách trực quan nhất. Bài toán tìm kiếm luôn là bài toán khó. Có rất nhiều yêu cầu phải đặt ra để đảm bảo cho một thuật toán tối ưu và hiệu quả. Hơn hết mục đích cuối cùng vẫn là đem lại lợi ích tối đa cho những người sử dụng. Cùng với sự phát triển của công nghệ thông tin các thuật toán tìm kiếm càng cần phải thay đổi để tối ưu và phù hợp hơn với xu thế đó. Công nghệ tác tử cũng là một hướng đi khá mới trong thời gian hiện tại. Nó đã tiến dần hơn tới những người dùng trong những ứng dụng mà họ sử dụng. Trong tương lai cùng với sự phát triển của khoa học máy tính và trí tuệ nhân tạo thì lĩnh vực tác tử này đang còn rất nhiều hứa hẹn. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 46 ĐH Công nghệ - ĐH Quốc Gia HN Những phần tác giả nghiên cứu được tuy mới chỉ nằm trên khuôn khổ lý thuyết và chưa có đủ điều kiện để thực hiện trong thực tế nhưng nó đã được những nhà nghiên cứu đi trước thực hiện và thử nghiệm rồi. Hi vọng trong tương lai sẽ có nhiều ứng dụng sử dụng những công nghệ và giải pháp mà khóa luận này đã trình bày. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 47 ĐH Công nghệ - ĐH Quốc Gia HN LỜI KẾT Khóa luận này không đi theo hướng triển khai một dịch vụ thực tế, nó chỉ là những nghiên cứu lý thuyết. Song lý thuyết luôn là nền tảng cho thực tế. Với những nghiên cứu lý thuyết, khả năng tư duy của con người cũng tốt hơn và khi đã có tư duy thì triển khai những công việc trong thực tế sẽ dễ dàng và thuận lợi hơn. Sau thời gian nghiên cứu và thực hiện khóa luận này tôi đã rút ra được nhiều bài học bổ ích, càng thấm thía hơn “học phải đi đôi với hành”. Sau này trong bước đường phát triển của mình những kinh nghiệm và kiến thức thu được sẽ là nền tảng tốt cho tôi. Thông qua khóa luận này tôi xin gửi lời tri ân tới tất cả các thầy cô, bạn bè, những người đã nâng đỡ và dìu dắt, động viên tôi trong suốt quá trình học tập, rèn luyện. Xin gửi lời chào tạm biệt mái trường Đại học Công nghệ thân yêu, nơi nuôi dưỡng những mầm xanh đất nước! Hà nội, tháng 05 năm 2009 Tác giả Nguyễn Thị Kim Oanh Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 48 ĐH Công nghệ - ĐH Quốc Gia HN TÀI LIỆU THAM KHẢO [1] Trần Hạnh Nhi, Lê Đình Duy, Nguyễn Đông Hà, Thái Trí Hùng, Văn Trọng Nam, Huỳnh Tấn Năng, Nguyễn Huy Thẩm, Nguyễn Thái Huy, Phan Đình Thế Huân, Hồ Thị Mỹ Hiền, Lê Văn Triều. Tổng quan về Mobile Agent. [2] Nguyễn Hoàng Linh Phương, Nguyễn Văn Thoại. Ứng dụng thử nghiệm Mobile Agent vào xây dựng Workflow. [3] Lê Thị Minh Nguyệt. Mobile Agent và ứng dụng trong thương mại điện tử. [4] Evan Sultanik, William Regli. Service Discovery on Dynamic Peer-to-peer networks using mobile agents. [5] Reza Dorrigiv, Alejandro Lospez-Ortiz, Pawel Pralat. Search algorithms for Unstructured Peer-to-Peer Networks. [6] Qin Lv, Pei Cao *, Edith Cohen, Kai Li, Scott Shenker. Search and Replication in Unstructured Peer-to-Peer Networks. [7] Cameron Ross Dunne. Using Mobile Agents for Network Resource Discovery in Peer-to-Peer Networks.