臺灣博碩士論文加值系統

地理位址路由是一種非常適合應用於無線隨意網路之路由方法，也在二度空間的環境中有許多深入的研究。然而針對三度空間中的地理位址路由提案卻寥寥無幾。在這篇論文中，我們發展出Slab Routing，利用投影的方式將二度空間的地理路由演算法延伸至三度空間，並保留其原有的短路徑優點。Slab Routing的做法是即時的切割出一個稱作slab的空間，將在其中之點投影至一個平面後擷取平面圖，再執行二度空間的地理路由演算法。雖然Slab Routing的操作方式無法確保所有訊息都可以抵達其目的地，我們推導出一個可以根據網路部署環境預測傳送機率的數學模型，並以實驗驗證之。

Geographic routing, an attractive routing solution for wireless ad hoc networks, has been studied extensively in two-dimensional environments. However, three-dimensional space has proven to be much more challenging, with only a few existing proposals. In this paper, we present Slab Routing - a novel projection based method for adapting two-dimensional geographic face routing techniques to three-dimensional space, avoiding flooding and preserving their route optimality properties. Slab Routing accomplishes this by executing face routing over the planar projected graph of nodes contained within a dynamically created space partition, called a slab. While the adaption does not offer guaranteed delivery, we provide an analysis of the conditions required to achieve a desired delivery probability and verify the results through simulation.

1 Introduction 1
2 Preliminaries and Related Work 4
2.1 Geographic Routing 4
2.2 Topology Control 8
3 Slab Routing 10
4 Analysis 16
5 Simulation 21
6 Conclusion 28
Bibliography 29

[1] A. E. Abdallah, T. Fevens, and J. Opatrny. Hybrid position-based 3d routing algorithms with partial flooding. In CCECE ’06: Proceedings of the 19th Annual IEEE Canadian Conference on Electrical and Computer Engineering, pages 227–230, 2006.
[2] A. E. Abdallah, T. Fevens, and J. Opatrny. Randomized 3d position-based routing algorithms for ad-hoc networks. In MOBIQUITOUS ’06: The 3rd Annual International Conference on Mobile and Ubiquitous Systems: Networks and Services, pages 1–8, 2006.
[3] A. E. Abdallah, T. Fevens, and J. Opatrny. High delivery rate position-based routing algorithms for 3d ad hoc networks. Computer Communications, 31(4):807–817, 2008.
[4] J. Allred, A. B. Hasan, S. Panichsakul, W. Pisano, P. Gray, J. Huang, R. Han, D. Lawrence, and K. Mohseni. Sensorflock: an airborne wireless sensor network of micro-air vehicles. In SenSys ’07: Proceedings of the 5th International Conference on Embedded Networked Sensor Systems, pages 117–129, 2007.
[5] L. Barri′ere, P. Fraigniaud, and L. Narayanan. Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In DIALM’01: Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pages 19–27, 2001.
[6] C. Bettstetter. On the minimum node degree and connectivity of a wireless multihop network. In MobiHoc ’02: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 80–91, 2002.
[7] H. Dette and N. Henze. The limit distribution of the largest nearest-neighbour link in the unit d-cube. Journal of Applied Probability, 26(1):67–80, 1989.
[8] J. Diaz, M. D. Penrose, J. Petit, and M. Serna. Convergence theorems for some layout measures on random lattice and random geometric graphs. Combinatorics, Probability, and Computing, 9(6):489–511, 2000.
[9] S. Durocher, D. Kirkpatrick, and L. Narayanan. On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. In ICDCN ’08: Proceedings of the 9th International Conference on Distributed Computing and Networking, pages 546–557, 2008.
[10] G. G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI/RR-87-180, Information Sciences Institute, 1987.
[11] R. Flury and R. Wattenhofer. Randomized 3d geographic routing. In INFOCOM ’08: Proceedings of the 27th IEEE Conference on Computer Communications, pages 834–842, 2008.
[12] P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity. In CDC ’98: Proceedings of the 37th IEEE Conference on Decision and Control, pages 1106–1110, 1998.
[13] J. Heidemann, W. Ye, J. Wills, A. Syed, and Y. Li. Research challenges and applications for underwater sensor networking. In WCNC ’06: Proceedings of IEEE Wireless Communications and Networking Conference, pages 228–235, 2006.
[14] G. Kao, T. Fevens, and J. Opatrny. Position-based routing on 3-d geometric graphs in mobile ad hoc networks. In CCCG ’05: Proceedings of the 17th Canadian Conference on Computational Geometry, pages 88–91, 2005.
[15] G. Kao, T. Fevens, and J. Opatrny. 3-d localized position-based routing with nearly certain delivery in mobile ad hoc networks. In ISWPC ’07: 2nd International Symposium on Wireless Pervasive Computing, pages 344–349, 2007.
[16] B. Karp and H. T. Kung. Gpsr: greedy perimeter stateless routing for wireless networks. In MobiCom ’00: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pages 243–254, 2000.
[17] E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In CCCG ’99: Proceedings of the 11th Canadian Conference on Computational Geometry, pages 51–54, 1999.
[18] F. Kuhn, R. Wattenhofer, and A. Zollinger. Worst-case optimal and average-case efficient geometric ad-hoc routing. In MobiHoc ’03: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 267-278, 2003.
[19] J. Li, J. Jannotti, D. S. J. De Couto, D. R. Karger, and R. Morris. A scalable location service for geographic ad hoc routing. In MobiCom ’00: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pages 120–130, 2000.
[20] M. S. Pan, C. H. Tsai, and Y. C. Tseng. Emergency guiding and monitoring applications in indoor 3d environments by wireless sensor networks. International Journal of Sensor Networks, 1(1/2):2–10, 2006.
[21] M. D. Penrose. On k-connectivity for a geometric random graph. Random Structures and Algorithms, 15(2):145–164, 1999.
[22] S. Ramanathan and E. L. Lloyd. Scheduling algorithms for multi-hop radio networks. SIGCOMM Computing Communication Review, 22(4):211–222, 1992.
[23] T. J. Shepard. A channel access scheme for large dense packet radio networks. SIGCOMM Computer Communication Review, 26(4):219–230, 1996.
[24] Sinalgo. Simulator for Network Algorithms. http://dcg.ethz.ch/projects/sinalgo, 2007.
[25] F. Xue and P. R. Kumar. The number of neighbors needed for connectivity of wireless networks. Wireless Networks, 10(2):169–181, 2004.