ĐỒ ÁN:
TÌM HIỂU VỀ MẠNG CẢM BIẾN

Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
2

Lời nói đầu
Kính gửi đến quý thầy Bài tập lớn của nhóm chúng em, với đề tài được
chọn là “Tìm hiểu về Mạng Cảm Biến “. Trong đề tài gồm 4 Chương:
- Chương I: Sự phát tiển của Mạng Cảm Biến
- Chương II: Cấu trúc & Kiến trúc giao thức
- Chương III: Chọn đường tron WSN
- Chương IV: Các kỷ thuật phân nhóm trong các mạng cảm biến vô tuyến
Vì đề tài em được chọn là đề tài em đang theo học theo tiến trình học ở lớp
nên em chưa thể đi sâu, những kiến thức tìm hiểu được, chưa được chi tiết. Vậy khi
em gửi đề tài này đến thầy kính mong Cô xem xét, hướng dẫn thêm cho em!
Với đề tài “Tìm hiểu về Mạng Cảm Biến “ em muốn hiểu rõ và sâu hơn
về cấu trúc và nguyên tắc hoạt động của Mạng Cảm Biến.
Đây là một phần rất quan trọng trong môn Truyền Số Liệu vì nó được ứng
dụng rộng rãi trong thực tế.
Em xin chân thành cảm ơn sự nhiệt tình hướng dẫn của Cô Lê Nguyễn Mai
Duyên, chính những điều đó đã giúp em được thuận lợi hơn trong quá trình làm đề
tài. Sau khi thực hiện đề tài em đã thu được rất nhiều kiến thức bổ ích, thiết thực,
góp phần rất lớn cho quá trình học và công việc của bản thân em sau này.

I. GIỚI THIỆU :

Mạng cảm biến vô tuyến (WSN) có thể hiểu đơn giản là mạng liên kết các
node với nhau bằng kết nối sóng vô tuyến (RF connection) trong đó các node mạng
thường là các (thiết bị) đơn giản , nhỏ gọn, giá thành thấp và có số lượng lớn, được
phân bố một cách không có hệ thống (non-topology) trên một diện tích rộng (phạm vi
hoạt động rộng), sử dụng nguồn năng lượng hạn chế (pin), có thời gian hoạt động lâu
dài (vài tháng đến vài năm) và có thể hoạt động trong môi trường khắc nghiệt (chất độc,
ô nhiễm, nhiệt độ ).
Các node mạng thường có chức năng sensing (sensor node): cảm ứng, quan sát
môi trường xung quanh như;nhiệt độ, độ ẩm, ánh sáng theo dõi hay định vị các mục
tiêu cố định hoặc di động Các node giao tiếp ad-hoc với nhau và truyền dữ liệu về
trung tâm (base station) một cách gián tiếp bằng kỹ thuật multi-hop.
Lưu lượng (traffic) dữ liệu lưu thông trong WSN là thấp và ko liên tục (không
hẳn với tracking và localization aplication). Do vậy để tiết kiệm năng lượng, các sensor
node thường có nhiều trạng thái hoạt động (active mode) và trạng thái nghỉ (sleep
mode) khác nhau. Thông thường thời gian 1 node ở trạng thái nghỉ lớn hơn ở trạng thái
hoạt động rất nhiều.
Như vậy, đặc trưng cơ bản nhất để phân biệt 1 mạng cảm biến và 1 mạng
wireless khác chính là giá thành, mật độ node mạng, phạm vi hoạt động, cấu hình mạng
(topology), lưu lượng dữ liệu, năng lượng tiêu thụ và thời gian ở trạng thái hoạt động
(active mode).
II. ĐẶC TRƯNG VÀ CẤU HÌNH MẠNG CẢM BIẾN :
Một node trong mạng WSN thông thường bao gồm 2 phần: phần cảm biến
(sensor) hoặc điều khiển và phần giao tiếp vô tuyến (RF transceiver). Do số lượng node
trong WSN là lớn và không cần các hoạt động bảo trì, nên yêu cầu thông thường đối
với 1 node mạng là giá thành thấp (10 - 50 usd) và kích thước nhỏ gọn ( diện tích bề
mặt vài đến vài chục cm2).
Do giới hạn về nguồn năng lượng cung cấp (pin ), giá thành và yêu cầu hoạt
động trong một thời gian dài, nên vấn đề tiêu thụ năng lượng là tiêu chí thiết kế quan

