Các giải thuật phân cụm cho mạng cảm biến không dây không đồng nhất (P1)

Trong những năm gần đây, mạng cảm biến không dây WSN đã có những ứng dụng quan trọng và rộng khắp trong lĩnh vực cảnh báo thảm họa, giám sát chiến trường, giám sát sản xuất công nghiệp và nông nghiệp. Phân cụm là kỹ thuật quan trọng để kéo dài thời gian sống của mạng cảm biến bằng cách giảm năng lượng tiêu thụ của mạng. Sự phân cụm cũng kéo theo việc phân cấp mạng. Những nhà nghiên cứu trong lĩnh vực WSN coi các nút trong mạng là đồng nhất, song một vài nút có thể có năng lượng lớn hơn để kéo dài thời gian sống và gia tăng độ tin cậy cho mạng. Bài báo giới thiệu mô hình mạng cảm biến không dây không đồng nhất và đưa ra một số giải thuật phân cụm cho mạng này.

MÔ HÌNH MẠNG CẢM BIẾN KHÔNG DÂY KHÔNG ĐỒNG NHẤT

Các nhà nghiên cứu thường coi toàn bộ nút trong mạng cảm biến không dây WSN (Wireless Sensor Network) là đồng nhất song trên thực tế một mạng như vậy khó tồn tại [1]. Ngay cả những cảm biến đồng nhất cũng có nhiều khả năng khác nhau như mức năng lượng ban đầu, tốc độ suy giảm năng lượng... Các mạng cảm biến không dây không đồng nhất thường sử dụng kỹ thuật phân cụm để sử dụng năng lượng hiệu quả, kéo dài thời gian sống cho mạng.

Các loại tài nguyên không đồng nhất

Có ba loại tài nguyên không đồng nhất trong mạng cảm biến không dây không đồng nhất (HWSN- Heterogenous WSN): 

-Không đồng nhất về năng lực tính toán: Trong mạng cảm biến có những nút cảm biến không đồng nhất có bộ xử lý mạnh hơn, bộ nhớ lớn hơn so với những nút thông thường để đảm trách nhiệm vụ thu thập, tổng hợp dữ liệu của những nút xung quanh gửi về trạm gốc (BS - Base Station).

-Không đồng nhất về liên kết: Nút không đồng nhất có bộ thu phát với băng thông lớn và khoảng cách xa hơn nút thông thường. Sự không đồng nhất về liên kết để đảm bảo tốt hơn việc truyền tin cậy dữ liệu tổng hợp từ nút chủ (CH - Cluster Head) tới trạm gốc.

-Không đồng nhất về năng lượng: Nút không đồng nhất được cấp nguồn, được thay pin thường xuyên hoặc có năng lượng khởi đầu lớn.

Trong số các tài nguyên không đồng nhất trên thì không đồng nhất về năng lượng là quan trọng nhất vì để có được sự không đồng nhất về năng lực tính toán hoặc liên kết cũng đều cần đến năng lượng lớn hơn.

Ảnh hưởng của sự không đồng nhất tới các mạng cảm biến không dây

Nếu đặt một vài nút cảm biến không đồng nhất vào WSN thì có một số lợi ích như sau:

-Thời gian đáp ứng: Không đồng nhất về năng lực tính toán có thể làm giảm trễ xử lý và không đồng nhất về liên kết có thể làm giảm thời gian trễ  truyền thông tin, vì thế thời gian đáp ứng sẽ giảm.

-Thời gian sống: Năng lượng tiêu thụ trung bình trong HWSN sẽ ít hơn so với các mạng đồng nhất cho việc chuyển tiếp gói tin từ nút thường tới trạm gốc và vì thế thời gian sống của toàn mạng sẽ tăng lên.

Theo các kết quả nghiên cứu về HWSN: nếu sử dụng các yếu tố không đồng nhất một cách hợp lý, thời gian đáp ứng sẽ nhanh hơn 3 lần và thời gian sống có thể kéo dài gấp 5 lần [2].

Các tham số hiệu năng

Một số tham số hiệu năng được dùng để đánh giá hiệu năng của các giao thức phân cụm là:

