i

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

Phạm Văn Toán

ỨNG DỤNG MẠNG CẢM BIẾN KHÔNG DÂY TRONG
CẢNH BÁO CHÁY CHO NHÀ CAO TẦNG

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

Thái Nguyên, tháng 06 năm 2015


ii

LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung trong luận văn này do tôi tự nghiên cứu,
đọc, dịch tài liệu, tổng hợp và thực hiện. Trong luận văn tôi có sử dụng một số tài
liệu tham khảo như đã trình bày trong phần tài liệu tham khảo.
Người viết luận văn

Phạm Văn Toán


3

LỜI CẢM ƠN
Đầu tiên em trân thành xin gửi lời cảm ơn đến các thầy cô trường Đại học

CHƯƠNG 2: CÁC GIAO THỨC ĐỊNH TUYẾN CHO MẠNG CẢM BIẾN KHÔNG
DÂY .......................................................................................................................... 22
2.1. Sự phân phối và tập hợp dữ liệu ............................................................. 22
2.2. Thiết kế trong kỹ thuật định tuyến không dây ........................................ 23
2.2.1. Kích thước mạng và đặc tnh thay đổi theo thời gian: ..................... 23
2.2.2. Tài nguyên hạn chế: ......................................................................... 24
2.3. Giao thức điều khiển truy nhập trong mạng cảm biến không dây ..........
24
2.3.1. Mô hình giao thức cho WSNs .......................................................... 25
2.3.2. Giao thức MAC ................................................................................ 26
2.3.3. Các giao thức MAC cho mạng WSNs: ............................................ 28
2.3.4. Nghiên cứu trường hợp SENSOR-MAC: ........................................ 29


5

2.4 Giao thức, giao vận trong mạng cảm biến không dây ............................. 36


6

2.4.1 Giao thức định tuyến trong WSNs: ................................................... 36
CHƯƠNG 3: MÔ HÌNH VÀ GIAO THỨC ĐƯỜNG ĐỊNH TUYẾN ĐÚNG DẦN NGẮN
NHẤT ........................................................................................................... 47
3.1. Xây dựng hài toán ................................................................................... 47
3.2. Lý thuyết đồ thị ....................................................................................... 49
3.2.1 Đồ thị và cây...................................................................................... 49
3.2.2 Thuật toán Dijkstra ............................................................................ 51
3.3 Đề xuất cho thuật toán định tuyến ...........................................................
54

Hình 2.9 Flooding các gói dữ liệu trong mạng thông tin.......................................... 39
Hình 2.10 Bùng nổ lưu lượng do flooding. .............................................................. 40
Hình 2.11 Vấn đề chồng lấn do flooding. ................................................................. 40
Hình 2.12 Hoạt động cơ bản của giao thức SPIN..................................................... 43


vii

Hình 2.13 Thủ tục bắt tay trong giao thức SPIN-PP. ............................................... 43
Hình 2.14 Giao thức SPIN-BC. ................................................................................ 45
Hình 3.1 Mô hình mạng cảm biến cho nhà cao tâng ................................................ 47
Hình 3.2 Cây đường đi ngắn nhất - SPT................................................................... 48
Hình 3.3 Sơ đồ nút mạng .......................................................................................... 48
Hình 3.4 Đồ thị ......................................................................................................... 49
Hình 3.5 Đồ thị ......................................................................................................... 50
Hình 3.6..................................................................................................................... 51
Hình 3.7 Sơ đồ SPT của u......................................................................................... 53
Hình 3.8 Ví dụ về giải thuật Dijkstra (1959) ............................................................ 54
Hình 3.9 Ví dụ về giải thuật Dijkstra (1959) [4] ...................................................... 54
Hình 3.10 Cụm nút được hình thành và cụm chủ được lựa chọn ............................. 58
Hình 3.11 So sánh giữa Leach và Quá trình định tuyến theo đường dẫn ngắn nhất 59
Hình 3.12 Sơ đồ thuật toán xây dựng đường định tuyến ngắn nhất .........................
60
Hình 3.13 Sơ đồ biểu diễn quá trình truyên dữ liệu.................................................. 61
Hình 3.14 Các nút chết ............................................................................................. 62
Hình 3.15 Gói tin đến BS.......................................................................................... 63
Hình 3.16 Các cụm chủ được hình thành ................................................................. 64
Hình 3.17 Các gói tin đến cụm chủ .......................................................................... 65
Hình 3.18 Số nút còn sống ........................................................................................ 66


WSNs

Wireless Sensor Network

Mạng cảm biến không dây