tiêu thụ , đơn giản hóa việc quản lý mạng và cấp phát địa chỉ cho từng node mạng (theo
cluster).
Do giới hạn khả năng tính toán của từng node mạng cũng như để tiết kiệm
năng lượng, WSN thường sử dụng các phương pháp tính toán và xử lý tín hiệu phi tập
trung (giảm tải cho node gần hết năng lượng) hoặc gửi dữ liệu cần tính toán cho các
base station (có khả năng xử lý tín hiệu mạnh và ít ràng buộc về tiêu thụ năng lượng).

III. MÔT SỐ CHUẨN MẠNG CẢM BIẾN :
Do phạm vi ứng dụng cua WSN rất rộng lớn, tính chất, đặc trưng của mạng
phụ thuộc vào ứng dụng triển khai cụ thể. Do vậy, các công ty, các phòng thí nghiệm
vẫn thường phát triển, triển khai giao thức riêng (MAC, Routing, synchronisation )
phù hợp cho từng ứng dụng cụ thể dựa trên các thiết bị phần cứng (transceiver chip)
trên thị trường. Một số chuẩn WSN được biết đến:
ALOHA system (U. of Hawaii)
PRNET system (U.S. Defense)
WINS (U. of California)
PicoRadio (U. of California)
MicroAMPS (M.I.T)
MANET (Mobile ad-hoc Network)
Zigbee: dựa trên physical layer và MAC layer của chuẩn WPAN
802.15.4

Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
5

IV. ỨNG DỤNG CỦA MẠNG CẢM BIẾN :

GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
6
Chương 2:

CẤU TRÚC & KIẾN TRÚC GIAO THỨC

Tóm tắt: Những tiến bộ gần đây trong thông tin vô tuyến và điện tử đã cho
phép phát triển các mạng cảm biến giá thành thấp. Mạng cảm biến có thể được sử
dụng trong các ứng dụng khác nhau như chăm sóc sức khoẻ, trong quân sự hoặc sử
dụng trong gia đình. Mạng cảm biến vô tuyến (WSN) bao gồm các nút nhỏ có khả năng
cảm biến, tính toán và trao đổi thông tin vô tuyến. Một số giao thức chọn đường, quản
lý công suất và trao đổi số liệu đã được thiết kế cho WSN với yêu cầu quan trọng nhất
là tiết kiệm được năng lượng. Các giao thức chọn đường trong WSN có thể khác nhau
tuỳ theo ứng dụng và cấu trúc mạng. Bài báo này sẽ trình bày về cấu trúc mạng và
phương pháp chọn đường trong WSN. Nói chung, các giao thức chọn đường được chia
thành 3 loại dựa vào cấu trúc mạng: ngang hàng, phân cấp hoặc dựa vào vị trí. Ngoài
ra, những giao thức này có thể được phân loại dựa theo đa đường, yêu cầu, hỏi/đáp,
QoS và liên kết tuỳ thuộc vào chế độ hoạt động. Bài báo cũng đánh giá chỉ tiêu về mức
tiêu thụ công suất và ảnh hưởng của phân bố nút cho giao thức chọn đường LEACH
của WSN (Low Energy Adaptive Clustering Hierarchy-Phân cấp nhóm thích ứng công
suất thấp).
I. GIỚI THIỆU :
Một mạng cảm biến bao gồm số lượng lớn các nút cảm biến được phân bố cả
bên trong hiện tượng hoặc phân bố bên cạnh hiện tượng. Vị trí của các nút cảm biến
không cần phải thiết kế hoặc xác định trước. Điều này cho phép phân bố ngẫu nhiên
trong các địa hình phức tạp hoặc các hoạt động trợ giúp thảm hoạ. Mặt khác, cũng có
nghĩa là các giao thức của mạng cảm biến và các thuật toán phải có khả năng tự tổ
chức. Một đặc điểm quan trọng khác của các mạng cảm biến là khả năng phối hợp giữa
các nút cảm biến. Các nút cảm biến được gắn một bộ xử lý bên trong. Thay vì gửi đi số
liệu thô tới nút đích, chúng sử dụng khả năng xử lý để thực hiện các tính toán đơn giản

