BÁO CÁO TỔNG KẾT
ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CỦA SINH VIÊN
THAM GIA XÉT GIẢI THƯỞNG "TÀI NĂNG KHOA HỌC TRẺ VIỆT NAM"
NĂM 2014 DÀNH CHO SINH VIÊN

CÂN BẰNG TẢI TRONG ĐỊNH TUYẾN VƯỢT HỐ CHO
MẠNG CẢM BIẾN KHÔNG DÂY
SỬ DỤNG YẾU TỐ NGẪU NHIÊN
Thuộc nhóm ngành khoa học: Kỹ thuật và Công nghệ 3 (KT3)
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

BÁO CÁO TỔNG KÊT
ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CỦA SINH VIÊN
THAM GIA XÉT GIẢI THƯỞNG "TÀI NĂNG KHOA HỌC TRẺ VIỆT NAM"
NĂM 2014 DÀNH CHO SINH VIÊN


-2-

CÂN BẰNG TẢI TRONG ĐỊNH TUYẾN VƯỢT HỐ CHO
MẠNG CẢM BIẾN KHÔNG DÂY
SỬ DỤNG YẾU TỐ NGẪU NHIÊN
Thuộc nhóm ngành khoa học: Kỹ thuật và Công nghệ 3 (KT3)

Sinh viên thực hiện:
Dân tộc:
Lớp, khoa:
Năm thứ:
Ngành học:
Người hướng dẫn:


Ý nghĩa

Sensor

Cảm biến

WSN

Wireless Sensor Network

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

NS2

Network Simulator – 2

Tên một phần mềm mô
phỏng mạng

Hố mạng

Vùng mạng không tồn tại
cảm biến còn khả năng hoạt
động

Hole

Chú thích


trên mạng cảm biến, gây nên những khó khăn và thách thức cho việc đảm bảo tốc độ truyền
tin và tiết kiệm năng lượng. Hơn nữa mỗi nút chỉ có khả năng nhận biết trong một vùng bán
kính rất hẹp, thường chỉ bao gồm một vài nút lân cận. Vì mỗi nút chỉ có thông tin cục bộ
hạn chế và có khả năng tính toán rất giới hạn, việc định tuyến – xác lập đường truyền tin
giữa các cặp nút nguồn và đích – trở nên không đơn giản. Đặc biệt bài toán truyền tin trên
mạng không dây, mà trung tâm của nó là vấn đề định tuyến, sẽ trở nên rất khó khăn, thách
thức khi mạng được bố trí ở vùng môi trường có địa hình phức tạp.
Hiện nay ứng dụng mạng cảm biến đang thu hút mối quan tâm rất lớn, do đó các hoạt
động nghiên cứu về công nghệ truyền tin cảm biến không dây đang được thúc đẩy mạnh.
Đặc biệt, bài toán định tuyến được coi là một vấn đề nóng do những đặc thù khó khăn riêng
biệt của mạng cảm biến đã kể trên. Tuy nhiên cho đến nay phần lớn các nghiên cứu học
thuật trong lĩnh vực này có xu hướng giả định một môi trường lý tưởng; chưa có nhiều
những đề xuất về giải thuật định tuyến có tính đến những yếu tố liên hệ địa hình phức tạp.
Trong thực tế, mạng cảm biến không dây thường được triển khai trên những địa hình phức
tạp, và còn phải chịu nhiều điều kiện khắc nghiệt từ bên ngoài. Trên các địa hình thực tế,
thường tồn tại nhiều vật cản như sông, hồ, đầm lầy,… dẫn tới việc không thể bố trí đều đặn


-8-

