


ĐẠ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 Linh Trung






HÀ NỘI – 2012
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

Chữ viết tắt
Tiếng Anh 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
Coding
Mã mạng tuyến tính ngẫu nhiên
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ố
i
s 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
Hình 3.3 : (a) Không gian con chứa 2 véc tơ rải rác trong
3
R
nằm gần với trục tọa độ;
(b) Trực quan hóa tối thiểu
2
l (5) tìm điểm tiếp xúc không rải rác
ˆ

s
giữa bóng
2
l và ma
trận đo chuyển đổi trong không gian rỗng; (c) Trực quan hóa tối thiểu
1
l tìm điểm tiếp
xúc rải rác
ˆ
s
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ơ
1
x
và
2
x
thì gói
tin ở đầu ra sẽ là
12
x
x . Đích
1
R
khôi phục
2
x
bằng cách lấy tổng XOR của
1
x
và
12
x
x . Tương tự như vậy đích
2
R
khôi phục
1
x
bằng cách lấy tổng XOR
2

x
với
12
x
x .
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
1
x
biểu
diễn tại nguồn dữ liệu
1
S
truyền tới nút đích
1
R
và gói dữ liệu
1
x
biểu diễn tại nút nguồn
2
S
truyền đến nút đích
2
R
.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
1
x
để

2
R
nhận và bit
2
x
để
7

1
R
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
1
x
hoặc
2
x
. Nếu chúng ta
quyết định gửi bit
1
x
, lúc đó
1
R
sẽ chỉ nhận được
1
x
trong khi
2

R
sẽ nhận được cả hai bít
1
x
và
2
x
.
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
1
x
và
2
x
để tạo ra một
bit thứ ba
3
x
=
12
x
x . Sau đó C truyền
3
x
qua cạnh CE. Nút nhận
1
R
sẽ nhận được

{
1
x
,
12
x
x } và giải mã để thu được
2
x
. Cuối cùng,
1
R
đã nhận được cả
1
x
và
2
x
như mục
tiêu của truyền đa điểm. Tương tự như vậy, nút nhận
2
R
nhận được {
2
x
,
12
x
x


} giải
mã để thu được
1
x
. Rõ ràng rằng, thay vì sử dụng 2 khe thời gian để chuyển tin
1
x
và
2
x
như trong mạng truyền thống, C chỉ cần dùng một khe thời gian để truyền
3
x
.
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
1
x

và
2
x
từ nút nguồn S tới
hai nút đích
1
R
và
2
R
. 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
1
x
tại nút nguồn
1
S
muốn
truyền tới nút
2
S
và gói
2
x
tại nút nguồn
2
S
muốn truyền tới nút
1
S

. 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
1
x
và
2
x
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

1
x
và
2
x
, và thực hiện xor
1
x
và
2
x
tạo ra tập tin
12
x
x

. Sau đó tập tin
12
x
x

này được phát đa điểm tới cả hai nút nhận.
Nút A đã có
1
x
và do đó, có thể giải mã để thu được
2
x
. Nút C đã có
2

x
và có thể giải mã
để thu được
1
x
.
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
1
x
và
2
x
đượ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
12
x
x , xác suất đoán chính xác
1
x
hoặc
2
x
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ữ
1
x
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
1
x
và
2
x
. 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ỉ
12
x
x gói. Với

chỉ gói
12
x
x , N không có thể có được hoặc
1
x
hay
2
x
. 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
12
x
x mà là một
gói tin giả mạo tương tự như
12
x
x

. 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.
12

2.4.3 Tích hợp với cơ sở hạ tầng hiện có
Khi mạng truyền thông phát triển thành những cơ sở hạ tầng ở khắp mọi nơi, một
nhiệm vụ khó khăn là kết hợp các công nghệ mới nổi như mã mạng với kiến trúc mạng
hiện có. Lý tưởng nhất, ta muốn sử dụng những lợi ích mà mã mạng đem lại mà không
làm thay đổi đáng kể trong các thiết b

ị và phần mềm. Một câu hỏi mở là làm thế nào mã
mạng có thể được tích hợp trong các giao thức mạng hiện tại? Hiện nay vấn đề này cũng
là một lĩnh vực cần nghiên cứu.
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
2.5.1 Định lý Luồng cực đại lát cắt cực tiểu (Min – Cut Max – Flow)
Cho G = (V, E) là một đồ thị (mạng) với tập các
đỉnh V và tập các cạnh E⊂V×V.
Giả sử rằng các cạnh có khả năng thông qua (capacity) là đơn vị và cho phép các cạnh
là tương đương nhau. Xét một nút S ⊂ V muốn truyền thông tin tới nút R ⊂ V . Một
lát cắt giữa S và R là một tập các cạnh của đồ thị phân tách S và R thành 2 tập rời nhau.
Giá trị của lát cắt là tổng các khả năng thông qua của các cạnh trong lát cắt. Lát cắt có
giá trị nhỏ nhất gọi là lát cắt c
ực tiểu (min - cut).
Giả sử dung năng của các cạnh là 1 thì giá trị của một lát cắt bằng với số các cạnh
trong lát cắt. Như vậy thuật ngữ min – cut tương đương với tổng số các cạnh trong lát
cắt. Giả sử như mạng được cấu hình như trong hình 2.8, như vậy tồn tại 3 đường đi
phân tách giữa S và R mang ba ký hiệu
1
x
,
2
x
và
3
x
.

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].
13