gốc. Việc chọn đường tới nút gốc theo đa bước nhảy được minh hoạ trong hình 1. Nút
gốc có thể liên lạc với nút quản lý nhiệm vụ thông qua Internet hoặc vệ tinh. Việc thiết
kế mạng cảm biến như mô tả trong hình 1 phụ thuộc vào nhiều yếu tố như khả năng
chống lỗi, giá thành sản phẩm, môi trường hoạt động, cấu hình mạng cảm biến, tích
hợp phần cứng, môi trường truyền dẫn và tiêu thụ công suất.

Hình 1: Phân bố nút cảm biến trong trường cảm biến
III. KIẾN TRÚC GIAO THỨC MẠNG :
Kiến trúc giao thức được sử dụng bởi nút gốc và các nút cảm biến ở hình 1
được trình bày trong hình 2. Kiến trúc giao thức này kết hợp giữa công suất và chọn
đường, kết hợp số liệu với các giao thức mạng, sử dụng công suất hiệu quả với môi
trường vô tuyến và sự tương tác giữa các nút cảm biến. Kiến trúc giao thức bao gồm
lớp vật lý, lớp liên kết số liệu, lớp mạng, lớp truyền tải, lớp ứng dụng, phần quản lý
công suất, phần quản lý di động và phần quản lý nhiệm vụ. Lớp vật lý cung cấp các kỹ
thuật điều chế, phát và thu. Vì môi trường có tạp âm và các nút cảm biến có thể di
động, giao thức điều khiển truy nhập môi trường (MAC) phải xét đến vấn đề công suất
và phải có khả năng tối thiểu hoá việc va chạm với thông tin quảng bá của các nút lân
cận. Lớp mạng quan tâm đến việc chọn đường số liệu được cung cấp bởi lớp truyền tải.
Lớp truyền tải giúp duy trì luồng số liệu nếu ứng dụng mạng cảm biến yêu cầu. Tuỳ
theo nhiệm vụ cảm biến, các loại phần mềm ứng dụng khác nhau có thể được xây dựng
và sử dụng ở lớp ứng dụng. Ngoài ra, các phần quản lý công suất, di chuyển và nhiệm
vụ sẽ giám sát việc sử dụng công suất, sự di chuyển và thực hiện nhiệm vụ giữa các nút
Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
8
cảm biến. Những phần này giúp các nút cảm biến phối hợp nhiệm vụ cảm biến và tiêu
thụ công suất tổng thể thấp hơn.

