i

LỜI CAM ĐOAN

Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu
trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình
nào khác.

TP. Hồ Chí Minh, ngày 15 tháng 8 năm 2017
Học viên thực hiện luận văn

Ngô Quang Quyền


ii

LỜI CẢM ƠN
Lời đầu tiên tôi xin gởi lời cảm ơn đến TS. Vũ Ngọc Phàn, Viện Hàn Lâm
Khoa Học và Công Nghệ Việt Nam. PGS.TS. Trần Công Hùng, phó trưởng phòng
Phòng Đào Tạo và Khoa Học Công Nghệ, Học Viện Công Nghệ Bưu Chính Viễn
Thông cơ sở TP.Hồ Chí Minh. Thầy đã tận tình hướng dẫn và giúp đỡ tôi trong suốt
quá trình thực hiện luận văn tốt nghiệp Thạc sĩ.
Chân thành cảm ơn quý Thầy/ Cô trong Khoa Công nghệ Thông tin - Học viện
Bưu chính Viễn Thông đã tận tình giảng dạy, trang bị cho tôi những kiến thức quý
báu trong thời gian tôi học tại Học viện.
Cảm ơn Ban Giám đốc Bệnh viện Nhi Đồng 2 đã tạo điều kiện thuận lợi cho
tôi hoàn thành khóa học một cách tốt nhất. Cảm ơn gia đình, các anh chị, bạn bè và
đồng nghiệp đã ủng hộ, giúp đỡ và động viên tôi trong suốt quá trình học tập và
thực hiện luận văn.
Xin trân trọng cảm ơn!



1.3.1

Cấu trúc một node trong mạng WSN ............................................... 11

1.3.2

Cấu trúc mạng WSN .......................................................................12

1.3.3

Giao thức định tuyến trong WSN .................................................... 14

1.3.4

Kiến trúc và giao thức WSN ........................................................... 15

1.4

Các thách thức và trở ngại đối với WSN ................................................ 17

1.4.1

Giới hạn về nguồn năng lượng ........................................................ 17

1.4.2

Giới hạn về phần cứng ....................................................................18

1.4.3

Các thuật toán phân cụm mờ trong WSN ............................................... 25

2.2.1

Thuật toán FCM ( Fuzzy C-Means) ................................................. 32

2.2.2

Thuật toán εFCM ( Insensitive Fuzzy C-Means)[7] ........................ 36

2.3

Tổng quan về giao thức định tuyến SEP................................................. 39

2.4

Kết luận .................................................................................................40

CHƯƠNG III - ĐỀ XUẤT GIAO THỨC SEP_εFCM MÔ PHỎNG
VÀ ĐÁNH GIÁ ............................................................................................ 41
3.1

Xây dựng mô hình mạng ........................................................................ 41

3.2

Mô hình năng lượng............................................................................... 41

3.3


v

DANH MỤC KÝ HIỆU

Viết tắt

Tiếng Anh

Tiếng Việt

BS

Base Station

Trạm gốc

CH

Cluster Head

Cụm chủ

FCM

Fuzzy C-Means

Thuật toán Fuzzy C-Means

FCM


đồng nhất


vi

DANH SÁCH BẢNG
Bảng 2.1: Tọa độ các node .............................................................................. 27
Bảng 2.2: Kết quả phân cụm K-Means ............................................................ 31
Bảng 3.1: Bảng tóm tắt giá trị các tham số trong luận văn ............................... 49
Bảng 3.2: Bảng mô tả các ký hiệu trong hình mô phỏng .................................. 50


vii

