臺灣博碩士論文加值系統

在無線環境中，網路的效能會高度受到底層的拓撲所影響。而一個稀疏的拓撲具有減少多餘流量的特性，因此可提升網路擴增性。然而一個稀疏拓撲經常會犧牲許多重要的網路線段，這些線段有可能是型成要能源有效路由的必經路徑。因此，在拓撲的能源有效性和稀疏度之間存在了相互牽制的議題。
在這篇論文中，我們將提出以幾合圖型為基礎的拓撲控制方法，這個方法可透過參數的設定達到在能源有效性和稀疏度之間調整的彈性，理論結果證明此方法可保證拓撲的連通性、平行性，和對稱性。更重要的是，每一個節點利用區域內所收集的資訊即可建構出所需的拓撲。
為了解決節點的移動性，我們以前面的圖型方法為基礎，提出了一個可適性的拓撲控制協定，此協定具有在保有節點能源和改進整體耗能之間動態調整的能力。數據及摸擬結果提出，我們的方法可有效減少能源消耗，特別是對高度行動的網路有明顯的改進。

The wireless ad hoc network is convenient to many applications, such as conferences, hospitals, battlefields, and etc. In these environments, the network performance heavily relies on the underlying topology. Especially, keeping the topology sparser enhances network scalability. However, a sparse topology may sacrifice some routes that consume less power. Therefore, a tradeoff is between the sparseness and the energy efficiency of the topology.
In this dissertation, we propose a geometric structure, named the r-neighborhood graph, to control the topology. The structure allows the flexibility to be adjusted between energy efficiency and node’s degree through a parameter r, 0 �T r �T 1. Theoretic results show that it can always result in a connected planar topology with symmetric edges. More importantly, the structure can be constructed in localized fashion using only 1-hop information.
To cope with node’s mobility, we investigate an adaptive protocol, based on a generalized version of the r-neighborhood graph. In this protocol, the parameter r can be adjusted distributively by each node according to the overall energy efficiency. To reduce the construction power, we further incorporate the protocol with a shrinking power mechanism for the topology maintenance. Simulation and numeric results show that the proposed approaches can significantly improve the energy consumption, especially in high mobility environment.

Abstract (in Chinese)...................................i
Abstract (in English)...................................ii
Acknowledgements........................................iii
Contents................................................iv
List of Tables..........................................vi
List of Figures.........................................vii
1 Introduction..........................................1
2 Netowrk Model and Related Works.......................7
2.1 Network Model.......................................7
2.2 Staionary Topolgoy Control..........................9
2.3 Mobile Topology Control.............................14
3 Graphic Structures....................................17
3.1 r-Neighborhood Graph................................17
3.2 Extended r-Neighborhood Graph.......................26
3.3 (r,alpha)-Neighborhood Graph........................33
3.4 (r,alpha)-Enclosed Graph............................35
3.5 (fr,alpha)-Neighborhood Graph.......................39
4 Energy-Efficient Construction.........................41
4.1 Localized Algorithm.................................41
4.2 Shrinking Power Mechanism...........................48
4.3 Neighborhood Graph Based Topology Control Protocol..51
4.4 Convergency.........................................54
5 Mobile Topology Control Protocol......................57
5.1 Extending on Shrinking Power mechanism..............57
5.2 Adaptive Mobile Topology Control Protocol...........58
5.3 Efficient Calculation and Time Complexity...........62
6 Experiments...........................................65
6.1 Evaluations on Graph Structures.....................65
6.2 Evaluations on Shrinking Power Mechanisms...........69
6.3 Evaluations on the Mobile Protocol..................70
7 Conclusion............................................73
Appendix................................................75
Bibliography............................................76
Vita....................................................81

