繞徑協定是Ad Hoc無線網路中的重要應用，也是被充分研究的議題。地理貪婪遞送是一個被廣泛應用的策略，因為其具有低複雜度和良好的可延展性。但當網路中存在有空洞時，地理貪婪遞送策略會導致空洞的周邊生成壅塞區域並降低網路的生命週期和有效流量。在這篇論文中提出了一個平衡負載的繞過空洞繞徑協定。為了避免壅塞區域的生成，該協定會在網路中建構出一虛擬梯度做為網路拓樸的信息模型，並藉著平衡等高線上的封包流量來達到繞過空洞和平衡負載的效果。模擬結果顯示了該機制不但延長了網路的生命週期還提高了網路的有效流量。

Routing is a well studied topic in multi-hop wireless ad hoc network. Geographic based greedy forwarding is a popular strategy for its scalability and low complexity. However when voids exist in networks greedy forwarding creates congestion area around voids and decreases both network lifetime and throughput. In this thesis, a load balanced antivoid routing protocol is proposed. A virtual gradient over the network is constructed and packet flow will be uniformly distributed among contours to achieve in advance void avoidance and relay load balancing. The simulation result indicates that our protocol achieves longer network lifetime and better trade-off between load balancing and path stretching ratio. When packet generation rate rise the proposed protocol provides higher average throughput. The effectiveness of a density adapted extended version of the proposed protocol is also evaluated.

[1] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, Aug. 2002.
[2] Q. Fang, J. Gao, and L. J. Guibas, “Locating and Bypassing Holes in Sensor Networks,” Mobile Networks and Applications, vol. 11, no. 2, pp. 187–200, Apr. 2006.
[3] B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” in Proceedings of the Annual International Conference on Mobile Computing and Networking, Aug. 2000, pp. 243–254.
[4] S. Subramanian, S. Shakkottai, and P. Gupta, “On Optimal Geographic Routing in Wireless Networks with Holes and Non-Uniform Traffic,” in Proceeding of the IEEE Conference on Computer Communications, May 2007, pp. 1019–1027.
[5] A. Mei and J. Stefa, “Routing in Outer Space: Fair Traffic Load in Multi-Hop Wireless Networks,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing, May 2008, pp. 23–32.
[6] D. Dong, Y. Liu, and X. Liao, “Fine-Grained Boundary Recognition in Wireless Ad Hoc and Sensor Networks by Topological Methods,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing, May 2009, pp. 135–144.
[7] Y. Wang, J. Gao, and J. S. Mitchell, “Boundary Recognition in Sensor Networks by Topological Methods,” in Proceedings of the Annual International Conference on Mobile Computing and Networking, Sept. 2006, pp. 122–133.
[8] A. Kr¨oller, S. P. Fekete, D. Pfisterer, and S. Fischer, “Deterministic Boundary Recognition and Topology Extraction for Large Sensor Networks,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithm, Jan. 2006, pp. 1000–1009.
[9] F. Yu, Y. Choi, S. Park, E. Lee, Y. Tian, and S.-H. Kim, “Virtual Circle Based Geometric Modeling of Holes for Geographic Routing,” in Proceedings of the Wireless Communications and Networking Conference, Mar. 2008, pp. 2426–2431.
[10] F. Yu, S. Park, Y. Tian, M. Jin, and S.-H. Kim, “Efficient Hole Detour Scheme for Geographic Routing in Wireless Sensor Networks,” in Proceedings of the Vehicular Technology Conference, Apr. 2008, pp. 153–157.
[11] F. Yu, E. lee, Y. Choi, S. Park, D. Lee, Y. Tian, and S.-H. Kim, “A Modeling for Hole Problem in Wireless Sensor Networks,” in Proceedings of the InternationalConference on Wireless Communications and Mobile Computing, Aug. 2007, pp. 370–375.
[12] Y. Tian, F. Yu, Y. Choi, S. Park, E. Lee, M. Jin, and S.-H. Kim, “Energy-Efficient Data Dissemination Protocol for Detouring Routing Holes in Wireless Sensor Networks,” in Proceeding of the IEEE International Conference on Communications, May 2008, pp. 2322–2326.
[13] M. Aissani, A. Mellouk, N. Badache, and M. Djebbar, “A New Approach of Announcement and Avoiding Routing Voids in Wireless Sensor Networks,” in Proceeding of the IEEE Global Telecommunications Conference, Nov. 2008, pp. 1–5.
[14] W.-J. Liu and K.-T. Feng, “Greedy Routing with Anti-Void Traversal for Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 8, no. 7, pp. 910– 922, July 2009.
[15] Z. Jiang, J. Ma, W. Lou, and J. Wu, “An Information Model for Geographic Greedy Forwarding in Wireless Ad-Hoc Sensor Networks,” in Proceeding of the IEEE Conference on Computer Communications, Apr. 2008, pp. 825 –833.
[16] S. Subramanian, S. Shakkottai, and P. Gupta, “Optimal Geographic Routing for Wireless Networks with Near-Arbitrary Holes and Traffic,” in Proceeding of the IEEE Conference on Computer Communications, Apr. 2008, pp. 1328–1336.
[17] “The Network Simulator – ns-2,” http://www.isi.edu/nsnam/ns/, 2010.