Đề tài Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác

................. 33 1.1. Giới thiệu ...................................................................................................... 33 1.2. Kiến trúc MIXGROUP .................................................................................. 33 1.3. Nguyên lý tìm kiếm dữ liệu của MIXGROUP ............................................... 34 II. ÁP DỤNG CÁC NGUYÊN LÝ NGHIÊN CỨU KHOA HỌC TRONG QUÁ TRÌNH NGHIÊN CỨU .............................................................................................. 35 2.1. Nguyên lý phân nhỏ ...................................................................................... 35 2.2. Nguyên lý kết hợp ......................................................................................... 36 Ngô Thùy Hương – 12 12 016 6 2.3. Nguyên lý linh động ...................................................................................... 36 2.4. Nguyên lý hoạt động theo chu kỳ .................................................................. 38 2.5. Nguyên lý sử dụng trung gian ....................................................................... 39 III. ĐỀ XUẤT VÀ KẾT LUẬN ............................................................................. 41 3.1. Đề Xuất ......................................................................................................... 41 3.2. Kết luận......................................................................................................... 41 Ngô Thùy Hương – 12 12 016 7 LỜI MỞ ĐẦU Sự phát triển lịch sử xã hội loài người gắn liền với quá trình sáng tạo lâu dài và liên tục, từ việc chế tạo ra các công cụ thô sơ cho tới công cụ hiện đại hơn sử dụng nhiệt năng và tới sự phát minh ra điện đã đánh dấu một bước phát triển nhảy vọt trong sáng tạo, các máy tính khổng lồ cho tới các máy tính cá nhân nhỏ gọn lần lượt xuất hiện. Cùng với sự sáng tạo, con người ngày càng đạt được những thành tựu vượt bậc trong khoa học công nghệ làm thay đổi thế giới, thay đổi hoàn toàn cách thức làm việc và suy nghĩ của con người. Tuy nhiên, ngày nay do nhu cầu cải tiến sáng tạo trong công nghệ phục vụ cho cuộc sống ngày càng cao đòi hỏi phải có một môn khoa học chuyên nguyên cứu về phương pháp sáng tạo giúp cho việc sáng tạo được dễ dàng và có cơ sở lý thuyết rõ ràng hơn. Vì thế các phương pháp luận sáng tạo ra đời với mục đích trang bị cho người học hệ thống các phương pháp, các kỹ năng thực hành về suy nghĩ để giải quyết các vấn đề và ra quyết định một cách sáng tạo, về lâu dài, tiến tới điều khiển được tư duy. Và trong đó 40 nguyên tắc sáng tạo cơ bản được Alshuller G.S tổng hợp lại trở thành những nguyên tắc thủ thuật cơ bản thiết thực nhất. Trước hết, em xin gửi lời cảm ơn chân thành tới GS.TSKH. Hoàng Kiếm đã giảng dạy và hướng dẫn tận tình giúp em có cái nhìn tổng quan hơn trong sáng tạo và tầm quan trọng của sự sáng tạo nhất là trong khoa học nghiên cứu và ứng dụng sáng tạo trong thực tế. Để đúc kết lại kiến thức mà em thu nhận được em xin trình bày bài thu hoạch về: “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác ”. Bài thu hoạch được phân tích dựa trên khóa luận tốt nghiệp của em [13]. Ngô Thùy Hương – 12 12 016 8 TỔNG QUAN CHƯƠNG 1: I. Giới thiệu chung 1.1. Giới thiệu Ngày nay, cùng với sự phát triển nhanh chóng của công nghệ mạng không dây, các thiết bị di động hiện đại như laptop, PDA, điện thoại di động, ... ra đời và mang lại rất nhiều ứng dụng tiện ích cho con người trong việc trao đổi, cập nhật thông tin hiệu quả. Với những thiết bị di động con người có thể trao đổi thông tin ở bất cứ nơi đâu, bất cứ lúc nào mà không cần phụ thuộc vào các kiến trúc cơ sở hạ tầng. Tuy nhiên, việc giao tiếp thông tin giữa các thiết bị trong môi trường mạng di động vẫn còn một số hạn chế như: giới hạn về băng thông, quyền chia sẻ tài nguyên, dung lượng ít, khả năng kết nối yếu, ...Vì vậy, cần có kỹ thuật quản lý và lưu trữ dữ liệu phù hợp để giúp hệ thống hoạt động, trao đổi dữ liệu hiệu quả hơn. Kỹ thuật lưu trữ lại dữ liệu (caching method) là một trong những kỹ thuật quan trọng giúp các máy khách lưu trữ lại dữ liệu tại bộ nhớ cục bộ của nó để phục vụ cho các yêu cầu dữ liệu sau đó trong trường hợp không kết nối được tới máy chủ hoặc hạn chế việc truy cập quá nhiều đến máy chủ. Kỹ thuật lưu trữ lại dữ liệu quan tâm tới bốn vấn đề chính đó là: khám phá dữ liệu (Cache Discovery), thu nạp dữ liệu (Cache Admission), thay thế dữ liệu (Cache Replacement), nhất quán dữ liệu (Cache Consistency). Tuy nhiên, trong mục tiêu và giới hạn của bài thu hoạch em chỉ đề cập tới vấn đề đó là khám phá dữ liệu (Cache Discovery). Với các ứng dụng trong mạng không dây, thì kho lưu trữ cục bộ của các thiết bị di động rất hạn chế về mặt kích thước lưu trữ, do đó vấn đề đặt ra là phải tận dụng được không gian lưu trữ sao cho hiệu quả. Chính vì thế, chúng ta cần quan tâm tới việc khám phá và thu nạp mục dữ liệu như thế nào, để đảm bảo việc sử dụng tối ưu kho lưu trữ cục bộ. Các kỹ thuật khám phá dữ liệu sẽ đề cập tới việc làm sao có thể tối ưu hóa chi phí khi tìm kiếm một hạng mục dữ liệu trong hệ thống, giúp giảm thiểu số lần truy vấn tới máy Ngô Thùy Hương – 12 12 016 9 chủ (hay còn gọi là BS (Base Station), Server, Data Source), rút ngắn thời gian phản hồi truy vấn dữ liệu tại mỗi máy khách (hay còn gọi là Client, nút di động). Tuy nhiên, việc tìm kiếm mục dữ liệu yêu cầu, và việc thêm vào một hạng mục dữ liệu không phải lúc nào cũng thuận lợi vì quyết định sai có thể làm giảm tính sẵn sàng của dữ liệu. Chính vì thế mục tiêu của bài thu hoạch “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác” là tìm hiểu và phân tích những nguyên lý sáng tạo đã được áp dụng vào các kỹ thuật khám phá dữ liệu.Từ kết quả phân tích có thể giúp cho những nhà nghiên cứu liên quan có lựa chọn đúng đắn đến việc sử dụng kỹ thuật khám phá vào trong mỗi hệ thống đặc thù của mình. 1.2. Hướng tiếp cận Với mục tiêu đề tài đưa ra, hướng tiếp cận và giải quyết bài toán là sẽ tìm hiểu lần lượt các kỹ thuật khám phá dữ liệu trong môi trường hệ thống thông tin di động từ các công trình nghiên cứu trong và ngoài nước. Đồng thời sẽ tiến hành phân loại các trường hợp của kỹ thuật khám phá dữ liệu đã tìm hiểu. Sau đó đánh giá và so sánh các ưu khuyết điểm của các kỹ thuật phám phá dữ liệu. Và cuối cùng là đề xuất và thử nghiệm một số kỹ thuật khám phá dữ liệu để kiểm tra tính hiệu quả của từng giải pháp. 1.3. Nội dung đề tài Với mục tiêu, hướng tiếp cận, và cách giải quyết của bài thu hoạch “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác”. Nội dung bài thu hoạch được trình bày theo cấu trúc như sau:  Chương 1: Tổng quan Giới thiệu về bối cảnh, mục tiêu, hướng tiếp cận và nội dung của đề tài.  Chương 2: Cơ sở lý thuyết cho các nghiên cứu khoa học Ngô Thùy Hương – 12 12 016 10 Trong chương này, em sẽ trình bày về cơ sở lý thuyết cho các nghiên cứu khoa học và 40 nguyên lý sáng tạo trong khoa học.  Chương 3: Phân tích các kỹ thuật khám phá dữ liệu và việc áp dụng nguyên lý sáng tạo trong đó Trong chương này, em sẽ trình bày về kỹ thuật khám phá dữ liệu trong hệ thống thông tin di động cộng tác, đồng thời phân tích những nguyên lý sáng tạo được áp dụng trong từng kiến trúc.  Chương 4 : Ứng dụng cơ sở lý thuyết nghiên cứu khoa học vào công việc nghiên cứu thực tiễn của bản thân Trong chương này, em sẽ trình bày những nguyên lý sáng tạo mà em đã áp dụng vào đề tài của mình. Ngô Thùy Hương – 12 12 016 11 CƠ SỞ LÝ THUYẾT CHO CÁC CHƯƠNG 2: NGHIÊN CỨU KHOA HỌC I. VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI QUYẾT 1.1. Khái niệm Vấn đề khoa học (scientific problem) [19] cũng được gọi là vấn đề nghiên cứu (research problem) hoặc câu hỏi nghiên cứu là câu hỏi được đặt ra khi người nghiên cứu đứng trước mâu thuẫn giữa tính hạn chế của tri thức khoa học hiện có với yêu cầu phát triển tri thức đó ở trình độ cao hơn. 1.2. Phân loại Nghiên cứu khoa học luôn tồn tại hai vấn đề : - Vấn đề về bản chất sự vật đang tìm kiếm - Vấn đề về phương pháp nghiên cứu để làm sáng tỏ về lý thuyết và thực tiễn những vấn đề thuộc lớp thứ nhất. 1.3. Các tình huống vấn đề Có ba tình huống : Có vấn đề , không có vấn đề, giả vấn đề được cho trong hình dưới đây: Có vấn đề Có nghiên cứu Không có vấn đề Không có nghiên cứu Ngô Thùy Hương – 12 12 016 12 Hình 2.1: Sơ đồ phân loại 1.4. Các phương pháp phát hiện vấn đề khoa học Có sáu phương pháp: 1) Tìm những kẻ hở, phát hiện những vấn đề mới 2) Tìm những bất đồng 3) Nghĩ ngược lại quan niệm thông thường 4) Quan sát những vướng mắc trong thực tiễn 5) Lắng nghe lời kêu ca phàn nàn 6) Cảm hứng : những câu hỏi bất chợt xuất hiện khi quan sát sự kiện nào đó. 1.5. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế 1.5.1. Có 5 phương pháp:  Dựng Vepol đầy đủ  Chuyển sang Fepol  Phá vở Vepol  Xích Vepol  Liên trường 1.5.2. Có 40 thủ thuật:  Nguyên lý phân nhỏ.  Nguyên lý “tách khỏi”. Giả vấn đề Không có vấn đề Nảy sinh vấn đề khác Không có nghiên cứu Nghiên cứu theo một hướng khác Ngô Thùy Hương – 12 12 016 13  Nguyên lý phẩm chất cục bộ.  Nguyên lý (phản) bất đối xứng.  Nguyên lý kết hợp.  Nguyên lý vạn năng.  Nguyên lý “chứa trong”.  Nguyên lý phản trọng lượng.  Nguyên lý gây ứng suất (phản tác động) sơ bộ.  Nguyên lý thực hiện sơ bộ.  Nguyên lý dự phòng.  Nguyên lý đẳng thế.  Nguyên lý đảo ngược.  Nguyên lý cầu (tròn) hóa.  Nguyên lý linh động.  Nguyên lý giải (tác động) “thiếu” hoặc “thừa”.  Nguyên lý chuyển sang chiều khác.  Sử dụng các dao động cơ học.  Nguyên lý hoạt động theo chu kỳ.  Nguyên lý liên tục các tác động có ích.  Nguyên lý “vượt nhanh”.  Nguyên lý biến hại thành lợi.  Nguyên lý quan hệ phản hồi.  Nguyên lý sử dụng trung gian.  Nguyên lý tự phục vụ.  Nguyên lý sao chép.  Nguyên lý “rẻ’ thay cho “đắt”.  Thay thế sơ đồ (kết cấu) cơ học.  Sử dụng các kết cấu khí và lỏng. Ngô Thùy Hương – 12 12 016 14  Sử dụng vỏ dẻo và màng mỏng.  Sử dụng các vật liệu nhiều lỗ.  Nguyên lý thay đổi màu sắc.  Nguyên lý đồng nhất.  Nguyên lý phân hủy hoặc tái sinh các phần.  Thay đổi các thông số hóa lý của đối tượng.  Sử dụng chuyển pha.  Sử dụng sự nở nhiệt.  Sử dụng các chất ôxy hóa mạnh.  Thay đổi độ trơ.  Sử dụng các vật liệu hợp thành (composite). II. 40 NGUYÊN TẮC SÁNG TẠO TRONG NGHIÊN CỨU KHOA HỌC 2.1. Nguyên tắc phân nhỏ a) Chia đối tượng thành các phần độc lập. b) Làm đối tượng trở nên tháo lắp được. c) Tăng mức độ phân nhỏ đối tượng. 2.2. Nguyên tắc “tách khỏi” a) Tách phần gây “phiền phức” (tính chất “phiền phức”) hay ngược lại tách phần duy nhất “cần thiết” (tính chất “cần thiết”) ra khỏi đối tượng. 2.3. Nguyên tắc phẩm chất cục bộ a) Chuyển đối tượng (hay môi trường bên ngoài, tác động bên ngoài) có cấu trúc đồng nhất thành không đồng nhất. b) Các phần khác nhau của đối tượng phải có các chức năng khác nhau. c) Mỗi phần của đối tượng phải ở trong những điều kiện thích hợp nhất đối với công việc. Ngô Thùy Hương – 12 12 016 15 2.4. Nguyên tắc phản đối xứng Chuyển đối tượng có hình dạng đối xứng thành không đối xứng (nói chung giảm bậc đối xứng). 2.5. Nguyên tắc kết hợp a) Kết hợp các đối tượng đồng nhất hoặc các đối tượng dùng cho các hoạt động kế cận. b) Kết hợp về mặt thời gian các hoạt động đồng nhất hoặc kế cận. 2.6. Nguyên tắc vạn năng Đối tượng thực hiện một số chức năng khác nhau, do đó không cần sự tham gia của các đối tượng khác. 2.7. Nguyên tắc “chứa trong” a) Một đối tượng được đặt bên trong đối tượng khác và bản thân nó lại chứa đối tượng thứ ba ... b) Một đối tượng chuyển động xuyên suốt bên trong đối tượng khác. 2.8. Nguyên tắc phản trọng lượng a) Bù trừ trọng lượng của đối tượng bằng cách gắn nó với các đối tượng khác có lực nâng. b) Bù trừ trọng lượng của đối tượng bằng tương tác với môi trường như sử dụng các lực thủy động, khí động... 2.9. Nguyên tắc gây ứng suất sơ bộ Gây ứng suất trước với đối tượng để chống lại ứng suất không cho phép hoặc không mong muốn khi đối tượng làm việc (hoặc gây ứng suất trước để khi làm việc sẽ dùng ứng suất ngược lại ). 2.10. Nguyên tắc thực hiện sơ bộ a) Thực hiện trước sự thay đổi cần có, hoàn toàn hoặc từng phần, đối với đối tượng. b) Cần sắp xếp đối tượng trước, sao cho chúng có thể hoạt động từ vị trí thuận lợi nhất, không mất thời gian dịch chuyển. Ngô Thùy Hương – 12 12 016 16 2.11. Nguyên tắc dự phòng Bù đắp độ tin cậy không lớn của đối tượng bằng cách chuẩn bị trước các phương tiện báo động, ứng cứu, an toàn. 2.12. Nguyên tắc đẳng thế Thay đổi điều kiện làm việc để không phải nâng lên hay hạ xuống các đối tượng. 2.13. Nguyên tắc đảo ngược a) Thay vì hành động như yêu cầu bài toán, hành động ngược lại (ví dụ, không làm nóng mà làm lạnh đối tượng) b) Làm phần chuyển động của đối tượng (hay môi trường bên ngoài) thành đứng yên và ngược lại, phần đứng yên thành chuyển động. 2.14. Nguyên tắc cầu (tròn) hoá a) Chuyển những phần thẳng của đối tượng thành cong, mặt phẳng thành mặt cầu, kết cấu hình hộp thành kết cấu hình cầu. b) Sử dụng các con lăn, viên bi, vòng xoắn. c) Chuyển sang chuyển động quay, sử dụng lực ly tâm. 2.15. Nguyên tắc linh động a) Cần thay đổi các đặt trưng của đối tượng hay môi trường bên ngoài sao cho chúng tối ưu trong từng giai đoạn làm việc. b) Phân chia đối tượng thành từng phần, có khả năng dịch chuyển với nhau. 2.16. Nguyên tắc giải “thiếu” hoặc “thừa” Nếu như khó nhận được 100% hiệu quả cần thiết, nên nhận ít hơn hoặc nhiều hơn “một chút”. Lúc đó bài toán có thể trở nên đơn giản hơn và dễ giải hơn. 2.17. Nguyên tắc chuyển sang chiều khác a) Những khó khăn do chuyển động (hay sắp xếp) đối tượng theo đường (một chiều) sẽ được khắc phục nếu cho đối tượng khả năng di chuyển trên mặt phẳng (hai chiều). Tương tự, những bài toán liên quan đến chuyển Ngô Thùy Hương – 12 12 016 17 động (hay sắp xếp) các đối tượng trên mặt phẳng sẽ được đơn giản hoá khi chuyển sang không gian (ba chiều). b) Chuyển các đối tượng có kết cấu một tầng thành nhiều tầng. c) Đặt đối tượng nằm nghiêng. d) Sử dụng mặt sau của diện tích cho trước. e) Sử dụng các luồng ánh sáng tới diện tích bên cạnh hoặc tới mặt sau của diện tích cho trước. 2.18. Nguyên tắc sử dụng các dao động cơ học a) Làm đối tượng dao động. Nếu đã có dao động, tăng tầng số dao động ( đến tầng số siêu âm). b) Sử dụng tầng số cộng hưởng. c) Thay vì dùng các bộ rung cơ học, dùng các bộ rung áp điện. d) Sử dụng siêu âm kết hợp với trường điện từ. 2.19. Nguyên tắc tác động theo chu kỳ a) Chuyển tác động liên tục thành tác động theo chu kỳ (xung). b) Nếu đã có tác động theo chu kỳ, hãy thay đổi chu kỳ. c) Sử dụng các khoảng thời gian giữa các xung để thực hiện tác động khác. 2.20. Nguyên tắc liên tục tác động có ích a) Thực hiện công việc một cách liên tục (tất cả các phần của đối tượng cần luôn luôn làm việc ở chế độ đủ tải). b) Khắc phục vận hành không tải và trung gian. c) Chuyển chuyển động tịnh tiến qua lại thành chuyển động qua. 2.21. Nguyên tắc “vượt nhanh” a. Vượt qua các giai đoạn có hại hoặc nguy hiểm với vận tốc lớn. b. Vượt nhanh để có được hiệu ứng cần thiết. Ngô Thùy Hương – 12 12 016 18 2.22. Nguyên tắc biến hại thành lợi a. Sử dụng những tác nhân có hại (thí dụ tác động có hại của môi trường) để thu được hiệu ứng có lợi. b. Khắc phục tác nhân có hại bằng cách kết hợp nó với tác nhân có hại khác. c. Tăng cường tác nhân có hại đến mức nó không còn có hại nữa. 2.23. Nguyên tắc quan hệ phản hồi a. Thiết lập quan hệ phản hồi b. Nếu đã có quan hệ phản hồi, hãy thay đổi nó. 2.24. Nguyên tắc sử dụng trung gian Sử dụng đối tượng trung gian, chuyển tiếp. 2.25. Nguyên tắc tự phục vụ a. đối tượng phải tự phục vụ bằng cách thực hiện các thao tác phụ trợ, sửa chữa. b. Sử dụng phế liệu, chát thải, năng lượng dư. 2.26. Nguyên tắc sao chép (copy) a. Thay vì sử dụng những cái không được phép, phức tạp, đắt tiền, không tiện lợi hoặc dễ vỡ, sử dụng bản sao. b. Thay thế đối tượng hoặc hệ các đối tượng bằng bản sao quang học (ảnh, hình vẽ) với các tỷ lệ cần thiết. c. Nếu không thể sử dụng bản sao quang học ở vùng biểu kiến (vùng ánh sáng nhìn thấy được bằng mắt thường), chuyển sang sử dụng các bản sao hồng ngoại hoặc tử ngoại. 2.27. Nguyên tắc “rẻ” thay cho “đắt” Thay thế đối tượng đắt tiền bằng bộ các đối tượng rẻ có chất lượng kém hơn (thí dụ như về tuổi thọ). Ngô Thùy Hương – 12 12 016 19 2.28. Thay thế sơ đồ cơ học a. Thay thế sơ đồ cơ học bằng điện, quang, nhiệt, âm hoặc mùi vị. b. Sử dụng điện trường, từ trường và điện từ trường trong tương tác với đối tượng c. Chuyển các trường đứng yên sang chuyển động, các trường cố định sang thay đổi theo thời gian, các trường đồng nhất sang có cấu trúc nhất định . d. Sử dụng các trường kết hợp với các hạt sắt từ. 2.29. Sử dụng các kết cấu khí và lỏng Thay cho các phần của đối tượng ở thể rắn, sử dụng các chất khí và lỏng: nạp khí, nạp chất lỏng, đệm không khí, thủy tĩnh, thủy phản lực. 2.30. Sử dụng vỏ dẻo và màng mỏng a. Sử dụng các vỏ dẻo và màng mỏng thay cho các kết cấu khối. b. Cách ly đối tượng với môi trường bên ngoài bằng các vỏ dẻo và màng mỏng. 2.31. Sử dụng các vật liệu nhiều lỗ a. Làm đối tượng có nhiều lỗ hoặc sử dụng thêm những chi tiết có nhiều lỗ (miếng đệm, tấm phủ…) b. Nếu đối tượng đã có nhiều lỗ, sơ bộ tẩm nó bằng chất nào đó. 2.32. Nguyên tắc thay đổi màu sắc a. Thay đổi màu sắc của đối tượng hay môi trường bên ngoài b. Thay đổi độ trong suốt của của đối tượng hay môi trường bên ngoài. c. Để có thể quan sát được những đối tượng hoặc những quá trình, sử dụng các chất phụ gia màu, hùynh quang. d. Nếu các chất phụ gia đó đã được sử dụng, dùng các nguyên tử đánh dấu. e. Sử dụng các hình vẽ, ký hiệu thích hợp. Ngô Thùy Hương – 12 12 016 20 2.33. Nguyên tắc đồng nhất Những đối tượng, tương tác với đối tượng cho trước, phải được làm từ cùng một vật liệu (hoặc từ vật liệu gần về các tính chất) với vật liệu chế tạo đối tượng cho trước. 2.34. Nguyên tắc phân hủy hoặc tái sinh các phần a. Phần đối tượng đã hoàn thành nhiệm vụ hoặc trở nên không cần thiết phải tự phân hủy (hoà tan, bay hơi..) hoặc phải biến dạng. b. Các phần mất mát của đối tượng phải được phục hồi trực tiếp trong quá trình làm việc. 2.35. Thay đổi các thông số hoá lý của đối tượng a. Thay đổi trạng thái đối tượng. b. Thay đổi nồng độ hay độ đậm đặc. c. Thay đổi độ dẻo d. Thay đổi nhiệt độ, thể tích. 2.36. Sử dụng chuyển pha Sử dụng các hiện tượng nảy sinh trong quá trình chuyển pha như: thay đổi thể tích, toả hay hấp thu nhiệt lượng... 2.37. Sử dụng sự nở nhiệt a. Sử dụng sự nở (hay co) nhiệt của các vật liệu. b. Nếu đã dùng sự nở nhiệt, sử dụng với vật liệu có các hệ số nở nhiệt khác nhau. 2.38. Sử dụng các chất oxy hoá mạnh a. Thay không khí thường bằng không khí giàu oxy. b. Thay không khí giàu oxy bằng chính oxy. c. Dùng các bức xạ ion hoá tác động lên không khí hoặc oxy. d. Thay oxy giàu ozon (hoặc oxy bị ion hoá) bằng chính ozon. Ngô Thùy Hương – 12 12 016 21 2.39. Thay đổi độ trơ a. Thay môi trường thông thường bằng môi trường trung hoà. b. Đưa thêm vào đối tượng các phần , các chất , phụ gia trung hoà. c. Thực hiện quá trình trong chân không. 2.40. Sử dụng các vật liệu hợp thành (composite) Chuyển từ các vật liệu đồng nhất sang sử dụng những vật liệu hợp thành (composite). Hay nói chung sử dụng các vật liệu mới. . Ngô Thùy Hương – 12 12 016 22 PHÂN TÍCH CÁC KỸ THUẬT KHÁM CHƯƠNG 3: PHÁ DỮ LIỆU & VIỆC ỨNG DỤNG CÁC NGUYÊN LÝ SÁNG TẠO KHOA HỌC TRONG ĐÓ I. GIỚI THIỆU 1.1. Giới thiệu Với mục tiêu tìm hiểu và nghiên cứu các kỹ thuật khám phá dữ liệu lưu trong hệ thống thông tin di động cộng tác. Trong phần này, với mỗi kiến trúc đã tìm hiểu em sẽ trình bày tổng quan về các kỹ thuật khám phá dữ liệu, đồng thời phân tích các nguyên lý sáng tạo được áp dụng trong các kiến trúc hệ thống thông tin di động cộng tác. 1.2. Kỹ thuật khám phá dữ liệu trong kiến trúc COCA Trong phần 1.2 này, em xin trình bày một mô hình cộng tác kho lưu trữ dữ liệu cục bộ, gọi là COCA (COoperative CAching) [5][6] của nhóm tác giả Chi-Yin Chow, Hong Va Leong và Alvin Chan. Kiến trúc COCA cho thấy sự hiệu quả trong truy vấn dữ liệu, giảm thời gian hồi đáp khi có yêu cầu dữ liệu từ một MH bất kì, các MHs ngoài vùng dịch vụ của BS có thể nhận được sự giúp đỡ của các MH láng giềng.  Khái quát kiến trúc COCA Trong COCA, mỗi MH và các MHs láng giềng của nó đều có thể chia sẻ thông tin theo kiểu ngang hàng (Peer - to – Peer) trong phạm vi truyền dẫn và tạo thành nhóm có tên “Nhóm động”(dynamic group). Như trong Hình 2 - 1, khi MH2 yêu cầu mục dữ liệu dx, đầu tiên nó sẽ tìm trong bộ nhớ cục bộ của chính nó. Nếu không tìm thấy dữ liệu trong bộ nhớ cục bộ, nó sẽ gửi yêu cầu đến các MHs trong nhóm là: MH1, MH3, MH7 trước khi gửi yêu cầu lên BS. Ngô Thùy Hương – 12 12 016 23 Hình 2 - 1: Kiến trúc COCA  Quá trình khám phá dữ liệu Quá trình khám phá mục dữ liệu của kiến trúc COCA được mô tả như trong Error! Reference source not found., Khi nhận được yêu cầu dữ liệu từ người dùng:  Bước 1: Đầu tiên, MH nguồn sẽ tìm kiếm mục dữ liệu yêu cầu trong bộ nhớ cục bộ (Local Cache Hit).  Bước 2: Nếu dữ liệu không được tìm thấy trong bộ nhớ cục bộ thì yêu cầu tìm kiếm sẽ được gửi “broadcast” đến các MHs trong vùng đồng thời tiếp tục lắng nghe tại kênh truyền “broadcast” được phát ra từ BS  Bước 3: Trong lúc chờ dữ liệu xuất hiện trên kênh truyền “broadcast”, nếu một trong số các MHs đích trong vùng có dữ liệu yêu cầu, MH đích trong vùng sẽ trả dữ liệu về cho MH nguồn trước khi có dữ liệu trên kênh truyền “broadcast”, MH nguồn sẽ chọn MH đích trả dữ liệu về sớm nhất và sẽ gửi thông điệp “retrieve” đến MH đích đó để nhận dữ liệu trả về (Global Cache Hit).  Bước 4: Trong trường hợp các MHs trong vùng không tìm thấy dữ liệu yêu cầu trong một khoảng thời gian nhất định, MH nguồn phải đợi đến khi dữ liệu xuất Ngô Thùy Hương – 12 12 016 24 hiện trên kênh truyền “broadcast” phát ra từ máy chủ. Nếu dữ liệu xuất hiện trên kênh truyền “broadcast” trước khi có tín hiệu trả về từ các MHs trong vùng, MH nguồn sẽ “bắt lấy” dữ liệu đó mà không cần gửi thông điệp “retrieve” đến các MHs đích trong vùng.  Bước 5: Tuy nhiên, nếu dữ liệu vẫn không được tìm thấy từ kênh truyền “broadcast” và các MHs trong vùng thì yêu cầu tìm kiến sẽ được gửi đếnBS qua kênh truyền Point-to-Point (Cache miss). 1.3. Kỹ thuật khám phá dữ liệu trong kiến trúc COOP Trong công trình nghiên cứu [10], tác giả: Yu Du và Sandeep K. S. Gupta đã đề xuất kiến trúc COOP giúp làm giảm số bản sao chép dữ liệu trong bộ nhớ giữa các MHs láng giềng và cho phép cộng tác bộ nhớ để lưu trữ nhiều hạng mục dữ liệu không trùng lắp nhằm cải thiện hiệu suất toàn hệ thống, cải tiến hiệu quả truy xuất và khả năng sử dụng lại dữ liệu tại mỗi MH.  Khái quát kiến trúc COOP Trong COOP, mỗi MH có cơ chế hoạt động như Hình 2 - 2: Hình 2 - 2: Cơ chế hoạt động của kiến trúc COOP Ngô Thùy Hương – 12 12 016 25 Trong COOP, khái niệm vùng cộng tác được định nghĩa như sau: vùng cộng tác của MHi bao gồm các MH xung quanh MHi, có khả năng liên lạc với MHi qua r bước chuyển (r-hop). Khi r càng lớn, vùng cộng tác càng được mở rộng, khả năng tìm thấy dữ liệu tăng lên, tuy nhiên lúc này chi phí tìm kiếm dữ liệu rất lớn. Do đó, cần cân nhắc khi chọn giá trị r.  Quá trình khám phá dữ liệu  Khi một MH yêu cầu mục dữ liệu:  Bước 1: Đầu tiên đầu tiên MH nguồn sẽ tìm kiếm trong bộ nhớ cục bộ của MH đó, nếu có dữ liệu, yêu cầu được giải quyết.  Bước 2: Nếu không tìm thấy, MH nguồn tiếp tục tìm kiếm trong kho dữ liệu cục bộ của các MH trong vùng của MHi, nếu tìm thấy dữ liệu, yêu cầu được giải quyết.  Bước 3: Nếu không, MH nguồn sẽ gửi yêu cầu dữ liệu đến BS để giải quyết yêu cầu dữ liệu. Trên đường đi đến BS, MH sẽ đi qua các MH trung gian, nếu tồn tại MH trung gian nào chứa dữ liệu yêu cầu, MH trung gian đó sẽ gửi dữ liệu về cho MH yêu cầu dữ liệu ban đầu, yêu cầu dữ liệu được giải quyết, quá trình gửi dữ liệu đến BS kết thúc. 1.4. Kỹ thuật khám phá dữ liệu trong mô hình cộng tác nhóm theo vùng CC (Cluster Cooperative Caching) Trong công trình nghiên cứu [3], tác giả Narottam Chand, R.C JoShi and Manoj Misra đề cập tới mô hình cộng tác theo vùng CC (Cluster Cooperative Caching). Trong CC, các cấu trúc liên kết mạng được phân chia thành các vùng kích thước bằng nhau, CC cải tiến đáng kể độ trễ truy vấn trung bình so với các chiến lược bộ nhớ đệm khác, nâng cao hiệu quả về mặt cộng tác và sử dụng bộ nhớ.  Khái quát kiến trúc Trong mỗi vùng, CC tự động chọn một MH trạng thái CSN (Cache State Node), CSN lưu trữ danh sách thông tin kho lưu trữ của các MH khác trong cụm CCS (Cluster Ngô Thùy Hương – 12 12 016 26 Cache State) cùng với khoảng thời gian sống TTL (time to live) của từng hạng mục dữ liệu. Với mỗi vùng CCS, cho phép một node lưu danh sách mục dữ liệu trong khoảng thời gian TTL. Khi một MH lưu trữ hay thay thế mục dữ liệu, CCS sẽ cập nhật lại CSN. CSN hoạt động như CCS chủ để lưu trữ các thông tin về các mục dữ liệu được lưu bởi MH trong nhóm, và được bổ sung trong quá trình tìm kiếm, kiểm soát thu nạp và thay thế dữ liệu.  Quá trình khám phá dữ liệu Trong CC, khi một MH tìm dữ liệu đầu tiên nó sẽ tìm trong bộ nhớ địa phương, nếu không có, nó sẽ yêu cầu tìm kiếm mục dữ liệu từ các MH khác trong cụm bằng cách gửi yêu cầu tới CSN. Nếu không tìm thấy mục dữ liệu yêu cầu từ các MH trong cùng cụm thì MH này sẽ gửi yêu cầu tới các MH nằm trên đường định tuyến tới BS. Nếu một cụm nằm trên đường định tuyến có mục dữ liệu mà MH yêu cầu thì nó sẽ không cần gửi yêu cầu tới BS. Ngược lại, MH có thể gửi yêu cầu tới BS để nhận được thông tin của mục dữ liệu cần tìm. Trong Hình 2 - 3, giả sử rằng MHi yêu cầu mục dữ liệu dx đến MHs đích, và giả sử con đường đi tới MHs là đi qua MHa, MHc, MHd. Ngô Thùy Hương – 12 12 016 27 Hình 2 - 3: Sự chuyển tiếp gói tin yêu cầu từ MHi nguồn tới MHs đích  Đầu tiên, MHi đầu tiên nó sẽ kiểm tra trong bộ nhớ cục bộ của chính nó. Nếu dữ liệu dx được tìm thấy thì kết quả sẽ được trả về. Nếu dữ liệu không được tìm thấy, MHi sẽ gửi gói tin “lookup” yêu cầu tìm kiếm lên CSN. CSN dựa vào thông tin tìm kiếm đó để tìm trong danh sách các cluters có dữ liệu dx. Nếu dữ liệu được tìm thấy thì CSN gửi 1 gói tin “ack” đến MHi, trong gói tin “ack” chứa thông tin địa chỉ ID của MH đích có chứa dx. Lúc này MHi gửi gói tin “confirm” tới MH đích có địa chỉ vừa nhận được từ gói tin “ack” và dữ liệu được trả về cho MHi. Nếu gói tin “ack” từ CSN là rỗng, nghĩa là trong vùng không có dữ liệu cần thiết. MHi sẽ gửi gói tin yêu cầu đến các MHa bên cạnh.  Khi MHk nhận được gói tin yêu cầu, k ∈ {a, c, d}, MHk sẽ gửi gói tin “lookup” tới CSN, nếu không có chứa mục dữ liêu dx, Khi MHk nhận một gói “ack” nó sẽ gửi gói tin “confirm” cho MH trong cụm hoặc gửi gói tin yêu cầu tới MH kế tiếp dựa trên địa chỉ trả về trong gói tin “ack” như mô tả ở trên. Ngô Thùy Hương – 12 12 016 28  Khi một MH hoặc MHs nhận được gói tin “confirm”, nó sẽ gửi gói tin “reply” cho MH nguồn.  Gói tin “reply” chứa id của mục dữ liệu dx, dữ liệu thật Dx, và thời gian sống TTLx. 1.5. Kỹ thuật khám phá dữ liệu trong cách tiệp cận khác cho cộng tác bộ nhớ PROACTIVE (Proactive Approach Caching) Trong công trình nghiên cứu [4], tác giả : Prashant Kumar, Naveen Chauhan, LK Awasthi và Narottam Chand đề xuất một phương pháp tiếp cận mới chủ động trong việc hợp tác bộ nhớ đệm trong mạng Manets là PROACTIVE (Proactive Approach Caching) giúp cải thiện hiệu quả sự sẵn có của dự liệu, ít hao tốn tài nguyên và hiệu suất trên toàn bộ hệ thống.  Khái quát kiến trúc Trong công trình nghiên cứu [4], mỗi MH sẽ liên kết tạo thành một khu vực (zone), mỗi khu vực sẽ có một MH quản lý (zone manager). Mỗi MH sẽ duy trì một bảng CIT (Cache Information Table) nhằm quản lý dữ liệu trong vùng. Giả sử, xét MH nguồn là A với mục dữ liệu tương ứng d. Thông tin bảng CIT của MH A như Bảng 2 - 1: STT Tên Mục Ý nghĩa Giá trị khởi tạo 1 d.available Cho biết d có lưu trong bộ nhớ cục bộ hay không FALSE 2 d.nnode Cho biết danh sách MH láng giềng của A lưu mục dữ liệu d. NULL 3 d.accesscount Số lượng MH láng giềng của A lưu mục dữ liệu d 0 4 d.TTL Thời gian sống của mục dữ liệu d Được chỉ định bởi dữ liệu trung tâm Bảng 2 - 1: Mô tả thông tin bảng CIT của MH A Ngô Thùy Hương – 12 12 016 29  Quá trình khám phá dữ liệu  Bước 1: Khi yêu cầu hạng mục dữ liệu, đầu tiên, MH nguồn sẽ tìm kiếm tại kho lưu trữ cục bộ (local cache) trước, sau đó là tìm kiếm thông tin lưu trữ trong bảng CIT (Hình A - 1). Hình A - 1: Tìm kiếm tại MH nguồn.  Bước 2: Nếu không tìm thấy tại cả kho lưu trữ cục bộ và bảng CIT thì MH nguồn sẽ gửi “broadcast” các yêu cầu dữ liệu đến các MHs lân cận. Khi các MHs lân cận nhận được thông điệp này nó cũng kiểm tra kho lưu trữ cục bộ và trong bảng CIT của chính nó (nếu có chứa mục dữ liệu yêu cầu, nó sẽ gửi trả dữ liệu về cho MH nguồn) (Hình A - 2). Hình A - 2: Tìm kiếm tại các MHs láng giềng  Bước 3: Nếu không nhận được bất kì thông điệp phản hồi từ các MHs láng giềng, MH nguồn sẽ gửi yêu cầu lên BS để lấy dữ liệu. Trên đường định tuyến lên BS nó sẽ đi Ngô Thùy Hương – 12 12 016 30 qua các MHs trung gian và tại các MHs trung gian cũng kiểm tra kho lưu trữ cục bộ và bảng CIT của chính nó, nếu tìm thấy mục dữ liệu yêu cầu thì sẽ dừng việc chuyển tiếp yêu cầu dữ liệu tới BS và gửi dữ liệu về cho MH yêu cầu (Hình A - 3). Hình A - 3: Gửi yêu cầu dữ liệu lên BS. Đồng thời, trong quá trình tìm kiếm dữ liệu, khi đã nhận được dữ liệu từ vùng hay BS thì MH yêu cầu sẽ “broadcast” dữ liệu nó vừa lưu, và dữ liệu nào đã xóa khi thay thế để cho các MH láng giềng cập nhật lại bảng CIT. II. PHÂN TÍCH CÁC NGUYÊN LÝ SÁNG TẠO KHOA HỌC ĐƯỢC ÁP DỤNG TRONG CÁC KỸ THUẬT KHÁM PHÁ DỮ LIỆU 2.1. Nguyên lý phân nhỏ Áp dụng nguyên lý phân nhỏ, trong kiến trúc COCA, việc tìm kiếm mục dữ liệu sẽ được tiến hành chia nhỏ tại kho lưu trữ cục bộ và các láng giềng trong vòng bán kính một bước nhảy, đồng thời lắng nghe trên kênh truyền “Broadcast” được phát ra từ BS, nên tỷ lệ tìm kiếm được dữ liệu sẽ thấp. Trong kiến trúc COOP, việc khám phá hạng mục dữ liệu sẽ được tiến hành loang mù, nên tỷ lệ tìm thấy dữ liệu sẽ rất cao. Kiến trúc CC đã tối ưu được không gian bộ nhớ cục bộ (không trùng lắp dữ liệu, thu nạp dữ liệu cũng có sự cộng tác nhờ các MHs láng giềng lưu dùm mục dữ liệu khi không Ngô Thùy Hương – 12 12 016 31 có đủ không gian bộ nhớ), dùng cộng tác theo vùng để tăng khả năng cộng tác chia sẽ dữ liệu, giảm khả năng trùng lắp dữ liệu. Tuy nhiên, việc tìm kiếm, thu nạp và thay thế đều phụ thuộc vào CSN sẽ dẫn tới khó khăn nếu CSN bị mất kết nối. 2.2. Nguyên tắc kết hợp Áp dụng nguyên lý kết hợp, trong COCA, việc tìm kiếm dữ liệu sẽ tìm trong vùng và máy chủ. Trong COOP, việc tìm kiếm dữ liệu sẽ tìm kiếm trong vùng, loang mù hai bước nhảy (hops) và máy chủ. Trong CC, cũng tiến hành tìm kiếm dữ liệu theo cách loang mù, tìm trong vùng rồi tìm tại máy chủ. Trong PROACTIVE: cũng tiến hành tìm kiếm dữ liệu trong vùng, loang mù ra ngoài vùng và máy chủ có xây dựng đường định tuyến. Chi phí xử lý cao. Tốn không gian bộ nhớ. Có tổ chức cấu trúc dữ liệu, xây dựng đường định tuyến nên tỷ lệ số thông điệp trung bình khi yêu cầu hạng mục dữ liệu sẽ giảm. 2.3. Nguyên tắc vạn năng Áp dụng nguyên lý vạn năng, trong kiến trúc COOP, có cơ chế là lưu vết thông tin tìm kiếm (Profile-based resolution). Cơ chế lưu vết thông tin tìm kiếm hoạt động dựa trên việc lưu trữ thông tin các câu yêu cầu dữ liệu đã được xử lý trước đó vào bảng RRT (Recent request table). Nhờ bảng RRT, ta sẽ biết chính xác MH nào đang giữ dữ liệu được yêu cầu, nhờ đó tiết kiệm thời gian chờ và tránh quá trình tìm kiếm hai lần cho cùng một yêu cầu dữ liệu. Bảng RRT được chia thành nhiều mục. Mỗi mục chứa một yêu cầu dữ liệu thành công trước đó. Các thông tin được lưu trữ trong một mục dữ liệu gồm: MH gửi dữ liệu (the sender), dữ liệu yêu cầu (the target), nhãn thời gian (timestamp of the request) [18]. Kiến trúc PROACTIVE cải thiện hiệu quả sự sẵn có của dự liệu, ít hao tốn tài nguyên và cải thiện hiệu suất trên toàn bộ hệ thống. Trong kiến trúc PROACTIVE có bảng CIT, khi tìm kiếm mục dữ liệu, không có loang mù, trong trường hợp yêu cầu dữ liệu phải gửi Ngô Thùy Hương – 12 12 016 32 tới BS thì sẽ gửi thông qua con đường định tuyến qua các MH để tới được BS, thay vì đi theo đường truyền trực tiếp qua kênh uplink, nên tỷ lệ số thông điệp trung bình sẽ thấp.. 2.4. Nguyên tắc thực hiện sơ bộ Áp dụng nguyên lý thực hiện sơ bộ, trong các kiến trúc, khi tìm kiếm dữ liệu đều thực hiện tại bộ nhớ cục bộ truơc. Nếu tìm thấy thông tin dữ liệu được yêu cầu sẽ dừng lại, tránh mất nhiều thời gian tìm kiếm. Nếu có không tìm thấy dữ liệu sẽ được phản hồi một cách nhanh chóng để máy client có thể ra những thông điệp chính xác. Mục đích của quá trình này đảm bảo máy client có thể thực hiện tốt trước khi phải gửi yêu cầu lên máy chủ. 2.5. Nguyên tắc dự phòng Áp dụng nguyên lý dự phòng, trong quá trình gửi thông điệp trực tuyến thường lượng dữ liệu thông tin tại máy khách rất lớn, do vậy tại các máy khách sẽ có thực hiện việc sao lưu lại các thông tin đó một cách định kì nhằm đảm bảo dữ liệu cục bộ không bị mất khi có sự cố xảy ra. 2.6. Nguyên tắc linh động Áp dụng nguyên lý linh động, trong các kiến trúc, khi dữ liệu yêu cầu không được tìm thấy tại bộ nhớ cục bộ, thì có khả năng nó sẽ có ở những máy khách hàng xóm xung quanh nó và máy client sẽ gửi thông điệp tới những máy xung quanh vùng của nó. 2.7. Nguyên tắc biến hại thành lợi Áp dụng nguyên lý biến hại thành lợi, trong khi tìm kiếm dữ liệu được yêu cầu, đôi lúc các thông điệp sẽ bị phản hồi sai, và sẽ gửi sai dữ liệu được yêu cầu, thì tại máy yêu cầu dữ liệu, sẽ tiến hành lưu dữ liệu đó, thay vì gửi trả lại dữ liệu cho máy phản hồi về dữ liệu sai. Điều này làm giảm số lượng thông điệp phát sinh và chi phí truyền nhận thông điệp, tăng cường sự sẵn có dữ liệu trong vùng. Ngô Thùy Hương – 12 12 016 33 ỨNG DỤNG CƠ SỞ LÝ THUYẾT CHƯƠNG 4: NGHIÊN CỨU KHOA HỌC VÀO CÔNG VIỆC NGHIÊN CỨU THỰC TIỄN CỦA BẢN THÂN I. GIỚI THIỆU Tên đề tài: “Các thủ thuật (nguyên tắc) sáng tạo được áp dụng vào bài toán khám phá dữ liệu trong hệ thống thông tin di động cộng tác”. 1.1. Giới thiệu MIXGROUP [1][1] là một mô hình cộng tác kho lưu trữ theo nhóm trong hệ thống thông tin di động. Kiến trúc này đã được cô Nguyễn Trần Minh Thư đề xuất và thử nghiệm dựa trên một số độ đo như: số thông điệp trung bình, thời gian hồi đáp dữ liệu, tỷ lệ tìm thấy dữ liệu...Tuy nhiên, điểm khó khăn trong các kiến trúc cộng tác dữ liệu nói chung cũng như kiến trúc MIXGROUP nói riêng là tìm ra một kỹ thuật khám phá dữ liệu ngoài vùng so với MH nguồn hiệu quả. Thông qua quá trình tìm hiểu về các kỹ thuật khám phá dữ liệu trong hệ thống thông tin di động, dựa trên ý kiến đề xuất của cô Minh Thư, em thực hiện hóa kỹ thuật khám phá dữ liệu dựa trên việc tính khoảng cách giữa các MHs vào trong kiến trúc MIXGROUP: kỹ thuật tính khoảng cách dựa trên bước nhảy (được gọi là MIXGROUP - Distance By Hops) và kỹ thuật tính khoảng cách theo Ơ-clit (được gọi là MIXGROUP - Distance By Euclide). 1.2. Kiến trúc MIXGROUP Trước hết, em xin trình bày lại những nét cơ bản về mô hình và nguyên lý hoạt động của kiến trúc MIXGROUP đã được xây dựng ở [12][1]. MIXGROUP là kiến trúc hệ thống thông tin di động có áp dụng kiến trúc mạng MANET, được thể hiện ở Hình 3 - 1. Kiến trúc gồm các phần chính như sau: máy chủ (Server), Trạm thông tin (BS), và các máy khách (có thể được gọi là các thiết bị di động – MH (Mobile host) – MU (Mobile User)). Ngô Thùy Hương – 12 12 016 34 Hình 3 - 1: Mô hình kiến trúc hệ thống  Server: nơi quản lý toàn bộ dữ liệu cho của hệ thống, cung cấp dữ liệu cho các BS  BS: là nơi lưu trữ và cung cấp dữ liệu cho các MH trong phạm vi của nó thông qua mạng vô tuyến. Dữ liệu của BS được cung cấp bởi máy chủ thông qua mạng hữu tuyến.  Máy khách (hay còn gọi là MH, MU): là các thiết bị di động có khả năng xử lý thông tin như PDA, laptop, … Các máy có thể truy xuất dữ liệu từ BS mà nó kết nối được hoặc thông qua các máy khác bằng đường định tuyến. Liên lạc giữa thiết bị di động và BS cũng như giữa các thiết bị di động với nhau thông qua mạng vô tuyến. 1.3. Nguyên lý tìm kiếm dữ liệu của MIXGROUP Khi yêu cầu dữ liệu được phát ra, đầu tiên MH nguồn sẽ tìm trong kho lưu trữ cục bộ của chính nó, nếu dữ liệu được tìm thấy thì kết quả sẽ được trả về cho người dùng, những phần dữ liệu còn lại không được tìm thấy thì MH sẽ gửi yêu cầu tìm kiếm đến các MHs khác trong vùng bán kính một bước nhảy. Nếu dữ liệu không được tìm thấy tại MH trong vùng bán kính một bước nhảy thì yêu cầu tìm kiếm sẽ được mở rộng ra đến các MHs ngoài vùng với phạm vi giao tiếp là k bước nhảy, nếu trong phạm vi k bước nhảy hoặc hết thời gian chờ cho phép vẫn không tìm thấy dữ liệu thì yêu cầu sẽ được gửi lên BS. Tất cả các MHs giao tiếp với nhau thông qua mạng vô tuyến. Ngô Thùy Hương – 12 12 016 35 II. ÁP DỤNG CÁC NGUYÊN LÝ NGHIÊN CỨU KHOA HỌC TRONG QUÁ TRÌNH NGHIÊN CỨU 2.1. Nguyên lý phân nhỏ Áp dụng nguyên lý phân nhỏ, MIXGROUP đã phân chia hệ thống tìm kiếm thành từng module nhỏ, mỗi module đảm nhiệm một vai trò. Trong kiến trúc MIXGROUP, mỗi MH sẽ có một bảng ZoneData cho biết thông tin về những máy trong nhóm (trong phạm vi 1 bước nhảy) và những dữ liệu lưu trữ tại mỗi máy đó thông qua bảng ZoneData. Mục tiêu của bảng ZoneData là cho biết những máy nào có dữ liệu yêu cầu, để máy nguồn sẽ truy xuất đến lấy dữ liệu, tránh tình trạng loang hết (loang mù) đến các máy khác trong nhóm và một bảng OutZoneData cho biết những máy ngoài nhóm nào có dữ liệu yêu cầu, để máy nguồn truy xuất đến lấy dữ liệu, tránh tình trạng loang hết (loang mù) đến các máy khác ngoài nhóm. Ví dụ như trong Hình 3 - 2, MH4 có các nút vùng là MH1, MH3, MH6, MH7, các nút mạng là MH2, MH9, MH8. Hình 3 - 2: Nguyên lý hoạt động của kiến trúc đề xuất Ngô Thùy Hương – 12 12 016 36 2.2. Nguyên lý kết hợp Áp dụng nguyên lý kết hợp, quá trình khám phá dữ liệu của kiến trúc MIXGROUP sẽ kết hợp thêm với việc áp dụng kỹ thuật tính khoảng cách giữa các MHs vào MIXGROUP [1][1] để phục vụ cho quá trình tìm kiếm dữ liệu ngoài nhóm cộng tác. Cụ thể, trong phần này em sẽ trình bày chi tiết quá trình xử lý truy vấn ngoài vùng dựa trên bảng thông tin OutZoneData và kỹ thuật tính khoảng cách giữa các MHs theo hai cách khác nhau là: (i) dựa khoảng cách tọa độ giữa các MHs (khoảng cách Ơ-clit) , (ii) dựa vào số bước nhảy (hop). Chi tiết các kỹ thuật này được áp dụng vào bảng OutZone Data được trình bày như sau: Thông qua bảng OutZone Data, máy nguồn có thể xác định được danh sách các máy ngoài nhóm cộng tác (ngoài phạm vi một bước nhảy) có chứa dữ liệu cần tìm, và gửi thông điệp yêu cầu đến các máy đó. Tuy nhiên, việc gửi thông điệp đến các máy ngoài nhóm, MIXGROUP sẽ tiến hành gửi thông điệp cho tất cả các máy ngoài vùng có chứa mục dữ liệu mà không xác định khoảng cách xa gần so với máy nguồn. Đây chính là điểm mấu chốt sẽ được thực hiện trong việc áp dụng kỹ thuật tính khoảng cách trong MIXGROUP - Distance By Hops và MIXGROUP - Distance By Euclide. 2.3. Nguyên lý linh động Áp dụng nguyên lý linh động trong phận tích: Khi máy nguồn tiến hành tìm kiếm dữ liệu ngoài vùng (ngoài phạm vi lớn hơn 1 bước nhảy): Nếu như trong kiến trúc MIXGROUP ban đầu, máy nguồn sẽ gửi yêu cầu đến tất cả các máy ngoài nhóm có chứa dữ liệu được lưu thông tin trong bảng OutzoneData, thì khi áp dụng kỹ thuật tìm kiếm dữ liệu dựa vào khoảng cách tính theo số bước nhảy (MIXGROUP – Distance By Hops), máy nguồn sẽ chỉ gửi yêu cầu đến các máy có khoảng cách tính theo số bước nhảy là nhỏ nhất nhằm tiết kiệm chi phí và thời gian truy vấn dữ liệu, lúc này trong bảng OutzoneData sẽ chứa những thông tin sau: Id của mục dữ Ngô Thùy Hương – 12 12 016 37 liệu, Id MH chứa mục dữ liệu và tham số m (thông tin về số bước nhảy so với MH nguồn). Trong Error! Reference source not found., sau khi nhận được gói tin “REQUEST_OUT” yêu cầu dữ liệu từ máy nguồn, máy chứa dữ liệu sẽ tìm kiếm trong kho lưu trữ cục bộ của chính nó và gửi trực tiếp kết quả về cho máy nguồn trong gói tin “RE_REQUEST_OUT”. Sau khi nhận được gói tin “RE_REQUEST_OUT” chứa thông tin các hạng mục dữ liệu từ các máy ngoài nhóm, máy nguồn sẽ lựa chọn kết quả gửi về đầu tiên để xử lý trả lời cho người dùng. Danh sách thông tin các dữ liệu còn lại không tìm thấy trong bảng OutZoneData sẽ được chuyển yêu cầu tìm kiếm đến BS kèm theo thông điệp “REQUEST_BS”. Tại BS sẽ tiến hành gửi dữ liệu về cho MH nguồn, hoàn tất một quá trình truy vấn dữ liệu. Ví dụ một mô hình mạng gồm các MHs là 1, 2, 3, 4, 5, 6, 7. Trong đó, MH1 là MH nguồn yêu cầu mục dữ liệu d. Hình 3 - 3: Mô phỏng cách tính khoảng cách theo bước nhảy Và lúc này trong thông tin của bảng OutzoneData sẽ như sau: Ngô Thùy Hương – 12 12 016 38 Id mục dữ liệu d Danh sách các MH chứa mục dữ liệu d Số bước nhảy (so với MH 1) 4 2 5 4 7 3 Dựa vào thông tin bảng Outzone, ta biết được MH 4 là MH gần nhất với MH 1. Ta sẽ chọn MH 4, là MH để gửi thông tin yêu cầu dữ liệu, lúc này sẽ giảm được 2/3 số thông điệp cần phát ra so với cách tìm kiếm dữ liệu ngoài vùng của MIXGROUP ban đầu. 2.4. Nguyên lý hoạt động theo chu kỳ Áp dụng nguyên lý hoạt động theo chu kỳ, để đảm bảo cho quá trình thực thi, chương trình mô phỏng sẽ có cấu trúc như sau: Hình 4.1 Cấu trúc mô phỏng chương trình Ngô Thùy Hương – 12 12 016 39 Giao thức “protoname” là giao thức chính của chương trình bao gồm các lớp chức năng: local_data, zone_data, out_zone_data. Tại lớp protoname sẽ gọi xử lý đến các lớp này. Hình 4 - 1: Sơ đồ phân bổ luồng xử lý 2.5. Nguyên lý sử dụng trung gian Áp dụng nguyên lý sử dụng trung gian: Trong khám phá dữ liệu, quá trình xử lý cuối cùng là phát sinh thông điệp dựa vào bảng Outzone Data. Cũng giống như khi áp dụng kỹ thuật tìm kiếm dữ liệu ngoài vùng bằng cách tính khoảng cách theo bước nhảy, thì kỹ thuật tìm kiếm dữ liệu ngoài vùng bằng cách tính khoảng cách theo Ơ-Clit, nguyên tắc tìm kiếm sẽ là máy nguồn sẽ chỉ gửi yêu cầu đến các máy có khoảng cách tính theo Ơ - Clit là nhỏ nhất nhằm tiết kiệm chi phí và thời gian truy vấn dữ liệu, lúc này trong bảng OutzoneData sẽ chứa những thông tin sau: Id của mục dữ liệu, Id MH chứa mục dữ liệu và tham số m (thông tin về khoảng cách theo Ơ- Clit so với MH nguồn). Ví dụ một mô hình mạng gồm các MHs là 1, 2, 3, 4, 5, 6, 7. Tọa độ của các MHs lần lượt là (x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), (x6, y6), (x7, y7). Trong đó, MH1 là MH nguồn yêu cầu mục dữ liệu d. Ngô Thùy Hương – 12 12 016 40 Hình 3 - 4: Mô phỏng cách tính khoảng cách theo Euclide Và giả sử ta tính được khoảng cách Ơ – Clit: ||14|| = d1, ||16|| = d2, ||15|| = d3như trên Hình 3 - 4 và giả sử d1 là khoảng cách nhỏ nhất. Trong thông tin của bảng OutzoneData sẽ như sau: Id mục dữ liệu d Danh sách các MH chứa mục dữ liệu d Khoảng cách Ơ - Clit (so với MH 1) 4 d1 6 d2 5 d3 Dựa vào thông tin bảng Outzone, ta thấy MH 4 là MH gần nhất với MH 1. Ta sẽ chọn MH 4, là MH để gửi thông tin yêu cầu dữ liệu, lúc này sẽ giảm được 2/3 Ngô Thùy Hương – 12 12 016 41 số thông điệp cần phát ra so với cách tìm kiếm dữ liệu ngoài vùng của MIXGROUP ban đầu”. III. ĐỀ XUẤT VÀ KẾT LUẬN 3.1. Đề Xuất Qua quá trình tìm hiểu viết bài thu hoạch, đã cho em thấy giá trị vô hình to lớn của 40 Nguyên tắc sáng tạo mà Genrich Altshuller đúc kết ra.Chính những nguyên tắc này đã giúp cho con người chúng ta có những hướng để giải quyết vấn đề từ đơn giản đến phức tạp. Em xin đề xuất một số ý tưởng để có thể triển khai ngoài thực tế cũng như hoàn thiện kiến trúc tốt hơn: xây dựng kỹ thuật cộng tác khám phá chia sẽ dữ liệu theo nhóm trong bán kính k bước nhảy. Xây dựng lớp giao tiếp giữa tầng ứng dụng và tầng mạng nhằm giúp tầng ứng dụng có thể đọc được bảng giao thức định tuyến chính xác, từ đó nắm rõ đường đi đến các MH khác để chọn lựa MH có chi phí tốt nhất. 3.2. Kết luận Ngày nay, với sự tiến bộ của khoa học kỹ thuật làm thế giới trở nên bình đẳng hơn, các biên giới quốc gia chỉ còn giá trị về địa lý thì cơ hội thành công là rất rõ rệt với tất cả mọi người. Do đó việc nắm vững 40 phương pháp sáng tạo sẽ là chìa khoá để mở cánh cửa thành công làm nên cuộc cách mạng công nghệ mới. Ngô Thùy Hương – 12 12 016 42 TÀI LIỆU THAM KHẢO Các tài liệu tiếng Anh: [1] Thu T.M Nguyen, Thuy T.B Dong, “An Efficient Model for Cooperative Caching in Mobile Information Systems”. The Seventh International Symposium on Frontiers of Information Systems and Network Applications (FINA 2011), Biopolis, Singapore, March 22 - 25, 2011. [2] Liangzhong Yin and Guohong Cao. “Supporting Cooperative Caching in Ad Hoc Networks”, Department of Computer Science & Engineering The Pennsylvania State University University Park, PA 16802, 2004. [3] Narottam Chand, R.C JoShi and Manoj Misra, “Cooperative Caching Strategy in Mobile Ad Hoc Networks Based on Clusters”, Department of Electronics and Computer Engineering, Indian Institute of Technology, Roorkee, India, 2006. [4] Prashant Kumar, Naveen Chauhan, LK Awasthi, Narottam Chand, “Proactive Approach for Cooperative Caching in Mobile Adhoc Networks”, Department of Computer Science, National Institute of Technology Hamirpur, INDIA, 2010. [5] Chi-Yin Chow, Hong Va Leong, Alvin Chan, “Peer-to-Peer Cooperative Caching in Mobile Environments”, Department of Computing, Hong Kong Polytechnic University, Hong Kong, 2004. [6] Chi-Yin Chow Hong Va Leong Alvin Chan, “Peer-to-Peer Cooperative Caching in a Hybrid Data Delivery Environment”, Department of Computing, Hong Kong Polytechnic University, Hong Kong, 2004. [7] Chi-Yin Chow Hong Va Leong Alvin Chan, “Group-based Cooperative Cache Management for Mobile Clients in a Mobile Environment”, Department of Computing, Hong Kong Polytechnic University, Hong Kong, 2004. Ngô Thùy Hương – 12 12 016 43 [8] Chi-Yin Chow, Hong Va Leong and Alvin T. S. Chan, “Distributed Group-based Cooperative Caching in a Mobile Broadcast Environment”, Department of Computing The Hong Kong Polytechnic University, Hong Kong, 2005. [9] G. Anandharaj and R. Anitha, “An improved Architecture for Complete Cache Management in Mobile Computing Environments”, Sengunthar Engineering College, K.S Rangasamy College of Technology, Tiruchengode, Tamil Nadu, India, 2009. [10] Yu Du and Sandeep K. S. Gupta, “COOP - A cooperative caching service in MANETs”, Department of Computer Science and Enginnering Ira A. Fulton School of Engineering at Arizona State University, 2005. [11] Yi-Wei Ting and Yeim-Kuan Chang, “ A Novel Cooperative Caching Scheme for Wireless Ad Hoc Networks: GroupCaching”, Department of Computer Science and Information Engineering National Cheng Kung University 701 Tainan, Taiwan R.O.C., 2007. Các tài liệu tiếng Việt: [12] Nguyễn Trần Minh Thư, Đồng Thị Bích Thủy “Hệ Thống Thông Tin Di Động và Kỹ thuật Kho Lưu Trữ Lại”. Hội thảo khoa học quốc gia lần thứ 4 về Nghiên cứu cơ bản và Ứng dụng Công nghệ Thông tin (FAIR 2009),Trường ĐH Công nghệ- ĐHQG Hà Nội, 25-26/12/2009. [13] Ngô Thùy Hương, Hà Văn Hoạt, “Khảo sát và thử nghiệm các kỹ thuật thu nạp dữ liệu và khám phá dữ liệu lưu trong hệ thống thông tin di động cộng tác.”, luận văn cử nhân – Khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, 2011. [14] Võ Văn Sinh, Phạm Xuân Quang, “Nghiên cứu mô hình cộng tác dữ liệu theo nhóm trong môi trường hệ thống thông tin di động và xây dựng ứng dụng Ngô Thùy Hương – 12 12 016 44 thử nghiệm”, luận văn cử nhân – Khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, 2011. [15] Trần Đức Duy, Trương Thị Anh Đào, “Nghiên cứu và thử nghiệm kỹ thuật cộng tác kho dữ liệu trong HTTT di động dựa trên kỹ thuật phân vùng”, luận văn cử nhân – Khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, 2011. [16] Phạm Minh Tú, Hồ Lê Thị Kim Nhung, “Nghiên cứu, vận dụng mô hình mạng P2P vào kiến trúc hệ thống thông tin di động hiệu quả”, luận văn cử nhân - Khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, 2010. [17] La Phương Thanh, Lê Thị Thanh Thúy, “Nghiên cứu kỹ thuật cộng tác kho dữ liệu lưu giữa các clients trong hệ thống thông tin di động dựa trên kiến trúc P2P”, luận văn cử nhân – Khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, 2010. [18] Lương Phương Hiền, Trương Thị Tuệ Mai, “Nghiên cứu kiến trúc hoàn chỉnh phục vụ truy vấn trong hệ thống thông tin di động và cài đặt thử nghiệm”, luận văn cử nhân – Khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, 2011. [19] Slide _ Phương pháp nghiên cứu khoa học trong tin học _ GS.TSKH. Hoàng Kiếm [20] Phương pháp luận sáng tạo khoa học – kỹ thuật giải quyết vấn đề và ra quyết định (giáo trình tóm tắt) _ Phan Dũng [21] Phương pháp nghiên cứu khoa học _ TS. Đinh Tuấn Hải