1. MỘT CẢI TIẾN PHÂN CỤM RFID ĐỘNG NHẰM LỌC DỮ LIỆU HIỆU QUẢ NĂNG LƯỢNG Võ Viết Minh Nhật1, Lê Văn Hòa1, Huỳnh Quốc Phương2, Nguyễn Văn Tùng3 1 Đại học Huế 2 Khoa CNTT, Đại học An Giang 3 Khoa CNTT, Đại học Công nghệ Thực phẩm – TP. Hồ Chí Minh Tóm tắt: Lọc dữ liệu trong mô hình tích hợp ánh sáng, âm thanh hay các rung động … mà phù hợp nhận dạng đối tượng bằng sóng vô tuyến (RFID) với cho việc thu thập thông tin [3]. Các nút cảm biến còn mạng cảm biến (SN) là một vấn đề thời sự đang thu có khả năng tính toán và cho phép xử lý các thông tin thu thập được. Thông tin này sau đó được chuyển đến hút nhiều sự quan tâm của các nhà nghiên cứu trên thế các trạm cơ sở. Mạng cảm biến cung cấp cơ chế giám giới. Một trong những hướng tiếp cận về lọc dữ liệu sát chi phí hiệu quả cho các ứng dụng quan trọng, bao hiệu quả năng lượng là dựa trên phân cụm trong đó gồm các ứng dụng giám sát biên giới, hải đảo, điều các điểm lọc dữ liệu chỉ được thực hiện bởi các nút khiển hoạt động trong các nhà máy công nghiệp, giám chủ cụm. Tuy nhiên, đa số các đề xuất đều xem xét sát môi trường, quân sự và cả các ứng dụng về y tế, du trong môi trường mà ở đó các đầu đọc được giả sử là lịch. không di chuyển và vai trò chủ cụm là cố định tại một nút. Điều này làm cho các chủ cụm tiêu tốn quá nhiều Với công nghệ RFID, nó cho phép phát hiện và năng lượng, mà kết quả là thời gian sống của chúng nhận diện các đối tượng trong một môi trường. Một hệ giảm nhanh. Bài viết này sẽ đề xuất một cải tiến về thống RFID bao gồm các thiết bị (reader) đọc dữ liệu phân cụm động đối với các đầu đọc RFID trong đó từ các thẻ (tag) như Hình 1. Một thẻ bao gồm một chip và một ăng ten được gắn trên một đối tượng mục tiêu việc phân cụm được thực hiện lại một cách định kỳ và cần đọc. Thông tin thu thập được bằng cách các thiết vai trò chủ cụm được thay đổi một cách linh hoạt giữa bị đọc quét qua các thẻ và sau đó truyền thông tin đọc các nút sao cho năng lượng được tiêu thụ được chia sẻ được đến server ở trạm cơ sở. Các ứng dụng của RFID hợp lý giữa chúng và do đó làm tăng thời gian sống đã được phát triển khá nhiều trong thời gian gần đây của toàn hệ thống. như trong quản lý chuỗi cung ứng, thu phí đường cao tốc, quản lý giao thông, phát triển nhà thông minh… Từ khóa: Tích hợp RFID với SN, lọc dữ liệu, hiệu [4]. quả năng lượng, phân cụm động. I. GIỚI THIỆU Tích hợp công nghệ nhận dạng đối tượng theo tần số vô tuyến (Radio Frequency Identification - RFID) [1] với mạng cảm biến (Sensor Networks - SN) [2] đang là một xu thế hiện nay bởi nó có một phạm vi ứng dụng rộng rãi và đa dạng mà ở đó những ưu điểm của cả hai công nghệ được khai thác và sử dụng. Mô hình tích hợp này đã tạo ra một cơ sở hạ tầng tuyệt vời để xử lý và phân phối dữ liệu trong môi trường động, được phân cấp. Tuy nhiên, mô hình tích hợp cũng đối mặt với nhiều thách thức trong đó việc làm giảm dữ liệu dư thừa là hết sức phức tạp vì nó còn đi kèm với Hình 1. Mô hình phủ sóng chồng lấp của các đầu đọc các yếu tố như độ trể truyền thông, năng lượng tiêu thụ RFID đối với các thẻ và lãng phí các loại tài nguyên khác. Công nghệ RFID đã được chấp nhận trong nhiều Về cơ bản, mạng cảm biến là một mô hình mạng ứng dụng công nghiệp, trong khi mạng cảm biến có gồm nhiều nút sink hay còn được gọi là trạm cơ sở thể phát hiện thông tin trong các điều kiện môi trường (base station) và nhiều nút cảm biến có kích thước bé, khắc nghiệt. Tuy nhiên, cũng có nhiều ứng dụng mà trọng lượng nhỏ. Các nút cảm biến có thể cảm nhận thông tin thu thập từ môi trường là không đủ để xử lý; điều kiện môi trường như: nhiệt độ, độ ẩm, áp suất, Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 17
  2. do đó việc xác định thêm thông tin như vị trí của đối toàn hệ thống. Cách tiếp cận này được thể hiện dưới tượng là hết sức cần thiết [3]. Việc sử dụng mạng cảm dạng cấu trúc cây theo nguyên tắc định tuyến đa chặng biến cho các ứng dụng về môi trường, quản lý các (multi-hops), trong đó các nút cha sẽ đóng vai trò nút điểm danh lam thắng cảnh… đang là một xu thế của lọc trong khi các nút con phát hiện sự trùng lặp dữ du lịch thông minh. Trong trường hợp này mô hình liệu. Như được chỉ ra trong Hình 2, nút A và M cùng tích hợp RFID với mạng cảm biến là giải pháp tối ưu, đọc dữ liệu ở vùng chồng lấp “x” và sau đó truyền dữ trong đó chúng vừa bổ sung, hỗ trợ cho nhau [4]. liệu đến trạm cơ sở qua nhiều chặng. Trong [6], việc lọc dữ liệu được đề xuất ở khoảng cách k chặng (trong Tuy nhiên, mô hình tích hợp cũng đối mặt với Hình 2 thì k = 3) và x được truyền theo 2 hành trình nhiều thách thức khác nhau như: xác định hiệu suất được định tuyến khác nhau để đến nút D. Nút D lúc thời gian thực, hiệu quả năng lượng, lọc dữ liệu dư này đóng vai trò nút lọc dữ liệu và sẽ loại bỏ bớt một thừa, chống va chạm (anti-collision) và hiệu quả xác bản sao trước khi chúng được gửi đến trạm cơ sở. thực [5]. Trong số các thách thức trên thì vấn đề lọc dữ liệu để vừa làm sạch dữ liệu và vừa hiệu quả năng lượng là một vấn đề quan trọng nhằm sử dụng hiệu quả các nguồn tài nguyên mạng, giảm tiêu thụ năng lượng [5]. Trong một hệ thống RFID, thiết bị đọc thường xuyên kiểm tra các thẻ nhiều lần để tăng tốc độ đọc. Điều này đã tạo ra nhiều bản sao về một đối tượng duy nhất, mà dẫn đến thừa dữ liệu tại các đầu đọc cùng đọc một thẻ. Như được chỉ ra trong Hình 1, vấn đề trùng lặp dữ liệu sẽ xuất hiện ở các đầu đọc R2, R3 và R4 vì cùng đọc thẻ T3. Thực tế việc dư thừa dữ liệu do 2 nguyên nhân chính: (1) một thẻ được bao phủ bởi nhiều đầu đọc (như thẻ T3) và (2) đầu đọc đọc thẻ nhiều lần nên tạo ra nhiều các bản sao không cần thiết. Việc loại bỏ các dư thừa này là cần thiết vì nó không đem lại bất kỳ một thông tin hữu ích nào. Việc loại bỏ dư thừa góp phần sử dụng hiệu quả Hình 2. Lọc dữ liệu theo phương pháp INPFM [6] các nguồn tài nguyên hơn. Quá trình lọc và loại bỏ các thông tin dư thừa, được gọi là là quá trình làm sạch dữ Trong [7], Kim và cộng sự đã đề xuất phương pháp liệu (data cleaning). Cụ thể, loại bỏ dữ liệu dư thừa là CLIF (Cluster-based In-network phase Filtering một quá trình thay thế, sửa đổi hoặc xóa những phần scheme) dựa trên phân cụm và việc lọc dữ liệu được không liên quan, không chính xác hoặc không chính xảy ra tại nút chủ cụm (Cluster Head). Cụ thể, các nút xác một phần. Hầu hết các vấn đề loại bỏ dữ liệu dư gần nhau được gom thành một cụm và một nút được thừa đều tập trung vào phương pháp phân cụm. Việc chọn để đóng vai trò chủ cụm. Nút chủ cụm sẽ chịu phân cụm sẽ hạn chế các điểm lọc, do chỉ có nút chủ trách nhiệm lọc dữ liệu cho cụm. Như được chỉ ra cụm mới chịu trách nhiệm lọc; do đó tiết kiệm được trong Hình 3, có 2 cụm A và B. Dữ liệu thuộc cụm A năng lượng trong quá trình lọc. Tuy nhiên do nút chủ sẽ được lọc bởi nút chủ cụm A, nhưng dữ liệu nằm cụm lọc dữ liệu nên nó sẽ phải tiêu tốn năng lượng lớn trong vùng chồng lấn của 2 cụm A và B sẽ được lọc hơn; kết quả là có thời gian sống ít hơn. Hơn nữa, việc bởi một nút chủ cụm trung gian. Nút chủ cụm này sẽ phân cụm chưa được xem xét trong môi trường mà các phát hiện sự trùng lắp dữ liệu (tức là nhận được từ 2 nút di chuyển tự do. Bài báo này sẽ đề xuất một giải bản sao trở lên). pháp phân cụm động các đầu đọc RFID nhằm nâng cao hiệu quả về năng lượng đối với việc lọc dữ liệu và do đó tăng thời gian sống của toàn hệ thống. Các phần tiếp theo của bài báo được tổ chức như sau: Phần 2 tóm lược và phân tích các công trình nghiên cứu liên quan. Trên cơ sở các đánh giá, Phần 3 trình bày mô hình lọc dữ liệu hiệu quả năng lượng được đề xuất. Cài đặt mô phỏng và phân tích kết quả sẽ được mô tả ở Phần 4. Cuối cùng kết luận ở Phần 5. II. CÁC ĐỀ XUẤT VỀ LÀM SẠCH DỮ LIỆU Lọc dữ liệu là một vấn đề quan trọng trong mạng cảm biến không dây tích hợp với RFID. Các ứng dụng dựa trên mô hình tích hợp này thường chỉ quan tâm đến một bản dữ liệu duy nhất, nhưng việc trùng lắp dữ liệu trong khi đọc đã tạo ra nhiều các bản sao không mong muốn. Hình 3. Lọc dữ liệu theo phương pháp CLIF [7] Wonil và cộng sự trong [6] đã đề xuất kỹ thuật INPFM (In-Network Phased Filtering Mechanism) Bashir và cộng sự trong [8] đã đề xuất sơ đồ EIFS trong đó dữ liệu chỉ được lọc ở nút thứ k vì họ cho (Energy efficient In-network RFID data Filtering rằng lọc dữ liệu tại tất cả các nút sẽ gây chậm trể trên Scheme), trong đó trùng lặp dữ liệu cũng được chia Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 18
  3. thành hai loại là nội cụm và liên cụm. Việc lọc đối với gọi là DCDF (Dynamic Clustering-based in-network hai loại này cũng được thực hiện tách biệt tương tự Data Filtering) và được trình bày trong Mục III.D. như trong CLIF. Tuy nhiên, sau khi nhận được dữ liệu, chủ cụm sẽ xác định loại trùng lặp dựa trên giá trị B. Phương pháp phân cụm các đầu đọc di chuyển trường f được lưu trong cấu trúc của gói dữ liệu. Nếu Giải thuật phân cụm được chúng tôi đề xuất có tên giá trị của trường f là 1, nút gửi được xác định là nút gọi là CMR (Clustering Moving Readers) dựa trên ý nội cụm và chủ cụm sẽ thực hiện việc lọc dữ liệu. Sau tưởng như sau. Bước 1, các đầu đọc được phân cụm khi việc lọc dữ liệu đã thực hiện xong, giá trị trường f bằng phương pháp K-mean [10]; một danh sách các được thiết lập bằng 0. Như vậy, chủ cụm sẽ không lọc đầu đọc di chuyển được lưu lại sau từng khoảng thời các gói tin có f = 0 và do đó làm giảm đáng kể chi phí gian (tương tự như vấn đề đọc dữ liệu của đầu đọc). tính toán. Sau bước lọc dữ liệu nội cụm, các chủ cụm Bước 2, khoảng cách từ mỗi đầu đọc di chuyển đến gửi dữ liệu của chúng về phía trạm cơ sở. Trong các tâm cụm được tính toán; một đầu đọc sẽ được trường hợp lọc dữ liệu liên cụm, EIFS đầu tiên sẽ tìm phân vào một cụm mới nếu khoảng cách từ nó đến tâm và phát hiện dữ liệu trùng lặp liên cụm. Nếu có dữ liệu cụm mới là bé nhất. Cụ thể, 2 bước của phương pháp trùng lặp được phát hiện, các chủ cụm trung gian sẽ CMR là như sau: gửi một thông tin phản hồi để thông báo cho các chủ cụm nơi sinh ra các gói dữ liệu trùng lặp tránh việc Bước 1: Xác định danh sách các đầu đọc di chuyển truyền gói không cần thiết. Với mỗi đầu đọc, tọa độ của nó được duy trì bởi Bashir và cộng sự trong [9] tiếp tục mở rộng EIFS một vector Ri(xi,yi), i = 1..N trong đó N là số lượng các thành giải thuật có tên gọi là IRDF (In-network RFID đầu đọc. Với một mạng cảm biến được triển khai, vị Duplicate data Filtering), trong đó việc lọc nội cụm trí của các đầu đọc là được xác định một cách dễ dàng. được tiến hành với phương pháp EIFS, nhưng việc lọc Dựa trên các toạ độ này, các đầu đọc được phân cụm ngoại cụm được tiến hành tại những cụm lân cận, thay dựa trên giải thuật K-mean. Mỗi khi có thay đổi vị trí vì tại nút chủ cụm trung gian như trong EIFS. Một (xi,yi) sau từng khoảng thời gian cố định, đầu đọc Ri khác biệt khác của IRDF là loại bỏ cơ chế phản hồi được đưa vào một danh sách cần phân cụm lại (như thông tin vì nó cho rằng việc làm này làm gia tăng độ được mô tả từ dòng 4 đến 10 trong giải thuật CMR). trễ của quá trình truyền dữ liệu. Bước 2: Phân bổ đầu đọc di chuyển vào cụm mới Tóm lại, các phương pháp nêu trên đã loại bỏ được Với mỗi đầu đọc Ri nằm trong danh sách cần phân đa số dữ liệu dư thừa trước khi được truyền đến trạm cụm lại, khoảng cách Euclidien từ nó đến các tâm cụm cơ sở. Tuy nhiên vẫn tồn tại 4 vấn đề sau: (1) nút chủ được tính toán lại. Đặt D(i,j) là khoảng cách từ Ri đến cụm phải chịu hao tốn năng lượng đáng kể vì lọc dữ tâm cụm j. Ri được phân vào cụm j nếu D(i,j) là bé liệu; (2) nếu nút chủ cụm không nằm trên tuyến đường nhất (như được mô tả từ dòng 13 đến 25 trong giải được định tuyến đến trạm cơ sở, các nút có dữ liệu thuật CMR). Lưu ý rằng tâm cụm j thay đổi một cách trùng lặp phải chuyển hướng đến nút này; điều này động và giải thuật xác định tâm cụm động được mô tả làm tăng độ dài hành trình và dẫn đến chậm trễ trong trong Mục III.C. việc lọc dữ liệu; (3) khi dữ liệu đến nút chủ cụm lớn, nó có khả năng rơi vào tình trạng quá tải; (4) các đầu Sau đây là mô tả chi tiết của giải thuật CMR: đọc và thẻ được giả thiết là cố định, trường hợp chúng Giải thuật CMR (Clustering Moving Readers) di chuyển chưa được xem xét đến. Đề xuất sau đây Input: của chúng tôi sẽ giải quyết 4 vấn đề này. - danh sách các đầu đọc đã phân cụm C ={Cj| j=1..K}, Cj = {Ri| i=1..m} và 0
  4. 15 temp ← ∞ ; 7 end if 16 while (j ≤ K) do 8 i++; 17 if (euclidien(Rt, ccj) < temp) then 9 end while 18 temp ← euclidien(Rt, ccj); 10 i ← 1; // lưu vị trí tâm cụm có khoảng cách bé nhất 11 t ← 0; 19 min ← j; 12 while (i ≤ n) do 20 end if // kiểm tra mức năng lượng của các đầu đọc 21 j++; 13 if (Ei > max_energy - ∆E) then 22 end while // DS các đầu đọc có khả năng làm chủ cụm // phân bổ Rt vào cụm có khoảng cách bé nhất 14 list_energy ← Ri; 23 Cmin ← Rt; // số lượng đầu đọc có khả năng làm chủ cụm 15 t++; 24 t++; 16 end if 25 end while 17 i++; Độ phức tạp của giải thuật là O(r×K) với r là số 18 end while lượng các đầu đọc di chuyển và K số cụm trong hệ 19 min ← ∞; thống. 20 i ← 1; 21 temp ← ∅; C. Phương pháp xác định lại tâm cụm 22 while (i ≤ t) do Việc xác định tâm cụm là quan trong vì nó phải // so sánh số nút trung gian của các nút có khả năng chịu trách nhiệm lọc dữ liệu. Phương pháp xác định lại làm chủ cụm, trong đó count(Ri) số nút trung gian tâm cụm mà chúng tôi đề xuất, có tên gọi là CCR để đến được trạm cơ sở của đầu đọc Ri (Cluster Center Recomputing), dựa trên 2 tiêu chí: (1) 23 if (count(Ri) < min) then năng lượng hiện tại của nút trong cụm; (2) nằm trên 24 temp ← Ri; hành trình định tuyến đến trạm cơ sở. Quá trình xác 25 min ← count(Ri); định lại tâm cụm được chia thành 2 bước: 26 end if Bước 1: Xác định danh sách các đầu đọc tiềm 27 i++; năng 28 end while Năng lượng hiện tại của các đầu đọc trong một 29 cc ← temp; // xác định tâm cụm cụm được so sánh để xác định một danh sách các đầu đọc tiềm năng làm chủ cụm (từ dòng 12 đến dòng 18 Độ phức tạp của giải thuật CCR là O(n) với n là số trong giải thuật CCR). Danh sách này gồm các đầu các đầu đọc trong một cụm. đọc có mức năng lượng cao nhất và có độ lệch không vượt quá một giá trị ∆E được xác định trước. ∆E được D. Mô hình lọc dữ liệu hiệu quả năng lượng gọi là khoảng chênh lệch năng lượng tiềm năng giữa các nút; nó cần đủ nhỏ để không gây chênh lệch quá Đầu tiên chúng tôi sử dụng phương pháp phân cụm lớn giữa các mức năng lượng trong danh sách. K-mean (từ dòng 2 đến 6 trong giải thuật DCDF) để phân bổ các đầu đọc tương ứng vào từng các cụm. Sau Bước 2: Xác định lại tâm cụm từng khoảng thời gian cố định chúng tôi sử dụng giải Các đầu đọc tiềm năng trong danh sách được xem thuật CCR dòng 8 để xác định lại các tâm cụm và sử xét về khả năng định tuyến đến trạm cơ sở, trong đó dụng giải thuật CMR dòng 9 để phân các đầu đọc di đầu đọc được chọn là đầu đọc đi qua ít nút trung gian chuyển vào các cụm mới. nhất để đến trạm cơ sở (như được mô tả từ dòng 22 Giải thuật DCDF được mô tả chi tiết như sau: đến dòng 29 trong giải thuật CCR). Giải thuật DCDF (Dynamic Clustering-based in-network Giải thuật xác định lại tâm cụm CCR được mô tả Data Filtering) chi tiết như sau: Input: - danh sách các đầu đọc Ri(xi, yi), i = 1..N; Giải thuật CCR (Cluster Center Recomputing) - số cụm K; khoảng thời gian xác định tâm cụm t; thời Input: gian kết thúc mô phỏng tend; - danh sách các đầu đọc trong một cụm Ri(xi, yi), i = 1..n; - năng lượng các đầu đọc Ei, i = 1..N; - năng lượng các đầu đọc Ei, i = 1..n; - độ lệch năng lượng ∆E. - độ lệch năng lượng ∆E. Output: Output: - năng lượng trung bình của các nút chủ cụm HE - tâm cụm cc. Process: Process: 1 HE ← 0; 1 i ← 1; 2 Khởi tạo K cụm {ccj; j = 1..K}; 2 list_energy ← ∅; // nếu có sự thay đổi giá trị tâm 3 max_energy ← ∅; 3 while (change(ccj) // Cj tập các đầu đọc trong cụm j, j*≠ j và j*=1..K 4 while (i ≤ n) do 4 Cj ← {Ri| euclidien(Ri, ccj) ≤ euclidien(Ri, ccj*)}; 5 if (Ei > max_energy) then // xác định lại tâm cụm theo K-mean và // xác định mức năng lượng cao nhất trong cụm average(Ri) giá trị trung bình của các đầu đọc 6 max_energy ← Ei; 5 trong cụm j, tâm cụm là nút gần với giá trị trung Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 20
  5. bình nhất. Tham số Giá trị ccj ← average(Ri | Ri ∈ Cj); Vùng mô phỏng 100x100m2 6 end while 7 while (t < tend) Số lượng đầu đọc 101 8 call(CCR);// gọi giải thuật CCR 9 call(CMR);// gọi giải thuật CMR Số lượng cụm 5, 7, 9 10 end while // xác định năng lượng trung bình của các tâm cụm Năng lượng ban đầu của đầu đọc 2KJ 11 HE ← average(ccj); Độ lệch năng lượng ∆E 0.1KJ E. Ví dụ minh họa Thời gian xác định phân cụm lại 1s Với việc xác định chủ cụm một cách động, phương Thời gian mô phỏng 10s pháp DCDF đảm bảo thích ứng được với những di chuyển ngẫu nhiên của các đầu đọc, giúp việc chọn chủ cụm hợp lý và cân bằng năng lượng tiêu thụ của Các mục tiêu mô phỏng bao gồm: các đầu đọc trong mạng. Hơn nữa, phương pháp - Xem xét ảnh hưởng của việc thay đổi số cụm K DCDF cũng giúp việc truyền dữ liệu nhanh hơn vì đến năng lượng trung bình của các đầu đọc; tuyến đường được chọn đi qua ít nút trung gian nhất. - So sánh hiệu quả năng lượng của giải thuật DCDF so với IRDF. A. Ảnh hưởng của số cụm đến năng lượng trung bình của các đầu đọc Chúng tôi tiến hành thay đổi số cụm K từ 5 đến 7 và 9 để xem xét ảnh hưởng của số cụm đến mức tiêu hao năng lượng trung bình của các đầu đọc trong cụm. Kết quả thu được như Hình 5, ở đó chúng ta nhận thấy rằng năng lượng trung bình của các đầu đọc giảm khi số cụm tăng. Điều này có được là do khi tăng số cụm thì số điểm lọc dữ liệu và số điểm truyền dữ liệu tăng lên dẫn đến việc mất mát nhiều dữ liệu hơn. Hình 4. Một ví dụ về phân cụm lại khi các đầu đọc di chuyển (với số cụm K=4) Để làm rõ hơn vấn đề này hãy xem xét một ví dụ như trong Hình 4, trong đó các đầu đọc được phân cụm theo thuật toán K-mean. Có 4 cụm được hình thành với các tâm lần lượt là C1, C2, C3 và C4 (những đường tròn đứt nét). Sau từng khoảng thời gian cố định, một số tâm cụm được xác định lại (theo giải thuật CCR), như trong Hình 4 là C2 và C3 (được thể hiện bằng các đường tròn liền nét). Khi các đầu đọc di chuyển chúng được đưa vào một danh sách cần phân Hình 5. Mức tiêu hao năng lượng trung bình của các cụm lại (theo giải thuật CMR) sau từng khoảng thời đầu đọc khi thay đổi số cụm gian xác định. Các đầu đọc vẫn có thể thuộc cụm ban đầu (chẳng hạn r2) nhưng cũng có thể chuyển sang Để xem xét ảnh hưởng của số cụm đến mức năng cụm mới (chẳng hạn r1). lượng của các nút chủ cụm, chúng tôi tiến hành so sánh năng lượng trung bình của các nút chủ cụm khi IV. MÔ PHỎNG VÀ PHÂN TÍCH KẾT QUẢ số cụm thay đổi; Kết quả thu được như Bảng II. Chúng tôi tiến hành cài đặt mô phỏng trên máy tính Bảng II. Mức tiêu hao năng lượng trung bình của các nút chủ cụm khi số cụm thay đổi (đơn vị KJ) 2.4 GHz Intel Core 2 CPU, 2G RAM. Các tham số mô phỏng được mô tả trong Bảng I, với 101 đầu đọc Thời gian (s) 2 4 6 8 10 trong có 1 đầu đọc đóng vai trò là trạm cơ sở. Các đầu đọc di chuyển ngẫu nhiên trong vùng bán kính là DCDF (K=5) 1.916 1.800 1.700 1.600 1.498 100x100m2; mức năng lượng ban đầu của các đầu đọc DCDF (K=7) 1.860 1.720 1.580 1.434 1.303 là 2KJ (Kilo Jun); số lượng các cụm theo K-mean thay đổi từ 5, 7, 9 cụm. Định kỳ 1s chúng tôi tiến DCDF (K=9) 1.820 1.640 1.456 1.276 1.105 hành xác định lại tâm cụm theo giải thuật CCR và phân cụm lại các đầu đọc theo giải thuật CMR. Rõ ràng, việc tăng số cụm không chỉ ảnh hưởng đến mức tiêu hao năng lượng của các đầu đọc trong Bảng I. Các tham số mô phỏng cụm mà còn gây ảnh hưởng đến các nút chủ cụm. Do trong chính sách của chúng tôi luôn sử dụng nút chủ Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 21
  6. cụm thay đổi nhằm bảo toàn năng lượng nên nút chủ Bảng III. Phân bố các đầu đọc trong mỗi cụm theo cụm luôn là nút có mức năng lượng cao hơn so với thời gian, khi các đầu đọc và thẻ di chuyển (trường hợp K=5) mức năng lượng trung bình của các đầu đọc trong cụm như chỉ ra ở Hình 6. Thời gian (s) 2 4 6 8 10 Cụm 1 16 11 19 17 23 Cụm 2 19 34 15 47 34 Cụm 3 25 21 32 6 12 Cụm 4 14 10 9 19 19 Cụm 5 26 24 25 11 12 V. KẾT LUẬN Trong bài báo này chúng tôi đã đề xuất một Hình 6. So sánh năng lượng trung bình nút chủ cụm phương pháp phân cụm RFID động nhằm lọc dữ liệu và các nút trong cụm khi K=5 hiệu quả năng lượng có tên là DCDF. Giải thuật DCDF bao gồm 2 giải thuật chính: (1) CMR nhằm B. So sánh hiệu quả năng lượng giữa DCDF và phẩn bổ các đầu dọc di chuyển vào các cụm mới và (2) IRDF CCR nhằm tính toán lại nút đóng vai trò là chủ cụm sau từng khoảng thời gian xác định. Kết quả mô Chúng tôi tiếp tục so sánh năng lượng trung bình phỏng trong Mục 4 đã chỉ ra rằng phương pháp mà của các nút chủ cụm khi K=5 giữa giải thuật DCDF chúng tôi đề xuất cho hiệu quả năng lượng tốt hơn và IRDF; Kết quả thu được như Hình 7. IRDF. Đồng thời DCDF cũng phù hợp với yêu cầu thực tế của các mô hình tích hợp RFID với mạng cảm biến mà ở đó các đầu đọc và các thẻ có thể tự do di chuyển. TÀI LIỆU THAM KHẢO [1] A. S. Korotkov. “Radio frequency identification systems: Survey,” Radio electronics and Communications Systems, vol. 59, no. 3, pp. 97-108, 2016. [2] Kamal D. Singh, Hakima Chaouchi, Jean M. Bonnin. “Wireless sensor networks: a survey on recent developments and potential synergies,” The Journal of Super computing, vol. 68, no. 1, pp. 1-48, 2014. Hình 7. So sánh năng lượng trung bình của các nút chủ cụm khi K=5 giữa DCDF và IRDF [3] Fadi M. Al-Turjman, Ashraf E. Al-Fagih1 and Hossam S. Hassanein, “A Novel Cost-Effective Architecture Từ Hình 7 chúng ta nhận thấy rằng giải thuật IRDF and Deployment Strategy for Integrated RFID and WSN Systems”, In: International Conference on tiêu hao năng lượng diễn ra nhanh hơn, điều này là do Computing, Networking and Communications, giải thuật IRDF không luân phiên sử dụng các nút chủ Network Architecture P2P Protocol Symposium, 2012. cụm, làm cho nút chủ cụm tiêu tốn năng lượng nhiều [4] Hai Liu, Miodrag Bolic, Amiya Nayak and Ivan hơn. Chẳng hạn, tại thời điểm 2s IRDF giảm năng Stojmenovic, “Taxonomy and Challenges of the lượng trung bình khoảng 7.8% so với DCDF, trong Integration of RFID and Wireless Sensor Networks,” khi tại 10s việc giảm năng lượng này là 50%. Với IEEE Network, vol. 22, no.6, pp.26-35, November- December 2008. trường hợp tăng số cụm lên 7 và 9, các kết quả Hình 5 và Hình 7 có thể giúp suy ra rằng IRDF sẽ làm giảm [5] Li Wang, Li Da Xu. “Data Cleaning for RFID and nhanh chóng năng lượng trung bình và thời gian sống WSN Integration,” IEEE Transactions On Industrial Informatics, vol. 10, no. 1, February 2014. của toàn hệ thống sẽ bị ảnh hưởng nghiêm trọng. [6] Choi. W., Park. M.S. “In-network Phased Filtering C. Nhận xét Mechanism for a Large-Scale RFID Inventory Application,” In: Proceedings of the 4th International Do giải thuật DCDF sử dụng phương pháp lọc dữ Conference on IT & Applications (ICITA), Harbin liệu như IRDF nên lượng dữ liệu truyền đến trạm cơ China (January 2007) pp. 401-405. sở không có nhiều thay đổi. Tuy nhiên, dựa trên kết [7] Kim. D.S., Kashif. A., Ming. X., Kim. J.H., Park. M.S. quả mô phỏng, DCDF là hiệu quả trong việc bảo toàn “Energy Efficient In-Network Phase RFID Data năng lượng, khi tiến hành thay đổi động các nút chủ Filtering Scheme,” In: Proceedings of the 5th cụm. Hơn nữa, với chính sách phân cụm được đề xuất International Conference on Ubiquitous Intelligence and Computing, UIC 2008, Oslo, Norway (23–25 June đối với các đầu đọc di chuyển, DCDF bảo đảm được 2008) pp. 311-322. hiệu quả năng lượng như được chỉ ra trong Bảng III. [8] Ali Kashif Bashir, Se-Jung Lim, Chauhdary Sajjad Việc triển khai giải thuật DCDF là khả thi vì các điều Hussain and Myong-Soon Park. “Energy Efficient In- kiện xem xét phù hợp với điều kiện thực tế là các đầu network RFID Data Filtering Scheme in Wireless đọc và thẻ có thể di chuyển. Sensor Networks”, Sensors, vol. 11, pp.7004-7021, Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 22
  7. 2011. Nguyễn Văn Tùng, nhận học vị [9] Ali Kashif Bashir, Se-Jung Lim, Chauhdary Sajjad thạc sỹ năm 2015; Hiện đang công tác Hussain and Myong-Soon Park. “In-network RFID tại Khoa CNTT, trường Đại học Công Data Filtering Scheme in RFID-WSN for RFID Nghiệp Thực Phẩm, Thành phố Hồ Applications”, In: nternational Conference on Chí Minh. Lĩnh vực nghiên cứu: Mạng Intelligent Robotics and Applications (ICIRA): truyền dẫn quang (OBS), mạng cảm Intelligent Robotics and Applications (2013) pp 454- biến tích hợp với RFID. 465. Email: tungnv@cntp.edu.vn [10] G. Sandhiya, and Ramya Jothikumar. “Enhanced K- means with dijikstra algorithm for energy consumption in wireless sensor network,” In: Intelligent Systems and Control (ISCO), 10th International Conference on, 7-8 Jan. 2016. AN IMPROVEMENT OF DYNAMIC RFID CLUSTERING FOR ENERGY-EFFICIENT DATA FILTERING Abstract: Data filtering in the model of integrated RFID and sensor networks is a current issue that is drawing much interest from researchers around the world. One of the approaches of energy-efficient data filtering is based on clustering in which data filter points are only performed by cluster nodes. However, most of the proposals are studied in an environment where readers are assumed to be non-moving and the clustering role is fixed at clusters. This causes clusters to consume too much energy, which results in a dramatic reduction in their living time. This article will propose an improvement in dynamic clustering for RFID readers in which clustering is replayed periodically and clustering roles are flexibly changed between readers so that the consumed energy is appropriately shared among them and thus increases the lifetime of the system. Võ Viết Minh Nhật, nhận học hàm Phó Giáo sư năm 2016, học vị Tiến sỹ năm 2007 tại đại học Quebec Canada; Hiện công tác tại Đại học Huế. Lĩnh vực nghiên cứu bao gồm: mạng truyền dẫn quang (OBS), mạng cảm biến tích hợp với RFID, tính toán mềm (mạng nơ ron nhân tạo, giải thuật tiến hóa, di truyền). Email: vvmnhat@hueuni.edu.vn Lê Văn Hòa, nhận học vị thạc sỹ năm 2013; Hiện làm nghiên cứu sinh tại Khoa CNTT, Đại học Khoa học, Đại học Huế. Lĩnh vực nghiên cứu: Mạng truyền dẫn quang (OBS), mạng cảm biến tích hợp với RFID. Email: lvhoa@hueuni.edu.vn Huỳnh Quốc Phương, nhận học vị thạc sỹ năm 2016; Hiện đang công tác tại Khoa CNTT, trường Đại học An Giang; Lĩnh vực nghiên cứu: mạng cảm biến tích hợp với RFID, mạng nơ ron nhân tạo. Email: hqphuong@agu.edu.vn Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 23