臺灣博碩士論文加值系統

感測器網路是現在一個新興而熱門的研究領域，室內追蹤定位為其中一個極重要的應用。現在有釵h相關研究主題在於設計與實現感測器網路的追蹤與定位，比如資料的融合處理，感測器節點間的傳輸協議，節省感測器能源的方式...等等。其中感測器網路中最重要的也是最關鍵的一個環節就是節省能源的方式。

雖然現在有釵h研究主題在於如何節省感測器網路的整體耗能，但是這些研究幾乎都忽略了感測器網路中最重要的一環：由於ＲＦ訊號的特性以及感測器網路物理上的限制，使得在偵測目標物時，容易產生釵h訊號或是量測上的誤差。而其中可能解決辦法就是：１.增加感測目標物的次數，以避免過大的誤差　２.開啟更多的感測器節點以降低誤差

但是在於即時的追蹤系統中，目標物是隨時在移動的，也就是隨時在改變自身的位置，因此我們無法使用增加感測次數來減少誤差。而若使用第２種方法則是會使整體感測器網路耗能增加而減少感測器存續時間。

因此基於於感測器網路物理上的限制與追蹤目標的及時性以及整體感測器網路節能考量，我們設計了結合灰色理論與權重最小平方近似法與感測器定位理論，建立可調式演算法於感測器網路，近而取得目標追蹤與整體感測器節能上的平衡點。

Target tracking sensor network is considered as one of the killer application for sensor network system. There are a lot of research issues in design and implement of the target tracking sensor network, such as data fusion, routing, and energy conservation, and etc. Energy conservation is one of the most important issues.

Unfortunately, the physical limitation on high inaccuracy of radio signal is a challenge for target tracking sensor network. Many researches neglect this critical factor and may underestimate the total energy consumption of the sensor network system. The possible improvements for the causes from radio signals quality are either triggering the sensor more times or activate multiple sensors.

However, the object will change its position and state anytime. It might not have more opportunity for the sensor nodes to detect twice at that time and position. For the consideration of energy conservation, the less active nodes, the more energy saved, it is a tradeoff between accuracy and energy.

Based on the physical limitation of radio signals and for real time monitoring the moving object, we develop an adaptive grey-fuzzy with weighted least square predictor to improve the accuracy of moving object trace.

摘要 i
Abstract ii
誌謝……………...……………………………………………………………………iii
Chapter 1 Introduction 1
1.1 Motivation 2
1.2 Objectives 4
1.3 Thesis Organization 6
Chapter 2 Literature Review 7
2.1 Introduction of Present Location Sensing Technologies 7
2.2 Important factor of Location system properties 8
2.2.1 Location Computation 8
2.2.2 Accuracy of Location system 9
2.2.3 Scale of Location system 10
2.2.4 Cost of Location system 11
2.2.5 Limitations of Location system 11
2.3 A Survey of Location systems 12
2.3.1 Active Badge 12
2.3.2 Cricket 14
2.3.3 Dust Network 16
2.3.4 RADAR 17
2.3.5 Motion Star Magnetic Tracker 18
2.3.6 Easy Living 20
2.3.7 Smart Floor 20
2.4 Wireless Local Positioning System 21
2.4.1 Wireless Positioning Technologies 22
2.4.2 Measurement Principles of Wireless Positioning System 24
2.4.3 The Solution Wireless of Positioning System 29
Chapter 3 Classic Location Algorithm and Energy Saving System 33
3.1 Triangular Algorithm 33
3.2 K-nearest Neighbors Algorithm 36
3.3 Smallest M-Vertex Polygon Algorithm 39
3.4 Triangular Interpolation and Extrapolation Algorithm 40
3.5 Multi-step Asaptive Sensor Scheduling Algorithm 42
3.6 Predection-based for Energy Saving in Object Tracking Sensor Network 45
Chapter 4 Zigbee and Experimental Hardware 48
4.1 Zigbee 48
4.1.1 The Comparison of Different Wireless Technology 49
4.1.2 The Features of Zigbee 50
4.1.3 Data Packet Description 52
4.1.4 Zigbee Device Types ZigBee networks use three device types: 53
4.1.5 Zigbee Network layer 54
4.1.6 Typical Zigbee-enabled Device 56
4.2 CC2420 Zigbee DK Development Kit 57
4.2.1 Hardware of CC2420DBK Demonstration Board kit 57
4.2.2 CC2420 libraries 60
Chapter 5 Adaptive Weight Prediction Method 64
5.1 Framework of Adaptive Weight Prediction System 65
5.2 Wireless Location System 68
5.2.1 RF Signal Propagation 68
5.2.2 Range Estimation 68
5.2.3 Maximum Likelihood Formulation 70
5.2.4 Location Coordination System 73
5.3 Weight Least Square 74
5.4 Grey Prediction Method 77
5.4.1 Grey Model GM (1, 1) 78
Chapter 6 Experiment Result 83
6.1Experiment Results 83
Chapter 7 Contributions and Conclusions 89