nút mạng cảm biến. Thậm chí, tại các vùng ảnh hưởng thiên tai như núi lửa, động đất, lũ lụt,
… các nút mạng dễ bị hỏng, bị phá hủy do tác động bên ngoài. Những trường hợp như trên
sẽ dẫn tới sự tồn tại các vùng mạng có mật độ cảm biến rất thấp, thậm chí không tồn tại cảm
biến có khả năng hoạt động; đây là các vùng thường được gọi là các “hố” hay “hố mạng”.
Sự tồn tại của các hố mạng sẽ dẫn tới ảnh hưởng không tốt tới hoạt động truyền tin trong
mạng, làm giảm hiệu quả hay thậm chí làm tê liệt hoạt động của toàn mạng.
Với các giải thuật định tuyến truyền thống đã có, sự tồn tại các hố mạng sẽ dẫn đến hiện
tượng một lượng lớn gói tin sẽ được truyền men theo biên của hố. Mà hố có thể có hình
dạng khúc khuỷu phức tạp dẫn tới đường đi của các gói tin này bị kéo dài, dài gấp nhiều lần
so với đường đi tối ưu. Một hiệu ứng khác từ hiện tượng tập trung giao thông trên biên hố là

nhập mặn… hầu hết được theo dõi và đánh giá dựa trên kinh nghiệm. Một trong những giải
pháp hiệu quả là ứng dụng mạng cảm biến không dây, cho phép theo dõi, đánh giá được các
điều kiện tự nhiên trên những diện tích nông nghiệp rộng lớn.
Như đã phân tích, việc ứng dụng mạng cảm biến không dây trong thực tế, đặc biệt là
trong hoàn cảnh nước ta, nơi có nhiều mặt nước, địa hình và khí hậu phức tạp, chỉ đem lại
chất lượng và hiệu quả kinh tế khi chúng ta giải quyết tốt bài toán truyền tin mạng cảm biến
trong địa hình phức tạp. Chìa khóa then chốt ở đây chính là bài toán xây dựng cơ chế định
tuyến khắc phục hố mạng. Đóng góp nghiên cứu ở đây sẽ đem lại những giải pháp thực tiễn
mang tính kinh tế cao, tiết kiệm chi phí ban đầu, chi phí bảo trì và phát sinh. Thiếu những
đóng góp này, mạng cảm biến sẽ làm việc kém hiệu quả mà thời gian sống ngắn, gây sự
triển khai đi lại nhiều lần, tốn phí tiền của và thời gian.
Việt Nam cũng là một trong những nước chịu ảnh hưởng nặng nề từ tình trạng biến đổi
khí hậu của trái đất, chúng ta thường xuyên hứng chịu những điều kiện thời tiết cực đoan và
các dạng thiên tai khác nhau (như triều cường, giông bão, lũ đầu nguồn,... ). Mặc dù có thể
còn hơi sớm, nhưng khả năng sử dụng mang cảm biến không dây để theo dõi, giám sát vùng
thiên tai đang xảy ra là một tiềm năng thấy trước được. Rất khó cho con người có thể trực
tiếp lao vào khảo sát biến đổi vùng đang trải qua thiên tai, điều mà mạng cảm biến không
dây có thể thay thế vừa hiệu quả, vừa tránh mất mát tính mạng. Các nghiên cứu của chúng
tôi hứa hẹn đưa ra giải pháp hiệu quả cho việc theo dõi sự biến đổi nhanh chóng của hố
mạng, điều mà có thể ứng dụng vào để theo dõi và giám sát vùng “hố thiên tai” trong thực
tế. Tất nhiện đây là một bài toán thách thức, vì sự biến đổi nhanh của “hố thiên tai” sẽ phá
hủy mọi thiết bị liên lạc trên đường đi của nó. Tuy nhiên các thuật toán định tuyến xấp xỉ
thông minh có thể khắc phục được khó khăn này. Việc luôn biết trước hướng phát triển của
“hố thiên tai” sẽ giúp con người đưa ra phương án phòng tránh và đối phó hiệu quả, làm
giảm thiểu thiệt hại do thiên tai gây ra.
Một giải pháp thông minh cho bài toán định tuyến trong mạng cảm biến không dây trên
địa hình xấu, đặc biệt là bài toán định tuyến khắc phục hố, sẽ cho phép nâng cao khả năng
thích nghi của mạng cảm biến không dây với các địa hình đa dạng, phức tạp trong thực tế.
Đóng góp nghiên cứu tốt trong vấn đề này sẽ là điểm tựa then chốt giúp chúng ta xây dựng
giải pháp chung cho việc ứng dụng các mạng cảm biến không dây đạt hiệu quả cao trong