một số hạn chế như giới hạn về nguồn công suất, khả năng tính toán và độ rộng băng
thông. Một trong những mục tiêu thiết kế chính của WSN là kéo dài thời gian sống của
mạng và tránh suy giảm kết nối nhờ các kỹ thuật quản lý năng lượng. Việc thiết kế các
giao thức chọn đường trong WSN bị ảnh hưởng bởi một số yếu tố. Vấn đề này phải
được giải quyết triệt để thì mới đạt được hiệu quả truyền tin trong WSN. Dưới đây sẽ
tóm tắt một số khó khăn trong vấn đề chọn đường và thiết kế trong mạng WSN.
Phân bố nút: Việc phân bố nút trong WSN phụ thuộc vào ứng dụng và có thể
được thực hiện bằng tay hoặc phân bố ngẫu nhiên. Khi phân bố bằng tay, số liệu được
chọn đường thông qua các đường xác định trước. Tuy nhiên khi phân bố các nút ngẫu
nhiên sẽ tạo ra một cấu trúc chọn đường đặc biệt (ad-hoc). Liên lạc giữa các nút cảm
biến thường có cự ly ngắn do các hạn chế về năng lượng và băng thông. Do đó việc
chọn đường sẽ thực hiện qua nhiều bước nhảy.
Tiêu thụ năng lượng không được làm mất độ chính xác: Các nút cảm biến
có thể sử dụng quá các giới hạn về công suất để thực hiện tính toán và truyền tin trong
môi trường vô tuyến. Thời gian sống của nút cảm biến phụ thuộc rất nhiều vào thời
gian sử dụng của pin [1]. Trong WSN đa bước nhảy, mỗi nút đóng hai vai trò là truyền
số liệu và chọn đường. Một số nút cảm biến hoạt động sai chức năng do lỗi nguồn công
suất có thể gây ra sự thay đổi cấu hình mạng nghiêm trọng và phải chọn đường lại các
gói hoặc tổ chức lại mạng.
Phương pháp báo cáo số liệu: Việc báo cáo số liệu trong WSN phụ thuộc vào
ứng dụng và có thể được chia thành báo cáo theo thời gian, theo sự kiện, theo yêu cầu
hoặc lai ghép những phương pháp này. Phương pháp báo cáo theo thời gian phù hợp
với các ứng dụng yêu cầu giám sát số liệu định kỳ. Khi đó, các nút cảm biến sẽ bật bộ
phận cảm biến và bộ phận phát theo định kỳ, cảm nhận môi trường, phát số liệu yêu cầu
theo chu kỳ thời gian xác định. Trong phương pháp báo cáo theo sự kiện và theo yêu
cầu, các nút cảm biến sẽ phản ứng tức thì đối với những thay đổi giá trị của thuộc tính
cảm biến do xuất hiện một sự kiện xác định nào đó hoặc để trả lời một yêu cầu được tạo
ra bởi nút gốc hay các nút khác trong mạng. Do vậy, những phương pháp này phù hợp
với các ứng dụng phụ thuộc thời gian. Cũng có thể sử dụng kết hợp các phương pháp
trên. Giao thức chọn đường chịu ảnh hưởng đáng kể từ phương pháp báo cáo số liệu về

Tính động của mạng: Trong nhiều nghiên cứu, các nút cảm biến được giả
thiết là cố định. Tuy nhiên trong một số ứng dụng, cả nút gốc và các nút cảm biến có
thể di chuyển [2]. Khi đó các bản tin chọn đường từ hoặc tới các nút di chuyển sẽ gặp
phải các vấn đề như đường liên lạc, cấu hình mạng, năng lượng, độ rộng băng Tuy
nhiên, đối tượng thì có thể di chuyển (ví dụ ứng dụng dò tìm/theo dõi mục tiêu). Các sự
kiện cố định thì cho phép mạng làm việc ở chế độ phản ứng (tạo lưu lượng khi cần báo
cáo) trong khi các sự kiện chuyển động thì trong hầu hết các ứng dụng đều yêu cầu phải
báo cáo định kỳ cho nút gốc.
Môi trường truyền dẫn: Trong mạng cảm biến đa bước nhảy, các nút thông
tin được kết nối qua môi trường vô tuyến. Các đặc tính của kênh vô tuyến như pha
đinh, tỷ lệ lỗi cũng có thể ảnh hưởng đến hoạt động của mạng cảm biến. Nói chung, độ
rộng băng yêu cầu của số liệu cảm biến là thấp, khoảng từ 1-100 kb/s. Liên quan đến
môi trường truyền dẫn là việc thiết kế MAC. Một phương pháp thiết kế MAC cho các
mạng cảm biến là sử dụng các giao thức đa truy nhập phân chia theo thời gian (TDMA)
sẽ tiết kiệm năng lượng hơn so với các giao thức đa truy nhập khác như đa truy nhập
theo sóng mang (CSMA) (ví dụ IEEE 802.11). Công nghệ Bluetooth [3] cũng có thể
được sử dụng.
Khả năng giám sát: Trong WSN, mỗi nút cảm biến giám sát một vùng xác
định. Vùng giám sát môi trường của nút cảm biến bị giới hạn bởi cự ly và độ chính xác,
nó có thể chỉ giám sát một phạm vi rất nhỏ. Do đó, vùng giám sát cũng là một tham số
thiết kế quan trọng trong WSN.
Kết hợp số liệu: Vì các nút cảm biến có thể tạo ra số liệu dư thừa nên các gói
tương tự nhau từ nhiều nút có thể được kết hợp lại để giảm số lượng truyền dẫn. Việc
kết hợp số liệu là từ nhiều nguồn khác nhau theo một hàm kết hợp xác định. Kỹ thuật
Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
11


