TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
──────── * ───────

ĐỒ ÁN

TỐT NGHIỆP ĐẠI HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN

PHÁT TRIỂN CÔNG CỤ PHÂN TÍCH HIỆU
NĂNG GIAO THỨC ĐỊNH TUYẾN MẠNG
KHÔNG DÂY VÀ CÀI ĐẶT GIẢI THUẬT
TÌM ĐƯỜNG GOAL TRÊN NS2
Sinh viên thực hiện :
Giáo viên hướng dẫn:

HÀ NỘI 05 – 2013


LỜI CẢM ƠN
Trước tiên con xin cảm ơn bố mẹ và anh trai Bùi Thái Sơn đã vất vả chăm sóc,
động viên, tạo mọi điều kiện để con có thể hoàn thành đồ án tốt nghiệp này.
Em xin gửi lời cảm ơn chân thành đến các thầy cô giáo Viện Công Nghệ Thông Tin
và Truyền Thông đã tận tình giảng dạy chỉ bảo em trong quá trình học tập. Những
kinh nghiệm các thầy cô truyền thụ là hành trang tốt cho em có thể vững bước trên
con đường tương lai.
Em xin cảm ơn sâu sắc đến TS. Nguyễn Khanh Văn, ThS. Nguyễn Phi Lê đã giúp
đỡ em rất nhiều trong quá trình hoàn thành đồ án tốt nghiệp. Phương pháp nghiên
cứu, suy nghĩ, giải quyết vấn đề của thầy cô là những kinh nghiệm quý báu mà em
sẽ luôn ghi nhớ, và duy trì thực hiện.
Cảm ơn các anh, các bạn trong phòng bảo mật, Công ty An Ninh Mạng Bkav đã tạo

-

-

Tìm hiểu các thông số đo lường hiệu năng giao thức định tuyến, xây dựng
một công cụ đo lường tự động với độ chính xác cao, giao diện dễ sử dụng,
cung cấp đầy đủ các chức năng phân tích như: tính toán, vẽ biểu đồ, xuất dữ
liệu nhiều khuôn dạng... và hoạt động tốt trên nhiều hệ điều hành.
Tìm hiểu, cài đặt giao thức định tuyến GOAL (Geographic Routing with
Constant Stretch in Large Scale Sensor Networks with Holes) trên nền tảng
NS2. Dựa trên cộng cụ xây dựng được, đánh giá hiệu năng của giao thức.

Cụ thể hơn, đồ án được chia làm 3 phần như sau:
Phần 1: Gồm hai chương. Phần này nêu những vấn đề đặt ra với mạng cảm biến
không dây, và định hướng giải quyết của tác giả.
Chương 1: Khái quát chung về mạng cảm biến không dây, quá trình giả lập mạng,
các vấn đề đặt ra và hướng giải quyết.
Chương 2: Sơ lược về NS2, thông tin tập tin theo vết định dạng mới.
Phần 2: Nội dung chính của đồ án. Phần này nêu lên những kết quả đạt được trong
quá trình thực hiện đồ án, được trình bày trong ba chương 3, 4, 5.
Chương 3:Xây dựng công cụ phân tích dữ liệu hiệu năng mạng Analyzer dựa trên
các thông số hiệu năng tiêu chuẩn do tổ chức The Internet Society đưa ra.
Chương 4: Cài đặt giao thức định tuyến GOAL trên nền tảng mô phỏng NS2. Đánh
giá chung về thuật toán.
Chương 5: Thử nghiệm, phân tích hiệu năng giao thức định tuyến GOAL bằng công
cụ Analyzer.
Phần 3: Nêu lên những vấn đề giải quyết được, còn tồn tại và hướng đi trong tương
lai của đồ án.
Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53



DANH MỤC TỪ VIẾT TẮT
Viết tắt

Ý nghĩa

Ns2

Network Simulator 2, bộ công cụ mô phỏng mạng

OTcl

