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

điều kiện thuận lợi cho em trong thời gian thực hiện đồ án.
Cuối cùng, xin gửi lời cảm ơn đến tập thể lớp Công Nghệ Phần Mềm K53, các bạn
bè đã quan tâm, đóng góp ý kiến và giúp đỡ tôi trong quá trình học tập, nghiên cứu
và hoàn thành đồ án tốt nghiệp này.

Hà Nội, ngày 29 tháng 5 năm 2013

Bùi Văn Trường

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


MỤC LỤC

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


TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP
Mạng cảm biến không dây là một thế hệ mạng mới, với tiềm năng ứng dụng to lớn,
nó đang nhận được sự quan tâm rất nhiều từ cácchuyên gia. Một lớp bài toán đặt ra
là phát triển các giao thức định tuyến hiệu quả cho mạng này. Để đánh giá được
hiệu quả, cần có bộ thông số chuẩn, và công cụ phân tích giúp so sánh các giao thức
với nhau.
NS2 là nền tảng mô phỏng mạng phổ biến hiện nay. Nó có thể đáp ứng được hầu
hết các yêu cầu đặt ra với mạng cổ điển như: mạng có dây, mạng không dây thông
thường. Tuy nhiên, với các thế hệ mới như: mạng cảm biến không dây, mạng vệ
tinh, thì các giao thức tìm đường được nó hỗ trợ lại rất ít. Do đó, cần có một bộ thư
viện giải thuật tìm đường cho mạng cảm biến không dây để người dùng có nhiều
lựa chọn hơn khi mô phỏng.
Đồ án được thực hiện nhằm 2 mục tiêu chính sau:

-

-

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



ABSTRACT OF THESIS
Wireless Sensor Network is a research field which attracts the concern of many scientists
in over the world because of its important application in real life. There is a group of
problems in this area, focuses on the routing protocols, in which the researchers use
simulation platform to run and evaluate their proposed protocols. However, the
performance evaluation of a routing algorithm is quite complicated, because there is no
toolkit can accomplish most of its requirements.
NS2 is a popular simulation platform, is highly regarded in the research community
because of the ease, architecture closely and a large developer commumity. But with the
new generation networks such as WSN, the NS2 is restricted by the amount of the existing
routing protocols, making it difficult for users to compare the different algorithms.
The graduation thesis focuses on two parts as follows:
-

Develop a tool to evaluate the performance of routing protocols.
Implement routing algorithms for wireless sensor networks and integrate into NS2.

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


DANH MỤC HÌNH ẢNH

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


DANH MỤC BẢNG BIỂU

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


WiSSim Analyzer – công cụ phân tích trong bộ công cụ mô
phỏng WiSSim

GOAL

Geographic Routing with Constant Stretch in Large Scale
Sensor Networks with Holes – giao thức định tuyến địa lý với
độ dài đường đi cố định trong mạng cảm biến diện rộng.

EP

Extreme Point – Đỉnh của đa giác lồi bao phủ hố mạng.

Sensor

Cảm biến – Trong đồ án sử dụng thuật ngữ này có nghĩa là
cảm biến không dây.

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


PHẦN I: ĐẶT VẤN ĐỀ
CHƯƠNG 1: ĐẶT VẤN ĐỀ VÀ ĐỊNH HƯỚNG GIẢI PHÁP
1.1.

Mạng cảm biến không dây

