Tóm tắt 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:27

Thêm vào BST

Báo xấu

17
lượt xem 2
download

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

MỤc đích nghiên cứu của đề tài là phân tích thiết kế giao thức định tuyến tiết kiệm năng lượng trong mạng cảm biến không dây; nghiên cứu, đề xuất thuật toán ước lượng vị trí đối tượng sử dụng trong mạng cảm biến không dây; đề xuất mô hình giám sát đối tượng theo vùng dựa trên thuật toán ước đoán vị trí và giao thức định tuyến đề xuất nhằm tiết kiệm năng lượng.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt 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 Chuyên ngành: Kỹ thuật Viễn thông Mã số: 62520208 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG Hà Nội – 2014
Công trình được hoàn thành tại: Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: PGS.TS NGUYỄN VĂN ĐỨC Phản biện 1: PGS.TS Lê Nhật Thăng Phản biện 2: PGS.TS Trương Vũ Bằng Giang Phản biện 3: PGS.TS Nguyễn Huy Hoàng Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ cấp Trường họp tại: Trường Đại học Bách khoa Hà Nội Vào hồi………giờ, ngày……tháng…….năm…….. Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu – Trường ĐHBK Hà Nội 2. Thư viện Quốc gia
MỞ ĐẦU 1.1. Mục đích nghiên cứu 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ế. Mục tiêu nghiên cứu của luận án - Phân tích thiết kế giao thức định tuyến tiết kiệm năng lượng trong mạng cảm biến không dây. - Nghiên cứu, đề xuất thuật toán ước lượng vị trí đối tượng sử dụng trong mạng cảm biến không dây. Đề xuất mô hình giám sát đối tượng theo vùng dựa trên thuật toán ước đoán vị trí và giao thức định tuyến đề xuất nhằm tiết kiệm năng lượng. Các vấn đề cần giải quyết của luận án - Đề xuất phương pháp định tuyến giảm thiểu gói tin dư thừa, hạn chế số nút mạng tham gia định tuyến. - Đề xuất phương pháp định tuyến kết hợp nhiều điều kiện để chọn đường đi tốt nhất. - Đề xuất phương pháp định tuyến loại bỏ tuyến đường có mức năng lượng không đảm bảo. - Đề xuất phương pháp định tuyến kết hợp điều khiển công suất. - Đề xuất thuật toán ước lượng, dự đoán vị trí đối tượng sử dụng trong mạng cảm biến không dây. - 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 - Tập trung nghiên cứu các giao thức định tuyến 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. - 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. Các đóng góp của luận án - Đề xuất giao thức định tuyến tiết kiệm năng lượng:  Đị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 Efficient Expanding Ring Search (EERS)  Định tuyến tiết kiệm năng lượng tối ưu chi phí tìm đường và cân bằng năng lượng Routing Dual Criterion (RDC) và Avoid Bad Route (ABR).  Định tuyến tiết kiệm năng lượng kết hợp điều khiển công suất. - Xây dựng ứng dụng giám sát đối tượng theo vùng dựa trên thuật toán dự đoán vị trí đối tượng Particle Filter và các thuật toán định tuyến đề xuất:  Đề xuất phương thức thực hiện thuật toán bộ lọc chất điểm mới.  Đề xuất mô hình giám sát đối tượng theo vùng tiết kiệm năng lượng. 1
1.2. Cấu trúc nội dung của luận án Nội dung của luận án bao gồm bốn chương. Trong đó toàn bộ đóng góp khoa học của luận án thể hiện ở các nội dung đề xuất và thực hiện trong chương 2 và chương 3. Với các nội dung cụ thể: - Chương 1: Trình bày tổng quan về mạng cảm biến không dây đa chặng, những khó khăn và ứng dụng của nó trong cuộc sống. - Chương 2: Trình bày các giao thức định tuyền tiết kiệm năng lượng mới: định tuyến mở rộng vòng tối ưu, định tuyến dựa vào năng lượng và điều khiển công suất. - Chương 3: Trình bày nghiên cứu về các thuật toán ước lượng, dự đoán vị trí đối tượng. Đề xuất phương pháp thực hiện thuật toán bộ lọc chất điểm mới ứng dụng trong mạng cảm biến không dây. Đề xuất mô hình giám sát theo vùng bằng cách điều khiển bật tắt các nút cảm biến dựa trên thuật toán ước lượng, dự đoán vị trí đối tượng. - Chương 4: Kết luận và hướng phát triển tiếp cho luận án. CHƢƠNG 1 TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY ĐA CHẶNG 1.1. Giới thiệu Mạng cảm biến không dây đa chặng là mạng bao gồm nhiều nút cảm biến nhỏ giao tiếp thông qua các kết nối không dây, các nút cảm biến này cảm nhận, tập trung dữ liệu, phân tích tính toán trên các dữ liệu thu thập được sau đó truyền đơn chặng hoặc đa chặng về trạm điều khiển để tiếp tục phân tích và đưa ra các quyết định toàn cục về môi trường xung quanh. Trong hình 1.1, các nút cảm biến được phân bố trong trường cảm ứng. Mỗi nút cảm biến có khả năng thu thập dữ liệu và định tuyến đa chặng đến các điểm xử lý tập trung gọi là nút sink. Dữ liệu được định tuyến lại đến các điểm xử lý tập trung bởi một cấu trúc đa chặng như hình vẽ. Các điểm xử lý tập trung có thể giao tiếp với các nút quản lý nhiệm vụ (task manager node) qua mạng Internet hoặc vệ tinh. Hình 1.1. Ví dụ về mạng cảm biến không dây đa chặng đơn giản 1.2. Cấu trúc mạng cảm biến không dây đa chặng 1.2.1. Đặc điểm của cấu trúc mạng cảm biến Mạng cảm biến bao gồm một số lượng lớn các nút cảm biến, các nút cảm biến có giới hạn và rằng buộc về tài nguyên đặc biệt là năng lượng rất khắt khe. Do đó, cấu trúc mạng mới có đặc điểm rất khác với các mạng truyền thống. - Khả năng chịu lỗi cao. - Khả năng mở rộng. - Giá thành sản xuất thấp. - Rằng buộc về phần cứng: Kích thước nhỏ, tiêu thụ năng lượng thấp, khả năng tự hoạt động, thích nghi với môi trường… - Môi trường hoạt động: Các nút cảm biến được thiết lập dày đặc, rất gần hoặc trực tiếp bên trong các hiện tượng để quan sát. vì thế chúng thường làm việc mà không cần giám sát ở những vùng xa xôi. - Phương tiện truyền dẫn: Ttruyền không dây đa chặng. Các đường kết nối này có thể tạo nên bởi sóng vô tuyến, hồng ngoại hoặc những phương tiện quang học. Hiện tại nhiều phần cứng của các nút cảm biến dựa vào thiết kế mạch RF. - Cấu hình mạng cảm biến: Có hàng trăm đến hàng nghìn nút được triển khai trên trường cảm biến. Chúng được triển khai trong vòng hàng chục mét mỗi nút. 2
- Sự tiêu thụ năng lượng: Nút cảm biến không dây được trang bị pin để hoạt động. Thời gian sống của các nút cảm biến phụ thuộc mạnh vào thời gian sống của pin. Vì vậy việc duy trì và quản lý nguồn năng lượng đóng một vai trò quan trọng. 1.2.2. Kiến trúc giao thức mạng Kiến trúc giao thức mạng cảm biến được trình bày như hình 1.2. Kiến trúc này bao gồm các lớp và các mặt phẳng quản lý. Các mặt phẳng quản lý này làm cho các nút có thể làm việc cùng nhau theo cách có hiệu quả nhất, định tuyến dữ liệu trong mạng cảm biến di động và chia sẻ tài nguyên giữa các nút cảm biến. Phần quản lý nhiệm vụ Phần quản lý di động Phần quản lý năng lƣợng Lớp ứng dụng Lớp truyền tải Lớp mạng Lớp liên kết dữ liệu Lớp vật lý Hình 1.2. Kiến trúc giao thức mạng cảm biến 1.2.3. Hai cấu trúc đặc trƣng của mạng cảm biến 1.2.3.1. Cấu trúc phẳng Trong cấu trúc phẳng (hình 1.3), tất cả các nút đều ngang hàng và đồng nhất trong hình dạng và chức năng. Các nút giao tiếp với điểm xử lý tập trung trực tiếp hoặc qua đa chặng sử dụng các nút ngang hàng làm bộ tiếp sóng. 1.2.3.2. Cấu trúc phân tầng Trong cấu trúc phân tầng (hình 1.4), mạng cảm biến được chia thành các vùng được gọi là cụm. Các nút cảm biến trong cụm gửi dữ liệu đơn chặng hay đa chặng tùy thuộc vào kích thước của cụm đến một nút định sẵn trong cụm, thường gọi là nút chủ (cluster head). Sau đó các nút chủ sẽ gửi đơn chặng hoặc đa chặng dữ liệu tập trung được đến nút xử lý tập trung. Trong cấu trúc này, các nút tạo thành một hệ thống cấp bậc mà ở đó mỗi nút ở một mức độ xác định thực hiện các nhiệm vụ đã định sẵn. Trong cấu trúc tầng thì chức năng cảm nhận, tính toán và phân phối dữ liệu không đồng đều giữa các nút. Những chức năng này có thể theo cấp, cấp thấp nhất thực hiện nhiệm vụ cảm nhận, cấp giữa thực hiện tính toán, cấp trên cùng thực hiện phân phối dữ liệu như hình 1.5. Nút chủ (Cluster Head) Nút cảm biến Nút cảm biến Điểm xử lý tập trung Điểm xử lý tập trung Hình 1.3. Cấu trúc phẳng của mạng cảm biến Hình 1.4. Cấu trúc tầng của mạng cảm biến 3
Internet Nút cảm biến Cấp 2: Phân phối Cấp 1: Tính toán Cấp 0: Cảm nhận Hình 1.5. Cấu trúc mạng phân cấp chức năng theo lớp 1.3. Ứng dụng mạng cảm biến không dây đa chặng 1.3.1. Ứng dụng trong quân đội Mạng cảm biến không dây có thể là một phần tích hợp trong hệ thống điều khiển quân đội, giám sát, giao thiếp, tính toán thông minh, trinh sát, theo dõi mục tiêu. - Giám sát lực lượng, trang thiết bị và đạn dược. - Giám sát chiến trường. - Giám sát địa hình và lực lượng quân định. - Phát hiện và thăm dò các vụ tấn công bằng hóa học, sinh học và hạt nhân. 1.3.2. Ứng dụng trong môi trƣờng - Phát hiện cháy rừng. - Phát hiện lũ lụt thiên tai. - Giám sát thú, động thực vật quý hiếm. - Theo dõi các điều kiện môi trường ảnh hưởng đến cuộc sống. - Thăm dò, nghiên cứu ở những nơi con người không đặt chân đến được. 1.3.3. Ứng dụng trong chăm sóc sức khỏe Giám sát bệnh nhân, các triệu chứng, quản lý thuốc trong bệnh viện, giám sát sự chuyển động và xử lý bên trong của côn trùng hoặc các động vật nhỏ khác, theo dõi bác sĩ và bệnh nhân trong bệnh viện. 1.3.4. Ứng dụng trong gia định Đo nhiệt độ và các thông số môi trường khác. Phát hiện sự dịch chuyển trong nhà, hỗ trợ trong việc thiết kế các tòa nhà thông minh, tự động.. CHƢƠNG 2 TỐI ƢU ĐỊNH TUYẾN ĐA CHẶNG TIẾT KIỆM NĂNG LƢỢNG 2.1. Giới thiệu chƣơng Chương này đề xuất các giao thức định tuyến đa chặng tiết kiệm năng lượng. Từ giao thức kinh điển AODV, thực hiện thay đổi cách thức gửi và nhận bản tin định tuyến, thay đổi thông số điều kiện tìm đường đi tốt nhất, luận án đề xuất giao thức định tuyến mở rộng vòng tối ưu EERS, định tuyến loại bỏ tuyến đường có mức năng lượng thấp ABR, định tuyến sử dụng hai điều kiện chọn đường RDC và định tuyến kết hợp điều khiển công suất PRP. 2.2. Phƣơng pháp định tuyến tiết kiệm năng lƣợng dựa trên giảm thiểu các gói tin dƣ thừa Giao thức AODV sử dụng phương pháp làm tràn gói tin để tìm đường. Quá trình làm tràn là quá trình một nút gửi thông tin đến toàn bộ các nút trên mạng. Đây là một phương pháp đơn giản vì nó không yêu cầu xử lý tính toán nhiều và mỗi nút không cần duy trì bảng định tuyến của riêng mình. Phương pháp này cũng giảm thời gian trễ trong quá trình tìm đường đi, do thông tin được gửi đi toàn mạng nên việc tìm kiếm có thể tìm được đường đi nhanh chóng. 2.2.1. Phƣơng pháp định tuyến mở rộng vòng – Expanding Ring Search (ERS) Với phương pháp làm tràn, khi một nút cần tìm đường tới đích, nút đó sẽ gửi bản tin ra toàn bộ mạng để 4
tìm kiếm. Điều này dẫn đến tất cả các nút trên mạng tham gia vào quá trình tìm đường gây tiêu tốn năng lượng. Để khắc phục nhược điểm này, giao thức ERS sử dụng cơ chế tìm kiếm mở rộng vòng để tìm đường. Với cơ chế này mỗi khi nút muốn tìm đường đi đến một nút khác, thay vì phải thực hiện làm tràn ngay, nó sẽ quảng bá một gói tin tìm đường RREQ trong phạm vi hop. Gói tin RREQ này có giá trị thời gian sống (Time To Live - ) gán bằng , sau mỗi lần được chuyển tiếp qua một nút, giá trị này được giảm đi một đơn vị và bị hủy khi đạt giá trị bằng không. Các nút trung gian nhận được gói tin RREQ này mà không có thông tin về nút đích, nó sẽ chuyển tiếp gói tin RREQ này sang các nút khác. Nếu nút trung gian có thông tin về nút đích, nó sẽ gửi trả lại một gói tin Route Reply (RREP) để thông báo cho nút nguồn biết đường đi đến nút đích. Trong quá trình gửi gói tin RREQ, các nút sẽ lưu gói tin RREQ này trong một bộ đệm trước khi chuyển tiếp gói tin RREQ đi. Nếu nó nhận được một gói RREQ khác trùng với gói tin trong bộ đệm, nó sẽ xóa gói tin đi mà không chuyển tiếp. Việc làm này tránh cho các nút phải gửi các bản tin trùng lặp. Nút nguồn sau khi gửi bản tin RREQ sẽ đợi trong một khoảng thời gian xác định. Nếu sau khoảng thời gian này nút nguồn không nhận lại được bản tin RREP phản hồi, nó xác nhận là không tìm thấy đường đi và lại thực hiện lại quá trình tìm đường nhưng tăng giá trị trong gói tin RREQ lên đơn vị. Nếu sau nhiều lần tăng gửi RREQ không tìm được đường đi và lớn hơn một giá trị xác định, nút sẽ thực hiện quá trình làm tràn cho toàn mạng như ban đầu. 2.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) Cơ chế ERS gặp phải nhược điểm: nếu mạng có bán kính lớn và khi nút nguồn nút đích ở xa nhau thì nút nguồn sẽ phải thực hiện quá trình tìm đường mở rộng vòng nhiều lần. Điều này dẫn đến việc các nút trong vùng tìm kiếm sẽ phải tiêu tốn năng lượng nhiều hơn. Để giải quyết vấn đề này, luận văn đề xuất giao thức tìm kiếm mở rộng vòng tối ưu EERS với phương pháp tối ưu các lần tìm kiếm mở rộng sau dựa trên các lần tìm kiếm trước đó. a. Làm tràn bản tin tìm đƣờng hiệu quả Trong quá trình làm tràn, từ các bản tin đến, mỗi nút thu nhặt thông tin mô hình nội bộ và thông tin này được sử dụng để giảm số nút chuyển tiếp bản tin trong lần làm tràn tiếp theo. Bởi vậy, kỹ thuật làm tràn hiệu quả được chia thành hai phần: trước tiên là thu thập thông tin từ các nút lân cận và sau đó là quá trình giảm dư thừa của quá trình làm tràn. Thông tin thu thập từ nút lân cận (Collecting Neighbors’ Information- CNI) cần một quá trình làm tràn. Khi một quá trình làm tràn xảy ra, mọi nút thu thập thông tin của các nút lân cận bằng cách nghe ngóng các bản tin gửi ra từ nút lân cận của nó. Mỗi nút có một biến được gọi là relay để quyết định xem có chuyển tiếp (forward) bản tin hay không trong các lần làm tràn tiếp theo. Nếu giá trị biến relay là đúng (true) và nút nhận bản tin này lần đầu tiên thì nó sẽ chuyển tiếp bản tin, ngược lại giá trị của relay là sai (false) thì nút này không chuyển tiếp bản tin làm tràn, không cần quan tâm bản tin này nhận lần đầu hay không. Giá trị khởi tạo của biến relay là sai và trong quá trình làm tràn lần đầu tiên (quá trình CNI), tất cả các nút chuyển bản tin không cần xác định giá trị của biến này. Quá trình xử lý ở mỗi nút xảy ra theo các bước sau: Khi nhận một bản tin làm tràn, nút chuyển tiếp bản tin nếu nó chưa nhận được bản tin này trước đó. Trước khi gửi một bản tin ra, nút gán thêm địa chỉ nút đã gửi bản tin cho nó (Predecessor) vào bản tin dữ liệu và sau đó gửi quảng bá bản tin. Nếu nút đã nhận được bản tin làm tràn này trước đó, nó lấy thông tin Predecessor trong gói tin dữ liệu trước khi hủy bản tin. Nút so sánh thông tin Predecessor này với địa chỉ của nó. Nếu hai thông tin trùng khớp, nút thiết lập giá trị biến relay là đúng. Còn không, biến relay vẫn giữ nguyên giá trị sai. Trong pha thứ hai, giảm bớt dư thừa của quá trình làm tràn (Reducing the Overhead of Flooding - ROF), nếu quá trình làm tràn khác xảy ra thì sự dư thừa của quá trình làm tràn này có thể được giảm bớt bằng cách sử dụng giá trị biến relay tại mỗi nút. Chỉ các nút có biến relay thiết lập true có thể chuyển tiếp bản tin nhận từ nút lân cận của nó, các nút với relay có giá trị false nhận bản tin nhưng không chuyển tiếp. Do đó giúp giảm thiểu bản tin dư thừa, giảm bớt số nút mạng tham gia định tuyến, tiết kiệm năng lượng toàn mạng. b. Tiết kiệm năng lƣợng tìm kiếm mở rộng vòng Trong lần tìm kiếm đầu tiên, nút nguồn gửi broadcast một bản tin request để tìm đường tới đích với - hops xung quanh nó. Mọi nút trong vòng tròn tìm kiếm thu thập thông tin mô hình mạng nội bộ dựa trên việc làm tràn (sử dụng CNI). Chúng xác định giá trị của biến Relay qua các bản tin được gửi từ các nút lân cận. Nếu không có đường tới đích, nút nguồn tăng bán kính vòng tìm kiếm và khởi tạo lại quá trình tìm kiếm (tìm kiếm lần hai). Một số nút tham gia lần tìm kiếm đầu tiên có thể không chuyển tiếp bản tin bằng cách áp dụng ROF. Các nút không chuyển tiếp bản tin có biến relay thiết lập là sai (false). Các nút không nằm trong 5
vùng tìm kiếm đầu tiên phải thực hiện quá trình CNI để xác định giá trị của biến relay. Tìm kiếm lần ba xảy ra nếu vẫn không tìm được đường đến đích, nút nguồn tiếp tục tăng bán kính vòng tìm kiếm và bắt đầu tìm kiếm lần nữa. Giống như lần tìm kiếm thứ hai, một số nút tham gia lần tìm kiếm thứ nhất và thứ hai có thể bị im lặng bởi ROF. Các nút không nằm trong cả hai vùng tìm kiếm lần một và hai phải thực hiện CNI. Tương tự như vậy, tiến trình xảy ra lần bốn, năm… nếu nút nguồn tiếp tục mở rộng vòng tìm kiếm thông tin về đích. 2.2.3. Kết quả mô phỏng Sử dụng phần mềm NS2 để mô phỏng đánh giá các kịch bản với mô hình mạng 50 nút, 60 nút, 70 nút, 80 nút, 90 nút và 100 nút mạng. Hình 2.1 biểu diễn thời gian sống của mạng khi sử dụng giao thức AODV, ERS và EERS. Từ đồ thị ta thấy giao thức EERS duy trì thời gian hoạt động mạng tốt hơn so với ERS và AODV. Kết quả cao hơn hẳn AODV và cao hơn một chút so với ERS. Điều này chứng tỏ khi sử dụng EERS các nút đã sử dụng năng lượng hiệu quả hơn. Dù số nút mạng thay đổi nhiều hay ít thì kết quả thu được vẫn là EERS đạt hiệu quả năng lượng tốt hơn, kéo dài tuổi thọ mạng. 110 AODV ERS 100 EERS Thời gian (s) 90 80 70 60 50 60 70 80 90 100 Số nút mô phỏng (nút) Hình 2.1. So sánh thời gian sống của mạng giữa AODV, ERS và EERS Hình 2.2 là kết quả so sánh tỷ lệ truyền gói tin thành công giữa EERS, ERS và AODV. Theo kết quả mô phỏng này, tỷ lệ truyền gói tin khi sử dụng giao thức định tuyến EERS gần tương tự như ERS và cao hơn AODV. Hình 2.3 đã cho ta thấy kết quả về thông lượng mạng khi sử dụng giao thức định tuyến EERS, ERS và AODV. Từ đồ thị ta thấy thông lượng mạng khi sử dụng EERS và ERS tốt hơn AODV. Với cùng một tình huống mô phỏng, cùng vị trí nút cảm biến, cùng số lượng kết nối và bản tin truyền trên mạng, EERS và ERS thu được thông lượng tốt hơn do tỷ lệ truyền gói tin thành công tốt hơn. Trong các mô phỏng này, khi số lượng nút tăng thì thông lượng mạng cũng tăng, đó không phải là xu hướng của kết quả, đó đơn giản chỉ là do trong các mô phỏng về sau, số lượng kết nối đã được tăng lên, kéo theo lượng dữ liệu truyền trên mạng nhiều hơn, từ đó làm tăng thông lượng mạng. 100 200 Throughput (Kbps) 95 150 PDR(%) AODV 90 ERS 100 AODV EERS ERS 85 50 EERS 80 0 50 60 70 80 90 100 50 60 70 80 90 100 Số nút mô phỏng (nút) Số nút mô phỏng (nút) Hình 2.2. So sánh tỷ lệ truyền gói tin thành công Hình 2.3. So sánh về thông lượng 6
2.3. Các phƣơng pháp nâng cao thời gian sống của mạng dựa vào năng lƣợng của nút cảm biến 2.3.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ó mức năng lƣợng thấp. Luận văn đề xuất giao thức Avoid Bad Route – ABR là giao thức được phát triển từ giao thức EERS với việc tìm đường dựa trên cả tiêu chí bước nhảy mạng hopcount và năng lượng. Trong thuật toán ABR bản tin route request và route reply được bổ sung thêm một trường lưu giá trị năng lượng: trường rq_min_energy trong bản tin RREQ và rp_energy trong RREP. Trường rq_min_energy sẽ lưu giá trị năng lượng của nút có năng lượng nhỏ nhất trên đường đi qua để nút đích có cơ sở lựa chọn. Trường rp_energy trong bản tin RREP lưu thông số năng lượng của tuyến đường được chọn để các nút cập nhật vào bảng định tuyến. Begin Begin Receive RREQ Create RREQ with rq_min_energy = limited Yes Have destination Create new RREQ information Broadcast RREQ No Rq_min_energy > Route No No energy threshold Yes No Yes Rq_min_energy > t >= T Is there RREP Node_energy Send RREP Yes Rq_min_energy = No Add route into routing table Node_energy Send data packet to destination Forward RREQ End End Hình 2.4. Thuật toán ABR thực hiện tại nút nguồn Hình 2.5. Thuật toán ABR thực hiện tại nút trung gian Tại nút đích được (trong hình 2.6), nút đích có một giá trị ngưỡng năng lượng để xác định đường nào sẽ thỏa mãn. Giá trị này là Destination_threshold_energy và được khởi tạo bằng 20J. Việc khởi tạo giá trị này phụ thuộc vào mô hình mạng và năng lượng của các nút trong mạng. Giá trị này khởi tạo càng lớn thì việc dùng ngưỡng để xác định đường đi sẽ được sử dụng sớm. Và khi đó sẽ ảnh hưởng đến độ trễ của mạng. Biến Temp_energy_threshold được khởi tạo bằng 0J. Biến này sẽ dùng để lưu lại giá trị lớn nhất của rq_min_energy từ các bản tin RREQ nhận được. Sau đó được sử dụng để điều chỉnh lại ngưỡng năng lượng trên nút nếu ngưỡng quá cao so với giá trị năng lượng thực tế của các nút trên mạng. Với lưu đồ mô tả trên hình 2.6, khi nút đích nhận được bản tin tìm đường RREQ, nút đích sẽ kiểm tra xem bản tin đó được nhận lần đầu tiên hoặc là bản tin trùng lặp hay không bằng cách sử dụng giá trị broadcast id trong bản tin. Nếu bản tin RREQ nhận được là bản tin lần đầu tiên hoặc là bản tin trùng lặp, giá trị trường rq_min_energy trong bản tin đó sẽ được so sánh với biến Temp_energy_threshold Nếu giá trị lớn hơn giá trị Temp_energy_threshold thì Temp_energy_threshold sẽ được update giá trị mới bằng rq_min_energy. Sau đó nút đích sẽ kiểm tra xem tuyến đường có thỏa mãn điều kiện năng lượng hay không bằng cách so sánh giá trị Rq_min_energy và Destination_threshold_energy Nếu giá trị Rq_min_energy lớn hơn Destination_threshold_energy tức là đường đi thỏa mãn điều kiện năng lượng, nút đích sẽ gửi lại bản tin RREP thông báo về đường đi cho nút nguồn. Trong trường hợp không thỏa mãn điều kiện năng lượng nút đích sẽ hủy bản tin RREQ và chờ bản tin tiếp theo. Nếu bản tin RREQ nhận được là bản tin thuộc vòng tìm kiếm tiếp theo, có nghĩa là vòng tìm kiếm trước đó không tìm được đường nào thỏa mãn điều kiện năng lượng. Nút đích thực hiện giảm giá trị ngưỡng thấp hơn giá trị Temp_energy_threshold. Trong mô phỏng này giảm đi 3J. Temp_energy_threshold với cách tính ở trên sẽ là giá trị năng lượng lớn nhất của các rq_min_energy trong vòng tìm đường thất bại trước. Và 3J là con số ước lượng năng lượng các nút bị giảm giữa hai lần gửi bản tin RREQ từ nút nguồn. Lúc này nút đích đã có giá trị ngưỡng mới, nó sẽ so sánh với giá trị của bản tin RREQ nhận được và xác định tuyến đường thỏa mãn như trường hợp trước. Nếu vẫn không có đường thỏa mãn, nút nguồn lại gửi tiếp bản 7
tin RREQ và nút đích lại tiếp tục giảm ngưỡng đến khi phù hợp. Begin Destination_threshold_energy = 20 Temp_energy_threshold = 0 Receive RREQ Broadcast ID = 0 or Broadcast ID = Old Broadcast ID Yes No Temp_energy_threshold = max(Temp_energy_threshold, Rq_min_energy) Destination_threshold_energy = Temp_energy_threshold – 3; Temp_energy_threshold = Rq_min_energy Rq_min_energy >= Destiantion_threshold_energy Rq_min_energy >= Destiantion_Threshold_energy No Yes Yes Delete RREQ No Delete RREQ Send RREP (RREP includes Rp_energy = Destiantion_threshold_energy) Send RREP (RREP includes Rp_energy = Destiantion_Threshold_energy) End Hình 2.6. Thuật toán ABR thực hiện tại nút đích Với cách làm này, các tuyến đường nút nguồn nhận được sẽ đảm bảo về năng lượng để hoạt động, và các tuyến đường có nút năng lượng thấp sẽ hạn chế được sử dụng, do đó năng lượng các nút trong mạng sẽ giảm đều hơn và thời gian sống của mạng được tăng cường. Khi tuyến đường có mức năng lượng đảm bảo cũng sẽ ổn định hơn, giúp tăng tỷ lệ truyền gói tin thành công và băng thông của hệ thống mạng. Việc tuyến đường bị lỗi do mất kết nối trong quá trình đang truyền data cũng sẽ hạn chế hơn. 2.3.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) Trong thuật toán này, nút sẽ lựa chọn đường đi tốt nhất dựa vào hai tham số là hopcount và năng lượng còn lại của nút. Để làm được việc đó, trường rp_min_energy được đưa và bản tin RREQ và trường rp_energy được đưa vào bản tin RREP để thu được thông tin năng lượng còn lại nhỏ nhất của các nút trên đường mà bản tin đó đi qua. Các trường này có giá trị khởi tạo bằng vô cùng và sẽ được thay đổi khi đi qua các nút. Với giá trị đó, thông số dùng lựa chọn đường đi tốt nhất lúc này sẽ là: (2.1) Về chi tiết cách thức gửi và xử lý bản tin RREQ và RREP thuật toán RDC hoạt động tương tự EERS, chỉ khác ở thông số lựa chọn đường đi. EERS lựa chọn đường đi tốt nhất dựa vào hopcount còn RDC dựa vào giá trị . 2.3.3. Kết quả mô phỏng Sử dụng phần mềm NS2 để mô phỏng đánh giá các giao thức đề xuất với 2 mô phỏng: - Mô phỏng 1: Mô hình 50 nút mạng với các vị trí sắp xếp ngẫu nhiên để tạo thành 5 mô hình mạng. 8
- Mô phỏng 2: Tạo ra các mô hình mạng 50 nút, 60 nút, 70 nút, 80 nút, 90 nút và 100 nút cảm biến với các nút mạng được sắp xếp ngẫu nhiên. Từ các kết quả mô phỏng 1 và 2 ta thấy hai thuật toán định tuyến được đề xuất thu được hiệu quả sử dụng năng lượng tốt hơn thuật toán cũ, kéo dài thời gian hoạt động của mạng. Các thông số khác như thông lượng, tỷ lệ truyền gói tin thành công vẫn được đảm bảo. 100 110 AODV 90 105 Thời gian (s) ERS PDR (%) AODV 100 80 EERS ERS 95 70 ABR EERS 90 RDC 60 ABR 85 50 RDC 80 Topo 1 Topo 2 Topo 3 Topo 4 Topo 5 Topo 1 Topo 2 Topo 3 Topo 4 Topo 5 Các Topo mô phỏng Các Topo mô phỏng Hình 2.7. So sánh thời gian sống của mạng Lifetime giữa Hình 2.8. So sánh tỷ lệ gửi gói tin thành công PDR giữa AODV, ERS, EERS, ABR và RDC mô phỏng 1 AODV, ERS, EERS, ABR và RDC mô phỏng 1 400 110 Throughput (Kbps) AODV 300 AODV 100 Thời gian (s) ERS ERS 90 200 EERS EERS 80 ABR 100 ABR 70 RDC 0 RDC 60 Topo 1 Topo 2 Topo 3 Topo 4 Topo 5 50 60 70 80 90 100 Các Topo mô phỏng Số nút mô phỏng (nút) Hình 2.9. So sánh thông lượng Throughput giữa AODV, Hình 2.10. So sánh thời gian sống của mạng Lifetime giữa ERS, EERS, ABR và RDC mô phỏng 1 AODV, ERS, EERS, ABR và RDC mô phỏng 2 100 200 Throughput (Kbps) 95 150 AODV AODV PDR(%) 90 ERS 100 ERS EERS EERS 85 ABR 50 ABR 80 RDC 0 RDC 50 60 70 80 90 100 50 60 70 80 90 100 Số nút mô phỏng (nút) Số nút mô phỏng (nút) Hình 2.11. So sánh tỷ lệ gửi gói tin thành công PDR giữa Hình 2.12. So sánh thông lượng Throughput của mạng giữa AODV, ERS, EERS, ABR và RDC mô phỏng 2 AODV, ERS, EERS, ABR và RDC mô phỏng 2 2.4. Phƣơng pháp tìm đƣờng tiết kiệm năng lƣợng dựa trên điều khiển công suất. 2.4.1. Kỹ thuật điều khiển công suất Kỹ thuật này được thực hiện nhờ quá trình tính toán suy hao và dự đoán công suất phát tại từng nút. Các nút sử dụng bản tin Hello của giao thức định tuyến để trao đổi thông tin và xác định công suất suy hao Ploss. Xét hai nút A và B. Nút A gửi bản tin Hello tới nút B sử dụng công suất mặc định lớn nhất Ptx_max (dBm). Nút B nhận bản tin Hello, nó xác định công suất nhận tại B Prx_B (dBm) và tính toán công suất suy hao từ A sang B theo công thức sau: – (2.2) 9
Sau đó nút B xác định công suất phát từ A sang B theo công thức: (2.3) Trong đó, Psen (dBm) là mức công suất nhỏ nhất để nhận được bản tin thành công tại bên thu (hay còn gọi là độ nhạy thu), Pmar (dBm) là giá trị dự trữ xác định trước cho liên kết tùy thuộc vào sự di dộng của node và các ảnh hưởng nhiễu của node xung quanh cũng như sự biến động của môi trường truyền dẫn. Sau khi tính toán xong, nút B gửi giá trị đó cho nút A qua bản tin Hello. Nút A lưu thông tin đó trong bảng các nút lân cận tương ứng với nút B. Giá trị này sẽ được nút A sử dụng làm công suất truyền các bản tin từ A đến B sau này. Mức công suất này sẽ được cập nhật mỗi khi có bản tin Hello trao đổi giữa các node với nhau. Trong quá trình truyền nhận theo thủ tục của giao thức sự dự đoán và tính toán công suất phát này được thực hiện liên tục. 2.4.2. Đề xuất phƣơng pháp định tuyến dựa trên điều khiển công suất Thuật toán mới được xây dựng dựa trên giao thức định tuyến AODV và điều khiển công suất, được gọi là thuật toán định tuyến kết hợp với điều khiển công suất (Power Control Combined with Routing Protocol (PRP)). Các quá trình gửi, nhận xà xử lý bản tin định tuyền không có gì thay đổi. Giao thức định tuyền mới chỉ khác AODV ở công thức tính chi phí đường đi metric và sử dụng điều khiển công suất khi truyền bản tin định tuyến và dữ liệu. Xét kết nối giữa 2 nút A và B, nếu sử dụng giao thức AODV thì chi phí đường đi giữa 2 nút này bằng 1 (sử dụng hopcount để tính metric) nhưng với giao thức PRP thì metric này được tính theo công thức: (2.4) Với { Trong đó, Ptx_AB là công suất truyền dữ liệu từ A sang B được xác định ở phần trên. là biến, có giá trị bằng C hoặc 0 tùy thuộc vào giá trị LPsent. Ptx_max là giá trị công suất truyền lớn nhất khi không có điều khiển công suất. LPsent là năng lượng còn lại của nút tại một thời điểm tính toán. LPthr là ngưỡng năng lượng còn lại. C là một hằng số, được sử dụng với mục đích loại bỏ những tuyến đường có mức năng lượng còn lại của nút thấp. Trong công thức 2.4, khi năng lượng còn lại của nút vẫn đáp ứng được hoạt động tốt, có giá trị bằng 0 và chi phí đường đi lúc này chỉ phụ thuộc vào công suất truyền. Nếu không có điều khiển công suất, tức là công suất truyền bằng công suất cực đại thì chi phí đường đi sẽ bằng 1 giống như trường hợp sử dụng AODV. Khi sử dụng điều khiển công suất, tuyến đường với mức tiêu tốn công suất nhỏ nhất sẽ được lựa chọn. Trong trường hợp năng lượng còn lại của nút thấp hơn ngưỡng năng lượng còn lại, giá trị C được cộng thêm vào chi phí đường đi. Giá trị của C đưa ra đủ lớn để những tuyến đường có chứa nút với năng lượng còn lại nhỏ không được lựa chọn. Điều này giúp cân bằng việc sử dụng năng lượng của các nút trên mạng cảm biến, từ đó kéo dài tuổi thọ của mạng. Giá trị ngưỡng năng lượng còn lại và C cần phải được tính toán và xác định. Chúng phụ thuộc vào công suất truyền và năng lượng của từng mạng cảm biến xác định. Ví dụ như, nếu một mạng có tuyến đường đi xấu nhất có chi phí đường đi bằng 10 thì giá trị của C nên được thiết lập cao hơn 10. Ngưỡng năng lượng còn lại LPthr thì khó xác định hơn. Nếu ngưỡng năng lượng để quá cao, việc áp dụng so sánh ngưỡng sẽ xảy ra sớm, lúc này những tuyến đường ngắn chứa nút có năng lượng dưới ngưỡng sẽ không được chọn, thay vào đó là các tuyến đường dài hơn được chọn. Điều này làm tiêu tốn năng lượng và tăng độ trễ trong mạng. Nếu ngưỡng năng lượng quá nhỏ, thông số này sẽ được áp dụng muộn, nút với năng lượng thấp tiếp tục hoạt động và sẽ nhanh chóng hết năng lượng, làm ảnh hưởng đến thời gian sống của toàn mạng. Do đó, việc xác định ngưỡng năng lượng còn lại chính xác là một vấn đề quan trọng. Chọn ngưỡng năng lượng chính xác sẽ giúp tiết kiệm năng lượng sử dụng và nâng cao thời gian sống của mạng. Giá trị ngưỡng này phụ thuộc vào từng mô hình và kích thước mạng cụ thể. Không có một giá trị chung của ngưỡng năng lượng cho tất cả các mô hình. Giá trị này có thể được xác định dựa trên phương pháp thực nghiệm 2.4.3. Kết quả mô phỏng Sử dụng phầm mềm NS2 để mô phỏng đánh giá. Các kết của về thời gian sống của mạng, thông lượng, độ trễ được thể hiện trong hình vẽ 2.13, 2.14 và 2.15. Từ các kết quả mô phỏng ta thấy giao thức định tuyến kết hợp điều khiển công suất cho kết quả sử dụng năng lượng tốt hơn, kéo dài thời hoạt động của mạng đồng thời cải thiện đáng kể thông lượng mạng và tỷ lệ gửi gói tin thành công. 10
100.000 8.000 Throughput (Kbps) 80.000 6.000 60.000 Thời gian (s) 4.000 PRP 40.000 PRP AODV AODV 20.000 2.000 0.000 0.000 60 70 80 90 100 110 120 60 70 80 90 100 110 120 Số nút mạng (nút) Số nút mạng (nút) Hình 2.13. So sánh thời gian sống của mạng khi sử dụng Hình 2.14. So sánh thông lượng của mạng khi sử dụng AODV và PRP AODV và PRP 100.000 80.000 PDR (%) 60.000 PRP AODV 40.000 20.000 0.000 60 70 80 90 100 110 120 Số nút mạng (nút) Hình 2.15. So sánh tỷ lệ truyền gói tin thành công khi sử dụng PRP và AODV 2.5. Tổng kết chƣơng Bắt nguồn từ giao thức định tuyến kinh điển AODV, luận văn thay đổi cách thức gửi bản tin định tuyến, thay đổi các thông số chọn đường và áp dụng kỹ thuật điều khiển công suất đã tạo ra các giao thức định tuyến mới nhằm sử dụng hiệu quả năng lượng trong mạng cảm biến không dây đa chặng gồm EERS, ABR, RDC và PRP. Các kết quả mô phỏng trên phần mềm NS2 đã chỉ ra rằng các giao thức đề xuất thu được kết quả sử dụng năng lượng tốt hơn giao thức truyền thống AODV trong khi các thông số khác của mạng như băng thông (throughput), độ trễ (delay), tỷ lệ truyền gói tin thành công (PDR) vẫn được đảm bảo. 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. Giới thiệu chƣơng Với các kỹ thuật định tuyến đã trình bày ở trên, mạng cảm biến không dây đã thu được hiệu quả đáng kể trong sử dụng năng lượng. Tuy nhiên trong ứng dụng giám sát đối tượng của mạng cảm biến không dây, đối tượng di chuyển trong mạng cảm biến và tại một thời điểm nhất định đối tượng sẽ ở một vị trí nào đó trong mạng cảm biến. Do đó việc tất cả các nút cảm biến hoạt động tại một thời điểm là không cần thiết và gây tiêu tốn năng lượng toàn mạng. Với ý tưởng dự đoán vị trí của đối tượng trong mạng cảm biến sau đó điều khiển bật tắt các nút cảm biến quanh khu vực dự đoán luận án thu được mô hình giám sát theo vùng sử dụng năng lượng hiệu quả hơn so với mô hình giám sát toàn mạng khi tất cả các nút cảm biến đều bật. Trong phần luận án này, trình bày thuật toán được sử dụng để dự đoán vị trí và hướng di chuyển của đối tượng sau đó mô phỏng để thấy được việc sử dụng mô hình giám sát đối tượng theo vùng sẽ hiệu quả hơn giám sát trên toàn bộ mạng. 3.2. Cơ sở toán học 3.2.1. Định lý xác suất Bayes Theo định lý Bayes, chúng ta có: ( | ) ( ) ( | ) (3.1) ( ) 11
Trong đó:  ( | ) được gọi là xác suất hậu nghiệm (posterior probability) của tín hiệu B khi biết tín hiệu A vì nó được rút ra hoặc phụ thuộc vào giá trị được cho của A  ( | ) được gọi là xác suất khả dĩ (likelihood probability) của A khi biết tín hiệu B  ( ) được gọi là xác suất tiền nghiệm (prior probability) của B vì nó hoàn toán độc lập với sự tồn tại của A, nói cách khác, việc đưa ra xác suất này hoàn toàn không phụ thuộc vào sự có mặt của A  ( ) xác suất của A, đại lượng này còn gọi là hằng số chuẩn hóa (normalising constant), vì nó luôn giống nhau, không phụ thuộc vào sự kiện B đang muốn biết. Khi giải quyết các bài toán theo vết đối tượng trong thực tế, mục đích của chúng ta chính là việc tính toán, ước lượng để đưa ra được xác suất hậu nghiệm bằng cách sử dụng các hàm xác suất tiên nghiệm và khả dĩ. 3.2.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.2.2.1. Hàm phân bố xác suất (Probability Distribution Function) Hàm phân bố xác suất của biến ngẫu nhiên X, kí hiệu là F ( X ) , là xác suất để biến ngẫu nhiên X nhận giá trị nhỏ hơn x, với x là một số thực bất kỳ: ( ) ( ) (3.2) Đối với hàm phân bố xác suất, ta có 2 tính chất quan trọng sau: ( ) ( ) ( ) (3.3) ( ) ( ) (3.4) Từ định nghĩa của hàm phân bố xác suất ( ) ( ) ta nhận thấy hàm phân bố xác suất phản ánh mức độ tập trung xác suất ở phía bên trái của một số thực nào đó. 3.2.2.2. Hàm mật độ xác suất (Probability Density Function) Hàm mật độ xác suất của một biến ngẫu nhiên liên tục , kí hiệu là ( ), là đạo hàm bậc nhất của hàm phân bố xác suất của biến ngẫu nhiên đó: ( ) ( ) (3.5) Một số tính chất quan trọng của hàm mật độ xác suất: ( ) (3.6) ( ) ∫ ( ) (3.7) ∫ ( ) (3.8) ( ) ∫ ( ) (3.9) 3.2.3. Kỳ vọng và phƣơng sai của biến ngẫu nhiên 3.2.3.1. Kỳ vọng của biến ngẫu nhiên Giả sử biến ngẫu nhiên rời rạc nhận một trong các giá trị có thể có với các xác suất tương ứng . Kỳ vọng của biến ngẫu nhiên rời rạc , ký hiệu ( ) là tổng các tích giữa các giá trị có thể có của biến ngẫu nhiên với các xác suất tương ứng: ( ) ∑ (3.10) Nếu là biến ngẫu nhiên liên tục với hàm mật độ xác suất ( ) thì kỳ vọng ( ) được xác định bằng biểu thức: ( ) ∫ ( ) (3.11) Ta nhận thấy, kỳ vọng của một biến ngẫu nhiên phản ánh giá trị trung tâm của phân phối xác suất của biến ngẫu nhiên. 3.2.3.2. Phương sai của biến ngẫu nhiên Trong thực tế, đôi khi nếu chỉ biết giá trị kỳ vọng của một biến ngẫu nhiên ta chưa thể xác định được biến ngẫu nhiên đó, bởi ta không thể biết được mức độ phân tán của các giá trị của biến ngẫu nhiên xung quanh giá trị trung bình của nó. Từ đó chúng ta có khai niệm về phương sai của một biến ngẫu nhiên Phương sai của biến ngẫu nhiên , ký hiệu là ( ) là kỳ vọng của bình phương sai lệch của biến ngẫu nhiên so với kỳ vọng của nó: ( ) , ( )- (3.12) Nếu là biến ngẫu nhiên rời rạc thì phương sai của nó sẽ được xác định theo công thức: ( ) ∑ , ( )- ∑ ,( )- (3.13) 12
Nếu là biến ngẫu nhiên liên tục thì phương sai của nó sẽ được xác định theo công thức: ( ) ∫ , ( )- ( ) ∫ ( ) , ( )- (3.14) Như vậy xuất phát từ định nghĩa của phương sai, ta thấy phương sai chính là trung bình số học của bình phương các sai lệch giữa các giá trị có thể có của biến ngẫu nhiên so với giá trị trung bình của các giá trị đó. Do đó nó phản ánh mức độ phân tán của các giá trị của biến ngẫu nhiên xung quanh giá trị trung bình của nó là kỳ vọng. 3.2.4. Mô hinh hóa hệ thống không gian trạng thái động Mô hình không gian trạng thái của hệ thống có thể được biểu diễn thông qua hai phương trình sau: Phương trình trạng thái: ( ) (3.15) Phương trình quan sát: ( ) (3.16) Với:  và lần lượt là trạng thái của hệ thống – đại lượng không thể quan sát được (unobserved system state) và tín hiệu đo đạc – đại lượng có thể quan sát được (observed measurement signal) ở thời điểm .  và là lần lượt là hàm chuyển trạng thái (state transition function) và hàm quan sát (observation function). Trong trường hợp tổng quát, và là các hàm phi tuyến  và lần lượt là nhiễu xử lý (process noise) và nhiễu quan sát (observation noise) với hàm phân phối xác suất đã biết. Trong trường hợp tổng quát, các nhiễu này tuân theo hàm phân phối xác suất phi Gauss  là đầu vào của hệ thống ở thời điểm . Ta cũng kí hiệu rằng:  * + là tập các trạng thái của hệ thống từ thời điểm tới thời điểm  * + là tập các tín hiệu quan sát được từ thời điểm tới thời điểm Ngoài ra, chúng ta hoàn toàn có thể biểu diễn mô hình không gian trạng thái động của đối tượng thông qua các hàm mật độ xác suất như sau:  Phương trình trạng thái: ( | )  Phương trình quan sát: ( | ) 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 Không mất tính tổng quát, ta xét một hệ (hệ này có thể là một hệ tín hiệu, hệ cơ học, ...) có không gian trạng thái được mô hình hóa bởi một hàm phi tuyến và tuân theo phân phối phi Gauss thỏa mãn 2 giả định sau:  Chuỗi trạng thái của hệ thỏa mãn giả định về hệ Markov bậc 1. Tức là: p( xt | x0:t 1 )  p( xt | xt 1 ) (3.17)  Các giá trị đo có được tại một thời điểm bất kỳ chỉ phụ thuộc vào trạng thái của hệ tại thời điểm đó. Tức là: t p( y1:t | x1:t )   p( yi | xi ) (3.18) i 0 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 Trong thực tế, mục tiêu của bài toán lọc thường là tìm được lời giải cho hàm mật độ xác suất hậu nghiệm p( x0:t | y1:t ) , và từ đó đưa ra kỳ vọng của một hàm ft ( x0:t ) như sau: E[ ft ( x0:t )]   ft ( x0:t ) p( x0:t | y1:t )dx0:t (3.19) Không giống như các phương pháp lọc đã được trình bày trước đó – là các phương pháp dựa trên các phép toán giải tích, các phương pháp Monte Carlo dựa trên sự mô phỏng và xấp xỉ các hàm mật độ và các tích phân bằng một tập các mẫu dữ liệu được sinh ra bởi chính các hàm mật độ và các tích phân đó. Nói cách khác, chúng ta có thể mô phỏng hàm mật độ xác suất hậu nghiệm p( x0:t | y1:t ) bằng cách lấy N điểm ngẫu nhiên x0:(it) , i  1, N . Các mẫu này được vẽ từ hàm mật độ xác suất p( x0:t | y1:t ) , chính vì vậy ta có thể đưa ra công thức thực nghiệm sau: 13
1 N 1 N p(dx0:t | y1:t )   N i1  ( x0:t  x0:(it) )   x( i ) (dx0:t ) N i1 0:t (3.20) Và khi đó chúng ta có thể dễ dàng xấp xỉ được kỳ vọng như sau: 1 N E[ ft ( x0:t )]   ft ( x0:t ) p(dx0:t | y1:t )   ft ( x0:(it) ) N i1 (3.21) Ta có thể nhận thấy cách tiếp cận này khá dễ dàng trong việc tính toán và ước lượng ra hàm phân bố hậu nghiệm. Nhưng trong thực tế, chúng ta thường không có cách nào để tạo ra một tập các mẫu ngẫu nhiên từ phân phối xác suất p( x0:t | y1:t ) , vì p( x0:t | y1:t ) trong trường hợp tổng quát thường là hàm đa biến và không có dạng chuẩn nhất định. Nhiều phương pháp tiếp cận đã được phát triển nhằm giải quyết nhược điểm này như là:  Phương pháp hàm tích lũy xác suất nghịch đảo (Inversed CDF)  Phương pháp lấy mẫu loại trừ (Rejection Sampling)  Thuật toán Metropolis – Hastings (Metropolis – Hastings Algorithm)  Phương pháp lấy mẫu quan trọng (Importance Sampling - IS) Trong số các phương pháp trên thì phương pháp lấy mẫu quan trọng là phương pháp được sử dụng trong bộ lọc chất điểm. 3.3.3. Lấy mẫu quan trọng (Importance Sampling) Như đã nói ở trên, thông thường chúng ta rất khó có thể lấy mẫu trực tiếp từ hàm phân phối xác suất hậu nghiệm. Thay vào đó chúng ta sẽ đưa ra một hàm phân phối đề xuất (Proposal Distribution)  ( x0:t | y1:t ) thay thế. Khi đó phương trình (3.19) sẽ tương đương với: p( x0:t | y1:t ) E[ ft ( x0:t )]   ft ( x0:t )  ( x0:t | y1:t )dx0:t   ft ( x0:t )w( x0:t ) ( x0:t | y1:t )dx0:t (3.22)  ( x0:t | y1:t ) Trong đó w( x0:t ) được biểu thị bằng công thức sau: p( x0:t | y1:t ) p( y1:t | x0:t ) p( x0:t ) w( x0:t )   (3.23)  ( x0:t | y1:t ) p( y1:t ) ( x0:t | y1:t ) Dựa trên phương pháp Monte Carlo, nếu chúng ta chọn ra N mẫu {x0:(it) , i  1,..., N} từ hàm phân phối  ( x0:t | y1:t ) , khi đó một ước lượng của hàm phân phối trạng thái là: 1 N E[ ft ( x0:t )]   N i1 ft ( x0:(it) )w( x0:(it) ) (3.24) Giả sử chúng ta gọi w( x0:t ) là trọng số chưa được chuẩn hóa. Khi đó w( x0:t ) có thể được biểu diễn như sau: p( y1:t | x0:t ) p( x0:t ) w( x0:t )  (3.25)  ( x0:t | y1:t ) Khi đó ta có: E[ ft ( x0:t )]   ft ( x0:t ) w( x0:t )  ( x0:t | y1:t )dx0:t   f ( x )w( x ) ( x | y )dx t 0:t 0:t 0:t 1:t 0:t (3.26) p( y1:t )  w( x ) ( x | y )dx 0:t 0:t 1:t 0:t Nên 1  N f ( x0:(it) )w( x0:(it) ) N i 1 t E[ ft ( x0:t )]  N   ft ( x0:(it) )w( x0:(it) ) (3.27) 1  w( x0:t ) N (i ) i 1 N i1 Trong đó: w( x0:(it) ) w t(i )  (3.28)  N i 1 w( x0:(it) ) 14
Là trọng số được chuẩn hóa. Và khi đó, ta có biểu thức tương đương như sau: w t(i ) =Nw t(i ) (3.29) Chính vì vậy hàm mật độ xác suất hậu nghiệm p( x0:t | y1:t ) có thể được xấp xỉ như sau: N p(dx0:t | y1:t )  pˆ (dx0:t | y1:t )   w t(i ) x( i ) (dx0:t ) (3.30) 0:t i 1 Và kỳ vọng có thể được biểu diễn bằng: E[ ft ( x0:t )]  Eˆ [ ft ( x0:t )]   ft ( x0:t ) pˆ (dx0:t | y1:t ) (3.31) Về nguyên tắc, phương pháp này là phương pháp lấy mẫu từ một hàm đề xuất đã được biết trước và được gọi là phương pháp lấy mẫu quan trọng (Important Sampling). Như chúng ta đã thấy thì phương pháp lấy mẫu quan trọng giải quyết việc ước lượng hàm phân phối xác suất hậu nghiệm trong điều kiện hàm này khó có thể được đánh giá. Tuy nhiên một vấn đề trở ngại gặp phải khi chúng ta làm việc với phương pháp này đó chính là dữ liệu phải được thu thập trước khi ước lượng ( | ), như vậy các trọng số sẽ phải được tính toán lại toàn bộ mỗi khi có dữ liệu mới. Để giải quyết vấn đề này, người ta đưa ra phương pháp lấy mẫu quan trọng tuần tự. Với phương pháp này, khối lượng tính toán sẽ được giảm đi rất nhiều so với phương pháp lấy mẫu quan trọng. 3.3.4. Lấy mẫu quan trọng tuần tự (Sequential Important Sampling – SIS) Để thực hiện thuật toán này một cách nội suy, chúng ta có thể nhận thấy rằng:  ( x0:t | y1:t )   ( x0:t 1 | y1:t 1 ) ( xt | x0:t 1, y1:t ) (3.32) Như vậy theo tính chất đệ quy ta có: t  ( x0:t | y1:t )   ( x0 ) ( xk | x0:k 1, y1:k ) (3.33) k 1 Ta có thuật toán SIS: Thuật toán lấy mẫu quan trọng tuần tự SIS () () () () [{ } ] [{ } ]  FOR i=1:N o Sinh ra xt(i ) ~  ( xt | xt(i1) , yt ) (i ) (i ) p( yt | xt(i ) ) p( xt(i ) | xt(i1) ) o Tính theo w công thức w =w t1 (i ) t t  opt ( x(i ) | x(i ) , yt ) t t 1  END FOR  FOR i=1:N, chuẩn hóa trọng số của các mẫu w( xt(i ) ) wt  N (i )  i1 w( xt(i ) )  END FOR Giả sử chúng ta có thể mô tả không gian trạng thái của một hệ thống thông qua các phương trình sau: 1 25 xk 1 xk  xk 1   8cos(1.2k )+w k (3.34) 2 1  xk21 1 2 yk  xk  vk (3.35) 20 Trong đó, và lần lượt là nhiễu xử lý và nhiễu quan sát trong quá trình ước lượng. Để đơn giản, trong mô phỏng này chúng ta coi các nhiễu này là nhiễu trắng tuân theo phân phối Gauss chuẩn N (0,1) . Dễ dàng nhận thấy các phương trình hệ thống trên đều là các phương trình phi tuyến. Quá trình mô phỏng được thực hiện trên Matlab với thời gian mô phỏng là 50s Kết quả mô phỏng như hình 3.1, 3.2 và 3.3. Qua các kết quả mô phỏng tương ứng với số lượng chất điểm N lần lượt là 100, 1000 và 5000, ta có thể rút ra một số nhận xét sau: 15
 So với kết quả theo vết thu được thông qua bộ lọc Kalman mở rộng, thì kết quả theo vết thu được từ thuật toán SIS chính xác hơn rất nhiều. Tuy nhiên, bên cạnh đó từ kết quả thu được của thuật toán SIS ta cũng dễ dàng nhận thấy rằng: số lượng các vị trí mà thuật toán SIS đưa ra kết quả ước lượng chưa chính xác còn khá cao. Nguyên nhân chủ yếu của hiện tượng này là do thuật toán SIS gặp phải vấn đề thoái hóa của các giá trị trọng số trong quá trình hoạt động hoạt động của nó như đã được trình bày chi tiết ở những phần tiếp theo. Hình 3.1. Kết quả của thuật toán SIS ứng với N = 100 mẫu Hình 3.2. Kết quả của thuật toán SIS ứng với N = 1000 mẫu Hình 3.3.Kết quả của thuật toán SIS ứng với N = 5000 mẫu 3.3.5. Vấn đề thoái hóa mẫu và giải pháp lấy mẫu lại (Resampling) Như đã được đề cập ở trên, trong khi phương pháp lấy mẫu quan trọng tuần tự có thể loại bỏ các vấn đề liên quan nhờ thực hiện việc tính toán truy hồi, nhưng nó lại phát sinh một nhược điểm ảnh hưởng quan trọng tới kết quả tính toán. Từ thực nghiệm người ta nhận thấy rằng, sau một số lần lặp, một số các chất điểm sẽ có trọng số với độ lớn không đáng kể. Điều này xảy ra là bởi vì phương sai của các trọng số tăng một cách ngẫu nhiên theo thời gian. Để giải quyết vấn đề này người ta đưa ra phương pháp lấy mẫu lại (resampling). Ý tưởng chính của phương thức này chính là: các mẫu mà trọng số có giá trị nhỏ sẽ được thay thế bởi các trọng số có giá trị lớn. Khi đó thuật toán SIS được thay thế bởi thuật toán SIR. Tuy nhiên làm sao chúng ta biết khi nào cần phải thực hiện việc tái chọn mẫu? Để làm được điều này, chúng ta đưa ra một đại lượng đo mới, gọi là kích thước mẫu hiệu dụng (Effective Sample Size) . Độ đo này cho phép chúng ta biết được số mẫu trong thuật toán có ảnh hưởng chủ yếu tới kết quả ước lượng và từ đó chúng ta biết được khi nào cần phải thực hiện việc tái chọn mẫu trong thuật toán của mình. ̂ (3.36) () ∑ . / 16
Thuật toán lấy mẫu lại (Resampling Algorithm) ( ) ( ) () () [{ } ] [{ } ]  Bắt đầu thuật toán.  Khởi tạo hàm CDF: c1 = 0  FOR i = 2 : N () o Xây dựng hàm CDF:  END FOR  i=1  Lấy một điểm ngẫu nhiên u1 theo , -  FOR o ( ) o WHILE  o END WHILE ( ) () o Gán mẫu: ( ) o Gán trọng số: o Gán  END FOR Kết thúc thuật toán. 3.3.6. Thuật toán Generic Particle Filter – GPF Thuật toán Generic Particle Filter thực hiện tương tự thuật toán SIS, nhưng sau khi trải qua các bước của SIS, thuật toán này kiểm tra xem có hiện tượng thoái hóa mẫu không, nếu có thuật toán này dùng thuật toán lấy mẫu lại như trình bày ở trên để tiến hành lấy mẫu lại. Chi tiết như sau: () () () () [{ } ] [{ } ]  Bắt đầu thuật toán.  FOR () () o Lấy mẫu ( | ) () (i ) (i ) p( yt | xt(i ) ) p( xt(i ) | xt(i1) ) o Tính toán các trọng số mới, , w =w t1 t  opt ( x(i ) | x(i ) , yt ) t t 1 (i ) w( x ) Chuẩn hóa trọng số: w t  (i ) t o  N i 1 w( xt(i ) )  END FOR  Tính ̂ theo 3.67  IF ̂ ( ) ( ) () () [{ } ] [{ } ]  END IF Kết thúc. 3.3.6. Thuật Sampling Importance Resampling – SIR Cũng với mục đích là giảm sự ảnh hưởng của hiện tượng thoái hóa mẫu và tăng khả năng áp dụng bộ lọc chất điểm PF cho các ứng dụng khác nhau. SIR có thể thu được từ SIS như sau: () () - Hàm mật độ quan trọng ( | ) được thay bằng ( | ) - Thực hiện thuật toán RESAMPLE trong tất cả các chu kỳ lặp. Như vậy, việc cập nhật trọng số được thực hiện đơn giản như sau: () () () ( | ) (3.37) 17
() Nhưng do thực hiện lấy mẫu lại tại tất cả các lần lặp, nên vì vậy: () () ( | ) (3.38) Với cách thiết đặt này thì có thể nói SIR là dạng đơn giản nhất của bộ lọc chất điểm PF. Thuật toán Sampling Importance Resampling (SIR)  x(i ) , w    SIR x(i ) , w (i ) N , y  (i ) N  t t  i 1  t 1 t 1 i1 t   FOR i=1:N o Sinh ngẫu nhiên ( ) ( | ( ) ) o Tính theo w t(i ) công thức ( ) ( | () )  END FOR  FOR i=1:N, chuẩn hóa trọng số của các mẫu w (i ) w t(i )  N t (i )  i1 w t  END FOR  Tiến hành lấy mẫu lại theo thuật toán RESAMPLE ( ) ( ) () () [{ } ] [{ } ]  Kết thúc thuật toán 3.3.7. Mô phỏng thuật toán bộ lọc chất điểm Quay trở lại bài toán theo vết mà chúng ta đã tiếp cận trước đó trong phần trên. Quá trình mô phỏng sẽ lần lượt được thực hiện trên Matlab với thời gian mô phỏng là 50s và 150s. Các kết quả trên các hình từ 3.4 đến 3.9 cho ta thấy:  Trong kết quả mô phỏng, các điểm màu đỏ biểu diễn vị trí thật của đối tượng tại thời điểm t, kết quả theo vết sử dụng thuật toán bộ lọc chất điểm và thuật toán bộ lọc Kalman mở rộng lần lượt có màu xanh dương và màu xanh lục  So với thuật toán bộ lọc Kalman mở rộng – được sử dụng nhằm khắc phục những nhược điểm của bộ lọc Kalman truyền thống trong việc giải quyết các bài toán mà hệ thống là phi tuyến và nhiễu tuân theo hàm phân phối phi Gauss – thì thuật toán bộ lọc chất điểm cho kết quả tốt hơn rất nhiều, điều này thể hiện bằng việc: số lượng các điểm màu đỏ được bộ lọc chất điểm bám theo khá chính xác  Khi số chất điểm tăng dường như kết quả theo vết của bộ lọc chất điểm càng tốt hơn. Điều này sẽ được chứng minh trong các kết quả mô phỏng tiếp theo Hình 3.4. Kết quả thuật toán SIR ứng với N = 100, t = 50s Hình 3.5. Kết quả thuật toán SIR ứng với N = 1000, t = 50s 18