Object-oriented Tcl, ngôn ngữ hướng đối tượng của ngôn
ngữ kịch bản Tcl

WiSSim

Wireless Sensor Simulator, bộ công cụ hỗ trợ giả lập mạng
cảm biến không dây

Trace file

Tập tin theo vết quá trình giả lập(thường nhắc đến trong
NS2)

NSD

Người sử dụng

WA

nhiệt độ tại lò phản ứng, mức nước, hay các nhiệm vụ phức tạp như phát hiện xâm
nhập…), và cần phải chuyển thông tin thu nhận được cho nhau, hoặc đến nơi điều
khiển.
Ứng dụng của mạng cảm biến không dây ngày một quan trọng, phong phú. Chúng
được sử dụng trong nhiều lĩnh vực, trong đó có an ninh quốc phòng (theo dõi địch,
phát hiện xâm nhập…), cảnh báo thiên tai (theo dõi mực nước tại các sông, suối,
nơi hay xảy ra lũ lụt, tốc độ gió của bão…), giải tỏa ùn tắc giao thông (gắn sensor
trên các phương tiện giao thông để theo dõi lưu lượng, phát hiện nơi tắc đường...)...
Có nhiều ứng dụng quan trọng như vậy, tuy nhiên, các sensor lại có khá nhiều
nhược điểm như: phạm vi kết nối hạn chế (bán kính nhỏ),giới hạn về năng lượng,
chất lượng cảm biến (do ở những vị trí khó khăn, sau khi triển khai cảm biến, khó
có thể thay thế được), topo mạng thường xuyên thay đổi (do các cảm biến có thể di
chuyển được). Trong quá trình hoạt động, nếu giải thuật tìm đường không tốt, có
thể dẫn đến ở một vài vị trí của mạng, nút mạng tại đó hoạt động quá tải, dẫn đến
hết năng lượng, dần dần có thể tạo nên một vùng không có sóng; trong khi một số vị
trí khác, cảm biến lại không được sử dụng.
Vì thế, cần phải có một giao thức định tuyến hiệu quả để khắc phục những sự cố
trên, duy trì độ ổn định của mạng.
Với những yêu cầu trên, có 2 vấn đề cần giải quyết, đó là:
-

Đánh giá hiệu năng giải thuật tìm đường trên mạng.
Xây dựng, cài đặt một số giải thuật tìm đường trong mạng cảm biến
không dây.

1.2.
Mô phỏng, giả lập mạng
1.2.1. Tầm quan trọng của quá trình mô phỏng

Mô phỏng là quá trình rất quan trọng trong hầu hết các ngành khoa học, nghiên cứu


Môi trường mạng ngày càng phức tạp. Và khái niệm mạng không còn chỉ tồn tại
trong lĩnh vực máy tính, mà nó đã lan rộng ra nhiều lĩnh vực khác, như mạng cảm
biến không dây, mạng vệ tinh… Kèm theo đó, phát triển những thuật toán tìm
đường hiệu quả đang là vấn đề cấp thiết với thế hệ mạng mới này. Để cài đặt một
thuật toán trên mạng thật đòi hỏi một chi phí không nhỏ, không phải ở đâu cũng có
điều kiện để thực hiện, hơn nữa, đó là một sự lãng phí.
Vì thế, các nhà khoa học, các công ty chuyên về lĩnh vực này đã xây dựng nên các
công cụ mô phỏng mạng rất hiệu quả. Có thể kể đến như: NS2, OpNET, OMNET+
+… Trong đó, NS2 (Network Simulator 2) là một công cụ rất phổ biến, được phát
triển bởi trường đại học UC Berkely, từ những năm 1990. Với thế mạnh là mã
nguồn mở, dễ sử dụng, và có cộng đồng phát triển đông đảo, nó dần trở thành một
công cụ phổ biến nhất trong nghiên cứu, mô phỏng mạng. NS2 được viết trên nền
tảng là ngôn ngữ C++ và OTcl (Object-oriented Tcl), 2 ngôn ngữ cơ bản và dễ sử
dụng. C++ dùng để thực thi phần kiến trúc bên trong (như các nút mạng, liên kết,
giải thuật tìm đường…), OTcl đóng vai trò là một thành phần cấu hình mạng, nút
Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