một phương pháp mô phỏng của riêng mình dựa trên một hệ công cụ có sẵn, nhưng cần
thêm những nỗ lực mở rộng chức năng công phu để có thể áp dụng hiệu quả.
Kỹ thuật phần mềm hệ thống: Phương pháp thực nghiệm của chúng tôi là xây dựng
một hệ thống mô phỏng chuyên dụng cho khảo sát định tuyến trên mạng không dây, với
những công cụ mạnh về tạo kịch bản trực quan và tự động, quản lý số nút mạng lớn với khả
năng thiết lập theo vùng, cho phép thiết lập các thuật toán định tuyến kiểu mới của người sử
dụng. Để xây dựng được một hệ thống phần mềm chuyên dụng này, chúng tôi dựa vào một
hệ công cụ mạnh đa năng đã phổ biến là NS2. Ý tưởng kiến trúc hệ thống của chúng tôi là
xây dựng những mô-đun hỗ trợ đa dạng để khai thác phần máy xử lý chính (engine) là lõi
thực hiện mô phỏng truyền tin do NS2 cung cấp. Ở đây, chúng tôi đã áp dụng nhiều kỹ thuật
phần mềm đa dạng để phát triển một hệ thống chuyên dụng kiểu mới trên cơ sở khai thác lõi
tính toán của một hệ đa năng có sẵn.
1.3 CÁC KẾT QUẢ ĐẠT ĐƯỢC – NỘI DUNG KỸ THUẬT CỦA BÁO CÁO
Những kết quả chính trong công trình nghiên cứu này của chúng tôi là như sau:


- 11 -

(i) Chúng tôi đề xuất mới một giao thức định tuyến vượt hố dựa trên thông tin địa lý,
khắc phục được những khó khăn gây ra do địa hình xấu gây ra. Đây là giao thức đầu
tiên có thể giải quyết tốt đồng thời 2 vấn đề nghiên cứu chuyên sâu:
− Sự kéo dài đường định tuyến: do các gói tin có xu hướng truyền men theo đường biên hô. Đường đi
của gói tin dài ra mức O(c2), c là độ dài đường đi tối ưu [1].
− Sự mất câng bằng tải của mạng: các nút biên hố và vùng lần cận phải chịu tải cao. Mất cân bằng tải
không những làm nút mạng tại vùng chịu tải cao hết băng thông dẫn tới tắc nghẽn đường truyền, mà
còn khiến chúng hoạt động liên tục, nhanh chóng cạn kiệt năng lượng và nút không còn khả năng
hoạt động (“nút chết”).

Một trong những ý tưởng cơ bản được đề xuất là sử dụng yếu tốt ngẫu nhiên để tạo ra
cơ chế định tuyến động, từ đó làm tăng tính cân bằng tải cho mạng. Chúng tôi tiến hành


- 12 -

