Luận văn Đánh giá ảnh hưởng của sự di động của nút mạng đến hiệu quả của các thuật toán định tuyến trong mạng manet
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
PHAN HỮU DŨNG
ĐÁNH GIÁ ẢNH HƯỞNG CỦA SỰ DI ĐỘNG
CỦA NÚT MẠNG ĐẾN HIỆU QUẢ CỦA CÁC THUẬT
TOÁN ĐỊNH TUYẾN TRONG MẠNG MANET
LUẬN VĂN THẠC SĨ
Hà Nội - 2011
2
Lời cảm ơn
Đầu tiên 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, Viện Khoa học kỹ thuật Bưu điện và Viện Công
nghệ Thông tin - Viện Khoa học và Công nghệ Việt Nam đã tận tình chỉ bảo tôi trong
suốt khóa học; cảm ơn tập thể lớp K15T1, tập thể lớp K15 chuyên ngành Mạng và
Truyền thông máy tính. Cảm ơn các thành viên trong nhóm nghiên cứu với những ý
kiến góp ý quý báu trong quá trình tôi thực hiện đề tài, và đặc biệt tôi chân thành cảm
ơn thầy hướng dẫn - PGS.TS Nguyễn Đình Việt, người đã tận tình hướng dẫn, chỉ bảo
tôi trong học tập và nghiên cứu.
Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè của tôi,
những người đã luôn ở bên động viên và khích lệ 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 có những thiếu
sót, tôi rất mong nhận được sự góp ý từ bạn bè, thầy cô và những người quan tâm đến
đề tài này.
Let’s start at the very beginning,
a very nice place to start,
when you sing, you begin with A, B, C,
when you simulate, you begin with the topology
-
The
ns
Manual
3
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. Trong toàn bộ nội dung của luận văn,
những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn
tài liệu. Tất cả cá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, ngày 01 tháng 05 năm 2011
Phan Hữu Dũng
4
Mục lục
Lời cảm ơn ..................................................................................................................1
Lời cam đoan...............................................................................................................3
Danh mục hình vẽ........................................................................................................7
Danh mục bảng............................................................................................................9
Bảng ký hiệu các chữ viết tắt .....................................................................................10
Chương 1: GIỚI THIỆU............................................................................................12
1.1. Đặt vấn đề.......................................................................................................12
1.2. Mục tiêu nghiên cứu........................................................................................12
1.3. Tổ chức của luận văn ......................................................................................13
Chương 2: MẠNG WLAN VÀ MẠNG MANET ......................................................14
2.1. Mạng không dây .............................................................................................14
2.1.1. Mạng cục bộ WLAN ................................................................................14
2.1.1.1. Lịch sử ra đời mạng WLAN ..............................................................15
2.1.1.2. Phân loại mạng WLAN .....................................................................15
2.1.1.3. Các chuẩn đối với mạng WLAN........................................................17
2.1.2. Một số mạng không dây phổ biến khác.....................................................18
2.1.2.1. Mạng cá nhân WPAN theo chuẩn 802.15.1, 802.15.3 và 802.15.4.....18
2.1.2.2. Mạng đô thị WMAN theo chuẩn 802.16............................................18
2.1.2.3. Mạng diện rộng WWAN theo chuẩn 802.20......................................19
2.2. Mạng di động không dây đặc biệt MANET.....................................................19
2.2.1. Giới thiệu mạng MANET.........................................................................19
2.2.2. Các đặc điểm của mạng MANET .............................................................22
2.2.3. Phân loại ..................................................................................................22
2.2.3.1. Phân loại mạng MANET theo cách thức định tuyến ..........................22
2.2.3.2. Phân loại mạng MANET theo chức năng của Nút..............................23
Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET................26
3.1. Các giao thức định tuyến phổ biến trong mạng có dây truyền thống................26
3.1.1. Distance Vector........................................................................................26
3.1.2. Link State.................................................................................................26
3.1.3. Source Routing.........................................................................................27
3.1.4. Kỹ thuật Flooding ....................................................................................27
3.2. Các yêu cầu đối với thuật toán định tuyến trong mạng MANET......................27
3.2.1. Mục tiêu thiết kế các giao thức định tuyến cho mạng MANET.................27
5
3.2.2. Áp dụng các thuật toán định tuyến truyền thống trong mạng MANET......28
3.3. Phân loại các giao thức định tuyến cho MANET [16]........................................29
3.3.1. Các khái niệm liên quan ...........................................................................30
3.3.1.1. Định tuyến chủ ứng và định tuyến phản ứng......................................30
3.3.1.2. Cập nhật định kỳ và cập nhật theo sự kiện.........................................30
3.3.1.3. Tính toán phi tập trung và tính toán phân tán.....................................31
3.3.1.4. Đơn đường và đa đường ....................................................................31
3.3.2. Phân loại các giao thức định tuyến ...........................................................31
3.3.2.1. Destination-Sequence Distance Vector (DSDV) ................................32
3.3.2.2. Optimized Link State Routing Protocol (OLSR)................................33
3.3.2.3. Ad hoc On-demand Distance Vector Routing (AODV) .....................35
3.3.2.4. Dynamic Source Routing (DSR) [12] ..................................................36
3.3.2.5. So sánh các giao thức định tuyến cho MANET..................................38
Chương 4: NGHIÊN CỨU VIỆC SỬ DỤNG CÔNG CỤ MÔ PHỎNG VÀ PHÂN
TÍCH KẾT QUẢ .......................................................................................................41
4.1. Lựa chọn phương pháp và công cụ đánh giá hiệu năng mạng [1] ......................41
4.1.1. Lựa chọn phương pháp.............................................................................41
4.1.1.1. Mô hình Giải tích ..............................................................................42
4.1.1.2. Mô phỏng mạng bằng chương trình máy tính ....................................42
4.1.1.3. Đo trên mạng thực.............................................................................42
4.1.1.4. Lý do sử dụng phương pháp mô phỏng để đánh giá hiệu năng mạng .43
4.1.2. Công cụ mô phỏng NS-2 [1, 12, 15]...............................................................43
4.1.2.1. Các chức năng mô phỏng chính của NS.............................................45
4.1.2.2 Cấu trúc phần mềm của NS ................................................................46
4.1.2.3. Lập trình mô phỏng bằng NS.............................................................46
4.1.3 Công cụ hỗ trợ phân tích kết quả mô phỏng...............................................46
4.1.3.1 Cấu trúc tệp vết chứa kết quả mô phỏng mạng không dây ..................46
4.1.3.2 Một số công cụ hỗ trợ việc phân tích và hiển thị kết quả mô phỏng....47
4.1.4. Công cụ hiển thị trực quan mạng MANET trong quá trình hoạt động
iNSPECT...........................................................................................................48
4.2. Thiết lập mô phỏng mạng MANET trong NS..................................................53
4.2.1. Tạo các nút mạng trong MANET .............................................................53
4.2.1.1 Nút di động.........................................................................................53
4.4.1.2 Mô hình phương tiện chia sẻ trong NS2..............................................54
4.4.1.3 Hoạt động của nút di động..................................................................55
4.4.1.4 Cấu hình nút di động trong NS ...........................................................56
6
4.4.1.5 Tạo sự di chuyển của nút trong NS.....................................................57
4.4.2. Tạo các đường truyền không dây (air interface) trong MANET................58
4.4.2.1 Mô hình FreeSpace.............................................................................58
4.4.2.2 Mô hình Two Ray Ground..................................................................58
4.4.2.3 Mô hình Shadowing ...........................................................................59
4.4.3. Tạo ngữ cảnh chuyển động.......................................................................59
4.4.3.1 Tạo diện tích mô phỏng......................................................................60
4.4.3.2. Tạo các thực thể giao thức và các nguồn sinh lưu lượng....................60
4.4.3.3. Tạo các dạng chuyển động theo mẫu .................................................61
4.4.4. Sơ đồ khái quát quá trình mô phỏng .........................................................64
4.5 Các tham số hoạt động của các giao thức định tuyến trong NS-2......................65
4.5.1 Giao thức định tuyến DSDV......................................................................65
4.5.2 Giao thức định tuyến OLSR ......................................................................66
4.5.3 Giao thức định tuyến AODV.....................................................................66
4.5.4 Giao thức định tuyến DSR.........................................................................67
Chương 5: ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO THỨC ĐỊNH TUYẾN THEO
MỨC ĐỘ LINH ĐỘNG CỦA CÁC NÚT MẠNG.....................................................68
5.1. Thực nghiệm mô phỏng ..................................................................................68
5.1.1 Các thông số mô phỏng.............................................................................68
5.1.2 Chương trình mô phỏng ............................................................................69
5.2. Các độ đo hiệu năng được dùng trong luận văn...............................................70
5.3. Kết quả mô phỏng...........................................................................................70
5.3.1 Mô phỏng sử dụng mô hình Random Waypoint.........................................70
5.3.1.1 Thiết lập thông số mô phỏng ..............................................................70
5.3.2.2 Kết quả và nhận xét............................................................................72
5.3.3 Mô phỏng sử dụng mô hình Random Walk ...............................................75
5.3.3.1 Thiết lập thông số mô phỏng ..............................................................75
5.3.3.2 Kết quả và nhận xét............................................................................77
5.3.4 Đánh giá hiệu quả của các giao thức định tuyến ........................................79
Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU...............................................81
6.1. Kết quả đạt được của luận văn.........................................................................81
6.2. Hướng nghiên cứu...........................................................................................82
TÀI LIỆU THAM KHẢO..........................................................................................83
PHỤ LỤC..................................................................................................................84
7
Danh mục hình vẽ
Hình 1. Phân loại các mạng không dây dựa trên quy mô. ..........................................14
Hình 2. Mạng WLAN có cơ sở hạ tầng .....................................................................16
Hình 3. Mạng WLAN không có cơ sở hạ tầng [10] ...................................................17
Hình 4. Mạng MANET và Sensor không dây [14].....................................................21
Hình 5. Định tuyến Single-hop..................................................................................23
Hình 6. Định tuyến Multi-hop...................................................................................23
Hình 7. Mạng MANET phân cấp ..............................................................................24
Hình 8. Mạng MANET kết hợp.................................................................................24
Hình 9. Phân loại các giao thức định tuyến trong mạng MANET [13].......................32
Hình 10. Tập chuyển tiếp đa điểm MPRs ..................................................................34
Hình 11. Định tuyến Link State và định tuyến cải tiến trong OLSR............................34
Hình 12. AODV tìm kiếm và duy trì tuyến đường .....................................................36
Hình 13. Ví dụ về Route discovery: nút A là nút nguồn, nút E là nút đích. ................37
Hình 14. Ví dụ về Route maintenance:......................................................................38
Hình 15. Kiến trúc NS-2 ...........................................................................................44
Hình 16. Ba giai đoạn của một phiên truyền từ nút nguồn 1 đến nút đích 48 .............49
Hình 17. Hình tròn bao phủ biểu diễn khu vực tắc nghẽn ..........................................50
Hình 18. Hình tròn bao phủ biểu diễn khu vực nguy hiểm.........................................51
Hình 19. iNSpect hiển thị tọa độ (x, y) của các nút ....................................................52
Hình 20. Nút di động mô phỏng trong NS2 ...............................................................53
Hình 21. Mô hình phương tiện chia sẻ trong NS2......................................................55
Hình 22. Sơ đồ của một mobilenode dưới chuẩn wireless của Monarch CMU mở rộng
ra NS [12]..................................................................................................................57
Hình 23. Các mô hình truyền thông trong NS2..........................................................60
Hình 24. Di chuyển của một nút theo mô hình Random Waypoint ............................62
Hình 25. Di chuyển của một nút theo mô hình Random Walk ...................................63
Hình 26. Sơ đồ tổng quan quá trình mô phỏng ..........................................................64
Hình 27. Đánh giá kết quả phân phát gói tin trong mô hình Random Waypoint.........72
Hình 28. Đánh giá kết quả trễ đầu cuối trong mô hình Random Waypoint ................72
Hình 29. Đánh giá kết quả thông lượng trong mô hình Random Waypoint................73
Hình 30. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Waypoint..............73
Hình 31. Đánh giá kết quả phân phát gói tin trong mô hình Random Walk ...............77
Hình 32. Đánh giá kết quả trễ đầu cuối trong mô hình Random Walk .......................77
Hình 33. Đánh giá kết quả thông lượng trong mô hình Random Walk.......................78
8
Hình 34. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Walk.....................78
9
Danh mục bảng
Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2]................................................17
Bảng 2. Tổng quan về họ các chuẩn ETSI HIPERLAN [2]........................................17
Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15 .....................................................18
Bảng 4: So sánh độ phức tạp của các giao thức định tuyến........................................39
Bảng 5: So sánh các đặc điểm của các giao thức định tuyến......................................39
Bảng 6: So sánh các đặc điểm của các giao thức định tuyến......................................40
Bảng 7. Các tham số của mô hình Random Waypoint ..............................................62
Bảng 8. Các tham số của mô hình Random Walk ......................................................63
Bảng 9. Các tham số hoạt động của DSDV trong NS2...............................................65
Bảng 10. Các tham số hoạt động của OLSR trong NS2 .............................................66
Bảng 11. Các tham số hoạt động của AODV trong NS2............................................66
Bảng 12. Các tham số hoạt động của DSR trong NS2................................................67
Bảng 13. Cấu hình các mạng mô phỏng trong mô hình Random Waypoint ...............71
Bảng 14. Cấu hình các mạng mô phỏng theo mô hình Random Walk........................76
10
Bảng ký hiệu các chữ viết tắt
AODV
CSMA/CA
DARPA
DSDV
DSR
Ad hoc On-demand Distance Vector
Carrier Sense Multiple Access with Collision Avoidance
Defense Advanced Research Projects Agency
Destination-Sequenced Distance Vector
Dynamic Source Routing
DV
Distance Vector
ETSI
European Telecommunications Standards Institute
US Federal Communications Commission
First In First Out
FCC
FIFO
GPRS
GSM
General Packet Radio Service
Global System for Mobile communication
High Performance European Radio LAN
Institute of Electrical and Electronic Engineering
Internet Engineering Task Force
interactive NS-2 protocol and environment confirmation tool
Industrial, Scientific and Medical bands
Local Area Network
HiperLAN
IEEE
IETF
iNSpect
ISM
LAN
LS
Link State
MAC
MANET
NEST
NS2
Media Access Control
Mobile Wireless Adhoc Network
Network Simulation Testbed
Network Simulator 2
OLSF
OLSR
Open Shortest Path First
Optimized Link State Routing Protocol
11
PDA
Personal Digital Assistant
Packet Radio Network
PRnet
QoS
Quality of Service
REAL
RIP
Realistic and Large
Routing Information Protocol
Route Reply
RREP
RREQ
RTS
Route Request
Request To Send
SURAN
TDMA/TDD
TORA
UMTS
VINT
Survivable Radio Network
Time Division Multiple Access/ Time Division Duplex
Temporally-Ordered Routing Algorithm
Universal Mobile Telecommunications Systems
Virtual InterNetwork Testbed
Wireless Fidelity
WIFI
WiMAX
WLAN
WMAN
WPAN
WRP
World Interoperability for MicroAccess
Wireless Local Area Network
Wireless Metropolitan Area Networks
Wireless Personal Area Networks
Wireless Routing Protocol
Wireless Wide Area Networks
Zone Routing Protocol
WWAN
ZRP
12
Chương 1: GIỚI THIỆU
1.1. Đặt vấn đề
Mạng di động không dây đặc biệt MANET (Mobile Wireless Adhoc Network) cho
phép các máy tính di động thực hiện 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ó dây. Trong MANET mọi nút mạng đều có thể thực hiện chức năng
của một router, chúng cộng tác với nhau, thực hiện chuyển tiếp các gói tin hộ các nút mạng
khác nếu các nút mạng này không thể truyền trực tiếp với nút nhận. Định tuyến là bài toán
quan trọng nhất đối với việc nghiên cứu MANET. Cho đến nay, đã có nhiều thuật toán định
tuyến được đề xuất, mỗi thuật toán đều có các ưu và nhược điểm riêng. Điều đặc biệt là
mức độ của các ưu nhược điểm phụ thuộc rất nhiều vào mức độ di động của các nút mạng.
Một số thuật toán là ưu việt hơn các thuật toán khác trong điều kiện các nút mạng di động ở
mức độ thấp nhưng lại kém hơn hẳn khi mức độ di động của các nút mạng tăng cao. Đề tài
luận văn này nhằm mục đích đánh giá và so sánh ảnh hưởng của sự di động của nút mạng
đến hiệu quả của một số thuật toán định tuyến trong mạng MANET.
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 ... hay những nơi yêu
cầu tính nhanh chóng, tạm thời như trong các trận chiến, do thám …Việc đánh giá và so
sánh ảnh hưởng của sự di động đến hiệu quả của các thuật toán định tuyến giúp cho việc
lựa chọn thuật toán định tuyến thích hợp cho các điều kiện cụ thể khi sử dụng MANET.
1.2. Mục tiêu nghiên cứu
Các mạng AD HOC ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực
cuộc sống như khoa học, giáo dục, y tế, quân sự … do nó có ưu điểm nổi bật là loại bỏ
sự phụ thuộc vào các cơ sở hạ tầng mạng cố định. Vấn đề đặt ra là đánh giá hiệu quả
hoạt động của các giao thức định tuyến trong mạng MANET trên nhiều khía cạnh và
phương diện khác nhau. Một trong những yếu tố ảnh hưởng rất lớn đến hiệu quả của
các giao thức định tuyến đó là sự linh động của các nút mạng. Mục đích của luận văn
là nghiên cứu các giao thức định tuyến kết hợp với việc đưa ra các kết quả mô phỏng
để đánh giá hiệu quả làm việc của chúng. Căn cứ vào mục đích chính của luận văn, tôi
xin đưa ra các mục tiêu cụ thể như sau:
Giới thiệu tổng quan về mạng LAN không dây (Wireless LAN) và Mạng di
động không dây đặc biệt – MANET (Mobile Wireless Adhoc Network).
Nghiên cứu một số giao thức định tuyến không dây sử dụng trong mạng
MANET: DSDV, OLSR, AODV, DSR.
Xác định các tham số hiệu suất chính của các giao thức định tuyến.
Tìm hiểu khả năng mô phỏng các giao thức định tuyến cũng như các mô hình
chuyển động khác nhau của bộ mô phỏng mạng NS-2.
13
Đánh giá bằng mô phỏng một số giao thức định tuyến phổ biến trong các ngữ
cảnh chuyển động của các nút mạng khác nhau.
1.3. Tổ chức của luận văn
Luận văn được tổ chức thành sáu chương, cụ thể như sau:
Chương 1: GIỚI THIỆU
Chương 2: MẠNG WLAN VÀ MẠNG MANET
Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET
Chương 4: NGHIÊN CỨU VIỆC SỬ DỤNG CÔNG CỤ MÔ PHỎNG VÀ
PHÂN TÍCH KẾT QUẢ
Chương 5: ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO THỨC ĐỊNH TUYẾN
THEO MỨC ĐỘ LINH ĐỘNG CỦA CÁC NÚT MẠNG
Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU
Trong đó, chương một trình bày cơ sở khoa học và tính thực tiễn cũng như mục
tiêu nghiên cứu của luận văn. Chương hai đưa ra kiến thức cơ sở về mạng WLAN và
mạng MANET. Các kỹ thuật định tuyến truyền thống được sử dụng trong mạng cố
định và các giao thức định tuyến dùng trong mạng MANET được trình bày chương ba.
Chương bốn đưa ra cái nhìn tổng quan về bộ mô phỏng NS-2 và giới thiệu công cụ mô
phỏng mới iNSpect từ đó ứng dụng vào việc mô phỏng các giao thức định tuyến.
Chương năm sử dụng những kết quả mô phỏng thu được trong chương bốn để tính
toán các độ đo hiệu năng sau đó kết hợp với cơ sở lý thuyết về các giao thức định
tuyến trình bày trong chương ba để rút ra những đánh giá về ảnh hưởng của sự di dộng
của nút mạng đến hiệu quả của các giao thức định tuyến trong mạng MANET. Cuối
cùng, trong chương sáu là những nhận xét về kết quả đạt được và hướng nghiên cứu
tiếp theo của luận văn.
14
Chương 2: MẠNG WLAN VÀ MẠNG MANET
Mục tiêu của chương này là giới thiệu với người đọc những kiến thức cơ sở về
mạng WLAN và mạng MANET bao gồm lịch sử ra đời, các đặc điểm, những ưu nhược
điểm cũng như các ứng dụng trong khoa học, công nhệ và cuộc sống từ đó có cái nhìn
tổng quan về hai mạng này và dễ dàng phân biệt được chúng.
2.1. Mạng không dây
Các mạng không dây (Wireless networks) thường được phân thành mạng cá
nhân WPAN - chuẩn IEEE 802.15, mạng cục bộ WLAN - chuẩn IEEE 802.11, mạng
đô thị WMAN - chuẩn IEEE 802.16 và mạng diện rộng WWAN - chuẩn IEEE 802.20.
Sự phân chia này dựa trên quy mô và phạm vi truyền dẫn của các bộ phát (transmitter)
vô tuyến và mỗi lớp mạng có thể gồm một vài tiêu chuẩn và công nghệ riêng.
Hình 1 bên dưới minh họa sự phân lớp các mạng không dây dựa trên quy mô:
Hình 1. Phân loại các mạng không dây dựa trên quy mô.
2.1.1. Mạng cục bộ WLAN
Wireless Local Area Network (WLAN) là một mạng cục bộ kết nối hai hay
nhiều máy tính với nhau mà không cần các kết nối vật lý giữa chúng. Môi trường
truyền được sử dụng trong WLAN là môi trường không khí với một dải tần số được
quy định cho các loại hình truyền thông. Có hai công nghệ chính được sử dụng để
truyền thông trong WLAN là truyền thông bằng tia hồng ngoại (bước sóng 900 nm)
hoặc truyền thông bằng sóng vô tuyến, thông thường thì sóng vô tuyến được dùng phổ
biến hơn vì nó truyền xa hơn, lâu hơn, rộng hơn và có băng thông cao hơn. WLAN
cũng có hai dạng kiến trúc là WLAN có cơ sở hạ tầng (sử dụng các Access Point) hoặc
trạm cơ sở (Base Station) để kết nối phần mạng không dây với phần mạng có dây
truyền thống và mạng không có cơ sở hạ tầng (mạng Ad hoc).
15
2.1.1.1. Lịch sử ra đời mạng WLAN
Năm 1971, tại Đại học Hawaii các công nghệ mạng và truyền thông vô tuyến đã
được kết hợp lần đầu tiên trong dự án Alohanet. Dự án này sử dụng các thiết bị máy
tính tại bảy điểm khác nhau nằm rải rác trên bốn hòn đảo thực hiện việc giao tiếp với
máy tính trung tâm trên đảo Oahu bằng cách sử dụng không khí làm môi trường
truyền. Nó thiết lập một topo Star và các trạm từ xa chỉ có thể giao tiếp thông qua máy
tính trung tâm đặt tại đảo Oahu.
Tuy nhiên, đến giữa thập niên 1980 thì mạng WLAN mới phát triển mạnh khi
Uỷ ban Truyền thông Liên bang Mỹ FCC (US Federal Communications Commission)
quyết định cho phép sử dụng phổ biến các dải tần số công nghiệp, khoa học và y tế
ISM (Industrial, Scientific and Medical bands). Quyết định này cho phép các công ty
và người dùng sản xuất và sử dụng các sản phẩm không dây của họ mà không cần
FCC cấp giấy phép hoạt động. Từ đó, dẫn đến sự tăng trưởng vượt bậc trong lĩnh vực
mạng WLAN. Tuy nhiên, do sự xuất hiện của nhiều sản phẩm độc quyền nhưng lại
không có một tiêu chuẩn chung thống nhất, dẫn đến các sản phẩm không cùng một
công ty sản xuất có thể sẽ không tương thích với nhau. Vì vậy, yêu cầu đặt ra là phải
chuẩn hóa trong lĩnh vực mạng WLAN.
Hiện nay, trên thế giới chủ yếu sử dụng hai chuẩn phổ biến cho mạng WLAN là:
Chuẩn IEEE 802.11x do các Nhóm công tác của Viện công nghệ Điện và Điện Tử IEEE
(Institute of Electrical and Electronics Engineers) phát triển và chuẩn HiperLAN/x
(High Performance European Radio LAN) được phát triển bởi nhóm RES10 thuộc Viện
Tiêu chuẩn Viễn thông Châu Âu ETSI (European Telecommunications Standards
Institute). Chuẩn IEEE 802.11x sử dụng giao thức CSMA/CA, còn chuẩn HiperLAN/x
là giao thức TDMA/TDD. Chuẩn IEEE 802.11x được sử dụng phổ biến hơn so với
chuẩn HiperLAN/x nhưng chuẩn HiperLAN/x có những ưu điểm nổi trội khi đối phó
với vấn đề lưu lượng thời gian thực.
2.1.1.2. Phân loại mạng WLAN
Mạng WLAN có cơ sở hạ tầng
Mạng WLAN có cơ sở hạ tầng là mạng mà các nút mạng truyền thông với nhau
sử dụng một thiết bị trung tâm gọi là điểm truy cập chung AP (Access Point), hay còn
được gọi là trạm cơ sở BS (Base Station). Các trạm cơ sở không chỉ cung cấp khả năng
kết nối mạng mà nó còn thực hiện chức năng điều khiển truy cập đường truyền nhằm
chuyển tiếp thông tin từ nguồn đến đích. Ngoài ra, các điểm truy cập mạng còn thường
được kết nối với mạng có dây và được kết nối với Internet nên nó đóng vai trò như là
cầu nối giữa các mạng không dây và mạng có dây với nhau tạo thành một mạng diện
rộng. Tốc độ truyền dữ liệu của mạng không chỉ phụ thuộc vào đặc điểm của các nút
mạng mà còn phụ thuộc vào bán kính phủ sóng của các điểm truy cập mạng. Các nút
mạng càng gần điểm truy cập mạng AP thì sóng thu được càng mạnh và tốc độ truyền
dữ liệu càng cao. Do đó, việc lựa chọn tốc độ truyền và phạm vi hoạt động của điểm
16
truy cập mạng khiến chúng ta cần phải cân nhắc, khi đó nó sẽ ảnh hưởng trực tiếp tới
hiệu năng hoạt động của mạng và của điểm truy cập mạng.
Khái niệm Indoor và Outdoor: Indoor là khái niệm sử dụng sóng vô tuyến trong
phạm vi không gian nhỏ, như trong một tòa nhà, một văn phòng. Outdoor là khái niệm
sử dụng sóng vô tuyến trong phạm vi không gian lớn hơn, với WLAN thì bán kính đến
các thiết bị mà nó quản lý có thể lên đến 5km.
Hình 2. Mạng WLAN có cơ sở hạ tầng
Mạng WLAN không có cơ sở hạ tầng (mạng Ad Hoc)
Một mạng Ad Hoc là một tập hợp các nút không dây di động (có chứ năng như
routers) cấu thành nên một mạng tạm thời mà không cần sử dụng cơ sở hạ tầng có sẵn
hoặc việc quản trị tập trung. Các routers được tự do di chuyển ngẫu nhiên và tự thiết
lập tùy ý, vì vậy topo mạng không dây có thể thay đổi nhanh chóng và không thể biết
trước [10].
Mạng Ad Hoc là mạng mà các nút trong mạng có thể tự thiết lập, tự tổ chức và
tự thích nghi khi có một nút mới gia nhập mạng, các nút trong mạng cần có cơ chế
phát hiện nút mới gia nhập mạng, thông tin về nút mới sẽ được cập nhật vào bảng định
tuyến của các nút hàng xóm và gửi đi. Khi có một nút ra khỏi mạng, thông tin về nút
đó sẽ được xóa khỏi bảng định tuyến và hiệu chỉnh lại tuyến, ...Mạng Ad Hoc có nhiều
loại thiết bị khác nhau tham gia mạng lên các nút mạng không những phát hiện được
khả năng kết nối của các thiết bị, mà còn phải phát hiện ra được loại thiết bị và các đặc
tính tương ứng của các loại thiết bị đó (vì các thiết bị khác nhau sẽ có các đặc tính
khác nhau ví dụ như: khả năng tính toán, lưu trữ hay truyền dữ liệu trong mạng,...)
17
Hình 3. Mạng WLAN không có cơ sở hạ tầng [10]
2.1.1.3. Các chuẩn đối với mạng WLAN
Chuẩn IEEE 802.11/x
802.11
802.11a
802.11b
802.11g
5.15-5.25 (lower)
5.25-5.35 (middle)
5.725-5.825 (upper)
Frequency Range
(GHz)
2.4-2.4835
2.4-2.4835 2.4-2.4835
Max.DataRate
(Mbps)
2
55
11
54
30
< 10 m
27-30(lowerband)
75-100
Range
Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2]
Chuẩn HIPERLAN/x
HIPERLAN HIPERLAN HIPERLAN
HIPERLAN
4
1
2
3
Fixed Wireless
Access -
WATM
Wireless Point
to Point Links -
WATM
WATM
WLAN
Application
Indoor Access
Remote
interconnection
Access
Frequency Range
(GHz)
5
5
5
17
Max.DataRate
(Mbps)
23.5
20
20
155
Bảng 2. Tổng quan về họ các chuẩn ETSI HIPERLAN [2]
18
2.1.2. Một số mạng không dây phổ biến khác
2.1.2.1. Mạng cá nhân WPAN theo chuẩn 802.15.1, 802.15.3 và 802.15.4
Mạng WPAN (Wireless Personal Area Networks) thường liên quan đến khái
niệm văn phòng không dây. Phạm vi của mạng PAN là một vài mét, cung cấp khả
năng đồng bộ hóa các máy tính, truyền files và truy cập được vào thiết bị ngoại vi cục
bộ như máy in hay các thiết bị cầm tay khác như điện thoại di động và PDAs. Hiện tại,
công nghệ nổi tiếng nhất của PAN là Bluetooth.
Viện công nghệ Điện và Điện Tử IEEE đưa ra chuẩn 802.15 sử dụng cho mạng
WPAN với các tốc độ truyền dữ liệu như sau: 802.15.1 đặc tả công nghệ Bluetooth có
tốc độ truyền dữ liệu ở mức trung bình, trong khi 802.15.3 được phát triển cho mạng Ad
hoc với lớp MAC phù hợp cho truyền dữ liệu đa phương tiện có tốc độ truyền dữ liệu ở
mức cao và 802.15.4 định nghĩa giao thức liên kết nối các thiết bị ngoại vi truyền thông
sóng vô tuyến trong hệ thống mạng một người dùng có tốc độ truyền ở mức thấp.
802.15.1
2.4 Ghz
1 Mpbs
< 10 m
802.15.3
2.4 Ghz
55 Mpbs
< 10 m
802.15.4
915MHz
40 Kbps
10 - 75 m
2.45 Ghz
250 Kpbs
868MHz
20 Kbps
Frequency Range
Max.Data Rate
Range
Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15
2.1.2.2. Mạng đô thị WMAN theo chuẩn 802.16
Mạng đô thị không dây WMAN (Wireless Metropolitan Area Networks) được
định nghĩa là mạng có qui mô lớn có thể bao phủ một vùng đô thị như một thành phố,
một quận, huyện hoặc là một khu vực dân cư rộng lớn nào đó. Mạng này sử dụng các
công nghệ dành cho mạng diện rộng (WAN), có tốc độ truyền dẫn cao và khả năng
kháng lỗi mạnh.
Năm 2001, chuẩn IEEE 802.16 đã được thiết kế để mở ra một tập hợp các giao
tiếp dựa trên giao thức tầng MAC và lớp vật lý. Chuẩn 802.16 cũng đề cập đến công
nghệ WiMax là công nghệ không dây băng thông rộng đang phát triển rất nhanh với khả
năng triển khai trên phạm vi rộng và mang lại khả năng kết nối Internet tốc độ cao tới
các gia đình và công sở. Giao thức lớp MAC của chuẩn IEEE 802.16 hỗ trợ truy cập
không dây băng rộng điểm - đa điểm với tốc độ truyền dữ liệu cao trên cả hai hướng
truyền đa người dùng, trong cùng thời gian có thể cho phép hàng trăm thiết bị trên kênh
đó có thể được chia sẻ đa người dùng. IEEE 802.16 là giao diện cho hệ thống truy nhập
băng rộng cố định, lớp MAC và lớp vật lý (PHY) hoạt động ở 10 GHz - 66 GHz.
Ngoài ra chúng ta có thể kể ra các chuẩn mở rộng của chuẩn IEEE 802.16 như
chuẩn IEEE 802.16a ra đời năm 2003, chuẩn 802.16d được đưa ra năm 2004 là sự kết
hợp của chuẩn IEEE 802.16 và chuẩn IEEE 802.16a có thay đổi lớp MAC và lớp vật
lý PHY.
19
Mạng WiMax là tập hợp các mạng WiFi và được thiết kế riêng cho việc phân
bố và di động rộng, phục vụ cho: các xí nghiệp, các khu dân cư nhỏ lẻ, mạng cáp truy
nhập WLAN công cộng nối tới mạng đô thị, các trạm gốc BS của mạng thông tin di
động và các mạch điều khiển trạm BS. WiMax đem lại tốc độ cao, trên 30 Mbps.
Hiện nay, công nghệ WiMAX được chia ra thành 2 công nghệ chính đó là công
nghệ WiMAX cố định theo chuẩn IEEE 802.16d - 2004 và công nghệ WiMAX di
động theo chuẩn IEEE 802.16e - 2005.
Ưu điểm của WiMax là:
Được thiết kế riêng cho hoạt động mạng không dây diện rộng.
Những khó khăn của WiMax bao gồm:
Giá thành sản phẩm WiMax đắt hơn rất nhiều so với WiFi.
2.1.2.3. Mạng diện rộng WWAN theo chuẩn 802.20
Các mạng trải dài trên một quốc gia hoặc thậm chí toàn thế giới được gọi là
mạng diện rộng WWAN (Wireless Wide Area Networks), Internet là một trong những
mạng WAN cố định nổi tiếng nhất và các mạng GSM/GPRS và 3G đại diện cho các
mạng WAN không dây. GSM (Global System for Mobile communication) hiện là hệ
thống thông tin liên lạc di động lớn nhất thế giới cung cấp các dịch vụ chuyển mạch
kênh. GPRS (General Packet Radio Service) được giới thiệu như là một phần mở rộng
dịch vụ chuyển mạch gói được chuẩn hóa của kiến trúc GSM cung cấp tốc độ truyền
tối đa cao hơn. Với dịch vụ chuyển mạch gói ta có thể sử dụng thiết bị di động kết nối
GPRS tương tự như một máy tính kết nối với Internet, mạng GPRS hoạt động chỉ khi
dữ liệu đang được truyền đi, do đó làm giảm chi phí sử dụng.
Các mạng di động thế hệ thứ ba (3G), phát triển bởi ETSI vào năm 1999, được
thiết kế để cung cấp cuối cùng tốc độ truyền ngang bằng với các mạng cố định. Điều
này làm 3G trở thành một thay thế thú vị cho các mạng WLAN. Mặc dù mục tiêu ban
đầu của mạng không dây toàn cầu cuối cùng là hai công nghệ khác nhau cùng tồn tại.
Tại châu Âu WCDMA được chọn là công nghệ chính, trong khi CDMA2000 đang phổ
biến ở Mỹ, 85% các mạng 3G trên thế giới được dựa trên công nghệ WCDMA.
2.2. Mạng di động không dây đặc biệt MANET
2.2.1. Giới thiệu mạng MANET
MANET là chữ viết tắt của cụm từ Mobile wireless Ad hoc NETwork, là tập hợp
các nút di động có trang bị các giao tiếp mạng không dây khi thiết lập truyền thông
không cần tới sự hiện diện của các cơ sở hạ tầng mạng và các quản trị trung tâm. Trong
MANET mọi nút mạng đều thực hiện chức năng của một router, chúng cộng tác với nhau,
thực hiện chuyển tiếp các gói tin hộ các nút mạng khác nếu các nút mạng này không thể
truyền trực tiếp với nút nhận.
Mobile = di động, không chịu sự quản lý của quản trị mạng.
MANET =
Adhoc = không hạ tầng mạng, topo mạng động.
NETwork
20
Năm 1971, tại Đại học Hawaii các công nghệ mạng và truyền thông vô tuyến đã
được kết hợp lần đầu tiên trong dự án Alohanet. Mục tiêu của mạng này là kết nối các
cơ sở giáo dục ở Hawaii. Mặc dù các trạm làm việc là cố định nhưng giao thức
ALOHA thực hiện việc quản lý truy cập kênh truyền dưới dạng phân tán, do đó cung
cấp cơ sở cho sự phát triển về sau của các lược đồ truy cập kênh phân tán cho phép
hoạt động của mạng Ad Hoc.
Mạng MANET có khởi nguồn từ mạng PRNet (Packet Radio Network) và dự
án SURAN (Survivable Radio Network) của tổ chức DARPA (Defense Advanced
Research Projects Agency) thuộc chính phủ Mỹ.
Năm 1972, mạng PRnet ra đời. Đây là mạng vô tuyến gói tin đa chặng đầu tiên.
Trong ngữ cảnh này, đa chặng có nghĩa là các nút hợp tác để chuyển tiếp truyền thông
cho các nút ở xa nằm ngoài dải truyền thông của một nút khác. PRnet cung cấp cơ chế
để quản lý hoạt động trên cơ sở tập trung cũng như phân tán. PRnet cũng là mạng đầu
tiên sử dụng trạm điều khiển tập trung, sử dụng những công nghệ sau này là tiền đề để
cấu thành một mạng MANET như sau:
Phát triển kiến trúc phân tán
Là mạng sử dụng sóng vô tuyến quảng bá
Tối thiểu hóa quản lý tập trung
Sử dụng định tuyến nhớ và chuyển tiếp đa chặng (sử dụng Aloha/CSMA, phổ
trải rộng trong thập kỷ 80 thế kỷ 20)
Vào năm 1983, dự án SURAN được phát triển. Động lực thúc đẩy là:
Xu hướng kích thước thiết bị truyền dẫn ngày càng nhỏ hơn, chí phí giảm, công
suất sóng vô tuyến thấp.
Hỗ trợ nhiều giao thức sóng vô tuyến phức tạp.
Phát triển và chứng minh được các thuật toán có tính khả mở rộng (scalable
algorithms), mạng có thể có đến 10.000 nút.
Phát triển và chứng minh sức chịu đựng và khả năng tồn tại chống lại các cuộc
tấn công tinh vi. (cải tiến trải phổ rộng, topo mạng phân cấp, tạo nhóm động …)
Trong quân đội (Army Research Office-ARO):
Đầu tiên, họ sử dụng MANET cho các ứng dụng trên mặt đất.
Được sử dụng chính thay cho các mạng có cơ sở hạ tầng cố định.
Trong hải quân (Office of Naval Research-ONR):
Ban đầu được dùng cho các tàu trên biển.
Mạng MANET trên biển không có mật độ dày như mạng trên đất liền.
Đòi hỏi kết hợp với liên kết vệ tinh.
Trong lực lượng không quân:
Khảo sát sử dụng những máy bay để cung cấp truyền thông với các trạm mặt đất.
21
Ứng dụng của mạng MANET
Truyền dữ liệu không dây di động có những bước tiến cả về công nghệ và khả
năng sử dụng, động lực thúc đẩy là sự phát triển mạnh mẽ của Internet và sự thành
công của thế hệ hệ thống di động thứ hai (2G), thế hệ hệ thống di động thứ ba (3G).
Dự kiến trong tương lai gần, vai trò truyền dữ liệu khoảng cách ngắn sẽ phát triển, là
một phần bổ sung cho truyền thông quy mô lớn truyền thống bởi phần lớn các thiết bị
thông tin liên lạc cũng như giao tiếp giữa con người xảy ra ở khoảng cách nhỏ hơn
mười mét. Một yếu tố khác thúc đẩy sự phát triển của mạng Ad Hoc là các dải tần số
được cấp phép miễn phí đem đến việc sử dụng các công nghệ truyền thông phát triển
(như Bluetooth) triển khai dễ dàng và không tốn kém.
Mạng MANET có tiềm năng to lớn cho các ứng dụng thương mại và quân sự,
và đặc biệt hữu ích cho việc cung cấp sự hỗ trợ thông tin liên lạc tại những nơi không
có cơ sở hạ tầng thông tin liên lạc sẵn có hoặc việc triển khai một cơ sở hạ tầng cố
định về mặt kinh tế là không khả thi. Ứng dụng của MANET bao gồm các hoạt động
quân sự, cứu trợ khẩn cấp, chăm sóc y tế, hoạt động mạng gia đình, môi trường học
thuật và các hoạt động khắc phục thảm họa. Ví dụ về các tình huống thiên tai bao gồm
động đất và lũ lụt, nơi các đội cứu hộ cần phải phối hợp với nhau mà không có các
mạng cố định sẵn có; các hoạt động quân sự, nơi thông tin liên lạc trong một môi
trường thù địch; các doanh nghiệp, nơi nhân viên chia sẻ thông tin trong hội nghị…
Hình 4. Mạng MANET và Sensor không dây [14]
22
2.2.2. Các đặc điểm của mạng MANET
Trong mạng AD HOC, các nút là di động và được trang bị các bộ phát và bộ
nhận không dây sử dụng các loại ăng ten đẳng hướng để phát quảng bá hoặc ăng ten
định hướng để phát điểm-điểm, có thể điều chỉnh được, hoặc kết hợp các loại ăng ten
này. Tại một thời điểm, tùy thuộc vào vị trí của nút và dạng bao phủ của bộ nhận và
phát tín hiệu, mức công suất phát và các mức giao thoa cùng kênh, kết nối không dây
giữa các nút có dạng ngẫu nhiên, đồ thị đa chặng. Cấu hình này thay đổi theo thời gian
do các nút di chuyển hoặc điều chỉnh các thông số phát và nhận sóng.
Mạng MANET có một số đặc điểm nổi bật có ảnh hưởng tới thiết kế và hiệu
suất của các giao thức trong mạng được trình bày dưới đây:
1. Cấu hình mạng động: Các nốt di chuyển tự do, do vậy cấu hình mạng gồm
nhiều chặng có thể thay đổi ngẫu nhiên và liên tục tại bất kì thời điểm nào, và
có thể bao gồm cả liên kết song hướng và một hướng.
2. Các liên kết với dung lượng thay đổi - băng tần hạn chế: Các liên kết vô tuyến
có dung lượng thấp hơn nhiều so với các liên kết hữu tuyến tương ứng. Ngoài
ra, thông lượng thực của liên kết vô tuyến sau khi tính toán ảnh hưởng của đa
truy nhập, fading, tạp âm và nhiễu... thường nhỏ hơn nhiều so với tốc độ truyền
dẫn tối đa.
Dung lượng thấp thường gây ra vấn đề tắc nghẽn, nghĩa là lưu lượng tổng
thường vượt quá dung lượng của mạng.
3. Hoạt động tiết kiệm năng lượng: Một số hoặc tất cả các nút trong mạng
MANET có thể dùng pin làm nguồn cung cấp năng lượng hoạt động. Đối với
các nút này, tiêu chí thiết kế hệ thống quan trọng nhất của việc tối ưu hóa là vấn
đề tiết kiệm năng lượng. Để thực hiện tiêu chí này, các nút trong mạng Ad Hoc
bị hạn chế về khả năng tính toán của CPU, kích thước bộ nhớ, khả năng xử lý
tín hiệu, và mức năng lượng phát và nhận sóng.
4. Bảo mật vật lý hạn chế: Đối với các mạng di động vô tuyến, khả năng bị nghe
trộm, giả mạo và tấn công từ chối dịch vụ DOS (denial-of-service) cần được
xem xét cẩn thận. Các kỹ thuật bảo mật cần được triển khai trên nhiều tầng giao
thức để làm giảm các nguy cơ bảo mật.
2.2.3. Phân loại
2.2.3.1. Phân loại mạng MANET theo cách thức định tuyến
Mạng MANET định tuyến một chặng (Single-hop)
Mạng MANET định tuyến một chặng là loại mô hình mạng Ad Hoc đơn giản
nhất, trong đó, tất cả các nút đều nằm trong cùng một vùng phủ sóng, nghĩa là các nút
có thể kết nối trực tiếp với các nút khác mà không cần thông qua các nút trung gian.
Trong mô hình này, các nút có thể di chuyển tự do nhưng chỉ trong một phạm
vi nhất định đủ để nút có thể liên lạc trực tiếp với các node khác trong mạng.
23
Hình 5. Định tuyến Single-hop
Mạng MANET định tuyến đa chặng Multi-hop
Đây là mô hình phổ biến nhất trong mạng MANET, mô hình này khác với mô
hình trước là các nút có thể kết nối với các nút khác trong mạng mà có thể không cần
phải có kết nối trực tiếp với nhau. Các nút có thể định tuyến đến nút khác thông qua
các nút trung gian trong mạng. Để mô hình này có thể hoạt động một cách hoàn hảo
thì cần phải có các giao thức định tuyến phù hợp với mô hình mạng MANET.
Hình 6. Định tuyến Multi-hop
Mô hình MANET định tuyến Mobile Multi-hop
Mô hình này là sự mở rộng của mô hình thứ hai với một chút khác biệt: mô
hình này tập trung vào các ứng dụng có tính chất thời gian thực như audio, video.
2.2.3.2. Phân loại mạng MANET theo chức năng của Nút
Mạng MANET đẳng cấp (Flat MANET)
Trong kiến trúc này, tất cả các nút có vai trò ngang hàng với nhau (peer-to-
peer) và các nút cũng đóng vai trò như các router dùng để định tuyến các gói dữ liệu
truyền trên mạng. Trong những mạng lớn thì kiến trúc Flat không tối ưu cho việc sử
dụng tài nguyên băng thông của mạng vì những thông báo điều khiển (control
message) phải truyền trên toàn bộ mạng. Tuy nhiên, nó thích hợp trong những cấu
hình mà các nút di chuyển nhiều.
Mạng MANET phân cấp (Hierarchical MANET)
Đây là mô hình mạng được sử dụng phổ biến nhất trong mạng MANET. Trong
kiến trúc này, mạng chia làm các domain, trong mỗi domain bao gồm một hoặc nhiều
cluster với mỗi cluster bao gồm một hoặc nhiều nút. Do đó, nút trong kiến trúc này
chia làm hai loại:
24
Master node là node quản trị một cluster và có nhiệm vụ chuyển dữ liệu của
các nút trong cluster đến các nút trong các cluster khác và ngược lại. Nói cách
khác, nó có chức năng như một gateway.
Normal node là các nút nằm trong cùng một cluster và chỉ có thể kết nối với
các nút trong cùng một cluster hoặc kết nối với các nút trong các cluster khác
thông qua master node.
Hình 7. Mạng MANET phân cấp
Với các cơ chế trên, mạng sử dụng tài nguyên băng thông mạng hiệu quả hơn vì
các thông báo điều khiển chỉ phải truyền trong một cluster. Tuy nhiên, việc quản lý
tính chuyển động của các nút trở nên phức tạp hơn. Kiến trúc mạng phân cấp thích hợp
cho các mạng có tính chuyển động thấp.
Mạng MANET kết hợp (Aggregate MANET)
Trong kiến trúc mạng này, mạng phân thành các zone và các nút được chia vào
trong các zone. Mỗi nút bao gồm hai mức topo (topology ): topo mức thấp (node level)
và topo mức cao (zone level) (high level topology).
Ngoài ra, mỗi nút còn đặc trưng bởi hai ID: node ID và zone ID. Trong một
zone có thể áp dụng kiến trúc đẳng cấp hoặc kiến trúc phân cấp.
Hình 8. Mạng MANET kết hợp
25
Vấn đề định tuyến trong mạng MANET
Trên thực tế trước khi một gói tin đến được đích, nó có thể phải được truyền
qua nhiều chặng, như vậy cần có một giao thức định tuyến để tìm đường đi từ nguồn
tới đích qua hệ thống mạng. Giao thức định tuyến có hai chức năng chính, lựa chọn
các tuyến đường cho các cặp nguồn-đích và phân phối các gói tin đến đích chính xác.
Truyền thông trong mạng MANET dựa trên các đường đi đa chặng và mọi nút
mạng đều thực hiện chức năng của một router, chúng cộng tác với nhau, thực hiện
chuyển tiếp các gói tin hộ các nút mạng khác nếu các nút mạng này không thể truyền
trực tiếp với nút nhận, do vậy định tuyến là bài toán quan trọng nhất đối với việc
nghiên cứu MANET. Cho đến nay, đã có nhiều thuật toán định tuyến được đề xuất,
mỗi thuật toán đều có các ưu và nhược điểm riêng. Điều đặc biệt là mức độ của các ưu
nhược điểm phụ thuộc rất nhiều vào mức độ di động của các nút mạng. Một số thuật
toán là ưu việt hơn các thuật toán khác trong điều kiện các nút mạng di động ở mức độ
thấp nhưng lại kém hơn hẳn khi mức độ di động của các nút mạng tăng cao. Đề tài
luận văn này chỉ nghiên cứu sâu vấn đề định tuyến trong mạng MANET nhằm mục
đích đánh giá và so sánh ảnh hưởng của sự di động của nút mạng đến hiệu quả của một
số thuật toán định tuyến trong mạng MANET.
26
Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG
MANET
Chương 3 trình bày vấn đề định tuyến trong mạng có dây truyền thống cùng
những yêu cầu chung đối với các thuật toán trong mạng MANET để giải thích cho việc
tạo và sử dụng những thuật toán định tuyến mới phù hợp với những đặc điểm của
mạng MANET.
3.1. Các giao thức định tuyến phổ biến trong mạng có dây truyền thống
Định tuyến là việc tìm đường đi từ nguồn tới đích qua hệ thống mạng. Giao
thức định tuyến có chức năng chính là lựa chọn đường cho các cặp nguồn-đích và
phân phát gói tin tới đích chính xác. Với đặc điểm tỉ lệ lỗi gói tin thấp, cấu hình ít thay
đổi và thay đổi chậm truyền thông trong mạng có dây truyền thống có thể áp dụng các
thuật toán định tuyến dựa trên bảng là giải thuật trạng thái liên kết (Link State
Routing) hoặc véc tơ khoảng cách (Distance Vector Routing). Thuật toán Link State
được sử dụng trong giao thức OLSF (Open Shortest Path First) của Internet. Thuật
toán Distance Vector còn được gọi là thuật toán Bellman-Ford, được dùng trong mạng
ARPANET lúc mới ra đời và được sử dụng trong mạng Internet với tên gọi là RIP
(Routing Information Protocol). Các giao thức định tuyến truyền thống cũng sử dụng
định tuyến nguồn (Source Routing) và kỹ thuật flooding để tìm đường đi cho các gói
tin trong mạng.
3.1.1. Distance Vector
Trong Distance Vector mỗi nút chỉ theo dõi chi phí của các liên kết đi ra của nó,
nhưng thay vì quảng bá thông tin này đến tất cả các nút, nó quảng bá định kỳ đến các
hàng xóm của nó một ước tính các khoảng cách ngắn nhất đến tất cả các nút khác
trong mạng. Các nút nhận sau đó sử dụng thông tin này để tính toán lại các bảng định
tuyến, bằng cách sử dụng thuật toán đường đi ngắn nhất.
So với Link State, Distance Vector tính toán hiệu quả hơn, dễ dàng hơn để thực
hiện và đòi hỏi không gian lưu trữ ít hơn nhiều. Tuy nhiên, Distance Vector có thể gây ra
sự hình thành các vòng lặp định tuyến ngắn và dài. Nguyên nhân chính cho việc này là
các nút chọn chặng tiếp theo của chúng một cách hoàn toàn dựa trên thông tin có thể là cũ.
3.1.2. Link State
Trong định tuyến Link State, mỗi nút duy trì một khung nhìn đầy đủ về cấu hình
mạng với chi phí cho từng liên kết. Để giữ cho các chi phí này phù hợp, mỗi nút quảng
bá định kỳ các chi phí liên kết của các liên kết đi ra của nó cho tất cả các nút khác
bằng cách sử dụng kỹ thuật flooding. Khi một nút nhận thông tin này, nó cập nhật
khung nhìn của nó về mạng và áp dụng thuật toán tìm đường đi ngắn nhất để chọn
chặng tiếp theo cho từng đích đến.
27
Một số chi phí liên kết trong một khung nhìn của nút có thể không xác định được
do độ trễ lan truyền lớn, mạng phân vùng… như vậy không phù hợp với khung nhìn cấu
hình mạng có thể dẫn đến hình thành các vòng lặp định tuyến. Tuy nhiên, những vòng lặp
là ngắn, vì các gói tin sẽ bị loại bỏ nếu đi quá một số chặng nhất định trong mạng.
3.1.3. Source Routing
Source routing có nghĩa là mỗi gói tin phải mang theo đường dẫn đầy đủ mà gói
tin nên đi trong mạng trong tiêu đề của nó, khi đó các nút trung gian chỉ việc chuyển tiếp
các gói tin theo đường dẫn đó. Như vậy, việc xác định đường dẫn đầy đủ (định tuyến)
được thực hiện tại nút nguồn. Ưu điểm của phương pháp này là loại bỏ nhu cầu quảng
cáo đường định kỳ, các gói tin phát hiện hàng xóm và nó rất dễ dàng tránh các vòng lặp
định tuyến. Vấn đề lớn nhất với định tuyến nguồn là khi mạng lớn và đường đi dài, việc
đặt toàn bộ đường trong tiêu đề gói tin sẽ làm lãng phí băng thông.
3.1.4. Kỹ thuật Flooding
Nhiều giao thức định tuyến sử dụng quảng bá để phân phối thông tin điều
khiển, có nghĩa là, gửi thông tin điều khiển từ nút nguồn gốc cho tất cả các nút khác.
Một hình thức quảng bá được sử dụng rộng rãi là kỹ thuật flooding hoạt động như sau.
Nút nguồn gửi thông tin của nó cho các nút hàng xóm. Những nút hàng xóm sẽ chuyển
tiếp cho hàng xóm của chúng và cứ tiếp tục như vậy, cho đến khi các gói tin đến được
tất cả các nút trong mạng. Một nút sẽ chỉ chuyển tiếp một gói một lần và để đảm bảo
điều này một số kiểu số thứ tự có thể được sử dụng. Số thứ tự này được tăng lên khi
mỗi gói tin mới được một nút gửi.
3.2. Các yêu cầu đối với thuật toán định tuyến trong mạng MANET
3.2.1. Mục tiêu thiết kế các giao thức định tuyến cho mạng MANET
Như ta đã biết, các đặc tính xác định của mạng ad hoc bao gồm các thiết bị có
tài nguyên hạn chế, băng thông thấp, tỷ lệ lỗi cao và topo động. Trong số các nguồn tài
nguyên của nút mạng, năng lượng pin thường là bị ràng buộc nhất. Do đó, mục tiêu
thiết kế điển hình cho các giao thức định tuyến mạng Ad Hoc thường bao gồm:
Phụ tải điều khiển tối thiểu (Minimal control overhead). Kiểm soát việc gửi
gói tin để tiết kiệm băng thông, chi phí xử lý và năng lượng pin cho cả việc
truyền và nhận gói tin. Bởi vì sử dụng băng thông là một phần chi phí, giao
thức định tuyến không nên gửi nhiều hơn số lượng tối thiểu các thông báo điều
khiển cần cho các hoạt động, và cần được thiết kế sao cho con số này là tương
đối nhỏ. Trong khi truyền năng lượng tiêu thụ gấp nhiều lần khi nhận, do đó
việc giảm kiểm soát thông báo cũng giúp bảo tồn năng lượng pin.
Phụ tải xử lý tối thiểu (Minimal processing overhead). Các thuật toán tính toán
phức tạp đòi hỏi nhiều chu trình xử lý trong các thiết bị. Các chu trình xử lý làm
cho các thiết bị di động sử dụng nguồn tài nguyên, tiêu thụ nhiều năng lượng
pin. Các giao thức đơn giản với yêu cầu quá trình xử lý tối thiểu từ thiết bị di
28
động dẫn đến năng lượng pin được dự trữ cho các nhiệm vụ theo định hướng
người sử dụng nhiều hơn, đồng thời kéo dài tuổi thọ pin.
Khả năng định tuyến đa chặng (Multihop routing capability). Phạm vi truyền
dẫn không dây của các nút di động thường được giới hạn, các nguồn và đích có
thể không nằm trong phạm vi truyền dẫn trực tiếp của nhau. Do đó, các giao
thức định tuyến phải có khả năng khám phá các tuyến đường đa chặng giữa
nguồn và đích để giao tiếp giữa các nút là có thể xảy ra.
3.2.2. Áp dụng các thuật toán định tuyến truyền thống trong mạng MANET
Các giao thức truyền thống như Distance Vector Routing hay Link State Routing
được sử dụng trong các mạng truyền thống với tỉ lệ lỗi gói tin thấp, băng thông lớn, cấu
hình ít thay đổi và thay đổi chậm. Ngược lại, những đặc điểm nổi bật của mạng
MANET là tỉ lệ lỗi gói tin cao, băng thông thấp, cấu hình động. Vậy chúng ta có thể sử
dụng các giao thức truyền thống Distance Vector Routing hay Link State Routing để
định tuyến trong mạng Ad Hoc không? Câu trả lời là không, vì các lý do sau:
Thứ nhất, Link State và Distance Vector được thiết kế cho một topo tĩnh, có
nghĩa là chúng sẽ gặp vấn đề về tính hội tụ về trạng thái ổn định cấu hình mạng
ad hoc thường xuyên thay đổi. Link State và distance vector sẽ làm việc rất tốt
trong một ad hoc có tính di động thấp, tức là một mạng mà ở đó topo không
thay đổi thường xuyên. Vấn đề tồn tại là link-state và distance vector phụ thuộc
nhiều vào các thông báo kiểm soát định kỳ. Mà số lượng các nút mạng lớn dẫn
đến số lượng các đích đến cũng lớn. Điều này đòi hỏi trao đổi dữ liệu lớn và
thường xuyên giữa các nút mạng, mâu thuẫn với thực tế là tất cả các thông tin
cập nhật trong một mạng ad hoc kết nối không dây được truyền qua không khí
và do đó tốn kém các tài nguyên như băng thông, năng lượng pin và thời gian
CPU. Bởi vì cả link-state và distance vector cố gắng để duy trì các tuyến đường
cho tất cả các đích đến có thể truy cập, điều này cần thiết để duy trì các tuyến
đường và cũng làm lãng phí nguồn tài nguyên.
Thứ hai, một đặc trưng khác của các giao thức truyền thống là chúng giả định
các liên kết là theo hai hướng cân xứng, ví dụ: việc truyền giữa hai host hoạt
động tốt như nhau trong cả hai hướng. Trong môi trường vô tuyến không dây
điều này không luôn luôn đúng như vậy.
Như đã trình bày ở trên, các giao thức định tuyến truyền thống như Link State
và Distance Vector không thể áp dụng trong mạng MANET vì chúng được thiết kế cho
mạng có topo tĩnh và các liên kết là liên kết đối xứng. Vì vậy, khi thiết kế các giao
thức định tuyến mới cho mạng MANET ta cần phải xem xét các yêu cầu sau đây:
1. Phù hợp với topo động của mạng: Thuật toán phải được thiết kế sao cho phù
hợp với tính động của topo mạng và các liên kết bất đối xứng.
2. Không để xảy ra hiện tượng lặp định tuyến: Giải pháp đưa ra có thể là sử dụng bộ
đếm chặng trong mỗi gói tin. Mỗi khi gói tin di chuyển đến một nút mạng mới, bộ
đếm chặng sẽ tăng thêm một, và đến một giá trị nào đó thì gói tin sẽ bị loại bỏ.
29
3. Chi phí tìm đường thấp: Tổng số gói tin tìm đường thấp và thời gian cần thiết
để tìm được đường đi nhỏ là những yêu cầu quan trọng đối với vấn đề định
tuyến trong mạng không dây.
4. Bảo mật: Giao thức định tuyến của mạng Ad Hoc có thể bị tấn công dễ dàng ở
một số dạng như đưa ra các cập nhật định tuyến không chính xác hoặc ngăn cản
việc chuyển tiếp gói tin, gián tiếp gây ra việc từ chối dịch vụ dẫn đến gói tin
không bao giờ đến được đích. Chúng cũng có thể thay đổi thông tin định tuyến
trong mạng, cho dù các thông tin đó là không nguy hiểm nhưng cũng gây tốn
băng thông và năng lượng, vốn là những tài nguyên ”quý hiếm” trong mạng
ad hoc. Do vậy cần có những phương pháp bảo mật thích hợp để ngăn chặn việc
sửa đổi hoạt động của giao thức.
5. Hoạt động phân tán: Cách tiếp cận tập trung cho mạng ad hoc sẽ thất bại do sẽ
tốn rất nhiều thời gian để tập hợp các thông tin trạng thái hiện tại của mạng để
tính toán rồi lại phát tán lại nó cho các nút mạng. Trong thời gian đó, cấu hình
mạng có thể đã thay đổi rất nhiều.
6. Thiết lập những cụm mạng nhỏ: Nếu giao thức định tuyến có thể xác định
được các nút mạng gần nhau và thiết lập chúng thành một cụm mạng nhỏ thì sẽ
rất thuận tiện trong định tuyến. Nếu các nút mạng đơn di chuyển nhanh hơn thì
các cụm mạng lại ổn định hơn. Do đó, định tuyến trong các cụm mạng sẽ đơn
giản hơn rất nhiều.
Vấn đề đặt ra là làm thế nào để đồng thời đạt được một số trong các yêu cầu
nêu trên khi chúng có thể mâu thuẫn với nhau? Ta xét yêu cầu thứ nhất và yêu cầu thứ
ba, dễ thấy theo yêu cầu thứ nhất thuật toán phải hoạt động tốt trong điều kiện topo
của mạng thay đổi liên tục khi đó các nút mạng di chuyển liên tục dẫn đến số gói tin
dùng tìm đường từ các cặp nguồn-đích nhiều hơn đồng thời làm tăng thời gian tìm
đường, điều này mâu thuẫn với yêu cầu thứ ba. Chính vì vậy, ta cần đánh giá ảnh
hưởng của mức độ linh động của các nút mạng đến hiệu quả của các giao thức định
tuyến. Để từ đó:
Đề xuất chọn sử dụng giao thức định tuyến thích hợp với mức độ linh hoạt của
mạng cụ thể.
Có thể điều chỉnh (tinh chỉnh) các tham số hoạt động của các giao thức định
tuyến cho tối ưu.
3.3. Phân loại các giao thức định tuyến cho MANET [16]
Các giao thức định tuyến trong mạng MANET ra đời bằng cách cải tiến, bổ
sung và kết hợp các thuật toán của các giao thức định tuyến truyền thống (Link State
Routing, Distance Vector Routing, Source Routing) với nhau. Dưới đây tôi trình bày
sơ lược về bốn giao thức định tuyến DSDV, OLSR, AODV và DSR được trình bày
trong luận văn.
30
Destination-Sequenced Distance-Vector Routing (DSDV) là giao thức định
tuyến bảng cho các mạng ad hoc dựa trên thuật toán Bellman-Ford. Nó được phát triển
bởi C. Perkins và P.Bhagwat vào năm 1994. Đóng góp chính của thuật toán là giải
quyết vấn đề lặp định tuyến.
Optimized Link State Routing Protocol (OLSR) là giao thức định tuyến IP tối
ưu hóa cho các mạng ad hoc đặc biệt. Nó thuộc nhóm giao thức định tuyến chủ ứng
dựa trên trạng thái liên kết, sử dụng thông báo Hello and Topology Control (TC) để
tìm và sau đó lan truyền thông tin trạng thái liên kết trong toàn mạng. Từng nút sử
dụng thông tin topo mạng để tính toán những chặng tiếp theo đến mọi đích trong mạng
theo đường đi có số chặng chuyển tiếp nhỏ nhất.
Ad hoc On-Demand Distance Vector (AODV) là giao thức định tuyến cho các
mạng MANET. Nó được phát triển bởi trung tâm nghiên cứu Nokia, Đại học California,
Santa Barbara và Đại học Cincinnati bởi Perkins, E. Belding-Royer và S. Das. AODV là
giao thức định tuyến phản ứng, nó thiết lập một tuyến đường đến đích khi có yêu cầu.
Cũng giống như DSDV, AODV sử dụng số sequence number để cập nhật tuyến đường
để tránh vấn đề lặp định tuyến.
Dynamic Source Routing (DSR) là giao thức định tuyến cho các mạng ad hoc.
Tương tự như AODV, DSR là định tuyến theo yêu cầu. Tuy nhiên, nó sử dụng định
tuyến nguồn thay vì sử dụng bảng định tuyến tại từng điểm trung gian.
3.3.1. Các khái niệm liên quan
3.3.1.1. Định tuyến chủ ứng và định tuyến phản ứng
Định tuyến chủ ứng (Proactive routing) là phương pháp định tuyến của các
giao thức mà đường tới tất cả các đích được tính toán trước. Các thông tin định tuyến
được cập nhật định kỳ hoặc bất cứ khi nào cấu hình mạng thay đổi. Ưu điểm của
phương pháp là độ trễ phát gói tin thấp. Tuy nhiên, một số đường không cần dùng đến
và việc truyền các thông điệp định kỳ tiêu tốn băng thông khi mạng thay đổi nhanh.
Định tuyến phản ứng (Reactive routing) là phương pháp định tuyến theo yêu
cầu. Đường tới đích không được tính toán trước và chỉ được xác định khi cần đến. Quá
trình phát hiện liên kết bị hỏng và xây dựng lại đường được gọi là quá trình duy trì
đường. Ưu điểm của định tuyến phản ứng là hạn chế được băng thông do chỉ cần
đường tới các đích cần thiết và loại bỏ các cập nhật định kỳ. Tuy nhiên, vấn đề với
phương pháp là độ trễ lớn trước khi phát do việc phát hiện đường.
3.3.1.2. Cập nhật định kỳ và cập nhật theo sự kiện
Cập nhật định kỳ thực hiện bằng việc phát các gói tin định tuyến một cách định
kỳ. Kỹ thuật này làm đơn giản hóa các giao thức và cho phép các nút học được về cấu
hình và trạng thái của toàn bộ mạng. Tuy nhiên, giá trị quãng thời gian cập nhật là một
tham số quan trọng.
Cập nhật theo sự kiện diễn ra khi có sự kiện xảy ra trong mạng như liên kết
hỏng hoặc liên kết mới xuất hiện. Khi đó, gói tin cập nhật sẽ được quảng bá và trạng
Tải về để xem bản đầy đủ
91 trang
09/04/2025
130
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Đánh giá ảnh hưởng của sự di động của nút mạng đến hiệu quả của các thuật toán đị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_anh_huong_cua_su_di_dong_cua_nut_mang_den.pdf
