在地理性路由(geographic routing)中，每個節點(node)都選擇鄰居之中離目的節點(destination)最近的作為轉送的下一個節點。這種轉送(forwarding)的方式稱之為貪婪轉送(greedy forwarding)，同時此種方法在成功實施的情況下也被證明為會近似最短路徑。然而貪婪轉送遇到局部極小(local minima)的情況時，會因為死路(dead end)的發生而無法繼續進行傳送。此問題可透過將整個網路分割成可單獨執行貪婪轉送的區塊來改善。以往的網路分割演算法大多為集中式，而集中式的演算法會存在傳輸訊息壅塞以及單點故障(single point of failure)的問題。在本論文，我們設計一個分散式的演算法Localized GRR Decomposition (LGD)來對整個網路進行貪婪區塊(Greedily Routable Region)的切割。在亂數產生網路中，我們的演算法與已知的演算法比較可產生更少的貪婪區塊。此外，LGD演算法也會因為分散式演算法的特性，使得分割所需的溝通負擔(overhead)減少。

In geographic routing, a node selects the neighbor closest to the destination to forward the packet. This scheme is known as the greedy forwarding, and has been shown to produce sub-optimal route when it works. However, the greedy forwarding may fail if the packet is forwarded to a local minimum. One way to solve this issue is to partition the network into a number of pieces. Within each piece, the greedy forwarding scheme is guaranteed to work. The network partition algorithms proposed in the past are centralized, which naturally suffer from message congestion and the single point of failure. In this thesis, we propose a distributed algorithm, namely Localized GRR Decomposition (LGD), to partition the network into a number of greedily routable regions. Using randomly generated sensor networks, we show that our algorithm is able to produce a lower number of GRRs when compared with the best known result. Additionally, the communication overhead of our LGD algorithm is lower due to its distributed nature.

中文摘要 i
英文摘要 ii
一、介紹 1
二、相關文獻 3
三、Localized GRR Decomposition (LGD) 11
3.1 Cutpoint-Discovery 11
3.2 Network-Decomposition 14
3.3演算法的正確性 20
四、效能評估 23
4.1隨機產生網路 23
4.2環境複雜度 24
4.3效能評估 24
五、結論與未來展望 35
參考文獻 36

[1]R. Szewczyk, A. Mainwaring, J. Anderson, and D. Culler, “An analysis of a large scale habit monitoring applicarion,” in Proc. ACM SenSys, 2004.
[2]T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, and et al., “An energy-efficient surveillance system using wireless sensor networks,” in Proc. ACM MobiSys, 2004.
[3]S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” in Proc. ACM MobiCom, 2005.
[4]C. E. Perkins and E. Bhagwat, “Highly dynamic destination-sequenced distance-vextor routin(DSDV) for mobile computer,” in Proc. ACM SIGCOMM, 1994.
[5]T. Clausen et al, “Optimized link state routing protocol,” IETF Internet Draft , 2003.
[6]D. Johnson and D. Maltz, “Dynamic source routing in ad hoc wireless networks,” in Proc. ACM Mobicom, 1996.
[7]C. Perkins and E. M. Royer, “ad hoc on-demand distance vector routing,” in Proc. IEEE WMCSA, 1999.
[8]V. D. Park and M. S. Corson, “A highly adaptive distributed routing algorithm for mobile wireless networks,” in Proc. IEEE INFOCOM, 1997.
[9]P. Bahl and V. N. Padmanabhan, “RADAR: An In-Building RF-Based User Location and Tracking System,” in Proc. IEEE INFOCOM, 2000.
[10]T. He, C. Huang, B. M. Blum, J. A. Stankovic, T. Abdelzaher, “Range-Free Localization Schemes for Large Scale Sensor Networks,” in Proc. ACM MobiCom, 2003.
[11]A. Harter, A. Hopper and P. Steggles, “A. Ward and P.Webster, The anatomy of a context-aware application, ” in Proc. ACM MobiCom, 1999.
[12]B. Karp and H. T. Kung, “GPSR : Greedy perimeter stateless routing for wireless networks,” in Proc. ACM Mobicom, 2000.
[13]A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, “Geographic routing without location information,” in Proc. ACM MobiCom, 2003.
[14]J. Bruck, J. Gao, A. Jiang, “MAP:Medial Axis Based Geometric Routing in Sensor Networks,” in Proc. ACM Mobicom, 2005.
[15]Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang, “GLIDER: Gradient landmark-based distributed routing for sensor networks,” in Proc. IEEE INFOCOM, 2005.
[16]G. Tan, M. Bertier and A-M. Kermarrec, “Visibility-Graph-based Shortest-Path Geographic Routing in Sensor Networks,” in Proc. IEEE INFOCOM, 2009.
[17]G. Tan, M. Bertier and A-M. Kermarrec, “Convex Partition of Sensor Networks and Its Use in Virtual Coordinate Geographic Routing,” in Proc. IEEE INFOCOM, 2009.
[18]X. Zhu, R. Sarkar, and J. Gao, “Shape segmentation and applications in sensor networks,” in Proc. IEEE INFOCOM, 2008.
[19]G. Tan and A-M. Kermarrec, “Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach,” in Proc. ACM Mobihoc, 2010.
[20]C. Zhang, Y. Zhang and Y. Fang, “Localized algorithms for coverage boundary detection in wireless sensor networks,” Wireless Networks, 2007.
[21]L. P. Chew and R. L. Drysdale, “Voronoi diagrams based on convex distance functions,” in Proc. ACM Sympos.Comput. Geom., 1985.
[22]D. T. Lee and F. P. Preparata, “Location of a point in a planar subdivision and its applications,” SIAM Journal on Computing, vol. 6, pp. 594–606, 1977.
[23]K. Mulmuley, “A fast planar partition algorithm,” Journal of Symbolic Computation, vol. 10, pp. 253–280, 1990.
[24]D. Lichtenstein, “Planar Formulae and Their Uses,” SIAM Journal on Computing, vol. 11, pp. 329-343, 1982.
[25]A-M Kermarrec and G. Tan, “Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach,” Technical report of INRIA-Rennes, July, 2010.
http://hal.archives-ouvertes.fr/inria-00493387/en/
[26]S.-Y. Ni, Y.-C. Tseng, Y.-S Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proc. ACM Mobicom, 1999.
[27]Y-B Ko, and N. H. Vaidya, “Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms,” in Proc. IEEE MCSA, 1999.