Định lý 1 [5]: “Xét một đồ thị G = (V, E) với các cạnh có khả năng thông qua đơn
vị, đỉnh phát là S, đỉnh thu là R. Nếu lát cắt nhỏ nhất giữa đỉnh phát S và đỉnh thu R là h
thì thông tin có thể truyền từ S tới R với tốc độ lớn nhất là h. Tương đương, tồn tại
chính xác h đường đi phân tách giữa đỉnh phát và đỉnh thu”.
2.5.2 Định lý chính của mã mạng
Xét một mạng phát đa điểm G = (V, E) trong đó có h nguồ
n có tốc độ đơn vị
1
S
, ,
h
S
nằm trên cùng một mạng. Nút S (nguồn) đồng thời truyền thông tin đến N nút
nhận
1
R
, ,
N
R
. Giả sử rằng G là một đồ thị có hướng không tuần hoàn với khả năng
thông qua của các cạnh bằng đơn vị, và giá trị min-cut giữa nút nguồn và nút nhận là h.
Tại mỗi thời điểm, giả sử không có trễ truyền, có nghĩa là trong mỗi khe thời gian tất cả
các nút nhận được tất cả đầu vào và gửi các kết quả đầu ra đồng thời.
Chúng ta nói, dung năng c
ủa các cạnh bằng đơn vị có nghĩa là: giả sử mô hình có
các cạnh có dung năng bằng 1, trong mỗi khe thời gian, có thể truyền tin cậy một ký
hiệu từ một số trường hữu hạn
q
F

có kích thước q. Do đó, mỗi nguồn có tốc độ đơn vị S
i
phát ra σ
i
, 1 <i <h, đây cũng là một phần tử của trường
q
F
.
Định lý 2 [5]: “Giả sử một đồ thị có hướng không tuần hoàn G=(V, E) có khả
năng thông qua của các cạnh bằng đơn vị, h nguồn có tốc độ đơn vị được đặt trên cùng
đỉnh của đồ thị và N đỉnh thu. Giả sử, giá trị của lát cắt cực tiểu tới mỗi đỉnh thu là h.
Do đó, tồn tại một sơ đồ phát đa điểm trên một trườ
ng hữu hạn đủ lớn
q
F
, trong đó các
nút trung gian kết hợp tuyến tính các ký hiệu thông tin đến trên
q
F
, phát thông tin đồng
thời từ đỉnh phát tới các đỉnh thu với tốc độ bằng h”.
Từ định lý 1, chúng ta biết rằng tồn tại h đường đi phân tách giữa đỉnh phát và mỗi
đỉnh thu. Vì vậy, nếu bất kỳ đỉnh thu R
j
nào sử dụng mạng, thông tin từ h đỉnh thu có
thể được định tuyến đến R
j
thông qua một tập h các đường đi. Khi nhiều đỉnh thu đồng
thời sử dụng mạng, tập hợp các đường đi có thể chồng lên nhau. Do đó, các đỉnh thu sẽ
phải chia sẻ các tài nguyên mạng, điều này làm giảm tốc độ truyền dữ liệu. Như vậy,

theo định lý 2 nếu cho phép các nút trung gian không chỉ chuyển tiếp dữ liệu mà còn kết
hợp các luồng thông tin đến thì mỗi đỉnh thu sẽ nhận được thông tin ở mức tương tự
như trường hợp chỉ có duy nhất đỉnh thu đó truy cập các tài nguyên mạng.
14

Trong mã mạng, mỗi đỉnh trong mạng có quyền kết hợp các gói đầu vào theo cách
tùy ý để gửi ra các liên kết đầu ra. Để đơn giản, ta giả sử tất cả các gói đều có cùng kích
thước là m bits, nghĩa là mỗi gói có thể được xem như một phần tử của trường F = 2m.
Sự “kết hợp” của các gói của các đầu vào ra một liên kết ra nào đó chẳng qua là một
hàm số. Khi ta nói
2
m
q  đơn giản có nghĩa là mỗi gói tin gửi từ nguồn có m bít, với m
đơn vị thời gian
được xác định là một khe thời gian. M bít được dùng để biểu diễn một
ký hiệu của
q
F
và được các nút mạng xử lý sử dụng các toán tử
q
F
. 
2.6 Kỹ thuật mã mạng tuyến tính
Cho mạng có
12
,XX là các nguồn phát đa điểm đến các nút nhận, và các hệ số

i
là
các phần tử của một trường hữu hạn, như mô tả trong hình 2.9. Nhãn trên mỗi liên kết

biểu diễn quá trình được truyền vào liên kết.

