由於無線通訊服務的應用日益增加，但可供使用之頻譜資源卻是有限的，如何有效率的使用資源變成一個非常重要的議題。本論文將應用模糊赫普菲爾類神經網路（Fuzzy Hopfield Neural Network；FHNN）來探討通訊排程方面之應用實例。
近年來，模糊赫普菲爾類神經網路常被用來求解最佳化問題，但尚未有其在通訊排程問題上的應用。因此，本論文將以FHNN為基礎來探索FHNN應用的潛能，我們考慮了二種不同存取方式的通訊排程問題，包括頻道指派問題(channel assignment problem)及廣播排程問題(broadcast scheduling problem)等二類通訊排程問題，此等通訊排程問題將被轉換成能量函數（Energy function）後再進行最佳化之設計工作。
首先，本文提出以對稱距離為基礎，以建立一套群聚驗證的方法來求解頻道指派問題及廣播排程問題，此演算法對於幾何特性不同的群聚能適切地加以分群，並可快速計算出最佳頻道指派及廣播排程方式。頻道指派及廣播排程問題是屬於NP-hard 最佳化問題，若應用一般性之數學解析法來求解是相當不切實際的。本文將頻道指派及廣播排程的問題視為是分類問題，由實證結果得知，本文提出之方法能夠快速求得問題個案之最佳解，並適合運用於快速求解通訊排程問題。

The demand for wireless communication service is increasing rapidly. But the available electromagnetic frequency spectrum is rigorously limited. How to manage the frequency resources effectively to provide the maximum service capacity becomes an important issue. This thesis will use the Fuzzy Hopfield Neural Network to probe the communication scheduling instances.
In recent years, Fuzzy Hopfield Neural Network is frequently used to solve optimization problems. The problems are mapped to a FHNN system and an energy function corresponds to the best solutions of the system is chosen. Then the optimal design procedures of the system are conducted. Two different communication scheduling examples, including channel assignment problem and broadcast scheduling problem are considered.
In this thesis, channel assignment problem is considered firstly. The cells on a cell phone communication system are considered as clusters and the frequency channels as objects or samples. The channel assignment problem is then as the optimal design problem of clustering the samples into fixed number of clusters. The channel assignment is an NP-hard problem. It is not realistic for solving the problem with analytic method. The second problem to be considered is the broadcast scheduling problem for packet radio networks. The BSP problem is also an NP-hard problem. Both of the above NP-hard problems are solved by the applied fuzzy Hopfield neural network. Simulation results show that the FHNN can provide an alternative approach for solving these class communication scheduling problems effectively.

