›

Đồ án Nghiên cứu mạng cảm biến không dây-WSN và những đặc điểm sửa lỗi truyền dữ liệu - Hồ Anh Tuấn

pdf 58 trang huongle 1890
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Nghiên cứu mạng cảm biến không dây-WSN và những đặc điểm sửa lỗi truyền dữ liệu - Hồ Anh Tuấn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_nghien_cuu_mang_cam_bien_khong_day_wsn_va_nhung_dac_di.pdf

Nội dung text: Đồ án Nghiên cứu mạng cảm biến không dây-WSN và những đặc điểm sửa lỗi truyền dữ liệu - Hồ Anh Tuấn

  1. - 1 - BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o NGHIÊN CỨU MẠNG CẢM BIẾN KHÔNG DÂY – WSN VÀ NHỮNG ĐẶC ĐIỂM SỬA LỖI TRUYỀN DỮ LIỆU ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY NGÀNH CÔNG NGHỆ THÔNG TIN Sinh viên thực hiên: Hồ Anh Tuấn Giáo viên hƣớng dẫn: PGS.TS.Vƣơng Đạo Vy Mã số sinh viên: 110786 SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  2. - 2 - MỤC LỤC MỤC LỤC 2 DANH MỤC HÌNH VẼ 4 DANH MỤC TỪ VIẾT TẮT 5 LỜI CẢM ƠN 6 MỞ ĐẦU 7 CHƢƠNG 1: TỔNG QUAN MẠNG CẢM BIẾN KHÔNG DÂY 8 1.1 Cái nhìn ban đầu về WSN. 8 1.2 Nút cảm biến không dây. 8 1.2.1 Phần cứng của nút cảm biến không dây. 9 1.2.2 Chuẩn cho nút cảm biến không dây. 10 1.2.3 Phần mềm cho nút cảm biến không dây. 11 1.2.4 Một số loại nút cảm biến không dây. 12 1.3 Kiến trúc và giao thức. 13 1.3.1 Kiến trúc mạng của WSN. 13 1.3.2 Giao thức Stack. 14 1.4 Ứng dụng của WSN. 15 1.5 Các yếu tố ảnh hƣởng đến thiết kế. 17 1.5.1 Hạn chế phần cứng 17 1.5.2 Khả năng chịu lỗi. 17 1.5.3 Khả năng mở rộng. 18 1.5.4 Chi phí sản xuất. 18 1.5.5 Cấu trúc liên kết. 18 1.5.6 Phƣơng tiện truyền thông. 18 1.5.7 Năng lƣợng tiêu thụ. 19 CHƢƠNG 2: KIỂM SOÁT LỖI TRONG WSN 26 2.1 Tổng quan về vấn đề kiểm soát lỗi trong WSN. 26 2.2 Các phƣơng án kiểm soát Lỗi trong WSN. 27 2.2.1 Kiểm soát năng lƣợng 27 2.1.2 Tự động phát lại (ARQ) 28 2.1.3 Sửa lỗi trƣớc khi truyền (FEC) 28 2.1.4 ARQ lai ghép (HARQ) 35 2.2 Lợi ích của tăng khả năng phục hồi lỗi. 36 2.3 Phân tích mô hình lớp chéo. 38 SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  3. - 3 - 2.3.1 Mô hình tham chiếu của WSN. 38 2.3.2 Khoảng cách bƣớc nhẩy dự kiến. 39 2.3.3 Phân tích năng lƣợng tiêu thụ dự kiến. 41 2.3.4 Phần tích độ trễ dự kiến. 45 2.3.5 Phân tích BER và PER 46 2.4 So sánh các phƣơng án kiểm soát Lỗi trong WSN 47 CHƢƠNG 3: BÀI TOÁN KIỂM SOÁT LỖI TRONG WSN 52 3.1 Vấn đề và giải pháp trong WSN. 52 3.2 Bài toán so sánh giữa sửa lỗi và phát lại trong WSN. 53 3.2.1 Phát biểu bài toán. 53 3.2.2 Nhận định từ bài toán. 53 3.2.3 Giải quyết bài toán. 54 KẾT LUẬN 57 TÀI LIỆU THAM KHẢO 58 SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  4. - 4 - DANH MỤC HÌNH VẼ Hình 1.1. Sơ đồ cấu tạo chung của một nút cảm biến không dây. 9 Hình 1.2. Thành phần kiến trúc dạng chuẩn WirelessHART 11 Hình 1.3. Kiến trúc mạng WSN. 14 Hình 1.4. Giao thức Stack của WSN. 14 Hình 1.5. Mô hình một số dự án ứng dụng của WSN. 16 Hình 1.6. Mức độ tiêu thụ năng lƣợng của nút cảm biến MicaZ. 20 Hình 1.7. Đơn giản hóa năng lƣợng tiêu thụ cho một cặp nút. 24 Hình 2.1. Tổng quan lớp liên kết dữ liệu 27 Hình 2.2. Mô hình xử lý trong WSN. 29 Hình 2.3. Sơ đồ mã hóa byte dữ liệu. 29 Hình 2.4. Biểu đồ tần suất lỗi bít của một nút cảm biến khi phát 10000 gói và tỷ lệ lỗi gói tin mở đầu theo khoảng cách. 30 Hình 2.5. Sơ đồ quy trình giải mã - truyền - mã hóa. 32 Hình 2.6. Trung bình tỉ lệ mục tiêu nhận gói tin, đồ thị (a) ARQ (N = 7) và (b) FEC (BCH (128, 78, 7)) cho nút MicaZ. 36 Hình 2.7. So sánh hiệu quả của FEC với ARQ. 37 Hình 2.8. Mô hình tham chiếu của WSN. 38 Hình 2.9. Trung bình khoảng cách bƣớc nhẩy (MicaZ). 48 Hình 2.10. Năng lƣợng tiêu thụ của một lƣu lƣợng với ψTh (MicaZ) 48 Hình 2.11. PER Tổng thể với ψTh (MicaZ). 49 Hình 2.12. Độ trễ trung bình tổng thể với ψTh (MicaZ). 50 Hình 2.13. (a) Năng lƣợng tiêu thụ trung bình của một luồng. (b) Độ trễ tổng thể trung bình với ngƣỡng (ψTh) cho những Pt khác nhau. 51 SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  5. - 5 - DANH MỤC TỪ VIẾT TẮT Từ viết tắt Nghĩa tiếng anh Nghĩa tiếng việt ARQ Automatic Repeat Request Tự động phát lại. ADC Analog-to-Digital Converter Bộ chuyển đổi tƣơng tự sang số. BER Bit Error Rate Tỷ lệ lỗi bít. DC Drection Current Dòng điện một chiều. DSP Digital Signal Processing Xử lý tín hiệu số. ECC Error Correct Code Mã sửa lỗi. FEC Forward Error Correction Sửa lỗi trƣớc khi truyền. HARQ Hybrid Automatic Repeat Request Tự động phát lại lai ghép FEC. PLL Phase Locked Loop Vòng khóa pha. PER Packet Error Rate Tỷ lệ lỗi gói tin. SNR Signal to Noise Ratio Tỷ lệ nhiễu tín hiệu. VCO Voltage Controlled Oscillator Bộ điều khiển điện áp dao động WSN Wireless sensor networks Mạng cảm biến không dây. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  6. - 6 - LỜI CẢM ƠN Cám ơn các thầy cô giáo trƣờng Đại học Dân lập Hải Phòng, đã dạy dỗ chúng em trong nhiều năm qua. Cám ơn thầy Trần Hữu Nghị đã cho em một mái trƣờng để cho chúng em có cơ hội học đƣợc những kiến thức bổ ích để có thể trở thành một công dân có ích cho xã hội. Xin chân thành cám ơn thày cô bộ môn Tin học đã truyền đạt kiến thức về công nghệ thông tin, một môn học bổ ích, là hành trang vững chắc để em tự tin trong công việc sau này. Cám ơn thầy Vƣơng Đạo Vy, trƣờng đại học công nghệ, Đại học Quốc gia Hà Nội đã giúp đỡ em trong quá trình viết đồ án cũng nhƣ quá trình học tập trên ghế nhà trƣờng. Để em có thể đem kiến thức mình đã học đƣợc trên ghế nhà trƣờng áp dung vào thực tiễn để em có thể nhận thấy mình đã trang bị đƣợc những gì còn thiếu những gì trong hành trang của mình. Cám ơn gia đình và ngƣời thân, đã tận tình giúp đỡ, chu cấp tài chính, động viên em trong suốt thời gian học tập tại trƣờng. Xin cám ơn các bạn bè trong lớp và các bạn trong khoa cũng nhƣ sinh viên cả trƣờng đã giúp đỡ tôi trong thời gian học tập cũng nhƣ trong thời gian làm thực tập tốt nghiệp. Hải Phòng, tháng 7 năm 2011. Sinh viên Hồ Anh Tuấn SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  7. - 7 - MỞ ĐẦU Wireless Sensor Networks (WSN) hay mạng cảm biến không dây, một xu hƣớng phát triển của thời đại ngày nay. Với khả năng cảm nhận, cung cấp các thông tin thực tế và triển khai, mở rộng phạm vi dễ dàng nhờ triển khai trên mô hình mạng truyền thông không dây. WSN gồm tập hợp các nút cảm biến rất nhỏ, hoạt động độc lập nguồn nuôi và thông qua hàng loạt các nút cảm biến để nắm bắt thông tin dữ liệu.Với bộ xử lý riêng, các nút cảm biến có thể đƣợc lập trình để hoàn thành nhiệm vụ phức tạp hơn ngoài việc xử lý đơn giản nhƣ thu, phát, chuyển tiếp dữ liệu. Tuy nhiên, Một thách thức sống còn của WSN là vấn đề năng lƣợng, nó tạo nên một thách thức lớn với WSN chính là giảm thiểu tối đa tiêu thụ năng lƣợng nhằm giữ hoạt động lâu dài cho các nút mạng. Mục đích của đồ án này là cung cấp một cái nhìn tổng quan về WSN. Chƣơng 1 là sự giới thiệu toàn diện về WSN, bao gồm các nút cảm biến và kiến trúc mạng, cung cấp cái nhìn toàn diện về các đặc điểm, các yếu tố thiết kế quan trọng, và khó khăn của WSN, đồng thời đƣa ra một số ứng dụng hiện có của WSN trong quân sự, y tế, công nghiệp và ứng dụng tại nhà. Chƣơng 2 tập trung đi sâu vào các kỹ thuật kiểm soát lỗi trong WSN cũng nhƣ tác động của nó lên truyền thông, tiết kiệm năng lƣợng. Cuối cùng, chƣơng 3 giải quyết vấn đề cụ thể trong một bài toán để từ đó thấy đƣợc tầm quan trọng của sửa lỗi truyền dữ liệu trong WSN. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  8. - 8 - CHƢƠNG 1: TỔNG QUAN MẠNG CẢM BIẾN KHÔNG DÂY 1.1 Cái nhìn ban đầu về WSN. Hiện nay, công nghệ vi mạch, truyền thông không dây và điện tử kĩ thuật số phát triển ngày càng mạnh mẽ. Nhờ đó những thiết kế và quá trình triển khai với giá cả ngày càng thấp, năng lƣợng tiêu thụ đƣợc giảm thiểu đã tạo điều kiện cho những nút cảm biến đa chức năng có kích thƣớc nhỏ và giao tiếp trong khoảng cách ngắn trở nên khả thi. Khả năng của các nút cảm biến ngày càng tăng trong đó bao gồm: cảm biến, xử lý dữ liệu và giao tiếp với một lƣợng lớn các nút cảm biến. WSN cấu thành từ một lƣợng lớn các nút cảm biến, truyền thông multi-hop là chủ yếu. Do đó, nó có khả năng triển khai với quy mô lớn, tƣơng tác nhanh chóng và đáng tin cậy nhờ sự tổng hợp thông tin hiệu quả giữa các nút. Hơn nữa, không chỉ truyền thông tin thô, các nút cảm biến còn có khả năng tự xử lý tính toán trƣớc khi truyền đi. Về triển khai, mạng này cho phép triển khai một cách ngẫu nhiên do đó thích hợp với cả những vùng thiên tai và những địa hình phức tạp. Tuy nhiên, WSN vẫn còn gặp một số thách thức nhất định để trở thành một mạng hoàn thiện. Thông thƣờng các giao thức truyền thông yêu cầu cung cấp năng lƣợng với hiệu suất cao do đó chỉ tập trung vào thông lƣợng và độ trễ còn với WSN với nguồn cung cấp năng lƣợng hạn chế mà thách thức chính của nó là tìm cách để giảm năng lƣợng tiêu thụ. Qua đó mà việc phát triển WSN phải tập trung vào giảm thiểu tối đa năng lƣợng nguồn cấp. Trong chƣơng 2 sau này, yếu tố sửa lỗi trong mạng đƣợc nghiên cứu khá kĩ nhàm giải quyết vấn đề này. Những phần tiếp sau, chúng ta đi sâu vào những yếu tố quan trọng tạo lên WSN. Đó là, nút cảm biến không dây: góp phần tạo nên cơ sở hạ tầng vật lý cho WSN, kiến trúc và giao thức: yếu tố không thể thiếu trong bất kì một mạng lƣới nào. ứng dụng của WSN trong thực tế từ đó rút ra một số yếu tố ảnh hƣởng và cách giải quyết trong quá trình thiết kế và triển khai WSN. 1.2 Nút cảm biến không dây. WSN bao gồm các hệ thống nhúng có khả năng: tƣơng tác với môi trƣờng thông qua các cảm biến khác nhau, xử lý thông tin tại chỗ, giao tiếp không dây giữa các nút. Một nút cảm biến là tập hợp của phần cứng, phần mềm và chuẩn. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  9. - 9 - 1.2.1 Phần cứng của nút cảm biến không dây. Mô-đun không dây: (hay còn gọi là motes) Motes là thành phần chính của nút cảm biến. Có khả năng thu phát vô tuyến. Một motes bao gồm:  Một vi điều khiển.  Bộ phận thu phát.  Nguồn điện (thƣờng là PIN).  Đơn vị bộ nhớ.  Đầu đo cảm biến. Ngoài ra còn một số thành phần nhƣ: Bảng mạch cảm biến (sensor board): đƣợc gắn trên motes, chứa một vùng thử cho khách hàng nối các loại đầu đo cảm biến khác nhau của họ vào motes. Bảng mạch lập trình (programming board): còn đƣợc gọi là bảng cổng, cung cấp giao tiếp Ethernet, Wi-Fi, USB.Với mục đích thu thập thông tin, nhúng chƣơng trình và tải các ứng dụng cho motes. Sơ đồ cấu tạo nút cảm biến: Cụ thể hơn, nút cảm biến không dây gồm bốn thành phần chính: đơn vị cảm biến, đơn vị xử lý, đơn vị thu phát và đơn vị năng lƣợng. thể hiện trong sơ đồ (hình 1.1). Hình 1.1. Sơ đồ cấu tạo chung của một nút cảm biến không dây. Đơn vị cảm biến: thành phần chính trong nút, gồm một số cảm biến, một bộ truyển đổi tín hiệu tƣơng tự sang tín hiệu số (ADC). Nhiệm vụ, thu thập thông tin môi trƣờng, chuyển thành tín hiệu số rồi gửi về đơn vị xử lý. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  10. - 10 - Đơn vị xử lý: gồm vi xử lý và một bộ nhớ trên bo mạch. Nhiệm vụ, quản lý hoạt động của nút, chạy các thuật toán liên quan, phối hợp với các nút khác thông qua mạng tuyền thông không dây. Bộ thu phát vô tuyến: chuyển đổi các bít thông tin để truyên thông qua một tần số vô tuyến (RF) và phục hồi ở đầu kia. Đơn vị năng lượng: thành phần quan trọng nhất quyết định tuổi thọ của WSN, gồm pin hoặc có thể thêm bộ phát điện (tùy ứng dụng). Nhiệm vụ, điều phối năng lƣợng tiêu thụ của các thành phần khác kéo dài. Hệ thống định vị vị trí: gồm một mô-đun tính toán phân tán giúp xác định vị trí hoặc một GPS (nút cao cấp). Nhiệm vụ, xác định vị trí hiện tại của nút nhằm cung cấp các thông tin chính xác cho mạng. Bộ phận chuyển động: Giúp nút di chuyển dƣới sự chỉ đạo của bộ vi xử lý. Máy phát điện: gồm một thành phần thu năng lƣợng mặt trời hoặc thu năng lƣợng nhờ rung động. Nhiệm vụ, cung cấp phụ trợ cho pin trong các ứng dụng đòi hỏi thời gian hoạt động lâu. Đặc điểm: kích cớ bằng một bao diêm hoặc rất nhỏ tùy vào từng ứng dụng cụ thê, trọng lƣợng nhẹ đến rất nhẹ (có thể bay lơ lửng trong không khí). Do đó Tiêu thụ rất ít năng lƣợng, hoạt động ở mật độ cao, chi phí sản xuất thấp, tự trị, hoạt động không cần giám sát và thích nghi với môi trƣờng tốt. 1.2.2 Chuẩn cho nút cảm biến không dây. Mục đích: do sự không đồng nhất của các loại nút cảm dẫn đến không tƣơng thích giữa các mạng và các ứng dụng khác nhau. Phân loại chuẩn: IEEE 802.15.4: Truyền thông với 3 băng tần: toàn cầu (2.4GHz), Châu Mỹ (915MHz) và Châu Âu (868MHz). Tầng Vật lý, sử dụng phƣơng án điều chế binary phase shift keying (BPSK) trong dải tần 868/915MHz và offset quadrature phase shift keying (O-QPSK) trong băng tần 2.4GHz. Tầng MAC cung cấp cấu trúc liên kết dạng sao, lƣới hoặc cây. Phạm vi truyền của các nút trong 10 đến100m với tốc độ dữ liệu là 20-250 kbps. ZigBee: nổi bật ở việc gắn địa chỉ cho thiết bị khi nó tham gia mạng (địa chỉ này ngắn hơn ID của thiết bị) do vậy mà nâng cao hiệu suất truyền thông. Sử dụng kiến trúc dạng cây cho định tuyến. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  11. - 11 - WirelessHART: nổi bật với việc tạo và xác minh liên tục nhiều đƣờng dự phòng trong quá trình thiết lập mạng dẫn đến khi một đƣờng truyền từ thiết bị đến cổng bị hỏng thì sẽ đƣợc thay thế ngay, hỗ trợ quản lý băng thông động cho thiết bị bằng cách chỉ định con số thích hợp của các khe đến các thiết bị.Kiến trúc mạng: gồm 5 phần nhƣ trong hình 1.2. Hình 1.2. Thành phần kiến trúc dạng chuẩn WirelessHART 6LoWPAN: nhằm tích hợp WSN với Internet thông qua IPv6, khi tích hợp IPv6 với WSN, do kích thƣớc của Ipv6 khá lớn (40byte). Một số giải pháp đƣa ra đó là thay vì một tiêu đề đơn khối duy nhất, bốn loại tiêu đề đƣợc sử dụng theo từng kiểu gói tin đƣợc gửi đi kết hợp sử dụng kĩ thuật nén stateless để giảm kích thƣớc. 1.2.3 Phần mềm cho nút cảm biến không dây. Ngoài phần cứng và chuẩn, phần mềm cũng đƣợc phát triển riêng cho WSN. Trong số này tiêu biểu nhất là TinyOS. Đặc điểm: là hệ điều hành mã nguồn mở cho WSN. Có kích cỡ mã nhỏ, linh hoạt trong giao thức truyền thông. Hoạt động dựa trên xử lý hƣớng sự kiện. Tiện ích: TinyOS mote simulator đơn giản hóa việc phát triển các giao thức mạng cảm biến và các ứng dụng, tạo môi trƣờng mô phỏng rộng và biên dịch trực tiếp từ mã TinyOS. Cung cấp một công cụ giao diện đồ họa ngƣời dùng (TinyViz) giúp hình dung và tƣơng tác với các hoạt động mô phỏng. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  12. - 12 - Ngoài ra, còn có một số hệ điều hành khác nhƣ: - LiteOS: là một hệ điều hành đa luồng nhƣ Unix. - Contiki: là hệ điều hành đa nhiệm (nguồn mở) - Squawk: sử dụng một máy ảo JAVA, thực hiện trực tiếp ở bộ nhớ flash. 1.2.4 Một số loại nút cảm biến không dây. Hiện nay, WSN đang phát triển rất mạnh mẽ trong các lĩnh vực từ quan trọng nhƣ quân sự, công nghiệp hay y tế cho đến sử dụng tại gia đinh. Do đó có rất nhiều loại nút cảm biến không dây khác nhau ra đời và có thể chia làm hai loại: loại nút thể hệ thấp và loại nút cao cấp. Nút cảm biến thể hệ thấp: đặc trƣng bởi khả năng xử lý, bộ nhớ và khả năng truyền thông thấp. Tuy nhiên, đƣợc sử dụng phổ biến trong các ứng dụng WSN. Một số loại nút nhƣ: Họ MICA (Mica, Mica2, MicaZ), IRIS, Telos / Tmote, EYES. Đặc điểm chung: sử dụng băng tần (ISM). Ngoài ra gần đây đƣợc bổ sụng các máy thu phát CC2420 trong băng tần 2.4 GHz và tƣơng thích IEEE 802.15.4. Nút cảm biến cao cấp: đặc trƣng bởi khả năng xử lý cục bộ cao hơn, bộ nhớ nhiều hơn. Áp dụng cho những nút trung tâm xử lý - lƣu trữ. Một số loại nút nhƣ: Stargate, Stargate NetBridge, Imote, Imote2. Bảng 1.1, tổng hợp cấu hình một số loại nút cảm biến hiện nay. Bảng 1.1. Cấu hình một số loại nút cảm biến không dây. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  13. - 13 - (a) Trang bị hai bộ thu phát: Bluetooth và một radio năng lƣợng thấp. (b) Phụ thuộc vào các thiết bị truyền thông đƣợc kết nối. 1.3 Kiến trúc và giao thức. WSN hình thành bởi tập hợp rất lớn các nút cảm biến, và hoạt động trên sự kết hợp của những nút này. Do đặc điểm của ứng dụng mà các nút trong mạng phân tán trong một vùng tƣơng đối rộng. Trong mục này, làm rõ kiến trúc và giao thức sử dụng trong WSN. 1.3.1 Kiến trúc mạng của WSN. Các nút cảm biến đƣợc phân tán trong một vùng cảm biến nhƣ hình 1.3, mỗi nút đều có khả năng thu thập và truyền dữ liệu về nút cơ sở (hay còn gọi là sink) và đến ngƣời dùng cuối. Dữ liệu đƣợc truyền thông qua kiến trúc multi-hop. Sink có thể giao tiếp với tác vụ quản lý/ngƣời dùng cuối thông qua Internet, vệ tinh hoặc bất kì loại mạng Wifi, mesh networks, cellular systems, WiMAX. Có thể có nhiều sink/cổng và ngƣời dùng cuối. Các nút thành viên: (với 2 chức năng)  chức năng nguồn dữ liệu: nút thực hiện truyền tải gói dữ liệu về sink.  chức năng định tuyến: tham gia vào chuyển tiếp gói tin nhận đƣợc từ các nút khác đến nút tiếp theo trong đƣờng dẫn multi-hop để tới sink. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  14. - 14 - Hình 1.3. Kiến trúc mạng WSN. 1.3.2 Giao thức Stack. Đƣợc sử dụng ở sink và tất cả các nút cảm biến nhằm kết hợp: năng lƣợng với định tuyến, tích hợp dữ liệu với giao thức mạng, truyền thông hiệu quả với phƣơng tiện không dây và giao tiếp giữa các nút. Thành phần của giao thức: (thể hiện trong hình 1.4) Hình 1.4. Giao thức Stack của WSN.  Tầng vật lý: giải quyết nhu cầu về kĩ thuật điều chế, truyền và nhận. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  15. - 15 -  Tầng liên kết dữ liệu: bảo đảm thông tin liên lạc đáng tin cậy, sử dụng kỹ thuật kiểm soát lỗi sẽ đƣợc nêu ra trong chƣơng 2 và quản lý truy cập kênh giảm thiểu va chạm.  Tầng mạng: quan tâm đến việc định tuyến gói dữ liệu.  Tầng vận chuyển: duy trì lƣu thông dữ liệu trong mạng với UDP.  Tầng ứng dụng: quản lý các ứng dụng, quản lý mạng, xử lý truy vấn, chứa các mã ứng dụng. Các chức năng quản lý, định vị, đồng bộ đều nhằm mục tiêu: gắn kết các nút cảm biến trong mạng lại với nhau, sử dụng năng lƣợng hiệu quả, chia sẻ tài nguyên mạng và giúp mở rộng mạng cảm biến. Giải pháp lớp chéo trong WSN: nhằm tích hợp chặt chẽ các giao thức trong lớp stack. Bằng cách loại bỏ giới hạn giữa các lớp cũng nhƣ các giao diện liên quan giữa chúng, nhằm tăng hiệu quả trong không gian và điều khiển. Nó nêu lên: - Mỗi nút đƣợc trang bị một thiết bị đo xung nhịp cục bộ. - Cảm biến ,xử lý, truyền thông đƣợc liên kết, kiểm soát bởi xung nhịp cục bộ. - Thời gian truyền thông dữ liệu ở từng nút đƣợc nhất quán. - Thông tin thu phát phải kết hợp với vị trí của nút tạo ra. - Giao thức truyền thông phải có thông tin vị trí. 1.4 Ứng dụng của WSN. Các ứng dụng của WSN ngày càng phát triển bởi những khả năng đặc biệt của nó, kích thƣớc các nút mạng rất nhỏ có thể triển khai trong bất kì môi trƣờng hay địa hình phức tạp nào, hoạt động tự do không cần nguồn cấp cố định do đƣợc tích hợp sẵn nguồn nuôi, tự xử lý cục bộ giúp cung cấp thông tin và thao tác nhanh chính xác với các hiện tƣợng mà nó theo dõi, đáp ứng đƣợc những yêu cầu phức tạp của các ứng dụng nhờ khả năng tích hợp đƣợc rất nhiều loại cảm biến nhƣ nhiệt độ, ánh sáng, gia tốc, âm thanh,v.v. Một số lĩnh vực đã triển khai ứng dụng của mạng cảm biến không dây: quân sự, y tế, công nghiệp, môi trƣờng và tại nhà. Một số ứng dụng đƣợc thể hiện trong hình 1.5. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  16. - 16 - Hình 1.5. Mô hình một số dự án ứng dụng của WSN. Trong quân sự: nhằm mục tiêu tiếp cận chiến trƣờng tốt hơn giảm thiệt hại cho con ngƣời và trang thiết bị. Một số ứng dụng của nó nhƣ: theo dõi các lực lƣợng thân thiện, thiết bị và đạn dƣợc, giám sát chiến trƣờng, trinh sát địa hình của lực lƣợng thù địch, phát hiện và tấn công trinh sát, mục tiêu, đánh giá thiệt hại trận chiến do vũ khí sinh học, hóa chất, hạt nhân. Trong y tế: nhằm mục đích hỗ trợ ngƣời bệnh, bệnh viện hay nghiên cứu y sinh nhƣ cung cấp giao diện cho ngƣời tàn tật, theo dõi tổng hợp bệnh nhân, chẩn đoán, quản lý thuốc tại các bệnh viện, giám sát các dữ liệu sinh lý con ngƣời, theo dõi chuyển động của côn trùng hay vi sinh vật. Trong công nghiệp: nhằm tăng khả năng tự động hóa trong công việc nhƣ quản lý hàng tồn kho, giám sát chất lƣợng sản phẩm, giám sát giao thông vận tải, kiểm soát quy trình sản xuất và tự động hóa, phát hiện và theo dõi hành vi trộm cắp xe; theo dõi và phát hiện xe, văn phòng thông minh, điều khiển robot, hƣớng dẫn trong các môi trƣờng sản xuất tự động, bảo tàng tƣơng tác. Trong môi trường: theo dõi chuyển động của các loài chim, động vật nhỏ, côn trùng, theo dõi môi trƣờng ảnh hƣởng đến cây trồng, chăn nuôi, thuỷ lợi, theo dõi tình trạng trái đất, thăm dò các hành tinh, giám sát môi trƣờng đất, biển, và khí quyển, phát hiện cháy rừng, khí tƣợng hoặc nghiên cứu địa vật lý, phát hiện lũ, lập bản đồ môi trƣờng và nghiên cứu ô nhiễm. Tại nhà: Các nút cảm biến không dây thông minh có thể gắn bên trong các thiết bị nhƣ máy hút bụi, lò vi sóng, tủ lạnh, và đầu DVD cũng nhƣ hệ thống nƣớc kết nối với mạng bên ngoài thông qua Internet hoặc vệ tinh. Cho phép ngƣời dùng dễ dàng hơn trong quản lý các thiết bị trong nhà từ xa. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  17. - 17 - 1.5 Các yếu tố ảnh hƣởng đến thiết kế. Nhƣ phần trƣớc đã đề cập, WSN hiện nay đang phát triển khá mạnh mẽ trên mọi lĩnh vực. Nhƣng chính vì thế mà những nhà phát triển ứng dụng của mạng này lại phải đối mặt với những thách thức không hề nhỏ. Phần này, đi sâu vào những yếu tố ảnh hƣởng tạo nên những thách thức trong thiết kế WSN. Các yếu tố đó là: hạn chế phần cứng, khả năng chịu lỗi, khả năng mở rộng, chi phí sản xuất, cấu trúc liên kết bộ cảm biến mạng, truyền thông và tiêu thụ điện năng. Trong đó, yếu tố tiêu thụ năng lƣợng quyết định đến sự sống còn của WSN. 1.5.1 Hạn chế phần cứng. Thách thưc: - Kích cỡ quá nhỏ mà yêu cầu ứng dụng cao. - Nguồn năng lƣợng pin quá ít. - Điện năng nuỗi ăng-ten và bộ thu phát là rất lớn. - Tuyền thông qua tần số vô tuyến khả năng mất mát, hỏng thông tin. - Bộ nhớ và bộ xử lý cấu hình vẫn còn thấp. Giải pháp: bổ sung máy phát điện cho mỗi nút trong mạng, thiết kế bộ thu phát với khả năng bật tắt lúc cần thiết, sử dụng thiết bị truyền thông cao cấp hơn, sử dụng phần mềm dung lƣợng thấp và thuật toán xử lý tối ƣu nhất. 1.5.2 Khả năng chịu lỗi. Yếu tố lỗi mạng sinh ra do những hạn chế của phần cứng và môi trƣờng ứng dụng. Một số lý do: thiếu điện, hỏng hóc do tác động của môi trƣờng và lỗi phần mềm. Quan trọng nhất là do các nút đƣợc cung cấp nguồn nuôi chủ yếu là pin dẫn đến năng lƣợng không đủ làm các nút ngƣng hoạt động. Khả năng chịu lỗi hiểu là khả năng mạng vẫn hoạt động bình thƣờng ngay khi có một vài lỗi nào đó xẩy ra. Thách thức: do pin với năng lƣợng ít, vi xử lý với khả năng chƣa cao, bộ nhớ thấp dẫn đến lỗi khi chạy phần mềm và làm cho nút ngƣng hoạt động. Ngoài còn tác động của nhiều loại môi trƣờng. Giải pháp: xây dựng mạng với mật độ các nút cao. Tức là nhiều nút trong một phạm vi phát sóng. Một nút bị hỏng thì có nút khác phát thay thế ngay. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  18. - 18 - 1.5.3 Khả năng mở rộng. Do nâng cao khả năng chịu lỗi của mạng, giải pháp tăng khả năng chịu lỗi đƣợc đƣa ra ở trên lại tạo ra một thách thức khác cho thiết kế WSN là với mật độ nút cao trong một phạm vi dẫn đến khi mở rộng mạng cần một lƣợng rất lớn các nút cảm biến (hàng trăm đến hàng nghìn nút). chính vấn đề này đã tạo ra một thách thức nan giải cho những nhà thiết kế, đó là làm sao để kiểm soát và điều khiển một lƣợng lớn các nút này hoạt động cách hiệu quả. 1.5.4 Chi phí sản xuất. WSN là tập hợp của một lƣợng lớn các nút cảm biến, do vậy chi phí để tạo ra một nút mạng là rất quan trọng để đƣa ra giá cả tổng thể cho toàn mạng. nếu chi phí này đắt hơn chi phí cho những thiết bị cảm biến truyền thống thi nó sẽ không đƣợc sử dụng. Hiện nay giá cả của một nút cảm biến vẫn khá cao (hơn 10$) trong khi yêu cầu mạng sẽ chỉ triển khai thực tế đƣợc với giá một nút là 1$. Do đó đây cũng là một thách thức khó khăn cho những nhà thiết kế WSN. 1.5.5 Cấu trúc liên kết. Số lƣợng lớn các nút cảm biến không thể truy cập, giám sát và thƣờng xuyên bị lỗi làm việc duy trì cấu trúc liên kết là một công việc đầy thử thách. Quá trình nghiên cứu cấu trúc liên kết của WSN thông qua ba giai đoạn: giai đoạn trƣớc và trong triển khai, giai đoạn hậu triển khai và giai đoạn tái triển khai. Trước và trong triển khai: phân bố hàng loạt bằng máy bay, tên lửa, hoặc đặt từng nút một bằng ngƣời hoặc robot. Cần một kế hoạch thiết kế cẩn thận nhằm : giảm chi phí lắp đặt ban đầu, tăng sự linh hoạt, tự tổ chức và chịu lỗi của mạng. Giai đoạn hậu triển khai: cấu trúc liên kết mạng thay đổi do nhiều nguyên nhân, do đó cần nhƣng giao thức mạng linh động có khả năng thay đổi ngắn hạn, định kỳ, và dài hạn trong các cấu trúc liên kết. Giai đoạn tái triển khai: bổ sung, thay thế các nút hỏng, thay đổi hoạt động theo yêu cầu ứng dụng. 1.5.6 Phƣơng tiện truyền thông. Hoạt động thành công của WSN phụ thuộc vào sự truyền thông tin cậy giữa các nút mạng. Chúng có thê truyền thông với nhau thông qua: radio, hồng ngoại, quang học, âm thanh hoặc cảm ứng từ. Nhƣng để thành một mạng lƣới rông khắp nó cần một phƣơng tiện có sẵn cho cả thế giới và băng tần ISM đƣợc chọn. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  19. - 19 - Đặc điểm: ISM đƣợc cấp giấy phép miễn phí, có sẵn ở khắp thế giới, không rằng buộc tiêu chuẩn cụ thể, tự do sử dụng các giao thức. Theo đó băng tần hiện nay sử dụng là ISM 2.4GHz trên toàn thế giới, ngoài ra băng tần ISM 433MHz ở châu Âu và băng tần ISM 915MHz ở Bắc Mỹ. Tần ISM trong bảng 1.2. Bảng 1.2. Tần số ISM. Hạn chế: có thể nhiễu tín hiệu từ các ứng dụng khác, do không đƣợc quy định dùng riêng cho WSN nên các mạng không dây khác cũng có can thiệp vào nó. Ngoài ra, Hồng ngoại cũng đƣợc sử dụng do đƣợc cấp miễn phí, chi phí rẻ và xây dựng dễ dàng. Tuy nhiên khoảng cách truyền thông ngắn thích hợp với các ứng dụng trong môi trƣờng khắc nhiệt. Âm thanh, sử dụng trong ứng dụng hàng hải. 1.5.7 Năng lƣợng tiêu thụ. Trong WSN, năng lƣợng tiêu thụ quyết định đến sự sống còn của mạng. Trong mục này, giới thiệu công thức tính toán để xác định mức năng lƣợng tiêu thụ trong mạng WSN. Một nút cảm biến không dây thông thƣờng chỉ đƣợc trang bị nguồn nuôi là Pin (0.5Ah <, 1.2V), mặt khác với hầu hết các ứng dụng của WSN thì việc bổ sung nguồn nuôi là không thể thực hiện đƣợc. Vì vậy, cần phân tích hoạt động tiêu thụ năng lƣợng của các nút trong WSN để sử dụng hiệu quả nó hiệu quả. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  20. - 20 - Các hoạt động của một nút cảm biến: - Khởi tạo dữ liệu: nút thu thập thông tin, xử lý chúng tạo dữ liệu khởi đầu. - Định tuyến dữ liệu: các nút chuyển dữ liệu khởi đầu đến các nút lân cận để đƣa đến sink (theo quy định định tuyến). Công việc tiêu thụ năng lượng: (rút ra từ hai hoạt động trên)  Cảm biến.  Truyền thông. (tiêu tốn năng lƣợng nhất thể hiện trong hình 1.6)  Xử lý dữ liệu. Hình 1.6. Mức độ tiêu thụ năng lƣợng của nút cảm biến MicaZ. 1.5.7.1 Năng lƣợng tiêu thụ cho cảm biến. Mức độ tiêu thụ năng lƣợng cho cảm biến tùy thuộc ứng dụng cụ thể nhƣ: một ứng dụng thu thập thông tin từng đợt mất ít năng lƣợng hơn thu thập thƣờng xuyên, sự kiện cảm biến phức tạp sẽ tốn năng lƣợng nhiều hơn sự kiện đơn giản hay nhiễu nhiều sẽ làm nút tiêu thụ năng lƣợng nhiều hơn. Nhƣng nhìn chung, trong mỗi đơn vị cảm biến có một hệ thống con gồm: một thiết bị khuếch đại tạp âm thấp, một bộ lọc khử răng cƣa, một ADC và một bộ xử lý tín hiệu số (DSP). Có thể tính đƣợc năng lƣợng tiêu thụ do cảm biến thông qua công thức 1.1. (1.1) Trong đó, Fs là tỷ lệ lấy mẫu, ENOB là số bit hiệu quả (hay độ phân giải). SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  21. - 21 - Tính chính xác của dữ liệu quyết định bởi tỷ lệ lấy mẫu. Tăng tỷ lệ lấy mẫu cũng sẽ cung cấp độ phân giải tốt hơn. Ví dụ: với một ứng dụng cảm biến nhiệt độ: Tỷ lệ lấy mẫu = 1ms không phù hợp khi nhiệt độ thay đổi theo phút hay giờ. Độ phân giải tăng lên 8bit - 10bit, ADC phải tinh vi hơn và gia tăng hoạt động cho một đơn cảm biến. Theo đó, năng lƣợng tiêu thụ tăng lên. 1.5.7.2 Năng lƣơng tiêu thụ cho xử lý. Theo tính toán, chi phí năng lƣợng của truyền một gói 1 (KB) trong khoảng cách 100 (m) là xấp xỉ bằng thực hiện 3.000.000 (chỉ thị) bởi một vi xử lý. Do đó, việc xử lý tại chỗ đƣợc áp dung trong WSN. Với vi xử lý với công nghệ bán dẫn (CMOS) rất thích hợp với các nút cảm biến yêu cầu nhỏ và rẻ của WSN. Công thức 1.2 (xác định mức năng lƣợng tiêu thụ cho xử lý Ep). (1.2) Trong đó, : năng lƣợng tiêu hao của thiết bị chuyển mạch bán dẫn. (N: số xung nhịp đồng hồ, C: tổng điện dung chuyển đổi, Vdd: điện áp cung cấp), : năng lƣợng tiêu hao do rò rỉ với mặt đất ( I0: sự rò rỉ hiện thời, n: là hằng số liên quan tới phần cứng vi xử lý, VT: ngƣỡng điện áp, f: tần số xung nhịp). Từ đó, ta có thể kiểm soát đƣợc Vdd và f. Thành phần f có thể đƣợc tính toán qua độ trễ cổng Tg (gate delay) trong công thức 1.3. Độ trễ cổng, phụ thuộc vào điện áp cung cấp, giảm điện áp cung cấp làm tăng độ trễ cổng có thể giảm thời gian nhàn rỗi cho bộ vi xử lý. (1.3) (K và a: biến phụ thuộc vào bộ vi xử lý (a ~ 2), Vth: điện áp tối thiểu) Nếu bộ vi xử lý hoạt động ở một ( f ) tƣơng ứng với thời gian chuyển tiếp cổng T0=1/f trong đó bộ vi xử lý có nhiệm vụ duy nhất là xử lý. Khi Tg < T0, bộ xử lý đƣợc nhàn rỗi khi hoàn tất một công việc cho đến khi công việc tiếp theo. Tử đó, f đƣợc đƣợc tính bằng công thức 1.4. (1.4) SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  22. - 22 - Giải pháp tiết kiệm năng lượng: từ những công thức trên. - Giảm Vth có thể giảm đƣợc Vdd mà không ảnh hƣởng đến xử lý. - Giảm f trong suốt thời gian hoạt động, chỉ tổn thất điện năng do dòng rò rỉ. - Giảm Vdd làm giảm sự rò rỉ tối đa. - Tìm mốc năng lƣợng tiêu thụ cao nhất để kiểm soát điện áp hoạt động. 1.5.7.2 Năng lƣợng tiêu thụ cho truyền thông. Một nút cảm biến không dây bỏ ra phần lớn năng lƣợng cho truyền thông. Theo phân tích, năng lƣợng mất đi nhiều nhất cho quá trình thu, phát và rò rỉ, mặt khác ở trạng thái ngủ nó lại tiết kiệm đến 99.99%. Thành phần tiêu thụ năng lƣợng chính trong truyền thông là bộ thu phát vô tuyến do đó cần xem xét thành phần này. Bộ thu phát: gồm bộ trộn, bộ tổng hợp tần số, bộ điều khiển điện áp dao động (VCO), vòng khóa pha (PLL), bộ giải điều chế và bộ khuếch đại năng lƣợng. Mô hình đơn giản: năng lƣợng tiêu thụ trong truyền thông (Pc), là cung cấp cho truyền và nhận thông tin, dữ liệu. thể hiện trong công thức 1.5 dƣới đây. (1.5) (Po: năng lƣợng đầu ra bộ khuếch đại, Prx và Ptx: năng lƣợng cho thu và phát). Theo công thức thì: - Po+Ptx : là năng lƣợng tiêu thụ của nút phát. - Prx : là năng lƣợng tiêu thụ của nút thu. Mô hình tổng thể: ngoài việc thu và phát, nút cảm biến còn tiêu thụ năng lƣợng trong chuyển trạng thái thức–ngủ và khởi động phần cứng. đồng thời cung mất năng lƣợng cho thiết bị chuyển mạch thực hiện. Thể hiện ở công thức 1.6. (1.6) Trong đó, Ec: năng lƣợng tiêu thụ tổng thể; Est: năng lƣợng tiêu thụ cho khởi động; Esw: năng lƣợng tiêu thụ cho thiết bị chuyển mạch; Erx và Etx: năng lƣợng tiêu thụ cho thu và phát. Năng lượng tiêu thụ cho khởi động: (1.7) Trong đó, PLO: năng lƣợng tiêu thụ của bộ tổng hợp tần số và VCO; tst: thời gian cần để khởi động nút. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  23. - 23 - Năng lượng tiêu thụ cho thiết bị chuyển mạch: (1.8) Trong đó, (tsw): thời gian chuyển đổi. Năng lượng tiêu thụ cho thu nhận thông tin: (1.9) Trong đó, PRX: năng lƣợng tiêu thụ của bộ khuếch đại, bộ trộn, và bộ giải điều chế; (trx): thời gian thu một gói tin. Năng lượng tiêu thụ cho phát thông tin. (1.10) Trong đó, PPA: năng lƣơng tiêu thụ cho bộ khuếch đại (không đáng kể) và bộ khuếch đại điện năng; (ttx): thời gian phát một gói tin. Năng lượng tiêu thụ cho bộ khuếch đại: (1.11) Trong đó, η: năng lƣợng hiệu quả của các bộ khuếch đại; Pout: năng lƣợng tạo ra từ bộ khuếch đại; γPA: là một yếu tố phụ thuộc vào ăng ten; d: khoảng cách truyền thông; r: tốc độ dữ liệu; n: số mũ trong công thức thể hiện sự mất mát. Yếu tố phụ thuộc ăng ten: là Bƣớc sóng, nhiệt độ làm nảy sinh tạp nhiễu cho thiết bị, tỷ lệ nhiễu tín hiệu (SNR). Chu trình giao tiếp: khi mà một nút truyền một gói tin đến một nút lân cận và nhận một phản ứng trở lại, bao gồm khởi động của bộ thu phát vô tuyến, truyền tải gói dữ liệu, chuyển đổi từ chế độ phát sang chế độ thu, và tiếp nhận gói tin. Kết quả là, mức tiêu thụ năng lƣợng tổng thể theo công thức 1.12. Thay các công thức 1.7, 1.8, 1.9, 1.10, 1.11, vào 1.6 ta đƣợc: (1.12) Giả sử tRX = tTX = lPKT / r, với lPKT là độ dài gói tin, ta đƣợc mức tiêu thụ năng lƣợng tổng thể là: (1.13) Từ công thức 1.13, thấy rằng việc tiêu thụ năng lƣợng cho truyền thông có ba thành phần chính: : không đổi và phụ thuộc vào các mạch thu phát. : độc lập với khoảng cách truyền thông (d) nhƣng có thể đƣợc SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  24. - 24 - điều khiển thông qua các kích thƣớc gói hoặc tốc độ truyền. (Hai thành phần này là các thành phần độc lập với năng lƣợng tiêu thụ) : phụ thuộc vào khoảng cách truyền thông cũng nhƣ chiều dài gói và có thể đƣợc điều khiển thông qua giao thức lớp cao hơn nhƣ là MAC và các giao thức định tuyến. Tính toán đơn giản cho tiêu thụ năng lượng trong truyền thông: Đƣợc đơn giản hóa cho một cặp nút thu-phát với khoảng cách truyền thông d. thể hiện trong hình 1.7. d Hình 1.7. Đơn giản hóa năng lƣợng tiêu thụ cho một cặp nút. Theo mô hình, năng lƣợng tiêu thụ do phát phụ thuộc vào thiết bị truyền điện tử và bộ khuếch đại truyền. Năng lƣợng tiêu thụ do thu chỉ phụ thuộc vào thiết bị thu điện tử. Từ đó ta có thể mô hình hóa nó dƣới dạng công thức 1.14. (1.14) Trong đó, Etx(k, d) và Erx(k): năng lƣợng tiêu thụ của nút phát và nút thu. và . Với ETX-elec và ERX-elec là năng lƣợng tiêu thụ trên mỗi bit cho nút phát và thu; eamp: năng lƣợng tiêu thụ trên mỗi bit trên bộ khuếch đại điện năng (phụ thuộc d). SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  25. - 25 - Thông qua những phân tích và công thức tính toán, có thể thấy năng lƣợng dành cho truyền thông trong WSN là rất lớn, trên thực tế việc truyền nhận dữ liệu không phải lúc nào cũng thành công. Hơn nữa, do đặc điểm phần cứng của WSN cũng gây ra lỗi dữ liệu truyền. Do đó một phƣơng án kiểm soát lỗi trong mạng WSN là vô cùng quan trọng nó sẽ đƣợc trình bầy trong chƣơng 2 của đồ án. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  26. - 26 - CHƢƠNG 2: KIỂM SOÁT LỖI TRONG WSN 2.1 Tổng quan về vấn đề kiểm soát lỗi trong WSN. WSN dựa vào sự kết hợp và phản hồi của nhiều cảm biến tƣơng tác với môi trƣờng. Do đó, lớp liên kết dữ liệu trong mạng thực sự rất quan trọng, với nhiệm vụ ghép kênh / giải mã kênh dữ liệu, phát khung dữ liệu, truy cập môi trƣờng và kiểm soát lỗi. Theo đó, để có độ tin cậy và hiệu quả dữ liệu trong mạng công việc kiểm soát lỗi là không thể thiếu. Trái ngƣợc với những mạng truyền thống, WSN đƣợc đặc trƣng bởi năng lƣợng thấp và sự hợp tác chặt trẽ của các nút cảm biến. Do vậy, các giải pháp truyền thông thƣờng đƣợc đƣa ra đều nhằm mục đích để làm giảm sự dƣ thừa trong lƣu thông bằng cách lọc dữ liệu liên quan hoặc tắt các nút dƣ thừa. Mục đích chính của kiểm soát lỗi là cung cấp thông tin đáng tin cậy trong các kênh không dây bởi lẽ những kênh này rất hay gặp sự cố nhƣ: nhiễu, yếu hay mất bit đồng bộ. Điều này dẫn đến lỗi kênh và tác động đến sự toàn vẹn của các gói tin đƣợc gửi đi bởi các nút cảm biến. Các lỗi này còn gia tăng hơn với WSN vì truyền thông điện năng thấp. Kết quả là, ngoài các kỹ thuật ở lớp vật lý cung cấp sự tin cậy ở cấp độ bit, các phƣơng án kiểm soát lỗi đƣợc sử dụng tại các lớp liên kết cung cấp độ tin cậy ở mức gói dữ liệu. Nhìn chung, các cơ chế kiểm soát lỗi trong WSN có thể đƣợc phân thành bốn phƣơng pháp chính: kiểm soát năng lƣợng, tự động phát lại (ARQ), sửa lỗi trƣớc truyền (FEC), và ARQ lai ghép (HARQ). Bốn phƣơng án này sẽ đƣợc là rõ tại chƣơng này, đồng thời trong chƣơng phân tích các phƣơng án kiểm soát lỗi bằng cách sử dụng kỹ thuật phân tích qua lớp chéo để để xem xét những tác động trên kênh không dây, truy cập môi trƣờng, và định tuyến multi-hop. Dƣới đây, tổng quan về các thành phần của lớp liên kết dữ liệu thông qua hình 2.1. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  27. - 27 - Hình 2.1. Tổng quan lớp liên kết dữ liệu. 2.2 Các phƣơng án kiểm soát Lỗi trong WSN. WSN đặc trƣng bởi nguồn năng lƣợng thấp và khả năng liên kết chặt trẽ giữa các nút cảm biến trong mạng. Do đó, vẫn đề đặt ra là làm sao để giữ cho mạng hoạt động ổn định và hiệu quả với nguồn năng lƣợng thấp đó. Các phƣơng án đã đƣợc đƣa ra: kiểm soát năng lƣợng và kiểm soát lỗi trong truyền thông dữ liệu. 2.2.1 Kiểm soát năng lƣợng. Trong nghiên cứu và triển khai nhƣng nhà nghiên cứu rút ra, khi kiểm soát nguồn năng lƣợng tốt thì lỗi mạng sẽ đƣợc giảm thiểu. Có 2 phƣơng án kiểm soát nguồn năng lƣợng để giảm tỉ lệ lỗi. Thứ nhất, Kiểm soát năng lƣợng tiêu thụ từ ăng-ten có thể giúp kiểm soát phạm vi truyền thông hiệu quả của một nút. Thứ hai, Kiểm soát năng lƣợng truyền tải. Truyền tải năng lƣợng cao làm giảm tỷ lệ lỗi gói tin bởi vì nó cải thiện đƣợc tỷ lệ nhiễu tín hiệu. Tuy nhiên, năng lƣợng tiêu thụ vì thế mà tăng đồng thời có thể gia tăng nhiễu với các nút lân cận. Kiểm soát năng lƣợng yêu cầu các giao thức phức tạp, do vậy đòi hỏi bộ nhớ cao để thực hiện làm cho phƣơng án này dƣờng nhƣ không phù hợp với tất cả các dự án của WSN. Mặc dù vậy, nó rất phù hợp khi sử dụng trong các dự án hoạt động trong khoảng thời gian gian dài. Năng lƣợng truyền tải của mỗi gói tin chiếm chi phí đáng kể trong nguồn năng lƣợng của WSN. Do vậy cần một phƣơng án hiệu quả hơn và đó là kiểm soát lỗi trong truyền thông. Sau đây là một số phƣơng án kiểm soát lỗi trong truyền thông đƣợc đƣa ra để xem xét đối với WSN. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  28. - 28 - 2.1.2 Tự động phát lại (ARQ). Một phƣơng án kiểm soát lỗi khá phổ biến trong các mạng truyền thông. Sau đây là nội dung và cơ chế hoạt động của nó trong quá trình kiểm soát lỗi. Nội dung: ARQ dựa chủ yếu dựa vào việc phát lại các gói dữ liệu bị mất hoặc bị hỏng để duy trì sự tin cậy. Cơ chế hoạt động: Bên gửi, sử dụng một phƣơng án phát hiện lỗi tạo các bít dƣ thừa rồi gắn vào gói dữ liệu truyền đi rồi đợi phản hồi từ bên nhận. Bên gửi đƣợc trang bị một bộ định thời gian, nếu sau khoảng thời gian quy định (time out) mà không nhận đƣợc phản hồi của bên nhận thì coi nhƣ đã có lỗi xẩy ra và sẽ truyền lại dữ liệu. Bên nhận, sau khi nhận đƣợc gói dữ liệu, sẽ sử dụng phƣơng án phát hiện lỗi tƣơng ứng kiểm tra gói dữ liệu. Nếu không có lỗi sẽ phản hồi lại bên gửi một ACK cho mỗi gói toàn vẹn. Các loại ARQ: - Go-back-N ARQ là cho phép bên gửi gửi N gói tin. Nếu có một gói tin không đƣợc ACK, thì tất cả các gói tin bị truyền lại. - Selective-repeat ARQ là gửi lại các gói tin chƣa đƣợc ACK. - Stop-and-wait ARQ là cho phép một gói tin đơn chƣa hoàn thành qua và truyền các gói tin sau sau khi các gói tin này đã hoàn thành nghĩa là ACK. Trong các chiến lƣợc trên stop-and-wait ARQ đƣợc sử dụng phổ biến với WSN. ARQ dựa trên cơ chế kiểm soát lỗi phải chịu chi phí đáng kể để bổ sung và phát lại. Tuy nhiên, ARQ thích hợp với ứng dụng bị hạn chế về khả năng xử lý của các nút cảm biến. 2.1.3 Sửa lỗi trƣớc khi truyền (FEC). Trong WSN năng lƣợng tiêu thụ là yếu tố vô cùng quan trọng, do vậy mà phƣơng án kiểm soát lỗi ARQ thực sự không phù hợp với đa số ứng dụng của mạng này. Một phƣơng án kiểm soát lỗi khác đƣợc đƣa ra, để tránh việc truyền lại khi gói dữ liệu bị lỗi thì việc sửa lỗi ngay tại nút nhận là giải pháp hợp lý nhất. Hơn nữa, các nút cảm biến với khả năng tự xử lý làm phƣơng án này trở lên khả thi hơn. Sau đây là những luận điểm và chứng minh phƣơng án mới này thực sự khả thi với WSN. Phƣơng án này mang tên “Sửa lỗi trƣớc khi truyền”. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  29. - 29 - 2.1.3.1 Cở sở lý thuyết của FEC. Sơ bộ hoạt động: (theo hình 2.2) Theo đó, tại lớp Application dữ liệu tồn tại ở dạng gói và khi tới lớp radio chip nó tồn tại dạng từng bít và đƣợc truyền đi. Lớp radio chip có thể là chipcon radio ( loại mới nhất hiện nay) hoặc RFM radio. Bên gửi, các gói dữ liệu đƣợc phân mảnh thành từng byte đƣợc mã hóa rồi gửi đi. Trƣớc đó một chuỗi byte đặc biệt gọi là “preamble” hay phần mở đầu đƣợc gửi đi nhằm đồng phát hiện và đồng bộ hóa gói dữ liệu. Bên nhận, sau khi nhận đƣợc gói mở đầu, nó bắt đầu giải mã các gói sau đó, và MAC thực hiện lắp ráp các gói đó lại và thông báo sự tồn tại gói tin. Hình 2.2. Mô hình xử lý trong WSN. Trong quá trình phân mảnh (hình 2.3), các bít dữ liệu đƣợc mã hóa với mã sửa lỗi (ECC) và đƣợc ánh xạ vào trong các byte dữ liệu gốc. Nếu có lỗi xẩy ra, các bít này sẽ đƣợc bên nhận sử dụng để sủa lỗi phục hồi dữ liệu gốc. Hình 2.3. Sơ đồ mã hóa byte dữ liệu. Đặc điểm lỗi trong WSN: Một thực nghiệm đƣợc thực hiện, nút cảm biến với chipcon radio gửi liên tục 10000 gói tin không mã hóa đến một máy PC. Kết quả nhận đƣợc cho bởi hình 2.4. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  30. - 30 - Hình 2.4. Biểu đồ tần suất lỗi bít của một nút cảm biến khi phát 10000 gói và tỷ lệ lỗi gói tin mở đầu theo khoảng cách. Từ biểu đồ hình 2.4 ta thấy đa số lỗi bít trong thực nghiệm là lỗi đơn bít và lỗi 2 bít, lỗi đa bít và lỗi gói khởi đầu có nhưng rất ít. Vì vậy, đối với đặc điểm này mà phƣơng án FEC tập trung vào sửa lỗi đơn bít và hai bít chứ không tập trung sửa lỗi đa bít. Sau đây, trình bầy khả năng sửa lỗi trong mã khối tuyến tính vì nó đơn giản và hiệu quả trong WSN. 2.1.3.2 Mã sửa lỗi sử dụng trong FEC. Mã khối tuyến tính: Phát biểu: || Một mã khối có chiều dài n gồm 2k từ mã được gọi là mã tuyến tính C(n,k) nếu và chỉ nếu 2k từ mã hình thành một không gian vectơ con k chiều của không gian vectơ n chiều gồm tất cả các vectơ n thành phần trên trường GF(2). Trường GF(2) (Galois Field 2) là trường nhị phân đồng thời phép cộng là phép cộng modul 2 (cộng tuyệt đối), và phép và (AND). || Cụ thể: Mã tuyến tính C(n, k) có mục đích mã hoá những khối tin k bit thành những từ mã n bit. Hay nói cách khác trong n bit của từ mã có chứa k bit thông tin. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  31. - 31 - Cách mã hóa: u = [a0, a1 , a2, . , ak-1] là thông tin cần đƣợc mã hoá thì từ mã v tƣơng ứng với u sẽ có đƣợc bằng cách lấy u nhân với ma trận sinh G. ta có : v = u.G hay v = a0g0 + a1g1 + +ak-1gk-1 Cách giải mã: có u=[a0, a1 , a2, . , ak-1], từ mã nhận đƣợc tại bộ thu v=[b0,b1, b2, ,bk-1,bk, ,bn-1], giả sử quá trình truyền không lỗi (tức là v thu đƣợc là đúng), từ v ta tìm lại u nhƣ sau: Từ phƣơng trình : v = u.G hay v = a0g0 + a1g1 + +ak-1gk-1 ta giải hệ phƣơng trình trên để tìm các ai => ta tìm đƣợc u. ví dụ: u = [a0, a1 , a2, . , ak-1], v=[b0,b1, b2, ,bk-1,bk, ,bn-1], C(7,4) g0 1 1 0 1 0 0 0 g1 1 0 1 1 1 0 0 G47 g2 0 1 0 0 0 1 1 g3 1 0 1 0 0 0 1 Tử: v=uG => hệ phƣơng trình dƣới b0 = a0 + a1 + a3 b1 = a0 + a2 b2 = a1 + a3 b3 = a0 + a1 b4 = a1 b5 = a2 b6 = a2 + a3 với v=[1100101] thay vào hệ trên => u=[1101] Mã hoá khối tuyến tính hệ thống: Một mã tuyến tính C(n,k) đƣợc gọi là mã tuyến tính hệ thống nếu mỗi từ mã có một trong hai dạng sau: k bit thông tin n – k bit kiểm tra Hoặc n-k bit kiểm tra k bit thông tin Khi đó ta sẽ xác định đƣợc ma trận sinh G hệ thống tƣơng ứng. Với dạng 1 thì : G = [Ik, P] Với dạng 2 thì : G = [P, Ik] Trong đó, P là ma trận nhị phân, Ik là ma trận đơn vị kích thƣớc k x k. khi đó, thông tin gốc có thể lấy đƣợc từ k-bit đầu hoặc k-bit cuối của từ mã. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  32. - 32 - Cách xác định ma trận sinh hệ thống (G): Xét cấu trúc mã khối hệ thống : r1,r2,r3, rn-k,b1,b2,b3, bk. Trong đó, ri là các bit kiểm tra đƣợc thêm vào; bi là bit thông tin. Ma trận sinh của hệ thống có dạng: G = [Ik×k:Pk×(n-k)] với I là ma trận đơn vị k×k ; P là ma trận nhị phân. Xác định ma trận nhị phân P: Ta có tổ hợp tuyến tính của k bit thông tin theo công thức: r1 p 11 b 1 p 12 b 1 p 1kk b (*) rn k p( n k )1 b 1 p ( n k )2 b 1 p ( n k ) k b k hay ta có hệ phƣơng trình tƣơng đƣơng: ri = p1ib1 + p2ib2 + p3ib3 + pkbk Thế k từ mã độc lập tuyến tính vào hệ phƣơng trình (*) để tìm các pij cho ma trận G, khi đó ta cũng có thể tìm P với: ( ) Quá trình chung: quá trình hoạt động chung của mã hóa, truyền và giải mã một thông điệp thể hiện trong hình 2.5. Hình 2.5. Sơ đồ quy trình giải mã - truyền - mã hóa. Phát hiện và sửa lỗi (nguyên lý khoảng cách Hamming tối thiểu): - Nguyên lý phát hiện sai : Kiểm tra xem tổ hợp nhận có phải là từ mã hay không, nếu không thì tổ hợp nhận là sai. - Nguyên lý sửa sai : Kiểm tra xem tổ hợp nhận có khoảng cách Hamming gần với từ mã nào nhất, thì đó chính là từ mã đúng đã đƣợc phát đi. (quyết định theo nguyên tắc gần vẫn đúng). SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  33. - 33 - Cách phát hiện lỗi: một ma trận kiểm tra (H) của bộ mã có ma trận sinh Gk×n có kích thƣớc (n-k)×n sao cho : G×HT = 0; Nhƣ vậy: Nếu ma trận sinh hệ thống cuả một mã tuyến tính hệ thống có dạng : (HT và PT là 2 ma trận chuyển vị) T T G = [Ik : P] => H = [P : Ir] hoặc G = [P : Ik] => H = [Ir : P ] T T T Ta có: G×H = [Ik : P][P : Ir] = P + P =0 (xét trong trƣờng GF(2)). Nếu gọi vector lỗi là e thì chúng ta có s - syndrome: s = r.HT = ( v + e )HT = uGHT + eHT = eHT s ≠ 0 nghĩa là có lỗi; sau đó tuỳ thuộc vào khả năng của mã sửa lỗi, s đƣợc so sánh với từng hàng hay tổng của các hàng trong HT đễ xác định lỗi dựa vào tập hợp các mẫu lỗi (T): - Tồn tại duy nhất một ti T sao cho ti = s thì xác định đƣợc vị trí lỗi. - Tồn tại hơn một ti =s ( giả sử s = ti = tj T ) thì chỉ xác định đƣợc lỗi mà không sửa đƣợc. - Không xác định đƣợc ti =s hay s T thì lỗi không xác định đƣợc hoặc gói tin bị mất một đoạn nào đó. Từ đó, ta tìm đƣợc vị trí lỗi - Lỗi đơn bit: có s trùng với 1 cột trong ma trận H, vị trí cột là vị trí của lỗi - Lỗi 2 bít: có s trùng với phép hoặc tuyệt đối của 2 cột trong ma trận H, vị trí của các cột trùng với vị trí của lỗi. Cách sửa lỗi: Phía thu sau đó có thể giải mã các từ mã đã đƣợc sửa lỗi bằng việc giải phƣơng trình v=u.G (nhƣ đã trình bày ở trên). Một cách đặc biệt, nếu G là một ma trận sinh hệ thống thì thông tin gốc có thể lấy đƣợc từ k-bit đầu hoặc k-bit cuối của từ mã nhận đƣợc. Phương pháp mã cột trọng số lẻ (Odd-weight-column): khả năng sửa đƣợc lỗi đơn bít và phát hiện lỗi 2bít. Với đầu vào là k bít dữ liệu thì H với số cột ≥ r+k (r số lƣợng bít chẵn lẻ). Ví dụ, r = 5 bit chẵn lẻ là cần thiết để phục hồi k = 8 bit dữ liệu, và r = 6 bit chẵn lẻ là cần thiết để phục hồi k = 24 bit dữ liệu. Xác định các cột của H nhƣ sau: - r cột cuối của H là một ma trận đơn vị Ir. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  34. - 34 - - k cột đầu của H đƣợc lấy từ r hàng vector cột trọng số lẻ ngoại trừ những cái sử dụng trong Ir. Ví dụ: cho u = [0100 0010], k=8, r=5 Từ u và G ta có: v = uG = [0100 0010 10111] Giả sử rằng các bit thứ hai của thông điệp mã hóa bị đảo ngƣợc do nhiễu. Bên nhận, nhận đƣợc thông điệp v’ = [0000 0010 10111]. Sau đó ta tính đƣợc: từ đây ta thấy rằng s giống với hàng thứ 2 của ma trận HT. Do đó, bằng cách đảo giá trị tại bít thứ 2 của v’ thì ta sẽ đƣợc v. Sau khi nhận đƣợc v’ không lỗi hoặc đã sửa lỗi, với ma trận sinh G theo một mã có hệ thống thì, u sẽ là k bít đầu tiên của v’. tức là : u = [0100 0010]. Phương án “Double error correction codes”: khả năng sửa lỗi hai bít và phát hiện lỗi 3 bít. Phƣơng án này chỉ sửa đƣợc lỗi đơn bít và 2 bít, lỗi 3 bít chỉ đƣợc phát hiện và thông báo cho các lớp trên. Một mã Double-Error-Correcting và Triple-Error-Detecting (DEC-TED) (16,8) đƣợc đề xuất bởi Gulliver và Bhargave với ma trận nhị phân C. Ma trận sinh G đƣợc tạo ra với dạng G=[I8 , C] và ma trận chẵn lẻ H có dạng T H = [C , 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. Ví dụ: cho u=[0100 0010], Lƣu ý: rằng khoảng cách Hamming tối thiểu giữa hai hàng bất kì là 5. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  35. - 35 - Từ đó, v = uG = [0100 0010 1001 1100] Giả sử, bít thứ 2 và 3 bị đảo ngƣợc do nhiễu. Bên nhận, nhận đƣợc thông điệp v’= [0010 0010 1001 1100]. Từ đó, tính đƣợc: , khi đó ta đem từng cặp hàng trong HT XOR với nhau, thi thấy hàng thứ 2 và 3 XOR với nhau bằng s. Vậy lỗi nằm ở bít thứ 2 và 3 của v’. Từ đó, đảo giá trị bít ta sẽ đƣợc v. Sau khi nhận đƣợc v’ không lỗi hoặc đã sửa lỗi, với ma trận sinh G theo một mã có hệ thống thì, u sẽ là 8 bít đầu tiên của v’, tức là, u = [0100 0010]. Trên đây, là những lý thuyết cơ bản của phƣơng án FEC và cách sửa lỗi đơn bít và 2 bít của nó. Đối với mạng WSN, FEC thực sự thích hợp được chọn làm phương án kiểm soát lỗi hiệu quả nhất. 2.1.4 ARQ lai ghép (HARQ). Phƣơng án ARQ và FEC duy trì độ tin cậy trong các kênh thông qua các kỹ thuật khác nhau. ARQ thƣờng có hiệu quả với kênh truyền tốt vì không có bit dƣ thừa đƣợc gửi đi. Tuy nhiên, ARQ trở nên không hiệu quả khi gặp lỗi do phải gửi lại toàn bộ gói tin, mặc dù chỉ có một số bit là bị hỏng. FEC thì ngƣợc lại, với hiệu quả kênh truyền không tốt vì phải truyền thêm nhƣng bít dƣ thừa nhƣng lại tốt trong điều kiện gặp lỗi vì nó có khả năng phục hồi lỗi. một phƣơng án mới đƣợc tính đến đó là Hybrid ARQ hay ARQ lai ghép. Nội dung: ARQ lai ghép (HARQ) kết hợp phƣơng án FEC và ARQ bằng cách nâng cao khả năng phục hồi lỗi trong một gói tin thông qua truyền lại. Cơ chế hoạt động: một gói uncoded hoặc mã hóa thấp đƣợc gửi lần đầu tiên. Trong trƣờng hợp lỗi kênh, HARQ thực hiện phát lại bằng cách sử dụng khả năng của FEC. Với 2 cách xử lý khác nhau trong 2 loại HARQ. Các loại HARQ: - Kĩ thuật HARQ-I: Nếu gói tin nhận bị lỗi, bên nhận sẽ gửi một NACK cho bên gửi. Sau đó, bên gửi, sẽ gửi một gói với dữ liệu và mã FEC. - Kĩ thuật HARQ-II: nếu gặp lỗi, chỉ có các bit mã FEC đƣợc gửi đi. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  36. - 36 - Trong khi loại II giảm sử dụng băng thông, thì loại I không yêu cầu các gói dữ liệu đã gửi trƣớc đó đƣợc lƣu trữ ở phía bên nhận. 2.2 Lợi ích của tăng khả năng phục hồi lỗi. Đối với hai phƣơng án FEC và HARQ với khả năng phục hồi lỗi đã làm năng lƣợng tiêu thụ trong truyền thông đã đƣợc kiểm soát rất tốt, tăng phạm vi truyền hiệu quả ở tỉ lệ lỗi gói tin (PER) giảm. Nhìn chung lợi ích này đƣợc tạo ra bởi hai khả năng chinh mà FEC và HARQ cung cấp đó là, mở rộng độ dài bƣớc nhẩy và kiểm soát năng lƣợng truyền tải. Khả năng 1: Mở rộng độ dài bước nhẩy. Trong các mạng multi-hop, khả năng phục hồi lỗi của FEC và HARQ đã nâng cao phạm vi truyền thông hiệu quả của một nút (hình 2.6). Trong hình những đƣờng nét thể hiện PER xung quanh một nút phát. Các đƣờng nét hiển thị các vị trí có PER tƣơng ứng với giá trị cụ thể. So sánh Hình 2.6 (a) và Hình 2.6 (b) đối với tỷ lệ mục tiêu nhận gói tin là 90%, phạm vi truyền tải trung bình của một nút là 29m với ARQ và 42m với FEC ở điện năng truyền tải là -5 dBm. Nó tăng 45% phạm vi hiệu quả, rõ ràng mã FEC có thể tăng phạm vi truyền dẫn hiệu quả của một nút so với ARQ. Từ đó, có thể thấy, việc tăng độ dài bƣớc nhẩy trong WSN làm tăng phạm vị truyền dẫn hiệu quả. Hình 2.6. Trung bình tỉ lệ mục tiêu nhận gói tin, đồ thị (a) ARQ (N = 7) và (b) FEC (BCH (128, 78, 7)) cho nút MicaZ. Phương án 2: Kiểm soát năng lượng truyền tải. Thông qua khả năng phục hồi lỗi của mã FEC cũng có thể giảm năng lƣợng truyền tải mà vẫn đảm bảo chất lƣợng mạng. Kỹ thuật này đƣợc gọi là kiểm soát SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  37. - 37 - năng lƣợng truyền tải và cải thiện hiệu quả mạng bằng cách giảm nhiễu, giảm một phần năng lƣợng tiêu thụ. Dẫn chứng cho việc nâng cao hiệu quả mạng với FEC: xem xét FEC để so sánh với ARQ thông qua PER trong mạng (Hình 2.7). Hình 2.7. So sánh hiệu quả của FEC với ARQ. Trong Hình2.7(a), truyền thông giữa nút A và B với ARQ. Nút A sử dụng truyền tải điện năng là PtARQ để gửi một gói tin đến nút B, cách xa một khoảng dARQ. Thu đƣợc SNRARQ tại nút B. Theo đó, xác định một . Bây giờ thay ARQ bằng FEC: có 2 trƣờng hợp xẩy ra. Trường hợp mở rộng độ dài bước nhẩy: Hình 2.7 (b), nút A lựa chọn nút C là bƣớc nhẩy tiếp theo xa hơn B. Do đó, dARQ > dFEC và vẫn là PtARQ, SNRFEC nhỏ hơn SNRARQ. Do đó, vẫn đạt đƣợc giá trị PER tƣơng tự ARQ. Trường hợp kiểm soát năng lượng truyền: Hình 2.7 (c), nút A vẫn sử dụng nút B là bƣớc nhẩy tiếp theo tức là dFEC=dARQ. Tuy nhiên, sử dụng năng lƣợng truyền tải nhỏ hơn, tức là, PtFEC < PtARQ, SNR vẫn nhỏ hơn. Do đó, cũng có đƣợc PER tƣơng tự với ARQ. Ngoài những lợi thế, phƣơng án FEC và HARQ phải bỏ chi phí năng lƣợng và độ trễ cho mã hóa/giải mã, mà làm truyền thông lâu hơn. Do đó, các phƣơng án kiểm soát lỗi đòi hỏi phân tích kĩ lƣỡng. Phần tiếp theo, trình bầy một hƣớng phân tích “mô hình lớp chéo” để thấy ƣu điểm và nhƣợc điểm của các phƣơng án này. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  38. - 38 - 2.3 Phân tích mô hình lớp chéo. Cung cấp một cái nhìn cụ thể về các phƣơng án ARQ, FEC, và HARQ. Mục tiêu của mô hình này là để phân tích và xác định các yếu tố sau đây: Khoảng cách bƣớc nhẩy dự kiến, năng lƣợng tiêu thụ, độ trễ và PER tổng thể. Sau đó giải thích mô hình và mô tả cách tính toán các số liệu này. 2.3.1 Mô hình tham chiếu của WSN. Mô tả mô hình: (hình 2.8) - Các nút cảm biến phân phối hai chiều với mật độ (ρ). - Một nút hoạt động trong khoảng thời gian (δ) và những nút khác thì ngủ. - Là ứng dụng theo dõi với tỷ lệ báo cáo của cảm biến là thấp, nhƣng các thông điệp đƣợc truyền đáng tin cậy với PER tổng thể. - Bƣớc nhẩy tiếp theo đƣợc xác định theo SNR nhận của gói tin đƣợc gửi từ một nút i cách sink một khoảng D. - Trong số những nút lân cận của i, có nút j gần sink hơn và có SNR cao hơn SNR ngƣỡng (ψTh), tức là (ψj> ψTh), đƣợc chọn là bƣớc nhẩy tiếp theo. - Truy cập môi trƣờng đƣợc thực hiện thông qua trao đổi bắt tay: - FEC là RTS-CTS-DATA. - ARQ là RTS-CTS-DATA-ACK. - HARQ là RTS-CTS-DATA-NACK. - Khi một nút gửi (ni) truyền một gói tin đến sink thông qua một đƣờng mà nút (nj) là bƣớc nhẩy kế tiếp. Với phạm vi truyền của một nút (Rinf), là khoảng cách mà tại đó gói tin có thể nhận thành công. Hình 2.8. Mô hình tham chiếu của WSN. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  39. - 39 - Lưu ý: Việc đặt khoảng cách bƣớc nhẩy và các thông số liên quan tại mỗi bƣớc nhẩy là chu kì nhiệm vụ hoạt động độc lập. Kết quả là, trạng thái của mạng sẽ thay đổi tại mỗi bƣớc nhẩy do các nút sẽ thức dậy vào thời điểm khác nhau. Mô hình phân tích chi phí cho quá trình truyền một gói dữ liệu từ nút nguồn dữ liệu cách sink một khoảng D. Đƣợc tính toán bằng những công thức cụ thể dƣới đây. Tổng năng lƣợng tiêu thụ của một luồng từ nút nguồn cách sink 1 khoảng D. (2.1) Trong đó, E[Eh] là năng lƣợng tiêu thụ dự kiến tại mỗi bƣớc nhẩy và E[nh(D)] là số lƣợng bƣớc nhẩy dự kiến từ nút nguồn cách sink một khoảng D. Tƣơng tự, độ trễ tổng thể của nó đƣợc cho bởi công thức 2.2. (2.2) Trong đó, E[Th] là dộ trễ dự kiến tại mỗi bƣớc nhẩy. Số lƣợng bƣớc nhẩy dự kiến tính bằng công thức 2.3. (2.3) Trong đó, D là khoảng cách tổng thể, Rinf là phạm vi truyền của nút, E[dh] là khoảng cách bƣớc nhẩy dự kiến. Trong các mục 2.3.2, 2.3.3, và 2.3.4 tiếp theo, sẽ làm rõ với khoảng cách bƣớc nhẩy dự kiến E[dh], mức tiêu thụ năng lƣợng dự kiến tại mỗi bƣớc nhẩy E[Eh], và độ trễ dự kiến tại mỗi bƣớc nhẩy E[Th]. 2.3.2 Khoảng cách bƣớc nhẩy dự kiến. Trong hình 2.8, nơi mà một nút j nằm trong khu vực rất nhỏ dA = dγ dα tại tọa độ (γ, α) đối với sink. Khoảng cách từ nút i đến nút j là: (2.4) Trong đó, D là khoảng cách từ nút nguồn i đến sink, (γ) là khoảng cách giữa sink và nút kế tiếp tiếp j, và góc α nhƣ trong hình 2.8. Theo đó, khoảng cách bƣớc nhẩy dự kiến E[dh], đƣợc tính bằng công thức 2.5. (2.5) Trong đó, γmin=D-Rinf là khoảng cách tối thiểu giữa một nút bƣớc nhẩy tiềm năng tiếp theo j đến sink. Hơn nữa, d(i, j) là khoảng cách giữa nút i và j đƣợc cho bởi SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  40. - 40 - công thức (2.4) và dP{Ni = j} là xác suất cho rằng bƣớc kế tiếp Ni đƣợc chọn là nút 2 2 2 j. Cuối cùng, αγ=a.cos[(γ + D - R inf) / (2γD)] là giới hạn của khoảng cách. Điều kiện j đƣợc chọn là bƣớc nhẩy tiếp theo: - Nút j tồn tại trong khu vực dA. - Các SNR nhận của nút j phải đáp ứng (ψj> ψTh). - Các SNR nhận của mỗi nút k, gần với sink hơn so với nút j, phải thấp hơn ngƣỡng SNR, tức là (ψk ≤ ψTh). Do đó, xác suất mà nút j đƣợc chọn nhƣ là bƣớc nhẩy kế tiếp đƣợc tính: (2.6) Trong đó, NA(dγ) là số lƣợng nút trong vùng dA tại khoảng cách γ từ sink; là xác suất có một nút trong khu vực A(dγ); là xác suất mà SNR nhận của nút j trên SNR ngƣỡng (ψTh); là xác suất có những nút gần sink hơn j có SNR dƣới ngƣỡng có thể tìm thấy tại khoảng cách γ từ sink. Thành phần thứ nhất, P{NA (dγ) = 1}, trong (2.6) có thể đƣợc xấp xỉ bằng: (2.7) Trong đó, ρ là mật độ nút trong mạng và δ là tham số chu kỳ nhiệm vụ. Thành phần đƣợc dùng khi (ρδγ dγ dα)→0 cũng nhƣ dγ →0,dα→0. Để tính toán P{ψj> ψTh} và P{d(j, s) ≥ γ} trong (2.6). Cần xác định năng lƣợng thu nhận ở một khoảng cách d từ nút phát Pr(d) đƣợc cho bởi công thức 2.8. (2.8) Trong đó, Pt là công suất truyền tải tính bằng (dBm), PL(d0) là tổn hao năng lƣợng ở khoảng cách lý thuyết d0 tính bằng (dBm), η là số mũ tổn hao và Xσ là thành phần bóng mờ, với Xσ~N(0, σ). Các SNR nhận cho bởi: ψ(d) = Pr(d)-Pn tính bằng (dBm), trong đó Pn là năng lƣợng nhiễu (dBm). Thành phần thứ hai, P{ψj> ψTh}, trong (2.6) tính bằng công thức 2.9. (2.9) SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  41. - 41 - (2.10) Trong đó, . Thành phần thứ ba, P{d (j, s) ≥ γ}, trong (2.6). Khu vực bao gồm các nút gần với sink hơn so với nút j là A(γ). Thì: (2.11) Trong đó A(γ) là vùng giao nhau của hai vòng tròn với tâm phân cách bởi D và với bán kính Rinf và γ tƣơng ứng. Do đó, NA(γ) là số nút trong A(γ) và M(γ) = ρδA (γ) là số lƣợng trung bình của các nút trong khu vực này. Pk(γ) = P{ψk ≤ ψTh, k ∈ A(γ)} là khả năng mà một nút k trong A(γ), với SNR nhận thấp hơn SNR ngƣỡng tức là ψk ≤ ψTh. Điều này có thể tìm thấy trong công thức 2.12. (2.12) (Trong đó γmin = D-Rinf) Sử dụng (2.6), (2.7), (2.9), (2.11), và (2.12) trong (2.5), khoảng cách bƣớc nhẩy dự kiến có thể đƣợc tìm ra bởi công thức 2.13. (2.13) 2.3.3 Phân tích năng lƣợng tiêu thụ dự kiến. Năng lƣợng tiêu thụ dự kiến đƣợc tính toán bằng cách xem xét một nút j nhƣ trong hình 2.8. Việc tiêu thụ năng lƣợng dự kiến giữa i nút và nút j đƣợc ký hiệu là E[Ej], là một hàm của γ và α. Dựa vào mục 2.3.2 và thay thế d(i, j) bởi E[Ej] trong (2.13), mức tiêu thụ năng lƣợng dự kiến mỗi bƣớc nhẩy đƣợc tính bằng công thức: (2.14) SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  42. - 42 - Một nút có thể trở thành một bƣớc nhẩy tiếp theo nếu có giá trị SNR nhận lớn hơn ngƣỡng, mức năng lƣợng tiêu thụ dự kiến E[Ej], tính bằng công thức 2.15. (2.15) Trong đó, Ecomm (d (i, j), ψ) là năng lƣợng tiêu thụ cho truyền một gói tin giữa các nút i và j ở khoảng cách d(i, j) và ψ là giá trị SNR tại nút j. Thành phần thứ hai, fψ (d(i,j),ψ) là hàm mật độ xác suất của SNR, là một hàm của các d(i, j) hiệu quả. Vì P(ψ ≤ ψ) = P(Xσ ≤ β(d(i,j),ψ)), fψ (d(i,j),ψ) đƣợc tính: (2.16) Trong đó β(d(i,j),ψ) đã có trong công thức 2.10. Năng lượng tiêu thụ cho một giao tiếp trong WSN: gồm ba thành phần  Năng lƣợng tiêu thụ của nút truyền  Năng lƣợng tiêu thụ của nút nhận  Năng lƣợng tiêu thụ cho nút lân cận. Theo đó, ta có công thức: (2.17) Trong đó ETX là năng lƣợng tiêu thụ bởi nút gửi (nút i), ERX là năng lƣợng tiêu thụ bởi nút nhận (nút j), và Eneigh là năng lƣợng tiêu thụ bởi các nút lân cận. Ba giá trị tiêu thụ năng lƣợng phụ thuộc vào MAC và sơ đồ điều khiển lỗi đƣợc triển khai trên mỗi nút. Theo đó, để truyền tải các gói dữ liệu thành công, nút một cần hoàn thành bốn bƣớc bắt tay: RTS-CTS-DATA-ACK của ARQ, ba bƣớc bắt tay: RTS-CTS-DATA của FEC, và RTS-CTS-DATA-NACK của HARQ. Trƣớc khi truyền một gói tin RTS, của truy cập môi trƣờng, một nút thực hiện cơ chế cảm nhận sóng mang để đánh giá sự sẵn sàng của một kênh truyền và truyền tải một gói tin sau đó. Một cấp phát thành công của kênh phụ thuộc vào cả cảm nhận sóng mang thành công và truyền tải không có va chạm. Xác suất cảm nhận sóng mang thành công (Pcs), có thể đƣợc tính nhƣ sau: (2.18) SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  43. - 43 - Trong đó K là số lần “cảm nhận lại” cho phép đối với một truyền tải và (Pcf) là xác suất cảm nhận đƣợc kênh tự do, đƣợc tính nhƣ sau (2.19) Trong đó τcs là thời gian truyền cảm nhận và Tcomm là thời gian truyền gói tin. Sau một cảm nhận truyền thành công, một va chạm chỉ có thể xảy ra nếu một nút truyền trong khoảng thời gian dễ bị đụng độ của τcs. kết quả là, xác suất không có va chạm PnoColl tính bởi công thức: (2.20) Kí hiệu λnet trong (2.19) và (2.20) là lƣu lƣợng tổng thể đƣợc tạo ra bởi tất cả các nút trong phạm vi truyền dẫn của một nút, đƣợc cho bởi công thức 2.21. (2.21) Trong đó λ là tổng lƣu lƣợng đƣợc tạo trong phạm vi truyền dẫn của một nút và Pcomm là xác suất truyền thành công. Theo đó, xác suất một nút có thể nhận thành công trên kênh đƣợc cho bởi Pcs và PnoColl, có thể đƣợc tìm thấy bằng cách giải hệ phƣơng trình (2.18) và (2.21). Giá trị (λ) phụ thuộc vào tỷ lệ lưu lượng được tạo và kích thước của gói. Giả định rằng các nút cảm biến có tỷ lệ lấy mẫu trung bình là (b) bít/s . Biểu diễn chiều dài tải trọng gói tin là (lD), tỷ lệ trung bình tạo gói của một nút i là (λii=b/lD) pkts/s. Trong WSN, từ một nút cũng có thê chuyển tiếp các gói tin thông qua các nút khác đến sink, tỉ lệ truyền gói tin của một nút cao hơn giá trị truyền kiểu này. Nếu một phƣơng án định tuyến bằng cách chia sẻ tải nguyên mạng giữa các nút thì tỉ lệ trung bình truyền tải gói tin của nút là ( λi = ci λii ) với ci>1. Do đó, λ tại (2.21) đƣợc cho bởi công thức: ; Khi đó số lƣợng các nút có trong phạm vi truyền dẫn của một nút là (Mn–1). Khi truy cập kênh truyền, mức tiêu thụ năng lƣợng phụ thuộc vào xác suất nhận thành công gói dữ liệu và gói kiểm soát ở khoảng cách d(i, j) với giá trị SNR ψ. Cách tính và sẽ đƣợc giải thích trong mục 2.3.5. Ngoài ra, một gói tin truyền (RTS) chỉ thành công nếu một nút có thể nhận thành công trên kênh (cho bởi Pcs và PnoColl). SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  44. - 44 - Năng lượng tiêu thụ của nút truyền: Theo đó, năng lƣợng tiêu thụ cho nút truyền ETX đƣợc cho bởi công thức tƣơng ứng với ARQ, FEC và HARQ. Với nret của ARQ, FEC, và HARQ, tƣơng ứng khi đó là: Các giá tri nret là số lƣợng dự kiến truyền lại với ARQ, FEC và HARQ, trong đó lại đƣợc giới hạn bởi số lƣợng tối đa cho phép của truyền lại; và là năng lƣợng truyền và nhận gói tin, trong đó: R, C, D và A tƣơng ứng với RTS, CTS, DATA, và ACK; Esense là mức tiêu thụ năng lƣợng cho cảm nhận khu vực. Hai thành phần cuối cùng trong dấu ngoặc đơn của 3 công thức thể hiện năng lƣợng tiêu thụ với độ trễ cho CTS và ACK trong trƣờng hợp lỗi gói tin. Ngoài ra, là năng lƣợng giải mã, D1 và D2 trong (2.24) tƣơng ứng với gói dữ liệu truyền cho lần đầu tiên và lần thứ hai trong HARQ. Hoạt động truyền một gói tin: Nếu các kênh cảm biến ở trạng thái tốt, nút truyền một gói tin RTS và nhận đƣợc một gói tin CTS nếu không có sự va chạm và các gói tin RTS đƣợc nhận thành công tại đích đến. Tƣơng tự, một gói dữ liệu đƣợc gửi nếu các gói tin CTS đƣợc nhận thành công, tiếp đó là tiếp nhận gói tin ACK. Năng lượng tiêu thụ của nút nhận: Sử dụng phƣơng pháp tƣơng tự, mức năng lƣợng tiêu thụ của nút nhận, ERX tại (2.17), đƣợc tính nhƣ sau: SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  45. - 45 - Năng lượng tiêu thụ cho nút lân cận: Trong các mạng không dây, những nút lân cận của nút truyền và nút nhận cũng bị ảnh hƣởng bởi các thông tin liên lạc do tính chất quảng bá của kênh không dây. Do đó, kí hiệu cuối cùng trong (2.17), Eneigh, là năng lƣợng tiêu thụ bởi những nút láng giềng của các nút truyền và nhận. Đƣợc tính băng những công thức sau: 2.3.4 Phần tích độ trễ dự kiến. Các biểu thức xác định độ trễ tổng thể của luồng phát sử dụng phƣơng pháp tƣơng tự nhƣ trên. Độ trễ mỗi bƣớc nhẩy đƣợc cho bởi công thức 2.32. (2.32) (2.33) Trong đó, Tcomm là độ trễ để truyền thông với ARQ, FEC và HARQ, đƣợc tính bởi công thức: Ctrl D Trong đó, Tsense là thời gian dành cho cảm biến, T và T là thời gian truyền gói kiểm soát và gói dữ liệu, Tt /o là thời gian chờ, và là độ trễ giải mã cho các gói kiểm soát và gói dữ liệu. Độ trễ giải mã và năng lượng: Một trong những chi phí quan trọng của mã FEC ngoài các truyền và nhận các bit dƣ thừa là tiêu thụ năng lƣợng để mã hóa và giải mã các gói dữ liệu cũng nhƣ độ trễ liên quan đến nó. Nhƣ đã biết rằng năng lượng mã hóa cho mã khối là không đáng kể. Do đó, năng lượng giải mã và độ trễ SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  46. - 46 - giải mã nên đƣợc xem xét trong phân tích này. Các độ trễ của giải mã cho một mã khối (n, k, t) đƣợc cho bởi công thức: (2.37) Trong đó, Tadd và Tmult là độ trễ do cộng và nhân tƣơng ứng, trong trƣờng m GF(2 ), với m=[log2n + 1]. Cả hai nút Mica2 và MicaZ đƣợc thực hiện với vi điều khiển 8-bit, nó có thể thực hiện cộng và nhân của 8 bit trong chu kỳ một và hai, tƣơng ứng. Kết quả là: (2.38) Trong đó, tcycle là một chu kỳ thời gian, thƣờng bằng 250 ns. Do đó, việc tiêu thụ năng lƣợng cho giải mã là trong đó Iproc là cƣờng độ dòng cho bộ xử lý, V là điện áp cung cấp và độ trễ cho giả mã. 2.3.5 Phân tích BER và PER. Việc tiêu thụ năng lƣợng và độ trễ này phụ thuộc vào PER trong truyền thông. Trong phần này, cung cấp các biểu thức cho BER và PER cho các nút Mica2 và MicaZ. Bởi những phƣơng án điều chế đƣợc sử dụng trong mỗi nút này rất khác nhau, do đó nó là cần thiết để nghiên cứu tác động của FEC và HARQ vào các nút này một cách riêng biệt. Tính BER: Với nút Mica2: đƣợc thực hiện với một phƣơng án điều chế không nhất quán FSK. Các BER của phƣơng án án này đƣợc cho bởi công thức: (2.39) Trong đó ψ là SNR nhận, BN là băng thông nhiễu và R là tốc độ dữ liệu. Với nút MicaZ: đƣợc điều chế bởi phƣơng án khóa dịch pha cần phƣơng lệch (O-QPSK) với trái phổ tuần tự trực tiếp (DSSS). Các BER của phƣơng án này đƣợc cho bởi công thức: (2.40) Trong đó, N là số lƣợng chip/bit, và K là số nút sử dụng đồng thời truyền tải. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  47. - 47 - Tính PER: Căn cứ vào BER (Pb) đã tính ở trên, các PER cho các phƣơng án kiểm soát lỗi có thể đƣợc tính nhƣ sau. Đối với ARQ, cơ chế phát hiện lỗi CRC-16 đƣợc triển khai ở cả hai loai nút Mica trên. Giả sử tất cả các lỗi trong một gói có thể đƣợc phát hiện, các PER của đơn truyền một gói tin với trọng tải l bít đƣợc cho bởi công thức: (2.41) Đối với các mã BCH, giả sử sự đan xen hoàn thiện ở bộ thu phát, tỷ lệ lỗi khối (BLER) đƣợc cho bởi công thức: (2.42) Qua thuật toán Berlekamp-Massey đƣợc thực hiện và mô phỏng để tìm các mối quan hệ giữa các BLER và BER. Khi gói tin lớn hơn độ dài khối n, đặc biệt là trong đó độ dài khối nhỏ đƣợc sử dụng, các PER cho FEC đƣợc cho bởi công thức: (2.43) Trong đó [l/k] là số khối cần thiết để gửi l bit và [.] là Hàm mức trần. Sử dụng (2.41), (2.42), và (2.43), các PER với các phƣơng án HARQ cũng đƣợc tìm thấy. Xác suất thành công của gói tin, và đƣợc sử dụng trong mục 2.3.3, mục 2.3.4 với các gói kiểm soát và gói dữ liệu sau đó có thể đƣợc tìm thấy bằng cách sử dụng l=lC và l = lD, tƣơng ứng. 2.4 So sánh các phƣơng án kiểm soát Lỗi trong WSN. Trong phần này, minh họa tác động của các phƣơng án FEC và HARQ với PER, năng lƣợng tiêu thụ và độ trễ tổng thể trong một mạng multi-hop thông qua các đánh giá bằng số liệu trong MATLAB và mô phỏng. Để thực hiện so sánh này, hai loại nút cảm biến đƣợc sử dụng là Mica2 và MicaZ ngoài ra có một số trƣờng khác, các thông số trong Bảng 2.1, đƣợc sử dụng cho các số liệu kết quả. Bảng 2.1. Các tham số. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  48. - 48 - Các kí hiệu sử dụng, khoảng cách bƣớc nhẩy dự kiến là dhop, đƣợc xác định tại (2.5), SNR nhận (ψTh), năng lƣợng truyền (Pt). Khả năng tăng khoảng cách bước nhẩy ở FEC và HARQ: Hình 2.9. Trung bình khoảng cách bƣớc nhẩy (MicaZ). Từ hình 2.9, nhận thấy ở ψTh nhỏ độ dài bƣớc nhẩy lớn là số lƣợng bƣớc nhẩy từ một nút tới sink giảm. Hơn nữa, khi truyền tải điện năng của nút giảm, khoảng cách bƣớc nhẩy dự kiến sẽ giảm. Hình 2.10. Năng lƣợng tiêu thụ của một lƣu lƣợng với ψTh (MicaZ). SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  49. - 49 - Trong hình 2.10, năng lƣợng tiêu thụ của luồng giảm khi giá trị ψTh giảm từ 15dB. Điều này do khoảng cách bƣớc nhẩy dự kiến tăng trong hình 2.9. Tuy nhiên, mức tiêu thụ năng lƣợng cho ARQ tăng đáng kể khi ψTh giảm nhỏ hơn một giá trị cụ thể, ví dụ, 5 dB. Vì chất lƣợng kênh thấp dẫn đến truyền lại xảy ra, làm tăng tiêu thụ năng lƣợng trên mỗi bƣớc nhẩy. Lưu ý: đối với ARQ, các đƣờng cong tiêu thụ năng lƣợng đạt đến một đỉnh cao và giảm khi ψTh giảm. Điểm này tƣơng ứng với trƣờng hợp truyền lại với số lƣợng tối đa, không còn đủ để truyền thông tin cậy. Trong hình 2.10, với các mã của FEC, khi chất lƣợng kênh truyền tốt thì năng lƣơng tiêu thụ nhiều hơn với ARQ bởi phải truyên thêm bít dƣ thừa và chi phí giải mã, nhƣng hiệu quả năng lƣợng hơn với ψTh~2dB vì khả năng phục hồi lỗi. Theo hình 2.11, nhận thấy PER của các mã FEC đã giảm khi giá trị SNR nhận vẫn còn thấp, từ đó có thể thấy khả năng phục hồi lỗi của FEC có thể giúp mạng hoạt động tốt trên một kênh truyền có chất lƣợng kênh không tốt, mà vẫn đảm bảo độ tin cậy cho gói tin. Trong hình 2.12, lại thấy với SNR thấp, các mã FEC hoạt động với độ trễ tốt hơm ARQ tuy nhiên ở những SNR cao hơn thì độ trễ của nó tăng rất nhanh cao hơn ca ARQ. Nguyên nhân, chính là do việc giải mã và các bít dƣ thừa tạo ra. Tuy nhiên, xét về tổng thể nó vẫn tốt hơn với ARQ vì ở SNR thấp, độ trễ của FEC ít hơn rất nhiều so với ARQ. Hình 2.11. PER Tổng thể với ψTh (MicaZ). SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  50. - 50 - Hình 2.12. Độ trễ trung bình tổng thể với ψTh (MicaZ). -2, Ví dụ, nếu PER mục tiêu của một ứng dụng là 10 giá trị tối thiểu cho ψTh tƣơng ứng với 6.1dB cho ARQ, 3dB cho BCH(128, 78, 7), 4.8dB cho RS(15, 9, 3), và 2.5dB cho HARQ-I. Kết quả là, trong hình 2.10 có BCH(128, 78, 7) là tiết kiệm năng lƣợng hơn chút ít so với ARQ. Mặt khác, mã RS(15,9,3) kết quả năng lƣợng tiêu thụ cao hơn so với ARQ. Rõ ràng rằng năng lƣợng đƣợc tiêu thụ trên bƣớc nhẩy với mã FEC gồm cả truyền bit dƣ thừa và giải mã. Tuy nhiên, vì khả năng phục hồi lỗi đƣợc cải thiện với mã FEC, các giá trị SNR thấp có thể đƣợc hỗ trợ. Kết quả là khoảng cách bước nhẩy dài hơn còn có thể đạt đến năng lượng tiêu thụ tổng thể thấp hơn. Khả năng kiểm soát năng lượng truyền tải ở FEC và HARQ: Để kiểm chứng ảnh hƣởng của năng lƣợng truyền (Pt) đến phƣơng án kiểm soát lỗi FEC hãy xem xét ba cấp điện áp: 0,-5 và -15 dBm. Khi giảm năng lƣợng tryền có thể nâng cao hiệu quả năng lƣợng cho phƣơng án FEC (hình 2.13 a) vì: - Tiêu thụ ít năng lƣợng hơn cho việc truyền gói dữ liệu mã hóa dài hơn. - Phạm vi giao thoa của một nút giảm, số lƣợng các nút láng giềng có thể tiêu thụ năng lƣợng nhàn rỗi cũng giảm. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  51. - 51 - - Làm tăng số lƣợng bƣớc nhẩy. Thể hiện trong hình 2.13(b), nơi mà độ trễ tổng thể đƣợc thể hiện. Trái ngƣợc với mở rộng khoảng cách bƣớc nhẩy, do kiểm soát năng lƣợng truyền không ảnh hƣởng đến thời gian cần thiết để truyền một gói tin, độ trễ tổng thể phụ thuộc vào số lƣợng bƣớc nhẩy. Nhƣ nêu ở trên khi giảm năng lƣợng truyền sẽ làm tăng số lƣợng bƣớc nhẩy, dẫn đến tăng đáng kể trong độ trễ, đặc biệt ảnh hƣởng rất lớn với mã BCH của FEC. Hình 2.13. (a) Năng lƣợng tiêu thụ trung bình của một luồng. (b) Độ trễ tổng thể trung bình với ngƣỡng (ψTh) cho những Pt khác nhau. Kết luận từ việc so sánh: các phƣơng án kiểm soát lỗi đƣợc sử dụng trong WSN có những ƣu nhƣợc điểm khác nhau. Tuy nhiên, trong WSN phƣơng án kiểm soát lỗi FEC vẫn đƣợc coi trọng hơn cả. Ngoài ra, phƣơng án HARQ cũng đƣợc xem xét kĩ càng trong từng ứng dụng khác nhau. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  52. - 52 - CHƢƠNG 3: BÀI TOÁN KIỂM SOÁT LỖI TRONG WSN 3.1 Vấn đề và giải pháp trong WSN. Trong chƣơng 1 của đồ án đã đề cập đến rất nhiều nội dụng xung quanh WSN, từ cấu tạo của một nút cảm biến không dây cho đến những ứng dụng, những yếu tố ảnh hƣởng đến thiết kế. Nhƣng có một điểm chung đó là xoay xung quanh vấn đề năng lƣợng tiêu thụ. Có thể nói, về phần cứng với khả năng hoạt động độc lập của các nút cảm biến không dây làm WSN hầu nhƣ thích hợp với mọi ứng dụng, mọi địa hình. Tuy nhiên, chính do sự độc lập đó đã tạo ra một yếu tố sống còn của WSN, đó là với một nguồn nuôi vô cùng hạn chế từ Pin khiến nó có thể ngƣng hoạt động bất cứ khi nào một nút mạng bị “hết điện”. Các giải pháp đã đƣợc đƣa ra, để sao cho một nút tiêu thụ năng lƣợng là thấp nhât mà vẫn phải đảm bảo độ tin cậy về dữ liệu cho mạng. Cuối cùng, phƣơng án giảm thiểu truyền thông giữa các nút mạng đƣợc lựa chọn hơn cả, bởi theo những thực nghiệm, các nhà nghiên cứu rút ra một kết luận đó là năng lượng tiêu thụ cho truyền thông tốn hơn rất nhiều so với xử lý. (đƣợc nói cụ thể trong mục 1.5.7). Khi đó, hƣớng tập trung đã đẩy vào vấn đề kiểm soát lỗi, vì kiểm soát lỗi tốt sẽ giúp mạng hoạt động hiệu quả hơn dẫn đến sử dụng năng lƣợng tiết kiệm hơn. Trong kiểm soát lỗi lại chia hai hƣớng chính, đó là ARQ và FEC đã đƣợc trình bầy chi tiết trong mục 2.1.2 và 2.1.3. Cụ thể có thể rút gon nội dung là, với phƣơng án ARQ, khi gặp lỗi tại nơi nhận thì sẽ thực hiện phát lại, còn với FEC thì khi gặp lỗi sẽ phục hồi lỗi ngay tại nơi nhận và truyền tiếp. Chính vì đặc điểm này mà trong WSN, FEC là một lựa chọn hàng đầu vì không tốn chi phí cho phát đi phát lại nhiều lần rất thích hợp với WSN. Một vấn đề đƣợc nghĩ tới, vậy các thuật toán sửa lỗi rất phức tạp, đặc biệt với lỗi đa bít. Do đó, một số nghiên cứu đã đƣợc thực hiện và kết luận, trong WSN lỗi thường gặp là lỗi đơn bít và hai bít lỗi đa bít cũng có nhưng rất ít, trình bầy trong mục 2.1.3. Vậy là, FEC hoàn toàn có thể đƣợc sử dụng một cách hiệu quả trong WSN. Sau đây, là một bài toán cụ thể nhằm củng cố những nhận định về lý thuyết giữa hai phƣơng án kiểm soát lỗi ARQ và FEC trong WSN. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  53. - 53 - 3.2 Bài toán so sánh giữa sửa lỗi và phát lại trong WSN. 3.2.1 Phát biểu bài toán. Bài toán (a): Đối với một kênh truyền dẫn có trung bình là 1 lỗi trong 4000 bit. Những lỗi bit đơn lẻ này đƣợc thống kê độc lập. Một gói cơ sở bao gồm 128 byte. Nó có thể đƣợc truyền: đầy đủ, chính xác hoặc không. Nút nhận có thể phát hiện đƣợc lỗi một gói tin truyền mà không mất chi phí bổ sung. Nếu một lỗi xuất hiện nút nhận yêu cầu nút gửi phát lại duy nhất một lần. Các yêu cầu phát lại đƣợc coi nhƣ một gói thông thƣờng là 128 byte. Nếu lỗi xảy ra trong một yêu cầu nó thì coi nhƣ không có yêu cầu đƣợc gửi đi. Làm thế nào có đƣợc tỷ lệ dữ liệu tổng thể cao trong trƣờng hợp này (theo phần trăm tỷ lệ dữ liệu về mặt lý thuyết có thể đạt đƣợc, nếu không có lỗi)? Bài toán (b): Để cho dễ dàng hơn chúng ta giả định rằng một bít lỗi xẩy ra một lần trên mỗi gói. Thay vì yêu cầu nút gửi phát lại chúng ta chọn phƣơng pháp sửa lỗi trƣơc khi truyền (FEC) với mã Hamming (mã này là không quan trọng trong bài tập này). Làm thế nào có đƣợc tỷ lệ dữ liệu thực tế cao trong trƣờng hợp này (theo phần trăm) so với tính toán theo mặt lý thuyết không sửa lỗi trƣớc và không có lỗi? 3.2.2 Nhận định từ bài toán. Bài toán đƣợc chia hai phần, với hai phƣơng án kiểm soát lỗi thông dụng trong WSN. Mục tiêu chính của hai phần là hƣớng vào tốc độ dữ liệu. Trong trƣờng hợp (a), tuy không nói trực tiếp nhƣng dễ dàng nhận thấy phƣơng án kiểm soát lỗi đƣợc sửa dụng là ARQ do nếu có lỗi xuất hiện trên một gói thì sẽ thực hiện truyền lại gói. Còn trong trƣờng hợp (b), đã nêu trực tiếp phƣơng án sửa lối là FEC. Trong trƣờng hợp (b), thực chất là việc so sánh tốc độ dữ liệu đạt đƣợc khi sửa dụng phƣơng án FEC với ARQ. Để qua đó, có một cái nhìn chính xác về hai phƣơng án này. Bổ sung thêm khảng định về mặt lý thuyết nêu ở chƣơng 2. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  54. - 54 - 3.2.3 Giải quyết bài toán. Giải quyết bài toán (a): Để giải quyết bài toán này, ta phải tập trung vào một số dữ kiện mà đề bài cho dƣới đây. (1) Dữ kiện thứ nhất: “Đối với một kênh truyền dẫn có trung bình là 1 lỗi trong 4000 bit”. Từ đó ta có thể suy ra: - Tỷ lệ lỗi bít (BER) là: pb = 1 / 4000. - Tƣơng ứng một bit đƣợc truyền chính xác với một xác suất = 3999/4000. (2) Dữ kiện thứ hai: “Một gói cơ sở bao gồm 128 byte”. Ta có thể chuyển sang tải trọng bít một lần truyền là (l): l = 128×8=1024 bít. Nhữ đã biết ở chƣơng 2, ARQ chủ yếu sử dụng phƣơng án CRC-16 để phát hiện lỗi kết hợp với hai dữ kiện 1 và dữ kiện 2 ta có thể xác định tỷ lệ lỗi gói (PER). Theo đó, có 2 trƣờng hợp đặt ra: - Trong môi trƣờng lý thuyết, tức là không có lỗi nào xẩy ra thì: Từ đó, có thể tính ra tỷ lệ lỗi gói lý thuyết = (1 – 1/4000)1024 77,4 % - Khi có lỗi xẩy ra do bất kì trƣờng hợp nào. Thì sử dụng công thức 2.41. Ta có thể tính ra tỷ lệ lỗi gói = 1 - (1 – 1/4000)1024 22,6 % (3) Dữ kiện thứ 3: “Gói có thể được truyền đầy đủ, chính xác hoặc không. Nếu một lỗi xuất hiện nút nhận yêu cầu nút gửi phát lại duy nhất một lần. Các yêu cầu phát lại được coi như một gói thông thường là 128 byte. Nếu lỗi xảy ra trong một yêu cầu nó thì coi như không có yêu cầu được gửi đi” Từ dữ kiện 3 này, ta có thể lập một sơ đồ trƣờng hợp xẩy ra khi thực hiện một chu kì gửi gói tin và kiểm soát gói tin với phƣơng án ARQ nhƣ sau: SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  55. - 55 - Quá trình thực hiện như sau: Ban đầu gửi một gói tin, sẽ có 2 trƣờng hợp xẩy ra là có lỗi và không có lỗi. Nếu không có lỗi coi nhƣ truyền thành công. Nếu có lỗi xẩy ra, thì một yêu cầu phát lại đƣợc truyền đi. Đối với yêu cầu phát lại, nếu lỗi xẩy ra với yêu cầu phát lại thì sẽ dừng không phát nữa, ngƣợc lại nếu yêu cầu này thành công thì bên gửi sẽ thực hiện phát lại một lần duy nhât (theo đề bài). Với gói tin phát lại tƣơng ứng xẩy ra hai trƣờng hợp nhƣ lần đầu gửi. tuy nhiên nếu lại có lỗi xẩy ra thì ngừng phát. Từ quá trình hoạt động, gửi một gói tin và những trƣờng hợp xẩy ra với một gói trong quá trình gửi đó. Với tỷ lệ lỗi gói tin trong hai trƣờng hợp không lỗi (0.774) và có lỗi (0.226). Kết quả, ta tìm đƣợc dữ liệu hữu ích trong dấu “( )” và số lƣợng byte mất đi do truyền thông trong dấu “ ”. Từ sở đồ hoạt động và kết quả nhận đƣợc ta xác định đƣợc: - Số lƣợng byte hiệu quả (payload) dự kiến là: 0,774 × 128 + 0,135 × 128 = 116 (byte). - Số lƣợng byte mất mát dự kiến là: 0,135 × 2 × 128 + 0,04 × 3 × 128 + 0,05 × 2 × 128 = 63 (byte). Khi đó, tận dụng khả năng tối đa của kênh ta có đƣợc tỷ lệ dữ liệu tổng thể: Tỷ lệ dữ liệu tổng thể = 116 / (116 + 63) 64,8% SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  56. - 56 - Giải quyết bài toán (b): Nhƣ đã biết FEC là một phƣơng pháp chèn thêm các bít dƣ thừa vào gói dữ liệu để sau này khi có lỗi xẩy ra bên nhận sẽ sử dụng các bít dƣ thừa này để phục hồi dữ liệu nguyên gốc. Cụ thể về cách phục hồi lỗi trong FEC đã đƣợc trình bầy trong mục 2.1.3. Ở đây chỉ đi vào những yếu tố của FEC ảnh hƣởng đến tỷ lệ dữ liệu tổng thể. Với dữ kiện ở bài toán (b) “giả định rằng một bít lỗi xảy ra một lần trên mỗi gói”, tức là ở bài toán này chỉ có lỗi đơn bít xẩy ra. Bởi vậy nằm trong khả năng sửa lỗi của FEC trình bầy trong mục 2.1.3. Do việc truyền lại của FEC là không có do vậy dữ liệu chỉ có duy nhất một trƣờng hợp là gói luôn đến nút nhận. Tuy nhiên, nhƣ đã nói ở trên, FEC cần chèn thêm các bít dƣ thừa vào dữ liệu, vì vậy tỷ lệ dữ liệu hƣu ích phải loại bỏ thành phần này. Để tính toán ra số lƣợng bít dƣ thừa, bằng cách: từ dữ kiện 2 ở bài toán (a), ta có tải trọng gói tin là: 1024 bit. Qua đó, để bảo vệ 1024 bit dữ liệu chống lại 1 lỗi bit thì phải thêm số lƣợng bít dƣ thừa (r) theo bất đẳng thức sau đây: 1024 + r + 1 <= 2r Từ đó, có thể thấy r=11 là thỏa mãn với bất đẳng thức trên. Vì : 1024 + 11 + 1 <= 211 = 2048. Qua đó có thể xác định tỷ lệ dữ liệu tổng thể = 1024 / (1024 + 11) 98,9% Một hướng giải quyết khác của bài toán (b): Nếu nhƣ, trong gói tin (128 byte ) đã có chứa sẵn các bít dƣ thừa rồi thì: tỷ lệ dữ liệu tổng thể = (1024 - 11) / 1024 98,9%. Nếu các bit kiểm lỗi đƣợc sắp xếp theo byte, thi tinh toán sẽ là (1024-16)/1024=98.4% , ở đây con số 16 là do 11 bit xếp theo byte là 2 byte. Kết luận từ bài toán: Bằng những số liệu chính xác từ bài toán nêu trên, ta thấy phƣơng án kiểm soát lỗi FEC và ARQ với cùng một tải trọng gói tin, cùng điều kiện truyền tuy nhiên với FEC với khả năng phục hồi lỗi trực tiếp tại nơi nhận hiệu quả hơn rất nhiều so với ARQ. Bằng chứng là thông qua tỷ lệ dữ liệu tổng thể đối với ARQ chỉ là 64,8% còn với FEC là 98,9%. Qua đó có thể khẳng định, trong WSN phƣơng án FEC hoàn toàn chiếm ƣu thế so với phƣơng án ARQ về mặt hiệu quả dữ liệu. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  57. - 57 - KẾT LUẬN Những vấn đề đã nghiên cứu đƣợc: Nắm đƣợc tổng quan về mạng cảm biến không dây (WSN), về thành phần của một nút cảm biến không dây (phần cứng, phần mềm và chuẩn nút), đồng thời cung cấp thông tin phân loại một số loại nút cảm biến không dây hiện nay đang đƣợc sử dụng phổ biến. Giới thiệu một số ứng dụng của mạng cảm biên không dây trong các lĩnh vực nhƣ: quân sự, y tế, công nghiệp, môi trƣờng và sử dụng tại nhà. Từ đo, đƣa ra các yếu tố ảnh hƣởng đến thiết kế mạng và chỉ ra yếu tố sống còn trong thiết kế mạng cảm biến không dây. Nhƣ một giải pháp, củng cố khả năng hoạt động hiệu quả của mạng truyền thông nói chung, và đặc biệt quan trọng với mạng cảm biến không dây nói riêng, đó là vấn đề kiểm soát lôi trong truyền thông. Tìm hiểu đƣợc đặc điểm lỗi chính của WSN gặp phải là lỗi đơn bít và hai bít, Lần lƣợt đƣa ra các phƣơng án kiểm soát lỗi từ đơn giản đến phức tạp, bằng những số liệu chính xác từ thực nghiệm hay mô hình lớp chéo, đƣa ra những so sánh công bằng giữa các phƣơng án kiểm soát lỗi. Để củng cố về mặt lý thuyết nêu ra, một bài toán cụ thể đã đƣợc giải quyết với mục đích tăng tính thuyết phục cho việc so sánh hai phƣơng án kiểm soát lỗi chính trong mạng cảm biến không dây ARQ và FEC. Để cuối cùng đƣa ra khẳng định Phương án FEC hoàn toàn chiếm ưu thế so với phương án ARQ trong mạng cảm biến không dây. Những vấn đề tồn tại cần đƣợc giải quyết: Trong các phƣơng án kiểm soát lỗi trong mạng cảm biến không dây, HARQ hay ARQ lai ghép thực sự hiệu quả hơn FEC trên một số thí nghiệm. Điều này cho thấy, phƣơng án HARQ có thể là một phƣơng án rất tốt khi áp dụng trong WSN. Tuy nhiên, nó chƣa đƣợc nghiên cứu kĩ càng trong đồ án. Đã củng cố lý thuyết về vấn đề kiểm soát lỗi. Tuy nhiên, chỉ với một bài toán so sánh ARQ và FEC thông qua tỉ lệ dữ liệu tổng thể, chƣa thể chứng minh hoàn toàn việc chiếm ƣu thế của FEC trong WSN. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu
  58. - 58 - TÀI LIỆU THAM KHẢO [1]. Ian F. Akyildiz and Mehmet Can Vuran, Wireless Sensor Networks, 2010. [2]., Jaein Jeong and Cheng Tien Ee, Department of Electrical Engineering and Computer Science, Forward Error Correction in Sensor Networks, University of California, Berkeley 2003. [3]. A. J. Goldsmith, Wireless Communications, 2005. [4]. Thomas Haenselmann, Sensor Network, 2008. [5]. S.Lin and D.J.Costello Jr, Error Control Coding:Fundamentals and Applications,1983. [6]. M. C. Vuran and I. F. Akyildiz, Error control in wireless sensor networks: a cross layer analysis. IEEE/ACM Transactions on Networking, 2009. [7]. L. C. Zhong and J. M. Rabaey, An integrated data-link energy model for wireless sensor networks. In Proceedings of IEEE ICC’04, 2004. SV- Hồ Anh Tuấn - CT1101 WSN – Đặc điểm sửa lỗi truyền dữ liệu