OS

Operating System

Hệ điều hành

LEACH

Low-Energy Adaptive Clustering
Hierarchy

Cấu trúc phân bậc tương thích,
năng lượng thấp

MAC

Medium access control

Điều khiển truy cập môi trường

PHY

Physic Layer


Hình 1.1 Hình ảnh về một số vụ cháy lớn
Cháy nổ luôn là một nguy cơ tiềm ẩn nhiều rủi ro trong sản xuất và sinh hoạt
hàng ngày. Mặc dù đã có những biện pháp, hệ thống được xây dựng để phát hiện
và cảnh báo cháy nổ nhưng nhiều thảm họa do cháy nổ gây ra vẫn hoành hành và
gây thiệt hại nhiều về người và của.
Trong những năm gần đây với sự phát triển mạnh mẽ của công nghệ linh
kiện điện tử và công nghệ thông tin đã tạo ra những sự thay đổi to lớn trong cuộc
sống. Mô hình mạng cảm biến không dây (WSNs – Wirless Sensor Networks) ra


2

đời dựa trên cơ sở ứng dụng những thành tựu của Công nghệ truyền thông không
dây[3]. Nó ra đời nhằm thỏa mãn nhiều yêu cầu trong thực tế và được ứng
dụng rộng rãi. Các ứng dụng tiềm năng của mạng cảm biến không dây hiện nay như
phán đoán quân sự, bảo vệ an ninh, điều khiển và giám sát giao thông, kỹ thuật tự
động trong sản xuất công nghiệp, điều khiển quy trình, quản lí kiểm kê, cảm nhận
môi trường, giám sát sinh thái, giám sát công trình xây dựng, trong y tế và
dân dụng,[1],[5]…Tại Việt Nam cũng đang có những ứng dụng của mạng cảm biến
không dây như: Hệ thống chiếu sáng, độ ẩm, phòng cháy, hệ thống điều hòa
nhiệt độ, … nhìn chung đây vẫn còn là một công nghệ rất mới mẻ ở Việt Nam.
Đặc biệt trong cháy việc duy trì nguồn điện cho mạng có dây là cực kỳ khó
khăn, vì khi xảy ra cháy thường xảy ra mất điện cục bộ, do đó việc duy trì hoạt
động của mạng có dây là vấn đề rất khó khăn. Bên cạnh đó mạng cảm biến không
dây lại sử dụng PIN và có nhiều giao thức định tuyến khác nhau, đặc biệt là giao
thức định tuyến theo nhóm. Với giao thức này khi xảy ra cháy có thể phá hủy các
Note khác nhau nhưng vẫn không ảnh hưởng đến quá trình truyền dữ liệu
trong
mạng.
Xuất phát từ xu hướng trên, cùng với sự gợi ý của PGS TS Lê Bá Dũng tôi đã

2.3. Giao thức điều khiển truy nhập trong mạng cảm biến không dây
2.4. Giao thức, giao vận trong mạng cảm biến không dây.
Chương 3
Mô hình và giao thức đường định tuyến đúng dần ngắn nhất
3.1. Xây dựng bài toán
3.2. Lý thuyết đồ thị
3.3. Đề xuất cho thuật toán định tuyến
5. Phương pháp nghiên cứu
a. Phương pháp nghiên cứu tài liệu
- Nghiên cứu các tài liệu về mạng không dây, mạng cảm biến không dây.
Tổng hợp các tài liệu và các phương pháp để thu thập dữ liệu từ mạng cảm
biến


b. Phương pháp nghiên cứu điều tra
- Thu thập các tài liệu liên quan đến đề tài
- Phân tch các thông tin liên quan và nghiên cứu lý thuyết
c. Phương pháp nghiên cứu thực nghiệm
- Phương pháp chính được sử dụng là phương pháp mô phỏng. Thay vì
triển khai trên hệ thống thực, tôi tiến hành mô phỏng và đánh giá kết quả đạt
được thông qua phần mềm mô phỏng.
- Chương trình mô phỏng.
6. Ý nghĩa khoa học của đề tài
- Tìm hiểu các kiến thức về mạng không dây.
- Xây dựng ứng dụng của mạng cảm biến không dây.
- Xây dựng hệ thống mô phỏng để phân tch các tn hiệu về mạng
cảm biến không dây.


CHƯƠNG 1: TỔNG QUAN VỀ MẠNG KHÔNG DÂY

