Đề xuất cải thiện giao thức định tuyến SEP bằng cách sử dụng
phương tiện mờ không nhạy cảm trong mạng cảm biến không dây
TÓM TẮT:
Ngày nay, với sự phát triển nhanh chóng của khoa học và công nghệ và nhu cầu
ngày càng tăng trong mọi lĩnh vực, mạng cảm biến không dây đang nổi lên như
một thành tựu khoa học cần thiết để đáp ứng nhu cầu của con người trong xã hội
hiện đại. Mạng cảm biến không dây (WSN) được thiết kế để giúp chúng tôi không
mất quá nhiều năng lượng, lực lượng lao động, tránh nguy hiểm và chúng mang lại
hiệu quả cao khi làm việc. Các giao thức định tuyến khác nhau đang được sử dụng
để tăng hiệu quả năng lượng của mạng, với hai loại giao thức riêng biệt, đồng nhất
và không đồng nhất. Trong hai giao thức này, Stable Election Protocol SEP (Giao
thức lựa chọn ổn định) là một trong những giao thức không đồng nhất hiệu quả
nhất làm tăng tính ổn định của mạng. Trong bài báo này, chúng tôi đề xuất một
cách tiếp cận thuật toán εFCM trong việc phân cụm giao thức SEP, giúp mạng
WSN tiết kiệm năng lượng hơn. Kết quả mô phỏng cho thấy giao thức đề xuất
SEP-εFCM hoạt động tốt hơn giao thức SEP thông thường
TỪ KHÓA:
Wireless sensor network (WSN), Insensitive Fuzzy C-Means, Stable Election
Protocol(SEP), SEPInsensitive Fuzzy C-Means.
1. GIỚI THIỆU
WSN là một mạng gồm các nút cảm biến được kết nối với nhau. Các nút cảm
biến được thiết kế nhỏ gọn và chi phí thấp. Các nút chịu trách nhiệm cảm nhận các
điều kiện môi trường xung quanh như nhiệt độ, âm thanh, độ rung, độ ẩm, áp suất,
v.v ... Các nút cảm biến gửi dữ liệu cảm nhận của chúng đến nút tổng hợp và
truyền dữ liệu đến Chìm (thu phát). Như được hiển thị trong Hình 1, Sink được
truyền qua internet hoặc vệ tinh tới người dùng. Trong quá trình này, chúng ta thấy
rằng CH (Head Cluster) không chỉ nghe tín hiệu từ các nút mà còn không tổng hợp
dữ liệu, sau đó truyền dữ liệu trên Sink làm tiêu thụ nhiều năng lượng hơn, do đó,
định tuyến, chỉ định đường dẫn của luồng dữ liệu này là rất quan trọng.

Hình 1: Cấu trúc cơ bản của mạng cảm biến không dây
Các giao thức định tuyến được chia thành hai loại là đồng nhất và không đồng
nhất. Các giao thức định tuyến đồng nhất là các nút có cùng mức năng lượng với
các giao thức: LEACH, TEEN, HEED, PEGASIS, APTEEN. Giao thức không
đồng nhất là một giao thức trong đó các nút có các mức năng lượng khác nhau và
được chia thành hai loại nút: nút Advance và nút Bình thường. Trong đó, nút
Advance có nhiều năng lượng hơn và xác suất trở thành nút nhiều hơn nút còn lại.
Các giao thức phổ biến trong loại giao thức này là SEP [1-5], DEEC, EDEEC.
Giao thức SEP xem xét các mức năng lượng trong quy trình lựa chọn CH và cải
thiện tính ổn định của quy trình phân cụm phân cấp bằng cách sử dụng các tham số
đặc trưng của tính không đồng nhất, thêm năng lượng giữa nút trước và nút bình
thường. Để kéo dài thời gian ổn định, SEP cố gắng duy trì mức tiêu thụ năng lượng
hạn chế. Các nút trước sẽ trở thành CH nhiều hơn các nút bình thường và sẽ được
cấp nguồn nhiều hơn các nút bình thường. Tuy nhiên, việc lựa chọn Head Cluster
trong giao thức SEP có một nhược điểm là từ hai loại nút Advance nút và nút Bình
thường không linh hoạt, do đó, các nút từ xa sẽ chết trước. Để giải quyết vấn đề
này, chúng tôi đã tiến hành nghiên cứu về SEP và đánh giá một số thuật toán phân
cụm nổi tiếng như K-Means, Fuzzy CMeans, Insensitive Fuzzy C-Means trong
phân cụm WSN. Dựa trên lý thuyết học tập, chúng tôi đề xuất một phương pháp
mới kết hợp thuật toán C-Means không nhạy cảm vào giao thức SEP, có thể giúp
mạng WSN tiết kiệm năng lượng hơn. Ngoài ra, chúng tôi đã sử dụng Matlab để
mô phỏng thuật toán mới, cho 140 nút trong mạng 500x500, với năng lượng không
đồng đều giữa các nút để hiển thị ảnh hưởng không đồng đều giữa các nút trong
mạng. 10% các nút có 1 năng lượng Joule và 90% các nút có 0,5 năng lượng
Joules. Vị trí của Sink được thiết lập ở (250.250) và độ dài của mỗi tin nhắn là


