ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
HOÀNG TIẾN LONG

PHÂN CỤM NÚT MẠNG CẢM BIẾN KHÔNG DÂY
VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN, THÁNG 10 NĂM 2015

1
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn “Phân cụm nút mạng cảm biến không dây và
ứng dụng” là công trình nghiên cứu của riêng tôi, đƣợc sự giúp đỡ và hƣớng dẫn
tận tình của thầy giáo PGS TS Lê Bá Dũng.
Trong thời gian làm luận văn này, tôi đã nhận đƣợc sự chỉ bảo nhiệt tình của
thầy giáo, chính vì sự nhiệt tình đó của thầy đã giúp tôi hoàn thành tốt luận văn
này.
Các số liệu và kết quả trong luận văn của tôi bao gồm các công thức và hình
ảnh mô tả các quá trình phân chia, năng lƣợng còn lại và thời gian sống hay sự
tồn tại của mạng (cảm biến không dây). Đây là kết quả một quá trình làm việc
nhiệt tình nghiêm túc của thầy và trò tạo cơ sở thực tiễn.
Thái nguyên, ngày 10 tháng 5 năm 2015

Hoàng Tiến Long



MỤC LỤC
LỜI CAM ĐOAN................................................................................................... 1
LỜI CẢM ƠN ........................................................................................................ 2
MỤC LỤC .............................................................................................................. 3
DANH MỤC BẢNG BIỂU ................................................................................... 5
DANH MỤC HÌNH VẼ ......................................................................................... 6
DANH MỤC CHỮ VIẾT TẮT.............................................................................. 8
Chƣơng 1: KHÁI QUÁT VỀ MẠNG CẢM BIẾN KHÔNG DÂY VÀ BÀI
TOÁN ĐỊNH TUYẾN ......................................................................................... 14
1.1: Khái quát về mạng cảm biến không dây ....................................................... 14
1.1.1: Giới thiệu mạng cảm biến không dây ......................................................... 15
1.1.2: Cấu trúc mạng cảm biến không dây ............................................................ 15
1.1.2.1: Cấu trúc một nút mạng cảm biến không dây ........................................... 15
1.1.2.2: Cấu trúc mạng cảm biến không dây ......................................................... 17
1.1.3: Mô hình mạng cảm biến không dây. ........................................................... 19
1.1.4: Đánh giá ƣu nhƣợc điểm của mạng cảm biến không dây ........................... 20
1.1.4.1: Ƣu điểm của mạng cảm biến không dây. ................................................ 20
1.1.4.2: Nhƣợc điểm của mạng cảm biến không dây ............................................ 23
1.1.5: Ứng dụng trong mạng cảm biến không dây ................................................ 24
1.2: Bài toán định tuyến trong mạng cảm biến không dây ................................... 25
1.2.1: Bài toán ....................................................................................................... 25
1.2.2: Công thức .................................................................................................... 25
Chƣơng 2: CÁC GIAO THỨC TRONG MẠNG CẢM BIẾN KHÔNG DÂY. .. 26
2.1: Các kỹ thuật định tuyến trong mạng cảm biến không dây..............................26
2.1.1: Kỹ thuật mạng kiến trúc mạng phẳng ..........................................................26
2.1.2: Kỹ thuật mạng tiết kiệm năng lƣợng ...........................................................27
2.1.3: kỹ thuật phƣơng pháp phân bổ .....................................................................27
4
Số hóa bởi Trung tâm Học liệu - ĐHTN

Hòa Bình................................................................................................................ 52
5
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

3.3: Mô phỏng quá trình thu nhập của mạng cảm biến không dây cho xử lý số
liệu nhà máy thủy điện trên cơ sở phân cấp, phân cụm, các nút mạng với quá
trình giảm thiểu năng lƣợng tiêu hao trong mạng. ............................................... 53
3.4: Phân cụm trong mạng cảm biến không dây. ................................................. 54
3.4.1: Phân tích năng lƣợng tiêu thụ trên mạng .................................................... 54
3.4.2: Phân cụm phân cấp các nút mạng cảm biến với năng lƣợng tiêu thụ nhỏ.. 56
3.5: Mô phỏng quá trình phân cụm và trọn cụm chủ. .......................................... 60
Kết luận và hƣớng phát triển. ................................................................................ 67
Tài liệu tham khảo ................................................................................................. 68

