臺灣博碩士論文加值系統

在無線感測器網路中，儲存感測器所感測到資料的策略會影響整個網路所產生的訊息量，如果可以使用合適的儲存策略來減少不必要的訊息傳送，整個網路所消耗的總電量將會減少，進而增加整個網路的運作時間。這篇論文首先提出了一個效率的資料儲存的方法，這個方法將感測到的資料儲存儲存在感測器本身，並以低通訊成本的鏈結串列(Linked List)來維護資料彼此之間的關係。這個資料的關連性是隨著物體事件移動自動建立，完整的資料可以從偵測到起始事件的感測器來取得完整資料。當感測器的儲存空間不足時，資料的連結將部份重建，將資料分散到鄰近的感測器上。另一方面，某些應用所感測到的事件是區域性，資料並不是一個物體的位置，因此無法使用所提出的資料鏈結串列演算法，本文針對這種不特定形狀的事件型態提出一個自動適應環境改變的演算法，動態變更儲存機制來減少訊息量。透過分析區域的Query Rate及Event Rate，我們提出的自動適應環境的演算法會決定應該選擇Local Storage Policy或Data Centric Policy。最後，本文將以分析和模擬的結果來驗證所提出的演算法確實能減少訊息量以及增加網路的運作時間。

In wireless sensor networks, storage policy of sensed event affects the number of required control messages. If the number of control message can be reduced, the network lifetime can be increased because transmitting unnecessary control message requires extra energy consumption. In this paper, a local storage method with small control overhead is proposed for object tracking applications in wireless sensor network. The main idea of the proposed method is to store the detected events in local storage and to maintain the relation of the sensed data through a low cost implicit linked list among sensor nodes. When an object moves across the sensing field, detecting sensor can construct a linked list automatically along the moving path of the object. The stored event records can be extracted by tracing the linked list from head to tail to get the complete information. When the memory space in a sensor node is full, a link reconstruction mechanism is proposed to distribute the heavy loads of sensor nodes to nearby nodes. For applications besides object tracking, the linked list data storage policies are not applicable. To reduce the total amount of message, an adaptive storage policy is also proposed. Based on the query rate and event rate, the proposed adaptive storage policy can switches between data centric and local storage. Finally, performance analysis and simulation have been conducted to verify that the proposed method can reduce the amount of control messages and increase the network lifetime.

目錄
1. 簡介 8
1.1. 研究背景 8
1.2. 研究動機 11
1.3. 研究目的 16
1.4. 研究方法 17
1.5. 本文貢獻 18
1.6. 章節安排 19
2. 文獻探討 20
3. 省電之資料儲存策略 23
3.1. 網路模型 24
3.2. 鏈結串列資料結構 25
3.3. 資料收集的程序 30
3.4. 資料滿載的問題 33
3.4.1. 資料搬移 34
3.4.2. 資料整合 41
3.4.3. 資料丟棄 42
3.5. 多鏈結資料結構 42
3.6. 機動性 46
3.7. Linked List資料儲存策略效能分析 47
3.8. 模擬 55
4. 自適性資料儲存策略 57
4.1. 系統模組 59
4.2. 策略轉換 60
4.3. 資料收集的程序 64
4.4. 負載平衡 65
4.5. 效能分析 66
4.6. 模擬 68
5. 討論 70
6. 結論 72
7. 參考文獻 73
圖目錄
圖 1：EXTERNAL STORAGE 12
圖 2：DATA-CENTRIC STORAGE 13
圖 3：LOCAL STORAGE 14
圖 4：LINK TO FORWARD NODE的儲存方式 26
圖 5：LINK TO BACKWARD NODE的儲存方式 27
圖 6：LINKED LIST 建立演算法 30
圖 7：使用者QUERY的過程 31
圖 8：LINKED LIST 建立演算法 32
圖 9：迴圈的鏈狀結構 33
圖 10：LINK TO FORWARD NODE的資料轉移 35
圖 11：LINK TO BACKWARD NODE 的資料轉移 35
圖 12：LINK TO FORWARD NODE的資料轉移 37
圖 13：LINK TO FORWARD NODE的資料轉移 37
圖 14：LINK TO FORWARD NODE產生的問題 38
圖 15：LINKS REBUILD後的結果 40
圖 16：LINK REBUILD演算法 41
圖 17：MULTI-LINK DATA STRUCTURE 44
圖 18：MULTI-LINKED LIST 建立演算法 46
圖 19：三種儲存方式的比較 50
圖 20：EXTERNAL STORAGE VS. ENERGY EFFICIENT DATA STORAGE 53
圖 21：QUERY成功的機率和備份點數以及故障機率比的關係 54
圖 22：在不同感測器數量的網路環境之最低電量 56
圖 23：GHT文中所提出的資料儲存策略 59
圖 24：自適性儲存策略演算法 64
圖 25：訊息量隨著事件增加的關係圖 67
圖 26：訊息量隨著詢問次數增加的關係圖 67
圖 27：QUERY RATE和EVENT RATE在各個時間點的大小 69
圖 28：在不同QUERY頻率的總電量消耗狀況 69
表目錄
表 1：模擬的參數設定 55

