Tìm kiếm tài liệu miễn phí

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

Bài viết 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 trình bà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ế,... Mời các bạn cùng tham khảo.



Đánh giá tài liệu

0 Bạn chưa đánh giá, hãy đánh giá cho tài liệu này


  • 5 - Rất hữu ích 0

  • 4 - Tốt 0

  • 3 - Trung bình 0

  • 2 - Tạm chấp nhận 0

  • 1 - Không hữu ích 0

Mô tả

TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT Tập 6, Số 2, 2016 187–196

187

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
a

b

Khoa Công nghệ Thông Tin, Trường Đại học Đà Lạt, Lâm Đồng, Việt Nam
Trườ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

TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN]

191

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

WSN  s 1 , s 2 ,..., s N  là một mạng cảm biến gồm N các cảm biến sj,
 j  1, N  ,

sj 

là một bộ gồm các thành phần :

x

j



, y j , h j , r j ,  j  1, N 

Trong đó:



o

x

o

hj là độ cao của sj tại x j , y j 

o

r j là bán kính của cảm biến

j

,yj

 là tọa độ của sj trong Oxy.

sj

R  r1 , r2 ,..., rH  là tập các vật cản trong mô trường

(1)

Tài liệu cùng danh mục Quản trị mạng

Tổng quan về ipv6 - part 1

Đinh dạng phần Header của các gói tin theo dạng mới Các gói tin sử dụng Ipv6 (Ipv6 Packet) có cấu trúc phần Header thay đổi nhằm tăng cương tính hiệu quả sử dụng thông qua việc dời các vùng (field) thông tin không cần thiết (non-essensial) và tùy chọn (Optional) vào vùng mở rộng (Extension Header Field)


kỹ thuật trong mạng LAN

ĐÁNH GIÁ HIỆU QUẢ TRUYỀN VIDEO THỜI GIAN THỰC BẰNG LƯỢC ĐỒ SPRS TRONG MẠNG ETHERNET TỐC ĐỘ CAO Phạm Mạnh Hà Hệ thống thông tin thời gian thực là hệ thống trong đó các quá trình vật lý diễn ra chính xác đồng thời theo trình tự thời gian. Hai yêu cầu chính của bất cứ ứng dụng thời gian thực nào


Secure Socket Layer: Giải pháp kỹ thuật hỗ trợ thương mại điện tử?

Secure Socket Layer: Giải pháp kỹ thuật hỗ trợ thương mại điện tử? SSL là giao thức đa mục đích được thiết kế để tạo ra các giao tiếp giữa hai chương trình ứng dụng trên một cổng định trước (socket 443) nhằm mã hoá toàn bộ thông tin đi/đến, được sử dụng trong giao dịch điện tử như truyền số liệu thẻ tín dụng, mật khẩu, số bí mật cá nhân (PIN) trên Internet. Mở đầu Trong các giao dịch điện tử trên mạng và trong các giao dịch thanh toán trực tuyến, thông tin/dữ liệu trên môi trường...


Kỹ thuật mạng máy tính part 9

Tham khảo tài liệu 'kỹ thuật mạng máy tính part 9', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả


Bài giảng môn học thiết bị mạng-Chương 1

Chương 1:  Định nghĩa mạng máy tính Mạng máy tính là một nhóm các máy tính, thiết bị ngoại vi được nối kết với nhau thông qua các phương tiện truyền dẫn như cáp, sóng điện từ, tia hồng ngoại... giúp cho các thiết bị này có thể trao đổi dữ liệu với nhau một cách dễ dàng.


Bài giảng Mạng máy tính: Bài 14 - Trường TCN Tôn Đức Thắng

Bài giảng Mạng máy tính (Trường TCN Tôn Đức Thắng - Bình Phước) - Bài 14. Mục đích môn học: Hiểu biết về mạng máy tính, Các thiết bị dùng kết nối mạng, Biết cách thiết kế hệ thống mạng LAN, INTERNET, Thiết lập mạng Microsoft Windows 2003 Server, Quản lý tài nguyên trên Microsoft Windows 2003 Server, Biết cách sử dụng cũng như cài đặt các dịch vụ mạng, Quản trị Windows 2003 server hiệu quả.


Quá trình hình thành quy trình thiết kế máy thu phát ký tự 32 bit p4

ơ đồ khối đơn vị xử lý dữ liệu. 4.2.2. Đơn vị xử lý dử liệu. Có nhiều đơn vị xử lý dử liệu khá phổ dụng trong các hệ vi xử lý 8 bit như: Vi xử lý 8085A (Intel) Vi xử lý Z80 (Zilog) Vi xử lý MC 6800 (Motorola) Các họ vi điều khiển của Intel (8031, 8051, 8951, 8751P) Linh kiện vi xử lý được dùng trong hệ thống này là vi xử lý 8085A, thực chất linh kiện này khá phổ dùng trên thị trường mà người thực hiện đề tài này...


Chia sẻ thư mục trong Dropbox

Dropbox hiện đang là 1 trong những ứng dụng chia sẻ, đồng bộ dữ liệu trực tuyến phổ biến nhất hiện nay. Trong bài viết sau, Quản Trị Mạng sẽ hướng dẫn các bạn cách thiết lập và chia sẻ thư mục bất kỳ của Dropbox với những người sử dụng khác.


Mô Hình Tham Chiếu OSI Toàn Tập: Lớp 6 - Presentation

Trong 5 bài trc, tôi đã viết về năm lớp thấp nhất của mô hình tham chiếu OSI. Trong bài này, chúng ta sẽ cùng nhau tìm hiểu lớp thứ 6. Lớp 6, còn đc gọi là lớp Presentation, là lớp đầu tiên thực hiện quá trình truyền dữ liệu xuyên qua 1 mạng ở mức độ trừu tượng hơn so với chỉ những bit 0 và 1


The Practice of System and Network Administration Second Edition phần 4

, tính chính xác dữ dội, hoặc bởi nhóm SA, có trách nhiệm cung cấp một nền tảng cơ bản mà người dùng có thể tùy chỉnh. Trong trường hợp trước đây, người ta có thể tưởng tượng một văn phòng Telesales nơi mà các nhà khai thác nhìn thấy một tập hợp các ứng dụng. Ở đây, công việc SA với


Tài liệu mới download

Từ khóa được quan tâm

Có thể bạn quan tâm

Fundamentals of Project Management
  • 24/01/2013
  • 87.940
  • 736
Quản lý kết nối Internet
  • 26/10/2009
  • 35.360
  • 747
strat_bk3
  • 27/05/2009
  • 38.587
  • 227

Bộ sưu tập

Danh mục tài liệu