ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------------------

Đặng Thanh Hải

NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁN
TỐI ƯU HÓA VÙNG PHỦ SÓNG VÀ NĂNG LƯỢNG
CỦA MẠNG CẢM BIẾN KHÔNG DÂY
TRONG MÔI TRƯỜNG 3 CHIỀU

LUẬN ÁN TIẾN SĨ TOÁN HỌC

Hà Nội, 2017


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------------------

Đặng Thanh Hải

NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁN
TỐI ƯU HÓA VÙNG PHỦ SÓNG VÀ NĂNG LƯỢNG
CỦA MẠNG CẢM BIẾN KHÔNG DÂY
TRONG MÔI TRƯỜNG 3 CHIỀU
Chuyên ngành:
Mã số:

Cơ sở toán cho tin học
62460110

nghiên cứu đƣợc trích dẫn, tham khảo trong luận án này, đây là những kiến thức cơ
sở để Nghiên cứu sinh phát triển và hoàn thiện các công bố của mình.
Nghiên cứu sinh xin chân thành cảm ơn Ban giám hiệu, lãnh đạo Khoa ToánCơ- Tin, các thầy cô giảng viên, đồng nghiệp Bộ môn Tin học, Trung tâm tính toán
hiện năng cao, trƣờng Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã
tạo điều kiện thuận lợi nhất để nghiên cứu sinh hoàn thành chƣơng trình học tập và
thực hiện luận án nghiên cứu khoa học của mình.
Nghiên cứu sinh xin chân thành cảm ơn Ban giám hiệu trƣờng Đại học Đà
Lạt, tập thể cán bộ, giảng viên Khoa Công nghệ Thông tin nơi nghiên cứu sinh công
tác và các bạn bè thân thiết đã luôn tạo điều kiện, động viên, khuyến khích để
Nghiên cứu sinh hoàn thành luận án này.
Cuối cùng, nghiên cứu sinh chân thành bày tỏ lòng cảm ơn tới gia đình đã
kiên trì, chia sẻ, động viên nghiên cứu sinh trong suốt quá trình học tập và hoàn
thành luận án này.

Nghiên cứu sinh
Đặng Thanh Hải

ii


MỤC LỤC
0 MỞ ĐẦU ............................................................................................................................ 1
1 CHƢƠNG 1. TỔNG QUAN MẠNG CẢM BIẾN KHÔNG DÂY.................................... 5
1.1. Mạng cảm biến không dây .......................................................................................... 5
1.1.1. Khái niệm............................................................................................................. 5
1.1.2. Cấu trúc nút cảm biến .......................................................................................... 5
1.1.3. Cấu trúc mạng cảm biến không dây .................................................................... 8
1.1.4. Mạng cảm biến trong môi trƣờng 3 chiều ......................................................... 10
1.1.5. Hố mạng và vật cản ........................................................................................... 11
1.2. Hai bài toán quan trọng trong mạng cảm biến không dây và các nghiên cứu

3.3.2. Thuật toán .......................................................................................................... 64
3.4. Thiết kế giải pháp tối ƣu năng lƣợng kết hợp chọn nút CH ..................................... 65
3.4.1. Ý tƣởng .............................................................................................................. 65
3.4.2. Thuật toán .......................................................................................................... 66
3.5. Thiết kế giải pháp tối ƣu năng lƣợng kết hợp cân bằng năng lƣợng ........................ 67
3.5.1. Ý tƣởng .............................................................................................................. 67
3.5.2. Thuật toán FCM- PSOEB .................................................................................. 68
3.6. Kết quả và đánh giá thực nghiệm ............................................................................. 69
3.6.1. Môi trƣờng thực nghiệm .................................................................................... 69
3.6.2. Đánh giá giải pháp tối ƣu năng lƣợng bằng phân cụm mờ ................................ 69
3.6.3. Đánh giá giải pháp tối ƣu năng lƣợng kết hợp lựa chọn nút chủ ....................... 77
3.6.4. Đánh giá giải pháp tối ƣu năng lƣợng kết hợp cân bằng năng lƣợng ................ 82
3.7. Kết luận chƣơng........................................................................................................ 84
4 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ........................................................................ 85
5 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN
ĐẾN LUẬN ÁN .................................................................................................................. 87
6 TÀI LIỆU THAM KHẢO ................................................................................................ 88
7 PHỤ LỤC A ..................................................................................................................... 99

