臺灣博碩士論文加值系統

　　近來在無線通訊與電子技術的進展下, 使得無線感測器這種低成本、低耗電的多功能偵測儀器漸漸的普及開來。這種微小的無線感測器的功能包含：偵測資料、資料處理、無線通訊。藉由一大群的無線感測器部署在環境週遭收集環境資料, 透過彼此的互相溝通傳輸可以將資料傳回特定的位置。

　　使用者會關心到底sensor nodes部署的環境之中, 特定的特徵資料發生在哪些區域。利用sensor network找尋並詳細的紀錄這些跟著時間改變的特徵區域, 可以省力且快速的幫助科學家或其他專業人員了解是什麼因素影響這些特徵區域的分佈。複合特徵查詢, 是指一種要找在哪些區域中同時具有多種不同的特徵的查詢。複合特徵查詢在sensor applications裡面是相當普遍的, 例如生物學家觀察鳥類棲息地、自動化環境控制系統, 所以在這些sensor applications裡面, 處理複合特徵查詢便成為一個相當關鍵的運算。

　但是因為sensor nodes有限的電源, 必須在進行複合特徵查詢的處理時盡量的減低傳輸的次數; 而且環境中的現象會隨著時間變動, 要能隨時抓住各個特徵區域的變化情形。本論文提出了一個可以在監測環境不斷變動的環境中, 有效率處理複合特徵查詢的演算法。我們根據sensor nodes所偵測到的資料, 來決定要如何建造處理composite feature discovery的searching structure, 才能節省最多的能源。同時也利用feature分佈的特性, 調整searching structure使能在收集這些composite feature data時能夠有好的aggregation效果。最後我們也以實驗的結果證明我們所提出的方法多數的情況下都有很好的表現。

　In the past few years, due to the development of wireless communication and microelectromechanical system technology, the wireless sensor has been an emerging technology. The functions of this tiny wireless sensor include: detecting data, data processing, wireless communication.Deploying a lot of wireless sensors in the environment, we can collect those detected data via sensor nodes.

　Using sensor networks to find and record the time-changing feature regions can help scientists and other professionals realize what factors influence the distribution of these feature regions. Composite feature query is a query that finds which regions have multiple features simultaneously.

　Because of the limited energy of sensor nodes and dynamic environment, we must reduce the communication cost during composite feature query processing. In this thesis, we propose an algorithm that can efficiently process composite feature queries in a variable environemnt. According to the detected data by sensor nodes, we build an efficient searching structure for composite feature discovery in a most energy-saving manner. Finally, the performance results show that the proposed algorithm indeed performs better than other traditional methods in most situations.

Abstract i
Acknowledgements iii
Table of Contents iv
Table of Figures vii
Table of Tables x
Table of Algorithms xi

1 Introduction 1
1.1 An example of composite feature discovery . . . . . . . . . 2
1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis organization . . . . . . . . . . . . . . . . . . . . . . 6

2 System Model and Problem Statement 7
2.1 Wireless sensor network environment . . . . . . . . . . . . 7
2.2 Data model for environment phenomenon . . . . . . . . . . 8
2.2.1 Characteristics of environment phenomenon . . . . 9
2.2.2 Feature query . . . . . . . . . . . . . . . . . . . . . 11
2.3 Problem statement: composite feature discovery . . . . . . 13

3 Energy-sensitive Composite Feature Discovery 17
3.1 The design of energy-sensitive composite feature discovery 18
3.2 Feature-aware structure for composite feature discovery . . 23
3.2.1 Basic idea of constructing feature-aware structure . 23
3.2.2 Constructing local searching structure . . . . . . . 25
3.2.3 Making feature sketches and forming FA structure . 34
3.3 Feature-aware structure with adaptive topology recon guration
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.1 The design direction of adaptive topology recon guration
. . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.2 Adaptive topology recon guration . . . . . . . . . . 42
3.4 Merging scattered searching structures . . . . . . . . . . . 45
3.4.1 Determining the similarity of feature graphs . . . . 48
3.4.2 Merging similar feature graphs . . . . . . . . . . . . 49
3.5 Composite feature query processing using FA structure . . 50
3.5.1 One shot composite feature query . . . . . . . . . . 52
3.5.2 Continuous composite feature query . . . . . . . . . 55

