ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN VĂN BA
NGHIÊN CỨU MÃ ĐIỀU KHIỂN LỖI TRONG
MẠNG CẢM BIẾN KHÔNG DÂY ĐỂ NÂNG CAO
HIỆU QUẢ VIỆC SỬ DỤNG NĂNG LƯỢNG
Ngành:
Chuyên ngành:
Mã ngành:
Công nghệ Điện tử - Viễn Thông
Kỹ thuật điện tử
60 52 70
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: Pgs.Ts Vương Đạo Vy
HÀ NỘI - 2010
MỤC LỤC
MỞ ĐẦU...................................................................................................................1
Chương 1. TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY (WSN)........3
1.1 Giới thiệu....................................................................................................3
1.2 Cấu trúc cho mạng cảm biến......................................................................5
1.2.1 Cấu trúc phẳng (Flat Architecture)...............................................6
1.2.2 Cấu trúc tầng (Tiered Architecture)..............................................6
1.2.3 Lựa chọn cấu trúc cho mạng cảm biến.........................................9
1.3 Các giao thức đặc trưng của mạng cảm biến...........................................11
1.3.1 Giao thức đồng bộ thời gian.......................................................11
1.3.1.1 Đồng hồ trong các node cảm biến.................................12
1.3.1.2 Đồng bộ thời gian trong mạng cảm biến.......................12
1.3.2 Giao thức vị trí............................................................................14
1.3.2.1 Định vị dựa vào mốc có sẵn..........................................15
1.3.2.2 Định vị dựa vào vị trí tương đối....................................15
1.3.3 Định tuyến trong mạng cảm biến................................................16
1.3.3.1 Định tuyến trung tâm dữ liệu (Data Center Protocol)...17
1.3.3.1.1 SPIN (Sensor Protocols for Information via
Negotiation).....................................................................17
1.3.3.1.2 Truyền trực tiếp Directed Diffusion................18
1.3.3.2 Định tuyến phân cấp......................................................20
1.4 Kiến trúc giao thức mạng.........................................................................22
1.5 Lỗi trong quá trình tuyền tin....................................................................25
1.6 Một số ứng dụng trong mạng cảm biến...................................................28
1.6.1 Ứng dụng trong quân đội............................................................29
1.6.2 Ứng dụng trong môi trường........................................................31
1.6.3 Ứng dụng trong chăm sóc sức khỏe............................................32
1.6.4 Ứng dụng trong gia đình.............................................................34
1.6.5 Ứng dụng trong giao thông.........................................................35
1.7 Những khó khăn trong việc phát triển mạng WSN..................................36
1.7.1 Giới hạn năng lượng...................................................................36
1.7.2 Bị giới hạn về dải thông..............................................................36
1.7.3 Bị giới hạn về phần cứng............................................................36
1.7.4 Kết nối mạng không ổn định.......................................................37
1.7.5 Sự kết hợp chặt chẽ giữa sensor và môi trường tự nhiên............37
Chương 2: PHÁT HIỆN VÀ SỬA LỖI TRONG MẠNG CẢM BIẾN WSN...38
2.1 Giới thiệu..................................................................................................38
2.2 Các loại lỗi bit..........................................................................................41
2.3 Phát hiện lỗi..............................................................................................41
2.4 Sửa lỗi......................................................................................................45
Chương 3: MÃ ĐIỀU KHIỂN LỖI SỬ DỤNG TRONG WSN.........................52
3.1 Giới thiệu..................................................................................................52
3.2 Lý thuyết về mã hoá.................................................................................52
3.3 Phương pháp sửa lỗi chuyển tiếp FEC.....................................................54
3.3.1 Mã hoá khối tuyến tính Linear Block Codes..............................56
3.3.1.1 Cách mã hoá..................................................................58
3.3.1.2 Cách giải mã..................................................................58
3.3.1.3 Các phát hiện lỗi............................................................59
3.3.1.4 Cách sửa lỗi...................................................................60
3.3.2 Kỹ thuật ghép xen Interleaving...................................................64
3.3.2.1 Khối xen dữ liệu............................................................65
3.3.2.2 Kỹ thuật xen chập Convolution Interleaving.................67
3.3.3 Mã sửa lỗi kép - Double error correction codes........................68
3.4 Hiệu quả trong việc sử dụng năng lượng.................................................70
3.4.1 Kiểm tra ngoài trời......................................................................71
3.4.2 Kiểm tra trong nhà......................................................................72
Chương 4. ĐIỀU KHIỂN LỖI ỨNG DỤNG CHIPCON CC1010.....................73
4.1 Giới thiệu..................................................................................................73
4.2 Tìm hiểu chương trình truyền nhận dữ liệu trong CC1010......................74
4.2.1 Quá trình truyền dữ liệu giữa 2 nút mạng [14]:..........................74
4.2.2 Quá trình nhận dữ liệu giữa 2 nút mạng [14]:............................77
4.3 Đề xuất sử dụng FEC cho tuyến truyền nhận dữ liệu giữa các node mạng
CC1010..........................................................................................................82
4.3.1 Giả định bài toán và cách tính các từ mã....................................83
4.3.2 Chương trình truyền dữ liệu sử dụng các từ mã.........................85
4.4 Kết luận chương 4....................................................................................86
KẾT LUẬN.............................................................................................................87
TÀI LIỆU THAM KHẢO.....................................................................................88
BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT
STT
Từ viết tắt
Tên tiếng anh
1
ADC
Analogue-to-Digital Converter
3
APL
Application Layer
4
CMOS
Complementary Metal Oxide Semiconductor
5
CPU
Central Processing Unit
6
D-MAC
Data-Gathering Media Access Control
7
FEC
Forward Error Correction
8
FIFO
First-In, First-Out
9
GPS
Global Positioning System
10
I/O
Input/Output
11
LEACH
Low-Energy Adaptive Clustering Hierarchy
12
LED
Light-Emitting Diode
13
MAC
Medium Access Control
14
OS
Operating System
15
OSI
Open Systems Interconnection
16
RF
Radio Frequency
17
ROM
Read Only Memory
18
RSSI
Received Signal Strength Indicator
19
TCP
Transmission Control Protocol
21
WSN
Wireless Sensor Network
MỞ ĐẦU
Với sự phát triển không ngừng của công nghệ, con người luôn muốn ứng
dụng những công nghệ tiên tiến nhất phục vụ cho cuộc sống. Xu hướng mạnh là
phát triển các công nghệ không dây để thuận tiện hơn, các kỹ sư, nhà nghiên cứu đã
nghiên cứu những hệ thống mạng cảm biến không dây có thể nói là làm thay đổi
cuộc sống, bao gồm các cảm biến giá thành rẻ, tiêu thụ ít năng lượng và đa chức
năng đã nhận được những sự chú ý đáng kể. Hiện nay người ta đang tập trung triển
khai các mạng cảm biến để áp dụng vào trong cuộc sống hàng ngày. Đó là các lĩnh
vực về y tế, quân sự, môi trường, giao thông… Trong một tương lai không xa, các
ứng dụng của mạng cảm biến sẽ trở thành một phần không thể thiếu trong cuộc
sống con người nếu chúng ta phát huy được hết các điểm mạnh mà không phải
mạng nào cũng có được như mạng cảm biến.
Tuy nhiên mạng cảm ứng đang phải đối mặt với rất nhiều thách thức, một
trong những thách thức lớn nhất đó là nguồn năng lượng bị giới hạn và không thể
nạp lại. Hiện nay rất nhiều nhà nghiên cứu đang tập trung vào việc cải thiện khả
năng sử dụng hiệu quả năng lượng của mạng cảm biến trong từng lĩnh vực khác
nhau.
Đề tài “Nghiên cứu mã điều khiển lỗi trong mạng cảm biến không dây để
nâng cao hiệu quả việc sử dụng năng lượng” do PGS.TS Vương Đạo Vy hướng
dẫn, đã được tác giả nghiên cứu và thực hiện với mục tiêu đưa ra các phương pháp
phát hiện và sửa lỗi, từ đó đưa phương pháp phù hợp cho mạng cảm biến.
Luận văn gồm bốn chương. Chương 1 giới thiệu về mạng cảm biến WSN.
Chương 2 nghiên cứu về các phương pháp phát hiện và sửa lỗi. Chương 3 nghiên
cứu về mã điều khiển lỗi trong WSN. Dựa trên cơ sở lý thuyết chương 1, và nghiên
cứu các phương pháp phát hiện và sửa lỗi ứng dụng trong mạng cảm biến ở chương
2 và chương 3, tác giả đưa ra kết luận khách quan về hiệu quả của việc sử dụng
năng lượng.
Mặc dù đã cố gắng rất nhiều nhưng do hạn chế về tài liệu, trình độ nên tác
giả còn rất nhiều thiếu sót. Tác giả rất mong các thầy, các cô và các bạn đóng góp ý
kiến để đề tài được hoàn thiện hơn.
Trong suốt quá trình làm luận văn này, tác giả đã nhận được sự giúp đỡ của
rất nhiều người. Đầu tiên, tác giả xin trân trọng gửi lời cảm ơn đến PGS.TS Vương
Đạo Vy , người luôn tận tình chỉ bảo và giúp đỡ tác giả từ khi tác giả bắt tay vào
thực hiện đến khi hoàn thành. Không có sự hướng dẫn và giúp đỡ tận tình của thầy,
chắc chắn tác giả sẽ không thể nào hoàn thành được đề tài này.
Tác giả cũng xin chân thành cảm ơn tới gia đình, bạn bè, những người luôn
động viên tác giả trong suốt quá trình học tập và nghiên cứu để hoàn thành luận văn
này.
Học viên
Chương 1. TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY (WSN)
1.1 Giới thiệu
Một mạng cảm biến không dây WSN bao gồm nhiều node cảm biến nhỏ có
giá thành thấp và tiêu thụ năng lượng thấp, giao tiếp thông qua các kết nối không
dây có nhiệm vụ cảm nhận, đo đạc, tính toán, xử lý thông tin và các thành phần
liên lạc. Tạo khả năng quan sát, phân tích và phản ứng lại với các sự kiện và hiện
tượng xảy ra trong môi trường cụ thể nào đó. Môi trường có thể là tự nhiên hay các
hệ thống sinh học. Các ứng dụng cơ bản của mạng cảm biến chủ yếu gồm thu thập
dữ liệu, giám sát, theo dõi và các ứng dụng trong y học. Tuy nhiên ứng dụng của
mạng cảm biến tùy theo yêu cầu sử dụng còn rất đa dạng và không bị giới hạn.
Mô hình mạng cảm biến được chia thành nhiều tầng, mỗi tầng có một nhiệm
vụ riêng:
Hình 1.1 Mô hình phân tầng mạng WSN
+ Tầng ứng dụng (Application Layer): cung cấp một giao diện (interface)
đến người sử dụng.
+ Tầng hỗ trợ ứng dụng (Application Support Layer): có nhiệm vụ phân chia
và quản lý truyền thông giữa hai node đang hoạt động.
+ Tầng mạng (Network Layer): làm nhiệm vụ định tuyến truyền thông giữa
các mạng.
+ Tầng MAC (MAC Sub-Layer): thực hiện hai nhiệm vụ cơ bản đó là:
- Sử dụng các kỹ thuật đóng khung để cho phép các tầng trên truy cập môi
trường.
- Sử dụng kỹ thuật truy nhập môi trường và dò lỗi để điều khiển làm sao cho
dữ liệu được đặt vào môi trường và được nhận từ môi trường.
+ Tầng vật lý (Physical Layer): có nhiệm vụ mã hóa các bit nhị phân trong
các frame của tầng liên kết dữ liệu thành tín hiệu và thực hiện truyền và nhận các
tín hiệu này qua môi trường vật lý (môi trường không dây).
Quá trình đóng gói dữ liệu trong mạng cảm biến như sau: Dữ liệu được đưa
xuống ngăn xếp giao thức trên đường đi của nó để truyền qua môi trường mạng,
mỗi giao thức khác nhau thêm thông tin vào dữ liệu với các mức khác nhau.
Hình 1.2 Quá trình đóng gói dữ liệu
Trong mạng cảm biến không dây, các node mạng liên tục nhận và truyền dữ
liệu về các node trung tâm để xử lý. Các node trung tâm sau khi nhận được khung
dữ liệu từ các node trong mạng sẽ phải thực hiện nhiệm vụ tách các thành phần
thông tin có ích trong khung đó. Để có thể tách được các thông tin có ích thì phải
có sự đồng bộ về dạng khung dữ liệu giữa các node truyền và node trung tâm. Quá
trình đồng bộ này hoàn toàn thực hiện được vì cả bên truyền và bên nhận đều được
lập trình bởi người sử dụng. Do đó, các lập trình viên định nghĩa các dạng khung cố
định cho các khung dữ liệu được truyền trong mạng. Nhờ vậy, các node mạng có
thể phân biệt rõ các trường dữ liệu trong khung đã nhận và quá trình chọn lọc để
tách các thông tin có ích trở nên nhanh chóng và đơn giản.[10]
Khi nghiên cứu về mạng cảm biến không dây, một trong những đặc điểm
quan trọng và then chốt đó là thời gian sống của các node cảm biến hay chính là sự
giới hạn về năng lượng của chúng. Do đó khi truyền dữ liệu trong mạng cảm biến
có lỗi xảy ra, phải có cơ chế phù hợp để làm tăng thời gian sống của node mạng
lên.
1.2 Cấu trúc cho mạng cảm biến
Cấu trúc mạng cảm biến không dây cần phải thiết kế sao cho sử dụng có
hiệu quả nguồn tài nguyên hạn chế của mạng, kéo dài thời gian sống của mạng. Vì
vậy thiết kế cấu trúc mạng cần phải dựa vào những đặc thù sau:
- Giao tiếp không dây multihop: Khi giao tiếp không dây được sử dụng cho
các node mạng, thì giao tiếp trực tiếp giữa hai node sẽ có nhiều hạn chế do khoảng
cách hay các vật cản. Đặc biệt là khi node phát và node thu cách xa nhau thì cần
công suất phát lớn. Vì vậy cần các nút trung gian làm nút chuyển tiếp để giảm công
suất tổng thể. Do vậy các mạng cảm biến không dây cần phải dùng giao tiếp
multihop.
Hình 1.3 Giao tiếp không dây multihop
- Điều khiển lỗi: Nếu việc truyền dữ liệu kéo dài do gặp phải lỗi thì làm giảm
thời gian sống của mạng, để hỗ trợ kéo dài thời gian sống của toàn mạng, ta phải
đưa ra giải pháp hợp lý.
- Cộng tác, xử lí trong mạng và tập trung dữ liệu: Trong một số ứng dụng
một node cảm biến không thu thập đủ dữ liệu mà cần phải có nhiều node cùng cộng
tác hoạt động thì mới thu thập đủ dữ liệu, khi đó nếu từng node thu dữ liệu gửi
ngay đến node chính 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 node chính thì sẽ tiết kiệm
băng thông và năng lượng.[8]
Sau đây xét hai cấu trúc đặc trưng của mạng cảm biến không dây:
1.2.1 Cấu trúc phẳng (Flat Architecture)
Đây là cấu trúc đơn giản nhất, tất cả các node đều ngang hàng và đồng nhất
về hình dạng và chức năng. Các node giao tiếp qua multihop sử dụng các nút ngang
hàng làm bộ tiếp sóng. Với phạm vi truyền cố định, các nút gần hơn sẽ đảm bảo vai
trò của bộ tiếp sóng đối với một số lượng lớn nguồn.
Hình 1.4 Cấu trúc phẳng
1.2.2 Cấu trúc tầng (Tiered Architecture)
Với cấu trúc này các cụm được tạo ra giúp các tài nguyên trong cùng một
cụm gửi dữ liệu single hop hay multihop tùy thuộc vào kích cỡ của cụm đến một
node định sẵn, thường gọi là node chủ (cluster head). Trong cấu trúc này các node
tạo thành một hệ thống cấp bậc mà ở đó mỗi node ở một mức xác định thực hiện
các nhiệm vụ đã định sẵn.
Hình 1.5 Cấu trúc phân tầng
Trong cấu trúc tầng thì được chia thành nhiều cấp và mỗi cấp được phân một
chức năng cụ thể, các chức năng như cảm nhận, tính toán và đưa ra kết quả.
- Cấp thấp nhất: thực hiện tất cả nhiệm vụ cảm nhận như đo đạc áp suất,
nhiệt độ, độ ẩm, nồng độ, độ sâu,…
- Cấp giữa: thực hiện tính toán tức là thu nhận dữ liệu từ nhiều node khác
nhau rồi đưa ra quyết định.
- Cấp trên cùng: thực hiện thu thập tất cả thông tin ở cấp giữa rồi đưa thông
tin về trạng thái ban đầu như nhiệt độ, áp suất,… tại node thấp nhất đã đo được.
Hình 1.6 Cấu trúc mạng phân cấp theo chức năng
Các nhiệm vụ xác định có thể được chia không đồng đều giữa các lớp, ví dụ
mỗi lớp có thể thực hiện một nhiệm vụ xác định trong tính toán. Trong trường hợp
này, các sensor ở cấp thấp nhất đóng vai trò một bộ lọc thông dải đơn giản để tách
nhiễu ra khỏi dữ liệu, trong khi đó các nút ở cấp cao hơn ngừng việc lọc dữ liệu
này. Sự phân tích chức năng của các mạng cảm ứng có thể phản ánh các đặc điểm
tự nhiên của các node, hoặc có thể gọi đơn giản là sự phân biệt theo logic. Một tập
hợp con các node với khả năng truyền thông ở phạm vi rộng có thể tạo nên cấu hình
mạng kiểu phân lớp xếp chồng vật lý.
Hình 1.7 Cấu trúc mạng phân lớp xếp chồng vật lý
Một tập hợp con các nút trong mạng có thể được phân biệt một cách logic
khi chúng thực hiện một nhiệm vụ đại diện cho các node khác. Những chức năng
như vậy phải bao gồm sự tập trung dữ liệu, truyền thông qua mạng xương sống,
hoặc kết hợp định tuyến giữa các node. Những quy tắc logic này tạo nên mạng phân
cấp logic.
Hình 1.8 Cấu trúc mạng phân cấp logic
Những quy tắc logic này có thể thay phiên nhau định kì để đảm bảo sự công
bằng. Khi các nút với khả năng tính toán cao hơn hoạt động thì các nút ít khả năng
hơn sẽ chuyển các nhiệm vụ tính toán sang các nút này. Nếu không có “computer
servers” như vậy, một cụm các sensor cần thiết phải chọn ra một nút để thực hiện
các nhiệm vụ như là tập trung dữ liệu. Tuy nhiên trong một số trường hợp chỉ có
mỗi nút có tài nguyên vật lý thích hợp mới thích hợp để thực hiện các nhiệm vụ
định sẵn.[9]
1.2.3 Lựa chọn cấu trúc cho mạng cảm biến
Mỗi một cấu trúc mạng đều có nhược điểm của nó, tuy nhiên việc chọn ra
một cấu trúc mạng sao cho nó tối ưu nhất là vấn đề cần thiết. Mạng cảm ứng xây
dựng theo cấu trúc tầng hoạt động hiệu quả hơn cấu trúc phẳng, với các lý do như
sau:
- Cấu trúc tầng có thể giảm chi phí mạng cảm ứng bằng việc định vị các tài
nguyên ở vị trí mà chúng hoạt động hiệu quả nhất. Rõ ràng là nếu triển khai các
phần cứng thống nhất, mỗi nút chỉ cần một lượng tài nguyên tối thiểu để thực hiện
tất cả các nhiệm vụ. Vì số lượng các nút cần thiết phụ thuộc vào vùng phủ sóng xác
định, chi phí của toàn mạng vì thế sẽ không cao. Thay vào đó, nếu một số lượng lớn
các nút có chi phí thấp được chỉ định làm nhiệm vụ cảm nhận, một số lượng nhỏ
hơn các nút có chi phí cao hơn được chỉ định để phân tích dữ liệu, định vị và đồng
bộ thời gian, chi phí cho toàn mạng sẽ giảm đi.
- Mạng cấu trúc tầng sẽ có tuổi thọ cao hơn mạng phẳng. Khi cần phải tính
toán nhiều thì một bộ xử lý nhanh sẽ hiệu quả hơn, phụ thuộc vào thời gian yêu cầu
thực hiện tính toán. Tuy nhiên, với các nhiệm vụ cảm nhận cần hoạt động trong
khoảng thời gian dài, các nút tiêu thụ ít năng lượng phù hợp với yêu cầu xử lý tối
thiểu sẽ hoạt động hiệu quả hơn. Do vậy với cấu trúc tầng mà các chức năng mạng
phân chia giữa các phần cứng đã được thiết kế riêng cho từng chức năng sẽ làm
tăng tuổi thọ của mạng.
- Về độ tin cậy: Mỗi mạng cảm ứng phải phù hợp với với số lượng các nút
yêu cầu thỏa mãn điều kiện về băng thông và thời gian sống. Với mạng cấu trúc
phẳng, qua phân tích người ta đã xác định thông lượng tối ưu của mỗi nút trong
mạng là:
Trong đó:
- W là độ rộng băng tần của kênh chia sẻ
- n là số lượng node mạng
Do đó khi kích cỡ mạng tăng lên thì thông lượng của mỗi nút sẽ giảm về 0.
Việc nghiên cứu các mạng cấu trúc tầng đem lại nhiều triển vọng để khắc phục vấn
đề này. Một cách tiếp cận là dùng một kênh đơn lẻ trong cấu trúc phân cấp, trong
đó các nút ở cấp thấp hơn tạo thành một cụm xung quanh trạm gốc. Mỗi một trạm
gốc đóng vai trò là cầu nối với cấp cao hơn, cấp này đảm bảo việc giao tiếp trong
cụm thông qua các bộ phận hữu tuyến. Tóm lại, việc tương thích giữa các chức
năng trong mạng có thể đạt được khi dùng cấu trúc tầng. Đặc biệt người ta đang tập
trung nghiên cứu về các tiện ích về tìm địa chỉ. Những chức năng như vậy có thể
phân phối đến mọi nút, một phần phân bố đến tập con của các nút. Giả thiết rằng
các nút đều không cố định và phải thay đổi địa chỉ một cách định kì, sự cân bằng
giữa những lựa chọn này phụ thuộc vào tân số thích hợp của chức năng cập nhật và
tìm kiếm. Hiện nay cũng đang có rất nhiều mô hình tìm kiếm địa chỉ trong mạng
cấu trúc tầng.
1.3 Các giao thức đặc trưng của mạng cảm biến
Trong phần này ta đi sâu nghiên cứu về hai giao thức đó là giao thức đồng bộ
thời gian và giao thức vị trí. Hai giao thức này có ý nghĩa rất quan trọng trong mạng
cảm biến.
1.3.1 Giao thức đồng bộ thời gian
Vấn đề thời gian rất quan trọng trong nhiều ứng dụng và giao thức trong
mạng cảm biến. Các nút có thể đo thời gian bằng cách dùng các xung đồng hồ cục
bộ lấy từ các bộ dao động. Bởi vì các pha ngẫu nhiên làm dịch chuyển và làm trôi
tốc độ của bộ dao động, do vậy thời gian cục bộ của các nút sẽ bắt đầu sai khác đi
làm cho mạng mất đi sự đồng bộ. Do vậy việc đồng bộ thời gian có vai trò rất quan
trọng trong hoạt động của mạng cảm biến.
Đồng bộ thời gian là phương thức cho phép các thực thể riêng biệt trong một
nhóm đồng bộ xung đồng hồ của chúng hoặc đồng bộ với thời gian toàn cầu phối
hợp. Phần này sẽ giải thích tại sao cần đồng bộ thời gian và đưa ra một số giao thức
đồng bộ khác nhau.
Đồng bộ thời gian trong mạng cảm biến với các lý do sau:
- Mạng cảm biến cần liên kết với thế giới thực để biết khi nào một hiện
tượng xảy ra.
- Dịch vụ cơ bản chính của mạng cảm biến là tích hợp dữ liệu. Do đó cần
đồng bộ giữa các nút để có thể tích hợp dữ liệu truyền đến mạng.
- Một vài giao thức yêu cầu đồng bộ thời gian: quản lý cấu hình
- Các nút cảm biến thường nhỏ, giá thành thấp nên bộ dao động thường
không chính xác, hơn nữa chúng bị giới hạn về năng lượng nên thường có chế độ
sleep để tiết kiệm năng lượng.
Thời gian dùng trong mạng cảm biến phải là thời gian tự nhiên (physical
time), đó là hai nút cảm biến phải có sự cảm nhận như nhau, thời gian tự nhiên phải
được phân biệt với khái niệm về thời gian logic (logical time) là thời gian mà cho
phép quyết định việc sắp xếp các sự kiện trong hệ thống phân bố nhưng không cần
thiết phải chỉ ra bất kì sự liên quan nào đến thời gian thực.
1.3.1.1 Đồng hồ trong các node cảm biến
Hầu hết các thiết bị đồng hồ của các nút cảm biến và máy tính đều có cấu tạo
giống nhau. Mỗi nút có một bộ dao động ở một tần số xác định và một máy đếm
xung dao động. Phần mềm của các nút chỉ truy nhập tới giá trị của bộ đếm này và
thời gian giữa hai lần tăng này quyết định cách giải quyết vấn đề thời gian: các sự
kiện xảy ra giữa hai lần tăng này không thể được phận biệt từ các nhãn thời gian
của chúng.
Bộ dao động thường có độ trôi, đó là sự dịch ngẫu nhiên so với tần số trên lý
thuyết, hay còn gọi là độ lệch đồng hồ. Điều này phụ thuộc vào sự không trong suốt
của tinh thể, hay các điều kiện môi trường như áp suất, nhiệt độ… do vậy việc triển
khai mạng cảm biến trên thực tế khác nhiều so với trong phòng thí nghiệm. Độ lệch
đồng hồ được đo bằng ppm (parts per million), nó đưa ra con số về số dao động
thêm vào hoặc số dao động bị mất mà đồng hồ tạo ra trong lượng thời gian cần cho
một triệu dao động ở tốc độ lý thuyết.
Tần số dao động thay đổi theo thời gian. Có 2 kiểu thay đổi:
- Thay đổi ngắn hạn: do thay đổi nhiệt độ, do thay đổi trong điện áp nguồn
cung cấp, áp suất không khí…
- Thay đổi dài hạn: do sự lão hóa của các bộ dao động.
Người ta thường giả định tần số các bộ dao động là ổn định vừa phải trong
phạm vi từ vài phút đến vài chục phút. Điều này cũng nói lên rằng các thuật toán
đồng bộ thời gian phải đồng bộ lại vài phút một lần để theo kịp sự thay đổi của tần
số. Vì thế giao thức đồng bộ thời gian là rất cần thiết.[11]
1.3.1.2 Đồng bộ thời gian trong mạng cảm biến
Trong mạng cảm biến có một số đặc điểm mà ảnh hưởng đến yêu cầu thiết kế
của các thuật toán đồng bộ thời gian:
- Thuật toán phải phù hợp với phạm vi mạng mutilhop rộng lớn, các nút bị
ràng buộc về mặt năng lượng. Yêu cầu về phạm vi bao hàm cả số lượng các nút
trong mạng và mật độ các nút.
- Yêu cầu về độ chính xác có thể thay đổi khác nhau từ mili giây cho đến vài
giây.
- Không sử dụng thêm phần cứng chỉ giành cho mục đích đồng bộ vì tốn chi
phí và năng lượng thêm vào cho phần phụ đó.
- Mức độ di động là rất thấp.
- Hầu như không có giới hạn trên cố định về trễ truyền gói vì phụ thuộc lớp
MAC, lỗi các gói, và truyền lại.
- Trễ truyền giữa hai nút hàng xóm là không đáng kể.
Có rất nhiều giao thức đồng bộ thời gian truyền thống cố gắng giữ việc đồng
bộ giữa các nút ở mọi thời điểm nhưng lại không quan tâm đến năng lượng và cấu
hình mạng cho nên không thể áp dụng vào mạng cảm biến. Vì đặc điểm của mạng
cảm biến cho nên giao thức đồng bộ thời gian cần chú ý về các vấn đề về độ chính
xác, chi phí năng lượng và các yêu cầu về bộ nhớ.
Phương pháp cơ bản để đồng bộ thời gian trong mạng cảm biến là cộng tác
giữa các nút trong toàn mạng. Có hai cách thiết lập sự cộng tác giữa hai nút trong
mạng đó là đồng bộ giữa bên gửi và bên nhận (Sender-Receiver) và giữa bên nhận
và bên nhận (Receiver-Receiver). Đồng bộ giữa bên gửi và bên nhận yêu cầu liên
kết hai chiều giữa hai nút lân cận. Trong phương pháp đồng bộ giữa bên nhận và
bên nhận, nhiều nút nhận của các gói có nhãn thời gian như nhau đồng bộ với nhau
mà không yêu cầu đồng bộ với bên gửi.
Hình 1.9 Đồng bộ bên phát-bên nhận và bên nhận-bên nhận
+ Giao thức đồng bộ giữa bên nhận và bên phát
Trong giao thức này, một nút gọi là bên nhận, trao đổi gói dữ liệu với nút
khác gọi là bên phát, làm cho bên nhận đồng bộ với đồng hồ của bên phát. Giao
thức đồng bộ giữa bên nhận và bên phát nói chung là đòi hỏi đường nối 2 chiều
giữa các nút lân cận.
Điển hình của giao thức đồng bộ giữa bên phát và bên nhận là Lightweight
time synchronization protocol (LTS). Trong khi hoạt động nó điều khiển các nút để
sử dụng năng lượng hiệu quả, đạt được độ chính xác cao, và đưa ra những giới hạn
tương đối chính xác về các phần cứng cơ sở và các hệ thống. LTS không yêu cầu
phải update đồng hồ cục bộ và nó cũng không ước lượng tốc độ trôi thực sự.
LTS chia quá trình đồng bộ làm 2 giai đoạn:
- Giao thức đồng bộ 2 chiều để đồng bộ 2 nút lân cận.
- Để giữ các nút hoặc một tập hợp các nút cần quan tâm đồng bộ theo một
tham chiếu chung, LTS xây dựng một cây phân tán từ các nút tham chiếu đến tất cả
các nút.
+ Giao thức đồng bộ giữa bên nhận và bên nhận
Trong giao thức này nhiều bên nhận của các gói có nhãn thời gian như nhau
đồng bộ với nhau nhưng không đồng bộ với bên gửi. Chúng ta xem xét một giao
thức cơ bản đó là đồng bộ quảng bá tham chiếu RBS (Reference broadcast
synchronization).
Giao thức này bao gồm hai thành phần: thành phần đầu tiên là một tập hợp
các nút nằm trong vùng broadcast đơn, ví dụ như một tập hợp các nút có thể nghe
thấy nhau, đánh giá xung đồng hồ của các nút ngang hàng với chúng. Thành phần
thứ hai cho phép liên kết các nhãn thời gian giữa các nút ở xa với một vài khu vực
broadcast giữa chúng. Đồng bộ trong một khu vực broadcast với ý tưởng cơ bản
như sau: Bên gửi sẽ gửi theo chu kỳ một gói không cần thiết đánh dấu nhãn thời
gian vào kênh broadcast và tất cả các bên nhận sẽ đánh dấu nhãn thời gian cho gói
này. Các bên nhận trao đổi nhãn thời gian của chúng và có thể sử dụng dữ liệu này
để biết được đồng hồ của nút hàng xóm. Bằng việc lặp lại quá trình này các nút
không chỉ biết về độ lệch pha của nhau mà còn cả tốc độ trôi nữa. Các nút không
điều chỉnh đồng hồ cục bộ của nó nhưng đối với mỗi nút hàng xóm nó xây dựng
một bảng lưu trữ các tham số cần thiết để chuyển đổi giá trị xung đồng hồ.
1.3.2 Giao thức vị trí
- Xem thêm -
.PDF 
99 
182 
54 
