Trong bài viết này, chúng tôi tiếp tục nghiên cứu thuật toán MCMF cho MTA trong việc: Xử lý ràng buộc dương vô cùng trong hàm mục tiêu đã đề xuất trước đây và đề xuất một chu trình đổi luồng mới nhằm giảm giá trị cho hàm mục tiêu đến mức tối đa. Thuật toán MCMF dựa trên chu trình mới vẫn đảm bảo chạy trong thời gian đa thức. | CẢI TIẾN THUẬT TOÁN LUỒNG CỰC ĐẠI CÓ GIÁ CỰC TIỂU CHO PHƯƠNG PHÁP MTA PHAN HOÀNG NAM*, TRẦN HOÀI NHÂN Khoa Tin học, Trường Đại học Sư phạm, Đại học Huế * Email: nam18ph@ Tóm tắt: Radio Frequency Identification (RFID) là công nghệ vô tuyến tầm ngắn để thu thập dữ liệu tự động xuất hiện lần đầu tiên vào thập niên 1960. Có hai phương pháp cân bằng tải cho hệ thống RFID đã được đề xuất vào năm 2007 là phương pháp Min-Max Cost Assignment (MCA) và Min-Max Tag Count Assignment (MTA). Trong đó, phương pháp MTA là trường hợp đặc biệt của MCA. Qunfeng Dong và các cộng sự đã đề xuất các thuật toán cho MTA dựa trên Luồng cực đại (MNF). Trong luận văn, tôi đã đề xuất một hàm mục tiêu với vai trò phân phối lại thẻ dựa trên năng lượng của bộ đọc và sử dụng thuật toán Luồng cực đại có giá thành nhỏ nhất (MCMF) cho MTA. Trong bài báo này, chúng tôi tiếp tục nghiên cứu thuật toán MCMF cho MTA trong việc: Xử lý ràng buộc dương vô cùng trong hàm mục tiêu đã đề xuất trước đây và đề xuất một chu trình đổi luồng mới nhằm giảm giá trị cho hàm mục tiêu đến mức tối đa. Thuật toán MCMF dựa trên chu trình mới vẫn đảm bảo chạy trong thời gian đa thức. Cuối cùng chúng tôi chứng minh đây là một cải tiến so với thuật toán đã trình bày trong luận văn. Từ khóa: MCMF, MNF, MCA, MTA, RFID. 1. GIỚI THIỆU RFID là công nghệ nhận dạng đối tượng bằng sóng vô tuyến, cho phép truyền và nhận dữ liệu từ một điểm đến một điểm khác. Công nghệ này đáng tin cậy để phát hiện và giám sát điện tử, một dạng mới của phương pháp truyền thông tin vô tuyến. Bộ đọc quét dữ liệu của thẻ và gửi thông tin đến cơ sở dữ liệu lưu trữ dữ liệu của thẻ. Công nghệ này có ứng dụng lớn trong thực tiễn: Thẻ có thể được đặt trên kính chắn gió xe hơi để hệ thống thu phí đường bộ có thể nhanh chóng nhận dạng và thu tiền trên các tuyến đường. Một hệ thống RFID có ba thành phần cơ bản: Thẻ, Bộ đọc và Máy chủ. Hình 1. Hệ thống RFID Tạp chí Khoa học, Trường Đại học Sư phạm, Đại học Huế ISSN 1859-1612, Số 04(48)/2018: tr. .
