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

pdf
Số trang 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 11 Cỡ tệp 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 1 MB Lượt tải 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 0 Lượt đọ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 0
Đánh giá 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
4.2 ( 15 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 11 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

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@gmail.com 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. 117-127 Ngày nhận bài: 16/11/2018; Hoàn thành phản biện: 10/12/2018; Ngày nhận đăng: 12/12/2018 PHAN HOÀNG NAM, TRẦN HOÀI NHÂN 118 Việc sử dụng năng lượng ở bộ đọc chủ yếu trong giao tiếp bộ đọc-thẻ. Giảm thiểu năng lượng này được các tác giả trong [1],[2] xem như là vấn đề Min-Max Cost Assignment (MCA), với giả sử rằng bộ đọc có thể sử dụng các mức công suất khác nhau để đọc các thẻ khác nhau, được xác định dựa trên khoảng cách của thẻ với bộ đọc. Các phương pháp sau sẽ xem xét vấn đề cân bằng tải dưới bài toán tối ưu hóa trên đồ thị. Cấu trúc tiếp theo của bài viết như sau: mục 2 trình bày mô hình bài toán RFID và các nghiên cứu liên quan; mục 3 mô tả thuật toán đề xuất; mục 4 mô phỏng đánh giá thuật toán đề xuất và mục 5 là phần kết luận. 2. MÔ HÌNH BÀI TOÁN VÀ CÁC NGHIÊN CỨU LIÊN QUAN 2.1. Mô hình hóa RFID bằng đồ thị Các tác giả trong [1],[2] đã chuyển bài toán cân bằng tải trong hệ thống RFID thành mô hình đồ thị hai phía có trọng số dương G  U V , E , trong đó: - U  u1 , u2 ,..., um  là tập hợp m bộ đọc và V  v1 , v2 ,..., vn  là tập hợp n thẻ. - E   u, v  u U , v V  là tập cạnh sao cho bộ đọc u và thẻ v có thể giao tiếp với nhau.   - cij  c ui , v j  0 là năng lượng mỗi lần bộ đọc ui đọc thẻ v j . m bộ đọc … … S n thẻ … … Hình 2. Đồ thị mô hình hóa hệ thống RFID 2.2. Phương pháp MCA và MTA Các tác giả trong [1], [2] tiếp tục đề xuất các phương pháp cân bằng tải cho hệ thống RFID trên đồ thị. Họ đã mô hình hóa phương pháp MCA như sau: Cho đồ thị G  U V , E , chi phí cij :  ui , v j  Z  và Bi  Z  . Tìm một phân bổ  :V  U cho các thẻ v j vào các bộ đọc sao cho tổng chi phí năng lượng tối đa trên tất cả các bộ đọc được tối thiểu và thỏa ràng buộc trên mỗi bộ đọc ui  U .  cij  Bi (1)   Nếu cij  1 phương pháp MCA được chuyển thành phương pháp MTA (Min-Max Tag j1, n ,ui  v j Count Assignment). CẢI TIẾN THUẬT TOÁN LUỒNG CỰC ĐẠI CÓ GIÁ TRỊ CỰC TIỂU... 119 2.3. Đề xuất thuật toán MCMF cho phương pháp MTA Phương pháp MTA có thể được giải quyết bằng thuật toán Luồng cực đại trên mạng (MNF) [1], [6], [7]. Từ mô hình đồ thị G  U V , E biểu diễn phương pháp MCA các tác giả đã chuyển thành một Mạng như sau:   ui , v j   E đều có khả năng thông qua cij  c  ui , v j   1 . U  U s, t , s được gọi là đỉnh phát, t được gọi là đỉnh thu. E  E   s, ui  E  E  v j , t  ui U với khả năng thông qua v j  V với khả năng thông qua cs ,ui  c( s, ui )  Bi cv j ,t  c(v j , t )  1 . . MTA trở thành bài toán tìm Luồng cực đại (Maximum Network Flow - MNF) trên mạng G  U V , E . Hàm mục tiêu cho thuật toán MNF Để hệ thống đạt hiệu quả hơn trong việc sử dụng năng lượng, bằng cách phân bố lại số thẻ dựa trên mức năng lượng của bộ đọc mà không ảnh hưởng đến số lượng tối đa các thẻ đã được phân phối cho các bộ đọc. Tác giả trong [3] đã đề xuất một hàm mục tiêu phân c bố như sau: T   uU s ,u  min (2) f s ,u cs ,u  u  U : f s ,u  0  uU f Ràng buộc: T   (3) s ,u   u  U : f s ,u  0  T được gọi là tỉ số giữa năng lượng của bộ đọc u và số thẻ được gán cho bộ đọc đó. Giá trị hàm T cần nhỏ nhất, bài toán tìm Luồng cực đại trên mạng trở thành bài toán tìm Luồng cực đại với giá cực tiểu (Minimum Cost Maximum Flow - MCMF). Ví dụ: Chuyển đổi bài toán MTA sang bài toán MNF và MCMF m bộ đọc 1 1 1 … … … … s n thẻ t 1 Hình 3. Mô hình bài toán tìm Luồng cực đại có giá cực tiểu PHAN HOÀNG NAM, TRẦN HOÀI NHÂN 120 3. CÁC THUẬT TOÁN CẢI TIẾN 3.1. Thuật toán dựa MCMF với chu trình  1 Như đã đề cập ở trên, tác giả trong [3] đã đề xuất hàm mục tiêu T và thêm ràng buộc dương vô cùng nếu tồn tại một bộ đọc chưa được phân phối thẻ. Thuật toán MCMF đã được đề xuất trong [3] thực hiện việc đổi luồng dọc theo chu trình xuất phát từ đỉnh phát s qua hai bộ đọc và một thẻ - sau khi đã tìm được luồng cực đại - để giảm giá trị hàm mục tiêu. Trong bài báo này chúng tôi đặt tên chu trình này là  1 và tên thuật toán đã được trình bày trong [3] là  1MCMF . Tại đây, chúng tôi thêm phần xử lý ràng buộc dương vô cùng vào thuật toán và trình bày lại như sau: Mạng G  U V , E Input: Output: Luồng cực đại f * sao cho hàm mục tiêu T nhỏ nhất có thể. Function  1MCMF () Tìm luồng cực đại f trong mạng G ; Tính giá trị hàm mục tiêu T theo công thức (3) ; do { foreach ui , uk  U do if ( v  V sao cho ui , v  , uk , v   E ) then if ( f (ui , v)  1 và f (uk , v)  0 và (đổi luồng làm giảm hàm mục tiêu T hoặc giảm số cung (s,u) có f s ,u  0 )) then cập nhật lại luồng f ; if ( f (ui , v)  0 và f (uk , v)  1 và (đổi luồng làm giảm hàm mục tiêu T hoặc giảm số cung (s,u) có f s ,u  0 )) then cập nhật lại luồng f ; } while (hàm mục tiêu T đã được cập nhật) ; return f ; Như vậy, thuật toán  1MCMF có thể giảm hàm mục tiêu T sau khi tìm được luồng cực đại, giúp phân phối thẻ vào các bộ đọc được cân bằng hơn [3]. Tuy nhiên, thuật toán chỉ phân phối lại thẻ cho hai bộ đọc bất kỳ có cùng thẻ; bởi vì, tất cả chu trình thay đổi luồng có dạng: f c 1 f 1  1  s    ui 0  v   uk  s  ui , uk U , v V  (4) CẢI TIẾN THUẬT TOÁN LUỒNG CỰC ĐẠI CÓ GIÁ TRỊ CỰC TIỂU... 121 Nên, nếu rơi vào trường hợp sau,  1MCMF không thể tiếp tục làm giảm được hàm mục tiêu T. Thật vậy, giả sử sau khi tìm được luồng cực đại ta có T  9.5 (Hình 4): 0 5|1 1 1 3|1 s 1 1 1 1 3|2 t 1 0 1 Hình 4. Trường hợp thuật toán MCMF không làm giảm hàm mục tiêu T Trong ví dụ ở Hình 4, thuật toán  1MCMF chỉ xét được 2 chu trình: f c f c 0 0 1 1 f 1 f 1 11  s     u2   u1   v1   v3   u2   u3  s và 21  s  s , các chủ trình đều không làm giảm hàm T. Nếu xét chu trình qua 2 thẻ như sau f c 0 1 0 1 f 1 s    u1   v1   u2   v3   u3  s làm giảm hàm T. Cụ thể, với chu trình mới T  8.5 cũng là giá trị nhỏ nhất (Hình 5) 0 5|2 1 1 3|1 s 1 1 0 1 1 3|1 t 1 1 Hình 5. Luồng mới có giá trị T đạt cực tiểu 3.2. Chu trình đổi luồng mới  k Từ ví dụ trên, chúng tôi đề xuất thuật toán dựa trên chu trình mới. Chu trình chứa k thẻ với k  1 và ký hiệu  k . Chu trình  k được định nghĩa như sau: f c 0 1 0 1 f 1  k  s   ui   vi  ...   vi  ui  s 1  k  m 1 1 k trong đó: ui j 0  vi j : (ui j , vi j )  E, fui j ,vi j vi j 1  ui j1 : (ui j1 , vi j )  E, fui j 1 0 ,vi j 1 k 1 (5) PHAN HOÀNG NAM, TRẦN HOÀI NHÂN 122 3.3. Thuật toán dựa trên MCMF với chu trình  k Trong bài báo này, chúng tôi đặt tên thuật toán mới là  k MCMF . Thuật toán được trình bày như sau: Input: Mạng G  U V , E Output: Luồng cực đại f * sao cho hàm mục tiêu T nhỏ nhất. Function  k MCMF () Tìm luồng cực đại f trên mạng G ; Tính giá trị hàm mục tiêu T theo công thức (3) ; do { foreach k  1..n do if (  k làm giảm hàm mục tiêu T) then { Cập nhật luồng dọc theo  k ; Cập nhật hàm T ; } else { if ( T   ) then if (  k làm giảm số cung (s,u) có f s ,u  0 ) then Cập nhật luồng dọc theo  k ; } } while (hàm mục tiêu T đã được cập nhật) ; return f ; 3.4. Chứng minh các tính chất của chu trình  k i. Chu trình  k chỉ phân phối lại số lượng thẻ cho 2 bộ đọc đầu và cuối của nó. Chứng minh: Chu trình  k có bộ đọc đầu tiên là ui1 và bộ đọc cuối cùng là uik 1 ; mỗi f 1 f 0 bộ đọc ui j còn lại có hai đỉnh lân cận vi j1 , vi j sao cho u j  v j 1 và u j   v j     . Nếu cập nhật luồng dọc theo  k thì ta có f ui j , vi j1  0 và f ui j , vi j  1 , nghĩa là số lượng thẻ đã phân bố cho bộ đọc ui j không thay đổi. Như vậy, tổng số thẻ mà các bộ đọc trên  k từ 2 tời k không thay đổi. CẢI TIẾN THUẬT TOÁN LUỒNG CỰC ĐẠI CÓ GIÁ TRỊ CỰC TIỂU... 123 ii. Chu trình  k không làm thay đổi tổng luồng ra khỏi s. Chứng minh: Với mọi chu trình làm thay đổi hàm T thì f s*,ui  f s*,uk  f s,ui  1  fs ,uk 1  fs ,ui  fs ,uk với ui , uk là hai bộ đọc đầu và cuối của chu trình. Như vậy, chu trình  k không làm thay đổi tổng luồng ra khỏi đỉnh phát s. iii. Mọi chu trình làm giảm hàm T đều có dạng  k . Chứng minh: Có hai trường hợp sau khi tìm được luồng cực đại f: (1) u  U : f s ,u  cs ,u và vV fv,t  m ; (2) u  U : f s ,u  cs ,u và  vV fv,t  m . Đối với trường hợp (1) thuật toán không cần phải tìm  k vì lúc này hàm T có giá trị nhỏ nhất. Đối với trường hợp (2), có thể có luồng cực đại mới làm thay đổi hàm T nên cần phải tìm chu trình thay đổi luồng. Lúc này chu trình cần tìm phải xuất phát từ đỉnh phát s và không thể đến đỉnh nguồn t bởi vì fv,t vV  1 . Vậy chu trình cần tìm phải có dạng  k . iv. Thuật toán  k MCMF không lặp vô hạn. Chứng minh: Thuật toán  k MCMF dừng tại hai trường hợp là hàm T đạt giá trị nhỏ nhất hoặc mọi chu trình  k được tìm xong. Bây giờ ta chỉ cần chừng minh hàm T sẽ giảm tời giá trị nhỏ nhất với số lần giảm là hữu hạn. Gọi f *s ,u uU là giá trị luồng từ s tới u khi hàm T đạt giá trị nhỏ nhất. Mỗi chu trình  k dịch chuyển f s ,u tời gần f s*,u một đơn vị và do f s ,u , f s*,u đều là số tự nhiên nên chắc chắn sau một số hữu hạn lần f s,u  f s*,u . Tính chất (i), (ii) và (iii) khẳng định tính đúng đắn của thuật toán  k MCMF . Tính chất (iv) khẳng định tính dừng của thuật toán  k MCMF . 3.5. Độ phức tạp giải thuật tính toán Thuật toán  k MCMF gồm hai giai đoạn độc lập nhau: (1) Tìm luồng cực đại và (2) Tìm các chu trình  k cho đến khi hàm T không thể giảm. - Độ phức tạp tính toán của giai đoạn (1) đã được chứng minh là   U V * E 2   m n  m n  3 2 2 3 - Độ phức tạp tính toán của giai đoạn (2) trong trường hợp xấu nhất: Do không biết trước giá trị nhỏ nhất của hàm T nên trường hợp xấu nhất của thuật toán là phải tìm mọi chu trình  k . Thấy rằng, trong  m 1 có chứa m2 các chu trình có ít thẻ hơn. Mặt khác, từ mỗi chu trình  m 1 đã tìm được có thể sinh ra chu trình  m 1 mới bằng cách thay thế m  1 thẻ cũ thành các m  1 thẻ mới. Trường hợp xấu nhất, có m2 * n * m chu trình  k cần tìm và việc đổi luồng dọc theo  k trong trường hợp này là duyệt qua m bộ đọc. PHAN HOÀNG NAM, TRẦN HOÀI NHÂN 124 Kết luận độ phức tạp tính toán của thuật toán  k MCMF :   m3n2  m2 n3  m4 n     m2 n(m  n)2  (6) 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ 4.1. Mục tiêu thực nghiệm Chúng tôi đã chứng minh được mọi chu trình đổi luồng làm giảm hàm mục tiêu T tại tính chất (iii) và nêu ra ví dụ thuật toán  1MCMF không làm giảm được hàm mục tiêu. Bây giờ, chúng tôi tiến hành thử nghiệm thực thế để so sánh hai thuật toán với mục tiêu sau: - Đánh giá khả năng làm giảm giá trị hàm mục tiêu của hai thuật toán  1MCMF và  k MCMF . - So sánh tốc độc chạy chương trình viết theo hai thuật toán:  1MCMF (1) và  k MCMF (2). Công thức so sánh thời gian: S Thêi gian ch¹y cña (1) trªn d÷ liÖu i - Thêi gian ch¹y cña (2) trªn d÷ liÖu i *100% 100 - Nếu S  0 : Thời gian chạy của chương trình 1 nhanh hơn 2, - Nếu S  0 : Thời gian chạy của hai chương trình bằng nhau, - Nếu S  0 : Thời gian chạy của chương trình 2 nhanh hơn 1. 4.2. Cách thức tiến hành - Chúng tôi cài đặt chương trình cho cả hai thuật toán cần so sánh. - Thực hiện chạy chương trình trên cùng một hệ thống máy tính. - Các bộ dữ liệu dùng so sánh được chúng tôi tạo ra với như sau: Kích thước 1 R=3,T=4 Bảng 1. Mô tả các bộ dữ liệu dùng để so sánh Phân bố thẻ Năng lượng của mỗi bộ đọc (Số thẻ mỗi bộ đọc có thể giao tiếp) N1  2 , N 2  2 , N3  2 B1  5 , B2  3 , B3  3 2 R=4,T=5 N1  2 , N 2  2 , N3  2 , N 4  2 B1  6 , B2  5 , B3  3 , B4  3 3 R=6,T=10 N1  2 , N 2  2 , B3  2 , N 4  2 , B1  10 , B2  9 , B3  9 , B4  4 , N5  3 , N6  2 B5  4 , B6  3 N1  2 , N 2  2 , B3  2 , N 4  2 , B1  10 , B2  9 , B3  9 , B4  4 , N5  2 , N6  2 B5  4 , B6  3 5 R=7,T=22 Ngẫu nhiên Ngẫu nhiên 6 R=8,T=24 Ngẫu nhiên Ngẫu nhiên 7 R=10,T=50 Ngẫu nhiên Ngẫu nhiên 8 R=50,T=71 Ngẫu nhiên Ngẫu nhiên 4 R=6,T=9 CẢI TIẾN THUẬT TOÁN LUỒNG CỰC ĐẠI CÓ GIÁ TRỊ CỰC TIỂU... 125 5. KẾT QUẢ Bảng 2. Số thẻ tối đa được phân phối cho các bộ đọc  1MCMF  k MCMF Đạt mức Dữ liệu 1 4 Dữ liệu 2 5 Dữ liệu 3 10 Dữ liệu 4 9 Dữ liệu 5 22 Dữ liệu 6 44 Dữ liệu 7 71 4 5 10 9 22 44 71 100% 100% 100% 100% 100% 88% 100% 0.060 0.070 0.083 0.069 0.132 0.161 0.173 0.230 0.054 -0.01% Thời gian chạy của thuật toán 1 trên các bộ dữ liệu 0.0740 0.075 0.0810 0.155 0.130 0.132 0.224 0.00% -0.01% 0.01% 0.02% -0.03% -0.04% -0.01% GIÁ TRỊ HÀM MỤC TIÊU Thời gian chạy của thuật toán 2 trên các bộ dữ liệu Bảng 3. Tốc độ chạy chương trình của hai thuật toán 40.00 35.00 30.00 25.00 20.00 15.00 10.00 5.00 0.00 R=3 T=4 R=4 T=5 R=6 T=10 R=6 T=9 R=7 R=8 R=10 R=50 T=22 T=24 T=50 T=71 1 9.50 15.50 23.00 28.00 29.00 30.39 31.39 34.00 2 8.50 14.00 23.00 25.00 26.00 27.40 29.19 33.40 Biểu đồ 1. Giá trị hàm mục tiêu T đạt được của thuật toán 1:  1MCMF , 2 :  k MCMF Phân tích kết quả: - Biểu đồ 1: Cho thấy giá trị hàm mục tiêu đạt được bởi thuật toán 2 luôn bé hơn hoặc bằng thuật toán 1. - Bảng 2: Cho thấy số lượng thẻ phân phối cho các bộ đọc của hai thuật toán đều bằng nhau. PHAN HOÀNG NAM, TRẦN HOÀI NHÂN 126 - Bảng 3: Cho thấy tốc thực tế của hai chương trình không chệnh lệch nhau. Từ đây chúng tôi có thể khẳng định, trong trường hợp số lượng thẻ và số lượng bộ đọc lớn hơn (thực tế số lượng thẻ luôn lớn hơn rất nhiều số bộ đọc) hai chương trình tốc độ chạy tương đương nhau, bởi vì độ phức tạp tính toán cũa hai thuật toán đều bằng với độ phức tạp tính toán của bước tìm luồng cực đại. 4. KẾT LUẬN Dựa vào phản ví dụ được thể hiện tại Hình 4, các tính chất của thuật toán  k MCMF đã được chứng minh và kết quả so sánh thực nghiệm theo hai thuật toán tại Biểu đồ 1, chúng tôi kết luận rằng: Thuật toán  k MCMF tối ưu được hàm mục tiêu T hơn so với thuật toán  1MCMF mà vẫn phân phối được tối đa số thẻ cho các bộ đọc. Chúng tôi sẽ tiếp tục nghiên cứu thay đổi hàm mục tiêu T để có thể giảm được ràng buộc dương vô cùng trong trường hợp tốn tại f s ,u  0 và cải tiến thuật toán  k MCMF nhằm giảm độ phức tạp tính toán của nó. TÀI LIỆU THAM KHẢO [1] [2] [3] [4] [5] [6] [7] Qunfeng Dong et al. Load Balancing in Large-Scale RFID Systems. 0743-166X/07 © 2007 IEEE. Qunfeng Dong et al. Load Balancing in Large-Scale RFID Systems. This is an extended version of a paper that appeared in IEEE Infocom 2007: Minisymposium on Wireless Networks, Anchorage, Alaska, USA, May 2007. Phan Hoàng Nam. Tìm hiểu phương pháp cân bằng tải trong hệ thống RFID. Luận văn Thạc sĩ, Chuyên ngành Công nghệ thông tin, Trường Đại học Khoa học, Đại học Huế 2017. Vijayakumar G. Dhas et al. Effective Load Balancing with Power Conservation in RFID. International Journal of UbiComp (IJU), Vol.1, No.4, October 2010. Vijayakumar G. Dhas et al. Optimal Solution for RFID Load Balancing. N. Meghanathan et al. (Eds.): NeCoM, WiMoN, and WeST 2010, CCIS 90, pp. 41–49, 2010 © SpringerVerlag Berlin Heidelberg 2010. J. Erickson. Maxflow Extensions Lecture Notes. UIUC, Fall 2013. L.R. Ford and D.R. Fulkerson. Maximal Flow Through a Network. Canadian Journal of Mathematics 8.3 (1956): 399-404. Tilte: IMPROVE ALGORITHM WITH MINIMUM COST AND MAXIMUM FLOW FOR METHOD MTA Abstract: Radio Frequency Identification (RFID) which has reseached since 1960 is a shortrange radio technology to collect data automatically. Two solutions were proposed in 2007 to balance load problem in RFID system were Min-Max Cost Assignment (MCA) and Min-Max Tag Count Assignment (MTA) [1]. MTA was a special case of MCA. Qunfeng Dong et al
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.