iv


DANH MỤC BẢNG
Bảng 1-1. Phân loại cảm biến theo khả năng cảm nhận ........................................................ 7
Bảng 1-2. Thuật toán LEACH ............................................................................................. 22
Bảng 1-3. Thuật toán LEACH-C ......................................................................................... 24
Bảng 1-4. Thuật toán phân cụm dùng K-Means .................................................................. 26
Bảng 1-5. Thuật toán FCM .................................................................................................. 27
Bảng 2-1. Thuật toán LoS cải tiến ....................................................................................... 37
Bảng 2-2. Thuật toán xác định hố mạng vật lý .................................................................... 39

Hình 1-2. Các thành phần cơ bản của nút cảm biến .............................................................. 7
Hình 1-3. Mô hình cấu trúc hình sao ..................................................................................... 8
Hình 1-4. Mô hình cấu trúc phân cấp .................................................................................... 9
Hình 1-5. Mô hình cấu trúc tập trung .................................................................................. 10
Hình 1-6. Hai mô hình DEM thông dụng ............................................................................ 11
Hình 1-7. Cách xác định vật cản trong địa hình .................................................................. 14
Hình 1-8. Tối ƣu phủ sóng dùng sơ đồ Voronoi .................................................................. 15
Hình 1-9. Tối ƣu phủ sóng dùng hình học mẫu ................................................................... 15
Hình 1-10. Mô hình cảm biến trong môi trƣờng 3 chiều ..................................................... 16
Hình 1-11. Thuật toán Voronoi trong 3 chiều ..................................................................... 17
Hình 1-12. Tăng vùng phủ sóng bằng cách chỉnh hƣớng và góc ........................................ 18
Hình 1-13. Mô hình cảm biến với vật cản ........................................................................... 19
Hình 1-14. Mô hình cảm biến với khái niệm tầm nhìn........................................................ 19
Hình 2-1. Biểu diễn các góc của cảm biến trong môi trƣờng 3 chiều ................................. 31
Hình 2-2. Đại diện hố mạng trong địa hình ......................................................................... 32
Hình 2-3. Xác định hố mạng vật lý...................................................................................... 39
Hình 2-4. Hố mạng vậy lý đƣợc phát hiện trên một số địa hình ......................................... 48
Hình 2-5. Các phân phối điểm lƣới lấy mẫu trong địa hình ................................................ 51
Hình 2-6. Khả năng phủ sóng với các phân bố khác nhau .................................................. 54
Hình 2-7. Khả năng phủ sóng với các bộ tham số khác nhau thuật toán PSO .................... 55
Hình 2-8. Khả năng phủ sóng với tỉ lệ điểm lƣới lấy mẫu khác nhau ................................. 56
Hình 3-1. Lƣu đồ giải pháp xây dựng topo WSN tối ƣu năng lƣợng .................................. 59
Hình 3-2. Phân phối các cảm biến ....................................................................................... 70
Hình 3-3. Năng lƣợng tiêu thụ trung bình với các số cảm biến khác nhau (joule).............. 72
Hình 3-4. Năng lƣợng tiêu thụ trung bình với các phân phối cảm biến khác nhau(joule) .. 74
Hình 3-5. Năng lƣợng tiêu thụ trung bình với số cụm khác nhau(joule)............................. 76
Hình 3-6. Tỉ lệ phần trăm CH kết nối tới BS với số cảm biến khác nhau ........................... 78
Hình 3-7. Tỉ lệ phần trăm non-CH kết nối tới CH với số cảm biến khác nhau .................. 78
Hình 3-8. Tỉ lệ phần trăm CH kết nối tới BS với các phân phối khác nhau ........................ 79



AHP

Analytical Hierarchy Process

Quá trình phân tích phân cấp

3

APTEEN

Adaptive Periodic Threshold

Giao thức hiệu quả năng

Energy Efficient Sensor Network

lƣợng thích ứng ngƣỡng

Protocol

cảm biến

4

BS

Base Station

Trạm cơ sở

8

DHAC

Distributed Hierarchical

Kỹ thuật phân cụm tích lũy

Agglomerative Clustering

phân cấp phân tán

distributed weight-based energy-

Giao thức phân cụm phân

efficient hierarchical clustering

cấp hiệu quả năng lƣợng

