B

TR N G

GIÁO D C VÀ À O T O

I

H C BÁCH KHOA HÀ N I

______________________________

BÁO CÁO CHUYÊN
Tên

tài:

Xây d n g công c mô ph n g các thu t toán
n h tuy n m n g không dây n g d n g nghiên c u
kh c ph c h m ng trong môi tr g a hình ph c
tp
S N PH M : Báo cáo k thu t cung c p gi i pháp
và kh o sát th c nghi m trên c s cài t gi l p .
-----------------------------------------N i dung 6: n g d n g m n g c m bi n
kh o sát
xác n h vùng b thiên tai n n g thông qua vi c nhanh
chóng xác n h h m n g: nghiên c u
xu t thu t toán
xác n h nhanh h kích th c l n trong i u ki n a
hình liên t c bi n n g ; á nh giá qua th c nghi m mô
ph n g .

2.2. Biểu diễn bitmap.......................................................................................................21
2.3. Thuật toán phát hiện biên hố (HBD).........................................................................22
2.4. Thuật toán cập nhập biên hố......................................................................................24
2.4. Tổng hợp thông tin biên hố.......................................................................................26
CHƯƠNG III. ĐÁNH GIÁ HIỆU NĂNG...........................................................................28
KẾT LUẬN..........................................................................................................................33
TÀI LIỆU THAM KHẢO....................................................................................................33

2


DANH SÁCH HÌNH ẢNH
Hình 1: Đa giác xấp xỉ bằng lưới ô vuông Hình 2: A-vertex................................................9
Hình 1: Đa giác xấp xỉ bằng lưới ô vuông Hình 2: A-vertex................................................9
Hình 3: Minh họa cho bổ đề 3..............................................................................................13
Hình 4: bao phủ - β...............................................................................................................15
Hình 5：Thuật toán tinh giản biên hố xấp xỉ.......................................................................17
Hình 6: Minh họa thuật toán.................................................................................................20
Hình 7: Minh họa về biểu diễn bitmap.................................................................................22
Hình 8: Minh họa thuật toán xác định biên hố.....................................................................23
Hình 9: Ví dụ về cập nhật thông tin biên hố........................................................................25
Hình 10: Vị trí tương đối của I-square.................................................................................26
Hình 11: Minh họa bổ đề 1...................................................................................................27
Hình 12: so sánh độ chênh lệch giữa số lượng nút chết thực sự và số lượng nút chết được
phát hiện bởi thuật toán........................................................................................................31
Hình 13: So sánh tỉ lệ diện tích hình xấp xỉ hố / diện tích hố thực sự..................................32

3



truyền nhận tin trực tiếp từ các nút mạng nằm trong vùng phủ sóng của
nó. Trong trường hợp hai nút mạng nằm ngoài vùng phủ sóng của nhau
mà muốn truyền nhận tin cho nhau thì gói tin sẽ phải được truyền qua
các nút trung gian. Đường truyền của các gói tin được quyết định bởi
các thuật toán định tuyến.
1.1.2. Vấn đề hố mạng
Hố mạng là các vùng trống, không chứa nút mạng, hoặc nút mạng
ở đó không còn khả năng hoạt động. Hố mạng có thể được sinh ra do sự
5


xuất hiện của các chướng ngại vật như sông, núi, ao, hồ; Hoặc do sự
xuất hiện của các phá hủy vật lý như núi lửa, động đất hoặc có thể do
bản thân các nút mạng cạn kiệt năng lượng và trở thành các nút chết.
Chính vì thế, hố mạng thường hay xuất hiện đối với các mạng cảm biến
không dây được triển khai trong địa hình phức tạp. Sự xuất hiện của hố
mạng thường là dấu hiệu của sự có mặt của một chướng ngại vật nào đó
hoặc là sự xuất hiện của một sự kiện nào đó. Ví dụ, sự có mặt của một
con sông hay sự xuất hiện của một đám cháy rừng sẽ sinh ra một hố
mạng. Chính vì vậy, việc xác định biên hố sẽ giúp ta xác định được vị trí
của các hiện tượng đi kèm với sự xuất hiện của hố mạng.
1.2. Tính cấp thiết của bài toán xác định biên hố
Hãy tưởng tượng một kịch bản như sau: Có một khu rừng nhiệt đới rất thường hay
xảy ra cháy rừng vào mùa hè. Bởi vì khu rừng này rất rộng và địa hình hiểm trở nên con
người gần như không thể thâm nhập và theo dõi, dự báo cháy rừng một cách trực tiếp
được. Để dự báo cháy rừng, người ta dùng một máy bay rải xuống khắp rừng một lượng
lớn các cảm biến. Các cảm biến này chỉ gồm 3 module cơ bản: cảm biến nhiệt độ, cảm
biến độ ẩm, truyền tín hiệu. Một trong những mục tiêu đầu tiên là phải làm sao để các gói
tin giữa các nút mạng được truyền đi thông suốt và dữ liệu được thu thập một cách hiệu
quả.

