Tài liệu ảnh hưởng của mã mạng lớp vật lý tới dư lượng kênh trong mạng ofdm

ĐẠ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.