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.
Lớp liên kết dữ
liệu
Phần quản lý nhiệm vụ
Lớp mạng
Phần quản lý di động
Lớp truyền tải
Phần quản lý năng lƣợng
Lớp ứng dụng
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.
Thời gian (s)
110
AODV
ERS
EERS
100
90
80
70
60
50
60
70
80
90
Số nút mô phỏng (nút)
100
Hình 2.1. So sánh thời gian sống của mạng giữa AODV, ERS và EERS
PDR(%)
100
95
AODV
90
ERS
EERS
85
80
Throughput (Kbps)
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.
200
150
100
AODV
ERS
50
EERS
0
50
60
70
80
90
Số nút mô phỏng (nút)
100
50
60
70
80
90
Số nút mô phỏng (nút)
100
Hình 2.3. So sánh về thông lượng
Hình 2.2. So sánh tỷ lệ truyền gói tin thành cô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
Create new RREQ
Have destination
information
Broadcast RREQ
No
t >= T
No
Rq_min_energy > Route
energy threshold
No
Yes
Yes
Is there RREP
No
Rq_min_energy >
Node_energy
Send RREP
Yes
Add route into routing table
Send data packet to destination
End
Rq_min_energy =
Node_energy
No
Forward RREQ
End
Hình 2.5. Thuật toán ABR thực hiện tại nút trung gian
Hình 2.4. Thuật toán ABR thực hiện tại nút nguồn
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
Yes
No
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.
110
105
100
95
90
85
80
90
AODV
80
ERS
70
EERS
60
ABR
50
AODV
ERS
PDR (%)
Thời gian (s)
100
RDC
Topo 1 Topo 2 Topo 3 Topo 4 Topo 5
EERS
ABR
RDC
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.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
Hình 2.7. So sánh thời gian sống của mạng Lifetime giữa
AODV, ERS, EERS, ABR và RDC mô phỏng 1
110
300
AODV
ERS
200
EERS
100
ABR
0
ERS
90
EERS
80
ABR
70
RDC
60
RDC
50
Topo 1 Topo 2 Topo 3 Topo 4 Topo 5
Các Topo mô phỏng
60
70
80
90
100
Số nút mô phỏng (nút)
Hình 2.9. So sánh thông lượng Throughput giữa AODV,
ERS, EERS, ABR và RDC mô phỏng 1
Hình 2.10. So sánh thời gian sống của mạng Lifetime giữa
AODV, ERS, EERS, ABR và RDC mô phỏng 2
100
AODV
ERS
90
EERS
85
ABR
80
RDC
50
60
70
80
90
Số nút mô phỏng (nút)
Throughput (Kbps)
200
95
PDR(%)
AODV
100
Thời gian (s)
Throughput (Kbps)
400
150
AODV
100
ERS
EERS
50
ABR
0
100
RDC
50
60
70
80
90
Số nút mô phỏng (nút)
100
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
Hình 2.11. 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 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
Thời gian (s)
80.000
60.000
40.000
PRP
20.000
AODV
0.000
60
70
80
90
100 110 120
Throughput (Kbps)
100.000
8.000
6.000
4.000
PRP
2.000
AODV
0.000
60
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
AODV và PRP
70
80 90 100 110 120
Số nút mạng (nút)
Hình 2.14. So sánh thông lượng của mạng khi sử dụng
AODV và PRP
100.000
PDR (%)
80.000
PRP
AODV
60.000
40.000
20.000
0.000
60
70
80
90
100 110
Số nút mạng (nút)
120
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ó:
( | )
( | ) ( )
( )
11
(3.1)
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
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.
Nếu
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
p(dx0:t | y1:t )
1 N
1 N
( x0:t x0:(it) ) x( i ) (dx0:t )
N i1
N i1 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
ft ( x0:(it) )
N i1
E[ ft ( x0:t )] ft ( x0:t ) p(dx0:t | y1:t )
(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:
E[ ft ( x0:t )] ft ( x0:t )
p( x0:t | y1:t )
( x0:t | y1:t )dx0:t ft ( x0:t )w( x0:t ) ( x0:t | y1:t )dx0:t
( x0:t | y1:t )
(3.22)
Trong đó w( x0:t ) được biểu thị bằng công thức sau:
w( x0:t )
p( x0:t | y1:t ) p( y1:t | x0:t ) p( x0:t )
( x0:t | y1:t ) p( y1:t ) ( x0:t | y1:t )
(3.23)
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à:
E[ ft ( x0:t )]
1 N
ft ( x0:(it) )w( x0:(it) )
N i1
(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:
w( x0:t )
p( y1:t | x0:t ) p( x0:t )
( x0:t | y1:t )
(3.25)
Khi đó ta có:
E[ ft ( x0:t )] ft ( x0:t )
w( x0:t )
( x0:t | y1:t )dx0:t
p( y1:t )
f ( x )w( x ) ( x | y )dx
w( x ) ( x | y )dx
t
0:t
0:t
0:t
0:t
0:t
1:t
1:t
0:t
(3.26)
0:t
Nên
N
1
f ( x0:(it) )w( x0:(it) ) N
i 1 t
E[ ft ( x0:t )] N
ft ( x0:(it) )w( x0:(it) )
N
1
(i )
i 1
w( x0:t )
N i1
(3.27)
Trong đó:
w t(i )
w( x0:(it) )
14
N
w( x0:(it) )
i 1
(3.28)
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 )
t
(i )
o Tính theo w công thức w =w t1
(i )
t
p( yt | xt(i ) ) p( xt(i ) | xt(i1) )
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 ) )
(i )
wt N
i1 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:
xk
1
25 xk 1
xk 1
8cos(1.2k )+w k
2
1 xk21
(3.34)
1 2
xk vk
20
(3.35)
yk
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
o
}
( |
]
()
Tính toán các trọng số mới,
)
()
,
(i )
t
(i )
w =w t1
p( yt | xt(i ) ) p( xt(i ) | xt(i1) )
opt ( x(i ) | x(i ) , yt )
t
o
Chuẩn hóa trọng số: w t
(i )
t 1
(i )
t
w( x )
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:
()
( |
)
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.
(3.38)
Thuật toán Sampling Importance Resampling (SIR)
x(i ) , w SIR x(i ) , w (i ) N , y
t
t 1 t 1 i1 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 )
i1 w t
(i ) N
t
i 1
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
- Xem thêm -