LỜI CẢM ƠN
Lời đầu tiên em xin chân thành cảm ơn các thầy (cô) giáo trong bộ môn
Mạng & Truyền Thông cũng như các thầy cô giáo trong trường Đại học Công nghệ
Thông tin & Truyền thông, những người đã dạy dỗ, trang bị cho em những kíến thức
bổ ích trong thời gian em được học tập và nghiên cứu tại trường.
Em xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy giáo ThS. Lê Khánh Dương
người đã tận tình hướng dẫn, gợi ý và chỉ bảo cho em trong suốt thời gian làm đồ án
tốt nghiệp vừa qua để em có thể hoàn thành đồ án một cách tốt nhất.
Tiếp theo, em xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, những
người thân đã cổ vũ, động viên tiếp thêm cho em nghị lực để em hoàn thành bản báo
cáo thực tập tốt nghiệp này.
Em xin chân thành cảm ơn !
Thái Nguyên, tháng 06 năm 2012.
Sinh viên
Phạm Sĩ Thức
 

1


LỜI CAM ĐOAN
Trong kỳ làm đồ án tốt nghiệp này để hoàn thành nội dung bản đồ án bản
thân em đã tự tìm hiểu, nghiên cứu dựa trên các tạp chí, sách báo và những nguồn
tài liệu trên internet, cộng với sự giúp đỡ nhiệt tình của ThS. Lê Khánh Dương và sự
tham khảo cách thức trình bày từ một một số đồ án từ các khóa trước. Kết quả là em
đã hoàn thành đồ án với đề tài “Nghiên cứu và cài đặt mô phỏng hoạt động của
dịch vụ HLS trong mạng MANET”
Em xin cam đoan nội dung trong đồ án này không sao chép từ các đồ án
trước đó. Nếu có điều gì sai sót em xin chịu hoàn toàn trách nhiệm.

Thái Nguyên, tháng 6 năm 2012

......................................................................................................................................33
Hình 1-10. Kiến trúc thư mục của ns-allinone-2.xx trong môi trường Linux............33
......................................................................................................................................33
Hình 1-11. Luồng các sự kiện cho file Tcl chạy trong NS.........................................33
......................................................................................................................................38
Hình 2-1. Nhóm các cell tạo thành các region............................................................38
4


......................................................................................................................................40
Hình 2-2. Candidate tree ở phân cấp 3 cấp.................................................................40
......................................................................................................................................41
Hình 2-3. Ví dụ về các reponsible cell của một node.................................................41
......................................................................................................................................42
Hình 2-4. Giải pháp cập nhật trực tiếp........................................................................42
......................................................................................................................................43
Hình 2-5. Giải pháp cập nhật gián tiếp.......................................................................43
......................................................................................................................................46
......................................................................................................................................46
......................................................................................................................................47
Hình 2-6. Các yêu cầu định vị.....................................................................................47
......................................................................................................................................49
Hình 2-7. Cơ chế mở rộng diện tích...........................................................................49
......................................................................................................................................53
Hình 2-8. Che giấu với một proxy cell.......................................................................53
......................................................................................................................................65
Hình 3-1. Hình ảnh mô phỏng dịch vụ với số node là 40...........................................65
......................................................................................................................................66
Hình 3-2. Hình ảnh mô phỏng dịch vụ với số node là 80...........................................66
......................................................................................................................................66


6


DANH MỤC BẢNG
Bảng 1-1. Sự so sánh của các dịch vụ định vị………………………………...……23
Bảng 3-1. Cấu trúc của dòng sự kiện HLS gửi yêu cầu…………………………….62
Bảng 3-2. Cấu trúc của dòng sự kiện HLS nhận phản hổi………………………….63
Bảng 3-3. Cấu trúc dòng sự kiện HLS khởi tạo một truy vấn vị trí node của một
node…………………………………………………………………………………64
Bảng 3-4. Cấu trúc dòng sự kiện của các gói tin được gửi, nhận, forward và drop..65

7


BẢNG THUẬT NGỮ VIẾT TẮT
Tên viết tắt
MANET
WLAN
DSDV
OLSR
DSR
AODV
ZRP
TORA
GPS
GLONASS
GALILEO
SPA


