Thạc Sĩ 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

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


8
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.
MỞ ĐẦU 7
Chương 1. TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY (WSN) . 9
1.1 Giới thiệu . 9
Hình 1.1 Mô hình phân tầng mạng WSN . 9
Hình 1.2 Quá trình đóng gói dữ liệu 10
1.2 Cấu trúc cho mạng cảm biến . 11
Hình 1.3 Giao tiếp không dây multihop . 11
1.2.1 Cấu trúc phẳng (Flat Architecture) 12
Hình 1.4 Cấu trúc phẳng . 12
1.2.2 Cấu trúc tầng (Tiered Architecture) . 12
Hình 1.5 Cấu trúc phân tầng 13
Hình 1.7 Cấu trúc mạng phân lớp xếp chồng vật lý . 14
Hình 1.8 Cấu trúc mạng phân cấp logic . 15
1.2.3 Lựa chọn cấu trúc cho mạng cảm biến 15
1.3 Các giao thức đặc trưng của mạng cảm biến 17
1.3.1 Giao thức đồng bộ thời gian 17
1.3.1.1 Đồng hồ trong các node cảm biến . 18
1.3.1.2 Đồng bộ thời gian trong mạng cảm biến 18
Hình 1.9 Đồng bộ bên phát-bên nhận và bên nhận-bên nhận 19
1.3.2 Giao thức vị trí 20
1.3.2.1 Định vị dựa vào mốc có sẵn 21
1.3.2.2 Định vị dựa vào vị trí tương đối . 21
1.3.3 Định tuyến trong mạng cảm biến 22
1.3.3.1 Định tuyến trung tâm dữ liệu (Data Center Protocol) 23
1.3.3.1.1 SPIN (Sensor Protocols for Information via Negotiation) . 23
Hình 1.10 Giao thức SPIN 24
1.3.3.1.2 Truyền trực tiếp Directed Diffusion 24
Hình 1.11 Các pha của giao thức truyền tin trực tiếp 25
1.3.3.2 Định tuyến phân cấp 26
Hình 1.12 Mô hình mạng LEACH 28
1.4 Kiến trúc giao thức mạng 28
Hình 1.13 Kiến trúc giao thức của mạng cảm biến 29
1.5 Lỗi trong quá trình tuyền tin . 31
Hình 1.14a Cơ chế phát lại dừng và đợi Stop and Wait ARQ . 32
Tx gửi 1 frame và đợi ACK từ Rx trước khi truyền next frame 32
Hình 1.14b Cơ chế phát lại theo nhóm Go back N ARQ 33
Tx có thể truyền liên tiếp các frame . 33
Hình 1.15 Cơ chế phát lại có lựa chọn Selective Repeat ARQ 33
Tx có thể truyền liên tiếp các frame . 33
1.6 Một số ứng dụng trong mạng cảm biến 34
1.6.1 Ứng dụng trong quân đội 35
Hình 1.16 Node cảm biến được gán lên mũ . 36
Hình 1.17 Ứng dụng mạng cảm biến trong quân đội 36
1.6.2 Ứng dụng trong môi trường 37
Hình 1.18 Ứng dụng trong môi trường 37
Hình 1.19 Cảnh báo cháy rừng 38
1.6.3 Ứng dụng trong chăm sóc sức khỏe 38
Hình 1.20 Gán node cảm biến lên cơ thể người . 39
Hình 1.21 Ứng dụng trong chăm sóc sức khỏe 40
1.6.4 Ứng dụng trong gia đình . 40


4
Hình 1.22 Ứng dụng trong gia đình . 41
1.6.5 Ứng dụng trong giao thông 41
Hình 1.23 Ứng dụng trong giao thông 41
1.7 Những khó khăn trong việc phát triển mạng WSN 42
1.7.1 Giới hạn năng lượng 42
1.7.2 Bị giới hạn về dải thông 42
1.7.3 Bị giới hạn về phần cứng . 42
Hình 1.24 Cấu trúc phần cứng của sensor . 42
1.7.4 Kết nối mạng không ổn định . 43
1.7.5 Sự kết hợp chặt chẽ giữa sensor và môi trường tự nhiên 43
Chương 2: PHÁT HIỆN VÀ SỬA LỖI TRONG MẠNG CẢM BIẾN WSN 44
2.1 Giới thiệu 44
Hình 2.1 Giao tiếp các node trong mạng cảm biến 44
Hình 2.2 Mã hoá NRZ và mã hoá Manchester 46
Hình 2.3 Mã hoá bit 46
2.2 Các loại lỗi bit . 47
47
Hình 2.4 Lỗi bit trong quá trình truyền nhận dữ liệu 47
2.3 Phát hiện lỗi . 47
Hình 2.5 Phương pháp sử dụng bit dư thừa . 48
Kiểm lỗi dư thừa tuần hoàn CRC 48
Hình 2.6 Quá trình kiểm lỗi CRC . 49
Hình 2.7 Phép chia nhị phân để tìm CRC . 50
2.4 Sửa lỗi 51
Mã Hamming . 51
Hình 2.8 Cách chèn các bit dư thừa vào dữ liệu . 51
Hình 2.9 Cách tính các bit chẵn lẻ trong mã Hamming 52
Hình 2.10 Kiểm tra các bit chẵn lẻ 53
Chương 3: MÃ ĐIỀU KHIỂN LỖI SỬ DỤNG TRONG WSN 58
3.1 Giới thiệu 58
Bảng 3.1 Sự tiêu thụ điện năng trong các node cảm biến 58
3.2 Lý thuyết về mã hoá 58
3.3 Phương pháp sửa lỗi chuyển tiếp FEC . 60
Hình 3.2 Cơ chế sửa lỗi FEC 60
Mục tiêu của phương pháp này là xây dựng nguyên tắc sửa lỗi dựa vào khoảng cách
Hamming. Trên nguyên tắc này, phương pháp sửa lỗi “kiểm tra chẵn lẻ (parity check)” được
xây dựng và tạo ra quy trình sửa lỗi tối ưu và phù hợp với công nghệ truyền tin hiện nay . 60
Xét v1 và v2 là 2 dãy nhị phân dài n bit, ta gọi khoảng cách Hamming giữa 2 dãy v1 và v2 là
số bit tương ứng khác nhau. Ký hiệu d(v1, v2) 61
Ví dụ : 61
v1 = 10101010 61
v2 = 10101111 61
Ta nhận thấy rằng bit thứ 6 và bit thứ 8 giữa v1 và v2 là khác nhau nên số bit tương ứng khác
nhau giữa v1 và v2 là 2. Do đó ta nói khoảng cách Hamming giữa v1 và v2 là 2 hay d(v1,v2)
= 2 61
Bổ đề tự sửa lỗi được ứng dụng trong FEC . 61


