Tối ưu hóa vùng phủ sóng của mạng cảm biến không dây bằng thuật toán Voronoi trong môi trường 3D

187 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT Tập 6, Số 2, 2016 187–196 
TỐI ƯU HÓA VÙNG PHỦ SÓNG CỦA MẠNG CẢM BIẾN KHÔNG 
DÂY BẰNG THUẬT TOÁN VORONOI TRONG MÔI TRƯỜNG 3D 
Đặng Thanh Hảia*, Lê Trọng Vĩnhb 
aKhoa Công nghệ Thông Tin, Trường Đại học Đà Lạt, Lâm Đồng, Việt Nam 
bTrường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Hà Nội, Việt Nam 
Nhận ngày 04 tháng 01 năm 2016 | Chấp nhận đăng ngày 16 tháng 03 năm 2016 
Tóm tắt 
Trong những năm gần đây mạng cảm biến không dây (WSN) được nhiều nhóm tác giả quan 
tâm. Một số phương pháp tối ưu hóa vùng phủ sóng của mạng cảm biến không dây được đề 
xuất để nâng cao hiệu quả triển khai mạng cảm biến do đó làm tăng độ phủ sóng, nhưng 
hầu hết được xây dựng trên mô hình 2D, mà thường xa rời với thực tế. Trong bài báo này 
chúng tôi mở rộng thuật toán Voronoi để triển khai các cảm biến trong môi trường 3D mà 
ở đó có nhiều vật cản làm ảnh hưởng đến khả năng phủ sóng của mạng cảm biến không 
dây. 
Từ khóa: 3D; Mạng cảm biến không dây (WSN); Phủ sóng; Voronoi; Vật cản. 
1. GIỚI THIỆU 
Mạng cảm biến không dây (WSN) bao gồm một số các điểm cảm biến, các điểm 
cảm biến này có khả năng cảm nhận môi trường, thu thập dữ liệu, xử lý dữ liệu và giao 
tiếp với nhau. Dữ liệu sau đó được chuyển về trung tâm xử lý, phân tích tạo ra các thông 
tin hữu ích hỗ trợ ra quyết định của các chương trình ứng dụng khác nhau [1]. Hiện nay 
mạng cảm biến không dây được áp dụng trong nhiều lĩnh vực khác nhau: giám sát môi 
trường, cảnh báo cháy rừng, cảnh báo có sự tấn công, giám sát trong các địa hình phức 
tạp như trong lòng đại dương, hang động, các đường hầm trong mỏ, Tùy thuộc vào 
loại ứng dụng mạng, cũng như bản chất và các điều kiện môi trường có ảnh hưởng đến 
hiệu quả và chi phí của mạng cảm biến không dây thì các kỹ thuật và phương pháp khác 
nhau được sử dụng để phát hiện và theo dõi các hiện tượng trong môi trường một cách 
hiệu quả. 
* Tác giả liên hệ: Email: haidt@dlu.edu.vn 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 188 
Việc triển khai mạng cảm biến cần đảm bảo tối đa vùng phủ sóng nghĩa là phạm 
vi cần quan sát. Phạm vi phủ sóng đã được nghiên cứu rất kỹ trong môi trường 2D 
[1][2]. Gần đây, vấn đề này đã được mở rộng sang môi trường 3D vốn gần gũi với thực 
tế hơn cũng đã được nhiều nhà nghiên cứu quan tâm [3][4]. Tuy nhiên đây cũng là bài 
toán phức tạp vì trong môi trường thực tế tồn tại rất nhiều vấn đề ví dụ như có tòa nhà là 
chướng ngại vật ngăn cản việc phủ sóng của các cảm biến, có sông hồ mà ở đó không 
thể đặt được các cảm biến. Vậy mục tiêu đặt ra là tìm kiếm một giải pháp triển khai các 
cảm biến trong môi trường 3D đạt hiểu quả tức là các cảm biến không được đặt vào 
vùng cấm đồng thời phải đảm bảo khả năng phủ sóng của toàn mạng cảm biến hiệu quả 
nhất. 
Một thuật toán Voronoi-Base được đề xuất triển khai trong môi trường 2D rất 
hiệu quả nhờ vào tính di chuyển được của các cảm biến [11]. Trong bài viết này chúng 
tôi đề xuất một cải tiến thuật toán Voronoi-Base để triển khai được các biến trong môi 
trường 3D với sự tồn tại của các chướng ngại vật mà vẫn đảm bảo được khả năng phủ 
sóng của toàn mạng cảm biến một cách hiệu quả. Phần còn lại của bài viết được tổ chức 
như sau. Phần 2 trình bày các phương pháp triển khai mạng cảm biến không dây. Phần 3 
trình bày mô hình mạng cảm biến và thuật toán Voronoi cải tiến trong môi trường 3D. 
Kết quả thực nghiệm sẽ được trình bày trong phần 4. Cuối cùng, kết luận và hướng phát 
triển trong tương lai được đưa ra trong phần 5. 
2. CÁC PHƯƠNG PHÁP TRIỂN KHAI MẠNG CẢM BIẾN 
2.1. Mô hình phủ sóng của mạng cảm biến trong không gian 2D và 3D 
Một mạng cảm biến được xem là có hiệu quả hay không, một trong các yếu 
được xem xét đó chính là khả năng thu thập thông tin và truyền dẫn dữ liệu về nút trung 
tâm để xử lý. Việc thu thập thông tin của mạng cảm biến phụ thuộc vào phạm vi phủ 
sóng cảm biến của toàn mạng đối với vùng mục tiêu và đặc biệt trong môi trường thực 
tế 3D có các vật cản làm ảnh hưởng đến phạm vi phủ sóng của mạng cảm biến. 
Một mạng cảm biến không dây là một tập hợp các điểm cảm biến trong không 
gian Euclide, và mỗi điểm cảm biến có một phạm vi cảm nhận thông tin như Hình 1a. 
Mục tiêu là thiết kế phương án triển khai các điểm cảm biến trong không gian phủ sóng 
189 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 
để đảm bảo vùng phủ sóng được nhiều nhất hay giảm thiểu không gian hố phủ sóng [5]. 
Hố phủ sóng là những vùng trong không gian cần phủ sóng mà không được bao phủ bởi 
bất kỳ một cảm biến nào của mạng cảm biến. 
 (a) (b) 