thực tế Một phần mềm mô phỏng mạng được sử dụng phổ biến trên toàn thế giới là NS2 [2].
NS2 là một phần mềm mã nguồn mở, phần lõi được viết bằng ngôn ngữ C++ kết hợp với
ngôn ngữ kịch bản Tcl. NS2 giao tiếp với người sử dụng thông qua giao diện dòng lệnh và
file. Đầu vào của NS2 là kịch bản mô phỏng dưới dạng dòng lệnh hoặc file chứa dòng lệnh
Tcl. Đầu ra của NS2 là file kết quả – trace file – dưới dạng văn bản có cấu trúc. Mặc dù
được đánh giá cao về tính chính xác và khả năng tùy biến, NS2 lại không dễ dàng sử dụng.
Các công đoạn viết kịch bản và xử lý kết quả mô phỏng không được hỗ trợ nhiều, người sử
dụng phải tự viết mã kịch bản, khá dài và phức tạp, bằng tay hoặc thông qua các chương
trình cung cấp bởi bên thứ ba. Vì vậy việc mô phỏng các hoạt động của một mạng lớn đến
hàng nghìn nút là gần như bất khả thi.
Để phục vụ việc thực nghiêm trong công trình này, cũng như đóng góp chung cho cộng
đồng nghiên cứu quốc tế về định tuyến cho mạng cảm biến không dây, chúng tôi đã xây
dựng bộ công cụ mô phỏng, phát triển trên nền tảng NS2, hướng tới bài toán chuyên biệt:
mô phỏng và phân tích hoạt động của mạng cảm biến không dây. Trong đó tập trung cho
việc phục vụ phân tích và đánh giá các giải thuật định tuyến khi áp dụng thực tế. Hệ mô
phỏng của chúng tôi cung cấp các công cụ tạo kịch bản trực quan, giúp cho ngay cả những
người mới làm quen với mô phỏng mạng (và NS2) cũng có thể tạo được kịch bản mô phỏng
trong một thời gian ngắn (có thể rút gọn từ nhiều tuần xuống còn một vài ngày). Kích thước
mạng mô phỏng có thể lên tới hàng nghìn nút. Đồng thời cũng cung cấp các công cụ phân
tích kết quả, hướng tới các phân tích chuyên biệt, đánh giá các yếu tố thường được quan tâm
trong các nghiên cứu về định tuyến trong mạng cảm biến không dây.
Ngoài hai kết quả chính nói trên, chúng tôi cũng xin giới thiệu ngắn gọn về những công
việc đang thực hiện và kết quả dự kiến sẽ thu được, dựa trên việc phát triển những kết quả
đã thu được trên. Trong giai đoạn triển khai mới này, chúng tôi tập trung cho việc nâng cao
hiệu quả sử dụng của mạng cảm biến không dây khi áp dụng cho những bài toán thực tế khá
đặc biệt. Dựa trên phương pháp nghiên cứu riêng, các thuật toán định tuyến mới của chúng
tôi có sự phù hợp rất cao, thích ứng rất hiệu quả với các mạng cảm biến được triển khai trên


2

BÀI TOÁN ĐỊNH TUYẾN CHO MẠNG CẢM BIẾN KHÔNG DÂY

Cùng với việc có nhiều ứng dụng mạnh mẽ trong thực tiễn, mạng cảm biến không dây
cũng là một lĩnh vực thu hút nhiều sự quan tâm của các nhà khoa học. Một trong các chủ đề
nghiên cứu chính là các giao thức định tuyến. Mạng cảm biến không dây có các đặc thù rất
riêng biệt như: nút mạng có khả năng tính toán hạn chế (bộ vi xử lý < 20 MHz), bộ nhớ nhỏ
(< 4KB), nguồn năng lượng giới hạn (khoảng 0.3 – 0.5 Ah, 1.2 – 3 V, tùy loại cảm biến),
mạng lại thường có quy mô rất lớn, từ vài trăm đến vài nghìn nút mạng. Vì vậy, việc định
tuyến trong mạng cảm biến không dây không thể áp dụng các giải thuật định tuyến thường
thấy ở các mạng truyền thống như ethernet, Lan hay Internet. Một hướng tiếp cận rất hiệu
quả và thường được sử dụng là định tuyến địa lý. Hướng tiếp này được sử dụng rộng rãi vì
tính đơn giản và hiệu quả của nó.
Định tuyến địa lý là giao thức định tuyến dựa trên thông tin vị trí của các nút mạng.
Trong đó, mỗi nút mạng biết tọa độ của mình, tọa độ của các nút mạng lân cận trong vùng
phủ sóng của nó và tọa độ của nút đích, thông qua các dịch vụ định vị (ví dụ: GPS hay các
dịch vụ khác [3] [4]). Hướng tiếp cận sử dụng thông tin địa lý này hoạt động tốt với mạng
cảm biến không dây được bố trí tương đối dày đặc, khi đó có thể đạt được đường định tuyến
tối ưu và gần tối ưu. Với các địa hình xấu, hướng tiếp cận sử dụng thông tin địa lý phải đối
mặt với bài toán định tuyến vượt hố. Trong đó “hố” được định nghĩa là những vùng không
tồn tại nút mạng cảm biến còn khả năng hoạt động [5] [6]. Tồn tại hố trong mạng cảm biến
không dây có thể do nguyên nhân khách quan như: địa hình xấu, có chướng ngại vật, sông
hồ, miệng núi lửa… Hoặc do nguyên nhân chủ quan như: bố trí nút mạng không tốt để trống
vùng không có nút mạng; Sử dụng thuật toán định tuyến không tốt làm nút mạng ở một số
vùng chịu tải cao, dẫn tới nhanh chóng cạn kiệt năng lượng và không còn khả năng hoạt
động. Sự tồn tại của hố trong mạng cảm biến không dây dẫn đến việc truyền tin theo các
chiến thuật cố điển gặp nhiều vấn đề, trong đó có:
− Sự kéo dài của đường định tuyến: Trong định tuyến vượt hố, khi nút nguồn và nút đích nằm về hai



