臺灣博碩士論文加值系統

　　設計一個具有節能效果之無線隨意網路中使得無線設備在有限的電池下得以減少交換或傳送訊息時的能量消耗一直是設計無線隨意網路的一個重要的目標。為了實現這個目標，我們首先採用圖論中的相對鄰居圖(Relative Neighborhood Graph, RNG)來調整節點與節點之間的傳輸距離，以便得到一個具節能效果的RNG邏輯網路拓撲結構。然後再根據所得的RNG邏輯網路拓撲結構，我們提出了一個名為GCA (Green Clustering Algorithm)的叢集演算法來建構一個具節能效果的叢集架構。模擬的結果證實了在我們考慮的環境中，我們所提的方法確實比其他方法可以更有效降低節點能量消耗及延長節點的存活時間。

Designing a power-efficient wireless ad hoc network to conserve the limited battery power in exchanging messages has been recognized as one of the important design goals. To achieve this objective, we first employ the concept of Relative Neighborhood Graph (RNG) to obtain a power-efficient logical network topology in which the transmission ranges between nodes are adjusted to the optimal. Then, based on the obtained RNG-based logical network topology, we present a green clustering algorithm to organize the wireless ad hoc network into a power-efficient clustered architecture. Compared to other approaches, simulation results confirm that the clustered architecture organized by the presented approaches can efficiently reduce the energy consumption and, thus, extend the time to live of each wireless node.

致謝 i
論文摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 ix
第一章 導論 1
1.1 研究動機和目的 1
1.2 無線隨意網路 1
1.3 圖論 3
1.4 最短路徑 6
1.5 廣播 7
1.6 路由協定 8
第二章 背景及研究相關 11
2.1 福利斯自由空間方程式 11
2.2 拓樸控制 13
2.3 叢集基本架構介紹 18
2.3.1 叢集角色定義 18
2.3.2 叢集之通訊 19
2.4 叢集化結構的重要性與優點 20
2.5 叢集演算法 23
第三章Green Clustering Algorithm 29
3.1 RNG拓樸控制特點與MQM演算法 29
3-2 GCA叢集演算法說明 31
3.3 GCA叢集演算法實例 36
第四章 系統維護與運作之耗能分析 41
4.1 系統維護 41
4.1.1 維護封包數目 41
4.1.2 維護封包耗能 42
4.2 路由設計 43
4.3 資料傳遞－雙向握手機制 44
4.4 傳輸模型 46
第五章 模擬實驗與結果 48
5.1 模擬參數相關 49
5.2 模擬結果 50
5.3 模型參數d_0之影響 75
5.4 綜合模擬之結果 78
第六章 結論與未來工作 80
6.1 結論 80
6.2 未來工作 80
參考文獻 82

