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


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:

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.
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.
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. 2

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. 3

- 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.

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.





Hình 1.4. Cấu trúc tầng của mạng cảm biến
4

Internet
Cấp 0: Cảm nhận
Cấp 1: Tính toán
Cấp 2: Phân phối
Nút cảm biến

Hình 1.5. Cấu trúc mạng phân cấp chức năng theo lớp

1.3
1.3.1. 
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
- 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
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ý

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.
         vòng         
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 
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

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.

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.

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.

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

60

AODV
ERS
EERS7

i gian sng ca mng dng ca nút cm bin
2.3.1.  

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
Create RREQ with
rq_min_energy = limited
End
Broadcast RREQ
Create new RREQ
t >= T Is there RREP
Yes
No
No
Add route into routing table
Send data packet to destination

Hình 2.4. Thuật toán ABR thực hiện tại nút nguồn

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 8

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
End
Send RREP
(RREP includes Rp_energy =
Destiantion_threshold_energy)
Yes

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. 9

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


(dBm).
Nút B nhận bản tin Hello, nó xác định công suất nhận tại B P
rx_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)

50
60
70
80
90
100
Topo 1 Topo 2 Topo 3 Topo 4 Topo 5


AODV
ERS
EERS
ABR
RDC
80
85
90

110
50 60 70 80 90 100


AODV
ERS
EERS
ABR
RDC
80
85
90
95
100
50 60 70 80 90 100
PDR(%)

AODV
ERS
EERS
ABR
RDC
0
50
100
150
200
50 60 70 80 90 100
Throughput (Kbps)


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nh tuyn d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 đó, P
tx_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ị

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. 11
Hình 2.13. So sánh thời gian sống của mạng khi sử dụng
AODV và PRP Hình 2.14. So sánh thông lượng của mạng khi sử dụng
AODV và PRP 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
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ư





(3.1)
0.000
20.000
40.000
60.000
80.000
100.000
60 70 80 90 100 110 120


PRP
AODV
0.000
2.000
4.000
6.000
8.000
60 70 80 90 100 110 120
Throughput (Kbps)

PRP
AODV
0.000
20.000
40.000
60.000

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.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à
()FX
, 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.7)








(3.8)














(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.13) 13

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.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à 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.

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à:

0: 1 1
( | ) ( | )
t t t t


0: 0: 0: 1: 0:
[ ( )] ( ) ( | )
t t t t t t t
E f x f x p x y dx

(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
0: 1:
( | )
tt
p x y
bằng cách lấy N điểm ngẫu
nhiên
()
0:
, 1,
i
t
x i N
. Các mẫu này được vẽ từ hàm mật độ xác suất
0: 1:
( | )
tt
p x y
, chính vì vậy ta có thể đưa ra
công thức thực nghiệm sau:

1
1
[ ( )] ( ) ( | ) ( )
N
i
t t t t t t t t
i
E f x f x p dx y f x
N




(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
0: 1:
( | )
tt
p x y
, vì
0: 1:
( | )
tt
p x y
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)



(3.22)
Trong đó
0:
w( )
t
x
được biểu thị bằng công thức sau:

0: 1: 1: 0: 0:
0:
0: 1: 1: 0: 1:
( | ) ( | ) ( )
w( )
( | ) ( ) ( | )
t t t t t
t
t t t t t
p x y p y x p x
x
x y p y x y


(3.23)
Dựa trên phương pháp Monte Carlo, nếu chúng ta chọn ra N mẫu
()
0:
{ , 1, , }
i

là trọng số chưa được chuẩn hóa. Khi đó
0:
w( )
t
x
có thể được biểu diễn như
sau:

1: 0: 0:
0:
0: 1:
( | ) ( )
w( )
( | )
t t t
t
tt
p y x p x
x
xy


(3.25)
Khi đó ta có:

0: 0: 0: 1: 0:
0:
0: 0: 0: 1: 0:
1:
0: 0: 1: 0:

0: 0: 0:
()
1
0:
1
1
( )w( )
[ ( )] ( )w( )
1
w( )
N
ii
N
t t t
i
ii
t t t t t
N
i
i
t
i
f x x
N
E f x f x x
x
N



15

Là trọng số được chuẩn hóa. Và khi đó, ta có biểu thức tương đương như sau:

( ) ( )
w =Nw
ii
tt
(3.29)
Chính vì vậy hàm mật độ xác suất hậu nghiệm
0: 1:
( | )
tt
p x y
có thể được xấp xỉ như sau:

()
0:
()
0: 1: 0: 1: 0:
1
ˆ
( | ) ( | ) w ( )
i
t
N
i
t t t t t t


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.
 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:

0: 1: 0: 1 1: 1 0: 1 1:
( | ) ( | ) ( | , )
t t t t t t t
x y x y x x y
  
  

(3.32)
Như vậy theo tính chất đệ quy ta có:

0: 1: 0 0: 1 1:
1
( | ) ( ) ( | , )
t
t t k k k
k
x y x x x y
  




(3.33)

x x x y



o Tính theo
()
w
i
t
công thức
1
1
1
( ) ( ) ( )
( ) ( )
( ) ( )
( | ) ( | )
w =w
( | , )
t t t
t
tt
i i i
t
ii
t
ii
opt t
p y x p x x
x x y

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
1
2
1
1 25
8cos(1.2 )+w
21
k
k k k
k
x
x x k
x



  

(3.34)

2
1
20
k k k
y x v
(3.35)
Trong đó, 


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) 17

