# 臺灣博碩士論文加值系統

(100.26.196.222) 您好！臺灣時間：2024/02/27 15:17

:::

### 詳目顯示

:

• 被引用: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 12 Preliminaries 83 Algorithm SB: Selecting Backbones 123.1 Determining Edges and Weights among Query Trees . . . . . . . . . . . . . . . 123.2 Design of Algorithm SB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Algorithm OOB: Obtaining Optimal Backbones 225 Performance Evaluation 285.1 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.2 The Impact of Sharing Partial Results . . . . . . . . . . . . . . . . . . . . . . 295.3 Time Complexity Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.4 Performance of Algorithm SB . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 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 managementapplications. 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 overstreaming sensor data. In ICDE, 2002.[6] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tag: A tiny aggregationservice for ad-hoc sensor networks. In OSDI, 2002.[7] S. Madden, M. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuousqueries 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 queriesover 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 acquisitionalquery 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 sensornetworks for habitat monitoring. In ACM International Workshop on Wireless SensorNetworks and Applications (WSNA’02), Atlanta, GA, Sept. 2002.[11] N. J. Nilsson. Principles of arti…cial intelligence. Morgan Kaufmann Publishers Inc., SanFrancisco, 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 andquality 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 thepower consumption of large-scale sensor network applications. In SenSys ’04: Proceedingsof 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 optimizationfor 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 sensornetworks. SIGMOD Record, 31(3):9–18, 2002.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 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年。

 1 利用資料涵蓋觀念解決無線感測網路中之近似查詢處理 2 具無線網路功能之數位錄影機的設計與實現 3 液相法製造程序對中孔洞沸石型吸附材特性及其丙酮吸附量影響之研究 4 利用官能化磁性粒子為萃取赭麴毒素A的探針及對掌性色胺酸的分離靜相 5 應用官能化磁性奈米粒子為含組胺酸標記及磷酸化蛋白質/胜肽之親和探針 6 以小世界社會網路為基礎的病媒性疾病模型: 7 藍光螢光粉劣化與螢光粉塗料之研究 8 二維奈米平板鑽石之合成及其微結構分析之研究 9 公共領域在數位環境中面臨的衝擊 10 自動光學檢測設備公司於平面顯示器產業之發展策略 11 QFT/H∞強健控制理論應用於防震伺服控制系統之研究 12 以眼動波應用於人機介面之眼滑鼠 13 以手指靜脈和關節紋為基礎的圖形萃取和辨識研究 14 MPEG-2/4低複雜度先進音訊編碼最佳化及雙核心處理器實現 15 具備多工排程功能之無線嵌入式腦機介面系統及其在即時汽車駕駛員疲勞狀態偵測與提醒之應用

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室