và thuật toán cập nhật biên hố nhanh chóng.

7


CHƯƠNG II. MỘT SỐ NGHIÊN CỨU LIÊN QUAN
2.1. Xấp xỉ hố dựa trên lưới ô vuông
2.2.1. Giới thiệu
Trong bài báo [21] chúng tôi đã đề xuất thuật toán xấp xỉ biên hố dựa trên lưới ô
vuông. Tư tưởng của thuật toán này là làm sao để xấp xỉ hố bằng một đa giác
đơn giản, bao ngoài hố sao cho sai số xấp xỉ cũng như số đỉnh của đa
giac là nhỏ nhất có thể dựa trên lưới ô vuông. Đa giác xấp xỉ của chúng
tôi là một đa giác thỏa m.n các thuộc tính sau:
•

Bao phủ: Đa giác xấp xỉ bao phủ toàn bộ hố

•

Dựa trên lưới ô vuông: Các đỉnh của đa giác xấp xỉ là mắt lưới và
các cạnh của đa giác xấp xỉ nằm trên cạnh của lưới ô vuông. Tính
chất này giúp cho việc biểu diễn thông tin của biên hố trở nên dễ
dàng, đỡ tốn chi phí.

•

Có thể khống chế được sai số xấp xỉ: Số đỉnh của đa giác xấp xỉ
được khống chế bởi cận trên N. Cận trên này là một hằng số được
quy định trước. Cận trên này sẽ quyết định sai số xấp xỉ theo
nghĩa, N càng lớn thì sai số xấp xỉ càng nhỏ và ngược lại.

tính chất như sau:
Định nghĩa 2 Xét đa giác xấp xỉ G với các đỉnh là G0,G1, ..., Gm được sắp
xếp theo chiều kim đồng hồ. Một đỉnh của G được gọi là đỉnh xác định
đa giác (A-vertex) nếu và chỉ nếu nó thỏa mãn ít nhất mổt trong các
tính chất sau:
•

Là đỉnh đầu tiên của một cạnh song song với trục x

•

Tọa độ x và y khác với tọa độ của A-vertex liền trước nó
9


Hình 2 biểu diễn một ví dụ về A-polygon và A-vertex. Trong ví dụ này, G1
được chọn là A-vertex đầu tiên và nó là đỉnh của cạnh đầu tiên song
song với trục x. Vì vậy, G3 là A-vertex tiếp theo bởi vì cả 2 tọa độ x,y của
nó đều khác G1. Tương tự, G5, G7, ...,G2k+1 cũng là A-vertex trong khi G0,
G2, ..., G2k thì không phải là A-vertex. Rõ ràng là tọa độ
của G0, G2, ..., G2k có thể suy ra từ tọa độ của các A-vertex theo công
thức sau:

