ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Văn Tứ
KHẢO SÁT ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG
CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ
GIAO THỨC ĐỊNH TUYẾN TRONG MANET
Phạm Văn Tứ KHẢO SÁT ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG
CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ
GIAO THỨC ĐỊNH TUYẾN TRONG MANET
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS.TS. Nguyễn Đình Việt
Cán bộ đồng hướng dẫn: Ths. Đoàn Minh Phương
HÀ NỘI - 2010
1.3.1. Giới thiệu về NS-2 5
1.3.2. Khả năng mô phỏng của NS-2 7
1.4. Tổ chức của KLTN 8
Chương 2. GIAO THỨC MAC CỦA MẠNG LAN VÀ WLAN 9
2.1. Mạng LAN và mạng WLAN 9
2.2. Chuẩn 802.3 và giao thức CSMA/CD 10
2.3. Chuẩn 802.11 và giao thức CSMA/CA 12
Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN 15
3.1. Mạng MANET 15
3.1.1. Lịch sử phát triển và các ứng dụng 15
3.1.2. Các đặc điểm chính của mạng MANET 16
3.2. Vấn đề định tuyến trong mạng MANET 17
3.2.1 Các thuật toán định tuyến truyền thống 17
3.2.2. Các yêu cầu chính đối với việc định tuyến trong mạng MANET 18
3.2.3. Phân loại các kỹ thuật định tuyến 19
3.2.3.1. Link state và Distance Vector 19
3.2.3.2. Định tuyến chủ ứng và phản ứng 20
3.2.3.3. Định tuyến nguồn và định tuyến theo chặng 21
3.3. Các giao thức định tuyến chính trong mạng MANET 22
3.3.1. DSDV 22
3.3.2 OLSR [8] 23
3.3.3. AODV [12] 25
3.3.4. DSR [7] 27 3.3.5. TORA [11] 28
Chương 4. ĐÁNH GIÁ BẰNG MÔ PHỎNG ẢNH HƯỞNG CỦA SỰ CHUYỂN ĐỘNG
CỦA CÁC NÚT MẠNG ĐẾN HIỆU SUẤT CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN 30
4.1. Xác định các tham số hiệu suất cần đánh giá và cách thức phân tích kết quả mô phỏng
30
Hình 1: Sự phát triển của mạng không dây và di động 1
Hình 2: Cấu trúc của NS-2 5
Hình 3: Luồng các sự kiện cho file Tcl chạy trong NS-2 6
Hình 4: Chu trình hoạt động của giao thức CSMA/CD (bên gửi) 11
Hình 5: Chu trình hoạt động của giao thức CSMA/CA (bên gửi) 13
Hình 6: Hoạt động lắng nghe kênh truyền của giao thức CSMA/CA 14
Hình 7: Phân loại các giao thức định tuyến trong mạng MANET 22
Hình 8: Tô-pô mạng thay đổi 23
Hình 9: Quy trình chuyển tiếp gói tin khi sử dụng kíp đa điểm – MPR 24
Hình 10: OLSR ngăn chặn vòng lặp bằng việc sử dụng MPR để chuyển phát gói tin 25
Hình 11: quá trình khám phá tuyến trong AODV 25
Hình 12: Định tuyến nguồn động (DSR) 27
Hình 13: Diện tích mạng mô phỏng và các nút mạng 35
Hình 14: Di chuyển một nút theo mô hình Random Waypoint 37
Hình 15: Di chuyển của 8 nút theo mô hình Random Walk 38
Hình 16: Đồ thị tỷ lệ phân phát gói thành công – Random Waypoint 44
Hình 18: Đồ thị tỷ lệ phân phát gói tin thành công – Random Walk 45
Hình 19: Đồ thị thời gian thiết lập kết nối trung bình_Random-Waypoint 46
Hình 20: Đồ thị thời gian thiết lập kết nối trung bình_Random-Walk 46 DANH MỤC BẢNG
Bảng 1: Sự phát triển của chuẩn 802.3 10
Bảng 2: Sự phát triển của chuẩn 802.11 12
Bảng 3: Cấu trúc tệp vết 31
Bảng 4: Các trường thêm vào trong cấu trúc tệp vết phụ thuộc vào kiểu gói tin 32
Bảng 5: Cấu hình mạng mô phỏng 36
Bảng 6: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Waypoint 41
Bảng 7: Thống kê chi tiết tỷ lệ phân phát gói tin thành công - Random Walk 42
DSR Dynamic Source Routing RREP Route Reply
IEEE Institute of Electrical and
Electronics Engineers
RREQ Route Request
LAN Local Area Network TORA Temporally-Ordered
Routing Algorithm
MAC Media Access Control WLAN Wireless LAN
LỜI CẢM ƠN
Trước tiên, tôi xin gửi lời cảm ơn chân thành tới PGS.TS.Nguyễn Đình Việt,
người thầy đã tận tình giúp đỡ tôi trong suốt quá trình làm khóa luận. Tôi cũng xin gửi
lời cảm ơn tới Ths. Đoàn Minh Phương, người đã hướng dẫn tôi trong giai đoạn chuẩn
bị nhận đề tài.
Tôi xin gửi lời biết ơn sâu sắc tới thầy, cô trong trường Đại Học Công Nghệ, Đại
Học Quốc Gia Hà Nội. Thầy, cô đã dìu dắt, truyền lại cho chúng tôi không chỉ những
kiến thức chuyên ngành mà còn dạy bảo chúng tôi đạo làm người, rèn luyện cho chúng
tôi nghị lực, khát vọng vươn lên, phát huy khả năng tư duy sáng tạo trong mọi lĩnh
vực.
Cuối cùng, tôi xin được cảm ơn gia đình, bạn bè, những người thân yêu nhất của
tôi. Mọi người luôn ở bên cạnh tôi, động viên, khuyến khích tôi vươn lên trong cuộc
sống.
Hà nội, tháng 5 năm 2010
Nikola Tesla truyền
thành công sóng radio.
Heinrich Rudolf Hertz
đã tạo ra được sóng điện
từ. Ông đã chứng minh
được thuyết Maxwell
thông qua thực nghiệm.
1887
1893
1895
thông tin qua sóng vô
tuyến.
-
1982
: Hội nghị CEPT
đã thống nhất chọn
GSM để phát triển thành
tiêu chuẩn cho hệ thống
điện thoại di động có thể
được sử dụng trên khắp
châu Âu.
- 1991: Các mạng GSM
đầu tiên đã được đưa ra
bởi Radiolinja ở Phần
Lan với kỹ thuật bảo
dưỡng cơ sở hạ tầng
chung từ Ericsson.
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Phạm Văn Tứ 3 K51MMT
-20/5/1999: Chính
thức phát hành chuẩn
Bluetooth 1.0
Chuẩn IEEE 802.11
(WiFi) đã được tạo ra,
với tốc độ tối đa là
2Mb/s.
1997
1998, 1999
2001
2003
2004, 2009
2010
Chuẩn IEEE 802.16 được
phát hành. Chuẩn này
được biết đến dưới cái tên
WIMAX. - Chuẩn
802.11g
được
phát hành với tốc độ
tăng hơn 10 lần so với
tốc độ hiện tại
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Phạm Văn Tứ 4 K51MMT
1.2 . Mục tiêu nghiên cứu của khóa luận
Với đặc tính có thể hoạt động không phụ thuộc vào cơ sở hạ tầng mạng, triển
khai nhanh, linh hoạt ở mọi vị trí địa hình khác nhau, mạng MANET đang là tâm điểm
nghiên cứu đầy triển vọng, sẽ là công nghệ đột phá trong tương lai với nhiều ứng dụng
hữu ích vào cuộc sống, thí dụ kết nối mạng truyền thông cho các các vùng mới xảy ra
thiên tai hoặc ứng dụng cho lĩnh vực quân sự.
Khóa luận tập trung đi sâu nghiên cứu về mạng MANET, kết hợp phân tích trên
lý thuyết cùng thực nghiệm mô phỏng để tìm ra và đánh giá ảnh hưởng sự di động của
các nút mạng ở các mức độ khác nhau đến hiệu suất của một số giao thức định tuyến.
Nội dung cụ thể gồm:
Tìm hiểu sâu về mạng MANET, trong đó chủ yếu xem xét tới các giao thức
định tuyến.
Tìm hiểu sâu về các mô hình chuyển động của nút mạng trong MANET.
Xây dựng môi trường mô phỏng, đưa các giao thức định tuyến trong mạng
MANET vào mô phỏng thông qua NS-2.
Đánh giá ảnh hưởng sự chuyển động của các nút mạng đến hiệu suất của các
giao thức định tuyến DSDV, AODV và DSR bằng bộ mô phỏng mạng NS-2.
Từ đó đưa ra các nhận xét so sánh giữa ba giao thức.
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Phạm Văn Tứ 5 K51MMT
1.3 . Công cụ nghiên cứu chính – NS-2
1.3.1. Giới thiệu về NS-2
Kịch bản OTcl có thể thực hiện những việc sau: Khởi tạo Bộ lập lịch Sự kiện
Thiết lập Mô hình mạng dùng các đối tượng thành phần mạng
Báo cho nguồn
traffic khi nào bắt đầu truyền và ngưng truyền packet trong Bộ lập lịch Sự kiện
Bộ lập lịch Sự kiện trong NS-2 thực hiện những việc sau: Tổ chức Bộ định thời mô
phỏng Huỷ các sự kiện trong hàng đợi sự kiện Triệu gọi các Thành phần mạng
trong mô phỏng.
Tùy vào mục đích của người dùng đối với kịch bản mô phỏng OTcl mà kết quả
mô phỏng có thể được lưu trữ vào tệp vết (trace file) với khuôn dạng (format) được
những người phát triển NS định nghĩa trước hoặc theo khuôn dạng do người sử dụng
NS quyết định khi viết kịch bản mô phỏng. Nội dung tệp vết sẽ được tải vào trong các
ứng dụng khác để thực hiện phân tích. NS đã định nghĩa 2 loại tệp vết:
Nam trace file (file.nam): Chứa các thông tin về tô-pô mạng như: các nút
mạng, đường truyền, vết các gói tin; dùng để minh họa trực quan mạng đã thiết
lập.
Trace file (file.tr): Tệp ghi lại vết của các sự kiện mô phỏng, tệp file dạng text,
có cấu trúc, dùng cho các công cụ lần vết và giám sát mô phỏng như: Gnuplot,
XGRAPH hay TRACEGRAPH.
Hình 3: Luồng các sự kiện cho file Tcl chạy trong NS-2
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Phạm Văn Tứ 7 K51MMT
1.3.2. Khả năng mô phỏng của NS-2
NS-2 hỗ trợ mô phỏng tốt cho cả mạng có dây và mạng không dây. Bao gồm các
ưu điểm nổi bật sau:
Chương 3: Nêu lên lịch sử hình thành, các đặc điểm chính của mạng MANET,
đồng thời mô tả chi tiết về các giao thức định tuyến như DSDV, AODV, DSR, OLSR,
TORA và phân loại các kỹ thuật định tuyến khác nhau.
Chương 4: Từ các kết quả thực nghiệm mô phỏng chúng tôi đánh giá ảnh hưởng
của sự chuyển động các nút mạng đến hiệu suất của một số giao thức định tuyến trong
mạng MANET.
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Phạm Văn Tứ 9 K51MMT
Chương 2. GIAO THỨC MAC CỦA MẠNG LAN VÀ
WLAN
2.1. Mạng LAN và mạng WLAN
Trong nhưng năm gần đây mạng WLAN đã trở lên phổ biến rộng khắp ở mọi
nơi: lớp học, sân trường, thư viện, văn phòng, quán cà phê, khách sạn, tới hộ gia đình.
Mạng WLAN đã đạt được những bước tiến khá dài và vững chắc, dần trở thành một
đối trọng của công nghệ mạng LAN phổ biến từ trước tới nay. Các lợi thế lớn mà
WLAN đem lại cho người dùng gồm:
1. Tính di động:
Với khả năng hỗ trợ của mạng không dây, người dùng không bị ràng buộc vào
các dây nối, tức là trong khi đang kết nối người sử dụng vẫn có thể di chuyển từ vị trí
này đến vị trí khác trong khu vực phủ sóng mà không bị gò bó tại một vị trí cố định
như trong mạng LAN truyền thống. Nhờ đó người dùng có thể mang theo thiết bị của
mình đến bất cứ đâu có sóng không dây là có thể truy cập vào mạng.
2. Tính mềm dẻo:
Triển khai mạng không dây rất thuận tiện và dễ dàng vì môi trường truyền luôn
có sẵn mọi lúc, mọi nơi mà không cần phải lên kế hoach trước, không cần kéo dây cáp
mạng hay bất kỳ sự vướng víu nào. Người dùng dễ dàng thiết lập kết nối một cách
nhanh chóng phục vụ cho công việc của mình.
3. Dễ dàng triển khai lắp đặt:
TX, 100BASE-T4, 100BASE-FX
802.3z
1998
1000BASE-X Gbit/s Ethernet qua cáp quang với tốc độ 1
Gbit/s
802.3ab
1999 1000BASE-T Gbit/s Ethernet qua cáp UTP với tốc độ 1 Gbit/s
802.3ae
2003 10 Gbit/s Ethernet over fiber
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Phạm Văn Tứ 11 K51MMT
2.2.2. Giao thức CSMA/CD Hình 4: Chu trình hoạt động của giao thức CSMA/CD (bên gửi)
CSMA/CD (Carrier Sense Multiple Access with Collision Detection) – là giao
thức Đa truy cập cảm nhận sóng mang có phát hiện xung đột. Mạng LAN hoạt động
dựa trên nguyên tắc này. Khi máy tính muốn truyền dữ liệu, trước tiên nó lắng nghe
xem đường truyền có bận hay không (bằng cách cảm nhận tín hiệu sóng mang). Nếu
không có, nó sẽ thực hiện truyền gói tin. Sau khi truyền gói tin, nó vẫn tiếp tục lắng
nghe để xem có máy nào định truyền tin hay không. Nếu không có xung đột, nó tiếp
tục truyền gói tin cho đến khi hoàn thành. Nếu phát hiện xung đột, nó sẽ gửi broadcast
ra toàn mạng tín hiệu nghẽn (jam signal) để các máy khác dễ dàng nhận ra xung đột.
Sau đó nó sẽ đợi một thời gian theo thuật toán Backoff rồi thử gửi lại gói tin.
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Số
luồng
MIMO
-
1997 2.4
20
1, 2 1
a
9/1999 5/3.7
20
6, 9, 12, 18, 24, 36, 48, 54 1
b
9/1999 2.4
20
1, 2, 5.5, 11 1
g
6/2003 2.4
20
1, 2, 6, 9, 12, 18, 24, 36, 48, 54 1
20 7.2, 14.4, 21.7, 28.9, 43.3, 57.8,
65, 72.2
n
10/2009
2.4/5
40 15, 30, 45, 60, 90, 120, 135,
150
4
Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
Backoff giảm đi 1. Trái lại nó được giữ nguyên cho khoảng thời gian
DIFS tiếp theo. Khi thời gian Backoff giảm đến không, nút bắt đầu truy
cập môi trường truyền. Tuy nhiên, nếu trước đó một nút khác đã truy cập
môi trường truyền trước khi thời gian Backoff của nút này giảm đến
không thì nó sẽ giữ lại giá trị thời gian Backoff hiện tại để sử dụng cho
lần truy cập tiếp theo. Khảo sát ảnh hưởng của sự chuyển động các nút mạng đến hiệu suất của một số giao thức
định tuyến trong MANET
Phạm Văn Tứ 15 K51MMT
Chương 3. MẠNG MANET VÀ BÀI TOÁN ĐỊNH TUYẾN
3.1. Mạng MANET
3.1.1. Lịch sử phát triển và các ứng dụng
Lịch sử:
Mạng di động đặc biệt (Mobile Adhoc Netwowk) là mạng tự cấu hình của các
nút di động kết nối với nhau thông qua các liên kết không dây tạo nên mạng độc lập
không phụ thuộc vào cơ sở hạ tầng mạng. Các thiết bị trong mạng có thể di chuyển
một cách tự do theo mọi hướng, do đó liên kết của nó với các thiết bị khác cũng thay
đổi một cách thường xuyên.
Nguyên lý làm việc của mạng Adhoc bắt nguồn từ năm 1968 khi các mạng
ALOHA được thực hiện. Tuy 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, đây là cơ sở lý
thuyết để phát triển kỹ thuật truy cập kênh phân tán vào mạng Adhoc.
Năm 1973 tổ chức DARPA đã bắt đầu làm việc trên mạng vô tuyến gói tin
PRnet. Đây là mạng vô tuyến gói tin đa chặng đầu tiên. Trong đó các nút hợp tác với
nhau để gửi dữ liệu tới một nút nằm ở xa khu vực kết nối thông qua một nút khác. Nó
cung cấp cơ chế cho việc quản lý hoạt động trên cơ sở tập trung và phân tán.
Một lợi điểm của làm việc đa chặng so với đơn chặng là triển khai đa chặng tạo
của mạng MANET như sau:
Cấu hình mạng động: Cấu hình mạng luôn biến đổi theo các mức độ di
chuyển của nút mạng.
Khoảng cách sóng ngắn: Khoảng cách sóng của các thiết bị di động là rất hạn
chế.
Năng lượng hạn chế: Tất cả các thiết bị di động đều sử dụng pin nên khi tham
gia vào mạng MANET chúng bị hạn chế về năng lượng, khả năng xử lý của
CPU, kích thước bộ nhớ.
Băng thông hạn chế: Các liên kết không dây có băng thông thấp hơn so với
đường truyền cáp và chúng còn chịu ảnh hưởng của sự nhiễu, suy giảm tín hiệu,
các điều kiện giao thoa vì thế mà thường nhỏ hơn tốc độ truyền lớn nhất của
sóng vô tuyến.
Bảo mật yếu: Đặc điểm của mạng MANET là truyền sóng qua môi trường
không khí, điều này khiến cho cơ chế bảo mật kém hơn so vơi môi trường
truyền cáp vì nó tiềm ẩn nhiều nguy cơ bị tấn công, nghe lén đường truyền, giả
mạo, DoS,…
Copyright: Tài liệu đại học ©