ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN VIỆT ĐỨC
ẢNH HƢỞNG CỦA MÃ MẠNG LỚP VẬT LÝ TỚI DUNG
LƢỢNG KÊNH TRONG MẠNG OFDM
LUẬN VĂN THẠC SĨ CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG
Hà Nội - 2013
i
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN VIỆT ĐỨC
ẢNH HƢỞNG CỦA MÃ MẠNG LỚP VẬT LÝ TỚI DUNG
LƢỢNG KÊNH TRONG MẠNG OFDM
Ngành: Công nghệ Điện tử - Viễn thông
Chuyên ngành: Kỹ thuật điện tử
Mã số: 60520203
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. ĐINH TRIỀU DƢƠNG
Hà Nội - 2013
ii
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này là kết quả của riêng tôi, dưới sự hướng dẫn của TS
Đinh Triều Dương, không sao chép của ai. Nội dung luận văn có tham khảo và sử dụng
các tài liệu thông tin được đăng tải trên các tác phẩm, tạp chí và các trang Website theo
danh mục tài liệu tham khảo của luận văn.
Tác giả luận văn
Nguyễn Việt Đức
iii
LỜI CẢM ƠN
Trước tiên tôi muốn gửi lời biết ơn chân thành nhất đến T.S Đinh Triều Dương người thầy đã tận tình chỉ bảo và tạo điều kiện thuận lợi nhất cho tôi trong suốt thời gian
thực hiện luận văn.
Tôi xin chân thành cảm ơn chân thành đến các thầy cô trường Đại Học Công Nghệ
- Đại học Quốc Gia Hà Nội, đặc biệt là những thày cô đã tận tình dạy bảo cho tôi suốt
thời gian học tập và hoàn thành khóa học.
Cuối cùng tôi xin gửi lời cảm ơn tới bạn bè trong Trường Đại học Công Nghệ - Đại
học Quốc gia Hà Nội; Lãnh đạo công ty cổ phần MITEC và đồng nghiệp trong công ty;
những người thân trong gia đình đã động viên và cổ vũ tôi rất nhiều về tinh thần trong
suốt quá trình học tập và hoàn thành luận văn.
Mặc dù tôi đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả sự nhiệt tình và
năng lực của mình, nhưng luận văn không tránh khỏi nhiều thiếu sót, tôi rất mong nhận
được sự chỉ bảo của thầy cô cùng sự góp ý của các bạn.
Nguyễn Việt Đức
iv
MỤC LỤC
Trang phụ bìa
Trang
LỜI CAM ĐOAN ...........................................................................................................i
MỤC LỤC .....................................................................................................................iv
Danh mục các ký hiệu và chữ viết tắt ....................................................................... vii
Danh mục các bảng .......................................................................................................x
Danh mục các hình vẽ, đồ thị ......................................................................................xi
MỞ ĐẦU .........................................................................................................................1
Chƣơng 1. TỔNG QUAN CHUNG ..............................................................................3
1.1.
Mạng không dây .............................................................................................3
1.1.1.
Tổng quan ...............................................................................................3
1.1.2.
Các mô hình mạng không dây ...............................................................3
1.1.3.
Phân loại các mạng không dây theo khoảng cách vật lý......................4
1.2.
Mã hóa mạng ..................................................................................................5
1.2.1.
Mã hóa ....................................................................................................6
1.2.2.
Giải mã ....................................................................................................6
1.2.3.
Cách lựa chọn tổ hợp tuyến tính ...........................................................7
1.2.4.
Các vấn đề thực tế với mã mạng ............................................................7
1.2.4.1. Giải mã ....................................................................................................7
1.2.4.2. Kích thước khối .......................................................................................8
1.2.4.3. Các phép toán hữu hạn............................................................................8
1.2.5.
Lợi ích của mã hóa mạng.......................................................................8
1.2.5.1. Tăng cường thông lượng .........................................................................8
1.2.5.2. Ổn định và thích nghi ..............................................................................9
1.3.
Mạng không dây hình lƣới ..........................................................................10
1.3.1.
Lớp vật lý ............................................................................................... 11
1.3.2.
Lớp liên kết dữ liệu ............................................................................... 11
1.3.3.
Lớp mạng ..............................................................................................12
1.3.3.1. Giao thức định tuyến với metric khác nhau ..........................................12
1.3.3.2. Định tuyến đa đường .............................................................................12
1.3.3.3. Định tuyến theo vùng địa lý ...................................................................13
1.3.4.
1.4.
Lớp giao vận .........................................................................................13
Mã mạng lớp vật lý ......................................................................................13
1.4.1.
Mô hình mạng không mã hóa..............................................................15
v
1.4.2.
Mô hình sử dụng mã mạng ..................................................................15
1.4.3.
Mô hình sử dụng mã mạng lớp vật lý ..................................................16
1.4.4.
Các vấn đề quan trọng với mã mạng lớp vật lý ...................................18
1.4.4.1. Tạp âm ...................................................................................................18
1.4.4.2. Mã hóa kênh ..........................................................................................20
1.4.4.3. Đồng bộ .................................................................................................20
1.4.4.4. Kênh fading không đối xứng và ước lượng kênh...................................21
1.4.4.5. Lý thuyết dung lượng kênh ....................................................................23
1.4.4.6. Mô hình mạng tổng quan và các vấn đề với lớp cao hơn. ....................23
Chƣơng 2. MẠNG DI ĐỘNG AD-HOC (MANET) DỰA TRÊN OFDM ..............24
2.1.
Mạng Mobile Ad-hoc Network (MANET) .................................................24
2.1.1.
Đặc điểm của mạng MANET ...............................................................25
2.1.2.
Kiến trúc mạng MANET ......................................................................26
2.1.2.1. Giao thức 802.11 ...................................................................................26
2.1.2.2. Lớp vật lý ...............................................................................................27
2.1.2.3. Lớp MAC ...............................................................................................28
2.1.3.
Định tuyến trong mạng MANET .........................................................29
2.1.3.1. Định tuyến theo bảng ............................................................................29
2.1.3.2. Định tuyến theo yêu cầu ........................................................................29
2.1.3.3. Định tuyến lai ghép ...............................................................................30
2.1.4.
Các giao thức định tuyến cơ bản trong mạng MANET ......................30
2.1.4.1. Định tuyến theo vector khoảng cách theo yêu cầu AODV. ....................30
2.1.4.2. Định tuyến theo vector khoảng cách tuần tự đích DSDV .....................31
2.1.4.3. Giao thức định tuyến nguồn động DSR .................................................31
2.1.4.4. Định tuyến theo trạng thái đường liên kết tối ưu - OLSR .....................32
2.1.4.5. Giao thức định tuyến vùng ZRP ............................................................32
2.2.
Kỹ thuật OFDM ...........................................................................................33
2.2.1.
Nguyên tắc cơ bản của OFDM ............................................................33
2.2.2.
Tính trực giao .......................................................................................35
2.2.3.
Sử dụng FFT/IFFT trong OFDM .......................................................36
2.2.4.
Nhiễu giao thoa ký tự và nhiễu giao thoa sóng mang ........................37
2.2.4.1. Khái niệm...............................................................................................37
2.2.4.2. Phương pháp chống nhiễu liên ký hiệu .................................................38
2.2.5.
Các vấn đề kỹ thuật trong OFDM .......................................................39
2.2.5.1. Ước lượng tham số kênh.......................................................................39
vi
2.2.5.2. Đồng bộ trong OFDM ...........................................................................40
2.2.5.3. Đồng bộ ký tự ........................................................................................40
2.2.5.4. Đồng bộ tần số sóng mang ....................................................................41
2.2.5.5. Đồng bộ tần số lấy mẫu .........................................................................41
2.2.5.6. Giảm PAPR (Peak to Average Power Ratio) .........................................41
2.2.6.
Hệ thống OFDM ...................................................................................42
2.2.7.
Ưu điểm và khuyết điểm của OFDM ...................................................43
2.2.7.1. Ưu điểm .................................................................................................43
2.2.7.2. Nhược điểm............................................................................................43
2.3.
Mạng MANET dựa trên công nghệ OFDM ...............................................44
Chƣơng 3: ẢNH HƢỞNG CỦA MÃ MẠNG LỚP VẬT LÝ TỚI DUNG LƢỢNG
KÊNH ...........................................................................................................................46
3.1.
Dung lƣợng mạng MANET một chiều .......................................................47
3.1.1.
Mô hình mạng MANET một chiều ......................................................47
3.1.1.1. Không gian mạng MANET một chiều ...............................................47
3.1.1.2. Đường cắt trong mạng MANET ........................................................49
3.1.2.
Dung lượng mạng MANET 1 chiều ....................................................49
3.1.2.1. Thông lượng mạng MANET truyền theo lưu lượng ..............................49
3.1.2.2. Thông lượng mạng MANET sử dụng mã mạng .....................................52
3.1.2.3. Thông lượng mạng MANET sử dụng mã mạng lớp vật lý .....................54
3.2.
Dung lƣợng mạng MANET 2 chiều ............................................................57
3.2.1.
Mô hình mạng MANET hai chiều .......................................................58
3.2.1.1. Không gian MANET hai chiều ..............................................................58
3.2.1.2. Định tuyến .............................................................................................59
3.2.1.3. Đường cắt ..............................................................................................59
3.2.2.
Dung lượng của mạng MANET hai chiều ..........................................60
3.2.2.1. Giới hạn trên dung lượng mạng MANET 2 chiều .................................60
3.2.2.2. Giới hạn dưới dung lượng mạng MANET 2 chiều ................................63
3.3. Ảnh hƣởng của mã mạng lớp vật lý tới dung lƣợng kênh trong mạng
MANET dùng OFDM .............................................................................................65
KẾT LUẬN ..................................................................................................................67
TÀI LIỆU THAM KHẢO ...........................................................................................68
PHỤ LỤC .....................................................................................................................71
vii
Danh mục các ký hiệu và chữ viết tắt
Ký hiệu
Tiếng Anh
Tiếng Việt
IP
Internet Protocol
Giao thức liên mạng
ACK
Acknowledgment
Bản tin báo nhận
ADSL
Asymmetric
Subscriber Line
ALOHA
Abramson's Logic of Hiring Giao thức OSI lớp 2 cho mạng LAN với
Access
Broadcast topology
API
Application
Interface
CDMA
Code
Division
Access
CMAPS
Conflict Maps
Bản đồ phân phối
CSMA
Carrier Sense Multiple Access
Đa truy cập nhận biết sóng mang
CSMA
/CA
Carrier Sense Multiple Access Đa truy cập nhận biết sóng mang phát
with Collision Avoidance
hiện xung đột
DFT
Discrete Fourier transform
DPSK
Differential
Keying
DSSS
Direct
Sequence
Spectrum
ETX
Expected Transmission Count
Số lượt dự kiến sẽ truyền
FDM
Time-division Multiplexing
Ghép kênh phân chia tần số
FDMA
Frequency Division Mutiple Đa truy cập theo phân chia tần số
Access
FFT
Fast Fourier Transform
Biến đổi Fourier nhanh
FIFO
First In First Out
Vào trước ra trước
Digital Đường dây thuê bao số bất đối xứng
Programming Giao diện lập trình ứng dụng
Multiple Đa truy cập phân chia theo mã
Phase
Biến đổi Fourier rời rạc
Shift Giải điều chế theo pha tín hiệu
Spread Trải phổ chuỗi trực tiếp
viii
Digital Kênh thuê bao số tốc độ cao
HDSL
High-bit-rate
Subscriber Line
ICI
Inter-Carrier Interference
Nhiễu liên sóng mang
IDFT
Inverse DFT
Biến đổi Fourier rời rạc ngược
IEEE
Institute of Electrical and Viện kỹ thuật điện và điện tử
Electronics Engineers
IFFT
Invert Fast Fourier transform
Biến đổi Fourier ngược
IP
Internet Protocol
Giao thức Internet
ISI
Intersymbol Interference
Nhiễu giữa các ký hiệu
ISMA
Inhibit Sense Multiple Access
Đa truy cập nhận biết ngăn chặn
LAN
Local Area Network
Mạng cục bộ
MAC
Media Access Control
Điều khiển truy cập môi trường
MACA
Multiple Access with Collision Giao thức đa truy cập tránh xung đột
Avoidance
MACAW Multiple Access with Collision Giao thức đa truy cập tránh xung đột
Avoidance for Wireless
cho mạng không dây
and Nhiều đầu vào và nhiều đầu ra
MIMO
Multiple-Input
Multiple-Output
NC
Network Coding
Mã hóa mạng
NP
Nondeterministic Polynomial
Đa thức bất định
OFDM
Orthogonal
Frequency Ghép kênh phân chia theo tần số trực
Division Multiplexing
giao
OMS
Opportunistic
Scheduling
PAPR
Peak to Average Power Ratio
Tỷ số công suất đỉnh trên công suất
trung bình
PLL
Phase Lock Loop
Vòng khóa pha
Multipath Cơ hội lập lịch đa đường
ix
Mã mạng lớp vật lý
PNC
Physical Network Coding
PRMA
Packet Reservation Multiple Đa truy cập đặt trước gói
Access
PSAM
Pilot
Signal
Modulation
PSK
Phase Shift Keying
QAM
Quadrature
Modulation
QoS
Quality of Service
Chất lượng dịch vụ
RF
Radio frequency
Tần số vô tuyến
RFID
Radio
Identification
RSVP
Resource Reservation Protocol Giao thức đinh
̣ trước nguồ n tài nguyên
RTT
Round-Trip Time
SINR
Signal to Interference plus Tỷ lệ tín hiệu với nhiễu cộng tạp âm
Noise Ratio
TCP
Transmission Control Protocol Giao thức điều khiển truyền thông tin
TDM
Time-Division Multiplexing
TDMA
Time
Division
Access
UWB
Ultra-Wide Band
Băng siêu rộng
VCO
Voltage Controlled Oscillator
Bộ dao động điều khiển bằng điện áp
VDSL
Very-high-bit-rate
Subscriber Line
WAN
Wide Area Network
Assisted Điều chế dùng tín hiệu dẫn đường
Điều chế số theo pha tín hiệu
Amplitude Điều chế số theo biên độ tín hiệu
Frequency Nhận biết tần số vô tuyến
Thời gian đi hai chiều
Ghép kênh phân chia thời gian
Multiple Đa truy cập theo phân chia thời gian
Digital Kênh thuê bao số tốc độ rất cao
Mạng diện rộng
x
Danh mục các bảng
Bảng 1.1 Ánh xạ mã mạng lớp vật lý (PNC mapping) của các thành phần đồng pha ..18
Bảng 2.1: Bảng so sánh các giao thức định tuyến trong mạng MANET ......................33
xi
Danh mục các hình vẽ, đồ thị
Hình 1.1 Sự phát triển của mạng không dây ...................................................................3
Hình 1.2 Phân loại mạng không dây ...............................................................................4
Hình 1.3 Ví dụ đơn giản sử dụng mã hóa mạng nhằm nâng cao thông lượng. ...............5
Hình 1.4 Giải mã các mã mạng thực hiện phép khử Gauss với m > n gói tin mã hóa đã
nhận. ................................................................................................................................7
Hình 1.5 Ví dụ đơn giản cho thấy mã hóa mạng cải thiện độ ổn định. Điểm truy cập có
thể truyền các tổ hợp tuyến tính đã được mã hóa của Pa và Pb tới A và B, làm đơn giản
hóa hoạt động của mạng. .................................................................................................9
Hình 1.6 Mã hóa mạng chống lại vấn đề mất gói..........................................................10
Hình 1.7 Kiến trúc mắt lưới điển hình. Các router hình thành các tuyến vô tuyến nhiều
chặng tới gateway kết nối tới Internet. Client kết nối với router vô tuyến gần nhất. .... 11
Hình 1.8 Mô hình đơn giản 03 nút trong mạng không dây ...........................................14
Hình 1.9 Mô hình truyền không sử dụng mã mạng .......................................................15
Hình 1.10 Mô hình mã mạng .........................................................................................16
Hình 1.11 Mô hình mã mạng lớp vật lý.........................................................................16
Hình 1.12: So sánh tỷ lệ lỗi bit của mô hình liên kết QPSK điểm – điểm (QPSK), kết nối
sử dụng mã mạng (SNC) và kết nối sử dụng mã mạng lớp vật lý (PNC)[24] ..............19
Hình 1.13: Lập lịch mã mạng lớp vật lý trong chuỗi tuyến tính. ..................................23
Hình 2.1: Mô hình mạng MobileAdhoc Network (MANET) .......................................24
Hình 2.2: Biểu đồ mạng MANET .................................................................................25
Hình 2.3: Các chuẩn giao thức IEEE 802 và mô hình OSI ...........................................26
Hình 2.4: Mô hình kiến trúc theo chuẩn 802.11 ............................................................27
Hình 2.5: Bảng phân loại các giao thức định tuyến ......................................................29
Hình 2.6: Quá trình khám phá tuyến trong AODV .......................................................30
Hình 2.7: Định tuyến nguồn động (DSR) ......................................................................32
Hình 2.8: Sơ đồ quá trình phát tin .................................................................................34
Hình 2.9: Phổ của tín hiệu FDM và OFDM ..................................................................34
Hình 2.10: a.Tác động của nhiễu đối với hệ thống đơn sóng mang ..............................34
b.Tác động của nhiễu đến hệ thống đa sóng mang ........................................................35
Hình 2.11: Phổ của các sóng mang trực giao ................................................................36
Hình 2.12: Phổ của bốn sóng mang trực giao ...............................................................37
xii
Hình 2.13: Phổ của bốn sóng mang không trực giao ....................................................38
Hình 2.14: Ảnh hưởng của ISI ......................................................................................38
Hình 2.15: Sơ đồ một hệ thống OFDM .........................................................................42
Hình 3.1. Mô hình mạng MANET một chiều ...............................................................47
Hình 3.2: Mô hình và khoảng cách các trạm trong không gian ....................................48
Hình 3.3: Giới hạn trong mô hình truyền theo lưu lượng 1 chiều .................................50
Hình 3.4. Giới hạn mạng MANET sử dụng mã mạng ..................................................53
Hình 3.5: Cơ chế truyền của mạng MANET dựa trên lưu lượng ..................................55
Hình 3.6: Cơ chế truyền của phương pháp mã mạng ....................................................56
Hình 3.7 Cơ chế truyền của phương pháp mã mạng lớp vật lý .....................................56
Hình 3.8. Mô hình mạng MANET hai chiều .................................................................58
Hình 3.9: Nhiễu giữa các điểm nhận của cùng một đường truyền và của đường truyền
khác trong mô hình MANET 2 chiều sử dụng mã mạng ..............................................59
Hình 3.10: Dung lượng cắt trong mạng MANET .........................................................60
Hình 3.11: Tính chất hình học của đường truyền qua điểm cắt ....................................61
Hình 3.12. Điểm phát và nhận ở một phía so với đường cắt .........................................62
Hình: 3.13. Điểm phát và nhận ở 2 phía khác nhau của đường cắt R2 ( y) R1 ( y) ........62
Hình 3.14. Điểm phát và nhận ở 2 phía khác nhau của đường cắt R2 ( y) R1 ( y) .........63
Hình 3.15: Giới hạn dưới dung lượng mạng MANET 2 chiều .....................................63
Hình 3.16. So sánh giới hạn dưới trong mạng MANET ...............................................66
1
MỞ ĐẦU
Mã mạng lớp vật lý là một công nghệ mới và đã được nghiên cứu trong rất nhiều
công trình nghiên cứu. Trong mô hình sử dụng mã mạng lớp vật lý, hệ thống có thể cải
thiện dung lượng kênh, giảm độ trễ và bảo mật dữ liệu.
Mục đích của luận văn là xem xét khả năng ứng dụng mã mạng lớp vật lý trong
mạng di động adhoc không dây (MANET). Đặc biệt luận văn tập trung vào dung lượng
kênh của mạng MANET sử dụng OFDM. Nội dung nghiên cứu trên mạng MANET sử
dụng mã mạng lớp vật lý, dung lượng kênh sẽ bị ảnh hưởng thế nào, và so sánh với các
nghiên cứu trước đây để đưa ra giới hạn chặt hơn. Luận văn so sánh dung lượng của
mạng MANET truyền theo lưu lượng, mạng MANET sử dụng mã mạng, và mạng
MANET sử dụng mã mạng lớp vật lý. Các nghiên cứu theo tính toán và mô phỏng đã chỉ
ra rằng trong mạng MANET sử dụng mã mạng lớp vật lý dung lượng kênh truyền có thể
cải thiện, ngoài ra khi sử dụng mã mạng lớp vật lý cho độ trễ giảm và tăng cường bảo
mật. Luận văn chỉ ra rằng với mạng MANET dùng mã mạng lớp vật lý, dung lượng kênh
được cải thiện so với các mạng MANET truyền dẫn theo lưu lượng và mạng MANET sử
dụng mã mạng lớp mạng. Kết luận trong luận văn là mạng MANET sử dụng mã mạng
lớp vật lý là một lựa chọn tốt để truyền thông tin qua mạng di động không dây Adhoc.
Đặc biệt khi mạng sử dụng công nghệ điều chế ghép kênh phân chia tần số trực giao
OFDM.
Nội dung bố cục của luận văn như sau:
Chƣơng 1: Tổng quan chung. Giới thiệu tổng quan về mạng không dây, mã hóa
mạng và mã hóa mạng lớp vật lý. Mục 1.1 giới thiệu tổng quan mạng không dây. Mục
1.2 nói về mã hóa mạng. Tổng quan kiến trúc, các vấn đề gặp phải và lợi ích của mã
mạng. Mục 1.3 thảo luận kiến trúc và cách xây dựng mạng lưới không dây hiện tại. Mục
1.4 tập trung vào mã mạng lớp vật lý và các vấn đề gặp phải khi áp dụng mã mạng lớp
vật lý vào trong thực tế.
Chƣơng 2: Mạng di động không dây adhoc dựa trên OFDM. Giới thiệu mạng
không dây adhoc. Đặc điểm và ứng dụng của mạng không dây adhoc. Đồng thời luận
văn cũng mô tả kỹ thuật ghép kênh phân chia tần số trực giao OFDM và các ưu điểm khi
sử dụng OFDM trong mạng Adhoc.
Chƣơng 3: Ảnh hƣởng của mã mạng lớp vật lý tới dung lƣợng kênh. Đầu tiên
chương giới thiệu về dung lượng kênh trong mạng không dây. Tiếp đó chương phân tích
dung lượng kênh trong các mạng MANET: Truyền thống, sử dụng mã mạng lớp mạng,
và sử dụng mã mạng lớp vật lý. Chương này sẽ giải quyết các vấn đề với dung lượng
kênh trong mạng MANET một chiều, mạng hai chiều và có những đóng góp dưới đây:
+ Phân tích dung lượng mạng MANET một chiều. Chương này trình bày dung
lượng của hệ thống trong không gian một chiều và đưa ra các kết quả về dung lượng
kênh trong các trường hợp mạng MANET truyền theo lưu lượng, sử dụng mã mạng, và
2
sử dụng mã mạng lớp vật lý. Dựa vào kết quả cho ta thấy với cùng một điều kiện truyền
thông như nhau, mạng MANET dùng mã mạng lớp vật lý có thể cải thiện dung lượng
kênh truyền. Ngoài ra với mã mạng lớp vật lý, độ trễ và tính bảo mật được nâng cao.
+ Phân tích dung lượng kênh không dây ngẫu nhiên trong không gian 2 chiều. Giới
hạn dung lượng kênh của mạng MANET truyền theo lưu lượng, mạng MANET sử dụng
mã mạng lớp mạng và mạng MANET sử dụng mã mạng lớp vật lý. Xác định giới hạn
trên, giới hạn dưới theo 3 mô hình đó
+ Đánh giá kết quả thu được. Kết quả này được tóm tắt như sau:
-
Khi sử dụng mã mạng lớp vật lý, dung lượng kênh được cải thiện khi truyền
trong mạng MANET.
-
Sử dụng mã mạng lớp vật lý cho độ trễ tín hiệu truyền thấp hơn và tính bảo mật
cao hơn so với các mô hình mạng MANET truyền theo lưu lượng và mạng
MANET sử dụng mã mạng.
3
Chƣơng 1. TỔNG QUAN CHUNG
1.1. Mạng không dây
1.1.1. Tổng quan
Mạng không dây được đánh dấu mốc hình thành từ những năm 1887 khi Heinrich
Rudolf Hertz chứng minh được thuyết điện từ Maxwell thông qua thực nghiệm. Từ đó
đến nay các nhà nghiên cứu đã cho ra đời hàng loạt phát minh sáng chế góp phần đưa
công nghệ mạng không dây không ngừng cải tiến vượt trội về tốc độ truyền nhận dữ liệu.
Những năm gần đây nền công nghiệp không dây và di động tăng trưởng mạnh mẽ cả về
mặt công nghệ lẫn sự bùng nổ ngày càng nhiều các thiết bị di động, hứa hẹn một kỷ
nguyên truyền thông số nở rộ trên nền các mạng không dây và di động. Sự phát triển này
được minh họa trên Hình 1.1 dưới đây.
Hình 1.1 Sự phát triển của mạng không dây
1.1.2. Các mô hình mạng không dây
Có 3 loại mô hình mạng không dây như sau:
- Mạng Infrastructure
- Mạng adhoc
- Mạng Hybrid
Tuy nhiên hiện nay có hai loại mạng đang được phát triển rộng rãi:
- Mạng Ad-hoc : Chỉ mạng (peer-to-peer) không dây ngang hàng. Mỗi thiết bị trong
mạng giao tiếp trực tiếp với nhau mà không dùng đến các thiết bị điều khiển truye
cập (Wireless Access Point - AP) và các bộ định tuyến (Wireless Router).
- Mạng Infrastructure : Các thiết bị trong hệ thống mạng sử dụng một hoặc nhiều các
thiết bị AP để thực hiện các hoạt động trao đổi dữ liệu với nhau và các hoạt động
khác. Trong chế độ này, mạng không dây được điều khiển bởi một AP không dây.
Các điểm truy cập này có chức năng như một cảnh sát giao thông trung tâm cho các
tín hiệu, vì thế nó cung cấp khả năng kết nối đáng tin cậy hơn mạng adhoc. Điểm truy
4
nhập cũng cho phép chia sẻ kết nối internet mà không cần tới qua một máy tính nào
khác.
1.1.3. Phân loại các mạng không dây theo khoảng cách vật lý
Hình 1.2 Phân loại mạng không dây
- WPAN : Mạng vô tuyến cá nhân. Nhóm này bao gồm các công nghệ vô tuyến có
vùng phủ nhỏ tầm vài mét đến hàng chục mét tối đa. Các công nghệ này phục vụ mục
đích nối kết các thiết bị ngoại vi như máy in, bàn phím, chuột, đĩa cứng, khóa USB,
đồng hồ,...với điện thoại di động, máy tính. Các công nghệ trong nhóm này bao gồm:
Bluetooth, Wibree, ZigBee, UWB, Wireless USB, EnOcean,... Đa phần các công
nghệ này được chuẩn hóa bởi IEEE, 802.15 và còn được biết đến với tên như IEEE
802.15.4 hay IEEE 802.15.3 ...
- WLAN : mạng vô tuyến cục bộ. Nhóm này bao gồm các công nghệ có vùng phủ
tầm vài trăm mét. Nổi bật là công nghệ Wifi với nhiều chuẩn mở rộng khác nhau
thuộc gia đình 802.11 a/b/g/h/i/... Công nghệ Wifi đã đạt được những thành công to
lớn trong những năm qua. Bên cạnh WiFi thì còn một cái tên ít nghe đến là
HiperLAN và HiperLAN2, đối thủ cạnh tranh của Wifi được chuẩn hóa bởi ETSI.
- WMAN: Mạng vô tuyến đô thị. Đại diện tiêu biểu của nhóm này chính là WiMAX.
Ngoài ra còn có công nghệ băng rộng BWMA 802.20. Vùng phủ sóng của nó sẽ ở
khoảng 4-5km.
- WWAN : Mạng vô tuyến diện rộng: Nhóm này bao gồm các công nghệ mạng
thông tin di động như UMTS/GSM/CDMA2000... Vùng phủ của nó cũng tầm vài
km đến tầm chục km.
- WRAN: Mạng vô tuyến khu vực. Nhóm này đại diện là công nghệ 802.22 đang
được nghiên cứu và phát triển bởi IEEE. Vùng phủ có nó sẽ lên tầm 40-100km. Mục
đích là mang công nghệ truyền thông đến các vùng xa xôi hẻo lánh, khó triển khai
5
các công nghệ khác. Nó sẽ sử dụng băng tần mà TV analog không dùng để đạt được
vùng phủ rộng.
1.2. Mã hóa mạng
Lý thuyết thông tin và mạng máy tính có rất nhiều phần liên quan, tương hỗ, bổ túc
cho nhau. Trong khoảng 5 năm trở lại đây, một nhánh nghiên cứu cực kỳ thú vị đang
càng lúc càng thu hút nhiều nhà nghiên cứu từ cả lý thuyết thông tin (đặc biệt là lý thuyết
mã) tới thực tế. Tên gọi của nhánh nghiên cứu mới này là mã hóa mạng (network
coding). Khởi đầu từ bài báo [1], đến nay network coding đã có ứng dụng ở rất nhiều nơi
trong nhiều lĩnh vực khác nhau. Để hiểu rõ hơn về mã mạng, xét mô hình mạng Hình 1.3
ở dưới đây
Hình 1.3 Ví dụ đơn giản sử dụng mã hóa mạng nhằm nâng cao thông lượng.
Nguồn S1 cần truyền gói P1 tới cả D1 và D2, và nguồn S2 cần truyền gói P2 cũng tới
D1, D2. Giả sử rằng tất cả đường truyền có khả năng truyền một gói trên giây. Nếu router
R1 và R2 chỉ chuyển tiếp gói tin chúng nhận được cùng một lúc, đường truyền ở giữa sẽ
bị tắc nghẽn. Tại mọi thời điểm, hai router hoặc là gửi P1 tới D2 hoặc P2 tới D1.
Ngược lại, nếu router gửi lên đường truyền gói tin P1⊕P2 (hoặc bất kỳ tổ hợp
tuyến tính nào của P1 và P2) xem Hình 1.3, cả hai đích sẽ nhận được hai gói tương ứng.
D1 sẽ có được P2 sau khi thực hiện phép toán XOR gói P1 (nhận được trực tiếp từ S1) với
P1⊕P2 và tương tự D2 sẽ tái tạo được P1. Do đó, mã hóa mạng có thể đạt tới thông lượng
multicast của 2 gói trên giây, Phương pháp này tốt hơn phương pháp định tuyến chỉ đạt
được tối đa là 1,5 gói trên giây.
Nếu trạm D1 nhận P1 trực tiếp với xác suất lỗi bằng 1 và nhận được P1⊕P2 với xác
suất lỗi 2 thì tổng hợp dữ liệu sẽ có P1 với xác xuất lỗi thấp hơn và bằng 1(1 - 2) + 2(1
- 1).
Mã hóa mạng tuyến tính là tương tự với ví dụ này, chỉ thay thế phép toán XOR bởi
phép tuyến tính khác. Điều này tạo nên sự linh hoạt trong cách thức mà các gói tin kết
hợp với nhau. Do đó, router thay vì chỉ chuyển tiếp gói tin thì sẽ tạo ra tổ hợp tuyến tính
6
của các gói tin đến tạo ra gói tin mã hóa rồi mới gửi đi. Chúng ta sẽ miêu tả ngắn gọn quá
trình mã hóa và giải mã trong những mục sau.
1.2.1. Mã hóa
Giả sử mỗi gói có L bit. Khi các gói có kích thước khác nhau kết hợp với nhau, thì
gói nào có ít bit hơn sẽ được thêm vào các bit 0. Ta xem s bit liên tiếp nhau như là một ký
tự của tập hữu hạn F2 , mỗi gói là một véc tơ của L/s ký tự. Với mã hóa tuyến tính, các
s
gói tin lối ra là tổ hợp tuyến tính của các gói ban đầu, ở đây cộng và nhân được thực hiện
trên trường hữu hạn F2 .
s
Gọi P1, P2, …, Pn là n gói tin ban đầu từ một hoặc nhiều nguồn khác nhau. Với mã
hóa tuyến tính, mỗi gói tin X được xem như một véc tơ của các hệ số g g (1), g (2)...g (n)
trong trường F2 gọi là véc tơ mã. Véc tơ mã chỉ ra cách gói tin X đạt được từ các gói tin
s
n
nguồn: X g (i ) Pi
(1.1)
i 1
Tổng này được xác định tại mọi vị trí ký tự, X (k ) i 1 g (i) Pi (k ) với Pi(k) và X(k)
n
là ký tự thứ k’ của Pi và X. Trong ví dụ ở Hình 1.1, trường F2 ={0,1}, một ký tự là một bit
và biến đổi tuyến tính gửi bởi R1 sau khi nhận được P1 và P2 là P1⊕ P2. Véc tơ mã được
mang trong tiêu đề của gói tin đã mã hóa X. Véc tơ được sử dụng tại bên nhận để giải mã
dữ liệu.
Mã hóa có thể được thực hiện đệ quy. Xem xét một nút đã nhận và lưu trữ một tập
các gói tin mã hóa ( g1 , X1 ),...,( g m , X m ) với g j là véc tơ mã hóa của gói Xj. Nút này có
thể lại tạo ra các gói tin mã hóa mới ( g ' , X ' ) bằng cách lựa chọn một tập các hệ số
m
h h(1),..., h(m) và tính toán tổ hợp tuyến tính X ' j 1 h( j ) X j . Véc tơ mã g ' không
bằng véc tơ mã h vì các hệ số là không liên quan tới các gói ban đầu P1, P2,…, Pn;
m
nhưng với một vài biến đổi số học ta có thể thấy g ' được cho bởi g ' j 1 h( j ) g i .
Phương trình này có thể lặp lại tại vài nút trong mạng.
1.2.2. Giải mã
Như đã nói ở trên, mỗi gói tin mã hóa là tổ hợp tuyến tính của các gói ban đầu. Khi
đích nhận được các gói tin đã mã hóa X1, X2, …, Xn với các véc tơ mã tương ứng
g1 ,..., g m . Vậy nên, để thu được các gói tin gốc đã truyền, cần phải giải hệ phương trình:
n
X j g j (i) Pi
(1.2)
i 1
Ở đây ẩn là tập các gói tin ban đầu Pi. Đây là hệ phương trình tuyến tính với m
phương trình và n ẩn. Khi m ≥ n và có ít nhất n tổ hợp độc lập tuyến tính, thì hệ phương
trình có nghiệm và các gói tin ban đầu có thể được giải mã. Do đó, mạng phải đảm bảo
7
truyền ít nhất n gói độc lập tuyến tính tới đích. Điều này có thể dễ dàng thực hiện, như sẽ
xem xét ở mục sau.
1.2.3. Cách lựa chọn tổ hợp tuyến tính
Vấn đề của thiết kế mã mạng là lựa chọn tổ hợp tuyến tính mà mỗi nút mạng thực
hiện để bảo đảm nút đích nhận được ít nhất n tổ hợp độc lập tuyến tính, từ đó có thể giải
mã gói tin ban đầu. Một thuật toán đơn giản là để mỗi nút lựa chọn theo biến ngẫu nhiên
đều các hệ số trong trường F2 , theo kiểu độc lập và không tập trung [2]. Với mã mạng
s
ngẫu nhiên sẽ có xác suất chắc chắn của lựa chọn tổ hợp độc lập tuyến tính [2]. Xác suất
này liên quan tới kích thước của trường 2s. Kết quả mô phỏng cho thấy thậm chí với kích
thước trường là nhỏ (ví dụ, s = 8) xác suất này là rất nhỏ.
Chúng ta có thể sử dụng thuật toán xác định để thiết kế mã mạng. Thuật toán đa
thức thời gian cho multicast, xem xét mỗi nút mạng và quyết định tổ hợp tuyến tính cho
mỗi nút thực hiện. Vì mỗi nút sử dụng hệ số tuyến tính xác định, các gói tin không cần
mang véc tơ mã. Cũng có những thuật toán phi tập trung xác định dùng để hạn chế cấu
hình mạng.
1.2.4. Các vấn đề thực tế với mã mạng
1.2.4.1. Giải mã
Việc giải mã yêu cầu giải một hệ các phương trình tuyến tính, có thể thực hiện sử
dụng phép khử Gauss. Một nút lưu các véc tơ mã nó nhận được cũng như các gói tương
ứng, theo từng hàng tạo thành ma trận giải mã. Đầu tiên, ma trận này không có phương
trình nào. Khi nhận một gói tin mã hóa, nó được thêm vào thành hàng cuối cùng trong
ma trận giải mã và phép khử Gauss được thực hiện tới dạng ma trận tam giác.
Một gói tin nhận được gọi là mới nếu nó làm tăng hạng của ma trận. Nếu một gói
tin là không mới, nó sẽ bị biến đổi thành một hàng toàn 0 bởi phép khử Gauss và bị loại
bỏ. Khi một phần véc tơ mã của ma trận gồm một hàng có dạng ei ( véc tơ đơn vị với duy
nhất một tại các vị trí thứ i’ ), khi này X chính là gói tin ban đầu Pi. Điều này xảy ra khi
nhận được n véc tơ mã độc lập tuyến tính. Chú ý là giải mã không cần thực hiện tại tất cả
các nút của mạng mà chỉ tại nơi nhận. Sơ đồ Hình 1.4 chỉ ra cách phép khử Gauss biến
đổi m gói tin mã hóa đã nhận thành n gói tin ban đầu.
Hình 1.4 Giải mã các mã mạng thực hiện phép khử Gauss với m > n gói tin mã hóa đã
nhận.
- Xem thêm -