臺灣博碩士論文加值系統

　　數年前，國立臺灣大學與中正大學的研究團隊完成了蜜蜂尋跡系統。其關鍵技術包含了諧波雷達、微型收發器、以及虛擬隨機序列測距。由於諧波雷達輸入電腦之資料量非常龐大，在相關運算上相當耗時而成為瓶頸，以致於雷達天線的轉速受到限制。天線緩慢掃描的後果，讓野外實驗得到的蜜蜂位置數據嚴重不足。再者，原系統之目標判讀有賴人工，不僅費時而且容易誤判。本論文針對以上缺失，提出了新的運算架構（平行處理）與兩種演算法（目標測距和資料分群）。
　　平行處理部分，由於蜜蜂尋跡系統其運作原理甚為繁複，為減少資料運算的耗時、以便即時呈現運算結果，因而提出平行處理架構，該架構有效的利用了四個運算元、解決上述遭遇的困難。
　　目標測距的部分，本文將會使用人工類神經網路（Artificial Neural Network）對訊號進行分類，以辨識其是否包含目標資訊，訊號的特徵萃取將採用高階累積量（Cumulant）以及相似係數（Resemblance Coefficient）。本文也會深入探討虛擬隨機序列（Pseudorandom Noise）遭受嚴重雜訊干擾時之統計特性，以凸顯利用累積量作為特徵，在本系統訊號識別上的優勢。
　　在每次些許差異的測試環境下，訊號偶會遭遇到反射現象，本文亦利用統計學中之漢佩爾辨識法（Hampel Identifier），克服了這個問題。緊接著的問題是，雷達之天線束指向性有限，因此同個目標往往造成重複出現的假象。針對此問題我們利用了DBSCAN（Density Based Spatial Clustering of Applications with Noise）演算法，並基於我們的應用做出些改善，最後確能有效的對這種散佈點的例子進行分群。
　　以上運算架構以及演算法，使得改善後的蜜蜂雷達尋跡系統掃描速度提升了14倍，掃描40度的範圍只需要三秒鐘，並在辨識正確率高達99.6%的情況下，自動產生蜜蜂位置資訊，以供昆蟲專家研究蜜蜂行為。此外本文亦深入的探討偽隨機序列於雜訊影響下的統計結果、以及累積量於此的使用。基於本應用的改善版DBSCAN，也是十分新穎的嘗試。這些種種不應視為只是本系統的特例，其廣泛性應可推廣到未來其他方面的應用。

Several years ago, the bee tracing system was set up by researchers from both National Taiwan University and National Chung Cheng University. Technics involve: harmonic radar, micro transponder, and pseudorandom noise ranging. However, the heavy load of correlation calculations caused bottlenecks, and further limited the rotation speed of the antenna. Such issue led to the lack of bees’ location information. Moreover, the target identification in original system relied on manual work, which is neither effective nor precise. In this paper, we hereby introduce a new processing structure (parallel processing) and a series of algorithms (detection, ranging and clustering) with respect to the mentioned problem in original system.
The parallel processing structure is mainly aim at solving the high computational complexity of our system, so that the result could be real-time presented. This structure properly utilized all four cores by parallel programming, thus increasing the scanning speed by 14 times, and the scanning of a 40° range will cost only 3 seconds.
For the detection, we are going to use the Artificial Neural Network as our classifier, and the feature extraction is based on: 1) “Cumulant”, a higher-order statistic quantity, and 2) “Resemblance Coefficient”, an effective approach for radar signal feature. Its accuracy could be as high as 99.6%. We will also further discuss the statistical properties of Pseudorandom Noise under the serious noise situation, giving prominence to the utilization of cumulant here.
Sometimes we may suffer from reflective propagations, we will introduce Hampel Identifier method to deal with such ranging problem. What comes next is the repeating of single target’s signals due to limited directivity of our antenna. We modified the DBSCAN algorithm, creating a novel method which is especially useful for clustering the spreading points such as our case.