mạng, giả lập (định dạng thông tin vào ra hệ thống…). Với những kiến thức cơ bản
về mạng, lập trình C++, OTcl, người sử dụng có thể dễ dàng thao tác với cả phần
lõi (qua mã nguồn) và phần kịch bản mô phỏng để tạo nên môi trường mô phỏng
của mình. Ngoài ra, một ưu điểm nữa đó là tài liệu sử dụng của công cụ này rất đầy
đủ (tài liệu từ nhà phát triển và từ bên thứ 3).
NS2 cung cấp rất nhiều các giao thức truyền thông ở nhiều tầng khác nhau như:
tầng ứng dụng (HTTP, FTP…), tầng giao vận (TCP, UDP), tầng mạng (các giao
thức định tuyến AODV, DSR, DSDV…), tầng MAC (Ethernet, chuẩn 802.11…).
Với các mạng có dây và một số mạng không dây truyền thống, NS2 hỗ trợ khá tốt,
do đã có những bộ giao thức chuẩn, tuy nhiên với mạng cảm biến không– một thế
hệ mạng tương đối mới, có nhiều ứng dụng trong các lĩnh vực quan trọng – thì các

sử dụng quan sát, hình dung một cách trực quan toàn bộ quá trình mô
phỏng xảy ra. Công cụ này hữu ích khi nhà nghiên cứu muốn kiểm tra
các hoạt động trong mạng có diễn ra như mình mong muốn, giải thuật
chạy có đúng như lý thuyết hay không.
Công cụ phân tích kết quả mô phỏng (WiSSim Analyzer): Công cụ phân
tích trace files để lấy ra các số liệu cần thiết cho việc thống kê, đánh giá,
giúp người sử dụng đánh giá được hiệu quả của giao thức định tuyến
được mô phỏng.Đối với nghiên cứu, việc đánh giá, phân tích đóng vai trò
quan trọng. Công cụ này sẽ đáp ứng hầu hết những yêu cầu của người
dùng về pha phân tích, cung cấp số liệu chính xác, biểu đồ trực quan, và
trích xuất kết quả dễ dàng.
Thư viện các giải thuật định tuyến cho mạng cảm biến không dây
(WiSSim Routing Protocol Library): Vung cấp cho người dùng các giao
thức định tuyến phổ biến trong mạng. Các giao thức được cài đặt sẽ giúp
người sử dụng thực hiện mô phỏng mạng với nhiều giao thức, qua đó có
các so sánh khách quan giữa các thuật toán với nhau.

Trong đó, hai modules WiSSim Analyzer và WiSSim Routing Protocol Library là
các thành phần sẽ được tác giả thực hiện trong đồ án.
1.4.
Giới thiệu đề tài
1.4.1. Vấn đề đặt ra

Phân tích hiệu năng giao thức định tuyến trong mạng cảm biến không dây là quá
trình trích xuất, tổng hợp các thông số khác nhau, để đưa ra những kết luận về hiệu
năng, ví dụ như thời gian ngủ, biến thiên năng lượng của nút mạng, tốc độ truyền
tin... Việc phân tích có thể dựa trên số liệu kết quả của pha mô phỏng.
Sau quá trình mô phỏng, để phân tích hiệu năng của mạng, người dùng gặp phải
những vấn đề như:
-

nào cung cấp những chức năng này.