Hình 1.2 Phân loại mạng vô tuyến
- WPAN: mạng vô tuyến cá nhân. Nhóm này bao gồm các công nghệ vô
tuyến có vùng phủ nhỏ tầm vài mét đến hàng chục mét tối đa. Các công nghệ này
phục vụ mục đích nối kết các thiết bị ngoại vi như máy in, bàn phím, chuột, đĩa
cứng, khóa USB, đồng hồ,...với điện thoại di động, máy tnh. Các công nghệ trong
nhóm này bao gồm: Bluetooth, Wibree, ZigBee, UWB, Wireless USB, EnOcean,... Đa
phần các công nghệ này được chuẩn hóa bởi IEEE, cụ thể là nhóm làm việc
(Working Group) 802.15. Do vậy các chuẩn còn được biết đến với tên như IEEE
802.15.4 hay IEEE 802.15.3 ...
- WLAN : mạng vô tuyến cục bộ. Nhóm này bao gồm các công nghệ có
vùng phủ tầm vài trăm mét. Nổi bật là công nghệ Wifi với nhiều chuẩn mở rộng
khác nhau thuộc gia đình 802.11 a/b/g/h/i/... Công nghệ Wifi đã gặt hái được
những thành công to lớn trong những năm qua. Bên cạnh WiFi thì còn một cái tên
ít nghe đến là HiperLAN và HiperLAN2, đối thủ cạnh tranh của Wifi được chuẩn
hóa bởi
ETSI.
- WMAN: mạng vô tuyến đô thị. Đại diện tiêu biểu của nhóm này chính là
WiMAX. Ngoài ra còn có công nghệ băng rộng BWMA 802.20. Vùng phủ sóng của
nó sẽ tằm vài km (tầm 4-5km tối đa).
- WWAN: Mạng vô tuyến diện rộng: Nhóm này bao gồm các công nghệ
mạng thông tin di động như UMTS/GSM/CDMA2000... Vùng phủ của nó cũng tầm
vài km đến tầm chục km.


- WRAN: Mạng vô tuyến khu vực. Nhóm này đại diện là công nghệ 802.22
đang được nghiên cứu và phát triển bởi IEEE. Vùng phủ có nó sẽ lên tầm 40100km. Mục đích là mang công nghệ truyền thông đến các vùng xa xôi hẻo lánh,
khó triển khai các công nghệ khác.
Bảng 1: So sánh các nhóm mạng
Công nghệ
UWB (Ultra


WWAN

3G

WWAN

3G

wideband)

Edge/GPRS
(TDMAGMS)
CDMA
2000/1x EVDO
WCDMA/
UMTS

Tốc độ
110-480

Vùng phủ
sóng

Băng tần

Trên 30 feet

7.5 GHz


1-5 dặm

1-5 dặm

400-2100
MHz
1800-2100
MHz

Tất cả các công nghệ này đều giống nhau ở chổ chúng nhận và chuyển tin
bằng cách sử dụng sóng điện từ (EM).
B. Dựa trên các công nghệ mạng, mạng không dây được chia thành 3 loại:
• Kết nối sử dụng tia hồng ngoại
• Sử dụng công nghệ Bluetooth
• Kết nối bằng chuẩn Wi-fi[1],[5]


1.1.3. Các mô hình mạng không dây
1. Mô hình mạng AD-HOC:
a. Khái niệm:
- Là mạng gồm hai hay nhiều máy tnh có trang bị card không dây
- Tương tự mô hình peer to peer trong mạng có dây
- Các máy tính có vai trò ngang nhau
- Khoảng cách liên lạc 30-100m
- Sử dụng thuật toán Spokesman Election Algorithm(SEA)
b. Mô hình vật lí:

Hình 1.3 Mô hình mạng AD-HOC
2. Mô hình mạng INFRASTRUCTURE
a. Khái niệm:

liệu từ thiết bị này đến thiết bị không dây. Lúc này, bản thân
thiết bị