6
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

DANH MỤC BẢNG
Bảng 3.1: Các thông số ban đầu của hệ thống mạng. .......................................... 61
Bảng 3.2: Năng lƣợng cho từng trƣờng hợp. ....................................................... 66

7
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>



Hình 3.13a: Minh họa mô hình các nút mạng cảm biến trong hầm turbin không
phân cụm. ............................................................................................................. 61
Hình 3.13b: Minh họa mô hình thời gian sống của các nút mạng qua 300 vòng
thiết lập cụm. ........................................................................................................ 62
Hình 3.13c: Minh họa mô hình năng lƣợng còn lại trung bình trên mạng ........... 62
Hình 3.14a: Các nút mạng cảm biến trong hầm turbin đƣợc chia thành 2 cụm. 63
Hình 3.14b: Minh họa mô hình thời gian sống của mạng. ................................... 63
Hình 3.14c: Minh họa mô hình năng lƣợng còn lại của các nút mạng. ............... 64
Hình 3.15a: Minh họa mô hình mạng cảm biến trong hầm chia thành 3 cụm. .... 64
Hình 3.15b: Minh họa mô hình thời gian sống của các nút mạng. ...................... 65
Hình 3.15c: Minh họa mô hình năng lƣợng các nút mạng và giá trị trung bình
của các nút mạng. ................................................................................................. 65

9
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

CHỮ VIẾT TẮT

Từ viết tắt

Nghĩa tiếng việt

Từ gốc

WSN

Wireless Sensor Networks


Personal Area Network

Mạng cá nhân

MAC

Media Access Control

Điều khiển truy cập kênh
truyền

FFDs

Full Functional Dependencien

Chức năng đầy đủ

RFDs

Reduced-function Devices

Thiết bị có chức năng hạn
chế

SEA

Spokesman Election Algorithm

Thuật toán

Mạng không dây cá nhân

WLANs

Wireless Local Area Network

Mạng không dây nội bộ

MANET

Mobile Ad-hoc Network

Mạng tùy biến di động
10

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

ADC

Analog Digital Converter

Chuyển đổi tƣơng tự - số

LFS

Location Filding System

Hệ thống định vị


Giao thức định tuyến với
chi phí nguồn nhỏ nhất

EAR

Energy Aware

Giao thức định tuyến nhận
thức về năng lƣợng

Energy-Aware Spanning Tree

Giao thức định tuyến E-

Ailgorithm

Span

BRE

Bursty Routing Extensisons

Giao thức định tuyến BRE

BCTP

Balanced Collection Tree Protocol

Giao thức định tuyến BCTP


ứng năng lƣợng thấp

11
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

MỞ ĐẦU
Mạng cảm biến không dây (Wireless Sensor Network) Bao gồm một tập
hợp các thiết bị cảm biến sử dụng các liên kết không dây nhƣ (vô tuyến, hồng
ngoại hoặc quang học) để phối hợp thực hiện nhiệm vụ thu thập thông tin dữ
liệu phân tán với quy mô lớn trong bất kỳ điều kiện và ở bất kỳ vùng địa lý nào.
Mạng cảm biến không dây có thể liên kết trực tiếp với nút quản lý giám sát trực
tiếp nó, hay gián tiếp thông qua một điểm thu phát nút (Sink) và môi trƣờng
mạng công cộng nhƣ Internet hay vệ tinh. Các nút cảm biến không dây có thể
đƣợc triển khai cho các mục đích chuyên dụng nhƣ: Điều khiển giám sát và an
ninh, kiểm tra môi trƣờng, tạo ra không gian sống thông minh, khảo sát đánh giá
chính xác trong nông nghiệp, trong lĩnh vực y tế, quân sự .... Lợi thế chủ yếu của
chúng là khả năng triển khai hầu nhƣ trong bất kỳ loại hình địa lý nào kể cả các
môi trƣờng nguy hiểm không thể sử dụng mạng cảm biến có dây truyền thống.
Các thiết bị cảm biến không dây liên kết thành một mạng đã tạo ra nhiều khả
năng mới cho con ngƣời. Các đầu đo với bộ vi xử lý và các thiết bị vô tuyến rất
nhỏ gọn tạo nên một thiết bị cảm biến không dây có kích thƣớc rất nhỏ, tiết kiệm
về không gian. Chúng có thể hoạt động trong môi trƣờng dày đặc, với khả năng
xử lý tốc độ cao. Ngày nay, các mạng cảm biến không dây đƣợc ứng dụng trong
nhiều lĩnh vực nhƣ nghiên cứu vi sinh vật biển, giám sát việc chuyên chở các
chất gây ô nhiễm, kiểm tra giám sát hệ sinh thái và môi trƣờng sinh vật phức
tạp, điều khiển giám sát trong công nghiệp và trong lĩnh vực quân sự, an ninh
quốc phòng hay các ứng dụng trong đời sống hàng ngày. Vậy mạng không dây