4 Performance Evaluation 58
4.1 Performance evaluation model . . . . . . . . . . . . . . . . 59
4.1.1 Sensor network environment . . . . . . . . . . . . . 59
4.1.2 Feature distribution model . . . . . . . . . . . . . . 60
4.2 Compared approaches . . . . . . . . . . . . . . . . . . . . 65
4.3 Evaluation and analysis . . . . . . . . . . . . . . . . . . . 66
4.3.1 Comparison in the static feature distributions . . . 66
4.3.2 Comparison in the dynamic feature distributions . . 82
4.4 Evaluation results summary . . . . . . . . . . . . . . . . . 89

5 Beyond Composite Feature Discovery 91
5.1 Result aggregation with redundancy removal . . . . . . . . 92
5.2 E cient sink-oriented result collection . . . . . . . . . . . 93
5.3 Multiple queries optimization . . . . . . . . . . . . . . . . 94
5.4 Feature region estimation . . . . . . . . . . . . . . . . . . 95
5.5 In-network feature mining . . . . . . . . . . . . . . . . . . 97

6 Related Work 98
6.1 Sensor feature extraction . . . . . . . . . . . . . . . . . . . 98
6.2 Sensor range query . . . . . . . . . . . . . . . . . . . . . . 100

7 Conclusions 102

Bibliography 103

Biography 112

[AFF+03] Anastassia Ailamaki, Christos Faloutsos, Paul S. Fischbeck,
Mitchell J. Small, and Jeanne VanBriesen. An environmental
sensor network to determine drinking water quality and security.
ACM SIGMOD Record, 32(4):47-52, December 2003.

[ASSC02] Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam,
and Erdal Cayirci. A survey on sensor networks. IEEE Communications Magazine, 40(8):102-114, August 2002.

[BBB04] Jenna Burrella, Tim Brooke, and Richard Beckwith. Vineyard
computing: Sensor networks in agricultural production. IEEE
Pervasive Computing, 3(1):38-45, January - March 2004.