Trong đó, Gix , Giy tương ứng là ký hiệu tọa độ x,y của Gi .
2.2.3. Mô tả chung về thuật toán
Mục đích của chúng tôi là xây dựng đa giác xấp xỉ G của hố H, giả
sử rằng hố H có các nút trên biên là δH = H0, H1, ..., Hn. Như đã nói ở trên,
trong thuật toán online này cả ba pha thu thập thông tin, xấp xỉ và rút
gọn được thực hiện đồng thời cùng một lúc tại tất cả các nút. Chúng tôi
sử dụng thuật toán xác định hố Boundhole [9] để xác định δH (tức là để

tọa độ của toàn bộ
các đỉnh A-vertex và từ đó sẽ dựng nên đa giác xấp xỉ.
2.2.4. Xấp xỉ các cạnh của biên hố
Theo thuật toán trong [18], toàn bộ hố phải nằm bên phải của véc-tơ PiPi. Từ định nghĩa của A-polyon, đoạn Pi-1Pi sẽ được xấp xỉ bằng đường

1

gấp khúc nối các cạnh của các hình vuông đơn vị cắt đoạn Pi-1Pi nằm bên
trái của véc-tơ Pi-1Pi (hình 3). Bổ đề dưới đây miêu tả điều kiện để một
mắt lưới ô vuông nằm về bên trái của tia Pi-1Pi.
Bổ đề 1. Giả sử G là một đỉnh của h.nh vuông đơn vị cắt đoạn thằng Pi1Pi.

Thế thì G nằm về bên trái của véc-tơ Pi-1Pi nếu và chỉ nếu G là ảnh

của tâm của h.nh vuông đơn vị cắt doạn thằng Pi-1Pi qua phép tịnh tiến
 ∠xPi −1 Pi  π 3π
theo véc-tơ v = (r 2 cos β , r 2 sin β ) . Trong đó, β = 
* +
 π /2  2 4
Bổ đề 2. Giả sử O là tâm của một h.nh vuông đơn vị cắt đường thằng Pi1Pi

và giả sử rằng tọa độ x, y của O lần lượt là mr+r/2 và nr+r/2. Thế thì,

bất đẳng thức sau đây là điều kiện cần và đủ của m và n:

(

)(

)

Đoạn giả code sau đây mô tả chi tiết thuật toán rút gọn biên hố

13


2.3. Xấp xỉ biên hố bằng đa giác lồi động
Trong bài báo [22] chúng tôi đã đề xuất một thuật toán xấp xỉ biên hố bằng đa giác
lồi động, trong chương này chúng tôi sẽ trình bày thuật toán đó.
2.3.1. Mô hình lý thuyết
Chúng tôi giả sử rằng, mạng đang xét có mật độ nút tương đối dày
đặc (ngoại trừ vùng có hố), và với giả thiết này chúng tôi có thể mô hình
hóa đường đi ngắn nhất từ S đến D trong trường hợp S, D nằm về hai
phía của hố H bằng đường gấpkhúc nối S, D và các nút trên biên hố. Hố
H được biểu diễn bằng một đa giác với các đỉnh là các nút mạng trên
biên hố. Để ý rằng số đỉnh của hố H có thể rất lớn và vì vậy, mục đich
của chúng tôi là t.m ra một giải pháp để xấp xỉ hố H bởi một đa giác P
đơn giản hơn (có ít đỉnh hơn) sao cho hệ số đường đi Ơclit (xem định
nghĩa 2.4.1) của P đối với H đủ nhỏ, trong khi vẫn đảm bảo chi phí cho
việc quảng bá và lưu trữ thông tin của hố là không quá lớn.
Trước khi đi vào mô hình lý thuyết, chúng tôi thấy có một số điểm
lưu ý như sau. Trước hết, nếu lấy tiêu chí đảm bảo đường đi ngắn nhất
qua 1 hố H, chúng ta chỉ cần xem xét các đa giác xấp xỉ là đa giác lồi.
Thứ hai, Ngoài tiêu chí đảm bảo đường đi ngắn đa giác xấp xỉ cũng cần
đảm bảo chi phí phát tán và lưu trữ thông tin của nó là nhỏ nhất có thể.
Từ hai tiêu chí này, ta thấy rằng số đỉnh của đa giác xấp xỉ đối với các
nút nguồn ở gần hố nên lớn và số đỉnh của nút nguồn ở xa hố th. nên
nhỏ. Cụ thể hơn, để đảm bảo hệ số đường đi Ơclit không vượt quá một
hằng sốα > 1 cho trước, nút nguồn gần đích sẽ cần sử dụng 　 một đa
giác xấp xỉ chính xác hơn (sai số so với hố nhỏ ) trong khi nút xa đích
hơn th. chỉ cần một đa giác xấp xỉ không quá chính xác (sai số so với hố

Chúng tôi sử dụng các thuật toán [9] để xác định biên hố cũng
như xác định bao lồi của hố. Giả sử rằng, sau khi sử dụng hai thuật toán
trên hố và bao lồi của hố đã được xác định, trong đó bao lồi của hố là đa
giác lồi H với số đỉnh là n. Dựa trên kết quả này chúng tôi sẽ xây dựng
một lược đồ xấp xỉ và phát tán biên hố sao cho thông tin về hố mà mỗi
nút mạng nhận được là vừa đủ để đảm bảo hệ số đường đi Ơclit không
vượt quá hằng sốα định trước. Lược đồ của chúng tôi có thể đảm bảo
được hệ số đường đi Ơclit của tất cả các cặp nguồn-đích không vượt quá
α.Tư tưởng của chúng tôi là xây dựng một d.y các đa giác xấp xỉ của H
15


là P(0)=H, P(1), P(1),..., P(n-3), có số đỉnh lần lượt là n, n-1, ..., 2, 3, đồng thời,
tìm ra một dãy khoảng cách Ơclit g1 < g2 < : : : < gn-3 sao cho điều kiện
sau thỏa mãn: Đối
với một nút bất kỳ ở khoảng cách ít nhất là gi đối với P(i), th. E-stretch
của P(i) đối với H không vượt quá α. Nghĩa là, nếu nút có khoảng cách tới
hố không vượt quá gi thì sẽ sử dụng P(i) làm đa giác xấp xỉ trong định
tuyến, và E-stretch luôn luôn được đảm bảo không vượt quá α.
Tất nhiên là, để tiết kiêm tài nguyên mạng thì muốn gi càng nhỏ
càng tốt. Chúng tôi tin rằng việc tìm ra một dãy P(i)’s và gi tối ưu là một
vấn đề phức tạp và khó giải quyết. Như chúng tôi đã nói ở trên, khi cố
định số đỉnh, thì đa giác xấp xỉ tối ưu ( cho E-stretch nhỏ nhất) nên là đa
giác có chu vi nhỏ nhất. Xác định đa giác có chu vi nhỏ nhất trong số
các đa giác bao ngoài một đa giác cho trước lại cũng là một vấn đề rất
khó trong hình học tính toán và không thích hợp với các đặc tính của
mạng cảm biến không dây. Tuy không tìm được lời giả tối ưu, nhưng ở
đây chúng tôi sẽ đề xuất một giải pháp tương đối tốt, sử dụng kỹ thuật
heuristic đơn giản.
Trước hết, chúng tôi xem xét thuật toán để tinh giản đa giác P ( với

1. Các nút trên biên hố H xác định bao lồi của hố dùng thuật toán mô tả
trong [23].
2. Các nút trên biên hố tính g1 và bắt đầu phát tán thông tin P(0)=H, g0 =
0 và g1 cho các nút bên ngoài hố.
3. Với i=0 đến n-4 : Sau khi nhận được (P(i), gi, gi+1), nút ở khoảng cách
d ∈ [ g i , g i +1 ) từ hố sẽ lưu thông tin của P(i) vào bộ nhớ , trong khi nút ở
khoảng cách gi+1 tính P(i) và gi+2, bằng cách sử dụng thuật toán tinh giản
đa giác xấp xỉ, và tiếp tục phát tán thông tin ra phía xa hố hơn.
Quá trình trên đây sẽ kết thúc khi nút ở khoảng cách gn-3 nhận
được đa giác P(n-3) (là một đa giác). Kết quả phân tích của chúng tôi trong
chương tiếp theo sẽ chỉ ra cách tính gi. Dựa vào quá trình phát tán thông
17


tin đa giác xấp xỉ tr.nh bày trên đây, thuật toán định tuyến sẽ được tiến
hành theo hướng như sau: gói tin xuất phát từ nút nguồn có khoảng
cách đến hố nằm trong khoảng d ∈ [ g i , g i +1 ) , i ≤ n − 4 sẽ sử dụng thông tin
của P(i), trong khi các gói tin xuất phát từ khoảng cách lớn hơn gn-3 sẽ chỉ
đơn giản được truyền đi bằng thuật toán định tuyến tham ăn cho đến khi
nó đến được một nút có thông tin của P(n-3).
2.3.3. Thuật toán cụ thể
Bây giờ chúng tôi sẽ mô tả thuật toán cụ thể . Mục tiêu của chúng tôi là
xây dựng một thuật toán phân tán để xấp xỉ và phát tán thông tin hố
theo phương thức động theo một phương thức hiệu quả sao cho hệ số
của đường định tuyến không vượt quá một hằng sốα> 1 quy định trước.
Nhớ lại rằng, trong chương 2.3.2 chúng tôi đ. xây dựng một dãy các đa
giác P(0)=H, P(1), P(1),..., P(n-3)( số đỉnh của các đa giác này lần lượt là n, n1, ..., 2, 3) bằng cách lặp lại nhiều lần thuật toán tinh giản đa giác một
cách đệ quy với đa giác ban đầu là bao lồi của hố. Từ định l. 2.3.3 chúng
ta có thể thấy rằng, toàn bộ mạng sẽ bị chia thành cách vành đai bởi
các đa giác G ( i ) (1 ≤ i ≤ n − 3) , trong đó các nút mạng nằm trong vùng vành



CHƯƠNG II. ĐỀ XUẤT THUẬT TOÁN XÁC ĐỊNH VÀ CẬP NHẬT BIÊN HỐ
2.1. Tổng quan thuật toán
Tiêu chí quan tr ng nh t c a chúng tôi khi thi t k thu t toán này là làm sao phát
hi n và update thông tin biên h càng nhanh, càng t t. Vì v y, thay vì xác n h chính xác
biên h , chúng tôi h n g t i vi c xác n h hình x p x c a biên h . Hình x p x này c
xác n h b ng m t t p các hình vuông n v c t h .
Chúng tôi cung c p hai thu t toán: thu t toán phát hi n biên h ( c ký hi u là
thu t toán HBD) và thu t toán c p nh t thông tin biên h ( c ký hi u là thu t toán
HBU). Thu t toán HBD c th c hi n b i các nút t c (các nút t c này c phát hi n
thông qua thu t toán TENT [9]).
ý r ng, khi s d ng thu t toán TENT, các nút t c phát
hi n c s luôn n m trên biên c a m t h nào ó nh ng không ph i t t c các nút trên
biên h u là nút t c. Vì v y, ch có m t s l n g nh các nút trên biên h s th c hi n
thu t toán HBD.
Các nút t c s t o ra gói tin HBA (vi t t t c a c m t Hole Boundary
Approximation) và truy n ti p gói tin HBA cho nút lân c n theo quy t c bàn tay ph i ([9])
cho n khi gói tin HBA n
c nút t c ti p theo. G i các nút t c t o ra gói tin HBA là
nút t c ngu n và nút t c mà t i ó gói tin HBA d ng l i là nút t c ích , nh v y m i gói tin
HBA s giúp xác n h o n biên h t nút t c ngu n n nút t c ích. Sau khi nh n c
gói tin HBA, nút t c ích s trích xu t ra thông tin c a o n biên h mà gói tin HBA ã i
qua và g i thông tin này v nút sink g n nh t (nút sink là m t nút m ng c bi t có n ng
l n g r t l n, làm nhi m v trung chuy n thông tin t các nút m ng c m bi n t i tr m i u
khi n trung tâm). Các nút sink s t ng h p thông tin nh n c t t t c các nút c m bi n
khác và g i v tr m i u khi n trung tâm.
Gi s r ng, t c
bi n i c a h di n ra r t nhanh. V y thì, n u chúng ta c p
nh t s thay i c a bi n h sau khi nó s di n ra thì nhi u kh n ng sau khi c p nh t xong,

Bi u di n bitmap c a toàn m ng là m t m ng hai chi u bmp[i][j], trong ó b[i][j] =
1 n u và ch n u ô vuông v i to
tâm là (1/2+i)a, (a/2+j)a c t c suy oán là n m
trong ít nh t m t h m ng.

Hình 7: Minh họa về biểu diễn bitmap

Hình 1 bi u di n m t m ng v i m t h l n. Trong hình này, các ô vuông n v c t
h
c tô xám. i v i ví d này, bi u di n bitmap c a node N1 là ….., bi u di n bitmap
c a o n th ng N1N2 là …. Và bi u di n bitmap c a toàn m ng là …. Trong thu t toán xác
n h o n biên h t nút t c ngu n n nút t c ích c xác n h b i gói tin HBA và c
g i t i nút sink g n nh t b i nút t c ích. Trong thu t toán c p nh t thông tin biên h , khi t
l các nút ch t trong m t ô vuông n v v t quá m t ng n g cho tr c , ô vuông y s
c phán oán là n m trong h . Pivot c a ô vuông c phán oán n m trong h s tính
bi u di n bitmap c a nó và g i cho nút sink g n nh t. Các nút sink s t ng h p các bitmap
nh n c b ng phép XOR và g i cho nút trung tâm. Các nút sink th c hi n vi c g i thong
tin cho trung tâm m t cách n h k . Nút trung tâm s th c hi n t ng h p thong tin bi u
di n bitmap nh n c t t t c các nút sink b ng phép XOR
tìm ra b n
bitmap c a
toàn b m ng.
2.3. Thuật toán phát hiện biên hố (HBD)
T t c các nút s th c hi n quy t c TENT m t cách n h k
xác n h xem mình
có n m trên biên c a m t h nào ó hay không. Nh ng nút phát hi n ra mình là nút t c s
t o m t gói tin HBA và g i gói tin này cho nút lân c n k trái c a nó. Gói tin HBA sau y
s c các nút chuy n ti p cho nút lân c n theo quy t c bàn tay ph i cho n khi nào n
nút m t nút t c khác. Thu t toán chuy n ti p gói tin theo quy t c bàn tay ph i ã c mô
t r t rõ trong bài báo [9], tuy nhiên chúng tôi s m r ng thu t toán này

c chuy n ti p cho n khi n
c nút
Si+1 và gói tin này s ch a thông tin bi u di n bitmap c a o n S iSi+1. Ví d , thông
23


tin bi u di n bitmap ch a trong gói tin

c chuy n t nút S1 n nút S2 s là ...

Sau khi thu t toán k t thúc chúng ta s xác n h c hình x p x c a h (là hình t o
b i các ô vuông c t biên h ho c n m bên trong h ) và các pivot c a các ô vuông
ó. Trong hình này, các ô vuông c t h
c tô màu xám còn các pivot là các i m
màu .
D i ây là o n gi code c a thu t toán c p nh t thông tin bi u di n h trong gói
tin HBA.

2.4. Thuật toán cập nhập biên hố

G i các ô vuông thu c h (t c là các ô vuông c t biên h ho c n m trong
lòng h ) là ô vuông en . Nh v y, sau khi k t thúc thu t toán xác n h biên h , m i
ô vuông en s có m t pivot. Các nút m ng trong các ô vuông en s n h k g i
gói tin thông báo tr ng thái n cho pivot. Gói tin này s giúp cho pivot bi t c
nút m ng nào còn s ng, nút m ng nào ã ch t. Khi t l các nút m ng ch t trong m t
ô vuông en v t quá m t ng n g cho tr c (g i là ng n g T 1) thì pivot c a ô
vuông en này s g i m t gói tin c nh báo n cho các ô vuông lân c n c a nó. Gói
tin này có ý ngh a báo cho các ô vuông lân c n (ô vuông có chung m t c nh ) bi t
r ng h có kh n ng cao s m r ng t i v trí c a chúng. Các ô vuông lân c n nh n
c gói tin c nh báo này s

ph i và sau m t th i gian m t s nút m ng trong ô vuông 6 b ch t. Khi s l n g
các nút ch t v t quá gi i h n cho phép T 1, nút pivot P6 s g i gói tin c nh báo cho
25