1
Các kỹ thuật phân nhóm trong các mạng cảm biến vô tuyến

TS. Lê Nhật Thăng, TS. Nguyễn Quý Sỹ

1. Giới thiệu chung

Trong những năm gần đây, rất nhiều mạng cảm biến vô tuyến đã và đang được phát triển và triển
khai cho nhiều các ứng dụng khác nhau như: theo dõi sự thay đổi của môi trường, khí hậu, giám
sát các mặt trận quân sự, phát hiện và do thám việc tấn công bằng hạt nhân, sinh học và hoá học,
chuẩn đoán sự hỏng hóc của máy móc, thiết bị, theo dấu và giám sát các bác sỹ, bệnh nhân cũng
nh
ư quản lý thuốc trong các bệnh viên, phát hiện và theo dấu các phương tiện xe cộ… Một mạng
cảm biến vô tuyến diện rộng bao gồm nhiều nút cảm biến nhỏ có giá thành thấp, và tiêu thụ năng
lượng ít. Thông qua các kết nối vô tuyến, số liệu thu thập được từ các nút cảm biến sẽ được gửi
đến một trạm gốc gần nhất, rồi sau đó, các số liệu này lại được chuyển tới các trung tâm xử lý dữ
liệu cho các bước phân tích tiếp theo. Một trong những yếu điểm hạn chế liên quan đến thời gian
tồn tại của các mạng cảm biến không dây chính là những nguồn năng lượng giới hạn phục vụ cho
hoạt động của các nút cảm biến được triển khai trong mạng. Để đạt được hiệu quả sử dụng năng
lượng cao và duy trì thời gian hoạt động lâu dài của mạng, các nút cảm biến thường được tổ chức
phân bậc bằng cách gộp chúng lại thành các nhóm riêng biệt mà ở đó số liệu được thu thập và xử
lý nội bộ tại các nút chính (cluster head nodes) trước khi chúng được gửi về một trạm gốc nào đó.
Cấu trúc của mạng cảm biến không dây có phân nhóm được minh họa ở hình vẽ dưới đây.


)
(
( )
)
(
( )
)
(
( )
)
(
( )
)
(
( )
)
(
( )
)
Base station
Cluster-head
Cluster-head
Cluster-head
Sensor
Cluster
Cluster
Cluster

2
•

thành nên một mạng đường trục và sử dụng định tuyến nhiều chặng để định hướng số liệu tới
trạm gốc. Hiện tượng “hot - spot” xảy ra trong mạng khi mà các nút chính sử dụng năng lượng
cung cấp ở tốc độ cao hơn và ngừng hoạt động nhanh hơn các nút chính khác. Việc quản lý lưu
lượng tải trở nên cần thiết để ngăn ngừa vấn đề suy giảm nguồn năng lượng cung cấp trước cho
riêng từng nút chính của mạ
ng.

Các vị trí của các nút chính trên mạng có ảnh hưởng đến tiêu thụ năng lượng tổng cộng của tất cả
các nút. Các nút chính có thể được phân tán trong trường cảm biến một cách ngẫu nhiên hoặc
chúng có thể được triển khai theo một cách thức xác định trước. Trong trường hợp sau, ví dụ, các
nút mạng có khả năng di chuyển và do vậy có thể thay đổi các vị trí của chúng cho tới khi chúng
tới được một vài vị trí được xác định trước. Mặc dầu một mạng cảm biến không đồng nhất và
được triển khai ngẫu nhiên là rất phổ biến và dễ dàng thực hiện, nhưng có nhiều khó khăn hơn để
điều khiển kích cỡ thực sự của các nhóm và cân bằng có hiệu quả lưu lượng giữa các nút chính
của nhóm. Do đó, vấn đề hot spot có thể dễ dàng nảy sinh do có sự tiêu thụ quá năng lượng ở một
nút chính nào đó.

Tuy còn có nhiều thảo luận liên quan đến vấn đề tiêu thụ và bảo toàn năng lượng, mạng cảm biến
không dây phân nhóm có hai ưu điểm chính so với mạng không có sự phân nhóm:

3
•
Mạng cảm biến không dây phân nhóm có khả năng làm giảm khối lượng thông tin trao
đổi giữa các nút bằng việc khoanh vùng truyền dẫn số liệu trong phạm vi các nhóm và
quan trọng hơn bằng việc giảm đáng kể số lượng truyền dẫn về trạm gốc.

•
Mạng cảm biến không dây phân nhóm có khả năng gia tăng thời gian không làm việc của
các nút cảm biến qua việc cho phép các nút chính được điều phối và tối ưu các hoạt động
của các nút thành viên

các điều kiện một trường khắc nghiệt cũng dẫn đến sự ngừng hoạt động không mong muốn của
các nút mạng cảm biến. Cho nên, phân nhóm lại theo định kỳ là rất cần thiết để gắn kết các vùng
bị mất liên lạc và phân bố sự tiêu thụ năng lượng ra toàn bộ các nút. Phân nhóm lại theo định kỳ
cũng rất cần thiết khi mà các tham số sử dụng cho phân nhóm (ví dụ như: năng lượng còn lại,
m
ức độ của nút…) là linh hoạt. Các kỹ thuật phân nhóm được đề xuất cho xử lý số liệu thường
xem xét các tham số tĩnh như là khoảng cách giữa các nút và giả sử rằng các nút là rất xác thực.