5
Xét bộ mã W= {w1 , w2, , ws} gồm có s từ mã nhị phân dài n bit và 1 số nguyên dương e.
61
- Nếu khoảng cách hamming nhỏ nhất dmin >= 2e+1 . 61
Khi đó thì tất cả các dãy nhận được v có thể tự sửa được tối đa e bit lỗi 61
- Nếu dmin >= 2e . 61
Thì tất cả các dãy nhận được v sẽ có khả năng phát hiện tối đa e lỗi; nếu tổng số bit lỗi < e thì
v có thể tự điều chỉnh được, nếu số bit lỗi = e thì chỉ phát hiện được lỗi và không thể điều
chính được 61
Trong bộ mã khối , gọi n là số bit trong một từ mã, k là số bit thông tin và m là bit kiểm tra
chẵn lẻ, e là số lỗi. khi đó: 61
Error! Objects cannot be created from editing field codes . 61
Điều kiện cần để bộ mã có thể tự sửa lỗi là 61
Điều kiện đủ để bộ mã có thể tự sửa lỗi (theo Vasharmov-Gilbert-Sacks) 61
Error! Objects cannot be created from editing field codes 61
Với: Error! Objects cannot be created from editing field codes . 62
Ví dụ: . 62
Mã 3 chiều (x, y, z) bắt đầu từ gốc 000. Cứ một tín hiệu t hay đổi thì mã bị đẩy đi theo 1 cạnh,
chẳng hạn : 62
000 cách 010, 001 bởi 1 cạnh . 62
011 cách 010, 111 và 001 bởi 1 cạnh 62
Như vậy, nếu ta chọn w1 = 010, w2 = 001, w3 = 111 thì khoảng cách giữa chúng là 2 ; tức là
d(w1,w2)=(w1,w3)=d(w2,w3)=2 62
Vậy nếu có lỗi phát sinh thì chỉ phát hiện chứ không sửa được 62
Như vậy ta có thể phân dạng các loại lỗi sau: . 62
- Lỗi có thể tự điều chỉnh: Gọi Error! Objects cannot be created from editing field codes.là
từ mã đúng được truyền tại nơi phát; v là từ mã nhận được tại nơi thu (truyền đúng thì wi = v).
62
Trường hợp v # w; có thể xác định và tự điều chỉnh lại lỗi khi và chỉ khi tồn tại duy nhất từ
mã Error! Objects cannot be created from editing field codes.sao cho d(vj, w*i)=min d(vj,
wi) => khi đó dựa theo nguyên tắc ngần vẫn đúng vj được gải mã về w*i 62
- Lỗi chỉ phát hiện không thể tự điều chỉnh: Trong trường hợp này tồn tại w* và w** sao cho
d(vj,w*) = d(vj,w**) = min d(vj,wi) với mọi wi thuộc W 62
=> không thể giải mã chính xác . 62
- Lỗi không phát hiện được: Trong trường hợp này ta giải mã ra w*I nhưng khác với wi đã
truyền . 62
3.3.1 Mã hoá khối tuyến tính Linear Block Codes 62
Hình 3.3 Mã hoá, truyền dẫn và giải mã dữ liệu 63
3.3.1.1 Cách mã hoá . 64
3.3.1.2 Cách giải mã . 64
Hệ phương trình này gọi là hệ phương trình giải mã 65
Do đó dữ liệu thu được ở bên nhận 65
3.3.1.3 Các phát hiện lỗi . 65
3.3.1.4 Cách sửa lỗi 66
Nếu d = 0 không lỗi 69
Suy ra không lỗi 69
Suy ra có lỗi bit thư 7 bị truyền lỗi 70
3.3.2 Kỹ thuật ghép xen Interleaving 70
Hình 3.4 Không có ghép xen dữ liệu 70
Hình 3.5 Hiệu quả của việc ghép xen dữ liệu 71
3.3.2.1 Khối xen dữ liệu 71
Hình 3.6 Đặc trưng khối xen từ bộ FEC tới kênh với D=3, N=7 72
Hình 3.7 Đặc trưng bộ giải xen từ kênh tới FEC với D=3, N=7 . 72