trọng trong việc truyền dữ liệu trong mạng cảm biến không dây.
Chính vì thế, chủ đề nghiên cứu của em về lĩnh vực chất lƣợng truyền tín
hiệu thông qua sự phân cụm nút mạng và sự tồn tại lâu dài của dàn mạng cảm

13
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

biến không dây, cũng gống nhƣ ta đi xây dựng kỹ thuật để xác định chất lƣợng
truyền tối ƣu.
Xuất phát từ xu hƣớng trên, đề tài “Phân cụm nút mạng cảm biến không
dây và ứng dụng” không chỉ có mục tiêu nghiên cứu mà còn đánh giá sự tồn tại
lâu dài của của hệ thống mạng. Kết quả của luận văn sẽ làm nền tảng cho hƣớng
nghiên cứu tiếp theo về chủ đề phân cụm trong mạng cảm biến không dây. Bố
cục của luận văn gồm các nội dung sau:

CHƢƠNG 1
KHÁI QUÁT MẠNG CẢM BIẾN KHÔNG DÂY
VÀ BÀI TOÁN ĐỊNH TUYẾN
Trình bày khái quát, cấu trúc, mô hình và bài toán định tuyến trong mạng
cảm biến không dây.
CHƢƠNG 2
CÁC GIAO THỨC TRONG MẠNG CẢM BIẾN KHÔNG DÂY
Trình bày các kỹ thuật định tuyến và giao thức trong mạng cảm biến
không dây.
CHƢƠNG 3
MẠNG CẢM BIẾN KHÔNG DÂY CHO
NHÀ MÁY THỦY ĐIỆN HÒA BÌNH
Trình bày chi tiết mô hình nhà máy thủy điện Hòa Bình, khảo sát nhà máy, ứng

với nhau, nhằm để trao đổi thông tin và đáp ứng yêu cầu cầu ngƣời dùng. Mỗi
nút cảm biến không dây bao gồm một bộ thu phát vô tuyến, một bộ vi xử lý, và
các cảm biến. Mạng cảm biến không dây sẽ liên kết các nút trong đó các nút
cảm biến trao đổi với nhau thông qua giao tiếp không dây và các nút trong mạng
thƣờng là các (thiết bị) đơn giản, nhỏ gọn, giá thành thấp, đa chức năng, công
suất tiêu thụ thấp và có một phạm vi hoạt động lớn có thể liên kết với các mạng
khác để tạo ra mạng cảm biến có phạm vi rộng lớn hơn. Các nút cảm biến có thể
sử dụng nguồn năng lƣợng hạn chế (pin), nên có giới hạn về thời gian hoạt động.
Các nút cảm biến này có nhiệm vụ cảm nhận, đo đạc, tín hiệu, thu thập, hoặc
đáp ứng yêu cầu của ngƣời dùng, nhƣ theo dõi, chụp ảnh, bật tắt hệ thống, thiết
bị điện, hay ở chế độ ngủ.
16
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

