Đồ án Tìm hiểu về mạng cảm biến

ĐỒ ÁN:  
TÌM HIỂU VỀ MẠNG CẢM BIẾN  
Tìm hiểu về Mạng Cảm Biến  
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 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.  
Tuy nhiên, vì đây là đề tài mang tính chất tìm hiểu, kinh nghiệm trình bày  
một vấn đề, một đề tài chưa có nên chúng em không thể tránh khỏi những thiếu sót.  
Vậy em kính mong quý cô xem xét và góp ý cho em để em có thể hoàn thiện hơn.  
Em xin chân thành cảm ơn.  
Nhóm Sinh Viên thực hiện  
-- 2 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Chương 1:  
SỰ PHÁT TRIỂN CÙA MẠNG CẢM BIẾN  
Khái niệm Wireless Sensor Network (WSN) tương đối còn lạ lẫm đối với  
nhiều người làm việc trong lãnh vực Telecom. Thread này được sử dụng để giới thiệu  
tổng quan về hệ thống WSN và những ứng dụng của WSN (trong quân sự, công nghiệp  
và cuộc sống hằng ngày)  
1. Giới thiệu  
2. Đặc trưng và cấu hình mạng cảm biến  
3. Môt số chuẩn mạng cảm biến  
4. Ứng dụng của mạng cảm biến  
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  
trọng nhất trong mạng cảm biến:  
-- 3 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
- Lớp vật lý (physical layer) tương đối đơn giản, gọn nhẹ do ràng buộc về kích  
thước và khả năng tính toán của node. Kỹ thuật điều chế tín hiệu số : O-QPSK, FSK cải  
thiện hiệu suất bộ khuếch đại công suất. Các kỹ thuật mã hóa sữa sai phức tạp như  
Turbo Codes, LDPC không được sử dụng, kỹ thuật trãi phổ được sử dụng để cải thiện  
SNR ở thiết bị thu và giảm tác động của fading của kênh truyền...  
- Lớp MAC: kỹ thuật đa trua cập TDMA hoặc CSMA-CA hiệu chỉnh với mục  
đích giảm năng lượng tiêu thụ.  
- Routing layer: "power aware" Routing Protocol, geography routing ...  
WSN thường được triển khai trên một phạm vi rộng, số lượng node mạng lớn  
và được phân bố một cách tương đối ngẫu nhiên, các node mạng có thể di chuyển làm  
thay đổi sơ đồ mạng... do vậy WSN đò hỏi 1 sơ đồ mạng (topology) linh động (ad-hoc,  
mesh, star ...) và các node mạng có khả năng tự điều chỉnh, tự cấu hình (auto-  
reconfigurable).  
Trong một số WSN thông dụng (giám sát, cảm biến, môi trường ...) địa chỉ ID  
các node chính là vị trí địa lý và giải thuật routing dựa vào vị trí địa lý này gọi là  
Geography routing protocol (GRT). Đối với mạng với số lượng lớn các node, sơ đồ  
mạng không ổn định ... GRT giúp đơn giản hóa giải thuật tìm đường, giảm dữ liệu bảng  
routing (routing table) lưu trữ tại các node. GRT phù hợp với các WSN cố định, tuy  
nhiên đối với các node di động (địa chỉ ID node thay đổi) giao thức routing trở nên  
phức tạp và không ổn định.  
Cluster hoá: phân chia mạng diện rộng (hàng trăm, hàng ngàn node) thành các  
clusters để ổn định topology của mạng, đơn giản hóa giải thuật routing, giảm đụng độ  
(collission) khi truy cập vào kênh truyền (medium acess) nên giảm được năng lượng  
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...  
-- 4 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
IV. ỨNG DỤNG CỦA MẠNG CẢM BIẾN :  
WSN được ứng dụng đầu tiên trong các lĩnh vực quân sự. Cùng với sự phát  
triển của ngành công nghiệp điều khiển tự động, robotic, thiết bị thông minh, môi  
trường, y tế ... WSN ngày càng được sử dụng nhiều trong hoạt động công nhiệp và dân  
dụng. Một số ứng dụng cơ bản của WSN:  
- Cảm biến môi trường (quân sự: phát hiện mìn, chất độc, dịch chuyển quân  
địch ... công nghiệp: hệ thống chiếu sáng, độ ẩm, phònh cháy, chống rò rỉ ... dân dụng:  
hệ thống điều hòa nhiệt độ, chiếu sáng ... )  
- Điều khiển (quân sự: kích hoạt thiết bị, vũ khí quân sự ... công nghiệp: điều  
khiển tự động các thiết bị, robot ... )  
- Theo dõi, giám sát, định vị (quân sự: định vị, theo dõi sự dịch chuyển thiết bị,  
quân đội ... )  
- Môi trường (giám sát lũ lụt, bão, gió, mưa ... phát hiện ô nhiễm, chất thải ...)  
- Y tế (định vị, theo dõi bệnh nhân, hệ thống báo động khẩn cấp ...)  
- Hệ thống giao thông thông minh: giao tiếp giữa biển báo và phương tiện giao  
thông, hệ thống điều tiết lưu thông công cộng, hệ thống báo hiệu tai nạn, kẹt xe ... hệ  
thống định vị phương, trợ giúp điều khiển tự động phương tiện tiện giao thông...  
- Gia đình (nhà thônh minh: hệ thống cảm biến, giao tiếp và điều khiển các  
thiết bị thông minh ...)  
...  
WSN tạo ra môi trường giao tiếp giữa các thiết bị thông minh, giữa các thiết bị  
thông minh và con người và giao tiếp giữa các thiết bị thông minh và các hệ thống viễn  
thông khác (hệ thống thông tin di động, internet ... )  
-- 5 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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  
và chỉ truyền số liệu đã được xử lý theo yêu cầu.  
Chọn đường trong WSN rất khó khăn do các đặc tính riêng phân biệt những  
mạng này với các mạng vô tuyến khác như các mạng ad-hoc hoặc các mạng tế bào.  
Trước hết, do số lượng nút cảm biến là khá lớn nên không thể xây dựng một quy tắc  
cho địa chỉ toàn cục khi triển khai vì phần điều khiển cho việc thiết lập ID là cao. Vì  
vậy, các giao thức dựa trên IP truyền thống có thể không áp dụng được cho WSN. Thứ  
hai, khác với các mạng thông tin nói chung, hầu hết các ứng dụng của mạng cảm biến  
yêu cầu truyền số liệu cảm biến từ nhiều nguồn tới một nút gốc. Thứ ba, các nút cảm  
biến bị hạn chế về công suất, khả năng xử lý và dung lượng nhớ. Thứ tư, trong hầu hết  
các ứng dụng, các nút trong WSN thường có vị trí cố định. Tuy nhiên, trong một số ứng  
dụng, các nút cảm biến có thể được phép di chuyển và thay đổi vị trí (mặc dù với độ di  
chuyển rất thấp). Thứ năm, các mạng cảm biến thường phụ thuộc vào ứng dụng. Thứ  
sáu, vị trí của các nút cảm biến đóng vai trò quan trọng vì việc lựa chọn số liệu thường  
dựa vào vị trí. Hiện nay chưa thích hợp cho việc sử dụng các phần cứng của hệ thống  
định vị toàn cầu (GPS) cho mục đích này. Các phương pháp xác định vị trí của các nút  
-- 6 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
cảm biến thường dựa vào cường độ tín hiệu từ một số điểm xác định. Cuối cùng, số liệu  
được lựa chọn bởi các nút cảm biến trong WSN thường dựa vào hiện tượng chung, do  
đó sẽ có độ dư thừa. Các giao thức chọn đường phải khắc phục được độ dư thừa này để  
sử dụng hiệu quả băng thông. Tóm lại, phương pháp chọn đường trong WSN cần phải  
quan tâm đến các đặc tính riêng của WSN cùng với các yêu cầu về ứng dụng và cấu  
trúc.  
II. CẤU TRÚC MẠNG CẢM BIẾN VÔ TUYẾN :  
Các nút cảm biến thường được phân bố trong trường cảm biến như hình 1.  
Mỗi nút cảm biến có khả năng thu thập số liệu và chọn đường để chuyển số liệu tới nút  
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  
-- 7 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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.  
Hình 2: Kiến trúc giao thức của mạng cảm biến  
Phần quản lý công suất điều khiển việc sử dụng công suất của nút cảm biến.  
Ví dụ, nút cảm biến có thể tắt khối thu của nó sau khi thu được một bản tin từ một nút  
lân cận. Điều này giúp tránh tạo ra các bản tin giống nhau. Cũng vậy, khi mức công  
suất của nút cảm biến thấp, nút cảm biến phát quảng bá tới các nút lân cận để thông báo  
nó có mức công suất thấp và không thể tham gia vào các bản tin chọn đường. Công suất  
còn lại sẽ được dành riêng cho nhiệm vụ cảm biến. Phần quản lý di động phát hiện và  
ghi lại sự di chuyển của các nút cảm biến để duy trì tuyến tới người sử dụng và các nút  
cảm biến có thể lưu vết của các nút cảm biến lân cận. Nhờ xác định được các nút cảm  
biến lân cận, các nút cảm biến có thể cân bằng giữa công suất của nó và nhiệm vụ thực  
hiện. Phần quản lý nhiệm vụ dùng để làm cân bằng và lên kế hoạch các nhiệm vụ cảm  
biến trong một vùng xác định. Không phải tất cả các nút cảm biến trong vùng đó điều  
phải thực hiện nhiệm vụ cảm biến tại cùng một thời điểm. Kết quả là một số nút cảm  
biến thực hiện nhiệm vụ nhiều hơn các nút khác tuỳ theo mức công suất của nó. Những  
phần quản lý này là cần thết để các nút cảm biến có thể làm việc cùng nhau theo một  
cách thức sử dụng hiệu quả công suất, chọn đường số liệu trong mạng cảm biến di động  
và phân chia tài nguyên giữa các nút cảm biến.  
-- 8 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Chương 3:  
CHỌN ĐƯỜNG TRONG WSN  
I. Thách thức đối với phương pháp chọn đường trong WSN :  
Mặc dù các ứng dụng của mạng WSN là rất lớn, tuy nhiên những mạng này có  
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ề  
vấn đề sử dụng năng lượng và chọn đường.  
Tính không đồng nhất của nút/tuyến: Trong nhiều nghiên cứu, tất cả các nút  
cảm biến được giả thiết là đồng nhất (nghĩa là có khả năng tính toán, khả năng truyền  
tin và có công suất như nhau). Tuy nhiên, tuỳ theo ứng dụng mà nút cảm có thể có vai  
trò hoặc khả năng khác nhau. Các nút cảm biến không đồng nhất tạo ra một số vấn đề  
kỹ thuật liên quan đến chọn đường. Ví dụ, một số ứng dụng có thể cần kết hợp các bộ  
-- 9 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
cảm biến để giám sát nhiệt độ, áp suất, độ ẩm của môi trường, phát hiện chuyển động  
nhờ âm thanh, chụp ảnh hoặc ghi hình các vật chuyển động. Ngoài ra, việc đọc hoặc  
báo cáo số liệu từ những bộ cảm biến này có thể có tốc độ khác nhau tuỳ theo QoS và  
có thể thuộc nhiều mô hình báo cáo số liệu khác nhau. Ví dụ, các giao thức phân cấp  
chỉ rõ nút chủ nhóm khác so với các nút cảm biến bình thường khác. Những nút chủ  
nhóm này có thể được chọn từ các nút cảm biến phân bố hoặc các nút mạnh hơn các nút  
cảm biến khác về công suất, băng thông và bộ nhớ. Do đó, nhiệm vụ truyền tin tới nút  
gốc được tập trung bởi một nhóm các nút chủ nhóm.  
Khả năng chống lỗi: Một số nút cảm biến có thể bị lỗi hoặc bị ngắt do thiếu  
công suất, hỏng phần cứng hoặc bị nhiễu môi trường. Sự cố của các nút cảm biến  
không được ảnh hưởng tới nhiệm vụ của toàn mạng cảm biến. Nếu có nhiều nút bị lỗi,  
các giao thức chọn đường hoặc điều khiển truy nhập môi trường (MAC) phải thành cập  
các tuyến mới tới nút gốc. Việc này có thể cần thiết phải điều chỉnh công suất phát và  
tốc độ tín hiệu trên các tuyến hiện tại để giảm sự tiêu thụ năng lượng hoặc là các gói  
phải chọn đường lại qua các vùng mạng có công suất khả dụng lớn hơn.  
Khả năng định cỡ: số lượng nút cảm biến có thể là hàng trăm, hàng nghìn  
hoặc nhiều hơn. Bất kỳ phương pháp chọn đường nào cũng phải có khả năng làm việc  
với một số lượng lớn các nút cảm biến như vậy.  
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  
-- 10 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
này được sử dụng để đạt hiệu quả về năng lượng và tối ưu hoá việc truyền số liệu trong  
một số giao thức chọn đường.  
Chất lượng dịch vụ: Trong một số ứng dụng, số liệu có thể được phân phối  
trong một khoảng thời gian xác định ngay khi nó cảm nhận được hiện tượng nếu không  
số liệu sẽ trở nên vô dụng. Vì vậy, giới hạn trễ của việc phân phối số liệu là một chỉ tiêu  
khác trong các ứng dụng phụ thuộc thời gian. Tuy nhiên trong một số ứng dụng khác  
thì việc tiêu thụ công suất (ảnh hưởng trực tiếp đến thời gian sống của mạng) lại quan  
trọng hơn. Khi năng lượng gần hết, mạng có thể yêu cầu giảm chất lượng các kết quả  
để giảm mức tiêu thụ năng lượng của nút và kéo dài thời gian sống của toàn mạng.  
II.Phân loại và so sánh các giao thức chọn đường trong WSN  
Nói chung, việc chọn đường trong WSN có thể được chia thành chọn đường  
ngang hàng, chọn đường phân cấp và chọn đường dựa theo vị trí tuỳ thuộc vào cấu trúc  
mạng. Trong chọn đường ngang hàng, tất cả các nút thường có vai trò hoặc chức năng  
như nhau. Trong chọn đường phân cấp, các nút sẽ đóng vai trò khác nhau trong mạng.  
Trong chọn đường dựa theo vị trí thì vị trí của các nút cảm biến được sử dụng để chọn  
đường số liệu. Một giao thức chọn đường được coi là thích ứng nếu các tham số của hệ  
thống có thể điều khiển được để thích ứng với các trạng thái mạng hiện tại và các mức  
năng lượng khả dụng. Những giao thức này cũng có thể được chia thành các giao thức  
chọn đường đa đường, yêu cầu, hỏi/đáp, liên kết hoặc dựa vào QoS tuỳ theo cơ chế  
hoạt động của giao thức. Ngoài ra, các giao thức chọn đường có thể được chia thành ba  
loại là chủ động, tương tác hoặc lai ghép tuỳ thuộc vào cách thức mà nguồn tìm đường  
tới đích. Trong các giao thức chủ động, tất cả các đường được tính toán trước khi có  
yêu cầu, trong khi đối với các giao thức tương tác thì các đường được tính toán theo  
yêu cầu. Các giao thức lai ghép kết hợp cả hai quy tắc ở trên. Khi các nút cảm biến cố  
định, nó thích hợp với các giao thức chọn đường theo bảng hơn là với các giao thức  
tương tác. Một lượng công suất đáng kể được sử dụng để tìm đường và thiết lập các  
giao thức tương tác. Một số giao thức khác dựa vào định thời và thông tin vị trí. Để  
khái quát, có thể sử dụng phân loại theo cấu trúc mạng và cơ chế hoạt động của giao  
thức (tiêu chuẩn chọn đường) . Việc phân loại và so sánh các giao thức chọn đường  
trong WSN được chỉ ra trong hình 3 và bảng 1.  
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  
-- 11 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
-- 12 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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)  
trong đó P là tỷ lệ phần trăm nút chủ, r chu kỳ hiện thời, và G là tập các nút  
không được lựa chọn là nút chủ trong 1/P chu kỳ cuối cùng. Sau khi các nút chủ được  
lựa chọn, những nút này sẽ thông báo tới tất cả các nút cảm biến trong mạng rằng  
chúng là các nút chủ mới. Khi các nút cảm biến thu được thông báo, chúng xác định  
nhóm mà chúng sẽ tham gia dựa theo cường độ tín hiệu của thông báo từ các nút chủ  
tới các nút cảm biến. Những nút cảm biến này sẽ khai báo với nút chủ thích hợp rằng  
chúng sẽ là thành viên của nhóm. Sau đó các nút chủ ấn định thời gian cho các nút cảm  
biến gửi số liệu tới các nút chủ theo phương pháp TDMA.  
Trong bước ổn định, các nút cảm biến có thể bắt đầu truyền số liệu tới các nút  
chủ. Các nút chủ cũng tập hợp số liệu từ các nút trong nhóm của nó trước khi gửi  
những số liệu này tới nút gốc. Sau một thời gian quy định cho bước ổn định, mạng lại  
tiếp tục bước thiết lập và bước sang một chu kỳ khác trong việc lựa chọn nút chủ  
Mô hình hoá  
Việc mô phỏng giao thức LEACH được thực hiện bằng phần mềm Visual C++  
vì đây là một ngôn ngữ lập trình mạnh Thuật toán mô phỏng dựa vào cơ chế hoạt động  
của giao thức phân cấp nhóm thích ứng công suất thấp (LEACH) là sử dụng bước phân  
nhóm trước khi truyền số liệu. Một nút cảm biến được chọn làm nút chủ nhóm và sẽ  
truyền tất cả số liệu của các nút cảm biến thuộc nhóm đó tới nút gốc. Đây là điểm khác  
biệt so với các phương pháp thông thường mà mỗi nút cảm biến sẽ truyền trực tiếp tới  
nút gốc. Giao thức LEACH giúp kéo dài thời gian sống của mạng bằng cách tối thiểu  
hoá năng lượng sử dụng của mỗi nút cảm biến nhờ vào việc kết hợp số liệu  
Lưu đồ quá trình thiết lập như sau:  
-- 13 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Lưu đồ quá trình ổn định như sau:  
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.  
-- 14 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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.  
-- 15 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Tổng quát :  
Các đặc tính như độ linh động, chi phí thấp, triển khai nhanh chóng... của các  
mạng cảm biến đã tạo ra rất nhiều ứng dụng mới. Trong tương lai, phạm vi ứng dụng  
rộng lớn này sẽ làm cho các mạng cảm biến trở thành một phần quan trọng trong cuộc  
sống của chúng ta. Tuy nhiên, việc thực hiện các mạng cảm biến cần phải giải quyết  
được các vấn đề về khả năng chống lỗi, định cỡ, chi phí, phần cứng, thay đổi cấu hình ,  
môi trường và công suất. Do những giới hạn chặt chẽ và mang tính đặc thù của các  
mạng cảm biến nên cần thiết phải có các kỹ thuật mạng vô tuyến đặc biệt (ad-hoc) mới.  
Chọn đường trong các mạng cảm biến là một lĩnh vực mới, các kết quả nghiên  
cứu còn chưa nhiều nhưng đang rất được quan tâm phát triển. Những kỹ thuật này có  
mục tiêu chung là kéo dài thời gian sống của mạng. Các giao thức chọn đường được  
phân loại dựa vào cấu trúc mạng gồm có các giao thức chọn đường ngang hàng, phân  
cấp và theo vị trí. Ngoài ra, các giao thức chọn đường còn được phân loại theo đa  
đường, theo yêu cầu, theo hỏi/đáp và theo QoS phụ thuộc vào cơ chế hoạt động của nó.  
Các kết quả mô phỏng giao thức LEACH của mạng WSN cho thấy đây là một  
phương pháp chọn đường phân cấp có khả năng tiết kiệm được công suất sử dụng và  
kéo dài thời gian sống của mạng cảm biến. Tuy nhiên, cơ chế hoạt động của giao thức  
LEACH là lựa chọn số liệu được tập trung và thực hiện theo chu kỳ. Do đó, giao thức  
này chỉ thích hợp với yêu cầu giám sát liên tục bởi mạng cảm biến. Với ứng dụng mà  
người sử dụng không cần tất cả số liệu ngay lập tức thì việc truyền số liệu theo chu kỳ  
là không cần thiết và có thể làm tiêu tốn năng lượng vô ích. Giao thức LEACH cần tiếp  
tục được cải tiến để khắc phục hạn chế này.  
-- 16 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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.  
Hình 1: Cấu trúc mạng cảm biến không dây phân nhóm  
-- 17 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Như vậy, việc phân nhóm hình thành nên một cấu trúc phân cấp 2 mức mà ở  
đó các nút chính hình thành nên một bậc cao còn các nút thành viên của nhóm thuộc về  
một bậc thấp hơn.  
Lưu ý rằng, các nút trong một nhóm không truyền số liệu mà chúng thu thập  
được về trực tiếp trạm gốc mà phải thông qua nút chính của nhóm. Nút chính có nhiệm  
vụ:  
Điều phối hoạt động giữa các nút trong nhóm và thu thập số liệu của các nút  
(Vì các nút có thể tạo ra các số liệu trùng lặp và thừa. Số liệu giống nhau từ nhiều nút  
có thể được tập hợp lại, sắp xếp, lọc loại bỏ số liệu thừa trùng lặp với mục đích giảm số  
lần truyền dẫn).  
Truyền trực tiếp các số liệu đã được tập hợp, tinh lọc về trạm gốc hoặc  
thông qua truyền dẫn nhiều chặng (multi-hop) nghĩa là qua các nút chính khác.  
Trên thực tế, thông tin trao đổi giữa các nút trong một nhóm cũng như giữa  
các nhóm khác nhau có thể được tổ chức như là một sự kết hợp giữa trao đổi thông tin  
một chặng (one-hop) và nhiều chặng. Ở trao đổi thông tin bằng một chặng, tất cả các  
nút cảm biến đều có thể trực tiếp truyền số liệu về đích, trong khi đó ở trao đổi thông  
tin qua nhiều chặng, các nút có phạm vi truyền dẫn hạn chế và do đó buộc phải định  
tuyến việc truyền số liệu của chúng qua một số chặng cho đến khi số liệu được truyền  
tới đích. Trong cả hai phương thức, có một vấn đề không thể tránh được đó là sự phân  
bố năng lượng tiêu thụ không đều giữa các nút. Điều này dẫn đến tình trạng một số nút  
bị mất năng lượng với tốc độ cao hơn, nhanh bị dừng hoạt động hơn một số nút khác và  
có thể làm giảm phạm vi cảm biến và chia cắt mạng. Đối với trao đổi thông tin một  
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.  
-- 18 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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:  
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.  
II. PHÂN LOẠI CÁC KỸ THUẬT PHÂN NHÓM TRONG CÁC  
MẠNG CẢM BIẾN KHÔNG DÂY :  
Như đã phân tích ở trên, chúng ta thấy các nút chính thường phải truyền số  
liệu qua những khoảng cách xa và xử lý nhiều công việc khác nhau trong nhóm, nên  
chúng thường mất nhiều năng lượng hơn các nút thành viên khác. Do vậy mạng phải tái  
phân nhóm định kỳ để lựa chọn các nút có dư thừa năng lượng hơn làm nút chính của  
các nhóm và phân bố lưu lượng tải đều hơn cho toàn bộ các nút. Ngoài việc đạt được  
hiệu quả về sử dụng năng lượng, phân nhóm còn làm giảm sự tranh chấp kênh, xung  
đột gói và làm cho thông lượng của mạng tốt hơn ngay cả khi có lưu lượng tải cao.  
Phân nhóm được xem như là một giải pháp làm cải thiện “thời gian hoạt động  
của mạng” – một tham số cơ bản cho việc đánh giá hiệu năng của một mạng cảm biến.  
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  
-- 19 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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  
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.  
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í:  
Các tham số được sử dụng cho việc lựa chọn các nút chính.  
Bản chất thực thi của một thuật toán phân nhóm (theo xác suất hay lặp).  
II.1. Lựa chọn các nút chính  
Một loại trong số các kỹ thuật phân nhóm sử dụng nhận dạng của nút để lựa  
chọn các nút chính.  
Sự thành công của hướng tiếp cận này phụ thuộc vào hai giả thiết:  
Tất cả các nút đều có một nhận dạng duy nhất  
Những nhận dạng này được phân bố đều trong toàn mạng  
Do các nút chính duy trì và quyết định cấu hình của các mạng cảm biến nên  
việc lựa chọn tối ưu các nút chính là một vấn đề hết sức quan trọng. Trong mô hình của  
[1, 2], các tác giả thiên về lựa chọn các nút có chỉ số nhận dạng thấp thành các nút  
chính. Phương thức tiếp cận này có thể không phù hợp cho những mạng cảm biến có  
năng lượng giới hạn bởi vì nó tập trung chuyên vào một số lượng nhỏ các nút có chỉ số  
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],  
-- 20 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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  
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 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ặc nghỉ tạm thời phụ thuộc vào kết nối  
giữa nó với các nút hai chặng lân cận.  
Mặc dầu những giao thức này không thuộc các kỹ thuật phân nhóm, nhưng  
ảnh hưởng của chúng lên cấu hình mạng tương tự như các kỹ thuật phân nhóm.  
II.2. Thực thi của một thuật toán phân nhóm  
Việc thực thi một thuật toán phân nhóm có thể được tiến hành tại một căn cứ  
trung tâm (ví dụ như tại một trạm gốc) hoặc theo cách thức phân tán tại các nút nội bộ.  
Hướng tiếp cận tập trung thường yêu cầu thông tin về cấu hình mạng. Phương thức  
phân nhóm kinh điển K-Means (được đề xuất trong các tài liệu xử lý số liệu) có thể  
được áp dụng nếu số các nhóm yêu cầu có thể được xác định trước và các vị trí của nút  
là hiện hữu. Trong trường hợp này, một tập hợp ngẫu nhiên ban đầu của các nhóm được  
lựa chọn và một nút được chuyển đi từ một nhóm này sang các nhóm khác nếu sự di  
dời này làm giảm chức năng chi phí mục tiêu ban đầu cho toàn hệ thống. Banerjee at.  
al. [10] đề xuất một kỹ thuật tập trung mà không yêu cầu biết trước các vị trí của nút.  
Kỹ thuật của họ dựa trên việc xây dựng một cây mở rộng (spanning tree) của các nhóm  
-- 21 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
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  
gói. Ví dụ, nếu một nút u phát hiện thấy một trong số các nút lân cận với nó - nút v có  
trọng số cao hơn, thì nút u sẽ đợi nút v quyết định trước khi nó đưa ra quyết định. Nếu  
nút v hỏng ngay sau pha phát hiện của các nút lân cận, nút u sẽ đợi nút v vô thời hạn để  
đưa ra quyết định của chính nó.  
Thuật toán DCA khá phù hợp với những mạng mà ở đó các nút là tĩnh hoặc di  
chuyển với tốc độ rất chậm. Thuật toán phân nhóm phân tán và thích ứng di động –  
DMAC (The Distributed and Mobility-Adaptive Clustering Algorithm) [12] thay đổi  
thuật toán DCA để cho phép các nút di chuyển trong hoặc trước giai đoạn thiết lập  
nhóm.  
Thuật toán DCA và DMAC tạo ra các nhóm 1 chặng, yêu cầu các tín hiệu  
đồng hồ đồng bộ và có độ phức tạp O(n). Điều này làm cho chúng chỉ phù hợp với các  
mạng có số lượng nút nhỏ.  
Để cải thiện các vấn đề nêu trên, một số giao thức thiết lập một giới hạn về số  
các lần lặp cho mỗi một nút. Ví dụ, ở ACE [7], khi một nút thực hiện xong một số lần  
lặp (5 lần chẳng hạn) dựa trên bậc của nút như là một tham số chính, nó đưa ra một  
quyết định dựa trên thông tin hiện có. Các lần lặp này là đủ để có được kích cỡ nhóm  
trung bình ổn định.  
-- 22 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Giao thức ở [4], cho phép một nhóm bao gồm các nút có D chặng cách xa nút  
chính và một nút thường thực hiện 2D lần lặp trước khi đưa ra một quyết định. Điều  
này dẫn đến một số lần lặp không đổi cho hội tụ. Thuật toán Max-Min D cluster đề xuất  
bởi các tác giả của [4] đạt được sự cân bằng tải tốt hơn giữa các nút chính, tạo ít nhóm  
hơn hơn so với một số thuật toán khác như LCA (Linked Cluster Algorithm) [1] và  
LCA2 [2]. Tuy nhiên, thuật toán này không đảm bảo năng lượng sử dụng trong trao đổi  
thông tin tới trung tâm thông tin được tối thiểu hóa.  
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òng hiện tại. Giá trị ngưỡng được tính toán dựa trên một biểu thức toán học có sự kết  
hợp phần trăm mong muốn trở thành nút chính, vòng hiện tại, và tập hợp các nút chưa  
được lựa chọn làm nút chính ở vòng trước đó – tập G. T(n) được xác định:  
-- 23 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Tất cả các nút chính được lựa chọn phát quảng bá một bản tin thông báo tới tất  
cả các nút còn lại trong mạng rằng chúng là các nút chính mới. Các nút khác, không  
phải là nút chính sau khi nhận được bản tin thông báo này sẽ quyết định thuộc về một  
nhóm nào đó mà chúng muốn. Quyết định này dựa trên cường độ tín hiệu của bản tin  
thông báo. Các nút không phải là nút chính sẽ thông báo cho các nút chính thích ứng  
rằng chúng sẽ là thành viên của nhóm. Sau khi thu nhận được tất cả các bản tin từ các  
nút muốn gia nhập nhóm và dựa trên số lượng các nút thành viên của nhóm, nút chính  
sẽ tạo ra một định thời TDMA, và cấp cho mỗi nút một khe thời gian khi nó truyền  
phát. Định thời (Schedule) được quảng bá tới tất cả các nút của nhóm.  
Trong giai đoạn ổn định trạng thái, các nút cảm biến bắt đầu cảm biến và  
truyền phát số liệu về các nút chính. Các nút chính, sau khi thu tất cả các số liệu, tập  
hợp chúng lại trước khi gửi đến trạm gốc. Sau một khoản thời gian nhất định nào đó  
được xác định trước, mạng sẽ quay trở lại trạng thái thiết lập và bắt đầu một vòng lựa  
chọn các nút chính mới. Ở đây các nhóm trao đổi thông tin với nhau bằng việc sử dụng  
các mã CDMA để giảm nhiễu từ các nút thuộc các nhóm khác.  
LEACH cung cấp một mô hình tốt mà các thuật toán nội bộ và tập hợp dữ liệu  
có thể được thực hiện trong các nút chính được lựa chọn một cách ngẫu nhiên. Điều  
này làm giảm quá tải thông tin và cung cấp một tập hợp tin cậy các số liệu cho người sử  
dụng cuối cùng. Các tác giả của LEACH cũng đã chỉ ra rằng LEACH góp phần giảm  
đáng kể năng lượng tiêu thụ và kéo dài hơn thời gian hoạt động của mạng cảm biến so  
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ị  
-- 24 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
thiết bị GPS chẳng hạn và tất cả các nút được phân nhóm là quan trọng như nhau. Mục  
đích chính của HEED là kéo dài thời gian hoạt động của mạng. Thời gian hoạt động  
của mạng được định nghĩa như là khoảng thời gian cho đến khi nút đầu tiên (hoặc cuối  
cùng) trong mạng dùng hết năng lượng của nó. Để đạt được mục đích này, HEED sử  
dụng phương thức tiếp cận xác suất để lựa chọn các nút chính có năng lượng dư thừa  
cao (so sánh với các nút thông thường) với số lần lặp không đổi.  
Một nút được sắp xếp vào một nhóm và phải có khả năng trao đổi thông tin  
với nút chính của nhóm qua một chặng bằng việc sử dụng phạm vi truyền dẫn bên trong  
nhóm, Rc, Rc tương ứng với mức công suất Pc. Định tuyến giữa các nhóm sử dụng phạm  
vi truyền dẫn lớn hơn, Rt, (Rt > Rc) và tương ứng với mức công suất Pt.  
Lựa chọn nút chính dựa vào hai tham số: tham số thứ nhất (năng lượng dư của  
nút) được sử dụng để lựa chọn một tập hợp ban đầu các nút chính, và tham số thứ hai  
được sử dụng để phá vỡ những sự ràng buộc. Sự ràng buộc xuất hiện khi có hai nút  
trong phạm vi Rc thông báo cho nhau về sự sẵn sàng trở thành nút chính. Tham số thứ  
hai này có thể được thiết lập cho việc ước lượng “chi phí” trao đổi thông tin trong  
nhóm, “chi phí” này là hàm của mật độ nhóm và quan hệ lân cận.  
Một nút thường thiết lập ban đầu xác suất của nó để trở thành nút chính  
ở đây Eresidual là năng lượng dư ước chừng của nút, Emax là năng lượng tối đa  
tham chiếu và Cprob là một hằng số nhỏ không đổi được sử dụng để giới hạn số các  
thông báo của nút chính ban đầu.  
CHprob không được phép thấp hơn một giá trị xác suất nhỏ pmin, để đảm bảo kết  
cuối thời gian không đổi. Trong mỗi một hoạt động lặp, một nút thường phân xử lựa  
chọn trong số các thông báo của nút chính mà nó thu được để lựa chọn nút chính có chi  
phí thấp nhất. Nếu nó không nhận được bất kỳ một thông báo nào, nó sẽ tự chọn nó trở  
thành nút chính với xác suất CHprob. Nếu thành công, nó gửi đi một thông báo nói về sự  
“sẵn sàng” trở thành nút chính. Tiếp đó nút sẽ gấp đôi giá trị xác suất CHprob, chờ trong  
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ỏ.  
-- 25 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Tuy nhiên, như các tác giả nhận định, việc lựa chọn thăm dò các nút chính là ngẫu  
nhiên và dựa trên năng lượng dư của các nút. Do vậy mà HEED không thể đảm bảo lựa  
chọn được tối ưu các nút chính về mặt năng lượng, và cũng như đối với số nhóm trong  
mạng và số nút trong một nhóm.  
Kuhn et. al. [3] đã đề xuất một kỹ thuật xác suất để lựa chọn các nút chính mà  
ở đó xác suất lựa chọn phụ thuộc vào bậc của nút. Sự hội tụ của kỹ thuật đề xuất bởi  
các tác giả phụ thuộc vào số nút ở trong mạng và bậc của nút là nhanh hơn rất nhiều so  
với các kỹ thuật lặp. Thêm vào đó phương thức tiếp cận này lựa chọn một tổ hợp chi  
phối của các nút chính gần tối ưu.  
Trên thực tế, trong khi và ngay sau khi triển khai một mạng cảm biến, không  
có một mô hình được thiết lập trước nào mà dựa vào đó các nút có thể trao đổi thông tin  
hiệu quả với nhau. Hay nói cách khác, sự không biết đầy đủ về cấu trúc của mạng (các  
nút không biết gì về các nút lân cận cũng như số lượng) là một đặc tính của mạng cảm  
biến vô tuyến trong khi được triển khai.  
Sự chuyển tiếp quá độ theo hướng tự tổ chức từ mạng không có cấu trúc sang  
mạng có cấu trúc được gọi là giai đoạn “khởi tạo” (Initialization). Thuật toán phân  
nhóm đề xuất bởi các tác giả của [3] đã lần đầu tiên quan tâm đến pha “khởi tạo” mạng  
với giả thiết mạng có nhiều chặng, không có phát hiện xung đột, các nút được triển khai  
không đồng bộ và do đó không phải truy nhập tới hệ thống đồng hồ đồng bộ chung.  
Đối với mô hình mạng ở giai đoạn khởi tạo, tập hợp các nút chính chi phối  
được xác định trong khoảng thời gian polylog(ñ), với ñ là giới hạn trên cho trước về số  
nút có trong hệ thống. Tuy nhiên, kỹ thuật phân nhóm của [3] hiện tại chỉ phù hợp với  
mô hình mạng cảm biến tĩnh, câu hỏi làm thế nào duy trì các nhóm có hiệu quả khi mà  
các nút di động vẫn đang là vấn đề mở cần phải giải quyết.  
Bảng 1 so sánh các ví dụ đại diện của các kỹ thuật phân nhóm phân bố. (lưu ý  
rằng một số các kỹ thuật khác đã được đề xuất trong một số các tài liệu liên quan ,  
nhưng không được thảo luận ở đây do giới hạn không gian) . Bảng 1 chỉ ra rằng, tất cả  
các giao thức phân nhóm phân tán có tổng phí trao đổi bản tin là không đổi cho một  
nút. Đây là một ưu điểm quan trọng của các kỹ thuật phân tán so với các kỹ thuật phân  
nhóm tập trung. Việc xử lý tính toán tổng chi phí của mỗi một mạng cảm biến là không  
đáng kể đối với phương thức tập trung khi so với phương thức phân tán mà ở đó các nút  
thường tham gia vào sự tính toán. Ví dụ ở các phương thức tiếp cận lặp, một nút phải  
kiểm tra các bản tin thu được để quyết định việc nó nên phản ứng lại như thế nào.  
Lượng các bản tin này tỷ lệ với O(δ ) δ là bậc của nút. Do năng lượng tiêu  
thụ cho xử lý số liệu thường thấp hơn cho trao đổi thông tin, tổng chi phí xử lý các bản  
tin có thể bỏ qua.  
Như đã được minh họa trong Bảng 1, phần lớn các giao thức phân tán có tổng  
chi phí thấp. Tổng chi phí này phụ thuộc vào tần suất phân nhóm lại mà thường nhỏ  
trong các áp dụng thông thường. Thông lượng (throughput) thường không bị ảnh hưởng  
tiêu cực bởi việc phân nhóm như đã được chỉ ra trong quá trình thực hiện nghiên cứu  
của HEED [6]. Thực chất, thông lượng được cải thiện khi lưu lượng tải cao bởi vì sự  
giảm tranh chấp kênh. Hiệu năng của mỗi một giao thức phân nhóm phụ thuộc vào cấu  
hình của mạng, mô hình hệ thống và tình huống áp dụng.  
Bảng 1: So sánh các kỹ thuật phân nhóm phân tán điển hình  
-- 26 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Chú thích: I/P chỉ ra giao thức có tính lặp hay xác suất, Diam là đường kính  
của mạng và n là  
3. KẾT LUẬN  
Các kỹ thuật phân nhóm trong mạng cảm biến vô tuyến là những phương thức  
quản lý cấu hình mạng hiệu quả, góp phần làm giảm chi phí trao đổi thông tin, duy trì  
mạng hoạt động trong thời gian dài. Trong thời gian tới, chúng tôi sẽ tập trung tìm hiểu  
về các cách thức tính toán kích cỡ tối ưu của một nhóm, xác định tần suất hoán chuyển  
tối ưu vai trò làm nút chính giữa các nút trong mạng cảm biến …nhằm tối đa thời gian  
hoạt động của mạng cảm biến vô tuyến.  
-- 27 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Nhận Xét Của Giáo Viên Hướng Dẫn  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
……………………………………………………………………………………  
…………………………………………………….  
-- 28 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
Tìm hiểu về Mạng Cảm Biến  
Mục Lục  
Lời nói đầu  
02  
Chương 1:SỰ PHÁT TRIỂN CÙA MẠNG CẢM BIẾN  
03  
03  
03  
04  
05  
06  
06  
07  
07  
I. GIỚI THIỆU  
II. ĐẶC TRƯNG VÀ CẤU HÌNH MẠNG CẢM BIẾN :  
III. MÔT SỐ CHUẨN MẠNG CẢM BIẾN  
IV. ỨNG DỤNG CỦA MẠNG CẢM BIẾN  
Chương 2: CẤU TRÚC & KIẾN TRÚC GIAO THỨC  
I. GIỚI THIỆU :  
II. CẤU TRÚC MẠNG CẢM BIẾN VÔ TUYẾN :  
III. KIẾN TRÚC GIAO THỨC MẠNG  
Chương 3:CHỌN ĐƯỜNG TRONG WSN  
09  
09  
11  
13  
I. Thách thức đối với phương pháp chọn đường trong WSN  
II.Phân loại và so sánh các giao thức chọn đường trong WSN  
III. Đánh giá chỉ tiêu giao thức chọn đường LEACH  
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  
17  
17  
II. PHÂN LOẠI CÁC KỸ THUẬT PHÂN NHÓM TRONG CÁC MẠNG CẢM  
BIẾN KHÔNG DÂY  
2.1. Lựa chọn các nút chính  
2.2. Thực thi của một thuật toán phân nhóm  
II.2.a. Các kỹ thuật phân nhóm lặp  
II.2.b. Các kỹ thuật phân nhóm có tính xác suất  
3. KẾT LUẬN  
19  
20  
21  
22  
23  
27  
-- 29 --  
GVHD: Lê Nguyễn Mai Duyên  
Lớp:K12T3  
pdf 29 trang yennguyen 25/03/2025 120
Bạn đang xem tài liệu "Đồ án Tìm hiểu về mạng cảm biến", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pdfdo_an_tim_hieu_ve_mang_cam_bien.pdf