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â

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYEN TRUNG DUNG NGHIÊN CUU PHAT TRIEN DINH TUYEN TIET KIEM NANG LUQNG CHO MANG CAM BIEN KHONG DAY LUAN AN TIEN Si KY THUAT VIEN THONG Hà Nội -2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRUONG ĐẠI HOC BACH KHOA HA NOI NGUYEN TRUNG DUNG 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 Si KY THUAT VIEN THONG 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 Loi cam on 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 CHUONG 1. TONG QUAN VE MANG CAM BIEN KHONG DAY 1.1 Cấu trúc mạng cảm biến không dây 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.2 Đặc điểm của cấu trúc mạng cảm biến 1.3 Kiến trúc giao thức mạng 1.4 Hai cau trúc đặc trưng của mạng cảm biến 1.1 Cau trúc phang | 1.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.1 Ứng dụng trong quân đội 1.2 Ung dụng trong môi trường 1.3 Ứng dụng trong chăm sóc sức khỏe 1.4 Ứng dụng trong gia đình 1.3 Một số vẫn đề thách thức kỹ thuật 1.1 Vấn đề lớp MAC 1.2 Vấn đề định tuyến 1.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 Phương pháp định tuyến mở rộng vòng Expanding Ring Search — ERS 2.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 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.2 Lam tràn bản tin tìm đường hiệu quả 2.3 Tiết kiệm năng lượng tìm kiếm mở rộng vòng 2.4 Lưu đồ thuật toán EERS 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.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 Đề 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.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.1 Kỹ thuật điều khiển công suất 2.2 Đề xuất phương pháp định tuyến dựa trên điều khiển công suất 2.3 Mô phỏng và đánh giá kết quả Trang 10 10 10 13 14 16 16 I? 19 20 21 22 22 22 22, 55 23 25 25 26 30 30 32 35 38 38 43 43 49 J1 56 56 Si 58 2.4 Kết luận CHUONG 3.TIẾT KIỆM NĂNG LƯỢNG TRONG MẠNG CẢM BIẾN KHONG DAY DA CHANG SU’ DUNG PHUONG PHAP UGC DOAN VI TRI CUA DOI TUQNG 3.1 Cơ sở lý thuyết toán học 3.1 Định lý xác suất Bayes 3.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 Hàm phân bố xác suất (Probability Distribution Function) 3.2 Hàm mật độ xác suất (Probability Density Function) 3.3 Kỳ vọng và phương sai cua | bién ngau nhién 3.1 Ky vong cua bién ngẫu r nhiên 3.1/32 Phương sai của biến ngẫu nhiên 3.4 Hàm phân phối xác suất Gaussian — Hàm phân phối chuẩn 3.5 Tiến trình Markov 3.6 Mô hình hóa hệ thống không gian trạng thái động 3.7 Tiếp cận Bayes 3.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.1 Bộ lọc Kalman 3.2 Bộ lọc Kalman mở rộng 3.1 Những giới hạn của mô hình tuyến tính 3.2 Khai triển chuỗi Taylor 3.3 Thuật toán bộ lọc chất diém (Particle Filter) 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.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 Lấy mâu quan trọng (Importance Sampling) 3.4 Lay mau quan trong tuan tu (Sequential Importance Sampling — SIS) 3.5 Vấn đề lựa chọn hàm mật độ để xuất 3.6 Vấn đề thoái hóa mẫu và giải pháp lấy mẫu lai (Resampling) 3.7 Thuật toán bộ lọc chất điểm tông quát (Generic Particle Filter — GPF) 3.8 Thuật toán lấy mẫu lại quan trọng tuần tự (Sequential Importance Resampling — SIR) 3.9 M6 phong thuat toan SIR 3.4 Ung dung gidm sat déi tượng trong mạng cảm biến không dây sứ dụng bộ lọc chất điểm PE 3.1 Mô hình hóa bài toán 3.2 Đề xuất phương pháp thực hiện bộ lọc chất điểm 3.1 Pha khởi tạo N chất điểm 3.2 Pha lan truyền chất điểm 3.3 Pha tính toán trọng số 3.4 Kết quả mô phỏng 3.5 Đề xuất mô hình giám sát theo vùng ii 65 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 KÉT LUẬN CHUNG TÀI LIỆU THAM KHẢO DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BÓ LIÊN QUAN TRỰC TIẾP CỦA LUẬN ÁN DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BÓ LIEN QUAN GIAN TIEP CUA LUAN AN 11 108 110 116 117 124 132 133 ABR ADC AODV AOMDV BS CNI CSMA/CA DSR EERS EKF ERS GPE KF LEACH MAC NS2 PDR PF PRP RDC RF RMS ROF RREP RREQ SIR SIS TIL WSN DANH MUC CAC CHU VIET TAT Avoid Bad Route Analog-to-Digital Adhoc On-demand Distance Vector Adhoc On-demand Multipath Distance Vector Base Station Collecting Neighbors’ Information Carrier Sense Multiple Access/ Collision Avoidance Dynamic Source Routing Efficient Expanding Ring Search Extended Kalman Filter Expanding Ring Search Generic Particle Filter Kalman Filter Low Energy Adaptive Hierarchy Media Access Control Network Simulator 2 Packet Delivery Ratio Particle Filter Power Control Combined with Routing Protocol Routing dual criterion Radio Frequency Root-Mean-Square Reducing the Overhead of Flooding Route Reply Route Request Sequential Importance Resampling Sequential Importance Sampling Time to Live Wireless Sensor Network iv Clustering Dinh 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 Định tuyến vector khoảng cách đa đường theo yêu cầu Trạm gốc Pha thu thập thông tin nút lân cận trong giao thức định tuyến EERS Cảm biến sóng mang đa truy cập/ tránh xung đột Định tuyến theo nguồn Định tuyến tìm kiếm mở rộng vòng tối ưu Bộ lọc Kalman mở rộng Định tuyến tìm kiếm mở rộng vòng Bộ lọc chất điểm tổng quát Bộ lọc Kalman Định tuyến phân vùng tiết kiệm năng lượng Điều khiển truy nhập đường truyền Phần mềm mô phỏng mạng Tỷ lệ truyền gói tin thành công Bộ lọc chất điểm Định tuyến dựa trên điều khiển công suất Định tuyến hai điều kiện Sóng vô tuyến Độ lệch căn phương trung bình Pha giảm thiểu bản tin dư thừa trong giao thức định tuyến EERS Bản tin trả lời chứa thong tin tuyến đường trong định tuyến Bản tin tìm đường Lây mẫu lại quan trọng tuần tự Lấy mẫu quan trọng tuần tự Thời gian sống Mạng cảm biên không dây F(X) fix) Pi E(X) V(X) M Pross Phụ max Pren Pinar P x LP. sent LPiny 1 n K t T N DANH MUC CAC KY HIEU 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 & Trang 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 +, Ước lượng tiên nghiệm của x, Hiệp phương sai của lỗi ước lượng của §Ƒ Hiệp phương sai của lỗi ước lượng của Ÿ- 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ị x¡ của biến ngẫu nhiên X Kỳ vọng của biến ngẫu r 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 DANH MỤC CÁC BẢNG Bảng 2.

Các thông số mô phỏng chung Bảng 2. Các thông só mô phỏng AODV và PRP Bảng 3. Ví dụ về kết quả khai triển Taylor Bảng 3. Thông só mô phỏng ứng dụng giám sát theo vùng vi Trang 39 59 80 111 DANH MUC CAC HINH VE, DO THI Hình 1.

Một mạng cảm biến không dây đơn giản Hình 1. Cấu tạo nút cảm biến Hình 1. Kiến trúc giao thức mạng cảm biến Hình 1. Cấu trúc phẳng của mạng cảm biến Hình 1.

Cấu trúc tầng của mạng cảm biến Hình I. Câu trúc mạng phân cấp chức năng theo lớp Hình 2. Luu dé thuật toán của nút nguồn gửi gói tin RREQ Hình 2. Lưu đồ thuật toán xử lí ở nút trung gian Hình 2.

Ví dụ cơ chế tìm kiếm mở rộng vòng (Expanding Ring Search) Hình 2. 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. Đề 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. Lưu đồ thuật toán EERS Hình 2.

So sánh thời gian sống của mạng giữa AODV, ERS và EERS Hình 2. So sánh tỷ lệ truyền gói thành công PDR giữa EERS, ERS và AODV Hình 2.