Mạng cảm biến không dây là một thế hệ mạng mới, được tạo nên từ các cảm biến
không dây (wireless sensor). Các cảm biến có chức năng nhất định (ví dụ theo dõi

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

và ứng dụng. Nó giúp giảm chi phí, thiệt hại, hậu quả không đáng có trong quá trình
thử nghiệm hệ thống gây ra. Mặt khác, không phải nghiên cứu nào cũng có thể triển
Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


khai trên thực tế ngay được.Vì thế, đôi khi, mô phỏng đóng vai trò là con đường
duy nhất để đạt được kết quả nghiên cứu. Ví dụ như nghiên cứu sao hỏa, các nhà
khoa học cần mô phỏng môi trường để thiết bị hoạt động, từ đó có căn cứ để điều
chỉnh các thống số thiết bị sao cho phù hợp, chuẩn bị cho việc đưa chúng lên thăm
dò ở môi trường thật. Một ví dụ khác đó là xây nhà, ở những vùng ít xảy ra thiên tai
thì công việc này có vẻ đơn giản. Tuy nhiên, có thể thấy, tại Nhật Bản, nơi mà động
đất xảy ra thường xuyên, thì đây lại là một vấn đề nóng, dành được nhiều sự quan
tâm. Người ta cần xây dựng môi trường giả lập các tác động từ thiên nhiên, sử dụng
vật liệu, kiến trúc…rồi thử nghiệm, đánh giá mức độ an toàn, sau đó mới có thể thi
công công trình.
Tuy nhiên, quá trình này cũng có khá nhiều yêu cầu khắt khe, nhược điểm:
Phải thiết lập một môi trường giả lập sao cho gần nhất với môi trường
thật, để kết quả chính xác. Điều này tương đối khó, đòi hỏi chuyên gia
phải có kiến thức sâu sắc về môi trường thật và công cụ mô phỏng.
Không phải mọi thứ đều có thể mô phỏng được (ít nhất là ở một thời
điểm nào đó con người chưa có đủ thông tin về nó). Ví dụ như môi
trường tại một ngôi sao cách rất xa trái đất.
Một môi trường giả lập sai sẽ làm kết quả nghiên cứu sai. Việc kiểm thử,
xác nhận mô hình trong môi trường giả lập cũng đòi hỏi nỗ lực không
nhỏ.
Mặc dù có những nhược điểm như vậy nhưng giả lập vẫn là một công cụ được sử
dụng rộng rãi trong nghiên cứu khoa học.
-

1.2.2. Mô phỏng mạng


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

giao thức do nó hỗ trợ lại tỏ ra hạn chế.
1.3.

Tổng quan về bộ công cụ hỗ trợ mô phỏng WiSSim

Hình 1. Sơ đồ tổng quan về hệ WiSSim

Để đáp ứng yêu cầu về giả lập mạng không dây nói chung, mạng cảm biến không
dây nói riêng, nhóm nghiên cứu đã đề xuất xây dựng bộ công cụ chuyên dụng cho
mô phỏng định tuyến không dây, với các tính năng bậc cao, phát triển trên nền tảng
NS2, đó là bộ công cụ WiSSim.
Hệ WiSSim sẽ có bốn khối chính như sau:
-

Công cụ tạo kịch bản mô phỏng (WiSSim Editor): Hỗ trợ người sử dụng
(NSD) tạo và biên tập kịch bản mô phỏng thông qua một giao diện người
dùng (GUI) đơn giản, dễ hiểu.

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


-

-

-

Công cụ tái hiện quá trình hoạt động của mạng (WiSSim Visualizer): Từ
đầu ra là các file theo vết (trace files) sau khi thực hiện mô phỏng sử
dụng NS2, công cụ thể hiện lại quá trình hoạt động của mạng, giúp người

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ư:
-


Không biết căn cứ vào những thông số nào để đánh giá, vì hiện có rất
nhiều tiêu chuẩn, cách tính khác nhau cùng tồn tại. Mỗi tiêu chuẩn này
hướng đến một mục đích đánh giá khác nhau, gây khó khăn cho NSD.

-

Công việc phân tích bằng tay phức tạp. Kết quả của quá trình giả lập là
file theo vết. Nó cung cấp các số liệu rất đầy đủ về quá trình hoạt động
của mạng giả lập. Tuy nhiên không có số liệu nào để đánh giá hiệu năng
một cách trực tiếp. Thay vào đó, người dùng cần tự tổng hợp, tính toán.

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


Với những giả lập lớn (thời gian dài, nhiều nút mạng…) thì tính toán
bằng tay tương đối khó khăn.
-

Phân tích số liệu cần phải đưa ra một báo cáo tổng quan, dễ hiểu. Đó là
các biểu đồ 2D, 3D, hình ảnh. Để làm việc này, cần phải sử dụng nhiều
công cụ khác nhau như: excel, xgraph, Matlab… Mỗi công cụ đều có
điểm mạnh riêng. Nhưng với NSD mới, đối diện với một loạt các công
cụ mới, phối hợp sử dụng chúng cũng tạo ra khó khăn nhất định.

-

Các yêu cầu nâng cao như: theo dõi năng lượng tại một vùng mạng nào
đó, đo lường thông lượng từ vùng này đến vùng khác, hay xem tổng
quan về mạng khi phân tích dữ liệu… thì hiện tại chưa có một công cụ

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ỏ.

Công việc chỉnh sửa các thông số trong công cụ mô phỏng khi cài đặt
một giao thức phức tạp, gây khó khăn cho người mới sử dụng.

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


Do đó, cần có một bộ thư viện các giao thức định tuyến, hỗ trợ người dùng mô
phỏng một cách dễ dàng, tiết kiệm thời gian, công sức.
1.4.2. Lựa chọn giải pháp

Với các vấn đề nêu trên, để thực hiện dự án WiSSim, là một người mới tìm hiểu nền
tảng NS2 và mạng cảm biến không dây, tác giả xin đưa ra giải pháp giải quyết vấn
đề như sau:
-

-

Nắm chắc cơ chế hoạt động, kiến trúc cơ bản của ns2. Thành thạo ngôn
ngữ lập trình C++ và OTcl.
Hiểu về mạng cảm biến không dây, các thuộc tính đặc trưng của nó.
Hiểu cách cài đặt một giải thuật định tuyến. Biết cách tích hợp vào NS2.
Hiểu rõ các thông số đo lường hiệu năng mạng không dây. Phân tích
được các thông số này bằng tay, từ đó nêu lên cách làm tự động.
Hiểu rõ các công cụ trung gian liên quan đến nghiệp vụ phân tích (ví dụ:
công cụ vẽ biểu đồ).
Lựa chọn nền tảng Qt C++ để phát triển công cụ. Công cụ xây dựng trên
nền tảng này sẽ hoạt động tốt trên các hệ điều hành khác nhau, giao diện
đơn giản, dễ sử dụng.
Nắm chắc những thành phần lập trình có liên quan đến việc xây dựng
ứng dụng như: đồ họa, vẽ biểu đồ…


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.

Hiện nay, có rất nhiều nền tảng mô phỏng mạng khác nhau như: ns2, GloMoSim,
NetSim, OMNeT++. Mỗi công cụ này đều có điểm mạnh riêng, phù hợp với từng
yêu cầu nghiên cứu.Thông thường, các công cụ này chủ yếu dựa trên cơ chế mô
phỏng phụ thuộc thời gian (Time-Dependent Simulation), bao gồm:mô phỏng theo
thời gian (Time-Driven Simulation) và mô phỏng theo sự kiện (Event-Driven
Simulation). Ở 2 kiểu này, quá trình mô phỏng, các sự kiện diễn ra dựa theo thứ tự
thời gian. Đối với mô phỏng theo thời gian, đặc điểm trên là dễ hiểu, tuy nhiên với
mô phỏng theo sự kiện, đặc điểm trên thể hiện ở hai điểm mấu chốt sau đây:
−

−

Mỗi một sự kiện được đưa vào trong danh sách sự kiện phải được gắn
với một mốc thời gian bằng hoặc lớn hơn so với thời gian của sự kiện
hiện tại.
Sự kiện được mô phỏng tiếp theo được thực thi luôn là sự kiện có mốc
thời gian nhỏ nhất trong danh sách sự kiện. Mô phỏng không bao giờ
được nhảy vượt thứ tự thời gian tới các sự kiện xảy ra sau.

Trong các nền tảng mô phỏng thông dụng, nhóm đặc biệt chú ý tới NS2. Nền tảng
NS2 hỗ trợ cho cả Linux và Windows, có ý tưởng từ năm 1989 và được phát triển
bởi UC Berkeley vào năm 1995. NS2 là một nền tảng mô phỏng theo sự kiện
(Discrete-Event Simulation). Lợi thế của nền tảng này đó là đây là một nền tảng
mở, được viết chủ yếu bằng C++ cho mô phỏng nhẹ nhàng, nhanh chóng và kết quả
đáng tin cậy. Những lợi ích đầu tiên có thể kể đến của NS2 là:
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à ta khó có thể thử nghiệm
trong thực tế hoặc thử nghiệm thực tế bất cập về nhiều mặt (thời gian, chi
phí, nhân lực…)

− 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

trong NS2 phải viết kịch bản mô phỏng dưới dạng ngôn ngữ Tcl (Tool Command
Language). Đặc điểm của Tcl là một ngôn ngữ đơn giản, dễ học, dễ sử dụng. Kịch
bản mô phỏng là đầu vào của NS2. Những nội dung được trình bày trong một kịch
bản mô phỏng bao gồm:
−
−
−

Khai báo mô hình mạng (diện tích triển khai, số node, cấu hình mỗi
node, hạ tầng mạng, giao thức truyền tin, các tham số cần thiết)
Khai báo các sự kiện (bắt dầu, gửi tin, thời gian mô phỏng, kết
thúc…)
Cấu hình các kết quả đầu ra mong muốn

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


NS2 gọi lệnh thực thi quá trình mô phỏng bằng dòng lệnh:
ns script.tcl
Trong đó script.tcl là file kịch bản mô phỏng viết bằng Tcl. Đầu ra của quá trình mô
phỏng là các file kết quả lưu lại toàn bộ thông tin các sự kiện diễn ra trong quá trình
mô phỏng (trace files). Phụ thuộc vào mục đích của người sử dụng được đưa ra
trong kịch bản mô phỏng .tcl, phân tích các file kết quả này ta có thể quan sát được
việc hoạt động của mạng, lấy ra và tính toán được các thông tin cần thiết. Các thông
tin có thể là những dữ liệu được ghi lại ở từng thời điểm xảy ra các sự kiện trong
quá trình mô phỏng (khởi tạo gói tin, gửi tin, truyền tin, nhận tin, hủy tin,… hoặc là
những dữ liệu ghi lại trạng thái của mạng ở từng thời điểm nhất định (những node
nào đã chết, năng lượng còn lại ở mỗi node, tọa độ hiện tại…), hoặc cũng có thể là
bất kỳ dữ liệu gì mà người thực hiện mô phỏng muốn lấy ra. Các tệp kết quả được
xem là tốt nếu nó giúp người sử dụng thu thập được đầy đủ các thông tin mong

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

gian mô phỏng và quản lý toàn bộ thời gian mô phỏng. Các đối tượng
mô phỏng quan trọng bao gồm các events, handlers, Scheduler và
Simulator.
Các đối tượng mạng (Network Objects): có nhiệm vụ gửi, nhận, tạo và
hủy các đối tượng liên quan tới gói tin. Các đối tượng này đều được kế
thừa từ lớp NsObject.
Các đối tượng liên quan tới gói tin (Packet-related Objects): bao gồm
các loại gọi tín khác nhau được truyền trên mạng.
Các đối tượng hỗ trợ (Helper Objects): các đối tượng này không trực
tiếp tham gia vào vấn đề truyền tin. Tuy nhiên, chúng có vai trò hỗ trợ
để hoàn thành mô phỏng. Ví dụ, một module định tuyến tính toán
đường đi từ node nguồn tới node đích.

Cấu trúc phân cấp các lớp của ns2 là rất lớn với hơn 100 classes C++ và cấu trúc dữ
liệu struct. Các thành phần chính, cơ bản của ns2 có thể được mô tả bởi một phần
của cấu trúc phân cấp như ở Hình 4.

Hình 4. Cấu trúc phân cấp ns2
Như đã đề cập, NS2 là một nền tảng mô phỏng theo sự kiện. Cụ thể, mỗi một sự
kiện chứa thời gian thực thi, một tập các tác vụ, và một liên kết tới sự kiện khác.
Các sự kiện này kết nối với nhau tương tự như danh sách liên kết đơn và hình thành
một chuỗi sự kiện trên dòng thời gian của quá trình mô phỏng. Khi mô phỏng bắt
đầu, các sự kiện trong chuỗi được thực hiện tuần tự từ trái qua phải (theo thứ tự thời
gian). Hình 5 mô tả rõ quá trình này. Trong Hình 5, trong lúc thực thi sự kiện 1 (tại
Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53


thời gian time = 0.9) phát sinh sự kiện 5 cần được thực hiện lúc time = 3.7, khi đó
sự kiện 5 được chèn vào chuỗi sự kiện theo đúng thứ tự thời gian, tức ngay trước sự
kiện 3 (time = 5) mặc dù sự kiện 3 được lên lịch trước. Khi đó, sự kiện 5 sẽ được

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.

Các thông tin trong trace file mới như sau:

STT

Tên Trường

Ý nghĩa

1

Width

Độ rộng của vùng mô phỏng

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


2

Length

Chiều dài vùng mô phỏng

3

Time

Thời gian mô phỏng

Bảng 1.Thông tin tổng quan về mạng


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


5

Labels

Vùng chứa nút mạng

6

Energy

Năng lượng ban đầu.

Bảng 2.Thông tin các nút mạng

STT

Tên trường

Ý nghĩa

1

type

Loại header (IP, HTTP…)

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

STT


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


Ý nghĩa

1

ID

Id gói tin

2

Type

Kiểu gói tin (ví dụ: ack, tcp…)

3

Source -id

Id nút nguồn gửi tin

4

Source-port

Cổng tương ứng với ứng dụng gửi tin

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


5


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


Thông tin về các sự kiện trong giả lập. Có 7 loại sự kiện: Send, Forward, Receive,
Drop, Sleep, Wake, Move; được chia làm 4 nhóm như sau:
STT

Tên trường

Ý nghĩa

1

Time

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

2

Packet-id

Id gói tin gắn với sự kiện

3

Source-id

Id nút nguồn gửi tin

4

Source-port


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


STT

Tên trường

Ý nghĩa

1

Time

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

2

Packet-id

Id gói tin bị hủy

3

Node-id

Id nút hủy gói tin

4

Reason

Lý do hủy


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


Node-id

Nút phát ra sự kiện

3

Remain-energy

Năng lượng còn lại

Bảng 9. Thông tin nhóm sự kiện Sleep/Wake

STT

Tên trường

Ý nghĩa

1

Node-id

Nút phát ra sự kiện

2

Time

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


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



PHẦN II. CÁC KẾT QUẢ ĐẠT ĐƯỢC
Nội dung chính thực hiện được trong đồ án:
-

-

Tìm hiểu các thông số hiệu năng mạng không dây.
Xây dựng công cụ phân tích tự động hiệu năng mạng cảm biến không
dây. Công cụ này cho phép người dùng thao tác dễ dàng với những
thông số đánh giá hiệu năng mạng, với cả các thành phần về hình ảnh
(đồ thị, tổng quan về mạng), và thành phần bảng biểu.
Tìm hiểu, nghiên cứu giao thức định tuyến GOAL.
Cài đặt giao thức GOAL vào NS2.
Đánh giá hiệu năng giao thức dựa trên thuật toán và công cụ đã xây
dựng.

-

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


CHƯƠNG 3. XÂY DỰNG BỘ PHÂN TÍCH DỮ LIỆU HIỆU NĂNG
GIAO THỨC ĐỊNH TUYẾN (ANALYZER)
3.1.
Giới thiệu công cụ phân tích WiSSim Analyzer
3.1.1. Quá trình phân tích hiệu năng

Quá trình phân tích hiệu năng mạng được thực hiện như sau:
-


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

ứng, đưa ra thông lượng trung bình, độ lệch chuẩn, thông lượng lớn nhất,
nhỏ nhất. Và vẽ biểu đồ hiển thị kết quả trực quan. NSD cần dùng một
vài công cụ như: excel, matlab…để vẽ biểu đồ thể hiện.
Lọc những gói tin nằm trong thời gian phân tích.

Những khó khăn trên đã dẫn đến nhu cầu cần dùng công cụ phân tích tự động hỗ trợ
người dùng các thao tác này.
3.1.2. Giới thiệu chung về WiSSim Analyzer

Công cụ WiSSim Analyzer là một trong 4 thành phần của bộ công cụ mô phỏng
WiSSim do nhóm phát triển (Mục 1.3, chương 1). Công cụ này được tạo ra với mục
đích giúp người dùng phân tích hiệu năng giao thức định tuyến mạng không dây
một cách tự động. Những yêu cầu của mạng cảm biến rất khắt khe, do đó, các thông
Sinh viên thực hiện: Bùi Văn Trường – 20082818 – CNPM K53