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

ENGINE THỂ HIỆN TRỰC QUAN ĐỒ HỌA
CHO HỆ MÔ PHỎNG WISSIM TRONG
MẠNG CẢM BIẾN KHÔNG DÂY
Giáo viên hướng dẫn: TS.Nguyễn Khanh Văn
TS.Nguyễn Thanh Hùng
Sinh viên thực hiện: Phạm Văn Khắc
Lớp CNPM–K53

HÀ NỘI 06 – 2013


Đồ án tốt nghiệp

PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
1. Thông tin về sinh viên
Họ và tên sinh viên:
Phạm Văn Khắc
Điện thoại liên lạc:
01689967593
Email:
Lớp: CNPM K53
Hệ đào tạo: Chính quy


2

Lớp CNPM-K53


Đồ án tốt nghiệp
TS. Nguyễn Khanh Văn

3

Phạm Văn Khắc - 20081397

3

Lớp CNPM-K53


Đồ án tốt nghiệp

TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP
Từ lý thuyết tới thực tế là cả một quãng đường dài. Để ra được một sản phẩm
ứng dụng được, ổn định và hoạt động tốt đòi hỏi nhiều công sức của những người thực
hiện. Đồng thời không có nhiều ý tưởng thành công. Trong hàng loạt nguyên nhân dẫn
tới sự thất bại của các ý tưởng đó, một phần rất lớn là do việc chưa khảo sát và thử
nghiệm tốt. Hoặc những thử nghiệm chưa sát với thực tế.Riêng đối với lĩnh vực định
tuyến mạng, việc thử nghiệm trước khi cài đặt lại càng rất quan trọng. Chỉ một sai sót
nhỏ thôi cũng gây ra thiệt hại rất lớn. Bởi lẽ, khi ứng dụng một mô hình định tuyến
mạng yêu cầu phần cứng sản xuất hàng loạt, nguồn nhân lực để cài đặt và thời gian để
đi vào hoạt động ổn định là rất lâu. Để khắc phục vấn đề trên, có nhiều công cụ cho

attention by many researchers. Because not only is it largely applied but it also is
unexplored so much. At the present, WSN has been implemented popularly. We, who are
working on the filed of studying, would like to own a tool allowing to simulate the WSN
to serve our job. However, now we haven’t seen anything meet our needs the best, hence
we decided to create a toolkit to satisfy us. First of all, these tools should serve us and
then, the researchers on WSN all could use them. Since then, our tool will give the
benefit for the researching community in this field. We are trying our best to achieve the
most effective products and looking forward to their consideration and feedback to make
us work better.

5

Phạm Văn Khắc - 20081397

5

Lớp CNPM-K53


Đồ án tốt nghiệp

LỜI CẢM ƠN
Trước tiên tôi xin gửi lời cảm ơn tới các thầy cô trong trường Đại học Bách khoa
Hà Nội cùng với Viện Công nghệ thông tin và Truyền thông đã giảng dạy để tôi có được
những kiến thức, kinh nghiệm từ lý thuyết tới thực tiễn trong quá trình học tập và rèn
luyện.
Đặc biệt, tôi muốn gửi lời cảm ơn chân thành tới TS. Nguyễn Khanh Văn và TS.
Nguyễn Thanh Hùng đã tận tình chỉ bảo và giúp đỡ tôi trong quá trình học tập, nghiên
cứu cũng như trong thời gian làm đồ án tốt nghiệp. Những ngày được làm việc cùng với
các thầy thực sự tôi đã học được rất nhiều, từ kiến thức tới cách làm việc và cách sống.

DANH SÁCH CÁC HÌNH

7

Phạm Văn Khắc - 20081397

7

Lớp CNPM-K53


Đồ án tốt nghiệp

DANH SÁCH CÁC BẢNG

8

Phạm Văn Khắc - 20081397

8

Lớp CNPM-K53


Đồ án tốt nghiệp

DANH SÁCH TỪ VIẾT TẮT VÀ THUẬT NGỮ
Từ viết tắt

Nghĩa tiếng Việt

Gói tin được truyền trong mạng

Sensor

Thiết bị cảm biến

Simulation

Quá trình mô phỏng

Source

Nguồn

TCL

Tool Command Language

Tkev

Thành phần thể hiện trực quan trong OMNet++

TraceFile
WiSSim
Visualizor
WSN

Tệp tin đầu ra của quá trình mô phỏng

Xgraph

hết các giao thức phổ biến, tuy nhiên một số vấn đề còn bất cập như:
-