-Thời gian sống của mạng: Đây là khoảng thời gian từ khi mạng cảm biến bắt đầu hoạt động tới khi một nút đầu tiên bị chết.

-Số lượng cụm chủ mỗi vòng: Đây là tham số đo tức thì phản ánh số nút sẽ gửi trực tiếp tới trạm gốc, thông tin tổng hợp từ những thành viên trong nhóm của nó.

-Số lượng nút mỗi vòng: Là số đo tức thì phản ánh tổng số nút và các loại nút vẫn chưa dùng hết năng lượng của chúng.

-Thông lượng: Là tổng tốc độ dữ liệu gửi trên mạng, tốc độ dữ liệu gửi từ các cụm chủ tới trạm gốc cũng như tốc độ dữ liệu gửi từ các nút tới cụm chủ của nó.

PHÂNLOẠI THUỘCTÍNH  CỤM

Mục tiêu chung của việc phân cụm trong các mạng cảm biến là cân bằng tải, tăng khả năng chịu lỗi, tăng khả năng kết nối, giảm trễ, giảm số cụm, tối đa thời gian sống của mạng. Bảng 1 giới thiệu một số thuộc tính chính được dùng để phân loại các giải thuật phân cụm trong HWSN như tính chất của cụm, khả năng của cụm chủ và quá trình phân cụm (lựa chọn cụm chủ).

Dựa trên những thuộc tính ở Bảng 1, phần tiếp theo sẽ phân loại các giải thuật phân cụm trong các mạng HWSN.

CÁC GIẢI THUẬT PHÂN CỤM TRONG HWSN

Mạng cảm biến không dây có hàng trăm nút được phân bố một cách ngẫu nhiên. Kỹ thuật phân cụm là một trong những cách tốt nhất để kéo dài thời gian sống của mạng bằng cách giảm năng lượng tiêu thụ. Kỹ thuật phân cụm cho HWSN cần phải hiệu quả về mặt năng lượng để tận dụng đặc điểm không đồng nhất của các nút trong mạng. Có thể chia các giải thuật phân cụm có trong các giao thức định tuyến phân cụm HWSN dựa trên hai tiêu chí: Hiệu quả năng lượng và khả năng ổn định. Sự lựa chọn cụm chủ trong các kỹ thuật hiệu quả năng lượng thường dựa vào năng lượng khởi đầu, năng lượng còn lại, năng lượng trung bình hoặc tốc độ tiêu thụ năng lượng hay là tổng hợp của các tham số trên. Còn với các giao thức lựa chọn ổn định cho HWSN phân cụm thì mục tiêu là kéo dài khoảng thời gian từ khi mạng hoạt động tới khi có nút đầu tiên chết, khoảng thời gian này còn được gọi là giai đoạn ổn định. Hình 2 cho thấy hai tiêu chí phân chia giải thuật phân cụm và một số trong rất nhiều giao thức phân cụm áp dụng cho HWSN trong những năm gần đây.

Các giao thức phân cụm hiệu quả năng lượng

Khái niệm phân cụm dựa trên việc định tuyến cũng được sử dụng để tạo ra những giao thức định tuyến hiệu quả năng lượng trong WSN [1]. Có rất nhiều giao thức định tuyến hiệu quả năng lượng đã được thiết kế dựa trên kiến trúc phân cụm của HWSN trong đó mỗi giải thuật phân cụm có hai pha chính: pha thiết lập cụm và pha trạng thái ổn định.

Với HWSN, nhiệm vụ quan trọng cho giao thức phân cụm là lựa chọn CH sao cho năng lượng tiêu thụ là nhỏ nhất và như vậy sẽ kéo dài thời gian sống của mạng. Một số các giao thức thuộc dạng này được phân tích ở đây là: EEHC, DEEC, DEBC, GPCA.

-EEHC: Sắp xếp cụm không đồng nhất hiệu quả năng lượng

