隨著無線通訊技術的快速發展，如何實現行動台(mobile station, MS)之位置估測是不可或缺的。憑藉精準的定位，無線定位技術可被應用於不同層面，如E911急難救助、安全服務以及智慧型運輸系統。行動台的定位精準度密切依賴訊號的傳播環境，事實上非視線傳播(non-line-of-sight, NLOS)的存在將導致信號量測的誤差。因此減少非視線傳播效應造成之誤差為無線定位系統之首要任務。
人工蜂群演算法(artificial bee colony, ABC)的技術被廣泛應用來解決各領域不同之問題，是一種基於蜜蜂群體智能覓食行為之最佳化演算法。行動台位置之估測是基於接收訊號強度(received signal strength indication, RSSI)量測值，並且利用目標函數來降低NLOS誤差達到提升預測精準度之效果，更利用人工蜂群演算法達成搜尋擁有最佳目標函數值之行動台估測位置之目標。不同的運算規則以及兩個實作階段被設計來處理實際接收訊號強度量測值。為了證明此演算法增之穩健度以及可行性，我們一併執行模擬分析及實測統計。模擬分析使用不同的誤差分布模型來測試並比較提出演算法與其他定位方法之優劣。根據模擬分析以及實作結果，顯示本論文所提出之人工蜂群定位演算法可以提供擁有最佳定位精確度且更有效率之行動台位置估測。

Since the rapid development of the wireless communication technology, the ability of how to estimate the location of mobile station (MS) is indispensable. By the accurately positioning, the location technology can be applied to various applications, like the E911 emergency assistance, security services, and intelligent transportation systems. The accuracy of MS location estimation depends on signal propagation environment closely. In practical, non-line-of-sight (NLOS) is existence everywhere and it leads to the error of signal measurement. Therefore, in a wireless location system, the main task is to cut down the error generated from NLOS environments.
Artificial Bee Colony (ABC) algorithm is a widely used technique to solve problems in various areas. It is an optimization algorithm based on the intelligent foraging behavior of honey bee swarm. MS location was estimated based on three received signal strength indication (RSSI) measurements in this thesis. To enhance the prediction accuracy, the proposed scheme employs the object function to mitigate the additional NLOS error. In this work, searching the optimal MS location with best object function value is accomplished by ABC algorithm. To deal with the practical RSSI measurements, different calculation principles and two stages are designed.
To prove the reliability and feasibility of the proposed location algorithm, the numerical simulations and practical measurements was implemented simultaneously. Different error distributions were used for numerical simulations, and the performance of the proposed scheme was compared with other existing methods. The results with simulation and measurement show that the proposed ABC-based location algorithm offers the MS location with best accuracy and the efficient positioning procedure.