500byte. Kết quả mô phỏng cho thấy giao thức SEP-εFCM được đề xuất thực hiện
tốt hơn giao thức SEP thông thường.
Bài viết của chúng tôi bao gồm năm phần: Phần 1 là giới thiệu, Phần 2 cho thấy

các công việc liên quan, đề xuất Phần 3, Kết quả mô phỏng Phần 4 và Phần cuối
cùng là kết luận.
2. Một vài đặc trưng:
Nếu LEACH là Malik M.et al. [6] được đưa ra như một giao thức cơ bản để
định tuyến và các giá trị có hiệu quả cho các mạng WSN, Smaragdakis đã giới
thiệu một giao thức định tuyến SEP mang tính cách mạng. SEP là một giao thức
định tuyến không đồng nhất và đã được chứng minh là hiệu quả hơn giao thức
LEACH. Trong giao thức SEP, các cảm biến nút được chia thành hai loại nút: nút
trước và nút bình thường trong đó nút trước được thiết kế để có mức năng lượng
cao hơn và xác suất trở thành nút CH so với nút bình thường. Như được hiển thị
trong Hình 2


Hình 2: Biểu đồ luồng của CH Lựa chọn trong giao thức SEP
Trong đó:
-

- G’: Nút bình thường không trở thành CH.
T (S’): là ngưỡng được áp dụng cho nút bình thường.
G”: nút nâng cao không trở thành CH.
T (S”) là ngưỡng được áp dụng cho nút nâng cao.

Nếu thuật toán K-Means [5] là thuật toán phân cụm được xác định rõ, điều đó
có nghĩa là một nút chỉ thuộc về một cụm, chỉ phù hợp để khám phá các cụm mật
độ cao và bị cô lập và phải xác định ranh giới. Tuy nhiên, trong thực tế khi triển


khai WSN, ranh giới giữa các cụm có thể bị mờ, các cụm có thể chồng lấp, có
nghĩa là một số nút thuộc về các cụm khác nhau. Vì vậy, trong trường hợp này, sử
dụng thuật toán K-mean sẽ giới hạn chức năng của mạng cảm biến không dây, do

