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

sau khi chúng được nhận. Lớp điều khiến đa truy cập Media – Access – Control (MAC) chuyển tiếp lớp ứng dụng với radio chip : + Khi 1 gói tin được gửi đi nhờ 1 ứng dụng, gói tin được phân nhỏ thành các byte. 1 chuỗi liên tiếp các byte đặc biệt được gọi là Preamble (phần mở đầu) được gửi đi trước các byte dữ liệu do đó phía thu có thể đồng bộ và xác định phần bắt đầu của 1 gói tin. 45 + Sau khi nhận 1 byte, radio chip mã hoá bit dữ liệu và truyền chúng. Ở phía nhận, radio chip báo hiệu việc đến của các byte sau khi xác định và giải mã các bit dữ liệu. + Sau đó lớp MAC hợp lại gói đầu tiên sau gói preamble. Tiếp theo lớp MAC báo hiệu việc đến của gói tin cho lớp trên. Các byte dữ liệu có thể được mã hoá một cách tuỳ ý sau khi được phân đoạn cùng với mã sửa lỗi (ECC – Error correction code) để khôi phục các bit dữ liệu trong trường hợp có số lượng nhỏ các bit bị lỗi. Có một hay nhiều các byte dữ liệu được xếp về phía trong của chuỗi các byte dữ liệu khác cái mà sau đó cũng đã được truyền qua radio chip. Ở phía bộ thu, các byte dữ liệu đã được nhận , và được mã hoá để trở về dạng các byte dữ liệu gốc. Bộ điều biến bit chuyển 1 bit vào thành 1 chuỗi bit trong dạng tương tự. Lược đồ điều biến bit đơn giản nhất là mã hoá NRZ (Non-Return to Zero). Mã hoá NRZ 1 cách đơn giản tạo ra 1 dạng sóng (của tín hiệu) với mức điện áp tương ứng: A cho đầu vào bit 0 và B cho đầy vào bit 1. Bộ thu phát radio giữ vết của tín hiệu tương tự có nghĩa để phân biệt với các bit đang dồn đến. Bằng việc so sánh các tính hiệu thu được với mức trung bình, bộ thu phát truyển đổi dạng sóng tương tự thành bit nhị phận 0 hay 1. Việc này có thể sinh ra 1 vấn đề khi có một chuỗi dài là 0 hay 1, cái mà lệch với mức tín hiệu tương tự có nghĩa, do đó giảm khả năng phiên dịch đúng của bộ thu phát đối với tính hiệu số được truyền. Trong mã hoá NRZ, việc nhồi bit, chính là chúng ta thêm vào phần bổ sung sau chính bit đầu vào đó, nó là cần để thực hiện loại bỏ vấn đề này. Mã hoá Manchester loại bỏ vấn đề này nhờ việc tạo ra các số 0 và 1 giống nhau cho bất kỳ chuỗi bit nào. Lược đồ mã hoá này mã hoá một 0 thành sự chuyển đổi từ A  B và 1 thành sự chuyển đổi từ B  A. Ví dụ được chỉ ra ở hình. 46 Hình 2.2 Mã hoá NRZ và mã hoá Manchester ChipCon radio là bộ thu phát radio mà hiện tại được sử dụng trong phiên bản mới nhất của các nút mạng cảm nhận không dây. Được so sánh với radio RFM cái mà được sử dụng trong platform sớm hơn, ChipCon radio có một số đặc tính được cải tiến. Đầu tiên, đó là các nút cảm biến không dây với các radio ChipCon có phạm vi lớn hơn radio RFM. Trong quá trình kiểm nghiệm ngoài trời, các nút cảm biến ChipCon đã có phạm vi khoảng 1000 feet, trong khi các nút cảm biến RFM vào khoảng 400 feet. Thứ 2 đó là, các bit dữ liệu được điểu chế sử dụng FSK (Frequency Shift Keying) khiến cho dữ liệu truyền đi có tính đàn hồi so với ồn (noise). Cuối cùng , radio ChipCon hỗ trợ mã hoá Manchester ở thiết bị phần cứng, cho phép các bit dữ liệu được truyền dẫn mà không cần phải rõ ràng ; phần mềm sử dụng cân bằng DC (software-level DC balancing). Hình 2.3 Mã hoá bit 47 Mã sửa lỗi của radio RFM không phù hợp so với radio ChipCon bởi vì nó nhồi bít một cách không cần thiết cho sự cân bằng DC. Hình trên chỉ ra cách mà 1 byte được mã hoà thành 3 byte từ mã. Ví dụ, nếu bit thứ 8 của byte dữ liệu là 1, thì từ mã có 1 trong bit thứ 8 của byte thứ 3 và 0 trong bit thứ 7. Nếu bít thứ 8 của byte là 0, thì từ mã có 0 và 1 trong bit thứ 8 và 7 trong byte thứ 3. 2.2 Các loại lỗi bit Khi truyền dữ liệu từ node này đến node khác, các tín hiệu dạng nhị phân “0” và “1” nếu bị lỗi có thể biến đổi từ “0” thành “1” và từ “1” thành “0”, có ba loại lỗi thường gặp đó là lỗi đơn bit, đa bit và đảo bit. Hình 2.4 Lỗi bit trong quá trình truyền nhận dữ liệu 2.3 Phát hiện lỗi Khi một node nhận gói tin từ node khác gửi đến, làm thế nào để nó có thể biết một trong những lỗi trên xảy ra, trừ trường hợp nó phải gửi mỗi đơn vị dữ liệu hai lần rồi node nhận so sánh hai đơn vị dữ liệu nhận được theo từng bit một, từ đó phát hiện ra lỗi. Nhưng như vậy thì làm mất hai lần thời gian để so sánh từng bit dữ liệu, cộng thêm thời gian để so sánh từng bit dữ liệu. Phương pháp này không hiệu quả do thời gian xử lý một gói tin gấp hai lần bình thường, và dữ liệu đến lần trước và lần sau cũng không biết được lần nào bị lỗi. Rõ ràng phải có cơ chế phát hiện lỗi vừa đơn giản mà không làm tốn thời gian truyền của gói tin trong mạng hay làm giảm hiệu năng mạng. Chỉ bằng cách đưa vào các thông tin dư thừa trong quá trình truyền nhằm mục đích so sánh, thay thế việc lặp toàn bộ dữ liệu, chỉ cần một nhóm nhỏ các bit thêm vào cuối mỗi đơn vị dữ liệu. Kỹ thuật này gọi là dư thừa bởi vì một số bit bên ngoài được thêm vào là thừa so với thông tin cần gửi đi. Những bit dư 48 thừa này sẽ được bỏ đi, khi thông tin truyền tới nơi nhận đã được kiểm tra và xác nhận là không bị lỗi. Hình 2.5 Phương pháp sử dụng bit dư thừa Mỗi khi chuỗi bit dữ liệu được phát đi đều phải đi qua một thiết bị phân tích và bổ sung vào một chuỗi dữ liệu đó, mã kiểm tra dư thừa thích hợp. Đơn vị dữ liệu trở nên lớn hơn bởi một số bit thêm vào, tất cả được truyền lên đường liên kết đến nơi nhận. Thiết bị nhận đặt toàn bộ chuỗi này vào một khối kiểm tra. Nếu chuỗi dữ liệu nhận được, đi qua được khối kiểm tra thì phần dữ liệu sẽ được nhận còn các bit dư thừa sẽ được bỏ qua.[4] Có 4 cách để kiểm tra dư thừa đó là: - Kiểm tra dư thừa đứng VRC, hay còn gọi là kiểm tra chẵn lẻ - Kiểm tra dư thừa dài LRC - Kiểm tra dư thừa tuần hoàn CRC - Tổng kiểm tra Checksum Kiểm lỗi dư thừa tuần hoàn CRC Phương pháp kiểm lỗi này có độ tin cậy cao nhất. VRC và LRC dựa vào việc bổ sung thêm số bit, còn CRC dựa vào phép chia nhị phân. Trong CRC chuỗi các bit dư thừa được gọi là số dư CRC, sẽ bổ sung thêm vào cuối đơn vị dữ liệu sao cho đơn vị dữ liệu mới này là chia không dư cho số nhị phân được quy định trước và sử dụng ở nơi gửi. Khi đó đơn vị dữ liệu được xem là không 49 lỗi và sẽ được nhận. Trường hợp phép chia có dư, nghĩa là đơn vị dữ liệu đã bị lỗi và không được nhận. Các bit dư thừa CRC được nơi gửi tính bằng cách chia đơn vị dữ liệu cho một số chia xác định trước, số dư chính là CRC. CRC phải có ít hơn số chia một bit và phải bổ sung vào cuối dữ liệ. Hình dưới minh hoạ quá trình kiểm lỗi CRC: Hình 2.6 Quá trình kiểm lỗi CRC Đầu tiên thêm n bit “0” vào cuối đơn vị dữ liệu, số n ít hơn số chia 1 bit. Tiếp theo đơn vị dữ liệu mới này được chia cho số chia. Số dư của phép chia chính là CRC. CRC thu được, thay cho các bit “0” ở cuối đơn vị dữ liệu. Nếu số dư ít hơn n bit thì bổ sung thêm số 0 vào các bit bên trái. Nếu phép chia không dư thì n số 0 được đặt làm số dư và nó là CRC.. Đơn vị dữ liệu chuyển tiếp đến thiết bị nhận, dữ liệu đến trước và theo sau là CRC. Thiết bị nhận xem toàn bộ dữ liệu này như một đơn vị và chia nó cho cùng một số chia đã được sử dụng ở bên gửi. Nếu chuỗi dữ liệu khi được kiểm tra CRC cho số dư bằng 0 được xem là không lỗi và được nhận. Nếu chuỗi dữ liệu bị thay đổi trong quá trình truyền, số dư sẽ khác 0 và đơn vị dữ liệu bị lỗi, không nhận được. 50 CRC phát hiện tất cả các lỗi, trừ khi giá trị các bit của khối chính xác bằng giá trị của số chia. Số chia CRC thông dụng là 13, 17 và 33, bảo đảm phát hiện hết lỗi. Hình 2.7 Phép chia nhị phân để tìm CRC Hình trên mô tả quá trình tạo ra CRC, dữ liệu là 111001, số chia là 11001. Số chia trong phép chia phải được chọn sao cho thực hiện phép chia nhị phân được dễ dàng và kết quả phép chia có dư. Nó được suy từ một đa thức sinh: Đa thức có thể biểu diễn dưới dạng khác: 51 Các hệ số trong đa thức lập thành 1011 là số chia. Do đó với CRC-12 thì số chia có 13 bậc nhị phân, CRC-16 thì số chia có 17 bậc nhị phân, CRC-32 thì số chia có 33 bậc nhị phân. 2.4 Sửa lỗi Sửa lỗi được thực hiện bằng hai cách đó là thiết bị nhận yêu cầu thiết bị gửi truyền lại toàn bộ dữ liệu đã gửi. Cách khác, thiết bị nhận sử dụng mã sửa lỗi tự động sửa một số lỗi nhất định.[3] Trên lý thuyết, có thể tự động sửa lỗi bất kỳ lỗi nhị phân nào. Mã sửa lỗi đòi hỏi nhiều bit dư thừa hơn so với mã phát hiện lỗi. Số bit cần để sửa các lỗi đa bit và lỗi đảo bit lớn đến nỗi trong nhiều trường hợp nó trở nên không còn hiệu quả. Vì vậy trong hầu hết các thao tác sửa lỗi chỉ giới hạn ở một, hai, hoặc ba bit lỗi trong một đơn vị dữ liệu. Mã Hamming Mã Hamming là một mã sửa lỗi tuyến tính (linear error-correcting code), được đặt tên theo tên của người phát minh ra nó, Richard Hamming. Mã Hamming có thể phát hiện một bit hoặc hai bit bị lỗi (single and double-bit errors). Mã Hamming còn có thể sửa các lỗi do một bit bị sai gây ra.[4] Xét dữ liệu 7 bit thì cần 4 bit dư thừa để thêm vào cuối đơn vị dữ liệu hoặc chèn vào những bit dữ liệu gốc Hình 2.8 Cách chèn các bit dư thừa vào dữ liệu Trên hình vẽ, các bit dư thừa được đặt vào vị trí 1, 2, 4 và 8 và được ký hiệu là r1, r2, r4, r8. Trong mã Hamming mỗi bit r là VRC của một tổ hợp các bit dữ liệu. Các tổ hợp được sử dụng để tính một trong bốn giá trị của r như sau: r1: bit 1, 3, 5, 7, 9, 11 52 r2: bit 2, 3, 6, 7, 10, 11 r4: bit 4, 5, 6, 7 r8: bit 8, 9, 10, 11 Mỗi bit dữ liệu có thể tham gia vào nhiều tính toán VRC. Sự thể hiện nhị phân của mỗi vị trí: ví dụ như bit r1 có đại diện nhị phân chứa 1 ở vị trí bên phải nhất của các vị trí 1, 3, 5, 7, 9, 11 Lấy ví dụ chúng ta có một từ dữ liệu dài 7 bit với giá trị là "0110101". Để chứng minh phương pháp các mã Hamming được tính toán và được sử dụng để kiểm tra lỗi, xin xem bảng liệt kê dưới đây. Chữ d (data) được dùng để biểu thị các bit dữ liệu và chữ p (parity) để biểu thị các bit chẵn lẻ (parity bits). Đầu tiên, các bit của dữ liệu được đặt vào vị trí tương thích của chúng, sau đó các bit chẵn lẻ cho mỗi trường hợp được tính toán dùng quy luật bit chẵn lẻ số chẵn Hình 2.9 Cách tính các bit chẵn lẻ trong mã Hamming Nhóm dữ liệu mới (new data word) - bao gồm các bit chẵn lẻ - bây giờ là "10001100101". Nếu chúng ta thử cho rằng bit cuối cùng bị thoái hóa (gets corrupted) và bị lộn ngược từ 1 sang 0. Nhóm dữ liệu mới sẽ là "10001100100". Dưới đây, sẽ phân tích quy luật kiến tạo mã Hamming bằng cách cho bit chẵn lẻ giá trị 1 khi kết quả kiểm tra dùng quy luật số chẵn bị sai. 53 Hình 2.10 Kiểm tra các bit chẵn lẻ Bước cuối cùng là định giá trị của các bit chẵn lẻ (nên nhớ bit nằm dưới cùng được viết về bên phải - viết ngược lại từ dưới lên trên). Giá trị số nguyên của các bit chẵn lẻ là 11, và như vậy có nghĩa là bit thứ 11 trong nhóm dữ liệu (data word) - bao gồm cả các bit chẵn lẻ - là bit có giá trị không đúng, và bit này cần phải đổi ngược lại. Việc đổi ngược giá trị của bit thứ 11 làm cho nhóm 10001100100 trở lại thành 10001100101. Bằng việc bỏ đi phần mã Hamming, chúng ta lấy được phần dữ liệu gốc với giá trị làn0110101. Các bit chẵn lẻ không kiểm tra được lẫn nhau, nếu chỉ một bit chẵn lẻ bị sai thôi, trong khi tất cả các bit khác là đúng, thì chỉ có bit chẵn lẻ nói đến là sai mà thôi và không phải là các bit nó kiểm tra (not any bit it checks). Cuối cùng, giả sử có hai bit biến đổi, tại vị trí x và y. Nếu x và y có cùng một bit tại vị trí 2k trong đại diện nhị phân của chúng, thì bit chẵn lẻ tương ứng với vị trí đấy kiểm tra cả hai bit, và do đó sẽ giữ nguyên giá trị, không thay đổi. Song một số bit chẵn lẻ nào đấy nhất định phải bị thay đổi, vì x ≠ y, và do đó hai bit tương ứng nào đó có giá trị x và y khác nhau. Do vậy, mã Hamming phát hiện tất cả các lỗi do hai bit bị thay đổi, song nó không phân biệt được chúng với các lỗi do 1 bit bị thay đổi. Hiện thời, khi nói đến mã Hamming chúng ta thực ra là muốn nói đến mã (7,4) mà Hamming công bố năm 1950. Với mỗi nhóm 4 bit dữ liệu, mã Hamming thêm 3 bit kiểm tra. Thuật toán (7,4) của Hamming có thể sửa chữa 54 bất cứ một bit lỗi nào, và phát hiện tất cả lỗi của 1 bit, và các lỗi của 2 bit gây ra. Điều này có nghĩa là đối với tất cả các phương tiện truyền thông không có chùm lỗi đột phát (burst errors) xảy ra, mã (7,4) của Hamming rất có hiệu quả (trừ phi phương tiện truyền thông có độ nhiễu rất cao thì nó mới có thể gây cho 2 bit trong số 7 bit truyền bị đảo lộn). Nguyên lý của mã Hamming bắt nguồn từ việc khai triển và mở rộng quan điểm chẵn lẻ. Việc khai triển này bắt đầu bằng việc nhân các ma trận, được gọi là Ma trận Hamming (Hamming matrices), với nhau. Đối với mã Hamming (7,4), chúng ta sử dụng hai mã trận có liên quan gần gũi, và đặt tên cho chúng là: và Các cột vectơ trong He là nên tảng hạch của Hd và phần trên của He (4 hàng đầu) là một ma trận đơn vị (identity matrix). Ma trận đơn vị cho phép vectơ dữ liệu đi qua trong khi làm tính nhân, và như vậy, các bit dữ liệu sẽ nằm ở 4 vị trí trên cùng (sau khi nhân). Sau khi phép nhân hoàn thành, khác với cách giải thích ở phần trước (các bit chẵn lẻ nằm ở vị trí 2k), trật tự của các bit trong từ mã (codewords) ở đây khác với cách bố trí đã nói (các bit dữ liệu nằm ở trên, các bit kiểm chẵn lẻ nằm ở dưới). Chúng ta dùng một nhóm 4 bit dữ liệu (số 4 trong cái tên của mã là vì vậy) chủ chốt, và cộng thêm vào đó 3 bit dữ liệu thừa (vì 4+3=7 nên mới có số 7 trong cái tên của mã). Để truyền gửi dữ liệu, chúng ta hãy nhóm các bit dữ liệu 55 mà mình muốn gửi thành một vectơ. Lấy ví dụ, nếu dữ liệu là "1011" thì vectơ của nó là: Giả sử, chúng ta muốn truyền gửi dữ liệu trên. Chúng ta tìm tích của He và p, với các giá trị môđulô 2: Máy thu sẽ nhân Hd với r, để kiểm tra xem có lỗi xảy ra hay không. Thi hành tính nhân này, máy thu được: Vì chúng ta được một vectơ toàn số không cho nên máy thu có thể kết luận là không có lỗi xảy ra Sở dĩ một vectơ toàn số không có nghĩa là không có lỗi, bởi vì khi He được nhân với vectơ dữ liệu, một sự thay đổi trong nền tảng xảy ra đối với không gian bên trong vectơ (vector subspace), tức là hạch của Hd. Nếu không có vấn đề gì xảy ra trong khi truyền thông, r sẽ nằm nguyên trong hạch của Hd và phép nhân sẽ cho kết quả một vectơ toàn số không. Trong một trường hợp khác, nếu chúng ta giả sử là lỗi một bit đã xảy ra. Trong toán học, chúng ta có thể viết: 56 trong đó ei là vectơ đơn vị đứng thứ i (ith unit vector), có nghĩa là, một vectơ số 0 có một giá trị 1 trong vị trí i. Biểu thức trên nói cho chúng ta biết rằng có một bit bị lỗi tại vị trí i. Nếu bây giờ chúng ta nhân Hd với cả hai vectơ này: Vì r là dữ liệu thu nhận được không có lỗi, cho nên tích của Hd và r bằng 0. Do đó Vậy, tích của Hd với vectơ nền chuẩn tại cột thứ i (the ith standard basis vector) làm lộ ra cột ở trong Hd, vì thế mà chúng ta biết rằng lỗi đã xảy ra tại vị trí cột này trong Hd. Vì chúng ta đã kiến tạo Hd dưới một hình thức nhất định, cho nên chúng ta có thể hiểu giá trị của cột này như một số nhị phân - ví dụ, (1,0,1) là một cột trong Hd, tương đồng giá trị với cột thứ 5, do đó chúng ta biết lỗi xảy ra ở đâu và có thể sửa được nó. Lấy ví dụ, giả sử chúng ta có: Nếu thi hành phép nhân: Tích của phép nhân cho chúng ta một kết quả tương đương với cột thứ 2 ("010" tương đương với giá trị 2 trong số thập phân), và do đó, chúng ta biết rằng lỗi đã xảy ra ở vị trí thứ 2 trong hàng dữ liệu, và vì vậy có thể sửa được lỗi. 57 Chúng ta có thể dễ dàng thấy rằng, việc sửa lỗi do 1 bit bị đảo lộn gây ra, dùng phương pháp trên là một việc thực hiện được. Bên cạnh đó, mã Hamming còn có thể phát hiện lỗi do 1 bit hoặc 2 bit bị đảo lộn gây ra, dùng tích của Hd khi tích này không cho một vectơ số không. Tuy thế, song mã Hamming không thể hoàn thành cả hai việc. 58 Chương 3: MÃ ĐIỀU KHIỂN LỖI SỬ DỤNG TRONG WSN 3.1 Giới thiệu Các nút cảm nhận thường nhỏ, và khi được lắp với các cảm nhận khác như các cảm nhận nhiệt độ số nó sẽ làm việc giống như các truyền thông không dây. Những tính năng này cho phép các mạng cảm cảm nhận dễ dàng được thực hiện trong tất cả các kiểu môi trường, và chúng ta mong rằng các mạng trở nên phổ dụng ở khắp mọi nơi trong tương lai không xa. Tuy nhiên, có một yếu tố nhỏ khiến cho các cảm nhận bị giới hạn về năng lượng. Bảng sau cho thấy sự tiêu thụ điện năng do các kiểu lệnh khác nhau được xác định: Bảng 3.1 Sự tiêu thụ điện năng trong các node cảm biến Từ bảng trên đã cho thấy rằng hầu hết điện năng bị tiêu thụ trong suốt quá trình truyền dẫn và tiếp nhận dữ liệu. Bằng việc sử dụng mã sửa lỗi (ECC) mà ở đây cụ thể là FEC, sẽ giảm được số lượng gói dữ liệu tái truyền phát, theo cách đó giảm được sự tiêu hao năng lượng trong quá trình xử lý. 3.2 Lý thuyết về mã hoá Lý thuyết mã hóa (Coding Theory) nhằm giải quyết tình trạng lỗi dễ xảy ra trong quá trình truyền thông số liệu trên các kênh truyền có độ nhiễu cao (noisy channels), dùng những phương pháp tinh xảo khiến phần lớn các lỗi xảy ra có thể được chỉnh sửa. Nó còn xử lý những đặc tính của mã (codes), và do vậy giúp phù hợp với những ứng dụng cụ thể. Có hai loại mã hoá: - Mã hóa nguồn (Mã hóa Entropy - Entropy encoding) 59 - Mã hóa trên kênh truyền (Sửa lỗi chuyển tiếp - Forward Error Correction) Mã hóa nguồn mục đích của phương pháp này là nén dữ liệu từ chính nguồn của nó, trước khi truyền đi, giúp cho việc truyền thông có hiệu quả hơn. Mã hóa trên kênh truyền thực hiện việc cộng thêm những bit mới vào trong dữ liệu được truyền, còn gọi là bit chẵn lẻ (parity bits), kỹ thuật này giúp cho việc truyền thông tín hiệu chính xác hơn trong môi trường nhiễu loạn của kênh truyền thông. Có nhiều chương trình ứng dụng, sử dụng mã hóa trên kênh truyền. Vì mã hoá nguồn không phù hợp trong mạng cảm biến nên ở trong phần này ta chỉ xét đến mã hoá kênh truyền. Mục đích lý thuyết của mã hóa trên kênh truyền (channel encoding theory) là tìm những mã có thể truyền thông nhanh chóng, chứa đựng nhiều mã ký (code word) hợp lệ và có thể sửa lỗi (error correction) hoặc ít nhất phát hiện các lỗi xảy ra (error detection). Các mục đích trên không phụ thuộc vào nhau, và mỗi loại mã có công dụng tối ưu cho một ứng dụng riêng biệt. Những đặc tính mà mỗi loại mã này cần còn tuỳ thuộc nhiều vào xác suất lỗi xảy ra trong quá trình truyền thông. Mã hoá kênh truyền được chia làm hai loại chính: - Mã khối tuyến tính (Linear block codes) - Mã kết hợp (Convolutional codes) Mã khối tuyến tính mang tính năng tuyến tính (linearity), chẳng hạn tổng của hai mã ký nào đấy lại chính là một mã ký và chúng được ứng dụng vào các bit của nguồn trên từng khối một. Bất cứ mã khối tuyến tính nào cũng được đại diện là (n,m,dmin), trong đó: - n là chiều dài của mã ký, ký hiệu symbols - m là số ký hiệu nguồn (source symbols) được dùng để mã hóa tức thời - dmin là khoảng cách Hamming tối thiểu của mã (The Minimum Hamming Distance For The Code) Có nhiều loại mã khối tuyến tính, như: - Mã tuần hoàn (Cyclic codes) (Mã Hamming là một bộ phận nhỏ của mã tuần hoàn) - Mã tái diễn (Repetition codes) - Mã chẵn lẻ (Parity codes) 60 - Mã Reed-Solomon (Reed Solomon codes) - Mã BCH (BCH code) - Mã Reed-Muller - Mã hoàn hảo (Perfect codes) Mã kết hợp (Convolutional Codes) được sử dụng trong các modem dải tần âm (voiceband modems) và trong các điện thoại di động, cũng như trong các thiết bị truyền thông của quân đội vũ trang và trong các thiết bị truyền thông với vệ tinh. 3.3 Phương pháp sửa lỗi chuyển tiếp FEC FEC được liên kết với một mã nhân chập khối bên trong để truyền dữ liệu tới hạn một cách thông suốt, như các truy nhập điều khiển khung và truy nhập khởi đầu. Hình 3.2 Cơ chế sửa lỗi FEC 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. 61 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). Ví dụ : v1 = 10101010 v2 = 10101111 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. Bổ đề tự sửa lỗi được ứng dụng trong FEC 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. - Nếu khoảng cách hamming nhỏ nhất dmin >= 2e+1 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. - Nếu dmin >= 2e 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. 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 đó: 0 2 e m i n i C   Điều kiện cần để bộ mã có thể tự sửa lỗi là Điều kiện đủ để bộ mã có thể tự sửa lỗi (theo Vasharmov-Gilbert- Sacks) 1 0 2 e m i n i C    62 Với: ! !*( )! i n nC i n i   Ví dụ: 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 : 000 cách 010, 001 bởi 1 cạnh 011 cách 010, 111 và 001 bởi 1 cạnh. 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 Vậy nếu có lỗi phát sinh thì chỉ phát hiện chứ không sửa được. Như vậy ta có thể phân dạng các loại lỗi sau: - Lỗi có thể tự điều chỉnh: Gọi w i W 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). 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ã w*i W 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 - 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 => không thể giải mã chính xác. - 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. 3.3.1 Mã hoá khối tuyến tính Linear Block Codes Mã hoá khối tuyến tính là một lớp mã được dùng rất phổ biến trong việc chống nhiễu. Loại mã này được xây dựng dựa trên các kết quả của đại số tuyến tính. Ở đây chúng ta chỉ nghiên cứu về mã nhị phân vì dữ liệu ở dạng nhị phân. 63 Hình 3.3 Mã hoá, truyền dẫn và giải mã dữ liệu Mã hoá thông điệp m thành từ mã v có thể được thực hiện bằng việc nhân m với ma trận sinh G. Xét một đơn vị dữ liệu gồm k bit, và r là số bit chẵn lẻ được thêm vào.[5] Ma trận sinh G sẽ có dạng: Với Ik là ma trận đơn vị dạng kxk và C ma trận nhị phân dạng k x r. Khi đó ta sẽ có phương trình : v = uG Ở phía đầu cuối của bộ thu, syndrome s được tính toán để xác định khả năng sửa các lỗi. Ma trận chẵn lẻ H được tạo ra từ ma trận sinh G với : Nếu gọi vector lỗi là e thì chúng ta có: Ở đây 64 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 hàng hay tổng của các hàng trong H. Phía thu sau đó có thể giải mã các từ mã đã được sửa lỗi bằng việc giả phương trình v=uG . Một cách đặc biệt, cho mã hệ thống đó là k cột đầu tiên của ma trận sinh G chính là dạng của ma trận đơn vị v. 3.3.1.1 Cách mã hoá Nếu: là thông tin cần được mã hoá thì từ mã v tương ứng với u được xác định công thức uxG hay Vì các từ mã tương ứng với các thông báo được sinh ra bởi G theo cách như trên nên G được gọi là ma trận sinh của bộ mã. 3.3.1.2 Cách giải mã Gọi thông báo là u = (a0,a1,a2,a3) và từ mã tương ứng là v = (b0,b1,b2,b3,b4,b5,b6), ta có phương trình sau liên hệ giữa u và v: 65 Suy ra: Hệ phương trình này gọi là hệ phương trình giải mã Giải hệ phương trình trên thu được kết quả là: Do đó dữ liệu thu được ở bên nhận 3.3.1.3 Các phát hiện lỗi Nếu v là một từ mã được sinh ra từ ma trận sinh G có ma trận trực giao tương ứng là H, thì do v là một tổ hợp tuyến tính của các vectơ hàng của G nên: Và ngược lại nếu: thì v phải là một tổ hợp tuyến tính của các vectơ hàng của G do đó v là một từ mã. 66 Syndrome – vectơ sửa sai (corrector) có dạng Do đó ta có v là từ mã khi và chỉ khi s(v) = 0 Với tính chất này ta có H có thể được sử dụng để kiểm tra một tổ hợp có phải là từ mã không hay nói cách khác H có thể được dùng để phát hiện sai. Vì lý do này mà ma trận H còn được gọi là ma trận kiểm tra Ma trận kiểm tra của một bộ mã ma trận sinh G(kxn) là ma trận H có kích thước (n – k)xn sao cho: 3.3.1.4 Cách sửa lỗi Xét vector lỗi là vectơ biểu diễn các vị trí lỗi giữa từ mã truyền và tổ hợp nhận, mỗi vị trí lỗi được biểu diễn bằng bit 1, các vị trí còn lại sẽ có giá trị 0. Nếu từ mã được truyền đi là w, vectơ lỗi là e và vectơ nhận là v thì: Ví dụ nếu từ mã w = 1011011, vectơ lỗi là e = 0010100 có nghĩa là sai ở vị trí số 3 và 5 (tính từ trái, bắt đầu bằng 1) thì vectơ nhận sẽ là v = w + e = 1001111. Ngược lại nếu từ mã w = 0110010 còn vec tơ nhận là v = 0010011 thì vectơ lỗi là e = w + v = 0100001 có nghĩa là đã có sai xảy ra ở các vị trí số 2 và số 7. Trọng số của vectơ lỗi biểu diễn khoảng cách Hamming giữa từ mã phát và tổ hợp nhận. Khái niệm trên gợi ý cho chúng ta một điều như sau, nếu vectơ nhận là v thì chúng ta có thể tính được vectơ lỗi tương ứng với mỗi từ mã bằng cách cộng v với lần lượt các từ mã và rồi dựa vào nguyên lý khoảng cách Hamming tối thiểu chúng ta thấy rằng vectơ lỗi nào có trọng số nhỏ nhất thì từ mã tương ứng chính là từ mã đã được phát đi. Xét một mã tuyến tính C(7x4) có ma trận hệ thống như sau: 67 Với bộ ma trận kiểm tra của bộ mã trên như sau: Bộ mã trên có khoảng cách Hamming d = 3. Vì vậy có thể phát hiện sai 2 bit và sửa sai được 1 bit. Giả sử đường truyền sai tối đa 1 bit. Và vectơ nhận là v = 1010110, tìm từ mã đúng đã được phát đi. Để giải bài này chúng ta tính: Trong đó hi (i = 1,2,3,…) là cột thứ i của H Chúng ta thấy s(v) ≡ h1 nên suy ra lỗi sai ở vị trí số 1, vì vậy từ mã đúng đã được phát đi là w = v + e = 1010110 + 1000000 = 0010110 Từ ý tưởng này gợi ý cho chúng ta một loại mã cho phép phát hiện sai 1 bit nhanh nhất. Mã này có tên gọi là mã tuyến tính Hamming. Xét ví dụ về sửa lỗi theo mã tuyến tính Hamming 68 Xác định ma trận kiểm tra của mã Hamming với ma trận sinh G: Giả sử có ma trận sinh G như sau: Với: Ma trận kiểm tra của mã Hamming (7x4) là: 69 Quá trình kiểm tra như sau: Nếu d = 0 không lỗi Nếu d ≠ 0 có lỗi, và bit ri bị lỗi trong quá trình truyền Ví dụ r = 1100011 Suy ra không lỗi Với r = 1010011 70 Suy ra có lỗi bit thư 7 bị truyền lỗi Sửa lỗi 1010011 => 1010010 3.3.2 Kỹ thuật ghép xen Interleaving Kỹ thuật ghép xen dữ liệu để nhận được sự phân tập không gian mà không thêm bất kỳ thông tin overhead nào. Kỹ thuật này dùng để giải quyết vấn đề lỗi cụm (bursty errors), các bit được phân tán nên không bị lỗi đồng thời khi xảy ra fading sâu hay cụm nhiễu (bursty noise)[12] Nếu khối sửa lỗi hướng trước FEC chỉ sửa được lỗi từ 1 đến 3 bit thì kỹ thuật ghép xen lại sửa được lỗi với các chuỗi dài. Có hai kỹ thuật ghép xen dữ liệu: - Khối xen dữ liệu Interleaver - Khối xen chập Convolution Interleaver Để minh hoạ kỹ thuật này ta xét đoạn dữ liệu được truyền đi không áp dụng kỹ thuật ghép xen và có kỹ thuật ghép xen. Hình 3.4 Không có ghép xen dữ liệu 71 Hình trên là đoạn dữ liệu không ghép xen, khi xảy ra lỗi dữ liệu bị phá huỷ hoàn toàn. Hình 3.5 Hiệu quả của việc ghép xen dữ liệu Hình trên mô tả có sử dụng xen dữ liệu, các block tín hiệu được tản đều, khi bị nhiễu phá huỷ, thì các block tín hiệu không bị phá huỷ hoàn toàn. 3.3.2.1 Khối xen dữ liệu Xét một khối interleaver với số cột D = 3, số hàng N = 7 72 Hình 3.6 Đặc trưng khối xen từ bộ FEC tới kênh với D=3, N=7 Các số trong khối biểu trưng sự xắp xếp các bit vào bộ xen. Các bit được viết theo hàng và đọc ra theo cột. Một hàng đơn chứa hoàn toàn một từ mã FEC, từ mã trong ví dụ trên là 7. Hình 3.7 Đặc trưng bộ giải xen từ kênh tới FEC với D=3, N=7 Các bit ở đây đến từ kênh, được viết vào trong bộ giải xen theo cột và đọc ra theo hàng. Hàng sắp xếp hợp thức các bit như định trước cho khối FEC. 73 Hình 3.8. Mô tả kết quả các giá trị xen dữ liệu Hai hàng đầu tiên của bảng trình bày sự sắp xếp các bit này sẽ được gởi lên kênh mà không cần thực hiện xen ở bộ xen. Nếu có lỗi xảy ra trong kênh thì được chỉ ra ở hàng thứ 3 của bảng, hai hàng cuối của bảng chỉ các bit sẽ được gửi tới khối FEC trong bộ thu trên cùng kênh. Khi dùng kỹ thuật xen, các bit bị phá huỷ, thì FEC sẽ tự sửa lỗi. 3.3.2.2 Kỹ thuật xen chập Convolution Interleaving Xét bộ xen chập với một từ mã có size N=7 và độ sâu D=3. Hình 3.9 Bộ xen chập N=7, D=3 74 Các từ mã được viết vào trong bộ xen theo hàng và đọc ra theo côt. Sự khác nhau giữa cách thực hiện này và cách thực hiện của bộ khối xen là từ mã không luôn bắt đầu cùng cột trong xen chập như nó đã làm trong khối bộ xen. Hơn nữa, các hàng không có kết thúc. Độ sâu và độ dài của bộ xen quyết định có hoặc không từ mã tiếp theo sẽ được viết ở hàng kế tiếp hay hàng đầu tiếp theo sau từ mã đã được viết trước đó. Hình 3.10 Mô tả bộ giải xen chập trong bộ thu khi bộ phát dùng xen chập Các giá trị đọc ra của bộ giải xen không rõ ràng như trong khối giải xen. Các bit ở đây được viết theo cột và đọc ra theo hàng với sự xử lý lỗi của FEC. Bộ giải xen chỉ đọc một từ mã đơn từ mỗi hàng và rồi xử lý tới hàng kế tiếp cho đến hàng cuối cùng được đọc. Sau khi đọc số hàng cuối cùng, bộ giải xen quay trở lại hàng đầu và đọc tiếp từ mã ở vị trí kế tiếp chưa đọc. 3.3.3 Mã sửa lỗi kép - Double error correction codes 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. 75 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. Ví dụ: Với ma trận sinh G được cho như sau : 8 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 [ : ] 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 G I P                           8 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 [P :I ] = 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 TH                          Khi đó nếu cho bản tin u = [0100 0010] thì từ mã v sẽ là: v = uG = [0100 0010 1001 1100] giả sử rằng bít thứ 2 và thứ 3 bị đảo do noise trong kênh không dây. Do đó, thông tin nhận được sẽ là v’ = [0010 0010 1001 1100]. Bằng việc nhận v’ với ma trận chuyển vị của ma trận chẵn lẻ H, chúng ta sẽ tính được s: s = v’HT = [1010 1111] Hãy chú ý rằng syndrome đạt được bằng việc cộng tuyệt đối hàng thứ 2 và thứ 3 của ma trận HT . Do đó ở thiết bị đầu cuối bộ thu thì các bít thứ 2 và thứ 3 đã bị đảo, để sửa lỗi, từ nhận định trên ta sẽ có từ mã đúng là v = [0100 0010 1001 1100]. Bởi vì ma trận sinh G là một mã hệ thống, nên chúng ta sẽ có 8 bit đầu tiên là dạng của dữ liệu nhận đúng là u =[0100 0010] 76 3.4 Hiệu quả trong việc sử dụng năng lượng Forward Error Correction (sửa lỗi hướng trước) là 1 cách của việc sửa lỗi các gói tin bằng cách thêm các bit thông tin vào quá trình truyền dẫn. Tiến hành thí nghiệm và kiểm tra sự khác nhau giữa các mã sửa lỗi trong radio ChipCon. Do sự hạn chế của việc tiêu thụ điện năng thấp và yếu tố về hình thức là nhỏ, nên các mã sửa lỗi được thiết kế đơn giản và có thể sửa lỗi đơn bít hoặc lỗi kép. Các thí nghiệm ECC của có hiệu quả khi tỷ lệ bít lỗi không cao và là các lỗi đơn bit. Khi các lỗi là chùm thì các mã của chúng tôi không hiệu quả trong việc giảm đi những mất mát trong gói tin. Tuy nhiên cũng như nhiều lược đồ khác thì nó khá là phức tạp và yêu cầu năng lượng xử lý cao và bộ nhớ lưu trữ tính toán lớn. Để xác định các đặc tính lỗi của radio ChipCon, chúng ta thực hiện vài phép đo sơ bộ. 1 nút gửi 1000 lần 1 gói tin không được mã hoá, với các gói thu được nhập vào trong PC ở thiết bị đầu cuối là bộ thu. Các thí nghiệm đã được tiến hành bên ngoài trời. Hình dưới mô tả hầu hết các lỗi bit là đơn hoặc là lỗi kép. Các chùm lỗi cũng có nhưng hiếm gặp. Do đó, cũng có thể coi rằng lược đồ mã hoá mà sửa lỗi đơn và lỗi kép có thể giảm thiểu các lỗi.[12] Hình 3.11 Bit lỗi đơn và lỗi kép 77 Phần tiếp theo là các tính toán để xác định tỷ lệ mất các gói tin, sự mất là rất nhỏ khoảng 0.4 % trong khoảng cách là 135 feet. Hình 3.12 Tính toán tỷ lệ mất gói tin 3.4.1 Kiểm tra ngoài trời Khi không sử dụng FEC thì ta thấy với 5000 gói tin ở khoảng cách 600 ft thì tỷ lệ mất gói tin ở môi trường ngoài trời là 0,26%[12] 78 3.4.2 Kiểm tra trong nhà Khi thực hiện truyền dữ liệu ở 3 vị trí khác nhau trong nhà không sử dụng FEC thì tỷ lệ mất gói tin cũng khá lớn.[12] Hình 3.13 Các vị trí các node ở trong nhà 79 Chương 4. ĐIỀU KHIỂN LỖI ỨNG DỤNG CHIPCON CC1010 4.1 Giới thiệu Trong khi 1 mã sửa lỗi ECC có thể được chỉ định trong bất kỳ lớp nào trong network stack, thì thực tế ECC được sử dụng trong lớp MAC [4] như hình minh hoạ : Hình 4.1 Interfacing ECC module with network stack Bởi vì với vị trí này sẽ không làm thay đổi sự chuyển giao với lớp ứng dụng. Do đó, bất kỳ ứng dụng nào được viết mà không dùng ECC trong MAC cũng có thể thực hiện mà không cần điểu chỉnh mã nguồn. Quá trình thực hiện mã sửa lỗi ECC tương tác với network stack qua giao diện RadioEncoding – Giao diện là 1 file được sử dụng ngôn ngữ TinyOS-nesC chỉ rõ toàn bộ các phương pháp và những bộ điều khiển sự việc cái mà 1 module sử dụng từ các module khác hay 1 module hiện hữu : interface RadioEncoding { command result_t encode_flush(); command result_t encode(char data); command result_t decode(char data); event result_t decodeDone(char data, char error); event result_t encodeDone(char data); 80 } Mã hoá được thực hiện ở lớp MAC (ChannelMonC module) cho mỗi byte dữ liệu trong gói tin. Dữ liệu vào được thông qua như một thông số được lưu trữ trong cấu trúc dữ liệu của mô-đun ECC. Sau khi một số lượng đủ của các byte dữ liệu vào – input được nhận, các byte dữ liệu đầu vào được mã hoá bởi hàm radio_encode_thread (mạch mã hoá radio) và từ mã được chuyển tới ChannelMonC qua hàm encodeDone. Tương tự như trên, ChannelMonC đưa ra quá trình giải mã cho từng byte của các gói tin nhận được. Sau khi đủ số lượng các byte dữ liệu vào được nhận, các byte dữ liệu được nhận sẽ được giải mã nhờ hàm radio_decode_thread ( mạch giả mã radio ) và các byte dữ liệu gốc được gửi tới ChannelMonC qua DecodeDone. Quá trình thực thi của radio_encode_thread và radio_decode_thread phụ thuộc vào loại mã sửa lỗi. radio_encode_thread tính toán các bit chẵn lẻ nhờ vào việc so sánh từng bit trong các byte dữ liệu đầu vào. Quá trình này tương đương với uG. Trong đó u là thông tin cần truyền và G là ma trận sinh. Trong quá trình radio_decode_thread , syndrome – s được tính nhờ vào các bit dữ liệu nhận được. Việc này cũng tương đương với thực hiện vHT , với v là dữ liệu nhận được và HT là ma trận chuyển vị của ma trận H. Nếu syndrome – s khác không (s # 0) có nghĩa là tồn tại lỗi và vị trí của các bit lỗi có thể được tìm thấy bằng việc so sánh syndrome – s với các vec-tơ cột trong ma trận H . Và quá trình tìm kiếm này có thể được thực hiện một cách nhanh chóng với việc sử dụng các biểu đồ tương ứng giữa các giá trị syndrome – s với các vị trí bit lỗi tương ứng. 4.2 Tìm hiểu chương trình truyền nhận dữ liệu trong CC1010 Thuật toán để xác định và sửa lỗi cho dữ liệu là CRC – 16 . Ta sẽ xem xét từng quá trình truyền và nhận giữa hai nút mạng. 4.2.1 Quá trình truyền dữ liệu giữa 2 nút mạng [14]: - Sử dụng hàm halRFSendPacket (…) để điều khiển việc gửi gói tin sử dụng trong cấu hình RF hiện thời: void halRFSendPacket(byte numPreambles, byte* packetData, byte length) { byte crcData, i; word crcReg; 81 // Set the first byte to transmit & turn on TX RFCON|=0x01; // Ensure that bytemode is selected RF_SEND_BYTE(RF_PREAMBLE_BYTE); RF_START_TX(); // Send remaining preambles while (--numPreambles) RF_WAIT_AND_SEND_BYTE(RF_PREAMBLE_BYTE); // Send sync byte + length byte RF_WAIT_AND_SEND_BYTE(RF_SUITABLE_SYNC_BYTE); RF_WAIT_AND_SEND_BYTE(length); - Nếu xuất hiện lệnh yêu cầu truyền ( tức là hàm halRFSendPacket được gọi ) cùng với cặp RX/TX phù hợp với chế độ RF_TX thì quá trình truyền sẽ được thực hiện : đầu tiên một byte đồng bộ sẽ được truyền đi để đảm bảo sự đồng bộ giữa bên truyền và bên nhận, sau đó là byte Preamble ( byte này có vai trò báo hiệu phần bắt đầu của gói tin ) và tiếp sau là dữ liệu cần truyền. Phần kiểm lỗi CRC sẽ được đặt ở vị trí cuối cùng trong gói tin để thuận tiện cho việc kiểm tra sau này. word culFastCRC16(byte crcData, word crcReg) { return (crcReg > 8)) ^ crcData]; } // culFastCRC16 word culFastCRC16Block(byte *crcData, word length, word crcReg) { word i; for (i = 0; i < length; i++) { crcReg = (crcReg > 8)) ^ crcData[i]]; } return crcReg; } // culFastCRC16Block 82 crcReg=CRC16_INIT; // Update CRC RF_WAIT_AND_SEND_BYTE(crcData); for (i=0; i<8; i++) { if ( ((crcReg&0x8000)>>8) ^ (crcData&0x80) ) crcReg=(crcReg<<1)^CRC16_POLY; else crcReg=(crcReg<<1); crcData<<=1; } } // Send CRC-16 RF_WAIT_AND_SEND_BYTE((crcReg>>8)&0xFF); RF_WAIT_AND_SEND_BYTE(crcReg&0xFF); Trong đó từ mã chứa trong hàm crcLUT[256] không được đưa ra ở đây, các dạng của từ mã đã được định trước trong CPU. Trường hợp này gồm có 256 từ mã. Hàm sửa lỗi là hàm culFastCRC16(crcDaTa, CRC REg) . Trong đó + crcData : là chuỗi dữ liệu gốc cần để thực hiện CRC-16 một cách hiệu quả. + crcReg : giá trị hiện thời của thanh ghi CRC. Quá trình thực hiện sửa lỗi dùng CRC 16 được xem là quá trình thực hiện nhanh chóng , hàm được gọi cho từng byte trong chuỗi dữ liệu.Với mỗi byte được gọi thì CRC được thêm vào phần cuối cuả byte dữ liệu đó, vị trí đặt như vậy sẽ giúp thuận tiện cho việc kiểm tra CRC sau này. Quá trình thêm vào CRC sau mỗi byte dữ liệu tương đương với việc uG với u là dữ liệu gốc, G là ma trận sinh. Vì ở đây là kiểm lỗi CRC-16 nên số bit được thêm vào là 8, đồng nghĩa với việc thanh ghi crcReg sẽ bị dịch trái đi 8 bit 83 sau khi thêm CRC, và trạng thái của nó sau đó cũng trở lại trạng thái lúc cuối cùng được cấp. return crcReg : là giá trị cập nhật của thanh ghi CRC16, giá trị này tương ứng với giá trị syndrome - s. Quá trình kiểm lỗi kết thúc, giá trị này sẽ quay về 0 nếu dữ liệu không bị thay đổi gì. Vì rằng để đảm bảo hiệu năng, hàm culFastCRC16 ở trên được thực hiện trong các khối dữ liệu thay vì cho những byte đơn lẻ, do đó hàm culFastCRC16Block(byte *crcData, word length, word crcReg) được sử dụng để đảm bảo cho quá trình kiểm lỗi của khối dữ liệu này. 4.2.2 Quá trình nhận dữ liệu giữa 2 nút mạng [14]: - Sử dụng hàm halRFReceivePacket (…) để điều khiển quá trình nhận các gói tin được gửi tới từ hà halSendPacket trong một bộ CC1010 khác. void halRFReceivePacket(...) byte halRFReceivePacket(byte timeOut, byte* packetData, byte maxLength, char* rssiByte, word clkFreq) { byte receivedBytes, pkgLen, crcData, i; word crcReg; halConfigTimer23(TIMER3|TIMER23_NO_INT_TIMER, 10000, clkFreq); INT_SETFLAG(INUM_TIMER3, INT_CLR); TIMER3_RUN(TRUE); RF_SET_PREAMBLE_COUNT(16); RF_SET_SYNC_BYTE(RF_SUITABLE_SYNC_BYTE); MODEM1=(MODEM1&0x03)|0x24; // Make sure avg filter is free- running + 22 baud settling time INT_ENABLE(INUM_RF, INT_OFF); INT_SETFLAG(INUM_RF, INT_CLR); RF_START_RX(); 84 while (1) { // Check if 10 ms have passed if (INT_GETFLAG(INUM_TIMER3)) { // Clear interrupt flag and decrement timeout value INT_SETFLAG(INUM_TIMER3, INT_CLR); if (timeOut && !--timeOut) { timeOut=255; break; // Timeout } } // Check if sync byte received if (INT_GETFLAG(INUM_RF)) { EXIF &= ~0x10; // Clear the flag break; } } receivedBytes=0; // Timeout or sync byte received? if (timeOut!=255) { // Lock average filter and perform RSSI reading if desired RF_LOCK_AVERAGE_FILTER(TRUE); // Get length of package RF_WAIT_AND_RECEIVE_BYTE( pkgLen ); pkgLen+=2; // Add the two CRC bytes if (rssiByte) *rssiByte=halRFReadRSSI(); 85 Tính toán và kiểm tra FEC // Calculate CRC-16 (CCITT) for (i=0; i<8; i++) { if ( ((crcReg&0x8000)>>8) ^ (crcData&0x80) ) crcReg=(crcReg<<1)^CRC16_POLY; else crcReg=(crcReg<<1); crcData<<=1; } } // Check if CRC is OK if (crcReg != CRC_OK) receivedBytes=0; } - Giả sử rằng RX đã được kích hoạt : khi đó bên nhận sẽ chờ nhận byte đồng bộ. Nếu quá thời hạn cho phép mà không nhận được byte đồng bộ nào thì hàm sẽ trở về 0, tức là sẽ tắt chế độ sẵn sàng nhận cho đến khi nhận được lệnh nhận tiếp sau. Nếu một byte đồng bộ được nhận trong khoảng thời gian chờ cho phép, thì các byte dữ liệu sau đó sẽ được nhận và được chuyển vào trong bộ đệm . Thứ tự các byte được chỉ ra trong trường độ dài gói tin. Tuy nhiên CRC chỉ ứng dụng được trong trường hợp số bít lỗi là nhỏ. Chính vì vậy vẫn cần tồn tại thuật toán truyền dữ liệu trong mạng cảm nhận không dây dựa vào gói trả lời ACK. Quá trình đảm bảo độ tin cậy của truyền dữ liệu trong mạng cảm nhận không dây dựa vào gói trả lời ACK có thuật toán phức tạp hơn quá trình CRC. Hơn nữa ta thấy nếu trong quá trình truyền mà không nhận được ACK thì gói tin sẽ được yêu cầu truyền lại trong giới hạn n lần. Điều này sẽ gây nên thời gian trễ lớn và tốn dung lượng bộ nhớ, cộng với thuật toán phức tạp làm tiêu hao nhiều năng lượng hơn, đây là một điều rất đáng quan tâm với các nút mạng cảm biến. 86 Nguyên lý truyền dẫn giữa 2 nút mạng được mô tả như sau: + Quá trình truyền : Nếu bộ thu phát ở trạng thái rỗi (sẵn sàng truyền) thì thành phần phát sẽ được kích hoạt. Qúa trình truyền được thực hiện trên RF ISR, và nút truyền chờ nhận lại ack (nếu được yêu cầu). Nếu tại bộ phát (nút truyền) được cấp yêu cầu truyền lại với ( sppSetting.TXAttempts = n ) thì gói tin sẽ được truyền lại (n-1) lần cho đến khi nhận được gói tin phản hồi ACK. Quá trình truyền được diễn ra liên tục ngay cả khi UART vẫn đang trong quá trình nhận, trong suốt quá trình truyền nó được đặt vào chế độ TX_Mode (chế độ đang truyền) hoặc chờ nhận ACK (TXACK_MODE). Kết thúc hoạt động truyền trạng thái của đường truyền sppStatus ( ) sẽ trở lại trạng thái rỗi (spp_IDLE_MODE). + Quá trình nhận: Nếu bộ thu phát rỗi (ở trạng thái sẵn sàng truyền và nhận spp_IDLE_MODE); khi đó nếu nhận được yêu cầu nhận, thì thành phần nhận trong nút mạng sẽ được kích hoạt. Quá trình nhận được thực hiện nhờ RF ISR ( Radio-Frequency Interrrupt-Service-Routine ) và thực hiện truyền ACK ( nếu được yêu cầu). Kết thúc mỗi lần nhận. Bộ nhận sẽ được tắt nguồn. Nhưng chức năng nhận sẽ được kích hoạt trở lại ngay khi ứng dụng được yêu cầu tiếp theo đó. Trong suốt quá trình nhận bộ nhận luôn ở trạng thái chờ nhận gói tin (RX_MODE) hoặc đang truyền ACK (RXACK_MODE). Kết thúc hoạt động truyền, trạng thái của đường truyền sppStatus ( ) sẽ trở lại trại thái rỗi ban đầu (spp_IDLE_MODE) . Giữa hai nút mạng cảm biến thì quá trình truyền và nhận luôn được chuyển đổi qua lại. Do đường truyền là bán song công nên trong cùng một thời điểm chỉ có một bên được phép truyền, kết thúc quá trình truyền nhận thường bộ thu phát sẽ thiết lập lại các giá trị. Dưới là một minh hoạ về cấu trúc chương trình truyền nhận trên RF được thực hiện trong vòng lặp while [13] : while (TRUE) { 87 // Receive a packet – Nếu nhận tin if (sppReceive(&RXI) == SPP_RX_STARTED) { do { if (txRequest && (TXI.status == SPP_TX_FINISHED) && (RXI.status == SPP_RX_WAITING)) { sppReset(); } } while (SPP_STATUS() != SPP_IDLE_MODE if (RXI.status == SPP_RX_FINISHED) { if (SPP_SEQUENCE_BIT & (lastRXflags ^ RXI.flags)) { while (uartRXPos != rxDataLen[uartRXBuffer]); if ((rxDataLen[rfRXBuffer] = RXI.dataLen) != 0) dau // Switch buffers and initiate UART0 transmission GLED = ~GLED; SWITCH(uartRXBuffer, rfRXBuffer); RXI.pDataBuffer = pRXBuffer[rfRXBuffer]; uartRXPos = 0; UART0_SEND(pRXBuffer[uartRXBuffer][uartRXPos]); } } lastRXflags = RXI.flags; } } // Transmit packet, if requested - truyền tin nếu nhận được yêu cầu if (txRequest) { if (sppSend(&TXI) == SPP_TX_STARTED) { // Wait for the transmission to finish 88 YLED = LED_ON; // đèn vàng bật  đang truyền } while (SPP_STATUS() != SPP_IDLE_MODE Nếu đường truyền rỗi thi ta thực hiện truyền YLED = LED_OFF; // Check out the results if (TXI.status == SPP_TX_FINISHED) { sppSettings.rxTimeout = NORMAL_TIMEOUT; RLED = LED_OFF; txRequest = TX_REQUEST_OFF; } else { RLED = LED_ON; sppSettings.rxTimeout = RETRY_TX_TIMEOUT; } } } // Recalibrate the transceiver if requested to --- xác lập lại tại bộ thu phát nếu có lệnh yêu cầu if (recalibRequest) { sppSetupRF(&RF_SETTINGS, &RF_CALDATA, TRUE); } } } // main Qua việc nghiên cứu chương trình tuyến nhận dữ liệu của CC1010, ta thấy chương trình này không sử dụng FEC. Hướng đến việc cải thiện hiệu quả sử dụng năng lượng cho node mạng, luận văn đề xuất cải tiến tuyến truyền nhận nói trên bằng cách sử dụng FEC. Sau đây là một số gợi ý cho việc cải tiến này. 4.3 Đề xuất sử dụng FEC cho tuyến truyền nhận dữ liệu giữa các node mạng CC1010 89 4.3.1 Giả định bài toán và cách tính các từ mã Giả sử đoạn dữ liệu đơn giản 1101 + Xác định ma trận sinh G: Thông tin cần mã hoá thì từ mã tương ứng sẽ là: Ma trận sinh G sẽ được chọn sao cho đảm bảo nguyên tắc các hàng của G phải độc lập tuyến tính. Gọi v = (a1,a2,a3,a4,a5,a6,a7) là một từ mã, ta có: Suy ra: Hay: Công thức này cho phép chúng ta mã hoá được thông báo u thành từ mã v. Chẳng hạn nếu: 90 Biến đổi công thức trên thành dạng v = uxG, ta đưa được về dạng: Ta suy ra được ma trận sinh G: + Xác định ma trận Hamming H: Trong dạng mã hoá khối tuyến tính G có thể được chuyển thành dạng như sau: G = [Ik:C] khi đó ma trận kiểm lỗi H = [CT:Ir] Hoặc G = [C:Ik] khi đó ma trận kiểm lỗi H = [Ir:CT] Do đó ta suy ra ma trận H: 91 + Xác định từ mã: Với dữ liệu cần gửi là u = 1101 Tại nơi thu dữ liệu u sẽ được mã hoá thành từ mã v: Giả sử rằng truyền lỗi làm nơi nhận nhận sai bit thứ 5; nghĩa là từ mã v nhận được tại nơi thu sẽ có dạng w = [0111101] Syndrome (s) sẽ được xác định tại bên nhận theo công thức: Suy ra s = [011] trùng với hàng thứ 5 trong ma trận HT, vậy ta có thể kết luận dữ liệu thu được bị lỗi tại vị trí thứ 5. Khi đó dữ liệu đúng nhận được là v=[01111001] và giải mã ra ta được từ mã đúng cần nhận là u = [1101] 4.3.2 Chương trình truyền dữ liệu sử dụng các từ mã 92 Trên cơ sở chương trình truyền dữ liệu đã nói ở mục 4.3.1 có thể chèn từ mã vào mã nguồn ở các vị trí sau: Tuy nhiên với việc đưa các từ mã sửa lỗi vào dữ liệu ở phía truyền cũng cần thuật toán để giải mã và sửa lỗi ở phía nhận, sau đó tiến hành thử nghiệm để đánh giá hiệu quả của phương pháp này so với phương pháp cũ, nhưng vì thời gian có hạn, luận văn dừng ở đây, với mong muốn công việc này được tiến hành tiếp sau này bởi chính tác giả hoặc một người nào đó. 4.4 Kết luận chương 4 Nghiên cứu chương trình truyền và nhận dữ liệu của mạng WSN trên cơ sở CC1010 đã có. Đã đề xuất ứng dụng phương pháp FEC cho việc truyền dữ liệu của CC1010. Đã giả thiết bài toán và tìm được các từ mã tương ứng. Trên cơ sở nhữn kết quả này có thể vận dụng vào các chương trình tuyến nhận dữ liệu nói trên, để thu được hiệu quả sử dụng năng lượng tốt hơn. 93 KẾT LUẬN Đề tài “Nghiên cứu mã điều khiển lỗi trong mạng cảm biến không dây để nâng cao hiệu quả việc sử dụng năng lượng” đã đạt được những kết quả sau: - Đã tổng quan về mạng WSN - Đã nghiên cứu phân tích về các kỹ thuật phát hiện lỗi và các kỹ thuật sửa lỗi. Trong đó đặc biệt nhấn mạnh kỹ thuật sửa lỗi hướng thuận FEC, đây là kỹ thuật sửa lỗi phù hợp với mạng WSN, hứa hẹn đưa lại hiệu quả sử dụng tốt năng lượng của node mạng, kéo dài tuổi thọ toàn mạng. - Đã tìm hiểu cụ thể các chương trình truyền nhận dữ liệu của mạng WSN trên cơ sở CC1010 có ở phòng thí nghiệm và phát hiện phương pháp sửa lỗi ở đây là truyền lại dữ liệu. Do vậy luận văn đề xuất và tính toán các từ mã để có thể ứng dụng phương pháp sửa lỗi hướng thuận FEC cho mạng WSN. Tuy nhiên công việc này đòi hỏi phải bổ sung vào chương trình nguồn đã có các đoạn chương trình mới cho bên phát và bên nhận. Do thời gian có hạn nên công việc này không kịp thực hiện. Tác giả đề xuất hướng nghiên cứu tiếp là bổ sung các từ mã của phương pháp FEC vào bên phát và bên gửi, sau đó tiến hành thực nghiệm đo hiệu quả truyền nhận dữ liệu và đo năng lượng tiêu hao của node mạng để đánh giá tính ưu việt của phương pháp FEC.