Với các yêu cầu nêu trên, đòi hỏi cần xây dựng một công cụ hỗ trợ người dùng phân
tích dữ liệu, thay thế công việc thủ công phức tạp này. Công cụ cần đơn giản hóa
quá trình phân tích dữ liệu mô phỏng mạng, thực hiện một cách tự động, dễ dàng
kiểm tra tính chính xác của kết quả, dễ sử dụng, dễ hiểu, thực hiện được hầu hết các
công việc trong pha phân tích. Nó cần hoạt động được trên nhiều hệ điều hành khác
nhau, đặc biệt là Linux, vì NS2 hoạt động tốt nhất trên nền tảng này.
Công cụ này cũng cần đảm bảo các tính chất sau:
- Tính chính xác: đây là điều tối quan trọng, vì mục tiêu hướng đến của
nó là dành cho việc tính toán số liệu trong nghiên cứu khoa học. Cần
phát hiện ra những trường hợp tính toán dữ liêu có lỗi, sai lệch. Các
thông số sai lệch này cần đo đếm được, và thông báo đến người dùng.
- Tính kế thừa: Công cụ cần phát triển sao cho có thể dễ dàng mở rộng,
cung cấp cho người dùng một giao diện lập trình, tương tác ngày một
hoàn thiện hơn.
- Khả năng tích hợp: Dễ dàng tích hợp với các công cụ khác trong bộ
công cụ mô phỏng WiSSim.
Một bài toán nữa đó là xây dựng, cài đặt giao thức định tuyến trên công cụ mô
phỏng. Người dùng cần hiểu rõ cơ chế hoạt động của giao thức, cách cài đặt, tích
hợp, sử dụng giao thức trong môi trường giả lập. Điều này gây ra những vấn đề
như:
-

-

Khi xây dựng một giao thức mới, muốn so sánh hiệu quả của nó với
giao thức nào đó. Họ muốn có ngay giao thức đó để đánh giá, chứ
không muốn phải tự mình cài đặt. Vì công việc này tiêu tốn thời gian
không nhỏ.


1.4.3. Tóm tắt kết quả đã thực hiện được

Trong quá trình là việc, tác giả đã đạt được những kết quả sau:
-

-

Tìm hiểu và cài đặt giải thuật tìm đường mạng cảm biến không dây
GOAL[3], tích hợp vào module thư viện giao thức định tuyến WiSSim
như đã nói trên.
Tìm hiểu, phân tích các thông số đánh giá hiệu năng mạng không dây.
Xây dựng thành công công cụ phân tích dữ liệuWiSSim Analyzer hỗ trợ
người dùng.
Thử nghiệm đánh giá hiệu năng giao thức trên công cụ đã xây dựng.

Chi tiết sẽ được làm rõ trong chương 3, 4, 5 của đồ án.

Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
2.1.
NS2[12]
2.1.1. Giới thiệu chung

Công cụ giả lập, mô phỏng ra đời giúp ích rất nhiều cho các nhà nghiên cứu, các
công ty phát triển sản phẩm của mình. Quá trình giả lập giúp họ tiết kiệm chi phí,
thời gian, công sức so với việc thử nghiệm trên thực tế. Trong khuôn khổ đồ án này,
tác giả sẽ tập trung vào các công cụ mô phỏng mạng.

− Khả năng mô phỏng nhiều loại mạng khác nhau.
−
−
−

NS2 hỗ trợ rất tốt để mô phỏng hầu hết các mạng có dây (WAN, LAN…) và một số
mạng không dây. NS2 cung cấp thư viện các giao thức rất phong phú ở tất cả các
Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


lớp mạng. Từ các giao thức điều khiển truy cập (MAC), các giao thức định tuyến
mạng có dây như Dijkstra; các giao thức định tuyến mạng Ad hoc, Manet như
AODV, DSR; các giao thức chuyển vận như UDP, TCP; các giao thức ứng dụng
tầng cao như FTP, TelNet, http, CBR, VBR; các kỹ thuật hàng đợi như DropTail,
RED.
Bên cạnh đó, nền tảng này được cộng đồng hỗ trợ và phát triển rất tốt, người sử
dụng theo đó sẽ dàng tìm hiểu, học hỏi khi gắp vướng mắc trong quá trình sử dụng.
Có nhiều tài liệu chi tiết có thể xem như hướng dẫn sử dụng mà người dùng có thể
dùng để sẵn sàng tra cứu khi cần thiết. Một số diễn đàn về ns2 hoạt động rất sôi nổi,
các câu hỏi thắc mắc được giải đáp nhanh chóng và thấu đáo.
Hình 2 là đồ thị dạng bánh thống kê mức độ phổ biến của các nền tảng mô phỏng
mạng được sử dụng trong các bài báo của ACM từ năm 2000 tới năm 2004. Theo
đó, nền tảng ns2 (ns2 – viết tắt của network simulation version 2) chiếm 45%, là
một trong những nền tảng mô phỏng thông dụng nhất hiện nay.