[1] J. Hightower, G. Borriello, “Location systems for ubiquitous computing,” IEEE transaction on Location Aware computing, issue 8, vol. 34, pp.:57 – 66, Aug. 2001
[2] G. Borriello, M. Chalmers, A. LaMarca, P. Nixon, “Delivering REAL-WORLD Ubiquitous Localization systems,” Communications of the ACM, Vol. 48 Issue 3, March 2005
[3] http://wwwgarmin.com/aboutGPS/
[4] M. Hazas, J. Scott, and J. Krumm, “Location–aware computing comes of age.” IEEE Computer, Volume 37, Issue 2, pp. 95 – 97, Feb. 2004
[5] M.D. Rodriguez, J. Favela, E.A. Martinez, M.A. Munoz, “Location-aware access to hospital information and services,” IEEE Transactions on Information Technology in Biomedicine, Vol. 8, Issue 4, pp. 448 – 455, Dec. 2004
[6] R. Want et al., “The Active Badge Localization system” ACM Trans. Information system, pp.91-102, Jan. 1992
[7] http://www.uk.research.att.com/ab.html
[8] A. Harter et al., “A Distrusted localization system for the Active Office,” IEEE Network, pp. 62-70, Feb. 1994
[9] http://nms.lcs.mit.edu/cricket/
[10] P. Bahl and V. Padmanabhan, “RADAR: An In-Building RF-based User Location and Tracking system,” Proc. IEEE Infocom 2000, IEEE CS Press, pp. 774-748, 2000
[11] F. Raab et al., “Magnetic Position and Orientation Tracking System,” IEEE trans. Aerospace and Electronic systems, pp. 709-717, Sept. 1979
[12] Technical Description of DC Magnetic Trackers, Ascension Technology Corp., Burlington, 2001.
[13] http://research.microsoft.com/easyliving/
[14] J. Krumm et al., “Multi-Camera Multi-Person Tracking for Easy Living,” Proc. 3rd IEEE Int’l Workshop Visual Surveillance, IEEE press, Piscataway, pp.3-10, 2000
[15] R. J. Orr and G.D. Abowd, “The Smart Floor: A Mechanism for Natural User Identification and Tracking,” Proc. 2000 Conf. Human Factors in Computing Systems, New York, 2000
[16] M. Vossiek, L. Wiebking, P.Gulden, J. Wieghardt; C. Hoffmann, P. Heide,” Wireless Local Positioning,” IEEE Microwave Magazine, vol. 4, Issue 4 pp.77 – 86, Dec. 2003
[17] C. Drane, M. Macnaughtan, and C. scott, “Positioning GSM telephones,” IEEE Commun. Mag., vol. 36, pp: 46-59, Apr. 1998.
[18] J. Latvala, J. Syrjarinne, H. Ikonen, and J. Niittylahti, “Evaluation of RSSI-based human tracking,” in Proc. 2000 European Signal Processing Conf., vol. 4, pp. 2273-2276, Sept. 2000
[19] K. Feher, Wireless Digital Communication, Englewood Cliffs, NJ: Prentice Hall, 1995
[20] M. Kossel, H.R. Benedickter, R. Peter, and W. Bachtold ”Microwave backscatter modulation systems,“ in Proc. 2000 IEEE Int. Microwave Symp. Dig., pp. 1427-1430, June 2000
[21]J. Thornton and D.J. Edwards, “Range measurement using modulated retro-reflectors in FM radar system,” IEEE Microwave Guided Wave Lett., vol. 10, pp. 380-382, Sept. 2000.
[22]M.M. Kaleja. P. Heide, and E.M. Biebl, “Imaging RFID system at 24 gigahertz for object localization,” in Proc. 1999 IEEE Int. Microwave Symp. Dig., vol. 10, pp. 1427-1430, June 2000
[23] C. Luxey and j.-M. Laheurte, “A retrodirective transponder with polarization duplexing for dedicated short range communications,” IEEE Trans Microwave Theory Tech., vol. 47, pp. 1910-1915, 1999
[24]K. Pahlavan, X. Li, M. Ylittila, R. Chana, and M. Lavta-acho , “An overview of wireless indoor geolocation technique and systems,” Lecture Notes in Computer Science, no. 1818, pp.1-13, Aug. 2000.
[25] J. J. Caffery, and G.L. Stuber, “Overview of radiolocation in CDMA cellular systems,” IEEE Commun. Mag., vol. 36, pp.38-45, Apr. 1998
[26]B. Ludden and L. Lopes, “Cellular based location technologies for UMTS: A comparison between IPDL and TA-IPDL,” in Proc. 2000 IEEE 51st Vehicular Technology Conf.., vol. 2, pp.1348-1953, May 2000.
[27] X. Li, K. Pahlavan, M. Latvaaho, and M. Ylianttila, “Comparison of indoor geolocation methods in DSSS and OFDM wireless LAN systems,” in Proc 2000 IEEE 52nd vehicular Technology Conf., vol. 6, p. 3015-3020, Sept, 2000
[28] http:// www.bluetooth.org
[29]J. Werb and C. Lanzl, “Designing a positioning system finding things and people indoors,” IEEE Spectr., vol. 35, pp. 71-78, Sept 1998
[30] http://findarticles.com
[31]R. Flerming, C. Kushner, G. Roberts, and U. Nandiwada, “Rapid acquisition for ultra-wideband localizer,” in Proc. IEEE Conf. Ultra Wideband Systems and Technologies, pp. 245-249, May 2002
[32]A. Stelzer, A. Fischer, F. Weinberger, and M. Vossiek, “RF-sensor for a local position measurement system,“ presented at. SPIE 8th NDE Symp., Sam Diego, CA, 2003.
[33] A. Ali, L.A. Latiff, N. Fisal, “GPS-free Indoor Location Tracking in Mobile Ad Hoc Network (MANET) Using RSSI, ” In proceedings of the RF and Microwave (RFM), pp. 251-255, Oct. 2004.
[34] D. Pandya, R. Jain, and E. K Lupu, “Indoor Location Using Multiple Wireless Technologies,” In Proceedings of the IEEE Personal, Indoor and Mobile Radio Communications, vol.3, pp. 2208 – 2212, Sept. 2003.
[35] Y. Gwon; R. Jain, T Kawahara, “Robust indoor location estimation of stationary and mobile users” In Proceedings of the IEEE Computer and Communications Societies(INFOCOM), vol. 2, pp. 1032 – 1043, March 2004
[36] P. Prasithsangaree, P. Krishnamurthy, and Chrysanthis P., K. “On Indoor Position Location with Wireless LANs,” In Proceedings of the IEEE Personal, Indoor and Mobile Radio Communications (PIMRC), vol. 2, pp.720 – 724, Sept. 2002
[37] Y. Gwon, and R. Jain, “Error Characteristics and Calibration–free Techniques for Wireless LAN-based Location Estimation,” In Proceedings of MobiWac, section 1 pp, 2-9, Oct. 1, 2004
[38] http://www.embedded.com/showArticle.jhtml?articleID=18902431
[39] http://www.cambridgeconsultants.com/wt_q_ZigbeeTech.shtml
[40] Chipcon, Inc., “SmartRF CC2420DBK Demonstration Board Kit User Manual Rev. 1.3,” www.chipcon.com at Web Site, 2004
[41] N. Patwari, A.O. Hero, III, M. Perkins, N.S Correal, R.J. O’Dea,” Relative location estimation in wireless sensor networks,” IEEE Trans. Signal Processing, vol. 51 , pp. 2137 - 2148, Aug. 2003
[42] P.-C. Chen, “A non-line-of-sight error mitigation algorithm in location estimation,” In Proceedings of IEEE Conference WCNC (Wireless Communications and Networking, vol.1, pp. 316 – 320, Sept. 1999
[43] R. Fleming and C. Kushner, “Low-power, miniature, distributed position location and communication devices using ultra-wideband, nonsinusoidal communication technology,” Technical report, Aetherwire Inc, Swmi-Annual Technical report, ARPA Contract JFBI-94-058, July 1995
[44]D. McCrady, L. Doyle, H. Forstrom, T. Demosy, and M. Martorana., “Mobile ranging with low accuracy clocks,” IEEE trans. on Microwave Theory and Techniques, 48(6):951-957, June 2000.
[45] J. L. Deng, “Introduction to Grey System theory, ” The Journal of Grey Systems, Vol. 1, No. 1, pp. 1-24, 1989
[46] J. L. Deng, Grey Systems Theory and Application, Gauli, 2000
[47] S. J. Huang, and C. L. Huang, “Control of an Inverted Pendulum Using Grey Prediction Model,” IEEE Transactions on Industry Application, Vol. 36m pp, 452-458. , 2000
[48] C. H. Lee, and C. J. Yu, “An intelligent handoff algorithm for wireless communication systems using grey prediction and fuzzy decision system,” In proceedings of IEEE Networking, Sensing and Control Conference, vol. 1, pp. 541 – 546, March 2004.
[49] P. Y. Gilliéron, D. Büchel, I. Spassov, B. Merminod, Swiss Federal Institute of Technology (EPFL), “Indoor Navigation Performance Analysis,” http://topo.epfl.ch/publications/epfl_gnss04.pdf at Web Site, 2004
[50] S. Kim; J. H. Kim, “Adaptive fuzzy-network-based C-measure map-matching algorithm for car navigation system,” IEEE Transactions on Industrial Electronics, Vol. 48, Issue 2, pp. 432 – 441, April 2001.
[51] D. Yang, J. Wang, and B. Cai, “Application of Information Integration in ITS,” The 2nd International Workshop on Autonomous Decentralized System, pp.246-253, Nov. 2002
[52]S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong “Tiny aggregate queries in ad-hoc sensor networks,” In ACM Symposium on Operating System Design and Implementation (OSDI), Dec. 2002.
[53]S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. “The design of an acquisitional query processor for sensor networks,” In 2003 ACMSIGMOD international conference on Management of data, pages 491 – 502, San Diego, California, June 2003.
[54]P. N. Hero, A.O. Perkins, M. Correal, N.S. O''Dea, and R.J., “Relative location estimation in wireless sensor networks,” IEEE Trans. Signal Processing, vol. 51 , pp. 2137 - 2148, Aug. 2003
[55]P. C. Chen, “A non-line-of-sight error mitigation algorithm in location estimation,” In Proceedings of IEEE Conference WCNC (Wireless Communications and Networking, vol.1, pp. 316 – 320, Sept. 1999
[56]K. Sohrabi and G. J. Pottie. “Performance of a novel self-organization protocol for wireless ad-hoc sensor networks,” In IEEE Vehicular Technology Conference, volume 2, pages 1222–1226, 1999.
[57]W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks”; System Sciences, Proceedings of the 33rd Annual Hawaii International Conference vol.2 Page(s):10 Jan. 2000
[58]E. H. Miller, “A note on reflector arrays (Periodical style—Accepted for publication),” IEEE Trans. Antennas Propagat., to be published.
[59]C. J. Kaufman, C. H. Lee, and C. J. Yu, “An intelligent handoff algorithm for wireless communication systems using grey prediction and fuzzy decision system,” In proceedings of IEEE Networking, Sensing and Control Conference, vol. 1, pp. 541 – 546, March 2004.
[60]D. Estrin, R. Govindan, J. Heidemann, and S. Kumar. Next century challenges: Scalable coordination in sensor networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, pages 263– 270, Seattle, Washington, USA, August 1999.
[61]S. Goel and T. Imielinski. Prediction-based monitoring in sensor networks: taking lessons from MPEG. ACM Computer Communication Review, vol. 31(5), October 2001.
[62]W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In IEEE Proceedings of the Hawaii International Conference on System Sciences (HICSS), January 2000.
[63]Y. B. Ko and N. H. Vaidya. “Location-aided routing (LAR) in mobile ad hoc networks,” In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), pages 66–75, 1998.
[64]J. Rabaey, J. Ammer, T. Karalar, S. Li, B. Otis, M. Sheets, and T. Tuan. Picoradios for wireless sensor networks: the next challenge in ultra-low-power design. In Proceedings of the International Solid-State Circuits Conference, San Francisco, CA, February 2002.
[65]J. M. Rabaey, M. J. Ammer, J. L. da Silva Jr., D. Patel, and S. Roundy. Picoradio supports ad hoc ultra-low power wireless networking. IEEE Computer, vol. 33(7), pages 42–48, July 2000.
[66]L. C. Zhong, R. Shah, C. Guo, and J. Rabaey. An ultra-low power and distributed access protocol for broadband wireless sensor networks. In IEEE Broadband Wireless Summit, USA, May 2001.
[67]L. Clare, G. Pottie, and J. Agre. Self-organizing distributed sensor networks. In The International Society for Optical Engineering, pages 229–237, USA, April 1999.
[68]G. Pei and C. Chien. “Low power TDMA in large wireless sensor networks.” In Military Communications Conference, pages 347–351, USA, Oct. 2001.
[69]W. Xiao, L. X. Shue, L. Shue “Multi-step adaptive sensor scheduling for target tracking in wireless sensor networks,” Acoustics, Speech and Signal Processing, 2006. Volume 4, Page(s):IV – IV Toulouse-France, May, 2006
[70]Y. Xu, J. Winter and W. C. Lee, “Prediction-based for Energy Saving in Object Tracking Sensor Network,” in 2004 IEEE International Conference in Mobile Data Management. USA, January, 2004