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 ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 190 
mạng cảm biến như Hình 2. Nếu một điểm trong ô lưới Voronoi không được phủ sóng 
bởi điểm cảm biến của ô lưới đó thì nó cũng không được phủ sóng bởi bất cứ điểm cảm 
biến nào trong mạng và kết quả sinh ra các hố phủ sóng trong không gian cần phủ sóng 
của mạng cảm biến không dây. 
Hình 2. Các hố phủ sóng hình thành khi 
xây dựng sơ đồ Voronoi 
Hình 3. Chiến lược VOR đẩy các cảm 
biến để đạt độ phủ sóng tối đa 
Nếu dựa vào tính di chuyển được của các cảm biến thì việc di chuyển này có khả 
năng phủ sóng được các hố phủ sóng đã nêu ở trên. Ba chiến lược di chuyển cảm biến 
trong sơ đồ Voronoi được đề xuất [11] đó là: Vector-Based (VEC), MiniMax, và 
Voronoi-Based (VOR). Tất cả các chiến lược này đều cải thiện tăng khả năng vùng phủ 
sóng của toàn mạng cảm biến bằng cách lặp đi lặp lại việc di chuyển các cảm biến trong 
mạng. 
Thuật toán VOR là một chiến lược đẩy các cảm biến nội bộ trong ô lưới Voronoi 
về hướng có đỉnh xa nhất làm tăng khả năng phủ sóng của các cảm biến như Hình 3. 
Thuật toán VOR là thuật toán tham nên có thể làm giảm kích thước hố phủ sóng lớn 
nhất, nhưng sau mỗi lần di chuyển các cảm biến thì một hố phủ sóng mới có thể được 
tạo ra, mà hố phủ sóng này có thể bao phủ bởi việc di chuyển cảm biến ngược lại trong 
vòng lặp tiếp theo. Để khắc phục việc một cảm biến mới được di chuyển đi sau đó lại di 
chuyển trở lại trong lần lặp kế tiếp như đã thảo luận thì một điều kiện được bổ sung vào 
thuật toán là không cho phép bất cứ một cảm biến nào di chuyển ngược lại ngay lần lặp 
kế tiếp tức là trước khi một cảm biến di chuyển thuật toán kiểm tra quỹ đạo di chuyển 
của cảm biến có di chuyển trái ngược lại với lần lặp trước đó không? Nếu có thì việc di 
191 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 
chuyển này sẽ dừng lại tại lần lặp này và hố phủ sóng đang đề cập sẽ được phủ sóng bởi 
cảm biến lân cận đó. Mặt khác việc di chuyển các cảm biến làm biến đổi hình dạng các 
ô lưới Voronoi mà có thể làm giảm diện tích phủ sóng của mạng cảm biến. Do đó thuật 
toán cần thêm điều kiện là khi di chuyển cảm biến đến các điểm mục tiêu thì cần phải 
đảm bảo làm tăng kích thước vùng phủ sóng trong từng ô lưới Voronoi và trong trường 
hợp điều kiện này không được đảm bảo thì vị trí mới của cảm biến chính là trung điểm 
giữa vị trí hiện hành và điểm mục tiên cần chuyển đến. 
3. 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 
3.1. Mô hình mạng cảm biến trong môi trường 3D 
Mô hình hóa một mạng cảm biến không dây trong môi trường 3D với các vật 
cản trong môi trường như sau: 
 Gọi T là một địa hình DEM (Digital Elevation Model) là một ma trận mà 
các giá trị đại diện cho độ cao của điểm ô lưới. 
o cellsize : kích thước ô lưới 
o nrows, ncols : số hàng và số cột của ma trận 
 NsssWSN ,...,, 21 là một mạng cảm biến gồm N các cảm biến sj, 
 Nj ,1  , là một bộ gồm các thành phần : 
 jjjjj rhyxs ,,, ,  Nj ,1  (1) 
 Trong đó: 
o jj yx , là tọa độ của js trong Oxy. 
o jh là độ cao của js tại jj yx , 
o jr là bán kính của cảm biến js 
 HrrrR ,...,, 21 là tập các vật cản trong mô trường 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 192 
