Luận văn 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

1 ĐẠ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: Công nghệ Điện tử - Viễn Thông Chuyên ngành: Kỹ thuật điện tử Mã ngành: 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 2 LỜI CAM ĐOAN Kính gửi : Hội đồng bảo vệ luận văn Thạc sĩ, khoa Điện Tử-Viễn Thông, trường Đại học Công Nghệ- Đại học Quốc Gia Hà Nội. Tôi tên là : Nguyễn Văn Ba Tên đề tài luận văn 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ượng” Trong thời gian dài qua quá trình nghiên cứu và học tập, tôi đã hoàn thành luận văn của mình với sự giúp đỡ của các thày, cô trong khoa và các bạn cùng lớp. Tôi cam đoan luận văn không có sự trùng lặp với các công trình khoa học, luận văn đã công bố trong và ngoài nước, đảm bảo tính trung thực, rõ ràng và trích dẫn đầy đủ trong tài liệu tham khảo. Hà Nội, tháng 05 năm 2010 Học viên thực hiện Nguyễn Văn Ba 3 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 6 Hình 3.8. Mô tả kết quả các giá trị xen dữ liệu ..................................................................... 73 3.3.2.2 Kỹ thuật xen chập Convolution Interleaving ........................................................ 73 Hình 3.9 Bộ xen chập N=7, D=3 .......................................................................................... 73 3.3.3 Mã sửa lỗi kép - Double error correction codes ...................................................... 74 Một mã Double-Error-Correcting và Triple-Error-Detecting (DEC-TED) (16,8) được đề xuất bởi Gulliver và Bhargave [5] với ma trận nhị phân P............................................................ 74 ................................................................................ 74 Ma trận sinh G được tạo ra với dạng G=[I8 , P] và ma trận chẵn lẻ H có dạng H = [PT , I8]. Nếu 1 hay 2 bit lỗi xuất hiện, syndrome s sẽ hoặc là giống với 1 cột trong H hoặc là bằng phép cộng tuyệt đối của 2 cột trong h; chỉ số của các cột này chính là vị trí của bit lỗi. ................. 75 Ví dụ:................................................................................................................................... 75 Với ma trận sinh G được cho như sau : ................................................................................ 75 Error! Objects cannot be created from editing field codes............................... 75 Error! Objects