Thut toán ly mu li (Resampling Algorithm)

 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 u
1
theo 







 FOR 
o 



 

  
o WHILE 



























 Bắt đầu thuật toán.
 FOR 
o Lấy mẫu 


opt t
p y x p x x
x x y





o Chuẩn hóa trọng số:
()
()
()
1
w( )
w
w( )
i
i
t
t
N
i
t
i
x
x












 END IF
Kết thúc.
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:




   
( ) ( ) ( ) ( )
11
11
,w ,w ,
NN
i i i i
t t t t t
ii
x SIR x y


   

   
   

 FOR i=1:N
o Sinh ngẫu nhiên 








o Tính theo
()
w


 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


Hình 3.9. Kết quả thuật toán SIR ứng với N = 5000, t = 150s
3.4. i tung trong mng cm bin không dây s dng b lc chm
3.4.1. Mô hình hóa bài toán
Bài toán được đặt ra là giám sát đối tượng di chuyển trong mạng cảm biến không dây. Giả sử đối tượng sẽ
di chuyển với vận tốc trong khảng 



với hướng di chuyển là bất kỳ, không biết trước. Yêu cầu xác
định vị trí của đối tượng, giảm tối đa trễ và kéo dài tối đa thời gian sống của mạng. Các mô hình được sử
dụng:
- Mô hình di chuyển của đối tượng: Như đã đề cập ở trên, giả thiết đối tượng có thể di chuyển theo hướng
bất kỳ, nhưng tốc độ di chuyển không quá nhanh. Đồng thời đối tượng có thể xuất hiện ở bất cứ đâu trong
mạng. Do tính chất di chuyển ngẫu nhiên và không theo quy luật nên rất khó có thể dùng một phương
trình nào diễn tả một cách chính xác sự di chuyển của mục tiêu. Tuy nhiên, PF không đòi hỏi phải miêu tả
chi tiết phương trình này. Cũng có một khó khăn là: tuy không miêu cả một cách chính xác được hành vi
di chuyển của đối tượng, nhưng trong một khoảng thời gian ngắn ta coi đối tượng di chuyển thẳng. mục
đích là để phục vụ cho việc thực hiện lan truyền các chất điểm trong thuật toán PF, vấn đề này được trình
bày ở phần sau.
- Mô hình đo lường: Để mô hình hóa mô hình cảm biến của nút cảm biến, giả sử giá trị đo lường là khoảng
cách giữa vị trí được cho là của mục tiêu tại thời điểm cảm biến và vị trí của nút cảm biến thực hiện phép
đo. Mô hình cảm biến này phù hợp với nhiều ứng dụng trong thực tế. Các giá trị đo lường được giả thiết
là có nhiễu. Nhiễu đo lường là nhiễu bất kỳ và có thể phi Gaussian.
- Mô hình hóa bài toán giám sát mục tiêu: Một số ký hiệu sử dụng để mô tả phương pháp thực hiện:






0
, trạng thái ước lượng 

và đám mây chất điểm Particle
Cloud từ tập thông tin đầu tiên đo đạc được. Vị trí ước lượng 

được xác định bằng giá trị được biểu diễn
cho nút cảm biến. Với khoảng cách xa hơn từ nút cảm biến tới đích, giá trị thấp được biểu diễn cho các nút
này. Sở dĩ ở đây sử dụng thuật ngữ đám mây chất điểm vì mong muốn các chất điểm sẽ phủ kín vị trí 

vừa
tính ra, và thông qua các bước lan truyền chất điểm, đám mây này sẽ luôn bao phủ tốt vị trí thực của mục
tiêu, qua đó kết quả ước lượng sẽ càng chính xác. Sử dụng một phân phối xác suất thống kê để tạo ra đám
mây chất điểm, và kèm theo đó là khởi tạo trọng số cho các chất điểm này. Cách làm này được đánh giá là
khá đơn giản và có thể chủ động thay đổi cấu trúc của đám mây chất điểm để tìm phương án tối ưu nhất.
3.4.2.2. Pha lan truyền chất điểm
Trong một số nghiên cứu trước đây, các tác giả có giới thiệu về phương pháp lan truyền chất điểm. Cách
thực hiện này quá phức tạp, đòi hỏi khối lượng truyền thông và tính toán lớn. Do vậy, luận án đề xuất một kỹ
thuật lan truyền chất điểm dựa theo lý thuyết SIS là sử dụng hàm 







