hoatuyet_babydautay93
New Member
Luận văn: Mã hóa mạng không dây sử dụng giao thức ALOHA : Luận văn ThS. Kỹ thuật điện tử - viễn thông: 60 52 70
Nhà xuất bản: Đại học Công nghệ
Ngày: 2013
Chủ đề: Mã hóa
Mạng không dây
Giao thức Aloha
Kỹ thuật điện tử
Miêu tả: Tổng quan về mã hóa mạng và thiết kế mạng lưới không dây: giới thiệu về mã hóa mạng ; Lợi ích của mã hóa mạng; 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. Giới thiệu giao thức đa truy cập: Giao thức đa truy cập không tranh chấp và Giao thức đa truy cập tranh chấp; Nguyên tắc hoạt động của giao thức ALOHA và ảnh hưởng của hiệu ứng lấn át; Chương trình và kết quả mô phỏng thuật toán pure-ALOHA và slot-ALOHA. Trình bày thiết kế, thực hiện và đánh giá hiệu năng dựa trên mô hình COPE sử dụng giao thức ALOHA, một kiến trúc mới cho truyền tin không dây sử dụng mã hóa mạng ở mức gói để cải thiện thông lượng mạng vô tuyến. Kiến trúc COPE chèn thêm các mã đệm giữa lớp IP và lớp MAC, từ đó có thể truyền nhiều gói tin trong cùng một lần truyền. Tiếp theo trình bày giao thức ALOHA mã hóa. Tập trung vào một topo mạng hình sao, trong đó các nút bên ngoài trao đổi dữ liệu với nhau thông qua nút trung tâm. Một câu hỏi là có bao nhiêu thông lượng tăng lên bằng cách áp dụng mã hóa mạng tại nút trung tâm. Bằng cách phân tích topo mạng hình sao, có thể kiểm soát nút tắc nghẽn trong một mạng multihop không dây, nơi mà rất
Electronic Resources
Luận văn ThS. Kỹ thuật điện tử -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2013
LỜI CAM ĐOAN.............................................................................................................i
M C L C ..................................................................................................................... iii
Danh mục các ký hiệu và chữ viết tắt.............................................................................vi
Danh mục các bảng.........................................................................................................ix
Danh mục các hình vẽ, đồ thị ..........................................................................................x
MỞ ĐẦU .........................................................................................................................1
hương 1. NHỮNG VẤN ĐỀ Ơ BẢN ......................................................................4
1.1. Mã hóa mạng....................................................................................................4
1.1.1. Mã hóa .....................................................................................................4
1.1.2. Giải mã ....................................................................................................5
1.1.3. Cách lựa chọn tổ hợp tuyến tính..............................................................6
1.1.4. Các vấn đề thực tế ...................................................................................6
1.1.4.1. Giải mã ....................................................................................................6
1.1.4.2. Khối hóa ..................................................................................................7
1.1.4.3. Các phép toán trường hữu hạn ................................................................7
1.2. Lợi ích của mã hóa mạng .................................................................................7
1.2.1. Tăng cường thông lượng .........................................................................7
1.2.2. Sự ổn định và thích nghi..........................................................................8
1.2.2.1. Đơn giản hóa phân phối nội dung ...........................................................8
1.2.2.2. Chống lại mất gói ....................................................................................9
1.3. Mạng không dây có topo hình lưới (mesh) ......................................................9
1.3.1. Lớp vật lý...............................................................................................10
1.3.2. Lớp liên kết dữ liệu ...............................................................................11
1.3.3. Lớp mạng...............................................................................................11
1.3.3.1. Giao thức định tuyến với metric khác nhau ..........................................11
1.3.3.2. Định tuyến đa đường .............................................................................12
1.3.3.3. Định tuyến theo vùng địa lý ..................................................................12
1.3.4. Lớp giao vận..........................................................................................12
hương 2. KỸ THUẬT ĐA TRUY ẬP...................................................................14
2.1. Phân loại các giao thức đa truy cập................................................................14
2.1.1. Giao thức đa truy cập không tranh chấp (lập lịch) ................................15
2.1.2. Giao thức đa truy cập tranh chấp (ngẫu nhiên) .....................................16iv
2.2. Giao thức ALOHA .........................................................................................16
2.2.1. Pure-ALOHA ........................................................................................16
2.2.2. Slot-ALOHA .........................................................................................18
2.3. Mô phỏng giao thức ALOHA ........................................................................20
2.3.1. Mô hình hóa hệ thống thông tin gói ......................................................20
2.3.1.1. Hiệu ứng lấn át ......................................................................................20
2.3.1.2. Lưu lượng yêu cầu.................................................................................20
2.3.1.3. Thông lượng ..........................................................................................21
2.3.1.4. Trễ truyền trung bình.............................................................................21
2.3.2. Cấu hình mô phỏng cơ bản....................................................................21
2.4. Mô phỏng thuật toán ALOHA........................................................................22
2.4.1. Chương trình và kết quả mô phỏng thuật toán pure-ALOHA ..............22
2.4.1.1. Tham số và cấu trúc chương trình.........................................................22
2.4.1.2. Kết quả mô phỏng .................................................................................24
2.4.2. Chương trình và kết quả mô phỏng thuật toán slot-ALOHA................25
2.4.2.1. Tham số và cấu trúc chương trình.........................................................25
2.4.2.2. Kết quả mô phỏng .................................................................................25
hương 3: Ã HÓA ẠNG KHÔNG DÂY SỬ D NG GIAO THỨ A OHA27
3.1. Thiết kế mức cao của COPE [4, 31] ..............................................................27
3.1.1. Nghe ......................................................................................................28
3.1.2. Mã hóa ...................................................................................................29
3.1.3. Học ........................................................................................................31
3.2. Kiến trúc hệ thống [4, 31] ..............................................................................32
3.2.1. Mục đích thiết kế...................................................................................32
3.2.2. Mô đun Mã hóa/ Giải mã ......................................................................32
3.2.2.1. Cơ hội mã hóa........................................................................................32
3.2.2.2. Mã hóa cực đại xác suất giải mã ...........................................................33
3.2.2.3. Mã hóa các gói tin có cùng độ dài.........................................................33
3.2.2.4. Cấu trúc dữ liệu và thuật toán mã hóa...................................................34
3.2.2.5. Thuật toán giải mã.................................................................................35
3.2.3. Độ tin cậy ..............................................................................................35
3.2.3.1. Độ tin cậy của 802.11 ............................................................................36
3.2.3.2. Đặt vấn đề..............................................................................................36
3.2.3.3. Giải pháp ...............................................................................................36
3.2.3.4. Độ tin cậy lớp giao vận .........................................................................37
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiv
3.2.4. Mô đun lắng nghe..................................................................................38
3.2.5. Mô đun học............................................................................................38
3.3. Chi tiết thực hiện [4, 31] ................................................................................39
3.3.1. Định dạng gói tin...................................................................................39
3.3.1.1. ID của gói tin gốc mã hóa .....................................................................39
3.3.1.2. Thông báo nhận .....................................................................................40
3.3.1.3. Biểu diễn ACK bất đồng bộ ngắn gọn và đơn giản...............................40
3.3.2. Điều khiển luồng ...................................................................................40
3.4. Hiệu quả của COPE [31]................................................................................41
3.4.1. Hiệu suất mã hóa ...................................................................................41
3.4.2. Hiệu suất mã hóa + MAC......................................................................43
3.5. Giới thiệu giao thức ALOHA mã hóa ............................................................45
3.6. Mô hình hệ thống ...........................................................................................46
3.7. Phân tích thông lượng ....................................................................................48
3.7.1. Slot-ALOHA .........................................................................................49
3.7.2. ALOHA mã hóa.....................................................................................49
3.7.3. Điều kiện ổn định ..................................................................................50
3.8. Kết quả số liệu................................................................................................51
KẾT UẬN ..................................................................................................................55
T I I U THA KHẢO...........................................................................................56
PH .....................................................................................................................59vi
Danh mục các ký hiệu và chữ viết tắt
Kí hiệu Viết đầy đủ Ý nghĩa
ACK Acknowledgment Bản tin báo nhận
API Application Programming
Interface
Giao diện lập trình ứng dụng
ARQ Automatic Repeat Query Tự động lặp lại truy vấn
CMAPS Conflict Maps Bản đồ phân phối
COPE Kiến trúc mã hóa mạng mức gói tin. Nó
chèn thêm lớp mã hóa ở giữa lớp mạng
và lớp liên kết
CSMA Carrier Sense Multiple
Access
Đa truy cập nhận biết sóng mang
CSMA/CA Carrier Sense Multiple
Access with Collision
Avoidance
Đa truy cập nhận biết sóng mang phát
hiện xung đột
C/N Carrier to Noise Tỷ số giữa công suất tín hiệu trên công
suất nhiễu
DSSS Direct Sequence Spread
Spectrum
Trải phổ chuỗi trực tiếp
ETX Expected Transmission
Count
Số lượt dự kiến sẽ truyền
ExOR Tích hợp định tuyến và giao thức MAC
làm tăng thông lượng chuyển luồng
unicast lớn trong các mạng multihop
không dây
FDMA Frequency Division
Multiple Access
Giao thức đa truy cập phân chia theo tần
số
FEC Forward Error Correction Sửa lỗi chuyển tiếp
FIFO First In First Out Vào trước ra trước
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phivii
GSM Global System for Mobile
communications Hệ thống thông tin di động toàn cầu
IEEE Institute of Electrical and
Electronics Engineers
Viện kỹ thuật điện và điện tử
IETF Internet Engineering Task
Force
Một tổ chức Viễn thông quốc tế. Lực
lượng chuyên phụ trách kỹ thuật kết nối
mạng.
IP Internet Protocol Giao thức Internet
ISMA Inhibit Sense Multiple
Access
Đa truy cập nhận biết ngăn chặn
ITU-T International
Telecommunication
Union-Telecommunication
Standardization Sector
Hiệp hội viễn thông quốc tế - Tổ chức
chuẩn chuẩn hóa các kỹ thuật Viễn
thông.
LAN Local Area Network Mạng cục bộ
MAC Media Access Control Điều khiển truy cập môi trường
MIMO Multiple-Input and
Multiple-Output
Nhiều đầu vào và nhiều đầu ra
MORE Giao thức định tuyến cơ hội MAC độc
lập
NP Nondeterministic
Polynomial
Đa thức bất định
OFDM Orthogonal Frequency
Division Multiplexing
Đa phân chia theo tần số trực giao
OMS Opportunistic Multipath
Scheduling
Cơ hội lập lịch đa đường
PRMA Packet Reservation
Multiple Access
Đa truy cập đặt trước gói
QoS Quality of Service Chất lượng dịch vụ
RFID Radio Frequency
Identification
Nhận biết tần số vô tuyến
RSVP Resource Reservation Giao thức định trước nguồn tài nguyênviii
Protocol
RTT Round-Trip Time Thời gian đi hai chiều
SINR Signal to Interference plus
Noise Ratio
Tỷ lệ tín hiệu với nhiễu cộng ồn
TDM Time Division
Multiplexing
Ghép kênh phân chia theo thời gian
TDMA Time Division Multiple
Access
Giao thức đa truy cập phân chia theo
thời gian
TCP Transmission Control
Protocol
Giao thức điều khiển truyền thông tin
UDP User Datagram Protocol Giao thức Datagram người dùng
UWB Ultra-Wide Band Băng siêu rộng
WAN Wide Area Network Mạng diện rộng
wifi Wireless Fidelity Mạng không dây Wifi
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiix
Danh mục các bảng
Bảng 2.1 Điều kiện mô phỏng.......................................................................................23
Bảng 3.1 Định nghĩa các thuật ngữ sử dụng trong chương này. ...................................28
Bảng 3.2 Hiệu suất theo lý thuyết cho một số topo cơ bản ...........................................45x
Danh mục các hình vẽ, đồ thị
Hình 1.1 Ví dụ đơn giản sử dụng mã hóa mạng nhằm nâng cao thông lượng................4
Hình 1.2 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. ................................................................................................................................6
Hình 1.3 Mã hóa mạng cải thiện độ ổn định. Access point có thể truyền các tổ hợp tuyến
tính của Pa và Pb cho tới khi cả A và B mã hóa được, làm đơn giản hóa hoạt động của
mạng. ...............................................................................................................................8
Hình 1.4 Mã hóa mạng chống lại vấn đề mất gói. A cần gửi gói tin tới C qua router B.
Đường truyền AB và BC có xác suất mất gói là εAB và εBC tương ứng. ..........................9
Hình 1.5 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
hop 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. .......10
Hình 2.1(a) TDMA và (b) FDMA .................................................................................15
Hình 2.2 pure-ALOHA..................................................................................................17
Hình 2.3 Sự xung đột giữa những gói tin trong hệ thống pure-ALOHA ......................17
Hình 2.4 slot-ALOHA ...................................................................................................18
Hình 2.5 Tranh chấp gói trong hệ thống slot-ALOHA..................................................18
Hình 2.6 Xung đột giữa những gói tin truyền đi ...........................................................20
Hình 2.7 Cấu hình mô phỏng máy tính cơ bản..............................................................22
Hình 2.8 Lưu lượng yêu cầu và thông lượng của pure-ALOHA ..................................24
Hình 2.9 Lưu lượng yêu cầu và độ trễ trung bình của pure-ALOHA ...........................24
Hình 2.10 Lưu lượng yêu cầu và thông lượng của slot-ALOHA..................................25
Hình 2.11 Lưu lượng yêu cầu và độ trễ trung bình của slot-ALOHA...........................26
Hình 3.1 Ví dụ minh họa cách COPE tăng thông lượng ...............................................27
Hình 3.2 Ví dụ của mã hóa cơ hội.................................................................................30
Hình 3.3 Tiêu đề COPE .................................................................................................39
Hình 3.4 Lưu đồ cho thực hiện COPE...........................................................................41
Hình 3.5 Những topo đơn giản để hiểu về mã hóa và hiệu suất mã hóa + MAC của COPE
.......................................................................................................................................43
Hình 3.6 Topo hình sao của k luồng hai chiều lưu lượng. Mọi lưu lượng đi qua nút trung
tâm (R) như là một chuyển tiếp.....................................................................................46
Hình 3.7. Phân tích thông lượng (3.11) và (3.13) như là một hàm xác suất truyền dẫn p ,
khi 1 , N0 0 , và k 4 ..........................................................................................52
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phixi
Hình 3.8 Phân tích thông lượng (3.11) và (3.13) như là một hàm xác suất truyền dẫn p ,
khi 1 , N0 0.1 , và k 4 .......................................................................................53
Hình 3.9 Thông lượng tối đa của (3.11) và (3.13) khi là hàm theo SINR , với p p * * , c và
k 4 ...............................................................................................................................531
MỞ ĐẦU
Tất cả mạng viễn thông ngày nay đều được giả định rằng thông tin là riêng rẽ. Dù
là gói tin hay tín hiệu mạng điện thoại, thông tin được truyền theo cách tương tự như ô tô
trên đường cao tốc hay các luồng nước trong ống dẫn. Đó là các luồng dữ liệu độc lập
chia sẻ tài nguyên mạng, nhưng thông tin vẫn tách rời. Định tuyến, nguồn dữ liệu, điều
khiển lỗi và các chức năng mạng đều dựa trên giả định này.
Tuy nhiên mã hóa mạng lại phá vỡ giả định này. Thay vì chỉ chuyển tiếp và lưu trữ
dữ liệu, các nút mạng kết hợp một vài gói dữ liệu ở đầu vào thành một vài gói dữ liệu tại
đầu ra.
Mục đích của luận văn này xem lại khả năng ứng dụng mã hóa mạng trong các
mạng multihop không dây. Đặc biệt, luận văn tập trung vào một topo hình sao kiểu như
chuẩn 802.11, trong đó các nút bên ngoài trao đổi dữ liệu với nhau thông qua một nút
trung tâm. Câu hỏi đặt ra là làm sao tăng hiệu năng bằng cách áp dụng mã hóa mạng tại
nút trung tâm. Để trả lời câu hỏi này, luận văn phân tích hiệu suất của slot-ALOHA cho
một topo mạng hình sao. Với hai phiên bản slot-ALOHA là slot-ALOHA được xác định
thông thường [12] và slot-ALOHA mã hóa [30] xác định cho giao thức slot-ALOHA
nhưng có mã hóa mạng, nơi mà nút trung tâm thực hiện một mã hóa mạng với phép toán
XOR để mã hóa hai hướng lưu lượng truy cập của các nút bên ngoài.
Mô hình kiến trúc COPE được đề xuất trong [4, 31], thực hiện phương pháp
slot-ALOHA mã hóa mạng, bằng cách tận dụng lợi thế để truyền quảng bá trên đường
truyền vô tuyến, cho phép nhiều nút gần nhau cùng thu được một gói tin được quảng bá
từ một nút nào đó. Điều này thường bất lợi vì các nút gần nhau đôi khi không cần các gói
tin thu được làm tiêu tốn băng thông vô ích. Truyền tin kiểu quảng bá được xem như là
một trong những hạn chế cơ bản của mạng vô tuyến đa hop.
Mạng dựa trên mô hình COPE hoạt động dựa trên sự chia sẻ đường truyền vô
tuyến, quảng bá gói tin xung quanh đường truyền của một nút nào đấy. Mỗi nút chỉ lưu
trữ các gói tin không cần thiết trong một khoảng thời gian ngắn, và thông báo tới nút lân
cận các gói tin nó đã nhận được bằng chú thích trong gói nó gửi đi. Khi một nút truyền
gói tin, nó xem xét thông tin về các gói tin nút lân cận đã nhận được để thực hiện mã hóa
cơ hội; nút thực hiện XOR nhiều gói tin và truyền gói tin kết quả, nếu một hop có đủ
thông tin sẽ giải mã gói tin nhận được. Điều này mở rộng kiến trúc COPE với hai luồng
truyền và XOR thực hiện với nhiều hơn một cặp gói tin.
Thiết kế kiến trúc chuyển tiếp gói tin dựa trên mã hóa mạng ngoài việc thiết kế một
thuật toán mã hóa và giải mã hiệu quả còn gặp phải một số thách thức nhất định. Đầu
tiên, để mã hóa chính xác tập các gói tin, các nút phải học xem các nút lân cận đã nhận
được những gói tin nào mà không tiêu tốn thêm đường truyền. Thứ hai, vì các gói tin mã
hóa là sử dụng cho ít nhất là hai hop, nút này phải bảo đảm truyền tin cậy các thông tin
tương ứng tới tất cả các hop. Nhận phản hồi của lớp liên kết các gói tin mất hay đã truyền
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi2
thành công từ hop khác thường khó khăn, do đó ta phải thiết kế một kỹ thuật xác nhận và
truyền lại hiệu quả hơn.
Kỹ thuật mã hóa mạng dựa trên COPE đưa ra cách xử lý các vấn đề lý thuyết của
mã hóa mạng khi có nhiều phiên unicast. Vấn đề cốt lõi của COPE là mã hóa mạng cục
bộ, các router xử lý các gói tin cục bộ để cho chúng có thể giải mã được khi đương
truyền các luồng unicast bị lệch. Điều này bảo đảm rằng thông tin không định truyền
trên một đường xác định sẽ không thể chuyển được và tránh lãng phí dung lượng. Với
mô hình mạng vô tuyến 20 nút, các tác giả trong công trình [31] đã đưa ra được các kết
luận sau:
Mã hóa mạng có rất nhiều lợi ích thực tế và có thể cái thiện đáng kể thông
lượng mạng vô tuyến.
Khi đường truyền trong mạng vô tuyến bị tắc nghẽn và lưu lượng gồm nhiều
luồng UDP, COPE sẽ tăng thông lượng mạng 3 - 4 lần.
Nếu lưu lượng không có điều khiển luồng (như UDP), mô hình COPE có thể
cải thiện thông lượng hơn nhiều so với lý thuyết mã hóa mạng bởi vì mã hóa mạng giúp
hàng đợi trong router nhỏ hơn, giảm xác suất mà router phải loại bỏ gói tin đang truyền
do tắc nghẽn.
Với mạng lưới kết nối với Internet qua access point, sự cải thiện về thông
lượng sử dụng mô hình COPE sẽ biến đổi phụ thuộc vào tỉ lệ giữa tổng lưu lượng đường
xuống (download) và đường lên (upload) truyền qua điểm truy cập (access point-AP),
và biến đổi từ 5% tới 70%.
Các thiết bị đầu cuối ẩn tạo ra sự xung đột cao không thể được đánh dấu thậm
chí với số tối đa của kỹ thuật truyền lại theo chuẩn 802.11. Lúc này, TCP không gửi đủ
dữ liệu, do đó không tạo ra cơ hội cho mã hóa mạng. Khi không có các thiết bị ẩn, thông
lượng TCP sẽ tăng lên.
Bố cục của luận văn
Nội dung của luận văn được bố cục như sau:
hương 1: Những vấn đề cơ bản. Chương này giới thiệu tổng quan về mã hóa
mạng và thiết kế mạng lưới không dây. Mục 1.1 giới thiệu về mã hóa mạng. Mục 1.2 lợi
ích của mã hóa 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.
hương 2: Kỹ thuật đa truy cập. Giới thiệu giao thức đa truy cập: Giao thức đa
truy cập không tranh chấp và Giao thức đa truy cập tranh chấp. Nguyên tắc hoạt động
của giao thức ALOHA và ảnh hưởng của hiệu ứng lấn át. Chương trình và kết quả mô
phỏng thuật toán pure-ALOHA và slot-ALOHA.3
hương 3: ã hóa mạng không dây sử dụng giao thức ALOHA. Đầu tiên
Chương này trình bày thiết kế, thực hiện và đánh giá hiệu năng dựa trên mô hình COPE
sử dụng giao thức ALOHA, một kiến trúc mới cho truyền tin không dây sử dụng mã hóa
mạng ở mức gói để cải thiện thông lượng mạng vô tuyến. Kiến trúc COPE chèn thêm
các mã đệm giữa lớp IP và lớp MAC, từ đó có thể truyền nhiều gói tin trong cùng một
lần truyền.
Tiếp theo trình bày giao thức ALOHA mã hóa. Luận văn tập trung vào một topo
mạng hình sao, trong đó các nút bên ngoài trao đổi dữ liệu với nhau thông qua nút trung
tâm. Một câu hỏi là có bao nhiêu thông lượng tăng lên bằng cách áp dụng mã hóa mạng
tại nút trung tâm. Bằng cách phân tích topo mạng hình sao, chúng ta có thể kiểm soát nút
tắc nghẽn trong một mạng multihop không dây, nơi mà rất nhiều lưu lượng truy cập đi
qua nút trung tâm. Trong phân tích của luận văn, chúng tui thực hiện tối ưu hóa xuyên
lớp qua lớp vật lý và lớp MAC.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi4
hương 1. NHỮNG VẤN ĐỀ Ơ BẢN
1.1. ã hóa mạng
Xét mô hình mạng Hình 1.1 sao cho
Hình 1.1 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. Cho 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, đường truyền ở giữa sẽ bị tắc nghẽn.
Tại mọi thời điểm, hai router hay là gửi P1 tới D2 hay P2 tới D1. Ngược lại, nếu router
gửi lên đường truyền gói tin P1⊕P2 (hay bất kỳ tổ hợp tuyến tính nào của P1 và P2) xem
Hình 1.1, cả hai đích sẽ nhận được hai gói. 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, 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.
Mặt khác 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 thấp hơn và bằng 1(1 - 2) +
2(1 - 1) .
Một cách tổng quát, 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 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.1.1. ã 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ý5
tự của tập hữu hạn F2s , 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
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 F2s .
Gọi P1, P2, …, Pn là n gói tin ban đầu từ một hay 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 g g n (1), (2)... ( )
trong trường F2s 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
nguồn:
Tổng này được xác định tại mọi vị trí ký tự, X k g i P k ( ) ( ) ( ) in1 i với Pi(k) và X(k)
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, sẽ giải thích ở mục sau.
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 ( , ),...,( , ) g X g X 1 1 m 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ố
h h h m (1),..., ( ) và tính toán tổ hợp tuyến tính X h j X ' mj1 ( ) 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;
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 h j g ' mj1 ( ) i . Đẳng
thức này có thể lặp lại tại vài nút trong mạng.
1.1.2. Giải mã
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 g g 1,..., 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. Vậy nên, để thu được các gói tin gốc đã truyền, cần giải hệ phương trình:
Ở đâ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
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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi6
1.1.3. á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 F2s , theo kiểu độc lập và không tập trung [25]. Với mã mạng
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 [25]. 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.1.4. ác vấn đề thực tế
1.1.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.2 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
Nhưng giá trị lớn nhất mà hiệu suất mã hóa có thể đạt được (khả năng của mạng vô
tuyến sử dụng COPE về lý thuyết) là bao nhiêu? Khả năng của mã hóa mạng tổng quát
cho lưu lượng unicast vẫn là một câu hỏi mở với đồ thị tùy ý. Tuy nhiên, chúng ta phân
tích những topo cơ bản để xem các yếu tố ảnh hưởng đến hiệu suất mã hóa của COPE.
Phân tích ở đây giả định rằng các nút là đồng nhất, phần vô tuyến là đẳng hướng, khả
năng nhận gói tin trong một bán kính nhất định nào đó là hoàn hảo, và ngoài khoảng bán
kính này thì không thể nhận được tín hiệu và nếu một cặp nút có thể truyền tin cho nhau,
định tuyến sẽ có đường truyền trực tiếp giữa hai nút. Thêm nữa, ta cho rằng các luồng là
vô hạn và ta chỉ xem xét trạng thái ổn định.
Định lý 2.1 Nếu thiếu cơ hội nghe, hiệu suất mã hóa tối đa mà COPE có thể đạt
được là 2.
Chứng minh:
Trước hết ta chứng minh giới hạn trên của hiệu suất mã hóa là 2. Chú ý rằng nếu
nút trung gian mã hóa N gói với nhau, những gói này phải tới N hop kế tiếp khác nhau,
bởi quy tắc mã hóa mục 2.1. Nếu thiếu cơ hội nghe, chỉ lân cận có một gói tin là hop liền
kề trước của gói tin. Cho rằng hop trung gian mã hóa ≥ 2 gói tin từ cùng lân cận. Tất cả
các lân cận khác phải có ≤ N - 2 gói tin trong gói mã hóa, điều này vi phạm quy tắc mã
hóa. Kết quả là, hop trung gian chỉ có thể mã hóa nhiều nhất một gói tin từ một lân cận.
Không có cơ hội nghe, chỉ có gói tin gốc trong gói mã hóa mà lân cận có. Theo quy tắc
mã hóa, điều này dẫn đến hop trung gian chỉ có thể mã hóa nhiều nhất 2 gói cùng nhau.
Từ đó tổng số lần truyền trong mạng nhiều nhất có thể giảm còn ½, cho hiệu suất mã hóa
là 2.
Thực tế, hiệu suất này là có thể đạt được trong chuỗi N đường truyền ở Hình 3.5(a).
Topo này là mở rộng của ví dụ ở Hình 3.1 khi N=2. Trường hợp không mã hóa yêu cầu
tổng cộng là 2N lần truyền để gửi một gói từ S1 tới D1 và ngược lại. Nếu có mã hóa, mỗi
N-1 nút trung gian có thể truyền thông tin đồng thời tới các lân cận ở một trong hai phía
bởi mã hóa hai gói tin truyền theo hai hướng ngược nhau, cho tổng cộng của N+1 lần
truyền. Hiệu suất mã hóa trong trường hợp này là 2
1
N
N
, xấp xỉ 2 khi số nút tăng lên.
Trong khi chúng ta không biết hiệu suất tối đa của COPE khi có cơ hội nghe, ở đây
đưa ra một số topo có thêm cơ hội nghe vào COPE. Ví dụ, xem xét topo “X” trong Hình
3.5(b). Topo này tương tự như trường hợp ở Hình 3.1 chỉ khác là hai luồng truyền theo
những đường cắt nhau. COPE mà không có cơ hội lắng nghe không thể thu được bất cứ
hiệu suất nào với topo này. Nhưng với cơ hội lắng nghe và dự đoán, nút trung gian có thể
kết hợp các gói tin truyền qua theo 2 hướng ngược nhau và cho hiệu suất mã 4/3=1,33.
Kết quả này là quan trọng vì trong mạng vô tuyến thực tế sẽ chỉ có một số lượng nhỏ các
luồng truyền trên đường ngược nhau như S1 và D1, nhưng một trong những mong chờ
nhiều luồng giao nhau tại một nút chuyển tiếp, và do đó có thể được mã hóa bằng cách
sử dụng cơ hội lắng nghe và đoán.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Nhà xuất bản: Đại học Công nghệ
Ngày: 2013
Chủ đề: Mã hóa
Mạng không dây
Giao thức Aloha
Kỹ thuật điện tử
Miêu tả: Tổng quan về mã hóa mạng và thiết kế mạng lưới không dây: giới thiệu về mã hóa mạng ; Lợi ích của mã hóa mạng; 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. Giới thiệu giao thức đa truy cập: Giao thức đa truy cập không tranh chấp và Giao thức đa truy cập tranh chấp; Nguyên tắc hoạt động của giao thức ALOHA và ảnh hưởng của hiệu ứng lấn át; Chương trình và kết quả mô phỏng thuật toán pure-ALOHA và slot-ALOHA. Trình bày thiết kế, thực hiện và đánh giá hiệu năng dựa trên mô hình COPE sử dụng giao thức ALOHA, một kiến trúc mới cho truyền tin không dây sử dụng mã hóa mạng ở mức gói để cải thiện thông lượng mạng vô tuyến. Kiến trúc COPE chèn thêm các mã đệm giữa lớp IP và lớp MAC, từ đó có thể truyền nhiều gói tin trong cùng một lần truyền. Tiếp theo trình bày giao thức ALOHA mã hóa. Tập trung vào một topo mạng hình sao, trong đó các nút bên ngoài trao đổi dữ liệu với nhau thông qua nút trung tâm. Một câu hỏi là có bao nhiêu thông lượng tăng lên bằng cách áp dụng mã hóa mạng tại nút trung tâm. Bằng cách phân tích topo mạng hình sao, có thể kiểm soát nút tắc nghẽn trong một mạng multihop không dây, nơi mà rất
Electronic Resources
Luận văn ThS. Kỹ thuật điện tử -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2013
LỜI CAM ĐOAN.............................................................................................................i
M C L C ..................................................................................................................... iii
Danh mục các ký hiệu và chữ viết tắt.............................................................................vi
Danh mục các bảng.........................................................................................................ix
Danh mục các hình vẽ, đồ thị ..........................................................................................x
MỞ ĐẦU .........................................................................................................................1
hương 1. NHỮNG VẤN ĐỀ Ơ BẢN ......................................................................4
1.1. Mã hóa mạng....................................................................................................4
1.1.1. Mã hóa .....................................................................................................4
1.1.2. Giải mã ....................................................................................................5
1.1.3. Cách lựa chọn tổ hợp tuyến tính..............................................................6
1.1.4. Các vấn đề thực tế ...................................................................................6
1.1.4.1. Giải mã ....................................................................................................6
1.1.4.2. Khối hóa ..................................................................................................7
1.1.4.3. Các phép toán trường hữu hạn ................................................................7
1.2. Lợi ích của mã hóa mạng .................................................................................7
1.2.1. Tăng cường thông lượng .........................................................................7
1.2.2. Sự ổn định và thích nghi..........................................................................8
1.2.2.1. Đơn giản hóa phân phối nội dung ...........................................................8
1.2.2.2. Chống lại mất gói ....................................................................................9
1.3. Mạng không dây có topo hình lưới (mesh) ......................................................9
1.3.1. Lớp vật lý...............................................................................................10
1.3.2. Lớp liên kết dữ liệu ...............................................................................11
1.3.3. Lớp mạng...............................................................................................11
1.3.3.1. Giao thức định tuyến với metric khác nhau ..........................................11
1.3.3.2. Định tuyến đa đường .............................................................................12
1.3.3.3. Định tuyến theo vùng địa lý ..................................................................12
1.3.4. Lớp giao vận..........................................................................................12
hương 2. KỸ THUẬT ĐA TRUY ẬP...................................................................14
2.1. Phân loại các giao thức đa truy cập................................................................14
2.1.1. Giao thức đa truy cập không tranh chấp (lập lịch) ................................15
2.1.2. Giao thức đa truy cập tranh chấp (ngẫu nhiên) .....................................16iv
2.2. Giao thức ALOHA .........................................................................................16
2.2.1. Pure-ALOHA ........................................................................................16
2.2.2. Slot-ALOHA .........................................................................................18
2.3. Mô phỏng giao thức ALOHA ........................................................................20
2.3.1. Mô hình hóa hệ thống thông tin gói ......................................................20
2.3.1.1. Hiệu ứng lấn át ......................................................................................20
2.3.1.2. Lưu lượng yêu cầu.................................................................................20
2.3.1.3. Thông lượng ..........................................................................................21
2.3.1.4. Trễ truyền trung bình.............................................................................21
2.3.2. Cấu hình mô phỏng cơ bản....................................................................21
2.4. Mô phỏng thuật toán ALOHA........................................................................22
2.4.1. Chương trình và kết quả mô phỏng thuật toán pure-ALOHA ..............22
2.4.1.1. Tham số và cấu trúc chương trình.........................................................22
2.4.1.2. Kết quả mô phỏng .................................................................................24
2.4.2. Chương trình và kết quả mô phỏng thuật toán slot-ALOHA................25
2.4.2.1. Tham số và cấu trúc chương trình.........................................................25
2.4.2.2. Kết quả mô phỏng .................................................................................25
hương 3: Ã HÓA ẠNG KHÔNG DÂY SỬ D NG GIAO THỨ A OHA27
3.1. Thiết kế mức cao của COPE [4, 31] ..............................................................27
3.1.1. Nghe ......................................................................................................28
3.1.2. Mã hóa ...................................................................................................29
3.1.3. Học ........................................................................................................31
3.2. Kiến trúc hệ thống [4, 31] ..............................................................................32
3.2.1. Mục đích thiết kế...................................................................................32
3.2.2. Mô đun Mã hóa/ Giải mã ......................................................................32
3.2.2.1. Cơ hội mã hóa........................................................................................32
3.2.2.2. Mã hóa cực đại xác suất giải mã ...........................................................33
3.2.2.3. Mã hóa các gói tin có cùng độ dài.........................................................33
3.2.2.4. Cấu trúc dữ liệu và thuật toán mã hóa...................................................34
3.2.2.5. Thuật toán giải mã.................................................................................35
3.2.3. Độ tin cậy ..............................................................................................35
3.2.3.1. Độ tin cậy của 802.11 ............................................................................36
3.2.3.2. Đặt vấn đề..............................................................................................36
3.2.3.3. Giải pháp ...............................................................................................36
3.2.3.4. Độ tin cậy lớp giao vận .........................................................................37
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiv
3.2.4. Mô đun lắng nghe..................................................................................38
3.2.5. Mô đun học............................................................................................38
3.3. Chi tiết thực hiện [4, 31] ................................................................................39
3.3.1. Định dạng gói tin...................................................................................39
3.3.1.1. ID của gói tin gốc mã hóa .....................................................................39
3.3.1.2. Thông báo nhận .....................................................................................40
3.3.1.3. Biểu diễn ACK bất đồng bộ ngắn gọn và đơn giản...............................40
3.3.2. Điều khiển luồng ...................................................................................40
3.4. Hiệu quả của COPE [31]................................................................................41
3.4.1. Hiệu suất mã hóa ...................................................................................41
3.4.2. Hiệu suất mã hóa + MAC......................................................................43
3.5. Giới thiệu giao thức ALOHA mã hóa ............................................................45
3.6. Mô hình hệ thống ...........................................................................................46
3.7. Phân tích thông lượng ....................................................................................48
3.7.1. Slot-ALOHA .........................................................................................49
3.7.2. ALOHA mã hóa.....................................................................................49
3.7.3. Điều kiện ổn định ..................................................................................50
3.8. Kết quả số liệu................................................................................................51
KẾT UẬN ..................................................................................................................55
T I I U THA KHẢO...........................................................................................56
PH .....................................................................................................................59vi
Danh mục các ký hiệu và chữ viết tắt
Kí hiệu Viết đầy đủ Ý nghĩa
ACK Acknowledgment Bản tin báo nhận
API Application Programming
Interface
Giao diện lập trình ứng dụng
ARQ Automatic Repeat Query Tự động lặp lại truy vấn
CMAPS Conflict Maps Bản đồ phân phối
COPE Kiến trúc mã hóa mạng mức gói tin. Nó
chèn thêm lớp mã hóa ở giữa lớp mạng
và lớp liên kết
CSMA Carrier Sense Multiple
Access
Đa truy cập nhận biết sóng mang
CSMA/CA Carrier Sense Multiple
Access with Collision
Avoidance
Đa truy cập nhận biết sóng mang phát
hiện xung đột
C/N Carrier to Noise Tỷ số giữa công suất tín hiệu trên công
suất nhiễu
DSSS Direct Sequence Spread
Spectrum
Trải phổ chuỗi trực tiếp
ETX Expected Transmission
Count
Số lượt dự kiến sẽ truyền
ExOR Tích hợp định tuyến và giao thức MAC
làm tăng thông lượng chuyển luồng
unicast lớn trong các mạng multihop
không dây
FDMA Frequency Division
Multiple Access
Giao thức đa truy cập phân chia theo tần
số
FEC Forward Error Correction Sửa lỗi chuyển tiếp
FIFO First In First Out Vào trước ra trước
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phivii
GSM Global System for Mobile
communications Hệ thống thông tin di động toàn cầu
IEEE Institute of Electrical and
Electronics Engineers
Viện kỹ thuật điện và điện tử
IETF Internet Engineering Task
Force
Một tổ chức Viễn thông quốc tế. Lực
lượng chuyên phụ trách kỹ thuật kết nối
mạng.
IP Internet Protocol Giao thức Internet
ISMA Inhibit Sense Multiple
Access
Đa truy cập nhận biết ngăn chặn
ITU-T International
Telecommunication
Union-Telecommunication
Standardization Sector
Hiệp hội viễn thông quốc tế - Tổ chức
chuẩn chuẩn hóa các kỹ thuật Viễn
thông.
LAN Local Area Network Mạng cục bộ
MAC Media Access Control Điều khiển truy cập môi trường
MIMO Multiple-Input and
Multiple-Output
Nhiều đầu vào và nhiều đầu ra
MORE Giao thức định tuyến cơ hội MAC độc
lập
NP Nondeterministic
Polynomial
Đa thức bất định
OFDM Orthogonal Frequency
Division Multiplexing
Đa phân chia theo tần số trực giao
OMS Opportunistic Multipath
Scheduling
Cơ hội lập lịch đa đường
PRMA Packet Reservation
Multiple Access
Đa truy cập đặt trước gói
QoS Quality of Service Chất lượng dịch vụ
RFID Radio Frequency
Identification
Nhận biết tần số vô tuyến
RSVP Resource Reservation Giao thức định trước nguồn tài nguyênviii
Protocol
RTT Round-Trip Time Thời gian đi hai chiều
SINR Signal to Interference plus
Noise Ratio
Tỷ lệ tín hiệu với nhiễu cộng ồn
TDM Time Division
Multiplexing
Ghép kênh phân chia theo thời gian
TDMA Time Division Multiple
Access
Giao thức đa truy cập phân chia theo
thời gian
TCP Transmission Control
Protocol
Giao thức điều khiển truyền thông tin
UDP User Datagram Protocol Giao thức Datagram người dùng
UWB Ultra-Wide Band Băng siêu rộng
WAN Wide Area Network Mạng diện rộng
wifi Wireless Fidelity Mạng không dây Wifi
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiix
Danh mục các bảng
Bảng 2.1 Điều kiện mô phỏng.......................................................................................23
Bảng 3.1 Định nghĩa các thuật ngữ sử dụng trong chương này. ...................................28
Bảng 3.2 Hiệu suất theo lý thuyết cho một số topo cơ bản ...........................................45x
Danh mục các hình vẽ, đồ thị
Hình 1.1 Ví dụ đơn giản sử dụng mã hóa mạng nhằm nâng cao thông lượng................4
Hình 1.2 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. ................................................................................................................................6
Hình 1.3 Mã hóa mạng cải thiện độ ổn định. Access point có thể truyền các tổ hợp tuyến
tính của Pa và Pb cho tới khi cả A và B mã hóa được, làm đơn giản hóa hoạt động của
mạng. ...............................................................................................................................8
Hình 1.4 Mã hóa mạng chống lại vấn đề mất gói. A cần gửi gói tin tới C qua router B.
Đường truyền AB và BC có xác suất mất gói là εAB và εBC tương ứng. ..........................9
Hình 1.5 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
hop 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. .......10
Hình 2.1(a) TDMA và (b) FDMA .................................................................................15
Hình 2.2 pure-ALOHA..................................................................................................17
Hình 2.3 Sự xung đột giữa những gói tin trong hệ thống pure-ALOHA ......................17
Hình 2.4 slot-ALOHA ...................................................................................................18
Hình 2.5 Tranh chấp gói trong hệ thống slot-ALOHA..................................................18
Hình 2.6 Xung đột giữa những gói tin truyền đi ...........................................................20
Hình 2.7 Cấu hình mô phỏng máy tính cơ bản..............................................................22
Hình 2.8 Lưu lượng yêu cầu và thông lượng của pure-ALOHA ..................................24
Hình 2.9 Lưu lượng yêu cầu và độ trễ trung bình của pure-ALOHA ...........................24
Hình 2.10 Lưu lượng yêu cầu và thông lượng của slot-ALOHA..................................25
Hình 2.11 Lưu lượng yêu cầu và độ trễ trung bình của slot-ALOHA...........................26
Hình 3.1 Ví dụ minh họa cách COPE tăng thông lượng ...............................................27
Hình 3.2 Ví dụ của mã hóa cơ hội.................................................................................30
Hình 3.3 Tiêu đề COPE .................................................................................................39
Hình 3.4 Lưu đồ cho thực hiện COPE...........................................................................41
Hình 3.5 Những topo đơn giản để hiểu về mã hóa và hiệu suất mã hóa + MAC của COPE
.......................................................................................................................................43
Hình 3.6 Topo hình sao của k luồng hai chiều lưu lượng. Mọi lưu lượng đi qua nút trung
tâm (R) như là một chuyển tiếp.....................................................................................46
Hình 3.7. Phân tích thông lượng (3.11) và (3.13) như là một hàm xác suất truyền dẫn p ,
khi 1 , N0 0 , và k 4 ..........................................................................................52
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phixi
Hình 3.8 Phân tích thông lượng (3.11) và (3.13) như là một hàm xác suất truyền dẫn p ,
khi 1 , N0 0.1 , và k 4 .......................................................................................53
Hình 3.9 Thông lượng tối đa của (3.11) và (3.13) khi là hàm theo SINR , với p p * * , c và
k 4 ...............................................................................................................................531
MỞ ĐẦU
Tất cả mạng viễn thông ngày nay đều được giả định rằng thông tin là riêng rẽ. Dù
là gói tin hay tín hiệu mạng điện thoại, thông tin được truyền theo cách tương tự như ô tô
trên đường cao tốc hay các luồng nước trong ống dẫn. Đó là các luồng dữ liệu độc lập
chia sẻ tài nguyên mạng, nhưng thông tin vẫn tách rời. Định tuyến, nguồn dữ liệu, điều
khiển lỗi và các chức năng mạng đều dựa trên giả định này.
Tuy nhiên mã hóa mạng lại phá vỡ giả định này. Thay vì chỉ chuyển tiếp và lưu trữ
dữ liệu, các nút mạng kết hợp một vài gói dữ liệu ở đầu vào thành một vài gói dữ liệu tại
đầu ra.
Mục đích của luận văn này xem lại khả năng ứng dụng mã hóa mạng trong các
mạng multihop không dây. Đặc biệt, luận văn tập trung vào một topo hình sao kiểu như
chuẩn 802.11, trong đó các nút bên ngoài trao đổi dữ liệu với nhau thông qua một nút
trung tâm. Câu hỏi đặt ra là làm sao tăng hiệu năng bằng cách áp dụng mã hóa mạng tại
nút trung tâm. Để trả lời câu hỏi này, luận văn phân tích hiệu suất của slot-ALOHA cho
một topo mạng hình sao. Với hai phiên bản slot-ALOHA là slot-ALOHA được xác định
thông thường [12] và slot-ALOHA mã hóa [30] xác định cho giao thức slot-ALOHA
nhưng có mã hóa mạng, nơi mà nút trung tâm thực hiện một mã hóa mạng với phép toán
XOR để mã hóa hai hướng lưu lượng truy cập của các nút bên ngoài.
Mô hình kiến trúc COPE được đề xuất trong [4, 31], thực hiện phương pháp
slot-ALOHA mã hóa mạng, bằng cách tận dụng lợi thế để truyền quảng bá trên đường
truyền vô tuyến, cho phép nhiều nút gần nhau cùng thu được một gói tin được quảng bá
từ một nút nào đó. Điều này thường bất lợi vì các nút gần nhau đôi khi không cần các gói
tin thu được làm tiêu tốn băng thông vô ích. Truyền tin kiểu quảng bá được xem như là
một trong những hạn chế cơ bản của mạng vô tuyến đa hop.
Mạng dựa trên mô hình COPE hoạt động dựa trên sự chia sẻ đường truyền vô
tuyến, quảng bá gói tin xung quanh đường truyền của một nút nào đấy. Mỗi nút chỉ lưu
trữ các gói tin không cần thiết trong một khoảng thời gian ngắn, và thông báo tới nút lân
cận các gói tin nó đã nhận được bằng chú thích trong gói nó gửi đi. Khi một nút truyền
gói tin, nó xem xét thông tin về các gói tin nút lân cận đã nhận được để thực hiện mã hóa
cơ hội; nút thực hiện XOR nhiều gói tin và truyền gói tin kết quả, nếu một hop có đủ
thông tin sẽ giải mã gói tin nhận được. Điều này mở rộng kiến trúc COPE với hai luồng
truyền và XOR thực hiện với nhiều hơn một cặp gói tin.
Thiết kế kiến trúc chuyển tiếp gói tin dựa trên mã hóa mạng ngoài việc thiết kế một
thuật toán mã hóa và giải mã hiệu quả còn gặp phải một số thách thức nhất định. Đầu
tiên, để mã hóa chính xác tập các gói tin, các nút phải học xem các nút lân cận đã nhận
được những gói tin nào mà không tiêu tốn thêm đường truyền. Thứ hai, vì các gói tin mã
hóa là sử dụng cho ít nhất là hai hop, nút này phải bảo đảm truyền tin cậy các thông tin
tương ứng tới tất cả các hop. Nhận phản hồi của lớp liên kết các gói tin mất hay đã truyền
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi2
thành công từ hop khác thường khó khăn, do đó ta phải thiết kế một kỹ thuật xác nhận và
truyền lại hiệu quả hơn.
Kỹ thuật mã hóa mạng dựa trên COPE đưa ra cách xử lý các vấn đề lý thuyết của
mã hóa mạng khi có nhiều phiên unicast. Vấn đề cốt lõi của COPE là mã hóa mạng cục
bộ, các router xử lý các gói tin cục bộ để cho chúng có thể giải mã được khi đương
truyền các luồng unicast bị lệch. Điều này bảo đảm rằng thông tin không định truyền
trên một đường xác định sẽ không thể chuyển được và tránh lãng phí dung lượng. Với
mô hình mạng vô tuyến 20 nút, các tác giả trong công trình [31] đã đưa ra được các kết
luận sau:
Mã hóa mạng có rất nhiều lợi ích thực tế và có thể cái thiện đáng kể thông
lượng mạng vô tuyến.
Khi đường truyền trong mạng vô tuyến bị tắc nghẽn và lưu lượng gồm nhiều
luồng UDP, COPE sẽ tăng thông lượng mạng 3 - 4 lần.
Nếu lưu lượng không có điều khiển luồng (như UDP), mô hình COPE có thể
cải thiện thông lượng hơn nhiều so với lý thuyết mã hóa mạng bởi vì mã hóa mạng giúp
hàng đợi trong router nhỏ hơn, giảm xác suất mà router phải loại bỏ gói tin đang truyền
do tắc nghẽn.
Với mạng lưới kết nối với Internet qua access point, sự cải thiện về thông
lượng sử dụng mô hình COPE sẽ biến đổi phụ thuộc vào tỉ lệ giữa tổng lưu lượng đường
xuống (download) và đường lên (upload) truyền qua điểm truy cập (access point-AP),
và biến đổi từ 5% tới 70%.
Các thiết bị đầu cuối ẩn tạo ra sự xung đột cao không thể được đánh dấu thậm
chí với số tối đa của kỹ thuật truyền lại theo chuẩn 802.11. Lúc này, TCP không gửi đủ
dữ liệu, do đó không tạo ra cơ hội cho mã hóa mạng. Khi không có các thiết bị ẩn, thông
lượng TCP sẽ tăng lên.
Bố cục của luận văn
Nội dung của luận văn được bố cục như sau:
hương 1: Những vấn đề cơ bản. Chương này giới thiệu tổng quan về mã hóa
mạng và thiết kế mạng lưới không dây. Mục 1.1 giới thiệu về mã hóa mạng. Mục 1.2 lợi
ích của mã hóa 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.
hương 2: Kỹ thuật đa truy cập. Giới thiệu giao thức đa truy cập: Giao thức đa
truy cập không tranh chấp và Giao thức đa truy cập tranh chấp. Nguyên tắc hoạt động
của giao thức ALOHA và ảnh hưởng của hiệu ứng lấn át. Chương trình và kết quả mô
phỏng thuật toán pure-ALOHA và slot-ALOHA.3
hương 3: ã hóa mạng không dây sử dụng giao thức ALOHA. Đầu tiên
Chương này trình bày thiết kế, thực hiện và đánh giá hiệu năng dựa trên mô hình COPE
sử dụng giao thức ALOHA, một kiến trúc mới cho truyền tin không dây sử dụng mã hóa
mạng ở mức gói để cải thiện thông lượng mạng vô tuyến. Kiến trúc COPE chèn thêm
các mã đệm giữa lớp IP và lớp MAC, từ đó có thể truyền nhiều gói tin trong cùng một
lần truyền.
Tiếp theo trình bày giao thức ALOHA mã hóa. Luận văn tập trung vào một topo
mạng hình sao, trong đó các nút bên ngoài trao đổi dữ liệu với nhau thông qua nút trung
tâm. Một câu hỏi là có bao nhiêu thông lượng tăng lên bằng cách áp dụng mã hóa mạng
tại nút trung tâm. Bằng cách phân tích topo mạng hình sao, chúng ta có thể kiểm soát nút
tắc nghẽn trong một mạng multihop không dây, nơi mà rất nhiều lưu lượng truy cập đi
qua nút trung tâm. Trong phân tích của luận văn, chúng tui thực hiện tối ưu hóa xuyên
lớp qua lớp vật lý và lớp MAC.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi4
hương 1. NHỮNG VẤN ĐỀ Ơ BẢN
1.1. ã hóa mạng
Xét mô hình mạng Hình 1.1 sao cho
Hình 1.1 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. Cho 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, đường truyền ở giữa sẽ bị tắc nghẽn.
Tại mọi thời điểm, hai router hay là gửi P1 tới D2 hay P2 tới D1. Ngược lại, nếu router
gửi lên đường truyền gói tin P1⊕P2 (hay bất kỳ tổ hợp tuyến tính nào của P1 và P2) xem
Hình 1.1, cả hai đích sẽ nhận được hai gói. 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, 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.
Mặt khác 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 thấp hơn và bằng 1(1 - 2) +
2(1 - 1) .
Một cách tổng quát, 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 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.1.1. ã 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ý5
tự của tập hữu hạn F2s , 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
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 F2s .
Gọi P1, P2, …, Pn là n gói tin ban đầu từ một hay 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 g g n (1), (2)... ( )
trong trường F2s 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
nguồn:
Tổng này được xác định tại mọi vị trí ký tự, X k g i P k ( ) ( ) ( ) in1 i với Pi(k) và X(k)
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, sẽ giải thích ở mục sau.
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 ( , ),...,( , ) g X g X 1 1 m 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ố
h h h m (1),..., ( ) và tính toán tổ hợp tuyến tính X h j X ' mj1 ( ) 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;
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 h j g ' mj1 ( ) i . Đẳng
thức này có thể lặp lại tại vài nút trong mạng.
1.1.2. Giải mã
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 g g 1,..., 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. Vậy nên, để thu được các gói tin gốc đã truyền, cần giải hệ phương trình:
Ở đâ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
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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi6
1.1.3. á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 F2s , theo kiểu độc lập và không tập trung [25]. Với mã mạng
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 [25]. 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.1.4. ác vấn đề thực tế
1.1.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.2 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
Nhưng giá trị lớn nhất mà hiệu suất mã hóa có thể đạt được (khả năng của mạng vô
tuyến sử dụng COPE về lý thuyết) là bao nhiêu? Khả năng của mã hóa mạng tổng quát
cho lưu lượng unicast vẫn là một câu hỏi mở với đồ thị tùy ý. Tuy nhiên, chúng ta phân
tích những topo cơ bản để xem các yếu tố ảnh hưởng đến hiệu suất mã hóa của COPE.
Phân tích ở đây giả định rằng các nút là đồng nhất, phần vô tuyến là đẳng hướng, khả
năng nhận gói tin trong một bán kính nhất định nào đó là hoàn hảo, và ngoài khoảng bán
kính này thì không thể nhận được tín hiệu và nếu một cặp nút có thể truyền tin cho nhau,
định tuyến sẽ có đường truyền trực tiếp giữa hai nút. Thêm nữa, ta cho rằng các luồng là
vô hạn và ta chỉ xem xét trạng thái ổn định.
Định lý 2.1 Nếu thiếu cơ hội nghe, hiệu suất mã hóa tối đa mà COPE có thể đạt
được là 2.
Chứng minh:
Trước hết ta chứng minh giới hạn trên của hiệu suất mã hóa là 2. Chú ý rằng nếu
nút trung gian mã hóa N gói với nhau, những gói này phải tới N hop kế tiếp khác nhau,
bởi quy tắc mã hóa mục 2.1. Nếu thiếu cơ hội nghe, chỉ lân cận có một gói tin là hop liền
kề trước của gói tin. Cho rằng hop trung gian mã hóa ≥ 2 gói tin từ cùng lân cận. Tất cả
các lân cận khác phải có ≤ N - 2 gói tin trong gói mã hóa, điều này vi phạm quy tắc mã
hóa. Kết quả là, hop trung gian chỉ có thể mã hóa nhiều nhất một gói tin từ một lân cận.
Không có cơ hội nghe, chỉ có gói tin gốc trong gói mã hóa mà lân cận có. Theo quy tắc
mã hóa, điều này dẫn đến hop trung gian chỉ có thể mã hóa nhiều nhất 2 gói cùng nhau.
Từ đó tổng số lần truyền trong mạng nhiều nhất có thể giảm còn ½, cho hiệu suất mã hóa
là 2.
Thực tế, hiệu suất này là có thể đạt được trong chuỗi N đường truyền ở Hình 3.5(a).
Topo này là mở rộng của ví dụ ở Hình 3.1 khi N=2. Trường hợp không mã hóa yêu cầu
tổng cộng là 2N lần truyền để gửi một gói từ S1 tới D1 và ngược lại. Nếu có mã hóa, mỗi
N-1 nút trung gian có thể truyền thông tin đồng thời tới các lân cận ở một trong hai phía
bởi mã hóa hai gói tin truyền theo hai hướng ngược nhau, cho tổng cộng của N+1 lần
truyền. Hiệu suất mã hóa trong trường hợp này là 2
1
N
N
, xấp xỉ 2 khi số nút tăng lên.
Trong khi chúng ta không biết hiệu suất tối đa của COPE khi có cơ hội nghe, ở đây
đưa ra một số topo có thêm cơ hội nghe vào COPE. Ví dụ, xem xét topo “X” trong Hình
3.5(b). Topo này tương tự như trường hợp ở Hình 3.1 chỉ khác là hai luồng truyền theo
những đường cắt nhau. COPE mà không có cơ hội lắng nghe không thể thu được bất cứ
hiệu suất nào với topo này. Nhưng với cơ hội lắng nghe và dự đoán, nút trung gian có thể
kết hợp các gói tin truyền qua theo 2 hướng ngược nhau và cho hiệu suất mã 4/3=1,33.
Kết quả này là quan trọng vì trong mạng vô tuyến thực tế sẽ chỉ có một số lượng nhỏ các
luồng truyền trên đường ngược nhau như S1 và D1, nhưng một trong những mong chờ
nhiều luồng giao nhau tại một nút chuyển tiếp, và do đó có thể được mã hóa bằng cách
sử dụng cơ hội lắng nghe và đoán.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: