在這篇論文中，我們提出針對大型無線網路之功率管理結合群集的演算法。首先，討論有效率之功率消耗;不適當之傳輸能量將導致大功率消耗及相互干擾問題，因此我們的演算法提供了在無線網路上調整傳輸能量方法來傳送資料封包。另外的問題是網路連結問題，我們針對這個問題引入了一些稱為"gateway"的點來維持整個無線網路的連結效果。相較於"blind flooding"的機制造成大量控制封包流竄於網路上，我們利用群集的作法來建立一個虛擬的骨幹網路來減低了轉送點和轉送封包的數目。且由於針對無線網點進行縮減功率，空間的重複利用性也可以很有效率提高。我們的目的為將整個空間切割為幾個較小的群集， 如此即可達到空間的重複使用; 再者，在我們的演算法下網路能量的消耗也可以明顯減低。經由模擬的結果可以驗證我們的演算法達到了能量效率和空間重複使用效率的優點。

　　In this dissertation, we propose a distributed algorithm for managing a large scale of ad hoc networks efficiently. We introduce a notion of power management scheme combined with the clustering scheme. The first topic is the power consumption efficiency in a wireless ad hoc environment. An inappropriate transmission power leads to high power consumption and interference of the networks, thus our power management scheme adapts power to transmit data packet throughout the networks. Therefore, there is something wrong with the connectivity of the topology; we investigate the effect of connectivity issue by introducing "gateway" nodes to maintain the connectivity of the topology. Compared with the blind flooding of control packets, we reduce number of relay nodes and relay packets by constructing the virtual backbone with clusters. Due to limited power of each node, the space reuse could be very effective. Our proposed scheme divided a large contention domain into small ones, so the spatial reuse could be achieved. Furthermore, the power consumption is obviously reduced by our proposed scheme. Simulations show that our scheme achieves efficient power consumption and effective space reuses.

[1] C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile computers," Comp. Commun. Rev., Oct. 1994, pp. 234-44.
[2] L. R. Ford Jr. and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, 1962.
[3] C. E. Perkins and E. M. Royer, " Ad-hoc On-Demand Distance Vector Routing", Second IEEE WorkShop on Mobile Computing Systems and Applications, pp90-100, February 1999.
[4] D. B. Johnson and D.A Maltz, "Dynamic Source Routing in Ad-Hoc Wireless Networks" in Mobile Computing, pp 153-181, 1996.
[5] C. K. Toh, "Associativity-Based Routing For Ad Hoc Mobile Networks," WL Pers. Commun. J., Special Issue on Mobile Networking and Computing System, Kliwer, vol. 4, no. 2, Mar.1997, pp.103-39.
[6] S. R Das, C. E. Perkins and E. M. Royer, "Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks," Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000.
[7] C. C. Chiang and M. Gerla, " Routing and Multicast in Multihop, Mobile Wireless Networks," Proc. IEEE ICUPC '97, San Diego, CA, NOV. 2000.
[8] Y. Yi, Gerla, M. T. J. Kwon, "Efficient Flooding in Ad Hoc Networks: A
Comparative Performance Study," 2003. ICC '03. 11-15 May 2003. pp. 1059 - 1063.
[9] D. Kim, S. Ha, and Y. Choi, "K-hop Cluster-based Dynamic Source Routing in Wireless Ad-Hoc Packet Radio Networks," IEEE VTC'98.
[10] Y. Fernandess, D. Malkhi, "K-Clustering in Wireless Ad Hoc Networks", POMC'02, October 30-31, 2002, Toulouse, France.
[11] C. M. Sas, S. K. Turgut, "An On-Demand Weighted Clustering Algorithm (WCA) for Ad Hoc Networks," GLOBECOM '00. IEEE. 27 Nov.-1 Dec. 2000. pp. 1697 - 1701.
[12] S. Banerjee, S. Khuller, "A Clustering Scheme for Hierarchical Control in Multi-hop Wireless Networks," IEEE INFOCOM 2001.
[13] L. Bao, J.J. Garcia-Luna-Aceves, "Topology Management in Ad Hoc Networks," MobiHoc '03, Jun 1-3. 2003, Annapolis, Maryland, USA
[14] K. Xu, X. Hong, M. Gerla, "An Ad Hoc Networks with Mobiles Backbones," IEEE ICC2002. April-2 May 2002, pp. 3138 - 3143.
[15] C. R. Lin, and M. Gerla, "Adaptive Clustering for Mobile Networks," IEEE Journal on Selected Area in Communication, Vol. 15, No. 7, Sep. 1997, pp. 1265-1275.
[16] M. Gerla, and J. T. Tsai, "Multicluster, mobile, multimedia radio network," ACM-Baltzer Journal of Wireless Networks, Vol.1 No. 3, pp.255-65,1997
[17] P. -J. Wan; Alzoubi, K.M. Frieder, O., "Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks", INFOCOM 2002. 23-27 June 2002 pp. 1597 - 1604.
[18] Rodoplu, V. Meng, T.H., "Minimum Energy Mobile Wireless Networks," Selected Areas in Communications, IEEE Journal. Aug. 1999 pp. 1333 - 1344.
[19] Wattenhofer, R.; Li, L.; Bahl, P.; Wang, Y.-M., "Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks," INFOCOM 2001. 22-26 April 2001 pp. 1388 - 1397.
[20] R. Ramanathan, R. R.-Hain, "Topology Control of Multihop Wireless Networks using Transmit Power adjustment," INFOCOM 2000, March 2000 pp.404 - 413 vol.2.
[21] ElBatt, T.A.; Krishnamurthy, S.V.; Connors, D.; Dao, S., " Power Management for Throughput Enhancement in Wireless Ad Hoc Networks," ICC 2000. 18-22 June 2000
[22] X. Zeng, R. Bagrodia, M. Gerla ,"GloMoSim: a Library for Parallel Simulation of Large-scale Wireless Networks", Proceedings of the 12th Workshop on Parallel and Distributed Simulations -- PADS '98, May 26-29, 1998 in Banff, Alberta, Canada
[23] Y. T Lin, J. S. Li, " Increasing Connectivity with Bounded Interference Using Percolation theory in Mobile Ad Hoc Networks," will publish in ICON 2005
[24] The Institute of Electrical and Electronics Engineers, Inc. IEEE Std 802.11 - Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, 1999 edition. (802.11 std )