Xem mẫu
- 10 Phạm Thị Dung, Lê Văn Sơn, Lê Thành Công, Đặng Hùng Vĩ
PHÂN CỤM DỰA TRÊN LOGIC MỜ
TRONG KHẢO SÁT THỜI GIAN SỐNG CHO MẠNG CẢM BIẾN KHÔNG DÂY
CLUSTERING BASED ON FUZZY LOGIC
FOR SURVEYING LIFETIME IN THE WIRELESS SENSOR NETWORK
Phạm Thị Dung, Lê Văn Sơn, Lê Thành Công, Đặng Hùng Vĩ
Trường Đại học Sư phạm, Đại học Đà Nẵng; levansupham2004@yahoo.com, dungsp2012@gmail.com
Tóm tắt - Trong báo cáo này, chúng tôi đi sâu nghiên cứu và mở Abstract - This paper presents an in-depth investigation into
rộng các thuật toán phân cụm đối với sự ảnh hưởng trực tiếp đến việc researching and extending the clustering algorithms that have a
khảo sát, phân tích thời gian sống (LifeTime) của các thành phần cấu direct impact on the examination and analysis of the lifetime of the
thành của mạng cảm biến không dây (W ireless Sensor Network). Đối com ponents in W ireless Sensor Networks. At present there still
với các hệ thống W SN hiện đang tồn tại còn có rất nhiều hạn chế, mà exist many limitations in the W ireless Sensor Networks, of which
một trong những hạn chế có tính chất thách thức quan trọng đáng kể lim ited energy resources difficult to recharge are critically
đến đó chính là nguồn năng lượng bị giới hạn và khó có thể nạp lại. challenging. Consequently, as a solution to the minimization of
Vì vậy, một giải pháp để giảm thiểu sự tiêu thụ năng lượng nhằm tối energy consumption and maximization of the W SN life span, the
đa hóa tuổi thọ của mạng WSN, phân cụm mờ là một trong những fuzzy clustering approach is one of the effective and practical
phương pháp mang lại hiệu quả thiết thực với độ tin cậy chấp nhận m ethods with acceptable reliability. The fuzzy in our research
được. Mờ trong phương pháp nghiên cứu chính là Logic mờ, nó hoạt method is the fuzzy logic approach, which operates based on the
động dựa trên giá trị định nghĩa bởi các hàm thành viên. values defined by m ember functions.
Từ khóa - W SN; logic mờ; phương pháp phân cụm; FIS; hàm Key words - W SN; fuzzy logic; clustering m ethod; FIS; m em ber
thành viên. functions.
1. Đặt vấn đề có thể thay thế hoặc nạp lại. Một node Sensor có thể thay
Hiện nay, WSN [1] với những tiềm năng nổi trội đã đổi kích thước tùy thuộc vào yêu cầu của mỗi ứng dụng [6].
mang lại những ứng dụng thiết thực trong cuộc sống con Điều này đồng nghĩa với việc chi phí có thể thay đổi từ
người [2, 3]. Thực chất, WSN là một tập hợp bao gồm các hàng trăm đô la đến một vài xu, tùy thuộc vào kích thước
thiết bị cảm biến sử dụng các liên kết không dây để phối của WSN. Với những hạn chế như vậy, các node Sensors
hợp thực hiện nhiệm vụ nhằm thu thập thông tin dữ liệu cũng hạn chế tương ứng về các mặt tài nguyên như pin, bộ
phân tán với quy mô lớn trong bất kỳ điều kiện cũng như nhớ, tốc độ tính toán và băng thông [7].
bất kỳ địa hình nào. Tuy nhiên, nó tồn tại rất nhiều hạn chế
và một trong những thách thức lớn nhất chính là thời gian Sensors
sống của các node Sensors trong mạng rất ngắn. Tối ưu hóa
Bộ nhớ Bộ vi xử GPS
thời gian sống của mạng là một bài toán phức tạp.
Những kết quả đạt được bởi nhiều công trình nghiên Thu phát vô tuyến
cứu đã chứng minh phân cụm là một kỹ thuật phổ biến với
thuật toán Fuzzy C – means của giáo sư Bezdek [4] trong Nguồn năng lượng
WSN nhằm nâng cao thời gian sống của các node Sensors
trong hệ thống mạng.
Hình 1. Thành phần node Sensor
Đồng thời hiện nay, có rất nhiều nghiên cứu phân tích Trong các thành phần trên, Sensors chính là thành phần
phương pháp phân cụm sử dụng logic mờ cho WSN nhằm cảm biến nhằm cảm nhận về sự thay đổi của môi trường.
tối đa hóa thời gian sống của nó [5]. Thành phần thứ hai, đó chính là bộ xử lý có nhiệm vụ xử lý
Chính vì lẽ đó, riêng đối với bài báo này, nhóm tác giả các dữ liệu khi các Sensors cảm nhận được. Còn thành phần
tập trung nghiên cứu phương pháp phân cụm dựa trên logic thu phát vô tuyến hay là thiết bị trao đổi thông tin liên lạc từ
mờ trong khảo sát thời gian sống cho WSN. node chủ đến trung tâm dữ liệu (node Sink) thì chúng ta có thể
Sự nghiên cứu của nhóm tác giả tập trung với một số hình dung thông qua sơ đồ sau:
nội dung chính được trình bày rất chi tiết lần lượt như đặt
vấn đề; mạng cảm biến không dây; logic mờ và thuật toán
FCM mở rộng; khảo sát và đánh giá, cuối cùng là kết luận.
2. Mạng cảm biến không dây
WSN bao gồm số lượng lớn các node Sensors phân bố
trên diện rộng, ngẫu nhiên nhằm thu thập thông tin về môi
trường. Mỗi node Sensor bao gồm một số thành phần cơ
bản, đồng thời cũng chính là một thiết bị nhỏ bé với những
tính toán đơn giản và hạn chế về nguồn năng lượng mà khó Hình 2. Cấu trúc hoạt động phân cụm trong WSN
- ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 12(97).2015, QUYỂN 2 11
Cuối cùng, GPS [8] chính là một thiết bị định vị. Như
vậy, việc tiêu hao năng lượng của các node Sensors chủ yếu
bởi ba thành phần chính, lần lượt là các Sensors, bộ xử lý dữ
liệu và thu phát vô tuyến hay còn gọi là truyền thông dữ liệu.
Tuy nhiên, Sensors là thành phần tiêu tốn năng lượng ít nhất.
Vì vậy, hệ thống logic mờ sẽ điều khiển trạng thái hoạt động
của các node Sensors rơi vào một trong hai trạng thái hoạt
động hoặc nghỉ ngơi để tiết kiệm nguồn năng lượng.
Hình 5. Hàm thành viên của số mờ tam giác
3. Logic mờ và thuật toán FCM mở rộng Hệ thống logic mờ gồm có ba giai đoạn, như sau:
3.1. Logic mờ
Suy diễn
Fuzzy Giải
Logic mờ [9] được phát triển từ lý thuyết tập mờ nhằm mờ
hóa mờ
thực hiện một lập luận xấp xỉ, cho phép sự không chính
xác, tính bất định, gần đúng nhằm tìm lời giải hiệu quả - Tri thức
đơn giản, dễ hiểu và dễ thực hiện với chi phí thấp. Nó sẽ
phân tích các thông tin bằng cách sử dụng tập mờ được Hình 6. Cấu trúc hệ thống Logic mờ
định nghĩa bởi các biến ngôn ngữ với công thức sau: Trong đó, thành phần trung tâm của hệ mờ chính là các
tri thức hay cơ sở luật mờ, nó được xây dựng dưới sự mô
~ μ ~ u tả của các chuyên gia về môt lĩnh vực áp dụng cụ thể, tức
u :u ∈ U,μ ~ u ∈ 0, 1 1
là bao gồm các luật If – then. Sau đó, nó sẽ được bộ suy
Trong đó ~ u ∈ 0, 1 là giá trị hàm thành viên. diễn mờ với nhiệm vụ kết hợp các luật If – then mờ trong
cơ sở luật để tạo thành một tập mờ đầu ra F.
, ,…, là các phần tử trên tập vũ trụ U. Tùy
thuộc hình dạng của hàm thành viên, tập mờ có các loại: Trong thực tế, có thể đánh giá hay thu nhận dữ liệu từ
môi trường thì dữ liệu đó chỉ có thể là những giá trị số chứ
không thể là những giá trị mờ. Thành phần tiếp theo trong
hệ thống logic mờ đó chính là Fuzzy hóa với nhiệm vụ biến
đổi các giá trị rõ x(T) thành tập mờ X(T). Thành phần cuối
cùng trong hệ chính là khâu giải mờ, với nhiệm vụ chuyển
đổi tập mờ F thành các giá trị rõ y(F) cụ thể.
Vì vậy, giai đoạn quan trọng nhất chính là hệ thống suy
diễn mờ “FIS – Fuzzy Inference System”. Vì nó đơn giản;
Hình 3. Các dạng hàm thành viên trong tập mờ
nó có thể xử lý dữ liệu không đáng tin cậy. Ngoài ra, FIS
Hàm thành viên WSN sử dụng chủ yếu bởi hai hình còn có một số tính năng không kém phần quan trọng trong
dạng chính đó là trimf (hình tam giác) và trapmf (hình Wireless Sensor Network, đó chính là nó có thể thiết kế
thang). Tập mờ ~ có dạng hình thang, ký hiệu một hệ thống đang chạy bằng cách sử dụng một mô hình
~
, , , và được xác định như sau: trực quan, mô tả thông qua những suy luận thông thường
, ế của con người về các vấn đề. Thứ hai, FIS thực hiện việc
tính toán nhanh và xây dựng trên các kiến thức chuyên
1, ế môn. Cuối cùng, FIS có thể thực hiện với ít bộ nhớ. Cụ thể
~ (2)
, ế sự liên hệ này được minh họa như hình vẽ bên dưới.
0, ò ạ Fuzzy
Suy diễn mờ
Giải mờ
Môi Node
Hàm thành viên được minh họa bởi mô hình bên dưới. trường sensor
hóa
Tổng Node
WSN MAC giao
số Tri thức
node tiếp
Hình 7. Cấu trúc D - FLER
3.2. Thuật toán Fuzzy C- means (FCM) mở rộng
Hình 4. Hàm thành viên của số mờ hình thang Cho u u1 , u2 ,..., uc là phân hoạch mờ C.
Đối với tập mờ hình tam giác hàm thành viên ký hiệu u11 u1n
~
, , và được xác định như sau:
U cxn
u
, ế c1 u cn
~ , ế (3) FCM mở rộng là thuật toán dựa trên cơ sở của thuật
0, ò ạ toán FCM nhằm phân hoạch một tập n vectors đối tượng
- 12 Phạm Thị Dung, Lê Văn Sơn, Lê Thành Công, Đặng Hùng Vĩ
dữ liệu trong không gian d chiều , ,…, ∈ Giả sử, xem tập , , , , với 5, 5 ,
thành c nhóm mờ, tức là ⋃ dựa trên tính toán 6, 8 , 8, 10 , 9, 12 . Với 2, 0,01.
tối ưu hóa của hàm mục tiêu bởi công thức (4) xác định bên Cho tâm của hai cụm như sau 5, 7 , 8, 11
dưới sau: và được biểu diễn bởi ma trận phân hoạch sau:
∗
; , min ; ,
1,0 1,0 0,0 0,0
min ∑ ∑ ‖ ‖ ~ (4)
0,0 0,0 1,0 1,0
Trong đó, ∈ ∗ là ma trận phân hoạch mờ
với là giá trị hàm thành viên của phần tử thứ k ở cụm Hãy sử dụng thuật toán để xác định phân cụm tối ưu.
thứ i. Giải
, ,… , , ∈ là một vector cụm trung Theo tuần tự các bước của thuật toán FCM mở rộng,
tâm được xác định bởi công thức (5) bên dưới. với lần lặp đầu tiên:
∑
~ ‖ ‖ ~ ∑ (5)
∑
Với ∈ 1, ∞ là tham số mờ, và thường chọn m = 2.
∗
Kết quả xác định toạ độ các cụm cụ thể như sau:
Trong không gian tập tất cả các ma trận phân
hoạch mờ U được xác định bởi công thức (6) sau: 11/2,13/2 và 17/2,11 .
∗ ,∀ , : ∈ , Tiếp tục thực hiện bước 6 trong thuật toán, cụ thể sau:
∈
∑ 1 Khoảng cách Khoảng cách đối
(6)
đối với cụm 1 với cụm 2
0 ∑ 1
Như vậy, để tối thiểu hàm muc tiêu khi và chỉ khi các √10/2 √10/2
công thức (7) và (8) được xác định bên dưới. √10/2 √61/2
2√2 √5/2
∀ ∑ (7)
√170/2 √5/2
∑ Tiếp tục thực hiện các bước 7, 8 và đạt được kết quả như sau:
Và (8)
∑ Giá trị phụ thuộc đối với cụm 1 Giá trị phụ thuộc đối với cụm 2
Cụ thể hơn nữa, thuật toán FCM mở rộng được biểu u 0,5 u 1,0 0,5 0,5
diễn toàn bộ minh họa bởi một sơ đồ khối bao gồm 10 bước u 0,86 u 1,0 0,86 0,14
thực hiện tuần tự như sau:
u 0,09 u 1,0 0,09 0,91
Bắt đầu
u 0,03 u 1,0 0,03 0,97
Từ bảng trên, ta cập nhật lại ma trận phân hoạch ở lần
Nhập số cụm c; m = 2; 0 . Các
tập mờ con X = 1 , 2, … , lặp thứ nhất và kết quả đạt được như bên dưới.
Khởi tạo ma trận phân hoạch mờ 0,5 0,86 0,09 0,03
0
∈ , 0
0,5 0,14 0,91 0,97
1 ‖
1
Tiếp tục kiểm tra điều kiện dừng đối với thuật toán
tương ứng ở bước 8 như sau:
Xác định vector trung tâm , max
1, bởi
Phân hoạch các
∑
∑
1
1
;1 điểm thuộc các ↔ max
cụm
1
à ∈
↔ max 0,5 1,0 , 0,86 1,0 , 0,09 0,0 , 0,03
Xác định khoảng cách
2
‖ ‖2 0,0 , 0,5 0,0 , 0,14 0,0 , 0,91
Kết thúc 1,0 , 0,97 1,0 0,5
Cập nhật ma trận phân hoạch mờ 0,01
bởi
2 1
Lúc này, điều kiện ở bước 8 của thuật toán chưa thỏa
1
;1 ,1 mãn, nên chúng ta thực hiện tương tự ở các lần lặp tiếp theo.
1
Sau khi qua 4 lần lặp, tức là j = 4, kết quả cuối cùng
như sau:
Hình 8. Thuật toán FCM mở rộng
Gọi T là số lần lặp thực hiện của thuật toán FCM mở 0,83 0,87 0,05 0,04
rộng. Riêng đối với thuật toán này độ phức tạp của nó được 0,17 0,13 0,95 0,96
chứng minh chính là O(T).
- ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 12(97).2015, QUYỂN 2 13
Như vậy, với tập dữ liệu ban đầu chúng ta sẽ phân giới thiệu, đầu vào của nó chính là các giá trị rõ, cụ thể
∈ được tác giả định nghĩa nằm trong [0, 100]. Với các giá trị
hoạch các điểm và được kết quả như sau:
∈ rõ đầu vào, sau khi đi vào hệ thống điều khiển xử lý dưới
Ngoài ra, việc phân cụm đối với thuật toán FCM mở các suy diễn mờ sử dụng các biến ngôn ngữ, kết quả đầu ra
rộng cũng có thể minh họa bởi đoạn mã như sau: chính là một giá trị rõ nằm trong [0, 100]. Như vậy, dưới
sự hỗ trợ của công cụ Matlab [10] chúng ta sẽ xác định
, , _ , _
được các hàm thành viên của cấu trúc trên và cụ thể đạt
Với centrer: Biến dùng để thể hiện tọa độ của các cụm được kết quả như Hình 12.
trung tâm, cụ thể ở đây minh họa chỉ với 2 cụm trung tâm.
Sau khi chúng ta định nghĩa được các hàm thành viên,
U: Chứa giá trị hàm thành viên đối với mỗi điểm dữ liệu. tiếp tục đến với quá trình sinh luật. Cụ thể, tác giả chỉ định
obj_fcm: Chứa giá trị lịch sử của hàm mục tiêu mà mỗi nghĩa minh họa 19 luật trong tổng số 1125 luật như sau:
lần lặp lại.
Hình 9. Demo thuật toán FCM mở rộng
Kết quả sau khi phân tách các điểm thuộc 2 cụm được
thể hiện như hình vẽ bên dưới. Hình 13. Các luật của hệ thống
Lúc này, thời gian sống của các node Sensors trong hệ
thống mạng thay đổi với rất nhiều kịch bản thử nghiệm
chính là do sự thay đổi các tham số đầu vào Input mà chính
nhóm tác giả thiết kế.
Trường hợp 1, chỉ với 32 cụm minh họa, nhưng chúng
ta sẽ xác định được thời gian sống tối đa của hệ thống mạng
đạt được là t = 5/năm và cụ thể mô phỏng như sau:
Hình 10. Kết quả phân hoạch của thuật toán FCM mở rộng
4. Khảo sát và đánh giá
Riêng đối với bài báo này, nhằm tăng tuổi thọ của các
node Sensors trong hệ thống mạng, nhóm tác giả nghiên
cứu khả năng ứng dụng của logic mờ trong mạng cảm biến
không dây và thiết kế một mô hình mô phỏng cụ thể gồm
năm đầu vào và một đầu ra. Mô hình cụ thể như sau:
Hình 14. Thời gian sống của mạng với 32 cụm
Đối với trường hợp 2, hệ thống chỉ với 78 cụm thì kết
quả mô phỏng đạt được như sau:
Hình 11. Cấu trúc hệ thống 5 – Input và 1 – Output
Hình 15. Thời gian sống của mạng với 50 cụm
Tuy nhiên, nếu chúng ta thay đổi khu vực phân bố các
nodes trong mạng, chẳng hạn, các nodes phân bố trong một
khu vực giảm thì thời gian sống của nó cũng sẽ thay đổi,
cụ thể là t = 7,51/năm và kết quả như Hình 16.
Hình 12. Kết quả mô phỏng hàm thành viên của hệ thống
Nhiều kịch bản mô phỏng khác nhau nhằm đánh giá kết
Riêng đối với cấu trúc hệ thống ở hình trên, thực chất luận cuối cùng được tác giả thống kê qua bảng bên dưới
mỗi đầu vào chính là một bộ điều khiển mờ. Hệ này như đã trong Hình 17.
- 14 Phạm Thị Dung, Lê Văn Sơn, Lê Thành Công, Đặng Hùng Vĩ
5. Kết luận
Với nghiên cứu thể hiện trong bài báo, các tác giả đã hệ
thống hóa và mở rộng các thuật toán phân cụm nhằm cho
phép khảo sát đầy đủ về thời gian sống của WSN.
Đồng thời, nhóm nghiên cứu cũng đã tập trung xây
dựng các kịch bản khác nhau và tiến hành thử nghiệm với
các tham số đại diện đầu vào để đánh giá thời gian sống
của một WSN cụ thể và hiệu quả hơn.
Hình 16. Thời gian sống của mạng với Area giảm Riêng phần minh chứng cho cải tiến FCM được tiến
hành bằng nhiều cách, chẳng hạn như cách thực hiện thủ
sonutCH thoigiansong
công hoặc sự thay đổi kích cỡ, màu sắc của các nodes trong
12 3,71 cụm và được thể hiện dưới sự hỗ trợ của Matlab.
27 3,86
32 5 TÀI LIỆU THAM KHẢO
78 6 [1] D. R. I. Gupta and S. Sampalli, "Cluster -head election using fuzzy
logic for wireless sensor networks”, in 3rd Annual Conference on
Hình 17. Dữ liệu thử nghiệm khi thực hiện các kịch bản Communication Networks and Services Research, vol. 2, 2005.
Kết quả thống kê như sau: [2] http://bass.gmu.edu/matlab/labdocs/LabinsM.pdf
[3] http://en.wikipedia.org/wiki/Fuzzy_clustering
Đánh giá thời gian sống của mạng [4] http://en.wikipedia.org/wiki/G lobal_Positioning_System
[5] J. Ibriq and I. Mahgoub, "Cluster - based routing in wireless sensor
90 networks: issues and challenges (SPECTS)”, in Symposium on
80 Performance Evaluation of Computer Telecommunication Systems, 2004.
70 [6] Mohd Ezwan Jalil, “Positioning and Location Tracking Using
sonutCH Wireless Sensor Network”, 2011.
60
[7] Q. L. Haining Shu and J. Gao, "Wireless Sensor Network Lifetime
sonutCH
50 thoigiansong
Analysis Using Interval Type-2 Fuzzy Logic Systems”, IEEE
40 Transactions on Fuzzy Systems, vol. 16, no. 2, pp. 416-427, 2008.
30 [8] S. A. a. o. Budiarto. (2012, Jul.) The wireless sensor network.
20 [Online]. accessed on 26th Aug. 2012, http://students.netindonesia
.net/blogs/ui_thefarmers/archive/2010/04/23/wireless-sensor-
10
networks-how-do-theywork.aspx
0
[9] T.M. F. Kuhn and R. Wattenhofer, "Initializing newly deployed ad
3,71 3,86 5 6
thoigiansong T/năm hoc and sensor networks”, in 10th annual international conference
on Mobile computing and networking, New York, NY, USA, 2004,
Hình 18. Đánh giá thời gian sống của mạng pp. 260-274.
phụ thuộc vào sonutCH [10] X. Chen, "Research on hierarchical mobile wireless sensor network
architecture with mobile sensor nodes”, in 3rd International
Như vậy, thời gian sống của các node Sensors có xu
Conference on Biomedical Engineering and Informatics (BMEI),
hướng tăng lên khi số node chủ tăng lên. vol. 7, Oct. 2010, pp. 2863-2867.
(BBT nhận bài: 28/07/2015, phản biện xong: 11/10/2015)
nguon tai.lieu . vn