protocol

dựa trên trọng số
Cân bằng năng lƣợng

9

DWEHC

10

Thuật toán phân cụm đa cấp

clustering algorithm

hiệu quả năng lƣợng

14

FCM

Fuzzy C-Means

Phân cụm mờ

15

GPS

Global Positioning System

Hệ thống định vị toàn cầu

16

HAC

Hierarchical Agglomerative

Phân cụm tích lũy phân cấp


Phân cụm phân tán lai với

Clustering

hiệu quả năng lƣợng

Hybrid-Low Energy Adaptive

Phân cụm phân cấp thích ứng

Clustering Hierarchy

năng lƣợng thấp

Location Aided Cluster Based

Định tuyến hiệu quả dựa vào

Energy Efficient Routing

phân cụm vị trí

21

LCA

Linked Cluster Algorithm

Thuật toán phân cụm liên kết



Nút thành viên trong cụm

26

PBO

Pollination Based Optimization

Tối ƣu hóa thụ phấn

27

PEGASIS

Power-Efficient Gathering in Sensor

Một giao thức tập trung năng

Information Systems

lƣợng hiệu quả trong các hệ
thống thông tin cảm biến

28

PSO

Particle Swarm Optimization



TCCA

TEEN

Time controlled Clustering

Thuật toán phân cụm theo

algorithm

thời gian

Threshold sensitive Energy Efficient

Giao thức hiệu quả năng

sensor Network protocol

lƣợng với ngƣỡng cảm biến

33

Topo

Topology

Cấu trúc liên kết mạng

34

nghiên cứu. Đặc biệt, mạng cảm biến không dây đang đƣợc nghiên cứu mạnh mẽ và
đƣợc triển khai trong nhiều lĩnh vực khác nhau của đời sống. Các ứng dụng điển hình
đƣợc triển khai nhƣ: nhà thông minh, thành phố thông minh; trong công nghiệp ứng
dụng vào: các hệ thống giám sát máy móc, phát hiện lỗi trong các nhà máy cho đến
các ứng dụng trong quân sự, y tế, nông nghiệp công nghệ cao, giao thông. Ngoài ra
còn có các ứng mạng cảm biến không thể thiếu trong một xã hội phát triển nhƣ: theo
dõi biến đổi môi trƣờng, dự báo thiên tai nhƣ các hệ thống dự báo lũ lụt, núi lửa, động
đất, cháy rừng, v.v.[6, 46]. Trong tƣơng lai không xa các ứng dụng mạng cảm biến
không dây sẽ trở thành một phần không thể thiếu trong cuộc sống của con ngƣời.
Tuy nhiên, khi nghiên cứu về mạng cảm biến không dây gặp rất nhiều thách
thức. Đặc biệt nghiên cứu triển khai mạng cảm biến không dây trong môi trƣờng 3
chiều đạt hiệu quả. Điều này có nghĩa là khi triển khai mạng cảm biến thì phải hiệu
quả về khả năng phủ sóng khu vực mục tiêu. Sau đó cần phải xây dựng cấu trúc mạng
để mạng cảm biến tiết kiệm năng lƣợng và kéo dài tuổi thọ trong môi trƣờng 3 chiều.
Bài toán triển khai mạng cảm biến không dây nhằm mục đích xác định vị trí
các cảm biến trong môi trƣờng để đạt đƣợc mục tiêu đề ra của mạng. Thông thƣờng,
các nhà nghiên cứu giả thiết môi trƣờng triển khai mạng cảm biến không dây tƣơng
đối tốt. Tuy nhiên, trong thực tế mạng cảm biến không dây đƣợc triển khai trong
nhiều môi trƣờng đa dạng thậm chí con ngƣời không tiếp cận trực tiếp đƣợc nhƣ
khu vực thiên tai, nhiễm hóa chất độc hại, v.v.[54]. Hơn thế nữa trong môi trƣờng
luôn tồn tại hố mạng, nơi chúng ta không thể đặt cảm biến vào đƣợc hoặc đặt đƣợc
cảm biến nhƣng chúng không thể phủ sóng cảm biến đƣợc do có vật cản che khuất
vùng cần phủ sóng. Việc triển khai tốt một mạng cảm biến không dây giúp cho hệ
thống mạng cảm biến có thể phủ sóng tối đa khu vực mục tiêu, đây là mục tiêu mà
các nhà nghiên cứu mong muốn đạt đƣợc [75].
1


