BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
NGUYỄN TRUNG DŨNG
NGHIÊN CỨU PHÁT TRIỂN ĐỊNH TUYẾN TIẾT KIỆM NĂNG
LƢỢNG CHO MẠNG CẢM BIẾN KHÔNG DÂY
LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG
Hà Nội -2014
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
NGUYỄN TRUNG DŨNG
NGHIÊN CỨU PHÁT TRIỂN ĐỊNH TUYẾN TIẾT KIỆM NĂNG
LƢỢNG CHO MẠNG CẢM BIẾN KHÔNG DÂY
LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG
Ngƣời hƣớng dẫn khoa học:
PGS.TS Nguyễn Văn Đức
Hà Nội -2014
Lời cam đoan
Tác giả xin cam đoan đây là công trình nghiên cứu của tác giả, không sao chép của bất kỳ
người nào. Các số liệu kết quả nêu trong luận án là hoàn toàn trung thực và chưa từng được
công bố bởi bất kỳ ai.
Tác giả
Nguyễn Trung Dũng
Lời cảm ơn
Tôi xin chân thành cảm ơn PGS.TS Nguyễn Văn Đức đã nhiệt tình hướng dẫn và giúp đỡ
tôi rất nhiều trong quá trình nghiên cứu và hoàn thành Luận án.
Cũng xin chân thành cảm ơn Viện sau Đại học, Bộ môn Kỹ thuật thông tin - Viện Điện tử
Viễn thông - Trường Đại học Bách khoa Hà Nội đã tạo điều kiện thuận lợi để tôi hoàn thành
nhiệm vụ nghiên cứu của mình.
Tôi cũng bày tỏ lòng biết ơn đến Gia đình tôi cùng Bố mẹ, các anh chị em và bạn bè những
người đã ủng hộ và động viên giúp đỡ tôi trong thời gian làm Luận án.
Nguyễn Trung Dũng
MỤCLỤC
MỞ ĐẦU
CHƢƠNG 1. TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY
1.1 Cấu trúc mạng cảm biến không dây
1.1.1 Các yếu tố ảnh hưởng đến cấu trúc mạng cảm biến không dây
1.1.2 Đặc điểm của cấu trúc mạng cảm biến
1.1.3 Kiến trúc giao thức mạng
1.1.4 Hai cấu trúc đặc trưng của mạng cảm biến
1.1.4.1 Cấu trúc phẳng
1.1.4.2 Cấu trúc phân tầng
1.2 Ứng dụng mạng cảm biến không dây
1.2.1 Ứng dụng trong quân đội
1.2.2 Ứng dụng trong môi trường
1.2.3 Ứng dụng trong chăm sóc sức khỏe
1.2.4 Ứng dụng trong gia đình
1.3 Một số vấn đề thách thức kỹ thuật
1.3.1 Vấn đề lớp MAC
1.3.2 Vấn đề định tuyến
1.3.3 Vấn đề năng lượng
CHƢƠNG 2.TỐI ƢU ĐỊNH TUYẾN ĐA CHẶNG TIẾT KIỆM NĂNG
LƢỢNG
2.1 Các phương pháp định tuyến tiết kiệm năng lượng dựa trên kỹ thuật giảm
thiểu các gói tin dư thừa
2.1.1 Phương pháp định tuyến mở rộng vòng Expanding Ring Search –
ERS
2.1.2 Đề xuất phương pháp định tuyến mở rộng vòng giảm thiểu số nút
tham gia định tuyến – Efficient Expanding Ring Search (EERS)
2.1.2.1 Kỹ thuật xác định thông tin nút lân cận cách hai bước nhảy
mạng
2.1.2.2 Làm tràn bản tin tìm đường hiệu quả
2.1.2.3 Tiết kiệm năng lượng tìm kiếm mở rộng vòng
2.1.2.4 Lưu đồ thuật toán EERS
2.1.2.5 Mô phỏng và đánh giá
2.2 Các phương pháp định tuyến dựa vào năng lượng của nút cảm biến nhằm
nâng cao thời gian sống của mạng
2.2.1 Đề xuất phương pháp định tuyến dựa vào mức năng lượng các nút
cảm biến để loại bỏ tuyến đường có năng lượng thấp
2.2.2 Đề xuất phương pháp định tuyến dựa vào hai điều kiện để chọn
đường đi tốt nhất - Routing Dual Criterion (RDC)
2.2.3 Mô phỏng kết quả
2.3 Phương pháp định tuyến tiết kiệm năng lượng dựa trên điều khiển công
suất
2.3.1 Kỹ thuật điều khiển công suất
2.3.2 Đề xuất phương pháp định tuyến dựa trên điều khiển công suất
2.3.3 Mô phỏng và đánh giá kết quả
i
Trang
1
10
10
10
13
14
16
16
17
19
20
21
22
22
22
22
23
23
25
25
26
30
30
32
35
38
38
43
43
49
51
56
56
57
58
2.4 Kết luận
65
CHƢƠNG 3.TIẾT KIỆM NĂNG LƢỢNG TRONG MẠNG CẢM BIẾN
KHÔNG DÂY ĐA CHẶNG SỬ DỤNG PHƢƠNG PHÁP
ƢỚC ĐOÁN VỊ TRÍ CỦA ĐỐI TƢỢNG
3.1 Cơ sở lý thuyết toán học
3.1.1 Định lý xác suất Bayes
3.1.2 Hàm phân bố xác suất và hàm mật độ xác suất của một biến ngẫu
nhiên
3.1.2.1 Hàm phân bố xác suất (Probability Distribution Function)
3.1.2.2 Hàm mật độ xác suất (Probability Density Function)
3.1.3 Kỳ vọng và phương sai của biến ngẫu nhiên
3.1.3.1 Kỳ vọng của biến ngẫu nhiên
3.1.3.2 Phương sai của biến ngẫu nhiên
3.1.4 Hàm phân phối xác suất Gaussian – Hàm phân phối chuẩn
3.1.5 Tiến trình Markov
3.1.6 Mô hình hóa hệ thống không gian trạng thái động
3.1.7 Tiếp cận Bayes
3.1.8 Một số thuật toán theo vết dựa trên tiếp cận Bayes
3.2 Sơ lược về một số thuật toán dự đoán vị trí
3.2.1 Bộ lọc Kalman
3.2.2 Bộ lọc Kalman mở rộng
3.2.2.1 Những giới hạn của mô hình tuyến tính
3.2.2.2 Khai triển chuỗi Taylor
3.2.3 Kết luận
3.3 Thuật toán bộ lọc chất điểm (Particle Filter)
3.3.1 Các điều kiện rằng buộc của thuật toán bộ lọc chất điểm
3.3.2 Hướng tiếp cận của bộ lọc thuật toán bộ lọc chất điểm
3.3.3 Lấy mẫu quan trọng (Importance Sampling)
3.3.4 Lấy mẫu quan trọng tuần tự (Sequential Importance Sampling –
SIS)
3.3.5 Vấn đề lựa chọn hàm mật độ đề xuất
3.3.6 Vấn đề thoái hóa mẫu và giải pháp lấy mẫu lại (Resampling)
3.3.7 Thuật toán bộ lọc chất điểm tổng quát (Generic Particle Filter –
GPF)
3.3.8 Thuật toán lấy mẫu lại quan trọng tuần tự (Sequential Importance
Resampling – SIR)
3.3.9 Mô phỏng thuật toán SIR
3.4 Ứng dụng giám sát đối tượng trong mạng cảm biến không dây sử dụng
bộ lọc chất điểm PF
3.4.1 Mô hình hóa bài toán
3.4.2 Đề xuất phương pháp thực hiện bộ lọc chất điểm
3.4.2.1 Pha khởi tạo N chất điểm
3.4.2.2 Pha lan truyền chất điểm
3.4.2.3 Pha tính toán trọng số
3.4.2.4 Kết quả mô phỏng
3.5 Đề xuất mô hình giám sát theo vùng
ii
66
66
67
67
67
68
68
68
69
69
70
70
71
73
73
74
78
78
79
80
81
81
82
83
84
88
89
90
91
92
99
99
100
100
101
102
103
105
3.6 Mô hình giám sát toàn mạng
3.7 Mô phỏng và đánh giá kết quả
3.8 Kết luận
108
110
116
KẾT LUẬN CHUNG
117
TÀI LIỆU THAM KHẢO
124
DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ
132
iii
DANH MỤC CÁC CHỮ VIẾT TẮT
ABR
ADC
AODV
AOMDV
BS
CNI
CSMA/CA
DSR
EERS
EKF
ERS
GPF
KF
LEACH
MAC
NS2
PDR
PF
PRP
RDC
RF
RMS
ROF
RREP
RREQ
SIR
SIS
TTL
WSN
Định tuyến loại bỏ tuyến đường xấu
Bộ chuyển đổi tương tự số
Định tuyến vector khoảng cách theo
yêu cầu
Adhoc On-demand Multipath Distance Định tuyến vector khoảng cách đa
Vector
đường theo yêu cầu
Base Station
Trạm gốc
Collecting Neighbors’ Information
Pha thu thập thông tin nút lân cận
trong giao thức định tuyến EERS
Carrier Sense Multiple Access/
Cảm biến sóng mang đa truy cập/
Collision Avoidance
tránh xung đột
Dynamic Source Routing
Định tuyến theo nguồn
Efficient Expanding Ring Search
Định tuyến tìm kiếm mở rộng vòng
tối ưu
Extended Kalman Filter
Bộ lọc Kalman mở rộng
Expanding Ring Search
Định tuyến tìm kiếm mở rộng vòng
Generic Particle Filter
Bộ lọc chất điểm tổng quát
Kalman Filter
Bộ lọc Kalman
Low Energy Adaptive Clustering Định tuyến phân vùng tiết kiệm
Hierarchy
năng lượng
Media Access Control
Điều khiển truy nhập đường truyền
Network Simulator 2
Phần mềm mô phỏng mạng
Packet Delivery Ratio
Tỷ lệ truyền gói tin thành công
Particle Filter
Bộ lọc chất điểm
Power Control Combined with Routing Định tuyến dựa trên điều khiển công
Protocol
suất
Routing dual criterion
Định tuyến hai điều kiện
Radio Frequency
Sóng vô tuyến
Root-Mean-Square
Độ lệch căn phương trung bình
Reducing the Overhead of Flooding
Pha giảm thiểu bản tin dư thừa trong
giao thức định tuyến EERS
Route Reply
Bản tin trả lời chứa thông tin tuyến
đường trong định tuyến
Route Request
Bản tin tìm đường
Sequential Importance Resampling
Lây mẫu lại quan trọng tuần tự
Sequential Importance Sampling
Lấy mẫu quan trọng tuần tự
Time to Live
Thời gian sống
Wireless Sensor Network
Mạng cảm biến không dây
Avoid Bad Route
Analog-to-Digital
Adhoc On-demand Distance Vector
iv
DANH MỤC CÁC KÝ HIỆU
δi
ck
xt
yt
gt
ht
wt
vt
ut
xˆt
Tham số của hàm phân phối xác suất Gaussian – giá trị kỳ vọng của biến ngẫu
nhiên X
Tham số của hàm phân phối xác suất Gaussian – giá trị phương sai của biến
ngẫu nhiên X
Hàm xung Delta
Trạng thái của hệ thống tại thời điểm k
Trạng thái của hệ thộng tại thời điểm t
Tín hiệu đo đạc của hệ thống tại thời điểm t
Hàm chuyển tại thời điểm t
Hàm quan sát tại thời điểm t
Nhiễu xử lý tại thời điểm t
Nhiễu quan sát tại thời điểm t
Đầu vào của hệ thống tại thời điểm t
Ước lượng hậu nghiệm của xt
xˆt
Ước lượng tiên nghiệm của xt
Pt
Hiệp phương sai của lỗi ước lượng của xˆt
Hiệp phương sai của lỗi ước lượng của xˆt
Ma trận hệ số khuếch đại Kalman
Biến ngẫu nhiên của hàm phân bố xác suất
Hàm phân bố xác suất của biến ngẫu nhiên X
Hàm mật độ xác suất của biến ngẫu nhiên X
Xác suất tương ứng của các giá trị xi của biến ngẫu nhiên X
Kỳ vọng của biến ngẫu nhiên X
Phương sai của biến ngẫu nhiên X
Chi phí tuyến đường
Công suất tiêu hao
Công suất truyền lớn nhất
Công suât nhạy thu
Công suất dự trữ
Công suất truyền
Năng lượng còn lại của nút cảm biến trong thuật toán PRP
Ngưỡng năng lượng còn lạicủa nút cảm biến trong thuật toán PRP
Thời gian đợi bản tin trả lời
Số nút cảm biến trong mạng
Độ tăng của giá trị TTL giữa hai lần tìm kiếm trong thuật toán tìm đường mở
rộng vòng
Thời gian hiện tại
Mốc thời gian trong tương lai
Số chất điểm
Pt
Kt
X
F(X)
f(x)
pi
E(X)
V(X)
M
Ploss
Ptx_max
Psen
Pmar
Ptx
LPsent
LPthr
Tc
n
K
t
T
N
v
DANH MỤC CÁC BẢNG
Bảng 2.1. Các thông số mô phỏng chung
Bảng 2.2. Các thông số mô phỏng AODV và PRP
Bảng 3.1. Ví dụ về kết quả khai triển Taylor
Bảng 3.2. Thông số mô phỏng ứng dụng giám sát theo vùng
vi
Trang
39
59
80
111
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1. Một mạng cảm biến không dây đơn giản
Hình 1.2. Cấu tạo nút cảm biến
Hình 1.3. Kiến trúc giao thức mạng cảm biến
Hình 1.4. Cấu trúc phẳng của mạng cảm biến
Hình 1.5. Cấu trúc tầng của mạng cảm biến
Hình 1.6. Cấu trúc mạng phân cấp chức năng theo lớp
Hình 2.1. Lưu đồ thuật toán của nút nguồn gửi gói tin RREQ
Hình 2.2. Lưu đồ thuật toán xử lí ở nút trung gian
Hình 2.3. Ví dụ cơ chế tìm kiếm mở rộng vòng (Expanding Ring Search)
Hình 2.4. Ví dụ quá trình xác định thông tin nút lân cận cách 2 bước nhảy
Hình 2.5. Đề xuất phương pháp làm tràn hiệu quả dựa trên kĩ thuật nghe ngóng
Hình 2.6. Lưu đồ thuật toán EERS
Hình 2.7. So sánh thời gian sống của mạng giữa AODV, ERS và EERS
Hình 2.8. So sánh tỷ lệ truyền gói thành công PDR giữa EERS, ERS và AODV
Hình 2.9. So sánh về thông lượng mạng khi sử dụng định tuyến EERS, ERS và
AODV
Hình 2.10. Ví dụ hoạt động của ABR
Hình 2.11. Thuật toán ABR thực hiện tại nút nguồn
Hình 2.12. Thuật toán ABR thực hiện tại nút trung gian
Hình 2.13. Thuật toán ABR tại nút đích
Hình 2.14. Sự thay đổi giá trị của biến rq_min_energy và rp_energy trong thuật
toán RDC
Hình 2.15. Ví dụ về hoạt động của thuật toán RDC
Hình 2.16. Quá trình duy trì update thông tin định tuyến trong thuật toán RDC
Hình 2.17. So sánh thời gian sống của mạng giữa AODV, ERS, EERS, ABR và
RDC mô phỏng 1
Hình 2.18. So sánh tỷ lệ gửi gói tin thành công giữa AODV, ERS, EERS, ABR
và RDC mô phỏng 1
Hình 2.19. So sánh thông lượng Throughput giữa AODV, ERS, EERS, ABR và
RDC mô phỏng 1
Hình 2.20. So sánh thời gian sống của mạng giữa AODV, ERS, EERS, ABR và
RDC mô phỏng 2
Hình 2.21. So sánh tỷ lệ gửi gói tin thành công giữa AODV, ERS, EERS, ABR
và RDC mô phỏng 2
Hình 2.22. So sánh thông lượng của mạng giữa AODV, ERS, EERS, ABR và
RDC mô phỏng 2
Hình 2.23. So sánh thời gian sống của mạng khi sử dụng AODV và PRP
Hình 2.24. So sánh thông lượng của mạng khi sử dụng AODV và PRP
Hình 2.25. So sánh tỷ lệ truyền gói tin thành công khi sử dụng PRP và AODV
Hình 2.26. Năng lượng toàn mạng còn lại khi sử dụng AODV và PRP với mô
phỏng 60 nút mạng
Hình 2.27. Năng lượng toàn mạng còn lại khi sử dụng AODV và PRP với mô
phỏng 80 nút mạng
Hình 2.28. Năng lượng toàn mạng còn lại khi sử dụng AODV và PRP với mô
phỏng 90 nút mạng
vii
Trang
11
12
15
17
17
18
27
28
29
31
34
37
40
41
42
44
45
46
47
49
50
51
52
53
53
54
55
56
60
60
61
61
62
62
Hình 2.29. Năng lượng toàn mạng còn lại khi sử dụng AODV và PRP với mô
phỏng 100 nút mạng
Hình 2.30. Năng lượng toàn mạng còn lại khi sử dụng AODV và PRP với mô
phỏng 110 nút mạng
Hình 2.31. Năng lượng toàn mạng còn lại khi sử dụng AODV và PRP với mô
phỏng 120 nút mạng
Hình 3.1. Sơ đồ tiếp cận Bayes
Hình 3.2. Đường đặc tuyến Von-Ampe
Hình 3.3. Kết quả của thuật toán SIS ứng với N = 100 mẫu
Hình 3.4. Kết quả của thuật toán SIS ứng với N = 1000 mẫu
Hình 3.5. Kết quả của thuật toán SIS ứng với N = 5000 mẫu
Hình 3.6. Kết quả thuật toán SIR ứng với N = 100, t = 50s
Hình 3.7. Kết quả thuật toán SIR ứng với N = 1000, t = 50s
Hình 3.8. Kết quả thuật toán SIR ứng với N = 5000, t = 50s
Hình 3.9. Kết quả thuật toán SIR ứng với N = 100, t = 150s
Hình 3.10. Kết quả thuật toán SIR ứng với N = 1000, t = 150s
Hình 3.11. Kết quả thuật toán SIR ứng với N = 5000, t = 150s
Hình 3.12. So sánh mức độ sai lệch trong việc giải quyết bài toán theo vết của
hai thuật toán SIS và SIR
Hình 3.13. So sánh lỗi RMS của thuật toán Kalman và bộ lọc chất điểm với
N=100
Hình 3.14. So sánh lỗi RMS của thuật toán Kalman và bộ lọc chất điểm với
N=1000
Hình 3.15. So sánh lỗi RMS của thuật toán Kalman và bộ lọc chất điểm với
N=5000
Hình 3.16. So sánh lỗi của thuật toán bộ lọc chất điểm khi N = 100 và N = 1000
Hình 3.17. So sánh lỗi của thuật toán bộ lọc chất điểm khi N = 1000 và N = 5000
Hình 3.18. Ví dụ về lan truyền đám mây chất điểm
Hình 3.19. Ước lượng đường đi của đối tượng thực hiện với các thuật tóan SIS,
GPF, SIR, SIS-Dis
Hình 3.20.Trễ đầu cuối khi mô phỏng các thuật toán theo thời gian
Hình 3.21.Độ chính xác ước lượng của các thuật toán SIS, GPF, SIR và SIS-Dis
khi mô phỏng theo thời gian
Hình 3.22. Ví dụ ứng dụng giám sát theo vùng
Hình 3.23. Ví dụ ứng dụng giám sát theo toàn bộ mạng
Hình 3.24. Mô hình mô phỏng ứng dụng giám sát vùng và giám sát toàn mạng
Hình 3.25. Đồ thị so sánh thời gian sống của mạng khi sử dụng mô hình giám sát
toàn mạng và giám sát theo vùng với các giao thức định tuyến khác nhau
mô phỏng 1
Hình 3.26. Đồ thị so sánh lượng dữ liệu gửi về trạm trong mạng khi sử dụng mô
hình giám sát toàn mạng và giám sát theo vùng với các giao thức định
tuyến khác nhau mô phỏng 1
Hình 3.27. Đồ thị so sánh thời gian sống của mạng khi sử dụng mô hình giám sát
toàn mạng và giám sát theo vùng với các giao thức định tuyến khác nhau
mô phỏng 2
Hình 3.28. Đồ thị so sánh lượng dữ liệu gửi về trạm trong mạng khi sử dụng mô
hình giám sát toàn mạng và giám sát theo vùng với các giao thức định
viii
63
63
64
73
79
87
87
88
92
93
93
94
94
95
96
96
97
97
98
98
102
104
104
105
107
109
110
111
112
112
113
tuyến khác nhau mô phỏng 2
Hình 3.29. Đồ thị so sánh thời gian sống của mạng khi sử dụng mô hình giám sát
toàn mạng và giám sát theo vùng với các giao thức định tuyến khác nhau
mô phỏng 3
Hình 3.30. Đồ thị so sánh lượng dữ liệu gửi về trạm trong mạng khi sử dụng mô
hình giám sát toàn mạng và giám sát theo vùng với các giao thức định
tuyến khác nhau mô phỏng 3
Hình 3.31.Đồ thị so sánh thời gian sống của mạng khi sử dụng mô hình giám sát
toàn mạng và giám sát theo vùng với các giao thức định tuyến khác nhau
mô phỏng 4
Hình 3.32. Đồ thị so sánh lượng dữ liệu gửi về trạm trong mạng khi sử dụng mô
hình giám sát toàn mạng và giám sát theo vùng với các giao thức định
tuyến khác nhau mô phỏng 4
ix
113
114
114
115
MỞ ĐẦU
1.1.Mục đích nghiên cứu
Trong các mạng viễn thông và mạng nội bộ không dây, các nút di động giao tiếp trực tiếp
với trạm gốc. Các mạng này có thể gọi là mạng đơn chặng. Trong một số mạng không dây đặc
biệt khác, xuất hiện một hoặc một số nút trung gian tham gia vào việc truyền dữ liệu từ một
nút di động về trạm gốc. Những mạng này thường được gọi là mạng không dây đa chặng. Khi
so sánh với mạng đơn chặng, mạng không dây đa chặng có một số lợi ích như khả năng mở
rộng vùng hoạt động của mạng, tăng cường khả năng kết nối và truyền dữ liệu từ các nút ở xa
về trạm gốc. Hơn nữa, khi truyền đa chặng, khoảng cách truyền sẽ được thu ngắn và do đó
công suất cũng như năng lượng truyền có thể ít hơn các kết nối ở xa đồng thời cho kết quả tốt
hơn về tốc độ truyền dữ liệu. Mạng không dây đa chặng loại bỏ được việc triển khai hệ thống
hạ tầng thiết bị và đường dây, giúp giảm thiểu chi phí triển khai. Trong trường hợp các mạng
đa chặng được triển khai dày đặc, sẽ có nhiều đường đi được lựa chọn, điều đó làm tăng khả
năng đáp ứng của hệ thống mạng.
Có nhiều ứng dụng mô hình mạng không dây đa chặng đã được nghiên cứu trong nhiều
năm qua. Ban đầu mạng không dây đa chặng được đề xuất để thực hiện mở rộng vùng bao phủ
trong hệ thống mạng viễn thông bằng cách chuyển tiếp các gói tin. Hiện nay, các lưới mạng
không dây đa chặng đã được đề xuất cho các dịch vụ Internet băng rộng không cần triển khai
hệ thống đường dây hạ tầng tốn kém. Lưới mạng không dây bao gồm các nút mạng không
dây. Chúng sử dụng các công nghệ mạng không dây như 802.11, 802.16… để tạo kết nối. Một
ví dụ của mô hình này là mạng thông tin trong hệ thống giao thông vehicle-to-vehicle. Trong
hệ thống này, nút mạng là các trạm bên đường và các thiết bị tham gia giao thông như ô tô, xe
máy. Các thiết bị này có giao tiếp không dây, chúng tự tạo kết nối và chia sẻ thông tin với
nhau. Mạng thông tin trong giao thông vehicle-to-vehicle là một trường hợp đặc biệt của mạng
không dây đặc biệt adhoc. Bên cạnh adhoc, mạng cảm biến không dây cũng là một dạng của
mạng không dây đa chặng. Mạng cảm biến bao gồm nhiều nút cảm biến được cài đặt trong
một phạm vi rộng, chúng thu thập thông tin, tự thiết lập kết nối không dây với nhau và truyền
thông tin về trạm gốc. Các mạng cảm biến không dây đa chặng được áp dụng trong rất nhiều
ứng dụng của đời sống như trong xây dựng nhà thông minh, theo dõi đối tượng, cảnh báo cháy
rừng, cảnh báo mực nước sông, cảm biến nhiệt độ, khám phá tài nguyên thiên nhiên nơi mà
1
con người không thể đặt chân đến được, chế tạo các sản phẩm y tế nhân tạo… Chính vì những
ứng dụng phổ biến trên tất cả các mặt đời sống xã hội mà mạng cảm biến không dây được
nhiều nhà khoa học quan tâm và nghiên cứu. Và mạng cảm biến không dây cũng là mô hình
mạng không dây đa chặng được sử dụng nghiên cứu trong luận án này.
Các mạng cảm biến đã có nhiều ứng dụng trong đời sống nhưng chúng vẫn còn phải đối
mặt với một số thách thức mà các mạng không dây khác không có như vấn đề bảo mật thông
tin, vấn đề nhiễu kênh truyền, vấn đề bị che khuất do địa hình, vấn đề năng lượng… Như ta đã
biết, mạng cảm biến không dây được tạo thành bởi các nút cảm biến, chúng tự thiết lập kết nối
với nhau thông qua hình thức không dây. Nguồn nuôi của các nút cảm biến này là pin với
dung lượng hạn chế. Tuổi thọ của các nút cảm biến nói riêng và của toàn mạng cảm biến nói
chung phụ thuộc vào việc sử dụng nguồn năng lượng này. Do đó, các thuật toán khi thiết kế
cho mạng cảm biến không dây cần chú trọng nhiều đến vấn đề năng lượng.
Có rất nhiều khía cạnh của kiến trúc mạng có thể được thiết kế để có năng lượng hiệu quả
như thiết kế ứng dụng tiết kiệm năng lượng, thiết kế giao thức điều khiển các chế độ hoạt động
của nút cảm biến, tắt tạm thời các nút cảm biến khi không cần thiết, thiết kế các giao thức định
tuyến tiết kiệm năng lượng… Trong các hướng tiếp cận đó thì thiết kế giao thức định tuyến
tiếp kiệm năng lượng là một hướng tiếp cận hiệu quả. Bởi vì, trong mạng cảm biến không dây,
dữ liệu truyền thông chiếm phần lớn nguồn tài nguyên năng lượng của mạng. Tối ưu được
giao thức định tuyến tức là tối ưu được việc truyền thông dữ liệu này. Do đó luận án tập trung
chủ yếu vào việc thiết kế các giao thức định tuyến tối ưu năng lượng đồng thời xây dựng mô
hình ứng dụng tổng hợp có thể ứng dụng vào thực tế.
Giao thức định tuyến trong mạng cảm biến không dây có thể được chia thành hai loại: các
giao thức tập trung dữ liệu và các giao thức truyền đa chặng về trạm. Giao thức tập trung dữ
liệu thể hiện cách thức các nút cảm biến không dây truyền dữ liệu thu thập được về trạm như
thế nào. Chúng có thể truyền trực tiếp về trạm hoặc truyền tới một nút cảm biến khác đóng vai
trò trung tâm của vùng cảm biến đó, nút này thường được gọi là clusterhead, sau đó các nút
clusterhead này sẽ tổng hợp dữ liệu và truyền về trạm. Một số giao thức thuộc loại này kể đến
là LEACH [1], LEACH-C [2], PEGASIS [3]… Bên cạnh các giao thức tập trung dữ liệu là các
giao thức truyền đa chặng. Khi các nút cảm biến truyền dữ liệu về trạm hay truyền đến các
clusterhead hay các nút clusterhead truyền về trạm chúng có thể truyền đơn chặng hoặc đa
2
chặng về trạm. Như đã phân tích ở trên thì truyền đa chặng sẽ cho khả năng mở rộng và hiệu
quảtốt hơn. Một số giao thức truyền đa chặng đã được phát triển như DSR [4], AODV [5],…
Với hai hướng tiếp cận định tuyến trong mạng cảm biến không dây này, các giao thức định
tuyến đa chặng sẽ quyết định dữ liệu được gửi về trạm theo đường nào do đó có ý nghĩa to lớn
trong việc chọn đường tiết kiệm năng lượng, cân bằng năng lượng giữa các nút cảm biến. Do
đó luận án tập trung vào việc nghiên cứu và phát triển các giao thức định tuyến truyền đa
chặng trong mạng cảm biến không dây nhằm đạt được mục tiêu tiết kiệm năng lượng của
mình.
Tình hình nghiên cứu trong và ngoài nƣớc
Tình hình trong nước:
Các nghiên cứu về sử dụng hiệu quả năng lượng trong mạng cảm biến không dây được đề
cập trong [6-9]. Trong [6, 7], các tác giả đã đề xuất các giao thức định tuyến đa chặng tiết
kiệm năng lượng, kéo dài thời gian sống của mạng cảm biến dựa vào năng lượng còn lại của
tất cả các nút cảm biến, năng lượng tiêu tốn của các nút lân cận, thực hiện thông báo để các
nút lân cận dừng hoạt động khi không cần thiết. Với các kỹ thuật này, các giao thức định tuyến
mà tác giả đề xuất đã thu được kết quả sử dụng năng lượng hiệu quả hơn so với các giao thức
trước đây.
Trong [8], tác giả đã trình bày phương pháp điều khiển công suất trong mạng cảm biến
không dây đa chặng, sau đó đề xuất giao thức định tuyến mới tiết kiệm năng lượng dựa trên
điều khiển công suất và chất lượng kênh truyền. Các kết quả mô phỏng trong [8] đã chỉ ra
thuật toán mới cho kết quả về năng lượng cũng như chất lượng đường truyền tốt hơn thuật
toán truyền thống AOMDV.
Trong [9], tác giả đã trình bày một giải pháp tối ưu giao định tuyến phân cấp (theo cluster)
cho mạng cảm biến không dây. Giao thức định tuyến phân cấp thường giải quyết vấn đề quy
mô lớn và truyền thông hiệu quả trong mạng không dây. Phương pháp này cũng có thể được
sử dụng để thực hiện hiệu quả năng lượng trong mạng cảm biến không dây đa chặng. Theo
báo cáo khoa học này, có nhiều thuật toán định tuyến cluster tiết kiệm năng lượng đã được đề
xuất. Nhưng phần lớn các thuật toán đó đều thực hiện qua mô phỏng (dạng heuristic), chưa có
3
mô hình hóa và phân tích bằng toán học. Lợi ích của các thuật toán này là đơn giản, tuy nhiên
chúng không đảm bảo các giải pháp tối ưu. Vì lý do đó, tác giả đã trình bày một mô hình giải
tích tối ưu để phân tích, đánh giávà thu được các giải pháp tối ưu cho các giao thức định tuyến
cluster trong mạng cảm biến.
Bên cạnh các kết quả đạt được về mặt học thuật, các nhà khoa học Việt Nam cũng đã có
các dự án hợp tác ứng dụng mạng cảm biến không dây vào thực tế như [10, 11, 89].
Từ những kết quả khảo sát trên ta thấy mạng cảm biến không dây đa chặng được khá nhiều
nhà khoa học trong nước quan tâm nghiên cứu và đã có những đóng góp nhất định về mặt
khoa học cũng như ứng dụng thực tiễn. Tuy nhiên các kết quả nghiên cứu và ứng dụng trong
nước vẫn còn khá hạn chế cả về số lượng và chất lượng.
Tình hình ngoài nước:
Với giao thức định tuyến đa chặng, trên thế giới đã có nhiều nghiên cứu về tối ưu năng
lượng như trong [5, 12 -18]. Trong [5], tác giả đề cập giao thức định tuyến AODV được thiết
kế đặc biệt cho mạng không dây đa chặng, sử dụng kỹ thuật mở rộng vòng ERS nhằm giảm
bớt bản tin dư thừa. Tuy nhiên khi sử dụng ERS thì hiệu quả về năng lượng thu được vẫn chưa
tốt. Tác giả tối ưu nhằm thu được hiệu quả sử dụng năng lượng bằng cách loại bỏ các bản tin
tìm đường dư thừa. Và bằng mô phỏng trên nhiều phần mềm mô phỏng khác nhau, tác giả đã
thu được kết quả khá tốt khi sử dụng năng lượng.
Trong [18], tác giả đã chỉ rõ, hầu hết các thiết bị không dây ngày nay hoạt động dựa vào
pin. Do đó vấn đề sử dụng năng lượng là cực kỳ quan trọng. Để kéo dài thời gian sống của
mạng, việc sử dụng năng lượng của mỗi nút phải được phân chia ngang bằng nhau và công
suất truyền cho mỗi kết nối phải là nhỏ nhất. Với mục đích đó, tác giả đã đề xuất giao thức
định tuyến mới vừa thực hiện cân bằng năng lượng giữa các nút mạng đồng thời chọn đường
với mức tiêu hao năng lượng ít nhất.
Ngoài ra một số tác giả đã nghiên cứu và đề xuất các ứng dụng của mạng cảm biến không
dây trong giám sát đối tượng như trong các tài liệu [19 -23].
4
Qua những khảo sát trên ta thấy, các nghiên cứu về lĩnh vực mạng cảm biến không dây đa
chặng ngoài nước đã đạt được nhiều thành tựu đáng kể về cả ý nghĩa khoa học và ứng dụng
thực tế. Tuy nhiên do ưu điểm và những ứng dụng trong mọi mặt đời sống mà mạng cảm biến
vẫn đang được các nhà khoa học tiếp tục nghiên cứu và thử nghiệm. Đặc biệt là ở Việt Nam,
khi các trang thiết bị còn yếu, các hệ thống tự động còn hạn chế thì mạng cảm biến không dây
vẫn là một đề tài đầy thách thức với các nhà khoa học.
Mục tiêu nghiên cứu của luận án
Mục tiêu thứ nhất của luận án là nghiên cứu và tối ưu các giao thức định tuyến đa chặng
trong mạng cảm biến không dây nhằm tiết kiệm năng lượng nhưng vẫn đảm bảo các thông số
truyền khác như băng thông, tỷ lệ truyền gói thành công. Các kỹ thuật định tuyến mới trình
bày trong luận án được thiết kế dựa trên giao thức định tuyến phổ biến trong mạng không dây
đa chặng là AODV. Giao thức này đã được trình bày chi tiết trong [24].
Định tuyến không dây đa chặng thường được chia thành 2 loại: định tuyến lại (reactive) và
định tuyến trước (proactive). Trong định tuyến reactive, một nút sẽ không lưu giữ một bảng
định tuyến hoàn chỉnh về toàn bộ thông tin đường đi của mạng, thay vào đó, khi muốn kết nối
đến một nút khác, nó sẽ phải thực hiện quá trình tìm đường đến đích. Một ví dụ điển hình của
định tuyến reactive là định tuyến Dynamic Source Routing (DSR). DSR được nghiên cứu và
phát triển bởi Johnson và Maltz [4]. Ngược lại với định tuyến reactive, định tuyến proactive
lưu thông tin về đường đi toàn mạng trong bảng định tuyến và bảng định tuyến này thường
xuyên được cập nhật. Ví dụ tiêu biểu của kiểu định tuyến này là định tuyến Optimized LinkState Routing (OLSR) đã được trình bày trong [25]. Với các đặc điểm hoạt động này, định
tuyến proactive thường được sử dụng cho các mạng có các nút mạng cố định, định tuyến
reactive thường được sử dụng với các kiểu mạng có các nút di chuyển, thường xuyên thay đổi
vị trí. Mặt khác, trong định tuyến proactive, các nút ngoài việc sử dụng bộ nhớ để lưu trữ
thông tin đường đi toàn mạng, chúng còn phải thường xuyên gửi bản tin để trao đổi duy trì
thông tin toàn mạng. Hoạt động này gây tốn tài nguyên mạng (tài nguyên băng thông, xử lý,
năng lượng mạng) do đó không thực sự thuận lợi khi triển khai cho mạng cảm biến không dây.
Trong mô hình mạng không dây đa chăng mà luận án nghiên cứu, các nút mạng là các thiết bị
cảm biến đứng yên. Với đặc điểm của nút mạng cảm biến và tính chất không thay đổi mô hình
mạng cần thiết phải có một giao thức định tuyến đáp ứng được cả 2 tiêu chí trên. Các giao
5
thức thuần reactive hay proactive đều không thực sự hiệu quả. Giao thức AODV được phát
triển từ giao thức DSR bằng cách duy trì thêm bảng định tuyến tại các nút giống như các định
tuyến proactive. Do đó giao thức AODV có các đặc điểm định tuyến theo yêu cầu như DSR,
không tiêu tốn tài nguyên hệ thống đồng thời không thường xuyên trao đổi bản tin duy trì định
tuyến như proactive nhưng vẫn có bảng thông tin đường đi sau mỗi lần tìm kiếm phù hợp cho
mạng có đặc điểm ít biến động. Chính vì những đặc điểm này mà luận án đã chọn AODV làm
cơ sở để phát triển các nghiên cứu của mình.
Mục tiêu thứ hai của luận án là nghiên cứu các thuật toán dự đoán vị trí đối tượng. Xây
dựng ứng dụng giám sát đối tượng theo vùng tiết kiệm năng lượng bằng cách tích hợp thuật
toán dự đoán vị trí đối tượng và các thuật toán định tuyến đề xuất.
Các vấn đề cần giải quyết của luận án
- Bằng cách sử dụng phương pháp làm tràn bản tin tìm kiếm, giao thức định tuyến AODV đã
cho kết quả tìm kiếm nhanh chính xác. Tuy nhiên với phương pháp này, số lượng các gói
tin dư thừa nhiều, dẫn đến hoạt động xử lý của các nút nhiều khi không cần thiết. Điều này
gây tiêu tốn tài nguyên hệ thống. Do đó, đưa ra một phương pháp định tuyến giảm thiểu
bản tin dư thừa, hạn chế số nút mạng tham gia định tuyến là một vấn đề cần giải quyết.
- Trong thuật toán định tuyến truyền thống, tuyến đường tốt nhất thường được chọn dựa trên
tiêu chí bước nhảy mạng. Các tiêu chí khác như băng thông, năng lượng, độ trễ chưa được
quan tâm. Điều đó dẫn đến tuyến đường được chọn có thể ngắn nhất về mặt bước nhảy
nhưng lại không được tối ưu về mặt năng lượng hay băng thông. Do đó, việc nghiên cứu đề
xuất giao thức kết hợp các tiêu chí kể trên để chọn đường tốt nhất là cần thiết.
- Trong quá trình định tuyến, tuyến đường tốt nhất thường là tuyến đường ngắn và đi qua
trung tâm của hệ thống mạng. Điều đó làm cho các nút nằm ở trung tâm thường xuyên
được chọn để chuyển tiếp bản tin, dẫn đến chúng nhanh chóng bị hết năng lượng và dừng
hoạt động. Khi một nút dừng hoạt động sẽ làm ảnh hưởng đến hoạt động của toàn mạng.
Đây là điều mà người quản trị không mong muốn. Do đó luận án cần nghiên cứu và đề xuất
phương pháp định tuyến mới để loại bỏ những tuyến đường có mức năng lượng không đảm
bảo nhằm mục đích cân bằng mức độ hoạt động của tất cả các nút mạng, kéo dài thời gian
sống của mạng.
6
- Trong mạng cảm biến không dây, khoảng cách giữa các nút cảm biến là không giống nhau.
Có những nút cách xa nhau hàng trăm mét, có nút chỉ cách nhau vài mét. Do đặc điểm dễ
triển khai nên các kết nối này đều dùng chung một mức công suất truyền, không quan tâm
tới khoảng cách giữa các nút cảm biến. Điều này gây tiêu tốn năng lượng không cần thiết.
Với mục tiêu tiết kiệm năng lượng trong mạng cảm biến thì điều khiển công suất truyền dữ
liệu, kết hợp điều khiển công suất vào định tuyến là một nhiệm vụ của luận án.
- Với các kết quả thu được từ việc tối ưu các giao thức định tuyến, luận án tiếp tục đặt mục
tiêu đề xuất ứng dụng giám sát đối tượng theo vùng. Tức là điều khiển bật các nút cảm biến
quanh đối tượng cần theo dõi, tắt các nút cảm biến khác nhằm tiết kiệm năng lượng toàn
mạng. Nhưng bật nút nào, tắt nút nào là một vấn đề cần làm rõ. Để làm được điều này, luận
án cần nghiên cứu các thuật toán dự đoán vị trí đối tượng đã có như Kalman, Kalman mở
rộng, Particle Filter. Xác định thuật toán nào là tốt và phù hợp cho mô hình. Từ đó xây
dựng mô hình ứng dụng giám sát đối tượng theo vùng kết hợp giữa thuật toán dự đoán và
các thuật toán định tuyến đã đề xuất.
Phạm vi nghiên cứu của luận án
- Tập trung nghiên cứu các giao thức định tuyến đa chặng trong mạng cảm biến không dây.
- Tập trung nghiên cứu các kỹ thuật điều khiển công suất trong mạng cảm biến không dây đa
chặng.
- Tập trung nghiên cứu các thuật toán dự đoán vị trí đối tượng. Đặc biệt là thuật toán bộ lọc
chất điểm.
- Tập trung nghiên cứu ứng dụng giám sát đối tượng sử dụng mạng cảm biến không dây.
Phƣơng pháp nghiên cứu
- Mô hình hóa giải tích các bài toán truyền thống, tiết kiệm năng lượng và điều khiển cấp
phát tài nguyên để đưa ra thuật giải khả thi.
- Tiến hành thiết kế, đề xuất thuật toán tối ưu, kiểm chứng bằng mô phỏng.
7
- Xem thêm -