Hình 3: Phân loại giao thức chọn đường trong WSN
Bảng 1: Phân loại và so sánh các giao thức chọn đường trong mạng cảm
biến vô tuyến
Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
12 Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
13
III. Đánh giá chỉ tiêu giao thức chọn đường LEACH
Giao thức chọn đường LEACH
Heinzelman [1] đã giới thiệu một giao thức phân cấp theo nhóm cho phép tiết
kiệm năng lượng trong mạng cảm biến được gọi là phân cấp nhóm thích ứng công suất
thấp (LEACH). Mục đích của LEACH là lựa chọn ngẫu nhiên các nút cảm biến làm các
nút chủ, do đó việc tiêu hao năng lượng khi liên lạc với nút gốc được trải đều cho tất cả
các nút cảm biến trong mạng. Quá trình hoạt động của LEACH được chia thành hai
bước là bước thiết lập và bước ổn định. Thời gian của bước ổn định kéo dài hơn so với
thời gian của bước thiết lập để giảm thiểu phần điều khiển.
Trong bước thiết lập, một nút cảm biến lựa chọn một số ngẫu nhiên giữa 0 và
1. Nếu số này nhỏ hơn ngưỡng T(n) thì nút cảm biến là nút chủ. T(n) được tính như sau:
(1)


Kết quả và đánh giá
Đánh giá về mức tiêu thụ công suất
Hình 4 là kết quả mô phỏng là cho trường hợp mạng WSN gồm 160 nút phân
bố đều, công suất ban đầu của nút là 3,0, sử dụng giao thức LEACH và Truyền trực tiếp
tới nút gốc. Từ đó có thể thấy rằng số nút truyền tin kết thúc sau khoảng 470 chu kỳ
thời gian đối với trường hợp truyền trực tiếp và sau khoảng 685 chu kỳ thời gian đối
với trường hợp sử dụng giao thức LEACH. Do đó có thể rút ra nhận xét là sử dụng giao
thức LEACH sẽ tiết kiệm công suất hơn so với truyền trực tiếp đến nút gốc.
Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
15

Hình 4: Khảo sát số nút truyền tin theo thời gian với 160 nút, phân bố đều,
công suất ban đầu là 3,0
Ảnh hưởng của phân bố nút tới sự tiêu thụ công suất của mạng
Hình 5 là kết quả mô phỏng là cho trường hợp mạng WSN gồm 160 nút phân
bố không đều, công suất ban đầu của nút là 3,0, sử dụng giao thức LEACH và Truyền
trực tiếp tới nút gốc. Từ đó có thể thấy rằng số nút truyền tin kết thúc sau khoảng 430
chu kỳ thời gian đối với trường hợp truyền trực tiếp và và sau khoảng 680 chu kỳ thời
gian đối với trường hợp sử dụng giao thức LEACH. So sánh với trường hợp trong hình
4 có thể rút ra nhận xét là phân bố nút cũng ảnh hưởng đến công suất tiêu thụ của
mạng. Tuy nhiên, ảnh hưởng này là không nhiều.

Hình 5: Khảo sát số nút truyền tin theo thời gian với 160 nút, phân bố không
đều, công suất ban đầu là 3,0. GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
17
Chương 4:

CÁC KỸ THUẬT PHÂN NHÓM TRONG CÁC MẠNG
CẢM BIẾN VÔ TUYẾN

I. 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.