. Từ hàm 




.
Sau đó tìm vận tốc  và sử dụng hàm propa_function() để quảng bá chất điểm. Và qua cách làm này, hai
bước có thể được hoàn thành: lấy mẫu 


và quảng bá trọng số 


. Hình 3.10 cho thấy sự quảng bá chất
điểm ở bước lặp t. Trong hình vẽ, vòng tròn xám nhỏ thể hiện các chất điểm, ô vuông là các vị trí của đối
tượng ở vòng lặp t-1 và t, vòng tròn với S1, S2, S3,… biểu thị các nút cảm biến. Ở thời điểm t, khi đối tượng
di chuyển đến vị trí mới với vận tốc là  thì đám mây chất điểm cũng di chuyển đến vị trí mới với vận tốc 
tương ứng. Ở bước 2.1 của thuật toán, hàm propa_function() là hàm quảng bá chất điểm.

Hình 3.10. Ví dụ về lan truyền đám mây chất điểm
Thut toán qum tc nhy thi gian t
Vào:


















1.3. Tính 











 





1.4. Vector quảng quá chất điểm: 

 


2. For 


. Cách thực hiện như sau:

















(3.39)
Trong đó 









Phương pháp tối ưu này được thực hiện trên 3 thuật toán bộ lọc chất điểm là SIS, GPF và SIR. Luận án mô
phỏng 3 trường hợp tối ưu đề xuất của bộ lọc chất điểm PF (SIS, SIR và GPF) và so sánh các kết quả với kỹ
thuật SIS-Dis đã được đề xuất trước đây. Các kết quả được trình bày như dưới đây.
3.4.2.4. Kết quả mô phỏng
Thông số mô phỏng:
- Kích thước mạng: 400x400 (m).
- Số lượng nút mạng: 400 nút.
- Băng thông kênh truyền: 250kbps.
- Chu kỳ lấy mẫu: 0.5s.
- Cự ly cảm biến: 30m.
- Cự ly truyền thông: 50m.
- Mục tiêu có quỹ đạo di chuyển bất kỳ, tốc độ di chuyển không quá nhanh.
Các thông số bộ lọc chất điểm (PF):
- Kích thước tập chất điểm: 41.
- Các thuật toán đưa ra so sánh: SIS, GPF, SIR, SIS-Dis.
Kết quả thu được:
Hình 3.11 thể hiện ước lượng tuyến đường với 3 thuật toán tối ưu đề xuất SIS, GPF và SIR và thuật toán
SIS-Dis. Kết quả đồ thị cho thấy, các phương thức đề xuất SIS, GPF, SIR cho kết quả tốt hơn phương thức
bộ lọc chất điểm phân tán SIS-Dis. Có được kết quả này là do phương pháp mới đã tăng kích thước của tập
chất điểm. Kích thước của tập này lớn hơn số đo đạc nhận được trong một chu kỳ theo dõi.

Hình 3.11. Ước lượng đường đi của đối tượng thực hiện
với các thuật toán SIS, GPF, SIR, SIS-Dis

Hình 3.12. Trễ đầu cuối khi mô phỏng các thuật toán
theo thời gian 22


23

thức LEACH-C để tập trung dữ liệu, chỉ khác nhau về kích thước vùng giám sát.
3.8
Hình 3.16. Đồ thị so sánh thời gian sống của mạng (Network lifetime) khi sử dụng mô hình giám sát toàn mạng và
giám sát theo vùng với các giao thức định tuyến khác nhau trường hợp 100 nút Hình 3.17. Đồ thị so sánh thời gian sống của mạng (Network lifetime) khi sử dụng mô hình giám sát toàn mạng và
giám sát theo vùng với các giao thức định tuyến khác nhau trường hợp 150 nút Hình 3.18. Đồ thị so sánh lượng dữ liệu gửi về trạm trong mạng khi sử dụng mô hình giám sát toàn mạng và giám sát
theo vùng với các giao thức định tuyến khác nhau trong mô phỏng 100 nút
Chúng tôi thực hiện mô phỏng so sánh 2 phương pháp giám sát theo vùng và giám sát toàn mạng trên
công cụ mô phỏng NS2.
Hình 3.16, 3.17 là đồ thị so sánh thời gian sống của mạng. Đường màu đỏ biểu diễn thông số của trường
hợp giám sát theo vùng, đường màu xanh biểu diễn thông số trường hợp giám sát toàn mạng. Nhìn vào đồ thị
ta có thể dễ dàng nhận thấy, thời gian sống của mạng trong trường hợp giám sát theo vùng cao hơn hẳn so
với trường hợp giám sát theo toàn bộ mạng. Nguyên nhân dẫn đến kết quả này là do trong trường hợp giám
0
20
40
60
80
100
120