Bài toán xây dựng cấu trúc mạng cảm biến không dây rất quan trọng, nó ảnh
hƣởng đến tuổi thọ của mạng. Các cảm biến thông thƣờng sử dụng nguồn năng


Chƣơng 3 ―Tối ƣu năng lƣợng tiêu thụ mạng cảm biến không dây trong môi
trƣờng 3 chiều‖ trình bày mô hình năng lƣợng tiêu thụ của mạng cảm biến; đề xuất
giải pháp xây dựng cấu trúc mạng cảm biến không dây trong môi trƣờng 3 chiều
dựa trên phƣơng pháp phân cụm mờ với mục tiêu giảm thiểu năng lƣợng tiêu thụ và
kéo dài thời gian sống của mạng cảm biến. Cuối cùng kết quả thực nghiệm đƣợc
phân tích đánh giá để khẳng định tính hiệu quả của giải pháp đề xuất. Kết quả chính
đã đƣợc công bố trong các công trình 2, 4, 5, 6.
Đối tƣợng và phƣơng pháp nghiên cứu
Trên cơ sở mục tiêu luận án, nghiên cứu sinh dựa trên các công cụ toán học
để mô hình hóa các địa hình, mạng cảm biến không dây, năng lƣợng tiêu thụ của
mạng cảm biến trong môi trƣờng 3 chiều. Nghiên cứu phát triển thuật toán tối ƣu
bầy đàn cho bài toán tối ƣu hóa vùng phủ sóng của mạng cảm biến không dây; thuật
toán phân cụm mờ cho bài toán xây dựng cấu trúc của mạng cảm biến không dây
nhằm tiết kiệm năng lƣợng tiêu thụ, kéo dài tuổi thọ mạng cảm biến. Phƣơng pháp
thực nghiệm đƣợc thực hiện trên nhiều bộ dữ liệu khác nhau, các phân bố và số
lƣợng cảm biến khác nhau, các tham số đầu vào của các thuật toán để đánh giá tính
hiệu quả và ổn định của giải pháp đề xuất.
Ý nghĩa về khoa học và thực tiễn của luận án
-

Ý nghĩa về khoa học
o Mô hình hóa toán học cho mạng cảm biến không dây trong môi
trƣờng 3 chiều và địa hình phức tạp trong thực tế.
o Nghiên cứu phát triển thuật toán tối ƣu bầy đàn cho phép triển khai
mạng cảm biến với khả năng phủ sóng tối đa khu vực mục tiêu.
o Nghiên cứu phát triển thuật toán phân cụm mờ, cân bằng năng lƣợng
giữa các cụm nhằm tối ƣu năng lƣợng tiêu thụ của toàn mạng, kéo dài
tuổi thọ của mạng cảm biến trong môi trƣờng 3 chiều.


Mỗi nút cảm biến đƣợc cấu thành bởi 4 thành phần cơ bản: đơn vị cảm biến,
đơn vị xử lý, đơn vị truyền dẫn và bộ nguồn nhƣ Hình 1-2. Ngoài ra, các cảm biến
có thể có thêm thành phần khác nhƣ hệ thống định vị, bộ phận di động tùy thuộc
vào các ứng dụng khác nhau [6].

5


Đơn vị cảm biến bao gồm các cảm biến và bộ chuyển đổi tín hiệu số ADC.
Các thông tin thu thập đƣợc bởi các cảm biến từ môi trƣờng ở tín hiệu tƣơng tự sẽ
đƣợc chuyển sang tín hiệu số bởi ADC. Cuối cùng tín hiệu số đƣợc chuyển đến cho
đơn vị xử lý.
Đơn vị xử lý bao gồm bộ xử lý và bộ nhớ, có nhiệm vụ thực hiện các chức
năng đƣợc cài đặt sẵn để xử lý dữ liệu nhận đƣợc.
Đơn vị truyền dẫn là các bộ thu, phát sóng, và có nhiệm vụ phát hoặc thu dữ
liệu từ các nút cảm biến khác trong mạng.
Hệ thống định vị cung cấp thông tin về vị trí của thiết bị cảm biến trên địa
hình và đƣợc bộ xử lý gởi tín hiệu về thông tin vị trí cho hệ thống mạng cảm biến.
Bộ phận di động giúp thiết bị cảm biến có thể di chuyển đến các vị trí xác
định đƣợc điều khiển bởi đơn vị xử lý khi cần thiết.
Bộ nguồn có nhiệm vụ cung cấp năng lƣợng cho tất cả các thành phần của
nút cảm biến. Do các cảm biến kết nối vào hệ thống mạng bằng sóng vô tuyến nên
thông thƣờng bộ nguồn sử dụng pin.
Khác với các loại mạng truyền thống, trong mạng cảm biến không dây, mỗi
nút cảm biến có kích thƣớc nhỏ, có khả năng về năng lƣợng, tính toán, bộ nhớ hạn
chế nên cấu trúc mạng thay đổi thƣờng xuyên do các nút cảm biến có thể hết năng
lƣợng [6]. Cấu trúc của mạng cảm biến cũng khác với mạng truyền thống và có các
đặc điểm sau:
-