- 16 -

vì hình xấp xỉ rất gần với biên hố nên các nút trên biên hố vẫn chịu tải cao hơn các nút
thông thường, nên các đề xuất này chưa giải quyết được vấn đề mất cân bằng tải. Hơn nữa,
hố là một đa giác phức tạp, không thể biết trước số đỉnh của hình bao lồi, vì thế, việc sử
dụng bao lồi để biểu diễn hố dẫn tới việc đòi hỏi chi phí lớn để phát tán và lưu giữ thông tin
về hố tại các nút mạng. Trong trường hợp hố mạng là một đa giác lồi, bao lồi của hố sẽ
chính là đa giác tạo bởi các nút trên biên hố. Khi đó, các giải thuật sử dụng hình bao lồi để
biểu diễn hố sẽ không giảm được dung lượng gói tin quảng bá cũng như dung lượng bộ nhớ
đòi hỏi để lưu trữ thông tin về hố tại mỗi nút.
Một số nghiên cứu khác như [9] [10] [11] đề xuất việc sử dụng một “vùng cấm” là hình
cố định đủ lớn để bao trùm toàn bộ hố trước khi phát tán thông tin. Việc sử dụng “vùng
cấm” là một hình cố định để miêu tả hố cho phép giam chi phí phát tán thông tin và giảm
dung lượng bộ nhớ đòi hỏi ở mỗi nút mạng để lưu trữ thông tin về hố. Tuy nhiên, một số
giải thuật có đường định tuyến bị kéo dài hơn rất nhiều so với đường định tuyến tối ưu
(Hình 3). Hơn nữa, các giải thuật này đó chưa hiệu quả khi xét tới tính cân bằng tải của
mạng. Vì khi sử dụng một hình cố định để làm “vùng cấm” thì hình này chính là một hố ảo
với kích thước lớn hơn. Các nút trên biên của vùng cấm vẫn chịu tải nhiều hơn các nút
thông thường.

Hình 3: Đường định tuyến bị kéo dài trong một số nghiên cứu hiện tại


- 17 -

3

CÁC NGHIÊN CỨU LIÊN QUAN

gói tin là tối ưu. Tuy nhiên đề xuất này vẫn gặp phải vấn đề mất cân bằng tải khi các nút
trên biên của hình bao lồi chịu tải nhiều hơn. Hơn nữa, việc thể hiện hố bằng bao lồi còn đòi
hỏi phải sử dụng tập hợp các điểm với số lượng lớn và không biết trước, dẫn tới gói tin


- 18 -