đó thuật toán Fuzzy c-means (FCM) [7-9] đã ra đời để giải quyết vấn đề này. FCM
là một thuật toán phân cụm mờ do Dunn phát triển vào năm 1973 và sau đó được
Bezděk cải tiến vào năm 1981. Kỹ thuật này chia một tập hợp các đối tượng dữ
liệu vectơ X = {x1, ..., xn} R thành các nhóm mờ dựa trên các nhóm mờ về việc tối
thiểu hóa hàm mục tiêu để đo chất lượng của phân vùng và tìm các tâm cụm trong
mỗi cụm, do đó chi phí của phép đo không tương tự là tối thiểu.
Đến năm 1998, Vapnick đề xuất sử dụng tham số được gọi là tham số nhạy với
nhiễu để giải quyết các cụm mật độ cao chồng lấp, trong đó một nút không chỉ
được gắn vào một cụm mà có thể thuộc về một cụm hoặc nhiều cụm khác nhau. Kể
từ đó, εFCM [10-14] luôn là lựa chọn hàng đầu cho phân cụm mờ.
Trong bài viết này, các kết quả mô phỏng cho thấy rằng việc lựa chọn nút CH
bằng thuật toán εFCM làm giảm mức tiêu thụ năng lượng của WSN.
3. ĐỀ XUẤT THUẬT TOÁN
Giao thức không đồng nhất SEP đã được Smaragdakis chứng minh là mang lại
sự ổn định và tuổi thọ dài hơn các giao thức hợp nhất. Tuy nhiên, chúng vẫn chứa
một số hạn chế, bao gồm phân cụm hạn chế cho các cụm mật độ nút cao và phân
phối đa chiều phức tạp, phân cụm dẫn đến các cụm không đồng đều. (Ít cụm nút và
nhiều cụm nút) gây ra cân bằng tải mạng.
Trong bài báo này, chúng tôi đề xuất sử dụng thuật toán εFCM để chọn các
nút CH cho giao thức SEP và việc chọn nút này ban đầu ưu tiên cho nút nút để tận
dụng nguồn năng lượng bổ sung này làm CH Node để tạo thời gian ổn định nhất
cho mạng . Sau khi các nút trước tiêu thụ năng lượng còn lại và năng lượng bằng
với nút bình thường, thì εFCM sẽ tiến hành chọn nút CH trên toàn bộ mạng, ưu
tiên nút đó có nhiều năng lượng hơn sẽ được tạo nút CH. Hàm mục tiêu của thuật
toán εFCM được định nghĩa như sau:

Trong đó:


, Ɛ là mức không nhạy cảm với tiếng ồn được

Vapnick đề xuất vào năm 1998 như sau:

