Nghiên cứu định tuyến đơn phát dựa trên thông tin vị trí cho mạng cảm biển không dây

Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 
13 
NGHIÊN CỨU ĐỊNH TUYẾN ĐƠN PHÁT DỰA TRÊN THÔNG TIN VỊ TRÍ 
CHO MẠNG CẢM BIỂN KHÔNG DÂY 
Vũ Văn Diện*, Nguyễn Thị Hiền 
Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên 
TÓM TẮT 
Định tuyến dựa trên thông tin vị trí đã thay thế định tuyến dựa trên topo trong mạng cảm biến 
không dây. Kỹ thuật chuyển tiếp tham lam đã được sử dụng rất hiệu quả để chuyển tiếp gói tin từ 
nguồn đến đích. Tuy nhiên, kiểu chuyển tiếp này có nhược điểm là dễ gặp thất bại khi gặp vùng 
trống. Khi đó, nó sẽ sử dụng định tuyến khôi phục trên đồ thị phẳng để đưa gói tin qua vùng 
trống. Trong bài báo này, nhóm tác giả sử dụng hai đồ thị phẳng là RNG (Relative Neighbor 
Graph) và GG (Gabriel Graph) trong định tuyến khôi phục. Qua mô phỏng, đánh giá định tuyến 
khôi phục trên đồ thị phẳng RNG và GG, nhóm tác giả đã thấy được định tuyến khôi phục trên đồ 
thị RNG cho kết quả tốt hơn xét về tỉ lệ phân phối gói tin thành công từ nguồn đến đích, chi phí 
giao thức định tuyến được sử dụng. 
Từ khóa: Mạng cảm biến không dây, định tuyến, chuyển tiếp, khôi phục, đồ thị phẳng 
GIỚI THIỆU* 
Các phương pháp định tuyến dựa trên topo 
yêu cầu các nút này phải lưu trữ nhiều thông 
tin về các đường định tuyến. Yêu cầu này 
vượt ngoài khả năng đáp ứng của các nút cảm 
biến. Ngoài ra, định tuyến dựa trên topo sử 
dụng nhiều gói tin điều khiển để tìm và duy 
trì các đường định tuyến. Ngoài tác động làm 
giảm băng thông sẵn có cho dữ liệu, nhiều gói 
tin điều khiển tiêu hao nhiều điện năng của 
các nút và hệ quả là làm giảm tuổi thọ của các 
nút. Với đặc điểm như phân tích ở trên, định 
tuyến dựa trên topo hầu như không áp dụng 
cho mạng cảm biến. 
Trong những năm gần đây, một cách tiếp cận 
hoàn toàn khác cho vấn đề định tuyến cho 
mạng cảm biến không dây là sử dụng thông 
tin về vị trí của các nút làm thông tin dẫn 
đường. Tiếp cận mới này có tên là định tuyến 
dựa trên thông tin vị trí. Định tuyến này giả 
thiết mỗi nút biết về vị trí của nó bằng việc sử 
dụng hệ thống định vị như GPS. Ngoài ra, 
định tuyến cần sử dụng một dịch vụ khác, 
được gọi là dịch vụ thông tin vị trí, để xác 
định vị trí của nút đích. Trước khi thực hiện 
giao thức định tuyến, nút nguồn xác định vị 
trí của nút đích thông qua việc gọi dịch vụ 
*
 Tel: 0977 680685, Email: vvdien@ictu.edu.vn 