Distance Routing Effect Algorithm For Mobility
Reactive Location Service
Grid Location Service
Hierarchical Location Service
Geographical Region Summary Service
Responsible Cell
Practical Extraction and Report Language

8


MỞ ĐẦU
Công nghệ thông tin là một lĩnh vực không thể thiếu trong cuộc sống con
người hiện nay. Sự phát triển của công nghệ thông tin là thước đo để đánh giá về
trình độ phát triển của mỗi quốc gia. Công nghệ thông tin đóng góp rất lớn vào trong
đời sống cũng như sản xuất của con người. Và trong lĩnh vực công nghệ thông tin
thì không thể không nhắc tới sự phát triển của các hệ thống mạng như: Mạng di
động, mạng internet, wireless network….
Truyền thông không dây đang phát triển rất mạnh mẽ trong thời gian gần đây.
Những công nghệ tính toán đang được hiện đại hóa rất nhanh, ngày càng có rất
nhiều loại máy tính tiện dụng, nhỏ, nhẹ xuất hiện trên thị tường. Những thiết bị này
đã làm cho việc tính toán và truyền thông được thực hiện ở bất cứ đâu và bất cứ thời
gian nào. Vì vậy một hướng đầy tiềm năng trong các cấu trúc mạng không dây là có
thể truyền thông ở bất cứ đâu và bất cứ thời gian nào và đó là kiểu mạng tùy biến
không dây di động (Mobile Ad hoc network - MANET). Một mạng MANET chứa
một tập hợp các thiết bị di động mà không cần sự hỗ trợ của trạm cơ sở. Nó có thể
được triển khai và hoạt động với nguồi năng lượng là pin.
“Nghiên cứu và cài đặt mô phỏng hoạt động của dịch vụ HLS trong
mạng MANET” là tên đề tài mà em sẽ giới thiệu trong báo cáo đồ án tốt nghiệp
này. Mục đích của đề tài nhằm nghiên cứu dịch vụ định vị trong mạng MANET và

thông giữa các node được thực hiện nếu như hai node là đủ gần nhau để trao đổi các
gói tin.
Có thể hình dung mạng MANET như một đồ thị, trong đó các node mạng
được biểu diễn bởi các đỉnh của đồ thị. Nếu hai node có thể truyền thông trực tiếp
với nhau, liên kết đó được biểu diễn bởi đường nối giữa hai node. Đồ thị biểu diễn
này là một đồ thị tùy ý, có thể thay đổi hình dạng tại bất cứ thời điểm nào.
10


Hình 1-1 là một mạng MANET gồm 7 node. Hình tròn biểu diễn phạm vi
hoạt động của mỗi node. Các node nằm trong phạm vi hoạt động của nhau có thể
truyền thông trực tiếp được với nhau.

Hình 1-1. Mạng MANET với 7 node mạng.
Mạng MANET có thể là một mạng độc lập, hoặc cũng có thể được kết nối
với một mạng khác lớn hơn, ví dụ mạng Internet.
Kết nối giữa các node mạng được đặc trưng bởi khoảng cách giữa các node
và tính sẵn sàng hợp tác để tạo thành mạng mặc dù là tạm thời.
(1) Khoảng cách giữa các node: Khoảng cách giữa các node hoặc trạng thái ở
gần nhau của chúng định nghĩa ranh giới mạng. Chỉ cần hai hoặc nhiều node
chuyển động trong một bán kính nhất định là tạo thành một mạng ad-hoc.
Chính sự chuyển động làm cho khoảng cách giữa các node thay đổi gây ra
bản chất đặc biệt (ad-hoc) của mạng.
(2) Tính sẵn sàng hợp tác: (1) chỉ là điều kiện cần, chưa phải là điều kiện đủ
để thành lập mạng ad-hoc. Các node ở trong khoảng cách đủ gần phải sẵn
11


sàng hợp tác để tạo thành mạng. Nói cách khác, tự bản thân node quyết định
“online” hay “offline”.

topology về mạng.
-

Chủ ứng: Duy trì các tuyến đường trước khi dữ liệu được gửi, ví dụ:
DSDV, OLSR…

-

Phản ứng: Khám phá một tuyến đường nếu một kết nối được thiết lập, ví
dụ: DSR, AODV…

-