Hình 1. Mô hình phủ sóng của cảm biến trong 2D và 3D 
Các phương pháp tính toán khả năng phủ sóng của mạng cảm biến đã được đề 
xuất [6][7]. Đặc biệt đã có đã có những nghiên cứu mở rộng mô hình tính toán khả năng 
phủ sóng trong môi trường 3D có sử dụng khái niệm khả năng tầm nhìn giữa cảm biến 
và vùng cần phủ sóng (line of sights) như Hình 1b.[8][9]. 
2.2. Các phương pháp tối ưu triển khai mạng cảm biến trong 2D 
Một số phương pháp tối ưu triển khai mạng cảm biến được đề xuất là phát hiện 
ra và làm giảm các hố phủ sóng do đó nó sẽ làm tăng vùng phủ sóng của các cảm biến 
trong mạng cảm biến không dây. Một trong các phương pháp tối ưu tăng cường khả 
năng phủ sóng của mạng cảm biến được tiếp cận dựa trên khái niệm về tính di động của 
các cảm biến. Các phương pháp này sử dụng cấu trúc hình học để phát hiện ra các hố 
phủ sóng rồi di chuyển các cảm biến để làm tăng vùng phủ sóng của toàn mạng, sơ đồ 
Voronoi và Delaunay Triangulation được ứng dụng vào phương pháp này và mang lại 
kết quả tốt [10][11]. 
Trong khái niệm sơ đồ Voronoi, ứng với mỗi điểm cảm biến sẽ xác định được 
một ô lưới Voronoi. Tất cả các điểm trong ô lưới của Voronoi được xem gần nhất với 
điểm cảm biến trong ô đó. Như vậy sau khi xây dựng xong sơ đồ Voronoi của tất cả 
cảm biến của mạng cảm biến không dây thì sẽ xác định được vùng phủ sóng của toàn 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