DANH SÁCH HÌNH VẼ
Hình 1.1: Cấu trúc cơ bản của mạng cảm biến không dây ................................. 4
Hình 1.2: Các ứng dụng của WSN .................................................................... 6
Hình 1.3: Ứng dụng trong quân sự .................................................................... 7
Hình 1.4: Ứng dụng trong giám sát và điều khiển công nghiệp ......................... 8
Hình 1.5: Ứng dụng theo dõi cháy rừng ............................................................ 9
Hình 1.6: Ứng dụng trong y tế ........................................................................ 10
Hình 1.7: Ứng dụng trong ngôi nhà thông minh .............................................. 11
Hình 1.8: Các thành phần cơ bản của một node cảm biến................................ 12
Hình 1.9: Cấu trúc mạng hình sao ................................................................... 13
Hình 1.10: Cấu trúc mạng dạng lưới ............................................................... 13
Hình 1.11: Cấu trúc mạng phân cụm hai tầng .................................................. 14
Hình 1.12: Kiến trúc giao thức mạng cảm biến không dây .............................. 16
Hình 2.1: Cấu trúc phân cụm trong mạng cảm biến không dây........................ 20
Hình 2.2: Lược đồ thuật toán K-Means ........................................................... 27
Hình 2.3: Tọa độ các node trên mặt phẳng ...................................................... 28

của quân địch; Theo dõi khô hạn và cảnh báo cháy rừng; Đo độ ẩm để điều tiết
nước tưới trong các trang trại nông nghiệp; Giám sát sức khỏe của bệnh nhân,…
Tuy nhiên WSN cũng còn tồn tại nhiều mặt hạn chế, một trong những hạn chế
lớn nhất đó là nguồn năng lượng của các node cảm biến (do kích thước nhỏ nên pin
cũng được thiết kế nhỏ). Với việc nguồn năng lượng không thể thay đổi thì một bài
toán đặt ra là chúng ta phải làm gì để kéo dài thời gian hoạt động của mạng WSN
này ?. Để giải quyết vấn đền này. Ngoài việc cải tiến về phần cứng thì việc ứng
dụng các thuật toán vào việc phân cụm các node cảm biến là một trong những kỹ
thuật có thể mang lại hiệu quả cao trong việc giải quyết vấn đề năng lượng này.
Luận văn này sẽ nghiên cứu một số các thuật toán phân cụm và đề xuất thuật toán
cải tiến nhằm mang lại hiệu cao trong việc phân cụm mạng WSN.


2

Mạng cảm biến không dây (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 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 trên một diện tích rộng với phạm vi hoạt động 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
độ...). Tất cả các cảm biến cảm nhận môi trường và truyền dữ liệu đến cụm đầu,
mỗi cụm có một chủ cụm (Cluster Head - CH) sẽ giao tiếp với tất cả các node thành
viên trong cụm. CH sẽ truyền toàn bộ dữ liệu đến Sink.
Như phân tích ở trên, chúng ta thấy các node chính thường phải truyền số liệu
qua những khoảng cách xa, lắng nghe và nhận tín hiệu từ các node trong cụm, và xử
lý nhiều công việc khác trong cụm, nên chúng thường mất nhiều năng lượng hơn
các node thành viên khác. Do vậy mạng phải tái phân cụm định kỳ để lựa chọn các
node có dư thừa năng lượng hơn làm node chính của các cụm và phân bố lưu lượng
tải đều hơn cho toàn bộ các node.


Giới thiệu về WSN
Mạng cảm biến không dây Wireless Sensor Network(WSN)[1] được định

nghĩa là một mạng lưới được hình thành từ sự kết hợp giữa các node cảm biến với
nhau. Node cảm biến là một thiết bị nhỏ gọn, có khả năng tự hành và giao tiếp
không dây qua một khoảng cách ngắn để 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.
Các node cảm biến được trang bị các tính năng cảm nhận, quan sát, đo đạc,
tính toán, định vị,… môi trường xung quanh sau đó truyền dữ liệu tổng hợp được về
node gốc bằng bộ thu và phát sóng vô tuyến của mình. Node gốc là nơi thu nhận các
dữ liệu từ các node thành viên trong nhóm tiến hành tổng hợp và phân tích dữ liệu
sau đó gởi dữ liệu này về Sink node tại đây dữ liệu đã sẵn sàng cho người dùng sử
dụng. 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 hay gián tiếp thông qua một điểm thu phát (Sink node) và môi trường
mạng công cộng như internet hay vệ tinh.

Hình 1.1: Cấu trúc cơ bản của mạng cảm biến không dây


5