Việc cài đặt một giải thuật mới khá là phức tạp và đòi hỏi một lượng lớn thời gian
vào việc tìm hiểu công cụ để sử dụng.
Quá trình thể hiện kết quả để đánh giá chưa thực sự là tốt. Chưa có một công cụ nào
có thể đáp ứng được hầu hết các nhu cầu cho việc đánh giá, phân tích những kết quả
mà thuật toán của họ mạng lại.

Chúng tôi đã nhận ra những bất cập đó và muốn góp phần rút ngắn quãng đường đi
từ lý thuyết tới đời thường. Chúng tôi đã quyết định xây dựng một công cụ cho phép
biểu diễn lại quá trình mô phỏng mạng với đầu vào là thuật toán của người dùng, đầu ra
là những đối tượng dưới dạng đồ họa, thể hiện một cách trực quan nhất sự hoạt động của
mạng. Từ đó, người dùng có thể đánh giá được kết quả của họ một cách nhanh nhất.
Bộ công cụ của chúng tôi xây dựng trên nền tảng NS2 bởi nền tảng vững chắc, bộ
giải thuật đầy đủ hơn cả so với các công cụ khác. Là một phần trong dự án lớn mà chúng
tôi sẽ xây dựng, đồ án này tập trung nghiên cứu về “Engine thể hiện trực quan đồ họa
cho hệ mô phỏng WiSSim trong mạng cảm biến không dây”. Trong phạm vi đồ án,
tôi sẽ trình bày về phần Engine của công cụ cho phép thể hiện trực quan kết quả đầu ra
trong quá trình mô phỏng thuật toán của người dùng.
Nội dung đồ án mà tôi thực hiện bao gồm những nội dung chính sau:
-

Tìm hiểu bộ công cụ nền tảng mô phỏng mạng NS2, cơ chế hoạt động cũng như
thành phần của nó. Từ đó đưa ra được hình mẫu cho hệ thống mà chúng tôi sẽ cài đặt
cho ứng dụng của mình.

10

Phạm Văn Khắc - 20081397

Bao gồm 2 chương:
a. Chương thứ nhất: Thiết kế hệ thống tổng quan. Kiến trúc WiSSim Visualizer hoạt

động như thế nào? Những thành phần mà chúng tôi đã xây dựng. Cơ chế liên kết giữa
các thành phần đó ra sao? Chúng tôi sẽ đưa tất cả những câu trả lời cho người đọc
trong phần này.
b. Chương thứ hai: Kiến trúc chi tiết và cài đặt. chương này bao gồm các sơ đồ thiết kế
chi tiết mà chúng tôi đã xây dựng. Người đọc có thể hiểu được sự hoạt động nhìn từ
góc độ của người dùng thông qua các lược đồ ca sử dụng. Chi tiết liên kết, cấu trúc
phân cấp của các lớp sẽ được biểu diễn qua sơ đồ lớp. Biểu đồ tuần tự sẽ cho người
dùng thấy được quá trình hoạt động của công cụ như thế nào. Từ đó những người
quan tâm có thể kế thừa, mở rộng các tính năng mà chúng tôi đã xây dựng. Từ đó
công cụ ngày càng hoàn thiện và mở rộng đáp ứng nhu cầu của người dùng.

11

Phạm Văn Khắc - 20081397

11

Lớp CNPM-K53


Đồ án tốt nghiệp

PHẦN I. ĐẶT VẤN ĐỀ VÀ ĐỊNH HƯỚNG GIẢI PHÁP.
Chương I. Mô phỏng mạng và định tuyến không dây.
1. Mô phỏng mạng là gì?

Để hiểu rõ hơn khái niệm này, trước hết ta tìm hiểu sơ qua về mạng. Mạng ở đây


12

Lớp CNPM-K53