thông tin vị trí. Sau đó, thông tin về vị trí của 
nút đích được gắn vào mỗi gói tin cần chuyển 
đi và được sử dụng làm thông tin dẫn đường. 
Trong định tuyến dựa trên thông tin vị trí, 
chuyển tiếp tham lam thường được sử dụng vì 
tính đơn giản và hiệu qủa của nó. Tuy nhiên, 
dạng chuyển tiếp này lại gặp thất bại khi xuất 
hiện vùng trống. Khi đó, kỹ thuật khôi phục 
sẽ được sử dụng để đưa gói tin thoát khỏi 
vùng trống sử dụng đồ thị phẳng. Hai đồ thị 
phẳng được sử dụng ở đây là đồ thị RNG và 
GG, qua mô phỏng sẽ đánh giá được định 
tuyến trên đồ thị phẳng nào là tốt hơn. 
Phần II của bài báo trình bày tổng quan về 
định tuyến dựa trên thông tin vị trí. Phần III 
trình bày về các kỹ thuật chuyển tiếp dựa trên 
thông tin vị trí. Định tuyến khôi phục trên đồ 
thị phẳng được trình bày trong phần IV. Phần 
V là kết quả mộ phỏng và đánh giá. Phần VI 
là kết luận. 
ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN 
VỊ TRÍ 
Định tuyến dựa trên thông tin vị trí sử dụng 
kết hợp chuyển tiếp dựa trên thông tin vị trí 
và kỹ thuật khôi phục để định tuyến gói tin. 
Chuyển tiếp dựa trên thông tin vị trí là kỹ 
thuật chuyển gói tin từ nút này đến nút khác 
gần đích hơn. Độ gần đích của một nút có thể 
đo bằng khoảng cách từ nút đó đến nút đích. 
Nitro PDF Software
100 Portable Document Lane
Wonderland
Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 
14 
Nút không có láng giềng gần đích hơn được 
gọi là cực tiểu địa phương (local minima). Để 
mỗi nút nhận được gói tin biết nên sử dụng 
chuyển tiếp dựa trên thông tin vị trí hay kỹ 
thuật khôi phục cho gói tin nhận được, thông 
tin chỉ dẫn được ghi trong tiêu đề của gói tin 
và được gọi là chế độ (mode) định tuyến của 
gói tin. Nút nguồn thiết lập chế độ tham lam, 
hay chế độ sử dụng chuyển tiếp dựa trên 
thông tin vị trí, cho gói tin. Khi nhận được gói 
tin ở chế độ tham lam, nút không có láng 
giềng gần đích hơn nó sẽ thay đổi gói tin sang 
chế độ khôi phục, hay chế độ sử dụng kỹ 
thuật khôi phục, đồng thời ghi thông tin về vị 
trí của nó vào tiêu đề gói tin ở trường nút 
không có láng giềng gần đích hơn gặp cuối 
cùng. Khi nhận được gói tin ở chế độ khôi 
phục, nút gần đích hơn cực tiểu địa phương 
gặp cuối cùng khôi phục gói tin về chế độ 
tham lam. Ở những tình huống còn lại, nút 
nhận được gói tin không thay đổi chế độ định 
tuyến của gói tin và chỉ chuyển tiếp gói tin 
bằng việc áp dụng chuyển tiếp dựa trên thông 
tin vị trí hay kỹ thuật khôi phục tùy theo chế 
độ định tuyến hiện tại của gói tin. Hành vi của 
các nút trong định tuyến dựa trên thông tin vị 
trí được mô tả trong Bảng 1. 
Các kỹ thuật chuyển tiếp dựa trên thông tin vị 
trí sẽ được trình bày trong phần tiếp theo. 
BẢNG 1. HÀNH VI CỦA MỖI NÚT CẢM 
BIẾN TRONG ĐỊNH TUYẾN DỰA TRÊN 
THÔNG TIN VỊ TRÍ 
------------------------------------------------------- 
PROCEDURE Xử_lý_gói_tin 
1: Nếu x là nút đích của gói tin, 
 1.1: Chuyển gói tin lên tầng trên (giao vận) 
2: Ngược lại, tôi không phải là nút đích của 
gói tin, 
 2.1: Nếu gói tin đang ở chế độ tham lam, 
 2.1.1: Sử dụng chuyển tiếp dựa trên thông 
tin vị trí (GF) để chuyển gói tin 
2.1.1.1: Nếu chọn được láng giềng để 
chuyển gói tin theo GF, chuyển gói tin cho 
láng giềng được chọn 
2.1.1.2: Nếu không chọn được láng 
giềng để 
chuyển gói tin theo GF, thì: 
 Đặt gói tin về chế độ khôi phục và 
 áp dụng kỹ thuật khôi phục để chuyển 
gói tin. 
Nếu áp dụng kỹ thuật khôi phục không 
thành 
công thì loại bỏ gói tin. 
2.2: Ngược lại, gói tin đang ở chế độ khôi 
phục, 
 2.2.1: Nếu có thể đưa gói tin về chế độ tham 
lam, 
 thì chuyển gói tin về chế độ tham 
lam rồi 
quay lại bước 2.1.1. 
 2.2.2: Ngược lại, không thể đưa gói tin về 