Các node cảm biến không dây liên kết thành một mạng cùng với đó là sự phát
triển của internet, vệ tinh đã tạo ra nhiều khả năng mới cho con người. Với sự tiến
bộ về kỹ thuật vi điện tử, công nghệ nano, công nghệ mạch tích hợp,…đã thiết kế ra
các cảm biến không dây 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 cùng với việc áp dụng các
kỹ thuật mã hóa, sửa lỗi truyền thống nhằm tăng độ tin cậy của các đơn vị riêng lẻ
bị giới hạn bởi kích thước và công suất của các node cảm biến. Việc tăng độ tin cậy


Triển vọng và ứng dụng của mạng cảm biến không dây trong quân sự. Các
mạng cảm biến không dây là một phần không thể thiếu trong các ứng dụng quân sự
ngày nay với các hệ thống mệnh lệnh, điều khiển, thu thập tin tức tình báo truyền
thông, tính toán, theo dõi kẻ tình nghi, trinh sát và tìm mục tiêu. Với đặc tính triển
khai nhanh chóng, tự tổ chức và khả năng chịu đựng lỗi của các mạng cảm biến cho
thấy đây là công nghệ đầy triển vọng trong lĩnh vực quân sự. Vì các mạng cảm biến
dựa trên cơ sở triển khai rất nhiều nút giá rẻ và chỉ dùng một lần, việc bị địch phá
hủy một số node không ảnh hưởng tới hoạt động chung như các cảm biến truyền
thống nên chúng tiếp cận chiến trường tốt hơn một số ứng dụng cụ thể như : kiểm
tra lực lượng, trang bị, đạn dược, giám sát chiến trường, trinh sát vùng và lực lượng
địch, tìm mục tiêu, đánh giá thiệt hại trận đánh, trinh sát và phát hiện các vũ khí hóa
học – sinh học – hạt nhân.


7

Hình 1.3: Ứng dụng trong quân sự

Ứng dụng của mạng cảm biến không dây trong giám sát và điều khiển công
nghiệp. Đặc thù của giám sát và điều khiển công nghiệp là môi trường nhiễu lớn,
không đòi hỏi lượng lớn dữ liệu thông tin được truyền tải nhưng yêu cầu rất cao về
độ tin cậy và đáp ứng thời gian thực. Mạng cảm biến không dây được ứng dụng
trong lĩnh vực này chủ yếu phục vụ việc thu thập thông tin, giám sát trạng thái hoạt
động của hệ thống, như trạng thái các van, trạng thái thiết bị, nhiệt độ và áp suất của
nguyên liệu được lưu trữ,… Ngoài ra, trong một số ứng dụng điều khiển trên diện
rộng thì mạng cảm biến không dây cũng thể hiện nhiều tính năng vượt trội. Đó là hệ
thống điều khiển không dây ánh sáng quảng cáo. Rất nhiều chi phí trong quá trình
cài đặt các bóng đèn trong một toà nhà lớn (các chuyển mạch có dây, các bóng đèn
được bật/tắt cùng nhau, điều khiển bóng đèn, …). Một hệ thống không dây có tính


9

Một số ứng dụng về môi trường của WSN :
+ Theo dõi sự di chuyển của các loài chim, loài thú nhỏ, côn trùng; kiểm
tra các điều kiện môi trường ảnh hưởng tới mùa màng và vật nuôi;
+ Các công cụ giám sát phát hiện hóa học, sinh học, kiểm tra môi trường
không khí, đất trồng, biển;
+ Phát hiện và cảnh báo cháy rừng, phát hiện động đất, sóng thần.
+ Các ứng dụng của WSN được sử dụng trên các trang trại chăn nuôi.
Người chăn nuôi có thể sử dụng các mạng cảm biến trong quá trình
quyết định vị trí của các con vật trong trang trại và các cảm biến được
gắn theo mỗi con vật, xác định các yêu cầu cho các phương pháp điều
trị để phòng chống các động vật ký sinh và dịch bệnh phát sinh.

Hình 1.5: Ứng dụng theo dõi cháy rừng