Đồ án tốt nghiệp
+ Tiết kiệm thời gian, nhân lực. Khi ta muốn thay đổi trạng thái, thông tin của các
thiết bị, ta không cần phải làm với từng thiết bị, không phải tốn nhiều nhân lực thực
hiện. Khi mô phỏng, ta chỉ cần thay đổi một vài thông số là đã có thể đạt yêu cầu đề ra.
+ Đánh giá kết quả một cách rõ ràng. Chẳng hạn, khi bạn có một giao thức mới.
Bạn muốn biết giao thức đó so với các giao thức đã có sẵn như thế nào? Khi đó bạn phải
nhờ tới công cụ mô phỏng mạng. Công cụ cho bạn thấy được với cùng điều kiện như
nhau, mạng mới hoạt động tốt hơn so với mạng cũ nhiều hay ít. Việc triển khai có tính
khả thi hay không?
+ Một lợi ích quan trọng không kém là đối với trường hợp khảo sát số lượng lớn.
Bạn không thể nào thử nghiệm từ hàng ngàn tới chục ngàn thiết bị được. Rất khó khảo
sát và thu thập thông tin. Khi đó bạn phải nhờ tới công cụ mô phỏng mạng. Số lượng bạn
có thể khảo sát là rất lớn. Thậm chí lên tới hàng triệu thiết bị bạn vẫn có thể khảo sát
được.
Hiện nay có rất nhiều công cụ cho phép thực hiện việc mô phỏng mạng. Chẳng hạn
như NS2, GloMoSim, NetSim, OMNeT++… Một công cụ mô phỏng mạng tốt là một
công cụ có khả năng thể hiện các tính chất của mạng giống với thực tế nhất. Từ đó,
những người nghiên cứu có thể đánh giá chính xác, thuận tiện. Mỗi công cụ đều tập
trung tới những mảng cụ thể và có những ưu nhược điểm riêng. Tại thời điểm chúng tôi
thực hiện dự án, 2 công cụ phổ biến nhất hiện tại chính là NS2 và OMNet++. Hai công
cụ này chính là ví dụ điển hình về mô phỏng mạng. Trong số những công cụ này, NS2
nổi bật hơn cả bởi tính lâu đời, kèm theo là cộng đồng phát triển đông đảo. NS2 ra đời từ
năm 1989 – công cụ ra đời sớm nhất, đến nay, bộ thư viện các giao thức đã rất đầy đủ.
NS2 đã hỗ trợ sẵn các giao thức phổ biến hiện nay. Đồng thời, khả năng tùy biến của

nên việc truyền nhận thông tin đối với các sensor này gặp nhiều khó khăn. Từ đó, chúng
ta cần tối ưu quá trình hoạt động của các sensor để đạt hiệu suất cao nhất. Bài toán định
tuyến trong mạng cảm biến không dây sinh ra để giải quyết vấn đề đó.
3. Ứng dụng của mạng cảm biến không dây.

Mạng cảm biến không dây được ứng dụng nhiều trong các lĩnh vực nghiên cứu và
quân sự. Một số ví dụ có thể kể ra là theo dõi hoạt động của các sinh vật. Khi nghiên cứu
các một số loài vật, ta cần biết được thói quen sinh hoạt của chúng. Chẳng hạn, một số
loài động vật sắp tuyệt chủng, để bảo vệ và giữ được các cá thể còn lại, ta cần biết được
tập tính của chúng. Hoặc khi nghiên cứu về các dư chấn động đất tại một vùng địa lý nào
đó, ta cũng có thể đặt các sensor cảm biến đo độ rung chuyển. Từ các kết quả thu được ta
có thể dự báo kết quả trong tương lai. Riêng đối với lĩnh vực quân sự, thông tin yêu cầu
phải luôn được cập nhật, chính xác và thay đổi liên tục. Từ các sensor ta có thể thu được
những trạng thái bất thường của môi trường khi có biến cố. Vấn đề càng nghiêm trọng
đối với những vùng chiến sự, thắng thua chỉ trong gang tấc. Còn đối với lĩnh vực sản
xuất, công nghệ cao, chẳng hạn ta cần thu thập nhiệt độ bề mặt của tường tại các vùng
khác nhau trong lò phản ứng hạt nhân. Mọi sự thay đổi sẽ liên tục cập nhật và luôn đảm
bảo giải quyết kịp thời khi có sự cố xảy ra.
4. Bài toán định tuyến mạng cảm biến không dây.

