TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC LẦN THỨ XXVIII NĂM HỌC 2010 – 2011 THÁNG NĂM 2011 BAN TỔ CHỨC HỘI NGHỊ BAN TỔ CHỨC Trưởng ban: TS Nguyễn Kim Khánh Phó trưởng ban: ThS Trần Tuấn Vinh Ủy viên: TS Trần Đức Khánh Ủy viên: KS Đỗ Bá Lâm Ủy viên: KS Nguyễn Tuấn Hải Đại diện Bộ môn, trung tâm BAN CHƯƠNG TRÌNH GS Nguyễn Thanh Thủy PGS.TS Đặng Văn Chuyết PGS.TS Nguyễn Thị Hoàng Lan TS Vũ Tuyết Trinh TS Lê Thanh Hương TS Nguyễn Hồng Quang TS Vũ Thị Hương Giang TS Cao Tuấn Dũng TS Đỗ Phan Thuận TS Hà Quốc Trung TS Ngô Hồng Sơn TS Ngô Quỳnh Thu TS Nguyễn Hữu Đức TS Nguyễn Khánh Văn TS Nguyễn Linh Giang TS Nguyễn Nhật Quang TS Nguyễn Thị Oanh TS Phạm Đăng Hải TS Phạm Huy Hoàng TS Tạ Hải Tùng TS Tạ Tuấn Anh TS Trần Đức Khánh TS Trương Thị Diệu Linh ThS Đỗ Văn Uy ThS Bùi Trọng Tùng ThS Huỳnh Thị Thanh Bình ThS Lương Ánh Hồng ThS Ngơ Tuấn Phong ThS Nguyễn Đức Tiến ThS Nguyễn Duy Hiệp ThS Nguyễn Mạnh Tuấn ThS Nguyễn Thị Thu Trang ThS Nguyễn Tiến Thành ThS Phạm Ngọc Hưng ThS Phạm Văn Thuận ThS Trần Nguyên Ngọc ThS Trần Tuấn Vinh KS Hoàng Văn Hiệp KS Phạm Hồng Phong KS Đỗ Bá Lâm LỜI GIỚI THIỆU Hội nghị Sinh viên nghiên cứu khoa học (SVNCKH) kiện thường niên tổ chức Đại học Bách Khoa Hà Nội, có tham gia Viện Công nghệ thông tin Truyền thơng (CNTT&TT) Chính từ hội nghị này, nhiều cơng trình nghiên cứu xuất sắc có tính khoa học cao phát bồi dưỡng để tham gia đạt giải thi cao Giải thưởng SVNCKH Bộ Giáo dục Đào tạo, Giải thưởng sáng tạo WIPO dành cho sinh viên…Hội nghị SVNCKH hàng năm sân chơi kích thích niềm sáng tạo, giúp sinh viên làm quen với thử thách nghiệp nghiên cứu, tìm tịi tri thức Phát huy kết đạt được, năm học 2010 – 2011, Viện CNTT&TT tiếp tục tổ chức kiện nhằm tìm cơng trình xuất sắc để trao giải đề cử tham gia thi SVNCKH cấp Bộ Có 43 cơng trình gửi báo cáo để đăng kỉ yếu chung Hội nghị Các báo cáo phân công phản biện giảng viên Viện CNTT&TT Kết phản biện sử dụng làm sở để chọn cơng trình có chất lượng tốt nhất, trình bày thức trước hội đồng chấm giải Viện Quyển kỉ yếu Hội nghị SVNCKH – Viện CNTT&TT thể kết làm việc nghiêm túc, đầy nỗ lực sinh viên giảng viên hướng dẫn nghiên cứu giảng dạy năm học 2010 – 2011 Cuốn kỉ yếu kỉ niệm đẹp, đánh dấu mốc son bắt đầu nghiệp nghiên cứu khoa học em sinh viên có cơng trình nghiên cứu đăng tải Chúc em ln sáng tạo, biết phát huy tri thức học tập làm việc! Thay mặt Ban Tổ Chức TS Nguyễn Kim Khánh Phó Viện Trưởng Viện CNTT&TT Đại học Bách Khoa Hà Nội Mục lục STT CƠNG TRÌNH - TÁC GIẢ TRANG ExpertRank: Thuật toán lặp đánh giá chuyên môn người dùng chất lượng câu trả lời hệ thống hỏi đáp cỡ lớn Nguyễn Văn Đông Anh, Phạm Tuấn Long, Nguyễn Thị Thanh Vi Chống trùng lặp địa danh hệ thống khai thác thông tin bất động sản Nguyễn Trung Kiên, Đinh Anh Tuấn Xây dựng JOO framework chuẩn hóa mơ hình lập trình ứng dụng web hệ thống phân tán cỡ lớn Bùi Kim Dung, Bùi Anh Dũng, Bùi Trung Hiếu 14 Truyện tranh di động Nguyễn Thị Thuyên 20 Hệ thống tổng hợp tiếng nói tiếng Việt chất lượng cao Nguyễn Trọng Hiếu, Lê Quang Thắng, Lê Anh Tú, Đỗ Văn Thảo, Nguyễn Hữu Thuận 24 Giải pháp ngữ nghĩa – Tích hợp liệu, gợi ý tìm kiếm thơng tin cho hệ thống hướng dẫn du lịch thông minh Phan Thanh Hiền, Nguyễn Anh Đức 32 Tích hợp nội dung web phổ dụng Phan Văn Hùng, Vũ Mạnh Hùng, Trần Đắc Long 41 Các vấn đề an toàn bảo mật cho điện thoại di động, phần mềm bảo mật Android Trần Ngọc Khải 46 Botnet Tracking Framework – Framework hỗ trợ theo dõi giám sát mạng botnet Triệu Minh Tuân 51 10 RSED: Môi Trường Giả Lập Mạng Giống Thực Tế Phục Vụ Cho Nghiên Cứu Tấn Công Từ Chối Dịch Vụ (DDoS) Trương Thảo Nguyên 56 11 Ứng dụng công nghệ GPS, GIS xây dựng hệ thống theo dõi quản lý xe buýt Hà Nội 61 Vũ Ngọc Thành 12 Xây dựng hệ mờ nhận dạng biển số xe Đoàn Hồng Quân 66 13 Các gợi ý cá nhân hóa gửi tự động cho người dùng di động Hoàng Minh Thuấn, Tạ Thị Quỳnh Lan 74 14 Hệ thống lưu trữ chia sẻ liệu Lindax Nguyễn Đức Huy, Nguyễn Thị Khen, Phạm Việt Linh 79 15 Chương trình tạo video 3D từ mơ hình 3D sử dụng cơng nghệ GPGPU Trịnh Quốc Việt, Nguyễn Hữu Dũng 84 16 Mơ hình dịch vụ điện toán đám mây Bkloud Lê Quang Hiếu, Hoàng Quốc Nam, Lưu Thị Thùy Nhung 88 17 Hệ điều hành hiệu cao HPOS Cao Minh Quỳnh, Nguyễn Đắc Minh, Ngô Văn Vĩ 94 18 Giải thuật di truyền lai giải toán phủ đỉnh Nguyễn Hữu Phước 100 19 Hệ thống nhận diện Virus máy tính theo hành vi Trần Minh Quảng 105 20 Phân cụm tài liệu sử dụng độ tương đồng dựa sở cụm từ Nguyễn Kim Thuật, Cao Mạnh Đạt 109 21 Hệ thống trích rút thơng tin cho việc xây dựng sở tri thức từ văn tiếng Việt Nguyễn Hữu Thiện, Nguyễn Quang Vinh, Nguyễn Thị Minh Ngọc 114 22 Phát triển tảng NS2 nhằm phục vụ mô giao thức định tuyến mạng cảm biến không dây Bùi Tiến Quân, Nguyễn Trung Hiếu 119 23 Xây dựng thư viện khung song song liệu cho hệ thống nhiều xử lí đồ họa Nguyễn Minh Tháp, Ngơ Huy Hồng 124 24 Hệ thống giám sát lượng tịa nhà sử dụng cơng-tơ điện tử hệ thống truyền tin đường điện lưới 129 Nguyễn Trọng Nhật Quang 25 Nâng cao chất lượng tín hiệu tiếng nói Nguyễn Đức Hải 134 26 Xây dựng hệ thống bán hàng tương tác dựa tảng mạng cảm biến không dây Phạm Đức Anh, Trương Quốc Tú 139 27 Nghiên cứu xây dựng mơ hình mạng Network-on-Chip Tạ Thi Hà Thư 144 28 Nghiên cứu mạng cảm biến không dây ứng dụng hệ thống xếp chỗ tự động Trần Duy Phương 150 29 Giải pháp camera giám sát giao thông tảng mạng 3G Trịnh Thị Mây 156 30 Hệ thống định vị - hỗ trợ quản lý học sinh tiểu học tảng GPS-GSM/GPRS Đinh Thanh Tùng, Đặng Thanh Huyền 161 31 Hệ thống định vị qua bước chân người mơi trường khơng có GPS với chi phí thấp Nguyễn Đình Thuận 166 32 Phát triển hệ thống dẫn đường giọng nói giám sát từ xa camera sử dụng công nghệ 3G tảng kit friendlyarm Nguyễn Thành Luân 171 33 Xây dựng tảng phát triển ứng dụng quảng cáo dựa công nghệ Led 3d Nguyễn Thị Phương Ly, Mai Xuân Chiến 176 34 Ứng dụng xác thực khuôn mặt kiểm tra hộ chiếu Nguyễn Viết Thành Trung 181 35 Hệ thống thu thập tài liệu theo chủ đề cho tiếng Việt Nguyễn Xuân Hòa 186 36 Xây dựng thiết bị tích hợp dịch vụ phục vụ cho hệ thống mạng doanh nghiệp vừa nhỏ Bạch Hà Duy, Hoàng Xuân Nam 192 37 Phát theo vết đối tượng chuyển động Phạm Đức Long, Trương Thị Tâm 197 38 Hệ thống xác thực khuôn mặt hỗ trợ quản lý thẻ thư viện Bùi Thị Minh Yến 202 39 Xây dựng ứng dụng tổng đài nội thoại hội nghị VOIP Asterisk Nguyễn Văn Nhẫn, Nguyễn Trung Hiếu 207 40 Bộ thu thập trang Web ẩn theo chủ đề Vũ Thành Đô, Bùi Anh Đức 212 41 Kỹ thuật định vị dựa wifi ứng dụng Chu Bảo Trung, Phạm Hữu Hoàng 218 42 Nghiên cứu, đánh giá cải tiến hiệu sử dụng lượng hiệu suất truyền gói tin giao thức định tuyến mạng cảm biến không dây Nguyễn Sơn Thủy, Nguyễn Đình Minh 223 43 Nghiên cứu lý thuyết xây dựng hệ thống phát xâm nhập Nguyễn Xuân Quang 228 ExpertRank: Thuật toán lặp đánh giá chuyên môn người dùng chất lượng câu trả lời hệ thống hỏi đáp cỡ lớn Nguyễn Văn Đông Anh, Phạm Tuấn Long, Nguyễn Thị Thanh Vi  Q&A, đời phát triển mạnh với mục tiêu hỗ trợ tạo câu trả lời vừa cập nhật vừa sát yêu cầu câu hỏi; đồng thời lưu trữ tri thức định dạng mà dễ tìm kiếm lại Một số hệ thống hỏi đáp tiếng giới phải kể đến Yahoo answers, Google Confucius, Google answers, Google AardVark, Quora, Baidu Zhidao,… Thậm chí tảng web mã nguồn mở có tên Question2Answer tạo để hỗ trợ việc xây dựng trang web Hỏi đáp; giúp tạo 1000 trang web Q&A lĩnh vực khác Thực tế chứng minh trang web Q&A thành công câu hỏi phải nhận câu trả lời vừa nhanh vừa có chất lượng cao Để làm điều đó, chúng cần tạo động lực cho người dùng trả lời câu hỏi khơng nhanh chóng mà cịn cẩn thận Google Confucius thống kê loại động lực trang Q&A phổ biến[3], có động lực giá trị ảo việc kết bạn trực tuyến, thể thân, giá trị vật chất mà cụ thể tiền bạc Cả hai loại động lực cần hệ thống tự động đánh giá chuyên môn người dùng chất lượng câu trả lời cách công Với động lực tiền bạc, việc đánh giá chuyên môn người dùng chất lượng câu trả lời để tính số tiền cần phải trả cho câu trả lời Với động lực giá trị ảo việc đánh giá chun mơn khách quan kèm với hồ sơ cá nhân cơng bố rộng rãi cộng đồng kích thích người dùng đóng góp nhiều cho hệ thống Tóm tắt - Nghiên cứu trình bày thuật tốn lặp đánh giá chất lượng câu trả lời trình độ chuyên môn người dùng lĩnh vực hệ thống hỏi trả lời cỡ lớn, mà cụ thể mạng cộng đồng chia sẻ tri thức Việt Nam BkProfile Việc đánh giá chất lượng câu trả lời giúp người dùng chọn câu trả lời đáng tin cậy cho câu hỏi, việc đánh giá chuyên môn người dùng giúp họ chứng minh kiến thức chun mơn hồ sơ nghề nghiệp họ hệ thống Hai việc đánh giá động lực quan trọng thúc đẩy hoạt động hệ thống Hỏi & Đáp có liên quan chặt chẽ với nhau: câu trả lời chất lượng cao đóng góp nhiều cho hồ sơ nghề nghiệp (profile) người trả lời ngược lại, câu trả lời từ người dùng có hồ sơ nghề nghiệp tốt đáng tin cậy Chúng tơi dựa thuật tốn phân loại trang web máy tìm kiếm Google có tên PageRank, mơ hình chuỗi Markov để chuyển tốn thành mơ hình xác suất, từ xây dựng thuật tốn lặp đánh giá lúc hai đại lượng Thuật toán chúng tơi thiết kế mơ hình Map-Reduce nên áp dụng cho hệ thống phân tán cỡ lớn Chúng tơi thử nghiệm hệ thống mã nguồn mở có tên Hadoop Map Reduce triển khai chạy ổn định ứng dụng web BkProfile địa http://www.bkprofile.com Các kết thuật tốn đóng gói tham số tin cậy sử dụng cho hệ thống đánh giá ứng dụng chia sẻ tri thức cỡ lớn khác 1.2 Đánh giá chuyên môn chuyên gia tiến cử sử dụng để đánh giá chất lượng câu trả lời Việc đánh giá chuyên mơn người thực trực tiếp cách đánh giá chất lượng công việc người hay gián tiếp tiến cử chuyên gia khác (rất phổ biến nước phương Tây Mỹ, Canada, ) Trong hệ thống Q&A việc đánh giá chất lượng câu trả lời cách trực tiếp thực phương pháp xử lý ngôn ngữ tự nhiên Tuy nhiên, cách địi hỏi biện pháp phức tạp để đạt độ xác cao Với việc tiến cử chun gia thơng thường ẩn chứa hoạt động chuyên gia hệ thống hỏi đáp Ví dụ chuyên gia Alice bình chọn cho câu trả lời chuyên gia Bob việc hiểu ngầm cần tiến cử người lĩnh vực câu trả lời có xác suất đó, Alice tiến cử Bob Sau có chất lượng chun mơn người dùng, dùng để đánh giá chất lượng câu trả lời Một câu trả lời coi tốt viết bình chọn chuyên gia có thứ hạng cao hệ thống Từ khóa - Iterative method, Markov chain, MapReduce, PageRank GIỚI THIỆU 1.1 Việc xếp hạng chuyên gia đánh giá chất lượng câu trả lời hệ thống hỏi đáp Trong năm gần đây, hệ thống hỏi đáp, viết tắt  Cơng trình thực bảo trợ nhóm BKProfile, http://www.bkprofile.com, hướng dẫn PGS TS Huỳnh Quyết Thắng, Ths Lê Quốc Nguyễn Văn Đông Anh, sinh viên lớp Công nghệ phần mềm, khóa 51, Viện Cơng nghệ thơng tin Truyền thông, trường Đại học Bách Khoa Hà Nội (điện thoại: 84-982-933-787, e-mail: anhnv@bkprofile.com) Phạm Tuấn Long, sinh viên lớp Cơng nghệ phần mềm, khóa 51, Viện Cơng nghệ thông tin Truyền thông, trường Đại học Bách Khoa Hà Nội (điện thoại: 84-972-889-760, e-mail: longpham@bkprofile.com) Nguyễn Thị Thanh Vi, sinh viên lớp Cơng nghệ phần mềm, khóa 52, Viện Công nghệ thông tin Truyền thông, trường Đại học Bách Khoa Hà Nội (điện thoại: 84-1688-329-541, e-mail: vinguyen@bkprofile.com) © Viện Công nghệ thông tin Truyền thông, trường Đại học Bách Khoa Hà Nội 1.3 ExpertRank Chúng tơi đưa khái niệm có tên ExpertRank để đánh giá chuyên môn người dùng ExpertRank đánh giá dựa tiến cử người dùng khác hệ thống Người có ExpertRank cao giá trị tiến cử họ lớn Đặc biệt, giả sử có loại tiến cử hai người có ExpertRank, người tiến cử người, người tiến cử 20 người chất lượng tiến cử người thứ cao CÁC NGHIÊN CỨU LIÊN QUAN Trong báo [4], AardVark thực việc xếp hạng kết tìm kiếm người sau nhận truy vấn người dùng Cơng việc tính tốn thơng thường phải khoảng thời gian định, với trường hợp AardVark vài phút để tìm người phù hợp gửi câu hỏi Google Confucius [3]thì xếp hạng người dùng bước đánh mục sử dụng thuật toán HITS [2] với đầu vào quan hệ người hỏi & người trả lời Lập luận Google số lượng bình chọn người dùng cho câu trả lời không đủ để tin cậy Hơn nữa, việc tính tốn đẩy cho q trình đánh mục làm thời gian truy vấn giảm xuống chưa đến giây Tuy nhiên, hệ thống khác Quora số lượng bình chọn người dùng lớn Lý Quora xây dựng hệ thống Q&A theo mơ hình mạng cộng đồng mà đó, người dùng trả lời bày tỏ quan điểm việc bình chọn cho câu trả lời mà họ thấy Một hệ thống khác liên quan đến việc đánh giá chất lượng chuyên gia thông qua tiến cử hệ thống đánh giá chất lượng viết khoa học thông qua danh mục tài liệu tham khảo [7] phương pháp thường không nhắm tới hệ thống xử lý liệu lớn Bài báo tập trung xây dựng thuật toán đánh giá chất lượng người dùng cho hệ thống hỏi đáp dạng cộng đồng cỡ lớn, tức hoạt động tương tác người dùng với hệ thống đủ nhiều để mang ý nghĩa Việc đánh mục cần thực hệ thống khơng tự động điều hướng câu hỏi mà gợi ý cho người dùng tự chọn chuyên gia, thời gian gợi ý lâu 1.4 PageRank mối liên hệ với ExpertRank PageRank [1] tên thuật toán tiếng ứng dụng máy tìm kiếm Google để xếp kết tìm kiếm khơng theo mật độ từ khóa phương pháp tìm kiếm văn thơng thường mà cịn dựa độ tin cậy trang web Độ tin cậy tính gần việc tiến cử trang web với thông qua đường liên kết chúng Ví dụ trang web BKProfile.com có chứa liên kết tới website Viện Công nghệ thông tin & Truyền thơng có nghĩa BKProfile tin tưởng trang web trang web có thêm điểm cho độ tin cậy Nếu ta nhìn trang web chuyên gia, liên kết trang web giống việc tiến cử chuyên gia hai hệ thống tương tự Hơn hệ thống hỏi đáp hệ thống tìm kiếm hướng tới tốn với liệu cỡ lớn Điều gợi ý ta áp dụng phương pháp tính tốn tầm quan trang web mà PageRank sử dụng để tính tốn trình độ chun mơn chun gia Tuy nhiên, có số vấn đề tiềm mà ExpertRank cần phải quan tâm áp dụng tư tưởng thuật tốn PageRank Đó cấu trúc mạng đầu vào ExpertRank khác UserRank; độ thưa mạng quy mô mạng vấn đề tiềm tàng, đặc biệt PageRank sử dụng quy luật xác suất, vốn áp dụng với số lớn Để khắc phục điều này, bên cạnh so sánh với PageRank, chúng tơi mơ hình hóa ExpertRank theo chuỗi Markov để phân tích tính đắn Tóm lại, phần báo, chúng tơi trình bày ExpertRank phiên mở rộng PageRank cho việc đánh giá chuyên môn người dùng Bên cạnh việc bám sát chi tiết PageRank để làm cho tính đắn, hiệu chỉnh bước cho phù hợp với điều kiện mới, kết hợp việc phân tích tính hợp lý ExpertRank rõ tính đắn dựa mơ hình chuỗi Markov Chúng áp dụng ExpertRank để thiết kế giải pháp đánh giá chất lượng chuyên gia dịch vụ web chia sẻ tri thức Việt Nam BKProfile, sử dụng mơ hình lập trình MapReduce, cài đặt tảng mã nguồn mở Hadoop cho phép phân tán hệ thống tính tốn để xử lý liệu lớn Thành cơng bước đầu BKProfile minh chứng cho tính hiệu ExpertRank XẾP HẠNG CHUYÊN MÔN NGƯỜI DÙNG 3.1 Đồ thị tiến cử chuyên gia Như mô tả, hệ thống Q&A, chuyên gia tiến cử ngầm hoạt động họ hệ thống, tiêu biểu lý sau để người dùng A tiến cử người dùng B: - B trả lời câu hỏi A - A bình chọn cho câu trả lời B - A tiến cử B trực tiếp chuyên gia lĩnh vực - A mời B vào hệ thống chun mơn B có liên quan đến lĩnh vực xét - A B có chung số thuộc tính có liên quan đến chun mơn chung hai người lớp, trường, nhóm dự án,… Bằng quan hệ ta xây dựng mạng lưới quan hệ người dùng với nhau, người tiến cử người với trọng số đó, tùy thuộc vào lý tiến cử Nếu coi chuyên gia nốt mạng, việc tiến cử người đến người cung có hướng tồn hệ thống giống đồ thị có hướng có trọng số Hình Trong lần lặp đầu, chun gia có chun mơn nghịch đảo tổng số chuyên gia Hình bên phải kết lần lặp đầu Hình Đồ thị tiến cử nhóm gồm chuyên gia với hai loại tiến cử: trả lời (A) bình chọn (V) 3.2 Cơng thức tính ExpertRank dạng đơn giản Giả sử u chuyên gia hệ thống Q&A Gọi Fu tập hợp chứa chuyên gia mà u tiến cử, Bu tập hợp chứa chuyên gia tiến cử u Gọi f(u,v) đại lượng đo mức độ tiến cử chuyên gia u với chuyên gia v mà Hình Dữ liệu đầu vào lần lặp thứ hai kết lần lặp thứ Trong ví dụ trên, sau lần lặp thứ hai, ta thấy chuyên gia số có điểm số cao chun gia cịn lại chun gia số trả lời nhiều câu hỏi bình chọn chuyên gia có chất lượng  f (u, v)  f(u,v) đóng vai trị hàm vFu phân phối chuyên môn chuyên gia u tới chuyên gia v Đặt R(u) ExpertRank u,  R(u)  , 3.4 Mơ hình khách hàng xin tư vấn ngẫu nhiên Thuật tốn mơ tả cách định tính mơ hình hóa cách tốn học dạng xác suất mà khách hàng xin tư vấn ngẫu nhiên viếng thăm chuyên gia hệ thống hỏi đáp để hỏi lĩnh vực Giả sử khách hàng xin tư vấn ngẫu nhiên cần tư vấn lĩnh vực đó, Java chẳng hạn, người có danh sách chuyên gia lĩnh vực Java hệ thống Người nhặt ngẫu nhiên tên bắt đầu xin tư vấn với chuyên gia tương ứng, ví dụ Alice Sau tham khảo ý kiến Alice, người muốn xin thêm tư vấn nên nhờ Alice giới thiệu cho mình chuyên gia khác mà Alice tin tưởng Alice vào lịch sử làm việc hệ thống để giới thiệu số chuyên gia Căn vào mức độ giới thiệu mà người xin tư vấn có xác suất viếng thăm chuyên gia khác Giả sử khách hàng chọn thăm Bob sau Alice Khi đó, q trình làm việc với Bob hoàn toàn tương tự làm việc với Alice: kết thúc phiên làm việc với Bob, khách hàng lại yêu cầu Bob giới thiệu thêm chuyên gia để xin tư vấn tiếp Lưu ý tới Bob giả sử khách hàng quan tâm tới lời khuyên Bob mà không quan tâm tới lời khuyên mà trước Alice khuyên, điều quan trọng cho việc kết nối mơ hình với chuỗi Markov trình bày phần sau Sau số lần đủ lớn di chuyển người dùng khơng cịn nhớ bắt đầu đâu xác suất tới thăm chuyên gia ổn định Lúc đó, xác suất khách hàng xin tư vấn tới thăm chuyên gia đại diện cho mức độ tiến cử chuyên gia đó; theo đại diện cho chun mơn chuyên gia u R(u )   R(k ) * f (k , u) (1) kBu 3.3 Sự lan truyền tiến cử thông qua mạng lưới tiến cử Một người có chun mơn cao làm cho chun môn người mà người tiến cử tăng lên, trình tiếp tục cho người khác mà tiến cử người người tiến cử Hiện tượng gọi lan truyền tiến cử thông qua mạng lưới tiến cử Sau q trình lặp đó, thuật tốn hội tụ trạng thái ổn định mà giá trị nốt mạng ExpertRank Các hình vẽ biểu diễn hai trình lặp đồ thị tiến cử chun gia mơ tả hình mà đó: số dấu ngoặc đơn ExpertRank nốt tương ứng lần lặp thời; mũi tên có biểu thức mơ tả việc truyền ExpertRank mạng, biểu thức có hai thừa số: thừa số thứ ExpertRank nốt tương ứng, thừa số thứ hai đo mức độ tin cậy nốt tiến cử với nốt tiến cử; mức độ tin cậy phụ thuộc vào lý tiến cử : trả lời hay bình chọn; tỷ lệ trọng số tầm quan trọng chúng hình vẽ 2:1 3.5 Sự tương ứng với chuỗi Markov khả hội tụ Trong mô hình trên, coi chuyên gia trạng thái, việc tiến cử từ chuyên gia đến chuyên gia Khoảng cách(m) 0.9 L1 L2 L3 L4 L5 -39 -45 -41 -45 -41 Trung bình -42.2 1.8 -43 -45 -49 -46 -46 -45.8 2.7 -49 -46 -47 -46 -54 -48.4 3.6 -57 -55 -56 -55 -58 -56.2 Bảng 1: Dữ liệu đo cƣờng độ sóng wifi  Nội suy hàm: Hình 2: Phƣơng pháp đạc tam giác Như mơ tả hình 2, phương pháp thực giống hệ thống GPS Để tính khoảng cách từ thiết bị di động tới AP, ta dựa vào cường độ sóng wifi mà thiết bị di động thu Mối liên hệ cường độ với khoảng cách từ thiết bị tới AP thể qua hàm số Bằng đo đạc thống kê ta suy hàm số 2.2 Thực nghiệm Trong thiết bị di động có khả bắt wifi, card mạng có đo giá trị thể độ mạnh yếu sóng khơng dây thu Đó RSSI (Received Signal Strenght Indication) Trong chuẩn mạng không dây IEEE 802.11, RSSI giá trị tương đối, khơng có đơn vị nằm khoảng từ – 255 (ở số thiết bị khoảng âm) Chuẩn IEEE 802.11 khơng định nghĩa mối quan hệ tương quan RSSI đơn vị đo lường cường độ khác mW hay dBm, mà tương quan nhà sản xuất phần cứng định nghĩa Do với phần cứng khác RSSI đo vị trí khác Pha 1: Nội suy hàm liên hệ Trong pha này, tiến hành đo đạc để suy hàm liên hệ cường độ sóng khoảng cách từ thiết bị di động tới AP  Thiết bị: + AP loại D-LINK 108G + iPhone 4, nhớ 32GB  Triển khai đo đạc: + AP đặt vị trí cố định + Bắt đầu từ 0.9m, 0.9m lại dùng điện thoại iPhone đo cường độ sóng Tại điểm đo lần Bảng phần liệu thu Cường độ sóng biểu diễn dạng số âm + Đo tới điểm đo cách AP ~ 30m dừng Hình 3: Nội suy hàm số matlab + Nhập liệu đo vào matlab (hình 3), thu hàm liên hệ D  0.00057670  RSSI  0.07379443  RSSI  3.36703189  RSSI  52.81736996 (1) Pha 2: Đạc tam giác  Phương pháp: + Chia khu vực định vị thành lưới kích thước 1m x 1m + Xét ô lưới, khoảng cách từ tâm ô tới AP d1, d2, d3 + Khoảng cách thu sau áp dụng (1) r1, r2, r3 + Tìm lưới có giá trị biểu thức sau nhỏ nhất:   (r1  d1 )2  (r2  d2 )2  (r3  d3 )2 (2) + Trung bình theo trọng số toạ độ định vị (trọng số nghịch đảo ∆) Kết quả: Toạ độ thật Toạ độ định vị ∆x ∆y (1;1) (3.5; 0.5) 2.5 0.5 (6;1) (6.5; 0.5) 0.5 0.5 (13.5;1) (20.5; 1.49) 0.49 (11.4; 6.6) (6.5; 0.5) 4.9 6.1 (6; 12.5) (14.5; 12.5) 8.5 (1;11.3) (0.5; 11.5) 0.5 0.2 (6;7) (3.17; 2.16) 2.83 4.84 (18.6; 6.6) (20.5; 11.5) 1.9 4.9 (18.6; 5.4) (20.5;1.4) 1.9 (18.6; 1) (20.5;1.4) 1.9 0.4 Đơn vị: mét Bảng 2: Kết định vị đạc tam giác Từ kết suy ra: 219 độ, dưới90 độ, phải 180 độ,  270 độ), hướng đo lần sau lấy trung bình  Nhập toạ độ điểm lấy mẫu mẫu vào sở liệu  Bảng ví dụ mẫu đo (mẫu gồm cường độ sóng đo từ AP) Toạ Hướng AP1 AP2 AP3 độ(m) 45 75 65 0  x  3.243(m) ;  y  2.193(m) ;    x   y  3.915(m) 2 2.3 Nhận xét Phương pháp “đạc tam giác” có sai số trung bình 3.91 m, nhiên có trường hợp sai số xấp xỉ 10m Đối với định vị nhà sai số lớn Tuy nhiên ưu điểm phương pháp là:  Cách thực đơn giản, chi phí nhỏ  Chỉ cần đo đạc lần để xác định hàm liên hệ (3;0) 74.3 74 180 45 76.3 66.3 45.6 74.6 62 59 75.6 70.6 90 55.6 77.6 73 180 56.6 74.6 64.6 270 3.1 Phương pháp Phương pháp đối sánh mẫu dựa vào nhận xét sau: “Hai vị trí khác có cường độ sóng tới AP khác nhau, AP đó, số lượng AP>=3” Bởi cường độ sóng thu đặc trưng cho khoảng cách từ AP tới thiết bị di động, hay nói cách khác, điểm có cường độ sóng tới AP điểm cách AP đó, hay nằm đường trịn tâm AP Vậy mà, >= đường trịn nhiều giao điểm, nên, khơng thể có điểm vị trí khác mà lại nằm >= đường tròn khác Áp dụng nhận xét trên, phương pháp đối sánh mẫu thực cách đo “mẫu” điểm mốc định sẵn, định vị, lấy cường độ sóng thu so sánh với “mẫu”, điểm mốc có “mẫu” khớp vị trí thiết bị di động 45 0 PHƢƠNG PHÁP ĐỐI SÁNH MẪU[7] 90 270 (0;0) 57 70 67.3 Bảng 3: “mẫu” cƣờng độ sóng Pha 2: Đối sánh mẫu (matching) Khi có liệu mẫu sở liệu ta tiến hành so sánh sóng thu với mẫu Cụ thể bước đây:  Lấy cường độ sóng thiết bị di động nhận từ AP, ss1, ss2, ss3  Với mẫu i, tính biểu thức đây:  ss i  SS1i  ss1  SS2 i  ss2  SS3 i  ss3 (3)   Tìm  ss i có giá trị nhỏ 3.2 Thực nghiệm Về mặt thiết bị phương pháp dùng thiết bị phương pháp đạc tam giác Khi thực phương pháp “đối sánh mẫu” trải qua pha Pha 1: Đào tạo (training) Hình đồ khu vực thực nghiệm viện bảo tàng Lịch Sử Việt Nam Những vị trí đánh dấu ngơi mầu đỏ vị trí AP, điểm đánh dấu hình thoi mầu xanh ví trí vật chọn thử nghiệm, điểm thực lấy mẫu   Nếu min(  ss i )   (  =10) vị trí thiết bị di động vị trí điểm mốc thứ i Cịn ngược lại khơng định vị thiết bị di động Kết quả: Toạ độ thật (1;1) (6;1) (13.5;1) (11.4; 6.6) (6; 12.5) (1;11.3) (6;7) (18.6; 6.6) (18.6; 5.4) (18.6; 1) Toạ độ định vị (1; 1) Không xác định (13.5; 1) Không xác định Không xác định (1; 11.3) Không xác định (18.6; 6.6) (18.6;5.4) (18.6;1) ∆x 0 0 0 ∆y 0 0 0 Đơn vị: mét Bảng 4: Kết định vị đối sánh mẫu Từ bảng suy  x ,  y Hình 4: Bản đồ lấy “mẫu”  Đo xác định toạ độ điểm lấy mẫu  Tại điểm lấy mẫu, đo cường độ sóng theo hướng (trái   3.3 Nhận xét Phương pháp đối sánh mẫu, với điểm gần với mẫu cho kết xác, nhiên với vị trí khác không 220 Sử dụng hai kỹ thuật “đạc tam giác” “đối sánh mẫu” bổ trợ cho nhau, xây dựng hệ thống có kiến trúc mơ tả hình Hệ thống gồm có hai server client Hai server viết ngôn ngữ PHP, chạy hệ điều hành MAC OS Snow Leopard 10.6.4, client iPhone4 Luồng xử lý hệ thống thực theo số thứ tự đánh hình đưa kết định vị Vì sai số phương pháp khơng thể xác định  Ưu điểm: + độ xác thiết bị di động gần điểm mốc gần tuyệt đối + phương pháp đơn giản, chi phí thấp  Nhược điểm: + khơng thể định vị thiết bị di động xa mẫu + muốn tăng khả định vị, cần phải tăng số lượng mẫu + có thay đổi trí phịng, xây dựng u cầu đo đạc lại mẫu HỆ THỐNG HƢỚNG DẪN THAM QUAN BẢO TÀNG Server định vị (các)số hiệu vật (8) x Xử lý Thơng tin cường độ sóng (4) (các)số hiệu vật (9) Giao diện ngƣời dùng Xử lý CSDL nội dung (các) số hiệu vật (10) Dữ liệu vật (12) (các)số hiệu vật (11) Tín hiệu kích hoạt (2) Server nội dung Dữ liệu vật (13) Thông tin cường độ sóng(3) x x Dữ liệu vật (14) Định vị Phía Client Thơng tin điều khiển (1) x Thơng tin cường độ sóng(5) Toạ độ định vị (6) 4.2 Kỹ thuật định vị Hai kỹ thuật định vị dựa vào sóng wifi có ưu nhược điểm khác nhau, mà chúng bổ trợ cho hệ thống hướng dẫn tham quan bảo tàng chúng tơi  Kỹ thuật “đạc tam giác”: có sai số lớn (từ đến 10m), khó dùng để phân biệt vật trình khách tham quan bảo tàng Tuy nhiên nhược điểm khắc phục phương pháp “đối sánh mẫu”, phương pháp đặc biệt hữu ích việc xác định vật mà khách tham quan  Kỹ thuật “đối sánh mẫu”: có sai số nhỏ thiết bị di động gần điểm mốc (các vật chọn làm điểm mốc) Tuy nhiên xa điểm mốc chút, phương pháp khơng đưa kết định vị Tuy nhiên nhược điểm giảm bớt phương pháp “đạc tam giác” Như vậy, trình định vị sau: + Khi thiết bị di động gần điểm mốc, “đối sánh mẫu” định vị được, lúc ta dùng kết phương pháp làm vị trí định vị +Khi thiết bị di động không gần điểm mốc nào, “đối sánh mẫu” không đưa vị trí thiết bị di động Thì lúc ta dùng phương pháp “đạc tam giác”để định vị Kết có sai số lớn để dẫn đường khách tham quan CSDL vị trí Toạ độ định vị (7) 4.1 Mục đích Bảo tàng Lịch sử Việt Nam nói riêng bảo tàng khác nói chung, có nhiều thơng tin vật Họ khó trưng bày tất thông tin vật Vì có số bảo tàng có hướng dẫn viên, giúp khách tham quan tiết kiệm thời gian mà có thơng tin đầy đủ Tuy nhiên có bảo tàng khơng có hướng dẫn viên bảo tàng Lịch sử Việt Nam Với mục đích thay người hướng dẫn viên, giúp khách tham quan có thơng tin đầy đủ phù hợp với mong muốn họ, đồng thời gợi ý cho họ lộ trình tham quan bảo tàng, nghĩ đến việc áp dụng kỹ thuật định vị tìm hiểu để xây dựng hệ thống hướng dẫn tham quan bảo tàng Đo sóng Xử lý x Hình 5: Kiến trúc hệ thống hƣớng dẫn tham quan bảo tàng CÁC CÔNG VIỆC LIÊN QUAN Trong nghiên cứu sử dụng kết nghiên cứu thuộc phòng nghiên cứu “định vị dẫn đường vệ tinh”-SNAP thuộc trường đại học New South Wales, Úc Hiện họ tiến hành cải tiến hai kỹ thuật lên nhiều nhằm khắc phục nhược điểm phương pháp KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN Kết luận: Hai kỹ thuật “đạc tam giác” “đối sánh mẫu” có ưu điểm nhược điểm riêng, với mục tiêu xây dựng hệ 4.3 Kiến trúc hệ thống 221 thống hướng dẫn tham quan bảo tàng hai phương pháp bổ trợ tốt cho Sự thành công việc triển khai hệ thống bước khởi đầu cho việc áp dụng kỹ thuật định vị sóng wifi vào ứng dụng thực tế Với lợi chi phí đầu tư, phương pháp lựa chọn hàng đầu cho “dịch vụ dựa vị trí”có phạm vi hoạt động nhỏ Hƣớng phát triển: Hướng phát triển mà ta nghĩ đến cải tiến khắc phục nhược điểm hai kỹ thuật trên:  Phương pháp “đạc tam giác”: cách tính tốn ảnh hưởng vật cản lên cường độ sóng, ta tăng độ xác lên  Phương pháp “đối sánh mẫu”: nhược điểm phương pháp việc phải đo đạc nhiều, ta tìm cách giảm số điểm phải đo đạc, thực tế phịng nghiên cứu SNAP họ nghiên cứu phương pháp nội suy cường độ sóng điểm chưa đo từ điểm đo, hướng để cải tiến phương pháp Ngoài việc cải tiến kỹ thuật định vị, ta cịn cải tiến theo cách kết hợp thơng tin khác, ngồi thơng tin vị trí, là: hồ sơ người sử dụng, phần cứng thiết bị di động, cách ta cung cấp dịch vụ thông tin linh hoạt hơn, đưa thơng tin thích hợp với người sử dụng LỜI TRI ÂN Trong suốt trình thực nghiên cứu tốt nghiệp chúng em nhận hướng dẫn tận tình TS Vũ Tuyết Trinh, chúng em muốn dành lời cảm ơn chân thành sâu sắc tới cô Tiếp theo chúng em muốn gửi lời cảm ơn chân thành tới cán bộ, nhân viên viện bảo tàng Lịch Sử Việt Nam, người tạo điều kiện thuận lợi giúp đỡ chúng em trình thử nghiệm, xây dựng hệ thống TÀI LIỆU THAM KHẢO [1] [2] [3] [4] [5] [6] [7] “Context-aware mobile and ubiquitous computing for enhanced usability: adaptive technologies and applications”, Dragan Stojanovic, University of Nis, Serbia, Information Science Reference, 2009 “Location based services: fundamentals and operation”, Axel Küpper, Ludwig Maximilian University Munich, Germany, John Wiley & Sons Ltd, 2005 “Mobile Location Services: The Definitive Guide”, Andrew Jagoe, Prentice Hall PTR, 2002 “Location-based services”, Jochen Schiller & Agne`s Voisard, Morgan Kaufman Publishers, 2004 “An indoors wireless positioning system based on wireless local area network infrastructure”, Y.Wang, X Jia, H.K.Lee, G.Y.Li, presented at SatNav 2003 “Two new algorithms for indoor wireless positioning system (WPS)”, Y Wang, X.Jia, Chris Rizos, School of Surveying and Spatial Information Systems, University of New South Wales, Sydney, Australia, 2004 “A new method for yielding a database of location fingerprints in WLAN”, Binghao Li, Y.Wang, H.K.Lee, Andrew Dempster, Chris Rizos, SNAP, University of New South Wales, 2005 222 Nghiên cứu, đánh giá cải tiến hiệu sử dụng lượng hiệu suất truyền gói tin giao thức định tuyến mạng cảm biến không dây Nguyễn Sơn Thủy, Nguyễn Đình Minh  biến khơng dây tồn vấn đề cần phải khắc phục : Tóm tắt — Ngày nay, ứng dụng mạng cảm biến không dây (WSNs) sử dụng rộng rãi nhiều lĩnh vực công nghiệp, quân sự, môi trường, y tế, nhà thông minh hay giao thông vận tải vv…[1] Tuy nhiên WSNs, nút mạng bị giới hạn khả truyền phát tín hiệu, khả tính tốn, nhớ hạn chế nguồn lượng cung cấp cho nút mạng có hạn[2] Và giao thức định tuyến WSNs có vai trị quan trọng ảnh hưởng tới chât lượng mạng lượng nút mạng Trong báo chúng tơi nghiên cứu phân tích thuật tốn định tuyến cho mạng cảm biến khơng dây Sau tiến hành cài đặt mơ số thuật toán định tuyến : Flooding, DSR, RIP, GF… để đánh giá hiệu thuật tốn với tiêu chí tính tin cậy, độ tiêu thụ lượng hiệu suất truyền gói tin Sau chúng tơi đề xuất số cải tiến cho giao thức Phần mềm mô WSNET WSNETStudio sử dụng để tiến hành cài đặt, mơ thuật tốn  Đảm bảo độ tin cậy q trình truyền thơng tin đây, phương tiện truyền tin sóng radio dễ bị ảnh hưởng môi trường xung quanh  Mơ hình mạng thay đổi nhiều theo thời gian thêm mới, thay hỏng hóc nút mạng  Mơ hình mạng phức tạp nên cần có phương pháp định tuyến (routing protocol) phù hợp để gói tin đến đích với quãng đường thời gian cho phép Từ khóa — Routing protocol, Wireless Sensor Network (WSN) – để tiếng Việt GIỚI THIỆU Mạng cảm biến không dây cấu tạo nhiều thiết bị có kích thước nhỏ, chúng gọi nút mạng Mỗi nút mạng thường có phận cảm biến, xử lí, truyền tín hiệu, định vị nguồn cung cấp lượng thường pin [3][4] Ngày khả triển khai dễ dàng giá thành thiết bị ngày rẻ nên ứng dụng mạng cảm biến không dây sử dụng ngày rỗng rãi nhiều lĩnh vực quân sự, công nghiệp, y tế sống sinh hoạt hàng ngày.Ví dụ : Hệ thống đo lường điều khiển số nhà máy,hệ thống quan trắc môi trường, hệ thống nhà thông minh,…Những hệ thống đem lại hiệu to lớn, giúp tăng suất lao động cải thiện chất lượng sống người Vì mạng cảm biến khơng dây đánh giá công nghệ giúp thay đổi sống người tương lai tới[5] Tuy nhiên, mạng cảm Cơng trình thực hướng dẫn TS Nguyễn Kim Khánh, với giúp đỡ thạc sĩ Phạm Văn Thuận, viện CNTT, Đại học Bách Khoa Hà Nội Nguyễn Sơn Thủy, sinh viên lớp IS1-chương trình Việt Nhật, khóa 51, Viện Công nghệ thông tin Truyền thông, trường Đại học Bách Khoa Hà Nội (điện thoại: 0983 212 885, e-mail: nguyensonthuy@gmail.com) Nguyễn Đình Minh, sinh viên lớp AS1-chương trình Việt Nhật, khóa 51, Viện Cơng nghệ thơng tin Truyền thông, trường Đại học Bách Khoa Hà Nội (điện thoại: 0975 111 688, e-mail: akaryuvn@gmail.com)  Các nút mạng thường máy tính nhúng có giới hạn tài nguyên giới hạn khả tính toán, thường sử dụng nguồn pin nên cần phải thiết kế phương pháp định tuyến đơn giản hiệu đảm bảo đạt mục tiêu tiết kiệm lượng…[6][7][8] Vì việc phát triển, lựa chọn giao thức định tuyến phù hợp cho mạng cảm biến không dây đóng vai trị quan trọng, định chất lượng mạng thời gian hoạt động nút mạng Hiện nghiên cứu giao thức định tuyến mạng cảm biến không dây quan tâm, giới Việt Nam Trong nội dung báo trình bày nghiên cứu, phân tích giao thức định tuyến mạng cảm biến không dây Phần tiến hành cài đặt mô số giao thức định tuyến Flooding,RIP,GF, Gossiping … để đánh giá khả tự cấu hình đồ hình mạng thay đổi, độ tin cậy, lượng tiêu thụ hiệu suất truyền gói tin mạng Sau có kết mô số cải tiến cho giao thức Cuối phần kết luận Hình 1: Cấu tạo mạng cảm biến khơng dây © Viện Công nghệ thông tin Truyền thông, trường Đại học Bách Khoa Hà Nội 223 CÁC GIAO THỨC CHO MẠNG CẢM BIẾN KHÔNG DÂY thức định tuyến GF nút mạng không cần lưu thông tin đường mà gửi gói tin tới nút mạng lân cận thấy nút mạng có vị trí gần nút đích muốn gửi đến Và nút mạng trung gian nhận gói tin chuyển tiếp gói tin dựa vào chế Giao thức GF có khả tự cấu hình sau thời gian định nút mạng gửi gói tin Hello đến nút xung quanh để cập nhật lại thông tin Thông thường mạng cảm biến không dây, giao thức định tuyến thường lựa chọn cho phù hợp với ứng dụng mạng Hiện có nhiều giao thức định tuyến phát triển cho mạng cảm biến không dây Các giao thức định tuyến phân loại sau [9]: Các giao thức định tuyến dựa vị trí ( Location based Protocols ) với giao thức như: MECN, SMECN, GAF, GEAR, Span, TBF, BVGF, GeRaF, GF, GEOStatic Các giao thức định tuyến theo nguyên tắc liệu tập trung (Data-centric Protocols): SPIN, COUGAR , ACQUIRE, EAD Các giao thức định tuyến phân cấp (Hierarchical protocols) : LEACH, PEGASIS, HEED, TEEN, APTEEN Các giao thức định tuyến hướng di động ( Mobility based Protocols ) : SEAD, TTDD, Data MULES, Dynamic Proxy Tree-Base Data Dissemination Các giao thức định tuyến đa hướng (Multipath-based Protocols) : Flooding, Sensor Disjoint Multipath, Braided Multipath Các giao thức định tuyến không đồng (Heterogeneity - based Protocols) : IDSQ, CADR, CHR Các giao thức định tuyến hướng chât lượng dịch vụ (QoS-based protocols ): SAR, SPEED, Energy-aware routing Trong báo này, hướng nghiên cứu tập trung chủ yếu vào số giao thức định tuyến phổ biến có khả đa đường truyền, thiết kế cho mạng không dây nhiều tầng (multi-hop wireless network) , giao thức : Flooding, GF, RIP giao thức DSR 1.Giao thức Flooding : giao thức đơn giản nhất, khơng phụ thuộc vào cấu hình mạng Trong giao thức Flooding, gói tin gửi quảng bá từ nút tới tất nút lân cận tới đích Vì tạo nhiều gói tin dư thừa, chiếm dụng hết băng thông mạng.Flooding thường sử dụng để so sánh, đánh giá hiệu hoạt động giao thức khác mạng cảm biến không dây Hình : Giao thức GF 3.Giao thức định tuyến RIP[11] :RIP giao thức sử dụng mạng Ethernet, đề cử thử nghiệm để từ cải tiến dùng mạng WSN hiệu Đặc điểm giao thức RIP dựa định tuyến theo véctơ khoảng cách Giao thức thực chế cập nhật định kỳ bảng định tuyến cách gửi nhận thông tin với nút lân cận Việc cập nhật định kỳ giúp trao đổi thông tin cấu trúc mạng thay đổi Khi gói tin cần chuyển tới đích, dựa vào bảng thơng tin định tuyến để chọn nút Ưu điểm giao thức khơng có gói tin liệu dư thừa tới đích Nhược điểm khơng thể dùng để định tuyến cho mạng có đồ hình lớn số hop tối đa RIP 16, thời gian hội tụ (thời gian xây dựng cập nhật bảng định tuyến có thay đổi đồ hình mạng) chậm RIP thích hợp dùng cho mạng nhỏ ổn định Hình : Giao thức RIP 4.Giaothức định tuyến nguồn động ( DSR - Dynamic Source Routing )[12] cho phép tự tổ chức, tự cấu hình mà khơng cần phải có thơng tin sẵn có hạ tầng mạng hay quản trị mạng DSR dựa vào hai chế chế tìm đường chế bảo trì đường Cơ chế dị tìm đường hoạt động chưa thấy đường nhớ nút gửi Vì mà khơng cần gửi gói tin quảng bá hay định kỳ gửi gói tin tìm nút lân cận số giao thức trên, nên tiết kiệm băng thông lượng mạng Mỗi phát sinh chế dị đường, gói tin dò đường đánh số định danh Nhờ số định danh mà nút mạng nhận gói tin dị đường có số định danh trùng với gói tin trước gói tin bị huỷ Ngoài ra, nút nhận gói tin dị đường mà nút nằm danh sách nút trung gian qua gói tin, gói tin bị huỷ Điều Hình : Giao thức Flooding 2.Giao thức định tuyến chuyển tiếp tham lam GF ( Geographic greedy forwarding ) [10] thuật toán định tuyến hiệu dựa vị trí các nút mạng sử dụng mạng ad hoc khơng dây có quy mơ lớn Trong giao 224 tránh việc lặp gói tin Cơ chế bảo trì đường phát đường cũ từ nút nguồn tới nút đích gặp lỗi Nút đích tìm nhớ xem có đường khác khơng, khơng khởi động q trình dị tìm đường Chính giao thức dựa vào chế độ thực thi có u cầu, nên làm giảm đáng kể thơng lượng tồn hệ thống Hình : Đồ hình mạng 20 nút Trong đồ hình có nút mạng (gateway) có nhiệm vụ thu thập, xử lý liệu, nút cảm biến gửi thông tin cho nút gateway Hình : Giao thức DSR B.Kết mơ MƠ PHỎNG VÀ ĐÁNH GIÁ A.Cài đặt, mơ : Để tiến hành phân tích, đánh giá cải tiến giao thức định tuyến, nhóm tác giả sử dụng phần mềm WSNET[13] để tiến hành cài đặt mô giao thức định tuyến WSNET phần mềm mô hướng kiện cho mạng cảm biến không dây Wsnet cung cấp khả mô phỏng: mô nút mạng, mô môi trường xung quanh nút mạng, mô môi trường truyền Kịch thử nghiệm giao thức sau : nút mạng triển khai để giám sát, theo dõi thơng tin tịa nhà Trong mục tiêu giám sát bao gồm :  Thu thập thơng tin nhiệt độ Hình : Biểu đồ thống kê gói tin tầng ứng dụng  Cảm biến hồng ngoại thu thập thông tin số lượng người ra, vào tòa nhà vào phòng tòa nhà Bảng 1: Thống kê gói tin với 50 nút mạng Ở giả thiết hệ thống đặt tầng thư viện Tạ Quang Bửu Thử nghiệm tiến hành vịng ngày ( thời gian mơ phỏng) với hai lần thử nghiệm 20 nút mạng 50 nút mạng Tất thông tin truyền/nhận ghi file log phân tích số liệu Số liệu phân tích hai góc độ: tầng ứng dụng phần định tuyến tầng mạng Dữ liệu dùng để phân tích bao gồm lượng tiêu hao số gói tin gửi , nhận, chuyển tiếp gói tin bị hủy nút mạng Bảng thống kê gói tin tầng mạng Gửi Gửi data Nhận Nhận data Chuyển tiếp Hủy Flooding 6758 6758 116538 4377 59969 52192 RIP 20124 7152 14255 7152 4933 106 GF 19647 7059 15431 7059 4576 78 DSR 14540 7256 25985 7256 14982 857 Bảng : Thống kê gói tin với 20 nút mạng 225 Qua biểu đồ bảng thống kê gói tin tầng mạng ta thấy : Tỉ lệ gói tin đến đích giao thức Flooding thấp đặc biệt số lượng nút mạng tăng lên giảm xuống 50% , kèm với số lượng gói tin phải chuyển tiếp hủy lớn 10 tới 25 lần số lượng gói tin chuyển gấp 20 tới 50 lần số gói tin đến đích Hai giao thức RIP GF có tỉ lệ gói tin đến đích cao gần 100% nhiên số lượng gói tin gửi tăng nhu cầu gửi thông tin cập nhật bẳng định tuyến (RIP) nhu cầu cập nhật thông tin nút lân cận (GF) Trong giao thức giao thức DSR tỏ hiệu độ giảm thiểu gói tin dư thừa mạng Tuy hiệu suất thành cơng gói tin khơng cao giao thức RIP giao thức GF tỉ lệ cao xấp xỉ 97% với đồ hình 50 nút mạng Độ tiêu hao lượng giao thức : để làm mốc so sánh, đánh giá độ hiệu giao thức định tuyến khác Cải tiến : Chúng ta cải tiến Flooding cách lưu vết đường gói tin qua nút mạng để tránh tượng gửi trùng lặp gói tin Thay chế quảng bá gói tin cách chọn ngẫu nhiên nút lân cận để gửi kết hợp giao thức tốn định tuyến nguồn RIP : Giao thức RIP giao thức định tuyến sử dụng cho mạng có dây với số lượng nút mạng nhỏ, nhiên giữ nguyên chế hoạt động RIP áp dụng vào mạng cảm biến khơng dây xảy số bất cập thứ RIP tiêu tốn lượng dặn sinh gửi gói tin chứa bảng định tuyến cho nút mạng lân cận, thứ hai mạng có số lượng nút lớn gói tin khơng đến đích hop_limit 16, thứ ba RIP hoạt động tốt trang mạng có tíng ổn định cao cập nhật đường chậm đồ hình mạng có thay đổi thay đổi đồ hình mạng mạng cảm biến không dây cao mạng cảm biến có nút mạng chuyển động.Chúng ta cải tiến cách : Cải tiến : Thay định kì gửi gói tin tìm đường nút mạng tìm đường có u cầu gửi gói tin , chế giống với chế giao thức AODV, bên cạnh phải tăng hop_limit để gói tin truyền xa GF: hoạt động hiệu khả truyền gói tin đến đích, nhiên chúng làm tăng dung lượng gói tin mạng phải định kì gửi gói tin cập nhật thơng tin nút lân cận Cũng giống RIP , GF giao thức có độ tin cậy cao có Gửi Flooding Gửi data Nhận Nhận data Chuyển tiếp Hủy 533657 7502 402583 1233541 17525 65985 17524 42260 2930 62497 18009 71671 18009 33306 874 DSR Ta nhận thấy rằng, với số lượng nút mạng (20 nút) , giao thức RIP, GF, DSR có mức tiêu hao lượng gần giống giao thức Flooding tiêu tốn gấp khoảng lần so với giao thức cịn lại Cịn với đồ hình mạng có số nút tăng lên, giao thức Flooding tiêu tốn nhiều lượng mạng, điều chứng minh độ tiêu hao lượng tỷ lệ thuận với số nút mạng, làm tăng số gói tin dư thừa, giảm băng thơng tồn mạng Hai giao thức RIP GF có lượng tiêu hao gần Đặc biệt giao thức DSR tiêu tốn lượng nhất, điều chứng tỏ rằng, nút mạng gửi gói tin tìm đường có nhu cầu, giao thức khơng phải gửi định gói tin giao thức RIP GF 17634 61795 GF Hình 8: Độ tiêu hao lượng 17634 RIP 31106 19455 53563 19445 26919 5458 khả tự cấu hình mạng cập nhật thơng tin đồ hình mạng định kì nên có thay đổi mạng giao thức tìm đường để gói tin đến đích GF có khả cập nhật nhanh RIP cập nhật thông tin nút lân cận thông tin đường RIP Độ hiệu thuật tốn định tuyến GF chương trình mơ tốt thực tế lại khó áp dụng lên tất mạng cảm biến không dây GF hoạt động nút mạng biết vị trí mình, nút lân cận header gói tin phải có thơng tin vị trí nút đích mà thực tế tốn xác định vị trí cho nút mạng mạng cảm biến không dây vấn đề không dễ giải Cải tiến : Với mạng có độ ổn định cao, nút mạng cố định không di chuyển cải tiến GF cách cho nút mạng cập nhật thông tin nút lân cận bắt đầu triển khai mang, sau dùng thơng tin để chuyển tiếp gói tin khơng phải cập nhật thường xun 30 C.Đánh giá, đề xuất cải tiến giao thức Flooding : Qua trình cài đặt thử nghiệm ta thấy hiệu suất truyền gói tin giao thức Flooding khơng cao bên cạnh lại tạo số lượng gói tin dư thừa lớn số lượng gói tin mạng tăng cao gây nghẽn mạng tiêu tốn lượng nút mạng.Vì thực tế Flooding thường sử dụng 226 giây lần, giảm đáng kể lưu lượng gói tin mạng LỜI TRI ÂN DSR : Là giao thức linh động, nút mạng tự cập nhật đường chưa có thơng tin đường lưu nhớ Do DSR áp dụng cho nhiều mạng có đồ hình khác hay có mạng có đồ hình hay thay đổi DSR tiêu thụ lượng ít, gửi gói tin dị đường chưa biết đường Nếu có đường đi, gửi theo định tuyến nguồn tới đích dễ dàng Tuy nhiên số khuyến điểm sử dụng giao thức DSR đề gửi tới số lượng nút đích nhiều, nút lưu nhiều đường nhớ nó, xảy trường hợp phải gửi gói tin dị đường nhiều lần gói tin trả lời khơng nút nguồn Cải tiến : Thay lưu nhiều đường đi, nút lưu đường từ đến nút đích gói tin dị đường từ nút nguồn đến Hạn chế lưu nhiều đường từ nút đến nút khác mà khơng phải nút đích Các nút trung gian cập nhật thơng tin đường thơng qua gói tin chuyển qua KẾT LUẬN Trong thời gian thực đồ án với cố gắng, nỗ lực thân, chúng tơi cịn nhận giúp đỡ hướng dẫn tận tình Tiến sĩ Nguyễn Kim Khánh Thạc sĩ Phạm Văn Thuận giúp chúng tơi hồn thầnh đề tài Chúng muốn gửi lời cám ơn chân thành sâu sắc tới hai thầy Bên cạnh chúng tơi xin cám ơn người bạn ủng hộ động viên cho ý kiến đóng góp để chúng tơi hoàn thành tốt đề tài TÀI LIỆU THAM KHẢO [1] [2] [3] [4] Trong mạng cảm biến khơng dây, hiệu thuật tốn định tuyến phụ thuộc nhiều vào đồ hình mạng ứng dụng mạng Vì để chọn thuật toán định tuyến tốt cho cảm biến khơng dây khó Trong thực tế triển khai mạng cảm biến không dây ta phải phân tích rõ yêu cầu chức ứng dụng đồ hình mạng để lựa chọn thuật tốn định tuyến cho phù hợp [5] [6] [7] [8] [9] Trong nội dung báo cáo giới thiệu phân tích số thuật tốn đinh tuyến cho mạng cảm biến khơng dây dựa sở lí thuyết kết mô Một số cải tiến đề nghị giúp nâng cao hiệu truyền gói tin mạng cho giao thức Flooding, RIP, DSR, GF đạt kết định chương trình mơ Tuy nhiên cần phải kiểm chứng môi trường thực tế nút mạng thật đánh giá xác hiệu giao thức cải tiến [10] [11] [12] [13] Trên sở những phần đạt với khả phát triển đề tài, định hướng nghiên cứu :  Tiếp tục tìm hiểu, cài đặt, phân tích đánh giá thêm giao thức định tuyến khác, từ tìm ưu, nhược điểm để áp dụng cải tiến  Cài đặt thiết bị thực tế nút mạng giao thức cho kết tốt phần mềm mô để đánh giá hiệu thực tế giao thức 227 Jun Zheng and Abbas Jamalipour, “Wireless Sensor Networks: A Networking Perspective”, a book published by A John & Sons, Inc, and IEEEE, 2009 Jamal Al-Karaki, and Ahmed E Kamal, “Routing Techniques in Wireless Sensor Networks: A Survey“, IEEE Communications Magazine, vol 11, no 6, Dec 2004, pp 6-28 Ian F Akyildiz, Iilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci “A survey on Sensor Networks” IEEE Communications Magazine, August 2002 Jamal N Al-Karaki Ahmed E Kamal - Routing Techniques in Wireless Sensor Networks: A Survey www.technologyreview.com Pham Van Thuan – Otimazing routing protocol for Wireless Sensor Network –Ms Thesis – Ha Noi University of Science and Technology - 2009 W R Heinzelman, A Chandrakasan and H Balakrishnan “Energy efficient Communication Protocol for Wireless Microsensor Networks ” Proceedings of the IEEE Hawaii International Conference onSystem Sciences (HICSS), Vol (2000) 1-10 R C Shah and J M Rabaey “Energy aware routing for low energy adhoc sensor networks” Proceedings of the IEEE Wireless Communication and Networking Conference (WCNC) (2001) Karl, H.; Willig, A Protocols and Architectures for Wireless Sensor Networks John Wiley & Sons:Chichester, West Sussex, UK, 2005 A Kermarrec and G Tan - Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach MobiHoc 2010 C Hendrik, RFC 1058, Routing Information Protocol, The Internet Society (June 1988) Y.Hu – UIUC - D Maltz - The Dynamic Source Routing Protocol (DSR) Rice University –Microsoft Research - February 2007 WSNET - An event-driven simulator for large scale wireless sensor networks - http://wsnet.gforge.inria.fr Nghiên cứu lý thuyết xây dựng hệ thống phát xâm nhập Nguyễn Xuân Quang Trong khuôn khổ đề tài đưa thuật toán phát xâm nhập có khả ứng dụng tốt TCM-KNN (Transductive ConfidenceMachines for K-Nearest Neighbors) Trên quan điềm kế thừa đặc điểm bật thuật toán KNN ( k-nearest neighbor) lý thuyết thống kê Thuật toán TCM-KNN tỏ có nhiều điểm bật khả phát tốt, khơng địi hỏi q khắt khe liệu đầu vào.Với kết đạt khả ứng dụng thuật toán thực tế lớn  Tóm tắt: Hiện với phát triển mạng máy tính xuất nguy an toàn thông tin an ninh mạng Với xu việc nghiên cứu giải pháp để tăng cường an ninh cho hệ thống thông tin ngày ý Trong nghiên cứu hệ thống phát xâm nhập dựa bất thường mạng ngày quan tâm Nội dung đề tài trình bày thuật tốn TCM-KNN ứng dụng việc phát xâm nhập Các kết kiểm tra với liệu KDD cup 99 cho kết phát tốt tốt với độ phức tạp thuật tốn khơng q cao mở khả ứng dụng thuật toán việc xây dựng hệ thống phát xâm nhập thực tế Cơ sở lý thuyết thuật toán TCM-KNN 2.1 Các đại lượng ngẫu nhiên phân phối xác suất việc phát xâm nhập Đại lượng ngẫu nhiên hay biến ngẫu nhiên giá trị thực tùy thuộc vào kết ngẫu nhiên phép thử Để xác địnhđặc trưng cho đại lượng ngẫu nhiên người ta sử dụng hàm phân phối xác xuất Với biến ngẫu nhiên liên tục ta có hàm phân phối xác suất là: 𝐹 𝑥 = 𝑃(𝑋 < 𝑥) (1) Với x biến số bất kỳ.Hàm phân phối ngẫu nhiên sử dụng với biến ngẫu nhiên rời rạc.Hàm phân phối xác suất đặc trưng cho xác suất xuất đại lượng nhỏ biến số x không gian mẫu.Với không gian mẫu xác định xuất phát từ đặc trưng cho khả tồn biến số x không gian mẫu xác định trước.Nhờ vào tính chất ta xác định giá trị có thuộc vào lớp cho trước không Các liệu mạng đại lượng ngẫu nhiên ( đại lượng ngẫu nhiên liên tục) việc lấy mẫu theo chu kỳ nên coi việc tính tốn biễn ngẫu nhiên rời rạc Những nghiên cứu Martin-Lὃf tồn phương pháp để xác định đặc điểm chuỗi liệu Nhưng khơng thể tính tốn mà phải dựa tính tốn gần dựa vào giá trị p ( xác suất xuất hiện) p đặc trưng cho xác suất xuất hay quan sát điểm mẫu biến ngẫu nhiên Giá trị p sử dụng giá trị để đánh giá khả tồn hay không tồn điểm tập liệu cho trước Giá trị p lớn cho ta thấy khả điểm ta xem xét thuộc lớp liệu ta xem xét cao, giá trị p nhỏ cho ta thấy khả điểm ta xem xét thuộc lớp liệu ta có nhỏ Về tính tốn ta có: 𝑝 𝑥 = 𝑃(𝑋 > 𝑥) (2) Với tính chất giá trị p dùng phương pháp phân lớp chia đặc tính tốt Trong mơi trường mạng thời điểm chia vào trạng thái ( lớp) khác như: bình thường, ddos, … Việc sử dụng xác suất p việc xác định bất thường mạng đạt hiệu tốt Ta có với liệu mạng trạng thái sau: (𝑥1 , 𝑥2 ,…,𝑥 𝑛 ) ta có xác suất ứng với giá trị ngẫu nhiên x tính sau: #(𝑥≤𝑥 𝑛 ) 𝑝 𝑥 = (3) 𝑛 Với #(𝑥 ≤ 𝑥 𝑛 ) phép đếm giá trị (𝑥 ≤ 𝑥 𝑛 ) Việc sử dụng Từ khóa: hệ thống phát xâm nhập, TCM-KNN, an ninh mạng Giới thiệu Ngày cơng nghệ thơng tin ngày phát triển ngồi tiện ích hỗ trỡ việc giao tiếp làm việc người Mạng internet phát triển mang lại nhiều rủi ro vấn đề an tồn thơng tin, cơng mạng Do việc bảo vệ an tồn thơng tin giữ an ninh cho hệ thống mạng ngày trở thành vấn đề cấp thiết cần nghiên cứu Một chủ đề đề cập nghiên cứu nhiều nghiên cứu xây dựng hệ thống phát xâm nhập ( thiết bị khơng thể thiếu việc bảo đảm an tồn cho mạng thông tin) Phát xâm nhập dựa bất thường mạng [8] phần quan trọng việc nghiên cứu an ninh mạng nói chung hệ phát xâm nhập nói riêng Hiện có nhiều phương pháp đưa việc phát xâm nhập dựa vào bất thường mạng như: thuật toán KNN, SVMs (support vector machines),Neutron… Nhưng thuật tốn cịn gặp phái nhiều hạn chế xác suất phát thấp, đòi hỏi liệu đầu vào khắt khe Do ứng dụng thực tế thuật toán chưa cao Đề tài thực bảo trợ trường Đại học Bách Khoa Hà Nội , sử dụng kết nghiên cứu giáo sư Yang Li học viện khoa học Bắc Kinh Nguyễn Xuân Quang, sinh viên lớp HTT&TT-KSCLC-K51 trường Đại học Bách Khoa Hà Nội (e-mail:quangnx@vnsecurity.vn) © Viện Cơng nghệ thơng tin Truyền thông, trường Đại học Bách Khoa Hà Nội 228 hàm xác suất p cho ta phương pháp xác địnhtốt việc xác định giá trị thuộc mẫu xác định sử dụng vọng số sau : 𝑥 ≤ (𝑋 ± 𝜀) (4) Với ɛ giá trị nhỏ thường dùng lần độ lệch quân phương tập biến ngẫu nhiên có đặc tính Với nghiên cứu đại lượng ngẫu nhiên cho ta phương pháp có tính xác cao tính tốn dùng việc phát bất thường môt trường mạng.Giá trị xác suất p thuật toán TCM-KNN sử dụng kết để xác định phân lớp trạng thái mạng xác định trạng thái điểm cần xem xét ta xét với điểm khác có quan hệ với Trong trường hợp ta sử dụng thuật toán KNN ( quan tâm đến điểm gần nó) có giá trị xác định khác biệt tính sau: 𝑎 𝑖𝑦 = 𝑦 𝑘 𝑗 =1 𝐷 𝑖𝑗 −𝑦 𝑘 𝑗 =1 𝐷 𝑖𝑗 (5) Với k số điểm hàng xóm Giá trị tính tốn thương tổng khoảng cách điểm với k điểm lớp với tổng khoảng cách điểm với k điểm khác nhóm ( tổng xếp) Giá trị tăng khoảng cách từ điểm đến điểm lớp tăng lên khoảng cách từ đến điểm khác lớp ngắn lại Với giá trị gần đề cập phần trước để làm cho tính tốn liệu ngẫu nhiên ta có hàm p tính từ giá trị khác biệt (trangeness) điểm đưa sau: #{𝑖:𝑎 𝑖 >𝑎 𝑛𝑒𝑤 } 𝑝 𝑎 𝑛𝑒𝑤 = (6) 𝑛 +1 Với 𝑎 𝑛𝑒𝑤 giá trị xác định khác biệt điểm ta xem xét thuộc tập liệu cần phân lớp (test set) Các liệu dùng để so sánh với 𝑎 𝑛𝑒𝑤 tập giá trị đánh giá khác biệt tập hợp điểm dùng cho trị học tập (training phase) Số lượng giá trị đánh giá khác biệt tập liệu học tập lớn 𝑎 𝑛𝑒𝑤 j ta có giá trị sác xuất suất điểm ta cần xem xét tính thương j chia cho (n+1) Hay giá trị p xác định xác suất giá trị ta xem xét tập hợp gồm bao gồm điểm thuộc nhóm liệu học tập điểm ta cần xem xét Thuật toán TCM-KNN xây dựng dựa hàm tính tốn giá trị p phương trình (6) Thuật tốn trình bày dạng sơ đồ khối sau: 2.2 Thuật toán KNN (k-nearest neighbor) Thuật toán KNN thuật toán với độ phức tạp thấp sử dụng việc phân lớp chia đặc tính với liệu ta cần phân tích Thuật toán KNN sử dụng phương pháp dựa điểm khác biệt điểm ta cần xét với hàng xóm có đặc điểm, từ đưa liệu mà từ làm để xác định điểm ta xem xét có đặc tính với điểm mà ta có khơng Trong thuật tốn KNN với điểm ta xét ta quan tâm đến điểm gần Việc làm cho việc tính tốn đơn giản đưa khả phân lớp xác đính khác biệt tốt Điểm hạn chế thuật toán KNN việc sử dụng điểm gần với điểm ta xem xét, có khuyết điểm sau: - Các điểm lân cận khơng giống với điểm mà ta xem xét - Do đặc điểm nên khả phân lớp phát bất thường mạng không cao Để hạn chế đặc điểm thuật toán TCM-KNN thay tính tốn khác biệt điểm ta xem xét với điểm gần giá trị tính tốn khác biệt điểm ta xem xét với điểm gần giống ( phép xếp tập khoảng cách điểm) 2.3 Thuật toán TCM-KNN Thuật toán TCM-KNN sử dụng để phân lớp liệu phát triển để phát bất thường mạng Giả sử có nhóm liệu mẫu đầu vào ( training set) với n điểm { 𝑥1 , 𝑦1 , … , 𝑥 𝑛 , 𝑦 𝑛 } 𝑥 𝑖 = {𝑥1 , … , 𝑥 𝑖 𝑚 ) 𝑖 tập thông tin trạng thái mạng ( số lượng connection, số bytes gửi nhận ….) 𝑦 𝑖 lớp điểm thuộc vào có giá trị từ (1,2,…,c) (DDOS, Sql injection …) Quá trình kiểm tra thuật toán sử dụng tập hợp điểm với đặc tính giống liệu mẫu đầu vào tiến hành phân lớp điểm thuộc nhóm này.[3] Để loại bỏ hạn chế thuật toán KNN khác với thuật toán KNN ( K-Nearest Neighbors) với thuật toán TCM ta xếp tập khoảng cách điểm nhóm ( tính tốn sử dụng phương pháp tính khoảng cách ví dụ 𝑦 Euclid Distance) Ta có: 𝐷 𝑖 khoảng cách từ điểm i đến −𝑦 điểm loại xếp, 𝐷 𝑖𝑗 khoảng cách ngắn thứ j −𝑦 𝐷 𝑖 khoảng cách từ điểm i đến điểm khác loại Các liệu xử dụng để tính tốn giá trị mà ta gọi giá trị xác định khác biệt.Giá trị xác định khác biệt điểm Hình 1.a Sơ đồ khối thuật toán TCM-KNN Ta thấy thuật toán để phân lớp liệu ta cần liệu training đầy đủ, thêm thuật toán có độ phức tạp tính tốn tốn nhớ lớn Vì lý thuật tốn có giá trị mặt lý thuyết cần thay đổi để áp dụng thực tế 2.4 Thuật toán TCM-KNN áp dụng thực tế 229 Thời gian để xác định tính chất giá trị instance đầu vào phụ thuộc vào việc tính tốn Distance với liệu tranning bao gồm khâu tính tốn: - Xác định khoảng với giá trị training data set ( độ phức tạp cỡ 𝑂(𝑛) ) - Sắp xếp giá trị ( độ phức tạp cỡ 𝑂 𝑛𝑙𝑜𝑔𝑛 với thuật toán xếp hiệu quả) - So sánh giá trị tính để xác định p ( độ phức tạp cỡ n) Do thời gian để tính tốn với giá trị instance đầu vào có độ phức tạp cỡ 𝑂(𝑛𝑙𝑜𝑔𝑛) với khối lượng tranning data set đủ nhỏ thời gian tính tốn chấp nhận Đánh giá nhớ sử dụng thuật toán: giá trị D lưu trữ với khối lượng lớn cỡ 𝑛2 nên nhớ sử dụng chủ yếu tính tốn xử lý nhớ dành cho việc lưu trữ giá trị khoảng cách việc xếp giá trị Vì việc sử dụng tài nghiên mức 𝑛2 độ lớn liệu D Để giải hạn chế thuật toán TCM-KNN nêu để thuật toán sử dụng với liệu đầu vào “ khơng đầy đủ” có thời gian tính toán đủ thấp Thuật toán áp dụng số thay đổi sau: - Các điểm chia làm lớp “bình thường” (normal) “khơng bình thường” (unormal) - Do có hai lớp lên giá trị 𝑎 𝑖𝑦 thay 𝑎 𝑖 tính tốn: 𝑎 𝑖 = 𝑗𝑘=1 𝐷 𝑖𝑘 (7) Những thay đổi giúp cho thuật tốn thích hợp xử dụng thực tế, với độ phức tạp chấp nhận cho việc tính tốn thời gian thực Thuật tốn miêu tả sơ đồ khổi sau: Bảng 1.Đánh giá độ phức tạp thuật toán Pharse Phép toán chủ yếu Độ phức tạp Tranning Phép toán xếp 𝑂(𝑛2 𝑙𝑜𝑔𝑛) detect Phép toán xếp 𝑂(𝑛𝑙𝑜𝑔𝑛) Đánh giá trường hợp phép tính distance có độ phức tạp đủ nhỏ Dữ liệu D 𝑎 p xếp Hình 1.b Sơ đồ khối thuật toán TCM-KNN dùng thực tế Thuật toán để phân lớp liệu ta cần liệu training đầy đủ, thêm thuật tốn có độ phức tạp tính tốn tốn nhớ lớn Vì lý thuật tốn có giá trị mặt lý thuyết cần thay đổi để áp dụng thực tế Các thay đổi khiến cho độ phức tạp thuật tốn giảm xuống đến mức chấp nhận để sử dụng thực tế, trì khả phát cao Số lượng 𝑛2 n n Phụ thuộc vào thuật toán xếp Khối lượng liệu 𝑛2 độ lớn D n * độ lớn 𝑎 n * độ lớn liệu Phụ thuộc vào thuật toán xếp lựa chọn n Bảng 2.Đánh giá mức độ sử dụng nhớ Bộ nhớ sử dụng phụ thuộc nhiều vào giải thuật dạng liệu mà ta lựa chọn 2.5 Đánh giá độ phức tạp sử dụng tài nguyên thuật toán Khi liệu đầu vào chuẩn hóa số phép tốn phức tạp sử dụng nhiều thuật toán phép toán xếp liệu ( sử dụng n lần) Do độ phức tạp thuật toán phụ thuộc nhiều vào thuật tốn xếp ta lựa chọn Vì tính phụ thuộc thời gian thuật toán vào phép so sánh nên thuật toán xếp lựa chọn phải thuật tốn hiệu ví dụng như: quick sort, heap sort, merger sort… Với việc sử dụng thuật toán xếp với độ phức tạp thấp mức 𝑂(𝑛𝑙𝑜𝑔𝑛) độ phức tạp thuật tốn cỡ 𝑂(𝑛2 𝑙𝑜𝑔𝑛) phép tốn xếp sử dụng n lần thuật toán pharse tranning ( pharse đòi hỏi thời gian lớn thuật tốn) 3.1 Mơ hình thiết kế hệ thống Hệ thống bao gồm thành phần chính:  Thu thập liệu  Phân tích liệu ( dùng trình học tập)  Tiền xử lý liệu  Thuật toán lõi TCM-KNN Sau mơ hình hệ thống thể dạng sơ đồ khối bao gồm đầy đủ thành phần bố trí theo trình tự tính tốn 230 Q trình phân tích lựa chọn tham số ranking khâu quan trọng ảnh hưởng trược tiếp đến khả phát bất thường thuật toán.Dựa vào bất đẳng thức Trêbưsép: 𝐷(𝑋) 𝑃 𝑋 − 𝑎 < 𝜀 ≥ − 𝜀 (8) Để cân tham số điểm xem xét với giá trị ɛ xấp xỉ ta tính tốn giá trị 𝐷(𝑋) ứng với tham số miền điểm dùng cho training phase Sau xếp giá trị 𝐷(𝑋) ta có giá trị 𝐷 𝑚𝑎𝑥 giá trị lớn 𝐷(𝑋) Việc lựa chọn trọng số thực sau: - Chọn giá trị ngưỡng 𝜏 ( ta lấy 1% hay 0.01) - Với 𝐷 𝑋 > 𝜏 ∗ 𝐷 𝑚𝑎𝑥 ta có ranking cho 𝐷 𝑋 𝐷 𝑚𝑎𝑥 𝐷(𝑋) Hình Mơ hình thiết kế.[2] - Thành phần thu thập liệu dùng chung cho trình trình học phát hiện, thành phần thu thập yếu tố đầu vào mạng số connections, trung bình thời gian connections, Các liệu liệu cho trình xử lý sau thành phần khác Chất lượng thành phần hay module ảnh hưởng nhiều đến khả phát thuật toán cần cơng cụ có tính xác cao Thành phần phân tích liệu dùng q trình học, thành phần phân tích liệu “bình thường” thu thập thành phần thu thập liệu đưa thông tin như: liệu lựa chọn để đưa bước tính tốn sau, tính rank cho tham số đầu vào mà trình thu thập liệu thu thập Quá trình thực tốt tăng xác suất phát cho hệ thống mà ta xây dựng Thành phần tiền xử lý liệu sử dụng cho trạng thái hệ thống.Thành phần dùng thông tin mà thành phần phân tích liệu đưa để xử lý với điểm đầu vào đưa kết cho thuật toán TCM-KNN.Thành phần góp phần giảm chi phí tính tốn thuật tốn TCM-KNN khiến có nhiều khả ứng dụng thực tế Trong khuôn khổ đề tài nghiên cứu thành phần phân tích liệu thuật toán lõi TCM-KNN thành phần nghiên cứu xem xét Các trường hợp cịn lại 𝐷 𝑋 ≤ 𝜏 ∗ 𝐷 𝑚𝑎𝑥 ranking 𝜏 Giá trị thu gọi 𝑟 𝐷 (𝑋) Một giá trị sử dụng cho trình đánh ranking số lượng giá trị khác mẫu tham số ( giá trị làm tròn theo (10 ∗ 𝜏)% 𝐷 𝑋 ) thu giá trị mà gọi 𝑓𝑛 (𝑋) Quy đồng 𝑓𝑛 (𝑋) với ranking theo 𝐷 𝑋 cách chia với giá trị 𝑛 ∗ 𝜏( n số điểm sử dụng training phase) Giá trị thu 𝑟𝑓 (𝑋) Với giá trị tính việt đánh giá tương đương có trọng số ứng với tham số tính tốn sau 𝑟 (𝑋) 𝑟 𝑋 = 𝑟 𝐷 (𝑋) (9) 𝑓 Với việc đánh ranking đưa vào tiền xử lý liệu ta đưa liệu đầu với điểm cần xét tham số Như với việc nâng cao chất lượng phân tích đánh giá liệu tương ứng với khả nâng cao chất lượng phát giảm độ phức tạp thuật toán 3.4 Thử nghiệm kết thu Thuật toán thành phần phân tích liệu lập trình ngơn ngữ python liệu đầu vào dạng csv, lưu thành file Quá trình kiểm tra thực với liệu đầu vào clean unclean, với liệu để kiểm tra giống gồm 8000 điểm lọc Thực tính tốn với liệu với giá trị k thay đổi giá trị ( 50,100,150,200) giá trị ngưỡng 𝜏 giữ không đổi 0.05 hay 5% cho kết đáng khả quan 3.2 Dữ liệu dùng để đánh giá thuật toán Dữ liệu sử dụng tập liệu kddcup99 [5] liệu hay sử dụng để kiểm tra thuật toán máy học dùng cho việc phát bất thường mạng Dữ liệu đưa bao gồm 42 tham số bản, tách để kiểm tra thuật toán sau: Training Phase: Clean data Dữ liệu 4000 điểm trạng thái bình thường Unclean data Dữ liệu 4000 điểm ( 3950 trạng thái “bình thường” 50 “khơng bình thường”) Detecting Phase: Dữ liệu 8000 điểm ( với 2463 trạng thái “khơng bình thường” 5537 “trạng thái bình thường”) Với liệu clean : Bảng Kiểm tra với liệu clean TP FP 99.41% 2.97% K=100 𝜏 =0.05 99.14% 3.44% K=150 𝜏 =0.05 98.98% 3.8% K=200 𝜏 =0.05 99.21% 3.86% K=50 𝜏 =0.05 3.3 Phân tích liệu lựa chọn trọng số ranking 231 [7] Denning, Dorothy E., "An Intrusion Detection Model," Proceedings of the Seventh IEEE Symposium on Security and Privacy, May 1986, pages 119–131 [8] Vaccaro, H.S., and Liepins, G.E., "Detection of Anomalous Computer Session Activity," The 1989 IEEE Symposium on Security and Privacy, May, 1989 [9] Lunt, Teresa F., "Detecting Intruders in Computer Systems," 1993 Conference on Auditing and Computer Technology, SRI International [10] Dowell, Cheri, and Ramstedt, Paul, "The ComputerWatch Data Reduction Tool," Proceedings of the 13th National Computer Security Conference, Washington, D.C., 1990 [11] Winkeler, J.R., "A UNIX Prototype for Intrusion and Anomaly Detection in Secure Networks," The Thirteenth National Computer Security Conference, Washington, DC., pages 115–124, 1990 Với liệu unclean Bảng Kết kiểm tra với liệu unclean TP FP 98.94% 3.61% K=100 𝜏 =0.05 98.74% 4.31% K=150 𝜏 =0.05 98.82% 4.67% K=200 𝜏 =0.05 98.32% 4.72% K=50 𝜏 =0.05 Các kết thu cho thật thấy tốn có khả phát cho thấy thuật tốn có khả phát tốt với xác suất phát xác lớn xác suất báo sai khơng q cao Thêm vào kết kiểm tra với liệu clean liệu unclean ( có nhiễu) cho thấy thuật tốn khơng bị phụ thuộc nhiều vào chất lượng liệu đầu vào.Q trình phân tích liệu lựu chọn tham số khiến cho thuật tốn có độ phức tạp thời gian tính tốn giảm nhiều việc khơng phải sử dụng thuật tốn tính distance với 42 tham số liệu đầu vào.Kết thu cho ta thấy với k có giá trị nhỏ thuật tốn đạt độ xác cao hơn, việc thuận lợi cho q trình tính tốn với k thấp độ phức tạp thuật tốn giảm nhiều Qua việc kiểm tra thuật toán ta thấy thuật tốn TCM-KNN thuật tốn có độ phức tạp chấp nhận để áp dụng thực tế, với xác suất phát cơng xác cao Điều cho thấy khả ứng dụng thuật toán việc xây dựng hệ thống phát xâm nhập thực tế Kết luận hướng phát triển tương lai Từ kết đạt cho ta thấy khả ứng dụng thuật toán TCM-KNN thực tế Để áp dụng thuật toán vào thực tế cần nghiên cứu thêm tương lai phương pháp để giảm độ phức tạp tính tốn thuật tốn tăng khả phát giảm xác suất báo sai.Trong thời gian tới xây dựng sản phẩm dựa thuật toán thử nghiệm thực tế để kiểm tra hiệu khả áp dụng vào mơi trường mạng Tài liệu tham khảo [1] An Effective TCM-KNN Scheme for High-Speed Network Anomaly Detection, Yang Li Chinese Academy of Sciences, Beijing China [2] TCM-KNN Algorithm for Supervised Network Intrusion Detection, Yang Li , Bin-Xing Fang , Li Guo , and You Chen [3] Proactive Detection of DDoS Attacks Utilizing k-NN Classifier in an Anti-DDos Framework, Hoai-Vu Nguyen and Yongsun Choi [4] Mitigating Distributed Denial of Service Attacks Using a Proportional-Integral-Derivative Controller, Marcus Tylutki and Karl Levitt [5]http://kdd.ics.uci.edu/databases/kddcup99/task.html [6] Anderson, James P., "Computer Security Threat Monitoring and Surveillance," Washing, PA, James P Anderson Co., 1980 232 HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC LẦN THỨ XXVIII NĂM HỌC 2010 – 2011 VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NHÀ XUẤT BẢN BÁCH KHOA – HÀ NỘI Số – Đại Cồ Việt – Quận Hai Bà Trưng – Hà Nội Điện thoại: 04 38684569; Fax: 04.38684570 Chịu trách nhiệm xuất bản: Giám đốc – Tổng biên tập Phùng Lan Hương Chịu trách nhiệm nội dung: Viện CNTT&TT, Trường Đại học Bách Khoa Hà Nội Biên tập: Đỗ Bá Lâm, Trần Tuấn Vinh Trình bày bìa: Nguyễn Xuân Cương In 80 khổ 21 x 29.7 cm xưởng in Nhà xuất Bách Khoa Hà Nội Giấy xác nhận đăng ký kế hoạch xuất số: In xong nộp lưu chiểu quý II năm 2011 233 ... chấm giải Viện Quyển kỉ yếu Hội nghị SVNCKH – Viện CNTT&TT thể kết làm việc nghiêm túc, đầy nỗ lực sinh viên giảng viên hướng dẫn nghiên cứu giảng dạy năm học 2010 – 2011 Cuốn kỉ yếu kỉ niệm đẹp,... GIỚI THIỆU Hội nghị Sinh viên nghiên cứu khoa học (SVNCKH) kiện thường niên tổ chức Đại học Bách Khoa Hà Nội, có tham gia Viện Công nghệ thông tin Truyền thơng (CNTT&TT) Chính từ hội nghị này,... viên? ? ?Hội nghị SVNCKH hàng năm sân chơi kích thích niềm sáng tạo, giúp sinh viên làm quen với thử thách nghiệp nghiên cứu, tìm tịi tri thức Phát huy kết đạt được, năm học 2010 – 2011, Viện CNTT&TT tiếp