Ứng dụng của mạng cảm biến không dây trong lĩnh vực y tế và giám sát sức
khỏe. Một số ứng dụng trong lĩnh vực y tế của mạng cảm biến không dây là khả
năng giao tiếp cho các người khuyết tật; kiểm tra tình trạng của bệnh nhân; chẩn
đoán; kiểm tra, giám sát sự di chuyển và các cơ chế sinh học, kiểm tra từ xa các số
liệu về sinh lý con người; giám sát, kiểm tra các bác sĩ và bệnh nhân trong bệnh
viện.


10

Hình 1.6: Ứng dụng trong y tế

Các ứng dụng tự động hóa cho các hộ gia đình và điện dân dụng. Gia đình là

1.3.1 Cấu trúc một node trong mạng WSN
Một trong những thành phần quan trọng nhất để hình thành mạng cảm biến
không dây đó chính là node cảm biến. Ngày nay với sự tiến bộ của khoa học đặc
biệt là ngành điện tử viễn thông đã cho ra đời những node cảm biến có kích thước
nhỏ gọn hơn, giá thành thấp, có khả năng lưu trữ cao, tính toán nhanh và hoạt động
hiệu quả hơn với năng lượng, bộ cảm biến nhạy hơn, khả năng thu và phát sóng
giữa các node với nhau tốt hơn. Tùy theo từng yêu cầu ứng dụng cụ thể của từng
mạng cảm biến các node cảm biến có thể được thiết kế thêm các chức năng riêng,
về cơ bản một node cảm biến được cấu tạo bởi bốn thành phần chính sau:


12

-

Bộ xử lý (a processing unit)

-

Bộ thu phát (a transceiver unit)

-

Bộ cảm nhận (sensing unit)

-

Bộ nguồn (a power unit)

Hình 1.8: Các thành phần cơ bản của một node cảm biến

Hình 1.10: Cấu trúc mạng dạng lưới

1.3.2.3 Cấu trúc phân cụm hai tầng
Cấu trúc này là cấu trúc phổ biến nhất trong việc phân cụm mạng WSN. Trong
cấu trúc này, các node trong một khu vực cụ thể báo cáo dữ liệu về một cụm chủ
CH. Cụm chủ này tạo thành một mạng lưới với node gốc, như vậy một node gốc sẽ


14

quản lý nhiều CH ở các cụm nhỏ khác nhau. Ưu điểm của cấu trúc này là nó chia
một mạng lớn thành nhiều khu vực nhỏ. Cụm chủ cũng có thể được thiết kế mạnh
mẽ hơn về tính năng thông tin liên lạc hoặc thậm chí có thể được kết nối thông qua
các mạng khác, tăng tốc độ truyền tải và độ tin cậy của mạng.

Hình 1.11: Cấu trúc mạng phân cụm hai tầng

1.3.3 Giao thức định tuyến trong WSN
Các node cảm biến trong mạng cảm biến không dây thường dùng pin, do thiết
kế nhỏ gọn nên lượng pin có giới hạn. Khi triển khai ở một phạm vi rộng và số
lượng node cảm biến lớn thì rất khó cho việc nạp lại năng lượng cho pin. Như vậy,
vấn đề năng lượng trong mạng WSN là một nguồn tài nguyên có giới hạn, cho nên
việc định tuyến phân cụm nhằm tiết kiệm năng lượng là một trong những khía cạnh
quan trọng nhất của việc kéo dài tuổi thọ cho các node cảm biến. Trong việc định
tuyến nhằm tiết kiệm năng lượng thì việc chọn đường đi giữa hai node và việc tiến
hành phân cụm thường xuyên để sử dụng cân bằng nguồn năng lượng ở tất cả các
node là yếu tố quan trọng hàng đầu. Để thực hiện được việc định tuyến phân cụm
này chúng ta cần giải quyết được những thách thức sau:
-


