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

Abstract

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.