臺灣博碩士論文加值系統

「定位精準度」是評量一個定位系統效能最重要的指標，對所有的位置感知服務是根本且重要的。但是，「能源效率」與「定位精準度」這兩個目標，常常會互相抵觸。所以我們提出一個高能源效率的定位服務，此服務能根據使用者現在的移動程度及定位誤差，在不影響到定位正確性的前提下，調整查詢位置的頻率，以減低耗電。
作為一個高能源效率的定位系統，我們的系統藉由外接一個感測器，來幫助系統估計現在使用者的移動程度。再依據所估計的移動程度，在不犧牲定位準確性的前提下，調整查詢位置的頻率，減低耗電。此外，為了要能更加符合應用的需求，我們改善傳統無線電波干涉定位法，以估計更準的位置誤差。因為位置誤差不僅跟使用者的移動程度有關，也跟現在定位誤差有關，所以我們為無線電波干涉定位法設計一個誤差估計模型，來估計此定位誤差。同時也利用此模型所估計的定位誤差，根據定位目標的位置，來選擇最佳的發射點組合，而發展出「適性的無線電波干涉定位法（Adaptive RIP）」，進一步改善無線電波干涉定位法的精準度。
為了能滿足應用對位置精準度的要求，我們的系統積極地調整查詢位置的頻率，以減少耗電。在這個論文中，基於不同定位系統（就是「Zigbee 訊號指紋定位系統」及「適性無線電波干涉定位系統」）的高能源效率定位服務，會被設計、實做及驗證。

One of the most important performance objectives for a localization system is positional accuracy. It is fundamental and essential to general location-aware services. Energy efficiency and positional accuracy, however, are often contradictive goals. We propose to decrease energy consumption without sacrificing significant accuracy by developing an energy-aware localization that adapts the sampling rate to target''s mobility level and current estimation error.
As an energy-aware adaptive localization system, our system actively adapts its sampling rate to conserve energy without sacrificing significant accuracy according to target''s mobility level which is estimated with the help of an additional sensor. Moreover, in order to be more adhering to application''s requirements, we improve the radio interferometric positioning (RIP) method to estimate positional error more accurately. Because the positional error is highly related to not only user mobility level but also current estimation error, we designed an estimation error model to estimate the estimation error of the RIP algorithm and applied it in the design of our energy-efficient localization system. Furthermore, building upon this estimation error model, we devise an adaptive RIP method that selects the optimal sender-pair combination (SPC) according to the locations of targets relative to anchor nodes.
Promising to satisfy an application''s requirements on positional accuracy, our system actively tries to adapt its sampling rate to reduce its energy consumption. In this thesis, energy-aware adaptive localization systems based on different sensor network localization systems, i.e. Zigbee-based fingerprinting positioning system or adaptive RIP system, are designed, implemented, and evaluated.

Acknowledgments iii
Abstract vii
List of Figures xiii
List of Tables xvii
Chapter 1 INTRODUCTION 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chapter 2 RATIONALE 7
2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Positional Error Model . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Energy-Saving Solutions . . . . . . . . . . . . . . . . . . . . . . . . 12
Chapter 3 SENSOR NETWORK POSITIONING SYSTEMS - ZIGBEEBASED
POSITIONING & ADAPTIVE RIP SYSTEMS 14
3.1 Zigbee-Based Fingerprinting Positioning System . . . . . . . . . . . 15
3.2 Adaptive Radio Interferometric Positioning (RIP) System . . . . . . . 16
3.2.1 Background on the radio interferometric positioning system . 17
3.2.2 Estimation error model . . . . . . . . . . . . . . . . . . . . . 24
3.2.3 Design of the adaptive RIP method . . . . . . . . . . . . . . 31
3.2.4 Implementation of the adaptive RIP system . . . . . . . . . . 33
Chapter 4 PERFORMANCE EVALUATION OF ADAPTIVE RIP SYSTEM
& ESTIMATION ERROR MODEL 34
4.1 Experimental Validation of the Estimation Error Model . . . . . . . . 35
4.2 Evaluation of the Adaptive RIP System . . . . . . . . . . . . . . . . 43
4.2.1 Multi-target tracking experiment (with one moving target). . . 44
4.2.2 Multi-target tracking using the adaptive RIP method (all targets
are moving). . . . . . . . . . . . . . . . . . . . . . . . . 47
Chapter 5 DESIGN AND IMPLEMENTATION OF POWER-SAVING METHODS
51
5.1 Underlying Positioning Systems . . . . . . . . . . . . . . . . . . . . 52
5.2 Design of Estimation Error Estimators . . . . . . . . . . . . . . . . . 54
5.3 Design of Mobility Level Estimators . . . . . . . . . . . . . . . . . . 55
5.3.1 Periodic sampling (PS) . . . . . . . . . . . . . . . . . . . . . 56
5.3.2 Adaptive sampling with constant-velocity (ASCV) . . . . . . 56
5.3.3 Sensor-assisted adaptive sampling with mobility detection (SAASMD) 58
5.3.4 Sensor-assisted adaptive sampling with foot-step detection (SAASFD) 59
Chapter 6 PERFORMANCE EVALUATION OF THE ENERGY-EFFICIENT
LOCALIZATION SYSTEM 61
6.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 Impact on Mobility Levels . . . . . . . . . . . . . . . . . . . . . . . 66
6.3 Impact on Application Error Tolerance . . . . . . . . . . . . . . . . . 70
6.4 Impact of Mobility Level on Nonconformance Rate . . . . . . . . . . 73
6.5 Impact of Underlying Positioning Engines . . . . . . . . . . . . . . . 75
6.6 Impact of the Estimation Error Model . . . . . . . . . . . . . . . . . 82
Chapter 7 RELATEDWORK 85
7.1 Energy-Efficient Design . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2 Positioning Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.2.1 Ranging-based methods . . . . . . . . . . . . . . . . . . . . 87
7.2.2 Range-free methods . . . . . . . . . . . . . . . . . . . . . . 88
7.2.3 Error estimation techniques . . . . . . . . . . . . . . . . . . 89
7.3 Sampling Rate Adaptation Techniques . . . . . . . . . . . . . . . . . 91
7.4 Computation Reduction Techniques . . . . . . . . . . . . . . . . . . 93
Chapter 8 CONCLUSION & FUTURE WORK 95
Bibliography 98