Hybrid: Là sự kết hợp của định tuyến chủ ứng cục bộ và phản ứng liên
vùng để tăng khả năng truyền thông, ví dụ: ZRP,TORA…

Dựa trên vị trí: Các gói tin được định tuyến tùy theo vị trí địa lý của đối tác
truyền thông. Thông tin vị trí này được hỗ trợ bởi một dịch vụ định vị.
Khi sử dụng các giao thức định tuyến dựa trên topology, chi phí truyền thông
phụ thuộc vào tốc độ thay đổi cấu trúc của mạng. Trong một mạng MANET có thể
chứa những node di chuyển nhanh, tốc độ thay đổi có thể là cao, kết quả là cần rất
nhiều lưu lượng truyền thông để đảm bảo những thông tin định tuyến trong những
node được cập nhật.
Với giao thức định tuyến dựa trên vị trí, những node có thể xác định vị trí của
chúng và những node khác trong mạng. Điều đầu tiên của những công việc này
được thực hiện bởi một hệ thống định vị vị trí, có khá nhiều những hệ thống như
vậy, như GPS, GLONASS hoặc GALILEO. Các dịch vụ này sử dụng độ trễ lan
truyền tín hiện của sự phát sóng vô tuyến của vệ tinh để tính toán những vị trí tuyệt
đối với sai số nhỏ (khoảng vài mét). Nhưng cũng có những hệ thống không yêu cầu
đặc tính này của cơ sở hạ tầng, ví dụ như Self-Positioning Algorithm (SPA) có thể



một node nhận được một gói tin trùng lặp với cùng số thứ tự nó sẽ loại bỏ gói tin
này. Trong bảng định tuyến node lưu trữ thông tin định tuyến tới tất cả các node
khác trong mạng.
AODV (Ad Hoc On-Demand Distance Vector): Là giao thức dựa trên thuật
toán vector khoảng cách. AODV tối thiểu hoá số bản tin quảng bá cần thiết bằng
cách tạo ra các tuyến trên cơ sở theo yêu cầu, ngược với việc duy trì một danh sách
hoàn chỉnh các tuyến như thuật toán DSDV.
DSR (Dynamic Source Routing): Là một giao thức định tuyến phản ứng từ
node nguồn. Trong đó, các node di động cần duy trì bộ nhớ đệm về tuyến chứa các
node nguồn mà node di động nhận biết được. Các thực thể trong bộ nhớ đệm về
tuyến được cập nhật liên tục.
TORA (Temporally Ordered Routing Algorithm): Là một thuật toán định
tuyến phân bố không có vòng lặp và độ thích nghi cao, dựa trên khái niệm đảo
ngược đường thông. TORA được đề xuất cho môi trường nối mạng có tính linh
động cao. Nó là một giao thức khởi phát từ nguồn và cung cấp đa tuyến cho mọi cặp
node nguồn/đích cần thiết.
Tiếp theo, sau đây là một số giao thức định tuyến dựa trên nhận thức vị trí.
1.2.1 GPSR
Greedy Perimeter Stateless Routing (GPSR) là một giao thức định tuyến hoạt
động theo nguyên tắc:“Tích cực sử dụng sơ đồ địa lý để đạt được khả năng mở
rộng”. Đây là sự kết hợp của greedy routing và primeter routing . Khi sử dụng
GPSR, mỗi node định kỳ gửi những gói tin broadcast 1-hop gọi là các beacon, chứa
node ID và vị trí hiện tại của nó. Bởi sử dụng những beacon, mỗi node có thể duy trì
một danh sách các lân cận 1-hop. Bất cứ khi nào một node không nhận được một
beacon từ một lân cận đã biết trước đó trong một khoảng thời gian nhất định, nó sẽ
cho rằng lân cận này là không thể đi đến và bị xóa khỏi danh sách hàng xóm.
15