[1]Jian Chen, Yong Guan and Udo Pooch, “An efficient data dissemination method in wireless sensor networks,” IEEE Global Telecommunications Conference (GLOBECOM), December 2004, pp. 3200-3204.
[2]Jian Chen, Yong Guan, and Udo Pooch, “A spatial-based multi-resolution data dissemination scheme for wireless sensor networks,” 19th IEEE International Parallel and Distributed Processing Symposium, April 2005, pp. 1-8.
[3]Ratnabali Biswas, Kaushik Chowdhury, and Dharma P. Agrawal, “Data-centric attribute allocation and retrieval (DCAAR) scheme for wireless sensor networks,” IEEE International Conference on Mobile Adhoc and Sensor Systems Conference (MASS), November 2005, pp. 7-10.
[4]Alexandros G. Dimakis, Vinod Prabhakaran, and Kannan Ramchandran, “Distributed data storage in sensor networks using decentralized erasure codes,” Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, November 2004, pp. 1387-1391.
[5]Chia-Hsing Hou, Hung-Chang Hsiao, Chung-Ta King, and Chun-Nan Lu, “Context discovery in sensor networks,” 3rd International Conference on Information Technology: Research and Education, June 2005, pp. 2-6.
[6]Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, and Fabio Silva, “Directed diffusion for wireless sensor networking,” IEEE/ACM Transactions on Networking, Vol. 11, Issue 1, February 2003, pp. 2-16.
[7]Seada Karim and Helmy Ahemd, “Rendezvous regions: a scalable architecture for service location and data-centric storage in large-scale wireless networks,” IEEE International Parallel and Distributed Processing Symposium (IPDPS), April 2004, pp.218.
[8]Brad Karp, and Hsiang-Tsung Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom), August 2000, pp. 243-254.
[9]Olaf Landsiedel and Katharina Anna Lehmann, and Klaus Wehrle, “T-DHT: topology-based distributed hash tables,” Fifth IEEE International Conference on Peer-to-Peer Computing, August 2005., pp. 143-144.
[10]Cai Le and Yung-Hsiang Lu, “Energy management using buffer memory for streaming data,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, February 2005, pp. 141-152.
[11]Thang Nam Le, Dong Xuan, and Wei Yu, “An adaptive zone-based storage architecture for wireless sensor networks,” IEEE Global Telecommunications Conference (GLOBECOM), December 2005, pp. 1-5.
[12]Chih-Yu Lin and Yu-Chee Tseng, “Structures for in-network moving object tracking in wireless sensor networks,” First International Conference on Broadband Networks, October 2004, pp. 718-727.
[13]Chih-Yu Lin, Wen-Chih Peng, and Yu-Chee Tseng, “Efficient In-Network Moving Object Tracking in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 5, August 2006, pp. 1044-1056.
[14]Hong Lin, John Rushing, Sara J. Graves, Steve Tanner, and Evans Criswell, “Real time target tracking with binary sensor networks and parallel computing,” IEEE International Conference on Granular Computing, May 2006, pp.112-117.
[15]Chenyang Lu, Guoliang Xing, Octav Chipara, Chien-Liang Fok, and Sangeeta Bhattacharya, “A Spatiotemporal Query Service for Mobile Users in Sensor Networks,” 25th IEEE International Conference on Distributed Computing Systems, June 2005, pp. 381-390.
[16]Sylvia Ratnasamy, Bard Karp, Yin Li, Fang Yu, Ramesh Govindan, Scott Shenker, and Deborah Estrin, “A Geographic Hash Table for Data-Centric Storage,” ACM Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), September 2002, pp. 78-87.
[17]Sylvia Ratnasamy, Deborah Estrin, Ramesh Govindan, Bard Karp, Scott Shenker, Yin Li, and Fang Yu, “Data-Centric Storage in Sensornets,” ACM Proceedings of the First Workshop on Sensor Networks and Applications (WSNA), Vol. 3, September 2002, pp. 137-142.
[18]Ravinder Tamishetty, Lek Heng Ngoh, and Pung Hung Keng, “An efficient resiliency scheme for data centric storage in wireless sensor networks,” IEEE 60th Vehicular Technology Conference, September 2004, pp. 2936-2940.
[19]Jeong-Hun Shin, Jaesub Kim, Keuntae Park, and Daeyeon Park, ”Railroad: virtual infrastructure for data dissemination in wireless sensor networks,” Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 2005, pp. 178-174.
[20]Minji Wu, Jianliang Xu, and Xueyan Tang, “Processing Precision-Constrained Approximate Queries in Wireless Sensor Networks,” 7th International Conference on Mobile Data Management, May 2006, pp. 31-31.
[21]Ping Xia, Panos K. Chrysanthis, and Alexandros Labrinidis, “Similarity-aware query processing in sensor networks,” 20th International on Parallel and Distributed Processing Symposium, April 2006, pp. 1-8.
[22]Kai Xing, Xiuzhen Cheng, and Jiang Li, ”Location-centric storage for sensor networks,” IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, November 2005, pp. 10.
[23]Wei Yu, Thang Nam Le, Dong Xuan and Wei Zhao, “Query aggregation for providing efficient data services in sensor networks,” IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), October 2004, pp. 31-40.
[24]Rong Zheng, Guanghui He, Gupta Indranil, and Lui Sha, “Time indexing in sensor networks,” IEEE International Conference on Mobile Ad-hoc and Sensor Systems, October 2004, pp. 274-283.
[25]Wensheng Zhang and Guohong Cao, ”An energy efficient framework for mobile target tracking in sensor networks,” IEEE Military Communications Conference (MILCOM), Vol. 1, October 2003, pp. 597-602.
[26]Wensheng Zhang and Guohong Cao, “DCTC: dynamic convoy tree-based collaboration for target tracking in sensor networks,” IEEE Transactions on Wireless Communications, Vol. 3, Issue 5, September 2004, pp. 1689-1701.
[27]Wensheng Zhang, Guohong Cao and La Porta Tom, “Dynamic proxy tree-based data dissemination schemes for wireless sensor networks”, IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), October 2004, pp. 21-30.
[28]Wensheng Zhang, Guohong Cao and La Porta Tom, “Data dissemination with ring-based index for wireless sensor networks,” 11th IEEE International Conference on Network Protocols, November 2003, pp. 305-341.
[29]Crossbow Technology MPR4x0 – MICA2 series, http://www.xbow.com/.
[30]The network simulator – ns-2, http://www.isi.edu/nsnam/ns.