Thị giác

Ánh sáng , hình dạng, kích thƣớc, Cảm biến thu hình, cảm

Xúc giác

Thiết bị cảm biến

vị trí xa gần, màu sắc

biến quang

Áp suất, nhiệt độ, cơn đau, ẩm, khô

Nhiệt trở, cảm biến độ
rung động

Vị giác

Ngọt, mặn, chua cay,…

Đo lƣợng đƣờng trong máu

Thính giác

Sóng âm, âm lƣợng,…

Cảm biến sóng siêu âm


một nút ở cấp cao hơn trong cây nếu nhƣ nó nằm trong phạm vi truyền thông. Các
nút ở cấp cao hơn sẽ đƣợc kết nối với trạm cơ sở. Đây đƣợc gọi là truyền thông đa
hop (multi-hop). Trong cấu trúc này, ƣu điểm là có khả năng mở rộng: nếu nhƣ một
nút bị lỗi, các nút ở xa có thể kết nối với các nút khác miễn là nằm trong phạm vi

8


truyền thông để chuyển dữ liệu đến trạm cơ sở. Tuy nhiên, nhƣợc điểm của cấu trúc
này là các nút gần trạm cơ sở sẽ tiêu tốn năng lƣợng nhiều hơn do phải chuyển tiếp
dữ liệu của các nút ở xa [30].

Hình 1-4 Mô hình cấu trúc phân cấp
1.1.3.3 Cấu trúc tập trung
Trong cấu trúc tập trung (Hình 1-5) các cảm biến đƣợc chia thành cụm,
trong mỗi cụm có một nút gọi là nút chủ (Cluster Head - CH), các nút còn lại là
thành viên của cụm (non-CH) đƣợc kết nối trực tiếp đến nút CH. Các nút non-CH
có nhiệm vụ thu thập các thông tin từ môi trƣờng và chuyển đến nút CH khi cần
thiết, trong khi đó các nút CH có nhiệm vụ thu thập thông tin từ các non-CH, tổng
hợp, phân tích loại bỏ thông tin dƣ thừa và chuyển tiếp đến trạm cơ sở. Trong cấu
trúc này, để kéo dài tuổi thọ của mạng các nút trong cụm sẽ thay phiên nhau đóng
vai trò nút CH, điều này cân bằng năng lƣợng tiêu thụ giữa tất cả các cảm biến
trong cụm. Hơn nữa, việc loại bỏ các thông tin dƣ thừa của các nút CH sẽ làm giảm
đáng kể năng lƣợng tiêu thụ và tránh quá tải cho quá trình chuyển dữ liệu đến trạm
cơ sở [30].
Trong các cấu trúc liên kết mạng trên, cấu trúc tập trung đƣợc các nhà nghiên
cứu quan tâm nhiều nhất.

9


Các công cụ chụp ảnh hiện nay thông thƣờng từ các vệ tinh nhƣ Aster và Spot.
Trong phƣơng pháp đƣờng đồng mức các bản đồ độ cao số đƣợc xây dựng từ
phƣơng pháp quan trắc địa số hóa dƣới dạng đƣờng đồng mức, mỗi đƣờng đồng mức
thể hiện một giá trị độ cao trong địa hình. Kết hợp việc sử dụng công nghệ hệ thống
thông tin địa lý GIS với các bản đồ địa hình dạng đƣờng đồng mức để xây dựng bản
đồ độ cao số bằng các phần mềm nhƣ Mapinfo, ArcGis, EarthExplore, v.v.