[1] “Revision of the commission’s rules to ensure compatibility with enhanced 911 emergency calling systems,” Washington, DC, RM-8143,CC Docket 94-102, U.S. FCC, 1996.
[2] Reed, J.H.; Krizman, K.J.; Woerner, B.D.; Rappaport, T.S. “An overview of the challenges and progress in meeting the E-911 requirement for location service,” IEEE Commun. Mag. 1998, 36, 30–37.
[3] J. J. Caffery, Jr. and G. Stuber, “Overview of radio location in CDMA cellular systems,” IEEE Communications Magazine, vol. 36, no. 4, pp. 38-45, Apr. 1998.
[4] E. D. Kaplan and C. J. Hegarty, Understanding GPS: principles and applications, Artech House Press, Boston, 2005.
[5] W. Wang, T. Jost, and U. Fiebig, “Characteristics of the NLoS Bias for an Outdoor to Indoor Scenario at 2.45 GHz and 5.2 GHz,” IEEE Antennas and Wireless Propagation Letters, vol. 10, October 2011.
[6] J. J. Caffery and G. L. Stüber, “Subscriber location in CDMA cellular networks,” IEEE Trans. Veh. Technol., vol. 47, no. 2, pp. 406–416, May 1998.
[7] S. Al-Jazzar, J. Caffery, and H.-R. You, “Scattering-model-based methods for TOA location in NLOS environments,” IEEE Trans. Veh. Technol., vol. 56, no. 2, pp. 583–593, Mar. 2007.
[8] P. C. Chen, “A non-line-of-sight error mitigation algorithm in location estimation,” in Proc. IEEE WCNC, New Orleans, LA, Sept. 1999, pp. 316–320.
[9] W. Kim, J. G. Lee, G.-I. Jee, and B. Kim, “Direct estimation of NLOS propagation delay for mobile station location,” Electron. Lett., vol. 38, no. 18, pp. 1056–1057, Aug. 2002.
[10] Z. Wang and S. Zekavat, “Omni-directional mobile NLOS identification and localization via multiple cooperative nodes,” IEEE Trans. Mobile Comput., 2011. doi:10.1109/TMC.2011.232 .
[11] R. Diamant, H. Tan, and L. Lampe, “LOS and NLOS classification for underwater acoustic localization,” IEEE Trans. Mobile Comput, Vol. 11, no. 12, pp. 2047–2059, Dec.2012, DOI:10.1109/TMC.2012.249.
[12] M. Boccadoro, G. D. Angelis and P. Valigi, “TDOA Positioning in NLOS Scenarios by Particle Filtering,” Wireless Networks, Vol.18, No.5, 2012, pp. 579-589.
[13] D. Dardari, A. Conti, U. J. Ferner, A. Giorgetti, and M. Z. Win, “Ranging with ultrawide bandwidth signals in multipath environments,” Proc. IEEE, vol. 97, no. 2, pp. 404–426, Feb. 2009.
[14] Chen, C.-S.; Su, S.-L.; Huang, Y.-F, “Hybrid TOA/AOA geometrical positioning schemes for mobile location,” IEICE Trans. Commun. 2009, E92-B, 396–402.
[15] Chen, C.-S.; Su, S.-L.; Huang, Y.-F, “Mobile location estimation in wireless communication systems,” IEICE Trans. Commun. 2011, E94-B, 690–693.
[16] S. S. Woo, H. R. You, and J. S. Koh, “The NLOS mitigation technique for position location using IS-95 CDMA networks,” IEEE Vehicular Technology Conference, vol. 6, pp. 2556-2560, Sep. 2000.
[17] M. Silventoinen and T. Rantalainen, “Mobile station emergency locating in GSM,” in IEEE International Conference on Personal Wireless Communications, pp. 232-238, Feb. 1996.
[18] K. A. Remley, G. Koepke, C. L. Holloway, C. Grosvenor, D. Camell, J. Ladbury, R. T. Johnk, and W. F. Young, “Radio wave signal propagation into large building structures–part 2: characterization of multipath,” IEEE Trans. Antennas. Propag., pp. 1290–1301, Apr. 2010.
[19] A. Goldsmith, S. A. Jafar, N. Jindal, and S. Vishwanath, “Capacity limits of MIMO channels,” IEEE J. Sel. Areas Commun., vol. 51, no. 6, pp. 684–702, Jun. 2003.
[20] J. H. Yap, S. Ghaheri-Niri, and R. Tafazolli, “Accuracy and hearability of mobile positioning in GSM and CDMA networks,” Third International Conference on 3G Mobile Communication Technologies, pp. 350 -354, May 2002.
[21] T. S. Rappaport, J. H. Reed, and B. D. Woerner, “Position location using wireless communications on highways of the future,” IEEE Communications Magazine, vol. 34, pp. 33-41, Oct. 1996.
[22] A. Oborina1, T. Henttonen and V. Koivunen, “Cell Hearability Analysis in UTRAN Long Term Evolution Downlink,” Proceedings of the 43rd Asilomar Conference on Signals, Systems and Computers, 2009, pp. 991-995.
[23] P. Misra and P. Enge, "Global Positioning System: Signals, Measurements and Performance," 2011.
[24] I. Guvenc and C. Chia-Chin, "A Survey on TOA Based Wireless Localization and NLOS Mitigation Techniques," Communications Surveys & Tutorials, IEEE, vol. 11, pp. 107-124, 2009.
[25] G. Mao, et al., "Wireless sensor network localization techniques," Computer Networks, vol. 51, pp. 2529-2553, 2007.
[26] M. Karkooti, et al., "FPGA implementation of matrix inversion using QRD-RLS algorithm," in Proceedings of the 39th Asilomar Conference on Signals, Systems and Computers, 2005, pp. 1625-1629.
[27] G. M. Siouris, Aerospace avionics systems: a modern synthesis vol. 466: Academic press New York, 1993.
[28] C. Park, I. Kim, J.G. Lee and G.I. Jee, “A satellite selection criterion incorporating the effect of elevation angle in GPS positioning”, Control Eng. Pract., vol.4, no.12, pp.1741-1746, Dec. 1996.
[29] H. Sairo, et al., "Weighted dilution of precision as quality measure in satellite positioning," IEE Proceedings-Radar, Sonar and Navigation, vol. 150, pp. 430-436, 2003.
[30] D. Simon and H. El-Sherief, "Navigation satellite selection using neural networks," Neurocomputing, vol. 7, pp. 247-258, 1995.
[31] D. E. Rumelhart, et al., "Learning representations by back-propagating errors," Cognitive modeling, vol. 1, p. 213, 2002.
[32] D.-J. Jwo and K.-P. Chin, "Applying back-propagation neural networks to GDOP approximation," Journal of Navigation, vol. 55, pp. 97-108, 2002.
[33] S. S. Wang, M. Green, and M. Malkawa, “E-911 location standards and location commercial services,” in IEEE Emerging Technologies Symposium: Broadband, Wireless Internet Access, pp. 1-5, Apr. 2000.
[34] J. S. Maltz, T. S. C. Ng, D. J. Li, J. Wang, K. Wang, W. Bergeron, R. Martin, and T. F. Budinger, “The trauma patient tracking system: implementing a wireless monitoring infrastructure for emergency response,” Proc. IEEE International Conference Engineering in Medicine and Biology Society, pp. 2441-2446, Jan. 2006.
[35] S. H. Chew, P. A. Chong, E. Gunawan, K. W. Goh, Y. Kim, and C. B. Soh, “A hybrid mobile-based patient location tracking system for personal healthcare applications,” Proc. IEEE International Conference Engineering in Medicine and Biology Society, pp.5188-5191, Sep. 2006.
[36] S. Riter and J. McCoy, “Automatic vehicle location—An overview,” IEEE Transactions on Vehicular Technology, vol. 26, no. 1, pp. 7-11, Feb. 1977.
[37] J. J. Caffery and G. L. Stuber, “Vehicle location and tracking for IVHS in CDMA microcells,” in IEEE Personal Indoor Mobile Radio Conference, vol. 4, pp. 1227-1231, Sep. 1994.
[38] J. J. Caffery and G. L. Stuber, “Radio location in urban CDMA microcells,” in Proc. IEEE International Symposium Personal, Indoor, Mobile Radio Communications, vol. 2, pp. 858-862, Sep. 1995.
[39] W. Chen, L. Chen, Z. Chen, and S. Tu, “WITS: A wireless sensor network for intelligent transportation system,” in Proc. of the First International Multi-Symposiums on Computer and Computational Science, vol. 2, pp. 635-641, Jun. 2006.
[40] M. N. Borenovic, M. I. Simic, A. M. Neskovic and M. M. Petrovic, “Enhanced Cell-ID + TA GSM positioning technique,” International Conference on in Computer as a Tool, vol. 2, pp. 1176-1179, Nov. 2005.
[41] G. Gracioli, A.A. Fröhlich, R.P. Pires, and L. Wanner, “Evaluation of an RSSI-based Location Algorithm for Wireless Sensor Networks,” IEEE Latin America Transactions, vol. 9, 2011, pp. 96-101.
[42] G. Ott, “Vehicle location in cellular mobile radio systems,” IEEE Trans. Veh. Technol., vol. VT-26, no. 1, pp. 43–46, Feb. 1977.
[43] G. Turin, W. Jewell, and T. Johnston, “Simulation of urban vehicle monitoring systems,” IEEE Trans. Veh. Technol., vol. VT-21, no. 1, pp. 9–16, Feb. 1972.
[44] Smith, J.O.; Abel, J.S. “Closed-form least squares source location estimation from range difference measurements,” IEEE Trans. Acoust. Speech Signal Process. 1987, ASSP-35, 1661–1669.
[45] Y. Qi, “Wireless geolocation in a non-line-of-sight environment,” Ph.D. dissertation, Princeton Univ., Princeton, NJ, 2003.
[46] M. Hata and T. Nagatsu, “Mobile location using signal strength measurements in a cellular system,” IEEE Transactions on Vehicular Technology, vol. VT-29, no. 2, pp. 245-252, May 1980.
[47] S. Anderson, M. Millnert, M. Viberg, and B. Wahlberg, “An adaptive array for mobile communication systems,” IEEE Transactions on Vehicular Technology, vol. 40, no. 1, pp. 230-236, Feb. 1991.
[48] W. C. Jakes, “Microwave Mobile Commun.” IEEE Press, 1994.
[49] W. H. Foy, “Position-location solutions by Taylor series estimation,” IEEE Transactions on Aerospace and Electronic Systems, vol. AES-12, no. 2, pp. 187-194, Mar. 1976.
[50] J. J. Caffery, Jr., “A new approach to the geometry of TOA location,” in Proc. IEEE Vehicular Technology Conference, pp. 1943-1949, Sep. 2000.
[51] Y. Zhao, “Mobile phone location determination and its impact on intelligent transportation systems,” IEEE Transactions on Intelligent Transportation Systems, vol. 1, no. 1, pp. 55-64, Mar. 2000.
[52] L. Cong and W. Zhuang, “Hybrid TDOAJAOA mobile user location for wideband CDMA cellular systems,” IEEE Trans. Wireless Commun, vol. 1, pp. 439–447, Jul. 2002.
[53] G. Ding, Z. Tan and Z. Zhang “Hybrid TOA/AOA Cooperative Localization in Non-Line-of-Sight Environments,” IEEE, Vehicular Technology Conference, pp. 1-5 May 2012.
[54] J. Huang and Q. Wan, “Analysis of TDOA and TDOA/SS based geolocation techniques in a non-line-of-sight environment,” Journal of Communications and Networks, Vol.14, pp.533-539, Oct. 2012.
[55] B. Y. Shikur, M. Farmani and T. Weber, “TOA/AOA/AOD-based 3-D mobile terminal tracking in NLOS multipath environments” Workshop on Positioning Navigation and Communication, pp201-205, Mar. 2012.
[56] S. Venkatraman and J. Caffery, Jr., “Hybrid TOA/AOA techniques for mobile location in non-line-of-sight environments,” in Proc. IEEE Wireless Communications and Networking Conference, vol. 1, pp. 274-278, Mar. 2004.
[57] S. Al-Jazzar, J. Caffery, and H.-R. You, “Scattering-model- based methods for TOA location in NLOS environments,” IEEE Trans. on vehicular Technology, vol. 56, no. 2, pp. 583–593, Mar. 2007.
[58] Chen, Chien-Sheng; Lin, Jium-Ming; Liu, Wen-Hsiung; and Chi, Ching-Lung, “MS Location Estimation with Genetic Algorithm,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E95.A, Issue 1, pp. 305-312, Jan. 2012.
[60] D. Karaboga, An Idea Based On Honey Bee Swarm For Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
[61] W.Y. Szeto, Y. Wu and S.C. Ho, “An Artificial Bee Colony algorithm for the capacitated vehiclerouting problem,” European Journal of Operational Research, vol. 215, pp. 126-135, 2012.
[62] R. S. Rao, S. V. L. Narasimham, and M. Ramalingaraju, “Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm,” Int. J. Elect. Power Energy Syst. Eng., vol. 1, no. 2, 2008.
[63] N. Karaboga, “A new design method based on artificial bee colony algorithm for digital IIR filters,” J. Franklin Inst., vol. 346, no. 4, pp. 328–348, 2009.
[64] P.W. Tsai, J.S. Pan, B.Y. Liao and S.C. Chu, “Enhanced Artificial Bee Colony optimization, International Journal of Innovative Computing,” Information and Control, vol. 5, pp. 5081-5092, 2009.
[65] M. Youssef and A. Agrawala, “Small-scale compensation for WLAN location determination systems,” in Proc. IEEE WCNC, 2003, vol. 3, pp. 1974–1978.
[66] M. Ibrahim and M. Youssef, “An energy-efficient GSM positioning system”, IEEE Trans. Veh. Tech., vol. 61, no. 1, pp. 286-296, 2012.
[67] J. H. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor, The University of Michigan Press, 1975.
[68] D. Karaboga and B. Basturk, “A powerful and efficient algorithm for numeric function optimization: artificial bee colony (ABC) algorithm,” J. Global Optimization, vol. 39, pp. 459–471, 2007.
[69] D. J. Mala, V. Mohan, and M. Kamalapriya, “Automated software test optimization framework-an artificial bee colony optimization-based approach,” Software, IET, vol. 4, no. 5, pp. 334–348, 2010.
[70] S. Venkatraman, J. Caffery, and H.-R. You, “A novel TOA location algorithm using LOS range estimation for NLOS environments,” IEEE Transactions on Vehicular Technology, vol. 53, no. 5, pp. 1515-1524, Sep. 2004.
[71] D. Karaboga and B. Basturk, “On the performance of artificial bee colony (ABC) algorithm,” Appl. Soft Comput., vol. 8, no. 1, pp.687–697, 2008.
[72] P. van Rooyen, M. Lotter, and D. van Wyk, Space-Time Processing for CDMA Mobile Communications. New York: Kluwer, 2000.
[73] P. Moscato, M.G. Norman, “A memetic approach for the travelling, salesman problem – implementation of a computational ecology for combinatorial optimization on message-passing systems,” International conference on parallel computing and transputer application, pp. 177–186, 1992.
[74] Dawkins R. The selfish gene, Oxford : Oxford University Press, 1976.
[75] P. Merz and B. Freisleben, “A Genetic Local Search Ap-proach to the Quadratic Assignment Problem,” in Pro-ceedings of the 7th International Conference on Genetic Algorithms, pp. 465-472, 1997.
[76] K. Ghoseiri, H. Sarhadi, “A memetic algorithm for symmetric travelling salesman problem,” International Journal of Management Science and Engineering Management, Vol. 3, pp. 275-283, Feb. 2008.