臺灣博碩士論文加值系統

在無線感測網路中，多數協定選擇貪婪式前進策略做為封包路由。通訊無效
是在訊息傳送時最不能容忍的事件，通訊無效是貪婪式前進策略無法將封包
向終點往前傳送。為了克服通訊無效的問題，無效處理技術已經引起很多關
注。許多貪婪式前進策略和無效處理技術已經被提出。本篇論文的主要貢獻
是提供三個常被使用的貪婪式前進策略和四個無效處理技術的概觀，以及提
供上述方法的12 種組合的比較。

In wireless sensor networks, most protocols choose greedy forwarding strategies
to route the messages. Communication voids are the most intolerable events that
occur at the time of transmission and a communication void is where greedy for-
warding fails to forward a packet further towards its destination. To overcome the
problem of communication voids,void handling techniques have attracted a lot of
attention. Many greedy forwarding strategies and void handling techniques have
been proposed. The main contribution of this thesis is to present an overview of
three commonly used greedy forwarding strategies (Most Forward Routing, Com-
pass Routing, and Ellipsoid Routing) and four void handling techniques (Face-2,
Request-Response, Cost-based forwarding, and Distance Upgrading Algorithm) and
to provide a comparison between the 12 combinations of the above approaches.

Abstract (in Chinese) i
Abstract (in English) ii
List of Figures vi
List of Tables vi
1 Introduction 1
2 Related Works 4
2.1 Greedy Forwarding Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Void handling techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Face-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Request-Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.3 Cost-based forwarding . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.4 Distance Upgrading Algorithm . . . . . . . . . . . . . . . . . . . . . 10
3 The comparisons 13
3.1 Simulation environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Concluding remarks 21

[1] S. Ansari, L. Narayanan and J. Opatrny, A generalization of the face routing al-
gorithm to a class of non-planar networks, in: The Second Annual International
Conference on Mobile and Ubiquitous Systems: Networking and Services (2005)
213-224.
[2] P. Bose, P. Morin, I. Stojmenovic and J. Urrutia, Routing with guaranteed delivery
in ad hoc wireless networks, Wireless networks 7 (6) (2001) 609-616.
[3] S.G. Chen, G.B. Fan and J.H. Cui, Avoid `void' in geographic routing for data
aggregation in sensor networks, International Journal of Ad Hoc and Ubiquitous
Computing 1 (4) (2006) 169-178.
[4] D. Chen and P.K. Varshney, A survey of void handling techniques for geographic
routing in wireless networks, IEEE Communications Surveys and Tutorials 9 (2007)
50-67.
[5] S. Datta, I. Stojenovic and J. Wu, Internal node and shortcut based routing with
guaranteed delivery in wireless networks, Cluster computing 5 (2) (2002) 169-178.
[6] T. Fevens, A.E. Abdallah and B.N. Bennani, Randomized AB-Face-AB routing
algorithms in mobile ad hoc networks, Ad-Hoc, Mobile, and Wireless Networks
(2005) 43-56.
[7] T.C. Hou and V.O.K. Li, Transmission range control in multihop packet radio net-
works, IEEE Transactions on Communications 34 (1986).
[8] M. Mauve, A. Widmer and H. Hartenstein, A survey on position-based routing in
mobile ad hoc networks, IEEE Network: The Magazine of Global Internetworking
15 (2001) 30-39.
[9] H. Frey and I. Stojmenovic, On delivery guarantees of face and combined greedy-
face routing in ad hoc and sensor networks, in: Proceedings of the 12th Annual
International Conference on Mobile Computing and Networking (2006) 390-401.
[10] E. Kranakis, H. Singh and J. Urrutia, Compass routing on geometric networks, in:
Proceedings of the 11th Canadian Conference on Computational Geometry (1999).
[11] H. Marc, T. Braun, T. Bernoulli and M. Wlchli, BLR: beacon-less routing algorithm
for mobile ad hoc networks, Computer Communications 27 (11) (2004) 1076-1086.
[12] R. Nelson and L. Kleinrock, The spatial capacity of a slotted ALOHA multihop
packet radio network with capture, IEEE Transactions on Communications 32
(1984).
[13] W. Si and A.Y. Zomaya, Ellipse and arc routing algorithms for delaunay tringula-
tions, School of Information Technologies (2009).
[14] I. Stojmenvoic, M. Russell and B. Vukojevic, Depth rst search and location based
localized routing and QoS routing in wireless networks, Computers and Informatics
21 (2) (2002) 149-65.
[15] H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed
packet radio terminals, IEEE Transactions on Communications 32 (1984).
[16] C.L. Yuan and C.Y. Chen, On the study of position-based routing algorithms for
wireless ad hoc networks, Masters Thesis, National Chiao Tung University, Taiwan
(2012).
[17] K. Yamazaki and K. Sezaki, A proposal of geographical routing protocols for
location-aware services, Electronics and Communications in Japan 87 (4) (2004).
[18] L. Zou, M. Lu and Z.X. Xiong, PAGER-M: A novel location-based routing protocol
for mobile sensor networks, in: Proceedings of Broadwise (2004).