[1]P. Bose, J. Gudmundsson, and P. Morin, “Ordered theta graphs,” In Proc. of Canadian Conference on Computational Geometry, 2002.
[2]P. Bose, P. Morin, I. Stojmenovi´c, and J. Urrutia, “Routing with guarantee delivery in ad hoc networks,” ACM/Kluwer Wireless Networks, vol. 7, no. 6, pp. 609–616, 2001.
[3]P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick, “On the spanning ratio of Gabriel Graphs and beta-skeletons,” to appear in SIAM Journal of Discrete Math, 2004.
[4]I. Chlamtac, M. Conti, and J.N. Liu, “Mobile ad hoc networking: imperatives and challenges,” Ad Hoc Networks, vol. 1, pp. 13–64, 2003.
[5]L. Feeney, “An energy-consumption model for performance analysis of routing protocols for mobile ad hoc networks,” ACM Journal of Mobile Networks and Applications, vol. 3, no. 6, pp. 239–249, 2001.
[6]K.R. Gabriel and R.R. Sokal, “A new statistical approach to geographic variation analysis,” Systematic Zoology, vol. 18, pp. 259–278, 1969.
[7]H.N. Gabow, J.L. Bently, and R.E. Tarjan, “Scaling and related techniques for geometry problems,” ACM Symposium on Theory of Computing, pp. 135–143, 1984.
[8]J. Geo, L.J. Guibas, J. Hershburger, L. Zhang, and A. Zhu, “Geometric spanner for routing in mobile networks,” In Proc. of ACM MobiHoc, 2001.
[9]A.A.K. Jeng and R.H. Jan, “An adjustable structure for topology control in wireless ad hoc network,” In Proc. of the 2005 International Conference on Wireless Network Communication and Mobile Computing, 2005.
[10]J. Katajainen, “The region approach for computing relative neighborhood graph in the Lp metric,” Computing, vol. 40, pp. 147–161, 1988.
[11]B. Karp and H. T. Kung, “GPSR: greedy perimeter stateless routing for wireless Networks,” In Proc. of ACM MobiCom, 2000.
[12]P. Klein, S. Rao, M. Rauch, and S. Subramanian, “Faster shortest-path algorithms for planar graph” In Symp. of theory of Computing, 1994.
[13]L.A. Latiff and N. Fisal, “Routing protocols in wireless mobile ad hoc network – a review,” Commuincations, vol. 2, pp. 600 – 604, 2003.
[14]W. H. Lee and T.H. Meng, “A lower power GPS receiver architecture” In Proc. of Global Telecommunications conference, vol. 11, pp. 153–157, 1999.
[15]X.Y. Li, P.J. Wan, and Y. Wang, “Power efficient and sparse spanner for wireless ad hoc networks,” In Proc. of IEEE International Conference on Computer Communicationsand Networks, pp. 564–567, 2001.
[16]X.Y. Li and P.J. Wan, “Constructing minimum energy mobile wireless networks,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, pp. 55–67, 2001.
[17]X.Y. Li, P.J. Wan, Y. Wang, and O. Frieder, “Sparse power efficient topology for wireless networks,” In Proc. of 35th Annual Hawaii International Conference on System Sciences (HICSS’02), vol. 9, 2002.
[18]X.Y. Li, G. Calinescu, P.J. Wan, and Y. Wang, “Localized delaunay triangulation with application in ad hoc wireless networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 10, pp. 1035–1047, 2003.
[19]X.Y. Li and Y. Wang. “Efficient construction of low weight bounded degree planar spanner,” International Journal of Computational Geometry and Applications, World Science Publications, vol.14, no. 1-2, pp. 69-84. 2004.
[20]L. Li and J.Y. Halpern, “Minimum-energy mobile wireless networks revisited” In Proc. of IEEE international conference on communications (ICC’01), 2001.
[21]R. Prakash, “Unidirectional links prove costly in wireless ad-hoc networks,” In Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), 1999.
[22]F.P. Preparata and M.I. Shamos, Computational geometry – an introduction, Springer-Verlag, New York, 1985.
[23]R. Rajaraman, “Topology control and routing and ad hoc network: a survey,” ACM SIGACT, vol. 33, no. 2, 2002.
[24]V. Rodoplu and T. H. Meng, “Minimum energy mobile wireless networks,” IEEE Journal Selected Area in Comm., vol. 17, no. 8, pp. 1333–1344, 1999.
[25]W.Z. Song, Y. Wang, and X.Y. Li, “Energy efficiency: Localized algorithms for energy efficient topology in wireless ad hoc networks,” In Proc. of the 5th ACM international symposium on Mobile ad hoc networking and computing, 2004.
[26]I. Stojmenovic and S. Datta, “Power and cost aware localized routing with guaranteed delivery in wireless networks,” Wireless Communications and Mobile Computing, Vol. 4, no. 2, pp. 175-188, 2004.
[27]I. Stojmenovic and X. Lin, “Power-aware localized routing in wireless networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 11, pp. 1122 – 1133, 2001.
[28]G.T. Toussaint, “The relative neighborhood graph of a finite planar set,” Pattern Recognition, vol. 12, no. 4, pp. 261–268, 1980.
[29]Y. Wang and X.Y, Li, “Distributed spanner with bounded degree for wireless ad hoc networks,” International Journal of Foundations of Computer Science, vol. 14, pp. 183–200, 2003.
[30]W. Wang, X.Y. Li, K. Moaveninejad, Y. Wang, and W.Z. Song, “The spanning ratios of beta-skeleton,” In Proc. of Canadian Conference on Computational Geometry (CCCG), 2003.
[31]Y. Wang and X.Y. Li, “Localized construction of bounded degree planar spanner for wireless ad hoc networks,” In Proc. of the 2003 Joint Workshop on Foundation of Mobile Computing, pp. 59 – 68, 2003.
[32]R, Wattenhofer and A. Zollinger, “XTC: A practical topology control for ad-hoc networks,” In Proc. of the 18th Parallel and Distributed Processing Symposium, pp. 26–30, 2004.
[33]A.C.C. Yao, “On constructing minimum spanning trees in k-dimensional spaces and related problems,” SIAM Journal of Computing, vol. 11, pp. 721–736, 1982.
[34]Paolo Santi, “Topology control in wireless ad hoc and sensor networks”, ACM Computing Survey, Vol. 37, no. 2, 2005, pp. 164 – 194.
[35]Silvia Giordano, Ivan Stojmenovic, and Ljubica Blazevic, “Position based routing algorithms for ad hoc networks a taxonomy,” Ad Hoc Networking, 2004, pp. 103 – 126.
[36]J. Liu, B. Li, “MobileGrid: capacity-aware topology control in mobile ad hoc network”, In Proc. of IEEE Internal Conference on Computer Communications and Networks, pp. 570-574, 2002.
[37]R. Ramanathan, R. Rosales-Hain, “Topology control of multihop wireless network using transmit power adjustment”, In Proc. of IEEE INFOCOM 2000, pp. 404-413, 2000.
[38]M. Blough, M. Leoncini, G. Resta, P. Santi, “The K-neigh protocol for symmetric topology control in ad hoc network”, ACM MobiHoc’03, 2003
[39]R. Wattenhoef, L. Li, P. Bahl, Y. Wang, “Distributed topology control for power efficient operation in multihop wireless ad hoc network”, In Proc. of IEEE INFOCOM, 2001, pp. 1388-1397.
[40]L. Li, J.H. Halpern, P. Bahl, Y. Wang, R. Wattenhofer, "Analysis of a cone-based distributed topology control algorithm for wireless multi-hop netwroks", In Proc. of ACM PODC 2001, pp. 264-273, 2001
[41]ns2 simulator: http://www.isi.edu/nsnam/ns/
[42]C.E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers”, In Proc. of ACM SIGCOMM’94, pp. 234-244, August 1994.