1.1.1: Giới thiệu mạng cảm biến không dây
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
nút với nhau bằng kết nối sóng vô tuyến trong đó các nút 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, sử dụng
nguồn năng lƣợng hạn chế là (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 nút (node) mạng thƣờng có chức năng 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 nút (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 mạng cảm biến không dây là
thấp và không liên tục (không hẳn với tracking và localization aplication). Do

Phần thu phát vô tuyến kết nối các nút vào mạng. Chúng gửi và nhận các
dữ liệu thu đƣợc từ chính nó hoặc các nút lân cận tới các nút khác hoặc tới sink.
Phần quan trọng nhất của một nút mạng cảm ứng là bộ nguồn. Bộ nguồn
có thể là một số loại pin. Để các nút có thời gian sống lâu thì bộ nguồn rất quan
trọng, nó phải có khả năng nạp điện từ môi trƣờng nhƣ là năng lƣợng ánh sáng
mặt trời.
Hầu hết các kỹ thuật định tuyến và các nhiệm vụ cảm ứng của mạng đều
yêu cầu có độ chính xác cao về vị trí, vì vậy cần phải có các bộ định vị. Các bộ
phận di động, đôi lúc cần để dịch chuyển các nút cảm ứng khi cần thiết để thực

18
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

hiện các nhiệm vụ đã ấn định nhƣ cảm biến theo dõi sự chuyển động của vật nào
đó.
Tất cả những thành phần này cần phải phù hợp với kích cỡ từng module.
Ngoài kích cỡ ra các nút cảm ứng còn một số ràng buộc nghiêm ngặt khác, nhƣ
là phải tiêu thụ rất ít năng lƣợng, hoạt động ở mật độ cao, có giá thành thấp, có
thể tự hoạt động, và thích ứng với môi trƣờng.
1.1.2.2: Cấu trúc mạng cảm biến không dây
Giao tiếp không dây multihop: Khi giao tiếp không dây là kỹ thuật chính,
thì giao tiếp trực tiếp giữa hai nút sẽ có nhiều hạn chế do khoảng cách hay các
vật cản. Đặc biệt là khi nút phát và nút thu cách xa nhau thì cần công suất phát
lớn.Vì vậy cần các nút trung gian làm nút chuyển tiếp để giảm công suất tổng
thể. Do đó các mạng cảm biến không dây cần phải dùng giao tiếp multihop.
Hoạt động hiệu quả năng lƣợng: để hỗ trợ kéo dài thời gian sống của toàn
mạng, hoạt động hiệu quả năng lƣợng là kỹ thuật quan trọng mạng cảm biến
không dây.

+ Đơn vị cảm biến
Bao gồm cảm biến và bộ chuyển đổi tƣơng tự - số (ADC). Dựa vào những hiện
tƣợng quan sát đƣợc, đo lƣờng đƣợc, tín hiệu tƣơng tự tạo ra bởi cảm biến đƣợc
số hóa bằng bộ chuyển đổi tƣơng tự - số ADC (Analog Digital Converter), sau
đó đƣợc đƣa vào bộ xử lý.
+ Đơn vị xử lý
20
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

Là bộ xử lý có khả năng lƣu trữ, xử lý dữ liệu cũng nhƣ việc chấp hành yêu cầu
của mạng theo ngữ cảnh khác nhau.

+ Đơn vị truyền dẫn
Là phần thu phát vô tuyến thực hiện việc thu phát tín hiệu qua môi trƣờng không
dây giữa các nút cảm biến, thông thƣờng chuẩn truyền thông trong mạng cảm
biến nhƣ Zigbee.
+ Bộ nguồn
Cung cấp năng lƣợng cho toàn bộ hoạt động của nút cảm biến. Tùy thuộc
vào nút cảm biển khác nhau, mà nguồn có thể đƣợc bổ sung từ năng lƣợng bên
ngoài nhƣ sóng điện từ, năng lƣợng mặt trời.
Ngoài ra nút có thể có thêm những thành phần khác tùy thuộc vào từng
ứng dụng nhƣ là hệ thống định vị (location filding system), bộ phát nguồn
(power generator) và bộ phận di động (mobilizer).
1.1.3: Mô hình mạng cảm biến không dây
+ Mô hình mạng AD-HOC
Khái niệm
- Là mạng gồm hai hay nhiều máy tính có trang bị card không dây
- Tƣơng tự mô hình peer to peer trong mạng có dây

đƣợc triển khai (nhà hay văn phòng). Với sự gia tăng số ngƣời sử dụng máy tính
xách tay (laptop), đó là một điều rất thuận lợi.
Khả năng di động: Với sự phát triển của các mạng không dây công cộng,
ngƣời dùng có thể truy cập Internet ở bất cứ đâu. Chẳng hạn ở các quán Cafe,
ngƣời dùng có thể truy cập Internet không dây miễn phí.
Hiệu quả: Ngƣời dùng có thể duy trì kết nối mạng khi họ đi từ nơi này đến nơi
khác.
Triển khai: Việc thiết lập hệ thống mạng không dây ban đầu chỉ cần ít
nhất 1 access point. Với mạng dùng cáp, phải tốn thêm chi phí và có thể gặp khó
khăn trong việc triển khai hệ thống cáp ở nhiều nơi trong tòa nhà.
Đơn giản về mặt tính toán, dễ thực hiện, và lắp đặt trên mọi địa hình, giả
thiết một tín hiệu chạy trong mạng nhờ có cách phân bổ các nút trong toàn mạng
cảm biến mà vẫn đảm bảo sự hội tụ do đó có thể triển khai và phát triển ứng
dụng này trên hệ thống mạng có quy mô lớn, giảm chi phí truyền thông, cho độ
chính xác cao hơn, lƣợng tiêu thu năng lƣợng trong mạng ít, vì vậy tuổi thọ
trong dàn mạng lâu hơn…..... Mặc dù không tránh khỏi những hạn chế tất yếu
trong việc chấp nhận sai số nhỏ (dần theo sự gia tăng số cảm biến), phƣơng pháp
này vẫn đƣợc coi là có tính khả thi cao nhờ những ƣu điểm vƣợt trội do mạng
cảm biến không dây mang lại.
+ Tiêu thụ điện năng thấp
Những ứng dụng mạng cảm biến không dây yêu cầu tiêu thụ điện trung
bình thấp hơn mạng không dây hiện thời khác do đa phần các phần tử cảm nhận
trong mạng đƣợc nuôi bằng pin do vậy năng lƣợng rất giới hạn. Một cách để giải
quyết vấn đề này, trong những ứng dụng nhất định không thể sử dụng một
nguồn pin duy nhất, những nút mạng trong những ứng dụng này phải có năng
23
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>


/>

+ An toàn bảo mật
Do sử dụng môi trƣờng truyền là sóng radio, nên có khả năng bị nhiễu … Do
đó, sự an toàn bảo mật của những mạng cảm biến không dây có hai khía cạnh
quan trọng nhƣ nhau là:
- Mạng thật sự an toàn nhƣ thế nào và việc mạng đƣợc lĩnh hội cho những
ngƣời dùng đặc biệt là những ngƣời dùng tiềm năng.
- Việc mã hóa thông tin để đảm bảo tính an toàn trong mạng, cần bảo đảm
cho bất kỳ ngƣời nhận đƣợc thông báo từ ngƣời gửi không bị sửa đổi
thông tin bên trong bằng bất kỳ cách nào.

+ Lƣu lƣợng dữ liệu
Những mạng cảm biến không dây có yêu cầu lƣu lƣợng dữ liệu thấp hơn
so với các mạng không dây nhƣ: Bluetooth (IEEE 802.15.1), WPANs và
WLANs khác. Tuỳ vào mục đích thiết kế tốc độ dữ liệu cực đại có thể là 512b/s
(64bytes/s) mặc dù tốc độ dữ liệu thƣờng dƣới tốc độ này ở khoảng 1b/s hoặc
thấp hơn trong một vài ứng dụng.
+ Tiềm ẩn thông báo
Những mạng cảm biến không dây có chất lƣợng dịch vụ (QoS) bởi vì
trong chúng không hỗ trợ truyền thông đồng thời hoặc trùng hợp. Yêu cầu tiềm
ẩn thông báo cho những mạng cảm biến không dây đƣợc giảm nhẹ khi so sánh
với WPANs khác. Trong nhiều ứng dụng sự tiềm ẩn thông báo có khi đến cỡ vài
giây hoặc vài phút thì có thể chấp nhận đƣợc.
+ Khả năng di động
Những ứng dụng mạng cảm nhận không dây không yêu cầu sự lƣu động
cao vì mạng giải quyết việc xác định những tuyến đƣờng truyền thông mở,

25
Số hóa bởi Trung tâm Học liệu - ĐHTN