BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------
PHẠM TRUNG KIÊN
ĐỊNH TUYẾN TIN CẬY TRONG MẠNG CẢM BIẾN KHÔNG DÂY
Chuyên ngành: Kỹ Thuật Viễn Thông
LUẬN VĂN THẠC SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC :
TS. TRẦN THỊ NGỌC LAN
Hà Nội – Năm 2016
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi và được sự hướng dẫn
khoa học của TS. Trần Thị Ngọc Lan. Các nội dung nghiên cứu, kết quả trong đề tài này
là trung thực và chưa từng được công bố dưới bất kì hình thức nào trước đây. Ngoài ra
trong đề tài có dùng một số hình vẽ của các tác giả khác đều có trích dẫn và chú thích
nguồn gốc.
Nếu phát hiện bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về nội dung
luận văn của mình.
1.2.1. Cấu trúc của 1 node mạng WSN ...................................................................... 10
1.2.2. Cấu trúc mạng cảm biến không dây ................................................................. 11
1.3.
Kiến trúc giao thức mạng ........................................................................................ 18
1.4.
Các yếu tố ảnh hưởng đến cấu trúc mạng cảm biến ................................................ 14
1.5.
Ứng dụng của mạng WSN....................................................................................... 16
1.6.
Kết luận ................................................................................................................... 17
CHƯƠNG 2 : ĐỊNH TUYẾN TIN CẬY TRONG MẠNG CẢM BIẾN KHÔNG DÂY 18
2.1.
Giới thiệu ................................................................................................................. 18
2.2.
CÁC GIAO THỨC TRUYỀN TẢI TIN CẬY........................................................ 23
2.2.1. Giao thức RMST............................................................................................... 23
2.2.1.1. Các ví dụ .................................................................................................... 24
Kết luận ................................................................................................................... 53
CHƯƠNG 3: GIAO THỨC ĐỊNH TUYẾN EARQ ......................................................... 55
3.1.
Giới thiệu ................................................................................................................. 55
3.2.
Lý do lựa chọn nghiên cứu giao thức EARQ .......................................................... 57
3.3.
Giao thức định tuyến EARQ ................................................................................... 59
3.3.1. Thông điệp beacon và bảng định tuyến ............................................................ 59
3.3.2. Việc lựa chọn nút và chuyển tiếp gói tin .......................................................... 63
3.3.3. Xem xét lựa chọn thời gian deadline ................................................................ 65
3.4.
Thiết kế với mạng nhỏ ............................................................................................. 68
3.5.
Kết quả mô phỏng ................................................................................................... 75
3.6.
Nâng cấp giao thức EARQ trong mạng cảm biến không dây ................................. 84
GARUDA
Acknowledgement
Analog to digital converter
Congestion Detection and
Avoidance
Energy and Activity-Aware
Routing Protocol
Energy Aware Routing with
Dynamic Probability Scaling
Energy Aware Routing Protocol
Energy Aware Routing with RealTime Guarantee
Enhanced EARQ Protocol for
Reliable Routing
Event-to-Sink Reliable Transport
MAC
Achieving Effective Reliability for
Downstream Communication
Media Access Control
MMSPEED
NACK
PSFQ
PDR
PLR
QoS
RF
RMST
4
Bộ chuyển đổi tương tự ra số
Giao thức nhận biết và tránh tắc
nghẽn
Giao thức truyền tải tin cậy sự
kiện đến sink
Giao thức điều khiển truy nhập
môi trường
Giao thức gửi chậm nhận nhanh
Tỉ lệ chuyển gói tin
Tỷ lệ mất gói tin
Chất lượng dịch vụ
Sóng vô tuyến
Giao thức truyền tin cậy đa đoạn
Giao thức truyền tải tin cậy và
thời gian thực
Giao thức quản lí mạng cảm biến
Giao thức điều khiển truyền vận
User Datagram Protocol
Mạng cảm biến công nghiệp
không dây
Mạng cảm biến không dây
LỚ P KTVT-2014B
Hình 2.7: Cơ chế Open-loop hop-by-hop backpressure của CODA ................................. 32
Hình 2.8: Cơ chế closed-loop multi-source regulation ..................................................... 33
Hình 2.9: Mối liên hệ giữa độ tin cậy và tốc độ báo cáo và định nghĩa vùng hoạt động của
ESRT ................................................................................................................................. 36
Hình 2.10: Phân tích chiếm dụng bộ đệm trong ESRT ..................................................... 37
Hình 2.11: Cơ chế chuyển gói đầu tiên trong GARUDA .................................................. 41
Hình 2.12: Truyền gói đầu tiên và kiến trúc lõi trong GARUDA ..................................... 42
Hình 2.13: Cơ chế phục hồi hai bước của GARUDA ....................................................... 44
Hình 2.14: Kết quả của tần số báo cáo của chuyển tin đúng thời gian (a) và tin cậy (b) .. 49
Hình 3.1: Các nút hàng xóm trong bảng định tuyến của nút i trong WISN ...................... 60
Hình 3.2: Ví dụ cho giá trị đơn hop cho thông tin đơn hop giữa nút i và các hàng xóm của
nó, và giá trị kỳ vọng của nút hàng xóm ........................................................................... 63
Hình 3.3: Triển khai các nút cảm biến .............................................................................. 65
Hình 3.4: Ví dụ tính toán đường đi trong giao thức EARQ .............................................. 69
Hình 3.5: Hiệu suất của EARQ theo tần số của thông điệp beacon .................................. 77
Hình 3.6: Tỉ lệ các gói nhỡ deadline, xem xét duy nhất deadline ..................................... 78
Hình 3.7: Tiêu hao năng lượng trung bình của các nút, chỉ xem xét deadline .................. 78
Hình 3.8: Tỉ lệ mất các gói chỉ xem xét duy nhất độ tin cậy ............................................. 79
Hình 3.9: Tiêu thụ năng lượng trung bình của các nút ...................................................... 80
HVTH: PHẠM TRUNG KIÊN
6
LỚ P KTVT-2014B
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
Để xây dựng một mạng cảm biến không dây, rất nhiều vấn đề sẽ được quan tâm như
môi trường của mạng, đối tượng giám sát, mô hình, giao thức, giá thành,… trong đó giao
thức định tuyến trong mạng đóng vai trò quan trọng bậc nhất cho một hệ thống. Có rất
nhiều giao thức được xây dựng cho WSN với nhiều mục đích, mỗi giao thức có những ưu
nhược điểm riêng và phù hợp với đặc thù từng mạng WSNs. Một yếu tố khác cũng luôn
được đặt lên hàng đầu đó là năng lượng. Có nhiều cách để giải quyết vấn đề tiết kiệm năng
lượng, chọn một giao thức truyền tin tin cậy trong mạng là một trong số đó. Một gói tin
được truyền đi chính xác sẽ giúp tiết kiệm năng lượng cho việc phải gửi lại, một gói tin
được truyền đến tức thời sẽ giúp giảm áp lực xử lý và bộ nhớ của các nút cảm biến từ đó
cũng giúp tiết kiệm năng lượng. Đây là một trong những thách thức rất lớn cho việc xây
dựng giao thức định tuyến trong mạng WSN. Nói cách khác sử dụng giao thức định tuyến
độ tin cậy cao sẽ tối ưu về mặt hiệu năng để có thể kéo dài tuổi thọ của mạng.
Trong quá trình tìm hiểu và nghiên cứu về mạng cảm biến không dây, nhờ sự định
hướng và chỉ bảo tận tình của Ts. Trần Thị Ngọc Lan – bộ môn kĩ thuật thông tin, viện
Điện tử - Viễn thông, em đã chọn tìm hiểu về các giao thức định tuyến tin cậy trong mạng
WSN và đánh giá hiệu quả hoạt động của một trong số giao thức đó, cụ thể ở đây là giao
thức EARQ (Energy Aware Routing Protocol). Do khả năng, kinh nghiệm còn hạn chế nên
luận văn của em không thể tránh khỏi những thiếu sót. Em kính mong nhận được sự đánh
giá nhận xét của các thầy cô giáo trong hội đồng bảo vệ giúp em có thêm kỹ năng và kinh
nghiệm chuyên môn.
HVTH: PHẠM TRUNG KIÊN
8
LỚ P KTVT-2014B
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
hóa học, chuẩn đoán sự hỏng hóc của máy móc, giám sát các bác sĩ, bệnh nhân cũng như
quản lí thuốc, theo dõi, điều khiển giao thông …..
Mạng cảm biến có một số đặc điểm sau :
Có khả năng tự tổ chức, yêu cầu ít hoặc không có sự can thiệp của con người.
Truyền thông không tin cậy, quảng bá trong phạm vi hẹp và định tuyến multihop.
Triển khai dày đặc và khả năng kết hợp giữa các nút cảm biến.
Cấu hình mạng thay đổi thường xuyên phụ thuộc vào fading và hư hỏng các node.
Các giới hạn về năng lượng, công suất phát, bộ nhớ và công suất tính toán.
1.2.
Cấu trúc của mạng WSN
1.2.1. Cấu trúc của 1 node mạng WSN
Mỗi nút cảm ứng được cấu tạo bởi 4 thành phần cơ bản (hình 1.2) : đơn vị cảm biến
(sensing unit), đơn vị xử lí (processing unit), đơn vị truyền dẫn (transceiver unit) và bộ
nguồn (power unit) [4]. Ngoài ra còn có thêm các thành phần khác tùy vào từng ứng dụng
như hệ thống định vị (location finding system), bộ phát nguồn (power generator) hay bộ
phận di động (mobilizer).
Hình 1.2: Các thành phần của một nút cảm ứng
HVTH: PHẠM TRUNG KIÊN
10
LỚ P KTVT-2014B
tự động. Chẳng hạn như các nút có thể xác định vị trí địa lý của nó thông qua các nút khác
(gọi là tự định vị).
HVTH: PHẠM TRUNG KIÊN
11
LỚ P KTVT-2014B
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
Xử lý trong mạng và tập trung dữ liệu: Trong một số ứng dụng một nút cảm biến không
thu thập đủ dữ liệu mà cần phải có nhiều nút cùng cộng tác hoạt động thì mới thu thập đủ
dữ liệu, khi đó mà từng nút thu dữ liệu gửi ngay đến sink thì sẽ rất tốn băng thông và năng
lượng. Cần phải kết hợp các dữ liệu của nhiều nút trong một vùng rồi mới gửi tới sink thì
sẽ tiết kiệm băng thông và năng lượng.
Do vậy, cấu trúc mạng mới sẽ:
Kết hợp vấn đề năng lượng và khả năng định tuyến.
Tích hợp dữ liệu và giao thức mạng.
Truyền năng lượng hiệu quả qua các phương tiện không dây.
Chia sẻ nhiệm vụ giữa các nút lân cận
Các nút cảm ứng được phân bố trong một sensor field như hình 1.1. Mỗi một nút cảm
ứng có khả năng thu thập dữ liệu và định tuyến lại đến các sink. Dữ liệu được định tuyến
lại đến các sink bởi một cấu trúc đa điểm. Các sink 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.
1.3.
Internet hoặc các mạng bên ngoài khác. Giao thức vận chuyển giữa sink và người
dùng (nút quản lý nhiệm vụ) có thể là giao thức gói người dùng UDP hay giao thức
điều khiển truyền tải TCP thông qua Internet hoặc các mạng khác. Còn giao thức
giữa sink và nút cảm biến là giao thức kiểu như UDP.
Lớp mạng: Thiết kế lớp mạng trong mạng cảm biến phải theo các nguyên tắc sau:
Hiệu quả về năng lượng luôn được xem là vấn đề quan trọng hàng đầu.
Các mạng cảm biến gần như là tập trung dữ liệu.
HVTH: PHẠM TRUNG KIÊN
13
LỚ P KTVT-2014B
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
Tích hợp dữ liệu và giao thức mạng.
Phải có cơ chế địa chỉ theo thuộc tính và biết về vị trí.
Lớp liên kết dữ liệu: Lớp kết nối dữ liệu chịu trách nhiệm cho việc ghép các luồng
dữ liệu, dò khung dữ liệu, điều khiển lỗi và truy nhập môi trường. Vì môi trường có
tạp âm và các nút cảm biến có thể di động, giao thức điều khiển truy nhập môi
trường (MAC – Media Access Control) phải xét đến vấn đề công suất và phải có
khả năng tối thiểu hoá việc va chạm với thông tin quảng bá của các nút lân cận.
Lớp vật lý: có nhiệm vụ lựa chọn tần số, tạo ra tần số sóng mang, phát hiện tín hiệu,
điều chế và mã hóa tín hiệu. Băng tần ISM 915 MHZ được sử dụng rộng rãi trong
mạng cảm biến. Vấn đề hiệu quả năng lượng cũng cần phải được xem xét ở lớp vật
lý, ví dụ : điều biến M hoặc điều biến nhị phân.
ĐHBKHN
độ tích cực gần 1 tháng hoạt động. Sự tiêu tốn và tính khả thi của giám sát và thay thế pin
cho một mạng rộng, thì thời gian sống dài hơn được thiết kế. Trong thực tế, pin rất cần
thiết trong rất nhiều ứng dụng để bảo đảm mạng WSN có thể tự động sử dụng không cần
thay thế trong vài năm. Sự cải thiện của phần cứng trong thiết kế pin và kĩ thuật thu năng
lượng sẽ giúp ta một phần trong việc tiết kiệm pin.
Sự đáp ứng: Giải pháp đơn giản nhất để kéo dài thời gian sống bên ngoài là điều khiển
các node trong 1 chu kì làm việc với chu kì chuyển mạch giữa 2 chế độ: chế độ ngủ (mode
sleep) và chế độ hoạt động (mode active). Trong khi quá trình đồng bộ ở chế độ ngủ là 1
thách thức của WSN, vấn đề lớn liên quan đến nữa là chu trình ngủ 1 cách tùy ý có thể làm
giảm khả năng đáp ứng cũng như hiệu suất của các sensor.
Tính chất mạnh (Robustness) : Mục tiêu của WSN là cung cấp ở phạm vi rộng lớn, độ
bao phủ chính xác (fine-grained coverage). Mục tiêu này phổ biến ở số lượng lớn các thiết
bị không đắt tiền. Tuy nhiên các thiết bị rẻ thường kém tin cậy và thường dễ xảy ra lỗi. Tốc
độ lỗi cũng sẽ cao khi các thiết bị cảm ứng được triển khai trong các môi trường khắt khe
và trong vùng của kẻ địch. Giao thức thiết kế do đó cũng phải xây dựng kỹ xảo để có thể
đáp ứng tốt. Rất khó để chắc chắn rằng việc định dạng toàn cầu của hệ thống là không bị
hỏng với các thiết bị lỗi.
Hiệu suất: Các cải tiến của luật Moore trong công nghệ đảm bảo dung năng của thiết bị
về các mặt: xử lí nguồn, bộ nhớ - lưu trữ, thực hiện truyền nhận vô tuyến, cải thiện nhanh
chóng sự chính xác của bộ cảm biến. Tuy nhiên, vấn đề kinh tế được đặt ra ở đây là giá cả
trên một node giảm mạnh (từ hàng trăm đô la xuống còn vài cent), nó có thể làm cho dung
năng của vài node sẽ bị hạn chế ở 1 mức độ nhất định. Đó là lý do để thiết kế các giao thức
cho hiệu suất cao, nó bảo đảm rằng hệ thống tổng thì sẽ có dung năng lớn hơn so với dung
năng của các thành phần trong nó cộng lại. Các giao thức cung cấp một khả năng hợp tác
giữa lưu trữ, máy tính và các tài nguyên thông tin.
Tính mở rộng (Scalability) : WSN có khả năng hoạt động ở một vùng cực rộng (lớn
hơn 10 ngàn, thậm chí là hàng triệu node trong một giới hạn về độ dài). Có một vài hạn
chế về thông lượng và dung lượng làm ảnh hưởng đến scalability của hoạt động mạng.
Tính mềm dẻo: các phương pháp thiết kế phải phổ biến cho các hoạt động.
Cách biệt và bảo mật: Phạm vi hoạt động lớn, phổ biến rộng, nhạy của thông tin thu
được bởi vì WSN làm tăng yêu cầu chính cuối cùng là: bảo đảm sự cách biệt và bảo mật.
1.5.
Ứng dụng của mạng WSN
WSN được ứng dụng đầu tiên trong các lĩnh vực quân sự. Cùng với sự phát triển của
ngành công nghiệp điều khiển tự động, robotic, thiết bị thông minh, môi trường, y tế ...
WSN ngày càng được sử dụng nhiều trong hoạt động công nhiệp và dân dụng.
Một số ứng dụng cơ bản của WSN:
Cảm biến môi trường:
HVTH: PHẠM TRUNG KIÊN
16
LỚ P KTVT-2014B
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
Quân sự: phát hiện mìn, chất độc, dịch chuyển quân địch,…
Công nghiệp: hệ thống chiếu sáng, độ ẩm, phòng cháy, rò rỉ,…
Dân dụng: hệ thống điều hòa nhiệt độ, chiếu sáng…
Điều khiển:
Quân sự: kích hoạt thiết bị, vũ khí quân sự,…
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
CHƯƠNG 2 : ĐỊNH TUYẾN TIN CẬY TRONG MẠNG CẢM
BIẾN KHÔNG DÂY
2.1.
Giới thiệu
Trong WSN các dữ liệu quan trọng được thu thập bởi các nút cảm biến cần phải được
chuyển tin cậy tới sink để giám sát môi trường. Do tính chất nhạy với lỗi của liên kết không
dây, đảm bảo truyền dữ liệu tin cậy từ các nút cảm biến tới sink là một thách thức lớn trong
WSN. Truyền dữ liệu tin cậy là đảm bảo rằng các gói mang thông tin sự kiện đến đích.
Trong WSN truyền tin cậy có thể chia thành các mức khác nhau (xem hình 2.1):
Mức tin cậy gói hay sự kiện (packet hay event)
Mức tin cậy hop-by-hop, hay end-to-end
Độ tin cậy packet yêu cầu tất cả các gói mang thông tin cảm nhận từ tất cả các nút cảm
biến được truyền tin cậy tới sink. Trong khi đó tin cậy event đảm bảo rằng sink chỉ lấy đầy
đủ thông tin về một sự kiện chắc chắn nào đó xảy ra trong mạng thay vì gửi tất cả các gói
cảm nhận được.
Để đạt được tin cậy packet hay event trong khôi phục thông tin bị mất tại mức hop by
hop hay end-to-end thông qua việc sử dụng cơ chế truyền lại hay dự phòng. Cơ chế truyền
lại là đơn giản truyền lại những thông tin bị mất và có thể thực hiện trên cả mô hình endto-end hoặc hop-by-hop. Truyền lại end-to-end chỉ yêu cầu nút nguồn mà tạo ra gói tin
truyền lại thông tin bị mất. Truyền lại hop-by-hop cho phép các nút trung gian truyền lại
thông tin bị mất tại bộ nhớ trong bộ nhớ đệm của chúng. Trong cơ chế dự phòng, thông tin
dự phòng sẽ được thêm vào dữ liệu ban đầu cho phép nhận và khôi phục thông tin bị mất.
Giống như cơ chế truyền lại cơ chế dự phòng cũng thực hiện được trên cả hop-by-hop và
end-to-end.
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
Hình 2.2: Cơ chế truyền iACK và eACK
Quá nhiều bản tin eACK và NACK phát sinh có thể dẫn tới tắc nghẽn và lãng phí tài
nguyên mạng, những đặc điểm này hoàn toàn không phù hợp với mạng cảm biến. Mặt khác,
trong cơ chế iACK luân phiên, nút gửi sau khi truyền gói tin, sẽ lắng nghe kênh truyền xem
gói tin nó gửi đi có đến được đích không. iACK khai thác tính broadcast của kênh không
dây để tránh truyền tải thêm và lãng phí năng lượng do việc truyền thông điệp điều khiển
(eACK/NACK).
Để ngăn chặn việc chiếm dữ bộ đệm do việc truyền lại mà có thể là nguyên nhân cho
việc chậm trễ. Các gói tin cần phải truyền lại ngay lập tức khi được phát hiện là mất. Việc
truyền lại ngay lập tức sẽ làm trầm trọng thêm trong tình trạng tắc nghẽn. Điều này dẫn
đến phải có một cơ chế truyền lại thông minh. Tuy nhiên hạn chế về bộ nhớ của các nút và
HVTH: PHẠM TRUNG KIÊN
20
LỚ P KTVT-2014B
LUẬN VĂN TỐT NGHIỆP
ĐHBKHN
số lượng lớn các gói tin nên có thể không đạt được tin cậy trong các nút cảm biến. Điều đó
cho ta nghĩ đến phương pháp truyền khác dựa trên thông tin dự phòng, để giải quyết vấn
HVTH: PHẠM TRUNG KIÊN
22
LỚ P KTVT-2014B
LUẬN VĂN TỐT NGHIỆP
2.2.
ĐHBKHN
CÁC GIAO THỨC TRUYỀN TẢI TIN CẬY
2.2.1. Giao thức RMST
Giao thức truyền tin cậy đa đoạn RMST [7] là một trong những giao thức đầu tiên được
phát triển cho WSN. Mục tiêu chính của RMST là cung cấp độ tin cậy end-to end. Theo
đó, RMST được xây dựng trên giao thức truyền tin trực tiếp, và sử dụng một số chức năng
của giao thức này. Đặc biệt hơn, RMST được thiết kế như một bộ lọc có thể gắn vào giao
thức truyền tin trực tiếp. RSMT cung cấp 2 trong 3 chức năng cần thiết cho một giao thức
lớp truyền tải: vận chuyển đáng tin cậy và ghép/giải mã kênh. Ghép kênh và giải mã kênh
được thực hiện tại các nút nguồn và sink, tương ứng. Trong khi đó, RMST cung cấp cơ chế
xử lý lỗi khắp các tuyến trong mạng. Cuối cùng, RMST sử dụng trong mạng lưới bộ nhớ
đệm và đảm bảo cung cấp các dữ liệu gói được tạo bởi dòng sự kiện. RMST dựa trên cơ
chế định tuyến khuếch tán trực tiếp của một đường dẫn giữa nguồn và đích. Do đó, một giả
thuyết là các gói tin của một dòng chảy theo cùng một đường dẫn trừ khi có nút lỗi. Trong
trường hợp nút lỗi, khuếch tán trực tiếp được giả định để định tuyến lại các gói tin. Trên
cơ sở giả định này, RMST có hai chế độ hoạt động:
Chế độ không đệm: chế độ này hoạt động rất giống với giao thức lớp truyền tải
thông thường, tức là chỉ có nguồn và đích đóng vai trò cung cấp độ tin cậy. Do đó,
Hình 2.4: Phục hồi lỗi với RMST trong chế độ không đệm
Trong chế độ không đệm, truyền lại end-to-end được thực hiện để cung cấp độ tin
cậy. Trong hình 2.4(a), 4 gói tin bị mất trước khi đến sink. Sink chỉ có thể nhận các gói
tin bị mất sau khi nhận được gói 5 (xem hình 2.4 (b)). Sau đó, sink phát đi một gói
HVTH: PHẠM TRUNG KIÊN
24
LỚ P KTVT-2014B
Copyright: Tài liệu đại học ©