chặng, các nút xa trạm gốc thường là những nút ở trong tình trạng nguy cấp nhất do
thiếu năng lượng hoạt động, trong khi ở trao đổi thông tin nhiều chặng, các nút gần
trạm gốc nhất thường phải gánh chịu nhiều lưu lượng tải và thường bị dừng hoạt động
trước tiên (đây là một vấn đề khá nguy hiểm và nghiêm trọng – “hot spot”).
Các mạng cảm biến có phân nhóm có thể được phân chia thành các mạng
không đồng nhất và các mạng đồng nhất tương ứng với kiểu và chức năng của các nút
trong mạng. Với mạng đồng nhất, tất cả các nút đều có các khả năng xử lý và cấu trúc
phần cứng như nhau. Vai trò của nút chính được hoán chuyển vòng tròn theo chu kỳ
giữa các nút để cân bằng tải. Mặc dù hoán chuyển vòng tròn vai trò các nút chính để
đảm bảo các nút cảm biến tiêu thụ năng lượng đồng đều hơn, nhưng vấn đề “hot spot”
đã nêu ra ở trên không thể tránh khỏi hoàn toàn. Trong các mạng không đồng nhất, một
số lượng nhất định các nút có những khả năng xử lý cao hơn và độ phức tạp phần cứng
lớn hơn được triển khai trên toàn mạng cùng với một số các nút cảm biến thông thường
khác. Đối với các nút chính, nhiều năng lượng hơn cần phải tiêu thụ để thực hiện một
vài chức năng nào đó và chúng phục vụ như là các bộ thu thập số liệu và các trung tâm
xử lý cho những số liệu thu thập bởi các nút cảm biến. Vì các mạng không đồng nhất
cấp phát các nút chính ở dạng tĩnh, thời gian hoạt động của mạng được xác định phụ
thuộc vào thời gian chức năng của các nút chính mà có liên quan trực tiếp tới hoạt động
của nút chính và tiêu thụ năng lượng. Các nút chính có thể hình 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.
Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
19

Mặc dầu vẫn chưa có định nghĩa thống nhất về “thời gian hoạt động của mạng” vì khái
niệm này phụ thuộc mục tiêu của ứng dụng, các định nghĩa chung bao gồm thời gian
cho đến khi nút đầu tiên/cuối cùng xả hết năng lượng của nó và thời gian cho đến khi
nút không được kết nối với trạm gốc nữa. Lưu ý rằng, thậm trí mục tiêu của một số giao
thức không phải để làm tối đa “thời gian hoạt động của mạng”.
Các cải thiện về “thời gian hoạt động của mạng” có thể vẫn đạt được nếu việc
thu thập số liệu được khai thác và mạng được tái phân lớp theo định kỳ.
Phân nhóm được nghiên cứu rộng rãi trong xử lý số liệu và mạng cố định. Tuy
nhiên, kỹ thuật phân nhóm được phát triển trong các lĩnh vực nêu trên đều không thể áp
dụng trực tiếp cho mạng cảm biến không dây do sự triển khai duy nhất và các đặc tính
hoạt động của những mạng này.
Đặc biệt, các mạng cảm biến không dây được triển khai theo cách thức tùy
biến (ad hoc) và có một số lượng lớn các nút. Các nút thường không nhận thức được về
các vị trí của chúng. Do vậy, các giao thức phân bố mà dựa trên thông tin ở lân cận
xung quanh thường được lựa chọn cho các mạng cảm biến không dây (tuy nhiên, phần
Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
20
lớn các nghiên cứu trong lĩnh vực này vẫn giả sử rằng cấu hình của mạng là đã được
biết bởi một bộ điều khiển trung tâm). Hơn nữa, các nút trong các mạng cảm biến
không dây hoạt động dựa trên nguồn năng lượng dự trữ có giới hạn (battery). Vì vậy,
kỹ thuật phân nhóm triển khai trên thực tế phải có chi phí trao đổi thông tin thấp. Cuối
cùng 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

nhận dạng thấp mà không xem xét đến thời gian hoạt động mà chúng có thể tồn tại.
Ngoài ra, nó không tạo ra được sự cân bằng về lưu lượng tải cho toàn bộ các nút trong
mạng.
Một phương pháp khác quan tâm đến các nút có bậc (degree) lớn hơn (ví dụ:
Kuhn et. al. [3],
Tìm hiểu về Mạng Cảm Biến
GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
21
Amis et. al. [4] và Gerla et. al. [5]) để tạo ra các nhóm và xây dựng tổ hợp các
nút chính chi phối.
Ở đây, bậc của một nút được tính toán dựa trên khoảng cách (phạm vi truyền
dẫn) giữa nút này với các nút khác. Nói cách khác, bậc của một nút là số các nút lân cận
trong một truyền dẫn được xác định trước gọi là phạm vi của nhóm. Nút có số lượng tối
đa các nút lân cận sẽ được chọn làm 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 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

GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3
22
mà được bắt đầu từ một người quan sát và việc cưỡng bức một giới hạn tối đa và tối
thiểu cho kích cỡ của nhóm.
Giao thức phân bố này được đề xuất ở [10] cho việc xây dựng cây mở rộng.
Tính hiệu quả của các phương thức tiếp cận tập trung bị hạn chế ở các mạng
có phạm vi rộng lớn nơi mà việc thu thập tất cả các thông tin cần thiết được thực hiện ở
căn cứ trung tâm cả về mặt thời gian và tiêu thụ năng lượng. Phương thức tiếp cận phân
tán thường phù hợp hơn cho các mạng có phạm vi rộng. Ở những phương thức tiếp cận
phân tán này, một nút quyết định gia nhập một nhóm nào đấy hoặc trở thành nút chính
dựa trên thông tin nhận được chủ yếu từ các nút lận cận một chặng với nó. Một số các
kỹ thuật phân nhóm phân tán đã được đề xuất. Những kỹ thuật này có thể có tính chất
lặp hoặc xác suất.
II.2.a. Các kỹ thuật phân nhóm lặp
Trong các kỹ thuật phân nhóm lặp, một nút thường đợi một sự kiện cụ thể xuất
hiện hoặc các nút nhất định nào đó để quyết định vai trò của chúng (ví dụ như trở thành
nút chính) trước khi đư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, thuật toán DCA yêu cầu u O( n ) bước lặp để kết
thúc thuật toán. Tốc độ hội tụ trong tình huống xấu nhất có thể là n-1 trong một thiết
lập một chiều (1D). Hiệu năng của các kỹ thuật lặp là khá nhạy cảm với những tổn thất

II.2.b. Các kỹ thuật phân nhóm có tính xác suất
Phương thức tiếp cận theo xác suất hay ngẫu nhiên cho việc phân nhóm các
nút đảm bảo sự hội tụ nhanh chóng mà vẫn có được một số các đặc tính quan trọng như
kích cỡ các nhóm cân bằng.
Nó cho phép các nút được quyết định độc lập về về vai trò của chúng trong
mạng phân nhóm và vẫn duy trì tổng phí trao đổi bản tin thấp. Chúng ta sau đây thảo
luận về một vài ví dụ của hướng tiếp cận này.
Giao thức LEACH: Heinzelman et. al. [13] đã giới thiệu một thuật toán phân
nhóm phân bậc cho các mạng cảm biến gọi là Phân nhóm phân bậc tương thích, năng
lượng thấp – LEACH (Low Energy Adaptive Clustering Hierarchy). LEACH lựa chọn
ngẫu nhiên một số nút cảm biến để trở thành các nút chính và quay vòng vai trò này để
phân bố đều tải năng lượng giữa các nút cảm biến trong mạng. Ở LEACH, các nút
chính nén các dữ liệu đến từ các nút khác trong nhóm của chúng và gửi các gói dữ liệu
thu thập này tới trạm gốc nhằm mục đích giảm số lượng thông tin truyền phát về trạm
gốc. Việc thu thập số liệu được thực hiện tập trung và theo chu kỳ. Do vậy giao thức
này thực sự thích ứng khi có nhu cầu trao đổi theo dõi thường xuyên của mạng cảm
biến. Thực tế, người sử dụng có thể không cần tất cả số liệu ngay lập tức, cho nên việc
truyền phát số liệu theo chu kỳ là không cần thiết và có thể làm suy giảm nguồn năng
lượng giới hạn của các nút cảm biến. Sau một khoảng thời gian cho trước, việc quay
vòng ngẫu nhiên thay đổi vai trò của nút chính được tiến hành sao cho có sự tiêu tán
năng lượng đều giữa các nút cảm biến trong mạng. Dựa vào mô hình mô phỏng mạng
của các tác giả, chỉ có 5 % số nút cần thiết hoạt động ở dạng nút chính.
Hoạt động của LEACH được phân tách thành hai pha, pha thiết lập và pha ổn
định trạng thái. Ở trong pha thiết lập, các nhóm được tổ chức và các nút chính được lựa
chọn. Còn ở giai đoạn ổn định trạng thái, việc truyền số liệu thực sự về các trạm gốc
được tiến hành. Khoảng thời gian tồn tại của pha ổn định trạng thái thường dài hơn so
với thời gian thiết lập ban đầu để giảm tối thiểu tổng chi phí. Trong pha thiết lập, một
số lượng nhỏ các nút được xác định trước, p, tự quyết định chúng trở thành các nút
chính như sau. Một nút cảm biến chọn lấy một số ngẫu nhiên, r, trong phạm vi 0 và 1.
Nếu số ngẫu nhiên này nhỏ hơn giá trị ngưỡng, T(n), thì nút đó sẽ trở thành nút chính ở