Một câu hỏi cũng được đặt ra là: tại sao không áp dụng các thuật toán định tuyến đã
có trước đây? Mặc dù những phương pháp đó đã được đánh giá là hiệu quả, hay đã được
áp dụng từ rất lâu rồi, tuy nhiên ta cũng cần phải hiểu là mỗi bài toán sẽ gặp một vấn đề
khác nhau, đặc biệt là trong lĩnh vực mạng không dây. Chẳng hạn, với các mạng thông
thường hiện nay, các phần tử trong mạng lưu dữ liệu về một bảng thông tin ở các phần tử
xung quanh. Khi muốn gửi thông tin tới đâu, node đó chỉ việc kiểm tra thông tin trong
bảng định tuyến đó rồi lựa chọn một số node để gửi. Nhưng vấn đề sẽ không còn đúng
nữa khi mà các node thường xuyên di chuyển (chẳng hạn các sensor gắn trên động vật)
hay khi chúng không hoạt động liên tục (sensor hoạt động dựa trên năng lượng ánh sáng,
14

node trên diện tích đó. Như vậy tọa độ của các node có thể coi là ngẫu nhiên. Việc mô
phỏng cũng phải đảm bảo được với điều kiện tương tự như vậy. Năng lượng ban đầu
cung cấp cho mỗi node có thể gần xấp xỉ nhau (trong quá trình sản xuất hàng loạt với số
lượng lớn các sensor), Vì vậy, ban đầu chúng ta có thể coi các node đồng đều về mặt
năng lượng. Trong quá trình hoạt động, do các điều kiện môi trường mà mỗi node sẽ bị
tiêu hao năng lượng khác nhau. Một node bị mất năng lượng sẽ không thể gửi nhận
thông tin tới các node khác, cũng như khả năng thu thập thông tin. Việc này sẽ ảnh
hưởng tới các node khác, mỗi node phải dựa vào thuật toán định tuyến đã được cài đặt
để quyết định gửi thông tin cho node nào còn đang hoạt động và có thể về được tới node
trung tâm mà không gây tắc nghẽn. Rõ ràng đây là một bài toán phức tạp và hiện nay
đang được nhiều nhà nghiên cứu đề xuất nhiều giải pháp khác nhau.
Những đề tài về mạng cảm biến không dây là khá nhiều. Lý do chính là đây là một
vấn đề lớn và còn nhiều vấn đề chưa được khai thác. Để thực hiện tốt hơn công việc của
mình, chúng tôi đã giới hạn phạm vi nghiên cứu từ đó làm tăng chất lượng và tính ứng
dụng của sản phẩm. Chúng tôi tập trung nghiên cứu bài toán định tuyến với điều kiện
15

Phạm Văn Khắc - 20081397

15

Lớp CNPM-K53


Đồ án tốt nghiệp
xuất hiện hố trong mạng. Với tình huống này, các node mạng giao tiếp với nhau sẽ bị
hạn chế hơn. Tuy nhiên tính thực tế lại rất cao vì điều kiện ngoại cảnh sẽ không bao giờ
thuận lợi cho việc truyền tin. Hình vẽ sau mô tả ví dụ việc tìm đường đi trong một mạng
xuất hiện hố lớn ở giữa:


trực quan cho OMNet++). Chi tiết của việc so sánh các công cụ mô phỏng NS2 và
OMNet++ có thể xem thêm trong phần phụ lục.

Hình Giao diện Tkev và NAM
Đặc tính

Tkev
Được tích hợp vào quá trình
mô phỏng
Đẹp, Dễ sử dụng, trực quan
Không cho phép di chuyển
chạy đến thời điểm bất kỳ
trong quá trình mô phỏng

NAM
Tách riêng sau khi quá trình
Phương thức hoạt động
mô phỏng ngầm kết thúc
Tính dễ sử dụng
Khó sử dụng, mất công học
Cho phép người dùng lựa
Thanh kéo thời gian
chọn thời điểm diễn ra sự
kiện
Người dùng có thể lựa chọn
Chưa cho phép người dùng
Theo vết
1 gói tin và theo dõi đường
theo vết gói tin
đi của nó

Không cho phép

Bảng : Bảng so sánh hai công cụ thể hiện trực quan mô phỏng mạng.

18

Phạm Văn Khắc - 20081397

18

Lớp CNPM-K53


Đồ án tốt nghiệp
Từ bảng trên, chúng tôi rút ra một số nhận xét như sau:
-

Mỗi công cụ đều có điểm mạnh: Tkev hướng tới tính dễ sử dụng, với đồ họa trực
quan, còn NAM cho phép người dùng có thể tương tác nhiều hơn.
Tkev không thể hoạt động độc lập và đó là hạn chế lớn, trong khi đó, NAM có thể
hoạt động với file trace đầu vào duy nhất.
Những tính năng hỗ trợ người dùng của NAM là rất cần thiết với những người
phân tích kết quả.

Thông qua những kết quả trên chúng tôi đã quyết định tích hợp những ưu điểm của
cả hai công cụ và khắc phục những hạn chế của các công cụ đó, từ đó đảm bảo tính dễ sử
dụng và trở thành công cụ hỗ trợ đắc lực cho những người nghiên cứu về các vấn đề định
tuyến mạng.

19


20

Lớp CNPM-K53


Đồ án tốt nghiệp

Hình Sự kiện được biểu diễn theo thời gian trong NS2
Các sự kiện này được sắp xếp theo trục thời gian. Như vậy, mỗi một sự kiện đã chứa
một biến thời gian tại thời điểm nó xảy ra. Các sự kiện này phải đảm bảo được các yếu
tố sau:
-

