- Trang Chủ
- Quản trị mạng
- Cải tiến giao thức định tuyến LEACH nhằm nâng cao tuổi thọ cho mạng cảm biến không dây
Xem mẫu
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
CẢI TIẾN GIAO THỨC ĐỊNH TUYẾN LEACH NHẰM NÂNG CAO TUỔI THỌ CHO
MẠNG CẢM BIẾN KHÔNG DÂY
Dương Thị Hằng và Phạm Thị Quỳnh Trang
Khoa Điện tử,
Trường Đại học Công nghiệp Hà Nội
Email: hangdt@haui.edu.vn pham.trang@haui.edu.vn
Abstract— Giao thức định tuyến phân cụm thích ứng TEEN (Threshold-sensitive Energy Efficient sensor
năng lượng thấp, LEACH (Low-Energy Adaptive Network - TEEN) [5]... LEACH là giao thức tiếp cận
Clustering Hierarchy – LEACH) đã được đề xuất dành định tuyến phân cấp đầu tiên và được dùng phổ biến
riêng cho mạng cảm biến không dây (Wireless Sensor nhất [6]. Trong giao thức LEACH, các nút cảm biến
Network – WSN) trong bài toán tăng tuổi thọ của hệ được tập hợp thành từng cụm, các cụm thực hiện chức
thống. Tuy nhiên, LEACH chưa xem xét đầy đủ tiêu chí năng thu thập và truyền dữ liệu tới trạm gốc (BS) thông
phân cụm và chọn các nút chủ cụm (Cluster Head – CH). qua nút chủ cụm (CH). Với nguyên lý này, LEACH có
Trong bài báo này, chúng tôi đề xuất cải tiến giao thức thể kéo dài tuổi thọ của mạng, giảm năng lượng tiêu
LEACH bằng cách kết hợp sử dụng thuật toán K-means
thụ của mỗi nút, tập trung dữ liệu để giảm bản tin
để phân cụm và lựa chọn các nút làm CH sao cho tổng
truyền trong mạng.
khoảng cách các nút trong cụm đến CH và từ CH đến
trạm gốc (Base Station – BS) là nhỏ nhất, dẫn đến việc Ý tưởng của LEACH là động lực cho rất nhiều giao
tiêu thụ năng lượng trung bình trong mạng giảm và kéo thức định tuyến phân cấp khác phát triển. Tác giả [7]
dài tuổi thọ của mạng. Các kết quả mô phỏng chứng tỏ đề xuất giao thức I-LEACH (Improved LEACH) thông
rằng, so với một số giao thức định tuyến hiện có, giao
thức đề xuất làm tăng đáng kể tuổi thọ của WSN. Đặc
qua việc chọn các nút cảm biến có năng lượng dư cao
biệt khi đánh giá về mức tiêu thụ năng lượng của New - hơn làm CH, [8] sử dụng thuật toán K-means để xác
LEACH với thuật toán LEACH và I-LEACH, tỉ lệ chết định CH, [9] đề xuất LEACH-C (LEACH-Centralized)
các nút cảm biến (SN – Sensor Node) của thuật toán đề thực hiện tập trung dữ liệu về thông tin của toàn bộ nút
xuất giảm xuống một cách rõ rệt và tuổi thọ mạng tăng cảm biến về trạm gốc rồi tiến hành chọn CH và hình
vượt trội trong khoảng 43% và 27% so với LEACH và I- thành cụm…Trong bài báo này, nhóm tác giả đề xuất
LEACH. giao thức New-LEACH nhằm cải tiến giao thức
LEACH bằng việc sử dụng thuật toán K-means để
Keywords- Mạng cảm biến không dây, giao thức định
phân cụm căn cứ theo mật độ SN với số lượng cụm
tuyến, tuổi thọ của mạng.
như giao thức LEACH kết hợp với việc chọn CH là nút
có tổng khoảng cách các nút trong cụm đến CH và từ
I. GIỚI THIỆU CH đến BS là nhỏ nhất. Việc chọn CH theo cách này sẽ
Mạng cảm biến không dây (WSN) bao gồm các nút đảm bảo năng lượng tiêu thụ của CH là tối ưu [6], kéo
cảm biến (Sensor Node - SN) với năng lượng hạn chế, dài tuổi thọ của mạng. Hiệu quả của đề xuất sẽ được
các SN thu thập các tham số môi trường và truyền mô phỏng và so sánh với giao thức LEACH và I-
thông tin đến trạm gốc (BS) nhằm theo dõi và phát hiện LEACH.
các thông số tùy theo ứng dụng khác nhau [1]. Do
WSN thường được triển khai trong phạm vi lớn và môi II. CƠ SỞ LÝ THUYẾT
trường khắc nghiệt, việc sạc hoặc thay pin của SN rất
khó khăn nên vấn đề sử dụng hiệu quả năng lượng pin A. Giao thức định tuyến LEACH
của SN được coi là mục tiêu chính khi nghiên cứu thiết
kế các giao thức truyền dẫn và kiến trúc phần cứng [2]. LEACH là giao thức phân cấp được đề xuất bởi
Heinzelman và các cộng sự trong công trình [3], dựa
Với đặc điểm của mạng cảm biến không dây, việc
tăng tuổi thọ của mạng nói chung và tăng tuổi thọ của trên việc tự phân cụm với các SN phân bố ngẫu nhiên.
từng nút mạng nói riêng luôn là một vấn đề được quan CH có chức năng điều khiển các nút trong cụm gửi dữ
tâm của các nhà nghiên cứu và chế tạo. Các loại giao liệu đến nó theo một chu kỳ nhất định. Tại CH, dữ liệu
thức định tuyến được chia thành ba loại: giao thức định sẽ được thu thập và xử lý tùy thuộc vào từng ứng dụng
tuyến dựa trên phân cấp, giao thức định tuyến trung
trước khi gửi tới BS. Hình 1 mô tả giao thức định tuyến
tâm dữ liệu và giao thức định tuyến dựa trên vị trí. Với
giao thức định tuyến dựa trên phân cấp, nhiều giao thức LEACH.
đã được đề xuất, như giao thức LEACH [3], HEED
(Hybrid Energy-Efficient Distributed – HEED) [4],
ISBN 978-604-80-5958-3 432
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
SN lân cận trong mạng thông tin chúng là CH mới. Để
tránh xung đột với các CH khác, LEACH sử dụng
phương thức đa truy cập dựa trên cảm nhận sóng mang
BS
CSMA (Carrier Sense Multiple Access – CSMA). Khi
các SN nhận được thông tin quảng bá từ các CH,
chúng sẽ xác định CH mà chúng thuộc về. Nếu SN chỉ
nhận được một thông tin quảng bá từ một CH, thì SN
này sẽ tự động trở thành thành viên của cụm đó. Nếu
SN nhận được thông tin quảng bá từ nhiều CH, việc lựa
Cụm 3
chọn CH dựa trên cường độ tín hiệu mà SN nhận được
từ CH, CH có cường độ tín hiệu cao nhất sẽ được chọn.
CH
Cụm 1
Nút trong cụm
Sau khi tạo cụm xong, giai đoạn tạo lịch được thực
hiện, trong đó CH chỉ định thời gian mà các SN có thể
Cụm 2
gửi dữ liệu đến CH theo phương pháp đa truy cập phân
chia theo thời gian (Time Division Multiple Access –
Hình 1. Giao thức định tuyến LEACH TDMA) và lịch này được quảng bá cho các SN thành
Hoạt động của LEACH được chia thành các vòng viên trong cụm. Các CH chọn một mã CDMA và phân
(round), mỗi vòng gồm hai pha: pha thứ nhất là pha phối đến các SN trong cụm, căn cứ vào mã này để lọc
thiết lập (set-up phase), pha này diễn ra quá trình chọn các dữ liệu của các SN trong cụm và cũng chọn một mã
CH và thành lập cụm và pha thứ hai là pha ổn định CDMA để truyền dữ liệu đến BS. Sau khi pha thiết lập
hoàn thành, LEACH chuyển sang pha trạng thái ổn
trạng thái (steady-state phase), pha này diễn ra quá định. Trong pha này, các SN bắt đầu cảm biến dữ liệu
trình truyền dữ liệu từ SN đến CH và từ CH đến BS. và truyền tới CH theo thời gian đã lập ở giai đoạn lập
Trong giao thức LEACH việc lựa chọn CH được tiến lịch. Khi một SN chờ đến lượt mình truyền dữ liệu, nó
hành khi bắt đầu một vòng mới. Các SN tự quyết định có thể chuyển sang trạng thái ngủ để tiếp kiệm năng
có hay không trở thành CH tại mỗi vòng hoạt động. Cơ lượng. Cuối trang thái ổn định, mạng đi vào pha thiết
sở để SN đưa ra quyết định làm CH là xác suất mong lập một lần nữa để tham gia vào vòng tiếp lựa chọn CH
mới.
muốn trở thành CH trong mạng ( P ) và số lần SN đó
đã trở thành CH tính cho đến vòng hiện tại. Mỗi SN B. Cải tiến giao thức LEACH
trong WSN lựa chọn một giá trị ngẫu nhiên ( S ) trong
khoảng 0 và 1, nếu giá trị này thấp hơn giá trị ngưỡng Với cách thức LEACH hoạt động như đã phân tích
T ( n ) , SN trở thành CH của vòng hiện tại. Ngược lại, trong mục A, yêu cầu năng lượng của hệ thống được
phân phối cho tất cả các nút, tự phân cụm không cần
nếu S lớn hơn T ( n ) thì SN đó là SN thông thường.
điều khiển từ BS, các SN ngủ khi chờ truyền dữ liệu
Giá trị ngưỡng ) được xác định bởi công thức (1):
dẫn đến tiết kiệm năng lượng của hệ thống. Tuy nhiên,
P LEACH có các hạn chế sau:
, nG
1 P r mod 1 i) Không xem xét đến năng lượng còn lại của SN: Vì
T ( n) (1)
chọn CH là ngẫu nhiên có thể dẫn đến một SN còn lại
P
ít năng lượng được chọn làm CH.
0
, nG
ii) Các CH ở xa BS hơn sẽ tiêu thụ năng lượng hơn và
với r 0 là vòng hiện tại, G là tập các nút chưa trở nhanh chóng dừng hoạt động.
thành CH trong 1 P vòng trước đó. iii) Số cụm và số lượng thành viên trong một cụm phân
chia không đều, có thể hai SN gần nhau đều là CH dẫn
Với ngưỡng T ( n ) này, mỗi SN sẽ trở thành CH vào
đến tuổi thọ của các CH khác nhau.
một thời điểm trong chu kỳ 1 P vòng. Trong vòng 0 Để khắc phục các hạn chế của LEACH, chúng tôi đề
( r 0 ), mỗi SN có một xác suất trở thành CH là P . xuất giao thức New-LEACH, trong đó sử dụng thuật
Các SN đã là CH trong vòng 0, không thể là CH cho toán K-means để phân cụm nhằm khắc phục hạn chế
1 P 1 vòng tiếp theo, vì vậy xác suất trở thành CH (iii) kết hợp việc chọn CH sao cho tổng khoảng cách
của các SN còn lại tăng lên. Tại vòng 1 P 1 , giá trị các nút trong cụm đến CH và từ CH đến BS là nhỏ nhất
T (n ) 1 đối với các SN chưa làm CH, vì vậy các nút nhằm khắc phụ hạn chế (i), (ii).
này sẽ trở thành CH và sau 1 P vòng, tất cả các SN Thuật toán K-means được đề xuất bởi MacQueen trong
một lần nữa lại đủ điều kiện trở thành CH. Sau khi [10] thuộc lớp phương pháp học không giám sát
được chọn là CH, các CH này phát quảng bá cho các (Unsupervised Learning) trong học máy (Machine
ISBN 978-604-80-5958-3 433
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
Learning). Mục đích chính của K-means là tìm cách vùng mô phỏng. Ngoài ra các tham số mô phỏng chọn
phân nhóm các đối tượng (objects) đã cho vào cụm ( theo các đề xuất [7], [9] với các giá trị như trong bảng
là số các cụm được xác đinh trước, nguyên dương) sao 1.
Để có các kết quả mô phỏng biểu diễn trên hình 3
cho tổng bình phương khoảng cách giữa các đối tượng
phương pháp mô phỏng Monte Carlo và phần mềm
đến tâm nhóm (centroid) là nhỏ nhất. Trong WSN, MATLAB 2018ª được sử dụng. Nguyên lý của phương
khoảng cách giữa và được tính như công thức (2) pháp này có thể diễn đạt như sau : xét một vòng hoạt
động WSN, hình 3a biểu diễn các cụm đã được phân
chia theo đề xuất của giao thức LEACH. Ở đây, các SN
Di , j ( x j xi )2 (y j yi )2 (2)
có dấu được lựa chọn ngẫu nhiên làm CH, với việc
với ( xi , yi ) , ( x j , y j ) lần lượt là tọa độ của SNi phân vùng như hình 3a, cách làm này còn tồn tại nhược
điểm là không xem xét đến năng lượng còn lại của SN,
và SN j . Vì vậy rất có thể khi lựa chọn CH ngẫu nhiên sẽ xuất
hiện trường hợp một SN có năng lượng thấp lại được
Hình 2 mô tả lưu đồ thuật toán thực hiện New-LEACH chọn làm CH. Mặt khác, nếu các CH ở xa BS thì việc
với các bước thực hiện cơ bản như sau: tiêu thụ năng lượng sẽ tốn kém hơn và rơi vào trạng
Bước 1: Chọn số cụm của mạng theo giá trị ngưỡng thái dừng hoạt động.
trong công thức (1). Nếu không có nút nào thỏa mãn Bảng 1: Các tham số mô phỏng
điều kiện nhỏ hơn , tất cả các nút trong WSN truyền
Tham số Giá trị
dữ liệu trực tiếp về BS.
Bước 2: Phân chia các nút trong cụm bằng thuật toán Diện tích vùng mô phỏng 100 x 100 m2
K-means. Tổng số SN 100
Bước 3: Xác định nút có tổng khoảng cách từ nó đến Xác suất SN trở thành 0,1
các nút khác trong cụm nhỏ nhất, đặt nút này làm CH. CH
Bắt đầu Vị trí SN Ngẫu nhiên
Vị trí BS (100,100)
Thiết lập các tham số: số nút cảm biến;
năng lượng các nút; vùng khảo sát
Năng lượng ban đầu của 0,5J
SN
Kích thước gói tin 4000 bits
Tính số cụm định phân chia theo công thức
(1) Năng lượng truyền 50nJ/bit
Năng lượng nhận 50nJ/bit
Số cụm > 1 Số vòng tối đa ( rmax ) 3500
Sai
Đúng
Với những đánh giá như vậy, giải pháp cải tiến phương
Phân cụm theo thuật toán K-means
pháp LEACH và kết quả phân vùng được biểu diễn
Các nút truyền dữ liệu
trực tiếp về BS trên hình 3b đã minh họa cho hiệu quả của phương
Chọn CH cho mỗi cụm sao cho CH là nút pháp đề xuất của chúng tôi. Trên hình này biểu diễn
trung tâm có tổng quãng đường truyền dẫn
đến các nút trong cụm là nhỏ nhất phân chia cụm trong mạng WSN theo thuật toán K-
Means, các SN có dấu là các nút được chọn làm CH
Kết thúc của cụm.
Kết quả biểu diễn trên đồ thị hình 4 minh họa số SN
Hình 2: Lưu đồ thuật toán New-LEACH còn sống theo số vòng hoạt động của giao thức
LEACH truyền thống, giao thức I-ELEACH và giao
III. MÔ PHỎNG VÀ THẢO LUẬN thức NEW-LEACH do nhóm tác giả đề xuất. Theo kết
Để đánh giá hiệu quả của New-LEACH so với các quả này, nếu xét tại số lượng vòng dao động trong
phương pháp truyền thống bài báo này xây dựng các khoảng 1000, hiệu quả của các phương pháp gần như
tham số như diện tích vùng mô phỏng, tống số SN sử tương đương nhau.
dụng . Tham số diện tích vùng mô phỏng được lựa
chọn giá trị 100 m x 100 m để đảm bảo không mất tính
tổng quát và có thể thực hiện được. Số SN được lựa
chọn là 100, đảm báo không quá dày đặc trên diện tích
ISBN 978-604-80-5958-3 434
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
100
90
80
70
60
50
40
30
20
10
0
0 20 40 60 80 100
a)
100
90
80 Hình 5: Thời gian nút đầu tiên, một nửa và nút cuối cùng
70 chết.
60 0.6
LEACH
50 New - LEACH
I-LEACH
0.5
40
0.4
N¨ng l-îng tiªu hao trung b×nh
30
20 0.3
10
0.2
0
0 10 20 30 40 50 60 70 80 90 100
b) 0.1
Hình 3: Phân cụm và chọn CH: a)LEACH; b)New- 0
LEACH
Tuy nhiên, khi số lượng vòng nằm trong khoảng từ -0.1
0 500 1000 1500 2000 2500 3000 3500
Sè vßng(r)
1000 đến 1500 thì hiệu quả của các phương pháp đã có
sự chênh lệch rõ rệt. Tại khoảng này, số SN của Hình 6: Năng lượng tiêu hao trung bình của mạng.
phương pháp LEACH còn sống qua mỗi vòng giảm đi
nhanh chóng và có thể tiến đến 0 khi số vòng đạt 1500. đến 43% so với LEACH và tăng 27% so với I-
Điều này là gây ra sự kém hiệu quả của LEACH so với LEACH.So sánh năng lượng còn lại của mạng WSN
các phương pháp còn lại. Với phương pháp I –LEACH khi sử dụng thuật toán New-LEACH, LEACH và I-
thì hiệu quả tốt hơn so với LEACH tuy nhiên khi số LEACH cho kết quả biểu diễn trong hình 6. Từ kết quả
vòng hoạt động tăng lên lớn hơn 1500 thì I – LEACH mô phỏng cho thấy việc phân phối năng lượng và cân
bằng tải được thực hiện đồng thời, sử dụng các chiến
lại giảm gần theo quỹ đạo đường tuyến tính. Kết quả
lược quản lý lựa chọn nút CH và các thành viên trong
này cho thấy, SN còn sống của New-LEACH tăng 54% các cụm. Nói cách khác, tổng năng lượng tiêu thụ trong
so với LEACH và tăng 3,4% so với I-LEACH. mạng sử dụng New-LEACH được quản lý tốt hơn so
Trong hình 5 các tham số đánh giá là thời gian nút đầu với LEACH và I-LEACH.
tiên chết, FND (First Node Death - FND), một nửa nút
chết, MND (Mid Node Death- MND) và nút cuối cùng
chết, LND (Last Node Death - LND). Kết quả chỉ ra IV. KẾT LUẬN
rằng, trong một số trường hợp, thời gian FND của Tiết kiệm và sử dụng hiệu quả năng lượng tiêu thụ
New-LEACH sớm hơn so LEACH và I-LEACH và do cũng như cân bằng tải là những thách thức đáng kể của
đó thời lượng ổn định mạng bị giảm đi một phần. Tuy các thuật toán định tuyến trong WSN. Trong bài báo
nhiên, mức tiêu thụ năng lượng giảm so với thuật toán này, một thuật toán định tuyến hiệu quả năng lượng
LEACH và I-LEACH dẫn đến tỉ lệ chết các SN của cho WSN đã được đề xuất trong đó xem xét việc phân
New-LEACH giảm. đáng kể và tuổi thọ mạng tăng lên cụm lựa chọn các nút CH. Bằng cách sử dụng thuật
toán K-means để phân cụm, lựa chọn các SN có
100
90
LEACH khoảng cách tương đối nhỏ để trở thành nút CH dẫn
đến năng lượng tiêu thụ trung bình WSN giảm; tuổi thọ
New - LEACH
I-LEACH
80
70 của WSN được kéo dài so với các thuật toán LEACH,
60 I- LEACH. Kết quả mô phỏng cũng chỉ ra thuật toán
Sè nót sèng
50
New-LEACH có tính linh hoạt trong việc lựa chọn CH
cũng như phân cụm.
40
30
20
10
0
0 500 1000 1500 2000 2500 3000 3500
Sè vßng (r)
Hình 4: Số lượng nút còn sống theo số vòng hoạt
động.
ISBN 978-604-80-5958-3 435
- Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)
TÀI LIỆU THAM KHẢO 12th International Conference on Communication Technology, 648-
651, 2010.
[1] D. Zhang, G. Li, K. Zheng, X. Ming, Z. H. Pan, ” An
energy-balanced routing method based on forward-aware factor for [7] Z. Beiranvand, A. Patooghy, M. Fazeli, “ I-LEACH: An
wireless sensor networks” IEEE Transactions on Industrial efficient routing algorithm to improve performance & to reduce
Informatics, 10(1), 766–773, 2014. energy consumption in wireless sensor networks”, The 5th
Conference on Information and Knowledge Technology, 13–18,
[2] T. Ma, M. Hempel, D. Peng, H. Sharif, “A survey of 2013.
energy-efficient compression and communication techniques for
multimedia in resource constrained systems”, IEEE Communication [8] P. Saheb, ” Improved LEACH Protocol Based on K-
Survey Tutorials, 15(3), 963–972, 2013. Means Clustering Algorithm for Wireless Sensor Networ”,.
International Journal of Electronics & Communication Technology,
[3] C. Donati-Martin, “Stochastic integration with respect to 8, 28–32,2017.
q Brownian motion. Probab”. Theory Relat. Fields, 125(1), 77–95,
2003. [9] W. B. Heinzelman, A. P. Chandrakasan, H.
Balakrishnan, “An application-specific protocol architecture for
[4] C. H. Lin, M. J. Tsai, “A comment on „HEED: A Hybrid, wireless microsensor networks”, IEEE Transactions Wireless.
Energy-Efficient, Distributed clustering approach for ad hoc sensor Communication, 1(14), 660–670,2002.
networks”, IEEE Transactions on Mobile Computing, 5(10), 1471–
1472, 2006. [10] J. B. MacQueen, “ Some Methods for classification and
Analysis of Multivariate Observations”, Proc. 5th Berkeley
[5] Arati Manjeshwar, Dharma P. Agrawal, “A Routing Symposium on Mathematical Statistics and Probability, 281–297,
Protocol for Enhanced Efficiency in Wireless Sensor Networks”, 1967.
Proc. IPDPS 2001 Workshop.
[6] Z. Xin, X. Junyuan, M. Zhengkun, “A Distance-based
Clustering Routing Protocol in Wireless Sensor Networks”, IEEE
ISBN 978-604-80-5958-3 436
nguon tai.lieu . vn