Phân nhóm trong mạng cảm biến không dây liên quan đến việc tập hợp các các nút lại thành các
nhóm và lựa chọn ra một nút chính sao cho:

•
Các thành viên của một nhóm có thể trao đổi thông tin trực tiếp với nút chính của
chúng.

4
•
Một nút chính có thể chuyển dữ liệu thu thập được tới trạm gốc trung tâm thông qua
các nút chính khác.

Do vậy, việc tập hợp các nút chính trong mạng hình thành nên một tổ hợp các liên kết chi phối
(connected dominating set) có ảnh hưởng lớn đến toàn mạng. Nghiên cứu về phân nhóm trong
các mạng cảm biến không dây tập trung vào việc phát triển các thuật toán tập trung cũng như
phân tán để tính toán xác định nên tổ hợp các liên kết chi phối. Ở đây, chúng tôi tập trung vào các
hướng tiếp cận phân tán vì chúng là thực tế hơn cho những hiện trạng được triển khai trên phạm
vi rộng. Vì để có được tổ hợp các liên kết chi phối là một vấn đề NP hoàn thiện, các thuật toán đề
xuất thường mang tính chất heuristic.

Chúng ta phân loại các kỹ thuật phân nhóm dựa trên hai tiêu chí:


nút chính. Tuy nhiêu, một nút chính không thể điều khiển được một số lượng lớn các nút của
nhóm do hạn chế về nguồn năng lượng. Điều này có thể
dẫn đến sự suy hao nhanh chóng nguồn
ắc qui của các nút có bậc lớn. Hơn nữa, thông lượng của hệ thống sẽ giảm khi số lượng các nút
trong nhóm tăng lên. Từ khía cạnh áp dụng, các nhóm có số lượng nút đồng đều sẽ làm giảm tải
cho các nút chính. Nhưng vấn đề này làm nảy sinh chi phí cho việc có nhiều nhóm trong mạng và
do vậy yêu cầu nhiều định tuyến hơn.

Các kỹ thuật thuộc loại thứ ba chú trọng đến các nút có trọng số lớn hơn và được chọn làm các
nút chính. Trọng số của một nút được dùng để xác định sự quan trọng của nút. Ví dụ, nó có thể là
năng lượng ắc qui còn lại của nút (như trong giao thức HEED [6]), bậc của nút (như trong giao
thức ACE [7]), hoặc kết hợp các tham số (ví dụ như năng lượng còn lại, phân bậc, tính di động,
khoảng cách trung bình đến các nút lân cận). Kỹ thuật này có nhược điể
m là không có một tiêu

5
chuẩn cụ thể để cấp trọng số cho các nút và nó khá phù hợp với mạng tĩnh mà ở đó các nút không
di chuyển nhiều hoặc di chuyển rất chậm

Một số các giao thức như GAF [8] và SPAN [9], được đề xuất cho việc điều khiển cấu hình mạng
bằng việc khai thác các dư thừa của nút. Các giao thức này lựa chọn các nút nhất định nào đó
thành các nút tích cực hoạt động (active) – tham gia vào quá trình cảm biến và truyền dẫn số liệu,
trong khi các nút khác được bố trí tạm thời ngừng hoạt động để tiết kiệm năng lượng. Theo [8], ví
dụ, một nút thuộc về một vùng nào đó được xác định bởi vị trí của nó. Khái niệm vùng trong ngữ
cảnh này là được định nghĩa như là một phạm vi A mà ở đó bất kỳ một nút u nào đều có thể trao
đổi thông tin qua một chặ
ng với bất kỳ nút v nào thuộc B mà B là vùng lân cận của A. Do vậy, chỉ
cần có một nút đại diện duy nhất trong bất kỳ một vùng nào để tham gia vào cơ chế định tuyến tại
bất cứ thời điểm nào để đảm bảo sự liên kết kết nối mạng. Ở [9], một nút quyết định liệu nó ở chế
độ hoạt động ho

đưa ra một quyết định. Ví dụ, ở trong thuật toán phân nhóm phân tán (DCA – Distributed
Clustering Algorithm) [11], trước khi đưa ra một quyết định, một nút thường đợi tất cả các nút
lân cận nó có trọng số cao hơn để quyết định trở thành nút chính hoặc gia nhập các nhóm đang
hoạt động. Các nút có trọng số cao nhất trong số các nút lân cận cách nhau một chặng được lựa
chọn làm nút chính. Nếu một nút nhận được nhiều thông báo của các nút chính, nó sẽ phân xử
giữa những nút chính bằng cách sử dụng điều kiện ưu tiên (tức là, nút có trọng số cao hơn sẽ
thắng). Nếu không có nút nào trong số các nút lân cận của một nút có trọ
ng số cao hơn quyết định
trở thành nút chính, thì chính nút đó quyết định trở thành nút chính. Vấn đề với phần lớn các
phương pháp lặp là ở chỗ tốc độ hội tụ của chúng phụ thuộc vào đường kính của mạng (đường có
số lượng chặng nhiều nhất). Trong một trường hai chiều có n nút đang được triển khai hoạt động,