chế độ tham lam, áp dụng kỹ thuật khôi phục 
để chuyển gói tin. Nếu áp dụng kỹ thuật khôi 
phục không thành công thì loại bỏ gói tin. 
------------------------------------------------------- 
CHUYỂN TIẾP DỰA TRÊN THÔNG TIN 
VỊ TRÍ 
Chuyển tiếp theo khoảng cách/tham lam 
Kỹ thuật chuyển tiếp dựa trên thông tin vị trí 
được sử dụng rộng rãi nhất, vì tính đơn giản 
của nó, kỹ thuật này là chuyển tiếp tham lam 
(greedy forwarding) hay chuyển tiếp theo 
khoảng cách [1]. Trong chuyển tiếp này, 
khoảng cách đến đích được sử dụng làm 
độ đo khi lựa chọn nút kế tiếp. Cụ thể, nút 
hiện tại chọn láng giềng gần đích nhất và gần 
đích hơn nó làm nút kế tiếp. Rất nhiều giao 
thức được đề xuất sử dụng chuyển tiếp 
tham lam [2, 3, 4]. Chuyển tiếp tham lam 
có ưu điểm là đơn giản, hiệu quả và không 
tạo vòng lặp định tuyến nhưng có yếu điểm là 
dễ thất bại khi gặp các vùng trống [9], do 
nút hết năng lượng, thiên tai, lũ lụt,... Nếu 
chuyển tiếp tham lam được sử dụng thành 
công bởi tất cả các nút trên đường định 
tuyến từ nguồn đến đích, đường định tuyến sẽ 
gần với đường tối ưu. 
Nitro PDF Software
100 Portable Document Lane
Wonderland
Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 
15 
Hình 1. Ví dụ về chuyển tiếp tham lam, y là nút 
láng giềng gần nút đích D nhất 
Hình 2. Chuyển tiếp tham lam bị lỗi, khi không có 
láng giềng nào của x gần D hơn nó 
Chuyển tiếp theo góc 
Chuyển tiếp theo góc (compass forwarding) 
[5, 6, 7] cũng yêu cầu thông tin vị trí của 
các láng giềng và nút đích như chuyển 
tiếp tham lam nhưng sử dụng góc được 
tạo bởi hai véctơ, một từ nút hiện tại đến 
đích và một từ nút hiện tại đến láng giềng, 
làm độ đo. Láng giềng có góc bé nhất sẽ được 
chọn làm nút kế tiếp. So với chuyển tiếp tham 
lam, chuyển tiếp theo góc ít thất bại do cực 
tiểu địa phương nhưng có thể tạo ra vòng lặp 
định tuyến. Sự khác biệt này có được do 
chuyển tiếp theo góc không ràng buộc nút 
kế tiếp phải gần đích hơn. Chuyển tiếp 
theo góc chỉ thất bại khi nút hiện tại không 
có láng giềng nào. Khi nút hiện tại không có 
láng giềng gần đích hơn, gói tin được tạm 
thời đẩy xa đích. Sau đó, khi gói tin được 
chuyển tiếp gần đích hơn, vòng lặp định tuyến 
có thể được tạo ra. 
Chuyển tiếp theo bước tiến 
Chuyển tiếp theo bước tiến (progress 
forwarding) [8] sử dụng độ đo là độ dài hình 
chiếu của đoạn thẳng nối nút hiện tại đến láng 
giềng lên đường thẳng đi qua nút hiện tại và 
nút đích. Láng giềng gần đích hơn và có độ 
đo lớn nhất được chọn làm nút kế tiếp. 
Hình 3. Ví dụ về chuyển tiếp theo góc, gói tin từ v 
được chuyển đến u 
ĐỊNH TUYẾN KHÔI PHỤC TRÊN ĐỒ THỊ 
PHẲNG 
Định tuyến khôi phục 
Chuyển tiếp tham lam thường hay được sử 
dụng để đưa gói tin từ nguồn đến đích. Tuy 
nhiên, khi xuất hiện vùng trống (rất hay xuất 
hiện trong mạng cảm biến) thì kiểu chuyển 
tiếp này hay gặp thất bại khi không có nút 
láng giềng nào gần đích hơn nút hiện tại. 
Trong trường hợp như vậy, ta sẽ sử dụng định 
tuyến khôi phục để đưa gói tin thoát khỏi 
vùng trống dựa trên đồ thị phẳng sử dụng quy 
tắc bàn tay phải. 
Hình 4: Quy tắc bàn tay phải, x nhận gói tin từ y, 
và chuyển tiếp nó đến nút láng giềng đầu tiên theo 
ngược chiều kim đồng hồ, z 
Nếu gói tin đến được một nút mà nó gần đích 
hơn nút cực tiểu địa phương thì sẽ khôi phục 
chế độ chuyển tiếp tham lam từ nút này. 
Ngược lại, gói tin vẫn sẽ được chuyển tiếp 
theo quy tắc bàn tay phải trên đồ thị phẳng. 
Các đồ thị phẳng 
Một đồ thị mà không có hai cạnh giao nhau 
được gọi là đồ thị phẳng . Một tập các nút với 
Nitro PDF Software
100 Portable Document Lane
Wonderland
Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 
16 
sóng vô tuyến, ở đó các phạm vi sóng vô 
tuyến là giống nhau (là r), có thể xem như là 
một đồ thị: mỗi nút là một đỉnh, và cạnh (n; 
m) tồn tại giữa các nút n và m nếu khoảng 
cách giữa n và m, rmnd ),( 
Đồ thị RNG (Relative Neighbor Graph) và 
GG (Gabriel Graph) [4] là hai đồ thị phẳng đã 
được biết đến từ lâu. 
Đồ thị RNG được định nghĩa như sau: 
Cho một tập các đỉnh, cạnh (u, v) tồn tại giữa 
đỉnh u và v nếu khoảng cách giữa chúng nhỏ 
hơn hoặc bằng khoảng cách giữa một điểm w 
bất kỳ (khác u, v) đến u hoặc đến v: 
 ),(),,(max),(:, wvdwudvudvuw  
Hình 5. Cạnh uv là cạnh của RNG khi giao 2 
đường tròn tâm u và v phải không chứa w 
Quá trình xây dựng đồ thị RNG từ đồ thị chưa 
phải là RNG thực hiện bằng cách loại bỏ các 
cạnh như sau: 
 For tất cả đỉnh v thuộc tập láng giềng N do 
 For tất cả đỉnh w thuộc N do 
 if w = = v then continue 
 else if d(u,v) > max[d(u,w), d(v,w)] 
then 
 loại bỏ cạnh (u,v) 
 break 
 endif 
 end for 
 end for 
Đồ thị GG được định nghĩa như sau: 
Một cạnh (u, v) tồn tại giữa u và v nếu không 
có đỉnh w nào khác trong vòng tròn nhận uv 
làm đường kính. Ta có công thức sau: 
 wvdwudvudvuw ,,),(:, 222  
Hình 6: Cạnh uv thuộc GG khi đường tròn đường 
kính uv phải không chứa w 
Quá trình xây dựng đồ thị GG từ đồ thị chưa 
phải là GG thực hiện bằng cách loại bỏ các 
cạnh như sau: 
m = trung điểm của uv 
for tất cả đỉnh v thuộc tập các láng giềng N 
do 
 for tất cả w thuộc N do 
 if w = = v then continue 
 else if d(m,w) < d(u, m) then 
 loại bỏ cạnh (u, v) 
 end if 
 end for 
end for 
KẾT QUẢ MÔ PHỎNG VÀ ĐÁNH GIÁ 
Môi trường mô phỏng 
Nhóm tác giả mô phỏng định tuyến khôi phục 
trên đồ thị phẳng RNG và GG sử dụng phần 
mềm mô phỏng ns-2 . Giao thức định tuyến 
sử dụng là GPSR [4]. Môi trường mô phỏng 
được thực hiện với 100 nút mạng trên vùng 
1000 x 500. 
Tỉ lệ phân phối gói tin thành công 
Tỉ lệ phân phối gói tin thành công được xác 
định bằng tỉ số giữa số gói tin nhận được chia 
cho số gói tin gửi đi. 
Kết quả mô phỏng được chỉ ra như trong hình 
7 sau: 
 Hình 7: Tỉ lệ phân phối gói tin thành công 
Nitro PDF Software
100 Portable Document Lane
Wonderland
Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 
17 
Khi định khôi phục sử dụng đồ thị RNG cho 
tỉ lệ phân phối gói tin thành công cao hơn so 
với đồ thị GG. 
Chi phí định tuyến 
Hình 8 chỉ ra chi phí của giao thức định 
tuyến, được đo bằng số gói tin được gửi đi 
trên toàn mạng. 
Hình 8: Chi phí giao thức định tuyến 
Khi định tuyến khôi phục sử dụng đồ thị 
RNG sẽ có chi phí giảm đi so với việc sử 
dụng đồ thị GG. 
KẾT LUẬN 
Báo cáo đã trình bày về định tuyến khôi 
phục dựa trên đồ thị phẳng trong định tuyến 
dựa trên thông tin vị trí. Qua mô phỏng, đánh 
giá ta thấy được được rằng định tuyến khôi 
phục trên đồ thị RNG giảm thiểu được chi 
phí so với GG mà lại cho tỉ lệ phân phối gói 
tin thành công tốt hơn GG, làm cơ sở để lựa 
chọn đồ thị phẳng khi định tuyến khôi phục 
đưa gói tin thoát khỏi vùng trống và cùng với 
chuyển tiếp tham lam đưa gói tin đến đích 
thành công. 
TÀI LIỆU THAM KHẢO 
1. G. G. Finn, “Routing and addressing 
problems in large metropolitan-scale 
internetwork,” Tech. Rep. ISI/RR-87-
180,Information Sciences Institute, Mar. 1987. 
2. P. Bose, P. Morin, I. Stojmenovic, and J. 
Urrutia, “Routing with guaranteed delivery in 
ad hoc wireless networks,” Wireless Networks, 
7(6):609-616, 2001. 
3. Q. Fang, J. Gao, and L. Guibas, “Locating and 
bypassing routing holes in sensor networks,” 
Mobile Networks and Applications, 11(2): 187- 
200, April 2006. 
4 B. Karp and H.T. Kung, “GPSR: Greedy 
perimeter stateless routing for wireless sensor 
networks,” Proc. of Mobicom, pp. 243-254, 2000. 
5. P. Bose, P. Morin, “Online routing in 
triangulations,” Proc. of 10th International 
Symposium on Algorithms and Computation, pp. 
113-122, 1999. 
6. P. Bose, A. Brodnik, S. Carlsson, E. D. 
Demaine, R. Fleischer, A. Lopez-Ortiz, P. 
Morin, J. I. Munro, “Online routing in convex 
subdivisions,” International Symposium on 
Algorithms and Computation, pp. 47-59, 2000. 
7. E. Kranakis, H Singh, and J. Urrutia, 
“Compass routing on geometric networks,” 
Proc. of the 11th Canadian Conference on 
Computational Geometry, pp. 51-54, 1989. 
8. I. Stojmenovic, X. Lin, “Loop-free hybrid 
single-path/flooding routing algorithms with 
guaranteed delivery for wireless networks,” IEEE 
Trans. on Parallel and Distributed Systems, vol. 
12, pp. 1023-1032, Oct. 2001. 
9. B. Karp, “Challenges in geographic routing: 
Sparse networks, obstacles, and traffic 
provisioning,” DIMACS Workshop on Pervasive 
Networking, Piscataway, NJ, May 2001.
Nitro PDF Software
100 Portable Document Lane
Wonderland
Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 
18 
SUMMARY 
RECOVERY ROUTING BASED ON PLANAR GRAPH IN GEOGRAPHIC 
ROUTING FOR WIRELESS SENSOR NETWORK 
Vu Van Dien
*
, Nguyen Thi Hien 
College of Information and Communication Technology - TNU 
Routing based on location information have alternatived the routing based on topology in wireless 
sensor networks. Greedy forwarding technique has been used very effectively to forward packets 
from source to destination. However, the drawback of this type of forwading is easy to fail to 
meet holes. As such, it will use recovery routing on planar graphs to put packets through the 
holes. In this paper, we use two planar graph, RNG (Relative Neighbor Graph) and GG (Gabriel 
Graph) in the recovery routing. Through simulation, evaluating about recovery routing on planar 
graphs RNG and GG, we saw the recovery routing on graph RNG for better results in terms of the 
percentage distribution of packets from source to destination successfully, cost of routing protocol 
used. 
Key: Wireless sensor network, routing, forwarding, recovery, planar graph 
Ngày nhận bài:31/10/2014; Ngày phản biện:28/11/2014; Ngày duyệt đăng: 31/5/2015 
Phản biện khoa học: TS. Đào Huy Du – Trường Đại học Kỹ thuật Công nghiệp - ĐHTN
*
 Tel: 0977 680685, Email: vvdien@ictu.edu.vn 
Nitro PDF Software
100 Portable Document Lane
Wonderland