Luận văn Đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng manet
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
ĐOÀN CAO THANH
ĐÁNH GIÁ CHI PHÍ TÌM ĐƯỜNG CỦA MỘT SỐ
GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET
LUẬN VĂN THẠC SĨ
Hà Nội - 2011
1
Lời cám ơn
Trước hết tôi xin gửi lời cám ơn tới các thầy cô giáo trong Trường Đại Học
Công Nghệ - Đại Học Quốc Gia Hà Nội đã tận tình chỉ bảo tôi trong suốt khóa học,
cám ơn tập thể lớp K15T3 và đặc biệt là tới thầy giáo, PGS.TS Nguyễn Đình Việt,
người đã nhiệt tình hướng dẫn, chỉ bảo tôi trong công việc nghiên cứu và học tập. Tôi
cũng chân thành cám ơn tới các thành viên trong nhóm nghiên cứu với những góp ý
quý báu trong quá trình thực hiện đề tài.
Sau cùng tôi muốn gửi lời cám ơn tới gia đình và người thân của tôi, những
người đã luôn khuyến khích và động viên tôi trong suốt khóa học.
Do thời gian và điều kiện có hạn nên luận văn không tránh khỏi những thiếu
sót, tôi rất mong sự góp ý của bạn bè, thầy cô và những người quan tâm đến đề tài này.
2
Lời cam đoan
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá
nhân tôi, không sao chép lại của người khác. Luận văn là kết quả của quá trình học
tập, nghiên cứu trong suốt hơn hai năm cao học. Trong các nội dung của luận văn,
những điều được trình bày hoặc là kết quả của cá nhân hoặc là kết quả tổng hợp từ
nhiều nguồn tài liệu khác. Những kết quả nghiên cứu nào của cá nhân đều được chỉ ra
rõ ràng trong luận văn. Các thông tin tổng hợp hay các kết quả lấy từ nhiều nguồn tài
liệu khác đều được trích dẫn đầy đủ và hợp lý. Tất cả tài liệu tham khảo đều có xuất
xứ rõ ràng và được trích dẫn hợp pháp.
Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định
cho lời cam đoan của mình
Hà Nội, Tháng 3, 2011
3
Mục lục
Lời cám ơn .......................................................................................................................1
Lời cam đoan....................................................................................................................2
Danh mục các kí hiệu, các chữ viết tắt ............................................................................5
Danh mục các hình vẽ......................................................................................................7
Danh mục các bảng..........................................................................................................8
Chương 1. GIỚI THIỆU CHUNG...................................................................................9
1.1. Đặt vấn đề [15] .....................................................................................................9
1.2. Mục tiêu nghiên cứu..............................................................................................9
1.3. Tổ chức của luận văn...........................................................................................10
Chương 2. TỔNG QUAN VỀ MẠNG WLAN VÀ MẠNG MANET..........................11
2.1. Giới thiệu và phân loại mạng không dây [15].....................................................11
2.1.1. Phân loại theo định dạng và kiến trúc mạng.................................................12
2.1.2. Phân loại theo phạm vi bao phủ truyền thông ..............................................13
2.1.3. Phân loại theo công nghệ truy cập đường truyền .........................................14
2.1.4. Phân loại theo các ứng dụng mạng...............................................................14
2.2. Mạng LAN không dây (WLAN).........................................................................14
2.2.1. Khái niệm về WLAN....................................................................................14
2.2.2. Lịch sử ra đời mạng WLAN [22] .................................................................16
2.2.3. Giao thức tầng con MAC trong WLAN [12] ...............................................17
2.3. Mạng không dây đặc biệt MANET [15] .............................................................22
2.3.1. Sự phát triển và các ứng dụng của mạng MANET.......................................22
2.3.2. Các đặc điểm của mạng MANET.................................................................23
Chương 3. CÁC GIAO THỨC ĐỊNH TUYẾN MẠNG MANET ................................25
3.1. Giới thiệu về bài toán định tuyến [15] ................................................................25
3.2. Các kĩ thuật định tuyến mạng MANET [10].......................................................26
3.2.1. Định tuyến chủ động và định tuyến phản ứng lại.........................................26
3.2.2. Định tuyến đơn đường và định tuyến đa đường...........................................26
3.2.3. Định tuyến dựa vào bảng và định tuyến khởi tạo phía nguồn......................26
3.2.4. Các kĩ thuật khôi phục..................................................................................27
3.2.5. Chiến lược lựa chọn tuyến............................................................................28
3.2.6. Cập nhật định kỳ và cập nhật theo sự kiện...................................................28
3.2.7. Cấu trúc phẳng và cấu trúc phân cấp............................................................28
3.3. Các giao thức định tuyến chủ yếu trong mạng MANET [8]...............................29
3.3.1. Giao thức DSDV (Destination-Sequenced Distance Vector) [4].................29
3.3.2. Giao thức CGSR (Clusterhead Gateway Switch Routing) [5].....................30
3.3.3. Giao thức WRP (Wireless Routing Protocol) [14].......................................31
3.3.4. Giao thức OLSR (Optimized Link State Routing) [16] ...............................32
3.3.5. Giao thức AODV (Ad Hoc On-Demand Distance Vector) [3] ....................33
3.3.6. Giao thức DSR (Dynamic Source Routing) [6] ...........................................34
4
3.3.7. Giao thức TORA (Temporally-Ordered Routing Algorithm) [11] ..............36
3.3.8. Giao thức ABR (Associativity-Based Routing) [2]......................................38
3.3.9. Giao thức SSR (Signal Stability Routing) [14]............................................40
3.3.10. So sánh các giao thức định tuyến chủ yếu trong mạng MANET [3]-[8] ...40
Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG CHI PHÍ TÌM ĐƯỜNG CỦA MỘT SỐ
GIAO THỨC ĐỊNH TUYẾN MẠNG MANET VỚI CÁC NGỮ CẢNH KHÁC
NHAU ............................................................................................................................45
4.1. Phân tích và lựa chọn phương pháp mô phỏng để đánh giá [1]..........................45
4.2. Bộ mô phỏng NS2...............................................................................................46
4.2.1. Giới thiệu [1] ................................................................................................46
4.2.2. Cấu trúc phần mềm của NS2........................................................................48
4.3. Thiết lập mô phỏng mạng MANET trong NS2...................................................48
4.3.1. Mô hình không dây cơ bản trong NS2 [9]....................................................48
4.3.2. Quá trình mô phỏng mạng MANET với NS2 [1].........................................52
4.3.3. Tích hợp giao thức TORA và OLSR vào bộ mô phỏng NS2.......................54
4.4. Đánh giá bằng mô phỏng chi phí tìm đường một số giao thức định tuyến chủ
yếu trong mạng MANET............................................................................................56
4.4.1. Các độ đo hiệu năng được đánh giá [1]........................................................56
4.4.2. Thiết lập các lựa chọn, tham số mô phỏng [17] ...........................................57
4.4.3. Các ngữ cảnh mô phỏng ...............................................................................57
4.4.4. Đánh giá, nhận xét chi phí tìm đường của một số giao thức định tuyến mạng
MANET..................................................................................................................73
KẾT LUẬN....................................................................................................................75
TÀI LIỆU THAM KHẢO..............................................................................................76
PHỤ LỤC.......................................................................................................................78
5
Danh mục các kí hiệu, các chữ viết tắt
ABR
Associativity-Based Routing
Adhoc On-Demand Distance Vector
Access Point
AODV
AP
BQ
Broadcast Query
BS
Base Station
CBR
Constant Bit Rate
CDMA
CGSR
CLR
Code Division Multiple Access
Clusterhead Gateway Switch Routing
Clear Packet
CSMA
CSMA/CD
CSMA/CA
CTS
Carrier Sense Multiple Access
Carrier Sense Multiple Access/Collision Detect
Carrier Sense Multiple Access/Collision Avoidance
Clear To Send
DAG
DCF
Directed Acyclic Graph
Distributed Coordination Function
DCF Interframe Space
DIFS
DRP
Dynamic Routing Protocol
Destination-Sequenced Distance-Vector
Dynamic Source Routing
File Transfer Protocol
DSDV
DSR
FTP
GPS
Global Positioning System
Institude of Electrical and Electronics Engineers
Internet Engineering Task Force
Internet Research Task Force
Local Area Network
IEEE
IETF
IRTF
LAN
LCC
Least Cluster Change
LQ
Localized Query
MAC
MAN
MANET
MRP
NAM
NAV
NPDU
NS2
Medium Access Control
Metropolitan Area Network
Mobile Adhoc Network
Multipoint Relay Selector
Network Animator
Network Allocation Vector
Network Protocol Data Unit
Network Simulator 2
OFDM
OLSR
OTCL
Orthogonal Frequency Division Multiplexing
Optimized Link State Routing
Object Tool Command Language
6
PAN
PCF
Personal Area Network
Point Coordination Function
PCF Interframe Space
Quality of Service
PIFS
QoS
RD
Route Delete
RN
Route Notification
RREP
RREQ
RT
Route Reply
Route Request
Routing Table
RTS
Request To Send
SIFS
SRP
Short Interframe Space
Static Routing Protocol
Signal Stability Routing
Signal Stability Table
Topology Control
SSR
SST
TC
TCL
Tool Command Language
Transmission Control Protocol
Time Division Multiple Access
Temporally Ordered Routing Algorithm
User Datagram Protocol
Virtual InterNetwork Testbed
Wide Area Network
TCP
TDMA
TORA
UDP
VINT
WAN
Wi-fi
WLAN
WMAN
WPAN
WWAN
WRP
ZRP
Wireless Fidelity
Wireless Local Area Network
Wireless Metropolitan Area Network
Wireless Personal Area Network
Wireless Wide Area Network
Wireless Routing Protocol
Zone Routing Protocol
7
Danh mục các hì nh vẽ
Hình 1. Ví dụ về mạng WLAN..................................................................................... 15
Hình 2. Hiện tượng đầu cuối ẩn.................................................................................... 17
Hình 3. Hiện tượng đầu cuối lộ..................................................................................... 18
Hình 4. Giải quyết vấn đề đầu cuối ẩn với RTS/CTS................................................... 20
Hình 5. Giải quyết vấn đề đầu cuối lộ với RTS/CTS ................................................... 20
Hình 6. Các khoảng thời gian đợi SIFS, PIFS và DIFS................................................ 21
Hình 7. Chức năng điều khiển tập trung PCF............................................................... 21
Hình 8. Mạng MANET................................................................................................. 22
Hình 9. Định tuyến hướng bảng và khởi tạo phía nguồn theo yêu cầu ........................ 27
Hình 10. Định tuyến CGSR từ nút 1 đến nút 8............................................................. 31
Hình 11. Phát hiện tuyến trong AODV......................................................................... 33
Hình 12. Tạo ra các bản ghi tuyến trong DSR.............................................................. 35
Hình 13. Việc tạo tuyến và đảm bảo tuyến trong TORA ............................................. 36
Hình 14. Lựa chọn tuyến trong ABR............................................................................ 38
Hình 15. Xây dựng lại tuyến trong ABR ...................................................................... 39
Hình 16. Lược đồ nút di động theo chuẩn mở rộng không dây của CMU monarch. ... 50
Hình 17. Lược đồ SRNode theo chuẩn mở rộng không dây của CMU monarch......... 51
Hình 18. Hình ảnh 50 nút di động, giao thức DSDV, thời gian tạm dừng 0, 1 nguồn
phát................................................................................................................................ 61
Hình 19. Số gói tin định tuyến trung bình cần phát với 1, 3 và 5 nguồn phát.............. 63
Hình 20. Số gói tin định tuyến trung bình cần phát với 4 giao thức định tuyến MANET
....................................................................................................................................... 64
Hình 21. Chi phí định tuyến chuẩn hóa theo tải với 1, 3 và 5 nguồn phát ................... 66
Hình 22. Chi phí định tuyến chuẩn hóa theo tải với 4 giao thức định tuyến MANET. 67
Hình 23. Thời gian phát hiện tuyến trung bình với 1, 3 và 5 nguồn phát..................... 69
Hình 24. Thời gian phát hiện tuyến trung bình với 2 giao thức định tuyến MANET .. 70
Hình 25. Số gói tin định tuyến trung bình cần phát trong mô hình Random Walk...... 72
Hình 26. Chi phí định tuyến chuẩn hóa theo tải trong mô hình Random Walk ........... 72
Hình 27. Thời gian phát hiện tuyến trung bình trong mô hình Random Walk............. 73
8
Danh mục các bảng
Bảng 1. So sánh giữa các giao thức định tuyến (Phân tích định tính 1) ....................... 29
Bảng 2. So sánh giữa các giao thức định tuyến (Phân tích định tính 2) ....................... 29
Bảng 3. So sánh đặc tính của các giao thức định tuyến hướng bảng............................ 41
Bảng 4. So sánh đặc tính của các giao thức định tuyến yêu cầu khởi tạo phía nguồn . 43
Bảng 5. Các đặc điểm ngữ cảnh giống nhau của thí nghiệm mô phỏng....................... 58
Bảng 6. Hình trạng mô phỏng với mô hình Random Waypoint................................... 60
Bảng 7. Hình trạng mô phỏng với mô hình Random Walk.......................................... 71
9
Chương 1. GIỚI THIỆU CHUNG
1.1. Đặt vấn đề [15]
Chúng ta biết rằng ngày nay khi mà tầm quan trọng của các máy tính trong cuộc
sống của con người tăng lên thì điều đó cũng đòi hỏi các yêu cầu mới cho việc kết nối
mạng máy tính. Ngoài các giải pháp cho mạng có dây đã được dùng từ lâu, chúng ta
thấy sự gia tăng yêu cầu đối với các giải pháp cho mạng không dây để có thể kết nối
tới Internet, đọc và gửi các thông điệp thư điện tử, trao đổi thông tin trong các cuộc
họp… Mạng không dây đặc biệt MANET (Mobile Adhoc Networking) bao gồm các
thiết bị tự tổ chức thành mạng đạt được sự giải phóng hoàn toàn khỏi cơ sở hạ tầng
mạng cố định, có chi phí truyền thông thấp và triển khai dễ dàng. Về mặt thực tiễn,
mạng MANET rất hữu ích cho các nhu cầu thiết lập mạng khẩn cấp tại những nơi xảy
ra thảm họa như hỏa hoạn, lụt lội, động đất…
Với tất cả những lý do trên, mạng MANET là một trong những lĩnh vực nghiên
cứu có tính thời sự cao và đầy thách thức của mạng không dây và công nghệ này hứa
hẹn sẽ trở nên phổ biến với cuộc sống của con người. Mạng MANET thừa kế những
đặc tính truyền thống của mạng không dây và truyền thông di động như tối ưu hóa
băng thông, điều khiển năng lượng và tăng chất lượng truyền thông. Ngoài ra, việc
truyền qua nhiều chặng, không dựa trên cơ sở hạ tầng mạng cố định và đặc biệt là sự
di chuyển tùy ý của mọi nút mạng đặt ra những vấn đề nghiên cứu mới về định tuyến,
tiết kiệm năng lượng và an ninh. Nhiều cách tiếp cận và giao thức khác nhau đã được
đề nghị để giải quyết các vấn đề phát sinh, một số phương pháp và giao thức đã được
IETF và IRTF chuẩn hóa.
1.2. Mục tiêu nghiên cứu
Với nhu cầu sử dụng mạng mọi lúc, mọi nơi và không phụ thuộc vào vị trí vật
lý, mạng không dây đặc biệt MANET cho phép các máy tính di động thực hiện các kết
nối và truyền thông với nhau không cần dựa trên cơ sở hạ tầng mạng có sẵn. Tuy
nhiên, bởi cấu trúc của mạng MANET có thể thường xuyên thay đổi do các nút có thể
gia nhập hay rời khỏi mạng nên để cho mạng có thể hoạt động thì tất cả các nút cần
phải thực hiện chức năng tương đương với một bộ định tuyến. Vấn đề định tuyến tại
tầng mạng được quan tâm đến nhiều nhất và cần tập trung giải quyết hai vấn đề cơ bản
là tìm ra đường đi từ nút phát đến nút nhận và làm thế nào để duy trì đường đi. Việc
định tuyến trong mạng MANET luôn đòi hỏi các chi phí về tài nguyên như dải thông
đường truyền, năng lượng tiêu hao trong quá trình tìm đường, dung lượng bộ nhớ cần
thiết cho việc lưu trữ bảng định tuyến và thời gian tìm đường. Đề tài luận văn này
nhằm mục đích đánh giá và so sánh chi phí tìm đường của một số giao thức định tuyến
điển hình trong mạng MANET với một số mức độ di động khác nhau của các nút
mạng. Quá trình đánh giá này được thực hiện qua lý thuyết và thông qua mô phỏng với
các nội dung bao gồm:
10
ü Nghiên cứu các đặc điểm của mạng MANET
ü Xem xét bài toán định tuyến trong mạng MANET và các giải pháp có thể
ü Phân loại các giao thức định tuyến mạng MANET
ü Xây dựng thí nghiệm mô phỏng và tích hợp một số giao thức định tuyến mạng
MANET vào bộ mô phỏng NS2
ü Đánh giá chi phí tìm đường của một số giao thức định tuyến mạng MANET với
các ngữ cảnh khác nhau. Ngữ cảnh của thí nghiệm thay đổi bằng cách:
· Thay đổi topo mạng (Số nút mạng, đường truyền cũng như vị trí ban đầu
của mỗi nút mạng)
· Thay đổi mô hình chuyển động (Mô hình Random Waypoint, Random
Walk… )
· Thay đổi mô hình sinh lưu lượng (TCP, CBR)
· Thay đổi diện tích và hình dạng vùng mô phỏng
· Thay đổi thời gian hoạt động của các nguồn sinh lưu lượng
· Thay đổi thời gian mô phỏng
1.3. Tổ chức của luận văn
Nội dung của luận văn được tổng hợp thành 4 chương chính. Chương đầu tiên
đưa ra mục tiêu nghiên cứu và tổ chức chi tiết của luận văn. Chương 2 của luận văn
trình bày tổng quan về mạng không dây WLAN và mạng không dây đặc biệt MANET.
Phần nghiên cứu tìm hiểu về việc định tuyến cũng như các yêu cầu với giao thức định
tuyến trong mạng MANET được trình bày ở chương 3. Ngoài ra, các kĩ thuật định
tuyến mạng MANET và việc phân loại các giao thức định tuyến mạng MANET cũng
được mô tả chi tiết tại chương này. Phần giới thiệu về bộ mô phỏng NS2, các thí
nghiệm, đánh giá mô phỏng và những kết quả phân tích, so sánh được mô tả ở chương
4 của luận văn. Phần cuối cùng của luận văn là kết luận những công việc mà luận văn
đã đạt được và những hướng nghiên cứu tiếp theo trong tương lai.
11
Chương 2. TỔNG QUAN VỀ MẠNG WLAN VÀ MẠNG
MANET
2.1. Giới thiệu và phâ n loại mạng không dây [15]
Những năm gần đây, công nghệ thông tin đã có những bước tiến vượt bậc và
được áp dụng vào hầu hết các mặt của đời sống xã hội như kinh tế, giáo dục, y tế, quân
sự… Xã hội càng phát triển thì nhu cầu tìm hiểu và cập nhật thông tin ngày càng tăng,
con người muốn được kết nối với thế giới ở bất kỳ chỗ nào, bất kỳ nơi đâu. Điều đó
giải thích tại sao mạng không dây lại được ra đời và phát triển mạnh. Ngày nay, chúng
ta có thể bắt gặp mạng không dây ở nhiều nơi như những văn phòng, tòa nhà, các công
ty, các tổ chức, tại các trường học, bệnh viện hay thậm chí là các quán cà phê, quán ăn
nhanh.
Nhờ những cải tiến nhanh chóng trong công nghệ mạng không dây và sự ra đời
của các dịch vụ và ứng dụng không dây mới, phạm vi truyền thông không dây đã có
những thay đổi đáng kể. Với sự nổi lên của các mạng tế bào thế hệ thứ ba làm tăng tốc
độ truyền dữ liệu, cho phép cung cấp các dịch vụ dữ liệu di động đa dạng với tốc độ
cao hơn. Trong khi đó thì các chuẩn mới cho sóng vô tuyến phạm vi ngắn như
Bluetooth, 802.11, HiperLAN và truyền hồng ngoại đang hỗ trợ để tạo phạm vi rộng
hơn cho các ứng dụng mới tại các hộ gia đình hay xí nghiệp, cho phép truyền thông
không dây dữ liệu đa phương tiện được tốt hơn.
Nói chung, khái niệm mạng không dây ám chỉ mạng sử dụng phương tiện
truyền là sóng hồng ngoại hoặc vô tuyến điện để chia sẻ thông tin và các tài nguyên
giữa các thiết bị. Nhiều kiểu thiết bị không dây đang được sử dụng phổ biến ngày nay
như các thiết bị cá nhân cầm tay (PDA), các máy tính xách tay (notebook, netbook),
các máy điện thoại di động, cảm biến không dây (wireless sensor), các thiết bị nhận vệ
tinh… Truyền thông không dây có các đặc tính như sau:
ü Nhiễu cao hơn trong khi độ tin cậy thấp hơn
o Các tín hiệu hồng ngoại chịu nhiễu từ ánh sáng mặt trời và các nguồn
nhiệt và có thể bị che chắn bởi nhiều loại vật cản. Các tín hiệu vô tuyến
điện thường có thể xuyên qua nhiều loại vật cản tuy nhiên chúng có thể
bị nhiễu bởi các thiết bị điện và điện tử.
o Truyền quảng bá đồng nghĩa với việc tất cả các thiết bị có khả năng gây
nhiễu cho nhau
o Tự nhiễu bởi đặc tính truyền đa đường (multi-path fading)
ü Băng thông và tốc độ truyền thấp hơn
o Thông thường tốc độ truyền của mạng không dây chậm hơn và không ổn
định so với mạng có dây, dẫn đến độ trễ và biến động trễ (jitter) cao hơn.
Đây là nguyên nhân làm giảm chất lượng dịch vụ.
ü Các điều kiện mạng biến đổi cao và thất thường
12
o Tỉ lệ mất mát dữ liệu cao hơn do nhiễu
o Việc di chuyển của người dùng dẫn đến việc bị ngắt kết nối thường
xuyên
o Sự thay đổi kênh khi những người dùng di chuyển vòng quanh
o Năng lượng nhận được giảm dần theo khoảng cách
ü Các tài nguyên tính toán và năng lượng bị hạn chế.
o Sức mạnh tính toán, bộ nhớ, kích thước ổ đĩa, dung lượng pin bị hạn chế
cũng như việc giới hạn kích cỡ thiết bị, trọng lượng và chi phí.
o Sự hạn chế của các tần số với các quy định khắt khe
o Sự khan hiếm và đắt của phổ
o Giới hạn kích cỡ thiết bị dẫn tới việc các kết quả bị giới hạn trong giao
diện người dùng và màn hình
ü Độ bao phủ dịch vụ bị hạn chế
o Do việc giới hạn công suất phát của thiết bị mạng dẫn đến khoảng cách
truyền bị hạn chế, việc thực thi dịch vụ trong mạng không dây phải đối
mặt với nhiều ràng buộc và chịu nhiều thách thức hơn so với mạng có
dây.
ü Thực hiện bảo mật khó hơn
o Do giao diện sóng vô tuyến là có thể bị truy cập bởi bất kỳ người nào
trong phạm vi phủ sóng của thiết bị phát, đảm bảo an ninh mạng không
dây là khó thực thi hơn.
Hiện nay có nhiều kiểu mạng không dây tồn tại và có thể được phân loại theo
nhiều cách đa dạng phụ thuộc vào tiêu chuẩn được lựa chọn cho việc phân loại.
2.1.1. Phâ n loại theo định dạng và kiến trúc mạng
Các mạng không dây có thể được chia thành hai kiểu lớn dựa trên cách làm thế
nào mạng được khởi tạo và kiến trúc mạng bên dưới. Người ta có thể phân loại thành:
ü Mạng dựa trên cơ sở hạ tầng: Mạng dựa trên cơ sở hạ tầng được tạo bởi các nút
mạng có kết nối không dây, có thể di động, chúng truyền thông với nhau một
cách trực tiếp hoặc thông qua một nút thuộc mạng có dây (nút cố định), nút này
đồng thời đóng vai trò nút cổng, qua đó các nút mạng không dây có thể kết nối
với các máy tính trong mạng có dây và Internet. Lấy ví dụ mạng gồm một số
nút di động không dây kết nối với một hoặc một vài AP (Access Point), các AP
này có thể kết nối với mạng LAN có dây và Internet. WLAN thuộc kiểu này.
ü Mạng không có cơ sở hạ tầng (MANET): Trong trường hợp này mạng được tạo
một cách động thông qua việc kết hợp của một tập tùy ý các nút độc lập. Không
có sự sắp xếp trước bất chấp vai trò xác định của mỗi nút. Thay vì đó, mỗi nút
đưa ra quyết định một cách độc lập dựa trên tình huống mạng không cần sử
dụng cơ sở hạ tầng mạng tồn tại trước. Lấy ví dụ, hai chiếc máy tính được trang
bị với cạc mạng không dây có thể thiết lập mạng độc lập mỗi khi chúng nằm
13
trong phạm vi của thiết bị kia. Trong mạng MANET, mỗi nút thực hiện chức
năng tương đương với một bộ định tuyến, cộng tác với các nút khác để thực
hiện việc phát hiện và bảo đảm các tuyến tới các nút trong mạng.
2.1.2. Phâ n loại theo phạm vi bao phủ truyền thô ng
Giống như các mạng có dây, các mạng không dây có thể được phân loại thành
các kiểu khác nhau dựa trên khoảng cách mà dữ liệu được truyền, bao gồm:
ü WWAN (Wireless Wide Area Network): Là mạng WAN không dây dựa trên cơ
sở hạ tầng bao gồm MSCs và trạm BS,… làm việc để cho phép các người dùng
thiết lập các kết nối không dây sử dụng sóng vô tuyến thay vì cáp đồng truyền
thống. Các kết nối này có thể được tạo ra trên các phạm vi địa lý lớn, thậm chí
bao trùm các thành phố hoặc các nước bằng việc sử dụng nhiều trạm BS hoặc
hệ thống truyền thông vệ tinh. Các mạng máy tính dựa trên các mạng viễn
thông kiểu tế bào (CDMA hoặc GSM) và các hệ thống vệ tinh là những ví dụ
điển hình về các mạng WWAN.
ü WMAN (Wireless Metropolitan Area Network): Là các mạng không dây cố định
cỡ thành phố, có cơ sở hạ tầng, cho phép người dùng thiết lập các kết nối không
dây dải tần rộng giữa nhiều vị trí trong một vùng dân cư ví dụ như giữa nhiều
tòa nhà, văn phòng trong một thành phố hoặc trong khuôn viên của trường đại
học mà không phải trả chi phí cao cho việc chạy cáp quang hoặc cáp đồng.
Ngoài ra, mạng WMAN có thể dùng làm mạng dự phòng cho các mạng có dây
khi các mạng có dây không khả dụng. Cả sóng vô tuyến và ánh sáng hồng ngoại
có thể được sử dụng trong WMAN để truyền dữ liệu. Tổ chức IEEE có một tập
các chuẩn về WMAN trong IEEE 802.16 và khuyến nghị sử dụng trong thực tế
để hỗ trợ việc phát triển và triển khai mạng WMAN băng thông rộng.
ü WLAN (Wireless Local Area Network): Là mạng LAN sử dụng đường truyền
không dây để liên kết các thiết bị, các thiết bị thường truyền thông với nhau
thông qua điểm truy cập – AP (Access Point), phương pháp truy cập đường
truyền thường là CSMA/CA với tầng vật lý sử dụng phương pháp trải phổ hoặc
OFDM. Điều này cho phép người dùng di động có thể di chuyển xung quanh
AP trong phạm vi phủ sóng của nó mà vẫn duy trì được kết nối mạng. WLAN
ngày càng trở nên phổ biến ở các hộ gia đình bởi việc cài đặt dễ dàng và sự phổ
biến của các máy tính xách tay.
ü WPAN (Wireless Personal Area Network): Là mạng không dây cá nhân được
tạo bởi sự kết nối vô tuyến giữa các thiết bị không dây như PDA, điện thoại di
động hay máy tính cá nhân… trong phạm vi ngắn. WPAN có tầm phủ sóng
ngắn thông thường trong phạm vi 10m. Hai công nghệ WPAN chính là
Bluetooth và ánh sáng hồng ngoại. Bluetooth là công nghệ sử dụng sóng vô
tuyến thay thế cáp để truyền dữ liệu trong khoảng cách 9-10m. Công nghệ
truyền hồng ngoại có thể kết nối các thiết bị trong phạm vi 1m. WPAN đang
14
được thúc đẩy phát triển mạnh mẽ bởi độ phức tạp thấp, tiêu thụ ít năng lượng
và tương thích với các mạng 802.11 [15].
2.1.3. Phâ n loại theo công nghệ truy cập đường truyền
Phụ thuộc vào các chuẩn xác định (tần số, phương pháp truyền sóng và điều
khiển truy cập đường truyền… ) các mạng không dây có thể được phân loại như sau:
ü Các mạng GSM
ü Các mạng TDMA
ü Các mạng CDMA
ü Các mạng vệ tinh
ü Các mạng Wi-fi (802.11)
ü Các mạng Hyperlan2
ü Các mạng bluetooth
ü Các mạng hồng ngoại
2.1.4. Phâ n loại theo các ứng dụng mạng
Các mạng không dây cũng có thể được phân loại dựa trên đối tượng sử dụng
mạng và các ứng dụng mà mạng cung cấp, ví dụ:
ü Các mạng doanh nghiệp
ü Các mạng gia đình
ü Các mạng quân sự
ü Các mạng cảm biến
ü Các mạng xe cộ tự động
2.2. Mạng LAN không dây (WLAN)
2.2.1. Khá i niệm về WLAN
Các mạng cục bộ không dây cho phép người dùng thiết lập các kết nối không
dây giữa các thiết bị trong một vùng nhỏ, thông thường thuộc một tổ chức hay trong
một tòa nhà, hoặc trong một không gian công cộng như sân bay, sân ga.
WLAN có thể được sử dụng trong các không gian cần kết nối mạng tạm thời,
hoặc tại những nơi trong đó việc chạy cáp là không được phép hoặc khó thực hiện.
WLAN thường là phần mở rộng của mạng LAN có dây hoặc của mạng Internet để hỗ
trợ cho người dùng có thể làm việc ở nhiều vị trí khác nhau. Các văn phòng, hộ gia
đình, cửa hàng cà phê hay các sân bay thường là các điểm nóng cho việc cài đặt
WLAN. Hình 1 là ví dụ minh họa về mạng WLAN.
15
Hình 1. Ví dụ về mạng WLAN
WLAN có thể vận hành trong chế độ có cơ sở hạ tầng hoặc MANET. Trong chế
độ có cơ sở hạ tầng, các trạm không dây kết nối tới các điểm truy cập không dây (AP)
có chức năng như là cầu nối các trạm không dây với nhau và kết nối chúng với mạng
LAN hoặc Internet. Một số AP kết nối với một mạng LAN có vai trò như là xương
sống mạng WLAN. Trong chế độ MANET, nhiều trạm không dây trong một khu vực
hạn chế có thể cộng tác với nhau để tạo ra một mạng tạm thời mà không cần sử dụng
các AP, nếu chúng không yêu cầu truy cập vào các tài nguyên mạng. Các mạng
WLAN ngày nay nói chung đều theo chuẩn 802.11. Theo chuẩn con 802.11a và
802.11b, việc truyền dữ liệu có thể đạt tới tốc độ từ 11Mbps tới 54Mbps.
Mạng WLAN ra đời với rất nhiều ưu điểm đáng kể như sau:
ü Sự tiện lợi: Mạng không dây cho phép người dùng truy xuất tài nguyên mạng ở
bất kỳ nơi đâu trong khu vực được triển khai (tòa nhà hay văn phòng). Với sự
gia tăng số người sử dụng máy tính xách tay và thiết bị di động thì đó là một
điều rất thuận lợi.
ü Khả năng di động: Với sự phát triển của các mạng không dây công cộng, người
dùng có có thể truy cập Internet ở bất kỳ đâu.
ü Hiệu quả: Người dùng có thể duy trì kết nối mạng khi họ di chuyển từ vị trí này
đến vị trí khác.
ü Triển khai nhanh, dễ và chi phí thấp: Việc thiết lập hệ thống mạng không dây
ban đầu chỉ cần tối thiểu một điểm truy cập. Với mạng dùng cáp, phải tốn thêm
chi phí và có thể gặp khó khăn trong việc triển khai hệ thống cáp ở nhiều nơi
trong tòa nhà.
16
ü Khả năng mở rộng dễ dàng: Mạng không dây có thể đáp ứng tức thì khi gia
tăng số lượng người dùng. Với hệ thống mạng dùng cáp cần phải gắn thêm cáp.
Bên cạnh những ưu điểm mà WLAN có được, nó cũng tồn tại những nhược điểm
như sau:
ü Bảo mật khó khăn hơn: Do môi trường kết nối không dây là không khí nên khả
năng bị tấn công là rất cao.
ü Phạm vi nhỏ hơn: Một mạng chuẩn 802.11g với các thiết bị chuẩn chỉ có thể
hoạt động tốt trong phạm vi vài chục mét. Nó phù hợp trong một căn nhà,
nhưng với một tòa nhà lớn thì không đáp ứng được nhu cầu. Để đáp ứng cần
phải mua thêm bộ lặp hay điểm truy cập, dẫn đến chi phí gia tăng.
ü Độ tin cậy thấp hơn: Vì sử dụng sóng vô tuyến để truyền thông nên việc bị
nhiễu, tín hiệu bị giảm do tác động của các thiết bị khác (lò vi sóng chẳng hạn)
là không tránh khỏi và làm giảm đáng kể hiệu quả hoạt động của mạng.
ü Tốc độ thấp hơn: Tốc độ của mạng không dây (1- 125 Mbps) chậm hơn so với
mạng sử dụng cáp (100Mbps đến hàng Gbps).
2.2.2. Lịch sử ra đời mạng WLAN [22]
Công nghệ WLAN xuất hiện lần đầu tiên vào cuối những năm 1990, khi những
nhà sản xuất giới thiệu những sản phẩm của họ hoạt động trong băng tần 900MHz.
Những giải pháp được áp dụng trong các sản phẩm này (không được thống nhất giữa
những nhà sản xuất) cung cấp tốc độ truyền dữ liệu 1Mbps, thấp hơn nhiều so với tốc
độ 10Mbps của hầu hết các mạng LAN sử dụng cáp hiện thời.
Sau đó không lâu, vào năm 1992, các nhà sản xuất bắt đầu bán những sản phẩm
WLAN sử dụng băng tần 2.4GHz. Mặc dù những sản phẩm này đã có tốc độ truyền dữ
liệu cao hơn nhưng chúng vẫn sử dụng những giải pháp riêng của mỗi nhà sản xuất và
không được công bố rộng rãi. Nhu cầu cần thiết cho việc hoạt động thống nhất giữa
các thiết bị ở những dải tần số khác nhau dẫn đến việc một số tổ chức bắt đầu phối hợp
xây dựng và phát triển ra những chuẩn mạng không dây chung. Kết quả là vào năm
1997, tổ chức IEEE đã phê chuẩn sự ra đời của chuẩn 802.11, và cũng được biết với
tên gọi WIFI cho các mạng WLAN. Chuẩn 802.11 hỗ trợ ba phương pháp truyền tín
hiệu, trong đó có phương pháp truyền tín hiệu vô tuyến ở tần số 2.4Ghz.
Năm 1999, tổ chức IEEE đã thông qua hai sự bổ sung cho chuẩn 802.11 là các
chuẩn 802.11a và 802.11b, chúng định nghĩa những phương pháp truyền tín hiệu mới
nhờ đó những thiết bị WLAN dựa trên chuẩn 802.11b đã nhanh chóng trở thành công
nghệ không dây vượt trội. Các thiết bị WLAN 802.11b truyền phát ở tần số 2.4Ghz,
cung cấp tốc độ truyền dữ liệu có thể lên tới 11Mbps. Mục đích của việc tạo ra chuẩn
IEEE 802.11b là để đáp ứng những đặc điểm về tính hiệu dụng, thông lượng và mức
độ bảo mật ngang với mạng có dây.
Vào năm 2003, tổ chức IEEE công bố thêm một sự cải tiến đó là chuẩn
802.11g, theo chuẩn này có thể truyền nhận thông tin ở cả hai dải tần số 2.4GHz và
17
5GHz và có thể nâng tốc độ truyền dữ liệu lên đến 54Mbps. Ngoài ra, những sản phẩm
áp dụng chuẩn 802.11g cũng có thể tương thích ngược với các thiết bị theo chuẩn
802.11b. Ngày nay, chuẩn 802.11g đã đạt đến tốc độ trong khoảng 108Mbps-
300Mbps.
2.2.3. Giao thức tầng con MAC trong WLAN [12]
Điểm nổi bật của mạng WLAN là giao thức tầng con MAC CSMA/CA điều
khiển truy cập đường truyền chung không dây sử dụng sóng radio. Giống như mạng
LAN có dây (mạng Ethernet), WLAN cũng sử dụng đa truy cập có cảm nhận sóng
mang (CSMA) để điều khiển truy cập môi trường truyền. Trong mạng Ethernet, việc sử
dụng thêm cơ chế phát hiện xung đột CD (Collision Detect) là hiệu quả và khả thi nhờ
việc sử dụng phần cứng. Kết quả là các trạm có thể phát hiện ra xung đột trong quá
trình đang truyền dữ liệu. Giao thức CSMA/CD có thể được mô tả một cách đơn giản
như sau, nếu một trạm muốn truyền gói tin, nó sẽ lắng nghe xem trên đường truyền có
sóng mang (carrier) hay không. Nếu đường truyền rỗi nó thực hiện truyền một gói tin.
Ngược lại, nếu đường truyền bận (đang được sử dụng), nó sẽ tiếp tục lắng nghe cho
đến khi đường truyền rỗi thì truyền gói tin đi với một xác suất nhất định. Ngoài ra
trong quá trình truyền thì trạm vẫn lắng nghe để đảm bảo phát hiện được xung đột đối
với gói tin đang truyền. Nếu phát hiện thấy có xung đột, trạm sẽ dừng ngay việc truyền
trong một khoảng thời gian trước khi tiếp tục nghe đường truyền theo thuật toán như
trên.
Tuy nhiên với mạng WLAN, không thể sử dụng giao thức CSMA/CD do các
đặc tính truyền sóng trong không khí của mạng WLAN khác rất nhiều so với truyền
sóng trong cáp đồng, dẫn tới các hiện tượng không mong muốn được mô tả sau đây.
ü Hiện tượng đầu cuối ẩn (Hidden Terminal)
Hiện tượng đầu cuối ẩn được minh họa trên hình 2. Giả sử trạm 2 nằm trong
vùng phủ sóng của trạm 1 và 3. Hai trạm 1 và 3 không nằm trong vùng phủ sóng của
nhau. Nếu trạm 1 truyền gói tin dữ liệu cho trạm 2, do trạm 3 không nằm trong vùng
phủ sóng của trạm 1 nên trạm 3 không cảm nhận được sóng mang của trạm 1. Do đó,
nếu trạm 3 truyền dữ liệu cho trạm 2 thì dẫn đến việc xung đột tại trạm 2.
Hình 2. Hiện tượng đầu cuối ẩn
ü Hiện tượng đầu cuối lộ (Exposed Terminal)
Hiện tượng đầu cuối lộ được minh họa trên hình 3. Giả sử trạm 2 muốn truyền
dữ liệu cho trạm 1, trong lúc đó trạm 3 muốn truyền dữ liệu cho trạm 4 nhưng do trạm
18
3 cảm nhận sóng mang thấy đường truyền đang bận nên không truyền trong khi nó có
thể truyền dữ liệu cho trạm 4 mà không gây ra xung đột tại trạm 1.
Hình 3. Hiện tượng đầu cuối lộ
Để khắc phục các đặc điểm nêu trên, trong WLAN sử dụng cơ chế đa truy cập
sử dụng sóng mang tránh xung đột (CSMA/CA) với việc sử dụng gói tin biên nhận
ACK. Khi một trạm muốn truyền dữ liệu, nó lắng nghe xem kênh truyền có bận hay
không (đây chính là thực hiện chức năng CS). Có hai kiểu chức năng cảm nhận sóng
mang trong WLAN bao gồm chức năng cảm nhận sóng mang vật lý và cảm nhận sóng
mang ảo NAV (Network Allocation Vector). Nếu cả 2 chức năng cảm nhận sóng mang
đều cho biết môi trường truyền là bận, tầng MAC sẽ báo cáo cho các tầng cao hơn biết
việc môi trường truyền bận. NAV là một bộ định thời cho biết khoảng thời gian mà
môi trường truyền sẽ được đặt trước. Phần lớn các khung theo chuẩn 802.11 chứa
trường duration được sử dụng để đặt trước việc sử dụng môi trường truyền một
khoảng thời gian xác định. Các trạm thiết lập giá trị NAV là thời gian chúng mong
muốn sử dụng đường truyền và tiến hành đếm ngược từ giá trị NAV tới 0. Khi giá trị
NAV khác không, chức năng cảm nhận sóng mang ảo cho biết môi trường là bận,
ngược lại khi giá trị NAV tới 0, môi trường truyền là rỗi.
Khi quá trình CS hoàn thành, nếu kênh truyền rỗi, trạm chỉ phải chờ một
khoảng thời gian DIFS (DCF Interframe Space) - thời gian nhỏ nhất mà các nút mạng
phải chờ trước khi sử dụng kênh truyền để truyền một gói tin dữ liệu (đây chính là
thực hiện chức năng MA). Trong trường hợp ngược lại, với kênh truyền bận thì trạm
phải đợi một khoảng thời gian DIFS cộng thêm khoảng trễ ngẫu nhiên gọi là “back-off
time” rồi lặp lại việc lắng nghe đường truyền để tránh việc xảy ra đụng độ. Sau khoảng
thời gian ngắn nhất DIFS tiếp theo, nếu môi trường rảnh rỗi thì giá trị back-off của
trạm giảm đi một đơn vị. Nếu môi trường vẫn bận thì giá trị back-off này được giữ
nguyên cho lần DIFS kế tiếp. Khi giá trị back-off giảm về không thì trạm có thể sử
dụng đường truyền (đây chính là thực hiện chức năng CA).
Tránh xung đột (CA) trong giao thức CSMA/CA sử dụng chức năng cộng phân
tán DCF hoặc chức năng điều khiển tập trung PCF
* Chức năng cộng phân tán DCF (Distributed Coordination Function)
Chức năng cộng phân tán DCF được thực thi trong giao thức CSMA/CA với
thuật toán trì hoãn (back-off) việc truyền gói tin một khoảng thời gian tăng theo hàm
mũ cơ số 2 của số lần phát hiện thấy đường truyền bận. DCF yêu cầu mỗi trạm muốn
truyền phải lắng nghe trạng thái kênh truyền trong khoảng thời gian DIFS. Nếu kênh
19
truyền là bận trong suốt khoảng DIFS, trạm sẽ trì hoãn việc truyền của nó. Với mạng
có nhiều trạm tranh chấp môi trường truyền không dây, nếu các trạm đều cảm nhận
kênh truyền bận và trì hoãn việc truy cập của chúng một khoảng thời gian giống nhau,
tất cả các trạm hầu như cùng lúc phát hiện thấy kênh truyền được giải phóng và cố
gắng để chiếm giữ kênh truyền. Kết quả là xung đột sẽ thể xảy ra. Để tránh vấn đề
xung đột này, DCF xác định giá trị back-off ngẫu nhiên áp dụng cho trạm để trì hoãn
thêm việc truy cập của nó với đường truyền. Độ dài của chu kỳ back-off được xác định
bởi công thức:
BackoffTime = random() x aSlotTime
Sau mỗi khoảng thời gian DIFS thì giá trị back-off ngẫu nhiên sẽ giảm đi một
đơn vị nếu đường truyền rỗi. Đến khi giá trị back-off giảm về không thì trạm có thể sử
dụng đường truyền. Tuy nhiên, trong trường hợp có một trạm khác vẫn đang sử dụng
đường truyền trước khi giá trị back-off giảm về không thì trạm vẫn giữ giá trị đó cho
lần DIFS tiếp theo. Chức năng cộng phân tán có sử dụng gói tin biên nhận ACK tại
bên nhận để thông báo đã nhận được gói tin thành công. Để làm được điều đó, bên
nhận dữ liệu phải chiếm được đường truyền. Để gói tin biên nhận ACK không phải
tranh chấp đường truyền và được truyền ngay, quá trình truyền ACK bỏ qua thuật toán
back-off ngẫu nhiên và chỉ phải đợi một khoảng thời gian SIFS (Short Interframe
Space) nhỏ hơn DIFS.
Giao thức CSMA/CA không loại bỏ được hiện tượng xung đột. Việc sử dụng
gói tin ACK giúp bên gửi biết được việc gửi gói tin có thành công hay không, nghĩa là
gián tiếp xác định được xung đột. Tuy nhiên, việc sử dụng CSMA/CA + ACK không
khắc phục được các hiện tượng đầu cuối ẩn và đầu cuối lộ. Để khắc phục được các
hiện tượng nói trên, người ta đã đề xuất việc sử dụng thêm các gói tin điều khiển RTS
và CTS.
ü DCF sử dụng gói tin điều khiển RTS/CTS (Request To Send/Clear To Send)
Gói tin điều khiển RTS chứa địa chỉ của trạm nhận và thời gian truyền dữ liệu
cần thiết. Khi trạm nhận nhận được gói tin RTS, nó sẽ đợi khoảng thời gian SIFS và
gửi lại gói tin CTS. Khi trạm gửi nhận được gói tin CTS, nó chờ khoảng thời gian
SIFS sau đó bắt đầu truyền dữ liệu và đợi gói tin biên nhận ACK. Áp dụng hai kiểu
gói tin này vào việc giải quyết hiện tượng đầu cuối ẩn và đầu cuối lộ như sau.
Với hiện tượng đầu cuối ẩn, khi trạm 1 truyền quảng bá gói tin cho trạm 2, do
trạm 3 nằm ngoài vùng phủ sóng của trạm 1 nên không cảm nhận được sóng mang và
cho rằng đường truyền vẫn rỗi. Trạm 2 nhận được gói tin RTS sẽ tiến hành gửi lại gói
tin CTS. Do trạm 3 nằm trong vùng phủ sóng của trạm 2 nên khi nhận được gói tin
CTS biết là đường truyền đang bận nên không gửi gói tin cho trạm 2. Hình 4 minh họa
việc giải quyết vấn đề đầu cuối ẩn với gói tin điều khiển RTS/CTS.
20
Hình 4. Giải quyết vấn đề đầu cuối ẩn với RTS/CTS
Với hiện tượng đầu cuối lộ, khi trạm 2 quảng bá gói tin RTS tới trạm 1, trạm 3
nằm trong vùng phủ sóng trạm 2 nên cảm nhận được sóng mang và trì hoãn việc
truyền dữ liệu cho trạm 4. Tuy nhiên khi trạm 1 phản hồi gói tin CTS cho trạm 2, do
trạm 3 nằm ngoài vùng phủ sóng với trạm 1 nên không nhận được gói tin CTS này. Do
đó, trạm 3 nghĩ rằng trạm 1 đã ra ngoài phạm vi phủ sóng và tiến hành truyền dữ liệu
bình thường cho trạm 4. Hình 5 minh họa việc giải quyết vấn đề đầu cuối lộ với gói tin
điều khiển RTS/CTS.
Hình 5. Giải quyết vấn đề đầu cuối lộ với RTS/CTS
* Chức năng điều khiển tập trung PCF (Point Coordination Function)
PCF là chức năng tránh xung đột của giao thức CSMA/CA được thực hiện bên
trong AP để quản lý việc phân phát các khung đến và đi từ AP mà không dẫn đến
tranh chấp đường truyền. Việc thực hiện PCF cần phải có một AP, do đó nó chỉ được
áp dụng cho các mạng WLAN có cơ sở hạ tầng và không được áp dụng cho mạng
MANET.
Trong PCF, thời gian được chia thành các siêu khung (super frame) được bắt
đầu với khung dẫn đường (beacon frame) và mỗi siêu khung lại được chia thành hai
giai đoạn: tranh chấp CP (Contention Period) và không tranh chấp CFP (Contention
Free Period). Các AP có vai trò quyết định xem trạm nào phải chờ sau khoảng thời
gian PIFS (PCF Interframe Space) để truy cập đường truyền. Giá trị của PIFS nằm
giữa SIFS và DIFS, nhờ đó PCF cho phép các trạm truy cập vào môi trường truyền
trước DCF nhưng vẫn đảm bảo các gói tin biên nhận ACK có thể giành được đường
truyền. Hình 6 minh họa các khoảng thời gian đợi để có thể sử dụng đường truyền:
21
Hình 6. Các khoảng thời gian đợi SIFS, PIFS và DIFS
Hoạt động của PCF được mô tả chi tiết trong hình 7. Ban đầu AP cho phép trạm
1 truyền dữ liệu bằng cách gửi cho trạm 1 gói tin dữ liệu D1. Trạm 1 muốn truyền dữ
liệu nên gửi gói tin U1 trở lại AP sau khoảng thời gian SIFS. Sau khi AP nhận được
gói tin từ trạm 1, AP chỉ định trạm 2 truyền dữ liệu sau khoảng thời gian đợi SIFS.
Trạm 2 cũng muốn truyền dữ liệu nên cũng gửi lại gói tin U2. Sau khoảng thời gian
SIFS, AP lại chỉ định trạm 3 truyền dữ liệu. Lúc này trạm 3 không muốn truyền dữ
liệu nên AP không nhận được gói tin U3. Sau khoảng thời gian PIFS, AP lại tiếp tục
chỉ định cho trạm 4 truyền dữ liệu. Trạm 4 muốn truyền dữ liệu nên gửi lại gói tin U4.
AP thông báo khoảng thời gian tranh chấp sắp hết bằng cách sử dụng tín hiệu CF-END
(Contention Free End).
Có thể thấy rằng, trong khoảng thời gian không tranh chấp (CFP) thì tại một
thời điểm chỉ có một trạm truy cập môi trường truyền, trạm đó có thể gửi hoặc không
gửi dữ liệu, nhờ đó tránh được việc xảy ra xung đột.
Hình 7. Chức năng điều khiển tập trung PCF
22
2.3. Mạng không dây đặc biệt MANET [15]
Mạng không dây đặc biệt MANET bao gồm các thiết bị di động có hỗ trợ giao
tiếp mạng không dây truyền thông với nhau không cần sử dụng cơ sở hạ tầng mạng và
các vùng quản trị trung tâm. Mỗi nút trong mạng MANET hoạt động như là một bộ
định tuyến độc lập và tuyến đường giữa các nút trong mạng MANET có thể bao gồm
nhiều chặng. Hình 8 chỉ ra ví dụ về mạng MANET và cấu hình truyền thông của nó.
Hình 8. Mạng MANET
Như đã chỉ ra ở trên, mạng MANET có thể bao gồm nhiều thiết bị tính toán cá
nhân bao gồm máy tính xách tay, thiết bị cầm tay cá nhân… Mỗi nút có thể truyền
thông trực tiếp với các nút khác nằm trong phạm vi truyền thông của nó. Để truyền
thông với các nút nằm ngoài phạm vi của nó, nút cần sử dụng các nút trung gian để
truyền thông điệp theo từng chặng.
2.3.1. Sự phát triển và cá c ứng dụng của mạng MANET
Mạng MANET ban đầu là mạng vô tuyến chuyển mạch gói được tài trợ và phát
triển bởi tổ chức DARPA từ những năm đầu thập niên 1970. Sau đó vào năm 1983,
mạng SURANs (Survivable Radio Networks) được đề xuất để hỗ trợ mạng có quy mô
lớn hơn. Ngày nay mạng MANET được tổ chức IEEE quy chuẩn trong 802.11.
Về mặt thực tiễn, mạng MANET rất hữu ích cho các nhu cầu truyền thông
mang tính chất tạm thời như trong một cuộc họp hay hội thảo. Trong những trường
hợp này nếu chúng ta thiết lập mạng sử dụng cơ sở hạ tầng sẽ rất tốn kém cả về thời
gian lẫn chi phí thực hiện. Ngoài ra trong các tình trạng khẩn cấp tại nơi xảy ra những
thảm họa như hỏa hoạn, lũ lụt, động đất…các cơ sở hạ tầng có thể bị phá hỏng dẫn đến
hệ thống mạng bị ngắt không thể kết nối. Trong trường hợp này việc thiết lập nhanh
mạng MANET là một giải pháp hữu ích. Nhờ đó có thể đáp ứng được việc truyền
thông nhằm khắc phục, giảm thiểu thiệt hại sau thiên tai. Đối với những vùng sâu,
vùng xa, những nơi có địa hình hiểm trở việc thiết lập hệ thống mạng có cơ sở hạ tầng
để đáp ứng việc truyền thông là khó khăn và tốn chi phí. Vậy nên, mạng MANET là
một lựa chọn tốt cho việc truyền thông tại những nơi như thế này.
23
2.3.2. Các đặc điểm của mạng MANET
Khi nghiên cứu, đánh giá hiệu năng của mạng MANET cần chú ý một số đặc
điểm nổi bật của mạng MANET như sau:
ü Tự trị và không có cơ sở hạ tầng: Mạng MANET không phụ thuộc vào bất kỳ
cơ sở hạ tầng mạng hay vùng quản trị trung tâm được thiết lập sẵn nào. Mỗi nút
vận hành trong chế độ điểm nối điểm phân tán, hoạt động như là bộ định tuyến
độc lập và tạo ra dữ liệu độc lập.
ü Định tuyến nhiều chặng: Không sử dụng các bộ định tuyến chuyên dụng cần
thiết, mỗi nút hoạt động như là bộ định tuyến và chuyển tiếp các gói tin của mỗi
nút khác để cho phép chia sẻ thông tin giữa các nút di động.
ü Các nút mạng có nguồn năng lượng dung lượng thấp: Các nút mạng di động
nói chung đều chạy pin nên vấn đề tiết kiệm năng lượng là rất quan trọng. Điều
này trở thành vấn đề lớn hơn trong các mạng MANET bởi vì mỗi nút vừa hoạt
động như là hệ thống đầu cuối vừa là một bộ định tuyến cùng một lúc, do đó
cần nhiều năng lượng hơn cho việc chuyển tiếp các gói tin của các nút khác
trong mạng.
ü Cấu trúc mạng thay đổi động: Trong các mạng MANET, vì các nút có thể di
chuyển tùy ý, nên tô-pô của mạng có thể thay đổi thường xuyên và không thể
dự đoán trước. Kết quả là việc xác định tuyến cần thực hiện thường xuyên hơn
và khả năng mất mát gói tin cao hơn do việc xác định tuyến không kịp thời.
ü Giới hạn băng thông và chất lượng: Các nút di động truyền thông với nhau bị
giới hạn về băng thông, dung lượng biến đổi và dễ xảy ra lỗi và tắc nghẽn.
ü Đảm bảo an ninh mạng khó hơn: Các mạng không dây di động nói chung dễ bị
tổn thương bởi các mối đe dọa về an ninh thông tin cũng như an ninh vật lý hơn
so với các mạng có dây cố định. Việc sử dụng các kênh không dây quảng bá mở
và chia sẻ đồng nghĩa với việc các nút thiếu sự bảo vệ và dễ gặp các đe dọa an
ninh. Ngoài ra, bởi vì mạng MANET là mạng không có cơ sở hạ tầng, nên về
cơ bản nó phải dựa vào các giải pháp an toàn riêng rẽ của mỗi nút di động bởi
việc điều khiển an ninh trung tâm là khó thực thi. Các yêu cầu an ninh chính
trong mạng MANET bao gồm:
o Tin cậy: Ngăn cản việc nghe trộm.
o Điều khiển truy cập: Bảo vệ truy cập.
o Toàn vẹn dữ liệu: Ngăn cản việc can thiệp lưu lượng (truy cập, sửa đổi,
loại bỏ lưu lượng) .
o Tấn công từ chối dịch vụ từ các nút độc hại.
ü Khó đảm bảo chất lượng dịch vụ: Đảm bảo chất lượng dịch vụ (QoS) là quan
trọng cho việc phân phối thành công lưu lượng mạng đa phương tiện. Các yêu
cầu về QoS thông thường ám chỉ tới một tập các độ đo bao gồm thông lượng, tỉ
lệ mất mát gói tin, độ trễ, thăng giáng độ trễ, tỉ suất lỗi…Với cấu hình mạng
luôn thay đổi động, băng thông liên kết và chất lượng bị giới hạn, sự biến thiên
24
về thông lượng của liên kết, thật là khó để đạt được yêu cầu về đảm bảo chất
lượng dịch vụ trong mạng MANET.
25
Chương 3. CÁ C GIAO THỨC ĐỊNH TUYẾN MẠNG MANET
3.1. Giới thiệu về bài toán định tuyến [15]
Chúng ta biết rằng các thay đổi thường xuyên và không thể dự đoán được trong
cấu trúc mạng làm cho mạng MANET có tính động cao khiến việc định tuyến giữa các
nút di động trong mạng thêm khó khăn và phức tạp. Những thách thức này cùng với
tầm quan trọng đặc biệt của các giao thức định tuyến trong việc thiết lập các truyền
thông giữa các nút di động khiến cho lĩnh vực định tuyến có lẽ là lĩnh vực nghiên cứu
tích cực nhất trong mạng MANET. Đặc biệt hơn trong những năm gần đây, số lượng
các giao thức định tuyến được đề nghị nhiều hơn và hiệu năng của chúng trong những
môi trường mạng và các điều kiện lưu lượng giống nhau được nghiên cứu và so sánh.
Kết quả cuối cùng của cộng đồng mạng MANET là cung cấp một tập các giao thức
được chuẩn hóa có sức mạnh và khả chuyển đối với hàng chục nghìn nút mạng nhờ đó
cho phép thương mại hóa các ứng dụng sử dụng mạng MANET.
Mục đích đầu tiên của giao thức định tuyến mạng MANET là việc thiết lập
đường đi chính xác và hiệu quả giữa các cặp nút có nhu cầu truyền thông với nhau để
các thông điệp có thể được phân phát tin cậy và đúng thời điểm. Việc khởi tạo tuyến
cần được thực hiện với phụ tải và tiêu thụ băng thông nhỏ nhất. Các giao thức định
tuyến Distance-Vector và Link-State được thiết kế cho môi trường tĩnh vì thế không
thể bắt kịp với những thay đổi cấu trúc mạng thường xuyên trong môi trường mạng
MANET, kết quả gây ra việc giảm hiệu năng bao gồm việc hội tụ tuyến chậm, thông
lượng truyền thông thấp. Có thể nói các giao thức định tuyến cần được thiết kế để
thích hợp với các nhu cầu xác định của môi trường mạng MANET và các đặc tính của
nó, cụ thể là tính di động và việc giới hạn băng thông, năng lượng.
Khi nghiên cứu các giao thức định tuyến trong mạng MANET cần lưu ý các
yếu tố sau:
ü Thiết lập đường đi chính xác và hiệu quả: Do mạng MANET có cấu trúc mạng
thay đổi động nên giao thức định tuyến phải đáp ứng được việc tìm thấy đường
đi chính xác và hiệu quả cho gói tin từ nút nguồn đến nút đích.
ü Không có lặp định tuyến: Nếu hiện tượng này xảy ra, một số gói tin có thể được
chuyển tiếp quay vòng trong mạng một số lần không xác định, dẫn đến việc tiêu
tốn các tài nguyên mạng và có thể gây tắc nghẽn mạng. Giải pháp đưa ra là
dùng trường TTL (Time To Live) trong mỗi gói tin, giá trị TTL được làm giảm
đi một đơn vị khi nút chuyển tiếp gói tin tới một nút mới và khi giảm đến một
giá trị quy định nào đó gói tin sẽ bị loại bỏ.
ü Vấn đề năng lượng và băng thông của mạng: Do các nút trong mạng MANET
có năng lượng bị giới hạn nên khi nghiên cứu các giao thức định tuyến cần xem
xét đến việc tiết kiệm năng lượng cho nút khi có thể. Ngoài ra, cần tránh vấn đề
lãng phí băng thông
26
ü Hỗ trợ liên kết đơn hướng: Trong trường hợp có một số liên kết đơn hướng
(simplex link) giữa một số cặp nút mạng liền kề, giao thức định tuyến cần có
khả năng tìm được đường đi theo cả 2 chiều giữa 2 nút mạng.
ü Bảo mật: Các giao thức định tuyến mạng MANET có thể bị tấn công nhằm gây
ra sự vận hành sai của giao thức ví dụ như thay đổi thông tin cập nhật định
tuyến, sửa đổi tiêu đề gói tin…Do đó, việc đảm bảo an toàn cho giao thức định
tuyến mạng MANET là cần thiết.
3.2. Cá c kĩ thuật định tuyến mạng MANET [10]
Việc định tuyến là vấn đề cốt lõi trong mạng MANET giúp cho việc phân phối
dữ liệu từ nút này tới nút khác. Có rất nhiều tiêu chuẩn khác nhau cho việc thiết kế và
phân loại các giao thức định tuyến mạng MANET như thông tin định tuyến nào được
trao đổi, khi nào và làm thế nào thông tin định tuyến được trao đổi, khi nào và làm thế
nào các tuyến được tính toán…Các kĩ thuật định tuyến mạng MANET có thể chia
thành các loại như sau:
3.2.1. Định tuyến chủ động và định tuyến phản ứng lại
Chiến lược định tuyến chủ động xác định các tuyến tới nhiều nút trong mạng, vì
thế tuyến đường là sẵn sàng mỗi khi cần thiết. Phụ tải phát hiện tuyến là lớn theo chiến
lược này vì một nút phải đảm bảo tuyến tới tất cả các nút khác. Chúng tiêu tốn băng
thông để định kỳ cập nhật các tuyến. Điều đạt được ở đây là khi có yêu cầu, việc
chuyển tiếp gói tin là nhanh hơn theo chiến lược này vì tuyến đã sẵn sàng. Ví dụ về
chiến lược này là giao thức định tuyến DSDV.
Chiến lược định tuyến phản ứng lại thực hiện xác định các tuyến mỗi khi cần.
Vì thế chúng có phụ tải phát hiện tuyến nhỏ hơn. Một nút có yêu cầu truyền gói tin có
thể phải đợi phát hiện tuyến. Các ví dụ về chiến lược này bao gồm AODV, DSR...
Ngoài định tuyến chủ động và phản ứng lại còn có kĩ thuật khác gọi là làm tràn.
Trong kĩ thuật làm tràn, không có tuyến nào được tính toán hay phát hiện. Gói tin được
quảng bá tới tất cả các nút trong mạng. Làm tràn là phương pháp định tuyến dễ dàng
nhất, tuy nhiên, nó tạo ra lưu lượng khổng lồ.
3.2.2. Định tuyến đơn đường và định tuyến đa đường
Có nhiều tiêu chuẩn cho việc so sánh định tuyến đơn đường và định tuyến đa
đường trong mạng MANET. Đầu tiên, phụ tải cho việc phát hiện tuyến trong định
tuyến đa đường là nhiều hơn so với định tuyến đơn đường. Tuy nhiên, tần suất cho
việc phát hiện tuyến là ít hơn trong mạng khi sử dụng định tuyến đa đường vì hệ thống
có thể vẫn vận hành thậm chí nếu một hay một vài đường giữa nguồn và đích gặp lỗi.
3.2.3. Định tuyến dựa vào bảng và định tuyến khởi tạo phía nguồn
üĐịnh tuyến dựa vào bảng
27
Với các giao thức định tuyến dựa vào bảng, việc cập nhật thông tin định tuyến
được thực hiện bằng cách cập nhật bảng định tuyến tại mỗi nút. Các thay đổi trong cấu
trúc mạng được truyền tới toàn bộ mạng bằng các gói tin cập nhật. DSDV và OLSR là
hai giao thức thuộc loại định tuyến dựa vào bảng.
üĐịnh tuyến khởi tạo từ nguồn
Các giao thức định tuyến thuộc loại định tuyến theo yêu cầu khởi tạo phía
nguồn tạo ra các tuyến chỉ khi được chính nút nguồn có yêu cầu gửi đi các gói tin. Khi
mà một nút yêu cầu tuyến tới một nút đích xác định, nó khởi tạo quá trình phát hiện
tuyến. Trong quá trình này, nút nguồn đặt thông tin mô tả địa chỉ đích trong tiêu đề của
gói tin. Bất kỳ nút trung gian nào nhận được yêu cầu sẽ tìm trong bảng định tuyến của
nó tuyến có địa chỉ đích như mô tả. Nếu tuyến tới đích là tồn tại, nút trung gian sẽ trả
về tuyến này cho nút nguồn và tiến trình kết thúc. Ngược lại, gói tin yêu cầu sẽ được
chuyển tiếp tới các hàng xóm và tiếp tục quá trình tìm kiếm tuyến. Một khi tuyến được
tìm thấy, nút nguồn sẽ đặt toàn bộ đường đi trong tiêu đề của gói tin dữ liệu, các nút
trung gian sẽ chuyển tiếp gói tin theo đường đi trong tiêu đề. Các giao thức định tuyến
được phân loại theo cách này bao gồm AODV, DSR, TORA.
Hình 9 biểu diễn các giao thức định tuyến mạng MANET thuộc 2 loại hướng
bảng và khởi tạo phía nguồn.
Hình 9. Định tuyến hướng bảng và khởi tạo phía nguồn theo yêu cầu
3.2.4. Cá c kĩ thuật khôi phục
Vì thông tin định tuyến trong mỗi nút có thể trở nên cũ không sử dụng được,
nhiều giao thức cần khôi phục tuyến hoặc có kĩ thuật duy trì tuyến. Rõ ràng là các giao
thức định tuyến chủ động không cần kĩ thuật khôi phục tuyến vì chúng phản ứng lại
với các thay đổi cấu trúc trong một chu kỳ ngắn. Tuy nhiên, các giao thức theo yêu cầu
cần phải loại bỏ các tuyến mà không còn được sử dụng nữa. Các giao thức sau đây có
các kĩ thuật khôi phục (tường minh hay không tường minh): ABR, AODV, CBRP,
DREAM3 DSR, FORP, WAR và ZRP.
28
3.2.5. Chiến lược lựa chọn tuyến
Chiến lược lựa chọn tuyến là khía cạnh quan trọng của giao thức định tuyến
mạng MANET. Các chiến lược chính bao gồm:
ü Độ mạnh tín hiệu: Lựa chọn tuyến dọc theo kết nối mà có độ mạnh tín hiệu tốt
nhất. Chiến lược này được sử dụng chủ yếu trong giao thức định tuyến ABR và
SSR.
ü Ổn định liên kết: Lựa chọn tuyến dọc theo kết nối mà xuất hiện ổn định nhất
trong một chu kỳ thời gian. Chiến lược này được sử dụng bởi giao thức định
tuyến DST và FORP.
ü Đường đi ngắn nhất/Trạng thái liên kết: Lựa chọn đường đi ngắn nhất theo một
số đơn vị đo. Chiến lược này được sử dụng bởi nhiều giao thức định tuyến:
CEDAR, DDR, FSR, GSR, HSR, OLSR, và TBRPF.
3.2.6. Cập nhật định kỳ và cập nhật theo sự kiện
Các giao thức định tuyến cập nhật theo chu kỳ sẽ thi hành việc cập nhật thông
tin định tuyến theo chu kỳ. Các cập nhật theo chu kỳ sẽ làm đơn giản hóa các giao
thức định tuyến và bảo đảm sự ổn định của mạng và quan trọng nhất đó là cho phép
các nút (mới) học về cấu trúc và trạng thái của mạng. Tuy nhiên, nếu chu kỳ giữa các
lần cập nhật mà lớn, thì giao thức định tuyến có thể không thể theo kịp việc cập nhật
thông tin. Ngược lại, nếu chu kỳ mà nhỏ thì sẽ có quá nhiều gói tin định tuyến được
phân phát làm tiêu tốn băng thông một cách nghiêm trọng. Với giao thức cập nhật theo
sự kiện, khi có các sự kiện xảy ra (ví dụ khi có liên kết lỗi hoặc có liên kết mới xuất
hiện), gói tin cập nhật sẽ được nút phát hiện ra sự kiện phát quảng bá và trạng thái cập
nhật có thể được phân phát tới toàn bộ mạng rất sớm. Vấn đề có thể xảy ra là nếu cấu
trúc của mạng thay đổi quá nhanh, có rất nhiều gói tin cập nhật sẽ được phân phát tới
toàn bộ mạng và sẽ sử dụng một lượng lớn băng thông có thể gây ra dao động tới các
tuyến.
3.2.7. Cấu trúc phẳng và cấu trúc phâ n cấp
Trong cấu trúc phẳng, tất cả các nút trong mạng là cùng mức và có cùng chức
năng định tuyến. Định tuyến phẳng là đơn giản và hiệu quả cho các mạng nhỏ. Vấn đề
xảy ra khi mạng trở nên lớn hơn, dung lượng của thông tin định tuyến sẽ lớn và cần
nhiều thời gian để thông tin định tuyến tới được các nút ở xa. Với các mạng lớn, định
tuyến phân cấp (dựa trên cụm) có thể được sử dụng để giải quyết vấn đề trên. Trong
định tuyến phân cấp, các nút trong mạng được tổ chức động thành các phân hoạch gọi
là các cụm và sau đó các cụm được hội tụ lại thành các phân hoạch lớn hơn gọi là siêu
cụm…Việc tổ chức mạng thành các cụm giúp cho việc bảo đảm cấu trúc mạng ổn định
một cách tương đối. Tính động cao của các nút và cấu trúc mạng bị giới hạn trong các
cụm. Chỉ thông tin ổn định và mức cao như mức cụm hay mức siêu cụm sẽ được
29
truyền theo khoảng cách xa vì thế lưu lượng điều khiển (hay phụ tải định tuyến) có thể
được giảm nhiều.
Dưới đây là các so sánh từ các tiêu chuẩn khác nhau:
Giao
thức
Triết lý định Tính toán
Định tuyến
nguồn
Cấu trúc
Các tuyến
tuyến
tuyến
LSR
Chủ động
Chủ động
Chủ động
Chủ động
Chủ động
Chủ động
Phản ứng lại
Phản ứng lại
Phản ứng lại
Phản ứng lại
Phản ứng lại
Lai ghép
Tập trung
Phân tán
Phân tán
Phân tán
Phân tán
Phân tán
Phân tán
Quảng bá
Quảng bá
Quảng bá
Quảng bá
Kế thừa
Phẳng
Phẳng
Phẳng
Phẳng
Đơn hoặc đa Không, có thể có
DVR
DSDV
GSR
Đơn
Đơn
Không
Không
Đơn hoặc đa Không, có thể có
FSR
Phân cấp Đơn hoặc đa Không, có thể có
CGSR
WRP
DSR
Phẳng
Phẳng
Phẳng
Phẳng
Phẳng
Phẳng
Phân cấp
Đơn hoặc đa Không, có thể có
Đơn
Đa
Không
Có
AODV
TORA
ABR
HSR
Đa
Không
Không
Có
Đa
Đơn
Đơn
Không
Bảng 1. So sánh giữa các giao thức định tuyến (Phân tích định tính 1)
Giao
thức
Cập nhật
Thông tin cập nhật
Đích cập nhật
LSR
Lai
Chu kỳ
Trạng thái liên kết của hàng xóm
Vec tơ khoảng cách
Vec tơ khoảng cách
Vec tơ khoảng cách
Trạng thái liên kết
Vec tơ khoảng cách
Vec tơ khoảng cách
Lỗi tuyến
Tất cả các nút
Hàng xóm
DVR
DSDV
GSR
Lai
Hàng xóm
Chu kỳ
Hàng xóm
FSR
Chu kỳ
Hàng xóm
CGSR
WRP
DSR
Chu kỳ
Hàng xóm và đầu cụm
Hàng xóm
Lai
Hướng sự kiện
Hướng sự kiện
Hướng sự kiện
Hướng sự kiện
Trên sự kiện
Nguồn
AODV
TORA
ABR
HSR
Lỗi tuyến
Nguồn
Độ dài của nút
Hàng xóm
Lỗi tuyến
Hàng xóm/Nguồn
Các nút trong cụm
Trạng thái liên kết ảo
Bảng 2. So sánh giữa các giao thức định tuyến (Phân tích định tính 2)
3.3. Cá c giao thức định tuyến chủ yếu trong mạng MANET [8]
3.3.1. Giao thức DSDV (Destination-Sequenced Distance Vector) [4]
Giao thức định tuyến DSDV được mô tả trong [4] là giao thức dựa trên bảng
khởi nguồn từ kĩ thuật định tuyến cổ điển Bellman-Ford. Các cải tiến từ kĩ thuật định
Tải về để xem bản đầy đủ
87 trang
15/05/2025
130
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng manet", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_danh_gia_chi_phi_tim_duong_cua_mot_so_giao_thuc_din.pdf
