ĐẠ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
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
ĐẠ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
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
TÓM TẮT
Ngày nay, cùng với sự bùng nổ, phát triển mạnh mẽ của các thiết bị di động cá
nhân như: laptop, smartphone, tablet,…, thì nhu cầu kết nối giữa các thiết bị này cũng
ngày càng đòi hỏi cao hơn về tốc độ và khả năng di chuyển trong khi kết nối. Mạng di
động đặc biệt – MANET (Mobile Ad-hoc Network) là một trong những công nghệ
vượt trội đáp ứng nhu cầu kết nối đó nhờ khả năng hoạt động không phụ thuộc vào cơ
sở hạ tầng mạng cố định, với chi phí hoạt động thấp, triển khai nhanh và có tính di động
cao. Tuy nhiên, hiện nay mạng MANET vẫn chưa được ứng dụng rộng rãi và đang được
thúc đẩy nghiên cứu nhằm cải tiến hơn nữa các giao thức định tuyến để mạng đạt được

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
4.1.1. Các tham số hiệu suất cần đánh giá ............................................................................ 30
4.1.2. Cách thức phân tích kết quả mô phỏng của NS-2 ...................................................... 30
4.1.2.1. Cấu trúc tệp vết .................................................................................................... 30
4.1.2. Công cụ để phân tích và biểu diễn kết quả mô phỏng ................................................ 33
4.1.2.1. Perl ........................................................................................................................ 33
4.1.2.2.GNUPLOT ............................................................................................................ 33
4.2. Thiết lập mạng mô phỏng MANET .................................................................................. 35
4.2.1. Thiết lập tô-pô mạng ................................................................................................... 35
4.2.2. Thiết lập mô hình chuyển động của các nút mạng và thời gian mô phỏng ............... 36
4.2.2.1. Mô hình Random Waypoint ................................................................................. 37
4.2.2.2. Mô hình Random Walk ........................................................................................ 38
4.2.3 Thiết lập các nguồn sinh lưu lượng đưa vào mạng ..................................................... 39
4.2.4. Lựa chọn thời gian mô phỏng ..................................................................................... 40
4.3. Thực hiện mô phỏng các giao thức định tuyến .................................................................. 40

Hình 19: Đồ 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
Bảng 8: Thời gian thiết lập kết nối trung bình-Random_Waypoint.............................................43
Bảng 9: Thời gian thiết lập kết nối trung bình-Random_Walk....................................................43
Bảng 10: Tỷ lệ phân phát gói tin thành công - Random Waypoint..............................................44
Bảng 11: Tỷ lệ phân phát gói tin thành công – Random Walk.....................................................45
BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT
AODV Adhoc On-demand Distance
Vector
MANET Mobile Adhoc NETwork
CSMA/CA Carrier sense multiple access
with collision avoidance
MPR Multi-Point Relays
CSMA/CD Carrier Sense Multiple Access
with Collision Detection
NS-2 Network Simulator 2
DARPA Defense Advanced Research
Projects Agency
OLSR Optimized Link State
Routing Protocol
DSDV Destination-Sequenced
Distance Vector
PRnet Packet Radio Network

liệu. Những năm gần đây nền công nghiệp không dây và di động tăng trưởng mạnh mẽ
cả về mặt công nghệ lẫn sự bùng nổ ngày càng nhiều các thiết bị di động, hứa hẹn một
kỷ nguyên truyền thông số nở rộ trên nền các mạng không dây và di động. Sự phát triển
này được minh họa trên Hình 1 dưới đây.
Hình 1: Sự phát triển của mạng không dây và di động
Phạm Văn Tứ 1 K51MMT
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
Các mốc hình thành và phát triển của mạng không dây:
Phạm Văn Tứ 2 K51MMT
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
1915 1931 1982 , 1991
Guglielmo Marconi:
Lần đầu tiên trong lịch sử, 3
dấu chấm (tức chữ S trong
bảng ký tự Morse) đã được
truyền qua không gian với
khoảng cách 3km bằng sóng
điện từ.
Truyền thành công sóng
vô tuyến vượt Đại Tây
Dương từ Arlington
Virginia tới Pháp.

Bluetooth Special
Interest Group (SIG).
- 1999: Chuẩn 802.11b
được phát hành cho tốc
độ tối đa lên 11Mb/s.
-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ối
đa lên tới 54 Mb/s.
- Bluetooth 1.2 được
công bố.
*2004:
- Phiên bản mới của
chuẩn 802.16 được bổ
sung, hoàn thiện chuẩn
WIMAX.
- Phát hành chuẩn
Bluetooth 2.0

 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.
Phạm Văn Tứ 4 K51MMT
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
1.3. Công cụ nghiên cứu chính – NS-2
1.3.1. Giới thiệu về NS-2
NS-2 là phần mềm mô phỏng mạng, hoạt động của nó được điều khiển bởi các sự
kiện rời rạc. NS-2 được thiết kế và phát triển theo kiểu hướng đối tượng, được phát triển
tại đại học California, Berkely. Bộ phần mềm này được viết bằng ngôn ngữ C++ và
OTcl.
Hình 2: Cấu trúc của NS-2
Cấu trúc của NS-2 bao gồm các thành phần được chỉ ra trên Hình 2, chức năng của
chúng được mô tả như sau:
• OTcl Script Kịch bản OTcl
• Simulation Program Chương trình Mô phòng
• OTcl Bộ biên dịch Tcl mở rộng hướng đối tượng
• NS Simulation Library Thư viện Mô phỏng NS
• Event Scheduler Objects Các đối tượng Bộ lập lịch Sự kiện
• Network Component Objects Các đối tượng Thành phần Mạng
• Network Setup Helping Modules Các mô đun Trợ giúp Thiết lập Mạng
• Plumbling Modules Các mô đun Plumbling
• Simulation Results Các kết quả Mô phỏng
• Analysis Phân tích

