zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» 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

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

Báo xấu

80
lượt xem 7
download

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

Bài viết trình bày việc đề xuất cải tiến giao thức LEACH bằng cách kết hợp sử dụng thuật toán K-means để phân cụm và lựa chọn các nút làm CH sao cho tổ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 tiêu thụ năng lượng trung bình trong mạng giảm và kéo dài tuổi thọ của mạng.

Chủ đề:

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

Lưu

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

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:  , nG 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  , nG 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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.