Hình 2.9: Ví dụ về mã mạng tuyến tính ngẫu nhiên phân bố [20].
Xét một mạng được biểu diễn bằng một đồ thị có hướng (,)GV

 , ở đây V là tập
các nút mạng và

là tập các liên kết. Thông tin có thể được gửi mà không bị nhiễu từ
nút i tới nút j với tất cả
(, )ij

 . Mỗi liên kết l


gắn với một số thực không âm
l
c biểu
diễn dung năng của liên kết đó. Các nút
i và
j
được gọi là nút nguồn và đích tương ứng
của liên kết(, )ij . Nguồn và đích của một liên kết
l


được biểu diễn tương ứng
bằng
()ol và ()dl . Giả sử () ()ol dl với mọi



l . Thông tin truyền trên liên kết l


có
thể coi là một hàm của thông tin nhận được trước đó tại ()ol .
Có r nguồn không nhớ
12
,
r
XX Xlà các chuỗi nhị phân ngẫu nhiên. Các
i
X được tạo
15

tại nút ()ai và phát đa điểm tới tất cả các nút ()
j
bi

, trong đó


: 1, ,arV và


: 1, , 2
V
br là các ánh xạ tùy ý. Các nút
(1), (2) , ( )aa ar
được gọi là các nút nguồn

và các nút


1
, ,
d
được gọi là các nút đích.
Xét cả hai trường hợp của mạng không tuần hoàn không xét đến trễ và trường hợp
mạng tuần hoàn và có trễ. Các gói tin khác nhau
j
Y truyền trên một liên kết j theo dạng là
sự kết hợp tuyến tính trên ,2
u
q
Fq

, của liên kết đầu vào j là các gói tin từ nguồn
i
X
với
() ( )ai o j và quá trình ngẫu nhiên
l
Y với () ( )dl o j

.
j
Y được biểu diễn bởi phương
trình:
  
,,

:() () :() ()
jijiljl
ia i o j ld l o j
YaX fY



(2.1)
Gói tin đầu ra thứ i
,i
Z

tại nút nhận

được biểu diễn như sau:

,
,,
:() )
i
il l
ld l
Z
bY








Đối với mạng phát đa điểm có trễ liên kết, cần phải có bộ nhớ tại nút nhận (hoặc nút
nguồn). Xét các liên kết có trễ là 1, mô hình hóa các liên kết có trễ lớn hơn là một loạt
các liên kết có trễ là 1 mắc nối tiếp. Phương trình mã hóa tuyến tính tương ứng là:
  
,,
:() () :() ()
(1) () ()
jijiljl
ia i o j ld l o j
Yt aXt fYt

 




,
'''
,, ,,
0:()0
(1) () ( ) ( )
i
ii ill
uldlu
Z
tbuZtu bYtu


 



  


Ở đây,
'''
,, ,,
(), (), (), () à ()
ij i i il
X
tYtZ tb tvb t
 
là các giá trị của các biến tương ứng tại
thời điểm t. Các phương trình này như với quá trình ngẫu nhiên trong mạng, có thể được
biểu diễn về mặt đại số dưới dạng một biến trễ D.
  
,,
:() () :() ()
() () ()
jijiljl
ia i o j ld l o j
Y D Da X D Df Y t





,
,,

:()
() ()
i
il l
ld l
Z
DbYD







Ở đây
16

1''
,,
0
,,
1'
,
0
()
()
1()
u
il
u

il
u
i
u
Db u
bD
Db u













(2.2)
0
() ()
t
ii
t
X
DXtD






0
() () , (0) 0
t
it j
t
YD Y jD Y





,, ,
0
() () , (0) 0
t
ii i
t
ZD ZtD Z
 





Các hệ số



,, ,,
,,
ij lj il
fb


có thể được lựa chọn trong các ma trận
r


.
A=
,
()
ij
a trong trường hợp mạng hở không trễ

,
()
ij
Da trong trường hợp thông thường có trễ
và
,,
()
il
Bb


F=
,

()
lj
f
trong trường hợp mạng hở không trễ

,
()
lj
Df trong trường hợp thông thường có trễ
Một cặp (A, F) hoặc tập hợp
1
( , , , , )
d
AF B

B
có thể được gọi là một mã mạng
tuyến tính.
2.7 Kỹ thuật mã mạng tuyến tính ngẫu nhiên
Trong một mạng, tại một nút trung gian, khi hai hoặc nhiều gói tin đến nút sẽ tạo
ra từng số hệ số ngẫu nhiên sau đó nhân lần lượt từng hệ số ngẫu nhiên đó với các gói
dữ liệu đầu vào cuối cùng lấy tổng để tạo thành một gói tin mới ở đầu ra.
Kỹ thu
ật mã mạng tuyến tính ngẫu nhiên được thực hiện dựa trên việc lựa chọn
các giá trị của (A, F) ngẫu nhiên của một trường hữu hạn. Nếu một nút nhận
k

tồn tại
một số giá trị của
k

B

để
k
T
A
GB

có hạng đầy đủ r khi đó dữ liệu nguồn có thể được giải
mã tại nút đích.