Hình 1-6 Hai mô hình DEM thông dụng
1.1.5 Hố mạng và vật cản
1.1.5.1 Hố mạng
Một trở ngại lớn trong hoạt động của mạng cảm biến là sự xuất hiện của
các ―hố mạng‖ [3, 40], tức là các vùng không tồn tại các nút mạng cảm biến hoặc
nếu có thì không còn khả năng hoạt động. Ngƣời ta thƣờng quan tâm đến các loại
hố mạng sau:
Hố mạng vật lý: Là các vùng không thể đặt đƣợc các cảm biến do đặc điểm
của địa hình, hoặc đặt đƣợc các cảm biến thì không có khả năng thu thập thông tin
từ đƣợc môi trƣờng xung quanh [40].

11


Hố định tuyến: Là khu vực trong mạng cảm biến mà không thể tham gia vào
việc truyền dữ liệu [3].
Hố nhiễu sóng: Một kịch bản thú vị cũng có thể xảy ra trong các ứng dụng
theo dõi các đối tƣợng mà các đối tƣợng này lại đƣợc trang bị thiết bị làm nhiễu tần
số giao tiếp giữa các nút cảm biến. Khi điều này xảy ra, các nút cảm biến vẫn có thể
phát hiện sự hiện diện của các đối tƣợng trong khu vực nhƣng không thể chuyển dữ
liệu về trạm cơ sở vì bị gây nhiễu. Những nút nhƣ vậy trong mạng cảm biến sẽ tạo
thành các hố nhiễu sóng [3].
Hố đen: Mạng cảm biến không dây rất dễ bị tấn công từ chối dịch vụ do đặc

chiều hoặc hiệu suất không cao vì trên địa hình phức tạp trong thực tế luôn tồn tại:
(a) các vật cản giữa cảm biến và điểm, vùng mục tiêu; (b) tồn tại các hố mạng vật lý
mà ớ đó không thể đặt các cảm biến. Chính vì vậy nghiên cứu vấn đề phủ sóng tối
ƣu trong môi trƣờng 3 chiều gặp nhiều thách thức.
Một giải pháp dùng để xác định số vật cản giữa cảm biến và điểm cần phủ
sóng trên địa hình đƣợc trình bày trong [34]. Kết quả của phƣơng pháp này dùng để
tính giá trị khả năng tầm nhìn giữa cảm biến và điểm mục tiêu trên địa hình. Trong
thực tế, các yếu tố ảnh hƣởng đến tầm nhìn giữa cảm biến và điểm mục tiêu trên địa
hình là độ cao của tất cả các điểm trên đƣờng thẳng nối giữa chúng. Các thông tin
độ cao này đƣợc cung cấp bởi ma trận DEM, mỗi tọa độ điểm lƣới lƣu trữ độ cao
của điểm đó trong môi trƣờng thực tế.
Trong phƣơng pháp LoS (Line-of-Sight) [34], để tính đƣợc khả năng tầm
nhìn giữa cảm biến và điểm mục tiêu. Các bƣớc đƣợc thực hiện nhƣ sau. Trƣớc tiên,
chúng ta chia đoạn thẳng giữa cảm biến và điểm mục tiêu thành nhiều đoạn, mỗi
đoạn có kích thƣớc của ô lƣới. Một danh sách các điểm lƣới trên đƣờng thẳng nối
giữa chúng đƣợc xác định. Thứ hai, mỗi điểm trong danh sách đƣợc kiểm tra với ô
lƣới chứa nó. Nếu độ cao của nó nhỏ hơn độ cao ô lƣới thì số vật cản tăng lên một.
Hình 1-7 cho thấy khả năng tầm nhìn giữa cảm biến sj và điểm mục tiêu ei.

13


(a) Không có vật cản, (b) Có vật cản
Hình 1-7 Cách xác định vật cản trong địa hình

1.2. Hai bài toán quan trọng trong mạng cảm biến không dây và các nghiên
cứu liên quan
1.2.1 Bài toán tối ƣu phủ sóng
Trong mạng cảm biến không dây, vấn đề tối ƣu phủ sóng khu vực mục tiêu
đặc biệt quan trọng ảnh hƣởng đến chất lƣợng của WSN. Trong không gian 2 chiều