[1]C. Siva Ram Murthy and B. S. Manoj, Ad Hoc Wireless Network: Architectures and Protocols, Prentice Hall, 2004.
[2]闕頌廉, 圖論基礎, 科技圖書股份有限公司, 民國80年6月1版
[3]孫惠泉, 圖論及其應用, 科學出版社, 2004年9月1日
[4]Graph theory (http://en.wikipedia.org/wiki/Graph_theory)
[5]C.E. Perkins and E.M. Royer, “ Ad Hoc On-Demand Distance Vector (AODV) Routing,” IETF Internet draft, Jul. 2003.
[6]E. Royer and C. -K. Toh, "A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks," IEEE Personal Communications Magazine, vol. 6, no.2, pp. 46-55, April 1999.
[7]R. Ramanathan and R. Rosales-Hain, “Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment,” Proc.IEEE INFOCOM, pp. 1-10, March 2000.
[8]Topology control (http://en.wikipedia.org/wiki/Topology_control)
[9]F. Araújo and L. Rodrigues, “Fast Localized Delaunay Triangulation,” Lecture Notes in Computer Science, vol. 3544, pp. 81-93, 2005.
[10]G. T. Toussaint, “The Relative Neighborhood Graph of a Finite Planar Set,” Pattern Recognition, vol. 12, pp. 261-268, 1980.
[11]J. W. Jaromczyk and G. T. Toussaint, “Relative Neighborhood Graphs and Their Relatives,” Proceedings of the IEEE, vol. 80, no. 9, pp. 1502-1517, 1992.
[12]J. Cartigny, I. Stojmenovic and D. Simplot, “Localized Minimum-Energy Broadcasting in Ad-Hoc Networks,” IEEE INFOCOM 2003.
[13]J. Cartigny, D. Simplot, and I. Stojmenovic, “Localized Minimum-Energy Broadcasting in Ad-Hoc Networks,” Proc. IEEE INFOCOM, vol. 3, pp. 2210-2217, 2003.
[14]J. Cartigny, P.M. Ruiz, D. Simplot-Ryl, I. Stojmenovic, and C.M. Yago, “Localized Minimum-Energy Broadcasting for Wireless Multihop Networks with Directional Antennas,” IEEE Transactions on Computers, vol. 58, no. 1, pp. 120-131, 2009.
[15]Y. Zhu, H. Xu, and J. Xiao, “A Clustering Topology Control Algorithm for Heterogeneous Wireless network”, in Proceedings of the International Conference on Communications, Circuits and Systems, pp. 392-396, 2005.
[16]W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-Efficient Routing Protocols for Wireless Microsensor Networks,” in Proc. 33rd Hawaii Int. Conf. System Sciences (HICSS), Maui, HI, Jan. 2000.
[17]M. R. Garey and D. S. Johnson, “Computers and Intractability: A guide to the theory of NP-Completeness,” Freeman, San Francisco, 1978.
[18]C. S. Li, “Clustering in Packet Radio Networks,” IEEE ICC 85, pp. 283-287, 1985.
[19]B. Das and V. Bhargavan, “Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets,” IEEE ICC 97, 1997.
[20]A. Parekh, “Finding Small Dominating Sets in Stationless Mobile Packet Radio Networks,” Tech. Rep. LIDSP-2050, Laboratory for Information and Decision Systems, M.I.T., Cambridge, MA, 1991.
[21]J. Wu and H. L. Li, “On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks,” ACM Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7-14, 1999.
[22]J. C. Lin, S. N. Yang and M. S. Chern, “An Efficient Distributed Algorithm For Minimal Connected Dominating Set Problem,” Tenth Annual International Phoenix Conference on Computers and Communications, pp. 204 –210, 1991
[23]D. J. Baker and A. Ephremides, “The Architectural Organization of A Mobile Radio Network via A Distributed Algorithm,” IEEE Trans. on Commu., vol. COM-29, no. 11, pp. 1694-1701, 1981.
[24]D. J. Baker, A. Ephremides, and J. A. Flyn, ”The Design and Simulation of A Mobile Radio Network with Distributed Control,” IEEE Journal on Selected Area of Communications, vol. SAC-2, pp. 226-237, Jan. 1984.
[25]C. H. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Area of Communications, vol. 15, no. 7, pp. 1265-1275, 1997.
[26]A. Ephremides, J. E. Wieselthier, and D. J. Baker, “A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling,” Proc. of the IEEE, vol. 75, no. 1, pp. 56-73, 1987.
[27]M. Gerla and J. T. C. Tsai, “Multicluster, Mobile, Multimedia Radio Network,” ACM/Baltzer J. Wireless Networks, vol. 1, no. 3, pp. 255-265, 1995.
[28]M. J. Shah and P. G. Flikkema, “Power-Based Leader Selection in Ad-Hoc Wireless Networks,” IEEE International Performance, Computing and Communications Conference, pp. 134-139, Feb. 1999.
[29]S. Basagni, “Distributed Clustering for Ad Hoc Networks,” Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN’99), pp. 310-315, 1999.
[30]S. Singh and J. Kurose, “Electing Leaders Based Upon Performance: The Delay Model,” IEEE International Conference on Distributed Computing, pp. 464-471, May 1991.
[31]C. S. Li, “Clustering in Packet Radio Networks,” IEEE ICC 85, pp. 283-287, 1985.
[32]C. C. Tseng and K. C. Chen, “Organizing an Optimal Cluster-Based Ad Hoc Network Architecture by the Modified Quine-McCluskey Algorithm,” IEEE Communications Letters, vol. 11, no. 1, Jan. 2007.
[33]W.B. Heinzelman, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660-670, 2002.
[34]L Nassef “On The Effects of Fading and Mobility in On-Demand Routing Protocols,” Egyptian Informatics Journal, pp. 67-74, 2010.