quảng bá có dung lượng lớn. Đồng thời, các nút mạng sẽ phải sử dụng bộ nhớ lớn cho việc
lưu trữ thông tin về hố.
Một số đề xuất khác sử dụng các hình cố định để biểu diễn hố như [9] [10] cho phép
đưa lượng thông tin miêu tả hố thành hằng số, đòi hỏi ít bộ nhớ để lưu trữ và cho phép dễ
dàng truyền tải rộng trong mạng. Tuy vậy, việc sử dụng một hình cố định để biểu diễn hố
vẫn không giải quyết triệt để vấn đề mất câng bằng tải. Khi tất cả các nút mạng sử dụng
chung hình xấp xỉ để định tuyến, vô hình chung, hình xấp xỉ này giống như một hố mạng
lớn hơn, các nút mạng trong khu vực biên của hình xấp xỉ phải chịu tải cao hơn so với các
nút thông thường trong mạng.
M. Choi đưa ra một đề xuất sử dụng hình tròn để bao quanh hố [11], thông tin về tọa độ
tâm và bán kính sẽ được gửi tới mỗi nút nguồn. Nút nguồn tìm hình lục giác đều tiếp xúc
ngoài với đường tròn và có một cặp cạnh song song với đường thẳng đi qua nút nguồn và
nút địch. Đề xuất này cho phép mỗi cặp nguồn – đích sử dụng một hình xấp xỉ khác nhau
của hố. Tuy nhiên, vì các hình lục giác cùng nhận một đường tròn cố định duy nhất làm
đường tròn nội tiếp nên đường định tuyến của các gói tin vẫn đi qua khu vực biên đường
tròn này với mật độ lớn hơn so với các khu vực khác.
Trong nghiên cứu này, chúng tôi đề xuất một thuật toán định tuyến vượt hố mới trong
mạng không dây, trong đó sử dụng yếu tố ngẫu nhiên làm tăng tính cấn băng trọng mạng.
Sau khi xác định được hố, nút mạng sẽ xấp xỉ hố thành một đường tròn – gọi là đường tròn
cơ bản và được phát tán thông tin về đường tròn cơ bản, gồm tọa độ tâm và bán kính đường
tròn, tới các nút trong mạng. Tại mỗi nút mạng có thông tin về đường tròn cơ bản, khi gửi
đi 1 gói tin, nút sẽ kiểm tra xem đoạn thẳng nối chính nó với nút đích có cắt với đường tròn
cơ bản không. Nếu có, nút sẽ xấp xỉ hố thành hình lục giác – gọi là hố lục giác – và chọn

bản. Thông tin về đường tròn cơ bản gồm tọa độ tâm và bán kính , sẽ được phát tán tới các nút
trong mạng bằng một gói tin quảng bá. Các nút mạng nhận được gói tin quảng bá sẽ lưu giữ thông tin
về đường tròn cơ bản để phục vụ cho quá trình định tuyến, sau đó tiếp tục phát tán gói tin quảng bá
tới các nút hàng xóm. Kết thúc quá trình định biên, toàn bộ các nút trong mạng có được thông tin về
đường tròn cơ bản.
− Pha định tuyến: khi các nút mạng đã có thông tin về đường tròn cơ bản, mỗi khi gửi đi một gói tin,
nút sẽ kiểm tra xem đoạn thẳng nối bản thân nó với nút đích có cắt qua đường tròn cơ bản hay
không. Nếu có, nó sẽ tính hố lục giác và tạo ra bảng định tuyến gồm tọa độ của nút đích và một hoặc
hai điểm neo là đỉnh của lục giác, theo một thứ tự nhất định. Trong trường hợp ngược lại, bảng định
tuyến sẽ chỉ có tọa độ của nút đích. Bảng định tuyến được gắn vào phần header của gói tin, phục vụ
việc chuyển tiếp gói tin tại các nút trong mạng.

Khi gói tin được chuyển tiếp tại mỗi nút, nút đó sẽ kiểm tra trong bảng định tuyến của
gói tín, lấy được tọa độ của điểm neo đang đứng đầu trong bảng định tuyến – có thể là nút
đích của gói tin hoặc đỉnh của hố lục giác. Nút sẽ gửi gói tin về phía điểm neo này bằng giải
thuật tham lam [13]. Trong trường hợp không có bất kỳ hàng xóm nào ở gần điểm neo hơn
chính nút đó, điểm neo sẽ bị loại ra khỏi bảng định tuyến và nút sẽ gửi gói tin tới điểm neo
tiếp theo trong bảng. Quá trình chuyển tiếp gói tin sẽ thực hiện liên tục cho tới khi gói tin
tới được nút đích.
Trong phần sau đây, chúng tôi sẽ trình bày chi tiết giải thuật cho hai pha: Pha định biên
và pha định tuyến.


- 20 -

4.1 PHA ĐỊNH BIÊN
Pha này có thể chia ra làm 3 bước nhỏ như sau:
-

Bước 1: xác định biên hố.



- 21 -

tâm và bán kính này phục vụ cho quá trình định tuyến, đồng thời quảng bá gói tin này tới
các nút hàng xóm của nó.

Giải thuật 1: xác định đường tròn cơ bản (C, rC)
Input: là nút nằm trên biên hố, n là tổng số nút trên biên.
Output:
Begin
1.
2.
3.
4.
5.
6.
7.
8.