Hình 2. Các công cụ mô phỏng mạng được sử dụng trong các bài báo của ACM
(2000 – 2004)
2.1.2. Kiến trúc NS2

Kiến trúc cơ bản của NS2 được mô tả ở hình 3. Người sử dụng muốn mô phỏng

muốn.

Hình 3. Kiến trúc cơ bản của ns2

NS2 sử dụng hai ngôn ngữ lập trình: ngôn ngữ kịch bản (Otcl – Object-oriented
Tool Command Language) và ngôn ngữ lập trình hệ thống (C++). Lý do NS2 cần
sử dụng đến hai ngôn ngữ là vì mục đích tối ưu hoạt động cho bộ mô phỏng. Một
mặt, các cài đặt chi tiết cho các giao thức, các đối tượng trong bộ mô phỏng yêu cầu
một ngôn ngữ lập trình hệ thống để có thể tính toán hiệu quả các byte, các tiêu đề
packet và các thuật toán thực thi đang chạy trên một tập dữ liệu lớn. Với chức năng
này, tốc độ thời gian chạy thực (run-time speed) là quan trọng trong khi thời gian
xoay vòng (turn-around time) thì ít quan trọng hơn (thời gian xoay vòng bao gồm
thời gian chạy mô phỏng, thời gian tìm lỗi, sửa lỗi thời gian biên dịch và thời gian
chạy lại). Mặt khác, khi người sử dụng thực hiện việc mô phỏng mạng, họ thường
rất quan tâm tới việc thay đổi các tham số trong giao thức hoặc các thay đổi nhỏ về
mặt cấu hình, đồng thời cần kết quả nhanh chóng của nhiều trường hợp mô phỏng
khác nhau. Trong tác vụ này thì thời gian lặp (iteration time) lại quan trọng hơn.
Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


Các thành phần trong NS2 có thể được phân thành 4 loại cơ bản dựa vào chức năng
cơ bản của chúng:
−

−

−
−

Các đối tượng mô phỏng (Simulation-related Objects): kiểm soát thời

thực thi trước sự kiện 3. Bởi vậy cơ chế này có tính rời rạc: các sự kiện được sắp
xếp không liên quan đến nhau mà chỉ được dựa vào thời gian gắn với sự kiện đó.

Hình 5. Ví dụ về chuỗi sự kiện trong mô phỏng theo sự kiện

2.2.

Thông tin file theo vết (trace file) của hệ thống

Như đã trình bày trong phần 2.1, đầu ra quá trình giả lập trên NS2 là tập tin theo
vết. Tuy nhiên, trace file ban đầu của NS2 gây ra những vấn đề sau:
-

-

Cung cấp nhiều thông tin, nhưng ở định dạng mà con người không hiểu
được.Vì thế gây khó khăn cho công việc kiểm tra tính chính xác của số
liệu.
Việc kiểm tra số liệu của quá trình phân tích, vì người kiểm tra phải rất
khó khăn để làm việc với nó.
Không có đầy đủ các thông số cần thiết cho quá trình phân tích (ví dụ
như Labels (vùng nút mạng), queue length (độ dài hàng đợi gói tin),
range (mức phủ sóng của nút mạng)…).

