đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng manet

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "đánh giá chi phí tìm đường của một số giao thức định tuyến trong mạng manet": http://123doc.vn/document/1044173-danh-gia-chi-phi-tim-duong-cua-mot-so-giao-thuc-dinh-tuyen-trong-mang-manet.htm

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
AODV Adhoc On-Demand Distance Vector
AP Access Point
BQ Broadcast Query
BS Base Station
CBR Constant Bit Rate
CDMA Code Division Multiple Access
CGSR Clusterhead Gateway Switch Routing
CLR Clear Packet
CSMA Carrier Sense Multiple Access
CSMA/CD Carrier Sense Multiple Access/Collision Detect
CSMA/CA Carrier Sense Multiple Access/Collision Avoidance
CTS Clear To Send
DAG Directed Acyclic Graph
DCF Distributed Coordination Function
DIFS DCF Interframe Space
DRP Dynamic Routing Protocol
DSDV Destination-Sequenced Distance-Vector
DSR Dynamic Source Routing
FTP File Transfer Protocol
GPS Global Positioning System
IEEE Institude of Electrical and Electronics Engineers
IETF Internet Engineering Task Force
IRTF Internet Research Task Force
LAN Local Area Network
LCC Least Cluster Change
LQ Localized Query
MAC Medium Access Control
MAN Metropolitan Area Network
MANET Mobile Adhoc Network
MRP Multipoint Relay Selector
NAM Network Animator
NAV Network Allocation Vector
NPDU Network Protocol Data Unit
NS2 Network Simulator 2
OFDM Orthogonal Frequency Division Multiplexing
OLSR Optimized Link State Routing
OTCL Object Tool Command Language
6

PAN Personal Area Network
PCF Point Coordination Function
PIFS PCF Interframe Space
QoS Quality of Service
RD Route Delete
RN Route Notification
RREP Route Reply
RREQ Route Request
RT Routing Table
RTS Request To Send
SIFS Short Interframe Space
SRP Static Routing Protocol
SSR Signal Stability Routing
SST Signal Stability Table
TC Topology Control
TCL Tool Command Language
TCP Transmission Control Protocol
TDMA Time Division Multiple Access
TORA Temporally Ordered Routing Algorithm
UDP User Datagram Protocol
VINT Virtual InterNetwork Testbed
WAN Wide Area Network
Wi-fi Wireless Fidelity
WLAN Wireless Local Area Network
WMAN Wireless Metropolitan Area Network
WPAN Wireless Personal Area Network
WWAN Wireless Wide Area Network
WRP Wireless Routing Protocol
ZRP 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