Kiến trúc giao thức được sử dụng trong bộ thu nhận (Sink) và tất cả các nút
cảm biến được thể hiện trên hình 1.12. Kiến trúc giao thức này phối hợp các tính
toán về định tuyến và năng lượng, kết hợp số liệu với các giao thức mạng, truyền tin
với hiệu quả về năng lượng thông qua môi trường không dây và tăng cường sự hợp
tác giữa các nút cảm biến. Kiến trúc giao thức bao gồm:
+ Lớp ứng dụng (Application Layer).
+ Lớp giao vận (Transport Layer).
+ Lớp mạng (Network Layer).
+ Lớp liên kết số liệu (Datalink Layer).
+ Lớp vật lý (Physical Layer).
+ Mặt phẳng quản lý nguồn (Power Management Plane).
+ Mặt phẳng quản lý tính di động (Mobility Management Plane).
+ Mặt phẳng quản lý tác vụ (Task Management Plane).


16

Hình 1.12: Kiến trúc giao thức mạng cảm biến không dây

Tuỳ theo nhiệm vụ của cảm biến, các kiểu phần mềm ứng dụng có thể được xây
dựng và sử dụng trên lớp ứng dụng:
+ Lớp giao vận giúp duy trì dòng số liệu khi các ứng dụng của mạng
cảm biến yêu cầu.
+ Lớp mạng tập trung vào việc định tuyến số liệu được cung cấp bởi lớp
giao vận. Do môi trường có nhiễu và các nút cảm biến có thể di động được, giao
thức MAC(Media Access Control) phải được tính toán về năng lượng và tối thiểu
hóa va chạm trong việc phát quảng bá với các nút lân cận.
+ Lớp vật lý sử dụng các kỹ thuật điều chế, truyền và nhận cần thiết đơn
giản nhưng mạnh mẽ. Thêm vào đó, các mặt phẳng quản lý năng lượng, di động và
nhiệm vụ điều khiển sự phân phối năng lượng, phối hợp di chuyển và nhiệm vụ giữa

Ngày nay mạng cảm biến không dây được ứng dụng rộng rãi trong hầu hết các
lĩnh vực nhờ những tính năng ưu việt mà chúng đem lại cho chúng ta, tuy nhiên bên
cạnh đó mạng cảm biến không dây vẫn tồn tại những hạn chế mà nếu chúng ta nắm
bắt được những hạn chế này sẽ khắc phục và hạn chế tối đa những trở ngại này.

1.4.1 Giới hạn về nguồn năng lượng
Các node cảm biến trong mạng cảm biến không dây thường sử dụng nguồn
năng lượng có sẵn (Pin), với kích thước nhỏ nên năng lượng bị giới hạn tuy ngày
nay nguồn năng lượng pin này ngày càng được tích hợp để mang được dung lượng
cao hơn, nhưng do đòi hỏi tính năng ngày một cao của con người, các node cảm
biến phải lắng nghe, cảm nhận, tính toán, truyền dữ liệu do đó, chúng ta phải tìm ra


18

giải pháp xử lý và truyền dữ liệu một cách hợp lý để tăng tuổi thọ cho mạng cảm
biến không dây. Việc thiết lập một chu kỳ làm việc với việc chuyển mạch giữa hai
chế độ : Chế độ ngủ (mode sleep) và chế độ hoạt động (mode active), việc định
tuyến phân cụm hiệu quả, tránh việc chồng chéo là những yếu tố quan trọng trong
việc giải quyết bài toán về nguồn năng lượng cho mạng cảm biến không dây.

1.4.2 Giới hạn về phần cứng
Đối với một số ứng dụng đòi hỏi chúng ta phải thiết kế những node cảm biến
nhỏ, điều này làm hạn chế đi bộ nhớ, khả năng tính toán, và nguồn năng lượng,
khiến cho chúng hạn chế về tính năng cũng như tuổi thọ của mạng. Điều này đòi hỏi
chúng ta không ngừng cải tiến công nghệ phần cứng để cho ra đời những sensor có
kích thước nhỏ gọn, giá thành thấp,hiệu suất cao và đặc biệt có tuổi thọ dài.

1.4.3 Ảnh hưởng của môi trường
Mạng cảm biến không dây sử dụng đường truyền là sóng vô tuyến, nên rất dễ