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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

28
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đi sâu nghiên cứu và mở 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 khảo sát, phân tích thời gian sống (LifeTime) của các thành phần cấu thành của mạng cảm biến không dây (Wireless Sensor Network).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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)