trong hình 1-3. Đường nét đậm biểu thị những hop mà gói tin từ nguồn S tới đích D
được chuyển tiếp trong chế độ greedy. Bất cứ khi nào gói tin đi đến một node mà
không có lân cận gần hơn tới D bên trong phạm vi thu phát sóng (diện tích màu tối
17


biểu thị vùng void), gói tin được chuyển sang chế độ perimeter và được chuyển tiếp
tương ứng theo luật bàn tay phải, được biểu thị bởi đường nét đứt. Đường nét tròn
hiển thị phạm vi vô tuyến của các node, và đường tròn nét đứt phân đoạn khoảng
cách tới đích khi gói tin được chuyển tới chế độ perimeter. Sau đó nếu nó tìm thấy
node mà gần với đích nhất mà trong phạm vi phát sóng thì gói tin thoát khỏi thế độ
perimeter và trở về chế độ greedy.
1.2.2 Định tuyến Terminodes
Định tuyến Terminodes bao gồm: Anchored Geodesic Packet Forwarding
(AGPF) và Terminode Local Routing (TLR). TLR sử dụng định tuyến nguồn để duy
trì các tuyến đường tới các lân cận gần với một node. Vì thế, nó xác định một lân
cận mà mọi node biết vị trí của lẫn nhau. Trong AGPF, nguồn bao gồm một danh
sách các điểm neo trong gói tin. Một điểm neo là một điểm địa lý trên tuyến đường
mà phải được thăm. Những điểm neo được tính toán dựa trên một bản đồ hoặc dựa
trên thông tin được cung cấp bởi những node khác. Giữa các điểm neo, AGPF sử
dụng định tuyến greedy tương tự như GPSR. Nếu một gói tin đi đến một node mà từ
đó điểm neo có thể được đi đến trong một số lượng các hop được xác định trước thì
nó được chuyển tiếp tới điểm neo tiếp theo. Trong trường hợp node mục tiêu nằm
bên trong cùng với lân cận thì gói tin được chuyển tới mục tiêu.
1.2.3 LAR
Location Aided Routing (LAR) là một phương pháp được sử dụng trong
những giao thức định tuyến phản ứng trong quá trình khám phá tuyến để hạn chế
flooding. Với thông tin định vị có sẵn, một vùng kỳ vọng là một vùng yêu cầu được
định nghĩa. Gói tin khám phá tuyến chỉ cần được broadcast trong vùng yêu cầu để
tìm ra node đích. Vùng yêu cầu thường chứa vùng kỳ vọng.

All-for-some.

-

All-for-all.

Nếu những server định vị phục vụ thông tin cho tất cả các node (some-for-all
và all-for-all), lưu lượng cập nhật là cao trong các mạng lớn hơn bởi vì tất cả các
node phải phát ra vị trí của chúng tới những server định vị. Vì thế, hệ thống có thể
đối mặt với các vấn đề mở rộng.
Ngoài ra còn có các tiêu chuẩn khác để phân loại các dịch vụ định vị là:
Cấu trúc: Một dịch vụ định vị có thể là phân cấp, có nghĩa là nó thiết lập một
loại cụ thể của phân cấp. Thông thường, điều này được sử dụng để đạt được sự tập
trung cao hơn của những server định vị gần với vị trí thực của một node. Khoảng
cách càng lớn thì sự tập trung của những thông tin vị trí càng thấp. Nói một cách
thông thường, số lượng các cấp độ phân cấp được thay đổi theo kích thước của
mạng. Tuy nhiên, có một vài cách tiếp cận với số lượng cố định các cấp của phân
cấp. Nếu dịch vụ định vị không sử dụng cấu trúc phân cấp thì sẽ là cấu trúc phẳng
(flat).
Sự xác định server định vị (LSI): Nếu dịch vụ định vị sử dụng những server
định vị, những server định vị này có thể được xác định bởi node ID (id-based LSI)
hoặc bởi vị trí thực của chúng (position-based LSI). Trong trường hợp thứ hai, các
server là có thể hoán đổi miễn là chúng nằm trong một vùng cụ thể.
Phân vùng: Hầu hết các dịch vụ định vị sử dụng việc phân chia diện tích
cũng như sử dụng một kiến trúc phân cấp. Các kiến trúc phân cấp dựa trên việc chia
vùng mạng thành những vùng khác nhau và sử dụng tập hợp những vùng này để
thành lập ra những vùng ở cấp cao hơn.
Chiến lược cập nhật và yêu cầu: Miêu tả phương thức được sử dụng bởi
một dịch vụ định vị để tìm ra các server định vị. Các chiến lược có thể là flooding,
20


