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ỳ

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

1
10

10
13
14
16
16
17
19
20
21
22
22
22

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
49
đường đi tốt nhất - Routing Dual Criterion (RDC)
2.2.3 Mô phỏng kết quả
51
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
56
suất
2.3.1 Kỹ thuật điều khiển công suất
56
2.3.2 Đề xuất phương pháp định tuyến dựa trên điều khiển công suất
57
2.3.3 Mô phỏng và đánh giá kết quả
58

i


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
66
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

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 –90
GPF)
3.3.8 Thuật toán lấy mẫu lại quan trọng tuần tự (Sequential Importance91
Resampling – SIR)
3.3.9 Mô phỏng thuật toán SIR
92
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

67
67
68
68
68
69
69
70
70
71
73

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

3


DANH MỤC CÁC CHỮ VIẾT TẮT
ABR
ADC
AODV

Avoid Bad Route
Định tuyến loại bỏ tuyến đường xấu
Analog-to-Digital
Bộ chuyển đổi tương tự số
Adhoc On-demand Distance Vector
Định tuyến vector khoảng cách theo
yêu cầu


Bộ lọc Kalman mở rộng
ERS
Expanding Ring Search
Định tuyến tìm kiếm mở rộng vòng
GPF
Generic Particle Filter
Bộ lọc chất điểm tổng quát
KF
Kalman Filter
Bộ lọc Kalman
LEACH
Low Energy Adaptive Clustering
Định tuyến phân vùng tiết kiệm
Hierarchy
năng lượng
MAC
Media Access Control
Điều khiển truy nhập đường truyền
NS2
Network Simulator 2
Phần mềm mô phỏng mạng PDR
Packet Delivery Ratio
Tỷ lệ truyền gói tin thành công PF
Particle Filter
Bộ lọc chất điểm
PRP
Power Control Combined with Routing
Định tuyến dựa trên điều khiển
công suất
Protocol

Mạng cảm biến không dây

5


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

Tc
n
K
t
T
N

t

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

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
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
RDC mô phỏng 2

47
50
52

49
51

53 và
53
54
55 và
56
60
60
61
61
62
62


vii


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ô
63
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ô
63
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ô

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
97
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
97
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
98
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
98
Hình 3.18. Ví dụ về lan truyền đám mây chất điểm
102

8


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
104
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
104
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
105
khi mô phỏng theo thời gian
Hình 3.22. Ví dụ ứng dụng giám sát theo vùng
107
Hình 3.23. Ví dụ ứng dụng giám sát theo toàn bộ mạng
109
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
110

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

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

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
2


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

3


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