với trường hợp mạng gồm các nhóm cố định.
Một phiên bản tập trung của LEACH, LEACH-C được đề xuất ở [14]. Không
giống như LEACH, nơi mà các nút tự định hình chúng vào trong các nhóm, LEACH-C
sử dụng trạm gốc cho việc hình thành các nhóm. Trong pha thiết lập của LEACH-C,
trạm gốc thu các thông tin liên quan đến vị trí và mức năng lượng của từng nút trong
mạng. Sử dụng những thông tin này, trạm gốc tìm số các nút chính được xác định trước
và cấu hình mạng thành các nhóm. Tập hợp các nhóm được chọn để giảm tối thiểu
năng lượng yêu cầu cho các nút không phải là nút chính để truyền phát số liệu của
chúng đến tương ứng các nút chính. Mặc dầu các hoạt động khác của LEACH-C giống
như LEACH, các kết quả được giới thiệu ở [14] chỉ cho thấy một sự cải thiện đáng kể
của LEACH-C so với LEACH. Các tác giả của [14] đưa ra hai lý do chính cho sự tiến
bộ:
• Trạm gốc sử dụng hiểu biết chung của nó về mạng để tạo ra các nhóm tốt
hơn có yêu cầu năng lượng ít hơn cho việc truyền phát số liệu
• Số lượng các nút chính trong mỗi vòng của LEACH-C bằng một giá trị tối
ưu được xác định trước, trong khi đó ở LEACH, số lượng các nút chính thay đổi từ
vòng nọ sang vòng kia do sự thiếu phối hợp chung giữa các nút.
Tuy nhiên, LEACH có một số nhược điểm:
• LEACH chưa xác định cụ thể được số lượng tối ưu các nút chính của mạng
khi mà các mạng khác nhau có cấu hình, mật độ và số lượng nút khác nhau.
• Chưa có gợi ý về khi nào thì việc tái tạo lại các nút chính cần được thực
hiện.
• Các nút chính ở xa trạm gốc sẽ tiêu thụ nhiều năng lượng hơn và nhanh
chóng dừng hoạt động hơn các nút khác.
Giao thức phân nhóm phân tán, hiệu quả năng lượng và lai ghép – HEED [6]
giả sử rằng, các nút cảm biến không có bất kỳ khả năng đặc biệt nào như được trang bị
Tìm hiểu về Mạng Cảm Biến

một khoảng thời gian lặp ngắn tc và sau đó bắt đầu lần lặp tiếp theo. Nút thường dừng
quá trình lặp sau khi CHprob đạt đến 1. Nếu một nút quyết định trở thành nút chính, nó
thường tăng công suất phát lên Pt cho trao đổi thông tin giữa các nhóm.
Các tác giả của HEED cũng đã chỉ ra trong [6] là HEED kết thúc việc chọn nút
chính với số lần lặp cố định Điều này tương phản với một số phương thức khác khi mà các nút chính được
lựa chọn mới ngay sau mỗi bước lặp và nó cũng làm giảm các chi phí thiết lập cao,
không cần thiết gắn kết với quá trình lựa chọn các nút chính. Thêm vào đó, mạng các
nhóm vẫn duy trì kết nối theo một mô hình mật độ nhất định khi t c R ≥ 6R . Ngoài ra,
xác suất mà hai nút chính nằm lẫn nhau trong cùng phạm vi của nhóm Rc là rất nhỏ.