[BK00] H. T. Kung Brad Karp. Gpsr: Greedy perimeter stateless
routing for wireless networks. In Proceedings of the 6th International Conference on Mobile Computing and Networking
(MobiCom'00), pages 243-254, Boston, Massachusetts, USA,
August 6-11 2000.

[BK01] Suman Banerjee and Samir Khuller. A clustering scheme for
hierarchical control in multi-hop wireless networks. In Proceedings
of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'01), pages
1028-1039, Anchorage, Alaska, USA, April 22-26 2001.

[CEE+01] Alberto Cerpa, Jeremy Elson, Deborah Estrin, Lewis Girod,
Michael Hamilton, and Jerry Zhao. Habitat monitoring: Application
driver for wireless communications technology. In
Proceedings of the ACM SIGCOMM Workshop on Data Com-
munications in Latin America and the Caribbean, pages 20-41,
Costa Rica, April 2001.

[CG03] Krishna Kant Chintalapudi and Ramesh Govindan. Localized
edge detection in sensor fields. Ad Hoc Networks, Special Issue:
Sensor Network Protocols and Applications, 1(2-3):273-291,
September 2003.

[CK03] Chee-Yee Chong and S.P. Kumar. Sensor networks: Evolution,
opportunities, and challenges. Proceedings of the IEEE,
91(8):1247-1256, August 2003.

[DCXC05] Min Ding, Dechang Chen, Kai Xing, and Xiuzhen Cheng. Localized
fault-tolerant event boundary detection in sensor networks.
In Proceedings of the 24rd Annual Joint Conference
of the IEEE Computer and Communications Societies (InfoCom'05), Miami, Florida, USA, March 13-17 2005.

[DKR04] Antonios Deligiannakis, Yannis Kotidis, and Nick Roussopoulos.
Hierarchical in-network data aggregation with quality
guarantees. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04), pages
658-675, Heraklion, Crete, Greece, March 14-18 2004.

[EGPS01] D. Estrin, L. Girod, G. Pottie, and M. Srivastava. Instrumenting
the world with wireless sensor networks. In Proceedings of
the International Conference on Acoustics, Speech and Signal
Processing (ICASSP'01), Salt Lake City, Utah, USA, May 7-11 2001.

[FJK+05] Michael J. Franklin, Shawn R. Je ery, Sailesh Krishnamurthy,
Frederick Reiss, Shariq Rizvi, Eugene Wu, Owen Cooper, Anil
Edakkunni, andWei Hong. Design considerations for high fanin
systems: the HiFi approach. In Proceedings of the Second
Biennial Conference on Innovative Data Systems Research
(CIDR'05), Asilomar, California, USA, January 4-7 2005.

[Fra04] Michael Franklin. HiFi systems: Network-centric query processing
for the physical world. Stanford DB Seminar and the
NCSU Database Musings seminar series, February 13 2004.

[GEG+03] Benjamin Greenstein, Deborah Estrin, Ramesh Govindan,
Sylvia Ratnasamy, and Scott Shenker. DIFS: A distributed
index for features in sensor networks. In Proceedings of
First IEEE International Workshop on Sensor Network Protocols and Applications (SNPA'03), pages 163-173, Anchorage,
Alaska, USA, May 11 2003.

[GM04] Johannes Gehrke and Samuel Madden. Query processing in
sensor networks. IEEE Pervasive Computing, 3(1):46-55, January-March 2004.

[GSYS02] Soheil Ghiasi, Ankur Srivastava, Xiaojian Yang, and Majid
Sarrafzadeh. Optimal energy aware clustering in sensor netB
works. Sensors, Special Issue: Networked Sensors and Wireless Sensor Platforms, 2(7):258-269, July 2002.

[HB01] John Heidemann and Nirupama Bulusu. Using geospatial information
in sensor networks. In Proceedings of the the Workshop on Intersections between
Geospatial Information and Information Technology, Arlington, VA, USA, October 2001.

[HC02] Jason Hill and David Culler. Mica: A wireless platform for
deeply embedded networks. IEEE Micro, 22(6):12-24, 2002.

[HCB00] Wendi Rabiner Heinzelman, Anantha Chandrakasan, and
Hari Balakrishnan. Energy-e cient communication protocol
for wireless microsensor networks. In Proceedings of the
33rd Hawaii International Conference on System Sciences
(HICSS'00), pages Volume 8, page: 8020, Maui, Hawaii, USA,
January 4-7 2000.

[HHM03] Joseph M. Hellerstein, Wei Hong, and Samuel R. Madden.
The sensor spectrum: Technology, trends, and requirements.
ACM SIGMOD Record, 32(4):22-27, December 2003.

[HHMS03] Joseph M. Hellerstein, Wei Hong, Samuel Madden, and Kyle
Stanek. Beyond average: Towards sophisticated sensing with
queries. In Feng Zhao and Leonidas J. Guibas, editors, Proceedings of the Second International Symposium on
Information Processing in Sensor Networks (IPSN'03), pages 63-79,
Palo Alto, California, USA, April 22-23 2003. Springer.

[Hil03] Jason Hill. System Architecture for Wireless Sensor Networks.
PhD thesis, University of California, Berkeley, Spring 2003.

[HSW+00] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister.
System architecture directions for networked sensors.
ACM SIGOPS Operating Systems Review, 34:93-104, 2000.

[HT03] Chi-Fu Huang and Yu-Chee Tseng. The coverage problem
in a wireless sensor network. In Proceedings of the 2nd ACM
International Workshop on Wireless Sensor Networks and Applications (WSNA'03), pages 115-121, San Diego, California,
USA, September 19 2003.

[IEGH02] Chalermek Intanagonwiwat, Deborah Estrin, Ramesh Govindan,
and John Heidemann. Impact of network density on data
aggregation in wireless sensor networks. In Proceedings of the
22nd International Conference on Distributed Computing Systems (ICDCS'02), Vienna, Austria, July 2002.

[JP04] Apoorva Jindal and Konstantinos Psounis. Modeling
spatially-correlated sensor network data. In Proceedings
of IEEE International Conference on Sensor and Ad hoc
Communications and Networks (SECON'04), pages 162-171,
Santa Clara, California, USA, October 4-7 2004.

[KAK03] Hyung Seok Kim, Tarek F. Abdelzaher, and Wook Hyun
Kwon. Minimum-energy asynchronous dissemination to mobile
sinks in wireless sensor networks. In Proceedings of the
First ACM Conference on Embedded Networked Sensor Systems (SenSys'03), pages 193-204, Los Angeles, California,
USA, November 5-7 2003.

[KEW02] Bhaskar Krishnamachari, Deborah Estrin, and Stephen B.
Wicker. The impact of data aggregation in wireless sensor
networks. In Proceedings of the 22nd International Conference
on Distributed Computing Systems Workshops (ICDCSW'02),
pages 575-578, Vienna, Austria, July 02-05 2002.

[KI03] Bhaskar Krishnamachari and S. Sitharama Iyengar. E cient
and fault-tolerant feature extraction in wireless sensor networks.
In Proceedings of the Second International Symposium
on Information Processing in Sensor Networks (IPSN'03),
pages 488-501, Palo Alto, California, USA, April 22-23 2003.

[KI04] Bhaskar Krishnamachari and Sitharama Iyengar. Distributed
bayesian algorithms for fault-tolerant event region detection in
wireless sensor networks. IEEE Transactions on Computers,
53(3):241-250, March 2004.

[LKGH03] Xin Li, Young Jin Kim, Ramesh Govindan, and Wei Hong.
Multi-dimensional range queries in sensor networks. In Proceedings of
the First ACM International Conference on Embedded Networked Sensor Systems (SenSys'03), pages 63-75,
Los Angeles, California, USA, November 5-7 2003.

[LR02] Stephanie Lindsey and Cauligi S. Raghavendra. Pegasis:
Power-e cient gathering in sensor information systems. In
Proceedings of the IEEE Aerospace Conference, pages 1-6, Big
Sky, Montana, USA, March 2002.

[LSS03] Shuoqi Li, Sang Hyuk Son, and John A. Stankovic. Event detection
services using data service middleware in distributed
sensor networks. In Proceedings of the Second International
Symposium on Information Processing in Sensor Networks
(IPSN'03), pages 502-517, Palo Alto, California, USA, April
22-23 2003.

[MFHH02] Samuel Madden, Michael J. Franklin, Wei Hong, and
Joseph M. Hellerstein. TAG: a Tiny AGgregation service for
ad-hoc sensor networks. In Proceedings of the 5th Symposium
on Operation Systems Design and Implementation (OSDI'02),
pages 131-146, Boston, USA, December 2002.

[MFHH03] Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein,
and Wei Hong. The design of an acquisitional query processor
for sensor networks. In Proceedings of the 2003 ACM
SIGMOD International Conference on Management of Data
(SIGMOD'03), pages 491-502, San Diego, California, USA,
June 9-12 2003.

[MLNL04] Xiaoqiao Meng, Li Li, Thyaga Nandagopal, and Songwu Lu.
Event contour: An e cient and robust mechanism for tasks
in sensor networks. Technical Report TR-040018, Computer
Science Department, University of California, Los Angeles,
April 16 2004.

[MPS+02] Alan Mainwaring, Joseph Polastre, Robert Szewczyk, David
Culler, and John Anderson. Wireless sensor networks for
habitat monitoring. In Proceedings of the 1st ACM International Workshop on
Wireless Sensor Networks and Applications (WSNA'02), pages 88-97, Atlanta GA, September 28
2002.

[MSFC02] Samuel Madden, Robert Szewczyk, Michael J. Franklin, and
David Culler. Supporting aggregate queries over ad-hoc wireless sensor networks. In Proceedings of 4th IEEE Workshop on
Mobile Computing and Systems Applications (WMCSA'02),
pages 49-58, Callicoon, New York, USA, June 2002.

[NM03] Robert Nowak and Urbashi Mitra. Boundary estimation in
sensor networks: Theory and methods. In Proceedings of the
Second International Symposium on Information Processing
in Sensor Networks (IPSN'03), pages 80-95, Palo Alto, California,
USA, April 22-23 2003.

[NMW04] Robert Nowak, Urbashi Mitra, and Rebecca Willett. Estimating
inhomogeneous fields using wireless sensor networks. IEEE
Journal on Selected Areas in Communications, 22(6):999-1006, August 2004.

[Orc] China Orchid. http://www.chinaorchid.net/.

[PKM04] Tri Pham, Eun Jik Kim, and Melody Moh. On data aggregation
quality and energy e ciency of wireless sensor network
protocols - extended summary. In Proceedings of the First
International Conference on Broadband Networks (BROADNETS'04), pages 730-732, San Jose, California, USA, October
25-29 2004.

[SBP04] Mitali Singh, Amol Bakshi, and Viktor K. Prasanna. Constructing
topographic maps in networked sensor systems. In
Proceedings of the Workshop on AlgorithmS for Wireless and
mobile Networks (ASWAN'04), Boston, Massachusetts, USA,
August 26 2004.

[SOP+04] Robert Szewczyk, Eric Osterweil, Joseph Polastre, Michael
Hamilton, Alan Mainwaring, and Deborah Estrin. Habitat
monitoring with sensor networks. Communications of the
ACM, Special Issue: Wireless Sensor Networks, 47(6):34-40,
2004.

[SP05] Mitali Singh and Viktor K. Prasanna. Supporting topographic
queries in a class of networked sensor systems. In Proceedings of the First International Workshop on Sensor Networks
and Systems for Pervasive Computing (PerSeNS'05), Kauai
Island, Hawaii, USA, March 8-12 2005.

[Sun03] Digital Sun. S.sense wireless sensors,
http://www.digitalsun.com/, 2003.

[VAA04] Mehmet C. Vuran,  Ozgur B. Akan, and Ian F. Akyildiz.
Spatio-temporal correlation: Theory and applications for
wireless sensor networks. Computer Networks, 45(3):245-259,
2004.

[YERG04] Yan Yu, Deborah Estrin, Mohammad Rahimi, and Ramesh
Govindan. Using more realistic data models to evaluate sensor
network data processing algorithms. In Proceedings of 29th
Annual IEEE International Conference on Local Computer
Networks (LCN'04), pages 569-570, Tampa, Florida, USA,
November 16-18 2004.

[YF04a] Ossama Younis and Sonia Fahmy. Distributed clustering
in ad-hoc sensor networks: A hybrid, energy-e cient approach.
In Proceedings of the 23th Annual Joint Conference
of the IEEE Computer and Communications Societies (InfoCom'04), pages 629-640, Hong Kong, China, March 7-11 2004.

[YF04b] Ossama Younis and Sonia Fahmy. Heed: A hybrid, energye
cient, distributed clustering approach for ad-hoc sensor networks.
IEEE Transactions on Mobile Computing, 3(4):366-379, October-December 2004.

[YGG+03] Yan Yu, Deepak Ganesan, Lewis Girod, Ramesh Govindan,
and Deborah Estrin. Synthetic data generation to support
irregular sampling in sensor networks. In Proceedings of
NSF Workshop on GeoSensor Networks (GSN'03), Portland,
Maine, USA, October 9-11 2003.

[ZGE03] Jerry Zhao, Ramesh Govindan, and Deborah Estrin. Computing
aggregates for monitoring wireless sensor networks. In Proceedings of the first IEEE International Workshop on Sensor
Network Protocols and Applications (SNPA'03), pages 139-148, Anchorage, Alaska, USA, May 11 2003.