Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài báo này nghiên cứu về bài toán định tuyến đa điểm (multicast) cho mạng cảm biến không dây nhiệm vụ tuần hoàn (DC-WSN). Đặc điểm của loại mạng cảm biến không dây này là các nút cảm biến hoạt động tuần hoàn theo chu kỳ và không bắt buộc phải hoạt động liên tục. Bài toán này đã được chứng minh thuộc lớp NP-khó. | Journal of Computer Science and Cybernetics, V.30, N.3 (2014), 253–266 DOI:10.15625/1813-9663/30/3/3328 GIẢI THUẬT HEURISTIC VÀ DI TRUYỀN GIẢI BÀI TOÁN ĐỊNH TUYẾN ĐA ĐIỂM TRÊN MẠNG CẢM BIẾN KHÔNG DÂY NHIỆM VỤ TUẦN HOÀN NGUYỄN THÁI DƯƠNG1 , HUỲNH THỊ THANH BÌNH2 , NGÔ HỒNG SƠN3 Trường Đại học Bách Khoa Hà Nội, Việt Nam 1 thaiduongnguyen91@gmail.com; 2 binhht@soict.hust.edu.vn; 3 sonnh@soict.hust.edu.vn Tóm tắt. Bài báo này nghiên cứu về bài toán định tuyến đa điểm (multicast) cho mạng cảm biến không dây nhiệm vụ tuần hoàn (DC-WSN). Đặc điểm của loại mạng cảm biến không dây này là các nút cảm biến hoạt động tuần hoàn theo chu kỳ và không bắt buộc phải hoạt động liên tục. Bài toán này đã được chứng minh thuộc lớp NP-khó. Chúng tôi đề xuất một giải thuật heuristic và một giải thuật di truyền để giải bài toán trên. Các giải thuật đề xuất được thử nghiệm trên bốn dạng đồ thị mạng cảm biến và được so sánh kết quả với giải thuật TCS là giải thuật tốt nhất hiện nay. Kết quả thử nghiệm cho thấy các giải thuật đề xuất đưa ra lời giải tốt hơn giải thuật TCS về mặt tối ưu năng lượng. Từ khóa. Mạng cảm biến không dây, multicast, tối thiểu năng lượng, giải thuật heuristic, giải thuật di truyền. Abstract. We study the Minimum-Energy Multicasting problem in Duty-Cycled Wireless Sensor Networks (DC-WSN). In DC-WSN, nodes can switch between active and dormant states to save energy. This problem has proved to be NP-hard. This paper proposes a heuristic algorithm and a genetic algorithm for solving this problem. We compare the proposed algorithms with TCS - the best known algorithm - by means of simulation on four typical WSN topologies. Experimental results show that our algorithms significantly outperform TCS in terms of minimizing the energy cost. Keywords. Wireless sensor networks, multicast, minimum-energy, heuristic, genetic algorithm. 1. GIỚI THIỆU Hiện nay, mạng cảm biến không dây đang được sử dụng rộng rãi trong theo dõi môi trường, giám sát đối tượng, cảnh báo nguy cơ