EEHC được đề xuất dựa trên các xác suất lựa chọn có trọng số của mỗi nút để trở thành CH. Giải thuật này dựa trên LEACH - giao thức định tuyến phân cụm cho mạng đồng nhất phổ biến nhất trong WSN. Trong LEACH, có một tỷ lệ phần trăm tối ưu popt nút phải trở thành CH trong mỗi vòng. Giải thuật này dựa trên tiến trình lựa chọn CH khi có các nút không đồng nhất [3]. Hình 3 cho thấy, sau vài vòng hoạt động thì các nút thường (hình tròn) sẽ chết nhanh hơn các nút tiên tiến (hình tam giác) và siêu nút (hình sao).

-DEEC: Giải thuật phân cụm hiệu quả năng lượng phân tán cho HWSN

DEEC là giải thuật phân cụm nhiều mức và phân tán cho HWSN. Giải thuật này lựa chọn CH sử dụng xác suất dựa vào tỷ lệ giữa năng lượng còn lại của nút trên năng lượng trung bình của mạng. Các nút khác nhau có thể là CH trong bao lâu phụ thuộc vào năng lượng ban đầu và năng lượng còn lại. Trong giao thức này giả sử toàn bộ các nút trong WSN có năng lượng khác nhau. DEEC cũng dựa trên LEACH, nó xoay vòng nhiệm vụ CH giữa các nút để kéo dài tính đồng nhất năng lượng. Có hai loại nút không đồng nhất được sử dụng ở đây là nút thường và nút có năng lực cao. Giải thuật với hai kiểu nút có thể mở rộng tiếp với HWSN đa mức.

Tới năm 2009, SDEEC được đề xuất phát triển dựa trên DEEC với chiến lược mới là chiến lược ngẫu nhiên trong đó việc truyền thông nội cụm được giảm đi khi cho một số nút không phải CH được tắt, đi vào chế độ "ngủ“ để bảo toàn năng lượng khi không dùng đến. Nhược điểm của giao thức này là nếu nút tắt khi CH tập hợp dữ liệu thì ở vòng tiếp theo khi "thức dậy" nó sẽ không biết được CH mới.

-DEBC: Giải thuật phân cụm cân bằng năng lượng cho HWSN

Giải thuật DEBC chọn CH dựa trên kiến thức về tỷ lệ giữa năng lượng còn lại của nút với năng lượng trung bình của mạng. Giao thức này cũng xem xét hai mức không đồng nhất và mở rộng kết quả cho đa mức. DEBC khác với LEACH, nó đảm bảo mỗi nút có khả năng trong mỗi n_i =1/p vòng. DEBC chọn n_i theo nút i và năng lượng còn lại E^k_i trong vòng k. p_i  là xác suất mỗi nút i trở thành CH trong n_i vòng. Có sự trợ giúp của p_i , xác suất của nút cải tiến và nút thường trở thành CH có thể tính được và có thể mở rộng cho mạng đa mức không đồng nhất.

-GPCA: Giải thuật phân cụm dựa trên năng lượng và vị trí cho HWSN

GPCA là giao thức phân cụm có tính đến sự không đồng nhất, điều này ảnh hưởng đáng kế đến việc tiêu thụ năng lượng của toàn mạng cảm biến. Trong GPCA, cụm chủ ảo VH (Virtual Header) truyền dữ liệu tới VH gần nhất và VH gần nhất chuyển tiếp dữ liệu tới trạm gốc. Bằng cách này, năng lượng tiêu thụ trên toàn mạng giảm đi vì khoảng cách truyền giữa các VH và trạm gốc được rút ngắn đáng kể. Đồng thời có rất nhiều nút được tự tổ chức thông qua kỹ thuật phân cụm phân tán. Hơn nữa, kỹ thuật ngẫu nhiên được sử dụng để xoay vòng CH nội bộ dựa trên nhãn năng lượng để phân bố đều tải năng lượng giữa các nút cảm biến trong mạng. GPCA còn sử dụng vị trí địa lý để có thể phân cấp và hỗ trợ tính tự động trong mạng. Thông qua mô phỏng GPCA cho kết quả tốt là kéo dài được thời gian sống, giảm tiêu thụ năng lượng và cải thiện số nút sống [4].

Nguyễn Thị Thu Hằng

(còn nữa)