Phạm Văn Tứ 6 K51MMT
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
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:
 Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại.
 Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng.
 Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi
được trong thực tế.
 Khả năng mô phỏng nhiều loại mạng khác nhau.
Trong đó NS-2 có khả năng mô phỏng:
 Các mô hình mạng: LAN, WLAN, di động, vệ tinh,...
 Các giao thức mạng như: TCP, UDP...
 Các dịch vụ nguồn lưu lượng như: FTP, CBR, VBR, Telnet, http...
 Các kỹ thuật quản lý hàng đợi: Vào trước Ra trước (Drop Tail), Loại bỏ sớm
ngẫu nhiễn - RED (Random Early Drop) và Xếp hàng dựa trên sự phân lớp –
CBQ (Class-Based Queueing)...
 Các thuật toán định tuyến như: Dijkstra, Distance Vector, Link State…
 Các Chuẩn IEEE 802.11, IEEE 802.3,…
 NS-2 cũng thực thi multicasting và vài giao thức lớp Điều khiển truy cập đường
truyền (MAC) đối với mô phỏng LAN.
Phạm Văn Tứ 7 K51MMT
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
1.4. Tổ chức của KLTN
Nội dung khóa luận bao gồm bốn chương như sau:
Chương 1: Giới thiệu về sự ra đời và phát triển của các mạng không dây, trình
bày tổng quát về bộ mô phỏng mạng NS-2 và nêu lên được mục tiêu nghiên cứu xuyên
suốt trong đề tài khóa luận tốt nghiệp này.

3. Dễ dàng triển khai lắp đặt:
Đối với nhiều khu vực việc triển khai mạng có dây khá là khó khăn, tốn nhiều
công sức do địa hình không thuận lợi hoặc không được phép lắp đặt vì làm mất mĩ quan.
Trái lại với mạng không dây ta chỉ cần thiết lập, lắp đặt các thiết bị trung tâm như
Access point, Switch, Router, sau đó không cần phải đi thêm các hệ thống dây cáp đến
từng máy cố định như trong mạng thông thường.
Phạm Văn Tứ 9 K51MMT
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
2.2. Chuẩn 802.3 và giao thức CSMA/CD
2.2.1. Chuẩn 802.3:
IEEE 802.3 là tập hợp các tiêu chuẩn do tổ chức IEEE định nghĩa về tầng vật lý
(Physical layer) và lớp con điều khiển truy cập môi trường truyền (MAC sublayer) của
lớp liên kết dữ liệu (Data link layer) trong mạng Ethernet. Theo chuẩn này, các kết nối
vật lý được thực hiện giữa các nút và (hoặc) các thiết bị cơ sở hạ tầng như: hub, switch,
router… bằng các loại cáp đồng hoặc cáp quang. Chuẩn 802.3 đồng thời cũng hỗ trợ
các kiến trúc mạng theo chuẩn 802.1.
Kích thước gói tin tối đa theo chuẩn là 1518 byte, mặc dù vậy để hỗ trợ mạng
LAN ảo và độ ưu tiên dữ liệu trong chuẩn 802.3ac, nó được mở rộng tới 1.522
byte. Nếu giao thức lớp trên đưa ra một khung dữ liệu (PDU) nhỏ hơn 64 byte, thì
chuẩn 802.3 sẽ đệm thêm các trường dữ liệu để đạt được tối thiểu 64 byte. Do đó kích
thước khung tối thiểu luôn luôn là 64 byte.
Với sự phát triển mạnh mẽ của công nghệ, tốc độ kết nối trong Ethernet không
ngừng được nâng lên. Dưới đây là một số mốc phát triển chính của chuẩn 802.3:
Bảng 1: Sự phát triển của chuẩn 802.3
Chuẩn Năm Sự kiện
802.3u 1995
Fast Ethernet ra đời với tốc độ 100 Mbit/s: 100BASE-
TX, 100BASE-T4, 100BASE-FX
802.3z 1998 1000BASE-X Gbit/s Ethernet qua cáp quang với tốc độ 1 Gbit/s

ứng dụng kỹ thuật điều biến đa luồng mới cho phép truyền dữ liệu ở tốc độ cao nhất lên
đến 150Mbps mỗi luồng. Chúng ta cùng nhìn lại sự phát triển, cải tiến của mạng không
dây chuẩn 802.11 theo bảng 2.
Bảng 2: Sự phát triển của chuẩn 802.11
802.11
Protocol
Năm
Tần số
(GHz)
Băng
thông
(MHz)
Tốc độ truyền dữ liệu trên
mỗi luồng (Mb/s)
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
n 10/2009 2.4/5

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.
Phạm Văn Tứ 14 K51MMT
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
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
thuận lợi cho việc dùng lại tài nguyên kênh truyền về cả không gian, thời gian và giảm
năng lượng phát cần thiết.
Sau đó có nhiều mạng vô tuyên gói tin phát triển nhưng các hệ thống không dây
này vẫn chưa bao giờ tới tay người dùng cho đến khi chuẩn 802.11 ra đời. IEEE đã đổi
tên mạng vô tuyến gói tin thành mạng Adhoc.
Ứng dụng:
Quân sự: Hoạt động phi tập trung của mạng Adhoc và không phụ thuộc vào cơ sở