當無線感測網路中有一片區域裡面沒有足夠數量的可用感測器節點，我們稱之為一個空洞。當無線感測網路中存在一個空洞的時候，經常使得傳統的地理路由演算法窒礙難行。在許多先前的研究中，他們將資料封包以固定的路徑沿著空洞的邊緣傳遞以解決這個問題，這種方式導致在固定路徑上的感測器節點的能量被快速地消耗殆盡而擴大了空洞的面積。
在本論文中，我們提出了一個方法建構能量感知之多路徑以繞過無線感測網路中之空洞。相較於許多先前的研究，我們不僅考慮到使用較短的資料傳遞路徑繞過空洞，更注重於如何減輕位於空洞邊緣的感測器節點的負載。模擬實驗結果顯示我們提出的方法可以有效縮短路由路徑的長度，減少能量消耗，以及增進無線感測網路的負載平衡。

When a hole (the region without enough available sensor nodes) exists in the wireless sensor network, it often causes traditional geographic routing algorithms to fail. In most previous works, the routing hole problem is addressed by using the static detour path to route data packets along the boundaries of holes. It leads to the energy of sensor nodes on the static path depletes quickly, and result in the hole size will be enlarged.
In this paper, we propose a scheme for bypassing holes in wireless sensor networks by energy aware multiple paths. With the difference between previous works, our approach not only takes into account of using the shorter path to bypass the hole, but also more attention to ease the loading of the sensor nodes on the boundaries of holes. Simulation results show that the proposed scheme can achieve short detour paths, low energy consumption and network load balancing.

[1] B. Warneke, M. Last, B. Liebowitz, K. S. J. Pister, “Smart Dust: Communicating with a Cubic-Millimeter Computer,” Computer Magazine, Vol. 34, No. 1, pp 44-51, Jan. 2001.
[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine,” vol. 40, pp. 102–114, 2002.
[3] Tiwari, Ankit et. al, “Energy-efficient wireless sensor network design and implementation for condition-based maintenance,” ACM Transactions on Sensor Networks (TOSN) Volume 3, Issue 1, 2007.
[4] M.T. Ha, T.D. Le, and H. Choo, “Employing a Novel Two Tiered Network Structure to Extend the Lifetime of WSNs,” Proc. WCNC’09, pp. 1–6, 2009.
[5] K. Akkaya and M. Younis, “A survey of routing protocols for wireless sensor networks,” Elsevier Ad Hoc Network Journal, Vol. 3/3, pp. 325-349, 2005.
[6] F. Zhao and L. Guibas, “Wireless Sensor Networks, an Information Processing Approach,” Elsevier, 2004.
[7] H. Karl and A. Willig, “Protocols and Architectures for Wireless Sensor Networks,” Wiley, 2005.
[8] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less low cost outdoor localization for very small devices,” IEEE Personal Communications Magazine, 7(5), 2000.
[9] A. Carus, A. Urpi, S. Chessa, and S. De, “GPS-free coordinate assignment and routing in wireless sensor networks,” in Proc. 24th Annu. Joint Conf. IEEE Comput. Commun. Soc. (INFOCOM ’05), 2005.
[10] J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris, “A scalable location service for geographic ad-hoc routing,” In Proceedings of Mobicom, 2000.
[11] A. Rao, C. Papadimitriou, S. Shenker, and I. Stoica, “Geographic routing without location information,” In Proc. of Mobicom, 2003.
[12] R. Fonseca, S. Ratnasamy, D. Culler, S. Shenker, and I. Stoica, “Beacon vector routing: Scalable point-to-point in wireless sensornets,” Intel Research, IRB-TR-04, vol. 12, 2004.
[13] N. Ahmed, S. S. Kanhere and S. Jha, “The holes problem in wireless sensor networks: a survey,” ACM SIGMOBILE Mobile Computing and Communications, Volume 9, Issue 2, 2005.
[14] I. F. Khan and M. Y. Javed, “A Survey on Routing Protocols and Challenge of Holes in Wireless Sensor Networks,” Advanced Computer Theory and Engineering, 2008.
[15] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, “Routing with guaranteed delivery in ad hoc wireless networks,” In Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM'99), 1999, pp.48-55.
[16] B. Karp, H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” In Proc. of the 6th Annual ACM/IEEE Int'l Conf. on Mobile Computing and Networking, 2000, pp.243-254.
[17] Q. Fang, J. Gao, and L. J. Guibas, “Locating and Bypassing Routing Holes in Sensor Networks,” In Proc. of IEEE INFOCOM 2004, vol.4, March 2004 pp.2458-2468.
[18] T. He, J.A. Stankovic, C. Lu and T.F. Abdelzaher, “A Spatiotemporal Communication Protocol for Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 10, October 2005, pp.995-1006.
[19] D. S. J. De Couto and R. Morris, “Location proxies and intermediate node forwarding for practical geographic forwarding,” Tech. Rep. MITLCS-. TR-824, MIT Laboratory for Computer Science, June 2001.
[20] J. You, D. Lieckfeldt, F. Reichenbach, and D. Timmermann, "Context-aware Geographic Routing for Sensor Networks with Routing Holes," Wireless Communications and Networking Conference, 2009.
[21] F. Yu, Y. Choi, S. Park, E. Lee, Y. Tian, S. Kim, “An Edge Nodes Energy Efficient Hole Modeling in Wireless Sensor Networks,” in Proc. IEEE Global Telecommunications Conference (GLOBECOM), 2007.
[22] Z. Jiang, J. Ma, W. Lou, and J. Wu, “An Information Model for Geographic Greedy Forwarding in Wireless Ad-Hoc Sensor Networks,” Proc. IEEE INFOCOM’08, pp. 825–833, 2008.
[23] W. Jia, T. Wang, G. Wang, M. Guo, “Hole Avoiding in Advance Routing in Wireless Sensor Networks,” in Proceedings of WCNC 2007.
[24] J. Li, J. Jannotti, D. DeCouto, D. Karger, and R. Morris, “A scalable location service for geographic ad-hoc routing,” in Proc. of the 6th Annual ACM/IEEE Int’l Conf. on Mobile Computing and Networking, pp.120-130, 2000.
[25] F. Yu, Y. Choi, S. Park, E. Lee, M. S. Jin, and S. H. Kim, “Sink Location Service for Geographic Routing in Wireless Sensor Networks,” IEEE Wireless Communications and Networking Conference (WCNC), pp. 2111--2116, March 2008.
[26] Graham, R.L, “An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set,” Information Processing Letters 1, 132-133.
[27] The CMU Monarch Project, “The CMU Monarch Project’s Wireless and Mobility extensions to NS,” http://www.isi.edu/nsnam/ns/, accessed September 2007.