hoạt động chẳng khác gì với khi lắp vào mạng có dây. Chúng ta nên mua cầu nối và
router của cùng nhà sản xuất, nhất là khi muốn tận dụng các chế độ như Super
G, Afterburner, và nhớ chọn loại có hỗ trợ mã hóa WPA.
5. Camera không dây
6. Thiết bị nghe nhạc và xem phim
7. Router du lịch
1.2. Kỹ thuật cảm biến không dây
1.2.1. Khái quát về các NODE cảm biến
Mạng WSNs gồm nhiều cảm biến phân bố phân tán bao phủ một vùng địa lí.
Các node (sensor nodes hay còn gọi là WSNs) có khả năng liên lạc vô tuyến với các
node lân cận và các chức năng cơ bản như xử lí tn hiệu, quản lý giao thức mạng và
bắt tay với các node lân cận để truyền dữ liệu từ nguồn đến trung tâm. Chức
năng cơ bản của các node trong mạng WSNs phụ thuộc vào ứng dụng của nó,
một số chức năng chính:
- Xác định được giá trị các thông số tại nơi lắp đặt. Như có thể trả về nhiệt
độ, áp suất, cường độ ánh sáng, ... tại nơi khảo sát.
- Phát hiện sự tồn tại của các sự kiện cần quan tâm và ước lượng các thông
số của sự kiện đó. Như mạng WSN dùng trong giám sát giao thông, cảm biến phải
nhận biết được sự di chuyển của xe cộ, đo được tốc độ và hướng di chuyển của các
phương tiện đang lưu thông, ...
- Phân biệt các đối tượng. Ví dụ phương tiện lưu thông mà cảm biến nhận
biết được là xe gì: xe con, xe tải, hay xe buýt, ...
- Theo dấu các đối tượng. Ví dụ trong mạng WSN quân sự, mạng cảm biến
phải cập nhật được vị trí các phương tiện của đối phương khi chúng di chuyển trong
vùng bao phủ của mạng, ...
Các hệ thống có thể đáp ứng thời gian thực hay gần như thế, tùy theo

3

là 1-mm .[1],[5]
1.2.2. Phần cứng và phần mềm
Liên quan đến thiết kế node trong mạng WSNs, các chức năng cần phải có:
chức năng cơ bản của node; chức năng xử lí tn hiệu, gồm xử lí số tn hiệu, nén,
phát hiện và sửa lỗi, điều khiển và thừa hành; phân nhóm và tnh toán trong mạng;
thông tin; tự kết hợp; định tuyến; và quản lý kết nối. Để có các chức năng này,


phần cứng của node phải có cảm biến và bộ phận thực thi, bộ xử lí, nguồn, và các
phần


phục vụ cho chức năng khác. Hình 1.6 chỉ ra các phần cấu tạo nên node cảm biến
thông thường gồm phần cứng và phần mềm.
Rõ ràng, cấu trúc bên trong và độ phức tạp phụ thuộc vào các ứng
dụng. Phần cứng gồm 4 nhóm chính:
- Nguồn cung cấp: đảm bảo năng lượng cho node hoạt động trong vài giờ,
vài tháng hay vài năm.
- Lưu trữ và tnh toán: phục vụ cho các chức năng xử lí, điều chế số, định
tuyến, ...
- Cảm biến: biến đổi các thông số môi trường thành thông tin.
- Liên lạc: trao đổi dữ liệu giữa các node với nhau và với trung tâm.
Phần mềm gồm 5 nhóm chính:
- Hệ điều hành (OS) microcode (còn được gọi là middleware): liên kết phần
mềm và chức năng bộ xử lí. Các nghiên cứu hướng đến thiết kế mã nguồn mở cho
OS dành riêng cho mạng WSNs.
- Sensor Drivers: đây là những module quản lý chức năng cơ bản của phần
tử cảm biến.

Di
động

Tự nạp Bộ xử lí, Đa
lại
lưu trữ mức năng,

Chế độ

Giao thức ở
các lớp thấp

chức Đa
cảm đường/lưới;

G. thức
ở các
lớp cao
Định
tuyến


14

cao

Lớn
2

Di

Đa chức năng
cảm
biến
thông số vật
lí, hóa sinh

Đa
đường/lưới;
4
>10 m; IEEE
MAC

Ít
di
động

Pin 10
giờ

Ít
di
động

Pin 10
giờ

Ít
di
động



Đa
chức
năng,
cảm
biến thông số
vật lí

Đa
Định
đường/lưới;
tuyến
1
2
10 – 10 m; động
IEEE MAC

3

Bộ xử lí, Đa
chức
cảm
lưu
trữ năng,
biến thông số
trung bình
hóa sinh

Đa
Định

Cỡ micro di động giờ
mức
cao,
-3
3
lưu trữ mức
(10 mm )
thấp

Một
chức
năng,
cảm
biến thông số
vật lí

Một
đường/lưới;
1
2
10 – 10 m;
IEEE MAC

Nhỏ
0

3

(10 mm )


cảm >104m; IEEE
biến thông số MAC
hóa sinh

Không
di động

Bộ xử lí
trung bình,
lưu trữ mức
thấp

Một
chức Một đường;
năng,
cảm >104m; IEEE
biến thông số MAC
hóa sinh

3

mm )

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