跳到主要內容

臺灣博碩士論文加值系統

(100.26.196.222) 您好!臺灣時間:2024/02/27 15:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:楊慧友
研究生(外文):Huei-You Yang
論文名稱:在感測網路中針對多個網路中彙整的查詢做最佳化來節省電量
論文名稱(外文):Optimizing Multiple In-network Aggregate Queries in Wireless Sensor Networks for Power Saving
指導教授:彭文志彭文志引用關係
指導教授(外文):Wen-Chih Peng
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學與工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:39
中文關鍵詞:網路中彙整查詢查詢最佳化無線感測網路
外文關鍵詞:In-network aggregate queryQuery optimizationWireless sensor networks
相關次數:
  • 被引用被引用:0
  • 點閱點閱:102
  • 評分評分:
  • 下載下載:11
  • 收藏至我的研究室書目清單書目收藏:0
在無線感測網路的監測應用中,查詢常常是長時間執行在特定週期當中。由於每個查詢是單獨的被處理,當查詢的數目增加時無線感測網路所耗費的能量是可觀的。在這篇論文當中,我們探討在多個查詢間分享他們的中繼資料來降低整體耗費的訊息的方式中所具有的特性。分享自身資料的查詢被稱為骨幹。給定一些查詢,我們要決定可以使訊息傳輸數量降至最低的那些查詢當做骨幹。更精確的說,我們首先將選擇骨幹的問題以數學的形式做正規的描述並將他轉換成Max-cut的問題。具體來說,給定一些查詢,我們從它們衍生出一個圖,其上的每一點是代表一個查詢,而相對的邊以及權重則代表經由分享中繼資料可以節省多少數量的訊息。根據衍生出來的圖,我們設計一個經由觀察而設計的演算法SB(全名為Selecting Backbones)去在圖上切分來決定骨幹。為了評估演算法SB所得到的結果,我們設計了一個演算法OOB(全名為Obtaining Optimal Backbones)來得到最佳解。這些演算法的效能被相互比較,以及分析它們對環境參數的敏感度,如查詢的數量以及查詢資料來源的分布等等。由實驗結果可得知,藉由分享中繼資料,演算法SB大幅度降低了所需耗費的訊息數量,因此解省了可觀的能源。
In monitoring applications of wireless sensor networks, queries are typically long-running and
executed over a specified period. Since each query is independently performed, wireless sensor networks
consume a considerable amount of energy when the number of queries increases. In this paper, we explore the feature of sharing
partial results of multiple queries so as to reduce the total number of messages incurred. Those queries sharing their partial results are referred to backbones.
Given a set of queries, we shall determine backbones with the purpose of minimizing the total number of messages. Explicitly, we first formulate the problem of selecting backbones and transform this problem into Max-Cut problem.
Specifically, given a set of queries, we derive a graph, where each vertex represents one query and the corresponding weight edge denotes the number of messages
reduced by sharing the partial results. According to the graph derived, we develop a heuristic algorithm SB (standing for Selecting Backbones) to derive a cut in which both backbones and non-backbones are determined. In order to evaluate the solution quality obtained by algorithm SB and compare its resulting backbone set with the optimal one, we devise an algorithm OOB (standing for Obtaining Optimal Backbones) to obtain the optimal solution.
Performance of these algorithms is comparatively analyzed and sensitivity analysis on several parameters, including the number of queries and the distribution of data sources for queries, is conducted. It is shown by our simulation results that by sharing the partial results, algorithm SB is able to significantly reduce the total number of messages, thereby saving a considerable amount of energy.
1 Introduction 1
2 Preliminaries 8
3 Algorithm SB: Selecting Backbones 12
3.1 Determining Edges and Weights among Query Trees . . . . . . . . . . . . . . . 12
3.2 Design of Algorithm SB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Algorithm OOB: Obtaining Optimal Backbones 22
5 Performance Evaluation 28
5.1 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.2 The Impact of Sharing Partial Results . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Time Complexity Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.4 Performance of Algorithm SB . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6 Conclusion 36
[1] I. Akyildiz,W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks,
2002.
[2] D. Carney, U. Çetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker,
N. Tatbul, and S. B. Zdonik. Monitoring streams - a new class of data management
applications. In VLDB, pages 215–226, 2002.
[3] S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J.M. Hellerstein,W. Hong,
S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah. Telegraphcq:
Continuous data‡ow processing for an uncertain world. In CIDR, 2003.
[4] S. Chandrasekaran and M. J. Franklin. Streaming queries over streaming data. In VLDB,
pages 203–214, 2002.
[5] S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over
streaming sensor data. In ICDE, 2002.
[6] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tag: A tiny aggregation
service for ad-hoc sensor networks. In OSDI, 2002.
[7] S. Madden, M. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuous
queries over streams. In SIGMOD ’02: Proceedings of the 2002 ACM SIGMOD inter-
national conference on Management of data, pages 49–60, New York, NY, USA, 2002.
ACM Press.
[8] S. Madden, R. Szewczyk, M. J. Franklin, and D. E. Culler. Supporting aggregate queries
over ad-hoc wireless sensor networks. In WMCSA, pages 49–58. IEEE Computer Society,
2002.
[9] S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tinydb: an acquisitional
query processing system for sensor networks. ACM Trans. Database Syst., 30(1):122–173,
2005.
[10] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson. Wireless sensor
networks for habitat monitoring. In ACM International Workshop on Wireless Sensor
Networks and Applications (WSNA’02), Atlanta, GA, Sept. 2002.
[11] N. J. Nilsson. Principles of arti…cial intelligence. Morgan Kaufmann Publishers Inc., San
Francisco, CA, USA, 1980.
[12] G. J. Pottie and W. J. Kaiser. Wireless integrated network sensors. Commun. ACM,
43(5):51–58, 2000.
[13] A. Sharaf, J. Beaver, A. Labrinidis, and K. Chrysanthis. Balancing energy e¢ ciency and
quality of aggregate data in sensor networks. The VLDB Journal, 13(4):384–403, 2004.
[14] V. Shnayder, M. Hempstead, B. rong Chen, G. W. Allen, and M. Welsh. Simulating the
power consumption of large-scale sensor network applications. In SenSys ’04: Proceedings
of the 2nd international conference on Embedded networked sensor systems, pages 188–
200, New York, NY, USA, 2004. ACM Press.
[15] N. Trigoni, Y. Yao, A. J. Demers, J. Gehrke, and R. Rajaraman. Multi-query optimization
for sensor networks. In V. K. Prasanna, S. S. Iyengar, P. G. Spirakis, and M. Welsh,
editors, DCOSS, volume 3560 of Lecture Notes in Computer Science, pages 307–321.
Springer, 2005.
[16] Y. Yao and J. Gehrke. The cougar approach to in-network query processing in sensor
networks. SIGMOD Record, 31(3):9–18, 2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 馬森〈誰來為張愛玲定位?——評張愛玲小說的時代感〉,收入《中外文學》第24卷第10期,1996年。
2. 馬森〈誰來為張愛玲定位?——評張愛玲小說的時代感〉,收入《中外文學》第24卷第10期,1996年。
3. 高全之〈那人正在燈火闌珊處——張愛玲如何三思「五四」〉,收入《當代》第176期,2002年。
4. 高全之〈那人正在燈火闌珊處——張愛玲如何三思「五四」〉,收入《當代》第176期,2002年。
5. 馬莊穆 著、于錫娟 譯〈由張愛玲看中國傳統在文學中的優點〉,收入《文季》第3期,1974年。
6. 馬莊穆 著、于錫娟 譯〈由張愛玲看中國傳統在文學中的優點〉,收入《文季》第3期,1974年。
7. 袁瓊瓊〈張愛玲記〉,收入《聯合文學》第11期,1995年。
8. 袁瓊瓊〈張愛玲記〉,收入《聯合文學》第11期,1995年。
9. 范銘如〈文化.空間.嬝狀F治——蘇偉貞的「孤島張愛玲」〉,收入《聯合文學》第209期,2002年。
10. 范銘如〈文化.空間.嬝狀F治——蘇偉貞的「孤島張愛玲」〉,收入《聯合文學》第209期,2002年。
11. 范伯群、季進〈論張愛玲的前期小說創作〉,收入《中國現代文學理論》第10期,1998年。
12. 范伯群、季進〈論張愛玲的前期小說創作〉,收入《中國現代文學理論》第10期,1998年。
13. 林幸謙〈女性焦慮與醜怪身體:論張愛玲小說中的女性亞文化群體〉,《中外文學》第27卷第6期,1998年。
14. 林幸謙〈女性焦慮與醜怪身體:論張愛玲小說中的女性亞文化群體〉,《中外文學》第27卷第6期,1998年。
15. 林幸謙〈重讀《怨女》:尋找女性和他者的聲音〉,收入《中國現代文學理論》第12期,1998年。