[1] 3rd Generation Partnership Project. In 3GPP TS 05.05, http://www.3gpp.org/.
[2] P. Bahl and V. N. Padmanabhan. RADAR: An In-Building RF-Based User Location and Tracking System. In Proc. Conf. Computer Communications (Infocom ’00), pages 775–784, March 2000.
[3] H. Balakrishnan and R. Katz. Explicit Loss Notification andWirelessWeb Performance. In Proc. 41th IEEE Int’l Telecommunications Conference (GLOBECOM ’98), November
1998.
[4] E. Blanton, M. Allman, K. Fall, and L. Wang. IETF RFC 3517: A Conservative Selective Acknowledgment (SACK)-Based Loss Recovery Algorithm for TCP, April 2003. http://gim.org.pl/rfcs/rfc3517.html.
[5] M. Busse, T. Haenselmann, and W. Effelsberg. TECA: A Topology and Energy Control Algorithm for Wireless Sensor Networks. In Proc. 9th ACM Int’l Symp. Modeling analysis and simulation of wireless and mobile systems (MSWiM ’06), pages 317–321, October 2006.
[6] L.-W. Chan, J.-R. Chiang, C.-N. Ke, Y.-C. Chen, H.-H. Chu, and J. Hsu. Collaborative Localization – Enhancing WiFi-Based Position Estimation with Neighborhood Links in
Clusters. In Proc. Int’l Conf. Pervasive Computing Pervasive ’06), pages 50–66, May 2006.
[7] Y. Chen, Q. Yang, J. Yin, and X. Chai. Power-Efficient Access-Point Selection for Indoor Location Estimation. 18(7):877–888, July 2006.
[8] Y.-C. Chen, J.-R. Chiang, H.-H. Chu, P. Huang, and A. W. Tsui. Sensor-Assisted Wi-Fi Indoor Location System for Adapting to Environmental Dynamics. In Proc. ACM Int’l
Symp. Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM ’05), pages 118–125, October 2005.
[9] L. Cong and W. Zhuang. Hybrid TDOA/AOA Mobile User Location for Wideband CDMA CEllular Systems. 1(3):439–447, July 2002.
[10] N. Dragos and B. Nath. Ad Hoc Positioning System APS Using AoA. In Proc. Conf. Computer Communications (IEEE Infocom ’03), pages 1734–1743, April 2003.
[11] L. Girod, M. Lukac, V. Trifa, and D. Estrin. The Design and Implementation of a Self-Calibrating Acoustic Sensing Platform. In Proc. 4th Int’l Conference Conf. Embedded
Networked Sensor Systems (SenSys ’06), pages 71–84, October 2006.
[12] G. P. Halkes, T. van Dam, and K. G. Langendoen. Comparing Energy-Saving MAC Protocols forWireless Sensor Networks. Mobile Networks and Applications, 10(5):783–791, October 2005.
[13] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher. Range-Free Localization Schemes in Large-Scale Sensor Networks. In Proc. 9th annual Int’l Conf. Mobile
computing and networking (MOBICOM ’03), pages 81–95, September 2003.
[14] C. E. Jones, K. M. Sivalingam, P. Agrawal, and J. C. Chen. A Survey of Energy Efficient Network Protocols forWireless Networks. ACM Wireless Networks, 7(4):343–358,
August 2001.
[15] K. Klues, G. Xing, and C. Lu. Link Layer Support for Unified Radio Power Management in Wireless Sensor Networks. In Proc. 6th Int’l Conf. Information processing in sensor
networks (IPSN ’07), pages 460–469, April 2007.
[16] B. Kusy, G. Balogh, A. Ledeczi, J. Sallai, and M. Maroti. inTrack: High Precision Tracking of Mobile Sensor Nodes. In Proc. 4th European Workshop on Wireless (EWSN
’07), pages 51–66, January 2007.
[17] B. Kusy, A. Ledeczi, and X. Koutsoukos. Tracking Mobile Nodes Using RF Doppler Shifts. In Proc. 5th Int’l Conf. Embedded Networked Sensor Systems (SenSys ’07), November 2007.
[18] B. Kusy, M. Maroti, G. Balogh, P. Volgyesi, J. Sallai, A. Nadas, A. Ledeczi, and L. Meertens. Node Density Independent Localization. In Proc. 5th Int’l Conf. Information Processing in Sensor Networks (IPSN/SPOTS 06), pages 441–448, April 2006.
[19] B. Kusy, J. Sallai, G. Balogh, A. Ledeczi, V. Protopopescu, J. Tolliver, F. DeNap, and M. Parang. Radio Interferometric Tracking of Mobile Wireless Nodes. In Proc. 5th Int’l Conf. Mobile systems, applications and services (MobiSys ’07), pages 139–151, June 2007.
[20] S.-W. Lee, S.-Y. Cheng, J. Hsu, P. Huang, and C.-W. You. Emergency Care Management with Location-Aware Services. In Proc. IEEE Int’lWorkshop on Location Based Services for Health Care (LOCARE ’06), November 2006.
[21] M. Li and Y. Liu. Rendered Path: Range-Free Localization in Anisotropic Sensor Networks With Holes. In Proc. 13th annual Int’l Conf. Mobile computing and networking (MOBICOM ’07), pages 51–62, September 2007.
[22] T.-H. Lin, P. Huang, H.-H. Chu, H.-H. Chen, and J.-P. Chen. Enabling Energy-Efficient and Quality Localization Services. In Proc. IEEE Int’l Conf. Pervasive Computer and
Communications (PerCom 06), Work In Progress Session, pages 624–627, March 2006.
[23] J. Liu, Y. Zhang, and F. Zhao. Robust Distributed Node Localization with Error Management. In Proc. 7th ACM Int’l Symp. Mobile ad hoc networking and computing (MobiHoc’06), pages 250–261, May 2006.
[24] K. Lorincz and M. Welsh. MoteTrack: A Robust, Decentralized Approach to RF-Based Location Tracking. In Proc. Int’l Workshop on Location- and Context-Awareness (LoCA’05), pages 63–82, May 2005.
[25] J. Ma, Q. Zhang, C. Qian, and L. M. Ni. Energy-Efficient Opportunistic Topology Vontrol in Wireless Sensor Networks. In Proc. 1st Int’l Mobisys Workshop Mobile opportunistic
networking (MobiOpp ’07), pages 33–38, June 2007.
[26] D. Madigan, E. Elnahrawy, R. P. Martin, W.-H. Ju, and P. Krishnan. Bayesian Indoor Positioning Systems. In Proc. 24th Annual Joint Conf. IEEE Computer and Communications Societies (Infocom ’05), pages 1217–1227, March 2005.
[27] M. Maroti, B. Kusy, G. Balogh, P. Volgyesi, A. Nadas, K. Molnar, S. Dora, and A. Ledeczi. Radio-Interferometric Geolocation. In Proc. 3rd Int’l Conf. Embedded Networked
Sensor Systems (SenSys ’05), pages 1–12, November 2005.
[28] D. Moore, J. Leonard, D. Rus, and S. Teller. Robust Distributed Network Localization with Noise Range Measurements. In Proc. 2nd Int’l Conference Conf. Embedded Networked Sensor Systems (SenSys ’04), pages 50–61, November 2004.
[29] L. M. Ni, Y. Liu, Y. C. Lau, and A. P. Patil. LANDMARC: Indoor Location Sensing Using Active RFID. In Proc. IEEE Int’l Conf. Pervasive Computing and Communications (PerCom ’03), pages 407–415, March 2003.
[30] D. Niculescu. Positioning in Ad Hoc Sensor Networks. IEEE Tran. Signal processing, 18(4):24–29, July 2004.
[31] S. Pattem, S. Poduri, and B. Krishnamachari. Energy-Quality Tradeoffs in Sensor Tracking: Selective Activation with Noisy Measurements. In Proc. 2nd Int’l Workshop on Information Processing in Sensor Networks (IPSN ’03), pages 32–46, April 2003.
[32] N. Patwari, A. O. H. III, M. Perkins, N. S. Correal, and R. J. O’Dea. Relative Location Estimation in Wireless Sensor Networks. IEEE Tran. Signal Processing, Special Issue on Signal Processing in Networking, 51(9):2137–2148, August 2003.
[33] N. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket Location-Support system. In Proc. 6th Annual ACM Int’l Conf. Mobile Computing and Networking(MobiCom’00), pages 32–43, August 2000.
[34] V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves. Energy-Efficient, Collision-Free Medium Access Control for Wireless Sensor Networks. Wireless Networks, 12(1):63–78, 2006.
[35] C. Randell, C. Djiallis, and H. Muller. Personal Position Measurement Using Dead Reckoning. In Proc. 7th IEEE Int’l Symp. Wearable Computers(ISWC ’03), pages 166–173,
October 2005.
[36] RIPS. http://tinyos.cvs.sourceforge.net/tinyos/tinyos-1.x/contrib/vu/apps/ripsonehop/.
[37] K. R’omer. The Lighthouse Location System for Smart Dust. In Proc. 1st Int’l Conf. Mobile systems, applications and services (MobiSys ’03), pages 15–30, May 2003.
[38] A. Savvides, C. C. Han, and M. B. Srivastava. Dynamic Fine-grained Localization in Ad-Hoc Networks of Sensors. In Proc. 7th annual Int’l Conf. Mobile computing and networking (MOBICOM ’01), pages 166–179, July 2001.
[39] G. Schindler, C. Metzger, and T. Starner. A Wearable Interface for Topological Mapping and Localization in Indoor Environments. In Proc. Int’l Workshop on Location- and
Context-Awareness (LoCA ’06), pages 64–73, May 2006.
[40] E. Shih, S.-H. Cho, N. Ickes, R. Min, A. Sinha, A.Wang, and A. Chandrakasan. Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks. In Proc. 7th annual Int’l Conf. Mobile computing and networking (MOBICOM’01), pages 272–287, July 2001.
[41] V. Shnayder, M. Hempstead, B.-R. Chen, G. W. Allen, and M. Welsh. Simulating the Power Consumption of Large-Scale Sensor Network Applications. In Proc. 2nd ACM Conf. Embedded Networked Sensor Systems (SenSys ’04), pages 188–200, November 2004.
[42] R. Stoleru, T. He, J. a. Stankovic, and D. Luebke. A High-Accuracy, Lowcost Localization System forWireless Sensor Networks. In Proc. 3rd Int’l Conference Conf. Embedded Networked Sensor Systems (SenSys ’05), pages 13–26, November 2005.
[43] S. Tilak, V. Kolar, N. B. Abu-Ghazaleh, and K.-D. Kang. Dynamic Localization Control for Mobile Sensor Networks. In Proc. IEEE Int’l Workshop on Strategies for Energy Efficiency in Ad Hoc and Sensor Networks (IWSEEASN ’05), April 2005.
[44] F. Wang, L. Qiu, and S. S. Lam. Probabilistic Region-Based Localization for Wireless Networks. ACM SIGMOBILE Mobile Computing and Communications Review, 11(1):3–14, January 2007.
[45] J.Winter, Y. Xu, andW.-C. Lee. Prediction-Based Strategies for Energy Saving in Object Tracking Sensor Networks. In Proc. IEEE Int’l Conf. Mobile Data Management (MDM’04), pages 346–357, January 2004.
[46] C. R. Wren and E. M. Tapia. Toward Scalable Activity Recognition for Sensor Networks. In Proc. Int’l Workshop on Location- and Context-Awareness (LoCA ’06), pages 168–185, May 2006.
[47] M. Youssef and A. Agrawala. Handling Samples Correlation in the Horus System. In Proc. Conf. Computer Communications (Infocom ’04), pages 1023–1031, March 2004.
[48] M. Youssef, A. Agrawala, and A. U. Shankar. WLAN Location Determination via Clustering and Probability Distributions. In Proc. IEEE Int’l Conf. Pervasive Computing and Communications (PerCom ’03), page 143, 2003.
[49] D. Zhang, J. Ma, Q. Chen, and L. M. Ni. An RF-Based System for Tracking TransceiverFree Objects. In Proc. IEEE Int’l Conf. Pervasive Computing and Communications (Per-Com ’07), pages 135–144, March 2007.
[50] Z. Zhong and T. He. MSP: Multi-Sequence Positioning of Wireless Sensor Nodes. In Proc. 5th Int’l Conference Conf. Embedded Networked Sensor Systems (SenSys ’07), November 2007.
[51] G. Zhou, T. He, and J. A. Stankovic. Impact of Radio Irregularity on Wireless Sensor Networks. In Proc. 2rd Int’l Conf. Mobile systems, applications and services (MobiSys’04), pages 125–138, June 2004.