Tài liệu Kỹ thuật lấy mẫu nén và áp dụng vào kỹ thuật mã mạng

  ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ             NGUYỄN THỊ ANH ĐÀO           KỸ THUẬT LẤY MẪU NÉN VÀ ÁP DỤNG VÀO KỸ THUẬT MÃ MẠNG                 LUẬN VĂN THẠC SĨ CÔNG NGHỆ ĐIỆN TỬ - VIỄN THÔNG                    HÀ NỘI – 2012   ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ             NGUYỄN THỊ ANH ĐÀO           KỸ THUẬT LẤY MẪU NÉN VÀ ÁP DỤNG VÀO KỸ THUẬT MÃ MẠNG     Ngành: Công nghệ Điện tử - Viễn thông Chuyên ngành: Kỹ thuật Điện tử Mã số: 60 52 70             LUẬN VĂN THẠC SĨ CÔNG NGHỆ ĐIỆN TỬ - VIỄN THÔNG  NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN LINH TRUNG                                                          Nguyễn     HÀ NỘI – 2012   Linh Trung iii    MỤC LỤC   LỜI CAM ĐOAN ...........................................................................................................i LỜI CẢM ƠN ............................................................................................................... ii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................ vi DANH MỤC CÁC HÌNH VẼ .................................................................................... vii TÓM TẮT .................................................................................................................... ix CHƯƠNG 1: GIỚI THIỆU ..........................................................................................1 1.1. Kỹ thuật mã mạng...............................................................................................1 1.2. Kỹ thuật lấy mẫu nén..........................................................................................1 1.3. Mục tiêu nghiên cứu............................................................................................2 1.4. Cấu trúc của luận văn .........................................................................................3 CHƯƠNG 2: MÃ MẠNG .............................................................................................4 2.1. Giới thiệu..............................................................................................................4 2.2. Mã mạng là gì? ....................................................................................................5 2.3. Các lợi ích của mã mạng.....................................................................................5 2.3.1 Tăng thông lượng............................................................................................6 2.3.2 Tiết kiệm tài nguyên mạng không dây ............................................................8 2.3.3 Tăng cường tính bảo mật ...............................................................................10 2.3.4 Tính bền (Robustness) ....................................................................................10 2.4. Mã mạng gặp phải những thách thức gì? .......................................................11 2.4.1 Phức tạp .........................................................................................................11 2.4.2 Bảo mật ..........................................................................................................11 2.4.3 Tích hợp với cơ sở hạ tầng hiện có ................................................................12 iv    2.5 Kết quả lý thuyết chính của kỹ thuật mã mạng cho mạng phát đa điểm .....12 2.5.1 Định lý Luồng cực đại lát cắt cực tiểu (Min – Cut Max – Flow) ..................12 2.5.2 Định lý chính của mã mạng ...........................................................................13 2.6 Kỹ thuật mã mạng tuyến tính ...........................................................................14 2.7 Kỹ thuật mã mạng tuyến tính ngẫu nhiên .......................................................16 CHƯƠNG 3: KẾT HỢP MÃ MẠNG VÀ LẤY MẪU NÉN ĐỂ ĐẠT TRUYỀN THÔNG HIỆU QUẢ TRONG MẠNG CẢM BIẾN KHÔNG DÂY ......................17 3.1 Lấy mẫu nén .......................................................................................................18 3.1.1 Tín hiệu thưa ..................................................................................................19 3.1.2 Bài toán lấy mẫu nén .....................................................................................20 3.1.3 Thiết kế ma trận đo ........................................................................................20 3.1.4 Thiết kế thuật toán khôi phục tín hiệu ...........................................................22 3.2 Mối liên hệ giữa mã mạng tuyến tính ngẫu nhiên và lấy mẫu nén ................23 3.3 Thiết kế NetCompress........................................................................................24 3.3.1 Định dạng gói tin ...........................................................................................24 3.3.2 Quá trình mã hóa ...........................................................................................26 3.3.3 Quá trình giải mã ...........................................................................................30 3.4 Kết luận ..............................................................................................................30 CHƯƠNG 4: PHẦN MỀM MÔ PHỎNG NECO .....................................................31 4.1 Giới thiệu chung .................................................................................................31 4.2 Các tính năng và cách dùng ..............................................................................31 4.2.1 Tính năng người dùng, giao diện và đầu ra ...................................................32 4.2.2 Phát triển các mô đun mở rộng ......................................................................33 4.2.3 Các số liệu thống kê .......................................................................................34 4.3 Cấu trúc của phần mềm mô phỏng ..................................................................34 v    4.3.1 Đồ thị .............................................................................................................34 4.3.2 Tóm tắt mạng và giao thức ............................................................................34 4.4 Hướng phát triển ................................................................................................35 4.4.1 Ngôn ngữ .......................................................................................................35 4.4.2 Thư viện .........................................................................................................35 4.4.3 Giấy phép và khả năng mở rộng ....................................................................36 4.5 Thực hiện mô phỏng ..........................................................................................37 4.5.1 Core................................................................................................................37 4.5.2 Giao diện người dùng ....................................................................................39 4.6 Cách thức mở rộng.............................................................................................40 4.6.1 Tập tin XML để tải các mô đun mở rộng ......................................................40 4.6.2 Thiết lập giao thức mạng mới ........................................................................41 4.6.3 Thiết lập các giao thức định tuyến mới .........................................................42 4.6.4 Thiết lập các kiểu liên kết mới.......................................................................42 4.6.5 Thiết lập các kiểu gói tin mới ........................................................................43 4.7. Kết luận ..............................................................................................................44 CHƯƠNG 5: KẾT LUẬN ...........................................................................................46 TÀI LIỆU THAM KHẢO ...........................................................................................48   vi    DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Tiếng Anh Chữ viết tắt Tiếng việt NC Network Coding Mã mạng CS Compressed Sensing Lấy mẫu nén ADC Analog to digital converter Bộ chuyển đổi tương tự - số RLNC Random Linear Network Mã mạng tuyến tính ngẫu nhiên Coding DSP Digital signal processing Xử lý tín hiệu số TS Time Slot Khe thời gian GUI Graphical User Interface Giao diện người dùng RIP Restricted isometry property Thuộc tính cùng kích thước được thu hẹp WSN Wireless Sensor Network Mạng cảm biến không dây vii    DANH MỤC CÁC HÌNH VẼ Hình 2.1: Kết nối mã mạng với những lĩnh vực khác [5]. ..............................................5 Hình 2.2: Mạng cánh bướm [30]. ....................................................................................6 Hình 2.3: Mạng cánh bướm với 2 nguồn và 2 đích [30]. ................................................7 Hình 2.4: Mạng cánh bướm không dây [30]. ..................................................................8 Hình 2.5: Mạng cánh bướm không dây sửa đổi [30].......................................................8 Hình 2.6: Nút A và C chuyển tiếp thông tin thông qua relay B. (a) Không sử dụng mã mạng, (b) sử dụng mã mạng. Phương pháp mã mạng sử dụng một đường phát đa điểm [5].....................................................................................................................................9 Hình 2.7: Trộn thông tin để tạo ra cách bảo vệ tự nhiên chống lại nghe trộm [5]. .......10 Hình 2.8: Một kết nối phát đơn đường có khả năng thông qua của các cạnh bằng 1 [5]. .......................................................................................................................................12 Hình 2.9: Ví dụ về mã mạng tuyến tính ngẫu nhiên phân bố [20]. ...............................14 Hình 3.1: Cấu trúc của mạng cảm biến không dây. ......................................................17 Hình 3.2: (a) Quá trình đo lấy mẫu nén với ma trận đo ngẫu nhiên Gaussian  và ma trận truyền cosin rời rạc (DCT)  . Véc tơ hệ số rời rạc s với K=4; (b) Quá trình đo với    . Có 4 cột tương ứng với các hệ số si khác 0; véc tơ đo y là sự kết hợp tuyến tính của các cột này [6]. .................................................................................................21 3 Hình 3.3 : (a) Không gian con chứa 2 véc tơ rải rác trong R nằm gần với trục tọa độ; (b) Trực quan hóa tối thiểu l2 (5) tìm điểm tiếp xúc không rải rác ŝ giữa bóng l2 và ma trận đo chuyển đổi trong không gian rỗng; (c) Trực quan hóa tối thiểu l1 tìm điểm tiếp xúc rải rác ŝ với xác suất cao [6]. .................................................................................23 Hình 3.4: Định dạng gói tin [8]. ....................................................................................25 Hình 3.5: Ví dụ hợp nhất 2 gói [8]. ...............................................................................27 Hình 3.6: (a) Định dạng gói nút cảm biến 3; (b) Định dạng gói nút cảm biến 4. .........29 viii    Hình 3.7: Sát nhập hai gói tin ........................................................................................30 Hình 4.1: Giao diện người dùng đồ họa của NECO [28] ..............................................33 Hình 4.2: Cấu trúc XML để tải và lưu các tham số mô phỏng trong NECO [32]. .......33 Hình 4.3: Các lớp đơn giản để kiểm tra giao thức mã mạng [32]. ................................35 Hình 4.4: Các mô đun chính của NECO [28]................................................................36 Hình 4.5: Bộ lập lịch [31] ..............................................................................................38 Hình 4.6: Các dòng chảy của bản tin trong mẫu mới của NECO [31]. .........................39 Hình 4.7: Cú pháp XML để tải và lưu các thông số mô phỏng với NECO [32]. ..........40 Hình 4.8: Thiết lập một giao thức mạng mới [32].........................................................42 Hình 4.9: Thiết lập một giao thức định tuyến mới [32]. ...............................................42 Hình 4.10: Thiết lập một kiểu liên kết mới [32]............................................................43 Hình 4.11: Thiết lập một kiểu gói tin mới [32]. ............................................................43 Hình 4.12: Thiết lập một kiểu đồ thị mới [32]. .............................................................44   ix    TÓM TẮT Các mạng truyền thông được thiết kế để chuyển thông tin từ một hay nhiều nút mạng nguồn đến một hay nhiều nút mạng đích. Trong một mạng viễn thông, vấn đề ta quan tâm là làm thế nào để truyền thông tin hiệu quả. Kỹ thuật mã mạng là một kỹ thuật truyền tin mới cho phép các nút mạng trung gian mã hóa thông tin nó nhận được trước khi gửi đi. Mã mạng có nhiều ưu điểm nổi bật như cho phép tăng hiệu suất sử dụng băng thông, tăng độ bảo mật, giảm thời gian trễ và ảnh hưởng của lỗi trên đường truyền, v.v. Một trong những kỹ thuật mã mạng được nhiều người quan tâm là kỹ thuật mã mạng tuyến tính ngẫu nhiên, được đề xuất bởi Ho và đồng nghiệp năm 2006. Lấy mẫu nén là một phương pháp hiện đại được đề xuất năm 2004 bởi Candes và Dohono, cho phép lấy mẫu một tín hiệu có tính chất thưa hoặc có thể nén được với số mẫu ít hơn nhiều so với số mẫu lấy theo phương pháp truyền thống Nyquist. Hiện nay, kỹ thuật lấy mẫu nén đang được rất nhiều người quan tâm do có những ưu điểm nổi bật như: giảm dung lượng bộ nhớ, tăng tốc độ lấy mẫu của các bộ ADC, giảm tiêu hao năng lượng trong các bộ cảm biến, v.v. Trong kỹ thuật lấy mẫu nén, hệ thống thu thập tín hiệu được thiết kế tuyến tính ngẫu nhiên, phần nào tương tự như kỹ thuật mã mạng. Vì thế, việc áp dụng kỹ thuật lấy mẫu nén trong kỹ thuật mã mạng tuyến tính ngẫu nhiên được quan tâm trong luận văn này. Luận văn tập trung đi sâu vào tìm hiểu kỹ thuật mã mạng, kỹ thuật mã mạng tuyến tính ngẫu nhiên, kỹ thuật lấy mẫu nén và kỹ thuật lấy mẫu nén có cấu trúc nhằm đào sâu áp dụng của kỹ thuật lấy mẫu nén và lấy mẫu nén có cấu trúc cho kỹ thuật mã mạng, với mục tiêu áp dụng kỹ thuật mã mạng có cấu trúc nhằm giảm thiểu độ phức tạp tính toán tại các nút mạng. Sau đó, luận văn trình bày phần mềm mô phỏng NECO là một phần mềm mô phỏng mới, hiệu năng cao để đánh giá kỹ thuật mã mạng dựa trên các giao thức. 1    CHƯƠNG 1 GIỚI THIỆU 1.1. Kỹ thuật mã mạng Trong các mạng truyền thông hiện nay, phương thức truyền tin được thực hiện bởi phương pháp định tuyến trong đó các nút mạng chỉ làm nhiệm vụ đơn thuần là lưu giữ và chuyển tiếp thông tin, còn việc xử lý thông tin chỉ được thực hiện tại các nút đầu cuối. Với phương thức truyền thống này, trong trường hợp nhiều nút nguồn cùng gửi thông tin đồng thời sẽ dẫn đến trường hợp là tài nguyên mạng bị chia sẻ và tốc độ truyền tin của mỗi một nút nguồn sẽ bị giảm đi. Mã mạng (network coding) được đề xuất năm 2000 bởi Ahslwede và đồng nghiệp [1] và đang càng lúc càng thu hút nhiều nhà nghiên cứu quan tâm. Bằng việc mã hóa tại các nút mạng trung gian, kỹ thuật mã mạng tác động lớn đến thế hệ mới của mạng truyền thông bởi nhiều lợi ích tiềm năng của nó như: làm tăng thông lượng, tăng tính bảo mật của mạng và tiết kiệm tài nguyên mạng không dây. Hiện nay, mã mạng đã trở thành một lĩnh vực nghiên cứu lớn trong lý thuyết thông tin và được xem là có khả năng cách mạng hóa hiểu biết của chúng ta về mạng truyền thông cũng như phương thức điều hành và quản lý mạng. Nhiều nghiên cứu về mã mạng đã tập trung xung quanh một dạng mã mạng đặc biệt, đó là mã mạng tuyến tính ngẫu nhiên (RLNC – Random linear network coding). RLNC, được Tracy Ho và đồng nghiệp giới thiệu trong công trình “A Random Linear Network Coding approach to Multicast” [3], là một phương pháp mã hóa đơn giản, ngẫu nhiên duy trì “một véc tơ các hệ số cho các gói tin khác nhau từ nguồn và được cập nhật bởi mỗi nút mã hóa”. Nói cách khác, RLNC yêu cầu các gói tin truyền qua mạng phải đi kèm với một số thông tin bổ sun g (ở đây chính là một véc tơ các hệ số). Trong các mạng truyền thông ngày nay, một loại mạng được sử dụng rộng rãi, dễ dàng chứa các thông tin thêm đó chính là mạng gói. Với các gói dữ liệu, thông tin thêm có thể được đặt trong tiêu đề gói tin. Ví dụ như số thứ tự thường được đặt trong tiêu đề gói tin để theo dõi đơn đặt hàng. 1.2. Kỹ thuật lấy mẫu nén 2    Chúng ta đang sống trong một thế giới kỹ thuật số. Viễn thông, giải trí, thiết bị y tế, tiện ích, kinh doanh - tất cả đều xoay quanh phương tiện truyền thông kỹ thuật số. Thiết bị chuyển đổi tương tự - số biến đổi các thông tin vật lý thành một chuỗi các con số. Về cơ bản tất cả các bộ chuyển đổi tương tự - số cho đến nay đều tuân theo định lý lấy mẫu Shannon-Nyquist. Định lý này yêu cầu tỷ lệ lấy mẫu ít nhất là gấp đôi băng thông của tín hiệu. Nguyên lý này là cơ sở của các ứng dụng xử lý tín hiệu số như âm thanh, video, radio, ứng dụng radar, thiết bị y tế, v.v. Khi công nghệ phát triển, do đó yêu cầu về số lượng dữ liệu ngày càng tăng, gây áp lực lên cả thiết bị chuyển đổi tương tự - số, xử lý tín hiệu số và phương tiện lưu trữ thông tin. Chính vì vậy tỷ lệ lấy mẫu theo định lý Shannon-Nyquist đã gặp phải những thách thức lớn cả về phần cứng, lưu trữ và xử lý tín hiệu số. Lấy mẫu nén (compressed sensing) được đề xuất bởi Candes và Dohono năm 2004 [16, 17], cho phép lấy mẫu một tín hiệu có tính chất thưa hoặc có thể nén được với số mẫu ít hơn nhiều so với số mẫu lấy theo phương pháp truyền thống Nyquist. Lấy mẫu nén đang được nhiều người quan tâm vì nó có những ưu điểm lớn như: giảm dung lượng bộ nhớ, giảm tốc độ lấy mẫu của các bộ chuyển đổi tương tự - số, giảm thiểu tiêu hao năng lượng trong các bộ cảm biến... Từ những ưu điểm này, kỹ thuật lấy mẫu nén đang được áp dụng cho kỹ thuật mã mạng với mục tiêu truyền thông hiệu quả trong mạng không dây. 1.3. Mục tiêu nghiên cứu Luận văn này có mục đích tìm hiểu kỹ thuật mã mạng, mã mạng tuyến tính ngẫu nhiên, kỹ thuật lấy mẫu nén nhằm đào sâu áp dụng kỹ thuật lấy mẫu nén cho kỹ thuật mã mạng. Để hiểu rõ hơn lý thuyết cũng như đánh giá hiệu năng của việc áp dụng kỹ thuật lấy mẫu nén cho kỹ thuật mã mạng, từ đó ứng dụng vào thực tế cần phải có các công cụ mô phỏng. Phần cuối của luận văn trình bày phần mềm mô phỏng NECO, một phần mềm mô phỏng mới, hiệu năng cao để đánh giá kỹ thuật mã mạng dựa trên các giao thức. Hiện nay, khá nhiều bài báo viết về NC đều sử dụng NECO là phần mềm giúp đánh giá kết quả. NECO sử dụng ngôn ngữ lập trình Python khá đơn giản và dễ đọc. Tuy nhiên, đây cũng là phần mềm mới nên các tài liệu tham khảo vẫn còn khá ít. 3    1.4. Cấu trúc của luận văn Luận văn được phân bố cụ thể như sau. Chương 2 giới thiệu về kỹ thuật mã mạng, các tính năng của nó so với kỹ thuật định tuyến thông thường và cuối cùng là giới thiệu kỹ thuật mã mạng tuyến tính ngẫu nhiên, làm nền tảng cho việc nghiên cứu áp dụng nó trong mạng cảm biến không dây. Chương 3 trình bày áp dụng của kỹ thuật lấy mẫu nén trong mạng cảm biến không dây dựa trên kỹ thuật mã mạng tuyến tính ngẫu nhiên. Chương 4 giới thiệu về phần mềm mô phỏng NECO, được thiết kế đặc biệt cho mục tiêu nghiên cứu kỹ thuật mã mạng. Cuối cùng, chương 5 đưa ra một số kết luận của luận văn. 4    CHƯƠNG 2 MÃ MẠNG 2.1. Giới thiệu Trong những năm gần đây, sự ra đời của mã mạng đã mở ra một hướng nghiên cứu mới đầy triển vọng, được xem là có khả năng cách mạng hóa phương thức điều hành, quản lý và hiểu về cơ cấu của mạng truyền thông. Đối với mã mạng, chúng ta có thể cho phép các nút không chỉ chuyển tiếp mà còn xử lý các luồng thông tin đến độc lập.Ví dụ, tại lớp mạng các nút trung gian có thể thực hiện cộng nhị phân chuỗi bít độc lập, trong khi đó, ở lớp vật lý của các mạng quang học, các nút trung gian có thể xếp chồng các tín hiệu quang đến. Nói cách khác, các luồng dữ liệu được tạo ra độc lập không cần được lưu giữ riêng biệt khi truyền trong mạng. Có nhiều cách để kết hợp và sau đó tách thông tin độc lập. Việc kết hợp các luồng dữ liệu độc lập cho phép điều khiển luồng thông tin trong môi trường mạng tốt hơn và phù hợp hơn với nhu cầu của các mô hình lưu lượng cụ thể. Sự thay đổi trong mô hình truyền dữ liệu có tác động sâu sắc trên một loạt các lĩnh vực như: truyền dữ liệu tin cậy, chia sẻ tài nguyên, điều khiển luồng dữ liệu hiệu quả, giám sát mạng, và bảo mật. Mô hình truyền dữ liệu mới này xuất hiện tại thời điểm chuyển giao thiên niên kỷ, và ngay lập tức thu hút sự quan tâm rất lớn trong lĩnh vực kỹ thuật điện tử và cộng đồng nghiên cứu khoa học máy tính. Mã mạng sử dụng sức mạnh tính toán giá rẻ để làm tăng đáng kể thông lượng mạng. Sự quan tâm trong lĩnh vực này vẫn tiếp tục tăng lên khi chúng ta thấy các ứng dụng mới sử dụng những ý tưởng này trong cả lý thuyết và thực tế của các mạng, và khám phá các kết nối mới với nhiều lĩnh vực (xem Hình 2.1). 5      Hình 2.1: Kết nối mã mạng với những lĩnh vực khác [5]. 2.2. Mã mạng là gì? Trong bài báo về “Network information flow” [1], Ahlswede, Cai, Li, và Yeung đề xuất mã mạng bằng cách mã hóa, tức là ánh xạ nhân quả tùy ý từ đầu vào của một nút trung gian của mạng đến đầu ra. Đây được coi là định nghĩa chung nhất của mã mạng. Một định nghĩa khác về mã mạng là mã hóa tại một nút trong một mạng với các liên kết không có lỗi. Định nghĩa phân biệt chức năng của mã mạng với mã hóa kênh cho các liên kết ồn (noisy). Định nghĩa này được sử dụng khá thường xuyên. Định nghĩa thứ ba của mã mạng, là mã hóa trong một mạng gói, tức là dữ liệu được chia thành các gói và mã mạng được áp dụng cho các nội dung của gói tin, hoặc tổng quát hơn mã hóa ở trên lớp vật lý. Điều này không giống như lý thuyết thông tin mạng, thường liên quan tới mã hóa ở lớp vật lý. 2.3. Các lợi ích của mã mạng Lợi ích được biết đến nhiều nhất của mã mạng là tăng thông lượng. Lợi ích này đạt được bằng cách truyền gói dữ liệu hiệu quả hơn, ví dụ như truyền nhiều thông tin chỉ bằng ít các gói tin. Ví dụ nổi tiếng nhất của lợi ích này được đưa ra bởi Ahlswede và đồng nghiệp trong [1], thường được gọi là mạng cánh bướm (hình 2.2) trong đó một nguồn duy nhất phát đa điểm đến hai đích. Cả hai đích đều muốn biết đầy đủ các thông tin tại nút nguồn. Bằng việc mã hóa tại các nút mạng trung gian, kỹ thuật mã mạng tác động lớn đến thế hệ mới của mạng truyền thông bởi nhiều lợi ích tiềm năng của nó. Kỹ thuật mã mạng còn đem đến một số lợi ích khác như tiết kiệm tài nguyên mạng không 6    dây, tăng độ bảo mật. Sau đây, chúng tôi sẽ giải thích rõ hơn các lợi ích của kỹ thuật mã mạng. 2.3.1 Tăng thông lượng   Hình 2.2: Mạng cánh bướm [30]. Hình 2.2 trên đây mô tả một mạng truyền thông được biểu diễn bằng một đồ thị có hướng mà các đỉnh tương ứng với các thiết bị đầu cuối và các cạnh tương ứng với các kênh truyền. Trong mạng kết nối đa điểm, một trong các nút trung gian phá vỡ các mô hình định tuyến truyền thống của mạng gói là các nút trung gian chỉ được phép sao chép các gói dữ liệu nhận được đưa ra đầu ra và thực hiện mã hóa hai gói tin nhận được, tạo thành một gói tin mới bằng cách lấy tổng nhị phân (XOR) để tạo thành một gói tin kết quả ở đầu ra. Như vậy, nếu nội dung của hai gói tin nhận được là véc tơ x1 và x2 thì gói tin ở đầu ra sẽ là x1  x2 . Đích R1 khôi phục x2 bằng cách lấy tổng XOR của x1 và x1  x2 . Tương tự như vậy đích R2 khôi phục x1 bằng cách lấy tổng XOR x2 với x1  x2 . Xét mạng phát đa điểm từ hai nguồn đến hai như trong hình 2.3. Trong mạng này, mỗi cạnh biểu diễn một liên kết trực tiếp có thể mang một gói dữ liệu đơn. Gói x1 biểu diễn tại nguồn dữ liệu S1 truyền tới nút đích R1 và gói dữ liệu x1 biểu diễn tại nút nguồn S2 truyền đến nút đích R2 .  Trong thực tế, thông qua cạnh CE, ta chỉ có thể truyền 1 bít trong mỗi khe thời gian. Tuy nhiên, muốn đồng thời gửi bít x1 để R2 nhận và bit x2 để 7    R1 nhận.Theo truyền thống, luồng thông tin được xử lý như một luồng chất lỏng thông qua đường ống, và các luồng thông tin độc lập được lưu giữ riêng biệt. Áp dụng phương pháp này, ta phải đưa ra quyết định cho cạnh CE để gửi bit x1 hoặc x2 . Nếu chúng ta quyết định gửi bit x1 , lúc đó R1 sẽ chỉ nhận được x1 trong khi R2 sẽ nhận được cả hai bít x1 và x2 . Theo ý tưởng đầu tiên của Ahlswede và đồng nghiệp, mã mạng cho phép các nút trung gian trong mạng có thể xử lý các luồng thông tin đầu vào của chúng thay vì chỉ chuyển tiếp chúng. Cụ thể là, trước hết nút C có thể XOR hai bít x1 và x2 để tạo ra một bit thứ ba x3 = x1  x2 . Sau đó C truyền x3 qua cạnh CE. Nút nhận R1 sẽ nhận được { x1 , x1  x2 } và giải mã để thu được x2 . Cuối cùng, R1 đã nhận được cả x1 và x2 như mục tiêu của truyền đa điểm. Tương tự như vậy, nút nhận R2 nhận được { x2 , x1  x2 } giải mã để thu được x1 . Rõ ràng rằng, thay vì sử dụng 2 khe thời gian để chuyển tin x1 và x2 như trong mạng truyền thống, C chỉ cần dùng một khe thời gian để truyền x3 . Như vậy, mạng có kết hợp kỹ thuật mã mạng cho phép tăng thông lượng.   Hình 2.3: Mạng cánh bướm với 2 nguồn và 2 đích [30]. Mã mạng cũng có thể được mở rộng với các mạng không dây. Hình 2.4 bản sao không dây của mạng cánh bướm và hình 2.5 là mạng cánh bướm sửa đổi. Trong các hình này, các gói tin bắt nguồn từ một nút duy nhất và kết thúc tại nhiều nút. 8      Hình 2.4: Mạng cánh bướm không dây [30].   Hình 2.5: Mạng cánh bướm không dây sửa đổi [30]. Trong hình 2.4, mỗi cạnh biểu diễn một liên kết trực tiếp có khả năng truyền một gói dữ liệu tới một hoặc nhiều nút. Ta muốn chuyển hai gói tin x1 và x2 từ nút nguồn S tới hai nút đích R1 và R2 . Trong hình 2.5, mỗi cạnh biểu diễn một liên kết trực tiếp có khả năng truyền một gói dữ liệu tới một hoặc nhiều nút. Một gói x1 tại nút nguồn S1 muốn truyền tới nút S2 và gói x2 tại nút nguồn S2 muốn truyền tới nút S1 . Như vậy mã mạng làm tăng thông lượng khi gói được truyền đi chỉ từ một nút duy nhất tới một nút duy nhất khác (mạng hữu tuyến) và khi chúng được truyền từ một nút duy nhất đến một hoặc nhiều nút khác (mạng không dây). 2.3.2 Tiết kiệm tài nguyên mạng không dây Trong một môi trường không dây, mã mạng có thể được sử dụng để tạo ra những 9    lợi ích về tuổi thọ pin, băng thông không dây và trễ truyền. Xét một mạng ad-hoc không dây, thiết bị A và C muốn trao đổi các tập tin nhị phân x1 và x2 bằng cách sử dụng thiết bị B là một relay. Giả sử thời gian sử dụng đường truyền được chia làm nhiều khung, mỗi khung được chia thành nhiều khe thời gian (Ts time slot) và một thiết bị có thể phát hoặc thu một tập tin trong một khe thời gian (truyền thông bán song công). Hình 2.6 bên trái mô tả phương pháp truyền thống: các nút A và C gửi các tập tin của chúng tới B, sau đó B sẽ lần lượt chuyển tiếp mỗi tập tin đến các đích tương ứng. (a) (b) Hình 2.6: Nút A và C chuyển tiếp thông tin thông qua relay B. (a) Không sử dụng mã mạng, (b) sử dụng mã mạng. Phương pháp mã mạng sử dụng một đường phát đa điểm [5]. Phương pháp mã mạng tận dụng lợi ích tự nhiên của các kênh phát sóng không dây là phát đa điểm để tạo ra các lợi ích về sử dụng nguồn tài nguyên, như minh họa trên hình 2.6. Đặc biệt, nút C nhận được cả hai tập tin x1 và x2 , và thực hiện xor x1 và x2 tạo ra tập tin x1  x2 . Sau đó tập tin x1  x2 này được phát đa điểm tới cả hai nút nhận. Nút A đã có x1 và do đó, có thể giải mã để thu được x2 . Nút C đã có x2 và có thể giải mã để thu được x1 . Phương pháp này tạo ra các lợi ích về sử dụng năng lượng hiệu quả (nút B chỉ truyền một lần thay vì hai lần), trễ truyền (truyền trong ba khe thời gian thay vì bốn khe thời gian), băng thông không dây  (thời gian sử dụng kênh không dây ngắn hơn), và 10    nhiễu (nếu có các nút không dây khác cố gắng truyền tin trong khu vực lân cận). 2.3.3 Tăng cường tính bảo mật Việc truyền đi sự kết hợp tuyến tính của các gói tin thay vì dữ liệu chưa được mã hóa tạo ra lợi ích bảo mật đa dạng, chống lại các cuộc tấn công nghe lén. Vì vậy, đối với những hệ thống mà chỉ cần chống lại các cuộc tấn công đơn giản như vậy không cần cơ chế bảo mật bổ sung. Giả sử nút A gửi thông tin tới nút D thông qua hai đường truyền ABD  và  ACD trong hình 2.7. Giả sử, một người (N) có thể nghe trộm trên một đường, và không có quyền truy cập trên đường bổ sung. Nếu các ký hiệu độc lập x1 và x2 được gửi mà không mã hóa, N có thể chặn một trong các ký hiệu đó. Thay vào đó, ta gửi sự kết hợp tuyến tính của các ký hiệu đó, thông qua một số trường hữu hạn, trên các đường truyền khác nhau, N sẽ không thể giải mã bất kỳ phần nào của dữ liệu. Ví dụ, nếu N thu được gói tin đã được mã hóa x1  x2 , xác suất đoán chính xác x1 hoặc x2 chỉ bằng 50%, giống như đoán ngẫu nhiên.   Hình 2.7: Trộn thông tin để tạo ra cách bảo vệ tự nhiên chống lại nghe trộm [5]. 2.3.4 Tính bền (Robustness) Kỹ thuật mã mạng có tính bền, khi tô-pô mạng bị thay đổi hay khi một số liên kết mạng không hoạt động, do mỗi gói tin được mã hóa chứa thông tin của nhiều gói tin khác nên nếu ta nhận được một số lượng đủ lớn gói tin mã hóa thì ta có thể thu lại thông tin đã được gửi đi. Bên cạnh khả năng chống lại tổn thất gói ngẫu nhiên, mã mạng cũng hữu ích cho việc chống lại các liên kết lỗi non-ergodic. Đó chính là bảo vệ duy trì đường truyền, ở 11    đây, một luồng chính và một luồng dự phòng được truyền cho mỗi kết nối, cho phép khôi phục các liên kết thất bại rất nhanh, do không cần phải định tuyến lại. Tuy nhiên, phương pháp này làm tăng gấp đôi thông lượng mạng. Bằng cách cho phép chia sẻ tài nguyên mạng giữa các luồng khác nhau, mã mạng có thể làm tăng cách sử dụng tài nguyên. 2.4. Mã mạng gặp phải những thách thức gì? Bên cạnh những lợi ích của mã mạng đã trình bày ở trên, việc triển khai mã mạng cũng gặp một số thách thức. Phần này trình bày một số thách thức chính của mã mạng. 2.4.1 Phức tạp Sử dụng mã mạng đòi hỏi các nút trong mạng phải có thêm các chức năng bổ sung. Trong hình 2.6, nút B cần có thêm bộ nhớ bổ sung để lưu trữ x1 tập tin thay vì ngay lập tức phát quảng bá và thực hiện các tính toán thông qua các trường hữu hạn, tức là thực hiện phép toán XOR x1 và x2 . Hơn nữa, các nút A và C cũng cần phải lưu trữ thông tin của chúng và sau đó giải một hệ các phương trình tuyến tính. 2.4.2 Bảo mật Trong truyền thông mạng, bảo mật là một yêu cầu quan trọng để chống lại các cuộc tấn công tinh vi. Do đó, việc triển khai mã mạng trong mạng đó cần phải đưa vào các cơ chế cho phép mạng thực hiện mã hóa mà không ảnh hưởng đến tính xác thực của dữ liệu. Xét về mặt bảo mật, mã mạng có thể đem lại cả lợi ích và những điều bất lợi. Xét mạng cánh bướm (hình 2.2). Giả sử một kẻ thù (N) nhận được được chỉ x1  x2 gói. Với chỉ gói x1  x2 , N không có thể có được hoặc x1 hay x2 . Như vậy ta có một cơ chế truyền thông bảo mật. Trong trường hợp này, mã mạng đưa ra lợi ích là tăng độ bảo mật của thông tin. Mặt khác, ta giả sử nút 3 là một nút có hại không gửi x1  x2 mà là một gói tin giả mạo tương tự như x1  x2 . Do các gói tin được mã hóa chứ không phải là định tuyến nên rất khó phát hiện gói tin đó là giả mạo hay là gói tin thật. Trong trường hợp này, mã mạng dẫn đến mặt hạn chế về bảo mật.