Trong đó: 
 fififisisisii hyxhyxr ,,,,, , ],...2,1[ Ni  (2) 
Mỗi vật cản được đại diện bởi tọa độ góc trên bên trái và góc dưới bên phải của một 
vùng 
3.2. Phương pháp Line-Of-Sight (LoS) 
Trong mô hình mạng cảm biến được đề xuất các cảm biến có khả năng di 
chuyển trong các ô lưới Voronoi, hơn nữa trong môi trường cũng giả định có các 
chướng ngại vật. Vậy để tránh được việc di chuyển của cảm biến vào các chương ngại 
vật thì trước tiên thuật toán phải kiểm tra giữa vị trí cảm biến với một đỉnh nào đó của ô 
lưới Voronoi có chướng ngại vật hay không? Phương pháp được áp dụng là LoS. 
Các bước chính thực hiện của phương pháp LoS là trước tiên kẻ một đường 
thẳng giữa vị trí cảm biến đến một đỉnh của ô lưới Voronoi cần kiểm tra xem ở giữa có 
chướng ngại vật không, tiếp đến là chia đoạn thẳng này thành nhiều đoạn mỗi đoạn có 
kích thước bằng kích thước cellsize của ô lưới ma trận địa hình, các điểm chia này được 
lập thành một danh sách. Ứng với mỗi điểm chia trong danh sách này được so sánh với 
độ cao trong địa hình. Trong bước này có thể khẳng định giữa hai điểm này có chướng 
ngại vật nếu như giá trị độ cao địa hình nằm ở phía trên đường thẳng như Hình 4. 
Hình 4. Phương pháp LoS 
(a) Giữa hai điểm không cho chướng ngại vật 
(b) Giữa hai điểm có chướng ngại vật 
3.3. Thuật toán Voronoi cải tiến trong môi trường 3D 
Thuật toán VOR có khả năng triển khai mạng cảm biến trong khu vực mục tiêu, 
tuy nhiên nó được cài đặt cho môi trường 2D bằng phẳng và không xem xét bất kỳ một 
193 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 
rằng buộc nào về môi trường chẳng hạn như có các vật cản. Chúng tôi cải tiến thuật 
toán VOR có thể áp dụng triển khai cảm biến địa hình cho một mạng cảm biến không 
dây (WSN) trong môi trường 3D có các vật cản như định nghĩa trong công thức (2), 
trong ứng dụng này áp dụng phương pháp LoS để xác định các vật cản khi cần di 
chuyển các cảm biến. Thuật toán đề xuất chỉ những cảm biến mà có đỉnh xa nhất không 
được phủ sóng thì sẽ bị di chuyển: Nếu các đỉnh của ô lưới Voronoi đã được phủ sóng 
bởi cảm biến thì cảm biến này không được di chuyển như Hình 5b, ngược lại, cảm biến 
sẽ di chuyển về hướng đỉnh xa nhất, trong trường hợp đỉnh xa nhất bị chắn bởi chướng 
ngại vật, chiều dài di chuyển của cảm biến được tính toán là khoảng cách từ cảm biến 
đến chướng ngại vật như Hình 5c. 
Hình 5. Thuật toán VOR cải tiến 
(a) Cảm biến di chuyển về hướng đỉnh xa nhất mà chướng ngại vật không được xem xét. 
(b) Tất cả các đỉnh của Voronoi (trừ V1) được phủ sóng bởi cảm biến, nên cảm biến sẽ không được di 
chuyển. 
(c) Cảm biến di chuyển về hướng đỉnh xa nhất với khoảng cách giữa cảm biến và chướng ngại vật. 
(d) Cảm biến di chuyển về hướng của đỉnh xa thứ hai vì không thể di chuyển tới đỉnh xa thứ nhất do 
chướng ngại vật. 
Nếu cảm biến không thể di chuyển về hướng đỉnh xa nhất vì chướng ngại vật thì 
đỉnh xa thứ hai được chọn để cảm biến di chuyển về hướng của đỉnh này như Hình 5d. 
4. KẾT QUẢ THỰC NGHIỆM 
Thuật toán VOR cải tiến được áp dụng trong môi trường 3D như Hình 6 là một 
khu vực bằng phẳng chứa một tập các tòa nhà hình hộp. Mạng cảm biến bao gồm các 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 194 
cảm biến hình cầu và có bán kính phủ sóng 30m được đề xuất. Ban đầu các cảm biến 
được triển khai với phân bố ngẫu nhiên trong không gian 3D có kích thước 200m x 
200m. 
Hình 6. Môi trường 3D với các tòa nhà hình khối 
Để đánh giá được sự ổn định của phương pháp đề xuất cả hai thuật toán VOR và 
VOR cải tiến được cài đặt và chạy thử nghiệm. Với số lần chạy là 30, Bảng 1 cho biết tỉ 
lệ phần trăm phủ sóng của vùng mục tiêu là giá trị lớn nhất, nhỏ nhất và trung bình 
trong các lần chạy thử nghiệm. Kết quả trong phương pháp được đề xuất tốt hơn. 
Bảng 1. Kết quả thử nghiệm các thuật toán 
 Thuật toán VOR VOR cải tiến 
Tỉ lệ phủ sóng Lớn nhất 59.1811 77.7044 
 Nhỏ nhất 39.9006 72.1707 
 Trung bình 56.4122 75.4123 
5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 
Bài viết đề xuất một phần cải tiến của thuật toán VOR để được áp dụng trong 
môi trường 3D, điều này rất có ý nghĩa vì môi trường 3D là rất thực tế với các yếu môi 
trường đặc biệt trong môi trường luôn luôn tồn tại các chướng ngại vật. Trong ứng dụng 
cũng áp dụng kỹ thuật phân tích tầm nhìn LoS để phát hiện ra chướng ngại vật giữa cảm 
biến và các điểm mục tiêu cần xem xét. Kết quả thực hiện cho thuật toán VOR cải tiến 
cũng cho kết quả phủ sóng của cảm biến không dây một cách đáng kể. Tuy nhiên để 
khẳng định chắc chắn thuật toán VOR cải tiến đáp ứng tốt cho tất cả các địa hình trong 
môi trường 3D cần phải thực nghiệm trên nhiều địa hình phức tạp khác nhau mà tồn tại 
các chướng ngai vật là sông hồ, và với kích thước địa hình lớn hơn. 
195 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 
TÀI LIỆU THAM KHẢO 
[1] Yick, J., Mukherjee, B., Ghosal, D., “Wireless sensor network survey,” Computer 
networks, vol. 52, no. 12, 2008, pp. 2292-2330. (2008) 
[2] Mulligan, R., Ammari, H.M., “Coverage in Wireless Sensor Networks”. A Survey. 
Journal of Network Protocols and Algorithms 2(2), 27–53 (2010) 
[3] Ravelomanana, V., “Extremal Properties of Three-Dimensional Sensor Networks 
with Applications”. IEEE Transactions on Mobile Computing 3(3), 246–257 (2004). 
[4] Huang, C., Tseng, Y., Lo, L., “The Coverage Problem in Three- Dimensional 
Wireless Sensor Networks”. In: Proceedings of Global Telecommunications 
Conference (GLOBECOM 2004), November 29-December 3, pp. 3182–3186. IEEE 
(2004). 
 [5] Hossain, A., Biswas, P.K., Chakrabarti, S. Sensing Models and Its Impact on 
Network Coverage in Wireless Sensor Network, Industrial and Information Systems, 
2008. ICIIS 2008. IEEE Region 10 and the Third international Conference on. IEEE, 
Kharagpur, pp. 1 - 5.(2008) 
[6] Ghosh, A., Estimating Coverage Holes and Enhancing Coverage in Mixed Sensor 
Networks, Local Computer Networks, 2004. 29th Annual IEEE International 
Conference on, pp. 68 - 76. (2004) 
[7] Wang, Y., Cao, G., Barrier Coverage in Camera Sensor Networks. MobiHoc '11 
Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc 
Networking and Computing. (2011). 
[8] Akbarzadeh, V., Hung- Ren Ko, A., Gagn'e, C., Parizeau, M., Topography-Aware 
Sensor Deployment Optimization with CMA-ES, Parallel Problem Solving from 
Nature, PPSN XI. Springer, pp. 141-150. (2010). 
[9] Argany, M., Mostafavi, M.A., Karimipour, F., Gagné, C., A gis based wireless 
sensor network coverage estimation and optimization: A voronoi ap-proach. 
Transacton on Computational Sciences Journal 14, 151-172. (2011). 
[10] Argany, M., Mostafavi, M.A., Karimipour, F., Voronoi-based Approaches for 
Geosensor Networks Coverage Determination and Optimisation: A Survey, 
Proceedings of the 7th International Symposium on Voronoi Diagrams in Science 
and Engineering (ISVD 2010), Quebec, Canada, pp. 115-123. (2010). 
[11] Karimipour, F., Argany, M., Mostafavi, M.A.,. Spatial coverage estimation and 
optimization in geosensor networks deployment, Wireless sensor networks: From 
theory to applications. CRC Press. (2013) 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] 196 
OPTIMIZATION FOR THE COVERAGE PROBLEM OF 
WIRELESS SENSOR NETWORK WITH VORONOI ALGORITHM 
IN 3D ENVIRONMENTS 
Dang Thanh Haia*, Le Trong Vinhb 
aThe Faculty of Information Technology, Dalat University, Lamdong, Vietnam 
bVNU University of Science, Hanoi, Vietnam 
*Corresponding author: haidt@dlu.edu.vn 
Article history 
Received: January 04th, 2016 
Accepted: March 16th, 2016 
Abstract 
In recent years, wireless sensor networks (WSN) has appeared interesting to many authors. 
Some methods to optimize the coverage of wireless sensor networks is proposed to improve 
the efficiency of deploying sensor networks, thus increasing the coverage; howerver, most 
are built on 2D model, which are often hard to implement in reality. In this paper we 
extend Voronoi algorithm to deploy sensors in 3D environments where there are obstacles 
which affect the ability of coverage of wireless sensor networks. 
Keywords: Coverage; Voronoi; Obstacles; Wireless Sensor Networks.