ĐẠ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Ĩ
Ngành:
Công nghệ thông tin
Chuyên Ngành:
Truyền dữ liệu và Mạng máy tính
Mã số:
60 48 15 LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Đình Việt
Hà Nội - 2011
1
Phan Hữu Dũng
3
Mục lục
Lời cảm ơn 1
Lời cam đoan 2
Danh mục hình vẽ 6
Danh mục bảng 7
Bảng ký hiệu các chữ viết tắt 8
Chương 1: GIỚI THIỆU 10
1.1. Đặt vấn đề 10
1.2. Mục tiêu nghiên cứu 10
1.3. Tổ chức của luận văn 11
Chương 2: MẠNG WLAN VÀ MẠNG MANET 12
2.1. Mạng không dây 12
3.1. Các giao thức định tuyến phổ biến trong mạng có dây truyền thống 24
3.1.1. Distance Vector 24
3.1.2. Link State 24
3.1.3. Source Routing 25
3.1.4. Kỹ thuật Flooding 25
3.2. Các yêu cầu đối với thuật toán định tuyến trong mạng MANET 25
3.2.1. Mục tiêu thiết kế các giao thức định tuyến cho mạng MANET 25
3.2.2. Áp dụng các thuật toán định tuyến truyền thống trong mạng MANET 26
4
3.3. Phân loại các giao thức định tuyến cho MANET
[16]
27
3.3.1. Các khái niệm liên quan 28
3.3.1.1. Định tuyến chủ ứng và định tuyến phản ứng 28
3.3.1.2. Cập nhật định kỳ và cập nhật theo sự kiện 28
3.3.1.3. Tính toán phi tập trung và tính toán phân tán 29
4.1.1.4. Lý do sử dụng phương pháp mô phỏng để đánh giá hiệu năng mạng . 41
4.1.2. Công cụ mô phỏng NS-2
[1, 12, 15]
41
4.1.2.1. Các chức năng mô phỏng chính của NS 43
4.1.2.2 Cấu trúc phần mềm của NS 44
4.1.2.3. Lập trình mô phỏng bằng NS 44
4.1.3 Công cụ hỗ trợ phân tích kết quả mô phỏng 44
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 44
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 45
4.1.4. Công cụ hiển thị trực quan mạng MANET trong quá trình hoạt động
iNSPECT 46
4.2. Thiết lập mô phỏng mạng MANET trong NS 51
4.2.1. Tạo các nút mạng trong MANET 51
4.2.1.1 Nút di động 51
4.4.1.2 Mô hình phương tiện chia sẻ trong NS2 52
4.5.2 Giao thức định tuyến OLSR 64
4.5.3 Giao thức định tuyến AODV 64
4.5.4 Giao thức định tuyến DSR 65
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 66
5.1. Thực nghiệm mô phỏng 66
5.1.1 Các thông số mô phỏng 66
5.1.2 Chương trình mô phỏng 67
5.2. Các độ đo hiệu năng được dùng trong luận văn 68
5.3. Kết quả mô phỏng 68
5.3.1 Mô phỏng sử dụng mô hình Random Waypoint 68
5.3.1.1 Thiết lập thông số mô phỏng 68
5.3.2.2 Kết quả và nhận xét 70
5.3.3 Mô phỏng sử dụng mô hình Random Walk 73
5.3.3.1 Thiết lập thông số mô phỏng 73
5.3.3.2 Kết quả và nhận xét 75
Hình 7. Mạng MANET phân cấp 22
Hình 8. Mạng MANET kết hợp 22
Hình 9. Phân loại các giao thức định tuyến trong mạng MANET [13] 30
Hình 10. Tập chuyển tiếp đa điểm MPRs 32
Hình 11. Định tuyến Link State và định tuyến cải tiến trong OLSR 32
Hình 12. AODV tìm kiếm và duy trì tuyến đường 34
Hình 13. Ví dụ về Route discovery: nút A là nút nguồn, nút E là nút đích. 35
Hình 14. Ví dụ về Route maintenance: 36
Hình 15. Kiến trúc NS-2 42
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 47
Hình 17. Hình tròn bao phủ biểu diễn khu vực tắc nghẽn 48
Hình 18. Hình tròn bao phủ biểu diễn khu vực nguy hiểm 49
Hình 19. iNSpect hiển thị tọa độ (x, y) của các nút 50
Hình 20. Nút di động mô phỏng trong NS2 51
Hình 21. Mô hình phương tiện chia sẻ trong NS2 53
Danh mục bảng
Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2] 15
Bảng 2. Tổng quan về họ các chuẩn ETSI HIPERLAN [2] 15
Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15 16
Bảng 4: So sánh độ phức tạp của các giao thức định tuyến 37
Bảng 5: So sánh các đặc điểm của các giao thức định tuyến 37
Bảng 6: So sánh các đặc điểm của các giao thức định tuyến 38
Bảng 7. Các tham số của mô hình Random Waypoint 60
Bảng 8. Các tham số của mô hình Random Walk 61
Bảng 9. Các tham số hoạt động của DSDV trong NS2 63
Bảng 10. Các tham số hoạt động của OLSR trong NS2 64
Bảng 11. Các tham số hoạt động của AODV trong NS2 64
Bảng 12. Các tham số hoạt động của DSR trong NS2 65
Bảng 13. Cấu hình các mạng mô phỏng trong mô hình Random Waypoint 69
Bảng 14. Cấu hình các mạng mô phỏng theo mô hình Random Walk 74
PDA Personal Digital Assistant
9
PRnet Packet Radio Network
QoS Quality of Service
REAL Realistic and Large
RIP Routing Information Protocol
RREP Route Reply
RREQ Route Request
RTS Request To Send
SURAN Survivable Radio Network
TDMA/TDD Time Division Multiple Access/ Time Division Duplex
TORA Temporally-Ordered Routing Algorithm
UMTS Universal Mobile Telecommunications Systems
VINT Virtual InterNetwork Testbed
WIFI Wireless Fidelity
WiMAX World Interoperability for MicroAccess
WLAN Wireless Local Area Network
WMAN Wireless Metropolitan Area Networks
WPAN Wireless Personal Area Networks
WRP Wireless Routing Protocol
WWAN Wireless Wide Area Networks
ZRP Zone Routing Protocol 10
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
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.
Đá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.
11
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.
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
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, )
15 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
Frequency Range
(GHz)
2.4-2.4835
5.15-5.25 (lower)
5.25-5.35 (middle)
5.725-5.825 (upper)
2.4-2.4835 2.4-2.4835
Max.DataRate
(Mbps)
2 55 11 54
Range
< 10 m 27-30(lowerband) 75-100 30
Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2]
Chuẩn HIPERLAN/x
HIPERLAN
1
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 802.15.3 802.15.4
Frequency Range
2.4 Ghz 2.4 Ghz 2.45 Ghz 915MHz 868MHz
Max.Data Rate
1 Mpbs 55 Mpbs 250 Kpbs 40 Kbps 20 Kbps
Range
< 10 m < 10 m 10 - 75 m
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ả
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.
M
obile = 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
18
Đượ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.
19
Ứ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ị…
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.
21 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)
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
23
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.
Copyright: Tài liệu đại học ©