End

Return (


- 22 -

4.2 PHA ĐỊNH TUYẾN
Tại pha này, nút mạng cần gửi gói tin đi sẽ kiểm tra xem gói tin có cần được định tuyến
vượt hố hay không. Nếu có, nút mạng sẽ tính đường định tuyến cho gói tin từ các thông tin

Hình 7: Định tuyên vượt hố lục giác
Sau khi xác định được đường tròn nội tiếp , việc xác định hố lục giác trở thành bài toán
nhỏ: Xác định hình lục giác đều biết tâm và bán kính đường tròn nội tiếp của lục giác đó và
biết rằng hình lục giác cần tìm có một cặp cạnh song song với một đường thẳng cho trước.
Đây là bài toán hình học đơn thuần. Giải thuật 2 trình bày một phương pháp xác định hình
lục giác này dựa trên phép xoay trục tọa độ.
Nhận xét rằng: có hai đường định tuyến vượt qua hố lục giác, đường thứ nhất đi qua
cạnh V1V2 tạo thành đường SV1V2D. Đường thứ hai đi qua cạnh V 4V5 tạo thành đường
SV5V4D. Như vậy, để chọn được đường định tuyến, chỉ cần xác định tọa độ của bốn đỉnh
(Hình 7). Giải thuật 2 không tìm sáu đỉnh của lục giác mà chỉ tìm lần lượt là toạ độ các đỉnh
.
Sau khi có được tọa độ bốn đỉnh , nút S sẽ chọn một trong hai đường SV 1V2D và
SV5V4D để tạo thành đường định tuyến cho gói tin. Việc lựa chọn dựa trên tiêu chí khoảng
cách, S sẽ lựa chọn đường đi có độ dài Euclid nhỏ hơn bằng cách so sánh:

Nếu , bảng định tuyến của gói tin sẽ gồm:

Ngược lại, nếu , bảng định tuyến sẽ gồm:

Khi gói tin được chuyển tiếp đi qua các nút, mỗi nút sẽ sử dụng giải thuật tham lam –
Greedy [13] để gửi gói tin tới hàng xóm gần với điểm neo nhất. Trong trường hợp không có


- 24 -

hàng xóm nào gần hơn chính nó, nút sẽ loại bỏ một điểm neo đó khỏi bảng định tuyến của
gói tin và lặp lại với điểm neo tiếp theo (Hình 7).

Giải thuật 2: Xác định hố lục giác
Input: , ,

Độ dài đường đi của gói tin được đánh giá qua chỉ số Stretch – chỉ số cho biết tỷ lệ giữa
độ dài đường đi thực tế khi áp dụng giải thuật định tuyến, so với độ dài đường đi ngắn nhất
có thể tìm được:

Trong đó:
−
−

: độ dài đường đi thực tế của gói tin khi áp dụng thuật toán định tuyến.
: độ dài đường đi ngắn nhất có thể tìm được.

Chỉ số Stretch phản ánh việc áp dụng một thuật toán định tuyến nào đó sẽ khiên cho
đường đi của gói tin bị kéo dài ra bao nhiều lần so với đường đi ngắn nhất có thể tìm được.
Tuy nhiên, Stretch chỉ có thể tính thông qua khảo sát quá trình truyền tin thực tế của cá
gói tin (hoặc mô phỏng truyền tin thực tế). Để dễ dàng hơn trong việc đánh giá mức tăng độ
dài dường đi của gói tin bằng lý thuyết, người ta còn sử dụng một chỉ số khác là E_Stretch.
E_Stretch đánh giá mức tăng của độ dài đường định tuyến của gói tin tìm được khi áp dụng
thuật toán định tuyến đang khảo sát, so với đường định tuyến ngắn nhất có thể tìm được
giữa nút nguồn và nút đích. Đường định tuyến ngắn nhất là đường tìm được khi áp dụng
thuật toán GOAL [7]. Công thức của E_Stretch:

Trong đó:
−

: độ dài đường định tuyến thực tế khi áp dụng giải thuật định tuyến.

−

: độ dài đường định tuyến ngắn nhất có thể tìm được.