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

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


STT

Từ viết tắt

1

ADC

3

APL

4

CMOS


LED

13

MAC

14

OS

15

OSI

16

RF

17

ROM

18

RSSI

19

TCP

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ệ


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.


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

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

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ụ đó.

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í


Trong nhiều trường hợp việc xác định vị trí của các nút trong mạng cảm biến
là rất cần thiết. Ví dụ như trong ứng dụng quan sát môi trường và khí tượng học, dữ
liệu sẽ không còn có ý nghĩa nếu như không được đánh dấu thời gian và vị trí. Hay
như trong các ứng dụng: theo dõi việc đóng gói hàng, lưu trữ sách trong thư viện,
tất cả các ứng dụng này đều cần xác định vị trí của các nút cảm biến. Ngoài ra

ảnh hưởng bởi vật chắn như nhà cửa, đồi núi,… lúc đó chúng có thể bị ảnh hưởng
bởi nhiễu môi trường hay là do sai số khi điều khiển. Hơn nữa, các nút cảm ứng
loại bình thường có thể hoạt động ở chế độ không tuyến tính hoặc nhiễu không tuân
theo phân bố Gauss. Để khắc phục những khó khăn này, các thông tin vùng được
đặt theo từng bước truyền từ nguồn cho đến đích. Để thu được các thông tin vùng
chính xác, các nút cảm ứng phải kết hợp để hỗ trợ cho nhau. Hơn nữa, năng lượng
có thể được dự trữ thêm bằng việc cho phép các nút cảm ứng dò theo vị trí của các
nút lân cận. Kỹ thuật xác định vị trí tương đối này được nghiên cứu kĩ hơn bởi cơ
cấu vị trí thụ cảm (perceptive localization framework -PLF). Trong cơ cấu này, một
nút có thể phát hiện và dò theo vị trí của của nút lân cận bằng cách dùng kỹ thuật
ước đoán kết hợp với một bộ lọc từng phần được ghép vào một dãy các sensor. Để
tăng độ chính xác của việc ước lượng vị trí, node chính có thể yêu cầu tất cả các nút
dọc theo đường từ nguồn phải lọc từng phần để tăng số lượng vật mẫu. Quá trình
tác động cục bộ này không yêu cầu bất kì một vật mốc nào. Hơn nữa, phần xử lý
trung tâm không cần phải quyết định vị trí của các nguồn. Cho dù dùng giao thức
định vị dựa trên vật mốc hay là dựa trên vị trí tương đối thì thông tin vùng đều cần
thiết trong các giao thức lớp vận chuyển, lớp mạng và lớp liên kết dữ liệu. Mỗi một
loại giao thức định vị có những yêu cầu khác nhau. Các ứng dụng mạng cảm ứng
sau này sẽ sử dụng kết hợp các kỹ thuật định vị này.
1.3.3 Định tuyến trong mạng cảm biến
Chính vì những đặc điểm riêng biệt của mạng cảm biến mà việc định tuyến
trong mạng cảm biến phải đối mặt với rất nhiều thách thức sau:
Mạng cảm biến có một số lượng lớn các nút, cho nên ta không thể xây dựng
được sơ đồ địa chỉ toàn cầu cho việc triển khai số lượng lớn các nút đó vì lượng
mào đầu để duy trì ID quá cao.
Dữ liệu trong mạng cảm biến yêu cầu cảm nhận từ nhiều nguồn khác nhau
và truyền đến node master.
Các nút cảm biến bị ràng buộc khá chặt chẽ về mặt năng lượng, tốc độ xử
lý, lưu trữ.



Protocols

for

Information via Negotiation)
Ý
tưởng của SPIN là đặt tên dữ liệu sử dụng ký hiệu mô tả ở mức độ cao hay
còn gọi là thông tin về dữ liệu (meta-data). Trước khi truyền, thông tin về dữ liệu
được trao đổi giữa các sensor qua một cơ chế thông báo dữ liệu, đó chính là đặc
điểm chính của SPIN. Mỗi một nút nhận dữ liệu mới, thông báo tới các nút lân cận


của nó và các nút lân cận quan tâm đến dữ liệu này, ví dụ như các nút mà không có
dữ liệu, lấy được dữ liệu nhờ gửi bản tin yêu cầu. Sự dàn xếp các thông tin về dữ
liệu của SPIN giải quyết được các vấn đề của flooding như là thông tin dư thừa,
chồng chéo các vùng cảm nhận, vì vậy đạt được hiệu quả về mặt năng lượng.
Có 3 bản tin được xác định trong SPIN dùng để trao đổi dữ liệu giữa các nút,
đó là bản tin ADV cho phép các nút thông báo một meta-data cụ thể, bản tin REQ
để yêu cầu các dữ liệu đặc biệt và bản tin DATA để mang thông tin thực. Hình dưới
miêu tả tổng kết lại các quá trình của SPIN.

Hình 1.10 Giao thức SPIN

Nút A bắt đầu quảng bá dữ liệu tới nút B (a). Nút B trả lời bằng cách gửi yêu
cầu tới nút A (b). Sau khi nhận dữ liệu yêu cầu (c), nút B bản tin quảng bá đến các
nút lân cận (d), sau đó các nút này gửi yêu cầu lại cho B (e-f)


Một ưu điểm của SPIN là các thay đổi về cấu hình được khoanh vùng vì thế