口試委員會審定書 I
誌　謝 III
摘　要 V
ABSTRACT VI
TABLE OF CONTENTS VII
LIST OF TABLES X
LIST OF FIGURES XI
CHAPTER 1 INTRODUCTION 1
1.1 MOTIVATION 1
1.2 PREVIOUS WORK 1
1.2.1 BASIC PRINCIPLES 2
1.2.2 HARMONIC RADAR SYSTEM 3
1.2.3 MIXING RADAR SYSTEM 5
1.3 SYSTEM PARAMETERS 7
1.3.1 TRANSMITTING 7
1.3.2 RECEIVING 7
1.3.3 CONTROLLING 8
1.4 OVERVIEW OF OUR WORKS 8
1.5 EXPERIMENTAL ENVIRONMENT 10
CHAPTER 2 PARALLEL PROCESSING 12
2.1 BACKGROUND 12
2.2 AMDAHL’S LAW 13
2.3 PROPOSED STRUCTURE 15
2.3.1 DESIGNING STRATEGY 15
2.3.2 CORRELATION THREAD 17
2.3.3 ACQUISITION THREAD 18
2.3.4 DISPLAY THREAD 18
2.3.5 OTHER NOTATIONS 19
2.4 SIMULATIONS 19
2.4.1 PLATFORM I 20
2.4.2 PLATFORM II 21
2.5 RESULTS OF IMPLEMENTATION 22
CHAPTER 3 SIGNALS OF SYSTEM 24
3.1 MODELING OF SIGNALS 24
3.1.1 SYSTEM MODELING 24
3.1.2 FIRST LOOK AT INTERFERENCE 26
3.1.3 INTERFERENCES MODELING 27
3.2 STATISTICS OF SIGNALS 28
3.2.1 CROSS-CORRELATION WITH WGN 29
3.2.2 CONSIDERATION OF DEMODULATION 32
3.2.3 THE SECOND-ORDER INTERFERENCES 36
3.3 SIMULATIONS OF SIGNALS 36
3.3.1 NORMALITY OF CROSS-CORRELATION WITH WGN 37
3.3.2 NORMALITY OF CROSS-CORRELATION WITH MIXED WGN 38
CHAPTER 4 DETECTION AND RANGING 40
4.1 BACKGROUND 40
4.2 FEATURE EXTRACTION 41
4.2.1 CUMULANT FEATURE 41
4.2.2 RESEMBLANCE COEFFICIENT FEATURE 44
4.2.3 SIMULATIONS OF FEATURE EXTRACTION 46
4.3 CLASSIFICATION 49
4.3.1 STRUCTURE AND CRITERIA 49
4.3.2 FINAL RESULTS 50
4.3.3 FURTHER DISCUSSIONS 51
4.4 TARGET RANGING 54
4.4.1 MODELING OF MULTI-REFLECTIONS 55
4.4.2 IMPLEMENTATION 56
CHAPTER 5 CLUSTERING 59
5.1 BACKGROUND 59
5.2 TRADITIONAL METHODS 61
5.3 PROPOSED METHOD 63
5.3.1 DECISIONS BASED ON INSTINCTS 63
5.3.2 REVISED ALGORITHM BASED ON LOCAL DENSITIES 64
5.4 SIMULATIONS 66
5.4.1 SCENARIO I 67
5.4.2 SCENARIO II 68
5.5 EXPERIMENTS 69
5.5.1 RESULT I 69
5.5.2 RESULT II 71
5.5.3 RESULT III 72
CONCLUSION 73
REFERENCES 75
APPENDICES 80
A. CUMULANT 80
A.1 MOMENT-GENERATING FUNCTION 80
A.2 CUMULANT-GENERATING FUNCTION 82
A.3 RELATION BETWEEN MOMENTS AND CUMULANTS 83
A.4 CUMULANT OF GAUSSIAN DISTRIBUTION 84
A.5 CUMULANT OF CHI-SQUARED DISTRIBUTION 87
A.6 ELEMENTARY ARITHMETIC 88
B. RESEMBLANCE COEFFICIENT 90
B.1 DEFINITION AND APPLICATION 90
B.2 PERFORMANCE ANALYSIS 90
C. CONFUSION MATRIX 94
C.1 CRITERIA 94
C.2 FURTHER TERMINOLOGIES AND DERIVATIONS 95
D. HAMPEL IDENTIFIER METHOD 96
D.1 BREAKDOWN POINT THEORY 96
D.2 MAIN METHOD 98
E. DBSCAN ALGORITHM 100
E.1 DEFINITIONS 100
E.2 ILLUSTRATION 101