Các bước của thuật toán εFCM:
Đầu vào: Số cụm c và tham số m, Ɛ cho hàm mục tiêu J;
Đầu ra: Dữ liệu cụm sao cho hàm mục tiêu (1) đạt giá trị tối thiểu;
Begin
1. Nhập tham số c (1< c < n ), m (1 Khởi tạo ma trận V= [vij], V(0) ϵ Rsxc , Đặt j=0;
2. Repeat
J:=j+1;
Tính ma trận phân vùng mờ U(j) theo công thức (2);
Cập nhật cụm trung tâm V(j) = [V1(j),V2(j),….,Vc(j)] theo
công thức (3) và U(j).
3. Until (||U(j+1) - U(j) ||F <= Ɛ);
4. Chứng minh kết quả của các cụm;
End


Giao thức SEP [10-12] có tính đến mức năng lượng trong quy trình chọn nút
chính. SEP cải thiện tính ổn định của quá trình phân cụm theo phân cấp bằng cách
sử dụng các tham số đặc trưng của không đồng nhất, năng lượng bổ sung giữa nút
nâng cao và nút bình thường. Để kéo dài thời gian ổn định, SEP cố gắng duy trì
giới hạn tiêu thụ năng lượng. Các nút nâng cao trở thành CH thường xuyên hơn các
nút bình thường. Các nút nâng cao thường có nhiều năng lượng hơn nút bình
thường. Tổng năng lượng của hệ thống khác nhau. Giả sử Eo là năng lượng ban
đầu của nút bình thường, năng lượng của nút nâng cao được đặt thành Eo * (1 + α).
Tổng năng lượng cần thiết để thiết lập (mới) tương đương với: n * (1-m) * Eo + n
* m * Eo (1 + α) = n * Eo (1 + αm). Do đó, tổng năng lượng của hệ thống được
tăng lên (1 + αm) lần. Chúng ta có thể tăng độ ổn định của mạng cảm biến (1 +
αm) lần.

Xác suất để nút bình thường trở thành CH là 1 và nút nâng cao trở thành CH
là 1 + α. Nếu ngưỡng T (n) được đặt thành bình thường và nút nâng cao khác nhau
thì nút bình thường của G sẽ trở thành cụm đầu tiên một lần và nút nâng cao của G
trở thành cụm đầu tiên 1 + α lần. Pnrm được định nghĩa là xác suất chọn trọng số
cho các nút bình thường và xác suất chọn trọng số cho các nút nâng cao. Vì vậy,
xác suất trọng lượng cho nút bình thường và nút nút nâng cao là:

Hàm T (n) được thay thế bằng Popt bằng xác suất trọng lượng để đạt ngưỡng
lựa chọn CH trong mỗi vòng.
Ngưỡng cho nút bình thường:

Trong đó:
- r: vòng lặp hiện tại
- G’: Nút bình thường không trở thành CH với chu kỳ 1 / Pnrm cuối mỗi pha.
- T (Snrm) là ngưỡng áp dụng cho nút bình thường n (1 - m). Điều này đảm
bảo rằng mỗi nút bình thường trở thành CH một lần trong 1/Popt(1 + αm)


mỗi pha và đó là trung bình của các nút bình thường trở thành CH mỗi vòng
là n (1-m) * Pnrm
Ngưỡng cho nút nâng cao

Trong đó:
- G”: nút nâng cao không trở thành CH CH trong 1/Padv chu kỳ cuối mỗi giai
đoạn.
- T (Sadv) là ngưỡng được áp dụng cho nút nâng cao n * m.
Chúng tôi coi giai đoạn này là giai đoạn thứ cấp. Mỗi giai đoạn có 1 + α giai
đoạn phụ và nút nâng cao trở thành CH chính xác 1 + α lần trong pha. Trung bình
của nút nâng cao trở thành CH cho mỗi chu kỳ có n * Padv.
Vậy số CHs trung bình mỗi vòng là: n * (1-m) * Pnrm + n * m * Padv = n *

Popt. Đây là số lượng CHs mong muốn trong mỗi giai đoạn.
4. GIẢ LẬP VÀ ĐÁNH GIÁ
Trong bài báo này, chúng tôi sử dụng phần mềm Matlab (R2016a) để thực hiện
mô phỏng, cho 140 nút có tọa độ cố định trong mạng 500x500, với năng lượng
không đồng đều giữa các nút để hiển thị ảnh hưởng không đồng đều giữa các nút
trong mạng. 10% nút có 1 năng lượng Joules (a = 1, Popt = 0,1), 90% nút có 0,5
năng lượng Joules. Vị trí của Sink được đặt ở (250.250), độ dài của mỗi tin nhắn là
500byte, hệ số khuếch đại efs = 10pJ / bit / m2 và e mp = 0,0013pJ / bit / m4, số
vòng lặp tối đa là 6000. Các tham số đầu vào được cố định, tác giả sẽ lần lượt đưa
các tham số này vào chạy giao thức SEP và giao thức được đề xuất SEP_ FCM.
Sau đó, chúng tôi so sánh giữa giao thức kết hợp giao thức SEP và SEP_ FCM dựa
trên các số liệu như: số nút sống, số nút chết và năng lượng còn lại của các nút.


4.1 KẾT QUẢ SAU 1200 VÒNG ĐẦU TIÊN
Trong Hình 3, trên giao thức SEP, chúng ta thấy rằng sau 1200 chu kỳ, nút chết
đã xuất hiện, trong khi trong liên kết SEP_ εFCM, chúng ta thấy kết quả sau 1200
chu kỳ trong Hình 4 cho thấy không có nút chết.


Hình 3: Giao thức SEP sau 1200 vòng

Hình 4: Giao thức liên kết SEP_ εFCM sau 1200 vòng
4.2 SỐ LƯỢNG NÚT SỐNG


Hình 5 cho thấy số lượng còn sống trong suốt vòng đời của mạng. Sau 800 chu
kỳ, SEP xuất hiện dưới dạng nút chết đầu tiên, sau khi 2790 vòng lặp SEP_ εFCM
xuất hiện. Giao thức được đề xuất cao hơn 21% SEP trong số các vòng mà nút cuối
cùng chết.

Do đó, các nút sống trong giao thức kết hợp SEP_ εFCM có nhiều nút sống hơn
giao thức SEP. Sau một vài vòng ban đầu không ổn định, nhưng sau đó số lượng
nút sống bắt đầu tăng lên, điều này chứng tỏ rằng giao thức kết hợp SEP_ εFCM
tiêu thụ năng lượng hiệu quả hơn so với giao thức SEP. Kết quả cho giao thức kết
hợp SEP_ εFCM đã cải thiện nhiều nút trực tiếp hơn giao thức SEP.

Hình 5: So sánh nút sống giữa giao thức SEP và giao thức SEP_ εFCM
4.3 NĂNG LƯỢNG CÒN LẠI:
Trong Hình 6, chúng ta thấy rằng, sau 4985 vòng chạy, nút trong SEP đã chết
hết và 5150 nút SEP_ εFCM. Giao thức đề xuất cao hơn 3,3% SEP. Kết quả cho
thấy năng lượng còn lại của giao thức kết hợp SEP_ εFCM lớn hơn năng lượng của
giao thức SEP. Kết quả của giao thức kết hợp SEP_ εFCM đã cải thiện năng lượng
còn lại của giao thức SEP.


Hình 6: So sánh năng lượng còn lại giữa giao thức SEP và giao thức SEP_ εFCM
5. KẾT LUẬN
Thiết kế mạng WSN với chức năng tốt, linh hoạt và dễ triển khai cho các ứng
dụng trong thế giới thực có nhiều khó khăn, với khó khăn lớn nhất hiện nay là sức
mạnh nút hạn chế và khó tải lại. Do đó, sử dụng tài nguyên năng lượng có sẵn trên
các nút giúp giảm hiệu quả tiêu thụ năng lượng giúp kéo dài tuổi thọ của toàn
mạng, giúp tăng tuổi thọ của mạng. Chúng tôi đã nghiên cứu các giao thức định
tuyến để đề xuất thuật toán mới sử dụng thuật toán mờ εFCM trong việc lựa chọn
CH nút vào giao thức SEP. Kết quả mô phỏng cho thấy cải tiến của chúng tôi có
mức tiêu thụ điện năng thấp hơn và tuổi thọ mạng dài hơn so với 3,3%
SEPprotatio. Điều này giúp mạng kéo dài tuổi thọ.
TÀI LIỆU THAM KHẢO
[1]. D. M. a. T. Z. K. Sohraby (2007), Wireless Sensor Network Technology,
Protocol, And Application, John Wiley & Sons, Inc.
[2]. S. Basagni (1999), Distributed Clustering Algorithm for Ad Hoc Networks,

Proc. Int’l. Symp. Parallel Architectures, Algorithms, and Networks.


[3]. S. B. a. S. Khuller (Apr. 2001), A Clustering Scheme for Hierarchical Control
in Multihop Wireless Networks, Proc. IEEE INFOCOM.
[4]. Srinivas Sivarathril and A.Govardhan2 (September 2014), “Experiments on
Hypothesis Fuzzy KMeans is Better Than K-Means for Clustering”, International
Journal of Data Mining & Knowledge Management Process (IJDKP) Vol.4, No.5.
[5]. Keerthi M, M.Tech 2nd year and Dr. B. Satish Babu,Professor (August 2012),
“An Improved FCM’s Clustering Protocol for Wireless Sensor Networks”,
International of Electronics and Communications (IJEC), Volume-1,Issue-1.
[6]. Meena Malik, Yudhvir Singh, Anshu Arora (February 2013), “Analysis of
LEACH Protocol in Wireless Sensor Networks”, International Journal of Advanced
Research in Computer Science and Software Engineering, Volume 3, Issue 2, pp.
178-183.
[7]. Maurad Hadjilal, Hervé Guyennet1, Mohammed Feham (2013), “EnergyEfficient in wireless sensor networks using fuzzy C-Means clustering approach”,
International Journal of Sensors and Sensor Network.
[8]. A. S. Raghuvanshi*, S Tiwari, R Tripathi and N. Kishor “Optimal Number of
Clusters in Wireless Sensor Networks: An FCM Approach”Motilal Nehru National
Institute of TechnologyAllahabad -211004, INDIA.
[9]. Raja Dutta, Shishir Gupta, Mukul K. Das (November 2014), “Low-Energy
Adaptive Unequal Clustering Protocol Using Fuzzy c-Means in Wireless Sensor
Networks”, Wireless Personal Communications, Springer, Volume 79, Issue 2, pp.
1187-1209.
[10]. I. M. Georgios Smaragdakis, Azer Bestavros (2004), “SEP : A Stable Election
Protocol for clustered heterogeneous wireless sensor networks”, Computer Science
Department Boston Univercity Boston, MA 02215, USA. International Journal of
Computer Networks & Communications (IJCNC) Vol.9, No.6, November 2017
[11]. G. Smaragdakis, I. Matta, A. Bestavros (2004), SEP: A Stable Election
Protocol for clustered heterogeneous wireless sensor networks, in: Second

International Workshop on Sensor and Actor Network Protocols and Applications
(SANPA 2004).
[12]. K. Latif, M. Jaffar, N.Javaid, M. N. Saqib, U. Qasim, Z. A. Khan (2012),
“Performance Analysis of Hierarchical Routing Protocols in Wireless Sensor
Networks” arXiv : 1208.2397v1 [cs.NI].


[13]. Dr. Firas Ali Al-Juboori, Eng. Sura F. Ismail (2013) “Performance Analysis of
Variable Energy Levels of Clustering Protocols for Wireless Sensor Network”
IJCSI International Journal of Computer Science Issues, Vol.10,No 1.
[14]. Bharti Kandari, Rajdeep Singh (2014) “K-SEP: A more stable SEP using KMeans Clustering and Probabilistic Transmission in WSN” INPRESSCO
International Journal of Current Engineering and Technology, Vol.4, No.4.
TÁC GIẢ
Phan Thi The được sinh ra ở Việt Nam năm 1982. Cô lấy bằng thạc sỹ về Mạng
và truyền số liệu tại Học viện Bưu chính – Viễn thông Hồ Chí Minh, Việt Nam vào
năm 2012. Hiện nay, cô đã lấy học vị Tiến sĩ Hệ thống thông tin của Học viện
Công nghệ Bưu chính Viễn thông, Việt Nam vào năm 2019. .Cô đang giảng dạy ở
trường đại học Thủ Đức.
Ngo Quang Quyen được sinh ra tại Việt Nam vào năm 1985. Anh đã nhận bằng
B.E tại Đại học Công nghiệp thành phố Hồ Chí Minh, Việt Nam, 2012. Anh hiện là
Thạc sĩ Hệ thống thông tin của Học viện Công nghệ Bưu chính Viễn thông, Việt
Nam năm 2017. Anh đang làm việc tại Bệnh viện Nhi đồng 2
Trần Công Hùng được sinh ra ở Việt Nam năm 1961. Ông đã nhận bằng B.E về
kỹ thuật điện tử và viễn thông khóa đầu tiên của Đại học Bách khoa tại Việt Nam,
1987. Ông đã nhận bằng B.E về tin học và kỹ thuật máy tính từ Đại học Bách khoa
Hồ Chí Minh tại Việt Nam, 1995. Ông nhận bằng thạc sĩ kỹ thuật viễn thông từ
khoa sau đại học Đại học Bách khoa Hà Nội tại Việt Nam, 1998. Ông nhận bằng
tiến sĩ tại Đại học Bách khoa Hà Nội tại Việt Nam, 2004. Các lĩnh vực nghiên cứu
chính của ông là các thông số hiệu suất B - ISDN và phương pháp đo, QoS trong
các mạng tốc độ cao, MPLS. Ông hiện là Phó giáo sư tiến sĩ của Khoa Công nghệ

Thông tin II, Học viện Công nghệ Bưu chính và Viễn thông tại Hồ Chí Minh, Việt
Nam.