Luận án Tiến sĩ Kỹ thuật viễn thô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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:146

Thêm vào BST

Báo xấu

20
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của đề tài 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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Kỹ thuật viễn thô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

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 Trang MỞ ĐẦU 1 CHƢƠNG 1. TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY 10 1.1 Cấu trúc mạng cảm biến không dây 10 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 10 1.1.2 Đặc điểm của cấu trúc mạng cảm biến 13 1.1.3 Kiến trúc giao thức mạng 14 1.1.4 Hai cấu trúc đặc trưng của mạng cảm biến 16 1.1.4.1 Cấu trúc phẳng 16 1.1.4.2 Cấu trúc phân tầng 17 1.2 Ứng dụng mạng cảm biến không dây 19 1.2.1 Ứng dụng trong quân đội 20 1.2.2 Ứng dụng trong môi trường 21 1.2.3 Ứng dụng trong chăm sóc sức khỏe 22 1.2.4 Ứng dụng trong gia đình 22 1.3 Một số vấn đề thách thức kỹ thuật 22 1.3.1 Vấn đề lớp MAC 22 1.3.2 Vấn đề định tuyến 23 1.3.3 Vấn đề năng lượng 23 CHƢƠNG 2.TỐI ƢU ĐỊNH TUYẾN ĐA CHẶNG TIẾT KIỆM NĂNG 25 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 25 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 – 26 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 30 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 30 mạng 2.1.2.2 Làm tràn bản tin tìm đường hiệu quả 32 2.1.2.3 Tiết kiệm năng lượng tìm kiếm mở rộng vòng 35 2.1.2.4 Lưu đồ thuật toán EERS 38 2.1.2.5 Mô phỏng và đánh giá 38 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 43 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 43 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 66 3.1.1 Định lý xác suất Bayes 67 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 67 nhiên 3.1.2.1 Hàm phân bố xác suất (Probability Distribution Function) 67 3.1.2.2 Hàm mật độ xác suất (Probability Density Function) 68 3.1.3 Kỳ vọng và phương sai của biến ngẫu nhiên 68 3.1.3.1 Kỳ vọng của biến ngẫu nhiên 68 3.1.3.2 Phương sai của biến ngẫu nhiên 69 3.1.4 Hàm phân phối xác suất Gaussian – Hàm phân phối chuẩn 69 3.1.5 Tiến trình Markov 70 3.1.6 Mô hình hóa hệ thống không gian trạng thái động 70 3.1.7 Tiếp cận Bayes 71 3.1.8 Một số thuật toán theo vết dựa trên tiếp cận Bayes 73 3.2 Sơ lược về một số thuật toán dự đoán vị trí 73 3.2.1 Bộ lọc Kalman 74 3.2.2 Bộ lọc Kalman mở rộng 78 3.2.2.1 Những giới hạn của mô hình tuyến tính 78 3.2.2.2 Khai triển chuỗi Taylor 79 3.2.3 Kết luận 80 3.3 Thuật toán bộ lọc chất điểm (Particle Filter) 81 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 81 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 82 3.3.3 Lấy mẫu quan trọng (Importance Sampling) 83 3.3.4 Lấy mẫu quan trọng tuần tự (Sequential Importance Sampling – 84 SIS) 3.3.5 Vấn đề lựa chọn hàm mật độ đề xuất 88 3.3.6 Vấn đề thoái hóa mẫu và giải pháp lấy mẫu lại (Resampling) 89 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 Importance 91 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 99 bộ lọc chất điểm PF 3.4.1 Mô hình hóa bài toán 99 3.4.2 Đề xuất phương pháp thực hiện bộ lọc chất điểm 100 3.4.2.1 Pha khởi tạo N chất điểm 100 3.4.2.2 Pha lan truyền chất điểm 101 3.4.2.3 Pha tính toán trọng số 102 3.4.2.4 Kết quả mô phỏng 103 3.5 Đề xuất mô hình giám sát theo vùng 105 ii
3.6 Mô hình giám sát toàn mạng 108 3.7 Mô phỏng và đánh giá kết quả 110 3.8 Kết luận 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 Avoid Bad Route Định tuyến loại bỏ tuyến đường xấu ADC Analog-to-Digital Bộ chuyển đổi tương tự số AODV Adhoc On-demand Distance Vector Định tuyến vector khoảng cách theo yêu cầu AOMDV Adhoc On-demand Multipath Distance Định tuyến vector khoảng cách đa Vector đường theo yêu cầu BS Base Station Trạm gốc CNI Collecting Neighbors’ Information Pha thu thập thông tin nút lân cận trong giao thức định tuyến EERS CSMA/CA Carrier Sense Multiple Access/ Cảm biến sóng mang đa truy cập/ Collision Avoidance tránh xung đột DSR Dynamic Source Routing Định tuyến theo nguồn EERS Efficient Expanding Ring Search Định tuyến tìm kiếm mở rộng vòng tối ưu EKF Extended Kalman Filter 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 Protocol suất RDC Routing dual criterion Định tuyến hai điều kiện RF Radio Frequency Sóng vô tuyến RMS Root-Mean-Square Độ lệch căn phương trung bình ROF Reducing the Overhead of Flooding Pha giảm thiểu bản tin dư thừa trong giao thức định tuyến EERS RREP Route Reply Bản tin trả lời chứa thông tin tuyến đường trong định tuyến RREQ Route Request Bản tin tìm đường SIR Sequential Importance Resampling Lây mẫu lại quan trọng tuần tự SIS Sequential Importance Sampling Lấy mẫu quan trọng tuần tự TTL Time to Live Thời gian sống WSN Wireless Sensor Network Mạng cảm biến không dây iv
DANH MỤC CÁC KÝ HIỆU 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 δi Hàm xung Delta ck Trạng thái của hệ thống tại thời điểm k xt Trạng thái của hệ thộng tại thời điểm t yt Tín hiệu đo đạc của hệ thống tại thời điểm t gt Hàm chuyển tại thời điểm t ht Hàm quan sát tại thời điểm t wt Nhiễu xử lý tại thời điểm t vt Nhiễu quan sát tại thời điểm t ut Đầu vào của hệ thống tại thời điểm t xˆ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 Pt  Hiệp phương sai của lỗi ước lượng của xˆt Kt Ma trận hệ số khuếch đại Kalman X Biến ngẫu nhiên của hàm phân bố xác suất F(X) Hàm phân bố xác suất của biến ngẫu nhiên X f(x) Hàm mật độ xác suất của biến ngẫu nhiên X pi Xác suất tương ứng của các giá trị xi của biến ngẫu nhiên X E(X) Kỳ vọng của biến ngẫu nhiên X V(X) Phương sai của biến ngẫu nhiên X M Chi phí tuyến đường Ploss Công suất tiêu hao Ptx_max Công suất truyền lớn nhất Psen Công suât nhạy thu Pmar Công suất dự trữ Ptx Công suất truyền LPsent Năng lượng còn lại của nút cảm biến trong thuật toán PRP LPthr Ngưỡng năng lượng còn lạicủa nút cảm biến trong thuật toán PRP Tc Thời gian đợi bản tin trả lời n Số nút cảm biến trong mạng K Độ 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 t Thời gian hiện tại T Mốc thời gian trong tương lai N Số chất điểm v
DANH MỤC CÁC BẢNG Trang Bảng 2.1. Các thông số mô phỏng chung 39 Bảng 2.2. Các thông số mô phỏng AODV và PRP 59 Bảng 3.1. Ví dụ về kết quả khai triển Taylor 80 Bảng 3.2. Thông số mô phỏng ứng dụng giám sát theo vùng 111 vi
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Trang Hình 1.1. Một mạng cảm biến không dây đơn giản 11 Hình 1.2. Cấu tạo nút cảm biến 12 Hình 1.3. Kiến trúc giao thức mạng cảm biến 15 Hình 1.4. Cấu trúc phẳng của mạng cảm biến 17 Hình 1.5. Cấu trúc tầng của mạng cảm biến 17 Hình 1.6. Cấu trúc mạng phân cấp chức năng theo lớp 18 Hình 2.1. Lưu đồ thuật toán của nút nguồn gửi gói tin RREQ 27 Hình 2.2. Lưu đồ thuật toán xử lí ở nút trung gian 28 Hình 2.3. Ví dụ cơ chế tìm kiếm mở rộng vòng (Expanding Ring Search) 29 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 31 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 34 Hình 2.6. Lưu đồ thuật toán EERS 37 Hình 2.7. So sánh thời gian sống của mạng giữa AODV, ERS và EERS 40 Hình 2.8. So sánh tỷ lệ truyền gói thành công PDR giữa EERS, ERS và AODV 41 Hình 2.9. So sánh về thông lượng mạng khi sử dụng định tuyến EERS, ERS và 42 AODV Hình 2.10. Ví dụ hoạt động của ABR 44 Hình 2.11. Thuật toán ABR thực hiện tại nút nguồn 45 Hình 2.12. Thuật toán ABR thực hiện tại nút trung gian 46 Hình 2.13. Thuật toán ABR tại nút đích 47 Hình 2.14. Sự thay đổi giá trị của biến rq_min_energy và rp_energy trong thuật 49 toán RDC Hình 2.15. Ví dụ về hoạt động của thuật toán RDC 50 Hình 2.16. Quá trình duy trì update thông tin định tuyến trong thuật toán RDC 51 Hình 2.17. So sánh thời gian sống của mạng giữa AODV, ERS, EERS, ABR và 52 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 53 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à 53 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à 54 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 55 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à 56 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 60 Hình 2.24. So sánh thông lượng của mạng khi sử dụng AODV và PRP 60 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 61 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ô 61 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ô 62 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ô 62 phỏng 90 nút mạng 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ô 64 phỏng 120 nút mạng Hình 3.1. Sơ đồ tiếp cận Bayes 73 Hình 3.2. Đường đặc tuyến Von-Ampe 79 Hình 3.3. Kết quả của thuật toán SIS ứng với N = 100 mẫu 87 Hình 3.4. Kết quả của thuật toán SIS ứng với N = 1000 mẫu 87 Hình 3.5. Kết quả của thuật toán SIS ứng với N = 5000 mẫu 88 Hình 3.6. Kết quả thuật toán SIR ứng với N = 100, t = 50s 92 Hình 3.7. Kết quả thuật toán SIR ứng với N = 1000, t = 50s 93 Hình 3.8. Kết quả thuật toán SIR ứng với N = 5000, t = 50s 93 Hình 3.9. Kết quả thuật toán SIR ứng với N = 100, t = 150s 94 Hình 3.10. Kết quả thuật toán SIR ứng với N = 1000, t = 150s 94 Hình 3.11. Kết quả thuật toán SIR ứng với N = 5000, t = 150s 95 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 96 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 96 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 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 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, 104 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.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 111 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ô 112 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 112 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ô 113 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
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 113 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ô 114 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 114 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ô 115 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
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 Link- State 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