[1].J. B.-Y. Tsui, Fundamentals of global positioning system receivers: A software approach. United States: John Wiley & Sons, 2005.
[2].J. S. Lee and L. E. Miller, CDMA systems engineering handbook. Boston, MA: Artech House Publishers, 1998.
[3].Z.-M. Tsai et al., "A high range resolution 9.4/18.8 GHz harmonic radar for bees searching," in Microwave Symposium Digest (MTT), 2012 IEEE MTT-S International, Montreal, QC, Canada, 2012, pp. 1-3.
[4].Z.-M. Tsai et al., "A high-range-accuracy and high-sensitivity harmonic radar using pulse pseudorandom code for bee searching," IEEE Trans. Microw. Theory Tech., vol. 61, no. 1, pp. 666-675, Jan. 2013.
[5].P.-H. Jau et al., "Signal processing for harmonic pulse radar based on spread spectrum technology," IET Radar, Sonar & Navigation, vol. 8, no. 3, pp. 242–250, Mar. 2014.
[6].Y. Li, In-Phase and Quadrature Imbalance. Dordrecht: Springer, 2013.
[7].P.-H. Jau et al., "A BPSK-based harmonic ranging system," in Proceedings of the 2011 International Technical Meeting of the Institute of Navigation, San Diego, CA, January 2011, pp. 238-243.
[8].M.-L. Hsu et al., "High transmitter-receiver isolation in mixing radar using pulse pseudorandom code for bee searching," IEEE Trans. Microw. Theory Tech, to be published.
[9].Y.-T. Lu et al., "A differential miniature transponder for 9.4/18.8 GHz harmonic bee searching radar with low gain degradation from bee’s body," presented at the Microwave Symposium (IMS), 2016 IEEE MTT-S International, San Francisco, CA, 2016.
[10].G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities, reprinted from the AFIPS conference proceedings, Vol. 30 (Atlantic city, N.J., Apr. 18–20), AFIPS press, Reston, Va., 1967, pp. 483–485, when Dr. Amdahl was at international business machines corporation, Sunnyvale, California," IEEE Solid-State Circuits Newsletter, vol. 12, no. 3, pp. 19–20, 2007.
[11].B. Parhami, Introduction to parallel processing. New York: Kluwer Academic, 2002.
[12].J. L. Gustafson, "Reevaluating Amdahl’s law," Communications of the ACM, vol. 31, no. 5, pp. 532–533, May 1988.
[13].J. Albahari and B. Albahari, C# 5.0 in a nutshell: The definitive reference, 5th ed. United States: O’Reilly Media, Inc, USA, 2012.
[14].C. Campbell, R. Johnson, and A. Miller, Parallel programming with Microsoft .NET: Design patterns for decomposition and coordination on Multicore architectures. United States: Microsoft Press, U.S., 2010.
[15].D. Koufaty and D. T. Marr, "Hyperthreading technology in the netburst microarchitecture," IEEE Micro, vol. 23, no. 2, pp. 56–65, Mar. 2003.
[16].R. G. Gallager, Stochastic Processes: Theory for Applications. New York, NY: Cambridge University Press, 2013.
[17].T. Schilcher. Class Lecture, Topic: "Digital signal processing in RF applications." The CERN Accelerator School, Sigtuna, Sweden, Jun. 07, 2007.
[18].F. J. MacWilliams and N. J. A. Sloane, "Pseudo-random sequences and arrays," Proceedings of the IEEE, vol. 64, no. 12, pp. 1715–1729, 1976.
[19].D. S. Moore, U. W. I. Notz, and U. M. A. Fligner, The basic practice of statistics, 6th ed. New York: Macmillan Higher Education, 2011.
[20].M. J. Hinich, " Testing for Gaussianity and linearity of a stationary time series," Journal of Time Series Analysis, vol. 3, no. 3, pp. 169–176, May 1982.
[21].V. Z. Marmarelis and P. V. Z. Marmarelis, Nonlinear dynamic modeling of physiological systems. United States: Wiley-Interscience, 2004.
[22].C. Forbes et al., Statistical distributions, 4th ed. United States: Wiley, John & Sons, 2011.
[23].H. C. Thode, Testing for normality. New York: Marcel Dekker, 2002.
[24].V. Mayer-Schönberger et al., Big data: A revolution that will transform how we live, work, and think. London: John Murray General Publishing Division, 2013.
[25].A. Spaulding and D. Middleton, "Optimum reception in an impulsive interference environment--part I: Coherent detection," IEEE Trans. Commun., vol. 25, no. 9, pp. 910–923, Sep. 1977.
[26].K. J. Sangston, “Coherent detection of radar targets in K-distributed, correlated clutter,” Naval Research Lab, Washington D.C., NRL-9130, 1988.
[27].F. Gini, "A cumulant-based adaptive technique for coherent radar detection in a mixture of k-distributed clutter and Gaussian disturbance," IEEE Trans. Signal Process., vol. 45, no. 6, pp. 1507–1519, Jun. 1997.
[28].M. Kendall et al., Kendall''s advanced theory of statistics. London: Edward Arnold, 1994.
[29].H. Cramér, Mathematical methods of statistics. Princeton: Princeton University Press, 1946.
[30].J. M. Mendel, "Tutorial on higher-order statistics (spectra) in signal processing and system theory: Theoretical results and some applications," Proceedings of the IEEE, vol. 79, no. 3, pp. 278–305, Mar. 1991.
[31].D. R. Brillinger, "An introduction to Polyspectra," The Annals of Mathematical Statistics, vol. 36, no. 5, pp. 1351–1374, Oct. 1965.
[32].J. F. Kenney Mathematics of Statistics Part I. London: Chapman & Hall Ltd, 1939.
[33].C. Rose and M. Smith, Mathematical Statistics with Mathematica®. New York, NY: Springer New York, 2002.
[34].M. Bulmer, Principles of statistics. New York: Dover Publications, 1979.
[35].A. Winkelbauer, "Moments and absolute moments of the normal distribution," arXiv preprint, arXiv:1209.4340, 2012.
[36].G. Zhang et al., "Radar emitter signal recognition based on resemblance coefficient features," in Rough Sets and Current Trends in Computing, Uppsala, Sweden, Jun. 2004, pp. 665-670.
[37].O. A. Dobre et al., "Higher-order cyclic cumulants for high order modulation classification," in Military Communications Conference, Boston, MA, 2003. pp. 112-117.
[38].O. Dobre et al., "Survey of automatic modulation classification techniques: classical approaches and new trends," IET Commun., vol. 1, no. 2, p. 137, 2007.
[39].J. P. M. de Sa and J. P. Marques de Sa, Pattern recognition: Concepts, methods and applications. Germany: Springer-Verlag Berlin and Heidelberg GmbH & Co. K, 2001.
[40].C. M. Bishop and G. Hinton, Neural networks for pattern recognition. New York: Oxford University Press, 1995.
[41].S. Karsoliya, "Approximating number of hidden layer neurons in multiple hidden layer BPNN architecture," International Journal of Engineering Trends and Technology, vol. 3, no. 6, pp. 713-717, 2012.
[42].D. E. Rumelhart et al., "Learning representations by back-propagating errors," Nature, vol. 323, no. 6088, pp. 533–536, Oct. 1986.
[43].S. Seo, “A review and comparison of methods for detecting outliers in univariate data sets,” M.S. thesis, Graduate School of Public Health, University of Pittsburgh, Pittsburgh, PA, 2006.
[44].P. J. Rousseeuw and A. M. LeRoy, Robust regression and Outlier detection. United States: Wiley, 2005.
[45].H. Liu, S. Shah, and W. Jiang, "On-line outlier detection and data cleaning," Computers & Chemical Engineering, vol. 28, no. 9, pp. 1635–1647, Aug. 2004.
[46].P. Huber, Robust statistics. New York: Wiley, 1981.
[47].J. L. Hodges Jr, "Efficiency in normal samples and tolerance of extreme values for some estimates of location." in Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, vol. 1, Berkeley, CA: University of California Press, 1967, pp. 163-186.
[48].F. R. Hampel, "A general qualitative definition of robustness," The Annals of Mathematical Statistics, vol. 42, no. 6, pp. 1887–1896, Dec. 1971.
[49].C. J. Geyer, "Breakdown point theory notes," Class Notes: Nonparametric Statistics, 2006.
[50].F. R. Hampel, "The influence curve and its role in robust estimation," Journal of the American Statistical Association, vol. 69, no. 346, pp. 383–393, Jun. 1974.
[51].L. Davies and U. Gather, "The identification of multiple Outliers," Journal of the American Statistical Association, vol. 88, no. 423, p. 782, Sep. 1993.
[52].R. R. Wilcox and R. Wilcox, Applying contemporary statistical techniques. United States: Elsevier Science, 2003.
[53].T. Fawcett, "An introduction to ROC analysis," Pattern Recognition Letters, vol. 27, no. 8, pp. 861–874, Jun. 2006.
[54].D. M. Powers, "Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation," Flinders Univ. of South Australia, Adelaide, South Australia, Rep. SIE-07-001, 2011.
[55].P. Berkhin, "A survey of clustering data mining techniques." in Grouping multidimensional data, Berlin: Springer, 2006, pp. 25-71.
[56].A. K. Jain et al., "Data clustering: A review," in ACM Computing Surveys, vol. 31, no. 3, pp. 264–323, Sep. 1999.
[57].T. Calinski and J. Harabasz, "A dendrite method for cluster analysis," Communications in Statistics - Theory and Methods, vol. 3, no. 1, pp. 1–27, 1974.
[58].R. Tibshirani et al., "Estimating the number of clusters in a data set via the gap statistic," Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 63, no. 2, pp. 411–423, May 2001.
[59].G. W. Milligan and M. C. Cooper, "An examination of procedures for determining the number of clusters in a data set," Psychometrika, vol. 50, no. 2, pp. 159–179, Jun. 1985.
[60].B. W. Silverman and M. C. Jones, "E. Fix and J.L. Hodges (1951): An important contribution to Nonparametric Discriminant analysis and density estimation: Commentary on fix and Hodges (1951)," International Statistical Review / Revue Internationale de Statistique, vol. 57, no. 3, p. 233, Dec. 1989.
[61].M. Ester et al., "A density-based algorithm for discovering clusters in large spatial databases with noise," in Kdd., Portland, OR, 1996, pp. 226-231.