hoặc gửi một yêu cầu định vị mà sau đó phải được trả lời một lần nữa bởi node được
yêu cầu.
No obfuscation: Có thể cho một intruder theo dõi vị trí của một node từ một
hoặc nhiều sự vị trí xa trong không gian mạng mà không cần nhận thấy node bị ảnh
hưởng.
Trong bảng 1-1, các dịnh vụ định vị được phân chia tùy theo những tiêu
chuẩn này. Trong trường hợp của cấu trúc phân cấp, số lượng của các cấp phân cấp
được đưa ra. Một dịch vụ định vị sử dụng truyền thông unicast cho các cập nhật
hoặc các yêu cầu định vị, truyền thông multicast có thể được triển khai khi cần thiết
và được hỗ trợ bởi giao thức định tuyến.

Bảng 1-1. Sự so sánh của các dịch vụ định vị.
Phần sau đây là một số dịch vụ định vị được sử dụng trong mạng MANET.
1.3.1 DREAM
22


Hình 1-5. Hiệu ứng khoảng cách.
Distance Effect Algorithm for Mobility (DREAM) sử dụng hiệu ứng khoảng
cách được thể hiện trong hình 1-5: Trong trường hợp 2 node B và C di chuyển với
tốc độ như nhau, hướng đi của A tới node mà cách xa hơn thay đổi chậm hơn. Các
node kết hợp hiệu ứng này trong chiến lược cập nhật của chúng. DREAM sử dụng
fllooding để lan truyền thông tin vị trí với tần số và khoảng cách flooding khác nhau
bởi việc kết hợp các quy tắc: Khoảng cách càng lớn thì tần số flooding càng thấp;
tốc độ di chuyển node càng cao, thì tần số flooding càng cao.
Giả sử rằng một gói tin có thể đi tới bất kỳ một node khác trong mạng với 15
hop, chiến lược cập nhật cơ bản dưới đây có thể được áp dụng theo DREAM: Mỗi
node flood thông tin vị trí cho các lân cập 2-hop sau mỗi 5 giây, cho lân cận 5-hop
cho mỗi 20 giây và cho lân cận 15-hop sau mỗi 120 giây. Hơn nữa các node thay đổi



Các vấn đề có thể xảy ra khi không có node nào trong homzone. Vấn đề đầu
tiên này có thể được giải quyết bởi tự động thay đổi kích thước của vùng. Vấn đề
thứ hai vô hiệu hóa dịch vụ định vị homezone từ việc mở rộng cho các mạng lớn:
Nếu các node cách xa với homezone của chúng, thì chúng cần cập nhật nó thường
xuyên. Điều này tạo nên rất nhiều lưu lượng khoảng cách dài mà cuối cùng có thể
gây tắc nghẽn mạng.
1.3.3 Hệ thống Qourum
Dịch vụ định vị Quorum được dựa trên ý tưởng của việc sử dụng các hệ
thống cơ sở dữ liệu. Thông tin định vị được gửi tới một tập con các node có sẵn
(được gọi là quorum), các yêu cầu định vị được gửi tới một quorum khác. Mỗi
quorum được xây dựng trong một cách mà phần giao nhau với bất kỳ quorum nào
khác là không rỗng. Như một hệ quả, gói tin yêu cầu định vị đi tới ít nhất một server
định vị cho những node được yêu cầu, truy vấn có thể được trả lời.
1.3.4 Dịch vụ định vị phản ứng(RLS)
Ý tưởng của dịch vụ này là giống với cơ chế khám phá tuyến của DSR. Một
yêu cầu định vị cho một node được flood tới toàn mạng. Khi yêu cầu đi tới mục tiêu
của nó, node này tạo ra một gói tin phản hồi và được trả lại cho node tạo truy vấn.
Cơ chế flooding cơ bản là không hoàn toàn tin cậy. Flooding tuyến tính, flooding
cấp số nhân và flooding nhị phân cung cấp các sự cải thiện.
RLS không tạo ra bất kỳ gói tin cập nhật chủ ứng nào cũng không có các
server định vị. Nó làm việc theo phương pháp phản ứng hoàn toàn.
1.3.5 Dịch vụ định vị lưới(GLS)
Sự phân chia vùng
GLS chia vùng mạng của Ad-hoc thành những grid phân cấp được kết hợp
bởi các hình vuông với các kích thước khác nhau. Sự phân chia này được biết bởi
25