[1]V. H. MacDonald, “Advanced Mobile Phone Service: The Cellular Concept”, the Bell System Technical Journal, Vol.58, No.1, pp. 15-41, January 1979.
[2]V. Kecman, Learning and Soft Computing, the MIT Press, London, England, 2001.
[3]D.C Cox and D.O. Reudink, “Effects of some nonuniform spatial demand profiles on mobile radio system performance”, IEEE Transactions on Vehicular Technology , Vol.21, Issue 2 , pp. 62- 67,1972.
[4]D. Nauck, F. Klawonn and R. Kruse, Foundations of Neuro-Fuzzy Systems, John Wiley & Sons, Inc., New York, 1997.
[5]G. Bilbro, R. Mann, T. Miller, W. Snyder, D. E. Van den Bout, and M. White, “Mean field annealing and neural networks,” Advances in Neural Information Processing System, Mogan-Kautmann, pp. 91-98, 1989.
[6]E. S. H. Hou, R. Hong, and N. Ansari, “Efficient multiprocessor scheduling based on genetic algorithm,” Proceedings IEEE of International 16th Annual Conference on Industrial Electronics, Vol. 2, pp. 1239-1243, 1990.
[7]J. J. Hopfield and D. W. Tank, “Neural computation of decision in optimization problems,” Biological Cybernetics, vol. 52, pp. 141-152, 1985.
[8]J. J. Hopfield and D. W. Tank, “Computing with neural circuits: A model,” Science, vol. 233, pp. 625-633, 1986.
[9]L. A. Zadeh, “Fuzzy sets,” Information and Control, vol, 8, pp. 338-353, 1965.C.L.
[10]S. Haykin, Neural networks: a comprehensive foundation, Second Edition, Prentice-Hall, Inc, 1999.
[11]E. W. Forgy, “Cluster analysis of multivariate data: efficiency vs. interpretability of classifications,” Biometrics, vol. 21, pp.768-769, 1993.
[12]M. A. Ismail and S. Z. Selim, “Fuzzy c-mean: optimality of solutions and effective termination of the algorithm,” Pattern Recognition, vol. 19, no. 6, pp. 481-485, 1986.
[13]H. J. Zimmermann, Fuzzy set theory and its application, Kluwer, Boston, pp. 217-240, 1991.
[14]K. Jain and R. C. Dubes, Algorithms for clustering data. Englewood Cliffs, NJ: Prentice Hall, New Jersey, 1988.
[15]K. Jain, M. N. Murthy and P. J. Flynn, "Data clustering: a review," ACM Computing Surveys, vol. 31, no. 3, pp. 265-323, 1999.
[16]J. C. Dunn, “A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters,” J. Cybernetics, vol. 3, no. 3, pp. 32-57, 1974.
[17]J. C. Bezdek, Pattern recognition with fuzzy objective Function Algorithms. New York: Plenum, 1981.
[18]J. C. Bezdek, “Numerical taxonomy with fuzzy sets,” J. Math. Biol., vol. 1, pp. 57-71, 1974.
[19]J. C. Bezdek, C. Coray, R. Gunderson, and J. Watson, “Detection and characterization of cluster substructure,” SIAM Journal on Applied Mathematics, vol. 40, pp. 339-372, 1981.
[20]J. C. Bezdek and N. R. Pal, “Some new indexes of cluster validity,” IEEE Transactions on System, Man, and Cybernetics, vol. 28, no. 3, pp. 301-315, 1998.
[21]C. Su and C. H. Chou, " A modified version of the K-means algorithm with a distance based on cluster symmetry,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 6, pp.674-680, 2001.
[22]C.Y. Chang and P.C. Chung, “Medical image segmentation using a contextual-constraint-based Hopfield neural cube,” Image and Vision Computing, vol. 19, pp. 669-678, 2001.
[23]Y. Takefuji and K. C. Lee, “An artificial hystersis binary neuron: a model suppressing the oscillatory behaviors of neuron dynamics,” Biol. Cybern., vol. 64, pp. 353-356, 1991.
[24]J. J. Hopfield, “Neural network and physical systems with emergent collective computational abilities”, Proceedings of Nat. Acad. Sci. USA, Vol.79, pp.2554-2558, 1982.
[25]S. Miyamoto, “An Overview and New Methods in Fuzzy Clustering,” Proceedings of Second International Conference on Knowledge-Based Intelligent Electronics Systems, vol. 1, pp. 33-40, 1998.
[26]M. P. Windham, ”Geometrical fuzzy clustering algorithms,” Fuzzy Sets and Systems, vol.10, pp.271-279, 1983.
[27]T. Ueda, K. Takahashi, C. Y. Ho, and S. Mori, “Fuzzy scheduling of the parameters in Hopfield neural networks,” IEEE Proceedings of International Conference on Neural Network, vol. 2, pp. 1512-1515, 1993.
[28]J. P. Davis, T. M. Warms, and W. R. Winters, “A neural net implementation of the fuzzy c-means clustering algorithm,” IEEE Proceedings of International Conference on Neural Network, Seatle, vol. II, pp.A-953, 1991.
[29]J. S. Lin, “Image vector quantization using an annealed Hopfield neural network,” Optical Engineering, 38 (4), pp. 599-605, 1999.
[30]J. S. Lin, K. S. Cheng and C. W. Mao, “The application of competitive Hopfield neural network to medical image segmentation,” IEEE Transactions on Medical Imaging, 15, pp. 560-567, 1996.
[31]C. H. Chao and A. P. Dhawan, “Edge detection using a Hopfield neural network,” Optical Engineering 33, pp. 3739-3747, 1994.
[32]C. T. Tsai, Y. N. Sun, P. C. Chung and J. S. Lee, “Endocardial boundary detection using a neural network,” Pattern Recognition 26 (7), pp. 1057-1068, 1993.
[33]S. C. Amatur, D. Piriano and Y. Takefuji, “Optimization neural network for the segmentation of magnetic resonance images,” IEEE Transactions on Medical Imaging
[34]J.S. Lin, “Fuzzy possibilistic neural network to vector quantization in frequency domains,” Optical Engineering, vol. 41, pp. 839-847, 2002.
[35]Chang and Y.T. Ching, “Fuzzy Hopfield neural network with fixed weight for medical image segmentation,” Optical Engineering, vol. 41, pp. 351-358, 2002.
[36]R.G. Roozbahani, M.H. Ghassemian, A.R. Sharafat, “Robust segmentation of medical images using competitive Hopfield neural network as a clustering tool,” Iranian Journal of Science and Technology, vol. 25, pp. 427-439, 2001.
[37]C.Y. Chang and P.C. Chung, “Two-layer competitive based Hopfield neural network for medical image edge detection,” Optical Engineering, vol. 39, pp. 695-703, 2000.
[38]M. Kaya, “A new image clustering and compression method based on fuzzy Hopfield neural network,” IJCI Proceedings of International Conference on Signal Processing, Canakkale-Turkiye, vol. 1, no. 2, pp. 11-16, 2003.
[39]J. S. Lin, K. S. Cheng and C. W. Mao, “Multispectral magnetic resonance image segmentation using fuzzy Hopfield neural network,” International Journal of Bio-Medical Computing 42, pp. 205-214, 1996.
[40]J. S. Lin, K. S Cheng, and C. W. Mao, “A fuzzy Hopfield neural network for medical image segmentation”, IEEE Transactions on Nuclear Science, vol. 43, no. 4, pp. 2389-2398, 1996.
[41]R. M. Chen and Y. M. Huang, “Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Technique”, Neural Computing and Applications, pp. 12-21, 2001.
[42]R. Leese and S. Hurley, editors,” Methods and Algorithms for Radio Channel Assignment,” Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, United Kingdom, 2002.
[43]R. Battiti, A. Bertossi and D. Cavallaro, “A Randomized Saturation Degree Heuristic for Channel Assignment in Cellular Radio Networks”, Technique Report, University of Trento, Italy, 2000.
[44]K. N. Sivarajan, R. J. McEliece, and J. W. Ketchum, “Channel assignment in cellular radio,” Proceeding of 39th IEEE Vehicular Technology, pp. 846–850, May 1989.
[45]F. Fox, “A heuristic technique for assigning frequencies to mobile radio nets,” IEEE Transactions on Vehicular Technology, vol. VT-27, pp. 57–64, May 1978.
[46]W. K. Hale, “Frequency assignment: Theory and applications,” Proceeding of IEEE, vol. 68, pp. 1497–1514, Dec. 1980.
[47]L.G. Anderson, “A Simulation Study of Some Dynamic Channel Assignment Algorithms in a High Capacity Mobile Telecommunications System”, IEEE Transactions on Communications, COM-21, pp. 1294-1301, 1973.
[48]Gamst and W. Rave, “On frequency assignment in mobile automatic telephone systems”, Proceedings of GLOBECOM’82, pp. 309–315, 1982.
[49]R. Mathar and J. Mattfeldt, “Channel assignment in cellular radio networks”, IEEE Transactions on Vehicular Technology, vol. 42, pp. 647–656, 1993.
[50]Gamst, “Homogeneous distribution of frequencies in a regular hexagonal cell system,” IEEE Transactions on Vehicular Technology, vol. 31, pp. 132–144, 1982.
[51]A. M. Koster C. A., “Frequency Assignment - Models and Algorithms”, Ph.D. thesis, Universities Maastricht, Maastricht, The Netherlands, 1999.
[52]S. Shirazi, Alireza Ghasempour; Amindavar, Hamidreza,” Fixed channel assignment using new dynamic programming approach in cellular radio networks ,”Computers and Electrical Engineering, vol. 31, Issue: 4-5, pp. 303-333, June - May, 2005.
[53]W. Wang and C. K. Rushford, “An adaptive local-search algorithm for the channel-assignment problem (CAP),” IEEE Transactions on Vehicular Technology, vol. 45, pp. 459-466, Aug. 1996.
[54]D. Kunz, “Channel assignment for cellular radio using neural networks”, IEEE Transactions on Vehicular Technology, vol. 40, pp. 188–193, 1991.
[55]N. Funabiki and Y. Takefuji, “A neural network parallel algorithm for channel assignment problems in cellular radio networks”, IEEE Transactions on Vehicular Technology, vol. 41, pp. 430–436, 1992.
[56]J. S. Kim, Park S. H, Dowd P. W., and Nasrabadi N, M.,, “Cellular radio channel assignment using a modified hopfield network”, IEEE Transactions on Vehicular Technology, vol. 46, pp. 957–967, 1997.
[57]D. Beckmann and U. Killat, “A New Strategy for the Application of Genetic Algorithms to the Channel-Assignment Problem”, IEEE Transactions on Vehicular Technology, vol.48, no. 4, pp. 1261-1269, 1999.
[58]K. Smith and M. Palaniswami, “Static and dynamic channel assignment using neural networks”, IEEE Journal on Selected Areas in Communications, vol. 15, pp.238–249, 1997.
[59]Z. He, Y. Zhang, C. Wei and J. Wang, “A multistage self-organizing algorithm combined transiently chaotic neural network for cellular channel assignment”, IEEE Transactions on Vehicular Technology, vol. 51, pp. 1386-1396, Nov. 2002.
[60]M. Duque-Antn, D. Kunz, and B. Rber, “Channel assignment for cellular radio using simulated annealing,” IEEE Transactions on Vehicular Technology, vol. 42, pp. 14–21, Feb. 1993.
[61]K. Lee, Y. Takefuji and N. Funabiki, “A parallel improvement algorithm for the biparties subgraphy problem,” Case Western Reserve University, CAISR Technique Report, TR91-105. 1991.
[62]C. Y. Ngo and V. O. K. Li, “Fixed channel assignment in cellular radio networks using a modified genetic algorithm,” IEEE Transactions on Vehicular Technology, vol. 47, pp. 163-171, 1998.
[63]I. Katzela and M. Naghshineh, “Channel Assignment Schemes for Cellular Mobile Telecommunication Systems: A Comprehensive Survey”, IEEE Personal Communications Magazine, pp.10-31, June 1996.
[64]W.K. Lai and G.G. Coghil, “Channel Assignment through Evolutionary Optimization”, IEEE Transactions on Vehicular Technology, vol.45, pp.91-95, 1996.
[65]D. H. Smith, S. Hurley and S. M. Allen, “A New Lower Bound for the Channel Assignment Problem”, IEEE Transactions on Vehicular Technology, vol.49, no.4, pp.1265-1272, July 2000.
[66]S. Tiourine, C. Hurkens and J. K. Lenstra, “An Overview of Algorithmic Approaches to Frequency Assignment Problem”, Technical Report T.U. Eindhoven, 1995.
[67]G. Wyman, G. R. Bradbeer, S. Hurley and D. H. Smith, “Improving Efficiency in Frequency Assignment Engines”, Military Communications Conference (MILCOM 2001), Communications for Network – Centric Operations: Creating the Information Force, IEEE, 2001.
[68]Y. J. Shen , M. S. Wang, " New resource management strategy for wireless cellular networks ", Computers & Electrical Engineering, vol. 32, pp. 135-146, 2006.
[69]C. M. Janssen and K. Kilakos, “An optimal solution to the ’Philadelphia’ channel assignment problem,” IEEE Transactions on Vehicular Technology, vol. 48, no. 3, pp. 1012–1014, 1999.
[70]H. Edgar Callaway, Jr. and Edgar H, Wireless Sensor Networks: Architectures and Protocols, Callaway, CRC Press, 352 pages, August 2003.
[71]S. Kim and J.I. Kim, “An adaptive time slot assignment algorithm for variable bandwidth switching systems,” Computers & Operations Research ,Vol.27, Issue:5, pp. 423-435, 2000.
[72]D. J. Baker and A. Ephremides, “The architectural organization of a mobile radio network via a distributed algorithm,” IEEE Transactions on Communications, vol. COM-29, pp. 1694-1701, Nov., 1981.
[73]L. Tassiulas, A. Ephremides, and J. Gunn, “Solving hard optimization problems arising in packet radio networks using Hopfield’s net,” Proc. 1989 Conf. Info. Sci. Sys., Johns Hopkins Univ., Mar., pp.603-608, 1989.
[74]S. Even, O. Goldreich, S. Moran and P. Tong, “On the NP-completeness of certain network testing problems,” Networks, vol.14, pp.1-24, 1984.
[75]N. Funabiki and Y. Takefuji, “A parallel algorithm for broadcast scheduling problems in packet radio networks,” IEEE Transactions on Communications, vol.41, no.6, pp.828-831, June 1993.
[76]Y. Takefuji, K. Lee, H. Aiso, “An artificial maximum neural network: a winner-take-all neuron model forcing the state of the system in a solution domain,” Biological Cybernetics, vol.67, pp.243-251, 1992.
[77]G. Chakraborty, Y. Hirano, “Genetic algorithm for broadcast scheduling in packet radio networks,” IEEE world congress on computational intelligence, pp.183-188, 1998.
[78]S. Salcedo-Sanz, C. Bousono-Calzon, A.R. Figueiras-Vidal,” A mixed neural-genetic algorithm for the broadcast scheduling problem,” IEEE Transactions on Wireless Communications, 2, pp.277–283, 2003.
[79]J. Yeo , H. Lee, S. Kim,”An efficient broadcast scheduling algorithm for tdma ad-hoc networks,” Computer & Operations Research, 29, pp.1793–1806, 2002.
[80]G. Wang and N. Ansari, ”Optimal broadcast scheduling in packet radio networks using mean field annealing,” IEEE Journal on Selected Areas in Communications, 15, pp.250–260,1997.
[81]H. Shi and L. Wang,” Broadcast scheduling in wireless multi-hop networks using a neural-network-based hybrid algorithm,” Neural Networks ,vol. 18, Issue: 5-6, July - May, pp. 765-771, 2005.
[82]Yu-Ju Shen, Ming-Shi Wang, “Broadcast scheduling in Wireless sensor networks using Fuzzy Hopfield Neural Network”, Expert Systems with Applications, to be published in 34(4) early 2008.
[83]D. Bertsekas and R. Gallager, Data Networks, Englewood Cliffs, NJ: Prentice-Hall, 1987.
[84]Y. Peng, B.H. Soong, L .Wang, “Broadcast scheduling in packet radio networks using mixed tabu-greedy algorithm,” Electronics Letters, vol.40, pp. 375 – 376, 2004.
[85]E. L. Lloyd, “Broadcast scheduling for TDMA in wireless multi-hop networks,” Wireless Networks and Mobile Computing, pp. 347–369, 2002.