-

Mỗi một sự kiện phải chứa một giá trị thời gian, cho biết sự kiện đó xảy ra tại thời
điểm nào. Sự kiện là tuần tự, tức là sự kiện sau có thời gian lớn hơn sự kiện trước
đó.
Các sự kiện diễn ra rời rạc. Khoảng cách giữa các sự kiện có thể sẽ không đều
nhau, lúc nhiều lúc ít.
Trong quá trình mô phỏng, sự kiện được gọi lần lượt. Sẽ không có hiện tượng sự
kiện sau lại được gọi trước. Mặc dù có những trường hợp sự kiện này sinh ra một
sự kiện khác như dưới đây:

Hình Quá trình mô phỏng các sự kiện.
Người dùng có thể tương tác với NS2 qua hai phương thức. Cách thứ nhất, người
dùng có thể sử dụng ngôn ngữ TCL để tương tác với NS2. Đây là một ngôn ngữ kịch bản
dễ học, ngắn gọn. Cách thứ hai là người dùng có thể trực tiếp chỉnh sửa ở sâu trong lõi
của NS2. Việc này đòi hỏi tốn nhiều công sức và cần một hiểu biết sâu về ngôn ngữ C+


Phạm Văn Khắc - 20081397

22

Lớp CNPM-K53


Đồ án tốt nghiệp

Hình Sự tương ứng từ TCL tới C++
Cả hai ngôn ngữ đều chứa các lớp đối tượng. Có một sự tương ứng giữa một số lớp
giữa hai ngôn ngữ. Sự kế thừa, bao đóng của các đối tượng cũng được giữ nguyên và
giống nhau ở cả hai ngôn ngữ này.
3. Các thành phần cơ bản của NS2

Hệ thống NS2 rất phức tạp. Hệ thống này bao gồm với hơn trăm lớp cơ bản. Trong
đó lại được chia thành hai khối: khối điều khiển và khối dữ liệu. Với khối điều khiển,
khối này có vai trò tạo và thực thi quá trình mô phỏng. Từ dữ liệu đầu vào, khối này xử
lý, đưa ra kết quả đầu ra. Khối thứ hai, khối dữ liệu, đóng vai trò là các đối tượng dữ liệu
cơ sở phục vụ cho quá trình mô phỏng. Để có một cái nhìn tổng quát hơn, người đọc có
thể xem trong hình sau:

23

Phạm Văn Khắc - 20081397

23

Lớp CNPM-K53


Hình File trace: trace.tr
Đây là file mặc định mà NS2 quy định (chúng ta hoàn toàn có thể thay đổi định dạng
này, và chúng tôi đã làm) bao gồm các trường thông tin cơ bản sau:

Hình Các trường thông tin của file trace.
Chẳng hạn, ký hiệu đầu tiên có thể là ‘+’ ‘-‘ ‘r’ hay ‘d’ biểu diễn loại của sự kiện.
-

Trace/Enque: + : gói tin được cho vào hàng đợi
Trace/Deque - : gói tin được lấy ra khỏi hàng đợi.
Trace/Drop: d : gói tin bị hủy
Trace/Recv: r : gói tin được nhận ở 1 node.

Các trường khác người đọc có thể tham khảo thêm trong cuốn sách giới thiệu về NS2:
“Introduction to Network Simulator NS2” trong phần phụ lục.
Trong quá trình tìm hiểu, chúng tôi đã nhận thấy rằng nếu để nguyên định dạng
như NS2 quy định, trace file sẽ gây khó khăn cho người đọc và muốn phát triển mở
rộng. Chúng tôi cũng nhận thấy rằng hiện nay có 2 loại định dạng phổ biến, đó là JSON
và XML. Hai ngôn ngữ đặc tả này thông dụng và được hỗ trợ bởi nhiều thư viện phân
tích. Chính vì vậy chúng tôi đã quyết định lựa chọn 1 trong 2 ngôn ngữ này để sử dụng
cho file trace của mình.Và chúng tôi quyết định lựa chọn XML bởi tính dễ đọc, dễ hiểu,
thuận lợi cho việc phân tích dữ liệu. Đồng thời khi phân tích trace file với dữ liệu lớn,
hiệu năng vẫn được đảm bảo. Ở phần sau chúng tôi có nói về hiệu năng phân tích trace
file với số lượng các node khác nhau.
Sau đây là định dạng của trace file mà chúng tôi quy định:

25

Phạm Văn Khắc - 20081397