Vì vậy, nhóm nghiên cứu đã quyết định phát triển một phiên bản trace file mới, dựa
trên cấu trúc XML, trực quan, dễ hiểu, có thể thêm vào những thông tin cần thiết
cho các quá trình phân tích, thể hiện trực quan… Và để thực hiện điều này, nhóm
cần chỉnh sửa mã nguồn của NS2.
Với định dạng mới này, NSD dễ dàng kiểm tra thông tin phân tích và thông tin sẵn
có trong quá trình giả lập.


STT

Tên trường

Ý nghĩa

1

ID

Id của nút mạng

2

X

Tọa độ x

3

Y

Tọa độ y

4

Range

Vùng phủ sóng của nút mạng


Tên trường

Ý nghĩa

1

Name

Tên trường trong header (flowid…)

Bảng 4. Thông tin về các trường trong một header

STT

Tên trường

Ý nghĩa

1

Size

Kích thước của dữ liệu gói tin

Bảng 5. Thông tin về dữ liệu của gói tin
STT

Tên trường



Dest-id

Id nút đích nhận tin

6

Dest-port

Cổng của ứng dụng nhận tin

7

Size

Kích thước gói tin

8

Headers

Các thành phần header gói tin

9

payload

Thông tin về dữ liệu gói tin (xem bảng 5)

Bảng 6. Thông tin về gói tin


Cổng nút nguồn sử dụng để gửi tin

5

Dest-id

Id nút đích của gói tin

6

Dest-port

Cổng nút đích sử dụng để nhận tin

7

Remain-energy

Năng lượng còn lại của nút phát ra sự
kiện

8

Buffer-length

Độ dài hàng đợi gói tin khi xảy ra sự kiện

Bảng 7. Thông tin nhóm sự kiện Send/Forward/Receive


5

Remain-energy

Năng lượng còn lại tại nút xử lý

6

Buffer-length

Độ dài hàng đợi gói tin của nút

Bảng 8. Thông tin nhóm sự kiện Drop

STT

Tên trường

Ý nghĩa

Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


1

Time

Thời gian diễn ra sự kiện

2


3

Cur x, y, z

Tọa độ đầu

4

Dest x, y, z

Tọa độ cuối

5

Speed

Tốc độ di chuyển

Bảng 10. Thông tin nhóm sự kiện Move

Ví dụ về định dạng file trace mới:

Hình 6. Trace file

Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53



Tìm các thành phần đánh giá hiệu năng mạng.
Thu thập số liệu trong quá trình thử nghiệm hoặc giả lập mạng.
Tìm cách tính toán hiệu năng từ số liệu thu được.

-

Tính toán, vẽ đồ thị kết quả và đưa ra kết luận.

Pha phân tích có thể thực hiện bằng tay ở mọi công đoạn. Tuy nhiên, thực hiện thủ
công đôi khi gặp nhiều khó khăn. Vì lượng thông tin do mạng tạo ra rất lớn, rời rạc.
Ngoài ra, để phân tích những yêu cầu nâng cao như phân tích thông lượng giữa 2
vùng mạng, với tập kết quả của quá trình thử nghiệm – giả lập, NSD cần:
-

-

-

Tìm tất cả những nút thuộc vùng gửi (nhận) tin. Vùng có thể là vùng địa
lý, vùng một số nút mạng được theo dõi (vùng bất kỳ).
Ghi lại toàn bộ các gói tin trong quá trình gửi – nhận giữa những nút
mạng thuộc 2 vùng này. Các thông tin quan trọng như: id gói tin, thời
gian hoàn thành gửi tin, kích thước gói tin. Độ phức tạp của công việc
này khá lớn nếu làm thủ công. NSD cần duyệt qua tất cả các gói tin, để
xác định những gói do vùng phát gửi đi, theo dõi id gói tin trong các sự
kiện, kiểm tra xem gói tin có đến được đích không (có thể do tắc nghẽn
mạng, không tìm được đường đi…mà gói tin bị tắc ở đâu đó), và thời
gian vùng nhận nhận được.
Tập hợp thông tin của các quá trình trên, tính toán thông lượng tương